無線傳感網容錯數據融合方案設計

謝冬青，邢蕭飛

（廣州大學計算機科學與教育軟件學院，廣東 廣州 510006）

無線傳感網容錯數據融合方案設計

謝冬青，邢蕭飛

（廣州大學計算機科學與教育軟件學院，廣東 廣州 510006）

數據融合是無線傳感器網絡中一個重要研究問題，現有基于壓縮感知（compressed sensing，CS）的數據融合方案主要是以集中的方式由基站節點完成數據融合任務，容易造成負載不均衡和“覆蓋空洞”等問題.文章提出了一個基于壓縮感知的容錯數據融合（compressed sensing-based erasure-correcting data aggregation，CSEDA）方案，并使用正交匹配追蹤（orthogonal matching pursuit，OMP）算法來準確地重構壓縮后的數據，在保證所獲得數據質量的條件下減少網絡通信開銷.另外，文章使用節點分簇機制來優化和均衡網絡負載.實驗結果表明，和其它的數據融合方案相比較，文章所提出的方案在數據重構的容錯性和網絡能量效率等方面上取得較好性能.

無線傳感器網絡；數據融合；壓縮感知；能量均衡

無線傳感器網絡（Wireless sensor networks）的產生解決人類對物理信息的采集，將客觀的物理世界與人類的邏輯社會聯結在一起，因而被廣泛應用在工農業、軍事、醫學護理、環境監測等領域［1］.由于傳感器節點在尺寸和成本方面的約束，使其在通信、計算和能量供應等方面受到了極大的限制.因此，在滿足網絡服務質量條件下如何實現對數據的有效壓縮是十分必要的.它可以去除感知信息中的冗余數據，在得到有效數據的前提下，減少節點之間數據通信量，也減少數據通信過程中的碰撞，減輕網絡數據擁塞，節省節點能量，從而達到延長網絡生存時間的目的.

最近幾年在信號處理領域出現的壓縮感知（compressed sensing）理論［2-3］提供了一種新的解決思路.它的核心思想是，只要采集的信號在時空域上具有稀疏性的特征，那么它就可以通過使用少量隨機線性觀測值來重新構造出原始信號.它憑借優異的壓縮性能、非自適應編碼及編碼解碼相互獨立的特征在信息處理和通信領域受到廣泛的關注，成為數據壓縮領域最新突出的理論之一.

與傳統數據融合技術不同，壓縮感知適用于無線傳感器網絡的數據融合處理的主要原因：①它具有優異的數據壓縮性能，實現數據采集和壓縮同步完成，大大減少了需要傳輸的數據量；②編碼的低計算復雜度，信號只需要在隨機觀測矩陣上進行線性投影，便可計算出壓縮后的觀測向量；③編碼和解碼的相互獨立，對于相同的編碼方法，可以使用不同的解碼技術，解碼節點通過收到的信息數據的觀測向量，使用解碼算法獨立重構數據.同時，在一定概率的原始數據丟失的情況下并不影響對原始數據的重構質量，這保證了數據融合與重構的容錯性能.

文獻［4］提出了一個基礎的壓縮感知（compressed sensing，CS）算法，它主要是對城市交通數據進行壓縮與重構，有效減少了網絡的通信量.文獻［5］提出了一個多信道單頻譜方案（multi-channel singular spectrum analysis，MSSA），該方案是一個基于滯后協方差矩陣的非參數數據構造，用于部分數據已丟失的地理數據信息的重構.文獻［6］提出了能量高效信息收集方案（energy efficient information collection，EEIC），它考慮了節點的能量消耗和感應數據的信息量2方面的因素，從節點收集數據并對其進行壓縮處理.文獻［7］提出了一個基于有效存儲的漸進小波數據壓縮算法，該算法依據小波函數的支撐長度和簇頭的可用存儲容量來確定漸進傳送的數據單元，依據空間相關性來選擇漸進傳送數據的傳感器節點，從而在存儲有效的同時又節省網絡傳輸耗能.文獻［8］提出了一個壓縮的稀疏函數方法（compressive sensing functions），它是在一個合適的函數基下通過使用一個改進的壓縮感知技術來提高網絡中采集數據的壓縮質量.也有一些文獻從其它角度提出了解決方案，如文獻［9］提出了一個基于分簇的數據預測傳送方案，根據應用期望的無縫覆蓋率與所需簇頭數量之間的數學關系來限制節點競選簇頭的初始概率，同時利用簇頭節點簇內數據進行聚合，然后傳送給基站，但這個方案沒有解決丟失數據的重構問題.文獻［10］基于改進的層次路由算法LEACH［11］而提出了一個基于分簇的數據融合算法，簇頭節點通過非沖突的CSMA方法來壓縮收集的數據，并將它傳送給基站節點.上述方案存在的問題集中2個方面：①大部分數據壓縮與處理以集中的方式由基站節點完成，導致了網絡負載的不均衡和“覆蓋空洞”等問題的產生；②基于壓縮感知技術的數據收集與融合方案僅考慮了以服務為中心的無線傳感器網絡的某一方面特征，如數據結構特征、數據的相關性和數據重構成功概率等，缺少對網絡這些特征的整體解決措施.本文依據網絡節點之間數據傳輸的特征，提出一種基于壓縮感知理論的容錯數據融合（Compressed Sensing-based Erasure-Correcting Data Aggregation，CS-EDA）方案.同時，針對傳感器網絡在應用中因節點負載的不同，造成局部“覆蓋空洞”情況的發生，設計了一個低開銷的網絡分簇方法，使所提出的方案在數據通信、能量效率、負載均衡和數據容錯等方面具有比較好的性能，從而在保障網絡服務質量的條件下，延長網絡的生存時間.

