Bandwidth Efficient And Scalable Tree-Based Multicast Routing Protocol For Mobile Ad Hoc Networks

Bandwidth Efficient And Scalable Tree-Based Multicast Routing Protocol For Mobile Ad Hoc Networks

Nehan Mumtaz Master of Technology

Department of Computer Science & Engineering ASET, Amity University, Lucknow

Parul Yadav

Sr. Lecturer, Dept. of Computer Science & Engineering Amity School of Engineering & Technology

Amity University, Lucknow

Abstract

In Mobile Ad-hoc network, wireless nodes are allowed to communicate with each other without any centralized support and without following any fixed infrastructure due to high mobility of nodes and multipath propagations. The group message transferring services are one of the important applications that are adopted by mobile ad hoc networks (MANETs). To support such services, multicast routing is used. To route any packet from source to destination, we must ensure that routing must be reliable and robust in the network. But in MANETs stable multicast routing is difficult due to limited resources and mobility of nodes. In this paper, we have proposed a multicasting approach to develop a stable multicast routing protocol. By offering some modifications over Flooding Algorithm, we involve packet holding time information in the proposed protocol named as BEST-MRP, to reduce bandwidth overhead and providing scalability in the network. Our routing protocol aims at achieving scalability in the network and reducing the bandwidth overhead in the network.

1. Introduction

   Mobile Ad hoc Networks are self-organizing and self- configuring networks composed of mobile nodes without any fixed infrastructure. In a Mobile Ad Hoc Network, nodes move randomly, due to which t h e t o p o l o g y i n t h e network is unpredicted and

   every node in MANET itself act as a router [1]. MANETs play a prominent role in the rapid deployment of independent mobile users, efficient and dynamic communication for emergency/rescue operations, disaster relief efforts, and military networks. Some key challenges in MANETs include Energy-constrained operation, Bandwidth constrained and limitations of network scalability. So, the main characteristics of MANETs are its distributed operation, dynamic topologies and no fixed infrastructure in the network.

   Various MANET Routing Protocols are designed to route packets from Source to single or multiple destinations which are divided into two categories namely, Unicast Routing Protocols and Multicast Routing Protocols. In Unicast Routing Protocol, packet is sent from source to single destination, while in Multicast Routing Protocol, packet is sent from source to multiple destinations. Moreover, Unicast and Multicast Routing Protocols are further broadly classified into three categories, i.e. Reactive, Proactive and Hybrid Routing Protocols. Some of the examples of Multicast Routing Protocols are Multicast Ad-Hoc On- Demand Distance Vector (MAODV)[15], Core- Assisted Mesh Protocol (CAMP)[4], Adaptive Demand- Driven Multicast Routing protocol (ADMR)[16], and On-Demand Multicast Routing Protocol (ODMRP)[18].

   Fig. 1: Mobile Ad hoc Network

   Multicast routing protocols can be as either mesh based or tree based. Chiefly, In a mesh based multicast routing protocol, there exists more than one path between a pair of source and receiver, while in a tree based multicast routing protocol, there exist only a single path between a pair of source and receiver. Earlier various Multicast Routing Protocols have been suggested and studied by many researchers [5], [9],

   [12] which have their own benefits and drawbacks. This paper proposes an idea for an efficient tree-based Multicast Routing Protocol in Mobile Ad hoc Networks named as Bandwidth Efficient and Scalable Tree-based Multicast Routing Protocol (BEST-MRP).

   The paper is organized as follows; Section II discusses some of the Multicast Routing Protocols. Section III presents the related work done by various researchers. Section IV presents the details of the proposed Multicast Routing Protocol for Mobile Ad-hoc Networks. Section V points out some future scope for the proposed protocol and Section VI concludes the paper.

