nicht so „dichte“ Graphen
mit wenigen hundert Knoten in vernünftiger Rechenzeit optimale Ergebnisse
liefert.
4.2. Das DAB-Blockzuweisungsproblem
Im Vergleich zu „normalen“ analogen Sendernetzen eröffnen DAB-Netze zusätzliche
Möglichkeiten zur Einsparung von Frequenzressourcen, die mit den existierenden,
ursprünglich für Analognetze entwickelten Kanalzuweisungsverfahren nicht oder nur
unzureichend ausgenutzt werden können. Wie wir bereits diskutiert haben, ist es bei
DAB möglich, ganze Teilnetze von Sendern aufzubauen, die alle synchron das gleiche
DAB-Ensemble – zusammengesetzt aus mehreren Rundfunkprogrammen und weiteren
Datendiensten – auf derselben Frequenz senden: Man spricht von sogenannten
Gleichwellennetzen. Im Gegensatz zur Situation beim UKW-Rundfunk stören sich die
Sender eines solchen Gleichwellennetzes nicht gegenseitig. Im Gegenteil, die Signalanteile
der verschiedenen Sender addieren sich im DAB-Empfänger zu einem Gesamtsignal –
wenn sie alle innerhalb einer gewissen Zeitspanne, dem sogenannten Schutzintervall,
beim Empfänger eintreffen.
Will man mehrere verschiedene DAB-Ensembles übertragen, so benötigt man dafür
natürlich auch mehrere DAB-Frequenzblöcke. Die im vorherigen Abschnitt diskutierten
Färbungsverfahren für das Kanalzuweisungsproblem lassen sich im Wesentlichen
unverändert auf die Zuweisung von solchen DAB-Blöcken übertragen. Will
man allerdings die bei DAB vorhandenen Möglichkeiten zur Einsparung von
Sendefrequenzen durch geschickte Bildung von Gleichwellennetzen ausnutzen, so
muss man auch die Planung der DAB-Ensembles in die Problemmodellierung
einbeziehen. Zwar lassen sich dadurch bessere Planungsergebnisse im Hinblick auf
die Frequenzökonomie erreichen, allerdings wird auch die Planungsaufgabe
komplizierter. Den im folgenden dargelegten Ansatz, in dem die Planung des
DAB-Netzes als zweistufiges Optimierungsproblem aufgefasst wird, haben wir in
Zusammenarbeit mit einer Arbeitsgruppe des damaligen SWF (jetzt SWR)
entwickelt, die sich intensiv mit der Modellierung von DAB-Netzen befasst hat
[Quellmalz/Knälmann/Müller 1995]. Dabei ergibt sich die zunächst paradox anmutende,
aber mathematisch beweisbare Tatsache, dass sich in einem DAB-Netz bei geschickter
Zusammenfassung der zu übertragenden Dienste durch Überversorgung Frequenzen
einsparen lassen.
Wir betrachten dazu ein einfaches, hypothetisches Beispiel. Abb. 3 zeigt fünf Gebiete
(I-V), die mit verschiedenen „Diensten“, hier mit A-H bezeichnet, versorgt werden sollen,
und zwar im Gebiet 1 die Dienste A, B und D, im Gebiet II die Dienste A, B und E usw.
In der Praxis kann es sich bei einem solchen „Dienst“ sowohl um ein Rundfunkprogramm
als auch um einen Datendienst handeln. Jeder Dienst verbraucht eine gewisse
„Bandbreite“ innerhalb eines DAB-Blocks, die wir in willkürlichen Einheiten angegeben
haben. Für die Verteilung der Dienste auf die Blöcke kommt es zunächst einmal
nur auf das Verhältnis der Dienste-Bandbreiten zur Blockgröße an, die wir
hier mit 9 angesetzt haben. Die Lösung unserer Planungsaufgabe besteht nun
zum einen aus der Verteilung der zu übertragenden Dienste auf verschiedene
Blöcke, wobei eine solche „Blockzuweisung“ bestimmte Bedingungen erfüllen
muss: