无线传感器网络中面向节能覆盖率保持协议的启发式算法与元启发式算法方法

摘要

无线传感器网络（WSN）监控某些站点时，可能会受到传感设备电池难以充电或更换的限制。因此，为了最大化此类网络的寿命，在满足应用需求的同时改善能耗的方法至关重要。在实现该目标的各种方法中，我们专注于基于占空比控制的能源管理方法，使传感器能够在两种模式之间切换：高能耗模式（活动）和低能耗模式（睡眠）。本文提出了两种新的调度启发式算法，用于解决在覆盖一组固定目标的约束下最大化无线传感器网络寿命的问题。第一种是随机贪婪算法，第二种基于模拟退火（SA）。这两种启发式算法都利用了针对该问题的特定知识。实验结果表明，虽然两种算法表现均良好，但贪婪算法更适合中小规模网络，而SA算法在大规模网络中具有竞争优势。

CCS概念

•计算理论 → 模拟退火;
•计算方法 → 规划与调度;
•计算机系统结构 → 传感器网络;

关键词

最大生命周期覆盖问题；无线传感器网络中的区域覆盖；元启发式；模拟退火；节能覆盖率保持协议

1 引言

无线传感器网络（WSN）的应用多种多样，且其应用数量每天都在增加[4]。其中一些部署在受控良好的环境中，便于维护、充电或更换电池。然而，在人类难以进入甚至无法进入的恶劣环境中部署时，传感器可能不易被访问，因此电池无法充电或更换。此类情况可能出现在自然环境中：如偏远沙漠、茂密森林、火山坡地，以及城市环境中：如地震后或工业场所发生灾难性事件之后。

在这种情况下，节能机制对于确保无线传感器网络正常工作至关重要。传感器网络的寿命被定义为满足应用需求的最大持续时间，而大多数情况下，由于电池耗尽导致能量不足，从而限制了网络的寿命。这促使过去二十年中大量研究集中在无线传感器网络的能量守恒问题上，根据[3]，可考虑三种主要方法：占空比控制、数据驱动和移动性。本研究聚焦于占空比控制的能量守恒方法。该方法认为每个传感器能够在某些时间段内关闭其主要的高能耗电路。因此，传感器在一个时隙可能处于 active state 状态，在另一个时隙则处于 sleep state 状态。为传感器确定活动/空闲时段的调度是本文研究的主要内容。传感器迭代执行感知、计算和通信三项主要任务，因此电源管理可以涉及这三个步骤中的任何一个，而在本研究中，我们主要关注感知任务的节能机制。

调度决策主要取决于应用的目标，许多依赖于无线传感器网络的应用都关注对特定区域的监控。从应用角度来看，基本问题是如何获得最佳覆盖率以从环境中收集数据。至少存在两种不同的方式供应用来考虑覆盖率：表面积的覆盖率或区域的覆盖率。

目标。在本研究中，我们关注的是环境包含一些规则分布的目标的后一种情况。这些目标在本文中称为兴趣点（POI）。

综合考虑所有这些因素，我们的问题在于如何在满足兴趣点（POIs）的覆盖率约束和最小化能耗之间找到最佳平衡，这可以表述为在满足应用需求的同时最大化网络寿命。本文介绍了两种基于知识的新算法在解决此问题上所获得的结果：一种是贪心启发式算法，另一种是基于模拟退火（SA）的算法。

本文的其余部分组织如下。下一节概述了主要的相关工作。第3节详细介绍了问题描述。接下来的两节分别描述了我们的贪心算法（第4节）和基于模拟退火的算法（第5节）。第6节展示了仿真实验的结果，并讨论了实验参数的选择，最后给出了一些结论性评述。

2 研究现状

本文所研究的问题是 Maximum Lifetime Coverage Problem (MLCP) 的一个变体。在本研究中，我们关注涉及一组固定点或目标（称为兴趣点 POIs）的变体。每个兴趣点可同时被多个传感器监控。应用要求是在任何时刻都必须监控所有兴趣点中的最小比例。为了最大化网络寿命，我们关注的是调度每个传感器活动的方法，其中每个传感器可能处于活动或休眠状态。

