Optimal link scheduling in millimeter wave multi-hop networks with space division multiple access

In this paper, we introduce a model for Multiple-Input Multiple-Output (MIMO) Space Division Multiple Access (SDMA) into the analysis of a multi-hop millimeter wave network under the classic Network Utility Maximization (NUM) framework with Maximum Back Pressure scheduling (MBP). We show that the proof of convergence of MBP remains valid when we allow the scheduler to select multiple links to the same receiver in the same frame. Conventional MBP with a single link per receiver is traditionally implemented using the Maximum Weighted Matching (MWM) algorithm over the network graph. Under our modification, the problem becomes a Maximum Weighted Partition of the graph. Message Passing (MP) algorithms are efficient and have been successfully applied to graph partitioning problems in the past, so we use one to approximate the optimal MBP scheduling. Through simulation over a randomized mmWave picocell, we compare the MWM reference without SDMA, the efficient MP approximation, and the exact optimal MBP scheduler with SDMA (obtained by brute force). Simulations show that by leveraging SDMA in multi-hop mmWave network scheduling, a 50% capacity increase is obtained on average.