基于可靠多播網絡下的上下文相關性網絡編碼方案

周艷玲，馬林山

（合肥學院，安徽 合肥 230601）

基于可靠多播網絡下的上下文相關性網絡編碼方案

周艷玲，馬林山

（合肥學院，安徽 合肥 230601）

網絡編碼可以提高多播網絡吞吐量,但傳統的網絡編碼算法中節點的編譯碼很明顯地增加了時間和空間的復雜度。文章給出的方案中，信源節點增加了編碼功能，具有編碼能力的節點對所接受到的信息進行簡單的線性編碼，不需要復雜的局部編碼矩陣和全局編碼向量的計算過程，中間節點和鏈路對所接受的信息塊只提供存儲和轉發的功能，目的節點不需要考慮網絡的拓撲結構和接受到數據塊的次序問題，只要能夠接收到足夠的信息塊，就可以在極短的時間內成功譯碼，恢復原信息。實驗證明，基于上下文相關性的網絡編碼在多播網絡中不僅使得多播傳輸達到理論的傳輸容量，并且降低了時間和空間復雜度，提高了網絡可靠性。

上下文相關性；線性網絡編碼；可靠多播；時間復雜度；空間復雜度

0 引言

網絡編碼引自Ahlswede等人編著的關于網絡編碼的開創性論文[1]。網絡編碼理論使得在單源多播的網絡環境下，數據的傳輸可以達到最大流最小割定理所決定的網絡流量理論上的最大值[2，3]。在多播中應用網絡編碼技術，除了有提升網絡吞吐量的顯著優勢，還有實現多播網絡的流量均衡、提高帶寬利用率、提升網絡的可靠性、降低最優吞吐量問題的計算復雜度[4]等優點。

在有向無環網絡中，研究最早也較為成熟的網絡編碼是線性網絡編碼，在線性網絡編碼中網絡節點對傳輸的信息進行線性操作。在多播網絡中，只要在足夠大的有限域Fq中通過合適的線性網絡編碼，總能使多播傳輸達到其理論的最大容量。線性網絡編碼的核心是確定兩個重要的參量，即局部編碼矩陣和全局編碼向量。局部編碼矩陣針對節點而言，要求該節點需要存在輸出鏈路，即出度不允許為0的節點。全局編碼向量針對鏈路而言，一般為列向量，它們是通過局部編碼矩陣計算得到的。

網絡編碼多播技術與傳統的多播路由機制相比，網絡編碼操作需要消耗額外的計算資源，增加了網絡成本和代價。文獻[5]統計了多播節點執行網絡編碼的運算時間。實驗數據顯示，在極壞的情況下，節點的編碼運算的時間可能達到1000s。文獻[6]從不同的角度對如何降低網絡編碼的代價問題進行了探討。由于多播網絡中節點的編碼和譯碼時間的限制，使得網絡編碼算法的研究至關重要。

本文主要從網絡編碼多播應用出發，針對有向無環的多播網絡提出一種多播網絡中基于上下文相關性的網絡編碼方案，通過在信源節點處對數據包進行劃分、線性編碼、存儲、轉發四個過程，使得信息在傳輸的過程中不需要了解網絡的拓撲結構。中間具有編碼能力的節點對信息的編碼采用最簡單的向量運算，然后對編碼后的信息進行存儲和轉發，不具有編碼能力的節點只對信息進行轉發，克服了傳統的局部編碼矩陣和全局編碼向量復雜的求解過程。此方案利用信源節點、中間節點和信宿節點之間所具有的上下文相關性的關系，使得具有編碼和解碼能力的節點在整個信息傳輸的過程中，縮短時間提高效率。

1 相關工作

