面向可靠性和能耗優化的可壓縮數據收集方案*

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

面向可靠性和能耗優化的可壓縮數據收集方案*

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

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

無線傳感器網絡；數據收集；壓縮感知；稀疏矩陣；測量矩陣；樹分解

0　引言

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

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

1　問題建模

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

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

2　節點上的數據處理

2.1稀疏矩陣設計

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

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

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

2.2測量矩陣設計

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

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

算法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'中對應位置的子矩陣。

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

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

2.3簇內數據收集

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

3　數據收集路徑優化

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

算法2：基于樹分解的測量值傳輸路徑優化算法

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

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

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

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

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

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

Else轉步驟（2）；

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

Ei=E'∩（Vi×Vi）；

3）對每個節點i∈，計算包含了節點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）對于所有的節點 i∈，以自底向上的方式計算HTi（i，θ），重復執行步驟（3）～（5）直到中所有的節點都處理完畢。

4　仿真實驗

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

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

式中x為原始數據，^x為其重構值。

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

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

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

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

5　結束語

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

［1］陳巖，譚婷，高峰，等.水質監測無線傳感器網絡節點雙電源設計［J］.傳感器與微系統，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］蔣暢江，石為人，唐賢倫，等.能量均衡的無線傳感器網絡非均勻分簇路由協議［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］王沖，張霞，李鷗.無線傳感器網絡中基于壓縮感知的分簇數據收集算法［J］.傳感器與微系統，2016，35（1）：142-145.

［8］劉冬培，劉衡竹，張波濤.基于準循環雙對角陣的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-），男，湖南瀘溪人，博士研究生，研究方向為無線傳感器網絡、壓縮感知技術。