基于多重競爭的無線傳感器網(wǎng)絡簇頭選擇算法*

賈銀亮，張馳宇，梁康武

(南京航空航天大學 自動化學院，江蘇 南京 210016)

0 引 言

無線傳感器網(wǎng)絡(wireless sensor networks,WSNs)是由部署在監(jiān)測區(qū)域內(nèi)的大量傳感器節(jié)點，通過無線通信方式形成的一個多跳自組織網(wǎng)絡[1]。其依賴于傳感器、無線通信、嵌入式系統(tǒng)等技術(shù)，具有低功耗、低成本、分布式和自組織等特點。隨著節(jié)點體積的縮小、能耗的降低和性能的提升，無線傳感器網(wǎng)絡已開始投入實用。

在無線傳感器網(wǎng)絡的研究中，能效一直是熱點問題。為了延長網(wǎng)絡生存周期，相關的軟硬件得到了大量的研究。分簇算法可以有效延長網(wǎng)絡生存周期，而分簇算法中，簇頭的選擇對網(wǎng)絡能耗有較大影響[2]。本文對分簇算法的簇頭選擇進行研究，提出了一種新的算法。

1 相關工作

LEACH算法[2,3]使用輪的概念，一輪由所有節(jié)點分簇的建立階段，和數(shù)據(jù)采集、傳遞、處理的穩(wěn)定階段組成。在建立階段，各個節(jié)點產(chǎn)生0～1之間的隨機數(shù)。對節(jié)點i而言，若該數(shù)小于閾值T(i)，則該節(jié)點成為簇頭

(1)

式中p為簇頭對存活節(jié)點的占比；r為當前循環(huán)的輪次；G為在最近 1/p輪中未成為簇頭的節(jié)點集合[4]。LEACH算法隨機性較強，實際工作中,由于簇頭的能耗各不相同，仍會帶來節(jié)點能耗不均問題[5]。

針對LEACH算法的缺點，國內(nèi)外的研究者提出了許多改進方案。根據(jù)節(jié)點剩余能量來選擇簇頭可以延長網(wǎng)絡生存周期。文獻[6]引入仿生學，模仿蜜蜂的行為來選擇簇頭；文獻[7]根據(jù)平均能量預測和歷史能耗來選擇簇頭；文獻[8]通過對節(jié)點剩余能量的估算實現(xiàn)對簇頭選舉機制的優(yōu)化，并提出“生命游戲”睡眠調(diào)度模型和利用鄰居節(jié)點作為轉(zhuǎn)發(fā)節(jié)點的多跳通信方式；文獻[9]通過簇內(nèi)進一步細分將整個網(wǎng)絡劃分為3個層次。上述算法在不同程度上提高了網(wǎng)絡生存周期，但較為復雜，增加了節(jié)點的負擔。

由于LEACH協(xié)議分簇的隨機性，不同輪簇頭數(shù)量不同，簇頭的能耗也不同。LEACH-MAC從減少能耗的角度研究了最佳簇頭數(shù)k，在選擇簇頭時逐個選擇，直到簇頭數(shù)量達到k[10]，從而提高了網(wǎng)絡生存周期。

文獻[11]提出了WRECS(weighted residual energy-based cluster head selection)算法，根據(jù)簇內(nèi)節(jié)點數(shù)量的不同，使簇頭節(jié)點在之后若干輪不能再次成為簇頭，從而達到了平衡節(jié)點能耗的目的。

本文提出了一種基于多重競爭的簇頭(multiple competitive cluster head,MCCH)選擇算法，根據(jù)簇頭的剩余能量、鄰節(jié)點數(shù)、到已選定簇頭的距離等因素選擇簇頭，提高了網(wǎng)絡的生存周期。

2 網(wǎng)絡模型

對無線傳感器網(wǎng)絡的節(jié)點假設如下:

1)節(jié)點隨機布設在邊長為L的正方形區(qū)域內(nèi)，位置信息未知。節(jié)點能量有限，并能感知自身的剩余能量。

2)節(jié)點可以收發(fā)數(shù)據(jù)，發(fā)送信號的強度可變。節(jié)點可以感知接收信號的強度，通過與發(fā)送信號的強度比較，可以估算到發(fā)送節(jié)點的距離。

3)節(jié)點工作相互獨立，各個節(jié)點具有唯一的ID，均可成為簇頭。簇頭直接發(fā)送信息到匯聚節(jié)點。

4)匯聚節(jié)點位置固定，具有較強的處理能力。相對于一般節(jié)點，匯聚節(jié)點的能量可以認為無限。

文獻[12]采用的能量模型比較典型，即當傳輸距離為d，發(fā)送數(shù)據(jù)長度為qbit時，能量消耗如式(2)

(2)

式中ETx,ERx分別為收、發(fā)能耗；Eelec為發(fā)送或接收電路每完成1 bit數(shù)據(jù)收發(fā)消耗的能量。dcorssover為閾值，若d

3 MCCH選擇算法

MCCH是一種分簇算法，將網(wǎng)絡的工作狀態(tài)劃分成輪，一輪包括建立階段和穩(wěn)定階段。建立階段的主要工作是選舉本輪的簇頭。

(3)

ηi=1-min[ni×p,1]

(4)

為了使ni大的節(jié)點優(yōu)先成為簇頭，設置延時時間

ti=(ηi+γ)×t0

(5)

式中t0為選定的時間;γ為隨機數(shù)且γ∈[0,1]。對于節(jié)點i，若其可以成為簇頭，則在簇頭選取時首先延時ti。ti到時若簇頭選取仍未結(jié)束，則i成為簇頭。

一般來說，簇頭均勻分布可以減少能耗[13]，本文通過調(diào)整ti來促使簇頭均勻分布。若一個節(jié)點成為簇頭，則以事先選定的強度發(fā)送建簇信息。其他節(jié)點接收該信息，根據(jù)接收信號的強度估算到該簇頭的距離l。并按式(6)更新延時時間

(6)

算法步驟如下：

3)延時結(jié)束時該節(jié)點成為簇頭，廣播建簇信息，信息中包含自身的ID。其他節(jié)點接收建簇信息，估算距離，按式(6)更自身延時時間。

4)匯聚節(jié)點接收建簇信息，當收到P×N個建簇信息后廣播簇頭選舉結(jié)束信息。未成為簇頭的節(jié)點收到該信息后，根據(jù)收到的信號強度，加入最近的簇頭，向其發(fā)送入簇信息并附上自身ID。簇頭接收入簇信息，向發(fā)出請求的節(jié)點返回一確認信息，完成簇的建立。

5)節(jié)點采集信息，通過時分多址(time division multiple access,TDMA)方式送給簇頭并附上自身剩余能量信息。簇頭進行數(shù)據(jù)融合后發(fā)給匯聚節(jié)點。

6)匯聚節(jié)點接收采集的信息數(shù)據(jù)并收集和各個節(jié)點的剩余能量信息。一輪結(jié)束后返回步驟(1)循環(huán)執(zhí)行。

4 系統(tǒng)仿真

使用NS2進行仿真，比較了LEACH，WRECS，LEACH-MAC和MCCH 4種算法的效果。仿真的具體環(huán)境為100個節(jié)點分布在邊長100 m的正方形區(qū)域內(nèi)，匯聚節(jié)點在正方形中心，其他參數(shù)設置：εfs為10 pJ/bit/m2，εmp為0.001 3 pJ/bit/m4，Eelec為50 nJ/bit，dcorssover為87 m，p為0.05。

圖1通過仿真數(shù)據(jù)比較了4種算法在隨機選取的10輪中每一輪的能耗。LEACH算法在簇頭數(shù)量、位置上存在較大的隨機性，且未考慮剩余能量，所以，能耗最大且不同輪的能耗差異較大。WRECS算法優(yōu)先選擇剩余能量高的節(jié)點做簇頭，在一定程度上實現(xiàn)了節(jié)點間的能耗均勻，但該算法不能降低能耗。LEACH-MAC算法可以確保合適的簇頭數(shù)量，從而減少了能耗和不同輪之間的能耗差異。MCCH算法根據(jù)剩余能量、鄰節(jié)點數(shù)、簇頭位置等因素進行競爭，在一定程度上實現(xiàn)了簇頭的均勻分布，所以能耗較小。

圖1 網(wǎng)絡能耗對比

圖2為4種算法網(wǎng)絡生命周期的仿真結(jié)果。從圖中可見，LEACH算法的生命周期最短。WRECS算法考慮了節(jié)點能耗的均勻，在一定程度上延遲了節(jié)點開始死亡的時間，但由于該算法不能降低能耗，所以,節(jié)點全部死亡的時間早于LEACH算法。LEACH-MAC算法穩(wěn)定了簇頭數(shù)量，從而減少了能耗，但由于簇頭分布不均勻等因素，網(wǎng)絡壽命提高幅度有限。MCCH算法在剩余能量較多的節(jié)點中選擇簇頭，并優(yōu)先選擇鄰節(jié)點多且到已選定簇頭距離合適的節(jié)點成為新的簇頭，從而提高了網(wǎng)絡的生存周期。

圖2 存活節(jié)點數(shù)對比

5 結(jié) 論

提出了MCCH算法,算法中節(jié)點根據(jù)多種因素進行競爭成為簇頭，剩余能量較多，選擇鄰節(jié)點多，到已選定簇頭距離合適的節(jié)點成為簇頭的可能性更大。通過仿真證明了該算法能延長網(wǎng)絡生存周期。下一步的工作可以研究簇覆蓋范圍與能耗的關系，根據(jù)能耗動態(tài)的調(diào)整簇覆蓋范圍。

[1] Kulkarni R V,F?Rster A,Venayagamoorthy G K.Computational intelligence in wireless sensor networks:A survey[J].IEEE Communications Surveys & Tutorials,2011,13(1):68-96.

[2] Heinzelman W B,Chandrakasan A P,Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications,2000,1(4):660-670.

[3] Al-Karaki J N,Kamal A E.Routing techniques in wireless sensor networks:A survey[J].IEEE Wireless Communications,2004,11(6):6-28.

[4] Nayebi A,Sarbazi-Azad H.Performance modeling of the LEACH protocol for mobile wireless sensor networks[J].Journal of Parallel & Distributed Computing,2011,71(6):812-821.

[5] Roseline R A,Sumathi P.Local clustering and threshold sensitive routing algorithm for wireless sensor networks[C]∥2012 International Conference on Devices,Circuits and Systems(ICDCS),IEEE,2012:365-369.

[6] Saleem M,Ullah I,Farooq M.BeeSensor:An energy-efficient and scalable routing protocol for wireless sensor networks[J].Information Sciences,2012,200(2):38-56.

[7] 洪 榛,俞 立,張貴軍.多級異構(gòu)無線傳感網(wǎng)高效動態(tài)聚簇策略研究[J].自動化學報,2013,39(4):454-460.

[8] 楊永健,賈 冰,王 杰.無線傳感器網(wǎng)絡中LEACH協(xié)議的改進[J].北京郵電大學學報,2013,36(1):105-109.

[9] Chen Y L,Wang N C,Shih Y N.Improving low-energy adaptive cllustering hierarchy architectures with sleep mode for wireless sensor networks[J].Wireless Personal Communications，2014,75(1)：349-368.

[10] Batra P K,Kant K.LEACH-MAC:A new cluster head selection algorithm for wireless sensor networks[J].Wireless Networks,2016,22(1):1-12.

[11] Bao X,Xie J,Nan L,et al.WRECS:An improved cluster heads selection algorithm for WSNs[J].Journal of Software,2014,9(2):78-89.

[12] Kumar D, Aseri T C, Patel R B.EEHC:Energy efficient heterogeneous clustered scheme for wireless sensor networks[J].Computer Communications, 2009, 32(4):662-667.

[13] Su J S,Guo W Z,Yu C L,et al.Fault-tolerance clustering algorithm with load-balance aware in wireless sensor networks[J].Chinese Journal of Computers,2014,37(2):445-456.