[Back]

D. Scheffknecht:
"A Game Theoretic Approach for Computational Offloading in Fog Computing";
Supervisor: S. Schulte; Institute of Information Systems Engineering, Distributed Systems Group, 2021; final examination: 2022-01-11.

With the ongoing digitalization and the rise of Internet of Things technologies, new requirements for distributed network technologies arise. Currently, most IoT architectures use cloud servers to process sensor data collected at the network edge. This might lead to high latency, because a lot of time is spent on transmitting data between sensors and cloud servers. Fog Computing (FC) can be used to overcome this issue. In FC, devices between the cloud and the network edge are used to perform latency-critical tasks (e.g., for self-driving vehicles or monitoring systems). Such FC systems require strategies to distribute the computing tasks over the nodes in the network. This distribution should optimize the whole system's Quality of Service. This is often done by solving an optimization problem centrally, which requires full knowledge about the FC system state and additionally is computationally complex. To enable the scalability of FC systems, distributed solutions for this problem are needed. The goal of this thesis is to design and implement an FC system prototype that uses a game theoretic approach to handle the allocation of computational resources. Game theoretic models are used to model competing parties where each player determines its strategy individually. So, if we formulate the resource allocation problem as a game, the players´ offloading strategies can be calculated in a distributed fashion. If a Nash Equilibrium is reached in the game, the FC systems´ performance should be near an global optimum.The evaluation discusses how the game theoretic approach performs compared to a first-fit heuristic. We also analyze how joining and leaving sensors affect the game playing during runtime. The results show that equilibria are reached efficiently if the number of sensors stays constant. The baseline is outperformed, if we compare the overall task round-trip times in the FC system. Additionally, we show that in simulations with dynamic sensors the game still converges to an equilibrium and only few strategy changes are needed once the game reaches a nearly stable state.

Mit der fortlaufenden Digitalisierung und der Verbreitung des Internet of Things (IoT) treten auch neue Anforderungen an verteilte Netzwerktechnologien auf. Zurzeit werden in den meisten IoT Netzwerken Daten, welche von Sensoren erfasst werden, in der Cloud verarbeitet. Bei der dafür benötigten Kommunikation kann es zu größeren Verzögerungen kommen, da die Distanz zwischen den Sensoren am Netzwerkrand und der Cloud relativ groß werden kann. Fog Computing (FC) kann dazu beitragen, solche Probleme zu reduzieren, indem die Entfernung zwischen Datenquellen und den verarbeitenden Knoten verringert wird. Dafür werden Geräte, die sich in der Netzwerkarchitektur zwischen den Datenquellen und der Cloud befinden genutzt, um zeitlich kritische Datenverarbeitungen (z. B. für selbstfahrende Fahrzeuge oder Überwachungssysteme) auszuführen. Hierfür brauchen FC-Systeme Mechanismen, um die auszuführenden Aufgaben den einzelnen Knoten im Netzwerk zuzuteilen. Die Zuteilung zielt üblicherweise darauf ab, die Dienstgüte im gesamten System zu optimieren. Oft wird diese Aufgabe mit einem Optimierungsproblem, welches zentral berechnet wird, gelöst. Hierfür sind aber vollständige Informationen über den Status des FC-Systems notwendig. Weiterhin kann die notwendige Berechnung sehr komplex werden. Um eine hohe Skalierbarkeit von FC-Systemen zu ermöglichen, wird darum eine Lösung, mit welcher sich das Problem über die Knoten verteilt lösen lässt, benötigt. Das Ziel dieser Arbeit ist es, einen Prototyp für ein FC-System zu entwerfen und zu implementieren, welcher die Spieltheorie nutzt, um die Rechenkapazitäten der einzelnen Knoten zuzuweisen. Die Spieltheorie wird dabei zur Modellierung von in Konkurrenz stehenden Spielern verwendet. Diese Spieler können individuell und eigensinnig ihre Strategien auswählen. Im FC-Anwendungsfall kann die Auswahl der Strategien der einzelnen Spieler dann verteilt berechnet werden. Wird im Spiel ein sogenanntes Nash Equilibrium (NE) erreicht, dann sollte auch das FC-System in einem stabilen Zustand sein und annähernd optimal performen. In der Evaluation vergleichen wir die Leistungsfähigkeit des spieltheoretischen Ansatzes und einer First-Fit-Heuristik. Zusätzlich beobachten wir, wie sich der neue Ansatz verhält, wenn Sensorknoten während der Laufzeit das System verlassen und betreten können. Unsere Auswertungen zeigen, dass in den Simulationen zuverlässig NEs erreicht werden, solange sich die Anzahl der Sensoren nicht verändert. Betrachten wir die Ausführungszeit einzelner Aufgaben, so wird beim spieltheoretischen Ansatz weniger Zeit benötigt. Bei dynamischen Sensoren werden immer noch Gleichgewichte erreicht oder zumindest angenähert. Befindet sich das Spiel schon nahe an einem NE, treten auch im dynamischen Fall nur noch wenige Strategieänderungen der einzelnen Spieler auf.

Fog Computing; Game Theory; Congestion Game; Computational Offloading; Internet of Things; Ressource Allocation

http://dx.doi.org/10.34726/hss.2021.80466