基于功率控制的無線傳感器網(wǎng)絡節(jié)點定位算法

趙志信， 郭繼坤， 彭 保

(1.黑龍江科技學院 電氣與信息工程學院，哈爾濱 150027;2.哈爾濱工業(yè)大學 通信技術(shù)研究所，哈爾濱 150080)

基于功率控制的無線傳感器網(wǎng)絡節(jié)點定位算法

趙志信1， 郭繼坤1， 彭 保2

(1.黑龍江科技學院 電氣與信息工程學院，哈爾濱 150027;2.哈爾濱工業(yè)大學 通信技術(shù)研究所，哈爾濱 150080)

針對野外大面積區(qū)域、不需要知道節(jié)點精確位置的應用場合，提出一種基于功率控制的節(jié)點定位算法。采用功率控制方式，分別由3個基站形成包含未知節(jié)點的3個圓環(huán)，通過計算由3個圓環(huán)形成的交叉區(qū)域的質(zhì)心來實現(xiàn)未知節(jié)點的定位。仿真結(jié)果表明:在方圓800 m范圍內(nèi)，算法的絕對定位誤差可達到8 m以下，可定位節(jié)點覆蓋度可達99%以上。算法的定位精度和可定位節(jié)點覆蓋度隨劃分的基站廣播功率等級數(shù)的增大而提高。該算法不需要部署錨節(jié)點，節(jié)點間也無須進行信息交換，具有較高的實用性。

無線傳感器網(wǎng)絡;功率控制;定位;定位誤差

0 引言

在無線傳感器網(wǎng)絡的許多應用中都需要知道事件發(fā)生或采集數(shù)據(jù)的位置，沒有位置信息的數(shù)據(jù)通常沒有意義。對于野外大面積區(qū)域的應用場合，如果采用過于復雜算法或GPS等高成本、高能耗的定位設備獲取每一節(jié)點的準確位置將會提高代價，況且對于很多的應用來說，只需要知道事件發(fā)生的區(qū)域或大致位置就足夠了。

目前的定位算法從定位方法上可分為基于測距的定位算法(range-based)［1］和無須測距的定位算法(range-free)［2］兩大類。N.Bulusu等提出了質(zhì)心定位算法［3］，但是由于未知節(jié)點可能在多邊形區(qū)域內(nèi)的任何位置，因此該算法只能實現(xiàn)節(jié)點的粗略定位。為提高定位精度，Qiu Meng等提出了APIT算法［2］，通過多個包含未知節(jié)點的三角形區(qū)域彼此交疊的方式來縮小未知節(jié)點所屬的交叉區(qū)域，將交叉區(qū)域的質(zhì)心作為未知節(jié)點的坐標，但該算法要求具有較高的錨節(jié)點密度。在文獻［4］中，采用圓環(huán)來代替三角形，將多個圓環(huán)構(gòu)成的交叉區(qū)域的質(zhì)心作為未知節(jié)點的位置坐標。文獻［5］中表述了同心交叉圓環(huán)的質(zhì)心定位算法。上述算法都只有在錨節(jié)點密度較高的情況下才能取得較高的定位精度，而且錨節(jié)點需配置GPS等設備來確定自己的位置。對于野外大面積區(qū)域內(nèi)、不需要知道節(jié)點精確位置的應用場合而言，上述算法并不適宜。為此，筆者提出一種基于功率控制的無線傳感器網(wǎng)絡節(jié)點定位算法，設計目標是將未知節(jié)點的位置估計在一個很小區(qū)域內(nèi)，并以該區(qū)域的質(zhì)心作為該節(jié)點的位置估計。

1 系統(tǒng)模型

設監(jiān)測區(qū)域是一個800 m×800 m的方形，在方形區(qū)域同側(cè)的兩個底角和另一側(cè)底邊的中點各部署一個高性能的基站，坐標分別為B1(xb1，yb1)，B2(xb2，yb2)和B3(xb3，yb3)，假設基站功率足夠大，可以覆蓋整個區(qū)域，并能通過功率控制技術(shù)以不同的功率等級向整個監(jiān)測區(qū)域發(fā)送信息，基站能夠估計出覆蓋整個區(qū)域的最大功率以及不同功率等級下的覆蓋半徑。

