Energy-aware on-demand routing protocols for wireless ad hoc networks

Energy use is a crucial design concern in wireless ad hoc networks since wireless terminals are typically battery-operated. The design objectives of energy-aware routing are two folds: Selecting energy-efficient paths and minimizing the protocol overhead incurred for acquiring such paths. To achieve these goals simultaneously, we present the design of several on-demand energy-aware routing protocols. The key idea behind our design is to adaptively select the subset of nodes that are required to involve in a route-searching process in order to acquire a high residual-energy path and/or the degree to which nodes are required to participate in the process of searching for a low-power path in networks wherein nodes have transmission power adjusting capability. Analytical and simulation results are given to demonstrate the high performance of the designed protocols in energy-efficient utilization as well as in reducing the protocol overhead incurred in acquiring energy-efficient routes. Baoxian Zhang received his B.S., M.S., and Ph.D. degrees in Electrical Engineering from Northern Jiaotong University, Beijing, China in 1994, 1997, and 2000, respectively. From January 2001 to August 2002, he was working with Department of Electrical and Computer Engineering at Queen’s University in Kingston as a postdoctoral fellow. He is currently a research scientist with the School of Information Technology and Engineering (SITE) of University of Ottawa in Ottawa, Ontario, Canada. He has published over 40 refereed technical papers in international journals and conference proceedings. His research interests include routing algorithm and protocol design, QoS management, wireless ad hoc and sensor networks, survivable optical networks, multicast communications, and performance evaluation. He is a member of the IEEE. Hussein Mouftah joined the School of Information Technology and Engineering (SITE) of the University of Ottawa in September 2002 as a Canada Research Chair (Tier 1) Professor in Optical Networks. He has been with the Department of Electrical and Computer Engineering at Queen’s University (1979-2002), where he was prior to his departure a Full Professor and the Department Associate Head. He has three years of industrial experience mainly at Bell Northern Research of Ottawa, now Nortel Networks (1977-79). He has spent three sabbatical years also at Nortel Networks (1986-87, 1993-94, and 2000-01), always conducting research in the area of broadband packet switching networks, mobile wireless networks and quality of service over the optical Internet. He served as Editor-in-Chief of the IEEE Communications Magazine (1995-97) and IEEE Communications Society Director of Magazines (1998-99) and Chair of the Awards Committee (2002-2003). He is a Distinguished Speaker of the IEEE Communications Society since 2000. Dr. Mouftah is the author or coauthor of five books, 22 book chapters and more than 700 technical papers and 8 patents in this area. He is the recipient of the 1989 Engineering Medal for Research and Development of the Association of Professional Engineers of Ontario (PEO), and the Ontario Distinguished Researcher Award of the Ontario Innovation Trust. He is the joint holder of the Best Paper Award for a paper presented at SPECTS’2002, and the Outstanding Paper Award for papers presented at the IEEE HPSR’2002 and the IEEE ISMVL’1985. Also he is the joint holder of a Honorable Mention for the Frederick W. Ellersick Price Paper Award for Best Paper in the IEEE Communications Magazine in 1993. He is the recipient of the IEEE Canada (Region 7) Outstanding Service Award (1995). Also he is the recipient of the 2004 IEEE Communications Society Edwin Howard Armstrong Achievement Award, and the 2004 George S. Glinski Award for Excellence in Research of the Faculty of Engineering, University of Ottawa. Dr. Mouftah is a Fellow of the IEEE (1990) and Fellow of the Canadian Academy of Engineering (2003).     

无线Ad Hoc网络中功率感知路由协议的研究

能量节省是无线Ad Hoc网络中的一个研究重点.功率感知路由协议不但可以解决无线Ad Hoc网络的节能问题,同时还能够提高网络的性能.文章对目前提出的功率感知路由协议进行了分类,并分别进行了描述,最后指出了功率感知路由协议的未来研究方向.     

QoS routing in ad hoc wireless networks

