改進的網絡路由協議低功耗自適應分簇算法

劉 軍，李 巖，齊 華

（1.武警工程學院，陜西 西安 710086；2.西安工業大學電子信息工程學院，陜西 西安 710032）

0 引言

無線傳感器網絡（Wireless Sensor Network）［1］是數據采集、處理及通信功能于一體的分布式自組織網絡，具有分布式式處理帶來的高監測精度、高容錯性、大覆蓋區域、可遠程監控等眾多的優點，在軍事、環境監測、醫療、智能建筑及其他商業領域等方面有著廣泛的應用。

無線傳感器網絡中傳感器節點能量有限，不同于傳統的有限網絡。無線傳感器網絡的路由協議必須時刻關注降低能耗、延長網絡生命周期這一核心問題［2］。設計精良的網絡協議就可以降低能耗，延長網絡的生命周期。目前，路由協議的主流是層次路由協議，該協議具有代表性的路由算法是低功耗自適應分簇（LEACH）算法［3］。LEACH 算法中，簇首形成高一層的網絡，這樣簇內成員的功能就變相對簡單，大大減少了路由控制信息的數量。但該算法也存在著簇首分布不均勻、簇首與基站之間只能采用單跳路徑的問題。針對以上問題，以降低功耗，實現能量均衡、延長網絡壽命為目的，對LEACH算法進行改進。

1 LEACH算法的分析

LEACH 算法（Low Energy Adaptive Clustering Hierarchy）是 MIT的Chandrakasan等人為無線傳感器網絡設計的低功率自適應分簇路由算法。它的基本思想是以循環的方式隨機選擇簇首節點，將整個網絡的能量負載平均分配到每個傳感器節點中，從而達到提高網絡整體生存時間的目的。

1.1 LEACH算法的工作流程

該算法的建立主要包括三個階段：

1）簇首的建立階段

簇頭節點的選取是LEACH算法中的關鍵，具體的選擇方法是：各節點產生一個［0，1］之間的隨機數，若該數小于某一個閾值T（n），則該節點成為簇頭。T（n）［4］如公式：

式中，p是網絡中簇頭數與總節點數的百分比；r是當前的選舉輪數；G是最近1／p輪不是簇頭的節點集合。

被選為簇首的節點會利用CSMA MAC協議廣播ADV消息，宣布自己成為簇首。非簇首節點收到來自各簇首的消息，并根據接收信號的強度選擇強度最大的簇首發送加入請求JOIN－REQ，其包含了節點的ID和要求加入簇首的ID信息。

2）時隙表建立階段

當簇首確定并且簇域劃分工作完成，簇頭將根據成員節點的數目，產生TDMA時隙表［5］。成員節點通過接收簇首的廣播獲取該表，并在自己的時隙到達時才開啟發送裝置向簇首發送數據，其余時間處于休眠狀態以節省寶貴能量。

3）穩定階段

相對于簇的建立階段，這個階段是相對較長的一個階段，該階段主要是各節點完成數據傳輸的任務。一旦簇形成，TDMA時刻表確定，則數據傳輸開始。簇首節點在收到成員節點傳來的數據后對數據進行數據融合和壓縮，將壓縮處理后的信號傳輸給基站。

1.2 LEACH算法存在的問題

1）壽命不均：簇首的選舉策略是隨機的，可能造成簇首分布不均，簇成員個數也有較大差異，使得各簇首負載不均衡，造成個別簇首較早死亡。

2）距離受限：LEACH協議只適用于小規模的無線傳感器網絡。由于基站與簇首之間采用單跳路徑選擇模式，所以簇首與基站必須布置在通信可達的范圍內。

2 LEACH算法的改進

2.1 改進算法的設計思路

針對LEACH算法中存在簇首壽命不均、傳輸距離受限的問題，并結合無線傳感器網絡自身的特點，本文從以下幾個方面對LEACH算法進行改進。

1）改變簇首產生方式來均衡各各簇首壽命

簇首的產生主要從以下兩個方面加以改變：

①基于節點的剩余能量選擇簇首?？紤]到無線傳感器網絡的能耗問題，選取能量較多節點作為簇首。將節點的剩余能量作為選擇簇首的一個重要衡量標準，保證區域內剩余能量較多的節點被選為簇首。

②基于節點與簇首之間的距離選擇簇首?？紤]到簇首地理分布平均的問題，每個簇首發射信號，其他節點根據接收到的信號判斷離簇首的距離，離簇首距離小于設定值M的節點不再選為簇首。從而保證所有簇首之間距離不小于M。

2）改變簇首與基站之間的通信方式來增加傳輸距離

LEACH算法中，簇首與基站之間的數據發送過程采用單跳的方式。由于基站距離傳感區域很遠，所以簇首將數據發送給基站時所消耗的能量很多，基于這一點，在簇首向基站發送數據的時候采用多跳的方式，這樣可以使簇首節點能量的消耗相對減少。因此，本論文提出的改進算法將會把簇首組織起來，以多跳的方式向基站發送融合之后的數據。

2.2 改進算法的實現

與傳統的LEACH算法相比，改進后的算法在選擇簇首之前，傳感區域內的所有節點需要將自己的地理位置信息和節點能量發送給基站，基站收集到區域內各個節點的位置信息后，根據這些信息將傳感器網絡按面積平均劃分為k個區域（本論文中設定k＝3，如圖1所示，這就意味著需要將整個區域劃分為三部分）。

