面向可靠性和能耗優(yōu)化的可壓縮數(shù)據(jù)收集方案*

李　鵬，王建新（中南大學信息科學與工程學院，湖南長沙410083）

面向可靠性和能耗優(yōu)化的可壓縮數(shù)據(jù)收集方案*

李鵬，王建新
（中南大學信息科學與工程學院，湖南長沙410083）

現(xiàn)有的無線傳感器網(wǎng)絡（WSNs）數(shù)據(jù)收集方法無法在耗費較低開銷的同時保證數(shù)據(jù)收集的可靠性?；趬嚎s感知（CS）理論，設計了基于指數(shù)核函數(shù)的稀疏矩陣和基于準循環(huán)低密度奇偶校驗（LDPC）碼的測量矩陣來用于節(jié)點的數(shù)據(jù)采集，以最大化網(wǎng)絡生命周期為目標，將測量值傳輸問題建模為漢密爾頓回路問題，并提出了一種基于樹分解的數(shù)據(jù)收集路徑優(yōu)化算法。仿真實驗結果表明：所提方案在數(shù)據(jù)重構誤差和能耗方面的性能要優(yōu)于目前典型的數(shù)據(jù)收集方法。

無線傳感器網(wǎng)絡；數(shù)據(jù)收集；壓縮感知；稀疏矩陣；測量矩陣；樹分解

0　引言

在無線傳感器網(wǎng)絡（wireless sensor networks，WSNs）［1］的諸多應用中，均要求傳感器節(jié)點以無差錯形式將監(jiān)測數(shù)據(jù)傳輸至Sink。但由于無線通信鏈路的高失效率、節(jié)點資源受限以及環(huán)境惡劣等原因，使得節(jié)點間通信受到干擾，產(chǎn)生丟包問題，導致可靠的數(shù)據(jù)傳輸難以得到保障。文獻［2］設計了一種基于壓縮感知和糾刪碼（compressive sensing erasure encoding，CSEC）的數(shù)據(jù)收集方案。然而，該方案在一定程度上是以犧牲節(jié)點的能耗為代價來提高數(shù)據(jù)收集可靠性，在真實傳感器網(wǎng)絡中的實際應用價值不大。文獻［3］針對可壓縮數(shù)據(jù)收集（compressive data gathering，CDG）方案［4］在有損信道中進行數(shù)據(jù)收集的不足，提出了最大稀疏隨機調度（sparsest random scheduling，SRS）的數(shù)據(jù)收集方案。然而，該方案僅根據(jù)感知數(shù)據(jù)間的空間相關性來提高數(shù)據(jù)收集可靠性，因此，它容易受到網(wǎng)絡節(jié)點初始分布的影響，魯棒性較差。

針對上述方法的不足，本文以壓縮感知理論為基礎，提出一種面向可靠性和能耗優(yōu)化的可壓縮數(shù)據(jù)收集方案，并通過仿真實驗也表明了該方案的有效性。

1　問題建模

設N個傳感器節(jié)點和1個Sink節(jié)點被隨機地分布在一個面積為N×N平方米的正方形區(qū)域A內。整個WSNs構成一個連通的無向圖。WSNs具有如下性質：1）所有節(jié)點在部署后保持靜止，節(jié)點的傳輸半徑相同。2）網(wǎng)絡中任意節(jié)點之間的鏈路可能存在丟包現(xiàn)象，且發(fā)生丟包的位置無法預測。3）采用能量均衡的非均勻分簇路由協(xié)議（distributed energy-balanced unequal clustering routing protocol，DEBUC）［5］對網(wǎng)絡進行分簇。節(jié)點的初始能量不統(tǒng)一，節(jié)點在其自身能量耗光后，不能進行補充。

現(xiàn)有的基于壓縮感知的數(shù)據(jù)收集方法［6］只適用于理想條件，當網(wǎng)絡中部分鏈路中斷而導致丟包現(xiàn)象發(fā)生后，會導致部分節(jié)點的測量值無法有效地被收集，此時，如果處于中斷鏈路端點的節(jié)點重要程度較高，則會嚴重影響到數(shù)據(jù)收集的質量，導致網(wǎng)絡應用可靠性較低。為此，本文研究的問題是：如何設計稀疏矩陣和測量矩陣來應對數(shù)據(jù)丟失，以及如何對數(shù)據(jù)收集路徑進行優(yōu)化，最終實現(xiàn)數(shù)據(jù)收集的高精確度與網(wǎng)絡生命周期的最大化。

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

