異構無線傳感器網絡的分簇算法

摘 ?要：針對LEACH算法缺乏對網絡中能量異構性的考慮問題，為延長網絡穩定周期，均衡節點能量消耗，提出一種改進的分簇算法。算法充分利用高級節點的能量優勢，在簇頭選舉階段，優先選舉高級節點當選簇頭，改善異構無線傳感器網絡中的簇頭選舉機制。仿真結果表明，改進后的算法均衡了網絡能量消耗，延長了網絡的穩定周期和一半節點死亡輪數。

關鍵詞：異構;無線傳感器網絡;分簇;算法

中圖分類號：TN929.5;TP212.9 ? ? 文獻標識碼：A 文章編號：2096-4706（2020）15-0149-04

Abstract：LEACH lacks the consideration of energy heterogeneity in the network. In order to prolong the network stability period and balance the energy consumption of nodes，an improved clustering algorithm was proposed. The algorithm makes full use of the energy advantages of advanced nodes. In the cluster head election stage，it elects advanced nodes to be cluster head preferentially，which improves cluster head election mechanism in heterogeneous wireless sensor networks. The simulation results show that the improved algorithm balances energy consumption of network，prolongs stability period of network and also the death rounds of half nodes.

Keywords：heterogeneous;wireless sensor networks;cluster;algorithm

0 ?引 ?言

無線傳感器網絡（Wireless Sensor Networks，WSNs）是一門綜合性的交叉學科，是物聯網的重要組成部分[1]。無線傳感器網絡由大量的傳感器節點組成。根據網絡中節點是否相同，分為同構無線傳感器網絡和異構無線傳感器網絡[2]。無線傳感器網絡的異構性分為計算能力異構性、鏈路異構性、網絡協議異構性、節點能量異構性[3]。當網絡工作一段時間或部署新的節點后，各節點的能量不盡相同，因此，在大多數情況下，無線傳感器網絡普遍存在節點能量異構性。

在環境惡劣或危險的監測區域，基本是無人值守的，無線傳感器網絡節點一旦部署就無法補充能量或替換[4]。節點能量的受限性，使得如何更好地利用節點能量成為WSNs的首要設計目標。分簇路由算法能比平面路由算法更有效地利用能量，節省網絡能耗[5]。

現有的經典分簇算法存在簇頭能耗過高、選舉機制不合理等問題，特別當網絡中能量異構性強時，沒有充分利用高級節點能量優勢，使得網絡出現能耗不均衡、穩定周期短等不良特性。針對以上問題，基于本校“無線傳感器網絡的節能分簇算法研究”項目，作者在LEACH（Low-Energy Adaptive Clustering Hierarchy）[6]算法基礎上進行改進，提出一種適用于異構無線傳感器網絡的分簇算法。在前面輪數中，網絡中能量異構性較強時，選擇高級節點當選簇頭;當能量異構性表現得不明顯時，提高剩余能量高的節點當選簇頭的幾率，優化簇頭選舉機制，延長網絡穩定周期。

1 ?相關研究

1.1 ?LEACH算法

LEACH算法是一個經典的分布式分簇路由算法。在LEACH算法中，工作周期按輪進行，每輪分為簇建立階段和數據傳輸階段[6]。在簇建立階段，每個節點生成一個隨機數，與設定的閾值作比較，決定自己是否成為簇頭。在此階段，整個網絡劃分為若干個分簇，每個分簇包含一個簇頭節點和若干個簇內成員節點。簇內成員節點負責監測區域內的傳感信息，發送至所在分簇的簇頭節點。簇頭節點融合各簇內成員節點的信息，發送至匯聚節點。簇內成員節點不直接與匯聚節點通信，而每輪中，簇頭節點都與匯聚節點直接通信，因此簇頭節點耗能較多。為了均衡簇頭的能耗，LEACH算法采用隨機選舉簇頭的方式，讓所有節點以輪流的方式當選耗能較多的簇頭節點。當序號n節點生成的隨機數小于式（1）的閾值T（n）時，如果此節點在前面1/p輪中沒有當選過簇頭節點，則在此輪中當選為簇頭節點。

