Elsevier

Ad Hoc Networks

Volume 1, Issue 4, November 2003, Pages 405-421
Ad Hoc Networks

Energy efficient routing in ad hoc disaster recovery networks

https://doi.org/10.1016/S1570-8705(03)00041-6Get rights and content

Abstract

The terrorist attacks on September 11, 2001 have drawn attention to the use of wireless technology in order to locate survivors of structural collapse. We propose to construct an ad hoc network of wireless smart badges in order to acquire information from trapped survivors. We investigate the energy efficient routing problem that arises in such a network and show that since smart badges have very limited power sources and very low data rates, which may be inadequate in an emergency situation, the solution of the routing problem requires new protocols. The problem is formulated as an anycast routing problem in which the objective is to maximize the time until the first battery drains-out. We present iterative algorithms for obtaining the optimal solution of the problem. Then, we derive an upper bound on the network lifetime for specific topologies and describe a polynomial algorithm for obtaining the optimal solution in such topologies. Finally, numerical results regarding the upper bound and the algorithms are presented.

Introduction

The terrorist attacks on the World Trade Center and the Pentagon on September 11, 2001 have drawn ever-increasing attention to improving rescue efforts following a disaster. One of the technologies that can be effectively deployed during disaster recovery is wireless ad hoc networking [25]. For example, rescue forces can use a Mobile Ad Hoc Network (MANET) in the lack of fixed communication systems. Furthermore, a wireless sensor network can be quickly deployed following a chemical or biological attack in order to identify areas affected by the chemical/biological agents [2]. We propose another application of an ad hoc network, which can be used in order to gather information from trapped survivors of structural collapse.

There are various possible reasons for structural collapse. The most frequent reasons are earthquakes, terror attacks, structural problems, and missile attacks. Regardless of the reason, the consequences of a collapse are usually very tragic. For example, in 1995 alone, the Kobe earthquake resulted in the death of nearly 5500 people, 168 people were killed in the Oklahoma City bombing, and more than 500 people were killed in the collapse of the Sampoong department store in Seoul. Thus, the importance of improving rescue techniques requires no explanation.

There are a few techniques for locating survivors of structural collapse trapped in the rubble: fiber optic scopes, sensitive listening devices, seismic sensors, search-and-rescue dogs, etc. [11]. Moreover, during the rescue attempts in the World Trade Center disaster site, the Wireless Emergency Response Team (WERT) attempted to locate survivors through signals from their mobile phones [29].

We propose to extend these capabilities and to enable the location of survivors by acquiring information from their smart badges. Smart badges (a.k.a. RFID badges [30]) will gain increased popularity in the near future and will apparently be used in any modern office building [27]. Since the transmission range of a badge is very short and since rescue equipment can usually be deployed at the periphery of the disaster scene, there is a need to construct an ad hoc network connecting victims trapped in the debris to the rescuers. In such a network, the information acquired from the badges (such as last known location, body temperature, etc.) will be repeatedly routed through other badges to wireless receivers deployed in the disaster scene. The receivers will forward the information through wired or wireless links to a central unit.

In the coming years, smart badges will use a proprietary technology (e.g. [28]) or the new IEEE 802.15.4 standard for Low-Rate Wireless Personal Area Networks (LR-WPAN) [6], [17], [19]. Either way they will be simple devices with very low data rates and very limited power sources. These data rates and power sources are expected to be adequate for regular use. For example, the data rate of an IEEE 802.15.4 device will be 20, 40 or 250 Kb/s [6]. A smart badge based on this standard is expected to establish about 20 connections per day [27]. Thus, the average data rates are expected to be much lower than the possible data rate. Moreover, the duty cycle of such a device is expected to be less than 1%, thereby enabling a long battery life.

However, in an emergency network constructed after a collapse, which may connect thousands of nodes and may route critical information, the required data rates and the consumed energy may be much higher than in daily use. Thus, the low data rates and the limited power sources are a major constraint on the performance of an emergency network. Furthermore, in such a network depleting the battery of a node may have tragic results.

This paper focuses on energy efficient routing protocols for emergency networks of badges. We note that since wireless devices usually have a finite power supply, there is an increasing interest in research regarding energy conserving protocols (see Section 2). Thus, our network model is based on the model for energy conserving routing in a wireless sensor network presented by Chang and Tassiulas [8]. However, unlike a wireless sensor network in which the available bandwidth is usually sufficient, in the emergency network there is a strict bandwidth restriction along with a strict energy restriction. Hence, the solution of the problem calls for the development of new protocols.

