基于距離補償模型的改進DV-Hop定位算法

高文根,陳其工,江 明,李云飛,牛明強

(安徽工程大學(xué)檢測技術(shù)與節(jié)能裝置安徽省重點實驗室,安徽蕪湖241000)

基于距離補償模型的改進DV-Hop定位算法

高文根,陳其工,江 明,李云飛,牛明強

(安徽工程大學(xué)檢測技術(shù)與節(jié)能裝置安徽省重點實驗室,安徽蕪湖241000)

傳統(tǒng)的DV-Hop定位算法在估計網(wǎng)絡(luò)平均跳距時,采用錨節(jié)點之間的物理直線距離代替信號實際傳播距離,兩者之間存在的距離誤差會引起平均跳距估計不精確,從而導(dǎo)致較高的節(jié)點定位誤差。針對該問題,提出一種改進算法。分析物理直線距離和實際傳播距離存在誤差的原因,將其總結(jié)為節(jié)點隨機布置導(dǎo)致的節(jié)點間距離不均勻,以及實際傳播路徑與物理直線距離的偏離,并根據(jù)不均勻度和偏離度建立距離補償模型,使物理直線距離更接近實際傳播距離。與傳統(tǒng)算法相比,改進算法未增加算法復(fù)雜度和額外的硬件設(shè)備。仿真結(jié)果表明,該算法較好地補償了錨節(jié)點之間的距離,顯著提高了算法對于未知節(jié)點的定位精度。

距離補償;估計距離;不均勻度;偏離度;DV-Hop定位算法;無線傳感器網(wǎng)絡(luò)

1 概述

目前,無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network, WSN)已經(jīng)廣泛應(yīng)用于諸多領(lǐng)域,如自然環(huán)境的監(jiān)測、遠程醫(yī)療監(jiān)控等［1］。在這些應(yīng)用中,遠程控制端所接收到的數(shù)據(jù),只有在具備顯示數(shù)據(jù)或者事件發(fā)生地點的條件下,才能作為有效地信息,幫助遠程控制端或者人類實現(xiàn)相應(yīng)的控制或者檢測目的,沒有攜帶發(fā)生位置的信息,沒有實用性［2-3］。因此,對無線傳感器網(wǎng)絡(luò)來說,節(jié)點的位置信息是至關(guān)重要的。

在現(xiàn)有的無線傳感網(wǎng)絡(luò)定位算法中,主要存在2類定位算法,其主要區(qū)別在于,如何獲得節(jié)點之間

的距離信息。由此,主要可以分成基于測距和無需測距(Range-Free)的2類定位算法。基于距離的定位算法常用測距方法有RSSI(Received Signal Strength Indicator),TOA(Time of Arrival),TDOA (TimeDifferenceonArrival),AOA(Angleof Arrival),且定位精度相對較高,同樣要求節(jié)點硬件達到一定的條件。無需測距的定位算法不依賴節(jié)點之間的據(jù)對距離和方位,在成本上,更加適用于大規(guī)模的網(wǎng)絡(luò)。基于無需測距的定位算法主要有質(zhì)心算法、DV-Hop算法、APIT算法、MDS-Map算法等［4］,其中DV-Hop算法應(yīng)用較為廣泛。

文獻［5］給出的改進DV-Hop算法,在采用改進PSO算法的基礎(chǔ)上,對WSN的部署覆蓋進行了優(yōu)化。文獻［6］算法通過Max-Min方法和多個參考節(jié)點的改進方式,來提高定位的精度。文獻［7］在原算法的基礎(chǔ)上,提出了修正距離誤差的算法,降低節(jié)點定位誤差。針對原DV-Hop算法由于平均跳距帶來的估計距離誤差,本文建立了數(shù)學(xué)模型,對距離誤差進行估計,修正未知節(jié)點到錨節(jié)點的估計距離,以期提高定位精度。

2 DV-Hop定位算法

DV-Hop定位算法由美國路特格斯大學(xué)(Rutgers University)的Niculescu等人［8］提出。該算法主要由3個階段組成［9-10］:第1階段,完成節(jié)點間信息的交換,錨節(jié)點將信息傳遞至除自己外的所有節(jié)點,使之獲得與錨節(jié)點的跳數(shù);第2階段,網(wǎng)絡(luò)平均跳距的估計和傳播。網(wǎng)絡(luò)中錨節(jié)點在獲得其他錨節(jié)點的相應(yīng)信息后,計算網(wǎng)絡(luò)平均每跳距離,然后將其作為校正值廣播至網(wǎng)絡(luò)中。所有網(wǎng)絡(luò)節(jié)點只記錄接收到的第一個校正值,并通過鄰居節(jié)點轉(zhuǎn)發(fā),接著根據(jù)記錄的最小跳數(shù),計算到附近各個錨節(jié)點的跳段距離;第3階段,完成坐標定位。最后當(dāng)未知節(jié)點獲得與3個或更多錨節(jié)點間的距離時,采用數(shù)學(xué)方法計算自身坐標。

