Re-Examination Of Protocols For Mobile Ah Hoc Network

A mobile ad hoc network is a multi-hop wireless network with dynamically and frequently changing topology. In recent years, with the development of mobile ad hoc networks (MANETs) technology, various multicast routing protocols such as On Demand Distance Vector Routing Protocol (AODV), AODV with break avoidance (AODV-BR), Scalable Multipath On Demand Routing (SMORT) protocol, DMSR have been proposed for MANETs. Most of the routing protocols, however, use a single route and do not utilize multiple alternate paths. These protocols have distinguishing features and different applications. This paper provides a control study of many different Routing Protocols by presenting their characteristics and functionality .We also focus on some applications of these protocols.

1.    Introduction: A mobile Ad Hoc Network (MANET)[1] is a multi-hop wireless network with dynamically and frequently changing topology. The energy, power and bandwidth constraint of these self operating and self organized systems has made routing a challenging problem. Various routing protocols have been proposed for mobile ad hoc networks. Such, protocols must deal with the typical limitations of these networks which, include: low bandwidth, high power consumption and high error rates.

When the packet switching technology, the fabric of the Internet was introduced with the ARPANET in 1960, the Department of Defense immediately understood the potential of packet switched radio technology to interconnect mobile nodes in the battlefield. The term “ad hoc” implies that this network is a network established for a special, often extemporaneous service customized to application so the typical ad hoc network is set up for a limited period of time. Routing protocols proposed for mobile ad hoc wireless networks can be generally categorized by the routing strategy. There are some protocols like On demand routing protocol, DSR etc are proposed for ad hoc networks only. On-demand routing protocols do not maintain route to each destination of the network on a continual basis; instead, routes are established on demand by the source. Control traffic overhead is greatly reduced in on-demand routing protocols, since no periodic exchanges of route tables are required.


In MANET, multicast can efficiently support a variety of applications that are characterized by close collaborative efforts. A multicast packet is typically delivered to all members of its destination group with the same reliability as regular unicast packets. When a user is walking with a handheld device or waiting for metro in a railway terminal. He/ she  does  not know  about his/ her neighbor, and switches on the handheld device and tries to scan the network to detect if someone would be interested in playing games or start a similar application of interest. This kind of community-centric application draws a lot attention in the data communication world. Multicast routing protocols for ad hoc networks have been proposed [] []  AMRoute, CAMP,DDM in order to save the node resource and network bandwidth because they are the protocols for powerful communication used in multi-hop applications and are more efficient than the approach of sending the same information from the source
 
On Demand Routing Protocols: - Reactive routing protocols can be divide into following categories:       1>   hop by hop routing
                                     2>   Source routing
In hop by hop routing, each data packet carries only the destination address and the next hop address. Routing tables maintained at each intermediate node are updated whenever, fresh topology information is available. The inclusion of complete address in the packet header of each data packet makes source routing inefficient in large network scenarios with high mobility and multiple hops. Thus, hop by hop routing is adaptable to dynamic varying network topology due to the use of fresher and better routes. AODV represents the class of reactive routing protocol. A number of modifications have been done on AODE to increase its performance in teems of various parameters like: routing latency, packet delivery ratio, routing overhead etc.
Routing protocol can be broadly categorized into two types as follow:-
1-    Conventional routing protocols
2-    Optimizations on AODV Routing protocols

2.    Conventional routing protocols: The progress in the field of ad hoc routing protocols includes the development of number of algorithms such as : AODV[2], Dynamic source Routing[3],Cluster Based Routing protocol(CBRP)[5], Signal Stability based Adaptive Routing(SSA)[4] etc. The basic idea of these algorithms is to find and maintain a route when it is required for communication. a>Dynamic Source Routing (DSR) was developed at Carnegie Mellon University. It uses source routing instead of hop-by –hop packet routing, each data packet carries the list of routers in the path. The main benefit of source routing is that intermediate notes need not keep route information because the path is explicitly specified in the data packet. DSR does not require any kind of periodic message to be sent, supports asymmetric and uni-directional links, and set up routes based on demand by the source.
The working of Dynamic Source Routing consists of two phases as:
i-    Route Discovery
ii-    Route Maintenance