We assume that since the proposed network will be composed of trapped survivors’ badges, the network topology and the requirements will be rather static. Therefore, our major interest is in distributed algorithms for quasi-static anycast routing in a network with stationary requirements and unchanging topology. The objective of the algorithms is to maximize the time until the first battery drains-out (i.e. to solve a max–min optimization problem). This objective function has been defined by Chang and Tassiulas [8] and although it is controversial when applied to MANETs or sensor networks, it is appropriate for an emergency network in which every node is critical.

In this paper we formulate the problem and present iterative algorithms for obtaining its optimal solution. These algorithms are based on the formulation of the problem as a concurrent max-flow problem [21] and the complexity of one of them is logarithmic in the network lifetime. We derive an upper bound on the network lifetime for specific topologies that is based on the new notion of non-max capacity cut. Then, a polynomial algorithm for obtaining the optimal solution in specific topologies is described. Finally, numerical results regarding the upper bound and the algorithms are presented.

The main contribution of this paper is the extension of the energy conserving routing model presented by Chang and Tassiulas [8] to a network in which some of the nodes have a very low data rate as well as a limited battery. Another contribution is the derivation of bounds on the network lifetime and the development of optimal algorithms, which can be implemented in a distributed manner.

This paper is organized as follows. In Section 2, we discuss related work and in Section 3, we present the model and formulate the routing problem. Algorithms for obtaining the solution of the problem and an upper bound on the network lifetime are introduced in Section 4. In Section 5, we present numerical results and in Section 6, we summarize the main results and discuss future research directions.

Section snippets

Related work

In 1998, Bambos [4] reviewed developments in power control in wireless networks and identified the need for minimum-power routing protocols. Since then, the issue of energy-conservation in ad hoc and sensor networks has attracted a vast amount of research (see for example, [14], [20], [26], and references therein). This research deals with all layers of the protocol stack and is mostly motivated by the fact that wireless devices usually have a very limited power supply. In particular, there is

Model and preliminaries

Consider the connected directed network graph G=(N,L). N will denote the collection of nodes {1,2,…,n}. A node could be a badge, a receiver (the collection of receivers is denoted by R), or the central unit (referred to as the destination and denoted by d). Recall that receivers are deployed at the periphery of the disaster scene (their role is to connect the badges network to the central unit).

The collection of the directional links will be denoted by L. We assume that since smart badges are

Algorithms and bounds

In this section, we present an equivalent formulation of Problem EER. This formulation is required in order to develop distributed algorithms. Then, iterative algorithms for obtaining the optimal solution of the problem are described. We also derive an upper bound on the network lifetime for specific topologies. Finally, we describe a polynomial algorithm for obtaining the optimal solution in these topologies.

Numerical results

The Iterative Algorithms (presented in Section 4.2) and the Non-max Capacity Algorithm (presented in Section 4.4) were implemented and tested on several representative cases. In addition, the upper bound on the network lifetime (presented in Section 4.3) was computed and compared to the optimal lifetime for a few network topologies. It was found that in a network with a single origin node, the Non-max Capacity Algorithm usually requires the lowest number of iterations. In a network with

Conclusions and future research

We have proposed to enable the formation of a network composed of smart badges in order to acquire information from survivors of structural collapse. The two main aspects that affect the performance of such a network are the limited batteries of the badges and their very low data rates (relatively to the requirements in a disaster scene).

Accordingly, an energy efficient routing problem in such a network has been formulated as an anycast routing problem. The problem has been formulated such that

Acknowledgements

We would like to thank Yaacov Bleiman for his invaluable advice and help. This research was supported by a grant from the Ministry of Science, Israel.

Gil Zussman received the B.Sc. degree in Industrial Engineering and Management and the B.A. degree in Economics (both summa cum laude) from the Technion––Israel Institute of Technology in 1995. He received the M.Sc. degree (summa cum laude) in Operations Research from Tel-Aviv University in 1999. He is currently working toward the Ph.D. degree in the Department of Electrical Engineering at the Technion. From 1995 to 1998, he served as an officer and an engineer in the Israel Defense Forces. His

