Date Added: Nov 2009
Optimal capacity analysis in multi-radio multichannel wireless networks by nature incurs the formulation of a mixed integer programming, which is NP-hard in general. The current state of the art mainly resorts to heuristic algorithms to obtain an approximate solution. In this paper, the authors propose a novel concept of Multi-Dimensional Conflict Graph (MDCG). Based on MDCG, the capacity optimization issue can be accurately modeled as a Linear Programming (LP) Multi-Commodity Flow (MCF) problem, augmented with Maximal Independent Set (MIS) constraints. The MDCG-based solution will provide not only the maximum throughput or utility, but also the optimal configurations on routing, channel assignment, and scheduling.