2.1稀疏矩陣設計

在密集部署的大規(guī)模WSNs中，不同節(jié)點的感知數(shù)據(jù)之間通常具有時空相關性。本文采用如下的指數(shù)核函數(shù)κ（xi，xj）對感知數(shù)據(jù)間的相關性進行衡量

式中dij為第i個傳感器和第j個傳感器之間的距離。σ為函數(shù)的寬度參數(shù)，可以通過最大似然估計或貝葉斯學習機制得到。根據(jù)式（1）可知，對于擁有N個節(jié)點的WSNs而言，其所有感知數(shù)據(jù)的相關性可以表示為

根據(jù)式（2）可知，R屬于托普利茲（Toeplitz）矩陣，它可以對角化為。其中，ΨR為由R的正交特征向量組成的基函數(shù)，Γ為一個對角矩陣，它的非零元素由R的特征值組成。依據(jù)上述分析，本文采用ΨR作為感知數(shù)據(jù)的稀疏矩陣，即有x=ΨRs。

2.2測量矩陣設計

已有的測量矩陣［7］大多將焦點集中在如何提高數(shù)據(jù)收集精度和降低數(shù)據(jù)收集能耗，但很少考慮到如何應對數(shù)據(jù)收集過程中的傳輸丟包問題，可靠性不高。為此，本文提出采用分塊矩陣的思路來設計測量矩陣，具體設計過程分為兩個部分：1）對于葉子節(jié)點而言，采用單位矩陣I來收集它們的數(shù)據(jù)，即對葉子節(jié)點的數(shù)據(jù)不經(jīng)壓縮采樣就直接收集。2）對于非葉子節(jié)點而言，則利用其數(shù)據(jù)傳輸?shù)男诺谰幋a校驗矩陣來設計測量矩陣。一般而言，信道編碼校驗矩陣的列向量很容易被稀疏化，且任意的兩個列向量之間具有線性無關的特性，容易滿足RIP性質。為此，提出一種基于準循環(huán)低密度奇偶校驗（low density parity check，LDPC）碼［8］的方法來構造測量矩陣'。綜上所述，本文要設計的測量矩陣為：=［I/＇］。

理論分析［8］表明：如果一個給定的二進制奇偶校驗矩陣在信道編碼/解碼中具有良好性能，則該矩陣作為測量矩陣同樣能夠精確地實現(xiàn)基于壓縮感知的信號重構。而對于網(wǎng)絡存在丟包情況下基于壓縮感知的數(shù)據(jù)收集應用而言，除了保證數(shù)據(jù)收集質量以外，如何盡可能少地消耗節(jié)點能量也是必須考慮的問題。因此，本文從降低節(jié)點能耗的角度出發(fā)，結合準循環(huán)低密度奇偶檢驗（low density parity check，LDPC）碼具有的稀疏性、高糾錯性等性質，通過搜索適當?shù)膯挝痪仃囈莆淮螖?shù)，提出了一種基于準循環(huán)LDPC碼的測量矩陣構造方法。其主要步驟如算法1所示。

算法1：基于準循環(huán)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'中對應位置的子矩陣。

5）對CM中的所有列向量做歸一化處理，然后抽取M個線性無關向量來填充壓縮感知測量矩陣'的前M個列向量，即：。

最后通過前M列的線性組合來表示測量矩陣中的剩余N-M個列向量，從而得到'。

2.3簇內數(shù)據(jù)收集

綜上所述，各個傳感器節(jié)點依據(jù)上述設計的稀疏矩陣ΨR和測量矩陣對各自的感知數(shù)據(jù)進行壓縮采樣后通過單跳或多跳的方式上傳到各自所屬的簇頭節(jié)點，然后由Sink來找到一條最優(yōu)的路徑將各個簇頭的測量值收集上來，并采用重構算法來還原各個節(jié)點的原始數(shù)據(jù)。

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

