WSN中基于壓縮感知的高能效數據收集方案

李鵬 王建新 丁長松

WSN中基于壓縮感知的高能效數據收集方案

李鵬1,2王建新1丁長松2

可靠高效的數據收集是無線傳感器網絡(Wireless sensor networks,WSN)應用中的關鍵問題.然而,由于無線通信鏈路的高失效率、節點資源受限以及環境惡劣等原因,網絡容易發生丟包問題,使得現有的數據收集方法無法同時滿足高精度和低能耗的要求.為此,本文提出了一種基于壓縮感知的高能效數據收集方案.該方案主要分為節點上的數據處理和數據收集路徑優化兩個步驟.首先設計了基于指數核函數的稀疏矩陣來對感知數據進行稀疏化處理,然后綜合考慮了數據的傳輸能耗和可靠性等因素,采用分塊矩陣的思路,將單位矩陣和準循環低密度奇偶校驗(Low density parity check,LDPC)碼的校驗矩陣相結合構造了測量矩陣,并證明了它與稀疏矩陣之間滿足限制等距性質(Restricted isometry property,RIP).最后,將數據收集路徑優化問題建模為哈密爾頓回路問題,并提出了基于樹分解的路徑優化算法進行求解.仿真結果表明,在網絡存在丟包的情況下,本文方案仍然能夠保證數據收集的高精確度,相比于其他數據收集方案而言,本文方案在數據重構誤差和能耗方面的性能更優.

無線傳感器網絡,數據收集,壓縮感知,樹分解,重構誤差,能耗

無線傳感器網絡 (Wireless sensor networks, WSN)[1]是由一組傳感器節點構成的無線自組織網絡,它實時感知、采集各種被監控對象的數據加以分析處理[2],然后將處理結果發送到Sink上,Sink再通過互聯網或衛星網絡等發送數據到達管理節點,從而為網絡決策提供支持.對于WSN中的任何應用而言,都要求各個節點準確無誤地將自身的感知數據發送到Sink節點上,即要保證數據收集的可靠性.但由于WSN通常部署在露天環境中,容易受到外部因素的影響以及節點自身資源的限制,網絡的運行是不穩定的,經常存在由于節點間通信鏈路中斷或節點死亡導致的數據傳輸丟包現象,因此,如何保證數據收集的可靠性成為WSN面臨的一項主要挑戰.已有研究表明[3?4],為了應對網絡通信不可靠而發生的多次重傳將額外耗費節點的能量,從而使得網絡的真實性能遠遠達不到預期.現有的可靠傳輸方法主要包括:重傳機制、前向糾錯機制以及多路徑傳輸等,這些方法存在著延時較高、能耗較大的缺點.例如,傳感器節點之間數據傳輸的丟包率最高可達30%[5],如果節點經過5跳能將自身的數據傳輸至Sink,則傳輸的成功率大約為16.8%.此時,為了保證數據傳至Sink的可靠性達到90%以上,則每跳節點至少需要重傳2次以上,即節點的能耗要比預先估計至少增大2倍.為此,本文基于壓縮感知理論[6],設計了一種高能效的數據收集方案,在保證數據收集可靠性的前提下,盡可能地延長網絡壽命.

1 相關工作

無線傳感器網絡的數據收集可靠性問題是目前的研究熱點.Wu等[7]提出一種基于冗余的方法用于實現數據收集的高可靠性和低延時,它采用網絡編碼的思想來改善數據包的冗余度,并能根據應用需求和鏈路丟失率自適應地變化數據包的冗余水平,以滿足端到端的延時要求.然而,該方法中節點需要傳輸的冗余數據量較大,導致了較高的通信能耗. Joo等[8]提出基于內網數據融合的無線廣播策略來保證數據傳輸的可靠性,該文利用無線媒介的多樣性來應對數據丟包現象,避免了采用重傳策略所導致的高延時.然而,該方法的一個主要問題是存在多節點隨機競爭信道所導致的數據包沖突.文獻[9]針對網絡中由于節點失效或故障導致的頻繁丟包現象,綜合考慮了節點能耗、數據收集延時和數據收集率來建模數據收集可靠性問題,然后提出了基于Reed-solomon(RS)編碼的數據收集策略,它以較低的能耗獲得了可使節點能耗最優的重傳參數和數據包編碼數目,可在保證數據收集質量的同時,使網絡能耗最小.然而,該方法在RS編碼過程中需要多個節點間的信息交換,采用窮舉法進行求解,使得算法的復雜性較高,不適用于大規模無線傳感器網絡.此外,文獻[10]提出一種基于壓縮感知和糾刪碼的數據收集算法(Compressive sensing erasure encoding,CSEC),首先基于偽隨機采樣策略構造得到初始的測量矩陣,然后將二進制刪除信道建模為丟失概率為p的貝努利分布,最后基于信道丟失概率自適應地增加測量矩陣的行數,即采用過采樣來實現對節點數據的投影操作,從而保證即使投影值的傳輸出現丟失也能在Sink處精確地恢復出原始數據.但是,隨著網絡規模的增加,CSEC方案仍然需要采集較多的數據才能保證數據重構質量,導致了較大的能耗,使得利用壓縮感知進行數據收集的優勢無從體現.文獻[11]分析了CDG算法[12]在網絡中存在丟包情形下無法有效實現數據收集的不足,設計了一種基于最稀疏隨機調度的數據收集方案(Sparsest random scheduling,SRS),該方案不僅降低了數據傳輸開銷,且在鏈路丟包率達到15%的情況下仍然能夠保證精確的數據收集性能.但是, SRS方案還不夠完善,它主要利用地理位置相近的節點間感知數據的相關性來保證數據收集精度,沒有考慮節點感知數據的時間相關性對于數據收集質量的影響.因此該方案容易受到網絡拓撲結構變化的影響,其應用的局限性較大.為了彌補以上方法的缺陷,本文提出了一種基于壓縮感知的高能效數據收集方案,文中首先通過稀疏矩陣和測量矩陣的設計保證節點上數據采集的可靠性,然后通過對數據收集路徑進行優化達到節省網絡能量的目的.

