基于最優(yōu)跳距和LevyPSO算法的DV_Hop定位算法*

檀 爽,毛永毅

(西安郵電大學(xué)電子工程學(xué)院,西安 710061)

信息的采集、傳輸、處理是無線傳感器網(wǎng)絡(luò)中3個重要過程,在眾多領(lǐng)域能夠?qū)崿F(xiàn)大規(guī)模的跟蹤和監(jiān)測任務(wù),在這過程中節(jié)點的位置尤其重要[1]。現(xiàn)階段,在無線傳感器網(wǎng)絡(luò)定位技術(shù)中,根據(jù)定位算法是否需要通過測距,將定位算法分為基于測距的和無需測距的兩種[2]?；跍y距的定位算法需要額外的硬件支持來配置,而無需測距的定位算法只需要網(wǎng)絡(luò)之間的連通性和錨節(jié)點信息就能估算出未知節(jié)點的信息,該算法成本較低,硬件設(shè)備簡單,功耗較小。與距離無關(guān)的典型的定位算法主要包括:質(zhì)心算法[3]、凸規(guī)劃算法和DV_Hop算法[4]等。許多學(xué)者對此進行了大量研究與改進。文獻[5]提出了一種帶權(quán)重的改進平均跳距與改進PSO算法來改進DV_Hop算法。文獻[6]得到最優(yōu)解是通過差分進化算法優(yōu)化適應(yīng)度函數(shù)以減小定位誤差。文獻[7]提出一種基于CS(Cuckoo Search)算法的WSN(Wireless Sensor Network)節(jié)點定位算法,利用CS算法替代在DV_Hop算法中求解未知節(jié)點坐標(biāo)階段所采用的最小二乘法。文獻[8]通過改進PSO算法優(yōu)化DV_Hop算法,并引入收縮因子加快收斂速度和提高定位精度,從而找到最優(yōu)位置。

本文提出一種基于最優(yōu)跳距與LevyPSO算法的WSN節(jié)點定位算法,即OLPDV_Hop定位算法。仿真結(jié)果表明,OLPDV_Hop算法在定位精度上相比于DV_Hop算法、文獻[5]算法和文獻[8]的算法均有所提高,同時也無需增加額外成本。

1 改進粒子群算法

1.1 DV_Hop算法

DV_Hop算法是由Niculescu等人提出的,利用跳數(shù)和平均每跳距離的乘積來估算未知節(jié)點和錨節(jié)點之間距離,進而通過極大似然估計法或三邊定位法得到未知節(jié)點位置。具體分為3個階段:

第1階段 跳數(shù)估計

通過距離矢量交換,網(wǎng)絡(luò)中所有節(jié)點獲得距離錨節(jié)點的跳數(shù)等信息。即錨節(jié)點以洪泛的形式向其他鄰居節(jié)點發(fā)送數(shù)據(jù)包,這個數(shù)據(jù)包中包括錨節(jié)點到接收信息節(jié)點的跳數(shù)、錨節(jié)點的標(biāo)識、坐標(biāo)。為保證未知節(jié)點到錨節(jié)點的跳數(shù)最小,當(dāng)未知節(jié)點接收到同一個錨節(jié)點的多個數(shù)據(jù)包時,只保留跳數(shù)最小的數(shù)據(jù)包。

第2階段 距離估計

每個錨節(jié)點根據(jù)所記錄的其他信標(biāo)節(jié)點的跳數(shù)和坐標(biāo)信息,根據(jù)式(1)估計平均每跳距離:

(1)

式中:(xi,yi),(xj,yj)是信標(biāo)節(jié)點i,j的坐標(biāo),hij是信標(biāo)節(jié)點i,j之間的最小跳數(shù)。

第3階段 位置估計

通過未知節(jié)點和錨節(jié)點的距離,挑選3個錨節(jié)點利用三邊定位算法求得未知節(jié)點坐標(biāo),也可以通過極大似然估計實現(xiàn)未知節(jié)點的定位。

1.2 DV_Hop算法改進

1.2.1 平均跳距修正

