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

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

定理 2. 设C,C′分别为阶段 1 和阶段 2 的输出结果,则有 Q(C′)≥Q(C)=U(D).
证明:显然,在阶段 2 中的节点调度并没有减少不相交无源节点集合 D 1 ,D 2 ,…,D k 中的节点,因此我们有
Q(C′)≥Q(C).又根据引理 1,我们有 Q(C′)≥Q(C)=U(D). □
D ∈ ∑ j D ∑ aw i
i
引理 2. 对于任意正整数 k, () = i φ ∈ R (D j ) 都是次模的.
UD
k ∑ a w
i φ ∈R i i
证明:显然, k ∑ a w 为常数.为了证明 U(D)为次模函数,我们只需证明 ∑ j D ∑ aw 是次模的.为
i φ ∈R i i D ∈ i φ ∈ R (D j ) i i
了证明 ∑ j D ∑ aw 是次模函数,我们只需证明 (UD = ∑ a w 为次模函数.
)
D ∈ i φ ∈ R (D j ) i i j i φ ∈R (D j ) i i
令δ i U(D j )=U(D j ∪{l})−U(D j ),则我们有:
i ∑
δ U (D = ) ∑ aw − aw = i φ ∑ a w = l − ∑ a w .
l j i φ (D ∪R j { }) i i i φ ∈ ∈ R (D j ) i ∈ (D ∪R j { })− l R (D j ) i i i φ ∈ R R (D j ) i i
l
假设存在一个节点集合 D′ ,满足 D′ ⊂ D ,且 UDδ ( ′ ) U= (D′ { })l − U (D′ ∪ ).
j j j l j j j
因为 D′ ⊂ D , 我们有 R − (D ⊂ R ) R − R (D′ 因此,我们有:
).
j j l j l j
i ∑
aw ≥ i φ ∈ ∑ a w .
i φ l −R R (D′ j ) i ∈ l −R R (D j ) i i
即 UDδ l ( ′ ≥ δ l UD j ) .根据次模函数的定义,我们有 U(D j )是次模函数,因此,U(D)为次模函数. □
(
)
j
引理 3. 给定一个 k′值,我们定义问题 P 为:构造 k′个不相交的无源节点集合 D={D 1 ,D 2 ,…,D k′ },满足每个无
i l
源节点的通信半径 r ,其中,l i =max{l|(Δ l /μ i )≤k′−1∧1≤l≤L},且每个集合中的无源节点与 Sink 节点的导出图为
c
UD′ ) 1
(
o
连通图,并最大化 U(D).设 D 为该问题的最优解,D′为阶段 1 返回的结果,则有 ≥ 1− .
(
UD o ) e
证明:在阶段 1 中,会按照 k 值从 k min 到 k max 的顺序,根据贪心思想,迭代地构造不相交的无源节点集合,并选
取目标函数值最大的 k 值.这样,对于阶段 1 不同 k 取值所得到的目标函数值,我们有 U(D′)=max{U k |k min ≤k≤
k max },其中,U k =U({D 1 ,D 2 ,…,D k }),且 D 1 ,D 2 ,…,D k 为阶段 1 中当 k 值为 k 时的输出结果.
o
这样,当 k=|D |=k′时,我们有 U(D′)≥U k′ .又因为目标函数 U(⋅)对于任意 k 值都是次模的(引理 2),这样,我们有
U k′ ≥ 1− 1 , 从而有 UD′ ) ≥ 1− 1 . □
(
(
UD o ) e UD o ) e
(
[2]
根据 Shi 中的定理 4 和定理 5,我们给出以下两个定理.在这两个定理中,我们将给出 TPA 算法的近似比.
o
A
设C 为本问题的最优解,C 为 TPA 算法输出的解.
定理 3. 给定一个无源传感器网络的无源节点集合 V 和监控周期T,令:
4
Λ = 22 ∫ ar + 2 a r − 2 rd sin( ),
a
α r s (, ) Θ∈ 11 2 2 1 1
xy
r α r ⎛ 2 + d − 2 r ⎞ 2 r ⎛ 2 + d − 2 r ⎞ 2 r α
其中, r = 1 s , r r = 2 s ,d = x + 2 y 2 ,a = 1 arccos ⎜ 1 2 ,a = ⎟ 2 arccos ⎜ 2 1 , ⎟ Θ表示一个半径为 s .
22 ⎝ 2rd ⎠ ⎝ 2r d ⎠ 2
2
1
r 2
l
如果 c ≥ , α 其 中 , r = c min{ |r c l (/Δμ = l i ) k max ∧ i V∈ ∧ 1≤≤ L }, 且α满足:
2.5r s 2
⎛ 1 ⎞ i ⎛ 1 ⎞ n i−
2|| R || C i ⎜ 2 || R || ⎟ ⎜ 1− 2 || R || ⎟ < , ε
α r 2 ∑ ≤≤ k max 1 n ⎜ ⎜ 2 ⎟ ⎟ ⎜ ⎜ 2 ⎟ ⎟
−
0 i
s
⎝ α r s ⎠ ⎝ α r s ⎠
Q (C A ) ⎛ 1 ⎞
则有 ≥ ⎜ 1− ⎟ . Λ
Q (C o ) ⎝ e ⎠
证明:构造全局覆盖C′如下.
按照阶段 1 中的方法,构造 k max 个不相交的无源节点集合 D = {,D D 2 ,...,D k max }, 且每个无源节点的通信半径
1
设为 r = c min{ | ( /r c l Δμ i ) = k max ∧ i V∈ ∧ 1≤≤ } L ,并周期性调度这 k max 个无源节点集合进行工作,从而构造全局
l
l