Moderne analytische und diskret-mathematische Methoden, angewendet auf Probleme der Kanalvergabe in Mobilfunknetzen

Inhaltsangabe:Einleitung: Die Anzahl der Mobiltelefone ist in den letzten Jahren explosionsartig angestiegen. Immer mehr Menschen nutzen die mobile Kommunikation. Während 1992 950.000 Menschen in Deutschland mobil telefonierten, so waren es Ende 1999 bereits mehr als 23 Millionen [10]. Die Entwicklung in anderen Mobilfunknetzen ist ähnlich. Deshalb wird die optimale Ausnutzung der zur Verfügung stehenden Funkkanäle immer wichtiger. Ein besonders kritischer Punkt ist hier die begrenzte Anzahl der Kanäle. Um Mobilkommunikation möglich zu machen werden Gebiete in Zellen eingeteilt. In Kapitel 2 wird unter anderem noch näher auf diese Zellen-Konzeption eingegangen. Der Radius der Funkzellen schwankt zwischen 250m und 35km. Er richtet sich auch nach dem zu erwartenden Gesprächsaufkommen. Im Zentrum jeder Zelle befindet sich eine Sende- und Empfangsstation, die auch Basisstationen genannt wird. Die mobilen Einrichtungen kommunizieren über diese Basisstationen. Zur Datenübertragung zwischen Mobiltelefon und Basisstation muss ein Funkkanal bereitgestellt werden. Derselbe Kanal, oder Kanäle mit ähnlichen Frequenzen, dürfen dann nicht mehr vergeben werden, da die gesendeten Funksignale sich überlagern oder verfälschen können. Diese Störungen werden als Interferenzen bezeichnet. Es müssen deshalb gewisse Abstände zwischen Kanälen, die im selben Gebiet verwendet werden, eingehalten werden. Dadurch soll es zu keinen Beeinträchtigungen der Gespräche kommen. Die Netzbetreiber sind nun daran interessiert möglichst viele Verbindungen erfolgreich durchzuführen. Dadurch kommt es zu folgendem Problem: Wie sollen die Kanäle sinnvoll an Mobilstationen, die ein Gespräch führen wollen, vergeben werden? Dabei sind die Mindestabstände zwischen den Frequenzen zu beachten. Es sollen natürlich auch möglichst viele Verbindungen aufgebaut werden. Es gibt auch schon verschiedene Lösungsansätze für dieses Problem. In der folgenden Arbeit werden wir uns ausschließlich mit einem dieser Lösungsansätze beschäftigen. In diesem Ansatz wird jeder Basisstation eine gewisse Anzahl von Kanälen unter Einhaltung von gewissen Mindestabständen zugeordnet. Soll im Gebiet dieser Basisstation eine Verbindung aufgebaut werden, so geschieht dies nur, wenn ein freier Kanal verfügbar ist. Ansonsten wird die Anforderung abgelehnt. Eine solche Lösung wird als Fixed-Channel-Assignment (FCA) bezeichnet. Die vorliegende Staatsexamensarbeit beschäftigt sich also mit dem Thema der Kanalvergabe in [...]