林业无线传感器网络节点定位技术1)

常庞帆 仉俊峰 仉斡

(东北林业大学，哈尔滨，150040) (中山大学)

林业无线传感器网络，是一种由部署在待检测区域，具有感知、计算与通信能力的微型传感器组成的自组织分布式无线网络系统。这些节点通过无线通信方式组成一个多跳自组织网络，从而协作地感知、采集和处理网络覆盖区域中感知对象的信息，并发送给观察者。在实际运用中，这些传感器节点通常是被飞机撒播在指定的监测区域中，它们的位置是随机的、未知的，因此，传感器节点定位技术是无线传感器网络应用中的关键技术之一，是无线传感器网络实现目标识别、监控、跟踪等众多功能的前提[1-2]。

现有的传感器网络节点定位算法通过节点相互传播信息，未知节点在收集信息后计算与自己相邻锚节点的距离，再采用最小二乘法求解自己的位置[3]。根据是否通过硬件测距，定位算法可分为依据测距、依据非测距。依据测距的定位算法，一般通过能量强度、到达时间、到达时间差、到达角度等参数测量未知节点与锚节点的距离，然后再采用最小二乘法求解未知节点的精确位置。依据非测距的定位算法，一般通过质心估计、距离估计等方式直接估计节点的位置或在估计节点之间的距离之后，再采用最小二乘法求解未知节点的位置。由于无论通过硬件测距方式，还是通过估距方式，都会产生距离误差，采用最小二乘法求解节点的位置会形成误差累积，影响定位精度[4-8]。

遗传算法起源于对生物系统进行的计算机模拟研究。是一种借鉴生物界自然选择和自然遗传机制的随机搜索方法，通过采用“适者生存”的原则，在潜在的解决方案种群中逐次产生一个近似最优的方案[9-10]。遗传算法具有良好的全局搜优性，并且收敛速度快，具有可扩展性，易于同其它技术混合使用，因此，被广泛地运用到很多科研领域中[11]。由于传统的遗传算法存在过早收敛问题，笔者对遗传定位算法进行了改进，提出了一种新的无线传感器网络节点定位算法；经仿真验证，改进遗传算法是一种较好的林业系统中无线传感器网络节点定位算法。

1 定位算法的数学模型

假设待定位无线传感器网络中共M+N个节点，其中已知节点(即锚节点)数为M，未知节点数为N。通过某种测距方式，每个未知节点知道在通信半径内所有已知节点与自己距离，则可利用最小二乘法求得未知节点位置。设已知节点坐标为Ai(xi，yi)，i=1、2、…、M；未知节点坐标为(x，y)，其与已知节点距离为d1、d2、…、dM；则可建立方程组(1)。

(1)

求解方程组(1)即可得到未知节点位置。当锚节点数目≥3时，此方程是欠定方程。在实际操作中，由于环境硬件因素的影响，测量得到的距离会产生误差，而求解此方程时运用最小二乘法也会造成误差累积，因此，需要引入遗传算法减小误差。

2 改进型遗传定位算法

遗传算法，是一种借鉴自然界生物的遗传和进化过程而形成的自适应全局随机搜索与优化算法。它将问题的所有可能解组成一个种群，将每一个可能解视为种群的个体。从选定的初始种群出发，在整个种群空间内随机搜索，按照一定的适应度函数评估每一个体，循环使用选择、交义、变异三种遗传算子，使问题的解不断进化，直至搜索到最优解。

传统遗传算法效率较低，容易出现过早收敛问题。笔者在综合考虑了传统遗传算法的优缺点之后，提出了一种新的无线传感器网络节点定位算法。

2.1 种群初始化

种群初始化是为了产生初始的染色体种群，为遗传算法的计算打好基础。首先需要通过编码把问题的可行解从其解空间转换到遗传算法的搜索空间。遗传算法的编码方式，主要有二进制编码、格雷码编码、实数编码、动态参数编码等，为了保证群体稳定性，本文采用二进制编码。二进制编码中，本文将每个个体的基因值用(0，1)区问均匀分布的随机数表示，未知节点的纵坐标与横坐标的编码长度均设为10位。

对产生的待计算的初始种群，通常做法是确定基因的取值范围，在取值范围内随机生成初始种群；但是，这样产生的初始种群分布过于随机，对提高算法的效率没有太大帮助。文献[11]提出，初始种群应根据锚节点到未知节点的距离进行筛选。本文采用类似的方法，即在不同锚节点通信区域的重叠范围内进行随机初始种群生成，筛选公式：

式中：i=1、2、…、n；xi为节点i的横坐标；yi为节点i的纵坐标；di为节点i与锚节点之间的距离。

2.2 适应度函数设置

适应度函数也称评价函数，是根据目标函数确定的用于区分群体中个体好坏的标准。适应度的值越大，代表对应染色体越接近最优解。

由方程组(1)可以设遗传算法中适应度函数为：

式中：x、y为未知节点坐标；xi、yi为锚节点坐标；di为未知节点到锚节点(xi，yi)的测量距离。

将定位问题转化为求解无约束极值问题。每次定位一个未知节点的位置时，调用一次遗传算法，染色体编码即为未知节点的待定坐标，上式最优解即为未知节点的估计位置。

2.3 选择算子设计

