一種能量高效的無線傳感器網絡拓撲控制算法

江禹生，李 萍，馬 超

（重慶大學通信工程學院，重慶市 400030）

0 引言

無線傳感器網絡低功耗、低成本、自組織與分布式等特點使其成為信息獲取的重要技術，然而資源受限使得對無線傳感器網絡的應用面臨著巨大的挑戰。減少能量消耗，延長網絡生命周期是無線傳感器網絡領域的重要研究方向。拓撲控制作為無線傳感器網絡中減少能量消耗、延長網絡生命周期的重要技術［1］，近年來成為了無線傳感器網絡領域研究的熱點與難點之一。

現有的拓撲控制算法主要集中于節點功率控制和分簇的層次型拓撲控制2個方面，本論文主要針對分簇的層次型拓撲控制算法進行深入研究。LEACH（low-energy adaptive clustering hierarchy）［2］是比較經典的層次型拓撲算法，其他的算法:HEED（hybrid energy-efficient distributed）［3］，DEEUC（distributed energy-efficient unequal clus-tering）［4］等，幾乎都是在LEACH算法基礎上做的改進。

由于LEACH是隨機等概率的選擇簇頭，沒有考慮節點的剩余能量，簇頭數量和質量都得不到保證。針對簇頭能耗過大的問題，Yassein M B等人在文獻［5］中提出了VLEACH（vice-LEACH）算法，該算法簇頭的選擇過程中設置了候選簇頭以均衡全網的能量消耗，但該算法未考慮全網的能量分布情況;在文獻［6］中，王偉超等人提出了LEACH-H算法，該算法在簇頭選擇過程中考慮了能量因素，但其涉及到鄰居節點ID、鄰居節點剩余能量、被選作為簇頭的次數、是否是鄰居節點4個數據項，增加了節點間的通信量，因而增加了能量的消耗;在文獻［7］中，周治平等人提出了EB-LEACH（energy balance LEACH）算法，該算法在簇頭的選擇過程中增加了能量閾值這一約束條件，但該算法只能平衡簇頭地區的能量分布，缺乏對全網能量消耗的平衡;通過對網絡中最佳簇頭數目的考慮，Thein M C M等人在文獻［8］中提出了能量有效的簇頭選擇算法，但該算法忽略了穩定階段的能量消耗。

本文在LEACH分簇算法的基礎上結合EB-LEACH的一些優秀思想，分別從建立階段和穩定階段進行改進，提出了一種能量高效的拓撲控制算法（energy efficient topology control algorithm，EETCA）。其基本思想是:在簇頭的選舉中，考慮節點的剩余能量，保證每輪選舉最佳節點當選簇頭;簇的形成綜合考慮了簇的規模，防止簇頭節點因為簇的規模過大而過早死亡;數據穩定傳輸階段，簇頭與Sink節點間的通信采用多跳路由方式，平衡網絡負載。

1 相關理論

1.1 能耗模型

通常傳感器節點的能量消耗模型采用文獻［2］中提出的無線電能量消耗模型，如圖1所示。

圖1 無線電能量消耗模型Fig 1 Radio energy dissipation model

在該模型中，傳感器節點發送kbit的數據包到距離為d的另一個傳感器節點，所消耗的能量由發射電路損耗和功率放大損耗兩部分組成，用ETx（k，d）表示

節點接收kbit數據包消耗的能量用ERx（k）為接收數據主要是電路能量消耗，具體見式（2）所示

1.2 最優簇數目

在EATC算法中，簇頭與Sink節點的通信采用多跳方式，結合文獻［2］中對LEACH算法最優簇數目的推導，可以對最優簇數目的計算公式進行調整。

則整個網絡的能量消耗Etotal為

其中，EDA為簇頭進行數據融合所消耗的能量，dCH-to-CH為簇頭與相鄰其他簇頭之間的平均距離。

對式（5）求導并令導數等于0，可得出改進的最優簇的數目mopt，計算如式（6）所示

1.3 多跳通信

大量研究表明，當網絡規模較大時，簇頭與Sink節點的通信采用多跳方式可以顯著降低能量消耗［9］。

對于節點多跳通信，如圖2所示，數據在線性網絡鏈路上轉發。其中相鄰2個傳感器節點間的平均距離為d，最后一個節點B到匯聚節點的距離也為d。假設節點A發送一個kbit的數據包，數據包數據經過n跳傳輸到達匯聚節點，所消耗的能量為

式（7）對n求導，并令導數為0，可以求出簇頭發送信息到基站的最優跳數nopt。

