Linear Network Coding Research

Network coding is first introduced by R.Ahlswede et.al.in 2000. Network coding can increase network capacity, improve the robustness and security, since the intermediate nodes are allowed to perform processing operations on the incoming packets, instead of just to forward them. The researches on network coding involve the knowledges about information theory, computer communication networks, multicast technique, multiple user information theory and graph theory. Network coding can be widely applied in the Internet, P2P systems, wireless network, the distributed file store and network security.The maximum flow problem is a focus of the studies about graph theory, operational research, optimization theory. The basic idea of some existing algorithms, such as the well-known Ford-Fulkerson algorithm and Dinic algorithm, is to find all augmenting paths. Recently Wu Yan et. al. proposed a new method to compute the network maximum flow based on the flow matrix. The main idea of this method is to balance the incoming flows and the outgoing follows at each of the intermediate nodes and to iteratively reduce the order of the flow matrix without changing the maximum flow. This method is simple and easy for realization. Howerer, it reduces the order of the flow matrix one by one, and all the balance number should be calculated before reducing the order. In particular, the matrix order is very large in the begining, and the matrix is far from the balance state in most cases, therefore this method is still very complex. This method is improved in this thesis. According to Maximum flow Minimum cut theorem, we show for the flow matrix some properties which are useful for reducing the matrix order. According to these properties, it is unnecessary to calculate the balance number before reducing the matrix order. In particular complex computations are avoided in the begining.According to the relationship between the inputs and outputs of the nodes, network coding may be divided into linear NC and nonlinear NC. R.W.Yeung et al. proved that for a single-source acyclic network, linear NC can achieve the maximum flow. Linear NC can meet different levels of data transmission demands in the mean while. According to demands of data transmission in each local area network, this thesis proposed the concepts of linear local-area multicast, linear local-area broadcast, linear local-area dispersion, the general linear local-area network coding. The realtionships between them are also studied. This thesis proposed a construction algorithm for the general linear local-area network coding. In this algorithm, at the non-public channels it needs only to check the linear independence with vector group in the local area Fi (not the whole graph G ) which hasω?1 global vector. The number of checks decreases significantly. Considering each local area has only one sink, this thesis also proposed a special construction algorithm for the general linear local-area network coding. This algorithm encodes the channels in each local area Fi , and then processes the public channels. The expansibility of this algorithm is very strong. The algorithm can also be used to construct linear local-area multicast and linear multicast.