文獻[7，8]中提出在有限域上進行線性運算可實現組播，進而提出了多播網絡中的線性網絡編碼（Linear Network Coding，LNC），線性網絡編碼的編碼譯碼簡單，因此，被作為主流的編碼方法。文獻[9，10]把網絡編碼問題轉換為代數問題，把信息的輸入和輸出用轉移矩陣聯系起來，實現了應用狀態變量方程或矩陣解決編譯碼問題。文獻[11，12]針對多播應用，提出一種多項式時間復雜度的線性網絡編碼方法，使得線性網絡編碼的算法復雜度有了一定程度的提高。文獻[13]提出了網絡中建立子樹分解的概念，并基于子樹分解提出了射影幾何編碼的分布式方法，把子樹的全局編碼矢量設計成射影線上的射影點坐標，從而保證了不同路徑上子樹的編碼矢量的線性無關性。在分解子樹方法的啟發下，文獻[14]也使用了子樹分解的方法，通過建立靜態子樹集和動態子樹集，為各個子樹分配全部編碼矢量，但算法是一種拓撲依賴的確定性方法，在拓撲信息未知的情況下，本算法的可行性不強。文獻[15]運用線性規劃理論對網絡編碼的代價進行了分析和建模，提出了最小代價網絡編碼的理論模型，但該模型難以在實際網絡中應用。鑒于此，文獻[16]提出了一種改進的最小代價的網絡編碼算法，該算法遵循了最少關鍵鏈路優先的原則，實現了兩點操作，一方面盡可能減少關鍵鏈路，另一方面使已經使用的鏈路次優先。該算法能夠在一定程度上保證在實現多播的理論容量的前提下形成包含較少的關鍵路徑，但是，當關鍵鏈路成為瓶頸時，會使網絡延遲加大，甚至會使網絡的效率明顯下降。

網絡編碼的出現，在一定程度上使得多播的傳輸容量得以提高，但是網絡編碼操作需要消耗額外的計算資源，增加了成本和代價，因此，有必要探討一種編碼和譯碼簡單、容錯能力強、安全性好的可靠的多播傳輸模式。

2 上下文相關性網絡編碼方案

本文僅考慮單源即僅有一個源節點，如果是多源的情況下，只需要引入一個超源節點即可。設向量x=(x1，x2，x3，…，xn)表示源節點初次劃分的消息向量。在本文中源節點根據下行鏈路的數量來決定消息的發送速率，當源節點的出度為h時，其發送的速率為h。節點和鏈路上所傳輸的消息y為x消息向量的線性向量。在本文中不管是行向量還是列向量，都是定義在某個有限域Fq上的，這樣可以保證運算有意義。

2.1 上下文相關性網絡編碼引入

在網絡編碼下的多播中，源節點對數據包的處理功能由傳統的分塊、存儲、轉發三個基本功能，變成分塊、編碼、存儲、轉發。保證了網絡中的數據包在傳輸的過程中，不會因為哪個數據包的丟失而引起數據包無法正常接收。源節點發送的數據包始終是數據分塊的編碼后的數據包，因此，網絡傳輸過程中的安全性和可靠性也顯著提高。在目的節點處，根據收到的數據包中的一部分信息組成可逆矩陣，另一部分組成編碼包向量，通過這兩部分的運算可以得到原數據包按順序分塊的數據包，從而得到原信息流。這種多播中的源節點、中間節點以及目的節點三者之間的編碼、解碼的過程完全具有上下文的相互聯系、互相影響的關系，因此，具有上下文相關性的特點。

2.2 上下文相關性網絡編碼下的源節點多播流

源節點將原始的數據劃分成n個數據塊，并且源節點具有編碼能力，將分塊后的網絡流在每一條鏈路上進行編碼，并且將編碼矩陣連同編碼后的網絡流一起傳輸。圖1為原數據流被劃分成三個數據塊m1、m2、m3，經過線性網絡編碼后，三個數據塊又形成了三個不同的線性編碼數據塊M1、M2、M3，三個編碼后的數據塊連同它們的編碼系數矩陣一起分別形成了三個數據包M1、M2、M3，這三個數據包分別由三條鏈路轉發到對應的下游節點路由器。源節點在對分塊包編碼的過程中，編碼系數向量能夠形成的系數矩陣A，且A是可逆的，即A-1有解，如圖2所示。

圖1 源節點數據流的劃分、編碼、轉發圖

圖2 源節點編碼后的信息系數形成的矩陣圖

2.3 上下文相關性網絡編碼下的多播中間節點

在多播網絡拓撲圖中，除了源節點和目的節點，其他節點稱為中間節點，在傳統的網絡中，中間節點都具有存儲和路由轉發能力。在網絡編碼多播網絡中，當中間節點的入度大于1時，這個節點具有編碼能力，當中間節點的入度等于1時，這個中間節點不需要具有編碼能力。圖3為具有網絡編碼能力的節點和不具有網絡編碼能力的節點比較。具有編碼能力的網絡節點采用最簡單的線性網絡編碼。在編解碼的過程中需要的時間最短，編碼算法簡單。

圖3 編碼節點和非編碼節點信息轉發圖

2.4 上下文相關性網絡編碼下的多播目的節點

在多播網絡中，目的節點所接受到的數據由兩部分組成，一部分為線性網絡編碼后的信息流，另一部分為線性編碼系數向量。在目的節點所接受的信息流，不需要關心信息流的次序問題，只需要關心是否收到與目的節點入度數相同的信息流數量，然后將信息流分離，按照接收的次序，將線性編碼系數向量組成線性系數矩陣，將線性編碼后的信息流組成一個目的信息流向量，經過運算得到原信息流的向量組合，最終形成原始數據。這個方法較傳統方法的優點是，算法簡單，不需要復雜的局部編碼矩陣和全局編碼向量的運算，減少了中間編碼節點的開銷，節省了時間，方便了計算。另外，在源節點就對信息流進行了信息分割和信息編碼，使得信息在傳輸過程中安全系數更高，并且節點和相鄰鏈路、鏈路與相鄰節點之間的信息傳遞的計算時間降低，傳輸速度提高，不需要太多的緩沖存儲。

2.5 上下文相關性網絡編碼下的多播網絡傳輸

基于網絡編碼下的多播網絡云圖如圖4所示。中間的網絡節點云中的拓撲結構可以已知也可以未知，在網絡傳輸的過程中，只要能夠保證源節點發送信息成功和目的節點接收信息成功，就可以成功地解碼形成原始信息。如果中間的網絡節點云中有某個節點或者某個鏈路出現問題，這時候會由其他的鏈路再次發送網絡編碼數據信息，因為信息都是編碼后形成的，因此，不需要分析哪個數據包丟失，只要在源節點再通過另外一條備份鏈路發送再次編碼后的信息，目的節點能夠接受到一定數量的數據包，就可以成功地還原出原始數據。

圖4 基于網絡編碼下的多播網絡云圖

3 基于上下文相關性網絡編碼下的多播網絡模型

多播網絡用有向圖G(V,E)表示，其中V表示網絡節點的集合，E表示傳輸鏈路（邊）的集合，源節點用S表示，目的節點的集合用T表示。本文中假設有向圖G為單位容量網絡，在圖5中，多播的最大理論傳輸容量為3個單位，源節點中的原始的數據包為m，在源節點處經過分塊和線性網絡編碼兩個過程，其中數據包m被原始分塊成三個數據塊m1、m2、m3，再次經過線性網絡編碼，最終形成了M1、M2和M3三個數據包。并且，原始編碼數據包塊M1、M2、M3系數向量形成的矩陣可逆。圖6為網絡拓撲圖和經過上下文網絡編碼后的網絡流傳輸圖。

圖5 網絡拓撲圖

圖6 網絡編碼后網絡流傳輸圖

3.1 每個節點編碼后的數據包

數據由上游的源點經過中間節點編碼、存儲、轉發后形成的網絡編碼數據流，以及到達最終的目的節點所形成的數據包流的集合而成。

3.2 在目的節點t1和t2可以收到的信息流

目的節點t1收到的信息流的6種可能組合，分別 為 （M1 M12 M23）、（M1 M23 M12）、（M12 M1 M23）、（M12 M23 M1）、（M23 M1 M12）、（M23 M12 M1）。

目的節點t2收到的信息流的6種可能組合，分別 為 （M12 M23 M3）、（M12 M3 M23）、（M3 M12 M23）、（M3 M23 M12）、（M23 M12 M3）、（M23 M3 M12）。

