TU Darmstadt / ULB / TUprints

Context-Aware Decision Making in Wireless Networks: Optimization and Machine Learning Approaches

Klos, Sabrina (2019):
Context-Aware Decision Making in Wireless Networks: Optimization and Machine Learning Approaches.
Darmstadt, Technische Universität, DOI: 10.25534/tuprints-00009176,
[Ph.D. Thesis]

Available under CC-BY-NC-SA 4.0 International - Creative Commons, Attribution Non-commercial, Share-alike.

Download (8MB) | Preview
Item Type: Ph.D. Thesis
Title: Context-Aware Decision Making in Wireless Networks: Optimization and Machine Learning Approaches
Language: English

In future wireless networks, an enormous number of heterogeneous devices will be connected, leading to a dramatic increase in data traffic. At the same time, future applications will have significantly higher requirements with respect to data rates, reliability, and latency. Conventional approaches, which aim at only improving the communication capabilities of wireless networks, will not be sufficient to satisfy the more demanding requirements arising in future. Hence, a paradigm shift is needed. While conventionally perceived as pure communication networks, wireless networks can provide not only communication resources, but also computation, caching, data collection, and even user resources. Such resources can be part of the network infrastructure and of the wirelessly connected devices and their users. This radically different view on wireless networks as networks of distributed connected resources calls for the development of new techniques that jointly consider and leverage different types of resources in order to improve the system performance.

In this thesis, we show that such new techniques that jointly consider and leverage different types of resources require context-aware decision making. This is due to the fact that first, resources need to be shared and secondly, trade-offs between different types of resources exist. Thirdly, the optimal resource allocation may depend not only on network conditions, but also on other node-related, user-related or externally given conditions, the so-called context. We provide an overview of context-aware decision making by discussing context awareness, architectures of decision making, and designs of decision agents. Designing a context-aware decision-making framework requires to formulate a context-aware system model. In particular, decision agents responsible for resource allocation need to be identified. These agents may be part of a centralized, decentralized or hierarchical architecture of decision making and a suitable architecture needs to be selected. Finally, designing decision agents requires to model and classify the problem to be solved and to develop an appropriate method according to which decision agents take decisions. We emphasize two designs relevant for context-aware decision making in wireless networks, namely, optimization-based approaches and machine-learning-based approaches, in the latter case specifically the framework of multi-armed bandits.

Moreover, in this thesis, we study three candidate techniques for wireless networks that jointly consider and leverage different types of resources, namely, computation offloading in multi-hop wireless networks, caching at the edge of wireless networks, and mobile crowdsourcing. For each technique, we identify a fundamental problem requiring context-aware decision making, propose a novel framework for context-aware decision making, and solve the problem using the proposed framework.

Computation offloading allows wirelessly connected devices to offload computation tasks to resource-rich servers. This may reduce the devices' task completion times and their energy consumption. Computation offloading hence trades computation resources off against communication resources. In this thesis, for the first time, we study computation offloading in multi-hop wireless networks, where wirelessly connected devices assist each other as relay nodes. We identify the fundamental problem of context-aware computation offloading for energy minimization in multi-hop wireless networks. We propose a novel model that takes into account channel conditions, computing capabilities of the devices, task characteristics, and battery constraints at relay nodes since the effect of computation offloading on the devices' energy consumption depends on these context factors. Based on this model, we take an optimization-based approach and formulate the considered problem as a multi-dimensional knapsack problem, which takes into account that offloading decisions in multi-hop networks are non-trivially coupled as communication resources of relay nodes need to be shared. Finally, we propose a novel context-aware greedy heuristic algorithm for computation offloading in multi-hop networks. Based on its centralized architecture of decision making, this algorithm enables a central entity to take offloading decisions using centrally collected context information. We show that despite its centralized architecture, the algorithm has a small communication overhead. Numerical results demonstrate that the offloading solution found by the proposed algorithm on average reduces the network energy consumption by 13% compared to the case when no computation offloading is used. Moreover, the proposed algorithm yields near-optimal results in the considered offloading scenarios, with a maximal deviation of less than 6% from the global optimum.

Caching at the edge allows popular content to be cached close to mobile users in order to serve user requests locally, thus reducing backhaul and cellular traffic as well as the latency for the user. Hence, caching at the edge exploits caching resources in order to save communication resources. In this thesis, we identify the fundamental problem of context-aware proactive caching for maximizing the number of cache hits under missing knowledge about content popularity. We introduce a new model for context-aware proactive caching that takes into account that different users may favor different content and that the users' preferences may depend on their contexts. Using a machine-learning-based approach based on contextual multi-armed bandits (contextual MAB), we propose a novel online learning algorithm for context-aware proactive caching. Based on its decentralized architecture of decision making, this algorithm enables the controller of a local cache to learn context-specific content popularity, which is typically not available a priori, online over time. The proposed algorithm takes the cache operator's objective into account by allowing for service differentiation. We analyze the computational complexity as well as the memory and communication requirements of the algorithm, and we show how the algorithm can be extended to practical requirements. Moreover, we derive a sublinear upper bound on the regret of the algorithm, which characterizes the learning speed and proves that the algorithm converges to the optimal cache content placement strategy. Simulations based on real data show that, depending on the cache size, the proposed algorithm achieves up to 27% more cache hits than the best algorithm taken from the literature.

Mobile crowdsourcing (MCS) allows task owners to outsource tasks via a mobile crowdsourcing platform (MCSP) to a set of workers. Hence, MCS exploits user resources for task solving. In this thesis, we identify the fundamental problem of context-aware worker selection for maximizing the worker performance in MCS under missing knowledge about expected worker performance. We present a novel model for context-aware worker selection in MCS that can cope with different task types and that explicitly allows worker performance to be a non-linear function of both task and worker context. Using a machine-learning-based approach based on contextual MABs, we propose a new context-aware hierarchical online learning algorithm for worker selection in MCS. Based on the proposed hierarchical architecture of decision making, this algorithm splits information collection and decision making among several entities. Local controllers (LCs) in the workers' mobile devices learn the workers' context-specific performances online over time. The MCSP centrally assigns workers to tasks based on a regular information exchange with the LCs. This novel approach solves two critical aspects. First, personal worker context is kept locally in the LCs, which reduces communication overhead and preserves the privacy of the workers, who may not want to share personal context with the MCSP. Secondly, the MCSP is enabled to select the most capable workers for each task based on what the LCs learn about their workers' context-specific performances, which are typically unknown a priori. We analyze the computational complexity and derive upper bounds on the local memory requirements of the algorithm and on the number of times the quality of each worker must be assessed. Moreover, we show that the more access to worker context is granted to the LCs the lower are the communication requirements of the proposed algorithm compared to an equivalent centralized approach. In addition, we derive a sublinear upper regret bound, which characterizes the learning speed and proves that the algorithm converges to the optimal worker selection strategy. Finally, we show in simulations based on synthetic and real data that, depending on the availability of workers, the proposed algorithm achieves an up to 49% higher cumulative worker performance than the best algorithm from the literature.

