LEACH協議的簇首多跳與選擇優化

付云虹，李 尹

(1．國家超級計算長沙中心(湖南大學)，湖南 長沙 410082；2．中南大學 信息科學與工程學院，湖南 長沙 410083)

LEACH協議的簇首多跳與選擇優化

付云虹1，李 尹2?

(1．國家超級計算長沙中心(湖南大學)，湖南 長沙 410082；2．中南大學 信息科學與工程學院，湖南 長沙 410083)

針對WSN層次型路由協議中簇首單跳傳輸數據至匯聚節點、而部分簇首因傳輸距離過長導致能量過早耗盡從而影響整個網絡壽命問題，提出了基于剩余能量對簇首優化選擇和簇首至匯聚節點間多跳數據傳輸的改進算法.對首個節點死亡輪數和能量圖像方面進行了分析和仿真，結果表明該改進算法可使全網負載更加均衡，并進一步延長了網絡整體壽命.

無線傳感網絡；層次型拓撲；簇首選擇；多跳

無線傳感網絡(Wireless Sensor Networks，WSN)是大型的信息采集網絡，傳感器節點通常依靠電池供電，而電池能量有限，從而影響到整個無線網絡的生存壽命，因此基于WSN的各種路由算法都會盡量節省能量，延長網絡的整體壽命[1].路由協議的任務是將數據分組從源節點(傳感器，sensor)通過無線網絡轉發到目的節點(匯聚節點，sink)[2-3].

無線傳感網絡中的路由協議從拓撲分布層面來看可分為平面型路由協議和層次型路由協議.由于平面型路由協議需要維護一個很大的路由表，從而會占用較大的存儲空間與較多的計算資源，并不適用于規模巨大的無線傳感網絡，而層次型路由協議可以改善這一點.文章基于層次型路由中的LEACH協議[4]，致力于深入研究已有的針對LEACH協議的算法優化，以延長網絡壽命和節省能量為目的，對其進一步優化和改進.

層次型拓撲控制利用分簇機制，選擇一些節點作為簇頭節點，由簇頭節點生成處理和轉發數據的骨干網，其余非骨干網節點可以暫時關閉通信信道，進入休眠狀態以節省能量[5].層次型的拓撲協議有LEACH,HEED,GAF等.無線傳感網絡拓撲控制主要研究的問題是：在滿足網絡覆蓋度和連通度的前提下，通過功率控制和骨干網節點的選擇，剔除節點之間不必要的通信鏈路，生成優化的網絡結構[6].LEACH協議是最初使用的協議，它的成簇思想對以后的協議改進影響很大.但是LEACH也有一些缺點，例如網絡分簇不均勻、可擴展性差和容錯性差等，因此后續的研究者根據其缺點進行了多方面的改進，下面是部分改進算法：

HEED算法針對LEACH算法簇頭分布不均,以及簇的規模大小不均這一問題的改進[7].在此算法中，節點以不同的概率發送消息，剩余能量越大當選簇首的概率越大.非簇首節點使用簇內最小可達能量來衡量簇內節點的通訊成本并以此來選擇合適的簇頭,可以平衡簇內節點的個數[8].

基于節點的剩余能量選擇簇首.考慮到無線傳感網絡的能耗問題，選取剩余能量較多的節點作為簇首.將節點的剩余能量作為選擇簇首的一個重要衡量標準，以保證區域內剩余能量越多的節點，被選為簇首的概率越大.簇首與匯聚節點(Sink)或者說基站(Base Station, BS)之間的數據發送過程采用單跳的方式.由于匯聚節點距離數據采集區域距離不定，可能在區域內，也可能在區域外.即使是在區域內，根據成簇方式的不同，部分簇首離基站的距離也可能很遠，因此這部分簇首將數據發送給基站時所消耗的能量較多[5].基于這一點，在簇首向基站發送數據的時候可考慮采用多跳的方式，這樣可以使簇首節點能量的消耗相對減少.

另一種改進算法將原有的簇頭選舉分為兩種情況：全網簇頭選舉和簇內簇頭選舉.在改進的LEACH算法中設置了一個閥值Va.每個簇周期開始時，首先檢查簇頭能量，如果所有節點的簇頭能量中存在小于Va的簇頭，則進行全網簇頭選舉，否則進行簇內選舉[9].

本文在已有的LEACH改進協議基礎上基于剩余能量對簇首進行優化選擇和簇首至匯聚節點間多跳傳輸方面提出改進措施，并對第一個節點死亡輪數和能量圖像開展分析和仿真，預期改進措施有3點：

1)根據距離匯聚節點遠近對節點進行分類；

2)根據節點剩余能量不同進行簇首優化選擇；

3)簇首間數據多跳傳遞至匯聚節點.

1 簇首個數最優化分析

采集區域內簇頭最優個數的確定是對層次型路由算法進行改進的基礎.設在M×M的區域內分布著N個節點，根據節點初始能量大小分為高級節點和普通節點兩類，其中存在C個簇頭，而C個簇頭決定了在該區域內一共有C個簇，假定所有的節點均勻分布，因此每個簇內有N/C個節點，其中一個是簇首節點，其余節點有(N/C-1)個.下面對兩類節點的能量消耗進行分析，首先分析簇首節點.

簇首能量消耗分為3部分：

1)接收非簇首節點傳輸數據的能量；

2)對接收到的數據進行融合處理的能量；

3)將融合后數據傳輸給匯聚節點的能量.

用公式表示為：

Ech=kEelec(N/C-1)+kEdaN/C+

kEelec+kεempd4

(1)

或

Ech=kEelec(N/C-1)+kEdaN/C+

kEelec+kεefsd2

(2)

式中Ech為簇首能量消耗；Eelec為射頻接收或發射1bit數據所消耗的能量；Eda為數據融合的能量消耗；εemp為數據傳輸單位距離消耗能量(自由空間)；εefs為數據傳輸單位距離消耗能量(多徑衰減)；N為節點總數量；C為簇頭數量.

非簇首節點能量消耗分為接收周圍相關信息消耗能量和將數據信息傳輸給簇首節點消耗的能量.用公式表示為：

Enonch=kEelec+kεempd4

(3)

或

Enonch=kEelec+kεefsd2

(4)

式中Enonch代表非簇首節點能量消耗.

總的能量消耗Etotal為：

Etotal=CEch+(N-C)Enonch

(5)

下面對式(1),(2)進行說明.由于傳感區域很大，不同的節點傳輸數據到目標節點的距離有大有小，因而傳輸過程中衰減分為自由空間衰減和多徑衰減[10].自由空間是一種理想介質，它不會吸收能量，但是隨著傳播距離的增大，發射天線的輻射功率密度與距離的平方成反比，因此自由空間傳播損耗是一種擴散式的自然能量損耗.在非簇首節點傳輸信息給簇首節點時，一般距離比較近，可以用表示自由空間能量損耗的式(2)表示.多徑衰落是指在微波信號的傳播過程中，由于受地面或水面反射和大氣折射的影響，會產生多個經過不同路徑到達接收天線的信號，通過矢量疊加后合成時變信號.基于簡化模型的思想，可認為遠距離傳輸更容易發生多徑衰落的現象.相對而言簇首節點和匯聚節點的距離較遠，因此在后面計算中簇首節點的能量消耗用公式(1).以上是針對最優簇頭個數進行計算，而決定其是屬于自由空間衰減還是多徑衰減具有一個臨界距離，在仿真模擬時可更精確地進行判斷.根據上述描述得到總的能量消耗公式：

Etotal=CEch+(N-C)Enonch=

(6)

總能量消耗Etotal對簇首個數C求導，并且令導數等于零，得到：

(7)

通過上述分析計算可以得到使數據采集區域總能量消耗最小的簇首最優個數的大小.決定節點是否為簇首的算法描述如圖 1所示，其中R代表節點距離匯聚節點的距離，xm是傳感區域的邊長，其算法依據主要是考慮該節點離匯聚節點的距離以及是否是高級節點.

圖1 簇首選舉算法

Fig.1 Cluster head’s selection algorithm

2 簇首選擇概率與多跳數據傳輸

根據距離大小可對節點進行細化分類，如果傳感區域很大，使用單跳傳輸數據方式時，距離匯聚節點距離太大的簇首節點能量消耗將會非常快速.經典的LEACH算法采用的方式是每個節點不管距離匯聚節點的距離遠近，其當選簇首節點的概率大小相同.而如果距離匯聚節點近的節點當選簇首的概率大，距離匯聚節點遠的節點當選簇首的概率小，就會使節點數據盡量向靠近匯聚節點的方向傳播，而不是先向遠離匯聚節點的簇首傳播，簇首再向匯聚節點傳播.具體實現是以匯聚節點為圓心，以不同長度為半徑將數據采集區域劃分為多個區塊，每個區塊的節點當選簇首的概率不同.處于不同半徑區域內的節點當選簇首的概率可通過設定不同的概率值進行仿真，根據仿真結果進行比對，以確定優化值.數據融合[11]方面，經典LEACH算法是非簇首節點把數據傳輸給簇首節點，簇首節點接收到數據后進行信息融合，再將數據傳輸給匯聚節點.在這過程中，簇首節點如果距離匯聚節點很遠，那么單跳數據傳輸過程中的能量衰減會相對較大.簇首節點可以先比較自身與其他簇首節點和匯聚節點的距離哪個更近，如果是距離匯聚節點更近那么直接傳輸數據給匯聚節點；如果是距離另一個簇首節點更近則傳輸給該簇首節點，第二個接收到數據的簇首節點再將數據進行融合，進行比較，采用同樣的方式對數據進行處理，直到傳輸給最后的匯聚節點.