基站采用全向天線，無線信號傳播采用理想自由空間傳播損耗模型［6］

式中:Pr——節(jié)點處的接收功率;

Pt——基站的廣播功率;

d——基站和接收節(jié)點之間的距離;

令Pth表示節(jié)點成功接收數(shù)據(jù)包的功率門限，根據(jù)式(1)，有

α=Pth·η為常數(shù)。基站以功率等級1，2，…，ω，…，τ廣播數(shù)據(jù)信息，τ為劃分的功率等級數(shù)，各功率等級對應的覆蓋半徑均勻分布，即覆蓋半徑分別為R， 2R，…，ωR，…，τR，則各功率等級的廣播功率分別為P1

t=αR2，=α(2R)2，第ω級的廣播功率為

其中ω=1，2，…，τ。由式(2)可知，第ω級的廣播功率為第1級廣播功率的ω2倍。

2 算法描述

首先，3基站分別以從小到大的功率等級向監(jiān)測區(qū)域廣播定位信息，經(jīng)過數(shù)輪廣播后，每個基站都形成一個包含未知節(jié)點的圓環(huán)，算法將不同基站形成的多個圓環(huán)的交叉區(qū)域的質(zhì)心作為節(jié)點的估計位置。

2.1 算法相關說明

2.1.1 基站的初始化

2.1.2 定位信息的廣播

定位信息分為配置信息和初始化信息兩種。3個基站分別以能夠覆蓋全部監(jiān)測區(qū)域的最大功率廣播配置信息(Mset)，配置信息主要包括當前輪數(shù)編號n、基站編號i、基站坐標、此輪廣播共劃分的功率等級數(shù)τ、每個功率等級ω所對應覆蓋半徑Rin，ω，收到該信息的節(jié)點解析并保存該信息。

3個基站(B1、B2、B3)分別以從小到大的功率等級廣播初始化信息(Minit)，功率等級較低的廣播信號覆蓋近基站區(qū)域，隨著功率等級的逐級遞增，覆蓋區(qū)域相應地逐步增加，初始化信息包含當前基站編號i、基站的功率等級編號ω等。監(jiān)測區(qū)域內(nèi)的節(jié)點根據(jù)收到的來自不同基站的初始化信息，確定自己分別處于哪一基站的哪兩個相鄰功率等級形成的圓環(huán)內(nèi)(如果當前基站以第5級功率廣播初始化信息，則其相鄰功率等級為4)。為避免節(jié)點在收到某一基站新的初始化信息后該節(jié)點所屬的圓環(huán)被重新設定，則設定了自己所屬圓環(huán)的節(jié)點不再接收該基站廣播的其余初始化信息，除非基站發(fā)出新一輪初始化指令。

2.2 包含節(jié)點的更小圓環(huán)的形成

基站經(jīng)過一輪初始化廣播后，每個節(jié)點確定自己分別屬于哪個基站的哪個圓環(huán)內(nèi)，并根據(jù)該圓環(huán)對應的兩個相鄰的功率等級編號查詢該輪的配置信息Mset，獲取相應的功率等級編號對應的覆蓋半徑，從而得到該圓環(huán)外邊界和內(nèi)邊界到基站的距離信息。此后，基站調(diào)節(jié)劃分的功率等級數(shù)τ，并廣播新的配置信息Mset及初始化信息Minit，開始新一輪的為節(jié)點確定其所屬圓環(huán)的過程。

經(jīng)過n輪的初始化廣播后，對于每個基站，每個節(jié)點明確了自己所屬的n個圓環(huán)，由同一基站形成的各圓環(huán)相互交疊形成包含未知節(jié)點的更小圓環(huán)。將由B1形成的n個圓環(huán)的各個內(nèi)、外徑分別排序，并取內(nèi)半徑最大者、外半徑最小者分別為此更小圓環(huán)的內(nèi)、外半徑。同理，可分別獲得由B2、B3形成的更小圓環(huán)的的內(nèi)、外半徑。

