基于跳距優化的改進型DV-Hop定位算法*

景路路,張玲華(.南京郵電大學物聯網學院,南京 20003;2.南京郵電大學江蘇省通信與網絡技術工程研究中心,南京 20003)

?

基于跳距優化的改進型DV-Hop定位算法*

景路路1,張玲華2*
(1.南京郵電大學物聯網學院,南京 210003;2.南京郵電大學江蘇省通信與網絡技術工程研究中心,南京 210003)

DV-Hop定位算法是無線傳感器網絡節點定位的關鍵技術之一。傳統DV-Hop定位算法節點定位,因跳數計算和跳距估計產生偏差,影響定位誤差,為了提高定位精度,提出一種改進型定位算法。改進算法引入多通信半徑方法細化節點間的跳數,計算未知節點平均跳距時,剔除孤立節點,并對利用錨節點得到的平均跳距進行加權歸一化處理,使得未知節點定位精度提高。仿真結果顯示,改進算法在不明顯提高算法復雜度與通信量的基礎上大大提高了定位精度。

無線傳感器網絡;DV-Hop定位算法;改進算法;通信半徑;加權平均

節點定位是無線傳感器網絡非常關鍵的一項技術。根據現有定位機制,將定位算法分為基于距離的(Range-based)定位算法和距離無關的(Range-free)定位算法兩種。基于距離的(Range-based)定位的算法有RSSI、TOA、TDOA、AOA等,適用于定位精度要求較高的應用場景中,這類算法對傳感器節點的硬件要求較高。距離無關的(Range-free)定位算法適用于定位精度要求不高的場景,或者出于硬件成本、實現復雜度等方面的考慮,可以采用距離無關(Range-free)的定位技術,常用有質心定位算法[1]、APIT[2]定位算法、DV-Hop[3-16]等。目前實際應用的定位系統絕大多數采用距離無關的(Range-free)定位算法。

DV-Hop算法采取距離矢量-跳數機制,由于其無需節點間距的測量及不需附加硬件支持,成為一種備受關注的距離無關的(Range-free)算法。目前許多學者提出了不同的方法對DV-Hop算法進行改進以提升定位精度:文獻[9-16]對跳數進行修正,再根據估計距離的誤差修正平均跳距;文獻[10]利用平均跳距誤差修正待定位節點的平均跳距;文獻[11]提出了一種基于跳距加權平均的的DV-Hop算法,對未知節點與各個錨節點的平均跳距進行歸一化加權處理,離未知節點較近的錨節點分配大的權值;文獻[12]計算每個錨節點平均跳距誤差,進而修正之前得到的平均跳距。文獻[11-12]與傳統DV-Hop算法相比較,定位精度有一定提高,缺點是計算成本和通信開銷比較大。文獻[13]在跳距修正、未知節點與錨節點之間距離的計算以及節點定位方法3個方面進行了改進,缺點是計算量較大。本文提出了一種基于跳距優化的改進型DV-Hop算法。在盡可能減小計算量的情況下,采用多通信半徑進行通信,并對利用錨節點計算得到的平均跳距進行加權歸一化處理,使得未知節點與錨節點之間的平均跳距更接近于真實值。仿真結果表明,相比原始DV-Hop算法,本文算法在定位精度上有顯著提高。

1 DV-Hop算法與誤差分析

1.1 傳統DV-Hop算法

DV-Hop算法是Rutgers大學的Dragons等人基于矢量路由及全球定位系統GPS提出的一種距離無關的(Range-free)定位算法[3]。主要包括3個階段,大體步驟如下:

①計算未知節點與錨節點的最小跳數。錨節點廣播包含自身位置信息和跳數字段的分組,跳數初始化為0.其他節點記錄其收到的每個錨節點的最小跳數,忽略來自同一錨節點較大跳數的分組,并將跳數字段加1轉發給相鄰節點。通過這種方式,網絡中所有節點均能獲得到每個錨節點的最小跳數。

②估算未知節點和錨節點間的距離。每個錨節點根據第1階段中獲得的其他錨節點的位置信息和最小跳數,利用式(1)估算錨節點平均每跳距離:

(1)

式中:(xi,yi)為錨節點i的位置坐標;hij為錨節點i和j之間的最小跳數。然后錨節點將計算的平均每跳距離廣播至網絡中,未知節點收到每跳距離并根據其到各個錨節點的最小跳數來估算其到各錨節點的距離。用hi表示某未知節點到第i個錨節點的最小跳數:

di=hi×HopSizeij(i≠j)

(2)

就可以計算出未知節點距第i個錨節點的距離,這里用di表示,見式(2)。

