Local sufficient rate constraints for guaranteed capacity region in multi-radio multi-channel wireless networks

It is very challenging to compute the capacity region of a multi-radio multi-channel (MR-MC) network, which involves complex resource contention including the co-channel interferences and radio interface contentions. In this paper, we study the local sufficient rate constraints that can be constructed at each network node in a distributed manner to ensure a feasible flow allocation for the MR-MC network. The analysis of capacity region with the rate constraints is facilitated by our tool of multi-dimensional conflict graph (MDCG) [12], which systematically describes all kinds of conflict relationships in an MR-MC network. Specially, we establish two types of local sufficient constraints, the neighborhood constraint and the sufficient clique constraint, respectively; and both types can ensure a constant portion of the optimal capacity region, termed as capacity efficiency ratio. The capacity efficiency ratios associated with the neighborhood constraint and the sufficient clique constraint are related to the analysis of the interference degree and the imperfection ratio of an MDCG, respectively. A specific challenge is that methodology computing the interference degree and the imperfection ratio of single-radio single-channel (SR-SC) networks could not be directly extended to the MR-MC context, because MR-MC network has disruptively different geometric properties compared to the SR-SC network: In an MR-MC network, the geometric closeness does not necessarily imply interference due to possible parallel transmissions over different radios and channels. The fundamental contributions of this paper are the theoretical studies of the interference degree and the imperfection ratio of an MDCG, revealing how such graphical characteristics are related to those in the SR-SC context under the impact of the MR-MC geometric property. We also present extensive numerical results to demonstrate the effectiveness of the proposed local sufficient constraints in ensuring a larger capacity region compared to the well-known results in [1].