Capacity analysis of multi-radio multi-channel (MR-MC) wireless network

The multi-radio multi-channel (MR-MC) networking provides a generic computing platform for a wide range of next-generation wireless networks, e.g., wireless mesh networks based on the IEEE 802.16, 4G cellular networks based on the long term evolution (LTE), and cognitive radio networks based on the dynamic spectrum sharing. However, the capacity of the MR-MC networking is not well studied due to the lack of effective tool addressing the complex interactions of the channel assignment and radio interface allocation problem. Moreover, how to efficiently utilize multiple interfaces and channels is unexplored. Generally, we have the four main contributions in this work. 1) an efficient methodology is proposed to compute the optimal capacity of MR-MC network and the concept of critical set is revealed. 2) two sufficient conditions are developed for the flow assignment, which can be constructed and verified in distributed manner. Both conditions achieve a provable portion of the optimal capacity region. 3) a novel framework and efficient algorithms are developed for the dynamic network control in the MR-MC network. 4) a new routing metric is proposed to consider both delay and interference for path selection, and a routing protocol is designed correspondingly.;Specifically, we originally construct a new multi-dimensional conflict graph (MDCG) to describe all the interference relationship in the MR-MC network. Based on MDCG, we formulate a multi-commodity flow (MCF) problem augmented with maximal independent set (MIS) constraint to compute the optimal capacity, so that the optimal capacity planning in MR-MC networks can be transformed from integer programming regime to linear programming regime. We further provide the new concept of critical MIS set, and estimate the upper bound of the size of critical MIS set. Moreover, we develop the sufficient conditions for the flow rate assignment, which achieve a provable portion of the optimal capacity region, termed as efficiency ratio. These sufficient constraints could be constructed and verified in the distributed and localized manner. We develop new method to compute the efficiency ratio for each sufficient condition by exploring the disruptively different geometric property of MR-MC networks compared with single radio single channel network. Then we develop a new framework to systematically study the resource allocation problem considering the dynamic network control in the MRMC network. The framework not only facilitates the formulation of throughput-optimal scheduling for the MR-MC network, but also allows us optimally solving the joint resource allocation problem. At last, a new routing metric is proposed to consider not only the transmission delay also queuing delay. In addition, in the MR-MC context, the inter-flow interference and intra-flow interference are taken into account. An AODV-based routing protocol is designed to implement the new metric.