Mobilfunknetze

Optimierung nach dem Vorbild der biologischen Evolution

Im Arbeitsbereich Digitale Kommunikationssysteme werden Probleme untersucht, die im Zusammenhang mit der Technik, der Planung und dem Management moderner Nachrichtennetze stehen. So ist es nicht überraschend, daß Themen aus dem Bereich der digitalen Mobilfunknetze einen Forschungsschwerpunkt dieses Arbeitsbereiches darstellen. Wesentlich mehr Verwunderung dürfte da schon die Frage auslösen, was denn die biologische Evolution mit der sonst eher technisch orientierten Forschung dieses Arbeitsbereiches zu tun haben könnte. Bevor diese Frage nun im Laufe dieses Artikels beantwortet werden kann, wird im folgenden zunächst das diesem Bericht zugrundeliegende technische Problem aus dem Bereich des Mobilfunks näher erläutert.

Mobilfunk
Die heutigen digitalen Mobilfunknetze sind sogenannte zellulare Netze. Das bedeutet, daß die gesamte zu versorgende Region, im Falle der D- und E-Netze also die Gesamtfläche Deutschlands, aufgeteilt wird in zahlreiche kleinere Gebiete, die sogenannten Funkzellen. In jeder Zelle wird von dem jeweiligen Netzbetreiber eine Basisstation installiert (vgl. Abbildung 1). über die Antenne dieser Basisstation gelangen die Signale von den in der jeweiligen Zelle befindlichen Mobilfunkteilnehmern dann in das Festnetz und werden dort entsprechend weitergeleitet. Die Funkverbindung zwischen den Handys der Mobilfunkteilnehmer und der jeweils zuständigen Basisstation erfordert dabei die Zuweisung sogenannter Trägerfrequenzen, auf denen das Funksignal übertragen werden kann. Genau diese Zuweisung von Trägerfrequenzen stellt jedoch in zellularen Mobilfunknetzen ein zunehmendes Problem dar, und dies soll im folgenden näher erklärt werden.

Im Rahmen der Planung von Mobilfunknetzen ist es also erforderlich, jeder Basisstation abhängig vom erwarteten Verkehrsaufkommen in der dazugehörigen Zelle eine bestimmte Zahl an Frequenzen zuzuweisen. Bei der Zuweisung dieser Frequenzen müssen jedoch sogenannte Interferenzbedingungen eingehalten werden, um sicherzustellen, daß sich verschiedene Basisstationen nicht stören. Solche unerwünschten Störungen durch Interferenzen treten auf, wenn dieselbe Frequenz innerhalb eines zu kurzen räumlichen Abstandes erneut einer weiteren Basisstation zugewiesen wird. Ebenso wie bei der Frequenzplanung im Bereich des UKW-Rundfunks, ermöglicht die stets auftretende Dämpfung der Funkwellen jedoch eine Wiederverwendung derselben Frequenz in einer hinreichend großen Entfernung. Diese für zellulare Netze typische räumliche Wiederverwendbarkeit von Frequenzen ist für den Mobilfunk außerordentlich wichtig, da die Zahl der für den Mobilfunk zur Verfügung stehenden Frequenzen stark begrenzt ist. Für einige Millionen von Teilnehmern stehen im D-Netz gerade mal 124 Frequenzkanäle zur Verfügung.

Dieses Problem der Frequenzzuweisung läßt sich mathematisch als diskretes Optimierungsproblem deuten. Das Ziel dieser Optimierung besteht darin, unter Verwendung der maximal zur Verfügung stehenden Frequenzen jeder Basisstation die geforderte Zahl an Frequenzen zuzuweisen und gleichzeitig die Störungen durch Interferenzen zu minimieren. Die Mathematiker bezeichnen ein solch komplexes Zuweisungsproblem als NP-vollständig. Aus praktischer Sicht bedeutet dies, daß es unmöglich ist, in vertretbarer Zeit für Mobilfunknetze realistischer Größenordnung die optimale Frequenzzuweisung zu berechnen. Selbst die Entwicklung immer schnellerer Computer bringt hier keine Lösung, da die Zahl zu untersuchender Frequenzzuweisungen explosionsartig mit der Zahl der Basisstationen im Mobilfunknetz ansteigt.

Insofern ist es also generell unmöglich, alle Frequenzzuweisungen auf ihre Optimalität hin zu untersuchen. Andererseits sind Frequenzzuweisungen hoher Qualität für die Mobilfunkbetreiber von immer größerer Bedeutung, da bekanntlich die Zahl der Mobilfunkteilnehmer weiterhin sehr stark ansteigt. Dem Engpaß einer begrenzten Anzahl von Funkfrequenzen läßt sich nur entgegenkommen, indem man die Frequenzen früher wiederholt, d.h. die Zellen kleiner macht, wodurch natürlich die Anzahl der Zellen und damit die Komplexität des Zuweisungsproblems weiter ansteigt. Die Mobilfunkbetreiber sind daher an Verfahren interessiert, die in akzeptabler Rechenzeit Frequenzzuweisungen hoher Qualität mit möglichst wenig Störungen durch Interferenzen erzeugen können.

Diskrete Optimierung
Zur Lösung sehr großer diskreter Optimierungsprobleme wie dem zuvor beschriebenen Problem der Frequenzzuweisung kommen also nur Näherungsmethoden in Frage, um qualitativ hochwertige Lösungen in akzeptabler Zeit zu bestimmen. Prinzipiell lassen sich die gängigen Näherungsverfahren in zwei unterschiedliche Kategorien einteilen.

Zum einen werden heuristische Algorithmen eingesetzt. Diese Heuristiken beruhen auf einfachen, plausibel erscheinenden Regeln, nach denen mögliche Lösungen konstruiert werden. Für das hier vorgestellte Problem der Frequenzzuweisung in Mobilfunknetzen findet man somit in der entsprechenden Fachliteratur auch eine Vielzahl an vorgeschlagenen Heuristiken, um die Frequenzen möglichst optimal auf die Basisstationen zu verteilen. Anhand diverser Beispiele läßt sich jedoch zeigen, daß diese heuristischen Verfahren in der Regel zu Ergebnissen führen, die von der theoretisch möglichen optimalen Lösung weit entfernt liegen. Dies ist auch nicht verwunderlich, da es allgemein geradezu unmöglich ist, für kombinatorische Probleme hoher Komplexität optimale Handlungsstrategien aufzustellen. Vergleichbar utopisch wäre die Forderung nach einigen wenigen Handlungsanweisungen, die für jede denkbare Spielsituation beim Schach direkt auf den wirklich optimalen Zug führen.

Eine Alternative zu den angesprochenen Heuristiken besteht in der Anwendung stochastischer Optimierungsverfahren. Dabei werden nacheinander zufällig ausgewählte  Lösungen auf ihre Qualität hinuntersucht. Da der eigentlich zu untersuchende Lösungsraum im Falle der Frequenzzuweisung jedoch gigantisch groß ist, kann im Rahmen der zur Verfügung stehenden Zeit nur ein sehr kleiner Bruchteil der Lösungen auf die gewünschte Optimalität hin geprüft werden. Somit steht man also vor der zunächst nahezu aussichtslos erscheinenden Aufgabe, einige wenige Stichproben aus der riesigen Zahl möglicher Lösungen so auszuwählen, daß die Chance dabei eine optimale Lösung zu finden, relativ groß wird.

Genetische Algorithmen
Es gibt zahlreiche Beispiele dafür, daß sich Lösungen technischer Probleme finden lassen, indem man Konzepte zum Vorbild nimmt, die die Natur im Laufe der Evolution für verwandte Probleme gefunden hat. Man denke beispielsweise an die Strukturierung der Oberflächen von Flugzeugen zur Herabsetzung der Wirbelbildung, wobei die Haut von Delphinen als Vorbild dient.