最早尝试解决此类问题的工作之一是由 Slijepcevic 和 Potkonjak 于 2001 年提出的[13]。他们提出了一种启发式算法，该算法由两部分组成：第一部分是将所有传感器划分为满足完全覆盖约束的互斥集合；第二部分是对每个传感器集合的活动进行调度，使得在任意时刻仅有一个集合处于激活状态。由于该方法在网络生命周期方面取得了良好的效果，这项工作启发了众多后续研究。其中，Abrams 及其同事在[2]中提出放宽完全覆盖约束，允许算法仅覆盖目标子集，并针对集合 k 覆盖问题的一种变体提出了三种近似算法，这种放宽约束的方法也在我们的工作中被考虑。一年后，[5]提出了该问题的理论模型：不相交集合覆盖问题（DSC），并证明了其 NP 完备性；随后在[6]中，作者又提出了另一种形式化模型——最大集合覆盖问题（MSC），同样证明了其 NP 完备性。这两个复杂性结果推动了人们寻找高效启发式算法，以提供该问题的近似解。

在过去的十年中，许多针对类似问题的自然启发式方法已被发表[11]。其中包括遗传算法[12]、多目标遗传算法[9]、进化策略[7]、模因算法[14]、粒子群优化[1]、差分进化[16]等。我们最近的研究应用一种通用的、受自然启发的元启发式算法来解决此问题[15]，结果表明它们的效率仍不够高。正如我们之前提到的，解的质量和计算复杂度均不理想。覆盖率问题在不同的场景和无线传感器网络类型下被研究，即动态环境中的无线多媒体传感器网络[7]、基于摄像头的无线传感器网络[14]、定向传感器网络[8]。这些假设导致了不同的问题描述，因此每种方法都需要进行修改，以适用于在其他类型的无线传感器网络中解决覆盖率问题。

我们的方法在寿命的表述以及…

3 问题描述

考虑一个传感器网络 $ S = {s_1, …, s_N} $，该网络由 $ N $ 个传感器节点随机分布在给定的二维矩形区域上构成。该区域被视为一个二维矩形区域。$ F $ 包含一组在二维网格上规则分布的兴趣点（POIs），如图1所示。传感器 $ s_j $ 定义为二维区域中坐标为 $(x_j, y_j)$ 的点，其感知范围为 $ R_s $，电池容量为 $ b $。所有传感器均相同：具有相同的感知范围和相同的初始电池容量。

假设每个传感器可以在两种模式下工作：active mode 和 sleep mode。在激活模式下，传感器 $ s_i $ 能够监测以其为中心、半径为 $ R_s $ 的圆盘范围内的所有兴趣点（POIs），并且我们认为时间被划分为长度相同的时间间隔。用 $ state^j_i $ 表示传感器 $ s_i $ 在时间间隔 $ t_j $ 内的状态。如果传感器 $ s_i $ 在该时间间隔内处于激活模式，则 $ state^j_i = 1 $；如果 $ s_i $ 在时间间隔 $ t_j $ 内处于睡眠模式，则 $ state^j_i = 0 $。

下面给出一些关于问题描述的定义。

传感器 $ s_i(x_i, y_i) $ 覆盖一个 POI $ p(x, y) $，当且仅当它们之间的欧几里得距离 $ d(s_i, p) \leq R_s $

我们用 $ POIs_{obs}(s_i) $ 表示传感器 $ s_i $ 在激活模式下覆盖的兴趣点集合，并用 $ cov(s_i) $ 表示这些兴趣点的数量：
$$
cov(s_i) = |POIs_{obs}(s_i)| \tag{1}
$$

在时间间隔 $ t_j $ 内，由激活的传感器集合覆盖的兴趣点集合表示为 $ POIs_{obs}(t_j) $，即
$$
POIs_{obs}(t_j) = \bigcup_{i=1}^{N} POIs_{obs}(s_i) \mid state^j_i = 1 \tag{2}
$$

在给定的时间间隔 $ t_j $ 内，$ F $ 的覆盖率记为 $ Cov(t_j) $，是指在 $ t_j $ 期间处于激活模式的传感器观测到的兴趣点数量与所有兴趣点数量的比值：
$$
Cov(t_j) = \frac{|POIs_{obs}(t_j)|}{|POIs|} \tag{3}
$$

我们假设任何传感器的能耗取决于其感知范围，使得任何传感器在任意时间间隔内消耗的能量都相同。

因此，我们问题的一个潜在解是所有传感器状态的调度，该调度可以用一个二进制元素矩阵表示。矩阵的每一列 $ j $ 对应于时间间隔 $ t_j $ 内传感器的状态，每一行 $ i $ 表示传感器 $ s_i $ 的活动调度。

