一种基于移动锚节点的多坐标系定位算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇一种基于移动锚节点的多坐标系定位算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
收稿日期:2009-12-16.
[BP（]基金项目:
[BP）]
作者简介:梁甲金（1983-），男，硕士研究生.主要研究方向：无线传感器网络定位.
通讯作者:
摘要: 提出一种分布式节点定位算法:移动锚节点辅助多坐标系定位算法(MBA-MC)，用于无线传感器网络节点定位.移动锚节点在WSN节点分布区域内移动，同时周期性发送信标信号，并且在同一位置分别在多个不同的发射功率下发送信标信号.未知位置节点接收信标后估算与锚节点距离范围，然后利用在多坐标系系统下接收的信标信息得到多个扇形的交叠区，并认为交叠区中心就是节点自身位置.仿真结果表明：在相同条件下，本文提出算法比其他算法能取得更好的定位准确性，其全分布式计算定位方式特别适用于大规模的无线传感器网络节点定位.
关键词: 无线传感器网络；节点定位；移动锚节点辅助；多坐标系
中图分类号:TP393
文献标识码:A文章编号:1672-8513(2010)04-0248-05
A Multi-Coordinate Localization Algorithm Based on the Mobile Anchor
LIANG Jiajin, DENG Ping
（Key Lab of Information Coding & Transmission, Southwest Jiaotong University, Chengdu 610031, China）
Abstract: A distributed localization algorithm in wireless sensor networks, that is, a mobile beacon assisted multi-coordinate (MBA-MC) localization algorithm, is proposed. The mobile anchor traverses across the whole WSN field and periodically broadcasts the beacons at two or more different power levels (including its current information). Each unknown node in the field passively receives the beacons within its sensing range, by using the information received from each beacon in the multi-coordinate systems; each node can obtain the approximated center of intersection of the multi-arc-area, and consider the approximated center as its position estimate. Simulation results show the algorithm is efficient and suitable for the large scale wireless sensor networks.
Key words: WSN; node localization; mobile beacon assisted; multi-coordinate
无线传感器网络(Wireless Sensor Network, WSN)由大量部署在监控区域的传感器节点通过无线通信方式自组成网，协作感知、采集和处理相关监控信息.监控事件的位置信息对研究覆盖、路由及跟踪等问题具有重要的作用，而传感器节点自身的正确定位是提供位置信息的前提，因此WSN节点本身的精确定位非常重要.
在WSN中，节点定位方法主要分成两大类［1］:Range based 算法以及Range free算法.Range based算法通过距离或者角度信息进行定位，测距技术包括：信号到达时间、信号到达时间差、信号到达角度、信号强度等.此类算法需要额外的硬件支撑，其定位精度相对较高.Range free算法不需要测量节点间的距离和方位，对硬件要求简单，但定位误差较大，满足部分不需要高精度位置信息的场合.其典型算法包括：质心算法、DV-HOP算法、Amorphous 算法、MDS-MAP算法及 APIT 算法等.在静态网络定位中需要利用较多的锚节点，解决静态锚节点高成本问题的办法是用移动锚节点来进行节点定位.
1 移动锚节点辅助定位方法描述
目前比较实用的定位方法是利用一些移动锚节点根据有效的规划路径移动，通过发送包含其自身坐标的信标来定位其他节点，该方法不会过多地增加无线传感器网络成本，还可以获得较高的定位精度.
WSN节点布置完成后自组织成网并进入探测状态，移动锚节点在监测区域内移动并周期发送信标信号.假定各移动锚节点均配置一个GPS接收器用于定位自身，并且有足够的能量自己移动或者附着于移动机器人及移动车辆等工具.移动锚节点在传感器区域内按照一定的路线移动，并周期性地发送信标，发送信标的位置我们称为信标点，信标包含锚节点当前位置等信息.传感器节点在其探测范围内能够感知移动锚节点的出现，接收、存储和选择移动锚节点发出的信标，然后融合定位算法确定自身位置.
Sichitiu等最先提出基于移动锚节点利用信号强度测距的定位方法［2］，文献［3-4］中也先后提出了基于信号强度测距的定位方法.此外，文献［5］提出了利用移动锚节点信标信号的发送时间和接收时间计算信标到达时间差进行定位的方法.在文献［6-8］中提出了几种利用非测距几何解法进行位置估计的方法.
本文提出一种基于移动锚节点的非测距定位算法，不需要任何特殊硬件支持.本算法中，移动锚节点在网络中周期地以不同功率发射信标信号，接收到信标信号的未知节点得到一系列关于自身位置的约束，然后利用最优约束进行自身位置估计.
该算法是一种分布式节点定位算法，利用较少的锚节点借助非测距的方法实现节点自定位.算法有以下特点：①算法简单，易于实现；②不需要节点与邻居节点通信；③在相同条件下，比其他算法取得更好的定位准确性.
2.1 移动锚节点信标发送功率分级
在本文算法中，移动锚节点在同一位置分别在多个不同的发射功率下发送信标信号，信标信号包含的内容为：锚节点编号、发送时刻锚节点所处位置和本次发射功率等级等.
本算法中，每个发射功率对应着1个等级数.例如发射功率Pi对应着等级i，在此发射功率下信标的最远传输距离为ri.锚节点以发射功率Pi传输信标时，信标内容包含锚节点编号、此时锚节点位置坐标和本次发射功率等级i等信息.未知节点接收到这个信标后就可知道它与锚节点的距离在ri内.如果接收到来自同一锚节点在相同位置发送的多个信标信号，节点选择发射功率等级i最低的信标用于定位.这样就可以把节点的位置约束在1个半径最小的圆域内.
本算法中把锚节点的发射功率按照传输距离圆环宽度相等分成多个级别.
2.2 移动锚节点辅助多坐标系定位算法步骤
WSN中所有节点布置完成后，每个未知节点开始接收信标信号，当节点接收到来自多个信标点的信标后就可以利用MBA-MC定位算法进行自身的位置估计.
本文算法仅考虑在二维情况下的实现过程.分布式多坐标系(Distributed MultiCoordinate, DMC)［10］定位算法是由节点从周围多个可通信锚节点中选择最锚节点，并由锚节点直角坐标进行极坐标转化，然后由极坐标系求节点可能存在区域并以这一区域的中心作为节点的位置估计.MBA-MC是一种由DMC定位算法结合锚节点发射功率分级方法实现的移动锚节点辅助的定位算法，算法的具体实施方法和步骤如下所述：
3 仿真与性能分析
本节利用Matlab对基于移动锚节点的DMC和质心定位算法与MBA-MC定位算法进行仿真比较.在算法仿真中，移动锚节点采用一种在Ad Hoc网络中广泛应用的模型：高斯-马尔可夫(Gauss-Markov)运动模型［11］.同随机行走模型相比，高斯-马尔可夫运动模型可以克服移动锚节点突然停止以及突然转弯情况.锚节点移动采用这种运动模型，容易覆盖区域内所有节点，这种运动模型比较适合于WSN.高斯-马尔可夫运动模型表示如下：
[JP2]v(k)=α•v(k－1)+(1－α)•v+1－α2•wv(k－1).[JP](6)
[JP2]d(k)=α•d(k－1)+(1－α)•d+1－α2•wd(k－1).[JP](7)
[JP+2]v(k)和d(k)表示k时刻移动锚节点的速度和移动方向，0≤α≤1表示随机转弯参数，和表示k∞时节点的平均速度和方向，wv(k－1)和wd(k－1)表示随机高斯变量.移动锚节点下一时刻的坐标位置基于当前时刻的速度和方向，计算方法如下：[JP]
[JP2]x(k)=x(k－1)+v(k－1)•cos(d(k－1)).[JP](8)
y(k)=y(k－1)+v(k－1)•sin(d(k－1)).(9)
本文中对定位算法仿真时，假设500个节点随机分布在1000m ×1000m 的正方形区域内，假定传感器节点感知范围为30m，锚节点最远有效通信距离为70m，即未知节点距离锚节点70m范围内可以可靠接收到锚节点发送的信标信号.
在仿真中，移动锚节点运动模型满足Gauss-Markov模型，在此模型中平均速度5m/s, 转弯系数α=0.85，当移动锚节点接近区域边沿时改变方向.初始时刻有4个移动锚节点从节点分布区域的4个顶点进入节点分布区域，经过大约1500s就可以覆盖整个区域，锚节点的移动路线如图3所示.在锚节点广播信标的周期从15s增加到90s，即用于定位的信标点数量逐渐减少的情况下，仿真得到定位算法的平均定位误差.
[FK(W][FK)]
本文分别对以下几种情况进行仿真对比：①基于移动锚节点的质心算法；②基于移动锚节点的DMC定位算法；③锚节点在同一位置分别以2个不同发射功率发送信标信号，即step=2，对应的最大传输距离分别为rmax和r1，且r1=rmax－r1；④锚节点在同一位置分别以3个不同发射功率发送信标信号，即step=3.仿真结果如图4所示，DMC、质心和MBA-MC在不同功率等级下的仿真性能比较.
[FK(W][FK)]
[JP+2]仿真结果表明，在相同的仿真环境中使用MBA-MC算法节点的估计位置更接近于节点的真实位置，比DMC算法直接用于移动锚节点定位取得更加准确的位置估计结果，定位性能得到明显改善.通过缩短锚节点广播信标信号的周期可以减小节点的定位误差，并且能够使更多节点完成自定位.由图4可知，MBA-MC算法在step=3时比step=2时取得更加准确的位置估计，由此可知锚节点发射功率分级越多定位的准确性就越高.MBA-MC定位算法与DMC定位算法相比，只是增加了发射功率等级识别，计算复杂度几乎没有增加，同时锚节点发射功率等级的增加不影响算法的复杂度.由于移动锚节点只应用在节点定位阶段，移动锚节点能量相对充足，适当增加发射功率的等级和减小信标的发射周期进一步缩小定位误差是可行的方法.[JP]
4 结语
WSN节点定位是研究其它问题及应用的基础.本文提出的MBA-MC定位算法，充分利用移动锚节点能量相对充足的优点，在同一位置分别在多个不同的发射功率下发送信标信号来提高定位准确性，仿真表明了本算法的有效性.算法采用全分布式计算方式，计算耗能少，可以广泛应用于WSN中的节点定位，这种算法特别适合于大规模WSN.在今后的应用中，还可以通过对移动锚节点的移动路线进行优化来得到更高的定位精度.无法完成自定位的节点可以利用已定位的邻居节点的位置信息完成自定位.[FL)]
参考文献:
［1］BULUSU N,HEIDEMANN J,ESTRIN D.GPS-less low cost outdoor localization for very small devices［J］.IEEE Personal Communications Magazine, 2000,7:28-34.
［2］SICHITIU M L, RAMADURAI V. Localization of wireless sensor networks with a mobile beacon［C］//Proc of the IEEE Int′l Conf on Mobile Ad-Hoc and Sensor Systems. IEEE Computer Society, 2004:174-183.
［3］任丽婕.无线传感器网络中节点部署和优化算法研究［D］.青岛:中国海洋大学,2009.
［4］KIM K,LEE W.MBAL: A mobile beacon-assisted localization scheme for wireless sensor networks［C］// Proceeding of the 16th International conference on computer communications and networks. Hawaii: IEEE Society Communications,2007:57-62.
［5］XIA Z J,CHEN C J.A localization scheme with mobile beacon for wireless sensor networks［C］// Proceeding of the 6th International Conference on ITS Telecommunications. Chengdu,2006:1017-1020.
［6］GUO Z, GUO Y, HONG F, et al. Perpendicular intersection: locating wireless sensors with mobile beacon［C］//Proceeding of the 2008 Real-Time Systems Symposium. 2008:93-102.
［7］SSU K F,OU C H, JIAU H C.Localization with mobile anchor points in wireless sensor networks［J］.IEEE Trasactions on Vehicular Technology, 2005,54(3):1187-1179.
［8］XIAO Bin,CHEN Hekang,ZHOU Shuigeng. Distributed localization using a moving beacon in wireless sensor networks［J］. IEEE Trasactions on parallel and distributed systms,2008,19(5):587-600.
［9］VIVEKANANDAN V, WONG V W S. Concentric anchor beacon localization algorithm for wireless sensor networks［J］.IEEE Trasactions on Vehicular Technology,2007,56(5):2733-2744.
［10］LI Zhi,CHEN Hui,QIAN Jing,et al.A distributed multi-coordinate localization algorithm For wireless sensor networks［C］//2008 International Symposiums on Information Processing,2008.
［11］CAMP T,BOLENG J,DAVIES V.A survey of mobility models for Ad Hoc network research［J］.Wireless Communication& Mobile Computing:Special issue on Mobile Ad Hoc Networking: Research,Trends and Applications,2002,2(5):483-502.
(上接第243页)
参考文献:
［1］周永彬,冯登国.RFID安全协议的设计与分析［J］.计算机学报,2006，29（4）:581-589.
［2］HAN D G,TAKAGI T,KIM H W, et al.New security problem in RFID systems“Tag Killing” ［C］//Computational Science and Its Applications 2006. LNCS 3982,2006：375-384, .
［3］LEE Y C,HSIEHG Y C,YOU P S,et al.An improvement on RFID authentication protocol with privacy protection［C］//Third 2008 International Conference on Convergence and Hybrid Information Technology.2008:569-573.
［4］王新锋,刘建国,蒋旭,等.移动型RFID安全协议及其GNY逻辑分析［J］.计算机应用, 2008，28（9）:2239-2241.
［5］高磊,盛焕烨.RFID应用系统中的Tag-reader安全通信协议.计算机工程［J］，2007，33（21）：128-129.
［6］LIU Yanfei.An efficient RFID authentication protocol for low-cost tags［C］//International conference on embedded and ubiquitous computing. 2008:180-185.
［7］李芳,黄生叶.一种基于EPC C1G2标准的低成本RFID双向认证协议［J］.科学技术与工程,2008，8（20）:5567-5571.
［8］王立斌,马昌社,王涛.一种安全高效的RFID双边认证协议,计算机应用［J］,2008,28（9）:2236-2238.
［9］杜治国,杨波,欧阳国帧,等.安全的RFID认证协议研究设计.计算机工程与设计［J］,2009,30(3)561-565.
［10］祝胜林,杨波,张明武,等.基于PRNG的低成本RFID 认证协议设计,计算机工程［J］,2008，34（21）：18-19.
［11］卿斯汉.安全协议［M］.北京：清华大学出版社,2005.