張玉蘭 郭曉惠
【摘 要】針對無線傳感器網絡中能量消耗不均引起的熱區(qū)問題,提出一種基于移動sink節(jié)點的WSN節(jié)能路由協(xié)議MSERP,將整個網絡分成若干個虛擬網格,根據(jù)節(jié)點剩余能量和到網格重心距離選舉簇頭。通過PSO算法來確定sink的下一個移動位置,粒子適應值函數(shù)由簇頭到sink節(jié)點的距離和sink節(jié)點周圍簇頭能量因素定義。仿真結果表明,該協(xié)議有效地解決了熱區(qū)問題,提高了網絡的生存周期。
【關鍵詞】無線傳感器網絡;熱區(qū)問題;移動sink節(jié)點;PSO算法
中圖分類號: TP212.9 文獻標識碼: A 文章編號: 2095-2457(2017)26-0010-002
Based on the Mobile Sink Node of WSN Energy-efficient Routing Protocol
ZHANG Yu-lan GUO Xiao-hui
(School of Computer Engineering,Chongqing College of Humanities, Science & Technology, Chongqing 401524, China)
【Abstract】WSN energy-efficient routing protocol based on a mobile sink node of (MSERP) was proposed in this paper. The whole network was divided into some virtual unit,which choose cluster heads according to the residual energy and the distance of a node and a virtual unit of center. The next stay the best location of the sink is determined by PSO algorithm. The definition of the fitness function of particle is based on two factors: the distance of cluster heads to sink and the energy of cluster heads around the sink. Simulation results demonstrate that the protocol can efficiently solve the hot spot problem and prolong the network lifetime.
【Key words】Wireless Sensor Networks (WSN); Hot spot problem; A mobile sink; PSO algorithm
0 引言
傳統(tǒng)的無線傳感器網絡分簇算法,sink保持靜止,距離sink越近的節(jié)點由于需要轉發(fā)更多的數(shù)據(jù)而過早死亡,容易出現(xiàn)“熱區(qū)”問題。分簇算法中較為典型的有LEACH、HEED、PEGASIS等。為了解決“熱區(qū)”問題,延長網絡生存周期,提出了一系列策略,如非均勻分簇路由協(xié)議[1]。然而,由于sink節(jié)點保持靜止,周圍的節(jié)點沒有改變,不能在根本上解決該問題。針對以上情況。Luo等人[2]提出了引入移動的sink節(jié)點,連續(xù)改變sink節(jié)點周圍的節(jié)點避免“熱區(qū)”。根據(jù) sink節(jié)點移動路徑的確定性大致可以分為三類:隨機移動策略[3],sink節(jié)點隨機選擇下一個移動位置,但sink節(jié)點頻繁的廣播位置信息,導致能量消耗較大;sink節(jié)點按照預先設定好的路徑移動[4],雖然降低網絡的能耗,但不合適大規(guī)模網絡的應用;sink動態(tài)選擇移動路徑策略[5],根據(jù)網絡中的某些參數(shù)決定sink的下一個移動位置,但算法較為復雜。
本文提出基于移動sink節(jié)點的WSN路由協(xié)議(MSERP)解決熱區(qū)問題。本協(xié)議把網絡劃分為若干個虛擬單元,通過PSO算法確定sink下一個移動位置,利用sink的移動性,從而平衡了網絡的能耗,延長網絡生命周期。
1 算法描述
1.1 PSO算法
粒子群優(yōu)化算法是一種基于群智能方法的演化計算技術。假設在D維空間中位置表示為向量第i個粒子經歷過的最佳位置為向量Pi=(pg1,pg2,…,pgd),每個粒子飛行速度為向量Vi=(vi1,vi1,…vid),i=1,2,…,m,所有粒子經歷的最佳位置為Pg=(pg1,pg2,…,pgd),每一代粒子根據(jù)公式(1)更新速度:
vid=wvid+c1r1(pid-xid)+c2r2(pgd-xid)(1)
式中,w為慣性系數(shù);c1和c2為學習因子;r1和r2是[0,1]之間的隨機數(shù)。
1.2 MSERP算法
將整個無線傳感器網絡劃分為有唯一ID編號的虛擬單元格,即簇。選取區(qū)域的重心坐標(Xg,Yg)擔任每個虛擬單元格節(jié)點簇頭。 該坐標滿足單元格內的任意節(jié)點到它的距離之和最小。
簇頭的評判模型定義為:
f=βf +φf +?酌f ,first round;?鄣f +βf +φf +?酌f ,otherwise.(2)
其中:fe反映能量對節(jié)點擔任簇頭的重要程度;fd反映了節(jié)點到網格重心的距離對節(jié)點擔任簇頭的重要程度;參數(shù)fn和fen進一步避免網絡陷入“熱區(qū)”問題。
簇頭選舉具體過程如下:(1)網絡初始化,完成網絡的劃分,每個節(jié)點計算出所屬的網格號;(2)根據(jù)(5)完成簇頭的選舉。每個網格選擇 值最大的節(jié)點擔任簇頭;(3)每輪完成時,每個節(jié)點把剩余能量發(fā)送到簇頭,簇頭根據(jù)(5)選舉下一輪簇頭。endprint
2 sink節(jié)點移動過程
網絡在完成分簇和簇頭的選擇后,各個簇頭發(fā)送能量信息和所在 編號到sink節(jié)點。接著判斷是否滿足sink節(jié)點的移動條件,若滿足執(zhí)行PSO算法,確定sink節(jié)點的下一位置;若不滿足條件,則sink的位置保持不變。
2.1 sink節(jié)點移動條件
基于每個簇頭的能量信息,sink 計算整個網絡所有簇頭的能量平均值。sink節(jié)點移動條件:sink節(jié)點周圍簇頭(到sink節(jié)點一跳)的能量低于整個網絡平均簇頭的能量。
2.2 sink位置的確定
本文協(xié)議應用PSO算法來最優(yōu)化sink節(jié)點位置,提高網絡的壽命。sink節(jié)點下一位置應滿足,所有簇頭到sink節(jié)點的距離之和及方差最??;sink節(jié)點周圍簇頭能量之和最大且方差最小。
sink節(jié)點執(zhí)行PSO 算法確定下一個停留位置,目標函數(shù)定義為:
cost=?鄣1f1+?鄣2f2+?鄣3f3+?鄣4f4(3)
式中:所有簇頭到sink節(jié)點的歐氏距離之和為f1,方差為f2;f3為當前所有節(jié)點能量之和除以sink節(jié)點周圍簇頭的能量之和;f4為sink周圍簇頭能量方差;?鄣1+?鄣2+?鄣3+?鄣4=1。最小的函數(shù)值即為sink節(jié)點的下一個最佳位置。
sink移動算法具體步驟:(1)初始化Q個粒子,每個粒子代表sink節(jié)點可能的下一個位置;(2)運用式(3)-(7)計算粒子適應值;(3)確定每個粒子最優(yōu)解和種群的的最優(yōu)解;(4)利用式(1)更新粒子的速度和位置;(5)根據(jù)上一次sink節(jié)點的位置調整粒子位置;(6)重復步驟(2)-(5),至最大循環(huán)次數(shù)。
2.3 sink節(jié)點信息發(fā)布
sink節(jié)點移動到確定的位置后,發(fā)布它的位置信息到所在單元格的簇頭,然后由該簇頭轉發(fā)給其他簇頭。sink節(jié)點位置更新避免了洪泛過程,有效的節(jié)約了能量。穩(wěn)態(tài)階段簇頭首先完成簇內數(shù)據(jù)采集、融合的任務,然后經簇間多跳路由傳遞數(shù)據(jù)至sink節(jié)點。
3 能量模型
3.1 無線通信能耗模型
本文采用一階無線通信模型,無線通信模塊具有功率控制能力,能夠以最小的能量將數(shù)據(jù)發(fā)送給希望的接收者。在保證合理信噪比條件下,節(jié)點發(fā)送數(shù)據(jù)能耗如式(4):
EIx(k,d)=E ×k+E ×k×d d
其中:k為發(fā)送的二進制位數(shù);d為發(fā)送距離;d0位發(fā)送距離門限值;Eelec為射頻能耗系數(shù);Efs和Eamp為不同信道傳播模型下的功率放大電路能耗系數(shù)。節(jié)點接收數(shù)據(jù)能耗如式(5):
ERx(k)=Eelec×k(5)
3.2 數(shù)據(jù)融合模型
數(shù)據(jù)融合模型假設為:簇頭接收每個節(jié)點發(fā)送的kbit數(shù)據(jù),無論簇內節(jié)點數(shù)目多少,均壓縮為kbit數(shù)據(jù)。數(shù)據(jù)融合的能耗設定為ED=5nJ/bit。
4 仿真分析
為了驗證本文提出的協(xié)議的有效性,利用MATLAB生成了100節(jié)點隨機部署在100m×100m范圍內。仿真中對比了EBRP,DCSR和MSERP三種協(xié)議。
圖1為這3種協(xié)議的節(jié)點死亡對比圖。從該圖中可以看出:MSERP協(xié)議的網絡壽命長于EBRP和DCSR。EBRP和EBRP協(xié)議在1000輪時開始出現(xiàn)節(jié)點死亡。而MSERP協(xié)議在1500附近才開始有節(jié)點死亡,說明本協(xié)議的能耗更加均勻。3種協(xié)議在1700輪時, MSERP協(xié)議節(jié)點死亡分布均勻,而EBRP和DCSR死亡節(jié)點集中,出現(xiàn)了“熱區(qū)”問題。在使用移動sink節(jié)點3種策略中,DCSR由于協(xié)議按照固定路徑移動,路徑附近節(jié)點死亡較多;EBRP由于隨機移動,路線不夠合理,會出現(xiàn)部分節(jié)點過早死亡。
5 結論
本協(xié)議通過對網絡劃分和簇頭選擇,應用PSO算法對sink節(jié)點位置進行優(yōu)化,通過一群粒子在解空間中逐代搜索,尋找sink最優(yōu)位置。仿真實驗證明,與EBRP和DCSR協(xié)議相比,該協(xié)議能夠有效均能網絡能耗,降低節(jié)點死亡速度,從而提高網絡壽命。
【參考文獻】
[1]黃廷輝,伊凱,崔更申,等.基于非均勻分簇的無線傳感器網絡分層路由協(xié)議[J].計算機應用.2016,36(1):66-71.
[2]Luo J,Huang J P,Joint Mobility and R-outing for Lifetime Elongation in Wir-eless Sensor Networks[C]//Pro-ceedings IEEE information 2005, Miami, FL, United- states. 2005, 3:1735-46.
[3]鐘智,羅大庸,劉少強.具有移動sink的無線傳感器網絡能量均衡分簇路由協(xié)議[J].控制與決策.2012,27(8):1211-1115.
[4]郭劍,孫力娟,許文君.基于移動sink的無線傳感器網絡數(shù)據(jù)采集方案[J].通信學報.2012,33(9):176-184.
[5]林志貴,王璽,趙可.帶移動sink節(jié)點的WSN節(jié)能路由算法[J].計算機科學.2014,41(11):199-203.