無線傳感器網絡中基于壓縮感知的分簇數據收集算法*

王　沖， 張　霞， 李　鷗

(信息工程大學 信息系統工程學院，河南 鄭州 450001)

?

無線傳感器網絡中基于壓縮感知的分簇數據收集算法*

王沖， 張霞， 李鷗

(信息工程大學 信息系統工程學院，河南 鄭州 450001)

摘要:針對無線傳感器網絡(WSNs)能量有限、通信鏈路不可靠的特點，提出一種基于稀疏分塊對角矩陣進行壓縮感知的分簇(SBDMC)數據收集算法。該算法以稀疏分塊對角矩陣作為觀測矩陣以減少參與收集節點數目；采用分布式分簇路由實現數據的分布式收集；通過分析能耗模型得到最優簇頭數目以減少網絡能耗。在此基礎上，給出一種有效的分簇路由數據收集算法。仿真分析表明:提出的算法較之已有算法可以減少通信能耗、延長網絡壽命，同時均衡能耗負載。

關鍵詞:無線傳感器網絡； 壓縮感知； 數據收集

0引言

在無線傳感器網絡(WSNs)[1]數據收集中，由于節點能量受限、感知數據存在冗余，因此,需要對數據進行壓縮處理以節省網絡能耗。壓縮感知(compressive sensing，CS)理論[2]應用于傳感器網絡數據收集可以有效地減少數據量，并實現很好的能耗均衡。

近年來，基于壓縮感知的WSNs分簇數據收集已將有很多研究。文獻[3]采用隨機稀疏觀測矩陣，減少了單次數據收集參與節點數目、優化了簇頭數目以保證能耗最優。文獻[4]則優化了采用Hybrid-CS下分簇數據收集的能耗，給出了集中式和分布式兩種數據收集方案。文獻[5]采用對角分塊矩陣作為觀測矩陣，分析網絡能耗并給出了一種集中式分簇方案。本文采用稀疏分塊對角矩陣(sparse block diagonal matrices，SBDM)[6]作為觀測矩陣，以一輪數據收集的能耗為優化目標，采用分布式分簇機制，提出了一種基于SBDM的分簇(SBDM-based clustering，SBDMC)數據收集算法。

本文介紹了壓縮感知中觀測矩陣的設計，分析了通信能耗，給出網絡總能耗；最后根據最優簇頭數目，提出SBDMC算法，并進行性能的分析與對比。

1壓縮感知數據收集

在壓縮感知數據收集中，節點采集的數據x=[x1,x2,…,xn]T可以看作是一個n維的原始信號。如果在稀疏基Ψ下可以稀疏表示為稀疏度為k的稀疏信號θ，通過簡單的線性變換可以變為M維(m?n)的觀測值y，從而減少通信量。在后端通過已有的正交匹配追蹤(OMP),誤差反向(BP)算法等成熟的重構算法，可以高精度重構原始數據。觀測矩陣的設計是壓縮感知數據收集的重要內容。

觀測矩陣的設計需要盡可能減少參與數據收集的節點數目，同時需要結合傳感器網絡特點便于在節點處分布式實現。本文采用SBDM作為觀測矩陣，矩陣中各元素以稀疏隨機矩陣[7]的生成方式生成，每個元素以1/s的概率取非零值。參數s表征矩陣的稀疏程度，取N/s=lgN，矩陣中每一行平均有N/s=lgN個非零元素。矩陣以對角陣的形式組成觀測矩陣，數據收集的具體實現如式(1)

(1)

其中，Φh為每個簇的對應對角陣中的一項在每次數據收集過程中各節點分布式生成觀測矩陣的一列，在每次數據收集過程中對應項系數非零的節點將感知數據權值發送到簇頭，簇頭壓縮后得到一個觀測值。每個簇頭平均收集M/h個觀測值，簇頭之間不再進一步壓縮，Sink可以收集到M個觀測值以重構原始數據。文獻[8]以高斯隨機矩陣為例證明在離散余弦變換(discretecosinetransform,DCT)基下BDM滿足壓縮感知的RIP條件。

