Investigation of adaptive ressource allocation mechanisms for end-to-end troughput optimisation in multihop ad-hoc networks with multiple ressources
Final Report Abstract
Gegenstand des Projektes ist ein Kanalzuweisungsverfahren für Mehrkanal-Ad-Hoc-Netze, bei denen die Knoten mehrere standardkonforme IEEE 802.11-Transceiver-Einheiten verwenden und somit zeitgleich auf mehrere im System verfügbare Kanäle zugreifen können. Die Auswahl eines Kanals erfolgt anhand erweiterter Routing-Tabellen. Für die Erstellung der erweiterten Einträge in den Routing-Tabellen wird ein Cross-Layer-basiertes Kanalzuweisungsverfahren verwendet, das die in einem Netz verfügbaren Kanäle nach einer zuvor definierten Kanalzuweisungsstrategie verteilt. Wesentlicher Vorteil des Verfahrens gegenüber anderen ist, dass standardkonforme IEEE 802.11-Transceiver-Einheiten genutzt werden können, da keine Anderungen der Medienzugriffssteuerung erforderlich sind. Im Vordergrund der Untersuchungen stehen DCF-orientierte Zuweisungsstrategien, die DCF-spezifische Problemsituation in Ad-Hoc-Netzen vermeiden und somit neben dem Effekt der höheren Netzkapazität durch Nutzung mehrerer Kanäle zusätzlich eine bessere Ausnutzung der in einem Netz verfügbaren Kapazität erzielen können. Ziel der Untersuchungen war die Beurteilung der entwickelten Kanalzuweisungsstrategien in Hinblick auf ihre Leistungsfähigkeit im Vergleich zu Ansätzen, bei denen die Kanalzuweisung ohne Berücksichtigung der DCF-spezifischen Probleme erfolgt. Basierend auf den möglichen Problemen bei Anwendung der DCF in Ad-Hoc-Netzen wurden vier DCF-orientierte Strategien abgeleitet: Exposed-Node-, Hidden-Node-, Blocking- und Maskinga Strategie. Zum Vergleich werden zusätzlich zwei Link-orientierte Verfahren beschrieben, die nicht direkt auf die DCF-spezifischen Probleme ausgerichtet sind: Kantenfärbung- und Zufall-Strategie. Alle Strategien basieren auf einem graphentheoretischen Ansatz, bei dem die Lösung durch Färbung eines geeigneten Abhängigkeitsgraphen ermittelt wird. Eine Kantenfärbung entspricht dem aus der Literatur bekannten PCA-Verfahren von Hu. Die Hidden-Node-Zuweisungsstrategie ist mit dem aus der Literatur bekannten TCA-Verfahren vergleichbar. Für die Untersuchungen wird ein Konzept zur Abschätzung der Kapazität der einzelnen Komamunikationsbeziehungen sowie der Gesamtkapazität in IEEE 802.11-basierten Netzen mit zufällig verteilten Knoten eingeführt und ein Vergleich mit der theoretisch maximal erzielbaren Kapazität durchgeführt. Der Vergleich zeigt, dass in IEEE 802.11-basierten Netzen unter den in dieser Arbeit angenommenen Randbedingungen wesentlich geringere Kapazitäten realisierbar sind, als im Idealfall möglich wären. Die Beurteilung der vorgeschlagenen Zuweisungsstrategien erfolgt mit Hilfe der im Projekt entwickelten Simulationsumgebung am Beispiel des Standards IEEE 802.11b. Anhand der aus den Kanalzuweisungsstrategien resultierenden Kapazitäten sowie der dazu erforderlichen Anzahl an Kanälen wird auf die Effizienz der Verfahren geschlossen. Zur Beurteilung der Leistungsfähigkeit in Bezug auf die Lösung von DCF-spezifischen Problemsituationen werden der Durchsatz eines Netzes im Verhältnis zu der Kapazität eines Netzes, die Fairness bei der Aufteilung der verfügbaren Kapazität auf die Kommunikationsbeziehungen im Netz sowie die Verzögerung beim Datentransport bei unterschiedlichen Belastungen des Netzes ermittelt. Die Simulationsergebnisse zeigen eine deutliche Überlegenheit der Blocking-Strategie gegenüber den anderen Strategien. Dies lässt darauf schließen, dass das Blocking-Problem einen signifikanten Einfluss auf die Leistungsfähigkeit IEEE 802.11-basierter Mehrkanal-Ad-Hoc-Netze hat und bestätigt somit die von Ray u.a. durchgeführten Untersuchungen zum Durchsatz in IE-EE 802.11-basierten Netzen mit nur einem Kanal. Die Untersuchungsergebnisse der vorliegenden Arbeit zeigen, dass durch die Verwendung von Informationen über die in einem Netz vorhandenen Flüsse und deren Richtungen zur Vermeidung DCF-spezifischer Problemsituationen eine effizientere Ausnutzung der verfügbaren Kapazität erreicht werden kann, als bei Verfahren, die nicht speziell auf DCF-spezifische Zugriffsprobleme ausgerichtet sind. Mit den Erkenntnissen aus diesem Projekt kann festgestellt werden, • dass die Verwendung mehrerer Spreizcodes in einem IEEE 802.11b-System nicht als alternative zu mehreren TRX-Einheiten angewendet werden kann, wenn ein Mehrkanalsystem mit dem im Projekt entwickelten flussorientierten Kanalzuweisungsverfahren realisiert werden soll und, • dass mit einer DCF-orientierten Zuweisungsstrategie eine bessere Ausnutzung der verfügbaren Kapazität erreicht werden kann, diese aber mit einer Linkadaption nicht kombinierbar ist. Eine vom Kanalzuweisungsverfahren entkoppelt agierende Linkadaption ist nicht von Vorteil, außer bei sehr wenig verfügbaren Kanälen. • Das Szenario hat zwar Auswirkungen auf das auf die Leistungsfähigkeit der unterschiedlichen Kanalzuweisungsstrategien, jedoch zeigte die Blocking-Strategie bei den im Projekt untersuchten Parametrierungen stets gute bzw. die besten Ergebnisse. • Haben bestimmte Knoten nicht die erforderliche Anzahl an Kanälen zur Verfügung und wird die Anzahl der Kanäle in diesen Knoten begrenzt, so kann keine optimale Lösung gemäß der Zuweisungsstrategie gefunden werden. Die Ergebnisse zeigen aber, dass sich auch bei einer suboptimalen Lösung die Charakteristiken der Kanalzuweisungsstrategien ausprägen. Auch hier zeigt die Blocking-Strategie stets gute bzw. die besten Ergebnisse. Die Untersuchungen in diesem Projekt wurden für statische Netze durchgeführt. Mögliche weitere Arbeiten eröffnen sich bei der Entwickulung von verteilten Algorithmen und speziellen Protokollen für das flussorientierte Zuweisungsverfahren sowie entsprechende Untersuchungen zur Leistungsfähigkeit in Netzen mit einer nicht vernachlässigbaren Knotendynamik. Der Antragsteller plant derzeit jedoch keine Arbeiten mit entspechendem Schwerpunkt. Das Verfahren zur flussorientierten Kanalzuweisung verwendet derzeit keine Kanalbündlung zur Übertragung zwischen einem Knoten paar. In weiteren Arbeiten könnte eine derartige Erweiterung implementiert werden. Die in diesem Projekt vorgeschlagenen Verfahren sind auf alle IEEE 802.11-basierten Netze mit Distributed Coordination Function (DCF) anwendbar. Derzeit arbeitet der Antragsteller u.a. im Bereich der Mesh-Netze. Da auch hier eine IEEE 802.11-basierte Lösung angestrebt wird, können die Erkenntnisse dieses Projektes bei der Weiterentwicklung dieser Netze einfließen. Auch die im Rahmen dieses Projektes entwickelte Simulationsumgebung wird von dem Antragsteller für die Untersuchungen dieser Netze eingesetzt werden.
Publications
- "Assigning Multiple Resources in Ad Hoc Networks Using Self-Organizing Maps,". 1st European Workshop on Wireless Sensor Networks (EWSN) - Work in Progress, Berlin, vol. 1, 2004, pp. 25 - 28
A. Heinrich and S. Feldmann
- "Blocking and Blocking Probability in IEEE 802.11-Based Ad Hoc Networks,". COST 273, Towards Mobile Broadband Multimedia Networks 11th Management Committee Meeting, Duisburg, Germany, 2004
S. Feldmann and A. Heinrich
- "Technischer Report zum Projekt OMURANET". Institut für Kommunikationstechnik, Technical Report, 2006
Andreas Heinrich
