基于壓縮感知的分布式協同估計算法*

張亞東，姚彥鑫

(北京信息科技大學 信息與通信工程學院，北京 100101)

基于壓縮感知的分布式協同估計算法*

張亞東，姚彥鑫*

(北京信息科技大學 信息與通信工程學院，北京 100101)

為了降低分布式協同估計算法的計算量并改善其收斂性能，提出了基于壓縮感知(CS)和遞歸最小二乘(RLS)的分布式協同估計算法。該算法在傳統(tǒng)RLS分布式協同估計算法的基礎上引入壓縮感知技術，首先在壓縮域中進行遞歸最小二乘運算，然后利用壓縮感知重構算法得到未知參數向量的估計值。提出的算法能夠在增量式策略和兩種模式的擴散式策略下實現對未知向量的有效估計。理論分析和仿真結果表明，該算法一方面降低了RLS分布式協同估計算法的計算量，另一方面保持較快的收斂速度與良好的均方誤差性能。

分布式估計；壓縮感知；遞歸最小二乘;增量式策略;擴散式策略

1 引 言

分布式網絡由特定地理區(qū)域中分散的大量節(jié)點構成，通過節(jié)點間的協作可以完成分布式估計、分布式檢測、目標定位及追蹤等復雜任務。分布式協同估計是指在分布式網絡環(huán)境中，各節(jié)點采用合適的分布式策略和估計算法，協同估計所處環(huán)境中感興趣的未知確定性參數的過程，是目前分布式網絡的研究熱點之一[1]。

壓縮感知(Compressed Sensing,CS)是一種新興的信號獲取和重構技術。對于稀疏信號，以遠低于奈奎斯特采樣定理的頻率獲取少量數據，應用恰當的重構算法實現對原始信號的精確恢復[2]。分布式網絡中待估計的未知參數向量往往具有稀疏性[3]，為CS理論的應用提供了條件。文獻[4]從稀疏模型的建立與稀疏信號的重構等方面對壓縮感知在分布式網絡中的應用進行了詳細的討論；文獻[5]引入了壓縮感知，提出了一種用于傳感器節(jié)點的貪婪重構算法，但是對分布式傳輸策略未作考慮；文獻[6]應用壓縮感知對基于最小均方(Least Mean Square,LMS)算法的分布式估計方案做了改進，但只研究了擴散策略下的LMS估計算法，對其他的傳輸策略和收斂性能較好的遞歸最小二乘(Recursive Least-Square,RLS)算法沒有提及。

本文結合CS理論和RLS算法提出了一種分布式協同估計算法，該算法在不同的分布式估計策略下實現對未知參數向量的有效估計，具有良好的均方誤差(Mean Square Error，MSE)性能和較快的收斂速度，降低了傳統(tǒng)RLS分布式協同估計算法的計算量和網絡的信息存儲與傳輸負擔。

2 CS理論概述

