基于概率稀疏隨機(jī)矩陣的壓縮數(shù)據(jù)收集方法

張 波劉郁林 王 開 王 嬌

(重慶通信學(xué)院DSP研究室 重慶 400035)

1 引言

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,WSNs)[1]憑借其部署靈活、抗毀性強(qiáng)、高容錯(cuò)等獨(dú)特優(yōu)勢(shì)，在環(huán)境監(jiān)測(cè)、城市管理、搶險(xiǎn)救災(zāi)等眾多領(lǐng)域均具有非常廣闊的應(yīng)用前景。傳感器節(jié)點(diǎn)通常采用微型嵌入式設(shè)備，攜帶的電池能量非常有限。因此，在節(jié)點(diǎn)能量受限條件下，實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)數(shù)據(jù)的有效收集，成為亟待解決的關(guān)鍵問題。

為節(jié)約數(shù)據(jù)收集的通信能耗，可采用數(shù)據(jù)壓縮技術(shù)對(duì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行壓縮，從而減少數(shù)據(jù)的傳輸量，達(dá)到節(jié)約節(jié)點(diǎn)能量目的[2]。然而傳統(tǒng)的數(shù)據(jù)壓縮方法一般先將數(shù)據(jù)壓縮后再傳輸，這種方法需要預(yù)先知道整個(gè)網(wǎng)絡(luò)(或者網(wǎng)絡(luò)的一部分)節(jié)點(diǎn)間的相關(guān)性，會(huì)帶來很高的額外通信開銷[3](交換數(shù)據(jù)來感知節(jié)點(diǎn)間相關(guān)性帶來的額外通信開銷)。近年來，國(guó)內(nèi)外研究學(xué)者將壓縮感知(Compressed Sensing, CS)[4,5]理論應(yīng)用到網(wǎng)絡(luò)數(shù)據(jù)收集中，提出了一種壓縮數(shù)據(jù)收集(Compressive Data Gathering, CDG)[6]方法，該方法將CS的測(cè)量過程和WSNs的多跳路由相結(jié)合，在傳輸?shù)倪^程中即可實(shí)現(xiàn)數(shù)據(jù)壓縮，為WSNs高能效數(shù)據(jù)收集提供了一種理想的解決思路。

然而，文獻(xiàn)[7]研究發(fā)現(xiàn)，采用傳統(tǒng)的稠密測(cè)量矩陣作為網(wǎng)絡(luò)數(shù)據(jù)收集的測(cè)量矩陣會(huì)帶來密集觀測(cè)問題，由于每個(gè)測(cè)量值均由密集觀測(cè)得到，因此測(cè)量值的獲取需要極大的通信開銷，且進(jìn)行數(shù)據(jù)重建時(shí)計(jì)算量巨大。為避免密集觀測(cè)問題，文獻(xiàn)[8]提出用稀疏隨機(jī)矩陣作為測(cè)量矩陣對(duì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行測(cè)量，該方法計(jì)算測(cè)量值只需部分節(jié)點(diǎn)參與，顯著減少了獲取測(cè)量值的通信開銷。文獻(xiàn)[9]設(shè)計(jì)了一種稀疏Toeplitz測(cè)量矩陣，該矩陣硬件實(shí)現(xiàn)容易，存儲(chǔ)成本低，在分布式應(yīng)用中，可節(jié)約獲取測(cè)量值的通信開銷，有效延長(zhǎng)網(wǎng)絡(luò)生命周期。

文獻(xiàn)[8]和文獻(xiàn)[9]均是從減少參與測(cè)量值計(jì)算節(jié)點(diǎn)個(gè)數(shù)的角度出發(fā)，設(shè)計(jì)適用于壓縮數(shù)據(jù)收集的稀疏測(cè)量矩陣。一般地，參與測(cè)量值計(jì)算的有效投影節(jié)點(diǎn)個(gè)數(shù)越少且分布越集中，那么獲取測(cè)量值的通信開銷越小?；谶@種思想，文獻(xiàn)[10]將測(cè)量過程和分簇路由相結(jié)合，提出了一種可實(shí)現(xiàn)網(wǎng)絡(luò)數(shù)據(jù)局部化測(cè)量的塊對(duì)角矩陣，但該測(cè)量矩陣需要較多的測(cè)量次數(shù)才能確保原始數(shù)據(jù)精確重構(gòu)，抵消了單次測(cè)量能耗較低的優(yōu)勢(shì)。

針對(duì)上述文獻(xiàn)的不足，本文將節(jié)點(diǎn)間距離作為參數(shù)來控制節(jié)點(diǎn)當(dāng)選有效投影節(jié)點(diǎn)的概率，設(shè)計(jì)了一種可以讓有效投影節(jié)點(diǎn)分布集中化的概率稀疏隨機(jī)矩陣。概率稀疏隨機(jī)矩陣既減少了參與測(cè)量值計(jì)算的有效投影節(jié)點(diǎn)個(gè)數(shù)，又實(shí)現(xiàn)了有效投影節(jié)點(diǎn)的分布集中化，從而進(jìn)一步節(jié)約了數(shù)據(jù)收集的通信能耗。在此基礎(chǔ)上，為提高網(wǎng)絡(luò)數(shù)據(jù)重構(gòu)精度，本文還提出了一種適用于概率稀疏隨機(jī)矩陣優(yōu)化的測(cè)量矩陣優(yōu)化算法。

2 問題描述

在WSNs數(shù)據(jù)采集應(yīng)用中，需要將監(jiān)控區(qū)域節(jié)點(diǎn)的采集數(shù)據(jù)傳輸至sink節(jié)點(diǎn)。設(shè)監(jiān)控區(qū)域有N個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)均采集得到一個(gè)數(shù)據(jù)值，那么整個(gè)網(wǎng)絡(luò)感知得到的數(shù)據(jù)可用表示。設(shè)x可在的稀疏字典D下進(jìn)行稀疏表示，即為變換系數(shù)構(gòu)成的向量，若，則稱θ的稀疏度為K,表示信號(hào)的零范數(shù)，即信號(hào)值不為零的個(gè)數(shù)。

若整個(gè)網(wǎng)絡(luò)共有M條路由，那么sink節(jié)點(diǎn)可獲得M個(gè)測(cè)量值，寫成矩陣形式有為測(cè)量值向量，為測(cè)量矩陣。

圖1 壓縮數(shù)據(jù)收集示意圖

由上述模型可知，若采用稠密測(cè)量矩陣作為網(wǎng)絡(luò)數(shù)據(jù)收集的測(cè)量矩陣會(huì)帶來密集觀測(cè)問題。為避免密集觀測(cè)問題，文獻(xiàn)[8]提出采用稀疏隨機(jī)矩陣作為測(cè)量矩陣對(duì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行測(cè)量，然而隨機(jī)選擇的有效投影節(jié)點(diǎn)分布非常分散，獲取投影值仍需要很大的通信開銷。

一般地，適用于壓縮數(shù)據(jù)收集的測(cè)量矩陣應(yīng)滿足以下兩個(gè)條件：(1)測(cè)量矩陣具有良好的稀疏性；(2)測(cè)量矩陣可以讓同一測(cè)量值對(duì)應(yīng)的有效投影節(jié)點(diǎn)分布盡可能集中。在下節(jié)中將同時(shí)考慮以上兩個(gè)條件，設(shè)計(jì)一種適用于壓縮數(shù)據(jù)收集的測(cè)量矩陣。

3 概率稀疏隨機(jī)矩陣設(shè)計(jì)

其中S為測(cè)量矩陣的稀疏率，即矩陣非零元素個(gè)數(shù)占總元素個(gè)數(shù)的比例。

概率稀疏隨機(jī)矩陣的設(shè)計(jì)思想是：在距離矩陣R已知條件下，分別以各節(jié)點(diǎn)作為路徑開啟節(jié)點(diǎn)，以節(jié)點(diǎn)間距離作為參數(shù)來控制節(jié)點(diǎn)當(dāng)選為有效投影節(jié)點(diǎn)的概率，設(shè)計(jì)一個(gè)既具有稀疏性又能讓有效投影節(jié)點(diǎn)分布集中化的測(cè)量矩陣。該矩陣構(gòu)建算法描述如下：

(1)分別以各節(jié)點(diǎn)作為路徑開啟節(jié)點(diǎn)，計(jì)算其它節(jié)點(diǎn)當(dāng)選為有效投影節(jié)點(diǎn)的概率。當(dāng)節(jié)點(diǎn)i為路徑開啟節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)j當(dāng)選為有效投影節(jié)點(diǎn)的概率為

其中iσ為常數(shù)。

依次以各節(jié)點(diǎn)作為路徑開啟節(jié)點(diǎn)，計(jì)算其它節(jié)點(diǎn)當(dāng)選有效投影節(jié)點(diǎn)的概率。將節(jié)點(diǎn)當(dāng)選有效投影節(jié)點(diǎn)的概率寫成矩陣形式：

那么矩陣Φ稱為概率稀疏隨機(jī)矩陣。

(3)上述得到的概率稀疏隨機(jī)矩陣Φ有N行，為實(shí)現(xiàn)欠采樣，可從Φ中等間隔或隨機(jī)抽取M行構(gòu)成測(cè)量矩陣'Φ。為進(jìn)一步提升該矩陣的性能，可利用測(cè)量矩陣優(yōu)化理論[1113]-對(duì)該矩陣進(jìn)行優(yōu)化，第4節(jié)將給出一種適用于概率稀疏隨機(jī)矩陣優(yōu)化的測(cè)量矩陣優(yōu)化算法。

4 概率稀疏隨機(jī)矩陣優(yōu)化

概率稀疏隨機(jī)矩陣Φ是NN×維的，為實(shí)現(xiàn)信號(hào)的欠采樣，可從中最優(yōu)抽取M行構(gòu)成測(cè)量矩陣。設(shè)為矩陣Φ的行索引集合是矩陣Φ行索引集合的子集，JΦ為Φ中保留集合J對(duì)應(yīng)行構(gòu)成的測(cè)量矩陣，則CS的測(cè)量過程可表示如下：為測(cè)量值向量y的等效字典。設(shè) ()J=G表示對(duì)矩陣列單位化后的矩陣，則稱為Gram矩陣。

在測(cè)量矩陣優(yōu)化理論中，一般采用整體互相干系數(shù)來衡量測(cè)量矩陣和稀疏字典的不相干性。整體互相干系數(shù)定義為 Gram 矩陣非對(duì)角元素的平方和[12]，即：是 Gram矩陣的元素。整體互相干系數(shù)度量了測(cè)量矩陣和稀疏字典的相干性，整體互相干系數(shù)越小，稀疏近似算法的平均恢復(fù)性能越好。為減少整體互相干系數(shù)，可求解式(8)的優(yōu)化問題：表示集合的勢(shì)，即集合中元素的個(gè)數(shù)。

上述優(yōu)化問題是在稀疏字典D和矩陣Φ已知的條件下，求解讓平方和最小的行索引子集合J?？筛鶕?jù)矩陣各行與稀疏字典的相干性，采用迭代方式，每次迭代刪除與稀疏字典相干性最強(qiáng)的行，經(jīng)過NM-次迭代后得到優(yōu)化后的測(cè)量矩陣optΦ，算法具體步驟如下：

(2)尋找刪除該測(cè)量向量可最小化整體互相干系數(shù)的索引tλ；

(3)刪除讓測(cè)量矩陣整體互相干系數(shù)最小化的測(cè)量向量，更新測(cè)量矩陣；

5 節(jié)點(diǎn)分布集中程度分析

證明 采用所有有效投影節(jié)點(diǎn)到路徑開啟節(jié)點(diǎn)的距離之和來度量有效投影節(jié)點(diǎn)分布的集中程度。要證明概率稀疏隨機(jī)矩陣的有效投影節(jié)點(diǎn)的分布更集中，只需證明任意一條路徑，概率隨機(jī)方式選擇的有效投影節(jié)點(diǎn)分布平均集中程度均高于隨機(jī)方式。設(shè)節(jié)點(diǎn)為路徑開啟節(jié)點(diǎn)，計(jì)算其它有效投影節(jié)點(diǎn)到節(jié)點(diǎn)i距離和的期望。

采用隨機(jī)方式時(shí)，該距離和的期望值為

采用概率隨機(jī)方式時(shí)，該距離和的期望值為

由式(4)可知以節(jié)點(diǎn)i作為路徑開啟節(jié)點(diǎn)構(gòu)建的路由有效投影節(jié)點(diǎn)的平均個(gè)數(shù)為，并結(jié)合式(3)可知

將式(11)代入式(10)可得

將式(9)與式(12)相除可得

式(13)當(dāng)且僅當(dāng) 1S= 時(shí)等式成立，即測(cè)量矩陣為稠密矩陣時(shí)，兩種測(cè)量矩陣有效投影節(jié)點(diǎn)的分布集中程度一致。當(dāng)時(shí)，概率稀疏隨機(jī)矩陣的有效投影節(jié)點(diǎn)分布集中程度高于稀疏隨機(jī)矩陣。

證畢

6 實(shí)驗(yàn)仿真

使用和文獻(xiàn)[14]相同的能量模型，發(fā)送數(shù)據(jù)和接收數(shù)據(jù)的無線通信模型分別為

圖2 有效投影節(jié)點(diǎn)的位置分布圖

圖4和圖5分別比較了不同稀疏矩陣完成一次壓縮數(shù)據(jù)收集的全局能耗和重建誤差。固定監(jiān)控區(qū)域節(jié)點(diǎn)個(gè)數(shù)為，稀疏系數(shù)向量長(zhǎng)度為L(zhǎng)=，稀疏度為，測(cè)量次數(shù)為，測(cè)量矩陣的稀疏率S由 0.05逐漸增加到 1，步長(zhǎng)為0.05。對(duì)每個(gè)稀疏率S取值，重復(fù)實(shí)驗(yàn)1000次，計(jì)算不同稀疏矩陣完成一次壓縮數(shù)據(jù)收集的平均全局能耗和平均重建誤差。由圖4可以看出，與稀疏隨機(jī)矩陣和稀疏Toeplitz測(cè)量矩陣相比，當(dāng)測(cè)量矩陣稀疏率小于0.55時(shí)，采用概率稀疏隨機(jī)矩陣作為壓縮數(shù)據(jù)收集的測(cè)量矩陣可降低約 15%~30%的通信能耗。這是因?yàn)榕c其它兩種矩陣相比，概率稀疏隨機(jī)矩陣的有效投影節(jié)點(diǎn)的分布最集中，因此數(shù)據(jù)傳輸所消耗的能量最少。由圖5可以看出，在測(cè)量矩陣稀疏率一定的情況下，概率稀疏隨機(jī)矩陣的重建誤差與稀疏隨機(jī)矩陣和稀疏 Toeplitz測(cè)量矩陣相仿，但是概率稀疏隨機(jī)矩陣經(jīng)過優(yōu)化后，重建誤差小于稀疏隨機(jī)矩陣和稀疏Toeplitz測(cè)量矩陣。

7 結(jié)束語

