张亚东,姚彦鑫
(北京信息科技大学 信息与通信工程学院,北京 100101)
基于压缩感知的分布式协同估计算法*
张亚东,姚彦鑫*
(北京信息科技大学 信息与通信工程学院,北京 100101)
为了降低分布式协同估计算法的计算量并改善其收敛性能,提出了基于压缩感知(CS)和递归最小二乘(RLS)的分布式协同估计算法。该算法在传统RLS分布式协同估计算法的基础上引入压缩感知技术,首先在压缩域中进行递归最小二乘运算,然后利用压缩感知重构算法得到未知参数向量的估计值。提出的算法能够在增量式策略和两种模式的扩散式策略下实现对未知向量的有效估计。理论分析和仿真结果表明,该算法一方面降低了RLS分布式协同估计算法的计算量,另一方面保持较快的收敛速度与良好的均方误差性能。
分布式估计;压缩感知;递归最小二乘;增量式策略;扩散式策略
分布式网络由特定地理区域中分散的大量节点构成,通过节点间的协作可以完成分布式估计、分布式检测、目标定位及追踪等复杂任务。分布式协同估计是指在分布式网络环境中,各节点采用合适的分布式策略和估计算法,协同估计所处环境中感兴趣的未知确定性参数的过程,是目前分布式网络的研究热点之一[1]。
压缩感知(Compressed Sensing,CS)是一种新兴的信号获取和重构技术。对于稀疏信号,以远低于奈奎斯特采样定理的频率获取少量数据,应用恰当的重构算法实现对原始信号的精确恢复[2]。分布式网络中待估计的未知参数向量往往具有稀疏性[3],为CS理论的应用提供了条件。文献[4]从稀疏模型的建立与稀疏信号的重构等方面对压缩感知在分布式网络中的应用进行了详细的讨论;文献[5]引入了压缩感知,提出了一种用于传感器节点的贪婪重构算法,但是对分布式传输策略未作考虑;文献[6]应用压缩感知对基于最小均方(Least Mean Square,LMS)算法的分布式估计方案做了改进,但只研究了扩散策略下的LMS估计算法,对其他的传输策略和收敛性能较好的递归最小二乘(Recursive Least-Square,RLS)算法没有提及。
本文结合CS理论和RLS算法提出了一种分布式协同估计算法,该算法在不同的分布式估计策略下实现对未知参数向量的有效估计,具有良好的均方误差(Mean Square Error,MSE)性能和较快的收敛速度,降低了传统RLS分布式协同估计算法的计算量和网络的信息存储与传输负担。
压缩感知理论的基本观点是:若信号是稀疏的或在某个变换域上是稀疏的,则可用一个测量矩阵将原始信号从一个高维空间投影到一个低维空间,然后通过求解优化问题,从少量投影中重构出原始信号[7]。
压缩感知的基本模型如下:一个长度为Q的稀疏信号f,只有K个非零值,且K≪Q,可以采用一种随机的观测方式对该信号进行采样:
y=Φf。
(1)
(2)
(3)
式中:Ψ为N×N维矩阵,称为稀疏分解矩阵;x为N×1维向量,是K稀疏的变换域系数,称为稀疏向量。则y可表示为
y=Φf=ΦΨx=Θx。
(4)
式中:Θ是一个M×N维矩阵。在所有满足方程y=Θx的解中,重建出的稀疏信号表示为
分布式网络是由具有有限处理能力的N个节点连接而成的互连网络,各节点只与确定的邻居节点交换信息。一个典型的分布式网络的拓扑结构可以用图1进行描述。
图1 分布式网络结构图
考虑如图1所示的具有N个节点的分布式网络,Nk表示节点k的封闭邻域(即所有邻居节点的集合,包括它本身)。该网络的目的是协同估计一个M×1的未知参数向量ω0。在每一时刻i,节点k获得一个标量测量值dk(i):
(5)
式中:uk(i)是长度为M的输入信号向量,vk(i)是环境噪声。所有节点的测量值都涉及到未知参数向量ω0,而ω0是具有S≪M个非零元素的稀疏向量。分布式网络中的N个节点基于特定的策略与邻居节点进行信息交互,协同合作计算向量ω0的估计值,使得如下代价函数最小:
(6)
式中:E{·}表示求期望操作。
分布式策略分为基于融合中心的集中式策略和基于节点间信息交换的协作式策略。增量式策略中,各节点间形成一条环形路径,信息从一个节点沿路径传往相邻的下一个节点,使信息传输至整个网络的所有节点[8]。扩散式策略依据网络的拓扑结构和相邻节点交互信息,节点采用交互之后的信息对本地估计进行更新,而依据各节点信息聚合和自适应估计的过程,又分为先结合再自适应(Combine-Then-Adapt,CTA)的扩散策略以及先自适应再结合(Adapt-Then-Combine,ATC)的扩散策略[9]。
由于未知参数向量ω0的稀疏性,可利用CS理论并结合RLS算法实现对向量ω0的协同估计。基于CS和RLS的分布式估计算法(CS-RLS)的基本框图如图2所示。
图2 CS-RLS算法框图
(7)
基于网络中信息交互方式的差异,可以采用不同的协作策略将CS-RLS算法应用到整个分布式网络,而在不同的协作策略下,CS-RLS算法具有不同的具体形式。
4.1 增量式CS-RLS算法
采用增量式策略,需要在整个网络中选择一条信息传输的循环路径,如图3所示。
图3 增量式策略的循环路径
(1)初始化。设定循环路径,设置i=0时的初始值,φ0=0,转移矩阵Pk(i)=σE,σ是一个小的正数,称为遗忘因子,E为单位矩阵。
(2)迭代计算。当i=1,2,…,I,对每一个节点k=1,2,…,N,接收来自前一节点的估计信息φk-1(i):
(8)
(9)
(10)
4.2 扩散式CS-RLS算法
扩散式策略的基本原理是节点k在第i个时刻将相邻节点的估计值{φl(i);l∈Nk}与节点自身的估计值φk(i)相结合,以得到对未知参数向量的全局估计。扩散式策略依据各节点自适应和信息交互过程的先后顺序,又分为ATC模式和CTA模式。ATC模式下各节点先进行自适应估计然后再与相邻节点进行信息交互,而CTA模式是各节点先进行信息交互再进行自适应估计过程。ATC模式下的CS-RLS估计算法过程如下:
(2)迭代计算。当i=1,2,…,I,对每一个节点k=1,2,…,N,结合相邻节点的估计值对转移矩阵和本地估计进行更新:
(11)
(12)
(13)
式中:akl是各节点间的连接系数,可通过Metropolis准则计算[10]:
(3)第I次迭代之后,对每一个节点有
(14)
首先,验证算法在增量式策略和两种扩散式策略下的性能,主要考察其收敛性和均方误差性能。图4即是CS-RLS算法在3种策略下的MSE性能曲线。均方误差的计算如下[12]:
(15)
图4 CS-RLS算法在不同策略下的MSE性能
CS-RLS估计算法在3种策略下均有良好的估计性能与较快的收敛速度。算法在两种扩散式策略下的性能十分接近,均方误差性能和收敛速度几乎相同,而增量式策略下的均方误差更低。实际实施中,可以根据网络资源的具体限制,灵活选择合适的协作策略,而又能保证估计性能的要求。
接下来,比较CS-RLS算法与普通的RLS协同估计算法以及文献[6]的DCE估计算法。由于文献[6]采用ATC扩散策略,因此,选择ATC模式作为本次仿真的协作策略。3种算法的MSE性能如图5所示。由图5可知,CS-RLS算法与DCE算法具有优于普通RLS协同估计算法的MSE性能,可以达到更低的均方误差,而CS-RLS算法和DCE算法的MSE性能非常接近。考虑收敛性,在迭代次数为200次时CS-RLS算法已经收敛,而DCE算法在迭代次数为300次时才达到收敛,显然,CS-RLS估计算法具有更快的收敛速度,这有赖于RLS算法优于LMS算法的快速收敛性。
图5 3种算法的MSE性能
针对分布式协同估计问题,本文结合CS理论提出了一种协同估计算法。首先,介绍了压缩感知的基本理论和分布式协同估计的基本模型;其次,提出了基于CS理论和递归最小二乘的CS-RLS分布式估计算法。CS-RLS算法结合了CS低采样率和RLS收敛速度快的特点,有效实现了对未知参数向量的估计。仿真表明该算法在不同的协作策略下均具有良好的性能,降低了网络的通信和计算负担,具有较好的MSE性能和更快的收敛速度。下一步工作中,将研究压缩感知的观测矩阵以及融合准则、遗忘因子等对算法性能的具体影响。
[1] CATTIVELLI F S,SAYED A H. Diffusion LMS strategies for distributed estimation[J].IEEE Transactions on Signal Processing,2010,58(3):1035-1048.
[2] DONOHO D L. Compressed sensing[J].IEEE Transactions on Information Theory,2006,52(4):1289-1306.
[3] LIU Z,LIU Y,LI C. Distributed sparse recursive Least-squares over networks[J].IEEE Transactions on Signal Processing,2014,62(6):1386-1395.
[4] 康莉,谢维信,黄建军,等. 无线传感器网络中的分布式压缩感知技术[J].信号处理,2013,29(11):1560-1567. KANG Li,XIE Weixin,HUANG Jianjun,et al. Distributed compressive sensing for wireless sensor networks[J].Journal of Signal Processing,2013,29(11):1560-1567.(in Chinese)
[5] CHEN W,RODRIGUES M R D,WASSELL I J. Distributed compressive sensing reconstruction via common support discovery[C]//Proceedings of 2011 IEEE International Conference on Communications(ICC).Kyoto,Japan:IEEE,2011:1-5.
[6] XU S,DE LAMARE R C,POOR H V. Distributed compressed estimation based on compressive sensing[J].IEEE Signal Processing Letters,2015,22(9):1311-1315.
[7] 吴凌华,张小川. 压缩感知的发展与应用[J].电讯技术,2011,51(1):120-124. WU Linghua,ZHANG Xiaochuan. Development and application of compressed sensing[J].Telecommunication Engineering,2011,51(1):120-124.(in Chinese)
[8] BOGDANOVIC N,PLATA-CHAVES J,BERBERIDIS K. Distributed incremental-based LMS for node-specific adaptive parameter estimation[J].IEEE Transactions on Signal Processing,2014,62(20):5382-5397.
[9] SAYIN M O,KOZAT S S. Compressive diffusion strategies over distributed networks for reduced communication load[J].IEEE Transactions on Signal Processing,2014,62(20):5308-5323.
[10] 郭超,张政保,姚少林,等. 自适应扩散算法的误差性能分析[J].电讯技术,2016,56(9):963-968. GUO Chao,ZHANG Zhengbao,YAO Shaolin,et al. Error performance analysis of adaptive diffusion algorithm[J].Telecommunication Engineering,2016,56(9):963-968.(in Chinese)
[11] ARABLOUEI R,DOGANCAY K,WERNER S,et al. Adaptive distributed estimation based on recursive Least-Squares and partial diffusion[J].IEEE Transactions on Signal Processing,2014,62(14):3510-3522.
[12] 王硕. 分布式协同估计方法研究 [D].北京:北京理工大学,2015. WANG Shuo. Research on distributed collaborative estimation [D].Beijing:Beijing Institute of Technology,2015.(in Chinese)
A Distributed Collaborative Estimation Algorithm Based on Compressed Sensing
ZHANG Yadong,YAO Yanxin
(School of Information and Communication Engineering,Beijing Information Science & Technology University,Beijing 100101,China)
In order to reduce the amount of calculation and improve the convergence performance,a distributed collaborative estimation algorithm based on compressed sensing and recursive least square(RLS) is proposed. Based on the traditional RLS distributed collaborative estimation algorithm,this algorithm introduces compressed sensing technology. Firstly,the recursive least square method is applied in the compressed domain. And then the estimation of the unknown parameter vector is achieved by compressed sensing reconstruction algorithm. The proposed algorithm can effectively estimate the unknown vector under the incremental strategy and two modes of diffusion strategy. The result of theoretical analysis and simulation shows that the proposed algorithm reduces the amount of calculation of RLS distributed collaborative estimation algorithm and also keeps fast convergence speed and good mean square error performance.
distributed estimation;compressed sensing;recursive least square;incremental strategy;diffusion strategy
10.3969/j.issn.1001-893x.2017.04.001
张亚东,姚彦鑫.基于压缩感知的分布式协同估计算法[J].电讯技术,2017,57(4):377-381.[ZHANG Yadong,YAO Yanxin.A distributed collaborative estimation algorithm based on compressed sensing[J].Telecommunication Engineering,2017,57(4):377-381.]
2016-12-21;
2017-03-02 Received date:2016-12-21;Revised date:2017-03-02
国家自然科学基金资助项目(61302073);北京市自然科学基金面上项目(4172021);北京市教委面上项目 (KM201711232010);北京市自然科学基金资助项目(Z160002)
TN911
A
1001-893X(2017)04-0377-05
张亚东(1990—),男,河南平顶山人,2013年于郑州大学获学士学位,现为硕士研究生,主要研究方向为通信信号处理;
Email:zydtxgc@yeah.net
姚彦鑫(1982—),女,河北张家口人,2009年于北京航空航天大学获博士学位,现为副教授、硕士生导师,主要研究方向为压缩感知与智能信号处理、节能通信网络等。
Email:yanxin_buaa@126.com
*通信作者:yanxin_buaa@126.com Corresponding author:yanxin_buaa@126.com