基于簇頭分級的改進非均勻分簇算法*

康 琳，董增壽

（太原科技大學電子信息工程學院，太原030024）

無線傳感器網絡被越來越多地應用于森林火災監控、戰場狀況檢測、動物行為監控等領域。在這些應用中，采用電池供電的傳感器節點被隨機地部署在無人到達的惡劣環境中，節點的再供電幾乎是不可能的，在能量受限的傳感網絡中，設計能量有效的路由策略以延長網絡的生存時間成為亟待解決的問題。

傳感器網絡中節點之間常形成簇狀的分層拓撲，被選中的簇頭節點CH（Cluster Head）將成員節點CM（Cluster Member）收集的數據包聚合為單一數據，并通過直接通信或CH中繼，將數據傳輸至匯聚節點（Sink）［1-2］，CH的數據聚合及CH之間的多跳中繼減少了網絡中冗余數據傳輸的能耗，因此，網絡的生存時間得以延長［3-4］。

但是，在成簇網絡中，距離sink節點較近的CH由于承擔過重的簇間中繼轉發任務，會過早的耗盡能量而形成“熱點”，引發網絡的不連通。文獻［5］設計了能量有效的非均勻成簇算法EEUC（Energy Efficient Unequal Clustering），首次提出了競爭半徑的概念，以CH的可變競爭半徑來調節簇的大小，使距離sink節點較近的CH擁有較小的簇，而較遠的CH形成較大的簇，以均衡CH消耗在簇內以及簇間中繼的能量，解決熱點問題，但是，算法的簇頭選舉過程耗能較多。文獻［6］通過優化非均勻簇的大小及簇頭輪換均衡了網絡能耗。特別地，對于節點分布均勻的傳感器網絡，文獻［7］設計了一種非均勻成簇策略（UCA）來均衡節點簇內及簇間的能耗，延長網絡生存時間。文獻［8］將備選CH的剩余能量、與sink節點的距離以及備選CH的度數作為模糊量，利用模糊算法選取了最佳CH以及競爭半徑。文獻［9］則基于PSO優化算法為非均勻簇選取了最優的雙簇頭。文獻［10］利用節點的剩余能量、節點到sink節點的距離、節點的鄰居節點數以及節點到簇頭的距離來優化非均勻簇的簇頭選擇。文獻［11］采用混合蛙跳算法優化了簇頭選擇；文獻［12］利用對節點選票及傳輸距離的加權，優化了非均勻簇的簇頭選取。文獻［13］則利用動態分簇及基于節點休眠/喚醒機制改進了非均勻簇的簇間路由。文獻［14］基于網絡的動態分區產生的區頭以及非均勻簇的簇頭構造了最優的簇間協作路由均衡網絡能耗。

雖然各類的非均勻成簇算法均通過選擇最佳CH、競爭半徑及簇間路由均衡了傳感器網絡中的能耗分布，解決了熱點問題。但是，在傳感器網絡每一輪數據傳輸開始時，即使當前CH還有足夠的能量完成數據傳輸，CH都會得到輪換，而在新CH的競爭選取過程中，競爭CH的節點需要向整個網絡廣播自身的ID號、剩余能量、感知半徑、到sink節點的距離，用以形成以自身為CH的新的簇內通信以及簇間路由。頻繁的CH輪換會引發過多的廣播能量開銷，進而縮短網絡的生存時間。

針對頻繁的簇頭輪換對網絡生存時間的影響，本文提出了一種基于簇頭分級的改進的非均勻成簇算法 CHCI（CH Classified Improved Unequal Clus?tering），來降低網絡中過多的廣播能量開銷。在一個簇內，設置主要簇頭節點（PrimaryCH）以及次要簇頭節點（Secondary CH），PCH完成簇內數據的聚合，SCH承擔簇間數據轉發任務，為PCH設置CH輪換閾值，只有當前PCH的剩余能量低于CH重選閾值時，才會啟動CH輪換過程，并將簇間中繼路由的選擇轉化為二次規劃問題，選擇了能耗最低的簇間通信路由，延長網絡的生存時間。

