Aomdv And Egmp Routing Protocols Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

A mobile ad-hoc network or MANET is a collection of mobile nodes sharing a wireless channel without any centralized control or established communication backbone. They have no fixed routers with all nodes capable of movement and arbitrarily dynamic. These nodes can act as both end systems and routers at the same time. When acting as routers, they discover and maintain routes to other nodes in the network. Many applications like the exchange of messages among a group of soldiers in a battlefield, communications among the firemen in a disaster area, and the support of multimedia games and teleconferences. With a one-to-many or many-to-many transmission pattern, multicast is an efficient method to realize group communications. In on-demand or reactive routing protocols, the routes are created on requirement basis. To find a path from source to destination, it invokes the route discovery

mechanisms. Only the routes that are currently in use are maintained a. Reactive routing protocols have some inherent limitations. First, since routes are only maintained while in use, it is usually required to perform a route discovery before packets can be exchanged between communication peers. This leads to a delay for the first packet to be transmitted. Second, even though route maintenance for reactive algorithms is restricted to the routes currently in use, it may still generate an important amount of network traffic when the topology of the network changes frequently. Finally, packets to the destination are likely to be lost if the route to the destination changes [1]. To reduce the topology maintenance over-head in multicasting, an option is to make use of the position information. But there are many challenges to implement an efficient and scalable geographic multicast scheme in MANET. For example, in unicast geographic routing, destination's position is carried in the packet header to guide packet forwarding. But in multicast routing, the destination is a group of members. Putting all the members' addresses and positions into the packet header is a direct and easy way, but this is only applicable for the small group case [2] [3] [4]. Besides scalable packet forwarding, a scalable geographic multicast protocol also needs to efficiently manage the membership of a possible large group, obtain the members' positions and forward packets to the members distributed in a possible large network terrain. These are ignored in the above protocols. We propose an efficient geographic multicast protocol (EGMP). EGMP can scale to large group size and network size and can efficiently implement multicasting delivery and group membership management. EGMP uses a hierarchical structure to achieve scalability.

Protocol Overview

2.1 Ad-hoc On-demand Multipath Distance Vector Routing (AOMDV)

Ad-hoc On-demand Multipath Distance Vector Routing (AOMDV) [5]protocol is an extension to the AODV protocol for computing multiple loop-free and link disjoint paths. The routing entries for each destination contain a list of the next-hops along with the corresponding hop counts. All the next hops have the same sequence number. This helps in keeping track of a route. For each destination, a node maintains the advertised hop count, which is defined as the maximum hop count for all the paths, which is used for sending route advertisements of the destination. Each duplicate route advertisement received by a node defines an alternate path to the destination. Loop freedom is assured for a node by accepting alternate paths to destination if it has a less hop count than the advertised hop count for that destination. Because the maximum hop count is used, the advertised hop count therefore does not change for the same sequence number [1]. When a route advertisement is received for a destination with a greater sequence number, the next-hop list and the advertised hop count are reinitialized.

AOMDV can be used to find node-disjoint or link-disjoint routes. To find node-disjoint routes, each node does not immediately reject duplicate RREQs. Each RREQs arriving via a different neighbour of the source defines a node-disjoint path. Here AOMDV is used for video transmission in multipath multicast.

It is possible to accommodate the video flow by multiple networks simultaneously. A video streaming flow can be split into multiple sub streams and delivered through multicast schemes simultaneously. The video is multipath multicast using AOMDV as shown in fig.1











N9 R3


Figure.1 AOMDV in Multipath Multicast Transmission

The AOMDV routing takes place from the source S to the multiple destinations R1, R2 and R3 in multiple path one path. The AOMDV algorithm works as follows:

2.1.1 AOMDV Algorithm

STEP1: S is the source node selected and R1, R2 and R3 are the receivers.

STEP2: Multiple paths are selected using Dijikstras algorithm.

STEP3: Source node broadcasts the route request in multipath to the destination receivers R1, R2, R3 through the intermediate nodes.

STEP4: RREQ reaches all the intermediate nodes. If the node recognizes a reliable path requested destination, it replies to the source node with a RREP message.

STEP5: If that particular node is not the destination, then it checks whether there is any valid path available for the destination. If it exists, it forwards the RREQ message to that node.

STEP6: After forwarding RREQ to the destination, the node appends its own address to a list of traversed hops and broadcasts the updated RREQ.

STEP7: Thus after getting the RREP message from that node, the specified path is available for the transmission. If the source node receives the RERR message, that path won't be used for the data transmission

STEP8:In Multipath data transmission, QoS parameters for each path is calculated and the path which has got the highest QoS will be used for transmission.

STEP9: Redundant paths are identified and suitable path is randomly selected.

2.2 Efficient Geographic Multicast Protocol

