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

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

需要指出的是:对于无源节点 i 而言,若不存在满足条件的通信半径等级时,则不考虑该节点.
(2) (Line 6~Line 17):设 D 1 =D 2 =…=D k =∅,并运行以下步骤.
a) 对于每一个无源节点 iV∈ − D ,按如下情况计算 i 对于每一个 D j 的收益:如果 D j ∪
j
1 ∪ ≤≤ k j
{i}的导出图为非连通图,则 u i,j =0;如果 D j ∪{i}的导出图为连通图,则:
u , ij ∑ = D ∈− j | ∪ hD k h | |+ ∪ hD j ∪ {}i i ∑ | − R D ∈ | ∪ R i D j R i |.
k D D
j D
∈
∈
∈
这样,对于无源节点 i,其整体收益为 u = max{u | D ∈ D } ,其中, j = argmax{u | D ∈ D };
, ij , ij j , ij j
b) 对于V − ∪ D 中的节点,选取最高收益节点 i′,其中, u = max{u | i V∈ − D };
j
j
1≤≤ k j ′ , ij , ij 1 ∪ ≤≤ k j
c) 将 i′放入 D 中,即 D = D ∪ {}i′ ;
j j j
d) 重复以上 3 个步骤,直到V − ∪ D =∅ ;或对于任意 iV∈ − D ,u = ... u= = 0 .
j
1≤≤ k j 1 ∪ ≤≤ k j i ,1 , i k
j
(3) (Line 18):计算 U k =U({D 1 ,D 2 ,…,D k }).
Step 3(Line 19):选定 k 的值为 k′=argmax{U k |k min ≤k≤k max },并按照 Step 2 中当 k=k′时分配节点的通信半径
和集合 D 1 ,D 2 ,…,D k′ .
算法 1. 节点集合划分算法.
Input: V , ,S R ,,{ , ,..., }r r 1 r 2 r L .
s c c c
Output: D.
1 k min =min{(Δ l /μ j )|1≤l≤L∧μ j ∈E};
2 k max =max{(Δ l /μ j )|1≤l≤L∧μ j ∈E};
3 for each k min ≤k≤k max do
4 for each i∈V do
5 l i =max{l|(Δ l /μ j )≤k−1∧1≤l≤L};
6 Let D 1 =D 2 =…=D k =∅;
7 while V − 1 ∪ j k D ≠∅ or iV∀ ∈ − 1 ∪ ≤≤ ≤ j≤ k D j ,u = i ,1 u i ,2 = ... u= , i k do
j
8 for each i V∈ − D do
1 ∪ ≤≤ k j
j
9 for each D j ∈D do
10 if ∃∈ D j && dis ( , )i i′ ≤ min{ ,r r c i l ′ } then
i l
i′
c
=
| − R
11 u , ij ∑ D ∈− j | ∪ h∈ D k h | |+ ∪ h∈ D j ∪ {} i i ∑ D ∈ | ∪ R i D j R j | ;
∈
k D D
j D
12 else
13 u i,j =0;
14 j = argmax{u , ij | D ∈ j D };
15 u , ij = max{u , ij | D ∈ j D } ;
16 u ′ , ij = max{u , ij | i V∈ − 1 ∪ ≤≤ k D j };
j
17 D = D ∪ {}i′ ;
j
j
18 U k =U({D 1 ,D 2 ,…,D k });
19 k′=argmax{U k |k min ≤k≤k max };
20 return D={D 1 ,D 2 ,…,D k′ };
3.1.2 步骤 2:节点集合调度算法
设 D={D 1 ,D 2 ,…,D k }为步骤 1 中的返回结果,则步骤 2 按照如下构造全局覆盖:
对于任意时间槽(采样周期)t j ∈T,如果 j mod (k+1)=m,则 C = D ,即
j t m
j
C = {C = D | t ∈ T ∧ mod (k + 1) = m ∧ D ∈ D } .
j t m j m