基于蛙跳算法的无线传感器网络定位.docx

刘杰慧，等 基于蛙跳改进算法的无线传感器网络定位
基于蛙跳改进算法的无线传感器网络定位*
刘杰慧，王颖，谢萍，王茜
（华北电力大学 控制与计算机工程学院，北京市102206）

摘要：针对无线传感器网络（WSNs）定位过程当中传统的DV-Hop定位算法在计算锚节点与未知节点之间的平均跳距时存在较大误差的问题，本文根据蛙跳算法（SFLA）计算速度快，全局搜索寻优能力强的优势，结合定位的实际问题，提出了一种改进的蛙跳算法。并将其引入到DV-Hop的算法设计中，实现节点的定位。

关键词：蛙跳算法、无线传感器网络、节点定位、DV-Hop算法
Wireless sensor network localization based on improved algorithm leapfrog
LIU Jie-hui,WANG Ying,XIE Ping,WANG Xi
(School of control and computer engineering, north china electric power university, Beijing, 102206)
Abstract：Exists for wireless sensor networks (WSNs) positioning process of traditional DV-Hop localization algorithm to calculate the average jump between anchor nodes and unknown nodes from the problem when large errors, according to leapfrog algorithm (SFLA) computing speed, global Search optimization capability advantages, combined with the practical problems locating proposed an improved leapfrog algorithm. And introduced into the DV-Hop algorithm design, the realization of positioning nodes.
Keyword：Leapfrog algorithm, wireless sensor network, the node localization, DV - Hop algorithm

