一種基于LEACH的改進WSN路由算法*

陳曉娟，王 卓，吳 潔

(東北電力大學信息工程學院，吉林省吉林132012)

無線傳感器網絡(WSN)節點由于有限的硬件資源和電池能量，且在應用過程中不可能更換電池，因此節能問題一直是無線傳感器網絡研究的重點之一，能量的利用效率是WSN路由協議設計的重要性能指標。現階段WSN路由協議可大體分為平面路由協議和分簇路由協議[1]。平面路由協議在運作過程中由于需要維持較大的路由表，并不適合在大規模網絡中采用，分簇路由協議與其相比一定程度改進了這個問題。LEACH路由協議[2]是第一個提出的分簇路由協議，例如 PEGASIS，TEEN，HEED等[3]都是在LEACH協議的基礎上進行一定程度上的改進。LEACH算法通過循環隨機選舉簇首以均衡網絡整體能耗，但它也同時存在著如簇首分布不合理，能量損耗不均，單跳路由選擇等明顯缺陷[4]。目前關于LEACH協議的改進都是圍繞簇結構的形成機制、簇首的選舉和數據傳輸進行設計的，文獻[5]綜合考慮了節點到簇首的距離、簇首到基站的距離和簇首能量的通信代價而改進了簇結構的形成[5]。文獻[6]將蟻群算法應用于路由選擇并通過環狀模型控制的節點間距離與路徑信息素的相互作用來選擇最優路徑[6]。文獻[7]則對其簇首選擇中的能量分布與地理分布利用粒子群算法進行了優化[7]。

本文針對LEACH算法中簇首分布不合理而導致網絡能量損耗不均的問題，提出了一種基于粒子群算法(PSO)的LEACH-PSOC路由算法。算法的主要思想是首先利用粒子群算法良好的收斂性和全局優化能力將整個網絡區域的分割成多個子區域，然后考慮區域內節點剩余能量的因素進而選舉出簇首。實驗結果表明，該算法能夠平衡網絡負載和延長網絡生命周期。

1 粒子群(PSO)算法

粒子群算法(PSO)是一種進化算法，源于對鳥群捕食的行為研究。粒子群優化算法的基本思想是通過群體中個體之間的協作和信息共享來尋找最優解[8]。PSO的優勢在于簡單容易實現并且沒有許多參數的調節。目前已被廣泛應用于函數優化等各種應用領域。

PSO初始化為一群隨機粒子，然后通過疊代找到最優解[9]。在每一次疊代中，粒子通過跟蹤兩個“極值”來進行更新。粒子本身所找到的最優解叫做個體極值Pid，整個種群目前找到的最優解叫做全局極值Pgd。找到這兩個最優值后，粒子通過式(1)和式(2)進行更新自己的速度和位置。

式中，Vid為粒子 i的速度;Xid為粒子 i的位置;rand()是介于(0，1)之間的隨機數;c1和c2為學習因子，通常c1=c2=2，ω為指定的權重系數。

2 LEACH-PSOC算法

2．1 LEACH 協議分析

LEACH協議運行流程以輪為單位，分為簇結構形成和穩定工作兩個階段。簇結構形成階段，全部節點按簇劃分，每個簇隨機選舉簇首。選舉過程是:每個節點隨機生成一個值在「0，1」之間的數，若小于T(n)，則此節點被選舉為簇首。T(n)的計算公式如下:

式中，p是網絡中所需簇首數目與總節點數目的比值;r是當前的選舉輪數;G是在剩余1/p輪中非簇首的節點集。

簇首節點利用CSMA-MAC協議廣播ADV消息(ADV消息中包括了簇首消息和簇首ID等信息)[10]，宣布自己當選為簇首。非簇首節點收到來自各簇首的消息，并根據接收信號的強度選擇強度最大的簇首發送加入請求。

簇首會為每個成員節點分配一個相應的TDMA時隙表，使節點在不同時間段發送數據避免信息擁擠。

在穩定運行階段，簇首將簇內成員發送的數據進行融合處理，最后將處理后的數據發送至基站。圖1為LEACH算法進程圖。

圖1 LEACH路由協議進程圖