圖1中陰影部分為經(jīng)過3輪的初始化廣播后由基站B1形成的包含未知節(jié)點A的更小圓環(huán)(圖中只畫出圓環(huán)的一段)，得到由B1形成的包含節(jié)點A的更小圓環(huán)的內(nèi)外半徑分別為。

圖1 經(jīng)過3輪初始化廣播后由B1形成的更小圓環(huán)Fig.1 Smaller ring for B1after 3 rounds of initialization broadcast

2.3 節(jié)點的位置估算

經(jīng)過3輪的初始化廣播后，分別由基站B1、B3形成的包含未知節(jié)點A的2個更小圓環(huán)、由基站B2形成的包含未知節(jié)A點的圓，如圖2所示。在每輪基站B2的初始化廣播中，因節(jié)點A收到的初始化信息中的功率等級編號均為1，即該節(jié)點在第1級功率所覆蓋圓內(nèi)。經(jīng)過3輪的初始化廣播后，A處于由B2形成的3個圓內(nèi)，這3個圓相互交疊形成的區(qū)域即為3個圓中最小的那個圓。

圖2中深色區(qū)域為由2個更小圓環(huán)和一個圓形成的包含未知節(jié)點A的交叉區(qū)域，該區(qū)域的頂點為有效交叉點。和/分別為由 B1和B3形成的更小圓環(huán)的內(nèi)/外半徑，為由 B2形成的圓的半徑。

由圖2可知，由2個更小圓環(huán)以及1個圓形成了若干個交叉點，已知3個基站的坐標分別為B1(xb1，yb1)，B2(xb2，yb2)和B3(xb3，yb3)，因此，對每個交叉點，都可以得到一個線性方程組，通過解相應方程組可以得到所有交叉點的坐標。以圖2中Q(xq，yq)點為例，關于Q點方程組為

可得Q點坐標。只有交叉點同時滿足

則該交叉點被視為有效交叉點，根據(jù)式(3)找出所有有效交叉點a(x1，y1)、b(x2，y2)、c(x3，y3)、d(x4，y4)，根據(jù)質(zhì)心算法可得未知節(jié)點A的估計位置:

圖2 有效交叉點選擇Fig.2 Selection of valid intersection

3 仿真結(jié)果與分析

在仿真實驗中，網(wǎng)絡模型作如下假設:監(jiān)測區(qū)域為一個800 m×800 m的方形區(qū)域，3個基站的坐標分別為B1(0，0)，B2(800，0)和B3(400，800)，200個節(jié)點隨機分布在監(jiān)測區(qū)域內(nèi)，采用全網(wǎng)絕對定位誤差的平均值衡量算法的定位精度，采用可定位節(jié)點的覆蓋度(可定位的節(jié)點占所有節(jié)點的比例)從整體上衡量算法的有效性。

設每個基站進行3輪初始化廣播，劃分的功率等級數(shù)分別相差1級、2級、3級，見表1的劃分方式1、劃分方式2、劃分方式3，各功率等級對應的覆蓋半徑是均勻分布的。共采集5個點，每個采樣點對應各輪初始化廣播采用的功率等級數(shù)。

算法的絕對定位誤差隨劃分的功率等級數(shù)變化的情況如圖3所示?？啥ㄎ还?jié)點覆蓋度如圖4所示。絕對定位誤差e，即節(jié)點實際位置與估計位置的差值［7］。當劃分監(jiān)測區(qū)域的功率等級數(shù)較少時，相鄰功率等級對應的覆蓋半徑相差較大，因而形成的包含未知節(jié)點的圓環(huán)的寬度較大，定位精度并不高。隨著劃分的功率等級數(shù)的逐步增大，相鄰功率等級的覆蓋半徑相差更小，形成的圓環(huán)寬度更小，定位精度更高。由圖3可知，在方圓800 m的范圍內(nèi)，絕對定位精度可達到8 m以內(nèi)。

表1 功率等級劃分模式Table 1 Partition of power level

