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

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

3.2 问题转化
问题 1 的解包含 K 个节点的部署及调度方案以及 N 个监测点在 J 个时隙的检测阈值.根据 Neyman-Pearson
法则 [24] ,当虚警率恰好达到给定阈值α时的检测率最大.因此,结合公式(5)求解 P F (, )nj = α ,可得到最优检测阈值:
σ 2 F − 1 (1 α− )
η , nj = I Y (17)
∑ ra ,
, in i j
i= 1
其中, F Y − 1 ()⋅ 为卡方分布的累积分布函数 F Y (⋅)的逆函数.由此,问题 1 可转化为如下等价问题.
问题 2. 给定 K 个节点,M 个射频能量源集合 C,N 个监测点集合 O 以及 I 个传感节点候选部署位置集合 S.
如何确定 K 个节点的部署及调度方案 A,使得系统检测质量 Q 最大化,且检测阈值满足限制条件,节点满足工作
时隙限制条件.
因此,问题 2 的形式化定义如下:
N J ⎫
nj
maxQ = ∑∑ p P (,) ( )A ⎪
A , nj D
= n 1 = j 1 ⎪
σ 2 − 1 (1 α F − ) ⎪
s.t. η = Y , = 1,2,..., , = n N j 1,2,..., ⎪
J
, nj I ⎪
∑ ra , ⎪
, in i j
= i 1 ⎪
I ⎪
∑ i = K ⎬ (18)
v
= i 1 ⎪
J ⎪
∑ a ≤ v B () i , = 1,2,...,I ⎪
i
, ij i max
= j 1 ⎪
= v 1 , = i 1,2,...,I ⎪
i { ∑ J a 0} ⎪
1 = j ij , >
⎪
⎪
⎭
3.3 问题复杂度分析
定理 1. 问题 2 是 NP 完全问题
证明:为证明问题 2 是 NP 完全问题,我们将问题 2 归约为一个已知的 NP 完全问题——k-不相交集合覆盖
判定问题 [26] (k≥2).k-不相交集合覆盖判定问题的描述如下:给定一个包含 N 个元素的集合U={u 1 ,…,u N },令集合
V={V 1 ,V 2 ,…}为U的子集构成的集合,即∀i,V i ⊆U,判断能否找到V的 k 个不相交的子集,且每个子集的并集均为U.
对于任意一个 k-不相交集合覆盖判定问题的实例,我们构造问题 2 的实例.首先,令信号衰减系数 u→+∞,令噪声
2
信号的方差σ =0,可得检测阈值均为 0.这样,检测模型简化为:当目标距离节点不超 d 0 时,可 100%检测到该目标,
否则不能检测到.接着令 K=I,即各个候选部署位置处均部署 1 个节点.进一步地,令 B i =1,即部署的节点在一个周
期内工作时隙个数均为 1,该条件可通过控制能量源的位置达到.这样,集合U中的每个元素 u n 对应集合 O 中的
一个监测点,集合V中的每个V i 对应位于 s i 处的节点,该节点能覆盖集合 O 中的若干监测点,只要位于 s i 处的节
点处于工作模式(不妨假设在第 j 个时隙处于工作模式)且与监测点 o n 的距离不超过 d 0 ,则有 P D (, )nj = 1.
综上可得问题 2 的判定问题的一个特例:给定包含 N 个监测点的集合 O,包含 K 个传感节点的集合 S,每个
N
J
节点在 J 个时隙内只工作 1 个时隙,判断是否存在这 K 个节点的调度方案,使得检测质量 Q = ∑∑ p , nj .该特例
n= 1 j= 1
的构造可在多项式时间内完成,所以问题 2 是 NP 难问题.又易知问题 2 属于 NP,因此问题 2 是 NP 完全问题. □
4 算法设计

本节首先分析了融合半径对检测率的影响,给出了融合半径取值上限,然后提出了基于贪婪算法的节点部
署调度联合优化方案.