3 DV-Hop算法的改進

3.1 DV-Hop定位算法問題描述

在傳統(tǒng)DV-Hop算法中,平均跳距的估計是基于錨節(jié)點之間的物理直線距離。如圖1所示,錨節(jié)點i的平均跳距的獲得如下:

假設(shè)未知節(jié)點獲得的校正值來自錨節(jié)點i,那么:

假設(shè)l2＞l1＞l3＞R,有:

顯然,這樣的平均跳距估計方式會帶來很大的定位誤差。

圖1 傳統(tǒng)DV-Hop算法的網(wǎng)絡(luò)拓撲結(jié)構(gòu)

3.2 距離補償模型

如圖1所示,錨節(jié)點i和j之間的物理直線距離,與實際傳播距離的誤差,主要由未知節(jié)點1部署的隨機性,使得實際傳播路徑偏離了錨節(jié)點i和j物理直線所在路徑,導(dǎo)致實際傳播距離和物理直線距離之間產(chǎn)生距離誤差。

要實現(xiàn)節(jié)點A和C之間的通信,節(jié)點B必須部署在2個節(jié)點A和C的重疊通信區(qū)域部分,顯然,節(jié)點B偏離度最大時,即節(jié)點B處在如圖2所示的位置。

圖2 網(wǎng)絡(luò)拓撲的偏離度示意圖

此時,如果節(jié)點A和C相互靠近,即dAC不斷減少,直到臨界條件:dAC=R。此時,偏離度h達到最大值:

節(jié)點A,B,C所在的區(qū)域節(jié)點密度為:

如果增加節(jié)點A和C之間的傳輸節(jié)點,即局部節(jié)點密度增加,如圖3所示。

圖3 節(jié)點密度增加部分網(wǎng)絡(luò)拓撲的偏離度示意圖

在中間傳輸節(jié)點個數(shù)增多的條件下,節(jié)點B1,B2的偏離度明顯大于節(jié)點B的偏離度,即在節(jié)點密度增加一定程度時,會影響到偏離度的大小。A,B1,B2,C所在區(qū)域的節(jié)點密度為:

此節(jié)點密度的下限臨界值如式(5)所示,上限臨界值為:

如果局部節(jié)點密度超過此界限,由于傳播路徑的可能性增多,在一定程度上會降低偏離度。同時,偏離度服從均勻分布［11］,則有:

將圖1中的不均勻度消除后,所形成的節(jié)點的拓撲結(jié)構(gòu)如圖4所示。顯然,即使在沒有偏離度的條件下,由于節(jié)點分布的不均勻性,同樣會帶來節(jié)點之間距離的不均勻性,從而導(dǎo)致節(jié)點定位誤差。

圖4 偏離度為0的網(wǎng)絡(luò)拓撲結(jié)構(gòu)

假設(shè)網(wǎng)絡(luò)中相鄰節(jié)點之間的距離均為R,那么相鄰節(jié)點之間不均勻度為0,如圖5所示。

圖5 不均勻度為0的網(wǎng)絡(luò)拓撲結(jié)構(gòu)

可以得出此時的節(jié)點密度為:

其中,n是節(jié)點周圍的節(jié)點個數(shù)。在最理想的條件下,不均勻度為0所對應(yīng)的最大節(jié)點個數(shù)為:

最大的節(jié)點密度和最小密度為:

在理想情況下,節(jié)點密度不超出［ρmin,ρmax］,節(jié)點的不均勻度為0。在實際情況下,節(jié)點的不均勻度受到節(jié)點部署影響［12-13］,因此,節(jié)點不均勻度呈現(xiàn)自然指數(shù)變化。

如圖1所示,未知節(jié)點1的不均勻度為:

同時,有:

由此,可以得到:

其中,i,k=1,2,…,hops。

基于以上結(jié)論,本文提出以下距離補償公式:

4 算法仿真及分析

為了檢驗算法的性能,在MatLab中同時對本文提出的改進定位算法、文獻［11］提出的改進定位算法、原DV-Hop定位算法3種算法進行仿真,并對所出現(xiàn)的仿真結(jié)果進行評估和分析。網(wǎng)絡(luò)中所有節(jié)點都隨機分布在特定的區(qū)域(100 m×100 m)。3種算法性能的評估,都是基于相同條件下,呈現(xiàn)不同錨節(jié)點密度、節(jié)點通信半徑對不同算法的性能影響。每種性能的仿真基于100次仿真結(jié)果的平均值。WSN隨機部署節(jié)點分布圖如圖6所示,其中,圓形表示未知節(jié)點;星形表示錨節(jié)點,錨節(jié)點比例為10%。

圖6 WSN隨機部署節(jié)點分布

定義節(jié)點定位誤差δ為:

其中,(xreal,yreal)是未知節(jié)點實際的坐標;(xestd,yestd)是估計出來的未知節(jié)點的坐標;R表示節(jié)點的通信半徑。節(jié)點平均定位誤差為已定位為未知節(jié)點的誤差和與能被定位的未知節(jié)點個數(shù)比值。

仿真結(jié)果如圖7～圖9所示,本文提出的改進定位算法記為改進DV-Hop1,文獻［11］提出的改進定位算法記為改進DV-Hop2,原DV-Hop定位算法記為DV-Hop。

圖7 平均定位誤差隨錨節(jié)點個數(shù)的變化曲線

圖8 平均定位誤差隨節(jié)點通信半徑的變化曲線

圖9 平均定位誤差隨節(jié)點總數(shù)的變化曲線

圖7顯示,隨著錨節(jié)點比例的增大,DV-Hop、改進DV-Hop1和改進DV-Hop2都逐漸下降,改進算法的變化趨勢與原算法保持一致,且誤差率一直要低于原算法。改進算法在錨節(jié)點比例較少時,優(yōu)化程度較低,錨節(jié)點個數(shù)較少,在距離補償?shù)倪^程中,對平均跳距的影響較小,不能很大程度地降低節(jié)點定位誤差,因此,3種定位算法誤差率相當(dāng)。隨著錨節(jié)點比例的增大,2種改進算法的性能逐漸優(yōu)于原算法,改進DV-Hop1稍優(yōu)于DV-Hop2。當(dāng)錨節(jié)點比例很大時,改進DV-Hop1在對更多錨節(jié)點進行距離補償后,更加有效地調(diào)節(jié)平均跳距,明顯地降低定位誤差。雖然錨節(jié)點比例增大有利于提高改進DV-Hop2的有效性,但由于沒有考慮節(jié)點之間的不均勻度,造成了在錨節(jié)點比例很大時,反而降低了模型的有效性,相對提高了誤差。

圖8顯示,當(dāng)通信半徑較小時,改進DV-Hop1的誤差率與原算法、改進DV-Hop2的誤差率基本接近。隨著通信半徑的增大,改進DV-Hop1的誤差率明顯低于原算法、改進DV-Hop2的誤差率。當(dāng)節(jié)點的通信半徑較小時,錨節(jié)點之間的跳數(shù)相對增多,在部署區(qū)域不變的條件下,式(9)中局部節(jié)點密度相對變大,雖然能提高偏離度的估計精度,但局部節(jié)點密度的變化,使得不均勻度精度受到較大影響,使改進算法的距離補償精度降低。隨著通信半徑的增大,節(jié)點間跳數(shù)相對減少,偏離度和不均勻度有效地補償了錨節(jié)點間距離,另一方面,式(9)中節(jié)點密度相對變小,而在整體節(jié)點密度不變的條件下,通信半徑的變化有效地提高了不均勻度的估計精度,從而提高了節(jié)點的定位精度。

圖9顯示,在監(jiān)測區(qū)域隨機部署不同數(shù)量的節(jié)點,數(shù)量為50,75,…,200,每個節(jié)點的半徑均為30 m,同時,每次部署的節(jié)點中,錨節(jié)點比例保持30%不變。在節(jié)點密度不斷增大的趨勢下,改進算法和原算法的定位誤差率都呈現(xiàn)遞減趨勢。在節(jié)點密度較低時,錨節(jié)點數(shù)量較少,對于距離補償模型對平均跳距的修正作用較小,因此,節(jié)點定位誤差率較高。隨著節(jié)點密度增大,錨節(jié)點相應(yīng)數(shù)據(jù)的增多,都使得距離補償模型很好地修正了平均跳距,有效性有很大程度提高,有效地降低了節(jié)點定位誤差率。但當(dāng)節(jié)點密度很大時,誤差率降低趨勢變緩。說明節(jié)點分布密度過大,對節(jié)點定位并不一定會有很好的效果。

5 結(jié)束語

本文在分析傳統(tǒng)DV-Hop算法缺陷的基礎(chǔ)上,提出一種基于距離補償模型的改進DV-Hop定位算法。該算法在不增加額外硬件設(shè)備和算法復(fù)雜度條件下,能有效補償原算法中錨節(jié)點之間距離的不足,在保持原算法簡單、低成本優(yōu)點的前提下,較好地降低定位誤差。在改進算法中,隨著錨節(jié)點比例和通信半徑的變化,優(yōu)化算法對錨節(jié)點間距離的修正程度愈發(fā)明顯,這也從側(cè)面反映出所提出的理論模型的可行性和有效性,但在錨節(jié)點比例和通信半徑都較大的條件下,模型沒有做出預(yù)測,同時,仿真結(jié)果也說明,還可以在錨節(jié)點稀疏和稀疏網(wǎng)絡(luò)的情況下做進一步的研究。

［1]孫利民,李建中,陳 瑜.無線傳感網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社,2005.

［2]Yick J,Mukherjee B,Ghosal D.Wireless Sensor Network Survey［J］.Computer Networks,2008,52(12):2292-2230.

［3]Karl H,Willig A.Protocols and Architectures for Wireless Sensor Networks［M］.［S.l.］:Wiley,2005.

［4]Niculescu D.Positioning in Ad Hoc Sensor Networks［J］.IEEE Network,2004,18(4):24-29.

［5]朱海榮,李 平,陳 劍.基于改進PSO算法的WSN覆蓋優(yōu)化方法［J］.計算機工程,2011,37(8):82-85.

［6]Dai Ying,Wang Jianping,Zhang Chongwei.Improvement of DV-Hop Localization Algorithms for Wireless Sensor Networks［J］.Wireless Communications Networking and Mobile Computing,2010,1(4):23-25.

［7]Yi Xiao,Liu Yu,Deng Lu,et al.An Improved DV-Hop Positioning Algorithm with Modified Distance Error for Wireless Sensor Network［C］//Proceedings of the 2nd International Symposium on Knowledge Acquisition and Modeling.Washington D.C.,USA:IEEE Press,2009: 216-218.

［8]Niculesca D,Nath B.DV Based Positioning in Ad Hoc Networks［J］.Journal of Telecommunication System, 2003,22(14):267-280.

［9]Wang Ruijin,Zhang Bo,Shen Yang,et al.PHDV-Hop: A More Accurate DV-Hop Positioning Algorithm in WSN［J］.International Journal of Digital Content Technology and Its Applications,2012,6(13):89-97.

［10]Kumar S,Lobiyal D K.An Advanced DV-Hop Localization Algorithm for Wireless Sensor Networks［J］.Wireless Personal Communications,2013,71(2):1365-1385.

［11]李云飛,江 明,婁 柯,等.無線傳感器網(wǎng)絡(luò)中DVHop定位算法的改進［J］.計算機工程與應(yīng)用,2014, 50(3):79-81.

［12]唐 弢.基于錨節(jié)點的無線傳感器網(wǎng)絡(luò)定位技術(shù)研究［D］.哈爾濱:哈爾濱工業(yè)大學(xué),2013.

［13]李旭東,趙 雪.矩形和橢圓內(nèi)均勻分布隨機點定理及應(yīng)用［J］.成都理工大學(xué)學(xué)報,2012,39(5): 555-558.

編輯 金胡考

Improved DV-Hop Localization Algorithm Based on Distance Compensation Model

GAO Wengen,CHEN Qigong,JIANG Ming,LI Yunfei,NIU Mingqiang
(Anhui Key Laboratory of Detection Technology and Energy Saving Devices,Anhui Polytechnic University,Wuhu 241000,China)

The traditional DV-Hop localization algorithm estimates the average hop distance with the physical distance between the anchor nodes instead of actual transmission distance,and the distance error between the two kinds of distance undoubtedly leads to the inaccuracy of the average hop distance and relatively high localization error.Aiming at this problem,the improved algorithm is proposed.The reason of error between the physical distance and actual transmission distance is analyzed in the paper,and is summarized as the asymmetry of distance resulted from the nodes random distribution,as well as the deviation degree between the actual transmission path and the physical distance,and the distance compensation model is built based on the asymmetry and deviation degree to make the physical distance closer to the transmission distance.The improved algorithm increases no extra hardware and the complexity of the DV-Hop.The simulation results show that the improved algorithm compensates the distance between the anchor nodes,and improves the localization accuracy to the unknown nodes.

distance compensation;estimated distance;asymmetry degree;deviation degree;DV-Hop positioning algorithm;Wireless Sensor Network(WSN)

高文根,陳其工,江 明,等.基于距離補償模型的改進DV-Hop定位算法［J］.計算機工程,2015, 41(3):32-36.

英文引用格式:Gao Wengen,Chen Qigong,Jiang Ming,et al.Improved DV-Hop Localization Algorithm Based on Distance Compensation Model［J］.Computer Engineering,2015,41(3):32-36.

1000-3428(2015)03-0032-05

:A

:TP393

10.3969/j.issn.1000-3428.2015.03.006

國家自然科學(xué)基金資助項目(61271377,61172131)。

高文根(1973-),男,講師、博士研究生,主研方向:無線傳感器網(wǎng)絡(luò);陳其工(通訊作者),教授、博士生導(dǎo)師;江 明,教授;李云飛、牛明強,碩士研究生。

2014-10-08

:2014-11-04E-mail:ahpuchina@ahpu.edu.cn