基于模擬退火的加權(quán)DV-Hop的WSN定位算法

張治華，張玲華

(1.南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003；2.江蘇省通信與網(wǎng)絡(luò)技術(shù)工程研究中心，江蘇 南京 210003)

0 引 言

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)[1]是目前一個(gè)比較新興的研究領(lǐng)域，研究其最基本的需求就是獲取采集數(shù)據(jù)的節(jié)點(diǎn)位置信息。一般對(duì)于無(wú)準(zhǔn)確位置信息的監(jiān)測(cè)信息是沒(méi)有任何利用價(jià)值的。在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中，需要獲取無(wú)線(xiàn)傳感網(wǎng)中傳感器節(jié)點(diǎn)的位置信息，只有獲取節(jié)點(diǎn)的具體位置，才能通過(guò)節(jié)點(diǎn)信息分析采取何種決策方式。所以說(shuō)獲取傳感器節(jié)點(diǎn)的位置信息具有重要意義。綜上所述，傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)是當(dāng)今國(guó)內(nèi)外研究的熱點(diǎn)和重點(diǎn)[2]。

無(wú)線(xiàn)傳感網(wǎng)絡(luò)中的定位算法主要分為兩種，一種是基于測(cè)距的定位算法(range-base),另一種是距離無(wú)關(guān)的(range-free)的定位算法[3]。前者主要是通過(guò)測(cè)量節(jié)點(diǎn)之間點(diǎn)到點(diǎn)的距離以及角度信息來(lái)計(jì)算節(jié)點(diǎn)位置，主要包括基于接受信號(hào)強(qiáng)度算法(RSSI)[4]、基于到達(dá)時(shí)間定位算法(TOA)[5]、基于到達(dá)時(shí)間差定位算法(TDOA)和基于到達(dá)角度算法(AOA)等[6]。這類(lèi)算法雖然精度較高，但是對(duì)于硬件要求也高，而且受限于測(cè)距技術(shù)。后者是利用節(jié)點(diǎn)間的估計(jì)距離計(jì)算未知節(jié)點(diǎn)的位置，所以無(wú)需通過(guò)額外的硬件測(cè)量節(jié)點(diǎn)間的距離等信息。常用的與距離無(wú)關(guān)的定位技術(shù)有DV-Hop、質(zhì)心算法[7]、Amorphous、APIT[8]等，這類(lèi)算法成本和功耗都較低，應(yīng)用也更加廣泛。

DV-Hop算法[9]是目前無(wú)線(xiàn)傳感網(wǎng)中應(yīng)用最廣泛的定位算法之一，針對(duì)原有算法的不足，提出了一種基于加權(quán)的平均每跳跳距的DV-Hop算法，通過(guò)未知節(jié)點(diǎn)對(duì)每個(gè)信標(biāo)節(jié)點(diǎn)估計(jì)的平均每跳跳距進(jìn)行歸一化加權(quán)處理，對(duì)于距離未知節(jié)點(diǎn)較近的信標(biāo)節(jié)點(diǎn)賦予大的權(quán)值。雖然改進(jìn)后的加權(quán)DV-Hop定位算法相比傳統(tǒng)定位算法的定位精度有所提高，但不是特別明顯。為了進(jìn)一步提高DV-Hop算法的定位精度，文中提出了模擬退火的加權(quán)DV-Hop算法。

1 經(jīng)典DV-Hop算法描述

經(jīng)典DV-Hop定位算法是基于距離矢量計(jì)算跳數(shù)的算法，具體步驟如下所述。

1.1 計(jì)算未知節(jié)點(diǎn)與每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)

首先信標(biāo)節(jié)點(diǎn)會(huì)向整個(gè)網(wǎng)絡(luò)廣播自身位置信息。信標(biāo)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)會(huì)記錄下廣播的信息，其中包括跳數(shù)信息，初始化為0。鄰節(jié)點(diǎn)會(huì)篩選同一信標(biāo)節(jié)點(diǎn)的最小跳數(shù)信息并記錄，然后將其加1傳播到網(wǎng)絡(luò)中。保證網(wǎng)絡(luò)中所有節(jié)點(diǎn)記錄下到信標(biāo)節(jié)點(diǎn)的最小跳數(shù)。