0. 引言
无线传感器网络（WSN）[1,2] 是一种新的获取信息和处理信息的技术。其在入侵监测、目标跟踪和定位相关领域有广泛的应用前景。无线传感器网络的许多应用都需要传感器节点明确其自身的位置信息，缺少位置信息的监测消息几乎没有什么价值。这里必须解决的关键问题是如何确定无线传感器网络中节点的位置信息。因此，定位技术[3-5]作为无线传感器网络的关键技术之一，其定位算法也引起了国内外越来越多学者的普遍关注。
目前的无线传感器网络定位技术大体可分为两类，分别是基于测距和非测距的定位技术。DV-Hop算法[6]是现有应用最广泛的无需测距定位算法之一，但是该算法的定位精度不是很理想。就这一问题，已经有很多专家学者对其进行了改进。文献[7]提出由改进DV-Hop算法得到的估算位置然后再利用粒子群优化算法对其进行校正。将定位问题看成一个多维优化问题。文献[8]在分析了DV-Hop算法中多边测量法的基础上，提出了一种自适应人工蜂群算法，并将其应用于未知节点坐标的计算阶段，实现节点定位。文献[9]针对DV-Hop的一种经典改进算法LPC中对影响定位精度的三个重要参数：锚节点数目、节点数目、节点通信半径，进行了进一步优化提高了定位精度。文献[10]针对DV-Hop算法中平均每跳距离的计算方式进行了改进，利用蛙跳算法来求解平均每跳距离，使其更接近实际值，从而提高最终定位结果的精确度。
本文针对DV-Hop算法在计算未知节点坐标是精度不高这一缺陷，将节点定位问题转化成最优化求解问题，结合蛙跳算法的优势，并对蛙跳算法进行了改进，将改进后的蛙跳算法应用到DV-Hop算法中，提出了一种基于改进蛙跳算法的DV-Hop改进方案。通过仿真实验结果表明，改进的算法较传统DV-Hop算法在精度和稳定性上均有明显的提高。
2.DV-Hop算法
DV-Hop算法是由美国路特葛斯大学的Dragos Niculescu等人根据距离矢量路由和GPS定位的思想提出的一种分布式定位算法。其定位过程分为三个步骤：
1) 计算未知节点与锚节点之间的最小跳数。每个锚节点采用距离矢量路由协议向范围内的邻居节点广播其位置信息，其中包括锚节点的坐标和跳数，跳数的初始值为0，接收节点记录到每个锚节点的最小跳数，忽略相同锚节点的较大的跳数信息，将跳数加1后转发给邻居节点，最终获得全网每个节点到每个锚节点的最小跳数。
2) 计算未知节点到锚节点的距离。每个锚节点根据到其它锚节点的坐标信息和最小跳数，根据下式计算出平均跳距：
(1)
式（1）中，Hopsizei是第i个锚节点的平均跳距，（xi，yi），（xj，yj）分别为锚节点i，j的坐标，Sij为锚节点i与j之间的跳数。锚节点计算出平均跳距后并将其广播至网络中，未知节点只记录接收到的第一个平均跳距信息，并转发给邻居节点。未知节点接收到平均跳距后，就可以根据式（2）计算出到锚节点的距离：
(2)
其中，di为未知节点到锚节点的距离，Si为未知节点到锚节点的最小跳数。
3) 当估算出未知节点到锚节点的距离后便可利用三边测量法或极大似然估计法计算未知节点的坐标。式(2)中的di还可以用下列式子表示：
(3)
将方程组中（m-1）个方程分别减去第m个方程之后得到的方程组可用线性表达式AX=b表示，其中X=（x，y）T，
(4)
(5)
使用标准的最小二乘法可以得到方程组的最小二乘解为
(6)
综上所述，由于测距误差、环境因素、通信等因素的影响，di的值总存在一定误差，影响了算法整体的定位精度。
3. 混合蛙跳算法的DV-Hop算法改进
3.1 蛙跳算法描述
蛙跳算法(SFLA)是一种基于群体智能的生物进化算法[11-13]。蛙跳算法模拟了青蛙群体寻找食物时按子群分类进行信息交换的过程，将全局搜索与子群局部搜索相混合，使SFLA能够收敛于全局最优解。蛙跳的基本思想是：
1）种群划分
设有M只蛙组成初始种群体S={X1,X2,…,XM},P维解空间中的第𝑖只蛙表示为Xi=[Xi1,Xi2,…,Xip],在生成初始种群后，按适应度降序排列种群内的青蛙，并将整个种群划分成n个子群，每个子群包含k只青蛙，满足关系M＝n×k；其中第1只青蛙分入第1子群，第2只青蛙分入第2子群，……，第n只青蛙分入第n子群，第n+1只青蛙分入第1子群，第n+2 只青蛙分入第 2 子群。依此类推，直到所有的M只青蛙划分完毕。设 Mj表示第j个族群青蛙的集合，则有
(7)
2）局部搜索
令每个子群中有最好适应值和最差适应值的青蛙分别记为𝑋𝑏和𝑋𝑤，所有子群中适应度最好值的青蛙表示为𝑋𝑔，然后对每个子群进行局部搜索，即只对SFLA算法规定的每个族群中适应度值最差的解𝑋𝑤进行更新，更新策略公式如下:
(8)
(9)
其中，Di表示分量i上移动的距离（1≤i≤p），Dmax表示青蛙所允许改变位置的最大值 ，Xnew为更新后的解，r为0到1之间的随机数。如果Xnew优于Xw，则令Xw=Xnew，否则，用𝑋𝑔代替𝑋𝑏重新按公式（8），（9）执行更新策略，若Xnew仍不能优于Xw，则随机产生一个新的解取代Xw，重复上述过程，直到达到设定的局部搜索次数为止。
3）全局信息交换
当全部的子群完成局部搜索后，将全部子群中的青蛙再混合并重新执行划分子群、局部搜索，如此重复直至达到事前设定好的中止条件（最大混合次数或搜索到最优解）。
3.2 改进的蛙跳算法
在传统蛙跳算法中，由于r的设置仅是在［0,1］之间的随机数，没有考虑到位置更新，具有较大的随机性，导致在寻优过程中存在收敛速度较慢、搜索精度低的问题，严重影响了算法的性能。在位置更新时，较大的r有利于跳出局部极小值点，而较小的r有利于算法的收敛。通常较好的方法是在算法的初期使用较大的r以通过较高的探索能力得到较优的解，而在后期则需要较小的r值，加快其收敛速度。因此将设计为迭代次数逐渐递减的函数，r的设置如下：
(10)
其中，rmin为初始权重，rmax为终止权重，Cmax为最大迭代次数，C为当前迭代次数，则（8）式更新为：
(11)
文献［14］给出用来提高局部搜索空间的青蛙粒子更新策略，但这种更新策略仍然只采用𝑋𝑏，因此并没有提高青蛙学习能力。本文在每个族群进行局部深度搜索时，结合粒子群算法更新思想，将上一次更新的移动距离引入到分量i上移动的距离上，和历史最优个体𝑋k𝑔，因此，（11）式变成：
(12)
(13)
其中，上一次分量i上更新时移动的距离用Di表示，D’i表示本次分量i上更新时移动的距离，群体初始化时，随机产Di生。与(13)式相比，(12)式不仅加大了算法搜索范围，还具备了初步的学习能力。
执行更新策略，若Xnew不能优于Xw，则按下式计算移动距离：
（14）
在传统的蛙跳算法中，如果经过局部或全局最优解更新后若Xnew仍不能优于Xw，则随机产生新的个体替代Xw，这个随机产生的个体增加了算法盲目性，为了改进这一问题，文章通过高斯变异取代随机产生青蛙个体的方法，高斯变异是指在原来的个体的基础上增加一个服从高斯分布的随机扰动，其公式如下：
(15)
其中,N(0，1) 为服从均值为0，均方差为1的高斯分布。
3.3改进DV-Hop定位算法
通过对DV-Hop算法的定位过程分析可知，由于外界因素及内部测量的误差，导致在算法的第三阶段测量锚节点与未知节点间距离时产生误差，因此这就使得di的误差较大。
设Fi为测距的误差，则，再由公式（3）可得：
(16)
从以上求解的过程可以看出，如果使（x，y）最接近真实值，总误差最小，那么就得在由公式（16）计算出来的F(x,y)取最小值，这样就把节点定位问题变成全局最优化求解问题。
在蛙跳算法中适应度函数的设定是寻优求解过程中的关键问题，在锚节点与未知节点测距的过程中产生的误差通常与两节点间的距离有关，即距离越小，产生的误差越小。距离越大，产生的误差越大。因此，本文根据锚节点距离未知位节点的远近来给定权值的大小，给定的权值越大表示距离未知位节点越近，相反越小，不同位置的锚节点对定位结果的影响用给定权值的方法来控制。
基于以上分析，本文给定的适应度函数为：
(17)
其中，cj表示未知节点与锚节点之间距离di的倒数。
由公式(17)可知，未知节点坐标受误差的影响将被降到最低，这样就提高了坐标计算的准确度。
综上所述，本文提出的基于改进蛙跳算法的SFDV-Hop定位算法流程如图1所示。

