一種無需測距的無線傳感器網絡定位算法研究

托乎提努爾，陳 曙

(山東大學信息科學與工程學院，濟南250100)

無線傳感器網絡(Wireless Sensor Network，WSN)是由大量成本低廉的，具有感知能力、計算能力和無線通訊能力的傳感器節點組成的智能網絡。WSN節點一般被密集部署在特定的監控區域內，節點間以無線、多跳的通信方式自組織網絡拓撲結構，通過協同工作完成單個節點不能完成的全局任務［1］。

節點定位是無線傳感器網絡非常重要的技術之一，目前已經提出了許多以獲取節點準確坐標位置為目的的定位算法。按照定位所采用的距離參數獲得方式，把定位算法分為基于測距算法(Range-based)和無需測距算法(Range-free)［2］?；跍y距的定位算法常用的測距技術有TOA或TDOA測距、AOA測距和RSSI測距［3-5］。Range-based定位算法對網絡的硬件設施提出了較高的要求，同時通常需要多次測量，這些算法在獲得相對精確定位結果的時候，都要產生大量計算和通信開銷。因此，Range-free定位算法受到越來越多的關注。

Range-free定位算法無需距離和角度信息，僅根據網絡連通性和己知位置的錨節點信息來實現相對精確的定位功能。這種算法降低了對節點的硬件要求，使節點成本更適用于大規模傳感器網絡［6］，而且其定位性能受環境因素的影響較小。典型的算法包括質心、DV-Hop［7］、Amorphous、APIT 等［8-9］。在DV-Hop定位算法中，錨節點廣播包含自身位置和跳數信息的分組，對于每個待定位節點，它只記錄到每個錨節點的最小跳數，知道錨節點的位置和平均每跳距離，就可以利用三邊測量法或極大似然估計法計算自身位置。

本文先簡要介紹DV-Hop算法的基本思想，分析和研究算法原理及誤差產生的主要原因，然后提出原來算法的改進方法，并給出仿真實驗的結果及其分析。

1 DV-Hop定位算法

DV-Hop定位算法，是一種基于距離矢量路由的無需測距定位算法，其基本思想是將未知節點到錨節點之間的距離用網絡每跳平均距離和兩者之間跳數之積表示，再使用三邊定位運算法獲得節點位置信息。

1.1 算法的基本思想

DV-Hop算法的定位過程分為3個階段［10-12］:

(1)計算未知節點與每個錨節點的最小跳數。錨節點向鄰居節點廣播自身位置信息的分組，其中包括跳數字段，初始化為0。接收節點記錄到每個錨節點的最小跳數，忽略來自同一個錨節點的較大跳數的分組。然后將跳數加1，并轉發給鄰居節點。通過這個方法，網絡中的所有節點能夠記錄到每個錨節點的最小跳數。

(2)計算未知節點和錨節點的每跳平均距離。

每個錨節點根據第一階段中記錄的其他錨節點的位置信息和相距跳數，利用式(1)估算平均每跳的實際距離。

其中(xi，yi)，(xj，yj)為錨節點i，j的坐標，hij是錨節點i與j之間的跳數。然后，錨節點將計算的每跳平均距離用帶有生存期字段的分組廣播至網絡中，未知節點僅記錄接收到的第一個每跳平均距離，并轉發給鄰居節點。這個策略確保了大多數節點從最近的錨節點接收到每跳平均距離值。未知節點接收到每跳平均距離后，根據記錄的跳數，計算到每個錨節點的跳段距離。

(3)計算未知節點的位置。

當未知節點獲得到附近錨節點的估計距離之后，通常采用三邊測量法進行位置估計。假設某一未知節點u坐標為(x，y)測得到n個錨節點的距離，第i個錨節點的坐標為(xi，yi)，節點u到錨節點i的距離為di。根據上面的已知數據，可以得到如式(2)所示的系統方程:

由式(2)可得，

未知節點u的坐標有如式(5)可以得到，

1.2 算法存在的問題

DV-Hop算法的不足有以下幾個方面:

(1)在一個錨節點覆蓋范圍內，不管未知節點位置在哪兒，都算1跳，即1 Hop。如圖1所示，K是錨節點，A，B是未知節點，R是錨節點的通信半徑，根據DV-Hop算法計算KA=1 Hop，KB=1 Hop，即KA=KB，所以產生誤差。

圖1 DV-Hop算法誤差示意圖

(2)DV-Hop算法用錨節點間的直線距離來估算錨節點間信息通路的曲線距離，在計算最小跳數時，無論相鄰節點物理距離的遠或近，跳數值均只固定增加1，并不能反映距離的差別，因而導致定位結果存在較大的誤差。

由于DV-Hop算法存在上面所說的定位誤差問題，在大規模傳感器網絡中積累這些誤差產生很大的誤差，降低定位精度，很大程度上影響準確定位。所以減少誤差DV-Hop定位算法中的最關鍵問題。

2 改進的DV-Hop定位算法

本文提出了兩種改進方案，對DV-Hop算法的第2個，第3個階段進行修改，然后把兩種方法相結合，提出了一個新的DV-Hop算法。

2.1 改進方法1

錨節點的數量很大程度上影響WSN定位算法的精度，如果網絡中有較少數量的錨節點，定位誤差會增加。所以盡量提高參與某一未知節點定位的錨節點數量。本方法的主要思想是:第1步，第2步和原來的DV-Hop算法一樣。第3步，與錨節點直接相鄰的未知節點先定位，然后使其升級到錨節點，下次參與定位未知節點，擴展錨節點數量，然后再重新回到第1步計算，直到把全部未知節點定位為止重復運行。

