基于網(wǎng)絡(luò)編碼的WSNs數(shù)據(jù)收集方法

汪淑麗

(吉林大學(xué)公共計(jì)算機(jī)教學(xué)與研究中心，吉林長(zhǎng)春130012)

0 引言

無(wú)線傳感器網(wǎng)絡(luò)(WSNs)中的節(jié)點(diǎn)不僅能量有限，而且緩存較小，因此，一個(gè)節(jié)點(diǎn)只能存儲(chǔ)一小部分從周圍收集到的信息，為了完成數(shù)據(jù)的收集、存儲(chǔ)和復(fù)制，大量的節(jié)點(diǎn)必須協(xié)同工作。現(xiàn)有的部分方式是服務(wù)器端首先給Sink節(jié)點(diǎn)發(fā)送查詢消息，然后Sink節(jié)點(diǎn)把查詢消息廣播給所有傳感器節(jié)點(diǎn)。最后所有的傳感器節(jié)點(diǎn)響應(yīng)此次查詢，把監(jiān)測(cè)數(shù)據(jù)通過(guò)路由發(fā)送給服務(wù)器端。但是，這種查詢方式存在著較多的弊端:1)延時(shí)比較大;2)如果服務(wù)器端需要原始數(shù)據(jù)，這樣導(dǎo)致就不能進(jìn)行數(shù)據(jù)融合，進(jìn)一步導(dǎo)致主干路由的負(fù)擔(dān)臨時(shí)變得非常大，容易發(fā)生通信中斷的情況;3)在轉(zhuǎn)發(fā)存儲(chǔ)過(guò)程中，存在著大量的數(shù)據(jù)拷貝，浪費(fèi)了存儲(chǔ)空間，也消耗了節(jié)點(diǎn)的能量。文獻(xiàn)［1］指出由于無(wú)線傳播的廣播特性，網(wǎng)絡(luò)編碼非常適合應(yīng)用于WSNs。如WSNs中，節(jié)點(diǎn)以自組織方式增加或移除部分節(jié)點(diǎn)會(huì)導(dǎo)致網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化，預(yù)測(cè)數(shù)據(jù)分組的丟失和節(jié)點(diǎn)以及鏈路的故障將變得困難，而網(wǎng)絡(luò)編碼卻能夠使目的節(jié)點(diǎn)有效地利用編碼數(shù)據(jù)流恢復(fù)原始信息，甚至可以恢復(fù)一些網(wǎng)絡(luò)中因干擾、擁塞或移動(dòng)而丟失的數(shù)據(jù)分組。

在數(shù)據(jù)采集方面，文獻(xiàn)［2］提出了部分網(wǎng)絡(luò)編碼(PNC)作為連續(xù)數(shù)據(jù)采集的一般工具。PNC推廣了現(xiàn)有的網(wǎng)絡(luò)編碼，能夠?qū)鞲衅鞴?jié)點(diǎn)連續(xù)接收到的數(shù)據(jù)進(jìn)行有效的存儲(chǔ)替換，但沒(méi)有給出完整數(shù)據(jù)收集算法。文獻(xiàn)［3］提出了一種數(shù)據(jù)聚合算法，每個(gè)單獨(dú)的節(jié)點(diǎn)只保存一個(gè)數(shù)據(jù)包，當(dāng)監(jiān)聽(tīng)到鄰居節(jié)點(diǎn)的數(shù)據(jù)包時(shí)，就在有限域上乘一個(gè)隨機(jī)系數(shù)并和自身數(shù)據(jù)相加。這樣，單個(gè)普通傳感器節(jié)點(diǎn)可能不能解碼數(shù)據(jù)，但是對(duì)信宿節(jié)點(diǎn)來(lái)說(shuō)，就能以很高的概率通過(guò)查詢僅僅n個(gè)節(jié)點(diǎn)而重建n個(gè)數(shù)據(jù)包，使得傳感器網(wǎng)絡(luò)數(shù)據(jù)聚合的效率得到極大的提高。