2 問題建模

2.1 系統模型

設1個Sink節點和N個傳感器節點被隨機地部署在一個大小為N×N平方米的監測區域中.所有節點之間構成一個動態連通的無向圖G=(V, E),其中V是傳感器節點集合,V={V1,V2,···, VN},|V|=N+1;E是圖中邊的集合,如果任意的兩個節點Vi和Vj能夠相互通信,則有(Vi,Vj)∈E.節點無需知曉自身的地理位置,節點通過向其周圍發送交換1個Hello消息來獲取其鄰居節點的信息.此外,WSN還具有如下的特性:

1)Sink節點和其他所有的傳感器節點在部署后保持靜止不動,傳感器節點的傳輸半徑相同.網絡中存在由于節點間通信鏈路中斷或節點失效所導致的傳輸丟包現象,且無法預測丟包發生在哪些傳感器節點上.

2)傳感器節點之間的感知數據具有時空相關性.采用DEBUC協議[13]對網絡進行分簇,簇內各節點基于壓縮感知理論對感知數據進行采樣并將其發送到各自的簇頭.

3)節點的初始能量是異構的,而且不能補充,網絡中節點采用的能量消耗模型如下:

其中,Etr和Ere分別為傳輸電路和接收電路消耗的能量,Eamp為多路衰減模型的功率放大系數,d表示源節點到目標節點的距離,packetsize為包的大小.所有節點采用相同的發射功率和接收功率.

2.2 相關定義

為了方便描述,給出本文用到的相關定義.

定義 1.限制等距性質(Restricted isometry property,RIP)[6].對于任意的信號x∈Σk(Σk表示k稀疏向量集合),如果存在常數δk∈(0,1),有下式成立:

則稱矩陣φ滿足k階RIP性質.

定義 2.圖的樹分解[14].對于任意一個無向圖G(V,E)和樹T,設?=(?i)i∈V(T)表示頂點集(?i)?V(G)的包,圖G的樹分解可由樹T和T的每一個節點關聯的子集構成,即Γ=(T,?).當且僅當T和?滿足以下三個條件:

1)頂點覆蓋:V(G)=∪i∈V(T)Vi;

2)邊覆蓋:對于任意的e∈E(G),總是存在一個節點i∈V(T)使得e的兩端點都在?i中;

3)一致性:如果i2是樹T中連接節點i1和i3的路徑中的節點,則有?i1∩?i3??i2.

定義3.亞高斯分布[15]給定任意的隨機變量ω,如果存在一個常數c＞0,使得對于任意的y∈R,有下面的不等式成立:

則稱該隨機變量ω服從亞高斯分布,即ω～Sub(c2).

2.3 問題描述

WSN一般部署在比較危險或人類很難進入的區域,這些區域中的無線傳感器節點在部署后就無法進行更換,因此如何讓這些節點能夠工作盡可能長的時間顯得至關重要.而采用壓縮感知理論進行數據收集[16?17]能夠降低節點上的數據采集量,實現網絡負載均衡,進而延長網絡生命周期.其基本過程為:首先將所有節點的原始數據表示為N×1的列向量x(n)∈RN.由于網絡數據的時空相關性,x在某一變換基Ψ上可被稀疏化為然后采用一個與Ψ不相關的測量矩陣φ(M×N)對x進行測量,得到M×1的測量值y=φx;最后,當Sink節點收到M 個測量值后,通過求解l1范數最小化問題就能精確地重構出x,如圖1(a)所示.

