引用本文

刘洲洲, 李士宁, 王皓, 张倩昀. 联合弹性碰撞与梯度追踪的WSNs压缩感知重构. 自动化学报, 2020, 46(1): 178-192. doi: 10.16383/j.aas.c170241

LIU Zhou-Zhou, LI Shi-Ning, WANG Hao, ZHANG Qian-Yun. A Compressed Sensing Reconstruction Based on Elastic Collision and Gradient Pursuit Strategy for WSNs. ACTA AUTOMATICA SINICA, 2020, 46(1): 178-192. doi: 10.16383/j.aas.c170241

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c170241

关键词

无线传感器网络，弹性碰撞优化算法，收敛性，压缩感知，稀疏重构算法 

摘要

为提高压缩感知(Compressed sensing, CS)大规模稀疏信号重构精度, 提出了一种联合弹性碰撞优化与改进梯度追踪的WSNs (Wireless sensor networks)压缩感知重构算法.首先, 创新地提出一种全新的智能优化算法---弹性碰撞优化算法(Elastic collision optimization algorithm, ECO), ECO模拟物理碰撞信息交互过程, 利用自身历史最优解和种群最优解指导进化方向, 并且个体以N(0, 1)概率形式散落于种群最优解周围, 在有效提升收敛速度的同时扩展了个体搜索空间, 理论定性分析表明ECO依概率1收敛于全局最优解, 而种群多样性指标分析证明了算法全局寻优能力.其次, 针对贪婪重构算法高维稀疏信号重构效率低、稀疏度事先设定的缺陷, 在设计重构有效性指数的基础上将ECO应用于压缩感知重构算法中, 并引入拟牛顿梯度追踪策略, 从而实现对大规模稀疏度未知数据的准确重构.最后, 利用多维测试函数和WSNs数据采集环境进行仿真, 仿真结果表明, ECO在收敛精度和成功率上具有一定优势, 而且相比于其他重构算法, 高维稀疏信号重构结果明显改善.

文章导读

智能优化算法又称启发式计算技术[1], 其在模拟种群生物学行为或者物质物理属性变化的基础上, 通过迭代计算实现最优化问题的求解.由于具有全局搜索能力以及稳定性好、容易实现等特点[2], 智能优化算法已经被广泛应用于日常生产生活各个领域.

随着智能优化理论研究不断深入, 大量不同类型的智能优化算法被相继提出, 如蚁群算法(Ant colony optimization, ACO)[3]、粒子群算法(Particle swarm optimization, PSO)[2]、混合蛙跳算法(Shuffled frog leaping algorithm, SFLA)[4]、烟花算法(Fireworks algorithm, FA)[5]、模拟退火算法(Simulated annealing, SA)[6]等等.当前实际优化问题日趋复杂, 高维度、多模态[7]和动态性[8]给经典智能优化算法带来了严酷的挑战.研究表明种群样本多样性和局部极值逃避学习能力是影响智能优化算法收敛性能的重要因素, 学者们也围绕扩展算法学习进化搜索空间、不同类型算法混合协同进化等方向展开深入研究: Liang[9]等提出了一种CLPSO (Comprehensive learning PSO)算法, 利用种群历史信息对PSO进化方向进行引导, 以增强算法跳出局部极值能力, 这种借鉴历史信息"回溯"思想具有典型代表意义, 不仅让算法具有了记忆功能, 而且有效改善了算法全局寻优能力; 文献[10]提出了一种改进布谷鸟优化算法, 将模式搜索(Pattern search, PS)引入到算法中, 利用PS快速搜索能力以提高算法收敛效率, 另外, 田瑾提出的量子行为粒子群优化算法[11]、Kang提出的和声粒子群算法[12]等都属于利用特定策略或者特定模型对算法进行引导, 以期达到克服容易陷入局部极值、收敛效率低的缺陷; 文献[13]融合粒子群与模拟退火算法, 提出了一种(Particle swarm optimization-simulated annealing, PSO-SA)协同进化算法, 利用不同算法的互补特性, 取长补短, 并行协同进化, 从而提高了改进算法的鲁棒性和适应性.这些改进算法提高了解决复杂优化问题的能力, 但是仍存在局限性: 1)改进算法往往简单融合不同类型进化策略, 并没有深入分析融合的合理性; 2)大多数改进算法虽然扩展了种群搜索空间, 但是缺少种群样本多样性理论分析支撑. 3)改进算法很大程度上增加了实现难度和计算复杂度, 然而这些牺牲代价却没有得到足够重视. "看似简单的过程往往包含着最朴素的哲理", 本文模拟物体间极短的相互作用过程, 以碰撞前后物理量变化作为学习进化机制, 提出一种全新的智能优化算法—弹性碰撞优化算法(Elastic collision optimization algorithm, ECO), 并从理论角度对算法收敛性和全局寻优能力进行分析.

压缩感知(Compressed sensing, CS)是一种新的信号处理理论[14], 其颠覆了传统Shannon-Nyquist采样定理限制, 具有强大的生命力.稀疏信号重构算法是当前CS研究热点之一, 也相继提出了组合优化、凸优化以及贪婪迭代等不同类型重构算法, 特别是对于信号稀疏度未知下的重构算法, 学者们进行了深入研究:王艳芬等[15]提出了一种稀疏度自适应超宽带信道估计算法, 该算法通过逐步逼近信道稀疏度, 实现稀疏度未知信号的精确重构, 但是逐步逼近方式很大程度地增加了算法运算量; YANG等[16]提出了一种稀疏自适应匹配追踪算法, 通过设置自适应步长逐渐逼近原始信号, 但是步长设置大小对重构精度和重构效率具有重要影响.当前大规模数据处理效率低、重构算法参数难以选择、信号稀疏度事先确定等缺陷仍是亟需解决的问题, 为此本文提出一种联合弹性碰撞优化与改进梯度追踪的WSNs压缩感知重构算法, 主要做了以下几个方面工作:

1) 提出全新弹性碰撞优化算法, 给出基于碰撞信息交换和N概率散落算法的更新机制, 并从理论角度分析算法收敛性和群体样本多样性.

2) 对StOMP贪婪重构算法进行改进, 引入ECO和拟牛顿梯度追踪策略以实现大规模稀疏度未知数据的准确重构.

3) 利用多维测试函数和WSNs数据采集环境进行仿真, 以验证所提算法的有效性.

图 1  极值碰撞示意图

图 2  改进StOMP贪婪重构算法实现

图 3  不同n下最优解均值和平均运行时间变化曲线

对一种全新智能优化算法及其在WSNs稀疏事件检测中的应用进行了研究, 从理论角度对碰撞优化算法收敛性和样本多样性进行了分析, 这对研究智能优化算法具有一定借鉴意义; 从WSNs稀疏事件检测应用研究入手, 针对稀疏度未知、重构精度要求高、传统贪婪算法固有缺陷, 将ECO与压缩感知相结合, 引入了分阶段检测框架和IStOMP重构算法, 最后仿真实验也验证了ECO算法和IStOMP重构算法的有效性.下一步将针对高维病态函数优化和提高重构算法普适性上做进一步研究.