EGMP supports scalable and reliable membership management and multicast forwarding through a two-tier virtual-zone-based structure. At the lower layer, in reference to a predetermined virtual origin, the nodes in the network self-organize themselves into a set of zones as shown in Fig. 2, and a leader is elected in a zone to manage the local group membership.

Figure 2. Zone structure and multicast session example.

At the upper layer, the leader serves as a representative for its zone to join or leave a multicast group as required. As a result, a network wide zone-based multi-cast tree is built. Each zone is given a zone id. For efficient and reliable management and transmissions, location information will be integrated with the design and used to guide the zone construction, group membership management, multicast tree construction and maintenance, and packet forwarding. The zone-based tree is shared for all the multicast sources of a group[12]. To further reduce the forwarding overhead and delay, EGMP supports bi-directional packet forwarding along the tree structure. That is, instead of sending the packets to the root of the tree first, a source forwards the multicast packets directly along the tree. At the upper layer, the multicast packets will flow along the multicast tree both upstream to the root zone and downstream to the leaf zones of the tree. At the lower layer, when an on-tree zone leader receives the packets, it will send them to the group members in its local zone [12][11].

2.2.1 Notations and Definitions

pos: A mobile node's position coordinates (x, y).

zone: The network terrain is divided into square zone as shown in Fig. 3.

Fig. 3. Zone depth in the multicast session.

rzone: Zone size. The length of a side of the zone square. In our zone structure, the intra zone nodes can communicate directly with each other without the need of any intermediate relays, so that zone size ≤ √r2 ,where r is the mobile nodes' transmission range.

zone ID: The identification of a zone. A node can calculate its zone ID (a, b) from its pos (x, y) as: a = [ r−x0 ] and b = [ r−y0], where (x0, y0) is the position zone zone of the virtual origin, which is set at the network initial stage as one of the network parameters. For simplicity, we assume all the zone IDs are positive.

zone center: For a zone with ID (a,b), the position of its center (xcenter , ycenter ) can be calculated as: xcenter = x0 +(a+0.5)-rzone, ycenter = y0 +(b+0.5)- rzone. A packet destined to a zone will be forwarded towards the center of the zone.

zLD: Zone leader. A zLD is elected in each zone for managing the local zone group membership and taking part in the upper tier multicast routing.

tZone: The zones on the multicast tree. The tZones are responsible for the multicast packet forwarding. A tZone may have group members or not.

Core zone: The core zone is the root of the multicast tree.

zone depth: For each multicast session, a zone's depth reflects its distance to core zone. For a zone with ID(a, b), its depth is depth = max(|a0 −a|, |b0 −b|), where (a0, b0) is core-zone ID. For example, in Fig. 3, for the five zones surrounding the core zone, depth = 1. And the outer six zones have depth as two. The depth of core

zone is zero.

zNode: Zone node, a node located in the same zone as the node being mentioned.

2.2.2 Moving between Different Zones

When a member node moves to a new zone, it must rejoin the multicast tree through the new leader. When a leader is moving away from its current zone, it must handover its multicast table to the new leader in the zone, so that all the downstream zones and nodes will remain connected to the multicast tree. Whenever a node M moves into a new zone, it will rejoin a multicast group G by sending a JOIN_REQ message to its new leader. During this joining process, to reduce the packet loss, whenever the node broadcasts a BEACON message to update its information to the nodes in the new zone, it also unicast a copy of the message to the leader of its previous zone to update its position. Since it has not sent the LEAVE message to the old leader, the old leader will forward the multicast packets to M. This forwarding process helps reduce the packet loss and facilitates seamless packet transmissions during zone crossing. When the rejoining process finishes, M will send a LEAVE message to its old leader.

To handle leader mobility problem, if a leader finds its distance to the zone border is less than a threshold or it is already in a new zone, it assumes it is moving away from the zone where it was the leader, and it starts the handover process. To look for the new leader, it compares the positions of the nodes in the zone it is leaving from and selects the one closest to the zone center as the new leader. It then sends its multicast table to the new leader, which will announce its leadership role immediately through a BEACON message. It will also send a JOIN_REQ message to its upstream zone. During the transition, the old leader may still receive multicast packets. It will forward all these packets to the new leader when the handover process is completed. If there is no other node in the zone and the zone will become empty, it will use the method introduced in the next section to deliver its multicast table. In the case that the leader dies suddenly before handing over its multicast table, the down-stream zones and nodes will reconnect to the multicast tree through the maintenance process.

If the to be empty zone is the root zone, since the root zone has no upstream zone, the leader will check its neighbouring zones and choose the one closest to the root zone as the new root zone. The leader then forwards its multicast table to the new root zone, and floods a NEW_ROOT message to announce the change.