節(jié)點間估計距離是通過跳數(shù)值和平均跳距的乘積所得到的,因此平均跳距的誤差直接影響估計距離的精確度。為了使誤差減小,利用錨節(jié)點間單跳平均誤差修正平均跳距,使其接近真實值,進而使距離得以優(yōu)化。

(2)

(3)

因此可以通過式(2)和式(3)的差值可以求得錨節(jié)點i和j之間的距離誤差,如式(4)所示

(4)

錨節(jié)點i的單跳平均誤差可以通過式(5)求出,其中n為錨節(jié)點個數(shù)。

(5)

最后通過式(6)修正平均跳距,如式(6)所示:

(6)

1.2.2 多錨節(jié)點平均跳距估計距離

在估計節(jié)點間距離階段,待求未知節(jié)點

根據(jù)就近原則只接收錨節(jié)點傳遞過來的第1個平均跳距信息。而網(wǎng)絡(luò)分布是隨機的,數(shù)據(jù)選擇的單一性必然增加了偶然性,進而影響后期定位。求到哪點的估計距離就用該點的平均跳距不僅可以考慮到全局信息,而且會在一定程度上降低偶然性,從而使定位精度有所提高。

各節(jié)點間平均跳距如下:

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ò)拓撲結(jié)構(gòu)圖

利用各節(jié)點平均跳距通過不同方法估算節(jié)點間距離,結(jié)果如表一所示。

觀察表1發(fā)現(xiàn),使用多錨節(jié)點平均跳距估計距離能使估計距離更接近真實值

表1 節(jié)點間實際距離與估計距離

2 LevyPSO算法

2.1 粒子群算法

粒子群優(yōu)化算法于1995年由Eberhart和Kennedy提出的[9],它模擬了魚類和鳥類在尋找食物方面的協(xié)作行為[10]。在PSO算法中,每個粒子表示優(yōu)化問題的潛在解決方案,而食物源的位置就是全局最優(yōu)解。PSO從隨機解出發(fā),具有快速收斂能力和優(yōu)異的全局搜索性能。

(7)

(8)

式中:w表示慣性權(quán)重,c1,c2為加速度常數(shù),r1,r2是[0,1]的隨機數(shù),pi表示第i個粒子的個體極值,pg表示整個粒子群的全局極值。

2.2 Levy飛行

Levy飛行是由Levy提出,Benoist-Madelbrot描述的一種穩(wěn)定分布。大體上說,Levy飛行就是一種模擬動物覓食的一種隨機游走過程。Levy飛行有如下特點:

①具有統(tǒng)計的隨機分形與自相似性,即隨機變量本身與獨立同分布的隨機變量之和同分布。

②其服從“重尾”分布,即具有冪律漸進性～|x|(-1-α)。

③就隨機分布與隨機變量而言,Levy飛行是極限的一種,其在鄰域范圍內(nèi)具有吸引力,當(dāng)系統(tǒng)的實現(xiàn)結(jié)果由大量隨機數(shù)之和決定時,就會出現(xiàn)吸引,即其具有廣義中心極限定理。

④具有無限方差與均值。

2.3 LevyPSO算法原理

PSO算法定位精度較低是由于在算法前期收斂速度較快但后期收斂速度逐漸變慢。其主要原因是當(dāng)PSO算法處于進化停滯時,粒子出現(xiàn)“聚焦”現(xiàn)象,種群失去多樣性,導(dǎo)致算法難以趨于全局最優(yōu),出現(xiàn)”早熟”[11]現(xiàn)象。許多學(xué)者針對此問題提出改進策略,但這些都是通過調(diào)整式(7)中的參數(shù)w,c1,c2。雖然在不同程度上提高了定位精度,但并沒有從PSO算法收斂于局部極值的根本原因上采取措施。經(jīng)過研究發(fā)現(xiàn),Levy飛行能使粒子隨機游走經(jīng)歷新的搜索路徑,產(chǎn)生新解,從而增加種群的多樣性,避免容易陷入局部極值。

