基于自適應(yīng)粒子群優(yōu)化的WSNs非均勻分簇路由算法*

杭 超, 李 剛,2,3, 包 涵, 李雯珺, 李德倉(cāng)

(1.蘭州交通大學(xué) 機(jī)電技術(shù)研究所,甘肅 蘭州 730070； 2.甘肅省物流及運(yùn)輸裝備信息化工程技術(shù)研究中心,甘肅 蘭州 730070； 3.甘肅省物流與運(yùn)輸裝備行業(yè)技術(shù)中心,甘肅 蘭州 730070)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)是由大量具有感知、無線通信和計(jì)算能力的低成本微型傳感器節(jié)點(diǎn)組成[1～3]。網(wǎng)絡(luò)一般由能量有限的電池進(jìn)行供電,為了最大程度利用能量,設(shè)計(jì)一種高效的路由協(xié)議至關(guān)重要,尤其在大規(guī)模WSNs中,高效的路由協(xié)議能提高網(wǎng)絡(luò)的工作效率,均衡網(wǎng)絡(luò)能量。

相比平面路由協(xié)議,基于分簇的層次路由方法能有效提升網(wǎng)絡(luò)的可擴(kuò)展性[4],減少數(shù)據(jù)轉(zhuǎn)發(fā)次數(shù),降低網(wǎng)絡(luò)能耗,提高數(shù)據(jù)采集效率和精度。LEACH[5]作為一種最為經(jīng)典的均勻分簇路由算法,在一定程度上能緩解網(wǎng)絡(luò)能耗問題,但該算法在簇頭選舉和簇間傳輸上存在缺陷,不利于網(wǎng)絡(luò)中能量均衡。HEED[6]改進(jìn)了LEACH上述缺陷，在簇首競(jìng)選時(shí)充分考慮到節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)相鄰度和節(jié)點(diǎn)密度等因素,簇間路由以多跳的形式傳輸數(shù)據(jù)。李成法等人[7]提出了EEUC算法,運(yùn)用競(jìng)爭(zhēng)半徑思想合理劃分網(wǎng)絡(luò)來均衡能耗,簇首到匯聚節(jié)點(diǎn)以多跳的通信方式。粒子群優(yōu)化(particle swarm optimization,PSO)算法作為種群智能優(yōu)化算法,相比其他算法在解決組合優(yōu)化問題上具有很大優(yōu)勢(shì)[8]。文獻(xiàn)[9]提出了一種基于PSO的非均勻雙簇頭分簇算法,簇首節(jié)點(diǎn)通過PSO算法優(yōu)化確定,然后在規(guī)模較大的簇中構(gòu)造一個(gè)副簇頭以減輕主簇頭的能耗,但選舉副簇首會(huì)消耗大量能量,不利于網(wǎng)絡(luò)能量平衡。文獻(xiàn)[10]提出一種基于非線性自適應(yīng)PSO(adaptive PSO,APSO)的WSNs分簇策略,通過調(diào)整傳統(tǒng)PSO算法的慣性權(quán)重避免過早陷入局部最優(yōu)。

為了使網(wǎng)絡(luò)能耗更加均衡,本文提出一種基于APSO的WSNs非均勻分簇路由(APSO-based non-uniform clustering routing,APSO-NUCR)算法。仿真結(jié)果表明,該算法能有效均衡網(wǎng)絡(luò)能耗,延長(zhǎng)網(wǎng)絡(luò)生存周期。

1 系統(tǒng)網(wǎng)絡(luò)模型

將N個(gè)傳感器節(jié)點(diǎn)隨機(jī)布置在一個(gè)規(guī)則平面內(nèi),并具有以下性質(zhì)：1)所有傳感器節(jié)點(diǎn)同構(gòu)且位置固定,并具有唯一編號(hào)；2)基站的能量和計(jì)算能力不被限制；3)根據(jù)需要可自主調(diào)節(jié)無線發(fā)射功率。WSNs的數(shù)據(jù)通信能耗模型計(jì)算公式如下

(1)

