基于三链混合遗传算法的WSNs中Sink节点布局优化

刘燕

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

基于三链混合遗传算法的WSNs中Sink节点布局优化

刘燕

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

对无线传感器网络的设计和布局中，多Sink节点的布局是其拓扑设计的关键，对网络通信的能量控制至关重要。本文通过分析其Sink节点布局模型，提出一种改进的三链混合遗传算法对Sink节点布局求取最优解。实验表明，三链混合遗传算法在针对Sink节点的布局算法中相对于枚举算法，具有较优解，并且算法效率高，可降低无线传感器网络的能耗，改善网络性能。

无线传感器网络；Sink节点布局；三链混合遗传算法

1 引言

无线传感器网络系统是一种由大量部署在监控区域的智能传感器节点构成的网络应用系统，一般包含三类不同节点：传感器节点、汇节点(称Sink,也称为基站Base station)和管理节点[1]。传感器节点一般采用随机投放方式，Sink节点的布局问题是拓扑控制中的一个难点[2-4]。如何通过功率控制以及骨干节点的选择，删除节点间不必要的无线通信链路，使得网络拓扑满足一定的性质，如连通性、稀疏性等，从而减少无线信号冲突，降低无线传输能耗，延长网络生存时间。因此，对Sink节点的布局研究具有一定的现实意义[5]。

遗传算法（Genetic Algorithm，GA）是模拟达尔文“优胜劣汰、适者生存”的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法[6]。经过国内外多年的研究与实践，遗传算法已经显示出了其解决复杂系统优化问题的良好能力，对NP组合优化问题的求解，更表现出了优异的性能。本文中多Sink节点的P中值布局模型就属于一类NP完全问题：搜索到Sink节点的最佳位置，使加权距离和最小。

2 问题描述

Sink节点的布局与无线传感器网络的服务性能紧密相关。可以认为无线传感器网络中的Sink节点与传感器节点之间存在服务与被服务的关系。由于无线通信链路可靠性及服务效率与服务点与被服务点之间的距离有关，因此缩短Sink节点与传感器节点之间的距离是一种提高服务效率的有效策略。

于是，对于一个具体的无线传感器网络环境作如下定义：

表1 问题变量定义表

则问题为在给定区域内，从M个候选Sink节点位置中找出P个Sink节点的位置，使得所有传感器节点到Sink节点之间的总加权距离最小化。加权值为节点i单位时间发送的请求数ri。

其中总数学表达式中的两个决策变量Kj，Tij的含义如公式（1）所示：

Tij=传感器节点i被汇节点j服务其他 （1）

同时，此问题还需要满足以下条件，如表2所示：

表2 问题满足的条件

3 遗传算法实现

Sink节点候选位置可以采用网格方法，将区域用网格划分，Sink节点布局在网格的交叉点上。针对不同的布局要求，网格的密度可以适应性改变。

3.1 染色体编码

根据上一节数学模型，由于取Sink节点采取布局在网格交叉点上，因此可以采用Sink节点的二维坐标作染色体，采用二进制编码。染色体由三条分链顺序拼接组成，分链1表示Sink节点的x坐标；分链2表示Sink节点的y坐标，分链三表示Sink节点单位时间所能处理的请求数目。

3.2 适应值函数和选择操作

针对上一节提出的数学模型，目标值函数是所有传感器节点到Sink节点之间的总加权距离。用评价函数取F(x)评价每个染色体的适应值大小，使得F(x)的值最小的解即可作为优化算法的满意解。目标函数到适应度函数的转换为：

根据各染色体的适应值的大小，采用赌轮盘法来选择一些染色体进行遗传操作[6]。一个染色体将被选择的概率与其适应值大小成正比。同时采用精英保留的选择策略，将每次选择时候出现的适应值最小的染色体（当前最好染色体）以概率1保留下来进行交叉和变异等遗传操作。

3.3 遗传操作算子

本文采用的是经典的顺序交叉算子[6]，每次运算将产生2个后代。

一种基于最近邻方法设计的启发式的变异算子[6]，用来产生更好的后代。一个父代通过改变邻域内的基因的序列来产生一组染色体。这些产生出来的染色体只留下适应度最好的作为变异产生的后代。这里，原来的启发式突变经过改进，以提高种群的多样性。所做的改进是将交换邻域基因所产生的所有染色体都作为新生成的后代。

逆序变异算子：反转变异操作是从父染色体中选择一个子串序列，将子串序列反转后生成一个后代。反转变异操作只作用于一个染色体。除了在两个染色体之间进行交换基因的特性之外它与启发式变异非常相似。所以，反转操作算子是一个变异遗传操作，主要原因是这是用于增加种群的多样性而非改善种群的质量。

4 算法性能对比仿真及实验分析

实验对象：无线传感器网络监控区域为100m×100m，传感器节点数量为90，各个节点的位置分布和请求数分布为随机值。预置的Sink节点数量P=8；遗传算法的遗传策略为：适应值函数取最大值，启发式变异率为0.05，交叉率取0.2。迭代次数取500。将Sink节点布局分别用枚举法和本文提出的三链混合遗传算法进行对比，效果图如图1所示。

图1 多Sink节点布局图对比

表3 两种算法布局效果对比

由图1可以看出，枚举法和三链混合遗传算法找到的布局位置有差异，表3数据比较了两种算法在求加权距离最优解的数据，包括总距离的大小和算法的效率、误差率。由数据可以看出，枚举法和三链混合遗传算法在总加权距离上有一定的差别，但在算法执行时间上有巨大的差异。并且三链混合遗传算法在加权距离上的差异与枚举法相比较可以算出其相对误差，误差率为10.7。可以看出三链混合遗传算法在最优解的求解和算法效率上都优于枚举法。

5 结语

本文主要应用了三链混合遗传算法来解决多Sink节点布局问题。首先介绍了无线传感器网络的内容，详细阐述了Sink节点布局的数学模型，并根据数学模型提出了三链混合遗传算法。通过与枚举法对比实验分析，论证了三链混合遗传算法在Sink节点布局上相对于枚举法具有更优的解及算法效率的提升。可见三链混合遗传算法在求解Sink节点布局最优解上具有一定的优势。

[1]马祖长，孙怡宁，梅涛．无线传感器网络综述[J]．通信学报．2004，25(04)：114-124．

[2]潘耘，李嫣，李晋凯，等．无线传感器网络中的多Sink节点的放置问题[J]．计算机研究与发展，2010，47(S2)：92-95．

[3]王金鑫，赖旭芝，吴敏．一种基于遗传算法的无线传感器网络定位新算法[J]．计算技术与自动化，2007，26(04)：53-56．

[4]刘强，毛玉明，冷甦鹏，等．无线传感器网络中多Sink节点优化部署方法[J]．计算机应用，2011，31(9)：2313-2316．

[5]韩凯州，马福昌．无线传感器网络中多Sink节点位置部署研究[J].传感器与微系统，2014，33(3)：37-39．

[6]Gen M，Cheng R(1997)Genetic algorithms and engineering design [M]．Wiley，New York．

Sink Node Location Optimization for WSNs Based on Improved Three Chain Hybrid GeneticAlgorithm

Liu Yan
(Jiaying University,Meizhou 514015,Guangdong)

In the design and layout of Wireless Sensor Networks(WSNs),multiple Sink node locating is the key step in network topology.It is very important to control energy-consumption of network communication.By analyzing the layout of Sink node model,an improved three chain hybrid genetic algorithm is proposed to solve the Sink node's optimal location problem.The experimental results show that compared with the enumeration algorithm,the three chain hybrid genetic algorithm for the Sink node has better solutions and higher efficiency of the algorithm,which can reduce the energy consumption of wireless sensor networks and improve the network performance.

wireless sensor networks(WSNs);Sink node locating;three chain hybrid genetic algorithm

TP393

A

1008-6609(2016)08-0013-03

刘燕，女，湖南永州人，硕士，助理实验师，研究方向：控制工程的理论与应用研究。

广东省教育厅创新强校工程重点平台建设、培育项目，项目编号：2014KTSCX173；嘉应学院自然科学研究项目，项目编号：314E23。