分布式能量高效的WSN非均勻分簇路由多跳算法

吳玉成，謝 璐

(1.重慶大學通信工程學院，重慶400030;2.國家保密科技測評中心，北京100044)

無線傳感器網(wǎng)絡［1］(wireless sensor networks，WSN)通過大量部署在監(jiān)測區(qū)域內(nèi)的傳感器節(jié)點，以多跳的無線通信方式，將采集的感知信息匯聚于sink節(jié)點，傳輸給終端用戶.因此sink附近區(qū)域的節(jié)點將承擔大量數(shù)據(jù)轉(zhuǎn)發(fā)，其能量消耗水平高于其他區(qū)域而被稱為“熱區(qū)”，熱區(qū)內(nèi)的節(jié)點過早消耗完自己的能量死亡導致網(wǎng)絡失效稱為能量空洞［1］現(xiàn)象.

當前避免能量空洞的方法主要是最大限度地均衡網(wǎng)絡負載［2］，許多文獻從不同方面采取應對策略，例如:節(jié)點初始能量不均勻配置［3］;控制節(jié)點功率［4］;節(jié)點非均勻部署［5］，以上策略可以使“熱區(qū)”能量充足，但對傳感器節(jié)點要求較高，需特定部署，不易操作.文獻［6］采用動態(tài)sink;文獻［7］通過部署多個sink，但是改變sink的位置或增加其數(shù)量都需耗費大量成本.為此許多學者提出采用靈活高效易實現(xiàn)的分簇路由策略來均衡網(wǎng)絡負載，但以LEACH［8］為代表的均勻分簇路由協(xié)議無法解決“熱區(qū)”問題.S.Soro等［9］首次提出采用非均勻分簇的思想來克服“熱區(qū)”問題，但所提協(xié)議簇首需事先設計，網(wǎng)絡擴展性較差.文獻［8］中提出經(jīng)典的非均勻分簇路由協(xié)議EEUC，候選簇首通過非均勻的競爭范圍構(gòu)造大小不等的簇來緩解“熱區(qū)”問題，隨后在此基礎上對簇間路由進行改進提出UCR［10］，以節(jié)約中繼節(jié)點的能量.但在EEUC和UCR中，節(jié)點部署及候選簇首選擇的隨機性，以及僅局部比較節(jié)點剩余能量來選擇最終簇首無法從整體上協(xié)調(diào)全網(wǎng)的能量消耗來避免能量空洞;所采取的就近入簇和固定路由方式也不利于均衡簇間能量消耗.

文中提出能量空洞避免的分布式能量高效的非均勻分簇多跳路由算法.該算法基于平衡全網(wǎng)能量選擇出的候選簇首通過自適應校正競爭半徑進行非均勻分簇;節(jié)點根據(jù)基于能量和距離的能耗函數(shù)選擇最佳簇加入;簇首采用動態(tài)路由與sink實現(xiàn)高效數(shù)據(jù)傳輸.

1 網(wǎng)絡模型及能量消耗模型

1.1 網(wǎng)絡模型

文中對網(wǎng)絡模型做如下假設:

1)N個傳感器節(jié)點隨機部署在二維平面觀測區(qū)域上，sink節(jié)點位于觀測區(qū)外，網(wǎng)絡一經(jīng)部署不再移動.

2)所有節(jié)點同構(gòu)，具備數(shù)據(jù)融合、自適應功率控制等功能，且節(jié)點ID號唯一但位置未知.文中用si表示第i個節(jié)點，i為節(jié)點的ID.

3)網(wǎng)絡鏈路是對稱的.

1.2 能量消耗模型

文中采用與文獻［10］相同的無線通信能量消耗模型.節(jié)點發(fā)送kbit數(shù)據(jù)到距離為d處所消耗的能量由發(fā)射電路損耗和功率放大損耗兩部分組成，即:

式中:Eelec為發(fā)射電路損耗的能量;當傳輸距離小于閾值d0時，功率放大損耗采用自由空間模型;當傳輸距離大于等于閾值d0時，采用多路徑衰減模型;εfs，εmp分別為這2種模型中功率放大所需的能量.

傳感器節(jié)點接收kbit數(shù)據(jù)所消耗的能量為

數(shù)據(jù)融合也消耗一定的能量，用EDF表示融合1 bit數(shù)據(jù)消耗的能量.

2 能量高效的非均勻分簇路由算法

文中提出的基于全網(wǎng)平均能量和節(jié)點位置的候選簇首選擇算法，使得能耗水平低，距離sink近的節(jié)點優(yōu)先成為簇頭，有效地平衡了全網(wǎng)能量.節(jié)點加入哪個簇，以及簇間通信路由方式也是平衡全網(wǎng)能量的關鍵因素，為此文中提出了基于能量和距離的能耗函數(shù)入簇機制和動態(tài)路由.

網(wǎng)絡運行以“輪”為單位，每一輪包括網(wǎng)絡建立階段和數(shù)據(jù)傳輸階段.其中網(wǎng)絡建立階段又分為3個時間段:T1為候選簇首產(chǎn)生階段;T2為最終簇首選擇階段;T3為成簇階段.數(shù)據(jù)傳輸階段包括簇內(nèi)數(shù)據(jù)傳輸階段和簇間數(shù)據(jù)傳輸階段.

2.1 網(wǎng)絡建立階段

在網(wǎng)絡建立初始化階段，sink以特定的發(fā)送功率向網(wǎng)絡廣播信號，每個傳感器節(jié)點接收此信號并根據(jù)其強度計算自己到sink的近似距離.隨后，每個傳感器節(jié)點以rhop為半徑廣播信號以統(tǒng)計自己一跳范圍內(nèi)的鄰居節(jié)點數(shù)目

2.1.1 候選簇首產(chǎn)生階段T1

由于節(jié)點部署的隨機性，隨機競選候選簇首的方式可能造成處于網(wǎng)絡邊緣的節(jié)點競選成功，而能量高的節(jié)點反而競選失敗，這無疑不利于平衡全網(wǎng)能量進而影響網(wǎng)絡壽命.文中算法引用位置因子和平均能量因子來平衡全網(wǎng)能量，使得離匯聚點越近，剩余能量占全網(wǎng)平均能量比重越大的節(jié)點成為候選簇首的概率越大.每個節(jié)點根據(jù)式(3)計算自己成為候選簇首的概率Psi，若節(jié)點si產(chǎn)生的隨機數(shù)μ＜Psi，μ∈(0，1)，則成為候選簇首，否則進入睡眠狀態(tài)以節(jié)省能量.計算式如下:

成為候選簇首的節(jié)點其競爭半徑計算式為

式中:dmax和dmin分別表示網(wǎng)絡中的節(jié)點到sink距離的最大值和最小值為si的初始能量;Negsi為si一跳范圍內(nèi)的鄰居節(jié)點數(shù)目;Rmax為候選簇首競爭半徑的最大值，文中由文獻［11］根據(jù)MEC(minimum energy consumption)，將其取值為c2，c3都是處于(0，1)的常數(shù)，其最優(yōu)取值由試驗仿真得出.由式(4)可知網(wǎng)絡運行過程中，候選簇首折中考慮簇內(nèi)負擔和自身能量消耗自適應地調(diào)節(jié)競爭半徑的大小.

2.1.2 最終簇首選擇階段T2

每個候選簇首si根據(jù)式(5)設定其等待時間Tsi參與最終簇首的競選，等待時間一到則成為最終簇首并以為半徑廣播競選成功消息，若在其等待時間到前收到其他候選簇首的競選成功消息，則退出競選進入睡眠狀態(tài).計算式為

式中:Crandom是處于(0.9，1)的隨機數(shù)，該參數(shù)的設置是為了避免多個候選簇首在同一時間廣播競選成功消息造成信息碰撞;α是處于(0，1)的常數(shù).文中最終簇首的選擇采用定時器競爭機制，綜合考慮節(jié)點的剩余能量和鄰居節(jié)點數(shù)，避免出現(xiàn)無法覆蓋整個網(wǎng)絡，造成網(wǎng)絡失衡的情況.

2.1.3 成簇階段T3

T2階段結(jié)束后，所有非簇首節(jié)點從睡眠狀態(tài)喚醒選擇簇加入.節(jié)點加入哪個簇關系到平衡當前簇頭地區(qū)的能量消耗.現(xiàn)有分簇路由算法幾乎都采取就近入簇，可能造成離sink近的簇規(guī)模反而比離sink遠的簇規(guī)模大，導致處于“熱區(qū)”的簇首簇內(nèi)負擔過重，不利于平衡全網(wǎng)能量消耗.為此文中提出基于能量和距離的能耗函數(shù)入簇機制，使得節(jié)點會盡量選擇與簇首距離近，簇首剩余能量多，且簇規(guī)模大的簇(離 sink遠的簇)加入，平衡了簇內(nèi)和簇間負載.

