陶志勇，魏強，劉影

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

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

陶志勇，魏強，劉影

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

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

無線傳感器網(wǎng)絡；節(jié)點定位；錨節(jié)點；平均每跳距離；極大似然法；距離向量算法

1 概述

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

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

根據(jù)定位機制，可將現(xiàn)有的無線傳感器網(wǎng)絡自定位算法分兩類：一是基于測距技術(shù)的定位算法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]、凸規(guī)劃算法、MDS-MAP算法、質(zhì)心算法等。

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

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

2 DV-Hop定位算法過程

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

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

第1步：計算最小跳數(shù)。

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

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

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

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

3.1 多功率錨節(jié)點分布模型

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

圖1 錨節(jié)點3級發(fā)射功率節(jié)點分布示意圖

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

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

3.2 距離校正值修正

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

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

Hdave為全網(wǎng)平均每跳距離；Hdi為第i個錨節(jié)點的平均每跳距離；n為錨節(jié)點的個數(shù)。

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

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

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

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

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

表1 不同算法的部分數(shù)據(jù)比較m

4 實驗結(jié)果及分析

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

（1）未知節(jié)點數(shù)目對定位誤差的影響

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

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

圖2 未知節(jié)點與定位誤差關(guān)系

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

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

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

圖3 錨節(jié)點與平均定位誤差關(guān)系圖（R=30）

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

圖4 錨節(jié)點與平均定位誤差關(guān)系圖（R=20）

圖5 錨節(jié)點與平均定位誤差關(guān)系圖（R=15）

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

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

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

5 結(jié)束語

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

[1]趙靈鍇，洪志全.基于無線傳感器網(wǎng)絡的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].傳感技術(shù)學報，2009，22（8）：1154-1158.

[7]王書鋒，侯義斌，黃樟欽.無線感知網(wǎng)絡最小二乘法定位算法的誤差分析與優(yōu)化[J].系統(tǒng)仿真學報，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的無線傳感器網(wǎng)絡定位算法研究[J].傳感技術(shù)學報，2011，24（10）：1469-1472.

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

[13]王穎，石昊旸.改進的無線傳感器網(wǎng)絡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]顧亦然，蔣璐璐.無線傳感器網(wǎng)絡定位算法研究[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.

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

陶志勇（1978—），男，博士研究生，副教授，主要研究方向：無線傳感器網(wǎng)絡、多媒體通信；魏強（1988—），男，通訊作者，碩士研究生，主要研究方向：無線傳感器網(wǎng)絡；劉影（1983—），女，博士研究生，主要研究方向：無線傳感器網(wǎng)絡。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