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

賈銀亮，張馳宇，梁康武

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

0 引 言

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

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

1 相關工作

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

(1)

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

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

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

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

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

2 網絡模型

對無線傳感器網絡的節點假設如下:

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

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

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

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

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

(2)

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

3 MCCH選擇算法

MCCH是一種分簇算法，將網絡的工作狀態劃分成輪，一輪包括建立階段和穩定階段。建立階段的主要工作是選舉本輪的簇頭。

(3)

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

(4)

為了使ni大的節點優先成為簇頭，設置延時時間

ti=(ηi+γ)×t0

(5)

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

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

(6)

算法步驟如下：

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

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

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

6)匯聚節點接收采集的信息數據并收集和各個節點的剩余能量信息。一輪結束后返回步驟(1)循環執行。

4 系統仿真

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

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

圖1 網絡能耗對比

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

圖2 存活節點數對比

5 結 論

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

[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] 洪 榛,俞 立,張貴軍.多級異構無線傳感網高效動態聚簇策略研究[J].自動化學報,2013,39(4):454-460.

[8] 楊永健,賈 冰,王 杰.無線傳感器網絡中LEACH協議的改進[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.