一種基于DV-Hop的無線傳感器網絡節點定位算法

王景琿

(國家數字交換系統工程技術研究中心,鄭州450001)

一種基于DV-Hop的無線傳感器網絡節點定位算法

王景琿

(國家數字交換系統工程技術研究中心,鄭州450001)

針對無線傳感器網絡節點的自身定位問題,提出一種基于分布式協作的DV-Hop改進算法。在距離計算的基礎上,采用最大似然估計方法選取共線度較低的參考點作為錨節點。綜合考慮所有錨節點,以可信度為準則,通過加權平均計算每一個未知節點的平均跳距。計算未知節點的定位誤差,將誤差低于預設閾值的未知節點轉化為錨節點,擴大定位范圍。仿真結果表明,在初始錨節點數和通信半徑相同的情況下,該算法的定位誤差比DVHop算法減少約20%,尤其當節點密度較小時,其定位誤差可穩定在40%以下。當節點通信半徑超過10 m時,該算法的剩余節點比例可降低約30%。

無線傳感器網絡;DV-Hop算法;錨節點;共線度;協作定位

1 概述

無線傳感器網絡的節點定位技術是網絡應用的關鍵支撐技術之一。對于無線傳感器網絡應用來說,節點的位置信息非常重要。傳感器節點的位置可以標示監測數據源的位置,為網絡管理提供拓撲結構,并可生成用于數據傳輸的路由協議。傳感器節點的位置可以通過配置GPS定位裝置或人工定位布置獲得,但由于傳感器網絡的節點數量較大,GPS定位裝置的費用較高,因此目前常用的做法是,網絡中的少量錨節點配備GPS接收器或人工布置,其他節點依靠錨節點的位置信息和節點間的通信或測距技術,通過相應的節點定位算法來獲得其位置信息[1-2]。

迄今為止,研究人員分別從不同的角度來考慮WSN節點的定位問題,如網絡拓撲、設備能力、定位精度和能量需求等,并提出了很多行之有效的節點定位算法。美國Rutgers大學的Niculescu提出了一系列分布式定位算法APS(Ad hoc Location System),其中DV-Hop定位算法DV-Hop(DistanceVector-Hop)是目前應用最為廣泛的一種,該算法根據距離矢量路由和GPS定位原理,僅依靠網絡的連通度就能實現對未知節點的定位,而且傳感器節點不需要任何的額外硬件設施。對于節點分布較規則、錨節點密度較大的傳感器網絡,該算法具有定位速度快、計算復雜度低、擴展性較好等優勢。

協作定位是近年來提出的新概念,是對傳統節點定位方法的擴展[3]。在傳統方法中,定位參數主要是指錨節點和未知節點間的距離、角度等信息,未知節點間的信息被忽略。而在協作方式中,任意2個未知節點間可以相互得到測量數據,能夠使不在錨節點傳輸距離內的節點也能被定位。利用協作思想,未知節點獲取自身位置信息后可以有條件地轉化為錨節點,從而獲得冗余信息,用來進一步提高定位算法的精度和魯棒性。文獻[4-5]都將協作思想應用于節點定位算法,通過循環求精的過程來得到較高的定位精度。

本文在DV-Hop算法的基礎上,提出DC DVHop算法。以最大似然估計準則為依據選取最優錨節點集合,并逐步將符合相應條件的未知節點轉化為錨節點,從而在相同的初始錨節點數量下擴大定位范圍和定位精度。

2 DV-Hop定位算法及誤差分析

DV-Hop算法的定位過程分3個步驟:

(1)距離矢量交換階段:錨節點以泛洪的方式向其鄰居節點發送廣播消息,消息中包含該錨節點的編號、位置坐標和跳數信息。通過錨節點的廣播消息,利用距離矢量路由交換協議,網絡中每個節點都獲得了與其他所有錨節點之間的最小跳段數。

(2)校正值計算和廣播階段:每個錨節點根據與其他錨節點的實際距離和第1步得到的2個錨節點之間的跳段數信息,可以求得每跳平均距離,最后將其作為校正值以廣播的形式發送到網絡中。未知節點根據接收到的最近錨節點的校正值,計算得到與各個錨節點的估計距離。錨節點i的平均跳距計算公式如下:

其中,(xi,yi)和(xj,yj)為錨節點i和j的坐標;hj為錨節點i和j之間的跳數。

(3)坐標計算階段:當未知節點獲得3個或3個以上錨節點的估計距離信息后,利用極大似然估計法計算未知節點坐標信息。

若選取3個錨節點進行三邊測量法,則未知節點U1的坐標(x,y)可通過求解以下方程組得到:

其中,(xi,yi)(i=1,2,3)代表錨節點Mi的精確坐標;di(i=1,2,3)為錨節點Mi與U1的估算距離。

DV-Hop算法使用最近錨節點的平均跳距來計算未知節點與錨節點之間的實際距離。但事實上,由于節點分布的不均勻,使用單個錨節點估計的平均跳距值無法準確地反映全網絡的實際平均跳距,造成距離估計誤差較大;其次,在利用極大似然估計法計算未知節點位置時,如果所選取的3個錨節點位置共線度較強,則位置估算誤差較大;另外,由于傳感器節點在播撒過程中的隨機性,其分布很不均勻,可能出現大量的孤立節點,在其通信范圍內可能無法找到足夠的錨節點以實現定位計算[6-7]。

針對以上對 DV-Hop算法的分析,本文提出一種改進的協作式節點定位算法(DC DV-Hop算法),首先,在選取用來計算未知節點位置的候選錨節點問題上,綜合考慮各個錨節點與未知節點之間的距離及相互位置,選取與未知節點距離最近且共線度最弱的3個錨點參與最大似然估計;其次,未知節點的平均跳距不是采用其最近錨節點的值,而是根據各個錨節點平均跳距的可信度,通過加權計算而獲得;最后,根據未知節點的定位誤差計算,將誤差范圍符合相關條件的已知位置節點轉化為錨節點,從而增加錨節點密度,擴大定位范圍。

3 DC DV-Hop算法原理

3.1 基于共線度計算的錨節點篩選

傳感器網絡的部分拓撲如圖1所示,M1～M4為靠近未知節點U1的4個錨節點,根據DV-Hop算法的最大似然估計原理,在二維平面上,U1至少需要選擇3個錨節點來估計自已的位置信息。

圖1 候選錨節點的選取

以選取錨節點M1～M3為例,如圖1所示,其組成的三角形的一個內角α滿足:

其中,M1M2,M2M3,M1M3為相應2個錨節點之間的距離。

由文獻[4]可知,當3個候選錨節點的共線度DC=π/3時,定位誤差最小。所以,算法預先設定一個閾值C(0＜C＜0.5),當未知節點接收到N個錨節點的路由信息后,首先根據式(2)計算離未知節點距離最近的3個錨節點的共線度,當其共線度滿足時,則進行三邊測量法求未知節點位置信息;否則,如圖1所示,算法自動選擇距U1距離次近的另一個錨節點M4代替M3作為候選錨節點,直到共線度滿足上述條件[8-9]。

3.2 錨節點的可信度

如圖2所示,未知節點U1與錨節點M1～M4相連通,且4個錨節點兩兩之間的距離值相近,U1與M3和M4的連接較靠近直線,但與M2的連接較為曲折。按照式(1)計算平均跳距的方法,錨節點M2參與計算導致平均跳距比實際偏小。由于誤差的傳遞,未知節點U1與錨節點M2的距離計算也會受到影響。

圖2 平均跳距的可信度計算

針對上述問題,本文提出錨節點信任度的計算方法[10]。假設傳感器網絡共有N個錨節點,若錨節點i與其余N-1個錨節點的單條路徑的平均跳距表示為HSij(j≠i),則單條路徑的平均跳距和錨節點i的總平均跳距的偏差程度,再經歸一化處理后,可用來表示錨節點j相對于錨節點i的信任度,具體計算方式如下:

可以看出,當HSij與Hi的偏差較大時,可信度wij的值較小,表明錨節點i與錨節點j的單條路徑上比較曲折,導致平均跳距計算誤差較大。

3.3 未知節點平均跳距的計算

在DV-Hop算法采用三邊測量法估計未知節點位置時,默認參與計算的3個錨節點的可信度相同。但根據上文分析,錨節點因分布的不均勻導致可信度不同,可信度較低的錨節點參與計算會降低定位的精確度。鑒于此,當未知節點接收到多個錨節點的平均跳距信息后,首先選擇離其最近的錨節點的平均跳距為參考,然后根據其他錨節點相對該錨節點的信任度進行加權平均[11]。

如圖2所示,未知節點U1接收到的4個錨節點的平均跳距分別為HS1～HS4,M1離未知節點U1最近,M2～M4的相對M1的可信度分別為w21,w31,w41,則U1的平均跳距計算公式為:

在獲取HSU后,根據U1與各個錨節點之間的最小跳數,兩者相乘估算出U1和候選錨節點之間的距離,然后運用式(1)計算U1的位置。

3.4 協作節點的轉化條件

協作定位算法的基本思想是將通過定位后的節點有條件地轉化為錨節點,從而參與其他未知節點的定位。只有定位結果精度足夠高的節點才可轉化為錨節點,否則以其估計位置來定位其他未知節點時,會使誤差累積[12]。