③利用基于距離的(Range-based)定位算法計算節點位置。未知節點利用步驟(2)中計算得到的到各錨節點的距離,采用基于距離的(Range-based)定位算法(極大似然估計)估計節點自身位置。

為了便于理解,我們假設網絡拓撲結構如圖1所示。

圖1 傳統DV-Hop算法示例

圖1中B1、B2、B3是3個錨節點,P是未知節點。經過步驟(1)B1得到帶有B2、B3位置信息和跳數信息的分組,如圖所示,B1、B2之間跳數為2,B2、B3之間的跳數為5,我們可以計算出該網絡中錨節點平均每跳的跳距:

hopsize=(42+77)/(2+5)=17

(3)

即可獲得未知節點P到B1、B2、B33個錨節點的距離:

(4)

1.2DV-Hop算法誤差分析

在DV-Hop算法中,用最小跳數來衡量節點間的距離。當跳數越小,即可認為距離就越近。假設兩個節點,只要可以進行直接通信,那么跳數值就記為1。能和同一節點直接通信的所有節點,距離不會完全一樣,比如圖1中B1、B2之間,一個未知節點間隔成兩段,跳數都計為1,但距離并不一樣。由此可見,經常會有節點間實際距離相差很大但是最小跳數一樣的情況。這樣的跳數誤差也會導致一定的定位誤差。所以,在計算跳數時可以采用多個通信半徑的方法,細化節點間跳數。

在通信過程中,通信半徑規定了某些節點屬于上級節點的相鄰節點,從而對節點間的跳數起了決定性作用,也同樣的決定了每一跳的距離。所以,在計算未知節點平均每跳的距離時,對利用錨節點所得到的平均跳距進行加權歸一化處理,能得到更精確的平均跳距值,進一步減小定位誤差。

在本文中,我們采用相對定位誤差來研究不同DV-Hop算法的定位誤差問題:

(5)

式中:N是未知節點的數量,(xm,ym)、(xr,yr)為待定為節點的估計坐標和真實坐標,R是通信半徑。

2 改進型的iDV-Hop算法

2.1 基本思路

通過對傳統DV-Hop算法分析可知,通信半徑的選取至關重要,在考慮到計算成本的同時,本文選取4個通信半徑,即R(未知節點和錨節點都使用的通信半徑R)、0.75R、0.5R、0.25R,這3個為錨節點專用通信半徑。錨節點不同的通信范圍,劃分了4組節點,如圖2,分為A、B、C、D。A組指的是錨節點在通信半徑0.25R內廣播信息時,能接收到信息的所有相鄰節點;B組指的是在通信半徑0.5R內廣播信息時,能接收到信息的所有相鄰節點。C組指的是在通信半徑0.75R內廣播信息時,能接收到信息的所有相鄰節點。D組指的是在通信半徑R內廣播信息時,能接收到信息的所有相鄰節點。如圖2所示:4組節點之間具有包含關系。

圖2 4通信半徑示意圖

錨節點廣播跳段信息時,A組節點到錨節點的最小跳數計為0.25,B組節點到錨節點的最小跳數計為0.5,C組節點記錄的到錨節點的最小跳數計為0.75,D組節點到錨節點的最小跳數計為1。然后,相鄰節點以通信半徑R廣播錨節點發來的分組信息。當消息傳輸結束后,每個節點都獲得了到錨節點的最小跳數。最短通信路徑如果經過A組和B組節點,最后記錄的最小跳數就有可能不是一個整數。使用這種辦法,錨節點利用0.75R、0.5R和0.25R的通信半徑通信時,最小跳數更加精確,跳距的計算也更為準確,定位精度提高。

與圖1對比,圖3采用同樣網絡拓撲結構,B1與A節點之間的跳數為0.25,B2與P之間為兩個0.25,P與B3之間有兩個0.75、一個1,則有下式:

(6)

式(6)比式(3)更接近于真實值。P與B1、B2、B3之間的距離也更接近于真實值。

圖3 4通信半徑算法示例

傳統DV-Hop算法中,未知節點估計自身位置,接收的是距離最近的錨節點估計的平均跳距值,用該值作為未知節點自身的平均跳距來估計自身位置。網絡中某個錨節點的平均跳距值并不能反映網絡中全部節點的屬性。改進算法在計算未知節點的平均跳距時進行加權處理,綜合考慮可以與未知節點通信的全部錨節點,各個錨節點計算出的平均跳距值與到未知節點跳數值的乘積作為未知節點平均跳距的加權參數值,并對所有權值進行歸一化處理。加權參數如下:

(7)

式中:n為未知節點可以通信的錨節點個數,disu表示未知節點到第u個錨節點之間跳數與錨節點平均跳距的乘積,通過式(7)歸一化處理,未知節點獲得n個錨節點平均跳距加權值,這n個加權值之和為1。在錨節點廣播跳數和平均跳距信息時,未知節點記錄兩者乘積并對數值較大的賦予較小的權值αu,求未知節點的平均跳距,加入該加權參數進行校正。

以上改進算法稱為iDV-Hop算法。

2.2 改進算法的基本步驟

①獲取網絡中未知節點與錨節點的最小跳數

與傳統DV-Hop算法相同,通過泛洪的方式在網絡中廣播自身的位置信息。網絡初始化,錨節點先在網絡中進行第1次廣播分組信息,此時的通信半徑設為0.25R。相鄰節點接收到錨節點發送的分組信息,到該錨節點的最小跳數記為0.25。此時的相鄰節點并不進行信息的轉發,這樣可以減小通信方面的開銷。

經過第1個時間t后,錨節點進行第2次廣播分組信息,通信半徑為0.5R。如果節點是第1次收到某個錨節點的分組信息,就把距該錨節點的最小跳數記為0.5。若不是第1次,證明該節點記錄的最小跳數為0.25。保留較小的跳數值,即0.25。此時的相鄰節點不進行信息的轉發,同樣可以減小通信開銷。

經過第2個時間t后,錨節點進行第3次的廣播分組信息,通信半徑為0.75R。最小跳數獲取同上。

經過第3個時間t后,錨節點進行第4次的廣播分組信息,通信半徑為R。最小跳數獲取后,節點把目前記錄的跳數值相應地加1后轉發出去。這樣,每個節點就都能獲得距錨節點的最小跳數,這里也用hi表示。

圖4 不同通信半徑誤差分析圖

②計算平均每跳距離,估算未知節點與錨節點之間的距離

每個錨節點根據步驟①可獲得到其他錨節點的位置信息和最小跳數,利用式(1)估算錨節點的平均每跳距離。錨節點廣播帶有跳數和平均跳距的分組,未知節點記錄跳數和錨節點平均跳距的乘積值di,并對di值較大的賦予較小的權值αu,加權參數為式(7),再利用式(8)計算未知節點的平均跳距值:

(8)

校正之后,式(2)求未知節點到第i個錨節點距離計算方法則變成式(9):

avgdi=hi×UnHopSizei

(9)

利用式(9)可得未知節點與錨節點之間的距離。

③利用基于距離的(Range-based)定位算法計算節點位置。未知節點利用步驟②得到未知節點到錨節點的距離,采用基于距離的定位算法(極大似然估計)估計節點自身位置。

3 仿真結果分析

假設仿真環境為邊長100 m的正方形二維區域,100個節點隨機分布。通信半徑分別取:20 m、28 m、36 m、44 m、分別對傳統DV-Hop算法和改進iDV-Hop算法進行了對比。相同比例的錨節點情況下,實驗進行100次,取平均值。圖4(a)～圖4(d)為不同半徑時,隨錨節點比例變化的誤差分析圖。

由圖4(a)～圖4(d)可以看出,不同半徑下,相對定位誤差隨著錨節點個數的增加而呈現減小的趨勢,100個節點中,錨節點個數大于20時,相對定位誤差會趨于穩定。當錨節點個數小于20時,通信半徑在30 m左右或者大于30 m時,相對定位誤差基本處于0.20以下,即控制在20%以內。當錨節點個數一定,通信半徑變大時,相應網絡的連通度會變大,相對定位誤差趨于變小。

圖4(a)～圖4(d)是通信半徑為20 m～44 m時的改進算法和傳統算法的對比,iDV-Hop算法(改進的4通信半徑算法)比改進的2通信半徑算法相對定位誤差降低了7%～9%,iDV-Hop算法(改進的4通信半徑算法)比改進的3通信半徑算法相對定位誤差降低了2%～3%,iDV-Hop算法(改進的4通信半徑算法)比傳統DV-Hop算法相對定位誤差降低了16%～25%。

4 結束語

本文首先對傳統DV-Hop算法進行了分析,明確了誤差的部分來源,在此基礎上采用了多半徑通信和加權參數的方法進行改進,在利用錨節點求平均跳距時剔除了孤立節點,綜合考慮所有可進行通信的錨節點的平均跳距值,并進行了加權歸一化處理。可以看出,采用了改進算法之后,相對定位誤差降低16%～25%。此外,網絡拓撲結構的變化也會帶來定位誤差的變化,本文是在相同的仿真條件下進行了100次實驗取得的平均值,盡可能減小這種拓撲結構的影響。錨節點的覆蓋率也會影響實驗結果,未來會進一步改進。

