WSN中基于壓縮感知的高能效數(shù)據(jù)收集方案

李鵬 王建新 丁長松

WSN中基于壓縮感知的高能效數(shù)據(jù)收集方案

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

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

無線傳感器網(wǎng)絡(luò),數(shù)據(jù)收集,壓縮感知,樹分解,重構(gòu)誤差,能耗

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

1 相關(guān)工作

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

2 問題建模

2.1 系統(tǒng)模型

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

1)Sink節(jié)點和其他所有的傳感器節(jié)點在部署后保持靜止不動,傳感器節(jié)點的傳輸半徑相同.網(wǎng)絡(luò)中存在由于節(jié)點間通信鏈路中斷或節(jié)點失效所導(dǎo)致的傳輸丟包現(xiàn)象,且無法預(yù)測丟包發(fā)生在哪些傳感器節(jié)點上.

2)傳感器節(jié)點之間的感知數(shù)據(jù)具有時空相關(guān)性.采用DEBUC協(xié)議[13]對網(wǎng)絡(luò)進行分簇,簇內(nèi)各節(jié)點基于壓縮感知理論對感知數(shù)據(jù)進行采樣并將其發(fā)送到各自的簇頭.

3)節(jié)點的初始能量是異構(gòu)的,而且不能補充,網(wǎng)絡(luò)中節(jié)點采用的能量消耗模型如下:

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

2.2 相關(guān)定義

為了方便描述,給出本文用到的相關(guān)定義.

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

則稱矩陣φ滿足k階RIP性質(zhì).

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

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

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

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

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

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

2.3 問題描述

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

然而,以上的基于壓縮感知的數(shù)據(jù)收集過程只適用于理想條件下的WSN,當(dāng)WSN中存在由于外部干擾或節(jié)點失效等原因?qū)е碌耐ㄐ胖袛嗍沟脭?shù)據(jù)傳輸發(fā)生丟包(見圖1(b))時,現(xiàn)有的方法無法保證數(shù)據(jù)收集質(zhì)量.特別當(dāng)丟包現(xiàn)象發(fā)生在網(wǎng)絡(luò)中較為重要的節(jié)點(例如度數(shù)較高的節(jié)點、離Sink較近的節(jié)點等)上時,則會嚴重影響到數(shù)據(jù)收集應(yīng)用的可靠性.為此,本文對網(wǎng)絡(luò)丟包條件下的數(shù)據(jù)收集可靠性問題進行了研究,依據(jù)圖1(b)所示的網(wǎng)絡(luò)模型,研究在采用壓縮感知理論進行數(shù)據(jù)收集的過程中如何應(yīng)對傳輸丟包現(xiàn)象,以及如何對數(shù)據(jù)收集路徑進行優(yōu)化,從而在保證數(shù)據(jù)收集質(zhì)量的同時,盡可能地延長網(wǎng)絡(luò)生命周期.

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

3 節(jié)點上的數(shù)據(jù)處理

3.1 稀疏矩陣設(shè)計

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

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

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

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

3.2 測量矩陣設(shè)計

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

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

2)對于非葉子節(jié)點而言,則將其信道矩陣看作是測量矩陣的一部分,由于信道編碼校驗矩陣列向量之間滿足線性無關(guān)性,且通?？上∈柙O(shè)計.因此,本文將信道編碼中的校驗矩陣用于壓縮感知的測量矩陣設(shè)計中,提出一種基于準循環(huán)低密度奇偶校驗(Low density parity check,LDPC碼)[19]的方法來構(gòu)造測量矩陣φ′.

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

3.2.1 基于準循環(huán)LDPC碼的測量矩陣構(gòu)造方法

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

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

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

算法1.基于準循環(huán)LDPC碼的測量矩陣構(gòu)造

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

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

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

步驟4.令

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

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

3.2.2 RIP性質(zhì)

設(shè)Θ=ΨRφ,壓縮感知理論告訴我們,為了精確地重構(gòu)出原始數(shù)據(jù),Θ必須滿足RIP性質(zhì).

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

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

3.3 簇內(nèi)數(shù)據(jù)收集

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

4 數(shù)據(jù)收集路徑優(yōu)化

4.1 路徑分析

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

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

4.2 優(yōu)化算法

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

算法2.基于樹分解的數(shù)據(jù)收集路徑優(yōu)化

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

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

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

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

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

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

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

5 仿真實驗

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

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

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

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

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

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

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

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

6 結(jié)束語

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

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 (李建中,高宏.無線傳感器網(wǎng)絡(luò)的研究進展.計算機研究與發(fā)展, 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:基于約束等距的壓縮感知匹配追蹤.計算機研究與發(fā)展,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 (蔣暢江,石為人,唐賢倫,王平,向敏.能量均衡的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議.軟件學(xué)報,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 (劉冬培,劉衡竹,張波濤.基于準循環(huán)雙對角陣的LDPC碼編碼算法.國防科技大學(xué)學(xué)報,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

李 鵬 中南大學(xué)信息科學(xué)與工程學(xué)院博士研究生.主要研究方向為無線傳感器網(wǎng)絡(luò),壓縮感知技術(shù).本文通信作者.

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.)

王建新 中南大學(xué)信息科學(xué)與工程學(xué)院教授.主要研究方向為網(wǎng)絡(luò)優(yōu)化理論,參數(shù)計算和生物信息學(xué).

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.)

丁長松 湖南中醫(yī)藥大學(xué)管理與信息工程學(xué)院副教授.主要研究方向為網(wǎng)絡(luò)優(yōu)化理論,云計算.

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中基于壓縮感知的高能效數(shù)據(jù)收集方案.自動化學(xué)報,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

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

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

本文責(zé)任編委趙千川

Recommended by Associate Editor ZHAO Qian-Chuan

1.中南大學(xué)信息科學(xué)與工程學(xué)院長沙410083 2.湖南中醫(yī)藥大學(xué)管理與信息工程學(xué)院長沙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