基于網(wǎng)絡編碼的無線廣播重傳方案的研究畢業(yè)論文

1、本科畢業(yè)設計（論文）基于網(wǎng)絡編碼的無線廣播重傳方案的研究2011年6月本科畢業(yè)設計（論文）基于網(wǎng)絡編碼的無線廣播重傳方案的研究學 院： 專 業(yè)： 學生姓名： 學 號： 指導教師： 答辯日期：2011-6-25 xx大學畢業(yè)設計（論文）任務書學院： 系級教學單位： 學號學生姓名專 業(yè)班 級題目題目名稱基于網(wǎng)絡編碼的無線廣播重傳方案的研究題目性質(zhì)1.理工類：工程設計 （ ）；工程技術(shù)實驗研究型（ ）；理論研究型（ ）；計算機軟件型（ ）；綜合型（ ）2.文管理類（ ）；3.外語類（ ）；4.藝術(shù)類（ ）題目類型1.畢業(yè)設計（ ） 2.論文（ ）題目來源科研課題（ ） 生產(chǎn)實際（ ）自選題目（ ）

2、主要內(nèi)容 重傳是無線網(wǎng)絡廣播傳輸中實現(xiàn)錯誤處理的重要技術(shù)。普通重傳方法通常逐一發(fā)送丟失包來進行錯誤處理。本課題研究網(wǎng)絡編碼在無線廣播重傳中的應用，設計一種適用于單源多宿無線廣播網(wǎng)絡的、基于網(wǎng)絡編碼的重傳方案，從而利用網(wǎng)絡編碼的特性，降低重傳次數(shù)，提高傳輸特性。利用matlab對所設計方案進行仿真實驗?；疽?通過學習相應書籍和查閱資料，熟悉隨機線性網(wǎng)絡編碼的基本理論2了解現(xiàn)有的無線廣播數(shù)據(jù)重傳方案。3設計出一種基于網(wǎng)絡編碼的重傳方案4基于matlab仿真，分析方案性能。參考資料1網(wǎng)絡編碼理論與技術(shù) 楊義先主編 國防工業(yè)出版社 20092高損耗無線網(wǎng)絡中基于網(wǎng)絡編碼的廣播重傳策略，中南大學學報

3、(自然科學版)，2008，39(6)3一種低丟包率無線網(wǎng)絡中基于網(wǎng)絡編碼的廣播重傳方法 小型微型計算機系統(tǒng)2009，30(6)4中國期刊網(wǎng)上的關(guān)于網(wǎng)絡編碼的文章周 次第1 4 周第5 8 周第 912 周第1316 周第17 18 周應完成的內(nèi)容收集資料熟悉課題內(nèi)容確定設計思路熟悉程序設計語言，確定算法的實現(xiàn)方案編寫程序?qū)崿F(xiàn)設計方案上機調(diào)試并進行優(yōu)化實驗結(jié)果整理和總結(jié)撰寫論文課題總結(jié)答辯指導教師：職稱： 2011年 2 月28 日系級教學單位審批： 年 月 日摘要摘要在無線網(wǎng)絡廣播的重傳處理中，多個接收節(jié)點中的任意一個節(jié)點丟失信息包都要求源節(jié)點重傳數(shù)據(jù)包，這就需要源節(jié)點廣播發(fā)送較多的重傳次數(shù)。

4、本文將隨機線性網(wǎng)絡編碼技術(shù)應用在無線網(wǎng)絡廣播重傳中，設計了一種基于隨機線性網(wǎng)絡編碼的無線廣播重傳方案。在該方案中，源節(jié)點需記錄多個接收節(jié)點中丟失信息包的數(shù)量最多的接收節(jié)點的丟包數(shù)量，再按照隨機線性網(wǎng)絡編碼的方法編碼組合該丟包數(shù)量個線性編碼信息包；源節(jié)點廣播重傳線性編碼組合包；接收節(jié)點采用運算編碼線性組合的方法獲得信息包數(shù)據(jù)。數(shù)學分析表明，該方法能保證所有接收節(jié)點的編碼可解性，同時重傳次數(shù)可達到理論最優(yōu)性；模擬測試結(jié)果表明：與傳統(tǒng)重傳方法相比，應用隨機線性網(wǎng)絡編碼的重傳方案有效地減少了信息包的平均傳輸次數(shù)，提高了傳輸效率關(guān)鍵詞無線廣播；網(wǎng)絡編碼；隨機線性網(wǎng)絡編碼；重傳i 燕山大學本科生畢業(yè)設計（

5、論文）abstractin wireless broadcasting retransmission, any node of multi-nodes request the retransmission of information packets. this approach always needs large mounts of broadcasting packets. this paper designs an approach in wireless broadcasting networks based on random linear network coding. firs

6、tly, source node will send linear coding packets based on the largest mounts of lost packets in received nodes. then, received nodes will decode lost packets with network coding theory mathematic analysis reveals that our approach can ensure the solvability in the received nodes, and have optimizati

7、on performance in wireless retransmission. simulation results indicate that compared with existing approach; the approach in this paper can effectively reduce the average number of transmissions and advance the transmission efficiencykeywordswireless broadcasting; network coding; random linear netwo

8、rk coding; retransmissioni 目 錄摘要iabstractii第1章 緒論11.1 課題背景及意義11.2 本課題國內(nèi)外的研究現(xiàn)狀21.3 本課題研究的主要內(nèi)容41.4 本文的章節(jié)安排4第2章 基于網(wǎng)絡編碼的無線傳輸?shù)姆治?2.1 網(wǎng)絡編碼的概念與定義62.1.1 網(wǎng)絡編碼的基本原理62.1.2 最大流-最小割定理82.2 幾種常見的網(wǎng)絡編碼構(gòu)造方法102.2.1 網(wǎng)絡編碼的前提假設102.2.2 線性向量編碼122.2.3 線性代數(shù)編碼132.2.4 隨機網(wǎng)絡編碼162.3 本章小結(jié)18第3章 基于隨機網(wǎng)絡編碼的重傳方案的設計193.1 隨機網(wǎng)絡編碼的實現(xiàn)193.2

9、無線廣播重傳模型的建立213.3 隨機線性網(wǎng)絡編碼包的構(gòu)造223.4 編碼可解性的證明233.5 信息包的分批重傳243.6 重傳機制的描述253.7 具體重傳過程263.7.1 重傳方案描述263.7.2 實際重傳方案描述283.8 本章小結(jié)32第4章 應用隨機線性網(wǎng)絡編碼性能分析334.1 數(shù)學理論分析334.2 模擬測試分析334.3 本章小結(jié)35結(jié)論36參考文獻37致謝39i第1章 緒論 第1章 緒論近年來，隨著無線技術(shù)的成熟，越來越多的人通過無線方式連接到互聯(lián)網(wǎng)上。與此同時，由于用戶數(shù)量的陡然增多、用戶對網(wǎng)絡服務需求的多樣性以及用戶對傳輸質(zhì)量要求的不斷提高，如何保障無線鏈路的可靠安全

