王　沖， 張　霞， 李　鷗

(信息工程大學(xué) 信息系統(tǒng)工程學(xué)院，河南 鄭州 450001)

?

無線傳感器網(wǎng)絡(luò)中基于壓縮感知的分簇?cái)?shù)據(jù)收集算法*

王沖， 張霞， 李鷗

(信息工程大學(xué) 信息系統(tǒng)工程學(xué)院，河南 鄭州 450001)

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

關(guān)鍵詞:無線傳感器網(wǎng)絡(luò)； 壓縮感知； 數(shù)據(jù)收集

0引言

在無線傳感器網(wǎng)絡(luò)(WSNs)[1]數(shù)據(jù)收集中，由于節(jié)點(diǎn)能量受限、感知數(shù)據(jù)存在冗余，因此,需要對數(shù)據(jù)進(jìn)行壓縮處理以節(jié)省網(wǎng)絡(luò)能耗。壓縮感知(compressive sensing，CS)理論[2]應(yīng)用于傳感器網(wǎng)絡(luò)數(shù)據(jù)收集可以有效地減少數(shù)據(jù)量，并實(shí)現(xiàn)很好的能耗均衡。

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

本文介紹了壓縮感知中觀測矩陣的設(shè)計(jì)，分析了通信能耗，給出網(wǎng)絡(luò)總能耗；最后根據(jù)最優(yōu)簇頭數(shù)目，提出SBDMC算法，并進(jìn)行性能的分析與對比。

1壓縮感知數(shù)據(jù)收集

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

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

(1)

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

2網(wǎng)絡(luò)能耗與最優(yōu)簇頭數(shù)目

在分簇路由中，網(wǎng)絡(luò)能耗主要分為兩部分：簇內(nèi)節(jié)點(diǎn)上傳至簇頭的能耗和簇頭數(shù)據(jù)上傳至Sink的能耗，即

(2)

(3)

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

(4)

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

(5)

(6)

網(wǎng)絡(luò)總的能耗為

(7)

(8)

根據(jù)卡爾丹公式可得最優(yōu)簇頭數(shù)目為

(9)

3分簇路由的數(shù)據(jù)收集算法

要想在實(shí)際網(wǎng)絡(luò)中實(shí)現(xiàn)網(wǎng)絡(luò)能耗最優(yōu)，需要保證分簇的規(guī)模大小一致、簇頭位于簇中心，這很難實(shí)現(xiàn)。結(jié)合壓縮感知自身具備能耗均衡的特點(diǎn)，本文提出一種簇頭數(shù)目固定的分布式分簇?cái)?shù)據(jù)收集策略，主要包括三個(gè)部分：首輪分簇、簇頭輪換機(jī)制以及數(shù)據(jù)收集策略。

首輪分簇：

1)Sink根據(jù)網(wǎng)絡(luò)實(shí)際情況計(jì)算最優(yōu)簇頭數(shù)目hopt、觀測次數(shù)M，將網(wǎng)絡(luò)劃分為規(guī)模大小盡量相等的hopt個(gè)簇，選擇中心節(jié)點(diǎn)為簇頭；

2)Sink發(fā)送簇頭信息給每個(gè)簇頭節(jié)點(diǎn)，簇頭廣播自身信息，普通節(jié)點(diǎn)選擇距離最近的簇頭節(jié)點(diǎn)作為自身簇頭；

3)節(jié)點(diǎn)向簇頭發(fā)送請求信息，簇頭恢復(fù)確認(rèn)消息完成首輪分簇。

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

分簇完成后開始數(shù)據(jù)收集，具體實(shí)現(xiàn)步驟如下：

1)簇頭確定觀測次數(shù)，并將數(shù)據(jù)收集劃分為M/h個(gè)時(shí)段，每個(gè)時(shí)段完成一個(gè)觀測值數(shù)據(jù)收集，進(jìn)一步為個(gè)節(jié)點(diǎn)分配時(shí)隙；

2)節(jié)點(diǎn)在對應(yīng)時(shí)隙內(nèi)，如果對應(yīng)感知數(shù)據(jù)權(quán)值非零，則將其發(fā)送至簇頭，簇頭將一個(gè)時(shí)段收集的數(shù)據(jù)權(quán)值求和得到一個(gè)觀測值；3)簇頭將壓縮后的M/h個(gè)觀測值經(jīng)距離平方最短路徑發(fā)送到Sink。

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

4仿真分析

本節(jié)利用Matlab仿真工具進(jìn)行仿真分析驗(yàn)證。設(shè)400個(gè)節(jié)點(diǎn)隨機(jī)分布在200 m×200 m的正方形監(jiān)測區(qū)域范圍內(nèi)。節(jié)點(diǎn)能量為1 J，數(shù)據(jù)包長度為1 024 bit，能耗參數(shù)按照文獻(xiàn)[9]設(shè)置。本文將提出算法與已有的分簇?cái)?shù)據(jù)收集算法相比較。對比的分簇?cái)?shù)據(jù)收集算法包括：

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

2)文獻(xiàn)[5]提出的基于稀疏投影的能量有效數(shù)據(jù)收集策略(ECDC)。以單次數(shù)據(jù)收集能耗為優(yōu)化目標(biāo)，計(jì)算最優(yōu)簇頭數(shù)目，簇頭之間構(gòu)建最短生成樹路由進(jìn)一步壓縮。

在LEACH-NC中，為獲得最優(yōu)的簇頭數(shù)目，圖 1給出了不同網(wǎng)絡(luò)環(huán)境下網(wǎng)絡(luò)壽命隨簇頭比例變化。以死亡10%節(jié)點(diǎn)死亡時(shí)的數(shù)據(jù)收集輪數(shù)作為網(wǎng)絡(luò)壽命。在Sink遠(yuǎn)離網(wǎng)絡(luò)、Sink在網(wǎng)絡(luò)邊界以及Sink在網(wǎng)絡(luò)中心三種網(wǎng)絡(luò)環(huán)境下最優(yōu)的簇頭比例分別為0.05,0.03,0.02。在能耗分析中，以最優(yōu)簇頭比例進(jìn)行數(shù)據(jù)收集。

圖1　LEACH-NC不同簇頭概率下的網(wǎng)絡(luò)壽命Fig 1　Network lifetime of LEACH-NC under different cluster head probabilities

根據(jù)上文的理論計(jì)算模型，取N/s=lgN≈2.6，可以得到最優(yōu)簇頭數(shù)目為8。在壓縮比ρ=M/N=0.2的條件下，得到三種網(wǎng)絡(luò)環(huán)境下死亡節(jié)點(diǎn)數(shù)目隨數(shù)據(jù)收集輪數(shù)的變化，如圖 2所示?？梢缘玫剑?)在網(wǎng)絡(luò)能耗和生存壽命方面，本文提出的SBDMC算法性能要優(yōu)于ECDC和LEACH-NC算法。2)采用壓縮感知進(jìn)行數(shù)據(jù)收集的ECDC和SBDMC算法中，節(jié)點(diǎn)在某幾輪數(shù)據(jù)收集內(nèi)擊中死亡，具有很好的能耗均衡性。

5結(jié)束語

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

圖2　不同網(wǎng)絡(luò)環(huán)境下死亡節(jié)點(diǎn)數(shù)目Fig 2　Number of dead nodes in different networks

參考文獻(xiàn):

[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-)，男，山東淄博人，碩士研究生，研究方向?yàn)闊o線傳感網(wǎng)。

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

文獻(xiàn)標(biāo)識碼:A

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

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

收稿日期：2015—04—30

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