无线传感器网络(wireless sensor networks, WSNs)为人类灵活快速地获取各种资源信息, 实时有效的监控目标区域状态提供了可能^[1], 并被广泛应用于环境检测、森林火灾预警、军事国防等领域。然而计算存储能力有限、服务模式单一、资源浪费严重等已成为制约WSNs深度发展的瓶颈问题^[2]。然而, 随着WSNs规模的不断扩大, 需要处理的节点数据呈现爆炸式增长, 这对WSNs通信能力、能耗来说将是极大的挑战。由于大规模WSNs中的监测事件远远小于传感器节点数量, 因此在均衡网络能耗的同时保证可靠稀疏数据采集是大规模WSNs最关键的问题。压缩感知(compressive sensing, CS)理论^[3]、移动Agent(mobile agent, MA)^[4]等技术的不断成熟，有效提高了大规模WSNs数据采集效率, 如何设计更加稳定高效的CS以及MA策略仍是当前WSNs数据采集研究热点。为此学者开展了相关系列研究:李鹏等^[5]提出了一种基于压缩感知和树分解路由优化的数据收集方法, 分为稀疏处理和路径优化2个步骤, 保证了数据收集的高精度, 但是随着网络规模的增大, 路径优化计算呈现爆炸式增长; 文献[6]提出了基于区域化压缩感知的数据收集方法, 将每个区域独立执行压缩感知, 从而避免在数据传输过程形成较大的数据流, 但是测量矩阵设计较为复杂; 文献[7]提出了一种将压缩感知和Pegasis路由协议相结合的数据收集方案, 通过在通信链路中压缩数据实现延长网络生存周期的目的, 但没考虑链路不可靠情况且网络能耗并不一定能够达到最小期望值; WU等^[8]提出了一种将LEACH分簇和压缩感知结合的数据收集算法, 实现了较高效率的网络数据收集, 但该算法没有充分考虑簇内节点数据相关性, 链路鲁棒性较差容易导致节点能耗过快。

但上述研究均未考虑移动节点对稀疏数据采样过程的影响, 同时, 稀疏信号重构算法的性能也直接影响着最后数据收集结果的可信度^[9], 目前大规模数据处理效率低、重构算法参数难以选择、信号稀疏度事先确定等缺陷仍是亟需解决的问题：①改进算法往往简单融合不同类型进化策略, 并没有深入分析融合的合理性; ②大多数优化算法虽然扩展了种群搜索空间, 但是缺少种群样本多样性理论分析支撑；③改进优化算法很大程度上增加了实现难度和计算复杂度, 然而这些牺牲代价却没有得到足够重视。本文模拟物体间极短的相互作用过程, 以碰撞前后物理量变化作为学习进化机制, 提出一种智能优化算法——弹性碰撞优化算法(elastic collision optimization algorithm, ECO)并加以离散化, 同时从理论角度对算法收敛性和全局寻优能力进行分析。

针对上述问题, 本文以大规模传感网稀疏数据收集为应用背景, 提出一种自适应块压缩感知与离散弹性碰撞优化算法的数据采集方案:对涉及的自适应块压缩感知数据采集策略、移动节点数据采集路径规划以及多移动节点协同计算机制进行详细描述, 以达到减少网络数据通信总量、降低网络时延和能耗要求的目的。

1 网络模型

压缩感知理论的提出为信号采集处理带来了全新研究思路, 其利用低维空间少量观测数据就能够实现对高维信号的准确感知。对于N维信号x_N×1, 可以用正交矩阵Ψ_N×N={ψ₁, …, ψ_N}进行表示, 即

(1)

式中, s_N×1为N×1维向量。当s_N×1仅有K(K≪N)个非零系数时, 则s_N×1在Ψ_N×N是稀疏的, 稀疏度为K。通过非相关测量矩阵Φ_M×N将x_N×1投影到低维测量向量y_M×1上, 得到M个测量数据, 即

(2)

式中, A_M×N=Φ_M×NΨ_N×N。当M≪N时, (2)式为欠定方程组, 但如果s_N×1足够稀疏, 且A_M×N满足RIP条件^[10]时, 可以通过求解最小l₀范数稀疏重构出s_N×1, 即

(3)

