基于加權雙曲線定位的DV-Hop改進算法

易仁杰，余劍，吳標，龔陽

（電子工程學院，合肥230037）

基于加權雙曲線定位的DV-Hop改進算法

易仁杰，余劍，吳標，龔陽

（電子工程學院，合肥230037）

針對基于雙曲線定位的DV-Hop算法中誤差項的異方差性引起的定位誤差大的問題，提出了一種基于加權雙曲線定位的DV-Hop改進算法。算法分析了基于雙曲線定位的DV-Hop算法模型中誤差項的異方差性，用加權最小二乘法對異方差性進行糾正，對加權最小二乘法中的權值矩陣進行了理論推導并得到與跳數(shù)相關的最佳權值矩陣，使得誤差項滿足同方差性，所得估計值接近最佳線性無偏估計。仿真結果表明，所提算法在定位精度上較目前常見的基于雙曲線定位的DV-Hop算法都有一定提高。

異方差，雙曲線定位，DV-Hop，加權最小二乘法

0 引言

無線傳感器網絡［1］是一種由大量的傳感節(jié)點通過自組織的方式構成的網絡，各傳感節(jié)點集成電源、通信、處理和傳感模塊，以單跳或多跳的方式進行無線通信，利用自身的存儲和計算能力完成整個區(qū)域中的信息采集與數(shù)據(jù)處理。伴隨無線通信技術與微機電技術的革新，無線傳感器網絡技術迅速發(fā)展，并被廣泛應用到軍事、醫(yī)療、環(huán)境監(jiān)測、空間探測等領域，深刻地影響著人們的生活［2］。由于節(jié)點的位置信息往往至關重要，各國學者針對節(jié)點定位技術展開了持續(xù)深入的研究。

目前的研究將定位算法分為基于測距［3］和非測距［4］兩類。與基于測距的定位算法相比，非測距的定位算法無需直接測距，硬件構成簡單，能量消耗低，抗干擾能力較強，同時可以達到一定的精度要求［5］。在基于非測距的定位算法中，DV-Hop［6］算法原理簡單、計算量小，硬件實現(xiàn)簡單，在節(jié)點分布均勻、各向同性的密集型網絡中具有較好的定位精度［7］，其應用最為成功和廣泛。目前針對DV-Hop算法的改進主要集中在待定位節(jié)點到錨節(jié)點之間距離的求精和根據(jù)該距離精確求解待定位節(jié)點的位置坐標兩方面。針對精確求解待定位節(jié)點的位置坐標，文獻［8］指出由極大似然估計法所求得的估計值并沒有真正滿足各誤差項的平方和最小，而是各誤差項之差的平方和最小，定位精度與參考方程精度有關；對于極大似然估計法存在的不足，文獻［9］引入雙曲線定位算法，提高了定位精度，但是沒有考慮模型中誤差項存在的異方差性對最小二乘估計精度的影響；文獻［10］在雙曲線定位算法的基礎上提出加權雙曲線定位算法，權值矩陣為待定位節(jié)點到錨節(jié)點最小跳數(shù)的倒數(shù)構成的對角陣，在一定程度上消除了模型中誤差項的異方差性，降低了定位誤差，但是文中未指明該權值矩陣是否為最佳權值矩陣且未見對該權值矩陣進行理論分析。

本文在上述研究的基礎上，提出了一種加權雙曲線定位的DV-Hop改進算法。算法分析了基于雙曲線定位的DV-Hop算法模型中誤差項的異方差性，采用加權最小二乘法對異方差性進行糾正，對加權最小二乘法中的最佳權值矩陣進行了理論推導，并根據(jù)模型中誤差求得與跳數(shù)相關的最佳權值矩陣，較好地克服了由誤差項的異方差性帶來的定位誤差大的問題，提高了節(jié)點定位精度。

1 DV-Hop算法簡介

1.1 算法基本原理

DV-Hop算法的基本原理為：根據(jù)網絡中節(jié)點之間的最小跳數(shù)以及錨節(jié)點的已知位置信息確定節(jié)點的平均每跳距離，之后由跳數(shù)與平均每跳距離確定待定位節(jié)點與各錨節(jié)點之間的距離，最后利用距離信息聯(lián)立方程求取待定位節(jié)點位置坐標。過程如下：