10、傳輸、優(yōu)化無線網(wǎng)絡性能、在現(xiàn)有網(wǎng)絡資源的基礎上提高網(wǎng)絡資源的利用率等問題已成為當今無線網(wǎng)絡通信研究的重要課題之一。1.1 課題背景及意義數(shù)據(jù)廣播業(yè)務在蜂窩網(wǎng)絡和無線mesh網(wǎng)絡中的應用越來越廣泛，自動重復重傳(automatic repeat request, arq)已經(jīng)成為無線通信環(huán)境下的提供可靠通信的重要容錯手段。普通的自動重復重傳機制主要包括：停止-等待自動重復重傳(sw-arq)、返回n型自動重復重傳(gbn-arq)和選擇自動重復重傳(sr-arq)1。盡管自動重復重傳應用于點對點傳輸確實可以達到較高的傳輸性能，然而對于多用戶的廣播、組播傳輸，其性能會隨接收節(jié)點數(shù)目的增加而迅速下降

11、2。2000年，香港中文大學的a. rhlswede等基于網(wǎng)絡流的概念率先提出了網(wǎng)絡編碼3這一概念，其精髓來源于著名的max-flow min-cut（最大流最小割）理論4。網(wǎng)絡編碼是指網(wǎng)絡節(jié)點既實現(xiàn)路由功能又實現(xiàn)編碼功能。利用無線信道的廣播特性，網(wǎng)絡編碼被應用于提高無線網(wǎng)絡性能、提高吞吐量、安全性等。同時網(wǎng)絡編碼也為無線廣播重傳提供了一種途徑。2006年，nguyen等人將網(wǎng)絡編碼技術(shù)應用于重傳策略中，提出了兩個接收節(jié)點的編碼重傳策略，減少了平均傳輸次數(shù)，但nguyen等人的策略僅考慮了兩個接收節(jié)點的情況且沒有提出具體的編碼方案。網(wǎng)絡廣播中應用普通的重傳策略，在較高的出錯率的情況下會產(chǎn)生兩個

12、方面的問題5：廣播傳輸中丟失信息包較多，需要數(shù)量較大的重傳次數(shù)；重傳信息包再次丟失，需要次數(shù)較大的再次重傳。因此如何利用現(xiàn)有的網(wǎng)絡資源來提高重傳效率成為研究的熱點。現(xiàn)在推廣到多個接收節(jié)點的情況下，將網(wǎng)絡編碼與廣播重傳相結(jié)合以減少重傳次數(shù)、提高重傳效率。因此，研究將網(wǎng)絡編碼應用于單源多宿的無線廣播網(wǎng)絡中以降低重傳次數(shù)是很有必要的。1.2 本課題國內(nèi)外的研究現(xiàn)狀無線傳輸中的廣播信道特性，使得網(wǎng)絡編碼在減少無線傳輸次數(shù)方面有很好的應用，近年來出現(xiàn)了很多相關(guān)的研究。wu等人提出了利用網(wǎng)絡編碼減少信息包互換傳輸次數(shù)的方法6，bin等人提出了網(wǎng)絡編碼尋找無線mesh網(wǎng)最少傳輸次數(shù)路徑的思想。katti等人

13、構(gòu)造了無線mesh網(wǎng)絡使用網(wǎng)絡編碼的體系結(jié)構(gòu)cope，并利用29個節(jié)點的實驗平臺證實能顯著減少平均傳輸次數(shù)。chachulski等人則提出無線路由協(xié)議more，并證實該協(xié)議能有效減少信息包的平均發(fā)送次數(shù)。同時，與傳統(tǒng)的有線網(wǎng)絡相比，無線網(wǎng)絡擁有較高的比特出錯率，重傳效率問題顯得更加重要。目前的研究現(xiàn)狀來看，國外在無線傳輸技術(shù)中引入網(wǎng)絡編碼的研究起步較早。國外多所著名大學如麻省理工學院、普林斯頓大學、多倫多大學、瑞士epfl學院等和多家it公司的研究中心，包括微軟研究所、貝爾實驗室、at&t的香農(nóng)信息實驗室等都在積極開展相關(guān)的研究7。目前國外在無線傳輸技術(shù)中引入網(wǎng)絡編碼的研究主要側(cè)重在二

14、個方面：改善無線傳輸吞吐量和能量利用效率、保證無線鏈路的可靠傳輸和安全性。在無線傳輸吞吐量研究上，a.rhlswede等人指出網(wǎng)絡編碼可以達到組播傳輸理論最大流速；li等人kotter等人8先后證明線性網(wǎng)絡編碼、隨機網(wǎng)絡編碼同樣可以達到組播傳輸理論最大流速、并對網(wǎng)絡編碼的數(shù)學框架進行了闡述，為網(wǎng)絡編碼在無線組播傳輸吞吐量方面的研究提供了必要的理論條件。在能量利用效率方面，wu等人證明在無線網(wǎng)絡組播時應用網(wǎng)絡編碼，可以將最小化每位數(shù)據(jù)能量消耗問題歸結(jié)為線性問題，為能量利用效率方面的研究提供了基礎。kari等人證實了局部混合網(wǎng)絡編碼的傳輸，在tcp和udp傳輸流的環(huán)境下均可以顯著提高傳輸吞量；wu

15、等人接下來研究了基于局部混合網(wǎng)絡編碼互換傳輸?shù)男阅?，證明了互換傳輸可以優(yōu)化傳輸性能，這些研究均為局部混合網(wǎng)絡編碼傳輸提供了理論基礎和條件。無線網(wǎng)絡由于環(huán)境的多變性，使得數(shù)據(jù)包在傳輸中更加容易丟失，傳輸中的重傳技術(shù)研究非常必要。當前應用網(wǎng)絡編碼的重傳技術(shù)研究主要涉及二個接收節(jié)點情況下的編碼發(fā)送重傳。從目前的研究現(xiàn)狀來看，國內(nèi)在無線傳輸中引入網(wǎng)絡編碼的研究起步較晚，中科院軟件研究所、清華大學、中國科技大學、國防科技大學、上海交通大學、華中科技大學等高校均有相關(guān)的研究組進行該課題有關(guān)的領域研究。在無線組播傳輸性能研究、多源信息交換傳輸、p2p數(shù)據(jù)流傳輸、衛(wèi)星技術(shù)中的組播傳輸、無線網(wǎng)絡的動態(tài)網(wǎng)絡編碼協(xié)

