陳曉娟，王 卓，吳 潔

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

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

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

1 粒子群(PSO)算法

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

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

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

2 LEACH-PSOC算法

2．1 LEACH 協(xié)議分析

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

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

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

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

在穩(wěn)定運行階段，簇首將簇內成員發(fā)送的數(shù)據(jù)進行融合處理，最后將處理后的數(shù)據(jù)發(fā)送至基站。圖1為LEACH算法進程圖。

圖1 LEACH路由協(xié)議進程圖

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

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

基于粒子群改進優(yōu)化的分簇算法首先是利用粒子群方法將整個區(qū)域劃分成若干個相同規(guī)模的簇;第二步根據(jù)節(jié)點的能量信息優(yōu)化選擇簇首，最終確定簇首節(jié)點，網(wǎng)絡分簇結構完成。

2．2．1 問題描述

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

2．2．2 算法詳解

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

2．2．3 網(wǎng)絡分簇階段

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

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

定義fitness函數(shù)為如下形式:

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

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

分簇算法描述:

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

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

Step3:對粒子的參數(shù)x，y，θ進行隨機賦值，由式(4)確定區(qū)域分割線，至此，整個區(qū)域被分割成Q×2個不同的子區(qū)域。由于節(jié)點的位置信息已知，可以確定各自節(jié)點對應的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)之間的隨機數(shù);w為權重因子。

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

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

2．2．4 簇首確立階段

經過粒子群算法對網(wǎng)絡優(yōu)化后，我們得到了一個分簇均勻的網(wǎng)絡。

簇首確立階段，為了均勻節(jié)點能耗，剩余能量越多的節(jié)點被選舉為簇首的概率應該越大。先將所有節(jié)點進行分類，首先設定一個合理的能量閾值η，剩余能量高于η的節(jié)點稱為高能節(jié)點，剩余能量低于η的稱為普通節(jié)點?？梢杂嬎愠龈吣芄?jié)點在所有節(jié)點中的比例為m。高能節(jié)點高于普通節(jié)點能量部分為α。如下式，Pnrm為普通節(jié)點成為簇首的概率，Padv為高能節(jié)點成為簇首的概率。

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

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

同理，對于高能節(jié)點，我們得到:

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

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

3 仿真分析

3．1 仿真環(huán)境

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

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

節(jié)點接收lbit長度數(shù)據(jù)所消耗能量為:

節(jié)點的初始能量為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，簇首與節(jié)點總數(shù)的比值取5%，即M=5。PSO算法中的相關參數(shù)值分別為:c1=c2=2，最大迭代次數(shù)MAXITER=100，權重因子w初始值為0．9，隨著迭代次數(shù)的增加隨下式而變化

式中，iter為當前的迭代次數(shù)。

仿真參數(shù)的設置見表1。

表1 仿真參數(shù)表

本文將以網(wǎng)絡死亡節(jié)點數(shù)目和系統(tǒng)總剩余能量作為算法節(jié)能的評價指標。

3．2 死亡節(jié)點數(shù)目比較

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

圖2 死亡節(jié)點對比圖

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

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

3．3 系統(tǒng)剩余能量比較

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

圖3 系統(tǒng)剩余能量對比圖

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

3．4 死亡節(jié)點分布的仿真對比

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

圖4 LEACH協(xié)議網(wǎng)絡節(jié)點分布

圖5 LEACH-PSOC協(xié)議網(wǎng)絡節(jié)點分布

3．5 節(jié)點數(shù)目增加后的仿真對比

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

圖6 死亡節(jié)點對比圖

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

圖7 系統(tǒng)剩余能量對比圖

4 結論

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

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

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

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

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

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

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

[7]蘇炳均，李林．粒子群優(yōu)化的無線傳感器網(wǎng)絡仿真研究[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．