无线传感器网络的自适应预测算法

张源峰，孙海信，颜佳泉，蒯小燕

（1.厦门大学水声通信与海洋信息技术教育部重点实验室，福建 厦门361005；2.闽西职业技术学院电气工程系，福建 龙岩364021）

随着通信及信号处理技术、传感器技术和计算机技术的发展，无线传感器网络（wireless sensor networks，WSN）越来越受到人们的关注.WSN一般包括传感器节点、汇聚点和任务管理节点，它通过在环境中布置多个传感器，协作地感知、采集和处理所覆盖的网络区域的监测对象的信息，并将这些来自不同时间和不同信息源的信息传递到汇聚点，进行多传感器数据信息融合技术处理，最后通过互联网或者卫星将信息送达任务管理节点.用户可通过管理节点对传感器网络进行设置和管理，发布实时监测任务及采集存储监测数据［1］.然而，恰恰因为WSN具有大量传感器节点，可以实时感知和采集环境的变化信息，使其受到能耗、存储空间和计算能力的限制.如何有效地实现WSN中的低能量消耗、低计算复杂度和存储空间的节省，正是WSN亟待解决的难题.

传统的信号获取和处理过程主要包括采样、压缩、传输和解压缩4个部分，其采样过程必须遵循奈奎斯特采样频率，这种方式采样数据量大，先采样后压缩，浪费了大量的传感元、时间和存储空间［2］.相较之下，压缩感知理论针对可稀疏表示的信号，能够将数据采集和数据压缩合二为一，可以用远远少于Nyquist采样定理所需的采样点数恢复出原信号.其中CS重构算法的研究是CS理论的关键环节，CS重构算法的研究对于WSN以及资源受限和大数据的采样系统具有重大的研究意义，它可以有效地减少采样传感器的数目，同时降低每个传感器的能耗、存储空间和计算复杂度.

CS利用了信号的时间或者空间相关性，只研究单个信号的稀疏、压缩和重构问题；WSN是一个分布式多传感器信号采集和数据融合的网络，显然CS理论无法满足其要求.然而分布式压缩感知研究多个信号的联合重构问题，它充分利用了信号内部和信号之间的相关结构，每个独立的传感器信号都能在某一特定的正交稀疏基下稀疏表示，每个传感器通过测量到的信号映射到另一个与稀疏基不相关的基上进行独立编码，然后将少量的投影结果传输到汇聚点，然后通过重构算法重构出每个传感器信号［3］.

本文介绍了CS理论，同时介绍了正交匹配追踪算法［4］和前向预测正交匹配追踪（look ahead orthogonal matching pursuit，LAOMP）算法；针对 LAOMP中的前向参数L只能固定选定，其中前向参数是每次迭代选择的潜力原子的个数，使得计算量非常大，提出了一种自适应前向预测正交匹配追踪（adaptive look ahead orthogonal matching pursuit，ALAOMP）算法，在每次迭代过程中，对L进行自适应选择，并通过仿真实验验证了，在不同信号观测噪声比下，ALAOMP算法的性能优于LAOMP算法.

1 CS理论

对于一个有限长度为N的一维离散信号f，f∈RN，信号f在稀疏基｛ψi｝Ni＝1上是K稀疏的，可以表示为一组标准正交基｛ψi｝Ni＝1的线性组合，则f可以表示为

其中，K为稀疏度，K＜N；s是信号f的加权系数序列，si＝〈f，ψi〉＝ψiTf；ψ＝｛ψi｝iN＝1，ψ 为稀疏基，ψi为列向量，ψ∈RN×N.CS是一个线性测量过程：将K稀疏的的信号f与感知向量组｛φj｝jN＝1做内积运算，产生观测信号yj＝〈f，φj〉；各个yj组成一个M×1的观测向量y，以φjT作为观测矩阵Φ 的行，即将信号f投影到观测矩阵Φ（Φ∈RM×N）上得到观测向量y，线性测量过程表达式为

由于y的维数远远低于f的维数，方程（2）有无穷多个解，即该问题是欠定的，很难重构出原始信号.但是如果系数s中只有K个非零值，同时观测矩阵满足 约 束 等 距 特 性 （res－tricted isometric property，RIP），即对于任意K稀疏度的信号f，存在常量0≤δk＜1，有

理论证明，信号重构可以由测量矩阵y求解最优l0范数得到，当考虑噪声时，CS重构模型可表示为

求解最优l0范数的问题，实际上是一个欠定问题，在多项式上很难求解.因此，相关学者提出了其他的求解方法，如基追踪算法、迭代贪婪追踪算法和最小全变分法等.

