ABSTRACT

For last few years, Mobile Ad hoc Networks (MANETs) have attracted a great interest in case of wireless and multimedia technologies. Infrastructure less nature of MANETs makes Quality of Service (QoS) provisioning very challenging and important research aspect. To find a QoS constrained route from source to destination, we should be able to effectively determine the available resources throughout the route. The routing protocol is the most integral part of any type of QoS provisioning. It has to decide which route is able to fulfill the requirement of the desired QoS for specified application. In this paper, modification has been proposed in the existing MANET protocols to get the information about total path bandwidth for delay sensitive applications. It uses modified technique for bandwidth estimation and for route maintenance. The proposed protocol is implemented and simulated using NS-2 simulator. Results of our implementation show that there is much improvement in overheads without any impact on overall end-to-end throughput.

1. Introduction

Mobile ad hoc networks (MANETs) have gained a lot of attention in past few years. MANET [1] is a collection of mobile nodes that can communicate with each other using multi-hop wireless links without utilizing any fixed base station infrastructure and centralized management. MANETs are usually deployed in emergency situations such as rescue operations, public gatherings and areas where setup of infrastructure is not possible. So, in MANETs every node is a workstation as well as router at the same time. Many routing protocols [2-6] have been proposed to provide quality of service provisioning. Broadly these protocols can be classified as: proactive routing protocols and reactive routing protocols. In proactive routing protocols, routing information is periodically exchanged between network nodes. While in reactive protocols, the routing information is obtained only on demand. The basic reactive protocols such as Ad hoc On Demand Distance Vector (AODV) [7] and Dynamic Source Routing (DSR) [8], flooding is used as the basic mechanism to propagate control packets. These control packets generates a large number of redundant packets that consumes network resources inefficiently. Due to this, more contention and overheads are there in the network. The current standard considers the shortest path with minimum hop count as the route selection. Although this hop metric is easy to implement and reliable in dynamic environments. As QoS parameters are not taken into consideration for route selection, so a minimum hop path cannot be QoS constrained path. Determination of link capacity and available bandwidth and path delay is must for the success of real time delay sensitive applications. If route selection criterion is least path delay with minimum required bandwidth instead of simple minimum hop count, then it will be able to maintain the required QoS constraints throughout the session. In IEEE 802.11, each node contends with its neighbor nodes and also the neighbors of its neighbors in the medium contention procedure [9]. Since the range of possible medium contention of a mobile node is wide, medium contention times can affect the end-to-end delay considerably.

This paper proposes a Modified QoS Ad hoc on demand Distance Vector protocol (MQAODV) for provision of minimum end-to-end delay guarantee with required throughput in mobile ad hoc networks. The proposed protocol is developed by modifying AODV [7], in which routing table is used to forward packets, “Hello” messages are used to detect broken route. The protocol modifies and extends AODV [7] to discover a route with least traffic and maintain the minimum required bandwidth. This algorithm selects routes with least traffic and follows alternate route method for route maintenance.

The rest of this paper is organized as follows. Section 2 provides an overview of the related work. In Section 3, we present the details of our proposed delay sensitive bandwidth constrained QoS routing protocol (MQAODV). Section 4 provides simulation environment, simulation results and its analysis obtained under various conditions. Finally, Section 5 concludes the paper with future research directions.

2. Related Work