2網絡能耗與最優簇頭數目

在分簇路由中，網絡能耗主要分為兩部分：簇內節點上傳至簇頭的能耗和簇頭數據上傳至Sink的能耗，即

(2)

(3)

E(d2)=?r3f(r,θ)drdθ

(4)

由式(3)和式(4)可知，簇內平均通信能耗為

(5)

(6)

網絡總的能耗為

(7)

(8)

根據卡爾丹公式可得最優簇頭數目為

(9)

3分簇路由的數據收集算法

要想在實際網絡中實現網絡能耗最優，需要保證分簇的規模大小一致、簇頭位于簇中心，這很難實現。結合壓縮感知自身具備能耗均衡的特點，本文提出一種簇頭數目固定的分布式分簇數據收集策略，主要包括三個部分：首輪分簇、簇頭輪換機制以及數據收集策略。

首輪分簇：

1)Sink根據網絡實際情況計算最優簇頭數目hopt、觀測次數M，將網絡劃分為規模大小盡量相等的hopt個簇，選擇中心節點為簇頭；

2)Sink發送簇頭信息給每個簇頭節點，簇頭廣播自身信息，普通節點選擇距離最近的簇頭節點作為自身簇頭；

3)節點向簇頭發送請求信息，簇頭恢復確認消息完成首輪分簇。

簇頭輪換機制：通過上文分析可知，簇頭需要消耗更多的能量，而簇內節點距離簇頭越近能耗越小。在余下輪的數據收集中采用基于節點剩余能量的簇頭輪換機制，選擇簇內剩余能量最大的節點作為簇頭，距離簇內節點最近的節點成為下一輪簇頭的概率最大。在一定程度上保證簇規模相等、且簇頭節點位于簇中心。

分簇完成后開始數據收集，具體實現步驟如下：

1)簇頭確定觀測次數，并將數據收集劃分為M/h個時段，每個時段完成一個觀測值數據收集，進一步為個節點分配時隙；

2)節點在對應時隙內，如果對應感知數據權值非零，則將其發送至簇頭，簇頭將一個時段收集的數據權值求和得到一個觀測值；3)簇頭將壓縮后的M/h個觀測值經距離平方最短路徑發送到Sink。

在數據收集過程中，簇與簇之間不再進一步壓縮，每個簇只需要收集M/h個觀測值即可在Sink重構原始數據，減少能耗的同時也降低了數據收集的時延。

4仿真分析

本節利用Matlab仿真工具進行仿真分析驗證。設400個節點隨機分布在200 m×200 m的正方形監測區域范圍內。節點能量為1 J，數據包長度為1 024 bit，能耗參數按照文獻[9]設置。本文將提出算法與已有的分簇數據收集算法相比較。對比的分簇數據收集算法包括：

1)LEACH-NC算法，為保證Sink可以重構原始數據以LEACH算法構建分簇的路由，但簇頭不對收集到的數據進行壓縮處理。

2)文獻[5]提出的基于稀疏投影的能量有效數據收集策略(ECDC)。以單次數據收集能耗為優化目標，計算最優簇頭數目，簇頭之間構建最短生成樹路由進一步壓縮。

在LEACH-NC中，為獲得最優的簇頭數目，圖 1給出了不同網絡環境下網絡壽命隨簇頭比例變化。以死亡10%節點死亡時的數據收集輪數作為網絡壽命。在Sink遠離網絡、Sink在網絡邊界以及Sink在網絡中心三種網絡環境下最優的簇頭比例分別為0.05,0.03,0.02。在能耗分析中，以最優簇頭比例進行數據收集。

圖1　LEACH-NC不同簇頭概率下的網絡壽命Fig 1　Network lifetime of LEACH-NC under different cluster head probabilities

