zurück zum CAFM-Ratgeber

Rechnerunterstützte Planung des Layouts von Kabelnetzen in Bauwerken¹⁾

Alfred Iwainsky, Silvia Nitz
IIEF GmbH und GFaI
Albert-Einstein-Str. 16, D-12489 Berlin
email: a.iwainsky@iief.de

Kurzfassung

Kabelnetze für Kommunikation und Energieversorgung sind wesentliche Bestandteile der Infrastruktur von Gebäuden, Gebäudekomplexen, Industrieanlagen und anderen Bauwerken. Zum Entwurf der Netzwerke gehören u. a. die Planung

• der räumlichen Anordnung von Trassen sowie ihrer Ausstattung mit Kabelführungseinrichtungen,
• der Lokalisierung bestimmter Netzknoten wie Verteiler mit den speziell für sie reservierten Räumen sowie
• des Layouts der eigentlichen Kabelnetze im Trassensystem.

Der Beitrag beginnt zunächst mit einer Erläuterung der oft übersehenen Bedeutung einer adäquaten computerbasierten Modellierung von Trassen für die Unterstützung von Entwurf und Verwaltung von Kabelnetzwerken. Dabei wird insbesondere auf das Konzept der potentiellen Trassen und auf hierarchisch strukturierte Trassen eingegangen.

Es folgt eine Darstellung der in verschiedenen Bereichen üblichen Netzwerkstrukturen. Daraus leiten sich dann unterschiedliche Entwurfsprobleme ab, die idealisiert auf eine Reihe klassischer Optimierungsprobleme bzw. Kombinationen solcher Probleme führen. Dabei handelt es sich um das

• Problem des kürzesten Weges (shortest path),
• Steiner-Baum-Problem (Steiner tree problem),
• Problem des Handelsreisenden (traveling salesman),
• Traveling salesman problem with no return,
• Problem des chinesischen Briefträgers (Chinese postman problem).

Im Vordergrund des Beitrages stehen die praktischen Probleme des Netzwerklayouts und die Klassifikation dieser Probleme aus mathematischer Sicht, insbesondere auch im Hinblick auf die algorithmische Komplexität. Dabei wird gleichzeitig eine kritische Analyse der Problemidealisierung vorgenommen, die sich ergibt, wenn man die praktischen Aufgaben versucht, auf klassische Optimierungsprobleme abzubilden. Mit anderen Worten: Der Beitrag artikuliert aus der Anwendersicht heraus Forschungsbedarf auf mathematischer Seite.

1) Teile der Arbeit entstanden im Rahmen der Projekte ECOFAM bzw. AUTEKA, die innerhalb der marktvorbereitenden Industrieforschung vom BMWi unter den Kennzeichen 544/96 bzw. 461/97 gefördert wurden.

1 Einführung

Kabelnetze für Kommunikation und Energieversorgung sind wesentliche Bestandteile der Infrastruktur von Gebäuden, Gebäudekomplexen und Industrieanlagen. Sie können sehr umfangreich werden. Dies betrifft einerseits die Gesamtlänge der Kabel (Auf dem Gelände der BASF Schwarzheide GmbH z. B. sind 1260 km Erdkabel verlegt!) und andererseits die Konzentration vieler Kabel in bestimmten Bereichen (in denen oft zusätzlich Rohrleitungsnetze vorkommen). Solche Bereiche können die Umgebung von Schaltfeldern (Schränken) sein, von den es z. B. im Velodrom Berlin allein 140 (!) gibt. Die Bilder 1 und 2 vermitteln einen Eindruck davon.

Die räumliche Anordnung (das Layout) von Kabelnetzen ist ein kompliziertes praktisches Problem, und zwar nicht allein aufgrund des gerade angedeuteten Umfangs dieser Netze, sondern teilweise auch wegen der algorithmischen Komplexität bestimmter mathematischer Problemabstraktionen (siehe Abschnitte 3 und 4). Der Layout-Entwurf von Kabelnetzen fordert dementsprechend eine Rechnerunterstützung geradezu heraus. Falls Kabel nicht irgendwie auf der "grünen Wiese" verlegt werden sollen (und wann ist dies schon der Fall?), müssen aber zunächst viel- fältige Restriktionen bezüglich der Möglichkeiten der Kabelverlegung beschrieben werden, die u. a. durch die Geometrie von Bauwerken bzw. die Struktur von Gebäudekomplexen bestimmt werden. Hierfür bietet es sich an, einen Graphen, der die Layout-Möglichkeiten für Kabelnetze beschreibt, in das jeweilige Gebäude-, Bauwerk- bzw. Geländemodell einzubetten (siehe Abschnitt 2). Wichtige Voraussetzungen dafür, den entsprechenden Modellierungsaufwand gering zu halten, sind heute häufig gegeben:

• Gebäude bzw. Bauwerke sind oft bereits mit Hilfe eines CAD-Systems modelliert worden. Die entsprechenden Modelle bieten eine gute Grundlage für die Beschreibung von Möglichkeiten zur Verlegung von Kabeln, insbesondere zur Integration von Modellen für Kabeltrassen.
• Es gibt Software-Systeme, die auf CAD-Systeme und entsprechende Gebäudemodelle aufsetzen sowie die Modellierung von Trassen und die virtuelle Verlegung von Kabeln in diesen unterstützen. Das System InfoCABLE® ist ein Beispiel dafür. Es benutzt MicroStation als CAD-Basis und dient der Planung, Verwaltung und Dokumentation von Kommunikationsnetzen.

