無(wú)線(xiàn)傳感器網(wǎng)絡(luò)選擇性DV-Hop定位算法*

羅 維，姜秀柱，盛蒙蒙

（1.中國(guó)礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇徐州 221116;2.北京理工大學(xué)信息與電子學(xué)院，北京 100081）

0 引言

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)（wireless sensor networks，WSNs）就是由部署在監(jiān)測(cè)區(qū)域內(nèi)大量的微型傳感器節(jié)點(diǎn)組成，通過(guò)無(wú)線(xiàn)通信方式形成的一個(gè)多跳的自組織的網(wǎng)絡(luò)系統(tǒng)［1］。確定事件發(fā)生的位置或獲取消息的節(jié)點(diǎn)位置是無(wú)線(xiàn)傳感器網(wǎng)絡(luò)最基本的功能之一。在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中，定位算法有很多種分類(lèi)。根據(jù)定位過(guò)程中是否測(cè)量實(shí)際節(jié)點(diǎn)間的距離，把定位算法分為基于距離的（range-based）定位算法［2，3］和距離無(wú)關(guān)的（range-free）定位算法［4，5］。其中距離無(wú)關(guān)的矢量跳距（DV-Hop）定位算法［5］應(yīng)用最為廣泛，目前已有對(duì)DV-Hop算法改進(jìn)的很多方法［6～8］。本文在對(duì)傳統(tǒng) DVHop算法分析后，提出了一種選擇性DV-Hop（selective DVHop，SDV-Hop）算法，該算法使得估計(jì)的平均每跳距離更接近實(shí)際每跳距離，能獲得高的定位精度。

1 DV-Hop定位算法

傳統(tǒng)DV-Hop定位算法的定位過(guò)程由3個(gè)階段組成:

1）使用典型的距離矢量交換協(xié)議，通過(guò)節(jié)點(diǎn)間信息交換，使網(wǎng)絡(luò)中所有節(jié)點(diǎn)獲得與信標(biāo)節(jié)點(diǎn)之間的最小跳數(shù)。

2）每個(gè)信標(biāo)節(jié)點(diǎn)在獲得其他信標(biāo)節(jié)點(diǎn)位置信息和跳數(shù)信息之后，利用公式（1）計(jì)算網(wǎng)絡(luò)平均每跳距離，并將其作為一個(gè)跳距校正值廣播至網(wǎng)絡(luò)中

其中，（xi，yi），（xj，yj）分別為信標(biāo)節(jié)點(diǎn)i，j的位置信息，h（i，j）為信標(biāo)節(jié)點(diǎn)i到信標(biāo)節(jié)點(diǎn)j的最小跳數(shù)。

3）未知節(jié)點(diǎn)接收第1個(gè)校正值后，用該校正值乘以到附近各信標(biāo)節(jié)點(diǎn)之間的最小跳數(shù)計(jì)算出估計(jì)距離。最后通過(guò)三邊測(cè)量法計(jì)算出自身的位置。

如圖1所示，已知信標(biāo)節(jié)點(diǎn)L1與L2，L3之間的實(shí)際距離和跳數(shù)，L2計(jì)算得到校正值為（40+75）/（2+5）=16.42m。假設(shè)A從L2獲得校正值，則它與3個(gè)信標(biāo)節(jié)點(diǎn)之間的距離分別為L(zhǎng)1:3 ×16.42 m，L2:2×16.42 m，L3:3×16.42 m。然后使用三邊測(cè)量定位法確定節(jié)點(diǎn)A的位置。

圖1 DV-Hop算法示意圖Fig 1 Diagram of DV-Hop algorithm

2 SDV-Hop定位算法

SDV-Hop算法［9］能完成對(duì)未知節(jié)點(diǎn)更精確的定位，區(qū)別于傳統(tǒng)DV-Hop算法主要體現(xiàn)在定位過(guò)程中對(duì)平均每跳距離的修正。傳統(tǒng)DV-Hop算法由3個(gè)階段組成，SDV-Hop算法也按照3個(gè)階段進(jìn)行。

2.1 跳數(shù)誤差分析與改進(jìn)