1 網絡模型與問題定義

1.1 網絡模型

本文假設網絡具有如下特征：

（1）節點是同構的，節點具有相同大小的感知半徑和通信半徑，節點采用有向的感知模型［12］；

（2）節點通信半徑是其感知半徑的2倍，一個完全覆蓋的網絡確保了節點之間的連通性；

（3）節點以隨機均勻形式部署在監測區域，節點保持時鐘同步.

1.2 問題定義

在給出正式問題定義之前，首先給出相關的定義.

定義1（節點有向感應模型）：節點有向感應模型定義為一個四元組＜O，Rs，V，α＞，見圖1，其中，O＝（x，y）表示有向傳感器節點的位置坐標，Rs表示節點的感知半徑，單位向量V＝（Vx，Vy）為扇形感應區域中軸線，即節點的感應方向；Vx和Vy分別是單位向量V在X軸和Y軸方向上的投影分量；α表示覆蓋邊界與感應向量V的感應夾角.

圖1 節點有向感應模型Fig.1 Diretional sensing model

定義2（感應矩陣）：它用于描述傳感器網絡監測的動態環境信息，其數學形式如下：

這里的n和t分別表示節點數量和節點在不同時間采集數據數量.

定義3（重構矩陣）：它是通過數據重構算法得到的近似于感應矩陣的重構矩陣，其數學表述形式如下：

問題定義：給定一個感應矩陣X，如何對其數據進行壓縮，使得重構后的重構矩陣X′盡可能地接近X，即X′與X之間的誤差最小化的問題.其數學表達如下：

2 基于壓縮感知的容錯數據融合方案

本節提出基于壓縮感知的容錯數據融合方案（Compressed Sensing-based Erasure-correcting Data Aggregation，CS-EDA），其基本思想是以分簇網絡為基礎，采用時間輪方式來選擇簇頭節點，簇頭節點負責收集和融合數據，并將處理后的數據發送給基站節點，基站節點完成原始數據的重構任務.

2.1 分輪機制

本文采用時間分輪的方法，將整個網絡運行時間劃分成若干大小相等的時間段，每個時間段稱為一個“輪”.每個時間輪由初始階段和工作階段組成，其中，工作階段的時間長遠大于初始階段.在初始階段完成包括節點覆蓋面積計算和簇頭選舉等在內的網絡分簇任務，在工作階段實現對目標數據的采集和融合工作.算法在整個網絡上以時間輪的方式運行，直至節點能量耗盡為止.同時，由于不需要事先掌握整個網絡的拓撲結構，減少了系統的計算量和通信量.時間輪的劃分見圖2.

圖2 網絡時間輪劃分Fig.2 Timeline of network

2.2 網絡分簇

首先依據節點的覆蓋面積來劃分網絡分簇的大小，然后在每個簇內選擇出簇頭節點（Cluster head）.

（1）目標覆蓋判斷

在時間輪的初始階段，根據節點的感知和通信半徑大小和用戶對網絡覆蓋質量的要求，將整個監測區域劃分成一些大小相等的虛擬網格（C1，C2，…，Cm）.任意一個節點的通信范圍能夠覆蓋其相鄰節點的位置，這樣2個相鄰的節點能夠相互直接通信.各個節點計算其在所在虛擬網絡內的覆蓋面積（見圖3），并根據其覆蓋面積所在網格內的大小決定其屬于哪一個網格.從屬于相同網格的節點組成了一個網絡分簇，為了提高網絡的性能，在分簇實現過程中需要注意以下2方面的因素：