在目的節點所收到的編碼信息流塊的組合可能為上面六種情況的任意一種。不管是哪種情況的組合，都可以還原出原始信息流。

3.3 目的節點解碼過程

假設t1收到的編碼信息流塊的組合為（M1 M12 M23），那么解碼的過程為：

將信息塊組合按照一定的順序分解和再組合，將線性組合系數向量形成的編碼矩陣為設為A，將編碼信息流形成信息流向量設為C，通過矩陣A和向量C的運算可以求出原信息流塊，然后將原信息流塊按照順序組合形成原信息流。公式如式（1）、（2）、（3）、（4）所示。

4 上下文相關性網絡編碼多播復雜性分析

基于上下文相關性的網絡編碼多播與傳統的多播相比，其復雜性明顯降低。本文所提出的方案中仍然采用最簡單的線性網絡編碼算法，它與傳統的線性網絡編碼有明顯的不同，傳統的線性網絡編碼過程包括中間節點的局部網絡編碼矩陣和網絡鏈路的全局網絡編碼向量，不管是哪種編碼方式，其轉換的過程都需要大量的運算時間，如果網絡節點的數量為n，鏈路數量為e，目的節點的數量是t，傳統多項式復雜度的線性網絡編碼算法的復雜度為O(eth(h+e))。基于上下文相關性網絡編碼多播中，參與編碼的節點有源節點和入度不小于2的中間節點，參與解碼的節點只為目的節點。在整個數據傳輸的過程中，不存在每一個節點的局部編碼矩陣和每一條鏈路的全局編碼向量的計算過程，中間的不具有編碼能力的節點和網絡中的所有鏈路都只是起到了接收信息和轉發信息的功能。并且在整個傳輸的過程中，傳輸的信息始終為線性編碼系數向量，不需要編碼矩陣的復雜運算，因此，節省了大量的時間。目的節點接收到的信息是向量集合，目的節點只需要通過簡單的組合，就可以形成編碼矩陣和編碼系數向量，從而求得原始的數據。相比之下，復雜度遠遠小于傳統的線性網絡編碼，其復雜度為O(n)。

本文中的方案與傳統多項式復雜度的網絡編碼復雜度的比較圖如圖7所示。算法1線為本文中的基于上下文的網絡編碼方案中所體現的時間復雜度，算法2線為傳統的多項式復雜度網絡編碼算法所體現的時間復雜度。通過圖7可以看出，本文的方案隨著網絡節點的增多，其復雜度呈現緩慢增長的趨勢，而傳統的多項式復雜度網絡編碼算法其復雜度隨著網絡節點的增加呈現快速增長的趨勢。實驗證明，隨著網絡節點數的增加，該方案的優勢更加突出。

圖7 算法1和算法2時間復雜度比較圖

5 結語

基于上下文多播網絡中的網絡編碼方案可用于解決在網絡拓撲結構未知的情況下的無圈有向網絡的可靠多播問題。該方案的實現是通過在源節點處增加了編碼的功能，使得源節點由傳統的分塊、存儲、轉發三功能變為分塊、編碼、存儲、轉發四個功能。在中間的網絡節點和鏈路處，避免了傳統線性編碼由于計算節點的局部編碼矩陣和鏈路編碼向量所帶來的計算和存儲代價的增加。只要源節點能夠保證原信息分塊編碼后的向量所組成的系數矩陣是可逆矩陣，目的節點在接收到足夠多的信息塊后，就可以成功譯碼，還原原始的信息，并且不需要考慮信息的次序問題。這在一定程度上節省了時間和存儲資源，同時，由于信息都是編碼后的數據塊，所以也不會因為傳輸過程中消息的丟失而產生牽連效應，以至于目的節點不能及時成功譯碼，從而增大譯碼時延的問題。

基于上下文多播網絡中的編碼方案是一種簡單的線性編碼算法，其實現的條件必須是源節點具有編碼的功能，并且在源節點處，信息編碼也需要一定的計算時間，這就要求源節點的能量必須充足，功能必須強大。另外，本方案在安全性方面也有了一定的提高。當然網絡中也避免不了可能存在重點節點加入垃圾消息或病毒，若不能正確和及時識別，經編碼后將造成垃圾消息或病毒的擴散，最終使得目的節點無法譯碼。因此，在后期工作中，需要在多播的安全性方面對本文的方案進一步改進。