Route Discovery and Route Maintenance each operate entirely on demand. DSR  does not use any periodic routing advertisement, link status sensing or neighbor detection packets and does not rely on these functions from any underlying protocols in the network. This entirely on demand behavior and lake of periodic activity allows the number of overhead packets caused by dynamic source routing to scale all the way down to zero, when all nodes are approximately stationary with respect to each other and all routes needed for current communication have already been discovered. As nodes begin to move more or as communication patterns change, the routing packet overhead of DSR automatically scales to only that needed to track the routes currently in use.
b>Dynamic multi-path  source routing (DMSR) Multi-path source routing (MSR)[7,8] extends DSR’s route delivery and route maintenance phases to compute multiple node disjoint paths. Lee el at [6] proposed Split Multi-path Routing which uses modified flooding algorithm and balances the transmission by splitting data among multiple paths to avoid network congestion. Thus, a dynamic multi-path source routing protocol is proposed to improve existing on-demand routing protocols. It consists of three main phases, namely, multi-path routing selection, routing discovery and routing maintenance.
In multi-path routing selecting phase, ideal number of multi-path routing is achieved to compromise between network overhead and load balancing.

c>Ad Hoc On Demand distance Vector Routing (AODV): AODV adopts the concept of using conventional routing tables to store the route between a source destination  routing tables to store the route between a source destination pair unlike DSR[8] which can maintain multiple route cache entries for each destination. Thus, AODV [3] routing protocol overcomes the drawback of DSR as the former scales well in large networks. In the route discovery cycle, RREQ packets are broadcasted on symmetric links to its neighbors, who then forward the request to their neighbors and so on , until either the destination or an intermediate node with a ”fresh-enough” route to the destination is located. A RREP packet is sent back to the neighbor from whom it first received the RREQ. As the RREP is routed back along the reverse path, forward route entries are made in the route tables of these nodes, which point to the node from which the RREP came. Route timer is associated with each route entry, which will cause the deletion of the entry if it is not used within the specified lifetime. RERR is propagated to the source node in the case of link failure, which may then choose to reinitiate route discovery for that destination if a route is still desired. To maintain the location connectivity of a node, Hello message can be used.
Various multi-path protocols based on distance vector routing scheme are also proposed for ad hoc networks. Valera et al.[10] uses  multi-path routing to reduce the number of packet drops caused  by route breaks. Saha et al. [6] proposed the use of zone disjoint path for traffic load balancing to minimize congestion in the network.[11-14] uses the concept  of node disjoint path to give better packet delivery ratio, increased robustness against route breaks and reduced latency. Ducatelle et al. [15] uses a hybrid multi-path routing based on ant colony optimization framework for traffic load balancing.
3.    Optimizations ON AODV Routing Protocol: The Routing protocols which are described previous has their own advantages but still there are certain limitations attached to each one of them. Due to the use of aggressive source routing, DSR cannot be used in large network conditions. AODV is suited for almost all kind of networks but has more routing load both route repair and at the time of route discovery. If certain extensions or optimizations are done on the base of AODV protocol then the problem of more control latency, scalability and overhead can be to a great extent.

a>    AODV with Break Avoidance (AODV-BR): RREQ is flooded into the network in the route recovery phase. To detect and drop duplicate packets, each RREQ packet carries a unique identifier. An intermediate node records the source node information and the previous hop in its route table on receiving a non-duplicate RREQ. RREP is sent back to the source upon reception of first or subsequent RREQs by any intermediate node having route to destination. If it is within the transmission range of more than one intermediate node of primary route, a node may receive numerous RREPs. Subsequent RREPs received by source forms an entry for alternate routes. A one hop broadcast is made to immediate neighbors and the primary route is replaced by the alternate route in a way to prevent loops, when a link break occurs. Through one or more alternate routes, data packets are transmitted and are not dropped when the route break occurs; the node that detects the link break also sends a RERR to the source node to initiate a route discovery. To distinguish between the fresh and stale routes Timer mechanism is used. Routing overhead of AODV-BR is same as that of AODV and packet delivery ration is more because it uses a longer route to deliver the packets that are dropped in AODV.AODV-BR is an extension to the uni-path AODV routing protocol.

b> Scalable Multi-path On Demand Routing (SMORT): SMORT computes multiple fail safe paths and it is a multipath extension to AODV routing protocol. A path between source and destination is said to be fail safe to the primary path if it bypasses at least one intermediate node on the primary path. Fail safe paths can have both links and nodes in common. The routing process of SMORT can be categorized into three phases: route discovery, route reply and route maintenance. The route discovery phase of SMORT is same as that of the route discovery phase of AODV except the fact that in SMORT, RREQ packet does not have any destination sequence numbers and nodes can accept multiple RREQ packets for computation of multiple fail safe paths and can rebroadcast only the first RREQ. In the route discovery cycle the protocol computes fail safe paths, as it reduces the route recovery time and path maintenance overhead more effectively. The fail safe paths have higher fault tolerance.