Alternative Abstract:
Alternative AbstractLanguage
In zukünftigen drahtlosen Netzwerken wird eine extrem hohe Zahl an heterogenen Geräten miteinander kommunizieren, sodass der Datenverkehr enorm ansteigen wird. Zudem werden zukünftige Anwendungen signifikant höhere Anforderungen in Bezug auf Datenraten, Zuverlässigkeit und Latenzzeiten aufweisen. Konventionelle Ansätze, die lediglich darauf abzielen, die Kommunikationsfähigkeiten der drahtlosen Netzwerke zu verbessern, reichen nicht aus, um zukünftigen Anforderungen gerecht zu werden. Daher ist ein Paradigmenwechsel nötig. Konventionell werden drahtlose Netzwerke als reine Kommunikationsnetzwerke verstanden. Zukünftig verfügen sie aber neben Kommunikationsressourcen in zunehmendem Maße auch über Rechen-, Speicher-, Datenerfassungs- und sogar Nutzerressourcen. Solche Ressourcen sind sowohl Teil der Netzwerkinfrastruktur als auch der drahtlos verbundenen Geräte und ihrer Nutzer. Diese fundamental andere Auffassung von drahtlosen Netzwerken als Netzwerke verteilter, miteinander verbundener Ressourcen erfordert die Entwicklung neuer Verfahren, die verschiedene Arten von Ressourcen gemeinsam betrachten und einsetzen, um die Performanz drahtloser Netzwerke zu erhöhen. In dieser Arbeit zeigen wir, dass Methoden zur kontextbezogenen Entscheidungsfindung für neue Verfahren, die verschiedene Arten von Ressourcen in drahtlosen Netzwerken gemeinsam betrachten und einsetzen, benötigt werden. Dies liegt daran, dass erstens Ressourcen geteilt werden müssen und dass zweitens zwischen den verschiedenen Arten von Ressourcen abgewogen werden muss. Drittens kann die optimale Ressourcenallokation nicht nur von Netzwerkbedingungen, sondern auch von weiteren Kontextfaktoren abhängen, die zum Beispiel die Knoten, die Nutzer oder externe Gegebenheiten betreffen. Wir geben einen Überblick über kontextbezogene Entscheidungsfindung, indem wir Kontextbewusstsein, Entscheidungsarchitekturen und Agentenentwürfe} diskutieren. Zunächst wird zur Erstellung eines Rahmenwerks für kontextbezogene Entscheidungsfindung ein kontextbewusstes Modell des Systems benötigt. Zudem müssen Entscheidungsträger, sogenannte Agenten, bestimmt werden, die innerhalb des Rahmenwerks für die Ressourcenallokation verantwortlich sind. Die Agenten können Teil einer zentralisierten, dezentralisierten oder hierarchischen Entscheidungsarchitektur sein. Zuletzt muss ein Entwurf der Agenten erstellt werden, indem das betrachtete Entscheidungsproblem modelliert und klassifiziert wird, und eine passende Methode entwickelt wird, anhand derer die Agenten Entscheidungen treffen. Relevante Methoden sind insbesondere Optimierungsansätze und Ansätze des maschinellen Lernens, im letzteren Fall insbesondere das Rahmenwerk des mehrarmigen Banditen. Darüber hinaus untersuchen wir in dieser Arbeit drei Verfahren, die verschiedene Arten von Ressourcen in drahtlosen Netzwerken gemeinsam betrachten und einsetzen. Diese sind die Auslagerung von Rechenaufgaben (Computation Offloading) in drahtlosen Multi-Hop-Netzwerken, das Speichern von Inhalten am Rand des drahtlosen Netzwerks (Caching at the Edge) und das Auslagern von Aufgaben an eine große Anzahl von mobilen Nutzern über das Internet (Mobile Crowdsourcing). Für jedes dieser drei Verfahren identifizieren wir ein fundamentales kontextbezogenes Entscheidungsproblem und schlagen ein neuartiges Rahmenwerk für kontextbezogene Entscheidungsfindung vor. Computation Offloading erlaubt es drahtlos verbundenen Geräten, Rechenaufgaben an ressourcenreiche Server auszulagern, was die Bearbeitungszeit der Rechenaufgaben und den Energieverbrauch der Geräte verringern kann. Somit wird mithilfe von Computation Offloading zwischen Rechenressourcen und Kommunikationsressourcen abgewogen. In dieser Arbeit untersuchen wir zum ersten Mal Computation Offloading in drahtlosen Multi-Hop-Netzwerken, in welchen drahtlos verbundene Geräte die Daten anderer Geräte im Sinne einer Relaisstation weiterleiten. Wir identifizieren das fundamentale Problem des kontextbezogenen Computation Offloadings mit dem Ziel der Energieminimierung in drahtlosen Multi-Hop-Netzwerken. Wir schlagen ein neuartiges Modell vor, welches die Kanalbedingungen, die Rechenfähigkeiten der Geräte, die Eigenschaften der Rechenaufgaben und die Batteriebeschränkungen der Relaisstationen berücksichtigt, da der durch Computation Offloading erzielte Nutzen von diesen Kontextfaktoren abhängt. Basierend auf dem vorgeschlagenen Modell wählen wir einen Optimierungsansatz und formulieren das betrachtete Problem als ein mehrdimensionales Rucksackproblem, welches die nichttrivialen Kopplungen bei der Auslagerung von Rechenaufgaben einbezieht, die sich daraus ergeben, dass die Kommunikationsressourcen der Relaisstationen geteilt werden müssen. Zuletzt schlagen wir einen neuartigen kontextbezogenen, heuristischen Greedy-Algorithmus für Computation Offloading in drahtlosen Multi-Hop-Netzwerken vor. Basierend auf einer zentralisierten Entscheidungsarchitektur ermöglicht dieser Algorithmus einem zentralen Agenten, Entscheidungen über die Auslagerung von Rechenaufgaben unter Zuhilfenahme von zentral gesammelten Kontextinformationen zu treffen. Wir zeigen, dass der Algorithmus trotz seiner zentralisierten Architektur einen geringen Kommunikationsaufwand aufweist. Numerische Ergebnisse legen dar, dass das Auslagern von Rechenaufgaben auf Basis des vorgeschlagenen Algorithmus den Energieverbrauch des Netzwerks im Mittel um 13% senkt, im Vergleich zu dem Fall, dass alle Rechenaufgaben lokal von den Geräten berechnet werden. Zudem erzielt der vorgeschlagene Algorithmus, mit einer maximalen Abweichung von unter 6% vom globalen Optimum, nahezu optimale Lösungen. Mittels Caching at the Edge werden populäre Inhalte nah bei den mobilen Nutzern gespeichert, um deren Anfragen lokal zu bedienen, wodurch die Menge an Mobilfunkverkehr und die Latenzzeiten der Nutzer reduziert werden. Somit werden mithilfe von Caching at the Edge Speicherressourcen ausgenutzt, um Kommunikationsressourcen zu sparen. In dieser Arbeit identifizieren wir das grundlegende Problem des kontextbezogenen Cachings at the Edge mit dem Ziel der Maximierung der Anzahl an Nutzeranfragen, die durch die Inhalte im Cache-Speicher abgedeckt werden können (Cache Hits), unter fehlender a priori Kenntnis der Popularität von Inhalten. Wir stellen ein neues Modell für kontextbezogenes proaktives Caching at the Edge vor, welches einbezieht, dass verschiedene Nutzer verschiedene Inhalte bevorzugen können und dass die Präferenzen der Nutzer von ihren Kontexten abhängen können. Unter Verwendung eines Ansatzes des maschinellen Lernens, basierend auf dem Rahmenwerk des kontextabhängigen mehrarmigen Banditen, schlagen wir einen neuartigen Online-Lernalgorithmus für kontextbezogenes proaktives Caching at the Edge vor. Auf Basis einer dezentralisierten Entscheidungsarchitektur ermöglicht dieser Algorithmus dem Controller eines lokalen Cache-Speichers, die kontextspezifische Popularität von Inhalten, die typischerweise a priori nicht bekannt ist, online im Laufe der Zeit zu erlernen. Der vorgeschlagene Algorithmus berücksichtigt die Zielvorgaben des Betreibers eines Cache-Speichers, indem die Differenzierung von Services ermöglicht wird. Wir analysieren die Komplexität, den Speicher- und den Kommunikationsbedarf des Algorithmus und zeigen, wie der Algorithmus an praktische Anforderungen angepasst werden kann. Außerdem leiten wir eine sublineare obere Schranke für den sogenannten Regret des Algorithmus her, welche die Lerngeschwindigkeit des Algorithmus charakterisiert und beweist, dass der Algorithmus gegen die optimale Inhaltsplatzierungsstrategie konvergiert. Simulationen auf Basis realer Daten zeigen, dass der vorgeschlagene Algorithmus, in Abhängigkeit der Größe des Cache-Speichers, bis zu 27% mehr Cache Hits erzielt als der beste Algorithmus aus der Literatur. Mobile Crowdsourcing (MCS) erlaubt es Inhabern von Aufgaben, diese Aufgaben mittels einer Mobile-Crowdsourcing-Plattform (MCSP) über das Internet an eine große Anzahl von mobilen Nutzern auszulagern. Somit nutzen MCS-Anwendungen Nutzerressourcen zur Aufgabenlösung aus. In dieser Arbeit identifizieren wir das fundamentale Problem der kontextbezogenen Auswahl von mobilen Nutzern in MCS-Anwendungen mit dem Ziel der Maximierung der Arbeitsleistung unter fehlender a priori Kenntnis der zu erwartenden Arbeitsleistungen individueller Nutzer. Wir stellen ein neuartiges Modell für die kontextbezogene Auswahl von Nutzern zur Aufgabenlösung in MCS-Anwendungen vor, welches verschiedenartige Aufgabentypen zulässt, und welches zudem explizit berücksichtigt, dass die Arbeitsleistung eine nichtlineare Funktion sowohl des Aufgabenkontextes als auch des Nutzerkontextes sein kann. Unter Verwendung eines Ansatzes des maschinellen Lernens, basierend auf dem Rahmenwerk des kontextabhängigen mehrarmigen Banditen, schlagen wir einen neuartigen kontextbezogenen hierarchischen Online-Lernalgorithmus für die Auswahl von Nutzern zur Aufgabenlösung in MCS-Anwendungen vor. Auf Basis einer hierarchischen Entscheidungsarchitektur teilt dieser Algorithmus die Datenerfassung und die Entscheidungsfindung unter mehreren Agenten auf. Lokale Controller in den mobilen Endgeräten der Nutzer erlernen die kontextspezifischen Arbeitsleistungen der Nutzer online im Laufe der Zeit. Basierend auf einem regelmäßigen Informationsaustausch mit den lokalen Controllern weist die zentrale MCSP den Nutzern Aufgaben zu. Dieser neuartige Ansatz löst zwei kritische Punkte. Zum einen verbleibt der persönliche Kontext der Nutzer lokal, was den Kommunikationsaufwand reduziert und die Privatsphäre der Nutzer schützt, da letztere ihren persönlichen Kontext möglicherweise nicht mit der MCSP teilen möchten. Zum anderen ermöglicht der Ansatz der MCSP, mithilfe der von den lokalen Controllern erlernten kontextspezifischen Arbeitsleistungen der Nutzer, die typischerweise a priori unbekannt sind, für jede Aufgabe die am besten geeigneten Nutzer auszuwählen. Wir analysieren die Komplexität des Algorithmus und leiten obere Schranken für seinen Speicherbedarf und für die maximal benötigte Anzahl an Qualitätsüberprüfungen eines einzelnen Nutzers her. Außerdem zeigen wir, dass je mehr Nutzerkontext die lokalen Controller zur Verfügung gestellt bekommen, desto kleiner wird der Kommunikationsbedarf des vorgeschlagenen Algorithmus im Vergleich zu einem äquivalenten zentralisierten Ansatz. Zudem leiten wir eine sublineare obere Schranke für den Regret des Algorithmus her, welche die Lerngeschwindigkeit des Algorithmus charakterisiert und beweist, dass der Algorithmus gegen die optimale Nutzerauswahlstrategie konvergiert. Zuletzt zeigen wir mittels Simulationen auf Basis synthetischer und realer Daten, dass der vorgeschlagene Algorithmus, in Abhängigkeit der Nutzerverfügbarkeit, eine bis zu 49% höhere kumulative Arbeitsleistung erzielt als der beste Algorithmus aus der Literatur.German
Place of Publication: Darmstadt
Classification DDC: 600 Technik, Medizin, angewandte Wissenschaften > 620 Ingenieurwissenschaften
Divisions: 18 Department of Electrical Engineering and Information Technology > Institute for Telecommunications > Communications Engineering
Date Deposited: 11 Dec 2019 12:05
Last Modified: 09 Jul 2020 02:47
DOI: 10.25534/tuprints-00009176
URN: urn:nbn:de:tuda-tuprints-91761
Referees: Klein, Prof. Dr. Anja and Freisleben, Prof. Dr. Bernd
Refereed: 29 August 2019
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/9176
Actions (login required)
View Item View Item