Cross-Layer Link Scheduling for End-to-End Throughput Maximization in Wireless Ad Hoc Networks

In wireless ad hoc networks, PHY-layer interference is highly dependent on link scheduling schemes, and in turn heavily affects the performance of link scheduling. However, most existing link scheduling schemes ignore such relationship between the PHY and network layers, and hence fail to achieve the optimal end-to-end throughput due to large co-channel interference. This paper proposed a general framework for optimal TDMA (time division multiple access) link scheduling in multi-hop wireless ad hoc networks with general topology. In contrast to existing work, we maximizes the end-to-end throughput by taking into consideration the explicit relationship between the transmission rate of a link and its PHY-layer SINR (signal to interference and noise ratio). In particular, the authors formulate the scheduling problem into a LP (linear programming) problem based on the rate matrices with each entry being a function of SINR. With this formulation, the cross-layer link scheduling problem can be solved in polynomial time. To further reduce the computational complexity the authors proposed an algorithm to effectively reduce the size of the LP problem. Furthermore, to handle large-scale wireless networks, the authors present a decentralized scheduling algorithm that achieves a suboptimal TDMA scheduling solution with dramatically lower computational complexity comparing to the original LP formulation. Numerical results show that the proposed cross-layer link scheduling schemes outperform the existing schemes that assume a simplistic PHY-layer interference model by 59.45%.