Optimisation under Data Uncertainty in Wireless Communication Networks

• Optimierung unter Unsicherheit in drahtlosen Kommunikationsnetzwerken

Claßen, Grit; Koster, Arie M. C. A. (Thesis advisor); Schmeink, Anke (Thesis advisor)

Aachen : Publikationsserver der RWTH Aachen University (2015)
Doktorarbeit

Aachen, Techn. Hochsch., Diss., 2015

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.