基于可靠多播網(wǎng)絡(luò)下的上下文相關(guān)性網(wǎng)絡(luò)編碼方案

周艷玲，馬林山

（合肥學(xué)院，安徽 合肥 230601）

基于可靠多播網(wǎng)絡(luò)下的上下文相關(guān)性網(wǎng)絡(luò)編碼方案

周艷玲，馬林山

（合肥學(xué)院，安徽 合肥 230601）

網(wǎng)絡(luò)編碼可以提高多播網(wǎng)絡(luò)吞吐量,但傳統(tǒng)的網(wǎng)絡(luò)編碼算法中節(jié)點(diǎn)的編譯碼很明顯地增加了時(shí)間和空間的復(fù)雜度。文章給出的方案中，信源節(jié)點(diǎn)增加了編碼功能，具有編碼能力的節(jié)點(diǎn)對所接受到的信息進(jìn)行簡單的線性編碼，不需要復(fù)雜的局部編碼矩陣和全局編碼向量的計(jì)算過程，中間節(jié)點(diǎn)和鏈路對所接受的信息塊只提供存儲和轉(zhuǎn)發(fā)的功能，目的節(jié)點(diǎn)不需要考慮網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和接受到數(shù)據(jù)塊的次序問題，只要能夠接收到足夠的信息塊，就可以在極短的時(shí)間內(nèi)成功譯碼，恢復(fù)原信息。實(shí)驗(yàn)證明，基于上下文相關(guān)性的網(wǎng)絡(luò)編碼在多播網(wǎng)絡(luò)中不僅使得多播傳輸達(dá)到理論的傳輸容量，并且降低了時(shí)間和空間復(fù)雜度，提高了網(wǎng)絡(luò)可靠性。

上下文相關(guān)性；線性網(wǎng)絡(luò)編碼；可靠多播；時(shí)間復(fù)雜度；空間復(fù)雜度

0 引言

網(wǎng)絡(luò)編碼引自Ahlswede等人編著的關(guān)于網(wǎng)絡(luò)編碼的開創(chuàng)性論文[1]。網(wǎng)絡(luò)編碼理論使得在單源多播的網(wǎng)絡(luò)環(huán)境下，數(shù)據(jù)的傳輸可以達(dá)到最大流最小割定理所決定的網(wǎng)絡(luò)流量理論上的最大值[2，3]。在多播中應(yīng)用網(wǎng)絡(luò)編碼技術(shù)，除了有提升網(wǎng)絡(luò)吞吐量的顯著優(yōu)勢，還有實(shí)現(xiàn)多播網(wǎng)絡(luò)的流量均衡、提高帶寬利用率、提升網(wǎng)絡(luò)的可靠性、降低最優(yōu)吞吐量問題的計(jì)算復(fù)雜度[4]等優(yōu)點(diǎn)。

在有向無環(huán)網(wǎng)絡(luò)中，研究最早也較為成熟的網(wǎng)絡(luò)編碼是線性網(wǎng)絡(luò)編碼，在線性網(wǎng)絡(luò)編碼中網(wǎng)絡(luò)節(jié)點(diǎn)對傳輸?shù)男畔⑦M(jìn)行線性操作。在多播網(wǎng)絡(luò)中，只要在足夠大的有限域Fq中通過合適的線性網(wǎng)絡(luò)編碼，總能使多播傳輸達(dá)到其理論的最大容量。線性網(wǎng)絡(luò)編碼的核心是確定兩個(gè)重要的參量，即局部編碼矩陣和全局編碼向量。局部編碼矩陣針對節(jié)點(diǎn)而言，要求該節(jié)點(diǎn)需要存在輸出鏈路，即出度不允許為0的節(jié)點(diǎn)。全局編碼向量針對鏈路而言，一般為列向量，它們是通過局部編碼矩陣計(jì)算得到的。

網(wǎng)絡(luò)編碼多播技術(shù)與傳統(tǒng)的多播路由機(jī)制相比，網(wǎng)絡(luò)編碼操作需要消耗額外的計(jì)算資源，增加了網(wǎng)絡(luò)成本和代價(jià)。文獻(xiàn)[5]統(tǒng)計(jì)了多播節(jié)點(diǎn)執(zhí)行網(wǎng)絡(luò)編碼的運(yùn)算時(shí)間。實(shí)驗(yàn)數(shù)據(jù)顯示，在極壞的情況下，節(jié)點(diǎn)的編碼運(yùn)算的時(shí)間可能達(dá)到1000s。文獻(xiàn)[6]從不同的角度對如何降低網(wǎng)絡(luò)編碼的代價(jià)問題進(jìn)行了探討。由于多播網(wǎng)絡(luò)中節(jié)點(diǎn)的編碼和譯碼時(shí)間的限制，使得網(wǎng)絡(luò)編碼算法的研究至關(guān)重要。

