A Weighted Learning Automata-Based Multicast Routing Protocol for Wireless MANET

A Weighted Learning Automata-Based Multicast Routing Protocol for Wireless MANET

1Joydipa Sen, 2Mrs Vinodha K

1MTECH student, Department of ISE, The Oxford College of Engineering

2Asst Professor, Department of ISE, The Oxford College of Engineering

Abstract

Multicasting in MANET is a difficult task because of randomness in mobility parameters. Finding the optimal solution to multicast routing is difficult when the probability distribution function of the random variables is assumed to be unknown. This paper proposing an algorithm based on weighted learning automata based multicast routing protocol for solving the proxy steiner tree problem aims at finding the most stable multicast route with maximum duration of link stability among all possible multicast paths against host mobility. Proposed algorithm is compared with existing one algorithm and simulation results indicate that the proposed multicast routing algorithm works better in terms transmission delay and route life time. It can significantly improve the performance of this network.

Keywords: multicasting, MANET, steiner tree, weighted learning automata.

1. Introduction

   A mobile ad hoc network (MANET)[1,2,3] is a self- organized and dynamically reconfigurable wireless network without central administration and wired infrastructure. Nodes in the MANET can instantly establish a communiqué structure while each node moves in a randomly and nodes may have limited property, limited battery life and they have capability of self organization. MANETs require fundamental changes to predictable routing protocols for both unicast and multicast communication due to its unique features. Lack of any infrastructure, such as a collection of base stations makes ad-hoc networks different from other wireless networks. Since connections of a mobile terminal do not take place via a base station as conducted in a configured network like cellular networks, a mobile terminal in ad-hoc networks can directly connect with other nodes that it finds within its radio range. In order to connect with a node that is located outside radio range, a multi hop transmission method is used. With the fast increase of group communication services, the multicast routing in MANET has concerned a lot of consideration

   recently [4][5][6][7][8]. In multicast routing, through paths all

   group members are connecting so that bandwidth is not wasted. Group communiqué applications include audio/video conferencing as well as one-to-many data distribution in critical situations such as failure recovery or battlefield scenarios.

   Also, most of the applications in MANET are in mobile/wireless environments where the speed and topology change produces very high overhead and affects the throughput performance in terms of packet delivery ratio. Since Group-oriented declaration is one of the important application classes in MANET environments, some selected number of MANET multicast routing protocols have been proposed. These multicast protocols are divided according to two different criteria. Routing techniques are into two categories: proactive and reactive. Proactive protocols retain routing state, in the same time reactive protocols decrease the impact of regular topology changes by acquiring routes on demand. Initiating a multicast routing protocol for MANET, is a different challenge than for wired networks due to characteristics of MANET such as usages of wireless broadcast standard, self-motivated topology, limited bandwidth, high packet error rate, etc.

   1. Types of MANET

      • Vehicular Ad Hoc Networks (VANETs) are used for making contact among vehicles and between vehicles and roadside equipment.

      • Intelligent vehicular ad hoc networks (InVANETs) are a kind of artificial intelligence, it helps vehicles to perform in intelligent manners during vehicle-to-vehicle clash, accidents etc.

      • Internet Based Mobile Ad hoc Networks (iMANET) are a kind of ad- hoc networks that connect mobile nodes and fixed Internet- gateway nodes.

      Multicasting plays a vital role in MANET. In Fig1.1 node A and D connected to each other directly, so A can send packet directly to D. But if A wants to send packet to G, then first it has to send the packet to D and then D forward the packet to G.

      receivers. In link stability based multicast routing

      B C protocol stable multicast path is from source to

      A destinations.

      The rest of the paper is organized as follows. The next section provides a brief about related work regarding link stability based multicasting. In section 3,

      D proposing link stability based multicast routing for

      tree based multicast routing scheme. In section 4, a

      E brief discussion about simulation environment In section 5, performance analysis of proposed system

      F G

      Fig 1.1: An example of MANET

      Multicast routing is an efficient way to make easy the group communications in which the messages need to be sent from a transmitting node to multiple receivers. Due to the broadcast nature of the wireless channels, a single transmission can be received by all neighbours of the transmitting node [9]. Therefore, the multicast routing in wireless ad-hoc networks significantly differs from the conventional multicasting in wired networks. In wired networks, the multicast packets are forwarded along the tree edges, and so the multicast routing problem can be defined as a Steiner tree problem (ST), where the multicast group members are the terminals (leaf nodes) in the Steiner tree. While in wireless networks, owing to the broadcast nature of the omni directional antennae, the Steiner connected dominating set (SCDS) problem [10] is a promising approach for modelling the multicast routing problem, where the only multicast group members need to be dominated. Due to the fundamental natural differences, the protocols designed for multicast routing in traditional wired networks cannot be applied to the wireless mobile ad-hoc networks.

      In this paper, we propose a weighted learning automata-based multicast routing protocol for wireless MANETs in which the multicast packets are forwarded along the edges of Steiner tree. To increase the performance of multicasting over MANETs link stability is considered as parameter. Assigning weights to the links and constructing steiner tree with nodes that are less mobile. The weight connected with a communiqué link is defined as its expected duration time which is assumed to be a arbitrary variable with unknown distribution. Routing of packets along the edges of steiner tree to achieve high performance. Expected link duration time is defined as the epoch of time during which the link is expected to be connected. The aim of the proposed algorithm is to find the most stable multicast route among all multicast routes against the host mobility. Comparative analysis with hydra and link stability multicast routing protocol is described here. Hydra is a multicast routing protocol that establishes multicast routing structure approximating the set of source rooted multicast route from multicast source to the

      through simulation and section 6 concludes the paper.

