Reactive CDS Based Enhancement of Ad Hoc On-Demand Distance Vector Routing Protocol to Alleviate ‘Broadcast Storm’ Problem

Reactive CDS Based Enhancement of Ad Hoc On-Demand Distance Vector Routing Protocol to Alleviate ‘Broadcast Storm’ Problem

Rebeka Tanij Tania1, Umme Ruman2

1Department of Computer Science & Engineering, 2Department of Mathematics, Atish Dipankar University of Science & Technology, Banani, Dhaka-1213, Bangladesh.

Abstract

A Mobile Ad Hoc Network (MANET) is an autonomous system of functionally equivalent mobile nodes, which must be able to communicate while moving, without any kind of wired infrastructure. To this end, mobile nodes must cooperate to provide the routing service. Routing in mobile environments is challenging due to the constraints existing on the resources and the required ability of the protocol to effectively track topological changes. Reactive routing protocols perform well in such an environment due to their ability to cope quickly against topological changes. The paper focuses on analyzing an Ad hoc On Demand Distance Vector Routing Protocols (AODV), its broadcast storm problem in the route discovery phase which has the very negative impact on the performance of the protocol. The complete AODV implementation has been studied and also implements a simple, efficient idea on AODV to make a reactive connected dominating set (CDS) in the purpose of reducing the aforementioned problem and enhance the performance thereby. The performance analysis is done by using Network Simulator (NS-2).

Key Words: Routing protocol, AODV, CDS and NS-2.

Due to advances in wireless communication technology and portable devices, wireless communication systems have recently become increasingly widespread. However, broadcasting by naive flooding causes severe contention, collision and congestion, which is called the broadcast storm or flooding problem. Many exiting on-demand routing protocols [1] suffer from the serious broadcast storm problem in the route detection phase. Routing based on a connected dominating set is a frequently used approach to solve this problem, where the searching space for a route is reduced to nodes in the set. A set is dominating if all the nodes in the system are either in the set or neighbors of nodes in the set. Extensive computing of CDS performed in advance without real demand makes these protocols inferior to reactive protocols for routing mobile Ad

hoc networks. In the context of the above scenario our intention has propped up to dedicate ourselves in this field. For that purpose a popular reactive protocol AODV has been chosen.

Design Phase Using the Idea of CDS

The AODV protocol can provide a satisfactory packet delivery ratio for long-term end-to-end constant bit rate (CBR) connections. However, it is still questionable to deploy such reactive algorithms in scenarios where many spontaneous communications exist [2]. This random and short-lived network traffic can generate heavy overhead and easily trigger a flooding storm due to the broadcasted route discovery messages [3]. The Connected Dominating Set (CDS) protocol is dedicated to reduce this overhead and to addressing this scalability problem [4].

A number of algorithms have been proposed to achieve a small CDS subset with good approximation quality [3]. These provide useful insights on how to construct and maintain a CDS backbone in mobile ad hoc networks. However, they also share the same unrealistic assumptions that prevent implementation with the existing wireless technologies, IEEE 802.11 in particular. Following the idea of the connected dominating set and their problems, designation of our CDS aims to achieve the problem of proactive nature of the CDS which poses serious hindrance to integrate or implement them in AODV. It is necessary to maintain both the primary features: connectivity and domination. We also expect that the reduction in the number of control packets will, in general, improve the traffic by decreasing congestion which in turn, will increase the delivery ratio.

Algorithm for the Reactive CDS

Two threshold values are determined in this algorithm to construct a reactive set of selective nodes which will do the act of broadcast in the route discovery phase of the on demand protocol. They are termed as traffic threshold and mobility threshold. These thresholds distinguish stable nodes which are included in the reactive CDS from obsolete nodes excluded from CDS.

• The first threshold Tthresh also named as traffic threshold is to compare the recent time interval from forwarding last data packet by the node up to the current time of receiving RREQ packet.

• And another is the distance M (measured approximately) named as mobility threshold is to compare the distance covered by a node after the event of last data packet forwarding.

We have worked in Route request phase and change it with respect to these two thresholds Tthresh and M.

Performance Measuring Metrics

There are two main categories of routing metrics, the first category, performance metrics, describes the outcome of a simulation, another is scenario metrics. These describe the simulation input parameters.

Performance Metrics: These metrics are interesting because they can be used to point out what really happened during the simulation and provide valuable information about the routing protocol. In the following sections some metrics of this type are described.

Packet Delivery Ratio: The packet delivery ratio presents the ratio between the number of packets sent by constant bit rate sources (CBR, application layer) and the number of received packets by the CBR sink at destination.

Packet delivery ratio =

CBR packets received by CBR sink

CBR packets sent by CBR sources

