第1章緒論

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

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

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

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

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

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

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

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

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

……………

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

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

參考文獻(xiàn)（略）