2. Related work

   Recent studies about weighted learning automata- based multicast routing protocol is discussed here. A.Jenifus Selvarani et al [11] presents link stability based multicast routing protocol in MANET to establish route from a source to multicast destinations. When a source node wants to send data to the receiver nodes, multicast mesh is created with stable nodes. Link Stability Based On Qos Aware On – Demand Routing In Mobile Ad Hoc Networks proposed by Prof. Rekha Patil et al [12] estimates link quality based on mobility prediction of nodes and incorporate same in the routing decision. Further new routes are accumulated and the primary transmission path is changed in case a better route in terms of link quality is obtained and proposing the idea of link stability and cost matrix, power consumption to uncover better path in terms of both stability and cost along with QoS support. Link Stability Estimation Based on Link Connectivity Changes in Mobile Ad-hoc Networks [13] proposed a scheme to estimate the link stability based on link connectivity changes, which can be performed on the network layer, without the need of peripheral devices or low layer data and also proposed a method to estimate the link transition rates. Prediction based Link Stability Scheme for Mobile Ad Hoc Networks [14] proposes a method which is to reduce the packet loss and provide better stability using the stability model. The proposed scheme consists of four phases like determination of stability of neighbour node, link, path, total mobile nodes and prediction of total network lifetime. A Radio-Link Stability-based Routing Protocol for Mobile Ad Hoc Networks [15] proposed a protocol, which is named as ad-hoc on-demand stability vector (AOSV) routing protocol, a link stability estimation method and a novel path finding algorithm are developed to find out and maintain stable routes for dynamically required communications services in MANETs. Link stability based routing in mobile ad hoc networks [16] proposed a method that uses link stability factor (LSF) and path stability factor (PSF) to select a stable path while minimizing number of hops. The node's transmission range is divided into

   stable zone and caution zone. Weighted Steiner connected dominating set and its application to multicast routing in wireless MANETs. [17] proposes distributed version of WSCDS algorithm.

