融合K均值分簇MST路由的無線傳感網壓縮采樣技術*

張美燕，蔡文郁

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

融合K均值分簇MST路由的無線傳感網壓縮采樣技術*

張美燕1，蔡文郁2*

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

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

無線傳感網；壓縮感知；自適應采樣；最小生成樹；K均值分簇

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

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

若采用傳統的無線傳感網數據收集方法，越接近Sink節點的節點需要轉發越多下游節點的數據，形成“hot spot”現象，嚴重影響網絡性能。本文結合無線傳感網的分層最短生成樹（MST）路由技術與壓縮感知技術，借鑒混合壓縮感知（Hybrid-CS）的思想，提出一種基于分層最短路徑樹的稀疏隨機投影算法，通過將數據融合樹與壓縮感知技術相結合，實現無線傳感網內數據的高效采集與傳輸。

1　相關文獻

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

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

2　基于分布式傳感網的壓縮感知技術

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

投影后的測量值向量公式為:

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

其中Φ是觀測矩陣，Ψ是正交基，Θ是信號變換后得到的稀疏系數向量，Acs=ΦΨT。

通過以下L-1范數能夠高概率地精確重建稀疏向量，從此變成了一個凸優化問題，從而轉化為一個求解線性規范的問題，可得恢復被壓縮的信號公式為:

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

圖1　壓縮感知原理示意

如圖2所示的無線多跳鏈路式拓撲網絡，可以解釋無線傳感網中基于壓縮采樣的無線多跳數據采集機制，相比較于傳統的無線多跳數據傳輸模式，匯聚節點不是接收單個節點的感知數據，而是接收所有節點的感知數據的權值之和。在這種數據收集策略下，所有節點發送的數據包數量是相同的，從而不會產生越靠近匯聚節點的節點會優先耗費完能量的情況。將壓縮感知應用于無線傳感網多跳中繼通信的數學模型表達式如式（3）和式（4）所示。

圖2　基于壓縮采樣的無線多跳數據采集機制

基于壓縮感知額數據恢復過程實質上式對可壓縮信號所對應的稀疏信號s進行恢復，而并非直接恢復感知數據x。稀疏信號s可以被恢復是因為每一個測量值yi包含了一部分s的信息，即每一個壓縮感知的測量值是稀疏信號s的一個線性組合值。然后，x中的每一個分量也是其對應稀疏信號s的一個線性組合。

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

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

根據壓縮感知理論，每個壓縮感知測量值是網內所有感知數據的一個加權線性組合值。如第i個壓縮感知測量值被表示為。如果測量矩陣Φ的第i行中的所有元素都為非零，則所有的節點都需要參與yi的收集。如果每一行只有一個非零的測量矩陣，而且單個測量值沿著最短路由方式傳輸數據，則單個測量值的傳輸代價可以達到最優。如圖3所示。

圖3　基于網絡分級傳輸的數據聚集方式

稀疏隨機投影認為對于可壓縮信號進行少量的線性投影仍然可以獲取該信號中的絕大部分信息，在稀疏投影過程中，參與單個測量值的傳感器節點數目從稠密投影中的O（N）降到O（logN）。稀疏隨機投影矩陣定義為:

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

圖4　基于網絡分簇結構的數據聚集方式

假設無線傳感器網絡集合G（V，E），將除了Sink節點之外的所有其他節點分為轉發節點集FS和編碼節點集CS，轉發節點集只負責轉發數據，編碼節點集在轉發數據時還進行CS壓縮，假設轉發節點集FS和編碼節點集CS是節點集V的完全分割，因此滿足:CS?FS=?，CS?FS=V。

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

圖5　基于壓縮感知的優化采樣模型

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

①初始化，已知網絡拓撲結構G（V，E），設置CS=?，FS=V。

②利用K均值分簇MST路由傳輸方法建立聚類內數據最小生成樹。

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

④每個聚類的簇頭節點CHζ直接將數據傳輸到Sink節點。

⑤Sink節點根據常規的正交匹配追蹤（Orthogonal Matching Pursuit，OMP）方法進行重構。OMP是以貪婪迭代的方法選擇Φ的列，使得在每次迭代中所選擇的列與當前的冗余向量最大程度地相關，從測量向量中減去相關部分并反復迭代，直到迭代次數達到稀疏度K，強制迭代停止。

4　仿真結果

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

圖6　網絡拓撲K均值聚類結果圖

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

圖7　壓縮感知數據重構效果（N=300）

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

圖9　網絡能量分布比較（Node=200，Round=200）

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

5　結語

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

［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］ 楊海蓉，張成，丁大為，等.壓縮傳感理論與重構算法［J］.電子學報，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］ 王泉，張納溫，張金成，等.壓縮感知在無線傳感器網絡數據采集中的應用［J］.傳感技術學報，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，FL，March 25-30，2012:603-611.

［8］ 陳正宇，楊庚，陳蕾，等.基于壓縮感知的WSNs長生命周期數據收集方法［J］.電子與信息學報，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結合的水下傳感器網絡信息采集方案［J］.傳感技術學報，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］黃海平，陳九天，王汝傳，等.無線傳感器網絡中基于數據融合樹的壓縮感知算法［J］.電子與信息學報，2014，36（10）:2364-2369.

［15］呂方旭，張金成，石洪君，等.WSN中的分布式壓縮感知［J］.傳感技術學報，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，Feng 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-），女，講師，從事無線傳感網絡、新型能源技術、物聯網技術等研究，主持浙江省自然科學基金1項，浙江省公益性行業專項1項，浙江省水利廳科技項目1項，參與浙江省廳級項目多項。近年來發表論文20余篇，被三大索引收錄近10篇，申請發明專利和實用新型專利10余項；

蔡文郁（1979-），男，博士，副教授，主要從事無線通信、物聯網、無線傳感網及嵌入式技術研究。主持和參與國家自然科學基金2項、浙江省自然科學基金3項、浙江省公益性行業專項2項，國家863計劃項目2項、國家海洋局行業專項1項、浙江省重大科技專項1項，橫向課題10余項。近年來發表論文40余篇，被SCI/EI收錄20余篇，申請專利及軟著40余項，授權30余項，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

項目來源:浙江省自然科學基金項目（LY15F030018，Y16F030018）；國家自然科學基金項目（61102067）

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