基于DV-Hop測距修正的遺傳模擬退火定位算法*

徐慧娟

(黃淮學(xué)院信息工程學(xué)院,河南 駐馬店 463000)

目前,無線傳感網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)已應(yīng)用于多個領(lǐng)域,如森林防火監(jiān)測、健康醫(yī)療等。而定位是WSNs應(yīng)用的基礎(chǔ)?，F(xiàn)有的定位算法可分為基于測距(Range-based)[2]和基于非測距[3]兩類。通常,基于測距定位算法的定位精度優(yōu)于基于非測距定位算法。但是,后者無需額外的硬件設(shè)備,成本低,其中DV-Hop算法屬典型的非測距定位算法,也被廣泛應(yīng)用。

然而,DV-Hop定位算法在測距過程中仍存在較大的誤差,為此,研究人員提出了不同的改進(jìn)算法。文獻(xiàn)[4]利用粒子群算法求解定位方程,提高了定位精度;文獻(xiàn)[5]提出基于差分進(jìn)化的定位算法,其利用差分進(jìn)化優(yōu)化適應(yīng)度函數(shù),從而獲取最優(yōu)的位置估計(jì)。此外,文獻(xiàn)[6-7]也分別提出基于遺傳、人工蜂群的定位算法。但是,這些算法需要的參數(shù)較多,容易產(chǎn)生局部最優(yōu)問題[1]。

本文提出基于DV-Hop測距修正的遺傳模擬退火定位算法IDV-Hop-GSAL(Improved DV-Hop Ranging-based Genetic-Simulated Annealing Localizatio)算法。IDV-Hop-GSAL算法首先利用DV-Hop測距,即通過引用相近度修正測距值,然后利用最小二乘估計(jì)未知節(jié)點(diǎn)的位置(初始解),再利用遺傳模擬退火算法優(yōu)化初始解。實(shí)驗(yàn)數(shù)據(jù)表明,提出的IDV-Hop-GSAL算法降低了DV-Hop算法的定位誤差,提高了定位精度。

1 DV-Hop測距原理及問題描述

1.1 DV-Hop測距原理

DV-Hop測距算法過程主要由3個階段構(gòu)成:

①估算跳數(shù) 在估算跳數(shù)階段,錨節(jié)點(diǎn)廣播自己位置以及初始跳數(shù)信息,使得鄰居節(jié)點(diǎn)能夠獲取離錨節(jié)點(diǎn)的跳數(shù)值。此階段是DV-Hop的初始階段。

②計(jì)算錨節(jié)點(diǎn)間的平均跳距 通過估算跳數(shù)階段,錨節(jié)點(diǎn)已獲取了各錨節(jié)點(diǎn)的跳數(shù)以及位置信息[8]。據(jù)此,計(jì)算平均跳距。假定錨節(jié)點(diǎn)i計(jì)算的平均跳距:

(1)

式中:dik表示錨節(jié)點(diǎn)i與錨節(jié)點(diǎn)k間的距離。相應(yīng)地,hik為它們間的跳數(shù)。而(xi,yi)和(xk,yk)分別表示錨節(jié)點(diǎn)i、k間的位置。

③測距 錨節(jié)點(diǎn)計(jì)算了平均跳距后,就將平均跳距值進(jìn)行廣播。未知節(jié)點(diǎn)接收后,就利用此值計(jì)算離錨節(jié)點(diǎn)間的距離[9]。假定未知節(jié)點(diǎn)j離錨節(jié)點(diǎn)k的距離為djk,其定義如式(2)所示:

djk=Hopsizek×hjk

(2)

式中:hjk為節(jié)點(diǎn)j與節(jié)點(diǎn)k間的跳數(shù)。

DV-Hop測距示例如圖1所示。

圖1 DV-Hop測距原理

圖1中的3個黑色實(shí)心圓表示錨節(jié)點(diǎn),其他節(jié)點(diǎn)為待定位節(jié)點(diǎn)(未知節(jié)點(diǎn))。以錨節(jié)點(diǎn)L2為例,在估算平均跳距前,先計(jì)算離另兩個錨節(jié)點(diǎn)(L1、L3)距離和跳數(shù),最后依據(jù)式(1)計(jì)算平均跳距:

Hopsize2=(40+75)/(2+5)=16.43m

(3)

隨后,錨節(jié)點(diǎn)L2就廣播平均跳距值。未知節(jié)點(diǎn)A接收后,就依據(jù)式(2)計(jì)算離3個錨節(jié)點(diǎn)的距離:

(4)

1.2 問題描述

從1.1節(jié)過程可知,DV-Hop測距是利用錨節(jié)點(diǎn)所計(jì)算的平均跳距與跳數(shù)相乘而得到的距離。而平均跳距是由錨節(jié)點(diǎn)依據(jù)錨節(jié)點(diǎn)的分布情況進(jìn)行計(jì)算的。如果錨節(jié)點(diǎn)分布不均勻,必然會存在大的誤差。為此,本文對測距值進(jìn)行修正。在獲取了修正后的測距值后,再利用遺傳模擬退火算法GASA進(jìn)行位置估計(jì),進(jìn)而提高位置估計(jì)。

2 IDV-HOP-GSAL定位算法

2.1 系統(tǒng)模型

2.2 測距值的修正

由2.1節(jié)可知,未知節(jié)點(diǎn)在估算離各錨節(jié)點(diǎn)間的距離時(shí),是采用同一個平均跳距值與離各錨節(jié)點(diǎn)間的跳數(shù)相乘。這沒有考慮各錨節(jié)點(diǎn)周圍節(jié)點(diǎn)分布的差異性,必然會引起測距誤差[10]。

以圖2為例。假定A是未知節(jié)點(diǎn)。B、C、D為錨節(jié)點(diǎn)。從圖2可知,節(jié)點(diǎn)A離錨節(jié)點(diǎn)B、C均是一跳。依據(jù)式(2)計(jì)算,節(jié)點(diǎn)A離錨節(jié)點(diǎn)B、C距離是相等的。而實(shí)際上,它們的距離并不相等。

圖2 節(jié)點(diǎn)通信示例

此外,如果節(jié)點(diǎn)A是從錨節(jié)點(diǎn)B獲取了平均跳距HopsizeB。若HopsizeB值誤差較大,則節(jié)點(diǎn)A在估算到其他錨節(jié)點(diǎn)距離時(shí),就會產(chǎn)生測距誤差,并且隨跳數(shù)增加而被累積。顯然,在利用單一平均跳距進(jìn)行測距時(shí),增加測距誤差。因此,必須對測距值進(jìn)行修正。

為此,提出的IDV-HOP-GSAL定位算法先對測距值進(jìn)行修正。具體而言,未知節(jié)點(diǎn)先計(jì)算離各錨節(jié)點(diǎn)的距離遠(yuǎn)近,再依據(jù)遠(yuǎn)近程度對測距值進(jìn)行修正。

(5)

式中:λjk表示未知節(jié)點(diǎn)j離它的鄰居錨節(jié)點(diǎn)k的相近度。而Setj、Setk分別表示節(jié)點(diǎn)j、k的鄰居節(jié)點(diǎn)集。相應(yīng)地Crad(Setj∪Setk)、Crad(Setj∩Setk)分別表示Setj和Setk兩個集的并集、交集的元素個數(shù)。

相近度能夠真實(shí)地反映節(jié)點(diǎn)離鄰居錨節(jié)點(diǎn)的遠(yuǎn)近信息。以圖3為例進(jìn)行說明。從圖3可知,Crad(SetA∪SetB)=21、Crad(SetA∩SetB)=7。因此,依據(jù)式(5)計(jì)算可得:節(jié)點(diǎn)A與B的相近度λAB=21/7=3。類似地,λAc=17/12≈1.42。由于λAB>λAC,說明節(jié)點(diǎn)C離節(jié)點(diǎn)A更近,而節(jié)點(diǎn)B離節(jié)點(diǎn)A更遠(yuǎn),其更接近于通信半徑R。

