無線傳感器網絡中基于無標度特性的拓撲控制算法*

劉洲洲,李文威

(西安航空學院傳感器網絡與智能計算實驗室,西安 710077)

項目來源:國家自然科學基金項目(61601365);陜西省自然科學基礎研究計劃面上項目(2017JM6096);陜西省教育廳科研計劃項目(16JK1395);西安市科技計劃項目(2017076CG/RC039(XAHK001))

2017-02-15修改日期2017-07-05

無線傳感器網絡中基于無標度特性的拓撲控制算法*

劉洲洲*,李文威

(西安航空學院傳感器網絡與智能計算實驗室,西安 710077)

針對無線傳感器網絡中的無標度特性中的抗毀和容錯能力差問題進行了研究,提出了一種改進的無標度網絡拓撲控制算法(BA Evolution Model,BAEM)。通過分析冪率指數對網絡容錯和拓撲抗毀性的影響,得出在兼顧拓撲容錯性的同時最大化網絡抗毀性的最優(yōu)網絡拓撲。仿真實驗結果表明:改進后的容錯拓撲可以保持無標度網絡模型對隨機故障較強的魯棒性,同時可以改善無標度網絡對蓄意攻擊的脆弱性,并延長了網絡生命周期。

無線傳感器網絡;無標度;抗毀;容錯

無線傳感器網絡WSNs(Wireless Sensor Networks)節(jié)點經常部署在惡劣的環(huán)境中,拓撲構建主要考慮電池能源無法更新的情況[1],因此,所得WSNs拓撲必須具有很強的容錯性,以應對頻繁出現(xiàn)的節(jié)點失效現(xiàn)象[2]。此外,無人值守的WSNs可能因遭受目的性的攻擊直接或間接的導致整個網絡的瓦解。所以,如何提高整個網絡的抗毀性即抗毀性也成為構建WSNs的重要課題。

近期對于無線傳感器網絡容錯拓撲的研究,主要是通過功率控制生成能量最小的k-連通網絡拓撲[3-5],基本思想是把容錯拓撲問題等價為尋找多連通圖,然而,尋找能量最優(yōu)的多連通圖問題被證明是NP難的。無標度特性(少數的節(jié)點往往擁有大量的連接,而大部分節(jié)點卻擁有很少的連接)的發(fā)現(xiàn)作為復雜網絡研究中的一大突破,其具有的強容錯性可以解決WSNs中的容錯問題。文獻[5]設計了一種基于勢博弈的拓撲控制模型,并證明了該模型納什均衡的存在性。通過構造兼顧節(jié)點連通性和能耗均衡性的收益函數,以確保降低節(jié)點功耗的同時維持網絡的連通性。而當經典BA模型BA(Barabsi-Albert Model)提出以后,文獻[6]將隨機網絡和BA無標度網絡中某些關鍵節(jié)點去除后兩種網絡的魯棒性進行了對比,由于無標度網絡的冪率特性,使其具有較強的容錯性,但是在面對蓄意攻擊時卻比較脆弱。因此如何設計和優(yōu)化一個網絡,使其具有較強的容錯能力和抗攻擊能力顯得尤為重要并且迫切,文獻[7]重點分析了EAEM(Energy-Aware Evolution Model)算法[8-9]研究如何構建能量有效的無標度拓撲結構,它在擇優(yōu)連接時考慮節(jié)點的剩余能量,促使網絡向節(jié)能的方向轉變。Qi等人[10]將隨機連接改進為基于節(jié)點適應度的優(yōu)先連接,并將適應度的計算與節(jié)點能量直接關聯(lián)。Wang[11-12]等人采用優(yōu)化度分布熵的方法,優(yōu)化網絡的度分布指數,增加網絡的異質性,達到提高網絡容錯能力的目的。Wu等人[13]對無標度拓撲結構非均勻性的研究發(fā)現(xiàn)標度指數越大,網絡越均勻。受此啟發(fā),可以使用新的網絡模型,使網絡盡量均勻,并繼承無標度網絡的強容錯性,最終實現(xiàn)提高網絡的抗攻擊性和延長生命期的目的。

基于上述分析,為了在兼顧拓撲容錯能力的同時增強網絡的抗攻擊能力,需要構造滿足不同網絡需求的容錯拓撲結構。本文提出了一種新的無標度網絡演化模型BAEM(BA Evolution Model),通過分析冪率指數對網絡抗毀性和拓撲容錯性的影響,得出一種滿足特定網絡需求的強容錯無標度拓撲。

