張美燕，蔡文郁

（1.浙江水利水電學(xué)院電氣工程系，杭州310018；2.杭州電子科技大學(xué)電子信息學(xué)院，杭州310018）

融合K均值分簇MST路由的無線傳感網(wǎng)壓縮采樣技術(shù)*

張美燕1，蔡文郁2*

（1.浙江水利水電學(xué)院電氣工程系，杭州310018；2.杭州電子科技大學(xué)電子信息學(xué)院，杭州310018）

考慮無線傳感網(wǎng)中數(shù)據(jù)采集特點(diǎn)和能量約束性，將分簇路由策略融合到壓縮感知采樣中，提出了一種融合K均值分簇MST路由的壓縮采樣算法。算法采用稀疏投影矩陣以減小投影矩陣與稀疏基之間的相關(guān)度，利用K均值分簇MST（Minimum Spanning Tree）機(jī)制構(gòu)造數(shù)據(jù)融合樹，在保證數(shù)據(jù)重構(gòu)質(zhì)量的基礎(chǔ)上減少網(wǎng)絡(luò)數(shù)據(jù)傳輸量。仿真結(jié)果表明，算法可以提高網(wǎng)絡(luò)能量使用效率，同時(shí)可以適應(yīng)各種規(guī)模的無線傳感網(wǎng)。

無線傳感網(wǎng)；壓縮感知；自適應(yīng)采樣；最小生成樹；K均值分簇

EEACC:6150Pdoi:10.3969/j.issn.1004-1699.2015.09.023

作為無線傳感網(wǎng)的最重要和最基本的功能，網(wǎng)內(nèi)數(shù)據(jù)采集技術(shù)得到了廣泛研究［1］。由于網(wǎng)內(nèi)傳感數(shù)據(jù)存在著較強(qiáng)的時(shí)空相關(guān)性，直接傳輸原始數(shù)據(jù)顯然并不合適，很多研究采用了傳統(tǒng)的壓縮編碼技術(shù)以盡量減少需要傳輸?shù)臄?shù)據(jù)量。近年來，壓縮感知技術(shù)［2-4］作為一種全新的信息采集與處理的理論框架，立刻引起了研究者的廣泛關(guān)注。壓縮感知借助信號(hào)內(nèi)在的稀疏性或可壓縮性，可從小規(guī)模的線性、非自適應(yīng)的測(cè)量中通過非線性優(yōu)化的方法重構(gòu)信息，在降低采樣頻率的同時(shí)還能實(shí)現(xiàn)采樣與壓縮同步并行。壓縮感知理論表明:只要信號(hào)在某個(gè)變換域是稀疏的或可壓縮表示的，就可用與稀疏基不相關(guān)的測(cè)量矩陣將該高維信號(hào)投影到低維空間，通過求解一個(gè)非線性最優(yōu)化問題，可重構(gòu)出原始信號(hào)。壓縮感知為解決傳統(tǒng)Shannon-Nyquist采樣方法面臨的高成本、低效率、信息冗余以及數(shù)據(jù)傳輸?shù)馁Y源浪費(fèi)等問題帶來了新的契機(jī)。最近研究表明，壓縮感知理論充分發(fā)掘了無線傳感網(wǎng)內(nèi)信號(hào)的內(nèi)相關(guān)性和互相關(guān)性，提高了網(wǎng)內(nèi)分布式數(shù)據(jù)采集的重構(gòu)性能和壓縮比。因此，將壓縮感知理論應(yīng)用于無線傳感網(wǎng)，可以用較低速率對(duì)信號(hào)進(jìn)行采樣，同時(shí)并行地對(duì)信號(hào)進(jìn)行壓縮處理，即在采樣的過程中尋找最少的系數(shù)來表示全部信號(hào)，并用適當(dāng)?shù)闹貥?gòu)算法從壓縮數(shù)據(jù)中恢復(fù)原始信號(hào)。

若采用傳統(tǒng)的無線傳感網(wǎng)數(shù)據(jù)收集方法，越接近Sink節(jié)點(diǎn)的節(jié)點(diǎn)需要轉(zhuǎn)發(fā)越多下游節(jié)點(diǎn)的數(shù)據(jù)，形成“hot spot”現(xiàn)象，嚴(yán)重影響網(wǎng)絡(luò)性能。本文結(jié)合無線傳感網(wǎng)的分層最短生成樹（MST）路由技術(shù)與壓縮感知技術(shù)，借鑒混合壓縮感知（Hybrid-CS）的思想，提出一種基于分層最短路徑樹的稀疏隨機(jī)投影算法，通過將數(shù)據(jù)融合樹與壓縮感知技術(shù)相結(jié)合，實(shí)現(xiàn)無線傳感網(wǎng)內(nèi)數(shù)據(jù)的高效采集與傳輸。

1　相關(guān)文獻(xiàn)

壓縮感知理論（CS，Compressed Sensing）［2-4］突破了奈奎斯特均勻采樣定理的限制，信號(hào)的帶寬不再由采樣速率來決定，而是由信息在信號(hào)中的結(jié)構(gòu)和內(nèi)容決定。CS編碼的計(jì)算復(fù)雜度比較低，只需要在某個(gè)隨機(jī)觀測(cè)矩陣上對(duì)信號(hào)進(jìn)行線性投影，就可以得到壓縮之后的觀測(cè)向量，編碼與解碼之間相對(duì)獨(dú)立，在編碼端采用相同的編碼方案，而在解碼端可以采用不同的解碼技術(shù)。因此，CS理論的這些優(yōu)點(diǎn)特別適合資源受限的分層無線傳感網(wǎng)，只要傳感器節(jié)點(diǎn)的數(shù)據(jù)能夠在某些正交基上對(duì)該信號(hào)進(jìn)行稀疏表示，在各個(gè)簇頭節(jié)點(diǎn)運(yùn)行具有較低復(fù)雜度的編碼算法得到觀測(cè)向量，匯聚節(jié)點(diǎn)在收集到節(jié)點(diǎn)感知數(shù)據(jù)的觀測(cè)向量后，運(yùn)行比較復(fù)雜的CS解碼算法進(jìn)行重構(gòu)，這樣傳感器節(jié)點(diǎn)之間不用進(jìn)行數(shù)據(jù)交換也可實(shí)現(xiàn)對(duì)感知數(shù)據(jù)的壓縮及重構(gòu)，明顯地減少了網(wǎng)絡(luò)的開銷。文獻(xiàn)［5］將CS理論應(yīng)用于無線傳感網(wǎng)的數(shù)據(jù)收集，并取得了較為顯著的數(shù)據(jù)壓縮效果。文獻(xiàn)［6-8］將壓縮感知技術(shù)應(yīng)用到大規(guī)模無線多跳傳感器網(wǎng)絡(luò)進(jìn)行分布式數(shù)據(jù)收集，結(jié)果證明該技術(shù)能有效地減少網(wǎng)絡(luò)通信量。文獻(xiàn)［9］提出了CDG （Compressive Data Gathering）方法，通過線性運(yùn)算將N個(gè)傳感器節(jié)點(diǎn)的數(shù)據(jù)從N維空間映射到M（M＜N）維空間，從而減少數(shù)據(jù)傳輸量。文獻(xiàn)［10］更是將壓縮感知應(yīng)用到了傳感數(shù)據(jù)的差錯(cuò)檢測(cè)中。

目前，研究者分別提出了基于簇的數(shù)據(jù)收集協(xié)議［11］、基于鏈的數(shù)據(jù)收集協(xié)議［12］和基于樹的數(shù)據(jù)收集協(xié)議［13-14］，其目標(biāo)是建立一種底層的拓?fù)浣Y(jié)構(gòu)，以有效利用節(jié)點(diǎn)能量資源。然而這些方法都無法克服數(shù)據(jù)收集所形成的“熱區(qū)”現(xiàn)象，即越靠近基站的節(jié)點(diǎn)需要承擔(dān)越多的數(shù)據(jù)轉(zhuǎn)發(fā)量，加快了能量消耗，縮短了網(wǎng)絡(luò)生命周期。分布式壓縮感知DCS［15］將單信號(hào)的壓縮感知擴(kuò)展到信號(hào)群的壓縮采樣，著重研究如何利用信號(hào)內(nèi)相關(guān)性和互相關(guān)性對(duì)多個(gè)信號(hào)進(jìn)行聯(lián)合重構(gòu)，大大減少了觀測(cè)數(shù)量。DCS理論為分布式信號(hào)處理提供了新的方法，但是如何將其擴(kuò)展到各種復(fù)雜的應(yīng)用中仍是一個(gè)難題。文獻(xiàn)［16］提出了融合函數(shù)的方法獲取采樣數(shù)據(jù)，但是融合函數(shù)僅能得到采集數(shù)據(jù)的統(tǒng)計(jì)量，而無法還原原始數(shù)據(jù)。綜上所述，以上方法從不同角度研究了壓縮感知技術(shù)在無線傳感網(wǎng)中的應(yīng)用，但是沒有綜合考慮傳感器網(wǎng)絡(luò)中資源受限節(jié)點(diǎn)的協(xié)作特性與網(wǎng)絡(luò)多跳協(xié)同傳輸特性，距離實(shí)際的應(yīng)用還有較大的距離。最新的文獻(xiàn)［17］提出了一種方法，聯(lián)合考慮隨機(jī)路徑（Random Walk）和壓縮感知的融合，但是缺乏普適性和高效性。

2　基于分布式傳感網(wǎng)的壓縮感知技術(shù)

與傳統(tǒng)的Shannon-Nyquist采樣相比，壓縮采樣以低采樣率直接感知具有稀疏或可壓縮性的對(duì)象，而不是先以高速率進(jìn)行采樣，然后再對(duì)數(shù)據(jù)進(jìn)行壓縮，因此避免了無謂的數(shù)據(jù)采樣，節(jié)省了能耗。在真實(shí)的無線傳感網(wǎng)中，感知數(shù)據(jù)并非是稀疏信號(hào)，但是可以找到一個(gè)合適的表示基ψT，使得其稀疏信號(hào)。壓縮采樣技術(shù)原理如圖1所示，基于分布式壓縮采樣的傳感數(shù)據(jù)高效收集機(jī)制假設(shè)N個(gè)傳感器節(jié)點(diǎn)的感知數(shù)據(jù)X是K稀疏的（K＜＜N）。這個(gè)N維稀疏信號(hào)可以從一個(gè)很小數(shù)目的非自適應(yīng)隨機(jī)線性投影中精確恢復(fù)。由于?1范數(shù)是凸函數(shù)，所以信號(hào)重構(gòu)的最優(yōu)化問題是一個(gè)線性優(yōu)化的問題，可以通過局部最優(yōu)的貪婪迭代算法來解決。

投影后的測(cè)量值向量公式為:

Y=ΦΘ=ΦΨTX=AcsX（1）

其中Φ是觀測(cè)矩陣，Ψ是正交基，Θ是信號(hào)變換后得到的稀疏系數(shù)向量，Acs=ΦΨT。

通過以下L-1范數(shù)能夠高概率地精確重建稀疏向量，從此變成了一個(gè)凸優(yōu)化問題，從而轉(zhuǎn)化為一個(gè)求解線性規(guī)范的問題，可得恢復(fù)被壓縮的信號(hào)公式為:

X*=argzmin‖‖Z1，s.t，Y=AcsZ（2）

圖1　壓縮感知原理示意

如圖2所示的無線多跳鏈路式拓?fù)渚W(wǎng)絡(luò)，可以解釋無線傳感網(wǎng)中基于壓縮采樣的無線多跳數(shù)據(jù)采集機(jī)制，相比較于傳統(tǒng)的無線多跳數(shù)據(jù)傳輸模式，匯聚節(jié)點(diǎn)不是接收單個(gè)節(jié)點(diǎn)的感知數(shù)據(jù)，而是接收所有節(jié)點(diǎn)的感知數(shù)據(jù)的權(quán)值之和。在這種數(shù)據(jù)收集策略下，所有節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包數(shù)量是相同的，從而不會(huì)產(chǎn)生越靠近匯聚節(jié)點(diǎn)的節(jié)點(diǎn)會(huì)優(yōu)先耗費(fèi)完能量的情況。將壓縮感知應(yīng)用于無線傳感網(wǎng)多跳中繼通信的數(shù)學(xué)模型表達(dá)式如式（3）和式（4）所示。

圖2　基于壓縮采樣的無線多跳數(shù)據(jù)采集機(jī)制

基于壓縮感知額數(shù)據(jù)恢復(fù)過程實(shí)質(zhì)上式對(duì)可壓縮信號(hào)所對(duì)應(yīng)的稀疏信號(hào)s進(jìn)行恢復(fù)，而并非直接恢復(fù)感知數(shù)據(jù)x。稀疏信號(hào)s可以被恢復(fù)是因?yàn)槊恳粋€(gè)測(cè)量值yi包含了一部分s的信息，即每一個(gè)壓縮感知的測(cè)量值是稀疏信號(hào)s的一個(gè)線性組合值。然后，x中的每一個(gè)分量也是其對(duì)應(yīng)稀疏信號(hào)s的一個(gè)線性組合。

研究表明，隨機(jī)觀測(cè)矩陣能以很大的概率同時(shí)滿足觀測(cè)矩陣與基矩陣的不相關(guān)性和可重構(gòu)性，因此實(shí)際中一般采用隨機(jī)矩陣進(jìn)行觀測(cè)，有以下定理:給定信號(hào)X∈RN，其稀疏基對(duì)應(yīng)的稀疏序列S=ΨX是K稀疏的，如果測(cè)量值的個(gè)數(shù)M滿足: M≥C·K·log（N/K），其中C為正常數(shù)，則信號(hào)可以被高概率恢復(fù)。根據(jù)上述壓縮感知理論，觀測(cè)值數(shù)目需要大于某個(gè)與稀疏度相關(guān)的最小觀測(cè)值門限，才能精確重構(gòu)原始信息。

3　融合K均值分簇MST路由的壓縮采樣

根據(jù)壓縮感知理論，每個(gè)壓縮感知測(cè)量值是網(wǎng)內(nèi)所有感知數(shù)據(jù)的一個(gè)加權(quán)線性組合值。如第i個(gè)壓縮感知測(cè)量值被表示為。如果測(cè)量矩陣Φ的第i行中的所有元素都為非零，則所有的節(jié)點(diǎn)都需要參與yi的收集。如果每一行只有一個(gè)非零的測(cè)量矩陣，而且單個(gè)測(cè)量值沿著最短路由方式傳輸數(shù)據(jù)，則單個(gè)測(cè)量值的傳輸代價(jià)可以達(dá)到最優(yōu)。如圖3所示。

圖3　基于網(wǎng)絡(luò)分級(jí)傳輸?shù)臄?shù)據(jù)聚集方式

稀疏隨機(jī)投影認(rèn)為對(duì)于可壓縮信號(hào)進(jìn)行少量的線性投影仍然可以獲取該信號(hào)中的絕大部分信息，在稀疏投影過程中，參與單個(gè)測(cè)量值的傳感器節(jié)點(diǎn)數(shù)目從稠密投影中的O（N）降到O（logN）。稀疏隨機(jī)投影矩陣定義為:

其中?ij為第i行第 j列的投影系數(shù)，Prob.為選擇概率，稀疏投影矩陣的稀疏程度由參數(shù)S決定。如果?ij≠0說明節(jié)點(diǎn) j參與到第i次投影過程中，若?ij≠0說明節(jié)點(diǎn) j只負(fù)責(zé)轉(zhuǎn)發(fā)來自其他節(jié)點(diǎn)的數(shù)據(jù)。當(dāng)S=N/（logN）時(shí)，則Φ中每一行有l(wèi)ogN個(gè)非零元素。由此可知，參與每輪數(shù)據(jù)收集的節(jié)點(diǎn)數(shù)至少是O（logN）。樹形網(wǎng)絡(luò)結(jié)構(gòu)中各節(jié)點(diǎn)通過多跳的方式將自己的數(shù)據(jù)發(fā)送到匯聚節(jié)點(diǎn)，但是在基于壓縮感知的數(shù)據(jù)收集過程中采用樹形網(wǎng)絡(luò)結(jié)構(gòu)，則網(wǎng)絡(luò)中所有節(jié)點(diǎn)都要參與單個(gè)測(cè)量值的收集，因此在稀疏隨機(jī)投影中過多的節(jié)點(diǎn)參與會(huì)導(dǎo)致網(wǎng)絡(luò)資源的浪費(fèi)，而簇結(jié)構(gòu)中簇內(nèi)節(jié)點(diǎn)只與簇頭節(jié)點(diǎn)進(jìn)行通信，簇頭與匯聚節(jié)點(diǎn)之間可以通過多跳方式進(jìn)行通信，因此可以減少單個(gè)測(cè)量值收集過程中參與的節(jié)點(diǎn)數(shù)目。如圖4所示。

