無線傳感器網(wǎng)絡(luò)中基于稀疏投影的數(shù)據(jù)收集方案

李鵬，王建新

?

無線傳感器網(wǎng)絡(luò)中基于稀疏投影的數(shù)據(jù)收集方案

李鵬1, 2，王建新1

(1. 中南大學(xué)信息科學(xué)與工程學(xué)院，湖南長沙，410083；2. 湖南中醫(yī)藥大學(xué)管理與信息工程學(xué)院，湖南長沙，410208)

考慮到現(xiàn)有的基于壓縮感知的數(shù)據(jù)收集方法大多采用密集投影來收集節(jié)點的數(shù)據(jù)，導(dǎo)致數(shù)據(jù)傳輸代價過高、節(jié)點能耗過快縮短了網(wǎng)絡(luò)生命周期，提出一種基于稀疏投影的數(shù)據(jù)收集方案(DGSP)。其步驟為：首先，設(shè)計一種基于最小化傳輸開銷的稀疏投影矩陣用于節(jié)點數(shù)據(jù)采樣，并利用亞高斯分布的尾部有界性證明其RIP性質(zhì)；然后，以網(wǎng)絡(luò)負載均衡和網(wǎng)絡(luò)生命周期最大化為目標來構(gòu)建數(shù)據(jù)收集樹，并將樹中節(jié)點的下一跳選擇問題建模成半匹配問題；最后，提出改進的Hungarian算法在多項式時間內(nèi)解決它。仿真結(jié)果表明：相比于目前典型的CDG，EDCA和MTT方案而言，DGSP的數(shù)據(jù)重構(gòu)誤差、能耗和延時等更低。

無線傳感器網(wǎng)絡(luò)；數(shù)據(jù)收集；壓縮感知；稀疏投影；半匹配；能耗

