BAGESS: A Software Module Based on a Genetic Algorithm to Sequentially Order Load-Balancing Evaluation Scenarios Over Smartphone-Based Clusters at the Edge

Abstract

Due to the increasing interest in employing smartphones as first-class citizens in high-performance Edge computing environments, the necessity of software to facilitate the evaluation of load-balancing strategies for smartphone-based clusters has emerged. Regarding this, to select the best strategy for a cluster with m smartphones, usually a number of g candidate strategies are evaluated based on a number of r scenarios that contain these smartphones, which differ in terms of the start battery levels required for these smartphones. Thus, each of the r scenarios must be prepared before evaluating each of the g strategies on each ri , so that the smartphones have the required start battery levels pre-configured for ri , which requires discharging or charging smartphones. This leads to a number of e = r*g scenario preparation events that must be sequentially developed, considering that the time required to develop each event depends on the previous event. Thus, the single-objective problem addressed here implies finding out the sequential order in which the events should be developed, so that the total time required to develop them is minimized. This problem is modeled as the ATSP (Asymmetric Traveling Salesman Problem), since defining the sequential order to develop the events is equivalent to defining the sequential order to visit the cities, and therefore, is an NP-Hard problem. Given the complexity of this problem, the novel software module BAGESS (Battery Aware Green Edge Scenario Sequencer) is proposed, which uses a genetic algorithm for defining the sequential order to develop the events. BAGESS’s performance outperforms those of the methods currently used for the problem, reaching significant savings regarding the time required to develop the events in the range [12, 85]%.