在傳統(tǒng)DV-Hop算法中信標(biāo)節(jié)點(diǎn)利用公式（1）的平均每跳距離計(jì)算出網(wǎng)絡(luò)中所有信標(biāo)節(jié)點(diǎn)的平均每跳距離的平均值如公式（2）所示

其中，N是信標(biāo)節(jié)點(diǎn)的總數(shù)量。

2個(gè)信標(biāo)節(jié)點(diǎn)之間的實(shí)際距離如公式（3）所示

其中，（xi，yi），（xk，yk）分別為信標(biāo)節(jié)點(diǎn)i，k的位置信息

由式（2）、式（3）可以得到信標(biāo)節(jié)點(diǎn)i，k的估計(jì)跳數(shù)如公式（4）所示

已知每一個(gè)信標(biāo)節(jié)點(diǎn)的實(shí)際跳數(shù)h（i，k）和估計(jì)跳數(shù)h'（i，k），利用公式（4）可以得到跳數(shù)差如公式（5）所示

跳數(shù)差反映出信標(biāo)節(jié)點(diǎn)i，k的實(shí)際跳數(shù)和估計(jì)跳數(shù)之間誤差的大小。當(dāng)DHC（i，k）的值大于 0.5～1 或小于 －0.5～－1時(shí)，說(shuō)明節(jié)點(diǎn)計(jì)算預(yù)期位置時(shí)，第k個(gè)信標(biāo)節(jié)點(diǎn)不在第i個(gè)信標(biāo)節(jié)點(diǎn)的泰森多邊形（Voronoi圖）區(qū)域內(nèi)。由此可見(jiàn)在傳統(tǒng)的DV-Hop算法中節(jié)點(diǎn)獲得的最小跳數(shù)是存在誤差的。

SDV-Hop算法在第1階段獲得最小跳數(shù)時(shí)作了改進(jìn)。最小跳數(shù)的獲得是在剔除了長(zhǎng)距離信標(biāo)節(jié)點(diǎn)之后，再按照傳統(tǒng)的DV-Hop算法使網(wǎng)絡(luò)中的節(jié)點(diǎn)獲得距離鄰居信標(biāo)節(jié)點(diǎn)的最小跳數(shù)。

2.2 平均每跳距離誤差分析與改進(jìn)

利用公式（1）計(jì)算的平均每跳距離是一個(gè)平均值，所以，當(dāng)未知節(jié)點(diǎn)利用平均每跳距離估計(jì)到信標(biāo)節(jié)點(diǎn)的距離時(shí)會(huì)產(chǎn)生誤差。已知未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的距離增加時(shí)，距離信標(biāo)節(jié)點(diǎn)的跳數(shù)也增加，誤差隨著增大。因此，當(dāng)未知節(jié)點(diǎn)要定位自身的位置時(shí)，應(yīng)該排除長(zhǎng)距離信標(biāo)節(jié)點(diǎn)的信息。

已知未知節(jié)點(diǎn)g距離所有信標(biāo)節(jié)點(diǎn)的最小跳數(shù)，則求得平均跳數(shù)如公式（6）所示

其中，h（g，k）為未知節(jié)點(diǎn)g到信標(biāo)節(jié)點(diǎn)k的最小跳數(shù)，M為未知節(jié)點(diǎn)g能到達(dá)的信標(biāo)節(jié)點(diǎn)總數(shù)目

將計(jì)算出的平均跳數(shù)廣播到網(wǎng)絡(luò)中，所有未知節(jié)點(diǎn)獲得這一平均跳數(shù)信息。當(dāng)h（g，k）大于Hg時(shí)，則剔除長(zhǎng)距離信標(biāo)節(jié)點(diǎn)k的信息。最后計(jì)算剩余信標(biāo)節(jié)點(diǎn)的平均每跳距離C0如公式（7）所示

其中，（xi，yi），（xw，yw）分別為信標(biāo)節(jié)點(diǎn)i，w的位置信息，h（i，w）是剔除長(zhǎng)距離信標(biāo)節(jié)點(diǎn)信息后，信標(biāo)節(jié)點(diǎn)i獲得的到鄰居信標(biāo)節(jié)點(diǎn)w的最小跳數(shù)。

剔除長(zhǎng)距離信標(biāo)節(jié)點(diǎn)后，這里要進(jìn)一步修正平均每跳距離。根據(jù)信標(biāo)節(jié)點(diǎn)i，w的位置信息（xi，yi），（xw，yw），求得信標(biāo)節(jié)點(diǎn)i到信標(biāo)節(jié)點(diǎn)w的實(shí)際距離如公式（8）所示

已知信標(biāo)節(jié)點(diǎn)i到信標(biāo)節(jié)點(diǎn)w的最小跳數(shù)h（i，w）和估計(jì)平均每跳距離C0，由此得信標(biāo)節(jié)點(diǎn)i到信標(biāo)節(jié)點(diǎn)w的估計(jì)距離如公式（9）所示

由公式（8）、式（9）得信標(biāo)節(jié)點(diǎn)i到信標(biāo)節(jié)點(diǎn)w的距離總誤差如公式（10）所示

其中，D（i，w）是信標(biāo)節(jié)點(diǎn)i到信標(biāo)節(jié)點(diǎn)w的實(shí)際距離，D（i，w）是信標(biāo)節(jié)點(diǎn)i到信標(biāo)節(jié)點(diǎn)w的估計(jì)距離。

根據(jù)n個(gè)信標(biāo)節(jié)點(diǎn)間的跳數(shù)總和為C2n，由信標(biāo)節(jié)點(diǎn)的距離總誤差求得每跳平均距離誤差如公式（11）所示

根據(jù)公式（11）的每跳平均距離誤差，第二次更新信標(biāo)節(jié)點(diǎn)i到信標(biāo)節(jié)點(diǎn)w的平均每跳距離如公式（12）所示［10］

最后信標(biāo)節(jié)點(diǎn)i將最接近實(shí)際每跳距離的平均每跳距離Clast廣播到網(wǎng)絡(luò)中的所有節(jié)點(diǎn)。

2.3 未知節(jié)點(diǎn)定位自身位置

未知節(jié)點(diǎn)獲得剩余可信的信標(biāo)節(jié)點(diǎn)的平均每跳距離信息后，估計(jì)到信標(biāo)節(jié)點(diǎn)的距離就可以確定自身位置。假設(shè)某一未知節(jié)點(diǎn)g坐標(biāo)為（x，y）測(cè)得到n個(gè)信標(biāo)節(jié)點(diǎn)的距離，第w個(gè)信標(biāo)節(jié)點(diǎn)的坐標(biāo)為（xw，yw），未知節(jié)點(diǎn)g到信標(biāo)節(jié)點(diǎn)w的距離為dw。根據(jù)上面的已知數(shù)據(jù)，可以得到一個(gè)非線(xiàn)性方程組，將其線(xiàn)性化并使用最小二乘法［11］來(lái)求解，可以得到未知節(jié)點(diǎn)的坐標(biāo)。

3 仿真與分析

利用Matlab仿真實(shí)驗(yàn)平臺(tái)比較SDV-Hop算法與傳統(tǒng)DV-Hop算法的性能。節(jié)點(diǎn)隨機(jī)分布在100 m×100 m的方形區(qū)域里，未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的坐標(biāo)隨機(jī)產(chǎn)生。下面分別討論信標(biāo)節(jié)點(diǎn)比例、節(jié)點(diǎn)數(shù)量以及通信半徑對(duì)兩種定位的平均定位誤差的影響。每種性能的仿真都是隨機(jī)進(jìn)行500次然后取平均值所得。

定位誤差率指的是通過(guò)定位算法得到的未知節(jié)點(diǎn)的估算位置與實(shí)際位置的偏差，這種偏差可以用兩者之間的歐氏距離除以節(jié)點(diǎn)的通信半徑來(lái)衡量，計(jì)算節(jié)點(diǎn)定位誤差如公式（13）所示

其中，（xa，ya）為未知節(jié)點(diǎn)的估算位置信息，（xb，yb）為未知節(jié)點(diǎn)的實(shí)際位置信息，R為節(jié)點(diǎn)的通信半徑。

在仿真環(huán)境中n個(gè)未知節(jié)點(diǎn)的定位誤差率求平均得到平均定位誤差率如公式（14）所示