To compute multiple fail safe paths and to avoid routing loops, three extra fields RREP contains: node-list, reply-gen and mul-reply. It is replaced by a valid secondary route in case of invalidated route to the destination, if one exists. Otherwise, to the source node through the nodes in the precursor list of the destination’s route entry, RERR is sent, which then initiates a fresh route discovery cycle to reestablish routes to the disconnected destination. In comparison to base AODV protocol, SMORT has better throughput and less routing overhead even in larger networks.

Multicast Routing Protocols: Multicast routing protocols for ad hoc networks have been proposed in order to save node resource and the network bandwidth because they are the protocols for powerful communication used in multi-hop applications and are more efficient than the approach of sending the same information from the source to each of the receivers individually. Such protocols must deal with the typical limitations of these networks, which include high error rates, low bandwidth and high power consumption.
Several multicast routing protocols have been proposed for MANETs, which can be classified in four types according to their multicast delivery structure:

1>    Overlay multicast schemes[]
2>    Stateless schemes[]
3>    Mesh-based schemes[]
4>    Tree-based schemes[]
The multicasting function is not provided by network layer in the overlay multicast; instead, a virtual overlay network among the multicast group members is built on the top of the physical network. With the tree-based scheme, all the routes form a tree infrastructure with the source node as the route, thus there is an only one single path between every pair of sender and receiver. However, mesh-based scheme can support more robust route through multiple redundant routes, but resource are wasted as a result of unnecessary forwarding of duplicate data. Both discussed schemes lead to partial inefficient for group communication. Thus two approaches have been proposed to enhance the performance of group communication; first one is an overlay multicast and second one is a stateless multicast.

a> AM Route: For MANETs Ad Hoc Multicast Routing Protocol (AM Route) [9] was the first multicast routing protocol, which uses an overlay for multicast data forwarding. The overlay is created in two step process first one is mesh creation and second one is tree creation.
The ad hoc multicast routing protocol continuously creates a mesh of bidirectional tunnels between a pair of group members that are close together. By using a subset of the available virtual mesh links, the protocol periodically creates a multicast distribution tree and only logical core nodes initiate mesh and tree creation, while the tree is periodically optimized by a recreation, the mesh is not optimized. It shows that AM Route is quite ineffective if mobility increases. Non optimization of the mesh leads to a delivery structure which becomes more inefficient over time. Another proactive tree-based protocol is an AMRIS. Its key idea is that each node is tagged with a multicast session member ID, which provides a logical height and builds a DAG, rooted from the Sid. Where Sid is a special node the broadcasts a New-session message including the Sid’s msm-ID when a new multicast session begins. Some other multicast routing protocols are as follow; progressively Adapted Sub-Tree in Dynamic Mesh (PAST-DM), Overlay Boruvka-based Ad-Hoc Multicast Protocol (OBAMP), A Robust Efficient Overlay Multicast Protocol (AREMP) and Application Layer Multicast Algorithm (ALMA) etc.

b>Core-Assisted Mesh Protocol (CAMP) [16] is proactive mesh-based multicast protocol. A node wishing to join a multicast group first determines if it has neighbors that are already mesh members. If so, the node announces its membership via a CAMP Update. Otherwise, the node either propagates a Join Request towards one of the cores, or attempts to reach a node in the mesh by broadcasting the requests. CAMP defines two types of members in the mesh: duplex member or simplex member. A duplex member can send and receive multicast data packets, while a simplex member can only send out data packets .So only duplex members can respond with a Join Ack, propagated back to the source of the request. If so, a heartbeat message is sent to the source along the new shortest path. If any node on the path is not a member of the mesh, then a push join message forces the nodes to become mesh members. Therefore, CAMP must rely on a unicast routing protocol, which guarantees correct distances to all the destinations within finite time.

c>Differential Destination multicast (DDM):
In DDM, [17] the multicast data packets contain a payload and a DDM header, which is composed of list of DDM blocks. Each DDM block is constructed for a particular downstream neighbor. Each DDM block contains the intended receiver, the DDM block type, the block sequence number and some other fields depending on the type. There are three types of the DDM blocks: Empty (E) blocks, Refresh (R) blocks and difference (D) blocks. Excepts for the E blocks, both R and D blocks have a destination list L. when used in broadcast media networks, DDM blocks of different downstream neighbors may be aggregated together into the header of one data packet. When the intended neighbors receive the data packet, each neighbor can locate the correct DDM block and the destination list for itself. Each node maintains one forwarding set (FS) for each active multicast session. It records to which destination this node needs to forward multicast data.