圖4　基于網(wǎng)絡(luò)分簇結(jié)構(gòu)的數(shù)據(jù)聚集方式

假設(shè)無線傳感器網(wǎng)絡(luò)集合G（V，E），將除了Sink節(jié)點(diǎn)之外的所有其他節(jié)點(diǎn)分為轉(zhuǎn)發(fā)節(jié)點(diǎn)集FS和編碼節(jié)點(diǎn)集CS，轉(zhuǎn)發(fā)節(jié)點(diǎn)集只負(fù)責(zé)轉(zhuǎn)發(fā)數(shù)據(jù)，編碼節(jié)點(diǎn)集在轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)還進(jìn)行CS壓縮，假設(shè)轉(zhuǎn)發(fā)節(jié)點(diǎn)集FS和編碼節(jié)點(diǎn)集CS是節(jié)點(diǎn)集V的完全分割，因此滿足:CS?FS=?，CS?FS=V。

最優(yōu)化目標(biāo)定義為最小化網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)包數(shù)量，優(yōu)化模型如圖5所示，其中）定義為在樹t中的節(jié)點(diǎn)i到節(jié)點(diǎn)j，是否存在這樣一條路徑；）定義為在樹t中的節(jié)點(diǎn)i到節(jié)點(diǎn)j的數(shù)據(jù)流。式（1）保證了只有唯一的一條路徑通往Sink節(jié)點(diǎn)，式（2）保證存在這樣數(shù)據(jù)流向的一個(gè)聚集樹，式（3）表示只有攜帶正值的邊才屬于該聚集樹，式（4）表示每一個(gè)節(jié)點(diǎn)都只有一條路徑可到達(dá)Sink節(jié)點(diǎn)，尋找是一個(gè)NP-Hard問題，接下來將提出基于K均值分簇MST路由的壓縮采樣算法步驟。

圖5　基于壓縮感知的優(yōu)化采樣模型

本文提出算法的具體步驟如下:

①初始化，已知網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)G（V，E），設(shè)置CS=?，F(xiàn)S=V。

②利用K均值分簇MST路由傳輸方法建立聚類內(nèi)數(shù)據(jù)最小生成樹。

③對(duì)每個(gè)K均值聚類ζ內(nèi)的節(jié)點(diǎn)，重復(fù)如下同樣的操作過程:選舉剩余能量最多的節(jié)點(diǎn)作為聚類中的簇頭節(jié)點(diǎn)；根據(jù)式（5）獲取投影矩陣Φ=［φ1φ2···φn］T，將矢量φi（1≤i≤m）中非零值所對(duì)應(yīng)的節(jié)點(diǎn)加入編碼節(jié)點(diǎn)集CSζ，零值所對(duì)應(yīng)的節(jié)點(diǎn)加入轉(zhuǎn)發(fā)節(jié)點(diǎn)集FSζ；對(duì)于編碼節(jié)點(diǎn)集CSζ中的每個(gè)節(jié)點(diǎn)都設(shè)置最小生成樹路由傳輸路徑；根據(jù)式（3）沿著最小生成樹進(jìn)行數(shù)據(jù)收集:葉子節(jié)點(diǎn)將其感知的數(shù)據(jù)乘上權(quán)值發(fā)送給它的父節(jié)點(diǎn)，父節(jié)點(diǎn)負(fù)責(zé)收集所有直接子節(jié)點(diǎn)發(fā)來的數(shù)據(jù)并將收集齊的數(shù)據(jù)和自己感知數(shù)據(jù)的權(quán)值累加再發(fā)送給其父節(jié)點(diǎn)，整個(gè)收集過程以此類推。

