Optimisation under Data Uncertainty in Wireless Communication Networks

Claßen, Grit; Koster, Arie M. C. A.; Schmeink, Anke

doi:34515

Optimisation under Data Uncertainty in Wireless Communication Networks = Optimierung unter Unsicherheit in drahtlosen Kommunikationsnetzwerken

Claßen, Grit

2015

Verantwortlichkeitsangabevorgelegt von Grit Claßen

ImpressumAachen : Publikationsserver der RWTH Aachen University 2015

UmfangVIII, 258 S. : Ill., graph. Darst.

Aachen, Techn. Hochsch., Diss., 2015

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Koster, Arie M. C. A. (Thesis advisor) ; Schmeink, Anke (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2015-03-04

Online
URN: urn:nbn:de:hbz:82-rwth-2015-016505
URL: https://publications.rwth-aachen.de/record/465292/files/465292.pdf
URL: https://publications.rwth-aachen.de/record/465292/files/465292.pdf?subformat=pdfa

Einrichtungen

Thematische Einordnung (Klassifikation)
DDC: 510

Kurzfassung
In der vorliegenden Dissertation befassen wir uns mit Robustheitsansätzen der mathematischen Optimierung und wenden diese auf Probleme im Bereich drahtloser Kommunikationsnetze mit Datenunsicherheiten an. Unsicherheiten treten häufig in Funknetzen auf, da sich unter anderem die Signalübertragungsqualität ändert oder Nutzeranforderungen schwanken. Robuste und stochastische Optimierung stellen zwei Methodiken dar, um derartige Abweichungen schon in der Planungsphase des Netzwerks zu berücksichtigen. Während stochastische Optimierung im Falle, dass die unsicheren Daten einer im Vorfeld bekannten Wahrscheinlichkeitsverteilung folgen, angewendet werden kann, ist die Verwendung von robuster Optimierung möglich, wenn die Unsicherheiten mit Hilfe von so genannten Unsicherheitsmengen dargestellt werden können. Dabei können Unsicherheitsmengen zum Beispiel aus historischen Daten generiert werden. Wir untersuchen in dieser Arbeit ein Spezialgebiet der stochastischen Optimierung, die sogenannten Chance Constraints, welche mit robuster Optimierung verwandt sind, und drei Robustheitskonzepte. Diese Konzepte sind Γ-Robustheit, die allgemeinere multi-Band Robustheit und der zweistufige Ansatz der adaptiven Robustheit.Um zuverlässige Richtfunknetze zu planen, entwickeln wir diverse (lineare) Formulierungen mit Hilfe von Chance Constraints und präsentieren gültige Ungleichungen und eine primale Heuristik zur Verbesserung des Lösungsprozesses. Ferner wenden wir alle drei Robustheitsansätze in der Planung von Mobilfunknetzen an und stellen jeweils ganzzahlige lineare Programme auf. Für das Γ-robuste Mobilfunknetzplanungsproblem, kurz WNPP, entwickeln wir zusätzlich gültige Ungleichungen und eine alternative Formulierung mittels eines vollständigen Branch-und-Price Algorithmus. Ein Teilproblem des WNPPs ist das Rucksackproblem, ein fundamentales kombinatorisches Problem. Für die multi-Band robuste Version dieses Problems entwickeln wir ein dynamisches Programm, mittels dessen wir neue Komplexitätsergebnisse ableiten. Weiterhin wenden wir dieses dynamische Programm auf eine Variante des multi-Band robusten WNPPs im Rahmen einer Lagrange Relaxierung an. Um die Möglichkeit der vorübergehenden Abschaltung von Basisstationen während Zeiten geringer Nutzernachfragen zu modellieren, wenden wir außerdem die adaptive Robustheit auf das WNPP an.Des Weiteren spielt die Interferenz in Mobilfunknetzen eine zentrale Rolle. Um eine vollständige Beschreibung solcher Netze zu erhalten, entwickeln wir neue Ansätze und erörtern Abwandlungen von bereits existierenden Formulierungen zur Interferenzmodellierung.Alle theoretischen Untersuchungen werden mit Hilfe von zahlreichen komplexen Rechenstudien, durchgeführt auf realistischen Testinstanzen, vervollständigt. Zusätzlich vergleichen wir numerisch die zwei Formulierungen für das Γ-robuste WNPP und Γ-robuste Lösungen mit multi-Band robusten. Basierend auf der sogenannten Leistungsvariabilität, welche inhärent in gemischt ganzzahligen Problemen ist, diskutieren wir abschließend kritisch die Interpretation von Rechenstudien und enden mit einigen Schlussbemerkungen und einem Ausblick auf zukünftige Forschungsthemen.

In this thesis, we study robustness concepts of mathematical optimisation and apply these to wireless network problems which are subject to data uncertainty. Uncertainties occur quite frequently in radio networks as, for instance, the quality of the transmission signal varies or user demands fluctuate. Robust and stochastic optimisation are two methodologies to tackle such deviations already in the planning phase of the network. While stochastic optimisation is a suitable technique in case that the uncertain data obeys a previously known probability distribution, robust optimisation is able to handle uncertain data which can be modelled by a so-called uncertainty set, which may, e.g., be constructed from historical information. One reason for the popularity of robust optimisation is that the theoretical complexity of the original problem is not increased by the incorporation of uncertainty. We investigate one specific area of stochastic optimisation, chance constraints, which are related to robust optimisation, and three robustness concepts. These concepts comprise Γ-robustness, the more general multi-band robustness, and the two-stage approach recoverable robustness.For reliable fixed broadband wireless networks, we develop miscellaneous (linear) formulations based on chance constraints and propose performance improvements such as valid inequalities and a primal heuristic. Furthermore, we apply all three robustness concepts to the planning problem of mobile wireless networks and propose integer linear programming formulations for each robust problem. For the Γ-robust wireless network planning problem (WNPP), we additionally develop valid inequalities and an alternative formulation via a complete branch-and-price framework. Since the knapsack problem (KP), which is one of the most fundamental combinatorial problems, is a subproblem of the WNPP, we study the multi-band robust KP theoretically and derive new complexity results via a dynamic programming algorithm. To apply this algorithm to a variant of the multi-band robust WNPP, we adopt Lagrangian relaxation. Additionally, we incorporate recoverable robustness to the WNPP to model the option of switching base stations off during low traffic times. Furthermore, to obtain a full description of mobile wireless networks, we develop novel approaches and discuss modifications of existing formulations to model interference in the WNPP. All theoretical investigations are supported by several extensive computational studies performed on realistic test instances. Moreover, we compare the two different formulations of the Γ-robust WNPP and Γ-robust to multi-band robust solutions via a numerical evaluation. Finally, we discuss the interpretation of computational studies critically based on the so-called performance variability which is intrinsic to mixed integer linear programs. We conclude by final remarks on the investigated robustness concepts and present future research topics.

Fulltext:
PDF PDF (PDFA)
(additional files)