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

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

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

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

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

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

1 DV-hop算法介紹

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

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

第2階段:錨節(jié)點計算平均每跳距離值，如果一個錨節(jié)點的坐標為(xi，yi)，則平均每跳距離計算公式為:

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

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

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

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

其中

使用標準的最小均方差估計方法可以得到未知節(jié)點X的坐標為:

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

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

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

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

2.2 節(jié)點通信半徑

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

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

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

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

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

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

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

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

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

圖3 錨節(jié)點個數(shù)不同時節(jié)點的定位精度

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

［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ǎng)絡(luò)技術(shù)［M］.北京:北京工業(yè)大學出版社，2007，1－17.

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

［5］王福豹，史龍，任豐原.無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和協(xié)議［J］.軟件學報，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］趙清華，劉少飛，張朝霞，等.一種無需測距節(jié)點定位算法的分析和改進［J］.傳感技術(shù)學報，2010，23(1):122－127.

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

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

［11］王書鋒，侯義斌，黃樟欽，等.無線感知網(wǎng)絡(luò)最小二乘法定位算法的誤差分析與優(yōu)化［J］.系統(tǒng)仿真學報，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.