基于LEACH協議的簇頭輔助路由算法

張繼榮，王文斌，苗國防

（西安郵電大學 通信與信息工程學院，陜西 西安710121）

無線傳感器網絡節點的能量、計算能力、存儲容量非常有限，在大型傳感器網絡中，無線傳感器節點的數量眾多，布置密集，受電能制約，路由易于失效，設計滿足要求的無線傳感器網絡路由算法極具挑戰性［1］。

傳感器節點部署在物理環境中，需要一定的工作壽命，節能是無線傳感器網絡設計的重要考慮因素。基于分簇的無線傳感器網絡路由協議憑借良好的擴展性和更高的能量效率受到廣泛的關注［2］。分簇是指把整個傳感器網絡劃分為若干個簇，每個簇有一個簇頭，簇內非簇頭節點把數據發送給簇頭，然后由簇頭進行數據融合后轉發給基站［3］。

低能量自適應分簇分層協議（Low Energy A－daptive Clustering Hierarchy，LEACH）是經典的無線傳感器網絡分簇路由協議［4］，通過等概率地隨機循環選擇簇頭，將與基站通信的高能耗平均分配到網絡的所有節點中，從而延長網絡的壽命，但是簇頭的負載大于普通節點，擴展性差，不適合大規模網絡。混合高效節能分布式分簇（Hybrid Energy Efficient Distributed Clustering，HEED）算法［5］在簇頭選擇過程中考慮了能量因素，選用剩余能量大的作為簇頭，但該算法沒有考慮簇頭負載過重的問題。多簇頭的自適應成簇算法（Self－Adaptive Algorithm Based on Multi－Cluster Head，SABMH）［6］，在數據的采集過程中選出的多個簇頭節點輪流擔當簇頭，均衡簇頭負載，但是簇頭頻繁更換，帶來額外的控制開銷。能量有效的多副簇頭層次型路由協議（Energy Efficient Hierarchical Multiple Vice－cluster－head Algorithm，EHMVA）［7］，選舉多副簇頭分擔主簇頭能耗，均衡簇內能耗，降低簇頭的負載，但是主副簇頭功能交疊，造成能量浪費。

針對分簇路由算法一般存在的簇頭負載過重的問題，本文擬提出一種基于LEACH協議的簇頭輔助路由算法，通過控制信息與數據信息分離的辦法來平衡網絡的負載，延長網絡的壽命，改進算法的性能將通過仿真進行驗證。

1 問題描述和系統模型

無線傳感器網絡路由算法必須解決兩個問題，其一是尋找去往目的節點的最佳路徑，對于無線傳感器網絡，所有傳感器節點的目的節點都是基站，其二是轉發傳感數據分組。無線傳感器網絡不同于傳統無線網絡，大量的傳感器節點可以提供傳感數據的冗余，傳感器網絡路由可以通過數據融合取得良好的性能［8］。根據無線傳感器的特點，解決這兩個問題，一般都要設定網絡模型和能量模型。

1.1 網絡模型

（1）在觀測區域內，傳感器節點和基站在部署后均不發生位置移動。

（3）為了節約能量，傳感器節點可以根據接收者的距離遠近調整其發射功率10］。

（4）考慮節點的連通度，至少有一個節點可以與基站通信，所有節點都可以收到基站的信息。為了保證無線傳感器網絡覆蓋集是連通的，節點的無線通信半徑大于等于其2倍感知半徑。

1.2 能量模型

傳感器節點的能耗分為：感知能耗、通信能耗、數據處理能耗。其中傳感器在通信方面的能耗最大［1］。路由算法與通信能耗有著密切的關系，好的路由算法，可以選擇最優的路徑，降低通信能耗，從而延長網絡的壽命。

采用與文獻［4，11］相同的能耗模型，假設通信節點之間的距離為d，d0代表節點的覆蓋半徑。無線傳感器節點發送l（bit）的數據需要消耗的能量

接收l（bit）的數據需要消耗的能量

傳感器節點聚合能耗

其中Eelec代表無線收發電路處理單位數據所消耗能量，EDA代表單位數據融合能耗，εfs與εmp分別表示兩種能耗模型的功率放大系數。

2 簇頭輔助路由算法

2.1 算法基本思想

簇頭輔助路由算法是一種分布式、自組織、自適應的分簇多跳路由協議。簇頭輔助路由算法和LEACH算法類似，也是采用“輪”的方式運行。每輪分為簇建立階段和數據穩定傳輸階段。簇建立階段分為簇頭的選舉、簇的形成，數據穩定傳輸階段分為數據融合、數據發送。

不同的是在簇頭輔助路由算法中簇頭不再承擔傳感數據的融合以及轉發功能。簇頭節點（cluster head，CH）只實現對整個簇的控制以及簇間的協同，也就是只處理控制信息。簇頭根據節點的剩余能量以及位置等信息從本簇中選擇簇內聚合節點（Aggregation node，AN）、簇間轉發節點（Transmission node，TN），簇內聚合節點負責傳感數據的融合，簇間轉發節點是下一跳節點的候選集，負責傳感數據的轉發。

