A REVIEW AND COMPARISON OF QUALITY OF SERVICE ROUTING IN WIRELESS AD HOC NETWORKS
---
paper_title: Routing Support for Providing Guaranteed End-To-End Quality-Of-Service

paper_content:

The up-coming Gbps high-speed networks are expected to support a wide range of real-time, communication-intensive applications. The quality-of-service (QoS) requirements for the timely delivery of multimedia information raise new challenges for the development of integrated-service broadband networks. One of the key issues is QoS routing, which allows selecting network routes with sufficient resources for requested QoS parameters. The goal of QoS routing solutions is two-fold: satisfying the QoS requirements for every admitted connection and achieving global efficiency in resource utilization. ::: Many unicast/multicast QoS routing algorithms were published recently. However, there still exist a lot of unsolved problems in this area. A few examples are listed as follows. (1) There lacks a simple solution with predictable performance and adjustable overhead for the NP-complete multi-constraint routing problem. (2) All existing algorithms are tailored towards specific problems, and there lacks a simple, general routing framework which can be easily extended to handle new problems. (3) Most routing algorithms assume the availability of precise state information about the network, which however is impractical in the real world. ::: We address the above problems, and the goal of this dissertation is to provide simple, general and extensible solutions for QoS routing. We study different routing strategies, compare them and outline the challenges. We propose various algorithms based on different network state models, evaluate these algorithms by analysis and simulation, discuss their strengths and weaknesses of different routing strategies, and compare them with the existing algorithms. The major achievement of this dissertation is outlined in the following. (1) A heuristic approach is proposed to solve the multi-constraint routing problem. It allows the dynamic tradeoff between performance and overhead. (2) A distributed routing framework is proposed to integrate a family of routing algorithms which support applications with QoS requirements on bandwidth, delay, delay jitter, cost, path length, and their combination. (3) Source and distributed routing algorithms axe proposed to work with state information which has a high degree of imprecision. (4) Distributed QoS routing algorithms are proposed for mobile ad-hoc networks whose topologies change as nodes move, join, or leave the networks. (5) An integrated framework is proposed to support routing and scheduling of co-existing QoS and best-effort flows.
---
paper_title: QoS in Mobile Ad Hoc Networks

paper_content:

A mobile ad hoc network (MANET) consists of mobile nodes communicating over wireless channels. Routing in MANETs is very challenging due to the random mobility of nodes and unreliability of wireless channels. Therefore most of the existing routing algorithms make only the best effort to find routes for communication but do not provide any performance guarantee. Because of the widespread use of MANETs in real-time applications, it becomes pertinent to provide deterministic network behavior. Quality of Service (QoS) aims to shape the network behavior and provide performance guarantees. In this work, a novel heuristic called Advanced-Optimised Link State Routing (A-OLSR) protocol is designed to provide QoS. It functions by enhancing the connectivity of nodes and establishing more stable routes as compared to standard best-effort Optimised Link State Routing (OLSR) protocol. The simulation results show that A-OLSR provides lower delay, reduces energy consumption and achieves higher throughput without introducing any additional routing overhead as compared to the standard OLSR and it's variants-A$$'$$?-OLSR and A$$''$$??-OLSR. The results also show that A-OLSR provides scalability since it's performance remains consistent with the increasing size of network.
---
paper_title: QoS-aware routing based on bandwidth estimation for mobile ad hoc networks

paper_content:

Routing protocols for mobile ad hoc networks (MANETs) have been explored extensively in recent years. Much of this work is targeted at finding a feasible route from a source to a destination without considering current network traffic or application requirements. Therefore, the network may easily become overloaded with too much traffic and the application has no way to improve its performance under a given network traffic condition. While this may be acceptable for data transfer, many real-time applications require quality-of-service (QoS) support from the network. We believe that such QoS support can be achieved by either finding a route to satisfy the application requirements or offering network feedback to the application when the requirements cannot be met. We propose a QoS-aware routing protocol that incorporates an admission control scheme and a feedback scheme to meet the QoS requirements of real-time applications. The novel part of this QoS-aware routing protocol is the use of the approximate bandwidth estimation to react to network traffic. Our approach implements these schemes by using two bandwidth estimation methods to find the residual bandwidth available at each node to support new streams. We simulate our QoS-aware routing protocol for nodes running the IEEE 802.11 medium access control. Results of our experiments show that the packet delivery ratio increases greatly, and packet delay and energy dissipation decrease significantly, while the overall end-to-end throughput is not impacted, compared with routing protocols that do not provide QoS support.
---
paper_title: Ad hoc networks

