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

3856 Journal of Software 软件学报 Vol.31, No.12, December 2020

M
i m
P () i = ∑ P ( , ) (8)
h h
m= 1
3 问题描述与分析
基于第 2 节的系统模型,我们给出本文研究问题的形式化定义,并证明该问题是 NP 完全问题.
3.1 问题定义
本文研究问题的目标是最大化系统检测质量 Q.给定监测周期内各个监测点处目标出现的概率 P、节点部
署和调度方案 A 及各监测点在各时隙内检测阈值集合 N={η n,j |n=1,2,…,N,j=1,2,…,J},检测质量 Q 的表达式为
N J
nj
Q = ∑∑ p P (,) (,AN ) (9)
, nj D
n= 1 j= 1
为了控制虚警率,要求各监测点在各个时隙内的虚警率均不可超过给定的阈值α:
P (, )nj (,AN )≤ α (10)
F
假设节点处于工作状态时的能耗功率为 P c ,候选位置 s i 处的节点每个周期可分配的工作时隙数为 B i ,那么
节点需满足能量中性条件,即:
B P ≤ (J − B i )P h ()i (11)
ic
因此,候选位置 s i 处的节点每个周期内可分配的工作时隙数最多为
⎢ JP ()i ⎥
()i
B max = ⎢ () i h ⎥ (12)
⎣ P h + P c ⎦
在第 2.1 节中,我们引入了 0-1 指示变量 v i ,用于表示候选位置 s i 处是否部署节点,即:
v = 1 (13)
i { ∑ J a 0}
j= 1 , ij >
若给定 K 个节点,则 v i 满足:
I
∑ v = K (14)
i
i= 1
候选位置 s i 处的节点每个周期内实际工作时隙数不可超过其最多可分配的工作时隙数,即:
J
() i
∑ a ≤ v B max (15)
, ij
i
j= 1
综上所述,本文研究的问题定义如下.
问题 1. 给定 K 个节点,M 个射频能量源集合 C,N 个监测点集合 O 以及 I 个传感节点候选部署位置集合 S.
如何确定 K 个节点的部署及调度方案 A 以及各监测点各时隙的检测阈值集合 N,使得系统检测质量 Q 最大化,
且各监测点满足虚警率限制条件,节点满足工作时隙限制条件.
结合公式(9)中的目标函数表达式,以及公式(10)、公式(13)~公式(15)中的限制条件表达式,问题 1 的形式化
定义如下:
⎫
N J
nj
maxQ = ∑∑ p P (, ) ( ,AN ) ⎪
, nj D
, AN ⎪
= n 1 = j 1 ⎪
nj
, =
J
s.t. P (, ) ( ,AN )≤α n 1,2,..., , = N j 1,2,..., ⎪
F
I ⎪ ⎪
v
∑ i = K ⎬ (16)
= i 1 ⎪
J ⎪
() i
i
∑ a , ij ≤v B max , = 1,2,...,I ⎪
i
= j 1 ⎪
= v i 1 J , = i 1,2,...,I ⎪ ⎪
{ ∑
1 = j a ij , > 0} ⎭