دانلود مقاله فرمول نویسی بهینه برای تخصیص منابع رادیویی
خلاصه
1. معرفی
2. بررسی ادبیات
3. تعریف مسئله
4. پیچیدگی مشکل
5. فرمولاسیون ILP
6. تجزیه و تحلیل آرامش LP
7. نتایج عددی
8. نتیجه گیری و کار آینده
بیانیه مشارکت نویسنده CRediT
قدردانی
در دسترس بودن داده ها
منابع
Abstract
1. Introduction
2. Literature review
3. Problem definition
4. Problem complexity
5. ILP formulations
6. Analysis of LP relaxations
7. Numerical results
8. Conclusions and future work
CRediT authorship contribution statement
Acknowledgments
Data availability
References
چکیده
ما یک مشکل تخصیص منابع رادیویی را در سیستم های ارتباطی سیار مطالعه می کنیم. به عنوان مشخصه بارز این مشکل، نرخ انتقال داده مشترک در تمام کانال های اختصاص داده شده به یک کاربر استفاده می شود. از آنجایی که کانال ها از نظر کیفیت متفاوت هستند، برای هر کاربر نرخ قابل دستیابی بر اساس کانال متفاوت است. بنابراین تخصیص کانال‌های بیشتر لزوماً نرخ کل را افزایش نمی‌دهد، زیرا نرخ مشترک محدود شده است که کمترین میزان پشتیبانی شده توسط کانال‌های اختصاص‌یافته باشد. تخصیص منابع رادیویی با توجه به محدودیت نرخ مشترک از اهمیت عملی برخوردار است، اگرچه توجه کمی به مدلسازی و حل مشکل شده است. ما یک دیدگاه بهینه سازی ریاضی با تمرکز بر مدل سازی داریم. ابتدا یک تحلیل پیچیدگی ارائه می کنیم. در مرحله بعد، چندین فرمول برنامه ریزی خطی عدد صحیح (ILP) برای مشکل، از جمله مدل های فشرده و غیر فشرده، مشتق شده اند. بخش عمده ای از تجزیه و تحلیل ما شامل یک مطالعه مقایسه ای دقیق از برنامه ریزی خطی (LP) آرامش آنها است، تا رابطه بین فرمول ها را از نظر مرزبندی نشان دهد. آزمایش‌های محاسباتی برای نشان دادن عملکرد عددی در حل مسئله به کمک LP ارائه شده‌اند. تجزیه و تحلیل نظری و نتایج عددی ما با هم در خدمت ایجاد زمینه ای برای مرحله بعدی توسعه روش های بهینه سازی مبتنی بر مدل و متناسب است....
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).
4G/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.