采用稀疏矩陣作為測(cè)量矩陣可顯著減少獲取測(cè)量值的通信開銷。因此，研究性能優(yōu)異的稀疏測(cè)量矩陣對(duì)推動(dòng)CS理論在WSNs中的應(yīng)用具有重要意義。結(jié)合WSNs的分布式特點(diǎn)，本文設(shè)計(jì)了一種適用于WSNs壓縮數(shù)據(jù)收集的概率稀疏隨機(jī)矩陣，該矩陣既減少了計(jì)算投影值的有效投影節(jié)點(diǎn)個(gè)數(shù)，又能讓有效投影節(jié)點(diǎn)分布集中化，顯著減少了獲取投影的通信代價(jià)，有效延長(zhǎng)了網(wǎng)絡(luò)的生命周期。

圖3 重建成功率比較

圖4 能耗隨測(cè)量矩陣稀疏率的變化情況

圖5 重建誤差隨測(cè)量矩陣稀疏率的變化情況

[1] Akyidiz L F, Su W, Sankarasubramaniam Y, et al.. A survey on sensor networks[J]. IEEE Communications Magazine,2002, 40(8): 102-114.

[2] 宋欣, 王翠榮. 基于線性回歸的無線傳感器網(wǎng)絡(luò)分布式數(shù)據(jù)采集優(yōu)化策略[J]. 計(jì)算機(jī)學(xué)報(bào), 2012, 35(3): 568-580.Song Xin and Wang Cui-rong. Linear regerssion based distributed data gathering optimization strategy for wireless sensor networks[J]. Chinese Journal of Computers, 2012,35(3): 568-580.

[3] Quer G, Masiero R, and Munaretto D. On the interplay between routing and signal representation for compressive sensing in wireless sensor networks[C]. Proceedings of Information Theory and Applications Workshop, San Diego,2009: 206-215.

[4] Donoho D L. Compressed sensing [J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306.

[5] 許志強(qiáng). 壓縮感知[J]. 中國(guó)科學(xué): 數(shù)學(xué), 2012, 42(9): 865-877.Xu Zhi-qiang. Compressed sensing: a survey[J]. Scientia Sinica Mathematica, 2012, 42(9): 865-877.

[6] Luo C, Wu F, Sun J, et al.. Compressive data gathering for large-scale wireless sensor networks[C]. Proceedings of the 15th Annual International Conference on Mobile Computing and Networking, Beijing, 2009: 145-156.

[7] Luo J, Xiang L, and Rosenberg C. Does compressed sensing improve the throughput of wireless sensor networks?[C].Proceedings of IEEE International Conference on Communications, Cape Town, 2010: 1-6.

[8] Wang W, Garofalakis M, and Ramchandran K. Distributed sparse random projections for refinable approximation[C].Proceedings of the 6th International Symposium on Information Processing in Sensor Networks, Cambridge, 2007:331-339.

[9] 張成, 楊海蓉, 韋穗. 基于隨機(jī)間距稀疏Toeplitz測(cè)量矩陣的壓縮傳感[J]. 自動(dòng)化學(xué)報(bào), 2012, 38(8): 1362-1369.Zhang Cheny, Yang Hai-rong, and Wei Hui. Compressive sensing based on deterministic sparse Toeplitz measurement matrices with random pitch[J]. Acta Automatica Sinica, 2012,38(8): 1362-1369.

[10] Lee S, Pattem S, Sathiamoorthy M, et al.. Spatially-localized compressed sensing and routing in multi-hop sensor networks[C]. Proceedings of the Third International Conference on Geosensor Networks, Oxford, 2009: 11-20.

[11] Elad M. Optimized projections for compressed sensing[J].IEEE Transactions on Signal Processing, 2007, 55(12):5695-5702.

[12] Duarte-Carvajalino J M and Sapiro G. Learning to sense sparse signals: simultaneous sensing matrix and sparsifying dictionary optimization[J]. IEEE Transactions on Image Processing, 2009, 18(7): 1395-1408.

[13] Abolghasemi V, Ferdowsi S, and SaeidSanei. A gradientbased alternating minimization approach for optimization of the measurement matrix in compressive sensing[J]. IET Transactions Signal Processing, 2012, 92(4): 999-1009.

[14] Heinzelman W, Chandrakasan A P, and Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communcations, 2002, 1(4): 660-670.