根據上文的理論計算模型，取N/s=lgN≈2.6，可以得到最優簇頭數目為8。在壓縮比ρ=M/N=0.2的條件下，得到三種網絡環境下死亡節點數目隨數據收集輪數的變化，如圖 2所示。可以得到：1)在網絡能耗和生存壽命方面，本文提出的SBDMC算法性能要優于ECDC和LEACH-NC算法。2)采用壓縮感知進行數據收集的ECDC和SBDMC算法中，節點在某幾輪數據收集內擊中死亡，具有很好的能耗均衡性。

5結束語

本文采用SBDM作為壓縮感知觀測矩陣，進一步減少了參與數據收集的節點數目。根據分析稀疏對角觀測矩陣進行數據收集的特點建立網絡能耗模型，通過分析該能耗模型，計算得到最優能耗簇頭數目。聯合節點剩余能量和最優簇頭數目，給出一種簇頭數目固定的基于節點剩余能量進行簇頭輪換的分布式分簇策略，在減少網絡能耗的同時實現了網絡中各節點能耗均衡。仿真分析表明:與已有算法相比，本文提出算法減少網絡能耗、延長了網絡壽命。

圖2　不同網絡環境下死亡節點數目Fig 2　Number of dead nodes in different networks

參考文獻:

[1]Akyildiz I F,Su W,Sankarasubramaniam Y,et al.Wireless sensor networks:A survey[J].Computer Networks,2002,38(4):393-422.

[2]Donoho D L.Compressed sensing[J].IEEE Transactions on Information Theory,2006,52(4):1289-1306.

[3]Wu X,Xiong Y,Huang W,et al.An efficient compressive data gathering routing scheme for large-scale wireless sensor network-s[J].Computers & Electrical Engineering,2013,39(6):1935-1946.

[4]Xie R,Jia X.Transmission-efficient clustering method for wireless sensor networks using compressive sensing[J].IEEE Transactions on Parallel and Distributed Systems,2014,25(3):806-815.

[5]Nguyen M T,Teague K A.Compressive sensing based data gathering in clustered wireless sensor networks[C]∥2014 IEEE International Conference on Distributed Computing in Sensor Systems (DCISS),IEEE,2014:187-192.

[6]Park J Y,Yap H L,Rozell C J,et al.Concentration of measure for block diagonal matrices with applications to compressive signal processing[J].IEEE Transactions on Signal Processing,2011,59(12):5859-5875.

[7]Wang W,Garofalakis M,Ramchandran K.Distributed sparse random projections for refinable approximation[C]∥Proceedings of the 6th Int’l Conf on Information Processing in Sensor Network,ACM,2007:331-339.

[8]Yap H L,Eftekhari A,Wakin M B,et al.The restricted isometry property for block diagonal matrices[C]∥2011 45th Annual Conference on Information Sciences and Systems (CISS),IEEE,2011:1-6.

王沖(1989-)，男，山東淄博人，碩士研究生，研究方向為無線傳感網。

Clustering data gathering algorithm for wireless sensor networks based on compressive sensing*

WANG Chong, ZHANG Xia, LI Ou

(School of Information System Engineering,Information Engineering University,Zhengzhou 450001,China)

Abstract:Aiming at characteristics of energy limitation and unreliable communication link of wireless sensor networks(WSNs),a sparse block diagonal matrices clustering(SBDMC)routing data gathering algorithm for compressive sensing is presented.Sparse block diagonal matrix is used as measurement matrix to reduce number of gathering participated nodes;data is collected distributively by distributive cluster routing;and the optimal number of cluster head is obtained by analyzing energy consumption model.On the basis of the above research,an efficient clustering routing data gathering algorithm is proposed.The simulation results show that compared with the existing algorithms,the proposed algorithm can effectively reduce the energy consumption,prolong network lifetime and balance the energy consumption load.

Key words:wireless sensor networks(WSNs); compressive sensing(CS); data aquisition

作者簡介:

中圖分類號:TP 393

文獻標識碼:A

文章編號:1000—9787(2016)01—0142—04

*基金項目：國家科技重大專項資助課題(2014ZX03006003)

收稿日期：2015—04—30

DOI:10.13873/J.1000—9787(2016)01—0142—04