ERX(k,d)=kEelec

(2)

2 基于改進(jìn)PSO的NUCR算法

2.1 非均勻分簇建立

1)候選簇首節(jié)點(diǎn)

引入能量閾值對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行篩選,考慮到網(wǎng)絡(luò)能量熱區(qū)問題,篩選公式引入距離因子如下

(3)

式中E(i)為節(jié)點(diǎn)i的當(dāng)前能量,Eave為網(wǎng)絡(luò)中節(jié)點(diǎn)的平均能量,w為調(diào)節(jié)系數(shù),di為節(jié)點(diǎn)i到匯聚節(jié)點(diǎn)之間的距離。初始化時(shí),每一個(gè)節(jié)點(diǎn)產(chǎn)生在[0,1]區(qū)間的隨機(jī)數(shù)μ,只有當(dāng)T(i)>μ時(shí),節(jié)點(diǎn)才有機(jī)會(huì)當(dāng)選為候選簇首。

2)競(jìng)爭(zhēng)半徑

通過上式篩選出的候選簇首節(jié)點(diǎn)的能量充足且靠近匯聚節(jié)點(diǎn)附近區(qū)域的簇首數(shù)量較多。為了有效均衡網(wǎng)絡(luò)能耗,需要對(duì)網(wǎng)絡(luò)進(jìn)行合理的劃分,競(jìng)爭(zhēng)半徑計(jì)算公式如下

(4)

2.2 基于改進(jìn)PSO的簇首優(yōu)化

將非均勻分簇階段篩選出的候選簇首節(jié)點(diǎn)形成一個(gè)候選簇首集合,從中進(jìn)行M次選取,每次選取K個(gè)候選簇首,最終形成M組包含K個(gè)元素的初始簇頭集合,即形成含有K個(gè)元素的M個(gè)粒子。本文將從簇首能量、簇首位置2個(gè)方面建立適應(yīng)度函數(shù)從而來綜合評(píng)價(jià),如式(5)所示

F=af1+(1-a)f2

(5)

式中a為權(quán)值系數(shù),用來調(diào)整能量與位置之間的比重,a∈(0,1]。

1)簇首能量因子

簇首能量因子定義為簇首的能量平均值與全網(wǎng)絡(luò)中簇成員節(jié)點(diǎn)的能量均值之比

(6)

2)簇首位置因子

由能耗模型可知,通信距離與能耗成正比?？紤]到位置因素對(duì)候選簇首的影響,從以下兩個(gè)方面分析：一是候選簇首在WSNs中的位置,二是候選簇首在簇內(nèi)的位置。通過網(wǎng)絡(luò)中非簇首節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的距離與候選簇首分別到匯聚節(jié)點(diǎn)距離、簇內(nèi)成員節(jié)點(diǎn)距離之和比

(7)

式中d(NCHi,Sink)為簇內(nèi)成員節(jié)點(diǎn)i和匯聚節(jié)點(diǎn)之間的距離,d(CHj,Sink)為簇首j到匯聚節(jié)點(diǎn)的距離,d(NCHi,CHj)為在簇首j競(jìng)爭(zhēng)半徑范圍內(nèi),簇內(nèi)成員節(jié)點(diǎn)i到簇首節(jié)點(diǎn)j的距離。

算法初始時(shí),對(duì)每一組候選簇首節(jié)點(diǎn)集合進(jìn)行適應(yīng)度計(jì)算,即計(jì)算每個(gè)粒子的適應(yīng)度值。此時(shí),適應(yīng)度值最大粒子的位置作為全局最優(yōu)位置,其他粒子的為局部最優(yōu)位置。

2.3 速度與位置的更新

算法完成初始化參數(shù)后,開始進(jìn)行迭代,更新粒子的速度和位置,再計(jì)算更新后粒子的適應(yīng)度值。由于速度是矢量,WSNs布置的區(qū)域又是一個(gè)規(guī)則的平面,所以建立一個(gè)二維平面坐標(biāo)系,能很好地將網(wǎng)絡(luò)中節(jié)點(diǎn)的位置xid和速度vid用在x,y坐標(biāo)方向上的分量表示,計(jì)算公式如下

