View source for Auswertung der Delivery Ratio Messung

== Zusammenfassung Aussagen ==

* Einfluss der Umgebung muss mit betrachtet werden
** Man kann nicht 'auf der grünen Wiese' anfagen mit der Kanalzuweisung. Es spielen immer die konkreten Umgebungsbedingungen eine Rolle.
* Im Ein-Kanal-Fall spielt die Kanalwahl eine bedeutende Rolle
** Differenz von 24% Node Delivery Ratio zwischen 'guter' und 'schlechter' Kanalwahl.
* Verwendung mehrerer Kanäle in einem Netz kann weitere Vorteile bringen
** Steigerung der Node Delivery Ratio um 10% gegenüber Ein-Kanal-Fall
* Asymetrie der Links hat praktische Relevanz
** Bestehende Protokolle und Metriken gehen nur schlecht mit (stark) asymetrische Links um (Beispiel ETX)
** ExOR [2,3]

== Begriffe ==
 
=== forward delivery ratio <math>d_f</math> === 
... is the measured probability that a data packet successfully arrives at the recipient [1]

=== reverse delivery ratio <math>d_r</math> ===
... is the probability that the ACK packet is successfully received [1]

=== (Forward) Delivery Ratio Symmetry ===

... ist ein Maß zur Beurteilung der Symetrie eines Links.

<math>d_{sym}(i,j) = Min( d_f(i,j)/d_f(j,i), d_f(j,i)/d_f(i,j) )</math> nach [4] (Wenn <math>d_f(j,i)</math> und <math>d_f(i,j)</math> beide Null, dann <math>d_{sym}</math> undef.)

=== (link) delivery ratio <math>d</math> ===

... is the expected probability that a transmission is successfully received and acknowledged [1].

<math>d = d_f * d_r</math>

=== (node) delivery ratio <math>nd</math> ===

... is the average of the delivery ratios of the nodes links. Imagine a node with links <math>l_1</math> ... <math>l_n</math> with <math>n = NetworkSize - 1</math> (all links are considered)

<math>nd(n) = 1/k * \sum_{k} d(l_k)</math>.

<font color=red>A.:</font> Wir müssen einen Schwellwert einführen, da ansonsten die Aussagen nicht sinnvoll sind. Z.B. man betrachtet lediglich
Links mit einer M > eps; wobei eps z.B. 0,3 oder so ist.

== Berlin RoofNet ==

Vorstellen, Hardware, Software


Hier können wir den Kram aus unserem anderen Paper nehmen.

[[Image:Indoor_2d.PNG]]

== Messdaten ==

In den Messungen vom 15.11.2005 und 25.12.2005 wurden die (mittleren) Delivery Ratios im Indoor-Testbed gemessen. Vorgehen:
* Jeder Knoten sendet in festen Zeitabständen sog. Link-Probe-Requests einer bestimmten Größe (60, 120 und 1000 Byte) mit einer bestimmten Rate (1, 2, 5.5, 11) auf einem gegebenen Kanal (1 bis 14) als Broadcast. 
*Ein empfangender Knoten zählt die empfangenen Probes seiner Nachbarn und berechnet die entsprechenden Delivery Ratios. 
* Diese werden in regelmäßigen Abständen extern abgefragt und über die Zeit gemittelt.
* 25.12.2005: Messung wurde mehrfach wiederholt, lief vom 15.12.2005 bis 25.12.2005

<font color="red">Bild Teppich oder ähnliches</font>
<font color="red">Messung 15.11.2005</font>

<font color="red">Hier die genauen Parameter angeben (über welchen zeitraum wird gemittelt, ...).</font>

== Beobachtungen ==

* Delivery Ratio eines Links ist abhängig vom Kanal.
[[Bild:20051225_delivery_ratio.png|800px|thumb|none|Delivery Ratio d in Abhängigkeit des Kanals für die Messung vom 25.12.2005 (Rate 11Mbit/s, Probe-Größe 1000Byte)]]

[[Bild:20051225_d.png|800px|thumb|none|Delivery Ratio d in Abhängigkeit des Kanals für die Messung vom 25.12.2005 (Rate 11Mbit/s, Probe-Größe 1000Byte, 0er-Links weggelassen)]]

Es gibt 'gute' Links mit hoher Delivery Ratio und geringer Standardabweichung, 'schlechte' Links mit geringer Delivery Ratio und Standardabweichung und einen Übergangsbereich mit Links mittlerer Delivery Ratio und hoher Standardabweichung. In dieser dritten Klasse sind Links zu finden, die auf bestimmten Kanälen eine hohe Delivery Ratio haben, während sie anderen Kanälen praktisch nicht existieren. 

