Hypergraph Modeling and Approximation Algorithms for the Minimum Length Link Scheduling in Multiuser MIMO Networks

[摘要] This paper investigates the problem of the minimum length link scheduling (MLLS) in multiuser MIMO (MU-MIMO) networks. Generally, in the networks with MU-MIMO capability, the number of concurrent transmissions can be as large as that of antenna elements at the receiver. As a result, link interference is no longer binary but demonstrates a strong correlation among multiple links, which cannot be captured by the conventional conflict graph interference model. Hence, we propose a novel hypergraph interference model, which can accurately and efficiently characterize the relationship of multiple interferences induced by concurrent transmissions, and provide a tractable formalization of the minimum length link scheduling in MU-MIMO networks (MU-MIMO MLLS). Afterwards, we prove that the MU-MIMO MLLS problem is NP-hard and introduce two approximation algorithms to find the near-optimal feasible schedule. Finally, extensive simulation experiments are presented.

[学科分类] 应用数学