門順治,孫順遠,徐保國

(江南大學物聯(lián)網(wǎng)工程學院,江蘇 無錫 214122)

?

基于PSO的無線傳感器網(wǎng)絡非均勻分簇雙簇頭路由算法*

門順治,孫順遠,徐保國*

(江南大學物聯(lián)網(wǎng)工程學院,江蘇 無錫 214122)

針對無線傳感器網(wǎng)絡中分簇路由算法簇頭負載過重,同時也為了提高無線傳感器網(wǎng)絡的能量利用效率,提出了一種基于PSO的非均勻分簇雙簇頭路由算法。該算法首先通過候選簇頭節(jié)點與基站距離的遠近構(gòu)造出幾何規(guī)模不等的簇,然后根據(jù)簇的規(guī)模引進PSO優(yōu)化算法最終選擇出主簇頭與副簇頭。主簇頭主要負責簇內(nèi)節(jié)點數(shù)據(jù)的采集跟數(shù)據(jù)融合,副簇頭主要完成簇內(nèi)及簇間數(shù)據(jù)轉(zhuǎn)發(fā)任務,實現(xiàn)數(shù)據(jù)的單跳與多跳傳輸。仿真結(jié)果表明,該算法有效的減少了簇頭節(jié)點的能耗,在很大程度上均衡了整個網(wǎng)絡的能耗,實現(xiàn)了網(wǎng)絡生存周期的延長。

無線傳感器網(wǎng)絡;非均勻分簇;粒子群優(yōu)化算法;雙簇頭

無線傳感器網(wǎng)絡WSN[1](Wireless Sensor Network)是由部署在監(jiān)測區(qū)域內(nèi)大量能量有限的微型傳感器網(wǎng)絡節(jié)點組成,通過無線通信的方式形成一個網(wǎng)絡系統(tǒng),其目的是協(xié)作感知、采集和處理網(wǎng)絡覆蓋地理區(qū)域內(nèi)感知對象的信息,并發(fā)布給觀察者。近年來,隨著傳感器技術、通信技術等技術的發(fā)展,WSN越來越廣泛的應用于工業(yè)、農(nóng)業(yè)、環(huán)境監(jiān)測等方面。在WSN中,由于節(jié)點一般處于靜止狀態(tài)且電池難以更新,如何設計出一種節(jié)約節(jié)點能量、延長網(wǎng)絡生存周期的無線路由算法是當前的熱點之一[2-3]。

1 相關工作

1.1 分簇算法的論述

2000年Heinzelman W R等人提出的LEACH[4](Low-Energy Adaptive Clustering Hierarchy)算法是一種經(jīng)典的低能量自適應分簇路由算法。在LEACH算法中,簇頭節(jié)點跟基站采用的是單跳路由通信協(xié)議,離基站較遠的簇頭能量消耗過大而過早死亡,影響整個網(wǎng)絡的生存周期,并且單跳傳輸不易于無線傳感器網(wǎng)絡的擴展。針對LEACH算法中離基站較遠的簇頭因發(fā)送數(shù)據(jù)能量消耗過多而過早死亡,文獻[5]采用了一種多跳通信方式,但是由于距離基站較近的簇頭承擔著更多的數(shù)據(jù)轉(zhuǎn)發(fā)任務而消耗過多能量,易形成“熱區(qū)”。EECS[6]算法采用的是分布式工作方式,節(jié)點僅需局部信息即可完成分簇,并且分簇充分考慮到節(jié)點的剩余能量及簇首間的負載平衡。但由于簇首到匯聚節(jié)點仍采用單跳傳輸方式,無法從根本上解決熱區(qū)問題。EEUC[7](Energy-Efficient Uneven Clustering)算法通過構(gòu)造幾何規(guī)模不等的簇來改善“熱區(qū)”問題,但當簇規(guī)模過大時,簇頭的選舉不當也會使簇內(nèi)節(jié)點的能量消耗過快,從而影響網(wǎng)絡的生存周期。文獻[8]是在LEACH分簇算法基礎上,利用PSO優(yōu)化一個比較理想的簇頭來實現(xiàn)能耗較少,但由于簇頭任務過重,易造成能耗過快消失,加速網(wǎng)絡死亡。文獻[9]提出了雙簇頭的方法,主簇頭根據(jù)節(jié)點間的最大連通度和能量來選擇,相對于單簇頭,能有效減小簇頭負載,但廣播信息較多,能耗較大。

