網(wǎng)絡(luò)編碼淺析

山東省招遠市阜山鎮(zhèn)廣播電視站 李寶杰

一、什么是網(wǎng)絡(luò)編碼

網(wǎng)絡(luò)編碼，是網(wǎng)絡(luò)中的節(jié)點將接收到的信息進行編碼后再轉(zhuǎn)發(fā)出去的多點傳送技術(shù)，是一種融合了路由和編碼的信息交換技術(shù)，它的核心思想是在網(wǎng)絡(luò)中的各個節(jié)點上對各條信道上收到的信息進行線性或者非線性的處理，然后轉(zhuǎn)發(fā)給下游節(jié)點，中間節(jié)點扮演著編碼器或信號處理器的角色。根據(jù)圖論中的最大流-最小割定理，數(shù)據(jù)的發(fā)送方和接收方通信的最大速率不能超過雙方之間的最大流值(或最小割值)，如果采用傳統(tǒng)多播路由的方法，一般不能達到該上界。R Ahlswede等人以蝴蝶網(wǎng)絡(luò)的研究為例，指出通過網(wǎng)絡(luò)編碼，可以達到多播路由傳輸?shù)淖畲罅鹘?，提高了信息的傳輸效率，從而奠定了網(wǎng)絡(luò)編碼在現(xiàn)代網(wǎng)絡(luò)通信研究領(lǐng)域的重要地位。

二、網(wǎng)絡(luò)編碼方案

網(wǎng)絡(luò)編碼方案可分為線性和非線性兩種，其中線性方法的編碼和解碼都相對簡單，因此，一般都傾向于采用線性方法。Li指出在有向網(wǎng)絡(luò)中，如果一個網(wǎng)絡(luò)編碼問題有解，則一定有線性解。從理論上保證了線性算法的有效性。線性組合要求網(wǎng)絡(luò)節(jié)點具有更高的計算能力，然而根據(jù)摩爾定律，隨著處理成本的降低，網(wǎng)絡(luò)的“瓶頸”逐漸轉(zhuǎn)向業(yè)務(wù)所需的更高的帶寬支持和服務(wù)質(zhì)量(QoS)保證。網(wǎng)絡(luò)編碼實際上是用節(jié)點處理能力換取更高的網(wǎng)絡(luò)效率。

（一）編碼過程

線性網(wǎng)絡(luò)編碼是將節(jié)點傳送信息線性映射到一個有限域內(nèi)，利用線性關(guān)系實現(xiàn)編譯碼過程。假設(shè)每個信息數(shù)據(jù)包為L比特，當(dāng)它與要組合的數(shù)據(jù)包長度不同較短的信息附加額外一串“0”，將包中的s個連續(xù)比特組成域上的一個符號，則一個包中包含L/s個符號。在線性編碼下，運用乘法和加法運算，使從節(jié)點發(fā)出去的數(shù)據(jù)為該節(jié)點接受到信息的線性組合。假設(shè)一個源或多個源產(chǎn)生的原始數(shù)據(jù)包含信息為M1.......Mn，則在線性網(wǎng)絡(luò)編碼中傳輸?shù)臄?shù)據(jù)可表示為線性網(wǎng)絡(luò)編碼是將節(jié)點傳送信息線性映射到一個有限域內(nèi)，利用線性關(guān)系實現(xiàn)編譯碼過程。假設(shè)每個信息數(shù)據(jù)包為L比特，當(dāng)它與要組合的數(shù)據(jù)包長度不同時，較短的信息附加額外一串“0”，將包中的s個連續(xù)比特組成域上的一個符號，則一個包中包含L/s個符號。在線性編碼下，運用乘法和加法運算，使從節(jié)點發(fā)出去的數(shù)據(jù)為該節(jié)點接收到信息的線性組合。

（二）解碼過程

解碼需要求解一組線性方程。實際中，可以應(yīng)用高斯消去的方法：節(jié)點存貯編碼向量以及編碼之后的結(jié)果，以行向量的形式，存儲在所謂解碼矩陣中。最初，解碼矩陣中只包含未經(jīng)該節(jié)點編碼的包以及與之相對應(yīng)的編碼向量(如果有的話)，否則為空。當(dāng)接收到一個已編碼包后，會從中抽取它的編碼向量以及編碼結(jié)果，放入到解碼矩陣中。解碼矩陣會經(jīng)過等價變換變成行階梯型，最終變成行最簡型。所收到的某一個包如果可以增加矩陣的秩，則稱之為更新包，如果所收到的包是非更新的，它可以通過等價變換變?yōu)槿?，從而可以忽略。?dāng)解碼矩陣變換成最簡型后，方程組得解。這種情況發(fā)生在當(dāng)接收到n個線性獨立的編碼向量之后。

三、總結(jié)

網(wǎng)絡(luò)編碼(Network Coding)是進入21世紀后通信領(lǐng)域的一項重大突破，它融合了編碼和路由的概念，通過允許對來自不同鏈路的信息進行編碼組合，使得網(wǎng)絡(luò)節(jié)點既實現(xiàn)路由功能又實現(xiàn)編碼功能.網(wǎng)絡(luò)編碼的應(yīng)用可以改善網(wǎng)絡(luò)性能，甚至可以改變網(wǎng)絡(luò)結(jié)構(gòu)、改變網(wǎng)絡(luò)協(xié)議設(shè)計方法，可以說網(wǎng)絡(luò)編碼正在給現(xiàn)有的網(wǎng)絡(luò)帶來革命性的變化。

[1]無線網(wǎng)絡(luò)編碼綜述[D].復(fù)旦大學(xué)計算機科學(xué)技術(shù)學(xué)院.

[2]網(wǎng)絡(luò)編碼中的優(yōu)化問題研究[D].華中科技大學(xué)電子與信息工程系.

[3]無線自組織網(wǎng)絡(luò)的編碼技術(shù)[D].北京郵電大學(xué)電信工程學(xué)院.