一種基于DV-Hop的無線傳感器網(wǎng)絡(luò)節(jié)點定位算法

王景琿

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

一種基于DV-Hop的無線傳感器網(wǎng)絡(luò)節(jié)點定位算法

王景琿

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

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

無線傳感器網(wǎng)絡(luò);DV-Hop算法;錨節(jié)點;共線度;協(xié)作定位

1 概述

無線傳感器網(wǎng)絡(luò)的節(jié)點定位技術(shù)是網(wǎng)絡(luò)應(yīng)用的關(guān)鍵支撐技術(shù)之一。對于無線傳感器網(wǎng)絡(luò)應(yīng)用來說,節(jié)點的位置信息非常重要。傳感器節(jié)點的位置可以標示監(jiān)測數(shù)據(jù)源的位置,為網(wǎng)絡(luò)管理提供拓撲結(jié)構(gòu),并可生成用于數(shù)據(jù)傳輸?shù)穆酚蓞f(xié)議。傳感器節(jié)點的位置可以通過配置GPS定位裝置或人工定位布置獲得,但由于傳感器網(wǎng)絡(luò)的節(jié)點數(shù)量較大,GPS定位裝置的費用較高,因此目前常用的做法是,網(wǎng)絡(luò)中的少量錨節(jié)點配備GPS接收器或人工布置,其他節(jié)點依靠錨節(jié)點的位置信息和節(jié)點間的通信或測距技術(shù),通過相應(yīng)的節(jié)點定位算法來獲得其位置信息[1-2]。

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

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

本文在DV-Hop算法的基礎(chǔ)上,提出DC DVHop算法。以最大似然估計準則為依據(jù)選取最優(yōu)錨節(jié)點集合,并逐步將符合相應(yīng)條件的未知節(jié)點轉(zhuǎn)化為錨節(jié)點,從而在相同的初始錨節(jié)點數(shù)量下擴大定位范圍和定位精度。

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

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

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

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

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

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

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

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

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

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

3 DC DV-Hop算法原理

3.1 基于共線度計算的錨節(jié)點篩選

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

圖1 候選錨節(jié)點的選取

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

其中,M1M2,M2M3,M1M3為相應(yīng)2個錨節(jié)點之間的距離。

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

3.2 錨節(jié)點的可信度

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

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

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

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

3.3 未知節(jié)點平均跳距的計算

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

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

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

3.4 協(xié)作節(jié)點的轉(zhuǎn)化條件

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

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

未知節(jié)點轉(zhuǎn)化為錨節(jié)點的條件是:預(yù)先設(shè)定誤差閾值M,僅當節(jié)點定位的歸一化誤差滿足e≤M時,才可將其轉(zhuǎn)化為錨節(jié)點參與其他未知節(jié)點的定位計算。

4 DC DV-Hop算法流程

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

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

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

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

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

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

(6)以新的錨節(jié)點集循環(huán)以上步驟,直到網(wǎng)絡(luò)中沒有符合定位條件的未知節(jié)點為止。

5 仿真及結(jié)果分析

使用Matlab作為仿真工具,設(shè)定傳感器網(wǎng)絡(luò)為100 m×100 m的正方形區(qū)域,錨節(jié)點和未知節(jié)點的位置為隨機分布,所有節(jié)點通信半徑相同。

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

圖3 平均定位誤差隨錨節(jié)點數(shù)的變化

圖4 剩余節(jié)點比例隨錨節(jié)點數(shù)的變化

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

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

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

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

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

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

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

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

6 結(jié)束語

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

下一步將應(yīng)用該算法實現(xiàn)傳感器網(wǎng)絡(luò)的信息融合,在節(jié)點快速精確定位的基礎(chǔ)上,提高信息融合算法中節(jié)點選取的合理性。

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

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

[3] 郭建全,趙 偉,黃松嶺.大規(guī)模無線傳感器網(wǎng)絡(luò)分布式無錨節(jié)點定位算法[J].高技術(shù)通訊,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-),男,高級工程師,主研方向:移動通信網(wǎng)絡(luò)。

2013-11-25

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

中文引用格式:王景琿.一種基于DV-Hop的無線傳感器網(wǎng)絡(luò)節(jié)點定位算法[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.