基于矢量的无线传感器网络节点定位综合算法

第11期王驭风等：基于矢量的无线传感器网络节点定位综合算法·231·基于矢量的无线传感器网络节点定位综合算法王驭风，王岩（北京航空航天大学 自动化学院，北京 100083）摘 要：基于DV-hop设计了一种节点的定位综合算法，并将其应用于移动节点。利用节点间估计距离和测量距离的差异构建位置校正矢量；通过改进的粒子群优化方法得到节点的校正步长；节点将其与位置校正矢量的乘积作为自身位置的校正值。通过仿真进行算法验证并分析了复杂度和有效性，结果证明该算法可以将DV-hop的定位误差下降75%，并且适用于稀疏网络。关键词：无线传感器网络；定位；移动节点；位置校正矢量；粒子群优化；DV-hop中图分类号：TP393 文献标识码：A 文章编号：1000-436X(2008)11-0227-05Integrated algorithm based on vectors in node localization for wireless sensor networks WANG Yu-feng, WANG Yan（School of Automation, Beijing University of Aeronautics and Astronautics, Beijing 100083,China）Abstract: An integrated algorithm based on DV-hop was designed and applied to mobile nodes. A location correction vector（LCV）was constructed by the differences between estimated distances and range measurements; an improved particle swarm optimization (PSO) was used to find correction steps of nodes; location correction equaled the value of LCV multiplying step. The algorithm and its complexity and validity had been approved through simulation，the results show that the localization error of DV-hop has been reduced by 75% using the algorithm, and it is also applicable to low-density networks.Key words: wireless sensor networks; localization; mobile node; location correction vector; particle swarm optimization; DV-hop1 引言收稿日期：2008-05-21；修回日期：2008-10-20基金项目：国家自然科学基金资助项目（60674053）Foundation Item: The National Natural Science Foundation of China (60674053)节点定位是无线传感器网络(WSN, wireless sensor networks) 1的关键应用支撑技术，对于大多数应用来说，带有位置信息的传感数据才具有实际意义。然而WSN节点的计算和通信能力都十分有限而且大量节点的部署往往无法人为控制，因此设计高效的节点定位算法2就显得十分重要。美国路特葛斯大学(Rutgers University)的Dragos Niculescu等人利用距离矢量路由的概念提出APS3系列算法，其中的DV-hop4成为range-free算法的典型，在之后的研究中被广泛利用和改进。文献5提出了一种基于测距的Malguki算法，该算法中的强迫矢量的构建方式与本文所提出的位置校正矢量相似，但是前者对网络通信能力和锚节点的分布具有很强的依赖性，而且单个节点计算量过大，而后者充分利用了所有邻居节点之间的测距信息，算法具有很好的弹性和扩展性。文献6和文献7都将智能优化算法引入到WSN的定位问题中，其中前者使用了实数编码的遗传算法来求解定位问题，该算法只有在网络连通度很高的情况下才能取得较为理想的定位精度，而且遗传算法的计算量对于节点来说有些偏大；后者提出一种基于模拟退火算法的定位方法，系统的计算量比较大，耗时比较长。综上所述，已有的利用了测距信息的改进算法对于算法性能普遍欠缺综合考虑，对于把高效节能放在重要位置的WSN网络来说还有待改进，而且都没有考率移动节点定位问题。本文提出一种集合了range-free算法、测距技术和智能优化算法的节点定位综合算法，并将其应用于移动节点定位，通过仿真验证了算法具有优良的定位性能，使range-free算法的定位误差大幅下降，节点的通信和计算损耗并没有急剧增加而在可接受的范围内，同时在稀疏网络中也具有良好的校正效果。2 基于校正矢量和粒子群优化的节点定位综合算法基于位置校正矢量（LCV, location correction vector）的节点定位综合算法首先用DV-hop算法取得粗糙的位置估计，然后利用与所有邻居节点间的测量距离与计算距离的差异构建合成的位置校正矢量，而对于移动节点则使用连续2次测量距离变化值和估计距离变化值的差异来构建LCV；以各锚节点为簇头，把未知节点以最近邻原则分簇，锚节点以最小化簇内距离误差总和的原则，利用改进的粒子群优化（PSO, particle swarm optimization）算法求得簇内每个节点的校正步长step，未知节点把自身的LCV与step相乘即得到位置校正值；考虑到簇内最优化结果并不能使全局网络最优化，在每个簇的边缘节点与邻簇的边缘节点之间构建附加位置校正矢量，然后由簇头（锚节点）利用自身的位置信息和测距信息得到附加校正步长，将附加LCV与附加step相乘，以此调整簇边缘节点的位置，也就是调整簇与簇的相对位置，以避免局部最优化。2.1 位置校正矢量（LCV）引入位置校正矢量的概念，在于充分利用由测距信息决定的节点间相对位置关系。未知节点通过DV-hop算法得到自身的估计位置，将其与邻居节点估计位置之间的距离记为“计算距离”；而节点通过RSSI等测距方法得到的与邻居节点间的距离记为“测量距离” 。引入位置校正矢量的目的就是通过调整节点的位置，尽可能缩小计算距离与测量距离之间的差别，因此LCV的每个分量沿着未知节点到某个邻居节点的方向，分量的大小为对应的计算距离与测量距离的差值。从物理意义上来讲，当2个相邻未知节点之间的距离计算值小于测量值时，用背向邻居节点的校正矢量来拉远2个节点之间的估计位置；反之，用指向邻居节点的校正矢量来拉近2个节点之间的估计位置。2.1.1 固定节点的位置校正矢量假设节点S通信范围内有N个邻居节点，节点自身的估计位置为，个邻居节点的估计位置为，节点S获得的N个测距值为，。那么节点S与第i个邻居节点的计算距离为(1)节点S与第i个邻居节点的差异值的大小可以表示为(2)节点S与第i个邻居节点差异值的矢量方向表示为(3)因此，节点S的合成LCV为，(4)图1是位置校正适量的示意图。图1 位置校正矢量示意图（实线表示节点实际位置，虚线表示节点估计位置；细箭头是校正矢量的分量，粗箭头表示合成的校正矢量）2.1.2 移动节点的位置校正矢量对于移动节点，初步位置估计方法：移动节点在时刻的初步估计位置等于其在时刻的定位结果的基础上加上(5)移动节点的位置校正用距离变化值代替距离值构建LCV，具体过程如下。假设时刻，与第i个邻居节点的计算距离为，测量距离为，而时刻，计算距离为，测量距离为，两者的变化值分别为和，那么差异值可以表示为(6)LCV矢量的合成方法与固定节点相同。2.2 分簇计算校正步长由于每个未知节点同时调整自身的位置，因此LCV只能给出节点位置的调整方向，而沿这个方向移动的距离（将其称之为校正步长）需要通过另外的方法来计算。为了避免集中式算法，同时兼顾节点的能耗，考虑使用分簇的计算方式来获取校正步长。考虑到算法的尽可能简单化和锚节点的计算通信能力比较强，就将每个锚节点作为簇头，未知节点以自身的当前估计位置为准，加入距离最近的锚节点所在的簇。2.2.1 问题描述分簇后，以簇内网络整体位置最优化为目标来计算簇内节点的校正步长。位置校正矢量的作用是使簇内所有邻居节点之间经过位置校正后，计算距离与测量距离差值的总和最小化，因此求校正步长的问题可以描述为一个多元函数最小化问题。假设簇内有个未知节点，它们的估计位置分别为，LCV分别为，待求步长为，是一个由stepi组成的维向量。问题的目标函数可以表示为(5)其中，；为簇内节点i、j之间的距离测量值，为簇内节点i、j之间的实际距离，为节点的通信半径。由于这个目标函数是带有绝对值的高次函数，形式比较复杂，本文引入粒子群算法来求解这个最小化问题。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例移动节点未校正的定位结果与校正后的定位结果的差异，横坐标为采样时间点，纵坐标是定位误差，虚线表示校正后的定位结果，实线是校正前的定位结果。(a) DV-hop定位结果(b) 基于LCV的算法定位结果图2 DV-hop和基于LCV的节点定位综合算法的定位结果比较图3 移动节点位置校正前后的定位结果差异3.2 低连通度的网络定位以上的实验数据均在网络连通度为10的情况下得到，而下面的实验数据表明本提出的算法在低连通度的网络中也具有良好的定位效果。从图4中可以看到，当网络连通度仅为5时，基于LCV的算法依然可以使DV-hop原本的定位误差下降将近50%，当连通度为8时，DV-hop的定位误差已经可以下降60%以上，证明该算法在稀疏的网络中同样有效。图4 不同连通度下的算法定位效果3.3 算法复杂度及定位耗时从位置校正矢量的构建和粒子群优化的目标函数的建立过程，很容易得到未知节点和锚节点的计算量都取决于网络的连通度，也就是整个网络的规模。未知节点空间复杂度和时间复杂度都为，而锚节点算法复杂度为，为网络的连通度。粒子群算法本身就属于计算量很小的优化算法，而本文中使用的算法中粒子群只需要更新10次，执行一次粒子群算法锚节点所增加的计算时间仅为1.56s，图5显示了算法循环次数与锚节点计算时间以及定位误差的关系。图中显示了随着循环次数的增加，定位误差减图5 算法循环次数与锚节点计算时间以及定位误差的关系小量和锚节点计算时间增加量都成线性增长，定位误差的下降并没有以急剧增加计算量为代价，两者基本上是线性关系，这对于低能耗的WSN节点来说是可以接受的。3.4 改进的粒子群算法对算法消耗的影响在本文中，对粒子群算法所做的优化使锚节点的运算量降低了约20%，而仿真结果显示定位误差增大量十分有限，而且随着算法循环次数的增加，改进的粒子群算法与原算法结果趋于接近，图6显示了两者计算时间和定位误差的差值随循环次数增加的变化趋势（改进后算法减去原算法所得）。(a) 粒子群算法改进对计算时间的影响(b) 粒子群算法改进对定位误差的影响图6 粒子群算法改进对算法有效性的影响4 结束语在DV-hop算法的基础上，本文结合测距技术和改进的粒子群优化算法，提出了一种基于位置校正矢量的节点定位综合算法，并将其应用于移动节点。仿真实验证明在不明显增大通信和计算损耗的前提下，该算法相比于DV-hop的定位误差可以下降75%，达到小于10%的误差，已经具有实际的应用价值。虽然本文仅以DV-hop为基础进行了仿真实验，但基于位置校正矢量的算法思想同样可以用在Convex、APIT等算法上以对节点作进一步定位，是一种普遍适用的精化算法。（下转第236页）