④每個(gè)聚類的簇頭節(jié)點(diǎn)CHζ直接將數(shù)據(jù)傳輸?shù)絊ink節(jié)點(diǎn)。

⑤Sink節(jié)點(diǎn)根據(jù)常規(guī)的正交匹配追蹤（Orthogonal Matching Pursuit，OMP）方法進(jìn)行重構(gòu)。OMP是以貪婪迭代的方法選擇Φ的列，使得在每次迭代中所選擇的列與當(dāng)前的冗余向量最大程度地相關(guān)，從測(cè)量向量中減去相關(guān)部分并反復(fù)迭代，直到迭代次數(shù)達(dá)到稀疏度K，強(qiáng)制迭代停止。

4　仿真結(jié)果

本文仿真場(chǎng)景如下:Node=100/200/300個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布在100×100區(qū)域內(nèi)，Sink節(jié)點(diǎn)位于區(qū)域中心（50，50）坐標(biāo)位置，傳感器節(jié)點(diǎn)半徑為15，每次數(shù)據(jù)發(fā)送長(zhǎng)度為512 bit，每輪隨機(jī)選擇比例為20%數(shù)量的節(jié)點(diǎn)進(jìn)行數(shù)據(jù)采樣傳輸。壓縮效率定義為原始數(shù)據(jù)的矢量維度N與壓縮觀測(cè)矢量的維度M之比:γ=N/M，壓縮效率越大說明壓縮率越高。為了降低傳感器節(jié)點(diǎn)任意分布對(duì)網(wǎng)絡(luò)性能的影響，實(shí)驗(yàn)結(jié)果為50次仿真實(shí)驗(yàn)的平均值，每次仿真中網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)隨機(jī)生成，運(yùn)行輪數(shù)Round=100-200。如圖6（a）所示，利用K均值分簇算法將網(wǎng)絡(luò)分為三個(gè)簇。壓縮感知的OMP重構(gòu)算法采用了文獻(xiàn)MATLAB中的CVX工具箱［18］。仿真采用的節(jié)點(diǎn)能量模型如下:假設(shè)每個(gè)傳感器節(jié)點(diǎn)的初始能量都為1 J，能量消耗模型采用常用的平方消耗模型，仿真的具體參數(shù)如下公式所示。

圖6　網(wǎng)絡(luò)拓?fù)銴均值聚類結(jié)果圖

由于平面區(qū)域內(nèi)的K均值聚類可以近似包含中心節(jié)點(diǎn)，因此可以將Sink節(jié)點(diǎn)作為每個(gè)聚類的匯聚節(jié)點(diǎn)，K均值聚類后實(shí)現(xiàn)了基于最小生成樹的數(shù)據(jù)傳輸樹形成，K均值聚類最小生成樹路由數(shù)據(jù)收集方式如圖6（b）所示。不同數(shù)據(jù)采樣長(zhǎng)度下壓縮感知數(shù)據(jù)重構(gòu)效果如圖7和圖8所示，N取值為300，K取值為5/10/15/20/25，M取值為50/100/150/200，可見均方根誤差RMSE較小，并且隨著稀疏度的提高，均方根誤差會(huì)逐漸增大。根據(jù)前述壓縮感知理論，觀測(cè)值數(shù)目需要大于某個(gè)與稀疏度相關(guān)的最小觀測(cè)值門限，才能精確重構(gòu)原始信息，所以可以發(fā)現(xiàn)當(dāng)M值較小時(shí)，重構(gòu)效果較差。

圖7　壓縮感知數(shù)據(jù)重構(gòu)效果（N=300）

圖8　壓縮感知重構(gòu)均方根誤差比較（N=300）

圖9　網(wǎng)絡(luò)能量分布比較（Node=200，Round=200）

圖9比較了直接匯聚傳輸和壓縮感知傳輸兩種情況下網(wǎng)絡(luò)能量耗費(fèi)分布，共有200個(gè)節(jié)點(diǎn)，仿真輪數(shù)為200輪。橫坐標(biāo)為剩余能量率，定義為歸一化能量率，即剩余能量與初始能量比值?？v坐標(biāo)為節(jié)點(diǎn)個(gè)數(shù)。剩余能量率高的節(jié)點(diǎn)越多說明網(wǎng)絡(luò)能量效率越高，因此可見采用本文提出的壓縮采樣傳輸方式可以提高一部分的能量使用效率。

