Datenverteilung in Ad-hoc Netzen 1/24 Adaptive Datenverteilung in mobilen Ad-hoc Netzen unter Verwendung des Area Graph basierten Bewegungsmodells S. Bittner,

Datenverteilung in Ad-hoc Netzen 1/24

Adaptive Datenverteilung in mobilen Ad-hoc Netzen

unter Verwendung des Area Graph basierten Bewegungsmodells

S. Bittner, U. Raffel, M. Scholz

Institut für Informatik

Freie Universität Berlin

Workshop „Grundlagen und Anwendungen mobiler Informationstechnologie “, Heidelberg, 23.03.2004


Motivation

Aufgabe: Datenverteilung in mobilen Ad-hoc-Netzen● Software-Update

● Anfrage an alle Netzteilnehmer

● Katastrophenszenario

Ziel: Effiziente Verteilung der Daten● Maximierung der Zahl der erreichten Clients

● Minimierung des Ressourcenverbrauchs

● Minimierung der Zeit

Probleme● Netztopologie ändert sich permanent

● Begrenzte Ressourcen (Energie, Bandbreite, CPU)


Gliederung

Motivation

Verteilungsprotokolle

Bewegungsmodelle

Untersuchungen/Ergebnisse

Zusammenfassung/Ausblick



Grundlagen der Funktechnik● beschränkte Reichweite

● kein Mehraufwand für Senden an alle Nachbarn (Broadcast) gegenüber Senden an einen (Unicast) oder mehrere (Multicast) Nachbarn

● gleichzeitiges Senden führt an Stellen der Überlappung zu Verlust beider Nachrichten

Protokolle:● Einfaches Fluten

● Probalistisches Fluten

● Adaptives probabilistisches Fluten


Einfaches / Probabilistisches Fluten

Einfaches Fluten● Jeder Knoten sendet an alle Nachbarn

● Abbruch, wenn Daten bereits erhalten

Probabilistisches Fluten● Jeder Knoten entscheidet, ob er weitersendet

(Wahrscheinlichkeit p)

● Wenn er sendet, dann an alle Nachbarn

● Abbruch, wenn Daten bereits erhalten

● Bei p=1 wie Einfaches Fluten


Adaptives Probabilistisches Fluten

wie Probabilistisches Fluten, aber...

Wahrscheinlichkeitswert p passt sich an Umgebung an

Anzahl der Nachbarn eines Knotens bekannt (durch „Hello“-Messages wie z.B. in AODV)

Betrachtet wird die Anzahl der Nachbarn des Senders (ns)

Bis Schwellenwert x: p = 1

Ab Schwellenwert x: p = x / (ns) erwartet x weitersendende Knoten

Bei x = ∞ wie Einfaches Fluten


Adaptives Prob. Fluten: Erweiterungen

Einbeziehung der Anzahl der Nachbarn des empfangenden Knotens (ne)

● betrachtet wird das Minimum aus ns und ne

● erleichtert Übergänge in weniger dichte Gebiete

Korrekturfaktor bei hohen Differenzen zwischen ns und ne

● Erhöhung des Wahrscheinlichkeitswertes p um Quotienten aus Maximum und Minimum aus ns und ne

