Study On The Coding Complexity And Algorithms Of Network Coding

In 2000, from the perspective of information theory Ahlswede et al. proposed a new concept "Network Coding" in a creative way. And it made network and routing as an organic integration at the first time and established new network architecture. Unlike the traditional mode of store-and-forward, the information transmitted on the network can be compressed again, and thus it possible to achieve the Shannon upper bound on the capacity of the multicast networkNetwork coding completely change the existing mode of information processing and communication transmission, which is a major breakthrough in the field of information theory research. So it has attracted great attention of academia and engineering. Currently, network coding theory has the following several important questions:First, the encoding complexity of network coding. As the complexity of coding operations is higher than that of routing forwarding operation, it's better to have less coding operations as much as possible. It is important to study the relation between the minimal number of encoding nodes and the structure of network. Second, the constructions of network coding. How to construct network coding with low complexity is the first step to be applied in real networks. For the acyclic networks, there exist polynomial time encoding algorithms. Whether the existing algorithms can further reduce the complexity is an important issue we are concerned about. For the cyclic networks, the constructions of network coding are mainly concentrated on convolutional network coding. Although there exist polynomial-time algorithms, it is not conducive to realization. Especially compied the method used in acyclic networks to construct convolutional network codes for cyclic networks. Third, the constructions of secure network coding. Cai N. and Yeung R.W. proposed a scheme of secure network coding for secure communications. In a few years, the study on the secure network coding has flourished. In particular, the secure network coding against anti-active attack (or Byzantine attack) has not only attracted the attentions of the experts in informatics, but also cryptography experts. Informatics experts from the perspective of information theory design secure network coding to detect tampering at terminal nodes. But this means more restrictions on the network, so it is not conducive to practical application. The messages encoded by network coding are signed by digital signatures, and after receiving the messages intermediate nodes verify the truth of the messages and then determine the next operations. Although these methods can prevent the error messages from spreading, they have very high computational complexity. Therefore, how to combine these two approaches to design new secure network code is the next focus of the study.In this article, the author studies these issues in depth, and has several key research findings, mainly summarized as follows:1. Combine coloring theory and network decomposition we get the optimal solution for acyclic multicast network on the minimum number of encoding nodes. Based on the results for the acyclic networks, we further analysis the minimum number of encoding nodes in cyclic networks, and have a better result than that of Langberg's. For the encoding complexity of network coding in multicast, although Langberg et al. have had some important results, they do not completely solve the problem of the number of encoding nodes, particularly for the cyclic networks.2. Based on the new results of the minimal number of encoding nodes, we further analysis the Langberg algorithm and find that it complexity should be lower. Moreover, we reanalysis the time complexity of integral and fractional network codes.3. Combining Jaggi-Sanders algorithm and Mason formula in control theory we design a new algorithm for the construction of convolutional network code.4. Combining the methods used in information science and cryptography theory, we design a class of secure network coding. First, secure network coding against eavesdropping attacks; Second, secure network coding against Byzantine attacks; Third, the combination of the first two algorithms, which can be used against eavesdropping and Byzantine attacks.