Energy Optimization And Load Balancing Using Tree Based Multicast Routing Protocol For Mobile Ad Hoc Network

Energy Optimization And Load Balancing Using Tree Based Multicast Routing Protocol For Mobile Ad Hoc Network

1

Guru Prasad

M-tech II year,CSE dept GNDEC Bidar

2Prof Arvind S

GNDEC Bidar

Abstract

A mobile adhoc network (MANET) is an interconnected system of mobile hosts without a xed infrastructure. In MANETs, each mobile host has multi-hop transmission capability, and it has to serve as a router. Owing to the dynamic topology and limited resources of mobile hosts, the routing scheme in MANETs presents an important challenge. In this study, a Energy Optimization and Load Balancing using -tree- based multicast routing protocol (EOLTMRP) for MANETs is proposed. In the proposed scheme, all nodes are randomly classied into two types, group-1 and group-2. To achieve the load balance, two multicast trees (tree-1 for group-1 and tree-2 for group-2) are constructed. Thus proposed system outperform AOMDV version of AODV in term of Performance evaluation metrics such as packet delivery ratio, control overhead , Network life time, Normalized delay

Keywords: Packet Delivery Ratio, Control Overhead, Network life time, Normalized Delay.

1. Introduction

   A mobile adhoc network (MANET) is an interconnected system of mobile hosts without a fixed infrastructure. Every node in an MANET must be able to function as a route to forward data to other nodes. When applications must send the same data to more than one destination, multicasting is often used. Multicasting reduces the communication costs for applications that send the same data to multiple recipients. Instead of sending via multiple uni-cast, multicasting minimizes the link bandwidth consumption, router processing and delivery delay.

   Existing multicast routing protocols for MANETs can be broadly classified into tree-based routing protocols [1-9] and mesh-based routing protocols [10-15]. Tree-based routing protocols build a tree

   structure that connects all multicast members and provide one path between a pair of source and destination nodes. Mesh-based protocols yield a multi-path between the source and the destination nodes. When a link fails, mesh-based multicast protocols do not need to re-compute a mesh. Royer and Perkins [7] propose a multicast ad hoc on demand distance vector routing protocol (AOMDV). AOMDV establishes on-demand multicast tree and uses these for delivery of multicast data. AOMDV is a typical tree-based multicast routing protocols. A mobile adhoc network is a collection of wireless mobile nodes that communicate with one another without any fixed networking infrastructure. Ad Hoc networks are multi-hop wireless networks where all nodes cooperatively maintain network connectivity. These types of networks are useful in any situation where temporary network connectivity is needed, such as in disaster relief. In multi-hop wireless ad- hoc networks, designing energy-efficient routing protocols is important because nodes have limited energy. However, it is also an inherently hard problem due to two important factors: First, the nodes may be mobile, this requires that the energy- efficient routing protocol should be fully distributed and adaptive to the current states of nodes; Second, the wireless links may be uni- directional due to asymmetric energy configurations of adjacent nodes.

