托乎提努爾，陳 曙

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

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

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

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

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

1 DV-Hop定位算法

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

1.1 算法的基本思想

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

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

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

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

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

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

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

由式(2)可得，

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

1.2 算法存在的問題

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

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

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

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

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

2 改進的DV-Hop定位算法

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

2.1 改進方法1

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

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

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

2.2 改進方法2

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

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

計算節(jié)點i，j之間的距離如下:

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

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

3 算法仿真與分析

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

圖3 節(jié)點隨機分布圖

圖4 節(jié)點鄰居關系圖

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

圖5 錨節(jié)點數量和定位誤差

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

圖6 節(jié)點通信半徑和定位誤差

4 結論

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

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

［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.