为了确定理想的信号f，需要决定Φ中的哪一列（即原子）加入到观测向量y，OMP算法［3］的主要思想是以贪婪的方式选择原子，在每次迭代中，选择Φ中与y剩余部分最相关的列，即选择一个与上次迭代残差内积最大的原子，然后更新原子候选集、估计信号和残差；判断是否满足迭代终止条件，是，则输出估计信号，否，则继续反复迭代［4］.

2 LAOMP和ALAOMP算法

2.1 LAOMP算法

在标准OMP算法中，选择当前迭代的新原子没有考虑到依赖于所选择的原子对所有迭代最终完成时OMP性能的影响，新原子的选择对未来迭代的影响 是 盲 目 的，因 此，Saikat Chatterjee 等［5］提 出LAOMP算法，该算法在OMP算法的基础上加入了前向预测策略，即一个原子的选择是通过评估其对最终性能指标的影响，即所有迭代结束时最小拟合残差.LAOMP算法的主要思想如下：在每次迭代中先选择L个与上次残差内积最大的原子，其中L表示前向参数；然后依次预测这L个原子对最终迭代残差的影响，将L个原子中使得最终残差模值最小的原子加入支撑集，然后更新原子候选集、估计信号和残差.LAOMP算法流程图如图1所示.前向预测策略可以由前向残差（look ahead residual，LAR）子算法［6］完成，具体描述如下：

算法1：LAR子算法

输入：观测矩阵Φ，观测向量y，稀疏度为K，上次迭代原子支撑集I，新选定的原子索引i.

初始化：当前迭代原子支撑集Ik＝Ik∪i，近似系数y，残差，迭代次数

迭代过程：

1）迭代次数更新：k＝k＋1；

2）确定新增原子索引并将其索引加入原子支撑集：

3）更新近似系数及残差：

4）迭代停止判断条件：

其中rk为当前迭代残差，rk－1为前次迭代残差.满足上式，则迭代终止；否则，返回步骤1）继续执行.

为了使用LAR子算法，定义前向预测残差LAR函数如下：设y∈RM，Φ∈RM×N，稀疏度为K，先前迭代的原子支撑集为I，当前迭代的新增原子索引为i，则最终输出残差r∈RM可以用下式表示：

图1 LAOMP算法流程图Fig.1 Flow chart of LAOMP algorithm

2.2 ALAOMP算法

在LAOMP算法中，正是因为前向参数L的引入，及外部L次循环及K次外部迭代和前向预测策略子算法中的内部迭代，使得LAOMP算法计算复杂度及计算量相当的大；同时，LAOMP对于最具潜力的L个原子的选定，其中前向参数L只能在程序初始化中人为地设定固定值，通过仿真实验发现，这L个降序排列的原子中，存在某两个相邻原子衰落大以及其相关性低，固定的前向参数反而成为选择最具潜力原子的缺陷.本文给出了一种ALAOMP算法，提出了一种自适应选择前向参数L的方法，以保证所选择的L个原子是最佳的，从而实现降低算法的计算复杂度.L个原子的选定由自适应前向参数（adaptive look ahead parement，ALAP）子算法完成，具体描述如下：

算法2：ALAP子算法

输入：观测矩阵Φ，观测向量y，上一次迭代残差r1，L＝1；

1）计算出所有原子与残差的内积绝对值，即

2）对product向量进行降序排列，计算相邻原子之间的相对误差，如下式：

relative＿error（i）＝｜val（i）－val（i－1）｜／val（i），其中，val为原子与残差内积绝对值product向量降序排列后的向量；

3）计算相邻原子的相对误差变化率，即

4）满足条件error＿rate≥τ，终止循环，否则执行L＝L＋1；同时设定L的上限T，满足L≥T终止程序.

输出：前向参数L.

自适应前向参数函数定义如下：设y∈RM，Φ∈RM×N，稀疏度为K，上一次迭代残差r1，残差r1∈RM，则ALAP算法函数为：

那么ALAOMP算法可以描述如下：

算法3：ALAOMP算法

输入：观测矩阵Φ，观测向量y，稀疏度K；

定义：n＝［n1，n2，…，nL］t，j＝［j1，j2，…，jl］t；

迭代过程：

1）迭代次数更新，k＝k＋1；自适应找到与ΦtrK－1幅值最大的L个原子的索引j，且j⊄Ik－1，执行ALAP函数：L＝ALAP（y，Φ，r1）；

2）预测这L个原子对最终迭代残差的影响，执行内部循环，循环次数为L，内部循环语句为rr＝LAR（y，Φ，K，Ik－1，jl），nl＝‖rr‖2，其中nl为迭代到原子索引jl时最终残差的范数；

3）支撑集更新：最终残差的范数n中最小元素的索引号为l，选择使得残差最小，

原子索引号为ik＝jl，更新支撑集Ik＝Ik－1∪ik；

5）如果满足‖rk‖2＞‖rk－1‖2或者k＞K，则k＝k－1，退出迭代.