遗传算法中的选择操作，是用来确定如何从父代群体中按某种方法选取那些个体遗传到下一代群体中的一种遗传运算，用来确定重组或交叉个体，以及被选个体将产生多少个子代个体。常用的选择算子，有轮盘赌选择、随机竞争选择、精英选择、期望值选择等。

为了最大限度保留优质基因，本文采用的选择方式：根据适应度函数式计算出的值进行排序，将适应度最高的两个个体完整复制到下一代，适应度最低的个体直接淘汰，其余个体则根据交叉算子与变异算子正常进行操作。与文献[6]中的选择算子相比，本文采用的方法可以更好地保证各代种群的优质性，同时避免早期的高适应度个体迅速占据种群，使后期的种群中因个体的适应度相差不大而导致种群停止进化。

2.4 交叉算子设计

遗传算法的交叉操作，是对两个相互配对的染色体，按某种方式相互交换其部分基因，形成两个新的个体。通过交叉操作，一方面，可以使父代群体中优良染色体的特性，在子代中继续保存；另一方面，可以使子代染色体具有多样性。常用的方法，主要有单点交叉、多点交叉、均匀交叉、算术交叉等。

定义交叉概率：

式中：pc1、pc2∈(0，1)；Fg为个体g的自适应度函数值；Fgb为最优个体自适应度函数值；Favg为自适应度函数的平均值；Farg为自适应度函数的实际参数值。

对于每代需要进行交叉操作的染色体，按如下步骤进行：

对每条染色体随机产生一个(0，1)之间随机数，将每条染色体的随机数与其交叉概率进行比较，若随机值小于交叉概率，则将该染色体定义为待交叉染色体，形成待交叉染色体集合。如果集合数目是偶数，顺序两两交叉；如果集合数目是奇数，顺序两两交叉后，集合中最后一个染色体不交叉，直接进入下一代。对于每一对交叉的染色体，通过随机数确定交叉的位置。

2.5 变异

遗传算法中的变异运算，是将个体染色体编码串中的某些基因座上的基因值，用该基因座上的其它等位基因替换，形成一个新的个体。通过变异操作，可以使遗传算法脱离局部最优解，继续计算全局最优解。常用的方法，主要有基本位变异、均匀变异、边界变异、非均匀变异、高斯变异等。

定义变异概率：

式中：pm1、pm2∈(0.01，0.10)；Fg为个体g的自适应度函数值；Fgb为最优个体自适应度函数值；Favg为自适应度函数的平均值。

对于每代需要进行变异操作的染色体，按如下步骤进行：

对每条染色体随机产生一个(0，1)之间随机数，将每条染色体的随机数与其变异概率进行比较，若随机值小于变异概率，选择对其进行变异。具体的变异操作，是通过随机数决定变异位置，并对该位进行取反完成。

设遗传算法中染色体数目为m，每条染色体编码长度为n，则每条染色体为s1、s2、…、sm，可以构成矩阵S(m)。

在二进制编码条件下，有时会出现一种情况，即矩阵S(m)的某一列全为相同的元素，即全为0，或全为1。此时通过交换操作，不能改变该位的值，这种情况会导致只能得出局部最优解，无法接近全局最优解。传统的突变操作，仅相当于对矩阵S(m)行上的数值进行突变，没有办法解决这种某一基因位单调的问题。因此在变异操作阶段，除了对染色体进行变异之外，还需要对这种单调基因位进行检测与位变异。

虽然本文提出的变异运算操作比文献提到的更加复杂，但可以有效提高算法的精度，避免局部最优解的出现。

3 仿真实验

为更准确验证本文提出的算法的有效性，在windows7操作系统下的Matlab平台上进行仿真模拟实验。随机在100×100的区域中选取100个节点，其中20个为锚节点，80个为未知节点，节点通信半径为40。遗传算法中，具体参数取值为：种群数目为20，交叉概率pc1=0.6、pc2=0.4，变异概率pm1=0.06、pm2=0.04，最大迭代次数为100。

3.1 算法仿真结果

根据上述数据进行仿真实验，原始节点分布如图1所示，经过遗传算法计算后的定位结果如图2所示。由图1、图2可见：定位结果基本都能准确定位到未知节点处。说明改进型遗传算法具有良好的定位性能。

〇为锚节点；△为未知节点。

〇为锚节点；△为未知节点；*为预测节点。

3.2 性能比较

为分析改进型遗传算法与传统遗传算法的性能差异，在相同参数条件下用两种算法进行计算，其迭代次数与适应度值变化关系如图3所示。由图3可见：随着迭代次数的增加，改进型遗传算法的收敛性优于传统遗传算法。

图3 适应度变化情况

在其余运行条件相同情况下，通过改变锚节点数目得到的两种算法的平均误差如图4所示。由图4可见：在锚节点数目不同情况下，改进型遗传算法的精确度始终高于传统型遗传算法。

图4 锚节点数目与平均误差关系

4 结束语

本文介绍了定位算法的数学模型，并利用遗传算法求解该数学模型的最优解。对现有遗传算法进行了改进，提高了算法的运行效率，优化了运行步骤，避免了局部最优解的形成。通过仿真实验验证，改进型遗传算法加快了收敛速度，也提高了对未知节点进行定位的精度，可以较好地解决无线传感器网络节点定位问题。