1.2 計(jì)算未知節(jié)點(diǎn)與每個(gè)信標(biāo)節(jié)點(diǎn)的估計(jì)距離

經(jīng)過(guò)上一步節(jié)點(diǎn)信息的路由洪泛，由式1計(jì)算平均每跳距離。

(1)

其中，(xi,yi),(xj,yj)為信標(biāo)節(jié)點(diǎn)i,j的坐標(biāo)；hi為信標(biāo)節(jié)點(diǎn)i與j之間的跳數(shù)：HopSize為平均跳距。

1.3 計(jì)算未知節(jié)點(diǎn)的自身位置

通過(guò)式2計(jì)算未知節(jié)點(diǎn)u到信標(biāo)節(jié)點(diǎn)的估計(jì)距離du,i：

du,i=HopSize·hu,i

(2)

其中，hu,i為最小跳數(shù)。

當(dāng)未知節(jié)點(diǎn)得到3個(gè)或者更多節(jié)點(diǎn)之間的距離后，再通過(guò)三邊測(cè)量法[9]或者極大似然法等數(shù)學(xué)方法計(jì)算未知節(jié)點(diǎn)的坐標(biāo)。

1.4 算法的誤差分析

在DV-Hop定位算法中，用未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的最小跳數(shù)乘以平均跳距來(lái)計(jì)算未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的距離。

如圖1所示，設(shè)A1、A2和A3為信標(biāo)節(jié)點(diǎn)，U1、U2、U3、U4、U5和U為未知節(jié)點(diǎn)。其中A1到A2的實(shí)際距離為40 m，A2到A3的距離為25 m，U到A1、A2、A3的實(shí)際距離分別為50 m、20 m、50 m。針對(duì)未知節(jié)點(diǎn)U，信標(biāo)節(jié)點(diǎn)A2與U的最小跳數(shù)為2，屬于局部最小跳數(shù)，因此U從A2獲取平均跳距。根據(jù)式1可得：Hopsize=(40+25)/(2+4)=10.8,那么U到A1、A2和A3的估計(jì)距離分別是10.8×3=32.4、10.8×2=21.6、10.8×3=32.4。由此可以看出，用A2估算平均跳距求U到其他信標(biāo)節(jié)點(diǎn)估計(jì)距離的誤差非常大，導(dǎo)致最終未知節(jié)點(diǎn)定位的誤差也很大。

圖1 誤差分析

2 WDV-Hop算法

由上文誤差分析可知，由于A2和A3實(shí)際距離很近，只是略大于通信半徑，然而A2和A3跳距不止兩跳而是達(dá)到四跳，導(dǎo)致用A2估計(jì)平均跳距產(chǎn)生的誤差很大。針對(duì)誤差分析可以引入加權(quán)系數(shù)[10]。在該算法中，用Wi表示不同信標(biāo)節(jié)點(diǎn)加權(quán)系數(shù)，通過(guò)式3確定：

(3)

其中，ni表示未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)i的跳數(shù)。然后根據(jù)式4計(jì)算未知節(jié)點(diǎn)的加權(quán)平均跳距[11]：

(4)

將加權(quán)平均跳距代入式2，求出未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的估計(jì)距離，最后通過(guò)三邊測(cè)量法或者極大似然估計(jì)法求出未知節(jié)點(diǎn)的坐標(biāo)。

