Fast algorithms for capacitated cloudlet placements

Mobile cloud computing addresses resource scarcity problem of mobile devices by offloading computation data from mobile devices into the cloud. However, remote server may be far from mobile users. Cloudlet could be used to deal with the long access delay problem. In the large-scale Wireless Metropolitan Area Network (WMAN) consisting of many wireless Access Points (APs), choosing the appropriate position of cloudlet is very important to reducing access delay. Recently, a heuristic algorithm has been proposed. However, it has so many repeated sorting process of APs that the algorithm efficiency is poor. In this paper, we propose a New Heuristic Algorithm (NHA) and a Particle Swarm Optimization (PSO) algorithm for the delaying problem. We evaluate the performance of the proposed algorithms through extensive simulations. Simulation results demonstrate NHA is more efficient then existing algorithm. For the PSO algorithm, in the case of parallelized execution, it is more efficient than the new heuristic algorithm within a bounded delay.

I. Introduction

With the tremendous growing of mobile devices, mobile data traffic is becoming more and more heavy. However, the running resources on mobile devices such as battery, computing capability, network bandwidth and storage are always limited due to their portable sizes [1]. There is gap between demands of resources by complex mobile applications and the limited capacity on mobile devices. A powerful approach to improve the performance of mobile applications is enabling mobile devices to offload some of their tasks to remote resource-rich clouds [2], [3]. However, in traditional architecture of mobile cloud computing for the complex network of WAN, the cloud is usually remotely located and far away from its users, mobile applications may suffer from high end-to-end latency [4]. Moreover, transferring data to the remote cloud is always costly for the network delay incurred. Finally, for the latency-sensitive mobile applications such as augmented reality, speech recognition, navigation, language translation, a crisp response time is critical to their users [5]. To meet the latency challenge, Satyanarayananet al. [4] propose a new element that extends the mobile device-cloud architecture, called cloudlet. Cloudlet is a trusted, resource rich device or server that is well-connected to the Internet and available for use by nearby mobile devices [6]. Cloudlets are self-managing so they have fewer requirements other than power and Internet connectivity. They can be viewed as datacenters in a box deployed in existing networks. For mobile device, logical proximity to the cloudlet is very important to reduce the end-to-end latency. So the best location for the cloudlet is one hop away from the mobile device. For example, the cloudlet can be deployed in a cellular base station or a Wi-Fi Access Point(AP) [1].