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

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

覆盖 ′ = C {C = j t D m | t ∈ j T ∧ j mod (k max + 1) = m ∧ D ∈ m D }.
A
显然,根据定理 2,Q(C )≥Q(C′).根据引理 3 以及文献[2]中的定理 4,我们有 ()Q ′ ≥C ⎛ ⎜ 1− 1 ⎞ ⎟ Λ Q ( ). ′ C
⎝ e ⎠
Q (C A ) ⎛ 1 ⎞
这样, ≥ ⎜ 1− ⎟ . Λ 定理得证. □
Q (C o ) ⎝ e ⎠
r 2
定理 4. 给定一个无源传感器网络的无源节点集合 V 和监控周期T.如果 c ≤ , α 且:
2.5r s 2
⎛ 1 ⎞ i ⎛ 1 ⎞ n i−
2|| R || i ⎜ ⎟ ⎜ 1− ⎟
r = min{ | ( / ) = k ∧ i V ∧ ∈ 1≤≤ L }, C 2 || R || 2 || R || < , ε
Δμ
l
r
l
i
c
c
max
l
0 i
−
α r 2 ∑ ≤≤ k max 1 n ⎜ ⎜ 2 ⎟ ⎟ ⎜ ⎜ 2 ⎟ ⎟
s
⎝ α r s ⎠ ⎝ α r s ⎠
Q (C A ) ⎛ 1 ⎞ α
则 ≥ ⎜ 1− ⎟ . 其中,α 满足:
⎠
Q (C o ) ⎝ e k max
⎛ 1 ⎞ i ⎛ 1 ⎞ n i−
2|| R || C i ⎜ 2 || R || ⎟ ⎜ 1− 2 || R || ⎟ < . ε
0 i α −
r s 2 ∑ ≤≤ 1 n ⎜ ⎜ 2 ⎟ ⎟ ⎜ ⎜ 2 ⎟ ⎟
⎝ r s ⎠ ⎝ r s ⎠
证明:同样地,构造与定理 3 中同样的全局覆盖,该定理可证. □
值得注意的是:与 Shi 等人 [4,5,26] 的工作不同,我们的问题定义与 TPA 算法中并没有对网络拓扑和环境中能
量源做出假设和特殊规定,所以 TPA 算法在理论上可适用于具有不同的拓扑结构和不同能量源的无源传感器
网络,TPA 算法在无源传感器网络中是一个普适的算法.
4 k-覆盖扩展
在以上章节中,我们认为:若一个监控区块被至少一个无源节点所监控,则该区块就被该无源节点所覆盖.
然而在另一些场景中,由于环境更加恶劣,导致无源节点的可靠性降低.因此,对于任意一个监控区块而言,需要
多个无源节点共同对其进行监控才可以实现完全覆盖,这种覆盖方式被称为 k-覆盖 [30] .为了解决这一问题,在本
节中,我们主要讨论如何扩展 CR-MC-BFN 问题和 TPA 算法,使其可以解决在无源传感器网络中的 k-覆盖问题.
在 k-覆盖中,我们认为:在一个采样周期(时间槽)内,一个监控区块可以被覆盖当且仅当其被至少 k 个无源
节点监控.显然,在 k-覆盖中局部覆盖与全局覆盖的定义保持不变.然而,无源节点能量的不稳定性使得无源节点
无法持续工作,k-覆盖的要求使得覆盖的难度加大,因此我们需要重新定义覆盖质量.
定义 5(k-覆盖质量). 给定一个全局覆盖C={C t |t∈T},对于任意局部覆盖 C t ∈C,其覆盖质量为
∑ λ i t aw i
i
i RC
() =
QC φ ∈ ( t ) ,
t ∑ aw
i φ ∈R i i
⎧ |{ |jj C∈ ∧ φ ∈ R }| ⎫
t
其中, λ = min ⎨ t i j ,1 . ⎬
i
⎩ k ⎭
这样,对于全局覆盖C,其覆盖质量为
1
( ).
Q () =C ∑ Q C t
| T | t∈T
这样,通信半径可调整的无源传感器网络 k-覆盖最大化问题(简称 k-CR-MC-BFN)可描述如下:给定一个无
源传感器网络,一个常数 k,一片监控区域和一个监控周期,输出一个全局覆盖,最大化 k-覆盖质量.
显然,CR-MC-BFN 问题是 k-CR-MC-BFN 问题在 k=1 时的子问题.因此,k-CR-MC-BFN 问题也是 NP-难问
题.为了解决 k-CR-MC-BFN 问题,我们提出了 k-TPA 算法.k-TPA 算法基于 TPA 算法,根据 k-覆盖质量的定义,
我们只需将 TPA 算法中的目标函数改为如下形式,而其他步骤则保持不变: