Study On Random Linear Network Coding And Its Applications

Network coding is a kind of new technology, which is proposed in recent years to reach the maximum transmission rate. Different from the traditional routing technology where each node simple stores and forwards the incoming packets, network coding allows intermediate nodes to do linear or nonlinear process of the received information and forward. Compared with the traditional routing approach, network coding has been proved to have incomparable advantages in improving the throughput, reducing transmission delay, reducing the transmission energy consumption, increasing the robustness of system and so on. Meanwhile network coding has been applied to many fields.Typically, because of its simple operation, and low encoding/decoding complexity, random linear network coding (RLNC) has been widely applied to the practical networks, where the intermediate nodes in the network are allowed to pick a random element as the combination coefficient. The research has indicated that the successful decoding probability can be very high, as the finite field size goes to infinity. This method brings two disadvantages, one of which is required to increase the size of the coding field in communication network, the other one is the correct transmission with a certain probability. Coding coefficients are selected frequently from the coding field to do encoding or decoding operation. If the size of coding field selected is too small, the successful decoding probability at the sink node is too low. That will not be conducive to the possible practice operation. If the size of coding field selected is too large, the encoding and decoding complexity are very high. This will result in the loss of energy and time wasting. Obviously, when the successful decoding probability is fixed, reducing the size of coding field is a significant research topic. For this problem, we have done some in-depth research and achieved some results. The main contributions are listed as follows.The first part gives an efficient polynomial time algorithm for the design of robust linear multicast network code construction by combining techniques from linear algebra, robust network flows, and randomization. For convenience, this algorithm is denoted by Algorithm RPR. We give a general model of single source multicast network with packet loss, present the specific steps in Algorithm RPR based on this model, then analyze the performance of this algorithm, including the successful decoding probability and time complexity, finally show the theoretical gain of the algorithm by analyzing the advantage in reducing the number of edges in large scale network, and the contribution in reducing the size of coding field through two specific network (i.e. the butterfly network and the combinatorial network).By constructing Algorithm RPR, an existence of a network code is equivalent to a combinatorial problem of arranging flows from the source node to the sink node. Compared with routing protocol, network coding has been show to offer advantages in achieving the maximum transmission rate. The process of network coding is essentially dealing with in the busy edge. If there is no busy channel in network, there exists a routing solution to achieve the maximum transmission rate. If the network is a minimal multicast network, the number of required coding edges in Algorithm RPR is minimal to achieve the network capacity.The second part researches the successful decoding probability problem in a class of combinatorial network. The combination is a basic method to construct the network, and combinatorial networks are applied in various fields, for example, the structure of block cipher by combinatorial network, analysis of city road network with combination network and so on. According to the analysis of successful decoding probability problem in combinatorial topology of random linear network coding without packet loss, two closed form expressions of exact decoding probability at a sink node and at all sink nodes are given. Based on the closed form solution, when the successful decoding probability is fixed, the minimum cardinality of the coding field can be determined. Through these expressions, we also analyze the effect of main parameters on the decoding performance, which are the number of relay nodes, the number of sink nodes, and the cardinality of the selected coding field. According to the analysis of successful decoding probability problem in combinatorial topology of random linear network coding with packet loss, two lower bounds of successful decoding probability at a sink node and at all sink nodes are given.The third part studies the successful decoding probability of random linear network coding in tree networks. In the emergency field, the network is commonly used in environmental monitoring, disaster information acquisition and so on. Therefore, according to the real demand of disaster environment, in this case, the hierarchical structure is a very convenient distributed management. From the network topological perspective, hierarchical structures can be reduced to tree-type networks. In addition, tree structured networks are scalable to expand coverage by increasing the depth of tree networks due to their flexibility and low delay, making it suitable for a variety of emergency applications. We further consider tree networks with and without packet loss, derive closed-form probability expressions of successful decoding at a destination node and at all destination nodes in this multicast scenario, investigate the impact of the major parameters, i.e., the size of finite fields, the number of internal nodes, the number of sink nodes and the channel failure probability, on the decoding performance with simulation results.