這樣簇頭輔助路由算法中傳感數據的傳輸路徑有很大的不同。在LEACH協議中，普通節點（GN）把感知的數據發送給簇頭，簇頭經過數據融合后轉發給基站（BS），而在簇頭輔助路由算法中普通節點把感知的數據發送給簇內聚合節點，簇內聚合節點進行數據融合后，發送給下一跳節點（從簇間轉發節點中選擇），經過幾次轉發后，傳感數據傳送到了基站。

2.2 功能節點的選擇

簇頭輔助路由算法采用減少簇頭功能的辦法平衡網絡的能耗，下面是不同功能節點的具體選擇。

（1）簇頭的選擇

簇頭輔助路由算法采用了控制信息與數據信息的傳送分離的思想，LEACH算法中簇頭在傳感數據方面的能耗被簇內聚合節點、簇間轉發節點分擔。簇頭的能量消耗大大減少，簇頭的選擇更加靈活，只要滿足一定的剩余能量要求，就可以被選為簇頭。為了滿足大規模無線傳感器網絡的需求，簇頭的選擇不能由基站決定。也就是簇頭的選擇應該是分布式的。基于LEACH協議簇頭的選擇方面的改進很多，在此不做探討，為了算法結果的比較，仍舊使用LEACH協議簇頭的選擇方法。

（2）簇內聚合節點

主要負責簇內節點數據的收集聚合。假設簇內聚合節點的坐標為（xi，yi），每一個簇內節點到簇內聚合節點的距離為dk，其小于無線傳感器節點覆蓋范圍，最優的簇頭聚合節點應該是簇內所有節點發送數據到簇內聚合節點的消耗的能量總和最小，即求

其中

也就是求

通過計算可得［12］

這說明在傳感器節點均勻分布的情況下，一個簇內，最優的簇內聚合節點的位置為該簇的幾何中心點，由于簇內聚合節點可以使用輪換的策略，簇頭需要選擇距離簇的幾何中心最近的節點作為簇內聚合節點。

（3）簇間轉發節點

簇間轉發節點負責把收到的數據轉發給本簇的下一跳節點或者是基站。假設簇間轉發節點的坐標是（xTN，yTN），簇間轉發節點與基站的距離dTN大于無線傳感器節點覆蓋范圍，簇間轉發節點可能需要把數據轉發給基站，為了簡單，最優的簇間轉發節點是本簇內發送數據到基站能量消耗ETN最少的節點。由于

其中

可見在可以與基站直接通信的情況下，簇間轉發節點為簇內離基站最近的節點，因此對于每個簇，簇頭選擇簇內給基站發送數據耗能最少的并且剩余能量較大的節點作為簇間轉發節點。

（4）簇的下一跳節點

簇的下一跳節點從簇間轉發節點中選出。簇頭選擇本簇的簇內聚合節點通過本簇周圍（包含本簇）的簇間轉發節點中到基站發送數據消耗能量最少的作為本簇的下一跳節點。如果是本簇的下一跳節點是本簇的簇間轉發節點，那么本簇轉發節點的下一跳就是基站。為了避免距離基站近的節點出現能量空洞問題，可以通過設置傳感數據跳數的最大值，如果傳感數據的跳數等于最大值，簇間轉發節點應該將其直接發送到基站。

無線傳感器節點部署在一些特殊環境下，節點可能失效。對于普通節點失效后，簇頭應以最少的代價回收該節點所占用的時隙。對于簇內聚合節點和下一跳節點的失效，簇頭重新選擇合適的節點代替失效的節點。對于簇頭節點的失效可以由簇內聚合節點代替或選擇。

在一輪周期內，簇頭可以根據簇的實際情況，簇內聚合節點以及簇間轉發節點的能量如果低于閾值，簇頭選擇新的簇內聚合節點以及簇間轉發節點，或者重新分簇。當簇頭的能量小于某個閾值或者簇頭在本輪的能量消耗大于設定閾值，以及簇內有大于設定閾值的節點死亡，應進行重新分簇。

2.3 算法能耗比較

LEACH算法每一簇的能耗Ecluster1等于簇頭發送能耗ECH與所有非簇頭節點發送能耗Enon－CH之和，即

簇頭輔助路由算法的能耗Ecluster2等于簇間聚合節點的能耗EAN、通過所有下一跳的能耗Enext、所有普通節點的能耗EGN之和，即

根據簇間聚合節點和下一跳節點的選擇原則有

其中ENext為在本簇的第一個下一跳耗費的能量，Enext為數據發送到基站經過的下一跳耗費的能量。可以得出

也就是簇頭輔助路由算法的能耗低于LEACH算法的能耗。

3 仿真實驗

由于分簇算法每一輪形成得到的簇各不相同，從理論上準確分析分簇的網絡性能幾乎是不可能的，通常的做法是用計算機模擬或仿真，獲得分簇路由算法在不同的網絡環境下的性能指標。在實際中又是很難測得大量的樣本，因此采用有限次的仿真來研究算法的性能。

