基于合作域的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)存儲機(jī)制研究*

李 薇，侯 睿，楊文俊

(中南民族大學(xué) 計算機(jī)科學(xué)學(xué)院，湖北 武漢430074)

0 引 言

無線傳感器網(wǎng)絡(luò)(WSNs)中，節(jié)點需要存儲本地觀測數(shù)據(jù)，并能夠向最終的用戶方提供實際的觀測信息，其在建筑健康狀態(tài)監(jiān)控［1］、環(huán)境監(jiān)控［2］等多個領(lǐng)域中均已得到廣泛應(yīng)用。然而，受傳感器節(jié)點能量、處理器性能和節(jié)點存儲空間等多方面因素的制約，傳感器已采集數(shù)據(jù)的存儲與處理往往都需要由網(wǎng)絡(luò)外部的高性能計算機(jī)來完成。因此，一些主要的應(yīng)用均假定傳感器網(wǎng)絡(luò)能夠?qū)崟r數(shù)據(jù)連續(xù)地發(fā)送至匯聚節(jié)點［3］。但當(dāng)網(wǎng)絡(luò)中出現(xiàn)失效節(jié)點或通信受到影響時，終端處理機(jī)將有可能無法連續(xù)地收到節(jié)點采集的數(shù)據(jù)，此時就需要在網(wǎng)絡(luò)內(nèi)采用一定的數(shù)據(jù)存儲機(jī)制，并在節(jié)點失效的情況下能夠盡量地恢復(fù)重要數(shù)據(jù)。在早期的一些研究工作中，通常采用信源編碼以提高向匯聚節(jié)點的數(shù)據(jù)傳輸效率，它們往往利用數(shù)據(jù)中的時空關(guān)系壓縮數(shù)據(jù)［4］，主要編碼方式可以分為分布式的變換編碼［5］、分布式的信源編碼［6］和向量編碼［7］等。而在恢復(fù)因節(jié)點失效而丟失的隨機(jī)數(shù)據(jù)時，傳統(tǒng)的方式往往只能恢復(fù)全部數(shù)據(jù)而無法進(jìn)行部分恢復(fù)，而且都是基于全網(wǎng)中心化的編碼方式，計算量過大［8］，因此，無法適用于傳感器網(wǎng)絡(luò)的應(yīng)用。

本文針對以上這些問題，提出了一種新型的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)存儲機(jī)制。根據(jù)節(jié)點間的相對位置和探測的事件類型進(jìn)行分組，使得每個分組能夠承擔(dān)一定范圍內(nèi)的一個或多個事件探測任務(wù)。在單個節(jié)點無法存儲組內(nèi)所有事件信息的情況下，引入合作域的概念，通過基于網(wǎng)絡(luò)編碼［9］的協(xié)作存儲機(jī)制和存儲算法，極大地提高了數(shù)據(jù)存儲的有效性，加強(qiáng)了整個網(wǎng)絡(luò)的數(shù)據(jù)容錯能力。仿真結(jié)果表明:該機(jī)制能夠節(jié)約節(jié)點能量，提高節(jié)點數(shù)據(jù)的有效性，加強(qiáng)整個傳感器網(wǎng)絡(luò)的持續(xù)性。

1 合作域數(shù)據(jù)存儲機(jī)制架構(gòu)

1.1 應(yīng)用假設(shè)與設(shè)計目標(biāo)

假設(shè)在一個擁有N 個傳感器節(jié)點的網(wǎng)絡(luò)中，節(jié)點采集到的數(shù)據(jù)信息需要發(fā)送至匯聚節(jié)點以便進(jìn)行下一步的處理。由于節(jié)點的無線傳輸速率有限，將所有實時數(shù)據(jù)均傳輸給匯聚節(jié)點所需的帶寬可能大大超出整個網(wǎng)絡(luò)的通信能力，因此，需要在節(jié)點中進(jìn)行適當(dāng)?shù)臄?shù)據(jù)緩存。此網(wǎng)絡(luò)中的每個節(jié)點均為同質(zhì)節(jié)點，有一定的運(yùn)算能力以便對數(shù)據(jù)進(jìn)行有限的編解碼工作，以提高傳輸和存儲的有效性。

在將傳感器網(wǎng)絡(luò)部署在某些危險區(qū)域時，如地震帶、火災(zāi)現(xiàn)場等，需要傳感器網(wǎng)絡(luò)能夠迅速地將實時數(shù)據(jù)反饋給上層用戶，并且能夠?qū)W(wǎng)絡(luò)有一定的控制能力?；谝陨系募僭O(shè)和應(yīng)用場景，可將設(shè)計目標(biāo)總結(jié)如下:

1)能夠在最短時間盡可能多地向匯聚節(jié)點傳遞數(shù)據(jù);

