Research On Opportunistic Network Coding In Wireless Networks

Wireless network coding is an important part of the network coding technology,and the localized opportunistic network coding is one of the most simple and practicalbranches of the wireless network coding. To address the basic problem of the through-put performance of the wireless opportunistic network coding, this thesis focuses on thethroughput performance optimization, and systematically conducts theory and applica-tion research from the following three levels: theory framework, scheduling algorithmand system improvement. The main research contents and contributions of this thesis areas follows:Firstly, by studying the classical problem of maximum multi-commodity flow, wepropose a theory framework for computing the maximum throughput of any given multi-ple unicast flows supported by a multihop wireless network with any given opportunisticnetwork coding setting. In this framework, we show that determining the capacity regionof a multihop wireless network with opportunistic network coding is an NP-hard prob-lem, and thus develop a greedy heuristic algorithm to determine a capacity subregion.We also show that finding an optimal schedule in a multihop wireless network with op-portunistic network coding is NP-hard, and thus develop a polynomial algorithm to findan approximate schedule with constant approximation bound. A numerical analysis ispresented to demonstrate the efciencies of the algorithms based on the framework.Secondly, we focus on the network coding schedule under the real physical inter-ference model, and develop a scheduling algorithm with constant approximation bound.Since that it is the first time to investigate the network coding schedule under the physi-cal interference model, we define several scheduling optimization problems for diferentwireless network coding scenarios. The MIMS problem, as one of these scheduling opti-mization problems, applies to the opportunistic network coding scenario. We then devel-op a polynomial algorithm with constant approximation bound for the MIMS problem.This thesis initially explores the research field of network coding schedule under the realphysical interference model, providing a reference for subsequent research.Finally, we investigate the problem of decoding bufer in opportunistic network cod-ing systems, and introduce a mechanism for decoding bufer management. In a practicalopportunistic network coding system, limited decoding bufer may result in the loss of coding opportunities, as well as the reduction of the throughput gain brought by net-work coding. Based on the flow characteristics of those decoding packets, we introducea mechanism called decoding bufer management (DBM) in practical opportunistic net-work coding systems, which consisting of the decoding bufer filtering function and thepacket information distributing function. The simulation results show that, DBM cangreatly improve the utilization level of decoding bufer while reducing the bandwidthoverhead, and provide more coding opportunities than the traditional COPE method whendecoding bufer is limited.