基于pso算法的無線傳感器網(wǎng)絡(luò)分簇路由優(yōu)化研究

1基于粒子群算法的分簇路由協(xié)議無線傳感器網(wǎng)絡(luò)（wsd）由大量集中在監(jiān)測區(qū)域的小型廉價低頻傳感器節(jié)點(diǎn)組成，這些節(jié)點(diǎn)通過無線通信形成了一個跳躍的無線網(wǎng)絡(luò)系統(tǒng)。wsd具有監(jiān)測精度高、容錯性高、覆蓋面積大等優(yōu)點(diǎn)。廣泛應(yīng)用于軍事、環(huán)境控制、工業(yè)控制和城市交通領(lǐng)域。特別是在不太適合環(huán)境和員工無法到達(dá)的遠(yuǎn)程監(jiān)控場所。與傳統(tǒng)的無線自組織(Ad-hoc)網(wǎng)絡(luò)不同,WSN節(jié)點(diǎn)通常是帶有有限的、不可更換的電源,其自身的計(jì)算、通信、存儲能力也非常有限,因此,WSN路由協(xié)議必須以節(jié)約能源和提高網(wǎng)絡(luò)生存時間為主要目標(biāo).針對大規(guī)模WSN遠(yuǎn)程監(jiān)控系統(tǒng),基于分簇的路由算法相對平面路由算法具有很好的適應(yīng)性和節(jié)能性.但目前大多數(shù)路由算法在成簇過程中僅僅根據(jù)候選節(jié)點(diǎn)的狀態(tài)信息選擇簇首,由于忽略了周圍鄰居節(jié)點(diǎn)的狀態(tài)信息,導(dǎo)致簇內(nèi)節(jié)點(diǎn)易出現(xiàn)盲節(jié)點(diǎn)現(xiàn)象,從而降低網(wǎng)絡(luò)的生存時間.本文提出基于粒子群算法(PSO)的分簇路由協(xié)議,在充分考慮了簇內(nèi)鄰居節(jié)點(diǎn)的能量和距離分布信息的前提下優(yōu)化簇首的選擇,該算法能夠較好地避免盲節(jié)點(diǎn)現(xiàn)象的過早發(fā)生并有效降低系統(tǒng)能量的損耗.2簇首選擇機(jī)制在大規(guī)模的傳感器網(wǎng)絡(luò)環(huán)境中,為了提高網(wǎng)絡(luò)的可擴(kuò)展性,延長網(wǎng)絡(luò)的生命周期,通常采用基于分簇機(jī)制的路由協(xié)議.分簇路由協(xié)議中,網(wǎng)絡(luò)通常被劃分為簇,每個簇由一個簇首和多個簇成員組成,這些簇首形成高一級的網(wǎng)絡(luò),在高一級網(wǎng)絡(luò)中,還可以分簇,再次形成更高一級的網(wǎng)絡(luò),直至最高級,如圖1所示.分簇路由算法中,簇首節(jié)點(diǎn)不僅負(fù)責(zé)所管轄簇內(nèi)信息的收集和融合處理,還負(fù)責(zé)簇間數(shù)據(jù)的轉(zhuǎn)發(fā),因此簇首的確定十分重要.目前典型的分簇路由算法,如LEACH,TEEN,PEGASIS,HEED等都從節(jié)能的角度側(cè)重解決了不同的問題,但上述算法在選擇簇首時僅僅根據(jù)候選節(jié)點(diǎn)的狀態(tài)信息確定是否為簇首,并沒有綜合考慮周邊鄰居節(jié)點(diǎn)的狀態(tài).當(dāng)鄰居節(jié)點(diǎn)間呈現(xiàn)能量不均衡的情況時,遠(yuǎn)離簇首的鄰居節(jié)點(diǎn)與簇首通信時會消耗更多的能量,若此時該節(jié)點(diǎn)的剩余能量有限,那么這種情況下該節(jié)點(diǎn)很快便耗盡現(xiàn)存能量成為盲節(jié)點(diǎn),盲節(jié)點(diǎn)的頻繁出現(xiàn)會降低網(wǎng)絡(luò)平均生命周期并導(dǎo)致路由協(xié)議的低效,圖1中簇1.2說明了這種情況.在簇1.2中,設(shè)簇內(nèi)節(jié)點(diǎn)A至簇首節(jié)點(diǎn)的距離為R1,能量為EA,節(jié)點(diǎn)B至簇首節(jié)點(diǎn)的距離為R2,能量為EB,且有EB?EA,R1>R2.由于通信所耗能量ET同到達(dá)目標(biāo)的距離平方成正比,顯然有EB-ETB?EA-ETA,因此可以看到簇內(nèi)節(jié)點(diǎn)的能量損耗不均衡,A節(jié)點(diǎn)會有較高的概率提前成為盲節(jié)點(diǎn).若分簇算法在選擇簇首節(jié)點(diǎn)時能夠充分考慮其鄰居節(jié)點(diǎn)的能量及距離分布情況,例如將簇首節(jié)點(diǎn)更靠近節(jié)點(diǎn)A,則能有效地降低盲節(jié)點(diǎn)的出現(xiàn)概率并進(jìn)一步提高網(wǎng)絡(luò)的生命周期.為了解決上述問題,需要優(yōu)化簇首的選擇機(jī)制.在優(yōu)化問題中,主要解決兩個問題:一是尋找全局最值解;二是尋找全局最值解時,要有較高的收斂速度.PSO是一種新興的智能優(yōu)化方法,具有收斂速度快、算法簡單、易于實(shí)現(xiàn)等優(yōu)點(diǎn),在求解單目標(biāo)優(yōu)化問題上已證明是一種有效的方法,而且也成功地應(yīng)用于許多實(shí)際的工程領(lǐng)域中.本文以簇內(nèi)節(jié)點(diǎn)能量損耗均衡化為出發(fā)點(diǎn),提出一種基于PSO算法的分簇路由協(xié)議,通過優(yōu)化簇首的選擇來避免某些節(jié)點(diǎn)的過快能量損耗,從而降低盲節(jié)點(diǎn)的出現(xiàn)概率.3標(biāo)準(zhǔn)pso算法PSO是一種進(jìn)化算法,由Eberhart等發(fā)明.算法源于對鳥群捕食行為的研究:一群鳥在隨機(jī)搜索食物,在特定區(qū)域里只有一塊食物,所有的鳥都不知道食物在那里,但是他們知道當(dāng)前的位置離食物還有多遠(yuǎn).那么找到食物的最優(yōu)策略是什么呢,最簡單有效的方法就是搜尋目前離食物最近的鳥的周圍區(qū)域,PSO從這種模型中得到啟示并用于解決優(yōu)化問題.在PSO中,每個優(yōu)化問題的解都是搜索空間中的一只鳥,稱為“粒子”,所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適應(yīng)值,每個粒子還有一個速度決定他們飛翔的方向和距離.然后粒子們追隨當(dāng)前的最優(yōu)粒子在解空間中搜索.PSO是一種基于疊代的優(yōu)化算法.系統(tǒng)初始化為一組隨機(jī)解,然后通過疊代找到最優(yōu)解.在搜索過程中,PSO結(jié)合本地及全局信息,不但根據(jù)自身的歷史信息而且綜合利用群體中鄰居粒子的相關(guān)信息來調(diào)整當(dāng)前位置,從而通過迭代搜索求得優(yōu)化解.在每次疊代過程中,粒子通過跟蹤兩個“極值”來更新自己:第一個是粒子本身所找到的最優(yōu)解,這個解叫做個體極值;另一個是整個種群目前找到的最優(yōu)解,這個極值是全局極值.另外也可以不用整個種群而只是用其中一部分作為粒子的鄰居,那么在所有鄰居中的極值就是局部極值.在找到這兩個最優(yōu)值時,粒子根據(jù)如下的公式來更新其速度和新位置:Vid=WVid+c1rand()(Ρid-Xid)+c2Rand()(Ρgd-Xid),(1)Xid=Xid+Vid.(2)Vid=WVid+c1rand()(Pid?Xid)+c2Rand()(Pgd?Xid),(1)Xid=Xid+Vid.(2)其中:Vid為粒子i的速度;Xid為粒子i的位置;Pid為粒子i在前一個位置時的個體位置極值;Pgd為群體的全局位置極值;rand()和Rand()是值域?yàn)榈碾S機(jī)函數(shù);c1和c2為一個正的常數(shù)值,稱為加速系數(shù),用于控制粒子的移動速度;W為指定的權(quán)重系數(shù),用于控制粒子的歷史值影響當(dāng)前值的程度,較大的權(quán)重系數(shù)可指導(dǎo)群體加大向新的區(qū)域進(jìn)行搜索的力度,而較小的權(quán)重系數(shù)可指導(dǎo)群體在當(dāng)前區(qū)域進(jìn)行細(xì)微的搜索.4優(yōu)化網(wǎng)絡(luò)高效基于PSO優(yōu)化的分簇路由算法首先需要對網(wǎng)絡(luò)進(jìn)行簇的初步劃分,然后利用PSO算法綜合鄰居節(jié)點(diǎn)的狀態(tài)信息優(yōu)化選擇簇首,最后將確定的簇首信息發(fā)布到整個簇內(nèi).(1)無區(qū)分區(qū)分質(zhì)間引領(lǐng)墻的微織構(gòu)成此階段可采用各種分簇算法(如LEACH算法)對無線傳感器網(wǎng)絡(luò)進(jìn)行簇的初步劃分,經(jīng)過該階段簇首及簇基本確定,但形成的簇存在易于出現(xiàn)盲節(jié)點(diǎn)的問題.此階段形成的各簇的簇首稱為輔助簇首.(2)輔助簇首內(nèi)存儲能量信息簇內(nèi)各鄰居節(jié)點(diǎn)將自身節(jié)點(diǎn)的位置、能量狀態(tài)信息傳遞給輔助簇首.此時在輔助簇首內(nèi)存儲了鄰居節(jié)點(diǎn)的位置信息P{p1,p2,…,pn}及能量信息E{e1,e2,…,en},其中n為簇內(nèi)的節(jié)點(diǎn)數(shù)量,pi為第i個節(jié)點(diǎn)的位置值,ei為第i個節(jié)點(diǎn)的能量值.(3)節(jié)點(diǎn)位置調(diào)整該階段為優(yōu)化算法的核心,為了使PSO算法適合本問題域必需改造上述PSO算法中提及的公式(1)和(2),同時給出相應(yīng)的適值函數(shù)f(x).搜索在網(wǎng)絡(luò)平面內(nèi)進(jìn)行,因此速度是矢量,不僅有大小而且具有方向,即存在x和y方向上的速度分量,因此有Vxid=WVxid+c1rand()(Ρid-Xxid)+c2Rand()(Ρgd-Xxid)?(3)Vyid=WVyid+c1rand()(Ρid-Xyid)+c2Rand()(Ρgd-Xyid).(4)Vxid=WVxid+c1rand()(Pid?Xxid)+c2Rand()(Pgd?Xxid)?(3)Vyid=WVyid+c1rand()(Pid?Xyid)+c2Rand()(Pgd?Xyid).(4)同理存在x和y方向上的位置分量,有Xxid=Xxid+Vxid?(5)Xyid=Xyid+Vyid?(6)Xxid=Xxid+Vxid?(5)Xyid=Xyid+Vyid?(6)由于無線傳感器網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)的分布是離散的,因此節(jié)點(diǎn)按式(5)和(6)所計(jì)算的值無法一一映射到相應(yīng)的網(wǎng)絡(luò)節(jié)點(diǎn),需要對求得的位置進(jìn)行調(diào)整,使調(diào)整后的Xxid∈{px1,px2,…,pxn},Xyid∈{py1,py2,…,pyn},其中pxi為簇內(nèi)第i個節(jié)點(diǎn)的x分量,pyi為簇內(nèi)第i個節(jié)點(diǎn)的y分量.令Δpxj=|Xxid-pxj|,Δpyj=|Xyid-pyj|,Δpj=(Δpxj)2+(Δpyj)2.其中Δpxj表示Xxid與簇內(nèi)網(wǎng)絡(luò)節(jié)點(diǎn)j的x分量差的絕對值,Δpyj表示Xyid與簇內(nèi)網(wǎng)絡(luò)節(jié)點(diǎn)j的y分量差的絕對值,設(shè)Δpk=min{Δp1,Δp2,…,Δpn},則表明在網(wǎng)絡(luò)中第k個節(jié)點(diǎn)的位置同Xid最為接近,因此調(diào)整后的值為Xxid≈pxk,Xyid≈pyk,即搜索點(diǎn)現(xiàn)在位于節(jié)點(diǎn)k的位置上.適值函數(shù)的確定同問題域的特點(diǎn)密切相關(guān),節(jié)點(diǎn)的適值不僅要考慮本身能量的大小而且應(yīng)該反映周圍節(jié)點(diǎn)的能量分布,距離該節(jié)點(diǎn)越遠(yuǎn)的鄰居節(jié)點(diǎn)其能量也應(yīng)該越大,相反距離該節(jié)點(diǎn)越近的鄰居節(jié)點(diǎn)應(yīng)具有較小的能量,根據(jù)此特點(diǎn)構(gòu)造的適值函數(shù)為f(k)=ηek+λˉe.f(k)=ηek+λeˉ.其中:η+λ=1且η和λ∈;ˉeeˉ為其他節(jié)點(diǎn)的等效平均能量;k為當(dāng)前網(wǎng)絡(luò)節(jié)點(diǎn)號;η為當(dāng)前節(jié)點(diǎn)能量影響因子,λ為鄰居節(jié)點(diǎn)能量影響因子,通過調(diào)整可以決定鄰居節(jié)點(diǎn)對適值的貢獻(xiàn)比例.等效平均能量定義為ˉe=1n-1n∑i=1,i≠k?ei,其中?ei=f(ei,ri)為第i個節(jié)點(diǎn)的等效能量,ri為第i個節(jié)點(diǎn)至當(dāng)前節(jié)點(diǎn)k的距離,ei為節(jié)點(diǎn)i的剩余能量.f(ei,ri)的構(gòu)造應(yīng)綜合考慮節(jié)點(diǎn)i的剩余能量及至節(jié)點(diǎn)k的距離,滿足如下條件:1)若距離節(jié)點(diǎn)k較遠(yuǎn),節(jié)點(diǎn)i的能量較大則具有較大的函數(shù)值;2)若距離節(jié)點(diǎn)k較近,節(jié)點(diǎn)i的能量較小則具有較大的函數(shù)值.經(jīng)篩選構(gòu)造f(ei,ri)=eiri/(ri+1),該函數(shù)在仿真中證明可有效反應(yīng)問題的特點(diǎn),綜合上述各式經(jīng)整理后可得適值函數(shù)f(k)=ηek+λn-1n∑i=1,i≠keiriri+1.(7)至此給出詳細(xì)的算法步驟如下:Step1:初始粒子群群體規(guī)模為n(即簇內(nèi)節(jié)點(diǎn)數(shù)).Step2:對每個粒子i進(jìn)行如下初始操作:1)隨機(jī)初始化粒子i的Xxid和Xyid,并按上述提到的方法進(jìn)行調(diào)整;2)隨機(jī)初始化粒子i的Vxid和Vyid;3)通過適值函數(shù)公式(7)計(jì)算適值fi;4)使Pgd=群體中的全局極大適值,Pid=fi.Step3:重復(fù)下列步驟直到滿足規(guī)定的循環(huán)次數(shù)或特定的結(jié)束條件:1)查找全局極大適值Pgd;2)對每個粒子i利用式(7)計(jì)算適值Pid;3)對每個粒子i利用式(3)～(6)更新Vxid,Vyid,Xxid,Xyid,并按照上述方法調(diào)整Xxid和Xyid;4)按式(7)計(jì)算各粒子i的適值.Step4:選取具有較大適值的粒子所代表的節(jié)點(diǎn)為優(yōu)化后的簇首.(4)優(yōu)化簇首節(jié)點(diǎn)信息融合該階段輔助簇首節(jié)點(diǎn)將優(yōu)化后的簇首信息發(fā)布給簇內(nèi)節(jié)點(diǎn),實(shí)現(xiàn)優(yōu)化簇首對簇內(nèi)節(jié)點(diǎn)信息的收集和融合.由于優(yōu)化簇的形成綜合考慮了鄰居節(jié)點(diǎn)的狀態(tài)信息,因此簇內(nèi)節(jié)點(diǎn)的能量損耗得以均衡,從而有效避免了盲節(jié)點(diǎn)的頻繁出現(xiàn).5模擬實(shí)驗(yàn)5.1仿真實(shí)驗(yàn)結(jié)果與分析在仿真實(shí)驗(yàn)中,無線傳感器網(wǎng)絡(luò)由100個具有GPS定位功能的節(jié)點(diǎn)組成,節(jié)點(diǎn)在模擬環(huán)境范圍為100m×100m的區(qū)域內(nèi)隨機(jī)分布,基站位于坐標(biāo)(x=50,y=300).本文采用ns-2網(wǎng)絡(luò)仿真器,利用文獻(xiàn)的無線通信系統(tǒng)模型計(jì)算路由協(xié)議的能量損耗.該模型由發(fā)送電路、功率放大器和接收電路構(gòu)成,如圖2所示,其中發(fā)送和接收電路的功耗為Eelec=50nJ/bit,放大電路的功耗為εamp=100pJ/bit/m.當(dāng)發(fā)送方傳輸kbit到距離為d的接收方時,收發(fā)雙方損耗的能量分別為EΤx(k,d)=EΤx-elec(k)+EΤx-amp(k,d)=Eeleck+εampkd2?(8)ERx(k)=ERx-elec(k)=Eeleck.(9)無線傳感器網(wǎng)絡(luò)模型的主要參數(shù)為:每個節(jié)點(diǎn)的初始能量是0.5J,利用LEACH算法對網(wǎng)絡(luò)進(jìn)行初步劃分,每回合的簇重構(gòu)過程中節(jié)點(diǎn)向其簇首發(fā)送的數(shù)據(jù)包為2000bit.選取PSO算法的各參數(shù)值為:η=0.6,λ=0.4,c1=c2=2,W=0.9,rand()和Rand()值在運(yùn)行過程中動態(tài)地隨機(jī)給出,退出條件是迭代次數(shù)為100次.為測試協(xié)議的節(jié)能性,將基于PSO優(yōu)化的分簇路由算法與典型的LEACH算法進(jìn)行比較,并使用如下的性能評價參數(shù):1)網(wǎng)絡(luò)生存時間:仿真開始到最后一個節(jié)點(diǎn)耗盡能量所需的回合數(shù)(回合數(shù)=算法執(zhí)行簇重構(gòu)過程的次數(shù)).2)系統(tǒng)總能量損耗:系統(tǒng)生存時間內(nèi)所有節(jié)點(diǎn)能量損耗的總和(系統(tǒng)生存時間=20%節(jié)點(diǎn)死亡所需的時間).5.2基于網(wǎng)絡(luò)半徑的均衡狀態(tài)圖3反映了兩種協(xié)議的網(wǎng)絡(luò)生存時間,可以看出,本文提出的優(yōu)化分簇算法比LEACH具有更長的網(wǎng)絡(luò)生存時間,其中第一個節(jié)點(diǎn)的死亡時間延遲了近20%.這是因?yàn)長EACH運(yùn)行一段時間后,網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)的剩余能量會出現(xiàn)不均衡狀態(tài),而本文提出的算法能夠均衡簇內(nèi)節(jié)點(diǎn)的能量損耗,避免了盲節(jié)點(diǎn)的過早出現(xiàn),從而延長了網(wǎng)絡(luò)的生存時間.圖4反映了隨著網(wǎng)絡(luò)半徑的不斷增加,兩種協(xié)議的系統(tǒng)總能量損耗.可以看到在小半徑網(wǎng)絡(luò)內(nèi)使用兩種策略,節(jié)點(diǎn)耗費(fèi)的能量相差不多.當(dāng)網(wǎng)絡(luò)的半徑小于50m時,基于優(yōu)化策略所耗費(fèi)的總能量要略高于LEACH.這是因?yàn)樾“霃骄W(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)間的距離很近,由通信距離不同而引起的能量不均衡現(xiàn)象不很明顯,而且本文的分簇算法在確定優(yōu)化簇首階段需要耗費(fèi)一定的能量進(jìn)行迭代計(jì)算.但是隨著網(wǎng)絡(luò)半徑的不斷增大,節(jié)點(diǎn)的能量不均衡現(xiàn)象越來越明顯,優(yōu)化分簇