Der Nutzen einer computerbasierten Planung des Layouts von Kabelnetzen erhöht sich weiterhin dadurch, daß zunehmend seitens der Praxis Bedarf an den in der Planung entstehenden rechnerinternen Modellen der Netzwerke und ihrer Umgebung auch für die Betriebsphase angemeldet wird. Hier zeichnet sich der Königsweg des Computer-Aided Network Facilities Management (CANFM) ab: Mit einer einheitlichen bzw. zumindest kompatiblen Technik werden Netze entworfen und die dabei entstehenden Netzwerkmodelle später für

• diverse Auswertungen,
• die Störungseingrenzung und zur Unterstützung von Störungsbeseitigungen,
• das Re-engineering von Netzen z. B. im Rahmen von Umzügen,
• Umzugsplanung und -management,
• die Erstellung von Dokumentationen in verschiedenen Formen

genutzt.

2 Layout-Räume von Kabelnetzen

Unter Layout-Räumen versteht man diejenigen räumlichen Bereiche, in denen Objekte (Facilities) prinzipiell angeordnet werden können. So kann z. B. Büromobiliar in bestimmten Räumen eines Gebäudes aufgestellt werden, Maschinen lassen sich in einer Werkshalle positionieren und Schaltkreise auf einer Leiterkarte unterbringen. Die Festlegung von Layout-Räumen stellt also die Spezifikation erster grundsätzlicher Restriktionen von Layout-Problemen dar. Sie betrifft räumlich-geometrische Einschränkungen. Layout-Probleme sind meist sehr komplex. Zur Spezifikation von Layout-Räumen treten meistens andere Nebenbedingungen hinzu, die u. a. funktionale, ästhetische, ergonomische und wiederum geometrische Aspekte der anzuordnenden Facilities betreffen.

Auch der Entwurf der räumlichen Anordnung (das Layout) von Kabelnetzen ist i. allg. ein kompliziertes Problem, was allerdings in der Praxis oft übersehen wird, weil man es mehr oder weniger willkürlich in einfache Teilprobleme (Routing eines Kabels von einem Punkt zu einem anderen) zerlegt. Wie jeder weiß, dürfen Kabel i. allg. nicht beliebig durch den dreidimensionalen Raum verlegt werden. Kabelnetze werden meist in einer Umgebung ausgelegt, die bereits eine ausgeprägte Struktur aufweist. Beispiele dafür sind Gelände mit einer inneren Struktur, die u. a. durch existierende Straßen und Gebäude gegeben ist. Auch innerhalb von Gebäuden ist eine starke räumliche Gliederung vorhanden, die bei der Auslegung von Kabelnetzen berücksichtigt werden muß.

Es hat vor längerer Zeit Versuche gegeben, Layout-Räume für Kabelnetze indirekt durch Festlegung von räumlichen Gebilden zu spezifizieren, die für die Verlegung von Kabeln verboten sind (siehe z. B. /Ben81a und b/). Man sprach von verbotenen Zonen. Dies implizierte, daß in allen anderen, nicht verbotenen Raumbereichen Kabel verlegt werden dürfen. Ein solches Layout-Modell eröffnet zwar der Optimierung der räumlichen Auslegung von Kabelnetzen den größten, gerade noch zulässigen Freiraum, hat sich in der Praxis aber dennoch aus folgenden Gründen nicht durchsetzen können:

• Die Spezifikation und computerbasierte Modellierung der verbotenen Zonen als Voraussetzung für Entwurf bzw. Optimierung ist i. allg. viel zu aufwendig.
• Das Modell berücksichtigt nicht die Tatsache, daß im Entwurf umfangreicherer Kabelnetzwerke die einzelnen Kabelverbindungen nicht unabhängig voneinander behandelt werden sollten (z. B. ist das parallele Führen vieler Kabel i. allg. kostengünstiger als das räumlich getrennte Verlegen einzelner Kabel). Bestehende Wechselwirkungen zwischen einzelnen Verbindungen (attraktive oder auch repulsive), die im Entwurf berücksichtigt werden sollten, sind also in diesem Modell zunächst einmal nicht erfaßt.
• Für die Lösung der eigentlichen Optimierungsprobleme lag und liegt kein breit gefächertes Arsenal mathematischer Hilfsmittel vor.

Eine grundsätzlich andere Vorgehensweise der Modellierung von Layout-Räumen für Kabelnetze, die sich inzwischen durchgesetzt hat, läßt sich folgendermaßen charakterisieren (siehe auch /Iwa86, ICTV86, IDRS86/):