從圖2可以看出:當(dāng)信標(biāo)節(jié)點(diǎn)比例增加時(shí)，兩種定位算法的平均定位誤差都減小并趨于穩(wěn)定，但SDV-Hop算法的平均定位誤差比傳統(tǒng)DV-Hop算法減少了約6%。

從圖3可以看出:隨著節(jié)點(diǎn)通信半徑的增大，SDV-Hop算法的平均定位誤差始終低于傳統(tǒng)DV-Hop算法。在通信半徑為65 m時(shí)，SDV-Hop算法的平均定位誤差比傳統(tǒng)DVHop算法減少了10%。

從圖4可以看出:隨著節(jié)點(diǎn)總數(shù)的增加，傳統(tǒng)DV-Hop和SDV-Hop的平均定位誤差都減小并趨于穩(wěn)定，當(dāng)節(jié)點(diǎn)總數(shù)為90個(gè)時(shí)，SDV-Hop算法的平均定位誤差比傳統(tǒng)DVHop算法減少了5%。

圖2 平均定位誤差與信標(biāo)節(jié)點(diǎn)比例的關(guān)系圖Fig 2 Relation diagram of average localization error vs ratio of beacon nodes

圖3 平均定位誤差與通信半徑關(guān)系圖Fig 3 Relation diagram of average localization error vs communication radius

圖4 平均定位誤差與節(jié)點(diǎn)總數(shù)關(guān)系圖Fig 4 Relation diagram of average localization error vs number of nodes

4 結(jié)論

SDV-Hop改進(jìn)算法對(duì)平均每跳距離做了二次修正，使得平均每跳距離更接近實(shí)際每跳距離。仿真結(jié)果表明:SDV-Hop算法使得未知節(jié)點(diǎn)定位自身位置時(shí)，平均定位誤差明顯減小。同時(shí)，該算法能剔除長(zhǎng)距離信標(biāo)節(jié)點(diǎn)的信息，因此，在實(shí)際應(yīng)用中既適合節(jié)點(diǎn)分布均勻的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)，同樣也適合節(jié)點(diǎn)分布非均勻的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)。該算法也存在著缺點(diǎn)，多次修正平均每跳距離增加了計(jì)算量。

［1］孫利民，李建中，陳 渝.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，2005:1 －3.

［2］Caffery J.A new approach to the geometry of ToA location［C］//Proc of IEEE Vehicular Technology Conference（VTC），2000:1943－1950.

［3］Nicolescu D，Nath B.Ad Hoc positoning systems（APS）using AoA［C］//Proc of the IEEE INFOCOM，San Francisco:IEEE Computer and Communications Societies，2003:1743 －1743.

［4］Niculescu D.Positioning in Ad Hoc sensor network［J］.IEEE Network，2004，18（4）:24 －29.

［5］Niculescu D，Nath B.DV-based positioning in Ad Hoc networks［J］.Telecommunication Systems，2003，22（1 －4）:267 － 280.

［6］張鴻飛，董齊芬，俞 立.基于局部信標(biāo)選擇的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)定位算法［J］.傳感技術(shù)學(xué)報(bào)，2010，23（4）:571 －576.

［7］姚忠孝，俞 立，董齊芬.基于移動(dòng)信標(biāo)的DV-Hop無(wú)線(xiàn)傳感器網(wǎng)絡(luò)定位算法［J］.傳感技術(shù)學(xué)報(bào)，2009，22（10）:1504－1509.

［8］劉少飛，趙清華，王華奎.基于平均跳距估計(jì)和位置修正的DV-Hop定位算法［J］.傳感器技術(shù)學(xué)報(bào)，2009，22（8）:1154－1158.

［9］Jin Seung-hwan，Yoo Sang-jo.Improved positioning scheme based on DV-Hop for wireless sensor networks［C］// IEEE ISCIT，2009:69－74.

［10］石為人，賈傳江，梁煥煥.一種改進(jìn)的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)DVHop 定位算法［J］.傳感技術(shù)學(xué)報(bào)，2011，24（1）:83－87.

［11］Langendoen K，Reijers N.Distributed localization in wireless sensor networks:A quantitative comparison［J］.Computer Networks，2003，43:69 －74.