16、助通信等方面，國內(nèi)均進行了相關(guān)的研究。從當前的國內(nèi)外研究情況來看，基于網(wǎng)絡編碼的無線傳輸技術(shù)的核心思想仍然是通過增加節(jié)點的編碼(計算)能力來換取網(wǎng)絡傳輸增益。一方面網(wǎng)絡編碼進行的運算復雜度相對來說較低，另一個方面來看，相比網(wǎng)絡傳輸增益，節(jié)點計算代價和延時是可以接受的。網(wǎng)絡編碼技術(shù)的提出只有10年的時間。a.rhlswede等人首先提出網(wǎng)絡編碼這個概念。他們的工作主要針對單個源點，多個接收點的信息傳輸問題，證明了在源點發(fā)送能力無限的情況下，一個網(wǎng)絡的最大信息傳送率等于該網(wǎng)絡的最小割的容量也就是網(wǎng)絡的最大流。將信息傳輸與圖論的最大流最小割理論聯(lián)系在一起。這也是第一次提出通信網(wǎng)絡的容量問題。a.rh

17、lswede等人僅給出了網(wǎng)絡最大信息傳送速率的存在性證明，并沒有給出具體的網(wǎng)絡編碼實現(xiàn)方式。li，yeung和cai提出單一源，多接收點網(wǎng)絡的最大傳輸速率可以通過線性編碼實現(xiàn)9。通過一個廣泛適的線性編碼多播算法(lcm)，每個接收節(jié)點都可以應用無線網(wǎng)絡編碼達到其最大流。lcm主要應用于非循環(huán)網(wǎng)絡。lcm規(guī)則為每條邊分配邊向量，每個節(jié)點分配向量空間。邊向量與點向量空間按照lcm規(guī)則滿足一定的關(guān)系通過邊向量和節(jié)點上的信息向量相乘對信息編碼，在接收節(jié)點處使用逆矩陣解碼。lcm方法可以達到任意節(jié)點的最大流。但由于lcm規(guī)則過于嚴格，尋找符合規(guī)則的向量需要大量的時間，造成了網(wǎng)絡的延時，因此lcm不適合用

18、在實際網(wǎng)絡中。koctter等人為網(wǎng)絡解碼設計了一個數(shù)學框架。它將一般的網(wǎng)絡編碼尋找線性解的方法簡化成為尋找多元多項式的非0解。同時尋找編碼系數(shù)的方法也通過代數(shù)編碼方式而簡化了。針對多播信息傳輸問題，ho等人設計了一種不需要知道網(wǎng)絡節(jié)點分布情況的隨機運算法則，通過在字母表中隨機選取系數(shù)實現(xiàn)網(wǎng)絡編碼。psanders等人提出了一種實現(xiàn)網(wǎng)絡編碼的多項式時間算法。這種方法將網(wǎng)絡編碼的構(gòu)造進一步簡化，它也是在己知拓撲的情況下，首先通過最大流最小割算法找到完成組播所需的路徑的集合，在找出的這個子圖上，再自上而下的確定各個節(jié)點所需要進行的操作。這種方法不但把網(wǎng)絡編碼構(gòu)造的復雜度從指數(shù)級降到了多項式級，而且

19、大大降低了網(wǎng)絡編碼中所采用的字母表的下限。另外，人們對網(wǎng)絡編碼在提高網(wǎng)絡性能方面的應用做了大量的研究。研究表明，網(wǎng)絡編碼除了能夠提高系統(tǒng)的容量外，在數(shù)據(jù)壓縮、負載均衡、降低節(jié)點能量消耗、減少傳播時延、提高網(wǎng)絡健壯性等方面都有重要的應用前景。1.3 本課題研究的主要內(nèi)容本課題的研究目標是結(jié)合網(wǎng)絡編碼的思想，設計應用于高傳輸損耗下的廣播重傳策略。傳輸損耗較嚴重的情況下無線廣播傳輸錯誤率高，必須使用重傳策略來進行錯誤處理。普通的重傳策略的思想在高損耗無線網(wǎng)絡廣播中會產(chǎn)生兩個方面的問題：丟失的信息包多需要較大的重傳次數(shù)；再次丟包率較高，需較大數(shù)量的再次重傳。因此，本課題研究單源節(jié)點、多個接收節(jié)點的情況

20、下，將網(wǎng)絡編碼應用于無線廣播重傳問題以提高重傳效率、減少重傳次數(shù)，為網(wǎng)絡編碼技術(shù)在實際無線傳輸環(huán)境中的應用提供良好的理論基礎。研究的主要內(nèi)容為：在了解網(wǎng)絡編碼原理的基礎，了解現(xiàn)有的無線廣播重傳方案。設計了一種基于隨機網(wǎng)絡編碼的無線廣播重傳方法。首先建立了一種接近現(xiàn)實環(huán)境的無線廣播重傳模型，構(gòu)造隨機線性編碼包，采用與傳統(tǒng)傳處理機制不同的處理機制即分批重傳信息包，以及具體的重傳步驟。1.4 本文的章節(jié)安排本文通過深入理解網(wǎng)絡編碼和無線網(wǎng)絡領域近年來的重要研究成果，對網(wǎng)絡編碼在無線傳輸網(wǎng)絡中的應用進行了深入的研究。設計了一種基于網(wǎng)絡編碼的無線廣播重傳方案，以減少重傳次數(shù)、提高重傳效率，各章的內(nèi)容組織

21、如下：第1章為緒論，主要介紹了應用網(wǎng)絡編碼的無線廣播傳輸技術(shù)的研究背景和意義、國內(nèi)外的研究現(xiàn)狀以及當前主要的研究成果，并對本文的主要工作進行了論述。第2章介紹了網(wǎng)絡編碼基本原理與最大流最小割定理，在此基礎上又進一步闡述了幾種常見的網(wǎng)絡編碼的構(gòu)造方法和它們的優(yōu)缺點。并從中選擇了隨機網(wǎng)絡編碼進行研究設計。第3章設計了一種基于隨機線性網(wǎng)絡編碼的重傳方案。首先建立了接近現(xiàn)實環(huán)境的無線廣播模型，構(gòu)造了隨機網(wǎng)絡編碼包，具體的描述了重傳過程以及重傳機制。第4章用表與圖兩種形式展現(xiàn)了接收節(jié)點在不同的丟包率的情況下應用隨機線性網(wǎng)絡編碼的重傳方法與傳統(tǒng)的方法在總的傳輸次數(shù)的比較，充分的證明了應用隨機線性網(wǎng)絡編碼的