無線傳感器網(wǎng)絡(luò)(wireless sensor networks, WSN)是近年來國內(nèi)外廣泛關(guān)注的研究熱點[1?2]。無線傳感器網(wǎng)絡(luò)在工作過程中，節(jié)點會不斷地感知和采集周邊物理環(huán)境的數(shù)據(jù)，并將通過無線天線將數(shù)據(jù)以多跳的方式發(fā)送給遠方的Sink節(jié)點(或稱為基站)進行處理，即進行數(shù)據(jù)收集[3]。由于節(jié)點只有有限的能量以及有限的存儲、計算和通信能力，如何有效地解決網(wǎng)絡(luò)負載失衡、數(shù)據(jù)收集延時較大等問題，以使網(wǎng)絡(luò)能長時間地工作并滿足數(shù)據(jù)收集的應(yīng)用需求，是目前數(shù)據(jù)收集中面臨的主要問題[4?5]。壓縮感知[6](compressive sensing, CS)也被稱為壓縮采樣或稀疏采樣，是一種利用稀疏的或可壓縮的信號進行信號重建的技術(shù)。基于壓縮感知的數(shù)據(jù)收集方法能夠節(jié)省傳統(tǒng)采樣方式前期所需的存儲空間和計算資源，而將上述資源用于后期的恢復(fù)算法中，因此，將壓縮感知技術(shù)應(yīng)用到數(shù)據(jù)收集中具有重要意義。CHENG等[7]提出一種基于矩陣完成技術(shù)的數(shù)據(jù)收集方案EDCA。該方案首先隨機地選擇部分節(jié)點來進行數(shù)據(jù)采樣和編碼并將其結(jié)果直接傳到Sink，然后Sink基于核范數(shù)優(yōu)化技術(shù)進行數(shù)據(jù)的重構(gòu)。XIE等[8]提出一種基于最小化傳輸次數(shù)的數(shù)據(jù)收集方案MTT。該方法認為用于進行壓縮采樣的投影矩陣中經(jīng)常包含很多零值，為了節(jié)省傳輸開銷，只需要選擇節(jié)點中的那些投影向量為非零值(即自身有數(shù)據(jù)需要傳輸)的輪次來建立路由路徑，實現(xiàn)數(shù)據(jù)收集，并構(gòu)建一顆具有最小化總傳輸次數(shù)的數(shù)據(jù)收集樹，通過一種啟發(fā)式算法予以解決。然而，該方案假定數(shù)據(jù)每次傳輸開銷為1，這與真實應(yīng)用場景不相符，方案的局限性較大。CHUN 等[9]基于壓縮感知技術(shù)研究了在數(shù)據(jù)收集過程中對傳感器節(jié)點進行投影操作時，如何在節(jié)點的單位能量消耗下最大化信息增益，并提出了3種啟發(fā)式算法予以解決。劉卉等[10]提出一種基于投影矢量的雙組播樹高效路由數(shù)據(jù)收集，該算法將貝葉斯壓縮感知理論與傳感器路由相結(jié)合，解決了現(xiàn)有算法不能滿足傳感器對能耗敏感的問題。SAEED等[11]提出利用人工智能技術(shù)來建立數(shù)據(jù)融合樹以最大化基于壓縮感知進行數(shù)據(jù)融合帶來的優(yōu)點，進而延長傳感器網(wǎng)絡(luò)的生命周期，降低傳輸延時。LUO等[12]提出了CDG方案用于大規(guī)模無線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)收集，首先設(shè)計了1種分塊的投影矩陣來采集節(jié)點數(shù)據(jù)，然后Sink節(jié)點基于最短路徑樹來收集各個節(jié)點得到的投影值，節(jié)省了傳輸開銷，取得了較高的數(shù)據(jù)重構(gòu)精度。然而，總體來說，以上基于壓縮感知的數(shù)據(jù)收集方法采用密集投影矩陣進行節(jié)點數(shù)據(jù)的采樣，沒有考慮如何將投影矩陣設(shè)計與無線傳感器網(wǎng)絡(luò)特性相結(jié)合以節(jié)省網(wǎng)絡(luò)能耗，從而導(dǎo)致數(shù)據(jù)收集的能耗較高，縮短了網(wǎng)絡(luò)的生命周期。為此，本文作者提出一種基于稀疏投影的數(shù)據(jù)收集方案(DGSP)。結(jié)合無線傳感器網(wǎng)絡(luò)的傳輸特性，分析投影操作與數(shù)據(jù)稀疏程度的關(guān)系，設(shè)計一種基于最小化傳輸開銷的稀疏投影矩陣，并利用亞高斯分布的尾部有界性證明其RIP性質(zhì)，然后以網(wǎng)絡(luò)負載均衡和網(wǎng)絡(luò)生命周期最大化為目標構(gòu)建數(shù)據(jù)收集樹，并將樹中節(jié)點的下一跳選擇問題建模成半匹配問題，最后提出改進的Hungarian算法在多項式時間內(nèi)解決此問題。

1 問題建模

1.1 網(wǎng)絡(luò)模型

設(shè)個傳感器節(jié)點隨機地分布在1個面積為×的正方形區(qū)域內(nèi)。整個傳感器網(wǎng)絡(luò)組成1個連通的無向圖(，)(其中，為傳感器節(jié)點集合，={1，2，…，V}，||=+1；為圖中邊的集合，若2個傳感器節(jié)點V和V相互處于對方的通信半徑內(nèi)，則(V，V)∈)。為了使算法具有可擴展性，節(jié)點不需要知道自己的位置信息，只要求節(jié)點知道自己的鄰居信息，這可以很容易地通過相互交換1個“Hello”消息來實現(xiàn)[13]。此外，網(wǎng)絡(luò)具有如下性質(zhì)。

1) 網(wǎng)絡(luò)是連通的靜態(tài)網(wǎng)絡(luò)，傳感器節(jié)點和Sink部署后不再移動，Sink位于網(wǎng)絡(luò)的中心，節(jié)點的傳輸半徑相等。

2) 節(jié)點的初始能量是異構(gòu)的，而且不能補充，網(wǎng)絡(luò)中節(jié)點采用的能量消耗模型如下：

其中：tr和re分別為發(fā)送數(shù)據(jù)和接收數(shù)據(jù)消耗的能量；amp為多路衰減模型的功率放大系數(shù)；為源節(jié)點到目標節(jié)點的距離；packet為數(shù)據(jù)包的大小。所有節(jié)點使用相同的發(fā)射功率和接收功率。

1.2 相關(guān)定義

為了描述方便，現(xiàn)給出本文中用到的相關(guān)定義。

定義1：RIP(restricted isometry property)性質(zhì)[6]。對于任意的信號(表示稀疏向量集合)，若存在常數(shù)，則有下面的不等式成立：

定義2：亞高斯分布[14]。給定任意的隨機變量，若存在1個常數(shù)＞0，使得對于任意的，有下面不等式成立：

則稱該隨機變量服從亞高斯分布。

定義3：節(jié)點的生命周期(輪)。任一節(jié)點v在1顆樹中存活的輪數(shù)為

定義4：樹的生命周期(輪)。指樹中第1個節(jié)點v死亡時，該節(jié)點已經(jīng)進行數(shù)據(jù)收集的輪數(shù)：

定義6：半匹配[15]。給定1個二分圖，其中。若在圖中存在1個邊集()，使得中的每個節(jié)點僅僅是中1條邊的端點，則稱屬于半匹配。

1.3 問題描述

無線傳感器網(wǎng)絡(luò)一般部署在比較危險或人類很難進入的區(qū)域，傳感器節(jié)點往往是無法替換的，因此，希望網(wǎng)絡(luò)能工作盡可能長時間。已有研究表明[16]，基于壓縮感知的數(shù)據(jù)收集方法能實現(xiàn)網(wǎng)絡(luò)負載均衡，降低數(shù)據(jù)傳輸開銷，進而延長網(wǎng)絡(luò)生命周期。依據(jù)1.1節(jié)中的網(wǎng)絡(luò)模型，基于壓縮感知進行數(shù)據(jù)收集的基本過程為：設(shè)所有節(jié)點的原始數(shù)據(jù)表示為×1的列向量。由于網(wǎng)絡(luò)數(shù)據(jù)的時空相關(guān)性，在某一變換基上可被稀疏表示為，然后采用1個與不相關(guān)的測量矩陣對進行測量，得到的測量值，最后，當Sink節(jié)點收到個測量值后，通過求解1范數(shù)最小化問題就能精確地重構(gòu)出，如圖1所示。

綜上所述，本文研究的問題是：如何設(shè)計一種基于傳輸開銷最小化的稀疏投影矩陣來收集各個節(jié)點的數(shù)據(jù)，并結(jié)合的設(shè)計來建立1顆優(yōu)化的數(shù)據(jù)收集樹，從而實現(xiàn)數(shù)據(jù)收集的高精確度與網(wǎng)絡(luò)生命周期的最大化。

圖1 基于壓縮感知的數(shù)據(jù)收集

2 稀疏投影矩陣設(shè)計

2.1 主要思路

在無線傳感器網(wǎng)絡(luò)中，目前大多數(shù)基于壓縮感知的數(shù)據(jù)收集方法都采用密集投影矩陣，如隨機高斯矩陣、以隨機±1為原始構(gòu)成的Rademacher矩陣等，這些矩陣與大多數(shù)固定正交基構(gòu)成的矩陣不相關(guān)，因此，很容易滿足RIP性質(zhì)，成為目前投影矩陣的首選。然而，事實上，在無線傳感器網(wǎng)絡(luò)中，由于節(jié)點采集到的大量數(shù)據(jù)是稀疏的，節(jié)點之間的數(shù)據(jù)具有相關(guān)性，因此，密集投影并不是必需的，它會帶來巨大的計算開銷和傳輸開銷，浪費了節(jié)點的能量[17]。為此，本文設(shè)計一種基于最小化傳輸開銷的投影矩陣，該矩陣在滿足RIP性質(zhì)的前提下，能夠使網(wǎng)絡(luò)傳輸?shù)哪芰块_銷最小。

2.2 RIP性質(zhì)證明

據(jù)壓縮感知理論，以遠少于Nyquist—Shanon的要求對原始數(shù)據(jù)進行采樣之所以還能夠?qū)崿F(xiàn)數(shù)據(jù)精確重構(gòu)的關(guān)鍵在于投影矩陣滿足一定階數(shù)的RIP性質(zhì)。投影矩陣滿足RIP性質(zhì)的驗證較困難，對于采樣的稀疏信號需要驗證個矩陣。為了解決該問題，本文根據(jù)文獻[18]和亞高斯分布的尾部有界性定理，給出驗證RIP性質(zhì)的方法。

引理1：給定任意正整數(shù)，和0＜＜1，若存在階隨機矩陣的概率分布滿足如下不等式：

則存在常數(shù)0＞0和1＞0，使得對給定的和任意的，以超過的概率使式(2)成立。

引理2[14]：設(shè)r為服從亞高斯投影分布且具有單位方差的隨機變量，，則對任意的，有

則

顯然，當取由式(9)定義的0時，式(14)的右邊達到最小，即

式(7)成立。證畢。

3 數(shù)據(jù)收集樹

3.1 能耗分析

下面通過1個例子分析數(shù)據(jù)收集樹的構(gòu)造與網(wǎng)絡(luò)生命周期的關(guān)系。數(shù)據(jù)收集樹的能耗分析結(jié)果如圖2所示，其中，實線表示存在通信鏈路，虛線表示不存在通信鏈路。假設(shè)傳感器節(jié)點1，2，3和4的初始能量分別為2，6，4和3 J，每個節(jié)點1次傳輸數(shù)據(jù)和接收數(shù)據(jù)的能耗為1(見圖2(a))。從圖2(b)可以看到：在每輪的數(shù)據(jù)收集中，節(jié)點2從節(jié)點3和4接收數(shù)據(jù)，然后加上自身的數(shù)據(jù)向Sink轉(zhuǎn)發(fā)，消耗的能量為3 J，其他節(jié)點消耗的能量為1，因此，網(wǎng)絡(luò)的生命周期為2輪。而從圖2(c)可以看到：在每輪的數(shù)據(jù)收集中，節(jié)點2每輪消耗的能量為2，其他節(jié)點為1，因此，網(wǎng)絡(luò)的生命周期為1?？梢姡簽楣?jié)點選擇最優(yōu)的下一跳來實現(xiàn)節(jié)點數(shù)據(jù)的轉(zhuǎn)發(fā)，對于節(jié)省能量、延長網(wǎng)絡(luò)生命周期具有重要意義。

(a) 初始的網(wǎng)絡(luò)拓撲；(b) 拓撲1；(c) 拓撲2

1) 若節(jié)點v是葉子節(jié)點，且，則E=0。

2) 若節(jié)點v是葉子節(jié)點，且，節(jié)點v的父親節(jié)點為v，則。

3) 若節(jié)點v不是葉子節(jié)點，且，節(jié)點v有個孩子節(jié)點，則

4) 若節(jié)點v不是葉子節(jié)點，且，節(jié)點v有個孩子節(jié)點，則

3.2 基于稀疏投影的數(shù)據(jù)收集(DGSP)

算法1：基于稀疏投影的數(shù)據(jù)收集。

輸入：無向連通圖(，)，和節(jié)點的能量。

輸出：數(shù)據(jù)收集樹。

步驟1 初始時，圖僅包含Sink節(jié)點，從Sink節(jié)點出發(fā)將通信半徑內(nèi)的所有1跳鄰居加入。

步驟2 從1跳鄰居出發(fā)將其通信半徑內(nèi)的所有節(jié)點加入，迭代地執(zhí)行，直到網(wǎng)絡(luò)中的所有節(jié)點都加入到圖中，形成全連通圖。

步驟3 從Sink節(jié)點出發(fā)，對圖進行廣度優(yōu)先遍歷，得到節(jié)點訪問序列：，存入堆棧中。

根據(jù)圖1所示的數(shù)據(jù)收集模型，設(shè)傳感器節(jié)點的原始數(shù)據(jù)可表示為向量，依據(jù)設(shè)計的投影矩陣，各個傳感器節(jié)點的原始數(shù)據(jù)首先可被壓縮采樣表示為：，然后各個傳感器節(jié)點將其被壓縮采樣后的數(shù)據(jù)沿著算法1中的數(shù)據(jù)收集樹上傳至Sink，Sink則依據(jù)已知的和，采用OMP算法求解1范數(shù)最小化問題，即可以實現(xiàn)對各個節(jié)點上原始數(shù)據(jù)的精確重構(gòu)。

3.3 半匹配問題

如算法1中步驟4所示，當節(jié)點和的父節(jié)點有多個父節(jié)點時，它們的下一跳選擇問題即為半匹配問題，它是二分圖匹配問題的1種特例，Hungarian 算法[19]是目前求解這問題的最典型手段。然而，將Hungarian算法直接用于無線傳感器網(wǎng)絡(luò)中節(jié)點的下一跳選擇時，由于算法本身的時間復(fù)雜度較高、迭代過程繁雜，會導(dǎo)致節(jié)點能量消耗過快。為了實現(xiàn)數(shù)據(jù)收集樹的負載均衡和延長網(wǎng)絡(luò)生命周期，本文提出改進的Hungarian算法用于求解節(jié)點的下一跳選擇問題。

算法2：半匹配求解算法。

步驟1：初始時，設(shè)置隊列={ }。

//是寬度優(yōu)先搜索中首先被訪問的節(jié)點集合

步驟3：While非空。

Else

End

End

End

End

End

End

4 仿真實驗

為了驗證不同方案的性能，以Matlab2012為工具，采用CitySee系統(tǒng)[20]測得的溫度進行一系列仿真實驗，考察方案DGSP在不同噪聲環(huán)境下進行數(shù)據(jù)收集的精確性和能量有效性，并與目前較典型的CDG[12]，EDCA[7]和MTT[8]這3種方案進行對比分析。測試所使用的軟硬件環(huán)境如下：Inter(R) Core(M) i3-3240 CPU 3.40 GHz, 500 G硬盤，4.0 GB內(nèi)存，Microsoft Windows 7 Professional。

在本文仿真中，設(shè)在高斯噪聲所涉及的無線傳感器網(wǎng)絡(luò)中總共有= 1 000節(jié)點。1 000個傳感器節(jié)點被隨機分布在區(qū)域為50 m×50 m的監(jiān)測區(qū)域內(nèi)；節(jié)點間的同步通過物理層和數(shù)據(jù)鏈路層來實現(xiàn)，其中，數(shù)據(jù)鏈路層采用IEEE802.15.4標準中的CSMA/CA機制來進行空閑偵聽和沖突避免，物理層則采用2.4 GHz頻段，其數(shù)據(jù)傳輸率為250 kb/s。實驗參數(shù)設(shè)置為：每個節(jié)點的初始能量為50 J；節(jié)點接收和發(fā)送單位數(shù)據(jù)的能耗都為50×10?6J/bit；節(jié)點上收發(fā)電路的能耗為50×10?6J/bit；節(jié)點成功發(fā)送1位數(shù)據(jù)通過1 m距離的能耗為100×10?9J/bit/m2；節(jié)點上計算能耗為5×10?6J/bit；每個數(shù)據(jù)包的長度為1 024 bit；每個控制包的長度為64 bit。數(shù)據(jù)重構(gòu)算法采用OMP算法。

不同方案的衡量指標包括能耗、延時和重構(gòu)誤差等。其中，數(shù)據(jù)重構(gòu)誤差采用信噪比SNR和相對誤差RE來衡量：

圖3所示為DGSP與其他3種方案的數(shù)據(jù)重構(gòu)誤差比較結(jié)果。從圖3可以看到：隨著投影矩陣的測量次數(shù)增加，4種方案的數(shù)據(jù)重構(gòu)誤差都降低，但當測量次數(shù)小于400次時，DGSP的重構(gòu)誤差要稍比其他3種方案的高。這是由于DGSP依據(jù)設(shè)計的稀疏投影矩陣來進行節(jié)點的數(shù)據(jù)采樣，當測量次數(shù)較少時，這種采樣方式可能會導(dǎo)致部分節(jié)點的數(shù)據(jù)沒有被有效地收集，影響了數(shù)據(jù)重構(gòu)性能；而隨著投影矩陣測量次數(shù)的增加，DGSP的性能優(yōu)勢越來越明顯。這主要是因為DGSP充分考慮了相鄰節(jié)點上數(shù)據(jù)的相關(guān)性，當測量次數(shù)達到一定次數(shù)時，采用稀疏投影矩陣進行節(jié)點數(shù)據(jù)采樣可以克服由于受到網(wǎng)絡(luò)初始拓撲結(jié)構(gòu)的影響以及測量矩陣稀疏化所導(dǎo)致的數(shù)據(jù)丟失現(xiàn)象。因此，當測量次數(shù)大于400次時，DGSP的重構(gòu)誤差要遠比其他3種方案的低。