本文主要從網(wǎng)絡(luò)編碼多播應(yīng)用出發(fā)，針對有向無環(huán)的多播網(wǎng)絡(luò)提出一種多播網(wǎng)絡(luò)中基于上下文相關(guān)性的網(wǎng)絡(luò)編碼方案，通過在信源節(jié)點(diǎn)處對數(shù)據(jù)包進(jìn)行劃分、線性編碼、存儲、轉(zhuǎn)發(fā)四個(gè)過程，使得信息在傳輸?shù)倪^程中不需要了解網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。中間具有編碼能力的節(jié)點(diǎn)對信息的編碼采用最簡單的向量運(yùn)算，然后對編碼后的信息進(jìn)行存儲和轉(zhuǎn)發(fā)，不具有編碼能力的節(jié)點(diǎn)只對信息進(jìn)行轉(zhuǎn)發(fā)，克服了傳統(tǒng)的局部編碼矩陣和全局編碼向量復(fù)雜的求解過程。此方案利用信源節(jié)點(diǎn)、中間節(jié)點(diǎn)和信宿節(jié)點(diǎn)之間所具有的上下文相關(guān)性的關(guān)系，使得具有編碼和解碼能力的節(jié)點(diǎn)在整個(gè)信息傳輸?shù)倪^程中，縮短時(shí)間提高效率。

1 相關(guān)工作

文獻(xiàn)[7，8]中提出在有限域上進(jìn)行線性運(yùn)算可實(shí)現(xiàn)組播，進(jìn)而提出了多播網(wǎng)絡(luò)中的線性網(wǎng)絡(luò)編碼（Linear Network Coding，LNC），線性網(wǎng)絡(luò)編碼的編碼譯碼簡單，因此，被作為主流的編碼方法。文獻(xiàn)[9，10]把網(wǎng)絡(luò)編碼問題轉(zhuǎn)換為代數(shù)問題，把信息的輸入和輸出用轉(zhuǎn)移矩陣聯(lián)系起來，實(shí)現(xiàn)了應(yīng)用狀態(tài)變量方程或矩陣解決編譯碼問題。文獻(xiàn)[11，12]針對多播應(yīng)用，提出一種多項(xiàng)式時(shí)間復(fù)雜度的線性網(wǎng)絡(luò)編碼方法，使得線性網(wǎng)絡(luò)編碼的算法復(fù)雜度有了一定程度的提高。文獻(xiàn)[13]提出了網(wǎng)絡(luò)中建立子樹分解的概念，并基于子樹分解提出了射影幾何編碼的分布式方法，把子樹的全局編碼矢量設(shè)計(jì)成射影線上的射影點(diǎn)坐標(biāo)，從而保證了不同路徑上子樹的編碼矢量的線性無關(guān)性。在分解子樹方法的啟發(fā)下，文獻(xiàn)[14]也使用了子樹分解的方法，通過建立靜態(tài)子樹集和動(dòng)態(tài)子樹集，為各個(gè)子樹分配全部編碼矢量，但算法是一種拓?fù)湟蕾嚨拇_定性方法，在拓?fù)湫畔⑽粗那闆r下，本算法的可行性不強(qiáng)。文獻(xiàn)[15]運(yùn)用線性規(guī)劃理論對網(wǎng)絡(luò)編碼的代價(jià)進(jìn)行了分析和建模，提出了最小代價(jià)網(wǎng)絡(luò)編碼的理論模型，但該模型難以在實(shí)際網(wǎng)絡(luò)中應(yīng)用。鑒于此，文獻(xiàn)[16]提出了一種改進(jìn)的最小代價(jià)的網(wǎng)絡(luò)編碼算法，該算法遵循了最少關(guān)鍵鏈路優(yōu)先的原則，實(shí)現(xiàn)了兩點(diǎn)操作，一方面盡可能減少關(guān)鍵鏈路，另一方面使已經(jīng)使用的鏈路次優(yōu)先。該算法能夠在一定程度上保證在實(shí)現(xiàn)多播的理論容量的前提下形成包含較少的關(guān)鍵路徑，但是，當(dāng)關(guān)鍵鏈路成為瓶頸時(shí)，會使網(wǎng)絡(luò)延遲加大，甚至?xí)咕W(wǎng)絡(luò)的效率明顯下降。

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

2 上下文相關(guān)性網(wǎng)絡(luò)編碼方案

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

2.1 上下文相關(guān)性網(wǎng)絡(luò)編碼引入

