曹騫 程軍

（巢湖學(xué)院計(jì)算機(jī)與信息工程學(xué)院，安徽 巢湖 238000）

為了提高組播中傳輸效率，香港中文大學(xué)的R.Alshwede等人[1]提出并證明如果網(wǎng)絡(luò)節(jié)點(diǎn)不只是簡單的對傳輸?shù)男畔⑦M(jìn)行存儲和轉(zhuǎn)發(fā)，而且可以利用線性編碼方式對信息進(jìn)行處理，可以讓網(wǎng)絡(luò)組播實(shí)現(xiàn)理論上的最大傳輸流量，我們將這種方法稱為網(wǎng)絡(luò)編碼。網(wǎng)絡(luò)編碼方法可以按照網(wǎng)絡(luò)中節(jié)點(diǎn)對消息的處理方式分為線性和非線性兩種，也可以按照網(wǎng)絡(luò)編碼系數(shù)的生成方式劃分為隨機(jī)網(wǎng)絡(luò)編碼和確定型網(wǎng)絡(luò)編碼。目前網(wǎng)絡(luò)中有三種通訊模式：單播、廣播和組播，其中組播同時具有單播和廣播的優(yōu)點(diǎn)，組播是通過在發(fā)送者和每一接收者之間實(shí)現(xiàn)點(diǎn)對多點(diǎn)的網(wǎng)絡(luò)鏈接，加入到同一個組的主機(jī)可以接收到此組內(nèi)的所有數(shù)據(jù)，發(fā)送者同時給多個接受者傳輸?shù)臄?shù)據(jù)相同，只復(fù)制一份相同的數(shù)據(jù)包組播的數(shù)據(jù)傳送效率較高，能夠有效地減少網(wǎng)絡(luò)擁塞的出現(xiàn)。傳統(tǒng)的組播通過構(gòu)造多播樹實(shí)現(xiàn)，其構(gòu)造過程一般是NP完全問題。而且傳統(tǒng)網(wǎng)絡(luò)中的中繼節(jié)點(diǎn)只能對數(shù)據(jù)進(jìn)行存儲和轉(zhuǎn)發(fā)，不能夠?qū)?shù)據(jù)進(jìn)行編碼處理，在傳輸過程中不能通過編碼技術(shù)對信息進(jìn)行疊加，因此大多數(shù)算法都不能達(dá)到”最大流、最小割”定理確定的理論流量值[2]。下面我們通過一些例子簡單說明網(wǎng)絡(luò)編碼的原理極其特點(diǎn)：

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

在組播樹中我們可以利用Ford and Fulkerson標(biāo)號法，通過尋找源節(jié)點(diǎn)和信宿節(jié)點(diǎn)之間的增廣鏈并進(jìn)行調(diào)整，可以尋找到最大流。對于單信源多接收的網(wǎng)絡(luò)，第一個查找的信宿節(jié)點(diǎn)可以通過這種標(biāo)記方法查找到與信源節(jié)點(diǎn)之間的最大流，但是從第二個信宿節(jié)點(diǎn)開始，在查找開始前需要把第一個信宿節(jié)點(diǎn)與信源節(jié)點(diǎn)之間用掉的容量從網(wǎng)絡(luò)中去除，因?yàn)閭鹘y(tǒng)網(wǎng)絡(luò)中的節(jié)點(diǎn)只能夠?qū)π畔⑦M(jìn)行簡單的存儲和轉(zhuǎn)發(fā)，并不能夠?qū)π畔⑦M(jìn)行疊加處理和傳輸，所以用組播樹的方式構(gòu)建的最大流方法，只有第一個信宿節(jié)與信源節(jié)點(diǎn)之間能夠以最大流進(jìn)行傳輸，其他的信宿節(jié)點(diǎn)都不能夠達(dá)到最大流，最終實(shí)際的組播傳輸容量達(dá)不到理論上的最大流最小割定理確定的理論容量上限，所以我們希望網(wǎng)絡(luò)中的節(jié)點(diǎn)不僅僅能夠?qū)π畔⑦M(jìn)行存儲和轉(zhuǎn)發(fā)，如果中繼節(jié)點(diǎn)能夠?qū)π枰獋鞑サ亩鄺l信息進(jìn)行處理，將信息進(jìn)行疊加之后進(jìn)行傳輸，在不增加網(wǎng)絡(luò)流量的情況下擴(kuò)充網(wǎng)絡(luò)傳輸?shù)哪芰?。圖1（a）是一個經(jīng)典的“單信源二信宿”蝴蝶網(wǎng)絡(luò)，其中s是信源，t1,t2是信宿，w,u,v1,v2是中繼節(jié)點(diǎn),a和b是信源s發(fā)出的信息，此圖中的最小割為2即組播的最大理論容量為2，信宿t1,t2能夠同時接收到信源s發(fā)出的2個單位的信息，但是傳統(tǒng)的路由傳輸方式中，圖中的w節(jié)點(diǎn)只能對收到的信息進(jìn)行存儲和轉(zhuǎn)發(fā)，并不能對信息進(jìn)行處理或者編碼，在一個時間段節(jié)點(diǎn)w只能轉(zhuǎn)發(fā)一種信息，所以與w相鄰的節(jié)點(diǎn)只能接收到一種信息，假定w轉(zhuǎn)發(fā)信息a，則鏈路（w，u），（u，t1）和（u，t2）中傳輸?shù)男畔⒍际?a，此時信宿t2接收到信息a，并且通過鏈路（v2，t2）接收到b，但是信宿t1只能接收到信息a，無法接收到信息b，在此圖中組播不能達(dá)到追到理論傳輸容量。圖1（b）中采用網(wǎng)絡(luò)編碼方式，對輸入的信息進(jìn)行模二加運(yùn)算，將結(jié)果a+b發(fā)送至節(jié)點(diǎn)w，此時鏈路（w，u），（u，t1）和（u，t2）中傳輸?shù)男畔⒍际莂+b，信宿t1,t2都能夠接收到a+b，而且信宿t1通過鏈路（v1，t1）接收到信息 a，通過信息 a和信息a+b,能夠解出信息b，同理信宿t2也能夠收到信息a和b，采用網(wǎng)絡(luò)編碼的方式，提高了網(wǎng)絡(luò)組播信息的傳輸效率，當(dāng)網(wǎng)絡(luò)編碼的域無限大，則運(yùn)用網(wǎng)絡(luò)編碼的組播傳輸能夠達(dá)到理論上最大傳輸容量。

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

