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

2584 Journal of Software 软件学报 Vol.32, No.8, August 2021

(2) 对于φ i 中的任意两点 p,p′,{j|dis(j,p)≤r s ∧j∈V}={j|dis(j,p′)≤r s ∧j∈V}.
定义 1 中的第 2 个条件表明,处于同一个监控区块中的所有点,均可被相同的无源节点集合所监控.图 2 中
给出了一个监控区块的例子.图 2 中具有 4 个无源节点,根据无源节点的感知半径,监控区域可以被分为 11 个监
控区块.对于任意的监控区块φ i ∈R,我们用 a i 来表示φ i 的面积.

Fig.2 An example of the monitor block
图 2 监控区块的例子
2.2 问题定义
为了有效地监控区域,无源网络需要调度节点,使得在任意时间槽内有无源节点进行工作,并对监控区域进
行监控.因此,我们给出如下局部覆盖的定义.
定义 2(局部覆盖). 给定一个无源传感器网络N(V∪S,E),在时间槽 t 的覆盖 C t ∈V 是一个无源节点集合,且满
足以下条件.
(1) 对于任意一个无源节点 i∈C t ,B i (t)≥B f ;
(2) 由 C t ∪S 导出的图 G t (C t ∪S,E t )是一个连通图,且 E t ={(i,j)|(dis(i,j)≤min{r c (i,t),r c (j,t)})∧(i,j∈C t )}.
定义 2 中的条件(1)表明,在时间槽 t 的局部覆盖中的所有无源节点均可工作.而第 2 个条件表明,由这些节
点和 Sink 节点所构成的图是连通图,这也保障了在时间槽 t 内局部覆盖的连通性.显然,对于一个局部覆盖 C t ,
其所能监控的区域为 () = ∑ iC t R .根据局部覆盖的定义,我们给出如下全局覆盖(或简称覆盖)的定义:
RC
t
i
∈
定义 3(全局覆盖(覆盖)). 给定一个无源传感器网络N(V∪S,E)、一个监控周期T,一个全局覆盖C={C t |t∈T}
是在监控周期T内的所有局部覆盖的集合.
我们定义如下的覆盖质量来度量一个(局部/全局)覆盖:
定义 4(覆盖质量). 给定一个全局覆盖C={C t |t∈T},对于任意局部覆盖 C t ∈C,其覆盖质量为
∑ aw
i RC
() =
QC t φ ∈ ( t ) i i .
∑ i φ ∈R aw i
i
1
( ).
Q
这样,对于全局覆盖C,其覆盖质量为 () =C ∑ Q C t
| T | t∈T
显然,当 Q(C)=1 时,监控区域在监控周期内可以被全覆盖.然而,由于无源节点的特点,一个无源节点很难保
障在任意时刻都可以工作.这样,如何合理地调度无源节点工作,选取节点的通信半径,从而最大化全局覆盖质
量,成为了一个问题.为此,我们定义了通信半径可调整的无源传感器网络覆盖最大化问题(简称 CR-MC-BFN).
该问题的输入输出如下.
输入:
1. 无源节点集合 V 和 Sink 节点集合 S;
2. 无源节点的能量存储空间 B 和无源节点可以工作的最小电量 B f ;
3. 无源节点的感知半径 r s ;
1
4. 无源节点通信半径的 L 个等级{, ,..., }rr 2 r L 以及无源节点在不同通信半径下的单位时间槽能量消耗
c c c