QoS support in Mobile Ad hoc networks (Review)

Due to mobile node's high mobility, rapid topology change, limited bandwidth and fluctuate link quality, QoS provision in mobile ad hoc networks has big difference to qos provision in wired networks and is much more difficult. The QoS techniques used in wired networks, such as IntServ [11], DiffServ [12], cannot be directly applied to the ad hoc networks to provide wireless QoS due to the characteristic of ad hoc networks. The research on QoS in ad hoc networks includes QoS model, resource reservation signaling protocol, QoS routing protocol, and Medium Access Control protocol support.

A QoS model is the system goal that specifies an architecture in which some kinds of service could be provided. It can be per flow based, or just provide several differentiated services. However, it must be feasible. Basically, there are two categories, stateless and stateful. In general, stateful QoS model has more overhead and scalability issue, but QoS can not be guaranteed in stateless model. Depends on the QoS model, we may or may not need a signaling protocol. Normally, statelful QoS model needs signaling protocol and stateless QoS model doesnĄ¯t. A signaling protocol is used to exchange user requirement, control and state information between different nodes so that resources can be reserved for certain flow. It can be in-band or out-of-band. For ad hoc networks, the signaling protocol must be soft state due to the frequent topology change. QoS routing protocol determines the path that can satisfy the requested service level. A QoS friendly MAC layer is required to make QoS possible in higher layers.

The most basic QoS support would be to provide bandwidth guarantee. There are other metrics, such as end-to-end delay, jitter, cost. According to [17], two types of QoS metrics are defined, concave and additive. The bandwidth metric is concave because a certain amount of bandwidth must be required on every link along the path from source to destination. Delay and cost are additive because we need add all delays or costs on every link along the path. With precise state information of the network, the bandwidth-constrained lease-cost QoS routing problem can be solved in polynomial time. However, the delay-constrained QoS routing problem is NP-complete, according to [19] and [20]. For ad hoc networks, even for bandwidth-constrained QoS routing is harder because it is very unlikely to get precise state information of the network due to node mobility and power outage. So, basically, we are doing QoS support in ad hoc networks using inaccurate or rough state information. Moreover, the overhead of QoS signaling and routing in ad hoc networks must be low. Otherwise, the normal data traffic will be affected due to the already limited network capacity. To low the QoS overhead, we need to let every node maintain the state information as few as possible, use local state and keep global state information low. Another reason we try to avoid global state information is its inaccuracy due to the frequent network change.

Core-Extraction Distributed Ad-hoc Routing (CEDAR) [13] presents the idea that establishes and maintains a self-organizing routing infrastructure called core for performing route computations. The core of the network is an approximation of a minimum dominating set of the network. Every host chooses a neighbor core host as its dominator. A path between two core hosts is called a virtual link. Core hosts and virtual links form a core graph. Core hosts are relatively stable, high performance hosts. Every host reports to its dominator when its stability or available bandwidth changes. Core hosts exchange the state information. CEDAR provides a link state propagation mechanism that keeps unstable low-bandwidth link states locally. Then, a route computation method is used to establish the path from source to destination based on the core path. Distributed route computation, no broadcasting and no global state information exchange are the advantages of CEDAR. However, the author did not explain in detail on the generation and maintenance of the core. We know finding the minimum dominating set is NP-hard. The author did give an approximation algorithm, but did not evaluate how good the core is. Moreover, the selection of the core nodes is not only a mathematical problem, but also needs follow certain criteria, such as stability, power, bandwidth and so on.

ChenĄ¯s paper [14] proposed a ticket-based probing algorithm, which is a distributed ad hoc QoS routing. The basic idea is using tickets to limit the number of candidate paths. A ticket is the permission to search one path. The source node issues a number of tickets based on the available state information. One guideline is that more tickets are issues for the connections with tighter requirement. Probe routing messages are sent from the source toward the destination to search for a low-cost path that satisfies the QoS requirement. Each probe is required to carry at least one ticket. At an intermediate node, a probe with more than one ticket is allowed to be split into multiple ones, each searching a different downstream sub-path. The maximum number of probes at any time is bounded by the total number of tickets. Upon receipt of a probe, an intermediate node can decide whether to split it and where to forward. Although ticket-based probing algorithm is done on a per-connection basis, the routing overhead is still low because there is no flooding path-discovery. The routing activity is localized in a small part of the network between the source and the destination. Another advantage of the algorithm is that it supports multi-path routes, which provides redundancy. Further, the algorithm makes an intelligent hop-by-hop path selection to guide the search along the best candidate paths. A certain number of criteria are used to make the path selection, such as the residual bandwidth, delay, connectivity. In the paper, the author used a loose source routing method to record the path. When the destination received a valid ticket, it can extract the exact path and report to the source. The problem here is that the probes become larger along the path and consumes more bandwidth. Another issue for the algorithm is that it may take a long time for the source to timeout if no valid ticket arrives the destination in case of message losses.

