基于DV-hop的無(wú)線傳感器網(wǎng)絡(luò)定位算法研究*

張 震，閆連山，劉江濤，李曉銀

(西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院信息光子與通信研究中心，成都 610031)

無(wú)線傳感網(wǎng)絡(luò)(Wireless Sensor Network，WSN)由大量無(wú)線傳感器節(jié)點(diǎn)組成，現(xiàn)已廣泛應(yīng)用在軍事、環(huán)境、醫(yī)療等領(lǐng)域［1－2］。節(jié)點(diǎn)定位技術(shù)是無(wú)線傳感網(wǎng)絡(luò)得以廣泛應(yīng)用的前提條件，網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)發(fā)回監(jiān)測(cè)區(qū)域內(nèi)的溫度、壓力、濕度等數(shù)據(jù)信息只有與位置信息相關(guān)聯(lián)才有意義［3－4］。節(jié)點(diǎn)的定位技術(shù)是無(wú)線傳感網(wǎng)絡(luò)獲取信息的關(guān)鍵技術(shù)，正逐步受到了越來(lái)越多的關(guān)注［5］。

現(xiàn)有的無(wú)線傳感器節(jié)點(diǎn)定位技術(shù)可以分為兩類:基于測(cè)距的定位技術(shù)［6］和無(wú)需測(cè)距的定位技術(shù)［7－8］?；跍y(cè)距的定位技術(shù)需要測(cè)量節(jié)點(diǎn)間的距離或角度信息，測(cè)量精度高;無(wú)需測(cè)距的定位技術(shù)不需要直接測(cè)量節(jié)點(diǎn)間的距離或角度信息，對(duì)節(jié)點(diǎn)的硬件要求低。出于對(duì)傳感器網(wǎng)絡(luò)成本、功耗等因數(shù)的考慮，以及在大多數(shù)應(yīng)用場(chǎng)合下對(duì)節(jié)點(diǎn)的定位精度要求不高，所以現(xiàn)階段對(duì)無(wú)需測(cè)距的定位技術(shù)研究較多。

DV-hop算法是目前研究和應(yīng)用最為廣泛的無(wú)需測(cè)距定位算法，但在計(jì)算未知節(jié)點(diǎn)和錨節(jié)點(diǎn)間的距離時(shí)估算較粗糙?，F(xiàn)階段，對(duì)DV-hop算法的改進(jìn)方法主要有:(1)與其他的定位算法相結(jié)合［9］;(2)修正未知節(jié)點(diǎn)與錨節(jié)點(diǎn)間的距離［10］;(3)改進(jìn)最后一步的定位計(jì)算方法［11］等，而對(duì)DV-hop算法本身的參數(shù)優(yōu)化研究較少。本文對(duì)DV-hop算法中的參數(shù)進(jìn)行了詳細(xì)的分析，并通過(guò)仿真對(duì)參數(shù)進(jìn)行優(yōu)化。仿真結(jié)果表明，通過(guò)參數(shù)優(yōu)化可以有效地提高DV-hop算法的定位精度。

1 DV-hop算法介紹

DV-hop［12－13］算法主要通過(guò)距離矢量和跳數(shù)來(lái)估測(cè)未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離，然后使用三邊或多邊測(cè)量法求出未知節(jié)點(diǎn)的位置信息。在未知節(jié)點(diǎn)的通信范圍內(nèi)，錨節(jié)點(diǎn)數(shù)目并不多，采用上述方法可以得到節(jié)點(diǎn)到其通信范圍外的多個(gè)錨節(jié)點(diǎn)的距離信息。DV-hop算法主要由以下三步組成:

第1階段:通過(guò)典型的距離矢量路由協(xié)議，使網(wǎng)絡(luò)中所有的節(jié)點(diǎn)獲得到錨節(jié)點(diǎn)最小跳數(shù)值。

第2階段:錨節(jié)點(diǎn)計(jì)算平均每跳距離值，如果一個(gè)錨節(jié)點(diǎn)的坐標(biāo)為(xi，yi)，則平均每跳距離計(jì)算公式為:

式中(xj，yj)表示錨節(jié)點(diǎn)j的坐標(biāo);hj表示錨節(jié)點(diǎn)j到錨節(jié)點(diǎn)i的最小跳數(shù);HopSizei表示錨節(jié)點(diǎn)i計(jì)算的平均每跳距離。將HopSizei作為一個(gè)校正值，在傳感器網(wǎng)絡(luò)中采用可控泛洪法進(jìn)行廣播，傳感器節(jié)點(diǎn)只保存第一個(gè)校正值，以此保證節(jié)點(diǎn)接收到的校正值是最近的一個(gè)錨節(jié)點(diǎn)發(fā)送過(guò)來(lái)的，未知節(jié)點(diǎn)收到校正值后就可以根據(jù)跳數(shù)和校正值計(jì)算其到錨節(jié)點(diǎn)的距離。

第3階段:當(dāng)未知節(jié)點(diǎn)至少獲得到三個(gè)錨節(jié)點(diǎn)的距離時(shí)，通過(guò)使用最小二乘法計(jì)算未知節(jié)點(diǎn)的坐標(biāo)。給定一個(gè)錨節(jié)點(diǎn)集Ri=(xi，yi)T，i=1，2，…M，M表示錨節(jié)點(diǎn)的數(shù)目，并且未知節(jié)點(diǎn)X=(x，y)T到錨節(jié)點(diǎn)i的最小跳數(shù)是Li，因此未知節(jié)點(diǎn)X=(x，y)T到錨節(jié)點(diǎn)i的距離值為di=Li×HopSizei，未知節(jié)點(diǎn)X的坐標(biāo)可以通過(guò)下列公式計(jì)算得:

將前面的(M－1)個(gè)方程依次減去最后一個(gè)方程得到:

式(3)的線性方程表示方式為

其中

使用標(biāo)準(zhǔn)的最小均方差估計(jì)方法可以得到未知節(jié)點(diǎn)X的坐標(biāo)為:

DV-hop算法定位誤差［14］主要來(lái)源于用曲線距離代表直線距離。平均每跳距離的估計(jì)很粗糙，并且多方面影響距離的估測(cè)，如錨節(jié)點(diǎn)數(shù)目、節(jié)點(diǎn)的通信半徑、總節(jié)點(diǎn)數(shù)目等。

2 DV-hop算法參數(shù)分析

2.1 錨節(jié)點(diǎn)數(shù)目

在DV-hop定位算法中，未知節(jié)點(diǎn)的位置是根據(jù)估算的未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離，并利用三邊定位法，計(jì)算出未知節(jié)點(diǎn)的坐標(biāo)。由于錨節(jié)點(diǎn)和未知節(jié)點(diǎn)都是隨機(jī)分布的，如果錨節(jié)點(diǎn)分布在一條直線上或近似在一條直線上，或者錨節(jié)點(diǎn)相距很近，那么式(2)中的某些方程就可以約去，導(dǎo)致最后參與未知節(jié)點(diǎn)位置估計(jì)的錨節(jié)點(diǎn)只有幾個(gè)甚至式(5)不成立，又由于估測(cè)出來(lái)的未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離di本身就有一定的誤差，因此錨節(jié)點(diǎn)的數(shù)目及分布情況對(duì)節(jié)點(diǎn)的定位精度有很大的影響。

2.2 節(jié)點(diǎn)通信半徑

DV-hop算法是通過(guò)跳數(shù)和平均每跳距離來(lái)估測(cè)未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離，而跳數(shù)和節(jié)點(diǎn)的通信半徑有關(guān)系，節(jié)點(diǎn)通信半徑不同會(huì)使兩個(gè)節(jié)點(diǎn)之間的跳數(shù)不同，如圖1所示。

圖1 不同的節(jié)點(diǎn)通信半徑和跳數(shù)的關(guān)系

