Maximizing Throughput in Wireless Multi-Access Channel Networks

Recent advances in the physical layer have enabled the simultaneous reception of multiple packets by a node in wireless networks. In this paper, we present a generalized model for the throughput optimization problem in multi-hop wireless networks that support multi-packet reception (MPR) capability. The model incorporates the multi-access channel, which accurately accounts for the achievable capacity of links used by simultaneous packet transmissions. The problem is modeled as a joint routing and scheduling problem. The scheduling subproblem deals with finding the optimal schedulable sets, which are defined as subsets of links that can be scheduled or activated simultaneously. We demonstrate that any solution of the scheduling subproblem can be built with |E| + 1 or fewer schedulable sets, where |E| is the number of links of the network. This result contrasts with a conjecture that states that a solution of the scheduling subproblem, in general, is composed of an exponential number of schedulable sets. Due to the hardness of the problem, we propose a polynomial time scheme based on a combination of linear programming and greedy paradigms. The scheme guarantees the operation of links at maximum aggregate capacity, where the sum of the capacity of the links is maximized and the multi-access channel is fully exploited.