基于可靠信標(biāo)和節(jié)點度估計距離的無線傳感器網(wǎng)絡(luò)定位算法

錢開國 卜春芬 王玉見 申時凱

摘 要：針對經(jīng)典的DV-Hop、Amorphous等免測距無線傳感器網(wǎng)絡(luò)（WSN）定位算法信標(biāo)節(jié)點選擇不可靠、距離模糊和距離估計不準(zhǔn)確等問題導(dǎo)致定位精度低，難以適應(yīng)傳感器節(jié)點分布不均勻應(yīng)用的情況，提出了基于可靠信標(biāo)和節(jié)點度估計距離的無線傳感器網(wǎng)絡(luò)定位算法（RDLA）。首先，通過跳數(shù)閾值和定位三角可靠度計算來選擇引入誤差小的信標(biāo)節(jié)點;然后，利用節(jié)點度感知的距離估計方法計算單跳距離以解決距離模糊問題，在累積最小跳數(shù)路徑（SHP）距離并修正使估計的最小跳數(shù)路徑距離更準(zhǔn)確;最后用雙曲線定位方法提高定位精度。Matlab R2012a仿真結(jié)果表明：在節(jié)點均勻分布的應(yīng)用中，RDLA的平均定位誤差（ALE）比DV-Hop算法及其改進算法小;在節(jié)點非均勻和具有覆蓋洞的C型分布的應(yīng)用中，與DV-Hop算法及其改進算法相比，RDLA的ALE顯著降低，幾乎控制在28%以下。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò);免測距;節(jié)點分布;平均定位誤差

中圖分類號： TP391

文獻標(biāo)志碼：A

文章編號：1001-9081（2019）03-0817-07

Abstract： Traditional DV-Hop localization algorithm and Amorphous algorithm for Wireless Sensor Network （WSN） can not meet practical application with lower localization accuracy due to defects of colinearity of beacons， range ambiguity and the distance error caused by path deviation. Especially， in the node heterogeneously distributed application scenario， the problem becomes more serious. So， a Reliable beacon-based and Density-aware distance Localization Algorithm for WSN （RDLA） was proposed to improve localization accuracy. Firstly， hop threshold and reliability function of approximate equilateral triangle were employed to select the beacon nodes with small error to avoid collinear problem. Secondly， node density-aware hop distance estimation method was used to solve range ambiguity problem， and distances were cumulatived along the Shortest Hop Path （SHP） from unknown node to three beacons. This distance was amended to straight-line distance. Finally， two-dimensional hyperbolic calculation method was adopted to determine locations of unknown nodes and improve node location accuracy. The extensive simulation results by Matlab R2012a show that the Average Localization Error （ALE） of RDLA is lower than that of DV-Hop algorithm and its improvement algorithms in node uniform distribution network. Remarkably， RDLA is tremendously superior to the others with the lowest ALE in node non-uniform distribution network and C shape network， in which， the ALE is almost controlled below 28%.

Key words： Wireless Sensor Network （WSN）; range-free; node distribution; Average Localization Error （ALE）

