粒子群優化算法實現的WSN路由協議的可靠性驗證

王曉慧

（太原工業學院電子工程系， 山西 太原 030008）

無線傳感器網絡（WSN） 是由很多傳感器組成的能監測環境的一種新型信息獲取系統，比如監測環境溫度和濕度、土壤成分等。無線傳感器網絡已廣泛應用于智能家居、環境監測、醫療護理、軍事、城市交通等多個領域[1]。 但是，通常WSN傳感器節點體積微小，并且只能通過自帶的電池供電，對于大多環境比較復雜的情況，監測人員很難為傳感器節點更換電池，如果個別節點任務量大，能量耗盡，會使整個網絡失去意義；然而，傳感器節點的能量消耗主要體現在無線通信模塊，因此，設計一個好的WSN路由協議能降低傳感器節點的能耗，并且能均衡所有節點的能耗，延長網絡壽命，避免出現邊緣節點能量過早耗盡而影響整個網絡性能。

1 原始粒子群算法

粒子群算法(Particle Swarm Optimization，PSO)是一種算法簡單、收斂快、易實現的新興智能方法，源于鳥類捕食的群體行為研究：一群鳥搜尋同一塊食物，所有鳥僅知道自己與食物的距離，而不知道食物的具體位置，所以通過先找到距離食物最近的鳥再來找食物。由于大多分簇算法在選擇簇頭時或者隨機選擇或者只考慮到簇頭節點的狀態，從而影響到網絡的生命周期，基于此粒子群算法能綜合各指數找到最優的簇頭節點。在WSN中每個傳感器節點就是一個“粒子”，通過粒子群算法初始化后，通過疊代方式找到最優解。即粒子通過跟蹤兩個極值來更新自己：一個是粒子自身找到的最優解（個體極值Pid）；另一個是整個種群目前找到的最優解（全局極值Pgd），找到這2個最優解后，粒子根據公式（1）和公式（2）更新自己的速度和位置：

式 中 ：t為迭代次數；vid、 xid分 別 為 粒 子i的 速度和位置；r1， r2是 0和1之間的隨機數；c1和 c2是控制粒子移動速度的系數；w控制粒子歷史值對當前值的影響程度[2,3]。

2 PSO-LP協議的特點

PSO-LP協議是利用改進的粒子群算法為基礎選取簇頭，采用雙簇頭和單簇頭結合的工作方式，并且簇間路由協議實行單路與多路相結合設計的無線傳感器網絡路由協議算法，由此提高網絡節點的能量利用率，延長整個網絡的生命周期。

2.1 粒子群算法的改進

粒子群算法中的適應度函數（下頁公式（3））是評價最優解的綜合因子，因此，通過改進PSO的適應度函數來提高WSN路由協議選取的簇頭質量（最優位置、最高能量等因素），PSO-LP的適應度函數綜合考慮因素：f1表示候選簇頭節點當前的剩余能量（顯然，節點剩余能量越高，其被選為簇頭后，工作效率越高）；f2表示當選簇頭與簇內成員節點的平均距離（由于簇內節點間數據傳輸消耗的能量與節點間的距離成正比，故f2越小，整個網絡能耗也越小）；f3評價簇頭節點對網絡均衡性的貢獻，如圖1所示（選簇頭時在考慮f1和 f2的前提下，如果網絡中簇頭距離能量較低的節點更近一些，使網絡提高低能量節點的能量利用率，因此更加均衡了整個網絡能耗，避免網絡空洞的出現）；f4等于當選簇頭與基站（S）的最大歐式距離除以基站至網絡中心（N）的距離。由此，適應度函數（T）可以定義為公式（3）：

圖1 兩種簇結構

2.2 簇頭節點的選擇及主、從簇頭的分配

為了解決網絡中節點間剩余能量不平衡的問題，PSO-LP協議在同一個簇選取主、從2個簇頭，2個簇頭分工合作。網絡初期：計算粒子群算法的適應度函數值，選取主、從簇頭，主簇頭的主要工作是收集簇內成員節點的信息并融合后將其直接發送至基站或通過最近的從簇頭發送至基站；網絡中期：同一簇的2個簇頭互相維護彼此的信息，如果在實際應用中某個簇頭由于異常原因失效或者能量耗盡時，由同一簇的另一簇頭同時擔任主、從簇頭的功能，從而避免信息混亂和網絡盲區的出現，提高網絡的穩定性；網絡后期：當2個簇頭都失效后，再進行新一輪的簇頭重選，通過延長網絡簇頭重選的周期，從而延長網絡數據穩定傳輸的時間，提高網絡生命周期。