1—DGSP；2—CDG；3—MTT；4—EDCA。

圖4所示為DGSP與其他3種方案的數(shù)據(jù)收集能耗比較結(jié)果。從圖4可以看到：隨著SNR增大，不同方案的能耗都增大，在相同的SNR條件下，EDCA的能量開銷最大，而DGSP的能量開銷最??；當SNR從10 dB增加到50 dB時，相比于CDG，MTT和EDCA這3種方案，DGSP的能耗分別降低約23.34%，35.25%和44.94%。這主要是因為DGSP通過設(shè)計的稀疏投影矩陣進行節(jié)點數(shù)據(jù)采樣，減少了節(jié)點的傳輸開銷；另外，通過對節(jié)點的下一跳選擇問題進行優(yōu)化，實現(xiàn)了負載均衡，從而節(jié)省了節(jié)點能量。

圖5所示為DGSP與其他3種方案的網(wǎng)絡(luò)生命周期比較結(jié)果。從圖5可以看到：隨著投影矩陣的測量次數(shù)增加(意味著4種方案需要采樣并傳輸?shù)臄?shù)據(jù)量增加)，網(wǎng)絡(luò)的傳輸開銷增加導(dǎo)致網(wǎng)絡(luò)生命周期縮短。但總體來說，DGSP的網(wǎng)絡(luò)生命周期始終要優(yōu)于其他3種方案，其中，EDCA的網(wǎng)絡(luò)生命周期最短。這是因為MTT以最小化數(shù)據(jù)傳輸次數(shù)為目標，通過求解0?1線性規(guī)劃問題來構(gòu)建數(shù)據(jù)收集樹，相比于采用矩陣完成技術(shù)的EDCA，MTT的傳輸開銷更小，能耗更低。CDG則利用了感知數(shù)據(jù)的內(nèi)部相關(guān)性進行數(shù)據(jù)編碼，設(shè)計了一種半稀疏化的投影矩陣來進行壓縮采樣，能實現(xiàn)負載均衡，在降低全局通信開銷的同時并沒有引入復(fù)雜的計算開銷和傳輸控制開銷，因此，取得了比EDCA和MTT更好的結(jié)果。而DGSP在CDG的基礎(chǔ)上進一步對投影矩陣和數(shù)據(jù)傳輸路徑進行了優(yōu)化，因此，DGSP的網(wǎng)絡(luò)生命周期最長。

圖6所示為DGSP與其他3種方案的數(shù)據(jù)收集延時比較結(jié)果。從圖6可以看到：隨著SNR增大，4種方案的延時都增大，但總的來說，MTT的延時最低，DGSP的延時要略比CDG的低，EDCA的延時最高。這是由于EDCA采用密集投影進行節(jié)點的數(shù)據(jù)采樣，并且為了得到較高的SNR，EDCA需要進行多次矩陣運算，增加了計算開銷。而CDG和DGSP則都對數(shù)據(jù)傳輸路徑進行了優(yōu)化，降低了各個節(jié)點的數(shù)據(jù)傳輸跳數(shù)，取得了比EDCA更好的延時性能。MTT延時最低的主要原因是它假設(shè)每次數(shù)據(jù)傳輸開銷為1，以最小化數(shù)據(jù)傳輸次數(shù)為目標，從Sink出發(fā)，MTT迭代地找到1條具有最小的傳輸代價增加值的邊加入到最終的數(shù)據(jù)收集樹中。該方法雖然延時最低，但對于數(shù)據(jù)傳輸開銷的假設(shè)過于苛刻，而DGSP是更真實的網(wǎng)絡(luò)模型，取得了與MTT相近的延時性能，因此，本文認為DGSP是高效的，相比于MTT而言，更加適用于真實的無線傳感器網(wǎng)絡(luò)應(yīng)用環(huán)境。

1—DGSP；2—CDG；3—MTT；4—EDCA。