0 引言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network， WSN） [1]是由部署在任務(wù)區(qū)域的大量傳感器節(jié)點通過自組織方式構(gòu)建的信息采集網(wǎng)絡(luò)，可應(yīng)用到健康護理、智能家居、戰(zhàn)場監(jiān)控、環(huán)境監(jiān)測、目標(biāo)跟蹤等廣闊領(lǐng)域中，是當(dāng)前的研究熱點。在大多數(shù)的應(yīng)用中，傳感器節(jié)點必須明確自身位置才能詳細(xì)說明“在什么位置或區(qū)域發(fā)生了特定事件”，實現(xiàn)對外部目標(biāo)的定位和追蹤[2]，但由于傳感器節(jié)點自身低功耗、微型化、資源有限等特點使得不可能給規(guī)模巨大的傳感器節(jié)點都配置全球定位系統(tǒng)（Global Positioning System， GPS）設(shè)備，必須為無傳感器網(wǎng)絡(luò)設(shè)計適用的節(jié)點位置獲取技術(shù)，即傳感器網(wǎng)絡(luò)節(jié)點定位。按照定位時所需的距離獲取方式，已有的定位方法主要分為基于測距（Range-based）的定位算法和免測距（Range-free）的定位算法兩種[3]?；跍y距的定位算法通過測量未知位置節(jié)點和信標(biāo)節(jié)點間的距離或方位角度，然后使用三邊測量法或三角測量法計算節(jié)點位置，經(jīng)典算法包括接收信號的強度指示（Received Signal Strength Indicator， RSSI）[4]、到達時間（Time-of-Arrival， TOA）[5]、到達時間差（Time Difference of Arrival， TDOA）[6]、到達角度（Angle of Arrival， AOA）[7]。這類算法需要傳感器網(wǎng)絡(luò)節(jié)點裝配硬件測量模塊，通過傳感器節(jié)點間信號參數(shù)來測量距離，測距精度受到信號衰減、多徑效應(yīng)影響，同時增大了傳感器節(jié)點的功耗。免測距的定位算法使用網(wǎng)絡(luò)節(jié)點間的拓?fù)溥B接關(guān)系來估計節(jié)點間的距離，然后采用多邊或者極大似然估計完成節(jié)點定位，經(jīng)典的定位算法包括DV-Hop（Distance Vector Hop）[8]、Amorphous algorithm[9]、質(zhì)心（Centroid）[10]定位算法、APIT（Approximate Point-In-Triangulation test）[11]。免測距定位算法不需要硬件支持，實現(xiàn)成本較低，功耗低，更適合資源受限的傳感器網(wǎng)絡(luò)應(yīng)用;但以DV-Hop、Amorphous為代表的免測距定位算法存在距離模糊、最小跳路徑偏離、信標(biāo)節(jié)點共線等問題導(dǎo)致距離估計誤差大，定位精度低。尤其在非均勻分布的應(yīng)用場景中，距離估計誤差更大，致使定位精度難以達到應(yīng)用要求，而在傳感器網(wǎng)絡(luò)實際應(yīng)用中，部署方式和障礙物使得節(jié)點分布多呈現(xiàn)非均勻分布，因此，在詳細(xì)分析DV-Hop、Amorphous定位算法的基礎(chǔ)上，本文根據(jù)節(jié)點分布提出了基于可靠信標(biāo)和節(jié)點度估計距離的無線傳感器網(wǎng)絡(luò)定位算法（Reliable beacon-based and Density-aware distance Localization Algorithm for WSN， RDLA），降低免測距算法定位誤差，并使其適用于節(jié)點非均方分布的應(yīng)用中。

1 DV-Hop算法和相關(guān)研究

DV-Hop算法根據(jù)信標(biāo)節(jié)點估計的平均跳距和節(jié)點間的跳數(shù)估算未知位置節(jié)點到信標(biāo)節(jié)點的距離，然后利用極大似然估計法或最小二乘法計算出節(jié)點位置坐標(biāo)。

1.1 DV-Hop定位算法

DV-Hop算法定位過程可分成三個階段。首先，信標(biāo)節(jié)點廣播信息分組給鄰居節(jié)點，該信息分組包括信標(biāo)節(jié)點ID、位置坐標(biāo)pi（xi，yi）、初始化為0的跳數(shù)hops。鄰居節(jié)點收到該數(shù)據(jù)分組后，將跳數(shù)參數(shù)hops加1，保存并向鄰居節(jié)點以廣播方式轉(zhuǎn)發(fā)。接收節(jié)點收到來自同一信標(biāo)節(jié)點的位置信息，則保留跳數(shù)最小的信息分組，使得每個節(jié)點（包括信標(biāo)節(jié)點）均保存了到所有信標(biāo)節(jié)點的最小跳數(shù)和信標(biāo)節(jié)點的位置信息。其次信標(biāo)節(jié)點si按式（1）計算以自己為根的平均每跳距離（Average Hop Size， AHS）：

其中：hopsij是節(jié)點i到節(jié)點j的最小跳數(shù)，m是網(wǎng)絡(luò)中部署的信標(biāo)節(jié)點總數(shù)，然后信標(biāo)節(jié)點將AHSi值廣播給未知位置節(jié)點，通過節(jié)點存儲轉(zhuǎn)發(fā)，未知位置節(jié)點保存了每個信標(biāo)節(jié)點的最小跳數(shù)和平均每跳距離AHS。未知位置節(jié)點從最近的信標(biāo)處獲得自身為根的平均每跳距離，用該平均每跳距離與最小跳數(shù)相乘就估算出未知定位節(jié)點到每個信標(biāo)節(jié)點的距離。最后，未知位置節(jié)點利用極大似然估計法或最小二乘法計算自身的位置坐標(biāo)。

1.2 相關(guān)算法分析

圍繞定位精度的提高，研究人員提出了一些改進機制。文獻[12]在經(jīng)典DV-Hop算法計算出平均每跳距離AHS后，利用信標(biāo)節(jié)點間的跳數(shù)與AHS相乘，估算出信標(biāo)節(jié)點間的距離，利用估計距離與信標(biāo)節(jié)點間的真實距離差值去除信標(biāo)節(jié)點跳數(shù)和，可計算出平均每跳距離估計誤差，從而修正平均跳距AHS，最后使用二維雙曲線計算方法完成節(jié)點定位。文獻[13]中提出一種加權(quán)處理平均每跳距離估算方法，根據(jù)到信標(biāo)節(jié)點的跳數(shù)對多個信標(biāo)節(jié)點的估計跳距進行加權(quán)處理，使網(wǎng)絡(luò)平均每跳距離更為準(zhǔn)確。文獻[14]從采用最小二乘法校正信標(biāo)節(jié)點的平均每跳距離、未知位置節(jié)點對收到的信標(biāo)節(jié)點的平均每跳距離進行加權(quán)處理、在位置坐標(biāo)估計時進行迭代求精等三項措施提高定位精度。文獻[15]引入多通信半徑方法細(xì)化節(jié)點間的跳數(shù)，在計算未知位置節(jié)點平均每跳距離時，剔除孤立節(jié)點，并利用信標(biāo)節(jié)點得到的平均每跳距離進行加權(quán)歸一化處理，來提高定位精度。文獻[16]對接收到的多個信標(biāo)節(jié)點平均每跳距離進行加權(quán)求和來減小平均每跳距離的誤差，并且利用改進的最小二乘法來解決誤差累積的問題。這些算法通過優(yōu)化跳距計算，降低距離估計誤差從而提高定位精度。Regulated neighborhood distance-based localization[17]算法使用了節(jié)點公共鄰居數(shù)作為距離估計因子，距離估計較為精確，但當(dāng)節(jié)點間跳數(shù)較大、最小跳路徑偏離嚴(yán)重時，距離估計誤差也會增大。Selective3-Anchor DV-Hop[18]用未知位置節(jié)點到信標(biāo)節(jié)點間的跳數(shù)作為向量，應(yīng)用向量差異最小為標(biāo)準(zhǔn)選擇出三個最佳的信標(biāo)節(jié)點完成未知位置節(jié)點定位，算法的距離估計仍使用DV-Hop的距離估計方法，孤立信標(biāo)節(jié)點、大跳數(shù)信標(biāo)節(jié)點也有機會成為參考節(jié)點。Rendered path[19]算法計算出渲染路徑和直線距離的角度，從而計算出未知位置節(jié)點到信標(biāo)節(jié)點的距離，提出了有效的、具有覆蓋空洞的傳感器網(wǎng)絡(luò)的節(jié)點定位算法。Hop Count based Decomposition DV-Hop （HCD-DV-Hop）[20]通過傳感器網(wǎng)絡(luò)子區(qū)域劃分，來降低DV-Hop算法在傳感器網(wǎng)絡(luò)非均勻分布時的定位誤差，但如何劃分子區(qū)域在分布較為復(fù)雜的傳感器網(wǎng)絡(luò)應(yīng)用中難以確定。Improved Weighted Centroid DV-Hop （IWC-DV-Hop）[21]首先設(shè)定距離閾值來選擇信標(biāo)節(jié)點，去除大跳數(shù)不可靠節(jié)點，這些信標(biāo)節(jié)點引入誤差較大，然后使用信標(biāo)節(jié)點的AHS和未知位置節(jié)點跳數(shù)相乘來估計距離，該距離和跳數(shù)作為因子，計算每個信標(biāo)節(jié)點的權(quán)值，使用加權(quán)質(zhì)心算法完成未知位置節(jié)點定位。文獻[22]利用移動信標(biāo)節(jié)點輔助定位，提高定位精度，在定位過程中，需要規(guī)劃信標(biāo)節(jié)點的移動軌跡。

1.3 誤差來源分析

免測距定位算法DV-Hop存在3個缺陷，引入定位誤差。

1.3.1 路徑偏離和距離模糊問題

免測距算法在距離計算時，采用最小跳路徑跳數(shù)與估算出的平均每跳距離相乘。這種距離計算方法首先用兩節(jié)點間最小跳路徑上的跳段距離替代節(jié)點直線路徑跳數(shù)，在覆蓋洞、分布不均勻等網(wǎng)絡(luò)應(yīng)用中，最小跳路徑嚴(yán)重偏離直線路徑時，將引入較大的距離估計誤差，即出現(xiàn)路徑偏離問題。如圖1（a）所示，節(jié)點對u、v之間的最小跳路徑為u-c-d-e-f-g-v，跳數(shù)hops為6;直線路徑為u-h-v，跳數(shù)hops為2。

