Optimization-Based Design of Wireless Link Scheduling With Physical Interference Model

We address the link-scheduling problem in wireless multihop networks under the realistic physical interference model. Different from most works, which adopt the protocol interference model that treats the pairwise interference, we use the physical interference model to reflect the aggregated signal-to-interference-plus-noise ratio (SINR), which is a more accurate abstraction of the real scenarios. We first propose a centralized scheduling method based on the integer linear programming (ILP) and get an approximate solution by relaxing it to linear programming (LP). The probability bound of getting the guaranteed approximate factor is given, which is distinguished from other LP-based algorithms. Then, for the cases where the required global information is hard to get, a distributed scheduling algorithm is proposed. We simplify the formulation of the scheduling problem in the distributed scenarios and calculate the optimal solution as the transmission probability. This method can be implemented on each node through the Jacobi algorithm, only relying on local channel information. Simulation results show that it converges fast to the optimal solution and provides good throughput performance comparable with the centralized algorithm.