Page 303 - 《软件学报》2021年第8期

石拓 等:多等级通信半径的无源传感器网络中的覆盖问题 2585

{Δ 1 ,Δ 2 ,…,Δ L };
5. 无源传感器网络的监控周期T={t 1 ,t 2 ,…,t K }以及任意无源节点 i 在不同时间槽 t j ∈T 获取的能量μ i (t j );
6. 无源网络所监控的监控区域R={φ 1 ,φ 2 ,…,φ m }以及每个监控区块φ j ∈R的权值 w j 和面积 a j ;
输出:一个具有最大覆盖质量的全局覆盖C={C t |t∈T}.
以下定理证明了 CR-MC-BFN 问题是 NP-Hard 的.
定理 1. CR-MC-BFN 问题是 NP-Hard 的.
[2]
证明:显然,Shi 等人 所研究的问题 MC-BFN 是 CR-MC-BFN 问题在 L=1 时的特例.因为 MC-BFN 问题是
NP-Hard 问题,所以 CR-MC-BFN 问题也是 NP-Hard 问题. □
3 CR-MC-BFN 问题的近似算法

因为 CR-MC-BFN 问题是 NP-Hard 的,我们在这一章提出了一个两阶段近似算法(two-phase approximation
algorithm,简称 TPA)对其进行求解.该近似算法分为两个阶段,这两个阶段简述如下.
• 阶段 1:节点工作预调度.在给定区域内基本能量分布(定义 5)的情况下,为每个无源节点预分配传输半
径,并给出每个无源节点的调度,从而最大化网络的覆盖质量;
• 阶段 2:节点工作自适应调度.根据节点的实际获能,对阶段 1 中为节点预分配的传输半径和工作调度进
行自适应式的微调,从而进一步最大化网络的覆盖质量.
在以下两节中,我们将详细地介绍这两个阶段.
3.1 阶段1:节点工作预调度
由于周围能源环境的变化十分复杂,对于一个无源节点,预测该节点在特定时间槽内的能量获取是十分困
难的.但是根据能源环境的历史数据,我们可以很容易地预测每个节点可获取能量的最小值.因此,我们可以定
义基本能量分布.
定义 5(基本能量分布). 给定无源节点集合 V,监控周期T,一个基本能量分布E={μ i |i∈V}满足对于任意μ i ∈E,
μ i ≤min{μ i (t)|t∈T}.
对于一个无源网络,基本能量分布可以从历史数据中很容易地得到.基于基本能量分布,我们可以对网络中
节点的工作状态进行提前调度,从而减少节点分布式调度时的能量消耗.我们的节点工作预调度算法大致分为
以下两个步骤.
• 步骤 1(节点集合划分算法):将无源传输节点分为 k 个不相交的集合 D={D 1 ,D 2 ,…,D k },为每个集合中的
无源节点分配通信半径,使得对于任意 D j ∈D,D j ∪S 的导出图是连通的,并且最大化目标函数:
D ∈ ∑ j D ∑ aw i
i
() =
UD i φ ∈ R (D j ) ,
k ∑ a w
i φ ∈R i i
)
其中, R (D = ∑ R .
∈
j iD j i
• 步骤 2(节点集合调度算法):调度步骤 1 中的 k 个集合,从而最大化网络的覆盖质量.
我们在以下两个章节中介绍这两个步骤中的具体操作.
3.1.1 步骤 1:节点集合划分算法
步骤 1 中主要存在两个问题:1) 如何确定 k 的具体值;和 2) 如何分割节点并分配节点的通信半径,从而最
大化目标函数.为了解决这两个问题,步骤 1(见算法 1)中按照如下子步骤进行.
Step 1(Line 1~Line 2):设 k 的最大值为 k max =max{(Δ l /μ j )|1≤l≤L∧μ j ∈E},最小值为
k min =min{(Δ l /μ j )|1≤l≤L∧μ j ∈E}.
Step 2(Line 3~Line 18):对于任意 k,且 k min ≤k≤k max ,重复以下步骤.
i l
(1) (Line 4~Line 5):对于每个无源节点 i∈V,为其分配通信半径 r ,其中,
c
l i =max{l|(Δ l /μ i )≤k−1∧1≤l≤L}.