2 網(wǎng)絡(luò)編碼的優(yōu)缺點(diǎn)

2.1 均衡網(wǎng)絡(luò)負(fù)載，提高帶寬利用率

傳統(tǒng)的組播中，信息有可能過度集中在某些節(jié)點(diǎn)，或者造成某一鏈路的流量過大，使得網(wǎng)絡(luò)鏈路的負(fù)載不均衡，利用網(wǎng)絡(luò)編碼技術(shù)，能夠提高網(wǎng)絡(luò)的負(fù)載均衡，平均的使用網(wǎng)絡(luò)鏈路的容量，避免網(wǎng)絡(luò)擁塞，在節(jié)點(diǎn)平均讀書較大時，效果更加明顯。圖2（a）是一個單源三接收網(wǎng)絡(luò)，每條鏈路的容量為2，圖2（b）中表示的是利用基于多播樹的路由多播，圖中用到了5條鏈路，每條鏈路上的可行流為2，消耗總帶寬為5*2=10，在圖2（c）中采用網(wǎng)絡(luò)編碼進(jìn)行多播，為了平均鏈路流量的使用，盡量使用了網(wǎng)絡(luò)中的可能鏈路，本例中一共9條傳輸鏈路，相比傳統(tǒng)多播技術(shù)多使用了4條鏈路，每條鏈路的可行流為1，消耗的總帶寬為9*1=9，相比于傳統(tǒng)的多播方法，節(jié)省了10%的帶寬消耗，每條鏈路的平均流量下降到1，鏈路的使用更加合理，均衡了網(wǎng)絡(luò)負(fù)載，提高了帶寬利用率。

圖2 單源三接收網(wǎng)絡(luò)

2.2 增強(qiáng)網(wǎng)絡(luò)安全