在提高魯棒性方面，文獻(xiàn)［4］提出了一種結(jié)合分布式源編碼私網(wǎng)絡(luò)編碼的優(yōu)化算法，目的是用來(lái)提高傳感器網(wǎng)絡(luò)的容錯(cuò)性和可靠性，同時(shí)對(duì)分布式源編碼的壓縮效率和網(wǎng)絡(luò)魯棒性進(jìn)行了折衷考慮。文獻(xiàn)［5］提出了一種通過(guò)在IP和MAC層之間植入一個(gè)網(wǎng)絡(luò)編碼層，將編碼層集成到現(xiàn)有協(xié)議棧中，針對(duì)實(shí)際使用環(huán)境，提出了一種自適應(yīng)糾錯(cuò)機(jī)制，使編碼的糾錯(cuò)能力與分組的丟失率相匹配，減少數(shù)據(jù)重傳次數(shù)。文獻(xiàn)［6］給出了連續(xù)的數(shù)據(jù)收集算法，但是，其要求在數(shù)據(jù)源節(jié)點(diǎn)周圍擁有較多專門用于存儲(chǔ)轉(zhuǎn)發(fā)的中繼節(jié)點(diǎn)，并不符合WSNs的特征。

本文參考上述文獻(xiàn)，提出了一種改進(jìn)的適應(yīng)于WSNs特性的部分網(wǎng)絡(luò)編碼的數(shù)據(jù)收集算法，該算法著重于網(wǎng)絡(luò)數(shù)據(jù)的收集、數(shù)據(jù)的編碼和解碼，實(shí)驗(yàn)結(jié)果表明其有不錯(cuò)的效果。

1 網(wǎng)絡(luò)編碼的基本概念

1.1 網(wǎng)絡(luò)編碼原理

目前，傳統(tǒng)路由器的存儲(chǔ)轉(zhuǎn)發(fā)模式根本不可能達(dá)到香農(nóng)最大流最小割定理規(guī)定的上界。這是因?yàn)楝F(xiàn)有通信網(wǎng)絡(luò)中使用的路由機(jī)制認(rèn)為網(wǎng)絡(luò)中傳輸?shù)男畔⑹遣荒墀B加的，只能進(jìn)行存儲(chǔ)和轉(zhuǎn)發(fā)［7］。然而 Ahlswede R等人［8］提出的網(wǎng)絡(luò)編碼技術(shù)徹底推翻了這一結(jié)論，Ahlswede R指出:如果允許網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)傳輸?shù)男畔凑蘸线m的方式進(jìn)行編碼處理，而非有限域存儲(chǔ)和轉(zhuǎn)發(fā)，則給予該方式的網(wǎng)絡(luò)多播總能夠?qū)崿F(xiàn)理論上的最大傳輸容量。網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)傳輸信息進(jìn)行操作和處理的過(guò)程，就稱為網(wǎng)絡(luò)編碼。

Ahlswede R等人以著名的“蝴蝶網(wǎng)絡(luò)”模型為例，詳細(xì)闡述了網(wǎng)絡(luò)編碼的基本原理。如圖1所示的網(wǎng)絡(luò)中，設(shè)各鏈路容量為1，S是信源節(jié)點(diǎn)，Y和Z是信宿節(jié)點(diǎn)，其余為中間節(jié)點(diǎn)。S有2個(gè)包 b1和 b2均要發(fā)送給 t1和 t2。在圖1(a)所示的傳統(tǒng)模式中，中間節(jié)點(diǎn)只能對(duì)接收到的數(shù)據(jù)包賦值和轉(zhuǎn)發(fā)，即3到4的鏈路每次只能傳輸b1或者b2，該鏈路必須使用2次才能達(dá)到目的，平均速率為1.5個(gè)包/s。而在圖1(b)中采用了網(wǎng)絡(luò)編碼，節(jié)點(diǎn)3對(duì)數(shù)據(jù)包進(jìn)行了異或處理，這樣一次傳輸就可以將b1⊕b2傳送到節(jié)點(diǎn)4，因?yàn)閠1和t2已經(jīng)接收到b1和b2，所以，再次進(jìn)行異或操作便可以得到b1和b2，該模式下的所能達(dá)到的平均速率為2個(gè)包/s。由此可見(jiàn)，基于網(wǎng)絡(luò)編碼的多播實(shí)現(xiàn)了理論上的最大傳輸容量。

