Scheduling for Network-Coded Multicast
The authors consider multicasting using random linear network coding over a multi-hop wireless network in the bandwidth limited regime. They address the associated medium access problem and propose a scheduling technique that activates hyper-arcs rather than links, as in classical scheduling approaches. They encapsulate the constraints on valid network configurations in a conflict graph model and formulate a joint optimization problem taking into account both the network coding subgraph and the schedule. Next, using Lagrangian relaxation, they decompose the overall problem into two sub-problems, a multiple-shortest-paths problem and a Maximum Weighted Stable Set (MWSS) problem.