LEACH算法中，簇首節點的作用是收集簇內節點的采集信息并融合處理，同時還有簇間信息的轉發和路由選擇，因此簇首節點的確立十分重要。當網絡中節點能量損耗不均衡時，遠離簇首的節點與簇首通信時會消耗更多的能量，從而導致部分節點的能量更快的消耗導致死亡，死亡節點的出現會降低網絡平均生命周期進而影響整個網絡的工作效率。所以優化簇首的選舉流程是算法改進的關鍵。

2．2 基于粒子群改進的的分簇算法LEACH-PSOC

基于粒子群改進優化的分簇算法首先是利用粒子群方法將整個區域劃分成若干個相同規模的簇;第二步根據節點的能量信息優化選擇簇首，最終確定簇首節點，網絡分簇結構完成。

2．2．1 問題描述

在實際的網絡環境中，節點并不是平均分布在整個區域的，隨機簇首選舉算法的結果可能導致各個簇的規模相差很大，這就意味著節點密集區域的簇首要承擔更多的數據處理和轉發任務，比稀疏節點區域的簇首能量消耗要大得多，也就有可能因能量耗盡而過早的死亡。出于均衡負載的考慮，我們希望能將整個區域劃分成規模相等的若干個簇，每個簇內的節點數目相等。

2．2．2 算法詳解

該算法分為兩大步驟，首先是利用PSO算法進行區域劃分，將整個區域劃分成若干個相同規模的簇;第二步是在已劃分好的簇內根據節點的信息和能量選舉出最合適的節點作為簇首節點。

2．2．3 網絡分簇階段

假設整個網絡共有N個傳感器節點，計劃將網絡分割為M個簇，則每個簇結構中的含有[N/M]個節點。首先，利用粒子群算法來確定一條網絡區域分割線，將網絡分割成兩個節點數目相同的區域。分割線以如下形式表示:

式中，(x，y)為位于分割線上的點的橫縱坐標;θ為分割線與x軸的夾角。

定義fitness函數為如下形式:

其中ci(i=1，2)為區域i中的節點數目，fi由下式決定:

其中，Mi為區域i期望的簇首節點數目，即希望通過分割使得該區域保留多少個簇首節點。

分簇算法描述:

Step1:網絡中所有節點向基站廣播自己的狀態信息(包括位置信息和能量信息)，即ADV報文;

Step2:基站收到報文后，開始執行PSO算法對網絡進行分簇，定義Q個粒子;

Step3:對粒子的參數x，y，θ進行隨機賦值，由式(4)確定區域分割線，至此，整個區域被分割成Q×2個不同的子區域。由于節點的位置信息已知，可以確定各自節點對應的ci(i=1，2)，進而帶入式(5)。

Step4:確定Q個不同的 fitness值，與上次搜索得到的最小fitness進行比較并取最小值，與其對應的粒子可以作為全局極值Pgd;同理，比較單個粒子得到的fitness值取最小的作為個體極值Pid，然后通過下式更新 x，y，θ:

其中，Xxid，Xyid—粒子的位置;Xθid—分割線的傾角;vxid，vyid，vθid—粒子在 x，y，θ三個維度上的搜索速度，由下式確定:

其中，c1，c2為學習因子，通常 c1=c2=2;rand()為(0，1)之間的隨機數;w為權重因子。

Step5:粒子得到新的x，y，θ后，代入 式(4)轉入Step3的搜索過程，直至滿足fitness值為0或者達到最大搜索次數時退出。理想情況下，滿足fitness函數值近似為0，此時可以整個區域分割成兩個規模相等的子區域。

Step6:將區域首次分割之后，對兩個子區域繼續分割，直到M個簇被劃分完畢。

2．2．4 簇首確立階段

經過粒子群算法對網絡優化后，我們得到了一個分簇均勻的網絡。

簇首確立階段，為了均勻節點能耗，剩余能量越多的節點被選舉為簇首的概率應該越大。先將所有節點進行分類，首先設定一個合理的能量閾值η，剩余能量高于η的節點稱為高能節點，剩余能量低于η的稱為普通節點。可以計算出高能節點在所有節點中的比例為m。高能節點高于普通節點能量部分為α。如下式，Pnrm為普通節點成為簇首的概率，Padv為高能節點成為簇首的概率。

在式(3)中，我們用上式中的概率代替(3)式中的p來得到每輪選舉簇首的閾值。這樣，對于普通節點，我們得到