1 問題模型

1.1 無標度網絡抗毀和容錯建模

由文獻[10]的分析可知,當無標度的冪率指數λ>2時,網絡的抗毀性隨著冪率指數的增大而減小。傳統(tǒng)BA無標度網絡模型中節(jié)點的最大度隨著網絡規(guī)模無限增大,使得網絡中存在少數度非常大的hub節(jié)點,這使得無標度網絡在選擇性攻擊度大的節(jié)點時異常脆弱。對于無標度網絡的最大節(jié)點度計算如下:

設無標度網絡度分布為p(k)=Ck-λ,系數C可歸一化估計如下

(1)

C=(λ-1)mλ-1

(2)

網絡的最大節(jié)點度kmax可用下式進行估計:

(3)

結合式(2)和式(3)可得

kmax=mN1/(λ-1)

(4)

由式(4)可知,kmax與網絡增長規(guī)模m、節(jié)點數N和冪率指數λ有關,通常情況下網絡的增長規(guī)模m=1,在不同節(jié)點數N的情況下畫出kmax與冪率指數λ的函數關系圖如圖1所示。

圖1 最大節(jié)點度與冪率指數關系函數圖

由圖1可知,kmax隨著冪率指數的增大而減小,這說明冪率指數越小,最大節(jié)點度越大,網絡的抗毀性就越差。以提高無標度網絡的抗攻擊能力為目的,優(yōu)化網絡結構,可以用kmax來度量無標度網絡整體的非均勻性。在網絡節(jié)點數N和網絡增長規(guī)模m給定的情況下,kmax越小,標度指數越大λ越大,網絡越均勻,抗毀性就越好,但容錯性較差,如隨機網絡;而kmax越大,標度指數λ越小,網絡越不均勻,網絡抗毀性越差,但容錯性能較好,如星型網絡。所以要構造強抗毀性的無標度拓撲就要minkmax。

其中Cohen等人[11]對無標度網絡的相變性質進行了深入研究,他們得到了一個網絡存在最大連通集團的判定標準:k≡〈k2〉/〈k〉=2,其中〈k〉代表平均節(jié)點度。

(5)

(6)

所以可以由pc來衡量拓撲的容錯性,當m為定值時,拓撲的容錯性隨著冪率指數λ的增大而減小,所以要構造強容錯性的拓撲就要maxpc。

1.2 問題分析

WSNs拓撲控制的主要目標就是在確保網絡容錯特性的前提下,兼顧抗毀性、網絡生命期、負載均衡等性能,形成優(yōu)化的網絡拓撲[14],這樣本文要解決的問題可以概括為:①最小化kmax,使得網絡擁有較好的抵御蓄意攻擊的能力,即minkmax。②最大化拓撲的容錯能力,使得網絡拓撲有較好的容忍節(jié)點失敗的能力,即maxpc。

所以可以將本文的研究問題歸結于建立一個兼顧minkmax和maxpc的WSNs無標度拓撲結構,由式(7)來描述

maxf=pc/kmax

(7)

2 BAEM算法

為了演化出對隨機節(jié)點移除和選擇性節(jié)點移除有綜合容錯性的WSNs無標度容錯拓撲結構,可以借助文獻[15-16]構建的無標度網絡模型,此模型介于BA模型和隨機網絡之間,所以存在最優(yōu)的無標度拓撲結構具有較好的容錯性并能夠提高選擇性節(jié)點移除的能力。

2.1BAEM算法

①增長性:以少量個m0節(jié)點開始,在每一時間步長,向存在網絡中加入一個新節(jié)點n,同時加上從此節(jié)點出發(fā)的m條邊;

②擇優(yōu)連接:在擇優(yōu)增長時,新節(jié)點n僅在其傳輸范圍內選擇連接節(jié)點i,且此時的擇優(yōu)連接概率為

(8)

2.2BAEM拓撲算法動態(tài)特性分析

(9)

(10)

采用分離變量法并結合初始條件ki(ti)=m解上述微分方程可得

(11)

