DV－Hop無線網(wǎng)絡(luò)定位算法研究

胡華鵬，胡方明，周 惇，張 釗

(西安電子科技大學(xué) 電子工程學(xué)院，陜西 西安710071)

節(jié)點(diǎn)定位問題已經(jīng)成為無線網(wǎng)絡(luò)傳感器的一個(gè)重要研究方向。無線網(wǎng)絡(luò)傳感器中，根據(jù)定位過程中是否用到節(jié)點(diǎn)間的實(shí)際距離，把定位機(jī)制分為:基于測距的(Range－based)定位和距離無關(guān)的(Range－free)定位方法［1］。

Range－based算法需要測量相鄰節(jié)點(diǎn)間的實(shí)際距離，利用已知節(jié)點(diǎn)間的距離和坐標(biāo)定位出未知節(jié)點(diǎn)的位置，但此定位方法的成本較高。該測距方法有Radio Signal Strength(RSSI)，Time of Arrival(TOA)，Time Difference of Arrival(TDOA)和Angel of Arrival(AOA)等。Range－free定位算法則僅利用節(jié)點(diǎn)間的距離關(guān)聯(lián)來計(jì)算未知節(jié)點(diǎn)的位置。定位算法比Range－based算法差，但成本大幅降低。典型的定位算法有DVHop算法［2］，Sum－Dist算法，Euclidean算法和基于連通性的定位算法等。

Niculescu等為避免對(duì)節(jié)點(diǎn)間距離的直接測量而提出了DV－Hop算法。該算法是基于距離矢量計(jì)算跳數(shù)的算法。該算法的基本思想是，將待定位節(jié)點(diǎn)到已知節(jié)點(diǎn)之間的距離用網(wǎng)絡(luò)中節(jié)點(diǎn)平均每跳距離和到已知節(jié)點(diǎn)間的跳數(shù)乘積來標(biāo)識(shí)，再使用三邊測量法和最大似然估計(jì)法來獲得待定位節(jié)點(diǎn)的位置信息。

由于無線傳感器網(wǎng)絡(luò)［3］中DV－Hop算法的錨節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的平均跳距估算的誤差較大，容易造成累積誤差［4］。由此本文對(duì)原有DV－Hop算法進(jìn)行修改，提出了一種新的節(jié)點(diǎn)位置估計(jì)算法。

1 DV－Hop算法的定位過程

DV－Hop的定位算法可以分為3個(gè)過程［5－7］:

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

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

式中，hij為第i個(gè)節(jié)點(diǎn)到第j個(gè)節(jié)點(diǎn)間的跳數(shù);(xi，yi)為第i個(gè)節(jié)點(diǎn)的坐標(biāo);(xj，yj)為第j個(gè)節(jié)點(diǎn)的坐標(biāo)。假設(shè)DV－Hop的模型如圖1所示。

圖1 DV－Hop算法模型

其中，L1，L2，L3是錨節(jié)點(diǎn);A是一個(gè)未知節(jié)點(diǎn);L1，L2，L3這3點(diǎn)之間的距離已知，分別是30，50和80。節(jié)點(diǎn)L1～L2的距離為30;跳數(shù)為4;節(jié)點(diǎn)L1到節(jié)點(diǎn)L3的距離為50;跳數(shù)為4，根據(jù)公式計(jì)算節(jié)點(diǎn)L1直接每跳的平均距離為［(30+50)/(4+4)］=10。同理亦可得L2的平均每跳距離為［(30+80)/(4+6)］=11，L3的每跳平均距離為［(80+50)/(4+6)］=13。

一個(gè)信標(biāo)節(jié)點(diǎn)在計(jì)算完與其他各信標(biāo)節(jié)點(diǎn)每跳的平均距離后，在對(duì)鄰居節(jié)點(diǎn)廣播的消息發(fā)分組中，包含了各錨節(jié)點(diǎn)的最新信息。這樣，其他節(jié)點(diǎn)可以得到錨節(jié)點(diǎn)的最新位置信息，一般是周圍相鄰節(jié)點(diǎn)先得到。在網(wǎng)絡(luò)中，位置信息以廣播的方式發(fā)射，網(wǎng)絡(luò)中的節(jié)點(diǎn)在收到位置信息時(shí)就與原來收到的位置信息進(jìn)行比較，如果新收到的位置信息比原來的位置信息更新，就拋棄原來的位置信息，將新收到的位置信息儲(chǔ)存起來，這樣就可以保證節(jié)點(diǎn)只儲(chǔ)存1條最新的位置信息。未知節(jié)點(diǎn)接收到錨節(jié)點(diǎn)的每段平均距離，再根據(jù)式(2)可計(jì)算得到未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離

