劉浩然，王星淇，覃玉華，鄧玉靜，尹榮榮

(燕山大學(xué)信息科學(xué)與工程學(xué)院，河北秦皇島 066004;燕山大學(xué)河北省特種光纖與光纖傳感重點實驗室，河北秦皇島 066004)

1 引言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)是由大量微型傳感器節(jié)點通過無線通信的方式，自組織形成的一個多跳分布式網(wǎng)絡(luò)系統(tǒng).目前應(yīng)用于環(huán)境監(jiān)測[1]、軍事偵察[2]、智能交通網(wǎng)絡(luò)[3]、電力網(wǎng)絡(luò)[4]和物流配送網(wǎng)絡(luò)[5]等領(lǐng)域，有著廣泛的應(yīng)用前景.網(wǎng)絡(luò)抗毀性[6]是指當網(wǎng)絡(luò)受到選擇性或隨機性攻擊時，網(wǎng)絡(luò)維持或恢復(fù)其性能到一個可接受程度的能力，作為WSNs的一種重要特性，其理論意義和應(yīng)用價值日益受到人們的關(guān)注和重視.如何構(gòu)建具有良好抗毀性的有向無標度網(wǎng)絡(luò)拓撲，成為WSNs面臨的一個重要挑戰(zhàn).目前，對于WSNs抗毀性拓撲的研究，大多建立在經(jīng)典無標度BA(Albert-László Barabási and Réka Albert)模型基礎(chǔ)上[7]，通過引入抗毀性相關(guān)參數(shù)因素，達到提高網(wǎng)絡(luò)抗毀性的目的.文獻[8]借助節(jié)點批量到達的Poisson網(wǎng)絡(luò)模型，提出了一種WSNs無標度容侵優(yōu)化拓撲(scale-free intrusion-tolerance optimization topology，SIOT)模型，通過優(yōu)化拓撲中的冪律指數(shù)提高網(wǎng)絡(luò)容侵性.文獻[9]通過減少網(wǎng)絡(luò)度分布的程度，建立了理論模型增加系統(tǒng)在惡意攻擊和隨機攻擊下相關(guān)網(wǎng)絡(luò)的抗毀性.文獻[10]在添加連接鏈路的基礎(chǔ)上提出一種輔助優(yōu)先附件策略，提高了相互依賴網(wǎng)絡(luò)的魯棒性.文獻[11]基于最短路徑，通過合理分配有限成本，添加連接鏈路和依賴鏈路，所構(gòu)建拓撲比只添加連接鏈路或依賴鏈路具有更強的抗毀性.文獻[8-11]多是從節(jié)點度或介數(shù)中心性相關(guān)理論角度提出策略或生成拓撲進行研究，雖然均在一定程度上提升了WSN的抗毀性，但是考慮角度比較單一，在優(yōu)化網(wǎng)絡(luò)抗毀性上仍存在局限性，且添加連接鏈路的方式大大增加了計算連接條件的復(fù)雜度，難以應(yīng)用于工程實踐.文獻[12]結(jié)合路徑中心性和節(jié)點度，提出路徑算子演化中心(path operator calculus centrality，POCC)，一定程度上提高了網(wǎng)絡(luò)的能耗和性能.文獻[13]從節(jié)點度和介數(shù)中心性兩方面建立了無標度網(wǎng)絡(luò)的魯棒性模型，有效地增強了無標度網(wǎng)絡(luò)對級聯(lián)失效的抗毀性.上述文獻雖從不同角度對網(wǎng)絡(luò)抗毀性進行大量研究，但均未考慮實際數(shù)據(jù)傳輸過程中的有向性.為了將WSNs相關(guān)理論更廣泛地應(yīng)用到人類生產(chǎn)生活和實踐當中，許多學(xué)者對有向網(wǎng)絡(luò)的研究進行了一系列深入探索，文獻[14]通過引入了一種定量標準來描述有向網(wǎng)絡(luò)社區(qū)，并利用馬爾可夫鏈蒙特卡洛(Markov chain Monte Carlo，MCMC)隨機搜索技術(shù)優(yōu)化有向局部社區(qū)結(jié)構(gòu)，同時提高其抗毀性.文獻[15]利用等價變換和相關(guān)劃分，研究了有向加權(quán)符號網(wǎng)絡(luò)(multiagent system，MAS)的能控性和穩(wěn)定性.文獻[16]同時考慮了單向拓撲和雙向拓撲，證明了在聯(lián)合強連通和無線聯(lián)合連通時，網(wǎng)絡(luò)的一致性問題.雖然文獻[14-16]對有向網(wǎng)絡(luò)相關(guān)問題進行了探索，但對抗毀性的研究不夠深入，更沒有在全局性和局域性角度全面考慮提升抗毀性的因素.而實際應(yīng)用中，有向網(wǎng)絡(luò)承受惡意攻擊的能力對于網(wǎng)絡(luò)持續(xù)有效地運行有著至關(guān)重要的作用.

