无线传感器网络节点位的信标节点移动路径规划.doc

无线传感器网络节点定位的信标节点移动路径规划刘辉亚1 徐建波1（1湖南科技大学计算机科学与工程学院 湖南湘潭411201）LIU Hui-ya1 XU Jian-bo1（1School of Computer Science and Engineering Hunan University of Science and Technology；Hunan 411201）E_mail:Path Planning for Mobile Beacon Nodes in Localization for Wireless Sensor NetworksAbstract:Localization is a key technology in wireless sensor networks. The main idea in most localization methods has been that some mobile beacon nodes transmit packets to help unknown nodes to localize themselves in order to reduce network cost and communication overhead.A fundamental issue is the planning of beacon nodes moving path in these methods. We apply moving path planning algorithm that beacon nodes move to the maximum coverage of unlocated nodes. The simulations show this algorithm obtains good localization performance and is well adapted to large-scale applications with nodes spreaded by random and uneven. Key words:wireless sensor network ;path planning algorithm; signal strength;mobile beacon node摘 要：节点定位是无线传感网络技术研究的一个基本问题。针对其身的特点，目前较为实用的节点定位方法主要是以移动信标节点来进行定位，以减少网络成本及节点间的通信开销，而这些方法，必需要解决的基本问题是信标节点移动路径的规划。本文针对这一问题，提出了信标节点向最大覆盖未定位节点方向移动的路径规划算法。仿真实验表明，具有较好的定位性能，能很好地适应大规模随机不均匀撒布节点的应用需求。关键字：无线传感器网络；路径规划算法；信号强度；移动信标节点中图法分类号：TP393文献标识码：A 1引言近年来，随着无线传感器网络（Wireless Sensor Networks ，WSN）的广泛应用，对于各个节点采集到的数据必须具有位置信息才有意义，因此，节点的自身定位显得尤为重要。目前，许多学者倾注研究节点定位问题，并提出了许多的定位算法，主要是基于信标节点（配有GPS或事先人工布置已知位置节点）和无信标节点两大类。基于信标节点定位算法是根据信标节点发送信息包，采用RSSI，TOA，TDOA和AOA等获得邻居信标节点的距离，再利用三边测量法或极大似然估计法计算得到未知节点的位置。无信标节点定位算法依靠节点间的相关位置，以网络中的某些节点作为参考点，形成局部坐标，最后进行合并产生整体相对位置，这种算法其应用具有局限性，而基于信标节点定位算法由于使用了GPS，增加了网络成本。因此尽可能减少使用信标节点并又能达到基金项目：湖南省自然科学湘潭联合基金项目(09JJ9006)，湖南省教育厅科学研究项目(09A027)作者简介：刘辉亚（1976年9月），男，湖南湘潭人，讲师，硕士，主要研究方向是无线传感器网络；徐建波（1963年），男，湖南湘潭人，教授，博士，主要研究方向是分布式计算和计算机网络。应用需求的定位方法成为WSN节点定位研究热点。目前，许多研究提出利用移动信标节点来进行定位，以减少信标节点数量的要求。文献中利用一个或多个信标节点在被监测区进行自由移动，同时发送信息包，未知节点可根据测定到信标节点的距离或角度进行定位；文献中利用9个信标节点以一定的几何形状进行移动，然后根据接收信标节点的信号强度再利用几何方法得到未知节点的坐标。然而这些方法中都未涉及到信标节点的移动路径规划问题，虽然文献提出了信标节点的移动路径获取方法，而文献信标节点移动是随机的；文献在节点密度不高，分布不均匀的情况下，就不一定是最优路径，因为在移动路径的某个位置上的覆盖区域中可能没有一个未定位节点；文献提出了圆形和S形规划路径方法是静态规划路径，无论WSN节点分布如何，移动信标节点都是按照预先规划的路径进行节点定位。针对以上情况，本文主要研究WSN节点定位中信标节点的移动路径问题。首先利用文献中的定位方法对信标节点所覆盖区域内节点进行定位，然后根据信标节点所覆盖区域外未定位节点数量来确定信标节点的下一个移动位置，最终实现对被监测区域的全部节点进行定位。2、信标节点移动路径规划算法由于信标节点移动路径将直接影响节点的定位精度、覆盖率及网络的通信开销，因此本文认为信标节点移动路径选择要考虑三个方面：（1）当信标节点整体移动时，需要在下一个移动位置其覆盖区域内未定位的节点尽可能多；（2）移动路径上信标节点移动位置尽可能少；（3）信标节点移动路径距离尽可能少。这样既可以减少定位过程中信标节点的移动距离，又可以减少定位过程中未知节点与信标节点的通信开销，最终达到节约节点能量，延长整个网络生命周期。基于这一观点，本文提出了信标节点向最大覆盖未知节点方向移动的路径规划算法。据文献信标节点所覆盖区域及其具体分布如图1所示，以信标节点为中心，13121415161181097432561 n均匀分布在以节点通信半径为R的圆周上。假设每个信标节点所发送的信息包在其通信半径范围内才能接收到，即：如果未知节点接收到信标节点的信号强度，则表示未知节点在信标节点的通信范围内；如果未知节点接收到信标节点的信号强度，则表示未知节点不在信标节点的通信范围内。对信标节点所覆盖区域内的未知节点定位方法采用文献，而本文重点是研究信标节点的移动路径规划算法(其它信标节点以为参照物并保持原来的位置关系进行移动)：采用向最大覆盖未定位节点方向的移动位置选择算法来获得的移动路径。这一方法需要研究两个方面的问题：一方面是信标节点移动方法，另一方面是信标节点移动方向。 图1信标节所覆盖区域示意图 图2未知节点随机部署示意图 (1)信标节点的移动方法考虑到文献的定位方法，对于32个小区域中离信标节点较远的未知节点定位误差比较大，为修正这一误差以及信标节点的移动距离和移动方向对覆盖整个被监测区域的影响，提出了如下的信标节点的移动方法：首先把信标节点所覆盖的圆形区域分成四个区：U（上半区）、R（右半区）、D（下半区）和L（左半区）U（上半区）对应的信标节点： R（右半区）对应的信标节点：D（下半区）对应的信标节点： L（左半区）对应的信标节点：信标节点具体的移动方法如图3所示： a向U区移动 b向R区移动 c向D区移动 d向L区移动图3 信标节点的移动方法与方向（2）信标节点的移动方向为了减少信标节点的移动次数，以减少与信标节点与未知节点的通信及信标节点移动距离，应向信标通信区域外的未定位节点数量最多的方向移动，其具体方法如下：设未知节点到信标节点， ，和的信号强度分别为：，和，如果(不在的通信范围)，则（1）（在信标节点的通信范围）的未定位的未知节点的个数设为；（2）（在信标节点的通信范围）的未定位的未知节点的个数设为；（3）（在信标节点的通信范围）的未定位的未知节点的个数设为；（4）（在信标节点的通信范围）的未定位的未知节点的个数设为；如果，信标节点向U（上半区）移动，如图3-a所示, 向上平行移动距离，即的下一个位置为：(，)；如果，信标节点向R（右半区）移动，如图3-b所示，向右平行移动距离，即的下一个位置为：(，)；如果，信标节点向D（下半区）移动，如图3-c所示，向下平行移动距离，即的下一个位置为：(，)；如果，信标节点向R（左半区）移动，如图3-d所示，向左平行移动距离，即的下一个位置为：(，)；以上，其中为被监测区域部署未知节点的总个数。当信标节点移动一次后，又会形成四个分区：U（上半区）、R（右半区）、D（下半区）和L（左半区），按以上的方法选择下一个移动方向。已此类推，获得覆盖整个被监测区域的信标节点移动位置，从而所有信标节点的移动路径。3、仿真实验与算法分析为了验证算法的有效性及合理性，本文利用Matlab进行仿真实验，并对信标节点随机方向移动算法与本文的移动路径规划算法性能进行对比分析。(1) 本文所使用的信号传输模型采用文献的空间传输损耗模型： 仿真参数采用文献中的数据，选择，(室外)，均值为0，方差。(2) 仿真的实验环境：在的正方形区域随机部署100个未知节点，如图2所示。信标节点位于正方形区域中心，其它16个信标节点均匀分布在以为圆心，通信半径=5m的圆周上。a 被监测区域覆盖情况图 b 信标节点移动路径图图4 本文算法区域覆盖情况及移动路径图a 被监测区域覆盖情况图 b 信标节点移动路径图图5 随机方向移动算法覆盖情况及移动路径图(3) 算法性能比较：如图4所示，本文算法在图2所示的节点部署情况下的覆盖情况及移动路径，覆盖率达90%以上，发射点为30个，移动路径约为；如图5所示是随机方向移动(不重复路径)情况，覆盖率达95%以上，发射点为47个，移动路径约为。如图6所示未知节点密度不同环境下，本文算法与随机方向移动算法的覆盖率和信标节点移动距离的比较，从图6中可以看出，本文算法在不影响应用需求的情况下，大幅度减少信标节点的移动位置及移动距离，从而达到节约能量，延长整个网络生命周期的目的。图6 不同的未知节点密度环境下覆盖率、信标节点移动距离比较4、结束语本文针对无线传感器网络移动信标节点定位，讨论了信标节点移动路径规划问题。考虑未知节点与信标节点间的通信及信标节点的移动路径，提出了信标节点向最大覆盖未知节点方向移动的路径规划算法，仿真实验表明，与随机移动算法相比，具有良好的定位性能，能很好地适应大规模随机不均匀撒布节点的应用需求。参考文献1 Lewis Girod, Vladimir Bychkovskiy, Jeremy Elson, and Deborah Estrin. Locating tiny sensors in time and space: A case study. Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD02).2 Andy Harter,Andy HoPPe,Pete Steggles,Andy Ward,Paul Webster.The Anatomy of a Context-Aware Application(1999)Jl.In:Proceedings of Mobile Computing and NetworkingSeattl,Washington USA:SCM Press,1999,8(2)59-68.3 Priyantha NB,Miu AKL,Balakrishnan H,Teller S.The cricket compass for context-aware mobile applicationsC.In:Proc.of the 7th Annual Int1 Conf. On Mobile Computing and Networking. Rome: ACM Press,200l,l-14.4 Sichitiu ML,Ramadurai V. Localization of wireless sensor networks with a mobile beacon .Proc.of the IEEE Intl Conf.on Mobile Ad-Hoc and Sensor Systems. IEEE Computer Society, 2004, :174-183 .5 Patro RK. Localization in wireless sensor network with mobile beacons .Proc.of the23rd IEEE Convention of Electrical and Electronics Engineers. IEEE Computer Society, 2004, :22-24 .6 Sun GL, Guo W. Comparison of distributed localization algorithms for sensor network with a mobile beacon. In: Proc. of the IEEE Intl Conf. on Networking, Sensing and Control. 2004. 536540.7 张正勇,孙智,王刚,余荣,梅顺良.基于移动锚节点的无线传感器网络节点定位J.清华大学学报（自然科学版）.2007,Vol.47.NO.4,234-537.8 Peter Corke , Ron Peterson , Daniela Rus. Localization and navigation assisted by cooperating networked sensors and robot s J . International Journal of Robotics Research ,2005 , 24 (9) : 771-786.9 李石坚,徐从富,杨旸,潘云鹤.面向传感器节点定位的移动信标路径获取J.2008,vol.2,1-13.10 Rui Huang, Zaruba Gergely V. Static path planning for mobile beacons to local