圖3 計(jì)算相近度示意圖

依據(jù)相近度,未知節(jié)點(diǎn)便可對距離進(jìn)行修正。假定未知節(jié)點(diǎn)j對距離djk修正后:

(6)

式中:λkmax表示節(jié)點(diǎn)k的所有鄰居節(jié)點(diǎn)離自己相近度的最大值。

2.3 定位算法

整個定位算法的思路就是:先通過DV-Hop測距并進(jìn)行修正,然后再利用最小二乘法估計(jì)未知節(jié)點(diǎn)的初始位置,最后將此初始解作為GSAS的輸入[11],并進(jìn)行全局搜索。再經(jīng)歷遺傳算法內(nèi)的選擇、交叉、變異等一系列操作,產(chǎn)生新的個體,然后再基于新個體進(jìn)行模擬退火操作,其結(jié)果作為下一代群體中的個體。

(7)

然后,再建立函數(shù)fk:

(8)

因此,fk表示錨節(jié)點(diǎn)k與未知節(jié)點(diǎn)i的定位誤差。為了最小化誤差,并且避免“早熟”情況,減少個體適應(yīng)度間的差異,使得群體具有多樣性。據(jù)此,建立適應(yīng)度[12]:

(9)

式中:βk表示權(quán)值,其反映了未知節(jié)點(diǎn)與錨節(jié)點(diǎn)間測量值的精度。IDV-HOP-GSAL算法就是利用GSAS降低適應(yīng)度值,適應(yīng)度值越小,定位越準(zhǔn)確。

為了更準(zhǔn)確地估計(jì)未知節(jié)點(diǎn)位置,對GSAS的參數(shù)進(jìn)行控制。首先利用式(10)更新種群,進(jìn)而更新染色體的好壞。

min{(p,exp(fk-f′)/Tt)}>random(0,1)p=1

(10)

從式(10)可知,更新種群的原則:將當(dāng)前種群中最佳染色體直接復(fù)制到子代種群中。式(10)中fk、f′分別表示子代中個體適應(yīng)值、父代中個體適應(yīng)值最差的個體。而Tt為控制溫度,單位度(℃)。

然后,通過Metropolis準(zhǔn)則來檢測是否對解進(jìn)行了更新。假定xi是本次解,xi+1是新解,且其以概率p進(jìn)行更新:

(11)

式中:T溫度參數(shù)。依據(jù)文獻(xiàn)[13],初步將T設(shè)置為90。

最后,進(jìn)行交叉、變異操作。在交叉操作時(shí),將選擇的點(diǎn)的序列分為左、右部,同時(shí)使得兩個基因的左、右部的序列進(jìn)行互換。然后,依據(jù)交換變異策略進(jìn)行變異操作,進(jìn)而維持種群的多樣性,最終增強(qiáng)全局探索能力。

圖4 IDV-HOP-GSAL定位算法流程

IDV-HOP-GSAL定位算法流程如圖4所示。首先進(jìn)行初始化階段。在此階段,設(shè)定初始值,包括初始迭代次數(shù)t=0、變異概率、交叉概率以及T0和Td,其中T0、Td分別表示初始溫度、終止溫度。然后,利用DV-Hop測距,直到迭代次數(shù)滿足要求。

3 仿真與分析

3.1 仿真環(huán)境

利用MATLAB建立仿真平臺,分析IDV-HOP-GSAL定位性能。迭代次數(shù)為100、交叉概率為0.008、變異概率為0.000 6,而種群大小為30。此外,仿真過程過程中考慮錨節(jié)點(diǎn)數(shù)、節(jié)點(diǎn)通信半徑以及總的節(jié)點(diǎn)數(shù)對平均定位誤差的影響,為此,設(shè)為3個獨(dú)立實(shí)驗(yàn)。平均定位誤差的定義如式(12)所示:

(12)

為了更好地的比較IDV-HOP-GSAL的定位算法,選擇幾個同類的定位算法進(jìn)行比較:①利用DV-Hop測距(未修正),最小二乘法定位,記為DV-Hop+LS;②布谷鳥改進(jìn)的DV-Hop算法,記為CSDV-Hop。

