劉士興,黃俊杰,劉宏銀,易茂祥

(合肥工業(yè)大學電子科學與應用物理學院,合肥 230009)

?

基于多通信半徑的加權DV-Hop定位算法*

劉士興*,黃俊杰,劉宏銀,易茂祥

(合肥工業(yè)大學電子科學與應用物理學院,合肥 230009)

DV-Hop定位算法是無線傳感器網(wǎng)絡中一種常用的基于非測距的定位技術,該算法使用平均跳距表示實際距離,在實際應用中造成很大的誤差和節(jié)點能耗。為此,分析了加權DV-HOP定位算法,并在加權算法基礎上,引入多通信半徑廣播方法細化節(jié)點間的跳數(shù),最后提出了一種基于加權DV-HOP的改進型RWDV-Hop定位算法。仿真結(jié)果證明,加權DV-HOP在定位精度上比DV-HOP算法提高了7.3%,改進型RWDV-HOP在定位精度上比加權DV-HOP算法提高了6.7%。

無線傳感器網(wǎng)絡;DV-Hop定位算法;信標節(jié)點;加權算法

近年來,隨著低功耗嵌入式技術,微機電系統(tǒng)MEMS(Micro-Electro-Mechanism),無線通信技術SOC(System on Chip)和無線通信(Wirless Communication)的飛速發(fā)展,無線傳感網(wǎng)絡技術應運而生[1]。無線傳感器網(wǎng)絡WSN(Wireless Sensor Network)是一種自組織的網(wǎng)絡,具有低功耗,低成本,體積小以及分布式等特點。無線傳感器網(wǎng)絡是信息感知的一場技術革命,是21世紀重要的技術之一。因此,無線傳感器網(wǎng)絡成為了國內(nèi)外學術界的研究熱點。

在無線傳感器網(wǎng)絡中,傳感器節(jié)點的位置信息是至關重要的,沒有位置信息的監(jiān)測,采集到數(shù)據(jù)也就沒有了實際意義。因此,在無線傳感器網(wǎng)絡中,確定事件發(fā)生的位置是至關重要的。只有傳感器節(jié)點的位置信息是確定的,才能獲得事件發(fā)生的具體位置,從而采取何種方式或者決策?；谝陨系姆治?傳感器網(wǎng)絡節(jié)點定位技術是當今國內(nèi)外學者研究的熱點和重點。

根據(jù)定位機制,將現(xiàn)有的定位算法分為兩種,即基于測距的定位算法(range-based)和與距離無關(range-free)的定位算法[2]。前者需要額外增加硬件來測量相鄰節(jié)點間的絕對距離或者方位,并利用節(jié)點間的實際距離來計算未知節(jié)點的位置;后者無需額外的硬件測量節(jié)點間的絕對距離或方位,而是利用節(jié)點間的估計距離計算未知節(jié)點的位置。常用的與距離相關的定位技術有RSSI、TOA、TDOA和AOA。這類算法定位精度相對較高,但是成本與能耗開銷也較大。與距離無關的定位算法利用網(wǎng)絡的連通性進行定位,常用的有質(zhì)心算法、DV-Hop[3]、Amorphous[4]、APIT[5]等,這類算法成本和功耗較低,應用更加廣泛。

DV-Hop算法是目前應用最廣泛的定位算法之一,針對DV-Hop算法改進研究,本文提出了提高節(jié)點定位精度的加權DV-Hop算法和降低功耗的基于節(jié)點密度的定位算法。

1 DV-HOP算法

DV-Hop定位算法是由Niculescud等人提出的一種基于距離矢量計算跳數(shù)的算法。其基本思想是將未知節(jié)點到信標節(jié)點之間的距離用平均跳距和兩者之間跳數(shù)的乘積表示,具體步驟如下[6]:

①信標節(jié)點信息泛洪廣播和所有節(jié)點獲取距離信標節(jié)點的最小跳數(shù)。信標節(jié)點采用泛洪廣播方式將其位置信息采用分組形式傳遞給其鄰居節(jié)點,廣播的信息包格式為:{Idi,xi,yi,Hopsi},其中包含了該節(jié)點的標識Idi、位置坐標(xi,yi)以及跳數(shù)信息Hopsi,初始Hopsi的值為0。接收到此數(shù)據(jù)的每個節(jié)點將此信息記錄下來,然后繼續(xù)向其鄰居節(jié)點廣播,每廣播一次就將Hopsi加1,并將分組信息以{Idi,xi,yi,Hopsi}的格式存儲到自己的數(shù)據(jù)表中。當節(jié)點接收到有相同Id的數(shù)據(jù)包時,對兩個數(shù)據(jù)包中的Hopsi進行比較,如果新的跳數(shù)小于原表中保存的跳數(shù),則用新的跳數(shù)替換節(jié)點中的信息,這就意味著找到了一條更短的到達該信標節(jié)點的路徑。如果新的跳數(shù)大于節(jié)點中的跳數(shù),則丟棄該數(shù)據(jù)包,也不再進行轉(zhuǎn)發(fā)。

②計算未知節(jié)點與信標節(jié)點的估計距離。經(jīng)過第1步后,每個信標節(jié)點獲得了其他信標節(jié)點的位置和最小跳數(shù)。這時通過式(1)計算網(wǎng)絡中平均每跳的距離。

(1)

式中:(xi,yi),(xj,yj)為信標節(jié)點i,j的坐標,hi為信標節(jié)點i與j(i≠j)之間的跳段數(shù),HopSize為求出的平均跳距。

③信標節(jié)點將平均跳距廣播到網(wǎng)絡,通過式(2)計算未知節(jié)點到信標節(jié)點的估計距離du,i。

du,i=HopSize·hu,i

(2)

當未知節(jié)點得到3個或者更多節(jié)點之間的距離后,再通過三邊測量法[7]或者極大似然估計等數(shù)學方法計算未知節(jié)點的坐標。

2 加權DV-Hop算法

在實際使用中,DV-Hop算法的定位精度受到節(jié)點密度及其分布情況影響。網(wǎng)絡中信標節(jié)點的密度越大,分布越合理,則定位精度越高,反之則定位誤差大。

2.1DV-Hop算法誤差分析

在實際使用中,部署信標節(jié)點的成本較高,因而信號節(jié)點的總數(shù)不會很多。另外,節(jié)點通常是隨機放置在探測環(huán)境中,難以保證信標節(jié)點分布的合理性[8-9]。綜上,實際使用中,DV-Hop定位算法會有很大的定位誤差。

DV-Hop定位算法使用跳段數(shù)與平均每跳距離的乘積來得到未知節(jié)點與信標節(jié)點的估計距離。這種估算方法有時候會有很大誤差,例如圖1對應的網(wǎng)絡拓撲結(jié)構:

圖1 DV-Hop誤差分析

圖1中,A1、A2和A3為信標節(jié)點,U1、U2、U3、U4、U5和A為未知節(jié)點。對于未知節(jié)點A,由于A2離它最近,所以A應該從A2獲取HopSize值。由式(1)得HopSize=(40+25)/(2+5)=10.7,那么3個信標節(jié)點與A之間的距離分別為A1:10.7×3,

A2:10.7×2,A3:10.7×3。但是A與3個信標節(jié)點的真實距離分別為:50、40和50 m,這使得定位誤差非常大。在該網(wǎng)絡中,A2與A3真實距離很小,只是略大于通信半徑,用A2與A3來估算每跳距離,所得的誤差就非常大。

2.2 加權DV-Hop算法

針對上文中提到的關于DV-Hop定位算法中使用相同的平均跳距來計算未知節(jié)點到信標節(jié)點間距離的定位誤差問題,有些學者提出了加權DV-Hop定位算法[10-11]。該算法的基本思想是在DV-Hop定位算法中,通過加權系數(shù)的大小體現(xiàn)不同信標節(jié)點對未知節(jié)點位置坐標運算中的影響力大小,然后通過加權平均跳距估算未知節(jié)點的位置。實際使用中,不同信標節(jié)點的加權系數(shù)Wi通過式(3)確定:

(3)

式中:ni表示信標節(jié)點i與未知節(jié)點之間的跳數(shù),

根據(jù)式(4),得未知節(jié)點的加權平均跳距為:

(4)

使用加權后的平均跳距,代入DV-Hop定位算法的第3步,計算出未知節(jié)點到信標節(jié)點之間的距離,再通過三邊測量法或者極大似然估計等數(shù)學方法計算出未知節(jié)點的坐標。

