تاريخ عضويت: 08 Feb 2010
ارسالها: 1
|
UNIVERSITY ABERDEEN INTERNATIONAL
THESIS
Routing Protocols in Wireless
Ad-hoc Networks - A Simulation Study
MOHAMMADREZA MAZLOOMNEZHAD
Master’s thesis in Computer Science and Engineering
Routing Protocols in Wireless Ad-hoc Networks -
A Simulation Study
2009
Supervisor: Per Johansson
Examiner: Mikael Degermark
Abstract
Ad-hoc networking is a concept in computer communications, which means that users wanting to
communicate with each other form a temporary network, without any form of centralized administration.
Each node participating in the network acts both as host and a router and must therefore be willing to
forward packets for other nodes. For this purpose, a routing protocol is needed.
An ad-hoc network has certain characteristics, which imposes new demands on the routing protocol.
The most important characteristic is the dynamic topology, which is a consequence of node mobility. Nodes
can change position quite frequently, which means that we need a routing protocol that quickly adapts to
topology changes. The nodes in an ad-hoc network can consist of laptops and personal digital assistants and
are often very limited in resources such as CPU capacity, storage capacity, battery power and bandwidth.
This means that the routing protocol should try to minimize control traffic, such as periodic update
messages. Instead the routing protocol should be reactive, thus only calculate routes upon receiving a
specific request.
The Internet Engineering Task Force currently has a working group named Mobile Ad-hoc Networks
that is working on routing specifications for ad-hoc networks. This master thesis evaluates some of the
protocols put forth by the working group. This evaluation is done by means of simulation using Network
simulator 2 from Berkeley.
The simulations have shown that there certainly is a need for a special ad-hoc routing protocol when
mobility increases. More conventional routing protocols like DSDV have a dramatic decrease in
performance when mobility is high. Two of the proposed protocols are DSR and AODV. They perform very
well when mobility is high. However, we have found that a routing protocol that entirely depends on
messages at the IP-level will not perform well. Some sort of support from the lower layer, for instance link
failure detection or neighbor discovery is necessary for high performance.
The size of the network and the offered traffic load affects protocols based on source routing, like DSR,
to some extent. A large network with many mobile nodes and high offered load will increase the overhead for
DSR quite drastically. In these situations, a hop-by-hop based routing protocol like AODV is more desirable.
Table of Contents
1 INTRODUCTION .................................................................................................................... 9
1.1 BACKGROUND................................................................................................................................... 9
1.2 PROBLEM DESCRIPTION .................................................................................................................. 9
1.3 RELATED WORK ............................................................................................................................. 10
1.4 PROJECT ORGANIZATION .................................................................................................................. 10
1.5 DISPOSITION................................................................................................................................... 11
1.6 ABBREVIATIONS............................................................................................................................ 11
2 GENERAL CONCEPTS....................................................................................................................... 12
2.1 WIRELESS AD-HOC NETWORKS................................................................................................... 12
2.1.1 General.................................................................................................................................... 12
2.1.2 Usage....................................................................................................................................... 13
2.1.3 Characteristics ........................................................................................................................ 13
2.2 ROUTING ........................................................................................................................................ 14
2.2.1 Conventional protocols ........................................................................................................... 14
2.2.2 Link State................................................................................................................................. 14
2.2.3 Distance Vector ....................................................................................................................... 14
2.2.4 Source Routing ........................................................................................................................ 14
2.2.5 Flooding .................................................................................................................................. 15
2.2.6 Classification........................................................................................................................... 15
3 AD-HOC ROUTING PROTOCOLS................................................................................................... 16
3.1 DESIRABLE PROPERTIES ............................................................................................................... 16
3.2 MANET........................................................................................................................................... 17
3.3 DESTINATION SEQUENCED DISTANCE VECTOR - DSDV ......................................................... 17
3.3.1 Description .............................................................................................................................. 17
3.3.2 Properties ................................................................................................................................ 17
3.4 AD-HOC ON DEMAND DISTANCE VECTOR - AODV ................................................................. 18
3.4.1 Description .............................................................................................................................. 18
3.4.2 Properties ................................................................................................................................ 19
3.5 DYNAMIC SOURCE ROUTING - DSR ............................................................................ 20
3.5.1 Description .............................................................................................................................. 20
3.5.2 Properties ................................................................................................................................ 20
3.6 ZONE ROUTING PROTOCOL - ZRP ............................................................................................... 21
3.6.1 Description .............................................................................................................................. 21
3.6.2 Properties ................................................................................................................................ 22
3.7 TEMPORALLY-ORDERED ROUTING ALGORITHM - TORA ....................................................... 22
3.7.1 Description .............................................................................................................................. 22
3.7.2 Properties ................................................................................................................................. 23
3.8 INTERNET MANET ENCAPSULATION PROTOCOL - IMEP........................................................ 24
3.8.1 Description .............................................................................................................................. 24
3.8.2 Properties ................................................................................................................................ 24
3.9 CLUSTER BASED ROUTING PROTOCOL - CBRP......................................................................... 24
3.9.1 Description .............................................................................................................................. 24
3.9.2 Properties ................................................................................................................................ 26
3.10 COMPARISON................................................................................................................................. 26
4 SIMULATION ENVIRONMENT ...................................................................................................... 28
4.1 NETWORK SIMULATOR................................................................................................................ 28
4.2 MOBILITY EXTENSION ................................................................................................................. 29
4.2.1 Shared media .......................................................................................................................... 30
4.2.2 Mobile node............................................................................................................................. 30
4.3 SIMULATION OVERVIEW ............................................................................................... 31
4.4 MODIFICATIONS ............................................................................................................................ 32
4.4.1 AODV ...................................................................................................................................... 32
4.4.2 DSR.......................................................................................................................................... 33
4.4.3 DSDV....................................................................................................................................... 34
4.4.4 Flooding .................................................................................................................................. 34
4.4.5 The simulator........................................................................................................................... 34
5 SIMULATION STUDY ........................................................................................................................ 35
5.1 MEASUREMENTS ........................................................................................................................... 35
5.1.1 Quantitative metrics ................................................................................................................ 35
5.1.2 Parameters .............................................................................................................................. 35
5.1.3 Mobility ................................................................................................................................... 35
5.2 SIMULATION SETUP ....................................................................................................................... 38
5.3 MOBILITY SIMULATIONS .............................................................................................................. 39
5.3.1 Setup ........................................................................................................................................ 39
5.3.2 Fraction of received packets.................................................................................................... 40
5.3.3 End-to-end delay ..................................................................................................................... 41
5.3.4 End-to-end throughput ............................................................................................................ 42
5.3.5 Overhead ................................................................................................................................. 43
5.3.6 Optimal path............................................................................................................................ 44
5.3.7 Summary mobility simulations................................................................................................. 46
5.4 OFFERED LOAD SIMULATIONS .................................................................................................... 46
5.4.1 Setup ........................................................................................................................................ 46
5.4.2 Fraction of received packets.................................................................................................... 47
5.4.3 End-to-end delay ..................................................................................................................... 48
5.4.4 End-to-end throughput ............................................................................................................ 49
5.4.5 Overhead ................................................................................................................................. 49
5.4.6 Optimal path............................................................................................................................ 51
5.4.7 Summary offered load simulations .......................................................................................... 51
5.5 NETWORK SIZE SIMULATIONS...................................................................................................... 52
5.6 REALISTIC SCENARIOS.................................................................................................................. 52
5.6.1 Setup ........................................................................................................................................ 52
5.6.2 Conference............................................................................................................................... 53
5.6.3 Event coverage ........................................................................................................................ 55
5.6.4 Disaster area ........................................................................................................................... 57
5.6.5 Summary realistic scenarios.................................................................................................... 60
5.7 OBSERVATIONS ............................................................................................................................. 60
5.7.1 Ability to find routes ................................................................................................................ 60
5.7.2 Temporary backward routes.................................................................................................... 61
5.7.3 Buffers ..................................................................................................................................... 62
5.8 DISCUSSION.................................................................................................................................... 62
5.9 CLASSIFICATION............................................................................................................................ 62
5.9.1 Mobile networks ...................................................................................................................... 63
5.9.2 Size of networks ....................................................................................................................... 63
5.9.3 Network scenarios ................................................................................................................... 64
5.10 IMPROVEMENTS ............................................................................................................................ 64
6 IMPLEMENTATION STUDY ............................................................................................................ 65
DESIGN........................................................................................................................................................ 65
6.1.1 Main ........................................................................................................................................ 65
6.1.2 Event queue ............................................................................................................................ 66
6.1.3 Route table.............................................................................................................................. 66
6.1.4 Neighbors / senders ............................................................................................................... 66
6.1.5 Request buffer......................................................................................................................... 66
6.1.6 Message ................................................................................................................................. 66
6.2 SETUP............................................................................................................................................. 66
6.3 TESTING ........................................................................................................................................ 67
6.3.1 Correctness............................................................................................................................ 67
6.3.2 Performance .......................................................................................................................... 67
6.4 PROBLEMS / LIMITATIONS........................................................................................... 67
6.5 IMPROVEMENTS ........................................................................................................................... 68
6.6 IMPLEMENTATION CONCLUSIONS .................................................................................................... 68
7 CONCLUSIONS................................................................................................................................... 69
7.1 RESULTS......................................................................................................................................... 69
7.2 FURTHER STUDIES ........................................................................................................................ 69
8 REFERENCES ...................................................................................................................................... 71
APPENDIX A - TERMINOLOGY.............................................................................................................. 73
A.1 GENERAL TERMS........................................................................................................................... 73
A.2 AD-HOC RELATED TERMS ........................................................................................................... 74
APPENDIX B - AODV IMPLEMENTATION FOR NS .......................................................................... 75
B.1 MESSAGE FORMATS...................................................................................................................... 75
B.1.1 Route Request – RREQ ........................................................................................................... 75
B.1.2 Route Reply - RREP................................................................................................................ 76
B.1.3 Hello ...................................................................................................................................... 76
B.1.4 Link failure ............................................................................................................................ 76
B.2 DESIGN.......................................................................................................................................... 77
B.3 IMPORTANT ROUTINES.................................................................................................................... 78
B.3.1 Sending RREQ ....................................................................................................................... 78
B.3.2 Receiving RREQ .................................................................................................................... 78
B.3.3 Forwarding RREQ................................................................................................................. 79
B.3.4 Forwarding RREP ................................................................................................................ 79
B.3.5 Receiving RREP .................................................................................................................... 79
B.3.6 Hello handling ...................................................................................................................... 80
B.3.7 Forwarding packets............................................................................................................... 80
B.3.8 Sending Triggered RREP ..................................................................................................... 80
B.3.9 Receiving Triggered RREP................................................................................................... 80
APPENDIX C - SIMULATOR SCREENSHOTS ................................................................................... 81
C.1 NETWORK ANIMATOR ................................................................................................................ 81
C.2 AD-HOCKEY ................................................................................................................................. 82
List of Figures
Figure 1: Example of a simple ad-hoc network with three participating nodes..................... 12
Figure 2: Block diagram of a mobile node acting both as hosts and as router. ................................ 13
Figure 3: Network using ZRP. The dashed squares show the routing zones for nodes S and D....... 22
Figure 4: Directed acyclic graph rooted at destination................................................................................ 23
Figure 5: IMEP in the protocol stack. ......................................................................................................... 24
Figure 6: Bi-directional linked clusters....................................................................................................... 25
Figure 7: Network simulator 2. ................................................................................................................... 28
Figure 8: Shared media model. ................................................................................................................... 30
Figure 9: A mobile node. ............................................................................................................................ 31
Figure 10: Simulation overview................................................................................................................ 32
Figure 11: Example of mobility. ............................................................................................................... 37
Figure 12: Relation between the number of link changes and mobility. .................................... 37
Figure 13: Mobility simulations - fraction of received packets. ............................................................... 40
Figure 14: Mobility simulations - delay..................................................................................................... 41
Figure 15: Mobility simulations - throughput. .......................................................................................... 42
Figure 16: Mobility simulations - overhead............................................................................................... 43
Figure 17: Mobility simulations - optimal path difference. ........................................................ 45
Figure 18: Offered load simulations - fraction of received packets. .......................................................... 47
Figure 19: Offered load simulations - average delay. ............................................................................... 48
Figure 20: Offered load simulations - average throughput. ...................................................................... 49
Figure 21: Offered load simulations - overhead........................................................................................ 50
Figure 22: Offered load simulations – optimal path.................................................................................. 51
Figure 23: Conference scenario. ............................................................................................................... 54
Figure 24: Event coverage scenario. ......................................................................................................... 56
Figure 25: Disaster area scenario. ............................................................................................................. 58
Figure 26: Simple example scenario. ........................................................................................................ 60
Figure 27: Overview of AODV daemon. .................................................................................................. 65
Figure 28: Different router identification approaches. From left to right: 3a, 3b, 3c. ................ 70
Figure 29: Route request format. ............................................................................................................... 75
Figure 30: Route reply format.................................................................................................................... 76
Figure 31: AODV design of implementation for simulator. ...................................................................... 77
Figure 32: Screenshot – Network animator............................................................................................... ..81
Figure 33: Screenshot – Ad-hockey – Conference scenario. .................................................................... 82
Figure 34: Screenshot – Ad-hockey – Event coverage scenario. .............................................................. 83
Figure 35: Screenshot – Ad-hockey – Disaster area. ................................................................................ 83
List of Tables
Table 1: Neighbor table. ............................................................................................................. 25
Table 2: Comparison between ad-hoc routing protocols. .......................................................................... 27
Table 3: Constants used in the AODV implementation............................................................................. 33
Table 4: Constants used in the DSR implementation. ............................................................................... 33
Table 5: Constants used in the DSDV implementation. ............................................................................ 34
Table 6: Mobility variables........................................................................................................................ 36
Table 7: Parameters used during mobility simulations.............................................................................. 39
Table 8: Optimal path difference for all protocols..................................................................................... 45
Table 9: Parameters used during offered load simulations. ....................................................................... 47
Table 10: Parameters used during realistic simulations............................................................................... 53
Table 11: Parameters used during conference scenario. .............................................................................. 53
Table 12: Conference simulation results. .................................................................................................... 54
Table 13: Packet drops in conference scenario............................................................................................ 55
Table 14: Parameters used during event coverage scenario. ....................................................................... 55
Table 15: Event coverage simulation results. .............................................................................................. 57
Table 16: Packet drops in event coverage scenario. .................................................................................... 57
Table 17: Parameters used during disaster area scenario............................................................................. 57
Table 18: Disaster area simulation results. .................................................................................................. 59
Table 19: Packet drops in disaster area........................................................................................................ 59
Table 20: Routing tables for AODV after a route discovery process. ......................................................... 60
Table 21: Routing caches for DSR, after a route discovery process............................................................ 61
1 Introduction
1.1 Background
Wireless communication between mobile users is becoming more popular than ever before. This due to
recent technological advances in laptop computers and wireless data communication devices, such as
wireless modems and wireless LANs. This has lead to lower prices and higher data rates, which are the two
main reasons why mobile computing continues to enjoy rapid growth.
There are two distinct approaches for enabling wireless communication between two hosts. The first
approach is to let the existing cellular network infrastructure carry data as well as voice. The major problems
include the problem of handoff, which tries to handle the situation when a connection should be smoothly
handed over from one base station to another base station without noticeable delay or packet loss. Another
problem is that networks based on the cellular infrastructure are limited to places where there exists such a
cellular network infrastructure.
The second approach is to form an ad-hoc network among all users wanting to communicate with each
other. This means that all users participating in the ad-hoc network must be willing to forward data packets
to make sure that the packets are delivered from source to destination. This form of networking is limited in
range by the individual nodes transmission ranges and is typically smaller compared to the range of cellular
systems. This does not mean that the cellular approach is better than the ad-hoc approach. Ad-hoc networks
have several advantages compared to traditional cellular systems. These advantages include:
N On demand setup
N Fault tolerance
N Unconstrained connectivity
Ad-hoc networks do not rely on any pre-established infrastructure and can therefore be deployed in
places with no infrastructure. This is useful in disaster recovery situations and places with non-existing or
damaged communication infrastructure where rapid deployment of a communication network is needed. Ad-
hoc networks can also be useful on conferences where people participating in the conference can form a
temporary network without engaging the services of any pre-existing network.
Because nodes are forwarding packets for each other, some sort of routing protocol is necessary to make
the routing decisions. Currently there does not exist any standard for a routing protocol for ad-hoc networks,
instead this is work in progress. Many problems remain to be solved before any standard can be determined.
This thesis looks at some of these problems and tries to evaluate some of the currently proposed protocols.
1.2 Problem description
The objective for this master thesis was to evaluate proposed routing protocols for wireless ad-hoc networks
based on performance. This evaluation should be done theoretically and through simulation. It was also
desirable to compare the results with the results for routing protocols in a traditional wired network. At the
beginning of this master thesis, no implementation of the protocols had been released, so the first main task
was to implement some of the protocols.
The thesis also included the goal to generate a simulation environment that could be used as a platform
for further studies within the area of ad-hoc networks. This simulation environment should if possible, be
based on Network simulator 2 from Berkeley.
9
The goal of this master thesis was to:
N Get a general understanding of ad-hoc networks.
N Generate a simulation environment that could be used for further studies.
N Implement some of the proposed routing protocols for wireless ad-hoc networks.
N Analyze the protocols theoretically and through simulation.
N Produce a classification of the protocols with respect to applicability in combinations of small/large
networks, and mobile/semi-mobile nodes.
N Recommend protocols for specific network scenarios.
1.3 Related work
Many routing protocols have been proposed [2][4][6][8][10][11][12][16][19][22][26], but few comparisons
between the different protocols have been made. Of the work that has been done in this field, only the work
done by the Monarch1 project at Carnegie Mellon University (CMU) has compared some of the different
proposed routing protocols and evaluated them based on the same quantitative metrics. The result was
presented in the article “A performance comparison of multi-hop ad hoc wireless network routing protocols”
[3] that was released in the beginning of October 1998. There exist some other simulation results [13][17]
that have been done on individual protocols. These simulations have however not used the same metrics and
are therefore not comparable with each other.
In parallel with our master thesis, a master thesis project in Gothenburg [28] implemented the AODV
[19] protocol and tested it in a environment that consisted of 5 computers with wireless interfaces. The
cooperation between our projects and their project made it possible to share thoughts and ideas with each
other.
1.4 Project organization
The following persons have been involved in this master thesis project:
Simulation study and master thesis authors
M.Sc. Tony Larsson
M.Sc. Nicklas Hedman
Supervisor at Ericsson Telecom AB, Switchlab
Tekn.Lic. Per Johansson
Examiner at Luleه University of Technology
Ph. D. Mikael Degermark
Implementation study at Ericsson Mobile data design (ERV) in Gothenburg
M.Sc. Johan Kِpman
M.Sc. Jerry Svedlund
Supervisor at ERV
M.Sc. Christoffer Kanljung
Contribution of realistic scenarios
Ph.D. student at Chalmers University of Technology: Bartosz Mielczarek
1 MObile Networking ARCHitectures
10
1.5 Disposition
This report consists of 8 chapters and two appendices. Chapters 1 and 2 explain the concept of ad-hoc
networks and routing in general. Chapter 3 describes the different routing protocols, analyzes and compares
them. Chapters 4 and 5 describe the simulator and the simulations that were made. Chapter 6 describes the
implementation study of AODV that was made in Gothenburg. Chapter 7 concludes the whole report and
chapter 8 is the references that we have used. The appendices contain some terminology, details about the
implementation of AODV that we did for the simulator and some screenshots of the simulator.
1.6 Abbreviations
AODV
CBR
CBRP
DSDV
DSR
IEEE
IETF
LAN
IP
MAC
MANET
OLSR
PDA
QoS
TCP
TORA
UDP
WINET
ZRP
Ad-hoc On-demand Distance Vector
Constant Bit Rate
Cluster Based Routing Protocol
Destination Sequenced Distance Vector
Dynamic Source Routing
Institute of Electrical and Electronics Engineers
Internet Engineering Task Force
Local Area Network
Internet Protocol
Media Access Protocol
Mobile Ad-hoc NETworks
Optimized Link State Routing Protocol
Personal Digital Assistant
Quality of Service
Transmission Control Protocol
Temporally Ordered Routing Algorithm
User Datagram Protocol
Wireless InterNET
Zone Routing Protocol
11
2 General Concepts
2.1 Wireless ad-hoc networks
2.1.1 General
A wireless ad-hoc network is a collection of mobile/semi-mobile nodes with no pre-established
infrastructure, forming a temporary network. Each of the nodes has a wireless interface and communicate
with each other over either radio or infrared. Laptop computers and personal digital assistants that
communicate directly with each other are some examples of nodes in an ad-hoc network. Nodes in the ad-
hoc network are often mobile, but can also consist of stationary nodes, such as access points to the Internet.
Semi mobile nodes can be used to deploy relay points in areas where relay points might be needed
temporarily.
Figure 1 shows a simple ad-hoc network with three nodes. The outermost nodes are not within
transmitter range of each other. However the middle node can be used to forward packets between the
outermost nodes. The middle node is acting as a router and the three nodes have formed an ad-hoc network.
Figure 1:
Example of a simple ad-hoc network with three participating nodes.
An ad-hoc network uses no centralized administration. This is to be sure that the network wont collapse
just because one of the mobile nodes moves out of transmitter range of the others. Nodes should be able to
enter/leave the network as they wish. Because of the limited transmitter range of the nodes, multiple hops
may be needed to reach other nodes. Every node wishing to participate in an ad-hoc network must be willing
to forward packets for other nodes. Thus every node acts both as a host and as a router. A node can be
viewed as an abstract entity consisting of a router and a set of affiliated mobile hosts (Figure 2). A router is
an entity, which, among other things runs a routing protocol. A mobile host is simply an IP-addressable
host/entity in the traditional sense.
Ad-hoc networks are also capable of handling topology changes and malfunctions in nodes. It is fixed
through network reconfiguration. For instance, if a node leaves the network and causes link breakages,
affected nodes can easily request new routes and the problem will be solved. This will slightly increase the
delay, but the network will still be operational.
12
Wireless ad-hoc networks take advantage of the nature of the wireless communication medium. In other
words, in a wired network the physical cabling is done a priori restricting the connection topology of the
nodes. This restriction is not present in the wireless domain and, provided that two nodes are within
transmitter range of each other, an instantaneous link between them may form.
Host
Host
Host
Router
Figure 2:
2.1.2 Usage
Block diagram of a mobile node acting both as hosts and as router.
There is no clear picture of what these kinds of networks will be used for. The suggestions vary from
document sharing at conferences to infrastructure enhancements and military applications.
In areas where no infrastructure such as the Internet is available an ad-hoc network could be used by a
group of wireless mobile hosts. This can be the case in areas where a network infrastructure may be
undesirable due to reasons such as cost or convenience. Examples of such situations include disaster
recovery personnel or military troops in cases where the normal infrastructure is either unavailable or
destroyed.
Other examples include business associates wishing to share files in an airport terminal, or a class of
students needing to interact during a lecture. If each mobile host wishing to communicate is equipped with a
wireless local area network interface, the group of mobile hosts may form an ad-hoc network.
Access to the Internet and access to resources in networks such as printers are features that probably
also will be supported.
2.1.3 Characteristics
Ad-hoc networks are often characterized by a dynamic topology due to the fact that nodes change their
physical location by moving around. This favors routing protocols that dynamically discover routes over
conventional routing algorithms like distant vector and link state [23]. Another characteristic is that a
host/node have very limited CPU capacity, storage capacity, battery power and bandwidth, also referred to as
a “thin client”. This means that the power usage must be limited thus leading to a limited transmitter range.
The access media, the radio environment, also has special characteristics that must be considered when
designing protocols for ad-hoc networks. One example of this may be unidirectional links. These links arise
when for example two nodes have different strength on their transmitters, allowing only one of the host to
hear the other, but can also arise from disturbances from the surroundings. Multihop in a radio environment
may result in an overall transmit capacity gain and power gain, due to the squared relation between coverage
and required output power. By using multihop, nodes can transmit the packets with a much lower output
power.
13
2.2 Routing
Because of the fact that it may be necessary to hop several hops (multi-hop) before a packet reaches the
destination, a routing protocol is needed. The routing protocol has two main functions, selection of routes for
various source-destination pairs and the delivery of messages to their correct destination. The second
function is conceptually straightforward using a variety of protocols and data structures (routing tables). This
report is focused on selecting and finding routes.
2.2.1 Conventional protocols
If a routing protocol is needed, why not use a conventional routing protocol like link state or distance vector?
They are well tested and most computer communications people are familiar with them. The main problem
with link-state and distance vector is that they are designed for a static topology, which means that they
would have problems to converge to a steady state in an ad-hoc network with a very frequently changing
topology.
Link state and distance vector would probably work very well in an ad-hoc network with low mobility,
i.e. a network where the topology is not changing very often. The problem that still remains is that link-state
and distance-vector are highly dependent on periodic control messages. As the number of network nodes can
be large, the potential number of destinations is also large. This requires large and frequent exchange of data
among the network nodes. This is in contradiction with the fact that all updates in a wireless interconnected
ad hoc network are transmitted over the air and thus are costly in resources such as bandwidth, battery power
and CPU. Because both link-state and distance vector tries to maintain routes to all reachable destinations, it
is necessary to maintain these routes and this also wastes resources for the same reason as above.
Another characteristic for conventional protocols are that they assume bi-directional links, e.g. that the
transmission between two hosts works equally well in both directions. In the wireless radio environment this
is not always the case.
Because many of the proposed ad-hoc routing protocols have a traditional routing protocol as
underlying algorithm, it is necessary to understand the basic operation for conventional protocols like
distance vector, link state and source routing.
2.2.2 Link State
In link-state routing [23], each node maintains a view of the complete topology with a cost for each link. To
keep these costs consistent; each node periodically broadcasts the link costs of its outgoing links to all other
nodes using flooding. As each node receives this information, it updates its view of the network and applies a
shortest path algorithm to choose the next-hop for each destination.
Some link costs in a node view can be incorrect because of long propagation delays, partitioned
networks, etc. Such inconsistent network topology views can lead to formation of routing-loops. These loops
are however short-lived, because they disappear in the time it takes a message to traverse the diameter of the
network.
2.2.3 Distance Vector
In distance vector [23] each node only monitors the cost of its outgoing links, but instead of broadcasting this
information to all nodes, it periodically broadcasts to each of its neighbors an estimate of the shortest
distance to every other node in the network. The receiving nodes then use this information to recalculate the
routing tables, by using a shortest path algorithm.
Compared to link-state, distance vector is more computation efficient, easier to implement and requires
much less storage space. However, it is well known that distance vector can cause the formation of both
short-lived and long-lived routing loops. The primary cause for this is that the nodes choose their next-hops
in a completely distributed manner based on information that can be stale.
2.2.4 Source Routing
Source routing [23] means that each packet must carry the complete path that the packet should take through
the network. The routing decision is therefore made at the source. The advantage with this approach is that it
is very easy to avoid routing loops. The disadvantage is that each packet requires a slight overhead.
14
2.2.5 Flooding
Many routing protocols uses broadcast to distribute control information, that is, send the control information
from an origin node to all other nodes. A widely used form of broadcasting is flooding [23] and operates as
follows. The origin node sends its information to its neighbors (in the wireless case, this means all nodes that
are within transmitter range). The neighbors relay it to their neighbors and so on, until the packet has reached
all nodes in the network. A node will only relay a packet once and to ensure this some sort of sequence
number can be used. This sequence number is increased for each new packet a node sends.
2.2.6 Classification
Routing protocols can be classified [1] into different categories depending on their properties.
N Centralized vs. Distributed
N Static vs. Adaptive
N Reactive vs. Proactive
One way to categorize the routing protocols is to divide them into centralized and distributed
algorithms. In centralized algorithms, all route choices are made at a central node, while in distributed
algorithms, the computation of routes is shared among the network nodes.
Another classification of routing protocols relates to whether they change routes in response to the
traffic input patterns. In static algorithms, the route used by source-destination pairs is fixed regardless of
traffic conditions. It can only change in response to a node or link failure. This type of algorithm cannot
achieve high throughput under a broad variety of traffic input patterns. Most major packet networks uses
some form of adaptive routing where the routes used to route between source-destination pairs may change
in response to congestion
A third classification that is more related to ad-hoc networks is to classify the routing algorithms as
either proactive or reactive. Proactive protocols attempt to continuously evaluate the routes within the
network, so that when a packet needs to be forwarded, the route is already known and can be immediately
used. The family of Distance-Vector protocols is an example of a proactive scheme. Reactive protocols, on
the other hand, invoke a route determination procedure on demand only. Thus, when a route is needed, some
sort of global search procedure is employed. The family of classical flooding algorithms belongs to the
reactive group. Proactive schemes have the advantage that when a route is needed, the delay before actual
packets can be sent is very small. On the other side proactive schemes needs time to converge to a steady
state. This can cause problems if the topology is changing frequently.
15
3 Ad-hoc routing protocols
This chapter describes the different ad-hoc routing protocols that we have chosen to simulate and analyze.
3.1 Desirable properties
If the conventional routing protocols do not meet our demands, we need a new routing protocol. The
question is what properties such protocols should have? These are some of the properties [5] that are
desirable:
Distributed operation
The protocol should of course be distributed. It should not be dependent on a centralized controlling node.
This is the case even for stationary networks. The difference is that nodes in an ad-hoc network can
enter/leave the network very easily and because of mobility the network can be partitioned.
Loop free
To improve the overall performance, we want the routing protocol to guarantee that the routes supplied are
loop-free. This avoids any waste of bandwidth or CPU consumption.
Demand based operation
To minimize the control overhead in the network and thus not wasting network resources more than
necessary, the protocol should be reactive. This means that the protocol should only react when needed and
that the protocol should not periodically broadcast control information.
Unidirectional link support
The radio environment can cause the formation of unidirectional links. Utilization of these links and not only
the bi-directional links improves the routing protocol performance.
Security
The radio environment is especially vulnerable to impersonation attacks, so to ensure the wanted behavior
from the routing protocol, we need some sort of preventive security measures. Authentication and encryption
is probably the way to go and the problem here lies within distributing keys among the nodes in the ad-hoc
network. There are also discussions about using IP-sec [14] that uses tunneling to transport all packets.
Power conservation
The nodes in an ad-hoc network can be laptops and thin clients, such as PDAs that are very limited in battery
power and therefore uses some sort of stand-by mode to save power. It is therefore important that the routing
protocol has support for these sleep-modes.
Multiple routes
To reduce the number of reactions to topological changes and congestion multiple routes could be used. If
one route has become invalid, it is possible that another stored route could still be valid and thus saving the
routing protocol from initiating another route discovery procedure.
Quality of service support
Some sort of Quality of Service support is probably necessary to incorporate into the routing protocol. This
has a lot to do with what these networks will be used for. It could for instance be real-time traffic support.
None of the proposed protocols from MANET have all these properties, but it is necessary to remember
that the protocols are still under development and are probably extended with more functionality. The
primary function is still to find a route to the destination, not to find the best/optimal/shortest-path route.
The remainder of this chapter will describe the different routing protocols and analyze them
theoretically.
16
3.2 MANET
IETF has a working group named MANET (Mobile Ad-hoc Networks) [15] that is working in the field of ad-
hoc networks. They are currently developing routing specifications for ad-hoc IP networks that support
scaling to a couple of hundred nodes. Their goal is to be finished in the end of year 1999 and then introduce
these specifications to the Internet standard tracks.
Even if MANET currently is working on routing protocols, it also serves as a meeting place and forum,
so people can discuss issues concerning ad-hoc networks. Currently they have seven routing protocol drafts:
N AODV - Ad-hoc On Demand Distance Vector [19]
N ZRP - Zone Routing Protocol [8]
N TORA / IMEP - Temporally Ordered Routing Algorithm / Internet MANET Encapsulation Protocol
[6][16][17]
N DSR - Dynamic Source Routing [12][13]
N CBRP - Cluster Based Routing Protocol [11]
N CEDAR - Core Extraction Distributed Ad hoc Routing [26]
N AMRoute – Ad-hoc Multicast Routing Protocol [2]
N OLSR - Optimized Link State Routing Protocol [10]
Of these proposed protocols we have chosen to analyze AODV, DSR, ZRP, CBRP and TORA
theoretically. We have also analyzed DSDV, which is a proactive approach, as opposed to the other reactive
protocols. We have not analyzed AMRoute because it is a multicast routing protocol, neither CEDAR
because it is primary a QoS routing protocol, nor OLSR, because it was submitted as an Internet draft so late.
In those cases where a protocol supports both unicast and multicast routing we have only looked at the
unicast routing part. Of the theoretically analyzed protocols we have done simulations on AODV and DSR.
3.3 Destination Sequenced Distance Vector - DSDV
3.3.1 Description
DSDV [22] is a hop-by-hop distance vector routing protocol that in each node has a routing table that for all
reachable destinations stores the next-hop and number of hops for that destination. Like distance-vector,
DSDV requires that each node periodically broadcast routing updates. The advantage with DSDV over
traditional distance vector protocols is that DSDV guarantees loop-freedom.
To guarantee loop-freedom DSDV uses a sequence numbers to tag each route. The sequence number
shows the freshness of a route and routes with higher sequence numbers are favorable. A route R is
considered more favorable than R' if R has a greater sequence number or, if the routes have the same
sequence number but R has lower hop-count. The sequence number is increased when a node A detects that a
route to a destination D has broken. So the next time node A advertises its routes, it will advertise the route
to D with an infinite hop-count and a sequence number that is larger than before.
DSDV basically is distance vector with small adjustments to make it better suited for ad-hoc networks.
These adjustments consist of triggered updates that will take care of topology changes in the time between
broadcasts. To reduce the amount of information in these packets there are two types of update messages
defined: full and incremental dump. The full dump carries all available routing information and the
incremental dump that only carries the information that has changed since the last dump.
3.3.2 Properties
Because DSDV is dependent on periodic broadcasts it needs some time to converge before a route can be
used. This converge time can probably be considered negligible in a static wired network, where the
topology is not changing so frequently. In an ad-hoc network on the other hand, where the topology is
expected to be very dynamic, this converge time will probably mean a lot of dropped packets before a valid
route is detected. The periodic broadcasts also add a large amount of overhead into the network.
17
3.4 Ad-hoc On Demand Distance vector - AODV
3.4.1 Description
The Ad Hoc On-Demand Distance Vector (AODV) [19] routing protocol enables multi-hop routing between
participating mobile nodes wishing to establish and maintain an ad-hoc network. AODV is based upon the
distance vector algorithm. The difference is that AODV is reactive, as opposed to proactive protocols like
DV, i.e. AODV only requests a route when needed and does not require nodes to maintain routes to
destinations that are not actively used in communications. As long as the endpoints of a communication
connection have valid routes to each other, AODV does not play any role.
Features of this protocol include loop freedom and that link breakages cause immediate notifications to
be sent to the affected set of nodes, but only that set. Additionally, AODV has support for multicast routing
and avoids the Bellman Ford "counting to infinity" problem [27]. The use of destination sequence numbers
guarantees that a route is "fresh".
The algorithm uses different messages to discover and maintain links. Whenever a node wants to try and
find a route to another node, it broadcasts a Route Request (RREQ) to all its neighbors. The RREQ
propagates through the network until it reaches the destination or a node with a fresh enough route to the
destination. Then the route is made available by unicasting a RREP back to the source.
The algorithm uses hello messages (a special RREP) that are broadcasted periodically to the immediate
neighbors. These hello messages are local advertisements for the continued presence of the node and
neighbors using routes through the broadcasting node will continue to mark the routes as valid. If hello
messages stop coming from a particular node, the neighbor can assume that the node has moved away and
mark that link to the node as broken and notify the affected set of nodes by sending a link failure notification
(a special RREP) to that set of nodes.
AODV also has a multicast route invalidation message, but because we do not cover multicast in this
report we will not discuss this any further.
Route table management
AODV needs to keep track of the following information for each route table entry:
N Destination IP Address: IP address for the destination node.
N Destination Sequence Number: Sequence number for this destination.
N Hop Count: Number of hops to the destination.
N Next Hop: The neighbor, which has been designated to forward packets to the destination for this route
entry.
N Lifetime: The time for which the route is considered valid.
N Active neighbor list: Neighbor nodes that are actively using this route entry.
N Request buffer: Makes sure that a request is only processed once.
Route discovery
A node broadcasts a RREQ when it needs a route to a destination and does not have one available. This can
happen if the route to the destination is unknown, or if a previously valid route expires. After broadcasting a
RREQ, the node waits for a RREP. If the reply is not received within a certain time, the node may
rebroadcast the RREQ or assume that there is no route to the destination.
Forwarding of RREQs is done when the node receiving a RREQ does not have a route to the
destination. It then rebroadcast the RREQ. The node also creates a temporary reverse route to the Source IP
Address in its routing table with next hop equal to the IP address field of the neighboring node that sent the
broadcast RREQ. This is done to keep track of a route back to the original node making the request, and
might be used for an eventual RREP to find its way back to the requesting node. The route is temporary in
the sense that it is valid for a much shorter time, than an actual route entry.
When the RREQ reaches a node that either is the destination node or a node with a valid route to the
destination, a RREP is generated and unicasted back to the requesting node. While this RREP is forwarded, a
route is created to the destination and when the RREP reaches the source node, there exists a route from the
source to the destination.
18
Route maintenance
When a node detects that a route to a neighbor no longer is valid, it will remove the routing entry and send a
link failure message, a triggered route reply message to the neighbors that are actively using the route,
informing them that this route no longer is valid. For this purpose AODV uses a active neighbor list to keep
track of the neighbors that are using a particular route. The nodes that receive this message will repeat this
procedure. The message will eventually be received by the affected sources that can chose to either stop
sending data or requesting a new route by sending out a new RREQ.
3.4.2 Properties
The advantage with AODV compared to classical routing protocols like distance vector and link-state is that
AODV has greatly reduced the number of routing messages in the network. AODV achieves this by using a
reactive approach. This is probably necessary in an ad-hoc network to get reasonably performance when the
topology is changing often.
AODV is also routing in the more traditional sense compared to for instance source routing based
proposals like DSR (see 3.5). The advantage with a more traditional routing protocol in an ad-hoc network is
that connections from the ad-hoc network to a wired network like the Internet is most likely easier.
The sequence numbers that AODV uses represents the freshness of a route and is increased when
something happens in the surrounding area. The sequence prevents loops from being formed, but can
however also be the cause for new problems. What happens for instance when the sequence numbers no
longer are synchronized in the network? This can happen when the network becomes partitioned, or the
sequence numbers wrap around.
AODV only support one route for each destination. It should however be fairly easy to modify AODV,
so that it supports several routes per destination. Instead of requesting a new route when an old route
becomes invalid, the next stored route to that destination could be tried. The probability for that route to still
be valid should be rather high.
Although the Triggered Route Replies are reduced in number by only sending the Triggered Route
Replies to affected senders, they need to traverse the whole way from the failure to the senders. This distance
can be quite high in numbers of hops. AODV sends one Triggered RREP for every active neighbor in the
active neighbor list for all entries that have been affected of a link failure. This can mean that each active
neighbor can receive several triggered RREPs informing about the same link failure, but for different
destinations, if a large fraction of the network traffic is routed through the same node and this node goes
down. An aggregated solution would be more appropriate here.
AODV uses hello messages at the IP-level. This means that AODV does not need support from the link
layer to work properly. It is however questionable if this kind of protocol can operate with good performance
without support from the link layer. The hello messages adds a significant overhead to the protocol.
AODV does not support unidirectional links. When a node receives a RREQ, it will setup a reverse
route to the source by using the node that forwarded the RREQ as nexthop. This means that the route reply,
in most cases is unicasted back the same way as the route request used. Unidirectional link support would
make it possible to utilize all links and not only the bi-directional links. It is however questionable if
unidirectional links are desirable in a real environment. The acknowledgements in the MAC protocol IEEE
802.11 would for instance not work with unidirectional links.
19
3.5 Dynamic Source Routing - DSR
3.5.1 Description
Dynamic Source Routing (DSR) [3][12][13] also belongs to the class of reactive protocols and allows nodes
to dynamically discover a route across multiple network hops to any destination. Source routing means that
each packet in its header carries the complete ordered list of nodes through which the packet must pass. DSR
uses no periodic routing messages (e.g. no router advertisements), thereby reducing network bandwidth
overhead, conserving battery power and avoiding large routing updates throughout the ad-hoc network.
Instead DSR relies on support from the MAC layer (the MAC layer should inform the routing protocol about
link failures). The two basic modes of operation in DSR are route discovery and route maintenance.
Route discovery
Route discovery is the mechanism whereby a node X wishing to send a packet to Y, obtains the source route
to Y. Node X requests a route by broadcastin |
|