①使用距離矢量交換協(xié)議［11］，通過各節(jié)點間的信息交換求取任意兩節(jié)點之間的最小跳數(shù)。

②計算待定位節(jié)點到錨節(jié)點的距離。

錨節(jié)點的平均每跳距離為：

Hopsizei表示錨節(jié)點i的平均每跳距離，（xi，yi）表示錨節(jié)點i的坐標，（xj，yj）表示錨節(jié)點j的坐標，n表示錨節(jié)點數(shù)目，hij表示錨節(jié)點i與j之間的最小跳數(shù)。待定位節(jié)點u到錨節(jié)點i的距離為：

其中dui表示待定位節(jié)點u到錨節(jié)點i的距離，Hopsizeu表示距離u最近的錨節(jié)點的平均每跳距離，hui表示待定位節(jié)點u與錨節(jié)點i之間的最小跳數(shù)。

③三邊或多邊定位算法定位

根據(jù)待定位節(jié)點到錨節(jié)點的距離可以得到如下方程：

其中（x，y）表示待定位節(jié)點坐標，（xi，yi）表示錨節(jié)點坐標，ξi表示各距離坐標方程中的觀測誤差。三邊定位算法有針對性地選擇3個錨節(jié)點進行定位，多邊定位算法則利用多個錨節(jié)點進行定位，比三邊定位算法具有更高的可靠性。目前常見的多邊定位采用極大似然估計法，式（3）中各方程通過減去參考方程（此處選擇第n個方程作為參考方程）得到線性方程組如下所示：

對式（4）采用最小二乘法進行求解定位。然而當ξn較大時，參考方程的精度較低，定位誤差明顯加大。

1.2 雙曲線定位算法

1.2.1 算法基本原理

雙曲線定位算法是一種通過將待定位節(jié)點定位在以錨節(jié)點為焦點、兩錨節(jié)點之間距離為焦距的雙曲線上，根據(jù)各雙曲線之間的交點確定待定位節(jié)點坐標的多邊定位算法。文獻［9］將雙曲線定位用于DV-Hop算法中，獲得了比極大似然估計法更高的定位精度，其定位原理如下：

待定位節(jié)點u與錨節(jié)點i之間的距離為：

假設u到錨節(jié)點i的距離與到錨節(jié)點j的距離之差為rij，則有rij=dui-duj，u位于以錨節(jié)點i和j（j≠i）為焦點、到焦點距離差值為rij的雙曲線上。由式（5）可得：

令K=x2+y2，帶入誤差項后由式（6）可得：

將K、x和y看作未知數(shù)，式（7）寫成線性方程的形式為：A·c=b，其中：

由最小二乘法解得：

待定位節(jié)點坐標由式（8）可得：

其中c（2）表示列向量c的第2項，c（2）表示列向量c的第3項。

1.2.2 誤差項分析

在傳感器節(jié)點隨機均勻分布、忽略環(huán)境影響的條件下，可認為觀測誤差僅與待定位節(jié)點和錨節(jié)點之間的距離誤差有關。假設待定位節(jié)點u與錨節(jié)點i之間的估計距離與實際距離的誤差為Δdui，則Δdui等于u與i最短路徑上所有相鄰兩節(jié)點之間的距離在u與i直線方向上的投影與平均每跳距離的誤差之和。假設最短路徑上相鄰兩節(jié)點之間的距離在該直線方向上的投影與平均每跳距離的誤差相互獨立且服從零均值同方差的高斯分布，則Δdui均值為零且方差與u、i之間的最小跳數(shù)成正比。

由式（9）可知ξi具備零均值、異方差的特性。高斯馬爾柯夫定理［12］指出，在給定經典線性回歸模型［13］的假定下，最小二乘估計是最佳線性無偏估計。然而誤差ξi不滿足同方差性，此時經典線性回歸模型不成立，最小二乘估計不滿足最佳線性無偏估計，需要對誤差ξi的異方差性進行糾正，使估計接近最佳線性無偏估計，從而提高定位精度。

