Supporting Mobile Cloud Computing in Smart Cities via Randomized Algorithms

Smart cities represent rich and dynamic environments in which a multitude of smart mobile devices (SMDs) interact among them by sharing data. SMDs require from fast access to online services, but they offer limited computing capabilities and battery lifetime. SMDs make frequent use of computation offloading, delegating computing-intensive tasks to the cloud instead of performing them locally. In such a large-scale and dynamic environment, there might be thousands of SMDs simultaneously executing processes and, therefore, competing for the allotment of remote resources. This arises the need for a smart allocation of these resources. Accordingly, this paper proposes a biased-randomized algorithm to support efficient and fast link selection. This algorithm is able to provide “real-time” near-optimal solutions that outperform solutions obtained through existing greedy heuristics. Furthermore, it overcomes the responsiveness limitations of exact optimization methods.