22、重傳方法減少了重傳次數(shù)，提高了傳輸效率。35 第2章 基于網(wǎng)絡編碼的無線傳輸?shù)姆治?第2章 基于網(wǎng)絡編碼的無線傳輸?shù)姆治鼍W(wǎng)絡編碼從廣義上講是網(wǎng)絡中的節(jié)點將接收到的信息進行編碼后再轉(zhuǎn)發(fā)出去的多點傳送技術(shù)。網(wǎng)絡編碼理論徹底改變了傳統(tǒng)的存儲轉(zhuǎn)發(fā)性能，可以達到最大流傳輸?shù)睦碚摌O限。而隨機網(wǎng)絡編碼理論將網(wǎng)絡編碼的應用延伸到任意網(wǎng)絡結(jié)構(gòu)中。隨機網(wǎng)絡編碼在無線網(wǎng)絡中的應用更是因此得到了長足的發(fā)展。本章將首先介紹網(wǎng)絡編碼的基本理論，然后將引出隨機網(wǎng)絡編碼在無線網(wǎng)絡中的一般模型和方法為后續(xù)的章節(jié)的展開做好鋪墊2.1 網(wǎng)絡編碼的概念與定義 網(wǎng)絡編碼(network coding)是一種融合編碼和路由的信息交換技術(shù)

23、，在傳統(tǒng)存儲轉(zhuǎn)發(fā)路由方法基礎上，通過允許對接收的多個數(shù)據(jù)包進行信息編碼融合，增加單次傳輸?shù)男畔⒘?，提高網(wǎng)絡整體性能。網(wǎng)絡編碼的本質(zhì)是利用節(jié)點的計算能力提高鏈路帶寬的利用率10。2.1.1 網(wǎng)絡編碼的基本原理 xyzyxzxyzf1(x, y, z)f2(x, y, z)f3(x, y, z)節(jié)點n節(jié)點na) 傳統(tǒng)路由方法b) 網(wǎng)絡編碼的路由方法圖2-1 網(wǎng)絡編碼概念描述如圖2-1所示，節(jié)點是網(wǎng)絡中的一個節(jié)點，其收到來自不同鏈路的信息包、并需要對信息包進行傳輸發(fā)送處理。如圖2-1 a)所示在傳統(tǒng)的計算機網(wǎng)絡中，每個節(jié)點（可以是交換機或路由器），在存儲轉(zhuǎn)發(fā)模式下，節(jié)點只進行數(shù)據(jù)分組的路由和復制。而

24、不同于傳統(tǒng)網(wǎng)絡，具有網(wǎng)絡編碼功能的節(jié)點則會對數(shù)據(jù)包進行編碼/解碼運算，如圖2-1 b)，交換機輸出的信息流是其輸入的信息流的函數(shù)。采用傳統(tǒng)路由方法，節(jié)點僅需要對收到的信息包進行存儲和轉(zhuǎn)發(fā)，節(jié)點的發(fā)送信息包為、。采用網(wǎng)絡編碼，節(jié)點可以對收到的信息包進行編碼運算，通過運算信息包、獲得信息包、，新信息包是來自不同鏈路收到信息包的編碼組合。此時，若通過網(wǎng)絡編碼進行發(fā)送，節(jié)點實現(xiàn)了對接收的多個數(shù)據(jù)的編碼信息融合操作，即網(wǎng)絡編碼操作。傳統(tǒng)網(wǎng)絡的存儲轉(zhuǎn)發(fā)模式可看作網(wǎng)絡編碼的特例。為了便于網(wǎng)絡編碼理論的分析闡述，我們僅考慮組播情況并且建立相應的網(wǎng)絡模型，模型中假設邊的帶寬為單位容量，允許節(jié)點間存在多條邊，并忽

25、略邊的傳輸錯誤及延時。傳統(tǒng)網(wǎng)絡分析中，通信網(wǎng)絡中的信息流被認為是網(wǎng)絡管道中的流體，類似于水在渠道中流動一樣。對于一個實際的通信網(wǎng)絡，我們可以采用一個有向圖來加以描述和研究11。對于圖，這里表示節(jié)點的集合，表示邊的集合。網(wǎng)絡中一條邊用表示，這里，為網(wǎng)絡中的兩個節(jié)點。若圖僅有一個源節(jié)點和一個接收節(jié)點，且有向圖中的每一條邊對應著一個非負數(shù)，并令其為該邊的容量，則稱該有向圖為網(wǎng)絡流圖。對于網(wǎng)絡流圖每一條邊都給定一個非負數(shù)，這一組數(shù)滿足下列兩個條件時稱為這網(wǎng)絡的可行流，表示為： (2-1)(1)每一條邊,有。(2)除了源節(jié)點和接收節(jié)點 以外的所有的節(jié)點，恒有等式(2-2): (2-2)這表示中間節(jié)點的流

26、量是守恒的，即節(jié)點的輸入的流量和輸出的流量是相等的。(3)源節(jié)點和接收節(jié)點滿足公式(2-3): (2-3)其中稱作網(wǎng)絡流的流量，而且從源節(jié)點流出的總量等于流入接收節(jié)點的總量。當時便稱邊飽和，或飽和，表示流對該邊已飽和。該網(wǎng)絡的最大流是指從源節(jié)點送往接收節(jié)點的流量的最大值，用表示。設為節(jié)點集合的一個子集，使得s，把一個端點屬于而另一個端點不屬于的邊的集合稱作源節(jié)點和接收節(jié)點的一個割。割的容量的定義為集合中包含所有邊的容量的和，用表示，即式(2-4)： (2-4)2.1.2 最大流-最小割定理網(wǎng)絡編碼通過允許對來自不同鏈路的信息進行編碼組合，從而提高網(wǎng)絡性能，在這種全新的體系結(jié)構(gòu)下，網(wǎng)絡性能可以達

27、到最大流傳輸?shù)睦碚摌O限。最大流-最小割定理：對于已知的網(wǎng)絡流圖，從信源節(jié)點到接收節(jié)點的流量的最大值等于其最小割的容量，即式（2-5）： (2-5)對于有向網(wǎng)絡，可以用ford-fulkerson算法來求解網(wǎng)絡的最大流。對于網(wǎng)絡信息流，為一個多播網(wǎng)絡，為信息從信源到信宿的多播傳輸速率。令信源節(jié)點到接收節(jié)點的最大流值為，則對于所有的，有式(2-6)： (2-6)即 (2-7)將這個稱作網(wǎng)絡多播傳輸?shù)淖畲罅飨蕖Ｈ鐖D2-2所示，圖中給出了最大流最小割定理的一個實例，圖中從信源節(jié)點到接收節(jié)點的流量最大值等于信源節(jié)點到接收節(jié)點的最大割集，即有： (2-8)圖2-3所示的蝴蝶網(wǎng)絡12是網(wǎng)絡編碼實現(xiàn)最大流傳輸

28、的例子。圖中假設網(wǎng)絡中各條鏈路無差錯和無時延，源節(jié)點通過網(wǎng)絡將l比特信息和傳輸?shù)浇邮展?jié)點和，所有的鏈路容量均為l。satcb3242443圖2-2 最大流最小割定理實力由圖2-3 a)的網(wǎng)絡鏈路容量圖，可以得知： (2-9) 由最大流最小割定理有： (2-10)由圖論中的點對點的最大流最小割定理，對于已知的網(wǎng)絡流圖2-3 a)，從源節(jié)點到接收節(jié)點的流量的最大值小于或等于任何一個割切的容量，即源節(jié)點到接收節(jié)點,的最大傳輸速率小于或等于2。圖2-3 b)是使用傳統(tǒng)路由傳輸?shù)那闆r，節(jié)點一次只能傳送l比特的信息到節(jié)點，節(jié)點也只能傳送l比特的信息到接收節(jié)點和,節(jié)點和之間的鏈路不得不被使用了二次，接收節(jié)點

29、和總共收到3比特信息，平均的傳輸速率是1.5比特/單位時間。采用傳統(tǒng)路由傳輸?shù)那闆r，發(fā)送者達不到最大流限。圖2-3 c)是網(wǎng)絡編碼傳輸?shù)那闆r，這里采用異或(模2和)的編碼方案。中間節(jié)點輸入信息流進行編碼，將編碼的結(jié)果傳送到節(jié)點，再傳送給接收節(jié)點,。接收節(jié)點，根據(jù)自身己收到的信息和，可以通過解碼解出。同理，接收節(jié)點z也能通過解碼出的完整的信息，這樣所能達到的平均速率是2比特/單位時間，發(fā)送者可以達到網(wǎng)絡的最大流限。suvwdxzsuvwdxzsuvwdxz111111111ababaa/bbababaabbabababa) 網(wǎng)絡鏈路容量b) 傳統(tǒng)路由傳輸c) 網(wǎng)絡編碼傳輸圖2-3 經(jīng)典網(wǎng)絡編碼原

30、理圖2.2 幾種常見的網(wǎng)絡編碼構(gòu)造方法 在網(wǎng)絡傳輸中應用網(wǎng)絡編碼技術(shù)，在每個節(jié)點如何進行編碼組合，相應的網(wǎng)絡編碼構(gòu)造方法至關(guān)重要。如果網(wǎng)絡節(jié)點對傳輸?shù)男畔⑦M行線性操作, 則稱為線性網(wǎng)絡編碼,否則稱為非線性網(wǎng)絡編碼12。根據(jù)網(wǎng)絡編碼系數(shù)的選取，主要分為確定性網(wǎng)絡編碼和隨機網(wǎng)絡編碼。確定性網(wǎng)絡編碼中網(wǎng)絡節(jié)點對信息符號進行組合的系數(shù)是確定產(chǎn)生的，而隨機網(wǎng)絡編碼的組合系數(shù)通常隨機選取。本章介紹了幾種常見的網(wǎng)絡編碼構(gòu)造方式，這也是我們后面算法的基礎。2.2.1 網(wǎng)絡編碼的前提假設li等人提出，通用的網(wǎng)絡編碼方法可以通過簡單的線性運算實現(xiàn)，即節(jié)點的輸出信息流是輸入信息流的線性組合，因此這種編碼方法稱為線性

31、網(wǎng)絡編碼。下面介紹的幾種形式的網(wǎng)絡編碼都是基于這一簡單的思想，只是編碼的構(gòu)造過程不同。為了簡化計算我們要作如下假設13：(1)傳輸網(wǎng)絡是非循環(huán)網(wǎng)絡(2)容量為的路徑可以看作是條單位容量路徑的并聯(lián)。(3)網(wǎng)絡中不存在傳輸錯誤，只存在由于節(jié)點和鏈路的無效造成的信息丟失。(4)每條邊傳輸信號的時延相同。(5)多個源節(jié)點的網(wǎng)絡可以看成只有一個虛擬源節(jié)點的網(wǎng)絡。假設解釋：為了簡化問題的表示與描述，假定傳輸網(wǎng)絡中沒有環(huán)路的存在，這也是無時延網(wǎng)絡的前提條件；通過選擇一個非常小的單位容量，使每兩個節(jié)點中間都有整數(shù)條路徑連接。這樣在下面討論兩個節(jié)點之間的容量的時候就可以用兩個節(jié)點之間的單位路徑數(shù)量來衡量，而且單

32、位路徑在單位時間內(nèi)傳輸單位信息；假設理想情況，取消了網(wǎng)絡的同步要求。在后面我們會討論更實用的網(wǎng)絡編碼。 網(wǎng)絡可以通過一個虛擬源節(jié)點和一些虛擬鏈接14，使虛擬源節(jié)點含有所有實際的源節(jié)點所含有的信息，而將所有實際的源節(jié)點都轉(zhuǎn)化成傳輸網(wǎng)絡的中間節(jié)點。整個網(wǎng)絡就從多個源節(jié)點、多個接收節(jié)點的網(wǎng)絡轉(zhuǎn)化成為單個源節(jié)點、多接收節(jié)點的網(wǎng)絡。虛擬源的設置如圖2-4：ss1s2s3圖2-4 虛擬源節(jié)點虛擬的方法是，將網(wǎng)絡中實際的源節(jié)點看作是這個虛擬源節(jié)點連接的第一層接收節(jié)點。如果實際的源節(jié)點每次有個信息要傳送給其他節(jié)點，那么在虛擬源節(jié)點與這個實際的源節(jié)點之間的鏈接上，信息以個單位信息每單位時間的速率傳送。相當于所有

33、信息都是從虛擬源節(jié)點通過實際的源節(jié)點傳送給接收節(jié)點的。2.2.2 線性向量編碼假設源節(jié)點發(fā)出的所有信息都是維(是整個網(wǎng)絡所有接收點最大流的最小值)的行向量，稱為信息向量15。源節(jié)點一次傳送個不同的信息，對應信息放在信息向量的對應位置上。對每個信息進行標號，無論信息中間經(jīng)過怎樣的變化在信息向量中的位置是不變的。中間節(jié)點將所有接到的信息按照標號放在對應位置上，形成中間節(jié)點的信息向量。節(jié)點根據(jù)線性編碼多播lcm(linear-code muticast)的規(guī)則為每一條邊分配一個邊向量，也稱為局部編碼向量16。邊上傳遞的信息是節(jié)點的信息向量與局部編碼向量作向量乘法之后得到的數(shù)值。每一個信息都攜帶一條全