本文第1部分對系統模型及場景進行了描述。第2部分具體介紹CHCI算法。第3部分通過仿真對比了本算法與經典的LEACH以及經典的EEUC算法性能的比較，最后，第4部分總結全文。

1 系統模型

假設N個傳感器節點隨機分布在M×M區域內，Sink節點處于M×M區域之外，其他基本假設如下：①Sink節點位置信息已知。②所有隨機分布的節點皆為靜態節點。③每一個節點有獨立的ID號和相同的初始能量Eo。④節點沒有配置GPS，但是在網絡初始化階段，節點可以根據RSSI值計算自身與sink節點的距離。⑤節點可以根據自身與Sink節點的距離調整傳輸半徑。

節點無線傳輸的能耗模型采用一階無線電模型［15］。將每l比特數據傳輸d所需要的能耗表示如下：

接收此l比特數據的能耗為：

式中：ETx表示發射節點能耗，ERx表示接收節點能耗，Eelec表示每發送或接收1比特數據電路消耗的能耗。l代表傳輸數據的長度。ξfs及ξmp分別表示傳感器節點中放大器在自由空間以及多徑衰落模型下的能耗系數。當d＜d0時，選用電波傳輸的自由空間模型，當d≥d0時采用多徑衰落模型，閾值d0表示如下：

2 CHCI算法

CHCI算法的數據傳輸主要分為：PCH選取，簇內通信建立，SCH選擇，簇間中繼選擇4個階段。以下先說明本算法的簇頭分級模型。

2.1 簇頭分級模型

在網絡初始化階段，Sink向區域內所有節點廣播“hello”數據包，每一個節點根據RSSI值確定自身距離sink節點的距離dtosink。而后，為了節省能量，我們將以隨機概率μ處于工作狀態的節點根據概率閾值P分為兩類：活躍節點及睡眠節點，如表1所示。

表1 節點工作狀態區分

當節點成為活躍節點后，加入活躍節點集，并向節點集中的其余節點廣播包含自身ID號、剩余能量、當前感知半徑信息的HEAD_MSG數據包，參與簇頭節點的競爭。參與競爭節點的當前感知半徑被定義為競爭半徑，用下式表示：

式中，d（i，Sink）表示任意節點i與 sink之間的距離。dmax及dmin分別表示所有dtosink數值中的最大以及最小值。c被定義為半徑控制因子，Rini為所有節點在網絡初始化時的半徑。而后，在活躍節點集中，擁有最高剩余能量的節點j當選為PCH，向其余節點發送CONFIRM_CH_MSG數據包以確認自身的PCH身份，沒有當選為PCH的節點向其周圍的CH節點發送JOIN_MSG數據包以確認自己加入此PCH，成為其成員節點。對于睡眠節點，當其接收到當選PCH廣播的CONFIRM_CH_MSG信息后，變為激活節點，向鄰近PCH節點發送JOIN_MSG信息，當PCH為其分配數據傳輸時隙后，這些節點會接收到ACK_MSG以確認自身已成為該PCH的成員節點。此后，PCH根據競爭半徑RTH(j)獲得簇的成員數kin，PCH為kin個成員節點分配TDMA時隙表，來完成簇內節點信息的匯聚，成員節點只在被分配的時隙內完成數據傳輸，在其他節點傳輸數據時則進入睡眠狀態，以減少數據包碰撞來減少網絡的能耗。假定當前輪t內，每個成員節點傳輸l比特數據，則簇內數據收集完成后，PCH的剩余能量為

則當前輪t網絡的平均剩余能量定義為

定義第t輪SCH節點的選舉因子p(k)為

顯然，我們選擇p(k)較高的節點作為SCH，將接收到的來自PCH的數據傳輸至Sink節點。其余節點作為成員節點將數據傳輸至PCH。

2.2 SCH-sink的中繼路由選擇

當SCHk從PCH接收到聚合的數據后，會廣播一個包含自身ID號、剩余能量、以及dtosink的STATE_MSG信息給其余SCH，而后節點k根據表2選取直接單跳通信或借助其余SCH的多跳通信以完成簇間中繼，將信息傳輸至Sink節點。

表2 中繼選擇方案

