第1章緒論

1.1研究背景
與多收發(fā)機多信道技術(shù)以及MIMO天線技術(shù)等相比，網(wǎng)絡編碼作為一種無需增加額外硬件設備的方法，為無線網(wǎng)絡性能優(yōu)化提供了一個薪新的思路。由于無線媒介的廣播特性以及拓撲的多跳特征，使得無線網(wǎng)絡中存在著大量的冗余報文。通過對網(wǎng)絡中冗余報文實施合理的網(wǎng)絡編碼并利用無線媒介的廣播特性，可有效減少傳輸次數(shù)，進而提高無線網(wǎng)絡性能。下面通過兩個例子來說明網(wǎng)絡編碼在無線網(wǎng)絡中應用的主流方法以及相應的性能優(yōu)勢。

1.2面向無線網(wǎng)絡的高效網(wǎng)絡編碼方法研究
一般而言，在多信道環(huán)境中，無線節(jié)點可根據(jù)鏈路的信道狀態(tài)信息選擇合適的信道速率。為了支持網(wǎng)絡編碼而選擇廣播傳輸時，出于信道傳輸可靠性需求的考慮，信道廣播速率的選擇通常由廣播所含的多條單播鏈路上的最壞信道狀態(tài)決定，從而使得廣播速率為多條單播鏈路傳輸速率的最低值。因此，如果盲目地應用網(wǎng)絡編碼，可能會導致性能的下降�；诖�，對于多信道環(huán)境，如何為節(jié)點設計合理的網(wǎng)絡編碼方案，使得基于網(wǎng)絡編碼的數(shù)據(jù)傳輸性能得到優(yōu)化，是網(wǎng)絡編碼應用中的一個關(guān)鍵問題。本文針對圖1.2所示的簡單卻又泛在的確定網(wǎng)絡編碼方法，對面向多信道環(huán)境的網(wǎng)絡編碼方法進行了研宄，并提出了多個高效的網(wǎng)絡編碼感知的信道調(diào)度算法。
隨機線性網(wǎng)絡編碼通常具有較高的解碼時延，而節(jié)點的移動性易于引起網(wǎng)絡拓撲變化，使得隨機線性網(wǎng)絡編碼的解碼時延更難以得到保證。（2)中的研究在一定程度上能夠保證隨機線性網(wǎng)絡編碼在單個目的節(jié)點上的解碼時延，然而，由于不同目的節(jié)點之間傳輸?shù)牟町愋�，�?)中的研究難以優(yōu)化應用于數(shù)據(jù)廣播場景中。如何針對節(jié)點的移動性，設計合理高效的網(wǎng)絡編碼方法，從而保證數(shù)據(jù)廣播場景中所有節(jié)點上的解碼時延，是面向無線移動環(huán)境中網(wǎng)絡編碼應用中的一個重要問?題。本文從單個消息廣播問題出發(fā)，對隨機線性網(wǎng)絡編碼在無線移動網(wǎng)絡中的應用與性能進行了探討，提出了一種基于隨機線性網(wǎng)絡編碼的廣播協(xié)議，并論證了其在廣播時延方面的漸進最優(yōu)性。
……………

第2章相關(guān)工作

2.1網(wǎng)絡編碼理論相關(guān)工作
上述研究主要針對無圈網(wǎng)絡中的單信源網(wǎng)絡編碼。然而，在有圈網(wǎng)絡中，節(jié)點之間不存在偏序關(guān)系，從而破壞了上述方法的最優(yōu)性。針對此問題，研究者對單位時延有圈網(wǎng)絡中的卷積網(wǎng)絡編碼(convolutional network codes)進行了研究。Koettei和Medard間首先證明了在單位時延網(wǎng)絡中存在卷積多播(convolutionalmulticast)。此后，Erez和Feder、Pragouli和Soljanin，以及Barbero和Ytrehus對于卷積多播的存在性與構(gòu)造進行了深入的研宄。Li則基于環(huán)論給出了卷積網(wǎng)絡編碼的一般抽象形式。相比于單信源網(wǎng)絡編碼，多信源網(wǎng)絡編碼的最優(yōu)構(gòu)造更為困難。Medard等人、Lehman等人以及Riis證明了特殊形式的線性編碼對于多信源網(wǎng)絡編碼是不充分的。Doughert等人則證明了更一般的線性編碼的不充分性。然而，當所有信源都由網(wǎng)絡同一個節(jié)點產(chǎn)生時，Chan構(gòu)造了一類基于群的網(wǎng)絡編碼并證明了其最優(yōu)性。這些工作對網(wǎng)絡編碼的理論研究具有較大的促進作用，但是這些工作中大多引入了非常強的假設，距離實際應用仍有較大的距離。

2.2確定網(wǎng)絡編碼方法研究
上述大多數(shù)關(guān)于確定網(wǎng)絡編碼的研究注重在基于協(xié)議的單信道無線網(wǎng)絡中。由于協(xié)議下信道調(diào)制速率是固定的，因此無需考慮無線信道廣播速率限制的問題。然而，在多信道環(huán)境中，同一個信道在不同鏈路上速率可能存在較大的差異，因此網(wǎng)絡編碼的應用需要適應于無線廣播信道速率。目前，只有少數(shù)的工作考慮了確定網(wǎng)絡編碼在多信道場景(如OFDMA網(wǎng)絡)中的應用與性能增益。Zhang和Li考慮了基于OFDMA的單跳蜂窩網(wǎng)絡中基站上確定網(wǎng)絡編碼的應用方法，并提出了信道分配的啟發(fā)式算法。Xu和Li, Xu等人，Liu等人[34]以及Kim和Lee[35]則考慮了確定網(wǎng)絡編碼在OFDMA中繼網(wǎng)絡中的中繼站上的應用。然而，這些工作中大多(1)采用香農(nóng)公式計算鏈路速率，從而使得信道廣播時，每一條鏈路上的速率與單播時相同，這不符合實際應用中無線廣播傳輸模式下信道速率選擇方法；（2)采用啟發(fā)式算法對信道進行調(diào)度，缺乏一定的性能保證；（3)忽略了一些實際因素的影響，如中繼站上數(shù)據(jù)緩存的能力[35]，信道環(huán)境的不穩(wěn)定性等等；（4)一味地追求網(wǎng)絡整體的性能，從而忽略了用戶之間的公平性。
……………

3面向多信道無線網(wǎng)絡的網(wǎng)絡編碼方法研究………………16
3.1 引言 ………………16
3.2相關(guān)工作 ……………18
3.3系統(tǒng)建模 ……………19
4面向無線移動網(wǎng)絡數(shù)據(jù)傳送的網(wǎng)絡編碼方法研究……… 47
4.1問題建模……………… 49
4.1.1編碼與解碼………… 49
4.1.2性能分析模型 ………50
4.2預編碼的重要性…………51
4.3無重疊分塊碼的可達速率 …………54
4.4擴展分塊碼 ……………57
5面向無線移動網(wǎng)絡數(shù)據(jù)廣播的網(wǎng)絡編碼方法研究……………69
5.1引言 ………………69
5.2相關(guān)工作………70
5.3系統(tǒng)建模………………………… 71

第5章面向無線移動網(wǎng)絡數(shù)據(jù)廣播的網(wǎng)絡編碼方法研究

