A Reliable Multicast Algorithm for Mobile Ad hoc Networks Thiagaraja Gopalsamy Mukesh Singhal D. Panda and P. Sadayappan Altera Corp. University of Kentucky Ohio State University [email protected] [email protected] {panda,saday}@cis.ohio-state.edu Abstract: A reliable multicast algorithm, called RMA, for mobile ad hoc networks is presented that is based on a new cost criterion, called link lifetime, for determining the optimal path between a pair of nodes. The algorithm has the characteristics of using an undirected graph for its routing operations rather than a fixed structure like a tree or a mesh. Previously proposed routing metrics for mobile ad hoc networks were designed for use in wired environments, where link stability is not a concern. We propose a new metric, called the lifetime, which is more appropriate for mobile ad hoc networks. The lifetime metric is dependent on the predicted future life of the link under consideration. We developed a simulator for the mobile ad hoc networks, which is portable and scalable to a large number of nodes. Using the simulator, we carried out a simulation study to analyze the effectiveness of the routing metrics and the performance of the proposed reliable multicast algorithm. The simulation results show that the lifetime metric helps achieve better performance in mobile ad hoc environments than the hop count metric. 1. Introduction Mobile ad hoc networks (MANET) are a special case of mobile network without any fixed backbone network to support them and provide connectivity or to perform state maintenance. The mobile hosts themselves perform all the routing and state maintenance operations. The nodes in the network also have lower processing capabilities than their stationary counterparts. The bandwidth of the wireless medium is less than wired media. Thus routing in ad hoc networks poses a challenging research problem. The standard routing protocols used in fixed networks or infra-structured mobile networks can’t be used in mobile ad hoc networks. The main applications of mobile ad hoc networks are in emergency rescue operations and in battlefields. The most characteristic operation in these areas is multicast, where messages are sent from one node to multiple recipients. Thus multicast routing is a challenging research problem [2-12]. There are several requirements posed on the multicast algorithm by the mobile ad hoc network environment. The existing multicast algorithms do not satisfy all of the requirements, e.g., reliability of message delivery. Routing is one of the most contentious and important issues in mobile ad hoc network environments. Routes are usually multi-hop and this necessitates the presence of a unified routing mechanism across the whole network. The routing mechanism has to maintain the routing structure and update it whenever changes occur in the system. The expectations on the routing mechanism are more, in that it is expected to be robust enough to handle all possible changes in the system topology and guarantee near optimal routes between any source destination pair. The resources provided to the routing mechanism on the other hand are limited, i.e., nodes with limited life and processing capabilities and the limited bandwidth of the wireless medium. These conflicting sets of resources and demands make routing in ad hoc networks a very challenging problem. Multicast routing is a subset of the routing problem. The advent and development of multi-user applications have led to the need for reliable, cost effective multicast mechanisms. The majority of the ad hoc network applications are in the multi-user domain. Hence the issue of multicast routing becomes an object of interest as well as concern. All the problems associated with routing are applicable to multicasting as well, but the demands are much higher, in the sense that multi-point delivery should be guaranteed. Multicast operations in mobile networks are generally used for dissemination of important and confidential information. The multicast operation is also used as a means for synchronization of operations between various mobile hosts. Multicast algorithms are hence expected to ensure a reliable message delivery and in most of the cases, the source of message transmission is to be informed of the success of the message delivery. In MANET environments, reliability is of much higher concern. Existing multicast algorithms for mobile ad hoc networks do not provide reliability. Our algorithm RMA concentrates on reliable message delivery. RMA ensures reliability through the use of Acknowledge messages from the destination to the source. These acknowledge messages also contribute to the reverse path maintenance in the routing tables. The source is also entrusted with the task of ensuring a reliable message delivery, through retransmissions in case of failure to get an acknowledge message back within a pre-specified time. The novelty of our approach is that we propose a new cost factor (discussed in the next section) for determining the optimal path between a pair of nodes. Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS’02) 1063-6927/02 $17.00 © 2002 IEEEThe remainder of the paper is organized as follows. In Section 2, we propose a new cost criterion for determining the optimal path and the changes that need to be made in the environment to incorporate these factors. In Section 3, the Reliable Multicast Algorithm (RMA) is presented. (A pseudo-code for the algorithm is given in the Appendix.) Section 4 presents a simulation study and a comparative performance analysis of the RMA and AODV [3] on RELSIM [1]. Finally, Section 5 concludes the paper with remarks on the future work. 2. A new cost criterion for determining the best path Existing multicast algorithms assume that the best path between two nodes is the path with the minimum number of hops. This assumption may be true in wired networks where wires are fixed and also for infra-structured networks. But for a highly unstable network like MANET, the number of hops alone is not a good measure of the cost of wireless links connecting the hosts. The lifetime of links plays an important role in determining the cost associated with links. A link with a longer life and more hops is preferred over a link with shorter lifetime and fewer hops. This is because any change in the link topology
View Full Document