畢業(yè)設(shè)計(jì)---基于網(wǎng)絡(luò)編碼的無(wú)線廣播重傳方案的研究

1、<p>　　xxxx畢業(yè)設(shè)計(jì)（論文）任務(wù)書</p><p>　　學(xué)院： 系級(jí)教學(xué)單位： </p><p>　本科畢業(yè)設(shè)計(jì)（論文）</p><p><b>　　摘要</b></p><p>　　在無(wú)線網(wǎng)絡(luò)廣播的重傳處理中，多個(gè)接收節(jié)點(diǎn)中的任意一個(gè)節(jié)點(diǎn)丟失

2、信息包都要求源節(jié)點(diǎn)重傳數(shù)據(jù)包，這就需要源節(jié)點(diǎn)廣播發(fā)送較多的重傳數(shù)。本文將隨機(jī)線性網(wǎng)絡(luò)編碼技術(shù)應(yīng)用在無(wú)線網(wǎng)絡(luò)廣播重傳中，設(shè)計(jì)了一種基于隨機(jī)線性網(wǎng)絡(luò)編碼的無(wú)線廣播重傳方案。在該方案中，源節(jié)點(diǎn)需記錄多個(gè)接收節(jié)點(diǎn)中丟失信息包的數(shù)量最多的接收節(jié)點(diǎn)的丟包數(shù)量，再按照隨機(jī)線性網(wǎng)絡(luò)編碼的方法編碼組合該丟包數(shù)量個(gè)線性編碼信息包；源節(jié)點(diǎn)廣播重傳線性編碼組合包；接收節(jié)點(diǎn)采用運(yùn)算編碼線性組合的方法獲得信息包數(shù)據(jù)。數(shù)學(xué)分析表明，該方法能保證所有接收節(jié)點(diǎn)的編碼可解

3、性，同時(shí)重傳次數(shù)可達(dá)到理論最優(yōu)性；模擬測(cè)試結(jié)果表明：與傳統(tǒng)重傳方法相比，應(yīng)用隨機(jī)線性網(wǎng)絡(luò)編碼的重傳方案有效地減少了信息包的平均傳輸次數(shù)，提高了傳輸效率．</p><p>　　關(guān)鍵詞　無(wú)線網(wǎng)絡(luò)廣播；網(wǎng)絡(luò)編碼；隨機(jī)線性網(wǎng)絡(luò)編碼；重傳</p><p><b>　　Abstract</b></p><p><b>　　Keywords　<

4、;/b></p><p>　　Abstract正文選用字體：Times New Roman，小四號(hào)字，行距20磅。</p><p>　?。ù硕挝淖珠喓髣h除）</p><p><b>　　目 錄</b></p><p><b>　　摘要I</b></p><p>　　A

5、bstractII</p><p><b>　　第1章 緒論1</b></p><p>　　1.1 課題背景及意義1</p><p>　　1.2 本課題國(guó)內(nèi)外的研究現(xiàn)狀2</p><p>　　1.3 本課題研究的主要內(nèi)容4</p><p>　　1.4 本文的章節(jié)安排4</p>

6、;<p>　　第2章 基于網(wǎng)絡(luò)編碼的無(wú)線傳輸?shù)姆治?</p><p>　　2.1 網(wǎng)絡(luò)編碼的概念與定義6</p><p>　　2.1.1 網(wǎng)絡(luò)編碼的基本原理6</p><p>　　2.1.2 最大流-最小割定理8</p><p>　　2.2 幾種常見(jiàn)的網(wǎng)絡(luò)編碼構(gòu)造方法11</p><p>　　2

7、.2.1 網(wǎng)絡(luò)編碼的前提假設(shè)11</p><p>　　2.2.2 線性向量編碼12</p><p>　　2.2.3 線性代數(shù)編碼14</p><p>　　2.2.4 隨機(jī)網(wǎng)絡(luò)編碼17</p><p>　　2.3 本章小結(jié)19</p><p>　　第3章 基于隨機(jī)網(wǎng)絡(luò)編碼的無(wú)線廣播重傳方案的設(shè)計(jì)20</

8、p><p>　　3.1 隨機(jī)網(wǎng)絡(luò)編碼的實(shí)現(xiàn)20</p><p>　　3.2 無(wú)線廣播重傳模型的建立21</p><p>　　3.3 隨機(jī)線性網(wǎng)絡(luò)編碼包的構(gòu)造22</p><p>　　3.4 編碼可解性的證明24</p><p>　　3.5 信息包的分批重傳25</p><p>　　

9、3.6 具體重傳過(guò)程26</p><p>　　3.6.1 重傳方案描述26</p><p>　　3.6.2 實(shí)際重傳方案描述28</p><p>　　第4章 應(yīng)用隨機(jī)網(wǎng)絡(luò)編碼性能分析20</p><p>　　4.1 數(shù)學(xué)理論分析20</p><p>　　4.2 模擬測(cè)試分析20</p>

10、<p>　　4.3 本章小結(jié)20</p><p><b>　　結(jié)論2</b></p><p><b>　　參考文獻(xiàn)3</b></p><p><b>　　致謝4</b></p><p><b>　　附錄16</b></p>

11、<p><b>　　附錄26</b></p><p><b>　　附錄36</b></p><p><b>　　附錄412</b></p><p><b>　　第1章 緒論</b></p><p>　　近年來(lái)，隨著無(wú)線技術(shù)的成熟，越來(lái)越多

12、的人通過(guò)無(wú)線方式連接到互聯(lián)網(wǎng)上。與此同時(shí)，由于用戶數(shù)量的陡然增多、用戶對(duì)網(wǎng)絡(luò)服務(wù)需求的多樣性以及用戶對(duì)傳輸質(zhì)量要求的不斷提高，如何保障無(wú)線鏈路的可靠安全傳輸、優(yōu)化無(wú)線網(wǎng)絡(luò)性能、在現(xiàn)有網(wǎng)絡(luò)資源的基礎(chǔ)上提高網(wǎng)絡(luò)資源的利用率等問(wèn)題已成為當(dāng)今無(wú)線網(wǎng)絡(luò)通信研究的重要課題之一。</p><p>　　1.1 課題背景及意義</p><p>　　數(shù)據(jù)廣播業(yè)務(wù)在蜂窩網(wǎng)絡(luò)和無(wú)線Mesh網(wǎng)絡(luò)中的應(yīng)用越來(lái)越廣泛，

13、自動(dòng)重復(fù)重傳(Automatic Repeat reQuest,ARQ)已經(jīng)成為無(wú)線通信環(huán)境下的提供可靠通信的重要容錯(cuò)手段。普通的自動(dòng)重復(fù)重傳機(jī)制主要包括：停止-等待自動(dòng)重復(fù)重傳(SW-ARQ)、返回N型自動(dòng)重復(fù)重傳(GBN-ARQ)和選擇自動(dòng)重復(fù)重傳(SR-ARQ)。盡管自動(dòng)重復(fù)重傳應(yīng)用于點(diǎn)對(duì)點(diǎn)傳輸確實(shí)可以達(dá)到較高的傳輸性能，然而對(duì)于多用戶的廣播、組播傳輸，其性能會(huì)隨接收節(jié)點(diǎn)數(shù)目的增加而迅速下降。</p>

14、<p>　　2000年，香港中文大學(xué)的A.Rhlswede等基于網(wǎng)絡(luò)流的概念率先提出了網(wǎng)絡(luò)編碼這一概念，其精髓來(lái)源于著名的Max-flow Min-cut（最大流最小割）理論。網(wǎng)絡(luò)編碼是指網(wǎng)絡(luò)節(jié)點(diǎn)既實(shí)現(xiàn)路由功能又實(shí)現(xiàn)編碼功能。利用無(wú)線信道的廣播特性，網(wǎng)絡(luò)編碼被應(yīng)用于提高無(wú)線網(wǎng)絡(luò)性能、提高吞吐量、安全性等。同時(shí)網(wǎng)絡(luò)編碼也為無(wú)線廣播重傳提供了一種途徑。2006年，Nguyen等人將網(wǎng)絡(luò)編碼技術(shù)應(yīng)用于重傳策略中，提出了兩個(gè)接收節(jié)點(diǎn)

15、的編碼重傳策略，減少了平均傳輸次數(shù)，但Nguyen等人的策略僅考慮了兩個(gè)接收節(jié)點(diǎn)的情況且沒(méi)有提出具體的編碼方案。</p><p>　　網(wǎng)絡(luò)廣播中應(yīng)用普通重傳策略，較高的出錯(cuò)率會(huì)產(chǎn)生2個(gè)方面的問(wèn)題：廣播傳輸中丟失信息包較多，需要數(shù)量較大的重傳次數(shù)；重傳信息包再次丟失，需要次數(shù)較大的再次重傳。因此如何利用現(xiàn)有的網(wǎng)絡(luò)資源來(lái)提高重傳效率成為研究的熱點(diǎn)?，F(xiàn)在推廣到多個(gè)接收節(jié)點(diǎn)的情況下，將網(wǎng)絡(luò)編碼與廣播重傳相結(jié)合以減少重傳次

16、數(shù)、提高重傳效率。因此，研究將網(wǎng)絡(luò)編碼應(yīng)用于單源多宿的無(wú)線廣播網(wǎng)絡(luò)中以降低重傳次數(shù)是很有必要的。</p><p>　　1.2 本課題國(guó)內(nèi)外的研究現(xiàn)狀</p><p>　　無(wú)線傳輸中的廣播信道特性，使得網(wǎng)絡(luò)編碼在減少無(wú)線傳輸次數(shù)方面有很好的應(yīng)用，近年來(lái)出現(xiàn)了很多相關(guān)的研究。Wu等人提出了利用網(wǎng)絡(luò)編碼減少信息包互換傳輸次數(shù)的方法，Bin等人提出了網(wǎng)絡(luò)編碼尋找無(wú)線Mesh網(wǎng)最少傳輸次數(shù)路徑的思想

17、。Katti等人構(gòu)造了無(wú)線Mesh網(wǎng)絡(luò)使用網(wǎng)絡(luò)編碼的體系結(jié)構(gòu)COPE，并利用29個(gè)節(jié)點(diǎn)的實(shí)驗(yàn)平臺(tái)證實(shí)能顯著減少平均傳輸次數(shù)。Chachulski等人則提出無(wú)線路由協(xié)議MORE，并證實(shí)該協(xié)議能有效減少信息包的平均發(fā)送次數(shù)。同時(shí)，與傳統(tǒng)的有線網(wǎng)絡(luò)相比，無(wú)線網(wǎng)絡(luò)擁有較高的比特出錯(cuò)率，重傳效率問(wèn)題顯得更加重要。</p><p>　　目前的研究現(xiàn)狀來(lái)看，國(guó)外在無(wú)線傳輸技術(shù)中引入網(wǎng)絡(luò)編碼的研究起步較早。國(guó)外多所著名大學(xué)如麻省