2.3 计算复杂度分析

OMP的计算复杂度为O（MNK），LAOMP的计算复杂度为O（MNK2L），其中O（g）表示算法计算复杂度的阶次，它是衡量算法在运行时间方面的效率.因此我们可以明显地看出，前向参数L的变大会增加算法的计算复杂度.在第i迭代时，L的大小决定了在本次迭代中执行LAR子算法的次数，同时LAR子算法的计算量相当于运行一个稀疏度为（K－i）的OMP算法，因此前向参数L决定了LAOMP算法和ALAOMP算法的计算复杂度.由于LAOMP中前向参数L是固定的，同时ALAOMP的ALAP子算法减少了前向参数L，使得ALAOMP算法的计算复杂度比LAOMP算法低；

3 实验结果及分析

定义信号噪声观测比［7］（signal to measurement noise ratio，SMRN）为：

其中w为观测噪声.

为了验证基于ALAOMP算法的重构性能，在信号加噪的情况下，设计了两组实验：1）在SMRN＝10 dB情况下，对比ALAOMP算法和LAOMP算法的重构性能；2）在SMRN＝20dB情况下，对比ALAOMP算法和LAOMP算法的重构性能.为了衡量算法的重构性能，定义了信号重构信噪比（signal to reconstruction noise ratio，SRNR）和平均支撑势误差（average support cardinality error，ASCE）这两个性能指标［7］.其中，SRNR用于测试信号重构性能，它的定义为：

ASCE主要测试的是支撑集的重构性能，其具体定义如下：

从ASCE定义可知，ASCE值越小表示支撑集的重构准确度越高.

仿真参数设置如下：信号的长度N＝500，稀疏度K＝20，LAOMP算法的前向参数L＝3，ALAOMP算法的前向参数L≤3，τ＝5，仿真次数n＝500.当SMRN＝10dB时，ALAOMP算法和LAOMP算法的信号重构准确度和支撑集的重构准确度如图2所示.当SMRN＝20dB时，ALAOMP算法和LAOMP算法的信号重构准确度和支撑集的重构准确度如图3所示.

图2 SMNR＝10dB时ALAOMP算法和LAOMP算法性能对比Fig.2 Comparison of performance between ALAOMP and LAOMP algorithm when SMNR＝10dB

仿真结果表明，在加入自适应选择前向参数后，在所有迭代中ALAOMP算法前向参数选择总数的平均值明显低于LAOMP，即ALAOMP的计算复杂度低于LAOMP.同时ALAOMP算法的SRNR值始终高于LAOMP算法，其ASCE值始终低于LAOMP算法，即ALAOMP算法的信号重构性能及支撑集性能始终优于LAOMP算法.

4 结 论

本文通过仿真验证了使用前向预测的LAOMP算法信号重构性能及支撑集重构性能明显优于OMP算法.同时验证了，文中提出的ALAOMP算法结合了前向预测策略和自适应选择前向参数的优点，相比只采用前向预测策略的LAOMP算法，能够用相比较低的计算复杂度，获得优于LAOMP算法的信号重构性能及支撑集重构性能.实验证明，这种自适应前向预测正交匹配追踪算法是实用有效的.

［1］Mei H，Sun H，En C，et al.Impulsive noise mitigation and doubly selective channels estimation for underwater acoustic OFDM with compressed sensing［J］.Journal of Convergence Information Technology，2013，8（9）：78－87.

［2］Sun H，Shen W，Wang Z，et al.Joint carrier frequency offset and impulse noise estimation for underwater acoustic OFDM with null subcarriers［C］∥Oceans，2012.Hampton Roads，USA：IEEE，2012：1－4.

［3］Mei H，Haixin S，En C，et al.Joint Interference mitigation with channel estimated in underwater acoustic OFDM system［J］.TELKOMNIKA Indonesian Journal of Electrical Engineering，2013，11（12）：7423－7430.

［4］Tropp J A.Signal recovery from random measurements via orthogonal matching pursuit［J］.IEEE Transactions on Information Theory，2007，53（12）：4655－4666.

［5］Chatterjee S，Sundman D，Skoglund M.Look ahead orthogonal matching pursuit［C］∥Acoustics，Speech and Signal Processing （ICASSP），2011IEEE International Conference on.Prague，Czech Republic：IEEE，2011：4024－4027.

［6］Swamy P B，Ambat S K，Chatterjee S，et al.Reduced look ahead orthogonal matching pursuit［C］∥Communications（NCC），2014Twentieth National Conference on.Kanpur：IEEE，2014：1－6.

［7］Chatterjee S，Sundman D，Vehkapera M，et al.Projectionbased and look－ahead strategies for atom selection［J］.Signal Processing，2012，60（2）：634－647.