Previous works on throughput constrained routing for MANETs [2-4] have already considered many of the aspects of the problem of estimating achievable throughput. This includes the need to consider all nodes within carrier sense range (cs-range) of an admitting node. Mutual contention between nodes on a session’s path and all pre-known fixed overheads (IP header, MAC header, 802.11RTS, CTS and ACK frames and interframe spaces) are included in a session’s throughput requirement. Despite their many considerations, the aforementioned work did not consider the capacity wasted due to the 802.11 back-off mechanism or to RTS and data packet collisions. Filali [5] proposed a technique implemented in a sniffing based tool (called wimeter) which captures and analyzes on real-time the frames sent in a preconfigured WLAN. The analysis of captured frames consists on determining the portion of time when the channel is free and then to estimate the available bandwidth in function of the packet size of expected frames to be transmitted and the link-layer rate of the sender and the receiver stations. They went ahead to implement a Call Admission Control Framework that uses the wimeter as a basis for bandwidth estimation. Chen and Heinzelman [4] modified the hello messages in the AODV routing protocol so that it carried bandwidth information of each node and its immediate neighbors. This information was then used to calculate the residual bandwidth due to second hop neighborhood interference. In [6], Liu et al. used average value of history data to calculate the available bandwidth for each period in the past, and use this data to predict the future available bandwidth. Hang et al. [10], implemented a load balancing technique based on a probing available bandwidth measuring technique. Chakers and Belding-Royer [3] et al. proposed an admission control method they called Perceptive Admission Control (PAC). In the method the used a band width estimation method based on listening for the idle time for channel and calculated the available bandwidth as a ratio of idle time to total time multiplied by the channel capacity. A. Abdrabou et al. [11] proposed a MAC layer based estimation method. It is based on the bandwidth of a link in discrete time intervals by averaging the throughputs of the recent packets in the past time window and use it to estimate the bandwidth in the current time window. Obviously, this estimation may not be accurate because the channel condition may have changed. Greedy [12] Perimeter Stateless Routing (GPSR) is used to discover a route to the destination of a new flow. This is a location based protocol which is characterized by their scalability and efficient bandwidth utilization as they do not flood the network to find the destination. Author [13] proposed a new approach based on Multipath Routing Backbone (MRB) for supporting enhanced QoS in MANETS. It improves throughput and minimizes overall end-to-end delay. This protocol is designed for highly dynamic ad hoc networks where link failures and route breaks occur frequently. This protocol finds multiple disjoint paths from source to destination where each path satisfies the conditions for QoS. Many other methods have been proposed varying from numerical calculations to probing methods. Greedy [14] based Backup Routing Protocol considers both route length and link lifetime to achieve high route stability. Primary route for forwarding data packets is formed primarily based on greedy forwarding mechanism, whereas local backup path is established according to link lifetime. Jiazi Li [15] et al. proposed a Multipath Optimized Link State Routing (MP-OLSR) which is a multipath routing protocol. This protocol gives great flexibility by employing different route metrics and cost functions. A modified route recovery and loop detection mechanisms are also implemented in MP-OLSR in order to improve QoS. Mammar Sedrati et al. [16] proposed that the discovery of the route operation for path reconstruction should be done from the source itself. It has also given a new mechanism to determine multiple disjoint path for forwarding the packets from source to destination. Nisha Arora et al. [17] proposed Geographic Location Aware Adaptive Routing (GLAAR). In this node location information is considered as a mean of reducing overall communication overhead for packet forwarding in MANETs. It fetches the node location information using GPS which reduces the computation and communication requirement to select the next node for packet forwarding.

However the most effective method should use less computational power and should not increase overhead in the network. It also has to fit well with the properties of MANETs.

3. Bandwidth Satisfied Delay Sensitive Routing

QoS is an assurance to provide some guaranteed constrained parameters services such as delay, jitter, bandwidth and packet delivery ratio etc. In this paper, we consider only bandwidth constrained routing for delay sensitive applications for supporting real time applications and live video or audio transmission. We propose a QoS constrained routing that provides feedback about the available bandwidth throughout the route considering overall end-to-end delay for transmission.

3.1. Available Bandwidth Estimation

For bandwidth constrained QoS routing, the available end-to-end bandwidth throughout the route must be known from source to destination. The available end-toend available bandwidth can be calculated by minimum residual bandwidth among the intermediate hosts throughout the route. Since the available bandwidth among the links is shared between neighboring hosts, it is difficult for individual host to calculate residual bandwidth as it has no knowledge about other neighboring hosts. Among the several proposed methods to estimate the available bandwidth, the most common is to estimate the network utilization and subtract it from the maximum link capacity. Different methods for estimating network utilization like MAC layer congestion window, queue length and collisions measures provide only little or no information about when a node is actively transmitting or not.

To estimate the available bandwidth, host can listen to the channel to track the network utilization and nearly estimate the available bandwidth per second. For this, 802.11 MAC can be used to determine free and busy times using a physical carrier sense and a virtual carrier sense through network allocation vector (NAV). MAC layer detects that the channel is free when network allocation vector is less than the current time or receive state is idle or send state is idle. It also detects that the channel is busy when network allocation vector sets a new value or receive state changes from idle to any other stage or send stage changes from idle to some other state. The available bandwidth can be calculated as

is the available bandwidth, is maximum possible bandwidth and is bandwidth used in network utilization. Because 802.11 MAC also utilizes some bandwidth in DIFS, SIFS and back off scheme as overheads, these must be taken into consideration in calculation of available bandwidth. These overheads restrict the MAC scheme to fully utilize the available bandwidth for data transmission.

3.2. Node Delay Calculation