在PSO算法中速度項v受上代粒子的移動方向影響較重而失去多樣性,從而容易陷入局部極值。另一方面也違背了Levy飛行的隨機游走理念。由此,本文采用式(9)更新粒子位置。

(9)

Levy飛行雖然可以解決局部收斂,但其并不一定能保證產(chǎn)生的新解一定優(yōu)于原來的解。由此本文提出一種貪婪的更新評價策略?；谪澙返母略u價策略能夠保證算法利用每一代最優(yōu)解引導(dǎo)算法進行局部搜索,從而加快收斂速度并獲取更高質(zhì)量的解。令

(10)

(11)

因此式LevyPSO算法將(7)、式(8)改進為

(12)

式中:α=α0(xi-pg)為步長信息,α0為常數(shù)0.01;⊕表示點對點乘法;Levy(β)～|x|(-1-β)(0<β<2);fit(x)為x適應(yīng)度值,pg為全局最優(yōu)位置。

2.4 適應(yīng)度函數(shù)設(shè)置

在DV_Hop定位算法中,估計距離dn通過最小跳數(shù)與估算平均跳距的乘積來替代,這會造成很大的誤差,所以通過最小二乘法求得的待定位節(jié)點坐標(biāo)精度較低,為了減小定位誤差影響,我們將問題轉(zhuǎn)換為dn的優(yōu)化問題。

設(shè)待定位節(jié)點D(x,y)到信標(biāo)節(jié)點A1,A2…,An的真實距離分別為r1,r2…rn,相應(yīng)的測距誤差為ε1,ε2…εn,則:

|ri-di|<εi

(13)

式(13)可改為

(14)

由式(13)可知,εi越小,所求得待定位節(jié)點的位置與其真實位置越接近。

(15)

當(dāng)適應(yīng)度函數(shù)fitness(x,y)取值最小時,所求待定位節(jié)點位置與其真實位置最接近,定位誤差最小。

3 OLPDV_Hop算法流程

OLPDV_Hop算法流程如下:

Step 1 初始化網(wǎng)絡(luò)中節(jié)點數(shù)以及網(wǎng)絡(luò)區(qū)域大小,初始化LevyPSO算法各參數(shù)、粒子位置、最大迭代次數(shù)、種群規(guī)模。

