On Link Scheduling Under Blockage and Interference in 60-GHz Ad Hoc Networks

In this paper, we tackle the problem of minimum time length link scheduling in 60-GHz ad hoc wireless networks using directional antennas with directional beamforming, under both traffic demand and signal to interference and noise ratio constraints. Both single-hop and multi-hop cases are considered. For the single-hop scenario, a binary integer programming problem is formulated by incorporating a general interference model for directional transmissions and a Markov chain-based blockage model. Two effective solution algorithms are proposed, including a greedy algorithm that maximizes the instant throughput for each time slot, and a column generation-based algorithm that iteratively improves the current link schedule. For the multi-hop scenario, we develop a more complicated problem formulation incorporating both route selection and flow conservation constraints. We also develop an effective algorithm to solve the multi-hop problem. The performance of the proposed algorithms is validated with simulations.