34、局編碼向量。這條全局編碼向量記載了某個信息在網(wǎng)絡中經(jīng)過不同的邊所經(jīng)歷的編碼的過程。中間節(jié)點發(fā)送信息的時候，首先將所有接到信息的全局編碼向量合成一個的矩陣。信息的全局編碼是矩陣中的第列。該矩陣與邊上的邊向量根據(jù)編碼規(guī)則作向量乘法，得到的維列向量就是輸出信息的全局編碼向量。在解碼信息的時候，將所有接到的信息的全局編碼組合成一個完整的矩陣。因為所以只要解出的逆矩陣就可以解碼出原始信息。 (2-11)為了方便起見，源節(jié)點的第條邊向量可以簡化成僅在第個位置上向量的值不為0。通過這種方法源節(jié)點首次傳輸?shù)男畔嶋H是不同的單個信息而不是信息混合后的結(jié)果。定義2.1 一個通用的多播網(wǎng)絡的線性編碼(lcm)方法是

35、，對于傳輸網(wǎng)絡，是所有節(jié)點的集合，是所有邊的集合。給每一個節(jié)點分配一個線性空間，每一條邊分配一個向量。源節(jié)點的向量它們之間的關(guān)系是：(1)；(2)只要；(3)對任何非源節(jié)點的集合，滿足： (2-12)式中 <.>線性張成的意思；是一個維的向量空間，是網(wǎng)絡的最大流。(4)節(jié)點的輸出邊的向量是節(jié)點輸入邊向量的線性組合。(1)的意思是源節(jié)點的向量空間是維的，就是說源節(jié)點可以同時發(fā)出個線性無關(guān)的信息。(2)的意思是對于某一個節(jié)點發(fā)出的所有邊，邊上的向量都屬于該點的向量空間。(3)的意思是某個非源節(jié)點的向量空間可以由其發(fā)出的邊的向量線形張成。也就是說，如果某些邊是從某個非源節(jié)點發(fā)出的，那么這

36、些向量的線性運算可以張成整個節(jié)點的線性空間。想實現(xiàn)這個要求就需要所有邊上的向量都是維的線性無關(guān)的向量。 (4)由于有這一條限制，輸出的信息包含全部的輸入信息。輸出信息是輸入信息的線性組合。雖然信息的大小沒有變化，但是包含的信息量有所增加。在不增加傳送的次數(shù)的前提下增加了單個信息的接收范圍，由于一個信息可以被多個接收節(jié)點接收，相當于不同接收節(jié)點共用了信道。這種編碼方法的評價：滿足以上方法的網(wǎng)絡編碼可以在網(wǎng)絡無錯傳輸?shù)那闆r下，在接收節(jié)點處正確地解碼出所有的原始信息，同時也可以使任何一個網(wǎng)絡中的節(jié)點達到該節(jié)點的最大流。但是要想達到所有邊向量線性無關(guān)的限制，在選擇向量的時候必須將生成的向量與所有已知向

37、量比較，確定任意維的向量之間都是線性無關(guān)的。當網(wǎng)絡的容量很大的時候，由于任意維向量所組成集合的數(shù)量隨著網(wǎng)絡的邊數(shù)成指數(shù)形式增長，驗證的工作量很大，因此將線性向量編碼應用到大型網(wǎng)絡中是不現(xiàn)實的。2.2.3 線性代數(shù)編碼koetter和medard從代數(shù)構(gòu)造角度出發(fā)，給出了實現(xiàn)線性網(wǎng)絡編碼的全局編碼向量所必須滿足的條件。在這種表示方法中，引入了系統(tǒng)轉(zhuǎn)移矩陣來描述輸入變量與輸出變量之間的關(guān)系17。設節(jié)點是網(wǎng)絡中的唯一源節(jié)點，源節(jié)點的輸出表示為。同時，用來表示接收節(jié)點的輸入。則輸入變量和輸出變量之間的關(guān)系我們就可以表示為，其中就稱為系統(tǒng)轉(zhuǎn)移矩陣。所以，要想在接收節(jié)點由接收到的消息向量得到源節(jié)點輸入，則

38、必須要求系統(tǒng)轉(zhuǎn)移矩陣的行列式不為0。那么，剩下的問題就是如何求得系統(tǒng)轉(zhuǎn)移矩陣？下面首先給出線性網(wǎng)絡編碼的代數(shù)描述。定義2.2：設是無延遲的通信網(wǎng)絡。如果對于網(wǎng)絡中的每一條邊上的隨機過程均滿足 (2-13)在接收節(jié)點處有： (2-14)其中，的取值為有限域中的元素。稱這樣的無延遲的通信網(wǎng)絡為線性網(wǎng)絡。定義23：式(2-13)和式(2-14)中的系數(shù)，被稱為局部編碼向量。定義24：組播通信網(wǎng)絡中，信源節(jié)點的輸入可以看作是有限域上的向量。由于采用線性網(wǎng)絡編碼，則邊上攜帶的信息是信源節(jié)點輸入符號向量的線性組合，用一個向量來表示，稱其為全局編碼向量。則有： (2-15)由式(2-15)可以看出，全局編碼

39、向量和局部編碼向量之間的關(guān)系是: (2-16)式(2-16)表示全局編碼向量與局部編碼向量之間的關(guān)系，描述出了若要在一個通信網(wǎng)絡中實現(xiàn)網(wǎng)絡編碼，網(wǎng)絡中的各個節(jié)點上需要進行的各種操作。定義2.4：任意通信網(wǎng)絡的鄰接矩陣，其中的元素為 (2-17)則鄰接矩陣是一個的的矩陣，它直接反映了通信網(wǎng)絡的拓撲結(jié)構(gòu)。定義2.5：任意通信網(wǎng)絡的信源輸出矩陣，其中的元素為： (2-18)它是一個階矩陣，反映了源節(jié)點的輸出情況。定義2.6：任意通信網(wǎng)絡的接收節(jié)點輸入矩陣定義為： (2-19)它是一個階矩陣，反映了某個接收節(jié)點對信息的接收情況。式(2-17)、式(2-18)、式(2-19)中矩陣,和都用編碼向量來表示

