Abstract

We study a radio resource allocation problem in mobile communication systems. As the distinct characteristic of this problem, a common data transmission rate is used on all channels allocated to a user. Because the channels differ in their quality, for each user the achievable rate varies by channel. Thus allocating more channels does not necessarily increase the total rate, as the common rate is constrained to be the lowest one supported by the allocated channels. Radio resource allocation subject to the common-rate constraint is of practical relevance, though little attention has been paid to modeling and solving the problem. We take a mathematical optimization perspective with focus on modeling. We first provide a complexity analysis. Next, several integer linear programming (ILP) formulations for the problem, including compact as well as non-compact models, are derived. The bulk of our analysis consists in a rigorous comparative study of their linear programming (LP) relaxations, to reveal the relationship between the formulations in terms of bounding. Computational experiments are presented to illustrate the numerical performance in bounding and LP-assisted problem solving. Our theoretical analysis and numerical results together serve the aim of setting a ground for the next step of developing model-based and tailored optimization methods.

Introduction

Mobile communication systems have been evolving rapidly in the past decades. From an optimization standpoint, a key research topic for mobile networks is radio resource management for utilizing the radio resource efficiently, particularly because the amount of data traffic is constantly growing in the current 4th generation (4G) systems, and the trend will remain or even accelerate in the 5th generation (5G) networks. Along with this growth, 5G networks target a plethora of new services (e.g., vehicular communications), making resource management more challenging than before, as pointed out in Calabrese et al. (2018).

۴G/5G networks deploy orthogonal frequency division multiple access (OFDMA). In essence, data transmission takes place in two dimensions, namely time and frequency that are divided into time slots and channels, respectively.1 Resource management for channel allocation in a time slot, as well as that across multiple time slots, is commonly called scheduling. In any time slot, a user may be scheduled to receive transmission from its base station (BS) on multiple channels, and a channel may be scheduled for at most one user of this BS. The latter is what the term “orthogonal” refers to in OFDMA. Among the BSs, the channels are reused, i.e., there is generally no dedicated (sub)set of channels for a BS. As a result, a channel is exposed to interference, if the channel is also scheduled in some nearby BSs in the same time slot. Note that even if interference is not present, the channels are still frequency-selective (Tse and Viswanath, 2005), meaning that they vary in quality and hence the achievable data rate from a user’s perspective.

Conclusions and future work

We have studied mathematical modeling of a resource optimization problem with common-rate channel allocation in mobile communication systems. We have demonstrated that the problem admits an array of integer programming formulations. The study shows that modeling does matter, analytically as well as numerically, in terms of performance in bounding and LP-based problem solving. Moreover, there is a clear correlation between the accuracy of LP and the quality of integer solution derived thereby.

As we have observed, straightforward schemes of constructing integer solutions are not practical in solution time, whereas for our resource allocation problem, the ultimate target is real-time optimization. To approach this goal with model-based optimization, we make several observations. First, to deliver a solution rapidly, the amount of computation has to be very small, and thus the LP relaxation may have to be solved approximately, followed by some primal heuristic (both admitting massive parallel computation). Second, non-compact models are also of interest, as restricting the number of columns or rows leads to approximation of the problem (and the LP relaxation). Finally, with presence of rate lower bound, obtaining solution feasibility is of clear significance, and one may need to trade solution quality against feasibility. Developing and implementing algorithmic notions along these lines form interesting topics for forthcoming research.