檀 爽,毛永毅
(西安郵電大學(xué)電子工程學(xué)院,西安 710061)
信息的采集、傳輸、處理是無線傳感器網(wǎng)絡(luò)中3個(gè)重要過程,在眾多領(lǐng)域能夠?qū)崿F(xiàn)大規(guī)模的跟蹤和監(jiān)測(cè)任務(wù),在這過程中節(jié)點(diǎn)的位置尤其重要[1]?,F(xiàn)階段,在無線傳感器網(wǎng)絡(luò)定位技術(shù)中,根據(jù)定位算法是否需要通過測(cè)距,將定位算法分為基于測(cè)距的和無需測(cè)距的兩種[2]。基于測(cè)距的定位算法需要額外的硬件支持來配置,而無需測(cè)距的定位算法只需要網(wǎng)絡(luò)之間的連通性和錨節(jié)點(diǎn)信息就能估算出未知節(jié)點(diǎn)的信息,該算法成本較低,硬件設(shè)備簡(jiǎn)單,功耗較小。與距離無關(guān)的典型的定位算法主要包括:質(zhì)心算法[3]、凸規(guī)劃算法和DV_Hop算法[4]等。許多學(xué)者對(duì)此進(jìn)行了大量研究與改進(jìn)。文獻(xiàn)[5]提出了一種帶權(quán)重的改進(jìn)平均跳距與改進(jìn)PSO算法來改進(jìn)DV_Hop算法。文獻(xiàn)[6]得到最優(yōu)解是通過差分進(jìn)化算法優(yōu)化適應(yīng)度函數(shù)以減小定位誤差。文獻(xiàn)[7]提出一種基于CS(Cuckoo Search)算法的WSN(Wireless Sensor Network)節(jié)點(diǎn)定位算法,利用CS算法替代在DV_Hop算法中求解未知節(jié)點(diǎn)坐標(biāo)階段所采用的最小二乘法。文獻(xiàn)[8]通過改進(jìn)PSO算法優(yōu)化DV_Hop算法,并引入收縮因子加快收斂速度和提高定位精度,從而找到最優(yōu)位置。
本文提出一種基于最優(yōu)跳距與LevyPSO算法的WSN節(jié)點(diǎn)定位算法,即OLPDV_Hop定位算法。仿真結(jié)果表明,OLPDV_Hop算法在定位精度上相比于DV_Hop算法、文獻(xiàn)[5]算法和文獻(xiàn)[8]的算法均有所提高,同時(shí)也無需增加額外成本。
DV_Hop算法是由Niculescu等人提出的,利用跳數(shù)和平均每跳距離的乘積來估算未知節(jié)點(diǎn)和錨節(jié)點(diǎn)之間距離,進(jìn)而通過極大似然估計(jì)法或三邊定位法得到未知節(jié)點(diǎn)位置。具體分為3個(gè)階段:
第1階段 跳數(shù)估計(jì)
通過距離矢量交換,網(wǎng)絡(luò)中所有節(jié)點(diǎn)獲得距離錨節(jié)點(diǎn)的跳數(shù)等信息。即錨節(jié)點(diǎn)以洪泛的形式向其他鄰居節(jié)點(diǎn)發(fā)送數(shù)據(jù)包,這個(gè)數(shù)據(jù)包中包括錨節(jié)點(diǎn)到接收信息節(jié)點(diǎn)的跳數(shù)、錨節(jié)點(diǎn)的標(biāo)識(shí)、坐標(biāo)。為保證未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的跳數(shù)最小,當(dāng)未知節(jié)點(diǎn)接收到同一個(gè)錨節(jié)點(diǎn)的多個(gè)數(shù)據(jù)包時(shí),只保留跳數(shù)最小的數(shù)據(jù)包。
第2階段 距離估計(jì)
每個(gè)錨節(jié)點(diǎn)根據(jù)所記錄的其他信標(biāo)節(jié)點(diǎn)的跳數(shù)和坐標(biāo)信息,根據(jù)式(1)估計(jì)平均每跳距離:
(1)
式中:(xi,yi),(xj,yj)是信標(biāo)節(jié)點(diǎn)i,j的坐標(biāo),hij是信標(biāo)節(jié)點(diǎn)i,j之間的最小跳數(shù)。
第3階段 位置估計(jì)
通過未知節(jié)點(diǎn)和錨節(jié)點(diǎn)的距離,挑選3個(gè)錨節(jié)點(diǎn)利用三邊定位算法求得未知節(jié)點(diǎn)坐標(biāo),也可以通過極大似然估計(jì)實(shí)現(xiàn)未知節(jié)點(diǎn)的定位。
1.2.1 平均跳距修正
節(jié)點(diǎn)間估計(jì)距離是通過跳數(shù)值和平均跳距的乘積所得到的,因此平均跳距的誤差直接影響估計(jì)距離的精確度。為了使誤差減小,利用錨節(jié)點(diǎn)間單跳平均誤差修正平均跳距,使其接近真實(shí)值,進(jìn)而使距離得以優(yōu)化。
(2)
(3)
因此可以通過式(2)和式(3)的差值可以求得錨節(jié)點(diǎn)i和j之間的距離誤差,如式(4)所示
(4)
錨節(jié)點(diǎn)i的單跳平均誤差可以通過式(5)求出,其中n為錨節(jié)點(diǎn)個(gè)數(shù)。
(5)
最后通過式(6)修正平均跳距,如式(6)所示:
(6)
1.2.2 多錨節(jié)點(diǎn)平均跳距估計(jì)距離
在估計(jì)節(jié)點(diǎn)間距離階段,待求未知節(jié)點(diǎn)
根據(jù)就近原則只接收錨節(jié)點(diǎn)傳遞過來的第1個(gè)平均跳距信息。而網(wǎng)絡(luò)分布是隨機(jī)的,數(shù)據(jù)選擇的單一性必然增加了偶然性,進(jìn)而影響后期定位。求到哪點(diǎn)的估計(jì)距離就用該點(diǎn)的平均跳距不僅可以考慮到全局信息,而且會(huì)在一定程度上降低偶然性,從而使定位精度有所提高。
各節(jié)點(diǎn)間平均跳距如下:
hopsizeA=(25+20)/(3+4)≈6.528 m
hopsizeB=(25+42)/(3+5)≈8.375 m
hopsizeC=(20+42)/(4+5)≈6.888 m
圖1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖
利用各節(jié)點(diǎn)平均跳距通過不同方法估算節(jié)點(diǎn)間距離,結(jié)果如表一所示。
觀察表1發(fā)現(xiàn),使用多錨節(jié)點(diǎn)平均跳距估計(jì)距離能使估計(jì)距離更接近真實(shí)值
表1 節(jié)點(diǎn)間實(shí)際距離與估計(jì)距離
粒子群優(yōu)化算法于1995年由Eberhart和Kennedy提出的[9],它模擬了魚類和鳥類在尋找食物方面的協(xié)作行為[10]。在PSO算法中,每個(gè)粒子表示優(yōu)化問題的潛在解決方案,而食物源的位置就是全局最優(yōu)解。PSO從隨機(jī)解出發(fā),具有快速收斂能力和優(yōu)異的全局搜索性能。
(7)
(8)
式中:w表示慣性權(quán)重,c1,c2為加速度常數(shù),r1,r2是[0,1]的隨機(jī)數(shù),pi表示第i個(gè)粒子的個(gè)體極值,pg表示整個(gè)粒子群的全局極值。
Levy飛行是由Levy提出,Benoist-Madelbrot描述的一種穩(wěn)定分布。大體上說,Levy飛行就是一種模擬動(dòng)物覓食的一種隨機(jī)游走過程。Levy飛行有如下特點(diǎn):
①具有統(tǒng)計(jì)的隨機(jī)分形與自相似性,即隨機(jī)變量本身與獨(dú)立同分布的隨機(jī)變量之和同分布。
②其服從“重尾”分布,即具有冪律漸進(jìn)性~|x|(-1-α)。
③就隨機(jī)分布與隨機(jī)變量而言,Levy飛行是極限的一種,其在鄰域范圍內(nèi)具有吸引力,當(dāng)系統(tǒng)的實(shí)現(xiàn)結(jié)果由大量隨機(jī)數(shù)之和決定時(shí),就會(huì)出現(xiàn)吸引,即其具有廣義中心極限定理。
④具有無限方差與均值。
PSO算法定位精度較低是由于在算法前期收斂速度較快但后期收斂速度逐漸變慢。其主要原因是當(dāng)PSO算法處于進(jìn)化停滯時(shí),粒子出現(xiàn)“聚焦”現(xiàn)象,種群失去多樣性,導(dǎo)致算法難以趨于全局最優(yōu),出現(xiàn)”早熟”[11]現(xiàn)象。許多學(xué)者針對(duì)此問題提出改進(jìn)策略,但這些都是通過調(diào)整式(7)中的參數(shù)w,c1,c2。雖然在不同程度上提高了定位精度,但并沒有從PSO算法收斂于局部極值的根本原因上采取措施。經(jīng)過研究發(fā)現(xiàn),Levy飛行能使粒子隨機(jī)游走經(jīng)歷新的搜索路徑,產(chǎn)生新解,從而增加種群的多樣性,避免容易陷入局部極值。
在PSO算法中速度項(xiàng)v受上代粒子的移動(dòng)方向影響較重而失去多樣性,從而容易陷入局部極值。另一方面也違背了Levy飛行的隨機(jī)游走理念。由此,本文采用式(9)更新粒子位置。
(9)
Levy飛行雖然可以解決局部收斂,但其并不一定能保證產(chǎn)生的新解一定優(yōu)于原來的解。由此本文提出一種貪婪的更新評(píng)價(jià)策略?;谪澙返母略u(píng)價(jià)策略能夠保證算法利用每一代最優(yōu)解引導(dǎo)算法進(jìn)行局部搜索,從而加快收斂速度并獲取更高質(zhì)量的解。令
(10)
(11)
因此式LevyPSO算法將(7)、式(8)改進(jìn)為
(12)
式中:α=α0(xi-pg)為步長(zhǎng)信息,α0為常數(shù)0.01;⊕表示點(diǎn)對(duì)點(diǎn)乘法;Levy(β)~|x|(-1-β)(0<β<2);fit(x)為x適應(yīng)度值,pg為全局最優(yōu)位置。
在DV_Hop定位算法中,估計(jì)距離dn通過最小跳數(shù)與估算平均跳距的乘積來替代,這會(huì)造成很大的誤差,所以通過最小二乘法求得的待定位節(jié)點(diǎn)坐標(biāo)精度較低,為了減小定位誤差影響,我們將問題轉(zhuǎn)換為dn的優(yōu)化問題。
設(shè)待定位節(jié)點(diǎn)D(x,y)到信標(biāo)節(jié)點(diǎn)A1,A2…,An的真實(shí)距離分別為r1,r2…rn,相應(yīng)的測(cè)距誤差為ε1,ε2…εn,則:
|ri-di|<εi
(13)
式(13)可改為
(14)
由式(13)可知,εi越小,所求得待定位節(jié)點(diǎn)的位置與其真實(shí)位置越接近。
(15)
當(dāng)適應(yīng)度函數(shù)fitness(x,y)取值最小時(shí),所求待定位節(jié)點(diǎn)位置與其真實(shí)位置最接近,定位誤差最小。
OLPDV_Hop算法流程如下:
Step 1 初始化網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)以及網(wǎng)絡(luò)區(qū)域大小,初始化LevyPSO算法各參數(shù)、粒子位置、最大迭代次數(shù)、種群規(guī)模。
Step 2 根據(jù)式(15)計(jì)算各粒子適應(yīng)度函數(shù),求出最優(yōu)適應(yīng)度fmin和當(dāng)前最好位置
Step 6 比較粒子當(dāng)前位置適應(yīng)度值與歷史最優(yōu)位置適應(yīng)度值,若當(dāng)前位置適應(yīng)度值小于歷史最優(yōu)位置適應(yīng)度值,則更新當(dāng)前位置為歷史最優(yōu)位置,否則保持歷史最優(yōu)位置不變。
Step 7 比較全局最優(yōu)位置適應(yīng)度值與歷史最優(yōu)位置適應(yīng)度值,若歷史最優(yōu)位置適應(yīng)度值小于全局最優(yōu)位置適應(yīng)度值,則更新全局最優(yōu)位置,否則保持全局最優(yōu)位置不變。
重復(fù)執(zhí)行Step 4~Step 7,直到達(dá)到最大迭代次數(shù),輸出最優(yōu)解。
為了驗(yàn)證OLPDV_Hop算法的性能,在Windows7的MATLABR2014a環(huán)境下分別對(duì)DV_Hop算法、IPSODV_Hop 算法和BDV_Hop算法進(jìn)行仿真比較與分析。本文采用文獻(xiàn)[12]提出的歸一化平均定位誤差作為算法性能的評(píng)價(jià)指標(biāo),如式(16)所示。
(16)
式中:(xr,yr)表示待定位節(jié)點(diǎn)的真實(shí)坐標(biāo),(xi,yi)表示待定位節(jié)點(diǎn)估計(jì)坐標(biāo),R表示節(jié)點(diǎn)通信半徑,k為待定位節(jié)點(diǎn)個(gè)數(shù)。
圖2為錨節(jié)點(diǎn)數(shù)為20,先后加入距離優(yōu)化和LevyPSO算法后,通信半徑從25 m~50 m平均定位誤差曲線圖。由圖可知,通信半徑為25 m~40 m時(shí)曲線都呈下降趨勢(shì),主要原因是網(wǎng)絡(luò)連通度的提升所導(dǎo)致。之后曲線逐漸上升,這是由于過大的通信半徑會(huì)導(dǎo)致平均定位誤差增大,因此不必一味追求過大通信半徑,應(yīng)適當(dāng)選取。由圖2可知,再加入距離優(yōu)化和LevyPSO算法后,平均定位誤差都呈下降趨勢(shì)。
圖2 不同通信半徑下平均定位誤差曲線圖
下面將OLPDV_Hop算法、DV_Hop算法、IPSODV_Hop算法和BDV_Hop算法分別在不同錨節(jié)點(diǎn)數(shù)和不同通信半徑下進(jìn)行仿真對(duì)比與分析。本文選取邊長(zhǎng)為100 m的正方形作為仿真區(qū)域,在相同參數(shù)下仿真100次,計(jì)算其均值并繪制出相應(yīng)的平均定位誤差曲線圖。
圖3 不同通信半徑下平均定位誤差曲線圖
①不同通信半徑
圖3為錨節(jié)點(diǎn)數(shù)為20%,節(jié)點(diǎn)總數(shù)為100個(gè),通信半徑為25 m~50 m不斷增加時(shí)4種算法的平均定位誤差變化曲線圖。由圖可知,當(dāng)錨節(jié)點(diǎn)數(shù)和節(jié)點(diǎn)總數(shù)一定時(shí),半徑為25 m~40 m,4種算法的平均定位誤差逐漸降低,而后逐漸上升,導(dǎo)致此現(xiàn)象原因與圖2 分析一致。且在任何通信半徑下OLPDV_Hop算法的平均定位誤差都小于另外3種算法,表明在節(jié)點(diǎn)分布稀疏的條件下OLPDV_Hop算法較另外3種算法優(yōu)勢(shì)更為顯著。經(jīng)計(jì)算,OLPDV_Hop算法的定位誤差較DV_Hop算法、IPSODV_Hop算法和BDV_Hop算法的定位誤差分別平均降低了40.11%、28.98%和13.91%。
②不同錨節(jié)點(diǎn)數(shù)
圖4表示通信半徑為30 m,節(jié)點(diǎn)總數(shù)為100個(gè),錨節(jié)點(diǎn)數(shù)從5~30不斷增加時(shí)4種算法的平均定位誤差曲線圖。由圖可知,當(dāng)通信半徑和節(jié)點(diǎn)總數(shù)一定時(shí),隨著錨節(jié)點(diǎn)數(shù)的不斷增加,4種算法的平均定位誤差逐漸減小,主要是由于錨節(jié)點(diǎn)密度的增大使其之間的跳數(shù)減小所致,且OLPDV_Hop算法平均定位誤差在所有錨節(jié)點(diǎn)數(shù)下均小于于另外3種算法。經(jīng)計(jì)算,OLPDV_Hop算法的平均定位誤差較DV_Hop算法、IPSODV_Hop算法和BDV_Hop算法分別下降了39.03%、23.45%和8.41%。
圖4 不同錨節(jié)點(diǎn)下平均定位誤差曲線圖
本文在DV_Hop算法基礎(chǔ)上采用單跳平均誤差修正平均跳距,利用多錨節(jié)點(diǎn)平均跳距估計(jì)節(jié)點(diǎn)間距離,進(jìn)而使距離得以優(yōu)化。為進(jìn)一步提高定位算法精度,避免速度項(xiàng)對(duì)收斂速度影響,利用Levy飛行模式改變粒子位置移動(dòng)方向,避免粒子陷入局部最優(yōu),并通過貪婪更新評(píng)價(jià)策略選擇最優(yōu)解,進(jìn)而得到最優(yōu)解。仿真實(shí)驗(yàn)表明,本文算法在定位精度上明顯優(yōu)于DV_Hop算法、IPSODV_Hop算法和BDV_Hop算法,適合在實(shí)際中使用。
參考文獻(xiàn):
[1] 李建坡,時(shí)明,鐘鑫鑫. 自適應(yīng)蒙特卡羅無線傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)定位算法[J]. 吉林大學(xué)學(xué)報(bào)(工學(xué)版),2014,44(4):1191-1196.
[2] Delin,K A,Jackson S P. Sensor Web:A New Instrument Concept[C]//Proc of Symposium on Integrated Optics. International Society for Optics and Photonics. 2001:1-9.
[3] Bulusu N,Heidemann J,Estrin D. GPS-Less Low Cost Outdoor Localization for Very Small Devices[J]. IEEE Personal Communications Magazine,2000,7(5):28-34.
[4] Gayan S,Dias D. Improved DV_Hop Algorithm Through Anchor Position Reestimation[C]//2014 IEEE Asia Pacific Conference on Wireless and Mobile. 2014:126-131.
[5] 范時(shí)平,羅丹,劉艷林. 基于跳距與改進(jìn)粒子群算法的DV_Hop定位算法[J]. 傳感技術(shù)學(xué)報(bào),2016,29(9):1410-1415.
[6] 林雯,張烈平,王守峰. 基于改進(jìn)粒子群優(yōu)化的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位方法研究[J]. 計(jì)算機(jī)測(cè)量與控制(S1671-4598),2013,21(7):2023-2026.
[7] 肖曉麗,李旦江,譚柳斌.基于布谷鳥搜索算法的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位[J/OL]. 計(jì)算機(jī)工程與應(yīng)用,http://www.cnki.net/kcms/detail/11. 2127. TP.20150902.1520.008.html.
[8] 裴祥,李巧君. 基于改進(jìn)粒子群優(yōu)化算法的無線傳感器網(wǎng)絡(luò)定位[J]. 計(jì)算機(jī)與現(xiàn)代化,2015(7):81-84.
[9] Okulewicz M,Mandziuk J. The Impact of Particular Components of the PSO-Based Algorithm Solving the Dynamic Vehicle Routing Problem[J]. Applied Soft Computing,2017,58(9):586-604.
[10] Vakil Baghmisheh M T,Peimani M,Sadeghi MH,et al. A Hybrid Particle Swarm-Nelder-Mead Optimization Method for Crack Detection in Cantilever Beams[J]. Applied Soft Computing,2012,12(8):2217-2226.
[11] 于桂芹,李劉東,袁永峰. 一種結(jié)合自適應(yīng)慣性權(quán)重的混合粒子群算法[J]. 哈爾濱理工大學(xué)學(xué)報(bào),2016,21(3):49-53.
[12] 王玉芳,毛永毅. 一種基于改進(jìn)布谷鳥算法的WSN節(jié)點(diǎn)定位算法[J/OL]. 計(jì)算機(jī)應(yīng)用研究,2017,34(11):3412-3415.