圖2 多跳轉發網絡模型Fig 2 Multi-hop transmit network model

2 EETCA實現策略

2.1 網絡模型

為了便于控制策略的描述和分析，先做如下假設:

1）監測區域為規則正方形，基站在監測區域的中心位置，能量沒有限制;

2）節點均勻分布在監測區域中，所有節點都知道自己的位置信息，節點位置固定不動;

3）每個節點具有相同的初始能量，且能夠獲得自身的剩余能量，都可以與基站直接通信;

4）鏈路是對稱的，可以根據源節點的發射功率和接收信號的RSSI估計到源節點的距離;

5）忽略真實環境中存在障礙物等影響通信質量的因素，所有節點的數據包都能夠進行可靠傳輸。

2.2 EETCA 設計思路

2.2.1 簇頭選擇階段

在此過程中，各節點首先選取一個［0，1］之間的隨機數，如果節點n產生的隨機數小于閾值T（n），則將節點n選為候選簇頭。然后繼續計算此時候選節點的剩余能量，并與能量閾值Eth進行比較，當節點的剩余能量大于該輪的能量閾值Eth時，則該節點當選為簇頭，然后簇頭節點向網絡中發送廣播信息［9］。其中T（n）的計算公式為

其中，p為節點當選簇頭的概率;r為選舉輪數;G為最近1/p輪中還未當選過簇頭的節點集合。

第r輪節點的能量閾值Eth的計算公式為

其中，L為網絡預計要運行的輪數，E0為節點的初始能量。

通過引入能量閾值，有效地防止了低能量的節點成為簇頭，避免了因為簇頭死亡造成的數據丟失和網絡空洞，使網絡能量得到均衡的利用，顯著地延長網絡的壽命。

2.2.2 簇的建立階段

離Sink節點近的簇頭承擔了轉發其他簇頭數據信息的任務，其能量消耗比離Sink節點遠的簇頭大，為了保證各簇頭節點的能量消耗達到均衡，離Sink節點近的簇的規模應適當的減小［2］。

假定簇頭節點都以一定的功率進行通信，其傳輸半徑為R，非簇頭節點根據式（10）加入相應的簇

其中，dj-to-CHi為節點j到簇頭i的距離，di-t--Sink為簇頭i到Sink節點間的距離，NCHi為簇頭i的一跳鄰居數，γ為權重。

節點在入簇過程中，綜合考慮了簇頭的鄰居數與傳感器節點到簇頭的距離，防止某個簇的規模過于龐大，均衡簇頭能量消耗。當所有傳感器節點都已成簇之后，簇頭節點為簇內節點分配通信時隙和進行簇內通信的直接序列擴頻碼，然后進入穩定數據傳輸階段。

2.2.3 穩定數據傳輸

基站根據網絡規模使用式（7）算得最優跳數nopt。簇內節點以單跳方式把數據發送到簇頭，簇頭進行數據融合，然后查詢路由表，若Sink節點在其通信范圍之內，則直接將數據信息發送給Sink節點;若不在，則根據最優跳數選擇轉發代價Etotal最小的簇頭作為下一跳，間接將數據傳送到Sink節點。

3 仿真實驗與結果分析

本文采用Matlab建立了網絡仿真模型，對EETCA進行仿真分析，并從網絡整體剩余能量、存活節點數等方面與LEACH，EB-LEACH算法進行比較。

3.1 仿真模型與參數設置

100個傳感器節點隨機分布在100 m×100 m的監測區域內，Sink節點部署在坐標為（50，50 m）的點上，如圖3。

圖3 網絡中隨機分布100個節點的示意圖Fig 3 Schematic diagram of 100 sensor nodes are scattered randomly in networks

實驗的其他參數如表1所示。

表1 實驗參數Tab 1 Experimental parameters

3.2 結果分析

3.2.1 最優跳數

圖4是當跳數n取不同值時，一個數據包經過網絡傳輸到達基站時所消耗的能量關系圖。從圖中可以看出:當n從1變化到2時，能量急劇下降，這主要是因為n=1時節點無線通信模塊的能耗與通信距離的四次方成正比;n=2時，網絡能耗達到最小值。隨著n的增大，增加了網絡對數據的轉發，網絡能耗也隨之增加。

圖4 能量消耗與傳輸跳數關系圖Fig 4 Transmission hop number vs energy dissipation

3.2.2 網絡剩余能量

