Exploring MANET Routing Protocols¶
Goals¶
Routing in Mobile Ad Hoc Networks (MANETs) is a challenging problem due to the dynamically changing network topology, which gave rise to the development of many different routing protocols. MANET routing protocols can be classified into reactive, proactive, and location-based, among others. INET features various routing protocols for MANETs from different categories.
In this showcase, we’ll look at three representative MANET routing protocols: a reactive protocol (AODV), a proactive protocol (DSDV), and a location-based protocol (GPSR). We’ll explore each of them through three example simulations.
4.0About MANETs¶
MANETs are ad hoc networks comprised of mobile wireless nodes. Given the mobile nature of the nodes, the network topology can change over time. The nodes create their own network infrastructure: each node also acts as a router, forwarding traffic in the network. MANET routing protocols need to adapt to changes in the network topology and maintain routing information, so that packets can be forwarded to their destinations. Although MANET routing protocols are mainly for mobile networks, they can also be useful for networks of stationary nodes that lack network infrastructure.
There are two main types of MANET routing protocols, reactive and
proactive (although there are others which don’t fit into either
category). Reactive or on-demand routing protocols update routing
information when there is an immediate demand for it, i.e. one of the
nodes wants to send a packet (and there is no working route to the
destination). Then, they exchange route discovery messages and forward
the packet. The routes stay the same until there is an error in a
packet’s forwarding, i.e. the packet cannot be forwarded anymore due to
a change in the network topology. Examples of reactive MANET routing
protocols include AODV, DSR, ABR, etc.
Proactive or table-driven routing protocols continuously maintain
routing information so the routes in the network are always up to date.
This update typically involves periodic routing maintenance messages exchanged
throughout the network. These types of protocols use more maintenance
transmissions than reactive protocols to make sure the routing
information is always up-to-date (they update it even when there is no
change in the network topology). Examples of reactive MANET routing
protocols include DSDV, OLSR, Babel, etc.
Reactive protocols require less overhead than proactive protocols (there are no concerning routing when the routes don’t change) but also might react more slowly to changes in the network topology. In the case of proactive protocols, due to the up-to-date nature of routing information, latency is lower than in the case of reactive protocols.
There are other types of MANET routing protocols, such as Hybrid (both reactive and proactive), Hierarchical, and Geographical routing. INET features several routing protocols, for MANETs and other uses (including wired and wireless cases). See /inet/src/inet/routing directory for the available routing protocols.
The example simulations in this showcase feature the reactive protocol
Ad hoc On-Demand Distance Vector routing (AODV), the proactive
protocol Destination-Sequenced Distance Vector routing (DSDV), and
the geo routing protocol Greedy Perimeter Stateless Routing (GPSR).
The following section details these three protocols briefly.
About AODV¶
AODV is a reactive (or on-demand) MANET routing protocol, and as such, it maintains routes for which there is a demand in the network (i.e. packets are frequently sent on the route). AODV maintains a routing table with the next hop for reaching destinations. Routes time out after a while if not used (i.e. no packets are sent on them). AODV features the following routing message types:
RREQ: Route requestRREP: Route replyRERR: Route error
When a node wants to send a packet, and it doesn’t know the route to the
destination, it initiates route discovery, by sending an RREQ
multicast message. The neighboring nodes record where the message came
from and forward it to their neighbors until the message gets to the
destination node. The destination node replies with an RREP, which
gets back to the source on the reverse path along which the RREQ
came. Forward routes are set up in the intermediate nodes as the
RREP travels back to the source. An intermediate node can also send
an RREP in reply to a received RREQ if it knows the route to
the destination, thus nodes can join an existing route. When the
RREP arrives at the source, and the route is created, communication
can begin between the source and the destination. If a route no longer
works due to link break, i.e. messages cannot be forwarded on it, a
RERR message is broadcast by the node which detects the link break.
Other nodes re-broadcast the message. The RERR message indicates the
destination which is unreachable. Nodes receiving the message make the
route inactive (and eventually the route is deleted). The next packet to
be sent triggers route discovery. As a reactive protocol, generally AODV
has less overhead (less route maintenance messages) than proactive ones,
but setting up new routes takes time while packets are waiting to be
delivered. (Note that the routing protocol overhead depends on the
mobility level in the network.)
Additionally, even though AODV is a reactive protocol, nodes can send periodic hello messages to discover links to neighbors and update the status of these links. This mechanism is local (hello messages are only sent to neighbors, and not forwarded), and it can make the network more responsive to local topology changes. By default, hello messages are turned off in INET’s AODV implementation.
About DSDV¶
DSDV is a proactive (or table driven) MANET routing protocol, so it makes sure routing information in the network is always up-to-date. Each node maintains a routing table with the best route to each destination. The routing table contains routing entries to all possible destinations known either directly because it’s a neighbor, or indirectly through neighbors. A routing entry contains the destination’s IP address, last known sequence number, hop count required to reach the destination, and the next hop. Routing information is frequently updated, so all nodes have the best routes in the network. Routing information is updated in two ways:
Nodes broadcast their entire routing tables periodically (infrequently)
Nodes broadcast small updates when a change in their routing table occurs
A node updates a routing table entry if it receives a better route. A better route is one that has a higher sequence number, or a lower hop count if the sequence number is the same.
In general, DSDV has more overhead than reactive routing protocols, because route maintenance messages are sent all the time. Since the routes are always up to date, DSDV has less delay in sending data.
About GPSR¶
GPSR is stateless (regarding routes), geographic location based routing protocol. Each node maintains the addresses and geographical co-ordinates of its neighbors, i.e. other nodes in its communication range. Nodes advertise their locations periodically by sending beacons. When no beacons are received from a neighboring node for some time, the node is assumed to be out of range, and its table entry is deleted. A table entry for a node is also deleted after link failure. Nodes attach their location data on all sent and forwarded packets as well. Each packet transmission resets the beacon timer, reducing the required protocol overhead in parts of the network with frequent packet traffic. The protocol is stateless in the context of routes. Nodes only have local information about their neighborhood, i.e. the positions of other nodes in their communication range, but they don’t have information about node positions or routes in the network as a whole.
Destination is designated by an IP address, but the destination’s location is also appended to packets. Packets are routed towards the destination’s location specified with co-ordinates. IP addresses are only used to determine whether a receiving node is the destination of a packet. The protocol operates in one of two modes:
In greedy mode, a node forwards a packet to its neighbor which is geographically closest to the destination node. Thus the packet gets gradually closer to its destination with every hop. If a forwarding node is closer to the destination than any of its neighbors, the node switches the packet to perimeter mode. In this case, the packet must take a route that takes it farther from its destination temporarily - it routes around a void, a region without any nodes.
In perimeter routing mode, the packet can circumnavigate a void. When the packet is in this mode, nodes create a planar graph of their neighboring nodes based on their location, where vertices represent nodes and edges represent possible links between nodes. Nodes use the right-hand rule for forwarding packets, i.e. they forward the packet on the first edge to the right, compared to the edge the packet arrived from. Each node does this until the packet arrives at its destination, or at an intermediate node which is closer to the destination than the one where the packet was switched to perimeter mode. In the latter case, the packet is switched to greedy mode. If the packet is in perimeter mode and would be forwarded again on the first edge of the perimeter, it is discarded (there is no route to the destination).
Several parameters of the protocol can be set according to the mobility rate and transmission ranges in the network, such as the interval of beacons and timeout of neighbor location data. Also, there are multiple planarization algorithms available, which can yield different planar graphs and thus result in different behavior of the protocol in certain situations.
Configuration and Results¶
This section contains the configuration and results for the three
simulations, which demonstrate the MANET routing protocols AODV,
DSDV and GPSR. The AODV and DSDV simulations use the
ManetRoutingProtocolsShowcaseA network, which features moving hosts.
The GPSR simulation uses the ManetRoutingProtocolsShowcaseB network,
featuring stationary hosts. The networks are defined in
ManetProtocolsShowcase.ned.
Both networks contain hosts of the type ManetRouter (an extension of
WirelessHost), whose routing module type is configurable. Just as
WirelessHost, it uses Ieee80211ScalarRadio by default. It also
has IP forwarding enabled, and its management module is set to
Ieee80211MgmtAdhoc. In the network, there is a source host named
source, a destination host named destination, and a number of
other hosts, which are named node1 up to node10 (their numbers
vary in the different networks). In addition to mobile nodes, both
networks contain an Ieee80211ScalarRadioMedium, an
Ipv4NetworkConfigurator, and an IntegratedMultiVisualizer
module. The nodes’ default PHY model (IEEE 802.11) will suffice because
we’re focusing on the routing protocols.
In all three simulations, the source node pings the destination node.
The two nodes are out of communication range of each other, and the
other nodes are responsible for forwarding packets between the two.
Since routes are managed dynamically by the MANET routing algorithms,
the Ipv4NetworkConfigurator module is instructed not to add any
routes (it will only assign IP addresses). The netmask routes added by
network interfaces are disabled as well. The following keys in the
General configuration in omnetpp.ini
achieve this:
*.configurator.addStaticRoutes = false
**.netmaskRoutes = ""
AODV¶
The example simulation featuring AODV is defined in the Aodv
configuration in omnetpp.ini. This
configuration uses the ManetProtocolShowcaseA network. The network
looks like the following:
The nodes are scattered on the scene. The source and destination
nodes are stationary, and the other nodes are configured to move in random
directions. The communication ranges are set up so that source
cannot reach destination directly but through the intermediate
nodes. The routing protocols will adapt the routes to the changing
network topology.
The mobility settings are defined in the MobileNodesBase
configuration in omnetpp.ini. The
simulations for AODV and DSDV, which feature moving nodes, are based on
this configuration. The nodes will be moving on linear paths in random
directions with a speed of 25 meters per second, bouncing back from the
edge of the scene. The mobility settings are the following:
*.node*.mobility.typename = "LinearMobility"
*.node*.mobility.initialMovementHeading = uniform(0deg,360deg)
*.node*.mobility.speed = 25mps
**.constraintAreaMaxX = 400m
**.constraintAreaMaxY = 400m
**.constraintAreaMinX = 0m
**.constraintAreaMinY = 0m
The ping app in source will send one ping request every second to
destination.
In INET, AODV is implemented by the Aodv module. This module is configured
in omnetpp.ini as the routing protocol
type in ManetRouter:
*.*.routingApp.typename = "Aodv"
The Aodv module has many parameters for controlling the operation of the protocol. The parameters should be set according to the number of nodes in a network, the nodes’ mobility levels, traffic, and radio transmission power levels/communication ranges. All of the parameters have default values, and Aodv should work out of the box, without setting any of the parameters. We will fine-tune the protocol’s behavior to our scenario by setting two of the parameters:
*.*.routingApp.activeRouteTimeout = 1s
*.*.routingApp.deletePeriod = 0.5s
The activeRouteTimeout parameter sets the timeout for the active
routes. If the routes are not used for this period, they become
inactive. The deletePeriod parameter sets the period after which the
inactive routes are deleted. The activeRouteTimeout parameter is
lowered from the default 3s to 1s, and the deletePeriod parameter is
lowered from the default 15s to 0.5s to make the protocol react
faster to the rapidly changing network topology. Higher mobility results
in routes becoming invalid faster. Thus the routing protocol can work
better - react to topology changes faster - with lower timeout values.
However, setting the timeout values too low results in increased routing
protocol overhead.
Successful data link layer transmissions are visualized by colored arrows. Note that only the routing protocol and ping packets are visualized, not the ACKs. Here is what happens in the video:
At the beginning of the simulation, source queues a ping request
packet for transmission. There are no routes for destination, so it
broadcasts an AodvRreq message. The RREQ is re-broadcast by the
adjacent nodes until it gets to destination. The destination node
sends a unicast AodvRrep. It is forwarded on the reverse path the
RREQ message arrived on
(destination->``node6``->``node1``->``source``). As the intermediate
nodes receive the RREP message, the routes to destination are
created. The routes are visualized with black arrows, and the
RoutingTableVisualizer is configured to visualize only the routes
leading to destination. When the route is established in source,
it sends the ping request packet, which gets to the destination. The
ping reply packet gets back to source on the reverse path.
When source sends the next ping request packet, host6 has already
moved out of range of destination. The ping packet gets to
host6, but can’t get to destination (host6 tries to transmit
the packet a few times, but it doesn’t get an ACK). So host6
broadcasts an AodvRerr message, indicating that the link no longer
works. When the RERR gets back to host1, it initiates route discovery
by broadcasting an RREQ message. When a new route is discovered
(source->``node1``->``destination``), the ping traffic can continue.
The following log excerpt shows node6 handling the first RREQ and
RREP messages:
DSDV¶
The example simulation featuring DSDV is defined in the Dsdv
configuration in omnetpp.ini. Just like
the AODV configuration, this one uses the
ManetRoutingProtocolsShowcaseB network. The mobility settings are
also the same as in the AODV simulation. The ping app in source will
send a ping request every second.
The DSDV protocol is implemented in the Dsdv module. The routing protocol type in all hosts is set to Dsdv:
*.*.routing.typename = "Dsdv"
Currently, complete routing table broadcasts are not implemented, only the broadcasting of changes in the routing table using periodic hello messages.
Like Aodv (and most routing protocol modules), Dsdv has many parameters with default values that yield a working simulation without any configuration. In this simulation, similarly to the previous one, we set two parameters of the protocol:
*.*.routing.helloInterval = 1s
*.*.routing.routeLifetime = 2s
The helloInterval parameter controls the frequency of the periodic
updates, or hello messages. Setting this parameter to a higher value
decreases the protocol overhead, but the network will react more slowly
to changes in topology. We lower it from the default 5s to 1s
to make the network more adaptive to rapid changes. When a route is not
used or updated after a time, it gets deleted. The routeLifetime
parameter sets after how long the routes are deleted after not being
used or updated anymore. We lower this from the default 5s to 2s.
The following video shows the nodes sending hello messages and routes being created at the beginning of the simulation. Note that the black arrows represent routes, and routes from all nodes to all destinations are visualized here.
The following video shows source pinging destination:
GPSR¶
The example simulation featuring GPSR is defined in the Gpsr
configuration in omnetpp.ini. It uses the
ManetRoutingProtocolsShowcaseB network. The network looks like the
following:
Just as with the previous two configurations, the nodes are
ManetRouters. The nodes are laid out along a chain. The
transmitter power of the radios is configured so that nodes can only
reach their neighbors in the chain (except for node9, which can reach
nodes 11, 5, and 8). There is a forest, which represents a void that GPSR
can route around. In this example simulation, the nodes will be static
(though GPSR is suitable for scenarios with moving nodes). The source
node will ping the destination node, which is on the other side of the
void. (The ping app in source will send one ping request every
second.)
The hosts’ routing protocol type is set to Gpsr:
*.*.routing.typename = "Gpsr"
The following video shows running the simulation from the beginning:
The nodes start sending out GPSR beacons (and learning about the
positions of their neighbors). Then, source sends a ping request
packet. It gets forwarded along the chain to node9, which sends it
to node5, as it is the closest to destination among node9’s
neighbors. However, node5 doesn’t have any neighbors closer to the
destination (and it is out of range of destination), thus it
switches the packet to perimeter mode. It forwards the ping packet
according to the right-hand rule. The packet gets to node1 and then
back up along the chain through node9 again. Then node10
switches it back to greedy routing mode because node10 is closer to
the destination than node5, where it was switched to perimeter mode.
Then the packet arrives at destination.
The reply packet starts off in perimeter mode, as the destination is
closer to source than destination’s only neighbor, node4.
The packet is switched back to greedy mode at node10 because it’s
closer to source than destination. From there, it gets to source
through node9 and node11.
Note that the reply packet didn’t get back on the same route as the request packet. Also, a packet is might not be routed to a closer neighbor because the sender doesn’t yet know about it (and its position).
Also, note that there are no IP routes; the ipv4 module routing
tables are empty. Instead, Gpsr maintains the positions of the nodes
in communication range (those that a beacon was received from) and uses
that for routing decisions. Here is node12’s neighbor position
table:
The table links node positions with IP addresses (it also contains the beacon arrival time).
Further information¶
The following papers describe the three MANET routing protocols featured in this showcase:
Sources: omnetpp.ini, ManetProtocolsShowcase.ned
Try It Yourself¶
If you already have INET and OMNeT++ installed, start the IDE by typing
omnetpp, import the INET project into the IDE, then navigate to the
inet/showcases/routing/manet folder in the Project Explorer. There, you can view
and edit the showcase files, run simulations, and analyze results.
Otherwise, there is an easy way to install INET and OMNeT++ using opp_env, and run the simulation interactively.
Ensure that opp_env is installed on your system, then execute:
$ opp_env run inet-4.0 --init -w inet-workspace --install --chdir \
-c 'cd inet-4.0.*/showcases/routing/manet && inet'
This command creates an inet-workspace directory, installs the appropriate
versions of INET and OMNeT++ within it, and launches the inet command in the
showcase directory for interactive simulation.
Alternatively, for a more hands-on experience, you can first set up the workspace and then open an interactive shell:
$ opp_env install --init -w inet-workspace inet-4.0
$ cd inet-workspace
$ opp_env shell
Inside the shell, start the IDE by typing omnetpp, import the INET project,
then start exploring.