另外，同一節(jié)點，其外圍分布的節(jié)點，如果距其跳數(shù)hops相同，則其估計距離相同，稱為距離模糊問題。如圖1（b）所示，信標(biāo)節(jié)點z的1-hops鄰居節(jié)點u、v、w被估計到z的距離相同，實際上u和w相差近節(jié)點通信半徑r的距離。

1.3.2 共線問題

未知位置節(jié)點定位時，至少需要選擇3個信標(biāo)節(jié)點作為參考節(jié)點。如果選擇的3個信標(biāo)節(jié)點共線或逼近共線時，引入巨大的定位誤差。如圖2所示，陰影區(qū)域為未知位置節(jié)點u可能的定位位置，如圖2（a）所示，3個信標(biāo)節(jié)點近正三角形分布時，定位誤差較小;而如圖2（b）、（c）逼近共線分布時，如果被定位到u′陰影區(qū)域，引入的定位誤差較大。

2 可靠信標(biāo)和節(jié)點度估計距離的改進算法

首先設(shè)計跳數(shù)閾值來限制大跳數(shù)節(jié)點參與定位，形成候選信標(biāo)節(jié)點集，再用近正三角形選擇函數(shù)選擇最佳分布的3個信標(biāo)節(jié)點;其次，使用節(jié)點度來估計每個節(jié)點單跳距離，累積最小跳路徑距離并修正該距離;最后采用雙曲線定位計算完成節(jié)點定位，從而使DV-Hop算法在傳感器網(wǎng)絡(luò)應(yīng)用中保持了較小的定位誤差，具有較高的定位精度，同時也適用于非均勻分布的傳感器網(wǎng)絡(luò)應(yīng)用。

2.1 拓?fù)湫畔⒔粨Q

信標(biāo)節(jié)點i生成元數(shù)據(jù)，包含自身序號、位置信息字段和跳數(shù)字段，即（id，xi，yi，hops）的四元組，其中，hops字段的初始值為0，向周圍鄰居節(jié)點廣播出去，鄰居節(jié)點接收該元數(shù)據(jù)后，將hops字段值加1，然后以泛洪方式廣播出去，每個接收節(jié)點如果收到來自同一信標(biāo)節(jié)點的元數(shù)據(jù)，則只保留hops字段值較小的元組數(shù)據(jù);同時未知位置節(jié)點生成最小跳數(shù)查詢元數(shù)據(jù)，包括自身序號和跳數(shù)字段，即（id，hops）的二元組，同信標(biāo)節(jié)點一樣的方式在全網(wǎng)內(nèi)泛洪。通過拓?fù)湫畔⒔粨Q，每個節(jié)點（包括信標(biāo)節(jié)點）都記錄了到其他節(jié)點所需要的最小跳數(shù)值。根據(jù)該跳數(shù)值hops（i），可構(gòu)建全網(wǎng)的最小跳數(shù)路徑拓?fù)浣Y(jié)構(gòu)。根據(jù)該拓?fù)浣Y(jié)構(gòu)，每個節(jié)點均可生成以自己為根的最小路徑生成樹。

2.2 信標(biāo)節(jié)點選擇

隨機部署的無線傳感器網(wǎng)絡(luò)，傳感器網(wǎng)絡(luò)節(jié)點的分布服從泊松分布[23]，在區(qū)域A內(nèi)分布的k個傳感器網(wǎng)絡(luò)節(jié)點概率密度函數(shù)為：

其中：λ=N/S為節(jié)點密度，N傳感器節(jié)點數(shù)，S為監(jiān)測區(qū)域面積。

因此，在未知位置節(jié)點u的n跳區(qū)域內(nèi)分布的平均信標(biāo)節(jié)點個數(shù)為：

其中r為傳感器節(jié)點通信半徑。

未知位置節(jié)點u完成定位，至少需要選擇3個信標(biāo)節(jié)點作為參考節(jié)點，則有：

即可求出未知位置節(jié)點最少取到3個信標(biāo)節(jié)點的最近的n跳信標(biāo)節(jié)點作為參考節(jié)點完成定位，即：

n3=UP-integer（1r3λπ）（5）UP-integer是一個函數(shù)名，還是UP減去integer？請明確