然而,以上的基于壓縮感知的數據收集過程只適用于理想條件下的WSN,當WSN中存在由于外部干擾或節點失效等原因導致的通信中斷使得數據傳輸發生丟包(見圖1(b))時,現有的方法無法保證數據收集質量.特別當丟包現象發生在網絡中較為重要的節點(例如度數較高的節點、離Sink較近的節點等)上時,則會嚴重影響到數據收集應用的可靠性.為此,本文對網絡丟包條件下的數據收集可靠性問題進行了研究,依據圖1(b)所示的網絡模型,研究在采用壓縮感知理論進行數據收集的過程中如何應對傳輸丟包現象,以及如何對數據收集路徑進行優化,從而在保證數據收集質量的同時,盡可能地延長網絡生命周期.

圖1 基于壓縮感知的數據收集Fig.1 Data gathering based on compressive sensing

3 節點上的數據處理

3.1 稀疏矩陣設計

在壓縮感知理論中,信號表示越稀疏,則信號的恢復就越準確、越可靠.文獻[18]已經證明光滑信號的離散余弦變換、小波變換以及振蕩信號的Gabor變換等都具有足夠的稀疏性,可以通過壓縮感知恢復信號.然而由于傳感器節點的種類繁多,可以采集具有復雜特征的多種信號(例如圖像、聲音、溫度或光照等),固定的正交基有時不足以捕獲信號的多種特征使信號在變換域足夠稀疏,從而影響了信號重構精度.例如,正交小波變換由于缺乏平移旋轉不變性而不能有效壓縮幾何圖像數據.為了彌補現有方法的不足,本文提出一種基于指數核函數的稀疏矩陣來對傳感器網絡中的感知數據進行稀疏化,提高了數據稀疏表示的可靠性.

根據第2.1節所示的節點間的感知數據具有時空相關性這一假設,對于任意兩個傳感器節點i和j而言,本文采用如下的指數核函數κ(xi,xj)來衡量i和j之間感知數據的相關性:

其中,dij表示節點i和節點j之間的距離.σ表示指數核函數的寬度參數,主要用于控制該函數的徑向作用范圍.它的取值可以采用交叉驗證法、梯度下降法或最大似然法等估計得到.指數核函數是高斯核函數的變種,它相對于高斯核函數而言,對于參數的依賴程度較低.對式(4)進行推廣可得,無線傳感器網絡中所有N個節點之間的感知數據相關性可以用矩陣R進行表示:

從式(5)可以看出,R屬于T型矩陣(Toeplitz).根據T型矩陣性質可知,對R做對角化處理可得其中,Γ是對角矩陣,其取值由R的特征值構成.ΨR是一個正交基函數,其取值由R的正交特征向量構成,它能夠滿足壓縮感知理論中的信號稀疏表示要求.因此,本文將ΨR作為稀疏矩陣來對WSN中的所有感知數據進行稀疏化處理,即有x=ΨRs.

3.2 測量矩陣設計

測量矩陣設計是基于壓縮感知的數據收集方法的關鍵步驟.現有的大多數方法[11?12]在測量矩陣的設計過程中關注的重點是降低數據重構誤差和減少數據傳輸開銷,達到了節省節點能耗的目的,但是當網絡中存在傳輸丟包時,這些方法不僅無法保證數據收集質量,而且還會導致能量的浪費.假設圖1(b)為某一個簇內節點組成的數據收集樹,從圖中可以看到,如果葉子節點的感知數據丟失,根據時空相關性可知,這一部分數據可由與其物理位置相近的其他節點感知數據代替.但如果靠近Sink或節點度較大的節點發生丟包,則會嚴重損害數據重構質量,因為這部分節點除了傳輸自身的數據外還需承載其他節點的數據.為此,本文綜合考慮了數據的傳輸能耗和可靠性等因素,對數據收集樹中的葉子節點和非葉子節點分別進行不同的處理來設計測量矩陣,具體過程如下:

1)對于葉子節點而言,它們的數據被直接收集上來并將其發往上游節點.相當于采用一個單位矩陣I對數據收集樹中的所有葉子節點做壓縮采樣.

2)對于非葉子節點而言,則將其信道矩陣看作是測量矩陣的一部分,由于信道編碼校驗矩陣列向量之間滿足線性無關性,且通常可稀疏設計.因此,本文將信道編碼中的校驗矩陣用于壓縮感知的測量矩陣設計中,提出一種基于準循環低密度奇偶校驗(Low density parity check,LDPC碼)[19]的方法來構造測量矩陣φ′.

綜上所述,本文要設計的測量矩陣為(I|φ′).

3.2.1 基于準循環LDPC碼的測量矩陣構造方法