簇頭節點選舉后，其余節點加入到最近的分簇中，簇頭節點向其簇內節點發送TDMA調度表，簇內各節點根據TDMA調度表，向簇頭節點發送數據。

1.2 ?異構分簇算法

針對LEACH算法假定節點初始能量相同，適用于同構無線傳感器網絡，國內外學者考慮節點能量異構性，提出了各種改進策略。文獻[5]提出一種基于能量分布的非均勻分簇算法，簇頭的選舉中考慮節點剩余能量分布狀況，采用非均勻的簇半徑，形成大小非均勻的簇。文獻[7]中考慮節點采集數據周期差異、初始能量的異構性和分布密度，結合模糊邏輯原理，采用競爭方式來選舉最優簇頭集合，成員節點采用類勾股定理的方法來選擇加入分簇。文獻[8]采用一種異構感知的分布式算法，針對異構無線傳感器網絡中不同能量級別的節點，根據能量來設置不同的簇頭當選閾值，增大高級節點當選簇頭的幾率。文獻[9]提出一種基于能量異構的多鏈路算法，根據高級節點能量和全網平均能量來確定簇頭的閾值，采用層間多鏈路多跳傳輸和簇內單跳傳輸的方式。文獻[10]提出一種多級異構的能量優化分簇算法，簇頭的閾值函數中考慮節點位置和剩余能量，提高離匯聚節點近且剩余能量高的節點當選簇頭幾率。

為了均衡網絡能量消耗，針對異構無線傳感器網絡中不同能量的節點，設置不同的當選簇頭幾率，才能有效利用網絡中節點能量異構性，提高網絡性能。

2 ?改進分簇算法

2.1 ?網絡模型

根據異構無線傳感器網絡的特征，提出以下假設：

（1）網絡是靜態或近似靜態的，節點隨機部署后，位置不再變化。

（2）只有一個匯聚節點，位于網絡上邊界的中點處，能量充足，不受限制。

（3）節點可與匯聚節點通信，具有唯一的ID號，能感知自身的能量水平和位置信息。

（4）網絡中有兩種不同初始能量水平的節點，能量高的為高級節點，能量低的為普通節點，節點能量不可補充。

（5）無線信道具有對稱性。

（6）所有節點的發射功率可控制。

2.2 ?能量消耗模型

本文采用無線電能量消耗模型，節點發送數據的能耗ETX與通信距離d、數據包大小L有關，如式（2）所示：

2.3 ?簇頭選舉與分簇

在簇頭選舉階段，考慮普通節點和高級節點初始能量不一樣，高級節點比普通節點高出能量倍數為α，為了充分利用網絡中高級節點的能量優勢，算法優先選舉高級節點為簇頭節點。

在前面輪數中，當輪數小于或等于輪數閾值r0時，高級節點比普通節點高出的能量較多，即網絡中節點的能量異構性較強，選擇高級節點為簇頭節點，承擔耗能較多通信任務;普通節點不當選簇頭節點。

由于高級節點在前面輪數中當選了簇頭，能量消耗比普通節點多。隨著輪數增大，網絡工作一段時間后，當輪數大于輪數閾值r0時，此時高級節點與普通節點的剩余能量差異縮小，即網絡中節點的能量異構性減弱時，對兩種節點設置不同的當選簇頭幾率。普通節點當選簇頭幾率pnrm為式（4），高級節點當選簇頭幾率padv為式（5）：

2.4 ?算法流程圖

改進后算法流程圖如圖1所示。

3 ?仿真結果分析

3.1 ?仿真環境

為了驗證算法的可用性和可靠性，本文采用MATLAB R2014a軟件進行仿真分析。在M×M m2的正方形區域內，隨機部署N個節點，其中，高級節點的比例為m，其能量為E0（1+α），其余為普通節點，其能量為E0，匯聚節點位于正方形區域上邊界中點處，當M=100 m時，匯聚節點坐標為（50，100）。當M=100 m時，各節點分布如圖2所示，其中，▲為匯聚節點，□為高級節點，○為普通節點。