壓縮感知理論的基本觀點是：若信號是稀疏的或在某個變換域上是稀疏的，則可用一個測量矩陣將原始信號從一個高維空間投影到一個低維空間，然后通過求解優(yōu)化問題，從少量投影中重構出原始信號[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的解中，重建出的稀疏信號表示為

3 系統(tǒng)模型

分布式網絡是由具有有限處理能力的N個節(jié)點連接而成的互連網絡，各節(jié)點只與確定的鄰居節(jié)點交換信息。一個典型的分布式網絡的拓撲結構可以用圖1進行描述。

圖1 分布式網絡結構圖

考慮如圖1所示的具有N個節(jié)點的分布式網絡，Nk表示節(jié)點k的封閉鄰域(即所有鄰居節(jié)點的集合，包括它本身)。該網絡的目的是協同估計一個M×1的未知參數向量ω0。在每一時刻i，節(jié)點k獲得一個標量測量值dk(i)：

(5)

式中：uk(i)是長度為M的輸入信號向量，vk(i)是環(huán)境噪聲。所有節(jié)點的測量值都涉及到未知參數向量ω0，而ω0是具有S?M個非零元素的稀疏向量。分布式網絡中的N個節(jié)點基于特定的策略與鄰居節(jié)點進行信息交互，協同合作計算向量ω0的估計值，使得如下代價函數最?。?/p>

(6)

式中：E{·}表示求期望操作。

分布式策略分為基于融合中心的集中式策略和基于節(jié)點間信息交換的協作式策略。增量式策略中，各節(jié)點間形成一條環(huán)形路徑，信息從一個節(jié)點沿路徑傳往相鄰的下一個節(jié)點，使信息傳輸至整個網絡的所有節(jié)點[8]。擴散式策略依據網絡的拓撲結構和相鄰節(jié)點交互信息，節(jié)點采用交互之后的信息對本地估計進行更新，而依據各節(jié)點信息聚合和自適應估計的過程，又分為先結合再自適應(Combine-Then-Adapt，CTA)的擴散策略以及先自適應再結合(Adapt-Then-Combine,ATC)的擴散策略[9]。

4 分布式壓縮估計算法

由于未知參數向量ω0的稀疏性，可利用CS理論并結合RLS算法實現對向量ω0的協同估計?；贑S和RLS的分布式估計算法(CS-RLS)的基本框圖如圖2所示。

圖2 CS-RLS算法框圖

(7)

基于網絡中信息交互方式的差異，可以采用不同的協作策略將CS-RLS算法應用到整個分布式網絡，而在不同的協作策略下，CS-RLS算法具有不同的具體形式。

4.1 增量式CS-RLS算法

采用增量式策略，需要在整個網絡中選擇一條信息傳輸的循環(huán)路徑,如圖3所示。

圖3 增量式策略的循環(huán)路徑

(1)初始化。設定循環(huán)路徑，設置i=0時的初始值，φ0=0，轉移矩陣Pk(i)=σE，σ是一個小的正數，稱為遺忘因子，E為單位矩陣。

(2)迭代計算。當i=1,2,…,I，對每一個節(jié)點k=1,2,…,N，接收來自前一節(jié)點的估計信息φk-1(i)：

(8)

(9)

(10)

4.2 擴散式CS-RLS算法

擴散式策略的基本原理是節(jié)點k在第i個時刻將相鄰節(jié)點的估計值{φl(i);l∈Nk}與節(jié)點自身的估計值φk(i)相結合，以得到對未知參數向量的全局估計。擴散式策略依據各節(jié)點自適應和信息交互過程的先后順序，又分為ATC模式和CTA模式。ATC模式下各節(jié)點先進行自適應估計然后再與相鄰節(jié)點進行信息交互，而CTA模式是各節(jié)點先進行信息交互再進行自適應估計過程。ATC模式下的CS-RLS估計算法過程如下：

(2)迭代計算。當i=1,2,…,I，對每一個節(jié)點k=1,2,…,N,結合相鄰節(jié)點的估計值對轉移矩陣和本地估計進行更新：

(11)

(12)

(13)

式中：akl是各節(jié)點間的連接系數，可通過Metropolis準則計算[10]：

(3)第I次迭代之后，對每一個節(jié)點有

(14)

5 仿真分析

首先，驗證算法在增量式策略和兩種擴散式策略下的性能，主要考察其收斂性和均方誤差性能。圖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算法具有優(yōu)于普通RLS協同估計算法的MSE性能，可以達到更低的均方誤差，而CS-RLS算法和DCE算法的MSE性能非常接近?？紤]收斂性，在迭代次數為200次時CS-RLS算法已經收斂，而DCE算法在迭代次數為300次時才達到收斂，顯然，CS-RLS估計算法具有更快的收斂速度，這有賴于RLS算法優(yōu)于LMS算法的快速收斂性。

圖5 3種算法的MSE性能

6 結束語

針對分布式協同估計問題，本文結合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] 吳凌華,張小川. 壓縮感知的發(fā)展與應用[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年于北京航空航天大學獲博士學位，現為副教授、碩士生導師，主要研究方向為壓縮感知與智能信號處理、節(jié)能通信網絡等。

Email:yanxin_buaa@126.com

*通信作者：yanxin_buaa@126.com Corresponding author：yanxin_buaa@126.com