2)使網(wǎng)絡(luò)具有一定的可配置性，以便針對不同的監(jiān)控情況對網(wǎng)絡(luò)加以控制;

3)網(wǎng)絡(luò)因具有一定的自適應(yīng)性，以應(yīng)變惡劣環(huán)境帶來的影響;

1.2 體系架構(gòu)

此機(jī)制的核心目標(biāo)是對各種事件進(jìn)行監(jiān)測并管理節(jié)點采集到的數(shù)據(jù)信息，此外，還需要進(jìn)行相關(guān)的分組控制、QoS調(diào)度和路由控制等工作。為了在有限的資源下達(dá)到此目標(biāo)，引入合作域(cooperation region)的概念，即將網(wǎng)絡(luò)中監(jiān)控事件類型一致并可以通過單跳或兩跳實現(xiàn)傳輸?shù)呐R近節(jié)點分為一組，并通過組內(nèi)協(xié)商確定合作域的管理(cooperation manager，CM)節(jié)點。合作域內(nèi)的成員節(jié)點實現(xiàn)數(shù)據(jù)冗余緩存，并由CM 統(tǒng)一進(jìn)行管理。

2 信息合作域的建立

為了說明合作域，首先給出其相關(guān)定義:令Z={z1，z2，…，zn}是由無線傳感器網(wǎng)絡(luò)中N 個節(jié)點所組成的集合，若)均可以直接進(jìn)行通信或通過另一個節(jié)點)進(jìn)行信息中轉(zhuǎn)，那么就稱zi，zj是鄰節(jié)點，且Z 可以形成一個合作域。

在網(wǎng)絡(luò)初始狀態(tài)下，節(jié)點會定時廣播本地的基本信息，如剩余能量、存儲能力等。每個節(jié)點接收到其他節(jié)點的信息后即可構(gòu)建其本地的鄰節(jié)點列表。在一個高密度的網(wǎng)絡(luò)中，某些節(jié)點可能包含在多個節(jié)點的鄰節(jié)點列表中，如直接根據(jù)鄰節(jié)點列表建立合作域，那么就會使得不同合作域出現(xiàn)重疊，此時就需要通過選取管理節(jié)點建立彼此獨立的合作域，這一過程與APTEEN［10］等協(xié)議中簇頭節(jié)點的選取比較類似。但由于CM 要擔(dān)負(fù)起一定的管理功能，因此，引入了一個CM 判定的權(quán)重機(jī)制，即

由式(1)即可獲得節(jié)點i 的權(quán)重值wi，通過比較各節(jié)點的權(quán)重，選取剩余能量和存儲空間較多，而距離其他節(jié)點較近，即wi較大的節(jié)點作為CM 節(jié)點。

3 合作域內(nèi)的數(shù)據(jù)存儲與提取

傳統(tǒng)的數(shù)據(jù)存儲方式往往未對數(shù)據(jù)進(jìn)行編碼，或由于編解碼計算量過大且數(shù)據(jù)恢復(fù)困難而無法應(yīng)用于傳感器網(wǎng)絡(luò)之中。如果不對數(shù)據(jù)進(jìn)行編碼直接存儲，那么就需要在不同節(jié)點上保存冗余數(shù)據(jù)。當(dāng)節(jié)點內(nèi)存耗盡或一定周期之后，再隨機(jī)丟棄數(shù)據(jù)包。這樣一來，為達(dá)到較好的恢復(fù)效果，將消耗較多的內(nèi)存和大量的查詢開銷。本文采用網(wǎng)絡(luò)編碼技術(shù)來解決這一問題，這種編碼方式可以將不同的數(shù)據(jù)糅合在一起，以減少對單個節(jié)點數(shù)據(jù)的依賴，從而增加數(shù)據(jù)的傳輸、存儲的可靠性，非常適合于傳感器網(wǎng)絡(luò)報文易丟失、節(jié)點容易失效的應(yīng)用特點［11］。

增值稅新政對企業(yè)帶來減稅效應(yīng)的研究 …………………………………………………………………… 謝 想 吳力佳（6/38）

實用網(wǎng)絡(luò)編碼將分組數(shù)據(jù)編碼成一組線性無關(guān)的數(shù)據(jù)，接收端只要能夠收到其中的一部分即可從中解碼出原始數(shù)據(jù)。在某段時間T 內(nèi)，當(dāng)某個合作域內(nèi)的管理節(jié)點CM接收到其他合作域的待緩存數(shù)據(jù)后，將該組數(shù)據(jù)定義為一代，因此，同一代的數(shù)據(jù)包含一定的時空相關(guān)性。假設(shè)n 為這一組數(shù)據(jù)中的數(shù)據(jù)包數(shù)量，N 為合作域內(nèi)當(dāng)前的節(jié)點數(shù)量，那么原始數(shù)據(jù)包隊列向量可以表示為，其中的每個數(shù)據(jù)包向量的長度由數(shù)據(jù)包大小和有限域的尺寸，那么包中的每個字節(jié)就可以表示為向量中的一個元素，即pi，j。為簡化說明，此時假設(shè)所有數(shù)據(jù)包的大小一致，均為k 字節(jié)，則每個數(shù)據(jù)包可表示為