基于以上分析，本文結(jié)合節(jié)點出入度和介數(shù)中心性兩種抗毀性因素，同時考慮網(wǎng)絡(luò)數(shù)據(jù)傳輸過程中的有向性，以提高有向網(wǎng)絡(luò)面對不同攻擊方式的抗毀性為目標，構(gòu)建了可以衡量網(wǎng)絡(luò)抗毀性的抗毀性度量模型.繼而將其引入節(jié)點擇優(yōu)連接概率中，構(gòu)建了具有抗毀性的有向傳感網(wǎng)絡(luò)拓撲模型(destruction resistant topology model of directed sensing network，DRTD)，并通過理論和仿真證明通過本文方法構(gòu)建的拓撲模型具有強抗毀性.

2 抗毀性度量模型

WSNs網(wǎng)絡(luò)抗毀性是指當網(wǎng)絡(luò)中的節(jié)點或邊發(fā)生故障或遭受攻擊時，網(wǎng)絡(luò)拓撲結(jié)構(gòu)保持連通的能力[17].本節(jié)從全局性和局域性角度出發(fā)，結(jié)合基于最短路徑數(shù)的介數(shù)中心性及節(jié)點自身特性的節(jié)點出入度兩種因素，構(gòu)建抗毀性度量模型，衡量節(jié)點的重要性及其對網(wǎng)絡(luò)抗毀性的影響程度，公式為

其中:i為節(jié)點編號，A表示鄰居節(jié)點的集合.為全局抗毀因子，由單獨節(jié)點和總體介數(shù)中心性的比值構(gòu)成.介數(shù)中心性是衡量節(jié)點重要性的指標之一，其定義為網(wǎng)絡(luò)中所有最短路徑中經(jīng)過某一節(jié)點的路徑數(shù)目在最短路徑總數(shù)中占有的比例[18]，它體現(xiàn)了節(jié)點傳輸數(shù)據(jù)時可選擇路徑的多少.對于有向網(wǎng)絡(luò)，數(shù)據(jù)沿著不同方向傳輸時，最短路徑也會改變，導(dǎo)致節(jié)點傳出數(shù)據(jù)時的介數(shù)中心性BCi(out)和接收數(shù)據(jù)時的介數(shù)中心性BCi(in)不相等，二者分別表示用經(jīng)過節(jié)點的出度路徑數(shù)目和入度路徑數(shù)目刻畫該節(jié)點重要性的指標.在數(shù)據(jù)傳輸過程中，節(jié)點之間是否有可選擇的冗余鏈路是網(wǎng)絡(luò)具有抗毀性的主要原因.因此，介數(shù)中心性反映了相應(yīng)的節(jié)點在整個網(wǎng)絡(luò)中的作用和影響力，參考文獻[18]中的定義，介數(shù)中心性的公式為

其中:n為網(wǎng)絡(luò)節(jié)點數(shù);σkt(i)為節(jié)點k到節(jié)點t的最短路徑經(jīng)過節(jié)點i的次數(shù);σkt為節(jié)點k和節(jié)點t之間最短路徑數(shù).最短路徑是網(wǎng)絡(luò)中節(jié)點數(shù)據(jù)傳輸?shù)闹匾緩?，在網(wǎng)絡(luò)面臨攻擊和破壞的情況時，最短路徑數(shù)越多，數(shù)據(jù)傳輸途徑的選擇越多，網(wǎng)絡(luò)抗毀性越強.因此節(jié)點間最短路徑數(shù)對于提升網(wǎng)絡(luò)抗毀性有著重要意義[19].

