馬淑麗，趙建平

(曲阜師范大學(xué) 物理工程學(xué)院,山東 曲阜 273165)

無(wú)線傳感器網(wǎng)絡(luò)中分階段的無(wú)需測(cè)距定位算法*

馬淑麗，趙建平

(曲阜師范大學(xué) 物理工程學(xué)院,山東 曲阜 273165)

為了提高無(wú)線傳感器網(wǎng)絡(luò)中基于無(wú)需測(cè)距算法定位精度，改進(jìn)質(zhì)心算法和DV-Hop算法，定位過(guò)程分為兩個(gè)階段：第一階段在最佳通信半徑與最佳閾值下，用基于閾值的優(yōu)先質(zhì)心算法定位部分節(jié)點(diǎn)；第二階段在最佳通信半徑與最佳指數(shù)值下用DV-Hop算法定位剩余節(jié)點(diǎn)。將算法應(yīng)用在一種錨節(jié)點(diǎn)人工部署環(huán)境下，并與其他算法對(duì)比。MTLAB仿真結(jié)果表明，改進(jìn)的算法在不增加泛洪次數(shù)、計(jì)算量和網(wǎng)絡(luò)硬件成本下能提高定位精度，同時(shí)實(shí)現(xiàn)100%定位。

無(wú)線傳感器網(wǎng)絡(luò);質(zhì)心算法;DV-Hop;最小均方差; 錨節(jié)點(diǎn)部署策略

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)區(qū)域中分布著大量傳感器節(jié)點(diǎn)[1-2]，節(jié)點(diǎn)將采集到的事件傳遞到用戶，許多應(yīng)用需要知道事件發(fā)生的位置[3-5]，所以節(jié)點(diǎn)定位技術(shù)相當(dāng)重要[6]。現(xiàn)有的無(wú)線傳感器網(wǎng)絡(luò)定位算法大體分為高成本、高定位精度的基于測(cè)距算法(Range-based)和低成本、低定位精度的無(wú)需測(cè)距算法(Range-free)兩類(lèi)[7-10]?；跓o(wú)需測(cè)距算法較為實(shí)用[8,11]，其中DV-Hop(Distance Vector-Hop[6])算法是應(yīng)用最廣泛的定位算法之一[3,12-13]。

DV-Hop算法定位精度受通信半徑的影響[14]，不同通信半徑對(duì)應(yīng)不同的定位精度[11]。另外，還受網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)影響[15]，DV-Hop算法在隨機(jī)分布環(huán)境中由于平均跳距誤差大[16]、跳段距離代替直線距離[12]等定位精度較低[11,14]。為解決這些問(wèn)題，提高定位精度，許多文獻(xiàn)優(yōu)化通信半徑,減小平均跳距誤差或優(yōu)化錨節(jié)點(diǎn)分布方案等。如文獻(xiàn)[14]提出一種基于最優(yōu)通信半徑改進(jìn)的DV-Hop算法，并采用一種錨節(jié)點(diǎn)分布策略進(jìn)一步提升定位精度。文獻(xiàn)[11]提出錨節(jié)點(diǎn)雙通信半徑定位算法。文獻(xiàn)[16-18]修正錨節(jié)點(diǎn)平均每跳距離，定位節(jié)點(diǎn)加權(quán)處理平均每跳距離。文獻(xiàn)[15,19]用最小均方差準(zhǔn)則求平均每跳距離。在一些應(yīng)用中，錨節(jié)點(diǎn)可以固定在區(qū)域中某位置[20-21]。文獻(xiàn)[2,22]指出錨節(jié)點(diǎn)的均勻部署能提高定位精度。文獻(xiàn)[19]將其改進(jìn)的算法應(yīng)用在錨節(jié)點(diǎn)人工均勻部署的環(huán)境中。文獻(xiàn)[23]提出最小均方差準(zhǔn)則下的最佳指數(shù)值求平均每跳距離，并將其應(yīng)用在一種錨節(jié)點(diǎn)人工部署的環(huán)境中。文獻(xiàn)[24]提出一種錨節(jié)點(diǎn)人工部署方案，并改進(jìn)DV-Hop算法，提高了定位精度，同時(shí)具有較強(qiáng)的穩(wěn)定性[11]。文獻(xiàn)[25]指出未知節(jié)點(diǎn)周?chē)腻^節(jié)點(diǎn)能構(gòu)成等邊三角形頂點(diǎn)時(shí)定位誤差最小。文獻(xiàn)[26]提出錨節(jié)點(diǎn)部署在小區(qū)域的幾何中心時(shí)可大大提高DV-Hop算法定位精度。優(yōu)化的錨節(jié)點(diǎn)部署方式可以大大提高定位性能[14]，缺點(diǎn)是增加了人工負(fù)擔(dān)，對(duì)有些應(yīng)用難以實(shí)現(xiàn)[11]。