為了避免選擇的3個信標(biāo)節(jié)點共線或者逼近共線，充分利用網(wǎng)絡(luò)中部署其余信標(biāo)節(jié)點約束產(chǎn)生距離模糊問題。設(shè)網(wǎng)絡(luò)監(jiān)測區(qū)域直徑為D，網(wǎng)絡(luò)中存在的最大跳數(shù)為：

則取未知位置節(jié)點u的k跳鄰居信標(biāo)節(jié)點形成候選參考節(jié)點集：

2.3 lg（u）的距離估計

2.3.1 u到3個未知位置節(jié)點的距離估計

2.3.2 距離修正

信標(biāo)節(jié)點選擇完成后，定位單元lg（u）的分布有2種情況，u位于3個信標(biāo)節(jié)點構(gòu)成的三角形內(nèi)部和u在信標(biāo)節(jié)點構(gòu)成的三角形外部，分別如圖4（a）和圖4（b）所示。

2.4 節(jié)點定位

3 實驗結(jié)果與分析

為了驗證算法的有效性，使用Matlab R2012a，在1000m×1000m的任務(wù)區(qū)域部署300個傳感器節(jié)點，傳感器節(jié)點在任務(wù)區(qū)域呈均勻隨機分布、非均勻分布和C型節(jié)點分布三種應(yīng)用場景中進行仿真實驗，實驗拓?fù)淙鐖D5所示。

將信標(biāo)節(jié)點比例設(shè)置為10%～45%，步長增長為5%，節(jié)點通信半徑設(shè)置為150～290m，步長增長為20m，兩個參數(shù)變化上，對經(jīng)典的DV-Hop算法、改進Improved DV-Hop （I-DV-Hop）算法[12]、IWC-DV-Hop[21]和本文改進算法RDLA定位性能進行實驗對比分析。用網(wǎng)絡(luò)的平均定位誤差（Average Localization Error， ALE）比較考察算法的定位性能。平均相

3.1 節(jié)點均勻分布

圖6是在節(jié)點均勻隨機分布的場景中，信標(biāo)節(jié)點比例和通信半徑變化時，4種算法的平均相對定位誤差結(jié)果。

從圖6可以看出，隨著信標(biāo)節(jié)點比例和通信半徑的增加，4種算法的定位誤差均呈整體下降趨勢。從圖6（a）可以看出，經(jīng)典的DV-Hop算法的定位精度從信標(biāo)節(jié)點比例為10%的31.7%下降到信標(biāo)節(jié)點比例為60%時的29%，改進算法I-DV-Hop從信標(biāo)節(jié)點比例為10%時的28.9%下降到信標(biāo)節(jié)點比例為60%時的24.8%，IWC-DV-Hop算法從31.5%下降到23%，而RDLA從信標(biāo)節(jié)點比例為10%時的21.8%下降到信標(biāo)節(jié)點比例為60%時的20.2%。總體上看，除了IWC-DV-Hop算法外，信標(biāo)節(jié)點比例的提高對定位誤差的影響不是很大，這是因為在節(jié)點均勻分布時，DV-Hop、改進算法I-DV-Hop和本文RDLA在跳距和距離估計時，最小跳路徑基本靠近節(jié)點間直線路徑，跳距估計和距離估計較為精確，只要滿足有3個信標(biāo)節(jié)點，定位就會比較準(zhǔn)確，所以信標(biāo)節(jié)點比例影響較小;而IWC-DV-Hop算法使用了閾值限制選擇信標(biāo)節(jié)點下的加權(quán)質(zhì)心算法，信標(biāo)節(jié)點數(shù)越多，可選擇更加靠近未知位置節(jié)點的信標(biāo)節(jié)點執(zhí)行加權(quán)質(zhì)心定位，精度就愈高。4種算法中，DV-Hop算法定位誤差最高;改進算法I-DV-Hop平均跳距修正和雙曲線定位計算方法提高了距離估計準(zhǔn)確度和降低了計算誤差，從而減少了定位誤差;IWC-DV-Hop的加權(quán)質(zhì)心定位計算方法在信標(biāo)節(jié)點數(shù)較多時，獲得了較高的定位精度;而本文RDLA通過正三角函數(shù)選擇可靠信標(biāo)，避免信標(biāo)節(jié)點共線引入的誤差，采用基于節(jié)點度的單跳距離估計和最小跳路徑距離累積和修正的方法使距離估計接近節(jié)點間的直線距離，并用雙曲線定位計算降低計算誤差，從而獲得最高的定位精度，且只要滿足3個信標(biāo)節(jié)點定位條件，信標(biāo)節(jié)點個數(shù)對定位誤差影響就很小。在實際應(yīng)用中，就可以部署較少的信標(biāo)節(jié)點來降低網(wǎng)絡(luò)成本。