仿真實驗中采用的網絡場景參數設置如表1所示。

3.2 ?仿真結果

改進后算法和LEACH算法的網絡生存時間對比如圖3所示。從網絡開始運行到第一個節點死亡的時間間隔，稱為網絡穩定周期，在此時間內，所有節點存活，網絡能穩定持續地監測環境信息和采集數據，網絡處于穩定的工作階段。從圖中可知，LEACH算法的穩定周期624輪，改進后算法的穩定周期為772輪，對比LEACH算法，延長了23.72%。從網絡開始運行到一半節點死亡的時間間隔內，出現部分節點死亡，但比例不高，網絡仍能工作。圖中LEACH算法一半節點死亡的輪數為732輪，改進后算法一半節點死亡的輪數為874輪，對比LEACH算法，延長了19.40%。改進后算法的穩定周期和一半節點死亡的輪數均比LEACH算法更優。

改進后算法和LEACH算法向匯聚節點發送數據量對比如圖4所示。LEACH算法的傳輸量為11 037 L，改進后算法的傳輸量為23 704 L，約是LEACH算法的2.15倍。改進后的算法優先選舉剩余能量較多的高級節點當選簇頭節點，在前面輪數中，網絡能量異構性較強，高級節點高出普通節點的能量較多，選舉的簇頭數量比LEACH算法較多，因此，改進后的算法向匯聚節點發送數據量較多。而LEACH算法不考慮節點能量異構性，把高級節點和普通節點視作一樣的節點，具有相同的當選簇頭幾率。隨著網絡工作時間推移，在輪數為732輪以后，由于LEACH算法中出現過半節點死亡，網絡剩余節點數量越來越少，LEACH算法向匯聚節點發送數據量明顯減少。

4 ?結 ?論

本文在異構無線傳感器網絡環境下，基于LEACH算法，提出了一種改進的分簇算法。該算法考慮高級節點和普通節點的能量不同，通過優先選舉高級節點當選簇頭，充分利用節點的能量異構性，提高節點能量利用率。仿真結果表明，改進后的算法均衡了網絡能量消耗，延長了網絡的穩定周期和一半節點死亡輪數，網絡性能更佳，算法可適用于能量異構網絡。

參考文獻：

[1] 馬颯颯，張磊，夏明飛，等.無線傳感器網絡概論 [M].北京：人民郵電出版社，2015.

[2] 楊柳.基于分簇結構的無線傳感器網絡節能路由協議研究 [D].重慶：重慶大學，2016.

[3] 李繼榮.異構無線傳感器網絡覆蓋問題研究 [D].濟南：山東大學，2010.

[4] 徐晶晶，張欣慧，許必宵，等.無線傳感器網絡分簇算法綜述 [J].計算機科學，2017，44（2）：31-37.

[5] 張春花，劉方愛，申志遠，等.一種新的異構無線傳感器網絡分簇算法 [J].傳感器與微系統，2013，32（6）：143-146.

[6] HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks [J]. IEEE Transactions on Wireless Communications，2002，1（4）：660-670.

[7] 徐世武.異構無線傳感網絡最優簇首選擇機制 [J].計算機系統應用，2016，25（1）：187-191.

[8] SMARAGDAKIS G，MATTA I，BESTAVROS A. SEP：a stable election protocol for clustered heterogeneous wireless sensor networks [C].In：Second International Workshop on Sensor and Actor Network Protocols and Applications，2004：223-233.

[9] 王衛星，黃虹，孫道宗，等.基于能量異構的WSN多鏈路算法 [J].華南理工大學學報（自然科學版），2015，43（9）：74-80.

[10] 胡中棟，伍華林.多級異構無線傳感器網絡能量優化分簇算法 [J].江西理工大學學報，2017，38（1）：73-78.

作者簡介：伍敏君（1986—），女，漢族，廣東中山人，講師，碩士，研究方向：無線傳感器網絡技術、計算機應用技術。