基于进化规划重采样的DV916

基于进化规划重采样的DV-Hop定位改进张万礼，杨小莹，宋启祥宿州学院信息工程学院，安徽宿州234000摘要：针对DV-Hop定位算法中利用三边测量法或极大似然估计法计算未知节点坐标带来的误差问题，本文将稳定性高，收敛速度快且全局寻优能力优异的进化规划算法引入到DV-Hop定位算法中，提出一种基于进化规划重采样的DV-Hop定位改进算法（EvolutionaryProgrammingResamplingDV-Hop,EPRDV-Hop）。在获得未知节点与锚节点的估算距离后，进行位置采样获得未知节点的初始位置估计，然后利用进化规划进行位置的重采样优化，最后通过迭代方式获得未知节点最终的位置估计。仿真结果证明，EPRDV-Hop算法在不增加硬件的情况下，有效提高了节点的定位精度。关键词：无线传感器网络；DV-Hop算法；进化规划；重采样1引言节点位置信息在无线传感器网络（WirelessSensorNetwork，WSN）的各种应用中占据着非常重要的位置。目前的定位算法被分为基于测距和无需测距两大类[1]。DV-Hop[2]算法是一种典型的无需测距定位算法，对硬件要求比较低，计算简单，因此广泛应用于无线传感器网络节点定位中。但该算法存在较大的定位误差，针对此问题，很多学者进行了大量研究。张爱清[3]采用RSSI信号对每跳进行分级的方式修正跳数；温江涛[4]采用采用RSSI信号对第一跳进行分级、节点间的距离比值加权处理其它的跳数的方式修正跳数；肖丽萍[5]通过对未知节点和锚节点间的跳数同时进行修正的方式减低跳数带来的定位误差；冯江[6]通过加权处理平均每跳距离的方式修正跳距带来的误差；王颖[7]根据邻近节点的夹角引入网络平均连通度方式修正节点间的跳距；王新生[8]使用多个锚节点估算的平均跳距离加权处理未知节点的平均跳距方式修正跳距误差；LuQingming[9]加权处理平均每跳距离后计算未知节点坐标；LiWenwen[10]采用差分进化算法求未知节点的坐标位置，李牧东[11]采用人工蜂群算法求未知节点的坐标位置。这些改进算法基本上都是针对定位过程的第一第二阶段带来的误差进行改进。而对定位第三阶段带来的误差的改进较少。本文针对DV-Hop定位第三阶段带来的误差，结合进化规划算法原理，提出了基于进化规划重采样的DV-Hop改进方案。仿真实验表明在不增加额外硬件的条件下，EPRDV-Hop算法的定位精度有较大的提高。2DV-Hop算法2.1定位过程基金项目：国家科技支撑计划项目（2012BAD35B02）;安徽省青年人才基金重点项目(2013SQRL083ZD)；宿州学院科研平台开放课题（2012YKF38）；安徽高校省级自然科学研究重点项目(KJ2014A247)。作者简介：张万礼（1977-），讲师，硕士，主研方向：计算机网络，无线传感器网络。E-mail:[e-mail]-Hop定位算法通过跳数乘以跳距得出未知节点与锚节点之间的估算距离，进而估算出未知节点坐标位置。定位过程分为三个阶段。第一阶段：每个锚节点向网络中广播包含标识号、自身坐标位置和跳数的分组{idi,(xi,yi),hopi}，hopi初始化为0。邻居节点收到后，查看表中是否已有该锚节点信息，如果没有则记录下分组信息，并将hopi+1，然后向其邻居节点转发该分组；如果已经存在并且跳数值比记录表中的跳数值大则忽略该分组。广播结束后，所有节点均获得到每个锚节点的最小跳数值hop。第二阶段：利用第一阶段获得的位置信息和跳数信息，各个锚节点利用式(1)计算平均每跳距离。hopsizei=∑√(xi−xj)2+(yi−yj)2i≠j/∑hopiji≠j(1)其中，(xi,yi),(xj,yj)分别是节点i，j的坐标，hopij为两节点之间的最小跳数。然后将hopsize广播至网络中，未知节点仅记下第一个hopsize，然后利用记录表中的hop与hopsize相乘即可得到每个锚节点的估算距离d。第三阶段：利用三边测量法或极大似然估计法获取未知节点的坐标位置。2.2定位误差分析传统DV-Hop算法中，未知节点获取三个或以上锚节点的估算距离后，利用三边测量法或极大似然估计法确定未知节点的坐标位置。设各锚节点的坐标位置为(x1,y1),(x2,y2),⋯,(xn,yn)，未知节点坐标为(x,y)，未知节点与锚节点的估算距离分别为d1,d2,⋯,dn，则有式(2)成立。{√(x−x1)2+(x−y1)2=d1√(x−x2)2+(x−y2)2=d2⋮√(x−xn)2+(x−yn)2=dn(2)由式(2)的线性表达式为AX=b，其中X=(x,y)T，A=[2(x1−xn)⋮2(xn−1−xn)2(y1−yn)⋮2(yn−1−yn)]，b=[x12−xn2+y12−yn2+dn2−d12⋮xn−12−xn2+yn−12−yn2+dn2−dn−12]。使用标准的最小均方差估计，得出未知节点的坐标为：XT=(ATA)−1ATb。在传统的DV-Hop算法定位第一阶段，获取节点间的最小跳数时，只要通信半径范围内的距离无论远近都记为1跳，无法反映实际距离的大小，利用式(1)计算出来的平均每跳距离必然存在误差，得出的d1，d2，⋯，dn，必然导致误差的累积，因而通过式(2)得到的未知节点坐标误差较大，影响了整个算法的定位精度。记锚节点与未知节点实际距离与估算距离误差为ε，式(2)可变为{√(x−x1)2+(x−y1)2−d1=ε1⋮√(x−xn)2+(x−yn)2−n=εn(3)求解未知节点坐标(x,y)时，只要使ε值取得最小，即式(4)取得最小值，此时求出的未知节点坐标受误差的影响最小，从而提高坐标计算的准确度。Fit(x,y)=∑√(x−xi)2+(x−yi)2−dini=1(4)3EPDV-Hop算法3.1EP算法进化规划(EvolutionaryProgramming,EP)是L.J.Fogel等[12]提出的一种有限状态机进化模型，它通过模仿自然界中生物进化过程来求解预测问题，具有稳健性，智能性等优点，是一种应用很广泛的优化搜索工具。进化规划模型中，采用表示问题的潜在解有限状态机来表示个体。首先产生一个有限状态机群体即父代，其中的每个个体通过变异产生一个子代个体，然后对子代个体进行评估，从父代群体和变异后的子代群体中选择出最好的个体组成新的群体。进化规划算法流程如图1所示。开始随机产生初始种群适应度评价产生机制产生新一代种群是否有满意解是否满足终止条件输出最佳结果结束是是否否图1EP算法流程图从图1可看出，EP算法的实现主要包括：确定问题的表达方式；随机产生初始种群；计算初始个体的适应度值；通过变异、计算新个体适应度、选择这几个操作产生新群体。直至得到满意解或满足终止条件，选择最优个体作为最优解。3.2算法的改进过程EPDV-Hop算法主要思想是：采用进化规划算法取代三边测量法计算未知节点的坐标位置。具体过程如下：(1)位置采样。经过第二阶段后，未知节点通过hop×hopsize获得与锚节点的估算距离。利用位置采样获得未知节点的初次估算坐标位置。假设未知节点的采样位置坐标为S(xsamplei,ysamplei)，则{xsamplei=x+rδicosθiysamplei=y+rδisinθi(5)δi，θi分别代表采样半径和采样角度的随机参数，取值分别区间为[0,1],[0,2π]。选择满足式(6)的采样位置。dj−√(xsamplei−xj)2+(ysamplei−yj)2≤ε(6)dj为锚节点j与未知节点的距离，（xj,yj)为锚节点j的坐标位置。ε为距离误差，可以人为设置，这里设置为3m,采样位置(xsamplei,ysamplei)如果满足式子(6)则被保留下来，否则丢弃。当采样位置数量达到阀值Neff或达到事先设定的最大采样次数时Nmax，停止采样，得到样本数量Ns。未知节点的初始位置估计可通过式(7)计算出来。{x=1Ns∑xsampleiNsj=1y=1Ns∑ysampleiNsj=1(7)(2)基于进化规划的位置重采样对未知节点的初始位置(x,y)利用进化规划算法进行优化。根据误差分析选择合适的估计位置使得式(4)取到最小值。将目标函数取为:G(xi,yi)=min∑(dij−√(x−xi)2+(x−yi)2)2(8)因此对位置的估算转化为求最小值问题即求函数最小问题。所以适应度函数选择为:fit(xi,yi)=1[α+βG(xi,yi)](9)其中α,β为适应度函数的常数系数，取α=β=1。将未知节点采样位置S(xsamplei,ysamplei)作为初始种群，经过进化规划产生未知节点的重采样位置。设未知节点的重采样位置为S′(x′samplei,y′samplei)，则有{S′(t+1)=EP(S,E,S′(t))S′(1)=S=(xsamplei,ysamplei)(10)其中，EP是进化规划，S是选择算子，E是变异算子。①设计变异算子。首先通过标准进化规划的变异运算通过式(11)对每个个体(x,y)作变异操作。{x(t+1)=x(t)+√fit(t)Nx(0,1)y(t+1)=y(t)+√fit(t)Ny(0,1)(11)其中，Nx(0,1)，Ny(0,1)均服从正态分布，为针对(x,y)方向上产生的随机数，fit(t)为旧个体的适应度。②设计选择算子。使用锦标赛选择法作为选择算子。将集合P(t)∪P′(t)记为I，P(t)为μ个父代个体组成的种群，P′(t)为P(t)经过变异运算后得到的μ个子代个体组成的种群。对I中的每个个体Pk=(xk,yk)，从集合I中选择q个其它个体，将Pk的适应度与q个个体的适应度进行比较，将适应度比Pk高的个体数目记为Pk的得分wk，从集合I中选择μ个得分wk最高的个体组成选择后的新一代种群P(t+1)。(3)迭代优化当进化完成后，进入迭代优化阶段。将重采样位置分别代入式(8)，计算出新的位置估计量（x(t+1),y(t+1))。令t←t+1，进入下一轮迭代。直到达到最大迭代次数或满足式(12)时，终止迭代过程。√(x(t+1)−x(t))2+(y(t+1)−y(t))2≤τ(12)其中τ为优化残差，本算法设为1m。经过节点位置估计相互之间不断调整，使得目标函数达到一个可期望的最小值，从而获得比较精确的位置估计。3.3EPRDV-Hop算法实现步骤EPDRV-Hop算法具体实现过程如下：(1)同传统DV-Hop算法第一阶段一样获取各节点间的最小跳数值；(2)同传统DV-Hop算法第二阶段一样计算出未知节点与各锚节点之间的估算距离；(3)随机产生位置采样点S(xsamplei,ysamplei)，求出满足式(6)的采样点，得出初始估计位置(x,y);(4)采样点通过变异和选择操作，产生新一代的重采样位置S′(x′samplei,y′samplei)，将新个体代入适应度式(9)得到新的适应度函数，进行新一轮进化，直到完成指定的进化次数；(5)将进化生成的重采样代入目标函数式(8)，当目标函数取得最小值时，将该新的位置估计取代旧的位置估计，产生新的目标函数，进行下一轮迭代，直到满足终止条件。(6)迭代结束，得到未知节点最终的坐标位置。4定位性能仿真为了验证EPRDV-Hop算法的定位性能，采用MATLAB平台进行仿真实验。设节点随机分布在100m×100m的方形区域中，距离差值ε为5m，最大采样次数为1000，采样个数门限为100，优化残差τ为1m，种群大小为100，选择参数q为30，通信半径为15m。采用定位误差作为本文实验的评价指标，假设未知节点真实坐标和估算坐标分别为(xt,yt),(xe,ye)，通信半径为R，定位误差定义为：err=√(xe−xt)2+(ye−yt)2/R×100%(13)(1)不同锚节点数条件下定位结果的比较要得到较高精度的定位效果，需要足够的锚节点数量，但因为成本因素，一般锚节点数量受到限制。在节点总数为200情况下，锚节点个数由5个逐渐增加至40个，比较EPRD