对于某块传感网区域内大规模部署Q个传感器节点的无线传感器网络W={S_i}(i=1, 2, …, Q), 利用虚拟技术将W划分为V个虚拟簇V={Z_j}(Z_j为第j个虚拟簇, j=1, 2, …, V), 以实现对不同区域的监控。对于虚拟簇Z_j, 根据传感器节点能耗, 在满足网络覆盖要求的情况下, 选择一定节点处于工作状态(取工作节点数为G)。Z_j监控区域内有N个事件源(取K为发生事件的事件源个数), 设f_i表示Z_j内工作节点S_i^j采集到的数据(i=1, 2, …, G), 则传感器数据向量X_G×1=(f₁, f₂, …, f_G)^T; 设s_k为第k(k=1, 2, …, N)个事件源信号强度, 则事件源信号向量s_N×1=[s₁, s₂, …, s_N]^T, 有

(4)

式中, Ψ_G×N为传播矩阵。根据压缩感知理论, 选取M(M < G)个传感器数据就可以得到s_N×1, 因此利用观测矩阵Φ_M×G对X_G×1进行选取, 得到测量向量y_M×1

(5)

通常来说, 同一时刻N个事件源只产生少量事件(K≪N), 即s_N×1是K度稀疏的。相关研究表明, 当采用(4)~(5)式列举的Ψ_G×N和Φ_M×N时, Φ_M×GΨ_G×N能以极大概率满足RIP条件, 因此可以利用CS技术, 只需要少量传感器节点数据, 就可以实现监控目的, 如图 1所示。

采用压缩感知技术很大程度的降低了数据采集量, 但是, 在数据通信阶段对节点进行数据采集仍需消耗一定时间, 从而造成数据时延。另外, 在传感网部署初期, 节点往往是很稠密的, 此时将Z_j动态的划分为C个具有相同半径R_C的块, 根据网络覆盖要求可以推导出 (R为节点通信半径, η为块内最大通信跳数)。当Z_j网络工作节点密度为λ时有

(6)

显然, 每个块具有O=G/C个工作节点, 此时每个块可以等效为一个WSNs。对于Z_j内第i个块(1≤i≤C), 选取位于块中心位置的节点为块中心C_i, 用来汇聚块内被采集的节点数据, 其利用Φ_I×Oⁱ选取块内I个节点进行数据采集(∑I=M), 得到观测信号y_I×1ⁱ=Φ_I×OⁱX_O×1ⁱ。当所有块完成数据采集后, 移动节点按照规划路径汇集所有块中心数据, 得到测量向量y_M×1={y_I×1ⁱ}(i=1, 2, …, C)

(7)

从(7)式可以看出Φ′_M×G为块矩阵, 令Α=Φ′_M×GΨ_G×N, 则A也为块矩阵。由于A中含有大量“0”元素, 因此大大降低了节点数据采集量, 而且研究表明, 对于同一种稀疏信号重构算法, 当采用块观测矩阵时, 稀疏信号恢复速度更快、精度更高。

由于分块个数C越大, 块内通信次数增加; 同样C越小, 块间通信次数增加, 因此需要合理确定C大小以平衡块内和块间通信。

结论1  当网络分块C取下值时, 可以使得块内与块间通信效益最大。

(8)

式中, μ₁∈(0, 1)、μ₂∈(0, 1)分别为块间通信与块内通信的控制系数, 且μ₁+μ₂=1。

证明  确定网络分块C的目的是平衡块内和块间通信能耗, 即有minF=μ₁C+μ₂Γ=μ₁· (Γ为块内通信总跳数)。如图 1a)所示, 块内节点至少需要a跳到达CH_i的节点数G_a=λπ(aR)²=πλa²R², 同理需要至少a-1跳到达C_i的节点数G_a-1=πλ(a-1)²R², 因此恰好需要a跳到达C_i的节点数G′_a为

(9)

因此, 块内节点通信跳数Γ′为

(10)

所有分簇簇内节点通信跳数为

(11)

联立(10)式、(11)式有

(12)

对(12)式求偏导

(13)

(13) 式为一元三次方程, 根据卡尔丹公式法, 该方程有唯一实数解, 即

(14)

结合, 有

(15)

证毕。

从结论1可知, 分块个数C的大小跟网络节点密度息息相关, 这也使得块压缩感知数据采集总量因节点密度改变而改变, 其本质是动态自适应变化过程, 这样更有利于降低网络数据采集量和降低网络能耗。

K度稀疏信号s_N×1满足准确重构的充分非必要条件为对于任意s_N×1和常数δ_K∈(0, 1), 矩阵A有K阶约束等距性

(16)

对于(7)式块压缩感知模型, 观测矩阵A以极大概率满足(16)式RIP条件, 因此对于s_N×1, z_N×1存在(通常K≪N/2)

(17)

联立(16)式、(17)式有

(18)

因此可以得出观测次数M满足(Λ≈0.28)

(19)

对于稀疏信号s_N×1精确重构问题, 目前存在的大多数重构算法需要设定K已知前提, 但是通常情况下这是不现实的, 因为无法预知有多少的事件源会发生事件, 因此为了解决稀疏度未知下信号重构问题, 以min‖s‖_l0为目标优化函数, 采用智能优化算法进行求解。

2 弹性碰撞优化算法(ECO)

学者们通过模拟物种生存进化规律, 提出了一系列智能优化算法, 并被广泛应用于生产生活各个领域^[9]。由于智能优化算法隶属于启发式搜索算法范畴, 早熟收敛、收敛效率低仍是当前智能优化算法需要解决的关键难题。大量研究表明, 有效保持种群样本多样性是提高智能优化算法全局寻优能力的关键因素, 为此本文模拟物体对心完全弹性碰撞、完全非弹性碰撞和非完全弹性碰撞3种弹性碰撞过程, 提出一种智能优化算法:弹性碰撞优化算法^[11], 关于ECO算法文献[10]已有详细介绍, 此处不再赘述。

大规模传感网稀疏数据采集主要涉及自适应块压缩感知、多移动节点协同计算和移动节点数据采集路径规划。其中, 多移动节点协同计算属于连续优化问题, 可以直接采用ECO对约束处理后的适应度值函数进行求解, 从而得到最佳多移动节点间数据协同处理方案, 而对于其他2个问题则属于离散优化问题, 本文提出离散弹性碰撞优化算法(discrete elastic collision optimization algorithm, DECO), DECO内每个粒子X_i=[x_i1, x_i2, …, x_in]代表问题的一个解。对于稀疏信号重构问题, X_i等效为待重构信号s_N×1, 每维元素取值为1或者为0, 而且取值为1的维度数恰好等于信号稀疏度K; 对于M_m移动路径规划问题, X_i维度为网络分块数C, 且每个维度取值与块中心集合{C_i^m}_i=1:C相互对应, 即X_i-{1, 2, …, C}=Ø。无论是稀疏信号重构还是移动路径规划, 可以发现, 2个不同粒子通过一系列编码位调整可以实现相互转化, 因此结合这个特点给出DECO更新策略。

对于粒子X_i=[x_i1, …, x_in], 定义粒子编码对调操作为选取X_i内第a, b维编码进行对调; 对于2个不同粒子X_i, X_j, 定义粒子转化操作X_i↔X_j为一系列编码对调操作, 即

(20)

式中, V_{i, j}表示X_i↔X_j包含编码对调操作的个数。

3 移动稀疏数据收集

图 1b)所示由U个可移动Sink{S₁, S₂, …, S_U}组成, 相互之间可以直连通信。将Sink间虚拟通信网络等效为G=(V, E), 其中E={e_{i, j}}(i, j=1, 2, …, U且i≠j)为边集, e_{i, j}为S_i和S_j之间通信时延, V={S₁, S₂, …, S_U}为顶点集。数据采集任务执行前, 根据Sink物理位置等信息对e_{i, j}进行更新:

1) for i=1:U

2)     for j=i:U

3)         refresh e_{i, j} according to the location of S_i and S_j

4)         j=j+1

5)     end for

6)     i=i+1

7) end for

当节点间通信时延完成更新后, 节点将采集到的数据分配到其他节点, 协同完成数据处理传输任务。WSNs采集数据可能来源于任一S_i, 不失一般性, 以S₁数据采集为例进行分析:定义S₁数据处理任务总量为H, 分配到节点S_i的任务量为h_i(0≤h_i≤H), 节点S_i任务处理速度为v_i、任务处理总时间为t_i, 则移动节点协同计算总时间t(H)为

(21)

从(21)式可以看出, 合理确定h=(h₁, h₂, …, h_U)^T可以使得t(H)取最小值, 此时移动节点协同计算问题转化为约束优化问题

(22)

式中, I为h搜索空间, 即

(23)

智能优化技术是求解目标优化问题行之有效的方法, 但是对于约束优化问题, 粒子目标函数值不能简单等效为粒子适应度值, 因此需要对粒子目标函数值进行约束处理。对于(23)式最小化约束优化问题, 对种群内粒子进行适应度值约束处理后, 在满足约束条件的同时能够选择适应度优秀的个体继续进化, 从而提高了算法求解约束优化问题效率和求解精度^[11-12]。

4 实验仿真