• Nicht die für Kabelverlegungen verbotenen Zonen, sondern gerade die dafür vorgesehenen Raumbereiche, nämlich die bereits vorhandenen oder geplanten Kabeltrassen, werden explizit modelliert (Bild 3 zeigt ein besonders interessantes Beispiel für eine Kreuzung zweier Kabeltrassen).
• Um zusätzliche "Freiheitsgrade" für das Layout der Kabelnetze zu schaffen, werden weitere potentielle Trassen in das Modell einbezogen. Erst im Zuge des Entwurfs des Kabelnetz-Layouts zeigt sich, ob diese Trassen wirklich benötigt werden und deshalb auch in der Realität eingerichtet werden sollten (daher der Begriff potentielle Trassen).
• Auf diese Weise entsteht ein diskretes Modell für die Layout-Optimierung, ein Netzwerk (Graph), das in den dreidimensionalen Raum mit seiner konkreten inneren Struktur (z. B. durch Gebäudesubstanz geprägt) eingebettet ist. Bild 4 illustriert dies anhand eines einfachen Beispiels. Tafel 1 zeigt, wofür die Elemente des Trassengraphen stehen können und welche Charakteristika ihnen dementsprechend zuzuordnen sind.
• Für den Entwurf (die Optimierung) des Layouts von Kabelnetzen steht damit ein großes Arsenal mathematischer Algorithmen innerhalb der Graphentheorie zur Verfügung.

Bei dieser Art der Modellierung von Layout-Räumen für Kabelnetze muß man dafür sorgen, daß alle Komponenten, die an ein Kabelnetzwerk angeschlossen werden sollen, auch über Kabel in Trassen erreichbar sind. Oder anders ausgedrückt: Das Trassennetz muß bis an diese Komponenten herangeführt werden. Dabei können im Modell Abschnitte von "Trassen" entstehen, die man im gewöhnlichen Sprachgebrauch kaum als solche bezeichnen würde (z. B. adäquate Verläufe von Konfektionskabeln).

Zunächst einmal nicht ganz konform mit der graphentheoretischen Modellierung von Layout-Räumen für Kabel sind auch solche zur Kabelführung vorgesehenen räumlichen Bereiche, die nicht linienartig sind. Die wichtigsten und bekanntesten Beispiele dafür sind Doppelböden und die Räume direkt über abgehängten Decken. Die Existenz solcher Bereiche für die Kabelführung war mit ein Anstoß für die Entwicklung eines neuartigen Modells für Räume zum Layout von Kabeln oder auch Rohrleitungen. Bei dieser Modellierung werden Graphenknoten, eindimensionale Elemente (Kanten), zweidimensionale Bereiche (Flächen) und Volumina miteinander kombiniert /BGT96/.

Eine andere praktikable Möglichkeit, z. B. Doppelböden in die graphentheoretische Modellierung von Layout-Räumen für Kabel einzubeziehen, besteht in der Einbettung von Graphen in diese Doppelböden, wobei die Kabelführung selbst dann auf die Kanten dieser Graphen beschränkt bleibt. Diese Möglichkeit wird im nächsten Abschnitt ausführlicher erläutert.

3.1 Entwurf von Trassensystemen

Der Entwurf von Trassensystemen erfolgt in der Praxis meist in interaktiver Arbeitsweise, wenn überhaupt Rechentechnik zu Hilfe genommen wird. Dies ist durchaus adäquat, da die Automatisierung des Trassenentwurfs aufgrund der Vielfalt zu berücksichtigender Randbedingungen die Implementation komplizierter Verfahren erforderlich machen würde. Eine solche Software steht für den Entwurf von Kabeltrassen im Gebäude- und Campus-Bereich nicht zur Verfügung. Für den Entwurf großer überregionaler Trassen (z. B. für Pipelines) sind allerdings entsprechende Algorithmen entwickelt und in EDV-Programme umgesetzt worden.

Bei der Anwendung von Rechentechnik auf die interaktive Planung von Kabeltrassen kann man drei verschiedene Arbeitsweisen unterscheiden:

1. Computerunterstützte Ergänzung von digitalen Bauzeichnungen (z. B. Geschoßplänen) um den Verlauf von Trassen verschiedener Art, Erstellung konventioneller Dokumentationen.
1. Interaktiver Entwurf von Kabeltrassen in 3D-Modellen von Bauwerken, die mit Hilfe eines CAAD-Systems erstellt wurden.
1. Interaktiver Entwurf von Kabeltrassen mit einem Computer-Aided Network Facilities Management System (CANFM), das außer der Planung von Kabelnetzen auch die späteren Lebensphasen dieser Netze unterstützt (Betrieb, Re-engineering, Abbau).

Die "hohe Schule" des interaktiven Entwurfs von Trassen ist die Nutzung eines CAAD-Systems (siehe obige Variante 2) und die anschließende Überführung des in ein Bauwerk eingebetteten Trassenmodells in ein CANFM-System (siehe 3).

Im Zusammenhang mit dem interaktiven Entwurf eines Trassensystems unter Einbeziehung potentieller Trassen wird man auf ein klassisches Problem der Graphentheorie geführt:

Es sei G(V,E) der Graph, der ein solches Trassennetz repräsentiert. Dabei ist V die Menge der Knoten und E die der Kanten. Weiterhin sei eine Knotenmenge V₁ Í V gegeben, die die Menge der Knoten von G repräsentiert, die in den später zu verlegenden Kabelnetzen enthalten sein müssen (z. B. fest vorgegebene Anschlußpunkte, Standorte von Einspeisungen und Abnehmern bzw. von Endgeräten). Wenn dieser Graph Kreise enthält, also kein Baum ist, dann entsteht die Frage, wie man das entworfene Trassennetz so weit reduzieren kann, daß es möglichst kostengünstig wird, aber die Knoten der Menge V₁ enthält.