圖1 蝴蝶網(wǎng)絡(luò)Fig 1 Butterfly networks

1.2 網(wǎng)絡(luò)編碼的核心思想

網(wǎng)絡(luò)編碼的核心思想為［7］:具備編碼條件的網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)接收到的信息進(jìn)行一定方式的處理(編碼)，然后傳輸給下一級(jí)的網(wǎng)絡(luò)節(jié)點(diǎn)，收到消息的下一級(jí)節(jié)點(diǎn)如果具備編碼條件，又對(duì)其接收的信息按照同樣的方式進(jìn)行處理和傳輸，如此反復(fù)，直到所有經(jīng)過(guò)處理后的信息都匯聚到信宿節(jié)點(diǎn)為止。最后，在信宿節(jié)點(diǎn)通過(guò)逆過(guò)程的操作(譯碼)，即可譯出信源發(fā)送的原始信息。

2 基于網(wǎng)絡(luò)編碼的數(shù)據(jù)收集方法描述

WSNs有其自身的資源缺陷，而在能量方面尤其明顯。參考已有的文獻(xiàn)可知，節(jié)點(diǎn)間的數(shù)據(jù)通信是耗能最大的環(huán)節(jié)，故網(wǎng)絡(luò)中的數(shù)據(jù)收集采用網(wǎng)絡(luò)編碼，以降低網(wǎng)絡(luò)中的數(shù)據(jù)流量，提高網(wǎng)絡(luò)的整體性能是可行的。

2.1 網(wǎng)絡(luò)的基本結(jié)構(gòu)描述

本文采用基于簇的網(wǎng)絡(luò)結(jié)構(gòu)，結(jié)構(gòu)中有3種不同類型的節(jié)點(diǎn)，分別為簇成員節(jié)點(diǎn)、簇頭節(jié)點(diǎn)和Sink節(jié)點(diǎn)，這3種類型的節(jié)點(diǎn)在緩存空間大小、攜帶能量多少和處理器的運(yùn)算處理能力方面均存在一定的不同。其中，Sink節(jié)點(diǎn)擁有大的緩存空間、多的能量和強(qiáng)的運(yùn)算處理能力，簇頭節(jié)點(diǎn)在這三方面的硬件條件次之，而簇成員節(jié)點(diǎn)在這三方面的硬件條件最差。這樣的網(wǎng)絡(luò)結(jié)構(gòu)能夠有效地克服網(wǎng)絡(luò)中所有節(jié)點(diǎn)具有相同但是小的緩存空間而引起的性能下降，保證簇頭節(jié)點(diǎn)對(duì)來(lái)自其簇成員節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行緩存和編碼，Sink節(jié)點(diǎn)對(duì)整個(gè)網(wǎng)絡(luò)的數(shù)據(jù)進(jìn)行存儲(chǔ)和解碼操作。網(wǎng)絡(luò)結(jié)構(gòu)圖如圖2所示。

圖2 網(wǎng)絡(luò)結(jié)構(gòu)圖Fig 2 Diagram of network structure

2.2 基于部分網(wǎng)絡(luò)編碼的舉例說(shuō)明

在傳統(tǒng)的網(wǎng)絡(luò)編碼中，可能存在延時(shí)、節(jié)點(diǎn)解碼準(zhǔn)確性不高和刪除過(guò)時(shí)數(shù)據(jù)存在缺陷的情況，這里考慮的情況是如何以最小的代價(jià)刪除過(guò)時(shí)的數(shù)據(jù)信息，部分網(wǎng)絡(luò)編碼將能夠比較有效地解決這個(gè)問(wèn)題，為了更好地說(shuō)明該問(wèn)題，參考文獻(xiàn)［2］，舉例說(shuō)明部分網(wǎng)絡(luò)編碼在數(shù)據(jù)刪除過(guò)時(shí)數(shù)據(jù)信息的優(yōu)點(diǎn)。

設(shè)有6個(gè)傳感器節(jié)點(diǎn)，傳感器節(jié)點(diǎn)分別標(biāo)記為s0，s1，s2，s3，s4，s5，每個(gè)節(jié)點(diǎn)的緩存空間大小為 2，每個(gè)緩存空間中原始數(shù)據(jù)的最大數(shù)量值為4，且這6個(gè)傳感器節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)分別為

當(dāng)產(chǎn)生新的數(shù)據(jù)c4時(shí)，c0變?yōu)檫^(guò)時(shí)數(shù)據(jù)，節(jié)點(diǎn)s0和s4分別丟棄過(guò)時(shí)數(shù)據(jù)，同時(shí)添加新的數(shù)據(jù)c4，則節(jié)點(diǎn)s0和s4緩存中的數(shù)據(jù)更新為

該舉例說(shuō)明部分網(wǎng)絡(luò)編碼具有無(wú)需解碼的情況下，就可以移除過(guò)時(shí)的數(shù)據(jù)的特性。不過(guò)，值得注意的是:部分網(wǎng)絡(luò)編碼的譯碼能力取決于組合數(shù)據(jù)的勢(shì)集(定義為其所包含的原始數(shù)據(jù)塊的個(gè)數(shù))，在統(tǒng)一的勢(shì)集分布情況下，譯碼性能最理想。然而，從傳感器的角度考慮，由于緩存空間有限，同時(shí)，傳感器節(jié)點(diǎn)也無(wú)法知道其他節(jié)點(diǎn)所存儲(chǔ)的數(shù)據(jù)。基于上述情況的考慮，由于本文所構(gòu)造的網(wǎng)絡(luò)構(gòu)造為基于簇的結(jié)構(gòu)，簇頭節(jié)點(diǎn)和Sink節(jié)點(diǎn)的緩存大和處理能力較強(qiáng)的特性，使得這兩種類型的節(jié)點(diǎn)能夠有效地獲取相對(duì)全局的信息。

2.3 網(wǎng)絡(luò)編碼過(guò)程

數(shù)據(jù)的收集基于簇結(jié)構(gòu)，簇成員節(jié)點(diǎn)和簇頭節(jié)點(diǎn)的通信距離均為一跳，這樣會(huì)降低因?yàn)橥ㄐ哦鴮?dǎo)致的能量消耗，而簇頭節(jié)點(diǎn)與簇頭節(jié)點(diǎn)的通信距離可以不受限制，這樣簇頭節(jié)點(diǎn)之間形成了數(shù)據(jù)收集和傳輸?shù)闹鞲陕酚?。簇成員節(jié)點(diǎn)采集其監(jiān)測(cè)區(qū)域的數(shù)據(jù)，簇頭節(jié)點(diǎn)根據(jù)其實(shí)際緩存的大小，對(duì)數(shù)據(jù)進(jìn)行緩存和更新，同時(shí)把緩存數(shù)據(jù)發(fā)送給簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)對(duì)接收到的數(shù)據(jù)采用隨機(jī)編碼，利用主干路由把數(shù)據(jù)發(fā)送到Sink節(jié)點(diǎn)，Sink節(jié)點(diǎn)在得到一定程度編碼數(shù)據(jù)的基礎(chǔ)上，解碼得到各個(gè)簇的編碼數(shù)據(jù)，進(jìn)而得到整個(gè)網(wǎng)絡(luò)的數(shù)據(jù)。

3 模擬實(shí)驗(yàn)結(jié)果與分析

均勻部署200個(gè)節(jié)點(diǎn)到100 m×100 m的區(qū)域，經(jīng)過(guò)成簇算法形成8～10個(gè)簇，成為簇頭節(jié)點(diǎn)的通信區(qū)域認(rèn)為可以覆蓋整個(gè)部署區(qū)域。在此要說(shuō)明的是，網(wǎng)絡(luò)中所需要匯報(bào)的數(shù)據(jù)只有一種類型的數(shù)據(jù)，而不考慮匯報(bào)多種類型的數(shù)據(jù)。

本文采用文獻(xiàn)［9］提出的能量模型，通信模型采用多路徑效應(yīng)模型，即完成一次發(fā)送、接收通信的總能量消耗為E(l，d)=l(2Eelec+ εmpd4)，通信能量參數(shù)設(shè)為:Eelec=50 nJ/bit，εmp=0.0013 pJ/bit/m4，d=20 m。

不同的網(wǎng)絡(luò)編碼方案將影響整個(gè)網(wǎng)絡(luò)的魯棒性，也對(duì)節(jié)點(diǎn)的丟包率產(chǎn)生影響，本文主要考慮能量開(kāi)銷和數(shù)據(jù)準(zhǔn)確率這2個(gè)性能評(píng)價(jià)參數(shù)。

圖3是整個(gè)網(wǎng)絡(luò)的能量消耗圖，從圖中可以看出:采用網(wǎng)絡(luò)編碼時(shí)，全網(wǎng)的能量消耗明顯低于非網(wǎng)絡(luò)編碼的數(shù)據(jù)。

圖3 網(wǎng)絡(luò)的能耗Fig 3 Energy consumption of network

圖4是采用網(wǎng)絡(luò)編碼時(shí)的數(shù)據(jù)恢復(fù)準(zhǔn)確率，從圖中可以看出:雖然數(shù)據(jù)恢復(fù)的準(zhǔn)確率有所反復(fù)，但是，基本保持在較高的準(zhǔn)確率，在參考能量消耗的基礎(chǔ)上，這個(gè)性能是比較理想的。

圖4 網(wǎng)絡(luò)的丟包Fig 4 Packet loss of network

4 結(jié)論

網(wǎng)絡(luò)編碼是一個(gè)學(xué)科交叉的產(chǎn)物，經(jīng)過(guò)多年的研究，網(wǎng)絡(luò)編碼正給網(wǎng)絡(luò)帶來(lái)革命性的變化，但在多源網(wǎng)絡(luò)編碼、非線性編碼、網(wǎng)絡(luò)編碼的具體實(shí)現(xiàn)、降低網(wǎng)絡(luò)編碼的復(fù)雜性，以及網(wǎng)絡(luò)編碼在安全方面的研究仍然方興未艾，將成為網(wǎng)絡(luò)編碼下一步的研究方向和熱點(diǎn)。本文主要討論了部分網(wǎng)絡(luò)編碼用于WSNs的監(jiān)測(cè)數(shù)據(jù)收集的算法，在基本保證數(shù)據(jù)精確度的前提下，能有效降低網(wǎng)絡(luò)內(nèi)的能量消耗。

［1］張書奎，樊建席，崔志明.無(wú)線傳感器網(wǎng)絡(luò)中可靠的數(shù)據(jù)協(xié)作傳輸機(jī)制［J］.通信學(xué)報(bào)，2010(11):30-40.

［2］Wang Dan，Zhang Qian，Liu Jiangchuan.Partial network coding:Theory and application for continuous sensor data collection［C］∥Proceedings of 14th IEEE International Workshop on Quality of Service，2006:93-101.

［3］Dimakis A G，Probhakaran V，Ramchandran K.Ubiquitous access to distributed data in large-scale sensor networks through decentralized erasure codes［C］∥ Proceedings of 4th International Symposium on Information Processing in Sensor Networks，2005:111-117.

［4］Zhang Xin，Wicker S B.Robustness vs efficiency in sensor networks［C］∥Proceedings of 4th International Symposium on Information Processing in Sensor Networks，2005:225-230.

［5］唐文勝，王 威，羅 娟.WSNs中一種基于網(wǎng)絡(luò)編碼的可靠傳輸算法［J］.湖南師范大學(xué)學(xué)報(bào):自然科學(xué)版，2008(1):59-64.

［6］王俊義.編碼分組網(wǎng)絡(luò)的效用最大化及網(wǎng)絡(luò)編碼在應(yīng)用方面的研究［D］.北京:北京郵電大學(xué)，2008.

［7］陶少國(guó)，黃佳慶，楊宗凱.網(wǎng)絡(luò)編碼研究綜述［J］.小型微型計(jì)算機(jī)系統(tǒng)，2008(4):583-592.

［8］Ahlswede R，Cai Ning，Li Shuoyen R.Network information flow［J］.IEEE Transactions on Information Theory，2000，46(4):1204-1216.

［9］Heinzelman W B，Chandrakasan A P，Balakrishnan H.An application-sepcific protocol archietecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications ＆Mobile Computing，2002，1(4):660-670.