A Survey on Multicast Routing Protocols for Mobile Ad-Hoc Networks

A Survey on Multicast Routing Protocols for Mobile Ad-Hoc Networks

Prabhu Kichadi

Department of Computer Science and Engg.

Akshaya Institute of Technology Tumkur, India

Yashavanth T R

Department of Computer Science and Engg.

Akshaya Institute of Technology Tumkur, India

Abstract A Mobile Ad-hoc Network (MANET) is composed of Mobile Nodes (MNs) and these nodes are self-organized to form a network without any infrastructure. In late years, Multicast routing plays a substantial role in MANETs and the main target is to send data from multiple sources to multiple destinations and at the same time minimize the employment of resources like bandwidth, time and link costs. To provide reliable multicasting suitable for mobile ad hoc networks, many researchers have continued trying to optimize existing multicast routing protocols. In this paper some of the most important problems considered in this area are analyzed and also a survey on multicast routing protocols is discussed in detail.

Keywords: Mobile Ad Hoc Network (MANETs), Multicast Routing Protocols, QoS, Mobile Nodes (MNs).

1. INTRODUCTION

   Ad Hoc is a term from the Latin which means For This Purpose. A temporary association of nodes for the function of communication becomes an ad-hoc network. A mobile ad hoc network (MANET) is a collection of autonomous mobile nodes that communicate with each other over wireless connections. The regional anatomy of an ad hoc network is extremely dynamic due to the arbitrary movement of each guest. In recent years, for an ad hoc network number of multicast protocols has been offered. They can generally be separated into two classes based on the routing structure they are tree-based protocols and mesh-based protocols. There survives a single route between any sender-receiver pair in tree-based protocols. And holds the advantage of high multicast efficiency (which is specified as the proportion of the total figure of data packets received by all receivers to the total figure of information packets transmitted or retransmitted by senders or intermediate nodes). However, tree-based protocols are not strong against frequent topology changes and the packet delivery ratio (which is specified as the proportion of the number of data packets delivered to all pass catchers to the number of data packets supposed to be picked up by all receivers) drops at high mobility. Mesh- based protocols provide redundant routes for maintaining connectivity to group members. The low packet delivery ratio problem caused by link failures is alleviated due to redundant routes. Mesh-based protocols are robust to node mobility. However, because of redundant route multicast efficiency becomes low. Hybrid multicast provides advantages both tree based as well as mesh based [1].

   In computer networking, multicast (one-to-many or many-to-many distribution) is group communication where information is directed to a group of destination computers simultaneously. A pictorial representation of transmission of information from multiple sources to multiple destinations is shown in the Figure 1. This is becoming a central demand of computer networks supporting multimedia applications. In order to support large numbers of multicast sessions efficiently, the network must transport the information exchanged in those sessions using as few network resources as possible, while meeting the sessions service requirements.

   Figure 1: Conceptual organization of a multicast group, with more than one destination.

   The main objectives of multicasting routing are every member receives exactly one copy of the packet and non-members receive nothing, then there should not be any loops in the route and also have an optimal path from the source to each destination.

   The rest of this paper is divided as follows. Section II presents multicast routing problems. An overview of existing multicast-source routing algorithms is described in section III. Then, in section IV research issue is explained. Finally conclusion presented in the section V.

2. ISSUES IN MULTICAST ROUTING

   MANET refers to (for the most part, wireless) networks where all network components are mobile. In general, there is no real distinction in a MANET between a host and a router for all network hosts can be endpoints as well as forwarders of traffic.

   Most research in the area of routing for MANET has concentrated on routing for unicast communication. Multicast routing and packet forwarding in MANET are a fairly unexplored area. One recent exception is the Shared-Tree Wireless Network Multicast (ST-WIM) work at UCLA, which aims to adopt fixed-network multicast approaches (PIM Sparse Mode) to MANET. Our position is that, since fixed network multicast routing is based on state in routers (either strong or easy), it is essentially unsuitable for a MANET environment with unconstrained mobility. In this context, unconstrained mobility implies the following:

   • Host behavior completely independent of other hosts.

   • No limit on host speed.

   • No constraints on direction of move.

   • High probability of frequent, temporary network partitions.

   So that all of these factors no longer make it worthwhile for a mobile host to maintain any multicast- related state information other than its own. Furthermore, in many types of the AHNs (e.g., where hosts are handheld devices) both storage capacity and power are severely limited. This is yet another reason to avoid maintaining and exchanging multicast state. Also, frequent changes in the topology make it difficult to apply clustering algorithms: heavy state maintenance and frequent elections of cluster leaders are too expensive for low-power hosts. One other important consideration has to do with the mission of AHNs. AHNs are most often deployed in the military (e.g., battlefield) and other emergency (e.g., disaster recovery) situations. In such critical environments robustness and high quality-of-service are of paramount concern. Consequently, multicast mechanisms (however attractive otherwise) that cannot provide the highest delivery guarantees are not appropriate.

   Depending on the link/tree constraints imposed and the objective functions used, a multicast routing problem can be formulated as:

   1. A link-constrained problem: a link constraint is imposed to construct feasible multicast trees such as bandwidth- constrained routing.

   2. A multiple-link-constrained problem: two or more link constraints are imposed to construct feasible trees such as bandwidth- and buffer-constrained routing.

   3. A tree-constrained problem: a tree constraint is imposed to construct feasible trees such as delay-constrained routing.

   4. A multiple-tree-constrained problem: two or more tree constraints are imposed to construct feasible trees such as delay- and inter receiver-delay-jitter-constrained routing.

   5. A link- and tree-constrained problem: a link constraint and a tree constraint are imposed to construct feasible trees such as delay- and bandwidth-constrained routing.

   6. A link optimization problem: a link optimization function is used to locate an optimal multicast tree such as the maximization of the link bandwidth over on-tree links in a multicast tree.

   7. A tree optimization problem: a tree optimization function is used to locate an optimal multicast tree such as minimization of the total cost of a multicast tree. This is also known as a Steiner tree problem.

   8. A link-constrained link optimization problem: a link constraint is imposed and a ink optimization function is used to locate an optimal multicast tree that fulfills the constraint such as the bandwidth-constrained buffer optimization problem.

   9. A link-constrained tree optimization problem: a link constraint is imposed and a tree optimization function is used to locate an optimal multicast tree that fulfills the constraint such as the bandwidth-constrained Steiner tree problem.

   10. A tree-constrained link optimization problem: a tree constraint is imposed and a link optimization function is used to locate an optimal multicast tree that fulfills the constraint such as the delay-constrained bandwidth optimization problem.

   11. A tree-constrained tree optimization problem: a tree constraint is imposed and a tree optimization function is used to locate an optimal multicast tree that fulfills the constraint such as the delay-constrained Steiner tree problem.

   12. A link and tree constrained tree optimization problem: link and tree constraints are imposed and link optimization functions are used to locate an optimal multicast tree that fulfills the constraints such as bandwidth- and delay constrained tree optimization problem.

   Problem 1 and 2 are tractable, because link constraints can be fulfilled by removing from the network topology links that do not meet the selection criteria. Wang and Crow Croft [2] proved that the problem of finding a path subject to two or more independent additive/multiplicative constraints in any possible combination is NP-complete. The only tractable combinations are the concave constraint and the other additive/multiplicative constraints. As a result, problem 3, 5 and 10 are polynomial time solvable, while problem 4 is NP-complete. A solution algorithm of polynomial time complexity for problem 6 has been proposed by Shacham [3]. Problem 8 reduces to problem 6 if links that do not meet the link constraints are removed from the network topology. Hence, it is also polynomial time solvable. Finally, problem 7 (Steiner tree problem) and problem 9, 11 and 12 (constrained Steiner tree problem) have been proved to be NP-complete [4]. Some source routing algorithms used to solve these problems are briefly introduced in the next section. A nice survey of multicast routing problems can be found in [5].

