無線傳感器網(wǎng)絡(luò)中DV-Hop定位算法的改進(jìn)

劉玉錕，廖惜春，沈海燕，陳俊麗

?

無線傳感器網(wǎng)絡(luò)中DV-Hop定位算法的改進(jìn)

劉玉錕1，廖惜春1，沈海燕1，陳俊麗2

（1. 五邑大學(xué) 信息學(xué)院，廣東 江門 529020；2. 成都理工大學(xué) 信息科學(xué)與技術(shù)學(xué)院，四川 成都 610059）

通過分析DV-Hop算法定位過程誤差產(chǎn)生的主要原因，在限制節(jié)點(diǎn)間跳數(shù)、校正相同跳數(shù)的節(jié)點(diǎn)之間的跳距和循環(huán)升級(jí)等3個(gè)方面進(jìn)行改進(jìn)，并對(duì)改進(jìn)算法進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明：在相同的環(huán)境下，本文提出的改進(jìn)算法能顯著提高節(jié)點(diǎn)定位精度和覆蓋率.

無線傳感器網(wǎng)絡(luò)；節(jié)點(diǎn)定位；DV-Hop算法；改進(jìn)DV-Hop算法

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSN）中，網(wǎng)絡(luò)節(jié)點(diǎn)的位置信息是非常重要的，缺少位置信息的監(jiān)測(cè)數(shù)據(jù)往往毫無意義[1]. 確定節(jié)點(diǎn)的位置信息后可以提供事件發(fā)生的地點(diǎn)信息，還可以實(shí)現(xiàn)對(duì)外部移動(dòng)目標(biāo)的定位和追蹤、預(yù)測(cè)移動(dòng)目標(biāo)的前進(jìn)軌跡等. 因此，傳感器節(jié)點(diǎn)定位問題已成為WSN中的一個(gè)重要的研究方向.

近年來國內(nèi)外學(xué)者提出了許多節(jié)點(diǎn)定位算法，按照定位過程中采用的技術(shù)手段基本可分為兩類[2]：基于測(cè)距的定位算法[3-4]和無需測(cè)距的定位算法[5-6]. 在無需測(cè)距定位算法中，DV-Hop是一種經(jīng)典的定位算法，該算法具有對(duì)信標(biāo)節(jié)點(diǎn)比例要求較少，定位精度高等優(yōu)點(diǎn). 文章詳細(xì)分析了DV-Hop算法過程，確定誤差產(chǎn)生的主要原因，提出改進(jìn)算法，并進(jìn)行仿真實(shí)驗(yàn).

1 DV-Hop定位算法及其誤差分析

1.1 DV-Hop算法基本原理

DV-Hop算法是由美國的Dragos Niculescu等人利用距離矢量路由和GPS定位原理提出來的一種無需測(cè)距的定位算法，該算法定位過程不依賴于直接測(cè)距方法，利用多跳信標(biāo)節(jié)點(diǎn)信息來參與節(jié)點(diǎn)定位，定位覆蓋率較大[7]. 其核心是在信標(biāo)節(jié)點(diǎn)的選擇過程中使用了最短路徑算法，利用多跳信標(biāo)節(jié)點(diǎn)的位置信息來計(jì)算未知節(jié)點(diǎn)的位置. 在該定位機(jī)制中，未知節(jié)點(diǎn)首先計(jì)算與信標(biāo)節(jié)點(diǎn)的最小跳數(shù)，然后通過公式

計(jì)算平均每跳距離，其中，(x,y)、(x,y)是信標(biāo)節(jié)點(diǎn)、的坐標(biāo)，h是信標(biāo)節(jié)點(diǎn)與()之間的跳段數(shù). 利用平均每跳距離乘以最小跳數(shù)得到未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的距離，最后再利用極大似然估計(jì)法計(jì)算出未知節(jié)點(diǎn)的坐標(biāo)[8].

如圖1所示，假設(shè)1，2和3是信標(biāo)節(jié)點(diǎn)，其他節(jié)點(diǎn)是未知節(jié)點(diǎn)，定義節(jié)點(diǎn)通信半徑為30 m. 經(jīng)過信息廣播和計(jì)算，由式（1）得信標(biāo)節(jié)點(diǎn)1計(jì)算得到平均每跳距離為(50+100)/(2+7)=16.67 m，信標(biāo)節(jié)點(diǎn)2計(jì)算得到平均每跳距離為(50+80)/(2+5)=18.57 m，信標(biāo)節(jié)點(diǎn)3計(jì)算得到平均每跳距離為(80+100)/(5+7)=15 m. 未知節(jié)點(diǎn)A從信標(biāo)節(jié)點(diǎn)3處獲得平均每跳距離，則它與3個(gè)信標(biāo)節(jié)點(diǎn)之間的距離分別為60 m(1)、30 m(2)、45 m(3)，最后利用極大似然估計(jì)法即可計(jì)算出未知節(jié)點(diǎn)A的位置.

圖1 DV-Hop算法示意圖

1.2 DV-Hop算法誤差分析

1.2.1 跳距引起誤差

DV-Hop算法采用平均每跳距離來估算實(shí)際距離，對(duì)節(jié)點(diǎn)的硬件技術(shù)要求低，實(shí)現(xiàn)簡(jiǎn)單. 其缺點(diǎn)是利用跳段距離代替直線距離，存在一定的誤差，誤差主要來源在于計(jì)算未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的估計(jì)距離時(shí)，是用跳數(shù)與平均每跳距離的乘積來代替直線跳距離，然而在實(shí)際的網(wǎng)絡(luò)拓?fù)渲?，信?biāo)節(jié)點(diǎn)到未知節(jié)點(diǎn)多數(shù)不是直線路徑[9]. 該算法得出的平均每跳距離在密度均勻的各向同性網(wǎng)絡(luò)中誤差不大，但在密度不均勻的各向異性網(wǎng)絡(luò)中，就會(huì)使定位精度下降，造成較大的誤差[10]. 產(chǎn)生誤差的原因如圖l所示，未知節(jié)點(diǎn)A與信標(biāo)節(jié)點(diǎn)1的實(shí)際距離（45 m）會(huì)用跳數(shù)乘以平均每跳距離（4×15 m）代替，誤差由此產(chǎn)生.

1.2.2 跳數(shù)引起誤差

在DV-Hop定位算法中，由于廣播分組和傳感器節(jié)點(diǎn)隨機(jī)分布過程中可能存在沖突等因素，節(jié)點(diǎn)得到的到信標(biāo)節(jié)點(diǎn)的最小跳數(shù)存在有一定偏差，且跳數(shù)越多，偏差越大. 文獻(xiàn)[11]仿真結(jié)果顯示，誤差值較大的節(jié)點(diǎn)距信標(biāo)節(jié)點(diǎn)跳數(shù)較大的點(diǎn)，而距離信標(biāo)節(jié)點(diǎn)跳數(shù)較小的點(diǎn)定位精度相對(duì)較高. 這是因?yàn)镈V-Hop算法采用跳段距離之和代替實(shí)際距離，跳段數(shù)增加將使累計(jì)誤差加大，所以本文在改進(jìn)算法中將采用限制節(jié)點(diǎn)跳數(shù)的方法，即未知節(jié)點(diǎn)若只接收距離較近的局部范圍內(nèi)的信標(biāo)節(jié)點(diǎn)信息，這樣會(huì)減少誤差的累加，有助于提高定位精度，并從整體上降低網(wǎng)絡(luò)通信量.

1.2.3 計(jì)算過程中存在誤差

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

分析DV-Hop算法中存在的誤差后，本文提出相應(yīng)的改進(jìn)措施，思路是：第1步限制未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的跳數(shù)，可提高定位精度，減少數(shù)據(jù)包的發(fā)送量. 第2步校正相同跳數(shù)的未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的距離，并且將限制條件只應(yīng)用于限定跳數(shù)范圍內(nèi)的平均每跳距離，利用最小二乘法計(jì)算出未知節(jié)點(diǎn)坐標(biāo). 第3步采用循環(huán)升級(jí)的方法，確定坐標(biāo)的未知節(jié)點(diǎn)經(jīng)過校正后升級(jí)為信標(biāo)節(jié)點(diǎn)，繼續(xù)定位其他未知節(jié)點(diǎn)，此過程可提高定位精度和網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋率.

