From Least Interference-Cost Paths to Maximum Concurrent Multiflow in MC-MR Wireless Networks

Pengjun Wan
Illinois Institute of Technology
Wachman 1015D
Thursday, November 7, 2013 - 15:00
Maximum concurrent multiflow in multi-channel multi-radio (MC-MR) wireless networks has been well-studied in the literature. It is NP-hard but admits a polynomial-time approximation scheme (PTAS) when the number of channels is bounded by a constant. However, such PTAS is quite infeasible practically. Other than the PTAS, all other known approximation algorithms, in both SC-SR wireless networks and MC-MR wireless networks, resorted to solve some polynomial-sized linear program (LP) exactly. The scalability of their running time is fundamentally limited by the general-purposed LP solvers. This talk first introduces the concept of interference cost of a path and explore the relations between the least interference-cost paths and the maximum concurrent multiflow. Then a purely combinatorial approximation algorithm is presented which computes successively a sequence of least interference-cost paths as well as the flow amounts routed along them. Such algorithm is faster and simpler, and achieves nearly the same approximation bounds known in the literature.