BOSCH-PMP
Frequenzplanung in Punkt- zu Mehrpunkt-Funksystemen
Beschreibung
Ein Punkt- zu Mehrpunkt-Funksystem dient der Anbindung von Kundenterminals an Basisstationen mittels Richtfunk. Im Unterschied zum Mobilfunk verfügt jeder Kunde über eine fest installierte Antenne und ist einer bestimmten Basisstation zugeordnet. Unter gewissen Bedingungen stören sich Funkverbindungen, falls diese die gleichen Frequenzen benutzen. Zur Gewährung einer interferenzfreien Datenübertragung im System sind zwei Planungsprobleme zu lösen, die Bandbreiten- und die Broadcast-Kanal-Planung. Die Bandbreitenplanung umfasst das Problem, den einzelnen Richtfunkstrecken Frequenzintervalle aus einem vorgegebenen Frequenzspektrum zuzuweisen. Ziel ist die Erstellung von Frequenzplänen mit geringem Bandbreitenbedarf unter Berücksichtigung einiger technischer Nebenbedingungen und der verschiedenen Kommunikationsbedarfe der Kunden. Die Bandbreitenplanung kann modelliert werden als Intervallfärbungsproblem auf gewichteten Graphen (mit allen Kunden als Knoten und deren Interferenzbeziehungen als Kanten. Diese Art von Problemen ist NP-schwer und nicht mit konstanter Gütegarantie lösbar. Daher stand die Entwicklung verschiedener schneller Heuristiken im Mittelpunkt. Während der Projektlaufzeit wurden zunächst erste primale Startheuristiken und ein duales Verfahren implementiert und getestet. Darauf aufbauend wurden weitere primale Start- und Verbesserungsheuristiken entworfen und implementiert. Mithilfe dieser Algorithmen konnten kleine und mittlere Probleme optimal gelöst werden. Die maximale Abweichung des Bandbreitenbedarfs der primalen Lösung von dem der dualen Lösung betrug höchstens 15 % (für die von BOSCH-Telecom zur Verfügung gestellten Problembeispiele). Die Broadcast-Kanal-Planung umfasst die Vergabe eines gesonderten Frequenzkanals an jeden Sektor, der dem Protokollverkehr zwischen der Basisstation und allen zugeordneten Kunden dient. Ziel ist es, jedem Sektor im System einen Broadcast-Kanal unter Beachtung aller Interferenzbeziehungen zuzuweisen und dabei insgesamt eine minimale Anzahl von Kanälen zu benutzen. Dieses Problem entspricht einem Färbungsproblem auf dem Graphen mit allen Sektoren als Knoten, der die Interferenzbeziehungen im System geeignet wiedergibt. Färbungsprobleme sind ebenfalls NP-schwer, die geringeren Problemgrößen gestatteten hier aber den Einsatz eines exakten Verfahrens mit verschiedenen Zeitschranken. Für alle von BOSCH-Telecom zur Verfügung gestellten Problembeispiele konnte ein optimaler Broadcast-Kanal-Plan erstellt werden.
Ansprechpartner
- Annegret Wagler
Mitarbeiter
- Andreas Bley
- Andreas Eisenblätter
- Annegret Wagler
- Roland Wessäly
- Martin Grötschel
Kooperationspartner
- BOSCH Telecom, Ansprechpartner: Dr. Tillmann Eckstein (e-mail: Tillmann.Eckstein@pcm.bosch.de)
Förderung
Projektdauer
07/1997 - 03/1999