文獻(xiàn)[27]先選擇合適的錨節(jié)點(diǎn)進(jìn)行初始定位，然后用迭代算法優(yōu)化節(jié)點(diǎn)位置，精確定位的節(jié)點(diǎn)升級(jí)錨節(jié)點(diǎn)，參與下一階段定位。文獻(xiàn)[28]指出所有錨節(jié)點(diǎn)參與定位時(shí)誤差不是最小，參與定位的錨節(jié)點(diǎn)與未知節(jié)點(diǎn)位置越近定位精度越高，并設(shè)定閾值限制參與定位的錨節(jié)點(diǎn)個(gè)數(shù)。本文結(jié)合上述文獻(xiàn)，改進(jìn)基于無(wú)需測(cè)距的定位算法，在一種錨節(jié)點(diǎn)人工部署的環(huán)境中，提出分兩個(gè)階段定位：第一階段用基于閾值的優(yōu)先質(zhì)心定位算法，用閾值限制參與定位的錨節(jié)點(diǎn)個(gè)數(shù)，找出最佳閾值下最佳通信半徑，優(yōu)先定位部分節(jié)點(diǎn)；第二階段在最佳通信半徑下，求出最佳指數(shù)值，用最佳指數(shù)值下的DV-HOP算法定位剩余節(jié)點(diǎn)，最終實(shí)現(xiàn)100%定位。

1 算法概述

1.1 質(zhì)心算法

質(zhì)心算法(Centroid)，是一種基于無(wú)需測(cè)距的定位算法[2,13]，由南加利福尼亞大學(xué)Nirupama Bulusu等人提出[29]。節(jié)點(diǎn)坐標(biāo)定位在其一跳范圍內(nèi)錨節(jié)點(diǎn)的幾何中心[30]，如下式：

(1)

式中，(x,y)是未知節(jié)點(diǎn)坐標(biāo)，(xi,yi)是定位節(jié)點(diǎn)周?chē)惶嚯x錨節(jié)點(diǎn)i的坐標(biāo)，n是定位節(jié)點(diǎn)周?chē)惶嚯x錨節(jié)點(diǎn)的個(gè)數(shù)。

在無(wú)線傳感器網(wǎng)絡(luò)區(qū)域中，未知節(jié)點(diǎn)一般隨機(jī)分布。由于未知節(jié)點(diǎn)可能在區(qū)域的任何位置，質(zhì)心算法定位誤差會(huì)很大[31-32]。本文將區(qū)域劃分為較小的區(qū)域，在較小的交叉區(qū)域[33]內(nèi)實(shí)現(xiàn)質(zhì)心定位。

1.2 DV-Hop算法

DV-Hop定位算法是由美國(guó)羅格斯大學(xué)(Rutgers University)Dragos Niculescu提出的6種分布式定位算法之一[3，22]。

定位過(guò)程[2，8，13]分為4階段：

Step1 錨節(jié)點(diǎn)以泛洪方式向網(wǎng)絡(luò)傳播自身位置信息和初始跳數(shù)值0。接收節(jié)點(diǎn)將錨節(jié)點(diǎn)位置信息和跳數(shù)值保留下來(lái)，并將跳數(shù)值加1轉(zhuǎn)發(fā)出去。在多次轉(zhuǎn)發(fā)過(guò)程中，接收節(jié)點(diǎn)保留錨節(jié)點(diǎn)的位置信息和最小跳數(shù)值。當(dāng)接收到的跳數(shù)值小于自己保留的跳數(shù)值，則更新跳數(shù)值。當(dāng)接收到的跳數(shù)值大于自己保留的跳數(shù)值，則拋棄接收到的跳數(shù)值。最后，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)知道所有錨節(jié)點(diǎn)的位置信息和與所有錨節(jié)點(diǎn)的最小跳數(shù)值。

Step2 錨節(jié)點(diǎn)根據(jù)到其他錨節(jié)點(diǎn)的實(shí)際位置信息和跳數(shù)值，計(jì)算自己的平均每跳距離。

有兩種方法[15]：一種方法是，根據(jù)無(wú)偏估計(jì)準(zhǔn)則計(jì)算平均每跳距離：

(2)

另一種方法是基于最小均方誤差準(zhǔn)則計(jì)算平均每跳距離：

(3)

式中，dHopi是錨節(jié)點(diǎn)i到其他錨節(jié)點(diǎn)的平均每一跳距離。hij是錨節(jié)點(diǎn)i，j間的最小跳數(shù)。xi，yi是錨節(jié)點(diǎn)i坐標(biāo)值，xj，yj是錨節(jié)點(diǎn)j坐標(biāo)值。dij是錨節(jié)點(diǎn)i、j間的距離。大多數(shù)文獻(xiàn)使用第一種方法，文獻(xiàn)[15]指出第二種方法更合理。本文采用第二種方法。

Step3 錨節(jié)點(diǎn)將平均每跳距離作為校正值以泛洪方式廣播出去。網(wǎng)絡(luò)中所有未知節(jié)點(diǎn)只接收第一個(gè)到達(dá)的校正值，即只保留離自己最近的錨節(jié)點(diǎn)校正值。然后，未知節(jié)點(diǎn)計(jì)算自己與每個(gè)錨節(jié)點(diǎn)的估計(jì)距離，如式(4)所示：

dmk=dHopm×hmk

(4)

式中，dmk為未知節(jié)點(diǎn)m到錨節(jié)點(diǎn)k的估計(jì)距離，dHopm為未知節(jié)點(diǎn)m的校正值，hmk為未知節(jié)點(diǎn)m到錨節(jié)點(diǎn)k的最小跳數(shù)值。

Step4 當(dāng)未知節(jié)點(diǎn)得到與3個(gè)以上錨節(jié)點(diǎn)[2]的估計(jì)距離后，代入式(5)，用多邊測(cè)量法定位[4]。最終得到未知節(jié)點(diǎn)的估算坐標(biāo)。

(5)

AX=b

(6)

(7)

(8)

(9)