2.3 數據傳輸階段

PSO-LP協議的數據傳輸分為簇內數據傳輸和簇間數據傳輸2個過程。

1）簇內數據傳輸。簇內數據傳輸為同一個簇內成員節點間的數據傳輸，與LEACH協議中傳感器節點進行數據傳輸的發送、接收、空閑和休眠的狀態類似，即節點在發送和接收信息的時間之外，可以處于休眠狀態，從而很好的節約單個節點的能量[4]。

2）簇間數據傳輸。簇間數據傳輸即簇頭節點將本簇成員融合的數據發送至基站的過程，設為單跳傳輸和多跳傳輸：當主簇頭到基站的距離小于或等于d0（假設所有主簇頭到基站距離的平均值為d0）時，主簇頭將信息直接傳送給基站，形成了單跳的簇間傳輸；當主簇頭到基站的距離大于d0時，主簇頭先將信息傳送給最近的從簇頭，從簇頭再通過粒子群算法搜索最優路徑將信息傳送到基站，形成了多跳的簇間路由。通過簇內和簇間數據傳輸的分工合作，避免某些簇頭因工作任務大而過早死亡，避免網絡盲區的過早出現，從而提高了路由的健壯性，也很好地改善了LEACH協議中唯一的單跳數據傳輸方式帶來的缺陷。

3 對PSO-LP協議的可靠性驗證策略

無線傳感器網絡路由協議主要針對傳感器節點能量有限的問題提出的，以降低網絡節點的能耗來延長網絡運行時間的。針對PSO-LP協議的特點，主要從以下三方面來驗證協議的可靠性：

1）生命周期。生命周期是評價無線傳感器網絡性能的一個重要指標。不同的應用環境，生命周期的定 義也不同，一般將網絡運行一段時間后監測區域內存活的節點數量來描述生命周期；本文中生命周期定義為從網絡開始運行到一半節點死亡所延續的時間[5]。

2）網絡剩余總能量。指網絡運行一定時間后所有傳感器節點剩余能量的總和。

3）簇頭節點分布。通過統計監測區域內簇頭總數目，分析簇的大小和簇頭分布的均勻性，從而降低通信協議的開銷，以適應動態變化的網絡拓撲結構。

因此，傳感器節點的自身因素、周圍變化的環境都會影響網絡的生命周期和剩余總能量，為延長網絡生命周期，在路由協議設計時首要考慮的還是如何降低節點的能量消耗，能量信息能夠比較直觀反映WSN路由協議的性能指標。

4 仿真及仿真分析

4.1 仿真環境

通過MATLAB2008軟件對PSO-LP路由協議的性能進行了仿真驗證。將模擬環境設置為一個正方形，并設置2個不同大小的區域，即對區域面積和節點數量增大時，簇的數量也比較多而容易出現信息冗余和重疊的情況下，將2個實驗做對比分析，從而驗證PSOLP算法不受節點數目和監測區域面積大小的影響。2個實驗中相同的主要參數為：每個節點的初始能量均為0.5 J，c1= c2=2，w=0.9，rand值在運行過程中動態地隨機給出，評價因子取a1=0.25，a2=0.25，a3=0.3，a4=0.2。

4.2 仿真結果及分析

1）實驗一。在100 m×100 m的正方形區域內隨機分布100個傳感器節點運行LEACH，LEACH-PSO，PSO-LP協議。種群規模Q=20個，rmax=3 500輪。

如圖2-1、圖2-2分別是基站位于中心時100個節點運行3種協議后的網絡生命周期和剩余能量情況。結果表明，執行PSO-LP算法相比LEACH和LEACH-PSO，網絡的生命周期得到較大的延長。

