本文選題：確定網(wǎng)絡(luò)編碼 + 隨機(jī)線性網(wǎng)絡(luò)編碼　； 參考：《南京大學(xué)》2014年博士論文

【摘要】：在無線網(wǎng)絡(luò)中,無線傳輸?shù)膹V播特性以及網(wǎng)絡(luò)拓?fù)涞亩嗵?使得無線網(wǎng)絡(luò)中存在大量冗余報(bào)文,直接影響著無線網(wǎng)絡(luò)的傳輸性能。近年來的研究表明,網(wǎng)絡(luò)編碼技術(shù)能夠通過有效利用無線網(wǎng)絡(luò)中的冗余報(bào)文,提升網(wǎng)絡(luò)性能。然而,網(wǎng)絡(luò)編碼增加了額外計(jì)算開銷,其性能增益通常受限于無線信道廣播速率及無線節(jié)點(diǎn)的計(jì)算能力,同時(shí)還會(huì)受到無線節(jié)點(diǎn)移動(dòng)性的影響。如何面向這些無線網(wǎng)絡(luò)的關(guān)鍵特征,設(shè)計(jì)合理高效的網(wǎng)絡(luò)編碼方法是無線網(wǎng)絡(luò)性能優(yōu)化中的重要問題。 針對(duì)上述問題,本文從適應(yīng)無線信道廣播速率限制的角度研究了多信道環(huán)境中網(wǎng)絡(luò)編碼方法,并從適應(yīng)無線節(jié)點(diǎn)計(jì)算能力與移動(dòng)性的角度分別對(duì)面向數(shù)據(jù)傳送及面向數(shù)據(jù)廣播的網(wǎng)絡(luò)編碼方法開展了研究。論文主要貢獻(xiàn)包括以下三個(gè)方面： (1)針對(duì)多信道無線網(wǎng)絡(luò)吞吐率性能優(yōu)化,以O(shè)FDMA中繼網(wǎng)絡(luò)為應(yīng)用背景,對(duì)適應(yīng)無線信道廣播速率的網(wǎng)絡(luò)編碼方法進(jìn)行了探討。首先以優(yōu)化性能與負(fù)載為切入點(diǎn),提出了用于支持編碼感知的信道調(diào)度策略的全局方法和局部方法。進(jìn)一步地,針對(duì)全局方法下的網(wǎng)絡(luò)編碼感知的信道調(diào)度問題,證明了該問題是NP難的且不存在多項(xiàng)式時(shí)間近似方案(polynomial time approximation scheme),并提出了一種具有低時(shí)間復(fù)雜度的啟發(fā)式算法。針對(duì)局部方法下的網(wǎng)絡(luò)編碼感知的信道調(diào)度問題,證明了該問題是NP難的,并提出了一種多項(xiàng)式時(shí)間近似方案及一種具有1／2近似率的貪婪算法。仿真實(shí)驗(yàn)結(jié)果表明所提算法相比于無網(wǎng)絡(luò)編碼的機(jī)制,能夠極大地提高網(wǎng)絡(luò)吞吐率。 (2)針對(duì)無線移動(dòng)網(wǎng)絡(luò)中數(shù)據(jù)傳送性能優(yōu)化,對(duì)具有常數(shù)復(fù)雜度的分塊隨機(jī)線性網(wǎng)絡(luò)編碼(簡(jiǎn)稱分塊碼)方法進(jìn)行了研究。首先證明了預(yù)編碼(precoding)在分塊碼達(dá)到正碼率中的不可或缺性。在預(yù)編碼的前提下,對(duì)無重疊分塊碼的可達(dá)碼率進(jìn)行了緊(tight)的分析,并進(jìn)一步地提出了采用擴(kuò)展圖(expander graph)生成重疊報(bào)文塊的擴(kuò)展分塊碼。通過基于樹的分析以及擴(kuò)展論證刻畫了擴(kuò)展分塊碼的可達(dá)碼率,從而明確了擴(kuò)展分塊碼是第一類具有非平凡性能保證的重疊分塊碼。數(shù)值分析結(jié)果顯示擴(kuò)展分塊碼性能接近最優(yōu),其可達(dá)碼率極大地超出了無重疊分塊碼。此外,仿真實(shí)驗(yàn)結(jié)果表明,當(dāng)輸入報(bào)文個(gè)數(shù)有限時(shí),擴(kuò)展分塊碼相比于其他重疊分塊碼具有低得多的傳輸負(fù)載和解碼錯(cuò)誤概率。 (3)針對(duì)無線移動(dòng)網(wǎng)絡(luò)中數(shù)據(jù)廣播性能優(yōu)化,提出了一種新穎的基于隨機(jī)線性網(wǎng)絡(luò)編碼的廣播協(xié)議。該協(xié)議將需要廣播的消息分割成多個(gè)子消息,并將子消息以隨機(jī)線性網(wǎng)絡(luò)編碼的方式進(jìn)行傳輸。隨機(jī)線性網(wǎng)絡(luò)編碼的應(yīng)用使得無線節(jié)點(diǎn)易于收集有效信息,從而減輕了因一個(gè)或多個(gè)節(jié)點(diǎn)過晚接收到消息所致的時(shí)延瓶頸。與此同時(shí),節(jié)點(diǎn)傳輸采用了隨機(jī)調(diào)度機(jī)制,即每一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)獨(dú)立地使用無線信道。隨機(jī)調(diào)度的使用能夠在利用無線媒介廣播特性的同時(shí),有效應(yīng)對(duì)并發(fā)傳輸所致的沖突問題。理論分析表明,該協(xié)議在任意的節(jié)點(diǎn)移動(dòng)速度下,均能夠達(dá)到漸進(jìn)最優(yōu)的廣播時(shí)延。相反地,純粹的隨機(jī)調(diào)度策略在節(jié)點(diǎn)快速移動(dòng)時(shí)不足以達(dá)到最優(yōu)性。
[Abstract]:In wireless networks, the broadcast characteristics of wireless transmission and the multiple hops of the network topology make a large number of redundant packets in the wireless network, which directly affect the transmission performance of the wireless network. In recent years, the research shows that the network coding technology can effectively use redundant packets in the wireless network to improve the network performance. However, the network coding is made up. The code increases the extra computing overhead, and its performance gain is usually limited to the radio channel broadcasting rate and the computing power of the wireless nodes, but it will also be affected by the mobility of wireless nodes. How to design a reasonable and efficient network coding method is an important problem in the performance optimization of wireless networks for the key features of these wireless networks.
In view of the above problems, this paper studies the network coding method in the multi channel environment from the angle of radio channel broadcast rate restriction, and studies the network coding method for data transmission and data broadcasting from the angle of wireless node computing power and mobility. The main contributions of this paper include the following three Aspect:
(1) aiming at the performance optimization of multi channel wireless network throughput, the network coding method adapted to the radio channel broadcasting rate is discussed with the OFDMA relay network as the application background. First, the global method and local method for the channel scheduling strategy used to support the coding awareness are proposed. It is proved that the problem is NP difficult and no polynomial time approximation (polynomial time approximation scheme), and a heuristic algorithm with low time complexity is proposed to solve the problem of network coding aware channel scheduling under global method. It is clear that the problem is NP difficult, and a polynomial time approximation scheme and a greedy algorithm with 1 / 2 approximation are proposed. The simulation results show that the proposed algorithm can greatly improve the network throughput compared to the non network coding mechanism.
(2) aiming at the optimization of data transmission performance in wireless mobile network, the method of block random linear network coding (block code) with constant complexity is studied. First, it is proved that the precoding (precoding) is indispensable to the positive rate of block code. Under precoding, the reachable code rate for non overlapping block codes is achieved. The analysis of tight is carried out, and an extended block code that uses an extended graph (expander graph) to generate overlapping packet blocks is further proposed. By tree based analysis and extension argument, the reachable code rate of extended block codes is depicted. Thus, the extended block code is the first class of overlapping block codes with non trivial performance guarantee. The analysis results show that the performance of the extended block code is close to the optimal, and the reachable code rate is greatly beyond the non overlapping block code. In addition, the simulation results show that when the number of input messages is limited, the extended block code has a much lower transmission load and decoding error probability compared to the other overlapped block codes.
(3) in order to optimize the performance of data broadcasting in wireless mobile networks, a novel broadcast protocol based on random linear network coding is proposed. This protocol divides the messages needed to be divided into multiple sub messages and transmits submessages in a random linear network. The application of random linear network coding makes wireless nodes It is easy to collect effective information, thus reducing the delay bottleneck caused by the late reception of one or more nodes. At the same time, the node transmission adopts a random scheduling mechanism, that is, each network node uses the wireless channel randomly and independently. The use of random scheduling can have effect while using the radio characteristics of the wireless media. The theoretical analysis shows that the protocol can achieve progressive optimal broadcast delay under the moving speed of any node. On the contrary, the pure random scheduling strategy is not sufficient to achieve optimality when the node moves quickly.
【學(xué)位授予單位】：南京大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2014
【分類號(hào)】：TN92

