Efficient Algorithms for Capacitated Cloudlet Placements

Zichuan Xu, Weifa Liang, Wenzheng Xu, Mike Jia, Song Guo

Research output: Journal article publicationJournal articleAcademic researchpeer-review

141 Citations (Scopus)

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.
Original languageEnglish
Article number7362036
Pages (from-to)2866-2880
Number of pages15
JournalIEEE Transactions on Parallel and Distributed Systems
Volume27
Issue number10
DOIs
Publication statusPublished - 1 Oct 2016
Externally publishedYes

Keywords

  • approximation algorithms
  • cloudlet access delay minimization
  • Cloudlet placement
  • mobile cloud computing
  • mobile user request assignment

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this