本文對(duì)DV-Hop算法改進(jìn)的具體步驟如下：

在此基礎(chǔ)上，門限取值應(yīng)能盡量滿足可以定位所有未知節(jié)點(diǎn)并且盡量接近所能取到的最小值，以使網(wǎng)絡(luò)通信量相對(duì)較小，同時(shí)取值應(yīng)適當(dāng)加大以滿足網(wǎng)絡(luò)整體的覆蓋率.

第2步確定未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間距離S. 當(dāng)未知節(jié)點(diǎn)計(jì)算出與信標(biāo)節(jié)點(diǎn)的距離后，通過限制跳距的約束條件來校正存在的誤差. 由理論可知，未知節(jié)點(diǎn)到各個(gè)信標(biāo)節(jié)點(diǎn)的跳段距離的估計(jì)值總存在誤差，這會(huì)引起較大的節(jié)點(diǎn)定位誤差. 如圖1所示，未知節(jié)點(diǎn)A到信標(biāo)節(jié)點(diǎn)2的跳數(shù)為2，節(jié)點(diǎn)的通信半徑為，則A與2的距離2應(yīng)大于通信半徑并且小于等于2，即＜2≤2. 傳統(tǒng)DV-Hop方法對(duì)節(jié)點(diǎn)A進(jìn)行定位時(shí)卻可能得到A的位置在2的一跳通信半徑內(nèi)或者在2的兩跳距離之外的結(jié)論，存在較大的誤差. 為此，本階段的改進(jìn)思路是，在定位過程中校正未知節(jié)點(diǎn)到最近信標(biāo)節(jié)點(diǎn)的跳段距離，從而有效提高節(jié)點(diǎn)定位精度. 改進(jìn)后的算法規(guī)則是：節(jié)點(diǎn)通信距離為，當(dāng)未知節(jié)點(diǎn)距離信標(biāo)節(jié)點(diǎn)一跳范圍之內(nèi)時(shí)，未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間距離1滿足條件：0＜1≤；當(dāng)未知節(jié)點(diǎn)距離信標(biāo)節(jié)點(diǎn)(>1)跳范圍之內(nèi)時(shí)，未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間距離S滿足條件：≤S≤·.

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

第3步將已定位的節(jié)點(diǎn)升級(jí)為信標(biāo)節(jié)點(diǎn). 在經(jīng)過以上兩個(gè)階段的廣播和計(jì)算后，多數(shù)未知節(jié)點(diǎn)都能接收到限定跳數(shù)內(nèi)的信標(biāo)節(jié)點(diǎn)廣播的平均跳距，并計(jì)算出符合限定條件的跳距，初步仿真顯示少數(shù)未知節(jié)點(diǎn)未收到廣播信息，或者接收到的廣播信息個(gè)數(shù)小于3[14]，則不能參與定位，可定位節(jié)點(diǎn)的比例就會(huì)下降，為了提高定位精度和節(jié)點(diǎn)覆蓋率，提出了本階段的改進(jìn)，即利用循環(huán)升級(jí)的方法將已求出坐標(biāo)位置的未知節(jié)點(diǎn)升級(jí)為信標(biāo)節(jié)點(diǎn)，然后新的信標(biāo)節(jié)點(diǎn)繼續(xù)廣播位置信息，循環(huán)執(zhí)行第1步和第2步，直到計(jì)算出最后一個(gè)可定位的節(jié)點(diǎn). 不可定位的節(jié)點(diǎn)定義為不良節(jié)點(diǎn)，即鄰居節(jié)點(diǎn)個(gè)數(shù)小于3的節(jié)點(diǎn).

綜合上述3步改進(jìn)措施的匯總算法稱為IDV-Hop（Improve DV-Hop），改進(jìn)算法流程描述如圖2所示.

3 算法仿真與分析

節(jié)點(diǎn)平均定位誤差為

3.1 信標(biāo)節(jié)點(diǎn)比例對(duì)定位誤差的影響

在仿真過程中，取門限值=6，節(jié)點(diǎn)通信半徑=25 m，通過設(shè)置不同信標(biāo)節(jié)點(diǎn)比例，比較改進(jìn)算法與原始算法的平均定位誤差. 其中軸表示信標(biāo)節(jié)點(diǎn)占總節(jié)點(diǎn)數(shù)的比例，軸表示節(jié)點(diǎn)平均定位誤差.

