无线传感器网络节点协作分布式相对定位算法

无线传感器网络节点协作分布式相对定位算法

无线传感器网络的节点受到能耗和低利率的限制。许多节点不能通过外部方法（gps）获取位置信息，但没有位置数据的节点信息通常没有实际意义。因此，节点的定位应该通过节点的合作和位置来计算。节点通常随机分布在特定的区域，受节点分布、消息冲突、障碍物等因素的影响，一些节点无法满足位置计算的条件，而是迷失了自己的节点。为了解决这个问题，提出了相对定位联合算法的方法，并将二次集群和三边定位结合起来，以提高节点的效率。1节点分簇、节点局部转换与节点局部失效相对定位算法的定位过程一般是以网络中一部分位置特殊的未知节点作为参考节点建立坐标系,其余节点通过消息传递和相互协作获得自身与参考节点的相对位置并计算相对坐标.对于基于距离的相对定位算法,由于存在测距误差,节点间大范围的消息传递会造成误差累积.将节点分簇进行定位的方法可以减少测距误差的累积.分簇算法一般是通过在网络中选取多个参考节点分别建立局部相对坐标系,其余节点在获取局部的相对坐标之后运用坐标变换或矢量计算的方法实现坐标统一.分簇方法实现定位只在局部区域进行消息传输,多跳传递较少,能减少计算过程中的累积误差.但是节点簇转换过程受到局部区域失效节点的影响比较严重,一旦节点簇内协助转换的节点失效,将会导致整个节点簇都无法定位.通过二次分簇增加邻居节点簇数量,结合三边定位方法增加协助转换节点数量,可以解决转换过程受节点局部失效影响而导致的节点簇失效问题.由于大部分节点簇只需一次转换就实现最终定位,减少了重复转换,一方面能降低通信量,另一方面能够增强算法对节点分布的适应性.2相对定位算法2.1跳段距离的计算法国巴黎大学的FaridBenbadis等人提出的GFF算法是一种距离无关算法.该算法使用类似DV-hop算法中距离矢量路由的思想,通过跳数估算节点之间的距离.主要流程是在靠近网络边界的区域选取三个点作为参考节点建立一个全局相对坐标系.其余节点接收自身到三个参考节点的最小跳数,然后以跳数代替直线距离使用三边定位法计算坐标.该算法实现简单,定位过程不涉及复杂运算,对硬件要求较低.不过该算法要求节点密度较高,并且和DV-hop定位算法一样,以跳段距离代替直线距离,存在一定的误差.2.2确定相对坐标系美国密苏里大学哥伦比亚分校的XiaoliLi等人提出的Map-growing算法是基于距离的算法,该算法通过递归调用三边定位法实现节点坐标获取.首先在网络中节点密度较大的区域选取一个点作为相对坐标系的坐标原点,在其邻居节点里面选取两个点构建相对坐标系,选取原则是三点能构成一个良好三角形(三个内角都大于30度).能同时与这三个节点直接通信的未知节点通过三边定位方法计算得出坐标,其余节点只要有三个邻居节点已经实现定位,就能够使用相同的方法计算坐标并将坐标信息发布,直至所有满足条件的节点都实现定位.该算法通信量小,在节点密集的区域能获得较高的节点定位覆盖率,并且对节点分布没有特殊要求.但是受到测距误差累积的影响,远离坐标原点的节点定位误差较大.2.3聚类pet算法美国仁斯利尔理工学院RajagopalIyengar等人提出的聚类SPA算法是典型的分簇定位算法,算法采用TOA测距方式,定位过程分局部坐标建立阶段和全局坐标转换阶段两步.算法开始运行之后,通过自身携带的定时器选取主节点,主节点一跳以内的其它节点声明为该主节点的从节点.主节点随机选择互为邻居节点的两个从节点建立局部坐标系,并计算得到其他从节点的局部坐标.在坐标转换阶段,主节点ID号大的节点簇向ID号比它小的相邻节点簇转换,最终以ID号最小的主节点为原点建立全局坐标系.聚类SPA算法通过分簇建立局部坐标,使得执行坐标变换的是每个节点簇,相比于每个节点都需要参与转换的算法,通信量和计算量得到了降低,并减少了测距误差的累积.但是该算法对节点密度和节点分布都有较高要求,在节点密度不高且分布不均匀的区域,失效节点较多.相对定位算法无需锚节点,适合于远距离信号接收受限或有障碍物阻隔的区域.但是现有相对定位算法往往需要在高节点密度和较规则的网络拓扑结构中才能获得比较好的定位效果,一定程度上限制了相对定位算法的应用.3节点合作算法针对现有算法对节点密度和节点分布要求较高的情况,提出通过节点协作分簇方式实现定位,以降低节点密度和节点分布对定位结果的影响.3.1节点分布不均匀对节点定位覆盖率的影响对聚类SPA算法节点失效进行分析.在局部坐标定位阶段,在定时器计时完成之后生成节点簇,簇的主节点为坐标原点,收到两个主节点声明的节点为边界节点.局部坐标系中任一个点都需要除原点以外的两个已知局部坐标的邻居节点才能计算自身坐标,将无法满足该计算条件的从节点记作第一类失效节点.由于边界节点处于节点簇边缘地带,更容易成为第一类失效节点.在坐标转换阶段,受到节点分布和第一类失效节点的影响,一些邻居节点簇无法找到两个以上的有效边界节点(获得局部坐标的边界节点)以实现转换.节点簇转换一旦失败,该簇的从节点都会成为失效节点,将这类失效节点记作第二类失效节点.由于以簇为单位,第二类失效节点比第一类失效节点数量多,对节点定位覆盖率有很大影响.由于通过定时器确定主节点是随机的,程序每次运行都会产生不同的主节点.为了验证主节点位置分布的不同对聚类SPA算法的影响,以及第一类失效节点和最终定位节点数量的关系,在节点分布不变的情况下,重复运行程序10次,得出第一类失效节点与节点定位覆盖率的关系,如表1所示.运行环境设定为20m×20m的区域上随机布置100个节点,节点密度为0.25,节点通信半径为3m.10次运行结果显示,100个节点中第一类失效节点最多占到16%,但是由于其中大部分,甚至全部都是边界节点失效,导致后一步的坐标变换难以完成,再加上节点分布不均匀对算法的影响,使得节点定位覆盖率偏低,最多不超过35%.综合分析可知,用于协助转换的有效边界节点数量不足是定位结果不理想的主要原因.在局部坐标建立阶段尽量减少第一类失效边界节点数量,并在坐标转换阶段增加新的边界节点有助于减少失效节点数量,提高节点定位覆盖率.3.2局部定位功能基于上述的分析,提出一种以聚类SPA算法分簇思想为基础,通过节点协作定位,辅以三边定位实现节点之间相对坐标获取的节点协作分布式相对定位算法ADRP(AssistantandDistributedRelativePositioningAlgorithm).算法使用TOA技术测量邻居节点间距,分局部坐标建立阶段和全局坐标转换阶段两步.(1)局部坐标建立阶段.使用定时器确定主节点及节点簇,收到两个以上主节点声明的从节点为边界节点.图1为节点分簇示意图,O为主节点,M为距离主节点O最近的从节点,N是M的邻居节点中距离O点最近的从节点.将M点和N点作为辅助节点构建局部坐标系MON,如图1所示,图中实线连接的两点距离可测距得到,虚线则表示所连接的两点不是邻居节点.在局部区域内,节点分布相对规则,以距离主节点最近的点确定x轴和y轴,实现简单,且有利于覆盖大部分从节点.图中节点J同时与M和N为邻居节点,通过余弦公式可得θ1、θ2、θ3,根据三个角之间关系以及主节点O与节点J之间的距离dOJ求出未知节点J在局部坐标系中的坐标值,具体如式(1).对于与节点M和节点N都不是邻居节点的从节点需要在已经获取坐标的节点中重新取两个点进行定位.⎧⎩⎨⎪⎪x=dOJ×cosθ2θ1=|θ2−θ3|⇒y=dOJ×sinθ2θ1≠|θ2−θ3|⇒y=−dOJ×sinθ2(1){x=dΟJ×cosθ2θ1=|θ2-θ3|⇒y=dΟJ×sinθ2θ1≠|θ2-θ3|⇒y=-dΟJ×sinθ2(1)局部坐标建立完成之后,获得局部坐标的从节点组成集合ue6e6(MON).没有获得局部坐标的节点分两种情况,第一种是只有一个邻居节点计算得出局部坐标,第二种是没有邻居节点实现局部定位.对于第一种情况,可以通过排除法定位.例如在图1中,节点P的邻居节点中只有节点L获得局部坐标,由于条件不足,通过计算出现P和P’两个待定结果,二者以OL为中轴相互对称.由于在集合ue6e6(MON)内只有节点L和主节点O在节点P通信范围内,若有第三个节点能与待定位置通信,可将该位置排除.ue6e6(MON)中的节点将两个待定位置分别进行计算,通过节点M可将错误结果P’排除,从而节点P的局部坐标得以确定,同时节点P也加入ue6e6(MON)协助其余从节点实现定位,以减少第一类失效节点的产生.(2)全局网络坐标转换.当所有的局部坐标系建立完成之后,相邻节点簇数量最多的节点簇声明为主簇,其主节点声明为全局网络的坐标原点,同时主簇内所有获得局部坐标的从节点升级为已定位节点,其他的节点簇根据距离主簇的远近逐步完成坐标变换,主要分为两步.第一步:对于与主簇相邻,并与主簇有两个以上有效边界节点的节点簇,可以利用文献中提出的方法向主簇进行坐标变换,其它的节点簇等待转换消息.完成坐标变换的节点簇声明为已定位簇,同时更新坐标.为了使无法直接进行坐标转换的节点簇实现定位,将已定位的节点簇与主簇合并,进行二次分簇.如图2所示,节点簇k和n实现定位以后与主簇i结合,形成簇集A.在A中边界节点使用转换以后的新坐标向外发布坐标消息,其余未定位簇只要与簇集A有两个有效边界节点,即可实现定位.在图2中,节点p是节点簇m与节点簇k的有效边界节点,节点q是节点簇m与节点簇n的有效边界节点,这样便可通过p和q协助节点簇m定位.p和q发布的坐标信息是已经更新的新坐标,所以簇m将直接和主簇进行坐标变换,这样只需要转换一次即可完成最终定位,减少了计算量和多次坐标转换带来的计算累积误差.转换完成后,节点簇m也加入簇集A中,协助相邻分簇定位.二次分簇方法使得未知节点簇可以通过多个相邻的已定位簇协作定位,减少了失效边界节点对定位的影响.分簇转换过程需要传递大量的消息,采用二次分簇方法可以减少转换次数,达到降低通信量的目的.在图3所示的局部网络拓扑中,4号节点簇和1、3号节点簇相邻,5号节点簇和2、3号节点簇相邻,并假设1号节点簇首先实现定位.聚类SPA算法是以主节点ID号由大到小转换为原则,最终所有节点的相对坐标都应该以1号节点簇主节点为原点,每次转换中各簇需要向ID号比它小的邻居簇转换一次.以5号节点簇为例,在第一次转换中,分别向3号和2号转换一次,以此类推,图3的局部网络需要8次转换才能完成定位;并且1号节点簇在不同位置所需转换的次数不同,最差的情况是高ID的主节点需要向局部区域内每个ID号比它低的主节点都转换一次才能实现定位,进一步增加了通信量.二次分簇方法所采取的转换顺序是:4向1转换,3向4转换,5向3转换,2向5转换.经过4次转换即可实现定位,而且1号节点簇的位置变化只会导致转换顺序的不同,转换次数不会改变.二次分簇方法始终以最少转换次数实现定位,减少了通信量和计算量,并使算法具有更好的稳定性.第二步:完成第一步之后,网络中还没有实现定位的未定位簇可分为与簇集A有一个有效边界节点的C簇,和与簇集A没有有效边界节点的D簇.节点簇发布声明消息,相互之间能取得联系的未定位簇构成节点域.各节点域中主节点ID号最小的C簇声明为原点簇,与原点簇相邻且具有两个以上有效边界节点的未定位簇直接向原点簇进行转换.对于无法直接转换的节点簇需要升级新的边界节点协助转换.节点簇中与从节点相邻的已经在主簇内实现局部定位的节点数量记为z.如果z≥3,则该从节点可以通过三边定位法计算得出自身在主簇中的局部坐标,进而升级为新的边界节点协助节点簇转换.节点簇转换完成后加入簇集B,并使用二次分簇的方法将簇集B扩展,如图4所示.最终形成的簇集B只要包括两个C簇即可完成定位,进一步减少失效节点.通过节点协作和升级新的边界节点的定位方式,使得各局部坐标系受失效边界节点的影响减小,同时减少了第二类失效节点的数量,提高了节点定位覆盖率,增强了算法对网络拓扑变化的适应性.4节点位置变化的适应性利用NS-2网络仿真软件,从通信量、网络拓扑结构适应性和节点定位覆盖率三个方面分析比较ADRP与聚类SPA算法.图5和图6是二者分别在30m×30m和40m×40m区域内的通信量比较,环境设定节点均匀分布,通信半径为2m,节点之间通信无障碍.图5和图6表明,ADRP算法的通信量低于聚类SPA算法,并且随着节点数量的增加,差距逐渐明显.由于ADRP算法在坐标转换阶段需要转换的次数少,减少了多余转换产生的通信量,随着节点簇数量增多,二次分簇方法优势逐渐明显,通信量的差距逐渐加大.图7是两种算法在主节点位置适应性方面的对比.设定节点区域为20m×20m,节点通信半径3m.在网络节点分布不变的情况下,对两种算法分别运行10次以对比节点定位覆盖率.由于主节点由定时器随机选择,每次运行时主节点位置都会有所变化,通过图7的实验结果可以得出两种算法对主节点位置变化的适应性.区域设定随机分布100个节点,节点密度为0.25,网络连通度为6,图中横轴为执行次数.图8是在节点密度较低时节点定位覆盖率的对比,节点区域和通信半径与图7相同,每一个节点密度下随机运行20次取均值以减少主节点位置变动的影响.如图7所示,ADRP算法的节点定位覆盖率是聚类SPA的两倍左右,而且曲线波动不大,性能相对稳定.聚类SPA算法受到主节点位置变动的影响较大,曲线波动严重,且定位节点数量不多.聚类SPA算法由于节点簇之间单独进行转换,转换过程是否能顺利进行很大程度上取决于主节点的位置,从而导致曲线较大的波动.ADRP算法采取不同主节点间不断合并、相互协作的定位方式,主节点位置变动对算法稳定性的影响较小.图8以节点密度对算法性能的影响为出发点,不考虑主节点位置变动对算法产生的影响,为了获得较为平均的结果,在每个节点密度上都经过多次运行,因此所得曲线较为平滑.聚类SPA算法对应的节点定位覆盖率较低,并在有些位置出现了一些波动.相比之下,ADRP算法对应的曲线很少出现大的跳动,在节点密度较低的情况下,ADRP算法也能实现大部分节点定位,节点定位覆盖率平均值在75%