一种基于遗传算法的无线传感器网络定位新算法

摘　要：针对无线传感器网络节点自身定位问题，提出一种基于遗传算法的新定位算法。该算法假设无线传感器网络中有一定比例的位置已知的节点，通过分析未知节点及其无线射程范围内的已知节点之间的通讯约束和几何关系，建立以未知节点位置为参数的优化设计数学模型，使用遗传算法求解此模型得出未知节点的位置，并通过修改遗传算法参数来提高遗传算法收敛速度。理论分析和试验结果表明，本算法具有很强的健壮性，未知节点的失效和新节点的加入不会影响算法的性能，并且算法定位精度高，条件简单，适合各种规模的无线传感器网络的节点定位。

关键词：无线传感器网络；节点定位；遗传算法；算法性能

中图分类号：TP301．6　文献标识码：A

1 引言

无线传感器网络(WSN)作为上世纪末新兴起的一种技术，在军事国防、工农业、城市管理、生物医疗、环境监测、抢险救灾、防恐反恐、危险区域的远程控制等许多领域都有重要的科研价值和巨大的应用前景，已引起了世界许多国家军界、学术界和工业界的高度重视，并成为进入21世纪以来公认的新兴前沿热点研究领域，被认为是将对21世纪产生巨大影响的技术之一。

WSN由大量的无线传感器节点组成，每个节点都被随机放置，因此很难得知其具置。虽然运用GPS可以精确得到每个节点的位置，但高昂的成本使得GPS不能广泛应用于WSN。现有的WSN定位算法就是依据少量的位置已知的节点(称为锚节点)以及可靠的节点通信信息来估计整个网络中每个节点的位置。如美国路特葛斯大学的Dragos Niculescu等人提出的DV-Distance方去，Lance Doherty等人提出的凸规划求解方去，以及Tian He等人提出的APIT算法等。这些方法都有自身的特点，但是它们的定位精度都不够理想，并且需要高密度的锚节点。

针对上述的几个问题，本文提出了一种利用遗传算法来实现WSN定位的新方法。围绕如何清楚的阐述此方法，全文组织如下：第二节详细介绍基于遗传算法的节点定位算法，并根据定位优化模型，设置合理的遗传算法参数；第三节介绍算法仿真，确定算法性能指标参数和影响算法性能的全局参数；第四节根据仿真结果，分析全局参数对算法性能的影响；第五节总结全文。

2　基于遗传算法的无线传感器网络节点定位算法

基于遗传算法的无线传感器网络定位算法是，通过分析未知节点与少量锚节点之间的通信约束，建立以未知节点位置为参数的定位优化模型，使用遗传算法对优化模型进行求解参数，所得结果即为未知节点的估计未知。

无线传感器网络有着节点数目多，分布区域广，通信约束多等特点，由此建立的定位优化模型是一个多目标多约束的非线性方程；而遗传算法做为目前比较成熟的一种进化算法，应用条件简单，搜索能力强并且特别适合多目标，多约束的求解，故非常适合无线传感器网络节点定位优化模型的求解。下面分别介绍节点定位问题描述，节点通信约束，定位优化模型以及遗传定位算法。

“注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文”