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

呂春峰,朱建平,陶正蘇

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

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

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

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

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

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

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

基于距離無關定位;IDV-Hop定位;權重最小二乘法;無線傳感器網絡

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

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

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

圖1 DV-Hop定位算法

1 IDV-Hop算法

1.1 DV-Hop算法

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

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

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

(1)

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

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

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

1.2IDV-Hop算法

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

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

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

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

IDV-Hop算法如下:

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

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

(2)

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

(3)

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

(4)

(5)

(6)

(7)

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

(8)

假設:

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

那么,有式(9):

QZ=H

(9)

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

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

(10)

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

(11)

在計算權重因子時,錨節點的個數可以采用式(2)計算。

(12)

2 實驗驗證

2.1 性能驗證

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

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

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

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

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

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

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

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

圖6 定位誤差比較

2.2 性能比較

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

圖7 定位時延比較

3 結束語

本文首先對傳統的距離無關定位機制DV-Hop進行了分析,指出其誤差的主要來源,提出了一種基于DV-Hop的距離無關的定位改進機制IDV-Hop機制。首先,基于對DV-Hop機制的限制分析,提出了改進的措施;接著,基于改進措施,提出IDV-Hop機制;最后,基于跳距、節點密度、錨節點分布比例、傳輸半徑等參數,進行仿真分析定位誤差、定位實時性等性能;并將IDV-Hop機制與相關DV-Hop機制進行了性能比較。下一步的工作是在節點移動(包括未知節點和錨節點)的情況下,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無線傳感器網絡節點定位算法[J]. 傳感技術學報,2015,28(3):412-415.

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

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

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

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

[9] 范時平,羅丹,劉艷林. 基于跳距與改進粒子群算法的DV-Hop定位算法[J]. 傳感技術學報,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年于上海交通大學獲得博士學位,現為上海海洋大學講師,主要研究方向無線傳感器技術、現代檢測技術,cflv@shou.edu.cn;

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

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