[1] 陳維克,李文峰,首珩,等. 基于RSSI的無線傳感器網絡加權質心定位算法[J]. 武漢理工大學學報,2006,30(12):265-268.

[2] 周勇,夏士雄,丁世飛,等. 基于三角形重心掃描的改進APIT無線傳感器網絡自定位算法[J]. 計算機研究與發展,2009,46(4):566-574.

[3] Hadir A,Zine-Dine K,Bakhouya M,et al. An Optimized DV-Hop Localization Algorithm Using Average Hop Weighted Mean in WSNs[C]//Codes,Cryptography and Communication Systems(WCCCS),2014 5th Workshop on,IEEE,Nov,2014:25-29.

[4] 江禹生,馮硯毫. 一種新的DV-Hop定位算法[J]. 傳感器技術學報,2003,23(12):1815-1819.

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

[6] Wang Yun,Wang Xiao,Wang Demin,et al. Range-Free Localization Using Expected Hop Progress in Wireless Sensor Networks[J]. IEEE Transactions on Parallel and Distributed Systems,2009,20(10):1540-1552.

[7] 孫利民,李建中,陳渝,等. 無線傳感器網絡[M]. 北京:清華大學出版社,2005:135-155.

[8] Peng Y,Wang D. A Review:Wireless Sensor Networks Location[J]. Journal of Electronic Measurement and Instrument,2011,25(5):389-399.

[9] 夏少波,鄒建梅,朱曉麗,等. 無線傳感器網絡DV-Hop定位算法的改進[J]. 計算機應用,2015,35(2):340-344.

[10] Ju H,Yang X,Qi Y,et al. Dynamic Updating Multigranulation Fuzzy Rough Set:Approximations and Reducts[J]. International Journal of Machine Learning and Cybernetics,2014,5:981-990.

[11] 劉峰,張翰,楊驥. 一種基于加權處理的無線傳感器網絡平均每跳跳距估計算法[J]. 電子與信息學報,2008,30(5):1222-1225.

[12] 林金朝,劉海波,李國軍,等. 無線傳感器網絡中DV-Hop節點定位改進算法的研[J]. 計算機應用研究,2009,26(4):1272-1275.

[13] Ji W,Liu Z. Study on the Application of DV-Hop Location Algorithms to Random Sensor Networks[J]. Journal of Electronics and Information Technology. 2008,30(4):970-974.

[14] 魏全瑞,劉俊,韓九強. 改進的無線傳感器網絡無偏距離估計與節點定位算法[J]. 西安交通大學學報,2014,48(6):1-6.

[15] 李娟,劉禹,錢志鴻. 于雙通信半徑的傳感器網絡DV-Hop定位算法[J]. 吉林大學學報(工學版),2014,44(22):502-507.

[16] 夏少波,朱曉麗,鄒建梅,等. 基于跳數修正的DV-Hop改進算法[J]. 傳感器技術學報,2015,28(5):757-762.

景路路(1989-),南京郵電大學,碩士研究生,主要研究方向為無線傳感器網絡定位,279233614@qq.com;

張玲華(1964-),南京郵電大學,教授、博士生導師,主要研究領域為數字信號處理、智能信號處理、語音信號處理及現代通信技術、無線傳感器網絡等,zhanglh@njupt.edu.cn。

An Improved DV-Hop Algorithm Based on Optimization of One-Hop Distance for Sensor Network Localization*

JING Lulu1,ZHANG Linghua2*
(1.College of Internet of things,Nanjing University of Posts and Telecommunications,Nanjing 210003,China;2.Jiangsu Engineering Research Center of Communication and Network Technology,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

DV-Hop localization algorithm is one of the key technologies of wireless sensor network node localization. The traditional DV-Hop localization algorithm due to the deviation of calculation the number of hops and estimate of one-hop distance,resulting in greater localization errors. In order to reduce the location error,an improved positioning algorithm is proposed. The improved algorithm broadcasts the data using multi communication radius and refines the hops to reduce the location error. When calculating the average hop distance of unknown nodes,,remove the isolated nodes,introduce weighted normalization processing,to obtain a more precise one-hop distance. The simulation result indicates that the improved algorithm can greatly improve the location accuracy without obviously increasing algorithm complexity and communication traffic.

wireless sensor network;DV-Hop location algorithm;improved algorithm;communication radius;weighted average

項目來源:江蘇省教育自然科學研究重大項目(13KJA510003);江蘇高校優勢學科建設工程項目(PAPD)

2016-10-11 修改日期:2016-12-01

TP393

A

1004-1699(2017)04-0582-05

C:7230

10.3969/j.issn.1004-1699.2017.04.017