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

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

0 引 言

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

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

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

1 網(wǎng)絡(luò)與能耗模型

1.1 網(wǎng)絡(luò)模型

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

1.2 能耗模型

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

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

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

2 RECR 協(xié)議

2.1 簇首選取

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

1)確定最優(yōu)簇首個數(shù)

文獻［13］推導(dǎo)了等間隔同心環(huán)形網(wǎng)絡(luò)模型中各環(huán)的簇首個數(shù)對網(wǎng)絡(luò)能耗的影響，根據(jù)文獻［13］的分析，本文以均衡各環(huán)簇間能耗和最小化第一環(huán)節(jié)點能耗為目標，推導(dǎo)各環(huán)中最優(yōu)的簇首個數(shù)。網(wǎng)絡(luò)模型如圖1 所示，半徑為R 的圓形區(qū)域被等分為S 個間隔為h 的環(huán)。設(shè)第k 環(huán)內(nèi)簇的數(shù)目為mk，第k 環(huán)節(jié)點總數(shù)為Nk。

圖1 RECR 的網(wǎng)絡(luò)模型Fig 1 Network model for RECR

第一環(huán)最優(yōu)簇首個數(shù)為

再以均衡各環(huán)簇首平均能耗出發(fā)，需滿足Echk=Ech1，即

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

2)選取候選簇首

首先，網(wǎng)絡(luò)中所有節(jié)點根據(jù)接收到的Sink 節(jié)點的信號強度判斷自身處于環(huán)狀模型中的第幾環(huán)，然后進行候選簇首的競選。各環(huán)中的節(jié)點競選候選簇首的概率為

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

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

2.2 主次簇首輪換

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

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

3 仿真與性能分析

3.1 仿真環(huán)境

本文以LEACH 和HEED 協(xié)議作為對比，在Matlab 中驗證分析RECR 協(xié)議的性能。仿真環(huán)境如下:監(jiān)測區(qū)域為半徑R=240 m 的圓形區(qū)域，分為環(huán)距h=80 m 的3 個環(huán)形區(qū)域，隨機部署1 000 個傳感器節(jié)點。根據(jù)2.1 中的最優(yōu)簇首個數(shù)公式計算出第一環(huán)簇首數(shù)為10，第二環(huán)為17，第三環(huán)為21。簇首選舉算法中的參數(shù)β 無閉合表達式，本文通過大量仿真實驗確定其最優(yōu)值為0.8。節(jié)點初始能量設(shè)置為1 J，數(shù)據(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 仿真結(jié)果與分析

1)網(wǎng)絡(luò)生命周期

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

圖2 存活節(jié)點數(shù)目隨輪次的變化Fig 2 Variation of survival node number with round

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

2)全網(wǎng)剩余能量

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

圖4 全網(wǎng)剩余能量比較Fig 4 Comparison of global network residual energy

3)簇首消耗的能量

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

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

4)簇首能耗方差

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

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

4 結(jié) 論

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

［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，F(xiàn)ahmy 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］李成法，陳貴海，葉 懋，等.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.計算機學(xué)報，2007，30(1):27－36.

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