Position Based Mobility Adaptive Multicast Routing in MANET

Position Based Mobility Adaptive Multicast Routing in MANET

R. Shankar,

Research Scholar and Associate Professor, Dept. of Co mputer Science and Engineering,

Aalim Muhammed Salegh College of Eng ineering, Chennai, Ta milnadu, India.

Dr. E. Ilavarasan,

Professor,

Dept. of Co mputer Science and Engg., Pondicherry Engineering College, Puducherry, India

Abstract Grou p communications are essential in Mobile Ad hoc Networks (MANET). Multicast routing is an important technique to implement the group communications. The optimal multicast tree creation needs to repair the group membership management issues and link disconnections induced by the node mobility properly. It is challenging to implement the scalable multicasting in MANET due to the issues in zone membership maintenance and multicast packet routing over dynamic environment. This paper introduces an efficient zone multicast scheme, based on mobility prediction, which track the future movement of the node in a precise way for efficient data delivery. The proposed Mobility Prediction AIDed Multicast Routing Protocol (MP-AID- MRP) constructs a virtual-zone-based structure to implement scalable and efficient group membership management. In order to reduce the mobility impact on the maintenance of tree structure and packet routing, the position information of the node is utilized to conduct the zone structure building, multicast tree construction, and multicast packet forwarding. The location- aware quick group is joining and leaving technique for more reliable membership management and packet transmissions dramatically improves the scalability even under a large network. The mobility prediction based zone leader handoff and group maintenance completely reduce the redundant overhead, and thus it achieves high scalability and adaptability to the highly dynamic environment. The simulation results demonstrate that proposed MP- AID-MRP is an effective protocol in term of high packet delivery ratio and low control overhead with a high degree of node mobility. Finally, it reveals that the proposed protocol, MP- AID-MRP performs well other than the existing multicast routing protocol EGMP.

Keyword sMANET, Multicast, Greedy Selection, Node Mobility, Mobility prediction, Scalability, and Efficiency.

1. INT RODUCTION

   A set of mob ile nodes in MANET is capable of making a direct or mu lt i-hop commun ication with each other [1]. These nodes are free to move anywhere at any time . The wireless communication between mobile nodes requires routing over multiple -hop wire les s paths. Much work applies unicast routing protocols over wire less communications . However, mu lticas t is a fundamental routing service to enable communicat ion among group of mobile nodes, where one-to- many data dissemination is in need such as disaster recovery s cenarios [2] [3]. Recently, the geographical routing protocols have been proposed for more scalable and efficient routing. In geographical routing protocols , the mobile nodes are aware of

   their own location in formation using Global Positioning System (GPS) or other location services.

   The local topology or geographic based routing mechanis m is more scalable and robust in a dynamic network topology. Making use of pos ition information to design the mu lticast routing scheme reduces the topology maintenance overhead and support more reliable routing. Ho wever, there are many challenges to imp le menting an efficient and reliable position based multicas t routing scheme over wire less communicat ion [4] [5]. For e xa mp le, a data packet carries the destination address to guide the packet forwarding in unicast routing protocols , whereas , in mult icasting the receiver is a group of nodes. A s imple way to apply the geographic routing in mult icas t routing is to load the address of all rece ivers into the packet header directly, however, it increases the packet header overhead over large scale network topology [6] [7]. The mu lticas t routing design is comple x due to the dynamic network topology and the limited network capacity. It is essential to reduce the states to be maintained in the network and make the mu lticast routing that should not impacted by the dynamic network topology.

   The proposed work, MP-AID-M RP influences the process of forwarding node selection and zone bas ed multicas t routing performance under highly dynamic netwo rk topology. This mobility prediction and fast update of the lis t of zone me mbe rs improves the overall performance of MP-AID-MRP. The simu lation results demonstrate that the proposed MP- AID-M RP provides an effective routing in terms of the high packet delivery ratio and routing overhead under highly mobile scenarios . It attains high scalability and effic iency under both group maintenance and data communicat ion than EGMP with the high frequency of node mobility.

   1. Problem Statement

      The design of highly efficient and scalable mult icas t routing protocols has many is sues such as scalability and reliability over MA NET environment. The proble ms associated with the zone based multicas t routing are group ma intenance and link disconnection due to the unpredictable node mobility in the network. Frequent and hard to predict the topology changes in the network due to the node mobility is the most important iss ue taken into account for improving the mu lticast routing scalability and effic iency. A greedy routing

      has taken in the geographical routing for providing an adaptive routing even under dynamic netwo rk environ ment. Ho wever, a greedy selection is not an optima l solution for deciding the forwa rding node always, as it can eas ily move out of the sender nodes communication range. In e xis ting multicas t routing schemes, the mobility factors of the network are identified, but the prediction of these factors is difficult under real t ime scenarios . Determining an optima l solution to the node mobility impact on the multicas t routing mechanis m is challenging, s ince the existing multicas t routing approaches take routing decision by assuming the probability dis tribution function of these random factors. Moreover, it s ignificantly fell down the group me mbership maintenance and degrades the mult icast routing performance. The re is a need to propose a geographical mult icast routing protocol for ach ieving efficient and scalable group communication over highly dynamic environment.

   2. Aim and Objectives of the paper

      The main aim and objectives of the paper are,

      • To construct a virtual zone based s tructure using the location information of the mobile nodes

      • To manage group me mbership of mobile nodes in a zone based virtual s tructure, under a highly dyna mic network topology

      • To select an efficient zone leader and route the mu lticast data packets using a mu lticast tree with the support of mobility prediction scheme

      • To enhance the scalability of zone based multicas t routing by reducing routing overhead, and eliminate the frequent broadcas t of beacon packets among the neighboring nodes.

   3. Paper Organization

   The rest of this paper is organized as follows . Section 2 discusses the related work of existing mult icast routing protocol. Section 3 e xp lains a proposed highly efficient MP- AID-M RP. Fina lly, Sect ion 4 demonstrates the s imulat ion results and concludes the proposed work in Section 5.

2. RELATED WORKS

   Several mult icast routing protocols build distribution s tructure either in mesh or tree-bas ed s tructure for delivering the mult icast packet in a dynamic environ ment. In e xisting, tree-bas ed multicas t routing technique forwards the data packets on a single route to a particular receiver. The association of routes to all the mult icast receivers forms the mu lticast tree, which is common for all the senders in a mu lticast session. However, the mesh-based routing includes mu ltip le paths to each receiver, but this redundancy leads to increased protection against dynamic environ ment.

   1. Multicast Routing Protocols

      The conventional topology based multicas t routing protocols includes tree [8-10] [11] and mesh-based protocols ([4], [12]). The tree-bas ed protocols form a tree topology for more effic ient forwarding of mult icast packets to all the

      receivers . Mesh-based routing protocols expand the tree s tructure with mu ltip le routes and these routes forward packets when the route gets failure. Even though the topology-aware tree or mesh-based routing are effic ient for the MANET environment [5], the global topology maintenance is difficult to scale to a large scale network topology. It is because, the s tates to be maintained in the mult icast routing increases the control routing overhead. The works in [13], [14] design the stateless mu lticast protocol [15] and it p rovides better scalability even to a large scale network topology.

      In contrast, EGMP [16] employs a location-aware mu lticas t routing scheme for efficient maintenance of group me mbe rs and supports high scale network topology. In order to obtain the location of the nodes and maintain the group, the geographic multicas t routing protocols require location s ervice

      [17] [18]. The geographic multicas t protocols in [19], [20] and
      [3] need to load entire tree information in the packet header, and this increas es the routing overhead when the group s ize is large. In contrast, the DSM [19] a llo ws each node to flood its location in the network. Moreover, a mult icast source node builds a Steiner tree and encodes the information about the entire multicas t tree into the data packets and follows the source routing to deliver the data packets . Two overlay mu lticas t trees , LGT [20] require each group to inform their location information with the members of all other groups.

   2. Mobility Impact on Multicast Routing

   The node mobility incurs additional challenge to the mu lticast routing protocol. It results in the frequent handover process of zone leader and link failure. With the use of geographical informat ion [21], ODM RP improves the scalability of mu lticas t routing by res tricting the flooding in a specific geographic region. In dynamic source mult icas t, DSM each node floods its position informat ion and knows the location of all others in MANET. The mult icas t source node constructs the multicas t tree from the position information of all receivers . This tree information is efficiently encoded in the packet header. By default, the mult icast source node forwa rds the data packets in a greedy manner. When no s uch neighbor exis ts in the positive progress set, the routing s cheme recovers the sys tem fro m local co mmunication hole. However, frequent lin k failure due to dynamic network topology impacts the multicas t routing scalability and effic iency. Both, the tree and mes h-bas ed multicas t routing protocols , need to maintain s tate information about the dis tribution s tructure and thus they are limited to environ ments, where the node mobility is high.

