張 波劉郁林 王 開 王 嬌

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

1 引言

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

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

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

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

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

2 問題描述

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

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

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

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

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

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

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

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

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

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

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

那么矩陣Φ稱為概率稀疏隨機矩陣。

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

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

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

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

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

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

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

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

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

采用隨機方式時，該距離和的期望值為

采用概率隨機方式時，該距離和的期望值為

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

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

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

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

證畢

6 實驗仿真

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

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

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

7 結(jié)束語

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

圖3 重建成功率比較

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

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

[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]. 計算機學(xué)報, 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] 許志強. 壓縮感知[J]. 中國科學(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] 張成, 楊海蓉, 韋穗. 基于隨機間距稀疏Toeplitz測量矩陣的壓縮傳感[J]. 自動化學(xué)報, 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.