Mobile Ad Hoc Networks

This post should be my first post in this blog.

A mobile ad-hoc network (MANET) is a kind of wireless ad-hoc network, and is a self-configuring network of mobile routers (and associated hosts) connected by wireless links – the union of which form an arbitrary topology. The routers are free to move randomly and organize themselves arbitrarily; thus, the network's wireless topology may change rapidly and unpredictably. Such a network may operate in a standalone fashion, or may be connected to the larger Internet.

Mobile ad-hoc networks became a popular subject for research as laptops and 802.11/Wi-Fi wireless networking became widespread in the mid to late 1990s. Many of the academic papers evaluate protocols and abilities assuming varying degrees of mobility within a bounded space, usually with all nodes within a few hops of each other, and usually with nodes sending data at a constant rate. Different protocols are then evaluated based on the packet drop rate, the overhead introduced by the routing protocol, and other measures.

The Children's Machine One Laptop per Child program has developed a cheap laptop for mass distribution (>1 million at a time) to developing countries for education. The laptops will use IEEE 802.11s based ad hoc wireless mesh networking to develop their own communications network out of the box.

Vehicular Ad Hoc Networks (VANET) are a form of MANETs used for communication among vehicles and between vehicles and roadside equipment.

Intelligent vehicular ad hoc network (InVANET) is a kind of Intelligence in Vehicle(s) which provide multiple autonomic intelligent solutions to make automotive vehicles to behave in intelligent manner during vehicle-to-vehicle collisions, accidents, drunken driving etc. InVANET uses WiFi IEEE 802.11 b/802.11g/802.11p and WiMAX IEEE 802.16 for providing easy, accurate, effective communication between multiple vehicles on dynamic mobility. Effective measures to track the automotive vehicles, media download /upload, conference between vehicles are also preferred. InVANET can also be applied for artillery vehicles during warfare, battlefield, and peace-time operations. Mesh networking in mobile applications have been demonstrated in multiple military scenarios.[1]

In September 2007, the Swedish company TerraNet AB presented a mesh network of mobile phones allowing for the routing of calls and data between participating hand sets, without the need to involve cell sites [Source].

DSR

The Dynamic Source Routing protocol (DSR) is a simple and efficient routing protocol designed specifically for use in multi-hop wireless ad hoc networks of mobile nodes. DSR allows the network to be completely self-organizing and self-configuring, without the need for any existing network infrastructure or administration.

DSR has been implemented by numerous groups, and deployed on several testbeds. Networks using the DSR protocol have been connected to the Internet. DSR can interoperate with Mobile IP, and nodes using Mobile IP and DSR have seamlessly migrated between WLANs, cellular data services, and DSR mobile ad hoc networks.

The protocol is composed of the two main mechanisms of "Route Discovery" and "Route Maintenance", which work together to allow nodes to discover and maintain routes to arbitrary destinations in the ad hoc network. All aspects of the protocol operate entirely on-demand, allowing the routing packet overhead of DSR to scale automatically to only that needed to react to changes in the routes currently in use.

The protocol allows multiple routes to any destination and allows each sender to select and control the routes used in routing its packets, for example for use in load balancing or for increased robustness. Other advantages of the DSR protocol include easily guaranteed loop-free routing, support for use in networks containing unidirectional links, use of only "soft state" in routing, and very rapid recovery when routes in the network change. The DSR protocol is designed mainly for mobile ad hoc networks of up to about two hundred nodes, and is designed to work well with even very high rates of mobility (Source).

SAODV

In an ad hoc network, from the point of view of a routing protocol,

there are two kinds of messages: the routing messages and the data
messages. Both have a different nature and different security needs.
Data messages are point-to-point and can be protected with any point-
to-point security system (like IPSec). On the other hand, routing
messages are sent to immediate neighbors, processed, possibly
modified, and resent.

Another consequence of the nature of the transmission of routing
messages is that, in many cases, there will be some parts of those
messages that will change during their propagation. This is very
common in Distance-Vector routing protocols, where the routing
messages usually contain a hop count of the route they are requesting
or providing. Therefore, in a routing message one could distinguish
between two types of information: mutable an non-mutable. It is
desired that the mutable information in a routing message is secured
in such a way that no trust in intermediate nodes is needed.
Otherwise, securing the mutable information will be much more
expensive in computation, plus the overall security of the system
will greatly decrease.

