Research On Network Coding In Three-source Sum-Networks

Along the flourish development of science and technology, and the better construction of global information technology, the network brings us great changes. Today, the emergency of new types of network applications and the surge of users make the existed network resources extremely scarce. Network coding is a new type of data transmission technology. Compared with traditional routing way which can only store and forward messages at intermediate nodes, network coding also can encode the information they received. Network coding can effectively improve the data transmission performance, and has the advantages of increasing the throughput, balancing network load, lowering energy consumption, of the nodes and enhancing the robustness of the network, etcl. However, due to the encoding and recoding of nodes, the transmission delay and computational complexity are increased.Currently, the research on network coding capacity of sum-network with a single source and linear network coding algorithm has achieved some outstanding results. However, when the number of the source and sink is larger than1, the relationship between network coding capacity and the upper minimum cut bound as well as the information rate is not sufficient. In addition, there are algorithms takes a lot of time to determine whether the global coding vectors are linearly independent or not. It increases the complexity of the algorithm. And the algorithms are mostly theoretical analysis.In view of the above problems, in this paper we make research on network coding capacity and linear network coding algorithm of the sum-network.We consider directed acyclic sum-networks with m sources and n sinks where each source generates one i.i.d. random process over a finite field and all the sinks want to recover the sum of the random process. The different source processes are assumed to be independent. In these sum-networks, each intermediate node has the ability to encode.In this paper, our main contributions are:1. We investigate on the capacity of such networks. As demonstrated, the upper bound of network coding capacity is the minimum of the minimum cut. At first, the lower bound on network coding capacity of multi-source multi-sink sum-networks are analyzed and summarized. Then, a lower bound on network coding capacity of sum-networks with at least three sources or three sinks is presented. And a value of network coding capacity of sum-network with three sources and three sinks and minimum cut2is given and proved.2. One simple network coding method for sum-network with three sources and three sinks are introduced. In the first step, we present structural decomposition of network. Any internal vertex which has total degree at most3is classed into type (3,3),(3,2),(2,3) and other by the number of sources and sinks it connects. Then assignment greedy network coding network vectors to each of them. In the end, the messages the sink received are summed together. Followed, in the eye of paths between sources and sinks, the feasibility analysis of the transmission method is given by using induction.3. Based on the shortest path algorithm in graph theory and the generic linear network coding algorithm, a novel multicast linear network coding algorithm is proposed. A virtual node is introduced to change the multi-source network into a single source network in the algorithm. In the shortest path Dijkstra reduction network, using Dijkstra algorithm to select the shortest paths from the source to the sink to simplify the process of obtaining global coding vectors. Then we can ensure that the sink can recover messages received from the source. Finally, simulation results show that the algorithm is effective, and indicates the superiority of the algorithm in lowering energy consumption of the nodes and balancing network load.