· 監測目標：保證每一個待監測的目標至少要被一個網絡分簇覆蓋.

· 節點分布：部署的節點密度要滿足網絡覆蓋和連通性的要求.由于分簇大小與節點有效的覆蓋面積成反比，當節點的有效覆蓋面積較大，需要縮小虛擬網格的大小.同時需要保證相鄰簇頭之間能夠進行通信.

圖3 節點覆蓋面積的計算Fig.3 The calculation of node′s coverage area

對目標的覆蓋判斷，本文采用了以下方法：假定監測目標位于P點位置，節點Si位于O點，2點之間只需要滿足下面2個公式，則可以判定目標被有向傳感器節點覆蓋.

這里β為0P與V之間的夾角.

（2）簇頭選舉

相比較普通成員節點，簇頭節點承擔了更多的任務，因此，簇頭節點的選擇首先依據剩余能量大小，其次是節點位置；靠近網格中心的節點具有優先權.在首次網絡分簇形成之后，隨機選擇一個位置靠近中心的節點作為簇頭節點；在其后的時間輪內，由成員節點向原簇頭節點發送一個“vote”競選消息，該消息包括節點ID、剩余能量、位置等信息.節點Si成為簇頭的概率采用公式（6）計算［6］.

原簇頭節點在收集到成員發送的“vote”消息后，計算并比較的大小，選擇其中最大的一個節點作為簇頭.新的簇頭節點向各成員節點發送一個“invitation”邀請消息，成員節點收到消息后確認，完成本輪簇頭選舉工作.在簇內，成員節點直接將數據發送給簇頭節點；在簇間，簇節點將簇內數據與其它簇頭節點傳送來的數據采用下文所提出的融合算法壓縮后發向基站節點.

2.3 空間相關性數據的收集與壓縮

對于簇內成員節點采集的數據，這些數據通常具有時域和空域上的相關性［13］，而要使這些數據具有稀疏的特性，需要對其進行處理.首先除去公共部分，只保留私有部分，然后對私有部分做壓縮處理，重構之后再加上公共部分，這樣就能減少重構誤差，提高節點對數據處理的速度，同時降低通信開銷.

利用離散余弦變換（DCT）對數據進行稀疏變換.利用DCT的原因是它能夠將大多數的信號的關鍵信息都集中在信號變換后的低頻部分，DCT變換函數如下：

簇頭節點將DCT函數變換得到需要的觀測向量發送給基站節點.為了快速重構出原始數據，需要控制向量的規模不超過1 000.由于本文采用了網絡分簇機制，每個簇內節點規模數控制在20以內，使得觀測向量規模較小，因此，基站節點較為容易地重構得到原始數據.

2.4 數據重構算法設計與分析

對數據的重構采用的是正交匹配追蹤算法來解決.數據重構算法實現步驟如下：

輸入：n×t維測量矩陣Φ，n維觀測向量y，理想數據矩陣的稀疏度k.

輸出：重建的t維恢復數據X′，從｛1，…，t｝中選取的含有k個元素的指標集Γk，對y的n維近似向量ak，n維殘差向量rm＝y-ak.

第1步：初始化剩余量，指標集Γk＝Φ，迭代計數器i＝0；

第2步：找到滿足下面最優化問題的指標λi

第4步：求解最小二乘問題

第5步：計算新的數據估計和殘差：yi＝Φixi，ri＝y-yi；

第6步：i＝i+1，假如i＜k，返回到第2步；

第7步：重構X′的非零值指標為Γk中的元素，X′的第λJ個元素的值等于xi的第J個元素.

算法的基本思想是在每次數據迭代中將從完備庫中選出的原子使用Gram-Schmidt正交化方法進行正交化處理，再將所得到的采樣數據在這些正交原子形成的空間上進行投影，得到數據在這些正交原子上的分量和余量，然后利用相同的方法進行余量分解，這些余量隨分解過程的進行而迅速減小.通過遞歸對已選擇原子集合進行正交化，這保證了迭代的最優性，減少了迭代次數.對一個k度稀疏n×t維測量矩陣，算法以極大概率重構原始數據矩陣值，其復雜度僅為O（knt）.

3 實驗評價及分析

為了評價本文所提出的CS-EDA方案的性能，本節使用Matlab仿真工具和Intel Berkeley實驗室對室內溫度、濕度和光照強度等監測的真實數據集［14］來評價所提出方案的性能，這個數據包含了室內溫度、濕度和光線強度等信息.并將所提出的CS-EDA方案與壓縮感知（Compressed Sensing，CS）方案［4］、多信道單頻譜方案（Multi-channel singular Spectrum Analysis，MSSA）［5］和能量高效信息收集方案（Energy Efficient Information Collection，EEIC）［6］做了不同評價標準下的性能對比.