For selection of route, the proposed QoS constrained algorithm considers only those paths which satisfies bandwidth requirement with total overall end-to-end delay equal to or less than the specified in the Route Request (RREQ). For calculating overall path delay, proposed algorithm estimates the path delay at each node. To provide QoS guarantee in bandwidth and delay, RREQ and Route Reply (RREP) packet format and routing table is modified to meet the service requirements. Since node traversal time at any node is very small, major part of the delay is contributed by packet queuing and contention delay at the 802.11 MAC. The overall end-toend delay of a path consist of node delay at each node and link delay between nodes. denotes the overall delay including contention and transmission delay. is the delay encountered in Attempt State and is the delay encountered in Backoff State. Neglecting the propagation delay as it is negligible, the forwarding delay [18] which is used to calculate the accumulated delay throughout the route formation can be calculated as.

where

and

here

denotes the probability of source successes in sensing channel idle for time interval “t”. is the probability of the state transition from Packet arrival to Attempt state and “” is the probability of the state transition from Packet arrival to Backoff state. Attempt state and Backoff state are illustrated in Figure 1 which shows the simplified state transition diagram of source that tries to transmit packet.

Initially, the source is in idle state. When any packet arrives at STA i from any neighbor or generated by itself, this node will enter into Packet arrival sate. In this state, source senses medium busy in SIFS period. It recognizes that the channel is busy and will enter into the Backoff state. Otherwise if the channel remains idle for DIFS period, it will enter into attempt state and delay a random backoff time interval before transmitting the packet.

3.3. Proposed Route Discovery

As previously stated, our proposed QoS aware routing protocol utilizes cross layer design. This supports two kinds of QoS constraints. One, when the application indicates in RREQ header about the minimum required bandwidth that must be guaranteed. Other, when the ap-

plication indicates in RREQ header for maximum permissible end-to-end delay. To provide quality of service constrained routing in terms of available bandwidth and overall endto-end delay, extensions are added to RREQ, RREP and Route Error (RERR) messages. Some modifications also have been made in routing table structure of AODV protocol. Any node which receives the RREQ with QoS guarantee must agree to fulfill the service requirement as desired by the application. To initiate the route discovery process, the source host sends a RREQ packet whose header is changed to (bandwidth request, max delay, Accumulated delay, AODV RREQ header). The bandwidth request indicates that RREQ packet will be forwarded only if residual bandwidth on that link is greater than the min bandwidth request. Max delay in the RREQ message is the maximum permissible overall end-to-end delay. Accumulated delay is the time which provides information about the time that has been experienced by nodes along the path from the source node to the node currently processing the RREQ. Before forwarding the RREQ packet, intermediate node must ensure that accumulated delay is less than maximum permissible overall end-to-end delay, otherwise discard the route RREQ will be discarded. The whole procedure is shown in the Figure 2. It illustrates the proposed route discovery method.

When any host gets a new RREQ, it will compare the available bandwidth with the desired bandwidth specified in RREQ header. If available bandwidth is less than desired one, host will discard the RREQ, otherwise it will compare accumulated delay with maximum permissible delay. If accumulated delay is more than maximum permissible delay, host will discard the RREQ. Otherwise, host will forward the RREQ to the next host for route formation. When the destination host receives the RREQ

packet, it will also do the checking procedure. Reason for this checking procedure is that if RREP is sent back through this route, the chosen hosts will bring the mutual interference into the network during transmission. Such type of potential interference cannot be taken into consideration during the route discovery procedure. Therefore final check is essential before sending the RREP to the source host.

Finally the destination host sends a RREP with modified header (min bandwidth, accumulated delay, AODV RREP header) to the source host. Once intermediate host receives the RREP, they enable the route and record the minimum bandwidth and accumulated delay in the routing table which is useful for route maintenance.

3.4. Proposed Route Maintenance

AODV detects a broken route by monitoring the “Hello” messages. If a node does not receive a “Hello” message from a specific neighbor within a predefined interval, it marks the routes using that neighbor host invalid and sends a corresponding error message RERR to the upstream hosts. Only the source host reinitiates the route discovery once receiving the error message. Thus cache memory of the host is not utilized to respond to route break. AODV cannot be implemented in QoS aware routing scheme as bandwidth is not released at the same time whenever there is a route break. It is not possible to calculate the new route without exactly knowing how much bandwidth is consumed by each host in the route. We have used a simple scenario as shown in Figure 3 to illustrate what will happen if we use AODV’s route maintenance scheme without any modification.

