一種基于分環的能量高效無線傳感器網絡分簇路由協議*

吳玉成，李偉琪，胡 真，謝 璐

(重慶大學 通信工程學院，重慶400030)

0 引 言

節點能量受限是無線傳感器網絡(wireless sensor networks，WSNs)的重要特征，設計能量高效的WSNs 路由協議對延長網絡生命周期尤為重要［1～3］。

基于分簇(clustering)的WSNs 路由協議是提高網絡能量效率的有效途徑［4～6］。現有分簇式路由協議主要包括:Heinzelman W 等人提出的低功耗自適應集簇分層(low energy adaptive clustering hierarchy，LEACH)協議［7］;為進一步提高成簇質量，Heinzelman W 等人又提出了集中式成簇算法LEACH－C 和考慮了幾點剩余能量的算法LEACH－E。Lidsey S 等 人 提 出 的PEGASIS(power－efficient gathering in sensor information system)算法［8］以鏈狀拓撲組織節點，該算法需要預知節點位置信息。Younis O 等人提出的HEED(hybrid energy efficient distributed clustering)協議［9］是針對LEACH 協議中簇首分布不均勻的問題提出的改進，但成簇機制需要多次消息迭代。上述三種算法沒有考慮到簇間的能耗均衡，容易造成“熱區”［10］。Soro S 等人最先提出了基于非均勻分簇的UCS(unequal clustering size)協議［11］來解決“熱區”問題，該方法采用兩層同心環狀拓撲，外環中的簇規模比內環中簇規模大。但該方法中的簇首節點及其位置是預先選定的，也沒有成簇機制。李成法、陳貴海等人提出了EEUC(energy－efficient uneven clustering)協議［12］，解決了多跳模式下簇首能耗不均衡引起的“熱區”問題，但簇首選取時未考慮節點的剩余能量和位置，影響了最終簇首的質量和簇的分布。

針對上述算法的缺陷，本文從全網能耗均衡出發，提出了一種基于分環的能量高效WSNs 分簇路由(ring－based energy－efficient clustering routing，RECR)協議。采用同心環狀網絡模型，根據節點的剩余能量和與環中線的距離選舉簇首，改善了簇在網絡中的分布;采用主次簇首輪換機制，減少了每輪成簇所帶來的能量開銷。仿真結果表明:與LEACH 和HEED 協議相比，本文所提算法能夠優化簇的規模與分布，緩解“熱區”問題，有效均衡了全網能耗并延長網絡生命周期。

1 網絡與能耗模型

1.1 網絡模型

本文采用等間隔同心環狀網絡模型，N 個傳感器節點均勻且隨機分布在以Sink 節點為圓心的原型監測區域內，網絡一經部署不再移動，所有節點具有相同功能和唯一ID，節點不具備定位功能，在已知發送方發射功率的前提下根據接收信號強度指示(received signal strength indication，RSSI)計算發送方和自身之間距離。

1.2 能耗模型

本文采用與LEACH 相同的無線通信能量消耗模型。節點發送k bit 數據到距離為d 出所消耗的能量由發射電路損耗和功率放大損耗兩部分構成，即

其中，Eelec為發射電路損耗的能量;當傳輸距離小于閾值d0時，功率放大損耗采用自由空間模型;當傳輸距離大于等于閾值d0時，采用多路徑衰減模型。εfs，εmp分別為這兩種模型中功率放大所需的能量。傳感器接收k bit 數據所消耗的能量為

數據融合也消耗一定的能量，用EDA表示融合1 bit 數據消耗的能量。

2 RECR 協議

2.1 簇首選取

本文所提算法中，簇首的選取分為3 個步驟:

1)確定最優簇首個數

文獻［13］推導了等間隔同心環形網絡模型中各環的簇首個數對網絡能耗的影響，根據文獻［13］的分析，本文以均衡各環簇間能耗和最小化第一環節點能耗為目標，推導各環中最優的簇首個數。網絡模型如圖1 所示，半徑為R 的圓形區域被等分為S 個間隔為h 的環。設第k 環內簇的數目為mk，第k 環節點總數為Nk。

圖1 RECR 的網絡模型Fig 1 Network model for RECR

第一環最優簇首個數為

再以均衡各環簇首平均能耗出發，需滿足Echk=Ech1，即

根據式(3)和式(4)可得各環最優簇首個數。其中，N為 節 點 總 數，k = 1，2，…，S。E表示第k 環中的簇首到第k－1 環中的簇首距離平方的期望。

