無線傳感器網絡選擇性DV-Hop定位算法*

羅 維，姜秀柱，盛蒙蒙

（1.中國礦業大學 計算機科學與技術學院，江蘇徐州 221116;2.北京理工大學信息與電子學院，北京 100081）

0 引言

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

1 DV-Hop定位算法

傳統DV-Hop定位算法的定位過程由3個階段組成:

1）使用典型的距離矢量交換協議，通過節點間信息交換，使網絡中所有節點獲得與信標節點之間的最小跳數。

2）每個信標節點在獲得其他信標節點位置信息和跳數信息之后，利用公式（1）計算網絡平均每跳距離，并將其作為一個跳距校正值廣播至網絡中

其中，（xi，yi），（xj，yj）分別為信標節點i，j的位置信息，h（i，j）為信標節點i到信標節點j的最小跳數。

3）未知節點接收第1個校正值后，用該校正值乘以到附近各信標節點之間的最小跳數計算出估計距離。最后通過三邊測量法計算出自身的位置。

如圖1所示，已知信標節點L1與L2，L3之間的實際距離和跳數，L2計算得到校正值為（40+75）/（2+5）=16.42m。假設A從L2獲得校正值，則它與3個信標節點之間的距離分別為L1:3 ×16.42 m，L2:2×16.42 m，L3:3×16.42 m。然后使用三邊測量定位法確定節點A的位置。

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

2 SDV-Hop定位算法

SDV-Hop算法［9］能完成對未知節點更精確的定位，區別于傳統DV-Hop算法主要體現在定位過程中對平均每跳距離的修正。傳統DV-Hop算法由3個階段組成，SDV-Hop算法也按照3個階段進行。

2.1 跳數誤差分析與改進

在傳統DV-Hop算法中信標節點利用公式（1）的平均每跳距離計算出網絡中所有信標節點的平均每跳距離的平均值如公式（2）所示

其中，N是信標節點的總數量。

2個信標節點之間的實際距離如公式（3）所示

其中，（xi，yi），（xk，yk）分別為信標節點i，k的位置信息

由式（2）、式（3）可以得到信標節點i，k的估計跳數如公式（4）所示

已知每一個信標節點的實際跳數h（i，k）和估計跳數h'（i，k），利用公式（4）可以得到跳數差如公式（5）所示

跳數差反映出信標節點i，k的實際跳數和估計跳數之間誤差的大小。當DHC（i，k）的值大于 0.5～1 或小于 －0.5～－1時，說明節點計算預期位置時，第k個信標節點不在第i個信標節點的泰森多邊形（Voronoi圖）區域內。由此可見在傳統的DV-Hop算法中節點獲得的最小跳數是存在誤差的。

SDV-Hop算法在第1階段獲得最小跳數時作了改進。最小跳數的獲得是在剔除了長距離信標節點之后，再按照傳統的DV-Hop算法使網絡中的節點獲得距離鄰居信標節點的最小跳數。

2.2 平均每跳距離誤差分析與改進

利用公式（1）計算的平均每跳距離是一個平均值，所以，當未知節點利用平均每跳距離估計到信標節點的距離時會產生誤差。已知未知節點到信標節點的距離增加時，距離信標節點的跳數也增加，誤差隨著增大。因此，當未知節點要定位自身的位置時，應該排除長距離信標節點的信息。

已知未知節點g距離所有信標節點的最小跳數，則求得平均跳數如公式（6）所示

其中，h（g，k）為未知節點g到信標節點k的最小跳數，M為未知節點g能到達的信標節點總數目

將計算出的平均跳數廣播到網絡中，所有未知節點獲得這一平均跳數信息。當h（g，k）大于Hg時，則剔除長距離信標節點k的信息。最后計算剩余信標節點的平均每跳距離C0如公式（7）所示

其中，（xi，yi），（xw，yw）分別為信標節點i，w的位置信息，h（i，w）是剔除長距離信標節點信息后，信標節點i獲得的到鄰居信標節點w的最小跳數。