從圖6（b）可以看出，隨著節(jié)點通信半徑提高，節(jié)點度提高，網(wǎng)絡(luò)連通性越來越好，4種算法的定位誤差均下降。經(jīng)典的DV-Hop定位誤差從41%減小到30.5%，改進算法I-DV-Hop從35.4%減小到27%，IWC-DV-Hop從41%降低到28%。本文的RDLA基于節(jié)點度的距離估計，減輕了距離模糊問題的影響，所以，定位性能最好，定位誤差從25.6%減小到21%左右。

3.2 非均勻分布

節(jié)點非均勻分布應(yīng)用場景按照圖5（b）完成節(jié)點部署，設(shè)置信標(biāo)節(jié)點比例和通信半徑兩個參數(shù)，定位誤差結(jié)果如圖7所示。

隨著信標(biāo)節(jié)點比例從10%增加到50%，經(jīng)典DV-Hop算法的定位誤差從36.5%降低到32%，改進算法I-DV-Hop在30%左右波動，IWC-DV-Hop算法從37.5%降低到24.5%。隨著信標(biāo)節(jié)點比例增加，IWC-DV-Hop算法的閾值控制下信標(biāo)節(jié)點選擇機制選出引入誤差下的信標(biāo)節(jié)點機會大幅度增加，尤其是信標(biāo)節(jié)點比例達到30%以后，其定位誤差就開始低于26%;而本文RDLA由于近似正三角的信標(biāo)節(jié)點選擇、基于節(jié)點度的單跳距離估計和最小跳數(shù)路徑距離修正保證距離估計準(zhǔn)確。只要能選擇到3個非共線節(jié)點，定位就比較精確，所以信標(biāo)節(jié)點比例影響較小，定位誤差幾乎維持在24.5%左右，遠低于其余三種算法。

隨著通信半徑從150增加到290，4種算法的定位誤差均降低，DV-Hop從42%降低到33%，改進算法I-DV-Hop從44%降低到29%，IWC-DV-Hop從37%降低到28%，而本文RDLA幾乎維持在25%左右，定位精度較高。

對比圖6和圖7，從節(jié)點均勻分布到非均勻分布，4種算法的定位誤差均升高，DV-Hop和改進算法I-DV-Hop升高最大。IWC-DV-Hop在信標(biāo)節(jié)點比例較小時升高較大，但信標(biāo)節(jié)點比例提高時升高較少。而本文RDLA升高最小，在非均勻分布時，也獲得較高的定位精度，說明本文算法基于節(jié)點度的距離估估計和修正在節(jié)點非均勻分布時，距離估計也較為準(zhǔn)確。

3.3 C型分布

按照圖5（c）的應(yīng)用場景完成節(jié)點部署，該節(jié)點部署方式存在覆蓋洞，節(jié)點間的最小跳數(shù)路徑存在嚴(yán)重彎曲，遠偏離節(jié)點間的直線路徑。

從圖8可以看出：隨著信標(biāo)節(jié)點比例和通信半徑的增加，經(jīng)典的DV-Hop、改進算法I-DV-Hop算法定位誤差有呈降低趨勢，但由于最小跳路徑偏離嚴(yán)重，距離估計非常不準(zhǔn)確，引入的定位誤差較大，達80%以上，難以滿足定位精度的應(yīng)用要求。而IWC-DV-Hop算法基于閾值完成信標(biāo)節(jié)點選擇后，再對信標(biāo)節(jié)點到未知位置節(jié)點間的跳數(shù)路徑距離進行修正后使用質(zhì)心算法完成節(jié)點定位，所以定位誤差相比前兩個算法，改進較大，而隨著信標(biāo)節(jié)點比例的增加，信標(biāo)節(jié)點比例為10%，定位誤差最大，在50%;當(dāng)信標(biāo)節(jié)點在15%時，定位誤差就下降到40%以下;隨著信標(biāo)節(jié)點比例的增加，定位誤差進一步減小。本文RDLA的距離估計方法，始終比較準(zhǔn)確，獲得的定位誤差也最小，無論信標(biāo)節(jié)點是否增加，維持在28%左右，遠低于其他三種算法。

隨著節(jié)點通信半徑的增加，4種定位算法的定位誤差均降低。整體來看，DV-Hop和改進算法I-DV-Hop算法定位誤差也非常大，大于65%;IWC-DV-Hop算法大于40%;而本文算法維持在28%左右，定位誤差最小，定位精度最高。