2 改進算法

普通的最小二乘法認為每項誤差對總體回歸直線的偏離程度全部相同，等價于權值都賦為1，各方程可信度［14］相同。然而由于模型中誤差項存在異方差性，每項誤差對總體回歸直線的偏離程度不同，此時普通最小二乘法無法確定各錨節(jié)點參與定位的可信度，得到的估計值不滿足最優(yōu)估計，因此，引入加權最小二乘法。

加權最小二乘法的思想是對原模型進行加權，對誤差項方差較大的觀測值賦予較小的權值，而對誤差項方差較小的觀測值賦予較大的權值，使之成為一個新的不存在異方差性的模型。根據(jù)式（8），加權最小二乘估計的性能指標為：

其中σ（c）表示離差平方和，W為正定的權值矩陣。式（10）最小時求得的cLSW為加權最小二乘估計量，此時估計值滿足最佳線性無偏估計，對c求偏導得到：

令式（11）為零，得到取極值時坐標：

此時估計誤差為：

當且僅當存在一個矩陣Q使得N=MTQ時，等式成立。將M和N帶入式（14）可得：

當待定位節(jié)點u與錨節(jié)點i、j不在同一直線上時，u、i之間距離誤差Δdui與u、j之間距離誤差Δduj相互獨立，因此，E{ξiξj}=0。當u與i、j在同一直線上時，由于任意相鄰兩節(jié)點之間的距離在該直線方向上的投影與平均每跳距離的誤差相互獨立并且方差相同，因此，E{ξiξj}與u、i之間的最短路徑跟u、j之間的最短路徑的重合段數(shù)成正比。而根據(jù)網絡分布特性可知，u與i、j共線概率極小，認為該重合路徑段數(shù)在絕大多數(shù)情況下為零，因此，忽略B可得：

由式（9）可得，

假設相鄰節(jié)點之間的距離誤差的方差為σ2，由于最短路徑上任意相鄰兩節(jié)點之間的距離誤差相互獨立，所以：

式（8）代入式（19）后，由式（17）可得：

所以權值矩陣化簡后為：

將式（21）代入式（12）可求出估計坐標。引入權值矩陣W后，離差平方和為：

其中wi為誤差項ξi的權系數(shù)，對應于權值矩陣W中對角線上第i個元素，則有：

由式（23）可知，引入權值矩陣后，誤差項ξi的方差與對應權系數(shù)的乘積為與i無關的常數(shù)，各誤差項在離差平方和中作用相同，方差大的誤差項不再具備更高的擬合程度，各誤差項對應的擬合程度相當。與文獻［10］提出的加權雙曲線定位算法相比，權值矩陣不再為待定位節(jié)點到錨節(jié)點最小跳數(shù)的倒數(shù)構成的對角陣，而是最小跳數(shù)倒數(shù)的三次方構成的對角陣，此時異方差性得到明顯改善，近似滿足最佳線性無偏估計。同時，由于僅增加了待定位節(jié)點與錨節(jié)點之間最小跳數(shù)的立方運算，計算復雜度基本持平。

3 仿真分析

為了對本文提出的算法進行驗證，分別對基于雙曲線定位的DV-Hop算法、文獻［10］提出的加權雙曲線算法以及本文所提的改進算法進行仿真?？紤]到隨機性帶來的定位誤差，仿真結果取自100次蒙特卡洛［15］仿真的平均值。網絡定位誤差采用歸一化之后的誤差，表達式為：

其中m表示未知節(jié)點數(shù)量，R表示節(jié)點通信半徑，（xest.u，yest.u）表示待定位節(jié)點u的估計坐標，（xtru.u，ytru.u）表示待定位節(jié)點的實際坐標。

