汪淑麗

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

0 引言

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

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

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

本文參考上述文獻，提出了一種改進的適應于WSNs特性的部分網絡編碼的數據收集算法，該算法著重于網絡數據的收集、數據的編碼和解碼，實驗結果表明其有不錯的效果。

1 網絡編碼的基本概念

1.1 網絡編碼原理

目前，傳統路由器的存儲轉發(fā)模式根本不可能達到香農最大流最小割定理規(guī)定的上界。這是因為現有通信網絡中使用的路由機制認為網絡中傳輸的信息是不能疊加的，只能進行存儲和轉發(fā)［7］。然而 Ahlswede R等人［8］提出的網絡編碼技術徹底推翻了這一結論，Ahlswede R指出:如果允許網絡節(jié)點對傳輸的信息按照合適的方式進行編碼處理，而非有限域存儲和轉發(fā)，則給予該方式的網絡多播總能夠實現理論上的最大傳輸容量。網絡節(jié)點對傳輸信息進行操作和處理的過程，就稱為網絡編碼。

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

圖1 蝴蝶網絡Fig 1 Butterfly networks

1.2 網絡編碼的核心思想

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

2 基于網絡編碼的數據收集方法描述

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

2.1 網絡的基本結構描述

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

圖2 網絡結構圖Fig 2 Diagram of network structure

2.2 基于部分網絡編碼的舉例說明

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

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

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

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

2.3 網絡編碼過程

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

3 模擬實驗結果與分析

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

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

不同的網絡編碼方案將影響整個網絡的魯棒性，也對節(jié)點的丟包率產生影響，本文主要考慮能量開銷和數據準確率這2個性能評價參數。

圖3是整個網絡的能量消耗圖，從圖中可以看出:采用網絡編碼時，全網的能量消耗明顯低于非網絡編碼的數據。

圖3 網絡的能耗Fig 3 Energy consumption of network

圖4是采用網絡編碼時的數據恢復準確率，從圖中可以看出:雖然數據恢復的準確率有所反復，但是，基本保持在較高的準確率，在參考能量消耗的基礎上，這個性能是比較理想的。

圖4 網絡的丟包Fig 4 Packet loss of network

4 結論

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

［1］張書奎，樊建席，崔志明.無線傳感器網絡中可靠的數據協作傳輸機制［J］.通信學報，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中一種基于網絡編碼的可靠傳輸算法［J］.湖南師范大學學報:自然科學版，2008(1):59-64.

［6］王俊義.編碼分組網絡的效用最大化及網絡編碼在應用方面的研究［D］.北京:北京郵電大學，2008.

［7］陶少國，黃佳慶，楊宗凱.網絡編碼研究綜述［J］.小型微型計算機系統，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.