基于能量優化的三維空間LEACH改進算法研究

于 雷，劉海隆

(電子科技大學資源與環境學院，四川成都 611731)

1 引言

近年來，隨著無線通信技術和物聯網技術發展的成熟，關于無線傳感器網絡(WirelessSensorNetwork，WSN)的研究更注重于解決實際應用問題[1]。WSN由大量傳感器節點和匯聚節點組成，用于監測特定區域內的環境參數[2]。由于WSN終端節點能量有限、分布不均等原因，可能導致某些節點能量消耗過快、過早死亡，縮短網絡的整體壽命[3]。因此，針對不同應用場景的網絡設計一種低能量損耗的路由算法成為當前WSN領域研究的熱點。

LEACH算法是一種最為常用的分簇式路由算法，適用于大規模、運行周期長的無線傳感器網絡[4]。但LEACH算法在每輪初始化階段沒有考慮節點能量，可能會加速某些網絡節點的死亡。另外LEACH算法默認WSN是同構平面網絡[5]，能量模型過于理想化，與實際應用場景間存在較大差異。因而出現了一些針對LEACH算法缺陷的改進算法。例如TEEN算法[6]通過設置閾值減少冗余信息，節約網絡節點能量。PEGASIS算法[7]將節點組成鏈式結構，每個節點只與鄰居節點通信，并選擇一個鏈首節點與sink節點通信，節約了遠距能耗，也減少了簇重構的代價。以上改進算法或沒有考慮節點剩余能量，或附帶較多的約束條件，不能很好地維持算法復雜度和算法有效性之間的平衡。

針對以上算法的不足，本文提出了一種LEACH-RE算法，該算法在簇頭選取階段考慮節點當前的相對剩余能量，并將異構網絡模型部署至立體空間中，綜合考慮電磁衰落建立能量模型，模擬真實環境中的WSN。

2 LEACH算法概述

LEACH(Low Energy Adaptive Clustering Hierarchy)算法是典型的分簇式路由協議，適用于低功耗需求下的WSN[8]。分簇式協議將網絡節點劃分至不同簇內，簇頭負責收集簇內節點的數據并匯聚到基站，因此簇頭的能耗高于其它節點。LEACH算法的基本思路就是輪換簇頭節點，使網絡的能量負載趨于均衡，避免少數節點的死亡導致網絡癱瘓。LEACH算法將網絡的整個生命周期分為多輪，每輪又分為初始化階段和穩定運行階段。初始化階段負責簇頭選擇、網絡分簇及簇內信息同步，建立樹型拓撲網絡。穩定運行階段負責數據的路由傳輸。LEACH算法流程圖如圖1所示。

2.1 初始化階段

LEACH協議在初始化階段，每個網絡節點會產生一個(0，1)內的隨機數，再與預設門限比較，如果隨機數小于門限值，則當選為簇頭。門限值定義如下式[9]：

(1)

其中p為當選簇頭節點概率，r為當前周期的輪數，rmod(1/p)為該輪當選過簇頭的節點數，G為該輪中未當選過簇頭的節點集合。該式在網絡節點中平等選舉簇頭，使能量消耗不會集中在某些節點。

簇頭當選后會向網絡中其它節點發送廣播信息，其它節點接收到該信號，并通過RSSI(Received Signal StrengthIndicator)判斷自身與發送節點的大致距離。節點通過比較不同的RSSI，選擇最大值加入該簇。節點請求簇頭為自己分配一個時隙。簇頭收到所有請求，并為每個節點分配獨立的時間片。

2.2 網絡穩定運行階段

WSN進入穩定運行階段后，簇頭會根據時間切片收集簇內各節點的數據并融合，將其匯聚到sink節點，完成數據傳輸。經過較長時間的穩定傳輸后，網絡進入下一輪初始化階段。

3 LEACH算法改進

由于LEACH協議的傳輸機制是基于節點當選簇頭次數的，算法不能兼容異構網絡；其次在網絡初始化階段也沒有考慮網絡節點的當前剩余能量。大大降低了普適性。

因此本文提出了LEACH-RE算法，主要針對兩個方面對LEACH算法進行改進，簇頭選舉閾值和原算法適用范圍。

3.1 三維空間傳感器節點布設

假設WSN由m個隨機部署在三維空間中的傳感器組成，網絡節點分布如圖2所示，對應的網絡節點集合為：

N={n1，n2，n3，…，nm}

(2)

其它條件假設如下：

1)匯聚節點位于立方體空間S的中央，傳感器節點在部署后位置不再改變。

2)傳感器節點之間、傳感器節點和匯聚節點之間可以數據傳輸。并且網絡節點能夠通過信號接受強度(RSSI)近似計算發送者信號直線傳輸距離。

3)發送節點會根據接收節點的距離自動調節功率，減少能量消耗冗余。

4)網絡節點在空閑時處于休眠狀態，即不考慮能量消耗。

3.2 異構網絡

