面向數(shù)據(jù)分發(fā)的網(wǎng)絡(luò)編碼研究.pdf

1、大規(guī)模的數(shù)據(jù)分發(fā)有著廣泛的應(yīng)用背景。在現(xiàn)有網(wǎng)絡(luò)條件下，如何更有效利用網(wǎng)絡(luò)資源并實現(xiàn)高質(zhì)量的數(shù)據(jù)分發(fā)，已成為網(wǎng)絡(luò)信息流研究領(lǐng)域的重要課題之一。近些年來提出的網(wǎng)絡(luò)編碼為實現(xiàn)這一目標(biāo)提供了新的解決方案。網(wǎng)絡(luò)編碼的核心思想是允許通信網(wǎng)絡(luò)中的節(jié)點對傳輸?shù)男畔⑦M行處理和操作（如有限域中的運算等），而不再限于存儲和轉(zhuǎn)發(fā)。網(wǎng)絡(luò)編碼革命性地拓展了現(xiàn)有的基于存儲和轉(zhuǎn)發(fā)的數(shù)據(jù)分發(fā)模式，被認(rèn)為是進入21 世紀(jì)后信息處理和信息傳輸理論研究領(lǐng)域上的重大突破，具有重

2、要的理論價值和廣泛的應(yīng)用前景。國內(nèi)外許多知名大學(xué)、科研機構(gòu)和公司等都積極投入對網(wǎng)絡(luò)編碼的研究，并取得了一些重要的研究成果。 已經(jīng)證明，網(wǎng)絡(luò)編碼能顯著改善數(shù)據(jù)分發(fā)系統(tǒng)的性能，如提升網(wǎng)絡(luò)吞吐量，節(jié)約傳輸帶寬和均衡網(wǎng)絡(luò)負(fù)載等。然而，與基于存儲和轉(zhuǎn)發(fā)操作的路由傳輸機制相比，網(wǎng)絡(luò)編碼系統(tǒng)中的節(jié)點需要執(zhí)行頻繁的編碼和譯碼操作，這必將消耗額外的計算資源（如I/O和CPU等），從而增加了在實際網(wǎng)絡(luò)中部署和實施網(wǎng)絡(luò)編碼的成本和代價。 因此

3、，對面向數(shù)據(jù)分發(fā)的網(wǎng)絡(luò)編碼傳輸過程進行優(yōu)化，減少網(wǎng)絡(luò)編碼操作所需的額外計算消耗，以此來實現(xiàn)低代價網(wǎng)絡(luò)編碼數(shù)據(jù)分發(fā)，對進一步提升數(shù)據(jù)分發(fā)系統(tǒng)的性能并促進網(wǎng)絡(luò)編碼的大規(guī)模應(yīng)用有重要的指導(dǎo)意義。 本文以降低網(wǎng)絡(luò)編碼操作所需的額外計算消耗為出發(fā)點，研究能實現(xiàn)更高效的基于網(wǎng)絡(luò)編碼的數(shù)據(jù)分發(fā)模式。研究主要從以下幾個方面展開：（1）基于信息流向量的網(wǎng)絡(luò)編碼傳輸模型的研究；（2）基于關(guān)鍵鏈路的低代價網(wǎng)絡(luò)編碼實現(xiàn)算法的研究；（3） 基于分

4、簇網(wǎng)絡(luò)編碼的傳輸策略與相關(guān)算法的研究。本文的研究工作得到了國家自然科學(xué)基金“無線Mesh 網(wǎng)絡(luò)流媒體分發(fā)研究”（No. 60773193），華為公司高科技基金“面向P2P的網(wǎng)絡(luò)編碼研究”（No. HW200606301254），湖北省智能互聯(lián)網(wǎng)技術(shù)重點實驗室開放基金（No. HSIT-200605）和華中科技大學(xué)電信系基礎(chǔ)理論研究基金（2008）的資助。 本文的研究成果包含以下幾個方面： 1）基于信息流向量的網(wǎng)絡(luò)編碼傳輸

