噴泉編碼在DTN網絡中的應用研究

徐鍵卉，杜昊陽，雷旺春，王青媛

(解放軍理工大學 通信工程學院，江蘇 南京210007)

?

噴泉編碼在DTN網絡中的應用研究

徐鍵卉，杜昊陽，雷旺春，王青媛

(解放軍理工大學 通信工程學院，江蘇 南京210007)

摘要：DTN(Delay and Disruption Tolerant Networks)的間歇連通性以及數據包易丟失的特性給數據傳輸帶來了很大挑戰。針對這一問題，大量的研究表明[1-3]在DTN中使用網絡編碼能有效提升其數據傳輸能力，但網絡編碼的使用又會帶來較高的復雜度和較大的編碼時延,以及更高的能量消耗。指出將噴泉碼應用于DTN網絡可以有效克服上述問題，并對目前噴泉碼在DTN網絡的研究現狀做了分析與總結。

關鍵詞：網絡編碼；噴泉編碼；DTN網絡；編譯碼復雜度；傳輸延遲

0引言

DTN網絡是為處理受限網絡中頻繁網絡斷開、高延時和異構性等問題而提出的一種覆蓋型網絡架構，是一種針對端到端連接和結點資源受限時的網絡解決方法，以滿足隨機性的異步消息的可靠性傳遞[1]。對DTN的研究將會對未來軍事戰爭、深空通信以及應急搶險等領域提供重要的科學依據[2]。

DTN網絡的上述特點使得網絡中節點間轉發機會變得極其稀缺與重要,因此在提高網絡吞吐量的同時盡量減少數據傳輸次數,成為了DTN網絡研究的重點內容[3]。而事實證明通過在信源處數據分塊后進行網絡編碼、在信宿處進行數據譯碼的方法，可以在較少的傳輸次數下達到較高的網絡吞吐量。但是同時該方法帶來較高的復雜度和較大的編碼時延,以及更高的能量消耗。而噴泉碼的優勢在于：① 可以像其他網絡編碼一樣有效提升系統吞吐量；② 較低的編譯碼復雜度將有效減少編譯碼時延；③ 無須反饋的特點又大大減小了傳輸時延；④ 無速率的特性使得其對復雜信道具有良好的適應能力[4]。

1DTN網絡

1.1DTN網絡簡介

DTN網絡最初來源于IPN(Interplanetary Internet)通信中遇到的問題，并于2003年由K.Fall等人作為正式網絡概念提出。初衷是盡力使得數據在地球與很遠距離的星空間的通信就好像地球上任何2個地方通信一樣簡單。之后這一概念被廣泛應用于野生動物監測傳感網絡、移動車載網、戰術通信網、口袋交換網、水下傳感器網、鄉村通信網絡和空間光通信網等一系列“受限網絡(challengednetworks) ”。

由于傳統的TCP/IP協議的因特網服務模型基于以下假設[5]：① 在通信持續的時間里，信源和信宿之間必須存在端到端路徑；② 節點間通信的最大往返時間不能太長；③ 丟包率較小等。因此單是對于太空通信這種高延遲、和高中斷率的鏈路來說，就足以說明TCP/IP協議不再實用于DTN網絡。

為了克服TCP/IP協議的不足，DTN網絡利用位于傳輸層和應用層之間的Bundle層通過持久存儲來應對網絡的頻繁中斷以及高時延問題，包括逐跳的可靠數據傳遞以及路徑的選擇。可見，Bundle層是一個端到端的面向消息的網絡覆蓋層，在這種機制中,發送方在發送Bundle包的同時會開啟一個等待確認的定時器。若下一個結點正確接收到Bundle包,則返回一個成功的信號給發送方;否則將不做任何反應,并且等待超時后發送方重傳該Bundle包[6]。

這種利用中間結點的“存儲-運載-轉發”技術，的確可以在鏈路不存在的時候將信息緩存下來，然后等待時機再次傳輸，但是當出現丟包或傳輸出錯的現象時，它的這種“確認重傳”機制無疑會造成更大的傳輸延遲，從而降低了數據信息傳輸的有效性和可靠性。

1.2DTN網絡的路由協議研究

在DTN網絡中，一個很關鍵的問題就是路由問題。而在DTN體系結構中，路由是在Bundle層完成的。由于網絡連接經常斷開和巨大的延遲，傳統的Internet中的路由協議在 DTN 中基本不可用，因此有必要研究針對DTN網絡特性的路由。

因為極大部分的DTN網絡中各個節點的運動是隨機的,無法對其未來的運動軌跡進行準確的預測與計算,所以對DTN路由算法的研究主要集中于隨機性路由，主要分為以下4類[7]。

(1)基于擴散的DTN路由

該路由協議的核心思想是,當網絡中的某節點接收到信息后，將其復制轉發給通信范圍內的所有其他節點，所以該路由又被稱為“傳染病路由”。此路由算法無須了解網絡的任何先驗知識,實現較為簡單,但消耗較高的網絡資源。

(2)基于機會鏈路代價評估的DTN路由

與擴散路由相比,該路由協議的特點是：中間節點不再是簡單的復制轉發，而是需要對通信范圍內的每一條機會鏈路進行轉發代價的評估，從而決定是直接對數據進行復制轉發還是等待最優路徑出現后再復制轉發。

(3)基于構建移動模型的DTN路由

通常情況下，DTN網絡中的節點經過一系列運動過后,其運動軌跡都會呈現出一定的規律性，并不能說成完全隨機的運動，所以對DTN網絡中節點的運動軌跡構建相應的移動模型有一定的研究價值。

(4)基于網絡編碼的DTN路由

在信源處進行數據分塊并進行網絡編碼、在信宿處進行數據譯碼的方法，可以在較少的傳輸次數下達到較高的網絡吞吐量。雖然該方法有上述優點，但網絡編碼的使用通常會帶來較高的復雜度、較大的編碼時延以及更高的能量消耗。

2噴泉編碼

1998年Luby等人為了解決大規模數據分發以及可靠傳輸的問題，首次提出了數字噴泉的概念。該概念的思想是將被傳輸的數據進行編碼，形成“一粒粒水滴”，接收端只須接收到足夠的“水滴”便可以高概率譯碼，而不用去考慮具體接收到了哪些“水滴”。2002年Luby提出了第一種實用的噴泉碼—LT碼(Luby transform code);2006年Shokrollahi在LT碼的基礎上提出了一種性能更優的Raptor碼，目前，一種由Digital Fountain公司設計的系統Raptor碼已經被DVB-H標準和3GPP組織的多媒體廣播和組播業務(MBMS)標準采用，并且正在參與其他多項國際標準的制定。2011年Luby等人再次提出了一種伽羅華域GF(256)的Raptor碼，稱為RaptorQ碼[8]，在譯碼開銷接近于零的情況下可以將誤碼率降低到10-7以下，并且可以支持更多信息分組的編碼傳輸，隨之而來的缺點是較高的編譯碼復雜度。

2.1噴泉碼的性能評估

噴泉碼性能的好壞決定于以下因素[9]：

定義1：度分布(degree distribution)：表示噴泉碼編碼過程中形成每個編碼包所需要選取的數據包的個數，是決定噴泉碼性能優劣的重要指標。

定義2：編碼復雜度(encoding complexity)：生成編碼分組時所需計算的操作次數。

定義3：譯碼復雜度(decoding complexity)：成功譯碼時所需計算的操作的次數。

定義4：譯碼開銷(overhead)：定義為ε=m/k-1，其中m為成功譯碼時所需要接收的數據包個數，k為輸入端參與形成編碼包的所有數據包個數。

2.2LT碼

LT碼作為第一種實用的噴泉碼，其編碼過程(如圖1所示)較為簡單，下面就某一編碼包的產生過程介紹如下：

① 由已定的度分布ρ(d)隨機選取一個度值d;

② 從輸入端的原始數據包中隨機選取d個不同的數據包;

③ 將這d個不同的數據包求異或和，生成該編碼包。

圖1　LT編碼過程

由于噴泉碼的無速率性，按照該編碼方法可以產生無數的編碼包，就像噴泉中有無數“水滴”一樣。此時，接收端只要接收到足夠的“水滴”便可以高概率譯碼。

