基于不平衡扩展模型的火灾信息分布式压缩感知

庄哲民 吴力科 路小波

(1汕头大学电子系，汕头 515063)

(2东南大学自动化学院，南京 210096)

基于不平衡扩展模型的火灾信息分布式压缩感知

庄哲民1吴力科1路小波2

(1汕头大学电子系，汕头 515063)

(2东南大学自动化学院，南京 210096)

针对无线传感网络数据传输与计算的不均衡而导致部分节点能耗大的问题，首先结合图论中二部图思想，将不平衡扩展模型应用在分布式压缩感知上，并设计出一种与该架构相对应的分布式算法.该算法通过一个列稀疏度确定的稀疏随机二值矩阵决定节点之间是否实现数据传输，从而将传输和计算任务平均分散在各个节点，并利用二阶锥形规划法对融合中心的数据进行重构.最后，在火灾场中利用不平衡扩展模型的分布式压缩感知网络进行仿真实验，并对算法的优越性和网络的节能性作出详细分析.在仿真过程中，通过分析均方误差和信噪比证明所提出的模型不仅在降低节点能耗上有较好的效果，而且在有噪声环境中可以很好地保证信号的重构性能.

无线传感网络;分布式压缩感知;不平衡扩展模型;稀疏测量矩阵

大规模无线传感网络中传感器节点的能量和带宽均有限，因此，在满足服务质量的前提下降低网络开销已成为急需解决的问题.近年来提出的压缩感知理论要求数据在某个转换域上只要满足一定的稀疏度就可对数据有效压缩，而对于大规模传感网络，节点间数据一般具有空间相关性，这个特性使得该数据在某个转换域上满足稀疏度要求，因此可把压缩感知理论应用于分布式传感网络中，从而降低无线传感网络的开销.

目前，虽然分布式压缩感知的研究才刚刚开始，但是利用分布式压缩感知的特点增加信号的可压缩性，降低信号的重构误差已是学者们关注的问题.文献［1］从分布式数据的空间相关性出发，通过调整传感器的节点位置增加信号的可压缩性，减小信号的恢复误差，从而增加无线传感网络中数据传送的效率;文献［2］利用分布式数据的空间相关性建立一个联合稀疏模型，该模型不仅减少传感网络中融合中心的数据量，同时分析了重构误差和压缩比之间的关系.文献［1－2］利用信号样本的空间相关性，虽然增加信号可压缩性的同时减小了信号的重构误差，但并未考虑缓解局部节点能耗大的问题.文献［3］利用多跳技术将测量数据按照最短路径的方式依次在节点间进行传输，在减少网络总能耗的前提下使各个节点平均分担传输任务，但由于其选择稠密测量矩阵，使得单个节点传输的数据量依然很大.文献［4］选择多值稀疏测量矩阵减少节点间的通信量，但由于稀疏测量矩阵的多值性，导致节点需要额外的运算，而且稀疏随机映射对分布式数据有特殊要求，因为分布式数据稀疏度过大会引起信息丢失.由以上分析可知，文献［3－4］虽然在一定程度上能缓解节点能耗大的问题，但仍存在着诸多不足.

针对上述问题，1996年 Sipser等［5］提出用扩展模型建立线性错误校正编码簇减少解码时间，这类编码称为低密度奇偶校验码(low-density paritycheck codes);Berinde等［6］把扩展编码应用到压缩感知领域中，从而减小编码的复杂度.但这些理论模型只限于单个信号的压缩感知，并没有深入地对分布式信号的处理进行研究.本文将不平衡扩展模型产生(0，1)二值稀疏测量矩阵的原理结构应用于分布式压缩感知中，提出一种基于不平衡扩展模型［7］的分布式压缩感知新的理论模型.不平衡扩展模型是一个简单的二部图，它可以利用该二部图的2个互不相交顶点子集来确定测量矩阵，不同子集中的顶点关联与否决定测量矩阵元素是否为1，从而构建一个只包含(0，1)的二值稀疏矩阵，这里的2个不同顶点子集分别为数据节点和编码节点，而连接不同子集顶点间的边代表数据传输链路.由于该二值矩阵的稀疏化程度很高，并且只有当测量矩阵中的元素为1时才对数据节点所采集到的数据进行传输，因此该方案既大量地减小了数据节点传输到编码节点的数据量，也减少了由于使用其他测量矩阵所造成数据预处理过程中额外的数乘运算，最终减少了数据节点的计算负荷.