The emergence of nomadic applications have generated much interest in wireless network infrastructures that support real-time communications. We propose a bandwidth routing protocol for quality-of-service (QoS) support in a multihop mobile network. The QoS routing feature is important for a mobile network to interconnect wired networks with QoS support (e.g., ATM, Internet, etc.). The QoS routing protocol can also work in a stand-alone multihop mobile network for real-time applications. This QoS routing protocol contains end-to-end bandwidth calculation and bandwidth allocation. Under such a routing protocol, the source (or the ATM gateway) is informed of the bandwidth and QoS available to any destination in the mobile network. This knowledge enables the establishment of QoS connections within the mobile network and the efficient support of real-time applications. In addition, it enables more efficient call admission control. In the case of ATM interconnection, the bandwidth information can be used to carry out intelligent handoff between ATM gateways and/or to extend the ATM virtual circuit (VC) service to the mobile network with possible renegotiation of QoS parameters at the gateway. We examine the system performance in various QoS traffic flows and mobility environments via simulation. Simulation results suggest distinct performance advantages of our protocol that calculates the bandwidth information. It is particularly useful in call admission control. Furthermore, “standby” routing enhances the performance in the mobile environment. Simulation experiments show this improvement     

Load balanced routing protocols for ad hoc mobile wireless networks - [Topics in ad hoc and sensor networks]

Mobile ad hoc networks are collections of mobile nodes that can dynamically form temporary networks without the need for pre-existing network infrastructure or centralized administration. These nodes can be arbitrarily located and can move freely at any given time. Hence, the network topology can change rapidly and unpredictably. Because wireless link capacities are usually limited, congestion is possible in MANETs. Hence, balancing the load in a MANET is important since nodes with high loads will deplete their batteries quickly, thereby increasing the probability of disconnecting or partitioning the network. This article discusses the various load metrics and summarizes the principles behind several existing load balanced ad hoc routing protocols. Finally, a qualitative comparison of the various load metrics and load balanced routing protocols is presented.     

Scalable routing protocols for mobile ad hoc networks

The growing interest in mobile ad hoc network techniques has resulted in many routing protocol proposals. Scalability issues in ad hoc networks are attracting increasing attention these days. We survey the routing protocols that address scalability. The routing protocols included in the survey fall into three categories: flat routing protocols; hierarchical routing approaches; GPS augmented geographical routing schemes. The article compares the scalability properties and operational features of the protocols and discusses challenges in future routing protocol designs     

Secure routing in mobile wireless ad hoc networks

We discuss several well known contemporary protocols aimed at securing routing in mobile wireless ad hoc networks. We analyze each of these protocols against requirements of ad hoc routing and in some cases identify fallibilities and make recommendations to overcome these problems so as to improve the overall efficacy of these protocols in securing ad hoc routing, without adding any significant computational or communication overhead.     

Scalable routing strategies for ad hoc wireless networks

We consider a large population of mobile stations that are interconnected by a multihop wireless network. The applications of this wireless infrastructure range from ad hoc networking (e.g., collaborative, distributed computing) to disaster recovery (e.g., fire, flood, earthquake), law enforcement (e.g., crowd control, search-and-rescue), and military (automated battlefield). Key characteristics of this system are the large number of users, their mobility, and the need to operate without the support of a fixed (wired or wireless) infrastructure. The last feature sets this system apart from existing cellular systems and in fact makes its design much more challenging. In this environment, we investigate routing strategies that scale well to large populations and can handle mobility. In addition, we address the need to support multimedia communications, with low latency requirements for interactive traffic and quality-of-service (QoS) support for real-time streams (voice/video). In the wireless routing area, several schemes have already been proposed and implemented (e.g., hierarchical routing, on-demand routing, etc.). We introduce two new schemes-fisheye state routing (FSR) and hierarchical state routing (HSR)-which offer some competitive advantages over the existing schemes. We compare the performance of existing and proposed schemes via simulation     

Robust position-based routing for wireless ad hoc networks

