QoS routing through alternate paths in wireless ad hoc networks

Quality of service (QoS) routing plays an important role in QoS provisioning for mobile ad hoc networks. This work studies the issue of route selection subject to QoS constraint(s). Our method searches for alternate routes with satisfied QoS requirement(s) to accommodate each communication request when the shortest path connecting the source–destination pair of the request is not qualified. In order to effectively reduce protocol overhead, a directed search mechanism is designed to limit the breadth of the searching scope, which aims at achieving a graceful tradeoff between the success probability in QoS route acquisition and communication overhead. Efficient hop‐by‐hop routing protocols are designed for route selection subject to delay and bandwidth constraint, respectively. Simulation results show that the designed protocols can achieve high performance in acquiring QoS paths and in efficient resource utilization with low control overhead. Copyright © 2004 John Wiley & Sons, Ltd.     

A new delay‐constrained algorithm for multicast routing tree construction

New multimedia applications provide guaranteed end‐to‐end quality of service (QoS) and have stringent constraints on delay, delay‐jitter, bandwidth, cost, etc. The main task of QoS routing is to find a route in the network, with sufficient resources to satisfy the constraints. Most multicast routing algorithms are not fast enough for large‐scale networks and where the source node uses global cost information to construct a multicast tree. We propose a fast and simple heuristic algorithm (EPDT) for delay‐constrained routing problem for multicast tree construction. This algorithm uses a greedy strategy based on shortest‐path and minimal spanning trees. It combines the minimum cost and the minimum radius objectives by combining respectively optimal Prim's and Dijkstra's algorithms. It biases routes through destinations. Besides, it uses cost information only from neighbouring nodes as it proceeds, which makes it more practical, from an implementation point of view. Copyright © 2004 John Wiley & Sons, Ltd.     

A location prediction based routing protocol and its extensions for multicast and multi-path routing in mobile ad hoc networks

This paper discusses a new location prediction based routing (LPBR) protocol for mobile ad hoc networks (MANETs) and its extensions for multicast and multi-path routing. The objective of the LPBR protocol is to simultaneously minimize the number of flooding-based route discoveries as well as the hop count of the paths for a source–destination (s–d) session. During a regular flooding-based route discovery, LPBR collects the location and mobility information of nodes in the network and stores the collected information at the destination node of the route search process. When the minimum-hop route discovered through flooding fails, the destination node locally predicts a global topology based on the location and mobility information collected during the latest flooding-based route discovery and runs a minimum-hop path algorithm. If the predicted minimum-hop route exists in reality, no expensive flooding-based route discovery is needed and the source continues to send data packets on the discovered route. Similarly, we propose multicast extensions of LPBR (referred to as NR-MLPBR and R-MLPBR) to simultaneously reduce the number of tree discoveries and the hop count per path from the source to each multicast group receiver. Nodes running NR-MLPBR are not aware of the receivers of the multicast group. R-MLPBR assumes that each receiver node also knows the identity of the other receiver nodes of the multicast group. Finally, we also propose a node-disjoint multi-path extension of LPBR (referred to as LPBR-M) to simultaneously minimize the number of multi-path route discoveries as well as the hop count of the paths.     

Bandwidth‐guaranteed QoS routing of multiple parallel paths in CDMA/TDMA ad hoc wireless networks

This paper investigates the issues of QoS routing in CDMA/TDMA ad hoc networks. Since the available bandwidth is very limited in ad hoc networks, a QoS request between two nodes will be blocked if there does not exist a path that can meet the QoS requirements, even though there is enough free bandwidth in the whole system. In this paper, we propose a new scheme of using multiple paths between two nodes as the route for a QoS call. The aggregate bandwidth of the multiple paths can meet the bandwidth requirement of the call and the delays of these paths are within the required bound of the call. We also propose three strategies by which to choose a set of paths as the route, namely, shortest path first (SPF), largest bandwidth first (LBF), and largest hop‐bandwidth first (LHBF). Extensive simulations have been conducted to evaluate the performance of the three strategies in comparison with a traditional single path routing algorithm. The simulation results show that the proposed multiple paths routing scheme significantly reduces the system blocking rates in various network environments, especially when the network load is heavy. Copyright © 2005 John Wiley & Sons, Ltd.     

