基于DV-HOP算法的提高定位精度研究

張佳,劉艷昌,王鮮芳

（1.河南科技學(xué)院,河南新鄉(xiāng)453003；2.河南師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院,河南新鄉(xiāng)453007）

基于DV-HOP算法的提高定位精度研究

張佳1,劉艷昌1,王鮮芳2

（1.河南科技學(xué)院,河南新鄉(xiāng)453003；2.河南師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院,河南新鄉(xiāng)453007）

無線傳感器網(wǎng)絡(luò)在目標(biāo)追蹤、環(huán)境監(jiān)測到空間探索等方面得到廣泛應(yīng)用,其關(guān)鍵支撐技術(shù)之一是節(jié)點(diǎn)定位.以經(jīng)典的DV-HOP算法為研究對(duì)象,為突破算法本身的計(jì)算應(yīng)用條件限制,在使用最小二乘原理得到位置信息時(shí),采用異方差消除原理,在參考節(jié)點(diǎn)位置信息存在明顯誤差時(shí),提高未知節(jié)點(diǎn)的定位精度.仿真實(shí)驗(yàn)結(jié)果表明：與原算法相比,改進(jìn)算法能夠降低累積誤差帶來影響,定位精度明顯提高.

無線傳感器網(wǎng)絡(luò)；自身定位算法；DV-HOP算法；異方差；最小二乘原理

無線傳感器網(wǎng)絡(luò)（wireless sensor network,WSN）通過部署在目標(biāo)區(qū)域的大量傳感器節(jié)點(diǎn),將采集到的數(shù)據(jù)在全網(wǎng)中進(jìn)行傳輸,實(shí)現(xiàn)對(duì)目標(biāo)的監(jiān)測.WSN在未來有極廣泛的應(yīng)用前景,而在其各種應(yīng)用中,傳感器節(jié)點(diǎn)所捕捉到的數(shù)據(jù)必須與位置信息相結(jié)合才能加以采用.因此節(jié)點(diǎn)定位是WSN正常運(yùn)行的首要工作,同時(shí)也是當(dāng)前無線傳感器研究的重點(diǎn),有許多問題還有待于解決.

傳感器節(jié)點(diǎn)的具有體積小、能耗低、自身資源有限等特點(diǎn),傳統(tǒng)的GPS等定位方法并不適合傳感器網(wǎng)絡(luò),比較現(xiàn)實(shí)的做法是將網(wǎng)絡(luò)中的若干傳感器配備GPS接收器或由人工配制位置信息,將這樣的傳感器節(jié)點(diǎn)作為參考節(jié)點(diǎn),而沒有位置信息的節(jié)點(diǎn)為未知節(jié)點(diǎn).傳感器網(wǎng)絡(luò)定位問題所要解決的就是未知節(jié)點(diǎn)如何根據(jù)參考節(jié)點(diǎn)的位置進(jìn)行自我定位.

WSN定位算法的發(fā)展到目前可分為兩類：基于測距的（Range-based）和非基于測距的（Range-free）.基于測距的算法主要依據(jù)信號(hào)接收的強(qiáng)度和時(shí)間、信號(hào)到達(dá)的時(shí)間差和角度等信息測量相鄰節(jié)點(diǎn)距離,優(yōu)點(diǎn)是定位精度較高,缺點(diǎn)是成本和能耗開銷大,規(guī)模較大的傳感器網(wǎng)絡(luò)不適合這種算法.非基于測距的算法主要是根據(jù)網(wǎng)絡(luò)的連通性進(jìn)行定位,由于不需要對(duì)距離進(jìn)行測量,所以成本和功耗相對(duì)較低,且對(duì)硬件支持等要求較低,因此這類定位方案近年來發(fā)展較快.例如：質(zhì)心法、APIT、Amorphous、LSBA等[1-3].而其中DV-HOP（Distance Vector-HOP）節(jié)點(diǎn)定位算法[4-5]由于具有定位精度相對(duì)較高、算法簡單、對(duì)參考節(jié)點(diǎn)比例要求較低等特點(diǎn),受到較多關(guān)注.本文著眼于對(duì)DV-HOP算法進(jìn)行研究,加以改進(jìn)以進(jìn)一步降低算法誤差.