1 压缩感知理论

在压缩感知中，一个最基本的问题是如何构造高效的测量矩阵，根据y=φx可知信号重建的实质是利用M维测量信号y和测量矩阵φ，然后采用一定的算法重建出N(N＞M)维信号的过程.因此，正确构建测量矩阵在获取测量向量和重建信号的过程中起着重要作用.以下将简单讲述测量矩阵的相关知识:

1)随机矩阵.目前应用在压缩感知［7］或分布式压缩感知的测量矩阵主要是稠密的随机矩阵，典型的稠密测量矩阵φ包括有高斯(Gaussian)随机分布测量矩阵和伯努利(Bernoulli)随机分布测量矩阵.由文献［5］可知，稠密随机测量矩阵仅需要O(Klog(N/K))个测量值就能保证重构信号在性能上逼近压缩信号的最优值.但是由于稠密矩阵元素的稠密性，应用到分布式压缩感知中会存在以下问题:①由于传感器节点数目多，导致数据测量的计算量较大;② 节点间的数据传输量大;③ 使用线性规划方法进行解码的计算复杂度达到O(N3).考虑到稠密测量矩阵的这些缺点，本文采用稀疏的测量矩阵代替稠密的测量矩阵，在保证重构性能的前提下减少数据测量和压缩的计算量及数据传输量.稀疏测量矩阵的基本构造方式如下:首先生成一个零元素的矩阵φ∈0M×N，M＜N，在矩阵φ的每一个列向量中，随机选取d个位置元素，然后对所选取位置的值赋1.

2)RIP特性.测量矩阵φ∈RM×N和向量集合T∈{1，2，…，N}，若集合 T 中非零元素个数小于或等于稀疏度，则矩阵φT为测量矩阵φ由集合T中元素所指示的列向量构成大小为的子矩阵，如果存在常数 δk∈(0，1)使不等式成立，就称矩阵φ具有K项RIP性质.RIP［8］给出了存在确定解的充要条件，即要想信号完全重构，必须保证观测矩阵不把2个不同的K项稀疏信号映射到同一个采样集合中，这就要求从观测矩阵中抽取的每M个列向量构成的矩阵是非奇异的.一个RIP-p矩阵等同于不平衡网络在分布式压缩感知中的邻接矩阵，因此，本文中需要解决的一个重要问题是使构建的测量矩阵满足RIP的理论特性.

3)测量数.在压缩感知中，测量数和信号的稀疏度有密切的关系.例如高斯随机测量矩阵需要的测量数为M≥cKlog(N/K)，贝努利随机测量矩阵测量数为M≈2Kln(N)，部分正交测量矩阵测量数为M≥cK(log(N))6等.并且，测量数还与计算的复杂度、重构的精度紧密相关，例如先构建非自适应线性测量矩阵，再利用链追踪算法恢复信号，需要的测量数为O(Klog2N)，相应算法复杂度为O(Klog2Nlog2K)［6］;或者先构建范德蒙德测量矩阵，再利用线性规划算法恢复信号，需要2K个测量值来恢复稀疏度为k的信号［5］，相应的算法复杂度为O(K2).由上可知，测量数的控制贯穿于压缩感知理论研究的整个过程，并且直接影响着无线传感网络的能耗.

2 基于不平衡扩展模型的分布式压缩感知

2.1 分布式压缩感知的网络架构