其中，hops為未知節(jié)點(diǎn)到錨節(jié)點(diǎn)之間的最小跳數(shù)。

(3)完成待定節(jié)點(diǎn)的位置估計(jì)。利用已經(jīng)得到的數(shù)據(jù)用三邊測量法和極大似然估計(jì)法完成位置節(jié)點(diǎn)的定位。

DV－Hop定位算法將平均每段的跳距與跳數(shù)的距離作為距離的估算值，所以平均跳距在較大程度上決定了DV－Hop的定位精度。若要誤差在合理的估算范圍內(nèi)，則要求無線網(wǎng)絡(luò)中節(jié)點(diǎn)分布虛密集、均勻。但網(wǎng)絡(luò)中的節(jié)點(diǎn)較少且分布離散時(shí)，就容易造成累積誤差。隨著跳數(shù)的增加，誤差將越來越大。

2 DV－Hop算法的改進(jìn)

2.1 均勻量化模型

對(duì)任意節(jié)點(diǎn)i，假設(shè)信號(hào)的最大接收功率為Pmax，最小接收功率為Pmin，對(duì)通訊半徑進(jìn)行量化，量化的最大等級(jí)為M。任意鄰居節(jié)點(diǎn)為j，設(shè)節(jié)點(diǎn)j接收到節(jié)點(diǎn)i的功率為Pij，則通過量化得到的距離信息dij為

這里k為1～M之間的任意整數(shù)，p代表最小量化單位，當(dāng)M確定后，p是一常數(shù)經(jīng)過上面量化，Pij大的節(jié)點(diǎn)所對(duì)應(yīng)的dij值小，說明信號(hào)強(qiáng)度越大，節(jié)點(diǎn)距離越小，這與實(shí)際情況相符。量化后，將節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集C劃分成M個(gè)聚類，每個(gè)聚類里的節(jié)點(diǎn)到i的距離量化值相同。其中p由節(jié)點(diǎn)的最大發(fā)射功率和最小能識(shí)別的功率確定。

在RSSI測距中，距離越近RSSI精度越高，距離越遠(yuǎn)時(shí)由RSSI值得到的誤差則較大，因此在量化同時(shí)可以采取非均勻量化，對(duì)較近的距離采用較小的量化區(qū)間，對(duì)較遠(yuǎn)的距離則采用較大的量化區(qū)間。

考慮到算法的復(fù)雜性，文中運(yùn)用均勻量化模型，量化后的模型中傳統(tǒng)意義上的1跳由多個(gè)量化單位取代，其在某種程度上提高了算法的精確性。

其計(jì)算步驟為:(1)計(jì)算節(jié)點(diǎn)與每個(gè)錨節(jié)點(diǎn)的最小累計(jì)量化值。錨節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播自身位置信息和路徑序列。其中自身位置信息包括距離量化值字段，初始化為0，路徑序列只包括自身節(jié)點(diǎn)編號(hào)。接收節(jié)點(diǎn)記錄具有到每個(gè)錨節(jié)點(diǎn)的最小累計(jì)量化值，忽略來自同一個(gè)信標(biāo)節(jié)點(diǎn)的較大累計(jì)量化值的分組，同時(shí)根據(jù)RSSI用式(3)～式(5)來估計(jì)其與上一跳節(jié)點(diǎn)間的dij，計(jì)算出k值，并將結(jié)果加入到量化值字段中，通過這一方法，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都能記錄到錨節(jié)點(diǎn)的最小累計(jì)量化單位。(2)計(jì)算未知節(jié)點(diǎn)和錨節(jié)點(diǎn)的實(shí)際跳段距離。每個(gè)錨節(jié)點(diǎn)根據(jù)第一階段中記錄的其他信標(biāo)節(jié)點(diǎn)的位置信息和相距量化單位數(shù)，利用式(6)估算平均每個(gè)量化單位的實(shí)際距離

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

2.2 加權(quán)最小二乘法

引入加權(quán)最小二乘估計(jì)的方法，即根據(jù)每個(gè)信標(biāo)節(jié)點(diǎn)的位置精度，在最小二乘估計(jì)中采用不同的加權(quán)系數(shù)進(jìn)行定位計(jì)算，以提高定位精度。在一般極大似然估計(jì)法的定位過程中，其一般步驟為:已知錨節(jié)點(diǎn)1，2，3，4，…，n的坐標(biāo)分別為(x1，y1)、(x2，y2)、(x3，y3)，…，(xn，yn)，未知節(jié)點(diǎn)A的坐標(biāo)為(x，y)。則根據(jù)空間坐標(biāo)計(jì)算