Dies ist das Steiner-Baum-Problem in einem gegebenen Graphen. Man sucht in G(V,E) einen Baum mit minimalen Gesamtkosten, der alle Knoten aus V₁ enthält (siehe z. B. /TM80, Iwa86/). Das kostengünstigste Trassensystem hat immer eine Baumstruktur (wie z. B. in Bild 4 dargestellt). Es ist aber zu beachten, daß sich die Minimierung der Trassenkosten später bei der Kabelverlegung rächen kann: Meist werden durch die Baumstruktur unnötig hohe Kosten für die Kabel (einschließlich ihrer Verlegung) erzwungen.

Wie schon in Abschnitt 2 erwähnt, passen räumliche Bereiche für die Kabelverlegung, die nicht linienartig sind, zunächst einmal nicht in das Konzept, mögliche Kabelverläufe durch Trassengraphen zu modellieren. Am Beispiel der Doppelböden soll aber im folgenden gezeigt werden, daß sich aus praktischen Gründen auch hier die Modellierung von Trassen anbietet. Da diese Trassen in Doppelböden zunächst nicht als Kabelführungselemente vorhanden sind, soll im folgenden von virtuellen Trassen gesprochen werden.

Bild 5 illustriert die Situation anhand eines einfachen Beispiels. Oben sind ein Raum mit Doppelboden, 6 Bodentanks und eine Kabeleintrittstelle dargestellt. Von letzterer sind Kabel zu jedem der Bodentanks zu verlegen. Die 2., 3. und 4. Grafik von oben in Bild 5 zeigen nun drei verschiedene Varianten für virtuelle Trassen für die Verlegung der Kabel. In der 2. Grafik von oben handelt es sich um einen Stern, dessen Zentrum die Kabeleintrittstelle ist und dessen Strahlen geradlinig zu den einzelnen

Bild 5: Virtuelle Trassennetze in Doppelböden

Bodentanks verlaufen. Diese virtuellen Trassen sind in dem Sinne optimal, daß die erforderliche Länge der Kabel minimal wird. Ihr großer Nachteil besteht aber darin, daß innerhalb des Doppelbodens keine Bündelung der Kabel vorliegt und dementsprechend bei einem notwendig werdenden Zugang von oben ein relativ großer Teil des Bodens einschließlich Bodenbelag in Mitleidenschaft gezogen wird.

Fragt man aus diesem Grund nun nach demjenigen Verlauf einer virtuellen Trasse, der am kürzesten ist und damit bei notwendigem Zugang von oben die geringsten Auswirkungen auf die Bodenfläche hat, so wird man auf das Steiner-Baum-Problem in der Ebene geführt (siehe z. B. /WZ97/). Die 3. Grafik von oben in Bild 5 zeigt die entsprechende Lösung. Selbstverständlich erkauft man den gerade genannten Vorteil i. allg. mit einer Verlängerung der Kabel selbst. Kürzeste Steiner-Bäume in der Ebene haben meist eine etwas unregelmäßige Lage, wie dies auch im Bild zu erkennen ist. Will man die Unregelmäßigkeit vermeiden, dann muß man den Verlauf der virtuellen Trassen einschränken, z. B. dadurch, daß man einen rektilinearen Verlauf fordert. Die Lösung für die entsprechende Variante des Steiner-Baum-Problems ist für das Beispiel in Bild 5 in der 4. Grafik von oben dargestellt.

In den beiden unteren Grafiken des Bildes 5 sind nun noch zusätzliche Luken vorhanden (durch Ellipsen repräsentiert). Diese Luken dienen dazu, die Kabel in bestimmten Bereichen des Doppelbodens auch ohne dessen Öffnung hinreichend zugänglich zu machen. Die zweite Grafik von unten stellt ein virtuelles Trassennetz dar, daß diese Situation berücksichtigt, aber noch Kreise enthält. Das Trassennetz ist also noch reduzierbar. Die unterste Grafik zeigt für diesen Fall die Optimallösung, und zwar einen solchen Baum als Trassengraph, der bei einem notwendig werdenden Zugang von oben den Boden in einem minimalen Bereich in Mitleidenschaft zieht und gleichzeitig für Kabellängen sorgt, die nahe beim Minimum liegen.

Bild 6 zeigt schließlich ein Beispiel für den Entwurf eines virtuellen Trassennetzes in einem Doppelboden mit Tanks und Zugangsluken.

Lediglich nebenbei sei hier erwähnt, daß die Festlegung der Lage der Zugänge von oben zu unterirdischen Rohrleitungsnetzen und die Berücksichtigung der entsprechenden Schächte beim Entwurf der Routen von Rohrleitungen im Erdreich auf ähnliche mathematische Probleme führt. Bild 7 zeigt den automatisierten Vortrieb eines Abwasser-Rohres mit Hilfe von ferngesteuertem Gelenkbohrer und Richtungs-Justierung mittels Laser-Strahl.

3.2 Routing von Punkt-zu-Punkt-Verbindungen