譯碼方法的選取關乎噴泉碼的性能，目前LT碼的主要譯碼方法有BP譯碼、GE譯碼(高斯消元法)以及BPML譯碼。其中，GE譯碼是矩陣求逆的常用方法,通過對矩陣行(列)變換將矩陣變為上三角或下三角，之后再通過回代來求解每一個未知量，雖然具有較好的誤碼率性能,但譯碼復雜度隨著碼長的增加非線性的增長，只適合碼長較短的噴泉碼。BP譯碼即置信傳播譯碼，是一種低復雜度的迭代譯碼方法，但由于每次迭代譯碼均需要從度數為1的編碼包開始，當不存在這樣的編碼包時譯碼便以失敗告終，所以其缺點是誤碼率較高。而BPML譯碼算法[10]巧妙的結合了二者的優勢，不但具有很好的譯碼性能，而且具有較低的譯碼復雜度。

由上述分析可知，度分布不僅關系到編碼復雜度，而且還關系到LT碼的譯碼成功率，因此如何設計好的度分布對LT碼的整體性能至關重要，文獻[9]已給出了能夠使LT碼實現高概率成功譯碼的魯棒孤分子度分布,其平均編碼復雜度為lnk,其中k為原來的數據包數目。因此,要產生k個數據包大概需要klnk次異或運算,這說明LT碼的編碼并不具有線性復雜度。

2.3Raptor碼

由2.2可知，盡管LT碼對度分布進行了精心的設計，但在譯碼時還需要很大的開銷。原因如下[11]：

① 當只有少部分輸入數據包未被譯出時，隨著譯碼的繼續，譯碼成功的概率增加的越來越緩慢，此時不得不接收更多的編碼包，導致譯碼開銷變得更大；

② LT編碼包中少量連接度高的包，雖然保證了對所有數據包的良好覆蓋，但同時它又造成了可譯集的減小，從而降低了譯碼成功率。

基于上述原因，Raptor碼提出了2步編碼(如圖2所示)的方式[12]:首先，對原始信息進行預編碼，一般采用LDPC碼或漢明碼，然后通過弱化的LT碼對數據進行編碼并分發。所謂弱化的LT編碼是指它生成的編碼包不存在連接度較高的包，只通過它無法完整譯出原始信息。Raptor碼的編碼過程的復雜度為O(kln(1/ε)),可見與碼長成線性關系，優于LT碼。

圖2　Raptor編碼過程

3噴泉碼在DTN中應用的研究現狀

3.1網絡編碼在DTN中的應用

網絡編碼在提高DTN網絡吞吐量以及數據包投遞率等方面具有很大優勢，文獻[13]對其進行了詳細的說明并進行了仿真驗證。在文獻[14]提出一種在網絡拓撲以及多播容量動態變化條件下的動態隨機網絡編碼傳輸方法之前，研究者們通常都假設DTN的網絡拓撲為靜態或者多播容量已知且不變，很明顯這種假設不符合實際情況。此外，文獻中指出相比于傳統的固定多播率編碼方法，動態隨機網絡編碼方法降低了數據的平均傳遞延遲，提高了數據投遞率。需要指出的是雖然文獻中提到的方法對提高DTN網絡的傳輸能力具有重要意義，但是相比于對信道具有良好適應性的噴泉碼而言，這種方法太過于繁雜，主要表現在為了獲取信道速率和信道容量而進行的各種復雜的算法上。

3.2噴泉編碼在DTN中應用的研究現狀

噴泉碼的無速率性對各種復雜信道的適應能力以及很低的編譯碼復雜度，使得其在DTN網絡中的應用有巨大意義。文獻[15]中提到，之前采用的固定編碼速率的可擦除編碼機制中存在一個弊端，那就是為了達到最優的編碼速率，設計時會盡量將編碼速率的值定的很高，這樣一來就會耗費很大的網絡資源，比如說帶寬。此外，由于實際的信道狀況是隨著時間改變而改變的，這就需要一種無速率碼能夠更好的適應信道的復雜變化。最后文獻通過仿真證實，將噴泉碼應用于DTN網絡中在可靠性、傳輸延遲等方面均取得了非常顯著的效果。

此外，噴泉碼應用于DTN網絡可以大大節約能耗。文獻[16]中提到隨著車載通信中路車間的頻繁通信，所消耗的能量不容小覷，所以從節能和環保的角度考慮，在保證通信質量的前提下，降低車載通信中的能耗具有很大的現實意義。

