基于dv-oh的锚节点位置校正

基于dv-oh的锚节点位置校正

0节点定位算法无线传感器网络（无线传感器网络）集成了传感器技术、嵌入式控制技术、无线传感器网络技术、分布式数据处理技术和电子技术。这是目前的一个新兴和热点研究领域。节点定位是无线传感器网络的关键应用支撑技术,对于大多数应用来说,带有位置信息的传感数据才具有实际意义,随着无线传感器网络技术的不断进步,会出现更多基于位置信息的协议和应用。然而WSN节点的计算和通信能力都十分有限而且大量节点的部署往往无法人为控制,因此设计高效的节点定位算法就显得十分重要。非基于测距(range-free)的算法原理简单,但是定位比较粗糙,而目前几乎所有节点的无线射频模块都具有获取信号接收强度指示值(ReceivedSignalStrengthIndex,RSSI)的能力,在range-free算法基础上使用测距技术对节点估计位置进一步求精是一种比较有效的定位机制,近年来不少学者也将各种智能计算方法引入到WSN的节点定位问题中来,设计综合的定位算法是一种新的思路。1智能算法的改进文献利用距离矢量路由的概念提出APS系列算法,其中的DV-Hop成为range-free算法的典型,在之后的研究中被广泛利用。文献提出了一种Malguki算法,该算法中的强迫矢量的构建方式与本文所提出的位置校正矢量(LocationCorrectionVector,LCV)相似,但是前者对网络通信能力和锚节点的分布具有很强的依赖性,而且单个节点计算量过大;而后者充分利用了所有邻居节点之间的测距信息,算法具有很好的弹性和扩展性。文献都将智能优化算法引入到WSN的定位问题中,其中前者使用了实数编码的遗传算法,该算法只有在网络连通度很高的情况下才能取得较为理想的定位精度,而且遗传算法的计算量对于节点来说有些偏大;后者提出一种基于模拟退火算法的定位方法,系统的计算量比较大,耗时比较长。综上所述,已有的这些改进对于算法性能普遍欠缺综合考虑,对于把高效节能放在重要位置的WSN来说还有待改进。本文提出一种集合了range-free算法、测距技术和智能优化算法的节点定位综合算法,并通过仿真实验证明它具有优良的定位性能。2轴分类质控算法本文提出一种基于位置校正矢量的节点定位综合算法,首先用DV-Hop算法取得粗糙的节点位置估计,然后对邻居节点间RSSI的测量距离与估计位置间的计算距离进行比较,构建一个位置校正矢量(只有方向);以各锚节点为簇头,把未知节点以最近邻原则分簇,锚节点以最小化簇内距离误差总和的原则,利用改进的粒子群优化算法(ParticleSwarmOptimization,PSO)求得簇内每个节点的校正步长Step,未知节点把自身的LCV与Step相乘即得到位置校正值,节点当前的估计位置加上这个位置校正值就得到新的估计位置;考虑到簇内最优化结果并不能使全局网络最优化,在每个簇的边缘节点与邻簇的边缘节点之间构建附加位置校正矢量,然后由簇头利用自身的位置和测距信息得到附加校正步长,将附加LCV与附加Step的乘积作为簇边缘节点的位置调整附加值,也就是调整簇与簇的相对位置,以避免局部最优化。2.1节点s的合成lcv本文引入位置校正矢量的概念,目的在于充分利用由测距信息得到的节点间相对位置关系,来校正节点的估计位置。未知节点通过range-free算法得到自身的估计位置,同时可以通过通信获取邻居节点的估计位置,把两个估计位置之间的距离记为“计算距离”;而未知节点通过接收邻居节点发来的数据包可以获得信号强度值RSSI,从而得到两者之间的“测量距离”。引入位置校正矢量的目的就是通过调整节点的位置,尽可能缩小计算距离与测量距离之间的差距,因此LCV的每个分量的方向由未知节点指向某个邻居节点,分量大小为对应的计算距离减去测量距离。从物理意义上来讲,当两个相邻未知节点之间的距离计算值小于测量值时,用背向邻居节点的校正矢量来拉远两个节点之间的估计位置;反之,则用指向邻居节点的校正矢量来拉近两个节点之间的估计位置。假设节点S通信范围内有N个邻居节点,节点自身的估计位置为PS=(xS,yS),N个邻居节点的估计位置为Pi=(xi,yi),节点S获得的N个测距值为dmi(i=1,2,…,N)。那么节点S与第i个邻居节点的计算距离为dci:节点S与第i个邻居节点的差异值可以表示为diffi:diffi=dci-dmi(2)节点S与第i个邻居节点差异值的矢量方向表示为vi:vi→=pSpi−→−∥pSpi−→−∥(3)vi→=pSpi→∥pSpi→∥(3)因此,节点S的合成LCV为VS:VS−→=∑idiffi×vi→VS→=∑idiffi×vi→;i=1,2,…,N(4)图1中,实线表示节点实际位置,虚线表示节点估计位置,细箭头是校正矢量的分量,粗箭头表示合成的校正矢量。2.2计算每相线的方法来计算由于每个未知节点同时调整自身的位置,因此LCV只能给出节点位置的调整方向,而沿这个方向移动的距离(我们称之为校正步长)需要通过另外的方法来计算。如果直接从全局网络最优化的角度计算所有节点的校正步长,不符合无线传感器网络分布式计算的原则,而如果由每个节点单独计算自身的校正步长,那么计算量又太大而且不能兼顾其他节点的位置调整情况,因此我们考虑使用分簇的计算方式来获取校正步长。同时,考虑到算法的尽可能简单化和锚节点的计算通信能力比较强,将每个锚节点作为簇头,未知节点以自身的当前估计位置为准,加入距离最近的锚节点所在的簇。2.2.1目标函数的建立分簇后,以簇内网络整体位置最优化为目标来计算簇内节点的校正步长。位置校正矢量的作用是使簇内所有邻居节点之间经过位置校正后,计算距离与测量距离差值的总和最小化,因此求校正步长的问题可以描述为一个多元函数最小化问题。假设簇内有Nm个未知节点,它们的估计位置分别为pmi=(xmi,ymi),LCV分别为Vmi−→−(i=1,2‚⋯‚Nm)Vmi→(i=1,2‚⋯‚Νm),待求步长为Step。问题的目标函数可以表示为:F(Step)=∑ijdisij≤R|∥p′mip′mj−→−−−−∥−dmij|(5)F(Step)=∑ijdisij≤R|∥p′mip′mj→∥-dmij|(5)其中:p′mi=pmi+Step×Vmi−→−‚p′mj=pmj+Step×Vmj−→−‚dmijp′mi=pmi+Step×Vmi→‚p′mj=pmj+Step×Vmj→‚dmij为簇内节点i,j之间的RSSI距离测量值,disij为簇内节点i,j之间的实际距离,R为节点的通信半径。由于这个目标函数是带有绝对值的高次函数,形式比较复杂,本文引入粒子群算法来求解这个最小化问题。2.2.2适应度函数的建立PSO是一种群智能优化算法,粒子通过跟踪两个“极值”来更新自己,一个是粒子本身所找到的最优解p_Best,另一个是整个种群目前找到的最优解g_Best。PSO很多方面与遗传算法相似,但与遗传算法比较,在大多数情况下,所有的粒子可能更快地收敛于最优解,而且PSO容易实现,并且没有许多参数需要调整,计算量很小。在本文所述的定位算法中,PSO用来求解校正步长,PSO粒子的长度等于簇内未知节点的个数,每一维分量对应一个节点的校正步长,将前文提到的以校正步长为自变量的目标函数作为适应度函数。考虑到WSN节点的特殊情况,为了减少算法的计算量和运算时间,本文对PSO算法作了改进:在每一次迭代计算粒子的速度之前,比较所有粒子的p_Best,将离最优解最远的粒子从种群中去除,这样从整个PSO算法的角度来说计算量有明显下降。2.3打造附加位置校正由于上述的最优化过程是在各个簇内进行,簇内的距离误差总和最小只能使簇内节点的相对位置在一定程度上最优化,而并不意味着全局网络所有节点的位置实现了最优化,可能存在簇间距离误差反而增大的问题。因此考虑对簇与簇之间的位置进行调整,具体方法如下。由簇的每个边缘节点查找所有不属于本簇但是在自身通信半径内的所有邻居节点(也就是邻簇的边缘节点),利用它们之间的计算距离和测量距离构建一个附加位置校正矢量。由于簇头(锚节点)的位置在一定程度上能反映整个簇在全局网络中的位置,因此我们利用锚节点的自身信息来计算附加位置校正矢量的步长:首先计算锚节点的估计位置与其真实位置的误差距离,再利用锚节点与其邻居节点的测距值构建锚节点的位置校正矢量,将误差距离值除以这个位置校正矢量模值得到的结果作为附加校正步长,簇内所有边缘节点都采用这个附加校正步长调整自身位置,以减小簇与簇的相对位置误差,避免了陷入局部最优。3在网络连通度为10时，节点的跳数阈值选取在对基于LCV的节点定位综合算法仿真之前,本文先对DV-Hop算法的锚节点数和跳数阈值的选取作了研究。Matlab仿真环境设置:在边长为100的正方形区域内随机均匀分布100个未知节点,节点的有效通信半径为20,网络的连通度约为10(连通度是指平均每个节点通信半径内的邻居节点个数,网络的连通度反映了网络的密度)。仿真中使用的RSSI测量距离为真实距离加上一个高斯随机误差。本文所说的定位误差是指整个网络所有节点平均位置误差与通信半径的比值,比如20%的定位误差,即节点平均位置误差为20×20%=4。锚节点的个数分别选取9,16,25,对应的锚节点密度分别为8.2%,13.8%,20%,锚节点和未知节点一样,也是随机均匀分布在网络中。跳数阈值的选择范围为5到10,定位误差的实验结果如表1和图2。对实验结果的图表进行分析,可以得出以下几个结论:1)在连通度为10的情况下,跳数阈值为7是最佳选择,且与锚节点密度无关。2)跳数阈值增大不一定使定位误差下降,远处锚节点的信息对定位不一定起正面作用。3)锚节点达到一定密度时,再增加锚节点对定位精度的提高帮助很小,因此无限制地增加锚节点是没有意义的。以上三点结论,反映了以DV-Hop为典型的基于距离矢量路由的定位算法的特点,对于选取这种类型定位算法的参数具有明确的指导意义。后面的仿真实验以这个实验结果为前提,即跳数阈值取7,锚节点数为16,锚节点比例为13.8%,在如上参数的条件下,DV-Hop算法仿真的定位误差为39.34%,仿真结果如图2(a)。图中“+”表示锚节点的位置,每条线段的一端是“○”,表示节点的真实位置,另一端则是定位算法运行后的节点估计位置,线段的长度即表示节点真实位置与估计位置的误差距离。图2(b)是以DV-Hop为基础的基于LCV的节点定位综合算法的仿真实验,结果证明该算法定位误差可以减小到9.41%,图3就是仿真结果。以上的实验数据均在网络连通度为10的情况下得到,而下面的实验数据表明本文提出的算法在低连通度的网络中也具有良好的定位效果。从图3中可以看到,当网络连通度仅为5时,基于LCV的算法依然可以使DV-Hop原本的定位误差下降将近50%;当连通度为8时,DV-Hop的定位误差已经可以下降60%以上,证明