利用網(wǎng)絡(luò)編碼進(jìn)行數(shù)據(jù)傳輸在一定程度上可以提高數(shù)據(jù)的安全性，在傳統(tǒng)的網(wǎng)絡(luò)傳輸中，數(shù)據(jù)有可能被竊聽，受到被動攻擊，例如在圖3（a）表示的結(jié)構(gòu)中，竊聽者可以竊聽網(wǎng)絡(luò)中的任意一條信道，獲取傳輸內(nèi)容。圖3（b）中我們利用網(wǎng)絡(luò)編碼方式進(jìn)行組播，信源不再直接發(fā)送a和b而是發(fā)送a+b和a+2b對消息進(jìn)行混合，在單獨(dú)的每一條路徑上都不會出現(xiàn)原始的信源消息a或者b，此時竊聽者在竊聽網(wǎng)絡(luò)中的任一信道（假設(shè)竊聽者只能竊聽一個信道）獲得的傳輸數(shù)據(jù)是難以破一出信源消息a和b的，信宿只有在接收到足夠多的消息后，從中譯出信源消息。而且在網(wǎng)絡(luò)編碼技術(shù)中可以引入數(shù)據(jù)加密技術(shù)，對部分消息數(shù)據(jù)進(jìn)行加密，并且將加密后的消息數(shù)據(jù)和未加密的消息數(shù)據(jù)充分混合，此時只要竊聽者竊聽的信道數(shù)量小于信源消息的總數(shù)，竊聽者就很難破譯出信源消息，信宿接收到足夠的消息數(shù)據(jù)時，同時得到加密的消息數(shù)據(jù)和未加密的消息數(shù)據(jù)，可以直接譯出未加密的信源消息，并且可以譯出加密的信源消息，利用解密算法對其解密，得到信源要傳遞的全部消息。通過數(shù)據(jù)編碼的方法在沒有增加網(wǎng)絡(luò)容量的情況下提高了數(shù)據(jù)傳輸?shù)陌踩?。圖3（c）中采用這種技術(shù)，將信源要傳遞的消息b經(jīng)過數(shù)據(jù)加密技術(shù)轉(zhuǎn)換層密文k，此時竊聽者在單一信道上不能竊聽到信源消息a，只能竊聽到消息k，但是無法破解密文k，在信宿節(jié)點(diǎn)通過足夠多的消息可以譯出消息a和k，再采用解密技術(shù)將k解密成明文b，這種方法提高了網(wǎng)絡(luò)的安全性，而且沒有網(wǎng)絡(luò)鏈路的開銷，但是這種技術(shù)增加了加密和解密的計(jì)算量，在實(shí)際的使用過程，對消息全部加密成本太高，所以可以選擇對發(fā)送的消息進(jìn)行部分加密，附加在發(fā)送的消息后面，減少加密和解密運(yùn)算的成本。

圖3 線性網(wǎng)絡(luò)編碼

2.3 減少無線網(wǎng)絡(luò)的能量消耗，提高數(shù)據(jù)安全

在無線網(wǎng)絡(luò)中通過對傳輸?shù)男畔⑦M(jìn)行編碼，將信息疊加之后進(jìn)行傳輸，這樣傳輸單位信息所需要的發(fā)射功率就會減少，無線網(wǎng)絡(luò)的能量消耗會下降。無線網(wǎng)絡(luò)很多節(jié)點(diǎn)都是依靠電池供電，功率的降低能夠延長無線設(shè)備的續(xù)航時間。無線網(wǎng)絡(luò)中還可以采用網(wǎng)絡(luò)編碼的方法增強(qiáng)網(wǎng)絡(luò)的安全性，在無線網(wǎng)絡(luò)中數(shù)據(jù)的傳輸容易被竊聽和攻擊，在安全級別要求較高時我們可以結(jié)合密碼學(xué)對數(shù)據(jù)進(jìn)行加密處理再進(jìn)行傳輸。數(shù)據(jù)加密技術(shù)計(jì)算復(fù)雜度較大，帶來的數(shù)據(jù)冗余也較多，從而影響數(shù)據(jù)的傳輸效率，并且數(shù)據(jù)在解碼的時候?qū)邮展?jié)點(diǎn)的計(jì)算能力和存儲能力也有較高的要求，整個的傳輸成本比較高，不適合普通信息和數(shù)據(jù)的傳輸中使用。

網(wǎng)絡(luò)編碼能夠在一定程度上提高無線網(wǎng)絡(luò)傳輸?shù)陌踩阅?。相比于傳統(tǒng)傳輸方法，在引入了數(shù)據(jù)編碼技術(shù)之后，無線網(wǎng)絡(luò)中傳輸?shù)氖钳B加之后的數(shù)據(jù)而不是原始數(shù)據(jù)，數(shù)據(jù)的防竊聽能力加強(qiáng)了。即使有人試圖從采用了網(wǎng)絡(luò)編碼技術(shù)的網(wǎng)絡(luò)中竊聽數(shù)據(jù)，只要監(jiān)聽者沒有竊聽到足夠多的數(shù)據(jù)或者沒有足夠強(qiáng)大的運(yùn)算能力，就不能譯出信源傳輸?shù)脑夹畔ⅲm然安全的級別不能夠達(dá)到利用數(shù)據(jù)加密或者哈希函數(shù)的方法運(yùn)算的等級，但是低安全級別的數(shù)據(jù)傳輸中還是有很廣的應(yīng)用前景。