无线传感器网络的调度是一个二进制 $ T_{max} \times N $ 矩阵，表示为 $ Sol $，即
$$
Sol(S) =
\begin{pmatrix}
state^1_1 & \cdots & state^j_1 & \cdots & state^{T_{max}} 1 \
\vdots & \ddots & \vdots & \ddots & \vdots \
state^1_i & \cdots & state^j_i & \cdots & state^{T {max}} i \
\vdots & \ddots & \vdots & \ddots & \vdots \
state^1_N & \cdots & state^j_N & \cdots & state^{T {max}}_N \
\end{pmatrix}
$$
其中 $ state^j_i = 0 $ 对应于睡眠状态，1 对应于激活状态。

调度 $ Sol(S) $ 是一个可行解，如果满足以下不等式：
$$
(\forall i) {i=1,…,N} \sum {j=1}^{T_{max}} state^j_i \leq b \tag{4}
$$

Definition 3.5. 我们将 Coverage String $ F $ 从 $ t_1 $ 到 $ t_{T_{max}} $ 时间间隔的覆盖率序列称为，即
$$
Coverage\ String = {Cov(t_1), Cov(t_2), …, Cov(t_{T_{max}})} \tag{5}
$$

对于我们的问题，我们考虑 $ q \in ]0, 1] $ 一个表示 $ F $ 覆盖率最小阈值的实数。如果在给定的时间间隔 $ t_j $, $ Cov(t_j) \geq q $，则认为该时间间隔内应用的覆盖要求已满足。

在这种情况下，无线传感器网络的寿命是 $ Cov(t_j) \geq q $ 成立的总时间间隔数
$$
Lifetime(q) = \sum_{j=1}^{T_{max}} \eta_{t_j} \tag{6}
$$
其中
$$
\eta_{t_j} =
\begin{cases}
1 & \text{if } Cov(t_j) \geq q \
0 & \text{if } Cov(t_j) < q
\end{cases}
$$

参数 $ T_{max} $ 是一个预定义的数值，应设置为大于通过某种方法获得的无线传感器网络寿命的值，且小于上界 $ LifetimeUp $，即
$$
Lifetime(q) < T_{max} \leq LifetimeUp \tag{7}
$$

让我们推导寿命的上限。我们假设 $ F $ 恰好包含 $ N_{POIs} $。

传感器能够监控的兴趣点最大数量等于：
$$
Max(N_{cov_POIs}) = \sum_{i=1}^{N} cov(s_i) \tag{8}
$$

如果我们假设在每个时间间隔内，活动传感器的电池消耗一个单位，则所有传感器在电池耗尽前能够监测的最大兴趣点数量等于：$ Max(N_{cov_POIs}) \times b $

但在每个时间间隔内，只需监控 $ N_{POIs} \times q $ 个兴趣点即可满足应用要求，因此满足覆盖要求的时间间隔的最大数量，记为 $ LifetimeUp $，等于：
$$
LifetimeUp = \frac{Max(N_{cov_POIs}) \times b}{N_{POIs} \times q} \tag{9}
$$

而且这个界限是紧的。事实上，如果所有传感器的集合可以被划分为互不相交的子集，使得每个子集中激活的传感器恰好覆盖 $ N_{POIs} \times q $ 个兴趣点且无重叠，则 $ Lifetime(q) $ 可能等于值 $ LifetimeUp $。

因此，参数 $ T_{max} $ 的上限由公式9定义为 $ LifetimeUp $。

我们将最大生命周期覆盖问题（MLCP）视为应用于无线传感器网络（WSN）的调度问题，用于解决离散二维空间中的区域覆盖问题。根据我们的模型，解决 MLCP 问题的方法应尽量减少每个时间间隔内监控冗余兴趣点（POIs）的传感器数量，以最小化能耗。

$ Lifetime(q) $ 如公式6中所定义，是我们的评估函数。应在所有可行解的空间上对其进行最大化。

然后，最大生命周期覆盖问题可以表述如下：

给定
- 一组数字 $ POIs = {1, 2, …, N_{POIs}} $，每个元素代表一个 POI 的序号，
- 一个包含 $ N $ 个子集 $ S = {S_1, S_2, …, S_N} $ 的集合，其中每个元素 $ S_i \subseteq POIs $、$ i = 1,2,…, N $ 表示传感器 $ s_i $ 所覆盖的兴趣点，并且
- 为表示初始电池容量的整数。