在網(wǎng)絡(luò)編碼下的多播中，源節(jié)點(diǎn)對數(shù)據(jù)包的處理功能由傳統(tǒng)的分塊、存儲、轉(zhuǎn)發(fā)三個(gè)基本功能，變成分塊、編碼、存儲、轉(zhuǎn)發(fā)。保證了網(wǎng)絡(luò)中的數(shù)據(jù)包在傳輸?shù)倪^程中，不會因?yàn)槟膫€(gè)數(shù)據(jù)包的丟失而引起數(shù)據(jù)包無法正常接收。源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包始終是數(shù)據(jù)分塊的編碼后的數(shù)據(jù)包，因此，網(wǎng)絡(luò)傳輸過程中的安全性和可靠性也顯著提高。在目的節(jié)點(diǎn)處，根據(jù)收到的數(shù)據(jù)包中的一部分信息組成可逆矩陣，另一部分組成編碼包向量，通過這兩部分的運(yùn)算可以得到原數(shù)據(jù)包按順序分塊的數(shù)據(jù)包，從而得到原信息流。這種多播中的源節(jié)點(diǎn)、中間節(jié)點(diǎn)以及目的節(jié)點(diǎn)三者之間的編碼、解碼的過程完全具有上下文的相互聯(lián)系、互相影響的關(guān)系，因此，具有上下文相關(guān)性的特點(diǎn)。

2.2 上下文相關(guān)性網(wǎng)絡(luò)編碼下的源節(jié)點(diǎn)多播流

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

圖1 源節(jié)點(diǎn)數(shù)據(jù)流的劃分、編碼、轉(zhuǎn)發(fā)圖

圖2 源節(jié)點(diǎn)編碼后的信息系數(shù)形成的矩陣圖

2.3 上下文相關(guān)性網(wǎng)絡(luò)編碼下的多播中間節(jié)點(diǎn)

在多播網(wǎng)絡(luò)拓?fù)鋱D中，除了源節(jié)點(diǎn)和目的節(jié)點(diǎn)，其他節(jié)點(diǎn)稱為中間節(jié)點(diǎn)，在傳統(tǒng)的網(wǎng)絡(luò)中，中間節(jié)點(diǎn)都具有存儲和路由轉(zhuǎn)發(fā)能力。在網(wǎng)絡(luò)編碼多播網(wǎng)絡(luò)中，當(dāng)中間節(jié)點(diǎn)的入度大于1時(shí)，這個(gè)節(jié)點(diǎn)具有編碼能力，當(dāng)中間節(jié)點(diǎn)的入度等于1時(shí)，這個(gè)中間節(jié)點(diǎn)不需要具有編碼能力。圖3為具有網(wǎng)絡(luò)編碼能力的節(jié)點(diǎn)和不具有網(wǎng)絡(luò)編碼能力的節(jié)點(diǎn)比較。具有編碼能力的網(wǎng)絡(luò)節(jié)點(diǎn)采用最簡單的線性網(wǎng)絡(luò)編碼。在編解碼的過程中需要的時(shí)間最短，編碼算法簡單。

圖3 編碼節(jié)點(diǎn)和非編碼節(jié)點(diǎn)信息轉(zhuǎn)發(fā)圖

2.4 上下文相關(guān)性網(wǎng)絡(luò)編碼下的多播目的節(jié)點(diǎn)

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

2.5 上下文相關(guān)性網(wǎng)絡(luò)編碼下的多播網(wǎng)絡(luò)傳輸

基于網(wǎng)絡(luò)編碼下的多播網(wǎng)絡(luò)云圖如圖4所示。中間的網(wǎng)絡(luò)節(jié)點(diǎn)云中的拓?fù)浣Y(jié)構(gòu)可以已知也可以未知，在網(wǎng)絡(luò)傳輸?shù)倪^程中，只要能夠保證源節(jié)點(diǎn)發(fā)送信息成功和目的節(jié)點(diǎn)接收信息成功，就可以成功地解碼形成原始信息。如果中間的網(wǎng)絡(luò)節(jié)點(diǎn)云中有某個(gè)節(jié)點(diǎn)或者某個(gè)鏈路出現(xiàn)問題，這時(shí)候會由其他的鏈路再次發(fā)送網(wǎng)絡(luò)編碼數(shù)據(jù)信息，因?yàn)樾畔⒍际蔷幋a后形成的，因此，不需要分析哪個(gè)數(shù)據(jù)包丟失，只要在源節(jié)點(diǎn)再通過另外一條備份鏈路發(fā)送再次編碼后的信息，目的節(jié)點(diǎn)能夠接受到一定數(shù)量的數(shù)據(jù)包，就可以成功地還原出原始數(shù)據(jù)。

圖4 基于網(wǎng)絡(luò)編碼下的多播網(wǎng)絡(luò)云圖

3 基于上下文相關(guān)性網(wǎng)絡(luò)編碼下的多播網(wǎng)絡(luò)模型

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

圖5 網(wǎng)絡(luò)拓?fù)鋱D

圖6 網(wǎng)絡(luò)編碼后網(wǎng)絡(luò)流傳輸圖

3.1 每個(gè)節(jié)點(diǎn)編碼后的數(shù)據(jù)包