在圖1中，由于節(jié)點(diǎn)的通信半徑不同，在圖1(a)中節(jié)點(diǎn)A與節(jié)點(diǎn)B之間的跳數(shù)是1跳，而在圖1(b)中，節(jié)點(diǎn)A與節(jié)點(diǎn)B之間的跳數(shù)是2跳。在不同的節(jié)點(diǎn)通信半徑下，估測(cè)出來(lái)的兩節(jié)點(diǎn)之間的距離就相差很大，從而影響節(jié)點(diǎn)的定位精度，因此節(jié)點(diǎn)的通信半徑不同會(huì)導(dǎo)致不同的定位精度。

2.3 總節(jié)點(diǎn)數(shù)目

在一定面積的傳感區(qū)域內(nèi)，不同的傳感器節(jié)點(diǎn)總數(shù)同樣影響DV-hop算法的定位精度。如圖2所示，在相同的節(jié)點(diǎn)通信半徑下，節(jié)點(diǎn)總數(shù)不同，平均一跳內(nèi)的節(jié)點(diǎn)數(shù)目會(huì)相差很大。如果節(jié)點(diǎn)數(shù)目過(guò)少，可能會(huì)出現(xiàn)在錨節(jié)點(diǎn)的通信范圍內(nèi)沒(méi)有節(jié)點(diǎn)，其它節(jié)點(diǎn)接收不到錨節(jié)點(diǎn)的信息，導(dǎo)致節(jié)點(diǎn)無(wú)法定位的情況。

圖2 不同的節(jié)點(diǎn)數(shù)目

3 仿真結(jié)果及分析

由上述分析可知，DV-hop算法中錨節(jié)點(diǎn)的個(gè)數(shù)、節(jié)點(diǎn)的通信半徑、節(jié)點(diǎn)的總個(gè)數(shù)均會(huì)對(duì)節(jié)點(diǎn)的定位誤差產(chǎn)生影響。本小節(jié)具體給出了在100 m×100 m的無(wú)線傳感器網(wǎng)絡(luò)區(qū)域內(nèi)，當(dāng)錨節(jié)點(diǎn)個(gè)數(shù)、節(jié)點(diǎn)的通信半徑、總節(jié)點(diǎn)個(gè)數(shù)變化時(shí)的節(jié)點(diǎn)定位誤差的仿真結(jié)果，并對(duì)其做了分析。

在無(wú)線傳感器網(wǎng)絡(luò)中錨節(jié)點(diǎn)個(gè)數(shù)不同，節(jié)點(diǎn)的定位精度不同，仿真結(jié)果如圖3所示。在圖3(a)中，傳感器節(jié)點(diǎn)總數(shù)為100個(gè)，取節(jié)點(diǎn)通信半徑R分別為15、25、50，對(duì)應(yīng)錨節(jié)點(diǎn)的個(gè)數(shù)B從3～30變化時(shí)。在圖3(b)中，節(jié)點(diǎn)通信半徑為25，取傳感器節(jié)點(diǎn)總數(shù)分別從100、300、500，對(duì)應(yīng)錨節(jié)點(diǎn)的個(gè)數(shù)B從3～30變化。

圖3 錨節(jié)點(diǎn)個(gè)數(shù)不同時(shí)節(jié)點(diǎn)的定位精度

從圖3(a)和(b)中可以看出:當(dāng)節(jié)點(diǎn)的通信半徑和節(jié)點(diǎn)總數(shù)分別不同時(shí)，錨節(jié)點(diǎn)的個(gè)數(shù)B=12左右，節(jié)點(diǎn)的定位誤差能降低到較小值;當(dāng)錨節(jié)點(diǎn)的個(gè)數(shù)從3～10變化時(shí)，節(jié)點(diǎn)的定位誤差迅速減少;隨著錨節(jié)點(diǎn)個(gè)數(shù)繼續(xù)增加，節(jié)點(diǎn)的定位誤差雖有所減小，但幅度趨于平緩。由以上分析可知，當(dāng)錨節(jié)點(diǎn)的個(gè)數(shù)達(dá)到一定數(shù)量時(shí)，其對(duì)節(jié)點(diǎn)定位誤差的影響降低，且錨節(jié)點(diǎn)本身成本較高，說(shuō)明節(jié)點(diǎn)通信半徑和節(jié)點(diǎn)總數(shù)不同時(shí)，在錨節(jié)點(diǎn)個(gè)數(shù)為12處，節(jié)點(diǎn)定位誤差基本接近最小值。

