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

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

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

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

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

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

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