3.1 實驗環境和評價標準

為了評價網絡的生存時間，本文通過MATLAB平臺進行實驗，傳感器節點被隨機部署在一個200 m*200 m的目標區域，整個監測區域被劃分成16個虛擬網格.部署的節點數量分別是100、150和200，各代表節點分布的稀疏、中等、稠密環境，節點能耗采用文獻［11］所提出的能耗模型，計算節點發送與接收數據所消耗的能量如公式（8）和公式（9）所示，其參數值分別設置為ET-elec＝50nJ/bit，ER-elec＝100nJ/bit，εfs＝10pJ/bit/m2.

其它實驗環境參數的設置見表1.

表1 實驗環境參數Table 1 Simulation parameters

實驗首先分別進行不同數據丟失率條件下各個方案重構數據的出錯率對比，數據重構的出錯率η定義如公式（10）所示.其次從不同網絡節點分布密度和分簇來評價網絡的能量效率.

3.2 實驗結果分析

圖4（a）～（c）是針對節點采集的室內溫度、濕度和光照強度數據在不同數據丟失率條件下4個方案在數據重構出錯率的對比.通過對比這3個實驗數據結果，本文所提的CS-EDA方案在4個方案中性能最好.從圖4可見，數據丟失率從10%增加90%時，CS-EDA方案的數據重構的出錯率保持在10%到20%的范圍內，而其它3個方案的數據重構出錯率較高，MSSA方案最高數據出錯率接近于60%.同時，相比較圖4（a）和（b）的室內溫度和濕度實驗數據重構結果，4個方案在圖4（c）室內光照的數據重構出錯率變化較小，這主要是因為光線強度的數據的相關度要比前兩者高.

圖4 測試室內不同條件下不同數據丟失率下數據重構的出錯率對比Fig.4 Comparison of the 4 algorithms under different data loss probability

圖5 不同節點分布密度條件下網絡生存時間對比Fig.5 Comparison of the 3 algorithms terms of network lifetime

圖5（a）～（c）是3種不同節點分布密度條件下網絡生存時間的對比，這3種不同節點分布分別表示稀疏（N＝100）、中等（N＝150）和稠密（N＝200）的節點分布環境.從圖5中可見網絡生存時間越久，死亡的節點數越多.同時，通過計算這3種實驗結果，CS-EDA方案比MSSA和EEIC方案在網絡生存時間上分別平均提高了13.9%和39.7%，相比稀疏的節點部署環境，實驗數據說明了CS-EDA方案在稠密節點部署環境下能夠明顯地提高網絡生存時間.同時，本文也對比網絡節點的剩余能量的大小，在稀疏的網絡實驗環境下，當死亡節點數為10時，本文隨機選取了5個工作節點對比它們的剩余能量，其結果見圖6.通過計算，CS-EDA方案比MSSA和EEIC方案在節點剩余能量上分別平均提高了16.1%和35.1%.

圖6 節點剩余能量對比Fig.6 Comparison on the residual enery of nodes（N＝100）

圖7為不同網絡分簇條件下網絡生存時間對比.網絡被劃分3種不同的分簇數，不同分簇對應的分簇大小見表2.從圖7可見，當k＝16時，網絡能夠得到最大的生存時間.這表明將每個分簇網格大小與節點覆蓋面積大小接近時，節點的能量效率最高，其原因是此時節點之間能夠維護較好的覆蓋和通連性，簇頭節點與成員節點及其它簇頭節點之間的通信效率最高.

圖7 不同網絡分簇下網絡生存時間對比Fig.7 Comparison of network lifetime under different cluster size（N＝100）

表2 3種網絡分簇Table 2 Three types of cluster size

4 結 論

由于無線傳感網在能量、計算和存儲等方面的限制，本文提出了一個基于壓縮感知理論的容錯數據融合方案，利用數據在時空域上的稀疏性特征，通過對原始數據進行有效處理來減少網絡節點之間數據通信量，在數據丟失率較高條件下，方案能夠重構出絕大部分的原始數據信息，提高了網絡數據融合的容錯性能.同時方案采用了網絡分簇技術，通過將網絡劃分成若干大小合適的簇集合，優化和均衡了各節點之間的負載，提高了整個網絡在通信和能量上的效率，從而在保證有效傳輸數據條件下，有效地延長了網絡生存時間.