一般而言，Sink可以采用多條路徑來收集各個簇頭上的測量值，因此，為了節(jié)省網(wǎng)絡能量，本文的目標是要找到一條最優(yōu)路徑，使得每個簇頭只需被訪問一次就能將所有簇頭的測量值收集上來，該問題可以看作一個起點和終點都是Sink的漢密爾頓回路問題，它屬于NP難題?？紤]到WSNs中節(jié)點的數(shù)目是有限的，本文提出一種基于樹分解［9］的測量值傳輸路徑優(yōu)化算法來解決該問題。

算法2：基于樹分解的測量值傳輸路徑優(yōu)化算法

輸入：由簇頭和Sink組成的無向連通圖G'=（V'，E'）

輸出：測量值的傳輸路徑P

1）Sink發(fā)送一個查詢包到各個簇頭，各個簇頭根據(jù)Sink的廣播路徑返回各自的測量值：

從圖G'=（V'，E'）的Sink頂點出發(fā)進行廣度優(yōu)先搜索，記錄得到的圖G'的頂點訪問序列集合為VaS，

If G'中任意兩個頂點的度數(shù)之和＜|V'|+1，Then

從VaS選取一條可以回到Sink的序列作為傳輸路徑P，算法結束。

Else轉步驟（2）；

2）首先，從圖 G'=（V'，E'）中任意刪除一個節(jié)點v'（v'∈V'）和與v'相關聯(lián)的邊，并在余下的圖中補充邊，將v'的鄰居節(jié)點組織成團結構。然后，采用最大勢搜索策略［10］來逐個消元圖G'=（V'，E'）的所有節(jié)點，可獲得具體的消元順序，然后依據(jù)該消元順序可構造得到圖G'=（V'，E'）的一個非平凡樹分解Γ=（T，），樹寬為k。對于每一個i∈，Vi=∪j，j=i or 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=θ，

If不存在回路Then設置HTi（i，θ）=-∞；

Else返回P；

∥HTi（i，θ）是圖G'=（V'，E'）上的一個漢密爾頓回路P

5）對于所有的節(jié)點 i∈，以自底向上的方式計算HTi（i，θ），重復執(zhí)行步驟（3）～（5）直到中所有的節(jié)點都處理完畢。

4　仿真實驗

采用Matlab 2012作為仿真工具，利用CitySee系統(tǒng)［11］測得的溫度數(shù)據(jù)作為測試數(shù)據(jù)來驗證本文方案的性能。實驗過程中用到的主要仿真參數(shù)設置：數(shù)據(jù)包長度為1000 b；發(fā)送1bit數(shù)據(jù)所需的能量為10nJ；接收1bit數(shù)據(jù)所需的能量為50 nJ；單個節(jié)點每次數(shù)據(jù)收集所需能量為1000 nJ；數(shù)據(jù)重構采用OMP算法。

主要考察了本文方案在與目前較為典型的SRS方案和CSEC方案在數(shù)據(jù)重構誤差和能耗方面的性能對比情況。實驗結果取50次仿真的平均值。其中，數(shù)據(jù)重構誤差采用下式進行衡量

式中x為原始數(shù)據(jù)，^x為其重構值。

圖1給出了丟包率變化情況下三種方案的重構誤差實驗結果?？梢钥吹?，隨著丟包率的增加，三種方案的重構誤差都在增加，但是本文方案的性能最優(yōu)，CSEC次之。另外，SRS方案和CSEC方案的數(shù)據(jù)重構誤差隨著丟包率的增加趨向于線性增加，而本文方案的數(shù)據(jù)重構曲線更為平坦，這表明本文方法的魯棒性更強，在應對網(wǎng)絡丟包方面更為有效，當丟包率達到15%時，本文方案的重構誤差相比于SRS方案和CSEC方案降低了約42.6%和31.2%。

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

圖2給出了本文方案與SRS方案和CSEC方案的能耗比較情況?？梢钥吹剑壕W(wǎng)絡能耗與重構誤差成反比關系，本文方案的能耗最低。隨著數(shù)據(jù)收集應用對于重構誤差的要求降低，本文方案的優(yōu)勢越發(fā)明顯，當重構誤差僅僅要求為0.1時，本文方案的能耗相比于CSEC方案和SRS方案分別節(jié)省了約56.1%和41.6%。

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

5　結束語