由式(1)可知，抗毀性度量值與節(jié)點的介數(shù)中心性和節(jié)點度的變化呈正比關(guān)系.當網(wǎng)絡(luò)不夠均勻時，處于重要位置的度大節(jié)點較少，絕大多數(shù)節(jié)點的抗毀性度量值過小甚至趨于零，網(wǎng)絡(luò)面對選擇性攻擊的抗毀性較差;反之，當網(wǎng)絡(luò)足夠均勻時，節(jié)點之間互異性較小，抗毀性度量值大的重要節(jié)點較多，網(wǎng)絡(luò)面對選擇性攻擊的抗毀性較強.

3 抗毀性有向網(wǎng)絡(luò)模型拓撲及動態(tài)特性分析

假設(shè)節(jié)點均勻部署在無線傳感器網(wǎng)絡(luò)中.為了獲取具有抗毀性的有向拓撲模型，解決有向WSNs面對不同攻擊方式時抗毀性較差的問題，將抗毀性度量模型引入到WSNs拓撲節(jié)點的出入邊擇優(yōu)連接概率中，演化生成出具有抗毀性的有向網(wǎng)絡(luò)拓撲結(jié)構(gòu)，并對其進行動態(tài)特性分析.

3.1 DRTD演化模型

由于網(wǎng)絡(luò)中節(jié)點的通信半徑有限，當有新的節(jié)點加入到網(wǎng)絡(luò)時，在只考慮局部信息的情況下，通過對其進行擇優(yōu)連接來構(gòu)建局域世界.再根據(jù)節(jié)點總是將接收到的數(shù)據(jù)向sink節(jié)點傳播這一方向性，結(jié)合無標度理論，將節(jié)點發(fā)送與接收時的抗毀性度量分別引入到節(jié)點出邊和入邊擇優(yōu)連接過程中.類似于經(jīng)典BA模型，同樣將DRTD算法分為增長和擇優(yōu)連接兩部分，構(gòu)建的演化模型具體描述如下:

1) 增長:由m0個節(jié)點，e0條有向邊任意相連而組成的初始網(wǎng)絡(luò).在每個時間步長內(nèi)，新加入的節(jié)點new與網(wǎng)絡(luò)中已存在的m ＜m0個節(jié)點相連，形成新的有向網(wǎng)絡(luò).

2) 有向局域世界擇優(yōu)連接:新節(jié)點new的M1個鄰居組成它的出度局域世界，用A1表示;M2個鄰居組成它的入度局域世界，用A2表示，同時引入?yún)?shù)p∈[0，1].

節(jié)點和邊的增長規(guī)律遵循以下原則:

①pm條有向邊將新節(jié)點new與網(wǎng)絡(luò)中的已存在的pm個節(jié)點相連，連接概率與當前節(jié)點的介數(shù)中心性和出度有關(guān)，邊的方向都是從節(jié)點new指向己經(jīng)存在的節(jié)點.該節(jié)點i被選擇的概率為

②其余的(1-p)m條有向邊與網(wǎng)絡(luò)中剩下的(1-p)m個節(jié)點相連，邊的方向都是從網(wǎng)絡(luò)中已經(jīng)存在的節(jié)點指向新節(jié)點new.該節(jié)點i被選擇的概率為

經(jīng)過t時間步后，將形成一個具有N=m0+t個節(jié)點，mt+e0條有向邊的無標度網(wǎng)絡(luò).

從DRTD演化模型可以看出，節(jié)點在進行擇優(yōu)連接時，同時考慮了全局抗毀因子和局域抗毀因子兩種因素.下面通過對DRTD演化模型動態(tài)性能進行分析，分別得到拓撲的出度和入度的度分布表達式.

3.2 DRTD模型動態(tài)特性分析