Will man in einem Trassennetz zwischen zwei vorgegebenen Netzknoten die Route eines Kabels planen, so wird man auf das Problem des kürzesten Weges in Graphen geführt. Für dieses klassische Problem der Graphentheorie ist eine Vielzahl von Algorithmen entwickelt und implementiert worden. Auch gute CANFM-Systeme verfügen über Funktionalität zum automatischen Routing einer Kabelverbindung zwischen zwei vorgegebenen Knoten des Trassengraphen. Allerdings sind hier

Bild 6: Entwurf eines virtuellen Trassennetzes in einem Doppelboden

gegenüber dem klassischen Shortest Path Problem vor allem folgende Besonderheiten zu berücksichtigen:

• Trassen haben eine begrenzte Aufnahme-Kapazität für Kabel. Daher sind bei der Suche nach einer geeigneten Route für ein neues Kabel die aktuellen Belegungen der einzelnen Trassenabschnitte mit Kabeln zu berücksichtigen. Trassenabschnitte, deren Aufnahme-Kapatzität (fast) erreicht ist, sind beim Routing neuer Kabel zu meiden.
• Weiterhin können unerwünschte Wechselwirkungen zwischen verschiedenen Leitungen für die Planung einer neuen Leitungsführung wichtig werden. Dies betrifft z. B. von Starkstromleitungen ausgehende elektromagnetische Störeinflüsse auf Kommunikationsnetze. Auch dieser Aspekt führt wieder dazu, daß u. U. bestimmte, mit Kabeln belegte Trassenabschnitte für das Routing einer neuen Leitung nicht in Frage kommen.
• In der Praxis der Planung von Kabelnetzwerken tritt also im hier betrachteten Zusammenhang meist nicht das Problem des kürzesten, sondern des optimalen Weges auf, wobei technische Randbedingungen zu berücksichtigen sind, die mit der vor dem Planungsschritt bereits vorhandenen Belegung des Trassennetzes mit Kabeln zusammenhängen. Nach Ausführung der Funktion des automatischen Routing und Bestätigung des vom System ermittelten Kabelweges durch den Planer muß diese Belegung natürlich ebenfalls automatisch aktualisiert werden.
  

Bild 7: Vortrieb eines Abwasser-Rohres ins Erdreich von einem Schacht aus

An dieser Stelle sei kritisch vermerkt, daß die CANFM-Funktion des automatischen Routing eines Kabelverlaufs zwischen zwei Punkten (Knoten im Trassennetz) meist nur ein bescheidenes Hilfsmittel zur Lösung komplexerer Planungsprobleme ist. Nur in Sonderfällen, z. B. im Rahmen einfacher Re-engineering-Prozesse, ist nach einer Route für genau eine neue Kabelverbindung gefragt. Meist geht es um das Layout komplexer Kabelnetze als Ganzes (z. B. von Netzen mit hierarchisch gegliederter Sternstruktur, siehe nächster Abschnitt). Mangels besserer Funktionen wird in der Praxis beim rechnerunterstützten Entwurf des Layouts von Kabelnetzen einfach mehrfach hintereinander die relativ einfache Optimierung einzelner Kabelwege vorgenommen. Dies führt i. allg. natürlich nicht zu einer Optimallösung für das eigentliche Layout-Problem, dessen Bedeutung für die Praxis seitens der Mathematiker leider bisher nicht erkannt wurde. Die Anzahl der Veröffentlichungen zum klassischen Shortest Path Problem steht in keinem adäquaten Verhältnis zur Anzahl der mathematischen Arbeiten betreffs Optimierung einer Menge von Wegen zwischen jeweils zwei vorgegebenen Knoten als Ganzes unter Berücksichtigung von Wechselwirkungen zwischen den Wegen wie sie im Fall des Kabelnetz-Layouts z. B. durch begrenzte Trassenkapazität zustande kommen. Zu den wenigen Beispielen für letztere Arbeiten gehören /Sch85a und b, Sch88b/.

Während das klassische Shortest Path Problem viel Aufmerksamkeit auf sich fokussiert hat und entsprechende anwendungsspezifische Algorithmen für das Routing von Kabelverbindungen zwischen zwei vorgegebenen Punkten in vielen CANFM-Systemen zur Verfügung stehen, ist folgendes Problem, das ebenfalls die Wegoptimierung betrifft, bisher völlig vernachlässigt worden:

Trassen sind häufig hierarchisch gegliedert (siehe auch /Lost97, Nitz97/). Bild 8 zeigt ein Beispiel. Die oberste Hirarchie-Ebene ist hier ein unterirdischer Schacht mit einem System von Kabelpritschen, die zweite Hierarchie-Ebene ist durch die

