Algorithmen zur Planung und Optimierung
moderner Kommunikationsnetze

Vom Promotionsausschuss der
Technischen Universität Hamburg-Harburg
zur Erlangung des akademischen Grades
Doktor-Ingenieur
genehmigte Dissertation

von

Dirk Beckmann

2001

Kurzfassung

In dieser Arbeit werden Algorithmen zur Optimierung unterschiedlicher Arten von Kommunikationsnetzen vorgestellt. Konkret handelt es sich dabei um Verfahren zur Frequenzplanung in Mobilfunknetzen sowie Methoden zur Kapazitätszuweisung und Dimensionierung von ATM-Netzen (A-synchroner Transfermodus) und optischen Wellenlängenmultiplex-Netzen, wobei unter anderem auch geeignete Redundanzkonzepte im Rahmen der Netzplanung berücksichtigt werden. Die bei den genannten Netzen untersuchten Probleme der Netzplanung erfordern dabei jeweils die Lösung komplexer diskreter Optimierungsprobleme, für welche sich die Eigenschaft der NP-Vollständigkeit nachweisen lässt. Dies hat zur Folge, dass für praxisrelevante Planungsprobleme die Bestimmung des globalen Optimums in der Regel nicht möglich ist und man statt dessen auf geeignete Näherungsverfahren zurückgreifen muss.

Somit werden in dieser Arbeit neben Darstellungen zur präzisen mathematischen Formulierung der einzelnen Optimierungsprobleme insbesondere auch entsprechende Optimierungsalgorithmen entwickelt, welche einerseits die Berücksichtigung der vielfältigen in der Netzplanung auftretenden Randbedingungen ermöglichen und andererseits ein durch die jeweilige Zielfunktion gegebenes Optimierungsziel bestmöglich zu erreichen versuchen. Die hier vorgeschlagenen Verfahren basieren dabei auf einer neuartigen Kombination genetischer Algorithmen mit einer an die jeweilige Aufgabenstellung anzupassenden deterministischen Heuristik und ermöglichen die Ermittlung qualitativ hochwertiger Lösungen innerhalb akzeptabler Rechenzeiten.

Bei der Bearbeitung NP-vollständiger Optimierungsprobleme stellt sich grundsätzlich die Frage, wie die von Näherungsverfahren gefundenen Lösungen bezüglich ihrer Qualität zu bewerten sind. In der vorliegenden Arbeit erfolgt dabei eine Beurteilung der erzielten Ergebnisse einerseits durch Vergleiche mit zuvor publizierten Ergebnissen anderer Algorithmen und andererseits durch die Berechnung theoretischer Schranken, welche eine Abschätzung der Entfernung zwischen der gefundenen Lösung und dem theoretisch erreichbarem globalen Optimum ermöglichen. Auf die mit dem Branch-and-Bound-Algorithmus und der Lagrange-Relaxation eingesetzten Verfahren zur Berechnung dieser Schranken wird daher ebenfallsnäher eingegangen.

Inhaltsverzeichnis

1. Einleitung ... 1

2. Verfahren zur Lösung diskreter Optimierungsprobleme ... 5
2.1 Grundbegriffe der Optimierungstheorie ... 5
2.2 Lineare Programmierung ... 8
2.2.1 Simplex-Algorithmus ... 8
2.2.2 Schnittverfahren ... 9
2.2.3 Branch-and-Bound Algorithmus ... 10
2.2.4 Berechnung von Schranken ... 12
2.3 Lagrange-Relaxation ... 13
2.4 Simulated Annealing ... 14
2.5 Genetische Algorithmen ... 17

3. Anwendung genetischer Algorithmen zur Netzoptimierung ... 21
3.1 Problem der Kanalzuweisung ... 21
3.2 Kombination mit dem Greedy-Algorithmus ... 23
3.3 Implementierung des genetischen Algorithmus ... 25
3.3.1 Selektion ... 26
3.3.2 Mutation ... 27
3.3.3 Vererbung ... 29
3.4 Begrenzung des Suchraumes ... 30

4. Frequenzplanung in Mobilfunknetzen ... 33
4.1 Grundlagen der Frequenzplanung ... 33
4.1.1 Netzarchitektur ... 34
4.1.2 Vielfachzugriff auf der Luftschnittstelle ... 34
4.1.3 Aufgabe der Frequenzplanung ... 35
4.2 Minimierung des benötigten Spektrums ... 37
4.2.1 Problemformulierung ... 38
4.2.2 Frequenzzuweisung mit genetischen Algorithmen ... 39
4.2.3 Vergleich mit anderen Lösungsansätzen ... 42
4.2.4 Ergebnisse am Beispiel des Philadelphia-Problems ... 44
4.3 Minimierung der Interferenzen ... 50
4.3.1 Problemformulierung ... 51
4.3.2 Frequenzzuweisung mit Simulated-Annealing ... 52
4.3.3 Untersuchung realistischer Beispielprobleme ... 55

