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

Abstract—Maximum multiflow and maximum concurrent mul-tiflow in multi-channel multi-radio (MC-MR) wireless networks have been well-studied in the literature. They are NP-hard even in single-channel single-radio (SC-SR) wireless networks when all nodes have uniform (and fixed) interference radii and the positions of all nodes are available. While they admit a polynomial-time approximation scheme (PTAS) when the number of channels is bounded by a constant, 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 a polynomial-sized linear program (LP) exactly. The scalability of their running time is fundamentally limited by the general-purposed LP solvers. In this paper, we first introduce the concept of interference costs and prices of a path and explore their relations with the maximum (concurrent) multiflow. Then we develop purely combinatorial approximation algorithms which compute a sequence of least interference-cost routing paths along which the flows are routed. These algorithms are faster and simpler, and achieve nearly the same approximation bounds known in the literature. I