仿真在Matlab中進行，無線傳感器網絡環(huán)境為：節(jié)點隨機均勻地分布在邊長為100的正方形區(qū)域中，節(jié)點的通信半徑為25，錨節(jié)點和待定位節(jié)點隨機產生，滿足均勻分布，其中節(jié)點總數(shù)、錨節(jié)點的比例隨著仿真的具體要求而改變。當節(jié)點總數(shù)為100、錨節(jié)點密度為20%時，無線傳感器網絡節(jié)點分布如圖1所示，其中“*”表示錨節(jié)點，實心圓點表示待定位節(jié)點。

圖1 節(jié)點分布示意圖

實驗1特定情況下算法的定位性能比較

在節(jié)點總數(shù)為100、錨節(jié)點密度為20%的條件下進行仿真，基于雙曲線定位的DV-Hop算法、文獻［10］中的算法以及本文改進算法的定位效果分別如圖2（a）、圖2（b）、圖2（c）所示，其中空心圓點表示待定位節(jié)點的估計坐標。未知節(jié)點的實際位置與估計位置由線段連接，線段越長表示定位誤差越大。圖2（d）為100次蒙特卡洛仿真取均值求得3種算法的定位效果對比圖，橫坐標表示待定位節(jié)點標號，縱坐標表示相應的待定位節(jié)點的平均定位誤差。從圖2（d）中可以看出，基于雙曲線定位的DV-Hop算法、文獻［10］提出的改進算法以及本文改進算法的定位誤差依次為30%、26%、23%，本文算法的定位誤差較前兩種算法均有所降低。

圖2 算法定位效果圖

實驗2不同節(jié)點數(shù)量情況下算法的定位性能比較

假設錨節(jié)點密度為20%，在節(jié)點總數(shù)不同的情況下分別比較本文改進算法與傳統(tǒng)雙曲線定位算法以及文獻［10］中算法之間的定位性能，得到仿真結果如圖3所示。圖中橫坐標表示網絡中節(jié)點總數(shù)，縱坐標表示歸一化之后的網絡定位誤差。隨著網絡中節(jié)點總數(shù)的增加，網絡的連通性增強，錨節(jié)點平均每跳距離更加精確，未知節(jié)點與錨節(jié)點之間的距離估算值更加接近真實值，3種算法定位誤差均減小并最終趨于穩(wěn)定。由于克服了模型中誤差項的異方差性對定位的影響，在相同條件下本文改進算法的網絡定位誤差比基于雙曲線定位的DV-Hop算法降低約7%，比文獻［10］中的算法降低約4%。

圖3 節(jié)點數(shù)量與定位誤差的關系

圖4 錨節(jié)點密度與定位誤差的關系

實驗3不同錨節(jié)點密度情況下算法的定位性能比較

假設節(jié)點總數(shù)為100，在錨節(jié)點密度不同的情況下分別比較本文改進算法與傳統(tǒng)雙曲線定位算法以及文獻［10］中算法之間的定位性能，得到仿真結果如圖4所示。圖中橫坐標表示網絡中錨節(jié)點密度，縱坐標表示歸一化之后的網絡定位誤差。在節(jié)點總數(shù)保持不變的情況下，隨著錨節(jié)點密度的增加，參與定位的錨節(jié)點數(shù)量增加，3種算法的定位誤差逐漸降低，本文所提算法定位誤差逐漸降低并最終趨于穩(wěn)定。在錨節(jié)點密度為45%時，本文改進算法網絡定位誤差為19.3%，比基于雙曲線定位的DV-Hop算法降低大約8.6%，比文獻［10］中改進算法降低約4.7%。

4 結論

本文介紹了傳統(tǒng)的基于雙曲線定位的DV-Hop算法并分析了誤差項的異方差性，針對由異方差性引起的定位誤差大的問題，提出了一種基于加權雙曲線定位的DV-Hop改進算法。算法根據(jù)網絡中節(jié)點間距離誤差與跳數(shù)之間的關系，對最佳權值矩陣進行了理論推導，得到了僅與節(jié)點間跳數(shù)相關的權值矩陣，糾正了傳統(tǒng)算法中誤差項的異方差性，使改進之后的加權最小二乘估計接近最佳線性無偏估計。仿真結果表明，與傳統(tǒng)的基于雙曲線定位的DV-Hop算法及文獻［10］中的算法相比，本文改進算法具有更高的定位精度。

