一種基于坐標改正的改進DV-Hop定位算法*

王 興,聶云峰,徐飛飛

(南昌航空大學信息工程學院,南昌 330063)

項目來源:國家自然科學基金項目(41101426)

2017-04-18修改日期2017-06-09

一種基于坐標改正的改進DV-Hop定位算法*

王 興,聶云峰*,徐飛飛

(南昌航空大學信息工程學院,南昌 330063)

為有效提高DV-Hop算法在拓撲隨機網絡中的定位精度,提出一種利用錨節點定位誤差修正未知節點坐標的新方法(PEDV-Hop)。首先定義偽距誤差因子剔除對平均跳距計算產生較大誤差的錨節點,從而有效抑制網絡拓撲隨機分布影響,提高平均跳距計算精度;其次,視錨節點為未知節點,在計算平均跳距的同時,運用三邊或多邊測量法評估自身定位坐標,從而可計算得到錨節點坐標改正值,并將平均跳距與坐標改正值向網絡廣播;最后,未知節點根據接收到各錨節點的坐標改正值來修正自身定位誤差,從而有效提高節點定位精度。仿真結果表明,PEDV-Hop算法實現簡單,有效提高了節點的定位精度。

DV-Hop算法;節點定位;平均跳距;偽距誤差因子

無線傳感網絡WSN(Wireless Sensor Networks)是由部署在監測區域內的大量微型并裝備低能耗收發器和有限數據處理能力的感知節點通過無線通信形成的多跳自組織網絡[1]。節點定位是WSN的關鍵技術之一[2],定位算法按測距與否可分為:基于測距(Range-based)和免測距(Range-free)兩種[3]。其中,基于測距的定位方法對硬件有較高要求,一般需借助特定硬件測量出相鄰節點間的角度或距離,計算和通信開銷大;而免測距定位算法,只需依靠網絡連通性或網絡拓撲關系就可以實現定位[4-5],具有成本低、定位過程簡單且能提供較理想定位精度等優勢,因此更適合大規模無線傳感網絡節點定位的實際應用需求[6]。

DV-Hop定位算法作為一種經典的免測距定位方法,以其過程簡潔,效果較好得到廣泛的應用,目前國內外研究者針對該算法的優化提出大量具有參考價值的改進算法,大致可分為以下3類:

①錨節點選取優化類算法。文獻[7]基于引入RSSI測距技術提出限制機制以減少節點的通信量和能耗,并通過優化參與定位的錨節點組合和質心算法有效降低定位誤差;文獻[8]通過Min-Max算法對未知節點進行初始位置的估計,然后通過未知節點和錨節點間的位置關系將未知節點升級為錨節點來增加錨節點的密度,從而提高網絡中其他節點的定位精度;文獻[9]通過設置未知節點接收錨節點信息數量的閾值,選擇距離較近的部分錨節點作為參考節點,減少定位誤差和計算量,提高效率和定位精度。

②平均跳距修正類算法,如:文獻[10]采用Cayley-Menger行列式給出的距離幾何約束條件對未知節點和錨節點間的估計距離進行處理,提高定位精度;文獻[11]采用最小二乘法和加權處理法修正錨節點間的平均跳距,并通過迭代求解法提高未知節點的定位準確性和精度的穩定性;文獻[12]通過最小均方差準則改進平均跳距的公式,并在最佳指數值下,修正錨節點的平均跳距,以此來提高節點定位的精度。

③跳數修正類算法,如:文獻[13]通過提出非整數的錨節點間跳數,使用跳數偏離因子對未知節點與錨節點間跳數進行修正,使得節點間距離估計更加準確;文獻[14]通過RSSI值對1跳鄰居節點進行分級,細化跳數,然后將節點間的距離比值作為跳數修正的權值,從而抑制跳數值計算誤差帶來的定位偏差較大的問題;文獻[15]根據跳數信息對錨節點進行了分類,設定不同跳數閾值,只選擇大于或等于跳數閾值的節點參與距離估算,以實現定位精度的提升。

在DV-Hop族系算法中,錨節點平均跳距的估算對定位精度有至關重要影響,對于節點分布均勻、各項同性的密集型網絡,通?？傻玫捷^合理的平均跳距,從而達到適當的定位精度,但對于網絡拓撲不規則、隨機分布的傳感網絡來說,錨節點到未知節點間往往不是直線路徑,用跳段距離代替直線距離誤差較大,因此定位精度較低[16-17]。為解決上述問題,提出一種利用錨節點定位誤差修正未知節點坐標的新方法——PEDV-Hop(Pseudo-Range Error DV-Hop)。該算法首先定義偽距誤差因子剔除對平均跳距計算產生較大誤差的錨節點,從而有效抑制網絡拓撲隨機分布影響,提高平均跳距計算精度;其次,視錨節點為未知節點,在計算平均跳距的同時,運用三邊或多邊測量法評估自身定位坐標,從而可計算得到錨節點坐標改正值,并將平均跳距與坐標改正值向網絡廣播;最后,未知節點根據接收到各錨節點的坐標改正值來修正自身定位誤差,從而有效提高節點定位精度。

1 DV-Hop算法

DV-Hop是Dragos Niculescu等人根據距離矢量路由原理提出的定位算法[18-20],主要包括3個階段:第1階段,使用典型的距離矢量交換協議,通過節點間的信息交換,使網絡中所有節點獲得與錨節點之間的跳數及錨節點位置信息;第2階段,錨節點計算平均跳距,然后將其作為一個跳距校正值廣播至網絡中,其中校正值采用可控洪泛法在網絡中傳播,這意味著一個節點僅接受獲得的第1個校正值,而丟棄所有后來者,這個策略確保了絕大多數節點可從最近的錨節點接收校正值。當未知節點接收到該校正值之后,用該校正值乘以到附近各錨節點之間的跳數,從而得出估計的歐氏距離;第3階段,當未知節點獲得與3個或更多錨節點間的歐氏距離時執行三邊或多邊測量定位法對未知節點進行定位。

傳統DV-Hop算法使用平均跳距與跳數相乘來計算實際距離,用節點間的直線距離來估算節點間信息通路的曲線距離。在計算最小跳距時,無論相近節點間物理距離的遠近,跳數值均加一,并不能反映出實際距離的差別,并且對于節點隨機分布的傳感網絡而言,錨節點到定位節點往往不是直線路徑,故采用經典DV-Hop算法可能會帶來較大的距離計算誤差。

2 PEDV-Hop算法

針對傳統DV-Hop定位算法在節點隨機分布、拓撲不規則傳感網絡中的定位精度較差的問題,提出PEDV-Hop算法通過定義偽距誤差因子對第2階段平均跳距進行修正,并利用錨節點坐標改正值對第3階段未知節點坐標進行修正,從而有效提高節點定位精度。

2.1 平均跳距修正

設隨機分布的網絡中錨節點的個數為N。通過典型的距離矢量交換協議,使網絡中所有節點獲得與錨節點之間的跳數及錨節點位置信息,錨節點Ni利用式(1)估算平均跳距:

(1)

定義Ni與Nj之間的偽距為:

(2)

定義Ni與Nj之間的偽距誤差因子為:

(3)

在隨機分布的網絡中,Ni與Nj之間的偽距與真實距離的誤差可能很大,將Ni與Nj之間的偽距誤差因子按升序排列。取前K(K≥3)個節點參與Ni平均跳距的計算,目的是剔除對測距誤差影響較大的錨節點,從而有效抑制拓撲隨機分布的影響,則Ni的平均跳距修正為:

(4)

2.2 錨節點坐標改正值計算

(5)

2.3 未知節點坐標改正

未知節點記錄接收到的錨節點的平均跳距及坐標改正值,根據記錄的跳數,計算到每個錨節點的跳段距離,采用三邊測量或最小二乘法計算自身的估計坐標。

(6)

式中:N為錨節點總數。

2.4PEDV-Hop算法流程

Step 1 網絡初始化;

Step 2 使用典型的距離矢量交換協議,錨節點Ni在網絡中廣播包含自身位置信息的數據包{IDi,(xi,yi),hop},通過節點間的信息交換,使網絡中所有節點獲得與錨節點之間的跳數;

Step 5 算法結束。

3 仿真分析

仿真場景為100 m×100 m的感知區域,節點總數為150,錨節點總數為N,K取值見3.2節,未知節點和錨節點隨機產生。定義平均定位誤差ave_error作為算法性能的評價標準,ave_error計算方法如式(7)所示:

(7)

式中:(xi,yi)、(Xi,Yi)分別為節點i的估計坐標和真實坐標,R為通信半徑,n為未知節點數。

3.1 結果分析

圖1給出了DV-Hop算法、文獻[17]算法、DDV-Hop算法、PEDV-Hop_1算法和PEDV-Hop算法在不同錨節點比例及通信半徑下定位誤差的比較結果。

圖1 錨節點比例、節點通信半徑變化下各算法定位誤差比較

圖1表明:①在相同的通信半徑下,上述算法的定位誤差隨著錨節點比例增加而減小,并逐漸趨于平穩。當錨節點比例小于20%時,隨著錨節點比例增加,PEDV-Hop算法定位精度提高明顯、變化幅度較大,比DV-Hop算法降低19%～25%,比PEDV-Hop_1算法降低8%～14%,比文獻[17]定位算法降低4%～10%,比DDV-Hop算法降低2%～12%;當錨節點比例大于20%時,PEDV-Hop算法定位精度提升較慢,趨于平穩,比DV-Hop算法降低17%～26%,比PEDV-Hop_1算法降低7%～13%,比文獻[17]定位算法降低5%～15%,比DDV-Hop算法降低1%～6%。

②在相同的錨節點比例下,隨著通信半徑增大,PEDV-Hop算法、PEDV-Hop_1算法、DV-Hop算法定位精度變化平穩,DDV-Hop算法及文獻[17]算法的誤差曲線變化波動較大;而且隨著通信半徑增大,PEDV-Hop算法定位精度總體呈下降趨勢,但比DV-Hop算法定位誤差減小幅度變大。這是因為隨著通信半徑的增大,網絡連通性變強,網絡拓撲結構更加復雜,導致平均跳距的估計誤差變大[21],而PEDV-Hop算法通過定義偽距誤差因子修正平均跳距,有效的抑制網絡拓撲隨機分布影響,提高了平均跳距計算精度,從而提高了節點定位精度。

③在相同的通信半徑及通信半徑下,PEDV-Hop_1算法定位精度比DV-Hop算法平均高11%,說明PEDV-Hop算法第1步修正的有效性;但比PEDV-Hop算法定位精度平均低13%,說明PEDV-Hop算法第2步修正的有效性。

3.2 K取值分析

在PEDV-Hop算法中,K的取值決定參與平均跳距計算錨節點數量,對平均跳距估算有一定的影響。本節通過實驗觀察K取值對PEDV-Hop定位精度的影響。實驗結果如圖2所示。

圖2 K取值對定位誤差的影響

圖2表明,K值的變化直接影響算法定位精度?？傮w上,當3≤K≤?N/3」時定位精度呈波動上升趨勢;當?N/3」≤K≤?N/3」時定位精度最優;當?N/2」≤K≤N時定位精度呈波動下降趨勢。因此,當?N/3」≤K≤?N/2」時,PEDV-Hop算法定位精度最優。

4 結語

本文介紹了DV-Hop算法的原理及實現過程,分析了DV-Hop在節點隨機分布、網絡拓撲不規則網絡中定位精度較低的問題,提出PEDV-Hop改進算法,通過定義偽距誤差因子修正平均跳距,并利用錨節點坐標改正值修正未知節點坐標,從而有效提高節點定位精度。仿真實驗對比了在不同通信半徑及錨節點比例下PEDV-Hop算法同傳統DV-Hop算法以及部分改進算法的定位精度差異,并對K取值進行探究。結果表明:PEDV-Hop算法穩定有效的提高了節點的定位精度;隨著通信半徑的增大,PEDV-Hop算法對傳統DV-Hop算法的改進效果更加明顯;總體上,當?N/3」≤K≤?N/2」時,PEDV-Hop算法精度最高。

[1] 孫立明,李建中,陳瑜,等. 無線傳感器網絡[M]. 北京:清華大學出版社,2005:149-151.

[2] Han G,Chao J,Zhang C,et al. The Impacts of Mobility Models on DV-Hop Based Localization in Mobile Wireless Sensor Networks[J]. Journal of Network and Computer Applications(S1084-8045),2014,42(4):70-79.

[3] Zhao J,Zhao Q,Li Z,et al. An improved Weighted Centroid Localization Algorithm Based on Difference of Estimated Distances for Wireless Sensor Networks[J]. Telecommunication Systems(S1018-4864),2013,53(1):25-31.

[4] Shang Y,Run I W,Zhang Y. Localization from Mere Connectivity[C]//Proc of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing Anna-Polis,USA:ACM,2003:201-211.

[5] Niculescu D,Nath B. Ad Hoc Positioning System(APS)Using AOA[C]//Proc of the 22nd Annual Joint Conf of the IEEE Computer and Communications Societies(INFOCOM’2003),2003(3):1734-1743.

[6] Bulusu N,Heidemann J,Estrin D. GPS-Less Low Cost Outdoor Localization for Very Small Devices[J]. IEEE Personal Communications Magazine,2000,7(5):28-34.

[7] 夏少波,鄒建梅,朱曉麗,等. 基于跳數區域劃分的DV-Hop改進算法[J]. 傳感技術學報,2014,27(7):964-969.

[8] 王翥,郝曉強,王玲. 基于錨節點選擇的無線傳感網絡器定位算法[J]. 計算機研究與發展,2010,47(S):31-34.

[9] 申鉉京,李成岳,王碩. 基于最優錨節點的無線傳感器網絡節點定位算法[J]. 吉林大學學報(工學版),2011,41,增刊:208-214.

[10] 鄭君剛,吳成東,秦好,等. 基于DV-Hop和距離幾何約束的定位算法[J]. 東北大學學報(自然科學版),2011,32(4):457-459.

[11] 林金朝,陳曉冰,劉海波. 基于平均跳距修正的無線傳感器節點迭代定位算法[J]. 通信學報,2009(10):107-113.

[12] 馬淑麗,趙建平. 多通信半徑的無線傳感網絡DV-Hop定位算法[J]. 傳感技術學報,2016,29(4):593-600.

[13] 肖麗萍,劉曉紅. 一種基于跳數修正的DV-Hop定位算法[J]. 傳感技術學報,2012,25(12):1726-1730.

[14] 溫江濤,范學敏,吳希軍. 基于RSSI跳數修正的DV-Hop改進算法[J]. 傳感技術學報,2014,27(2):502-507.

[15] 祝宇鴻,歷彥愷,王魯娜,等. 基于跳數閾值和節點分類的DV-Hop改進算法[J]. 吉林大學學報(信息科學版),2014,32(4):407-412.

[16] Hou S F,Zhou X J,Liu X X. A Novel DV-Hop Localization Algorithm for Asymmetry Distributed Wireless Sensor Networks[C]//3rd IEEE International Conference on Computer Science and Information Technology(ICCSIT),2010,4:243-248.

[17] Chen H Y,Karo S,Deng P,et al. A Improved DV-Hop Localization Algorithm for Wireless Sensor Networks[C]//IEEE ICIEA,2008:1557-1561.

[18] Niculescu D. Positioning in Ad Hoe Sensor Networks[C]//IEEE Network,2004,18(4):24-29.

[19] Niculescu D,Nath B. DV Based Positioning in Ad Hoc Networks[J]. Journal of Telecomm-Unications Systerns,2003,22(1/4):267-280.

[20] Kumar S,Lobiyal K. An Advanced DV-Hop Localization Algorithm for Wireless Sensor Networks[J]. Wireless Personal Communications,2013,71:1365-1385.

[21] 嵇瑋瑋,劉中. DV-Hop定位算法在隨機分布傳感器網絡中的應用研究[J]. 電子與信息學報,2008,30(4):970-974.

AnImprovedDV-HopLocalizationAlgorithmBasedonCoordinateCorrection*

WANGXing,NIEYunfeng*,XUFeifei

(School of Information Engineering,Nanchang Hangkong University,Nanchang 330063,China)

In order to improve the localization accuracy of DV-Hop algorithm in the random topology network scenario,a novel algorithm named PEDV-Hop is put forward. PEDV-Hop uses the localization error of anchor nodes to correct the coordinates of unknown nodes. Firstly,the pseudo-range error factor is defined to remove anchor nodes which may cause a larger calculation error of the average hop distance,through this way to improve the calculation accuracy of average hop distance,and to decrease the influence of topology random distribution. Secondly,the anchor node broadcasts the updated average hop distance together with its coordinate correction values calculated by trilateral or multilateral measurement with the premise of being treated as the unknown node. Lastly,the coordinates of each unknown node are corrected through the weighted average value of the coordinate correction values of the

anchor nodes. The simulation results show that PEDV-Hop algorithm has better localization accuracy and stability than the tradiDV-Hop algorithm and some existing improved algorithms,and it is easy to implement.

DV-Hop algorithm;node localization;average hop distance;pseudo-range error factor

TP393

A

1004-1699(2017)10-1560-05

10.3969/j.issn.1004-1699.2017.10.018

王興(1992-),男,碩士研究生,主要研究方向為無線傳感網絡,地理信息系統,Jwangxing0719@163.com;

聶云峰(1980-),男,博士,副教授,主要研究方向為無線傳感網絡,遙感與地理信息系統,nieyunf@gmail.com;

徐飛飛(1992-),男,碩士研究生,主要研究方向為無線傳感器網絡,1032074982@qq.com。