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

門順治,孫順遠,徐保國

(江南大學物聯網工程學院,江蘇 無錫 214122)

?

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

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

(江南大學物聯網工程學院,江蘇 無錫 214122)

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

無線傳感器網絡;非均勻分簇;粒子群優化算法;雙簇頭

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

1 相關工作

1.1 分簇算法的論述

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

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

1.2 PSO算法

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

PSO優化算法將粒子群初始化為一組隨機粒子(隨機解),所有粒子在搜索空間中通過迭代找到最優解。在迭代過程中,粒子根據個體極值與全局極值不斷調整自己的位置,不斷更新。個體極值指的是一個是粒子本身找到的最優解,而全局極值為目前整個群體找到的最優解。通過找到兩個極值后,粒子由式(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為加速系數,用于控制粒子的運動速度;r1、r2是[0,1]里的隨機數;w是權重系數,用于控制粒子歷史值對當值的影響程度;vij(t)表示的是粒子i在第t次迭代過程中第j維的速度;xij(t)表示的是粒子i在第t次迭代過程中第j維的位置;pid(t)、pgd(t)分別為個體極值與全局極值。

2 PSO-NUDC算法

2.1 非均勻簇的建立階段

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

(3)

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

(4)

2.2 PSO優化主副簇頭選取階段

非均勻分簇階段完成后,根據簇幾何規模的大小引進PSO算法選取最終的主副簇頭以減少算法的復雜度。設定一個門限制k,當簇半徑大于門限值k時,將運用PSO選取最終的主副簇頭;當簇半徑小于門限值k時,初始主副簇頭將直接轉變為最終簇頭。

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

假設n個網絡節點處于平面坐標內,網絡節點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)

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

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

Δpxi=|xxid(t)-pxi|

(9)

Δpyi=|xyid(t)-pyi|

(10)

則:

(11)

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

(12)

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

xxid(t)≈pxk

(13)

xyid(t)≈pyk

(14)

即搜索點現在位于節點k的位置上。

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

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

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

(15)

(16)

(17)

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

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

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

g=λg1+(1-λ)g2

(18)

(19)

(20)

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

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

圖1 基于PSO優化選擇主簇頭的流程

2.3 多跳傳輸

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

(21)

(22)

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

3 仿真結果及分析

3.1 仿真環境

本文采用MATLAB仿真平臺,如圖2所示將200個傳感器節點均勻散布在200 m×200 m網絡中,基站位于0 m,100 m。每個節點的初始能量為0.5 J,控制包大小為100 byte,數據包大小為4000 byte,門限值τ為0.4,PSO優化算法的各參數為:ε=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 節點分布圖

3.2 仿真結果及分析

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

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

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

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

圖4 網絡剩余存活節點數

圖5 網絡總能耗

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

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

4 結論

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

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

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

[3]宮鵬. 無線傳感器網絡技術環境應用進展[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]陸立芳,閆建國. 無線傳感器網絡路由協議的優化設計[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]李成法,陳貴海,葉懋,等. 一種基于非均勻分簇的無線傳感器網絡路由協議[J]. 計算機學報,2007,30(1):27-36.

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

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

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

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

[12]鄒杰,史長瓊,姬文燕. 基于粒子群優化的非均勻分簇路由算法[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-)男,山東煙臺人,碩士研究生,研究方向為計算機控制,傳感器網絡應用;

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

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

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