綜合圖6～8來看，隨著節(jié)點分布非均勻程度的增加，4種算法的定位誤差均升高，但是DV-Hop、改進算法I-DV-Hop定位誤差升高最大，存在有覆蓋洞的極端情況C型分布中，定位誤差非常大，難以滿足定位精度要求;IWC-DV-Hop定位誤差升高次之，在非均勻分布和C型分布時，隨著信標(biāo)節(jié)點比例和通信半徑的增加，定位誤差增加較小。而本文RDLA，近似正三角形的信標(biāo)節(jié)點選擇避免了共線引入誤差，基于節(jié)點度的單跳距離估計減輕了距離模糊問題，而最小跳數(shù)路徑距離估計和修正使距離估計使得無論在節(jié)點怎么分布時，距離估計都非常準(zhǔn)確，所以隨著節(jié)點分布非均勻度增長，定位誤差盡管有所增加，但始終保持在28%以下，定位精度較高。

4 結(jié)語

針對傳統(tǒng)的DV-Hop算法及其改進算法中存在的信標(biāo)節(jié)點共線或近似共線、距離模糊和距離估計不準(zhǔn)確等問題，在無線傳感器網(wǎng)絡(luò)節(jié)點分布較為均勻、節(jié)點密度較高的應(yīng)用場景中，引入誤差小，定位精度滿足應(yīng)用要求。當(dāng)無線傳感器網(wǎng)絡(luò)節(jié)點分布不均勻，甚至存在覆蓋洞等應(yīng)用場景中，引入較大的定位誤差，難以滿足定位精度要求。本文引入基于跳數(shù)閾值和近正三角形信標(biāo)節(jié)點選擇避免信標(biāo)節(jié)點共線，去除大跳數(shù)、不可靠的信標(biāo)節(jié)點參與節(jié)點定位;并采用基于節(jié)點度的單跳距離估計緩解距離模糊問題，對最小跳數(shù)路徑累計估計并進行修正，從而保證無論節(jié)點均勻分布、非均勻分布或存在覆蓋洞分布情況下，距離估計均較為準(zhǔn)確，保持較低的定位誤差。

參考文獻 （References）

[1] AKYILDZ I.F， SU W， SANKARASUBRAMANIAM Y， et al. A survey on sensor networks[J]. IEEE Communications Magazine， 2002， 40（8）：102-114.

[2] 王福豹，史龍，任豐原.無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學(xué)報，2005，16（5）：857-867.（WANG F B， SHI L， REN F Y. Self-localization systems and algorithms for wireless sensor networks[J]. Journal of Software， 2005， 16（5）：857-867.）

[3] 曾凡仔，孫正章，羅娟，等.無線傳感器網(wǎng)絡(luò)的節(jié)點定位方法[J].通信學(xué)報，2008，29（11）：62-66.（ZENG F Z， SUN Z Z， LUO J， et al. Improved node localization algorithm for wireless sensor network[J]. Journal on Communications， 2008，29（11）：62-66.）

[4] ZHONG Z， HE T. Achieving range-free localization beyond connectivity[C]// Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems. New York： ACM， 2009：281-294.

[5] PATWARI N， HERO A O， PERKINS M， et al. Relative location estimation in wireless sensor networks[J]. IEEE Transactions on Signal Processing， 2003， 51（8）：2137-2148.

[6] GIROD L， ESTRIN D. Robust range estimation using acoustic and multimodal sensing[C]// Proceedings of the 2001 International Conference on Intelligent Robots and Systems. Piscataway， NJ： IEEE， 2001：1312-1320.

[7] LAZOS L， POOVENDRAN R. ROPE： robust position estimation in wireless sensor networks[C]// Proceedings of the 2005 International Symposium on Information Processing in Sensor Networks. Piscataway， NJ： IEEE， 2005：323-331.

[8] NICULESCU D， NATH B. DV based positioning in Ad Hoc networks[J]. Telecommunication Systems， 2003， 22（1/2/3/4）：267-280.

[9] JI W W， LIU Z. An improvement of DV-Hop algorithm in wireless sensor networks[C]// Proceedings of the 2006 International Conference on Wireless Communications， Networking and Mobile Computing. Piscataway， NJ： IEEE， 2006：1-4.