TREE: Routing strategy with guarantee of QoS for industrial wireless sensor networks

As considerable progress has been made in wireless sensor networks (WSNs), we can expect that sensor nodes will be applied in industrial applications. Most available techniques for WSNs can be transplanted to industrial wireless sensor networks (IWSNs). However, there are new requirements of quality of service (QoS), that is, real‐time routing, energy efficiency, and transmission reliability, which are three main performance indices of routing design for IWSNs. As one‐hop neighborhood information is often inadequate to data routing in IWSNs, it is difficult to use the conventional routing methods. In the paper, we propose the routing strategy by taking the real‐time routing performance, transmission reliability, and energy efficiency (TREE, triple R and double E) into considerations. For that, each sensor node should improve the capability of search range in the phase of data route discovery. Because of the increase of available information in the enlarged search range, sensor node can select more suitable relay node per hop. The real‐time data routes with lower energy cost and better transmission reliability will be used in our proposed routing guideline. By comparing with other routing methods through extensive experimental results, our distributed routing proposal can guarantee the diversified QoS requirements in industrial applications. Copyright © 2012 John Wiley & Sons, Ltd.     

On-demand loop-free routing with link vectors

We present the on-demand link vector (OLIVE) protocol, a routing protocol for ad hoc networks based on link-state information that is free of routing loops and supports destination-based packet forwarding. Routers exchange routing information reactively for each destination in the form of complete paths, and each node creates a labeled source graph based on the paths advertised by its neighbors. A node originates a broadcast route request (RREQ) to obtain a route for a destination for which a complete path does not exist in its source graph. When the original path breaks, a node can select an alternative path based on information reported by neighbors, and a node can send a unicast RREQ to verify that the route is still active. A node that cannot find any alternate path to a destination sends route errors reliably to those neighbors that were using it as next hop to the destination. Using simulation experiments in ns2, OLIVE is shown to outperform dynamic source routing, ad hoc on-demand distance vector, optimized link-state routing protocol, and topology broadcast based on reverse-path forwarding, in terms of control overhead, throughput, and average network delay, while maintaining loop-free routing with no need for source routes.     

Improved ant colony-based multi-constrained QoS energy-saving routing and throughput optimization in wireless Ad-hoc networks简

In order to establish a route supporting multi-constrained quality of service（QoS）, increase network throughput and reduce network energy consumption, an improved ant colony-based multi-constrained QoS energy-saving routing algorithm（IAMQER） is proposed. The ant colony algorithm, as one of the available heuristic algorithms, is used to find the optimal route from source node to destination node. The proposed IAMQER algorithm, which is based on the analysis of local node information such as node queue length, node forwarding number of data packets and node residual energy, balances the relationship between the network throughput and the energy consumption, thus improving the performance of network in multi-constrained QoS routing. Simulation results show that this IAMQER algorithm can find the QoS route that reduce average energy consumption and improves network packet delivery ratio under the end-to-end delay and packet loss ratio constraints.     

Two algorithms for multi‐constrained optimal multicast routing

Multimedia applications, such as video‐conferencing and video‐on‐demand, often require quality of service (QoS) guarantees from the network, typically in the form of minimum bandwidth, maximum delay, jitter and packet loss constraints, among others. The problem of multicast routing subject to various forms of QoS constraints has been studied extensively. However, most previous efforts have focused on special situations where a single or a pair of constraints is considered. In general, routing under multiple constraints, even in the unicast case is an NP‐complete problem. We present in this paper two practical and efficient algorithms, called multi‐constrained QoS dependent multicast routing (M_QDMR) and (multicasting routing with multi‐constrained optimal path selection (M_MCOP)), for QoS‐based multicast routing under multiple constraints with cost optimization. We provide proof in the paper that our algorithms are correct. Furthermore, through extensive simulations, we illustrate the effectiveness and efficiency of our proposals and demonstrate their significant performance improvement in creating multicast trees with lower cost and higher success probability. Copyright © 2003 John Wiley & Sons, Ltd.     