● erleichtert sowohl Übergänge in weniger dichte Gebiete aus auch in dichtere Gebiete

),min(

),max(

),min(,1min

nnnn

nn es

es

es

xp


Gliederung

Motivation


Bewegungsmodelle




Bewegungsmodelle

Ziel von Bewegungsmodellen● Abbildung realer Bewegungen

● einfach berechenbar / simulierbar

Bewegungsmodelle:● Random Waypoint Bewegungsmodell

● Area Graph basiertes Bewegungsmodell


Random Waypoint Bewegungsmodell

Rechteckige Fläche

Netzknoten wählen zufälligen Wegpunkt

Bewegung zum Wegpunkt mit zufälliger Geschwindigkeit, dann neuer Wegpunkt

keine realistische Abbildung von Bewegungen und Netztopologie


Area Graph basiertes Bewegungsmodell

Realistischer als Gleichverteilung in der Ebene

z.B. Topologie von Städten, Ausstellungen, Universitäten

Einzelne Geräte bilden unstabilen Graphen

Abbildung auf einen stabileren Area Graphen● Cluster Knoten

● Wege Kanten


Area Graph - Formalisierung

mehrere rechteckige Flächen (Cluster)

durch Wege miteinander verbunden

zufällige Verweildauer im Cluster

Innerhalb eines Clusters Bewegung nach Random Waypoint Bewegungsmodell

Nach Ablauf der Verweildauer zufällige Wahl eines anderen Cluster, direkte Bewegung auf dem Weg


Gliederung

Motivation


Bewegungsmodelle




Untersuchungen

Verschiedene Protokolle● Einfaches Fluten

● Probabilistisches Fluten: 20%, 40%, 60%, 80%

● Adaptives Probabilistisches Fluten: Schwellenwerte 5, 6, 7, 8 und 9

Verschiedene Szenarien● 3 verschiedene mit Random Waypoint Bewegungsmodell

● 4 verschiedene mit Area Graph basiertem Bewegungsmodell

Realisierung der Szenarien mittels OMNeT++

Ziel: Finden von optimalen Protokollen für verschiedene Szenarien / Umgebungen


Zielgrößen

Anzahl der erreichten Knoten

Dauer der Verteilung (Erreichte Knoten bis Zeitpunkt t)

Anzahl der Nachrichten(relativ zur Anzahl der erreichten Knoten)


Simulationsparameter

Knotenanzahl: 2000

Sendereichweite: 30 m

Bandbreite: 11 MBit/s

Nachrichtengröße: 400 Byte

Verteilung von einem Startknoten aus

Für Random Waypoint Bewegungsmodell:● Quadratische Fläche mit Kantenlänge 400 m, 600 m, 800 m

● Geschwindigkeit der Knoten: 1 m/s – 4 m/s


Ergebnisse Random Waypoint

Dargestellt:

● Erreichte Knoten

● Nachrichten pro Erreichtem Knoten

1 Punkt pro Protokoll

Protokoll sollte möglichst rechts unten liegen

600 x 600 m Fläche (400 x 400 m / 800 x 800 m ähnlich) Fast alle Knoten werden erreicht Probabilistische Protokolle erreichen deutlich weniger „bestes“ Protokoll: Adapt 5

Fluten

Prob 20%

Prob 40%

Prob 60%

Prob 80%

Adapt 5

Adapt 6

Adapt 7Adapt 8

Adapt 9

0

5

10

15

20

0 200 400 600 800 1000 1200 1400 1600 1800 2000

Erreichte Knoten

Na

ch

ric

hte

n je

err

eic

hte

n K

no

ten


Area Graph basiertes Bewegungsmodell

Area Graph mit 4 Knoten und 4 Kanten

Größe eines Ballungszentrums

● 200 x 200 m („klein“)

● 300 x 300 m („groß“)

Verweildauer innerhalb eines Knotens

● 300 - 700 s („kurz“)

● 1000 - 1400 s („lang“)

200m 200m,

300m 300m

500m50 %

50 %

500m50 %

50 %

500 m50 %

50 %

500m50 %

50 %

200m 200m,

300m 300m

200m 200m,

300m 300m

200m 200m,

300m 300m


Ergebnisse Area Graph „klein“/„kurz“

Bei kleinen Ballungsräumen und kurzer Verweildauer:

Adaptive Protokolle deutlich besser als Probabilistische

„bestes“ Protokoll: Adapt 9

Fluten

Prob 20%

Prob 40%

Prob 60%

Prob 80%

Adapt 5Adapt 6

Adapt 7Adapt 8

Adapt 9

0

5

10

15

20

25

30

0 200 400 600 800 1000 1200 1400 1600 1800 2000

Erreichte Knoten

Na

ch

ric

hte

n je

err

eic

hte

n K

no

ten


Ergebnisse Area Graph „klein“/„lang“

Fluten

Prob 20%

Prob 40%

Prob 60%

Prob 80%

Adapt 5Adapt 6

Adapt 7Adapt 8

Adapt 9

0

5

10

15

20

25

30

0 200 400 600 800 1000 1200 1400 1600 1800 2000

Erreichte Knoten

Na

ch

ric

hte

n je

err

eic

hte

n K

no

ten

Bei großen Ballungsräumen (kleinere Dichte):

ähnliche Ergebnisse wie bei kleinen Ballungsräumen

Bei kleinen Ballungsräumen und langer Verweildauer:

maximal 70% der Knoten erreicht

„bestes“ Protokoll: Adapt 9


Gliederung

Motivation


Bewegungsmodelle




Zusammenfassung

Neues Bewegungsmodell: Area Graph basiert● realistischer als Random Waypoint

● relevant, da Ergebnisse qualitativ abweichen

Neuer Verteilungsalgorithmus: Adaptives Probabilistisches Fluten● nutzt Wissen über Anzahl der Nachbarn aus

● effizienter als Probabilistisches Fluten

● besonders bei Übergängen Cluster <-> Weg geeignet


Ausblick

Validierung durch theoretische Ergebnisse Theoretisches Modell für das Area Graph basierte Bewegungsmodell

Weitere Untersuchungen:● Nachbarschaftsbasierte Verfahren

● sehr dünn besiedelter Gebiete (Rebroadcast nötig?)

● Ortsbasierte Methoden


Vielen Dank für Ihre Aufmerksamkeit

Fragen?

Documents

Datenverteilung in Ad-hoc Netzen 1/24 Adaptive Datenverteilung in mobilen Ad-hoc Netzen unter Verwendung des Area Graph basierten Bewegungsmodells S. Bittner,