文中最初的設想是，由于無線信號的衰落隨傳輸距離的增大而指數增加，所以可以通過將一個路邊設施的大覆蓋區域劃分成多個路邊設施的小覆蓋區域的方法來降低能耗。但這樣帶來的問題是：① 車輛通過一個路邊設施的小型覆蓋區域往往不能完全接收到所需要的信息，造成譯碼失敗，這樣就需要多個路邊設施共同協作，達到正確譯碼的目的；② 為了保證路邊設施向車輛發送的數據包能夠被正確的接收，往往通過逐一的發送反饋信息，這無疑增大了控制的復雜度；③ 當某個路邊設施向多個車輛廣播信息時，為了保證每個車輛可以按順序正確的接收到所有的數據包，就必須再次增大反饋的信息流以及控制的復雜度。文章指出在傳輸過程中采用噴泉編碼能夠有效克服以上問題。具體做法如下：首先，不同路邊設施對n個數據包進行噴泉編碼得到任意數量的編碼包，之后多個路邊設施的協作接力將足量的編碼包傳輸給目的車輛，研究表明目的車輛只須接收夠任意(1+ε)n(ε為譯碼開銷，一般為0.05到0.1)個數據包，便可以高概率譯碼；其次，當向多個車輛廣播信息時，路邊設施可以模糊掉車輛之間的差異，不用為某一車輛傳輸特定的信息，而任何一個車輛只要收到任意(1+ε)n個數據包，便可以高概率譯碼。可見，通過對發送信息進行噴泉編碼后再傳輸的方法，可以大大簡化路邊設施發送信息時的控制復雜度，同時減少反饋信息量，甚至不需要反饋信息。文獻最后通過數值計算以及仿真證實：將噴泉碼應用于該網絡中有效減少了數據包的發送量、從而大大降低了能源消耗。

4結束語

將噴泉碼應用于具體的網絡中是數字噴泉碼在網絡環境中的自然擴展，也是當前數字噴泉碼研究的一個重要趨勢，正引起越來越多的關注。本文介紹了噴泉碼和DTN網絡的基本概念，指出了噴泉碼相比于其他網絡編碼的優勢，對噴泉碼在DTN網絡中應用的研究現狀進行了列舉與分析，得出以下結論：① 噴泉碼對復雜信道有良好的適應性，非常適合于DTN這種信道條件瞬息萬變的網絡環境；② 噴泉碼不僅可以提高系統吞吐量、數據投遞率，同時還可以大大縮短傳輸時延。

但是目前對于噴泉碼在具體網絡中的應用研究仍處于起步階段，現有的研究成果仍是不全面的和零散的，系統性的理論尚未形成，許多方面仍然需要進一步研究[17]：① 對網絡整體性能進行規劃，研究適合具體網絡的噴泉碼度分布以及網絡編碼策略，使網絡吞吐量達到最大；② 目前的研究主要局限于基本的網絡結構模型如單跳中繼網絡、多跳中繼網絡、多信源單信宿網絡等，而對于復雜的網絡結構模型中噴泉編碼的應用方面所做的研究工作甚少；③ 目前研究的噴泉碼的應用網絡模型中主要局限于譯碼轉發型，而對放大轉發型的研究甚少。后者中各信源度分布與總體度分布的關系較為復雜，所以仍然有待對其漸近性能做深入的分析。

噴泉碼在具體網絡(例如DTN網絡)中的應用作為數字噴泉碼發展過程中的重要分支，是一種高效的網絡傳輸策略，目前正處于起步和不斷完善階段。隨著噴泉碼在網絡中應用的深入研究，相信其研究成果必將為網絡信息理論的發展提供強大的推動力。

參考文獻

[1]Yoon S K,Haas Z J.Invited Paper Application of Linear Network Coding in Delay Tolerant Networks[C]∥Ubiquitous and Future Networks(ICUFN),2010 Second International Conference on.IEEE,2010:338 - 343.

[2]Bao J,Zhang S,Zhang J,et al.Secure Efficient Routing Based on Network Coding in the Delay Tolerant Networks[C]∥Software Engineering and Service Science(ICSESS),2014 5th IEEE International Conference on.IEEE,2014:456 - 459.