3.2 仿真數(shù)據(jù)

3.2.1 實(shí)驗(yàn)一

首先分析錨節(jié)點(diǎn)數(shù)對平均定位誤差的影響。實(shí)驗(yàn)參數(shù)如下:總的節(jié)點(diǎn)數(shù)為100(錨節(jié)點(diǎn)和未知節(jié)點(diǎn)),其中錨節(jié)點(diǎn)比例從5%～35%變化。此外,通信半徑R=30 m。實(shí)驗(yàn)數(shù)據(jù)如圖5所示。

圖5 錨節(jié)點(diǎn)數(shù)對平均定位誤差率的影響

圖5是DV-Hop+LS定位算法、CSDV-Hop和IDV-Hop-GSAL定位算法運(yùn)行了50次的平均定位誤差隨錨節(jié)點(diǎn)變化曲線。從圖5可知,當(dāng)通信半徑R、總的節(jié)點(diǎn)數(shù)固定時(shí),DV-Hop+LS、CSDV-Hop和IDV-HOP-GSAL定位算法的平均定位誤差隨錨節(jié)點(diǎn)數(shù)的增加而減少。換而言之,錨節(jié)點(diǎn)數(shù)的增加有利于定位精度的提高。與DV-Hop+LS、CSDV-Hop算法相比,提出的IDV-HOP-GSAL算法的平均定位誤差得到有效地控制,且分別比DV-Hop+LS、CSDV-Hop下降了25%、6%。

3.2.2 實(shí)驗(yàn)二

本次實(shí)驗(yàn)分析通信半徑R對平均定位誤差的性能。實(shí)驗(yàn)參數(shù)如下:通信半徑R從20 m～50 m變化,總的節(jié)點(diǎn)數(shù)為100,錨節(jié)點(diǎn)數(shù)為30。圖6描述了DV-Hop+LS、CSDV-Hop和IDV-HOP-GSAL定位算法運(yùn)行了50次的平均定位誤差隨通信半徑R的變化曲線。

圖6 通信半徑R對平均定位誤差率的影響

從圖6可知,通信半徑R的增加,降低了平均定位誤差,提高了定位精度。原因在于:通信半徑越長,跳數(shù)越短,這有利于測距的精度的提高。與DV-Hop+LS、CSDV-Hop算法相比,提出的IDV-HOP-GSAL算法的平均定位誤差得到下降,且分別下降了28%、5%。這主要?dú)w功于IDV-HOP-GSAL算法利用相近度對測距值進(jìn)行了修正,同時(shí)也利用GSAS算法估計(jì)了未知節(jié)點(diǎn)位置。

3.2.3 實(shí)驗(yàn)三

最后,分析節(jié)點(diǎn)數(shù)對平均定位誤差的影響。實(shí)驗(yàn)參數(shù)如下:錨節(jié)點(diǎn)數(shù)為30、通信半徑R=30 m,總的節(jié)點(diǎn)數(shù)從60～180變化,步長為20。圖7描繪了DV-Hop+LS、CSDV-Hop和IDV-Hop-GSAL算法運(yùn)行50次的平均定位誤差曲線。

圖7 節(jié)點(diǎn)數(shù)對平均定位誤差率的影響

從圖7可知,當(dāng)錨節(jié)點(diǎn)數(shù)不變、通信半徑R=30 m固定時(shí),節(jié)點(diǎn)數(shù)的增加,降低了平均定位誤差,但下降幅度逐漸下降。與DV-Hop+LS、CSDV-Hop算法相比,提出的IDV-HOP-GSAL定位算法的平均定位誤差得到控制,且比DV-Hop+LS、CSDV-Hop算法下降了30%、4.7%。

3.2.4 算法復(fù)雜度