Delay constraint multipath routing for wireless multimedia ad hoc networks

According to the disadvantages of real time and continuity for multimedia services in ad hoc networks, a delay constraint multipath routing protocol for wireless multimedia ad hoc networks, which can satisfy quality of service (QoS) requirement (QoS multipath optimized link state routing [MOLSR]), is proposed. The protocol firstly detects and analyzes the link delay among the nodes and collects the delay information as the routing metric by HELLO message and topology control message. Then, through using the improved multipath Dijkstra algorithm for path selection, the protocol can gain the minimum delay path from the source node to the other nodes. Finally, when the route is launched, several node‐disjoint or link‐disjoint multipaths will be built through the route computation. The simulation and test results show that QoS‐MOLSR is suitable for large and dense networks with heavy traffic. It can improve the real time and reliability for multimedia transmission in wireless multimedia ad hoc networks. The average end‐to‐end delay of QoS‐MOLSR is four times less than the optimized link state routing. Copyright © 2014 John Wiley & Sons, Ltd.     

A resource‐tuned QoS multicast routing protocol

This paper presents a novel framework for quality‐of‐service (QoS) multicast routing with resource allocation that represents QoS parameters, jitter delay, and reliability, as functions of adjustable network resources, bandwidth, and buffer, rather than static metrics. The particular functional form of QoS parameters depends on rate‐based service disciplines used in the routers. This allows intelligent tuning of QoS parameters as functions of allocated resources during the multicast tree search process, rather than decoupling the tree search from resource allocation. The proposed framework minimizes the network resource utilization while keeping jitter delay, reliability, and bandwidth bounded. This definition makes the proposed QoS multicast routing with resource allocation problem more general than the classical minimum Steiner tree problem. As an application of our general framework, we formulate the QoS multicast routing with resource allocation problem for a network consisting of generalized processor sharing nodes as a mixed‐integer quadratic program and find the optimal multicast tree with allocated resources to satisfy the QoS constraints. We then present a polynomial‐time greedy heuristic for the QoS multicast routing with resource allocation problem and compare its performance with the optimal solution of the mixed‐integer quadratic program. The simulation results reveal that the proposed heuristic finds near‐optimal QoS multicast trees along with important insights into the interdependency of QoS parameters and resources.     

Cross‐layer optimized routing in wireless sensor networks with duty cycle and energy harvesting

In this paper, we propose a cross‐layer optimized geographic node‐disjoint multipath routing algorithm, that is, two‐phase geographic greedy forwarding plus. To optimize the system as a whole, our algorithm is designed on the basis of multiple layers' interactions, taking into account the following. First is the physical layer, where sensor nodes are developed to scavenge the energy from environment, that is, node rechargeable operation (a kind of idle charging process to nodes). Each node can adjust its transmission power depending on its current energy level (the main object for nodes with energy harvesting is to avoid the routing hole when implementing the routing algorithm). Second is the sleep scheduling layer, where an energy‐balanced sleep scheduling scheme, that is, duty cycle (a kind of node sleep schedule that aims at putting the idle listening nodes in the network into sleep state such that the nodes will be awake only when they are needed), and energy‐consumption‐based connected k‐neighborhood is applied to allow sensor nodes to have enough time to recharge energy, which takes nodes' current energy level as the parameter to dynamically schedule nodes to be active or asleep. Third is the routing layer, in which a forwarding node chooses the next‐hop node based on 2‐hop neighbor information rather than 1‐hop. Performance of two‐phase geographic greedy forwarding plus algorithm is evaluated under three different forwarding policies, to meet different application requirements. Our extensive simulations show that by cross‐layer optimization, more shorter paths are found, resulting in shorter average path length, yet without causing much energy consumption. On top of these, a considerable increase of the network sleep rate is achieved. Copyright © 2014 John Wiley & Sons, Ltd.     

