多功率錨節點輔助的DV-Hop定位算法

陶志勇，魏強，劉影

遼寧工程技術大學電子與信息工程學院，遼寧葫蘆島 125105

多功率錨節點輔助的DV-Hop定位算法

陶志勇，魏強，劉影

遼寧工程技術大學電子與信息工程學院，遼寧葫蘆島 125105

在無線傳感器網絡中，DV-Hop定位算法在計算未知節點到錨節點的距離以及通信半徑之內相鄰節點跳距時存在較大誤差，提出了一種錨節點輔助的分布式定位算法。此算法不需要任何測距技術支持。它是利用錨節點的功率控制，即以不同的發射功率發射信標信號，接收到信標信號的未知節點將這些信標信息記錄。此外還考慮了用全網錨節點來修正單獨錨節點的平均每跳距離，用極大似然法計算節點坐標。Matlab仿真實驗結果表明，在相同網絡環境下，該算法能有效減小距離計算帶來的定位誤差，可適合實際定位情況且具有較高的定位精度。

無線傳感器網絡；節點定位；錨節點；平均每跳距離；極大似然法；距離向量算法

1 概述

無線傳感器網絡（Wireless Sensor Network，WSN），是由大量智能傳感器節點構成，通過無線通信方式構成的一個多跳的網絡系統，具有環境適應性、自組織和低成本的特點。在很多領域已經實施應用，例如目標跟蹤、環境監測、戰場偵察、生物醫療、搶險救災以及工業監控等領域，WSN具有廣闊的應用前景[1-2]。

無線傳感器網絡定位分為自定位和對外定位兩種，其中無線傳感器網絡中定位技術是最關鍵的技術之一。無線傳感器網絡自定位是通過少數已知位置的節點來確定大多數未知節點的位置。傳感器網絡的定位算法一般有以下特點：自組織性、節點數量龐大、動態性、容錯性好、高可靠性、能采用分布式計算的機制、遵守能量高效利用的原則。

根據定位機制，可將現有的無線傳感器網絡自定位算法分兩類：一是基于測距技術的定位算法Range-Based，例如RSSI（Received Signal Strength Indicator）[3]、TOA（Time of Arrival）、TDOA（Time Difference on Arrival）、AOA（Angel of Arrival）；二是基于無需測距的定位算法Range-Free，如DV-Hop（Distance Vector-Hop）算法[4]、凸規劃算法、MDS-MAP算法、質心算法等。

基于測距的定位機制由于實際測量節點間的距離或角度或時間，因此節點需要安裝特殊的硬件設備。通常定位精度相對比較高，但對節點的硬件要求也較高，實現起來較復雜，定位過程中消耗的能量也比較多，而且這些測量信息極易受衰弱、干擾等影響。無需測距定位算法不需要測量節點間的距離或角度，對硬件要求也簡單，實現也方便，適用于部分不需要高精度的場合。因為功耗和成本的因素，所以基于無需測距定位算法受到了廣泛關注。

DV-Hop算法是目前研究和應用最為廣泛的基于無需測距的定位算法，并且對硬件要求較低，實現簡單。但在計算未知節點和錨節點間的距離時估算較粗糙、誤差較大。當節點間跳數為1跳時，不管兩節點之間距離到底多遠或多近，DV-Hop定位算法計算出的距離是一樣的，這就會對定位造成誤差。當節點跳數大于1跳時，大部分節點之間是成折線的不是直線的，算法是用折線距離代替節點之間的實際距離因此也會帶來誤差。如果跳數越多，未知節點與錨節點之間路徑偏離兩點直線連線的可能性越大，計算出的未知節點與錨節點估計距離與真實距離誤差越大。現階段，對DV-Hop算法的改進方法主要有：（1）與其他的定位算法相結合[5]；（2）修正未知節點與錨節點間的距離[6]；（3）改進最后一步的定位計算方法[7]，而對DV-Hop算法本身的參數優化研究較少，定位精度不是很高，適用于定位精度要求比較低的環境中。本文對參數進行了詳細的分析并且提出了一種新的利用錨節點功率控制計算節點間距離，結果表明可以有效地提高DV-Hop算法的定位精度。

2 DV-Hop定位算法過程

DV-Hop算法的基本思想[8-11]：用網絡中節點之間的平均每跳距離和節點間的跳數乘積表示待定位節點間距離，然后采用三邊定位法獲取節點的位置信息。

