Project topics and materials
Get Complete Project Material File(s) Now! »
Properties of Ad Hoc Networks
Ad hoc networks have the following main attributes:
Dynamic topology: A particularity of ad hoc networks is the dynamic topology of the network. Links between routers may change dynamically { due to router mobility, or other factors in uencing link stability such as environmental changes, obstacles, etc. { and with a higher frequency than in classic, wired networks. At a given point in time, depending on the mobile routers’ positions and stability of the wireless link between two adjacent routers, a wireless connectivity in the form of a random, multi-hop graph or \ad hoc » network exists between the routers [10].
Wireless radio characteristics: In addition to the dynamism of the topology, the following properties of the wireless radio medium a ect the topology of the network: asymmetry and non-transitivity of links. Asymmetry means that, unlike on a wired link (i.e. a cable), the fact that a router A \hears » a router B does not necessarily imply the inverse, as depicted in gure 1.6(a).
Furthermore, transitivity is not guaranteed in ad hoc networks. In gure 1.6(b), three routers A, B and C are depicted, each of them equipped with a wireless interface. Non-transitivity means that router A cannot \hear » C, even though A can hear B, and B can hear C.
Infrastructureless: Typically, no centralized infrastructure exists in ad hoc networks, such as access points in classic networks. Even if a \central » router exists in an ad hoc network, communication between that central router and each other router in the network cannot be guaranteed due to the dynamic topology. Autonomy: Ad hoc networks are \autonomous », i.e. routers do not need any a priori con guration. All parameters required for establishing communication, such as for the routing protocol, are negotiated between the routers by a message exchange [10].
FunkFeuer Community Ad Hoc Network
One example of operational ad hoc networks are community networks in Europe, such as the FunkFeuer [11] network in Vienna, Austria. FunkFeuer is a public, non-regulated, community network allowing inhabitants of Vienna to connect to each other and { through an uplink to an ISP { to the Internet for no fee, other than the initial purchase of a wireless router. Funk-Feuer comprises several hundred routers [11], many of which have several radio interfaces (with omnidirectional and some directed antennas)2. The routers of the network are small-sized wireless routers, such as the Linksys WRT54GL, available in 2011 for less than 50 Euros. These routers, with 16 MB of RAM and 264 MHz of CPU power, are mounted on the rooftops of Vienna, as depicted in gure 1.7.
When new users want to connect to the network, they have to acquire a wireless router, install the appropriate rmware and routing protocol, and mount the router on the rooftop. IP address(es) for the router are assigned manually from a list of addresses.
This network is not intended for testing purposes, and there is no \operator » or \maintainer » having remote access to the routers once installed, which requires the routers to be completely autonomous. Figure 1.8 depicts the network topology of the FunkFeuer network as of July 23, 2010. The network covers a large area of central Vienna, and via some directed links, also some suburbs further away from the city center. While the routers are non-mobile, uctuations in link quality require an ad hoc routing protocol that allows for quick convergence to re ect the e ective topology of the network. Similar community network deployments are situated, e.g., in Berlin [12], Athens [13] and Seattle [14].
As of 2011, the routing protocol that operates on FunkFeuer routers is unsecured. Therefore, the users of the network have to trust that nobody harms the network integrity (intentionally or otherwise).
Ad Hoc Networks in Emergency Situations
Establishing basic communication after an emergency such as a ood, earthquake or nuclear accident, is di cult when the communication infrastructure is damaged. Mobile phones require nearby infrastructure that provide connectivity, which may not work any more. Even if the infrastructure is still available, the increased use of mobile phones after an emergency can saturate the network. The cable telephone network may be malfunctioning when cables are broken, satellite phones are rarely available and expensive.
In addition to voice communication, data collection on the emergency site is desirable. In-formation, such as temperature, humidity or radioactivity of the disaster area, can help under-standing the degree of the disaster, and to coordinate help accordingly. [15, 16, 17, 18] describe di erent such deployments, establishing communication in emergency situations. To pick one example, the SKYMESH project of Niigata University [15], is aimed at establishing communi-cation between several unmanned balloons (as depicted in gure 1.9) in order to rapidly create communication networks for rescuers. A small computer, together with a GPS device and a camera, is attached to the balloon, which oats in a height of 50 to 100m over ground, allowing remote wide area monitoring of the disaster area, as well as establishing communication (voice or data) using the ad hoc network.
Another deployment in emergency situations is to drop large numbers of sensors from an airplane. The sensors can then establish an ad hoc network, once they are on the ground, without the necessity for humans to enter the disaster site and to deploy the sensors manually.
Wireless Sensor Networks
The general context for Wireless Sensor Networks (WSNs) is small, cheap devices whose primary function is data acquisition, with communications capabilities enabling them to send data to a controller, using a wireless multi-hop topology. As an example, a WSN deployed for environmen-tal monitoring might contain a set of temperature sensors, sending \noti cations » to a central controller when the temperature exceeds certain thresholds. Compared to a network of wired sensors, WSNs o er the advantage of enabling mobility to sensors, as well as reducing cost and space requirements for the installation of cables. The properties of WSNs are similar to the ad hoc network presented in section 1.3.1, with the following di erences: (1) hardware resources (in terms of CPU and memory) of sensor routers are even more constrained than ad hoc routers in the FunkFeuer network, (2) unlike the routers in the FunkFeuer network, sensor routers may be battery driven, and (3) sensor network topologies are often optimized for particular tra c patterns.
Table of contents :
I Introductory Part
1 Introduction
1.1 Classic Networks
1.2 Highly Dynamic Core
1.2.1 Properties of Ad Hoc Networks
1.3 Use Cases
1.3.1 FunkFeuer Community Ad Hoc Network
1.3.2 Ad Hoc Networks in Emergency Situations
1.3.3 Wireless Sensor Networks
1.4 Challenges of Ad Hoc Networks
1.5 Standardization in the Internet Engineering Taskforce
1.5.1 MANET Working Group
1.5.2 AUTOCONF Working Group
1.5.3 ROLL Working Group
1.6 Contributions and Structure of the Manuscript
2 Simulation Toolchain
2.1 Chapter Outline
2.2 The NS2 Simulator
2.3 Scenario Generation Tools
2.3.1 Wsg { The Scenario Generator
2.3.2 create-multiple-runs.sh
2.4 NS2 Tools
2.5 Evaluation Tools
2.5.1 NS2stats.awk
2.5.2 plot.rb and result.rb
2.5.3 stats.plot
2.6 Typical Work ow of a Simulation and Evaluation
2.6.1 Generating the Scenario Files
2.6.2 Running the Simulation
2.6.3 Performing Statistics
2.6.4 NS2 Trace File Visualizer
2.7 Conclusion
3 Framework for Supporting Java NS2 Routing Protocols (AgentJ)
3.1 Chapter Outline
3.2 Related Work
3.3 AgentJ Overview without Routing Functionalities
3.4 Architectural Modications of AgentJ for Support of Routing Protocols
3.4.1 Overview
3.4.2 Detailed Description
3.5 Performance Comparison
3.6 Advantages of AgentJ Routing Framework
3.7 Conclusion
II General Architectural Considerations of Ad Hoc Networks
4 Architectural Considerations of Ad Hoc Networks
4.1 Chapter Outline
4.2 What is an IP Address?
4.2.1 The Basics
4.2.2 Networks
4.2.3 Prexes { the Internet Term for Intervals
4.2.4 Delegation and Assignment
4.3 The MANET Architecture
4.3.1 The Classic IP Link Model
4.3.2 The Missing Link
4.3.3 /32 and /128 Prex Lengths
4.3.4 Denition of a MANET Router
4.3.5 `M’ for Mobility { `A’ for Ad hoc
4.4 Connected vs. Disconnected MANETs
4.4.1 On why these Terms are Misleading
4.4.2 On why these Terms are Unfortunate
4.4.3 A Better Taxonomy
4.5 AUTOCONF { The Goals
4.5.1 Architectural Considerations
4.5.2 Acquiring a Prex in an Autonomous MANET
4.5.3 Acquiring a Prex in a Subordinate MANET
4.5.4 Consequences
4.6 Automatic Conguration in the Internet
4.6.1 Dynamic Host Conguration Protocol (DHCP)
4.6.2 Stateless Autoconguration / Neighbor Discovery Protocol
4.6.3 IP Architecture Assumptions
4.7 Internet vs MANETs
4.7.1 Dierent Link-Model of MANETs
4.7.2 Routers vs. Hosts
4.7.3 Mobility in MANETs
4.7.4 Relationship between MANET Routers
4.8 Conclusion
5 Yet Another Autoconf Proposal (YAAP) for MANETs
5.1 Chapter Outline
5.2 Related Work
5.3 MANET Autoconguration Mechanism
5.3.1 Algorithmic Overview
5.3.2 Formal Protocol Specication
5.3.3 Autoconguration Example
5.4 Extensions and Optimizations
5.4.1 Proxying
5.4.2 Unicast RAs
5.4.3 Optimized Broadcasting
5.4.4 Periodical Prex Propagation
5.4.5 IPv4 vs. IPv6
5.4.6 Initiator Selection
5.5 Additional Considerations
5.5.1 Duplicate UUIDs
5.5.2 No Initiator Router
5.5.3 Initiator Proxying
5.6 Formal Validation using a Model Checker
5.6.1 Assumptions and Simplications of the Model
5.6.2 Results of Verication of Properties in UPPAAL
5.7 Simulation
5.7.1 Simulation Results
5.8 Conclusion
III OLSRv2 Performance and Scalability
6 OLSRv2 Overview
6.1 Chapter Outline
6.2 Classic Link State Protocol
6.2.1 Neighborhood Discovery
6.2.2 Link State Advertisements
6.2.3 Classic Flooding (CF)
x CONTENTS
6.2.4 Shortest Path Calculation
6.3 OLSRv2
6.3.1 Neighborhood Discovery (NHDP)
6.3.2 MPR Flooding (MPRF)
6.3.3 Link State Advertisement
6.3.4 Flexible Message Format
6.3.5 Inherent Protocol Extensibility
6.4 Conclusion
7 Java OLSRv2 Implementation
7.1 Chapter Outline
7.2 Architecture Overview
7.2.1 Packetbb
7.2.2 NHDP
7.2.3 OLSRv2
7.3 RMI GUI Client
7.4 Logging API
7.5 Routing API for other Operating Systems
7.6 Writing Extensions
7.7 Interoperability Tests
7.7.1 Packetbb Tests
7.7.2 Packetbb Applets
7.7.3 Emulator for large Topologies
7.7.4 NHDP Tests
7.7.5 OLSRv2 Tests
7.7.6 Packetbb Interoperability Test Results
7.7.7 Network Emulation using CORE
7.7.8 Remote Tests
7.8 Conclusion
8 Dynamic Shortest Path Algorithm in OLSRv2
8.1 Chapter Outline
8.2 Related Work
8.3 Routing Set Updates in OLSRv2
8.4 Test Methodology
8.4.1 Topology Emulator
8.4.2 OLSRv2 Implementation
8.4.3 Time Measurement
8.5 Evaluation
8.6 Incremental Route Updates
8.6.1 Evaluation Settings
8.6.2 Results
8.7 Conclusion
9 OLSRv2 Network Management and Performance Monitoring
9.1 Chapter Outline
9.2 OLSRv2 Router Conguration
9.3 A Brief SNMP Primer
9.4 Related Work
9.5 Problem Statement: Managing OLSRv2 Networks
9.6 OLSRv2 Management Architecture
9.7 NHDP and OLSRv2 MIBs
9.8 Performance Management
9.8.1 Object Types
9.8.2 Derived Objects in NHDP and OLSRv2
9.9 Performance Study of SNMP in OLSRv2 MANETs
9.9.1 Simulation Settings
9.9.2 Simulation Results
9.10 Conclusion
10 Delay Tolerant Routing with OLSRv2
10.1 Chapter Outline
10.2 Link Buer Mechanism
10.2.1 IP Buering
10.2.2 L2 Buering
10.2.3 Flow Chart
10.2.4 Buering at Intermediate Hops
10.3 Model Description
10.4 Performance Evaluation
10.4.1 God Routing Protocol
10.4.2 Graceful Shutdown
10.4.3 Simulation Settings
10.4.4 Simulation Results
10.5 Conclusion
11 Vulnerability Analysis of OLSRv2
11.1 Chapter Outline
11.2 Related Work
11.3 Overview
11.3.1 Link State Vulnerability Taxonomy
11.3.2 OLSRv2 Attack Vectors
11.4 Topology Map Acquisition
11.4.1 Flooding Disruption
11.4.2 Radio Jamming
11.4.3 Attack on Jittering
11.4.4 Hop Count and Hop Limit Attacks
11.5 Eective Topology
11.5.1 Incorrect Forwarding
11.5.2 Wormholes
11.5.3 Sequence Number Attacks
11.5.4 Message Timing Attacks
11.5.5 Indirect Jamming
11.6 Inconsistent Topology
11.6.1 Identity Spoong
11.6.2 Link Spoong
11.6.3 Creating Loops
11.7 Replay Attacks
11.8 Inherent OLSRv2 Resilience
11.9 Conclusion
12 Router and Link Admittance Control in OLSRv2
12.1 Chapter Outline
12.2 Problem Statement
12.3 Router Admittance Control
12.3.1 Resilience Evaluation
12.4 Link Admittance Control
12.5 Protocol Extension Specication: Router and Link Admittance Control
12.5.1 TLV Specication
12.5.2 OLSRv2 Interaction
12.6 Cryptographic Keys
12.7 Timestamps
12.8 Performance Study
12.8.1 Overhead of Router and Link Admittance Control
12.8.2 In-Router Resource Requirements
12.9 Conclusion
IV Wireless Sensor Networks
13 RPL Protocol Overview
13.1 Chapter Outline
13.2 DODAG Routing Structure
13.3 RPL Data Trac Flows
13.3.1 Upward Routes
13.3.2 Downward Routes
13.3.3 Sensor-to-Sensor Routes
13.4 Rank Changes in RPL
13.5 RPL Operational Requirements
13.6 Trickle Timer
13.7 RPL Discussion
13.8 Conclusion
14 Java RPL Implementation
14.1 Chapter Outline
14.2 Architecture Overview
14.3 Objective Function
14.4 Upward Flow
14.4.1 DIO
14.4.2 Upward Unicast Trac
14.5 Downward Flow
14.5.1 DAO
14.5.2 DAOACK
14.5.3 Downward Unicast Trac
14.6 Local Repair
14.7 Loop Detection
14.8 Conclusion
15 Multipoint-to-Point in RPL
15.1 Chapter Outline
15.2 Simulation Settings
15.2.1 DIO settings
15.3 Simulation Results
15.3.1 RPL Control Trac
15.3.2 Unicast Data Trac
15.4 Conclusion
16 Broadcast in RPL
16.1 Chapter Outline
16.2 Data Broadcasting in RPL
16.2.1 Classic Flooding (CF)
16.2.2 MultiPoint Relay Flooding (MPRF)
16.2.3 Parent Flooding (PF)
16.2.4 Preferred Parent Flooding (PPF)
16.2.5 Preferred Parent MPR Flooding (PPMPRF)
16.2.6 Optimized Preferred Parent MPR Flooding (PPMPRF-opt)
16.3 RPL Performance Study
16.3.1 Simulation Settings
16.3.2 Broadcast Data Trac
16.4 Conclusion
V Conclusion