5. Planung optischer WDM-Netze ... 61
5.1 Grundlagen der WDM-Technik ... 61
5.1.1 Wellenlängenmultiplex ... 62
5.1.2 Optische Pfade ... 63
5.1.3 Wellenlängenzuweisung und Routing ... 64
5.1.4 Vergleich statischer und dynamischer Verfahren ... 65
5.2 Minimierung der Zahl benötigter Wellenlängen ... 67
5.2.1 Problemformulierung ... 67
5.2.2 Bestimmung der R kürzesten Wege ... 71
5.2.3 Anwendung genetischer Algorithmen ... 72
5.2.4 Ergebnisse ... 74
5.3 Dimensionierung optischer Netze ... 79
5.3.1 Problemformulierung ... 79
5.3.2 Anwendung genetischer Algorithmen ... 82
5.3.3 Ergebnisse ... 84
5.4 Behandlung von Netzausfällen ... 87
5.4.1 Mögliche Redundanzkonzepte ... 88
5.4.2 Heuristik zur Planung von Ersatzpfaden ... 92
5.4.3 Ergebnisse ... 95

6. Optimierung virtueller Pfade in ATM-Netzen ... 99
6.1 Konzept der virtuellen Pfade ... 99
6.1.1 Vor- und Nachteile virtueller Pfade ... 100
6.1.2 Minimierung der Blockierungswahrscheinlichkeit ... 102
6.2 Minimierung der Netzkosten ... 105
6.2.1 Planung aktiver Pfade ... 105
6.2.2 Behandlung von Netzausfällen ... 107
6.3 Anwendung genetischer Algorithmen ... 110
6.4 Schrankenberechnung durch Lagrange-Relaxation ... 112
6.5 Ergebnisse ... 114
6.5.1 Planung redundanter Netze ... 115
6.5.2 Vergleich mit unteren Schranken ... 117

7. Zusammenfassung ... 121

Literaturverzeichnis

Kapitel 1

Einleitung

In einer Zeit, in der die Telekommunikation zu den Branchen mit den höchsten Wachstumsraten insgesamt zu zählen ist, werden laufend neue Kommunikationsnetze entwickelt und geplant. Diese äußerst schnelle Entwicklung hin zu neuen Netzen mit immer höheren Bandbreiten und zusätzlichen Leistungsmerkmalen wird durch eine kontinuierliche Weiterentwicklung der Technologien im Bereich der Nachrichtentechnik ermöglicht. Exemplarisch seien hier insbesondere die Entwicklung der unter den Abkürzungen ,,GSM“ und ,,UMTS“ bekannten Mobilfunknetze der zweiten und dritten Generation genannt. Ferner führt im Zusammenhang mit dem inzwischen weltweit genutzten Internet vor allem die Weiterentwicklung der Glasfasertechnik auch im Bereich der Festnetze zu einem rasanten Fortschritt der Netztechnologien und ihrer Möglichkeiten. Besonders die durch die Wellenlängenmultiplextechnik(WDM) erreichbaren Steigerungen der Übertragungskapazitäten einzelner Glasfasern bieten hier enormes Potenzial für zukünftige breitbandige Anwendungen hoher Übertragungsqualität.

Die Planung und auch der spätere Betrieb solcher neuen Kommunikationsnetze erfordern dabei grundsätzlich geeignete Werkzeuge zur Optimierung der Netze. Insbesondere vor dem Hintergrund eines harten Konkurrenzkampfes auf dem Telekommunikationsmarkt ist schon aus wirtschaftlicher Sicht eine möglichst effiziente Nutzung der Ressourcen im Netz anzustreben. Hierfür benötigt man Algorithmen, welche sämtliche für die Planung eines Netzes wichtigen Randbedingungen berücksichtigen und gleichzeitig dem Betreiber eine Netzkonfiguration beziehungsweise eine Netzdimensionierung mit einer möglichst optimalen Ressourcennutzung liefern. Neben einer solchen wirtschaftlich motivierten Minimierung der Netzkosten kann der Einsatz leistungsfähiger Optimierungsalgorithmen aber auch aufgrund technischer Randbedingungen notwendig werden. Beispielsweise hatte das kontinuierliche Wachstum der Teilnehmerzahlen im Mobilfunk bei einigen Betreibern von GSM-Netzen zur Folge, dass die ihnen zur Verfügung stehende begrenzte Zahl an Frequenzen zu Engpässen bei der Bedienung des Verkehrs geführt hat. In diesem Fall gewinnt die Optimierung der Frequenzplanung und die damit verbundene effizientere Nutzung des Spektrums stark an Bedeutung, da die Zahl der Frequenzkanäle durch die Netzbetreiber in der Regel nicht oder nur in begrenztem Maße erhöht werden kann.

Die somit allgemein anzustrebende bestmögliche Ressourcennutzung in modernen Kommunikationsnetzen erfordert in der Regel die Lösung sehr komplexer Optimierungsprobleme. Konkret lässt sich für zahlreiche Aufgabenstellungen im Bereich der Netzplanung zeigen, dass die zu lösenden diskreten Optimierungsprobleme zur Klasse der NP-vollständigen Probleme gehören, sodass eine optimale Lösung selbst mit den heute zur Verfügung stehenden schnellen Rechnern unmöglich bleibt. Folglich gilt es entsprechende Näherungsverfahren zu entwickeln, deren Ergebnisse dem theoretisch erreichbaren Optimum möglichst nahe kommen. Solche Optimierungsalgorithmen zur Bearbeitung unterschiedlicher Aufgabenstellungen im Bereich der Planung und des Betriebes verschiedener Arten von Netzen werden in dieser Arbeit vorgestellt. Ferner wird, soweit dies möglich ist, eine Bewertung der jeweils erzielten Lösungsqualität vorgenommen, wobei sowohl Vergleiche mit anderen Näherungsverfahren als auch Berechnungen theoretischer Schranken durchgeführt werden. Die Gliederung der resultierenden Arbeit zur Netzoptimierung wird nun im Folgenden anhand einer kurzen Beschreibung der einzelnen Kapitel dargestellt.

In Kapitel 2 werden zunächst einige wichtige Grundbegriffe der Optimierungstheorie erläutert, ehe anschließend unterschiedliche Ansätze zur Lösung solcher Probleme allgemein vorgestellt und beschrieben werden.

Im folgenden Kapitel 3 wird stellvertretend für die im weiteren Verlauf der Arbeit bearbeiteten konkreten Anwendungen der Netzoptimierung ein allgemeines Kanalvergabeproblem formuliert. Am Beispiel dieses bewusst allgemein gehaltenen Beispiels wird dann gezeigt, wie mit dem sogenannten EGA-Ansatz (EGA=Extended Genetic Algorithm) eine leistungsfähige Optimierung durchgeführt werden kann. Dieser EGA-Ansatz bezeichnet dabei eine Kombination aus einem genetischen Algorithmus und einer an die jeweilige Aufgabenstellung anzupassenden deterministischen Heuristik.

Die Anwendung dieses EGA-Ansatzes erfolgt dann erstmals in Kapitel 4 am Beispiel der Frequenzplanung in GSM-Netzen, wobei zwei unterschiedliche Formulierungen dieses Optimierungsproblems untersucht werden. Während die am Ende dieses Kapitels bearbeitete Problemstellung den Anforderungen der Praxis eher gerecht wird, hat die zunächst untersuchte Variante des Problems der Frequenzzuweisung den Vorteil, dass dort ein umfassender Vergleich mit anderen Algorithmen vorgenommen werden kann. Auf diese Weise kann die allgemeine Leistungsfähigkeit des in dieser Arbeit weitgehend verwendeten EGA-Ansatzes deutlich demonstriert werden.

Eine weitere Anwendung des EGA-Ansatzes folgt mit der Optimierung von zukünftig immer mehr an Bedeutung gewinnenden optischen WDM-Netzen in Kapitel 5. Dort werden die für die Planung und das Management solcher Netze wichtigen Fragen nach einer günstigen Wegewahl (Routing), geeigneten Redundanzkonzepten und der optimalen Dimensionierung beantwortet. Zur Beurteilung der erreichten Lösungsqualität wird in diesem Kapitel außerdem mit dem Branch-and-Bound-Algorithmus eine nützliche Methode zur Berechnung theoretischer Schranken eingesetzt.

In Kapitel 6 werden dann am Beispiel sogenannter ATM-Netze (Asynchroner Transfermodus) ebenfalls Probleme der Planung von Festnetzen behandelt. Dabei wird die Konfiguration von virtuellen Pfaden optimiert, wobei letztlich ähnliche Kriterien wie schon zuvor in Kapitel 5 den Gegenstand der Optimierung bilden. Neben einer in der bisherigen Literatur noch relativ wenig beachteten Problemformulierung zur Berücksichtigung eines dem ATM-Netz untergeordneten Transportnetzes wird außerdem mit der Lagrange-Relaxation eine weitere Methode zur Berechnung von Schranken bezüglich der theoretisch erreichbaren Lösungsqualität vorgestellt.

Die Arbeit endet schließlich in Kapitel 7 mit einer zusammenfassenden Betrachtung der vorgestellten Algorithmen. Dabei wird insbesondere auch ein Ausblick auf mögliche zukünftige Anwendungen beziehungsweise Erweiterungen der vorgeschlagenen Verfahren gegeben.

[...]