無線傳感器網絡拓撲控制算法的改進

李 華，陳 超，盧 令

(1.解放軍第四五二醫院信息科，成都 610036;2.四川理工學院自動化與電子信息學院，四川 自貢 643000)

引 言

近年來，無線傳感器網絡［1］作為一種全新類型的智能網絡信息系統，在信息領域迅速發展。相比于其他短距離無線通信技術，無線傳感器網絡具有易部署、成本低、規模大、自組織等許多優點，使得無線傳感器網絡的研究與應用得到了越來越多的重視。但是無線傳感器網絡中，節點通常使用電池供電，而其應用環境又使得電池的更換非常困難。所以，想要充分利用節點有限的計算和存儲能力，就必須有一個好的拓撲控制機制來優化網絡的拓撲結構，以達到節能和延長網絡生命周期的目的。

根據目前國內外的研究成果，可將無線傳感器網絡的拓撲控制分為功率控制和層次控制兩種。功率控制中，要求節點必須具有較強的存儲和計算能力來維護路由信息，因而只適用于規模較小的無線傳感器網絡。而層次控制可有效解決這個問題，網絡結構具有較好的可擴展性，可用于大規模部署的傳感器網絡。LEACH算法(Low Energy Adaptive Clustering Hierarchy)［2］是最早被提出來的較成熟且具有典型性的層次控制算法，該算法通過選舉簇頭來構成骨干網［3］，但是簇頭的選擇具有隨機性，會導致簇頭的分布不均勻，不能有效均衡能耗和延長網絡生命周期，對于此，本文將在簇頭選舉和更新方面對LEACH算法進行改進。

1 經典的LEACH算法

LEACH算法通過等概率隨機選擇簇頭，算法的運行過程是周期性的，因此定義了“輪(round)”這個概念，每一次輪循環包括建簇和數據傳輸兩個階段［4］，每一次輪循環結束后要重新選舉簇頭節點，執行建簇和數據傳輸以保持網絡節點的能耗均衡。

1.1 建簇階段

LEACH算法中各節點輪流擔任簇頭，每一輪選舉簇頭時，各節點在0～1之間隨機產生一個數Ti，同時設定閾值Tn，若Ti＜Tn，則簇頭由節點i擔任［5］。對于已經擔任過簇頭的節點，設置Tn=0，于是該節點在以后各輪中都作為普通節點。隨著輪數增加，節點的閾值Tn將隨著已擔任過簇頭的節點數目的增大而增大，則未擔任過簇頭的節點被選為簇頭的概率也就會增大。如果只有一個節點未擔任過簇頭，其Tn=1，意味著該節點一定當選。閾值Tn由以下公式確定:

式中，p0是簇頭數占總節點數的百分比，r是當前輪數，rmod(1/p0)是目前為止節點集合中已當選過簇頭的節點個數，G是目前為止節點集合中沒有當選過簇頭的節點的集合。

選舉完簇頭后，簇頭節點便向全網廣播簇頭消息，消息包含簇頭節點ID和消息類型的頭部。網內其他節點接收到簇頭消息后，根據消息強弱來選擇要加入的簇。若節點i接收到來自某個簇頭節點消息的信號越強，說明節點i離該簇頭節點越近，通信代價也就越小。如果接收到的消息信號強度相當，則節點可以隨機選擇要加入的簇。

若節點i決定要加入簇j后，需通知簇頭j，即向簇頭j發送自身ID和簇頭j的ID。

當簇頭節點接收到每個節點的入簇請求消息后，會建立一個TDMA調度時間表并將其發送給每一個簇成員節點。當所有非簇頭節點都收到時間表后，簇的建立就完成了，隨后便是數據傳輸階段。

1.2 穩定的數據傳輸階段

該階段主要是簇內節點按TDMA調度時間表完成數據傳輸任務。該階段被劃分成為若干個時間長度相等的幀，每個幀又包含若干個時間長度相等的時隙。

所有非簇頭節點都只在自己所在時隙內發送數據，其余時間關閉自己的無線通信模塊以減少能耗。簇頭節點要隨時準備接收成員節點發來的數據，因此要時刻保持活躍狀態，簇頭節點收集所有簇內節點發來的信息后，對相似信號和噪音信號進行處理和融合，并發送給匯聚節點。網絡持續工作一個固定的時間段后，將會重新進行簇建立階段和穩定的數據傳輸階段［6］。

1.3 LEACH算法的缺點

LEACH算法通過構建骨干網的方式來進行數據多跳傳輸，網絡的性能得到了很大的提升，但是在某些方面算法還存在一定的局限性。

首先，LEACH算法是基于初始能量相同且均勻分布的網絡模型研究的。而實際情況很難達到這樣的理想狀態，節點的能量和地理位置都將會存在差異，因此LEACH算法無法保證簇頭的均勻分布，從而不能有效地提高網絡整體性能和生命周期，簇頭節點負載也不均衡。其次，LEACH算法中，簇頭是隨機選擇的，并未考慮到剩余能量和其他問題，而對于剩余能量不同的節點，成為簇頭的代價也不同。另外，LEACH算法中，簇頭節點承擔任務重，能耗相對較大，因此簇頭節點容易失效并造成簇頭頻繁更新，而全網的簇頭選舉會帶來較高的額外頭開銷，這樣的頭開銷將會降低節點的能量利用率。

2 基于組合加權的改進算法

2.1 改進算法(M－LEACH)的設計思想

借鑒Ad Hoc網絡中的按需加權分簇算法(AOW)的思想［7-8］，對無線傳感器網絡的LEACH算法進行改進。在LEACH分簇算法中，簇頭的合理選擇對網絡的拓撲結構至關重要，簇頭的選擇是否合理決定了整個無線傳感器網絡性能的好壞。傳統的LEACH算法通過隨機的方式選擇簇頭，M-LEACH算法主要對簇頭的選舉和簇的更新方式進行改進。

改進算法的主要設計思想是:在簇頭的選舉階段，把節點的剩余能量、節點度數、節點的移動性以及節點與其鄰居節點之間的平均距離作為簇頭選舉所考慮的因素;簇頭的更新只在簇內進行，并不在全網范圍內進行更新，局部調整簇頭可以減少全網選舉簇頭帶來的頭開銷;簇頭的更新使用按需更新簇頭策略，即當簇頭節點的剩余能量小于某個閾值時進行簇頭的重新選舉。

2.2 改進算法描述

在簇頭選舉初始階段，為每一個節點分配一個權值W，該權值衡量了節點適合充當簇頭的程度，權值W越小的節點越適合充當簇頭。節點i的權值W(i)由以下公式計算可得:

其中，E(i)表示節點i到目前為止已消耗掉的能量，D(i)表示節點i當前的節點度與網絡理想節點度差值的絕對值，M(i)是衡量節點i移動性的參數，P(i)表示節點i到所有鄰居節點的平均距離，a1、a2、a3、a4分別為四個參數的權重。算法的執行過程可描述如下:

(1)建簇階段

①首先，根據網絡具體情況確定簇頭概率p，所有節點通過周期性地交換“Hello”消息，可統計出鄰居節點數目以及與所有鄰居節點的距離。

②每個節點i計算自己已耗能量E(i)。假設所有節點擁有相同的初始能量，由于節點接收和發送數據所消耗能量遠比感知數據時所消耗能量大，所以各節點的已消耗能量由節點收發數據時消耗能量來計算。

③每個節點i計算自己的節點度Di與網絡理想節點度D0之差，即

④用每個節點i的平均移動速度代表節點的移動性M(i)。

⑤每個節點i統計其到自己所有鄰居節點的距離總和Pi(總)，并除以鄰居節點個數，得到節點i到所有鄰居節點之間的平均距離P(i)。

⑥對每個節點i計算它的組合權重W(i)，其中權重因子 a1、a2、a3、a4滿足a1+a2+a3+a4=1，當某個參數越重要，其權重因子的值越大。每個節點依據自己的權值W(i)大小設置一個門限時間，門限時間的大小和W(i)的大小成正比，權值越小的節點，為其設置越短的門限時間。

⑦門限時間到的節點自動升為簇頭，這意味著權值越小的節點就優先成為了簇頭，即節點綜合性能越好，就越容易成為簇頭。若存在節點權值相等的情況，即門限時間相同，則選擇ID號較小的那個節點作為簇頭。

⑧當選為簇頭的節點在全網范圍內廣播簇頭消息，若在各自的門限時間內，節點收到了簇頭廣播消息，則根據廣播消息的信號強弱選擇要加入的簇并向所選簇的簇頭發送入簇消息，同時取消門限時間。簇頭節點收到所有入簇消息后，建立一個TDMA調度時間表，并發送給簇內每個節點。當所有節點都收到TDMA時間表后，進入穩定的數據傳輸階段。

