Extending the AODV Protocol to Provide Quality of Service in Mobile Ad hoc Networks Nadir Bouchama CERIST Research Center, 03 Rue des fr?©res Aissou, Ben Aknoun, Algiers 16306, Algeria University of Be]aia. Rue de Targa Ouzemmour 06000. Algeria [email protected] dz, Nadia Nouali [email protected] dz DJamil Aissani LAMOS Laboratory, University of Be]aia. Rue de Targa Ouzemmour 06000. Algeria Natalia DJellab Department of Mathematics, University of Annaba 23000, Algeria Houari Maouchi University of Tizi Ouzou. Algeria houari. [email protected] com Abstract Voice communication is the most needed application in disaster management. However, without good QoS tuning, its performance can be poor. QoS routing is one of the most important building blocks in any given QoS solution. To conceive a QoS routing protocol for ad hoc networks, we can either conceive a new protocol from scratch, or extend an existing best effort protocol like AODV (Ad-hoc OnDemand Distance Vector Routing Protocol). The main advantage for the second approach is its easiness.
In this paper, we propose a new QoS routing protocol that can satisfy multimedia application requirements in ad hoc networks. Thereafter, we present and discuss simulation results obtained under the NS-2 simulator or a VoIP application. 1. Introduction A mobile ad hoc network (or MANET) is an operate in isolation, or may have gateways to and interface with a fixed network. In the latter operational mode, it is typically envisioned to operate as a “stub” network connecting to a fixed internetwork .
Thanks to their “anytime, anywhere” property, mobile ad hoc networks have the potential to serve as a main building block for pervasive computing. Thus, they attracted a great enthusiasm for military, industrial, and academic communities. Indeed, applications built upon mobile ad hoc networks cover a wide spectrum going from home nd educational networking to tactical networking (military communications, automated battlefields, etc. ) , . For example, in disaster or emergency situation, a wireless ad hoc network can easily be deployed for rapid communications and information sharing.
This can drastically help to save the lives of the victims and/or minimize losses . The flip side of the coin is that, before a widespread deployment, many challenges should be efficiently overcome. Routing, scalability, security, mobility management, energy conservation, and Quality of Service (QoS) are some relevant examples . The organization of the paper is as follows: The next section revisits quality of service solutions in ad hoc networks. In section 3, we review QoS routing principles. Section 4 revisits routing mechanisms in the AODV protocol.
In section 5, we propose AODV-D (AODV with Delay constraints), a new routing protocol inspired from the DEAN protocol. In section 6, we evaluate the performances of our protocol. Finally, in Section 7, we conclude the paper. ICIST’2011 International Conference, 24-26 May 2011. University of Tebessa, Algeria 2. Quality of Service in mobile ad hoc networks “Quality of Service” (QoS) is a fuzzy ord and its definition tightly depends on the context in which it is used. The literature yields a great deal of definitions for this term as well as debates about the accuracy of their meanings.
However, two definitions (International Telecommunication Union), defines Quality of Service as “a collective effect of service performance which determines the degree of satisfaction of a user of the service” . On the other hand, quality of service is defined, by the IETF (Internet Engineering Task Force), as “a set of service requirements to be met by the network while transporting a flow from a source to a destination” . According to some authors like [1 5], the last definition does not fit perfectly into mobile ad hoc networks.
For the authors, providing QoS in a MANET is concerned with the optimization of resource consumption rather than satisfying the needs of the applications. So, quality of service is adapting application to the dynamics of the network. With the beginning of wireless networking, the main preoccupation was network connectivity, i. e. finding a path from a source to a destination, without any consideration for optimizing the utilization of network resources or for satisfying application requirements 3]. For this purpose, many routing protocols have been proposed.
The IETF adopted a set of routing protocols such OnDemand Distance Vector Routing) , OLSR (Optimized Link State Routing) , DSR (Dynamic Source Routing) [1 1], TBRPF (Topology Broadcast based on Reverse-Path Forwarding) . With the popularity of multimedia applications such as Voice over IP (VoIP), Audio on Demand (AoD), Video on Demand (VOD) and videoconferencing, on the one hand, and the failure of the legacy best effort service to provide satisfactory services in MANETS on the other hand, Quality of Service support in MANETS ecomes a necessity rather than an “additional feature” .
According to the extensive literature search that we did, QoS solutions for MANETS can be classified according to several criteria. However, the well known taxonomy is given in . The authors divide the solutions into four categories, namely: QoS routing, and signalling protocols. In this paper, we are concerned with the first class of solutions, i. e. QoS routing protocols. 3. QoS routing in mobile ad hoc networks The concept of QoS routing was born in the late 1980 with the advent of the ATM (Asynchronous Transfer Mode) .
The objectives of QoS routing re threefold : (i) Find (if possible) a feasible path between a source-destination pair such as QoS requirements are met; Optimize resource utilization of the network; and finally (iii) Adapt to network congestion providing graceful performance degradation to lower-priority traffic. QoS routing is well studied in Internet in its two aspects: QoS routing algorithms (static), and distributed QoS routing (dynamics) .
Surveys of QoS routing protocols in ad hoc networks are provided in  and . In [1 3], the authors discuss QoS routing challenges in wired networks and wireless ad hoc networks (sensor networks, mobile ad hoc etworks, and mesh networks). It is desirable for QoS routing protocol for MANETS to satisfy the maximum of the following properties: ??? Adaptivity: the protocol has to take in account the characteristics of MANETS such as mobility, scarcity of resources, and versatile medium.
It should react efficiently according to variation of those parameters, and adapt itself to the “state” of the network , [1 5]; ??? Combinatorial stability: QoS routing can only be successfully achieved if the network is combinatory stable. This means QoS and routing information updates are faster than node motion. Consequently, the choice of the requency of QoS information updates is of paramount importance ; ??? Efficiency: the QoS routing protocol should optimize the overall resource utilization of the network while satisfying the application requirements ; possible.
The simpler is the protocol, the easier is the implementation, and the lower is the resource consumption; ??? Scalability: Scalability (a. k. a the “S” word problem) is big deal for packet-switched networks. It can be broadly defined as the ability of the network to provide an acceptable service level even with the increase of its limiting parameters. The number of nodes, the density of the network, he number of flows, the mobility rate and the traffic density are examples of limiting parameters ; 2 Security: security requirements depend on the use-scenario of the ad hoc network.
For example, in a battlefield scenario, it can be crucial to detect and avoid intrusions in the network. To conceive a new QoS routing protocol, we can either conceive a protocol from scratch, or extend existing best effort protocols (QoS-unaware protocols) to make them QoS-aware. We argue that the second approach is more suitable for two main reasons: (1) easiness, and (2) interoperability with existing best effort protocols. In this work, we have chosen AODV as the best effort routing protocol to be extended.
Before presenting our QoS extensions of this protocol, we revisit, in the next section, the routing mechanism used in AODV. 4. Overview of the AODV routing protocol AODV (Ad Hoc On-Demand Distance Vector)  is a reactive routing protocol that discovers route on an on-demand basis: When a given node S needs a route to some destination D, it broadcasts a ROUTE REQUEST (RREQ) to its neighbours, including the last known Sequence help to avoid the counting-to-infinity problem of other distance-vector protocols. The RREQ message is looded through the network until it reaches a node that has a route to the destination.
Each node that forwards the RREQ message creates a reverse route for itself back to node S . in forwarding this REPLY back toward node S creates a forward route to D (Fig. 2). Figure 2. Route REPLY AODV The main advantages of AODV are its simplicity, and its adaptivity to highly dynamic networks. Consequently, it can be easily extended to provide QoS for multimedia applications in the context of disaster and/or emergency management. 5. our proposal: AODV-D In this section, we present our protocol, namely, AODV-D (AODV with Delay constraints).
It consists of an extension for the AODV protocol in order to support delay-aware applications in ad hoc networks. Figure 1 . Route Discovery in AODV Once the RREQ reaches a node with a route to D, that node generates a ROUTE REPLY (RREP) that contains the number of hops necessary to reach D and the sequence number for D most recently seen by the node generating the RREP. Each node that participates Figure 3. A synoptic view of the AODV-D protocol 3 The main building blocks added to the original protocol are depicted in Fig. 3. They are as follows: 2. . added in the application layer to allow pplication to notify quantitatively their QoS requirements in terms of end to end delay and bandwidth. For example, to have an acceptable quality of voice, the ITU (International Telecommunication Union) considers that the one-way network delay should not exceed 150 ms. Thus, we added, in the RREQ paquet of AODV, a new field to specify this QoS requirement for VoIP applications. Resource estimation: A resource is anything that is required in order to perform a task and which is consumed during performance .
Estimating available resources (battery life, queue length, processing delay and bandwidth) is a crucial step in mobile ad hoc etworks . The more accurate is the information; the better is the decision of accepting or rejecting a new flow. Besides, resource estimation helps in performing QoS adaptation. Bandwidth and delay are the two most used metrics in QoS routing. Bandwidth can be seen as the width of the path from the source to the destination and delay its length. Due to the dynamics of ad hoc networks, obtaining accurate measure for this two metrics is a very challenging task.
Usually, The one hop delay in 802. 11 networks is estimated using queuing theory such as M/MMGI/I/K [1 5], M/G/I , M/M/I/K  and G/G/I . The two key challenges in estimating delay and/or bandwidth are: How to estimate them? And how frequently to estimate them. A trade-off is generally made between estimation exactitude and generated overhead. In this paper, bandwidth and delay are estimated using the same approach used in the DEAN (Delay Estimation in Ad hoc Networks) protocol . This approach estimates the one-hop delay using the M/M/11K queuing model.
Admission control: this building block is concerned with accepting/re]ecting new RREQ, and the HELLO packets of our protocol to make admission control are slightly different from those of the DEAN rotocol. 6. Performance evaluation In order to evaluate the performances of our protocol, we implemented AODV-D under the NS-2 simulator (version 2. 33). For this purpose, we exploited the AODV and 802. 11 source code provided in the simulator. We evaluated our protocol by comparing it to AODV. We chose VoIP as the basic application. Three QoS metrics are required for VoIP are: end to end delay; Jitter, and packet loss rate .
Figure 4. Topology used in simulation 6. 1 . Simulation scenario We used a static topology as shown in Fig. 4. It consists of 16 wireless nodes. We initiated four CBR flows as shown in Table. 1. The next simulation results are given for the CBRI flow. CBRI connection has an end to end QoS requirement of 150 ms. We evaluate the VoIP quality for this connection; using AODV and D-AODV, according to three metrics given above. Figure 5. Routes chosen by AODV and AODV-D 4 In Fig. 5, we can notice when AODV is used, the shortest path is chosen, even if it is congested.
However, when AODV-D is used, the chosen route has to expect the above condition (end to end delay < 150 ms). Thus, the chosen route is different from AODVS one. Table. l : Simulation parameters for the flows. CBRI CBR2 CBR3 CBR4 (kb/S) 380 620 Starts second) at 15 5 10 20 Ends at 35 25 This is Justified by the fact that the only difference is the number of hops of the paths chosen by both protocols. 6. 2. 2. Results for Jitter (delay variation) For AODV-D protocol, the choice of route is subject to the delay constraint which must not exceed 150 ms.
The route chosen respects delay constraints. Therefore, obtained Jitter does not exceed 50 ms in most of the time (Fig. 7). This is acceptable for an average quality of VoIP. 6. 2. Results and discussions 6. 2. 1. Results for end to end delay that the delays of the standard AODV protocol are much higher compared to AODV-D. This is because the latter has required a period of 150 ms maximum to accept the route, and then has chosen the path through the nodes 7-0-1-2-3-4-5-8 with more hops but with less congestion (only CBR4 flow is active).
However, a slight excess of 150 ms was produced after the validation of the route by the routing protocol. Figure 7. Jitter results for AODV-D 6. 2. 3. Figure 6. End to end delay: AODVvs. AODV-D However, the AODV protocol chose the route that passes through the nodes 10-11-12-13-14-1 5 according to the conventional criterion: the shortest path. This route is congested (CBR2 and CBR3 flows are active). This caused high delays (up to 700 ms). After the 25th second, CBR3 flow is stopped; we note that the delays for the standard AODV are close to those of AODV-D.
Results for Packet loss rate The results presented in the Table. 2 show that the simple scenario and simulation parameters used do not cause significant loss rates in most cases. But there are differences between the two protocols. When the standard AODV protocol is enabled, CBRI and CBR2 flows have suffered loss rates of 3. 5% and 3. 68% respectively. This is Justified by the choice of route 10-11-12-13-141 5 which is already congested y the two flows CBR2 and CBR3. Thus, adding the CBRI flow to this route caused packet losses.
However, when the protocol AODV-D is used, the route selection criterion with the delay constraint allowed choosing the route 7-0-1-2-34-5-8. This route is more stable because only the flow CBR4 is active. In general, for VoIP metrics, our protocol shows more interesting performances. However, we expect that AODV will show better performances in terms of route search delays. This is due to the fact that, contrarily to AODV, AODV-D performs admission control at every node to verify QoS satisfaction.