A Multi Objective Discrete Particle Swarm Optimization Algorithm for Mobile Offloading

Abstract

Die steigenden Anforderungen von mobilen Applikationen in Bezug auf Rechenleistung sowie die hohen Erwartungshaltungen der Nutzer an Energieeffizienz erfordern innovative Strategien wie Mobile Edge Cloud Offloading (MECO). Diese Arbeit stellt einen Multi-Objective Discrete Particle Swarm Optimization (MDPSO)-Algorithmus vor, welcher für die Optimierung von möglichen Deployments in MECO-Umgebungen entwickelt wurde. Ziel des Algorithmus ist die Berechnung von effizienten und ausgeglichenen Offloading-Strategien der einzelnen Applikationsaufgaben auf die gegebenen Rechenknoten, mit Berücksichtigung der in Konflikt stehenden Optimierungsziele von Applikationslaufzeit, Batterielaufzeit und Nutzerkosten. Der MDPSO-Algorithmus erweitert klassische Particle-Swarm-Optimization-Ansätze (PSO) mit dem diskreten Aufgaben-Mapping der MECO-Deployments. Dazu wurden ein Mechanismus zur Darstellung und Geschwindigkeitsberechnung der Partikel, eine Archivierungsstrategie für die besten Lösungen sowie eine Auswahlregel dieser globalen Optima mit Bezug auf die Optimierungsziele integriert. Zur Validierung des Algorithmus wurde ein Edge-Simulation-Framework verwendet, mit dem realistische MECO-Szenarien, bestehend aus verschiedenen Infrastrukturkonstellationen sowie typischen mobilen Applikationen, dargestellt als gerichtete azyklische Graphen (DAGs), modelliert wurden. Der verwendete Algorithmus wurde anhand standardisierter Qualitätsindikatoren wie Hypervolume und Generational Distance evaluiert und mit den etablierten Multi-Objective-Optimization-Algorithmen (MOO) NSGA-II, NSGA-III, MOCell und SPEA2 verglichen. Die Ergebnisse zeigen, dass der MDPSO-Algorithmus besonders in MECO-Szenarien mit mittlerer bis hoher Komplexität durch eine hohe Konvergenz und Diversität der Lösungen überzeugt. Gleichzeitig wurde das Potenzial zur Verbesserung der Rechenleistung und Effizienz im Vergleich zu bestehenden Algorithmen bei weniger komplexen Szenarien identifiziert.

The increasing computational demands of modern mobile applications, along with user expectations for energy efficiency and low latency, require advanced strategies, like mobile edge cloud offloading (MECO). This thesis proposes a Multi-Objective Discrete Particle Swarm Optimization (MDPSO) algorithm designed to optimize the deployment of computational tasks in MECO environments. By addressing the conflicting objectives of application runtime, battery life and user costs, the proposed algorithm aims to deliver efficient and balanced task offloading strategies. The MDPSO algorithm is designed to combine traditional particle swarm optimization (PSO) techniques with discrete task mapping by incorporating a particle encoding mechanism for the MECO deployment problem, a leader archive strategy as well as an objective-based global best selection rule. To validate the applied algorithm, an edge simulation framework was used to model the edge and cloud computing environments of real-world MECO scenarios with directed acyclic graphs (DAGs) to represent mobile applications. The proposed algorithm is evaluated and compared against state-of-the-art multi-objective optimization algorithms such as NSGA-II, NSGA-III, MOCell and SPEA2, by using standardized performance metrics like hypervolume and generational distance. The results demonstrate the MDPSO's ability to find well-distributed Pareto-optimal solutions. In medium- to high-complexity MECO scenarios, the proposed MDPSO outperforms the reference algorithms in terms of convergence and diversity. However, it also shows possible improvements in computational efficiency and performance in simpler problem instances compared with established algorithms.