為了研究節(jié)點(diǎn)的通信半徑R不同時(shí)，節(jié)點(diǎn)定位誤差的變化情況，本文給出了在總節(jié)點(diǎn)數(shù)為100，錨節(jié)點(diǎn)個(gè)數(shù)分別為6、8、10、12時(shí)，節(jié)點(diǎn)通信半徑R從10～50變化，節(jié)點(diǎn)的定位誤差變化情況，結(jié)果如圖4所示。

圖4 在不同的節(jié)點(diǎn)通信半徑下定位誤差值

在圖4中，給出了不同錨節(jié)點(diǎn)個(gè)數(shù)下，節(jié)點(diǎn)通信半徑R從10～50變化時(shí)節(jié)點(diǎn)的定位誤差。從圖4可以看出:隨著錨節(jié)點(diǎn)個(gè)數(shù)的逐漸增加(6～12變化時(shí))，節(jié)點(diǎn)的定位誤差相應(yīng)的降低;在不同錨節(jié)點(diǎn)個(gè)數(shù)下，當(dāng)節(jié)點(diǎn)通信半徑從10～20變化時(shí)，節(jié)點(diǎn)定位誤差迅速減少，并達(dá)到最小值，隨著節(jié)點(diǎn)通信半徑的繼續(xù)增加，節(jié)點(diǎn)的定位誤差也開始增加，說(shuō)明當(dāng)錨節(jié)點(diǎn)不同時(shí)，總節(jié)點(diǎn)數(shù)100時(shí)，存在最優(yōu)R值。

為了使仿真的結(jié)果更加真實(shí)有效，圖3和圖4中的數(shù)值均是100次仿真結(jié)果求得的平均值。綜合考慮圖3和圖4可以得出:在100 m×100 m的區(qū)域內(nèi)，總節(jié)點(diǎn)數(shù)目為100的條件下，當(dāng)錨節(jié)點(diǎn)的個(gè)數(shù)B=12，節(jié)點(diǎn)的通信半徑R=22 m時(shí)，節(jié)點(diǎn)的定位誤差較小。在本文的后續(xù)仿真中，在100 m×100 m的無(wú)線傳感器網(wǎng)絡(luò)區(qū)域內(nèi)，取錨節(jié)點(diǎn)的個(gè)數(shù)為12。

為了研究無(wú)線傳感器網(wǎng)絡(luò)區(qū)域內(nèi)總節(jié)點(diǎn)個(gè)數(shù)不同時(shí)，最優(yōu)節(jié)點(diǎn)通信半徑是否變化，以及最低節(jié)點(diǎn)定位誤差的變化情況，圖5分別給出了總節(jié)點(diǎn)數(shù)在100、300、500處，節(jié)點(diǎn)通信半徑R從5～50變化時(shí)，節(jié)點(diǎn)定位誤差的變化情況。

圖5 在不同的節(jié)點(diǎn)通信半徑下定位誤差值

從圖5中可以看出，隨著總節(jié)點(diǎn)數(shù)的增加，節(jié)點(diǎn)的定位誤差整體都在下降，并且最優(yōu)的節(jié)點(diǎn)通信半徑也在變化，表1給出了在不同總節(jié)點(diǎn)數(shù)下，對(duì)應(yīng)的最優(yōu)節(jié)點(diǎn)通信半徑和相應(yīng)的最低節(jié)點(diǎn)定位誤差值。

表1 不同總節(jié)點(diǎn)數(shù)下的最優(yōu)節(jié)點(diǎn)通信半徑和定位誤差

