粒子群優(yōu)化算法實現(xiàn)的WSN路由協(xié)議的可靠性驗證

王曉慧

（太原工業(yè)學(xué)院電子工程系， 山西 太原 030008）

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

1 原始粒子群算法

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

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

2 PSO-LP協(xié)議的特點

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

2.1 粒子群算法的改進(jìn)

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

圖1 兩種簇結(jié)構(gòu)

2.2 簇頭節(jié)點的選擇及主、從簇頭的分配

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

2.3 數(shù)據(jù)傳輸階段

PSO-LP協(xié)議的數(shù)據(jù)傳輸分為簇內(nèi)數(shù)據(jù)傳輸和簇間數(shù)據(jù)傳輸2個過程。

1）簇內(nèi)數(shù)據(jù)傳輸。簇內(nèi)數(shù)據(jù)傳輸為同一個簇內(nèi)成員節(jié)點間的數(shù)據(jù)傳輸，與LEACH協(xié)議中傳感器節(jié)點進(jìn)行數(shù)據(jù)傳輸?shù)陌l(fā)送、接收、空閑和休眠的狀態(tài)類似，即節(jié)點在發(fā)送和接收信息的時間之外，可以處于休眠狀態(tài)，從而很好的節(jié)約單個節(jié)點的能量[4]。

2）簇間數(shù)據(jù)傳輸。簇間數(shù)據(jù)傳輸即簇頭節(jié)點將本簇成員融合的數(shù)據(jù)發(fā)送至基站的過程，設(shè)為單跳傳輸和多跳傳輸：當(dāng)主簇頭到基站的距離小于或等于d0（假設(shè)所有主簇頭到基站距離的平均值為d0）時，主簇頭將信息直接傳送給基站，形成了單跳的簇間傳輸；當(dāng)主簇頭到基站的距離大于d0時，主簇頭先將信息傳送給最近的從簇頭，從簇頭再通過粒子群算法搜索最優(yōu)路徑將信息傳送到基站，形成了多跳的簇間路由。通過簇內(nèi)和簇間數(shù)據(jù)傳輸?shù)姆止ず献鳎苊饽承┐仡^因工作任務(wù)大而過早死亡，避免網(wǎng)絡(luò)盲區(qū)的過早出現(xiàn)，從而提高了路由的健壯性，也很好地改善了LEACH協(xié)議中唯一的單跳數(shù)據(jù)傳輸方式帶來的缺陷。

3 對PSO-LP協(xié)議的可靠性驗證策略

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

1）生命周期。生命周期是評價無線傳感器網(wǎng)絡(luò)性能的一個重要指標(biāo)。不同的應(yīng)用環(huán)境，生命周期的定 義也不同，一般將網(wǎng)絡(luò)運行一段時間后監(jiān)測區(qū)域內(nèi)存活的節(jié)點數(shù)量來描述生命周期；本文中生命周期定義為從網(wǎng)絡(luò)開始運行到一半節(jié)點死亡所延續(xù)的時間[5]。

2）網(wǎng)絡(luò)剩余總能量。指網(wǎng)絡(luò)運行一定時間后所有傳感器節(jié)點剩余能量的總和。

3）簇頭節(jié)點分布。通過統(tǒng)計監(jiān)測區(qū)域內(nèi)簇頭總數(shù)目，分析簇的大小和簇頭分布的均勻性，從而降低通信協(xié)議的開銷，以適應(yīng)動態(tài)變化的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

因此，傳感器節(jié)點的自身因素、周圍變化的環(huán)境都會影響網(wǎng)絡(luò)的生命周期和剩余總能量，為延長網(wǎng)絡(luò)生命周期，在路由協(xié)議設(shè)計時首要考慮的還是如何降低節(jié)點的能量消耗，能量信息能夠比較直觀反映WSN路由協(xié)議的性能指標(biāo)。

4 仿真及仿真分析

4.1 仿真環(huán)境

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

4.2 仿真結(jié)果及分析

1）實驗一。在100 m×100 m的正方形區(qū)域內(nèi)隨機分布100個傳感器節(jié)點運行LEACH，LEACH-PSO，PSO-LP協(xié)議。種群規(guī)模Q=20個，rmax=3 500輪。

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

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

圖2 100個節(jié)點實驗結(jié)果

表1 生命周期比較 輪

2）實驗二。200 m×200 m的正方形網(wǎng)絡(luò)監(jiān)測區(qū)域內(nèi)200個傳感器節(jié)點運行LEACH，LEACH-PSO，PSO-LP協(xié)議，Q=40個，rmax=5 000輪。

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

圖3 200個節(jié)點實驗結(jié)果

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

4.3 簇頭數(shù)目分布統(tǒng)計

據(jù)統(tǒng)計，1個無線傳感器網(wǎng)絡(luò)中最優(yōu)簇頭節(jié)點數(shù)目應(yīng)為整個網(wǎng)絡(luò)節(jié)點數(shù)目的5%，本文通過比較PSOLP與LEACH協(xié)議中每輪的簇頭數(shù)目來分析最優(yōu)簇頭數(shù)目（由于PSO-LP協(xié)議采用雙簇頭，但主、從簇頭數(shù)目相同，因此只統(tǒng)計主簇頭數(shù)目）[6]。

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

圖4 LEACH簇頭總數(shù)統(tǒng)計

圖5 PSO-LP簇頭總數(shù)統(tǒng)計

5 結(jié)語

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

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

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

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

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

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

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