張治華，張玲華

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

0 引 言

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

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

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

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

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

1.1 計算未知節(jié)點與每個信標節(jié)點的最小跳數(shù)

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

1.2 計算未知節(jié)點與每個信標節(jié)點的估計距離

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

(1)

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

1.3 計算未知節(jié)點的自身位置

通過式2計算未知節(jié)點u到信標節(jié)點的估計距離du,i：

du,i=HopSize·hu,i

(2)

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

當未知節(jié)點得到3個或者更多節(jié)點之間的距離后，再通過三邊測量法[9]或者極大似然法等數(shù)學方法計算未知節(jié)點的坐標。

1.4 算法的誤差分析

在DV-Hop定位算法中，用未知節(jié)點到信標節(jié)點的最小跳數(shù)乘以平均跳距來計算未知節(jié)點到信標節(jié)點的距離。

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

圖1 誤差分析

2 WDV-Hop算法

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

(3)

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

(4)

將加權平均跳距代入式2，求出未知節(jié)點到信標節(jié)點的估計距離，最后通過三邊測量法或者極大似然估計法求出未知節(jié)點的坐標。

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

3 模擬退火加權DV-Hop算法

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

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

模擬退火加權DV-Hop算法的核心思想如下：

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

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

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

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

(5)

令：

(6)

則目標函數(shù)為：

(7)

(4)設置初試溫度T0。

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

(6)通過對當前解的最優(yōu)點做一個隨機變動來產(chǎn)生一個新的最優(yōu)點，計算其目標函數(shù)S2。然后令目標函數(shù)的增量Δ=S2-S1。

(7)根據(jù)Metropolis準則：

(8)

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

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

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

4 仿真與分析

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

(9)

4.1 基于信標節(jié)點個數(shù)的分析

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

圖3 信標節(jié)點個數(shù)-平均定位誤差

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

4.2 通信半徑對平均定位誤差的影響

圖4為通信半徑與平均定位誤差的關系圖，固定信標節(jié)點的個數(shù)為10，其他條件不變。通過改變節(jié)點的通信半徑R來比較算法的性能。當R增大時，三種算法的平均定位誤差都會減小。這主要是因為增加通信半徑使得網(wǎng)絡的連通度[17]提高。連通度表明在一個網(wǎng)絡中，能夠與一個節(jié)點直接進行通信的節(jié)點的平均個數(shù)。由圖可知，在相同條件下，文中改進的算法相比其他兩種算法下降趨勢更加明顯。在圖4中，在橫軸上隨機取一點，即傳輸半徑不變，wdvth算法的定位誤差在三種算法中最小，所以該算法能夠有效地節(jié)約節(jié)點的能量消耗。

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

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

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

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

5 結束語

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

參考文獻：

[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定位原理的研究與實現(xiàn)[J].無線電工程,2013,43(7):8-10.

[5] 姜志鵬,陳正宇,劉 影,等.TOA定位算法非線性優(yōu)化問題研究[J].傳感技術學報,2015,28(11):1716-1719.

[6] 鄒艷玲,程愛華.超寬帶室內(nèi)環(huán)境下的TDOA/AOA定位系統(tǒng)[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] 熊志廣,石為人,許 磊,等.基于加權處理的三邊測量定位算法[J].計算機工程與應用,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] 周杭霞,崔 晨,葉佳駿.一種基于加權處理和誤差修的DV-Hop定位算法研究[J].傳感技術學報,2014,27(12):1699-1703.

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

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

[13] 傅文淵,凌朝東.布朗運動模擬退火算法[J].計算機學報,2014,37(6):1301-1308.

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

[15] 張新榮,熊偉麗,徐保國.采用RSSI模型的無線傳感器網(wǎng)絡協(xié)作定位算法[J]. 電子測量與儀器學報,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] 孫小軍,劉三陽,王志強.求解網(wǎng)絡連通度問題的新算法[J].計算機工程與應用,2009,45(34):82-84.