不平衡扩展模型［5，9－10］是一种特殊的二部图［11］，它广泛应用于理论分析和实际问题的解决中，特别是在节点间的通信、降低编码错误率和减小计算复杂度方面.本文将不平衡扩展模型应用到分布式压缩感知中，设计基于不平衡扩展器的分布式传感网络模型，进一步讨论计算复杂度、误差和能耗等问题.

不平衡扩展模型包含顶点集和边集，顶点集又可分为2个互不相交的子集，并且每条边的2个顶点分属不同的子集.定义一个(k，ε)不平衡扩展模型G=(A，B，E)，顶点子集A称为数据节点集合，顶点子集B称为编码节点集合，边集E是数据节点向编码节点传输数据的链路;其中，数据节点数编码节点数，每个数据节点的度为d;设集合A的任意节点子集为使得数据节点子集的邻域满足，这里的ε是扩展常数.不平衡扩展模型是在m＜n的基础上提出的，且m越小，不平衡的程度越大，信号恢复的难度也相应加大，因此，需要严格控制数据节点的度d和编码节点数m.文献［12］提出在k，ε，n＞0 时，存在普通常数 θ0＞0，使得数据节点的度满足不等式:

顶点子集B的编码节点数m满足不等式:

另外，E可以用一个测量矩阵φ∈Rm×n(m≪n)表示:

式中，i=1，2，…，m;j=1，2，…，n.

如果数据节点采集到的数据x∈Rn在某个转换域内是k项稀疏，稀疏系数为s，可得到［14］

假使测量矩阵 φ∈Rm×n(m＜n)是由(3k，ε)不平衡扩展模型产生的，s1∈Rn是k项稀疏信号，s2∈Rn是2k项稀疏信号，φs1=φs2.存在信号z，满足

那么z∈Rn是3k项稀疏信号.由式(4)得到可以推出s1=s2，‖z‖1=0.

由上可得(3k，ε)不平衡扩展模型产生的邻接矩阵不存在3k项稀疏的零向量.即对于任意k项稀疏信号s1∈Rn，通过优化算法求出y=φs1的唯一解.

2.2 分布式算法

假设无线传感网络数据节点数为n，编码节点数为m，不平衡扩展模型产生的稀疏测量矩阵φ∈Rn×m.在本文算法中，令第j个传感器本地产生的随机测量矩阵元素和传输数据分别为φij和xj，从而每个编码节点计算和存储的数据相应为.分布式算法流程如图1所示，具体的步骤如下:

图1 分布式算法流程

①数据节点j在本地产生稀疏度为k的随机二值向量{φ1j，φ2j，…，φmj}.当 φij=1 时，数据节点j把采集的数据xj传送到编码节点i，编码节点i保存xj;当φij=0时，数据节点不做任何操作，直至完成所有的j(1≤j≤n)操作.

②当编码节点对接收到的所有数据值进行累加求和后，若融合节点对编码发送请求，则编码节点发送数据.

本文中设定数据节点的度d=2，即测量矩阵φ中每一列的非零个数为2，因此，数据节点j本地生成列向量{φ1j，φ2j，…，φmj}的稀疏度为k(k=2m).根据重构误差需要适当调整编码节点数，但由于数据节点产生稀疏向量的稀疏度k是确定的，因此增加编码节点数并不影响数据节点与编码节点之间的通信量.但假设数据节点j本地产生的是高斯列向量{φ1j，φ2j，…，φmj}，则需要传送m次数据，当增加编码节点的个数，节点间的通信量也随着增加.从上述分析可得:①无线传感网络的传输任务分散在各个数据节点上，避免了使用多跳路由技术引起的距离融合中心近局部节点失效的问题;②由于不平衡扩展模型将输入节点分为数据节点与编码节点，分别完成编码与存储步骤，将传输和计算任务平均分散在各个节点，从而极大地提高了输入节点的工作效率，避免了常规方法节点编码过程中部分节点工作的不平衡问题.

