基于混合蛙跳的无线传感器网络定位方法

江宇波，赵攀，邱玲

（四川理工学院计算机学院，四川自贡643000）

基于混合蛙跳的无线传感器网络定位方法

江宇波，赵攀，邱玲

（四川理工学院计算机学院，四川自贡643000）

为了解决无线传感器网络未知节点的定位问题，提出了一种新的三维空间定位方法。首先给出了未知节点位置的计算方法和误差评价模型，并利用混合蛙跳算法建立了评价模型的求解算法SFLL。最后，利用仿真实验，对比了与其它算法之间的性能状况，结果表明SFLL具有较好的适应性。

无线传感器网络；定位；最小二乘法；混合蛙跳

引言

随着无线传感器网络（Wireless Sensor Network，WSN）的发展和物联网技术的兴起，对未知节点的定位逐渐成为了研究的热点和重点［1-2］。目前，定位算法可以分为距离和非距离两种方法。距离定位算法根据未知节点与锚节点的距离，并结合三边或者多边角方法来确定未知节点位置，主要有RSSI算法［3］、TOA算法［4］等。而基于非距离定位算法则根据未知节点与锚节点之间的邻接关系来定位，典型代表有质心算法［5］、MDS－MAP算法［6］等。最近，基于距离的定位算法又有了更新的发展，如最小二乘定位算法［7］，采用负梯度搜索等优化算法进行定位，不仅所需锚节点比例较少，而且定位精度更高。

在上述工作的基础上，本文提出了一种新的三维空间的定位算法和误差评价模型。该模型利用混合蛙跳算法对评价函数进行求解，同时通过数学仿真对比研究了该算法与RSSI（Received Signal Strength Indicator）算法、TOA（Time Of Arrival）算法之间的性能状况，以此验证该模型的有效性。

1 节点定位方法

假设某无线传感器网络中存在N个节点，其中M个为锚节点，坐标信息通过GPS定位系统确定，如图1所示，其中M代表锚节点，N代表未知节点。由于受到能量、成本等因素限制，只有少量节点可以成为锚节点，其余节点需要通过锚节点进行定位。距离定位算法［8-9］利用三边法或最大似然估计法，并结合信号强度来获取未知节点与锚节点之间的距离，但此方法只适用于锚节点个数大于3的情况。因此，本文基于三维空间提出了一种新的无线传感器网络节点定位算法，其思路是：首先根据能量和传输距离将网络节点划分成多个簇，其次根据每个簇内的锚节点对未知节点进行定位。

在初始情况下，令所有节点功能相同、能量有限、通信功率可调。首先将节点划分成簇，簇内节点之间均采用直接通信方式，而簇间则可以选择直接或间接等方式通信，以达到能耗最低和效率最高的目的。根据LEACH协议，需要在各簇中产生簇首节点。对于各节点随机生成（0，1）之间的常数ε及阈值J，如果ε＜J，则将当前节点加入候选簇首集合并向周围节点进行广播。如果在相邻区域内存在多个候选簇首节点，那么比较当前这些节点的剩余能量，剩余能量大者作为簇首节点，其余为普通节点。这里，阈值J定义为：

其中，p为簇首节点占总节点的比例，E0为节点i的初始能量，λ为距离比例，dm为最大阈值，φ为常系数（0＜φ＜1），Ee为发送或接收1比特信息时所消耗的能量，η为在单位距离内的信道上传输1比特信息时所消耗的能量，d为节点之间相距距离。

此时，按照产生的簇首节点集合，以各簇首节点为中心、R为半径的球体来划分簇结构。如果某节点位于多个球体交界处，那么以距某簇首节点距离最短作为划分标准，如图1中虚线代表簇边界。

假设簇内数据转发只需1跳，而转发到相邻簇则需要2跳。由各个簇内锚节点的分布状况，定位未知节点位置可分为以下几种情况：

（1）簇内存在2个以上锚节点

此时，可以通过最小二乘法进行求解。假设未知节点N的坐标为（x，y，z），锚节点Mi（i＝1，2，…，k，k≥3）的坐标为（xi，yi，zi），那么未知节点Node与锚节Mi之间的测量距离ri满足：

由于存在多于3个已知锚节点信息，对上述方程进行求解可得到如下形式：

（2）簇内存在2个锚节点

假设这2个锚节点坐标分别为M1（x1，y1，z1）和M2（x2，y2，z2），根据公式（2）计算它与未知节点之间的测量距离r1和r2。同时分别以这两个锚节点为中心、r1和r2为半径的作出两球区域，在连接球心的轴线上，取其中心点位置为新增临时锚节点M3（x3，y3，z3），当两球体相交时，其坐标为：

当两球体不相交时：根据锚节点M1（x1，y1，z1）、M2（x2，y2，z2）和M3（x3，y3，z3）信息，利用标准最小二乘法可获得未知节点坐标信息。

（3）簇内存在2个以下锚节点

此时由于锚节点距离未知节点较远，只能利用上述2个锚节点定位方法进行计算，其定位误差将增大。

2 算法描述

对于上述方法，其关键在于求解测量距离ri。但是由于GPS定位误差以及计算结果的近似处理，未知节点位置会存在一定偏差。假设位置节点与锚节点之间实际距离为di，误差为εi，那么满足越小代表定位精度越高，当εi→0时，定位算法获得最优解。因此，本文首先建立目标函数：

其约束条件为：

由此，本文结合混合蛙跳算法对上述方法进行求解。混合蛙跳算法是一种群体智能的生物进化算法［10-11］，它模拟了青蛙群体寻找食物时按族群分类进行信息交换的过程，算法将群体分割为多个族群，在族群内部和簇群之间进行更新操作。各族群内部搜索和全局信息交换一直持续交替进行到满足收敛条件或达到最大迭代次数为止。本文结合混合蛙跳算法给出目标函数的求解算法（Shuffled Frog Leaping－based Localization algorithm，SFLL），其步骤如下：

（1）定义混合蛙跳算法的适应度函数来衡量当前解的优劣：

（2）初始化，确定t＝0时WSN的各项参数。并令青蛙个体初始数目为a，将目标函数F视作青蛙个体，测量距离ri视作表示青蛙个体移动步长，最大迭代次数为MAXT；

（3）随机产生初始种群，计算个体适应度。然后将个体按照适应度值大小进行降序排列，并按以下原则分配到s个族群中：第1个个体放入第1个族群，第2个个体放入第2个族群，…，第s个个体放入第s个族群，第s＋1个个体放入第1个族群，这样一直循环，直至所有个体分配完毕；

（4）在每一个族群中，适应度最优解和最差解是以其适应函数值的最大和最小值来确定的，记为Fopt（s）和Fwst（s），并将所有族群Fopt（s）的最大值作为种群的全局最优解Fopt；

（5）在每个族群内部进行如式的内部搜索：

其中，a为（0，1）之间的系数，rnewi表示青蛙个体更新之后的移动步长。如果Fwst（s）发生改变，则使用新的Fwst（s），否则将Fopt（s）换成Fopt来重新执行内部搜索；如果仍没有改变，则随机产生（Fwst（s），Fopt（s））之间的任意数来替换Fwst（s）；

（6）当所有族群内部更新完成后，令t＝t＋1并跳转到步骤（3），重新划分族群和执行更新操作，直到达到最大迭代次数MAXT；

（7）输出当前最优解，即为预测误差极小值；

（8）算法结束。

3 仿真实验

对于本文提出的SFLL算法，利用NS2和MATLAB进行仿真实验来验证其有效性。这里基于NS2建立如图1所示的仿真拓扑结构，设置三维空间大小为100 m×100m×100m，节点数目100个，并划分为15个栅格，测距半径为10 m。同时令青蛙个体初始数目为100个，共有15个族群，最大迭代次数为200。这里将本文提出的SFLL算法与传统的RSSI（Received Signal Strength Indicator）算法、TOA（Time Of Arrival）算法进行对比。

首先研究平均定位误差与锚节点通信半径之间的关系。图2给出了这三种算法对应的平均定位误差与锚节点通信半径之间的关系。由图2可以看出，随着锚节点通信半径的增加，平均定位误差逐渐减低，直至平稳。这与通常理解是一致的，若锚节点通信半径可以增大到整个区域空间，那么该区域内将不存在盲区，那么平均定位误差趋于0。而当达到相同平均定位误差时，SFLL算法所需的锚节点通信半径更小。

其次，对比分析锚节点数量对平均定位误差的影响情况（图3）。令ρ表示锚节点数量与总节点数量的比值，从图3可以看出，当ρ增加时平均定位误差呈现递减趋势，这与通常的理解一致。加大锚节点在空间区域中的密度，使得网络中的盲点区域减少，可以获得更大的定位精度，但是此时将会加大系统开销成本。所以在实际应用中，应综合各种因素来考虑锚节点密度。并且从图3中可以看出，在相同密度下，SFLL算法计算得到的平均定位误差最小，而TOA算法精度最差，说明SFLL算法具有一定的精度优势。

最后，深入分析影响SFLL算法的关键因素。图4给出了不同青蛙簇群数量s下平均定位误差的变化趋势。在仿真初始阶段，簇群数越大对应的平均定位误差越小，而在仿真后期情况发生突变，簇群数越大对应的平均定位误差越大。这是因为初始阶段青蛙个体性能普遍较低，此时簇群数越大即意味着簇内个体越小，个体性能更新速度将越快；而在仿真后期，随着整体性能的提供啊，此时簇群数越小可以有效扩大个体寻优的目标，避免陷入局部最优。

4 结束语

为了有效解决无线传感器网络中未知节点定位精度的问题，本文结合最小二乘法建立了三维空间的定位算法SFLL。首先将WSN节点划分成簇，并根据簇内锚节点数量给出了未知节点坐标的具体计算方法和误差评价模型，同时利用混合蛙跳算法对评价模型进行求解。最后通过进行数学仿真，深入研究了该算法与其他算法之间的性能差异，结果表明SFLL具有较好的适应性。

［1］Wang W,Srinivasan V,Wang B,et al.Coverage for target localization in w ireless sensor neworks［J］.IEEE Transactions on W ireless Communications,2008,7（2）：667-676.

［2］冯晨.无线传感器网络定位精度优化方法研究［D］.南京：南京邮电大学,2013.

［3］詹杰,刘宏立,刘述钢,等.基于RSSI的动态权重定位算法研究［J］.电子学报,2011,39（1）：82-88.

［4］孟令军,王宏涛,夏善红.WSN节点声测距TOA值频域估计方法［J］.电子与信息学报,2010,32（4）：993-997.

［5］宫娜娜,王缓缓.无线传感器网络质心算法的最佳通信半径［J］.计算机仿真,2013,30（5）：203-207.

［6］马震,刘云,沈波.分布式无线传感器网络定位算法MDS-MAP（D）［J］.通信学报,2008,29（6）：57-62.

［7］匡兴红,邵惠鹤.基于传感器网络的气体源定位方法研究［J］.系统仿真学报,2007,19（7）：1464-1467.

［8］丁卫平,王建东,管致锦.基于量子蛙跳协同进化的粗糙属性快速约简［J］.电子学报,2011,39（11）：2597-2603.

［9］杨维剑,王梅英.无线网络传感器中超低功耗节点能源技术研究［J］.四川理工学院学报：自然科学版, 2010,23（1）：44-47.

［10］葛宇,王学平,梁静.基于蛙跳算法的DV-Hop定位改进［J］.计算机应用,2011,31（4）：922-924.

［11］葛宇,梁静,许波,等.基于蛙跳算法的无线传感器网络节点定位［J］.计算机工程与应用,2012,48（20）：126-130.

Node Localization Method ofW ireless Sensor Network Based on Shuffled Frog Leaping

JIANG Yubo，ZHAO Pan，QIU Ling
（School of Computer Science，Sichuan University of Science＆Engineering，Zigong 643000，China）

In order tomitigate the node localization accuracy in wireless sensor network，a new three-dimensional localization method is proposed.At first，the calculationmethod and error evaluationmodel of unknown node is presented.Then，an evaluation algorithm SFLL is proposed by shuffled frog leaping.At last，amathematic simulation is conducted.Compared to the performances of other algorithms，the results show that SFLL has better adaptability.

wireless sensor network；localization；Least Squares；Shuffled Frog Leaping

TP393

A

1673-1549（2014）04-0034-04

10.11863／j.suse.2014.04.09

2014-05-05

四川省教育厅重点项目（13ZA0118）；人工智能四川省重点实验室开放基金项目（2012RYY02）；四川理工学院培育项目（2012PY13）；企业信息化与物联网检测技术四川省高校重点实验室项目（2013WYJ01）

江宇波（1982-），男，四川自贡人，助理实验师，硕士，主要从事计算机网络通信方面的研究，（E-mail）598256382＠qq.com