Joint MAC Scheduling
and Network Coding: From Wired Networks to Realistic Wireless Networks
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.