Paper Info
Title
Application of Graph Theory to the Multicell Beam Scheduling Problem
Abstract
This paper applies combinatorial optimization techniques to improve the downlink transmission to multiple users in a network with N cells, where intercell interference is a performance-limiting factor. A fair distribution of the signal-to-interference-plus-noise ratio (SINR) is desirable. A well-known technique to get a fair (balanced) SINR is max-min unicast beamforming (MBF). However, in a multicell network, there are conditions where MBF can result in a low balanced SINR. This happens if, e.g., two users are geographically close together and served by two base stations (BSs) from, e.g., two different interfering sectors. Then, the mutual interference among the two links will be large, and the balanced SINR among all jointly optimized links decreases. Therefore, the users must be scheduled such that these situations are avoided. In this paper, smart selection of active beams to avoid intercell interference is called beam scheduling and leads to a combinatorial optimization problem. This paper proposes a graph-theory-based problem that is closely related to the beam scheduling problem. The proposed algorithms maximize the sum rate or the minimum SINR among all users and slots. For the two-cell case, an optimal algorithm exists. In the N > 2-cell case, the beam scheduling problem is proven to be NP-hard. Based on the close relation between the beam scheduling problem and the multidimensional assignment problem (MAP), this paper presents suboptimal algorithms for N > 2 to maximize either the sum rate or the minimum SINR among all users and slots. The performance gain in terms of the mean sum rate or the minimum SINR is significant compared with random scheduling.
Year
DOI
Venue
2013
10.1109/TVT.2013.2242912
Vehicular Technology, IEEE Transactions
Keywords
Field
DocType
array signal processing,cellular radio,computational complexity,graph theory,optimisation,radiofrequency interference,MAP,MBF,NP-hard problem,SINR,combinatorial optimization techniques,downlink transmission improvement,graph theory,intercell interference,maxmin unicast beamforming,multicell beam scheduling problem,multicell network,multidimensional assignment problem,mutual interference,performance-limiting factor,signal-to-interference-plus-noise ratio,Assignment problem,beam scheduling,beamforming,bottleneck assignment problem
Beamforming,Mathematical optimization,Job shop scheduling,Fair-share scheduling,Scheduling (computing),Computer science,Combinatorial optimization,Electronic engineering,Assignment problem,Interference (wave propagation),Unicast
Journal
Volume
Issue
ISSN
62
4
0018-9545
Citations 
PageRank 
References 
2
0.39
12
Authors
3
Name
Order
Citations
PageRank
Guido Dartmann120.39
Xitao Gong210811.91
Gerd Ascheid31205144.76