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

2878 Journal of Software 软件学报 Vol.32, No.9, September 2021

⎧ ⎪ fr i ⎪
()⎫∂
a
ˆ a = i argmin ⎨ i a ⎬ = argmin{C′ i a (r T )T Tμ− i λ + i a α + i a e s } (20)
i
⎪ r ∂ i ⎭ ⎪ ⎩
如果对于传感器节点 i 有多个最小成本锚点,可随机选择一个锚点作为最小成本锚点.通过自适应算法 [24]
可以得到:
+
⎧ ⎪ 0, μ < C′ a (0) σ a
a
q = ⎨ i i i (21)
i a a − 1 a a a
⎪ ⎩ σ i (C′ i ) (μ i σ − i ), μ i ≥ C′ i (0) σ + i
a
通过调整 q 的大小,可以改变节点的数据感知率大小,进而达到最小化网络能量消耗地目的.对于节点 i,
i
a
a ∈ A ,a = ˆ a ,可以通过增大 q 的值以达到增加在锚点 a 处的数据传输量的目的,相应地,在其他锚点处传输的
i i i
数据会有所减少,最终使得传感器节点 i 的能量消耗减少;否则,对于节点 i, a ∈ A ,a ≠ ˆ a ,减小 q 的值会导致在最
a
i i i
a
少成本锚点处增大数据传输量.在这里,假设传感器节点 i 的σ 为固定值.
i
通过对偶变换,公式(17)可以转化为
⎛ ⎞
max ∑∑ ∑ f a (λ a α + a e ) + ∑ f a (α a e − λ a ) = ⎟ ∑∑ (λ ∑ a α + a e + α a e − λ a ) f a (22)
⎜
f ⎜ gi i i r ij i t i ⎟ j j r i t i ij
∈
∈
∈
∈
∈
∈
aA iN a ⎝ h g C , ia j P , ia ⎠ aA iN h j P , ia
∈
a
约束条件为公式(12)、公式(13),解决路由调度问题可以从子集为空的传感器节点开始,根据其自身的拉格
朗日乘子初值和次梯度的方法计算该节点的拉格朗日乘子最优值.随后,节点根据物理链路将最优值传至邻居
节点.邻居节点通过获得的乘子最优值进而求出自身的最优拉格朗日乘子值.重复此过程,直到所有节点的最优
乘子值获得为止.通过这一方法,可以得到传感器节点 i 的最佳物理链路传输率其实相当于找出集合:
X = i {( , ) |j a λ a j α + a j r α i a e − t λ i a > 0, j∀ ∈ P ij a , a∀ ∈ A }.
e +
逐个选择传感器节点 i 集合 X i 中最大值所对应的父节点和锚点,并为其赋予最大链路率 f ij a = E i e ,同时更
t
τ a
新节点剩余电池能量.重复此过程,直到集合为空为止.此外,可以利用启发式的分布算法 [31] 解决此类问题.
在计算每个传感器节点的数据感知率和物理链路传输率时,另一个重要因素是拉格朗日乘子的迭代.每个
传感器节点需要更新其拉格朗日乘子,并将更新后的值发送给该节点直接相连的邻居节点,邻居节点进而计算
自身的数据感知率和链路传输率.更新法则如下:
⎡ ⎛ ⎞ ⎤ + ⎫
μ i ( + 1) μ i ( ) η= t t + ⎢ ⎜ i − ⎜ ∑ i r T ⎟ M ⎟ ⎥ ⎪
a
⎢ ⎝ aA ⎠ ⎦ ⎥ ⎣ ⎪
⎪
∈ i
⎡ ⎛ ⎞ ⎤ + ⎪
⎪
λ i a ( + t 1) = λ i a ( ) η ⎢ + t i a + ⎜ ∑ gi a −f ∑ f ij a ⎥ ⎟r ⎬ (23)
⎢ ⎣ ⎜ ⎝ gC , ia j P , ia ⎟ ⎠ ⎥ ⎦ ⎪
∈
∈
⎡ ⎛ ⎤ ⎞ + ⎪
⎪
α i a ( + 1) α t i a ( ) η=⎢ t + ⎜ i a s + ∑ r e gi r + f e t − E i /τ ∑ f e a ⎥ ⎟ ⎪
a
a
ij
⎢ ⎣ ⎝ ⎜ gC , ia j P , ia ⎟ ⎠ ⎥ ⎦ ⎭
⎪
∈
∈
+
其中,t 是迭代次数,η是迭代步长,[⋅] =max{⋅,0}.在本文中,将所有传感器节点的拉格朗日乘子μ i ,λ,α的初值均设
a
为 1.由于 C i a ()⋅ 是严格凸函数,当乘子为唯一确定值时, f 存在唯一最大值.
ij
由于路由调度问题是线性的,使得拉格朗日求出的最优值不能直接应用于原始问题.因此,本文中使用文献
a
a
a
[32]中的方法恢复 f 的原始解.一旦得到的原始解{ f ˆ a } 收敛,此时的 f 和 r 即为优化函数 P1 的最优解.
ij
ij
ij
i
5 实验验证与分析
本节将通过大量的实验来验证所提方案和网络整体策略的高效性.所有实验结果由 MATLAB 计算得到.首
先验证基于最小化网络能量消耗函数所得传感器节点数据感知率的收敛性.其次,通过对比不同分区方案下基
站收集到的数据量,验证分区方案 NP-NSD的高效性;接着,由于 DCV收集锚点数据时的巡游路径长度和网络系