EGMP handles the zone partitioning problem as follows: If there are multiple clusters in a zone, because these clusters are not aware of the existence of each other, each cluster will elect a leader. When an upstream zone leader receives JOIN_REQ messages from multiple leaders of the same zone and the new message is not sent as a result of leader handover (in which case the old leader's address needs to be carried), it detects that the downstream zone has partitioned into multiple clusters. It identifies a cluster by its zone id and the leader's address. When sending a packet to the cluster, it uses the leader's position instead of the zone center (in which case the zone ID is carried as the destination) as the transmission reference. Even though the leader may move, its position carried in JOIN_REQ message can still be used as a reference to forward packets to its cluster. When receiving a packet with the position of the leader as the reference, a cluster leader can learn that multiple clusters exist within its zone. In case that not all the clusters of a partitioned zone send JOIN_REQ messages, the upstream zone leader may not be aware of the partitioning of the downstream zone. When a cluster leader receives a packet destined to its zone but does not match its status, it will send an update message to its upstream zone. For example, when a cluster leader receives a JOIN_REPLY message or a multicast packet but did not send JOIN_REQ message, it will send a LEAVE message to the upstream zone. When receiving messages from multiple leaders of the same zone, the upstream leader can detect zone partitioning. It will resend the previous message to the target cluster with the position of the zone leader as the destination.

In this paper this Efficient Geographic Multicast Protocol (EGMP) uses a hierarchical structure to implement scalable and efficient group membership management. Video is multipath multicast using this system as follows.

2.2.3 EGMP Algorithm

STEP 1: Source node initiates the whole network by sending the message NEW_SESSION.

STEP 2: The network is divided into different zones.

STEP 3: If the source node is not a leader node it sends a JOIN_REQ message to its zone leader, carrying its address, position and group to join.

STEP 4: After the node has joined the zone it sends the multicast packets to its zone leader in multipath.

STEP 5: Multipaths are selected using the shortest path algorithm

STEP 6: After selecting the shortest path the zone leader forwards the packet to the respective destination zone leader.

STEP 7: The zone leader may receive duplicate multicast packets from different upstream zones. Therefore, when the two upstream zones have the same distances to the root zone one of them is randomly selected.

STEP 8: Zone leader sends the packet to the destination node. The destination node ends the session by sending the END_SESSION message.

Video Streaming Traffic

A video streaming flow can be split into multiple sub-streams and delivered through different network simultaneously. Based on video transmitted, each video traffic burst is generated over fixed intervals and consist of an I or P frame and number of B frame.

To remove temporal redundancy, intra-coded (I) frame are interleaved with predicted (P) frames and bi-directionally code (B) frames. I frames are compressed versions of raw frames independent of other frames, whereas P frames only refer preceding I/P frames and B frames can refer both preceding and succeeding frames. A sequence of video frames from I frame to next I frame comprises group of picture (GoP). Because P and B frames are encoded with reference to preceding and/or succeeding I/P frames, traffic transmission follows the batch arrival .

Performance Evaluation

Our evaluations are based on the simulation of 100 wireless mobile nodes forming an ad hoc network, moving about over a square (1000m x 1000m) flat space for simulated time. A square space is chosen to allow free movement of nodes with equal density. We choose the traffic sources to be constant bit rate (CBR) source. The source and destination pairs were spread randomly over the network. In the simulation, node movement is due to random waypoint model.

3.1 Performance Evaluation Metrics

We compare the performance of AOMDV and EGMP according to the following performance metrics: Throughput, Packet delivery ratio.

3.2 Simulation Results

We have run the simulation environments and evaluated throughput and packet delivery ratio for AOMDV and EGMP. The results are summarized below with their corresponding graphs.

3.2.1. Packet delivery ratio: The ratio of the number of packets received and the number of packets.

Figure.4 Comparison of AOMDV and EGMP on basis of packet delivery ratio

From this Figure.4 EGMP achieves 2% higher packet delivery ratio than AOMDV, hence reliability is better than AOMDV.

3.2.2 Throughput: Maximum rate of data that an network can accept. EGMP reduce the packet drop up to 30%, whereas AOMDV is about 40%.

Figure.5 Comparison of OMDV and EGMP on basis of Throughput

From the Figure.5 EGMP achieves 20% higher throughput than AOMDV.


In this paper it is seen that EGMP outperforms AOMDV due its ability to search for alternate routes more faster when a current link breaks down. AOMDV incurs more routing overheads while flooding the network and packet delays due its alternate route discovery mechanism. It is found that if routing overhead and end to end delay is concerned, then EGMP is preferred over AOMDV for multipath multicast transmission. Comparison was based on the parameter throughput, Packet delivery ratio. We conclude that EGMP is better than AOMDV by achieving throughput 20% higher.