圖3 劃分的功率等級數(shù)對定位誤差的影響Fig.3 Impact of number of power level on location error

圖4 節(jié)點覆蓋度Fig.4 Coverage for sensor

有一些節(jié)點因沒有正確接收到基站的初始化信息而無法實現(xiàn)定位，這些節(jié)點在算法中屬于不良節(jié)點。圖4可見，隨著劃分的功率等級數(shù)的增大，功率劃分越來越細，可定位節(jié)點覆蓋度C也在不斷增大，甚至可以達到99%以上。

4 結(jié)束語

基于功率控制的節(jié)點定位算法是針對野外大面積區(qū)域、不需要知道節(jié)點精確位置的定位方法。通過仿真驗證了算法的有效性，仿真結(jié)果表明，通過增大基站初始化廣播的功率等級數(shù)，可進一步縮小包含未知節(jié)點的交叉區(qū)域，減小定位誤差。該算法不需要部署錨節(jié)點，節(jié)點之間也無須進行信息交換，降低成本的同時也降低了能耗。該算法具有較高的實用性和可操作性。

［1］CAO YICHAO.Target localization based on angle of arrivals［J］.Journal of Electronic Science and Technology of China，2007，5 (2):172－174.

［2］QIU MENG，XU HUIMIN.A distributed range-free localization algorithm based on clustering for wireless sensor networks［C］// Proceedings of the International Conference on Wireless Communications，Networking and Mobile Computing.Shanghai:IEEE，2007:2633－2636.

［3］BULUSU N，HEIDEMANN J，ESTRIN D.GPS-less low-cost outdoor localization for very small devices［J］.IEEE Personal Communications，2000，7(5):28－34.

［4］LIU CHONG，WU KUI，HE TIAN.Sensor localization with ring overlapping based on comparison of received signal strength indicator［C］//Proceedings of The 1st IEEE International Conference on Mobile Ad-hoc and Sensor Systems(MAHSS04).Florida，USA:IEEE，2004:516－518.

［5］VIVEKANANDAN V，WONG V W S.Concentric anchor beacon localization algorithm for wireless sensor networks［J］.IEEE Transactions on Vehicular Technology，2007，56(5):2733－2744.

［6］YAO QI，TAN SENG KEE，GE YU，et al.An area localization scheme for large wireless sensor networks［C］//Proceedings of the IEEE 61st Vehicular Technology Conference(VTC2005-Spring)，Stockholm，Sweden:IEEE，2005，5:2835－2839.

［7］汪 煬.無線傳感器網(wǎng)絡定位技術(shù)研究［D］.合肥:中國科學技術(shù)大學，2007.

［8］吳開興，張榮華.基于信息分組的TDOA安全定位算法［J］.河北工程大學學報:自然科學版，2011，28(2):60－63.

Localization algorithms based on power control for wireless sensor network

ZHAO Zhixin1， GUO Jikun1， PENG Bao2

(1.College of Electric＆Information Engineering，Heilongjiang Institute of Science＆Technology，Harbin 150027，China; 2.Communication Research Center，Harbin Institute of Technology，Harbin 150080，China)

For the field of a large area or the field which doesn’t need exact location，a node localization algorithm was proposed based on power control.With power control technology，three ring containing the unknown node was formed by the three base stations，and by calculating the centroid of the cross-region formed by the three rings location of the unknown node was achieved.Simulation results showed that within a radius of 800 meters，the absolute location error of the algorithm could be smaller than 8 m and the coverage was up to 99%.With the increase of the number of broadcast power level of base station，location accuracy and coverage also improved.The algorithm did not require the deployment of anchor nodes and information exchange between nodes，and was with high practicality.

wireless sensor network;power control;localization;localization error

TP393.03

:A

1671－0118(2012)02－0168－04

2012－02－21

黑龍江省教育廳科學技術(shù)研究項目(11551443)

趙志信(1979－)，男，黑龍江省哈爾濱人，講師，碩士，研究方向:無線傳感器網(wǎng)絡定位，E-mail:zhaozhixin0830@163.com。

(編輯徐 巖)