其中r為當前輪，G'為本周期的后1/pnrm輪沒有成為簇首的普通節點的集合，T(snrm)是用于普通節點的閾值。這保證了每個普通節點每個周期每)輪將成為簇首一次，并且每個周期每輪普通節點成為簇首的平均數目為n·(1－m)×pnrm。

同理，對于高能節點，我們得到:

其中‘G’是此周期內后1/padv輪沒有成為簇首的高能量節點的集合，并且T(sadv)是用與高能節點的閾值。

當各個簇的區域范圍和簇首的選舉后，即簇結構形成完畢。整個無線傳感器網絡進行數據采集，然后簇間通信開始，該過程與LEACH相同，不再贅述。

3 仿真分析

3．1 仿真環境

本文采用Matlab 7．1仿真軟件，假設無線傳感器網絡中100個節點組成，節點隨機分布在100 m×100 m的區域內，遠程基站位于坐標(x=50，y=175)。

本文采用文獻[5]的通信模型。設兩節點間距離為d，無線覆蓋半徑為 r，傳送lbit數據所消耗能量為:

節點接收lbit長度數據所消耗能量為:

節點的初始能量為0．8 J。式(15)和式(16)的通信模型中，Eelec=50 nJ/bit，r=25 m，εfs=10 pJ/bit·m－2，εmp=0．001 3 pJ/bit·m－4，簇首與節點總數的比值取5%，即M=5。PSO算法中的相關參數值分別為:c1=c2=2，最大迭代次數MAXITER=100，權重因子w初始值為0．9，隨著迭代次數的增加隨下式而變化

式中，iter為當前的迭代次數。

仿真參數的設置見表1。

表1 仿真參數表

本文將以網絡死亡節點數目和系統總剩余能量作為算法節能的評價指標。

3．2 死亡節點數目比較

圖2為改進算法LEACH-PSOC與原LEACH算法的死亡節點數目變化的仿真結果。虛線為改進算法LEACH-PSOC，實線為原算法LEACH。以橫坐標表示網絡工作的輪數，縱坐標表示每一輪結束后，網絡中死亡節點(即剩余能量為零)的個數。

圖2 死亡節點對比圖

由圖2所示，在原算法LEACH進行到1 000輪左右時，出現了第一個死亡節點，而改進算法LEACH-PSOC則在1 300輪左右出現了第一個死亡節點，首個節點死亡時間延遲了大約33%。而兩種算法進行到1 700輪次以后，改進算法中節點出現了大面積死亡，只是因為改進算法中的節點損耗相對均衡，死亡節點出現的時間段較集中，但是節點工作效率較高。而原算法LEACH的死亡節點出現時間較分散，尤其是關鍵節點的死亡直接會影響整個網絡的工作效率，剩余節點作用有限。由于LEACH協議的簇首選舉是隨機的，所以容易導致簇首節點位置過于集中或者處于邊緣區域，網絡拓撲不合理，數據傳輸損耗過大。由于LEACH-PSOC首先將網絡區域合理分割后形成的簇結構，減少簇結構覆蓋區的重疊，而且在簇首選擇時我們考慮了剩余能量，剩余能量不足的節點當選簇首的概率大大降低，各節點的能量損耗比較均衡。平衡的網絡負載和每輪小的節點能量損耗使得節點的生存時間變長且基本相同，這樣可以使基站在較長的時間都能收集到較多的位置數據，因此可以使基站的分析更加準確有效。

實驗證明本文提出的改進算法延長了首節點死亡時間，相比于LEACH，節點死亡時間更加集中，能夠均衡網絡節點的能量損耗，監控盲點出現時間短，網絡生命周期得到延長，傳感器節點更加經濟高效;數據采集總量明顯提高。

3．3 系統剩余能量比較

圖3表示改進算法LEACH-PSOC與原LEACH算法隨著輪次的進行，網絡總剩余能量的變化曲線。虛線為改進算法 LEACH-PSOC，實線為原算法LEACH。以橫坐標表示網絡工作的輪數，縱坐標表示每一輪結束后，網絡中的總剩余能量。

圖3 系統剩余能量對比圖

