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

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

D ∈ ∑ j D ∑ λ i j aw i
i
() =
UD i φ ∈ R (D j ) ,
k ∑ a w
i φ ∈R i i
⎧ |{ |ll ∈ D ∧ φ ∈ R }| ⎫
其中, λ = min ⎨ j i l ,1 . ⎬
j
i
⎩ k ⎭
综上,我们就解决了在无源传感器网络当中的 k-覆盖问题.
5 实验结果
5.1 朴素算法
在介绍实验结果之前,我们首先提出了如下基于贪心策略的朴素算法(naïve algorithm),用来与 TPA 算法进
行对比.
算法 2. 朴素算法.
1
Input: VS R , , ,,{ , ,...,rr r c 2 r c L },T .
s
c
Output: C.
1 C=∅;
2 for each t∈T do
3 C t =∅;
4 while C t ≠V||∃i∈V−C t ,B i (t)≥B f do
5 for each i∈V−C t && B i (t)≥B f do
1
(, )t =
6 ri r ;
c
c
7 if C t ∪S∪{i}的导出图是连通的 then
8 u i =Q(C t ∪{i})−Q(C t );
9 else
10 u i =−1;
11 i=argmax{u i |i∈V−C t ∧B i (t)≥B f };
12 C t =C t ∪{i};
13 C=C∪C t ;
14 更新每个无源节点的能量;
15 return C;
该算法在任意时间槽 t 内构造局部覆盖C t .在任意时间槽 t,该算法将局部覆盖C t 初始化为空集(Line 3),并执
行以下步骤.
Step 1(Line 4~Line 12):当C t ≠V,或存在 V−C t 中的节点 i,且 B i (t)≥B f 时,重复以下子步骤.
(1) 对于任意 i∈V−C t 且 B i (t)≥B f ,设置节点 i 在时间槽 t 的通信半径为 (, )ri t = r .这一步的目的是尽
1
c
c
量减少无源节点的能量消耗;
(2) 对于满足步骤(1)中条件的无源节点 i,如果集合C t ∪{i}∪S 的导出图是连通图,则说明将无源节点
i 加入局部覆盖C t 后,覆盖的连通性可以得到满足,这样,为无源节点 i 分配权值:u i =Q(C t ∪{i})−
Q(C t );否则,为无源节点 i 分配权值 u i =−1;
(3) 对于所有 i∈V−C t 且 B i (t)≥B f ,选取权值最大的无源节点,并加入局部覆盖C t 当中.
Step 2(Line 13):将 Step 1 中所得到的局部覆盖C t 加入全局覆盖C中.
Step 3(Line 14):根据基本能量分布更新无源节点的能量,即:对于 i∈C t ,B i (t+1)=min{B i (t)+μ i −Δ 1 ,B};对于 i≠C t ,
B i (t+1)=min{B i (t)+μ i ,B}.在更新无源节点的能量之后,进行下一时间槽的局部覆盖的构造.