LEACH算法的一個重要前提為分布均勻的同構網絡，即網絡節點初始能量是相同的；不同節點每次收發信號所消耗的能量也是相同的。滿足以上的假設條件，根據節點當選簇頭次數考慮簇頭選舉概率才是有效的，但是在真實的復雜環境下，很難滿足上述條件。首先WSN的特點是低成本和高可靠性，大規模網絡中不同節點在硬件和軟件上實現統一標準難度很大，并且會影響網絡可擴展性。其次WSN一般是自組織網絡，復雜環境下設備節點會因意外情況容易掉電、重新入網，或者因后續網絡規模的擴展需求而加入新的節點設備，如果每次設備入網都需要考慮網絡整體拓撲結構保證每個節點的分布均勻性，會造成大量人力成本浪費，也會破壞WSN的自組織性。所以選取異構網絡作為LEACH協議的使用對象是合理的，同時也拓寬了原算法的適用范圍。

本文將網絡節點分為一般節點和高級節點，不同節點的初始能量不同，并且當選簇頭的概率也不同。

3.3 基于相對剩余能量的簇頭選舉

LEACH算法選舉簇頭時只考慮當前節點當選簇頭的次數，無法很好地解決復雜環境下的WSN能耗問題。參選節點的當前剩余能量在一定程度上能夠反映節點未來的生存狀況。網絡節點剩余能量越多，則該節點的生存周期期望越大，有能力承擔較多信號收發帶來的能量消耗，因此更適合當選簇頭節點。在此基礎上，再考慮參選節點的初始能量，如果網絡節點的當前剩余能量與初始能量的比值越小，則說明此節點在歷史周期中消耗的能量比網絡節點平均能量消耗要多，為了減輕該節點的負載，改善生存狀況，應該減少它當選簇頭的概率。

綜上所述，本文的一般節點簇頭選舉概率公式和高級節點簇頭選舉概率用公式可以分別表示為

(3)

(4)

其中En為當前節點的剩余能量，E0表示一般網絡節點的初始能量，1+α表示高級網絡節點初始能量和一般網絡節點初始能量的倍數，因此E0(1+α)表示高級節點的初始能量。pn表示每輪選舉中一般節點當選簇頭的概率，pa表示每輪選舉中高級節點當選簇頭的概率，Gn為該輪中未當選過簇頭的一般網絡節點的集合，Ga為該輪中未當選過簇頭的高級網絡節點的集合。簇頭選舉階段結束，進行簇內信息同步。當整個網絡初始化完成后，節點便按照正常流程進入穩定運行階段。

無線通信能量消耗模型為文獻[10]中收發機通信模型，構成如圖3所示。模型包含發送信號能量消耗和接收信號能量消耗，其中發送信號消耗的能量又可分為發射電路損耗和功率放大損耗，公式如下式所示[11]：

(5)

(6)

其中，l表示網絡節點發送或接收的數據包長度(bit)，Eelec表示網絡節點發送或接收單位bit的數據所消耗的能量，d表示發送節點和接收節點之間的直線傳播距離，節點i和節點j之間的距離如下式

(7)

當傳輸距離小于閾值d0時，只考慮電磁波的直射，功率放大損耗采用自由空間損耗模型；當傳輸距離大于閾值d0時，還考慮電磁波的反射、折射和繞射，功率放大損耗采用多徑損耗模型。

接收信號消耗的能量為

ERX(l)=lEelec

(8)

因此無線傳感器網絡節點收發信號的能量模型如圖3所示。

數據融合過程極其復雜[11]，本文將其消耗的能量過程簡化為

EDA(l)=lEda

(9)

其中Eda為融合單位bit所消耗的能量。本文假設簇頭節點會根據事先設定的數據融合率將本簇簇內節點上傳的數據進行融合，去除部分數據冗余。

4 仿真及結果分析

通過MATLAB對LEACH-RE算法進行驗證。假設100個網絡節點(包含一般節點和高級節點)隨機分布在100m×100m×40m空間中，sink節點位于空間正中心，即(50m，50m，20m)，其它仿真參數初始化如下表所示：

表1 仿真參數

通過仿真運行，結果下圖所示。

從仿真結果中可以分析得出循環周期與網絡節點存活數量的關系以及循環周期與無線傳感器網絡剩余能量的關系。在圖4和圖5中，‘x’表示死亡節點，可見LEACH-RE算法節點存活情況優于LEACH算法。從圖6可知，在1000輪周期后，LEACH-RE算法中的節點生存狀況明顯優于LEACH算法中的節點生存狀況，這是因為LEACH-RE算法改善單個節點的生存狀況，從而均衡網絡節點的能量負載。從圖7可知WSN的能量變化，曲線斜率表示網絡能量消耗速度，可以看出LEACH-RE算法的整體網絡剩余能量高于LEACH算法中的整體網絡剩余能量，且網絡能量消耗速度慢于原算法，證明改進路由協議能夠有效均衡網絡能量，延長網絡生存周期。

5 結語

通過在三維空間的LEACH算法的基礎上結合網絡節點的異構性，引入相對剩余能量減少低能量節點當選簇頭的概率，從而實現算法有效改進，通過MATLAB平臺對WSN存活節點數量和整體網絡剩余能量兩項指標進行仿真驗證，得到如下結論：

1)設置100個網絡節點，網絡經過1500輪周期運行后，LEACH-RE算法存活28個節點，原算法只存活8個節點，改進算法較原算法提升250%；

2)LEACH-RE算法在1500輪周期左右耗盡能量，LEACH算法在1300輪周期耗盡能量，改進算法較原算法提升15%。結果證明改進算法能夠有效均衡網絡能量，延長網絡生存周期。