Throughput Optimization in Multi-hop Wireless Networks with Multi-packet Reception and Directional Antennas

Recent advances in the physical layer have enabled the simultaneous reception of multiple packets by a node in wireless net-works. We address the throughput optimization problem in wireless networks that support multi-packet reception (MPR) capability. The problem is modeled as a joint routing and scheduling problem, which is known to be NP-hard. 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 jEj+ 1 or fewer schedulable sets, where jEj is the number of links of the network. This result is in contrast with previous works that stated that a solution of the scheduling subproblem 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 approximation algorithm paradigms. We illustrate the use of the scheme to study the impact of design parameters on the performance of MPR-capable networks, including the number of transmit interfaces, the beamwidth and the receiver range of the antennas