算法的具體流程如圖2所示。

圖2 改進方法一的計算流程

2.2 改進方法2

為了提高定位精度，需要減少未知節點實際位置和估算位置的誤差。與未知節點距離最近的錨節點，對這個未知節點平均每跳距離的影響最大。首先求每跳距離平均值，然后計算改進的每跳平均距離，具體如下:

其中，de是錨節點對未知節點作用離散之后的每跳距離，hui是錨節點之間的跳數n是錨節點個數，unknown是未知節點個數。在改進的方法中提出了一種新的誤差修正值Ce計算錨節點之間的每跳平均距離誤差修正值如下:

計算節點i，j之間的距離如下:

其中，hhop(i，j)是節點i和j之間的跳數。

用這種方法計算未知節點位置，和原來的DVHop算法相比更接近實際位置，我們能夠有效地減少平均每跳距離誤差對節點定位的影響，顯著提高定位精度。

3 算法仿真與分析

為了驗證改進算法的性能，本文對傳統DVHop定位算法和改進算法在MATLAB平臺上進行了仿真對比分析。假設仿真節點都隨機分布了一個二維平面上，在一個100 m×100 m的區域內，隨機布散200個節點，如圖3、圖4所示，其中錨節點的坐標信息是已知的，而未知節點需要通過計算得到。在仿真中對每種算法都隨機運行100次，然后取其整體定位誤差的平均值。

圖3 節點隨機分布圖

圖4 節點鄰居關系圖

在圖5中，通信半徑R=30 m，分別選取了4、6、8、10、12、15、18 這7 種初始錨節點數量進行觀測和結果對比。從圖3中可以看出，隨著錨節點數量的增加，兩種算法的定位誤差都在降低。當錨節點數量為4～10時，兩種算法的定位誤差下降趨勢都很明顯，然后定位誤差下降趨勢減緩。在錨節點數量為4時，改進算法比原算法平均誤差降低了約19%。仿真結果表明，改進的定位算法有效地減少未知節點的定位誤差。

圖5 錨節點數量和定位誤差

在圖6中，在實驗區域內保持錨節點數量為6，通信半徑從15 m變化到40 m，比較傳統DV-Hop算法和改進DV-Hop算法。從圖中可以看出，隨著節點通信半徑的增大，兩種算法的節點平均定位誤差都呈現遞減趨勢，當節點通信半徑較大時，這種下降趨勢明顯。在相同條件下，改進算法的平均定位誤差明顯小于傳統DV-Hop算法。當通信半徑為15時，兩種算法的平均誤差差距最小，但源算法的定位誤差仍高于改進算法。

圖6 節點通信半徑和定位誤差

4 結論

本文針對傳統DV-Hop算法在節點隨機分布的網絡拓撲環境下存在較大誤差的問題，提出了一種改進DV-Hop定位算法。通過擴展錨節點數量和修正每跳平均距離，使得到的結果更加接近實際每跳距離。

理論分析和算法仿真顯示，與傳統算法相比，在定位節點無須額外增加傳感器節點硬件開銷的條件下，可明顯提高節點定位的精度，同時具有良好的擴展性。因此，對于精度要求不高，硬件環境不足的定位應用，它是一種實用，有效的選擇。對精度要求更高的環境中，需要我們將來進一步研究出應用范圍更廣的新的定位算法。

［1］楊石磊，樊曉平，劉少強，等.一種改進的無線傳感器網絡DVHop定位算法［J］.計算機測量與控制，2008，16(9):1356-1358.

［2］石為人，賈傳江，梁煥煥.一種改進的無線傳感器網絡DV-Hop定位算法［J］.傳感技術學報，2011，24(1):83-87.

［3］Niculescu D，Nath B.Ad Hoc Positioning System(APS)Using AOA［C］//IEEE Infocom，2003:1124-1136.

［4］李曉維，徐勇軍，任豐原.無線傳感器網絡技術［M］.北京:北京理工大學出版社，2007:191-221.

［5］Wang Fubao，Shi Long，Ren Fengyuan.Positioning Systems and Algorithms for Wireless Sensor Network［J］.Journal of Software，2004，16(5):45-49.

［6］張品，孫巖.一種新的無線傳感器網絡DV-Hop算法［J］.電子器件，2010，33(1):117-120.

［7］Niculescu D，Nath B.DV Based Positioning in Ad Hoc Networks［J］.Telecommunication Systems，2003，22:267-280.

［8］孫晶晶.無線傳感器網絡定位算法的研究［D］.西安電子科技大學，8-29.

［9］Wu Yanhai，Zhang Jia，Wu Nan.Improved Localization Algorithm in Wireless Sensor Networks［C］//2011 Fourth International Conference on Intelligent Computation Technology and Automation，2011，576-579.

［10］Li Yuanyuan.Improved DV-HOP Location Algorithm Based on Local Estimating and Dynamic Correction in Location for Wireless Sensor Networks［J］.International Journal of Digital Content Technology and Its Applications，2011，5(8):196-202.

［11］Lu Qingling，Bai Mengliang，Zhang Wei.A Kind of Improved DVHop Algorithm［C］//The 2nd International Conference on Intelligent Control and Information Processing，2011，867-869.

［12］Fang Wangsheng，Yang Guangyu.Improvement Based on DV-Hop Localization Algorithm of Wireless Sensor Network［C］//2011 International Conference on Mechatronic Science，Electric Engineering and Computer，2011，2421-2424.