2. Multicast routing protocols

   Multicast Routing is the routing of packets from source to the group of destinations. As Multicast routing protocols can be as either mesh based or tree based, the various Multicasting Tree based Protocols proposed

   so far are Multicast operation of the Ad hoc On demand Distance Vector (MAODV) routing protocol[15], Ad hoc Multicast Routing (AMRoute) [17], Bandwidth Efficient Multicast Protocol [20], and Ad hoc Multicast Routing protocol utilizing Increasing id-numbers (AMRIS) [19]. Some of Mesh based Protocols proposed so far are ODMRP, Core-Assisted Mesh Protocol (CAMP)[25], Forwarded Group Multicast Protocol (FGMP) [21], and Neighbor Aware Ad hoc Multicast routing Protocol (NAMP) [23].

   Fig. 2: Categorization of Multicast Routing Protocols

   Some of the Multicast Routing Protocols are described as follows:

   Tree-based Protocols

   1. Multicast Operation of Ad Hoc On- demand Distance Vector (MAODV)

      The Multicast operation of Ad-hoc On-demand Distance Vector (MAODV) [15] is a reactive tree-based multicast routing protocol. It is an extension of the unicast routing protocol Ad-hoc On-demand Distance Vector (AODV). Three tables are maintained by each node: a Routing Table (RT), a Multicast Routing Table (MRT) and a Request Table. Routing information is stored in RT, IP addresses of the multicast groups, IP address of group leaders, hop counts, group sequence number is contained by MRT and IP addresses of a

      node, which has sent a request and the IP address of the requested multicast group is stored in Request table.

   2. Ad Hoc Multicast Routing (AMRoute)

      The Ad-hoc Multicast Routing (AMRoute) [17] is a tree based multicast routing protocol for mobile ad hoc networks. It depends on the underlying unicast routing protocol and its working takes place in two key phases: mesh creation and tree creation. In AMRoute, bi- directional unicast tunnels are created continuously between pairs of group numbers that are close to each other which forms a mesh for the multicast group and for each multicast group, a multicast distribution tree is constructed periodically on the mesh links available. AMRoute is efficient by constructing a shared tree for each group.

   3. Ad Hoc Multicast Routing Protocol Using Increasing Id-numbers (AMRIS)

      The AMRIS [19] is a proactive shared tree based multicast routing protocol, which does not depend on the underlying unicast routing protocol. In AMRIS, the new concept of a session specific multicast session member id (msm-id) is given which is assigned to each node in the multicast session. The msm-id is calculated by every node initially, and initiated by a source node containing a special id known as Sid. Sid contains the minimum value.

   4. Differential Destination Multicast (DDM)

      The Differential Destination Multicast (DDM) [27] is an efficient source based tree approach which is designed for only small multicast group. In this protocol, source node has the knowledge of all the members of the multicast group as their information is embedded in the data packets which are to be transferred to the destinations. DDM falls under the category of stateless multicast protocols since no multicast routing information is required to be maintained by the intermediate nodes in the network. It depends on the underlying unicast routing protocol for forwarding the packets from source to destinations.

      Mesh-based Protocols

   5. On-demand Multicast Routing protocol (ODMRP)

      The On-Demand Multicast Routing Protocol (ODMRP)

      [18] is a reactive mesh based multicast routing protocol. The key concept used in ODMRP protocol is the forwarding group concept for the transmission of multicast packets. Each multicast group in the network is associated with a forwarding group FG. The main advantage of ODMRP is that it reduces the overhead in the network.

      Fig. 3: Forwarding Group Concept in ODMRP

      Every node in the multicast group is in charge of the forwarding group and establishes the multicast route whenever demanded.

   6. Core-Assisted Mesh Protocol (CAMP)

      The Core-Assisted Mesh protocol (CAMP) [25] is a proactive multicast routing protocol which is based on the concept of shared meshes. CAMP depends upon the underlying unicast routing protocol through which each node maintains a routing table. Another Multicast Routing Table (MRT) is maintained that contains the set of known groups. MRT is based on the Routing Table maintained by each node. In the multicast session, a node can leave the group any time if it is not interested in the multicast session.

      Fig. 5: Traffic flow from non-member sources in CAMP

      2.8 NAMP: Neighbor Aware Multicast Routing

      Protocol for Mobile Ad Hoc Networks

      Neighbour Aware Multicast Routing Protocol for Mobile Ad Hoc Networks (NAMP) [23] is an efficient tree-based multicast routing protocol which includes the neighbouring concept. Routes are built and maintained using request and reply messages by the forwarding nodes. NAMP uses neighbour information of two-hops away for forwarding the packets to the receiver(s).

      2.7 Forwarding Group Multicast Protocol (FGMP)

      Forwarding Group Multicast Protocol (FGMP) [21] keeps track of group of nodes which participate in forwarding of multicast packets. Forwarding Group (FG) is associated with each multicast group and node in FG is in charge of forwarding multicast packets of multicast group. The packets are broadcasted only if it is not the duplicate.

      Fig. 4: An example of FGMP

      For each Forwarding Group, only one flag and timer are needed. So, each node in FG forwards the packets belonging to the multicast group until the time expires.

      Fig. 6: Dominant Pruning Method

      In the above figure, N (v) implies the set of adjacent nodes of node v while N (N (v)) is the set of nodes at most two-hops apart from node v. If the receiver(s) is not within this range, then it searches the receiver(s) using dominant pruning flooding method and forms the multicast group using the replies along the reverse path.