5　結(jié)語

壓縮感知理論突破了奈奎斯特均勻采樣定理的限制，信號(hào)的帶寬不再由采樣速率來決定，而是由信息在信號(hào)中的結(jié)構(gòu)和內(nèi)容決定。壓縮感知理論的這些優(yōu)點(diǎn)特別適合資源受限的分層結(jié)構(gòu)的無線傳感網(wǎng)，采集終端采用了復(fù)雜度較低的稀疏采樣后，匯聚節(jié)點(diǎn)運(yùn)行比較復(fù)雜的解碼算法進(jìn)行可接受重構(gòu)，這樣傳感器節(jié)點(diǎn)之間不用進(jìn)行數(shù)據(jù)交換也可實(shí)現(xiàn)對(duì)感知數(shù)據(jù)的壓縮及重構(gòu)。本文基于K均值分簇本地最小生成樹路由的數(shù)據(jù)傳輸方式，實(shí)現(xiàn)了壓縮感知數(shù)據(jù)采樣與重構(gòu)，仿真結(jié)果表明本文提出的算法明顯地減少了網(wǎng)絡(luò)的開銷。下一步工作將研究無線多跳中繼環(huán)境中普適性更高的數(shù)據(jù)采樣與傳輸方案。

［1］ Qian Zhihong，Wang Yijun.Internet of Things-Oriented Wireless Sensor Networks Review［J］.Journal of Electronics&Information Technology，2013，35（1）:215-227.

［2］ 楊海蓉，張成，丁大為，等.壓縮傳感理論與重構(gòu)算法［J］.電子學(xué)報(bào)，2011，39（1）:142-148.

［3］ Davenport M A，Duarte M F，Eldar Y C，et al.Introduction to Compressed Sensing.Compressed Sensing:Theory and Applications ［M］.Cambridge:Cambridge University Press，2012.

［4］ Luo C，Wu F，Sun J，et al.Efficient Measurement Generation and Pervasive Sparsity for Compressive Data Gathering［J］.IEEE Transactions on Wireless Communications，2010，9（12）:3728-3738.

［5］ Tang Yu，Zhang Bowu，Jing Tao，et al.Robust Compressive Data Gathering in Wireless Sensor Networks［J］.IEEE Transactions on Wireless Communications，2013，12（6）:2754-2761.

［6］ 王泉，張納溫，張金成，等.壓縮感知在無線傳感器網(wǎng)絡(luò)數(shù)據(jù)采集中的應(yīng)用［J］.傳感技術(shù)學(xué)報(bào)，2014，27（11）:1562-1567.

［7］ Wang J，Tang S，Yin B，et al.Data Gathering in Wireless Sensor Networks Through Intelligent Compressive Sensing［C］//Proceedings of IEEE INFOCOM，Orlando，F(xiàn)L，March 25-30，2012:603-611.

［8］ 陳正宇，楊庚，陳蕾，等.基于壓縮感知的WSNs長(zhǎng)生命周期數(shù)據(jù)收集方法［J］.電子與信息學(xué)報(bào)，2014，36（10）:2343-2349.

［9］ Zheng Haifeng，Xiao Shilin，Wang Xinbing，et al.Capacity and Delay Analysis for Data Gathering with Compressive Sensing in Wireless Sensor Networks［J］.IEEE Transactions on Wireless Communications，2013，12（2）:917-927.

［10］Chun T C，Aleksandar I，Wen H.Efficient Computation of Robust Average of Compressive Sensing Data in Wireless Sensor Networks in the Presence of Sensor Faults［J］.IEEE Transactions on Parallel and Distributed Systems，2013，24（8）:1525-1534.

［11］劉亞，劉功亮，康文靜.壓縮感知和LEACH結(jié)合的水下傳感器網(wǎng)絡(luò)信息采集方案［J］.傳感技術(shù)學(xué)報(bào)，2013，26（3）:388-395.

［12］Durmaz Incel O，Ghosh A，Krishnamachari B，et al.Fast Data Collection in Tree-Based Wireless Sensor Networks［J］.IEEE Transactions on Mobile Computing，2012，11（1）:86-99.

