水文无线传感网覆盖的多目标优化算法研究

涂振宇,陈 杰，曾 瑄

(1.南昌工程学院;2.江西省防汛信息中心)

为了获得监测目标区域的水位、蒸发、温湿度等水文数据，人们通常采用人工部署传感节点采集数据的方式进行。这种技术路线具有简单易行，便于操作的特点。但如果监测区域面积大(通常可能有几百个平方米)、目标环境复杂、不便于人工部署数据采集节点。此时可采用飞机抛洒大量廉价的水文无线传感器的方式进行水文监测[4]。每个无线传感器都被看作一个拥有无线通信能力，同时还具有一定的数据采集与信号处理的智能节点。各节点能够自组织，自管理。这些特性使得监测网络具有较高的健壮性和容错性，任何节点的故障不会影响整个网络的数据探测与传输能力。

传感器的硬件构成如图1所示。传感节点由传感模块、微处理器模块、能量单元和无线通信模块构成。传感模块可以监测目标区域的水雨情数据、蒸发、温湿度、水质污染等多方面的数据乃至多媒体信息。

图1 传感器硬件构成

无线传感技术同样也适应农林业生产中的农作物病虫害、土壤酸碱度和其他信息监测。

传感信息经过采集和A/D转换，经过处理器的处理并在存储器里暂存。通信模块负责数据发送并接受交换控制信息。能量单元为节点提供运行所需能量，一般采用电池供电。

1 系统模型

本文将监测水域划分成二维网格来对监测的区域离散化，大量传感器节点分散在某些网格中，用统一的初始化电量。我们要研究以下几个问题:

1.1 覆盖问题

每个传感器节点的感知范围是一个半径为Rs的圆，节点之间的通信半径为Rc，当Rc≥2Rs时，可以认为节点网络全连通[2]。如果一个监测点位于K个节点感知范围内，称为K覆盖[7]。节点的感知模型可以分为布尔感知模型和随机感知模型二类。

(1)布尔模型(0- 1 Boolean)

监测点p位于节点s的感知圆形区域内，其感知概率为：

(1)

其中，L(s,p)为点p(xp,yp)到点s(xs,ys)的欧氏距离

(2)

(2)概率模型：监测节点d被感知的概率与它与节点s的距离有下面关系

(3)

其中，re容错半径(表示节点的不确定性物理特性)，l=d(s,d)-(rs-re)如果监测点d的监测概率大于(或等于)一个门槛值pth，则表示P点可以被监测到。如果监测点P被K个传感器节点感知，则其被K重覆盖，其监测概率为：

(4)

在水信息监测工程实践中，我们通常监测的对象是二维水面的某个区域的水文信息，因此可以把目标区域离散成二维网格，网格的大小按合适的测量精度及传感器的感知半径来划分。在监测水文数据时，我们要求的是无线传感网能尽可能地覆盖更大的面积并保存更长时间的监测周期，而不是要求监测特定的网格。在这种数据优先的前提下，我们在计算覆盖面积时可以做一定的简化。

监测区域的总网格数有m×n个，按上面公式计算每个网格的覆盖度，如果该网格的覆盖度大于设定的门槛值，则认为该网格被覆盖。被传感器覆盖的网格数有Ni个，传感器网络按照时间段打开一定数目的传感器，能有效地延长网络生存期。

定义第i个时间段的覆盖度为

传感网的各个工作时间段都有一个覆盖度值，取其最小值作为整个网络的覆盖度。

COV=MINCOVii属于是[1T]区间的时间段

1.2 问题建模

一个节点集Ci对监测区域的覆盖率可以定义为能被传感器感知覆盖的总面积与监测区域总面积之比。下面我们可以给出无线传感网生存期优化模型：

MAX CS

满足对于每个周期的工作节点，其节点集合满足覆盖条件并且

(8)

公式(8)表示，在所有工作周期内，任一节点的工作能耗总和不能超过其初始电量。

适应度函数设定：

Fit(s)=α×Cs+β×T(s)

(9)

其中α+β=1

在工程实际中，我们可以根据工程需要分别指定“网络覆盖度”，“网络生存期”两个目标的权重大小。通过公式(9)可以把多目标优化问题转成单目标优化问题，有助于简化编程，并且可以通过调整权重系数将算法向期待的方向引导。

2 多目标遗传算法

2.1 算法步骤

用遗传算法求解多目标优化问题的思想是：将问题进行编码，构建初始种群，开始迭代运算，在每次迭代中，根据个体的适应度函数的值来选择优良的个体并进行个体编码的杂交、变异操作，最后达到终止条件后可以得到多个解的种群，通过解码得到解空间[7]。

本文讨论的优化问题是在传感器的最大工作时间周期内，每个周期内获得最大的覆盖率。激活更多的传感器节点可以获得较大的覆盖率，但同时消耗更多的电量，减少传感器监测网络总的生存期。因此编码中要将传感器节点的工作状态与工作周期带入问题中来，为此，先做如下规定：