4.    Application: Application of On-demand protocol is to use the internet to interactively communicate with one another through Internet telephony and Internet teleconferencing .Interactive audio/Video refers to the use of the Internet for interactively audio/video applications.
Multicasting has many applications today such as access to:
>Distributed database
>Information Dissemination
>Teleconferencing
>Distance learning.

5.    Conclusion: The choice of routing protocol should be done carefully according to the requirements of the specific application because a single protocol cannot perform best in all kind of networks. This paper covers some important protocols for mobile Ad Hoc Networks Each protocol has its own advantage, disadvantages and also their applications.

6.    References:
1.    Don Galatchi; Roxana Zoican” On-Demand Multicast routing protocols in Dynamic Ad Hoc Networks”.
2.    C.E. Perkins, E.M. Belding-Royer, and S.R. Das, (2003) "Ad Hoc On-Demand Distance Vector (AODV) Routing," http://www.ietf.org/rfc/ rfc3561.txt, July 2003. RFC 3561.
3.    D. Johnson and D. Maltz, (1996) "Dynamic Source Routing in Ad Hoc Wireless
Networks," Mobile Computing, Chapter 5, Kluwer Academic: Hingham, MA, USA.
4.    M. Jiang, J. Ji,and Y.C. Tay, (1999) "Cluster Based Routing Protocol," Internet Draft, draft-ietf-manet-cbrp-spec-01.txt, work in progress.
5.    Azzedine Boukerche, (2004) "Performance Evaluation of Routing Protocols for Ad Hoc Wireless Networks," Kluwer Mobile Networks and Applications, vol. 9, pp. 333-342.
6.    S.-J. Lee and M. Gerla, (2001)"Split Multipath Routing with Maximally Disjoint Paths in Ad Hoc Networks," Proceedings of IEEE International Conference on Communications 2001, vol. 10, pp. 3201-3205, June.
7.    L. Wang, Y. Shu, M. Dong, L. Zhang, and O.W.W. Yang,(2001)"Adaptive Multipath Source Routing in Ad Hoc Networks," Proceedings of IEEE International Conference on Communications, vol. 3, pp. 867-871, June.
8.    L. Wang, L. Zhang, Y. Shu, and M. Dong, (2000)"Multipath Source Routing in Wireless Ad Hoc Networks," Proceedings of Canadian Conference on Electrical and Computer Engineering- 2000, vol. 1, pp. 479-483, March.
9.    Liu, M.; McAuley, A.; and Talpade, R, (2002)"AMRoute: Ad-hoc Multicast Routing Protocol", Mobile Networks and Applications 7, 429-439,
@2002 Kluwer Academic Publishers.
10.    A. Valera, W.K.G. Seah, and S.V. Rao, (2003)"Cooperative Packet Caching and Shortest Multipath Routing in Mobile Ad Hoc Networks," IEEE INFOCOM 2003, pp. 260-269, April.
11.    Y. Liang and S.F. Midkiff,(2005) "Multipath Fresnel Zone Routing for Wireless Ad Hoc Networks," Proceedings of IEEE Wireless.
12.    Communications and Networking Conference, vol. 4, pp. 1958-1963, March 2005. 
13.    Z. Ye, S.V. Krishnamurthy, and S.K. Tripathi,(2004) "A Routing Framework for Providing Robustness to Node Failures in Mobile Ad Hoc Networks," Journal of Ad Hoc Networks, vol. 2, no. 1, pp. 87-107.
14.    A.M. Abbas and B.N. Jain, (2004) "Path Diminution in Disjoint Multipath  Routing for Mobile Ad Hoc Networks," Proceedings of 15th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, vol. 1, pp. 130-134, September.
14.N. Wisitpongphan, and O.K. Tonguz, (2003)"Disjoint Multipath Source Routing in Ad Hoc Networks: Transport Capacity," Proceedings of IEEE 58th Vehicular Technology Conference, vol. 4, pp. 2207-2211, October.
15.    F. Ducatelle, G.D. Caro, and L.M. Gambardella,(2005) "Ant Agents for Hybrid Multipath Routing in Mobile Ad Hoc Networks," Proceedings of the Second Annual Conference on Wireless On Demand Network Systems and Services (WONS), January.
16.    J.J.Garcia-Luna-Aceves and Ewerton L. Madruga (1999) “The Core-Assisted Mesh Protocol Selected Areas in Communications, IEEE Journal on Volume 17, Issue 8, Aug 1999 Page(s):1380 – 1394
17.    Lusheng Ji and M. Scott Corson Institute for System Research University of Maryland “Differential Destination Multicast-A MANET Multicast Routing Protocol for Small Groups http://www.ieeeinfocom.org/2001/paper/278.ps