Routing Overhead: The sum of all transmissions of routing packets sent during the simulation. For packets transmitted over multiple hops, each transmission over one hop, counts as one transmission.

Routing overhead = transmission of routing packets

Hop Count: The average path length of data packets measured in hops. This is actually the number of intermediate nodes that act as a router to forward the data packet in the way from source to destination.

Intermediate Hops Average Hop Count =

CBR packets sent

Simulation Model:

Simulation model has the two basic components: the movement model and communication model which comprises the topology. Nodes in simulation move according to a random waypoint model. The movement scenario files are characterized by a pause time. Each node begins the simulation by remaining stationary for different pause time which is 0, 30, 60 and 100 seconds. It

then selects a random destination in the 1500m × 300m space and moves to that destination at a speed distributed uniformly between 0 and some maximum speed [6]. The entire simulation time is 900 seconds. We experimented with two different maximum speeds 10 meter per second and 20 meter per second. For communication model we have chosen traffic sources to be constant bit rate (CBR) sources.

Simulation parameters

Performance Analysis

overhead

The aggregation of overhead graph for original AODV and enhanced AODV are shown in figure 2. Relative overhead measures the number of overhead packets (packets that are used for route establishment and for other route controlling purpose) per second. Our CDS- implemented AODV offers improved performance i.e. lower overhead with the traffic threshold (.05), mobility threshold (1) for each of the speed (10, 20 m/s). This is because broadcast storm of route discovery phase is made limited by the act of the connected dominating set.

Figure 2: Simulation result with varying maximum speed and threshold

Delivery Ratio Graph

Figure 3 shows various plot of delivery ratio of the enhanced AODV for traffic threshold (0.05) and speed 10 m/s. The delivery ratio increased with the increased node velocity and here also the traffic threshold value (0.05) presents the best performance.

Delivery Ratio:conn 17,rate: packets/sec.

1.02

1

0.98

0.96

0.94

0.92

0.9

0

30

60

100

original AODV,speed 10 m/s

traffic threshold 0.05,

speed 10 m/s

mobility threshold 1,speed 10 m/s

pause time

delivery ratio

Figure 3: Simulation result with varying maximum speed and threshold

Combined Graph with the Original AODV

avg. hop count

The combined graph of figure 4 focuses that original AODV simulated with speed 10 m/s needs lower average hops than CDS-implemented AODV with mobility threshold (1). But enhanced AODV with traffic threshold (.05) provides better performance over original AODV in case of speed 20 m/s also.

Figure 4: Simulation result with varying maximum speed and threshold

Tabular Representation

The overhead, the delivery ratio and the average number of hops for different values of the mobility threshold M (1, 2, 25, and 10000) are given in Table 1, Table 2 and Table 3. The packet rate is 4 packets/second and the maximum number of connections 17 with 10 sources and the total number of nodes is 50. We may conclude that the mobility threshold 1 is the best and practically for all scenarios (except for the pause time 0 and the speed 10) all characteristics of AODV are improving.

Table 1: Normalized Overhead

Table 2: Delivery Ratio

Table 3: Hop Count

Conclusion

The AODV routing protocol with the idea of CDS has been presented. The enhanced AODV model has been verified through simulation and establishes that in order to have successful integration it is necessary to use a reactive CDS. We formulate requirements for the reactive CDS and give an enhancement of AODV based on using nodes recently used in data packet routing for the reactive CDS. Though it does not fully eliminate the flooding problem, it limits the effect of the broadcast storm in significant manner. Another drawback of this reactive CDS is that it doesnt assure the connectivity of the source destination pair which is exceeded by the dynamic and reactive nature of the CDS. There is no need to retain or periodically exchange overhead information to maintain the connectivity. Although CDS enhancement was targeted to reduce the routing overhead, the resulted protocol improves the original AODV in all three metrics average decrease in overhead as well as average increase in the delivery ratio.

Reference

1. C. Perkins, E. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, 1999, pp. 90-100.

2. Design and Analysis of a Connected Dominating Set Alorithm for Mobile Ad Hoc Networks by Kan Cai M.Eng., Northeastern University, 2000B.Eng., Northeastern University, 1998

3. On Calculating Connected Dominating Set for Efficient Routing in Ad Hoc Wireless Networks Jie Wu and Hailan Li Department of Computer Science and Engineering Florida Atlantic University Boca F&ton, FL 33431 {jie, hli}@cse.fau.edu.

4. Connected Domination in Multihop Ad Hoc Wireless Networks Mihaela Cardei _ Xiaoyan Cheng _ Xiuzhen Cheng _ Ding-Zhu Du, 2000

5. Metrics in Ad hoc networks, Andree Jaconson, Lulea University,May 19,2000.