paper_content:

Recent developments offer potential solutions to problems encountered In ad hoc networks Including topology control, data communication, and service access.
---
paper_title: Routing Protocols for Next Generation Networks Inspired by Collective Behaviors of Insect Societies: An Overview

paper_content:

In this chapter we discuss the properties and review the main instances of network routing algorithms whose bottom-up design has been inspired by collective behaviors of social insects such as ants and bees. This class of bio-inspired routing algorithms includes a relatively large number of algorithms mostly developed during the last ten years. The characteristics inherited by the biological systems of inspiration almost naturally empower these algorithms with characteristics such as autonomy, self-organization, adaptivity, robustness, and scalability, which are all desirable if not necessary properties to deal with the challenges of current and next-generation networks. In the chapter we consider different classes of wired and wireless networks, and for each class we briefly discuss the characteristics of the main ant- and bee-colony-inspired algorithms which can be found in literature. We point out their distinctive features and discuss their general pros and cons in relationship to the state of the art.
---
paper_title: CEDAR: a core-extraction distributed ad hoc routing algorithm

paper_content:

CEDAR is an algorithm for QoS routing in ad hoc network environments. It has 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 stable high-bandwidth links in the core through increase/decrease waves, and (c) a QoS route computation algorithm that is executed at the core nodes using only locally available state. But preliminary performance evaluation shows that CEDAR is a robust and adaptive QoS routing algorithm that reacts effectively to the dynamics of the network while still approximating link-state performance for stable networks.
---
paper_title: Research challenges in QoS routing

paper_content:

Quality of Service Routing is at present an active and remarkable research area, since most emerging network services require specialized Quality of Service (QoS) functionalities that cannot be provided by the current QoS-unaware routing protocols. The provisioning of QoS based network services is in general terms an extremely complex problem, and a significant part of this complexity lies in the routing layer. Indeed, the problem of QoS Routing with multiple additive constraints is known to be NP-hard. Thus, a successful and wide deployment of the most novel network services demands that we thoroughly understand the essence of QoS Routing dynamics, and also that the proposed solutions to this complex problem should be indeed feasible and affordable. This article surveys the most important open issues in terms of QoS Routing, and also briefly presents some of the most compelling proposals and ongoing research efforts done both inside and outside the E-Next Community to address some of those issues.
---
paper_title: Routing Protocols for Next Generation Networks Inspired by Collective Behaviors of Insect Societies: An Overview

paper_content:

In this chapter we discuss the properties and review the main instances of network routing algorithms whose bottom-up design has been inspired by collective behaviors of social insects such as ants and bees. This class of bio-inspired routing algorithms includes a relatively large number of algorithms mostly developed during the last ten years. The characteristics inherited by the biological systems of inspiration almost naturally empower these algorithms with characteristics such as autonomy, self-organization, adaptivity, robustness, and scalability, which are all desirable if not necessary properties to deal with the challenges of current and next-generation networks. In the chapter we consider different classes of wired and wireless networks, and for each class we briefly discuss the characteristics of the main ant- and bee-colony-inspired algorithms which can be found in literature. We point out their distinctive features and discuss their general pros and cons in relationship to the state of the art.
---
paper_title: Routing Support for Providing Guaranteed End-To-End Quality-Of-Service

paper_content:

The up-coming Gbps high-speed networks are expected to support a wide range of real-time, communication-intensive applications. The quality-of-service (QoS) requirements for the timely delivery of multimedia information raise new challenges for the development of integrated-service broadband networks. One of the key issues is QoS routing, which allows selecting network routes with sufficient resources for requested QoS parameters. The goal of QoS routing solutions is two-fold: satisfying the QoS requirements for every admitted connection and achieving global efficiency in resource utilization. ::: Many unicast/multicast QoS routing algorithms were published recently. However, there still exist a lot of unsolved problems in this area. A few examples are listed as follows. (1) There lacks a simple solution with predictable performance and adjustable overhead for the NP-complete multi-constraint routing problem. (2) All existing algorithms are tailored towards specific problems, and there lacks a simple, general routing framework which can be easily extended to handle new problems. (3) Most routing algorithms assume the availability of precise state information about the network, which however is impractical in the real world. ::: We address the above problems, and the goal of this dissertation is to provide simple, general and extensible solutions for QoS routing. We study different routing strategies, compare them and outline the challenges. We propose various algorithms based on different network state models, evaluate these algorithms by analysis and simulation, discuss their strengths and weaknesses of different routing strategies, and compare them with the existing algorithms. The major achievement of this dissertation is outlined in the following. (1) A heuristic approach is proposed to solve the multi-constraint routing problem. It allows the dynamic tradeoff between performance and overhead. (2) A distributed routing framework is proposed to integrate a family of routing algorithms which support applications with QoS requirements on bandwidth, delay, delay jitter, cost, path length, and their combination. (3) Source and distributed routing algorithms axe proposed to work with state information which has a high degree of imprecision. (4) Distributed QoS routing algorithms are proposed for mobile ad-hoc networks whose topologies change as nodes move, join, or leave the networks. (5) An integrated framework is proposed to support routing and scheduling of co-existing QoS and best-effort flows.
---
paper_title: Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers

paper_content:

An ad-hoc network is the cooperative engagement of a collection of Mobile Hosts without the required intervention of any centralized Access Point. In this paper we present an innovative design for the operation of such ad-hoc networks. The basic idea of the design is to operate each Mobile Host as a specialized router, which periodically advertises its view of the interconnection topology with other Mobile Hosts within the network. This amounts to a new sort of routing protocol. We have investigated modifications to the basic Bellman-Ford routing mechanisms, as specified by RIP [5], to make it suitable for a dynamic and self-starting network mechanism as is required by users wishing to utilize ad hoc networks. Our modifications address some of the previous objections to the use of Bellman-Ford, related to the poor looping properties of such algorithms in the face of broken links and the resulting time dependent nature of the interconnection topology describing the links between the Mobile Hosts. Finally, we describe the ways in which the basic network-layer routing can be modified to provide MAC-layer support for ad-hoc networks.
---
paper_title: QoS in Mobile Ad Hoc Networks

paper_content:

A mobile ad hoc network (MANET) consists of mobile nodes communicating over wireless channels. Routing in MANETs is very challenging due to the random mobility of nodes and unreliability of wireless channels. Therefore most of the existing routing algorithms make only the best effort to find routes for communication but do not provide any performance guarantee. Because of the widespread use of MANETs in real-time applications, it becomes pertinent to provide deterministic network behavior. Quality of Service (QoS) aims to shape the network behavior and provide performance guarantees. In this work, a novel heuristic called Advanced-Optimised Link State Routing (A-OLSR) protocol is designed to provide QoS. It functions by enhancing the connectivity of nodes and establishing more stable routes as compared to standard best-effort Optimised Link State Routing (OLSR) protocol. The simulation results show that A-OLSR provides lower delay, reduces energy consumption and achieves higher throughput without introducing any additional routing overhead as compared to the standard OLSR and it's variants-A$$'$$?-OLSR and A$$''$$??-OLSR. The results also show that A-OLSR provides scalability since it's performance remains consistent with the increasing size of network.
---
paper_title: Adaptive Proportional Routing: A Localized QoS Routing Approach

paper_content:

Most of the QoS routing schemes proposed so far require periodic exchange of QoS state information among routers, imposing both communication overhead on the network and processing overhead on core routers. Furthermore, stale QoS state information causes the performance of these QoS routing schemes to degrade drastically. In order to circumvent these problems, we focus on localized QoS routing schemes where the edge routers make routing decisions using only local information and thus reducing the overhead at core routers. We first describe virtual capacity based routing (vcr), a theoretical scheme based on the notion of virtual capacity of a route. We then propose proportional sticky routing, an easily realizable approximation of vcr and analyze its performance. We demonstrate through extensive simulations that adaptive proportional routing is indeed a viable alternative to the global QoS routing approach.
---
paper_title: Cross-layer wireless multimedia transmission: challenges, principles, and new paradigms

paper_content:

Wireless networks are poised to enable a variety of existing and emerging multimedia streaming applications. As the use of wireless local area networks spreads beyond simple data transfer to bandwidth-intense, delay-sensitive, and loss-tolerant multimedia applications, addressing quality of service issues become extremely important. Currently, a multitude of protection and adaptation strategies exists in the different layers of the open systems interconnection (OSI) stack. Hence, an in-depth understanding and comparative evaluation of these strategies are necessary to effectively assess and enable the possible trade-offs in multimedia quality, power consumption, implementation complexity, and spectrum utilization that are provided by the various OSI layers. This further opens the question of cross-layer optimization and its effectiveness in providing an improved solution with respect to the above trade-offs. In this article we formalize the cross-layer problem, discuss its challenges, and present several possible solutions. Moreover, we also discuss the impact the cross-layer optimization strategy deployed at one station has on the multimedia performance of other stations. We introduce a new fairness concept for wireless multimedia systems that employs different cross-layer strategies, and show its advantages when compared to existing resource allocation mechanisms used in wireline communications. Finally, we propose a new paradigm for wireless communications based on competition, which allows wireless stations to harvest additional resources or free up resources as well as optimally and dynamically adapt their cross-layer transmission strategies to improve multimedia quality and/or power consumption.
---
paper_title: Application-Specific Protocol Architectures for Wireless Networks

paper_content:

In recent years, advances in energy-efficient design and wireless technologies have enabled exciting new applications for wireless devices. These applications span a wide range, including real-time and streaming video and audio delivery, remote monitoring using networked microsensors, personal medical monitoring, and home networking of everyday appliances. While these applications require high performance from the network, they suffer from resource constraints that do not appear in more traditional wired computing environments. In particular, wireless spectrum is scarce, often limiting the bandwidth available to applications and making the channel error-prone, and the nodes are battery-operated, often limiting available energy. ::: My thesis is that this harsh environment with severe resource constraints requires an application-specific protocol architecture, rather than the traditional layered approach, to obtain the best possible performance. This dissertation supports this claim using detailed case studies on microsensor networks and wireless video delivery. The first study develops LEACH (Low-Energy Adaptive Clustering Hierarchy), an architecture for remote microsensor networks that combines the ideas of energy-efficient cluster-based routing and media access together with application-specific data aggregation to achieve good performance in terms of system lifetime, latency, and application-perceived quality. This approach improves system lifetime by an order of magnitude compared to general-purpose approaches when the node energy is limited. The second study develops an unequal error protection scheme for MPEG-4 compressed video delivery that adapts the level of protection applied to portions of a packet to the degree of importance of the corresponding bits. This approach obtains better application-perceived performance than current approaches for the same amount of transmission bandwidth. These two systems show that application-specific protocol architectures achieve the energy and latency efficiency and error robustness needed for wireless networks. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)
---

Title: A REVIEW AND COMPARISON OF QUALITY OF SERVICE ROUTING IN WIRELESS AD HOC NETWORKS

Section 1: INTRODUCTION
Description 1: Summarize the essentials of Wireless Ad Hoc Networks (WANET) and introduce the importance of Quality of Service (QoS) routing in these networks.

Section 2: QOS ROUTING
Description 2: Explain the concept of QoS routing, its objectives, and differentiate it from best-effort routing. Discuss the bottom-up and top-down design approaches for routing protocols.

Section 3: Routing Protocol
Description 3: Detail the role and different approaches of the routing protocol in wireless ad hoc networks including local, global, and aggregated state representations.

Section 4: Routing Algorithm
Description 4: Outline the static routing algorithm's role in making routing decisions, and classify routing algorithms based on behavior, selection rule, and routing decision.

Section 5: Challenges in QoS Routing
Description 5: Address the challenges faced in QoS routing such as dynamic topology, bandwidth sharing, resource constraints, and lack of centralized control.

Section 6: QOS METRICS
Description 6: Describe the constraints and metrics used in QoS routing, including delay, bandwidth, probability of packet loss, and classify these metrics into concave, multiplicative, or additive constraints.

Section 7: Multi Constrained Path (MCP) Problem
Description 7: Define the MCP problem, elaborate on finding feasible paths that satisfy multiple constraints, and introduce the concept of path dominance.

Section 8: Multi Constrained Optimal Path (MCOP) Problem
Description 8: Present the MCOP problem which involves optimizing paths that satisfy multiple constraints, and discuss nondominated solutions and the pareto optimal set.

Section 9: QOS AWARE ROUTING PROTOCOLS
Description 9: Provide analysis and examples of different QoS-aware routing protocols like CEDAR, TBP, AQOR, BEQR, APR, and QAODV.

Section 10: CROSS LAYER DESIGN
Description 10: Discuss the concept of cross-layer design as an alternative to traditional network architectures for optimizing performance, and outline its application in wireless standards.

Section 11: CONCLUSION
Description 11: Summarize the importance of QoS routing in wireless ad hoc networks, review the discussed protocols, and suggest future research directions focusing on energy constraints and cross-layer optimization.