Paper Info
Title
Efficient Algorithms for Capacitated Cloudlet Placements.
Abstract
Mobile cloud computing is emerging as a main ubiquitous computing platform to provide rich cloud resources for various applications of mobile devices. Although most existing studies in mobile cloud computing focus on energy savings of mobile devices by offloading computing-intensive jobs from mobile devices to remote clouds, the access delays between mobile users and remote clouds usually are long and sometimes unbearable. Cloudlet as a new technology is capable to bridge this gap, and can enhance the performance of mobile devices significantly while meeting the crisp response time requirements of mobile users. In this paper, we study the cloudlet placement problem in a large-scale Wireless Metropolitan Area Network (WMAN) consisting of many wireless Access Points (APs). We first formulate the problem as a novel capacitated cloudlet placement problem that places $K$ cloudlets to some strategic locations in the WMAN with the objective to minimize the average access delay between mobile users and the cloudlets serving the users. We then propose an exact solution to the problem by formulating it as an Integer Linear Programming (ILP). Due to the poor scalability of the ILP, we instead propose an efficient heuristic for the problem. For a special case of the problem where all cloudlets have identical computing capacities, we devise novel approximation algorithms with guaranteed approximation ratios. We also devise an online algorithm for dynamically allocating user requests to different cloudlets, if the $K$ cloudlets have already been placed. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrate that the proposed algorithms are promising and scalable.
Year
DOI
Venue
2016
10.1109/TPDS.2015.2510638
IEEE Trans. Parallel Distrib. Syst.
Keywords
Field
DocType
Cloud computing,Mobile communication,Delays,Approximation algorithms,Mobile handsets,Approximation methods,Heuristic algorithms
Mobile computing,Cloudlet,Computer science,Computer network,Real-time computing,Ubiquitous computing,Distributed computing,Mobile cloud computing,Approximation algorithm,Algorithm,Mobile device,Mobile telephony,Cloud computing
Journal
Volume
Issue
ISSN
27
10
1045-9219
Citations 
PageRank 
References 
52
1.75
24
Authors
5
Name
Order
Citations
PageRank
Zichuan Xu136827.39
Weifa Liang21676134.75
Wenzheng Xu331521.18
Mike Jia42019.78
Song Guo53431278.71