[15] presents an idea to support QoS in mobile wireless environment, predictive and adaptive QoS scheme by integrating mobility model into the service model. If you can have an accurate mechanism to predict the trajectory of the mobile user, then it would be much easier to allocate the resource, select the path in advance, then fulfill required QoS. To do this, we need to know the mobile users mobility model and have their movement profile. However, the paper is mainly focused on cellular networks. For ad hoc networks, the mobility model and user profile are different. We need more mechanism to extract more relevant information to do prediction. We may need GPS, or other more precise location system to provide detailed mobility model. We need not only predict the movement, but also the power, error rate, bandwidth and other factors. To get precise information about these, we need rely on some MAC layer mechanism.

SWAN[6] represents a simple, stateless network model that uses distributed control algorithms to support "soft" real-time services and service differentiation in wireless ad hoc networks. SWAN uses rate control for UDP and TCP best-effort traffic and sender-based admission control for UDP real-time traffic. In addition, SWAN uses explicit congestion notification (ECN) to dynamically regulate admitted real-time traffic in the face of network dynamics brought on by mobility or traffic overload conditions. They use the term "soft" real-time services to indicate that real-time sessions could be regulated or dropped due to mobility or excessive traffic overloading at wireless routers. SWAN is designed to limit such conditions, however. They claim that it does not require the support of a QOS-capable/real-time MAC. Rather, soft real-time services are built using existing best effort wireless MAC technology. They implemented SWAN using the ns-2 simulator. They evaluate and compare the performance of DCF, SWAN, and CWmin.

INSIGNIA[5] is an IP-based quality of service framework that supports adaptive services in mobile ad hoc networks. The framework is based on an in-band signaling and soft-state resource management approach that is well suited to supporting mobility and end-to-end quality of service in highly dynamic environments where the network topology, node connectivity, and end-to-end quality of service are time varying. Architecturally INSIGNIA is designed to support fast reservation, restoration, and end-to-end adaptation based on the inherent flexibility and robustness and scalability found in IP networks. They evaluate the framework, paying particular attention to the performance of the in-band signaling system, which helps counter time-varying network dynamics in support of the delivery of adaptive services. They claim their results show the benefit of the framework under diverse mobility, traffic, and channel conditions.

In a localized routing algorithm[8], node A currently holding the message forwards it based on the location of itself, its neighboring nodes and destination. They propose to use depth first search (DFS) method for routing decisions. Each node A, upon receiving the message for the first time, sorts all its neighbors according to a criteria, such as their distance to destination, and uses that order in DFS algorithm. It is the first localized algorithm that guarantees delivery for (connected) wireless networks modeled by arbitrary graphs, including inaccurate location information. They then propose the first localized QoS routing algorithm for wireless networks. It performs DFS routing algorithm after edges with insufficient bandwidth or insufficient connection time are deleted from the graph, and attempts to minimize hop count. They apply GPS in QoS routing decisions, and to consider the connection time (estimated lifetime of a link) as a QoS criterion. The average length of measured QoS path in their experiments, obtained by DFS method, was between 1 and 1.34 times longer than the length of QoS path obtained by shortest path algorithm. The overhead is considerably reduced by applying the concept of internal nodes.

This paper[1] explores, primarily by means of analysis, the differences that can exist between individual and aggregate loss guarantees in an environment where guarantees are only provided at an aggregate level. The focus is on understanding which traffic parameters are responsible for inducing possible deviations and to which extent. They seek to evaluate the level of additional resources, e.g., bandwidth or buffer, required to ensure that all individual loss measures remain below their desired target. The paper's contributions are in developing analytical models that enable the evaluation of individual loss probabilities in settings where only aggregate losses are controlled, and in identifying traffic parameters that play a dominant role in causing differences between individual and aggregate losses. The latter allows the construction of guidelines identifying which traffic can be safely multiplexed into a common service class.

The QoS information[2] used for routing by traditional QoS routing protocols becomes obsolete due to node mobility. To overcome this problem, a predictive QoS routing scheme is needed. In this paper, they present a location-delay prediction scheme, based on a location-resource update protocol, which assists a QoS routing protocol. Their location updates also 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. They claim that their simulation results show that, with their approach, they can predict the location at a given instant in the future with a high degree of accuracy.

Overall, only limited number of literature have practical effect on QoS routing in ad hoc networks. Just like general ad hoc routing protocols, there is no one-fit-all solution for ad hoc qos routing. Depends on the different scenarios, different algorithms may be used. We believe QoS in ad hoc networks needs to hold the following properties: lightweight (limited overhead), adaptive to the highly dynamic environment, not optimal but robust, ability to work decently even under inaccurate information [20] and uncertain QoS parameters [18], localized state information exchange, close interaction between different layers. Better performance can be achieved by using new technology and techniques, such as location service, mobility prediction, geography routing.

1. Y. Xu and R. Guerin, "Individual QoS versus aggregate QoS: A loss performance study." In Proceedings of INFOCOM'02, New York, NY, June 2002.

2. Samarth H. Shah, Klara Nahrstedt, Predictive Location-Based QoS Routing in Mobile Ad Hoc Networks, in Proc. of IEEE International Conference on Communications (ICC 2002), New York, NY, April 28th - May 2nd, 2002. 

3. QoS routing performance in a multi-hop, wireless networks 
     Tsu-Wei Chen, Mario Gerla and Jack Tzu-Chieh Tsai 
     In Proceedings of ICUPC '97

4. Lee, S.B., Ahn, G.S., Campbell, A.T., "Improving UDP and TCP Performance in Mobile Ad Hoc Networks with INSIGNIA",June 2001, IEEE Communication Magazine. 

5.Seoung-Bum Lee and Andrew T. Campbell " INSIGNIA: In-band signaling support for QOS in mobile ad hoc networks" , Proc of 5th International Workshop on Mobile Multimedia Communications (MoMuC,98) , Berlin, Germany, October 1998.

6. Gahng-Seop Ahn, Andrew T. Campbell, Andras Veres and Li-Hsiang Sun, "Supporting Service Differentiation for Real-Time and Best Effort Traffic in Stateless Wireless Ad Hoc Networks (SWAN)", IEEE Transactions on Mobile Computing, September 2002.

7. Gahng-Seop Ahn, Andrew T. Campbell, Andras Veres and Li-Hsiang Sun, "SWAN: Service Differentiation in Stateless Wireless Ad Hoc Networks", Proc. IEEE INFOCOM'2002, New York, New York, June 2002.

8. Depth first search and location based localized routing and QoS routing in wireless networks (2000) 
Ivan Stojmenovic, Mark Russell
International Conference on Parallel Processing

9. David Julian and Mung Chiang and Daniel O'Neill and Stephen Boyd, QoS and Fairness Constrained Convex Optimization of Resource Allocation for Wireless Cellular and Ad Hoc Networks", IEEE INFOCOM 2002


10. Si Wu and K. Y. Michael Wong and Bo Li , A dynamic call admission policy with precision QoS guarantee using stochastic control for mobile wireless networks, IEEE/ACM Transactions on Networking (TON), V10(2), 2002

11. Braden, R., Clark, D., Shenker, S., Integrated Services in the Internet Architecture: An Overview, IETF RFC 1633, 1994.

12. S.Blake et. al., An Architecture for Differentiated Services, IETF RFC 2475, December 1998.

13 R. Sivakumar, P. Sinha, and V. Bharghavan, CEDAR: A Core-Extraction Distributed Ad Hoc Routing Algorithm, IEEE Journal on Selected Areas in Communications, Special Issue on Ad Hoc Networks, vol. 17, pp. 1454 65, Aug. 1999.

14 S. Chen and K. Nahrstedt. Distributed quality-of-service routing in ad-hoc networks. IEEE Journal on Selected Areas in Communications, 17(8), August 1999.

15 Abdul Rahman Aljadhai, Taieb Znati: Predictive mobility support for QoS provisioning in mobile wireless environments. IEEE Journal on Selected Areas in Communications 19(10): 1915-1930 (2001)

16 M. Chiang, D. ONeill, D. Julian, and S. Boyd, Resource Allocation for QoS Provisioning in Wireless Ad Hoc Networks,Proceedings of IEEE GLOBECOM, San Antonio, TX, November 2001, pp. 2911-5.

17 S. Chen and K. Nahrstedt. Distributed Quality-of-Service Routing in High-Speed Networks Based on Selective Probing. In 23rd Annual Conference on Local Computer Networks, LCN'98, 1998

18 D. H. Lorenz and A. Orda, QoS Routing in Networks with Uncertain Parameters. IEEE INFOCOM'98, March 1998.

19 Z. Wang and J. Crowcroft, QoS routing for supporting resource reservation, IEEE J. on Select. Areas in Comm., Vol.14(7), pp.1228-1234, September 1996.

20 R. Gu'erin and A. Orda. QoS-based routing in networks with inaccurate information: Theory and algorithms. IEEE/ACM Transactions on Networking, 7(3):350 -- 364, 1999.