3 融合节点中数据的重构算法

对于二维信号x∈Rn×n，定义［13－15］

则x每一点离散梯度的幅值和为

然后可以通过搜索最小求解x，即

式(9)可重写为

定义不等式函数，用标准的对数障碍法将式(10)转化成一系列线性约束函数，即

其中，τl＞ τl－1，随着 τl增大，式(11)的解xl逼近式(10)的解x*.具体解决步骤为:

① 输入可行的初始点x0，t0，偏差η，参数μ=10，初始值 τ1，l=1.

② 再利用① 求解的xl－1作为初始点，采用全变量牛顿法解式(11)，得到xl，其中l为已迭代的次数.

③ 如果n/τl＜η，结束程序并输出xl.否则设置 τl+1= μτl，l=l+1，重复②.

④ 如果迭代次数，则跳出循环并输出xl.

4 实验仿真和分析

为验证基于不平衡扩展模型的分布式压缩感知网络的可行性，本文设定在开放的无限环境中，存在水平往右风向，构建一个从初始时刻以一定扩散系数向四周散发烟气的火源点，在32 m×32 m的平面中构建基于不平衡扩展模型的无线传感网络，整个平面均匀分布着n=1 024个气体传感器节点.为了能够证明不平衡扩展模型应用在分布式压缩感知上，可以提高计算效率和降低网络系统的能耗，首先，将对无线传感网络进行能耗分析，在此基础上，通过实验比较重构信号的均方误差和信噪比，证明不平衡扩展网络模型不仅可以节省网络能耗，而且较好地保证了信号的重构性能.

4.1 分布式传感网络能耗分析

在无线传感器网络中，由于传感器节点需要电池供电，因此降低节点能耗成为组建无线传感网络优先考虑的因素.本文构建的基于不平衡模型的分布式压缩感知正是针对无线传感网络节点能耗大提出的，而传感器节点耗电的模块有传感模块、处理器模块和无线通信模块.

1)处理器模块能耗.常用的高斯随机测量向量中的元素值需要与数据值做相乘运算，再将得到的结果进行传输，因此每个数据节点都需要进行相乘运算并传输数据;但本文构建的网络模型的每个传感节点只需检测产生的稀疏测量向量元素是否为1，从而决定是否传输数据;比较两者，本文构建的网络模型最终通过减少处理器模块的计算量来实现运算能耗的降低.

2)无线通信模块.传感器节点的绝大部分能量消耗在无线通信模块上，因此无线通信模块设计的合理程度决定节点能耗的大小.在利用高斯随机向量时，单个数据节点需要发送的数据包个数为m，因此无线通信模块要消耗大量能量.本文中，尽管使用了稀疏随机测量矩阵，但由于其多值性，测量矩阵的非零项元素以概率出现，所以每个数据节点平均传送的数据包的个数为O(logn)，在大规模传感网络中，n值一般较大，数据包的传送个数也相应较大.本文从减少节点间通信的数据量出发，将单个数据节点产生的二值向量的稀疏度设定为k(本文中k=8，设置为4，6，16等整数对结果影响不大)，在减少重构误差的情形下，增加编码节点数并不会导致数据节点与编码节点间通信量的增大，因为单个数据节点只传输k个数据包，在大规模传感网络中，显然有k＜O(logn)［5］.所以本文构建的基于不平衡扩展模型的分布式压缩感知网络不仅能通过增加编码节点数使信号的重构误差减小，而且它在节能方面尤为突出.

4.2 网络模型重构性能分析

由于常用的高斯测量矩阵具有高效压缩信号和重构误差小的优点，因此用该矩阵与本文中网络模型构建的稀疏测量矩阵进行对比，论证本文模型的合理性.其步骤如下:①对信号进行测量和重建仿真;②对比信号的重建质量，其中信号重建的质量评价标准包括信噪比和均方误差.假设一个m×n的原始信号x，算法所重建的信号为，则