3. Related work

   Various Multicast Protocols have been proposed by various researchers e.g. ODMRP[18], NAMP[23], MZR[24] and so on. Bommaiah and McAuley[17] presents AMRoute Protocol which suffers from the drawback of having temporary loops and may create non optimal trees with host mobility. Royer and Charles[15] proposed MAODV which discovers multicast routes using a broadcast route-discovery mechanism but still suffers from Long delays and high overhead associated with fixing broken links in

   conditions of high mobility and traffic load. Sung-Ju and Gerla[18] proposed ODMRP which is a mesh based protocol, and uses a forwarding group concept and suffers from the increasing routing overhead as the number of senders increases. Wu and Tay[19] give the concept of multicast session member id (msm-id) in AMRIS routing protocol in which packets loss will happen if a link in the tree breaks until the tree is reconfigured. Garcia-Luna-Aceves and Madruga[25] proposed a concept of shared mesh in CAMP protocol which provide correct distances to all destinations within finite time but it exploits special mechanisms (Heartbeat, Push Join) to ensure the validity of all reverse shortest paths. AODV has the weakness of a typical tree-based protocol. Mesh based multicast routing protocol is more robust in comparison to tree based multicast routing protocols. The construction of a multicast tree can be done either from the source or from a destination. T h e r e f o r e , a s t he Ad hoc environment suffers from frequent breaking of paths due to mobility of nodes; efficient multicast group maintenance is necessary.

   This research is concerned with the design of a fully efficient multicast protocol. In this paper, we have tried to give an idea to design a multicast protocol which minimizes the loopholes of the previous protocols up to great extend.

4. A new multicast routing protocol : BEST-MRP

   1. Overview

      The BEST-MRP is an efficient tree-based protocol which also includes the selection of time for holding the packets and this time is based on the perimeter of senders transmission range. Nodes furthest away from the local sender should select the smallest packet holding time whereas nearer nodes should select larger packet holding time. Routes in the network are built and maintained using reply and request messages. When a message is sent to the node, the node first determines that the message that was send by other node is received for the first time or not. If it was received first time, the node will forward that message, otherwise it drops the message. Each sending message is stamped by the source with a unique sequence

      number. The duplicates can be detected by storing a record of source and sequence number for previously received messages. So, BEST-MRP provides a reduced bandwidth by dropping the duplicate messages before forwarding. Due to this, congestion control can also be done in the network which reduces the time delay in transferring the message from source to destinations. Thus, the packet holding time strategy and dropping of duplicate packets bring lots of efficiency in the routing of information from one place to another and also increases the scalability in the network.

      Fig. 7: Mobile Nodes showing transmission range and packet holding time

      In this protocol, we apply Geo flood Algorithm [14] to improve flooding by having each node waiting for some time before forwarding on receiving the message first time, and does not allow forwarding if the same message is received from all neighboring nodes. In the above diagram, T1 T2 and T3 are the packet holding time for the nodes S, A and B. A location field is attached with each message. Once the message is forwarded, each intermediate node updates its location field with its own position. BEST-MRP target to achieve reduced bandwidth overhead and providing scalability in the network.

   2. Methodology

      If the message t h a t w a s r e c e i v e d has been forwarded earlier by any other node, the message is not allowed to be forwarded. If the message is received for the first time, we record the direction from where the

      message comes, and the time for holding the packet is selected. The message is not allowed to be forwarded until either the message is received from all the neighboring nodes or time for holding the packets has been passed. If the message arrives from all the neighboring nodes before time selected for holding the packets, then the message is not allowed to forward, otherwise it is forwarded and the source and sequence number is stored in order to filter future duplicates and forms the multicast group using the replies along reverse path. It is not necessary to have Location knowledge on all nodes. A node that does not know its location do not wait and will forward the messages immediately. The time for holding the packets will increase if the distance of source from the sender reduces. A random element was considered in the network so that the contention among the nodes located at the same distance from the sender will not arise. As will be discussed later, simulation results indicate this random element does not have the intended effect. This time selection for holding the packets serves two purposes. The far away nodes i n t h e network cover more new network space than closer nodes, thus smaller times for holding packets for ar away nodes and larger time for holding packets for nearer nodes help messages broadcast faster and keep latencies down for far-away nodes. This makes our protocol more efficient than others.

      Fig. 8: Multicast Request and Reply Messages

      Today, nodes can easily obtain their location through already popular GPS devices. Therefore, the

      B E S T – M R P can also use known ad-hoc location discovery methods[26] which are less accurate than GPS but can be used indoors. Moreover, if enough farther nodes are able to transmit faster, closer nodes that dont cover much network space will not allow forwarding if they receive the message from farther nodes on all directions.

   3. Multicast Tree Creation

      For each Multicast transmission of packets in the ad hoc network, a tree rooted at source is created. The multicast group is formed using the replies along reverse path. Location knowledge is not strictly required on all nodes. The source sends a FLOOD- REQUEST to each node, through unicast routes obtained from the network routing table. A FLOOD- REQUEST packet is uniquely identified by the corresponding (source, sequence) pair that is stored in the forwarding cache. As the FLOOD-REQUEST packet is propagated to other node, reverse route entries are created at each intermediate node. The reverse routes are basically multicast route entries. After receiving the FLOOD-REQUEST message from source nodes, the corresponding nodes reply with the FLOOD- REPLY messages in order to create the Multicast tree.

5. Conclusion

   All multicast routing protocols in MANETs tries to overcome the difficulties that arise while transferring data to multiple destinations. All protocols have their own advantages and disadvantages [5]. Multicast trees are constructed in order to reduce end-to-end latency. Multicast tree-based routing protocols are efficient and satisfy the scalability issue, they have several drawbacks in ad hoc wireless networks due to mobility of nodes that participate during multicast transfer of messages. We have presented a scalable and bandwidth efficient method for multicast routing in mobile ad hoc networks. The BEST-MRP significantly reduces the bandwidth overhead under high node densities. Because of its timer selection criteria, the protocol is able to maintain the latency delivered under reasonable boundations while providing an efficient reduction in bandwidth overhead. Our protocol assumes that nodes know their own location. Therefore, the BEST-MRP can use known ad- hoc location discovery methods[26] which are less

   accurate than GPS but can be used indoors. The knowledge of locations is not necessarily required on all nodes.

6. Future work

In future, we plan to test this scheme by varying different simulation parameters like the eld size, the number of nodes and the node movement pattern. We would also like to apply our scheme to other protocols, in particular to tree-based protocols like AODV. As we know that tree-based protocols do not have redundant packets transmissions like a mesh-based protocol, so much reduction in packet transmissions is not expected but improvement of signicant delivery rate is expected. It will be interesting to investigate the benets of BEST-MRP protocol for multicast routing, especially the ones that broadcast route request packets to discover routes.

REFERENCES

1. Amandeep Makkar, Bharat Bhushan, Shelja, and Sunil Taneja, Behavioral Study of MANET Routing Protocols, International Journal of Innovation, Management and Technology, Vol. 2, No. 3, June 2011.

2. Anuj K. Gupta, Member, IACSIT, Dr. Harsh Sadawarti, Dr. Anil K. Verma Performance analysis of AODV, DSR & TORA Routing Protocols, IACSIT International Journal of Engineering and Technology,Vol.2,No.2, April 2010 ISSN: 1793-8236

3. Jyoti Jain, Mehajabeen Fatima, Dr. Roopam Gupta, Dr.

   .K.Bandhopadhyay, Overview and Challenges of Routing Protocol and Mac layer in mobile ad-hoc network, Journal of Theoretical and Applied Information Technology

4. Kamal Kant, Lalit K. Awasthi, Unicast and Multicast Routing Protocols for MANETs: a Comparative Survey,

   Department of Computer Science and Engineering

5. Murthy, S. and J.J. Garcia-Luna-Aceves, An Efficient Routing Protocol for Wireless Networks, ACM Mobile Networks and App. J., Special Issue on Routing in Mobile Communication Networks, Oct.1996, pp. 183- 97.

6. Anuj K. Gupta, Member, IACSIT, Dr. Harsh Sadawarti, Dr. Anil K. Verma,Performance analysis of AODV, DSR & TORA Routing Protocols, IACSIT International Journal of Engineering and Technology, Vol.2, No.2, April 2010.

7. Georgios Kioumourtzis, Simulation and Evaluation of Routing Protocols for Mobile Ad Hoc Networks, Thesis, Master of Science in Systems Engineering and Master of Science in Computer Science, Naval Postgraduate School, Monterey, California, 2005.