目标：
- 找到子集 ${S’ 1, S’_2, …, S’_m}$ 的最大数量 $ m $，其中 $ S’_j \subseteq S $，使得被覆盖的元素数量 $ |\bigcup {S_i \in S’ j} S_i| $ 满足覆盖率（见公式 10），并且族 $ S $ 中的每个元素 $ S_i $ 最多包含在 $ b $ 个子集 ${S’ {j1}, S’ {j2}, …, S’ {jz}}$ 中（见公式11），即
$$
(\forall j) {j=1,…,m} \frac{|\bigcup {S_i \in S’ j} S_i|}{|POIs|} \geq q \tag{10}
$$
$$
(\forall i)(\exists j_1, …, j_z) \mid S_i \in S’ {j_1}, …, S_i \in S’ {j_z},
$$
其中 $ i = 1, …, N $ 和 $ (\forall k) {k=1,…,z} 1 \leq j_k \leq m $ 以及 $ z \leq b $。

寻找满足(10)的最大子集数量 $ m $ 的目标等同于寿命最大化，对应于传感器节点的活动调度。最后一个方程(11)对应电池容量限制。

MLCP-specific knowledge

通过贪心启发式和基于 SA 的算法（见下文）进行的搜索过程结合了 MLCP 特定知识，并基于调度中列的分类。调度解的所有列被划分为三个组，称为三个子序列：
(1) Redundant Subsequence (RS)，
(2) Excellent Subsequence (ES)，
(3) Unsatisfactory Subsequence (US)。

每个子序列将时间间隔进行分组，使得由活动传感器构成的网络以特定的 coverage ratio 覆盖目标区域。

RS subsequence 的引入是为了揭示可能存在冗余传感器的时间间隔，我们希望将元素从 RS 转移到 ES。RS 被定义为一系列时间间隔 ${t_i}$，在此期间，在至少 $ \delta $ 上，coverage 大于 coverage ratio $ q $。
$$
cov(t_i) > q + \delta, \tag{12}
$$
其中 $ \delta $ 是表示相对于 coverage ratio $ q $ 的预定义下降量的一个小值。

ES subsequence 由调度中的时间间隔 ${t_i}$ 组成，在这些时间间隔内，目标区域的 coverage 在给定 coverage ratio $ q $ 的 $ \delta $ 范围内。
$$
|cov(t_i) - q| \leq \delta \tag{13}
$$

我们使用 ES 作为衡量调度方案在寿命方面高质量的标志。为了延长无线传感器网络的生命周期，应增加 ES 中的多个元素，并且这些元素的值应小于包含在 US 中的元素。

US subsequence 被定义为调度中的时间间隔 ${t_i}$，在此期间目标区域的覆盖度至少低于某一阈值，即
$$
cov(t_i) < q - \delta \tag{14}
$$

设 RS、ES 和 US 中的元素数量分别为 $ N_R $、$ N_E $ 和 $ N_U $ 分别表示。图1所示网络在 $ q=0.55 $ 和 $ \delta=0.05 $ 条件下所构建调度的 RS、ES 和 US 的示例如图2所示。在该调度中，1 表示激活的传感器，0 表示关闭的传感器。根据覆盖率，七个时间间隔被划分为三种类型：ES = {t3, t7}、RS = {t5} 和 US = {t1, t2, t4, t6}。此网络的调度的 Lifetime(0.55) 等于 3。

4 一种贪心启发式算法求解 MLCP

在本节中，我们提出了一种基于知识的迭代式随机贪心启发式算法来求解 MLCP。该算法基于构建一个解树。树根是一个随机生成的解。在每次迭代中，称为前驱的解通过以下描述的两个步骤进行修改，从而形成另一个称为后继者的解。下一次迭代则从前驱与其后继者中较优解对应的节点继续进行。

该算法的伪代码如算法1所示。在每次迭代中，一个调度会经历两种类型的处理过程，其伪代码如过程1（算法2）和过程2（算法3）所示。

过程1的目的是在未达到必要覆盖的时间间隔内，通过合并活动子网络来改进当前解。该目标可通过将 US 中的若干列多次移至 ES 或 RS 来实现。在过程1中，调度按如下方式改变：通过对 US 列中同一行的两个值应用布尔运算函数 OR 和 AND，生成两列新列（算法2中的第5行）。第一列包含 OR 运算的结果，第二列包含 AND 运算的结果。