图1 SFDV-Hop定位算法流程图
4.仿真实验结果分析
4.1仿真实验设计
本文的实验在Matlab平台上进行，假设节点随机分布在一个100m100m的网络区域内，并随机产生未知节点和锚节点的坐标，每个节点的通信半径R=20m，改进蛙跳算法中种群大小100，子群个数10，子群内最大搜索次数为10，最大全局搜索次数为200，rmin=0.4，rmax=1.2，r的初始值设为1，本文分别从平均定位误差均方差和归一化平均定位误差两个指标来衡量算法的定位精确度和稳定性。节点随机分布图如图2所示。

图2节点随机分布图
假设各次仿真时各网络参数均不变，令仿真的次数为k，未知节点的个数为n，节点个数为M，第i个节点的实际坐标和估算坐标分辨用pi和qi表示，则一次实验中所有未知定位节点的平均定位误差和定位误差的均方差分别为：
(18)
(19)
其中，式（18）中的e表示的平均定位误差，式（19）中的φ为所有未知定位节点定位误差的均方差。
令R为节点的通信半径，则基于k次实验统计的归一化平均定位误差为：
(20)
基于k次实验统计的归一化的平均定位误差的均方差分别为：
(21)
为了客观地表现改进DV-Hop算法的定位性能，通过k=500次仿真实验，将改进算法(SFDV-Hop) 与DV-Hop算法进行对比。
4.2实验结果及分析
图3显示了锚节点所占比例在10%-40%时，由式(20)计算出的平均定位误差变化情况；图4显示了锚节点比例变化时，由式(21) 计算出的归一化平均定位误差均方差变化情况。从图3、4可以看出：在节点总数和节点通信半径不变的情况下，两种算法的平均定位误差和均方差均都随着锚节点比例的增加而减小，并逐渐趋于平稳；另外，在相同条件下，SFDV-Hop的平均定位误差和均方差都明显小于DV-Hop。