(2)穩定的數據傳輸階段

簇成員節點按照TDMA時間表將采集數據發送給簇頭節點，簇頭節點收集所有成員節點發來的信息，對其進行融合處理并轉發給匯聚節點。簇內節點在TDMA時間表分配給自己的時隙之外關閉其通信模塊。

(3)簇的更新

①當簇頭節點的能量小于某個閾值Em時，接收簇內節點最后一幀數據，簇成員節點會將自己當前的權值信息和ID號聯合最后一幀數據發送給簇頭節點。簇頭節點比較每個成員節點的權值，權值最小的節點將當選為下一輪的簇頭，簇頭節點將在簇內廣播下一輪簇頭的信息，并把自己設置為非簇頭節點。

②簇內節點收到新簇頭節點信息后，把自己的ID號與新簇頭的ID號進行對比，如果相等則將自己設置為簇頭。

值得注意的是，第一輪簇頭選舉時，由于所有節點有著相同的初始能量，所以計算權值時不考慮已消耗能量。

3 仿真分析

3.1 仿真環境參數設置

仿真區域為一矩形區域:500×100 m，隨機放置100個節點，基站坐標為(50 m，50 m)。節點的通信距離范圍為:1～100 m。其余參數設置如下:

(1)整個網絡是連通的，即不存在獨立部分或者是孤立的節點。

(2)所有節點隨機分布且每個節點都有一個唯一的ID號。

(3)部分節點具有移動性，即部分節點在一定時間以后會改變自身坐標。

(4)節點通過廣播“hello”消息來計算鄰節點數及其與鄰節點的距離。

(5)節點的天線采用全向天線且所有節點都能接收到來自鄰節點的消息。

(6)節點初始能量為 0.5 J，簇頭概率為 0.05，控制包長度為100字節，數據包長度為4000字節。節點能量等于0時，標記為死亡，并不再進行數據的傳輸。

(7)節點的權重因子a1、a2、a3、a4滿足a1+a2+a3+a4=1，且考慮到每個影響因素在簇頭選舉過程中的作用程度不同，分別取值為:0.5、0.2、0.2、0.1。同時，只有當簇頭的能量下降至充當簇頭時能量的百分之七十時，才重新選舉簇頭。

3.2 仿真結果分析

使用MATLAB對M-LEACH算法進行仿真，并與LEACH算法進行比較分析。

(1)生命周期。也就是網絡維持正常工作所持續的時間，本文中將其定義為網絡從開始工作到節點存活個數降至初始節點數的50%時所持續的時間。算法的生命周期仿真結果如圖1所示。

圖1 網絡生命周期

由圖1可知，隨著節點的最大通信距離的增大，改進算法與LEACH算法的網絡生命周期都在減小，并且，在整個過程中，改進算法的生命周期都優于原算法。其原因是:相比于LEACH算法，改進算法選出的簇頭節點的綜合性能更好，能始終讓剩余能量較多的、節點移動性較小的、節點度與理想節點度之差較小的、與鄰節點的平均距離較優的節點來擔任簇頭，使得能量的有效性得到了提高，節點的負載也更均勻，延長了節點存活的時間，因此，網絡生命周期也更長。

(2)節點平均剩余能量。即網絡正常工作中，所有節點的平均剩余能量。節點平均剩余能量仿真結果如圖2所示。

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

從圖2可以看出，改進算法的剩余能量要高于LEACH算法，并且隨著輪數的增加，剩余能量最終都趨于0，即節點死亡。這是因為，改進算法采用了新的簇頭更新機制，減少了簇頭的更新次數，從而降低了選舉簇頭帶來的頭開銷，節約了一定的能耗，同時也有助于延長網絡的生命周期。

(3)節點充當簇頭的公平性指數(HFI)。該性能指標用來衡量節點充當簇頭的公平性程度，也就是節點充當簇頭的時間相比于所有節點充當簇頭的平均時間的偏離程度。HFI由以下公式計算可得:

其中，ti為節點i充當簇頭的時間，為節點作為簇頭的平均時間，N為全體節點數，V為網絡中的節點集合。因此，HFI值越小，節點在充當簇頭方面就越公平。在最好的時候，ti=E(ti)，這時HFI=0。一般情況下，簇頭的能耗遠比普通節點大，HFI值越小，說明所有節點越能較均勻地分擔能耗，也就是所有節點可以較公平地充當簇頭，從而可以有效地延長網絡生存時間。HFI值越小表示網絡工作越長的時間才會出現節點的分區，因此網絡的整體性能可以得到更好的維護。節點充當簇頭的公平性指數的仿真結果如圖3所示。