Das Prinzip, die Natur nachzuahmen, wird allerdings in der Praxis häufig dadurch beschränkt, daß es sich bei der von der Evolution „erfundenen" Lösung eben um die Lösung eines verwandten Problems handeln muß und sich der Verwandtschaftsgrad von Problemen nur schwer qualifizieren läßt. So ist die Idee, ein Großflugzeug vogelähnlich mit den Flügeln schlagen zu lassen, trotz des natürlichen Vorbildes keine besonders glückliche. Was aber in jedem Fall nachahmenswert sein könnte, sind die Mechanismen, mit denen die Natur optimale Lösungen produziert.

Die biologische Evolution stellt nämlich eine äußerst flexible Optimierungsstrategie dar, um die Eigenschaften von Pflanzen, Tieren und Menschen an die Erfordernisse der Umgebung dynamisch anzupassen und somit deren überlebensfähigkeit zu gewährleisten. Die wesentlichen Mechanismen der biologischen Evolution werden allgemein in der natürlichen Selektion, der Mutation und schließlich der sexuellen Reproduktion gesehen. Die Selektion garantiert, daß nur Lebewesen (Individuen) hoher Qualität überlebensfähig sind und somit für die Fortpflanzung, d.h. die Produktion von Nachkommen, in Frage kommen. Die Bildung von neuen Individuen nach den Regeln der Vererbung bewirkt eine Durchmischung und somit neue Kombination der Gene zweier Elternteile. Durch die Paarung zweier Individuen hoher Qualität besteht somit eine gute Chance, Nachkommen noch besserer Qualität zu erzeugen. Diese Methode der „gezielten Vererbung" wird zum Beispiel bei der Zucht von Rennpferden seit langer Zeit erfolgreich angewendet. Die Mutation schließlich bewirkt einzelne zufällige Veränderungen an den Genen und verhindert somit, daß sich eine Population identischer Individuen entwickelt. Eine solche einförmige Population wäre nämlich zu keiner weiteren Evolution mehr fähig und könnte sich somit also nicht weiter in ihrer Qualität verbessern.  Es bleibt nun also die Frage zu beantworten, wie diese in der Natur so hervorragend funktionierenden Prinzipien der biologischen Evolution für die Suche nach einer optimalen Frequenzzuweisung genutzt werden können. Zu diesem Zweck ist es nun generell nicht notwendig, jede Einzelheit der Evolution auf Molekularebene genau zu verstehen und entsprechend für das Ziel der Frequenzzuweisung zu kopieren. Vielmehr geht es darum, die Optimierungsmethodik der Evolution mit den Einzelschritten Selektion, Mutation und Vererbung sinngemäß auf das Frequenzzuweisungsproblem anzuwenden. Wie das geschehen kann, wird nun erläutert: In Abbildung 2 ist ein Standardbeispiel gegeben, an dem sich schon viele Forscher versucht haben. Die Zahlen in den 21 Funkzellen geben den (aus einem Verkehrsaufkommen berechneten) Frequenzbedarf an; in diesem Fall handelt es sich um insgesamt 470 Verbindungen. Als Interferenzbedingung wird u.a. gefordert, daß zwei Zellen, die dieselbe Frequenz benutzen, durch mindestens zwei andere Zellen getrennt sein müssen. Eine Lösung für die Frequenzzuweisung besteht letztlich in einem Vektor mit 470 Komponenten, die in 21 Segmenten angeordnet sind. Jede Komponente gibt eine Frequenz an, die dem entsprechenden Segment (der Funkzelle) zugewiesen wird. Eine optimale Lösung wäre ein Vektor mit einer möglichst geringen Anzahl unterschiedlicher Einträge (Frequenzen). Der Brückenschlag zur Biologie erfolgt nun dadurch, daß man diese Art Vektoren als Chromosomen interpretiert. Man beginnt daher mit einer Vielzahl („Population") nicht-optimaler Lösungen und unterwirft diese den Prozessen von Selektion, Mutation und Vererbung über viele Generationen hinweg. Dieses Vorgehen wird mit dem Iterationsverfahren skizziert. Dabei wird die betrachtete Population von Lösungsvektoren konstant gehalten, z.B. =50. Während jedes Generationsdurchlaufes werden die (z.B.) 40 besten Lösungen selektiert und in die neue Population übernommen. Die 10 ausgesonderten Lösungen werden ersetzt durch  neue Lösungen, die aus der Menge der besseren durch Mutations- und Vererbungsprozesse erzeugt werden. Ein Mutationsprozeß wäre z.B. eine Permutation der Komponenten eines Vektors. Bei einem Vererbungsprozeß, bei dem „die Kinder Gene von beiden Elternteilen erben", wird im Laufe mehrerer Generationen durch diese Vorgehensweise eine kontinuierliche Verbesserung der Lösungsqualität erreicht, die sich beispielsweise durch eine Abnahme der Verbindungen ausdrückt, für die keine Frequenzzuweisung gefunden werden konnte. Für diese Gütemaßzahl (N.B.: die optimale Lösung liefert den Wert 0) ist in Abbildung 3 der Populationsmittelwert über der Anzahl der Generationen aufgetragen. Man erkennt, daß die besten Ergebnisse nur zu erzielen sind, wenn sowohl Vererbung als auch Mutation als Bestandteile des genetischen Algorithmus eingesetzt werden. Dieses Ergebnis entspricht dabei wiederum den Beobachtungen in der Natur, wo auch erst das Zusammenspiel beider Mechanismen eine leistungsfähige Evolution ermöglicht.