【共引文獻(xiàn)】

相關(guān)期刊論文 前10條

1 沈軍;曹元大;楊鯤;;LAB:Ad Hoc網(wǎng)絡(luò)中的位置輔助動(dòng)態(tài)廣播協(xié)議[J];北京理工大學(xué)學(xué)報(bào);2006年08期

2 扈鵬;劉元安;馬曉雷;高松;;Ad Hoc網(wǎng)絡(luò)中按需路由協(xié)議的動(dòng)態(tài)廣播算法[J];北京郵電大學(xué)學(xué)報(bào);2009年06期

3 王孟浩;劉晏兵;;移動(dòng)自組網(wǎng)中基于區(qū)域的多路路由算法[J];重慶郵電學(xué)院學(xué)報(bào)(自然科學(xué)版);2006年05期

4 劉海英;林海燕;;基于支配集和自減的無線移動(dòng)Ad hoc網(wǎng)絡(luò)泛洪算法[J];儀器儀表用戶;2011年06期

5 李宏;于宏毅;劉阿娜;;一種基于樹的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集方法[J];電子與信息學(xué)報(bào);2007年07期

6 文凱;郭偉;黃廣杰;;無線Ad hoc網(wǎng)絡(luò)中基于拓?fù)涞墓β矢兄酚蓞f(xié)議[J];電子與信息學(xué)報(bào);2008年12期

