無線傳感器網絡中分階段的無需測距定位算法*

馬淑麗，趙建平

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

無線傳感器網絡中分階段的無需測距定位算法*

馬淑麗，趙建平

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

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

無線傳感器網絡;質心算法;DV-Hop;最小均方差; 錨節點部署策略

0 引 言

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

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

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

1 算法概述

1.1 質心算法

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

(1)

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

在無線傳感器網絡區域中，未知節點一般隨機分布。由于未知節點可能在區域的任何位置，質心算法定位誤差會很大[31-32]。本文將區域劃分為較小的區域，在較小的交叉區域[33]內實現質心定位。

1.2 DV-Hop算法

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

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

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

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

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

(2)

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

(3)

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

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

dmk=dHopm×hmk

(4)

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

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

(5)

AX=b

(6)

(7)

(8)

(9)

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

1.3 錨節點人工部署策略

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

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

(10)

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

2 應用環境與改進定位算法

2.1 應用環境

經研究，文獻[26]提出的部署方式更能提高DV-Hop算法的定位精度。本文考慮將質心定位算法應用在其環境中。并研究質心算法在文獻[26]環境下的定位規律。

2.2 第一階段：基于最佳閾值的優先質心算法

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

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

2.3 第二階段：最佳指數下DV-Hop

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

(11)

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

2.4 將上述3種方法結合

本文算法定位步驟：

首先，準備工作——仿真應用環境，計算最佳值工作。仿真第一、第二階段求最佳閾值，最佳通信半徑、最佳指數值。

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

3 仿真結果分析

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

3.1 應用環境驗證

按文獻[26]提出的錨節點部署方式， 錨節點覆蓋率分別取4%、9%、16%、25%、36%、49%。監控區域邊長100 m，網絡節點總數100個,未知節點隨機分布。將質心算法、DV-Hop算法在兩種錨節點部署方式下進行對比。

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

圖1 質心算法和DV-HOP算法在兩種環境下對比

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

(12)

3.2 仿真第一階段

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

3.2.1 錨節點覆蓋率4%

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

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

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

(a)DV-HOP算法和基于閾值的優先質心算法

(b)基于閾值的優先質心定位節點數

3.2.2 錨節點覆蓋率9%

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

(a)基于閾值的優先質心算法和DV-HOP算法

(b)基于閾值的優先質心定位節點數

3.2.3 錨節點覆蓋率16%

錨節點覆蓋率16%時,閾值取0～9，通信半徑范圍13～49 m，基于閾值的優先質心定位算法定位精度占優勢，且閾值越大定位節點數越少，如圖4所示。

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

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

(c)基于閾值的優先質心定位節點數

3.3 仿真第二階段

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

3.3.1 錨節點覆蓋率4%

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

(b)yu=2

3.3.2 錨節點覆蓋率9%、16%

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

(a)n=9% yu=5

(b)n=16% yu=5

3.4 本文算法

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

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

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

(a)4% yu=2

(b)9% yu=5

(c)16%

4 結 語

首先驗證了質心算法適于一種錨節點人工部署環境，然后提出了改進的基于無需測距的算法，將定位分為兩個階段，第一階段改進質心算法定位部分節點，第二階段改進DV-Hop算法定位剩余節點。錨節點個數為4時，本文算法比DV-Hop算法提高定位精度36%，使基于無需測距的定位算法在較低的錨節點個數下，能應用到一般的粗精度定位中。錨節點覆蓋率9%、16%時定位精度比DV-Hop算法分別提升9.3%、8.5%。優點是在不增加網絡硬件成本、泛洪次數和計算量下能提高定位精度，實現100%定位，缺點是采用人工部署錨節點的方式增加了人力負擔。下一步將研究基于多通信半徑的無需測距定位算法，進一步提升定位精度。

[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] 李彬,王文杰,殷勤業等.一種利用天線旋轉的無線傳感器網絡定位算法[J].西安交通大學學報,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] 李娟,劉禹,錢志鴻.基于雙通信半徑的傳感器網DV-Hop定位算法[J].吉林大學學報:工學版，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] 吳玉成,李江雯.基于最優節點通信半徑的改進DV-Hop定位算法[J].華南理工大學學報:自然科學版,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].電子與信息學報，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] 林金朝,陳曉冰,劉海波.基于平均跳距修正的無線傳感器網絡節點迭代定位算法[J].通信學報，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] 魏全瑞,劉俊,韓九強.改進的無線傳感器網絡無偏距離估計與節點定位算法[J].西安交通大學學報,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] 馬淑麗,趙建平.無線傳感器網絡中DV-Hop定位算法的改進[J].通信技術,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] 劉瑾.無線傳感器網絡定位算法的研究及應用[D].南京:南京航空航天大學: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中節點定位方法的改進[J].通信技術,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] 王翥,郝曉強,王玲.基于錨節點選擇的無線傳感器網絡定位算法[J].計算機研究與應用，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] 申鉉京,李成岳,王碩.基于最優錨節點的無線傳感器網絡節點定位算法[J].吉林大學學報:工學版,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] (德)達爾吉,(美)玻爾拉伯爾.無線傳感器網絡基礎理與實踐[M].孫利民等譯.北京：清華大學出版社，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].西安交通大學學報,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] 閆斌,周小佳,王厚軍等.無線傳感器網絡功率控制的質心定位算法[J].電子科技大學學報，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] 李新春,王曉明.節點分布對無線傳感器節點定位性能的影響[J].計算機工程與應用.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] 宮娜娜,武海艷.傳感器網絡節點分布均勻性與定位性能的關系[J].電子測量技術，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] 江禹生,馮硯毫,管芳等.無線傳感網非測距三維節點定位算法[J].西安電子科技大學學報:自然科學版,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] 周正.無線傳感器網絡的節點自定位技術[J].中興通信技術，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

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

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