無線傳感器網(wǎng)絡(luò)中基于無標度特性的拓撲控制算法*

劉洲洲,李文威

(西安航空學(xué)院傳感器網(wǎng)絡(luò)與智能計算實驗室,西安 710077)

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

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

無線傳感器網(wǎng)絡(luò)中基于無標度特性的拓撲控制算法*

劉洲洲*,李文威

(西安航空學(xué)院傳感器網(wǎng)絡(luò)與智能計算實驗室,西安 710077)

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

無線傳感器網(wǎng)絡(luò);無標度;抗毀;容錯

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

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

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

1 問題模型

1.1 無標度網(wǎng)絡(luò)抗毀和容錯建模

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

設(shè)無標度網(wǎng)絡(luò)度分布為p(k)=Ck-λ,系數(shù)C可歸一化估計如下

(1)

C=(λ-1)mλ-1

(2)

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

(3)

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

kmax=mN1/(λ-1)

(4)

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

圖1 最大節(jié)點度與冪率指數(shù)關(guān)系函數(shù)圖

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

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

(5)

(6)

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

1.2 問題分析

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

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

maxf=pc/kmax

(7)

2 BAEM算法

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

2.1BAEM算法

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

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

(8)

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

(9)

(10)

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

(11)

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

(12)

(13)

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

(14)

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

(15)

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

3 仿真分析

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

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

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

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

圖2 容錯對比圖

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

圖3 抗毀對比圖

3.2 網(wǎng)絡(luò)生命期對比

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

圖4 生命周期對比

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

4 結(jié)論

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

[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] 王寧,周圓,劉敬浩. 一種基于改進粒子群的無線傳感器網(wǎng)絡(luò)層次化聚類協(xié)議[J]. 傳感技術(shù)學(xué)報,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] 杜巍,蔡萌,杜海峰. 網(wǎng)絡(luò)結(jié)構(gòu)魯棒性指標及應(yīng)用研究[J]. 西安交通大學(xué)學(xué)報,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] 吳俊,譚躍進,鄧宏鐘,等. 標度指數(shù)不大于2的無標度網(wǎng)絡(luò)的若干性質(zhì)[J]. 系統(tǒng)科學(xué)與數(shù)學(xué),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-)男,漢族,陜西延安人,博士,副教授,主要研究方向為無線傳感器網(wǎng)絡(luò),liuzhouzhou8192@126.com。