HEINZ NIXDORF INSTITUTUniversität Paderborn

Fakultät für Elektrotechnik,Informatik und Mathematik

Algorithmische Probleme in Funknetzwerken

XIKlaus Volbert

kvolbert@upb.de

2Klaus Volbert07.01.2003

HEINZ NIXDORF INSTITUTUniversität Paderborn

Fakultät für Elektrotechnik, Informatik und Mathematik

Algorithmische Probleme inFunknetzwerken XI

Einführung

Mobiles Ad Hoc Netzwerk (MANET)

Autonomes System aus beweglichen Teilnehmern (Knoten), die untereinander über drahtlose Verbindungen (Kanten) kommunizieren können.

Drahtlose Kommunikation:

Omnidirektional (Funk)

Unidirektional (Richtfunk, Infrarot)

Jeweils mit fester oder variabler Sendestärke

3Klaus Volbert07.01.2003

HEINZ NIXDORF INSTITUTUniversität Paderborn

Fakultät für Elektrotechnik, Informatik und Mathematik

Algorithmische Probleme inFunknetzwerken XI

Mobiles Ad Hoc Netzwerk

Eigenschaften:• Keine feste Infrastruktur

• Keine zentrale Verwaltung

• Freie Bewegung der Teilnehmer

• Dynamische Netzänderungen

• Eigenständig oder Teil eines anderen Netzes

• Keine Ortsinformationen

• …

4Klaus Volbert07.01.2003

HEINZ NIXDORF INSTITUTUniversität Paderborn

Fakultät für Elektrotechnik, Informatik und Mathematik

Algorithmische Probleme inFunknetzwerken XI

Probleme in MANETs

• Interferenzen– Hidden Terminal Problem– Exposed Terminal Problem– Asymmetrie (var. Reichweite)

• Zusammenhang und Routing

• Dynamische Änderungen– Bewegung– Ein/Ausschalten

A B C

A B C D

D

A B

C

5Klaus Volbert07.01.2003

HEINZ NIXDORF INSTITUTUniversität Paderborn

Fakultät für Elektrotechnik, Informatik und Mathematik

Algorithmische Probleme inFunknetzwerken XI

Kommunikation in MANETs:Experimentelle Untersuchungen

• Netzwerkschicht– Charles E. Perkins

• Verbindungsschicht– Nitin Vaidya

• IETF MANET Working-Group

http://www.crhc.uiuc.edu/~nhv/presentations.html

http://www.ietf.org/html.charters/manet-charter.html

6Klaus Volbert07.01.2003

HEINZ NIXDORF INSTITUTUniversität Paderborn

Fakultät für Elektrotechnik, Informatik und Mathematik

Algorithmische Probleme inFunknetzwerken XI

Netzwerkschicht

• Routingprotokoll– Bestimmung von Kommunikationswegen– Transport von Informationen entlang dieser Wege

• Protokollklassen:– Proaktiv: Tabelle, kontinuierliche Aktualisierungen– Reaktiv: Aktualisierung auf Abruf– Hybrid: Teilweise Tabelle, Teilweise auf Abruf

• Verteilte Routingvarianten:– Distanzvektor-Protokolle (count-to-infinity)– Linkzustands-Protokolle– Weitere Varianten: Fluten, Potential-Algorithmen, u.ä.

7Klaus Volbert07.01.2003

HEINZ NIXDORF INSTITUTUniversität Paderborn

Fakultät für Elektrotechnik, Informatik und Mathematik

Algorithmische Probleme inFunknetzwerken XI

Routingprotokolle

• Proaktive Protokolle:– Destination Sequenced Distance Vector (DSDV)– Optimized Link State Routing (OLSR)

• Reaktive Protokolle:– Dynamic Source Routing (DSR)– Ad hoc On-demand Distance Vector (AODV)– Temporally Ordered Routing Algorithm (TORA)

• Hybride Protokolle:– Zone Routing Protocol (ZRP)– Greedy Perimeter Stateless Routing (GPSR)

8Klaus Volbert07.01.2003

HEINZ NIXDORF INSTITUTUniversität Paderborn

Fakultät für Elektrotechnik, Informatik und Mathematik

Algorithmische Probleme inFunknetzwerken XI

Dynamic Source Routing

• Jeder Knoten unterhält einen Wege-Cache• Ein Paket soll verschickt werden:

– Cache wird überprüft: ex. ein Weg zum Zielknoten?– Falls nicht: Starte Wegeermittlung durch Fluten (Route Discovery)– Geflutete Pakete (Route Request) werden nur von Knoten

weitergegeben, die das Paket noch nicht empfangen haben– Dabei wird jeder besuchte Knoten in den Paketkopf eingetragen– Ein Weg wird zurückgegeben (Route Reply), sobald er vollständig

ermittelt wurde (z.B. Teil eines Weges im Cache gefunden)

• Fehlerhafte Verbindungen werden erkannt und die Wege darüber aus dem Cache entfernt– Nachbarn werden nach Ersatzwegen gefragt oder eine neue

Wegeermittlung gestartet (Route Maintenance)

9Klaus Volbert07.01.2003

HEINZ NIXDORF INSTITUTUniversität Paderborn

Fakultät für Elektrotechnik, Informatik und Mathematik

Algorithmische Probleme inFunknetzwerken XI

Verbindungsschicht

• Übertragungstechniken:– FDMA, TDMA, CDMA, SDMA, CSMA/CD, CSMA/CA

• Medium Access Control (MAC)– Probleme: Hidden Terminals und Exposed Terminals– Übertragung mit Bestätigungen (ACK)– MACA: RTS-CTS Austausch (Request-to-Send, Clear-to-Send)– Exponentieller BackOff– MACAW: Backoff ohne komplettes Zurücksetzen, dafür

Verringerung bei erfolgreicher Übertragung um 1– Probabilistische Protokolle– Bei variabler Sendestärke sende „Besetztzeichen“ (Busy Tone)

auf zusätzlicher Frequenz (PCMA)– Weitere Varianten: PAMAS, D-MAC, …