準循環LDPC碼是一種具有稀疏校驗矩陣的分組糾錯碼.它的性能逼近香農限,描述和實現簡單,且可并行操作,適合硬件實現.已有研究表明[19],對于一個任意給定的準循環LDPC碼,如果它的校驗矩陣能實現良好的信道編碼或解碼性能,則將它的校驗矩陣作為基于壓縮感知的信號處理中的測量矩陣,也能實現精確的數據重構.為此,本文根據準循環LDPC碼校驗矩陣的正交性和稀疏性來設計測量矩陣.設SM 是大小為S×S的單位矩陣的1次循環移位陣

則SMi是單位陣的第i次循環移位陣,0≤i＜S. SM∞為零方陣.設MS×NS的矩陣CM為

其中,aij∈{0,1,···,S?1,∞},1≤i≤M,1≤j≤N,則以CM為校驗矩陣的碼字C稱為準循環LDPC碼.對于網絡存在丟包情況下基于壓縮感知的數據收集應用而言,為了保證數據收集質量和節約網絡能耗,測量矩陣的設計必需考慮稀疏性、高糾錯性等因素,而采用準循環LDPC碼來設計測量矩陣恰好能夠滿足這一要求.因此,本文設計了一種基于準循環LDPC碼的測量矩陣構造算法.

算法1.基于準循環LDPC碼的測量矩陣構造

步驟1.構造一個由M×N個大小為S×S的零方陣組成矩陣CM′.

步驟2.隨機選擇ai1和a1j構造移位矩陣SMai1和SMa1j,0≤ai1,a1j＜S,0＜i≤M,1＜j≤N,并用SMai1和SMa1j替代CM′中對應位置的零方陣.

步驟3.隨機選擇aij構造移位矩陣SMaij,0≤aij＜S,并用SMaij替代CM′中對應位置的子矩陣.

步驟4.令

步驟5.將校驗矩陣CM 列向量進行歸一化處理,得到標準正交基.然后抽取M 個線性無關向量填充壓縮感知測量矩陣φ′的前M 個列向量,即:CM2,···,CMM],最后通過前M列的線性組合來表示測量矩陣中的剩余N?M 個列向量,從而得到φ′.

在算法1的步驟4中,當aij≥2時重新選擇aij,這是因為LDPC編碼算法經過2次迭代后, LDPC譯碼無法收斂或收斂速度太慢,因此需要回溯.在步驟5中,CM 的秩為|M|,因此總是可以保證至少存在M 個線性無關向量.此外,算法1的主要開銷在于構造準循環LDPC碼的校驗矩陣CM, CM 屬于線性分組碼,在編碼過程中,CM 需采用高斯消去法轉換為(CM′′|I)形式的矩陣.其中,單位矩陣I是M階,CM′′是(N?M)×M階.因為對CM 進行高斯消去后,其中的元素不再是稀疏的,因此構造校驗矩陣的復雜度為(N?M)M/2,即算法1的復雜度為多項式時間,從節省傳感器節點能耗來看,算法1的開銷是可以接受的.

3.2.2 RIP性質

設Θ=ΨRφ,壓縮感知理論告訴我們,為了精確地重構出原始數據,Θ必須滿足RIP性質.

定理1.對于任意給定的σ∈(0,1),矩陣Θ的每行滿足亞高斯分布,如果M=O(klog(N/k)),則對于任意N維的k稀疏信號s而言,Θ能以較高概率滿足即Θ滿足RIP性質.

因此,當M=O(klog(N/k))時,對于任意N維的k稀疏信號s,Θ以接近于1的概率滿足

3.3 簇內數據收集

綜上所述,簇內數據處理過程為:在采用DEBUC協議對WSN進行分簇后,各個傳感器節點依據第3.1節設計的稀疏矩陣ΨR對感知數據進行稀疏化,依據第3.2節設計的測量矩陣φ決定是直接采樣還是壓縮采樣,然后將自身的數據發往所屬的簇頭(網絡中各個簇都采用類似的處理).最后,整個網絡的感知數據都被集中到簇頭上.

4 數據收集路徑優化

4.1 路徑分析

在節點上的數據處理過程完畢后,下一步則需要為各個簇頭找一條到達Sink的最優路徑,以將各個簇頭上的數據收集上來,并采用壓縮感知重構算法恢復出各個傳感器節點的數據,以完成數據收集過程.能否找到一條最優的路徑來實現簇頭與Sink之間的數據傳輸,對于節省網絡傳輸開銷,延長網絡生命周期至關重要.考慮一個包含6個簇頭CH1,CH2,CH3,CH4,CH5,CH6和一個Sink的無線傳感器網絡,如圖2所示.假設各個簇頭上待傳輸的感知數據為xi,i=1,···,6.各個簇頭的投影向量為φ=[0.1,0.3,0.15,0.25,0.05,0.15],則可以采用路徑Sink?CH1?CH4?CH6?CH5?CH3?CH2?Sink來收集整個網絡中的測量值,這可以通過由Sink向整個網絡廣播該條路徑信息來實現,即有y=0.1x1+0.3x4+0.15x6+ 0.25x5+0.05x3+0.15x2.從圖2可以看出,可以采用多條路徑來收集整個網絡中簇頭的數據到Sink上,在這些路徑中,某些簇頭可能被多次訪問到,額外增加了不必要的數據傳輸開銷,浪費了網絡能量.因此,從節省網絡能耗的角度出發,最優的數據傳輸路徑是:從Sink節點出發,只需訪問各個簇頭一次再回到Sink節點的路徑.如何找到一條這樣的路徑是一個典型的哈密爾頓回路問題[20],屬于NP (Non-deterministic polynomial)困難問題.但對于本文研究的數據收集問題而言,由于待訪問的簇頭數目是有限的,因此我們提出了一種基于樹分解的數據收集路徑優化算法進行解決.

圖2 測量值傳輸Fig.2 Measurement transmission

4.2 優化算法

根據定義2可知,采用樹分解技術可以將任意一個圖中的節點劃分為相互關聯的節點集合.在求解某些較為復雜的圖問題時,只要給定的圖滿足有限樹寬條件,就可以先對圖進行樹分解,然后在其分解得到的各部分節點集上單獨求解,再將各部分求解結果綜合起來即可.自然世界中用圖表示的諸多問題雖然其規模十分龐大,但是通常只有很小的樹寬.例如,一個包含1000個傳感器節點的WSN的樹寬僅等于4[21].因此,利用樹分解可以很容易解決以該網絡為背景的各種復雜問題.在本節研究的問題中,為了節省簇頭上的測量值傳輸能耗,首先對各個簇頭構成的連通圖進行樹分解,然后采用動態規劃來為測量值的傳輸找到一條最優路徑.具體過程如算法2.

算法2.基于樹分解的數據收集路徑優化

輸入.由簇頭組成的無向連通圖G′=(V′,E′).

輸出.測量值傳輸路徑P.

步驟1.Sink發送一個查詢包到各個簇頭,各個簇頭根據Sink的廣播路徑返回各自的測量值.如果只存在唯一的路徑P來傳輸各個簇頭的測量值到Sink則返回P;否則,轉步驟2～4.

步驟2.在圖G′=(V′,E′)中刪除一個節點v′和與v′相連的邊,并在余下的圖中補充邊,使得v′原來的鄰居節點構成一個團.然后,采用最大勢搜索策略[22]逐個消去圖G′=(V′,E′)的所有節點,可以得到圖G′=(V′,E′)的非平凡樹分解Γ=(T,?),樹寬為k.對于每一個節點i∈?,Vi=∪?j,j=i或j是i的孩子節點,Ei=E′∩(Vi×Vi).

步驟3.對每個節點i∈?,計算包含節點i參與的所有回路集合的哈希表HTi(i,θ),θ??i,|HTi|≤2k+1.

步驟4.對于θ??i,在HTi(i,θ)中找到一條最短的回路P使得?i∩P=θ,不存在回路則設置HTi(i,θ)=?∞;返回P.

步驟5.對于所有的節點i∈?,按自下向上的順序計算HTi(i,θ),重復執行步驟2～4,直到?中所有的節點都處理完畢.

5 仿真實驗

為驗證本文方案的性能,采用CitySee系統[23]測得的溫度數據進行仿真實驗.采用Matlab2012作為仿真工具,實驗過程中的主要參數設定如表l所示.

測試所使用的軟硬件環境如下:Inter(R)Core (M)i3-3240 CPU 3.40GHz,500GB硬盤,4.0GB內存,Microsoft Windows 7 Professional.在本文的仿真中,節點間的同步通過物理層和數據鏈路層來實現,其中,數據鏈路層采用IEEE802.15.4標準中的CSMA/CA機制進行空閑偵聽和沖突避免,物理層采用2.4GHz頻段,其數據傳輸率為250kb/s.以重構誤差和能耗作為評價指標,主要對比分析本文方案與SRS方案和CSEC方案在不同場景下的實驗結果.取本文方案50次仿真運行結果的平均值作為最終的實驗結果.其中,數據重構誤差采用下式衡量:

圖3給出了在不同的丟包率(plratio=0,0.05, 0.10,0.15)條件下本文方案的重構誤差情況.可以看到,隨著測量次數的增加,無論丟包率如何,重構誤差的總體趨勢都在下降.其中plratio=0表示理想狀態下的傳感器網絡,此時的網絡不發生丟包,在該情況下本文方案的重構性能最優.另外,仔細觀察不同丟包率下的重構誤差曲線可以發現,當測量次數增加到600次后,不同丟包率下的重構誤差越來越接近,甚至當測量次數達到1000次時,四種情形下的重構誤差基本達到一致,這充分表明了本文方案在網絡發生丟包情況下進行數據收集的可靠性,此時就算網絡發生較大規模的丟包,只要適當地增加測量次數,本文方案仍然能夠保證精確地重構出網絡中各節點的原始數據.

圖3 不同丟包率下的本文方法重構誤差比較Fig.3 Reconstruction error comparison of the proposed scheme with different packet loss rates

圖4給出了本文方案與SRS方案和CSEC方案的重構誤差比較情況.圖4(a)首先給出了測量次數為600次時,不同丟包率plratio下三種方案的重構誤差實驗結果.從圖4(a)可以看到,對于三種數據收集方案而言,其重構誤差都隨著丟包率的增加而增加,但本文方案的重構誤差始終低于SRS方案和CSEC方案,且隨著網絡丟包率的不斷增加,本文方案的性能優勢越來越明顯.特別地,當網絡丟包率為0.15時,就重構誤差而言,本文方案比SRS方案低42.6%,比CSEC方案低31.2%.表明本文方案在網絡存在丟包的情形下仍然能夠實現有效的數據收集,算法的魯棒性較強.究其原因,主要是因為SRS方案采用稀疏隨機調度應對網絡丟包,當網絡規模較大、丟包現象較為頻繁時,該方案的稀疏矩陣會導致部分節點的數據丟失,影響了數據重構精度. CSEC方案則基于信道丟失概率增加測量矩陣的行數應對網絡丟包,并對不同信道模型下的丟包現象做了自適應處理,因此取得了比SRS方案更好的重構性能.本文方法主要針對SRS方案和CSEC方案的不足進行改進,以保證數據收集可靠性這一目標設計測量矩陣,并對數據收集路徑做了一定的優化,因此進一步提高了數據重構精度.圖4(b)給出了丟包率為0.1時,不同測量次數下三種方案的重構誤差實驗結果.從圖4(b)可以看到,在丟包現象存在的前提下,本文方案的重構性能始終優于其他兩種方案.特別地,為了達到數據重構精度為0.03,本文方案需要花費約600次測量,而SRS方案和CSEC方案分別需要花費約800次測量和900次測量,表明本文方案在保證數據收集高可靠性的前提下,比SRS方案和CSEC方案的效率更高,成本更低.

圖5給出了本文方案與SRS方案和CSEC方案的能耗比較情況.從圖5可以看出,網絡能耗與重構誤差成反比關系,因為如果要保證重構誤差盡可能低,節點通常需要采集更多的數據,導致網絡的傳輸開銷加大,能耗增高.但無論縱向對比還是橫向對比,本文方案的能耗或重構誤差都低于SRS方案和CSEC方案.就能耗而言,當應用要求的重構誤差為0.1時,本文方案比SRS方案節能41.6%,比CSEC方案節能56.1%.究其原因,SRS方案將每一個采樣值看作一次測量,始終保持測量矩陣的每一行只有一個非零元素,這種稀疏隨機調度的采樣方式以犧牲一定的重構精度為代價來保持網絡能量. CSEC方案通過增加測量矩陣的采樣次數保證數據收集可靠性,一定程度上導致了冗余采集,因此SRS方案比CSEC方案更加節能.本文方案更進一步,將信道矩陣看作是測量矩陣的一部分,設計了基于準循環LDPC碼的測量矩陣對網絡內的數據進行壓縮收集,減少了節點的傳輸開銷,然后提出一種基于樹分解的數據收集路徑優化算法來收集各個簇頭的數據,保證每個簇頭的數據只被收集一次,因此節省了能量,延長了網絡壽命.

圖4 不同方案的重構誤差比較Fig.4 Reconstruction error comparison of different schemes

圖5 不同方案的能耗比較Fig.5 Energy consumption comparison of different schemes

6 結束語

在無線傳感器網絡的諸多應用中,均要求傳感器節點以無差錯形式將監測數據傳輸至Sink節點.為了滿足應用需求,本文以壓縮感知理論為基礎,提出了一種高能效的數據收集方案.該方案首先通過設計的稀疏矩陣和測量矩陣完成節點上的數據處理,然后采用樹分解和動態規劃的思路優化數據收集路徑.仿真結果表明,在網絡存在丟包的情況下,本文方案仍然能夠保證數據收集的高精確度,相比于其他數據收集方案,本文方案的性能更優.在下一步工作中,我們關注的重點是:1)對本文的網絡場景假設做出改變,以提高數據收集精度和降低網絡能耗為目標,研究移動Sink條件下基于壓縮感知的數據收集方案;2)對真實無線傳感器網絡中節點感知數據的稀疏性進行分析,研究基于壓縮感知的自適應數據重構算法.

1 Guo S,He L,Gu Y,Jiang B,He T.Opportunistic flooding in low-duty-cycle wireless sensor networks with unreliable links.IEEE Transactions on Computers,2014,63(11):2787?2802

2 Li Jian-Zhong,Gao Hong.Survey on sensor network research.Journal of Computer Research and Development, 2015,45(1):1?15 (李建中,高宏.無線傳感器網絡的研究進展.計算機研究與發展, 2015,45(1):1?15)

3 Luo H,Tao H X,Ma H D,Das S K.Data fusion with desired reliability in wireless sensor networks.IEEE Transactions on Parallel and Distributed Systems,2011,22(3):501?513

4 Guo W Z,Hong W,Zhang B,Chen Y Z,Xiong N X.Reliable adaptive data aggregation route strategy for a trade-off between energy and lifetime in WSNs.Sensors,2014,14(9): 16972?16993

5 Rosberg Z,Liu R P,Le Dinh T,Dong Y F,Jha S.Statistical reliability for energy efficient data transport in wireless sensor networks.Wireless Networks,2010,16(7):1913?1927

6 Xie Zhi-Peng,Chen Song-Can.CSMP:compressive sensing matching pursuit based on restricted isometry property.Journal of Computer Research and Development,2015, 49(3):579?588 (謝志鵬,陳松燦.CSMP:基于約束等距的壓縮感知匹配追蹤.計算機研究與發展,2015,49(3):579?588)

7 Wu C,Ji Y S,Xu J,Ohzahata S,Kato T.Coded packets over lossy links:a redundancy-based mechanism for reliable and fast data collection in sensor networks.Computer Networks, 2014,70(10):179?191

8 Joo C,Shroff N B.On the delay performance of in-network aggregation in lossy wireless sensor networks.IEEE/ACM Transactions on Networking,2014,22(2):662?673

9 Chou C T,Ignjatovic A,Hu W.Efficient computation of robust average of compressive sensing data in wireless sensor networks in the presence of sensor faults.IEEE Transactions on Parallel and Distributed Systems,2013,24(8):1525?1534

10 Charbiwala Z,Chakraborty S,Zahedi S,He T,Bisdikian C, Kim Y,Srivastava M B.Compressive oversampling for robust data transmission in sensor networks.In:Proceedings of the 29th IEEE Conference on Computer Communications (INFOCOM).San Diego,CA,USA:IEEE Press,2010.1?9

11 Wu X G,Yang P L,Jung T,Xiong Y,Zheng X.Compressive sensing meets unreliable link:sparsest random scheduling for compressive data gathering in lossy WSNs.In:Proceedings of the 15th ACM International Symposium on Mobile Ad Hoc Networking and Computing(MOBICOM).Maui, HI,USA:ACM Press,2014.13?22

12 Luo C,Wu F,Sun J,Chen C W.Efficient measurement generation and pervasive sparsity for compressive data gathering.IEEE Transactions on Wireless Communications,2010, 9(12):3728?3738

13 Jiang Chang-Jiang,Shi Wei-Ren,Tang Xian-Lun,Wang Ping,Xiang Min.Energy-balanced unequal clustering routing protocol for wireless sensor networks.Journal of Software,2012,23(5):1222?1232 (蔣暢江,石為人,唐賢倫,王平,向敏.能量均衡的無線傳感器網絡非均勻分簇路由協議.軟件學報,2012,23(5):1222?1232)

14 Fafianie S,Bodlaender H L,Nederlof J.Speeding up dynamic programming with representative sets:an experimental evaluation of algorithms for Steiner tree on tree decompositions.Algorithmica,2015,71(3):636?660

15 Ai A,Lapanowski A,Plan Y,Vershynin R.One-bit compressed sensing with non-Gaussian measurements.Linear Algebra and Its Applications,2014,441:222?239

16 Zheng H F,Yang F,Tian X H,Gan X Y,Wang X B,Xiao S L.Data gathering with compressive sensing in wireless sensor networks:a random walk based approach.IEEE Transactions on Parallel and Distributed Systems,2015,26(1): 35?44

17 Ebrahimi D,Assi C.Network coding-aware compressive data gathering for energy-efficient wireless sensor networks. ACM Transactions on Sensor Networks(TOSN),2015, 11(4):1?24

18 Malloy M L,Nowak R D.Near-optimal adaptive compressed sensing.IEEE Transactions on Information Theory,2014, 60(7):4001?4012

