網絡編碼及其應用優勢分析

曹騫 程軍

（巢湖學院計算機與信息工程學院，安徽 巢湖 238000）

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

1 網絡編碼原理

在組播樹中我們可以利用Ford and Fulkerson標號法，通過尋找源節點和信宿節點之間的增廣鏈并進行調整，可以尋找到最大流。對于單信源多接收的網絡，第一個查找的信宿節點可以通過這種標記方法查找到與信源節點之間的最大流，但是從第二個信宿節點開始，在查找開始前需要把第一個信宿節點與信源節點之間用掉的容量從網絡中去除，因為傳統網絡中的節點只能夠對信息進行簡單的存儲和轉發，并不能夠對信息進行疊加處理和傳輸，所以用組播樹的方式構建的最大流方法，只有第一個信宿節與信源節點之間能夠以最大流進行傳輸，其他的信宿節點都不能夠達到最大流，最終實際的組播傳輸容量達不到理論上的最大流最小割定理確定的理論容量上限，所以我們希望網絡中的節點不僅僅能夠對信息進行存儲和轉發，如果中繼節點能夠對需要傳播的多條信息進行處理，將信息進行疊加之后進行傳輸，在不增加網絡流量的情況下擴充網絡傳輸的能力。圖1（a）是一個經典的“單信源二信宿”蝴蝶網絡，其中s是信源，t1,t2是信宿，w,u,v1,v2是中繼節點,a和b是信源s發出的信息，此圖中的最小割為2即組播的最大理論容量為2，信宿t1,t2能夠同時接收到信源s發出的2個單位的信息，但是傳統的路由傳輸方式中，圖中的w節點只能對收到的信息進行存儲和轉發，并不能對信息進行處理或者編碼，在一個時間段節點w只能轉發一種信息，所以與w相鄰的節點只能接收到一種信息，假定w轉發信息a，則鏈路（w，u），（u，t1）和（u，t2）中傳輸的信息都是 a，此時信宿t2接收到信息a，并且通過鏈路（v2，t2）接收到b，但是信宿t1只能接收到信息a，無法接收到信息b，在此圖中組播不能達到追到理論傳輸容量。圖1（b）中采用網絡編碼方式，對輸入的信息進行模二加運算，將結果a+b發送至節點w，此時鏈路（w，u），（u，t1）和（u，t2）中傳輸的信息都是a+b，信宿t1,t2都能夠接收到a+b，而且信宿t1通過鏈路（v1，t1）接收到信息 a，通過信息 a和信息a+b,能夠解出信息b，同理信宿t2也能夠收到信息a和b，采用網絡編碼的方式，提高了網絡組播信息的傳輸效率，當網絡編碼的域無限大，則運用網絡編碼的組播傳輸能夠達到理論上最大傳輸容量。

圖1 蝴蝶網絡

2 網絡編碼的優缺點

2.1 均衡網絡負載，提高帶寬利用率

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

圖2 單源三接收網絡

2.2 增強網絡安全

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

圖3 線性網絡編碼

2.3 減少無線網絡的能量消耗，提高數據安全

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

網絡編碼能夠在一定程度上提高無線網絡傳輸的安全性能。相比于傳統傳輸方法，在引入了數據編碼技術之后，無線網絡中傳輸的是疊加之后的數據而不是原始數據，數據的防竊聽能力加強了。即使有人試圖從采用了網絡編碼技術的網絡中竊聽數據，只要監聽者沒有竊聽到足夠多的數據或者沒有足夠強大的運算能力，就不能譯出信源傳輸的原始信息，雖然安全的級別不能夠達到利用數據加密或者哈希函數的方法運算的等級，但是低安全級別的數據傳輸中還是有很廣的應用前景。

3 目前存在的問題

進行網絡編碼需要網絡中的節點，需要具有運算和編碼的能力，傳統的節點設備可能不具備這些功能，而且網絡編碼涉及到大量的編碼運算，而且運算復雜度和編碼規則相關，在增加通信能力的同時也增加了網絡中節點計算的復雜性，在某些情況下還需要在編碼前進行信號的轉換，這些都可能造成網絡編碼對網絡帶來更高的計算成本，也提高網絡節點的制造成本，而且目前主要針對單信源多信宿的網絡情況進行網絡編碼研究，對于實際的網絡組播情況中多信源的多源網絡進行網絡編碼還是具有相當的難度。如果傳輸的信息進行了編碼，信宿節點接收到的某些信息并不能直接解碼，只有在接收到足夠的信源發出的信息后，才能夠解碼得到源信息，對網絡傳輸的同步提出了更高的要求。而且在有些網絡中并不是所有具有多輸入鏈路的節點都需要網絡編碼，如果對所有具有多條鏈路的節點都進行網絡編碼，同樣會產生冗余，因為網絡編碼的主題是輸出鏈路而不是節點。例如在圖4中，由于節點v3的存在使得在不用給節點w進行網絡編碼的情況下也可以讓信宿節點同時收到信源節點發送的信息a和b，所以在一些網絡拓撲結構上保證組播速率達到最大理論值的前提下，只在必須的網絡鏈路上使用網絡編碼技術，優化網絡編碼減少網絡中的開銷。

圖4 不需要編碼的網絡

網絡編碼是網絡通信研究中的重大突破，是下一代網絡的關鍵技術，有著很好的應用前景。目前對于網絡編碼的研究和驗證都基于理想化的模型，很多的網絡編碼技術需要在實際的網絡環境中進行檢驗。而且隨著網絡拓撲結構的增大，網絡編碼的速度就會變慢，對于資源的消耗變大，一些研究中已經引入遺傳算法對網絡編碼進行優化。網絡編碼和糾錯碼、數字簽名技術之間的聯系，非線性網絡編碼與安全網絡構建之間的聯系，這些都是以后網絡編碼研究新的方向。綜上所述，網絡編碼技術在未來網絡技術的發展中有著很重要的地位，網絡編碼技術會有更好的應用前景，對網絡的組播傳輸效率、網絡安全、數據糾錯都會帶來新的發展。

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

[2]黃佳慶.網絡編碼原理[M].北京：國防工業出版社，2012.