einzelnen Pritschen gegeben, auf denen wiederum Kabel verlegt werden. In vielen CANFM-Anwendungen ist es nun wichtig, im Netzwerk-Modell die Kabel nicht nur der Trasse als Ganzes, sondern den jeweiligen Kabelführungselementen der jeweils untersten Hierarchie-Ebene (im Bild 8 also den einzelnen Pritschen) zuzuordnen. Auch in diesem Fall bietet sich zur Vereinfachung der Planung der einzelnen Kabelverläufe wieder eine CANFM-Funktion zur Bestimmung optimaler Routen im Trassengraphen an. Worin soll dabei nun die neue Problemstellung liegen? Man braucht doch nur die Kabelführungselemente, die die unterste Hierarchie-Ebene einer hierarchisch gegliederten Trasse bilden (also z. B. Kabelpritschen), durch Kanten des Trassengraphen zu modellieren. Dies ist zwar grundsätzlich richtig, aber was dann mit dem Trassengraphen geschieht, illustriert Bild 9 anhand eines einfachen Beispiels. In Bild 9a ist eine "normale" Trassenkreuzung durch einen Knoten eines Graphen gleichzeitig mit den inzidenten Kanten, die die Trassen repräsentieren, dargestellt. Ist nun jede einzelne Trasse hierarchisch gegliedert (siehe auch /Lost97, Nitz97/), so bläht sich der kleine Ausschnitt aus einem Graphen, der in Bild 9a gezeigt ist, gewaltig auf. Im Beispiel des Bildes 9 besteht die zweite und letzte Hierarchie-Ebene des Trassensystems aus jeweils vier Rohren, durch die Kabel verlegt werden können. Bild 9b zeigt stark schematisiert in der Mitte die Draufsicht auf einen Einstiegsschacht in eine Trassenkreuzung. Die grau hinterlegten Elemente der Grafik symbolisieren die Trassenabschnitte mit den jeweils vier Rohren für die Aufnahme von Kabeln (aufgeklappt auf die Darstellungsebene der Zeichnung). Bild 10 zeigt ein Beispiel mit einem umfangreicheren Raster von Kabelführungselementen. In Bild 9c ist nun illustriert, wie aus dem einfachen Teil eines Graphen (1 Knoten mit 4 inzidenten Kanten) des Bildes 9a im Falle der Kreuzung hierarchischer Trassen mit je vier Kabelführungselementen ein Graph wird, der 16 Knoten und 96 Kanten zwischen diesen enthält und in den von außen 16 Kanten hineinführen. Die 96 Kanten repräsentieren alle Möglichkeiten der Kabelführung von jeder der 16 Rohröffnungen aus zu den 3x4=12 Rohröffnungen der anderen in die Kreuzung einmündenden Trassenabschnitte. Natürlich könnte man das Problem des Routing von Kabelverbindungen auf einem derartig in seiner Knoten- und Kantenzahl vergrößerten Graphen mathematisch exakt als Optimierungsproblem lösen, jedoch ist der Aufwand (wesentliche Erhöhung des Aufwandes für die Trassenmodellierung durch Graphen, sprunghaft erhöhter Speicherplatz- und Rechenzeit-Bedarf) offenbar nicht angemessen. Man sollte zur Lösung des Problems vielmehr mit Graphenmodellen auskommen können, die gegenüber den Graphen, die nur die oberste Hierarchie-Ebene von Trassen repräsentieren, nur wenig erweitert sind, selbst wenn dann eine exakte Routenoptimierung nicht mehr möglich sein sollte. Ein solcher einfacher Ersatzgraph für eine Kreuzung hierarchischer Trassen ist in Bild 9d gezeigt. Gegenüber der Kreuzungsmodellierung gemäß 9a besteht hier nun immerhin die Möglichkeit, den geradlinigen und den abzweigenden Kabelverläufen im Kreuzungsbereich zweier hierarchischer Trassen unterschiedliche Gewichte zuzuordnen. Dabei kann es sich z. B. um Unter- bzw. Obergrenzen für Kabellängen in diesen Kreuzungsbereichen handeln. Zur Einbeziehung von Funktionen zum optimalen Routing in hierarchisch gegliederten Trassen besteht derzeit noch FuE-Bedarf.

3.3 Hierarchien von Sternen

Sternförmige Strukturen spielen in Versorgungsnetzen eine große Rolle. Von einem zentralen Punkt (Knoten) aus verlaufen N Leitungen oder Versorgungswege zu
N Endpunkten (oft Abnehmern).

Mit einer sogenannten strukturierten Verkabelung /Rie95/ strebt man insbesondere für Bürogebäude eine flächendeckende Versorgung mit Kommunikationsmöglichkeiten an. Man will damit eine weitgehende Unabhängigkeit des jeweiligen Kommunikationsnetzes z. B. von der aktuellen Belegung von Büroräumen mit Arbeitsplätzen erreichen.

Im Gegensatz zu einer Verkabelung, die sich am aktuellen Bedarf orientiert, erfordert die strukturierte Verkabelung eine relativ hohe Anfangsinvestition, die sich später in der Betriebsphase auszahlt. Bild 11 zeigt die strukturierte Verkabelung mit den vorgesehenen drei Verteiler-Ebenen (Standort-, Gebäude- und Etagenverteiler). Bild 11 zeigt, daß die strukturierte Verkabelung graphentheoretisch gesprochen einem Baum entspricht. Es ist jedoch ein ganz spezieller Baum, der gut als Hierarchie von Sternen beschrieben werden kann. Sind die Positionen der Sternzentren (der Verteiler) a priori gegeben, so reduziert sich das Problem der Optimierung des Layouts einer Stern-Hierarchie offenbar auf die mehrfache Lösung des Routing Problems zwischen je zwei vorgegebenen Knoten des Trassennetzwerkes (siehe Abschnitt 3.2). Man kann dabei die Tatsache ausnutzen, daß der eine von jeweils zwei Knoten mehrfach derselbe ist, z. B. sind i. allg. mehrere Routen von einem

