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

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

3.2 阶段2:节点工作自适应调度
在阶段 1 当中,我们根据网络中的基本能量分布,对无源节点进行了预调度,并得到了一个全局覆盖C.然而,
在阶段 1 中所取得的全局覆盖的主要依据是每个无源节点的静态的基本能量分布.如果单独依赖阶段 1 中的全
局覆盖,则会造成节点存储能量无法充分利用的后果.因此在这一阶段,我们将根据网络中每个节点的实时能量
获取以及节点自身所存储的能量,自适应地调度节点进行工作,从而最大化全局覆盖质量.
阶段 2 包含以下两个步骤.
• Step 1:对于任意一个无源节点 i∈V 和任意的时间槽 t∈T,如果 i∈C t ,则 i 在时间槽内工作.
• Step 2:对于任意一个无源节点 i∈V 和任意的时间槽 t∈T,如果 i∉C t ,则 i 按照如下情况判断在时间槽 t
内的工作状态:
(a) 如果∀1≤l≤L,都有 B i (t)−Δ l +kμ i <B f ,则无源节点 i 保持睡眠状态;
(b) 如果∃1≤l≤L,并满足以下两个条件:
(1) min{B i (t)−Δ l +kμ i ,B}≥B f ;
l
(2) ∃∈ ,dis ( , )i j ≤ min{ ( , ), }r j t r .
jC
t c c
则对于每一个满足该条件的 l,为其分配权值 w l =λ/Δ l ,其中,
λ R − ∪ (),Γ = C =R { | j j V∈ − C ∧ dis i r l }.
( , ) j ≤
j Γ∈ j t t c
这里,λ值表示如果将节点 i 加入 C t 之后,可能继续加入 C t 中的无源节点的个数.令 l max =argmax{w l |1≤l≤L∧l 满
足条件(1)、条件(2)},并且调度节点 i 在时间槽 t 工作(即C t =C t ∪{i}),通信半径为 (, )ri t = r c l max .
c
这样,根据阶段 1 和阶段 2,TPA 算法即可完成对无源节点的调度.该算法的时间复杂度、近似比将在下一
章节给出.
3.3 TPA算法的性能分析
3.3.1 时间复杂度
在阶段 1 中,共有 k max −k min 次迭代.在每一次迭代中,需要构造 k 个不相交的无源节点集合.构造无源节点集
合的过程也需要进行迭代,并且并在每一次迭代中选取一个无源节点.因此,为了构造这些无源节点集合,需要
进行最多|V|次迭代.同时,在每次迭代中需要计算每一个无源节点对应于不同的不相交节点集合的权值.这样,
2
构造不相交无源节点集合的时间复杂度为 O(k|V| ),其中,k min ≤k≤k max .因此,阶段 1 的时间复杂度为
2
O((k − k )k |V | ) = 2 O(k 2 |V | ).
max min max max
在阶段 2 中,在每一个时间槽内需要确定每一个无源节点的状态,判断该节点是否满足可以工作的条件.这
样,至多有|V|个节点满足工作条件.对于每一个满足条件的无源节点,需要计算其权值,计算权值的过程的时间
复杂度为 O(L).这样,在阶段 2 的时间复杂度为 O(L|T||V|).
2
根据以上分析,TPA 算法的时间复杂度为 O(k 2 |V | + | L T ||V |).
max
3.3.2 算法近似比
引理 1. 设 C = {C = D | t ∈ T ∧ j mod (k + 1) = m ∧ D ∈ D } 为阶段 1 的输出结果,且 D 为阶段 1 中步骤 1
j t m j m
的输出结果,则有 Q(C)=U(D).
i l
证明:首先,根据阶段 1 中 Step 2 的通信半径构造方法,即对于任意无源节点 i,其通信半径为 r ,且 l i =max{l|
c
()
(Δ l /μ i )≤k−1∧1≤l≤L},我们可知:若节点 i 可以在时间槽 t j 工作,则其工作后的能量满足 Bt ≥ B − Δ .这样,
i
j
f
i l
无源节点 i 在 t j+k 时间槽的能量满足 B i (t j k+ ) = B i ( )t ≥ j B − f Δ + i l kμ ≥ i B .这样,无源节点在 t j+k 时间槽一定可以
f
工作.因此,根据覆盖C的构造,在集合 D m 中的无源节点可以在时间槽 t m ,t m+k ,t m+2k ,…工作.
一般而言,|T|>>k,因此我们可以认为|T|>>nk,其中,n 为正整数.这样,根据覆盖C的构造,覆盖C可被认为是集
合 D 中的无源节点集合的循环工作.显然,在每一个循环中,其覆盖质量为 U(D).这样,在 n 个循环后的覆盖质量
1
为 ()Q C = (nU ( ))D = U ( ).D □
n