3.1 數(shù)據(jù)的編碼與分發(fā)

其中

在傳感器網(wǎng)絡(luò)中，為節(jié)省節(jié)點能量，節(jié)點在正常工作一段時間后就會進(jìn)入休眠直到下次激活。盡管各節(jié)點的工作時長相同，但由于各節(jié)點的具體激活時間一般處于隨機(jī)狀態(tài)，可能造成管理節(jié)點需要較長時間才能與某些節(jié)點建立通信，進(jìn)而導(dǎo)致管理節(jié)點難于將編碼后的數(shù)據(jù)即時、均勻地分發(fā)給合作域中的成員節(jié)點。雖然可以讓管理節(jié)點一直處于工作狀態(tài)，等待其他節(jié)點的激活以發(fā)送數(shù)據(jù)，但這種方式也將增大管理節(jié)點的能量消耗。因此，引入了激活時間控制機(jī)制。當(dāng)合作域建立后，通過管理節(jié)點協(xié)調(diào)域內(nèi)節(jié)點的激活時間點，使得管理節(jié)點在一定的周期內(nèi)能夠與所有的成員節(jié)點均建立通信，以便及時地發(fā)送緩存數(shù)據(jù)。

管理節(jié)點編碼過程:

1)生成M×n 維的隨機(jī)系數(shù)矩陣Φ={φij}，其中1≤i≤M，1≤j≤n;

2)IF 已完整收到一代數(shù)據(jù)中的所有數(shù)據(jù)包THEN

3)END IF;

4)IF 與節(jié)點ni(1≤i≤N)建立通信AND 未發(fā)送過緩存數(shù)據(jù)包THEN;

5)從P'中隨機(jī)選擇M/N 個包進(jìn)行發(fā)送，并將它們從P'中刪除;

6)END IF。

3.2 數(shù)據(jù)的提取與解碼

當(dāng)匯聚節(jié)點節(jié)點或其他的移動數(shù)據(jù)收集器訪問合作域并進(jìn)行數(shù)據(jù)查詢時，合作域中的節(jié)點即可將編碼后的數(shù)據(jù)提交給接收對象。根據(jù)上文的編碼方式，此時需要獲取至少n 個已編碼的數(shù)據(jù)包才能對其進(jìn)行解碼以獲得原始數(shù)據(jù)，即需要查詢［nN/M］個節(jié)點。接收到這些數(shù)據(jù)包后，從中提取出n×n 階的系數(shù)矩陣Ψ 和n×k 階的數(shù)據(jù)矩陣D，如果Ψ 滿秩，則可通過式(3)獲得原始數(shù)據(jù)

若Ψ 不滿秩，則需要繼續(xù)從合作域中的其他節(jié)點處獲得其他編碼數(shù)據(jù)包后再進(jìn)行解碼。

4 仿真與分析

能夠?qū)W(wǎng)絡(luò)性能帶來根本影響的主要指標(biāo)參數(shù)包括:1)每代數(shù)據(jù)組中的數(shù)據(jù)包數(shù)量n;2)合作域尺寸，即域內(nèi)節(jié)點的數(shù)目N;3)編碼度M。

網(wǎng)絡(luò)性能主要可以通過以下指標(biāo)進(jìn)行判定:1)控制消息開銷;2)傳感器網(wǎng)絡(luò)內(nèi)的信息可靠性，即出現(xiàn)節(jié)點失效后現(xiàn)有數(shù)據(jù)占原有數(shù)據(jù)的百分比;3)數(shù)據(jù)包解碼率。本文使用OMNeT++仿真平臺［12］實現(xiàn)了此機(jī)制的部分組件，以便于比較在不同參數(shù)下的具體網(wǎng)絡(luò)性能。仿真中的相關(guān)參數(shù)詳為:場景大小為100 m×100 m，仿真時間為2 h，節(jié)點數(shù)量為121 個，節(jié)點間距為10 m，節(jié)點通信半徑為20 m。

4.1 控制信息的開銷

在實驗中，首先研究了不同合作域尺寸N 對控制信息開銷帶來的影響。如圖1 所示，隨著域尺寸的增長，整個控制信息所消耗的通信量在總通信量中所占的比例也隨之增長。主要原因在于，當(dāng)合作域內(nèi)節(jié)點數(shù)目增加時，為維持合作域的正常運(yùn)行的調(diào)度開銷也會增加，選舉新的管理節(jié)點也更為復(fù)雜。

