DV-Hop算法中未知節點獲取校正值的改進方法

狄振強，馬淑麗，趙建平，劉鳳霞

(曲阜師范大學 物理工程學院,山東 曲阜 273165)

?

DV-Hop算法中未知節點獲取校正值的改進方法

國家自然科學基金資助項目(No.11404185)；山東省高等學?？萍加媱濏椖抠Y助(No.J12LN08)；曲阜師范大學技術開發項目(No.hxkj2015017)Foundation Item:National Natural Science Foundation of China(No.11404185); Supported by the Science and Technology Project of Higher Education of Shandong Province(No.J12LN08); Qufu Normal University Technology Development Project(No.hxkj2015017)

狄振強，馬淑麗，趙建平，劉鳳霞

(曲阜師范大學 物理工程學院,山東 曲阜 273165)

無線傳感器網絡中，大量傳感器節點隨機部署。在DV-Hop定位算法中，未知節點根據校正值和與錨節點間的最小跳數值估算自身與錨節點間的距離。校正值的選擇和計算方法有多種。對比多種取校正值的方法，并提出兩種新的計算校正值方法。MATLAB仿真表明，各種取校正值的方法在一定的通信半徑下各占優勢。新的計算校正值方法在相同條件下比其他方法明顯占優勢。改進的DV-Hop算法比一般的DV-Hop算法、加權的DV-Hop算法、最佳指數值下DV-Hop算法定位精度分別提高2.38%、1.96%、1.31%，同時不會增加網絡硬件成本。

無線傳感器網絡;節點定位;加權DV-Hop算法;最小均方差

0　引　言

無線傳感器網絡(WSN, Wireless Sensor Network) 主要由大量傳感器節點組成，可以應用于環境監測、精準農業、軍事等領域。一般，在比較偏僻、無人值守的網絡環境中，大量節點隨機拋撒部署。由于成本等原因，少數節點已知自己的坐標，被稱為信標節點或錨節點。剩余的大部分節點需要依靠網絡中的錨節點估算自身坐標，這部分節點稱為未知節點。在定位技術中，無需測距的定位算法由于簡單、成本低受到廣泛關注[1]。其中，國內外研究較多的是DV-Hop算法、APIT(Approximate Point-In-Triangulation Test)算法及衍生的算法等。由于無需測距定位算法定位精度不高[2]，許多學者通過改進算法來提高定位精度。關于改進DV-Hop算法的文獻很多，大多是改進錨節點部署策略、改進最小二乘法、改進錨節點平均每一跳距離計算、改進定位條件等方面[3]。本文從校正值的計算和選擇方面入手，改進DV-Hop算法。首先，列舉并對比其他文獻提出的一系列改進未知節點選擇和計算校正值的方法。然后，提出兩種新的未知節點獲取校正值方法。最后，進行實驗仿真對比。經實驗證明改進的方法能提高DV-Hop算法定位精度。

本文的結構安排，第一部分，基本概述，包括DV-Hop算法及其定位誤差分析。第二部分，列舉了一些文獻提出的未知節點選取和計算校正值的方法。第三部分，提出本文兩種創新方法。第四部分，實驗仿真，驗證本文提出的新的方法的有效性。最后一部分，總結。

1　基本概念

1.1DV-Hop定位算法

Dragos Niculescu(美國羅格斯大學，Rutgers University)等人在2003年提出了6種分布式定位算法，其中包括DV-Hop定位算法[4]。

在無線傳感器網絡中，DV-Hop算法定位步驟如下：

(1)網絡中的錨節點以泛洪的方式向周圍廣播包含自身坐標和初始跳數值0的數據包。接收節點保存數據包，將跳數值自加1后轉發數據包出去。在不斷的轉發過程中，接收節點只保留跳數值較小的數據包，遇到比自己保留的跳數值大的數據包則拋棄。

(2)計算錨節點平均每一跳距離。錨節點將自己的平均每一跳距離值廣播出去。

(3)未知節點選擇性的接收廣播信息并作為自己的平均每一跳距離(我們將未知節點選擇的平均每一跳距離稱為校正值)。用校正值乘以未知節點與每個錨節點間的最小跳數值，得到未知節點與每個錨節點間的估算距離。

最后，當未知節點獲得與至少三個錨節點的距離時，可以用三邊測量法[5]、極大似然估計法等估算坐標。

極大似然估計法：

(1)

AX=b

(2)

(3)

(4)

X=(ATA)-1ATb

(5)

(x,y)為未知節點坐標，di為未知節點與錨節點i間的估算距離。

1.2誤差分析

基于無需測距的定位算法比基于測距的定位算法定位精度低，最主要的原因：基于測距的定位算法能夠獲得節點間較為精確的距離或角度信息，而無需測距的定位算法只能估算節點間的距離等信息。

如DV-Hop算法的第二至第三步，未知節點獲取校正值，并將校正值乘以最小跳數值得到與錨節點間的距離。只是利用錨節點的坐標信息和信息傳輸過程中記錄的跳數值來估算距離，誤差較大[6]。如圖1所示，網絡中節點部署是隨機的，節點間的距離有大有小，而在信息傳輸過程中跳數值記錄為1對應的實際跳段距離也是有大有小。未知節點用跳數值乘以校正值獲得與錨節點間的估算距離，誤差很大。所以，需要選擇合適的校正值來減小估算距離誤差，從而提高定位精度。

圖1　網絡結構

2　計算或選擇校正值方法

校正值會影響未知節點與錨節點間估算距離的誤差。所以為了提升DV-Hop算法定位精度，許多文獻從DV-Hop算法的第二和第三步入手，提高節點定位精度。本文研究了許多文獻，并總結了7種校正值獲取和計算的方法。如下：

(1)最常用的獲取校正值方法。

許多文獻如文獻[7]，在第二步，利用無偏估計準則求錨節點的平均每一跳距離(dHopi)。首先，錨節點i計算出自己與其他錨節點(如錨節點j)間的距離dij。無偏估計準則需要滿足：

(6)

然后，將錨節點i與其他所有錨節點間的距離累加，除以與其它錨節點(如錨節點j)間的最小跳數值hij的累加值，得到錨節點i的平均每一跳距離dHopi，如式(7)：

(7)

式中，xi，yi是錨節點i坐標值，xj，yj是錨節點j坐標值。

就近原則獲取校正值，是大多數文獻采用的方法。在第三步，未知節點只接收最近的錨節點的平均每一跳距離信息，即只接受第一個送達的平均每一跳距離信息，并將其作為自己的校正值。

(2)文獻[1，5，8，9]求錨節點的平均每一跳距離公式如式(7)。未知節點對所有錨節點的平均每一跳距離取平均值后作為自己的校正值，即網絡中所有未知節點的校正值相同。公式如下：

(8)

n為網絡中錨節點個數。

(3)文獻[2，10]。未知節點根據每個錨節點與自己距離的遠近影響校正值的大小。首先，未知節點獲取所有錨節點的平均每一跳距離，公式如式(7)。然后對每個錨節點的平均每一跳距離進行加權。

如式(9)，對錨節點j的加權系數Mji：

(9)

對錨節點j的平均每一跳距離進行加權處理：

MDji=Mji×dHopj

(10)

式(10)中dHopj由式(7)計算而來。將每個錨節點加權處理后的平均每一跳距離累加，得到未知節點的校正值。未知節點i的校正值為：

(11)

未知節點i與錨節點f(f取1～n)的估算距離為：

dif=MJi×hif

(12)

(4)文獻[11]。利用最小均方差準則，錨節點平均每一跳距離滿足：

(13)

對上式求關于dHopi的偏導，并將等式取零，得到最小均方誤差下的求dHopi公式：

(14)

未知節點只接收離自己最近的錨節點發過來的平均每一跳距離信息。

(5)文獻[12]。首先，用最小均方差準則求錨節點平均每一跳距離，如式(14)。然后，未知節點接收所有錨節點廣播的平均每一跳距離。在計算未知節點與錨節點間估算距離時，求到哪個錨節點的距離用哪個錨節點的平均每一跳距離，即在DV-Hop算法的第三步未知節點i與錨節點j的估算距離為：

(15)

(6)文獻[13]，也就是本文作者的另一篇論文提出的創新方法。改進式(14)，提出最佳指數值概念，在最佳值下求錨節點平均每一跳距離。研究發現指數在取非2時，取1.9～2.0間的數時能提高定位精度。公式如下：

(16)

未知節點只接收離自己最近的錨節點發過來的平均每一跳距離信息

(7)文獻[14]，也是本文作者的另一篇論文提出的創新方法。將文獻[9，12]的算法結合，提出最佳指數值下的加權DV-Hop算法。首先，用最佳指數值下的最小均方差準則求錨節點平均每一跳距離，如式(16)。然后，未知節點接收保留所有錨節點廣播來的平均每一跳距離。并按照文獻[2,10]的方法對每個錨節點的平均每一跳距離進行加權處理。最后，未知節點將每個錨節點加權處理后的平均每一跳距離累加，得到自身校正值。

3　改進的計算或獲取校正值方法