實(shí)際應(yīng)用中，加權(quán)系數(shù)Wi與誤差的協(xié)方差有關(guān)。理論可以證明，當(dāng)W取測量值誤差方差矩陣的逆矩陣時(shí)可使估計(jì)誤差的方差最小，但實(shí)際應(yīng)用中如何定義加權(quán)矩陣W還有待進(jìn)一步改善。一般情況下，當(dāng)節(jié)點(diǎn)間的跳數(shù)越大時(shí)造成的誤差將越大，所以取的加權(quán)值要小一些;而當(dāng)節(jié)點(diǎn)間的跳數(shù)較小的造成的誤差會(huì)變小，所以取的加權(quán)值應(yīng)大一些。

在此引入一個(gè)加權(quán)系數(shù)Wi，利用最小二乘法可得未知節(jié)點(diǎn)的坐標(biāo)為

其中，Wi=1/hi，hi為參與定位的錨節(jié)點(diǎn)距離未知節(jié)點(diǎn)A的最小跳數(shù)，則

2.3 仿真與比較

為檢驗(yàn)改進(jìn)算法的性能，在Matlab平臺(tái)上對(duì)傳統(tǒng)DV－Hop定位算法和改進(jìn)算法進(jìn)行性能仿真對(duì)比分析，對(duì)算法的性能主要從定位誤差方面進(jìn)行評(píng)估。仿真實(shí)驗(yàn)網(wǎng)絡(luò)模型的主要參數(shù)如下:網(wǎng)絡(luò)規(guī)模是100個(gè)節(jié)點(diǎn)，隨機(jī)分布在100 m×100 m的地域范圍內(nèi)，未知節(jié)點(diǎn)的坐標(biāo)隨機(jī)產(chǎn)生，節(jié)點(diǎn)的通信半徑為16 m，量化最大等級(jí)為4。每種算法的仿真進(jìn)行100次，取其定位誤差的平均值，其兩種算法的定位誤差隨著參與定位的錨節(jié)點(diǎn)個(gè)數(shù)變化結(jié)果如圖2所示。

圖2 定位誤差對(duì)比圖

由圖可知，隨著參與定位的錨節(jié)點(diǎn)個(gè)數(shù)的增加，其定位誤差越來越小。在錨節(jié)點(diǎn)達(dá)到20時(shí)，其定位誤差的下降率趨于平緩。在其對(duì)比中，改進(jìn)算法與DVHop相比，其誤差百分比有明顯的改善，在錨節(jié)點(diǎn)達(dá)到30時(shí)，其定位誤差減少了12%。

3 結(jié)束語

針對(duì)無線傳感器網(wǎng)絡(luò)定位中的DV－Hop定位算法中定位精度不足，提出了均勻量化模型來提高每段跳距的精度并用最小二乘法來解決定位過程中造成的累積誤差。仿真結(jié)果證明，該算法在定位精度上有了一定得提高。此處討論的算法都是停留在仿真試驗(yàn)的基礎(chǔ)上，如何在實(shí)際系統(tǒng)中實(shí)現(xiàn)，并檢驗(yàn)算法在現(xiàn)實(shí)環(huán)境中的性能表現(xiàn)也是一個(gè)急需實(shí)現(xiàn)解決的問題。

［1］WANG F B，SHI I，REN F Y.Self－localization systems and algorithms for wireless sensor networks［J］.Journal of Software，2005，16(5):857－868.

［2］NIU Y C，ZHANG S D，XU X Y，et a1.An enhanced DVHop localization algorithm for irregularly shaped sensor networks［C］.LNCS 4864，2007:694－704.

［3］SUN L M，LI J Z，CHEN Y，et a1.Wireless sensor networks［M］.Beijing:Tsinghua University Press，2005.

［4］ZHANG S G，CAO J N，CHEN J，et a1.Accurate and energy－efficient range－free localization for mobile sensor networks［J］.IEEE Transactions on Mobile Computing，2010，9(6):897－910.

［5］ 劉文遠(yuǎn)，王恩爽，陳子軍.無線傳感器網(wǎng)絡(luò)中DV－Hop定位算法的改進(jìn)［J］.小型微型計(jì)算機(jī)系統(tǒng)，2011，32(6):1071－1074.

［6］ 劉明，包亞萍，劉漢義.無線傳感器網(wǎng)絡(luò)中一種改進(jìn)的DVHop算法［J］.傳感器與儀器儀表，2009，25(4):128－129.

［7］ 王穎，石昊陽.基于DV－Hop的無線傳感器網(wǎng)絡(luò)定位算法［J］.儀表技術(shù)與傳感器，2012(4):97－99.

［8］ 張新生，趙衍靜，李海濤.基于DV－Hop定位算法的改進(jìn)與研究［J］.計(jì)算機(jī)科學(xué)，2011(2):76－78，90.