2. Routing Protocol

   Ad hoc Routing protocols is classified into two types such as proactive and reactive. The table- driven routing protocol is proactive , it worked on distance vector based or link state based routing strategies. The drawback of this algorithms is the frequent updation is required which consumes large amount of memory, bandwidth and energy [1]. But, in the reactive routing protocol, each node does not need to maintain the routing table. When a source node is ready to send data, it initiates the

   route discovery procedure and maintains its routes only. The reactive routing protocol minimizes the routing overhead and also called on-demand approach.

   1. Aodv protocol

      The AODV [2] protocol based on the reactive routing discovery uses three different kinds of messages: Route request (RREQ), Route Reply (RREP) and Route Error (RERR). In addition, destination sequence numbers are used to ensure loop freedom at all times. In AODV, each source node finds a new route by the limited flooding of RREQ and obtains a route to its destination through RREP.

   2. Aomdv protocol

      The AOMDV [3] protocol is the extension of AODV routing protocol, in which the source node keeps several different alternative routes from multiple RREPs. The static route selection is used in AOMDV, it cannot handle the dynamic change of the network due to severe congestion caused by biased traffic. Multipath Routing with Load Balancing QoS in Ad hoc Network [4] gives new protocol proposed for Ad Hoc routing. Minimization of Maximum Delay in

      [5] deals with only delay that does not satisfy the bandwidth requirement.

      AOMDV [7] is based on ad-hoc on-demand distance vector routing (AODV) [27], and it is an extension of AODV in supporting multicasting. AOMDV establishes on-demand multicast tree and uses these for delivery of multicast data. AOMDV uses a shared group tree and periodically uses hello messages for link break detection and group leader oods for group information dissemination. When a mobile node wishes to join a multicast tree or has data to send to a multicast group but it does not have a route to that group, the mobile node broadcasts a route request (RREQ) packet. Only members of the desired multicast group can respond to a RREQ.

      When an intermediate node receives a RREQ packet, the intermediate node rebroadcast the RREQ to its neighbours. A node receiving the RREQ packet may unicast a route reply (RREP) to the source node if it is either the destination or a member of the multicast tree with a corresponding sequence number greater than or equal to that of the RREQ. As nodes along the path to the source receive the RREP, they add both a route table and a multicast routing table entry for the node from which they received the RREP.

      After the source node receives the RREPs, it selects the route with the largest sequence number and shortest hop count from the RREPs and sends a multicast activation (MACT) message to select its next hop. The MACT message activates the route. The next hop node receiving the MACT message enables the entry for the source node in its multicast routing table. If the node is a member of the multicast tree, it does not send the MACT message any further. However, if the intermediate node is not a member of the multicast tree, it receives several RREPs from its neighbour. The MACT message ensures that the multicast tree does not have multiple paths to any tree node. The intermediate node forwards data packets only along the activated route.

3. Energy Optimization and Load Balancing dual tree Multicast Routing protocol

In this study,a Energy Optimization and Load Balancing using tree-based multicast routing protocol (EOLTMRP) for MANETs is proposed. In the proposed scheme, all nodes are randomly classied into two types, group-1 and group-2. To achieve the load balance, two multicast trees (tree-1 for group-1 and tree-2 for group-2) are constructed.

Each node maintained two routing tables: the neighbouring table and the routing table. The neighbouring table was easily obtained by the periodic broadcast of the hello packet. These tables are described below:

1. Neighbouring table: Any node which want to know which are its neighbour with in its tansmission range it will broadcast Hello packet . The nodes which are in transmission range will reply to Hello packet. The format of the table was<node_id, distance>.

2. Routing table: This table contained the path that was used for the transmission of data. The format of the path table was <sourceID, destination_ID,seq_number,r oute_class,next_hop>

.The source_ID and destination_ID elds contained the unique addresses of the source and the destination node, respectively. The seq_number eld contained the sequence number of the source node (guaranteeing the loop-freedom of all routes to the destination node). The route_class eld recorded the class of route for group-1 or group-2. The next_hop eld contained the address of the neighbouring node to which data packets had to be forwarded.

3.1 Route Discovery Process and Route Maintainance

In the proposed scheme, energy level threshold (Pthreshold) is defined. When the source node wants to send the packet to the destination nodes, it broadcasts the route request (RREQ) packet to the neighbouring nodes in its transmission range, when the source node does not have a path in the routing table. The RREQ packet carries the following information in its header:<kTYPE, Source, DestinationList, SourceSeq,PathTraversed, Class, RREQTypel. Type refers to the packet type: RREQ, RREP or RERR. Source is the source node. SourceSeq is a monotonically increasing sequence number. Source and SourceSeq are used to uniquely identify each RREQ packet. It can be used to check duplicate copies of an old request and detect the stale cached routes. DestinationList is a set of destinations. PathTraversed records the routing information. Class is the type of node: group-1 or group-2. RREQType refers to the RREQ type: RREQ,After neighbouring nodes receive the RREQ packet, the neighbouring nodes first check the remaining battery of nodes (Premain). When Premain of nodes is higher than Pthreshold, the neighbouring nodes store received the RREQ packet and re-broadcasted the RREQ packet. The neighbouring node adds its ID to the routing path field of the RREQ packet and the class field of the RREQ packet is assigned a type (group-

1 or group-2) of neighbouring node. When the destination node receives the first RREQ packet with group-1 and the first RREQ packet with group-2, the destination node selects the last hop of each RREQ packet as its upstream node to be the primary routing paths for tree-1 and tree-2. Then, the destination node sent two route reply (RREP) packets to the source node. The RREP packet carries the following information in its header:

<TYPE, Source, Destination, ReversePath, Class,RREPType>. Here Type is certainly RREP. Source is the source node. Destination is the destination node. The field ReversePath in each RREP packet includes the reverse path. Class is the type of node: group-1 or group-2.The Class field of RREP packet is the assigned type for the RREQ packet. When the intermediate node receives the RREP packet, it selects the upstream node based on the corresponding type of RREP packet and sends the RREP packets to the source node. The detail of the route discovery process.

Algorithm: A network is modelled as graph G(N, E), where N is the finite set of mobile nodes and E is a set of links. Suppose n is the number of mobile nodes and N is the set of mobile nodes N= {N1, N2, . . . , Nn}. Assume that source node Ni wants to find a path to destination node Nj. Node Ni broadcasts a RREQ packet, and node Nk receives the RREQ packet, where Ni, Nj, Nk [ N, 1 i, j, k

n and i = j.if (node Nk is the destination node Nj)]

{

1. Node Nk selects the first RREQ packet with group-1 and RREQ with group-2 as the upstream node and unicasts a RREP packet to the source node.

2. Each node receives the reply RREP packet and writes the entry to the current routing table. Then the node selects an upstream node with a corresponding type of RREP.

}

else if (Premain of node Nk is higher than Pthreshold)

{

1. Node Nk stores the received RREQ packet in its list of upstream nodes.

2. Node Nk forwards the RREQ packet to the neighbouring nodes.

}

else

Node Nk discards the request packet.

The simulation was implemented by using NS2 (Network Simulation 2, version 2.35) [30]. The simulation modelled a network in a 900 m × 900 m area with varying mobile speed. We used random waypoint model was used as mobility model. In random waypoint model, each node randomly selects the moving direction, and when it reaches to the boundary of simulation area, it bounces back and continues

to move.. The transmission range was 150 m. The data packet size was 250 bytes. The initial defined Pthreshold was 15 J. Each simulation was executed

for 10 s. The source and destination nodes were

randomly chosen and each node was randomly assigned an initial energy. We used constant bit rate (CBR) as the traffic type. In CBR model, the source transmits a certain number of fixed size packets. The parameters used in the simulations are listed as shown below.

The performance evaluation metrics used in the simulations were:

1. Packet delivery ratio: The data packets delivered divided by the data packets expected to be delivered.

   .

2. Packet delivery delay: The interval from the time the multicast is initiated to the time the last host finishes its multicasting.

3. Total Energy consumption: The total consumed Energy of all nodes after data transmission.

4. Wireless Simulations

   The Network simulation-2 implementation has following important parts.

   • Generating wireless Environment

   • Creating UPD and FTP Agent

   • Various modules are added to simulate node mobility and wireless networking such as mobile node, ad-hoc routing such as aodv, MAC802.1

   • Radio propagation Model and channel etc.

     Figure 1 .Simulation at NAM

     Simulator	Ns-2.35
     Routing Protocol	AOMDV,EOLTMRP
     Simulation Time	500sec
     Number of Mobile Nodes	50
     Mobility speed(m/s)	5,10,15,20,25
     Mobility Model	Random way point Model
     Simulation Area	900 X 900
     Node transmission Range	150 m
     Data packet Size	250 bytes
     Traffic Type	CBR

     Table 1.Simulation Parameter

     .

     The simulation was implemented by using NS2 (Network Simulation 2, version 2.35) [30]. The simulation modeled a network in a 900 m × 900 m area with 50 mobile nodes. We used random way

     point model was used as mobility model. In random waypoint model, each node randomly selects the moving direction, and when it reaches to the boundary of simulation area, it bounces back and continues to move. The mobile speed of each node was from 1 to 25 m/s. The transmission range was 150 m. The data packet size was 250 bytes.

     The initial energy of each node was 10 J. Pthreshold was 15 J. Each simulation was executed for 500s. The value in the following simulation figures are the average values of 50 runs. The source and destination nodes were randomly chosen and each node was randomly assigned an initial energy. We used constant bit rate (CBR) as the traffic type.

