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

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

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

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

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

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

1 DV－Hop算法的定位過程

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

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

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

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

圖1 DV－Hop算法模型

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

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

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

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

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

2 DV－Hop算法的改進

2.1 均勻量化模型

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

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

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

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

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

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

2.2 加權最小二乘法

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

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

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

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

2.3 仿真與比較

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

圖2 定位誤差對比圖

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

3 結束語

針對無線傳感器網絡定位中的DV－Hop定位算法中定位精度不足，提出了均勻量化模型來提高每段跳距的精度并用最小二乘法來解決定位過程中造成的累積誤差。仿真結果證明，該算法在定位精度上有了一定得提高。此處討論的算法都是停留在仿真試驗的基礎上，如何在實際系統(tǒng)中實現，并檢驗算法在現實環(huá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］ 劉文遠，王恩爽，陳子軍.無線傳感器網絡中DV－Hop定位算法的改進［J］.小型微型計算機系統(tǒng)，2011，32(6):1071－1074.

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

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

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