本文提出了一種面向可靠性和能耗優(yōu)化的可壓縮數(shù)據(jù)收集方案，首先設計了稀疏矩陣和測量矩陣用于節(jié)點上的數(shù)據(jù)收集，然后提出了一種基于樹分解的數(shù)據(jù)收集路徑優(yōu)化算法。仿真實驗結果表明：本文方案無論是數(shù)據(jù)重構精度還是能耗都要優(yōu)于已有的方法。下一步工作的重點是：1）采用壓縮感知理論，研究基于多個固定Sink的數(shù)據(jù)收集路徑優(yōu)化方案；2）采用壓縮感知理論，研究基于單個移動Sink的數(shù)據(jù)收集可靠性方案。

［1］陳巖，譚婷，高峰，等.水質監(jiān)測無線傳感器網(wǎng)絡節(jié)點雙電源設計［J］.傳感器與微系統(tǒng)，2015，34（10）：93-95.

［2］Charbiwala Z，Kim Y，He Ting，et al.Compressive oversampling for robust data transmission in sensor networks［C］∥The 29th IEEE Conference on Computer Communications，Joint Conference of the IEEE Computer and Communications Societies（INFOCOM），San Diego，CA，USA：IEEE，2010：1-9.

［3］Wu Xuanguo，Yang Panlong，Jung Taeho，et al.Compressive sensing meets unreliable link：Sparsest random scheduling for compressive data gathering in lossy WSNs［C］∥The 20th Annual International Conference on Mobile Computing and Networking （MOBICOM），Maui，HI，USA：ACM，2014：13-22.

［4］Luo Chong，Wu Feng，Sun Jun，et al.Efficient measurement generation and pervasive sparsity for compressive data gathering［J］.IEEE Transactions on Wireless Communications，2010，9（12）：3728-3738.

［5］蔣暢江，石為人，唐賢倫，等.能量均衡的無線傳感器網(wǎng)絡非均勻分簇路由協(xié)議［J］.軟件學報，2012，23（5）：1222-1232.

［6］Zheng Haifeng，Yang Feng，Tian Xiaohua，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.

［7］王沖，張霞，李鷗.無線傳感器網(wǎng)絡中基于壓縮感知的分簇數(shù)據(jù)收集算法［J］.傳感器與微系統(tǒng)，2016，35（1）：142-145.

［8］劉冬培，劉衡竹，張波濤.基于準循環(huán)雙對角陣的LDPC碼編碼算法［J］.國防科技大學學報，2014，36（2）：156-160.

［9］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［J］.Algorithmica，2015，71（3）：636-660.

［10］Azad A，BulucA，Pothen A.A parallel tree grafting algorithm for maximum cardinality matching in bipartite graphs［C］∥The 30th IEEE International Parallel&Distributed Processing Symposium （IPDPS），Chicago，USA：IEEE，2015：1231-1241.

［11］Wu Xuangou，Yan Xiong，Yang Panlong，et al.Sparsest random scheduling for compressive data gathering in wireless sensor networks［J］.IEEE Transactions on Wireless Communications，2014，13（10）：5867-5877.

Compressible data gathering scheme for reliability and energy consumption optimization*

LI Peng，WANG Jian-xin
（School of Information Science and Engineering，Central South University，Changsha 410083，China）

The existing wireless sensor networks（WSNs）data gathering methods cannot be ensure reliability of data gathering with low cost.To solve this problem，Based on the theory of compressive sensing（CS），sparse matrix based on exponential kernel function and measurement matrix based on quasicyclic low density parity check （LDPC）code are designed to be used for data acquisition of node.Maximization of network lifetime is target，the measurement value transmission problem is modeled as the Hamilton loop problem，and a data gathering path optimization algorithm based on tree decomposition is proposed.Simulation results show that the performance of the proposed scheme is better than the typical data gathering methods in terms of data reconstruction error and energy consumption.

wireless sensor networks（WSNs）；data gathering；compressive sensing（CS）；sparse matrix；measurement matrix；tree decomposition

TP393

A

1000—9787（2016）06—0024—03

10.13873/J.1000—9787（2016）06—0024—03

2016—05—23

國家自然科學基金資助項目（61472449，61173169，61402542）

李鵬（1983-），男，湖南瀘溪人，博士研究生，研究方向為無線傳感器網(wǎng)絡、壓縮感知技術。