5、模型：將數(shù)據(jù)分發(fā)系統(tǒng)中傳輸?shù)男畔⒔榫W(wǎng)絡(luò)信息流，提出了一種具有線性復(fù)雜性的描述網(wǎng)絡(luò)信息流的方法：信息流向量。結(jié)合信息流向量，分析了網(wǎng)絡(luò)編碼系統(tǒng)中存在的信息流向量約束，提出了反映網(wǎng)絡(luò)編碼操作數(shù)的指標(biāo)：代價函數(shù)，并構(gòu)建了最小代價的網(wǎng)絡(luò)編碼傳輸模型。該模型將網(wǎng)絡(luò)編碼數(shù)據(jù)分發(fā)系統(tǒng)的優(yōu)化問題轉(zhuǎn)化為數(shù)學(xué)規(guī)劃問題，因此能夠利用數(shù)學(xué)規(guī)劃的相關(guān)理論求解并確定出最小代價的網(wǎng)絡(luò)編碼數(shù)據(jù)分發(fā)模式。此外，為考慮一些特殊網(wǎng)絡(luò)中網(wǎng)絡(luò)編碼操作執(zhí)行效率的問題，提出了一

6、種基于效用折中的網(wǎng)絡(luò)編碼傳輸模型。該模型對在實際網(wǎng)絡(luò)中，構(gòu)建具有最小代價的，基于網(wǎng)絡(luò)編碼的數(shù)據(jù)分發(fā)系統(tǒng)具有重要的理論指導(dǎo)意義。 2）低代價網(wǎng)絡(luò)編碼實現(xiàn)算法的研究：通過分析網(wǎng)絡(luò)編碼的本質(zhì)特性，將網(wǎng)絡(luò)編碼區(qū)分于傳統(tǒng)的基于存儲和轉(zhuǎn)發(fā)的數(shù)據(jù)分發(fā)模式并顯著提升數(shù)據(jù)分發(fā)系統(tǒng)性能的根本原因歸結(jié)為構(gòu)建的傳輸路徑上存在“關(guān)鍵”鏈路。為實現(xiàn)給定網(wǎng)絡(luò)中數(shù)據(jù)分發(fā)系統(tǒng)的理論吞吐量，關(guān)鍵鏈路必須傳輸編碼信息。編碼信息能夠在信宿節(jié)點通過合適的譯碼操作加以“區(qū)

7、分”。因此，在構(gòu)建網(wǎng)絡(luò)編碼數(shù)據(jù)分發(fā)系統(tǒng)的傳輸路徑時，如果能夠保證形成較少的關(guān)鍵鏈路，就能在一定程度上減少系統(tǒng)中網(wǎng)絡(luò)編碼操作的執(zhí)行次數(shù)，從而降低網(wǎng)絡(luò)編碼所需的額外計算消耗，進而降低網(wǎng)絡(luò)編碼的實施成本和代價，并構(gòu)建低代價的基于網(wǎng)絡(luò)編碼的數(shù)據(jù)分發(fā)模式?；谠撍枷耄岢隽艘环N基于關(guān)鍵鏈路的低代價網(wǎng)絡(luò)編碼實現(xiàn)算法，并對該算法進行了分布式實現(xiàn)。 3）基于分簇網(wǎng)絡(luò)編碼的傳輸策略與相關(guān)算法研究。雖然網(wǎng)絡(luò)編碼源于IP組播，并被證明能提升組播網(wǎng)絡(luò)中

8、的數(shù)據(jù)分發(fā)性能，但由于技術(shù)和非技術(shù)上的挑戰(zhàn)，IP組播并沒有在現(xiàn)有互聯(lián)網(wǎng)上得到大規(guī)模的部署和應(yīng)用。作為一種替代的解決方案，基于對等網(wǎng)的協(xié)作式數(shù)據(jù)分發(fā)模型及其系統(tǒng)近年來得到了長足的發(fā)展，并被廣泛應(yīng)用。網(wǎng)絡(luò)編碼與基于對等網(wǎng)的協(xié)作式數(shù)據(jù)分發(fā)模型相結(jié)合，是網(wǎng)絡(luò)編碼應(yīng)用研究領(lǐng)域的熱點。然而，由于網(wǎng)絡(luò)編碼固有的特點，即節(jié)點需要執(zhí)行編碼和譯碼操作，一些學(xué)者對網(wǎng)絡(luò)編碼究竟能在多大程度上提升協(xié)作式數(shù)據(jù)分發(fā)系統(tǒng)的性能表示懷疑。以此為研究背景，以降低節(jié)點執(zhí)行編