式中:1≤i≤CH，CH為簇首數(shù)目;1≤j≤CM，CM為非簇首節(jié)點數(shù)目;d(i，j)表示節(jié)點sj與簇首si之間的物理距離;β是處于(0，1)的權(quán)重常數(shù).

2.2 數(shù)據(jù)傳輸階段

數(shù)據(jù)傳輸階段包括簇內(nèi)數(shù)據(jù)傳輸階段和簇間數(shù)據(jù)傳輸階段.其中簇內(nèi)數(shù)據(jù)傳輸時，各成員節(jié)點采取TDMA方式，在各自分配的時間內(nèi)將其傳感數(shù)據(jù)傳輸給簇首，簇首接收完所有數(shù)據(jù)后進行數(shù)據(jù)融合處理，壓縮成一個數(shù)據(jù)包后再進行簇間數(shù)據(jù)傳輸.簇間數(shù)據(jù)傳輸采用多跳動態(tài)路由的方式.路由構(gòu)建時，所有非簇首節(jié)點進入睡眠狀態(tài).每個簇首以相同概率廣播其狀態(tài)信息，若簇首si到sink的距離dsi小于閾值TD_MAX，則直接與sink通信，否則在自己的路由轉(zhuǎn)發(fā)集合中隨機動態(tài)選取一個簇首作為轉(zhuǎn)發(fā)節(jié)點多跳傳送給匯聚點，且

若簇首si的Rsirouter為空，則與sink直接通信.采取動態(tài)路由方式雖然不及每次選取最優(yōu)的轉(zhuǎn)發(fā)節(jié)點，但可避免固定的轉(zhuǎn)發(fā)路徑導致轉(zhuǎn)發(fā)節(jié)點因能量消耗過快而死亡，均衡了中繼簇首節(jié)點的能量消耗，進而均衡了全網(wǎng)能量消耗.

3 仿真及結(jié)果分析

3.1 試驗參數(shù)設置

采用Matlab對文中算法和UCR算法進行仿真分析比較.文中算法所用參數(shù)因受網(wǎng)絡規(guī)模，節(jié)點密度等因素的影響，通過上千次隨機試驗獲取其最優(yōu)值如下:P=0.4，c1=0.25，c2=0.3，c3=0.2，α =(與 UCR 選取一樣).UCR算法的參數(shù)是基于文獻［8］選取的最優(yōu)值，試驗中其他參數(shù)設置如下:網(wǎng)絡覆蓋區(qū)域，(0，0)～ (200，200)，單位為 m;匯聚點位置，(250 m，100 m);節(jié)點總數(shù)N，400;節(jié)點初始能量，1 J;Eelec，50 nJ·bit-1;εfs，10 pJ·(bit·m2)-1;εmp，0.001 3 pJ·(bit·m2)-1;d0，87 m;EDA，5 nJ·(bit·signal)-1;數(shù)據(jù)包大小，4 000 bit.

3.2 仿真結(jié)果分析

文中所有仿真結(jié)果是1 000次隨機試驗結(jié)果的平均值.圖1和2分別比較各輪候選簇首數(shù)目和隨機抽取60輪簇首消耗能量的方差.

圖1 候選簇首數(shù)目比較

由圖1可知，文中算法中各輪候選簇首的數(shù)目約為UCR的一半且無需維護鄰簇首集合，節(jié)約了大量控制開銷;最優(yōu)候選簇首呈非均勻分布，離匯聚點越近分布越多，有利于最終簇首的競選和分布.

圖2 簇首消耗能量的方差比較

由圖2可知，文中算法簇首消耗能量的方差比UCR低，且波動不大較穩(wěn)定，相比UCR更好地均衡了簇首能量消耗.圖3是隨機抽取20輪，各輪簇首消耗的能量之和比較.

圖3 簇首消耗的能量之和比較

由圖3可見，文中算法每輪簇首消耗的能量之和小于UCR，所以文中算法比UCR更能實現(xiàn)能量高效.圖4是網(wǎng)絡中存活的節(jié)點數(shù)隨時間變化的情況比較.

圖4 網(wǎng)絡存活節(jié)點數(shù)比較