References (39)

  • I.F. Akyildiz et al.

    Wireless sensor networks: a survey

    Computer Networks

    (2002)
  • J.E. Wieselthier et al.

    Resource management in energy-limited, bandwidth-limited, transceiver-limited wireless networks for session-based multicasting

    Computer Networks

    (2002)
  • R.K. Ahuja et al.

    Network Flows

    (1993)
  • B. Awerbuch, T. Leighton, Improved approximation algorithms for the multi-commodity flow problem and local competitive...
  • N. Bambos

    Toward power-sensitive network architectures in wireless communications: concepts, issues, and design aspects

    IEEE Personal Commun.

    (1998)
  • M. Bhardwaj, T. Garnett, A.P. Chandrakasan, Upper bounds on the lifetime of sensor networks, in: Proc. IEEE ICC’01,...
  • E. Callaway et al.

    Home networking with IEEE 802.15.4: a developing standard for low-rate wireless personal area networks

    IEEE Commun.

    (2002)
  • J.H. Chang, L. Tassiulas, Routing for maximum system lifetime in wireless ad-hoc networks, in: Proc. 37th Annual...
  • J.H. Chang, L. Tassiulas, Energy conserving routing in wireless ad-hoc networks, in: Proc. IEEE INFOCOM’00, March...
  • J.H. Chang et al.

    Fast approximate algorithms for maximum lifetime routing in wireless ad-hoc networks

  • C.F. Chiasserini et al.

    Energy efficient design of wireless ad hoc networks

  • Federal Emergency Management Agency (FEMA)––The National Urban Search and Rescue Response System. Documentation...
  • L.M. Feeney

    An energy consumption model for performance analysis of routing protocols for Mobile Ad Hoc Networks

    ACM/Kluwer Mobile Networks and Applications

    (2001)
  • A.V. Goldberg et al.

    A new approach to the maximum flow problem

    J. ACM

    (1988)
  • Energy-Aware Ad Hoc Wireless Networks

    IEEE Wireless Communications

    (2002)
  • J. Gomez, A.T. Campbell, M. Naghshineh, C. Bisdikian, Conserving transmission power in wireless ad hoc networks, in:...
  • O. Gunluk

    A new min-cut max-flow ratio for multicommodity flows

  • J.A. Gutierrez et al.

    IEEE 802.15.4: a developing standard for low-power low-cost wireless personal area networks

    IEEE Network

    (2001)
  • W.R. Heinzelman, A. Chandrakasan, H. Balakrishnan, Energy-efficient communication protocol for wireless microsensor...
  • Cited by (0)

    Gil Zussman received the B.Sc. degree in Industrial Engineering and Management and the B.A. degree in Economics (both summa cum laude) from the Technion––Israel Institute of Technology in 1995. He received the M.Sc. degree (summa cum laude) in Operations Research from Tel-Aviv University in 1999. He is currently working toward the Ph.D. degree in the Department of Electrical Engineering at the Technion. From 1995 to 1998, he served as an officer and an engineer in the Israel Defense Forces. His current research interests are in the area of ad hoc and sensor networks. In particular, he is interested in personal area networks, energy efficient routing, and medium access control protocols. He received the Knesset (Israeli Parliament) Award for distinguished students, the Best Student Paper Award at the IFIP-TC6 Networking 2002 Conference, and the IEEE Communications Magazine Best Paper Award at the OPNETWORK 2002 Conference.

    Adrian Segall received the B.Sc. and M.Sc. degrees in Electrical Engineering from the Technion, Israel Institute of Technology in 1965 and 1971, respectively, and the Ph.D. degree in Electrical Engineering with a Minor in Statistics from Stanford University in 1973. After serving active duty in the Israel Defense Forces, he joined in 1968 the Scientific Department of Israel’s Ministry of Defense. From 1973 to 1974 he was a Research Engineer at System Control Inc., Palo Alto, CA and a Lecturer at Stanford University. From 1974 to 1976 he was an Assistant Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology. From 1987 to 1998 he was on the faculty of the Department of Computer Science at the Technion. He is presently Benjamin Professor of Computer-Communication Networks in the Department of Electrical Engineering, Technion, Israel Institute of Technology. From 1982 to 1984 he was on leave with the IBM T.J. Watson Research Center, Yorktown Heights, NY. He held visiting positions with IBM, AT&T and Lucent Bell Labs. His current research interests are in the area of optical networks, wireless, sensor and ad hoc networks. He is an IEEE Fellow and has served in the past as Editor for Computer Communication Theory of the IEEE Transactions on Communications and Editor for the IEEE Information Theory Society Newsletter. He was selected as an IEEE delegate to the 1975 IEEE-USSR Information Theory Workshop, and is the recipient of the 1981 Miriam and Ray Klein Award for Outstanding Research and of the 1990 Taub Award in Computer Science. He is presently a Senior Editor for the IEEE Selected Areas in Communications journal.

    View full text