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

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

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

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

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

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

1 DV－Hop算法的定位過程

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

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

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

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

圖1 DV－Hop算法模型

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

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

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

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

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

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

2.1 均勻量化模型

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

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

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

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

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

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

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

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

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

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

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

2.3 仿真與比較

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

圖2 定位誤差對比圖

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

3 結(jié)束語

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