Bild 11: Strukturierte Verkabelung nach EN50173

Gebäudeverteiler zu mehreren Etagenverteilern oder von einem Etagenverteiler zu mehreren Dosen zu ermitteln.

Sind als Standorte für Verteiler mehrere Alternativen möglich, so ist die Layout-Optimierung für Stern-Hierarchien etwas komplexer. Als Lösungsmethode bietet sich die von dem amerikanischen Mathematiker Richard Bellmann entwickelte Methode der Dynamischen Programmierung an (siehe z. B. /Bel57, Iwa 84/). Ein speziell auf Stern- Hierarchien zugeschnittenes Verfahren wurde in /Iwa85/ vorgeschlagen.

3.4 Auslegung von Ringen

Teile von Kommunikationsnetzen haben oft eine Ring-Struktur (z. B. Token-Ring, FDDI-Ring). Bei der Planung der räumlichen Anordnung von Ringen sind zwei wesentliche Bedingungen zu berücksichtigen:

• Der Ring muß durch eine Anzahl vorgegebener Knoten führen. Im Falle eines FDDI-Ringes, der das Kommunikationsrückrat eines Universitäts-Campus darstellt, wären das z. B. die Gebäudeanschlüsse.
• Selbstverständlich gelten auch für Ringe wieder die Restriktionen, die auch für andere Kommunikationsleitungen eine Rolle spielen (z. B. Verlegung in dafür vorgesehenen Trassen).

Das Problem der räumlichen Auslegung von ringförmigen Kommunikationsleitungen entspricht damit einem der berühmtesten mathematischen Probleme, dem des Traveling Salesman /Len90, Tur96/. Dieses Problem ist NP-hart, d. h. der Rechenzeit-Bedarf für seine Lösung nimmt mit der wachsenden Anzahl der vorgegebenen Knoten, durch die der Ring (die Rundreise) verlaufen soll, exponentiell zu. Deshalb sind viele heuristische Algorithmen entwickelt worden, in der überwiegenden Mehrzahl der Fälle aber entweder mit rein mathematischen Zielsetzungen oder aber für andere Anwendungsgebiete als Kabelnetzwerk-Layout.

Bild 12 illustriert das Problem des räumlichen Layouts von Ringleitungen aus praktischer Sicht. Bild 12a zeigt die typische Ringstruktur, wie sie z. B. in schematisierten Darstellungen zu FDDI-Ringen häufig verwendet wird. Bild 12b verdeutlicht die Möglichkeit, bei Beibehaltung der Ringstruktur durch räumlich parallele Verlegung eines Paares von Leitern zu einer offenen Kette (bezogen auf dieses Paar) zu gelangen. Die zu den Bildern 12a bzw. b gehörigen Layout-Probleme sind in den Bildern 12c bzw. d präsentiert. Dort ist jeweils ein Trassengraph mit festen Anschlußstellen von Kommunikationsendgeräten, die in den Ring einzubeziehen sind, dargestellt. Bild 12c zeigt eine geschlossene Route für die Ringleitung, die der Übersichtlichkeit halber etwas versetzt zu den Trassen und Anschlußstellen gezeichnet wurde. In Bild 12d handelt es sich entsprechend Bild 12b um eine offene Kette. Das zugehörige mathematische Problem ist hier nicht mehr das des Handelsreisenden, sondern das des Traveling Salesman without Return. Der Weg des Salesman, d. h. hier des Kabels, muß die vorgegebenen Knoten enthalten und soll gleichzeitig möglichst kurz sein.

3.5 Layout von Gebäude- bzw. Feldbussystemen

Ein Gebäude- bzw. ein Feldbus kann die Struktur einer unverzweigten Linie haben. In der Praxis ist ein derartiger Bus in einem Netzwerk, das mögliche Leitungsführungen für ihn repräsentiert, so zu verlegen, daß alle fest vorgegebenen Anschlußpunkte (z. B. Orte installierter Sensoren und Aktoren) in die Gesamtroute des Busses einbezogen werden. Es entsteht das bereits am Ende des vorigen Abschnittes angesprochene Problem des Traveling Salesman with no Return in einem Graphen.

Das Feldbus-System selbst und das zugehörige Anordnungsproblem werden etwas komplexer, wenn von der o. g. Linie einzelne, ihrerseits unverzweigte Seitenzweige abgehen dürfen, was in der Praxis der Fall ist. Sowohl für die Länge dieser einzelnen Seitenzweige als auch für die Gesamtlänge des Busses gibt es Obergrenzen. Beim Layout eines Busses dieser Struktur entsteht damit das Problem, den verzweigten Bus so in das durch einen Graphen repräsentierte Trassennetz hineinzulegen, daß

• alle vorgegebenen Anschlußstellen vom Bus berührt werden,
• der Bus eine minimale Gesamtlänge hat und
• die o. g. Längen-Obergrenzen

eingehalten werden. Bild 13 zeigt ein fiktives Beispiel für das Layout eines verzweigten Busses in einem Etagenplan. Nach Kenntnis der Autoren gibt es bisher keine Funktionalität zur Lösung dieses Problems im Bereich des CANFM. Forschungs- und Entwicklungsbedarf ist also vorhanden.