針對上述問題,本文提出了一種基于PSO的非均勻分簇雙簇頭路由算法(PSO-NUDC)。首先通過候選簇頭節(jié)點與基站距離的遠近構(gòu)造出幾何規(guī)模不等的簇,然后在規(guī)模較大的簇內(nèi)采用PSO優(yōu)化算法重新選擇主副簇頭,主簇頭主要完成簇內(nèi)節(jié)點數(shù)據(jù)的采集跟數(shù)據(jù)融合的任務,副簇頭主要負責簇內(nèi)及簇間數(shù)據(jù)轉(zhuǎn)發(fā),實現(xiàn)數(shù)據(jù)的多跳傳輸。

1.2 PSO算法

粒子群優(yōu)化PSO(Particle Swarm Optimization)算法是由Eberhart博士和Kennedy博士提出,是一種模擬鳥類覓食的群智能優(yōu)化算法。在算法中,每一個優(yōu)化問題都是搜索空間一個粒子,所有的粒子都有一個被優(yōu)化的函數(shù)決定的適應值,每一個粒子還有一個速度決定著他們的方向跟距離,粒子跟隨當前的最優(yōu)粒子在解空間中搜索,不停的改變自己的方向以及速度大小。在這個過程中,開始粒子比較分散,逐漸匯成一群,直到找到最優(yōu)解[10-11]。

PSO優(yōu)化算法將粒子群初始化為一組隨機粒子(隨機解),所有粒子在搜索空間中通過迭代找到最優(yōu)解。在迭代過程中,粒子根據(jù)個體極值與全局極值不斷調(diào)整自己的位置,不斷更新。個體極值指的是一個是粒子本身找到的最優(yōu)解,而全局極值為目前整個群體找到的最優(yōu)解。通過找到兩個極值后,粒子由式(1)～式(2)來更新自己的位置。

vij(t+1)=wvij(t)+c1r1[pij-xij(t)]+c2r2[pij-xij(t)]

(1)

xij(t+1)=xij(t)+vij(t+1)

(2)

其中,c1、c2為加速系數(shù),用于控制粒子的運動速度;r1、r2是[0,1]里的隨機數(shù);w是權重系數(shù),用于控制粒子歷史值對當值的影響程度;vij(t)表示的是粒子i在第t次迭代過程中第j維的速度;xij(t)表示的是粒子i在第t次迭代過程中第j維的位置;pid(t)、pgd(t)分別為個體極值與全局極值。

2 PSO-NUDC算法

2.1 非均勻簇的建立階段

LEACH算法將單個節(jié)點的狀態(tài)作為簇頭選擇的度量標準,沒有考慮剩余能量平衡問題,為了避免能量低的節(jié)點成為簇頭,定義門限值τ如下:

(3)

式中,p是節(jié)點當選為簇頭的概率,r為當前循環(huán)的輪數(shù),En_max和E(ni)分別為節(jié)點的初始能量和當前能量,G是最近1/p輪當選為簇頭的節(jié)點集合。從式(3)中可以看出,當選過的節(jié)點在接下來的1/p輪內(nèi)不能成為簇頭。網(wǎng)絡初始化時,每一個普通節(jié)點都生成一個隨機數(shù)μ(0<μ<1)。若μ<τ,則該節(jié)點成為候選簇頭節(jié)點;非候選簇頭節(jié)點將進入休眠狀態(tài),直至初始簇頭競選過程結(jié)束。同時,通過候選簇頭節(jié)點設置的競爭范圍Rc[12]來控制簇在網(wǎng)絡中分布。距離基站越近的簇的幾何半徑越小,簇的個數(shù)越多,以解決“熱區(qū)”問題,相反的,離基站越遠的簇的幾何半徑也越大,簇的個數(shù)越小,以平衡網(wǎng)絡節(jié)點能量。由此可見候選簇頭節(jié)點的競爭半徑與基站的距離成正比例關系。假設Si為一個候選簇頭節(jié)點,其競爭半徑Rc為