1)信噪比

2)均方误差

本文中测量矩阵产生的原理与参数设置如下:①高斯随机测量矩阵参数设置.每个数据节点随机产生m=512个高斯向量.②稀疏测量矩阵参数设置.每个数据节点产生稀疏度k=8，长度为512的二值向量.

考虑在有噪声环境下数据在传输过程中总有乘性或加性的噪声污染，为更好模拟实际环境，在数据节点传输数据的过程中添加了均值为0、方差为1的高斯白噪声，并分别利用高斯测量矩阵和稀疏测量矩阵对火源点在不同位置的数据样本进行测量以及重构，从而获得在不同火源点上信号重构的信噪比和均方误差值，如表1所示.从表1可以看出，在采用不平衡扩展模型提高计算效率、降低能耗的基础上，在同一数据样本集下，稀疏测量矩阵与高斯测量矩阵相比，获得的测量值都能完美重构原信号，所得到重构信号的信噪比和均方误差都无明显差别.

表1 火源点处于不同位置情况下测量矩阵性能比较

从图2可看出，随着测量数增大，在稀疏随机矩阵和高斯随机矩阵下重构的信噪比都呈递增趋势，但前者比后者的趋势更为明显.从图3同样可以看出，在测量数较小(即小样本时)且存在高斯噪声的情况下，稀疏随机矩阵同样表现出较好的重构性能，即在这种情况下，稀疏随机矩阵优化算法依然显示出其算法上的优越性.

图2 测量数与信噪比的关系曲线

图3 测量数与均方误差的关系曲线

5 结语

针对大规模无线传感网络在火灾信息收集中的节点能量有限和带宽有限问题，提出基于不平衡扩展模型的分布式压缩感知网络，进而把数据的传输任务均衡分布于各个数据节点间.通过算法的理论分析和网络的能耗分析表明，该网络模型在减少数据节点运算量和数据节点与编码节点间数据传输量的同时，较大地节省了功耗，延长了传感网络的工作寿命.实验的仿真结果也表明，本文中构建的网络模型应用在有噪环境中有着较好的重构性能.在本文中，只利用了无线传感网络节点间的空间相关性进行数据压缩与重构，下一步的研究应考虑如何在结合时间相关性和空间相关性的基础上建立模型，进一步减小节点间数据传输量的同时提高信号的重构性能.

［1］Mhmudimanesh M，Khelil A，Suri N.Reordering for better compressibility:efficient spatial sampling in wireless sensor networks［C］//The Third IEEE International Conference on Sensor Network，Ubiquitous，and Trustworthy Computing.Newport Beach，CA，USA，2010:50－57.

［2］Hu Haifeng，Yang Zhen.Spatial correlation-based distributed compressed sensing in wireless sensor networks［C］//Wireless Communications Networking and Mobile Computing.Chengdu，China，2010:1－4.

［3］Luo Chong，Wu Feng，Sun Jun，et al.Compressive data gathering for large-scale wireless sensor networks［C］//Proceedings of the15th Annual International Conference on Mobile Computing and Network. Beijing， China，2009:145－156.

［4］Wang Wei，Garofalakis M，Ramchandran K W.Distributed sparse random projections for refinable approximation［C］//Proceedings of the Sixth International Symposium on Information Processing in Sensor Networks.Cambridge，MA，USA，2007:331－339.

［5］Sipser M，Spielman D A.Expander codes［J］.IEEE Transaction on Information Theory，1996，42(6):1710－1722.

［6］Berinde R，Gilbert A C，Indyk P，et al.Combining geometry and combinatorics:a unified approach to sparse signal recovery［C］//46th Annual Allerton Conference on Communication，Control，and Computing.Urbana-Champaign，IL，USA，2008:798－805.

