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

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

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

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

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

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

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

距離補償;估計距離;不均勻度;偏離度;DV-Hop定位算法;無線傳感器網絡

1 概述

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

在現有的無線傳感網絡定位算法中,主要存在2類定位算法,其主要區別在于,如何獲得節點之間

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

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

2 DV-Hop定位算法

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

3 DV-Hop算法的改進

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

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

假設未知節點獲得的校正值來自錨節點i,那么:

假設l2＞l1＞l3＞R,有:

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

圖1 傳統DV-Hop算法的網絡拓撲結構

3.2 距離補償模型

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

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

圖2 網絡拓撲的偏離度示意圖

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

節點A,B,C所在的區域節點密度為:

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

圖3 節點密度增加部分網絡拓撲的偏離度示意圖

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

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

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

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

圖4 偏離度為0的網絡拓撲結構

假設網絡中相鄰節點之間的距離均為R,那么相鄰節點之間不均勻度為0,如圖5所示。

圖5 不均勻度為0的網絡拓撲結構

可以得出此時的節點密度為:

其中,n是節點周圍的節點個數。在最理想的條件下,不均勻度為0所對應的最大節點個數為:

最大的節點密度和最小密度為:

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

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

同時,有:

由此,可以得到:

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

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

4 算法仿真及分析

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

圖6 WSN隨機部署節點分布

定義節點定位誤差δ為:

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

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

圖7 平均定位誤差隨錨節點個數的變化曲線

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

圖9 平均定位誤差隨節點總數的變化曲線

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

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

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

5 結束語

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

［1]孫利民,李建中,陳 瑜.無線傳感網絡［M］.北京:清華大學出版社,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覆蓋優化方法［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]李云飛,江 明,婁 柯,等.無線傳感器網絡中DVHop定位算法的改進［J］.計算機工程與應用,2014, 50(3):79-81.

［12]唐 弢.基于錨節點的無線傳感器網絡定位技術研究［D］.哈爾濱:哈爾濱工業大學,2013.

［13]李旭東,趙 雪.矩形和橢圓內均勻分布隨機點定理及應用［J］.成都理工大學學報,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

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

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

2014-10-08

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