綜合圖5和表1可得:在不同的總節(jié)點(diǎn)數(shù)目條件下，存在最優(yōu)的節(jié)點(diǎn)通信半徑，使定位誤差降低到最低值。要想使DV-hop算法的定位精度達(dá)到最好，可以根據(jù)表1，在不同總節(jié)點(diǎn)數(shù)目下，選擇最優(yōu)的節(jié)點(diǎn)通信半徑，從而使節(jié)點(diǎn)的定位誤差降低到最小值。

4 結(jié)論

本文主要對(duì)基于DV-hop算法的無(wú)線傳感器網(wǎng)絡(luò)自身定位進(jìn)行了研究，首先詳細(xì)介紹了DV-hop算法的步驟。然后分析了影響DV-hop算法的定位精度的主要參數(shù)包括:錨節(jié)點(diǎn)個(gè)數(shù)、節(jié)點(diǎn)的通信半徑、網(wǎng)絡(luò)中的總節(jié)點(diǎn)數(shù)。經(jīng)分析和仿真結(jié)果表明:在100 m×100 m監(jiān)測(cè)區(qū)域內(nèi)，錨點(diǎn)節(jié)點(diǎn)個(gè)數(shù)為12左右，并且針對(duì)不同總節(jié)點(diǎn)數(shù)，選擇合適的節(jié)點(diǎn)通信半徑，可以使節(jié)點(diǎn)的定位誤差降低到較低值。

［1］Ren F Y，Huang H N，Lin C.Wireless Sensor Network［J］.Journal of Software，2003，4(7):1282－1291.

［2］Akyildiz L F，Su W，Sankarasubramaniam Y，et al.A Survey on Sensor Networks［J］.IEEE Communications Magazine，2002，40(8):102－114.

［3］李曉維，徐勇軍，任豐原.無(wú)線傳感器網(wǎng)絡(luò)技術(shù)［M］.北京:北京工業(yè)大學(xué)出版社，2007，1－17.

［4］戴瑩，王建平，張崇巍.無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法的研究也改進(jìn)［J］.傳感技術(shù)學(xué)報(bào)，2010，23(4):567－570.

［5］王福豹，史龍，任豐原.無(wú)線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和協(xié)議［J］.軟件學(xué)報(bào)，2005，16(5):857－868.

［6］Xiao J，Ren L R，Tan J D.Research of TDOA Based Self-Localization Approach in Wireless Sensor Network［J］.Intelli-Gent Robots and Systems，2006，(10):2035－2040.

［7］Li M，Liu Y H.Rendered Path:Range-Free Localization in Anisotropic Sensor Networks with Holes［J］.IEEE/ACM Transactions on Networking，2010，18(1):320－332.

［8］趙清華，劉少飛，張朝霞，等.一種無(wú)需測(cè)距節(jié)點(diǎn)定位算法的分析和改進(jìn)［J］.傳感技術(shù)學(xué)報(bào)，2010，23(1):122－127.

［9］胡斌，李方敏，劉新華.基于RSSI量化模型的定位算法研究［J］.武漢理工大學(xué)學(xué)報(bào)，2009，31(23):92－95.

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

［11］王書鋒，侯義斌，黃樟欽，等.無(wú)線感知網(wǎng)絡(luò)最小二乘法定位算法的誤差分析與優(yōu)化［J］.系統(tǒng)仿真學(xué)報(bào)，2009，21(19):6211－6215.

［12］Niculescu D，Nath B.DV Based Positioning in ad hoc Networks［J］.Journal of Telecommunication Systems，2003:22(1－4):267－280.

［13］Niculescu D，Nath B.Ad hoc Positioning System(APS)Using AOA［C］//INFOCOM 2003.22nd Annual Joint Conference of the IEEE Computer and Communications.San Francisco，USA，2003.IEEE Societies(3)，1734－1743.

［14］He T，Huang C，Blum B M，et al.Range-Free Localization Schemes for Large Scale Sensor Networks［C］//Proceedings of the 9th Annual International Conference on Mobile Computing and Networking，San Diego，2003.ACM Press，81－95.