5. Simulation Results

   In the following, the impact of mobility speed on AOMDV and EOLTMRP is studied. These protocols have been simulated for packet delivery ratio, packet delivery delay and total energy consumption. From Figs. 24, we depict the routing performance of two protocols under different mobility speeds. Fig.2 shows the perormance of the packet delivery ratio under various mobility speeds. As shown in Fig.2, the packet delivery ratio decreased with increasing mobility because of more link breaks. Notice that the packet delivery ratio is high when the nodes have low mobility. EOLTMRP achieves a much higher packet delivery ratio than AOMDV because energy is evaluated while establishing of two stable routing paths for multicasting. Thus, the packet delivery ratio of EOLTMRP is higher than that of AOMDV.

   From Fig 3 we depict performance of the packet delivery delay under various mobility speeds. As shown in Fig.3, as the mobility speed increases, the packet delivery delay also increases. The packet delivery delay of EOLTMRP is lower AOMDV. This is also because energy is evaluated while establishing of two stable routing paths for multicasting

   From Fig 4, shows the performance of the total energy consumption energy under various mobility speeds. Owing to the mobility of the node making the control overhead increases, it consumes more energy. Therefore the total energy consumption increases with increasing mobility. As observed in Fig 4, the total energy consumption of EOLTMRP is lower than that of AOMDV. This is because of EOLTMRP reducing the energy consumption by using dual trees for transmission

6. Conclusion

Fig 2.Packet Delivery Ratio against mobile speed(m/s)

Fig 3.Packet Delivery Delay against mobile speed(m/s)

Fig 4.Total Energy Consumption against mobile speed(m/s)

In this paper, we propose a EOLTMRP for MANETs. In this scheme, load balance is used to increase the lifetime of a network. In the route discovery, this scheme not only improves the route stability of multicast routing, but also achieves the load balance of data transmission. Therefore the control overhead for route construction and the number of route reconstructions can be decreased. Simulation results show that the packet delivery ratio and the packet delivery delay of the proposed scheme outperform that of AOMDV. Moreover, the traffic load can be balanced and the network lifetime can be prolonged. EOLTMRP is a energy- aware multicast routing protocol. The node with low energy does not selected as a member of multicast tree. EOLTMRP improves the route stability of multicast routing. The total energy consumption can be decreased and the network lifetime can be prolonged.

6. References

1. Ballaradie, A., Crowcroft, J., Francis, P.: Core based tree (CBT) an architecture for scalable inter-domain multicast routing protocol. Proc. ACM SIGCOM, October 1993, pp. 8589

2. Baolin, S., Layuan, L.: On the reliability of MAODV in ad hoc networks. Proc. IEEE Int. Symp. on Microwave, Antenna,

   Propagation and EMC Technologies for Wireless Communications, August 2005, vol. 2, pp. 15141517

3. Bommaiah, E., Liu, M., McAuley, A., Talpade, R.: AMRoute: ad hoc multicast routing protocol. Internet Draft, August 1998

4. Calvert, K.L., Zegura, E.W., Donahoo, M.J.: Core selection methods for multicast routing. Proc. Fourth Int. Conf. on Computer

   Communications and Networks, September 1995, pp. 638642

5. Das, S.K., Manoj, B.S., Murthy, C.S.R.: A dynamic core based multicast routing protocol for ad hoc wireless network. Proc. Third

   ACM Int. Symp. on Mobile Ad Hoc Networking and Computing,2002, pp. 2435

6. Macker, J.P., Corson, M.S.: Mobile ad hoc networking and the IETF,ACM SIGMOBILE Mob. Comput. Commun. Rev.., 1998, 2, (2),pp. 914

7. Royer, E.M., Perkins, C.E.: Multicast operation of the ad hoc on demand distance vector routing protocol. ACM MOBICOM, 1999,pp. 207218

8. Wang, B., Gupta, S.K.S.: On maximizing lifetime of multicast tree in wireless ad-hoc networks. Proc. Int. Conf. on Parallel Processing, October 2003, pp. 333340 9 Wu, C.W., Tay, Y.C., Toh, C.K.: Ad hoc multicast routing protocol utilizing increasing ID-numbers (amris) functional specification.Internet Draft, November 1998 10 Chiang, C., Gerla, M., Zhang, L.: Forwarding group multicast protocol (FGMP) for multihop, mobile wireless networks, Cluster Comput.,Spec. Issue Mob. Comput., 1998, 1, (2), pp. 187196

