移动节点定位的校正步长优化算法

移动节点定位的校正步长优化算法

1基于测距的算法节点定位是基于无线传感器网络（无线传感器网络）的主要应用程序支持技术。对于大多数应用程序来说，具有位置信息的传感器数据具有实际意义。然而WSN节点的计算和通信能力都十分有限而且大量节点的部署往往无法人为控制,因此设计高效的节点定位算法就显得十分重要。美国路特葛斯大学(RutgersUniversity)的DragosNiculescu等人利用距离矢量路由的概念提出APS系列算法,其中的DV-hop成为range-free算法的典型,在之后的研究中被广泛利用和改进。文献提出了一种基于测距的Malguki算法,该算法中的强迫矢量的构建方式与本文所提出的位置校正矢量相似,但是前者对网络通信能力和锚节点的分布具有很强的依赖性,而且单个节点计算量过大,而后者充分利用了所有邻居节点之间的测距信息,算法具有很好的弹性和扩展性。文献和文献都将智能优化算法引入到WSN的定位问题中,其中前者使用了实数编码的遗传算法来求解定位问题,该算法只有在网络连通度很高的情况下才能取得较为理想的定位精度,而且遗传算法的计算量对于节点来说有些偏大;后者提出一种基于模拟退火算法的定位方法,系统的计算量比较大,耗时比较长。综上所述,已有的利用了测距信息的改进算法对于算法性能普遍欠缺综合考虑,对于把高效节能放在重要位置的WSN网络来说还有待改进,而且都没有考率移动节点定位问题。本文提出一种集合了range-free算法、测距技术和智能优化算法的节点定位综合算法,并将其应用于移动节点定位,通过仿真验证了算法具有优良的定位性能,使range-free算法的定位误差大幅下降,节点的通信和计算损耗并没有急剧增加而在可接受的范围内,同时在稀疏网络中也具有良好的校正效果。2提升正矢量的计算基于位置校正矢量(LCV,locationcorrectionvector)的节点定位综合算法首先用DV-hop算法取得粗糙的位置估计,然后利用与所有邻居节点间的测量距离与计算距离的差异构建合成的位置校正矢量,而对于移动节点则使用连续2次测量距离变化值和估计距离变化值的差异来构建LCV;以各锚节点为簇头,把未知节点以最近邻原则分簇,锚节点以最小化簇内距离误差总和的原则,利用改进的粒子群优化(PSO,particleswarmoptimization)算法求得簇内每个节点的校正步长step,未知节点把自身的LCV与step相乘即得到位置校正值;考虑到簇内最优化结果并不能使全局网络最优化,在每个簇的边缘节点与邻簇的边缘节点之间构建附加位置校正矢量,然后由簇头(锚节点)利用自身的位置信息和测距信息得到附加校正步长,将附加LCV与附加step相乘,以此调整簇边缘节点的位置,也就是调整簇与簇的相对位置,以避免局部最优化。2.1出位置校正矢量引入位置校正矢量的概念,在于充分利用由测距信息决定的节点间相对位置关系。未知节点通过DV-hop算法得到自身的估计位置,将其与邻居节点估计位置之间的距离记为“计算距离”;而节点通过RSSI等测距方法得到的与邻居节点间的距离记为“测量距离”。引入位置校正矢量的目的就是通过调整节点的位置,尽可能缩小计算距离与测量距离之间的差别,因此LCV的每个分量沿着未知节点到某个邻居节点的方向,分量的大小为对应的计算距离与测量距离的差值。从物理意义上来讲,当2个相邻未知节点之间的距离计算值小于测量值时,用背向邻居节点的校正矢量来拉远2个节点之间的估计位置;反之,用指向邻居节点的校正矢量来拉近2个节点之间的估计位置。2.1.1节点s回归系数假设节点S通信范围内有N个邻居节点,节点自身的估计位置为Ps=(xs,ys),N个邻居节点的估计位置为Pi=(xi,yi),节点S获得的N个测距值为dmi,i=1,2,…,N。那么节点S与第i个邻居节点的计算距离为dci节点S与第i个邻居节点的差异值的大小可以表示为ui节点S与第i个邻居节点差异值的矢量方向表示为vi因此,节点S的合成LCV为图1是位置校正适量的示意图。2.1.2位置校正过程对于移动节点,初步位置估计方法:移动节点Sm在tk+1时刻的初步估计位置等于其在tk时刻的定位结果的基础上加上移动节点的位置校正用距离变化值代替距离值构建LCV,具体过程如下。假设时刻tk,Sm与第i个邻居节点的计算距离为dcik,测量距离为dmik,而时刻tk+1,计算距离为dcik+1,测量距离为dmik+1,两者的变化值分别为dcik+1-dkci和dmik+1-dkmi,那么差异值可以表示为LCV矢量的合成方法与固定节点相同。2.2校正步长的计算由于每个未知节点同时调整自身的位置,因此LCV只能给出节点位置的调整方向,而沿这个方向移动的距离(将其称之为校正步长)需要通过另外的方法来计算。为了避免集中式算法,同时兼顾节点的能耗,考虑使用分簇的计算方式来获取校正步长。考虑到算法的尽可能简单化和锚节点的计算通信能力比较强,就将每个锚节点作为簇头,未知节点以自身的当前估计位置为准,加入距离最近的锚节点所在的簇。2.2.1求校正步长的问题分簇后,以簇内网络整体位置最优化为目标来计算簇内节点的校正步长。位置校正矢量的作用是使簇内所有邻居节点之间经过位置校正后,计算距离与测量距离差值的总和最小化,因此求校正步长的问题可以描述为一个多元函数最小化问题。假设簇内有N个未知节点,它们的估计位置分别为pi=(xi,yi),LCV分别为,i=1,2,…,N,待求步长为stepi,step是一个由stepi组成的N维向量。问题的目标函数可以表示为其中,;dm_ij为簇内节点i、j之间的距离测量值,dij为簇内节点i、j之间的实际距离,R为节点的通信半径。由于这个目标函数是带有绝对值的高次函数,形式比较复杂,本文引入粒子群算法来求解这个最小化问题。2.2.2适应度函数的建立PSO是一种群智能优化算法,粒子通过跟踪2个“极值”来更新自己,一个是粒子本身所找到的最优解p_Best,另一个是整个种群目前找到的最优解g_Best。PSO很多方面与遗传算法相似,包括初始化种群,适应度函数;与遗传算法比较,在大多数的情况下,所有的粒子可能更快的收敛于最优解,而且PSO容易实现并且没有许多参数需要调整,计算量很小。在本文所述的定位算法中,PSO用来求解校正步长,参数只需要最简单的设置,PSO粒子的长度等于簇内未知节点的个数,每一维分量对应一个节点的校正步长,将前文提到的以校正步长为自变量的目标函数作为适应度函数。考虑到WSN节点的特殊情况,为了减少算法的计算量和运算时间,本文对PSO算法作了改进:在每一次跌代计算粒子的速度之前,比较所有粒子的p_Best,将距离最优解最远的粒子从种群中去除;这样随着跌代次数的增加,离子数呈线性下降,从整个PSO算法的角度来说计算量有明显的下降。2.3附加位置校正矢量由于上述的最优化过程是在各个簇内进行,而簇内节点的相对位置的最优化并不意味着全局网络所有节点的位置实现了最优化,有可能存在簇整体平移或者簇间距离误差反而增大的问题。因此考虑对簇与簇之间的位置进行调整,具体方法如下。由簇的每个边缘节点查找所有不属于本簇但是在自身通信半径内的邻居节点(也就是邻簇的边缘节点),利用它们之间的计算距离和测量距离构建附加位置校正矢量。由于簇头(锚节点)的位置在一定程度上能反映整个簇在全局网络中的位置,因此利用锚节点的测距信息和位置信息来计算附加校正步长,首先用range-free算法计算锚节点的估计位置(过程和未知节点是一样的),然后求其与锚节点真实位置的误差距离,再利用锚节点与周围邻居节点的测距值构建位置校正矢量,将误差距离值除以这个位置校正矢量模值得到的结果作为附加校正步长,簇内所有边缘节点都采用这个附加校正步长。每个簇的边缘节点都通过上述的过程调整自身的位置,以此减小簇与簇的相对位置误差,避免了陷入局部最优化。3该算法的实验和结果3.1节点位置误差Matlab仿真环境设置:在边长为100的正方形区域内随机均匀分布100个未知节点,节点的有效通信半径为20,网络的连通度约为10(连通度是指平均每个节点通信半径内的邻居节点个数,网络的连通度反映了网络的密度,与跳数阈值的选择有直接关系)。仿真中使用的测量距离为真实距离加上一个高斯随机误差,测距误差不超过10%。本文所说的定位误差是指整个网络所有节点平均位置误差与节点通信半径的比值,比如20%的定位误差,即节点平均位置误差为20×20%=4。经过DV-hop仿真实验得到的数据显示,在连通度为10的情况下,跳数阈值为7是最佳选择,且与锚节点密度无关。锚节点密度无限制增加对定位精度没有帮助。后面的仿真实验以这个实验结果为前提,跳数阈值取7跳,锚节点数为16个,锚节点比例为13.8%,在如上参数的条件下,DV-hop算法仿真的定位误差为39.34%,仿真结果如图2(a)所示。图中“+”表示锚节点的位置,每条线段的一端是“o”,表示节点的真实位置,另一端则是定位算法运行后的节点估计位置,线断的长度即表示节点真实位置与估计位置的误差距离。粒子群算法的初始粒子数为20个,粒子群算法的更新次数是10次。图2(b)是以DV-hop为基础的基于LCV和粒子群优化的节点定位综合算法的仿真实验,结果证明该算法定位误差可以减小到9.41%。对于移动节点,假设在坐标系2个方向上每秒移动距离不超过10,且做连续随机的运动。对移动节点以1s为间隔连续进行25次定位,图3显示了2例移动节点未校正的定位结果与校正后的定位结果的差异,横坐标为采样时间点,纵坐标是定位误差,虚线表示校正后的定位结果,实线是校正前的定位结果。3.2低连通度网络定位以上的实验数据均在网络连通度为10的情况下得到,而下面的实验数据表明本提出的算法在低连通度的网络中也具有良好的定位效果。从图4中可以看到,当网络连通度仅为5时,基于LCV的算法依然可以使DV-hop原本的定位误差下降将近50%,当连通度为8时,DV-hop的定位误差已经可以下降60%以上,证明该算法在稀疏的网络中同样有效。3.3锚节点算法复杂度从位置校正矢量的构建和粒子群优化的目标函数的建立过程,很容易得到未知节点和锚节点的计算量都取决于网络的连通度,也就是整个网络的规模。未知节点空间复杂度和时间复杂度都为O(n),而锚节点算法复杂度为O(n2),n为网络的连通度。粒子群算法本身就属于计算量很小的优化算法,而本文中使用的算法中粒子群只需要更新10次,执行一次粒子群算法锚节点所增加的计算时间仅为1.56s,图5显示了算法循环次数与锚节点计算时间以及定位误差的关系。图中显示了随着循环次数的增加,定位误差减小量和锚节点计算时间增加量都成线性增长,定位误差的下降并没有以急剧增加计算量为代价,两者基本上是线性关系,这对于低能耗的WSN节点来说是可以接受的。3.4循环次数对算法结果影响在本文中,对粒子群算法所做的优化使锚节点的运算量降低了约20%,而仿真结果显示定位误差增大量十分有限,而且随着算法循环次数的增加,改进的粒子群算法与原算法结果趋于接近,图6显示了两者计算时间和定位误差的差值随循环次数增加的变化趋势(改