搜索
MATLAB大作业题目：基于蝙蝠算法的DV-Hop算法改进院（系）信息工程学院专业班级12级网络工程本(1)班学号1242158122学生姓名倪峰指导教师陆建银目录1引言--------------------------------------------------------------------------------------------------------------------32DV-Hop定位算法及误差分析---------------------------------------------------------------------------------32.1DV-Hop定位算法工作步骤---------------------------------------------------------------------------32.2DV-Hop定位误差分析---------------------------------------------------------------------------------53BADV-Hop算法的节点定位------------------------------------------------------------------------------------53.1改进的蝙蝠算法-----------------------------------------------------------------------------------------53.2适应值函数设计-----------------------------------------------------------------------------------------63.3BADV-Hop算法的节点定位步骤--------------------------------------------------------------------73.4BADV-Hop算法的工作流程---------------------------------------------------------------------------74仿真实例------------------------------------------------------------------------------------------------------------84.1仿真环境---------------------------------------------------------------------------------------------------84.2结果与分析------------------------------------------------------------------------------------------------95结束语-------------------------------------------------------------------------------------------------------------11摘要:为了减少DV-Hop算法对于无线传感网络的定位误差，我利用编蝠算法(BA)和DV-Hop算法相融合的传感器节点定位方法(BADV-Hop)。在DV-Hop算法的第三阶段，利用编蝠算法代替最小二乘法来计算未知节点的坐标，以降低定位误差。相对于DV-Hop算法，BADV-Hop算法提高了传感器的节点定位精度，具有较高的应用价值，利用MATLAB仿真工具仿真出的结果验证了BADV-Hop的有效性。关键词:DV-Hop算法;编蝠算法;节点定位1引言无线传感器网络的关键技术是节点定位技术，当前传感器节点定位算法分为:距离有关和距离无关的定位算法[2]。距离有关定位算法由于受到外界环境因素的干扰比较大，所以获得的误差较大，且成本高[3];距离无关定位算法主要有质心算法、DV-Hop算法，这类定位算法无需额外硬件支持，功耗低，成为当前主要研究方向[4-5]。DV-Hop算法实现比较简单，只需要少量的锚节点就可以实现对未知节点的定位，备受关注，但是精度有待提高[6]。为此，学者们提出一些改进的DV-Hop算法，如文献[7]中将RSSI策略引入到DV-Hop算法节点距离计算中，减小节点间误差，提高定位精度；文献[8]在DV-Hop算法中引入介质访问机制来调节距离误差;文献[9]通过引入最佳调整因子对每个锚节点计算的距离进行修正，从而减小了平均跳距的计算误差。采用遗传算法、模拟退火算法、蛙跳算法、粒子群算法等群智能算法对DV-Hop算法的误差进行校正，一定程度上提高了DV-Hop算法的定位精度[9-11]。蝙蝠算法(BA)是一种群智能优化算法，在准确性和有效性方面相较其他算法有很大优势，且没有许多参数要调整，为DV-Hop算法误差校正提供了一种新的研究思路[1-2]。为了减少无线传感器网络节点的定位误差，提出一种改进蝙蝠算法(BA)和DV-Hop算法相融合的传感器节点定位方法(BA-DVHop)。在DV-Hop算法的第三阶段，利用蝙蝠算法代替最小二乘法来计算未知节点的坐标，并对蝙蝠算法进行改进避免算法陷入局部最优，最后在Matlab上对算法性能进行仿真分析。仿真结果表明，BADV-hop定位算法在不同锚节点密度、不同通信半径、不同节点数量以及定位精确度等方面表现出良好性能。2DV-Hop定位算法及误差分析2.1DV-Hop定位算法工作步骤第一阶段:计算节点的最小跳数。信标节点向网络发送一个广播信号，邻居节点接收到信号后，记录信标节点的坐标信息，并保存每个信标节点的最小跳数，然后向其他的邻居传感器节点传播，通过该方法，WSN网络中全部节点可以得到信标节点的位置信息和与信标节点间的跳数。第二阶段:估算到信标节点的跳段距离。通过第一阶段后，每个信标节点就可以得到其他信标节点的坐标值和跳数，然后通过式(1)计算平均每跳距离，同时将每跳平均距离广播至网络中，未知节点将平均每跳距离值与最小跳数值相乘，得到其与信标节点间的距离:（1）式中，hi是信标节点i和j之间的跳数，(xi,yi)、(xi,yi)是信标节点i,j的坐标。第三阶段:通过最大似然法计算自身位置。设P1(x1,y1),P2(X2,Y2),…,Pn(Xn,yn)表示n个信标节点的坐标位置，待定位节点位置为(x,y)，其与信标节点估计距离分别为d1,d2,…dn-1，可以建立式(2)的方程:（2）第一个方程组减去最后一个方程后，得到:（3）用线性方程组表示为AL=b，其中:在无线传感器节点测距过程中，不可避免会产生一些随机误差，这样线性方程组为AL+N=b,N为误差向量，最小二乘法的求解方程为:（4）2.2DV-Hop定位误差分析设信标节点（xi，yi），i=1,2，…，n，与未知节点（x，y）的实际距离为ri，i=1,2，∙∙∙，n测距误差为εi,那么|ri−di|εi,i=1,2,∙∙∙,n。根据式（2）可知，（x，y）应该满足如下约束条件：（5）求解（x，y），使得:（6）由于式(5)代表可行解的区域，那么该区域一定存在最优解，且当𝑓(𝑥，y)取最小值时，节点定位总误差最小，此时的坐标（x，y）将为最优值，这样无线网络传感器节点定位问题转化成一个约束优化问题，然后采用BA算法进行求解，提高传感器定位精度。3BADV-Hop算法的节点定位3.1改进的蝙蝠算法2010年，有学者通过模拟蝙蝠回声定位行为而提出的蝙蝠算法(BA)，其在迭代寻优方面相较其他群智能算法有很大优势。BA算法首先对所有蝙蝠的位置和速度随机初始化，其中位置是待求解问题的潜在解，然后通过适应度函数评价群体，找出群体最优个体(最优解);接着分别按式(9)更新个体的脉冲频率、速度和位置:（7）式中，Fi、Fmax和Fmin分别表示第i只蝙蝠在当前时刻发出的脉冲频率、脉冲频率的最大值和最小值，βϵ[0,1]是一个服从均匀分布的随机因子，x∗为最优蝙蝠位置。据生物学知识，在初始阶段蝙蝠脉冲频度低且声响大，有助于在大范围内搜索目标，发现猎物后，逐渐使声响变小并增加脉冲频度以便精确掌握猎物的空间位置，因此声响和脉冲频度随着运行进行而不断地更新，公式如下:（8）其中，0a1,y0，均为常量。随机飞动产生新解xi的公式为:xnew=xold+εAt（9）式中，εϵ[−1,1]是一个随机变量：At是所有蝙蝠在此步中平均声音响度。对BA算法原理进行分析可知，BA算法缺乏有效的变异机制，群体容易聚集于局部极值，导致早熟收敛，因此本文对其进行改进，并将其用于解决无线传感网节点定位问题，以提高定位精度。具体改进如下:（1）蝙蝠通过调整频率F得到新的位置，在频率公式(4)中，εϵ[−1,1]区间内均匀分布的随机因子，其实质上是个体的变异操作，在一定的程度上使种群保持多样性，β是变异因子，其值越大，对新构建的解贡献越大;反之，值越小，对新构建的解贡献越小，控制好β值能提高种群多样性，避免早熟，从而提高算法的求精能力。因此本文采用动态自适应机制调整变异因子β，公式如下:（10）式中，fbest(i)是第i代最佳的适应度值;fworst(i)是第i代中最差的适应度值;(fbest(i)−fworst(i))/fbest(i)表示变异因子根据每代中最佳和最差适应度值完成自适应的调整。(2)当randRi时，基本BA算法是通过随机飞动产生新解xi，相关研究表明，位置移动机制对算法优化精度、收敛速度有重要影响，基本BA算法中，蝙蝠移动后的位置目标函数值可能比原来的更差，因此，改进BA算法考虑以概率Pa∈[0,1]抛弃最差的解，然后再用随机飞动重新生成相同数量的新解。(3)当基本BA算法进行了n次迭代，最小值无变化或者变化很小，算法可能陷入局部最优，因此改进BA算法在n3且当前解的变化很小(1E-3)时，则考虑在当前解的基础上以莱维随机游动方式进行扰动，以扩大种群的搜索范围，评价并保留较好的解。莱维飞行是一种特殊的随机行走行为，体现出的是一类非高斯随机过程，其平稳增量服从Lévy稳定分布，则有蝙蝠位置更新公式为:（11）式中，xik表示第i个蝙蝠在第k代的位置;a0表示步长控制量;⊕表示点对点乘法;Lévy(λ)为Lévyflights随机搜寻路径，且服从Lévy概率分布:Lévy(λ)~u=k−λ。3.2适应值函数设计蝙蝠算法在优化的过程中，通过蝙蝠的适应度值来判断蝙蝠所处位置的优劣，蝙蝠算法种群中的每一个蝙蝠是未知节点的一个候选解，适应值函数计算公式为:（12）式中，m为锚节点的个数，ωi为未知节点与第i个锚节点测量距离的权重，其值与未知节点到锚节点的跳数hi成反比，h由Dv-Hop算法的第一阶段获得，未知节点的估计距离是通过最小化适应度函数的目标值来决定的。3.3BADV-Hop算法的节点定位步骤(1)在目标区域随机部署节点，先运用Dv-Hop算法的第一、二阶段定位方法，通过节点间相互通信，确保每个未知节点都接收并保存其到各锚节点的跳数h和网络跳距d。(2)在目标区域内随机初始化蝙蝠种群，种群中的每个蝙蝠都是当前未知节点位置的一个可行解，根据式(12)计算每个个体的适应值，保存群体最优位置x,以及群体最优值f(x∗)。(3)用式(7)调整搜索脉冲频率F，并计算蝙蝠个体的飞行速度v，更新蝙蝠的空间位置x。(4)产生随机数rand，如果randR，则接受新位置x，否则，按发现概率P。丢弃差的个体，用式(11)产生新的位置替代丢弃的位置。(5)如果(randA;)&&f(x;)f(x,)，则移动至更新后的位置，然后按式(10)更新脉冲频度R和声响A。(6)判断是否出现连续3次f(x,)变化量小于1E-3的现象，若是，则转步骤（6），否则，转步骤（8