(8)

式中w為慣性權(quán)重,起調(diào)整粒子搜索速度的作用；c1,c2分別為個(gè)體部分和群體部分的認(rèn)知因子,通常取2；r1和r2為分布在區(qū)間[0,1]內(nèi)的隨機(jī)數(shù),用來增加搜索的隨機(jī)性。

粒子在x,y軸上的位置分量更新公式為

(9)

由于WSNs中節(jié)點(diǎn)是離散式分布的,在每一輪迭代結(jié)束后,候選簇首的位置被更新,但在網(wǎng)絡(luò)中不一定能找到對(duì)應(yīng)位置存在的節(jié)點(diǎn),這時(shí)按照距離最近原則確定實(shí)際節(jié)點(diǎn)所在位置,計(jì)算公式如式(10)所示

dCMn=

(10)

式中 (CMnx,CMny)為節(jié)點(diǎn)CMn的坐標(biāo)。

PSO簇首流程如圖1所示。

圖1 PSO簇首流程

2.4 改進(jìn)慣性權(quán)重系數(shù)

傳統(tǒng)PSO算法將慣性權(quán)重系數(shù)設(shè)置為固定值,無法隨著算法具體運(yùn)行狀態(tài)的改變而變化。當(dāng)粒子適應(yīng)度值小時(shí),增大粒子的搜索速度,注重尋找全局最優(yōu)位置；相反,當(dāng)粒子適應(yīng)度較大時(shí),降低粒子的搜索速度,重點(diǎn)關(guān)注局部最優(yōu)位置,提高收斂精度。根據(jù)不同粒子的不同適應(yīng)度值,提出了自適應(yīng)的慣性權(quán)重分配策略。在每一次迭代中,計(jì)算每一個(gè)粒子的適應(yīng)度值,根據(jù)粒子的當(dāng)前適應(yīng)度值為每個(gè)粒子分配一個(gè)慣性權(quán)重,計(jì)算公式如式(11)

(11)

2.5 自適應(yīng)的學(xué)習(xí)因子

學(xué)習(xí)因子c1為粒子靠近個(gè)體最優(yōu)位置的能力強(qiáng)弱。當(dāng)c1值越大,粒子靠近個(gè)體最優(yōu)的能力越強(qiáng),即粒子加強(qiáng)對(duì)自身的思考,行為越發(fā)獨(dú)立,導(dǎo)致粒子在搜索空間內(nèi)越分散。學(xué)習(xí)因子c2為粒子靠近種群最優(yōu)位置的能力。當(dāng)c2值越大時(shí),粒子靠近種群最優(yōu)位置的能力越強(qiáng),即加強(qiáng)了粒子群體意識(shí),粒子在搜索空間上體現(xiàn)出更加聚集,算法收斂速度大大增強(qiáng),但收斂精度下降,容易越過全局最優(yōu)位置[11]。

傳統(tǒng)PSO算法將學(xué)習(xí)因子統(tǒng)一設(shè)定為固定值,這不利于算法的收斂速度和精度。當(dāng)粒子的適應(yīng)度值越大時(shí),表明此時(shí)粒子處于較優(yōu)的位置,應(yīng)加強(qiáng)對(duì)粒子本身的思考,反之當(dāng)粒子適應(yīng)度值較小時(shí),應(yīng)加強(qiáng)種群間的社會(huì)認(rèn)知能力,具體計(jì)算公式如下

(12)

式中c1max,c2max為影響個(gè)體、種群部分的最大學(xué)習(xí)因子,在本文中均取2.5,c1min,c2min為影響個(gè)體、種群部分的最小學(xué)習(xí)因子,在本文中都均取0.5。

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

簇內(nèi)成員節(jié)點(diǎn)直接與簇首進(jìn)行通信,簇間通信則采用基于最小生成樹建立的最優(yōu)路徑進(jìn)行數(shù)據(jù)傳輸。采用Prim算法以匯聚節(jié)點(diǎn)為作為根節(jié)點(diǎn),建立基于最小生成樹的最優(yōu)數(shù)據(jù)傳輸路徑,由于在本文中WSNs中通信鏈路是對(duì)稱的,建立了從匯聚節(jié)點(diǎn)到各個(gè)簇首的最優(yōu)路徑等同于各個(gè)簇首到匯聚節(jié)點(diǎn)的最優(yōu)路徑。以簇首和匯聚節(jié)點(diǎn)的位置構(gòu)造一個(gè)帶有權(quán)值的有向連通圖G=(V,E),V為包含有簇首節(jié)點(diǎn)和匯聚節(jié)點(diǎn)的集合,E代表V集合中節(jié)點(diǎn)連線的權(quán)值。用U集合來保存最小生成樹的節(jié)點(diǎn),W記錄待轉(zhuǎn)發(fā)節(jié)點(diǎn)和其鄰居節(jié)點(diǎn)連線的權(quán)值,T用來記錄最小生成樹的邊的權(quán)值,權(quán)值計(jì)算公式如下

(13)

式中a,b,c分別為調(diào)節(jié)各部分的權(quán)重系數(shù),a+b+c=1；dij為簇首i,j之間的距離；ei,ej分別為簇首i,j的當(dāng)前能量；Si,Sj分別為簇首i,j所在簇的規(guī)模大小。

匯聚節(jié)點(diǎn)向全網(wǎng)簇首廣播一個(gè)信號(hào),各個(gè)簇首根據(jù)接收到的信號(hào)強(qiáng)度值確定各自到匯聚節(jié)點(diǎn)的大致距離。同理,簇首間相互發(fā)送信號(hào),確定簇首間的距離。最終確定了網(wǎng)絡(luò)中簇首與匯聚節(jié)點(diǎn)、簇首之間的距離。

根據(jù)Prim的最小生成樹路由算法步驟如下：

步驟1 初始時(shí)將匯聚節(jié)點(diǎn)作為根節(jié)v0點(diǎn)添加到U集合中,此時(shí)U={v0},W,T為空集；

步驟2 根據(jù)權(quán)值公式計(jì)算G=(V,E)中所有邊的權(quán)值并記錄到W集合中,規(guī)定如果匯聚節(jié)點(diǎn)到某節(jié)點(diǎn)的距離d0i

步驟3 從根節(jié)點(diǎn)v0出發(fā)尋找權(quán)值最小的下一跳節(jié)點(diǎn),并將找到的下一跳節(jié)點(diǎn)添加到U集合中,將權(quán)值最值最小所在的邊添加進(jìn)T集合中；

步驟4 重復(fù)步驟3,直到U=V,將集合U中的節(jié)點(diǎn)和集合T中的邊形成一棵最小生成樹。網(wǎng)絡(luò)中的簇首節(jié)點(diǎn)按照最小生成樹將數(shù)據(jù)傳輸至匯聚節(jié)點(diǎn)。

基于Prim算法建立的最小生成樹路徑忽略了各節(jié)點(diǎn)的負(fù)載問題,負(fù)載過高的節(jié)點(diǎn)能量消耗過快,使其過早失效,從而影響其他節(jié)點(diǎn)。在完成初始路由建立后,需要根據(jù)節(jié)點(diǎn)的負(fù)載情況來優(yōu)化路由結(jié)構(gòu)。假設(shè)有k個(gè)節(jié)點(diǎn)與某個(gè)節(jié)點(diǎn)通信,則視為該節(jié)點(diǎn)的負(fù)載為k,優(yōu)化流程如圖2所示。

圖2 節(jié)點(diǎn)負(fù)載優(yōu)化流程

4 仿真結(jié)果分析

4.1 仿真參數(shù)設(shè)置

本文采用MATLAB作為仿真工具對(duì)本文所提出的算法性能進(jìn)行驗(yàn)證,仿真參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)

4.2 不同適應(yīng)度函數(shù)權(quán)重的取值

均方差值反映一組數(shù)據(jù)的差異性,一組數(shù)據(jù)的均方差值越小,表明這組數(shù)據(jù)差異性越小,越均衡、越穩(wěn)定。如圖3采用不同的適應(yīng)度函數(shù)權(quán)值進(jìn)行迭代,根據(jù)節(jié)點(diǎn)剩余能量均方差值來評(píng)判權(quán)值選取的優(yōu)越性。當(dāng)a取值為0.5時(shí),即能量因子和位置因子權(quán)值相同時(shí),節(jié)點(diǎn)剩余能量均方差值最小,表明此時(shí)網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)剩余能量差異最小,能量消耗越均衡,有利于延長(zhǎng)網(wǎng)絡(luò)的生命周期。

圖3 在不同適應(yīng)度函數(shù)權(quán)值下的節(jié)點(diǎn)剩余能量均方差

4.3 節(jié)點(diǎn)存活數(shù)量

由圖4表明,網(wǎng)絡(luò)中存活節(jié)點(diǎn)的個(gè)數(shù)隨著運(yùn)行輪數(shù)的增加不斷減少。其中LEACH算法存活節(jié)點(diǎn)的減少速率最快,大約在305輪左右出現(xiàn)第一個(gè)節(jié)點(diǎn)死亡,直到1 300輪左右網(wǎng)絡(luò)中的節(jié)點(diǎn)全部死亡。EEUC算法和NAPSO算法分別在400輪左右和510輪左右開始出現(xiàn)第一個(gè)節(jié)點(diǎn)死亡,直到1 480輪左右和1 700輪左右網(wǎng)絡(luò)中的節(jié)點(diǎn)全部死亡。APSO-NUCR算法大約在600輪左右開始有節(jié)點(diǎn)死亡,比LEACH,EEUC,NAPSO分別延長(zhǎng)了96.7 %,50 %,17.6 %,APSO-NUCR算法在2 200輪左右節(jié)點(diǎn)全部死亡,比LEACH,EEUC,NAPSO分別延長(zhǎng)了69.2 %,48.6 %,29.4 %。

圖4 不同路由算法的節(jié)點(diǎn)存活數(shù)對(duì)比

4.4 簇首能耗

如圖5對(duì)比了4種路由算法的簇首能耗,由于LEACH算法在選擇簇首的隨機(jī)性,導(dǎo)致相比其他3種算法的簇首能耗要大一些,而且能耗波動(dòng)較大。EEUC算法改進(jìn)了LEACH的缺陷,簇間采用多跳傳輸數(shù)據(jù)方式,相比LEACH一定程度上緩解了簇首的能耗。NAPSO算法的簇首能耗基本上在0.02～0.05 J之間徘徊。本文APSO-NUCR算法在簇首能耗方面表現(xiàn)最為優(yōu)秀,波動(dòng)也較小,基本上在0.01～0.03 J 范圍內(nèi)。這是由于APSO-NUCR在簇首選舉時(shí),充分考慮到能量和簇首在網(wǎng)絡(luò)中、簇內(nèi)的位置關(guān)系,更加合理挑選出性能優(yōu)越的節(jié)點(diǎn)。

圖5 不同路由算法的簇首能耗對(duì)比

5 結(jié) 論

針對(duì)WSNs中出現(xiàn)的能量熱區(qū)問題,本文提出一種基于自適應(yīng)粒子群的WSNs非均勻分簇路由算法。通過粒子適應(yīng)度值合理優(yōu)化的慣性權(quán)重和學(xué)習(xí)因子,平衡全局搜索能力和局部探索能力。APSO-NUCR算法通過以能量和位置因子來評(píng)判候選簇首的性能,并確定最終簇首；建立了基于最小生成樹的最優(yōu)傳輸路徑。仿真結(jié)果表明,APSO-NUCR算法能最大化利用網(wǎng)絡(luò)能量,均衡網(wǎng)絡(luò)中各區(qū)域的能耗,延長(zhǎng)了網(wǎng)絡(luò)的生存周期。