Solvable Linear Network Coding Computational Complexity And Construct Method

Network coding is a new research area which is aimed to improve the efficiency of transmitting messages in communication networks. Traditional routing only allows the intermediate nodes to store and forward the messages, while network coding enables nodes to encode the messages and then forward them. The sinks do decoding to get original messages after they receive enough encoded messages.In a communication network, each node could get messages at rate of no more than its maxflow. For single source multicast networks, all the sinks could get messages simultaneously at the rate of the minimum value of their maxflow, furthermore, linear network coding is sufficient in this case.However, linear network coding for multicast networks does not utilize all the sinks capacities. This thesis proposes a new type of network code that is called maximum decodable linear network code, under which every sink could get messages at the rate of its own maxflow and could decode these messages.The thesis focuses on two facets of maximum decodable linear network coding: the computing complexity and the constructing method. We prove that it is NP-hard to decide whether there exists a maximum decodable linear network code for a given network from information flow perspective and algebraic perspective; and then present a simple greedy constructing algorithm and an improved heuristic method to construct maximum decodable linear network code based on the importance of channels.