借助Mean-Field理論來分析有向網(wǎng)絡(luò)中出度和入度的度分布，解析得到網(wǎng)絡(luò)中節(jié)點的出度和入度隨時間的分布情況.假設(shè)新節(jié)點new在t時刻加入網(wǎng)絡(luò)(如圖1所示)，R0為初始時刻網(wǎng)絡(luò)半徑，R0+t為t時刻的網(wǎng)絡(luò)半徑，Rnew為新加入new節(jié)點的通信半徑.具體情況見圖1.

圖1 模型有向組網(wǎng)示意圖Fig.1 Schematic diagram of model directed networking

因監(jiān)測區(qū)域內(nèi)節(jié)點部署服從均勻分布，選擇新節(jié)點new的鄰節(jié)點集的概率可由節(jié)點new覆蓋區(qū)域的面積與t時刻網(wǎng)絡(luò)區(qū)域的面積比來近似，則首先對于節(jié)點出度的節(jié)點度分析為

由于網(wǎng)絡(luò)中的節(jié)點均勻分布，新節(jié)點new局部區(qū)域內(nèi)節(jié)點出度的總和可表示為

其中:N(t)為t時刻網(wǎng)絡(luò)中的總出節(jié)點數(shù);ki(out)為網(wǎng)絡(luò)中節(jié)點的平均節(jié)點出度.

將式(6)和式(7)代入式(5)得

其中f(BCi(out))=.借助連續(xù)性和連續(xù)場理論，可通過平均場近似方法求得算法中節(jié)點出度同時間的演化關(guān)系.假設(shè)節(jié)點k是連續(xù)變化的，則ki(out)連續(xù)變化的速率可以表示為

求解該微分方程可得

其中:ki(out)(t)為t時刻節(jié)點i的出度;C為常數(shù).將初始變化條件ki(in)(t)=m代入式(10)，解得常數(shù)C:

到節(jié)點i的節(jié)點出度隨時間變化的規(guī)律為

節(jié)點i的出度小于k的概率P(ki(out)(t)＜k)可由下式求得:

由于在擇優(yōu)增長過程中，ti服從均勻分布，其概率密度滿足如下條件p(ti)=，代入式(13)可得節(jié)點出度分布P(ki(out))的表達式為

同理，對節(jié)點入度進行節(jié)點度分析得到節(jié)點入度分布P(ki(in))的表達式為

由式(14)和式(15)可以看出，演化生成的有向無標度拓撲，其出度和入度均服從冪律分布，分布的冪率指數(shù)為γ=，因此上述的分析結(jié)果表明由DRTD模型生成的拓撲具有無標度特性.

4 仿真分析

通過MATLAB軟件對DRTD模型進行實驗仿真.為了明確通過抗毀性度量模型衡量網(wǎng)絡(luò)抗毀性的正確性和所構(gòu)拓撲網(wǎng)絡(luò)自身的抗毀性，首先對模型自身的網(wǎng)絡(luò)度分布及抗毀性度量進行仿真，實驗環(huán)境參數(shù)見表1;其次在最大連通分支比例和網(wǎng)絡(luò)效率兩方面對DRTD拓撲模型和文獻[8]、文獻[10]、文獻[12]模型進行對比分析，驗證所提出模型的優(yōu)越性.同時，為了較好的研究不同算法的性能差異，在4種算法運行之初規(guī)定相同的網(wǎng)絡(luò)規(guī)模，并假設(shè)擁有相同的初始節(jié)點鏈接，數(shù)據(jù)結(jié)果均取50次實驗的平均值.

表1 實驗環(huán)境參數(shù)Table 1 Experimental environment parameters

4.1 DRTD模型動態(tài)特性分析

節(jié)點按照均值為λ 的泊松分布隨機部署在500 m×500 m的方形區(qū)域中[21]，節(jié)點數(shù)目設(shè)為100個，依據(jù)表1所示實驗參數(shù)，演化出了本文所構(gòu)建的具有抗毀性的有向網(wǎng)絡(luò)拓撲結(jié)構(gòu)，如圖2所示.

圖2 網(wǎng)絡(luò)拓樸結(jié)構(gòu)Fig.2 Network topology structure