WDV-Hop算法主要是對(duì)傳統(tǒng)DV-Hop算法的第二步進(jìn)行改進(jìn)，通過(guò)修正平均每跳跳距來(lái)提高定位精度，對(duì)第三步計(jì)算未知節(jié)點(diǎn)位置并未涉及。雖然對(duì)平均每跳跳距進(jìn)行加權(quán)修正，但是平均每跳跳距誤差還是依然存在。由于最小二乘法對(duì)測(cè)距敏感，WDV-Hop算法的平均每跳跳距誤差對(duì)節(jié)點(diǎn)的定位精度產(chǎn)生較大的影響。

3 模擬退火加權(quán)DV-Hop算法

在傳統(tǒng)的DV-Hop和加權(quán)DV-Hop算法中，通常采用最小二乘法對(duì)未知節(jié)點(diǎn)的坐標(biāo)進(jìn)行估計(jì)，但基于最小二乘法對(duì)測(cè)距誤差比較敏感，導(dǎo)致由于測(cè)距誤差偏大而使得定位過(guò)程中的定位準(zhǔn)確度降低。故應(yīng)用模擬退火算法加強(qiáng)局部搜索最優(yōu)解，提高定位算法精度。

模擬退火算法[12-14](simulated annealing，SA)是目前應(yīng)用比較廣泛，基于蒙特卡洛迭代的隨機(jī)尋優(yōu)方法。

模擬退火加權(quán)DV-Hop算法的核心思想如下：

(1)通過(guò)加權(quán)DV-Hop算法由式4求出HopSizeavg，然后將其帶入式2求出未知節(jié)點(diǎn)U到信標(biāo)節(jié)點(diǎn)的距離。

(2)選取合適的目標(biāo)函數(shù)。該定位算法中建立合適的目標(biāo)函數(shù)是非常關(guān)鍵的。

圖2 節(jié)點(diǎn)定位示意圖

如圖2所示，設(shè)A1，A2，…，An為信標(biāo)節(jié)點(diǎn)，節(jié)點(diǎn)坐標(biāo)分別為(x1,y1),(x2,y2),…,(xn,yn)。U為未知節(jié)點(diǎn)，坐標(biāo)為(x,y)，未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的估計(jì)距離分別是d1,d2,…,dn。根據(jù)兩點(diǎn)間的距離公式可得：

(5)

令：

(6)

則目標(biāo)函數(shù)為：

(7)

(4)設(shè)置初試溫度T0。

(5)設(shè)置循環(huán)計(jì)算器的初始值K=0。

(6)通過(guò)對(duì)當(dāng)前解的最優(yōu)點(diǎn)做一個(gè)隨機(jī)變動(dòng)來(lái)產(chǎn)生一個(gè)新的最優(yōu)點(diǎn)，計(jì)算其目標(biāo)函數(shù)S2。然后令目標(biāo)函數(shù)的增量Δ=S2-S1。

(7)根據(jù)Metropolis準(zhǔn)則：

(8)

如果Δ<0，則接受新產(chǎn)生的解作為當(dāng)前的最優(yōu)解；如果Δ≥0，以概率e-Δ/T接受新產(chǎn)生的解作為當(dāng)前的最優(yōu)解。

(8)如果k小于終止迭代步數(shù)，k=k+1，然后轉(zhuǎn)向步驟6，否則轉(zhuǎn)向步驟9。

(9)如果溫度T未到達(dá)冷卻狀態(tài)，令T=T×α，α為降溫系數(shù)，取值范圍為0到1，并轉(zhuǎn)向步驟5；如果溫度達(dá)到冷卻狀態(tài)，輸出當(dāng)前的解即為最優(yōu)解，結(jié)束算法。

4 仿真與分析

為評(píng)價(jià)提出的模擬退火加權(quán)DV-Hop算法性能，基于Matlab仿真平臺(tái)對(duì)其進(jìn)行仿真。實(shí)驗(yàn)設(shè)置如下：100個(gè)節(jié)點(diǎn)隨機(jī)散布在100 m×100 m區(qū)域內(nèi)，為使在不同條件下的分析直觀化，將平均定位誤差定義為[15]：

(9)