换句话说，在结果中，第一个被选中的列在所有单元格中包含“1”，只要来自两列的相应单元格中至少有一个包含“1”。第二列包含未在第一列中使用的其余两个值。这些步骤重复 $ k $ 次或不超过 $ \frac{N_U(N_U - 1)}{2} $ 次，其中 $ N_U $ 是 US 中元素的数量。

随着算法的进行，可能出现新解在 Lifetime(q) 意义上并未改进的情况。此时，参数 $ k $（使用过程1的次数）增加1（算法1中的第12-14行）。初始时，$ k $ 等于1。

过程1(US, 1) 的一步所得解的示例如图3所示。该调度是针对图1所示的传感器网络在七个连续的时间间隔内构建的。

对于覆盖率 $ q $ 等于 0.55 且覆盖下降率 $ \delta $ 等于 0.05 的情况，US 包含三个元素 {1, 2, 4}。由于 $ N_U = 3 $，因此该过程重复 $ k $ 或不超过 3 次。例如，初始调度包含对应于 $ t_1 $ 和 $ t_2 $ 时间间隔的两列。在新解中，所选两列中与传感器 s1 和 s3 相关的两对值发生了变化。由于执行了操作（算法2中的第5行），第一个时间间隔的覆盖率提高到了 0.6。因此，网络的 Lifetime(0.55) 也提高了1。解的前驱及其后继者以及对应的 coverage strings 分别在图中（左）和（右）展示。

通过第一次修改（过程1）获得的解随后由过程2进行更改。此阶段的目标是减少能量的冗余消耗，即从 RS 时间间隔中随机选择一个处于激活状态的传感器将其关闭，然后在 US 时间间隔期间重新开启。

过程2（参见，算法3）在当前解上执行，包含以下步骤：从 $ i-th $ RS 列中以概率 $ p_i $ 随机选择一个单元格：
$$
p_i = \frac{1}{n_1}
$$
其中 $ n_1 $ 是该列中值为“1”的单元格数量。我们将所选单元格所在的行记为 $ j $。
- 第1行 US 列中的“0”单元格被更改为“1”。

因此，第一个被选中的单元格等于1。第二个被选中的单元格是从 US 中选取的与前一个单元格在同一行的第一个“0”单元格。然后这两个被选中的单元格交换它们的值。如果在 US（US）中不存在值为“0”的单元格，则前驱解与其后继者相同。上述两个步骤对每个 RS（RS）列依次重复 $ N_R $ 次。

过程2的单步操作导致解变化的一个示例如图4所示。该调度是为图1所示传感器网络在七个连续的时间间隔内构建的。

对于覆盖率 $ q $ 等于 0.55 且覆盖衰减 $ \delta $ 等于 0.05 的情况，初始覆盖序列为
$$
{0.8, 0.16, 0.4, 0.24, 0.64, 0, 0.6}
$$
其中 RS 包含两个元素 $ t_1 $ 和 $ t_5 $。因此，通过改变调度中的第一列和第五列，过程2执行两次。从 $ t_1 $ 列中，所有值为“1”的单元格具有相等的概率 0.16，选取其中一个，例如选择了第4个单元格。所选的“1”单元格将其值更改为“0”，而对应行中来自 US 的第一个“0”单元格（在图中该单元格取自 $ t_3 $ 列）将其值更改为相反值。第一次时间间隔（从 $ t_1 $ 列开始）的调度覆盖率降低，而 $ t_3 $ 的覆盖率增加。

后继解的覆盖序列变为如下：
$$
{0.16, 0.76, 0.56, 0.24, 0.64, 0, 0.6}
$$
因此，ES 中元素的数量增加，Lifetime(0.55) 也提高了1。

前驱调度及其后继者通过 Lifetime(q) 指标进行评估，其中较优的一个将被保存为当前调度，用于下一次迭代。这些步骤重复执行，直到满足停止条件。最后保存的调度即为该算法的结果。

5 模拟退火算法求解 MLCP

模拟退火是一种基于在玻璃和金属冶金中观察到的物理退火过程的受自然启发的元启发式算法，最初由 Kirkpatrick、Gelatt 和 Vecchi 提出[10]。

SA 技术求解 MLCP 的基本思想如算法4所示。

在设置算法的初始参数后，特别是初始温度 $ T $，该算法从随机生成的初始解开始（见第1行），该初始解成为问题的当前解。接下来，从当前解的邻域中随机生成一个新解（见第6行）。如果新解优于当前解，则该新解成为新的当前解（见第9-10行）。如果新解比当前解差，则以概率 $ \exp(-\Delta / T) $ 接受其为新解，该概率取决于当前解与新解的质量差异以及系统的当前温度 $ T $（见第11-13行）。在当前温度 $ T $ 下搜索解的过程持续进行预定义迭代次数（见第4-14行），超过该迭代次数后，系统温度降低（见第15行）。如果停止条件未满足（见第3行），则算法返回到在给定温度 $ T $ 下搜索解的主循环。

$$
\text{算法4 GeneralSA}
$$
1: 生成初始解 $ Sol_{cur} $
2: 设置温度 $ T $
3: while 停止条件未满足 do
4: for $ i \leftarrow 1 $ to $ L $ do
5:       $ Life = \text{计算适应度 of } Sol_{cur} $
6:       生成邻域解 $ Sol_N(Sol_{cur}) $
7:       $ Life_N = \text{计算适应度 of } Sol_N $
8:       $ \Delta = Life - Life_N $
9: if $ \Delta \leq 0 $ then
10:          $ Sol_{cur} = Sol_N $
11: else
12:          $ Sol_{cur} = Sol_N $ 以概率 $ \exp(-\Delta / T) $
13: end if
14: end for
15:    减小 $ T $
16: end while
17: Output:
18: $ Sol_{cur} $

将 SA 应用于求解 MLCP 的主要问题是在当前解的邻域内生成新解。由于 MLCP 可行解具有特定的限制，生成有效解成为一个难题。为了解决该问题，我们提出了一种利用 MLCP 相关信息的算法。该算法的伪代码如下所示（见，算法5）。

$$
\text{算法5 生成邻域解}
$$
1: Input:
2: $ Sol $
3: $ k $
4: 计算 RS, US
5: for $ i \leftarrow 1 $ to $ k_{neigh} $ do
6: for $ j \leftarrow 1 $ to $ RS.size() $ do
7:       选择一个值为“1”的随机单元格 $ i-th $ 剩余集合中的值列，该单元格的行我们记为 $ l $
8:       从 $ US $ 和 $ l-th $ 行中找到第一个 “0” 单元格
9:       交换所选对的值
10: end for
11:    $ j = j + 1 $
12:    $ i = i + 1 $
13: end for
14: Output:
15: $ Sol $

Generating neighbouring solutions

生成后续解基于在当前调度的某一行中交换一对相反值。邻域解与当前解相比，在给定解的基础上改变了若干位。我们将这种由改变的位对数量定义的特征称为 neighbourhood size，并将其记为 $ k_{neigh} $—邻域。

以这种方式，在更改调度中的两个随机单元格的情况下，我们从给定解得到一个 1-邻域中的解。随机邻居的生成方式如下：$ k_{neigh} $ 次从同一行中随机选择的两个相反值进行交换（见算法5）。还会计算关于解的附加信息，例如每个时隙的覆盖率，据此将时间线划分为 RS、ES 和 US。基于知识的邻域生成过程的思想是：在冗余子序列中关闭一个活动传感器，以减少被冗余覆盖的兴趣点数量；并在第一个不充分子序列中开启该传感器，以增加额外时间间隔内的覆盖率。这些步骤可能提高所生成解的寿命。

6 实验结果

在本节中，我们展示了所提算法实验研究的一些初步结果。为了将这两种方法的性能与其他最先进的解决方案进行比较（这些方案需要适应我们提出的 MLCP 变体），更多的实验仍在进行中。每种算法的性能均通过九个 problem instances 的测试进行评估。每个 problem instance 由传感器数量 $ N $、传感器坐标 $(x, y)$、在目标区域上均匀分布的兴趣点数量、感知范围 $ R_s $ 以及电池容量 $ b $ 定义。

覆盖要求由两个实数组成：所需的覆盖率百分比 $ q $ 和相对于 $ q $-要求的允许下降值 $ \delta $。

我们考虑由数量分别为 100、200 和 300 的传感器组成的无线传感器网络。对于每个 $ N $ 值，我们创建了三个实例，这些实例因传感器的随机分配而不同，因此实验研究中使用了九个实例。每个实例表示为 Instance{indicator of network size}{order number of WSN instance}，其中 $ N $ 等于 indicator of network size 乘以 100。例如，实例23表示由 200 个传感器组成的无线传感器网络的第三个实例。为了测试目的，创建了以下实例：
- instance11, instance12, instance13 对于 $ N=100 $,
- instance21, instance22, instance23 对于 $ N=200 $,
- instance31, instance32, instance33 对于 $ N=300 $。