3. PRIOR STUDY WORK

   Royer et al. [6] Examined routing protocols for ad hoc networks and evaluates these protocols based on a given set of parameters. The article provides an overview of eight different protocols by presenting their characteristics and functionality, and then provides a comparison and discussion of their respective merits and drawbacks.

   Sabari et al. [7] proposed an ant agent based adaptive, multicast protocol that exploits group members desire to simplify multicast routing and invoke broadcast operations in appropriate localized regimes. By reducing the number of group members that participate in the construction of the multicast structure and by providing robustness to mobility by performing broadcasts in densely clustered local regions, the proposed protocol achieves packet delivery statistics that are comparable to that with a pure multicast protocol but with significantly lower overheads. By their simulation results, they show that their proposed protocol achieves increased Packet Delivery Fraction (PDF) with reduced overhead and routing load.

   Baburaj et al. [8] Presented a GA-based MAODV model to support the multicast routing optimization algorithm in mobile ad-hoc networks. The simulation results demonstrate that the proposed approach and parameters provide an accurate and efficient method in realistic scenarios. Finally, they suggest that in future multicast protocol evaluations need to be more comprehensive. Evaluations should consider a range of realistic mobility models and should include special cases, such as high density and high traffic rates.

   Gour [9] investigated different routing protocols, and provide the study of problems identified in these routing as their literature collection. In addition of that here they propose a new kind of path discovery strategy that promises to deal with a dynamically changing network with adoptable Quality of service (QoS) parameters. Here they discuss their proposed solution to achieve the desired goal. Their proposed technique uses a traditional genetic algorithm and similarity functions that help to improve the performance of the proposed routing algorithm.

   Lakshmi et al. [10] Presented an essential component of communication protocols in mobile ad hoc networks. Routing protocols typically fall under two classifications: first one is unicast routing protocol, second one is a multicast routing protocol. The design of the protocols is driven by specific goals and requirements based on respective assumptions about the network properties or application area. On comparing these protocols Hybrid unicast and multicast routing protocols are better than proactive and reactive routing protocols.

   Asma et al. [11] illustrated an energy efficient routing algorithms for MANETs are surveyed and categorized on the basis of the metrics used for energy efficient routing. These algorithms are analyzed in highlighting their strengths and deficiencies.

   Gupta et al. [12] aimed to provide a platform for researchers worldwide to get an overview of the existing ACO based routing protocols. To know about their performance against traditional ad hoc routing protocols. This would rather help them consider appropriate protocols for their research work. The authors have tried their best to present a comparative study of various proposed ad hoc routing protocols based on ant colony optimization techniques. They have evaluated and compared various ACO based algorithms to the original ones and obtained better results in terms of an end to end delay and routing overhead etc. for environments of dynamic topology. In future a more

   critical performance evaluation of these protocols shall be done on the basis of simulations and varying performance metrics.

   MOSPF [13] is a multicast extension of the unicast link-state protocol OSPF. It was based on Deerings work [14]. In addition to a global state information, at every node the protocol maintains the membership information of every multicast group in the routing domain. Group membership changes in a sub-network are detected by a local router, which broadcasts the information to all other nodes. Given all knowledge of the network state and group membership, any node can compute the shortest-path multicast tree from a source to a group of destinations by using Dijkstras algorithm. Such a protocol can be easily used for delay- constrained multicast routing.

   Zhu, Parsa and Garcia-Luna-Aceves (ZPG) [15] proposed this problem. ZPG allows variable delay bounds to destinations. A shortest-path tree in the terms of delay is first constructed by Dijkstras algorithm. If the delay constraint cannot be satisfied for any destination, it must be renegotiated; otherwise, the algorithm proceeds by iteratively refining the tree for lower cost. The basic idea is to replace a path in the tree by another path with lower cost unless such a replacement cannot be found. The algorithm always finds a delay-constrained tree (probably not least-cost), if one exists, because it starts with a shortest-path tree.

   Widyono [16] proposed several heuristic algorithms for the constrained Steiner tree problem. The one with the best performance is called the constrained adaptive ordering heuristic. At each step, a constrained Bell-man-Ford algorithm is used to find a delay-constrained least-cost path from the source to a destination that is not yet in the tree. The found path as well as the destination is then inserted into the tree. The cost of links in the tree is set to zero. The above process repeats until the tree covers all destinations.

   Zone-based Hierarchical Link State routing (ZHLS)

   [17] is a hybrid routing protocol. In ZHLS, mobile nodes are assumed to know their physical ocations with assistance from a locating system like GPS. ZHLS uses a hierarchical addressing scheme that contains a zone ID and node ID. A node determines its zone ID according to its location and the pre-defined zone map is well known to all nodes in the network. It is assumed that a virtual link connects two zones if there exists at least one physical link between the zones. A two-level network topology structure is defined in ZHLS, the node level topology and the zone level topology. Respectively, there are two kinds of link state updates, the node level LSP (Link State Packet) and the zone level LSP. A node level LSP contains the node IDs of its neighbors in the same zone and the zone IDs of all other zones.

4. RESEARCH ISSUES

   Basically, the design should take three issues into consideration: robustness, multicast efficiency, and control overhead. If the degree of robustness is low, the packet delivery ratio will drop and high control overhead will be incurred. Thus, the mesh structure is more appropriate to be the multicast routing structure. A mesh that is built and maintained by only one core node is robust to low mobility and can avoid duplicate transmissions. Moreover, the number

   of forwarding nodes in this kind of mesh is limited such that some degree of multicast efficiency is ensured. However, this sort of mesh may not be robust enough to high mobility. An excellent mesh-based protocol should be designed with the connectivity adapted to the degree of mobility.

   Since the mesh is constructed and refreshed by one core node, the position of the core node affects the efficiency of the mesh. If the core node is located far away from other group members, multicast efficiency is reduced and longer paths increase the probability of link failures. Therefore, it is important to select a new core located in a better position periodically. How to devise an efficient core migration scheme with low overhead is a crucial issue.

   The periodic reelection of the core node results in regular flooding of control messages, so the frequency of flooding needs to be further studied. The soft-state maintenance should be used only for refreshing the mesh; while the hard-state one should be used for repairing broken links.

   General multicast protocols often provide shortest paths between senders and receivers. Although shortest paths have low data delivery latency and low probabilities of link failures, they reduce multicast efficiency. Hence, the protocol should strike a balance between multicast efficiency and path lengths. At last, a mesh may be partitioned because of node movement. Several protocols merge separated meshes by requiring the core node with the highest IP address (or other criteria) to be the new core of the merged mesh. This merging procedure is inefficient and time-consuming. In our opinion, it is better for one of the group members that detect more than one mesh existing to be the new core node. This is because that these members are located in the middle of these separated meshes.