4.1 基于信標(biāo)節(jié)點(diǎn)個(gè)數(shù)的分析

圖3為信標(biāo)節(jié)點(diǎn)個(gè)數(shù)與算法定位誤差[16]的關(guān)系圖，其中dv為傳統(tǒng)的DV-Hop算法，wdv為加權(quán)DV-Hop算法，wdvth為模擬退火加權(quán)DV-Hop算法。由圖可知，固定其他條件，當(dāng)增加網(wǎng)絡(luò)中信標(biāo)節(jié)點(diǎn)的數(shù)量，三種算法的定位誤差都呈現(xiàn)逐漸下降的趨勢(shì)。主要因?yàn)楫?dāng)信標(biāo)節(jié)點(diǎn)的數(shù)目增加，用于節(jié)點(diǎn)定位的信息也增加，平均誤差也隨之減小。在相同條件下，模擬退火加權(quán)DV-Hop算法的平均誤差下降趨勢(shì)比其他兩

圖3 信標(biāo)節(jié)點(diǎn)個(gè)數(shù)-平均定位誤差

種算法要明顯很多。所以在低密度信標(biāo)節(jié)點(diǎn)網(wǎng)絡(luò)中，文中提出的算法優(yōu)于傳統(tǒng)DV-Hop和加權(quán)DV-Hop。

4.2 通信半徑對(duì)平均定位誤差的影響

圖4為通信半徑與平均定位誤差的關(guān)系圖，固定信標(biāo)節(jié)點(diǎn)的個(gè)數(shù)為10，其他條件不變。通過(guò)改變節(jié)點(diǎn)的通信半徑R來(lái)比較算法的性能。當(dāng)R增大時(shí)，三種算法的平均定位誤差都會(huì)減小。這主要是因?yàn)樵黾油ㄐ虐霃绞沟镁W(wǎng)絡(luò)的連通度[17]提高。連通度表明在一個(gè)網(wǎng)絡(luò)中，能夠與一個(gè)節(jié)點(diǎn)直接進(jìn)行通信的節(jié)點(diǎn)的平均個(gè)數(shù)。由圖可知，在相同條件下，文中改進(jìn)的算法相比其他兩種算法下降趨勢(shì)更加明顯。在圖4中，在橫軸上隨機(jī)取一點(diǎn)，即傳輸半徑不變，wdvth算法的定位誤差在三種算法中最小，所以該算法能夠有效地節(jié)約節(jié)點(diǎn)的能量消耗。

圖4 通信半徑-平均定位誤差

4.3 基于總節(jié)點(diǎn)數(shù)量的分析

圖5是通過(guò)改變節(jié)點(diǎn)的總數(shù)來(lái)考察對(duì)算法對(duì)平均定位誤差的影響。在仿真過(guò)程中，信標(biāo)節(jié)點(diǎn)、通信半徑等條件固定不變，將節(jié)點(diǎn)的總數(shù)從100開(kāi)始逐漸增加。由圖可知，節(jié)點(diǎn)總數(shù)的變化對(duì)算法的平均定位誤差也是有影響的，三種算法的節(jié)點(diǎn)平均定位誤差會(huì)隨著節(jié)點(diǎn)總數(shù)的增加而下降。增加節(jié)點(diǎn)總數(shù)，同時(shí)不改變整個(gè)網(wǎng)絡(luò)的區(qū)域大小，相當(dāng)于提高了網(wǎng)絡(luò)中的節(jié)點(diǎn)密度，使得網(wǎng)絡(luò)的連通度得到提升。雖然三種算法的平均定位誤差都下降，但是相比其他兩種算法模擬退火加權(quán)DV-Hop算法的定位精度明顯高于其他兩種算法。

圖5 總節(jié)點(diǎn)個(gè)數(shù)-平均定位誤差

5 結(jié)束語(yǔ)

文中首先對(duì)傳統(tǒng)定位算法的平均跳距進(jìn)行了加權(quán)修正，更加準(zhǔn)確地對(duì)平均每跳進(jìn)行估計(jì)，減少誤差對(duì)后續(xù)節(jié)點(diǎn)定位的影響。然后針對(duì)最大似然估計(jì)定位抗干擾性較弱，引入模擬退火算法對(duì)未知節(jié)點(diǎn)的坐標(biāo)進(jìn)行最優(yōu)搜索。該算法在提高定位精度上具有明顯的優(yōu)勢(shì)，能夠有效降低由測(cè)距誤差造成的對(duì)定位精度的影響。在信標(biāo)節(jié)點(diǎn)密度較低時(shí)，該算法也能有較高的定位精度，同時(shí)能夠有效地利用網(wǎng)絡(luò)中的通信量，減少節(jié)點(diǎn)的能量消耗，具有較高的實(shí)用價(jià)值。

參考文獻(xiàn)：

[1] YICK J,MUKHERJEE B,GHOSAL D.Wireless sensor network survey[J].Computer Networks,2008,52(12):2292-2330.

[2] MAO Guoqiang,FIDAN B,ANDERSON B D O.Wireless sensor network localization techniques[J].Computer Networks,2007,51(10):2529-2553.

[3] HE Tian,HUANG Chengdu,BLUM B M,et al.Range-free localization schemes for large scale sensor networks[C]//Proceedings of the 9th annual international conference on mobile computing and networking.San Diego:ACM,2003:81-95.

[4] 李再煜.RSSI定位原理的研究與實(shí)現(xiàn)[J].無(wú)線(xiàn)電工程,2013,43(7):8-10.

[5] 姜志鵬,陳正宇,劉 影,等.TOA定位算法非線(xiàn)性?xún)?yōu)化問(wèn)題研究[J].傳感技術(shù)學(xué)報(bào),2015,28(11):1716-1719.

[6] 鄒艷玲,程愛(ài)華.超寬帶室內(nèi)環(huán)境下的TDOA/AOA定位系統(tǒng)[J].微計(jì)算機(jī)信息,2008,24(33):164-166.

[7] ZHANG Bingjiao,JI Minning,SHAN Lianhai.A weighted centroid localization algorithm based on DV-Hop for wireless sensor network[C]//2012 8th international conference on wireless communications,networking and mobile computing.Shanghai,China:IEEE,2012:1-5.

[8] 熊志廣,石為人,許 磊,等.基于加權(quán)處理的三邊測(cè)量定位算法[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(22):99-102.

[9] NICULESCU D,NATH B.DV based positioning in Ad Hoc networks[J].Telecommunication Systems,2003,22(1-4):267-280．

[10] 周杭霞,崔 晨,葉佳駿.一種基于加權(quán)處理和誤差修的DV-Hop定位算法研究[J].傳感技術(shù)學(xué)報(bào),2014,27(12):1699-1703.

[11] 李 琳,趙 可,林志貴,等.基于加權(quán)的三維DV-Hop定位算法[J].控制工程,2015,22(4):761-764.

[12] 李玉增,張雪凡,施惠昌,等.模擬退火算法在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)定位中的應(yīng)用[J].通信技術(shù),2009,42(1):211-213.

[13] 傅文淵,凌朝東.布朗運(yùn)動(dòng)模擬退火算法[J].計(jì)算機(jī)學(xué)報(bào),2014,37(6):1301-1308.

[14] 蔣惠波,劉 彬,袁衛(wèi)華.基于Metropolis準(zhǔn)則的自適應(yīng)隨機(jī)搜索算法研究[J].中國(guó)西部科技,2015,14(3):17-19.

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

[16] WANG Yun,WANG Xiaodong,WANG Demin,et al.Range-free localization using expected hop progress in wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2009,20(10):1540-1552.

[17] 孫小軍,劉三陽(yáng),王志強(qiáng).求解網(wǎng)絡(luò)連通度問(wèn)題的新算法[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(34):82-84.