［7］Xu Weiyu，Hassibi Babak.Efficient compressive sensing with deterministic guaranteesusing expandergraphs［C］//IEEE Information Theory Workshop.Tahoe City，CA，USA，2007:414－419.

［8］Otero Daniel，Arce Gonzalo R.Generalized restricted isometry property for alpha-stable random projections［C］//IEEE International Conference on Acoustics，Speech and Signal Processing.Prague，Czech Republic，2011:3676－3679.

［9］Yuen K，Liang B，Li B.A distributed framework for correlated data gathering in sensor network［J］.IEEE Trans-actions on Vehicular Technology，2008，57(1):578－593.

［10］Jafarpour Sina，Xu Weiyu，Hassibi Babak，et al.Efficient and robust compressed sensing using optimized expander graphs［J］.IEEE Transactions on Information Theory，2009，55(9):4299－4308.

［11］Lan Lihui，Ju Shiguang，Jin Hua.Anonymizing social network using bipartite graph［C］//Information Sciences on Computational and International Conference.Washington，DC，USA:IEEE Computer Society，2010:993－996.

［12］de Castro Yohann.Error prediction and variable selection via unbalance［J］.Statistics Theory，2010，4:1－15.

［13］Emmanuel Candes，Romberg Justin.L1-MAGIC:recovery of sparse signals via convex programming［EB/OL］.(2009-01-22)［2011-08］.http://users.ece.gatech.edu/justin/l1magic/downloads/l1magic.pdf.

［14］石光明，刘丹华，高大化，等.压缩感知理论及研究进展［J］.电子学报，2009，37(5):1070－1081.

Shi Guangming，Liu Danhua，Gao Dahua，et al.Advances in theory and application of compressed sensing［J］.Acta Electronica Sinica，2009，37(5):1070－1081.(in Chinese)

［15］Kang Jian，Tang Liwei，Zuo Xianzhang，et al.Distributed compressed sensing-based data fusion in sensor networks［C］//First International Conference on Pervasive Computing Signal Processing and Applications.Harbin，China，2010:1083－1086.

Distributed compressed fire signal sensing based on unbalance expander

Zhuang Zhemin1Wu Like1Lu Xiaobo2

(1Department of Electronics，Shantou University，Shantou 515063，China)
(2School of Automation，Southeast University，Nanjing 210096，China)

In wireless sensor networks，the huge power consumption of part of nodes brings great hardship for various applications，which is caused by the unbalanced data transmission and calculation.To solve this problem，using bipartite graph thought in graph theory，distributed compressive sensing network architecture based on unbalanced expander is proposed.Meanwhile the distributed algorithm corresponding to the architecture is designed.This algorithm decides whether or not to transmit data through a fixed column sparse degree sparse random bipartite matrix，then decentralize the transmission and calculation mission to every node equally and reconstruct the data in fusion center by using secondorder cone programming.Finally the distributed compressive sensing network based on unbalanced expander is applied to the fire ground simulation experiment and the superiority of the algorithm and the energy conservation of the network are analyzed in detail.In the process of simulation，through analysis of the mean square error and signal-to-noise ratio，it is proved that the proposed model not only has good effect on reducing nodes'energy consumption but also ensures the performance for the signal reconstruction in noisy case.

wireless sensor networks;distributed compressive sensing;unbalance expander model;sparse measurement matrix

TP393

A

1001－0505(2013)01-0039-06

10.3969/j.issn.1001－0505.2013.01.008

2012-06-21.

庄哲民(1965—)，男，博士，教授，zmzhuang@stu.edu.cn.

国家自然科学基金面上资助项目(61070152)、广东省重大科技计划项目资金资助项目(2011A080404005)、汕头大学科研基金资助项目(NTF10012).

庄哲民，吴力科，路小波.基于不平衡扩展模型的火灾信息分布式压缩感知［J］.东南大学学报:自然科学版，2013，43(1):39－44.［doi:10.3969/j.issn.1001－0505.2013.01.008］