No-regret learning in wireless networks

Dams, Johannes; Hoefer, Martin

doi:34264

No-regret learning in wireless networks = No-Regret-Learning in Drahtlosnetzwerken

Dams, Johannes (Author)

2014

Verantwortlichkeitsangabevorgelegt von Johannes Dams

ImpressumAachen : Publikationsserver der RWTH Aachen University 2014

UmfangVIII, 110 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2014

Zsfassung in dt. u. engl. Sprache. - Druckausg.: Dams, Johannes: No-regret learning in wireless networks

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Hoefer, Martin (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2014-10-16

Online
URN: urn:nbn:de:hbz:82-opus-52377
URL: https://publications.rwth-aachen.de/record/459460/files/5237.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Approximationsalgorithmus (Genormte SW) ; Funknetz (Genormte SW) ; Interferenz (Genormte SW) ; Scheduling (Genormte SW) ; Verteilter Algorithmus (Genormte SW) ; Kanalkapazität (Genormte SW) ; Informatik (frei) ; SINR (frei) ; approximation algorithm (frei) ; wireless network (frei) ; interference (frei) ; scheduling (frei) ; distributed algorithm, capacity maximization (frei) ; power control (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Eine bestimmende Eigenschaft von drahtlosen Netzwerken ist die kabellos per Funk stattfindende Kommunikation. Das Funkspektrum unterliegt hierbei einer Vielzahl von Einflüssen. Insbesondere Interferenz gleichzeitiger Übertragungen kann zu erfolgloser Kommunikation führen. Geräte müssen trotz dieser Interferenz agieren. Die algorithmische Betrachtung von Funknetzwerken impliziert häufig zentralisiert koordinierte Geräte. Diese kann man typischerweise nicht annehmen, da Funknetzwerke von Natur aus dezentralisiert sind. Sogar wenn eine zentrale Instanz existiert, würde die Koordination zu zusätzlichen Übertragungen und Interferenz führen. In dieser Dissertation betrachten wir verteilte adaptive Algorithmen, die nur auf wenige Informationen ange-wiesen sind, um die Anzahl gleichzeitig erfolgreicher Übertragungen zu maximieren. Wir zeigen beweisbare Garantien für diese adaptiven Protokolle. Wir modelieren ein Funknetzwerk als Sender-Empfänger-Paare oder Links, deren Übertragungen sich auf einem Konflikt-Graphen basierend beeinflussen. Dieses Interferenzmodel verallgemeinert vorherige Modelle wie Unit-Disk-Graphen und das Signal-zu-Interferenz-plus-Rausch-Verhältnis (signal-to-interference-plus-noise ratio - SINR). Wir betrachten No-Regret-Algorithmen bekannt aus der Spieltheorie. Diese Algorithmen passen ihre Übertragungswahrscheinlichkeit basierend auf Nutzenfunktionen an, welche den Erfolg vorheriger Übertragungen darstellen. Unser Ansatz erweitert frühere Betrachtungen von Kapazitätsmaximierung in Funknetzwerken mit No-Regret-Techniken. Im ersten Teil dieser Arbeit betrachten wir das Capacity-Maximization Problem, in dem eine Menge maximaler Kardinalität von Links zu wählen ist, sodass Links gleichzeitig erfolgreich übertragen können. Wir identifizieren relevante Eigenschaften und erstellen eine Beweisvorlage für die Analyse von No-Regret-Algorithmen für Capacity-Maximization. Die Beweisvorlage wenden wir auf Szenarien mit bösartigen Störsendern, mehreren Empfängern und Links, die das Netzwerk wieder verlassen dürfen, an. Mehrere Kanäle und Kanalverfügbarkeiten werden unter Anwendung ähnlicher Techniken ebenfalls betrachten. Wir erweitern frühere Arbeiten durch konkurrierende Netzwerke und bösartige Störsender, die wir als Gegenspieler modelieren. Diese Störsender sind eingeschränkt und können nur in einem bestimmten Anteil der Zeitschritte Übertragungen stören. Wir zeigen, dass adaptive No-Regret-Algorithmen konvergieren und die erreichten Approximationsfaktoren von den Parametern des Störsenders abhängen. Angenommen diese Parameter sind bekannt, dann erreichen die Algorithmen sogar konstante Approximationsfaktoren, wenn Störsender genau ihre Beschränkungen erfüllen oder gegen stochastische Störsender. Der Beweis liefert die selben Garantien für weiter verallgemeinerte Szenarien, in denen Sender nicht einen Empfänger erreichen wollen sondern eine Menge von Empfängern. Wir verzichten auch auf die Standardannahme verwandter Arbeiten, dass Links unbegrenzt im Netzwerk verbleiben. Wir erneuern die Beweisvorlage mit einem Verlust von O(log n) in der Approximationsgüte. Weil das Funkspektrum mehr und mehr ausgelastet ist, haben Regulierungsbehörden Pläne ausgearbeitet, dass Primärnutzer, welche das exklusive Recht besitzen bestimmte Frequenzen oder Kanäle zu nutzen, ihr Spektrum für Sekundärnutzer öffnen können. Für dieses Szenario erweitern wir Capacity-Maximization durch mehrere Kanäle und stochastische Verfügbarkeit dieser Kanäle. Wir nutzen verschiedene Arten von Regret um konstante Approximationsfaktoren zu erreichen, wenn die Verfügbarkeit für verschiedene Links unkorreliert ist. Andernfalls hängt die Garantie von der Korrelation ab. Tatsächlich sind viele Funksender fähig, ihre Sendeleistung zu beeinflussen. Daher betrachten wir im zweiten Teil dieser Dissertation das Power-Control Problem, in dem Links die minimale Energie finden sollen, so dass alle Links erfolgreich übertragen können. Wir analysieren einen bekannten Fixpunkt-Ansatz von Foschini und Miljanic im Hinblick auf die Konvergenzzeit und beziehen dies auf No-Regret-Sequenzen, die ebenfalls zur optimalen Energiezuweisung konvergieren. Für No-Regret-Algorithmen können wir sogar einen bestimmten Anteil erfolgreicher Übertragungen garantieren.

The defining property of wireless networks is that communications are not done over a wired connection. In contrast, radio spectrum is used which is subject to a variety of influences. Especially, interference from other concurrent transmissions can cause communication attempts to be unsuccessful. Wireless devices have to operate and perform transmissions despite this interference. Algorithmic considerations often assume a centralized coordination of devices. This coordination behavior can typically not be assumed, as wireless networks are inherently distributed. Even if a central authority existed, the necessary coordination would introduce additional traffic and interference. In this thesis, we consider distributed adaptive algorithms that only rely on very little information to maximize the number of successful transmissions. We give provable guarantees for the performance of these adaptive protocols. We model a wireless network to consist of sender-receiver pairs denoted as links whose transmissions interfere based on a conflict graph. This model generalizes previous interference models like unit-disk graphs or ones based on the signal-to-interference-plus-noise ratio (SINR). We consider no-regret-learning approaches known from game theory. These algorithms adapt transmission probabilities based on utilities, which represent feedback on the success of previous transmission attempts. Our approach extends previous considerations of no-regret techniques for capacity maximization in wireless networks. In the first part of this thesis, we consider the capacity-maximization problem. The task is to choose a maximal-cardinality set of links that can simultaneously transmit successfully. We identify key properties and use them to introduce a flexible proof template for the analysis of adaptive no-regret learning algorithms. This proof template is applied to settings with adversarial jammers, multiple receivers, and links being allowed to leave the network almost arbitrarily. Settings with multiple channels and channel availabilities are also considered by applying similar techniques. We extend previous works by introducing concurrent networks or malicious devices, which are modeled as adversarial jammers. These jammers are limited and can render all transmissions in a certain fraction of time steps unsuccessful. We show that no-regret learning algorithms are able to converge with approximation factors depending on parameters of the jammer. Assuming these parameters to be known to the algorithm, they even achieve constant-factor approximations when jammers tightly fulfill their limitations or against a stochastic jammer. The proof template yields the same guarantees when applied to further generalized scenarios. Here, senders do not strive to transmit data to one receiver but to a set of receivers. At the expense of O(log n) in the approximation guarantees, we also omit the standard assumption from related works that links stay in the network indefinitely. As the wireless spectrum becomes more and more utilized, regulatory authorities devise plans to let primary users with the exclusive right to use a certain part of the spectrum open up their spectrum for secondary usage. To consider this scenario, we extend the capacity-maximization setting to multiple channels and stochastic channel availabilities. We utilize different notions of regret to achieve constant-factor approximations if the availabilities are uncorrelated among links. Otherwise the guarantees depend on the degree of correlation. Many wireless devices are actually capable of adjusting their transmission power. Thus, in the second part of this thesis, we consider the power-control problem, where we strive to find a minimal power assignment such that all links can transmit successfully. We analyze a well-known fixed-point approach of Foschini and Miljanic in terms of convergence time and relate this to no-regret learning also converging to the optimal power assignment. For no-regret learning algorithms we can even guarantee a certain fraction of time steps to be successful.

Fulltext:
PDF