Moreover, as a result of the processing of the routing message, a
node might modify its routing table. This creates the need for the
intermediate nodes to be able to authenticate the information
contained in the routing messages (a need that does not exist in
point-to-point communications).

SAODV is an extension of the AODV routing protocol that protects
the route discovery mechanism providing security features like
integrity and authentication. It uses digital signatures to
authenticate the non-mutable fields of the messages, and hash chains
to secure the hop count information (the only mutable information in
the messages).

SAODV can use the Simple Ad hoc Key Management (SAKM) as a key
management system. (Related link)

AODV

The Ad hoc On Demand Distance Vector (AODV) routing algorithm is a routing protocol designed for ad hoc mobile networks. AODV is capable of both unicast and multicast routing. It is an on demand algorithm, meaning that it builds routes between nodes only as desired by source nodes. It maintains these routes as long as they are needed by the sources. Additionally, AODV forms trees which connect multicast group members. The trees are composed of the group members and the nodes needed to connect the members. AODV uses sequence numbers to ensure the freshness of routes. It is loop-free, self-starting, and scales to large numbers of mobile nodes.

AODV builds routes using a route request / route reply query cycle. When a source node desires a route to a destination for which it does not already have a route, it broadcasts a route request (RREQ) packet across the network. Nodes receiving this packet update their information for the source node and set up backwards pointers to the source node in the route tables. In addition to the source node's IP address, current sequence number, and broadcast ID, the RREQ also contains the most recent sequence number for the destination of which the source node is aware. A node receiving the RREQ may send a route reply (RREP) if it is either the destination or if it has a route to the destination with corresponding sequence number greater than or equal to that contained in the RREQ. If this is the case, it unicasts a RREP back to the source. Otherwise, it rebroadcasts the RREQ. Nodes keep track of the RREQ's source IP address and broadcast ID. If they receive a RREQ which they have already processed, they discard the RREQ and do not forward it.

As the RREP propagates back to the source, nodes set up forward pointers to the destination. Once the source node receives the RREP, it may begin to forward data packets to the destination. If the source later receives a RREP containing a greater sequence number or contains the same sequence number with a smaller hopcount, it may update its routing information for that destination and begin using the better route.

As long as the route remains active, it will continue to be maintained. A route is considered active as long as there are data packets periodically travelling from the source to the destination along that path. Once the source stops sending data packets, the links will time out and eventually be deleted from the intermediate node routing tables. If a link break occurs while the route is active, the node upstream of the break propagates a route error (RERR) message to the source node to inform it of the now unreachable destination(s). After receiving the RERR, if the source node still desires the route, it can reinitiate route discovery.

Multicast routes are set up in a similar manner. A node wishing to join a multicast group broadcasts a RREQ with the destination IP address set to that of the multicast group and with the 'J'(join) flag set to indicate that it would like to join the group. Any node receiving this RREQ that is a member of the multicast tree that has a fresh enough sequence number for the multicast group may send a RREP. As the RREPs propagate back to the source, the nodes forwarding the message set up pointers in their multicast route tables. As the source node receives the RREPs, it keeps track of the route with the freshest sequence number, and beyond that the smallest hop count to the next multicast group member. After the specified discovery period, the source node will unicast a Multicast Activation (MACT) message to its selected next hop. This message serves the purpose of activating the route. A node that does not receive this message that had set up a multicast route pointer will timeout and delete the pointer. If the node receiving the MACT was not already a part of the multicast tree, it will also have been keeping track of the best route from the RREPs it received. Hence it must also unicast a MACT to its next hop, and so on until a node that was previously a member of the multicast tree is reached.

AODV maintains routes for as long as the route is active. This includes maintaining a multicast tree for the life of the multicast group. Because the network nodes are mobile, it is likely that many link breakages along a route will occur during the lifetime of that route. The papers listed below describe how link breakages are handled. The WMCSA paper describes AODV without multicast but includes detailed simulation results for networks up to 1000 nodes. The Mobicom paper describes AODV's multicast operation and details simulations which show its correct operation. The internet drafts include descriptions of both unicast and multicast route discovery, as well as mentioning how QoS and subnet aggregation can be used with AODV. Finally, the IEEE Personal Communications paper and the Infocom paper details an in-depth study of simulations comparing AODV with the Dynamic Source Routing (DSR) protocol, and examines each protocol's respective strengths and weaknesses. (Source)