5.1引言
在本章中，我們通過考慮移動自組網(wǎng)中的數(shù)據(jù)廣播問題以及如何利用網(wǎng)絡編碼優(yōu)化數(shù)據(jù)廣播時延來對上述問題進行初步的探討。為完整起見，首先對移動自組網(wǎng)中的廣播問題進行介紹。一個典型的移動自組網(wǎng)是自配置的無線網(wǎng)絡，其中的網(wǎng)絡節(jié)點不僅可以充當主機，也可以作為中繼，為其它網(wǎng)絡節(jié)點存儲轉(zhuǎn)發(fā)數(shù)據(jù)，此外，節(jié)點還可以按照自己的意愿進行移動。移動自組網(wǎng)中一個基本操作是廣播，被用在了各種各樣的應用中。廣播操作的任務是將源節(jié)點的一個消息分發(fā)給網(wǎng)絡中所有的其他節(jié)點。出于對時間緊急的應用(如發(fā)送警報，救災搶險等)的考慮，本章致力于最小化廣播時延，即網(wǎng)絡中所有節(jié)點均收到該消息所需要的時間。

5.2相關(guān)工作
近年來，已有一些工作考慮了節(jié)點移動對廣播時延的影響。這些工作可根據(jù)傳輸半徑是否超出關(guān)鍵半徑分成兩類。在稀疏的情況下，即傳輸半徑低于關(guān)鍵半徑時，研究者在各種移動模型下對廣播時延進行了討論。這些模型包括廣為人知的獨立同分布移動模型[138丨，隨機行走模型[139]等等。在密集的情況下，即傳輸半徑高于關(guān)鍵半徑時，Clementi等人[140，141, 142]在與本章工作中幾乎相同的網(wǎng)絡模型下對廣播時延進行了一些研宄。他們建立了一個廣播時延的下界，并對洪泛方法下的廣播時延進行了分析。然而，他們的工作并沒有考慮并發(fā)傳輸時的干擾問題。Chen等人[143]引入了一種閑談的方法，這種方法采用了功率控制從而有效地對抗了干擾問題，然而這種方法沒有利用無線媒介的廣播特性，從而導致性能是次優(yōu)的。

……………

第6章總結(jié)與展望

本文首先從適應無線信道廣播速率的角度對多信道環(huán)境中的網(wǎng)絡編碼方法進行了研究，接著從適應無線節(jié)點計算能力與移動性的角度分別對面向數(shù)據(jù)傳送及面向數(shù)據(jù)廣播的網(wǎng)絡編碼方法進行了研宄，其主要貢獻總結(jié)如下：
以OFDMA中繼網(wǎng)絡為應用背景，對適應無線信道廣播速率的網(wǎng)絡編碼方法進行了探討。以優(yōu)化性能與負載為切入點，提出了全局方法和局部方法用以支持網(wǎng)絡編碼感知的信道調(diào)度策略。針對全局方法下的網(wǎng)絡編碼感知信道分配問題，證明了其是NP難旳且不存在PTAS，并提出了一種低時間復雜度的啟發(fā)式算法EMW。針對局部方法下的網(wǎng)絡編碼感知信道分配問題，證明了其是NP難的，并提出了一種PTAS解法以及一種實用的具有1/2近似率的貪姿算法HAG。仿真實驗結(jié)果表明，EMW和HAG相比于無網(wǎng)絡編碼的機制，能夠極大地提高網(wǎng)絡吞吐率。
對面向無線移動網(wǎng)絡中可靠數(shù)據(jù)傳送的具有常數(shù)復雜度的分塊碼方法進行了研究。首先證明了預編碼在對分塊碼的不可或缺性，否則分塊碼的可達碼率在漸進意義下為0。接著在預編碼的前提下，對無重疊分塊碼的可達碼率進行了緊的分析，并發(fā)現(xiàn)其較為低下。進一步地，提出了一類新穎的采用擴展圖生成重疊報文塊的擴展分塊碼，并通過樹的分析以及擴展論證對其可達碼率進行了刻畫，從而表明擴展分塊碼是第一類具備非平凡性能保證的重疊分塊碼。擴展分塊碼的可達碼率極大地超出了無重疊分塊碼，并且仿真結(jié)果表明，當輸入報文數(shù)目有限時，擴展分塊碼與其它重疊分塊碼相比，具有低得多的傳輸負載和解碼錯誤概率。
……………

參考文獻（略）