1 DV-HOP算法及誤差分析

DV-HOP算法是為了避免節(jié)點(diǎn)之間直接測量距離提出來的.它的基本思想是用網(wǎng)絡(luò)中節(jié)點(diǎn)之間的平均每跳距離和節(jié)點(diǎn)之間的跳數(shù)乘積表示待定位節(jié)點(diǎn)之間的距離,然后采用三角定位的方法獲取節(jié)點(diǎn)的定位信息.DV-HOP定位算法大體分為3步：

（1）節(jié)點(diǎn)間使用距離矢量交換協(xié)議交換位置信息,使未知節(jié)點(diǎn)獲得與參考節(jié)點(diǎn)之間距離值,該距離值以跳數(shù)表示.

（2）在獲得其他參考節(jié)點(diǎn)位置（Xj,Yj）和相隔跳數(shù)后,各參考節(jié)點(diǎn)（Xi,Yi）利用所收集的信息按式（1）計(jì)算平均每跳距離

（3）在未知節(jié)點(diǎn)收集到與3個(gè)或更多參考節(jié)點(diǎn)之間的距離信息時(shí),就可以用最小二乘法來確定自身的位置信息.

假設(shè)未知節(jié)點(diǎn)所得到參考節(jié)點(diǎn)的坐標(biāo)分別是（x1,y1）,（x2,y2）,…,（xn,yn）,且它們到未知節(jié)點(diǎn)D的距離以d1,d2,…,dn表示,設(shè)未知節(jié)點(diǎn)D的坐標(biāo)是（x,y）,則可得到

在式（2）中,由第一個(gè)方程開始分別減去最后一個(gè)方程,可得

式（3）用線性方程表示為

式（4）中

最后使用最小均方差估計(jì)方法,得到未知節(jié)點(diǎn)的坐標(biāo)

假設(shè)參考節(jié)點(diǎn)的初始坐標(biāo)是由GPS測量得到的.由于存在多徑干擾[6],測到的參考節(jié)點(diǎn)坐標(biāo)有誤差,而以這些節(jié)點(diǎn)位置數(shù)據(jù)作為待求節(jié)點(diǎn)的約束條件,導(dǎo)致求出的新節(jié)點(diǎn)位置也存在數(shù)據(jù)誤差.這些誤差在以后遞推定位計(jì)算中不斷傳播與積累,使得到的節(jié)點(diǎn)位置數(shù)據(jù)存在較大誤差.從數(shù)學(xué)上講,DV-HOP算法定位計(jì)算是基于普通最小二乘法（Ordinary Least Squares,簡記OLS）.普通最小二乘法的基本原則是：最優(yōu)擬合直線應(yīng)該使各點(diǎn)到直線的距離的和最小,也可表述為距離的平方和最小,即Ax=b+△b,其中,△b是測量誤差.而事實(shí)上,與定位機(jī)制相關(guān)的矩陣A是由參考節(jié)點(diǎn)位置信息決定的,因而與不斷積累的定位誤差有關(guān)聯(lián)的.目前已對(duì)DV-HOP算法提出多種改進(jìn)方法,其中主要有：提高算法的平均跳距估計(jì)精度[7-10]；改進(jìn)最后一步的定位計(jì)算方法[11]；與其他定位算法相結(jié)合等[12].

在DV-HOP算法中,節(jié)點(diǎn)位置由式（5）用標(biāo)準(zhǔn)最小二乘方法求得.最小二乘法是基于測量均方誤差最小的算法,在對(duì)應(yīng)的測量方程Ax=b+△b中,沒有考慮到A也是存在誤差的.在確定節(jié)點(diǎn)的過程中,依據(jù)的新參考節(jié)點(diǎn)（xi,yi）是以前計(jì)算的節(jié)點(diǎn)（i=1,2,…,N）,其本身就有誤差.當(dāng)考慮到這一誤差時(shí),測量方程應(yīng)為（A+△A）x=b+△b.也就是說,用最小二乘基于均方差假設(shè)得到的節(jié)點(diǎn)位置信息不是最優(yōu)的.針對(duì)這個(gè)問題,我們提出用異方差存在假設(shè)來替換OLS的均方差假設(shè),并對(duì)異方差進(jìn)行消除的方法,以下給出求解節(jié)點(diǎn)位置的理論根據(jù)與仿真結(jié)果.

