基于DV-Hop算法改進(jìn)的研究

李亞杰 杜春暉 吉高卿

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

基于DV-Hop算法改進(jìn)的研究

李亞杰 杜春暉 吉高卿

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

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

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

0 引 言

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

1 DV-Hop基本過程

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

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

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

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

(1.1)

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

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

(1.2)

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

2 DV-Hop算法的改進(jìn)

2.1 算法局部化的改進(jìn)

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

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

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

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

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

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

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

(2.1)

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

(2.2)

(2.3)

(2.4)

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

(2.5)

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

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

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

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

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

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

4 結(jié)束語

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

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

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

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

[4]馮縝.基于區(qū)域的無線傳感器網(wǎng)絡(luò)定位算法研究[D].華中科技大學(xué)，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

河北建筑工程學(xué)院青年基金項(xiàng)目(QN201418)

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

TP 301.6

A