5. CONCLUSION

   In this paper, a broad range of multicast routing protocols for MANETs are discussed. Multicast routing protocol in MANETs tries to master some difficult problems which can be categorized under basic issues or considerations. All protocols have their own advantages and disadvantages. One constructs multicast trees to reduce end-to-end response time while another builds a mesh to ensure validity. Some protocols create overlay networks and use unicast routing to forward packets. Energy aware multicast protocols optimize either total energy consumption or the system lifetime of the multicast tree. It is really difficult to design a multicast routing protocol considering all the issues mentioned in section II.

6. REFERENCES

1. Junhai, Luo and Danxia, Ye and Liu, Xue and Mingyu, Fan "A comprehensive survey of multicast routing protocols for mobile ad hoc networks." IEEE Communications Surveys & Tutorials, Vol.11, No-1, pp. 25-34, 2008.

2. Wang, Z. & Crowcroft, J., QoS Routing for Supporting Resource Reservation, IEEE Journal on Selected Areas in Communications, Vol.14, pp.1228-1234, Sept-1996.

3. Shacham, N. Multicast Communication by Hierarchically Encoded Data, IEEE INFOCOM, pp. 107-114, May-1992

4. Carey, M.R. & Johnson, D.S., Computers and Intractability, New York, Freeman, 1979.

5. Wang, B. & Hou, J.C., Multicast routing and its QoS extension: problems, algorithms, and protocols, The Magazine of Global Internetworking, Vol.14 Issue no.1, pp. 22 36. Jan-Feb. 2000.

6. Royer, E.M.; Chai-Keong Toh, "A review of current routing protocols for ad hoc mobile wireless networks," Personal Communications, IEEE, vol.6, no.2, pp.46-55, Apr 1999.

7. A. Sabari, K.Duraiswamy, Ant Based Adaptive Multicast Routing Protocol (AAMRP) for Mobile Ad Hoc Networks, International Journal of Computer Science and Information Security, Vol.6, No. 2, 2009.

8. Baburaj, E., and V. Vasudevan. "An Intelligent Multicast Ad-hoc on demand Distance Vector Protocol for MANETs." journal of Networks, Vol.3, no. 6, pp.62-68, 2008.

9. Gaur, Priti. "Implementation of Multicast Routing Using Genetic Algorithm." pp. 226-234, 2013.

10. Lakshmi, M. Vijaya, and S. Venkatachalam. "Comparative analysis of QoS routing protocols in MANETS: Unicast &Multicast." International Journal of Emerging Technology and Advanced Engineering, Vol. 2, no. 4, pp. 242-250, 2012.

11. Asma, Anjum, and Gihan Nagib. "Energy efficient routing algorithms for mobile ad hoc networks a survey." International Journal of Emerging Trends & Technology in computer Science, Vol. 3, no. 1,pp. 218-223, 2012.

12. Gupta, Anuj K., Harsh Sadawarti, and Anil K. Verma. "MANET routing protocols based on Ant Colony Optimization." International Journal of Modelling and Optimization, Vol. 2, no. 1, pp. 42-49, 2012.

13. Moy, J., Multicast Extensions to OSPF, Internet Draft, September, 1992.

14. Deering, S. & Cheriton, D., Multicast Routing in Datagram Internetworks and Extended LANs, ACM Trans, Comp. Sys. PP. 85- 111, May-1990.

15. Qing, Z & Parsa, M.& Garcia-Luna-Aceves, J.J., A Source-based Algorithm for Delay-constrained Minimum-cost Multicasting, Fourteenth Annual Joint Conference of the IEEE Computer and Communications Societies, Vol.1, pp. 377-385, 1995.

16. Widyono, R., The Design and Evaluation of Routing Algorithms for Real Time Channels, Technical Report, ICSI TR-94-024, Univ. CA at Berkeley Intl. Computer Science. Inst., June,-1994.

17. S. R. Murthy and B. S. Manoj, Ad Hoc Wireless Networks: Architectures and Protocols, Prentice-Hall, Upper Saddle River, NJ, USA, 2004.