[[Bild:20051225_d_avg_std.png|800px|thumb|none|Mittelwert und Standardabweichung der Delivery Ratio d über alle Kanäle hinweg (Messung vom 25.12.2005, Rate 11Mbit/s, Probe-Größe 1000Byte, Links mit Delivery Ratio 0 weggelassen).]]

* Bestimmte Links sind sehr asymetrisch, d.h die Differenz aus Forward und Reverse Delivery Ratio ist groß.
[[Bild:20051225_diff_df_dr.png|800px|thumb|none|Differenz von Forward und Reverse Delivery Ratio in Abhängigkeit vom Kanal (Messung vom 25.12.2005, Rate 11Mbit/s, Probe-Größe 1000Byte).]]

<font color=red>Frage</font> Wie stabil waren die Messungen über die Zeit? Varianz.

<font color=red>std über die gemessenen tupel (timeline) in abh. von link (konst. channel size, rate)</font>

=== Links ===

<font color=red>timeline für ausgewählte links (konst. channel size, rate)</font>

* Link wgt34 -> wgt55 (wgt55 -> wgt34)
* Link wgt34 -> wgt44
** Link bei 11Mbit/s und Size 1000Byte nicht vorhanden (keine Messwerte)
* Link wgt52 -> wgt21

[[Bild:20051225_timeline_wgt52_wgt21.png]]

* Asymetrie von Links
** (Forward) Delivery Ratio Symmetry <math>d_{sym}(i,j) = Min( d_f(i,j)/d_f(j,i), d_f(j,i)/d_f(i,j) )</math> nach [4] (Wenn <math>d_f(j,i)</math> und <math>d_f(i,j)</math> beide Null, dann <math>d_{sym}</math> undef.)

[[Bild:20051225_d_sym.png|800px|thumb|none|Histogram Delivery Ratio Symmetry für alle Paare (i,j), für die <math>d_{sym}(i,j)</math> definiert ist (Messung vom 25.12.2005, Rate 11Mbit/s, Probe-Größe 1000Byte).]]

[[Bild:20051225_d_sym_chan.png|800px|thumb|none|Histogram Delivery Ratio Symmetry für alle Paare (i,j), für die <math>d_{sym}(i,j)</math> definiert ist, in Abhängigkeit des Kanals (Messung vom 25.12.2005, Rate 11Mbit/s, Probe-Größe 1000Byte).]]

<font color="red"> Korellation Distance - Delivery Ratio ?? </font>

=== Ursachen ===

* Innerhalb/durch das Netz selbst
** Topologie
** Entfernung zw. Knoten
** Hardware
** ...
* Umwelt 
** Andere Accesspoints
** physiche Struktur der Umwelt: Wände, Blätter, usw.
** Mikrowellen
** ...

== Konsequenzen ==

=== Kanalwahl hat Einfluss auf die Leistung des Netzes ===

* <font color="red">Hinweis:</font> Zusätzlich wurde der eigentlich nicht erlaubte Kanal 14 gewählt, um den Einfluss von fremden APs zu minimieren.

Wenn alle Knoten des Netzes den gleichen Kanal verwenden, hat die Wahl dieses Kanals Einfluss auf die Delivery Ratios und damit auf die Gesamtleistungsfähigkeit. Wird beispielsweise der Kanal 14 verwendet, ergibt sich eine mittlere Node Delivery Ratio von 0.25, währenddessen auf Kanal 9 nur 0.13 erreicht werden (Differenz zwischen Maximum und Minimum 0.12 oder 48% des Maximums).

[[Bild:20051225_nd_netcolor.png|800px|thumb|none|Mittlere Node Delivery Ratio in Abhängigkeit des Kanals für die Messung vom 25.12.2005 (Rate 11Mbit/s, Probe-Größe 1000Byte)]]

=== Benutzen von verschiedenen Kanälen bringt weitere Vorteile ===

Charakteristik eines zugrundeliegenden MAC- bzw. Routing-Protokolls:
* Jeder Knoten empfängt auf einem ihm zugewiesenen 'Heimatkanal'
* Link-Level Acknowledgements auf dem gleichen Kanal (Unicast-Traffic)
* Beim Senden wechselt der Knoten auf die Frequenz des Empfängers

Auf Grundlage der ermittelten Node Delivery Ratios lässt sich eine Kanalzuordnung finden, die die mittlere Node Delivery Ratio maximiert (Greedy in Linearzeit). Auf gleiche Weise kann eine schlechte Zuordnung ermittelt werden, die die mittlere Node Delivery Ratio minimiert. Die folgende Tabelle zeigt eine solche Zuordnung:

[[Bild:20051225_nd_nodecolor_tab.png]]

[[Bild:20051225_nd_nodecolor.png|800px|thumb|none|Mittlere Node Delivery Ratio in Abhängigkeit des Kanals für die Messung vom 25.12.2005 (Rate 11Mbit/s, Probe-Größe 1000Byte)]]