TDmax是判定SCHk采用單跳或多跳通信方式的閾值。

圖1 能量有效路由的中繼節點選擇示意圖

如圖1，當SCHk通過鄰近sink的節點m作為中繼節點時，數據傳輸時耗費的能量可以表示為：

為了減少能耗，SCHk需選擇一條經過中繼節點m?的能量有效的路由，節點m?可通過以下方式選擇：

式中，Ω(k)表示SCHk的一跳鄰居節點集。

2.3 PCH重選因子

在數據傳輸階段，當第t（t≥1）輪數據傳輸結束后，引入PCH重選因子T（t+1）來降低PCH輪換的頻率，T（t+1）可表示為：

表3 CHCI算法中的數據傳輸

3 仿真與分析

3.1 算法的消息復雜度

假定傳感器網絡中共有N個節點，在執行CHCI算法網絡初始化時，Sink節點向N個節點廣播“hel?lo”數據包，N×P個節點被選為激活節點參與簇頭競爭，會廣播N×P條HEAD_MSG信息，若M個節點競選PCH成功，會發送M條CONFIRM_CH_MSG信息，其余N-M個節點收到CONFIRM_CH_MSG信息后，向PCH發送JOIN_MSG信息，M個PCH發送NM個ACK_MSG信息以確認加入節點被分配了時隙。簇內通信的消息復雜度為O（N）。簇間路由建立時，M個SCH在網絡內產生M條STATE_MSG信息，計算最佳路由時，消息復雜度為O（M）。

若T（t+1）=1，PCH不得到更換，則網絡中不需要重復簇內通信的建立過程，只需要SCH建立簇間路由，此時算法的消息負雜度為O（M），若T（t+1）=0，PCH更換，網絡重新進行簇內及簇間通信的建立，由于N?M，算法的消息復雜度為O（N）。

3.2 仿真參數設置

假設400個節點隨機分布200 m×200 m的區域內。主要仿真參數參考表4。

本部分通過仿真分析了參數c，Rini，a，TDmax對網絡性能的影響，然后比較了CHCI協議與經典的LEACH算法以及非均勻成簇的EEUC算法對網絡生存時間以及節點平均剩余能量的影響。

表4 仿真參數

3.3 仿真結果及分析

圖2顯示了參數c對于首個死亡節點出現輪數的影響，對于一個確定的初始競爭半徑Rini，c增大時，競爭簇頭的節點的競爭半徑減小，網絡中會出現更多的簇，消耗在簇間中繼通信上的能量增大，相應地會縮短網絡生存時間，從圖2中可以看到，當c=0.6時，網絡中的簇的數量可以均衡簇內及簇間能耗，從而延遲首個死亡節點出現的輪數。

圖3顯示了Rini對首個死亡節點出現輪數的影響，當Rini增大時，網絡中簇的尺寸增大，引起PCH用于簇內匯聚的能耗增大，當Rini=30 m時，簇內及簇間中繼通信的能耗得到均衡，首個死亡節點出現的輪數出現在850輪，延長了網絡生存時間。

圖2 參數c對網絡性能的影響

圖3 參數Rini對網絡性能的影響

圖4顯示了參數a對網絡死亡節點的影響，當進行了600輪數據傳輸后，若a=0，即沒有選取SCH時，大概60個節點死亡，當a=0.4時，由于SCH分擔了PCH用于簇間中繼的能耗，降低了PCH的能量損耗，從而降低了PCH輪換的頻率，死亡節點的數量達到最少，SCH的引入降低了網絡中死亡節點的數量，改善了網絡的性能。

圖5顯示了TDmax對網絡生存時間的影響，從表2可知，若TDmax較小簇間通信主要采用中繼通信，若TDmax變大，簇間通信主要采用直接通信，當TDmax=140 m時，網絡中有更多的節點存活。

圖4 參數a對網絡死亡節點的影響（r=600）

圖5 參數TDmax對網絡性能的影響

