Joint MAC Scheduling and Network Coding: From Wired Networks to Realistic Wireless Networks

Carleton University, Ontario, Canada. September 2012.

In this work, we explore different aspects and steps of building a joint network coding and scheduling solution for wireless multihop networks. Network coding allows transmission networks to combine data at intermediate network nodes. In contrast to routing, where nodes only relay and replicate data in network nodes, network coding provides an opportunity to improve a performance measure of interest like the throughput or the transmission energy.

 

The focus of this work is on formulating a joint linear optimization problem for wireless networks. The optimization problem is formulated on a wired graph that represents the wireless graph, allowing us to apply known code-design techniques for wired networks. We also study network codes design methods for the equivalent wired graph which satisfy two constraints: wireless broadcast links have to transmit the same (coded) information, and the transfer of codes from the wired back to the wireless domain has to correctly deal with scheduling sets with unequal timeshares. Furthermore, we compare the performance and run-time complexities of the two most well-known interference models in wireless networks, physical model and protocol model, for scheduling transmissions. The performance of the protocol model is very close to that of the physical model in throughput maximization problems, while its run-time complexity is significantly lower. Therefore, the protocol model can be used in those problems without loss of the performance. In minimum energy problems however, the run-time complexities of the two models are not very different and the performance of the protocol model is worse than that of the physical model. Therefore, using the physical model is a better choice when studying the minimum energy problem. Finally, we propose a new scheduling heuristic that outperforms the existing heuristics for networks with central schedulers. Our new scheduling method, capacity-bundling scheduling, builds scheduling sets based on their link capacities, which results in improved throughput in throughput maximization problems and energy savings in energy minimization problems. Our results show that this improvement is up to about 80% for the throughput, and about 55% for the energy consumption in the scenarios simulated in this work.