3 改進加權DV-Hop算法

3.1 加權DV-Hop算法誤差分析

在DV-Hop和加權算法中,計算跳數(shù)的時候,只要節(jié)點在信標節(jié)點通信半徑R以內(nèi),無論遠近跳數(shù)都為1跳,則該算法計算出的平均跳距誤差將會很大。如圖2所示,未知節(jié)點U1到未知節(jié)點U2的距離比節(jié)點U2到信標節(jié)點A的距離小的多,而在加權DV-Hop算法中,將U1到U2和U2到A的跳數(shù)都記為1跳,因此在這種情況下計算平均跳距將產(chǎn)生很大的誤差[12]。

圖2 節(jié)點分布拓撲結(jié)構

3.2 基本思想

根據(jù)前文分析,通信半徑和信鄰節(jié)點是加權DV-Hop定位算法中的重要兩個因素。因此,如果能夠得到信標節(jié)點與其鄰居節(jié)點之間更準確的距離,無疑能夠提高所有未知節(jié)點的定位精度。本文參考文獻[13],對每個信標節(jié)點引入多通信半徑廣播數(shù)據(jù),細化信標節(jié)點與鄰居節(jié)點之間的跳數(shù)。

鑒于通信半徑R是對所有節(jié)點而言是相對固定的,因此信標節(jié)點以通信半徑R廣播數(shù)據(jù)時,鄰居節(jié)點的跳數(shù)記為1,然后節(jié)點以不同的通信半徑廣播數(shù)據(jù),不同的通信半徑代表不同的跳數(shù),這樣可以細化信標節(jié)點與鄰居節(jié)點之間的跳數(shù)。

設信標節(jié)點的通信半徑為R,信標節(jié)點與其鄰居節(jié)點之間的實際距離為d,跳數(shù)為h,若節(jié)點以通信半徑R/n廣播數(shù)據(jù),i為小于n的整數(shù),則通過不同的通信半徑廣播數(shù)據(jù)之后,跳數(shù)h為:

(5)

該算法使加權DV-Hop定位算法的跳數(shù)值不再是整數(shù),而是小數(shù),這有效提高了跳數(shù)值的準確性,從而降低了定位誤差。

3.3 改進算法的具體步驟

(1)計算信標節(jié)點與鄰居節(jié)點之間的跳數(shù)

網(wǎng)絡啟動時,信標節(jié)點首先以通信半徑R/n向網(wǎng)絡廣播數(shù)據(jù),同時把接收節(jié)點與發(fā)送節(jié)點之間的跳數(shù)記為1/n跳。數(shù)據(jù)包格式同DV-Hop定位算法。經(jīng)過時間T之后,信標節(jié)點再以通信半徑2R/n向網(wǎng)絡廣播數(shù)據(jù),接收到信標節(jié)點信號的節(jié)點首先查詢是否記錄過該信標節(jié)點的跳數(shù)信息,如果沒有,將該未知節(jié)點與錨節(jié)點之間跳數(shù)記為2/n,如果有,則不改變跳數(shù)信息,并將信息轉(zhuǎn)發(fā)。以此類推,最后信標節(jié)點以通信半徑R廣播數(shù)據(jù),收到信標節(jié)點信號的節(jié)點首先查詢是否記錄過該信標節(jié)點的跳數(shù)信息,如果沒有,將該未知節(jié)點與錨節(jié)點之間跳數(shù)記為1,如果有,則不改變跳數(shù)信息。這樣通過不斷的轉(zhuǎn)發(fā),所有節(jié)點都能得到與錨節(jié)點之間的最小跳數(shù)。

(2)計算各錨節(jié)點之間的平均跳距

參考加權DV-Hop定位算法,利用步驟(1)得到的跳數(shù)信息,通過平均跳距公式和加權系數(shù),計算出各錨節(jié)點之間的加權平均跳距。

4 算法仿真驗證

采用MATLAB軟件對上述算法進行仿真,并對仿真數(shù)據(jù)進行分析[14]。仿真環(huán)境為100m×100m的正方形區(qū)域,區(qū)域中隨機分布100個節(jié)點。在相同的信標節(jié)點數(shù)條件下,進行100次重復實驗取平均值的方法,對定位誤差進行評估。假設未知節(jié)點的估算位置為(xc,yc),節(jié)點的實際位置為(xi,yi),則未知節(jié)點的定位誤差為[15-16]:

(6)

式中:R為節(jié)點的通信半徑,N為未知節(jié)點的個數(shù)。

圖3為通信半徑R為20m時,信標節(jié)點以R/2、R/3、R/4 3種不同通信半徑廣播數(shù)據(jù)時,節(jié)點定位的誤差仿真圖。

從圖3可以得出,信標節(jié)點以四通信半徑廣播數(shù)據(jù)時,節(jié)點的定位誤差最小,三通信半徑次之,兩通信半徑的定位誤差最大。例如,當信標節(jié)點個數(shù)為16時,n值取4及四通信半徑時,節(jié)點的定位誤差為32.1%,而在節(jié)點以三通信半徑和兩通信半徑廣播數(shù)據(jù)時,節(jié)點的定位誤差分別為34%和38.1%。由此,可以得到,n值越大,節(jié)點通信半徑越小,跳數(shù)劃分的越細,節(jié)點的定位誤差越小。

圖3 不同通信半徑時的定位誤差(R=20 m)

圖4和圖5分別是節(jié)點通信半徑為20m和25m時,本文提出的多通信半徑定位算法(RWDV-Hop算法)、加權DV-Hop算法和DV-Hop算法在錨節(jié)點數(shù)目變化時的定位誤差仿真圖。

圖4 節(jié)點個數(shù)與定位誤差的關系(R=20 m)

圖5 節(jié)點個數(shù)與定位誤差的關系(R=25 m)

從圖中可以看出,在相同的通信半徑和錨節(jié)點比例下,RWDV-Hop定位算法定位精度最高,加權DV-Hop定位算法次之,DV-Hop定位算法定位誤差最大。

例如:從圖5可以看出,當節(jié)點通信半徑為25 m,錨節(jié)點數(shù)目為14時,DV-Hop定位算法的定位誤差為48.2%,加權DV-Hop定位算法的定位誤差為42.1%,而RWDV-Hop定位算法的定位誤差為38.2%。

從圖4可以看出,當節(jié)點通信半徑為20m,錨節(jié)點數(shù)目為14時,DV-Hop定位算法的定位誤差為46.8%,加權DV-Hop定位算法的定位誤差為43.1%,而RWDV-Hop定位算法的定位誤差為39.3%。當錨節(jié)點數(shù)目為16時,加權DV-Hop定位算法比DV-Hop定位算法的定位誤差小了4.4%,而RWDV-Hop定位算法的定位誤差比加權DV-Hop定位算法的定位誤差小了3.5%。

由此說明本文提出的基于多通信半徑的定位算法,在相同的環(huán)境以及相同的錨節(jié)點數(shù)目條件下,該算法相對于加權DV-Hop算法和DV-Hop定位算法,在對未知節(jié)點的位置計算上更加準確即該算法的定位精度最高。

圖4和圖5比較發(fā)現(xiàn),當節(jié)點通信半徑增大,定位誤差降低。這是因為,通信半徑影響節(jié)點的連通度,會對節(jié)點間的跳數(shù)及節(jié)點的平均跳距計算產(chǎn)生影響。

6 結(jié)論

本文介紹了現(xiàn)有的DV-Hop定位算法,分析了該算法存在定位精度低缺陷。加權DV-Hop定位算法通過加權系數(shù),修正了平均跳距,有效的降低了定位誤差。本文提出的RWDV-Hop算法,使用多個通信半徑廣播自身的分組信息,從而獲得未知節(jié)點與信標節(jié)點之間更精確的跳數(shù),從而計算更加精確的加權平均跳距。利用MATLAB軟件進行仿真,仿真結(jié)果表明本文提出的RWDV-Hop算法比DV-Hop定位算法和加權DV-Hop定位算法在定位精度上有明顯的提高。

本文討論的算法都是在理想狀態(tài)下進行的仿真,但現(xiàn)實環(huán)境中往往會因為溫度、濕度以及大氣壓強等因素對節(jié)點定位造成影響。如何在考慮這些影響因素的前提下來提高節(jié)點的定位精度還有待進一步的研究。

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

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

