董铮　张其林　吴中博　吴继广

摘要：针对无线传感器网络算法定位精度不高的问题，提出一种定位算法（GADO），该算法将动力学中进化计算和遗传算法中迭代优选相结合。用GADO算法求解网络信标节点与经典的DV-hop定位算法、遗传算法进行对比，改进的算法定位误差明显减少，精度更好。

关键词：动力学；遗传算法；定位算法；精度

中图分类号：TP391

文献标志码：A

文章编号：1006-8228（2017）01-27-03

0.引言

随着数据业务的快速发展，人们对目标定位与导航的需求日益增长。定位领域吸引了越来越多的科技工作者的广泛关注与深入研究。

无线传感器网络的定位，可以简单地描述为：用已知数量的节点来计算出未知节点的距离信息。根据定位是否需要对节点问的距离进行测量，可以分为基于测距的定位算法和非测距的定位算法；根据节点位置信息表达的形式，分为绝对定位算法和相对定位算法；根据网络中位置节点的定位状态的不同，分为静止节点定位和移动节点辅助定位。其中，免距离测量的DV-Hop算法的定位技术只利用网络内部的连通性就可以实现未知节点的定位方法，已受到广大学者的重视。

1.DV-Hop算法描述

1.1算法实现过程

DV-Hop算法主要由以下三个阶段组成。

（1）利用典型的距离矢量路由协议，使网络所有定位节点获得参考节点跳数信息。

其中（x_i，y_i）为第j个参考节点的位置，h_j为第j个参考节点到第i个参考节点的跳数，将其结果作为一个校正值广播至网络中。当待定位节点获得三个或更多参考节点距离后，使用三边或多边测量定位。因其采用简单的平均单跳距离和最小跳数信息来估计节点问的距离。偏差较大的节点距离参与定位过程计算，会引入更大的误差，使得定位精度大大降低，这也是其算法不足之处。

2.改进的遗传优化算法

遗传算法是以群体解为起点，通过选择的方式选取具有较高适应度的个体再次进入循环圈，而被选择的个体再经过交叉产生新的个体，变异操作用于保持种群的多样性。通过新的群体不断替代旧的群体的进化过程，实现群体适应度值的提高。

动力学算法是受复杂系统自组织临界生物演化模型发展而来的一种自组织优化算法，选择当前解中适应度最差的变量及其相互关联的变量进行变异，从而使整个优化系统向自组织临界状态演化。

普通遗传算法只是针对无约束问题，需要的种群多，收敛速度慢。对于一般为有约束优化的，设计问题需进行转换。为解决这一问题，把动力学中表现的局部优化能力与普通遗传算法的全局搜索功能相结合，提出GADO算法（dynamization optimization and geneticalgorithm），其实质就是寻找未知节点与已知节点实际距离与估计距离的最小误差，达到对节点的准确估计。

2.2 GADO算法实现步骤

针对传统文献[4]中计算每跳估算粒度太粗，提出以下算法。

（1）网络初始化，其参数变量有以下。

SW：监测区域边长

NN：定义节点个数

CD：定义通信距离

AL（X，Y）：定義节点坐标矩阵（包括横坐际，纵坐标）

（2）在初始t时刻将节点空间等分。

（5）将得到的优良节点中，随机选择两个相互独立的个体节点进行杂交，产生新解。

（6）判断对新解是否变异，判断条件为p_i

（7）由最佳个体和新生个体形成与原始规模相等的新一代群体节点。

重复（3）-（7）步骤直至平均适度趋于稳定。

3.仿真评价

为检验GADO算法的性能指标，将传统文献Dv-hop算法、文献遗传GA算法和GADO算法在Matlab7.11平台进行仿真对比分析。其模型参数如下。

（1）在100*100的区域内布撒节点；

（2）节点通讯半径均取50m；

（3）所有节点坐标用随机函数分布；

（4）节点比例为0.03～0.15。

将GADO算法及DV-hop算法在平均定位误差和覆盖率作为评价指标，并与文献[4-5]作对比（为保证实验结果精确性，性能仿真都是100次的仿真结果）。

3.1网络连通度对精度影响

图1为传统DV-hop定位算法、遗传算法和GADO算法的仿真结果，从图1可以看出，当连通为12时，三种算法误差都会降低，这时已知节点都能较好定位未知节点，但GADO算法明显优于其他两种算法，而随着连通度增加，相隔跳数的估计距离出现误差，因此精度都有所下降，但GADO算法其下降幅度较为缓慢，这是由于其算法对节点进行优选，舍弃一些平均距离差的节点。本文算法较文献[4]Dv-hop算法而言，整体平均误差降低8%，比文献[5]遗传算法降低5.43%。

3.2节点数目对定位精度的影响

图2为三种算法中的已知节点比例对定位误差的影响，从中看出，随着节点数目增加，其各自误差均有所提高，其原因是网络连通度提高，算法精度均有所提高，但GADO算法始终优于传统算法，较文献Dv-hop算法，整体平均误差降低12.6%，比文献遗传算法降低4.6%。

3.3节点数目对覆盖率的影响

从图3可以看出，当节点数目500，已知节点个数在20-35内变化时，节点比率与网络完整率成正比率关系，而且GADO算法明显优于其他算法。在节点比率小时，GADO算法显示出覆盖率较大的特性，而随着节点比率增大，与DV-hop算法、GA算法逐渐趋于一致。这也与实际情况相符。并且覆盖比率随已知节点个数整体比文献[4]提高了11.3%，比文献[5]遗传算法提高了2.2%。

4.结束语

为提高节点定位精度，在不增加网络通信开销的前提下，提出一种基于GADO的无线网络定位算法。对传统算法进行优化修正，利用其算法独特优势对节点进行优选，结合遗传算法和动力学算法各自优缺点，相互交叉，其算法定位效果更优，但由于算法复杂性较高，响应时间较长，下—步将继续改进。