(4)

2.2 PSO優(yōu)化主副簇頭選取階段

非均勻分簇階段完成后,根據(jù)簇幾何規(guī)模的大小引進PSO算法選取最終的主副簇頭以減少算法的復雜度。設定一個門限制k,當簇半徑大于門限值k時,將運用PSO選取最終的主副簇頭;當簇半徑小于門限值k時,初始主副簇頭將直接轉(zhuǎn)變?yōu)樽罱K簇頭。

為使原PSO適用于本問題,需將原PSO中的式(1)和式(2)進行改進,并得出一個合適的適應值函數(shù)fit(x)。

假設n個網(wǎng)絡節(jié)點處于平面坐標內(nèi),網(wǎng)絡節(jié)點i的位置xid和速度vid分別由x,y兩個方向上的分量決定。所以式(1)被具體化為式(5)和式(6):

xxid(t)=xxid(t-1)+vxid(t)

(5)

xyid(t)=xyid(t-1)+vyid(t)

(6)

式(2)被具體化為式(7)和(8)

vxid(t)=wvxid(t-1)+c1r1[pid-xxid(t-1)]+
c2r2[pgd-xxid(t-1)]

(7)

vyid(t)=wvyid(t-1)+c1r1[pid-xyid(t-1)]+
c2r2[pgd-xyid(t-1)]

(8)

由于網(wǎng)絡節(jié)點是離散分布的,由式(5)～式(6)計算所得出的位置無法一一映射到相應的實際節(jié)點,因此需要進行調(diào)整,xxid(t)∈{px1,px2,…,pxn},xyid(t)∈{py1,py2,…,pyn},其中pxi和pyi分別為簇內(nèi)節(jié)點上的x分量與y分量。

設Δpxi是xxid(t)跟i節(jié)點上的x分量差的絕對值,Δpyi是xyid(t)跟i節(jié)點上的y分量差的絕對值:

Δpxi=|xxid(t)-pxi|

(9)

Δpyi=|xyid(t)-pyi|

(10)

則:

(11)

Δpk=min(Δp1,Δp2,…,Δpn)

(12)

可以得出第k個節(jié)點的位置同xid(t)最為接近,所以調(diào)整后的值為

xxid(t)≈pxk

(13)

xyid(t)≈pyk

(14)

即搜索點現(xiàn)在位于節(jié)點k的位置上。

適應值函數(shù)的確定是PSO算法中的一個重要的問題。適應值函數(shù)設定的理想程度直接決定了最終選取主副簇頭的優(yōu)劣。主簇頭節(jié)點的適應值函數(shù)的確定要考慮兩個方面,一方面是主簇頭節(jié)點能量問題,這主要是主簇頭節(jié)點負責數(shù)據(jù)收集跟轉(zhuǎn)發(fā)任務,要比簇內(nèi)節(jié)點消耗更多能量;另一方面是簇頭節(jié)點離簇內(nèi)節(jié)點的距離問題,由于主簇頭節(jié)點主要負責收集簇內(nèi)節(jié)點的信息,因此主簇頭節(jié)點與簇內(nèi)節(jié)點之間的平均距離越小越好。

考慮上述因素,可以采用下面的適應函數(shù)f:

f=ε×f1+(1-ε)f2

(15)

(16)

(17)

其中,m是簇內(nèi)節(jié)點個數(shù);E(ni)是節(jié)點ni的能量;f1是主簇頭節(jié)點能量占簇內(nèi)節(jié)點能量的多少;f2是簇內(nèi)節(jié)點到主簇頭的平均距離的倒數(shù);di to H是節(jié)點i到主簇頭的距離。

由此可見,f1表示是使主簇頭具有更多的能量,而f2表示的是使主簇頭到簇內(nèi)節(jié)點的平均距離最小。而由ε可以調(diào)節(jié)適應函數(shù)f中f1和f2所占的比重。選擇使f值最大的節(jié)點作為主簇頭。

對于副簇頭,其任務是將數(shù)據(jù)傳輸至基站,因此它不僅需要具有較高的能量,而且距離基站越近越好。基于以上原因,副簇頭的選取應采用下面的適應值函數(shù)g:

g=λg1+(1-λ)g2

(18)

(19)

(20)

其中,g1與式(16)中f1一樣,是指副簇頭節(jié)點能量占簇內(nèi)節(jié)點總能量的比例;dH to BS是副簇頭到基站的距離;di to BS是節(jié)點i到基站的距離;g2則表示副簇頭到基站的距離占簇內(nèi)節(jié)點到基站距離總和的比例。g2越大則表示副簇頭離基站也越近。由λ調(diào)節(jié)適應函數(shù)g中g1與g2所占比重,選擇使g值最大的節(jié)點為副簇頭。

簇內(nèi)應用PSO優(yōu)化算法選取主簇頭流程圖如圖1所示,基本步驟如下:①初始化粒子群。在簇內(nèi)隨機初始化粒子i的位置xxid(t)、xyid(t)與速度vxid(t)、vyid(t),由式(9)～式(14)對粒子的位置進行調(diào)整;②由式(15)～式(17)得出適應值f,并且令粒子的個體極值pid=粒子當前位置,全局極值pgd=取得最大適應值的粒子的位置;③由式(5)～式(8)對每個粒子的位置xxid(t)、xyid(t)與速度vxid(t)、vyid(t)進行更新,并由式(9)～式(14)對粒子的位置進行調(diào)整;④由式(15)～式(17)得出各個粒子的適應值f,同時更新個體極值與全局極值;⑤重復步驟③～步驟④,直到達到最大的迭代次數(shù)為止,選擇最優(yōu)解對應的節(jié)點為主簇頭;⑥根據(jù)副簇頭適應值函數(shù)式,重復以上操作,選擇最優(yōu)解對應的節(jié)點為副簇頭。

圖1 基于PSO優(yōu)化選擇主簇頭的流程

2.3 多跳傳輸

在數(shù)據(jù)傳輸階段,副簇頭接收來自主簇頭的數(shù)據(jù)后,將根據(jù)自身離匯聚節(jié)點的距離選擇單跳或多跳傳輸至基站。在數(shù)據(jù)傳輸開始階段,每個副簇頭向全網(wǎng)廣播消息,包含其ID、當前剩余能量和距匯聚點的距離。副簇頭Si收到副簇頭Sj廣播的消息后,可以計算出它們之間的近似距離。假設Si選擇Sj作為數(shù)據(jù)轉(zhuǎn)發(fā)副簇頭,并且Sj直接將lbit數(shù)據(jù)傳輸給基站,采用文獻[13]所提出的一階無線通信能耗模型,根據(jù)能耗公式得:

(21)

(22)

其中,α可根據(jù)具體的應用環(huán)境進行設置;當Si選擇剩余能量大于自身,并且到基站的通信開銷低于Si的副簇頭Sj為下一跳路由。各個副簇頭從Wnext大于1的副簇頭中選擇權值最大的副簇頭為下一跳節(jié)點,進而形成到基站的多跳路由路徑,Wnext最大的節(jié)點將收集的監(jiān)測數(shù)據(jù)傳輸給基站。如果副簇頭找不到Wnext大于 1的下一跳節(jié)點,則該副簇頭節(jié)點就直接與基站進行單跳數(shù)據(jù)傳輸。這樣就形成了副簇頭到基站的單跳與多跳相結(jié)合的路由路徑。

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

3.1 仿真環(huán)境

本文采用MATLAB仿真平臺,如圖2所示將200個傳感器節(jié)點均勻散布在200 m×200 m網(wǎng)絡中,基站位于0 m,100 m。每個節(jié)點的初始能量為0.5 J,控制包大小為100 byte,數(shù)據(jù)包大小為4000 byte,門限值τ為0.4,PSO優(yōu)化算法的各參數(shù)為:ε=0.6,εfs=10 pJ/(b·m-2),εamp=0.0013 pJ/(b·m-4),λ=0.3,c1=c2=2,w=0.9,α=0.4,Eelec=50 nJ/bit。

圖2 節(jié)點分布圖

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

為了對PSO-NUDC算法的有效性跟可用性進行評估,將其與文獻[4]中的LEACH算法和文獻[7]中的EEUC算法進行仿真對比,以不同輪中簇頭節(jié)點的能耗之和、網(wǎng)絡的生存周期和網(wǎng)絡剩余總能量為評價標準。

圖3為3種算法的簇頭節(jié)點在不同輪中能耗之和的對比。為了減小實驗的偶然性,在前50輪中每隔5輪進行一次能耗對比。從圖(3)可以看出,PSO-NUDC算法的簇頭節(jié)點能耗在0.01 J～0.05 J之間,并且較為平緩,遠遠好于EEUC與LEACH算法。這主要是由于PSO-NUDC算法根據(jù)簇頭的任務不同,選取最優(yōu)主簇頭負責數(shù)據(jù)的收集與融合,最優(yōu)副簇頭通過多跳負責數(shù)據(jù)的轉(zhuǎn)發(fā),有效的減輕了簇頭負載,而LEACH算法的簇頭是隨機產(chǎn)生,并且采用單跳與基站傳輸數(shù)據(jù),離基站較遠的簇頭由于能量消耗過大會導致過早死亡。

圖3 每輪簇頭能耗總和比較

網(wǎng)絡的生存周期是衡量傳感器網(wǎng)絡質(zhì)量的一個重要指標,本文以第1個節(jié)點死亡時間作為網(wǎng)絡生命周期的評價標準。由圖4可以看出,LEACH算法第1個節(jié)點死亡出現(xiàn)在第147輪,EEUC算法出現(xiàn)在第324輪,PSO-NUDC算法出現(xiàn)在第564輪。其中,PSO-NUDC算法與LEACH算法和EEUC算法相比,網(wǎng)絡生存周期分別延長了41.7 %和24 %。這是因為PSO-NUDC算法中非均勻簇的建立以及最優(yōu)主副簇頭的不同分工可以更有效的均衡簇內(nèi)和簇間的能耗。

圖4 網(wǎng)絡剩余存活節(jié)點數(shù)

圖5 網(wǎng)絡總能耗

較小的坡度表示了總能量消耗的較慢跟較長的生存周期,由圖5可以看出,PSO-NUDC算法的坡度明顯小于其余兩種。在第400輪時,PSO-NUDC算法的剩余能量比較LEACH算法與EEUC算法分別增加了39.58 %和15.52 %。非均勻簇的建立以及利用PSO選擇最優(yōu)主副簇頭能夠更好的提高整個網(wǎng)絡的能量使用效率。

通過MATLAB仿真與LEACH算法、EEUC算法相比可以看出,PSO-NUDC算法能夠更好的提高能量使用效率,顯著的延長網(wǎng)絡的生存周期。

4 結(jié)論

針對WSN網(wǎng)絡中分簇路由算法的不足,本文提出了一種基于PSO的非均勻分簇雙簇頭路由算法。該算法通過MATLAB仿真實驗與其他算法比較表明,PSO-NUDC算法較好的改善了“熱區(qū)”問題,副簇頭的存在減輕了主簇頭的能量消耗,更好的均衡了整個網(wǎng)絡的能量能耗,延長網(wǎng)絡的生存周期。但是在一些比較小的簇里面,沒有必要設置副簇頭。因此今后的重點是研究簇頭數(shù)目的彈性設置問題以及算法中各參數(shù)的選擇對結(jié)果的影響問題。

[1] 彭力. 無線傳感器網(wǎng)絡技術[M]. 北京:冶金工業(yè)出版社,2011:1-5.