Ein positiver Nebeneffekt der Benutzung mehrerer Kanäle ist die (potentielle) Reduzierung der Interferenz-Erscheinungen. Allerdings kann die Wirkung einer solchen Reduzierung mit den Delivery Ratio Messungen nicht bestimmt (quantfiziert) werden. 

==== Reduzierung der Interferenz-Erscheinungen durch eine geeignete Kanalzuweisung ====

* Nebenbedingung 1: Benachbarte Knoten dürfen nicht den gleichen Kanal benutzen. 
** Berechung in Exponentialzeit, evtl. Approximation durch geeignete Heuristiken.
** Evtl. keine Lösung, da die Bedingung zu streng.
** Problem: Der Effekt der Reduzierung lässt sich mit der vorgestellten Messungen nicht bestimmen.
* opt. Lockerung der Bedingung 1: Gleiche Faerbung benachbarter Knoten wird bestraft. 
* opt. Nebenbedingung 2: Interferenz-Kanten als Ausdruck der Nachbar-Nachbar-Beziehung (Idee: Interferenzbereich ist i.A. groesser als der Empfangsbereich)

Fazit: Interferenz- und Qualitätsoptimale Lösungen existieren möglich, 
allerdings ist der dadurch entstehende, quantitative Vorteil (mit bisherigen Mitteln) nicht bestimmbar.

=== Vorteile der bewussten Benutzung asymetrischer Links ===

* Bestehende Protokolle nutzen die Asymetrie eines Links unzureichend aus (eigentlich können sie gar <font color="red">NICHT</font> damit umgehen)
** 802.11-ähnliche Protokolle mit Link-Level-Acknowledge müssen den Link in beide Richtung traversieren (Achtung: Bitraten für Daten/ACK müssen nicht gleich sein). Daher ist die Betrachtung der Link Delivery Ratio

* ExOR [2, 3] 
** "is able to use long links that are asymmetric"
** Batch maps flow back to the source on different path than the data packets.
** "Traditional routing, in contrast, avoids these asymmetric links because ETX takes link-level ACK losses into account."


Charakteristik eines zugrundeliegenden MAC- bzw. Routing-Protokolls:
* Keine Link-Level-Acknowledgments 
* (Jeder Knoten empfängt auf einem ihm zugewiesenen 'Heimatkanal')?  <font color="red">für ExOR nicht zutreffend</font>
* (Beim Senden wechselt der Knoten auf die Frequenz des Empfängers)? <font color="red">für ExOR nicht zutreffend</font>

<font color="red">Lassen sich unter diesen Annamhen brauchbare Diagramme erstellen?</font>

== Probleme / Offene Punkte / Out of Scope ==

* Wie die Delivery Ratios im laufenden Betrieb bestimmen/aktualisieren 
** Koennen die Daten im laufenden Betrieb erhoben werden (dynamische Anpassung) oder ist nur eine statische Konfiguration des Systems moeglich?
* Kosten des Kanalwechsel und dessen Einfluss auf die resultierende Leistung
* Entwurf eines Multichannel MAC/Routing-Protokolls, dass diese Erkenntnisse berücksichtigt
* Gibt es noch anders charakterisierte Multichannel-Protokolle (siehe Punkt Konsequenz), für die sich die Berechnung anders gestaltet.
** Beispielsweise fuehrt das ACK auf gleichem Kanal dazu, dass nicht nur die Forward sondern die aggregierte Delivery Ratio betrachtet werden muessen. Dadurch kann eine potentielle Asymetrie eines Links nicht ausgenutzt werden.

== References ==

* [1] De Couto, Aguayo, Bicket, Morris: "A HighThroughput Path Metric for MultiHop Wireless Routing", 2003, [http://pdos.csail.mit.edu/papers/grid:mobicom03/paper.pdf]
* [2] Biswas, Morris: "Opportunistic Routing in Multi-Hop Wireless Networks", 2003, [http://pdos.lcs.mit.edu/papers/roofnet:exor-hotnets03/roofnet_exor-hotnets03.pdf]
* [3] Biswas, Morris: "Opportunistic Routing in Multi-Hop Wireless Networks", 2005, [http://www.pdos.lcs.mit.edu/papers/roofnet:exor-sigcomm05/roofnet_exor-sigcomm05.pdf]
* [4] Kotz, Newport, Elliott: "The mistaken axioms of wireless-network research", 2003, [http://pdos.csail.mit.edu/decouto/papers/kotz03.pdf]
* [5] Ganesan, Krishnamachari, Woo, Culler, Estrin, Wicker: "Complex behavior at scale: An experimental study of low-power wireless sensor networks", Technical Report
UCLA/CSD-TR 02-0013, UCLA Computer Science, 2002.[http://lecs.cs.ucla.edu/%7Edeepak/PAPERS/empirical.pdf]