【作者】 王蔚；

【导师】 朱光喜； 喻莉；

【作者基本信息】 华中科技大学 ， 信息与通信工程， 2011， 博士

【摘要】 网络传输自TCP/IP协议诞生并取代原始ATM交换方式以来,数年来未有大的改动。2000年,Ahlswede、Cai和Li等人提出“网络编码”的新概念,将网络上的信息处理技术带入了新的时代,尤其对于网络多播场景,通过网络编码的方式进行信息融合后,可大幅度提高多播传输速率。网络编码技术使得多播网络传输上的研究主题由信息内容分发转变成信息容量界定。然而,在以数据包作为网络信息传输和处理载体的传统方式中,由于存在传输冗余过大、处理复杂度高和理论建模较为繁琐等问题,难以应对未来社会网络规模大、用户多和信息业务多样化等多方面的需求,势必将被以信息流作为信息承载和网络交换的基本单位这种新型方式所取代。因此,本文以信息流在多播网络的表现形式和应用方式为主题展开研究。如今的网络信息流已不再是ATM时代狭义上的信息流,而是广义上基于网络信息论的、具有多种表现形式且难以简单用香农定理量化的信息承载方式。它具有易统计、易处理、易纠检错和低损耗的特点,更能适应未来超大规模网络通信的需求。另外在实际网络的应用中,这一概念将和其他类型的学科技术交融,如图论、排队论。基于以上思想,本文首先分析多播网络下网络编码的本质和网络信息流的定义,然后研究信息空间的自由度、信息流的新型网络编码算法以及在实际网络系统中的应用。基于网络编码的网络信息流在理论上可以达到网络多播的传输最大流,实际中则需要结合各种理论知识建模、设计适合不同多播场景的传输机制,最终逼近理论极限。本文的主要研究方向包括以下几个方面：第一,基于线性空间对多播网络的信息流建模,进而基于此信息流模型对多播网络的容量进行分析,并通过与最优路由算法下的多播传输进行各方面性能比较,展示网络编码给多播网络带来的增益和优势。然后,通过对网络编码的各种算法进行比较总结,提出以网络信息流为处理对象的新型网络编码算法,即混洗网络编码。该算法可有效降低编码和解码的复杂度。第二,结合图论,将混播交换上的阻塞问题转化为基于信息流的改进冲突图(Enhanced Conflict Graph)上的着色问题,分析网络编码解决此类问题的原理并推出结合范德蒙矩阵而形成的半随机网络编码方式,弥补以往在换结点(本文以网络交换机为例)上运用网络编码技术的缺陷,使编码复杂度大幅度降低。第三,分析应用网络编码技术的交换机所对应的基于帧的改进冲突图,通过提取信息流和分析信息流内网络编码的实质,揭示原有调度算法无法高效支持网络编码算法的实质,从而提出编码驱动的交换机调度算法,增加信息流内网络编码的机会,达到进一步提升交换吞吐率的目的。第四,在多感知中继这一协同通信模式下,应对无线媒介容易信息丢失后冗余重传这一问题,对通过不同感知信道的信息划分得到网络信息流并建模；提出基于无线信道的信息流熵估计机制,和缓存编码算法的编码感知传输协议,从而有效减少冗余,显著地提高了频谱利用率。通过对多播信息流流的建模和理论分析,本文验证网络编码对网络传输改进的有效性,然后对各类应用场景建模,基于网络编码的思想进行信息流建模并设计传输机制,显著地提高了实际网络的传输速率和处理效率。基于理论分析,本文还分别引用实验数据对所提的算法机制进行了验证。理论分析和实验结果同时表明,采用信息流建模的方式对多播任务设计调度算法和传输协议,更有利于网络编码在实际网络的融合,进一步减少传输中信息冗余度,提高传输效率。更多还原

【Abstract】 Since the ATM switching was placed by packet switching in TCP/IP protocols, there are rarely major revisions on transmission protocols for several decades. However, the situation has been changed by introducing a new technology called as network coding, which are presented by Ahlswede et al.. It brought a new age for information theory. With network coding, information can be distributed after integration in multicast scenarios, which noticeably increases transmission rates. With the leverage of network coding in multicasts, the subject of transmission is not how to distribute the information, but the capacity of network information flow. In the traditional schemes, information is delivered and processed in packets, which brings burdens due to redundancies, computing and modeling complexity. The burdens become huge when the network scale grows with large group of clients and the corresponding growing requirements on services. One of the approaches to lower the burdens is to transmit and process information by flow. As the main motivation of my research work, the questions rise about how to represent information flows and how to apply them.Network information flow in this thesis is not the information flow defined for ATM switching. Based on network information theory, it can be formed as multiple specifications in different functions, like vector for coding, such that the entropy of the flow is hardly defined by Shannon’s theory. However, it is much simpler to measure, process and correct in big scaled network with much lower cost than packet switching. To apply information flow in real network, we should further consider the leverage with other theory, such as graph theory and queue theory.With the aforementioned conceptions, the thesis first presents the definition of network information flow and the core idea of network coding. I also discuss a new metric, which is called the degree of freedom, to measure the dimension of information flow field. Based on flows, I explored new approaches applying network coding to be compatitable with different multicast scenarios, as well as the corresponding revisions on transmission protocols. In theory, network coding can assists multicast transmissions to achieve their maximum flow, which are the upper-bounds of transmission rates. However, in practice, the upper-bounds are hard to achieve without specially designed transmission schemes, which are referred by theoretical results. The research interests and the corresponding contributions of this thesis are list as follows.First, I establish a linear space model for information flows and explain the maximum flow in multicast networks based on the model. Furthermore, I analyze the capacity of multicast networks, and show the advantages to apply network coding in multicast networks by comparing with the optimal results by fractional routing in traditional protocols. After the illustrations of various coding algorithms for network coding, I present a novel coding algorithm to employ flow as the coding unit and shuffle them for coding, which lowers the complexity for both encoding and decoding.Second, I studied the Head of Line blocking problem in network multicast switches and deduce the problem as the graph coloring problem. The function of network coding in multicast switches is presented as well as the proof on its promising enhancement. I further propose a new coding algorithm based on Vandermond matrices, which can lower the requirements of coding processes on switch buffer as well as the complexity.Third, based on the theoretical results in my second contribution, I further analyze the gap between theory and practice when applying network coding in frame-based multicast switches. To assist network coding in switches, I propose a so-called Coding-Driven scheduling algorithm instead of traditional scheduling policies, and enhance performances of switches with network coding.Fourth, under the mode of cognitive relay with multiple assistants,I aim to handle the lost information when propagating through wireless medium. With the character of wireless broadcasting in the spectrum, the information flows go through different sensing channels synchronically. A further estimation on the entropy of end-to-end information flows is made in the model according to CSI (Channel State Information). Accordingly, with network coding, I propose a so-called CodeAssist relay protocol, which can decrease the redundancy of relay and enhance the efficiency to use the spectrum.According to analysis on network properties, the promise of network coding on network transmission is given in this thesis. By establishing universal models in different applications, I analyze the properties of information flows and revise the correlated transmission schemes to enhance the efficiency. I also support the information flow theory by empirical results. It is demonstrated in both theoretical and empirical phases that, to model and design transmission protocols for network multicast missions with integrated information flows will benefit the leverage of network coding in practice. It will definitely decrease the redundancies in transmissions and enhance the transmission efficiency.更多还原