Scheduling for network coded multicast: a distributed approach
We address the problem of maximizing the throughput for network coded multicast traffic in a wireless network in the bandwidth limited regime. For the joint scheduling and subgraph selection problem, we model valid network configurations as stable sets in an appropriately defined conflict graph. The...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2010
|
| Online Access: | http://hdl.handle.net/1721.1/59368 https://orcid.org/0000-0003-4059-407X |
| Summary: | We address the problem of maximizing the throughput for network coded multicast traffic in a wireless network in the bandwidth limited regime. For the joint scheduling and subgraph selection problem, we model valid network configurations as stable sets in an appropriately defined conflict graph. The problem formulation separates the combinatorial difficulty of scheduling from the arising optimization problem and facilitates the application of less complex scheduling policies. Lagrangian relaxation gives rise to two subproblems, a multiple shortest path, and a maximum weight stable set (MWSS) problem. For the latter we propose a greedy approach which can be computed in a distributed fashion, thus yielding a fully decentralized algorithm. Simulation results show that our technique is nearly optimal and outperforms heuristics such as orthogonal scheduling by a large margin. |
|---|