隨機線性網(wǎng)絡(luò)編碼問題及其應(yīng)用研究.pdf

1、網(wǎng)絡(luò)編碼技術(shù)是近些年來提出的可達到最大傳輸速率的一種新興技術(shù)。不同于傳統(tǒng)路由技術(shù)，即存儲轉(zhuǎn)發(fā)模式，網(wǎng)絡(luò)編碼允許中間節(jié)點對其收到的信息進行線性或者非線性的編碼操作后轉(zhuǎn)發(fā)給下一個節(jié)點。相比于傳統(tǒng)的路由方法，網(wǎng)絡(luò)編碼被證明了具有提高吞吐量、降低傳輸延遲、減少傳輸能耗、增加系統(tǒng)魯棒性等優(yōu)點，并應(yīng)用到了多個領(lǐng)域中。
　　特別地，由于操作簡單和編、譯碼復(fù)雜度低，隨機網(wǎng)絡(luò)編碼被廣泛應(yīng)用到實際網(wǎng)絡(luò)中。隨機網(wǎng)絡(luò)編碼允許網(wǎng)絡(luò)的中間節(jié)點對接收到的信息進

2、行線性組合操作，其中組合系數(shù)是在一個有限域內(nèi)隨機選擇的一個元素。研究顯示隨著有限域基數(shù)趨于無窮，這種方法的成功率就可以趨于1。這種隨機選取系數(shù)的方法帶來的缺點有兩個。一個是需增大編碼操作中所需編碼域的大小，另一個是保證特定的概率實現(xiàn)正確的傳輸。網(wǎng)絡(luò)節(jié)點頻繁的從編碼域中選取編碼系數(shù)進行編、譯碼操作。如果編碼域選取的過小，那么信宿節(jié)點的成功譯碼概率過低。這將不利于實際操作的應(yīng)用。如果編碼域選取的過大，那么編、譯碼的復(fù)雜性過大。這將造成不必要

3、的能源損耗和時間浪費。顯而易見，在保證固定成功譯碼概率的同時，減小所需編碼域基數(shù)是一個很有意義的研究課題。本文圍繞這個問題展開討論，所取得的主要成果包括以下三個方面。
　　第一部分研究基于線性代數(shù)、魯棒網(wǎng)絡(luò)流和隨機化給出一個魯棒性的多項式時間的隨機線性網(wǎng)絡(luò)編碼的構(gòu)造方法，全文中簡稱算法RPR。建立了基于有丟包的單源多播網(wǎng)絡(luò)的一般模型，并在此模型上給出了算法的構(gòu)造方法和具體步驟。隨后給出了算法的性能分析，包括成功譯碼概率和時間復(fù)雜度

4、等。最后給出了算法的理論增益，通過在大規(guī)模網(wǎng)路上的理論分析給出算法在減少編碼邊數(shù)上的優(yōu)勢，并且通過兩個特定網(wǎng)絡(luò)（即蝴蝶網(wǎng)絡(luò)和組合網(wǎng)絡(luò)）給出算法在減少編碼域基數(shù)上的貢獻。
　　通過算法RPR的構(gòu)造，得出一個網(wǎng)絡(luò)編碼存在的問題等價于排列從信源到信宿的信息流的組合問題。網(wǎng)絡(luò)編碼之所以優(yōu)于存儲轉(zhuǎn)發(fā)的路由協(xié)議可以達到最大傳輸速率，其本質(zhì)就是在忙碌邊上進行編碼操作。如果網(wǎng)絡(luò)中沒有忙碌邊，則網(wǎng)絡(luò)必定存在路由解保障最大速率的可達性。如果網(wǎng)絡(luò)是最小

5、多播網(wǎng)絡(luò)，算法中給出的編碼邊的個數(shù)是最少的。
　　第二部分研究一類組合網(wǎng)絡(luò)的成功譯碼概率問題。組合是構(gòu)造網(wǎng)絡(luò)的一種基本方法，且組合網(wǎng)絡(luò)應(yīng)用在各個領(lǐng)域，例如，用組合網(wǎng)絡(luò)構(gòu)造分組密碼，用組合網(wǎng)絡(luò)分析城市道路網(wǎng)等。針對在組合網(wǎng)絡(luò)拓?fù)渲醒芯苛穗S機線性網(wǎng)絡(luò)編碼的成功譯碼概率問題，當(dāng)網(wǎng)絡(luò)模型中不發(fā)生丟包時，給出一個信宿節(jié)點和所有信宿節(jié)點都成功譯碼的閉式解。根據(jù)這些閉式解，在固定的成功譯碼概率下，可以選取基數(shù)最小的編碼域。通過這些表達式，還分析

6、了主要參數(shù)，即編碼選取的有限域的基數(shù)、信宿節(jié)點的個數(shù)和網(wǎng)絡(luò)中繼節(jié)點的個數(shù)對譯碼性能的影響。當(dāng)網(wǎng)絡(luò)模型中發(fā)生丟包時，給出一個信宿節(jié)點和所有信宿節(jié)點都成功譯碼的下界。
　　第三部分研究基于樹型網(wǎng)絡(luò)的隨機線性網(wǎng)絡(luò)編碼的成功譯碼概率問題。在應(yīng)急領(lǐng)域，網(wǎng)絡(luò)常用于環(huán)境監(jiān)測，災(zāi)難信息獲取等。因此針對災(zāi)難環(huán)境的真實需求，在這種情況下，分層結(jié)構(gòu)是一種很方便的分布式管理。從網(wǎng)絡(luò)拓?fù)渖峡矗謱咏Y(jié)構(gòu)可以簡化成樹型網(wǎng)絡(luò)。此外，增加網(wǎng)絡(luò)深度就可以擴大網(wǎng)絡(luò)的覆