感知范围 $ R_s $ 和电池容量 $ b $ 的值分别等于 20 m 和 10 t.u.。作为目标区域，我们考虑在尺寸为 $ 100 \times 100 \, m^2 $ 的方形区域内兴趣点呈均匀分布，且相邻兴趣点之间的步长 $ g $ 等于 10 m。

应选择算法参数为每种算法（贪心启发式和 SA）的最佳值集合。SA 由以下值定义：温度根据对数降温方案进行冷却，初始温度 50，温度周期长度 25，冻结水平 10，最大迭代次数 100。终止条件如下：超过最大迭代次数或达到冻结温度水平。

贪心启发式需要设置等于 150 的迭代次数，之后算法停止。

本节中的所有实验结果均基于每个问题实例进行十次运行的平均值。

图5展示了这两种算法在典型运行中的一个示例，呈现了贪心算法和模拟退火算法在三个由 100、200 和 300 个节点组成的实例上，随着 Lifetime(q) 函数计算次数的变化所得到的 Lifetime(0.8) 的动态变化。

可以注意到，两种算法的行为有所不同。当模拟退火算法以线性速度达到其最大值 Lifetime(0.8) 时（对于 300 个节点约为 190，200 个节点约为 130，100 个节点约为 60），greedy algorithm 以不同的速度趋近其最大值，达到的 Lifetime(0.8) 分别为：300 个节点时约为 108，200 个节点时约为 80，100 个节点时约为 62。对于 300 个节点，模拟退火算法找到了更好的解（约 190 对比约 108），且计算代价大致相同（约 6000 次迭代）。对于 200 个节点情况类似，但 greedy algorithm 的计算代价大约是模拟退火算法的两倍（约 4000 次迭代对比约 8100 次迭代）；而对于 100 个节点，greedy algorithm 略优（60 对比 62），但计算代价却高出一倍（约 2000 次迭代对比 4150 次迭代）。

Experiment 2

为了更详细地研究这两种算法的行为，进行了下一次实验，通过多次运行算法获得结果。表1包含了 greedy 和模拟退火算法得到的 Lifetime(q) 函数值的最大值、平均值和标准差。

从表中可以看出，对于具有 100 个节点的较小网络，greedy algorithm 的 Lifetime(q) 的平均值和最大值更优。具有 200 个节点的网络也得到类似的结果，但差异很小。对于包含 300 个节点的网络，模拟退火算法比 greedy algorithm 提供了更好的结果，但两种算法结果之间的差异仍然很小。

值得注意的是，对于所有情况，SA 计算得到的标准差优于 greedy algorithm 提供结果所计算的 $ \sigma $-值。这表明 SA 比 greedy algorithm 更稳定。因此，我们可以假设在较大的问题实例中，SA 应该比 greedy 提供更好的解。

instance	greedy Max 平均 ± σ	SA Max 平均 ± σ
N=100
instance11	77, 79.0 ± 5.3	71, 74.0 ± 1.41
instance12	82, 71.0 ± 5.39	77, 68.0 ± 1.73
instance13	74, 74.0 ± 6.09	71, 68.0 ± 1.73
N=200
instance21	154, 148.0 ± 8.49	153, 144.0 ± 2.0
instance22	152, 151.0 ± 6.09	149, 149.0 ± 1.73
instance23	156, 152.0 ± 7.62	152, 147.0 ± 2.0
N=300
instance31	230, 220.0 ± 7.55	232, 223.0 ± 2.0
instance32	225, 221.0 ± 22.21	227, 223.0 ± 2.0
instance33	227, 226.0 ± 6.0	227, 226.0 ± 2.23

结论

本文考虑了在无线传感器网络（WSN）中以覆盖率要求 $ q $ 定义的非完全覆盖假设下，将寿命最大化问题表述为 MLCP 的问题。该问题属于 NP 难问题类别，具有较高的计算复杂度，因此有必要采用能够提供近似解的算法。为解决此问题，我们提出并研究了两种集中式基于知识的算法：随机贪心启发式和模拟退火算法。

实验研究结果表明，尽管两种算法在较广泛的节点数量范围内均表现出色，但贪心启发式算法对于中小型网络略优，而 SA 算法在大规模网络中更具竞争力。