基于Jacobi ADMM的传感网分布式压缩感知数据重构算法

李国瑞 孟 婕 彭三城 王 聪

1(东北大学计算机科学与工程学院 沈阳 110819)2(广东外语外贸大学语言工程与计算实验室 广州 510006)

无线传感器网络通常由部署在监测区域的若干无线传感器节点构成，每个传感器节点通过感知环境信息，并将其处理后以无线多跳的方式传输至Sink节点[1].无线传感器节点通常部署在无人值守的野外区域或复杂的工业控制现场，更换电池极为不便.同时，无线传感器节点的计算、存储和能量等各项资源极为有限，因此，将传感器节点采集到的监测数据压缩后再进行传输可有效地延长无线传感器网络的存活周期.目前，无线传感器网络中的数据压缩与重构技术已成为该领域研究中的核心问题之一[2-3].

时空关联分析预测[4]与分布式压缩编码[5]是传统无线传感器网络中采用的2类数据压缩技术，但两者均需在节点中执行复杂的运算，同时还需在网络中传输大量的同步参数.因此，存在明显的弊端[6].近年来，压缩感知(compressed sensing， CS)理论作为信号处理领域中一个备受关注的研究热点，以远低于Nyquist采样定理规定的方式压缩数据，并通过求解优化问题实现稀疏或可压缩数据的精确重构，从而为传感网中的数据压缩与重构研究提供了一个新的方向[7].

经典的压缩感知理论仅支持单个信号的压缩与重构，然而在大规模监测网络中同一个区域内的多个信号之间存在一定的相关性[8].因此，Baron等人[9]在压缩感知理论的基础上进行了扩充，把对单个信号的压缩采样扩展到了对信号群的压缩采样，提出了分布式压缩感知(distributed compressed sensing， DCS)理论.该理论包含3种典型的联合稀疏模型(joint sparse model， JSM)，与经典的压缩感知理论相比，由于其充分发掘了信号的内相关性和互相关性，可以有效地节约信号观察数量，并提高信号的重构精度.

目前，分布式压缩感知重构算法主要包括集中式重构和分布式重构2类算法.其中，集中式重构算法的研究较为成熟，典型的算法包括同步正交匹配追踪(simultaneous orthogonal matching pursuit, SOMP)算法[10]、同步子空间追踪(simultaneous subspace pursuit, SSP)算法[11]和同步压缩采样匹配追踪(simultaneous compressive sampling matching pursuit, SCoSaMP)算法[12]等.然而，由于集中式重构算法需要将各个监测节点的感知数据传输至统一的数据中心进行集中式重构，不但对网络的带宽、延时和节点的能耗要求较高，而且各级监测/控制节点不能直接获取重构结果.因此，无法满足无线传感器网络的实际应用需求.

分布式重构算法采用分布式计算模式避免了上述问题，通过在部分簇头节点之间交换公共信息，并以迭代的方式更新个体信息，从而实现信号群的高精度压缩数据重构.Li等人[13]通过改进集中式的压缩采样匹配追踪算法和子空间追踪算法，提出了分布式协同子空间追踪(decentralized and collabora-tive subspace pursuit， DCSP)算法，并进行了详细的理论分析和验证.Xu等人[14]基于交替方向乘子法迭代求解信号群中的公共部分和个体部分，从而实现了分布式的压缩数据重构.然而，该方案在簇头节点数量大于等于3时无法确保迭代重构的收敛性，还具有一定的局限性.

本文针对无线传感器网络的分布式数据收集应用场景，采用分布式压缩感知理论中的JSM-1模型，通过在优化问题的目标函数中增加近似项以确保分布式压缩数据重构的收敛性，从而设计了一种基于Jacobi ADMM的分布式压缩数据重构算法.该算法通过在簇头节点间迭代交换公共信息以提取相关感知数据的公共部分，并在各个簇头节点内部更新各自的独立部分，从而实现无线传感网中相关感知数据的分布式压缩重构.实验结果表明，与现有其他重构算法相比，本文所提出的算法具有更高的数据重构精度.

1 研究背景