之前也有學者對簇首節點多跳算法開展研究，但是數據采集區域面積大小與多跳算法改進效率的關系并未提及.簇首間采用多跳數據傳輸的出發點，在于離匯聚節點距離較遠的簇首節點單跳傳輸數據給匯聚節點所耗費的能量太大，因此才考慮使用簇首間多跳.基于這一出發點，推測數據采集區域越大，其對整個網絡生存壽命的改善效果應該越好.同時，中繼簇首如果接收其他簇首的數據進行融合然后再傳輸也需要消耗能量，因此簇首多跳算法的改進效果與數據采集區域的大小是有密切關系的.

3 仿真結果與分析

使用Matlab工具開展仿真實驗.本文所述的改進思路主要是在簇的建立階段，因此考慮使用簡化模型，只考慮簇建立階段和數據傳輸階段即穩定階段的能量消耗，忽略節點數據具體內容和數據的融合方式.

將n個節點隨機散布在傳感區域內，sink節點分布在傳感區域的中心，仿真用到的其他基礎數據來自于文獻[12].由于針對LEACH算法進行了兩點改進，分析單獨改進每一點后的仿真結果，最后再將兩點綜合起來分析仿真結果.

首先考慮根據節點距離匯聚節點遠近選取不同的當選概率時的仿真結果，如表1所示.R是節點距離匯聚節點的距離，M為傳感區域邊長.在First-dead一列中代表網絡中第一個節點死亡的輪數，該數據越大代表網絡壽命越長，負載越均衡.如表中仿真結果所示，節點當選簇首概率選取數據⑥時，其第一個節點死亡輪數最長，性能最優，數據(①代表的是經典LEACH算法中簇首選擇概率.由仿真結果可以算出，采用該改進方法，第一個節點死亡的輪數比經典算法優化：

(960-939)/939×100% = 2.24%

表1 以不同概率當選為簇首對網絡壽命的影響

圖2是上述數據的能量圖像的對比，橫軸代表傳感網絡運行的輪數，縱軸代表傳感網絡剩余的總能量.

由于節點是隨機均勻分布，每次仿真時所得到的第一個節點死亡的輪數不盡相同，從圖像和相關數據分析，改進后的算法在有節點死亡后的優勢更加凸顯，其能量下降得更慢一點，表明全網絡的負載更加均衡一些.

下面分析使用簇首間多跳傳輸算法的仿真結果.

表2給出的是在數據采集區域大小取不同值時，對經典LEACH算法和改進簇首多跳傳輸算法(以LEACH-MH標示)第一個節點死亡輪數的比較，考慮到節點死亡數目達到一定比例后整個網絡已不具備正常收集數據的能力，因此該對比過程僅以首個節點死亡時間作為參考.

輪數

輪數

表2 LEACH與LEACH-MH算法首個節點死亡輪數對比

根據表2中數據，可計算出不同的區域大小LEACH-MH算法對LEACH算法在延長全網絡壽命的改善程度，直方圖如圖 3所示.

100 m×100 m：(965-939)/939=2.8%

200 m×200 m：(868-799)/799=8.6%

300 m×300 m：(315-221)/221=42.5%

由以上仿真結果可以看出，在其他條件相同的情況下，面積越大簇首多跳改進算法對全網生存周期的改善優勢越明顯，這與之前的推導結果是一致的.

將上文所述的改進點包括根據距離匯聚節點遠近對節點進行分類、根據節點剩余能量不同進行簇首優化選擇和簇首間信息多跳傳遞至基站綜合起來，仿真得到與經典LEACH算法在延長全網生命期的數據如表3所示，仿真時采集區域大小為300 m×300 m.壽命相對提升率為：

(427-221)/ 221=93.2%

邊長/(102 m)

表3 綜合改進算法與LEACH生命期的比較

4 小 結

本文通過對經典LEACH算法及其改進算法進行研究，在綜合節點與匯聚節點的距離、節點初始能量大小和傳感區域面積這三點的基礎上提出改進措施，延長第一個節點死亡時間即均衡網絡負載延長網絡壽命.通過Matlab對改進算法進行仿真后發現，改進程度的大小和傳感區域面積大小有密切關系：面積越大多跳改進方案的優勢越明顯.雖然節點是隨機分布的，簇頭為隨機選舉，每次仿真時第一個節點死亡輪數不盡相同，但是從仿真結果看，對網絡壽命還是有明顯的延長.當然這其中還存在一些其他的問題，例如在距離越大當選簇頭概率相對越小這部分改進措施適應性尚待加強，因為當區域面積改變或者節點數目改變時相應的概率大小也要隨之調整；一些論文也提出多跳算法所用到的數據融合即將多級數據融合后壓縮到原來的長度其實很難實現.下一步工作將會在以上不足之處再繼續開展深入研究，進一步改善無線網絡性能.

[1] OZEL Omur, TUTUNCUOGLU Kaya, YANG Jing,etal. Transmission with energy harvesting nodes in fading wireless channels: optimal policies[J]. IEEE Journal on Selected Areas in Communications, 2011,29(8):1732-1743.

[2] LIU A, ZHENG Z, ZHANG C,etal. Secure and energy-efficient disjoint multipath routing for WSNs[J]. Vehicular Technology, IEEE Transactions on, 2012, 61(7): 3255-3265.

[3] LONG H, QU Z H, FAN X,etal. Dynamic nearest neighborhood collaboration target tracking for WSN[J]. Energy Procedia, 2011, 11: 707-714.

[4] 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.

[5] RAZZAQUE M A, AHMED M H U, HONG C S,etal.QoS-aware distributed adaptive cooperative routing in wireless sensor networks[J]． Ad Hoc Netw,2014,19:28-42．

[6] LI Chang-le,WANG Li-ran, SUN Ting-ting,etal. Topology analysis of sireless sensor networks based on nodes’ spatial distribution[J]. IEEE Transactions on Wireless Communications, 2014,13(5): 2454-2467.

[7] YOUNIS O, FAHMY S. Distributed clustering in ad-hoc sensor networks: A hybrid, energy-efficient approach[C] // INFOCOM 2004, Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE, 2004,1-5.

[8] 金鑫. 無線傳感器網絡層次型拓撲控制算法[D]. 合肥: 中國科學技術大學計算機科學與技術系，2008.

JIN Xin. A research on hierarchical topology control algorithms and the related problems of wireless sensor networks[D]. Hefei:Department of Computer Science& Technology, University of Science and Technology of China, 2008.(In Chinese)

[9] 唐甲東. 無線傳感器網絡路由協議研究-LEACH路由協議的改進[D]. 無錫: 江南大學物聯網工程學院, 2013.

TANG Jia-dong. Research on routing protocol for wireless sensor networks-Improment of LEACH routing protocol[D]. Wuxi:College of Internet of Things Engineering, Jiangnan University, 2013. (In Chinese)

[10]LI Changle, WANG Liran, SUN Tingting ,etal. Topology analysis of wireless sensor networks based on nodes’ spatial distribution[J]. IEEE Transactions on Wireless Communications, 2014,13(5): 2454-2467.

[11]李嘉, 劉春華, 胡賽陽, 等. 基于交通數據融合技術的行程時間預測模型[J].湖南大學學報：自然科學版,2014,41(1):33-38.

LI Jia, LIU Chun-hua, HU Sai-yang,etal. A travel time prediction model based on traffic data fusion technology[J]. Journal of Hunan University: Natural Sciences, 2014,41(1):33-38. (In Chinese)

[12]SMARAGDAKIS Georgios, MATTA Ibrahim, BESTAVROS Azer. SEP: A stable election protocol for clustered heterogeneous wireless sensor networks[C]//Second International Workshop on Sensor and Actor Network Protocols and Applications (SANPA 2004).Boston MA,2004: 165-190.

Optimization of Cluster Head Multihop and Selection in LEACH

FU Yun-hong1, LI Yin2?

(1．National Supercomputing Center in Changsha, Hunan Univ, Changsha，Hunan 410082,China;2．School of Information Science and Engineering, Central South Univ, Changsha,Hunan 410083, China)

An improved algorithm in WSN hierarchical routing protocols was put forward, which considered the residual energy of cluster head selection and multi-hop data transmission from cluster heads to the sink node, to solve the problems of some cluster heads' premature depletion, which affect the whole life of the network, caused by part of the cluster heads over long distances with single hop data transmission to the sink node. Analyses and the simulations were conducted on the first node's death round number and the energy image.The results show that the improved algorithm can balance the network load better and extend the whole network life, compared with the traditional algorithms.

wireless sensor networks(WSN); hierarchical topology; cluster head selection; multi-hops

1674-2974(2015)02-0121-05

2014-08-05

國家科技支撐計劃資助項目(2012BAH09B02);湖南省自然科學基金資助項目(14JJ5009)

付云虹(1968-)，女,貴州遵義人,湖南大學高級工程師?通訊聯系人，E-mail:liyin2012@csu.edu.cn

TP391.9

A