表1描述了在100個節(jié)點(diǎn)數(shù)、30個錨節(jié)點(diǎn)以及通信半徑R=30 m的環(huán)境下的算法運(yùn)行時(shí)間。從表1可知,提出的IDV-HOP-GSAL定位算法的運(yùn)行時(shí)間高于DV-Hop+LS算法。這也說明,IDV-HOP-GSAL定位算法以一定的復(fù)雜度換取高的定位精度。

表1 算法的運(yùn)行時(shí)間

4 總結(jié)

本文針對傳統(tǒng)的DV-Hop的定位算法,先分析它的不足,再提出基于DV-Hop測距修正的遺傳模擬退火定位算法 IDV-Hop-GSAL算法。IDV-Hop-GSAL算法利用節(jié)點(diǎn)分布情況,對測距值進(jìn)行了修正。在定位階段,先利用最小二乘法估計(jì)未知節(jié)點(diǎn)位置,并將其作為初始值,然后再GSAL算法優(yōu)化初始值。實(shí)驗(yàn)數(shù)據(jù)表明,提出的IDV-Hop-GSAL算法的定位精度優(yōu)于DV-Hop+LS算法。在后期,將優(yōu)化算法,降低算法的復(fù)雜度。

[1] 劉登峰,章力,邴曉瑛,等. 基于布谷鳥差分算法優(yōu)化的DV-Hop改進(jìn)算法[J]. 系統(tǒng)仿真學(xué)報(bào),2017,29(4):790-797.

[2] Chu Y L,Tzeng J R,Cheng Y P. Density-Adaptive Range-Free Localization in Large-Scale Sensor Networks[C]//41st International Conference on Parallel Processing Workshops(ICPPW),2012. USA:IEEE,2012:488-495.

[3] Maung N,Kawai M. Experimental Evaluations of RSS Threshold-Based Optimised DV-HOP Localisation for Wireless Ad-Hoc Networks[J]. Electronics Letters(S1350-911X),2014,50(17):1246-1248.

[4] 黃艷,臧傳治,于海斌. 基于改進(jìn)粒子群優(yōu)化的無線傳感器網(wǎng)絡(luò)定位算法[J]. 控制與決策,2012,27(1):156-160.

[5] 林雯,張烈平,王守峰. 基于差分進(jìn)化算法的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位方法研究[J]. 計(jì)算機(jī)測量與控制(S1671-4598),2013,21(7):2023-2026.

[6] 劉彥隆,呂顯朋,王相國. 混合遺傳算法在WSNs定位中的應(yīng)用[J]. 傳感器與微系統(tǒng),2014,33(2):150-153.

[7] 李牧東,熊偉,梁青. 基于人工蜂群改進(jìn)算法的無線傳感網(wǎng)絡(luò)定位算法[J]. 傳感技術(shù)學(xué)報(bào),2013,26(2):241-245.

[8] 向滿天,王勝,楊友華. 基于閾值機(jī)制與距離校正的WSN改進(jìn)DV-Hop定位算法[J]. 傳感技術(shù)學(xué)報(bào),2016,29(6):920-926.

[9] 張新榮,熊偉麗,徐保國. 采用RSSI模型的無線傳感器網(wǎng)絡(luò)協(xié)作定位算法[J]. 電子測量與儀器學(xué)報(bào),2016,30(7):1008-1017.

[10] 任克強(qiáng),李亞東. WSN中DV-Hop節(jié)點(diǎn)定位算法的改進(jìn)[J]. 傳感技術(shù)學(xué)報(bào),2017,30(4):611-618.

[11] 李騰宇,易曉梅,陳石. 基于RSSI加權(quán)質(zhì)心和GASA優(yōu)化的WSN定位算法[J]. 計(jì)算機(jī)工程與應(yīng)用,2017,53(6):118-123.

[12] Tian Jun. Reversible Data Embeding Using a Difference Expansion[J]. IEEE Trans on Circuits and Systems for Video Technology,2013,13(8):56-62.

[13] Wu H C,Lee C C,Tsai C S. A High Capacity Reversible Data Hiding Scheme with Edge Prediction and Difference Expansion[J]. Journal of Systems and Software,2014,82(12):1966-1973.