采用贪婪启发式的异构WSNs 部分覆盖算法*

陈志国，滕桂法

（河北农业大学信息科学技术学院，河北 保定 071000）

0 引言

无线传感网络（Wireless Sensor Networks，WSNs）由多个微型传感节点构成［1］，其广泛应用于事件检测，如入侵检测、危险区域检测等。利用WSNs 中的节点感测环境，再将感测数据传输至控制中心，进而实现对环境的监测目的［2-3］。

在监测区域部署WSNs 的目的在于监测目标区域的异常情况，如森林防火检测。这就要求监测区域被节点覆盖或者满足监测区域的覆盖要求［3］。若出现覆盖空洞区域或覆盖要求不能满足，就可能会出现对异常情况的漏检。覆盖要求是指针对不同应用环境，对监测区域的覆盖面积有不同要求。因为有些应用并非要求100%覆盖（全覆盖），只需部分区域覆盖，即部分覆盖［4］。如图1 所示，4 个不同监测区域的覆盖要求并不同，如A 区域的覆盖要求为80%，而B 区域要求60%。

图1 部分覆盖等级

同时，通常WSNs 是由大量的微型传感节点构成，这些节点可能存在一些特性不同。即使是同类传感节点，也可能因硬件故障问题而表现出不同的特性。因此，本文讨论的对象是异构WSNs 的部分覆盖问题［5-7］。在异构WSNs 中，传感节点具有不同的感测和通信范围。

为此，本文提出基于贪婪启发式的部分覆盖（Greedy Heuristic -based Partial Coverage ，GHPC）算法。GHPC 算法引用贪婪启发式算法，并通过覆盖冗余概念选择节点，再利用这些节点满足部分覆盖要求。选择覆盖贡献率大的节点感测环境，这有两个原因：1）选择覆盖贡献率大的节点，可以用更少的节点满足覆盖要求；2）保持节点连通，降低了能耗。本文的主要工作在于：1）对异构WSNs 的部分覆盖问题进行了形式表述；2）用贪婪启发式算法求解；3）建立仿真平台分析算法性能。

1 约束条件及问题描述

1.1 约束条件

假定N 个节点随机分布于L×W 的区域A 内，且这些节点分为m 类，每类节点具有不同的感测半径和通信半径［8］。Ri、Ci分别表示节点Si的感测半径、通信半径。因此，不同类节点的通信和感测区域不同。图2 显示了不同类的节点Si和Sj的通信和感测区域。通常，感测半径大于通信半径。

图2 不同节点的感测和通信区域

此外，如果节点Si在节点Sj的通信范围内，则节点Si能与节点Sj通信，反之亦然。同时，若节点Si与Sj的欧氏距离小于Ri，则节点Si与节点Sj有覆盖重叠［9］。用σ 表示部分覆盖率。若σ=100，则100%覆盖。σ 等于覆盖面积与总的监测区域面积之比。

为了降低网络能耗，每个节点具有空闲和激活两种状态［10］。若节点未被选择去覆盖（激活），则进入休眠。

1.2 问题描述

GHPC 算法的目的在于：从N 个节点中选择部分节点进行工作，即加入覆盖集（Cover Set，CS），并由这些节点覆盖监测区域，进而满足覆盖要求。

先定义覆盖冗余变量ρij，其表示节点Si与节点Sj是否存在覆盖重叠，定义如式（1）所示。

再定义二值变量γi，其表示节点Si是否加入了CS。如果节点Si加入CS，则γi值为1，否则为零，如式（2）所示：

因此，GHPC 算法需解决的问题可形式化表述，如式（3）所示：

2 GHPC 算法

GHPC 算法要解决的问题就是如何从N 个节点中选择n 个节点满足式（3）。然而，文献［12］已分析证实式（3）是NP 问题。为此，GHPC 算法引用贪婪启发式算法求解。

GHPC 算法先从位于监测区域中心位置的节点中随机选择一个节点加入CS 集。然后，再从它的一跳邻居节点中选择覆盖贡献率最大的节点加入，重复执行，直到满足覆盖要求σ。

具体而言，首先，从监测区域中心随机选择节点为Sk，即Sk→CS。Mk表示节点Sk的一跳邻居节点。然后，计算Mk内每个节点的覆盖贡献率，再选择覆盖贡献率最大的节点加入CS，如式（5）所示：

其中，|Mk|表示Mk内节点个数。

