Page 193 - 《软件学报》2020年第12期

李燕君 等:射频供能传感网面向融合检测的部署调度方法 3859

定理得证. □
我们进一步用函数W(k n,j )来表示不等式(25)的右半部分.大量数据结果显示:当虚警率阈值α<0.45 时,
W(k n,j )为单调递减函数.而在实际应用中,虚警率阈值一般会设定为一个较小的值,例如 0.05 或 0.1.考虑在 k n,j =2
−1
且节点 s 位于融合区边缘的最坏情况,令 R=W (W(2)),即可保证在任何情况下检测率函数为单调递增.
4.2 节点部署调度联合优化贪婪算法
由于问题 2 是 NP 完全问题,提出贪婪算法对节点部署和调度进行联合优化求解该问题,算法简写为 JOGA
(joint optimization greedy algorithm).JOGA 的运行逻辑见算法 1,具体地,JOGA 首先计算节点部署在各个候选部
()i
署位置处时的最大可分配工作时隙数 B max .接着,迭代地遍历所有未部署传感节点的候选位置,对于其中每个候
选位置,再进一步遍历各个时隙,选取 B ()i max 个使得函数 Q 值最大的时隙作为节点部署在该候选位置时的工作时
隙,其余时隙作为充电时隙,如果多个时隙的函数值相同,则从中随机选取.每次遍历完成后选择一个使得系统
检测质量最大的候选部署位置及其对应的节点调度,更新矩阵 A.如果多个候选部署位置的系统检测质量值相
同,同样从中随机选取.
算法 1. 节点部署及调度联合优化贪婪算法 JOGA.
输入:相关模型参数,节点个数 K,虚警率阈值α,融合半径 R;
输出:节点部署及调度方案 A.
1: A=zeros(I,J); k=0
2: for s i ∈S do
()i
3: 根据公式(12)计算 B max .
4: end
5: while k<K do
6: Q=zeros(I,J); A′=A;
7: for s i ∈S do
8: for j=1:J do
9: 假设在候选部署位置 s i 额外部署一个节点,并在第 j 个时隙处于工作模式,令 A′(i,j)=1;
10: 令 (, )ij = ∑ N p P (,) ( ) ′ A ; A′=A;
nj
Q
n= 1 , nj D
11: end
(i)
(i)
()i
12: 找出 Q(i,⋅)中最大的 B max 个元素,用 J 表示这 B ()i max 个元素的列编号,令 A′(i,J )=1;
13: sum_Q(i)= ∑∑ J pP (,) () ′ A ; A′=A;
N
nj
n= 1 j= 1 , nj D
14: end
(i)
15: =i argmax sum Q ; A(i,J )=1; k=k+1; S=S\{s i };
_
i s ∈S
16: end
下面分析该算法的时间复杂度.首先,遍历候选部署位置点计算 B ()i max 的时间复杂度为 O(I),对应算法 1 的第
2 行~第 4 行;其次,while 循环一共运行 K 次,每次最多需遍历 I 个候选部署位置,对于每个候选位置需遍历 J 个
时隙,对于每个时隙,计算 Q(i,j)需遍历 N 个监测点,因此时间复杂度为 O(N),对应算法 1 的第 10 行;然后在第 12
行中寻找 B ()i max 个最大元素的时间复杂度为 O(JlogJ).在第 13 行中计算 sum_Q(i)需要遍历所有监测点的所有时
隙,因此时间复杂度为 O(JN);最后,第 15 行找出 sum_Q 的最大值的时间复杂度为 O(I).综上,该算法的时间复杂
度为 O(I+K(I(JN+JlogJ+JN)+I))=O(KIJ(N+logJ)).

5 性能评估

本节首先引入基准算法,然后介绍了仿真设置,最后通过多组在小规模网络、大规模网络以及真实数据集