一種基于IDV-Hop算法的改進定位機制*

呂春峰,朱建平,陶正蘇

(1.上海海洋大學大學工程學院,上海 201306;2 上海交通大學電子信息與電氣工程學院,上海 200240)

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

2016-12-08修改日期2017-07-04

一種基于IDV-Hop算法的改進定位機制*

呂春峰1,朱建平1,陶正蘇2*

(1.上海海洋大學大學工程學院,上海 201306;2 上海交通大學電子信息與電氣工程學院,上海 200240)

無線傳感器網(wǎng)絡中的節(jié)點定位或者事件定位越來越受到重視?；诰嚯x無關(guān)的定位機制DV-Hop,提出了一種改進定位算法IDV-Hop(Improved DV-Hop)。首先,對DV-Hop進行分析,提出了DV-Hop的局限性;根據(jù)這些局限性,結(jié)合密集節(jié)點的應用實際,提出了相應的改進措施;其次,基于改進的措施,提出了融合了HTC傳送機制及權(quán)重最小二乘法的IDV-Hop協(xié)議;而且,為了提高系統(tǒng)的定位性能,提出了兩個重要的參數(shù):校正系數(shù)kc和權(quán)重因子wNx,i;最后,基于跳距、節(jié)點密度、錨節(jié)點分布比例、傳輸半徑等參數(shù),對IDV-Hop協(xié)議的性能進行仿真分析;并將基于IDV-Hop算法的定位機制性能與其他的典型的DV-Hop機制比較,得出了對于大規(guī)模定位網(wǎng)絡,基于IDV-Hop算法的機制優(yōu)于其他機制的結(jié)論。

基于距離無關(guān)定位;IDV-Hop定位;權(quán)重最小二乘法;無線傳感器網(wǎng)絡

隨著傳感器技術(shù)、MEMS技術(shù)、嵌入式技術(shù)、現(xiàn)代網(wǎng)絡及通信技術(shù)的飛速發(fā)展,無線傳感器網(wǎng)絡(Wireless Sensor Networks,WSNs)得到了更為廣泛的應用。沒有具體的地理位置的監(jiān)測數(shù)據(jù)或者事件,對于觀測者或者觀測中心來說,都是沒有任何意義的,定位技術(shù)也是無線傳感器網(wǎng)絡的重要技術(shù),研究高效、節(jié)能、精準的定位機制是延長網(wǎng)絡壽命、提高定位精準度、保證定位實時性的保障。

無線傳感器網(wǎng)絡定位算法根據(jù)是否測量距離可以分成兩類:基于距離(Range-based)的算法和距離無關(guān)(Range-free)的定位算法[1-2]?；诰嚯x的定位主要是直接測量未知節(jié)點的確切距離或者角度,典型的Range-based定位方法主要包括:基于到達時間TOA(Time of Arrival)[3]、基于到達時間差TDOA(Time difference of Arrival)[4]、基于到達角度AOA(Angle of Arrival)[5]、基于接收信號強度指示RSSI(Received Signal Strength Indicator)[6]等?；诰嚯x的算法定位精度高,但它對硬件資源要求非常高,其各個節(jié)點之間要保持嚴格的時鐘同步,成本要求高,并不太適合無線傳感器網(wǎng)絡定位?；诰嚯x無關(guān)的定位無需額外的硬件設備,其算法主要包括:DV-Hop算法[7-9]、質(zhì)心算法(Centroid)、API(Approximate Pointin triangulation Test)、CPE(Convex Position Estimation)定位算法等。相比之下,在大規(guī)模無線傳感器網(wǎng)絡中,由于其低功耗、通信開銷小、無需硬件設施支撐以及成本低等優(yōu)勢,距離無關(guān)的定位算法具有更大的實用性。

本文將對基于距離無關(guān)的定位算法DV-Hop算法進行全面的分析,并從3各方面對DV-Hop機制進行了改進。首先,提出DV-Hop定位的局限性,針對這些局限性提出了相應的改進措施,提出了IDV-Hop算法的定位機制(簡稱IDV-Hop機制),并引入距離修正系數(shù)kc和權(quán)重因子wNx,i;其次,對IDV-Hop機制進行實驗驗證;最后,將IDV-Hop機制和其他基于DV-Hop算法的定位機制進行性能比較。

圖1 DV-Hop定位算法

1 IDV-Hop算法

1.1 DV-Hop算法

傳統(tǒng)的DV-Hop算法[10]分3步(如圖1)。

第1步 計算每個錨節(jié)點與未知節(jié)點的最小跳距。錨節(jié)點Ai廣播一個包含其位置信息和初始值為0的跳數(shù)域hopi的信息包。每個收到該包的鄰居節(jié)點(不論錨節(jié)點還是未知節(jié)點),都會更新這個域,如果原本存儲的跳數(shù)比收到的包里的跳數(shù)大,存儲該包里的跳數(shù),否則忽略該包。在廣播的過程中,未知節(jié)點獲取了與每個錨節(jié)點的最小跳距。

第2步 計算未知節(jié)點與每個錨節(jié)點之間的確切距離。每個錨節(jié)點都獲取了其他的錨節(jié)點與自己的最小跳距,可以計算每個錨節(jié)點的平均跳每距dphi,采用式(1):

(1)

知道了每個錨節(jié)點的平均每跳距,錨節(jié)點廣播該平均每跳距,未知節(jié)點計算其與每個錨節(jié)點的距離。未知節(jié)點存儲與其最近的錨節(jié)點的平均每跳距dphnear,乘以與每個錨節(jié)點之間的最小跳距,就是未知節(jié)點與每個錨節(jié)點之間的確切距離di=dphnear×hopi。

如圖1中,未知節(jié)點Nx距離4個錨節(jié)點的距離計算如下:(1)錨節(jié)點A1距離A2=40 m、2跳;距離A3=100 m、6跳;距離A4=40 m、3跳;(2)錨節(jié)點A1平均每跳距dph1為(40+100+40)/(2+6+3)=16.36 m。同理,其他的錨節(jié)點平均每跳距dph2,dph3,dph4分別為17.5 m、16.88 m、17.73 m。Nx保存A2的dph2并計算與其他錨節(jié)點的距離:17.5×3=52.5 m,17.5×2=35 m,17.5×3=52.5 m,17.5×2=35 m。

第3步 采用三邊測量法或最大似然估計計算未知節(jié)點的位置,具體計算公式見文獻[10-13]。

1.2IDV-Hop算法

從上面的敘述可以看出,DV-Hop算法存在若干問題:①步1中,節(jié)點只要收到一次廣播包,基本上hopi值就需要增加1,對于節(jié)點密度較大,傳輸距離較小的網(wǎng)絡,hopi值的估算會大大增加;②節(jié)點之間的跳距受到網(wǎng)絡連通度的影響,例如A1和A4之間只有40 m,但是跳距有3跳,如果網(wǎng)絡是全連通,它們之間只有1～2跳,這樣就增加了dphi誤差;③未知節(jié)點只需要存儲離它最近的錨節(jié)點的dphi,計算與所有錨節(jié)點的距離都采用這個dphi值,沒有考慮到其他節(jié)點的dphi獨立性,這顯然有較大誤差;④如果未知節(jié)點與2個或多個錨節(jié)點的跳距相同且都最短,未知節(jié)點不知道需要存儲哪一個錨節(jié)點的dphi,存儲不同的dphi值,計算的距離不同,會造成較大誤差。

針對DV-Hop機制的這些缺點,很多文獻都進行了改進。文獻[7]將傳統(tǒng)的DV-Hop定位算法用流程圖直觀展示出來,并提出了改進策略:①進入限跳機制,即設置一個跳數(shù)閾值;②引入RSSI測距技術(shù),在節(jié)點接收到其他節(jié)點位置信息之后,在進行節(jié)點間跳距估算之前,先對節(jié)點間的跳數(shù)值作一個判斷,如果跳數(shù)為1,直接采用RSSI測距技術(shù);③信標節(jié)點不僅僅要還要估算出實際距離與估算距離間的誤差,再用該誤差作為修正值修正信標節(jié)點的平均每跳距,將修正后的平均每跳距作為校正值向外廣播。文獻[8]也對DV-Hop算法進行了改進:①平均跳距的估計:將離未知節(jié)點最近錨節(jié)點的每跳距計算出來的跳距d1和該最近錨節(jié)點與其他錨節(jié)點間的距離與跳數(shù)之商d2的平均數(shù),考慮了其他的錨節(jié)點對該未知節(jié)點的影響;②位置修正:通過對原來估計距離進行修正,獲取更準確的位置信息。文獻[9]從兩個方面對DV-Hop機制進行改進:①引入平均每跳距離均方加權(quán)誤差的思想對信標節(jié)點平均每跳距進行優(yōu)化;②采用改進的粒子群算法優(yōu)化位置信息。

文獻[7-9]中對DV-Hop的改進主要從跳數(shù)、每跳距等方面進行改進。本文不僅僅從跳數(shù)限制、每跳距離、未知節(jié)點與錨節(jié)點的距離等方面進行改進,而且從傳輸層獲得支撐。本文對DV-Hop機制改進的措施:

①采用基于CSMA/CA傳輸機制的HTC機制[11],所有的傳輸、定位等都只限于2跳,這樣在節(jié)點密度較高的情況下,減少傳輸沖突,降低hopi值估算的誤差;②未知節(jié)點與每個錨節(jié)點的距離采用各自dphi分別乘以跳距,避免了所有的距離都是用一個dphnear值和相同跳距的錨節(jié)點dphi選擇問題,并引入校正因子kc;③計算未知節(jié)點的坐標采用權(quán)重最小二乘法,定義了權(quán)重因子wNx,i,該因子全面考慮未知節(jié)點與錨節(jié)點的跳距、錨節(jié)點之間的跳距、傳輸距離等,更加準確可靠。

IDV-Hop算法如下:

步驟1 請求定位階段。時間分成若干的時隙,定位時間由多個時隙組成。hopi初始化為0。在系統(tǒng)初始化結(jié)束,每個節(jié)點建立自己的一跳鄰居列表,并在每個定位時隙初始階段節(jié)點更新該鄰居列表(HTC算法[11])。建立了這個鄰居列表,未知節(jié)點Nx會確定他的一跳距離內(nèi)的一跳錨節(jié)點鄰居A1i,然后,Nx發(fā)送定位請求包給A1i。如果A1i數(shù)量等于或者大于3,節(jié)點直接執(zhí)行DV-Hop機制進行定位;如果A1i數(shù)量小于3,那么這個請求定位的包還需要通過中繼傳送到他的二跳錨節(jié)點鄰居A2i,并且二跳鄰居節(jié)點會加到這個請求定位列表中,如果A1i和A2i的數(shù)量和等于或者大于3,可以進行DV-Hop定位,否則,定位失敗。

步驟2 跳數(shù)信息交換階段。定位請求階段結(jié)束后,錨節(jié)點A1i廣播一個HIE包(跳數(shù)信息交換,Hop Information Exchange)。該包包含A1i的位置信息、A1i的ID信息和hopi信息。計算hopi有3種情況:第1種,Nx的一跳與A1i的一跳的重疊鄰居(錨節(jié)點)數(shù)量等于或者大于3個,hopi=1,且式(1)分母部分∑hopij(i≠j)值為所有A1i數(shù)量減1;第2種,如果這個重疊部分錨節(jié)點數(shù)量小于3,但是在Nx的1跳之內(nèi)、A1i的1跳之外2跳之內(nèi)錨節(jié)點數(shù)加上重疊部分錨節(jié)點數(shù)量等于或大于3,在那么式(1)的分母可以設置成(NA1i+2NA2i-1);第3種,Nx的1跳之內(nèi)的錨節(jié)點數(shù)量小于3,那么需要擴充到他的2跳,這時∑hopij(i≠j)的計算跟第2種情況相同。

(2)

步驟3 距離計算階段。采用式(1)計算每個錨節(jié)點的平均跳距。那么未知節(jié)點收到錨節(jié)點發(fā)送來的平均跳距,計算其到每個錨節(jié)點的距離。與DV-Hop算法只保存最近錨節(jié)點的dphnear不同,IDV-Hop算法是每個錨節(jié)點的每跳距乘以與未知節(jié)點的跳數(shù),才是相應的距離。

(3)

步驟4 未知節(jié)點坐標計算。在本階段的計算中,引入了2個參數(shù):校正因子kc和權(quán)重因子wNx,i。kc采用的是已知錨節(jié)點之間的誤差推廣到錨節(jié)點與未知節(jié)點之間。

(4)

(5)

(6)

(7)

將式(7)兩端平方并且簡化,有式(8):

(8)

假設:

對于準備要參加的會議，會前若有征文，要精心撰寫論文，不僅為爭取大會發(fā)言創(chuàng)造條件，也為申請獲得經(jīng)費資助增加法碼。另外，對于在大會上做報告的專家的學術(shù)情況要有所了解，以便在會上更好地與專家進行交流互動。

那么,有式(9):

QZ=H

(9)

因為IDV-Hop里的距離是采用每個錨節(jié)點與未知節(jié)點之間的距離,那么為了準確計算未知節(jié)點的坐標,采用權(quán)重最小二乘法WLS(WeightedLeastSquare)計算,如式(10):

Z=(Q′W′WQ)-1Q′W′WH

(10)

式中:W是權(quán)重矩陣,代表錨節(jié)點的跳距、錨節(jié)點與未知節(jié)點間的跳距、傳送距離、錨節(jié)點的個數(shù)等因素對計算距離的影響。在ADV-Hop算法中[12],權(quán)重因子只考慮了錨節(jié)點與未知節(jié)點之間的跳距。

(11)

在計算權(quán)重因子時,錨節(jié)點的個數(shù)可以采用式(2)計算。

(12)

2 實驗驗證

2.1 性能驗證

我們通過NS-2仿真軟件來驗證IDV-Hop機制的性能。搭建仿真平臺:所有節(jié)點包含錨節(jié)點都分布在同一個邊長1 km的正方形區(qū)域內(nèi);假設所有在傳輸距離內(nèi)的傳輸,節(jié)點都能偵聽到其他節(jié)點的傳送;沒有信號衰減。設定CSMA/CA機制參數(shù)為:重傳次數(shù)為2,最大退避次數(shù)為4,數(shù)據(jù)包長為5個時隙單位。從前面分析可以看出,IDV-Hop的定位誤差主要取決于跳距、節(jié)點密度、錨節(jié)點分布比例、傳輸半徑等,我們從這幾個參數(shù)來驗證IDV-Hop的性能。

從圖2可以看出,節(jié)點的密度越大,其定位誤差越小;錨節(jié)點的比例越高,定位誤差越小。從式(1)不難看出,dphi計算的準確度與∑hopij有較大關(guān)系,而IDV-Hop中的∑hopij計算涉及的跳數(shù)較少,而且不存在連通度的影響,所以較為準確;而且,錨節(jié)點數(shù)量增加,在Nx一跳內(nèi)就可以直接執(zhí)行IDV-Hop算法,這大大減小了誤差。

圖2 定位誤差(節(jié)點密度影響)

圖3 定位誤差(傳輸距離影響)

定位誤差也跟傳輸距離有較大關(guān)系。IDV-Hop機制的節(jié)點(包含錨節(jié)點)都是只考慮了2跳的傳輸,那么傳輸距離決定了錨節(jié)點的數(shù)量,這樣也決定了dphi計算的準確性。而且,權(quán)重因子wN,i也考慮了傳輸距離。從圖3看出,節(jié)點的傳輸距離并不是越大越好,而是有個權(quán)衡問題。

IDV-Hop定位機制針對的是實時定位,那么,實時性也是考慮的重點之一。從圖4和圖5看出,隨著節(jié)點數(shù)量、錨節(jié)點比例的增加,實時性提高,原因跟前面定位誤差的分析相似。

圖4 定位時延(節(jié)點密度影響)

圖5 定位時延(傳輸距離影響)

圖6 定位誤差比較

2.2 性能比較

在眾多基于DV-Hop機制的定位算法中,ADV-Hop機制[12]、HDV-Hop機制[13]、Selective-3-anchor機制[14],是應用較廣、算法相對簡單的定位機制,本文將IDV-Hop機制與這幾個機制進行比較,發(fā)現(xiàn),IDV-Hop機制在實時性上表現(xiàn)較為優(yōu)越,而在節(jié)點密度較大時定位誤差也表現(xiàn)出了較好的優(yōu)勢。

圖7 定位時延比較

3 結(jié)束語

本文首先對傳統(tǒng)的距離無關(guān)定位機制DV-Hop進行了分析,指出其誤差的主要來源,提出了一種基于DV-Hop的距離無關(guān)的定位改進機制IDV-Hop機制。首先,基于對DV-Hop機制的限制分析,提出了改進的措施;接著,基于改進措施,提出IDV-Hop機制;最后,基于跳距、節(jié)點密度、錨節(jié)點分布比例、傳輸半徑等參數(shù),進行仿真分析定位誤差、定位實時性等性能;并將IDV-Hop機制與相關(guān)DV-Hop機制進行了性能比較。下一步的工作是在節(jié)點移動(包括未知節(jié)點和錨節(jié)點)的情況下,DV-Hop機制或者其他的相應機制的性能提高。

[1] Cheon J,Hwang H,Kim D S,et al. IEEE 802.15.4 ZigBee-Based Time-of-Arrival Estimation for Wireless Sensor Networks[J]. Sensors,2016,203(16):203-213.

[2] Boukerche A,Oliveira H A B,Nakamura E F,et al. Localization Systems for Wireless Sensor Networks[J]. IEEE Wireless Communications,2007,14(6):6-12.

[3] Spano D,Ricciato F. Opportunistic Time-of-Arrival Localization In Fully Asynchronous Wireless Networks[J]. Pervasive and Mobile Computing,2016,in press:1-15.

[4] 張會新,陳德沅,彭晴晴,等. 一種改進的TDOA無線傳感器網(wǎng)絡節(jié)點定位算法[J]. 傳感技術(shù)學報,2015,28(3):412-415.

[5] 蔣鵬,覃添,陳歲生. 基于AOA降維和同心圓定位的三維傳感器網(wǎng)絡節(jié)點自定位方法[J]. 傳感技術(shù)學報,2012,25(7):999-1006.

[6] 陳淑敏,喬曉田,毛佳,等. 基于接收信號強度(RSSI)的室內(nèi)二次定位方法[J]. 傳感技術(shù)學報,2015,28(4):572-5777.

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

[8] 劉少飛,趙清華,王華奎. 基于平均跳距估計和位置修正的DV-Hop定位算法[J]. 傳感技術(shù)學報,2009,22(8):1154-1157.

[9] 范時平,羅丹,劉艷林. 基于跳距與改進粒子群算法的DV-Hop定位算法[J]. 傳感技術(shù)學報,2016,29(9):1410-1415.

[10] Nicuescu D,Nath B. DV Based Positioning in Ad Hoc Networks[J]. Telecommunication Systems,2003,22:267-280.

[11] Zhu J P,Tao Z S,Lü C F. Performance Analyses and Improvements for IEEE 802.15.4 CSMACA Scheme in Wireless Multi-Hop Sensor Networks Based on HTC Algorithm[J]. International Journal of Distributed Sensor Networks,2013(10):1-22.

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

[13] Safa H. A Noval Localization Algorithm for Large Scale Wireless Sensor Networks[J]. Computer Communications,2014,45:32-46.

[14] Gui L Q,Val T,Wei A,et al. Improvement of Range-Free Localization Technology by a Novel DV-Hop Protocol in Wireless Sensor Networks[J]. Ad Hoc Networks,2015,24:55-73.

AnImprovedLocalizationSchemeBasedonIDV-HopforLarge-ScaleWirelessSensorNetworks*

LüChunfeng1,ZHUJianping1,TAOZhengsu2*

(1.SOU College of Engineering Science and Technology Shanghai Ocean University,Shanghai 201306,China; 2.Department of Electronic Information and Electrical Engineering Shanghai Jiaotong University,Shanghai 200240,China)

It is extremely urgent to establish and maintain low cost and high efficient localization schemes for real-time large-scale surveillance systems. An improved DV-Hop based localization scheme IDV-Hop embedded in WLS(weighted least square)method,accompanying with HTC scheme,is proposed for the purpose of surrounding surveillance,object localization for early warning,rescue operations and restructuring plan et al. Two critical parameters,correction coefficient kcand weighted coefficient wNx,i,are introduced into IDV-Hop scheme to improve location performance. And then,NS-2 simulations demonstrate that analysis results match well with simulation results. Besides,behaviors of IDV-Hop is improved largely relative to other DV-Hop based schemesfor large-scale sensor networks.

range-free localization;IDV-Hop scheme;weighted least square;wireless sensor networks

TP393

A

1004-1699(2017)10-1542-06

10.3969/j.issn.1004-1699.2017.10.015

呂春峰(1978-),男,2000年于昆明理工大學獲得學士學位,2006年于昆明理工大學獲得碩士學位,2014年于上海交通大學獲得博士學位,現(xiàn)為上海海洋大學講師,主要研究方向無線傳感器技術(shù)、現(xiàn)代檢測技術(shù),cflv@shou.edu.cn;

朱建平(1978-),女,2000年于昆明理工大學獲得學士學位,2005年于昆明理工大學獲得碩士學位,2012年于上海交通大學獲得博士學位,現(xiàn)為上海海洋大學副教授,主要研究方向無線傳感器網(wǎng)絡技術(shù)、在線檢測技術(shù),jp-zhu@shou.edu.cn;

陶正蘇(1961-),男,2005年于香港科技大學獲得博士學位,現(xiàn)為上海交通大學教授,主要研究方向無線傳感器技術(shù)、在線測量理論及技術(shù)、光電檢測新技術(shù)和儀器,zstao@sjtu.edu.cn。