李鵬 王建新 丁長(zhǎng)松

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

李鵬1,2王建新1丁長(zhǎng)松2

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

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

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

1 相關(guān)工作

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

2 問(wèn)題建模

2.1 系統(tǒng)模型

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

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

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

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

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

2.2 相關(guān)定義

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

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

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

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

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

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

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

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

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

2.3 問(wèn)題描述

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

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

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

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

3.1 稀疏矩陣設(shè)計(jì)

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

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

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

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

3.2 測(cè)量矩陣設(shè)計(jì)

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

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

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

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

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

準(zhǔn)循環(huán)LDPC碼是一種具有稀疏校驗(yàn)矩陣的分組糾錯(cuò)碼.它的性能逼近香農(nóng)限,描述和實(shí)現(xiàn)簡(jiǎn)單,且可并行操作,適合硬件實(shí)現(xiàn).已有研究表明[19],對(duì)于一個(gè)任意給定的準(zhǔn)循環(huán)LDPC碼,如果它的校驗(yàn)矩陣能實(shí)現(xiàn)良好的信道編碼或解碼性能,則將它的校驗(yàn)矩陣作為基于壓縮感知的信號(hào)處理中的測(cè)量矩陣,也能實(shí)現(xiàn)精確的數(shù)據(jù)重構(gòu).為此,本文根據(jù)準(zhǔn)循環(huán)LDPC碼校驗(yàn)矩陣的正交性和稀疏性來(lái)設(shè)計(jì)測(cè)量矩陣.設(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為校驗(yàn)矩陣的碼字C稱為準(zhǔn)循環(huán)LDPC碼.對(duì)于網(wǎng)絡(luò)存在丟包情況下基于壓縮感知的數(shù)據(jù)收集應(yīng)用而言,為了保證數(shù)據(jù)收集質(zhì)量和節(jié)約網(wǎng)絡(luò)能耗,測(cè)量矩陣的設(shè)計(jì)必需考慮稀疏性、高糾錯(cuò)性等因素,而采用準(zhǔn)循環(huán)LDPC碼來(lái)設(shè)計(jì)測(cè)量矩陣恰好能夠滿足這一要求.因此,本文設(shè)計(jì)了一種基于準(zhǔn)循環(huán)LDPC碼的測(cè)量矩陣構(gòu)造算法.

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

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

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

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

步驟4.令

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

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

3.2.2 RIP性質(zhì)

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

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

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

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

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

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

4.1 路徑分析

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

圖2 測(cè)量值傳輸Fig.2 Measurement transmission

4.2 優(yōu)化算法

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

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

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

輸出.測(cè)量值傳輸路徑P.

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

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

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

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

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

5 仿真實(shí)驗(yàn)

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

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

圖3給出了在不同的丟包率(plratio=0,0.05, 0.10,0.15)條件下本文方案的重構(gòu)誤差情況.可以看到,隨著測(cè)量次數(shù)的增加,無(wú)論丟包率如何,重構(gòu)誤差的總體趨勢(shì)都在下降.其中plratio=0表示理想狀態(tài)下的傳感器網(wǎng)絡(luò),此時(shí)的網(wǎng)絡(luò)不發(fā)生丟包,在該情況下本文方案的重構(gòu)性能最優(yōu).另外,仔細(xì)觀察不同丟包率下的重構(gòu)誤差曲線可以發(fā)現(xiàn),當(dāng)測(cè)量次數(shù)增加到600次后,不同丟包率下的重構(gòu)誤差越來(lái)越接近,甚至當(dāng)測(cè)量次數(shù)達(dá)到1000次時(shí),四種情形下的重構(gòu)誤差基本達(dá)到一致,這充分表明了本文方案在網(wǎng)絡(luò)發(fā)生丟包情況下進(jìn)行數(shù)據(jù)收集的可靠性,此時(shí)就算網(wǎng)絡(luò)發(fā)生較大規(guī)模的丟包,只要適當(dāng)?shù)卦黾訙y(cè)量次數(shù),本文方案仍然能夠保證精確地重構(gòu)出網(wǎng)絡(luò)中各節(jié)點(diǎn)的原始數(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)首先給出了測(cè)量次數(shù)為600次時(shí),不同丟包率plratio下三種方案的重構(gòu)誤差實(shí)驗(yàn)結(jié)果.從圖4(a)可以看到,對(duì)于三種數(shù)據(jù)收集方案而言,其重構(gòu)誤差都隨著丟包率的增加而增加,但本文方案的重構(gòu)誤差始終低于SRS方案和CSEC方案,且隨著網(wǎng)絡(luò)丟包率的不斷增加,本文方案的性能優(yōu)勢(shì)越來(lái)越明顯.特別地,當(dāng)網(wǎng)絡(luò)丟包率為0.15時(shí),就重構(gòu)誤差而言,本文方案比SRS方案低42.6%,比CSEC方案低31.2%.表明本文方案在網(wǎng)絡(luò)存在丟包的情形下仍然能夠?qū)崿F(xiàn)有效的數(shù)據(jù)收集,算法的魯棒性較強(qiáng).究其原因,主要是因?yàn)镾RS方案采用稀疏隨機(jī)調(diào)度應(yīng)對(duì)網(wǎng)絡(luò)丟包,當(dāng)網(wǎng)絡(luò)規(guī)模較大、丟包現(xiàn)象較為頻繁時(shí),該方案的稀疏矩陣會(huì)導(dǎo)致部分節(jié)點(diǎn)的數(shù)據(jù)丟失,影響了數(shù)據(jù)重構(gòu)精度. CSEC方案則基于信道丟失概率增加測(cè)量矩陣的行數(shù)應(yīng)對(duì)網(wǎng)絡(luò)丟包,并對(duì)不同信道模型下的丟包現(xiàn)象做了自適應(yīng)處理,因此取得了比SRS方案更好的重構(gòu)性能.本文方法主要針對(duì)SRS方案和CSEC方案的不足進(jìn)行改進(jìn),以保證數(shù)據(jù)收集可靠性這一目標(biāo)設(shè)計(jì)測(cè)量矩陣,并對(duì)數(shù)據(jù)收集路徑做了一定的優(yōu)化,因此進(jìn)一步提高了數(shù)據(jù)重構(gòu)精度.圖4(b)給出了丟包率為0.1時(shí),不同測(cè)量次數(shù)下三種方案的重構(gòu)誤差實(shí)驗(yàn)結(jié)果.從圖4(b)可以看到,在丟包現(xiàn)象存在的前提下,本文方案的重構(gòu)性能始終優(yōu)于其他兩種方案.特別地,為了達(dá)到數(shù)據(jù)重構(gòu)精度為0.03,本文方案需要花費(fèi)約600次測(cè)量,而SRS方案和CSEC方案分別需要花費(fèi)約800次測(cè)量和900次測(cè)量,表明本文方案在保證數(shù)據(jù)收集高可靠性的前提下,比SRS方案和CSEC方案的效率更高,成本更低.

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