圖3 節(jié)點(diǎn)平均定位誤差和信標(biāo)節(jié)點(diǎn)比例之間的關(guān)系

從圖3中可以看出，本文提出的改進(jìn)算法定位誤差低于DV-Hop算法，平均定位誤差降低約10%，在信標(biāo)節(jié)點(diǎn)比例較低的情況下，改進(jìn)后的算法性能較明顯，特別是信標(biāo)節(jié)點(diǎn)比例為10%的時(shí)候，定位誤差降低了約50%.

3.2 通信半徑對(duì)定位誤差的影響

在仿真過程中，取門限值=6，信標(biāo)節(jié)點(diǎn)比例為20%，通過設(shè)置不同節(jié)點(diǎn)通信半徑，比較改進(jìn)算法與原始算法的平均定位誤差.

圖4 節(jié)點(diǎn)平均定位誤差和節(jié)點(diǎn)通信半徑之間的關(guān)系

圖5 信標(biāo)節(jié)點(diǎn)比例和網(wǎng)絡(luò)覆蓋率之間的關(guān)系

圖4是在不同通信半徑下定位誤差的比較，相對(duì)于DV-Hop算法，改進(jìn)算法明顯降低了定位的誤差，平均定位誤差減少10%左右，在通信半徑較小的情況下，改進(jìn)算法性能較明顯，特別是=15 m的時(shí)候，定位精度提高了約40%. 平均定位誤差均隨著通信半徑的增加而在逐漸減少，但是當(dāng)通信半徑達(dá)到30 m后，隨著通信半徑的增加，節(jié)點(diǎn)定位誤差幾乎保持不變，因?yàn)橥ㄐ虐霃皆谝欢ǚ秶鷥?nèi)增加可以增強(qiáng)網(wǎng)絡(luò)的連通度，而連通度的增加也會(huì)引起誤差的增長，即一跳內(nèi)的節(jié)點(diǎn)數(shù)增加，定位過程中不同的節(jié)點(diǎn)可能會(huì)定位成同一位置.

3.3 信標(biāo)節(jié)點(diǎn)比例對(duì)定位覆蓋率的影響

取門限值=6，節(jié)點(diǎn)通信半徑=25 m仿真，通過設(shè)置不同信標(biāo)節(jié)點(diǎn)比例，比較改進(jìn)算法與原始算法的定位節(jié)點(diǎn)覆蓋率.

從圖5可以看出，隨著信標(biāo)節(jié)點(diǎn)比例的增大，改進(jìn)算法和原始DV-Hop算法的定位覆蓋率都在增加. 在信標(biāo)節(jié)點(diǎn)比例為25%時(shí)，改進(jìn)算法IDV-Hop的定位覆蓋率即達(dá)到100%，比DV-Hop算法提高10%左右.

3.4 原始算法與改進(jìn)算法仿真效果對(duì)比

圖6 DV-HOP算法與IDV-HOP算法仿真效果圖對(duì)比

原始DV-HOP算法仿真結(jié)果直觀效果圖如圖6-a所示，未知節(jié)點(diǎn)與對(duì)應(yīng)所求坐標(biāo)位置用直線連接，改進(jìn)DV-HOP算法仿真結(jié)果直觀效果圖如圖6-b所示，根據(jù)兩圖對(duì)比能直觀地得出改進(jìn)算法顯著地降低了定位誤差的結(jié)論.

4 結(jié)論

通過對(duì)DV-Hop算法的理論分析，誤差產(chǎn)生主要原因是由跳數(shù)、跳距和計(jì)算過程引起的，提出了限制節(jié)點(diǎn)間跳數(shù)，校正相同跳數(shù)的節(jié)點(diǎn)之間的跳距和循環(huán)升級(jí)三種措施對(duì)原始算法進(jìn)行改進(jìn). 仿真實(shí)驗(yàn)證明：改進(jìn)算法能提高原算法的定位精度和覆蓋率，同時(shí)對(duì)于低密度的各向異性網(wǎng)絡(luò)具有更高的適應(yīng)性. 但由于改進(jìn)算法采用了循環(huán)升級(jí)的方法，定位時(shí)間和能耗有所增加，在定位精度、定位時(shí)間和能耗之間找到一個(gè)平衡點(diǎn)將是下一步研究的重點(diǎn).