[10] 張愛清，葉新榮，胡海峰.無線傳感器網(wǎng)絡(luò)質(zhì)心定位新算法及性能分析[J].計算機應(yīng)用，2012，32（9）：2429-2431.（ZHANG A Q， YE X R， HU H F. Performance analysis of new centroid localization algorithm in wireless sensor network[J]. Journal of Computer Applications， 2012， 32（9）：2429-2431.）

[11] HE T， HUANG C， BLUM B M， et al. Range-free localization and its impact on large scale sensor networks[J]. ACM Transactions on Embedded Computing Systems， 2005， 4（4）：877-906.

[12] 石為人，賈傳江，梁煥煥.一種改進的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法[J].傳感技術(shù)學(xué)報，2011，24（1）：83-87.（SHI W R，JIA C J， LIANG H H. An improved DV-Hop localization algorithm for wireless sensor networks[J]. Chinese Journal of Sensors and Actuators， 2011，24（1）：83-87.）

[13] 劉鋒，張翰，楊驥.一種基于加權(quán)處理的無線傳感器網(wǎng)絡(luò)平均跳距離估計算法[J].電子與信息學(xué)報，2008，30（5）：1222-1225.（LIU F， ZHANG H， YANG J. An average one-hop distance estimation algorithm based on weighted disposal in wireless sensor network[J]. Journal of Electronics and Information Technology， 2008， 30（5）：1222-1225.）

[14] 林金朝，陳曉冰，劉海波.基于平均跳距修正的無線傳感器網(wǎng)絡(luò)節(jié)點迭代定位算法[J].通信學(xué)報，2009，30（10）：107-113.（LIN J Z， CHEN X B， LIU H B. Iterative algorithm for locating nodes in WSN based on modifying average hopping distances[J]. Journal on Communications， 2009，30（10）：107-113.）

[15] 景路路，張玲華.基于跳距優(yōu)化的改進型DV-Hop定位算法[J].傳感技術(shù)學(xué)報，2017，30（4）：582-586.（JING L L， ZHANG L H. An improved DV-Hop location algorithm based on hop-distance optimization [J]. Chinese Journal of Sensors and Actuators， 2017， 30（4）：582-586.）

[16] 趙芝璞，吳棟，王艷，等.基于平均跳距和位置優(yōu)化的改進DV-Hop定位算法[J].系統(tǒng)仿真學(xué)報，2016，28（6）：1273-1280.（ZHAO Z P， WU D， WANG Y， et al. Improved DV-Hop localization algorithm based on average hopping distance and position optimization[J]. Journal of System Simulation， 2016， 28（6）：1273-1280.）

[17] WU G， WANG S， WANG B， et al. A novel range-free localization based on regulated neighborhood distance for wireless Ad Hoc and sensor networks[J]. Computer Networks， 2012， 56（16）：3581-3593.

[18] GUI L， VAL T， WEI A， et al. Improvement of range-free localization technology by a novel DV-Hop protocol in wireless sensor networks[J]. Ad Hoc Networks， 2015， 24： 55-73.

[19] LI M， LIU Y H. Rendered path： range-free localization in anisotropic sensor networks with holes[J]. IEEE/ACM Transactions on Networking， 2007， 18（1）：320-332.

[20] GAO B， ZHAO X， WANG J， et al. Decomposition based localization for anisotropic sensor networks[J]. International Journal of Distributed Sensor Networks， 2015， 2015： Article No. 8.

[21] SONG G， TAM D. Two novel DV-Hop localization algorithms for randomly deployed wireless sensor networks[J]. International Journal of Distributed Sensor Networks， 2015， 2015： Article ID 187670.

[22] SABALE K， MINI S. Anchor node path planning for localization in wireless sensor networks[J]. Wireless Networks， 2017（8）：1-13.

[23] HUANG B， YU C， ANDERSON G， et al. Connectivity-based distance estimation in wireless sensor networks[C]// Proceedings of the 2010 Global Telecommunications Conference. Piscataway， NJ： IEEE， 2010：1-5.

[24] HAN G， CHOI D， LIM W. Reference node placement and selection algorithm based on trilateration for indoor sensor networks[J]. Wireless Communications & Mobile Computing， 2009， 9（8）：1017-1027.

[25] SARRATR J， PALAU J， HUERTA A. Numerical representation of the quality measures of triangles and triangular meshes[J]. International Journal for Numerical Methods in Biomedical Engineering， 2003， 19（7）：551-561.

[26] KLEIN L， SILEVESTR J. Optimum transmission radii for packet radio networks or why six is a magic number[C]// Proceedings of the 1978 IEEE National Telecommunication Conference. Piscataway， NJ： IEEE， 1978：431-435.