3. OVERVIEW OF THE PROPOSED METHODOLOGY The proposed mobility prediction aided multicas t

   routing protocol, MP-AID-MRP is location based routing protocol, each node identifies its own position informat ion using GPS. The location-bas ed mult icas t routing performs three prima ry functions such as multicas t structure construction, group members hip ma intenance, and multicas t data forwarding. In our propos ed MP-AID-M RP, cons iderable enhancements that provide adaptability for the unpredictable

   node mobility are carried out in three primary functions in location based multicas ting.

   1. Multicast structure construction with Mobility Prediction

      In the proposed MP-AID-M RP, constructs the virtual zone based s tructure in the form of two -level h ierarchy. In the lower level, each node identifies its zone id distributively, and each zone me mber e lects a leader based on the node mobility factor. In the upper level, elected zone leaders of every zone serve as a representative for its zone and also take responsibility fo r a new node joining or leaving process.

   2. Group membership maintenance

      In order to reduce group members hip ma intenance overhead, MP-AID-M RP a llo ws each node inspect only its group members hip changes rather than tracking of each node move ment. In the case of wrong prediction, the me mber node informs its new location only to its zone leader, wh ich periodically broadcas t the beacon packet including its group me mbe rship information. Hence, node movement in the routing zone is eas ily identified with the help of mobility prediction.

   3. Mobility Adaptive Multicast packet forwarding

   Towards destination zone, the mult icast source node selects the next hop and forwards the multicas t routing packets . Multicast source node forwards the data packets from source to destination means source node selects one of its me mbe rs or ordinary node which is closer to the destination. Moreover, a frequent detection of node mobility and fast joining and leaving process of the mobile node under highly dynamic network topology improves the multicas t packet forwa rding.