從而,節(jié)點i的度小于k的概率p(ki(t)

(12)

(13)

考慮到在改進的擇優(yōu)增長過程中,每一個時間步長僅有一個新節(jié)點加入到網絡中,因此,ti服從均勻分布,其概率密度滿足如下條件

(14)

結合式(14)和式(15)可得,經改進的擇優(yōu)增長過程演化出的容錯拓撲BAEM的度分布表達式,如式(16)所示

(15)

由式(15)可見,在增長規(guī)模m給定后,演化拓撲BAEM近似為標度指數為λ=3+b的無標度網絡,通過調節(jié)參數p可以使標度指數在[3,+∞)內變化。當p=0時,BAEM的度分布近似于p(k)～k-3,為標準的BA無標度網絡模型,對隨機節(jié)點移除行為有強容錯性;當p=1時,BAEM的度分布近似為p(k)～e-k/m,網絡無偏好傾向,為隨機網絡模型,可有效抵御選擇性節(jié)點移除現(xiàn)象。

3 仿真分析

由于目前對于WSNs無標度拓撲容錯算法的研究多集中于能源效率的優(yōu)化,同時考慮網絡容錯和抗攻擊抗毀能力的算法還不常見,為此,本文針對具有節(jié)能代表性的EAEM算法和經典的BA算法進行MATLAB2012a仿真實驗對比。在仿真實驗中,3種算法采用了相同的初始網絡規(guī)模和節(jié)點總數,其中,每一次實驗都是50次實驗的平均值,如表1所示。

表1 實驗環(huán)境參數

3.1 拓撲容錯性和抗毀性對比

為了衡量BAEM優(yōu)化拓撲的容錯能力和抗毀能力,將BA模型、EAEM算法拓撲模型和BAEM優(yōu)化算法拓撲模型進行仿真對比,分別按隨機刪除和按節(jié)點度從大到小的順序刪除節(jié)點,然后分別統(tǒng)計網絡中最大連通片分支上的節(jié)點數目,得到的容錯抗毀對比圖如圖2和圖3所示。

圖2 容錯對比圖

圖2為拓撲對隨機失效的容忍能力比較圖,有仿真圖可知,BAEM算法擁有BA算法和EAEM算法幾乎相同的容錯性,這表明,BAEM算法繼承了無標度網絡強容錯性的特點。圖3為拓撲對惡意攻擊的容忍能力比較圖,由圖中可以看出BAEM優(yōu)化算法對惡意攻擊的容忍能力明顯高于EAEM算法和BA算法,BA算法和EAEM算法在選擇性移除3到4個節(jié)點時,網絡就處于癱瘓狀態(tài),而BAEM能承受將近9個節(jié)點的攻擊。綜上所述,BAEM算法生成的網絡拓撲,不僅對節(jié)點隨機失效有較好的容忍能力,而且對拓撲的蓄意攻擊有較好的容忍性。

圖3 抗毀對比圖

3.2 網絡生命期對比

由于傳感器節(jié)點能量受限,最大限度的延長網絡生命期成為構造WSNs拓撲的另一目標。分別運行上述3種算法,并記錄不同節(jié)點失效比例下的網絡生命期。每一輪試驗中,各個節(jié)點與其鄰居節(jié)點進行數據交換,依據低功耗無線通信能量消耗模型[13],運行BAEM優(yōu)化算法、EAEM算法和BA算法,圖4顯示了在不同失效節(jié)點比例下(首節(jié)點,10%,30%,50%,70%,80%)網絡生命期的對比情況。

圖4 生命周期對比

從圖4中可以看出,EAEM算法和BAEM優(yōu)化算法所得拓撲在出現(xiàn)首節(jié)點失效時就相差較大,隨著節(jié)點失效比例的增加,BAEM算法的網絡生命期提升幅度越來越大,這主要是由于BAEM算法在構建拓撲時綜合考慮了最大節(jié)點度和拓撲的容錯性,限制了最大節(jié)點度,從而使節(jié)點的能耗更加均衡,提高了網絡的生命期。

4 結論

本文提出了一種新的無標度拓撲演化算法BAEM,并通過優(yōu)化指標計算出最優(yōu)拓撲參數。對BAEM優(yōu)化算法與BA算法和EAEM算法進行仿真對比分析,BAEM算法具有強容錯性,并能提高網絡的抗毀能力,而且能夠延長網絡的生命期。利用BAEM優(yōu)化算法,僅通過改變算法參數信息就可以產生滿足特定網絡性能需求的容錯拓撲結構,為綜合性能優(yōu)化的無線傳感器網絡容錯拓撲設計奠定了良好的基礎。

[1] Li X Y,Wan P J,Wang Y,et al. Fault Tolerant Deployment and Topology Control in Wireless Ad Hoc Networks[J]. Wireless Communications and Mobile Computing,2004,4(1):109-125.

[2] 王寧,周圓,劉敬浩. 一種基于改進粒子群的無線傳感器網絡層次化聚類協(xié)議[J]. 傳感技術學報,2017,30(1):120-125.

[3] Thallner B,Moser H,Schrnid U. Topology Control for Fault-Tolerant Communication in Wireless Ad Hoc Networks[J]. Wireless Networks,2010,16(2):387-404.

[4] Jia Xiaohua,Dongsoo Kim,Sam Makki,et al. Power Assignment fork-Connectivity in Wireless Ad Hoc Networks[J]. Journal of Combinatorial Optimization 9.2,2005:213-222.

[5] Li X L Feng D L,Peng C C. A Potential Game Based Topology Control Algorithm for Wireless Sensor Networks[J]. Acta Physica Sinica,2016,65(2):028401.

[6] Jiang Lurong,Jin Xinyu,Xia Yongxiang,et al. A Scale-Free Topology Construction Model for Wireless Sensor Networks[J]. International Journal of Distributed Sensor Networks,2014,Article ID 764698.

[7] Yao Hongxing,Tang Yu. Topology Evolving Model with Scale-Free Property for Wireless Sensor Networks[J]. International Journal of Nonlinear Science,2013,16(1):82-86.

[8] 杜巍,蔡萌,杜海峰. 網絡結構魯棒性指標及應用研究[J]. 西安交通大學學報,2010,44(4):93-97.

[9] Zhu H L,Luo H,Peng H P,et al. Complex Networks-Based Energy-Efficient Evolution Model for Wireless Sensor Networks[J]. Chaos,Solitons and Fractals,2009,41(4):1828-1835.

[10] Qi X Q,Ma S Q,Zheng G Z. Topology Evolution of Wireless Sensor Networks Based on Adaptive Free-Scale Network[J]. Journal of Information and Computational Science,2011,8(3):467-475.

[11] Solé Ricard V,Sergi V. Information Theory of Complex Networks:On Evolution and Architectural Constraints[J]. Complex Networks,2004:189-207.

[12] Wang Bing,Huanwen Tang,Chonghui Guo,et al. Optimization of Network Structure to Random Failures[J]. Physica A:Statistical Mechanics and its Applications 2006,368(2):607-614.

[13] 吳俊,譚躍進,鄧宏鐘,等. 標度指數不大于2的無標度網絡的若干性質[J]. 系統(tǒng)科學與數學,2008,28(7):6.

[14] Cohen,Reuven,DBen-Avraham,et al. Breakdown of the Internet Under Intentional Attack[J]. Physical Review Letters,2001,86(16):3682-3685.

[15] Liu Zonghua,Ying Chenglai,Nong Ye,et al. Connectivity Distribution and Attack Tolerance of General Networks with Both Preferential and Random Attachments[J]. Physics Letters,2002,A303(5):337-344.

[16] Xi W B,Xian E M,Chen Y G. Load Balancing for Wireless Sensor Networks Based on an Equiprobable Routing Model[J]. Journal of Electronics and Information Technology,2010,32:1205-1211.

TopologyControlAlgorithmBasedonScale-FreePropertyinWirelessSensorNetworks*

LIUZhouzhou*,LIWenwei

(Xi’an Aeronautical University Sensor network and Intelligent Computing Lab,Xi’an 710077,China)

The issue that the WSNs are vulnerable with deliberate attacks is studied,and a new scale-free network evolution model(BAEM)is proposed. And then through analyzing the effect of the power-law exponent on network intrusion-tolerance and topology fault-tolerance,the optimal topology is derived which can assure the topology fault-tolerance and maximize topology intrusion-tolerance. The simulation results show that new fault-tolerant topology can keep the character that the scale-free network model has stronger robustness to random failures,and it also can reduce their fragility against intentional attacks and provide longer network lifetime.

wireless sensor networks;scale-free;intrusion-tolerance;fault-tolerance

A

1004-1699(2017)10-1578-05

10.3969/j.issn.1004-1699.2017.10.021

劉洲洲(1981-)男,漢族,陜西延安人,博士,副教授,主要研究方向為無線傳感器網絡,liuzhouzhou8192@126.com。