式中，di是未知節(jié)點(diǎn)與錨節(jié)點(diǎn)i間的估算距離，x，y是未知節(jié)點(diǎn)估計(jì)坐標(biāo)值，xi，yi是錨節(jié)點(diǎn)i坐標(biāo)值，n是錨節(jié)點(diǎn)個(gè)數(shù)。X為未知節(jié)點(diǎn)的估算坐標(biāo)陣。

1.3 錨節(jié)點(diǎn)人工部署策略

不同的應(yīng)用環(huán)境對(duì)應(yīng)不同的節(jié)點(diǎn)部署策略，如文獻(xiàn)[4]應(yīng)用在河流監(jiān)測(cè)環(huán)境中，節(jié)點(diǎn)分布呈帶狀。許多應(yīng)用(如農(nóng)業(yè)監(jiān)測(cè)、環(huán)境檢測(cè)等)在二維環(huán)境中, 錨節(jié)點(diǎn)位置固定已知或有GPS等設(shè)備能自定位，未知節(jié)點(diǎn)隨機(jī)分布(如飛機(jī)撒落[6])。文獻(xiàn)[34]指出基于無(wú)需測(cè)距的DV-Hop定位算法的定位精度受限于網(wǎng)絡(luò)中節(jié)點(diǎn)分布的均勻性。文獻(xiàn)[35]研究了圓形區(qū)域內(nèi)節(jié)點(diǎn)分布均勻性對(duì)定位精度的影響，并在其提出的圓形均勻分布環(huán)境中用3種無(wú)需測(cè)距的算法仿真。

文獻(xiàn)[24]提出了一種均勻二維錨節(jié)點(diǎn)分布方式：利用歐式范數(shù)，根據(jù)式(9)推導(dǎo)出相對(duì)定位誤差最小時(shí)，其錨節(jié)點(diǎn)分布滿足下式：

(10)

文獻(xiàn)[26]提出的環(huán)境：將正方形區(qū)域劃分為大小相同的小正方形，每個(gè)小正方形內(nèi)切圓中心放置1個(gè)錨節(jié)點(diǎn)，其他未知節(jié)點(diǎn)隨機(jī)分布，并將其提出的錨節(jié)點(diǎn)部署策略與其他文獻(xiàn)對(duì)比，證明有一定優(yōu)勢(shì)

2 應(yīng)用環(huán)境與改進(jìn)定位算法

2.1 應(yīng)用環(huán)境

經(jīng)研究，文獻(xiàn)[26]提出的部署方式更能提高DV-Hop算法的定位精度。本文考慮將質(zhì)心定位算法應(yīng)用在其環(huán)境中。并研究質(zhì)心算法在文獻(xiàn)[26]環(huán)境下的定位規(guī)律。

2.2 第一階段：基于最佳閾值的優(yōu)先質(zhì)心算法

當(dāng)未知節(jié)點(diǎn)的優(yōu)先值大于閾值(yu)時(shí)，該未知節(jié)點(diǎn)可參與第一階段定位，否則參與第二階段定位。優(yōu)先值，指未知節(jié)點(diǎn)在其通信范圍內(nèi)即一跳錨節(jié)點(diǎn)的個(gè)數(shù)。參與第一階段定位的未知節(jié)點(diǎn)，將其滿足閾值的周?chē)^節(jié)點(diǎn)坐標(biāo)信息，代入式(1)求自身坐標(biāo)值。

若網(wǎng)絡(luò)中錨節(jié)點(diǎn)個(gè)數(shù)為n，則閾值可設(shè)為0～n之間的任何整數(shù)。經(jīng)研究，不同的閾值和不同通信半徑對(duì)應(yīng)不同的定位精度。本文在實(shí)際應(yīng)用前，先根據(jù)實(shí)際環(huán)境建立仿真，求出最佳閾值和最佳通信半徑。將仿真出的最佳閾值和最佳通信半徑用到本文算法第一階段，求出部分節(jié)點(diǎn)的坐標(biāo)。

2.3 第二階段：最佳指數(shù)下DV-Hop

基于最小均方誤差準(zhǔn)則計(jì)算平均每跳距離如式(3)所示。文獻(xiàn)[23]改進(jìn)式(3)中分母hij的指數(shù)，精化錨節(jié)點(diǎn)i的平均每一跳距離dHopi，如式(11)。提出在不同錨節(jié)點(diǎn)覆蓋率和不同通信半徑下取1.9到2.0范圍內(nèi)最佳指數(shù)值時(shí)，能提高DV-Hop算法定位精度。

(11)

首先根據(jù)剩余節(jié)點(diǎn)仿真DV-Hop算法，找出最佳閾值和最佳通信半徑下對(duì)應(yīng)的最佳指數(shù)值α。第二階段將最佳指數(shù)值α帶入式(11)求平均每跳距離，并用DV-Hop定位剩余節(jié)點(diǎn)。經(jīng)研究發(fā)現(xiàn)在一定的節(jié)點(diǎn)個(gè)數(shù)與通信半徑下，α的取值范圍可擴(kuò)大到1.7～2.0，使DV-Hop算法用式(11)求平均每跳距離比用式(2)、式(3)求平均每跳距離定位精度要高。

2.4 將上述3種方法結(jié)合

本文算法定位步驟：

首先，準(zhǔn)備工作——仿真應(yīng)用環(huán)境，計(jì)算最佳值工作。仿真第一、第二階段求最佳閾值，最佳通信半徑、最佳指數(shù)值。

