WSNs中基于遗传算法移动信宿路径的优化

2019-12-23王继营

中国电子科学研究院学报 2019年10期

王继营,胡君

(1.黄淮学院，河南驻马店 463000;2.湖南大学，湖南长沙 410004)

0 引言

采用静态信宿的无线传感网络(Wireless Sensor Networks, WSNs)[1]易遭受信宿黑洞问题。信宿附近的节点能量消耗速度高于其他节点。一旦它们的能量耗尽，就造成覆盖空洞，形成网络断裂。原因在于：信宿附近的节点需要转发更多数据包[2]。

可采用多个信宿策略均衡传感节点的能耗[3]。最为理想的策略是：采用单个信宿，信宿依据预定的路径在网络内进行移动，并沿着路径收集数据。信宿的移动，能够平衡节点的能量消耗。相比于静态信宿，移动信宿(Mobile Sink, MS)具有明显的优势[4]。

然而，采用移动信宿的WSNs也存在一个问题：信宿如何移动，如何实现收集数据最大化。目前，有两个策略解决此问题。其一，MS直接遍历每个传感节点，直接从每个传感节点接收数据[5]；其二，允许MS遍历一些预定的位置，这些位置称为驻留点(Rendezvous Points, RPs)[6]。相比于前者，采用驻留点算法更有效，消耗的能量更少。

但是，如何搜索最优的驻留点数以及它们的位置，进而获取最大的数据收集量是驻留点算法必须解决的问题。当然，搜索最优驻留点数以及最优位置是NP问题。

遗传算法广泛应用于求解NP问题的近似解。遗传算法以随机初始可行解开始，这些随机初始可行解称为群体(Population)。群体内的每个个体称为染色体(Chromosome)。一条染色体是一系列的值，而每个值称为基因(gene)。遗传算法通过交叉、变异操作，最终能获取最优的群体，进而得到NP问题的次优解。

为此，提出基于遗传算法的搜索RPs (Genetic algorithm-based find RPs algorithm, GAFR) 算法。RAFR算法充分利用遗传算法在求解NP问题上的优势，利用遗传算法求解MS的RPs，进而构建最优的移动路径。仿真结果表明，提出的GAFR算法有效地降低了移动路径，减少了数据收集时间。

1 问题描述

假定所有传感节点随机分布于方形网络区域。利用GAFR算法获取驻留点数及位置。MS通过遍历驻留点[7]，从传感节点收集数据。驻留点的初始位置是随机的。每个MS具有足够容量和能量计算遍历路径。当然，遍历路径需包含每个驻留点。为了表述简单，引用以下的变量：

(1)传感节点集S={s1,s2,…,sn}，其中n表示为传感节点总数；

(2)驻留点集RP={r1,r2,…,rm}，其中m表示驻留点总数；

(3)用τ表示MS移动的总路径长度，其近似等于驻留点间的距离之和，如式(1)所示：

(1)

其中χi,i+1表示第i个驻留点与第i+1个驻留点距离。

(4)令L0=0.2n、LF=0.5n分别表示一条信息素的最小长度、最大长度；

(5)令Sri表示第i个驻留点所覆盖的传感节点集；

(6)令K表示最优驻留点数，最初K=m；

提出GAFR算法的目的在于寻找最优K值，并且最小化MS遍历的路径。具体而言：(1)构建最优K值，使得传感节点能密集在分布于离其最近的驻留点周围；(2)MS遍历路径长度τ最小。

综上所述，可形式化表述所需解决的问题：

Minimize(τ)

(2)

约束条件：

|Sr1|+|Sr2|+|Sr3|+…+|Srm|=n

(3)

式(3)确保了MS能覆盖所有传感节点，进而能够有效地收集数据。

2 GAFR算法

提出的GAFR算法主要由染色体表述、初始群体的产生、适度函数的构建、选择、交叉和变异阶段构成。

2.1 染色体表述

图1 染色体表述

2.2 初始群体

对于不同长度的染色体，均采用固定的初始群体尺寸。若采用初始群体数为N，则只要满足群体数为N的染色体才是有效的。群体数反应了可行解数。图2显示了长度为10、12的两条染色体，但它们的群体数均为5(N=5)。

图2 初始群体

2.3 适度函数

遗传算法采用适度函数估计每条染色体的性能，并依据适度函数判断染色体的合法性和非合法性。MS的最佳移动路径取决于驻留点数。令L表示驻留点数或信宿的长度。同时，MS的最佳移动路径也受τ的长度影响。

为此，利用L和τ这两个因子构建适度函数，进而优化最佳路径。驻留点数少，路径短，但可能会导致部分传感节点无法覆盖。反之，若驻留点数多，路径会越长。同时，采用权重因子平衡这两个因子，如式(5)所示：

F=αL+βτ

(5)

其中α、β为权重因子，且α+β=1。

2.4 选择阶段

在选择阶段，选择部分染色体去执行交叉、变异操作，进而产生新的种子(offsprings)[9]。为了能够产生最优的种子，选择具有最优的适度值的染色体进行操作。目前，有赌轮选择(Roulette-wheel Selection)、秩值选择算法。GAFR算法引用赌轮选择算法，完成染色体的选择。作为常用的选择算子，赌轮选择算法并不要求对个体先按适值排序。个体被选中的几率与它的适应值呈正比。

2.5 交叉

将已选择的染色体进行交叉操作。目前，也存在多种方式完成交叉操作，如单点交叉(Single-point crossover)、多点交叉(Multi-point crossover)。本文采用单点交叉操作。

如图3所示，第一条染色体的长度为8，它的交叉点为红实线；第二条染色体的长度为12，它的交叉点也为红实线。两条染色体通过交叉，完成信息交换，构成两条新的染色体，且生成的子染色体长度均为10。

治疗前，两组2型糖尿病合并胃溃疡患者在血糖水平差异无统计学意义（P>0.05）；治疗后，观察组2型糖尿病合并胃溃疡患者空腹血糖（5.52±1.32）mmol/L、餐后 2 h 血糖（7.30±1.44）mmol/L，对照组空腹血糖（5.69±1.67）mmol/L、餐后 2 h 血糖（7.32±1.64）mmol/L，两组间相比，差异无统计学意义（P>0.05）。见表2。

图3 染色体交叉示意图

2.6 变异

完成了交叉操作后，便可对新产生的子染色体进行变异[10]。通过变异，提高子染色体质量。假定基因发生变异的概率为50%。变异后，必须保证新的子染色体能够有效。

图4显示了变异过程。图4显示长度为10的染色体，第5个基因位置上发生变异，由原来的31变化成64，形成新的子染色体。

图4 变异后的操作

图5 GAFR算法流程

GAFR算法的整个流程如图5所示，先产生初始群体，然后进行选择操作，同时计算适度值，并选择优质的染色体。再利用这两项信息产生新的群体。随后，利用交叉、变异产生新的子染色体。直到满足终止条件，就停止。

3 性能分析

3.1 仿真环境

为了更好地分析GAFR算法的性能，选择Python3.5软件建立仿真平台。在面积为S的方形区域内部署50～300个传感节点，迭代次数为1000。具体的仿真参数如表1所示。

表1 仿真参数

同时，选择TSP算法作为参照。采用与GAFR算法相同的仿真参数，并对比分析它们的性能，包括MS移动的路径长度、数据收集时间。

3.2 数据分析

考虑两个实验：实验一，方形区域面积为：100 m2，传感节点数从50变化至300；实验二，方形区域面积为200 m2，传感节点数从50变化至300。

3.2.1实验一

首先，分析传感节点数对路径长度的影响，如图6所示。

图6 路径长度(实验一)

从图6可知，节点数的增加，增长MS移动路径。原因在于：节点数越多，分布区域越广泛，MS需要收集的数据区域越广，其需移动的路径也就越长。相比于TSP算法，提出的GAFR算法有效地缩短了移动路径。这要归结于：GAFR算法利用遗传算法搜索最优的驻留点数，减少了移动路径。

接下来，分析数据收集时间随节点数的变化情况，如图7所示。

图7 数据收集时间(实验一)

图7的图形走趋与图6图形相似。节点数的增加也提高数据收集时间。节点数越多，MS移动的路径越长，相应地，数据收集时间也相应地增加。相比于TSP算法，提出的GAFR算法通过减少移动路径，降低了数据收集时间。

3.2.2实验二

相比实验二，本次实验改变了网络区域面积。类似地，图8、图9显示了在200 m2仿真环境下的路径长度和数据收集时间。

图8 路径长度(实验二)

图9 数据收集时间(实验二)

对比图6可知，实验二环境下的路径长度得到较大幅度的增加。这正如预期的，网络区域面积越大，节点分布区域也越广，MS移动的路径肯定越长。例如，当节点数在300时，网络区域面积为100 m2时，TSP和GAFR算法的路径长度分别为约1350和450；但当区域面积增加至200 m2时，它们的路径长度分别增加至2500和900。

类似地，图9的数据收集时间相比图7(实验一)大幅度地提升。原因在于：路径的增长，增加了数据收集时间。对比图7不难发现，网络区域面积的增加，提高了数据收集时间。相比于TSP算法，提出的GAFR算法能够有效地控制数据收集时间。