圖2中:黑色箭頭表示出邊，即網(wǎng)絡(luò)數(shù)據(jù)從其他節(jié)點向該節(jié)點傳輸;灰色箭頭表示入邊，即網(wǎng)絡(luò)數(shù)據(jù)從該節(jié)點向其他鄰居節(jié)點傳輸.從圖中可以看出，該算法生成的有向網(wǎng)絡(luò)拓撲結(jié)構(gòu)均勻，擁有少量居于重要位置且度較大的關(guān)鍵節(jié)點，例如80號節(jié)點、82號節(jié)點和99號節(jié)點等，且簇與簇之間同樣有連接，與理論分析結(jié)果一致.

4.2 節(jié)點出入度分布分析

網(wǎng)絡(luò)拓撲節(jié)點的出度和入度度分布如圖3所示.

圖3 網(wǎng)絡(luò)節(jié)點出入度度分布Fig.3 Network node access degree distribution

從圖3中可看出，本文所構(gòu)DRTD演化模型生成的有向網(wǎng)中的節(jié)點出度和入度度分布均近似服從冪律分布，遵循了形成無標度拓撲的必要條件，滿足無標度的網(wǎng)絡(luò)特征，與理論分析結(jié)果一致.

4.3 網(wǎng)絡(luò)抗毀性效果分析

根據(jù)本文所提出的的網(wǎng)絡(luò)抗毀性度量計算公式，分別對網(wǎng)絡(luò)抗毀性度量隨介數(shù)中心性及節(jié)點度而變化的趨勢和各個節(jié)點的抗毀性度量值進行仿真.仿真效果如圖4所示.

圖4 抗毀性度量值效果圖Fig.4 Effect diagram of damage resistance measurement value

根據(jù)圖4可看出，網(wǎng)絡(luò)抗毀性度量隨著節(jié)點介數(shù)和度的增加呈正冪次遞增趨勢.網(wǎng)絡(luò)中擁有少量介數(shù)和節(jié)點度較大的關(guān)鍵節(jié)點，大量的介數(shù)和節(jié)點度較小的小度節(jié)點.從節(jié)點重要性分布角度觀察，有助于提高網(wǎng)絡(luò)抗毀性.

4.4 最大連通分支比例對比

為了分析不同算法下的網(wǎng)絡(luò)對節(jié)點失效規(guī)模的容忍程度，衡量DRTD算法形成拓撲的抗毀性，將此模型同上文所提3種模型進行對比仿真，分別統(tǒng)計隨機移除和選擇性移除節(jié)點后網(wǎng)絡(luò)的最大連通分支比例.本實驗中，最大連通分支比例定義為當網(wǎng)絡(luò)中的失效節(jié)點被移除時，剩余網(wǎng)絡(luò)各連通分支存活節(jié)點數(shù)總和同網(wǎng)絡(luò)總節(jié)點數(shù)的比值，如圖5-6所示.

圖5 隨機移除情況下最大連通分支比例對比圖Fig.5 Comparison of the maximum connected branch ratio under random removal

從圖5中可看出，4種模型在面對隨機移除時均表現(xiàn)出一定的抗毀性能，這是因為它們的建立均基于無標度演化規(guī)則，拓撲中度小的節(jié)點數(shù)量較多，移除并失效的概率偏大，而度小節(jié)點的失效往往不會嚴重影響網(wǎng)絡(luò)的連通性.隨著隨機移除比例不斷增大，DRTD模型最大連通分支比例始終高于其他3種模型.這是由于在擇優(yōu)連接時，DRTD模型考慮到節(jié)點自身介數(shù)和節(jié)點度，有關(guān)因素的全面分析使得對連接節(jié)點的選擇更合理，有助于增強網(wǎng)絡(luò)的健壯性，相當于其他3種模型，也表現(xiàn)出更強的抗毀性.