如圖 1所示,未知節點U1的位置由錨節點M1,M2,M4通過三邊測量法計算獲得,其定位誤差的分析如下:將U1與任一錨節點(M1)進行身份互換,然后根據另2個錨節點(M2和M4)來估算被互換的錨節點(M1)的位置。因為錨節點的位置已知,M1的估算位置若與實際位置較吻合,則表明節點的定位精度較高。假設M1的實際坐標位置為(x,y),而經過互換后的估算位置為(x′,y′),節點間的通信半徑為R,則歸一化定位誤差可表示為:

未知節點轉化為錨節點的條件是:預先設定誤差閾值M,僅當節點定位的歸一化誤差滿足e≤M時,才可將其轉化為錨節點參與其他未知節點的定位計算。

4 DC DV-Hop算法流程

DC DV-Hop算法的流程如下:

(1)通過錨節點的泛洪信息,各個未知節點得知與自己相連通的錨節點的個數、跳距;

(2)未知節點按照跳數從近到遠的原則選取符合共線度準則的3個錨節點;

(3)以距離未知節點最近的錨節點為參考計算其他節點的可信度,按式(5)計算其平均跳距;

(4)計算未知節點與各個錨節點之間的距離,執行三邊測量法估算未知節點的位置;

(5)按照3.4節的方法計算定位結果的誤差,將符合誤差條件的節點轉化為錨節點;

(6)以新的錨節點集循環以上步驟,直到網絡中沒有符合定位條件的未知節點為止。

5 仿真及結果分析

使用Matlab作為仿真工具,設定傳感器網絡為100 m×100 m的正方形區域,錨節點和未知節點的位置為隨機分布,所有節點通信半徑相同。

圖3和圖4分別給出了節點通信半徑為15 m或20 m時,2種算法的歸一化定位誤差和剩余節點比隨錨節點數的變化規律。剩余節點比指的是當定位算法執行完畢后,網絡中未能定位的節點占總節點數的比例。

圖3 平均定位誤差隨錨節點數的變化

圖4 剩余節點比例隨錨節點數的變化

從圖中可以看出,在錨節點數和通信半徑相同的情況下,改進算法比DV-Hop算法擁有更小的定位誤差和剩余節點比,而且可以看到,在錨節點較小的情況下,改進算法能夠獲得較低的定位誤差和剩余節點比。在錨節點數相同的情況下,通信半徑越大,DC DV-Hop算法的定位誤差和剩余節點比越小。當錨節點數超過40個后,2個參數取值都趨于穩定,說明DC DV-Hop算法具有較好的魯棒性。

圖5和圖6分別給出了錨節點數總數不變和錨節點比例不變2種情況下,平均定位誤差同節點密度之間的關系。從圖中可以看出,在2種情況下,改進算法都比原始算法的定位誤差小,尤其在節點密度較小的情況下,改進算法仍具有較低的定位誤差,性能優勢更明顯。在相同節點密度下,通信半徑越大,定位誤差越小。

圖5 平均定位誤差隨節點密度的變化(錨節點數不變)

圖6 平均定位誤差隨節點密度的變化(錨節點比例不變)

圖7和圖8分別給出了錨節點為15個或20個時,平均定位誤差和剩余節點比例與節點通信半徑之間的關系。從圖7可以看出,節點通信半徑相同的情況下,改進算法的定位誤差比原始算法小,尤其在通信半徑較小時(10 m),改進算法的平均定位誤差不到原始算法的1/2。隨著節點通信半徑的增加,平均定位誤差的減小趨于平緩,對于相同算法,錨節點數越大,平均定位誤差越小。

圖7 平均定位誤差隨節點通信半徑的變化

圖8 剩余節點比例隨通信半徑的變化

從圖8可以看出,相同節點通信半徑的情況下,改進算法的剩余節點比小于原始算法,當通信半徑為10 m時,改進算法的剩余節點比約為原始算法的7/10。隨著通信半徑的增大,2種算法的剩余節點比例都變小,而且對于同一種算法,錨節點數越大,剩余節點比例越小。

6 結束語

本文在DV-Hop算法的基礎上,提出了一種基于分布式協作的改進算法。針對參與三邊測量定位的錨節點位置關系,提出根據共線度對候選錨節點進行篩選;針對平均跳距計算誤差較大的問題,提出以錨節點的可信度為參考進行加權平均處理;最后,為減小定位的剩余節點比例,提出以計算定位誤差為條件將部分未知節點轉化為錨節點參與其他節點的定位。通過仿真可以證明,當錨節點密度和節點通信半徑較小的情況下,改進算法的定位誤差和節點剩余比例明顯優于原始算法。