1. Devarapalli, V., Sidhu, D.: MZR: A multicast protocol for mobile ad hoc networks. Proc. IEEE Int. Conf. on Communications, June 2001, pp. 886891

2. Garcia-Luna-Aceves, J.J., Madruga, E.L.: The core- assisted mesh protocol, IEEE J. Sel. Areas Commun., 1997, 17, (8), pp. 13801394

3. Gui, C., Mohapatra, P.: Efficient overlay multicast for mobile ad hoc networks. Proc. IEEE Wireless Communication and Networking Conf., 2003, 2, pp. 11181123

4. Lee, S.J., Gerla, M., Chiang, C.C.: On demand multicast routing protocol. Proc. IEEE Wireless Communication and Networking Conf., September 1999, pp. 12981302

5. Sinha, P., Sivakumar, R., Bharghavan, V.: MCEDAR: multicast core extraction distributed ad-hoc routing. Proc. Wireless Communications and Networking Conf., September 1999, pp. 13131317

6. Singh, S., Woo, M., Raghavendra, C.S.: Energy- aware routing in mobile ad hoc networks. Proc. Fourth Annual ACM/IEEE Int.Conf. on Mobile Computing and Networking, October 1998,pp. 181190

7. Toh, C.K., Cobb, H., Scott, D.A.: Performance evaluation of batterylife-aware routing scheme for wireless ad hoc networks. Proc. IEEE Int. Conf. on Communications, 2001, vol. 9, pp. 28242829

8. Wu, Y.-C., Tuan, C.-C.: Energy saving routing protocol with energy sieving in wireless ad hoc networks. Proc. Int. Conf. on Networks Security, Wireless Communications and Trusted Computing, April 2009, vol. 1, pp. 349352

9. Dube, R., Rais, C.D., Wang, K.-Y., Tripathi, S.K.: Signal stability based adaptive routing (SSA) for ad-hoc mobile network, J. IEEE Wirel. Commun., 1997, 4, (1), pp. 3645 20 Rishiwal, V., Kush, A., Verma, S.: Stable and energy efficient routing for mobile ad hoc networks. Proc. Int. Conf. on Information Technology: Next Generations, April 2008, pp. 10281033

1. Wang, S.Y., Liu, J.Y., Huang, C.C., Kao, M.Y., Li,

   Y.H.: Signal strength-based routing protocol for mobile ad hoc networks. Proc.IEEE Int. Conf. on Advanced Information Networking and Applications, March 2005, pp. 1720

2. Lee, S.J., Gerla, M.: Split multipath routing with maximally disjoint paths in ad hoc networks. Proc. IEEE Int. Conf. on Communications,June 2001, pp. 32013205 23 Pearlman, M.R., Haas, Z.J., Sholander, P., Tabrizi, S.S.: On the impact of alternate routing for load balancing in mobile ad hoc networks. Proc.First Annual Workshop on Mobile and Ad Hoc Networking and Computing, August 2000, pp. 310

1. Sheng, M., Li, H., Shi, Y.: Delay sensitive adaptive routing protocol for ad hoc network. Proc. 17th Int. Conf. on Advanced Information Networking and Applications, March 2003, pp. 731736

2. Wei,W., Zakhor, A.: Multiple tree video multicast over wireless ad hoc networks, IEEE Trans. Circuits Syst. Video Technol., 2007, 17, (1),pp. 215

3. Johnson, D.B., Maltz, D.A.: Dynamic source routing in ad hoc wireless networks: Mobile computing, (Kluwer Publishing Company, 1996),pp. 153181

4. Perkins, C.E., Royer, E.: Ad-hoc on-demand distance vector routing.Proc. Second IEEE Workshop on Mobile Computing System and Application, New Orleans, LA, USA, February 1999, pp. 90100

5. Heinzelman, W.R., Chandrakasan, A., Baladrishnan, H.: Energy efficient routing protocols for microsensor

   networks. Proc. 33rd Hawaii Int. Conf. on System Sciences, 2000, vol. 8, pp. 110

6. Rappaport, T.S.: Wireless communications: principles and practice (Prentice-Hall, Upper Saddle River, NJ, 1995)

30.The Network simulator 2-35, http://www.isi.edu/nsnam/ns/index.html