Methods For Efficient Network Coding In Wireless Networks

Due to the broadcast nature of wireless medium as well as the multi-hop network topologies, there are a lot of redundant packets in wireless networks, which affect the network performance directly. In recent years, it has been shown that network coding can be used to enhance the performance of wireless networks by exploiting the redundant packets. However, network coding incurs extra computational cost, and its performance gain is usually limited by the broadcast rate of wireless channels as well as the computational capabilities of wireless nodes, and also affected by the mobility of wireless nodes. Therefore, network coding schemes should be designed and applied to meet the requirements of these characteristics of wireless networks.In this dissertation, we conduct a comprehensive study on the methods of efficient network coding in wireless networks considering the applications of network coding in multi-channel scenarios and for reliable data transmission and broadcast in wireless mobile networks. The contributions of this dissertation are summarized as follows:(1) We investigate the network coding methods subject to the broadcast rate constraint in OFDMA relay networks. Considering the tradeoff between performance and overhead, we propose two approaches, global approach (GA) and local approach (LA) for the support of coding-aware scheduling decision making. For the coding-aware multi-channel scheduling problem, we show it is NP-hard under both the GA model and the LA model. For the GA model, we also show that it does not admit any polynomial time approximation scheme (PTAS), and then propose a heuristic algorithm with low time complexity, while for the LA model, we present a PTAS and also introduce a practical greedy algorithm with an approximation ratio of1/2. Simulation results show that both proposed practical algorithms can achieve significant throughput improvement over a state-of-the-art noncoding scheme.(2) We investigate the methods for chunked random linear network codes (chunked codes) with a constant computational complexity for reliable data transmission in wireless mobile networks. We first highlight the importance of precoding for chunked codes to achieve non-vanishing rates, and then present a tight analysis on the achievable rates of non-overlapped chunked codes with precoding. We further introduce the first class of overlapped chunked codes with non-trivial performance guarantee, called expander chunked codes, which use expander graphs to form overlapped chunks, and then characterize their achievable rates using a tree-based analysis as well as some expander arguments. Numerical results reveal that expander chunked codes perform near-optimally, and achieve significantly higher rates than non-overlapped chunked codes. Also, simulation results show that for a finite number of input packets expander chunked codes incur much lower transmission overhead to recover the whole input packets than all other state-of-the-art chunked codes.(3) We investigate the methods of data broadcast with network coding in wireless mobile networks by proposing a novel random linear network coding based broadcast protocol name R2. In this protocol, the message to be broadcast is divided into multiple mini-messages, while the mini-messages are transmitted in a fashion of random linear network coding. The use of random linear network coding makes nodes easier to accumulate useful information and thus mitigates the bottleneck for completing the broadcast process due to the very late reception of the message by one or more nodes. Meanwhile, R2employs random scheduling, that is, each network node uses the wireless channel randomly and independently, which on one hand exploits the broadcast nature of wireless medium and on the other hand combats the interference due to concurrent transmissions efficiently. Theoretical analyses show that R2performs optimally in terms of broadcast latency in order sense, no matter how fast nodes move around the network. In contrast, the pure random scheduling strategy is insufficient to achieve the order-optimality when nodes move very fast.