基于跳距優(yōu)化的改進型DV-Hop定位算法*

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

?

基于跳距優(yōu)化的改進型DV-Hop定位算法*

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

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

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

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

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

1 DV-Hop算法與誤差分析

1.1 傳統(tǒng)DV-Hop算法

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

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

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

(1)

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

di=hi×HopSizeij(i≠j)

(2)

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

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

為了便于理解,我們假設網(wǎng)絡拓撲結(jié)構(gòu)如圖1所示。

圖1 傳統(tǒng)DV-Hop算法示例

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

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

(3)

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

(4)

1.2DV-Hop算法誤差分析

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

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

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

(5)

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

2 改進型的iDV-Hop算法

2.1 基本思路

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

圖2 4通信半徑示意圖

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

與圖1對比,圖3采用同樣網(wǎng)絡拓撲結(jié)構(gòu),B1與A節(jié)點之間的跳數(shù)為0.25,B2與P之間為兩個0.25,P與B3之間有兩個0.75、一個1,則有下式:

(6)

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

圖3 4通信半徑算法示例

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

(7)

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

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

2.2 改進算法的基本步驟

①獲取網(wǎng)絡中未知節(jié)點與錨節(jié)點的最小跳數(shù)

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

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

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

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

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

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

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

(8)

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

avgdi=hi×UnHopSizei

(9)

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

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

3 仿真結(jié)果分析

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

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

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

4 結(jié)束語

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

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

[2] 周勇,夏士雄,丁世飛,等. 基于三角形重心掃描的改進APIT無線傳感器網(wǎng)絡自定位算法[J]. 計算機研究與發(fā)展,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] 孫利民,李建中,陳渝,等. 無線傳感器網(wǎng)絡[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] 夏少波,鄒建梅,朱曉麗,等. 無線傳感器網(wǎng)絡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] 劉峰,張翰,楊驥. 一種基于加權處理的無線傳感器網(wǎng)絡平均每跳跳距估計算法[J]. 電子與信息學報,2008,30(5):1222-1225.

[12] 林金朝,劉海波,李國軍,等. 無線傳感器網(wǎng)絡中DV-Hop節(jié)點定位改進算法的研[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] 魏全瑞,劉俊,韓九強. 改進的無線傳感器網(wǎng)絡無偏距離估計與節(jié)點定位算法[J]. 西安交通大學學報,2014,48(6):1-6.

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

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

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

張玲華(1964-),南京郵電大學,教授、博士生導師,主要研究領域為數(shù)字信號處理、智能信號處理、語音信號處理及現(xiàn)代通信技術、無線傳感器網(wǎng)絡等,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);江蘇高校優(yōu)勢學科建設工程項目(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