圖1 不同域尺寸下的控制信息開銷Fig 1 Control Information overhead of different region size

4.2 信息的有效性

核心設(shè)計目標(biāo)就是在有限的條件下盡量提高信息的可靠性。圖2 說明了在不同的域尺寸和節(jié)點失效比率的情況下數(shù)據(jù)有效率的變化。從圖2 中可知，當(dāng)合作域內(nèi)節(jié)點數(shù)目較多時，由于提取數(shù)據(jù)時很容易獲得一個滿秩的Ψ 矩陣，從而解碼出原始數(shù)據(jù)，使得節(jié)點失效對信息可靠性的影響不大。因此，在個別節(jié)點容易失效的環(huán)境下，增大域尺寸有利于提高信息的可靠性。從圖中可知，在節(jié)點失效率分別為10%和30%的情況下，如果要取得97%的信息可靠率，那么域內(nèi)節(jié)點數(shù)目分別需要達(dá)到10 個和15 個。

圖2 不同平均域尺寸下的信息有效率Fig 2 Information availability rate of different average region size

雖然增加域尺寸對信息可靠性的提高大有裨益，但從圖1 可知，這同樣也增加了域內(nèi)的控制信息開銷，使得節(jié)點能量消耗增加。因此，需要綜合考慮這些因素，設(shè)定一個合適的域尺寸，以便在盡量節(jié)約節(jié)點能量的前提下增加信息的有效性。

5 結(jié) 論

通過分析無線傳感器網(wǎng)絡(luò)的特性及其應(yīng)用特點，針對節(jié)點存儲能力有限，無法將網(wǎng)內(nèi)大量數(shù)據(jù)信息存儲在若干個存儲節(jié)點上的情況，提出了一種新型的基于合作域的傳感器網(wǎng)絡(luò)數(shù)據(jù)儲機(jī)制，以便在節(jié)約節(jié)點能量和內(nèi)存開銷的前提下提高數(shù)據(jù)的可靠性。給出了其設(shè)計目標(biāo)和體系結(jié)構(gòu)，提出了數(shù)據(jù)存儲合作域、管理節(jié)點等基本概念，以及合作域的建立機(jī)制和管理節(jié)點的選取算法。通過仿真測試，證明其能夠在較低的資源開銷下提高信息的可靠性。

［1］ Akio H，Kenichi S，Ruoshui L，et al.Lagrangian heuristic method for the wireless sensor networks design problem in railway structural health monitoring［J］.Mechanical Systems and Signal Processing，2012，28:20－35.

［2］ Mohd F，Khairunnisa S.Wireless sensor networks applications:A study in environment monitoring system［J］.Procedia Engineering，2012，41:1204－1210.

［3］ Ousmane D，Joel J，Mbaye S.Real－timedata management on wireless sensor networks:A survey［J］.Journal of Network and Computer Applications，2012，35(3):1013－1021.

［4］ Tossaporn S，Kamol K，Poonlap L，et al.Practical data compression in wireless sensor networks:A survey［J］.Journal of Network and Computer Applications，2012，35(1):37－59.

［5］ Oka A，Lampe L.Energy efficient distributed filtering with wireless sensor networks［J］.IEEE Transaction on Signal Process，2008，56(5):2062－2075.

［6］ Chew L W，Ang L M，Seng K P.Survey of image compression algorithms in wireless sensor networks［C］∥International Symposium on Information Technology，Kuala Lumpur:IEEE，2008:1－9.

［7］ Donoho D L.Compressed sensing［J］.IEEE Transaction on Information Theory，2006，52(4):1289－1306.

［8］ Marcelloni F，Vecchio M.An efficient lossless compression algorithm for tiny nodes of monitoring wireless sensor networks［J］.The Computer Journal，2009，52(8):969－987.

［9］ Fragouli C，Boudec J L，Widmer J.Network coding:An instant primer［J］.Computer Communication Review，2006，36(1):63－68.

［10］Manjeshwar A，Agrawal D P.APTEEN:A hybrid protocol for efficient routing and comprehensive information retrieval in wireless sensor networks［C］∥Proc of the 2nd Int'l Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing，F(xiàn)lorida:IEEE，2002:195－202.

［11］Li Y H，Zhang Q Y，Wu S H.Efficient data gathering with network coding coupled compressed sensing for wireless sensor networks［J］.Information Technology Journal，2013，12(9):1737－1745.

［12］Weingartner E，Vom L H，Wehrle K.A performance comparison of recent network simulators［C］∥IEEE International Conference on Communications，Dresden:IEEE，2009:1－5.