如表1是由圖2-1分別對網絡中第一個節點、一半節點、80%節點死亡所需要的時間進行比較。可以看出，若以50%節點死亡輪數作為生命周期，PSO-LP比LEACH算法延長了近80%，比LEACH-PSO算法生命周期延長了47%。運行PSO-LP協議的網絡工作主要在一半節點死亡之前，從網絡一半節點死亡到80%節點死亡這段時間，PSO-LP運行時間最短，也說明PSOLP中網絡節點能耗更均衡。圖2-2的結果是執行PSOLP后，網絡的剩余能量總是大于LEACH和LEACHPSO協議。

圖2 100個節點實驗結果

表1 生命周期比較 輪

2）實驗二。200 m×200 m的正方形網絡監測區域內200個傳感器節點運行LEACH，LEACH-PSO，PSO-LP協議，Q=40個，rmax=5 000輪。

如下頁圖3-1、3-2分別是200個節點基站位于中心時3種協議的實驗結果。同樣的結果，圖3-1顯示了PSO-LP協議的生命周期比LEACH和LEACH-PSO得到延長，圖3-2顯示在任何周期PSO-LP協議剩余總能量都比LEACH和LEACH-PSO高。

圖3 200個節點實驗結果

由以上2個實驗可見：增加節點數目、擴大網絡區域面積并不影響PSO-LP的有效性，因為PSO-LP利用了粒子群算法智能化選取簇頭、合理分配簇結構的背景，有效地節約了時間和節點能耗，并能提高大區域內節點能耗的均衡性，很好地避免網絡空洞的出現。

4.3 簇頭數目分布統計

據統計，1個無線傳感器網絡中最優簇頭節點數目應為整個網絡節點數目的5%，本文通過比較PSOLP與LEACH協議中每輪的簇頭數目來分析最優簇頭數目（由于PSO-LP協議采用雙簇頭，但主、從簇頭數目相同，因此只統計主簇頭數目）[6]。

結果如圖4為LEACH協議中每輪的簇頭總數目，其中簇頭總數在4~6個之間的約占總輪數的51%，簇頭1~3個約占總輪數的32%，簇頭6~10個約占總輪數的17%。圖5是對PSO-LP協議的統計，每輪簇頭數目大多數在4~6個，其占總輪數的69%，而簇頭數目在1~3個的僅占總輪數的17%，簇頭數目在7~10個的占總輪數的14%，其中簇頭數目為1、2、9、10的輪數幾乎沒有，由此得出，PSO-LP協議通過粒子群算法選取的簇頭更符合WSN路由協議最優簇頭數目的要求（5%）。

圖4 LEACH簇頭總數統計

圖5 PSO-LP簇頭總數統計

5 結語

通過優化粒子群算法實現了WSN的優化分簇，又通過選擇主、從2個簇頭，并在數據傳輸階段分工合作，進一步做到能耗均衡，達到延長網絡生命周期的效果。最后通過MATLAB2008仿真實驗，設置兩個不同區域大小、不同節點數量的實驗，分別將PSO-LP協議的生命周期、網絡能耗和最優簇頭數目等性能方面與經典的LEACH和LEACH-PSO做了比較，結果充分表明了PSO-LP的優越性：說明PSO-LP不僅相對LEACH和LEACH-PSO提高了性能，而且也適合應用于大面積、大數量的無線傳感器網絡，如對100個節點的網絡，PSO-LP的生命周期比LEACH延長約80%，而200個節點的網絡，PSO-LP的生命周期比LEACH延長近150%。

[1] 王曉慧,胡 彧 .利用粒子群實現能耗均衡的網絡主從簇頭分簇路由協議[J].中國科技論文在線,2011(5):401.

[2] 肖劉軍,鄧平.一種基于位置和能量的 WSN 改進分簇協議[J].通信技術,2010,43(8):43-45.

[3] 侯志榮,呂振肅.基于MATLAB的粒子群優化算法及其應用[J].計算機仿真，2003,20(10):68-70.

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

[5] 蘇淼，錢海，王煦法.基于蟻群的無線傳感器網絡雙簇頭算法[J].計算機工程，2008,34(13):174-177.

[6] 周冬鑫,金文光,容志能.基于分層的無線傳感網絡多跳分簇路由算法[J].傳感技術學報,2011,24(1)：73-78.