張亞東，姚彥鑫

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

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

張亞東，姚彥鑫*

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

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

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

1 引 言

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

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

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

2 CS理論概述

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

壓縮感知的基本模型如下：一個長度為Q的稀疏信號f，只有K個非零值，且K?Q，可以采用一種隨機的觀測方式對該信號進行采樣：

y=Φf。

(1)

(2)

(3)

式中:Ψ為N×N維矩陣，稱為稀疏分解矩陣；x為N×1維向量，是K稀疏的變換域系數(shù)，稱為稀疏向量。則y可表示為

y=Φf=ΦΨx=Θx。

(4)

式中：Θ是一個M×N維矩陣。在所有滿足方程y=Θx的解中，重建出的稀疏信號表示為

3 系統(tǒng)模型

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

圖1 分布式網(wǎng)絡(luò)結(jié)構(gòu)圖

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

(5)

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

(6)

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

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

4 分布式壓縮估計算法

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

圖2 CS-RLS算法框圖

(7)

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

4.1 增量式CS-RLS算法

采用增量式策略，需要在整個網(wǎng)絡(luò)中選擇一條信息傳輸?shù)难h(huán)路徑,如圖3所示。

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

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

(2)迭代計算。當(dāng)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é)合，以得到對未知參數(shù)向量的全局估計。擴散式策略依據(jù)各節(jié)點自適應(yīng)和信息交互過程的先后順序，又分為ATC模式和CTA模式。ATC模式下各節(jié)點先進行自適應(yīng)估計然后再與相鄰節(jié)點進行信息交互，而CTA模式是各節(jié)點先進行信息交互再進行自適應(yīng)估計過程。ATC模式下的CS-RLS估計算法過程如下：

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

(11)

(12)

(13)

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

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

(14)

5 仿真分析

首先，驗證算法在增量式策略和兩種擴散式策略下的性能，主要考察其收斂性和均方誤差性能。圖4即是CS-RLS算法在3種策略下的MSE性能曲線。均方誤差的計算如下[12]：

(15)

圖4 CS-RLS算法在不同策略下的MSE性能

CS-RLS估計算法在3種策略下均有良好的估計性能與較快的收斂速度。算法在兩種擴散式策略下的性能十分接近，均方誤差性能和收斂速度幾乎相同，而增量式策略下的均方誤差更低。實際實施中，可以根據(jù)網(wǎng)絡(luò)資源的具體限制，靈活選擇合適的協(xié)作策略，而又能保證估計性能的要求。

接下來，比較CS-RLS算法與普通的RLS協(xié)同估計算法以及文獻[6]的DCE估計算法。由于文獻[6]采用ATC擴散策略，因此，選擇ATC模式作為本次仿真的協(xié)作策略。3種算法的MSE性能如圖5所示。由圖5可知，CS-RLS算法與DCE算法具有優(yōu)于普通RLS協(xié)同估計算法的MSE性能，可以達到更低的均方誤差，而CS-RLS算法和DCE算法的MSE性能非常接近。考慮收斂性，在迭代次數(shù)為200次時CS-RLS算法已經(jīng)收斂，而DCE算法在迭代次數(shù)為300次時才達到收斂，顯然，CS-RLS估計算法具有更快的收斂速度，這有賴于RLS算法優(yōu)于LMS算法的快速收斂性。

圖5 3種算法的MSE性能

6 結(jié)束語

針對分布式協(xié)同估計問題，本文結(jié)合CS理論提出了一種協(xié)同估計算法。首先，介紹了壓縮感知的基本理論和分布式協(xié)同估計的基本模型;其次，提出了基于CS理論和遞歸最小二乘的CS-RLS分布式估計算法。CS-RLS算法結(jié)合了CS低采樣率和RLS收斂速度快的特點，有效實現(xiàn)了對未知參數(shù)向量的估計。仿真表明該算法在不同的協(xié)作策略下均具有良好的性能，降低了網(wǎng)絡(luò)的通信和計算負擔(dān)，具有較好的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] 康莉,謝維信,黃建軍,等. 無線傳感器網(wǎng)絡(luò)中的分布式壓縮感知技術(shù)[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ā)展與應(yīng)用[J].電訊技術(shù),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] 郭超,張政保,姚少林,等. 自適應(yīng)擴散算法的誤差性能分析[J].電訊技術(shù),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] 王碩. 分布式協(xié)同估計方法研究 [D].北京:北京理工大學(xué),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

張亞東，姚彥鑫.基于壓縮感知的分布式協(xié)同估計算法[J].電訊技術(shù)，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

國家自然科學(xué)基金資助項目(61302073)；北京市自然科學(xué)基金面上項目(4172021)；北京市教委面上項目 (KM201711232010)；北京市自然科學(xué)基金資助項目(Z160002)

TN911

A

1001-893X(2017)04-0377-05

張亞東(1990—)，男，河南平頂山人，2013年于鄭州大學(xué)獲學(xué)士學(xué)位，現(xiàn)為碩士研究生，主要研究方向為通信信號處理;

Email:zydtxgc@yeah.net

姚彥鑫(1982—)，女，河北張家口人，2009年于北京航空航天大學(xué)獲博士學(xué)位，現(xiàn)為副教授、碩士生導(dǎo)師，主要研究方向為壓縮感知與智能信號處理、節(jié)能通信網(wǎng)絡(luò)等。

Email:yanxin_buaa@126.com

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