Scheduling in wireless networks with oblivious power assignments

Fanghänel, Alexander; Vöcking, Berthold

doi:30402

Scheduling in wireless networks with oblivious power assignments = Scheduling in Funknetzwerken mit distanzbasierten Sendeleistungen

Fanghänel, Alexander (Author)

2011

Verantwortlichkeitsangabevorgelegt von Alexander Fanghänel

ImpressumAachen : Publikationsserver der RWTH Aachen University 2011

UmfangX, 101 S.

Aachen, Techn. Hochsch., Diss., 2010

Zsfassung in engl. und dt. Sprache

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Vöcking, Berthold (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2010-12-07

Online
URN: urn:nbn:de:hbz:82-opus-35149
URL: https://publications.rwth-aachen.de/record/63842/files/3514.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Scheduling (Genormte SW) ; Funknetz (Genormte SW) ; Routing (Genormte SW) ; Interferenz (Genormte SW) ; Online-Algorithmus (Genormte SW) ; Approximationsalgorithmus (Genormte SW) ; Informatik (frei) ; SINR (frei)

Thematische Einordnung (Klassifikation)
DDC: 004
ccs: F.2.2

Kurzfassung
Diese Dissertation beschäftigt sich mit dem Scheduling von Kommunikationsanfragen in drahtlosen Netzwerken unter dem physikalischen Interferenzmodell. Wir untersuchen, wie viele Zeitschritte benötigt werden, damit n solcher Anfragen, modelliert als Paare von Punkten aus einem metrischen Raum, ihre Nachrichten kollisionsfrei senden können. Unser Ziel ist es, die Anzahl der notwendigen Zeitschritte zu minimieren. Dazu weisen wir jedem Kommunikationspaar einen Zeitschritt und eine Sendeleistung zu, so dass die Interferenz an allen Empfängern im selben Zeitschritt hinreichend klein ist. Interferenz modellieren wir unter Zuhilfenahme des sogenannten Signal-zu-Interferenz-plus-Rausch-Verhältnisses. Dieses setzt die empfangene Signalstärke in Verhältnis zu der Summe aller anderen zeitgleich empfangenen Signale plus Hintergrundrauschen. Wir konzentrieren uns in dieser Arbeit auf distanzbasierte Sendeleistungen, bei denen jedem Paar eine Leistung zugewiesen wird, die nur vom Abstand der beiden Kommunikationspartner abhängig ist. Die bekanntesten distanzbasierten Zuweisungsschemata sind lineare Sendeleistungen, bei denen die Energie proportional zum Abstand der Punkte ist, und uniforme Sendeleistungen, bei denen jeder Sender mit der gleichen, konstanten Energie sendet. Im ersten Teil geben wir ein Interferenzmaß an, dass es uns ermöglicht, eine untere Schranke für die Anzahl benötigter Zeitschritte sowohl für das lineare als auch für das optimale Sendeleistungsschema anzugeben. Weiterhin präsentieren wir auf dem Interferenzmaß basierende verteilte Scheduling-Algorithmen für lineare Sendeleistungen, die diese untere Schranken bis auf kleine Faktoren erreichen. Die nächste Frage, die uns beschäftigt, ist die Folgende. Wie gut können Algorithmen mit distanzbasierten Sendeleistungen im Vergleich zu optimalen Algorithmen sein? Wir zeigen, dass wenn wir nur die Anzahl n der Kommunikationsanfragen berücksichtigen, für solche Algorithmen nur die triviale untere Schranke von Omega(n) gezeigt werden kann. Wenn wir hingegen ein bidirektionales Kommunikationsmodell betrachten, gelten diese Schranken nur noch für einige distanzbasiere Sendeleistungsschemata, darunter auch das lineare und das uniforme Schema. Ausgehend von dieser Beobachtung starten wir eine detaillierte Untersuchung des bidirektionalen Modells. In diesem können zwei Kommunikationspartner während eines Zeitschrittes Nachrichten in beide Richtungen austauschen, solange nur einer von beiden zu einem gegebenen Zeitpunkt sendet. Wir zeigen, dass Sendeenergien proportional zur Quadratwurzel der Distanz zwischen den Knoten eine exponentiell bessere Worst-Case-Schranke liefern als lineare oder uniforme Sendeenergien. Im letzten Teil untersuchen wir die Kapazität von drahtlosen Netzwerken in einem Online-Szenario. Wir nehmen an, dass Kommunikationsanfragen nacheinander gestellt werden. Bei Ankunft einer Anfrage müssen wir entscheiden, ob wir diese akzeptieren oder zurückweisen. Dabei wollen wir möglichst viele Anfragen akzeptieren, ohne dass an einem der akzeptierten Empfänger die Interferenz zu hoch wird. Unsere Analyse zeigt eine signikante Diskrepanz zwischen deterministischen Offline- und Online-Algorithmen. Weiterhin präsentieren wir einen randomisierten Online-Algorithmus, der die deterministischen Algorithmen deutlich übertrifft.

In this thesis we analyze scheduling in wireless networks under the physical model. In particular, we ask the following question. Given n communication requests as pairs of nodes from a metric space, how fast can we schedule all of them? We have to assign a schedule slot and a transmission power to each request and need to ensure that during each schedule step the interference at the addressed receivers is not too high. The interference is modeled in terms of the Signal to Interference Plus Noise Ratio (SINR) that compares the received signal strength with the sum of all other simultaneously sent signals plus ambient noise. We strive to minimize the schedule length. We investigate scheduling using oblivious power assignments where each request uses a transmission power depending only on the path loss between sender and receiver. The most famous examples of such power assignments are the uniform assignment, where each sender uses the same transmission power, and the linear assignment that uses transmission powers linear in the path loss between the two nodes. We first present a measure of interference that allows us to lower bound the schedule length when using linear or optimal power assignment. Based on this measure of interference we devise distributed scheduling algorithms for the linear power assignment reaching the minimal schedule length up to small factors. Second, we study the limitations of oblivious power assignments by proving lower bounds for scheduling algorithms using these power assignments. In particular, when only considering the number of nodes in the lower bound, oblivious power assignments cannot yield an approximation ratio asymptotically better than the worst possible performance guarantee. When modifying the problem to bidirectional communication these lower bounds only hold for some oblivious power assignments, e. g., for uniform and linear power assignment. This motivated us to deeply investigate the bidirectional variant of the problem. Here, in every schedule step the two nodes of a pair can exchange messages in both directions, as long as only one of them acts as a sender at any given time. We present a detailed analysis of bidirectional scheduling using the square root power assignment which provides an exponential shorter worst-case schedule than, e. g., the linear or uniform power assignment. In the last part we raise the question of the capacity of wireless networks in an online setting. To be more specic, requests arrive over time and on arrival of a single request we have to either accept or reject it. The objective is to accept as much requests as possible such that all accepted requests form an SINR feasible set. Not only does our analysis reveal an exponential gap between the performance of deterministic offine and online algorithms, we also present a well-performing randomized algorithm for this problem.

Fulltext:
PDF