3.6 Layout räumlich disjunkter Mehrfachverbindungen

Bei besonders hohen Verfügbarkeitsanforderungen werden manchmal mehrere Verbindungen zwischen zwei Knoten eines Kommunikationsnetzes gefordert. Diese Redundanz sollte dann natürlich so ausgelegt werden, daß bei einer Havarie (z. B. einem Brand oder einer Trassenzerstörung durch Bauarbeiten) nicht alle Verbindungen gleichzeitig ausfallen. Man ist deshalb bestrebt, die einzelnen Verbindungen räumlich getrennt zu führen und dabei möglichst geringe Kabel- bzw. Kabelverlegungskosten zu verursachen. Bezogen auf einen Trassengraphen ist dieses praktische Problem mathematisch in /DI85/ formalisiert. Dort ist auch ein Lösungsverfahren auf der Grundlage einer Graphen-Reduktion angegeben.

3.7 Auslegung von Meßdaten in Trassensystemen

Bisher ist wenig bekannt, daß ein LWL nicht nur der Datenübertragung dienen kann, sondern auch ein hervorragender passiver Temperatursensor ist, und zwar auf seiner gesamten Länge. Die Messung beruht auf der OTDR-Methode (Optical Time Damain Reflectometry). Das technische Prinzip ist u. a. in /GHIN97a und b/ be-schrieben. Es ist naheliegend, mit Hilfe solcher Meßkabel Kabeltrassen bezüglich ihrer Temperatur zu überwachen, stellen diese mit den darin verlegten Leitungen für Kommunikation und Stromversorgung doch einen wichtigen Teil der Infrastruktur jeden Gebäudes dar. Überhitzungen sind hier eine ernste Bedrohung. Sie können die Funktionsfähigkeit der Netzwerke einschränken oder gar aussetzen. Außerdem können bestimmte Kabeltrassen, insbesondere Schächte, zur Ausbreitung von Bränden beitragen.

Will man mit Hilfe eines Sensorkabels ein gegebenes Trassensystem überwachen, so entsteht zunächst ein Layout-Problem. Man muß einen geeigneten Standort für das Meßgerät und die Einheit zur Auswertung und Visualisierung der Meßergebnisse festlegen. Anschließend ist eine solche Route für das Sensorkabel zu bestimmen, die durch alle Kanten des gegebenen Trassengraphen mindestens einmal verläuft und gleichzeitig möglichst kurz ist. Bild 14 zeigt verschiedene Varianten für das Meßsystem. Bei Variante 1 wird eine einzelne optische Faser ausgehend vom Meßgerät (als kleines Rechteck dargestellt) durch das Trassennetz zurück zum Meßgerät geführt. Zweck dieser Rückführung ist die Möglichkeit der Erkennung wesentlicher Meßfehler, indem das Meßgerät abwechselnd mit den beiden Faserenden verbunden wird (in Bild 14 durch einen Schalter angedeutet). Bei dieser Variante ergibt sich bezüglich der Führung der optischen Faser durch das Trassennetz exakt das auf einen chinesischen Mathematiker (Meigu Guan) zurückgehende Chinese Postman Problem (siehe z. B. /Fre79, EGL95/). Variante 2 in Bild 14 ergibt sich aus Variante 1 durch Verwendung eines Meßkabels mit zwei optischen Fasern, wobei letztere an dem einen Kabelende an das Meßgerät angeschlossen und am anderen Ende miteinander verbunden sind. Bei der Planung des Kabelverlaufs entsteht dann eine Abwandlung des Chinese Postman Problems (CPP), das hier Chinese Route Problem (CRP) genannt wird: Es ist nicht mehr nach einer zum Ausgangspunkt (Meßgerät) unbedingt zurückzuführenden Route für das Meßkabel gefragt. Vielmehr geht es jetzt um eine möglichst kurze Route, die alle Trassenabschnitte mindestens einmal durchläuft, aber durchaus offen sein kann. Verzichtet man auf die o. g. Möglichkeit der Fehlererkennung (Variante 3 in Bild 14), so entsteht bei der Planung des dann einadrig ausgeführten Meßkabels natürlich genau das gleiche Problem.

Wesentlich komplizierter wird die Situation, wenn das Meßgerät mehrere (K) Anschlüsse für Meßkabel besitzt (Varianten 4 und 5 in Bild 14). Wieder geht es darum, daß jeder Trassenabschnitt von einem Meßkabel erfaßt wird (von welchem ist egal). Ziel ist die Minimierung der Gesamtlänge aller Meßkabel oder (aus Gründen der Meßgenauigkeit) des längsten Kabels. Zur Lösung des Problems in der Praxis des Kabel-Layouts bietet es sich an, in heuristischer Weise das gesamte Trassennetz geeignet in K Komponenten (z. B. Subnetze in den einzelnen Etagen eines Gebäudes) zu zerlegen und dann für jede Komponente eines der K Meßkabel vorzusehen. Damit ließe sich das Problem auf die Suche nach K Lösungen des CPP- oder CRP in den jeweiligen Teilen des gesamten Trassennetzes zurückführen.

Literatur

 zurück zum CAFM-Ratgeber