王景琿

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

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

王景琿

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

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

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

1 概述

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

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

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

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

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

DV-Hop算法的定位過(guò)程分3個(gè)步驟:

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

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

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

(3)坐標(biāo)計(jì)算階段:當(dāng)未知節(jié)點(diǎn)獲得3個(gè)或3個(gè)以上錨節(jié)點(diǎn)的估計(jì)距離信息后,利用極大似然估計(jì)法計(jì)算未知節(jié)點(diǎn)坐標(biāo)信息。

若選取3個(gè)錨節(jié)點(diǎn)進(jìn)行三邊測(cè)量法,則未知節(jié)點(diǎn)U1的坐標(biāo)(x,y)可通過(guò)求解以下方程組得到:

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

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

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

3 DC DV-Hop算法原理

3.1 基于共線度計(jì)算的錨節(jié)點(diǎn)篩選

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

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

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

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

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

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

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

圖2 平均跳距的可信度計(jì)算

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

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

3.3 未知節(jié)點(diǎn)平均跳距的計(jì)算

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

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

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

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

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

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

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

4 DC DV-Hop算法流程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語(yǔ)

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

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

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

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

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

2013-11-25

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

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