一个自组网中基于局部状态位置已知的分布式QoS路由算法

在分析自组网的单播QoS路由问题的基础上，提出了一种位置信息已知的利用局部状态信息进行路由选择的的分布式QoS路由算法——LILAGR算法。LILAGR路由算法的基本思想是逐段优化费用和尽快到达目的节点，即在决定节点之间是选择带宽约束费用最小的路径而各个决定节点则是按照贪婪地尽快到达目的节点的原则进行选择。仿真结果表明：LILAGR算法能够以适度的路由消息开销取得较高的路由成功率。此外，LILAGR算法具有可扩展性，可以应用于较大规模的自组网中。     

Secure multicast routing protocols in mobile ad‐hoc networks

A mobile ad‐hoc network (MANET) is a collection of autonomous nodes that communicate with each other by forming a multi‐hop radio network. Routing protocols in MANETs define how routes between source and destination nodes are established and maintained. Multicast routing provides a bandwidth‐efficient means for supporting group‐oriented applications. The increasing demand for such applications coupled with the inherent characteristics of MANETs (e.g., lack of infrastructure and node mobility) have made secure multicast routing a crucial yet challenging issue. Recently, several multicast routing protocols (MRP) have been proposed in MANETs. Depending on whether security is built‐in or added, MRP can be classified into two types: secure and security‐enhanced routing protocols, respectively. This paper presents a survey on secure and security‐enhanced MRP along with their security techniques and the types of attacks they can confront. A detailed comparison for the capability of the various routing protocols against some known attacks is also presented and analyzed. Copyright © 2013 John Wiley & Sons, Ltd.     

Adhoc-like routing in wired networks with genetic algorithms

Routing of packets in networks requires that a path be selected either dynamically while the packets are being forwarded, or statically (in advance) as in source routing from a source node to a destination. Quality of service (QoS) driven routing has been proposed using a protocol called the “Cognitive Packet Network” (CPN) which dynamically selects paths through a store and forward packet network so as to provide best effort QoS to route peer-to-peer connections. CPN operates very much as an adhoc protocol within a wired setting, and uses smart packets to select routes based on QoS requirements. We extend the path discovery process in CPN to include a genetic algorithm which can help discover new paths that may not have been discovered by smart packets. We describe how possible routes can “evolve” from prior knowledge, and then be selected based on “fitness” with respect to QoS. We detail the design of the algorithm and of its implementation, and report on resulting QoS measurements.     

Power and cost aware localized routing with guaranteed delivery in unit graph based ad hoc networks

In a localized routing algorithm, each node currently holding a message makes forwarding decision solely based on the position information about itself, its neighbors and destination. In a unit graph, two nodes can communicate if and only if the distance between them is no more than the transmission radius, which is the same for each node. This paper proposes localized routing algorithms, aimed at minimizing total power for routing a message or maximizing the total number of routing tasks that a network can perform before a partition. The algorithms are combinations of known greedy power and/or cost aware localized routing algorithms and an algorithm that guarantees delivery. A shortcut procedure is introduced in later algorithm to enhance its performance. Another improvement is to restrict the routing to nodes in a dominating set. These improvements require two‐hop knowledge at each node. The efficiency of proposed algorithms is verified experimentally by comparing their power savings, and the number of routing tasks a network can perform before a node loses all its energy, with the corresponding shortest weighted path algorithms and localized algorithms that use fixed transmission power at each node. Significant energy savings are obtained, and feasibility of applying power and cost‐aware localized schemes is demonstrated. Copyright © 2004 John Wiley & Sons, Ltd.     

A Novel Routing Protocol for Supporting QoS for Ad Hoc Mobile Wireless Networks