從圖6中可看出，網(wǎng)絡(luò)最大連通分支比例隨著選擇性移除比例的增大而迅速降低.但相比其他3種模型，DRTD模型所構(gòu)建網(wǎng)絡(luò)連通性的損壞程度較低，表現(xiàn)出更強的抗毀性.當重要節(jié)點遭受選擇性攻擊并被移除時，影響的節(jié)點范圍增大，連接節(jié)點數(shù)大量減少，網(wǎng)絡(luò)連通性迅速下降.當選擇性移除比例達到0.12%時，其他3種模型的最大連通分支比例降為0，而DRTD模型仍達到近0.1%.這是因為DRTD模型在節(jié)點之間連接的概率因素中考慮了全局性和局域性因素，通過最短路徑數(shù)所獲得的介數(shù)中心性和節(jié)點度以更加合理的比重將連接鏈路分配給節(jié)點，因此所構(gòu)拓撲相對于其他3種模型更加穩(wěn)定，也表現(xiàn)出更好的抗毀性.

圖6 選擇性移除情況下最大連通分支比例對比圖Fig.6 Comparison of the maximum connected branch ratio under selective removal

4.5 網(wǎng)絡(luò)效率對比

為了更好地反映出無標度網(wǎng)絡(luò)在面臨部分節(jié)點失效時，連通分支尺寸從大到小的演化過程，本文又針對不同模式的節(jié)點失效狀態(tài)下網(wǎng)絡(luò)效率E的變化進行對比仿真.網(wǎng)絡(luò)效率公式為E=其中dij為任意兩點間最短距離的跳數(shù).在節(jié)點失效后，E值保持越大，表明網(wǎng)絡(luò)抗毀性越好，并且有E∈(0，1]，其中，E=0對應(yīng)全孤立點網(wǎng)絡(luò)，E=1對應(yīng)全局耦合網(wǎng)絡(luò).仿真結(jié)果如圖7所示.

從圖7可看出，本文所提出的DRTD模型的網(wǎng)絡(luò)效率E相較于其他3種模型初始值較高，在隨機移除和選擇性失效情況均有優(yōu)勢.例如，在隨機節(jié)點失效達到較高的0.2%時，DRTD模型網(wǎng)絡(luò)效率達到0.05%，而其他3種模型在0.04%以下;在選擇性失效情況下，DRTD 模型曲線更為平緩，網(wǎng)絡(luò)效率下降速度較為緩慢，在失效比例達到0.3%時仍處于對比模型中最高的一種.

圖7 網(wǎng)絡(luò)效率隨節(jié)點失效比例變化圖Fig.7 Network efficiency changes with node failure ratio

由上述實驗分析可得，由DRTD模型所建立的有向無標度網(wǎng)絡(luò)拓撲對于網(wǎng)絡(luò)遭受攻擊，特別是選擇性攻擊時，表現(xiàn)出更加優(yōu)越的抗毀性能，節(jié)點之間的連接更為穩(wěn)定，網(wǎng)絡(luò)變得更均勻化.同時比較文獻[12]與其他兩種只考慮單一因素的算法，也證明了本文算法考慮角度的正確性.DRTD模型更符合WSNs拓撲的演化規(guī)則，更符合實際應(yīng)用的要求.

5 結(jié)論

本文在深入研究無線傳感網(wǎng)絡(luò)抗毀性的基礎(chǔ)上，提出了一種結(jié)合節(jié)點出入度和介數(shù)中心性兩種抗毀性因素的有向傳感網(wǎng)絡(luò)拓撲模型DRTD.通過動態(tài)性能分析，證明了該拓撲中節(jié)點出度和入度均服從冪律分布，符合無標度特性.仿真結(jié)果表明，通過該算法生成的有向拓撲網(wǎng)絡(luò)中，抗毀性度量值隨節(jié)點出入度和介數(shù)中心性的增大而呈正冪次遞增趨勢.當面對選擇性攻擊和蓄意攻擊時，同文獻[8]、文獻[10]、文獻[12]3種不同模型相比，DRTD模型的最大聯(lián)通分支比例和網(wǎng)絡(luò)效率在下降速率和網(wǎng)絡(luò)崩潰臨界值上，都表現(xiàn)出更好的抗毀性，為研究有向無線傳感器網(wǎng)絡(luò)提供了新思路.