7 吳大鵬;武穆清;甄巖;張曉靜;;帶有帶寬感知的自適應(yīng)轉(zhuǎn)發(fā)節(jié)點(diǎn)集合建立機(jī)制[J];高技術(shù)通訊;2009年09期

8 王秀峰;鄒炳松;崔剛;;基于時(shí)間預(yù)測(cè)的廣播協(xié)議[J];智能計(jì)算機(jī)與應(yīng)用;2013年01期

9 王建新;朱敬;劉耀;;基于副本限制和社會(huì)性的延遲容忍網(wǎng)絡(luò)路由算法[J];華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年05期

10 袁培燕;劉萍;高宏卿;;自組織網(wǎng)絡(luò)洪泛方式的一種改進(jìn)算法[J];河南師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年06期

相關(guān)會(huì)議論文 前2條

1 胡平;任品毅;馮佳;薛波;;一種基于AODV的能量均衡路由[A];中國(guó)電子學(xué)會(huì)第十五屆信息論學(xué)術(shù)年會(huì)暨第一屆全國(guó)網(wǎng)絡(luò)編碼學(xué)術(shù)年會(huì)論文集（下冊(cè)）[C];2008年

2 秦彬;李禮;張春元;;多接口多信道無線ad-hoc網(wǎng)絡(luò)的廣播研究[A];中國(guó)通信學(xué)會(huì)第五屆學(xué)術(shù)年會(huì)論文集[C];2008年

相關(guān)博士學(xué)位論文 前10條

1 付永生;無線Ad Hoc網(wǎng)絡(luò)中可靠路由若干關(guān)鍵問題的研究[D];浙江大學(xué);2010年

2 官權(quán)升;移動(dòng)自組織網(wǎng)絡(luò)的拓?fù)淇刂萍熬W(wǎng)絡(luò)性能研究[D];華南理工大學(xué);2011年

3 周連科;基于交通流密度的VANET廣播技術(shù)研究[D];哈爾濱工業(yè)大學(xué);2011年

4 匡羅貝;無線公交車載網(wǎng)絡(luò)MAC及路由關(guān)鍵技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2011年

5 穆嘉松;基于節(jié)點(diǎn)移動(dòng)性的ZigBee網(wǎng)絡(luò)自適應(yīng)路由策略研究[D];天津大學(xué);2012年

6 鄭石;能量受限Ad Hoc網(wǎng)絡(luò)的路由協(xié)議研究[D];哈爾濱工業(yè)大學(xué);2011年

7 沈中;無線Ad Hoc網(wǎng)絡(luò)拓?fù)涔芾硌芯縖D];西安電子科技大學(xué);2005年

8 任雄偉;無線移動(dòng)自組網(wǎng)中路由度量和路由策略的研究[D];華中科技大學(xué);2005年

9 袁江;小衛(wèi)星組網(wǎng)路由方法研究[D];中國(guó)科學(xué)院研究生院（空間科學(xué)與應(yīng)用研究中心）;2006年

10 年梅;Ad Hoc網(wǎng)絡(luò)的單播和組播路由協(xié)議的研究[D];華東師范大學(xué);2006年

相關(guān)碩士學(xué)位論文 前10條

1 劉濤;Ad hoc無線自組網(wǎng)的研究[D];江南大學(xué);2011年

2 楊東東;Ad Hoc網(wǎng)絡(luò)中廣播算法的研究[D];吉林大學(xué);2011年

3 王楠楠;無線網(wǎng)絡(luò)中基于CDS的拓?fù)淇刂扑惴ㄑ芯縖D];曲阜師范大學(xué);2011年

4 黎薇;多速率WLANs用戶接入機(jī)制研究[D];北京郵電大學(xué);2011年

5 劉江濤;混合傳感網(wǎng)絡(luò)路由與定位技術(shù)研究[D];西南交通大學(xué);2011年

6 柴營(yíng);分簇DTN網(wǎng)絡(luò)路由算法研究[D];天津大學(xué);2010年

7 謝金慧;一類面向節(jié)能的生產(chǎn)調(diào)度模型及優(yōu)化算法研究[D];上海交通大學(xué);2012年

8 劉欣;分布式審計(jì)系統(tǒng)中消息廣播和超大數(shù)據(jù)傳輸方法的研究[D];蘇州大學(xué);2011年

9 趙賓華;Ad Hoc網(wǎng)絡(luò)接入Internet過程中開銷控制的研究[D];東北大學(xué);2009年

10 Walid M. Rajeh Al-Derwesh（伍力德）;移動(dòng)自組網(wǎng)中可靠組播協(xié)議研究[D];中南大學(xué);2005年

，

本文編號(hào)：2113944