Hypergraph Modeling and Approximation Algorithms for the Minimum Length Link Scheduling in Multiuser MIMO Networks. (25th November 2013) - Shen, Hu; Lv, Shaohe; Dong, Xuan; Deng, Junquan; Wang, Xiaodong; Zhou, Xingming
Abstract : 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.