Hypergraph Modeling and Approximation Algorithms for the Minimum Length Link Scheduling in Multiuser MIMO Networks. (25th November 2013)

• Record Type: Journal Article
• Authors: Shen, Hu; Lv, Shaohe; Dong, Xuan; Deng, Junquan; Wang, Xiaodong; Zhou, Xingming
• Other Names: Liao Ching-Jong Academic Editor.
• Is Part Of: Journal of applied mathematics. Volume 2013(2013)
• Publication Date: 2013-11-25
• Subjects: Mathematics -- Periodicals; 519.05
• DOI: 10.1155/2013/982713
• Languages: English
• ISSNs: 1110-757X

Abstract

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.