基于離散粒子群的單跳路由分簇協(xié)議

基于離散粒子群的單跳路由分簇協(xié)議

0基于快速收斂離散粒子群的分布式分簇路由粒子群算法優(yōu)化（pso）是基于團(tuán)隊(duì)智能的自適應(yīng)優(yōu)化算法。它具有快速收斂性能，可以根據(jù)不同的優(yōu)化目標(biāo)提出相應(yīng)的解決方案。無(wú)線傳感器網(wǎng)絡(luò)（無(wú)線傳感器網(wǎng)絡(luò)）通常用于一些特殊環(huán)境。在節(jié)點(diǎn)能量受到限制時(shí)，集群路徑協(xié)議是延長(zhǎng)網(wǎng)絡(luò)壽命的有效方法之一。如果節(jié)點(diǎn)的剩余能量隨著網(wǎng)絡(luò)的運(yùn)行而減少，則會(huì)動(dòng)態(tài)、快速、有效地找到一組最佳節(jié)點(diǎn)作為集群的長(zhǎng)度。這是一個(gè)以這些節(jié)點(diǎn)為中心的節(jié)點(diǎn)分割和節(jié)點(diǎn)規(guī)劃問(wèn)題。這是一個(gè)非常困難的問(wèn)題。現(xiàn)在，在集群分割過(guò)程中，大多數(shù)集群算法采用競(jìng)爭(zhēng)模式，從集群第一開(kāi)始競(jìng)爭(zhēng)，并消耗一定的能量（如leach、lech-e、heed、eec等）。在文獻(xiàn)中，基于leach預(yù)測(cè)簇的排序是最好的集群之一。然而，對(duì)于數(shù)據(jù)收集節(jié)點(diǎn)（基地矩陣，bs）通常定義在監(jiān)控區(qū)域外，集群負(fù)責(zé)人負(fù)責(zé)收集、融合和傳輸來(lái)自集群的信息。當(dāng)任意選擇一組節(jié)點(diǎn)作為集群時(shí)，很容易使遠(yuǎn)離bs的節(jié)點(diǎn)盡快死亡。即使考慮到節(jié)點(diǎn)的剩余能量競(jìng)爭(zhēng)簇的頭，如lech、heed、eec等，也不能解釋相同輸出能量的節(jié)點(diǎn)有相同可能性成為集群的原因。要考慮節(jié)點(diǎn)1時(shí)的能耗消耗率的大小。本文將以延長(zhǎng)網(wǎng)絡(luò)壽命和均衡節(jié)點(diǎn)能耗為目標(biāo),在定義包含鄰居節(jié)點(diǎn)信息的粒子適應(yīng)度函數(shù)的基礎(chǔ)上,提出一種基于快速收斂離散粒子群(DPSO)優(yōu)化簇首選擇過(guò)程的分布式分簇路由協(xié)議,該協(xié)議采用選舉方式產(chǎn)生簇首,無(wú)簇首競(jìng)爭(zhēng)能量消耗,可以較好地避免簇首選擇的隨機(jī)性和均衡網(wǎng)絡(luò)節(jié)點(diǎn)的能量消耗,極大地延長(zhǎng)網(wǎng)絡(luò)壽命;同時(shí),慣性權(quán)重隨機(jī)性的增加和k-收斂準(zhǔn)則有利于提高網(wǎng)絡(luò)壽命與收斂代數(shù)的比.1算法的基本思想通常,對(duì)一m個(gè)粒子的種群,在D維空間的粒子i位置為Xi=(xi1,xi2,…,xiD),粒子搜索至當(dāng)前代個(gè)體最優(yōu)解為Pi=(pi1,pi2,…,piD),當(dāng)前代種群的全局最優(yōu)解為Gi=(gi1,gi2,…,giD),粒子移動(dòng)速度為Vi=(vi1,vi2,…,viD)(vid∈[Vmin,Vmax]),則廣義PSO模型的速度-位移公式如下:V(t+1)i=W(t)×V(t)i+c1R1×(Pi?X(t)i)+c2R2×(Gi?X(t)i)(1)X(t+1)i=Q(X(t)i+V(t+1)i)(2)Vi(t+1)=W(t)×Vi(t)+c1R1×(Ρi-Xi(t))+c2R2×(Gi-Xi(t))(1)Xi(t+1)=Q(Xi(t)+Vi(t+1))(2)(1)和(2)式中t和t+1分別表示當(dāng)前代和下一代.定義Xic為粒子連續(xù)位置向量,則函數(shù)Q(Xic)為粒子位置映射函數(shù),對(duì)連續(xù)問(wèn)題函數(shù)為原來(lái)位置與位移的線性疊加,對(duì)離散問(wèn)題則根據(jù)具體問(wèn)題進(jìn)行非線性變換.式中R1,R2為取值范圍內(nèi)的D維隨機(jī)數(shù)向量;學(xué)習(xí)因子c1,c2用來(lái)調(diào)節(jié)個(gè)體最優(yōu)解和全局最優(yōu)解的對(duì)粒子下一代的影響,慣性權(quán)重W(t)用來(lái)控制當(dāng)前代粒子速度對(duì)下一代的影響,其選擇方式有:①約束方式(CFA,constrictionfactorapproach),該方式適用于Pi和Gi固定的問(wèn)題求解.②線性方式(IWLA,inertiaweightlinearapproach),慣性權(quán)重取值如下:W(t)j=wmax?wmax?wminImaxiiter(3)Wj(t)=wmax-wmax-wminΙmaxiiter(3)式中Imax為終止迭代次數(shù).隨著迭代次數(shù)iiter的增加,W(t)如由wmax減小為wmin,即起始粗粒度搜索全局最優(yōu),逐漸過(guò)渡到細(xì)粒度的最優(yōu)解查找,該方式與求解問(wèn)題無(wú)關(guān).③隨機(jī)方式(IWRA,inertiaweightrandomapproach),慣性權(quán)重確定如下:W(t)=wI+(1?w)R3(4)W(t)=wΙ+(1-w)R3(4)式中I為D維全1向量,R3為取值范圍內(nèi)的隨機(jī)數(shù)D維向量,w為取值范圍內(nèi)的隨機(jī)數(shù),通常為0.5,學(xué)習(xí)因子c1,c2取值為1.494.收斂準(zhǔn)則:通常,迭代的結(jié)束以算法不能找到更優(yōu)解為準(zhǔn)則,而在實(shí)現(xiàn)時(shí),需要在每次迭代循環(huán)中判斷是否要結(jié)束.在避免早熟和收斂速度采取折衷措施,在迭代過(guò)程中目標(biāo)函數(shù)F(z(g))滿足下面條件:F(z(g))?F(z(g?k))≤ε(5)F(z(g))-F(z(g-k))≤ε(5)則算法終止.其中ε>0,g為當(dāng)前迭代代數(shù),k為迭代間隔.對(duì)本文的離散問(wèn)題,目標(biāo)函數(shù)為粒子的適應(yīng)度,由于問(wèn)題的動(dòng)態(tài)變化,無(wú)法預(yù)知是否達(dá)到最優(yōu)解,因此,算法迭代終止準(zhǔn)則有:一種是在規(guī)定的終止代數(shù)Niter間內(nèi)不能找到更優(yōu)解,即全部粒子收斂于一點(diǎn),簡(jiǎn)稱全收斂(Allconvergence,All-C),顯然,該準(zhǔn)則收斂速度較慢;另一種是連續(xù)k代未有更優(yōu)解,簡(jiǎn)稱k-收斂(k-convergence,k-C).2dpso分簇路由協(xié)議對(duì)某一區(qū)域范圍內(nèi)的M個(gè)傳感器節(jié)點(diǎn),構(gòu)造一m(m≤M)個(gè)粒子的種群,定義位置映射函數(shù)為Q(Xic)={Xnd|min(∥Xnd?Xic∥),1≤n≤M}(6)Q(Xic)={Xnd|min(∥Xnd-Xic∥),1≤n≤Μ}(6)(6)式表示與Xic歐氏距離最小離散節(jié)點(diǎn)粒子位置Xnd作為新的位置.本文的適應(yīng)度函數(shù)充分考慮某區(qū)域范圍內(nèi)節(jié)點(diǎn)粒子的剩余能量和預(yù)測(cè)能耗等因素.首先,定義粒子n的能量富裕指數(shù)為f1(n)=εˉr?Er(n)ΔE?r(n)(7)f1(n)=εˉr-Er(n)ΔE^r(n)(7)式中,Er(n)為粒子剩余能量,εˉrεˉr為區(qū)域內(nèi)所有粒子剩余能量均值,ΔE?E^r(n)為粒子的預(yù)測(cè)能耗;顯然,該值越小,表示該粒子的能量富裕程度越高.其次,定義粒子預(yù)測(cè)能耗消耗率為f2(n)=ΔE?r(n)Er(n)(8)f2(n)=ΔE^r(n)Er(n)(8)fz(n)值越小,表示該粒子節(jié)點(diǎn)負(fù)荷越輕.若定義粒子預(yù)測(cè)能耗消耗率與粒子群預(yù)測(cè)能耗消耗率均值的比率為f3(n),則該值越小,表示相對(duì)于粒子群中的其他粒子負(fù)荷較輕.同理,若定義預(yù)測(cè)能耗消耗率在區(qū)域內(nèi)所有粒子預(yù)測(cè)能耗消耗率均值的比率為f4(n),該值越小,表示相對(duì)于區(qū)域中其它粒子負(fù)荷較輕.據(jù)此,本文的粒子n適應(yīng)度函數(shù)定義為fFit(Xnd)=∑j=14αjfj(n),∑j=14αj=1,αj∈(9)fFit(Xnd)=∑j=14αjfj(n),∑j=14αj=1,αj∈(9)顯然,系數(shù)α1～α4決定了4種分量對(duì)適應(yīng)值的貢獻(xiàn)比例.粒子越富裕,負(fù)荷越輕,其適應(yīng)值就越小,越有可能成為簇首.本文的DPSO分簇算法就是尋找最小適應(yīng)值粒子擔(dān)任簇首,即min{fFit(Xnd)}.基于分簇的WSN路由協(xié)議分為分簇、簇內(nèi)時(shí)隙分配、簇內(nèi)數(shù)據(jù)傳輸、簇間(包括至BS)數(shù)據(jù)傳輸幾個(gè)階段.DPSO分簇路由協(xié)議的主要任務(wù)是在分簇階段完成簇首的選舉.在分簇階段隨機(jī)選擇一組節(jié)點(diǎn)執(zhí)行DPSO算法,執(zhí)行該算法的節(jié)點(diǎn)稱為DPSO代理,由代理選舉產(chǎn)生出適應(yīng)值最小的節(jié)點(diǎn)擔(dān)任簇首.若代理有Nb個(gè)鄰居節(jié)點(diǎn),種群規(guī)模數(shù)m為min{Nb/3,mmax},mmax為最大種群規(guī)模,終止代數(shù)為Niter,則算法流程如圖1所示.本文的路由協(xié)議考慮如下能耗:數(shù)據(jù)包在收發(fā)機(jī)中處理能耗、數(shù)據(jù)包的發(fā)送能耗,數(shù)據(jù)包的數(shù)據(jù)融合能耗,并假設(shè):①監(jiān)測(cè)區(qū)域內(nèi)所有節(jié)點(diǎn)同質(zhì),初始能量相同,可以通過(guò)信號(hào)強(qiáng)度計(jì)算節(jié)點(diǎn)間的距離;②節(jié)點(diǎn)的通信功率可調(diào);③BS和節(jié)點(diǎn)位置信息已知,BS位置固定且遠(yuǎn)離監(jiān)測(cè)區(qū)域,BS能量足夠大,網(wǎng)絡(luò)已經(jīng)同步.基于DPSO的分簇路由協(xié)議如下:1打造分簇形成子階段節(jié)點(diǎn)n根據(jù)式(10)計(jì)算r“輪”是否成為DPSO代理的門(mén)限T(n,r)Th1(n,r)={PN/Na,PN/Na<11,PN/Na≥1(10)Τh1(n,r)={ΡΝ/Νa,ΡΝ/Νa<11,ΡΝ/Νa≥1(10)式中P為簇首比例因子,N為傳感器節(jié)點(diǎn)數(shù),Na為非死亡傳感器節(jié)點(diǎn)數(shù).選擇一隨機(jī)數(shù)p(0≤p≤1),若p<Th1(n,r),該節(jié)點(diǎn)當(dāng)選為代理,進(jìn)入選舉簇首子階段2).當(dāng)p≥Th1(n,r)時(shí),若在DPSO最大演化時(shí)間TDPSO內(nèi)監(jiān)聽(tīng)到選擇簇首消息Candidate_Sel_Req或聲明成為簇首消息Clusterhead_Msg,則進(jìn)入分簇形成子階段;否則,調(diào)整代理門(mén)限Th1(n,r)為T(mén)h2(n,r,i)Th2(n,r,i)={2iP,2iP<11,2iP≥1(11)Τh2(n,r,i)={2iΡ,2iΡ<11,2iΡ≥1(11)式中i為在該階段的循環(huán)迭代次數(shù),繼續(xù)循環(huán)執(zhí)行1).2獲得本地節(jié)點(diǎn)代理節(jié)點(diǎn)執(zhí)行DPSO算法終止后,選舉產(chǎn)生節(jié)點(diǎn)Id為簇首,若為本地節(jié)點(diǎn),則對(duì)外發(fā)送Clusterhead_Msg后成為簇首;若非本地節(jié)點(diǎn),則發(fā)送Candidate_Sel_Req;進(jìn)入分簇形成子階段3).3dpso代理與引領(lǐng)性基于信號(hào)發(fā)送階段在該子階段,節(jié)點(diǎn)在不同狀態(tài)時(shí)對(duì)收到消息的處理如下:①狀態(tài)不為簇首時(shí)收到己方的Candidate_Sel_Req,則發(fā)送消息Clusterhead_Msg成為簇首,等待其他節(jié)點(diǎn)加入該簇,繼續(xù)循環(huán)執(zhí)行3);②狀態(tài)不為簇首時(shí)收到Clusterhead_Msg,則根據(jù)信號(hào)強(qiáng)弱對(duì)選擇距離最近簇首發(fā)送加入簇請(qǐng)求消息Join_Req_Msg,等待簇首確認(rèn)消息Join_Ack_Msg;若收到Join_Ack_Msg,節(jié)點(diǎn)成為普通節(jié),進(jìn)入發(fā)送監(jiān)測(cè)數(shù)據(jù)階段,否則,繼續(xù)等待.③狀態(tài)為簇首在收到所有請(qǐng)求加入簇消息Join_Req_Msg后,發(fā)送Join_Ack_Msg完成該簇內(nèi)節(jié)點(diǎn)的時(shí)隙分配,進(jìn)入TDMA工作的監(jiān)測(cè)數(shù)據(jù)的發(fā)送階段.協(xié)議后續(xù)階段與LEACH協(xié)議結(jié)構(gòu)類似,這里不再贅述.在簇首選舉期間,即在DPSO代理產(chǎn)生和選舉簇首2個(gè)子階段的發(fā)送簇首選擇或聲明消息的通信開(kāi)銷介于PN與N之間;而時(shí)間開(kāi)銷最大為Niter[log2(1/P)],因此,其復(fù)雜度為O(1),在不影響DPSO最佳搜索結(jié)果和收斂速度情況下,降低Niter可降低算法的時(shí)間開(kāi)銷.為評(píng)價(jià)慣性權(quán)重對(duì)DPSO的收斂速度和網(wǎng)絡(luò)壽命LFND影響,定義評(píng)價(jià)指標(biāo):網(wǎng)絡(luò)壽命與平均收斂代數(shù)比為Φ=LFNDIc(12)Φ=LFΝDΙc(12)式中Ic為在LFND內(nèi)DPSO算法的平均收斂代數(shù).顯然,LFND越大,Ic越小,則算法的性價(jià)比Φ越高.3多經(jīng)傳播能耗3.1網(wǎng)絡(luò)節(jié)點(diǎn)能耗均勻性分析DPSO慣性權(quán)重采用IWRA,Niter=100,mmax=20,w=0.5,c1=c2=1.494,α1=0.6,α2=0.1,α3=α4=0.15,收斂準(zhǔn)則為All-C,圖2給出了場(chǎng)景S1的3種協(xié)議的節(jié)點(diǎn)死亡數(shù)與工作輪數(shù)的關(guān)系曲線,可以看到:基于CDPSO算法較LEACH和LEACH-E延長(zhǎng)了LFND達(dá)91.7%和53.3%,并且在LFND輪之后其余網(wǎng)絡(luò)節(jié)點(diǎn)在較短的工作輪之后失效,能量利用特性較好.圖3給出了相應(yīng)的每一輪中非死亡節(jié)點(diǎn)平均剩余能量與均方差曲線,結(jié)果表明:在LFND輪內(nèi),LEACH、LEACH-E算法的節(jié)點(diǎn)剩余能量均方差近似于線性增加,而CDPSO算法的剩余能量均方差維持在一個(gè)較小的范圍,因此DPSOCA的網(wǎng)絡(luò)節(jié)點(diǎn)能耗均勻性較好.3.2全收斂準(zhǔn)則的lfnd分析在Niter=100,c1=c2=1.494,α1=0.6,α2=0.1,α3=α4=0.15,mmax=20時(shí),對(duì)IWRA方式,w由0.1增加至0.9,算法收斂準(zhǔn)則分別為:全收斂(All-C),k-收斂(k=10,3),場(chǎng)景S1和S2的Φ如圖4所示,結(jié)果表明:①w從0.1增至0.9時(shí),慣性權(quán)重隨機(jī)性降低,LFND有少許增加,而CDPSO收斂代數(shù)快速上升反而使得Φ有所下降;②在其他參數(shù)設(shè)置相同條件下,全收斂準(zhǔn)則的收斂代數(shù)明顯大于k-收斂的收斂代數(shù),而其LFND較為穩(wěn)定變化很小,如S1在3種終止準(zhǔn)則的LFND統(tǒng)計(jì)值為(1739.5±1.7)All-C,(1740.2±1.6)10-C和(1737.7±1.2)3-C,S2在3種終止準(zhǔn)則的LFND統(tǒng)計(jì)值為(710.1±2.0)All-C,(692.9±1.5)10-C和(684.4±4.3)3-C,說(shuō)明k-C準(zhǔn)則的Φ性能明顯優(yōu)于All-C準(zhǔn)則;③在k-C準(zhǔn)則下,減小k有利于提高Φ,且在高節(jié)點(diǎn)濃