趙志信， 郭繼坤， 彭 保

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

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

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

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

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

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

0 引言

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

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

1 系統(tǒng)模型

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

基站采用全向天線，無(wú)線信號(hào)傳播采用理想自由空間傳播損耗模型［6］

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

Pt——基站的廣播功率;

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

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

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

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

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

2 算法描述

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

2.1 算法相關(guān)說(shuō)明

2.1.1 基站的初始化

2.1.2 定位信息的廣播

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

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

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

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

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

圖1中陰影部分為經(jīng)過3輪的初始化廣播后由基站B1形成的包含未知節(jié)點(diǎn)A的更小圓環(huán)(圖中只畫出圓環(huán)的一段)，得到由B1形成的包含節(jié)點(diǎn)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é)點(diǎn)的位置估算

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

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

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

可得Q點(diǎn)坐標(biāo)。只有交叉點(diǎn)同時(shí)滿足

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

圖2 有效交叉點(diǎn)選擇Fig.2 Selection of valid intersection

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

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

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

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

表1 功率等級(jí)劃分模式Table 1 Partition of power level

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

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

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

4 結(jié)束語(yǔ)

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

［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ú)線傳感器網(wǎng)絡(luò)定位技術(shù)研究［D］.合肥:中國(guó)科學(xué)技術(shù)大學(xué)，2007.

［8］吳開興，張榮華.基于信息分組的TDOA安全定位算法［J］.河北工程大學(xué)學(xué)報(bào):自然科學(xué)版，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

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

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

(編輯徐 巖)