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

李鵬，王建新

?

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

李鵬1, 2，王建新1

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

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

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

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

1 問(wèn)題建模

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

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

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

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

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

1.2 相關(guān)定義

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

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

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

則稱(chēng)該隨機(jī)變量服從亞高斯分布。

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

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

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

1.3 問(wèn)題描述

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

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

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

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

2.1 主要思路

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

2.2 RIP性質(zhì)證明

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

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

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

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

則

顯然，當(dāng)取由式(9)定義的0時(shí)，式(14)的右邊達(dá)到最小，即

式(7)成立。證畢。

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

3.1 能耗分析

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

(a) 初始的網(wǎng)絡(luò)拓?fù)洌?b) 拓?fù)?；(c) 拓?fù)?

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

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

3) 若節(jié)點(diǎn)v不是葉子節(jié)點(diǎn)，且，節(jié)點(diǎn)v有個(gè)孩子節(jié)點(diǎn)，則

4) 若節(jié)點(diǎn)v不是葉子節(jié)點(diǎn)，且，節(jié)點(diǎn)v有個(gè)孩子節(jié)點(diǎn)，則

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

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

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

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

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

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

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

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

3.3 半匹配問(wèn)題

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

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

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

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

步驟3：While非空。

Else

End

End

End

End

End

End

4 仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

圖6所示為DGSP與其他3種方案的數(shù)據(jù)收集延時(shí)比較結(jié)果。從圖6可以看到：隨著SNR增大，4種方案的延時(shí)都增大，但總的來(lái)說(shuō)，MTT的延時(shí)最低，DGSP的延時(shí)要略比CDG的低，EDCA的延時(shí)最高。這是由于EDCA采用密集投影進(jìn)行節(jié)點(diǎn)的數(shù)據(jù)采樣，并且為了得到較高的SNR，EDCA需要進(jìn)行多次矩陣運(yùn)算，增加了計(jì)算開(kāi)銷(xiāo)。而CDG和DGSP則都對(duì)數(shù)據(jù)傳輸路徑進(jìn)行了優(yōu)化，降低了各個(gè)節(jié)點(diǎn)的數(shù)據(jù)傳輸跳數(shù)，取得了比EDCA更好的延時(shí)性能。MTT延時(shí)最低的主要原因是它假設(shè)每次數(shù)據(jù)傳輸開(kāi)銷(xiāo)為1，以最小化數(shù)據(jù)傳輸次數(shù)為目標(biāo)，從Sink出發(fā)，MTT迭代地找到1條具有最小的傳輸代價(jià)增加值的邊加入到最終的數(shù)據(jù)收集樹(shù)中。該方法雖然延時(shí)最低，但對(duì)于數(shù)據(jù)傳輸開(kāi)銷(xiāo)的假設(shè)過(guò)于苛刻，而DGSP是更真實(shí)的網(wǎng)絡(luò)模型，取得了與MTT相近的延時(shí)性能，因此，本文認(rèn)為DGSP是高效的，相比于MTT而言，更加適用于真實(shí)的無(wú)線傳感器網(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è)計(jì)了一種基于最小化傳輸開(kāi)銷(xiāo)的投影矩陣用于數(shù)據(jù)采樣。相比于密集投影矩陣而言，該矩陣在滿足RIP原則的前提下，利用了各個(gè)節(jié)點(diǎn)間感知數(shù)據(jù)的相關(guān)性來(lái)對(duì)矩陣進(jìn)行稀疏化，在保證數(shù)據(jù)收集質(zhì)量的同時(shí)，顯著降低了網(wǎng)絡(luò)通信開(kāi)銷(xiāo)。

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

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

參考文獻(xiàn)：

[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ú)線傳感器網(wǎng)絡(luò)研究進(jìn)展[J]. 計(jì)算機(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ú)線傳感器網(wǎng)絡(luò)中一種新型的混合型數(shù)據(jù)收集協(xié)議[J]. 計(jì)算機(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ù)高效路由數(shù)據(jù)收集[J]. 傳感技術(shù)學(xué)報(bào), 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ú)線傳感器網(wǎng)絡(luò)基于多元簇首的分簇?cái)?shù)據(jù)收集算法[J]. 電子與信息學(xué)報(bào), 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ī)投影的圖像重建方法[J]. 計(jì)算機(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

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

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