下一步將應用該算法實現傳感器網絡的信息融合,在節點快速精確定位的基礎上,提高信息融合算法中節點選取的合理性。

[1] 王福豹,史 龍,任豐原.無線傳感器網絡中的自身定位系統和算法[J].軟件學報,2005,16(5):857-868.

[2] 楊新宇,孔慶茹,戴湘軍.一種改進的加權質心定位算法[J].西安交通大學學報,2010,44(8):1-5.

[3] 郭建全,趙 偉,黃松嶺.大規模無線傳感器網絡分布式無錨節點定位算法[J].高技術通訊,2011,21(6): 555-561.

[4] Savvides A,Han C C,Srivastava M B.Dynamic Finegrained Localization in Ad-hoc Networks of Sensors [C]//Proceeding ofthe7th AnnualInternational ConferenceonMobileComputingandNetworking Rome.[S.l.]:ACM Press,2001:166-179.

[5] Avvides A,Park H,Srivastava M B.The Bits and Flops of the N-hop Multilateration Primitive for Node Localization Problems[C]//Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications. Atlanta,USA:ACM Press,2002:112-121.

[6] Niculescu D,Nath B.Error Characteristics of Ad Hoc Location Systems(APS)[C]//Proceedings of MobiHoc’04.Roppongil,Japan:[s.n.],2004:20-30.

[7] Jin Seung-Hwan,Yoo Sang-Jo.Improved Location Scheme Based on DV-hop for Wireless Sensor Network[C]// Proceedings ofthe9th InternationalSymposium on Communications and Information Technology.[S.l.]: IEEE Press,2009:69-74.

[8] Lee Byeong-Tae,Kim Sunwoo.Scalable DV-hop Localization forWirelessSensorNetworks[C]// Proceedings of the 14th Asia-Pacific Conference on Communications.Akihabara,Tokyo:[s.n.],2008:1-4.

[9] Lee J,Chung W,Kim E,Hong I W.Robust DV-hop Algorithm for Localization in Wireless Sensor Network[C]//Proceedings of International Conference on ControlAutomation and Systems.Orlando,USA: [s.n.],2010:2506-2509.

[10] Agashe A A,Patil R S.Evaluation of DV Hop Localization Algorithm in Wireless Sensor Networks[C]// Proceedings of International Conference on Advances in Mobile Network,Communication and Its Applications. London,UK:[s.n.],2012:79-82.

[11] Tomic S,MezeiI.Improved DV-Hop Localization Algorithm forWireless Sensor Networks[C]// Proceedings of the 10th Jubilee International Symposium on Intelligent Systems and Informatics.[S.l.]:IEEE Press,2012:389-394.

[12] Li Li,KunzT.Cooperative Node Localization for Tactical Wireless Sensor Networks[C]//Proceedings of Military Communications Conference.Orlando,USA: IEEE Press,2007:1-7.

編輯 金胡考

A Node Location Algorithm in Wireless Sensor Network Based on DV-Hop

WANG Jinghui
(National Digital Switching System Engineering&Technological R&D Center,Zhengzhou 450001,China)

Aiming at the problem of node location in Wireless Sensor Network(WSN),this paper proposes an improved algorithm for DV-Hop based on distributed collaboration.It depends on calculating distance between nodes,and selects the nodes as the anchor nodes which have lower collinear degrees by maximum likelihood estimation.It considers of all anchor nodes,and calculates each nodes average hops by the weighted average algorithm based on their credibility. It calculates the location error of unknown nodes,and turns some nodes as anchor nodes which have lower error,to expand the location scope.Simulation results show that,the improved algorithm can reduce the location error by about 20%compare,with DV-Hop with the same number of anchor nodes and the communication distance between nodes. Especially if the nodes density is smaller,DC DV-Hop can control the location error below 40%,and when the communication distance between nodes is more than 10 meters,this improve algorithm can reduce the ratio of remaining nodes by approximately 30%.

Wireless Sensor Network(WSN);DV-Hop algorithm;anchor node;collinear degree;cooperative localization

1000-3428(2015)01-0082-05

A

TP393

10.3969/j.issn.1000-3428.2015.01.015

王景琿(1969-),男,高級工程師,主研方向:移動通信網絡。

2013-11-25

2014-03-06 E-mail:wjinghui@sina.com

中文引用格式:王景琿.一種基于DV-Hop的無線傳感器網絡節點定位算法[J].計算機工程,2015,41(1):82-86.

英文引用格式:Wang Jinghui.A Node Location Algorithm in Wireless Sensor Network Based on DV-Hop[J].Computer Engineering,2015,41(1):82-86.