4. MOBILIT Y PREDICTION AIDED MULT ICAST ROUTING PROTOCOL (MP-AID-M RP)

   The ma in is sue in multicas ting is the proper selection of zone leader and group ma intenance under highly dynamic environment. To enhance the performance gain of the mu lticas ting, the MP-AID-M RP inc ludes mobility predict ion with the process of three primary functions in location based mu lticas ting. The MP-AID-M RP form v irtual zone structure using a reference point. However, the zone construction does not depend on the network structure, and this makes the proposed work eas y to maintain the zone. A multicas t group crosses multip le zones, and there is no need to track individual

   1. Zone Leader Election

      In every zone, each mobile node may act as a zone me mbe r or an ordinary node. Each zone selects a node to act as a leader (Zldr) that manage the multicas t group me mbers. To init iate the process, the zone leader selection and ma intenance process follows three s teps. Initia lly, each node in the zone broadcast the hello packets including its current location with velocity and measures Acceptable Location Change (ALC) factor for its elf and Zone leader, Zld. Init ially, each node in each zone elects a node with les s ALC va lue, and it should be located at the center of the zone region [19] [20]. This node is named as Zone leader, Zldr. In the second s tep, the Zldr selected in a dis tributed manner periodically broadcas ts the beacon packets including the lis t of zone me mbers and re main ing neighboring nodes in the commun ication range with the measured ALC value for every i interval. In the third step, Zldr measures ALC value for all the neighboring nodes, and a node updates its location informat ion to the Zldr, only when the measured ALC value is false. Thus, there is no need to broadcas t the beacon packets frequently among the neighboring nodes , including both zone members and ordinary nodes in the zone. Moreover, each node is aware of its neighboring nodes and divides the neighbor zones into upstream and downstream zones based on its dis tance to the destination zone. The upstream zone supports to ma intain the virtual zone, when it has no zone members.

      /*Neighbor List and Zone Leader Selection*/

      Each node in a zone do

      {

      Broadcas t the beacons to all nodes, n;

      Creates the neighbor's list for each node i, NHi; Zldr election ();

      NHi Update ();

      }

      Zldr election: each i do

      {

      For( i=1; i<=n; i++)

      {

      For( j=i+1; j<=n; j++ )

      {

      If (ACL < ACL )

      node movement. It is sufficient to track the move ment of i j

      group members , and thus it reduces the routing overhead. By {

      using the constraint virtual based zone cons truction and ma intenance [19], the proposed work can s ignificantly minimize the maintenance overhead and improves the efficiency of the proposed MP-AID-M RP protocol performance.

      Temp = A CLi;

      }

      }

      Temp elected as Zldr;

      }

      }

      ìï ï ï ï

      ìï ï ï ï

      NH Update alg: do æ X – X ü ìVx – Vy ü ö

      { ALC = ç i j + i j * t ÷ – – – – -(2)

      çíY – Y ý íVx – Vy ý ÷

      Receives Zone me mber list, ZMl fro m Zldr; èîï

      i j ïþ i j ø

      Updates the NHi:

      }

      Fig. 1 Algorit hm for Zone Leader Election and Group Maint enance

      On receiv ing the beacon packets , each node compares the neighboring nodes ACL to others and select a node which is the center of the zone region. In each one, a high s tability node is elected as a Zldr and the neighboring nodes send the vote message to it. To ensure its leadership, the Zldr broadcas ts it for every i/2 period enabling the leader flag b it in the beacon packets . Moreover, it includes the predicted next location of neighboring nodes, and thus it minimizes the beaconing overhead, as there is no need to do the position update among all the neighboring nodes. Instead of that, Zldr includes the neighboring node list in beacons .

   2. Group membership maintenance

      This section describes the mult icas t group me mbership construction and maintenance schemes. It facilitates adaptive group joining and leaving, and empty zone handling process [EGM P]. On the node joining process, it sends the join request to Zldr when it overhears the data transmission of particular mu lticast session or receives the beacon message from Zldr. Each ordina ry node sends the beacon packet including its Zldr informat ion per every I interval. Thus, each Zldr is aware of its neighboring zones. Under highly dynamic environ ment, the measured ALC assists to maintain the zone me mbership efficiently.

      1. Acceptable Location Change

         In the proposed MP-AID-M RP, each Zldr predicts the next location of its zone me mbe rs and ordinary nodes using a s imp le predict ion scheme and measures ALC for each of its neighboring nodes. Based on the location prediction scheme, the Zldr can ensure whether the zone me mber or an ordinary node is s till with in their co mmunication range and update their lis t accordingly. For every i/2 time period, the Zldr sends beacon packets including both the lis t of zone me mbers and ordinary nodes. The main rule of the mobility prediction scheme is to inform the location information fro m node i to Zldr, when the error is identified between the predicted location informat ion of node i and node is actual location after its move ment.

         Over a re latively short period of time, one can assume that each node, i follo ws a linear tra jectory, and its next location is a function of time and velocity as shown in the equation (1).

         ìX ü Vi

         If an error occurs between the original and its predicted next location, it ma kes an error in the ALC value. In this case, a node i send its original location informat ion to the Zldr and it informs all the neighboring nodes using beacon packet. Note that each node measures ALC for Zldr. In case of Zldr move ment prediction, the higher priority node waits to receive the handover message from Zldr and the measured ALC of Zldr is high, it sends messages to provide the leadership for higher priority node, attaching the selected node address as Zldr. Thus, it s ignificantly min imizes the routing overhead and impact of node mobility on zone management, and moreover, it reduces the node mobility impact on the group maintenance and reduces the routing overhead.

   3. Multicast Data Forwarding

   The proposed MP-AID-M RP d ivides the neighboring zones into upstream and downstream zones based on its distance to the destination zone without using additional beacon packets [20] [21]. When a node i wants to forward the mu lticas t packets to a lis t of multicas t receivers (R1; R2;::Rn), it decides the next hop node towards each destination or select forwarders fro m the upstream zone as shown in the Fig. 2.

   (0,0)	(0,1)	(0,2)	(0,3)
   (1,0)	(1,1)	(1,2)	(1,3)
   (2,0)	(2,1)	(2,2)	(2,3)
   (3,0)	(3,1)	(3,2)	(3,3)

   Group Member Zone Leader

   Mu lticast Receiver Source Node

   Fig. 2 MP-AID-MRP

   i

   i

   Pos (t +1) = í

   ý + í

   x ý * (t – t1) – – – – -(1) In order to determine the nearer neighbor node to

   v

   v

   îYi þ Vi

   upstream s tream, each node calculates the distance of its neighboring nodes in the upstream zone to reach its target zone (Xtgt,Ytgt) as follows ,

   æìX – X ü ìdx – dxy ü ö

   2) Control Overhead

   Control overhead is also the ratio between nu mber of

   D(i, j) = çï i jï+ ï i j ï * t ÷ – – – – -(3) control messages accumulated over through each hop to the

   çíY – Y ý

   ídx – dxy ý ÷

   è i j i j ø total number of data packets received at the destination. Under

   the dynamic mobility, high overhead is incurred to maintain

   Thus, a zone with a s maller distance value is closer to the target zone is determined. The source node will forward the data packet towards the zone leader of the target zone. After determining the very nearer ne xt hop node to reach the target zone. Zone representative forward the data packet to the destination node in the zone by explo iting the informat ion in the membership table after arriv ing at the destination zone.