DV-Hop算法步驟[12-14]：

第1步：計算最小跳數。

第2步：計算各節點間的實際跳數距離。第i個錨節點的平均每跳距離為：

式中(xi，yi)、(xj，yj)為錨節點i、j坐標，hij為錨節點i、j之間的最小跳數。

第3步：定位未知節點位置。將估算的平均每跳距離作為一個校正值廣播至網絡中，待定位的節點接收到校正值后，根據跳數信息計算與參考節點間的距離。利用三邊測量法或極大似然估計法計算出未知節點的位置。

3 多功率錨節點輔助的DV-Hop定位算法

3.1 多功率錨節點分布模型

當未知節點與錨節點間的跳數為1跳時，計算出的估計距離是一個定值。例如，節點隨機分布在網絡環境中，節點的通信半徑R為30 m，根據DV-Hop算法計算得到的平均每跳距離為21 m，假設1跳之內有兩個未知節點a、b，它們到錨節點的實際距離為3 m、15 m。根據算法得出未知節點到錨節點的估計距離均為21 m，則用估計距離21 m代替實際距離3 m和15 m會有很大的誤差。如果能獲得未知節點到錨節點相對更準確的距離無疑能提高未知節點的定位精度，因此本文依據與錨節點進行通信時，控制錨節點的發射功率來調節信號傳輸最大半徑，假如，錨節點有N個級別的發射功率，其對應的信號傳輸最大半徑分別為Ri，i=1，2，…，N。這樣就可以控制錨節點傳輸不同長度的半徑。本文采用錨節點有3級發射功率，如圖1所示，對應半徑就有三種R1、R2、R3，在這里R1取R/3，R2為2R1，R3為R。特殊說明，錨節點有三個通信半徑，未知節點只有一個通信半徑R。

圖1 錨節點3級發射功率節點分布示意圖

錨節點以通信半徑R（即R3）向網絡中廣播位置信息數據包，以得到所有節點到各個錨節點的最小跳數并記錄。其次，錨節點分別再以R1、R2通信半徑向全網廣播，并統計在通信半徑R1范圍內的未知節點和在通信半徑R1、R2之間的未知節點。這樣未知節點到錨節點的距離分為四種情況。第一種情況是統計R1范圍內未知節點到錨節點的距離為1/3×HopSizei；第二種情況是未知節點在R1～R2范圍內，計算估計距離為2/3×HopSizei；第三種情況是未知節點在R2～R范圍內，計算到錨節點的距離是HopSizei；第四種情況就是當跳數大于1跳時，計算估計距離為di。四種情況具體如下式(R=3R1=1.5R2)：

這樣在上面的例子中，未知節點a在R1=10范圍之內，所以就用7 m取代原來的21 m，節點b在通信半徑R1～R2所以就用14 m取代原來的21 m，雖然與實際距離還有誤差，但總比原來的21 m來估計距離無疑提高了不少。使離未知節點1跳的錨節點的估計距離更接近實際距離，這樣就能達到提高定位精度的目的。

3.2 距離校正值修正

在經典的DV-Hop算法中計算每個錨節點的平均每跳距離時，如果算出的平均每跳距離誤差大會造成DV-Hop算法一系列誤差，最終定位肯定不準確。算法中計算平均每跳距離是等于錨節點間距離之和除以錨節點間跳數之和。但是求未知節點到各個錨節點的距離只需最先到達的錨節點平均每跳距離，而未考慮其他節點的影響。本文改進的算法在計算錨節點的平均每跳距離時不僅考慮最先接收到的平均每跳距離，同時也要考慮網絡環境中其他錨節點的平均每跳距離。

根據經典DV-Hop算法求出各個錨節點的平均每跳距離，綜合考慮所有節點對定位精度的影響。把所有錨節點的平均每跳距離求均值定義為全網平均每跳距離。

Hdave為全網平均每跳距離；Hdi為第i個錨節點的平均每跳距離；n為錨節點的個數。

在此基礎上，對Hdave和Hdi求均值得到修正后的錨節點平均每跳距離Hi，這樣就充分地把所有錨節點分布考慮在內，進而達到減小誤差的效果。

利用反饋的思路來驗證求得的平均每跳距離是否誤差較大，從而更進一步改進平均每跳距離。用已經求得的平均每跳距離計算各個錨節點之間的距離——平均每跳距離乘以跳數即得錨節點之間的距離。錨節點是位置已知的節點，各個錨節點之間的真實距離可以得知，比較用平均每跳距離乘以跳數求得的估計距離和真實實際距離兩者之間的差距，并計算誤差。計算平均每跳距離誤差為：

dij為錨節點i，j之間的真實距離，dˉi是錨節點i到錨節點j之間的估計距離，hij為兩錨節點間的跳數，n則為錨節點的總數。

將得到的錨節點平均每跳距離誤差來修正錨節點平均每跳距離Hi，可得出修正后的每個錨節點的平均每跳距離。

最后在利用極大似然估計法定位時當選擇所有錨節點作為未知節點的參考錨節點，其平均定位誤差并不會達到最小誤差的結果，而是選擇其中離未知節點較近的一部分錨節點作為參考節點會有更好的效果，這時得到的估計距離是最接近實際距離的。本文改進的算法定位精度相對提高，為了更直觀，表1列出了本文算法與幾種改進算法的部分數據比較。

表1 不同算法的部分數據比較m

4 實驗結果及分析

為了驗證改進后算法的性能，利用Matlab對本文改進的算法與其他算法進行仿真對比，對比其定位精度。在100 m×100 m的無線傳感器網絡環境中，且仿真結果數據均取自30次仿真的平均值。分別對算法中未知節點數目、錨節點所占比例、節點通信半徑三個參數變化時，定位誤差是如何變化的進行仿真分析。為了便于比較，使用統一的評價標準為平均定位誤差，并對其做通信半徑歸一化處理。其定義式為：

（1）未知節點數目對定位誤差的影響

仿真環境為錨節點數目20，節點通信半徑為30 m，通過改變未知節點數量，觀察對定位算法誤差的影響。

由圖2可知，隨著未知節點個數的不斷增加，各種算法的平均定位誤差均大幅度下降，改進的算法要比其他算法下降幅度大。未知節點到達120之后，誤差下降的幅度逐漸趨于平緩、穩定。因為隨著未知節點數的增加，節點之間聯系更加緊密，加強了網絡的連通性。

圖2 未知節點與定位誤差關系

（2）錨節點比例對定位誤差的影響

節點總數200，節點通信半徑R分別為30 m、20 m、15 m三種情況下，觀察錨節點比例對平均定位誤差的影響。

圖3是當節點通信半徑為30 m時，錨節點數量的增加與平均定位誤差的關系圖。從圖中可以明顯看出，隨著錨節點個數的不斷增加，定位誤差均呈現降低的趨勢。但是，當錨節點的數量相同時，本文提出的算法下降速度要快于其他算法。

圖3 錨節點與平均定位誤差關系圖（R=30）

圖4和圖5是當節點通信半徑為20 m和15 m時，錨節點數量的增加與算法平均定位誤差的關系圖。均是隨著錨節點數量的增加，所有算法平均定位誤差迅速下降，下降到一定程度趨于平緩，改進的算法要比其他算法下降得快。

圖4 錨節點與平均定位誤差關系圖（R=20）

圖5 錨節點與平均定位誤差關系圖（R=15）

（3）不同通信半徑下，本文算法平均定位誤差關系

圖6是在不同的通信半徑下，改進算法的誤差隨錨節點的變化情況。隨著節點通信半徑的增加，錨節點的增加平均定位誤差均明顯下降，且通信半徑為30 m時，算法性能最好，定位誤差最低。

圖6 不同通信半徑下，本文算法平均定位誤差關系圖

5 結束語

本文對DV-Hop無線傳感器網絡節點定位算法進行了研究，首先簡單介紹了原始DV-Hop算法流程，并簡要分析了算法的不足。提出了一種多功率錨節點輔助定位方法，使用不同發射功率來控制錨節點傳輸不同的通信半徑，保證了1跳之內節點間距離更加精確，進一步為校正值選取提供了可靠的數據，并且對DV-Hop算法本身的參數進行優化，最后對改進算法進行仿真。仿真結果顯示，本文提出的算法其性能更好，有效地提高了算法的定位精度，網絡節點覆蓋率，算法的適應性更強。

[1]趙靈鍇，洪志全.基于無線傳感器網絡的DV-Hop定位算法的改進[J].計算機應用，2011，31（5）：1189-1192.

