面向无线网络的网络编码技术研究

发布时间：2018-03-01 06:34

本文关键词： SIMD 可靠传输多源网络编码机会路由效用优化模型流内网络编码流间网络编码　出处：《南京理工大学》2016年博士论文　论文类型：学位论文

【摘要】：网络编码理论在2000年由Ahlswede等基于网络信息流的概念提出,目前已被应用于网络安全、路由算法和可靠传输等领域。本文对无线网络上基于网络编码的的关键技术,如随机线性网络编码、基于网络编码的可靠传输及基于网络编码的机会路由等进行了细致的分析与研究,主要创新点如下:1.应用SIMD实现了随机线性网络编码的硬件加速。虽然随机线性网络编码已经被证明可以达到多播容量的上限,但受限于其较低的编解码速率,随机线性网络编码并没有被应用于商用领域。本文分析了随机线性网络编码的复杂度,指出在随机线性网络编码中行运算占用了 99%的编解码时间,因此提高随机线性网络编码效率的重点在于提高行运算的效率。本文提出预查表的思想,应用SSE3指令PSHUFB将行乘运算转换为对GF(28)乘法表的并行查找。实验结果表明,在IntelT55001.66G桌面机上对128个大小为4096字节的信息块进行运算,编码速率可达到24.522MB/second,比同类的SIMD优化算法性能高5-6倍。2.构建了一个轻量级的、基于NACK的可靠多播协议,其中网络编码作为差错恢复策略。提出了"反馈轮"机制,使用"反馈轮"在发送端与接收端、接收端与接收端之间进行同步,将接收端等待修复的时间平均到每一轮,防止了抖动。实验表明,在最大发送速率为2Mbps、编码组长度为128个1000字节信息块的设定下,该协议的吞吐量是因特网标准NORM协议的1.5倍以上。3.对无线Mesh网络中基于网络编码的动态多源多播模型进行了分析与研究,给出了该模型的启发式实现MulSrc。在MulSrc中,我们引入了虚拟分组"信用度"的概念,并给出了新的"信用度"统计方法。通过"信用度"的分配,MulSrc将速率分配、流控制和路由同实际的分组发送分离开来,简化了协议设计。性能分析与仿真实验表明,在存在多个多播流的网络上,MulSrc可以取得比同类协议Pacifier更好的性能。4.提出了一个应用于无线Mesh网络单播机会路由的效用优化模型,旨在最大化网络吞吐量,并在各个流之间均衡地分配资源。给出了该模型对偶算法的渐近最优性证明及该对偶算法的启发式实现MulPro,应用可控的要素,如流的选择、传输速率的控制等,以实际发送的分组数量指引流量分配。提出了一个类似于TCP协议的拥塞控制机制,根据当前网络状况控制源节点的发送速率,实现准可靠传输,从而更能适应允许少量丢失的实时应用的需求。性能分析与仿真实验表明,算法在稠密网络上及存在多个流的条件下,可以取得比同类的MORE协议和NCMR协议更大的吞吐量、更低的网络整体开销和更合理的带宽资源的分配。5.扩展了仅使用流内编码的优化结构,将流内网络编码看作一种特殊的流间网络编码,提出了一个无线Mesh网络上的、结合流内和流间网络编码的效用优化模型。证明了该优化结构对偶算法的渐近最优性,并给出了该算法的启发式实现MiiCode。MiiCode依据节点上"编码信用度"队列的积压以统一的方式对流间编码和流内编码方式进行选择,并利用随机线性网络编码的特性简化协议设计。性能分析与仿真实验表明,在大部分情况下,MiiCode比使用确定路径的COPE协议具有更高的性能、比MulPro具有更好的适应性。本文提出的机会路由算法MulSrc、MulPro和MiiCode主要针对任意时刻总是连通的无线Mesh网络上的、允许一定丢失、延迟要求较小的应用,考虑如何利用无线链路的广播特性和终端的空间多样性来提高无线网络的吞吐量和传输可靠性。协议位于IP层和MAC层之间,提供准可靠传输,主要考虑大尺寸流媒体数据。
[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

【参考文献】