Cloudlet Placement and Minimum-Delay Routing in Cloudlet Computing

Mobile applications becomes increasingly computation intensive, while the computing capability of portable mobile devices is limited. Although cloud computing is emerging as a main ubiquitous platform to provide rich cloud resources for various mobile applications, the communication delay between mobile devices and remote clouds is difficult to control. A promising solution is to deploy clusters of computers near mobile users, called Cloudlets, so that mobile devices can offload their job requests to cloudlets with low latency. There has been a body of research in cloudlet computing, but little attention has been paid to cloudlet placement and routing of job requests. In this paper, we study how to place cloudlets to the wireless access points (APs), and how to route mobile job requests to minimize the communication latency. In order to cope with dynamic arrivals of mobile job requests, we first construct a number of snapshots among different time intervals based on the historical data. And then we derive an approximation algorithm for each snapshot to select some APs as candidate locations for the final locations of cloudlets. Finally we design an iterative algorithm to choose permanent locations to deploy cloudlets. Furthermore, based on the placement strategy, we propose an online job routing algorithm to dispatch mobile job requests to cloudlets such that the total communication delay is minimized. Simulation results demonstrate that our proposed algorithms performances well, and our online solution is comparable with state-of-the-art off-line solutions in the literature.