Saturday, December 4, 2010

Energy efficient routing in ad hoc disaster recovery networks

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 and 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.;u=12376;u=38089;u=41872;u=120559;u=50980;u=62976;u=49943;u=26854;u=47827;u=80625;u=44130;u=96559;u=164313;u=86655;u=51837