The topology is a single chain and is composed of five hosts N1, N2, N3, N4, and N5. Every host is in its neighbor’s transmission range and its second neighbor’s interference range. The source host sends packets with a 1.0 Mb/s feeding rate. The first table shows the host’s first neighbors and the linked tables show the host’s second neighbors. If the link between N3 and N4 is broken, an “Error” message is initiated in N3 and N1 receives it through N2’s propagation. Once N1 gets the error message, it sends a new RREQ. The time interval between claiming a broken route and initiating a route discovery is only several milliseconds. Therefore, the host neighbors’ caches have not yet updated their bandwidth consumption when the new RREQ arrives. In fact, all bandwidth is offered to this single chain transmission and the available end-to-end bandwidth is actually 1.0 Mb/s. This problem is caused by the fact that the neighbor cache was not updated in a timely fashion. Therefore, we should incorporate a forced cache update in the route maintenance scheme. The QoS-aware routing with “Forced Bandwidth Information” uses the first neighbors’ relay to get the second neighbors’ information. Therefore, once the neighbors get the forced updates, they should disseminate the update information immediately to their neighbors. We use “Forced release BW” message to address this concern. This special message’s content is exactly the same as the “Hello” message, except the packet type is marked as “Forced release BW” in order to differentiate with the regular “Hello” message. When a host receives “Forced release BW” message, it sends its regular “Hello” message immediately. The “Error” message is also adopted to trigger an update of bandwidth consumption registers and the dissemination of “Forced release BW” messages. Once a host receives an “Error” message, it will deduct the amount of bandwidth that the broken route consumes from its bandwidth consumption register to reflect the bandwidth allocation changes. The proposed protocol uses “Forced release BW” because the bandwidth should be released instantly among all the neighboring hosts whenever a route break is there.

4. Simulation and Discussions

To test the performance of our QoS-aware routing protocol,

simulations are implemented using ns-2. We use the IEEE 802.11 MAC protocol in RTS/CTS/Data/ ACK mode with a channel data rate of 2 Mb/s. Each host is equipped with a radio transceiver whose transmission range is up to 250 meters over a wireless channel. We used two ray ground model to predict the signal power received by the user. The packet size used in our simulations is 1200 bytes. The topologies vary according to the different simulation purposes. In the simulations, CBR data traffic flows are injected into the network from the servers and size of the data payload is 512 bytes. To test the performance of our proposed protocol, 50 mobile nodes are placed randomly in 1000 m × 1000 m area. Simulation run time is 50 sec. The average simulation results with node velocity 15m/sec are shown.

From Figure 4, we can see that there is much improvement in delivery ratio of packets in MQAODV as compared to conventional AODV.

From Figure 5 we can see that overheads are largely reduced in our proposed protocol than that of AODV.

From Figure 6, we can see that end to end throughput using MQAODV has almost no negative impact despite of the fact that number of overheads is largely reduced.

Simulations results show that normalized overheads

are much less in MQAODV as compared to conventional AODV with the new proposed protocol without much impact on overall end-to-end throughput. As the conventional AODV does not put any constraint on the QoS parameters, so there is no QoS guarantee in this conventional protocol. In our new proposed protocol, the routes less loaded and therefore less packets are dropped due to less congestion. As the results shows clearly that overheads are largely reduced in QMAODV which improves scalability. Delivery ratio is much significantly improved in QMAODV as compared to AODV.

5. Conclusions and Future Work

In this paper, a novel on demand QoS routing protocol (MQAODV) for bandwidth constrained delay sensitive applications in MANETs has been proposed to overcome some shortcomings of AODV protocol. It is an efficient method where networks are not very stable since it can better estimate the residual bandwidth in case of frequent route breaks. Our proposed protocol discovers routes based on bandwidth constrained path delay in addition to hop count instead of hop count only. Route maintenance is more efficient than the existing standards as consumed bandwidth is updated immediately. These characteristics make the protocol more suitable for real time data and voice transmission applications in MANETs under 802.11. Our proposed protocol provides more accurate bandwidth estimation and overall end-to-end delay. It has a provision to avoid more congested path. Earlier paper for delay estimation considered only processing delay at each node along the path. This approach provides more accurate estimation of bandwidth and end-to-end delay throughout the path. In our proposed protocol, we have not considered any predictive way to foresee a route break, which degrades the performance in mobile topologies. Therefore, some methods such as preemptive maintenance routing and route maintenance based on signal strength might help to reduce the transient time when the required QoS is not guaranteed due to a route break or network partition, so that the routing protocol can react much better to mobile topologies.

In this paper, only bandwidth and end-to-end delay are considered for QoS routing. It can be extended to some other resource reservation scheme also.

REFERENCES

Abbreviations

DIFS—Distributed Co-ordination Function Inter Frame Space SIFS—Short Inter Frame Space WLAN—Wireless Local Area Network ACK—Acknowledgement MAC—Media Access Control EA—Attempt State EB—Back off State