然后，再判断CS 内节点的覆盖区域是否满足部分覆盖要求σ，如果满足，则停止；否则继续向CS添加节点，直到满足部分覆盖要求。

图3 GHPC 算法伪代码

GHPC 算法是利用贪婪启发式算法构建CS。多数情况是在监测区域内密集部署传感节点，因此，可建立多个CS。GHPC 算法的伪代码如图3 所示。

图4 显示GHPC 算法构建CS 的示例。图4 中有10 个节点，且这10 个节点分为两类，这两类节点的覆盖半径不同。图4（a）显示这10 个节点分布情况。

图4 GHPC 算法构建CS 示例

首先，先选择覆盖贡献率最大的节点。从图4可知，节点5 具有这种特性，因此，节点5 作为首选节点加入CS，如图4（b）所示。然后，节点2、4、6、8和9 作为第2 轮加入CS 的候选节点，原因在于：1）它们能够提高覆盖率；2）它们是节点5 的邻居节点，选择它们可以保证网络连通率。在这些节点中，再计算各自的覆盖贡献率，选择具有覆盖贡献率最大的节点加入，节点4 具有这种特性。因此，节点4 加入CS，如图4（c）所示。依次类推，节点8、节点1和节点6 分别加入CS，进而满足部分覆盖要求。

3 性能仿真

为了更好地分析GHPC 算法的性能，利用NS-2.34 软件建立仿真平台［13］。N 个传感节点分布于100 m×100 m 内。考虑两类节点（m=2），且第1类节点的感测半径为15 m，通信半径为15 m，而第2 类节点，感测半径为18 m，通信半径为20 m。此外，考虑3 类部分覆盖要求（σ=0.95，0.80，0.60）。

第1 类节点感测半径与通信半径相同，而第2类节点不同。若N 个节点内第1 类节点数越多，网络同构性越高。假定第1 类节点数与第2 类节点数的比例为m1∶m2。如果N=100，若m1∶m2=1∶1，则第1 类、第2 类节点各为50 个。

3.1 实验1

首先分析节点数对活动节点数的影响。所谓活动节点数就是指CS 内的节点数。显然，在满足部分覆盖要求情况下，活动节点数越小，性能越好。图5分别显示了m1∶m2=1∶1 和m1∶m2=1∶3 两种情况下的活动节点数。

图5 活动节点数（实验1）

从图5 可知，σ 越高，活动节点数越多。原因在于需要更多的节点满足更高的σ 要求。此外，节点数N 的增加对活动节点数的影响并不大，活动节点数主要取决于部分覆盖要求σ。将图5（a）与图5（b）对比，发现第2 类节点数的增加，降低了活动节点数，原因在于：第2 类节点的感测半径大于第1 类节点。这样的节点越多，越容易满足覆盖要求。

3.2 实验2

本次实验对比分析，选择PCP［14］和CCP［15］作为参照。600 个节点随机分布于100 m×100 m 内。图6 分别显示了在m1∶m2=1∶0 和m1∶m2=0∶1两种情况下，各自算法的活动节点数。

图6 活动节点数（实验2）

从图6 可知，部分覆盖要求σ 的增加提高了活动节点数。与PCP、CCP 算法相比，提出的GHPC 算法能够有效地降低活动节点数。此外，对比分析m1∶m2=1∶0 和m1∶m2=0∶1 两种情况，不难发现：前者所需的活动节点降低。原因在于m1∶m2=1∶0 表明600 个节点全是第1 类节点，即同构网络，而后者m1∶m2=0∶1，尽管全是第2 类节点，但它们的通信半径和感测半径并不相同。这不利于降低活动节点数。这主要是因为：在保证网络覆盖率的同时，也需要满足网络连通率。

4 结论

针对异构WSNs 部分覆盖问题进行研究，先对部分覆盖问题进行形式化表述，然后再利用贪婪启发式算法求解，实现以最少的节点数满足覆盖要求。通过实验分析可知，提出的GHPC 算法能够以少的节点数满足覆盖要求。

本文是在给定的覆盖要求条件下，利用贪婪启发式算法部署传感节点。然而，本文并没有考虑到网络能耗问题，也没有分析同构网络与异构网络的能耗差异。这将是后期的工作方向。此外，传感节点的部署问题是一个NP 问题，属系统优化问题。而自动学习机算法能够有效地处理优化问题。自动学习机在节点部署方面的应用将是今后分析研究的重点。