Für das in Bild 2 vorgestellte Problem haben Mathematiker eine untere Schranke für die Anzahl mindestens benötigter Frequenzen, nämlich 253, gefunden, wobei bis vor kurzem unbekannt war, ob diese Schranke erreichbar ist. Die bislang eingesetzten Verfahren benötigten zwischen 259 und 270 Frequenzen. Den Autoren dieses Berichts ist es nun gelungen, mit Hilfe genetischer Algorithmen eine Lösung mit 253 Frequenzen vorzustellen [1]. Damit wurde erstmalig die optimale Lösung dieses „Benchmark"-Problems gefunden und zugleich gezeigt, daß die Autoren über besonders effiziente Algorithmen für Planungsaufgaben in Mobilfunknetzen verfügen. Der eigentliche Pfiff des an der TUHH entwickelten Algorithmus besteht, wie in diesem Aufsatz leider nicht detailliert werden konnte, darin, daß trotz der in den Operationen von Mutation und Vererbung grundsätzlich innewohnenden Zufälligkeit keine zufälligen Verletzungen der Interferenzbedingungen erzeugt werden, d.h. die Lösungssuche wird immer auf den zulässigen Bereich des Lösungsraumes beschränkt.

Abschließend muß allerdings leider auch auf eine Unzulänglichkeit genetischer Algorithmen hingewiesen werden. Im Gegensatz zu exakten Optimierungsverfahren, wie sie für kleinere Probleme eingesetzt werden können, läßt sich für die Anwendung genetischer Algorithmen keine theoretische Garantie dafür geben, daß die optimale Lösung auch in jedem Fall gefunden wird. Diesem theoretischen Nachteil steht jedoch der Vorteil einer großen Effizienz der Lösungssuche gegenüber, die den erfolgversprechenden Einsatz für große Optimierungsprobleme überhaupt erst ermöglicht. Da die Methodik genetischer Algorithmen nicht problemgebunden ist, ist es nicht verwunderlich, daß auch Optimierungsprobleme in Festnetzen auf diese Weise gelöst wurden [2].

Literatur
[1] D. Beckmann und U. Killat, „A New Strategy for the Application of Genetic Algorithms to the Channel-Assignment Problem", wird veröffentlicht in „IEEE Transactions on Vehicular Technology"
[2] D. Beckmann und U. Killat, „Minimizing the Number of Fibres in Optical Networks Using Genetic Algorithms", „Int. Symposium on Broadband European Networks", Zürich, Mai 1998

Dipl.-Ing. Dirk Beckmann
Prof. Dr. Ulrich Killat
Arbeitsbereich Digitale Kommunikationssysteme