在無(wú)線傳感器網(wǎng)絡(luò)的諸多應(yīng)用中,均要求傳感器節(jié)點(diǎn)以無(wú)差錯(cuò)形式將監(jiān)測(cè)數(shù)據(jù)傳輸至Sink節(jié)點(diǎn).為了滿足應(yīng)用需求,本文以壓縮感知理論為基礎(chǔ),提出了一種高能效的數(shù)據(jù)收集方案.該方案首先通過(guò)設(shè)計(jì)的稀疏矩陣和測(cè)量矩陣完成節(jié)點(diǎn)上的數(shù)據(jù)處理,然后采用樹(shù)分解和動(dòng)態(tài)規(guī)劃的思路優(yōu)化數(shù)據(jù)收集路徑.仿真結(jié)果表明,在網(wǎng)絡(luò)存在丟包的情況下,本文方案仍然能夠保證數(shù)據(jù)收集的高精確度,相比于其他數(shù)據(jù)收集方案,本文方案的性能更優(yōu).在下一步工作中,我們關(guān)注的重點(diǎn)是:1)對(duì)本文的網(wǎng)絡(luò)場(chǎng)景假設(shè)做出改變,以提高數(shù)據(jù)收集精度和降低網(wǎng)絡(luò)能耗為目標(biāo),研究移動(dòng)Sink條件下基于壓縮感知的數(shù)據(jù)收集方案;2)對(duì)真實(shí)無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)感知數(shù)據(jù)的稀疏性進(jìn)行分析,研究基于壓縮感知的自適應(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ú)線傳感器網(wǎng)絡(luò)的研究進(jìn)展.計(jì)算機(jī)研究與發(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:基于約束等距的壓縮感知匹配追蹤.計(jì)算機(jī)研究與發(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ú)線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議.軟件學(xué)報(bào),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 (劉冬培,劉衡竹,張波濤.基于準(zhǔn)循環(huán)雙對(duì)角陣的LDPC碼編碼算法.國(guó)防科技大學(xué)學(xué)報(bào),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é)院博士研究生.主要研究方向?yàn)闊o(wú)線傳感器網(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é)院教授.主要研究方向?yàn)榫W(wǎng)絡(luò)優(yōu)化理論,參數(shù)計(jì)算和生物信息學(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.)

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

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

李鵬,王建新,丁長(zhǎng)松.WSN中基于壓縮感知的高能效數(shù)據(jù)收集方案.自動(dòng)化學(xué)報(bào),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

國(guó)家自然科學(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é)院長(zhǎng)沙410083 2.湖南中醫(yī)藥大學(xué)管理與信息工程學(xué)院長(zhǎng)沙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