剔除長距離信標節點后，這里要進一步修正平均每跳距離。根據信標節點i，w的位置信息（xi，yi），（xw，yw），求得信標節點i到信標節點w的實際距離如公式（8）所示

已知信標節點i到信標節點w的最小跳數h（i，w）和估計平均每跳距離C0，由此得信標節點i到信標節點w的估計距離如公式（9）所示

由公式（8）、式（9）得信標節點i到信標節點w的距離總誤差如公式（10）所示

其中，D（i，w）是信標節點i到信標節點w的實際距離，D（i，w）是信標節點i到信標節點w的估計距離。

根據n個信標節點間的跳數總和為C2n，由信標節點的距離總誤差求得每跳平均距離誤差如公式（11）所示

根據公式（11）的每跳平均距離誤差，第二次更新信標節點i到信標節點w的平均每跳距離如公式（12）所示［10］

最后信標節點i將最接近實際每跳距離的平均每跳距離Clast廣播到網絡中的所有節點。

2.3 未知節點定位自身位置

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

3 仿真與分析

利用Matlab仿真實驗平臺比較SDV-Hop算法與傳統DV-Hop算法的性能。節點隨機分布在100 m×100 m的方形區域里，未知節點與信標節點的坐標隨機產生。下面分別討論信標節點比例、節點數量以及通信半徑對兩種定位的平均定位誤差的影響。每種性能的仿真都是隨機進行500次然后取平均值所得。

定位誤差率指的是通過定位算法得到的未知節點的估算位置與實際位置的偏差，這種偏差可以用兩者之間的歐氏距離除以節點的通信半徑來衡量，計算節點定位誤差如公式（13）所示

其中，（xa，ya）為未知節點的估算位置信息，（xb，yb）為未知節點的實際位置信息，R為節點的通信半徑。

在仿真環境中n個未知節點的定位誤差率求平均得到平均定位誤差率如公式（14）所示

從圖2可以看出:當信標節點比例增加時，兩種定位算法的平均定位誤差都減小并趨于穩定，但SDV-Hop算法的平均定位誤差比傳統DV-Hop算法減少了約6%。

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

從圖4可以看出:隨著節點總數的增加，傳統DV-Hop和SDV-Hop的平均定位誤差都減小并趨于穩定，當節點總數為90個時，SDV-Hop算法的平均定位誤差比傳統DVHop算法減少了5%。

圖2 平均定位誤差與信標節點比例的關系圖Fig 2 Relation diagram of average localization error vs ratio of beacon nodes

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

圖4 平均定位誤差與節點總數關系圖Fig 4 Relation diagram of average localization error vs number of nodes

4 結論

SDV-Hop改進算法對平均每跳距離做了二次修正，使得平均每跳距離更接近實際每跳距離。仿真結果表明:SDV-Hop算法使得未知節點定位自身位置時，平均定位誤差明顯減小。同時，該算法能剔除長距離信標節點的信息，因此，在實際應用中既適合節點分布均勻的無線傳感器網絡，同樣也適合節點分布非均勻的無線傳感器網絡。該算法也存在著缺點，多次修正平均每跳距離增加了計算量。

［1］孫利民，李建中，陳 渝.無線傳感器網絡［M］.北京:清華大學出版社，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］張鴻飛，董齊芬，俞 立.基于局部信標選擇的無線傳感器網絡定位算法［J］.傳感技術學報，2010，23（4）:571 －576.

［7］姚忠孝，俞 立，董齊芬.基于移動信標的DV-Hop無線傳感器網絡定位算法［J］.傳感技術學報，2009，22（10）:1504－1509.

［8］劉少飛，趙清華，王華奎.基于平均跳距估計和位置修正的DV-Hop定位算法［J］.傳感器技術學報，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］石為人，賈傳江，梁煥煥.一種改進的無線傳感器網絡DVHop 定位算法［J］.傳感技術學報，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.