［1］Ahlswede R，Cai Ning，Y S，et al.Network information flow［J］.IEEE Trans.on Inform Theory，2000，46（4）:1204-1216.

［2］Yeung R W，Li S Y R，Cai N，et al.Network coding theory［M］.Hanover:Now Publishers Inc，2006.

［3］黃佳慶，程文青.信息論基礎［M］.北京：電子工業出版社，2010.

［4］黃佳慶，李宗鵬.網絡編碼原理［M］.北京：國防工業出版社，2012.

［5］Ho T，Medard M，Koetter R，et al.A Random Linear Network Coding Approach to Multicast［J］.IEEE Transactions on Information Theroy，2006，52（10）:4413-4430.

［6］Ebrahimi J B，Fragouli C.Algebraic Algorithm for Vector Network coding［J］.IEEE Transactions on Information Theory，2011，57（2）:996-1007.

［7］Li S Y，Sun Q，Shao Z，et al.Linear Network Coding:Theory and Algorithms［J］.Proceedings of the IEEE，2011，99（3）:372-387.

［8］Ma S Y，Zhuo X J，Guo Q，et al.A Unified Result for Variable-rate Linear Network Coding［J］.Journal of Harbin Institute of Technology,2010，17（5）:657-660.

［9］Dougherty R，Freiling C，Zeger K.Insufficiency of Linear Coding in Network Information flow［J］.IEEE Transaction on Information Theory，2005，51（8）:2745-2759.

［10］Fong S L，Yeung R W.Variable-rate Linear Network Coding［J］.IEEETransactiononInformationTheory，2010，56（6）:2618-2625.

［11］Jaggi S，Sanders P，Chou P A，et al.Polynomial Time Algorithms for Multicast Network Code Construction ［J］.IEEE TransactionsofInformationTheory，2005，51（6）:1973-1982.

［12］Li S Y R，Cai N,Yeung R W.On Theory of Linear Network Coding［A］.IEEE ISIT［C］.2005.

［13］Fragouli C，Soljanin E.Information Flow Decomposition for Network Coding［J］.IEEETransactiononInformationTheory，2004，52（3）:829-848.

［14］劉宴濤，夏桂陽，等.一種基于子樹分解的組播線性網絡編碼算法［J］.計算機工程，2015，41（11）：153-159.

［15］Bhattad K，Ratnakar N，Koetter R,et al.Minimal network coding for multicast［A］.IEEE International Symposium on Information Theory［C］.Melbourne:IEEE Communication Society，2005:1730-1734.

［16］陶少國，黃佳慶，等.一種改進的最小代價網絡編碼算法［J］.華中科技大學學報（自然科學版），2008，36（5）:1-4.

Context Correlation Network Coding Scheme under the Reliable Multicast Network

ZHOU Yan-ling，MA Lin-shan
（Hefei University，Hefei 230601，China)

Network coding can improve the multicast network throughput，but the encoding nodes and decoding nodes of traditional network codingalgorithmobviouslyincreased the complexityoftime and space.In this scheme，the source code can encode the blocked packets.The encoding nodes encoded the packets simply and didn’t need to intricately compute the local encoding matrix and the global coding vector.The middle nodes and links that have no encoding ability only store and forward the data packet.The destination nodes do not need to consider the network topology and the data-block order.As long as they can receive enough packets，they can decode successfully in a very short time and restore the original information.The experiments prove that the scheme can not only make the multicast reach the transmission capacity in theory，but also reduce the time and space complexityand enhance the reliabilityofmulticast network.

context correlation；linear network coding；reliable multicast；time complexity；space complexity

TP393.01

A

1674-3229（2017）03-0026-06

2017-05-25

安徽省教育廳自然科學資助項目（KJ2016A609）;安徽高校人文社會科學研究重點項目（SK2017A0606）

周艷玲（1979-）,女，博士，合肥學院計算機科學與技術系講師，研究方向：多播技術、網絡編碼等。