圖3 節點充當簇頭的公平性指數比較

從圖3可以看出，兩算法的HFI值都隨節點的最大通信距離do的增大而增大，而改進算法的HFI值在整個區間內都比LEACH算法的HFI值要小，說明改進后的算法使得節點能夠更公平的充當簇頭。隨著節點的最大通信距離增大，造成了節點之間的沖突域，數據傳輸的碰撞率增大，能量損耗變大，節點充當簇頭的時間變短，以至于頻繁的分簇，簇頭公平性降低，所以HFI值呈上升趨勢。而本算法對簇頭選舉進行了改進，簇頭分布更為合理，能耗也更均勻地分配到所有節點上，因此，節點充當簇頭的公平性更好。

(4)網絡負載平衡因子(LBF)。網絡的負載表現為簇頭處理負載的能力，即簇頭能夠支持的簇的大小。分簇結構中，簇頭將承擔較多的任務，能耗較大，因此拓撲控制算法應使網絡的負載盡可能均勻地分配給選出的每個簇頭。某簇頭處理負載的能力可由該簇的大小近似衡量，因此，網絡負載平衡因子可由簇成員節點個數的方差的倒數來計算:

其中，nh為網絡中簇頭總數，xn為簇頭n所在簇的成員節點個數，u=(N-nh)/nh為網絡內所有簇的成員節點的平均個數，N為網絡中總節點數。若LBF越大，說明網絡的負載越能均勻地分配給每個簇頭，在負載平衡程度最好時，xn=u，這時LBF趨于無窮大［9］。網絡負載平衡因子仿真結果如圖4所示。

圖4 負載平衡因子比較

由圖4可以看出，在整個循環過程中，改進算法的負載平衡因子明顯高于LEACH算法。在循環開始時，兩算法的負載平衡因子都較大，隨著輪數的增加，都呈遞減趨勢，在輪數r=600后LBF均趨于0。改進算法的LBF較好的原因在于:算法在簇頭選舉時綜合考慮了節點的多種影響因素，使選出來的簇頭不管在節點度方面，還是在簇頭與其鄰居節點的平均距離方面，都優于LEACH算法，因此，簇頭分布更均勻，負載的分布也越平衡，從而避免了瓶頸節點的出現以及網絡擁塞的情況。

4 結束語

本文提出了一種基于組合加權的改進LEACH算法，并對其簇更新方式進行了改進。改進算法在生命周期、節點平均剩余能量、HFI、LBF上都優于LEACH算法。另外，本文中僅對分簇算法進行了改進，后續研究可對分簇算法與功率控制相結合的拓撲控制機制做一定的嘗試和研究。

［1］ Estrin D，Govindan R，Heidemann J S，et al.Next century challenges:scalable coordination in sensor networks［C］//Proc of the 5thInternational Conference on Mobile Computing and Networking(MobiCom)，Seattle，Washington，August 15-20，1999:263-270.

［2］ Heinzelman W R，Chandrakasan A，Balakrishnan H.An application-special protocol architecture for wireless microsensor networks［J］.IEEE Transactionson wireless communications，2002，1(4):660-670.

［3］ Gerla M，Tsai J T C.Multicluster，mobile，multimedia radio network［J］.Wireless Networks，1995，1(3):255-265.

［4］劉曉文，閆靜杰，苗 錦，等.礦井無線傳感器網絡LEACH協議的改進［J］.煤炭科學技術，2009，37(4):46-49.

［5］陳曉娟，王卓，吳浩.一種基于LEACH的改進WSN路由算法［J］.傳感技術學報，2013，26(1):116-121.

［6］肖劉軍，鄧 平.一種基于位置和能量的WSN改進分簇協議［J］.通信技術，2010，43(8):43-45.

［7］杜國勇，束永安.基于鏈接率的Ad hoc自適應按需加權分簇算法［J］.計算機技術與發展，2014，24(1):93-97.

［8］林要華，胡華平.基于軌道預測自適應Ad Hoc分簇算法［J］.計算機工程與科學，2012，32(2):27-30.

［9］鄭少仁，王海濤，趙志峰，等.Ad hoc網絡技術［M］.北京:人民郵電出版社，2005.