［1］AKYILDIZ I F，SU W，SANKARASU Y，et al.Wireless sensor networks：a survey［J］.Computer Networks，2002，38（4）：393-422.

［2］ARAMPATZIS T，LYGEROS J，MANESIS S.A survey of applications of wireless sensors and wireless sensor networks［C］//Intelligent Control，2005.Proceedings of the 2005 IEEE InternationalSymposiumon，MediterreanConferenceon Control and Automation.IEEE，2005：719-724.

［3］BOUSHABA M，HAFID A，BENSLIMANE A.High accuracy localization method using AoA in sensor networks［J］.Computer Networks，2009，53（18）：3076-3088.

［4］CHEN M X，WANG Y D.An efficient location tracking structure for wireless sensor networks［J］.Computer Communications，2009，32（13）：1495-1504.

［5］JIAN L，HE P L.A new weighted centroid localization algorithm in coal mine wireless sensor networks［C］//Computer Research and Development（ICCRD），2011 3rd International Conference on.IEEE，2011，3：106-109.

［6］NICULESCU D，NATH B.DV based positioning in ad hoc networks［J］.Telecommunication Systems，2003，22（4）：267-280.

［7］邱奉美，游曉鵬，李懷忠.幾種無需測距定位算法定位性能仿真研究［J］.計算機仿真，2014，31（4）：285-289.

［8］鐘麗鴻，胡成全，金京姬.基于RSSI極大似然估計定位算法的分析與實現(xiàn)［J］.吉林大學學報（理學版），2014，52（3）：556-560.

［9］CHEN H，SEZAKI K，DENG P，et al.An improved DV-Hop localization algorithm for wireless sensor networks［C］//Industrial Electronics and Applications，2008.ICIEA 2008.3rd IEEE Conference on.IEEE，2008：1557-1561.

［10］吳玉成，李江雯.基于最優(yōu)節(jié)點通信半徑的改進DV-Hop定位算法［J］.華南理工大學學報（自然科學版），2012，40（6）：35-42.

［11］BULUSU N，HEIDEMANN J，ESTRIN D.GPS-less lowcost out-door localization for very small devices［T］.IEEE Personal Communications，2000，7（5）：28-34.

［12］倪偉才.高斯馬爾柯夫定理的拉格朗日證明方法［J］.統(tǒng)計與決策，2009，25（2）：153-153.

［13］何曉群，劉文卿.淺談加權最小二乘法及其殘差圖——兼答孫小素副教授［J］.統(tǒng)計研究，2006，23（4），53-57.

［14］CHUAN X.Research on improved DV-HOP localization algorithm based on weighted least square method［C］//Knowledge Acquisition and Modeling Workshop，2008.KAM Workshop 2008.IEEE International Symposium on.IEEE，2008：773-776.

［15］邵偉.蒙特卡洛方法及在一些統(tǒng)計模型中的應用［D］.濟南：山東大學，2012.

An Improved DV-Hop Algorithm Based on Weighted Hyperbolic Positioning

YI Ren-jie，YU Jian，WU Biao，GONG Yang
（Electronic Engineering Institute，Hefei 230037，China）

Aiming at solving the problem that the heteroscedasticity of observation errors leads to low locating accuracy in DV-Hop algorithm which is based on hyperbolic positioning，this paper proposes an improved DV-Hop algorithm which is based on weighted hyperbolic positioning.The algorithm analyzes the heteroscedasticity of the error term in the model and takes advantage of weighted least square method which corrects heteroscedasticity straightforwardly.Then，the weight matrix that is related to least hops between nodes is deduced，the estimators thus obtained are more close to the best linear unbiased estimator.The simulation results show that the localization performance of the improved algorithm is better than the current DV-Hop algorithm.

heteroscedasticity，hyperbolic positioning，DV-Hop，weighted least square method

TP212

A

1002-0640（2016）12-0096-05

2015-10-11

2015-12-19

易仁杰（1990-），男，湖北隨州人，碩士研究生。研究方向：無線傳感器網絡。