5. PERFORMANCE EVALUAT ION

   The NS2 simulat ion is employed to evaluate the performance of proposed priority location aided scalable mu lticast protocol. The propos ed work is simu lated in the network doma in consists of 100 nodes s ituated randomly within the flat square of area 1000m x 1000m area. Moreover, in the s imulation the velocity of each node varies between 10 and 60 m/s. To show the advantage of proposed algorithm MP-AID-M RP, the performance co mparison is evaluated between existing EGMP and proposed protocol.

   1. Simulation Results

      The following section illus trates the experimental results of the proposed protocol in terms of packet delivery ratio and routing overhead with varying node mobility.

      1. Packet delivery ratio

   The packet delivery ratio is defined as the ratio between the number of packets received at the destination to the number of packets sent from the source. In order to improve successful transmission of data packets from source to destination, proper zone me mbership maintenance is performed in accordance with dynamic mobility. The proposed work predicts the mobility of zone leader and its neighboring nodes, and hence in MP-AID-M RP, the high packet delivery ratio is achieved rather than other stateless mu lticast protocol, EGMP.

   Fig. 3 Node velocit y Vs Packet Delivery Ratio

   group members hip of all nodes in a zone. Location updation is performed in accordance with the ind ividual node move ment, but it leads to large e xces s ive overhead in EGMP. However, in the proposed MP-AID-M RP reduces the location updation among neighboring nodes and min imizes the node mobility impact on multicas t routing.

   Fig. 4 Node velocit y Vs Control Overhead

6. CONCLUSION

In this paper, a zone based mult icast routing protocol MP-AID-M RP for MA NET is proposed. The proposed apprach attains high scalability and effic iency by selecting s table forwarding me mbe rs using mobility prediction s cheme. Thus, the group me mbership maintenance and multicas t data transmission successfully perform their tasks using the accurate location information that reduces the routing overhead and access delay. The use of location informat ion for construction of the zone structure s ignificantly reduces the group maintenance comple xity. In the proposed MP-AID- MRP, the partition of neighbor zones into upstream and downstream zones handles the empty zone problem without incurring control overhead. Achieving fast tree structure adaptation under dynamic network topology and avoid redundant packet transmission, the MP-AID-MRP e mp loys the location prediction scheme in a p recise way. Thus, it influences the process of forwarding node selection and zone based mult icast routing performance in MANET. Expe rimental results obtained from the simulat ion demonstrate that the proposed protocol MP-AID-M RP achieves a high packet delivery ratio and reduced control overhead under highly dynamic environ ment. Finally, it reveals that the proposed protocol performs we ll when compared to the existing EGM P.

REFERENCES

1. Carlos De Morais Cordeiro and Dharma p. Agarawal Mobile Ad hoc networking, OBR research centre, pp. 1-63, 2002.

2. S. Basagni, I. Chlamt ac, and V. R. Syrot iuk, Location aware, dependable multicast for mobile ad hoc net works, Computer Net works,

   Vol. 36, No. 5-6, pp. 659670, 2001

3. M. Mauve, H. Fubler, J. Widmer, and T. Lang, Position-based multicast rout ing for mobile ad-hoc net works, In Poster sect ion in ACM MOBIHOC, 2003

4. C.-C. Chiang, M. Gerla, and L. Zhang, Forwarding group mult icast protocol (FGMP) for multi-hop mobile wireless networks In AJ. Clust er Comp, Special Issue on Mobile Comput ing, vol. 1, no. 2, pp.187196, 1998

5. J. J. Garcia-Luna-Aceves and E. Madruga, The core-assist ed mesh protocol, In IEEE JSAC, pp. 13801394, 1999

6. Young-Bae Ko and Nitin H. Vaidya, Geocast ing in Mobile Ad Hoc Networks: Locat ion-Based Multicast Algorit hms, 1999

7. Kai Chen and Klara Nahrstedt, Effect ive Locat ion-Guided Tree Construct ion Algorit hms for Small Group Multicast in MANET, IEEE Infocom, pp. 1180-1189, 2002

8. E. M. Royer and C. E. Perkins. Multicast operat ion of the ad hoc on- demand distance vector rout ing protocol. in Proceedings of the ACM/IEEE Int ernat ional Conference on Mobile Comput ing and Networking (MOBICOM), August 1999, pp. 207218.

9. C. Wu, Y. Tay, and C.-K. Toh. Ad hoc multicast rout ing protocol ut ilizing increasing id-numbers (AMRIS) funct ional specificat ion. Internet draft, November 1998.

10. X. Zhang and L. Jacob. Multicast zone rout ing protocol in mobile ad hoc wireless networks. in Proceedings of Local Computer Net works, 2003 (LCN 03), October 2003.

11. V. Devarapalli and D. Sidhu. MZR: A multicast prot ocol for mobile ad hoc networks. In ICC 2001 Proceedings, 2001

12. M. Gerla, S. J. Lee, and W. Su. On-demand multicast rout ing protocol (ODMRP) for ad hoc net works. in Internet draft , draft -iet f-manet- odmrp- 02.txt, 2000.

13. C. Gui and P. Mohapat ra. Scalable Multicasting for Mobile Ad Hoc Networks. In Proc. IEEE INFOCOM, Mar. 2004.

14. C. Gui and P. Mohapatra. Overlay Multicast for MANET s Using Dynamic Virt ual Mesh. In ACM/Springer Wireless Net works (WINET), Jan. 2007.

15. L. Ji and M. S. Corson. Different ial dest inat ion mult icast : a MANET mult icast rout ing protocol for small groups. In Proc. IEEE Infocom01, Anchorage, Alaska, April 2001.

16. Xiang, Xiaojing, Xin Wang, and Yuanyuan Yang. "Support ing efficient and scalable multicasting over mobile ad hoc net works." Mobile Comput ing, IEEE Transact ions on 10.4 (2011): 544-559.

17. J. Li and et al. A scalable locat ion service for geographic ad hoc rout ing. In Proceedings of the ACM/IEEE International Conference on Mobile Comput ing and Networking (MOBICOM), pages 120130, 2000.

18. S. Giordano and M. Hamdi. Mobility management : The virtual home region. In Tech. report , October 1999.

19. S. Basagni, I. Chlamt ac, and V. R. Syrot iuk, Locat ion aware, dependable multicast for mobile ad hoc networks, Comput er Networks, vol. 36, no. 5-6, pp. 659670, August 2001.

20. K. Chen and K. Nahrst edt . Effect ive location-guided t ree construction algorithms for small group multicast in MANET. In IEEE INFOCOM, 2002, pp. 11801189.

21. B. Karp. Greedy perimet er st ateless rout ing (GPSR). http://www.icir.org/bkarp/gpsr/gpsr.ht ml.