本文選題：網(wǎng)絡(luò)編碼 + 組播網(wǎng)絡(luò)　； 參考：《浙江理工大學(xué)》2012年碩士論文

【摘要】：網(wǎng)絡(luò)編碼是一種新穎的網(wǎng)絡(luò)傳輸技術(shù)，最早于2000年，由香港中文大學(xué)的Ahlswede等人首次提出。與傳統(tǒng)路由組播方式只允許中間節(jié)點(diǎn)轉(zhuǎn)發(fā)接收信息不同，網(wǎng)絡(luò)編碼理論允許中間節(jié)點(diǎn)對(duì)接收到的信息進(jìn)行編碼處理，再轉(zhuǎn)發(fā)出去，信宿節(jié)點(diǎn)通過(guò)解碼運(yùn)算譯出信源發(fā)出的信息。網(wǎng)絡(luò)編碼可以實(shí)現(xiàn)由最大流最小割定理所決定的組播網(wǎng)絡(luò)的理論信息流傳輸容量。網(wǎng)絡(luò)編碼具有提高網(wǎng)絡(luò)吞吐量、魯棒性等優(yōu)點(diǎn)，已經(jīng)被廣泛應(yīng)用于無(wú)線Ad Hoc網(wǎng)絡(luò)、傳感器網(wǎng)絡(luò)、P2P內(nèi)容分發(fā)、分布式文件存儲(chǔ)和網(wǎng)絡(luò)安全等領(lǐng)域，其研究結(jié)合了信息論、計(jì)算機(jī)通信網(wǎng)絡(luò)、組播技術(shù)、多用戶信息論和圖論等多方面的知識(shí)。自網(wǎng)絡(luò)編碼理論提出以來(lái)，關(guān)于網(wǎng)絡(luò)編碼理論及其應(yīng)用的研究已經(jīng)成為網(wǎng)絡(luò)信息界的熱點(diǎn)之一。 網(wǎng)絡(luò)編碼理論在充分利用網(wǎng)絡(luò)理論組播速率的同時(shí)，也帶來(lái)了相應(yīng)的開銷，如中間節(jié)點(diǎn)進(jìn)行編碼處理帶來(lái)的計(jì)算開銷和存儲(chǔ)開銷，信宿節(jié)點(diǎn)進(jìn)行解碼計(jì)算引入的時(shí)延，編碼節(jié)點(diǎn)需要具有編碼能力的網(wǎng)絡(luò)硬件設(shè)備等。如何在應(yīng)用網(wǎng)絡(luò)編碼技術(shù)充分利用網(wǎng)絡(luò)傳輸能力的同時(shí)，盡可能的減少時(shí)延和各種開銷，是網(wǎng)絡(luò)編碼在實(shí)際應(yīng)用中所要解決的重要問(wèn)題。 在本文我們主要做了以下2個(gè)方面的工作： 1.針對(duì)應(yīng)用于大規(guī)模網(wǎng)絡(luò)環(huán)境中的隨機(jī)線性網(wǎng)絡(luò)編碼算法的編解碼吞吐率較低的情況，結(jié)合GPU高度并行的特性，本文提出了一種基于GPU并行加速的線性網(wǎng)絡(luò)編碼算法，該并行算法程序主要借助了英偉達(dá)于2007年6月推出的基于GPU的通用計(jì)算模型：CUDA統(tǒng)一架構(gòu)，，將實(shí)現(xiàn)過(guò)程轉(zhuǎn)化成CUDA多線程的并行計(jì)算過(guò)程，在GPU中實(shí)現(xiàn)了加速，提高了編碼和解碼的吞吐率，減少了編碼和解碼操作帶來(lái)的計(jì)算時(shí)延，有利于網(wǎng)絡(luò)編碼在流媒體服務(wù)等實(shí)時(shí)網(wǎng)絡(luò)中的應(yīng)用。 2.對(duì)于已知拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)，本文研究了其網(wǎng)絡(luò)編碼資源開銷優(yōu)化問(wèn)題，即尋找具有最小編碼節(jié)點(diǎn)或編碼鏈路的編碼方案，以及代數(shù)型網(wǎng)絡(luò)編碼框架下的編碼優(yōu)化模型，并對(duì)應(yīng)用于編碼優(yōu)化中的啟發(fā)式-遺傳算法進(jìn)行了分析和研究，該算法產(chǎn)生一個(gè)優(yōu)化結(jié)果往往需要幾個(gè)小時(shí)，且難以得到最優(yōu)解，針對(duì)以上情況，本文提出了一種基于GPU并行加速的遺傳算法的解決方案，并在算法中加入了新的處理步驟，不僅減少了遺傳算法每次循環(huán)所需要的時(shí)間，而且解決了算法的局部性問(wèn)題和收斂速度較慢的問(wèn)題。然后通過(guò)仿真實(shí)驗(yàn)和結(jié)果分析，從算法的有效性，收斂性能，運(yùn)行時(shí)間等方面進(jìn)行了驗(yàn)證。 最后，對(duì)本文的研究工作進(jìn)行了總結(jié)，并指出了本文的不足以及下一步的研究?jī)?nèi)容和方向。
[Abstract]:Network coding is a novel network transmission technology, which was first proposed by Ahlswede et al of the Chinese University of Hong Kong (CUHK) in 2000.Different from the traditional routing multicast mode which only allows intermediate nodes to forward received information network coding theory allows intermediate nodes to code and process the received information and forward it out.Network coding can realize the theoretical information flow transmission capacity of multicast networks determined by the maximum flow minimum cut theorem.Network coding has been widely used in wireless Ad Hoc networks, sensor networks, P2P content distribution, distributed file storage and network security.Computer communication network, multicast technology, multi-user information theory and graph theory and other aspects of knowledge.Since the theory of network coding was put forward, the research on network coding theory and its application has become one of the hot topics in the field of network information.Network coding theory not only makes full use of the multicast rate of network theory, but also brings the corresponding overhead, such as the computation overhead and storage overhead brought by the intermediate node coding processing, the delay caused by the decoding calculation of the host node.Coding nodes need network hardware devices with coding capability.How to use the network coding technology to make full use of the network transmission ability and reduce the delay and all kinds of overhead as much as possible is an important problem to be solved in the practical application of network coding.In this paper, we mainly do the following two aspects of work:1.In view of the low throughput of random linear network coding algorithm applied in large-scale network environment and the high parallelism of GPU, a linear network coding algorithm based on GPU parallel acceleration is proposed in this paper.The parallel algorithm program mainly uses the universal computing model: CUDA based on GPU, which was put forward by Nvidia in June 2007, to transform the realization process into the parallel computing process of CUDA multithreading, and accelerates it in GPU.It improves the throughput of coding and decoding, reduces the computational delay caused by coding and decoding operations, and is conducive to the application of network coding in real-time networks such as streaming media services.2.For the network with known topology, this paper studies the optimization problem of the network coding resource overhead, that is, to find the coding scheme with the minimum coding node or the coding link, as well as the coding optimization model under the algebraic network coding framework.The heuristic genetic algorithm used in coding optimization is analyzed and studied. It takes several hours for the algorithm to produce an optimization result, and it is difficult to obtain the optimal solution.In this paper, a solution of genetic algorithm based on GPU parallel acceleration is proposed, and a new processing step is added to the algorithm, which not only reduces the time required for each cycle of genetic algorithm.Moreover, the localization problem and the slow convergence rate of the algorithm are solved.Then, the validity, convergence performance and running time of the algorithm are verified by simulation experiment and result analysis.Finally, this paper summarizes the research work, and points out the shortcomings of this paper, as well as the next research content and direction.
【學(xué)位授予單位】：浙江理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2012
【分類號(hào)】：TN915.01;TP338.6

【參考文獻(xiàn)】

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

1 郝琨;金志剛;;一種最小化編碼節(jié)點(diǎn)的網(wǎng)絡(luò)編碼優(yōu)化算法[J];電子與信息學(xué)報(bào);2011年02期

2 鄧亮;趙進(jìn);王新;;網(wǎng)絡(luò)編碼下的編碼開銷-鏈路開銷聯(lián)合優(yōu)化[J];計(jì)算機(jī)研究與發(fā)展;2010年03期

3 吳恩華,柳有權(quán);基于圖形處理器(GPU)的通用計(jì)算[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2004年05期

4 黃政;王新;;網(wǎng)絡(luò)編碼中的優(yōu)化問(wèn)題研究[J];軟件學(xué)報(bào);2009年05期

5 鄧亮;趙進(jìn);王新;;基于遺傳算法的網(wǎng)絡(luò)編碼優(yōu)化[J];軟件學(xué)報(bào);2009年08期

6 陶少國(guó);黃佳慶;楊宗凱;喬文博;熊志強(qiáng);;網(wǎng)絡(luò)編碼研究綜述[J];小型微型計(jì)算機(jī)系統(tǒng);2008年04期

本文編號(hào)：1763539