圖6、圖7分別比較了LEACH，EEUC，CHCI算法執行1200輪后，節點的平均剩余能量以及存活節點的數量，這里將一半節點死亡定義為網絡生存時間的結束。LEACH算法在執行700輪后，一半節點死亡，采用了非均勻成簇的EEUC算法執行750輪后，一半節點死亡，網絡不再連通。采用CHCI算法后，由于SCH的存在，節省了節點的能耗，增加了節點的平均剩余能量，從而降低了PCH輪換的頻率，此外，簇間中繼最佳路由的確定也降低了SCH的能耗，網絡的總體能耗得到降低，生存時間被延長至900輪。生存時間比EEUC算法提高了20%。

圖6 節點平均剩余能量比較

圖7 存活節點比較

4 結論

本文設計了基于簇頭分級的新的非均勻成簇算法CHCI。在主要簇頭PCH當選后，每一個簇內會選出一個次要簇頭節點SCH來承擔簇間中繼轉發任務，以此降低PCH的能耗。PCH重選因子T（t+1）在每一輪數據傳輸結束時得到更新，只有在當前簇頭的剩余能量低于PCH輪換閾值時，啟動PCH的輪換，來降低網絡中由于EEUC算法中CH頻繁更換引起的額外的廣播開銷，延長網絡的生存時間，并將SCH傳輸的中繼選擇問題通過二次規劃問題得出能量有效的路由。仿真結果表明，與LEACH以及非均勻成簇的EEUC算法相比，CHCI算法延長了網絡生存時間。

［1］Tian Q，Coyle E J.Optimal Distributed Detection in Clustered Wireless Sensor Networks：The Weighted Median［C］//INFO?COM，2006.

［2］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-Effi?cient Communication Protocol for Wireless Microsensor Networks.In：Proc of the 33rd Hawaii Int’l Conf on System Science（HICSS 2000），2000：3005-3014.

［3］Engels D W，Sarma S E.The Reader Collision Problem.In：Proc of IEEE International Conference on Systems，Man and Cybernet?ics.SMC，2002.

［4］AbdelSalam H S，Olariu S.Bees：Bioinspired Backbone Selection in Wireless Sensor Networks［J］.Parallel and Distributed Sys?tems，IEEE Transactions on，2012，23（1）：44-51.

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

［6］Xiang M，Shi W R，Jiang C J，et al.Energy Efficient Clustering Al?gorithm for Maximizing Lifetime of Wireless Sensor Networks［J］.AEU—Int’l Journal of Electronic and Communication，2010，64（4）：289-298.

［7］Yuan Huiyong，Liu Yongyi，Yu Jiaping.A New Energy-Efficient Unequal Clustering Algorithm for Wireless Sensor Networks［C］//IEEE Conference Proceedings，2011：431-434.

［8］Mao S，Zhao C，Zhou Z，et al.An Improved Fuzzy Unequal Clus?tering Algorithm for Wireless Sensor Network［J］.Mobile Net?works and Applications，2013，18（2）：206-214.

［9］門順治，孫順遠，徐保國.基于PSO的無線傳感器網絡非均勻分簇雙簇頭路由算法［J］.傳感技術學報，2014，27（9）：1281-1286.

［10］張文梅，廖福保.改進的無線傳感器網絡非均勻分簇路由算法［J］.傳感技術學報，2015，5：21.

［11］劉洲洲，王福豹，張克旺.基于混合蛙跳算法的非均勻分簇WSNs路由協議［J］.計算機應用研究，2013，30（7）：2173-2176.

［12］張瑞華，賈智平，程合友.基于非均勻分簇和最小能耗的無線傳感網絡路由算法［J］.上海交通大學學報，2012，46（11）：1774-1778.

［13］彭鐸，黎鎖平，楊喜娟.一種能量高效的無線傳感器網絡非均勻分簇路由協議［J］.傳感技術學報，2014，27（12）：1687-1691.

［14］孫彥清，彭艦，劉唐，等.基于動態分區的無線傳感器網絡非均勻成簇路由協議［J］.通信學報，2014，35（1）：198-206.

［15］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-Effi?cient Communication Protocol for Wireless Microsensor Networks［C］//System Sciences，2000.Proceedings of the 33rd Annual Ha?waii International Conference on.IEEE，2000，（2）：10.