Step 2 根據(jù)式(15)計算各粒子適應(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,直到達到最大迭代次數(shù),輸出最優(yōu)解。

4 仿真實驗

為了驗證OLPDV_Hop算法的性能,在Windows7的MATLABR2014a環(huán)境下分別對DV_Hop算法、IPSODV_Hop 算法和BDV_Hop算法進行仿真比較與分析。本文采用文獻[12]提出的歸一化平均定位誤差作為算法性能的評價指標(biāo),如式(16)所示。

(16)

式中:(xr,yr)表示待定位節(jié)點的真實坐標(biāo),(xi,yi)表示待定位節(jié)點估計坐標(biāo),R表示節(jié)點通信半徑,k為待定位節(jié)點個數(shù)。

圖2為錨節(jié)點數(shù)為20,先后加入距離優(yōu)化和LevyPSO算法后,通信半徑從25 m～50 m平均定位誤差曲線圖。由圖可知,通信半徑為25 m～40 m時曲線都呈下降趨勢,主要原因是網(wǎng)絡(luò)連通度的提升所導(dǎo)致。之后曲線逐漸上升,這是由于過大的通信半徑會導(dǎo)致平均定位誤差增大,因此不必一味追求過大通信半徑,應(yīng)適當(dāng)選取。由圖2可知,再加入距離優(yōu)化和LevyPSO算法后,平均定位誤差都呈下降趨勢。

圖2 不同通信半徑下平均定位誤差曲線圖

下面將OLPDV_Hop算法、DV_Hop算法、IPSODV_Hop算法和BDV_Hop算法分別在不同錨節(jié)點數(shù)和不同通信半徑下進行仿真對比與分析。本文選取邊長為100 m的正方形作為仿真區(qū)域,在相同參數(shù)下仿真100次,計算其均值并繪制出相應(yīng)的平均定位誤差曲線圖。

圖3 不同通信半徑下平均定位誤差曲線圖

①不同通信半徑

圖3為錨節(jié)點數(shù)為20%,節(jié)點總數(shù)為100個,通信半徑為25 m～50 m不斷增加時4種算法的平均定位誤差變化曲線圖。由圖可知,當(dāng)錨節(jié)點數(shù)和節(jié)點總數(shù)一定時,半徑為25 m～40 m,4種算法的平均定位誤差逐漸降低,而后逐漸上升,導(dǎo)致此現(xiàn)象原因與圖2 分析一致。且在任何通信半徑下OLPDV_Hop算法的平均定位誤差都小于另外3種算法,表明在節(jié)點分布稀疏的條件下OLPDV_Hop算法較另外3種算法優(yōu)勢更為顯著。經(jīng)計算,OLPDV_Hop算法的定位誤差較DV_Hop算法、IPSODV_Hop算法和BDV_Hop算法的定位誤差分別平均降低了40.11%、28.98%和13.91%。

②不同錨節(jié)點數(shù)

圖4表示通信半徑為30 m,節(jié)點總數(shù)為100個,錨節(jié)點數(shù)從5～30不斷增加時4種算法的平均定位誤差曲線圖。由圖可知,當(dāng)通信半徑和節(jié)點總數(shù)一定時,隨著錨節(jié)點數(shù)的不斷增加,4種算法的平均定位誤差逐漸減小,主要是由于錨節(jié)點密度的增大使其之間的跳數(shù)減小所致,且OLPDV_Hop算法平均定位誤差在所有錨節(jié)點數(shù)下均小于于另外3種算法。經(jīng)計算,OLPDV_Hop算法的平均定位誤差較DV_Hop算法、IPSODV_Hop算法和BDV_Hop算法分別下降了39.03%、23.45%和8.41%。

圖4 不同錨節(jié)點下平均定位誤差曲線圖

5 結(jié)束語

本文在DV_Hop算法基礎(chǔ)上采用單跳平均誤差修正平均跳距,利用多錨節(jié)點平均跳距估計節(jié)點間距離,進而使距離得以優(yōu)化。為進一步提高定位算法精度,避免速度項對收斂速度影響,利用Levy飛行模式改變粒子位置移動方向,避免粒子陷入局部最優(yōu),并通過貪婪更新評價策略選擇最優(yōu)解,進而得到最優(yōu)解。仿真實驗表明,本文算法在定位精度上明顯優(yōu)于DV_Hop算法、IPSODV_Hop算法和BDV_Hop算法,適合在實際中使用。

參考文獻:

[1] 李建坡,時明,鐘鑫鑫. 自適應(yīng)蒙特卡羅無線傳感器網(wǎng)絡(luò)移動節(jié)點定位算法[J]. 吉林大學(xué)學(xué)報(工學(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] 范時平,羅丹,劉艷林. 基于跳距與改進粒子群算法的DV_Hop定位算法[J]. 傳感技術(shù)學(xué)報,2016,29(9):1410-1415.

[6] 林雯,張烈平,王守峰. 基于改進粒子群優(yōu)化的無線傳感器網(wǎng)絡(luò)節(jié)點定位方法研究[J]. 計算機測量與控制(S1671-4598),2013,21(7):2023-2026.

[7] 肖曉麗,李旦江,譚柳斌.基于布谷鳥搜索算法的無線傳感器網(wǎng)絡(luò)節(jié)點定位[J/OL]. 計算機工程與應(yīng)用,http://www.cnki.net/kcms/detail/11. 2127. TP.20150902.1520.008.html.

[8] 裴祥,李巧君. 基于改進粒子群優(yōu)化算法的無線傳感器網(wǎng)絡(luò)定位[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é)報,2016,21(3):49-53.

[12] 王玉芳,毛永毅. 一種基于改進布谷鳥算法的WSN節(jié)點定位算法[J/OL]. 計算機應(yīng)用研究,2017,34(11):3412-3415.