從圖3可知，隨著輪次的進行，兩種算法的網絡總剩余能量情況，當程序試行初始，兩種算法節點耗費的能量相差不多。隨著網絡實驗的進行，2種協議的總能量消耗都在增加，但改進后的協議增長的速度較慢，隨著論數的增加，這種優勢更加明顯，當輪次進行到500左右，LEACH-PSOC算法中簇首分布均勻的優勢開始漸漸體現出來，網絡的總剩余能量遠遠高于原算法LEACH。直至4 000輪左右，網絡能量消耗殆盡，整體時間上足足提高了14%。

3．4 死亡節點分布的仿真對比

圖4與圖5分別是LEACH路由協議與LEACH-PSOC路由協議在1 500輪時期的網絡節點分布示意圖，“+”表示為存活節點，點表示為死亡節點，圖4中死亡節點數目為81個，占總節點數的81%;圖5中死亡節點為63個，占總節點數 的63%，可以明顯看出，改進算法LEACH-PSOC的存活節點更多，整體網絡的運行效率更高，保障了整個系統的工作效率，而原算法LEACH在1 500輪左右的時候80%的節點已經死亡，網絡運行能效變低，已不能保障整個系統可以正常工作。

圖4 LEACH協議網絡節點分布

圖5 LEACH-PSOC協議網絡節點分布

3．5 節點數目增加后的仿真對比

為了進一步驗證算法的有效性，將節點總數增加到200個，其他參數值不變，仿真結果如圖6和圖7所示。

圖6 死亡節點對比圖

從圖6中可以看出，新算法的死亡節點達到50%時，Leach算法的死亡節點數已經接近80%，并且推遲了第一節點死亡的時間，仿真進行到2 000輪次以后，改進算法中節點出現了大面積死亡，因為改進算法中的節點損耗相對均衡;從圖7中可以得到，網絡能耗降低了約20%。由圖可知，隨著仿真輪數的增加，LEACH-PSOC算法的優勢更加明顯。

圖7 系統剩余能量對比圖

4 結論

本文以無線網絡能耗模型為基礎，針對LEACH算法中簇首分布不均的缺陷，提出了一種基于粒子群改進的LEACH-PSOC算法，網絡仿真顯示，算法不僅提高了網絡能量利用效率，平衡節點的能效負載，延長網絡的生命周期;同時提高了無線傳感器網絡的工作效率和基站接收的數據量，使網絡具有更好的穩健性和更高的通信效率。筆者今后的研究重點是多跳路由和穩定階段的算法設計上，進一步提高算法的性能。

[1]孫立民，李建中，陳渝．無線傳感器網絡[M]．清華大學出版社，2005:89－96．

[2]沈波，張世永，鐘亦平．無線傳感器網絡分簇路由協議[J]．軟件學報，2006，17(7):1588－1600．

[3]陳靜，沈鴻．一個高效節能的WSN路由協議[J]．傳感技術學報，2007，20(9):2089－2094．

[4]王國芳，李臘元．基于LEACH和PEGASIS的節能可靠路由協議研究[J]．計算機技術與發展，2009，19(11):115－118．

[5]李田，史浩山，楊俊剛．無線傳感器網絡LEACH協議成簇算法研究[J]．傳感技術學報，2010，23(8):1158－1162．

[6]胡彧，王靜．基于蟻群算法的LEACH協議研究[J]．傳感技術學報，2011，24(5):747－751．

[7]蘇炳均，李林．粒子群優化的無線傳感器網絡仿真研究[J]．計算機仿真，2010，27(9):150－153．

[8]紀震，廖惠連，吳青華．粒子群算法及應用[M]．北京:科學出版社，2009．

[9]鄒學玉，曹陽，劉徐迅．基于離散粒子群的WSN分簇路由算法[J]．武漢大學學報，2008，54(1):99－103．

[10]范興剛，侯佳斌．基于DPSO的智能WSN分簇路由算法[J]．傳感技術學報，2011，24(4):593－600．

[11]FANG M Q，WANG J，XU X H．A Preemptive Distributed Address Assignment Mechanism for Wireless Sensor Networks[C]．Dalian:Wireless Communications，Networking and Mobile Computing International Conference，2008:1－5．

[12]GIRI D，ROY U K．Address Borrowing in Wireless Personal Area Network[C]．Patiala:2009 IEEE International Advance Computing Conference，2009:181－186．

[13]Wairagu G．Richard，Extending Leach Routing Algorithm for Wireless Sensor Networks[D]，in Msc．Thesis，Makerere University，March，2009．