[2]唐勇,周明天,張欣. 無線傳感器網(wǎng)絡路由協(xié)議研究進展[J]. 軟件學報,2006,17(3):410-421.

[3]宮鵬. 無線傳感器網(wǎng)絡技術環(huán)境應用進展[J]. 遙感學報,2010,14(2):387-388.

[4]Heinzelman W,Chandrakasan A,Balakrishnan H. Energy Efficient Communication Protocol for Wireless Microsensor Networks[C]//Proceedings of the 33rd Hawaii International Conference on System Sciences. Maui:IEEE Inc,2000:3005-3014.

[5]陸立芳,閆建國. 無線傳感器網(wǎng)絡路由協(xié)議的優(yōu)化設計[J]. 計算機仿真,2010,27(12):125-128.

[6]Ye Mao,Li Chengfa,Chen Guihai,et al. EECS:An Energy Efficient Clustering Scheme in Wireless Sensor Networks[C]//Proceedings of 24th IEEE International Performance Computing and Communi-cations Conference(IPCCC). Phoenix,USA:IEEE Inc,2005:535-540.

[7]李成法,陳貴海,葉懋,等. 一種基于非均勻分簇的無線傳感器網(wǎng)絡路由協(xié)議[J]. 計算機學報,2007,30(1):27-36.

[8]劉志坤,劉忠,李朝旭. 基于混沌粒子群優(yōu)化的無線傳感器網(wǎng)絡分簇路由協(xié)議[J]. 傳感技術學報,2011,24(10):1459-1463.

[9]徐丹丹,章勇. 一種基于最大連通度的雙簇頭分簇算法[J]. 傳感技術學報,2008,21(11):1909-1912.

[10]蔣暢江,石為人,向敏,等. 基于PSO的無線傳感器網(wǎng)絡節(jié)能分簇協(xié)議[J]. 計算機工程,2010,36(8):15-17.

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

[12]鄒杰,史長瓊,姬文燕. 基于粒子群優(yōu)化的非均勻分簇路由算法[J]. 計算機應用,2012,32(1):131-133.

[13]Heinzelman W R. An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communications,2002,4(1):660-670.

門順治(1988-)男,山東煙臺人,碩士研究生,研究方向為計算機控制,傳感器網(wǎng)絡應用;

孫順遠(1984-),男,博士研究生,主要從事計算機控制,無線傳感網(wǎng)絡應用方面研究;

徐保國(1951-)男,教授,博士生導師,主要研究方向為過程控制、智能儀表及現(xiàn)場總線網(wǎng)絡等。

WirelessSensorNetworksNon-UniformClusteringandDclusterHeadsRoutingAlgorithmBasedonPSO*

MENShunzhi,SUNShunyuan,XUBaoguo*

(School of IOT Engineering,JiangNan University,WuXi Jiangsu 214122,China)

Because cluster heads of clustering routing algorithm have heave load in wireless sensor network(WSN),and in order to improve the energy efficiency in WSN,this paper proposes non-uniform clustering and double cluster heads routing algorithm based on PSO. Firstly,the proposed algorithm construct clusters with different geometric sizes according to the distance from the base station,then introduce PSO optimization algorithm according to the size of the cluster. The main cluster head is responsible for collecting the node data and data fusion,the deputy cluster heads is mainly completed the tasks of forwarding data between cluster and cluster,and the deputy cluster achieve multiple hop transmission of data. The simulation results show that the algorithm is effective to reduce the energy consumption of cluster head nodes,balance the energy consumption of the entire network in a large part,and prolong the life cycle of network.

Wireless Sensor Network(WSN);non-uniform clustering routing;Particle Swarm Optimization(PSO)algorithm;double cluster heads

項目來源:國家自然科學基金項目(21206053,21276111);中國博士后基金項目(2012M511678)

2014-04-16修改日期:2014-07-30

10.3969/j.issn.1004-1699.2014.09.022

TP393

:A

:1004-1699(2014)09-1281-06