The main purposes of this article are to lessen the influence of the fastchanging network topology, rapidly varying bandwidth information, and the increasing size of routing tables onquality of service routing. Based on DSDV (Destination-Sequenced Distance-Vector) routing protocol formaintaining up-to-date routing information, the related research has to update routing tables when networktopology changes; moreover, the routing tables must be updated periodically even though the networktopology has not changed. To put emphasis on QoS routing, they also have to exchange routing tables by thetime of bandwidth information changes. Furthermore, the size of routing tables increases with the numberof mobile nodes; therefore, the precious wireless bandwidth is wasted on transmitting the large-scalerouting tables. In this article, we propose an on-demand-based QoS routing protocol to mitigate theseproblems and to achieve the QoS requirement. The goal of this article is to discover an optimal routewith minimum time delay for transmitting real-time data from a source node hop by hop to adestination node under some predefined constraints. Our contributions are as follows: our researchprovides a rigorous bandwidth definition and bandwidth application, a broad view of bandwidth calculationand reservation, minimizing the size of control packets and the number of control packet transmissions,and an efficient QoS routing protocol.     

无线网络中一种高QoS保证的路由协议研究

随着多媒体及实时应用的普及,在移动自组网中为业务流提供服务质量保证现已成为研究热点.提出一种在大规模移动自组网中提供服务质量保证的分段式路由协议.该协议采用直线逼近的方法,逐段建立满足带宽要求且延迟小的路径,并选择到源节点和目的节点连线距离最近的节点作为转发节点.通过分段、独立地维护路由,减小了路由维护的代价,提高了可扩展性.模拟结果表明该路由协议具有路由成功率高、路径短和延迟小等特点.     

QoS routing based on multi-class nodes for mobile ad hoc networks

In this paper, we present a new quality of service (QoS) routing protocol for mobile ad hoc networks (MANETs). Most of the existing routing protocols assume homogeneous nodes in MANETs, i.e., all nodes have the same communication capabilities and characteristics. However, in many ad hoc networks, nodes are not the same. Some nodes have longer transmission range, larger transmission bandwidth, and are more reliable and robust than other nodes. We take advantage of the non-homogeneous property to design more efficient QoS routing protocol. And node location information is used to aid routing. We also develop a new algorithm to calculate end-to-end bandwidth for a given path. Our QoS routing protocol contains end-to-end bandwidth calculation and bandwidth reservation. QoS route is discovered and setup only when it is needed. Extensive simulation studies demonstrate the good performance of the QoS routing protocol.     

一种安全的Ad Hoc On-demand路由协议

由于Ad Hoc网络固有的弱点,设计安全、有效的Ad Hoc路由协议是困难的.本文从新的角度设计了一个简单、安全的On-demand路由协议.在路径请求和响应阶段,源节点和目的节点的身份分别被隐藏,只有那些位于目的节点选择的最优路径上的节点可以获得完整的路由信息,从而产生有效的前向和反向路径.同时,一个公开的单向Hash函数可以利用隐藏的路由信息构建单向Hash链用于路由信息的认证,从而不需要预先的共享密钥.在一次路由计算中,只有源节点和目的节点需要进行一次非对称密码运算.     

The effects of shadow‐fading on QoS‐aware routing and admission control protocols designed for multi‐hop MANETs

Providing quality‐of‐service (QoS) assurances in a mobile ad hoc network (MANET) is difficult due to node mobility, contention for channel access, a lack of centralised coordination, and the unreliable nature of the wireless channel. QoS‐aware routing (QAR) and admission control (AC) protocols comprise two of the most important components of a system attempting to provide QoS guarantees in the face of the above‐mentioned difficulties. This paper presents a comparative study, utilising a realistic shadow fading channel, of the performance of several state‐of‐the‐art amalgamated QAR‐AC protocols, which are designed for providing throughput guarantees to applications. The advantages and drawbacks of their particular features are highlighted. For an environment where link quality varies rapidly, the results of the study highlight the ineffectiveness of previously‐proposed methods of relying merely on the success of route discovery to perform AC, of relying on the exceeding of the MAC layer retransmission count for link failure detection, of existing congestion detection schemes and of careful re‐admission of data sessions rather than fast re‐routing after shadowing‐induced link failures. Based on the lessons learnt, design guidelines for future QAR and AC protocols operating in a mobile shadow‐fading‐afflicted environment are presented. Copyright © 2010 John Wiley & Sons, Ltd.