由圖4可見，文中算法與UCR算法第1個節(jié)點死亡的時間分別為1 251輪，1 670輪，即文中算法的網(wǎng)絡生命周期較UCR提高了34%;且文中算法第1個節(jié)點死亡與全網(wǎng)節(jié)點死亡的時間跨度比UCR小，即網(wǎng)絡能耗均衡性較好.這是由于文中算法選取候選簇首基于平衡全網(wǎng)剩余能量的考慮;所采取的入簇機制和動態(tài)路由降低處于“熱區(qū)”的簇首能量消耗速度.圖5比較網(wǎng)絡運行到第600輪和第1 000輪時熱區(qū)內(nèi)節(jié)點的剩余能量.

圖5 “熱區(qū)”內(nèi)節(jié)點的剩余能量比較

文中定義與sink距離為TD_MAX的區(qū)域為熱區(qū)［8］.由圖5可見，文中算法中熱區(qū)內(nèi)節(jié)點剩余能量大于UCR熱區(qū)內(nèi)節(jié)點剩余能量，并且隨著網(wǎng)絡的運行，剩余能量差距越大，說明文中算法緩解“熱區(qū)”問題的效果比 UCR好，能有效避免能量空洞.

4 結(jié)論

針對無線傳感器網(wǎng)絡中存在的能量空洞問題，在已有分簇路由協(xié)議的基礎上提出一種分布式能量高效的WSN非均勻分簇路由多跳算法，結(jié)論如下:

1)算法在選擇候選簇首時引入位置因子和平均能量因子，無需維護鄰簇首集合，節(jié)約了大量控制開銷，均衡了全網(wǎng)能耗.

2)文中算法簇首消耗能量的方差比UCR算法低，且波動不大較穩(wěn)定，相比UCR算法更好地均衡了簇首能量消耗.

3)文中算法能有效地避免能量空洞，與UCR算法相比，延長了網(wǎng)絡生命周期，緩解“熱區(qū)”問題的效果更為顯著.

References)

［1］Li Changle，Zhang Hanxiao，Hao Binnin，et al.A survey on routing protocols for large-scale wireless sensor networks［J］.Sensors，2011，11(4):3498-3526.

［2］Anastasi G，Conti M，Di Francesco M，et al.Energy conservation in wireless sensor networks:a survey［J］.Ad Hoc Networks，2009，7(3):537-568.

［3］Chen Changwen，Wang Yu.Chain-type wireless sensor network for monitoring long range infrastructures:architecture and protocols［J］.International Journal of Distributed Sensor Networks，2008，4(4):287-314.

［4］Zheng Liqiang，Wang Wensi，Mathewson Alan，et al.An adaptive transmission power control method for wireless sensor networks［C］∥Proceedings of IET Signal and Systems Conference.Cork，Ireland:Institution of Engineering and Technology，2010:261-265.

［5］Wu Xiaobing，Chen Guihai，Das Sajal K.Avoiding energy holes in wireless sensor networks with nonuniform node distribution［J］.IEEE Transactions on Parallel and Distributed Systems，2008，19(5):710-720.

［6］Yun Y S，Xia Y.Maximizing the lifetime of wireless sensor networks with mobile sink in delay-tolerant applications［J］.IEEE Transactions on Mobile Computing，2010，9(9):1308-1318.

［7］Marta M，Cardei M.Improved sensor network lifetime with multiple mobile sinks［J］.Pervasive and Mobile Computing，2009，5(5):542-555.

［8］李成法，陳貴海，葉 懋，等.一種基于非均勻分簇的無線傳感器網(wǎng)絡路由協(xié)議［J］.計算機學報，2007，30(1):27-36.Li Chengfa，Chen Guihai，Ye Mao，et al.An uneven cluster-based routing protocol for wireless sensor networks［J］.Chinese Journal of Computers，2007，30(1):27-36.(in Chinese)

［9］Soro S，Heinzelman W B.Prolonging the lifetime of wireless sensor networks via unequal clustering［C］∥Proceedings of19th IEEE International Conference on Parallel and Distributed Processing Symposium.Denver:IEEE Computer Society，doi:10.1109/IPDPS.2005.365.

［10］Chen Guihai，Li Chengfa，Ye Mao，et al.An unequal cluster-based routing protocol in wireless sensor networks［J］.Wireless Networks，2009，15(2):193-207.

［11］Yuan Huiyong，Liu Yongyi，Yu Jianping.A new energy-efficient unequal clustering algorithm for wireless sensor networks［C］∥Proceedings of2011IEEE International Conference on Computer Science and Automation Engineering.Shanghai:IEEE Computer Society，2011:431-434.