ONLINE RESOURCE RESERVATION FORMOBILE EDGE COMPUTING SERVICES

Abstract

Over the last decade, the world has witnessed the rapid penetration and proliferation of the Internet of Things (IoT). With the rise of smart IoT applications, the edge of the computer network is envisioned to be the data processor, which refers to as mobile edge computing (MEC). Instead of processing tasks locally, the IoT applications offload computational intensive tasks to the MEC server for processing. As a large portion of smart IoT applications are event-triggered, MEC users have very limited information about future tasks, which includes the communication as well as computing resource usage and the arrival time of the task. Therefore, the MEC resource needs to be purchased or reserved in an online manner. As MEC market reaches maturity, MEC brokers will emerge to help reduce the cost of individual users by aggregating users’ task demand to improve resource utilization. In this thesis, we investigate the online MEC resource reservation problem for both individual users and brokers. Similar to the cloud computing and wireless communication market, MEC users and brokers can purchase both communication and computing resources by PAYG or plans. Besides data and computing plans for each type of resource, we also consider combo plans specifically designed for MEC services covering both resources. Compared with PAYG, plans have a high upfront fee but can cover the corresponding resource usage for a period of time. As such, how to choose between PAYG and plans and when to purchase the resource determine the cost of users and brokers. To the best of our knowledge, we are the first to consider online resource reservation problem for MEC users and brokers. To solve the resource reservation problem, we first formulate offline cost minimization problems for both individual users and brokers, which are NP-Complete. Then we formulate online cost minimization problems and convert them to competitive ratio minimization problems. We propose deterministic online resource reservation algorithms for individual users and brokers to solve these problems. By conducting competitive analysis, we derive the competitive ratio of the deterministic online re-source reservation algorithms for individual users and prove it to be the minimum among all deterministic online resource reservation algorithms for individual users. We also derive the competitive ratio of the deterministic online resource reservation algorithm for brokers, and prove it to be the minimum among all deterministic online resource reservation algorithms for brokers. Besides deterministic algorithms, we derive randomized online resource reservation algorithms for individual users and brokers, which are probability distribution of deterministic algorithms. By conducting competitive analysis, we derive the competitive ratio of the randomized online resource reservation algorithm for individual users and prove it to be the minimum among all randomized online resource reservation algorithms for individual users. We also derive the competitive ratio of the randomized online resource reservation algorithm for brokers, and prove it to be the minimum among all randomized online resource reservation algorithms for brokers. In the trace-driven simulations, our proposed deterministic online resource reservation algorithms for individual users and brokers outperforms all benchmark schemes including prediction based methods in terms of cost minimization and resource utilization. Although our proposed randomized online resource reservation algorithms for users and brokers have better competitive ratios (worst case guarantee) than deterministic online resource reservation algorithms, their performances are worse than the deterministic online resource reservation algorithms. Furthermore, we verify that MEC brokers can reduce costs of individual users through demand aggregation. Our proposed algorithms can be used for new MEC users and brokers with little knowledge on future resource usage or users and brokers with highly fluctuating demands.