图3锚节点数量与平均定位误差的关系

图4锚节点数量与定位误差的均方差关系
图5和图6是在实验固定锚节点比例为10%，节点总数从50到400变化的情况下，对不同算法的性能进行了比较，图5、6分别显示了由式(20)计算出的归一化平均定位误差变化情况；由式(21) 计算出的平均定位误差标准差变化情况。从图 5、6图可以看出，在锚节点比例不变的情况下，定位算法的平均定位误差、定位误差均方差都随节点个数的增加而逐渐递减。另外，可以明显的看出SFDV-Hop算法的平均定位误差和均方差都明显小于DV-Hop算法。

图5节点个数与归一化定位算法的平均误差关系

图6节点个数与归一化定位算法误差的均方差关系
从以上的结果分析可以看出SFDV-Hop算法在定位的精确度和稳定性方面都优于DV-Hop算法，说明了将改进蛙跳算法应用在无线传感器网络节点定位上是一种可行的方案，有效地提高了传统DV-Hop算法的全局搜索能力和收敛速度。
5.结论
本文在分析DV-Hop算法中定位过程的基础上，将节点定位问题转化为最优化求解问题，并利用蛙跳算法在解决最优化问题的优势，结合具体问题，对蛙跳算法进行改进，并提出了基于改进蛙跳算法的DV-Hop算法，该定位算法实现简单，搜索速度快。通过仿真实验结果表明，与传统的DV-Hop算法相比，在不同锚节点数目和节点个数的情况下，改进的算法能明显的减小定位时出现的误差，使定位的精度和稳定性得到了有效的提高。
参考文献：
[1]彭宇,王丹. 无线传感器网络定位技术综述[J]. 电子测量与仪器学报,2011,05:389-399.
[2]周雅琴,谭定忠. 无线传感器网络应用及研究现状[J]. 传感器世界,2009,05:35-40.
[3]郭小华. 基于无线传感器网络的车辆定位技术研究[J]. 自动化技术与应用,2009,01:74-77+73.
[4]汪苑,林锦国. 几种常用室内定位技术的探讨[J]. 中国仪器仪表,2011,02:54-57.
[5]刘潇,刘幸,吴胜华. 基于RFID的智能家居用户识别定位技术分析[J]. 物联网技术,2011,09:60-62.
[6]张震,闫连山,刘江涛,李晓银. 基于DV-hop的无线传感器网络定位算法研究[J]. 传感技术学报,2011,10:1469-1472.
[7]赵吉,傅毅,梅娟. 基于粒子群算法的改进DV-Hop定位算法[J]. 计算机应用与软件,2012,12:69-72+76.
[8]李牧东,熊伟,梁青. 基于人工蜂群改进算法的无线传感器网络定位算法[J]. 传感技术学报,2013,02:241-245.
[9]张亚丽,敖珺,陈名松,刘潇忆. 基于DV-HOP的无线传感器网络节点定位算法研究[J]. 计算机与数字工程,2013,01:1-3+104.
[10]葛宇,王学平,梁静. 基于蛙跳算法的DV-Hop定位改进[J]. 计算机应用,2011,04:922-924+1002.
[11] Eusuff M M, Lansey K E 2003 Water Resour, Planning Manag.129 210
[12]许金元. 混合型蛙跳算法及其应用研究[J]. 计算机应用研究,2011,08:2835-2837.
[13]张海玉,刘军,刘志都. 基于混沌优化策略的SFLA算法[J]. 计算机应用研究,2013,06:1708-1711.
[14] Zhang Xuncai,Hu Xuemei,Cui Guangzhao,Wang Yanfeng.et al.An improved shuffled frog leaping algorithm with cognitive behavior[C].//Proc of the 7th World Congress on Intelligent Control and Antomation.New York:IEEE Press,2008:6197-6202