3.1 仿真場景

傳感器節點隨機均勻分布在200m×200m的檢測區域內，基站的坐標為（100，100），傳感器節點數量設為100、1 000。節點數100隨機生成的拓撲圖如圖1所示。

圖1 節點數100的拓撲圖

3.2 仿真參數設置

［13］，對仿真過程中將要使用到的參數進行設置，如表1所示。

表1 仿真參數設置

3.3 仿真結果

（1）無線傳感器網絡的存活時間

定義為網絡從開始運行到所有的傳感器網絡節點全部死亡的時間。其中比較重要的指標：第一個節點死亡的時間、10%的節點死亡的時間、最后一個節點死亡的時間。圖2和圖3分別為場景基站的坐標為（100，100），傳感器節點數量設為100、1 000下死亡個數與時間的關系，表2和表3分別為兩種場景下網絡第一個節點死亡的時間、10%的節點死亡的時間、最后一個節點死亡的時間，從中可以看出簇頭輔助路由算法在節點數1 000場景下，第一個死亡時間小于LEACH算法，這是由于簇頭輔助路由算法是多跳的，靠近基站的節點承擔了較多的數據傳輸，因為明顯的延長了整體的壽命，少量節點死亡是可以接受的。上述結果驗證簇頭輔助路由算法比LEACH算法網絡存活時間明顯延長。

表2 節點數n＝100時網絡存活指標對比

表3 節點數n＝1 000時網絡存活指標對比

圖2 節點數100場景下網絡生命周期對比

圖3 節點數1 000場景下網絡生命周期對比

（2）數據接收總量

定義為基站接收到的簇間轉發節點發送的經過簇內聚合節點進行數據聚合過的數據總量。數據接收總量越多，說明傳感器網絡對環境的檢測越精確。圖4和圖5分別為場景基站的坐標為（100，100），傳感器節點數量設為100、1 000下數據接收與時間的關系。可以看出簇頭輔助路由算法與節點的數量有密切的關系，節點數量越大，簇頭輔助路由算法相對于LEACH有比較明顯的優勢。這是由于簇頭輔助路由算法比LEACH協議的生命周期長，簇頭輔助路由算法在LEACH協議的網絡已經死亡后，繼續發送的數據超過了LEACH網絡發送數據的總量。

圖4 節點數100場景下網絡數據接收對比

圖5 節點數1000場景下網絡數據接收對比

4 結語

針對LEACH算法的簇頭負載過重的問題，提出了簇頭輔助路由算法，讓簇內聚合節點承擔簇頭的數據融合功能，讓簇間轉發節點承擔簇頭的數據發送功能，實現了簇的控制信息與數據發送分離，新算法以增加節點的計算量的代價換來整個網絡靈活性的提高。仿真結果顯示，網絡的壽命有明顯的提高。每一種路由算法各有特點，沒有哪一種算法是絕對最優的，應根據具體情況選擇合適的路由算法。簇頭輔助路由算法適用于大規模的無線傳感器網絡。

參考文獻

［1］陳林星.無線傳感器網絡技術與應用［M］.北京：電子工業出版社，2009：11－17.

［2］Naeimi S，Ghafghazi H，Chow C O，et al.A survey on the taxonomy of cluster－based routing protocols for homogeneous wireless sensor networks［J］.Sensors，2012，12（6）：7350－409.

［3］鄭娟毅，石明衛.基于ZigBee技術的無線傳感器網絡樹型路由的研究［J］.西安郵電學院學報，2010，15（1）：23－26.

［4］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy－efficient communication protocol for wireless micro－sensor networks［C］／／Proceedings of 33rd Hawaii International Conference on System Sciences（HICSS）.Washington DC：IEEE computer Society，2000：3005－3014.

［5］Younis O，Fahmy S.HEED：a hybrid，energy－efficient，distributed clustering approach for ad hoc sensor networks［J］.IEEE Transactions on Mobile Computing，2004，3（4）：366－79.

［6］楊坤.無線傳感網絡中多簇頭算法研究與仿真［D］.成都：電子科技大學，2010：31－52.

［7］呂金鵬.無線傳感器網絡的路由協議研究［D］.杭州：杭州電子科技大學，2012：32－53.

［8］張德干，張曉丹，李光.無線傳感與路由技術［M］.北京：科學出版社，2013：8－41.

［9］鄔春學，肖麗.基于蟻群算法的低能耗LEACH協議分析［J］.上海理工大學學報，2010，32（1）：99－102.

［10］林力偉，許力，黃榕寧，等.能量均衡的無線傳感器網絡容錯分簇優化策略［J］.福建師范大學學報：自然科學版，2009，25（5）：41－44.

［11］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.

［12］牛偉偉，高鐵杠.LEACH－C協議中模擬退火算法的改進［J］.計算機工程與設計，2011，32（6）：1869－1872.

［13］鄧亞平，唐駿.基于控制的低能耗多跳分簇路由協議［J］.計算機應用，2013，33（1）：108－111.