Research On Network Coding For Heterogeneous Networks

Network coding, which generalizes traditional store-and-forward by allowing intermediate network nodes to generate new packets by performing algebraic operations on incoming packets, has shown advantages in many areas of communication and networking. From the beginning, most efforts are paid on the research on single-rate transmission schemes with network coding. However, networks are heterogeneous in general. Single-rate transmission could not fully utilize the network bandwidth resource to serve sink nodes of different capacities. To design efficient transmission strategies based on network coding for heterogeneous networks is a meaningful but challenging subject. This dissertation mainly researches network coding theory and technology to realize efficient multi-rate transmission and variable-rate transmission in heterogeneous networks.The work in the dissertation can be summarized as follows:In most existing layered multicast schemes, the rate of each linear multicast session is given. Only the multicast subgraphs are optimized. Thus, the maximal aggregate throughput achieved is affected by the given multicast rates. In this dissertation, we research the layered multicast scheme with optimal-selectable multicast rates. We deduce the necessary condition for optimal rates selection, and propose an optimal-rate-select scheme for layered multicast to maximize the aggregate throughput. Moreover, to apply this scheme in highly heterogeneous networks, we propose a Genetic Algorithm (GA) based method to solve our optimization problem. Simulation results demonstrate that combining with this GA-based method our optimization scheme could select the optimal rates for layered multicast efficiently.Since the layered multicast based on intra-session network coding must divide available network resources into separate network coding subgraphs, it is suboptimal in general. This dissertation investigates inter-session network coding for the distribution of layered encoded source data. We define special inter-session network codes--Inter-layer Hierarchical Random Linear Network Codes (IHRLNC), and propose the Inter-layer Hierarchical Multicast (IHM). To determine the optimal type of IHRLNC that should be performed on each edge in IHM, we formulate an optimization problem based on 0-1 integer linear programming, and propose a heuristic approach to approximate the optimal solution in polynomial time. Theoretical analysis and simulation results both show that our proposed IHM can achieve throughput gains over the layered multicast.The multi-rate transmission schemes based on multiple linear multicast sessions usually involve NP-hard optimization problem. To avoid this problem, this dissertation investigates the feasibility to realize multi-rate transmission with a single network coding session in heterogeneous networks. We propose a scheme based on specially packetized source data and random linear network coding, and deduce the success probability for a single linear broadcast network coding session to realize multi-rate transmission.Linear broadcast network code can guarantee that the dimension of linearly independent coded symbols received by each sink in the network achieves its own max-flow value. However, it may happen at these sinks that the independent network coded symbols received are completely undecodable. Facing this problem, we propose a new type of linear network code in this dissertation—the strict linear network code. We research the construction algorithm for the strict linear dispersion, the transition relationship from the general linear dispersion to the strict linear dispersion, and the advantages presented by the strict linear network codes when applied in heterogeneous networks. We also propose the static strict linear network codes for networks with link failures. Moreover, based on strict linear network codes or static strict linear network codes, we propose a special kind of hierarchical transmission schemes for heterogeneous networks, which can solve the undecodable problem inherent in the general linear network codes and indeed realize multi-rate transmission with a single network code session. Specially, the scheme realized with static strict linear network codes is also robust to the link failures suffered in the network.Most works in network coding to date focused on the fixed-rate linear network codes. However, in practical networks, the source may transmit messages at different rates in different periods according to the content and properties of the generated data. Hence, variable-rate linear network codes should be constructed, which is referred to as the linear network codes constructed on a common network that can support a range of possible transmission rates of the source. Few efforts have been paid on this subject. However, this dissertation investigates the unified framework and efficient construction schemes for variable-rate linear network codes. We prove the existence of each type of variable-rate linear network codes which have the same local encoding kernel at every non-source node, and propose an efficient scheme to realize variable-rate linear network codes with a single fixed-rate strict linear network code session. Thus, every node in the network, including the source node, needs to store only one local encoding kernel to support a range of possible transmission rates of the source. Our constructed variable-rate linear network codes can also realize multi-rate transmission under each possible source rate, if combined with the special packetization strategy designed in this dissertation. Moreover, we propose the efficient construction scheme for variable-rate static linear network codes. If this scheme is applied, on matter what the source rate is and where link failures happen, the operation performed on each node in the network remains unchanged.At last, this dissertation investigates the application of linear network codes in two special kinds of heterogeneous networks:P2P streaming networks and wireless sensor networks. On one hand, we design the schemes to apply layered random linear network code and inter-layer hierarchical random linear network code in P2P streaming network to provide the partial decidability for low-bandwidth peers then guarantee the continuous decoding and smooth playback. On the other hand, we investigate the problem of lifetime maximization for wireless sensor networks with the assistance of network coding. We propose a new hypergraph model that accords with the broadcast nature of wireless sensor networks and a linear pricing model for the broadcast links. Simulations demonstrate that our energy measurement model is more precise than the point-to-point one. Moreover, network coding does have the effect of prolonging the network lifetime in our optimization problem.