錢開國(guó) 卜春芬 王玉見 申時(shí)凱

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

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

中圖分類號(hào)： TP391

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

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

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

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

1.1 DV-Hop定位算法

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

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

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

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

1.3 誤差來源分析

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

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

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

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

1.3.2 共線問題

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

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

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

2.1 拓?fù)湫畔⒔粨Q

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

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

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

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

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

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

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

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

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

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

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

2.3 lg（u）的距離估計(jì)

2.3.1 u到3個(gè)未知位置節(jié)點(diǎn)的距離估計(jì)

2.3.2 距離修正

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

2.4 節(jié)點(diǎn)定位

3 實(shí)驗(yàn)結(jié)果與分析

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

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

3.1 節(jié)點(diǎn)均勻分布

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

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

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

3.2 非均勻分布

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

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

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

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

3.3 C型分布

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

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

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

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

4 結(jié)語

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

參考文獻(xià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é)報(bào)，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é)點(diǎn)定位方法[J].通信學(xué)報(bào)，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].計(jì)算機(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] 石為人，賈傳江，梁煥煥.一種改進(jìn)的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法[J].傳感技術(shù)學(xué)報(bào)，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ì)算法[J].電子與信息學(xué)報(bào)，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é)點(diǎn)迭代定位算法[J].通信學(xué)報(bào)，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)化的改進(jìn)型DV-Hop定位算法[J].傳感技術(shù)學(xué)報(bào)，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)化的改進(jìn)DV-Hop定位算法[J].系統(tǒng)仿真學(xué)報(bào)，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.