40、，它們反映了整個通信網(wǎng)絡的信息輸入輸出情況和整個拓撲結(jié)構(gòu)的情況。其次給出系統(tǒng)轉(zhuǎn)移矩陣的表達式。定理2.7：在給定了一個表示網(wǎng)絡的矩陣，后，可以得到這個網(wǎng)絡的系統(tǒng)的轉(zhuǎn)移矩陣為： (2-20)其中，一個的單位矩陣。證明：矩陣與矩陣,對整個轉(zhuǎn)移矩陣不起根本性的作用，它們只是輸入與輸出隨機過程的一個線性組合。為了找到在一個輸入隨機過程與輸出隨機過程間的連接關(guān)系，必須沿著所有經(jīng)過的路徑記錄隨機過程所經(jīng)歷的所有變化，并最終轉(zhuǎn)化為。在網(wǎng)絡中節(jié)點間的路徑的變化可以用序列來表示。其中矩陣是一個上三角矩陣，最終將會有一個使得為一個全零矩陣。又因為，又有。所以得到，反映了源節(jié)點的信息在網(wǎng)絡的傳輸過程中由于經(jīng)過網(wǎng)絡編

41、碼而引起的影響。定理得證。定理2.8：給定一個線性網(wǎng)絡，以下的三個命題是等價的：(1)一個組播傳輸是可解的。(2)可以達到圖g上由最小割-最大流定理得到的容量限。(3)轉(zhuǎn)移矩陣的行列式在環(huán)非零。只要根據(jù)約束條件，在系統(tǒng)轉(zhuǎn)移矩陣的行列式不為0的條件下，確定出上式中的滿足條件的變量，也就是得到了局部編碼向量，就完成了這個通信網(wǎng)絡的線性網(wǎng)絡編碼。這種編碼方法的評價：代數(shù)編碼方法適用于動態(tài)網(wǎng)絡，優(yōu)點在于編碼調(diào)整時的靈活性強。當網(wǎng)絡的拓撲結(jié)構(gòu)改變的時候，網(wǎng)絡編碼矩陣不需要整體改動，只需要局部調(diào)整編碼系數(shù)，令網(wǎng)絡的轉(zhuǎn)移矩陣對于所有接收節(jié)點都有解即可適應新的網(wǎng)絡結(jié)構(gòu)。同時代數(shù)編碼抵抗網(wǎng)絡變化的能力更高，也就

42、是魯棒性很好，尤其是對節(jié)點和鏈路丟失的錯誤情況。因為鏈路的丟失意味著在全局編碼矩陣中，邊上的局部編碼為0。由于網(wǎng)絡轉(zhuǎn)移矩陣的行列式值由多個局部編碼聯(lián)合作用得到，其中幾個值為0有可能不會影響到所有接收節(jié)點。仍然有接收節(jié)點可以解碼出全部信息。同時網(wǎng)絡局部編碼系數(shù)也不需要太大的改變，因此稱代數(shù)編碼對于網(wǎng)絡鏈路的丟失有一定的魯棒性。但是這種方法由于需要每一個節(jié)點知道網(wǎng)絡的全局拓撲，因而并不能完全在實際網(wǎng)絡上應用。2.2.4 隨機網(wǎng)絡編碼實際網(wǎng)絡中，由于網(wǎng)絡拓撲的變化和網(wǎng)絡規(guī)模的擴大，每一個無線節(jié)點獲取整個網(wǎng)絡結(jié)構(gòu)信息和網(wǎng)絡中各個節(jié)點的編碼系數(shù)是不容易實現(xiàn)的。針對這一問題，ho等人提出了一種隨機網(wǎng)絡編碼

43、的思想18。隨機網(wǎng)絡編碼思想的系數(shù)構(gòu)造中，可以讓節(jié)點攜帶一個全局編碼向量，在經(jīng)過每一個節(jié)點的時候都根據(jù)該節(jié)點的編碼方式在改變信息的同時改變編碼向量。這樣當接收節(jié)點接到信息的時候不需要知道整個網(wǎng)絡的拓撲和網(wǎng)絡的編碼情況，只要接到信息的全局編碼向量組成的矩陣維數(shù)(一次發(fā)送信息的數(shù)量)就可以解碼出全部的個信息。這樣接收節(jié)點就不需要知道網(wǎng)絡拓撲。圖2-5舉例說明了隨機網(wǎng)絡編碼的思想。(1, 2, 3)(4, 5, 6)random linearnetwork coding(6, 9, 12)圖2-5 隨機網(wǎng)絡編碼思想舉例圖2-5中，中間節(jié)點接收到信息編碼組合包和。此時，中間節(jié)點將應用隨機網(wǎng)絡編碼的思想

44、發(fā)送編碼信息包，這就需要在一個有限域中隨機選取新的編碼系數(shù)(圖2-5例中選取的編碼系數(shù)為2、1)，并對編碼組合后的信息包進行新的編碼運算： (2-21)得到新的編碼系數(shù)為6,9,12，將新的編碼組合包傳輸發(fā)送。該方法不需要考慮網(wǎng)絡拓撲結(jié)構(gòu)，并適合在分布式的網(wǎng)絡中使用。應用隨機網(wǎng)絡編碼傳輸，當接收節(jié)點收到滿足線性可解條件的編碼組合，即可使用解線性組合的方法恢復原始信息包。隨機網(wǎng)絡編碼同時規(guī)定，中間節(jié)點在分配局部編碼向量的時候只需要在有限域中隨機選取系數(shù)，不需要驗證是否相關(guān)。當然這樣的結(jié)果是在接收節(jié)點可能出現(xiàn)的線性相關(guān)的向量從而使接收節(jié)點解碼失敗。對于可行的多播網(wǎng)絡，帶有獨立或線性相關(guān)的源，當所有

45、的系數(shù)都在有限域中獨立隨機地選擇時，所有的接收節(jié)點都能夠解碼出信息的可能性至少是 (2-22)式中 接收節(jié)點的個數(shù)；系數(shù)選擇的范圍即字母表的大小；滿足以下條件的邊的最大數(shù)量。該條件為：邊上傳遞的信息來自所有源節(jié)點，同時可將信息傳到任何一個接收節(jié)點。網(wǎng)絡傳輸?shù)氖÷逝c網(wǎng)絡的尺寸成反比，傳輸失敗率與編碼之后碼字的長度成指數(shù)關(guān)系減少。這樣只要根據(jù)網(wǎng)絡的大小和信息多少，估算出傳輸需要的中間邊的數(shù)量就可以適當?shù)倪x擇合適的字母表大小，在網(wǎng)絡的穩(wěn)定性與網(wǎng)絡傳播冗余量之間做出選擇。對于線性相關(guān)的網(wǎng)絡，這種算法也不需要源節(jié)點知道其他源節(jié)點的信息。與傳統(tǒng)路由方法相比，對于源節(jié)點的增加或減少和網(wǎng)絡拓撲結(jié)構(gòu)的變化等問