圖5是網絡整體剩余能量隨網絡運行輪數的變化曲線。從圖中可以看出:本文提出的EETCA每輪剩余的總能量最多，其次是EB-LEACH算法，最差的是LEACH算法。主要因為EETCA中簇頭的選舉、簇的形成以及數據的傳輸方式更加合理，減少了節點的能量消耗，使網絡每輪的剩余能量隨之增加。

圖5 網絡整體剩余能量與網絡運行輪數關系圖Fig 5 Network running number of sheaves vs overall residual energy of network

圖6是3種算法節點剩余能量的標準差隨網絡運行輪數變化的曲線圖。EETCA的節點剩余能量標準差比LEACH算法和EB-LEACH算法的都小，且隨著輪數的增加有明顯的下降趨勢。其根本原因在于，EETCA在均衡簇頭節點和普通節點能耗的同時，還通過減小離Sink節點近的簇的規模均衡了簇頭之間的能耗，使網絡總體能量消耗更加均衡。

圖6 節點剩余能量標準差與網絡運行輪數關系圖Fig 6 Network running number of sheaves vs standard deviation of residual energy of node

3.2.3 網絡生命周期

圖7是隨著網絡運行輪數的推移，在相同的環境條件下，3種算法的存活節點個數與網絡運行輪數關系圖。由于EETCA與EB-LEACH算法在簇頭選擇階段都充分考慮了節點的剩余能量，因此，在同樣規模的環境下網絡生命周期明顯較LEACH算法長。又由于EETCA在簇的形成時考慮了簇的規模，在穩定數據傳輸階段采用單、多跳相結合的方式傳輸數據，所以，EETCA與EB-LEACH算法相比，網絡生命周期又有一定延長。

圖7 存活節點個數與網絡運行輪數關系圖Fig 7 Network running number of sheaves vs number of nodes alive

表2統計了3種算法在第一個節點死亡、10%的節點死亡和剩余節點為節點總數10%時的輪數。如果以網絡剩余節點為節點總數10%作為網絡生命周期判斷，3種算法網絡生命周期分別為707，1484，1633，可以看出:EETCA有效地延長了網絡生命周期。

表2 3種算法節點死亡輪數比較Tab 2 Death number of rounds comparison of three algorithms of node

4 結束語

本文提出了一種能量高效的拓撲控制算法，該算法主要從簇頭的產生、簇的形成以及穩定階段數據傳輸3個方面對LEACH進行了改進，并與LEACH和EB-LEACH算法進行比較。仿真實驗驗證了EETCA算法在網絡整體剩余能量、存活節點數方面均優于LEACH和EB-LEACH算法。

［1］Mahfoudh S，Minet P.Survey of energy efficient strategies in wireless Ad Hoc and sensor networks［C］//The Seventh International Conference on Networking，Cancun:IEEE，2008:1-7.

［2］Heinzelman W B，Chandrakasan A P，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002，1（4）:660-670.

［3］Younis O，Fahmy S.HEED:A hybrid，energy-efficient，distributed clustering approach for Ad Hoc sensor networks［J］.IEEE Trans on Mobile Computing，2004，3（4）:660-669.

［4］尚鳳軍，Mehran Abolhasan，Tadeusz Wysocki.無線傳感器網絡的分布式能量有效非均勻成簇算法［J］.通信學報，2009，30（10）:34-43.

［5］Yassein M B，Al-zou'bi A，Khamayseh Y，et al.Improvement on LEACH protocol of wireless sensor networks（VLEACH）［J］.International Journal of Digital Content Technology and Its Applications，2009，3（2）:1-5.

［6］王偉超，代增全，徐啟建.LEACH協議簇頭選擇算法的改進［J］.無線電工程，2010，40（3）:1-3.

［7］周治平，王 亭，張明亮.傳感器網絡中一種能量有效的簇頭選擇機制［J］.計算機工程與應用，2012，48（8）:105-108.

［8］Thein M C M，Thein T.An energy efficient cluster-head selection for wireless sensor networks［C］//2010 International Conference on Intelligent Systems，Modelling and Simulation（ISMS），2010:287-291.

［9］Li C F，Chen G H，Ye M，et al.An uneven cluster-based routing protocol for wireless sensor networks［J］.Chinese Journal of Computer，2007，30（1）:27-36.

［10］Rashed M G，Kabir M H，Ullah S E.WEP:An energy efficient protocol for cluster-based heterogeneous wireless sensor networks［J］.International Journal of Distributed and Parallel Systems（IJDPS），2011，2（2）:54-60.

［11］Saini P，Sharma A K.Energy efficient scheme for clustering protocol prolonging the lifetime of heterogeneous wireless sensor networks［J］.International Journal of Computer Applications，2010，6（2）:30-36.