2)選取候選簇首

首先，網絡中所有節點根據接收到的Sink 節點的信號強度判斷自身處于環狀模型中的第幾環，然后進行候選簇首的競選。各環中的節點競選候選簇首的概率為

其中，pk(i)為第k 環中的節點i 稱為候選簇首的概率;pk為第k 環中簇首節點占環內節點總數的百分比，即pk=mk/Nk;k 是當前的輪數;Eres(i)為節點i 當前剩余能量;Eave－k為第k 環內節點平均剩余能量;s(t)·dist 表示節點i到Sink 節點的物理距離;Lk表示第k 環的環中心線;β 為(0，1)間的隨機數。網絡中所有的節點參與候選簇首的競選，若節點i 產生的隨機數小于pk(i)，則競選成功，并以環間距h 為半徑廣播競選成功消息，該廣播消息內容包括:節點ID，節點所在環號，節點當前剩余能量。

3)確定最終簇首若候選簇首s(i)剩余能量比其鄰里(h/2 半徑內)同屬一環的其他候選簇首的能量都高，則s(i)當選為最終簇首，并以2h 為半徑廣播獲勝消息，消息內容包括:節點的ID，剩余能量，與Sink 節點的物理距離，所在環數。非簇首節點根據該消息選擇最近的簇加入。

2.2 主次簇首輪換

各環在每1/pk輪在全環進行簇首的重新選取，其余輪次采用主次簇首輪換機制。主次簇首輪換的過程為:每一輪簇內數據傳輸階段，非簇首節點將感知到的數據信息以數據包的形式發送給本簇簇首，并在數據包包頭插入自身信息，包括ID 號，剩余能量。本簇簇首(主簇首)根據各個包頭信息選擇下一輪簇首(次簇首)，并單播發送消息告知被當選的次簇首節點。次簇首的選取原則如下

其中，dtoCH(i)為非簇首節點到其所屬簇首節點的距離。主簇首選取T(i)值最大的非簇首節點為次簇首。

3 仿真與性能分析

3.1 仿真環境

本文以LEACH 和HEED 協議作為對比，在Matlab 中驗證分析RECR 協議的性能。仿真環境如下:監測區域為半徑R=240 m 的圓形區域，分為環距h=80 m 的3 個環形區域，隨機部署1 000 個傳感器節點。根據2.1 中的最優簇首個數公式計算出第一環簇首數為10，第二環為17，第三環為21。簇首選舉算法中的參數β 無閉合表達式，本文通過大量仿真實驗確定其最優值為0.8。節點初始能量設置為1 J，數據報長度為4 000 bit，Eelec=50 J/bit，εfs=10 pJ/(bit·m2)，εmp=0.001 3 pJ/(bit·m2)，EDA=5 nJ/bit，d0=87 m。

3.2 仿真結果與分析

1)網絡生命周期

圖2 比較了RECR，LEACH，HEED 網絡中存活的節點數隨輪次的變化。如圖所示，RECR 第一個節點死亡的時間和最后一個節點死亡的時間都晚于其他兩種協議，并且RECR 第一個節點死亡與全網節點死亡的時間跨度更小。這是因為RECR 算法選擇剩余能量高且離環中心線較近的節點為簇首，避免了LEACH 協議中低能量節點當選簇首而過早死亡和HEED 協議在簇首選舉過程中反復迭代造成的能量開銷。圖3 分別對RECR，LEACH，HEED 三種協議的第一個節點死亡時間(FND)、節點死亡50%的時間(HND)、節點全部死亡的時間(LND)進行比較。顯然，RECR 的性能較優。

圖2 存活節點數目隨輪次的變化Fig 2 Variation of survival node number with round

圖3 節點死亡時間比較Fig 3 Comparison of node death time

2)全網剩余能量

圖4 比較了RECR，LEACH，HEED 全網剩余能量隨時間變化的情況。由于RECR 協議采用了主次簇首輪換機制，從而節約了大量能量。由圖可見，RECR 協議的全網剩余能量隨輪次的增加而近似呈線性下降，性能顯著優于其他兩種算法。

圖4 全網剩余能量比較Fig 4 Comparison of global network residual energy

3)簇首消耗的能量

圖5 比較了RECR，LEACH，HEED 簇首消耗的總能量隨時間變化的情況。LEACH，HEED 每輪產生的簇首數目大于RECR，并且每輪均進行簇首重選，導致了簇首能量消耗較大。RECR 協議的簇首個數少且數目穩定，不需每輪重選簇首而產生額外的能量開銷，因而，簇首消耗能量之和波動小。

圖5 簇首消耗能量之和比較Fig 5 Comparison of cluster head energy consumption summation

4)簇首能耗方差

算法是否較好地均衡了簇首的能耗，可以通過簇首能耗的方差反映出來。圖6 比較了RECR，LEACH、HEED 簇首方差隨時間變化的情況。從圖6 明顯看出:RECR 簇首的方差最低且波動較小，較穩定，因此相比較LEACH，HEED 最好地均衡了簇首的能耗。LEACH 因為是隨機產生簇，簇首分布不均勻，導致簇首能量消耗不均勻。HEED中未被覆蓋的節點獨立成簇，導致某些簇可能只含有一個節點即簇首本身，因此，導致全網簇首負載不均衡，能量消耗差別較大。

圖6 簇首消耗的能量方差比較Fig 6 Comparison of cluster head energy consumption variation

4 結 論

本文在分析了幾種典型隨機分簇型路由協議的基礎上，提出了一種RECR 算法。該算法將監測區域分成等間隔的多個環形區域，在各環中根據各環最優簇首數目、節點剩余能量、節點距離環中心線的距離進行簇首的選擇，使得網絡成簇均勻合理。同時，引入了主次簇首輪換機制，降低簇首重選頻率以節省能耗，有效地延長了網絡生命周期。

［1］ Liang Yuzhu，Zhang Aili，Li Yongzhen.An energy effective routing protocol efficiency constructs cluster topology for WSNs［C］∥Proceedings of the 2013 Third International Conference on Instrumentation，Measurement，Computer，Communication and Control(IMCCC)，Shenyang:IEEE，2013:1097－1100.

［2］ Pantazis N A，Nikolidakis S A，Vergados D D.Energy－efficient routing protocols in wireless sensor networks:A survey［J］.Communications Surveys＆Tutorials，2013，15(2):551－591.

［3］ Yi Xiushuang，Jiang Peijun，Wang Xingwei，et al.Survey of energy－saving protocols in wireless sensor networks［C］∥Proceedings of the 2011 First International Conference on Robot，Vision and Signal Processing(RVSP)，Kaohsiung:IEEE，2011:208－211.

［4］ Soua R，Minet P.A survey on energy efficient techniques in wireless sensor networks［C］∥Proceedings of 2011 4th Joint IFIP Wireless and Mobile Networking Conference(WMNC)，Toulouse:IEEE，2011:1－9.

［5］ Doddapaneni K，Omondi F A，Ever E，et al.Deployment challenges and developments in wireless sensor networks clustering［C］∥Proceedings of 2014 28th International Conference on Advanced Information Networking and Applications Workshops(WAINA)，Victoria，BC，IEEE，2014:227－232.

［6］ Liu Mengyao，Zhang Yangyan，Li Xia.Ring－based security energy－efficient routing protocol for WSNs［C］∥Proceedings of The 26th Chinese Control and Decision Conference，2014 CCDC，Changsha:IEEE，2014:1892－1897.

［7］ Heinzelman W，Chandrakasan A，Balakrishnan H.Energy efficient communication protocol for wireless micro sensor networks［C］∥Proceedings of the 33rd Annual Hawaii International Conference on System Sciences，Maui，HI，2000:1－10.

［8］ Lidsey S，Raghavendra C S.PEGASIS:Power－efficient gathering in sensor information systems［C］∥Proeeedings of the IEEE Aerospace Conference，Montana，USA，2002:1125－1130.

［9］ Younis O，Fahmy S.HEED:A hybrid，energy－efficient，distributed clustering approach for Ad－Hoc sensor networks［J］.IEEE Transaction on Mobile Computing，2004，3(4):660－669.

［10］Baker D J，Ephremides A.The architectural organization of a mobile radio network via a distributed algorithm［J］.IEEE Trans Commun，1981，29(11):1694－1701.

［11］Soro S，Heinzelman W B.Prolonging the lifetime of wireless sensor networks via unequal clustering［C］∥Proceedings of 19th IEEE International Conference on Parallel and Distributed Processing，2005:1－8.

［12］李成法，陳貴海，葉 懋，等.一種基于非均勻分簇的無線傳感器網絡路由協議［J］.計算機學報，2007，30(1):27－36.

［13］劉 志，裘正定.基于分環多跳的無線傳感網分簇路由算法［J］.通信學報，2008，29(3):104－113.