Study On Linear Network Coding For Single-source Directed Acyclic Network

Ahlswede et al. put forward the theory of network coding, that is the intermediate nodes in the network can process the input data stream, for the first time in 2000. The theory can not only realize the function of store-forward of traditional routing, but also realize the information processing, so that improving the performance of the network. Network coding changes the way of information processing and transmission in communication network completely and overturns the traditional concept that the intermediate nodes in the network processing the input data will not bring any benefits, so it is one of the most important theoretical results in the field of information processing and transmission in the 21 st century.Linear network coding, as a technology with simple coding scheme and obtaining the maximum flow of multicast, has caused wide public concern.The problem of network maximum has been a subject of much research interest in the fields of graph theory, optimization theory and operational research. Different from the classical algorithms which are based on augmenting path strategy or preflow-puch strategy,the algorithm of network maximum flow based on network flow matrix proposed by WU et al.adopts the idea of the node flow balance, problem conversion and reducing the matrix order,which provides a new way to solve the problem of maximum flow. The method is simple to operate and easy to implement, but it also has some deficiencies. For example, only reducing one step at each time, and all the balance numbers should be calculated before reducing the order. Especially when a large number of nodes exist in a network, reducing the order is more complicated. This paper studies some new properties of network flow matrix according to Max-Flow Min-Cut theorem, and all the balance numbers need not to be calculated before reducing the order, thus avoiding a lot of computation at the early stages of reducing the order and improving the original algorithm.The research of linear network coding has achieved a reasonable result so far. In this paper, the concept of type-preserving conversion matrix is proposed to describe the conversion relationship between two linear network coding of the same type but of different rates, and an effective construction plan of transformation matrix for linear multicast is put forward, which has a certain significance for the study of variable-rate linear network coding.In addition, to overcome the shortcoming of linear broadcast and linear dispersion network coding for decoding space dimension, a new style of linear network coding which is calledstrict linear network coding is introduced. Then, combining with a special data packaging strategy, the application advantages of strict linear dispersion network coding is demonstrated.In the past several years, the theoretical research of network coding mainly focuses on fixed-rate linear network coding. However, in the practical network in which flow varies dynamically, the source transmits messages at different rates in different time sessions. This needs to built variable-rate linear network coding, which can support a set of possible transmission rate. So far, when the source rate varies, there are two algorithms which are based on reduction vector and transformation matrix respectively. In the algorithms any non-source nodes have the same local encoding kernels for different transmission rate, but the acquisition of global encoding kernels is complicated. This paper uses the concept of strict linear network coding to propose an effective construction plan, which implements variable-rate linear dispersion with a fixed-rate linear network coding.