1.1 分布式压缩感知理论

y=Φf+e,

(1)

y=Ax+e，

(2)

(3)

随后再利用变化基Ψ将x还原至原始空间得到，其中ε>0为重构误差.由于式(3)为NP难问题[16]，通常将其松弛为l1最小化问题进行求解：

(4)

xi=zc,i+zi.

(5)

由于公共部分为所有节点所共有，即zc,1=zc,2=…=zc,n，因此可将该式表示为

(6)

令

则在分布式压缩感知中l1最小化问题(即式(4))可表示成：

(7)

1.2 ADMM算法

ADMM算法主要用于求解多变量优化问题，目前已被广泛应用于大规模分布式网络系统的优化计算领域[17].ADMM算法解决问题的一般形式为

minf(x)+g(z),
s.t.Ax+Bz=d，

(8)

(9)

其中，ρ为惩罚参数，u为拉格朗日乘子.

2 系统模型

Fig.1 The network system model图1 网络系统模型

本文提出的分布式数据重构算法适用于层次结构的无线传感器网络，其系统模型如图1所示：

整个无线传感器网络由大量簇成员节点和簇头节点构成.簇成员节点在采集到感知数据后利用相应的测量矩阵进行投影压缩，并将压缩后的数据传输至各自的簇头节点[18].簇头节点汇集本簇内的压缩数据后运行本文所提出的分布式压缩数据重构算法，从而以分布式方式在无线传感器网络内实现压缩数据的重构操作.

3 基于分布式压缩感知的数据重构算法

在无线传感器网络中，为求解分布式压缩数据重构问题(即式(7))，首先构造增广拉格朗日函数：

(10)

(11)

(12)

α(k+1)=α(k)+νγ(ZcB)，

(13)

其中，ν为惩罚参数.通过求解子问题(即式(11)和式(12))即可在重构出无线传感器网络中的感知数据.

算法1.基于Jacobi ADMM的分布式压缩数据重构算法.

输入：感知矩阵Ai、测量信号yi；

输出：稀疏信号xi.

① 初始化拉格朗日乘子α，惩罚参数μ，γ，ν，公共部分zc,i和个体部分zi，内层迭代次数阈值kth和外层迭代次数阈值lth，残差阈值r；

③ whilek

⑦ 根据式(13)更新α；

⑧k=k+1；

⑨ end while

⑩ 通过求解子问题式(12)更新独立部分zi；

4 实验结果与分析

为了验证本文所提出的算法在无线传感器网络中的数据重构性能，本节分别利用合成数据集和真实数据集进行实验验证.其中，合成数据集由Matlab软件仿真合成，真实数据集选用了黑河流域中游生态水文数据集[22]和City Pulse空气污染物数据集[23].在衡量算法性能时，使用相对均方误差(relative mean square error， RMSE)进行度量，用τ表示，其定义为

(14)

1) 分布式重构算法[14].该算法属于分布式数据重构算法，通过将数据分解成公共部分和个体部分，利用ADMM算法进行迭代重构.

2) 分布式贝叶斯算法[24].该算法属于分布式数据重构算法，通过将数据分解成公共部分和个体部分，利用变分贝叶斯推断进行迭代重构.

3) SSP算法[11].该算法属于集中式数据重构算法，利用相同的稀疏基，通过改进子空间追踪贪婪算法进行迭代重构.

4) SCoSaMP算法[12].该算法属于集中式数据重构算法，利用相同的稀疏基，通过改进压缩采样匹配追踪贪婪算法进行迭代重构.

Fig.2 Influence of m on the data reconstruction accuracy图2 观测信号长度m对数据重构性能的影响

4.1 合成数据实验

在生成合成数据集时，首先随机生成m×n的高斯矩阵作为测量矩阵Ai，然后从中随机挑选k个小于n的索引并随机生成稀疏信号xi，最后利用投影运算yi=Aixi+ei生成测量信号yi，其中ei为高斯随机噪声.

