29-06-2010, 12:54 PM
[attachment=3897]
A SURVEY OF QoS ROUTING PROTOCOLS FOR MOBILE AD HOC
NETWORKS
Presented By:
Mrs. Santhi.G
Senior Lecturer Department of Information Technology Pondicherry Engineering College Puducherry -605014.
Dhanalakshmi.A
Department of Information
Technology Pondicherry Engineering College, Puducherry- 605014.
Gayathri.J
Department of Information
Technology Pondicherry Engineering College, Puducherry- 605014.
Abstract
Real time services like audio/ videoconferencing, webcasting requires the network to provide the guarantee of the service being provided to the receiver. The provision of QoS guarantees is much more challenging in Mobile Ad hoc Networks. Many researches have been done so as to provide QoS assurances by designing various MANET protocols. A number of new QoS routing protocols of different styles have been proposed for ad hoc networks. However, systematic performance evaluations and comparative analysis of these protocols in a common realistic environment have been performed only in a limited manner. The relative strengths, weaknesses, and applicability of each multicast protocol are studied and discussed. Keywords: QoS, Adhoc, Protocol, Routing
I. Introduction
A Mobile Ad hoc Network (MANET) is
composed of mobile nodes. In MANETs, there is no fixed infrastructure such as base stations. MANETs are self-configuring; there is no central management system with configuration responsibilities. All the mobile nodes can communicate each other directly, if they are in other's wireless links radio range. In order to enable data transfer they either communicate through single hop or through multiple hops with the help of intermediate nodes. Since mobile ad-hoc networks (MANETs) allow the construction of flexible and adaptive networks with no fixed infrastructure they can be widely used in military battlefields, crisis management services, classrooms, etc.
Wireless networks allow ubiquitous service access, anywhere, anytime. These networking developments lead to development of excess applications (such as those involving audio and video) many of which have stringent Quality of Service (QoS) requirements that must be satisfied. However, there still remains a significant challenge to provide QoS solutions and maintain end-to-end QoS with user mobility.
QoS routing usually involves two tasks: collecting and maintaining up-to-date state information about the network and finding feasible paths for a connection based on its QoS requirements. It relies on state parameters specifying resource availability at network nodes or links, and uses them to find paths with enough free resources. To support QoS, the routing protocol should support metrics such as delay, bandwidth, energy, delay jitter and packet loss ratio etc. Addressing QoS support in the Internet has been widely investigated by various protocols.
Following this, we summarize the operation, key features and major advantages and drawbacks of a selection of QoS routing protocols proposed in the literature. We focus on journal articles and peer-reviewed conferences, thereby hopefully extracting the most useful and important subset of the candidate solutions.
II. Issues need to be considered while providing QoS
QoS provision will lead to an increase in computational and communicational cost. In other words, it requires more time to setup a connection and maintains more state information per connection. The improvement in network utilization counterbalances the increase in state information and the associated complexity and various issues are needed to be faced while providing QoS for MANETS. The major problems that are faced are as follows:
Unreliable channel: The bit errors are the main problem which arises because of the unreliable wireless channels. These channels cause high bit error rate and this is due to high interference, thermal noise, multipath fading effects, and so on. This leads to low packet delivery ratio. Since the medium is wireless in the case of MANETs, it may also lead to leakage of information into the surroundings.
Maintenance of route: The dynamic nature of the network topology and changing behavior of the communication medium makes the maintenance of network state information very difficult. The established routing paths may be broken even during the process of data transfer. Thus arises the need for maintenance and reconstruction of routing paths with minimal overhead and delay. The QoS aware routing would require the reservation of resources at the intermediate nodes. The reservation maintenance with the changes in topology becomes cumbersome.
exposures. The physical medium of communication is inherently insecure. So we need to design security-aware routing algorithms for ad hoc networks.
III.Protocol classification
QoS routing protocols are classified widely based on their:
1) Network topology (hierarchical or location-
aware),
2) Approach to route discovery with QoS
(proactive, reactive, hybrid, or predictive).
Mobility of the node: Since the nodes considered here are mobile nodes, that is they move independently and randomly at any direction and speed, the topology information has to be updated frequently and accordingly so as to provide routing to reach the final destination which result in again less packet delivery ratio.
Limited power supply: The mobile nodes are generally constrained by limited power supply compared to nodes in the wired networks. Providing QoS consumes more power due to overhead from the mobile nodes which may drain the node's power quickly.
Lack of centralized control: The members of any ad hoc networks can join or leave the network dynamically and the network is set up spontaneously. So there may not be any provision of centralized control on the nodes which leads to increased algorithm's overhead and complexity, as QoS state information must be disseminated efficiently.
Channel contention: Nodes in a MANET must communicate with each other on a common channel so as to provide the network topology. However, this introduces the problems of interference and channel contention. For peer-to-peer data communications these can be avoided in various ways. One way is to attempt global clock synchronization and use a TDMA-based system where each node may transmit at a predefined time. This is difficult to achieve since there is no centralized control on the nodes. Other ways are to use a different frequency band or spreading code (as in CDMA) for each transmitter. This requires a distributed channel selection mechanism as well as the dissemination of channel information.
Security: Security can be considered as a QoS attribute. Without adequate security, unauthorized accesses and usages may violate the QoS negotiations. The nature of broadcasts in wireless networks potentially results in more security
1) Network Topology Based Protocols
There are several protocols which can be classified based on the topology the network has adopted. Those protocols can be named as the network topology based protocols.
a. A Core-Extraction Distributed Ad hoc Routing algorithm (CEDAR)
It is a topology based hierarchical routing algorithm having three key components:
(a) the establishment and maintenance of a self-organizing routing infrastructure called the core for performing route computations,
(b) the propagation of the link-state of high-bandwidth and stable links in the core through increase/decrease waves, and
© a QoS route computation algorithm that is executed at the core nodes using only locally available state. Bandwidth is the main constraint included here.
Advantages
It is a robust and adaptive QoS routing algorithm that reacts quickly and effectively to the dynamics of the network while still approximating link-state performance for stable networks.
Limitations
1. Range of transmission is less
2. Only small to medium sized networks are used
b. Predictive Location-Based QoS Routing in Mobile Ad Hoc Networks (PLBQR)
It is a location aware QoS routing protocol in which a location-delay prediction scheme, based on a location-resource update protocol has been performed. The location updates contain resource information pertaining to the node sending the update. This resource information for all nodes in the network and the location prediction mechanism are together used in the QoS routing decisions.
There are dynamic changes in topology and resource availability due to the high degree of mobility of nodes in the ad hoc network. Due to these changes, the topological and routing information used by current network protocols is rendered obsolete very quickly. Advantages
Prediction of new location based on previous location is made when there is variation in the geographical location. QoS routing based on the resource availability at the intermediate nodes in the source to destination route is performed which is rare in other location based routing scheme.
Limitations
Accurate prediction on velocity and direction is not made when there are dynamic changes in the direction. The transmission is made only in linear pattern (i.e., angular velocity is kept as zero)
2) Route discovery with QoS based protocols
It is very important for any network to provide a better route. The route discovery needs to be made explicitly by satisfying the various quality of service. Those protocols which provide the routing with better QoS are named as route discovery with QoS based protocols and they are mainly categorized as proactive, reactive and hybrid.
A. Proactive
Proactive protocols are one where a routing table is maintained at every node. So it is a table driven routing protocol.
A.1.QoS Optimized Link State Routing (QOLSR)
QOLSR protocol[1] which is an enhancement of the OLSR routing protocol to support multiple-metric routing criteria. The oscillation problem and the proposed solution in the QOLSR protocol have been presented.
The flow collision problem and the back off-based solution have been identified. OLSR is a proactive routing protocol, which inherits the stability of a page link state algorithm. The basic metrics considered here are throughput and delay.
Advantages
The routes are immediately available when needed. The OLSR protocol uses a kind of Dijkstra's shortest path algorithm to provide optimal routes in terms of number of hops. It minimizes the control overhead involved in flooding routing information.
Limitations
MAC protocol is required to notify the routing protocol when it transmits a packet. QOLSR does not rely on the MAC protocol to provide residual channel capacity or delay information. These values are estimated statistically, using the periodic HELLO messages.
A.2.On-demand delay-constrained unicast routing
protocol (ODCR)
A proactive distance vector algorithm is employed to establish and maintain routing tables containing the distance and next hop along the shortest path to each destination node here. When a delay constrained path is required, this information is used to send a probe to the destination along the shortest path to test its suitability. If this path satisfies the maximum delay constraint, the destination returns an ACK packet to the source, which reserves resources. For this purpose a resource reserving MAC protocol is assumed.
Limitations
While the aim of the directed flooding is to avoid global flooding, thereby reducing overhead compared to protocols that are based on that, extra overhead is incurred by the proactive distance-vector protocol which maintains the routing tables. The article simply assumes the existence of a resource reserving MAC. However, the authors do not discuss what kind of resources they wish to reserve and how this is to be achieved. Reserving channel capacity for example, is problematic.
B. Reactive
Reactive protocols are one which does not require the maintenance of network topology when there is no traffic. The state information is acquired when needed. Thus it is an on-demand routing protocol.
B.1.Delay-sensitive adaptive routing protocol
(DSARP)
DSARP employs reactive route discovery, is completely decoupled from the MAC protocol and provides delay guarantees for time-sensitive data sessions. Its basic operation is very similar to classical reactive MANET routing protocols such as DSR. However, when a path is required for delay-sensitive traffic, a different algorithm is employed. When forwarding the RRep, each intermediate node on the path attaches the number of packets awaiting transmission in its buffer. Multiple RReps may be received by the source node, which then selects several shortest paths, if there are multiple. Alternatively, the shortest path plus the next shortest path are selected. Using the information about buffer usage at each node, the source calculates the total number of packets on each selected path. Finally, the traffic flow on each path is adjusted such that the new traffic allocated to it is greater if the existing traffic on it is lower and the number of packets on other paths is greater.
Advantages
This algorithm pushes the network towards a state where each path has an equal flow of traffic on it and thus is likely to produce the same packet delay. Essentially, this implements a form of loadbalancing, ensuring that the energy usage of nodes is also distributed evenly.
Limitations
The number of buffered packets on each path must be rediscovered each time a new session begins, regardless of whether the route has failed or not. This incurs extra overhead. Also, the delay guarantees may fail in the face of mobility, if other nodes move into contention range and cause greater channel access delays for nodes on a session's path.
B.2.QoS Routing protocol with Route Request Selection based on Mobile Predicting (QRRSMP)
QRRSMP [6] is a reactive scalable routing algorithm whose control overhead should be under control to keep up with increasing offered load. This algorithm using mobile predicting and route request selection mechanism, chooses the stable links which satisfy the multiconstraint QoS and selects the route request packets (RREQ) to reduce the number of route request packet in Mobile Ad hoc Network, thus constructing the stable QoS routing path. The reduction of RREQ packets can be done by forwarding or discarding those packets. It adopts the on demand strategy to establish and reconstruct the route. Here two neighboring nodes use GPS to communicate. Therefore Link Expiration Time (LET) between them can be easily computed. Bandwidth, delay and delay jitter are the basic QoS metrics considered over here.
B.3.Genetic Algorithm-Based QoS Routing
Protocol for MANETS (GAMAN)
A Genetic Algorithm-based source-routing Protocol for MANETs (GAMAN) is proposed, which uses end-to-end delay and transmission success rate for QoS metrics. Genetic Algorithms (GAs) may be employed for heuristically approximating an optimal solution to a problem, in this case finding the optimal route based on the two QoS constraints mentioned. The first stage of the process involves encoding routes so that a GA can be applied; this is termed gene coding. For this purpose, paths are discovered on-demand and then a network topology view is constructed in a logical tree-like structure. Each node stores a tree routed at itself with its neighbor nodes as child nodes and in turn their neighbor nodes as their children.
B.4.Multipath routing protocol (MRP)
MSR is a reactive on-demand routing Protocol which extends DSR protocol to find multipath routing coupled with bandwidth and reliability constraint. It consists of three phases: routing discovery, routing maintenance and traffic allocation.
In routing discovery phase, the protocol selects several multiple alternate paths which meet the QoS requirements and the ideal number of multipath routing is achieved to compromise between load balancing and network overhead. In routing maintenance phase, it can effectively deal with route failures similar to DSR. Furthermore, the per-packet granularity is adopted in traffic allocation phase.
B.5.Ad hoc QoS on-demand routing (AQOR)
This protocol uses limited flooding to discover the best route available in terms of smallest end-to-end delay with bandwidth guarantee. A route request packet includes both bandwidth and end-to-end delay constraints. Let Tmax denote the delay constraint. If a node can satisfy both constraints, it will rebroadcast the request to the next hop and switch to explored status for a short period of 2 Tmax.
If multiple request packets arrive at the destination, it will send back a reply packet along each of these routes. Intermediate nodes will only forward the reply, if they are still in explored state. However, the bandwidth reservation for each flow is only activated by the arrival of the first data packet from the source node. Delay is measured during route discovery. The route with the least delay is chosen by the source. No mechanism for connection tear-down is needed or integrated, since all reservations are only temporary. Timers are reset every time a route is used. So there is an upper time bound after which broken routes are detected.
To further reduce communication overhead during route discovery, AQOR can work with some location aided routing protocols. For delay violation detection, the estimated time offset between the system clocks of source and destination node has to be known.
C. Hybrid
As the name implies this kind is a combination of both proactive and reactive strategies. Thus the hybrid based routing protocols combine the merits of both proactive and reactive approaches.
C.1. QoS Multicast Routing Protocol with Dynamic group topology (QMRPD)
The QMRPD is a hybrid protocol which attempts to significantly reduce the overhead of constructing a multicast tree with multiple QoS constraints. In QMRPD, a multicast group member can join or leave a multicast session dynamically, which should not disrupt the multicast tree. It satisfies the multiple QoS constraints and least cost's (or lower cost) requirements. Its main objective is to construct a multicast tree that optimizes a certain objective function (e.g., making effective use of network resources) with respect to performance-related constraints (e.g., end-to-end delay bound, inter-receiver delay-jitter bound, minimum bandwidth available, and maximum packet-loss probability) and design a multicast routing protocol with dynamic group topology.
Advantages
It attempts to minimize overall cost of the tree. The dynamic group membership has been handled by this protocol with less message processing overhead.
C.2. Hybrid ad hoc routing protocol
As the name implies it is a hybrid protocol uses the notion of quality of connectivity (QoC) as its routing metric. This is defined as a function of two nodes states: residual buffer space and relative stability. The higher a node's residual buffer space and relative stability, the better the QoC to it is. The QoC of each node is used in a logical topology construction algorithm. In brief, a tree is constructed which is considered as routing zone, within which proactive routing occurs. Inter-zone routing is performed on-demand, and hence the hybrid route discovery of this protocol.In inter-zone routing, other zones may be abstracted as nodes, thus a packet can be routed to another zone and on arrival, and the intra-zone routing mechanism can direct the packet to its final destination.
Advantages
It includes route discovery optimizations which reduce overhead. The tree structure can be used to avoid having to flood route request (RReq) packets used in inter-zone routing. Then features of the relative distance micro discovery routing protocol (RDMAR) are incorporated into HARP [3]. Usage of the QoC metric to discover routes that have fewer buffered packets and results in lower average delay and fewer mid-session route failures, potentially yielding a lower session dropping rate. Additionally, QoC-based routing produces a load-balancing effect, which avoids congestion and early battery drainage of any single node, thereby delaying network partitioning.
Limitations
HARP does not consider an application's particular requirements, it aims only to improve average packet delay and network lifetime and to reduce the chance of route failure during a data session.
IV. Future challenges
MANETs are likely to expand their applications in the future communication environments. The support for QoS will thus be an important and desirable component of MANETs. Several important research issues and open questions need to be addressed to facilitate QoS support in MANETs. Use of location, mobility, power consumption and route availability are some of the issues that are currently being examined and need further exploration. Other challenges and open issues include robustness and security, and support for multiple levels of services in QoS routing schemes.
V. Conclusion
In this paper, we focused on the basic concepts in QoS routing in MANETs and the various issues that are needed to be faced during the provision of Quality of Service. The through overview on various QoS routing protocols have been made. We have summarized the operation, strengths and drawbacks of these protocols. There are still many issues and challenges which have not been considered. This will be subjected to further investigations.
References
[1] Hakim Badis, Ignacy Gaw^edzki and Khaldoun Al Agha, "QoS Routing in Ad Hoc Networks using QOLSR With no Need of Explicit Reservation", 2005
[2] Li Layuan and Li Chunlin, "A QoS Multicast Routing Protocol for Dynamic group topology", Information Sciences 169 (2005) 113-130.
[3] N. Nikaein, C. Bonnet, and N. Nikaein, ."Hybrid ad hoc routing protocol - HARP",. in Proc. Int. Symp. Telecommunications, 2001.
[4] M. Sheng, J. Li, and Y. Shi, . "Routing protocol with QoS guarantees for ad-hoc network" ,. Electronics Letters, vol. 39, pp. 143.145, Jan. 2003.
[5] B. Zhang and H. T. Mouftah,. "QoS routing for wireless ad hoc networks: problems, algorithms and protocols" ,. IEEE Commun. Mag., vol. 43, pp. 110.117, Oct. 2005.
[6] Jin LIAN, Layuan LI and Xiaoyan ZHU,"A multi-constraint QoS Routing Protocol with Route-Request Selection based on Mobile Predicting in MANET",.International conference on computational Intelligence and security Workshops,2007
[7] P. Jacquet, P. Muhlethaler, T. Clausen, A. Laouiti, A. Qayyum, and L.Viennot,. "Optimized page link state routing protocol for ad hoc networking",. in Proc. IEEEMulti Topic Conf., pp. 62.68, Dec. 2001.
[8] H. Badis and K. A. Agha,. "QOLSR, QoS routing for ad hoc wireless networks using OLSR",. Wiley European Trans. Telecommunications, vol. 15, no. 4, pp. 427.442, 2005.
[9] H. Badis, A. Munaretto, K. Al Agha and G. Pujolle, "QoS for Ad hoc Networking Based on Multiple Metrics: Bandwidth and Delay," In the proceedings of IEEE MWCN2003, Singapore, October 2003.
[10] H. Badis, K. Al Agha, A. Munaretto and G. Pujolle, "Optimal Path Selection in a Link State QoS Routing," In the proceedings of IEEE VTC'04 spring, Italy, May 2004.
[11]L. Hanzo (II.) and R. Tafazolli, "A survey on QoS Routing Solutions for Mobile Adhoc networks",a technical support from CCSR,2007.