[1] 孫利民，李建中，陳渝，等. 無線傳感器網(wǎng)絡(luò)[M]. 北京：清華大學(xué)出版社，2005.

[2] 王福豹，史龍，任豐原. 無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J]. 軟件學(xué)報(bào)，2005, 16(5): 857-868.

[3] GIROD L, BYCHOVSKIY V, ELSON J, et al. Locating tiny sensors in time and space: a case study [C]// 2002 IEEE Int’l Conf on Computer Design: VLSI in Computers and Processors, Freiburg: IEEE Computer Society, 2002: 214-219.

[4] BULUSU N, HEIDEMANN J, ESTRIN D. GPS-less low cost outdoor localization for very small devices [J]. IEEE Personal Communications, 2000, 7(5): 28-34.

[5] NICULESSCUD D, NATH B. Ad-Hoc positioning systems (APS) [C]// 2001 IEEE Global Telecommunications Conference, San Antonio: IEEE Computer Society, 2001: 2926-2931.

[6] NAGPAL R. Organizing a global coordinate system from local information on an amorphous computer [R]. Cambridge MA: MIT AI Laboratory, 1990.

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

[8] 衛(wèi)開夏，田金鵬，王克謙. 無線傳感器網(wǎng)絡(luò)DV-Hop定位改進(jìn)算法[J]. 傳感技術(shù)學(xué)報(bào)，2010, 23(12): 1820-1824.

[9] 楊智鋒，裴騰達(dá)，裴炳南. 基于代數(shù)重建法的DV-Hop定位算法[J]. 計(jì)算機(jī)工程，2010, 36(15): 117-119.

[10] 張佳，吳延海，石峰，等. 基于DV-HOP的無線傳感器網(wǎng)絡(luò)定位算法[J]. 計(jì)算機(jī)應(yīng)用，2010, 30(2): 323-326.

[11] 于寧. 無線傳感器網(wǎng)絡(luò)定位優(yōu)化方法[D]. 北京：北京郵電大學(xué)，2008.

[12] 楊智鋒，裴炳南，劉波. 提高DV-Hop算法定位精度研究[J]. 計(jì)算機(jī)工程與應(yīng)用，2011, 47(1): 113-115.

[13] 于寧，萬江文，吳銀鋒. 無線傳感器網(wǎng)絡(luò)定位算法研究[J]. 傳感技術(shù)學(xué)報(bào)，2007, 20(1): 188-193.

[14] 石為人，賈傳江，梁煥煥. 一種改進(jìn)的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法[J]. 傳感技術(shù)學(xué)報(bào)，2011, 24(1): 83-87.

[責(zé)任編輯：韋 韜]

Improvement on DV-Hop Localization Algorithm in Wireless Sensor Networks

LIUYu-kun1, LIAOXi-chun1, SHENHai-yan1, CHENJun-li2

(1. School of Information Engineering, Wuyi University, Jiangmen 529020, China; 2. College of Information Science and Technology, CDUT, Chengdu 610059, China)

After analyzing the localization process of the DV-Hop algorithm, in light of the main reasons for errors, this paper proposes improvements on 3 aspects: limiting inter-node hop counts, correcting the distance between nodes of the same number of hops and upgrading circulation. Simulation experiments on the improved algorithm are carried out. Simulation results show that in the same environment, the proposed algorithm can significantly improve localization accuracy and coverage.

wireless sensor networks; node localization; DV-Hop algorithm; improved DV-Hop algorithm

1006-7302（2013）02-0059-06

TP393

A

2013-01-09

廣東省科技計(jì)劃資助項(xiàng)目（2009B010800012）

劉玉錕（1988—），男，河南周口人，在讀碩士生，主要從事無線傳感器網(wǎng)絡(luò)路由及定位算法的應(yīng)用研究；廖惜春，教授，碩士生導(dǎo)師，通信作者，主要從事無線通信網(wǎng)絡(luò)理論與技術(shù)應(yīng)用研究.