Distributed biconnectivity testing in Wireless multi-hop networks [Elektronische Ressource] / von Bratislav Milic

Dipl.-Ing. Bratislav Milic

Sujets

• Physik

Informations

• Publié par: humboldt-universitat_zu_berlin
• Publié le: 01 janvier 2010
• Nombre de lectures: 13
• Langue: English
• Poids de l'ouvrage: 6 Mo

Extrait

Distributed Biconnectivity Testing in Wireless Multi-hop
Networks
DISSERTATION
zur Erlangung des akademischen Grades
Doktor-Ingenieur (Dr.-Ing.)
im Fach Informatik
eingereicht an der
Mathematisch-Naturwissenschaftlichen Fakultät II
Humboldt-Universität zu Berlin
von
Dipl.-Ing. Bratislav Milic
24.07.1978 in Belgrad
Präsident der Humboldt-Universität zu Berlin:
Prof. Dr. Christoph Markschies
Dekan der Mathematisch-Naturwissenschaftlichen Fakultät II:
Prof. Dr. Peter Frensch
Gutachter:
1. Prof. Dr. Edgar Nett
2. Prof. Dr. Alexander Reinefeld
3. Prof. Dr. Miroslaw Malek
eingereicht am: 01.09.2009
Tag der mündlichen Prüfung: 04.12.2009First and foremost I would like to thank my supervisor, Professor Miroslaw Malek, for
his continued support throughout my work at the Humboldt University. My thanks also
go to all the colleagues for useful comments and fruitful discussions.
This work would not be possible without the understanding, patience, support and love
of my family.Abstract
Wireless multi-hop network (WMN) is a distributed communication system com-
posed of autonomous processing nodes that is known for its ability to automatically
adjusttorapidlychangingconditionsin the surrounding environment. Connectivity
is one of the basic properties of a network. Removal of a bridge or an articulation
point partitions a network. Biconnectivity testing identifies bridges and articula-
tion points in a network, and once they are known corrective actions can be per-
formed in order to improve network’s reliability. Numerous biconnectivity testing
algorithms are successfully applied in graphs, wired networks and multiprocessor
systems. However, they are inadequate for application in wireless networks since
the frequent packet losses introduce uncertainty in the system which these algo-
rithms cannot handle. The stochastic analysis shows that errors in decision-making
in WMNs are considerable even for seemingly simple tasks such as the detection of
links.
The main contribution of this work is to provide means for accurate binary
decision-making under uncertainty within the context of biconnectivity testing in
WMNs. A distributed algorithm is developed that successfully handles the faults
caused by message losses and simultaneously utilizes benefits of wireless commu-
nication to reduce message complexity from O(e) to O(n). Based on stochastic
analysis of WMN topologies and a comprehensive analysis of impact of communi-
cation faults on algorithm’s behavior, the algorithm is extended by voting theory
to reduce probability of erroneous decisions.
TheWMNsinBerlinandLeipzigareusedasthecasestudy. Topologicaldatacol-
lected in them demonstrates that real networks are composed of dense and sparse
parts, and confirms existence of numerous bridge and articulation points. The
known node-placement algorithms are unable to recreate these properties so a new
node placement algorithm for realistic topologies in WMN simulation was devel-
oped.
The algorithm and the voting rules are evaluated in experiments in Motelab
testbed and in the event-based simulator Jist/SWANS. The algorithm is accurate
under various conditions which demonstrates its applicability in reality and capa-
bility of successful operation in presence of packet losses.
vZusammenfassung
Ein drahtloses Multihop-Netzwerk (DMN) ist ein verteiltes Kommunikationssys-
tem aus autonomen Verarbeitungsknoten, welches vor allem die Fähigkeit zur au-
tomatischen Anpassung an sich ständig änderne Umgebungsbedingungen hat. Eine
zentrale Fragestellung in DMNen ist, ob das Netzwerk partitioniert ist, ob also nicht
mehr jeder Knoten mit jedem anderen Knoten kommunizieren kann. Um festzu-
stellen, ob eine Partitionierung droht werden mit Hilfe von 2-Zusammenhangstests
Brücken und Artikulationspunkte im Kommunikationsgraphen gesucht. Daraufhin
können anschließend korrektive Aktionen eingeleitet werden um die Partitionierung
zu verhindern und somit die Netzwerkverfügbarkeit zu erhöhen. Eine Vielzahl von
2-Zusammenhangstestverfahren wurde bereits erfolgreich bei drahtgebundenen Net-
zen eingesetzt. Allerdings sind diese Verfahren ungeeignet für drahtlose Netze, da
die Ungenauigkeiten durch den häufigen Paketverlust in solchen Systemen bisher
nicht berücksichtigt wurden. Mit Hilfe von stochastischen Modellen wird gezeigt,
dass Fehler in der Entscheidungsfindung für DMNen bereits bei sehr einfachen Pro-
blemen wie der Link-Erkennung signifikant sein können.
In dieser Arbeit werden daher verschiedene Verfahren präsentiert, die auch auf
Grundlage unsicherer Informationen noch eine verlässliche Entscheidungsfindung
ermöglichen. Die Arbeit präsentiert einen neuen verteilten Algorithmus zum Test
auf 2-Zusammenhang, welcher Fehler durch Nachrichtenverlust berücksichtigt und
gleichzeitig die Anzahl an Nachrichten reduziert. Basierend auf einer umfassenden
Analyse der Einflüsse von Kommunikationsfehlern auf den Algorithmus, wurden
Abstimmungsprozeduren entwickelt, die die Wahrscheinlichkeit von Fehlentschei-
dungen nochmals reduzieren.
Eine Fallstudie mit öffentlichen DMNen in Berlin und Leipzig hat die Existenz
zahlreicher Brücken und Artikulationspunkte in echten Netzwerken bestätigt. Da
keiner der bekannten Algorithmen zur Erzeugung von Topologien in simulierten
DMNen zu annähernd realistischen Ergebnissen führt, wird ein neuer Algorithmus
vorgestellt.
Zur weiteren Analyse werden die Algorithmen erstens in der Motelab-Umgebung
und zweitens mit Hilfe von Simulationen untersucht. Die präsentierten Algorithmen
zeigen überzeugende Ergebnisse unter variierenden Bedingungen, was ihre Anwend-
barkeit in realen Szenarien unterstreicht.
viiContents
1. Introduction 1
1.1. Wireless Multi-hop Networks . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3. Problem Statement and Goals . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4. Structure of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2. Background 11
2.1. Modeling of Wireless Multi-hop Networks . . . . . . . . . . . . . . . . . 11
2.1.1. Node Placement Models . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.2. Mobility Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.3. Wireless Signal Propagation Models . . . . . . . . . . . . . . . . 16
2.1.4. Medium Access Control Sublayer . . . . . . . . . . . . . . . . . . 18
2.2. Graph as a Wireless Multi-hop Network Model . . . . . . . . . . . . . . 19
2.2.1. What is Topology of a Wireless Multi-hop Network? . . . . . . . 20
2.2.2. Graph Theory Basics . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.3. Random Geometry Graphs . . . . . . . . . . . . . . . . . . . . . 22
2.2.4. Planarization of Random Geometric Graphs . . . . . . . . . . . . 23
2.3. Simulators, Emulators and Testbeds - Their Benefits and Drawbacks . . 26
2.4. Accuracy Metrics of Biconnectivity Testing Algorithm . . . . . . . . . . 27
3. Related Work 31
3.1. Biconnectivity Testing in Wireless Multi-hop Networks . . . . . . . . . . 32
3.2. Other Approaches for Circumvention of Network Partitioning or Its Effects 33
3.2.1. Topology Control . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.2. Partitioning Prevention by Mobility . . . . . . . . . . . . . . . . 36
3.2.3. Disruption-Tolerant Networks . . . . . . . . . . . . . . . . . . . . 36
3.3. Proactive Topology Management in WMNs . . . . . . . . . . . . . . . . 37
3.3.1. Link Detection in Wireless Multi-hop Networks . . . . . . . . . . 39
3.3.2. Local Topology Dissemination . . . . . . . . . . . . . . . . . . . 41
3.4. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4. Heartbeat-Based Link Status Detection in Wireless Multi-hop Networks 45
4.1. Heartbeat Link Detector Model . . . . . . . . . . . . . . . . . . . . . . . 45
4.2. Analysis of Heartbeat Link Detector Behavior in Static Networks . . . . 47
4.2.1. Heartbeat Link Detector at a Link without Node Failures . . . . 48
4.2.2.eat Link Behavior in a Network . . . . . . . . . 51
4.3. Node Failures and Limited Duration of Link Existence . . . . . . . . . . 56
4.4. Effects of HLD Errors on Proactive Topology Management Protocols . . 63
4.5. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
ixContents
5. Distributed Bridge and Articulation Point Detection Algorithm for Wireless
Networks (DIBADAWN) 67
5.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.2. Biconnectivity Testing Algorithms in Context of Wireless Multi-hop Net-
works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.3. Adaptation of the Echo Algorithms for Application in WMNs . . . . . . 74
5.4. Distributed Biconnectivity Testing in WMNs . . . . . . . . . . . . . . . 76
5.4.1. Execution Issues of Echo Algorithms in WMNs . . . . . . . . . . 83
5.4.2. Analysis of the Communication Overhead . . . . . . . . . . . . . 85
5.5. Algorithm Behavior in Presence of Packet Losses and Node Failures . . 87
5.5.1. Analysis of Faults, Errors and Failures of the Detection Algorithm 88
5.5.2. Ex