基于功率控制的无线传感器网络节点定位算法

赵志信， 郭继坤， 彭 保

(1.黑龙江科技学院 电气与信息工程学院，哈尔滨 150027;2.哈尔滨工业大学 通信技术研究所，哈尔滨 150080)

基于功率控制的无线传感器网络节点定位算法

赵志信1， 郭继坤1， 彭 保2

(1.黑龙江科技学院 电气与信息工程学院，哈尔滨 150027;2.哈尔滨工业大学 通信技术研究所，哈尔滨 150080)

针对野外大面积区域、不需要知道节点精确位置的应用场合，提出一种基于功率控制的节点定位算法。采用功率控制方式，分别由3个基站形成包含未知节点的3个圆环，通过计算由3个圆环形成的交叉区域的质心来实现未知节点的定位。仿真结果表明:在方圆800 m范围内，算法的绝对定位误差可达到8 m以下，可定位节点覆盖度可达99%以上。算法的定位精度和可定位节点覆盖度随划分的基站广播功率等级数的增大而提高。该算法不需要部署锚节点，节点间也无须进行信息交换，具有较高的实用性。

无线传感器网络;功率控制;定位;定位误差

0 引言

在无线传感器网络的许多应用中都需要知道事件发生或采集数据的位置，没有位置信息的数据通常没有意义。对于野外大面积区域的应用场合，如果采用过于复杂算法或GPS等高成本、高能耗的定位设备获取每一节点的准确位置将会提高代价，况且对于很多的应用来说，只需要知道事件发生的区域或大致位置就足够了。

目前的定位算法从定位方法上可分为基于测距的定位算法(range-based)［1］和无须测距的定位算法(range-free)［2］两大类。N.Bulusu等提出了质心定位算法［3］，但是由于未知节点可能在多边形区域内的任何位置，因此该算法只能实现节点的粗略定位。为提高定位精度，Qiu Meng等提出了APIT算法［2］，通过多个包含未知节点的三角形区域彼此交叠的方式来缩小未知节点所属的交叉区域，将交叉区域的质心作为未知节点的坐标，但该算法要求具有较高的锚节点密度。在文献［4］中，采用圆环来代替三角形，将多个圆环构成的交叉区域的质心作为未知节点的位置坐标。文献［5］中表述了同心交叉圆环的质心定位算法。上述算法都只有在锚节点密度较高的情况下才能取得较高的定位精度，而且锚节点需配置GPS等设备来确定自己的位置。对于野外大面积区域内、不需要知道节点精确位置的应用场合而言，上述算法并不适宜。为此，笔者提出一种基于功率控制的无线传感器网络节点定位算法，设计目标是将未知节点的位置估计在一个很小区域内，并以该区域的质心作为该节点的位置估计。

1 系统模型

设监测区域是一个800 m×800 m的方形，在方形区域同侧的两个底角和另一侧底边的中点各部署一个高性能的基站，坐标分别为B1(xb1，yb1)，B2(xb2，yb2)和B3(xb3，yb3)，假设基站功率足够大，可以覆盖整个区域，并能通过功率控制技术以不同的功率等级向整个监测区域发送信息，基站能够估计出覆盖整个区域的最大功率以及不同功率等级下的覆盖半径。

基站采用全向天线，无线信号传播采用理想自由空间传播损耗模型［6］

式中:Pr——节点处的接收功率;

Pt——基站的广播功率;

d——基站和接收节点之间的距离;

令Pth表示节点成功接收数据包的功率门限，根据式(1)，有

α=Pth·η为常数。基站以功率等级1，2，…，ω，…，τ广播数据信息，τ为划分的功率等级数，各功率等级对应的覆盖半径均匀分布，即覆盖半径分别为R， 2R，…，ωR，…，τR，则各功率等级的广播功率分别为P1

t=αR2，=α(2R)2，第ω级的广播功率为

其中ω=1，2，…，τ。由式(2)可知，第ω级的广播功率为第1级广播功率的ω2倍。

2 算法描述

首先，3基站分别以从小到大的功率等级向监测区域广播定位信息，经过数轮广播后，每个基站都形成一个包含未知节点的圆环，算法将不同基站形成的多个圆环的交叉区域的质心作为节点的估计位置。

2.1 算法相关说明

2.1.1 基站的初始化

2.1.2 定位信息的广播

定位信息分为配置信息和初始化信息两种。3个基站分别以能够覆盖全部监测区域的最大功率广播配置信息(Mset)，配置信息主要包括当前轮数编号n、基站编号i、基站坐标、此轮广播共划分的功率等级数τ、每个功率等级ω所对应覆盖半径Rin，ω，收到该信息的节点解析并保存该信息。

3个基站(B1、B2、B3)分别以从小到大的功率等级广播初始化信息(Minit)，功率等级较低的广播信号覆盖近基站区域，随着功率等级的逐级递增，覆盖区域相应地逐步增加，初始化信息包含当前基站编号i、基站的功率等级编号ω等。监测区域内的节点根据收到的来自不同基站的初始化信息，确定自己分别处于哪一基站的哪两个相邻功率等级形成的圆环内(如果当前基站以第5级功率广播初始化信息，则其相邻功率等级为4)。为避免节点在收到某一基站新的初始化信息后该节点所属的圆环被重新设定，则设定了自己所属圆环的节点不再接收该基站广播的其余初始化信息，除非基站发出新一轮初始化指令。

2.2 包含节点的更小圆环的形成

基站经过一轮初始化广播后，每个节点确定自己分别属于哪个基站的哪个圆环内，并根据该圆环对应的两个相邻的功率等级编号查询该轮的配置信息Mset，获取相应的功率等级编号对应的覆盖半径，从而得到该圆环外边界和内边界到基站的距离信息。此后，基站调节划分的功率等级数τ，并广播新的配置信息Mset及初始化信息Minit，开始新一轮的为节点确定其所属圆环的过程。

经过n轮的初始化广播后，对于每个基站，每个节点明确了自己所属的n个圆环，由同一基站形成的各圆环相互交叠形成包含未知节点的更小圆环。将由B1形成的n个圆环的各个内、外径分别排序，并取内半径最大者、外半径最小者分别为此更小圆环的内、外半径。同理，可分别获得由B2、B3形成的更小圆环的的内、外半径。

图1中阴影部分为经过3轮的初始化广播后由基站B1形成的包含未知节点A的更小圆环(图中只画出圆环的一段)，得到由B1形成的包含节点A的更小圆环的内外半径分别为。

图1 经过3轮初始化广播后由B1形成的更小圆环Fig.1 Smaller ring for B1after 3 rounds of initialization broadcast

2.3 节点的位置估算

经过3轮的初始化广播后，分别由基站B1、B3形成的包含未知节点A的2个更小圆环、由基站B2形成的包含未知节A点的圆，如图2所示。在每轮基站B2的初始化广播中，因节点A收到的初始化信息中的功率等级编号均为1，即该节点在第1级功率所覆盖圆内。经过3轮的初始化广播后，A处于由B2形成的3个圆内，这3个圆相互交叠形成的区域即为3个圆中最小的那个圆。

图2中深色区域为由2个更小圆环和一个圆形成的包含未知节点A的交叉区域，该区域的顶点为有效交叉点。和/分别为由 B1和B3形成的更小圆环的内/外半径，为由 B2形成的圆的半径。

由图2可知，由2个更小圆环以及1个圆形成了若干个交叉点，已知3个基站的坐标分别为B1(xb1，yb1)，B2(xb2，yb2)和B3(xb3，yb3)，因此，对每个交叉点，都可以得到一个线性方程组，通过解相应方程组可以得到所有交叉点的坐标。以图2中Q(xq，yq)点为例，关于Q点方程组为

可得Q点坐标。只有交叉点同时满足

则该交叉点被视为有效交叉点，根据式(3)找出所有有效交叉点a(x1，y1)、b(x2，y2)、c(x3，y3)、d(x4，y4)，根据质心算法可得未知节点A的估计位置:

图2 有效交叉点选择Fig.2 Selection of valid intersection

3 仿真结果与分析

在仿真实验中，网络模型作如下假设:监测区域为一个800 m×800 m的方形区域，3个基站的坐标分别为B1(0，0)，B2(800，0)和B3(400，800)，200个节点随机分布在监测区域内，采用全网绝对定位误差的平均值衡量算法的定位精度，采用可定位节点的覆盖度(可定位的节点占所有节点的比例)从整体上衡量算法的有效性。

设每个基站进行3轮初始化广播，划分的功率等级数分别相差1级、2级、3级，见表1的划分方式1、划分方式2、划分方式3，各功率等级对应的覆盖半径是均匀分布的。共采集5个点，每个采样点对应各轮初始化广播采用的功率等级数。

算法的绝对定位误差随划分的功率等级数变化的情况如图3所示。可定位节点覆盖度如图4所示。绝对定位误差e，即节点实际位置与估计位置的差值［7］。当划分监测区域的功率等级数较少时，相邻功率等级对应的覆盖半径相差较大，因而形成的包含未知节点的圆环的宽度较大，定位精度并不高。随着划分的功率等级数的逐步增大，相邻功率等级的覆盖半径相差更小，形成的圆环宽度更小，定位精度更高。由图3可知，在方圆800 m的范围内，绝对定位精度可达到8 m以内。

表1 功率等级划分模式Table 1 Partition of power level

图3 划分的功率等级数对定位误差的影响Fig.3 Impact of number of power level on location error

图4 节点覆盖度Fig.4 Coverage for sensor

有一些节点因没有正确接收到基站的初始化信息而无法实现定位，这些节点在算法中属于不良节点。图4可见，随着划分的功率等级数的增大，功率划分越来越细，可定位节点覆盖度C也在不断增大，甚至可以达到99%以上。

4 结束语

基于功率控制的节点定位算法是针对野外大面积区域、不需要知道节点精确位置的定位方法。通过仿真验证了算法的有效性，仿真结果表明，通过增大基站初始化广播的功率等级数，可进一步缩小包含未知节点的交叉区域，减小定位误差。该算法不需要部署锚节点，节点之间也无须进行信息交换，降低成本的同时也降低了能耗。该算法具有较高的实用性和可操作性。

［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］汪 炀.无线传感器网络定位技术研究［D］.合肥:中国科学技术大学，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

黑龙江省教育厅科学技术研究项目(11551443)

赵志信(1979－)，男，黑龙江省哈尔滨人，讲师，硕士，研究方向:无线传感器网络定位，E-mail:zhaozhixin0830@163.com。

(编辑徐 岩)