8. Satya Ranjan Rath, Study of Performance of Routing Protocols for Mobile Adhoc Networking in NS-2, Department of Computer Science and Engineering, National Institute of Technology, Rourkela,2009.

9. Guangyu Pei; Gerla, M.; Tsu-Wei Chen; Fisheye state routing: a routing scheme for ad hoc wireless networks,IEEE International Conference on Communications, 2000.

10. S.Sathish, K. Thangavel and S. Boopathi, Comparative Analysis of DSR, FSR and ZRP Routing Protocols in MANET, 2011 International Conference on Information and Network Technology.

11. Elizabeth M. Royer, University of California, Santa Barbara Chai-Keong Toh, Georgia Institute of Technology, A Review of Current Routing Protocols for AdHoc Mobile WirelessNetworks.

12. V. Park, and S. Corson, Temporally-Ordered Routing Algorithm (TORA), Version 1 Functional Specification. IETF Internet draft,1997.

13. Osamah S. Badarneh, Michel Kadoch, Multicast Routing Protocols in Mobile A d Hoc Networks: A Comparative Survey and Taxonomy, EURASIP Journal on Wireless Communications and Networking volume 2009 , Article ID 764047,42 pages.

14. Jesus Arango, Mikael Degermark, Alon Efrat Computer, An Efficient Flooding Algorithm for Mobile Ad-hoc Networks, University of Arizona Tucson, Arizona, USA.

15. Elizabeth M. Royer and Charles E. Perkins: Multicast Operation of the Ad-hoc On-Demand Distance Vector Routing Protocol", In Proc. of the 5th annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom),. 207 – 218 August (1999).

16. Jorjeta G. Jetcheva and David B. Johnson: "Adaptive Demand-Driven Multicast Routing in Multi-Hop Wireless Ad Hoc Networks", InProc.of the 2nd ACM International Symposium on Mobile and Ad-hoc Networking & Computing (MobiHOC), 33 – 44, October (2001).

17. E. Bommaiah, M. Liu, A. McAuley, and R. Talpade, AMRoute: Ad hoc Multicast Routing Protocol, Internet-

    Draft, draft-talpade-manet-amroute-00.txt, August 1998, Work in progress.

18. Sung-Ju Lee, Mario Gerla, and Ching-Chuan Chiang: "On-Demand Multicast Routing Protocol", In Proc. of the Wireless Communications and Networking Conference (WCNC), 1298 – 1302, September (1999).

19. C. W. Wu, Y. C. Tay, and C. K. Toh, Ad hoc Multicast Routing Protocol Utilizing Increasing id-numbers (AMRIS) Functional Specification, Internet-Draft, draft-ietf-manet- amris-spec-00.txt, November 1998, Work in progress.

20. T. Ozaki, J. B. Kim, and T. Suda, Bandwidth Efficient Multicast Routing Protocol for Ad hoc Networks, Proceedings of IEEE ICCCN99, pp. 10-17, October 1999

21. C. Chiang, M. Gerla, and L. Zhang, Forwarding Group Multicasting Protocol for Multihop, Mobile Wireless Networks, ACM-Baltzer Journal of Cluster Computing: Special Issue on Mobile Computing, vol. 1, no. 2, pp. 187- 196, 1998.

22. Tanu Preet Singh, Neha and Vikrant Das:MULTICAST ROUTING PROTOCOLS IN MANETS, International Journal of Advnced Research in Computer Science and Software Engineering, Volume 2, Issue 1, January 2012.

23. Al-Sakib Pathan, Muhammad Monowar, Md. Rabbi, Muhammad Alam, and Choong Hong:NAMP: Neighbor Aware Multicast Routing Protocol for Mobile Ad Hoc Networks, The International Arab Journal of Information Technology, Vol. 5, No. 1, January 2008.

24. Vijay Devarapalli and Deepinder Sidhu: MZR: A Multicast Protocol for Mobile Ad Hoc Networks, University of Maryland Baltimore County.

25. J.J. Garcia-Luna-Aceves and E.L. Madruga, The Core- Assisted Mesh Protocol. The IEEE Journal on Selected Area in Communication,vol.17, no.8, Aug. 1999, pp1380-1394.

26. Ljubica Blazevic, Jean-Yves Le Boudec and Silvia Giordano:A Location-Based Routing Method for Mobile Ad Hoc Networks, IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 3, NO. 4,OCT

27. L. Ji, and M.S Corson , Differential Destination Multicast A MANET Multicast Routing Protocol for small groups, Proc. INFOCOM, pp. 1192-02, 2001.