利用NS3平台模拟大规模无线传感器网络, 在10 km×10 km区域内部署Q=2 000个传感器节点, 传感器节点位置信息和性能指标参数已知; 通信速率250 kb/s, 发送功率1 mW, 路由协议选取经典的LEACH协议, MAC协议采用IEEE802.15.4, 在设定时间内连续对网络进行数据采集; 利用Matlab实验仿真平台模拟多移动节点协同计算和移动节点数据采集路径规划过程, 有U=20个移动节点, 每个移动节点初始位置信息已知, 且具有相同的物理指标参数, 取移动节点数据处理速度v_i=1.5 GHz, e_{i, j}在0.08~0.12xs范围内随机生成。采用实验法给出弹性碰撞优化算法参数设置:P=300, ε=0.35, ξ=0.15, β=0.35, T_max=500, r_min, r_max根据具体优化问题设定取值。选取文献[13]提出的DGSP数据采集算法和经典的CDG数据采集算法进行对比试验, 实验过程设定3种方案采用固定节点汇集数据的模式, 在这里使用一阶无线模型进行网络能耗分析, 即将m个比特数据传送至距离为d的节点或基站处的发送和接收能耗分别定义如下

(24)

(25)

公式中E_trans和E_recv分别表示节点发送和接收能耗。E_Tx-amp为信道传输能耗。E_elec为发送单个字节时的传感器节点能耗, 通常取E_elec=50 nJ/bit, ε=100 pJ/(b·m^-2)。图 2给出了不同重构误差要求下测量节点数M和网络能耗对比结果, 具体实验参数见表 1。

从图 2可以看出, 随着系统对重构误差要求的不断降低, 本文提出的自适应分块压缩感知方案和DGSP所需要的测量节点数M不断降低, 并且本文方案所需M要小于DGSP, 而CDG算法仍需要采集所有工作节点数据, 这表明, 在满足重构精度的前提下, 本文算法只需要采集少量工作节点数据, 就可以实现准确监测, 从而有效降低了网络数据通信量, 相比于其他2种方案, 数据采集量降低了约20%。对于网络能耗, 由于CDG需要多次重复采集数据以提高重构精度, 因此随着系统对重构误差要求不断降低, 网络能耗也随之下降, 但是仍远远高于本文和DGSP。对于相同系统重构误差下, 本文方案能耗要求小于DGSP, 特别的, 即使本文和DGSP在相同测量节点数M下, 本文方案能耗仍要小于DGSP, 上述实验结果表明, 自适应块压缩感知数据采集机制能够有效降低数据采集量, 而且网络节点能耗更加均衡, 网络生存周期更长。

不失一般性, 假设只有1个移动节点数据需要进行负载均衡分配, 为了分析ECO求解多移动节点协同计算问题的有效性, 分别与Greedy-LB(贪婪负载均衡算法)、WRR(加权轮转法)和文献[14]提出的CPSO-LB 3种负载均衡算法进行对比分析, 评价指标设定为数据协同计算时延, 其具体含义为数据进行负载均衡分配时间, 图 3给出了3种负载均衡算法时延对比结果, 图 4给出了ECO算法与遗传算法(GA)^[9]、量子粒子群优化算法(QPSO)^[15]目标函数收敛曲线对比结果, 图 5给出了移动节点数U对数据协同计算时延的影响。

从图 3可以看出, 随着任务处理量不断增加, 4重算法数据协同计算时延都在增加, 但是ECO要好于其他3种算法, 特别的当数据处理量较大(20 Gb)时, ECO数据协同计算时延优势更加明显, 约降低了50.1~77.6%。从图 4可以看出, ECO算法在处理目标优化问题时, 收敛速度更快、精度更高, 只需要迭代204次就可以找到全局最优解, 要快于QPSO和GA算法。从图 5可以看出, 当数据处理量较小时, 可移动节点数对数据协同计算时延影响不大, 但是当数据处理量逐渐增大时, 可移动节点数越多, 数据协同计算时延越小。上述实验表明, 对于较大数据处理任务, ECO能够给出更加优秀的负载均衡分配方案, 而且增加可移动节点数能够有效。可以看出, 移动节点以及自适应块压缩感知的引入能够大大降低网络能耗, 这是因为采用移动节点进行数据采集, 块中心节点之间无需进行数据通信, 而且路径规划以网络节点能耗均衡度为优化目标, 从而有效降低网络能耗, 延长网络生存时间。

5 结论

对大规模无线传感器网络数据采集问题进行了研究, 提出了一种基于自适应块压缩感知与离散弹性碰撞优化算法的传感网移动数据采集方案, 该方案以解决传感网大规模数据处理网络流量大、任务时延高、网络能耗不均衡等问题为目的, 设计了自适应块压缩感知、多移动节点数据采集路径规划、弹性碰撞优化算法关键技术。最后仿真实验也验证了本文传感网移动数据采集方案的有效性和突出优势。