本文提出兩種新的未知節點選擇和計算校正值的方法。

3.1改進方法一

第一種方法：我們對比第二節中未知節點計算和選擇校正值的方法，發現錨節點利用最小均方差準則計算平均每一跳距離時誤差較小，錨節點用改進的計算式(16)求平均每一跳距離時誤差進一步減小。在未知節點選擇校正值時，就近原則選取校正值的方法定位誤差較大，而采用所有錨節點的平均每一跳距離參與到校正值計算時，定位誤差較小。

所以，本文嘗試并提出將所有錨節點在文獻[12]最佳指數值下求錨節點平均每一跳距離的平均值作為未知節點的校正值。公式如下：

(17)

經過多次實驗仿真，發現本文提出的未知節點選取校正值的方法可以明顯的提高定位精度。

3.2改進方法二

第二種方法：我們將所有的錨節點平均每一跳距離都參與到校正值的計算。在DV-Hop算法中，未知節點需要計算與所有錨節點間的距離，然后，才能用最小二乘法或者三邊測量法計位置。我們在未知節點計算與某個錨節點間的距離時，用該錨節點的平均每一跳距離乘以該錨節點與該未知節點間的最小跳數值。也就是說，用求到誰的距離用誰的平均每一跳距離。錨節點平均每一跳距離的計算公式仍然用在最佳指數值下的公式(16)。

求未知節點i求與錨節點j間的距離時，公式如下：

(18)

經過實驗仿真，發現本文第二種方法也能減小節點定位誤差，提高DV-Hop算法定位精度。

4　實驗仿真

將無線傳感器網絡區域假設為100 m×100 m的正方形，其中隨機部署100個傳感器節點，錨節點的覆蓋率為9%，傳感器節點的無線通信半徑取22～45 m范圍。將文獻[9-14]提出的未知節點選擇和計算校正值的7種方法和本文提出的兩種方法對比，為了便于區分，將本文第一、二種方法分別用DV-Hop(A)、DV-Hop(B)表示，如圖2所示。

(a)文獻[9]

(b)文獻[10-11]

(c)文獻[11-12]

(d)文獻[13-14]

(e)DV-Hop(A)

(f)DV-Hop(B)

經實驗對比，如圖2(a)、圖2 (b)、圖2 (c) 所示，文獻[8-11]提出的未知節點選擇和計算校正值的方法并不能明顯的提高DV-Hop算法定位精度。如圖2(d)所示，本文作者在文獻[12-13]中提出的創新方法可以明顯的提升定位精度。如圖2(e)、圖2(f)所示，本文作者在本文提出的兩種新的未知節點選擇和計算校正值的方法，可以在一定條件下比一般常用的方法大大的提高定位精度。本文第一種方法,用所有錨節點參與定位，即所有未知節點校正值相同，且每個錨節點的平均每一跳距離在最佳指數下計算時，定位精度比其他8種方法都占優勢，如圖2(e)所示。通信半徑為35m時，本文兩種方法分別比一般方法提高定位精度3%、2%左右。

5　結　語

無線傳感器網絡中無需測距定位算法的定位精度受限于未知節點的校正值和計算與錨節點間的估算距離。本文收集了一些未知節點校正值選擇和計算的方法，并分別仿真對比。然后，提出兩種新的未知節點校正值計算和選擇方法。經過Matlab仿真證明，本文方法可以有效提高定位精度，總體上可以提升約3%的定位精度，換算到實際中可以將定位誤差減小1 m左右。下一步，將研究基于多通信半徑的定位算法，并將本文方法應用到其中。

[1]CHEN H, Sezaki K, DENG P, HC So. An Improved DV-Hop Localization Algorithm with Reduced Node Location Error for Wireless Sensor Networks. Ieice Transactions on Fundamentals of Electronics Communications & Computer Sciences. 2008, 91-a(8):2232-2236.

[2]YANG Xiao-ying, SONG Qi-xiang. An Improved DV-Hop Algorithm for Resisting Wormhole Attack. The Open Cybernetics & Systemics Journal,2015,9,1443-1448.

[3]DING J, ZHANG L,CHENG G, LING Z,ZHANG Z. Study on DV-Hop Algorithm based on Modifying Hop Count for Wireless Sensor Networks. International Journal of Computer Science Engineering & Technolo, Oct2012, Vol. 2 Issue 10, p1452.

[4]Niculescu D, Nath B. Ad-Hoc Positioning System(APS)[J].IEEE Global Telecommunications,2001,5:2926-2931.

[5]ZHANG Shu-peng. Wireless Sensor Network Positioning Technology Research [D] Guangzhou: South China University of Technology, 2010.

[6]YANG H, WANG Q, LIU Z. A Wireless Sensor Network DV-Hop Localization Algorithm. International Conference on Information Science & Computer Applications, 2013, 92:281-286.

[7]CHEN Xiao and ZHANG Ben-liang. Improved DV-Hop Node Localization Algorithm in Wireless Sensor Networks. International Journal of Distributed Sensor Networks, vol.2012, Article ID 213980, 7 pages, 2012.

[8]WU Hua-rui, GAO Rong-hua. An Improved Method of DV-Hop Localization Algorithm. Journal of Computational Information Systems 7:7(2011) 2293-2298.

[9]賈琦,周新志.基于無線傳感器網DV-Hop定位算法的改進和研究[J]. 計算機測量與控制,2013，21(11): 3043-3046.

JIA Qi, ZHOU Xin-zhi. Improvement and Research on DV-Hop Localization Algorithm for Wireless Sensor Networks[J]. Chinese Journal of Computer Measurement & Control，2013.21(11):3043-3046.

[10]馮江,朱強,吳春春.改進的DV-Hop定位算法研究[J].計算機工程,2012,38(19):74-81.FENG Jiang, ZHU Qiang, WU Chun-chun. Research on Improved DV-Hop Localization Algorithm[J]. Chinese Journal of Computer Engineering,2012,38(19):74-81.

[11]魏全瑞,劉俊,韓九強.改進的無線傳感器網絡無偏距離估計與節點定位算法[J].西安交通大學學報,2014, 48(06):1-6.

WEI Quan-rui,LIU Jun,HAN Jiu-qiang. An Improved DV-Hop Node Localization Algorithm based on Unbiased Estimation for Wireless Sensor Networks[J]. Journal of Xi’an Jiaotong University,2014,48(06):1-6.

[12]嵇瑋瑋,劉中.DV-Hop定位算法在隨機傳感器網絡中的應用研究[J].電子與信息學報,2008,30(04):970-974.

JI W W,LIU Z. Study on the Application of DV-Hop Localization Algorithms to Random Sensor Networks[J]. Chinese Journal of Electronics & Information Technology, 2008，30(04):970-974.

[13]馬淑麗,趙建平.無線傳感器網絡中DV-Hop定位算法的改進[J]. 通信技術,2015,48(07):840-844.

MA S L,ZHAO J P,ZHANG B T. The Improvement of DV-Hop Algorithm in Wirless Sensor Networks[J]. Chinese Journal of Communications Technology, 2015,48(07):840-844.

[14]馬淑麗,趙建平. WSN中基于最佳指數的加權DV-Hop算法[J].通信技術,2015,48 (10):1147-1151.

MA S L,ZHAO J P,ZHANG B T. Weighted DV-Hop Algorithm based on Optimal Index in WSN[J]. Chinese Journal of Communications Technology, 2015, 48(10):1147-115.

狄振強(1965—)，男，副教授，主要研究方向為無線通信技術、物聯網技術；

馬淑麗(1989—)，女，碩士研究生，主要研究方向為無線傳感器網絡、無線通信技術；

趙建平(1964—)，男，教授，主要研究方向為無線通信技術；

劉鳳霞(1988—)，女，碩士研究生。主要研究方向為智能信息處理。

A Modified Method for Obtaining Correction Value of Unknown Nodes in DV-Hop Algorithm

DI Zhen-qiang，MA Shu-li，ZHAO Jian-ping，LIU Feng-xia

(College of Physics Engineering,Qufu Normal University,Qufu Shandong 273165,China)

In wireless sensor networks, a large number of nodes are randomly distributed. In DV-Hop localization algorithm, the unknown nodes estimate the distance between themselves and the anchor nodes in accordance with the corrected value and the minimum hop count between the anchor nodes. There are various method for selection and calculation of the correction value. After the comparison of multiple methods, two novel methods for calculating the correction value are proposed. MATLAB simulation indicates that various methods for obtaining correct values enjoy different advantages under a certain communication radius. The novel calculation method is clearly superior to other methods in same conditions. The positioning accuracy of modified DV-Hop algorithm is improved by 2.38%, 1.96%, 1.31% respectively as compared with that of DV-Hop algorithm, the weighted DV-Hop algorithm,and the DV-Hop algorithm of optimal index value,without any increase of network hardware cost.

wireless sensor network; node localization; weighted DV-Hop algorithm; minimum mean square error

10.3969/j.issn.1002-0802.2016.03.015

2015-10-11；

2016-01-26Received date:2015-10-11；Revised date：2016-01-26

TP393

A

1002-0802(2016)03-0329-06