Mobile Adhoc Networking MANET Part 1

We will outline Mobile Ad hoc Network technology in this post. 

Content of this post is as follows ;

1) Introduction and Motivation
2) How is Routing in Mobile Adhoc Networks
3) Selected Routing Protocols (1)
* Ad hoc on-demand distance vector routing protocol ( AODV ) 

1) Introduction and Motivation

 

Let's first talk about wired and wireless networks 

 These aspects are explained pretty well by Julien Thomas. Let's see his explaination.

During the past years, wireless networks have widespread due to new technologies such as BlueTooth [IEEE 802.15] and WiFi [IEEE 802.11]. Contrary to wired networks, these networks do not rely on physical links. They can thus provide new services, such as easy access to the Internet (using hotspots^1.1) or access to private networks (domestic or professional) without having to install cables. However, this mean of communication calls into question several assimilated notions in wired networks. For instance, as anybody can try to access to the network or to eavesdrop communications, access management have to be reconsidered. Moreover, some wireless networks do not rely on a logic infrastructure, which complicates the problem, for instance for the services management, as presented in the next section. 
http://master.julienthomas.eu/rapports/html/rapport-node8.html ////

Differences between several wireless networks

Due to the fact that they are used to provide high level services, such as Internet connexions, the most widespread wireless networks are those relying on an infrastructure. As their names suggest, these networks are built in a logic way, respecting a stable infrastructure, in particular for the routing management. Thus, all the administration functions are managed by an Internet Service Provider (ISP), which provides a simple and reliable service.

The wireless networks without infrastructure are auto-built networks. These networks (called MANET ^1.2, Mobile Ad hoc NETwork) rely on network's nodes to satisfy all the network functioning's needs, in particular the routing politics. The network management is thus dynamic and dependent on its nodes. These networks offer new services, such as easy and fast deployment of systems, without having to envisage an administration structure (the deployment of a communicating captors network is an example of such systems). However, the lack of infrastructure leads to weakness, which can be for example exploited to limit the network availability (see section http://master.julienthomas.eu/rapports/html/rapport-node8.html ////

Wiki says : A mobile ad-hoc network (MANET) is a self-configuring infrastructureless network of mobile devices connected by wireless links. ad hoc is Latin and means "for this purpose".^[1][2]
 

 

http://www.ece.iupui.edu/~dskim/manet/images/adhocnet.gif

All of the devices in the picture above work as a router that directs the traffic to another if it does not need that packet.

Basics

• Principle is to create a communication without any infrastructure . 
• Devices can communicate with each other using short range communication. 
•  Multihop routing is necessary. 
•  Spontaneous networks can be supported by Ad hoc networks
• Self-organizing, mobile and wireless nodes.
• Systems are both terminals (end systems) and routers (nodes)

There are of course some problems, challenges in Ad hoc networks such as dynamics, energy, bandwidth, link asymmetry. We will outline them later in this blog.

Characteristics 

- Dominated by heterogeneity and variability.
- Different routing behaviors of different devices.
- Mobility characteristics ( Speed, predictability ) , Wireless characteristics( limited  range, transmission errors) , application characteristics (P2P , real time) , system characteristics (distribution, absence of infrastructure)  all of them have some effects.
Note : Adaptation is crucial. 

For instance,
I would like to send a message to a mobile device by using adhoc network, however how can I use his IP ? because IP has no topological meaning in this concept,  he moves around so his IP changes all the time ?  This is one of the biggest problems to overcome in adhoc networks.

Some Ad-hoc Applications

- Military applications ( soldiers, tanks , planes ... )
- Civilian applications ( car to car communication, emergency services, sensor networks, ... )

Let's give an example related to home networking;
We do not want to deal with cables at home, right :) generally it is a big mess. Speaker has  a cable to the TV , DVD player has another and so on. Instead of these cables, would not it be great if they communicate with each other without cables ?

Another example can be a system that warns you before something happens. For instance, a system that stops your car before hitting the car in front of it .

Peer to Peer vs AdHoc ?  

People mix these terms . They are similar but not same .
First of all Adhoc network focuses on network layer while P2P focuses on app layer.

P2P networks replicate data and data is distributed widely. It may not be the case in Adhoc networks. 

What about Mesh network ? 

We can say that Mesh network includes both sensor networks and ad hoc networks.

Characteristics ;
- Multihop communication to reach destinations.
- Self-forming , self-healing, self-organizing
- Weak mobility and power constraits.
Compared to Adhoc networks ;
- There is wireless infrastructure
- They enable easy integration of different radio technologies.
- Additional capabilities ;  sophisticated algorithms can be applied.

 

About Ad hoc Routing - 

Why do we need a specialized ad hoc routing ?

1. To deal with topology dynamics caused by mobility
2. To reach nodes that have no direct neighbours. 
3. To match characteristics of wireless communication.
4. To support spontaneous formation of network
5. To operate without fixed infrastructure
6. Because all end systems are also acting as routers 

 What do you think the answer of this question ? which ones would you pick ?

Actually the correct answer is "there is no incorrect option". All of them are the reasons why we need a specialized ad hoc routing.  There are some protocols to meet these requirements. 

Requirements for Ad hoc routing 

The routing protocol needs to deal with these dynamics.
- The routing protocol needs to converge fast !
- It has to minimize signaling overhead.

The routing strategy ( algorithm ) may include ;
- Shortest distance
- Minimum delay
- Minimum loss
- Minimum congestion ( load - balancing )
- Minimal interference
- Maximal signal strength
- Minimum energy (power aware routing )


