Abstract
The Mobile Edge Computing (MEC) paradigm brings computing and cache capacity resources in the proximity of users. It gives rise to a new ecosystem of services, such as video delivery and Augmented Reality (AR) ones, while reducing the latency that is experienced by users and lowering network service costs. The main challenges that MEC faces are related to the scarcity of resources at the network edge, the unpredictability of important system parameters, such as traffic, content and computation demand, and the ultra-low latency requirements that must be satisfied. In this thesis we deal with the challenges above, towards the optimization of two MEC goals: content delivery and real-time analytics at the edge of the network. We present resource allocation mechanisms and methods that automate the resource allocation, for fifth-generation (5G), Beyond-5G (B5G) and sixth-generation (6G) communication systems, accounting for edge resources such as caches, computational resources of mobile dev ...
The Mobile Edge Computing (MEC) paradigm brings computing and cache capacity resources in the proximity of users. It gives rise to a new ecosystem of services, such as video delivery and Augmented Reality (AR) ones, while reducing the latency that is experienced by users and lowering network service costs. The main challenges that MEC faces are related to the scarcity of resources at the network edge, the unpredictability of important system parameters, such as traffic, content and computation demand, and the ultra-low latency requirements that must be satisfied. In this thesis we deal with the challenges above, towards the optimization of two MEC goals: content delivery and real-time analytics at the edge of the network. We present resource allocation mechanisms and methods that automate the resource allocation, for fifth-generation (5G), Beyond-5G (B5G) and sixth-generation (6G) communication systems, accounting for edge resources such as caches, computational resources of mobile devices and edge servers, bandwidth and energy. We tackle both offline and Online Learning (OL) instances of optimization problems that span content recommendations and caching, user association and allocation of computing resources. We use a variety of mathematical tools to solve these problems, such as combinatorial optimization, convex optimization and Online Convex Optimization (OCO), a special case of OL. We analyse and we exploit the structural properties of the formulated optimization problems, either by designing algorithms ex novo, or by adapting existing techniques to our settings. We provide cost-efficient, fast and elegant solutions with provable performance guarantees, for a variety of important problems that arise within the MEC context. We start by studying the interplay of caching and Recommender Systems (RSs) mechanisms. Caching decisions typically seek to cache content that maximizes cache hit ratio. Recommendation systems, on the contrary, focus on individual users and recommend to them appealing content in order to elicit further content consumption. We explore how these, phenomenally conflicting, objectives can be jointly addressed. First, we formulate an optimization problem for the Joint Caching and Recommendation (JCR) decisions, aiming to maximize the cache hit ratio under minimal controllable distortion of the in- herent user content preferences by the issued recommendations. Then, we prove that the problem is NP-complete and that its objective function lacks those monotonicity and submodularity properties that would guarantee its approximability. Hence, we proceed to introduce a simple algorithm with polynomial time complexity, that essentially serves as a form of lightweight control over recommendations so that they are both appealing to end-users and friendly to network resources. We draw on both analysis and simula- tions with real and synthetic datasets to evaluate the performance of the algorithm. We point out its fundamental properties, provide analytical bounds for the achieved cache hit ratio, and study its sensitivity to its own as well as system-level parameters. We then enhance the problem setting above by considering user association control, i.e., each user may be associated to one out of a set of different BSs/caches, and direct content requests to that cache. We formulate the problem of Joint content Caching, design of Recommendations and user Association (JCRA), aiming at the maximization of the total cache hit ratio. We design an algorithm that extends our JCR algorithm. We perform a proof-of-concept validation that indicates that significant gains, both in terms of the achieved cache hit ratio, and in terms of the cache resources that are needed in order to obtain the same cache hit ratio in JCR and JCRA, can be obtained by controlling user association. We analyse the structural properties of special cases of the JCRA problem, we draw their connection with the Generalized Assignment Problem (GAP), and we expose the NP-completeness of the JCRA problem. Next, we study the problem of online learning optimal user association policies to Access Points (APs), in the presence of unknown and time-varying traffic demand. We aim at minimizing a broad family of α-fair cost functions that express various objectives in load assignment in the wireless downlink, such as total load or total delay minimization. Finding an optimal user association policy in dynamic environments is challenging, because traffic demand fluctuations over time are non-stationary and difficult to char- acterize statistically, which obstructs the computation of cost-efficient associations. As- suming arbitrary traffic patterns over time, we formulate the problem of online learning of optimal user association policies using the OCO framework. We introduce a periodic benchmark for OL problems that generalizes state-of-the-art benchmarks. We exploit inherent properties of the online user association problem and propose PerOnE, a simple online learning scheme that dynamically adapts the association policy to arbitrary traf- fic demand variations. We compare PerOnE against our periodic benchmark and prove that it enjoys the no-regret property, with additional sublinear dependence of the net- work size. To the best of our knowledge, this is the first work that introduces a periodic benchmark for OL problems, and a no-regret algorithm for the online user association problem. Our theoretical findings are validated through results on a real-trace dataset. Afterwards, we focus on edge computing systems, and we present a model that incorporates some aspects of AR, such as object recognition and classification through image or video processing. We study an offline instance of computation offloading to maximize the classification precision of the context of users of AR applications. We consider a scenario where context identification is performed through elicitation of user-generated information, such as images or small video files. It is the quantity of this information that ultimately determines the context classification precision, which we model as a Binomial random variable. We introduce the problem of maximizing a lower bound of the precision of context classification through prudent resource allocation, namely computation offloading. We consider bandwidth and computational capacity limita- tions at the wireless network edge, and the latency requirements of such systems. We discuss the structural properties of this combinatorial problem, which include the lack of monotonicity and convexity of the objective function. We design a fast algorithm for its solution, proving an approximation ratio for it. We then numerically evaluate our algorithm based on a setting that is derived from existing literature. We perform a sensitivity analysis over the systems’ parameters and observe that the tightness of the approximation ratio we proved for our algorithm is affected by the amount of available resources. However, in practice, our algorithm reaches 97-98% classification accuracy under very limited energy availability and delay tolerance, even when only 3% of the bandwidth resources are available. Finally, we study a multi-user MEC system with limited energy autonomy for the mobile devices and with limitations on the computing capability of both mobile devices and at an edge server where users can offload part of their computation load. We define a utility over “resource residuals”, that capture the difference between the assigned resources, and those needed, and we aim at the minimization of regret, i.e., of the difference between the utility obtained by the static offline benchmark that knows the system evolution in hindsight, and our online decision policy. We design OJOSO, an algorithm that jointly learns policies for offloading computations and scheduling them for execution at the shared MEC server. We prove that our algorithm is asymptotically optimal, i.e., it has no regret over the static benchmark, and that its performance is independent of the number of devices in the system. From our numerical evaluation we conclude that OJOSO adapts to unpredictable demand changes, it learns to identify resource-limited devices, and it learns to share the server’s resources. Overall, this Ph.D. thesis tackles a set of important optimization problems that arise in the context of edge computing and networking. We present novel problem formulations and algorithms that lead to solutions with provable performance guarantees, bringing the Mobile Edge Computing (MEC) paradigm a step closer to its practical realization.
show more
