李亞杰 杜春暉 吉高卿

(河北建筑工程學院，河北 張家口 075000)

基于DV-Hop算法改進的研究

李亞杰 杜春暉 吉高卿

(河北建筑工程學院，河北 張家口 075000)

對無線傳感器網(wǎng)絡(luò)中的DV-Hop的定位算法進行了研究和分析，它是一種基于無需測距的無線傳感器網(wǎng)絡(luò)的定位算法.針對DV-Hop根據(jù)全部網(wǎng)絡(luò)的數(shù)據(jù)計算單跳距離，通信負擔大，而且對于錨節(jié)點分布不均和稀疏節(jié)點網(wǎng)絡(luò)，定位精度差，提出把網(wǎng)絡(luò)分局部和分區(qū)域.針對非測距算法的定位精度粗糙，在DV-Hop后，加入分布式迭代算法，進一步提高定位的精度.通過對算法的仿真，得出該算法定位精度提高，和改進算法的一些特定應(yīng)用環(huán)境.

DV-Hop；節(jié)點定位；距離約束；定位算法

0 引 言

DV-Hop算法是由Niculescud等人提出的，一種非測距的無線傳感器網(wǎng)絡(luò)的定位算法.該算法依賴于軟件和編程，不需要任何的其他硬件.算法的核心思想是利用未知節(jié)點到錨節(jié)點的跳數(shù)乘以每跳的估算距離，得到三個或者以上的位置信息，則可以利用三邊算法或者最大似然估計來計算節(jié)點的位置.由于每跳距離是估算的，定位精度粗糙，本文對定位精度和網(wǎng)絡(luò)的類型來展開研究，在此算法的基礎(chǔ)之上進行相應(yīng)的改進，通過matlab仿真顯示能明顯提高定位的精度.

1 DV-Hop基本過程

算法的基本過程由三步構(gòu)成:(1)網(wǎng)絡(luò)中廣播消息，通過信息交互，節(jié)點獲得到錨節(jié)點的跳數(shù).(2)根據(jù)步驟(1)獲得的消息，計算網(wǎng)絡(luò)中跳數(shù)的平均距離，讓跳數(shù)乘以平均距離獲得未知節(jié)點到錨節(jié)點之間的距離信息.(3)當未知節(jié)點獲得三個或者以上的位置信息后，通過三邊測量法或極大似然估計法計算自身位置[1].

DV-Hop算法的定位過程分為三個階段[2]：

(1)錨節(jié)點向周圍網(wǎng)絡(luò)廣播自己的位置信息和分組信息，其中包括跳數(shù)字段，初始化為0.接收節(jié)點記錄具有到每個信標節(jié)點的最小跳數(shù)，忽略來自同一個信標節(jié)點的較大跳數(shù)的分組.然后將跳數(shù)加1，并轉(zhuǎn)發(fā)給鄰居節(jié)點.通過這個方法，網(wǎng)絡(luò)中的所有節(jié)點能夠記錄下到每個信標節(jié)點的最小跳數(shù).

(2)計算未知節(jié)點和信標節(jié)點的實際跳段距離.每個信標節(jié)點根據(jù)第一階段中記錄的其他信標節(jié)點的位置信息和相距跳數(shù)，利用公式(1.1)估算平均每跳的實際距離.

(1.1)

其中，(xi,yi)，(xj,yj)是信標節(jié)點i，j的坐標，hj是信標節(jié)點i與j(j≠i)之間的跳段數(shù).然后，信標節(jié)點將計算的每跳平均距離用帶有生存期字段的分組廣播至網(wǎng)絡(luò)中，未知節(jié)點僅記錄接收到的第一個每跳平均距離，并轉(zhuǎn)發(fā)給鄰居節(jié)點.這個策略確保了大多數(shù)節(jié)點從最近的信標節(jié)點接收到每跳平均距離值.未知節(jié)點接收到平均每跳距離后，根據(jù)記錄的跳數(shù)，計算到每個信標節(jié)點的跳段距離.

(3)利用三邊測量法或極大似然估計法計算自身位置.

(1.2)

其中公式(1.2)是三邊算法.

2 DV-Hop算法的改進

2.1 算法局部化的改進

根據(jù)本文前面的分析和論述，就DV-Hop算法進行相應(yīng)的修改，對于算法的流程大家已經(jīng)很清楚，下面就改動的部分做詳細的闡述.

在算法的第一步中，錨節(jié)點不再向網(wǎng)絡(luò)中的全部節(jié)點廣播位置信息，在廣播過程中，加入廣播信息跳數(shù)的限制選項n，就不再向n跳意外的節(jié)點發(fā)送消息.這樣可以大大減輕網(wǎng)絡(luò)的通信負擔，每個區(qū)域也都會形成局部的網(wǎng)絡(luò)[4].

在估算平均每跳距離的算法的第二步中，錨節(jié)點選擇自本節(jié)點范圍內(nèi)的m個錨節(jié)點，這樣處理既可以保證如實反映網(wǎng)絡(luò)節(jié)點的分布情況，有減少不必要的通信，同時未知節(jié)點的定位的準確度，在各向異性的網(wǎng)絡(luò)中，該算法同樣適用.

2.2 協(xié)作優(yōu)化階段

根據(jù)第一步的DV-hop得到的每個位置的精度不是很高的位置信息，可利用質(zhì)量-彈簧模型對定位的精度迭代優(yōu)化.從計算量和定位精度的綜合考慮，只考慮基于2跳范圍連通性約束.具體的步驟如下：

(1)每個未知節(jié)點ni向網(wǎng)絡(luò)中廣播自己的當前的計算坐標Pi，并從它的周圍2跳范圍內(nèi)獲取它的估計的坐標[3].

nj和ni是一跳鄰居，那么計算公式如下：

(2.1)

nj和ni是二跳鄰居，那么計算公式如下：

(2.2)

(2.3)

(2.4)

根據(jù)節(jié)點受的作用力和勢能公式可以計算出節(jié)點新的位置：

(2.5)

由于錨節(jié)點本身知道自己的位置，故不參加迭代過程，未知節(jié)點迭代后均收斂，定位精度明顯提高.

3 算法的仿真與結(jié)果分析

對于改進的算法進行相關(guān)的仿真工作，利用matlab仿真軟件，分別實現(xiàn)了DV-Hop算法和改進算法.利用matlab的rand函數(shù)在的范圍內(nèi)隨機產(chǎn)生了200個無線傳感器網(wǎng)絡(luò)的節(jié)點，其中錨節(jié)點比例也是隨機產(chǎn)生.并作如下假設(shè)：網(wǎng)絡(luò)中的節(jié)點是相同的，并且擁有相同的通信半徑.在仿真中距離的誤差是指通過算法計算的坐標與真實坐標之間的差值，定義距離誤差與節(jié)通信半徑的比值為估算誤差.下面就參變量的不同分布詳細的比較兩種算法的定位精度.仿真的結(jié)果如下所示：

圖3.1可以看出，兩種算法均隨著通信半徑的加大，誤差在逐步減小.原因是隨通信半徑的加大，節(jié)點可以利用的相關(guān)約束信息增加，節(jié)點的鄰居節(jié)點數(shù)也在增加，所以誤差在逐步減小，但是當通信半徑增加到一定程度，這種變化就不是很明顯.另外還可以看出，改進的算法比原算法在相同的條件下定位精度要高.

圖3.1 估算誤差與通信半徑關(guān)系 圖3.2 估算誤差與連通度關(guān)系

圖3.2是估算誤差和連通度的變化關(guān)系，可以看出，連通度增加，定位誤差就減小，因為隨著連通度的增加，在迭代階段，就有更多的相對位置信息可以利用.可以看出，改進算法在隨連通度變化前期非常明顯，隨著在增加，基本變化不大.改進算法比原算法的定位精度提高近15%.

4 結(jié)束語

本文對DV-Hop算法作了改進，由于該定位算法針對網(wǎng)絡(luò)錨節(jié)點不均勻，改進的局部的定位算法，減少通信量和網(wǎng)絡(luò)的工作負擔，針對稀疏節(jié)點的網(wǎng)絡(luò)定位精度比原算法高.在此算法基礎(chǔ)之上，加入迭代的過程，解決了無測距DV-Hop算法定位的定位精度問題.以上都是在算法上的改進，無需其他的硬件支持.

[1]NiculescuD,NathB.AdHoepositioningsystem(APS)[J].IEEEGlobeCom，2001(5)：2926～2931

[2]田金鵬.無線傳感器網(wǎng)絡(luò)定位技術(shù)研究[D].上海大學.2008.

[3]李新.無線傳感器網(wǎng)絡(luò)中節(jié)點定位算法的研究[D].中國科學技術(shù)大學，2008.

[4]馮縝.基于區(qū)域的無線傳感器網(wǎng)絡(luò)定位算法研究[D].華中科技大學，2007.

ResearchontheimprovementofDV-Hopalgorithm

LI Ya-jie1,DU Chun-hui1,JI Gao-qing1

(1.HebeiInstituteofArchitectureandcivilengineeringHebeiZhangjiakou075000)

This paper studies and analyzes the DV-Hop localization algorithm in wireless sensor network,which is based on the wireless sensor network positioning algorithm without ranging.In the DV-Hop,single hop distance is calculated according to the data of whole network,and the communication burden is large.For the uneven distribution of the anchor nodes and the sparse nodes network,the positioning accuracy is poor.So propose the division and the sub region of the network.Because positioning accuracy of the non ranging algorithm is rough,after the DV-hop,the distributed iterative algorithm is added,further improving the accuracy of positioning.Through the simulation of the algorithm,the algorithm can improve the positioning accuracy,and also improve some specific application environment of algorithm.

DV-Hop；Node localization；Distance constraint;localization algorithm

2015-03-21

河北建筑工程學院青年基金項目(QN201418)

李亞杰(1983-)，男，漢，河北邯鄲，碩士，講師，從事計算機控制技術(shù)研究.

TP 301.6

A