2 結(jié)合異方差消除原理的DV-HOP定位算法

2.1 產(chǎn)生異方差的原因

由于在線性回歸模型中采用最小二乘法估計(jì)模型中的參數(shù),根據(jù)其假設(shè)條件,隨機(jī)誤差項(xiàng)具有以下性質(zhì)：

（1）在一元線性回歸模型y=a+bx+ε中,其誤差項(xiàng)ε屬于位置偏差,即絕對(duì)誤差.根據(jù)一元線性回歸模型的假設(shè)條件,則ε～N（0,σ2）.

（2）在多元線性回歸模型y=b0+b1x1+b2x2+...+bnxn+ε中,隨機(jī)誤差項(xiàng)屬于位置偏差,按照多元線性回歸模型假設(shè)條件,滿足ε～N（0,σ2）.以上都是滿足同方差假定條件,在這種情況下的最小二乘法（OLS）估計(jì)稱為最佳線性無偏估計(jì)[13]（Best Linear Unbiased Estimators,簡記BLUE）.

而對(duì)于線性回歸模型

若D（εi）=σ2≠常數(shù),則表明模型顯現(xiàn)出異方差性.在這種情況下,OLS估計(jì)不再是最佳線性無偏估計(jì)BLUE,即不滿足最小方差性質(zhì).由于無法準(zhǔn)確估計(jì)系數(shù)的標(biāo)準(zhǔn)差,則檢驗(yàn)[14]可靠性減小,導(dǎo)致模型估計(jì)誤差的加大.在利用截面數(shù)據(jù)建立模型時(shí),則會(huì)產(chǎn)生異方差.而導(dǎo)致模型系數(shù)估計(jì)產(chǎn)生誤差的原因一般就是由于在建立模型時(shí)遺漏了影響增大的因素.

2.2 異方差的消除

加權(quán)最小二乘法（Weighted Least Squares,簡記WLS）[13]和模型變化法是消除異方差的常用方法,這里,選用WLS.WLS的思想是在同方差模型假定下,每個(gè)殘差ei[13]對(duì)總體回歸直線的偏離程度大致相同,權(quán)數(shù)都賦為1,這時(shí)OLS估計(jì)滿足BLUE估計(jì)；當(dāng)模型存在異方差性時(shí),每個(gè)ei對(duì)總體回歸直線的偏離程度不同,對(duì)于σi2較大,即偏離程度較大的ei,樣本點(diǎn)可信度隨之降低,就對(duì)其賦予較小的權(quán)數(shù),而對(duì)σi2較小,說明偏離程度較小的ei,樣本點(diǎn)的可信度較大,則隨之賦予較大的權(quán)數(shù),使模型估計(jì)時(shí)殘差的加權(quán)平方和最小.

設(shè)一元回歸模型y=a+bxi+εi若D（εi）=σ2,兩邊同除以σi得到消除了模型的異方差性.這時(shí)可以利用最小二乘法（OLS）估計(jì)模型.使得

提出的改進(jìn)算法如下：首先根據(jù)參考節(jié)點(diǎn)位置信息對(duì)未知節(jié)點(diǎn)的距離進(jìn)行估算,估算出未知節(jié)點(diǎn)到鄰近3個(gè)或者3個(gè)以上參考節(jié)點(diǎn)的距離值,然后用加權(quán)最小二乘法來消除式（5）中出現(xiàn)的異方差,最終得到未知節(jié)點(diǎn)的坐標(biāo)信息.

3 改進(jìn)算法的仿真

用仿真的方法比較使用普通最小二乘法OLS和使用加權(quán)最小二乘測量法WLS經(jīng)過異方差消除改進(jìn)后的DV-HOP定位算法的性能,證明改進(jìn)算法的有效性.仿真工具采用Matlab7.0,使用平均定位誤差（Estimation Error）來作為算法評(píng)價(jià)的標(biāo)準(zhǔn).平均定位誤差是所有節(jié)點(diǎn)的估測位置和真實(shí)位置之間相差的平均距離,在本次實(shí)驗(yàn)中用節(jié)點(diǎn)的通信距離將其歸一化.實(shí)驗(yàn)中傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分布在200 m×200 m的區(qū)域內(nèi),節(jié)點(diǎn)最大通信距離為50 m,干擾噪聲服從高斯分布,所有實(shí)驗(yàn)數(shù)據(jù)都是在獨(dú)立運(yùn)行100次之后得到的.

3.1 變化誤差率

討論出現(xiàn)明顯誤差的參考節(jié)點(diǎn)的比例變化對(duì)定位誤差的影響.實(shí)驗(yàn)參數(shù)設(shè)置如下：傳感器節(jié)點(diǎn)總數(shù)為200,參考節(jié)點(diǎn)個(gè)數(shù)為30,標(biāo)準(zhǔn)差為30 m,存在顯著誤差的參考節(jié)點(diǎn)信息比例從30%增加到100%.比較結(jié)果如圖1.

由圖1可以看出,在參考節(jié)點(diǎn)誤差率低于60%的情況下,兩種算法的定位誤差相差不大,但在誤差率繼續(xù)增加時(shí),原始算法的定位誤差迅速增加,而改進(jìn)后算法則對(duì)于誤差信息干擾的抑制較為明顯,始終將位置信息誤差帶來的影響控制在較低的范圍.說明在參考節(jié)點(diǎn)誤差率較高的情況下,改進(jìn)后算法的優(yōu)勢更加顯著.

3.2 變化標(biāo)準(zhǔn)差

標(biāo)準(zhǔn)差的變化反映了參考節(jié)點(diǎn)位置信息所出現(xiàn)誤差的變化范圍.本節(jié)討論標(biāo)準(zhǔn)差從20 m增加到100 m的過程中對(duì)DV-HOP算法定位精度的影響.實(shí)驗(yàn)參數(shù)設(shè)置如下：參考節(jié)點(diǎn)個(gè)數(shù)為30,誤差率為50%.比較結(jié)果見圖2.

從圖2來看,在標(biāo)準(zhǔn)差高于大約25 m以后,改進(jìn)后的算法的定位精度始終高于原始算法,隨著標(biāo)準(zhǔn)差的增加,原始算法的定位誤差也明顯繼續(xù)加大,而改進(jìn)后算法的定位誤差并沒有顯著增加,在標(biāo)準(zhǔn)差越高時(shí),改進(jìn)算法的優(yōu)勢越為明顯.

3.3 變化參考節(jié)點(diǎn)數(shù)目

討論參考節(jié)點(diǎn)總數(shù)從20增加到100的情況下對(duì)定位算法性能的影響.實(shí)驗(yàn)參數(shù)設(shè)置如下：參考節(jié)點(diǎn)誤差率為50%,標(biāo)準(zhǔn)差為30 m.比較結(jié)果見圖3.

圖2 標(biāo)準(zhǔn)差對(duì)定位算法性能的影響Fig.2 Change of standard deviation to positioning accuracy

圖3 參考節(jié)點(diǎn)數(shù)對(duì)定位算法性能的影響Fig.3 Change of reference number to positioning accuracy

一般情況下參考節(jié)點(diǎn)數(shù)目越多定位誤差應(yīng)該越小,但是從圖3來看,在參考節(jié)點(diǎn)數(shù)目逐漸增加的情況下,兩種算法的定位誤差變化出現(xiàn)起伏.這是由于誤差率不變的情況下,參考節(jié)點(diǎn)數(shù)量的增加在帶來更多位置信息的同時(shí)也會(huì)導(dǎo)致帶來更多誤差信息.但改進(jìn)算法的定位誤差始終低于原始算法,并且定位誤差的波動(dòng)相對(duì)于原始算法并不明顯,表明在使用異方差消除算法后改進(jìn)算法能明顯減少參考節(jié)點(diǎn)位置信息誤差帶來的影響.

4 小結(jié)

本文對(duì)DV-HOP定位算法產(chǎn)生誤差的原因進(jìn)行了理論分析,針對(duì)基于OLS原理的DV-HOP算法的缺點(diǎn),提出了基于異方差假設(shè),采用基于異方差消除的WLS原理改進(jìn)的DV-HOP算法.仿真實(shí)驗(yàn)表明,改進(jìn)算法較明顯提高了DV-HOP算法的定位精度.改進(jìn)方案具有良好的擴(kuò)展性,未來將研究將其應(yīng)用到其它基于最小二乘原理的定位算法之后的使用效果.

[1]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.

[2]He T,Huang C.Range-Free localization schemes for large scale sensor networks[C].In：Proc 9th Annual Int’l Conf on Mobile Computing and Networking,San Diego：ACM Press,2003：81-95.

[3]Li X,Hua B,Guo Y.Link state based annulus localization algorithm for wireless sensor networks[C].Proceedings of the International Conference on Communications and Networking,Shanghai：ICST,2007：298-303.

[4]Niculescu D,Nath B.DV based positioning in Ad hoc Networks[J].Journal of Telecommunication Systems,2003,22（1/4）：267-280.

[5]張震,閆連山,劉江濤,等.基于DV-Hop的無線傳感器網(wǎng)絡(luò)定位算法研究[J].傳感技術(shù)學(xué)報(bào),2011,24（10）：1469-1472.

[6]吳順君,梅曉春.雷達(dá)信號(hào)處理和數(shù)據(jù)處理技術(shù)[M].北京：電子工業(yè)出版社,2008：146-149.

[7]林金朝,陳曉冰,劉海波.基于平均跳距修正的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)迭代定位算法[J].通信學(xué)報(bào),2009,30（10）：107-113.

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

[9]劉少飛,趙清華,王華奎.基于平均跳距估計(jì)和位置修正的DV-HOP定位算法[J].傳感技術(shù)學(xué)報(bào),2009,22（8）：1154-1158.

[10]丁江鵬,陳曙.一種基于跳數(shù)比的無線傳感器網(wǎng)絡(luò)定位算法[J].傳感技術(shù)學(xué)報(bào),2009,22（12）：1823～1827.

[11]王書鋒,侯義斌,黃樟欽,等.無線感知網(wǎng)絡(luò)最小二乘法定位算法的誤差分析與優(yōu)化[J].系統(tǒng)仿真學(xué)報(bào),2009,21（19）：621l-6215.

[12]胡斌,李方敏,劉新華.基于RSSI量化模型的定位算法研究[J].武漢理工大學(xué)學(xué)報(bào),2009,31（23）：92-95.

[13]王軍.回歸模型異方差性分析[J].科技和產(chǎn)業(yè),2008,8（1）：61-63.

[14]劉明.基于一元線性回歸模型異方差對(duì)加權(quán)最小二乘法的考察[J].統(tǒng)計(jì)與決策,2012（19）：11-14.

（責(zé)任編輯：盧奇）

Study of improving location accuracy based on DV-HOP algorithm

Zhang Jia1,Liu Yanchang1,Wang Xianfang2
（1.Henan Institute of Science and Technology,Xinxiang 453003,China；2.College of Computer and Information Engineering,Henan Normal University,Xinxiang 453007,China）

Wireless sensor networks have been wildly used in target tracking,environmental monitoring and space exploration,etc.One of its key supporting technologies is node localization.The DV-HOP algorithm is taken as the research object.To break the algorithm’s calculation application restrictions,the heteroscedasticity elimination principle is adopted when obtaining node location information through the Least Squares principle.This method is applied to remove distinct errors emerging when referring to the node location information and improve the positioning accuracy of unknown nodes.The simulation experiment results demonstrate that the improved algorithm can reduce the affects which the accumulation error brings about and improves the positioning accuracy compared with the original algorithm significantly.

wireless sensor network；self-location algorithm；DV-HOP algorithm；heteroscedasticity；least squares principle

TP393

A

1008-7516（2013）05-0058-05

10.3969/j.issn.1008-7516.2013.05.014

2013-07-11

國家自然科學(xué)基金項(xiàng)目（61173071）

張佳（1979-）,男,河南新鄉(xiāng)人,碩士,助教.主要從事無線傳感器網(wǎng)絡(luò)研究.