馬淑麗，趙建平

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

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

馬淑麗，趙建平

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

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

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

0 引 言

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

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

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

1 算法概述

1.1 質(zhì)心算法

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

(1)

式中，(x,y)是未知節(jié)點坐標，(xi,yi)是定位節(jié)點周圍一跳距離錨節(jié)點i的坐標，n是定位節(jié)點周圍一跳距離錨節(jié)點的個數(shù)。

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

1.2 DV-Hop算法

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

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

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

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

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

(2)

另一種方法是基于最小均方誤差準則計算平均每跳距離：

(3)

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

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

dmk=dHopm×hmk

(4)

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

Step4 當未知節(jié)點得到與3個以上錨節(jié)點[2]的估計距離后，代入式(5)，用多邊測量法定位[4]。最終得到未知節(jié)點的估算坐標。

(5)

AX=b

(6)

(7)

(8)

(9)

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

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

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

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

(10)

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

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

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

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

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

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

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

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

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

(11)

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

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

本文算法定位步驟：

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

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

3 仿真結(jié)果分析

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

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

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

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

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

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

(12)

3.2 仿真第一階段

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

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

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

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

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

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

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

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

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

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

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

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

錨節(jié)點覆蓋率16%時,閾值取0～9，通信半徑范圍13～49 m，基于閾值的優(yōu)先質(zhì)心定位算法定位精度占優(yōu)勢，且閾值越大定位節(jié)點數(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é)點數(shù)

3.3 仿真第二階段

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

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

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

(b)yu=2

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

同理，錨節(jié)點覆蓋率為9%時，Range-free(B)算法最佳閾值為5，最高定位精度0.25，比Range-free(A)算法定位精度提升0.17%，最佳通信半徑49 m，最佳指數(shù)值1.935，如圖6(a)所示。錨節(jié)點覆蓋率為16%時，最佳閾值為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é)點覆蓋率下最高定位精度(AC)分別比DV-Hop算法定位精度(AC)提升36%、9.3%、8.5%。

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

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

(a)4% yu=2

(b)9% yu=5

(c)16%

4 結(jié) 語

首先驗證了質(zhì)心算法適于一種錨節(jié)點人工部署環(huán)境，然后提出了改進的基于無需測距的算法，將定位分為兩個階段，第一階段改進質(zhì)心算法定位部分節(jié)點，第二階段改進DV-Hop算法定位剩余節(jié)點。錨節(jié)點個數(shù)為4時，本文算法比DV-Hop算法提高定位精度36%，使基于無需測距的定位算法在較低的錨節(jié)點個數(shù)下，能應(yīng)用到一般的粗精度定位中。錨節(jié)點覆蓋率9%、16%時定位精度比DV-Hop算法分別提升9.3%、8.5%。優(yōu)點是在不增加網(wǎng)絡(luò)硬件成本、泛洪次數(shù)和計算量下能提高定位精度，實現(xiàn)100%定位，缺點是采用人工部署錨節(jié)點的方式增加了人力負擔(dā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ǎng)絡(luò)定位算法[J].西安交通大學(xué)學(xué)報,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] 李娟,劉禹,錢志鴻.基于雙通信半徑的傳感器網(wǎng)DV-Hop定位算法[J].吉林大學(xué)學(xué)報:工學(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é)點通信半徑的改進DV-Hop定位算法[J].華南理工大學(xué)學(xué)報:自然科學(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] 嵇瑋瑋,劉中.定位算法在隨機傳感器網(wǎng)絡(luò)中的應(yīng)用研究[J].電子與信息學(xué)報，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ǎng)絡(luò)節(jié)點迭代定位算法[J].通信學(xué)報，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] 魏全瑞,劉俊,韓九強.改進的無線傳感器網(wǎng)絡(luò)無偏距離估計與節(jié)點定位算法[J].西安交通大學(xué)學(xué)報,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ǎng)絡(luò)中DV-Hop定位算法的改進[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ǎ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é)點定位方法的改進[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] 王翥,郝曉強,王玲.基于錨節(jié)點選擇的無線傳感器網(wǎng)絡(luò)定位算法[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é)點的無線傳感器網(wǎng)絡(luò)節(jié)點定位算法[J].吉林大學(xué)學(xué)報:工學(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] (德)達爾吉,(美)玻爾拉伯爾.無線傳感器網(wǎng)絡(luò)基礎(chǔ)理與實踐[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] 楊新宇,孔慶茹,戴湘軍.一種改進的加權(quán)質(zhì)心定位算法[J].西安交通大學(xué)學(xué)報,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ǎng)絡(luò)功率控制的質(zhì)心定位算法[J].電子科技大學(xué)學(xué)報，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é)點分布對無線傳感器節(jié)點定位性能的影響[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é)點分布均勻性與定位性能的關(guān)系[J].電子測量技術(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ǎng)非測距三維節(jié)點定位算法[J].西安電子科技大學(xué)學(xué)報:自然科學(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ǎng)絡(luò)的節(jié)點自定位技術(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

國家自然科學(xué)基金(No.11302118)；山東省自然科學(xué)基金(No.ZR2014FM011)；山東省高等學(xué)校科技計劃(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—)，女，碩士研究生，主要研究方向為無線傳感器網(wǎng)絡(luò)、無線通信技術(shù)；

趙建平(1964—)，男，教授，主要研究方向為無線通信技術(shù)。