然后，實(shí)際定位。選取最佳通信半徑的節(jié)點(diǎn)，按照文獻(xiàn)[26]節(jié)點(diǎn)部署方式將節(jié)點(diǎn)分布在網(wǎng)絡(luò)區(qū)域。第一階段：1.錨節(jié)點(diǎn)以泛洪方式向網(wǎng)絡(luò)發(fā)送自身位置信息和初始跳數(shù)值。接收節(jié)點(diǎn)保留信息，并將跳數(shù)值加1后轉(zhuǎn)發(fā)。多次轉(zhuǎn)發(fā)過(guò)程中，接收節(jié)點(diǎn)只更新比自己先前保留的較小的跳數(shù)值，當(dāng)接收到比自己先前保留的跳數(shù)值大的則不更新。最終，每個(gè)節(jié)點(diǎn)存有與所有錨節(jié)點(diǎn)間的最小跳數(shù)值和所有錨節(jié)點(diǎn)的坐標(biāo)值。2.用基于閾值的優(yōu)先質(zhì)心算法先定位部分節(jié)點(diǎn)，閾值取最佳值。未知節(jié)點(diǎn)根據(jù)保留的與錨節(jié)點(diǎn)的最小跳數(shù)值，計(jì)算優(yōu)先值(即求一跳的錨節(jié)點(diǎn)個(gè)數(shù))，然后判斷優(yōu)先值是否大于閾值，若大于閾值，則未知節(jié)點(diǎn)進(jìn)行自定位，將保留的一跳距離的錨節(jié)點(diǎn)位置信息代入式(1)計(jì)算出自身坐標(biāo)。若小于閾值，則參與第二階段定位。第二階段：錨節(jié)點(diǎn)根據(jù)收到的其他錨節(jié)點(diǎn)位置信息和跳數(shù)值，用式(11)求出自己的平均每一跳距離(α取最佳指數(shù)值)，并作為校正值以泛洪方式廣播至網(wǎng)絡(luò)。剩余未定位的節(jié)點(diǎn)，只保留第一個(gè)送達(dá)的校正值，然后將與各錨節(jié)點(diǎn)間的最小跳數(shù)值，代入式(4)求出自身與各錨節(jié)點(diǎn)間的估計(jì)距離，當(dāng)求出超過(guò)3個(gè)錨節(jié)點(diǎn)估計(jì)距離時(shí)，用多邊測(cè)量法定位。最終實(shí)現(xiàn)節(jié)點(diǎn)100%定位。

3 仿真結(jié)果分析

無(wú)需測(cè)距算法廣泛應(yīng)用在粗精度定位的應(yīng)用中，達(dá)到0.4以下即可滿足應(yīng)用[27，36，37]。本文算法考慮降低網(wǎng)絡(luò)成本、減小節(jié)點(diǎn)能耗等問(wèn)題，控制定位精度在0.4以下、錨節(jié)點(diǎn)覆蓋率4%～16%以?xún)?nèi)，通信半徑13～49 m以?xún)?nèi)，網(wǎng)絡(luò)連通度6～75以?xún)?nèi)。由于節(jié)點(diǎn)分布隨機(jī)性，程序仿真100次。

3.1 應(yīng)用環(huán)境驗(yàn)證

按文獻(xiàn)[26]提出的錨節(jié)點(diǎn)部署方式， 錨節(jié)點(diǎn)覆蓋率分別取4%、9%、16%、25%、36%、49%。監(jiān)控區(qū)域邊長(zhǎng)100 m，網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)100個(gè),未知節(jié)點(diǎn)隨機(jī)分布。將質(zhì)心算法、DV-Hop算法在兩種錨節(jié)點(diǎn)部署方式下進(jìn)行對(duì)比。

如圖1所示，錨節(jié)點(diǎn)均勻部署下的質(zhì)心算法比錨節(jié)點(diǎn)隨機(jī)部署下的質(zhì)心算法和DV-Hop算法定位精度高。在錨節(jié)點(diǎn)均勻部署的環(huán)境下，質(zhì)心定位算法比DV-Hop算法占優(yōu)勢(shì)。說(shuō)明文獻(xiàn)[26]錨節(jié)點(diǎn)部署方式更適于質(zhì)心定位算法。

圖1 質(zhì)心算法和DV-HOP算法在兩種環(huán)境下對(duì)比

定位精度(Accuracy)指網(wǎng)絡(luò)中全部節(jié)點(diǎn)(N個(gè))的平均定位誤差與節(jié)點(diǎn)通信半徑R的比值，值越小說(shuō)明定位精度越高，計(jì)算如式(12)所示:

(12)

3.2 仿真第一階段

在不同的通信半徑、不同的閾值、不同的錨節(jié)點(diǎn)覆蓋率下仿真本文算法第一階段，求出錨節(jié)點(diǎn)覆蓋率分別為4%、9%、16%時(shí)，較優(yōu)的閾值范圍和較優(yōu)的通信半徑范圍。

3.2.1 錨節(jié)點(diǎn)覆蓋率4%

當(dāng)錨節(jié)點(diǎn)覆蓋率4%時(shí)，仿真基于閾值的優(yōu)先質(zhì)心定位算法和DV-Hop定位算法。為確保第一階段定位節(jié)點(diǎn)數(shù)大于0，且第一階段算法比DV-Hop算法定位精度更占優(yōu)勢(shì)，多次試驗(yàn)，得出本文第一階段仿真的較優(yōu)的閾值范圍和較優(yōu)的通信半徑范圍為圖2中對(duì)應(yīng)的范圍，其中不同的閾值對(duì)應(yīng)不同的較優(yōu)通信半徑范圍。

如圖2(a)所示，在一定通信半徑范圍內(nèi)，基于閾值的優(yōu)先質(zhì)心算法比DV-Hop算法定位精度要高。閾值為3時(shí)，基于閾值的優(yōu)先質(zhì)心算法定位精度與DV-Hop曲線重合。

在不同的閾值和不同的通信半徑下基于閾值的優(yōu)先質(zhì)心算法定位節(jié)點(diǎn)數(shù)不同，如圖2(b)所示，閾值越大定位節(jié)點(diǎn)數(shù)越少。

(a)DV-HOP算法和基于閾值的優(yōu)先質(zhì)心算法

(b)基于閾值的優(yōu)先質(zhì)心定位節(jié)點(diǎn)數(shù)

3.2.2 錨節(jié)點(diǎn)覆蓋率9%

同理，當(dāng)錨節(jié)點(diǎn)覆蓋率9%時(shí)，閾值取0～5，通信半徑范圍26～49 m，較優(yōu)的閾值范圍和較優(yōu)的通信半徑范圍為圖3中對(duì)應(yīng)的范圍，不同的閾值對(duì)應(yīng)不同的較優(yōu)通信半徑范圍，且閾值越大定位節(jié)點(diǎn)數(shù)越少。

(a)基于閾值的優(yōu)先質(zhì)心算法和DV-HOP算法

(b)基于閾值的優(yōu)先質(zhì)心定位節(jié)點(diǎn)數(shù)

3.2.3 錨節(jié)點(diǎn)覆蓋率16%

錨節(jié)點(diǎn)覆蓋率16%時(shí),閾值取0～9，通信半徑范圍13～49 m，基于閾值的優(yōu)先質(zhì)心定位算法定位精度占優(yōu)勢(shì)，且閾值越大定位節(jié)點(diǎn)數(shù)越少，如圖4所示。

(a)基于閾值的優(yōu)先質(zhì)心算法和DV-HOP算法yu=0～3

(b)基于閾值的優(yōu)先質(zhì)心算法和DV-HOP算法yu=4～9

(c)基于閾值的優(yōu)先質(zhì)心定位節(jié)點(diǎn)數(shù)

3.3 仿真第二階段

將第一階段用基于閾值的優(yōu)先質(zhì)心算法，第二階段用式(2)求錨節(jié)點(diǎn)平均跳距的DV-Hop算法用Range-free(A)表示。將第一階段用基于閾值的優(yōu)先質(zhì)心算法，第二階段用式(11)求錨節(jié)點(diǎn)平均跳距的DV-Hop算法(α范圍取1.7～2.1)用Range-free(B)表示。在錨節(jié)點(diǎn)覆蓋率4%、9%、16%下，分別仿真較優(yōu)閾值、較優(yōu)通信半徑范圍內(nèi)的兩種算法，找出最佳閾值、最佳通信半徑和最佳指數(shù)。

3.3.1 錨節(jié)點(diǎn)覆蓋率4%

如圖5所示，錨節(jié)點(diǎn)覆蓋率4%，閾值yu為1時(shí)，Range-free(B)算法定位精度最高為0.33，比Range-free(A)算法定位精度提升3%，此時(shí)通信半徑R為44 m，指數(shù)值eq為1.83。閾值yu為2時(shí)，定位精度最高為0.319，比Range-free(A)算法定位精度提升6%，此時(shí)通信半徑R為46m，指數(shù)值eq為1.78。得出，錨節(jié)點(diǎn)覆蓋率為4%時(shí)，最佳閾值為2，最佳通信半徑為46m，最佳指數(shù)值為1. 78。

(b)yu=2

3.3.2 錨節(jié)點(diǎn)覆蓋率9%、16%

同理，錨節(jié)點(diǎn)覆蓋率為9%時(shí)，Range-free(B)算法最佳閾值為5，最高定位精度0.25，比Range-free(A)算法定位精度提升0.17%，最佳通信半徑49 m，最佳指數(shù)值1.935，如圖6(a)所示。錨節(jié)點(diǎn)覆蓋率為16%時(shí)，最佳閾值為5，最高定位精度0.2193，比Range-free(A)算法定位精度提升3.42%，最佳通信半徑35 m，最佳指數(shù)值1.93，如圖6(b)所示。

(a)n=9% yu=5

(b)n=16% yu=5

3.4 本文算法

如表1所示，本文算法在3種錨節(jié)點(diǎn)覆蓋率下最高定位精度(AC)分別比DV-Hop算法定位精度(AC)提升36%、9.3%、8.5%。

表1 本文算法最高定位精度與DV-Hop算法定位精度

在相同的節(jié)點(diǎn)個(gè)數(shù)、通信半徑、網(wǎng)絡(luò)連通度、錨節(jié)點(diǎn)覆蓋率下，將本文算法Range-free(B)與其它算法對(duì)比。錨節(jié)點(diǎn)隨機(jī)部署下的DV-Hop算法用Range-free(S)表示，錨節(jié)點(diǎn)隨機(jī)部署下最佳指數(shù)值的DV-Hop算法用Range-free(SE)表示，錨節(jié)點(diǎn)均勻部署的DV-Hop用Range-free(J)表示，錨節(jié)點(diǎn)均勻部署下最佳指數(shù)值的DV-Hop算法用Range-free(JE)表示。錨節(jié)點(diǎn)覆蓋率4%、9%時(shí)，本文算法取最佳閾值，在一定的通信半徑范圍內(nèi)，取對(duì)應(yīng)的最佳指數(shù)值，如圖7(a)、圖7 (b)所示，定位精度比其它算法高。錨節(jié)點(diǎn)覆蓋率為16%時(shí)，在較優(yōu)的閾值范圍內(nèi)，取對(duì)應(yīng)的最佳通信半徑和最佳指數(shù)值，如圖7(c)所示，本文算法定位精度也比其它算法高。

