一種無(wú)需測(cè)距的無(wú)線傳感器網(wǎng)絡(luò)定位算法研究

托乎提努爾，陳 曙

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

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

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

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

本文先簡(jiǎn)要介紹DV-Hop算法的基本思想，分析和研究算法原理及誤差產(chǎn)生的主要原因，然后提出原來(lái)算法的改進(jìn)方法，并給出仿真實(shí)驗(yàn)的結(jié)果及其分析。

1 DV-Hop定位算法

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

1.1 算法的基本思想

DV-Hop算法的定位過(guò)程分為3個(gè)階段［10-12］:

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

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

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

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

(3)計(jì)算未知節(jié)點(diǎn)的位置。

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

由式(2)可得，

未知節(jié)點(diǎn)u的坐標(biāo)有如式(5)可以得到，

1.2 算法存在的問題

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

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

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

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

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

2 改進(jìn)的DV-Hop定位算法

本文提出了兩種改進(jìn)方案，對(duì)DV-Hop算法的第2個(gè)，第3個(gè)階段進(jìn)行修改，然后把兩種方法相結(jié)合，提出了一個(gè)新的DV-Hop算法。

2.1 改進(jìn)方法1

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

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

圖2 改進(jìn)方法一的計(jì)算流程

2.2 改進(jìn)方法2

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

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

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

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

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

3 算法仿真與分析

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

圖3 節(jié)點(diǎn)隨機(jī)分布圖

圖4 節(jié)點(diǎn)鄰居關(guān)系圖

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

圖5 錨節(jié)點(diǎn)數(shù)量和定位誤差

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

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

4 結(jié)論

本文針對(duì)傳統(tǒng)DV-Hop算法在節(jié)點(diǎn)隨機(jī)分布的網(wǎng)絡(luò)拓?fù)洵h(huán)境下存在較大誤差的問題，提出了一種改進(jìn)DV-Hop定位算法。通過(guò)擴(kuò)展錨節(jié)點(diǎn)數(shù)量和修正每跳平均距離，使得到的結(jié)果更加接近實(shí)際每跳距離。

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

［1］楊石磊，樊曉平，劉少?gòu)?qiáng)，等.一種改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)DVHop定位算法［J］.計(jì)算機(jī)測(cè)量與控制，2008，16(9):1356-1358.

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

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

［4］李曉維，徐勇軍，任豐原.無(wú)線傳感器網(wǎng)絡(luò)技術(shù)［M］.北京:北京理工大學(xué)出版社，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］張品，孫巖.一種新的無(wú)線傳感器網(wǎng)絡(luò)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］孫晶晶.無(wú)線傳感器網(wǎng)絡(luò)定位算法的研究［D］.西安電子科技大學(xué)，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.