基于遗传算法的无线传感器网络节点优化方法研究

刘　燕

（嘉应学院 电子信息工程学院，广东　梅州　514015）

基于遗传算法的无线传感器网络节点优化方法研究

刘燕

（嘉应学院 电子信息工程学院，广东梅州514015）

随着科技的不断发展，传感器网络得到了极大的发展，其拥有极为广阔的应用前景，已被应用于智能家居、空间探索、军事、健康护理以及环境监测等领域。文章就其测控系统所具有的特殊性，提出了一种可以达到节点连通约束来对节点数量加以减少的新模型，同时利用遗传算法对其加以优化计算。要想使节点收敛速度大幅提升，文章将采取以二分法为基础的遗传算法进行研究。

遗传算法；无线传感器网络；节点优化；连通性

无线传感器网络（Wireless Sensor Network，WSN）是一种由众多小型传感器所构成的网络，其主要的功能是对网络区域中的对象信息以协作式进行感知、采集并进行处理，之后将其发送至基站中。随着对WSN不断深入的研究以及广泛应用，WSN将被应用到人类的生活生产的各个领域。传感器网络在之前主要有两类分布方式，即随机撒布和有计划安置。但是其具有各自的应用方面以及优势，因此在进行具体应用时要根据具体情况加以选取。本文的WSN仅需进行特定地点展开监测，所以分布范围广、节点相对较少。路由器节点具有较为灵活的位置，同时该节点还具有一定的移动性。

1　优化数学模型

定义：拥有传感器节点集合，g =｛C1， C2， …CN｝，求取一个子集从而实现将C⊂g，整个网络进行连通，同时满足C中节点数最少。

假设监测区域是二维平面：其｛ S（x ， y ）： 0 ≤ x ≤Length 0 ≤ x ≤ Width ｝中Length是检测区的长度，Width是监测区的宽度；所安置的感知节点数是N个，而且已知全部节点坐标；根据区域大小和节点数估计移动节点数为M个，从而确保该网络连通性，移动节点坐标为（x，y）；节点i，j间存在的距离为dij；网络内全部节点拥有同等传输范围，其传输范围是以（x，y）坐标作为圆心，半径是r的圆；将全部节点看作是一个无向图，其邻接矩阵为A，若dij< r时，节点能够直接通信，此时称i，j间有一条弧，相应的Aij是1［1］。

假定图G具有n个顶点，其邻接矩阵是A，那么道路矩阵可以根据邻接矩阵A通过布尔运算加以获取：

利用遗传算法展开优化计算过程中，通常编码长度是固定的，而其中固定节点数目已知，也就是说要移动节点数量确定。所以，优化过程中应该采取数量相对较多的节点，一旦节点有冗余式，一定会产生重复位置的节点，那么可以将重合节点看作成一个节点，这边可以将节点数目最小化加以转化，利用重复节点最多化来进行间接求取［2］。那么优化函数便是：

根据上述函数中未将重合结点数当作是变量，主要是确保指标可以满足连续性，这样可以将重合节点数较少的染色体进行优化计算。函数中的bD是距离基值，其作用是判断节点间的重合程度。若dij越小那么函数值将会越大，重合程度就越高。bD值越小，则重合判断的越精细。bM+N是重合节点数目基值，该值是由检测区域与节点数目决定的［3］。

而对于连通约束，则将采取惩罚函数，定义惩罚函数是：

式中，PMN是道路矩阵P内不是0的元素数目；bMN是一个基值，其值是由（M+N）2加以对其决定的。若网络内全部节点均可以利用多跳路由与其他节点进行连通时，那么PMN=（M+N）2，那么上述函数其值最大是1，从而可以确保整个网络所具有的连通性。

利用上述函数进行相应的优化，之前计算出的移动节点数N与优化重合节点数相减得到的数目就是实际所需安装的路由节点数。

2　基于GA节点分布优化

遗传算法即GA是一类创建于自然选择原理以及自然遗传机制前提下的迭代自适应检索方式［4］。在进行最优解求取过程中，要从随机解开始，该随机解被称作种群，种群内的所有解均是一个个体［5］。其中个体解利用适值加以评定来选取相应最佳解，适值好的个体拥有的生存几率会相对较高［6］。

此外，还应对适应度进行一定的选取。通过对上文的探讨后，WSN的分布优化作为多目标优化工作，应该使节点数和其连通性能够达到一种平衡。总目标函数即是上文提到的两函数经过归一化得到的加权和。将总适应度函数做出如下定义：

其中，α1是优化函数的加权值，α2是惩罚函数的加权值，其选取范围取决于该网络指标所需的综合要求，同时要满足的是

3　仿真实验

这里利用仿真实验进行算法有效性的检验。对安装在400m×600m监测区域中的10个节点加以仿真分布。根据算法要求事先安装10个固定节点，同时将每个节点的传输半径设置为120m，种群个体数量是200，其变异概率是0.02；交叉概率是0.5。仿真结果如图1所示。

通过对图1进行分析，在初始化过程中，节点存在极少的连通，整个检测网络完全是不连通状态。随着优化代数不断地向前推进，相互连通的节点数也在不断地增加，当运行至90代时，全部节点均已连通，同时存在一个移动节点与其他节点发生重合。当运行至第100代时，其结果与第90代结果基本一致，这就说明此时已经得到了节点分布的最好方案。此方案分布不但确保了全部固定节点得到了连通，而移动节点也得到了一定的优化。而且还有一个节点发生重合，这就说明安装9个节点便能确保网络的连通性。

图1　仿真实验结果

4　结语

综上所述，通过对无线传感进行一定研究，在确保固定节点所具有的连通性基础上，尽可能对移动节点加以减少。根据对二分法为基础的遗传算法进行仿真，可以实现对染色体长度进行极大地缩减，从而使收敛速度得到快速提升，在全部节点连通的基础上将节点减少。

［1］叶苗，王宇平.一种新的容忍恶意节点攻击的无线传感器网络安全定位方法［J］.计算机学报，2013（3）：532-545.

［2］沈海洋.基于遗传PSO的无线传感网络覆盖优化算法研究［J］.微电子学与计算机，2013（3）：148-151.

［3］胡静娴，冯秀芳.RGA-D：一种无线传感器网络覆盖优化方法［J］.测控技术，2014（10）：105-108.

［4］樊富有，杨国武，乐千桤，等.基于量子遗传算法的无线视频传感网络优化覆盖算法［J］.通信学报，2015（6）：98-108.

［5］邵开丽，付辉.能耗均衡的无线传感器网络多Sink节点部署优化方法［J］.仪表技术与传感器，2015（9）：106-110.

［6］沙超，王汝传，黄海平，等.一种基于多目标遗传优化的无线多媒体传感器网络节能覆盖方法［J］.电子学报，2012（1）：19-26.

［7］李海龙，李宝华，韩彦春.无线传感器网络DV-Hop算法的一种优化方法［J］.辽宁工程技术大学学报（自然科学版），2016（5）：523-528.

Research on optimization method of wireless sensor network node based on genetic algorithm

Liu Yan
（Electronic and Information Engineering Department of Jiaying University， Meizhou 514015， China）

With the continuous development of science and technology， the sensor network has been developed greatly， which has a very broad application prospects， and has been applied to smart home， space exploration， military， health care and environmental monitoring and other felds. A new model which can reduce the number of nodes in the control system is proposed in this paper， which can be achieved by using the genetic algorithm to optimize the measurement system. In order to improve the convergence speed of the nodes， this paper will adopt the genetic algorithm based on the dichotomy to carry out the research.

genetic algorithm； wireless sensor network； node optimization； connectivity

刘燕（1989— ），女，湖南永州，硕士，助理实验师；研究方向：控制科学与技术。