We consider a wireless ad hoc network composed of a set of wireless nodes distributed in a two dimensional plane. Several routing protocols based on the positions of the mobile hosts have been proposed in the literature. A typical assumption in these protocols is that all wireless nodes have uniform transmission regions modeled by unit disk centered at each wireless node. However, all these protocols are likely to fail if the transmission ranges of the mobile hosts vary due to natural or man-made obstacles or weather conditions. These protocols may fail because either some connections that are used by routing protocols do not exist, which effectively results in disconnecting the network, or the use of some connections causes livelocks. In this paper, we describe a robust routing protocol that tolerates up to roughly 40% of variation in the transmission ranges of the mobile hosts. More precisely, our protocol guarantees message delivery in a connected ad hoc network whenever the ratio of the maximum transmission range to the minimum transmission range is at most .     

Energy efficient routing protocols for mobile ad hoc networks

Although establishing correct and efficient routes is an important design issue in mobile ad hoc networks (MANETs), a more challenging goal is to provide energy efficient routes because mobile nodes' operation time is the most critical limiting factor. This article surveys and classifies the energy‐aware routing protocols proposed for MANETs. They minimize either the active communication energy required to transmit or receive packets or the inactive energy consumed when a mobile node stays idle but listens to the wireless medium for any possible communication requests from other nodes. Transmission power control approach and load distribution approach belong to the former category, and sleep/power‐down mode approach belongs to the latter category. While it is not clear whether any particular algorithm or a class of algorithms is the best for all scenarios, each protocol has definite advantages/disadvantages and is well suited for certain situations. The purpose of this paper is to facilitate the research efforts in combining the existing solutions to offer a more energy efficient routing mechanism. Copyright © 2003 John Wiley & Sons, Ltd.     

Mobility prediction and routing in ad hoc wireless networks

By exploiting non-random behaviors for the mobility patterns that mobile users exhibit, we can predict the future state of network topology and perform route reconstruction proactively in a timely manner. Moreover, by using the predicted information on the network topology, we can eliminate transmissions of control packets otherwise needed to reconstruct the route and thus reduce overhead. In this paper, we propose various schemes to improve routing protocol performances by using mobility prediction. We then evaluate the effectiveness of using mobility prediction via simulation. Copyright © 2001 John Wiley & Sons, Ltd.     

Minimum-power multicast routing in static ad hoc wireless networks

Wieselthier et al. (2000) proposed three greedy heuristics for Min-Power Asymmetric Broadcast Routing: SPT (shortest-path tree), MST (minimum spanning tree), and BIP (broadcasting incremental power). Wan et al. (2001) proved that SPT has an approximation ratio of at least (n/2) where n is the total number of nodes, and both MST and BIP have constant approximation ratios. Based on the approach of pruning, Wieselthier et al. also proposed three greedy heuristics for Min-Power Asymmetric Multicast Routing: P-SPT (pruned shortest-path tree), P-MST (pruned minimum spanning tree), and P-BIP (pruned broadcasting incremental power). In this paper, we first prove that the approximation ratios of these three heuristics are at least (n-1/2),n-1, and n-2-o(1), respectively. We then present constant-approxiation algorithms for Min-Power Asymmetric Multicast Routing. We show that any /spl rho/-approximation Steiner tree algorithm gives rise to a c/spl rho/-approximation heuristic for Min-Power Asymmetric Multicast Routing, where c is a constant between 6 and 12. In particular, the Takahashi-Matsuyama Steiner tree heuristic leads to a heuristic called SPF (shortest-path first), which has an approximation ratio of at most 2c. We also present another heuristic, called MIPF (minimum incremental path first), for Min-Power Asymmetric Multicast Routing and show that its approximation ratio is between (13/3) and 2c. Both SPF and MIPF can be regarded as an adaptation of MST and BIP, respectively, in a different manner than pruning. Finally, we prove that any /spl rho/-approximation Steiner tree algorithm also gives rise to a 2/spl rho/-approximation algorithm for Min-Power Symmetric Multicast Routing.     

QoS routing for wireless ad hoc networks: problems, algorithms, and protocols