［1］ WANG F，LIU J.Networked wireless sensor data collection：Issues，challenges and approaches［J］.IEEE Commun Surv Tutor，2011，13（4）：673-687.

［2］ KULKAMNI R V，FORSTER A，VENAYAGAMOORTHY G K.Computational intelligence in wireless sensor networks：A survey［J］.IEEE Commun Surv Tutor，2011，13（1）：68-96.

［3］ 焦李成，楊淑媛，劉芳，等.壓縮感知回顧與展望［J］.電子學報，2011，39（7）：1651-1662.JIAO L C，YANG S Y，LIU F，et al.Development and prospect of compressive sensing［J］.Acta Electr Sin，2011，39（7）：1651-1662.

［4］ LI Z，ZHU Y M，ZHU H Z，et al.Compressive sensing approach to urban traffic sensing［C］∥Proceed IEEE Icdcs，2011：889-898.

［5］ ZHU H，ZHU Y，LI M，et al.SEER：Metropolitan-scale traffic perception based on lossy Sensory data［C］∥ProceedIEEE Infocom，2009：217-225.

［6］ CHOU C，RANA R H U.Energy efficient information collection in wireless sensor networks using adaptive compressive sensing［C］∥Proceed IEEE LCN，2009：443-450.

［7］ 周四望，林亞平，葉松濤，等.傳感器網絡中一種存儲有效的小波漸進數據壓縮算法［J］.計算機研究與發展，2009，46（12）：2085-2092.ZHOU S W，LIN Y P，YE S T，et al.A wavelet data compression algorithm with memory-efficiency for wireless sensor network［J］.J Comput Res Devel，2009，46（12）：2085-2092.

［8］ XU L，QI X，WANG Y，et al.Efficient data gathering using compressed sparse functions［C］∥Proceed IEEE Infocom，2013：310-314.

［9］ 楊軍，張德運，張云翼，等.基于分簇的無線傳感器網絡數據匯聚傳送協議［J］.軟件學報，2010，21（5）：1127-1137.YANG J，ZHANG D Y，ZHANG Y Y，et al.Cluster-based data aggregation and transmission protocol for wireless sensor networks［J］.Chin J Softw，2010，21（5）：1127-1137.

［10］LIU Y，ZHU L，TANG W.The data aggregation of wireless sensor networks based on compressed sensing and cluster［J］.J Comput Inform Sys，2013，9（9）：3399-3406.

［11］HEINZELMAN W，CHANDRAKASAN A，BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor networks［J］.IEEE Trans Wirel Commun，2002，1（4）：660-670.

［12］TAO D，TANG S，ZHANG H，et al.Strong barrier coverage in directional sensor networks［J］.Comput Commun，2012，35（8）：895-905.

［13］WANG P，AKYILDIZ I F.Spatial correlation and mobility-aware traffic modeling for wireless sensor networks［J］.IEEE/ ACM Trans Net（TON），2011，19（6）：1860-1873.

［14］Intel Indoor Test Data［EB/OL］.http：//www.select.cs.cmu.edu/data/labapp3/index.htm l.

Design of an erasure-correcting data aggregation approach for w ireless sensor networks

XIE Dong-qing，XING Xiao-fei
（School of Computer Science and Educational Software，Guangzhou University，Guangzhou 510006，China）

Data aggregation is a key issue in wireless sensor networks（WSNs）.Existing compressed sensing（CS）-based data aggregation work utilizes the centralized method to process the data by a sink node，which causes the load imbalance and“coverage hole”problems.This paper presents a CS-based erasure-correcting data aggregation（CS-EDA）approach and designs a data reconstruction algorithm to perform data recovery tasks by utilizing the orthogonal matching pursuit theory，which reduces communication cost under guaranteeing the quality of obtained data.Moreover，the energy consumption of network is optimized and balanced by using clustering mechanism.Simulation results demonstrate that the proposed CS-based erasure-correcting data aggregation approach obtains a better performance on the metrics of accurate data reconstruction and energy efficiency significantly compared to existing methods.

wireless sensor network（WSN）；data aggregation；compressed sensing；energy balance

TP 393

A

1671-4229（2016）01-0001-07

【責任編輯：陳 鋼】

2015-12-20；

2016-01-06

國家自然科學基金委-廣東聯合基金資助項目（U1135002）；中國博士后科學基金資助項目（2014M562153）；廣州市教育局市屬高校科研基金資助項目（1201430560）；廣東省教育廳青年創新人才資助項目（2015KQNCX109）

謝冬青（1965-），男，教授，博士.Email：dongqing_xie＠hotmail.com