區域劃分完成以后，每個節點隨機產生一個0～1之間的隨機數，如果小于閾值T（n），則該節點當選為候補簇首，T（n）的計算與LEACH算法中相同，然后把選出的候補簇首按能量的大小遞減排列成一個隊列，從隊列中第一個節點開始，取消以節點為圓心，半徑為M的圓內的其它候補簇首成為簇首的資格，并將其從列隊中刪除。依次遍歷其他節點，重復上述操作，最后剩下的候補簇首成為最終簇首。

圖1 傳感區域的劃分Fig.1 The regional division

當選為簇首的節點會將自己的ID添加到該簇域的全局變量ch＿list＿中去，最終得到的ch＿list＿就是該簇域內所有簇首節點ID的列表。通過簇域的ch＿list＿即可以得到下游簇域內的所有節點的ID列表，所謂下游指的是指向BS方向的下一個簇域，有了該列表，就相當于得到了下一跳的候選列表，如圖2所示，簇首只需從這些候選節點中隨機選出一個節點作為自己的下一跳節點，這樣就將各個簇首的多跳路徑建立起來了。

簇首確定、簇域劃分完成后，各簇域將建立各自的時隙表，時隙表建立后，進入到穩定傳輸階段。

圖2 簇首多跳路徑示意圖Fig.2 Multi－ hop path

3 算法的仿真及分析

3.1 仿真平臺的構建

本文 采 用 NS2［6］對 LEACH 及 改 進 后 的LEACH算法進行了仿真。NS2（Network Simulator）是一種內核源代碼開放的，針對網絡研究的離散事件大型可視化仿真器。它能夠建立目前幾乎所有網絡對象的基本模型之間的互連，并且使復雜的網絡交通和拓撲結構得到高度切合實際的模擬和仿真。仿真環境設定如下：

1）傳感器節點和虛擬聚類區域具有全局唯一的ID標識；

2）網絡內所有傳感器節點均相同，具有相同的初始能量2J，且到BS均可達；

3）各個傳感器節點具備GPS功能，即節點能定位其位置。

3.2 仿真結果與分析

1）圖3對兩種算法在不同時段仍然存活的節點個數做出了比較。

圖3 網絡中存活節點數量的仿真Fig.3 Simulation of alive node number

從圖3可以得出以下結論：

①LEACH算法在365s的時候出現節點死亡，而改進后的算法在375s的時候開始有節點出現死亡。從節點開始死亡的時間上來說，改進后的算法相對于LEACH算法提高了2.73%。

②LEACH算法在500s左右的時候結束了網絡生命，而改進后的算法在580s左右的時候才結束網絡生命，從網絡存活時間比較來說，改進后的算法比LEACH算法延長了16%。

2）不同時段網絡內存活節點數目的比較很直觀地說明了兩種算法下網絡生命周期的不同，下面從能量消耗的角度來進一步對兩種算法進行比較。

圖4比較了兩種算法下在不同時段網絡消耗總能量的值，可以看出LEACH算法在500s結束網絡生命時的總能耗是450J左右，而改進后的算法在580s結束生命周期時總能耗是350J。更進一步印證了算法較LEACH算法延長了網絡生命周期。

圖4 網絡總能量消耗的仿真Fig.4 Simulation of energy consumption

3）兩種算法的性能比較

New－LEACH算法和LEACH算法相比，性能有所提高。從表1可以看出，如果以節點開始死亡的時間為標準，New－LEACH算法相比LEACH算法能有2.73%的提高；若以網絡生命周期為標準，則有16%的提高；如果以網絡總能耗為標準，相比LEACH算法，New－LEACH算法獲得了21%的性能提高。

表1 不同路由協議下網絡生命周期的比較Tab.1 The comparison of life－cycle under different network routing prorocols

4 結論

本文針對無線傳感器網絡，在理論分析的基礎上提出了一種改進的LEACH算法。該算法在選擇簇首方面，充分地考慮了網絡中節點的位置和剩余能量，進而使簇的大小更為合理；在簇首與基站之間的路徑選擇方面，采取了多跳傳輸的方式。通過NS2的仿真實驗表明：與傳統的LEACH算法相比較，網絡的能量消耗率降低了將近21%。因此，改進后的算法能更有效地降低與均衡網絡的能量消耗，從而較大幅度的延長了傳感器網絡的生命周期。

［1］孫利民，李建中，陳渝，等.無線傳感器網絡［M］.北京：清華大學出版社，2005.

［2］余勇昌，韋崗.無線傳感器網絡中基于PEGASIS協議的改進算法［J］.電子學報，2008，36（7）：1 309－1 313.YU Yongchang，WEI Gang.An improved pegasis algorithm in wireless sensor network［J］.Acta Electronica Sinica，2008，36（7）：1 309－1 313.

［3］Shah R C，Rabaey J.Energy Aware Routing for Low Energy Ad hoc Sensor Networks［C］／／Orlando：IEEE Wireless Communications and Networking Conferenee（WCNC），2002：350－355.

［4］陶東.基于無線傳感器網絡LEACH協議的仿真分析研究［J］.現代電子技術，2011：24－26.TAO Dong.Analysis and simulation of leach routing protocol in wireless sensor networks［J］.Modern Electronics Technique，2011（11）：24－26.

［5］王盛.基于NS2的無線傳感器網絡LEACH協議的改進仿真研究［D］.武漢：武漢理工大學畢業論文，2010.

［6］徐雷鳴.NS與網絡模擬［M］.北京：人民郵電出版，2003.