基于移动信标节点的无线传感器网络 定位算法研究.doc

基于移动信标节点的无线传感器网络 定位算法研究 研究与开发Research&Development51基于移动信标节点的无线传感器网络定位算法研究引言无线传感器网络(Wireless Sensor Network,WSN)1主要用来监测网络部署区域内各种环境特性，如温度、声强、磁场强度、压力运动物体的加速度，但如果这些传感数据不知道相应的位置信息就没有意义，因此，如何确定无线传感器网络中节点的位置信息成为必须解决的关键问题之一。 节点定位的基本原理是通过一定的技术、方法和手段获取无线传感器网络节点的绝对或相对位置信息的过程。 由于每种系统和算法都是用来解决不同的具体问题或者支持不同的应用，它们在网络组成、能量需求2、基础设施等许多方面都有所不同。 目前常用的无线传感器节点定位方法可分为两种3Range-based和Range-free。 前者的特点是较为精确，但计算和通信开销较大；后者的特点是定位精度较低，但各方面开销较小，适用于低功耗、低成本的应用领域。 应用Range-based定位机制的传感器网络中的节点可分为两类一类节点是不具备测量自身坐标能力的节点，我们称其为普通节点或节点，它们构成了网络的主体；另一类节点装备了GPS4之类的定位工具，能够测量自身的坐标，通常被称为参考节点、灯塔节点、信标节点或Beacon，它们散布在整个传感器网络部署的区域中。 通过测量节点到信标节点的距离或角度信息，使用三边测量、三角测量或极大似然估计法就可以计算出节点位置3。 显然，在这种定位方式中，信标节点的排布方式和数量对最终的定位精度影响很大。 但使用的信标节点越多，布设整个网络的开销就越大，所以，在传感器网络中，采用过多的信标节点会造成较大浪费5-6。 鉴于此，提出了基于移动信标(Mobile Beacon,MB)进行节点定位的思想，如图1所示，利用1个或多个信标节点在监测区域中自由移动，然后根据多个测量结果进行定位。 000505050100100100150150150xx00200000505050100100100150150150xx00200(*-锚节点位置，O节点)图1移动锚节点随机路径唐宏钟璐重庆邮电大学移动通信技术重庆市重点实验室重庆400065摘要对移动信标节点的无线传感器定位路径进行研究分析，分析规律性折线路径，随机路径和虚拟力方法路径的缺陷，结合两者优点，提出改进的自适应的动态路径。 采用matlab仿真工具，结合RSSI测距方法以及无线传输模型，对改进算法进行仿真验证，得到更高的覆盖率和更小的误差率，从而减小了网络硬件成本，更能满足无线传感器网络定位的实际应用。 关键词无线传感器网络；定位；移动信标；虚拟力基金资助国家科技重大专项(xxZX03004009)，重庆市科委重点实验室专项经费，重庆市教委优秀成果转化项目Kjzh11206研究与开发Research&Development521移动节点定位算法原理无线传感器网络移动锚节点定位基本流程如图2所示。 图2移动锚节点定位流程锚节点的工作一般分为三个阶段。 1)锚节点i计算到其通信范围内所有节点的距离；2)锚节点估计其范围内节点的位置；3)锚节点移动到下一位置。 1.1RSSI测距接收信号强度(Receive SignalStrength,RSS)3的测距方法是一种低成本的测距技术,也是本文所使用的测距算法的基础。 其基本思想是，已经知道发射信号的强度，接收节点根据自身接收到的信号强度，来计算信号在传播过程中的传播损耗,然后使用理论信号传播模型将无线信号的传播损耗转化为节点之间的距离。 由于无线信号对于复杂环境的适应能力非常弱，所以使用这种方法来测的距离精确度不高。 但是使用这种方法用到的硬件设备简单，而且大多数无线通信模块都可以直接提供RSS的值7。 因此,在现实生活中基于RSSI的测距方法被人们广泛的应用到生活和环境保护之中。 1.2三边测量技术三边测量技术的基本思想2是根据3个已知坐标的节点到节点的距离来确定节点坐标。 已知A、B、C三个节点的坐标分别为()aayx,、()bbyx,和，()yx,它们到节点()yxD,的距离分别为a d、b d和c d，如图3所示。 ABCDdadbdc图3三边测量则通过计算可以得到以下三个式子 (1)()()2b22bbdyyxx=?+? (2)2c22dyyxx=?+? (3)通过高斯消元法写成矩阵形式，可以求出()yxD,，因而达到定位的目标。 注意，A要可逆的必要条件是A、B、C三点不共线。 1.3无线传播损耗模型文献8中提出了一种无线传感器通信范围不规则模型(Degree ofIrregularity,DOI)模型。 在理想情况下，无线传感器节点的传输范围是一个规则的圆形区域，如图4(a)所示。 但实际情况是无线传感器网络中无线传播有一个共同的不可忽视的现象，即通信范围不规则，如图4(b)所示。 它会导致无线电范围丢包的情况，所以我们在定位过程中不得不考虑这样的一个会导致定位误差的问题。 研究与开发Research&Development53-40-xx040-40-30-20-10010203040DOI ModelDOI=0(a)-30-20-100102030-40-30-20-100102030DOI ModelDOI=0.02(b)图4节点实际通信范围1.4锚节点路径获取1.4.1自适应移动锚节点路径获取算法的提出1)移动锚节点静态路径的缺陷。 移动锚节点规律性折线路径9(如图5所示)，折线路径能够在短时间内实现均匀分布，但是如果采用这样的路径在RSSI测距的的情况下，太多的锚节点都在一条直线上，所以能定位的节点数目就小，出现相对覆盖率减小的情况。 2)基于虚拟力的锚节点移动路径获取算法5的缺陷。 上一小节提到的规律性折线路径是一种静态的路径，虚拟力的信标移动路径算法是一种动态路径算法，通过作用在移动节点的虚拟力来确定信标下一站位置，从而获得动态10的锚节点移动路径。 050100150200050100150200(*-锚节点位置，O节点)图5锚节点静态折线路径基于虚拟力的信标移动路径获取算法稳定性差，信标节点受到边界的排斥力、当前通信范围内节点的排斥力、以及当前位置对下一位置节点的排斥力决定。 所以如果出现锚节点跑出监测区域的情况，就很可能回不到监测区域，导致算法不稳定。 虚拟力算法除了稳定性差以外，在定位同等规模的节点的情况下需要的信标节点位置数很多，也就是说信标的移动距离长，能量消耗太大。 1.4.2自适应移动信标获取算法针对规律性折线算法不能很好地躲避障碍物的问题11以及基于虚拟力的移动锚节点路径获取算法的锚节点能量消耗大和不稳定等情况，本文提出了一种新的自适应的锚节点路径获取方法。 自适应路径获取算法分为三个步骤。 1)预设定一条折线路径，估计出信标节点所有存在于折线上的位置，将其作为奇数点的12+k位置。 在一个长和宽都为square_L的矩形监测区域，我们假设step是信标节点每一次移动的长度，即步长。 整个矩形区域折线的条数为num，一条折线段上信标节点研究与开发Research&Development54位置个数为stepLbnum/_= (4)整个矩形监测区域中信标节点的位置个数为 (5)L表示一条折线段的长度，由折线的角度确定。 2)信标节点向周围广播信息包Message_beacon，信息包包括信息位置的id，以及当前移动信标的位置。 3)当在id周围的信息收到Message_beacon信息包之后，节点接收到信息之后能够测量该信息的接收功率，可以根据RSSI线性模型将功率损耗转化为距离dist，并反馈信息给信标节点id。 4)对存在于第12+k位置的信标节点通过虚拟力的方法进行计算信标节点第22+k位置。 节点j(包括前一位置的信标节点也包括节点)对信标节点的作用为 (6)上式为作用力在极坐标上的表现形式，为节点j与id为i的信标节点的角度，k为作用力参数，当节点在当前信标节点R/2范围内的时候为排斥力，即1,0 ()jid,表示信标点i与节点j的距离。 作用在移动信标上的合力为 (7)0S是信标节点i通信范围内节点的集合，1S是信标节点通信范围内1?i位置的信标节点集合。 boundaryiF_是信标节点i收到边界的排斥力，同样与其同边界的距离成反比。 10,是权重参数。 ()oldoldYX,是信标节点i的坐标，根据合力可以计算出信标节点1+i的位置()newnewYX, (8)5)信标移动到下一位置，当节点在位置通信范围内没有任何节点或者说收不到任何节点反馈信息的时候，自动回退到num+1条折线上最近的那个节点位置，并返回第1)步。 2算法性能分析本文采用matlab作为仿真工具，在同样的网络条件下，分别从覆盖率和定位误差等性能方面做了对比分析。 表1是仿真设置的参数，在一个监测区域长和宽都为200m的矩形监测区域，均匀随机分布着100个节点，这些节点的位置需要被测量。 一个锚节点的出发位置在(0,0)，锚节点携带着GPS定位系统，能随时知道自己的位置，可以向各个方向移动并且在移动一定的步长后，停下形成虚拟的锚节点，收集周围位置节点的信息，并对其定位。 节点对锚节点排斥力系数，吸引力系数分别都为0.5，然而在新算法中，预设定的折线路径的锚节点位置对其的吸引力系数为1，这样的参数设置有利于锚节点相对均匀的覆盖整个区域。 表1仿真参数参数值检测区域面积200m200m节点通信范围20m节点个数100个节点对锚节点排斥力系数0.5节点对锚节点吸引力系数0.5预设定的折线位置锚点的吸引力系数1作为改进算法获得的路径的对比，其中有锚节点随机路径，折线路径以及虚拟力方法得到的动态路径。 下面我们分别在一定数量的锚节点位置情况下，对它们得到的覆盖率进行分析。 覆盖率在这里也就是可以定位的节点的规模大小，可以表示为 (9)nnode_是所有节点的个数，ncando_表示研究与开发Research&Development55可以被定位的节点个数，在这里可以定位的个数表示可以收到3个以上不在同一直线上的锚节点位置信息。 从图6可以看出，对于折线方法，虽然能够很快很均匀的覆盖整个区域，但是由于很多锚节点位置都在同一条直线上，所以这些锚节点是不能对节点进行定位的，那么它的相对覆盖率最小。 其次是随机路径，由于它的随机性，有些区域覆盖不了，不能实现均匀覆盖，那么相对覆盖率也较低。 红色方形线代表的是虚拟力的动态路径，这种动态路径具有一定的自适应性，因此比前两种的相对覆盖率高，但是由于它的稳定性差，在相同锚节点位置个数的情况下，它的相对覆盖率比改进算法低10%左右。 改进算法比其他两种算法分别高出了20%和30%的相对覆盖率。 图6相对覆盖率比较由于节点通信范围的不规则性，我们很显然的知道越靠近锚节点的距离误差就越小，整个网络的误差率也与相对覆盖率有关。 我们定义误差率为 (10)假设计算出节点的估计坐标为()estimateestimateyx,，然而节点的真实坐标是()truetrueyx,。 仿真中我们求得的是在一定步长条件下的平均误差，从图7可以看出，改进的新算法获得的路径在步长一定的情况下，误差率最低，其次是虚拟力方法获得路径，随机路径和折线路径。 新路径在步长为20的情况下误差率可以达到20%以下。 图7误差率比较3结束语本文对无线传感器网络基于移动锚节点的定位方法进行了研究，结合了RSSI测量技术和三边估计法，和新改进的集静态路径优点和动态路径优点于一身的新路径，在DOI模型下用matlab进行仿真验证。 结果与随机路径、折线路径和虚拟力方法获得的路径进行对比分析，得到了较高的相对覆盖率和较低的平均定位误差，使得网络硬件成本的锚节点的功率消耗相对降低，所以本文改进的新方法更能适合随机分布的无线传感器网络。 参考文献1王殊,阎毓杰,胡富平,等.无线传感器网络的理论及应用M.北京:北京航空航天大学出版社,xx:143-1662张怡,李云,刘占军,等.无线传感器网络中基于能量的簇首选择改进算法J.重庆邮电大学学报,xx (5):613-6163白进京,严新平,张存保.基于加权质心和DV-Hop混合算法WSN定位方法研究J.计算机应用研究,xx (6):2247-22504罗磊,田增山,孙冬梅,等.基于粒子滤波的姿态测量动态系统设计J.重庆邮电大学学报,xx (5):(a)603-6065Fu Qin,Chen Wei,Liu Kezhong,e tal.Study on Mobile BeaconTrajectory forNode Localizationin Wireless Sensor NetworksC/Proceedings of thexxIEEE研究与开发Research&Development56唐宏博士，教授，硕士生导师，主要研究方向为移动通信、计算机网络。 钟璐硕士研究生在读，主要研究方向为移动通信、计算机网络作者简历Study onLocalization BasedonMobile Beacon in Wireless Sensor Networks TangHongZhong luAbstractAfter studyingon thetrajectory ofa mobilebeacon in wireless sensor works localizationand analyzingdefects ofa statictrajectory,random trajectoryand method of virtualforce,a improvedautomatical algorithmis proposedin thispaper.By simulationtool matlab,bine rangingmethodofRSSI,model ofradio irregularityinwirelesssensorworksand thenovel trajectory,specially.The simulationresult demonstratesthe improvedalgorithm canobtain ahigher coveragerate andless errors.Thus,it isable toreduces costofthehardware andsatisfes theapplication.Keywords WirelessSensor Networks;Localization;Mobile Beacon;Virtual ForceChongqingKey Labof MobileCommunications Technology,Chongqing Universityof Postand Communications(CQUPT),Chongqing400065,ChinaInternational Conferenceon Informationand AutomationJune20-23,Harbin,China6Anushiya A,Kannan,Baris Fidan,et al.Analysis ofFlip Ambiguitisfor RobustSensorNetworkLaocalizationJ.I