Evolutionary multi-objective task allocation for IoT networks

Abstract

The Internet of Things (IoT) has been an area of growing research interest for decades and continues to expand in use cases and applications. Most of these consist of highly heterogeneous and resource-constrained devices interconnected through dynamic wireless networks. Efficient task allocation is essential to ensuring reliable operation in such environments, as the performance of the network with respect to metrics such as energy consumption, latency, reliability, and network lifetime depends strongly on where the given tasks are executed. However, this Task Allocation Problem (TAP) is NP-hard, and optimizing multiple conflicting objectives under dynamic network conditions further increases its complexity. Existing approaches typically address only simplified variants of the problem, focus on single-objective optimization, or assume static and failure-free networks, limiting their applicability in real-world IoT deployments. This thesis presents a decomposition of the TAP into distinct sub-problems and introduces a series of evolutionary multi-objective optimization algorithms to address them. First, the Multi-Objective Task Allocation Algorithm (MOTA) is proposed to solve the base problem in static networks. This foundation is subsequently extended to incorporate node failures (Availability-Aware Multi-Objective Task Allocation Algorithm (A-MOTA)), node mobility (Mobility-Aware Multi-Objective Task Allocation Algorithm (M-MOTA)), and then the full range of dynamic changes in network conditions (Dynamic Multi-Objective Task Allocation Algorithm (D-MOTA)). To ensure applicability in large-scale or hardware-constrained environments, surrogate-assisted optimization techniques are further developed, significantly reducing computational cost while maintaining solution quality. Comprehensive experimental evaluations across a variety of network topologies and scenarios demonstrate that the proposed algorithms consistently outperform other strategies in terms of solution quality, robustness, and adaptability. These results confirm the feasibility and impact of the proposed multi-objective task allocation algorithms in IoT networks.

Das IoT ist seit Jahrzehnten ein Forschungsgebiet mit wachsendem Interesse und wird zunehmend in verschiedensten Einsatzbereichen genutzt. Die meisten dieser Systeme bestehen aus heterogenen und ressourcenbeschränkten Geräten, die über drahtlose Netzwerke miteinander verbunden sind. Eine effiziente Aufgabenverteilung ist entscheidend für einen zuverlässigen Betrieb in solchen Umgebungen, da die Leistungsfähigkeit des Netzwerks in Bezug auf Kennzahlen wie Energieverbrauch, Latenz und Lebensdauer stark davon abhängt, an welchen Geräten die jeweiligen Aufgaben ausgeführt werden. Das zugrunde liegende Zuordnungsproblem ist jedoch NP-schwer, und die Optimierung mehrerer widersprüchlicher Ziele unter dynamischen Netzwerkbedingungen erhöht die Komplexität zusätzlich. Bestehende Ansätze behandeln in der Regel nur vereinfachte Varianten des Problems, konzentrieren sich auf optimierung eines einzelnen Zieles, oder gehen von statischen und fehlerfreien Netzwerken aus, was ihre Anwendbarkeit in realen IoT-Umgebungen einschränkt. Diese Arbeit präsentiert eine systematische Zerlegung des Zuordnungsproblems in Teilprobleme und stellt eine Reihe evolutionärer Multikriterieller Optimierungsalgorithmen zu deren Lösung vor. Zunächst wird der MOTA vorgestellt, um das Grundproblem in statischen Netzwerken zu lösen. Darauf aufbauend wird der Ansatz schrittweise erweitert, um Ausfälle (A-MOTA), Mobilität (M-MOTA), sowie schließlich das vollständige Spektrum dynamischer Änderungen der Netzwerkbedingungen (D-MOTA) zu berücksichtigen. Um die Anwendbarkeit in hardwarebeschränkten Umgebungen sicherzustellen, werden zusätzlich surrogategestützte Optimierungstechniken entwickelt, die die Rechenkosten erheblich reduzieren, ohne die Lösungsqualität zu beeinträchtigen. Umfassende experimentelle Auswertungen über verschiedene Netzwerktopologien und Szenarien hinweg zeigen, dass die vorgeschlagenen Algorithmen existierende Strategien in Bezug auf Lösungsqualität, Robustheit und Anpassungsfähigkeit durchgängig übertreffen. Diese Ergebnisse bestätigen die Machbarkeit und den Nutzen der multkriteriellen Aufgabenverteilung in IoT-Netzwerken.