3. Proposed work

   Learning automata theory [18] is an adaptive decision making unit in a random environment and learns best possible action through frequent interactions. In wireless MANETs, due to the mobility of nodes the communication links between neighbouring nodes is weak. Because of this reason constructed routes may quickly lose their stability. Using learning automata theory learns the mobility of the nodes and finding out the nodes with less mobility and these nodes will be used for multicasting. To improve the stability of communication links, routes composed of long duration link which is distinct to as link duration time is considered. Depending on the expected duration time of communication links weights are assigned to that links. In this paper we propose weighted learning automata-based multicast routing protocol for MANET considering link stability as a parameter based multicast routing scheme based on learning automata theory. The multicasting routing problem solved by defining a steiner tree problem in multicasting environment. In deterministic case, steiner tree edges have fixed weight. When the weight of edges varies with time, finding the best possible solution is difficult. To overcome the problem of dynamic changes in MANET link stability based learning automata theory is proposed.

   Learning automata theory

   A learning automata theory (Narendra and Thathachar, 1989, Thathachat and Sastry, 1997, Thathachar and Harita, 1987) [19] is an adaptive decision making unit that learns best possible action through repetitive interactions in a random environment. The performances are chosen according to an exact probability distribution which is updated based on the environment reaction the automaton obtains by performing a particular action. The environment reacts to the exact taken action in return with a back up signal. The action probability vector is updated based on the corroborative response from the environment. The aim of a learning automata theory is to recover the optimal action from the action-set so that the average results are received from the environment is minimized.

   Steiner tree

   The steiner tree problem is required to find the shortest interconnected path between set of objects. In MANET, nodes are highly mobile i.e nodes are dynamic. The basic property of steiner tree is that

   Relative speed of each host considered as weight. Forwarding of multicast messages along the MVB(Multicast Virtual Backbone) by which multicast host is connected to multicast receivers.

   additional nodes can be added in to the tree to minimize the cost of routing. In mesh based networks inclusion of additional requires the reconfiguration of the network leading to complex task. Exploiting the property of steiner tree we propose steiner based routing to attain efficient routing in MANET.

4. Simulation

   In order to evaluate qualitative properties of multicasting in MANET such as link stability, we have developed simulations with identical parameter set in ns-2. Focusing on application and routing level measurements, we are able to compare high-level key parameters of mobile ad hoc networks like successfully multicast route life time, route creation delay and transmission delay.

   4.1 Simulation environment

   To study the performance of the proposed multicast routing algorithm, several simulation experiments have been conducted in NS2.In all these experiments, a mobile ad-hoc network is modelled by randomly and uniformly distributing 50 mobile hosts with in a square simulation area of size 900(m)x900(m). The maximum mobility speed of each host changes from 5 to 25 m/sec, and multicast group size is fixed at 4. It is assumed that the mobility characteristics change at the beginning of each epoch. IEEE 802.11 Distributed Coordination Function (DCF) with wireless physical network interface type and two ray ground as the propagation model. All mobile hosts are equipped with omni-directional antennas and have the same radio-propagation range 40 m. The simulated scene comprises parameters like number of nodes, field dimension and simulated time. Table 1 briefly summarizes used values.

   Table 1: Short overview on simulation parameters

   Parameter	Value(s)
   No of nodes	50
   Topography dimension	900(m)x900(m)
   Traffic type	CBR(UDP)
   Average node speed	5-25m/sec
   Mac-type	IEEE 802.11
   Transmission range	40m

   Simulation time(s)	300s
   Radio propagation Model	Two-way ground model
   Antenna type	Omni antenna

   To show the efficiency of the proposed multicast routing algorithm, LLMR (Learning automata-based Link stability Multicast Routing) its results are compared with LSMRM (a link stability-based multicast routing algorithm for MANET proposed by Biradar et al. (2010)), which is existing mobility- based multicast routing protocol. In conducted experiments, the performance of the multicast routing algorithm is measured in terms of the multicast route lifetime, transmission delay and route creation delay.

5. Simulation results

   1. Multicast route lifetime

      Multicast route life time is defined as the period of time during which multicast routes remain connected. This shows the stability of multicast paths and is also called multicast route duration. It is measured in second and this represents the resistance of the multicast routing algorithm. ). LSMRM uses instant information of the communication links to find stable paths and so it cannot predict long-term behaviour of the links. But in case of LLMR, it is capable of predicting the long-term behaviour of links so high packet delivery and multicast route life time is longer. Fig 5.1.1 shows the changes in the multicast route life time as the host speed increases.

      Fig.5.1.1. Multicast route life time versus host mobility (m/sec)

      In this figure the multicast route life time constructed by LLMR (Learning automata-based Link Stability Multicast Routing) is very longer in comparison to the LSMRM (Link Stability based Multicast Routing for MANET).

      1. Route creation Delay

         Route creation delay is as the time spent for building a route i.e how much link will be stable and it is measured in second. This fig 5.1.2 shows the changes in the route creation delay as the host speed increases.

         Fig5.1.2. route creation delay versus host mobility(m/sec)

         In this figure route creation delay for LLMR (Learning automata-based link stability Multicast Routing) is more in

         comparison to the LSMRM (Link Stability based Multicast Routing for MANET).

      2. Transmission Delay

         Transmission delay is defined as the time required for transmitting the multicast packets along the constructed paths. It is measured in seconds and how much time packets are transmitting along the constructed path. Fig 5.1.3 shows the changes in the transmission delay as the host moobility increases.

         Fig.5.1.3. transmission delay versus host mobility (m/sec)

         In this figure transmission delay for LLMR (Learning automata-based link stability Multicast Routing) is shorter in comparison to the LSMRM (Link Stability based Multicast Routing for MANET).

      3. Packet Delivery Ratio

   Packet delivery ratio is defined as the average number of packets received at multicast receivers over the number of packets sent out by the multicast source. So the packet deliver ratio (PDR) defines the efficiency of the routing technique in a multicasting protocol. The packet delivery ratio for all multicast routing protocols decreases as the host speed horizontal to breakage as the host speed increases. This fig5.1.4 shows the packet delivery ratio against mobility

   Fig5.1.4. packet delivery ratio versus speed (m/sec)

   In this figure LLMR (Learning automata-based link stability Multicast Routing) has the high delivery rate because it estimates the expected duration time of the routes over different periods. But in case of LSMRM (Link Stability based Multicast Routing for MANET) delivery ratio is less because it uses instant link stability information to find out the stable paths and so it cannot expect the long-term behaviour of the links.

6. Conclusion

The multicast routing problem (MRP) under MANET scenarios is modelled into the steiner tree problem. This paper, proposes a scheme to find the most stable multicast route among all possible routes. The network parameters are supposed to be random variables with unknown distribution. Modelling the routing in MANET as a steiner tree problem with nodes as vertices and stable links as edges proves to be an efficient multicast routing scheme. In Weighted learning automata-based multicast routing protocol packet forwarding is along the edges of the steiner tree. The multicast routes with longer expected duration time are more stable against the host mobility. This method provides low transmission delay, high route creation delay and high multicast route life time.

REFERENCES

1. Learning automata based multicast routing algorithm for wireless mobile ad-hoc network Javad Akbari Torkestani, Mohammad Reza Meybodi, Journal of Network and Computer Applications 34 (2011) 14291440

2. Link stability based multicast routing scheme in Manet, G N V Prasad , V. Siva Parvathi, Dr.K.Nageswara Rao

   Department of Computer Science & Engineering, PVP Siddhartha Institute of Technology Vijayawada, Andhra Pradesh, INTERNATIONAL JOURNAL OF ADVANCED ENGINEERING SCIENCES AND TECHNOLOGIES Vol No. 8, Issue No. 2, 169 176

3. E-ODMRP: Enhanced ODMRP with motion adaptive refreshI Soon Y. Oh, Joon-Sang Park, Mario Gerla, J. Parallel Distrib. Comput. 68 (2008) 1044 1053.

4. Kaan Bur, Cem Erosy, Ad Hoc quality of service multicast routings, Computer communications, Vol. 29, 2005, pp. 136-148

5. Hui Cheng a, Jiannong Cao, Xingwei Wang, A fast and efficient multicast algorithm for QoS group communications in heterogeneous network, Computer communications, Elsevier, Vol. 30, 2007 pp. 2225-2235.