46、題，隨機網(wǎng)絡編碼更加靈活。2.3 本章小結(jié)本章闡述了網(wǎng)絡編碼的概念、原理，并且對幾種常見的網(wǎng)絡編碼的構(gòu)造方法做了歸類，同時也分析了這幾種常見的網(wǎng)絡編碼方案的優(yōu)缺點，對當前基于網(wǎng)絡編碼的無線傳輸技術(shù)研究作了綜述。第3章 基于隨機網(wǎng)絡編碼的重傳方案的設計 第3章 基于隨機網(wǎng)絡編碼的重傳方案的設計無線廣播傳輸中，為了保證無線鏈路的可靠性，多個接收節(jié)點中任意一個節(jié)點丟失的信息包都要求源節(jié)點重新傳送數(shù)據(jù)包以實現(xiàn)差錯控制，需要較高的信道占用率和較多的重傳次數(shù)。本章針對無線傳輸中的廣播重傳問題，研究了如何應用網(wǎng)絡編碼的思想組合接收節(jié)點上的多個不同丟失信息包進行重傳發(fā)送，設計了一種基于隨機網(wǎng)絡編碼的無線廣播重

47、傳策略，該策略對傳輸信息包進行分批重傳處理，采用隨機線性網(wǎng)絡編碼解碼的方法保證每一信息包批次內(nèi)的重傳可解性，相比起原有策略顯著的提高了重傳性能。盡管該策略需要對批次內(nèi)的信息包進行延時等待，但重傳性能可以達到每個信息包批次內(nèi)的重傳最優(yōu)性。3.1 隨機網(wǎng)絡編碼的實現(xiàn)在這一部分，我們首先介紹隨機線性網(wǎng)絡編碼的基本思想，然后闡述節(jié)點如何構(gòu)造隨機線性網(wǎng)絡編碼信息包的策略思想，最后分析了隨機線性網(wǎng)絡編碼包在接收節(jié)點的解碼操作和可解性條件。網(wǎng)絡中所有節(jié)點對其輸入信息進行線性組合操作，稱為線性網(wǎng)絡編碼，如果線性編碼系數(shù)是隨機產(chǎn)生的則稱為隨機線性網(wǎng)絡編碼。圖3-1說明了普通傳輸方法與應用隨機線性網(wǎng)絡編碼的傳輸方

48、法的比較。如圖所示，節(jié)點需要發(fā)送信息包，。圖3-1 a)表示傳統(tǒng)的發(fā)送方法：源節(jié)點要逐一廣播待發(fā)送的信息包,接收節(jié)點也逐一接收各個信息包，完成節(jié)點間的數(shù)據(jù)傳輸過程。當節(jié)點丟失某信息包時，源節(jié)點要逐一發(fā)送丟失的信息包。圖3-1 b)表示應用了隨機線性網(wǎng)絡編碼思想的信息包的傳輸方法。節(jié)點不再僅具有存儲轉(zhuǎn)發(fā)功能，而是具有編碼功能，其可以再一個有限域中獨立隨機的選取系數(shù)、，通過編碼運算得到： (3-1) (3-2) (3-3)三個編碼信息包，同時把隨機編碼系數(shù)、寫入編碼組合包，節(jié)點廣播逐一發(fā)送各編碼組合包。接收節(jié)點x和y在完整接收到3個編碼組合包以后，將會獲得: (3-4) 節(jié)點x(或者節(jié)點y)聯(lián)合式

49、(3-4)，將得到一個包含三個方程的方程組，其中編碼系數(shù)、在編碼組合包中為已知，三個方程有三個未知數(shù)(,)，由矩陣論可知，當三個方程線性無關(guān)時，此方程組具有可解性，節(jié)點x(或者節(jié)點y)可以通過解方程組運算操作解出原始信息包,。rxy,rxya) 傳統(tǒng)的發(fā)送方法b) 隨機線性網(wǎng)絡編碼方法圖3-1 傳統(tǒng)方法和隨機線性網(wǎng)絡編碼方法的信息傳輸比較應用隨機線性網(wǎng)絡編碼的重傳方法，接收節(jié)點處理的問題由是否接收到完整的信息包的問題，轉(zhuǎn)換為是否收到足夠多的滿足可解性條件的編碼信息包的問題。通過研究發(fā)現(xiàn)，通過發(fā)送隨機線性網(wǎng)絡編碼組合可以帶來良好的吞吐量、魯棒性、安全性等個方面的增益，為網(wǎng)絡傳輸性能的改善提供了一

50、種新的途徑。對于源節(jié)點的增加或減少和網(wǎng)絡拓撲結(jié)構(gòu)的變化等問題，隨機線性網(wǎng)絡編碼更加靈活。3.2 無線廣播重傳模型的建立無線廣播重傳策略的設計，需要建立一個接近現(xiàn)實環(huán)境的無線廣播重傳模型。假設一具有一個廣播源節(jié)點和(，本課題設計的是)個接收節(jié)點的無線廣播網(wǎng)絡，廣播源節(jié)點和接收節(jié)點之間的傳輸鏈路存在損耗。假設1 傳輸信息包長度相同，均為比特，由編碼運算中的有限域封閉計算理論，線性網(wǎng)絡編碼包的長度同樣為比特。廣播源以固定時間間隔()廣播傳送信息包(本課題設計的是有10個待發(fā)送的信息包)，廣播源節(jié)點和(,本課題設計的是)個接收節(jié)點之間的傳輸丟包率互不相關(guān)，且服從伯努利分布，對應某個接收節(jié)點()的丟包率

51、為。12345信息包反饋圖3-2 一個源節(jié)點五個接收節(jié)點無線廣播模型假設2 廣播源節(jié)點傳輸中某個信息包發(fā)送完畢后，(,本課題設計的是)個接收節(jié)點接收并發(fā)送ack/nak控制信息包反饋該信息包的接收情況。丟失情況包括：信息包是否成功接收；丟失信息包序列號和丟失節(jié)點序列號。假定ack/nak控制信息包在信道中不存在損耗。ack/nak中包含丟失包的序列號與接收節(jié)點序列號。假設3 (,本課題設計的是)個接收節(jié)點的丟失情況記錄在一個廣播接收狀態(tài)矩陣中。矩陣中行表示接收節(jié)點的接收情況，列表示信息包接收情況。接收成功相應位置賦值為0，否則賦值為1。3.3 隨機線性網(wǎng)絡編碼包的構(gòu)造在編碼中，把信息看作是特定基域上的向量，假定每一個信息包等長為比特(當參與編碼的信息包的長度低于比特時，通過補0來實現(xiàn)同樣長度