［13］Ebrahimi D，Assi C.A Distributed Method for Compressive Data Gathering in Wireless Sensor Networks［J］.IEEE Communications Letters，2014，18（4）:624-627.

［14］黃海平，陳九天，王汝傳，等.無線傳感器網(wǎng)絡(luò)中基于數(shù)據(jù)融合樹的壓縮感知算法［J］.電子與信息學(xué)報(bào)，2014，36（10）:2364-2369.

［15］呂方旭，張金成，石洪君，等.WSN中的分布式壓縮感知［J］.傳感技術(shù)學(xué)報(bào)，2013，26（10）:1446-1452.

［16］Chen Zhengyu，Yang Geng，Chen Lei，et al.Data Aggregation Scheduling with Guaranteed Lifetime and Efficient Latency in Wireless Sensor Networks［J］.China Communications，2012，9 （9）:11-21.

［17］Haifeng Z，F(xiàn)eng Y，Xiaohua T，et al.Data Gathering with Compressive Sensing in Wireless Sensor Networks:A Random Walk Based Approach［J］.IEEE Transactions on Parallel and Distributed Systems，2015，26（1）:35-44.

［18］Grant M，Boyd S.CVX:MATLAB Software for Disciplined Convex Programming［BL/OL］http://cvxr.com/cvx/，2015.

張美燕（1983-），女，講師，從事無線傳感網(wǎng)絡(luò)、新型能源技術(shù)、物聯(lián)網(wǎng)技術(shù)等研究，主持浙江省自然科學(xué)基金1項(xiàng)，浙江省公益性行業(yè)專項(xiàng)1項(xiàng)，浙江省水利廳科技項(xiàng)目1項(xiàng)，參與浙江省廳級(jí)項(xiàng)目多項(xiàng)。近年來發(fā)表論文20余篇，被三大索引收錄近10篇，申請(qǐng)發(fā)明專利和實(shí)用新型專利10余項(xiàng)；

蔡文郁（1979-），男，博士，副教授，主要從事無線通信、物聯(lián)網(wǎng)、無線傳感網(wǎng)及嵌入式技術(shù)研究。主持和參與國(guó)家自然科學(xué)基金2項(xiàng)、浙江省自然科學(xué)基金3項(xiàng)、浙江省公益性行業(yè)專項(xiàng)2項(xiàng)，國(guó)家863計(jì)劃項(xiàng)目2項(xiàng)、國(guó)家海洋局行業(yè)專項(xiàng)1項(xiàng)、浙江省重大科技專項(xiàng)1項(xiàng)，橫向課題10余項(xiàng)。近年來發(fā)表論文40余篇，被SCI/EI收錄20余篇，申請(qǐng)專利及軟著40余項(xiàng)，授權(quán)30余項(xiàng)，dreampp2000@163.com。

Compressed Sensing Technology Combined with K-Means Clustered MST Routing for Wireless Sensor Networks*

ZHANG Meiyan1，CAI Wenyu2*
（1.School of Electrical Engineering，Zhejiang University of Water Resources and Electric Power，Hangzhou 310018，China）2.School of Electronics&Information，Hangzhou Dianzi University，Hangzhou 310018，China）

Considering the special characteristics of data collection and energy constraints of wireless sensor networks，the paper combines clustered routing strategy with compressed sensing data collection method and then proposes a compressed sensing based compressive sampling algorithm with K-Means clustering MST（Minimum Spanning Tree）routing.The proposed algorithm uses the sparse projection matrix in order to reduce the correlation degree value between the projection matrix and sparse matrix so as to reduce the amount of data transmission in the basis to ensure the quality of the data reconstruction by using K-Means clustering MST data fusion tree.The simulation results show that this algorithm can improve the network energy usage efficiency，and also be suitable to all kinds of scale wireless sensor networks.

wireless sensor networks；compressive sensing；adaptive sampling；minimum spanning tree；K-Means clustering

TP393

A

1004-1699（2015）09-1402-06

項(xiàng)目來源:浙江省自然科學(xué)基金項(xiàng)目（LY15F030018，Y16F030018）；國(guó)家自然科學(xué)基金項(xiàng)目（61102067）

2015-04-26修改日期:2015-06-10