6. Khalid A. Farhan, Network sender multicast routing protocol, Proceedings of seventh IEEE International conference on networking, 2008, pp. 60- 65.

7. Harleen Dhillon, Hung Q. Ngo, CQMP: A mesh- based multicast routing protocol with consolidated query packets, IEEE Communications Society

   /WCNC 2005, pp. 2168-2174.

8. Luo Junhai, Ye Danxia, Xue Liu, and Fan Mingyu A Survey of Multicast Routing Protocols for Mobile Ad-Hoc Networks, IEEE Computer Communications Surveys and Tutorials Vol. 11, No. 1, First Quarter 2009, pp. 78-91.

9. Nadeem, T., & Parthasarathy, S. (2006). Mobility control for throughput maximization in ad-hoc networks. Wireless Communication and Mobile Computing, 6, 951967.

10. Guha, S., & Khuller, S. (1998). Approximation algorithms for connected dominating Sets. Algorithmica,

    20(4), 374387.

11. J. J. Garcia-Luna-Aceves and E. L. Madruga, The Coreassisted Mesh Protocol, IEEE Journal on

    Selected Areas in Communications, vol. 17, no. 8, pp. 1380-1394, 1999

12. Prof.Rekha Patil, Megha Rani.R and Prof.Rajkumar Bainoor Link Stability Based On Qos Aware On – Demand Routing In Mobile Ad Hoc Networks IOSR Journal of Computer Engineering (IOSRJCE) ISSN: 2278-0661, ISBN: 2278-8727 Volume 5, Issue 3 (Sep-Oct. 2012), PP 52-57

13. Qingyang Song, Zhaolong Ning, Shiqiang Wang, and Abbas JamalipourLink Stability Estimation Based on Link Connectivity Changes in Mobile Ad- hoc Networks

14. Geetha Nair and Dr.N.J.R.Muniraj Prediction based Link Stability Scheme for Mobile Ad Hoc Networks IJCSI International Journal of Computer Science Issues, Vol. 9, Issue 6, No 3, November 2012

15. Jenn-Hwan Tarng, Chung-Hua Univ; Hsinchu Chuang, Bing-Wen; Wu, Fang-Jing; A Radio-Link Stability-based Routing Protocol for Mobile Ad Hoc NetworksSystems, Man and Cybernetics, 2006. SMC '06. vol. 5, IEEE International Conference on Oct. 2006

16. Sun, Jianzhen Beijing Univ. of Posts & Telecommun. (BUPT), Beijing, China Liu, Yuan'an An; Hu, Hefei; Yuan, Dong-ming Link stability based routing in mobile ad hoc networks Industrial Electronics and Applications (ICIEA), 2010 the 5th IEEE Conference on 15-17 June 2010

17. Akbari Torkestani J, Meybodi MR. Weighted Steiner connected dominating set and its application to multicast routing in wireless MANETs. Wireless Personal Communications, Springer Publishing Company; in press-d, doi:10.1007/ s11277-010-9936- 4.

18. Javad Akbari Torkestani , Mohammad RezaMeybodi , A link stability based multicast routing protocol for wireless mobile ad-hoc networks Amirkabir University of Technology,Tehran,Iran, Journal of Network and Computer Applications 34 (2011) 14291440

19. Narendra KS, Thathachar KS. Learning automata: an introduction New York : Prentice Hall; 1989

Ms Joydipa Sen received her Bachelor of Engineering in Computer Science and Engineering in 2011. Currently She is a M.Tech student in Computer Network Engineering from Visvesvaraya

Technological University at The Oxford Collage of Engineering, Bangalore. Her research interests are Computer Networks.

Mrs Vinodha K received her Bachelor of Engineering in Electronics and Communication in 1998. She received her ME in Computer Science and Engineering from Anna University in 2008.She is pursuing PhD in Computer

Science and Engineering at VTU, Belgaum. Currently she also holds a faculty position as Assistant Professor, Department of ISE, The Oxford College of Engineering. Her main resarch interests are Computer Networks and Distributed Networks.