數(shù)據(jù)由上游的源點(diǎn)經(jīng)過中間節(jié)點(diǎn)編碼、存儲、轉(zhuǎn)發(fā)后形成的網(wǎng)絡(luò)編碼數(shù)據(jù)流，以及到達(dá)最終的目的節(jié)點(diǎn)所形成的數(shù)據(jù)包流的集合而成。

3.2 在目的節(jié)點(diǎn)t1和t2可以收到的信息流

目的節(jié)點(diǎn)t1收到的信息流的6種可能組合，分別 為 （M1 M12 M23）、（M1 M23 M12）、（M12 M1 M23）、（M12 M23 M1）、（M23 M1 M12）、（M23 M12 M1）。

目的節(jié)點(diǎn)t2收到的信息流的6種可能組合，分別 為 （M12 M23 M3）、（M12 M3 M23）、（M3 M12 M23）、（M3 M23 M12）、（M23 M12 M3）、（M23 M3 M12）。

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

3.3 目的節(jié)點(diǎn)解碼過程

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

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

4 上下文相關(guān)性網(wǎng)絡(luò)編碼多播復(fù)雜性分析

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

本文中的方案與傳統(tǒng)多項(xiàng)式復(fù)雜度的網(wǎng)絡(luò)編碼復(fù)雜度的比較圖如圖7所示。算法1線為本文中的基于上下文的網(wǎng)絡(luò)編碼方案中所體現(xiàn)的時(shí)間復(fù)雜度，算法2線為傳統(tǒng)的多項(xiàng)式復(fù)雜度網(wǎng)絡(luò)編碼算法所體現(xiàn)的時(shí)間復(fù)雜度。通過圖7可以看出，本文的方案隨著網(wǎng)絡(luò)節(jié)點(diǎn)的增多，其復(fù)雜度呈現(xiàn)緩慢增長的趨勢，而傳統(tǒng)的多項(xiàng)式復(fù)雜度網(wǎng)絡(luò)編碼算法其復(fù)雜度隨著網(wǎng)絡(luò)節(jié)點(diǎn)的增加呈現(xiàn)快速增長的趨勢。實(shí)驗(yàn)證明，隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的增加，該方案的優(yōu)勢更加突出。

圖7 算法1和算法2時(shí)間復(fù)雜度比較圖

5 結(jié)語

基于上下文多播網(wǎng)絡(luò)中的網(wǎng)絡(luò)編碼方案可用于解決在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)未知的情況下的無圈有向網(wǎng)絡(luò)的可靠多播問題。該方案的實(shí)現(xiàn)是通過在源節(jié)點(diǎn)處增加了編碼的功能，使得源節(jié)點(diǎn)由傳統(tǒng)的分塊、存儲、轉(zhuǎn)發(fā)三功能變?yōu)榉謮K、編碼、存儲、轉(zhuǎn)發(fā)四個(gè)功能。在中間的網(wǎng)絡(luò)節(jié)點(diǎn)和鏈路處，避免了傳統(tǒng)線性編碼由于計(jì)算節(jié)點(diǎn)的局部編碼矩陣和鏈路編碼向量所帶來的計(jì)算和存儲代價(jià)的增加。只要源節(jié)點(diǎn)能夠保證原信息分塊編碼后的向量所組成的系數(shù)矩陣是可逆矩陣，目的節(jié)點(diǎn)在接收到足夠多的信息塊后，就可以成功譯碼，還原原始的信息，并且不需要考慮信息的次序問題。這在一定程度上節(jié)省了時(shí)間和存儲資源，同時(shí)，由于信息都是編碼后的數(shù)據(jù)塊，所以也不會因?yàn)閭鬏斶^程中消息的丟失而產(chǎn)生牽連效應(yīng)，以至于目的節(jié)點(diǎn)不能及時(shí)成功譯碼，從而增大譯碼時(shí)延的問題。

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

［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］黃佳慶，程文青.信息論基礎(chǔ)［M］.北京：電子工業(yè)出版社，2010.

［4］黃佳慶，李宗鵬.網(wǎng)絡(luò)編碼原理［M］.北京：國防工業(yè)出版社，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，F(xiàn)ragouli 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，F(xiàn)reiling 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］劉宴濤，夏桂陽，等.一種基于子樹分解的組播線性網(wǎng)絡(luò)編碼算法［J］.計(jì)算機(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ìn)的最小代價(jià)網(wǎng)絡(luò)編碼算法［J］.華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），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

安徽省教育廳自然科學(xué)資助項(xiàng)目（KJ2016A609）;安徽高校人文社會科學(xué)研究重點(diǎn)項(xiàng)目（SK2017A0606）

周艷玲（1979-）,女，博士，合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系講師，研究方向：多播技術(shù)、網(wǎng)絡(luò)編碼等。