QoS routing plays an important role for providing QoS in wireless ad hoc networks. The goals of QoS routing are in general twofold: selecting routes with satisfied QoS requirement(s), and achieving global efficiency in resource utilization. In this article we first discuss some key design considerations in providing QoS routing support, and present a review of previous work addressing the issue of route selection subject to QoS constraint(s). We then devise an on-demand delay-constrained unicast routing protocol. Various strategies are employed in the protocol to reduce the communication overhead in acquiring cost-effective delay-constrained routes. Simulation results are used to verify our expectation of the high performance of the devised protocol. Finally, we discuss some possible future directions for providing efficient QoS routing support in wireless ad hoc networks.     

3D geographical routing protocols in wireless ad hoc and sensor networks: an overview

Wireless Networks - Geographical routing is a prominent area of research in wireless networks where route establishment is based on known locations of wireless nodes. The location may be an exact...     

Interference aware cooperative routing for wireless ad hoc networks

In this paper, we propose a cooperative approach for routing in wireless ad hoc networks. Our solution improves the interference distribution in the network, with an immediate positive impact on the throughput performance and energy efficiency. In determining new routes, we consider not only the cost associated with the current route, but also the potential interference impact of the route on the neighboring nodes.We use this cooperative approach to determine routes for CDMA ad hoc networks, which are known to be severely limited in performance by the near–far effect. Our simulation results using cooperative routing show an improvement in throughput of up to 60% compared to the classic minimum energy routing approach. This improvement is achieved at the expense of only a slight increase in the average energy per bit transmission for an end-to-end path.     

Scalable geographic routing algorithms for wireless ad hoc networks

The design of efficient routing protocols for dynamical changing network topologies is a crucial part of building power-efficient and scalable ad hoc wireless networks. If position information is available due to GPS or some kind of relative positioning technique, a promising approach is given by geographic routing algorithms, where each forwarding decision is based on the positions of current, destination, and possible candidate nodes in vicinity only. About 15 years ago heuristic greedy algorithms were proposed, which in order to provide freedom from loops might fail even if there is a path from source to destination. In recent years planar graph traversal has been investigated as one possible strategy to recover from such greedy routing failures. This article provides a tutorial for this class of geographic routing algorithms, and discusses recent improvements to both greedy forwarding and routing in planar graphs.     

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.     

Low-cost routing in selfish and rational wireless ad hoc networks

Numerous routing protocols have been proposed for wireless networks. A common assumption made by the majority of these protocols is that each wireless node will follow the prescribed protocol without any deviation. This may not be true in practice since wireless nodes could be owned by users who perform in their own interests. We then have to design routing protocols that still work properly even for networks composed of selfish nodes. In this paper, we propose a unicast routing protocol to address this issue under the assumption that all networking nodes are rational. Here, a node is rational if it always chooses a strategy that maximizes its benefit. We assume that each node has a privately known cost of relaying a unit of data for other nodes. In our protocol, each wireless node has to declare a cost for forwarding a unit of data. When a node wants to send data to the access point, it first computes the least cost path to the access point and then computes a payment to each node on this path. We present a pricing mechanism such that the profit of each relay node is maximized when it declares its true cost. We also give a time optimal method to compute the payment in a centralized manner. We then discuss in detail how to implement the routing protocol in the distributed manner. We conduct extensive simulations to study the ratio of the total payment over the total cost incurred by all relay nodes. We find that this ratio is small in practice. Our protocol works when the wireless nodes will not collude and we show that no truthful mechanism can avoid the collusion of any pair of two nodes. We also give a truthful mechanism when a node only colludes with its neighbors.     

Energy efficient broadcast routing in static ad hoc wireless networks

In this paper, we discuss energy efficient broadcast in ad hoc wireless networks. The problem of our concern is: given an ad hoc wireless network, find a broadcast tree such that the energy cost of the broadcast tree is minimized. Each node in the network is assumed to have a fixed level of transmission power. We first prove that the problem is NP-hard and propose three heuristic algorithms, namely, shortest path tree heuristic, greedy heuristic, and node weighted Steiner tree-based heuristic, which are centralized algorithms. The approximation ratio of the node weighted Steiner tree-based heuristic is proven to be (1 + 2 ln(n - 1)). Extensive simulations have been conducted and the results have demonstrated the efficiency of the proposed algorithms.