1—DGSP；2—CDG；3—MTT；4—EDCA。

1—EDCA；2—MTT；3—CDG；4—DGSP。

5 結(jié)論

1) 設(shè)計了一種基于最小化傳輸開銷的投影矩陣用于數(shù)據(jù)采樣。相比于密集投影矩陣而言，該矩陣在滿足RIP原則的前提下，利用了各個節(jié)點間感知數(shù)據(jù)的相關(guān)性來對矩陣進行稀疏化，在保證數(shù)據(jù)收集質(zhì)量的同時，顯著降低了網(wǎng)絡(luò)通信開銷。

2) 將采樣后的數(shù)據(jù)傳輸問題建模成半匹配問題，并提出一種半匹配問題求解算法為節(jié)點選擇最優(yōu)的下一跳，用于數(shù)據(jù)傳輸，最后以實現(xiàn)網(wǎng)絡(luò)負載均衡和網(wǎng)絡(luò)生命周期最大化為目標構(gòu)建了1顆數(shù)據(jù)收集樹。

3) 采用CitySee系統(tǒng)測得的溫度進行仿真實驗，結(jié)果表明，本文方法在降低數(shù)據(jù)重構(gòu)誤差和延時、節(jié)約能耗和延長網(wǎng)絡(luò)生命周期等方面要優(yōu)于目前較典型的CDG，EDCA和MTT等方案。

參考文獻：

[1] GUO Shuo, GU Yu, JIANG Bo, et al. Opportunistic flooding in low-duty-cycle wireless sensor networks with unreliable links[J]. IEEE Transactions on Computers, 2014, 63(11): 2787?2802.

[2] 崔莉, 鞠海玲, 苗勇, 等. 無線傳感器網(wǎng)絡(luò)研究進展[J]. 計算機研究與發(fā)展, 2015, 42(1): 163?174. CUI Li, JU Hailing, MIAO Yong, et al. Overview of wireless sensor networks[J]. Journal of Computer Research and Development, 2015, 42(1): 163?174.

[3] ZHAO Miao, LI Ji, YANG Yuanyuan. A framework of joint mobile energy replenishment and data gathering in wireless rechargeable sensor networks[J]. IEEE Transactions on Mobile Computing, 2014, 13(12): 2689?2705.

[4] MA Junchao, LOU Wei, LI Xiangyang. Contiguous link scheduling for data aggregation in wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(7): 1691?1701.

[5] 徐建波, 李仁發(fā). 無線傳感器網(wǎng)絡(luò)中一種新型的混合型數(shù)據(jù)收集協(xié)議[J]. 計算機研究與發(fā)展, 2015, 45(2): 254?260. XU Jianbo, LI Renfa. A Novel framework for miscellaneous data gathering in wireless sensor networks[J]. Journal of Computer Research and Development, 2015, 45(2): 254?260。

[6] KRAHMER F, WARD R. Stable and robust sampling strategies for compressive imaging[J]. IEEE Transactions on Image Processing, 2014, 23(2): 612?622.

[7] CHENG Jie, JIANG Hongbo, MA Xiaoqiang, et al. Efficient data collection with sampling in WSNs: making use of matrix completion techniques[C]//Proceedings of the Global Communications Conference(GLOBECOM). Miami, Florida, USA: IEEE Press, 2010: 1?5.

[8] XIE Ruitao, JIA Xiaohua. Minimun transmission data gathering trees for compressive sensing in wireless sensor networks[C]//Proceedings of the Global Communications Conference (GLOBECOM). Houston, Texas, USA: IEEE Press, 2011: 1?5.

[9] CHUN T C, RAJIB R, HU Wen. Energy efficient information collection in wireless sensor networks using adaptive compressive sensing[C]//The 34th IEEE Conference on Local Computer Networks(LCN). Zürich, Switzerland: IEEE Press, 2009: 443?450.

[10] 劉卉, 李澤軍. 基于投影矢量的雙組播樹高效路由數(shù)據(jù)收集[J]. 傳感技術(shù)學(xué)報, 2013, 26(4): 570?576. LIU Hui, LI Zejun. High-efficiency routing data collection of dual multicast tree based on the projection vector[J]. Chinese Journal of Sensors and Actuators, 2013, 26(4): 570?576.

[11] SAEED M, JAMSHID S, MIR M P. A novel intelligent energy-efficient delay-aware routing in WSN, based on compressive sensing[C]//The 5thIEEE International Symposium on Telecommunications(IST). Tehran, Iran: IEEE Press, 2010: 415?420.

[12] 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.

[13] 胡升澤, 包衛(wèi)東, 王博, 等. 無線傳感器網(wǎng)絡(luò)基于多元簇首的分簇數(shù)據(jù)收集算法[J]. 電子與信息學(xué)報, 2014, 36(2): 403?408. HU Shengze, BAO Weidong, WANG Bo, et al. Clustering data gathering algorithm based on multiple cluster heads for wireless sensor networks[J]. Journal of Electronics & Information Technology, 2014, 36(2): 403?408.

[14] 方紅, 章權(quán)兵, 韋穗. 基于亞高斯隨機投影的圖像重建方法[J]. 計算機研究與發(fā)展, 2008, 45(8): 1402?1407. FANG Hong, ZHANG Quanbing, WEI Sui. A method of image reconstruction based on sub-Gaussian random projection[J]. Journal of Computer Research and Development, 2008, 45(8): 1402?1407.

[15] HARVEY N J A, LADNER R E, LOVáSZ L, et al. Semi-matchings for bipartite graphs and load balancing[J]. Algorithms & Data Structures, 2013, 59(1): 294?306.

[16] 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 & Distributed Systems, 2015, 26(1): 35?44.

[17] CAIONE C, BRUNELLI D, BENINI L. Distributed compressive sampling for lifetime optimization in dense wireless sensor networks[J]. IEEE Transactions on Industrial Informatics, 2012, 8(1): 30?40.

[18] WANG W, GAROFALAKIS M, RAMCHANDRAN K. Distributed sparse random projections for refinable approximation[C]//ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN). Louis, Missouri, USA: ACM Press, 2007: 331?339.

[19] ALLEN W J, RIZZO R C. Implementation of the Hungarian algorithm to account for Ligand symmetry and similarity in structure-based design[J]. Journal of Chemical Information & Modeling, 2014, 54(2): 518?529.

[20] MAO Xufei, XIN Miao, HE Yuan, et al. CitySee: Urban CO2 monitoring with sensors[C]//Proceedings of the IEEE International Conference on Computer Communications (INFOCOM). Orlando, FL, USA: IEEE Press, 2012: 1611?1619.

(編輯 陳燦華)

Data gathering scheme based on sparse projection in wireless sensor networks

LI Peng1, 2, WANG Jianxin1

(1. School of Information Science and Engineering, Central South University, Changsha 410083, China;2. School of Management and Information Engineering, Hunan University of Chinese Medicine, Changsha 410208, China)

Considering that the existing data gathering schemes based on compressive sensing usually use the dense projection to achieve the sensor readings, which results in the higher transmission cost and the larger energy consumption, and thus shortens the lifetime of network, a data gathering scheme based on the sparse projection (DGSP) was proposed. The procedures were as follows. Firstly, the sparse projection matrix based on the minimization of the transmission overhead was designed for the sampling at the nodes, and the nature of its RIP was proved by the sub-Gaussian distribution tail roundedness. A data gathering tree was then constructed based on the load balancing of network and the maximum lifetime of network, and the next hop selection problem of the nodes was modeled into the semi-matching problem. An improved Hungarian algorithm was finally proposed to solve it in the polynomial time. The simulation results show that, compared with the CDG, EDCA and MTT schemes, the data reconstruction error, energy consumption and delay of DGSP are lower.

wireless sensor networks; data gathering; compressive sensing; sparse projection; semi-matching; energy consumption

10.11817/j.issn.1672-7207.2016.10.022

TP393

A

1672?7207(2016)10?3445?09

2015?11?20；

2016?01?22

國家自然科學(xué)基金資助項目(61472449，61173169，61402542)(Projects(61472449, 61173169, 61402542) supported by the National Natural Science Foundation of China)

李鵬，博士研究生，從事無線傳感器網(wǎng)絡(luò)及壓縮感知技術(shù)研究；E-mail：lpchs617@csu.edu.cn