[3]Zeng D,Guo S,Jin H,et al.Segmented Network Coding for Stream-Like Applications in Delay Tolerant Networks[C]∥Global Telecommunications Conference(GLOBECOM 2011),IEEE,2011:1 - 5.

[4]Mousavi L S M,Jabbehdari S,Yousefi S,et al.File transfer in Vehicular Delay Tolerant Networks using Fountain coding[C]∥Computer and Knowledge Engineering(ICCKE).2013 3th International Conference on,IEEE,2013:121 - 128.

[5]侯君婷.簡析DTN網絡與傳統網絡的區別[J].電信快報:網絡與通信,2010(4):44-46.

[6]周建國.基于DTN的空間綜合信息網絡關鍵技術研究[D].武漢:武漢大學,2013:23-30.

[7]白云飛.基于鏈路代價綜合評估和網絡編碼的延遲容忍網絡路由優化研究[D].北京:北京郵電大學,2012:21-33.

[8]IETF RFC(6330(2011)):RaptorQ Forward Error Correction Scheme for Object Delivery[S],2011：2551-2567.

[9]Luby M.LT Codes[C]∥Proceedings of the 43rd Symposium on Foundations of Computer Science.IEEE Computer Society,2002:271-282.

[10]朱宏鵬,李廣俠,馮少棟.LT碼的BPML譯碼算法[J].計算機科學,2009,36(10):77-81.

[11]杜超.深空通信中噴泉碼編譯碼性能研究[D].黑龍江:哈爾濱工業大學,2009:18-22.

[12]Shokrollahi A.Raptor Codes[J].IEEE Transactions on Information Theory,2004,52(6):2551-2567.

[13]Zhang Q,Jin Z,Zhang Z,et al.Network Coding for Applications in the Delay Tolerant Network(DTN)[C]∥Proceedings of the 2009 Fifth International Conference on Mobile Ad-hoc and Sensor Networks.IEEE Computer Society,2009:376-380.

[14]鄧廣宏,曹萬華,張劍,等.DTN網絡環境下動態隨機網絡編碼方法[J].通信學報,2014,(2):76-86.

[15]Vellambi B N,Subramanian R,Fekri F,et al.Reliable and Efficient Message Delivery in Delay Tolerant Networks Using Rateless Codes[C]∥ Proceedings of the 1st international MobiSys workshop on Mobile opportunistic networking,ACM:2007:91-98.

[16]雷維嘉,陳佳,李世成.一種路-車通信中的噴泉協作節能傳輸機制[J].重慶郵電大學學報:自然科學版,2012,24(5):559-566.

[17]徐大專,邵漢欽,張小飛,等.數字噴泉碼及網絡噴泉碼的最新進展[J].數據采集與處理,2014,29(3):351-362.

Application of Fountain Code in DTN

XU Jian-hui,DU hao-yang,LEI Wang-chun,WANG Qing-yuan

(College of Communications Engineering,PLA University of Science and Technology,Nanjing Jiangsu 210007,China)

Abstract：DTN poses many challenges on file transferring due to intermittent connectivity and packet loss.To improve file transfer in DTN,lots of research results show that network coding can effectively improve the capability of data transmission.However the use of network coding brings about such problem as high encoding and decoding complexity,long data transmission delay and high energy consumption.This paper presents that fountain code can effectively overcome above-mentioned problems,at the same time,analyzes and summarizes the present research of the application of fountain code in DTN.

Key words：network coding; fountain coding; DTN; encoding and decoding complexity; transmission delay

中圖分類號：TN91

文獻標志碼：A

文章編號：1003-3114(2016)03-110-5

作者簡介：徐鍵卉(1990—)，女，碩士研究生，主要研究方向：衛星通信、噴泉編碼。杜昊陽(1990—),男，碩士研究生，主要研究方向：短波通信、信道編碼。

收稿日期：2016-01-04

doi:10.3969/j.issn.1003-3114.2016.03.29

引用格式：徐鍵卉，杜昊陽，雷旺春，等.噴泉編碼在DTN網絡中的應用研究[J].無線電通信技術,2016,42(3):110-114.