Page 253 - 《软件学报》2021年第9期

钟萍 等:一种高效低能耗移动数据采集与无线充电策略 2877

⎛ ⎞ ⎛ ⎞
(, , , , )f μλ α = ∑∑
a
Lr C i a (rT − i a ) ∑ μ i ⎜ ⎜ rT − i a M i ⎟ ∑ ⎟ + λ i a ⎜ r + ∑∑ i a f − ⎜ gi ∑ f ⎟ ij a ⎟ + ∑
∈ ⎝
∈
∈
∈
∈
∈
∈
∈
a A iN a h i N aA i ⎠ aA iN h a ⎝ g C , i a j P . i a ⎠
⎛ (13)
∑∑ α i ∑ fe +⎜ ij a t f e + ∑ mi r r e − i a s E ⎞ i ⎟
a
a
⎜
∈
∈
∈
∈
aA iN a h ⎝ j P , ia m C , ia τ ⎟ a ⎠
a
拉格朗日的对偶函数是公式(9)在 r 的最小值,那么对偶函数的目标函数为
i
D (, , )μ λα = min ( , , , , )L r f μ λ α (14)
r
拉格朗日对偶函数可定义为如下形式:
max ( , , )μ λα =D max min ( , , , , )μ λ αL r f (15)
r
假设 r = * {r i a | a∈ , A i ∈ N a h } 和 f = * { f ij a | a∈ , A i ∈ N a h , j ∈ P a , i j } 为问题 P1 的最优解.该拉格朗日函数可分解为
两个子问题,即节点速率控制问题和路由调度问题.去除 L(r,f,μ,λ,α)中的常数项,该可以分为两个子函数形式:
r +
a a
L 1 (, , , )r μλ α = C i a (r T − ∑ ∑ i a ) ∑ ∑ r Tμ + i a i ∑ ∑ λ i i ∑ a a ∑ α i i r e s
∈
∈
∈
∈
∈
∈
∈
∈
aA iN h a i N aA i a A iN a h a A i N h a
(16)
= (Cr T ) r Tμ− ∑∑ i a i λ + i i r + α i i r e s )
a a
a
a
a a
(
i
i
∈
∈
aA iN a h
⎛ ⎞ ⎛ ⎞
a
(, , )λα =
a
a
Lf λ ⎜ i ∑ f − ∑∑ gi ∑ f ⎟ a + α ⎜ i ∑ f e + ∑∑ a ∑ f e ⎟ a
2 ⎜ ij ⎟ ⎜ ij t mi r ⎟
∈
∈
∈
∈
∈
∈
aA iN a h ⎝ g C , ia j P . i a ⎠ aA i N a h ⎝ j P , ia m C , ia ⎠
∈
∈
⎛ ⎞ ⎛ ⎞
a
a
a
a
= ⎜ ⎜ λ i ∑ f + ∑∑ gi a α i ∑ f e ⎟ mi r ⎟ ∑ ⎜ ∑ α + i ∑ f e − ⎜ ij a t ∑ λ i ∑ a f ⎟ ij a ⎟ (17)
∈
∈
∈
∈
∈ ∈
∈
∈
∈
aA iN a ⎝ h g C , ia m C , ia ⎠ aA ⎝ i N h a j P , ia iN a h j P . ia ⎠
⎛ ⎞
= ⎜ f gi a (λ i a α + ∑∑ i a e r ) +⎜ ∑ f ij a (α i a e − t λ i a )⎟ ∑ ⎟
∈
∈
∈
aA iN a ⎝ h g C , ia j P , ia ⎠
∈
a
对于传感器节点 i 的数据感知率问题,由于 C 是一个单调递增的函数,为获得节点 i 的最少能量消耗,只有
i
当公式(10)相等时,目标函数才可能实现.因此,单个传感器节点 i 的能量消耗最小化问题可定义为
P2: min ∑ a ( T ) + ∑ Cr q a ⎫
a
i i i
∈
aA aA i ⎪
∈ i
⎬ (18)
a
rT ≥ M ⎪
i
s.t. ∑ i
aA ⎭
∈ i
a
a
a
x
其中, r ≥ 0, a∀∈ A .令 x = i i a rT ,q = i a σ i a a i ,q 为当 DCV 停留在锚点 a 处时,传感器节点 i 为获得数据传输机会
i
i
i
a
a
所需支付的能量,σ 为传输单个数据的能量消耗, x 为传感器节点 i 在锚点 a 处的数据传输量.传感器节点 i 的
i
i
能量消耗可分为两部分:(1) 将数据传输至其邻居锚点的消耗;(2) 用于获得数据传输机会的能量要求.传感器
节点 i 的能量消耗可以独立地通过调整其支付能量动态调整.
引入新的拉格朗日乘子ν i 构建问题 P2 的拉格朗日函数,通过库恩-塔克(Karush-Kuhn-Tucker,简称 KKT)条
件解得:
1 ′ C a ⎛ a i ⎞ q +− ν i = ⎫
1
σ i ⎜ a ⎝ σ a ⎟ ⎠ σ a 0⎪
i i ⎪ i ⎬ (19)
⎛ q a ⎞ ⎪
ν ⎜ i i a − ∑ i ⎟ = M 0 ⎪
⎝ ∈ σ i ⎠ aA ⎭
通过对公式(13)进行 KKT 转换,并与公式(19)进行对比,可得出拉格朗日乘子μ i =ν i 且 C′ i a (q a i /σ a i ) σ + a i μ = i .
令 f i 代表传感器节点 i 的能量消耗最小化目标函数,即 P2.对于每个节点 I,若 ˆ a 代表节点 i 具有最小成本的锚点,
i
那么: