本文關(guān)鍵詞： SIMD 可靠傳輸 多源網(wǎng)絡(luò)編碼 機會路由 效用優(yōu)化模型 流內(nèi)網(wǎng)絡(luò)編碼 流間網(wǎng)絡(luò)編碼　出處：《南京理工大學》2016年博士論文　論文類型：學位論文

【摘要】：網(wǎng)絡(luò)編碼理論在2000年由Ahlswede等基于網(wǎng)絡(luò)信息流的概念提出,目前已被應(yīng)用于網(wǎng)絡(luò)安全、路由算法和可靠傳輸?shù)阮I(lǐng)域。本文對無線網(wǎng)絡(luò)上基于網(wǎng)絡(luò)編碼的的關(guān)鍵技術(shù),如隨機線性網(wǎng)絡(luò)編碼、基于網(wǎng)絡(luò)編碼的可靠傳輸及基于網(wǎng)絡(luò)編碼的機會路由等進行了細致的分析與研究,主要創(chuàng)新點如下:1.應(yīng)用SIMD實現(xiàn)了隨機線性網(wǎng)絡(luò)編碼的硬件加速。雖然隨機線性網(wǎng)絡(luò)編碼已經(jīng)被證明可以達到多播容量的上限,但受限于其較低的編解碼速率,隨機線性網(wǎng)絡(luò)編碼并沒有被應(yīng)用于商用領(lǐng)域。本文分析了隨機線性網(wǎng)絡(luò)編碼的復雜度,指出在隨機線性網(wǎng)絡(luò)編碼中行運算占用了 99%的編解碼時間,因此提高隨機線性網(wǎng)絡(luò)編碼效率的重點在于提高行運算的效率。本文提出預查表的思想,應(yīng)用SSE3指令PSHUFB將行乘運算轉(zhuǎn)換為對GF(28)乘法表的并行查找。實驗結(jié)果表明,在IntelT55001.66G桌面機上對128個大小為4096字節(jié)的信息塊進行運算,編碼速率可達到24.522MB/second,比同類的SIMD優(yōu)化算法性能高5-6倍。2.構(gòu)建了一個輕量級的、基于NACK的可靠多播協(xié)議,其中網(wǎng)絡(luò)編碼作為差錯恢復策略。提出了"反饋輪"機制,使用"反饋輪"在發(fā)送端與接收端、接收端與接收端之間進行同步,將接收端等待修復的時間平均到每一輪,防止了抖動。實驗表明,在最大發(fā)送速率為2Mbps、編碼組長度為128個1000字節(jié)信息塊的設(shè)定下,該協(xié)議的吞吐量是因特網(wǎng)標準NORM協(xié)議的1.5倍以上。3.對無線Mesh網(wǎng)絡(luò)中基于網(wǎng)絡(luò)編碼的動態(tài)多源多播模型進行了分析與研究,給出了該模型的啟發(fā)式實現(xiàn)MulSrc。在MulSrc中,我們引入了虛擬分組"信用度"的概念,并給出了新的"信用度"統(tǒng)計方法。通過"信用度"的分配,MulSrc將速率分配、流控制和路由同實際的分組發(fā)送分離開來,簡化了協(xié)議設(shè)計。性能分析與仿真實驗表明,在存在多個多播流的網(wǎng)絡(luò)上,MulSrc可以取得比同類協(xié)議Pacifier更好的性能。4.提出了一個應(yīng)用于無線Mesh網(wǎng)絡(luò)單播機會路由的效用優(yōu)化模型,旨在最大化網(wǎng)絡(luò)吞吐量,并在各個流之間均衡地分配資源。給出了該模型對偶算法的漸近最優(yōu)性證明及該對偶算法的啟發(fā)式實現(xiàn)MulPro,應(yīng)用可控的要素,如流的選擇、傳輸速率的控制等,以實際發(fā)送的分組數(shù)量指引流量分配。提出了一個類似于TCP協(xié)議的擁塞控制機制,根據(jù)當前網(wǎng)絡(luò)狀況控制源節(jié)點的發(fā)送速率,實現(xiàn)準可靠傳輸,從而更能適應(yīng)允許少量丟失的實時應(yīng)用的需求。性能分析與仿真實驗表明,算法在稠密網(wǎng)絡(luò)上及存在多個流的條件下,可以取得比同類的MORE協(xié)議和NCMR協(xié)議更大的吞吐量、更低的網(wǎng)絡(luò)整體開銷和更合理的帶寬資源的分配。5.擴展了僅使用流內(nèi)編碼的優(yōu)化結(jié)構(gòu),將流內(nèi)網(wǎng)絡(luò)編碼看作一種特殊的流間網(wǎng)絡(luò)編碼,提出了一個無線Mesh網(wǎng)絡(luò)上的、結(jié)合流內(nèi)和流間網(wǎng)絡(luò)編碼的效用優(yōu)化模型。證明了該優(yōu)化結(jié)構(gòu)對偶算法的漸近最優(yōu)性,并給出了該算法的啟發(fā)式實現(xiàn)MiiCode。MiiCode依據(jù)節(jié)點上"編碼信用度"隊列的積壓以統(tǒng)一的方式對流間編碼和流內(nèi)編碼方式進行選擇,并利用隨機線性網(wǎng)絡(luò)編碼的特性簡化協(xié)議設(shè)計。性能分析與仿真實驗表明,在大部分情況下,MiiCode比使用確定路徑的COPE協(xié)議具有更高的性能、比MulPro具有更好的適應(yīng)性。本文提出的機會路由算法MulSrc、MulPro和MiiCode主要針對任意時刻總是連通的無線Mesh網(wǎng)絡(luò)上的、允許一定丟失、延遲要求較小的應(yīng)用,考慮如何利用無線鏈路的廣播特性和終端的空間多樣性來提高無線網(wǎng)絡(luò)的吞吐量和傳輸可靠性。協(xié)議位于IP層和MAC層之間,提供準可靠傳輸,主要考慮大尺寸流媒體數(shù)據(jù)。
[Abstract]:Network encoding theory in 2000 by Ahlswede and the concept of network information flow based on the proposed, it has been used in network security, routing algorithm and reliable transmission and other fields. The wireless network based on the key technology of network encoding, such as random linear network encoding, reliable transmission network encoding and network encoding based on opportunistic routing the thorough analysis and Research on the main innovations are as follows: 1. the application of SIMD to realize the random linear network encoding hardware acceleration. Although the random linear network encoding has been shown to achieve the multicast capacity limit, but limited to the codec rate low, random linear network encoding has not been applied to the commercial field. This paper analyzes the complexity of random linear network encoding, that occupies in the random linear network coding and decoding arithmetic encoding bank 99% of the time, so the increase The key machine of linear network encoding efficiency is to improve efficiency for operation. This paper pre look-up table theory, application of SSE3 command will be converted to PSHUFB multiplication on GF (28) parallel search of the multiplication table. The experimental results show that the IntelT55001.66G desktop information on the 128 block size is 4096 bytes for operation that the encoding speed can reach 24.522MB/second, compared to similar SIMD 5-6 times high performance.2. algorithm optimization is constructed with a lightweight, NACK reliable multicast protocol based on the network encoding as the error recovery strategy is proposed. The "Feedback Wheel" mechanism, use the "feedback" in the sending end and receiving end, synchronization between and the receiving end, the receiving end waiting for repair time per round, to prevent jitter. Experiments show that in the maximum transmission rate is 2Mbps, encoding group length is 128 1000 byte message block set, the co On the Internet the throughput is 1.5 times more than the standard NORM protocol.3. has carried on the analysis and research of dynamic multicast model of multi-source network encoding based on wireless Mesh network, gives a heuristic implementation of the model MulSrc. in MulSrc, we introduce the concept of virtual packet "credit", and gives a new credit "statistical methods. Through the" allocation of credit ", MulSrc rate allocation, packet flow control and routing with the actual transmission separated, simplifies the protocol design. Performance analysis and simulations show that in the presence of multiple multicast network, MulSrc can achieve similar performance than.4. protocol Pacifier better the utility model is applied to optimization of a wireless Mesh network unicast routing opportunity, aimed at maximizing the network throughput, and balanced allocation of resources in each flow is given. The algorithm of dual asymptotic model A heuristic proof of optimality and the duality of MulPro algorithm, such as the application of controllable elements, choice, transmission rate control, the number of packets transmitted. The actual flow distribution guide presents a protocol similar to TCP congestion control mechanism, according to the current network conditions to control the sending rate of the source node, realize the reliable transmission, so it can adapt to real-time applications allow a small amount of lost demand. Performance analysis and simulations show that the algorithm in the dense network and multiple flow conditions, can be more than the same kind of MORE protocol and NCMR protocol throughput,.5. distribution network overall lower overhead and more reasonable bandwidth the expansion of the structure optimization only stream encoding used, the network encoding stream as a special network encoding flow, proposes a wireless Mesh network, combined with the flow and flow The utility optimization model of network encoding. Prove the asymptotic optimality of the dual structure optimization algorithm, and gives the MiiCode.MiiCode algorithm based on heuristic node "encoding credit backlog queue in a unified way between convection and the intra flow encoding encoding, and simplify the design by using the characteristic of random linear network protocol encoding. Performance analysis and simulations show that in most cases, MiiCode has higher performance than using COPE protocol to determine the path, has better adaptability than MulPro. This machine will MulSrc routing algorithm, MulPro and MiiCode is mainly aimed at any time is always connected the wireless Mesh network, allowing a certain loss small, delayed application requirements, consider how to use the radio terminal wireless link characteristics and space diversity to improve network throughput and Transmission reliability. The protocol is located between the IP layer and the MAC layer, providing quasi reliable transmission, mainly considering large size streaming media data.

【學位授予單位】：南京理工大學
【學位級別】：博士
【學位授予年份】：2016
【分類號】：TN92

【參考文獻】

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

1 陳晨;董超;茅婭菲;陳貴海;王海;;無線網(wǎng)絡(luò)編碼感知路由綜述[J];軟件學報;2015年01期

2 王偉平;陳小專;魯鳴鳴;王建新;;應(yīng)用累積系數(shù)確認的網(wǎng)絡(luò)編碼機會路由協(xié)議[J];軟件學報;2014年07期

3 田賢忠;周前偉;;一種基于流內(nèi)與流間網(wǎng)絡(luò)編碼的無線路由算法[J];電子學報;2013年02期

4 王萬良;李桂森;姚信威;岑躍峰;;車載自組網(wǎng)中基于滑動窗口的網(wǎng)絡(luò)編碼傳輸策略[J];計算機科學;2012年09期

5 肖瀟;楊路明;王偉平;;高損耗無線網(wǎng)絡(luò)中基于網(wǎng)絡(luò)編碼的廣播重傳策略[J];中南大學學報(自然科學版);2008年06期

6 許胤龍;詹成;羅文;李沛;;Ad hoc網(wǎng)絡(luò)中基于網(wǎng)絡(luò)編碼的可靠組播[J];中國科學技術(shù)大學學報;2008年07期

7 呂凌;于宏毅;;一種基于空時碼的協(xié)作網(wǎng)絡(luò)編碼技術(shù)及其性能分析[J];電子與信息學報;2008年07期

8 姜博;晏堅;蔣衛(wèi)東;;噴泉碼及其在通信網(wǎng)絡(luò)中的應(yīng)用[J];數(shù)字通信世界;2007年10期

，

本文編號：1550845