18、理工學(xué)院、普林斯頓大學(xué)、多倫多大學(xué)、瑞士EPFL學(xué)院等和多家IT公司的研究中心，包括微軟研究酣、貝爾實(shí)驗(yàn)室、AT&T的香農(nóng)信息實(shí)驗(yàn)室等都在積極開展相關(guān)的研究。</p><p>　　目前國(guó)外在無(wú)線傳輸技術(shù)中引入網(wǎng)絡(luò)編碼的研究主要側(cè)重在二個(gè)方面：改善無(wú)線傳輸吞吐量和能量利用效率、保證無(wú)線鏈路的可靠傳輸和安全性。在無(wú)線傳輸吞吐量研究上，Ahlswede等人指出網(wǎng)絡(luò)編碼可以達(dá)到組播傳輸理論最大流速；Li等人Kot

19、ter等人先后證明線性網(wǎng)絡(luò)編碼、隨機(jī)網(wǎng)絡(luò)編碼同樣可以達(dá)到組播傳輸理論最大流速、并對(duì)網(wǎng)絡(luò)編碼的數(shù)學(xué)框架進(jìn)行了闡述，為網(wǎng)絡(luò)編碼在無(wú)線組播傳輸吞吐量方面的研究提供了必要的理論條件。在能量利用效率方面，Wu等人證明在無(wú)線網(wǎng)絡(luò)組播時(shí)應(yīng)用網(wǎng)絡(luò)編碼，可以將最小化每位數(shù)據(jù)能量消耗問(wèn)題歸結(jié)為線性問(wèn)題，為能量利用效率方面的研究提供了基礎(chǔ)。KaRi等人證實(shí)了局部混合網(wǎng)絡(luò)編碼的傳輸，在TCP和UDP傳輸流的環(huán)境下均可以顯著提高傳輸吞量；Wu等人接下來(lái)研究了基于

20、局部混合網(wǎng)絡(luò)編碼互換傳輸?shù)男阅?，證明了互換傳輸可以優(yōu)化傳輸性能，這些研究均為局部混合網(wǎng)絡(luò)編碼傳輸提供了理論基礎(chǔ)和條件。無(wú)線網(wǎng)絡(luò)由于環(huán)境的多變性，使得數(shù)據(jù)包在傳輸中更加容易丟失，傳輸中的重傳技術(shù)研究非常必要。當(dāng)前應(yīng)用網(wǎng)絡(luò)編碼的重傳技術(shù)研究主要涉及二個(gè)接收節(jié)點(diǎn)情況下的編碼發(fā)送重傳。</p><p>　　從目前的研究現(xiàn)狀來(lái)看，國(guó)內(nèi)在無(wú)線傳輸中引入網(wǎng)絡(luò)編碼的研究起步較晚，中科院軟件研究所、清華大學(xué)、中國(guó)科技大學(xué)、國(guó)防科技

21、大學(xué)、上海交通大學(xué)、華中科技大學(xué)等高校均有相關(guān)的研究組進(jìn)行該課題有關(guān)的領(lǐng)域研究。在無(wú)線組播傳輸性能研究線多源信息交換傳輸、P2P數(shù)據(jù)流傳輸、衛(wèi)星技術(shù)中的組播傳輸、無(wú)線網(wǎng)絡(luò)的動(dòng)態(tài)網(wǎng)絡(luò)編碼協(xié)助通信等方面，國(guó)內(nèi)均進(jìn)行了相關(guān)的研究。</p><p>　　從當(dāng)前的國(guó)內(nèi)外研究情況來(lái)看，基于網(wǎng)絡(luò)編碼的無(wú)線傳輸技術(shù)的核心思想仍然是通過(guò)增加節(jié)點(diǎn)的編碼(計(jì)算)能力來(lái)?yè)Q取網(wǎng)絡(luò)傳輸增益。一方面網(wǎng)絡(luò)編碼進(jìn)行的運(yùn)算復(fù)雜度相對(duì)來(lái)說(shuō)較低，另一個(gè)

22、方面來(lái)看，相比網(wǎng)絡(luò)傳輸增益，節(jié)點(diǎn)計(jì)算代價(jià)和延時(shí)是可以接受的。</p><p>　　網(wǎng)絡(luò)編碼技術(shù)的提出只有10年的時(shí)間。Ahlswede等人首先提出網(wǎng)絡(luò)編碼這個(gè)概念。他們的工作主要針對(duì)單個(gè)源點(diǎn)，多個(gè)接收點(diǎn)的信息傳輸問(wèn)題，證明了在源點(diǎn)發(fā)送能力無(wú)限的情況下，一個(gè)網(wǎng)絡(luò)的最大信息傳送率等于該網(wǎng)絡(luò)的最小割的容量也就是網(wǎng)絡(luò)的最大流。將信息傳輸與圖論的最大流最小割問(wèn)題聯(lián)系在一起。這也是第一次提出通信網(wǎng)絡(luò)的容量問(wèn)題。Ahlswed

23、e等人僅給出了網(wǎng)絡(luò)最大信息傳送速率的存在性證明，并沒(méi)有給出具體的網(wǎng)絡(luò)編碼實(shí)現(xiàn)方式。Li，Yeung和Cai提出單一源，多接收點(diǎn)網(wǎng)絡(luò)的最大傳輸速率可以通過(guò)線性編碼實(shí)現(xiàn)。通過(guò)一個(gè)廣泛適的線性編碼多播算法(LCM)，每個(gè)接收節(jié)點(diǎn)都可以無(wú)線網(wǎng)絡(luò)編碼研究達(dá)到其最大流。LCM主要應(yīng)用于非循環(huán)網(wǎng)絡(luò)。LCM規(guī)則為每條邊分配邊向量，每個(gè)節(jié)點(diǎn)分配向量空間。邊向量與點(diǎn)向量空間按照LCM規(guī)則滿足一定的關(guān)系．通過(guò)邊向量和節(jié)點(diǎn)上的信息向量相乘對(duì)信息編碼，在接收節(jié)點(diǎn)

24、處使用逆矩陣解碼。LCM方法可以達(dá)到任意節(jié)點(diǎn)的最大流。但由于LCM規(guī)則過(guò)于嚴(yán)格，尋找符合規(guī)則的向量需要大量的時(shí)間，造成了網(wǎng)絡(luò)的延時(shí)，因此LCM不適合用在實(shí)際網(wǎng)絡(luò)中。Koctter等人為網(wǎng)絡(luò)解碼設(shè)計(jì)了一個(gè)數(shù)學(xué)框架。它將一般的網(wǎng)絡(luò)</p><p>　　1.3 本課題研究的主要內(nèi)容</p><p>　　本課題的研究目標(biāo)是結(jié)合網(wǎng)絡(luò)編碼的思想，提出應(yīng)用于不同傳輸因素下的廣播重傳策略。傳輸損耗較嚴(yán)重的

25、情況下無(wú)線廣播傳輸錯(cuò)誤率高，必須使用重傳策略來(lái)進(jìn)行錯(cuò)誤處理。普通的重傳策略的思想在高損耗無(wú)線網(wǎng)絡(luò)廣播中會(huì)產(chǎn)生2個(gè)方面的問(wèn)題：丟失的信息包多需要較大的重傳次數(shù)；再次丟包率較高，需較大數(shù)量的再次重傳。</p><p>　　因此，本課題研究單源節(jié)點(diǎn)、多個(gè)接收節(jié)點(diǎn)的情況下，將網(wǎng)絡(luò)編碼應(yīng)用于無(wú)線廣播重傳問(wèn)題以提高重傳效率、減少重傳次數(shù)，為網(wǎng)絡(luò)編碼技術(shù)在實(shí)際無(wú)線傳輸環(huán)境中的應(yīng)用提供良好的理論基礎(chǔ)。</p>&l

26、t;p>　　研究的主要內(nèi)容為：分析針對(duì)不同丟包率進(jìn)行網(wǎng)絡(luò)編碼重傳的可解性條件，提出具有實(shí)際可用性的網(wǎng)絡(luò)編碼組合算法和重傳機(jī)制；針對(duì)基于網(wǎng)絡(luò)編碼的無(wú)線廣播重傳策略在較高鏈路丟包率的性能下降問(wèn)題，引入重傳再丟失策略和發(fā)送排序策略進(jìn)行改進(jìn)來(lái)改善重傳性能。</p><p>　　1.4 本文的章節(jié)安排</p><p>　　本文通過(guò)深入理解網(wǎng)絡(luò)編碼和無(wú)線網(wǎng)絡(luò)領(lǐng)域近年來(lái)的重要研究成果，對(duì)網(wǎng)絡(luò)編碼在

27、無(wú)線傳輸網(wǎng)絡(luò)中的應(yīng)用進(jìn)行了深入的研究。設(shè)計(jì)了一種基于網(wǎng)絡(luò)編碼的無(wú)線廣播重傳方案，以減少重傳次數(shù)提高重傳效率，各章的內(nèi)容組織如下：</p><p>　　第1章為緒論，主要介紹了應(yīng)用網(wǎng)絡(luò)編碼的無(wú)線廣播傳輸技術(shù)的研究背景和意義、國(guó)內(nèi)外的研究現(xiàn)狀以及當(dāng)前主要的研究成果，并對(duì)本文的主要工作進(jìn)行了論述。</p><p>　　第2章介紹了網(wǎng)絡(luò)編碼基本原理與最大流最小割定理，在此基礎(chǔ)上又進(jìn)一步闡述了幾種常

28、見(jiàn)的網(wǎng)絡(luò)編碼的構(gòu)造方法和它們的優(yōu)缺點(diǎn)。并從中選擇了隨機(jī)網(wǎng)絡(luò)編碼進(jìn)行研究設(shè)計(jì)。</p><p>　　第3章設(shè)計(jì)了一種隨機(jī)線性網(wǎng)絡(luò)編碼的重傳方案。首先建立了接近現(xiàn)實(shí)環(huán)境的無(wú)線廣播模型，構(gòu)造了隨即網(wǎng)絡(luò)編碼包，具體的描述了重傳過(guò)程以及重傳機(jī)制。</p><p>　　第4章用表與圖兩種形式展現(xiàn)了接受節(jié)點(diǎn)在不同的丟包率的情況下應(yīng)用隨機(jī)線性網(wǎng)絡(luò)編碼的重傳方法與傳統(tǒng)的方法在總的傳輸次數(shù)的比較，充分的證明了

29、應(yīng)用隨機(jī)線性網(wǎng)絡(luò)編碼的重傳方法。</p><p>　　第2章 基于網(wǎng)絡(luò)編碼的無(wú)線傳輸?shù)姆治?lt;/p><p>　　網(wǎng)絡(luò)編碼從廣義上講是網(wǎng)絡(luò)中的中間節(jié)點(diǎn)是網(wǎng)絡(luò)中的節(jié)點(diǎn)將接收到的信息進(jìn)行編碼后再轉(zhuǎn)發(fā)出去的多點(diǎn)傳送技術(shù)。網(wǎng)絡(luò)編碼理論徹底改變了傳統(tǒng)的存儲(chǔ)轉(zhuǎn)絡(luò)性能可以達(dá)到最大流傳輸?shù)睦碚摌O限。而隨機(jī)網(wǎng)絡(luò)編碼理論將網(wǎng)絡(luò)編碼的應(yīng)用延伸到任意網(wǎng)絡(luò)結(jié)構(gòu)中。隨機(jī)網(wǎng)絡(luò)編碼在無(wú)線網(wǎng)絡(luò)中的應(yīng)用更是因此得到了長(zhǎng)足的發(fā)

30、展。本章將首先介紹網(wǎng)絡(luò)編碼的基本理論，然后將引出隨機(jī)網(wǎng)絡(luò)編碼在無(wú)線網(wǎng)絡(luò)中的一般模型和方法為后續(xù)的章節(jié)的展開做好鋪墊</p><p>　　2.1網(wǎng)絡(luò)編碼的概念與定義 </p><p>　　網(wǎng)絡(luò)編碼(Network Coding)是一種融合編碼和路由的信息交換技術(shù)，在傳統(tǒng)存儲(chǔ)轉(zhuǎn)發(fā)路由方法基礎(chǔ)上，通過(guò)允許對(duì)接收的多個(gè)數(shù)據(jù)包進(jìn)行編碼信息融合，增加單次傳輸?shù)南⒘?，提高網(wǎng)絡(luò)整體性能。網(wǎng)絡(luò)編碼的本質(zhì)是利

31、用節(jié)點(diǎn)的計(jì)算能力提高鏈路帶寬的利率。</p><p>　　2.1.1 網(wǎng)絡(luò)編碼的基本原理 </p><p>　　如圖2-1所示，節(jié)點(diǎn)N是網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)，其收到來(lái)自不同鏈路的信息包x、 y、z并需要對(duì)信息包進(jìn)行傳輸發(fā)送處理。如圖2-1.a)所示在傳統(tǒng)的計(jì)算機(jī)網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)（可以是交換機(jī)或路由器），在存儲(chǔ)轉(zhuǎn)發(fā)模式下，節(jié)點(diǎn)只進(jìn)行數(shù)據(jù)分組的路由和復(fù)制。而不同與傳統(tǒng)網(wǎng)絡(luò)，具有網(wǎng)絡(luò)編碼功能的節(jié)點(diǎn)則

32、會(huì)對(duì)數(shù)據(jù)包進(jìn)行編碼/解碼運(yùn)算，如圖2-1.b)，交換機(jī)輸出的信息流是其輸入的信息流的函數(shù)。</p><p>　　采用傳統(tǒng)路由方法，節(jié)點(diǎn)N僅需要對(duì)收到的信息包進(jìn)行存儲(chǔ)和轉(zhuǎn)發(fā)，節(jié)點(diǎn)的發(fā)送信息包為x、y、z。</p><p>　　采用網(wǎng)絡(luò)編碼，節(jié)點(diǎn)N可以對(duì)收到的信息包進(jìn)行編碼運(yùn)算，通過(guò)運(yùn)算信息包x、y、z獲得信息包F1(x, y, z)、F2(x, y, z)、F3(x, y, z)，新信息包是

33、來(lái)自不同鏈路的收到信息包的編碼組合。此時(shí)，若通過(guò)網(wǎng)絡(luò)編碼進(jìn)行發(fā)送，節(jié)點(diǎn)實(shí)現(xiàn)了對(duì)接收的多個(gè)數(shù)據(jù)的編碼信息融合操作，即網(wǎng)絡(luò)編碼操作。傳統(tǒng)網(wǎng)絡(luò)的存儲(chǔ)轉(zhuǎn)發(fā)模式可看作網(wǎng)絡(luò)編碼的特例。</p><p>　　為了便于網(wǎng)絡(luò)編碼理論的分析闡述，我們僅考慮組播情況并且建立相應(yīng)的網(wǎng)絡(luò)模型，模型中假設(shè)邊的帶寬為單位容量，允許節(jié)點(diǎn)間存在多條邊，并忽略邊的傳輸錯(cuò)誤及延時(shí)。</p><p>　　傳統(tǒng)網(wǎng)絡(luò)分析中，通信網(wǎng)絡(luò)

34、中的信息流被認(rèn)為是網(wǎng)絡(luò)管道中的流體，類似于水在渠道中流動(dòng)一樣。對(duì)于一個(gè)實(shí)際的通信網(wǎng)絡(luò)，我們可以采用一個(gè)有向圖G(V,E)來(lái)加以描述和研究。對(duì)于圖G = (V, E)，這里V 表示節(jié)點(diǎn)的集合，E表示邊的集合。網(wǎng)絡(luò)中一條邊用(i, j)表示，這里i，j 為網(wǎng)絡(luò)中的兩個(gè)節(jié)點(diǎn)。若圖G = (V, E)僅有一個(gè)源節(jié)點(diǎn)s和一個(gè)接收節(jié)點(diǎn)t，且有向圖中的每一條邊(i, j)對(duì)應(yīng)著一個(gè)非負(fù)數(shù)，并令其為該邊的容量，則稱該有向圖為網(wǎng)絡(luò)流圖。對(duì)于網(wǎng)絡(luò)流圖G．每

35、一條邊(i, j)都給</p><p>　　定一個(gè)非負(fù)數(shù)f ，這一組數(shù)滿足下列兩個(gè)條件時(shí)稱為這網(wǎng)絡(luò)的可行流，用表示它。</p><p>　　1. 每一條邊(i, j) ,有。</p><p>　　2．除了源節(jié)點(diǎn)s和接收節(jié)點(diǎn)t 以外的所有的節(jié)點(diǎn)i ，恒有式(2-1):</p><p><b>　　(2-1)</b><

36、/p><p>　　這表示中間節(jié)點(diǎn)i的流量守恒，即節(jié)點(diǎn)的輸入的流量和輸出的流量是相等的。</p><p>　　3．源節(jié)點(diǎn)s和接收節(jié)點(diǎn)t滿足公式(2-2):</p><p><b>　　(2-2)</b></p><p>　　其中R稱作網(wǎng)絡(luò)流的流量，而且從源節(jié)點(diǎn)流出的總量等于流入接收節(jié)點(diǎn) 的總量。</p><

37、p>　　當(dāng)時(shí)便稱邊(i, j)飽和，或f 飽和，表示流f 對(duì)該邊已飽和。該網(wǎng)絡(luò)的最大流是指從源節(jié)點(diǎn)送往接收節(jié)點(diǎn)的流量R的最大值，用max flow(s, t)表示。設(shè)U 為節(jié)點(diǎn)集合的一個(gè)子集，使得s∈U ，t?U ，把一個(gè)端點(diǎn)屬于U 而另一個(gè)端點(diǎn)不屬于U 的邊的集合稱作源節(jié)點(diǎn)s 和接收節(jié)點(diǎn)t 的一個(gè)割。割的容量的定義為集合EU中包含的所有邊的容量的和，用C(s, t)表示，即式(2-3):</p><p>

38、<b>　　(2-3)</b></p><p>　　2.1.2 最大流-最小割定理</p><p>　　網(wǎng)絡(luò)編碼通過(guò)允許對(duì)來(lái)自不同鏈路的信息進(jìn)行編碼組合，從而提高網(wǎng)絡(luò)性能，在這種全新的體系結(jié)構(gòu)下，網(wǎng)絡(luò)性能可以達(dá)到最大流傳輸?shù)睦碚摌O限。</p><p>　　最大流-最小割定理：對(duì)于已知的網(wǎng)絡(luò)流圖，從信源節(jié)點(diǎn)s到接收節(jié)點(diǎn)t的流量R的最大值等于其最小

39、割的容量，即式（2-4）：</p><p><b>　　(2-4)</b></p><p>　　對(duì)于有向網(wǎng)絡(luò)，可以用Ford-Fulkerson算法來(lái)求解網(wǎng)絡(luò)的最大流。</p><p>　　對(duì)于網(wǎng)絡(luò)信息流，G(V,E) 為一個(gè)多播網(wǎng)絡(luò)， h 為信息從信源s 到信宿t1，t2，t3，…的多播傳輸速率。令信源節(jié)點(diǎn)s到接收節(jié)點(diǎn)的最大流值為max fl

40、ow(s, )， 則對(duì)于所有的l =1,2,…,L，有：</p><p><b>　　即</b></p><p>　　將這個(gè)稱作網(wǎng)絡(luò)多播傳輸?shù)淖畲罅飨蕖?lt;/p><p>　　如圖2-2所示，圖中給出了最大流最小割定理的一個(gè)實(shí)例，，圖中從信源節(jié)點(diǎn)s到接收節(jié)點(diǎn)的流量最大值C等于信源節(jié)點(diǎn)到接收節(jié)點(diǎn)t的最大割集，即有：</p><p

41、>　　C=min{cut(s，t)}=9。</p><p>　　圖2-3所示的蝴蝶網(wǎng)絡(luò)是網(wǎng)絡(luò)編碼實(shí)現(xiàn)最大流傳輸?shù)睦?。圖中假設(shè)網(wǎng)絡(luò)中各條鏈路無(wú)差錯(cuò)和無(wú)時(shí)延，源節(jié)點(diǎn)s通過(guò)網(wǎng)絡(luò)將l比特信息a和b傳輸?shù)浇邮展?jié)點(diǎn)x和z，所有的鏈路容量均為l。</p><p>　　由圖2-4.a)的網(wǎng)絡(luò)鏈路容量圖，可以得知：</p><p><b>　　(2-5) &l

42、t;/b></p><p>　　由最大流最小割定理有：</p><p><b>　　(2-6)</b></p><p>　　由圖論中的點(diǎn)對(duì)點(diǎn)的最大流最小割定理，對(duì)于已知的網(wǎng)絡(luò)流圖2-4.a)，從源節(jié)點(diǎn)到接收節(jié)點(diǎn)的流量的最大值小于或等于任何一個(gè)割切的容量，即源節(jié)點(diǎn)s到接收節(jié)點(diǎn)x, z，的最大傳輸速率小于或等于2。</p>&l

43、t;p>　　圖2-3.b)是傳統(tǒng)路由傳輸?shù)那闆r，節(jié)點(diǎn)w一次只能傳送l比特信息到節(jié)點(diǎn)d，節(jié)點(diǎn)d也只能傳送l比特信息到接收節(jié)點(diǎn)x和 z,節(jié)點(diǎn)w和d之間的鏈路不得不使用了二次，接收節(jié)點(diǎn)x和z總共收到3比特信息，平均傳輸速率是1．5比特／單位時(shí)間。采用傳統(tǒng)路由傳輸情況，發(fā)送者達(dá)不到最大流限。</p><p>　　圖2-3.c)是網(wǎng)絡(luò)編碼傳輸?shù)那闆r，這里采用異或(模2和)的編碼方案。中間節(jié)點(diǎn)w輸入信息流進(jìn)行編碼，將編

44、碼的結(jié)果傳送到節(jié)點(diǎn)d，再傳送給接收節(jié)點(diǎn)x, z。接收節(jié)點(diǎn)x，根據(jù)自身己收到的信息a和，可以通過(guò)解碼解出b。同理，接收節(jié)點(diǎn)z也能通過(guò)解碼出a的完整的信息，這樣所能達(dá)到的平均速率是2比特／單位時(shí)間，發(fā)送者可以達(dá)到網(wǎng)絡(luò)的最大流限。</p><p>　　2.2 幾種常見(jiàn)的網(wǎng)絡(luò)編碼構(gòu)造方法 </p><p>　　在網(wǎng)絡(luò)傳輸中應(yīng)用網(wǎng)絡(luò)編碼技術(shù)，在每個(gè)節(jié)點(diǎn)如何進(jìn)行編碼組合，相應(yīng)的網(wǎng)絡(luò)編碼構(gòu)造方法至關(guān)重要

45、。如果網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)傳輸?shù)男畔⑦M(jìn)行線性操作, 則稱為線性網(wǎng)絡(luò)編碼,否則稱為非線性網(wǎng)絡(luò)編碼。根據(jù)網(wǎng)絡(luò)編碼系數(shù)的選取，主要分為確定性網(wǎng)絡(luò)編碼和隨機(jī)網(wǎng)絡(luò)編碼。確定性網(wǎng)絡(luò)編碼中網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)信息符號(hào)進(jìn)行組合的系數(shù)是確定產(chǎn)生的，而隨機(jī)網(wǎng)絡(luò)編碼的組合系數(shù)通常隨機(jī)選取。本章介紹了幾種常見(jiàn)的網(wǎng)絡(luò)編碼構(gòu)造方式，這也是我們后面算法的基礎(chǔ)。</p><p>　　2.2.1 網(wǎng)絡(luò)編碼的前提假設(shè)</p><p>　　Li等

46、人提出，通用的網(wǎng)絡(luò)編碼方法可以通過(guò)簡(jiǎn)單的線性運(yùn)算實(shí)現(xiàn)，即節(jié)點(diǎn)的輸出信息流是輸入信息流的線性組合，因此這種編碼方法稱為線性網(wǎng)絡(luò)編碼。下面介紹的幾種形式的網(wǎng)絡(luò)編碼都是基于這一簡(jiǎn)單的思想，只是編碼的構(gòu)造過(guò)程不同。為了簡(jiǎn)化計(jì)算我們要作如下假設(shè)：</p><p>　　(1)傳輸網(wǎng)絡(luò)是非循環(huán)網(wǎng)絡(luò)</p><p>　　(2)容量為n的路徑可以看作是n條單位容量路徑的并聯(lián)。</p><

47、p>　　(3)網(wǎng)絡(luò)中不存在傳輸錯(cuò)誤，只存在由于節(jié)點(diǎn)和鏈路的無(wú)效造成的信息丟失。</p><p>　　(4)每條邊傳輸信號(hào)的時(shí)延相同。</p><p>　　(5)多個(gè)源節(jié)點(diǎn)的網(wǎng)絡(luò)可以看成只有一個(gè)虛擬源節(jié)點(diǎn)的網(wǎng)絡(luò)。</p><p>　　假設(shè)解釋：為了簡(jiǎn)化問(wèn)題的表示與描述，假定傳輸網(wǎng)絡(luò)中沒(méi)有環(huán)路的存在，這也是無(wú)時(shí)延網(wǎng)絡(luò)的前提條件；通過(guò)選擇一個(gè)非常小的單位容量，使每?jī)?/p>

48、個(gè)節(jié)點(diǎn)中間都有整數(shù)條路徑連接。這樣在下面討論兩個(gè)節(jié)點(diǎn)之間的容量的時(shí)候就可以用兩個(gè)節(jié)點(diǎn)之間的單位路徑數(shù)量來(lái)衡量，且單位路徑在單位時(shí)間內(nèi)傳輸單位信息；假設(shè)理想情況，取消了網(wǎng)絡(luò)的同步要求。在后面我們會(huì)討論更實(shí)用的網(wǎng)絡(luò)編碼。 </p><p>　　虛擬源的設(shè)置如圖2-4。</p><p>　　網(wǎng)絡(luò)可以通過(guò)一個(gè)虛擬源節(jié)點(diǎn)和一些虛擬鏈接，使虛擬源節(jié)點(diǎn)含有所有實(shí)際源節(jié)點(diǎn)所含有的信息，而將所有實(shí)際源節(jié)點(diǎn)都

49、轉(zhuǎn)化成傳輸網(wǎng)絡(luò)的中間節(jié)點(diǎn)。整個(gè)網(wǎng)絡(luò)就從多個(gè)源節(jié)點(diǎn)、多個(gè)接收節(jié)點(diǎn)的網(wǎng)絡(luò)轉(zhuǎn)化成為單個(gè)源節(jié)點(diǎn)、多接收節(jié)點(diǎn)的網(wǎng)絡(luò)。虛擬的方法是，將網(wǎng)絡(luò)中實(shí)際的源看作是這個(gè)虛擬源節(jié)點(diǎn)連接的第一層接收節(jié)點(diǎn)。如果實(shí)際的源節(jié)點(diǎn)每次有n個(gè)信息要傳送給其他節(jié)點(diǎn)，那么在虛擬源節(jié)點(diǎn)與這個(gè)實(shí)際源節(jié)點(diǎn)之間的鏈接上，信息以n個(gè)單位信息每單位時(shí)間的速率傳送。相當(dāng)于所有信息都是從虛擬源節(jié)點(diǎn)通過(guò)實(shí)際源節(jié)點(diǎn)傳送給接收節(jié)點(diǎn)的。</p><p>　　2.2.2 線性向量

50、編碼</p><p>　　假設(shè)源節(jié)點(diǎn)s發(fā)出的所有信息都是d維(d是整個(gè)網(wǎng)絡(luò)所有接收點(diǎn)最大流的最小值)的行向量，稱為信息向量。源節(jié)點(diǎn)一次傳送d個(gè)不同的信息，對(duì)應(yīng)信息放在信息向量的對(duì)應(yīng)位置上。對(duì)每個(gè)信息進(jìn)行標(biāo)號(hào)，無(wú)論信息中間經(jīng)過(guò)怎樣的變化在信息向量中的位置是不變的。中間節(jié)點(diǎn)將所有接到的信息按照標(biāo)號(hào)放在對(duì)應(yīng)位置上，形成中間節(jié)點(diǎn)的信息向量。</p><p>　　節(jié)點(diǎn)根據(jù)線性編碼多播LCM(Line

51、ar-code muticast)的規(guī)則為每一條邊分配一個(gè)邊向量，也稱為局部編碼向量。邊上傳遞的信息是節(jié)點(diǎn)的信息向量與局部編碼向量作向量乘法之后得到的數(shù)值。每一個(gè)信息都攜帶一條全局編碼向量。這條全局編碼向量記載了某個(gè)信息在網(wǎng)絡(luò)中經(jīng)過(guò)不同的邊所經(jīng)歷的編碼的過(guò)程。中間節(jié)點(diǎn)發(fā)送信息的時(shí)候，首先將所有接到信息的全局編碼向量合成一個(gè)d*d的矩陣。信息k的全局編碼是矩陣中的第k列。該矩陣與邊上的邊向量根據(jù)編碼規(guī)則作向量乘法，得到的d維列向量就是輸出

52、信息的全局編碼向量。在解碼信息的時(shí)候，將所有接到的信息的全局編碼組合成一個(gè)完整的矩陣F。因?yàn)樗灾灰獬龅哪婢仃嚲涂梢越獯a出原始信息。</p><p><b>　　(2-5)</b></p><p>　　為了方便起見(jiàn)，源節(jié)點(diǎn)的第k條邊向量可以簡(jiǎn)化成僅在第k 個(gè)位置上向量的值不為0。通過(guò)這種方法源節(jié)點(diǎn)首次傳輸?shù)男畔?shí)際是不同的單個(gè)信息而不是信息混合后的結(jié)果。</p

53、><p>　　定義2.1 一個(gè)通用的多播網(wǎng)絡(luò)的線性編碼(LCM)方法是，對(duì)于傳輸網(wǎng)絡(luò)，V是所有節(jié)點(diǎn)的集合，E是所有邊的集合。給每一個(gè)節(jié)點(diǎn)v分配一個(gè)線性空間礦，每一條邊分配一個(gè)向量。源節(jié)點(diǎn)的向量它們之間的關(guān)系是：</p><p><b>　　(1)</b></p><p><b>　　(2)只要</b></p>&

54、lt;p>　　(3)對(duì)任何非源節(jié)點(diǎn)的集合，滿足：</p><p><b>　　(2-6)</b></p><p>　　(4)節(jié)點(diǎn)的輸出邊的向量是節(jié)點(diǎn)輸入邊向量的線性組合</p><p>　　其中<.>是線性張成的意思。是一個(gè)d維的向量空間，d是網(wǎng)絡(luò)的最大流。(1)的意思是源節(jié)點(diǎn)的向量空間是d維的，就是說(shuō)源節(jié)點(diǎn)可以同時(shí)發(fā)出d個(gè)線

55、性無(wú)關(guān)的信息。(2)的意思是對(duì)于某一個(gè)節(jié)點(diǎn)發(fā)出的所有邊，邊上的向量都屬于該點(diǎn)的向量空間。(3)的意思是某個(gè)非源節(jié)點(diǎn)的的向量空間可以由其發(fā)出的邊的向量線形張成。也就是說(shuō)，如果某些邊是從某個(gè)非源節(jié)點(diǎn)發(fā)出的，那么這些向量的線性運(yùn)算可以張成整個(gè)節(jié)點(diǎn)的線性空間。想實(shí)現(xiàn)這個(gè)要求就需要所有邊上的向量都是d維的線性無(wú)關(guān)的向量。(4)由于有這一條限制，輸出的信息包含全部的輸入信息。輸出信息是輸入信息的線性組合，也就是說(shuō)所有輸入信息的混合信息。雖然信息的大

56、小沒(méi)有變化，但是包含的信息量有所增加。在不增加傳送的次數(shù)的前提下增加了單個(gè)信息的接受范圍，由于一個(gè)信息可以被多個(gè)接收節(jié)點(diǎn)接收，相當(dāng)于不同接收節(jié)點(diǎn)共用了信道。</p><p>　　這種編碼方法的評(píng)價(jià)： 滿足以上方法的網(wǎng)絡(luò)編碼可以在網(wǎng)絡(luò)無(wú)錯(cuò)傳輸?shù)那闆r下，在接收節(jié)點(diǎn)處正確地解碼出所有的信息，同時(shí)使任何一個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)達(dá)到該節(jié)點(diǎn)的最大流。線性向量編碼可以充分利用網(wǎng)絡(luò)資源，使每一個(gè)傳輸?shù)男畔⒍急欢鄠€(gè)接收節(jié)點(diǎn)接收。但是要想達(dá)

57、到所有邊向量線性無(wú)關(guān)的限制，在選擇向量的時(shí)候必須將生成的向量與所有已知向量比較，確定任意維的向量之間都是線性無(wú)關(guān)的。當(dāng)網(wǎng)絡(luò)的容量很大的時(shí)候，由于任意n維向量所組成集合的數(shù)量隨著網(wǎng)絡(luò)的邊數(shù)成指數(shù)形式增長(zhǎng)，驗(yàn)證的工作量是很大的，因此將線性向量編碼應(yīng)用到大型網(wǎng)絡(luò)中是不現(xiàn)實(shí)的。</p><p>　　2.2.3 線性代數(shù)編碼</p><p>　　Koetter和Medard從代數(shù)構(gòu)造角度出發(fā)，給出了

58、實(shí)現(xiàn)線性網(wǎng)絡(luò)編碼的全局編碼向量所必須滿足的條件。</p><p>　　在這種表示方法中，引入了系統(tǒng)轉(zhuǎn)移矩陣來(lái)描述輸入變量與輸出變量之間的關(guān)系。設(shè)節(jié)點(diǎn)s是網(wǎng)絡(luò)中的唯一源節(jié)點(diǎn)，源節(jié)點(diǎn)s的輸出表示為。同時(shí)，用來(lái)表示接收節(jié)點(diǎn)s的輸入。則輸入變量和輸出變量之間的關(guān)系我們就可以表示為，其中就稱為系統(tǒng)轉(zhuǎn)移矩陣。所以，要想在接收節(jié)點(diǎn)由接收到的消息向量z得到源節(jié)點(diǎn)輸入，則必須要求系統(tǒng)轉(zhuǎn)移矩陣的行列式不為0。那么，剩下的問(wèn)題就是如何

59、求得系統(tǒng)轉(zhuǎn)移矩陣？</p><p>　　下面首先給出線性網(wǎng)絡(luò)編碼的代數(shù)描述。</p><p>　　定義2.2:設(shè)是無(wú)延遲的通信網(wǎng)絡(luò)。如果對(duì)于網(wǎng)絡(luò)中的每一條邊上的隨機(jī)過(guò)程均滿足</p><p><b>　　(2-7)</b></p><p><b>　　在接收節(jié)點(diǎn)處有：</b></p>

60、<p><b>　　(2-8)</b></p><p>　　其中，，，的取值為有限域中的元素。稱這樣的無(wú)延遲的通信網(wǎng)絡(luò)為線性網(wǎng)絡(luò)。</p><p>　　定義2．3：式(2-7)和式(2-8)中的系數(shù)，，被稱為局部編碼向量。</p><p>　　定義2．4：組播通信網(wǎng)絡(luò)中，信源節(jié)點(diǎn)的輸入可以看作是有限域上的向量。由于采用線性網(wǎng)絡(luò)編碼，則

61、邊上攜帶的信息是信源輸節(jié)點(diǎn)入符號(hào)向量的線性組合，用一個(gè)向量來(lái)表示，稱其為全局編碼向量。則有：</p><p><b>　　(2-9)</b></p><p>　　可以著出，全局編碼向量和局部編碼向量之間的關(guān)系是:</p><p><b>　　(2-10)</b></p><p>　　式(2-10)表

62、示全局編碼向量與局部編碼向量之間的關(guān)系，描述出了若要</p><p>　　在一個(gè)通信網(wǎng)絡(luò)中實(shí)現(xiàn)網(wǎng)絡(luò)編碼，網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)上需要進(jìn)行的各種操作?！?lt;/p><p>　　定義2.4：任意通信網(wǎng)絡(luò)的鄰接矩陣，其中的元素為：</p><p><b>　　(2-11)</b></p><p>　　則鄰接矩陣是一個(gè)的的矩陣，它直接反

63、映了通信網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。</p><p>　　定義2.5:任意通信網(wǎng)絡(luò)的信源輸出矩陣，其中的元素為：</p><p><b>　　(2-12)</b></p><p>　　它是一個(gè)階矩陣，反映了源節(jié)點(diǎn)的輸出情況。</p><p>　　定義2.6：任意通信網(wǎng)絡(luò)的接收節(jié)點(diǎn)輸入矩陣定義為：</p><p&g

64、t;<b>　?。?-13）</b></p><p>　　它是一個(gè)階矩陣，反映了某個(gè)接收節(jié)點(diǎn)對(duì)信息的接收情況。</p><p>　　式(2-11)、式(2-12)、式(2-13)中矩陣,和都用編碼向量來(lái)表示，它們反映了整個(gè)通信網(wǎng)絡(luò)的信息輸入輸出情況和整個(gè)拓?fù)浣Y(jié)構(gòu)的情況。</p><p>　　其次給出系統(tǒng)轉(zhuǎn)移矩陣的表達(dá)式。</p>

65、<p>　　定理2.7：在給定了一個(gè)表示網(wǎng)絡(luò)的矩陣，，后，可以得到這個(gè)網(wǎng)絡(luò)的系統(tǒng)的轉(zhuǎn)移矩陣為：</p><p><b>　　(2-14)</b></p><p>　　其中，一個(gè)的單位矩陣。</p><p>　　證明：矩陣與矩陣、對(duì)整個(gè)轉(zhuǎn)移矩陣不起根本性的作用，它們只是輸入與輸出隨機(jī)過(guò)程的一個(gè)線性組合。為了找到在一個(gè)輸入隨機(jī)過(guò)程與輸出隨

66、機(jī)過(guò)程間連接關(guān)系，必須沿著所有經(jīng)過(guò)的路徑記錄隨機(jī)過(guò)程所經(jīng)歷的所有變化，并最終轉(zhuǎn)化為。在網(wǎng)絡(luò)中節(jié)點(diǎn)間的路徑的變化可以用序列來(lái)表示。其中矩陣是一個(gè)上三角矩陣，最終將會(huì)有一個(gè)N使得為一個(gè)全零矩陣。又因?yàn)?，又有。所以得到，反映了源?jié)點(diǎn)的信息在網(wǎng)絡(luò)的傳輸過(guò)程中由于經(jīng)過(guò)網(wǎng)絡(luò)編碼而引起的影響。定理得證。</p><p>　　由以上的敘述可以得到以下重要定理：</p><p>　　定理2．8：給定一個(gè)線性

67、網(wǎng)絡(luò)，以下的三個(gè)命題是等價(jià)的：</p><p>　　(1)一個(gè)組播傳輸是可解的。</p><p>　　(2)可以達(dá)到圖G上由最小割-最大流定理得到的容量限。</p><p>　　(3)轉(zhuǎn)移矩陣的行列式在環(huán)非零。</p><p>　　只要根據(jù)約束條件，系統(tǒng)轉(zhuǎn)移矩陣的行列式不為0，確定出上式中的滿足條件的變量，也就是得到了局部編碼向量，就完成了這

68、個(gè)通信網(wǎng)絡(luò)的線性網(wǎng)絡(luò)編碼。</p><p>　　這種編碼方法的評(píng)價(jià)：代數(shù)編碼方法適用于動(dòng)態(tài)網(wǎng)絡(luò)，優(yōu)點(diǎn)在于編碼調(diào)整時(shí)的靈活性。當(dāng)網(wǎng)絡(luò)拓?fù)涓淖兊臅r(shí)候，網(wǎng)絡(luò)編碼矩陣不需要整體改動(dòng)，只需要局部調(diào)整編碼系數(shù)，令網(wǎng)絡(luò)的轉(zhuǎn)移矩陣對(duì)于所有接收節(jié)點(diǎn)都有解即可適應(yīng)新的網(wǎng)絡(luò)結(jié)構(gòu)。同時(shí)代數(shù)編碼抵抗網(wǎng)絡(luò)變化的能力更高，也就是魯棒性很好，尤其是對(duì)節(jié)點(diǎn)和鏈路丟失的錯(cuò)誤情況。因?yàn)殒溌返膩G失意味著在全局編碼矩陣中，邊上的局部編碼為0。由于網(wǎng)絡(luò)轉(zhuǎn)移

69、矩陣的行列式值由多個(gè)局部編碼聯(lián)合作用得到，其中幾個(gè)值為0有可能不會(huì)影響到所有接收節(jié)點(diǎn)。仍然有接收節(jié)點(diǎn)可以解碼出全部信息。同時(shí)網(wǎng)絡(luò)局部編碼系數(shù)也不需要太大的改變，因此稱代數(shù)編碼對(duì)于網(wǎng)絡(luò)鏈路的丟失有一定的魯棒性。但是這種方法由于需要每一個(gè)節(jié)點(diǎn)知道網(wǎng)絡(luò)的全局拓?fù)?，因而并不能完全在?shí)際網(wǎng)絡(luò)上應(yīng)用。</p><p>　　2.2.4 隨機(jī)網(wǎng)絡(luò)編碼</p><p>　　實(shí)際網(wǎng)絡(luò)中，由于網(wǎng)絡(luò)拓?fù)涞淖兓途W(wǎng)

70、絡(luò)規(guī)模的擴(kuò)大，每一個(gè)無(wú)線節(jié)點(diǎn)獲取整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)信息和網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的編碼系數(shù)是不容易實(shí)現(xiàn)的。針對(duì)這一問(wèn)題，Ho等人提出了一種隨機(jī)網(wǎng)絡(luò)編碼的思想。</p><p>　　隨機(jī)網(wǎng)絡(luò)編碼思想的系數(shù)構(gòu)造中，可以讓節(jié)點(diǎn)攜帶一個(gè)全局編碼向量，在經(jīng)過(guò)每一個(gè)節(jié)點(diǎn)的時(shí)候都根據(jù)該節(jié)點(diǎn)的編碼方式在改變信息的同時(shí)改變編碼向量。這樣當(dāng)接收節(jié)點(diǎn)接到信息的時(shí)候不需要知道整個(gè)網(wǎng)絡(luò)的拓?fù)浜途W(wǎng)絡(luò)的編碼情況，只要接到信息的全局編碼向量組成的矩陣維數(shù)d(一

71、次發(fā)送信息的數(shù)量)就可以解碼出全部的d個(gè)信息。這樣接收節(jié)點(diǎn)就不需要知道網(wǎng)絡(luò)拓?fù)?。圖2-5舉例說(shuō)明了隨機(jī)網(wǎng)絡(luò)編碼的思想。</p><p>　　圖2-5中，中間節(jié)點(diǎn)接收到信息編碼組合包和。此時(shí)，中間節(jié)點(diǎn)將應(yīng)用隨機(jī)網(wǎng)絡(luò)編碼的思想發(fā)送信息包，這就需要在一個(gè)有限域中隨機(jī)選取新的編碼系數(shù)(圖2-5例中選取的編碼系數(shù)為2、1)，并對(duì)編碼組合后的信息包包進(jìn)行新的編碼運(yùn)算得到新的編碼系數(shù)為6,9,12，將新的編碼組合包傳輸發(fā)送。該

72、方法不需要考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，并適合在分布式的網(wǎng)絡(luò)中使用。應(yīng)用隨機(jī)網(wǎng)絡(luò)編碼發(fā)送，當(dāng)節(jié)點(diǎn)收到滿足線性可解條件的編碼組合，即可使用解線性組合的方法獲得原始信息包。</p><p>　　隨機(jī)網(wǎng)絡(luò)編碼同時(shí)規(guī)定，中間節(jié)點(diǎn)在分配局部編碼向量的時(shí)候只需要在有限域中隨機(jī)選取系數(shù)，不需要驗(yàn)證是否相關(guān)。當(dāng)然這樣的結(jié)果是在接收節(jié)點(diǎn)可能出現(xiàn)的線性相關(guān)的向量從而使接收節(jié)點(diǎn)解碼失敗。對(duì)于可行的多播網(wǎng)絡(luò)，帶有獨(dú)立或線性相關(guān)的源，當(dāng)所有的系數(shù)都在

73、有限域中獨(dú)立隨機(jī)地選擇時(shí)，所有的接收節(jié)點(diǎn)都能夠解碼出信息的可能性至少是，其中d是接收節(jié)點(diǎn)的個(gè)數(shù)，q是系數(shù)選擇的范圍即字母表的大小，v是滿足以下條件的邊的最大數(shù)量，該條件為：邊上傳遞的信息來(lái)自所有源節(jié)點(diǎn)，同時(shí)可將信息傳到任何一個(gè)接收節(jié)點(diǎn)。</p><p>　　由此可見(jiàn)，網(wǎng)絡(luò)傳輸?shù)氖÷逝c網(wǎng)絡(luò)的尺寸成反比，傳輸失敗率與編碼之后碼字的長(zhǎng)度成指數(shù)關(guān)系減少。這樣只要根據(jù)網(wǎng)絡(luò)的大小和信息多少，估算出傳輸需要的中間邊的數(shù)量就可

74、以適當(dāng)?shù)倪x擇合適的字母表大小，在網(wǎng)絡(luò)的穩(wěn)定性與網(wǎng)絡(luò)傳播冗余量之間作出選擇。對(duì)于線性相關(guān)的網(wǎng)絡(luò)，這種算法也不需要源節(jié)點(diǎn)知道其他源節(jié)點(diǎn)的信息。與傳統(tǒng)路由方法相比，對(duì)于源節(jié)點(diǎn)增加減少和網(wǎng)絡(luò)拓?fù)涞淖兓葐?wèn)題，隨機(jī)網(wǎng)絡(luò)編碼更加靈活。</p><p><b>　　2.3 本章小結(jié)</b></p><p>　　本章闡述了網(wǎng)絡(luò)編碼的概念、原理，并且對(duì)幾種常見(jiàn)的網(wǎng)絡(luò)編碼的構(gòu)造方法做了歸

75、類，同時(shí)也分析了這幾種常見(jiàn)的網(wǎng)絡(luò)編碼方案的優(yōu)缺點(diǎn)，對(duì)當(dāng)前基于網(wǎng)絡(luò)編碼的無(wú)線傳輸技術(shù)研究作了綜述。</p><p>　　第3章 基于隨機(jī)網(wǎng)絡(luò)編碼的無(wú)線廣</p><p><b>　　播重傳方案的設(shè)計(jì)</b></p><p>　　無(wú)線廣播傳輸中，為了保證無(wú)線鏈路的可靠性，多個(gè)接收節(jié)點(diǎn)中任意一個(gè)節(jié)點(diǎn)丟失的信息包都要求源節(jié)點(diǎn)重新傳送數(shù)據(jù)包以實(shí)現(xiàn)差錯(cuò)控制

76、，需要較高的信道占用率和較多的重傳次數(shù)。本章針對(duì)無(wú)線傳輸中的廣播重傳問(wèn)題，研究了如何應(yīng)用網(wǎng)絡(luò)編碼的思想組合多個(gè)接收節(jié)點(diǎn)上的不同丟失信息包進(jìn)行重傳發(fā)送，提出了一種基于隨機(jī)網(wǎng)絡(luò)編碼的無(wú)線廣播重傳策略，該策略對(duì)傳輸信息包進(jìn)行分批重傳處理，采用隨機(jī)線性網(wǎng)絡(luò)編碼解碼的方法保證每一信息包批次內(nèi)的重傳可解性，相比起原有策略顯著的提高了重傳性能。盡管該策略需要對(duì)批次內(nèi)的信息包進(jìn)行延時(shí)等待，但重傳性能可以達(dá)到每個(gè)信息包批次內(nèi)的重傳最優(yōu)性。</p&g

77、t;<p>　　3.1 隨機(jī)網(wǎng)絡(luò)編碼的實(shí)現(xiàn)</p><p>　　在這一部分，我們首先介紹了隨機(jī)線性網(wǎng)絡(luò)編碼的基本思想，然后闡述了節(jié)點(diǎn)如何構(gòu)造隨機(jī)線性網(wǎng)絡(luò)編碼信息包的策略思想，最后分析了隨機(jī)線性網(wǎng)絡(luò)編碼包在接收節(jié)點(diǎn)的解碼操作和可解性條件。</p><p>　　絡(luò)中所有節(jié)點(diǎn)對(duì)其輸入信息進(jìn)行線性操作，稱為線性網(wǎng)絡(luò)編碼，如果線性系數(shù)是隨機(jī)產(chǎn)生的則稱為隨機(jī)線性網(wǎng)絡(luò)編碼。</p&

78、gt;<p>　　圖3-1說(shuō)明了普通傳輸方法與應(yīng)用隨機(jī)線性網(wǎng)絡(luò)編碼的傳輸方法的比較。如圖所示，節(jié)點(diǎn)R需要發(fā)送信息包，，。</p><p>　　圖3-1.a)表示傳統(tǒng)的發(fā)送方法：發(fā)送節(jié)點(diǎn)要逐一廣播待發(fā)送的信息包,,,接收節(jié)點(diǎn)也逐一接收各個(gè)信息包，完成節(jié)點(diǎn)間的數(shù)據(jù)傳輸過(guò)程。</p><p>　　圖3-1.b)表示應(yīng)用了隨機(jī)線性網(wǎng)絡(luò)編碼思想的信息包的傳輸方法。節(jié)點(diǎn)R不再僅具有存儲(chǔ)轉(zhuǎn)

79、發(fā)功能，而是具有編碼功能，其可以再一個(gè)有限域中選取隨機(jī)系數(shù)、、，通過(guò)編碼運(yùn)算得到、、三個(gè)編碼信息包，同時(shí)把隨機(jī)編碼系數(shù)、、寫入編碼組合包，節(jié)點(diǎn)R廣播逐一發(fā)送各編碼組合包。接收節(jié)點(diǎn)X和Y在完整接收到3個(gè)編碼組合包以后，將會(huì)獲得：</p><p><b>　　(3-1)</b></p><p><b>　　(3-2)</b></p>&

80、lt;p><b>　　(3-3)</b></p><p>　　節(jié)點(diǎn)X(或者節(jié)點(diǎn)Y)聯(lián)合式(3-1)、式(3-2)和式(3-3)，將得到一個(gè)包含三個(gè)方程的方程組，其中編碼系數(shù)、、在編碼組合包中為已知，三個(gè)方程有三個(gè)未知數(shù)(,,)，具有可解性，節(jié)點(diǎn)X(或者節(jié)點(diǎn)Y)可以通過(guò)解方程組運(yùn)算操作解出原始信息包,,。</p><p>　　用隨機(jī)線性網(wǎng)絡(luò)編碼方法，接收節(jié)點(diǎn)處理的

81、問(wèn)題由是否收到完整信息包數(shù)據(jù)，轉(zhuǎn)換為是否收到足夠多的滿足可解性條件的編碼包。通過(guò)研究人們發(fā)現(xiàn)，隨機(jī)線性編碼組合發(fā)送可以帶來(lái)良好的吞吐量、魯棒性、安全性等方面的增益，為網(wǎng)絡(luò)性能的改善提供了一種新的途徑。</p><p>　　3.2 無(wú)線廣播重傳模型的建立</p><p>　　無(wú)線廣播重傳策略的設(shè)計(jì)需要一個(gè)接近現(xiàn)實(shí)環(huán)境的無(wú)線廣播重傳模型。</p><p>　　我假設(shè)一

82、個(gè)具有一個(gè)廣播源節(jié)點(diǎn)和(,本課題設(shè)計(jì)的是)個(gè)接收節(jié)點(diǎn)的無(wú)線廣播網(wǎng)絡(luò)，廣播源節(jié)點(diǎn)和接收節(jié)點(diǎn)之間的傳輸鏈路存在損耗。</p><p>　　假設(shè)1 傳輸信息包長(zhǎng)度相同，廣播源以固定時(shí)間間隔()廣播傳送信息包(本課題設(shè)計(jì)的是有10個(gè)待發(fā)送的信息包)，廣播源節(jié)點(diǎn)和(,本課題設(shè)計(jì)的是)個(gè)接收節(jié)點(diǎn)之間的傳輸丟包率互不相關(guān)，且服從伯努利分布，對(duì)應(yīng)某個(gè)接收節(jié)點(diǎn)()的丟包率為。</p><p>　　假設(shè)2

83、 廣播源傳輸中某個(gè)信息包發(fā)送完畢后，(,本課題設(shè)計(jì)的是)個(gè)接收節(jié)點(diǎn)發(fā)送ACK／NAK控制信息包反饋該信息包的丟失隋況。丟失情況包括：(1)信息包是否成功接收；(2)丟失信息包序列號(hào)和丟失節(jié)點(diǎn)序列號(hào)。假定ACK／NAK控制信息包在信道中不存在損耗。ACK/NAK中包含丟失包的序列號(hào)與接收節(jié)點(diǎn)序列號(hào)。</p><p>　　假設(shè)3 (,本課題設(shè)計(jì)的是)個(gè)接收節(jié)點(diǎn)的丟失情況記錄在一個(gè)廣播接收狀態(tài)矩陣中。矩陣中行表示接收

84、節(jié)點(diǎn)的接收情況，列表示信息包接收情況。接收成功相應(yīng)位置賦值為0，否則賦值為1。</p><p>　　3.3 隨機(jī)線性網(wǎng)絡(luò)編碼包的構(gòu)造</p><p>　　在編碼中，把信息看作是特定基域上的向量，假定每一個(gè)信息包等長(zhǎng)為比特(當(dāng)參與編碼的信息包的長(zhǎng)度低于比特時(shí)，通過(guò)補(bǔ)0來(lái)實(shí)現(xiàn)同樣長(zhǎng)度)，由編碼運(yùn)算中的有限域封閉計(jì)算理論，線性網(wǎng)絡(luò)編碼包的長(zhǎng)度同樣為比特。</p><p>

85、;　　圖4-2為隨機(jī)線性網(wǎng)絡(luò)編碼的構(gòu)造描述，其中假定源節(jié)點(diǎn)傳輸中將要發(fā)送這10個(gè)原始信息包。 </p><p>　　在隨機(jī)線性網(wǎng)絡(luò)編碼包構(gòu)造中，網(wǎng)絡(luò)節(jié)點(diǎn)均是在有限域上隨機(jī)的選取線性編碼系數(shù)。Ho等人在文獻(xiàn)中證明，若隨機(jī)編碼系數(shù)都在有限域中獨(dú)立隨機(jī)地選擇時(shí)，當(dāng)有限域字母表足夠大時(shí)，系數(shù)選取出現(xiàn)線性無(wú)關(guān)的概率會(huì)越來(lái)越小。而且，在普通的隨機(jī)線性編碼傳輸中，選取的字母表時(shí)即可以保證出現(xiàn)線性無(wú)關(guān)的概率忽略不計(jì)。</p

86、><p>　　如圖4-2所示，在源節(jié)點(diǎn)需要構(gòu)造隨機(jī)線性網(wǎng)絡(luò)編碼時(shí)，源節(jié)點(diǎn)隨機(jī)選取線性編碼系數(shù)，將編碼系數(shù)和原始信息包進(jìn)行有限域運(yùn)算獲得隨機(jī)線性網(wǎng)絡(luò)編碼包數(shù)據(jù)，對(duì)應(yīng)編碼數(shù)據(jù)為：</p><p><b>　　(3-4)</b></p><p>　　若用分別表示隨機(jī)線性網(wǎng)絡(luò)編碼包中對(duì)應(yīng)的編碼系數(shù)，如表示中對(duì)應(yīng)的原始信息包的系數(shù)，則隨機(jī)線性網(wǎng)絡(luò)編碼包中對(duì)應(yīng)

87、的系數(shù)向量為：</p><p><b>　　(3-5)</b></p><p>　　在隨機(jī)線性網(wǎng)絡(luò)編碼包構(gòu)造中，源節(jié)點(diǎn)通過(guò)編碼運(yùn)算獲得編碼信息包以及相應(yīng)的系數(shù)向量，并發(fā)送相應(yīng)的到傳輸鏈路中。</p><p>　　3.4 編碼可解性的證明</p><p>　　當(dāng)接收節(jié)點(diǎn)收到來(lái)自傳輸鏈路的關(guān)于原始信息包的若干個(gè)隨機(jī)線網(wǎng)絡(luò)編

88、碼包，接收節(jié)點(diǎn)對(duì)應(yīng)有：</p><p><b>　　(3-6)</b></p><p>　　當(dāng)接收節(jié)點(diǎn)獲得式(3-6)的個(gè)編碼信息包，隨機(jī)線性網(wǎng)絡(luò)編碼包的解碼問(wèn)題即可以轉(zhuǎn)換為如何在個(gè)關(guān)于的線性組合中具有可解性的問(wèn)題。由矩陣論中關(guān)于線性方程組具有可解性的定理可知，只有當(dāng)式(3-6)中個(gè)線性組合中線性無(wú)關(guān)的線性方程組個(gè)數(shù)大于未知變量的個(gè)數(shù)10時(shí)，線性方程組才具有可解性。&

89、lt;/p><p>　　同時(shí)，式(3-6)中m個(gè)編碼信息包對(duì)應(yīng)原始信包的系數(shù)向量為：</p><p><b>　　(3-7)</b></p><p>　　由矩陣論可知，系數(shù)向量的秩即線性組合中線性無(wú)關(guān)的線性方程組個(gè)數(shù)，當(dāng)時(shí)，隨機(jī)線性網(wǎng)絡(luò)編碼包組合具有可解性，可以通過(guò)解碼操作解出原始信息包。</p><p>　　當(dāng)目的節(jié)點(diǎn)收到

90、的編碼信息包滿足可解性定理，即組成的系數(shù)向量的秩時(shí)，對(duì)應(yīng)有：</p><p><b>　　(3-8)</b></p><p>　　隨機(jī)線性網(wǎng)絡(luò)編碼組合的解碼操作即在式(3-8)中通過(guò)收到的編碼信息包組合和系數(shù)向量解出即：</p><p><b>　　(3-9)</b></p><p>　　接收節(jié)點(diǎn)通

91、過(guò)對(duì)滿足可解性的系數(shù)向量運(yùn)算或得，通過(guò)式(3-9)可以解碼運(yùn)算獲得原始信息包，完成解碼操作。</p><p>　　3.5 信息包的分批重傳</p><p>　　為將隨機(jī)線性網(wǎng)絡(luò)編碼應(yīng)用于無(wú)線重傳策略中達(dá)到重傳最優(yōu)性，我們需要采用與傳重傳處理機(jī)制不同的處理機(jī)制。</p><p>　　信息包分批的重傳處理機(jī)制的核心思想是將全部信息包分批成若干個(gè)信息包批次，將全部信息包

92、的重傳問(wèn)題轉(zhuǎn)換為若干個(gè)信息包批次的重傳問(wèn)題。</p><p>　　假設(shè)全部參與傳輸?shù)男畔膫€(gè)數(shù)為，假定分批中將每個(gè)信息包視為一個(gè)信息包批次，則全部的信息包可以轉(zhuǎn)換為個(gè)信息包批次的情況(若不為整數(shù)，可以補(bǔ)零)，此時(shí)全部的個(gè)信息包的重傳問(wèn)題變成了個(gè)信息包批次的重傳問(wèn)題。圖3-4 給出了信息包分批處理的描述。</p><p>　　在圖3-4中，全部參與傳輸?shù)男畔鼈€(gè)數(shù)。若取每個(gè)信息包分批構(gòu)成一

93、個(gè)信息包批次，此時(shí)全部的信息包可以分成個(gè)信息包批次。因而，全部參與傳輸44個(gè)信息包的重傳問(wèn)題就轉(zhuǎn)換成個(gè)信息包批次的重傳問(wèn)題。本課題只考慮一個(gè)信息包批次的重傳，信息包批次內(nèi)含有10個(gè)信息包。</p><p>　　3.6 具體重傳過(guò)程</p><p>　　由3.4節(jié)的信息包分批重傳處理機(jī)制描述，全部傳輸信息包的廣播重傳問(wèn)題可以表示若干個(gè)信息包批次的廣播重傳問(wèn)題。此時(shí)，無(wú)線廣播重傳策略所需要解

94、決的問(wèn)題轉(zhuǎn)換成在一個(gè)固定長(zhǎng)度的信息包批次中如何實(shí)現(xiàn)重傳。</p><p>　　3.6.1 重傳方案描述 </p><p>　　應(yīng)用隨機(jī)線性網(wǎng)絡(luò)編碼的重傳策略的基本思想是源節(jié)點(diǎn)記錄針對(duì)信息包批次中多個(gè)接收節(jié)點(diǎn)上丟包最多的接收節(jié)點(diǎn)丟包數(shù)，再按照隨機(jī)線性網(wǎng)絡(luò)編碼的方法編碼組合該丟包數(shù)個(gè)線性網(wǎng)絡(luò)編碼包，然后再?gòu)V播發(fā)送編碼組合包，實(shí)現(xiàn)重傳。</p><p>　　為了便于理解

95、，圖3-5給出了一個(gè)信息包批次的隨機(jī)線性網(wǎng)絡(luò)編碼的重傳策略的示例。示例中有五個(gè)接收節(jié)點(diǎn)，一個(gè)信息包批次包含五個(gè)信息包，接收狀態(tài)矩陣中行表示接收節(jié)點(diǎn)的接收情況，列表示信息包接收情況。0表示信息成功接收，1表示信息接受失敗。</p><p>　　如圖3-5所示，廣播源節(jié)點(diǎn)首先逐一廣播發(fā)送么信息包。發(fā)送后，接收節(jié)點(diǎn)，丟失信息包；接收節(jié)點(diǎn)丟失信息包；接收節(jié)點(diǎn)丟失信息包；接收節(jié)點(diǎn)丟失信息包；接收節(jié)點(diǎn)丟失信息包。需要應(yīng)用重傳

96、來(lái)實(shí)現(xiàn)差錯(cuò)控制。</p><p>　　差錯(cuò)控制應(yīng)用普通重傳策略，廣播源節(jié)點(diǎn)需要分別逐一廣播重傳1、2、2、3、4、5五個(gè)信息包，在不存在重傳丟失的情況下，需要廣播源節(jié)點(diǎn)廣播重傳5次。差錯(cuò)控制應(yīng)用隨機(jī)線性網(wǎng)絡(luò)編碼的重傳策略，五個(gè)信息包看成一個(gè)信息包批次，廣播源節(jié)點(diǎn)參照全局的接收節(jié)點(diǎn)丟包情況進(jìn)行隨機(jī)線性網(wǎng)絡(luò)編碼處理。在該例中，五個(gè)接收節(jié)點(diǎn)中，接收節(jié)點(diǎn)均丟失2個(gè)信息包；接收節(jié)丟失1個(gè)信息包。最大的單個(gè)接收節(jié)點(diǎn)丟失信息包

97、個(gè)數(shù)為2。這樣，源節(jié)點(diǎn)可以通過(guò)隨機(jī)線性網(wǎng)絡(luò)編碼構(gòu)造方法計(jì)算得到：</p><p><b>　　(3-10)</b></p><p><b>　　(3-11)</b></p><p>　　將隨機(jī)線性網(wǎng)絡(luò)編碼系數(shù)和附帶到編碼組合包中，將隨機(jī)線性網(wǎng)絡(luò)編碼包廣播重傳。這樣，接收節(jié)點(diǎn)，在收到編碼組合包后，由于接收節(jié)點(diǎn)，有信息包，而且

98、接收到的中包含有和，則通過(guò)將編碼系數(shù)和的值代入式(3-10)得：</p><p><b>　　(3-12)</b></p><p><b>　　(3-13)</b></p><p>　　由式(3-12)、(3-13)得：</p><p><b>　　(3-14)</b><

99、/p><p><b>　　(3-15)</b></p><p>　　在式(3-12)和(3-13)中，由于網(wǎng)絡(luò)編碼系數(shù)是已知的，，二個(gè)線性方程二個(gè)未知參數(shù)具有編碼可解性，可以轉(zhuǎn)換為式(3-14)式(3-15)的形式，代入已知值，解出丟失包。</p><p>　　同理節(jié)點(diǎn)可解出丟失包；節(jié)點(diǎn)可解出丟失包；節(jié)點(diǎn)可解出丟失包；節(jié)點(diǎn)可解出丟失包。隨機(jī)線性網(wǎng)絡(luò)

100、編碼包在所有接收節(jié)點(diǎn)具有可解性，可達(dá)到重傳目的。在不存在重傳丟失的情況下，應(yīng)用隨機(jī)線性網(wǎng)絡(luò)編碼的重傳方案只需要廣播源節(jié)點(diǎn)廣播重傳2次。提高了重傳效率，減少了重傳次數(shù)。</p><p>　　3.6.2 實(shí)際重傳方案描述 </p><p>　　由3.4節(jié)的信息包分批重傳處理機(jī)制描述，全部傳輸信息包的廣播重傳問(wèn)題可以表示若干個(gè)信息包批次的廣播重傳問(wèn)題。此時(shí)，無(wú)線廣播重傳策略所需要解決的問(wèn)題轉(zhuǎn)換

101、成在一個(gè)固定長(zhǎng)度的信息包批次中如何實(shí)現(xiàn)重傳。本課題實(shí)驗(yàn)是廣播源節(jié)點(diǎn)傳輸發(fā)送10個(gè)信息包，信息包數(shù)據(jù)位等長(zhǎng)，這10個(gè)信息包為一個(gè)信息包批次。實(shí)驗(yàn)中有5個(gè)接收節(jié)點(diǎn)。</p><p>　　普通的傳輸過(guò)程的流程圖為：</p><p>　　應(yīng)用網(wǎng)絡(luò)編碼的過(guò)程得流程圖：</p><p>　　在圖(3-6)中，為一的矩陣，其中存放的是待發(fā)送的信息包。是一個(gè)隨機(jī)產(chǎn)生的(0,1)矩陣

102、，且0,1比例可以改變。模擬信道傳輸時(shí)信息接收的隨機(jī)性。為5個(gè)接收節(jié)點(diǎn)的接收矩陣，其是的矩陣，前10列存放各信息包的系數(shù)，最后一列存放的是各信息包。為反饋矩陣，存放著各個(gè)信息包的接收情況。為接收狀態(tài)矩陣，矩陣中行表示接收節(jié)點(diǎn)的接收情況，列表示信息包接收情況。接收成功相應(yīng)位置賦值為0，否則賦值為1。起到計(jì)數(shù)的作用，表示到接收節(jié)點(diǎn)全部接收為止源節(jié)點(diǎn)一共發(fā)送信息包的次數(shù)。為再一次沖傳中源節(jié)點(diǎn)需要發(fā)送信息包的最大次數(shù)。</p>&

103、lt;p>　　圖(3-7)為普通重傳的流程圖。其沒(méi)有網(wǎng)絡(luò)編碼模塊，僅僅是諸葛發(fā)送丟失的信息包。也起到計(jì)數(shù)的作用，表示到接收節(jié)點(diǎn)全部接收為止源節(jié)點(diǎn)一共發(fā)送信息包的次數(shù)。</p><p>　　在傳統(tǒng)的無(wú)線鏈路傳輸中，反饋狀態(tài)報(bào)告為，報(bào)告內(nèi)容為某個(gè)傳輸信息包是否成功接收。</p><p>　　使用隨機(jī)線性網(wǎng)絡(luò)編碼策略的信息包重傳處理機(jī)制中，發(fā)送端發(fā)送的不再是單個(gè)的信息包，而是信息包批次。此

104、時(shí)，接收狀態(tài)報(bào)告需要進(jìn)行重新定義。</p><p>　　在傳統(tǒng)的無(wú)線鏈路傳輸中，編碼緩存為，緩存內(nèi)容為信息包的接收情況與一共丟失的信息包的個(gè)數(shù)。</p><p>　　使用隨機(jī)線性網(wǎng)絡(luò)編碼策略的信息包重傳處理機(jī)制中，編碼緩存為,存放著信息報(bào)批次序列號(hào)，此批次中信息包的接收情況，丟失信息包數(shù)量最多的節(jié)點(diǎn)的丟包數(shù)。</p><p>　　在傳統(tǒng)的無(wú)線鏈路傳輸中，源節(jié)點(diǎn)直接重

105、傳丟失的信息包。</p><p>　　使用隨機(jī)線性網(wǎng)絡(luò)編碼策略的信息包重傳處理機(jī)制中，編碼組合包存放的是信息包批次號(hào)，此批次中各信息包的隨機(jī)線性編碼系數(shù)和待發(fā)送的信息內(nèi)容。</p><p>　　下面給出了應(yīng)用隨機(jī)線性網(wǎng)絡(luò)編碼的無(wú)線廣播重傳策略的編碼算法步驟:</p><p>　　步驟1.根據(jù)狀態(tài)接收矩陣，尋找接收狀態(tài)矩陣中存在1的列位置，編碼緩存矩陣為一個(gè)矩陣，若某

106、列不存在1，則中對(duì)應(yīng)的位置0，否則置1，尋找中行中1個(gè)數(shù)的最大值。</p><p>　　步驟2.在廣播源節(jié)點(diǎn)進(jìn)行隨機(jī)線性網(wǎng)絡(luò)編碼操作，選取和編碼個(gè)編碼包。隨機(jī)線性編碼系數(shù)是從有限域中獨(dú)立選取的。將中各元素與發(fā)送的各信息相乘再乘以隨機(jī)編碼系數(shù)構(gòu)成編碼組合包存入編碼矩陣中準(zhǔn)備發(fā)送。</p><p>　　步驟3. 重的編碼組合包與隨機(jī)產(chǎn)生的出現(xiàn)概率一定的（0，1）序列模擬信道傳輸過(guò)程中接受節(jié)點(diǎn)接

107、收信息的隨機(jī)性。</p><p>　　步驟4.將信息傳遞給各接收節(jié)點(diǎn)，接收節(jié)點(diǎn)根據(jù)自身丟包情況接收各編碼組合信息包，將其存貯在丟失的信息包的位置上。</p><p>　　步驟5.接收結(jié)點(diǎn)根據(jù)接收到的信息包和編碼組合信息包解出丟失的信息包。</p><p>　　步驟6.接收節(jié)點(diǎn)反饋信息包的接收情況 </p><p>　　步驟7.在執(zhí)行步驟1，直

108、到接收節(jié)點(diǎn)全部接收成功為止。</p><p>　　3.6.3 重傳機(jī)制的描述 </p><p>　　綜合隨機(jī)線性網(wǎng)絡(luò)編碼策略的狀態(tài)報(bào)告包定義、隨機(jī)線性編碼重傳包定義和隨機(jī)線性網(wǎng)絡(luò)編碼策略的源節(jié)點(diǎn)編碼策略，參照現(xiàn)有的重傳機(jī)制，可以給出隨機(jī)線性網(wǎng)絡(luò)編碼策略的重傳處理機(jī)制。</p><p>　　接收端上的節(jié)點(diǎn)，可以根據(jù)信息接收情況，獲得該節(jié)點(diǎn)在對(duì)序列為的信息包批次的丟包

109、數(shù)，并將該數(shù)值記錄在狀態(tài)報(bào)告包中發(fā)送到發(fā)送端，發(fā)送端在延時(shí)時(shí)間后獲得所有接收節(jié)點(diǎn)的狀態(tài)報(bào)告，執(zhí)行隨機(jī)線性網(wǎng)絡(luò)編碼策略的源節(jié)點(diǎn)編碼策略，發(fā)送隨機(jī)線性網(wǎng)絡(luò)編碼重傳包。接收端在收到隨機(jī)線性網(wǎng)絡(luò)編碼重傳包后執(zhí)行解碼操作解出丟失數(shù)據(jù)，完成重傳。圖3-13給出了該處理機(jī)制的描述。</p><p>　　圖3-13中，發(fā)送端發(fā)送信息包批次、、，接收端的多個(gè)接收節(jié)點(diǎn)將信息包批次的狀態(tài)報(bào)告、、反饋給發(fā)送端，發(fā)送端根據(jù)隨機(jī)線性網(wǎng)絡(luò)編碼

110、策略的源節(jié)點(diǎn)編碼策略，發(fā)送重傳編碼包完成重傳。</p><p><b>　　3.7 本章小結(jié)</b></p><p>　　本章提出了一種應(yīng)用隨機(jī)線性網(wǎng)絡(luò)編碼的無(wú)線廣播重傳策略。首先建立了無(wú)線廣播重傳模型，構(gòu)造了隨即網(wǎng)絡(luò)編碼包，具體的描述了重傳過(guò)程以及重傳機(jī)制。</p><p>　　第4章 應(yīng)用隨機(jī)線形網(wǎng)絡(luò)編碼性能分析</p>&

111、lt;p>　　4.1 數(shù)學(xué)理論分析</p><p>　　本節(jié)通過(guò)數(shù)學(xué)分析給出普通重傳方法和隨機(jī)線性網(wǎng)絡(luò)編碼方法重傳性能比較．衡量參數(shù)為信息包的平均傳輸次數(shù)。</p><p>　　文獻(xiàn)[6]中給出了普通重傳方法在廣播接收節(jié)點(diǎn)個(gè)數(shù)為情況下的平均傳輸次數(shù)：</p><p>　　其中 (4-1)</p><p>　　若無(wú)線網(wǎng)絡(luò)廣播重傳