[2]Qiu R C，Zhang Changchun，Hu Zhen，et al.Towards a largescale cognitive radio network tested spectrum sensing system architecture and distributed sensing[J].Journal of Communications，2012，7（7）：552-566.

[3]Chen Xiaoyan，Pei Yanli.The application of QGA in sensor optimization design[C]//Proc of the 6th International Conference on Distributed Computing and Applications for Business，Engineering and Sciences，Wuhan，China，2007：14-17.

[4]Shihong Duan，Yadong Wan，Zhiqiang Guo，et al.RAAH：Reliability Aware Adaptive Hopping scheme on timevarying channel model in WSN[J].JCIT，2013，8（1）：16-25.

[5]胡斌，立方敏.基于RSSI量化模型的定位算法研究[J].武漢理工大學學報，2009，31（23）：92-95.

[6]劉少飛，趙清華，王華奎.基于平均跳距估計和位置修正的DV-Hop定位算法[J].傳感技術學報，2009，22（8）：1154-1158.

[7]王書鋒，侯義斌，黃樟欽.無線感知網絡最小二乘法定位算法的誤差分析與優化[J].系統仿真學報，2009，21（19）：6211-6215.

[8]Qiu Lele，Hu Yanjun，Wang Yi，et al.A novel multimedia transmissionmethodbasedonquantizedcompressive sensing for Wireless Sensor Network[J].IJACT，2013，5（1）：496-504.

[9]Zhao Chanchan，Hai Xiaowei，Jiang Xiaohua，et al.Coal mine environment monitoring with Wireless Sensor Networks[J].IJACT，2013，5（1）：505-514.

[10]He T，Huang C，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 Press，2003： 81-95.

[11]張震，閆連山，劉江濤，等.基于DV-Hop的無線傳感器網絡定位算法研究[J].傳感技術學報，2011，24（10）：1469-1472.

[12]王麗俠.無線傳感器網絡中DV-Hop算法的研究及改進[J].唐山學院學報，2013，26（3）：75-78.

[13]王穎，石昊旸.改進的無線傳感器網絡DV-Hop定位算法[J].計算機工程，2012，38（7）：66-69.

[14]Wang Guo，Juan Wei.Optimization research of the DVHop localization algorithm[J].TELKOMNIKA Indonesian Journal of Electrical Engineering，2014，12（4）：2735-2742.

[15]顧亦然，蔣璐璐.無線傳感器網絡定位算法研究[D].南京：南京郵電大學，2012：23-30.

TAO Zhiyong,WEI Qiang,LIU Ying

School of Electronic and Information Engineering,Liaoning Technical University,Huludao,Liaoning 125105,China

In wireless sensor networks,aiming at the default that DV-Hop localization algorithm has large errors in the calculation of the distance of unknown node to an anchor node and the jump distance of the adjacent nodes in the communication radius,this paper presents an auxiliary anchor node distributed localization algorithm.This algorithm does not require any ranging technical support.It uses the power control of the anchor nodes by sending the beacon signals with different transmit powers,and the unknown nodes which receive the beacon signals will record the beacon information.It uses whole network anchors to fix separate anchor nodes on per hop distance,and then calculates the coordinates of nodes with great natural method.The Matlab simulation results show that in the same network environment,this algorithm can effectively reduce positioning errors caused by distance calculation and is suitable for the actual situation with high accuracy.

Wireless Sensor Networks（WSN）;node location;anchor;average hop distance;maximum likelihood method; Distance Vector（DV）-Hop algorithm

A

TP393

10.3778/j.issn.1002-8331.1403-0101

TAO Zhiyong,WEI Qiang,LIU Ying.Improved DV-Hop localization algorithm based on more power auxiliary anchor nodes.Computer Engineering and Applications,2014,50（21）：121-124.

遼寧工程技術大學研究生學院第五屆科研立項（No.5A2014029-01）。

陶志勇（1978—），男，博士研究生，副教授，主要研究方向：無線傳感器網絡、多媒體通信；魏強（1988—），男，通訊作者，碩士研究生，主要研究方向：無線傳感器網絡；劉影（1983—），女，博士研究生，主要研究方向：無線傳感器網絡。E-mail：1102773015@qq.com

2014-03-11

2014-04-26

1002-8331（2014）21-0121-04

CNKI出版日期：2014-07-02，http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1403-0101.html