汪淑麗

(吉林大學(xué)公共計算機教學(xué)與研究中心，吉林長春130012)

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

WSNs有其自身的資源缺陷，而在能量方面尤其明顯。參考已有的文獻可知，節(jié)點間的數(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é)點，分別為簇成員節(jié)點、簇頭節(jié)點和Sink節(jié)點，這3種類型的節(jié)點在緩存空間大小、攜帶能量多少和處理器的運算處理能力方面均存在一定的不同。其中，Sink節(jié)點擁有大的緩存空間、多的能量和強的運算處理能力，簇頭節(jié)點在這三方面的硬件條件次之，而簇成員節(jié)點在這三方面的硬件條件最差。這樣的網(wǎng)絡(luò)結(jié)構(gòu)能夠有效地克服網(wǎng)絡(luò)中所有節(jié)點具有相同但是小的緩存空間而引起的性能下降，保證簇頭節(jié)點對來自其簇成員節(jié)點的數(shù)據(jù)進行緩存和編碼，Sink節(jié)點對整個網(wǎng)絡(luò)的數(shù)據(jù)進行存儲和解碼操作。網(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ò)編碼的舉例說明

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

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

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

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

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

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

3 模擬實驗結(jié)果與分析

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

本文采用文獻［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ò)編碼方案將影響整個網(wǎng)絡(luò)的魯棒性，也對節(jié)點的丟包率產(chǎn)生影響，本文主要考慮能量開銷和數(shù)據(jù)準(zhǔn)確率這2個性能評價參數(shù)。

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

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

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

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

4 結(jié)論

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

［1］張書奎，樊建席，崔志明.無線傳感器網(wǎng)絡(luò)中可靠的數(shù)據(jù)協(xié)作傳輸機制［J］.通信學(xué)報，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é)報:自然科學(xué)版，2008(1):59-64.

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

［7］陶少國，黃佳慶，楊宗凱.網(wǎng)絡(luò)編碼研究綜述［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.