19 Liu Dong-Pei,Liu Heng-Zhu,Zhang Bo-Tao.Study on encoding algorithms for QC-LDPC codes with dual-diagonal parity check matrix.Journal of National University of Defense Technology,2014,36(2):156?160 (劉冬培,劉衡竹,張波濤.基于準循環雙對角陣的LDPC碼編碼算法.國防科技大學學報,2014,36(2):156?160)

20 Pang S C,Ma T M,Liu T.An improved ant colony optimization with optimal search library for solving the traveling salesman problem.Journal of Computational and Theoretical Nanoscience,2015,12(7):1440?1444

21 Akiba T,Maehara T,Kawarabayashi K.Network structural analysis via core-tree-decomposition.In:Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,NY,USA: ACM Press,2014.1476?1485

22 Azad A,Bulu?c A,Pothen A.A parallel tree grafting algorithm for maximum cardinality matching in bipartite graphs.In:Proceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium(IPDPS).Hyderabad:IEEE Press,2015.1075?1084

23 Wu X G,Xiong Y,Yang P L,Wan S H,Huang W C. Sparsest random scheduling for compressive data gathering in wireless sensor networks.IEEE Transactions on Wireless Communications,2014,13(10):5867?5877

李 鵬 中南大學信息科學與工程學院博士研究生.主要研究方向為無線傳感器網絡,壓縮感知技術.本文通信作者.

E-mail:lpchs617@csu.edu.cn

(LI Peng Ph.D.candidate at the School of Information Science and Engineering,Central South University.His research interest covers wireless sensor networks and compressive sensing technology.Corresponding author of this paper.)

王建新 中南大學信息科學與工程學院教授.主要研究方向為網絡優化理論,參數計算和生物信息學.

E-mail:jxwang@mail.csu.edu.cn

(WANG Jian-Xin Professor at the School of Information Science and Engineering,Central South University.His research interest covers network optimization theory,parameter calculation,and bioinformatics.)

丁長松 湖南中醫藥大學管理與信息工程學院副教授.主要研究方向為網絡優化理論,云計算.

E-mail:dinghongzhe@yeah.net

(DING Chang-Song Associate professor at the School of Management and Information Engineering,Hunan University of Chinese Medicine. His research interest covers network optimization theory and cloud computing.)

Energy-efficient Data Gathering Scheme Based on Compressive Sensing in Wireless Sensor Networks

LI Peng1,2WANG Jian-Xin1DING Chang-Song2

Reliable and energy-efficient data gathering is a key problem in the application of wireless sensor networks (WSN).However,due to the high failure rate of wireless communication link,limited resource and severe environment, the network easily generates the packet loss problem,which makes the existing data gathering methods fail to meet the requirements of high-accuracy and low-energy consumption at the same time.To solve this problem,an energy-efficient data gathering scheme based on compressive sensing is proposed in this paper.It is divided into the two steps:the data processing of nodes and the data gathering path optimization.The sparse matrix based on the exponential kernel function is firstly designed for sparse processing of sensed data.Then considering both the energy consumption and reliability of data transmission,a measurement matrix is constructed by using the idea of block matrix,which combines the unit matrix and the check matrix of quasi cyclic low density parity check(LDPC)code.It is proved that the restricted isometry property(RIP)is satisfied between the sparse matrix and the measurement matrix.Finally,the data gathering path-optimization problem is modeled as the Hamilton loop problem,and a path optimization algorithm based on the tree decomposition is proposed to solve this problem.Simulation results show that the proposed scheme can still guarantee the high-accuracy of data gathering in the case of packet losses.Compared with the other data gathering schemes,the proposed scheme has better performance in terms of the data reconstruction error and energy consumption.

Wireless sensor networks(WSN),data gathering,compressive sensing,tree decomposition,reconstruction error,energy consumption

李鵬,王建新,丁長松.WSN中基于壓縮感知的高能效數據收集方案.自動化學報,2016,42(11):1648?1656

Li Peng,Wang Jian-Xin,Ding Chang-Song.Energy-efficient data gathering scheme based on compressive sensing in wireless sensor networks.Acta Automatica Sinica,2016,42(11):1648?1656

2016-03-15 錄用日期2016-05-16

Manuscript received March 15,2016;accepted May 16,2016

國家自然科學基金(61472449,61173169,61402542)資助

Supported by National Natural Science Foundation of China (61472449,61173169,61402542)

本文責任編委趙千川

Recommended by Associate Editor ZHAO Qian-Chuan

1.中南大學信息科學與工程學院長沙410083 2.湖南中醫藥大學管理與信息工程學院長沙410208

1. School of Information Science and Engineering,Central South University,Changsha 410083 2.School of Management and Information Engineering,Hunan University of Chinese Medicine,Changsha 410208

DOI 10.16383/j.aas.2016.c160258