图2展示了在采样率m/n=40%、稀疏度k=0.05n的条件下，本文算法与其余4种算法的数据重构性能比较.从图2可以看出，本文算法具有最高的数据重构精度.同时，所有压缩数据重构算法的重构误差都随着观测信号长度m的增加而降低，并逐渐趋于稳定.另外，所有将数据分解成公共部分和个体部分的分布式算法在数据重构精度方面均优于基于贪婪思想的集中式算法.

图3展示了稀疏信号群中个体部分数量对5种数据重构算法的数据重构精度的影响.实验的参数为m=96，n=240，k=15.从图3可以看出，本文算法依然具有最高的数据重构精度.同时，所有压缩数据重构算法的重构误差都随着个体部分数量的增加而降低.显然，信号群中的信号越相似，重构算法重构时越容易，因此重构精度也就越高.另外，从图3还可以看出，信号群中个体部分数量对分布式算法的影响较大，而对基于贪婪思想的集中式算法影响较小.

Fig.3 Influence of number of innovation components on the data reconstruction accuracy图3 个体部分数量对数据重构性能的影响

表1展示了5种压缩数据重构算法在不同簇头节点数量N和观测信号长度m条件下的相对均分误差.从表1可以看出，本文算法具有最高的数据重构精度.同时，所有算法的数据重构误差都随着簇头节点数量N和观测信号长度m的增加而降低.但是，簇头节点数量N的变化对数据重构误差的影响不显著.

图4和图5分别展示了本文算法在与图3相同的实验参数条件下稀疏度k和通信簇头数量c对数据重构精度的影响.从图4和图5可以看出，本文算法的数据重构误差随着稀疏度k的增加而逐渐升高，随着通信簇头数量c的增加而逐渐降低.显然，信号的稀疏度越高，数据重构算法的重构难度越大，因此本文算法的数据重构精度也就相应越低.同时，互相通信的簇头节点越多，对信号群中公共部分的计算越精确，因此本文算法的数据重构精度也就越高.

Table 1 Influence of N and m on the Data Reconstruction Accuracy表1 簇头节点数N与观测信号长度m对数据重构精度的影响

Fig.4 Influence of k on the data reconstruction accuracy图4 稀疏度k对数据重构性能的影响

Fig.5 Influence of c on the data reconstruction accuracy图5 通信簇头数量c对数据重构性能的影响

4.2 真实数据实验

在真实数据集实验中，首先基于黑河流域中游生态水文数据集对比本文算法与其余4种数据重构算法的数据重构性能.实验中使用了离散小波变换基对原始数据进行稀疏表示，实验参数为n=128，μ=16，γ=0.5，N=35.

图6展示了5种算法在该数据集上的数据重构误差.从图6可以看出，本文算法具有最高的数据重构精度.同时，所有压缩数据重构算法的重构误差都随着采样率的增加而降低.显然，采样率越高，数据重构算法的重构难度越低，因此数据重构的误差也就相应越低.

Fig.6 Data reconstruction accuracy of the ecological hydrological dataset in the middle reaches of the Heihe river图6 黑河流域中游生态水文数据集的数据重构精度

图7展示了所有压缩数据重构算法在City Pulse空气污染物数据集上的数据重构误差，其中选用了NO2浓度数据，除簇头节点数量N取值修改为25外其余实验参数与图6保持一致.基于该数据集的实验结论与基于黑河流域中游生态水文数据集的结论一致，本文算法依然展现出最高的数据重构性能.

Fig.7 Data reconstruction accuracy of the City Pulse air pollutant dataset图7 City Pulse空气污染物数据集的数据重构精度

5 结束语

本文提出了一种适用于无线传感器网络的分布式压缩数据重构算法.该算法采用分布式压缩感知理论中的JSM-1模型，通过将信号分解为公共部分和个体部分，并在交替方向乘子法中引入近似项求解，从而实现无线传感器网络的分布式数据收集操作.实验过程中分别使用合成数据集和真实数据集进行验证，结果表明，本文所提出的算法在数据重构精度方面优于现有的分布式压缩数据重构算法.在未来的工作中，将重点考虑如何引入边缘计算技术以实现大规模物联网中的分布式压缩数据重构.