3 目前存在的問題

進(jìn)行網(wǎng)絡(luò)編碼需要網(wǎng)絡(luò)中的節(jié)點(diǎn)，需要具有運(yùn)算和編碼的能力，傳統(tǒng)的節(jié)點(diǎn)設(shè)備可能不具備這些功能，而且網(wǎng)絡(luò)編碼涉及到大量的編碼運(yùn)算，而且運(yùn)算復(fù)雜度和編碼規(guī)則相關(guān)，在增加通信能力的同時也增加了網(wǎng)絡(luò)中節(jié)點(diǎn)計(jì)算的復(fù)雜性，在某些情況下還需要在編碼前進(jìn)行信號的轉(zhuǎn)換，這些都可能造成網(wǎng)絡(luò)編碼對網(wǎng)絡(luò)帶來更高的計(jì)算成本，也提高網(wǎng)絡(luò)節(jié)點(diǎn)的制造成本，而且目前主要針對單信源多信宿的網(wǎng)絡(luò)情況進(jìn)行網(wǎng)絡(luò)編碼研究，對于實(shí)際的網(wǎng)絡(luò)組播情況中多信源的多源網(wǎng)絡(luò)進(jìn)行網(wǎng)絡(luò)編碼還是具有相當(dāng)?shù)碾y度。如果傳輸?shù)男畔⑦M(jìn)行了編碼，信宿節(jié)點(diǎn)接收到的某些信息并不能直接解碼，只有在接收到足夠的信源發(fā)出的信息后，才能夠解碼得到源信息，對網(wǎng)絡(luò)傳輸?shù)耐教岢隽烁叩囊?。而且在有些網(wǎng)絡(luò)中并不是所有具有多輸入鏈路的節(jié)點(diǎn)都需要網(wǎng)絡(luò)編碼，如果對所有具有多條鏈路的節(jié)點(diǎn)都進(jìn)行網(wǎng)絡(luò)編碼，同樣會產(chǎn)生冗余，因?yàn)榫W(wǎng)絡(luò)編碼的主題是輸出鏈路而不是節(jié)點(diǎn)。例如在圖4中，由于節(jié)點(diǎn)v3的存在使得在不用給節(jié)點(diǎn)w進(jìn)行網(wǎng)絡(luò)編碼的情況下也可以讓信宿節(jié)點(diǎn)同時收到信源節(jié)點(diǎn)發(fā)送的信息a和b，所以在一些網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)上保證組播速率達(dá)到最大理論值的前提下，只在必須的網(wǎng)絡(luò)鏈路上使用網(wǎng)絡(luò)編碼技術(shù)，優(yōu)化網(wǎng)絡(luò)編碼減少網(wǎng)絡(luò)中的開銷。

圖4 不需要編碼的網(wǎng)絡(luò)

網(wǎng)絡(luò)編碼是網(wǎng)絡(luò)通信研究中的重大突破，是下一代網(wǎng)絡(luò)的關(guān)鍵技術(shù)，有著很好的應(yīng)用前景。目前對于網(wǎng)絡(luò)編碼的研究和驗(yàn)證都基于理想化的模型，很多的網(wǎng)絡(luò)編碼技術(shù)需要在實(shí)際的網(wǎng)絡(luò)環(huán)境中進(jìn)行檢驗(yàn)。而且隨著網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的增大，網(wǎng)絡(luò)編碼的速度就會變慢，對于資源的消耗變大，一些研究中已經(jīng)引入遺傳算法對網(wǎng)絡(luò)編碼進(jìn)行優(yōu)化。網(wǎng)絡(luò)編碼和糾錯碼、數(shù)字簽名技術(shù)之間的聯(lián)系，非線性網(wǎng)絡(luò)編碼與安全網(wǎng)絡(luò)構(gòu)建之間的聯(lián)系，這些都是以后網(wǎng)絡(luò)編碼研究新的方向。綜上所述，網(wǎng)絡(luò)編碼技術(shù)在未來網(wǎng)絡(luò)技術(shù)的發(fā)展中有著很重要的地位，網(wǎng)絡(luò)編碼技術(shù)會有更好的應(yīng)用前景，對網(wǎng)絡(luò)的組播傳輸效率、網(wǎng)絡(luò)安全、數(shù)據(jù)糾錯都會帶來新的發(fā)展。

[1]AHLSWEDER,CAIN,LISY-R.etal Network information flow[J].IEEE Transactions on Information Theory,2000，（4）：1204-1206.

[2]黃佳慶.網(wǎng)絡(luò)編碼原理[M].北京：國防工業(yè)出版社，2012.