! Standard Internet routing cannot fulfill these requirements !
- Because Standard Internet routing assumes there is an  infrastructure, symmetrical conditions and  plenty of resources.  ( We have to have more dynamic systems  not Standard Internet routing)


So what can we do ? let's have a look at other routing protocols .

1.  Flooding of Data packets :   A simple solution , but  results in high overhead. Some sensor network application only use flooding. It reaches the destination if there is no disconnection of nodes. There might be some situations that I do not need to do flooding. 
2. Uniform routing protocols :  Each node shares the same responsibility. Each packet has a direct path to the destination. Uniform routing protocol has two paradigms; Proactive (table-driven) and reactive (on-demand) paradigms.  Proactive protocols try to maintain routes all the time. It keeps the track of routes and when the topology happens to change, we already know the  route .    Reactive protocols look for a new route on demand, route discovery is handled on demand. For example, I want to send a package to a neighbour , but I do not know the route. Then I ask the route and see the topology.  Because it looks for the route on demand, there is less overhead compared to proactive protocols.
3. Non-Uniform Protocols. In this protocol, nodes in the network have different tasks to do. While some of them deal with routing management, others might deal with something else.

Note that "There is no protocol for adhoc routing that we can say yes it is the best one to use" .  

 There are many routing protocols. The picture below is just a small part of the whole picture actually.  

There are some much details of these protocols. Each protocol might have a special feature, or operation. If you would like to go into particulars of these protocols, you can find many documentation related to them. However we will only outline some of them in our post.   You may want to check this out for further info; http://en.wikipedia.org/wiki/List_of_ad_hoc_routing_protocols


Based on your needs, you might want to select a specific protocol considering its features.

Selected Routing Protocols (generally  Preferred ones ) 

1) AODV
2) DSR/OLSR/LAR (these have things in common with AODV, that's why we will not cover them in this post)


AODV ( Ad hoc On-demand distance vector protocol )
- Reactive protocol ( on demand )
-  All nodes are treated equally.  ( they share similar responsibilities )
-  Based on distance vector principle  ( I have information about my neighbors and network topology , and I share it among  my neighbors ) so that I have a distance vector to the destination. 
- We have a route discovery cycle in AODV. We first flood-broadcast the route request thorough the network, then destination gets it. And destination replies back with the information available in the nodes' tables.

- Basic principle in AODV is to use 3 messages.
- There is no overhead on data packets.


Status :  Many implementations are available (IPv4, IPv6 )  

Each request has a sequence number, so if a node takes multiple requests coming from same source for same destination then it means it is a duplicate message which will be discarded.  So first routing request is forwarded and others are discarded.

http://www.cse.wustl.edu/~jain/cis788-99/ftp/adhoc_routing/fig4.gif

Let's assume that, Node 1 tries to send a message to the destination 8. Node 1 first sends the request to its neighbours, and its neighbours do so and so on until a route/ some routes are found. Figure a depicts this propagation of Route Request (RREQ) packet . Later, destination replies back from the path which was calculated to be the fast path, the efficient one. In this case, path taken by the Route Reply Packet (RREP) is 8->6->4->1 .

Route Maintenance in AODV 

AODV uses 2 timeouts to keep the route alive ;  one for forward path, one for reverse path. Timeout should be long enough to allow RREP to come back. Otherwise, it might be unfortunate to assume that existing route has disappeared or broken.  ( Default value for time out is 6 seconds ) 

Flooding is used. Because we have no information about the topology, what is the shortest path and so on.  First, I need to search what is going on in the network. Using flooding makes sense for this concept. It can be of course optimized.  However you need to have some extra information for optimization. Briefly we have to use flooding to get to the destination.


It also uses destination sequence numbers to determine fresh routes. By doing so, it can avoid using old/broken routes and prevent formation of loops .

From Matthias Hollick's presentation that he gave in UIO.

You can understand what actions taken in case of a route error. I would like to explain one more time how sequence number works. Defined route has a sequence number (lets say 6 links to go for destination ) , if an error detected, system tries to find >6 (because 6 was the shortest path , and now it tries find another short path  ) .

Note :AODV does not find shortest path in terms of distance , it finds the shortest path in terms of time meaning fastest path. 

From Matthias Hollick's presentation that he gave in UIO.

For instance the graph above,  we plan to reach from source 2 to destination 13 . Green path is taken as the fastest path, while dashed red line was the shortest path in terms of distance. However as you can see, even though the green line (2->20->22-> and so on) is our route,  we also propagate request message in irrelevant part of the graph as well. Red arc includes the unnecessary routes.

So what to do in order to get read of unnecessary messages ?

There are some algorithms for this purpose.
- AODV -LR Local repair .
- AODV - ESP Expanding Ring Search.  ( you do not flood the message through the network if you set time to live as 1 hope , so that it only checks one hope away neighbors )


IF you have a wide - dense network , AODV will fail . Because it is based on broadcasting mechanism , right ;) .

However there are multiple open issues in AODV such as Security , QoS.
These issues are being studied currently.

AODV optimizations - Gossiping (1) 

- We said that that flooding is inefficient if the network is dense.
Gossiping is one of the mechanisms to deal with density.  Gossiping randomly selects subsets of neighbors to send the message. 

AODV Extension - Multipath (2) 

- Instead of dropping duplicate RREQ packets, AODVM uses RREQ table to store all RREQ information in order to have alternative ways of sending the reply back. If the nodes on the way back are mobile , or they fail whatever , why not use multipath.




Resources : The content of this post has been generated from the slides of the presentation that was given by Matthias Hollick in UIO in 2006.