传感器节点集合记为S，每个传感器的一个工作周期为t,网络总的工作时间可以表示为T={t1,t2,,tn}。

在t时间内，如果传感器节点处于工作状态，其值为1，如果处于休眠状态，设定为0。因此可以用T×N的矩阵来表示一个解的个体。

对于一个5个传感器的WSN，如果设定有4个工作时间段，可以用图2表示一种传感器状态。传感器节点1，4，5工作，2、3休眠。

10011

图2传感器工作状态

用如图3所示矩阵表示监测区域内传感器集合的工作方案。

图3 传感器编码矩阵

这种编码方案可以映射到问题的全部解空间，但每个矩阵个体不一定是合理的解。每个矩阵的列的和可能超过该节点的起始电量。因此在选择操作中要淘汰某些不合理的解。

(1)选择算子

在初始种群中，一个矩阵对于一个个体，在选择作为父代个体前，可以对矩阵进行解的合理性检查，如果某列的元素之和超过该传感器电量，则淘汰该个体，根据“轮盘赌选择”算法选择个体进入下一次迭代。设种群规模为N，个体r的适应度为fitness(r)，它被选中作为遗传算法父体的概率为：

(10)

(2)杂交算子

行交换：产生二个[1T]区间的随机整数N1，N2。父代个体1中选择第N1行与父代个体2中的第N2行做交换，得到两个子代个体。子代个体每行都是符合覆盖要求的染色体。但可能产生某列的元素电量总和超过该传感器的初始电量，产生不合理解个体。

列交换：产生二个[1M]区间的随机整数N1，N2。父代个体1中选择第N1列与父代个体2中的第N2列做交换，得到两个子代个体。子代个体每列都符合覆盖电量约束，但可能导致一个染色体的覆盖约束不能得到满足。故也要通过算法淘汰劣质解。

(3)变异算子

变异算子可以拓宽解空间的大小，能使得解空间跳出局部最优，在本例中属于一个辅助算子，可以选择父代的个体的某一行，按初始化方法生成某行元素，并检查各列的电量约束条件。新的个体重新进入迭代运算。

2.2 算法的改进

在上面的算子操作过程中，如果没有合理的运算指导，只靠随机概率来引导算法，很容易陷入局部最优或让算法发散。本文对上面传统的算法加以改进，引入邻域搜索的概念来改进算法，收到良好的效果。在上面如果在计算适应度函数值的时候指定了固定的加权值α,β。算法只能得到一个非劣解。如果在选择算子开始前，随机设置新的权值组合可以使得算法在邻域开始新的进化方向，从而弥补遗传算法的局部搜索的局限[1,3]，改进的算法可以表述如下：

(1)随机生成规模为初始种群，种群规模为N。

(2)根据适应度函数加权值的初始设定，计算当前种群每个解的适应度值,按支配关系,更新临时非支配解集。

(3)随机设定新的加权值α，β，按轮盘赌方式从非支配解集之外选出父代个体，产生进行遗传操作交叉、变异。

(4)上述操作产生的子代和(2)中的非支配解集中的个体合并在一起，形成新的种群。

(5)如果满足终止条件，则结束算法，否则重新转(3)。

3 仿真算例

设置监测区域大小为50m×50m，在其中随机放在100个节点，设置节点感知半径RS=5m,节点的通信半径为RC=10m,初始电量为个单位。网络覆盖率门槛值为0.5，杂交概率为0.8，变异概率取0.1，初始种群个体50个，最大迭代次数为150。算法目标，找到满足覆盖概率约束的，总工作周期T最大的个体解集。算法迭代次数分别设为50,75,100,125时，在每次迭代完成挑选出具有代表性地非劣解，见表1。如表1可知，在算法进行100次迭代过程中，所得到的非劣解分布均匀，解的质量良好，更多的迭代次数并没有更多的改善，只能增加算法的时间。

表1 算法实验结果

图4给出了一个较为理想的Pareto解集，与理论值较为吻合。图4表明，在迭代次数为50的情况下，网络覆盖度的门槛值设定为0.5，如果要求100%的覆盖，则网络生存期为5个单位时间，如果维持最低的覆盖度，则可以保持最大的生存期15个单位时间。调整不同的权重组合会得到不同的变化曲线。在实际工程中，可以根据需要进行设定。

图4 Pareto解集

4 结语

无线传感网覆盖优化是一个多目标优化问题，传统方法难以得到最优解，一般也只能得到一系列的非支配解。在采用遗传方法进行迭代寻优的过程中，个体的编码很大程度上直接影响算法的效率和解空间的质量。本文采用迭代过程中的邻域搜索算法，可以有效地避免算法的早熟收敛，提高算法的质量。与标准遗传算法相比，新算法在网络的有效覆盖度和网络生存期两个方面都有明显的提高，收敛速度也得到了加快。