[3] Lin Jinchao,Chen Xiaobing,Liu Haibo. Iterative Algorithm for Locating Nodes in WSN Based on Modifying Average Hopping Distances[J]. Journal on Communications,2009,10(30):107-133.

[4] Nagpal R. Organizing a Global Coordinate System from Local Information on an Amorphous Computer[D]. AI Memo 1666,MIT AI Laboratory,August 1999:257-262.

[5] He Tian,Huang Chengdu,Blum B M,et al. Range-Free Localization Schemes in Large Scale Sensor Networks[C]//Proceedings of the 9th Annual International Conference on Mobile Computing and Networking,MOBICOM’2003. San Diego(CA,USA),2003. New York(NY,USA):ACM Press,2003:81-95.

[6] 李曉維,徐勇軍,任豐原. 無線傳感器網(wǎng)絡技術[M]. 北京:北京理工大學出版社,2007:247-259.

[7] Cao Yu,Chen Xiupeng,Yu Yang,et al. Range-Free Distance Estimate Methods Using Neighbor Information In Wireless Sensor Networks[C]//Proc IEEE 70th Vehicular Technology conference Fall(VTC 2009-Fall),2009,9:1-5.

[8] Tian Shuang,Zhang Xinming,Wang Xinguo,et al. A Selective Anchor Node Localization Algorithm for Wireless Sensor Networks[J]. International Conference on Convergence Information Technology(ICCIT),2007(11):164-168.

[9] Liu Shaoqiang,Pang Xinmiao,Fan Xiaoping. Improved DV-Hop Algorithm for Higher Positioning Accuracy[J]. Chinese Journal of Sensors and Actuators,2010,8(23):1179-1183.

[10] 馮江,朱強,吳春春. 改進的DV-Hop定位算法研究[J]. 計算機工程,2012,38(19):74-77

[11] Chen Hongyang,Sezaki,K,Ping Deng,et al. An Improved DV-HOP Localization Algorithm for Wireless Sensor Networks[C]//Industrial Electronics and Applications. ICIEA 2008. 3rd IEEE Conference,2008,6:1557-1561.

[12] Erchin Serpe din,Qasim M Chaudhari. Synchronization in Wireless Sensor Networks[J]. Science Press,2011:124-128.

[13] Li Juan,Liu Yu,Qian Zhihong,Improved DV-Hop Localization Algorithm Based on Two Communication Ranges for Wireless Sensor Network[J]. Journal of Jilin University,2014,3(44):25-29.

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

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

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

劉士興(1969-),男,畢業(yè)于中國科學技術大學,現(xiàn)任合肥工業(yè)大學副教授。主要研究方向為無線傳感網(wǎng)絡,多參數(shù)火災探測;

黃俊杰(1991-),男,安徽明光人,合肥工業(yè)大學碩士在讀,主要研究方向物聯(lián)網(wǎng)、無線傳感器網(wǎng)絡、火災探測等,askao_know@163.com;

劉宏銀(1988-),男,安徽天長人,合肥工業(yè)大學碩士在讀,主要研究方向物聯(lián)網(wǎng)、無線傳感器網(wǎng)絡、火災探測等,liuhongyin115@163.com。

An Improving DV-Hop Algorithm Based onMulti Communication Radius*

LIUShixing*,HUANGJunjie,LIUHongyin,YiMaoxiang

(School of Electronic Science and Applied Physics,Hefei University of Technology,Hefei 230009,China)

DV-Hop is one of the most common used localization algorithms in range-free algorithms. This algorithm uses hop distance instead of the actual distance,which results in localization error and large energy consumption. The weighted DV-Hop algorithm is analyzed,and an improved algorithm based on the weighted DV-Hop is proposed. The improved algorithm broadcasts the data using multi communication radius and refines the hops to reduce the location error. The average hop distance depended on the neighbor nodes and the communication radius is corrected in this new algorithm. The simulation shows that the improvement of the improved algorithm on the positioning precision is 6.7%.

wireless sensor networks;anchor node;weighted algorithm;DV-Hop

項目來源:國家自然科學面上基金項目(61371025);安徽高校省級自然科學研究重點項目(KJ2012Z316)

2015-01-06 修改日期:2015-02-16

C:7230

10.3969/j.issn.1004-1699.2015.06.018

TN929.52

A

1004-1699(2015)06-0883-05