(a)4% yu=2

(b)9% yu=5

(c)16%

4 結(jié) 語(yǔ)

首先驗(yàn)證了質(zhì)心算法適于一種錨節(jié)點(diǎn)人工部署環(huán)境，然后提出了改進(jìn)的基于無(wú)需測(cè)距的算法，將定位分為兩個(gè)階段，第一階段改進(jìn)質(zhì)心算法定位部分節(jié)點(diǎn)，第二階段改進(jìn)DV-Hop算法定位剩余節(jié)點(diǎn)。錨節(jié)點(diǎn)個(gè)數(shù)為4時(shí)，本文算法比DV-Hop算法提高定位精度36%，使基于無(wú)需測(cè)距的定位算法在較低的錨節(jié)點(diǎn)個(gè)數(shù)下，能應(yīng)用到一般的粗精度定位中。錨節(jié)點(diǎn)覆蓋率9%、16%時(shí)定位精度比DV-Hop算法分別提升9.3%、8.5%。優(yōu)點(diǎn)是在不增加網(wǎng)絡(luò)硬件成本、泛洪次數(shù)和計(jì)算量下能提高定位精度，實(shí)現(xiàn)100%定位，缺點(diǎn)是采用人工部署錨節(jié)點(diǎn)的方式增加了人力負(fù)擔(dān)。下一步將研究基于多通信半徑的無(wú)需測(cè)距定位算法，進(jìn)一步提升定位精度。

[1] LIU Jin-long, WU Zhi-lu, YIN Zhen-dong.An Improved Location Algorithm in Wireless Sensor Network[C]. Optoelectronics and Microelectronics (ICOM), 2013 International Conference on. IEEE(Sept2013)255-258.

[2] Gayan S; Dias D. Improved Dv-hop Algorithm Through Anchor Position Re-Estimation[C]. Wireless and Mobile, 2014 IEEE Asia Pacific Conference on. (Aug 2014)126-131.

[3] WANG, CHEN, An Improved DV-Distance Localization Algorithm for Wireless Sensor Networks[C]. Advanced Computer Control (ICACC), 2010 2nd International Conference on .IEEE, March 2010 , Volume 5 ,472-476.

[4] HOU Shou-feng, ZHOU Xiao-jia, LIU Xin-xin. A Novel DV-Hop Localization Algorithm for Asymmetry Distributed Wireless Sensor Networks[C].Computer Science and Information Technology (ICCSIT) Conference (Volume:4 ), IEEE(July 2010)243-248.

[5] Hadir A, Zine-Dine K, Bakhouya M, El Kafi J. An Improved DV-Hop Localization Algorithm for Wireless Sensor Networks[C]. Next Generation Networks and Services (NGNS), 2014 Fifth International Conference on. IEEE(May2014)330-334.

[6] DAI Ying, WANG Jian-ping, ZHANG Chong-wei. Improvement of DV-Hop Localization Algorithms for Wireless Sensor Networks[C].Wireless Communications Networking and Mobile Computing(WiCOM),2010 6th International Conference on.IEEE,Sept2010,1-4.

[7] Kirci P, Chaouchi H, Laouiti A. Wireless Sensor Networks and Efficient Localisation[C]. Future Internet of Things and Cloud (FiCloud), 2014 International Conference on. IEEE, Aug 2014, 98-100.

[8] CHANG Xiao-hui, LUO Xiong. An Improved Self-Localization Algorithm for Ad Hoc Network based on Extreme Learning Machine[C].Intelligent Control and Automation (WCICA),2014 11th World Congress on.IEEE,2014,564-569.

[9] ZHANG Shu-zhen, LI Shan-cang. A Distributed Self-Localization Algorithm for Wireless Sensor Networks[C].Computer Engineering and Technology (ICCET), 2010 2nd International Conference on. IEEE, April 2010, Volume 6,197-200.

[10] 李彬,王文杰,殷勤業(yè)等.一種利用天線旋轉(zhuǎn)的無(wú)線傳感器網(wǎng)絡(luò)定位算法[J].西安交通大學(xué)學(xué)報(bào),2011, 45(04):60-66. LI Bin, WANG Wen-jie, YIN Qin-ye. A Localization Method Using Rotary Antennas in Wireless Sensor Networks[J].Journal of Xi′an Jiaotong University, 2011,45(04)：60-66.

[11] 李娟,劉禹,錢(qián)志鴻.基于雙通信半徑的傳感器網(wǎng)DV-Hop定位算法[J].吉林大學(xué)學(xué)報(bào):工學(xué)版，2014,44(02)：502-507. LI Juan, LIU Yu, QIAN Zhi-hong. Improved DV-Hop Localization Algorithm based on Two Communication Ranges for Wireless Sensor Network[J]. Journal of Jilin University (Engineering and Technology Edition),2014,44(02):502-507.

[12] LI Chang-yu, ZHAO Pei-zhe, YU Zeng. Improved DV-Hop Localization Algorithm for Wireless Nodes in the Smart Grid[C]. Control and Decision Conference (2014 CCDC), the 26th Chinese，IEEE, 2014, 4535-4540.

[13] HU Juan, JIANG Min-lan. An Improved Node Localization Algorithm in Wireless Sensor Network[C]. Advanced Research and Technology in Industry Applications (WARTIA), 2014 IEEE Workshop on, Sept 2014, 398-401.

[14] 吳玉成,李江雯.基于最優(yōu)節(jié)點(diǎn)通信半徑的改進(jìn)DV-Hop定位算法[J].華南理工大學(xué)學(xué)報(bào):自然科學(xué)版,2012, 40(06):37-42. WU Yu-cheng,LI Jiang-wen.Improved DV-Hop Localization Algorithm based on Optimal Communication Radius of Nodes [J].Journal of South China University of Technology(Natural Science Edition),2012,40 (06):37-42.

[15] 嵇瑋瑋,劉中.定位算法在隨機(jī)傳感器網(wǎng)絡(luò)中的應(yīng)用研究[J].電子與信息學(xué)報(bào)，2008,30(04)：970-974. JI Wei-wei, LIU Zhong. Study on the Application of DY-Hop Localization Algorithms to Random Sensor Networks[J]. Journal of Electronics & Information Technology，2008,30(04)：970-974.

[16] YUAN Bing, YU Zhen, LU Hong-fei, SHU Bing. The Optimization Research of Node Localization Algorithm based on Wireless Sensor Network[C].Biomedical Engineering and Informatics (BMEI), 2014 7th International Conference on.IEEE,Oct.2014,929-934.

[17] BAO Xi-rong, BAO Fu-peng, ZHANG Shi, LIU Lei. An Improved DV-Hop Localization Algorithm for Wireless Sensor Networks[C]. Wireless Communications Networking and Mobile Computing (WiCOM),2010 6th International Conference on. IEEE,Sept2010, 1-4.

[18] 林金朝,陳曉冰,劉海波.基于平均跳距修正的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)迭代定位算法[J].通信學(xué)報(bào)，2009,30(10)：107-113. LIN Jin-zhao, CHEN Xiao-bing, LIU Hai-bo. Iterative Algorithm for Locating Nodes in WSN based on Modifying Average Hopping Distances[J]. Journal on Communications, 2009,30(10)：107-113.

[19] 魏全瑞,劉俊,韓九強(qiáng).改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)無(wú)偏距離估計(jì)與節(jié)點(diǎn)定位算法[J].西安交通大學(xué)學(xué)報(bào),2014,48(06):1-6. WEI Quan-rui, LIU Jun, HAN Jiu-qiang. An Improved DV-hop Node Localization Algorithm based on Unbiased Estimation for Wireless Sensor Networks[J]. Journal of Xi′an Jiaotong University,2014,48(06):1-6.

[20] Gayan S,Dias D. Novel Enhancements for Node Localization in Wireless Sensor Networks[C]. Information and Automation for Sustainability (ICIAfS),2014 7th International Conference on.IEEE, Dec2014,1-7.

[21] Hadir A,Zine-Dine K,Bakhouya M,El Kafi J. An Optimized DV-Hop Localization Algorithm Using Average Hop Weighted Mean in WSNs [C].Codes, Cryptography and Communication Systems (WCCCS), 2014 5th Workshop on. IEEE,Nov2014,25-29.

[22] FANG Wang-sheng,YANG Guang-yu.Improvement based on DV-Hop Localization Algorithm of Wireless Sensor Network[C].Mechatronic Science, Electric Engineering and Computer(MEC),2011 International Conference on.IEEE,Aug 2011,2421-2424.

[23] 馬淑麗,趙建平.無(wú)線傳感器網(wǎng)絡(luò)中DV-Hop定位算法的改進(jìn)[J].通信技術(shù),2015,48(07):840-844. MA Shu-li,ZHAO Jian-ping.The Improvement of DV-Hop Algorithm in Wirless Sensor Networks[J]. Communications Technology, 2015, 48(07):840-844.

[24] ZHENG You-si, WAN Lei,SUN Zhi,et al.A Long Range DV-Hop Localization Algorithm with Placement Strategy in Wireless Sensor Networks[C].Wireless Communications, Networking and Mobile Computing, 2008. WiCOM ′08. 4th International Conference on.IEEE,Oct 2008,1-5.

[25] 劉瑾.無(wú)線傳感器網(wǎng)絡(luò)定位算法的研究及應(yīng)用[D].南京:南京航空航天大學(xué):25-27. LIN Jin. Research and Application of Wireless Sensor Network Localization Algorithm[D].Nanjing: Nanjing University of Aeronautics and Astronautics, 25-27.

[26] 馬淑麗,趙建平,張炳婷等.WSN中節(jié)點(diǎn)定位方法的改進(jìn)[J].通信技術(shù),2015,48(04):453-457. MA Shu-li,ZHAO Jian-ping,ZHANG Bing-ting,et al.Improvement of Node Locating Algorithm in WSN[J].Communications Technology,2015,48(04):453-457.

[27] 王翥,郝曉強(qiáng),王玲.基于錨節(jié)點(diǎn)選擇的無(wú)線傳感器網(wǎng)絡(luò)定位算法[J].計(jì)算機(jī)研究與應(yīng)用，2010,47(S)：31-34. WANG Zhu,HAO Xiao-qiang,WANG Ling.Choice of Location-based Anchor Node Localization Algorithm for Wireless Sensor Networks[J]. Journal of Computer Research and Development,2010, 47(S)：31-34.

[28] 申鉉京,李成岳,王碩.基于最優(yōu)錨節(jié)點(diǎn)的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法[J].吉林大學(xué)學(xué)報(bào):工學(xué)版,2011,41 (S1):208-214. SHEN Xuan-jing,LI Cheng-yue,WANG Shuo.Localization Algorithm based on Optimal Nodes for Wireless Sensor Networks[J]. Journal of Jilin University (Engineering and Technology Edition),2011,41(S1):208-214.

[29] (德)達(dá)爾吉,(美)玻爾拉伯爾.無(wú)線傳感器網(wǎng)絡(luò)基礎(chǔ)理與實(shí)踐[M].孫利民等譯.北京：清華大學(xué)出版社，2014. (Germany) Dargie W,(America) Poellabaure C. The Wireless Sensor Network Basic Theory and Practice [M]. SUN M L Translation. Qinghua University Press, 2014.

[30] 楊新宇,孔慶茹,戴湘軍.一種改進(jìn)的加權(quán)質(zhì)心定位算法[J].西安交通大學(xué)學(xué)報(bào),2010,44(08):1-4. YANG Xin-yu,KONG Qing-ru,DAI Xiang-jun.An Improved Weighted Centroid Location Algorithm[J].Journal of Xi′an Jiaotong University,2010,44(08):1-4.

[31] XIE Shao-guo,HU Yan-jun,WANG Yi. Weighted Centroid Localization for Wireless Sensor Networks[C]. Consumer Electronics-China,2014 IEEE International Conference on.April 2014,1-4.

[32] 閆斌,周小佳,王厚軍等.無(wú)線傳感器網(wǎng)絡(luò)功率控制的質(zhì)心定位算法[J].電子科技大學(xué)學(xué)報(bào)，2010,39(03)：416-419. YAN Bin,ZHOU Xiao-jia,WANG Hou-jun,et al.Centroid Localization Algorithm based on Power Control in Wireless Sensor Networks[J]. Journal of University of Electronic Science and Technology of China，2010,39(03)：416-419.

[33] CHEN Liang-yin,LI Miao,LIU Kai.Distributed Range-Free Localisation Algorithm for Wireless Sensor Networks[J].Electronics Letters, IET Journals & Magazines,2014, 50(12): 894-896.

[34] 李新春,王曉明.節(jié)點(diǎn)分布對(duì)無(wú)線傳感器節(jié)點(diǎn)定位性能的影響[J].計(jì)算機(jī)工程與應(yīng)用.http://www.cnki. net/kcms/detail/11.2127.TP.20150116.1123.017.html, 2015-1-16. LI Xin-chun,WANG Xiao-ming. Node Distribution Effect on the Performance of Wireless Sensor Node Localization [J]. Computer Engineering and Applications.http: //www.cnki. net /kcms/ detail / 11.2127.TP. 2015 0116.1123.017.html, 2015-1-16.

[35] 宮娜娜,武海艷.傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分布均勻性與定位性能的關(guān)系[J].電子測(cè)量技術(shù)，2014，37(12):80-85. GONG Na-na,WU Hai-yan. The Relationship Between the Sensor Network Node Distribution Uniformity and Positioning Performance[J].Electronic Measurement Technology, 2014,37(12):80-85.

[36] 江禹生,馮硯毫,管芳等.無(wú)線傳感網(wǎng)非測(cè)距三維節(jié)點(diǎn)定位算法[J].西安電子科技大學(xué)學(xué)報(bào):自然科學(xué)版,2012,39(05):140-147. JIANG Yu-sheng,FENG Yan-hao,GUAN Fang,et al.Range-Free Three-Dimensional Node Location Algorithm for the Wireless Sensor Network[J].Journal of Xidian University,2012,39(05):140-147.

[37] 周正.無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)自定位技術(shù)[J].中興通信技術(shù)，2005,11(04):51-56. ZHOU Zheng.Self-Localization Technologies for Wireless Sensor Network Nodes[J].ZTE Communications,2005,11(04):51-56.

A Range-Free Localization Algorithm in Stages for Wireless Sensor Network

MA Shu-li，ZHAO Jian-ping

(College of Physics Engineering ，Qufu Normal University ， Qufu Shandon 273165，China )

In order to optimize the rang-free algorithm in wireless sensor network, the centroid algorithm and DV-Hop algorithm are improved, and the positioning process is divided into two stages: the first stage, under the optimal communication radius and optimal threshold, with threshold-based priority centroid localization algorithm for locating parts of nodes; the second stage, in the best communication radius and the best index value with DV hop positioning algorithm for locating the remaining nodes. The algorithm is applied to an anchor node artificial deployment environment and compared with other algorithms. MTLAB simulation results show that the improved algorithm can enhance the positioning accuracy without any increase of flooding times, and achieve 100% positioning, without any increase of network-hardware cost.

wireless sensor network; centroid localization algorithm; DV-Hop; least mean square error criterion; anchor node deployment strategy

2015-04-05；

2015-07-25 Received date:2015-04-05；Revised date：2015-07-25

國(guó)家自然科學(xué)基金(No.11302118)；山東省自然科學(xué)基金(No.ZR2014FM011)；山東省高等學(xué)?？萍加?jì)劃(No.J12LN08)

Foundation Item:National Natural Science Foundation of China(No.11302118);National Natural Science Foundation of Shandong Province(No. ZR2014FM011); Science and Technology Project of Higher Education of Shandong Province(No.J12LN08)

TP393

A

1002-0802(2015)09-1044-09

10.3969/j.issn.1002-0802.2015.09.013

馬淑麗(1989—)，女，碩士研究生，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)、無(wú)線通信技術(shù)；

趙建平(1964—)，男，教授，主要研究方向?yàn)闊o(wú)線通信技術(shù)。