Multi-dimensional Packing for Resource Allocation in 5G

Sammanfattning: The Fifth Generation (5G) of wireless communication system brings a series of new challenges in resource optimization. For example optimizing the number of bits and dedicated time used by each service would improve the quality of communications. Some of these challenges may be viewed as multidimensional resource allocation problems, which can be described as the assignment of available resources to various services over multiple dimensions. This problem has some similarities with already known NP-hard problems such as: multidimensional binpacking, multidimensional job scheduling, and multidimensional knapsack. In this thesis we study a special case of this resource allocation problem: finding the optimal assignment of resources (multidimensional blocks of bits) to services (a time-frequency pair), initially aiming to maximize the number of satisfied services and, only afterwards, minimize the resources' consumption. There is no known algorithm that guarantees the global optimum in any of the two problems, that scales linearly in all dimensions (time, frequency, and bits) and minimizes the consumption of the resources. The problem got split into the two goals previously described, and the first one was prioritized over the second one. We prove the existence of a Polynomial Randomized Approximation Scheme (PRAS) for the resource allocation problem. Furthermore we have designed and implemented several heuristics in order to achieve the two goals through broadword programming and succinct data structures: extended First-Fit (FF), Swap-Fit (SF), Merge-Fit (MF) and Swap-Merge-Fit (SMF) for the first goal, and Approximated-Integer-Allocation (AIA) for the second one. In conclusion SF turned out to be the best heuristic in order to achieve the maximization of satisfied services, while AIA had proven good results regarding the minimization of resources.