Minimum Coverage Breach and Maximum Network Lifetime in Wireless Sensor Networks

Published on Dec 1, 2007
· DOI :10.1109/GLOCOM.2007.215
Chen Wang5
Estimated H-index: 5
(THU: Tsinghua University),
My T. Thai40
Estimated H-index: 40
(UF: University of Florida)
+ 2 AuthorsWeili Wu37
Estimated H-index: 37
(UTD: University of Texas at Dallas)
Sources
Abstract
Network lifetime is a critical issue in Wireless Sensor Networks. It is possible to extend network lifetime by organizing the sensors into a number of sensor covers. However, with the limited bandwidth, coverage breach (i.e, targets that are not covered) can occur if the number of available time-slots/channels is less than the number of sensors in a sensor cover. In this paper, we study a joint optimization problem in which the objective is to minimize the coverage breach as well as to maximize the network lifetime. We show a "trade-off" scheme by presenting two strongly related models, which aim to tradeoffs between the two conflicting objectives. The main approach of our models is organizing sensors into non-disjoint sets, which is different from the current most popular approach and can gain longer network lifetime as well as less coverage breach. We proposed two algorithms for the first model based on linear programming and greedy techniques, respectively. Then we transform these algorithms to solve the second model by revealing the strong connection between the models. Through numerical simulation, we showed the good performance of our algorithms and the pictures of the tradeoff scheme in variant scenarios, which coincide with theoretical analysis very well. It is also showed that our algorithms could obtain less breach rate than the one proposed in [2].
📖 Papers frequently viewed together
2005INFOCOM: International Conference on Computer Communications
4 Authors (Mihaela Cardei, ..., Weili Wu)
891 Citations
808 Citations
955 Citations
References11
Newest
#1Mihaela Cardei (FAU: Florida Atlantic University)H-Index: 28
#2Ding-Zhu Du (UMN: University of Minnesota)H-Index: 62
A critical aspect of applications with wireless sensor networks is network lifetime. Battery-powered sensors are usable as long as they can communicate captured data to a processing node. Sensing and communications consume energy, therefore judicious power management and scheduling can effectively extend operational time. To monitor a set of targets with known locations when ground access in the monitored area is prohibited, one solution is to deploy the sensors remotely, from an aircraft. The l...
808 CitationsSource
Mar 13, 2005 in INFOCOM (International Conference on Computer Communications)
#1Maggie X. Cheng (MU: University of Missouri)H-Index: 20
#2Lu Ruan (Iowa State University)H-Index: 18
Last. Weili WuH-Index: 37
view all 3 authors...
This paper addresses the coverage breach problem in wireless sensor networks with limited bandwidths. In wireless sensor networks, sensor nodes are powered by batteries. To make efficient use of battery energy is critical to sensor network lifetimes. When targets are redundantly covered by multiple sensors, especially in stochastically deployed sensor networks, it is possible to save battery energy by organizing sensors into mutually exclusive subsets and alternatively activating only one subset...
107 CitationsSource
Mar 13, 2005 in INFOCOM (International Conference on Computer Communications)
#1Mihaela Cardei (FAU: Florida Atlantic University)H-Index: 28
#2My T. Thai (FAU: Florida Atlantic University)H-Index: 40
Last. Weili WuH-Index: 37
view all 4 authors...
A critical aspect of applications with wireless sensor networks is network lifetime. Power-constrained wireless sensor networks are usable as long as they can communicate sensed data to a processing node. Sensing and communications consume energy, therefore judicious power management and sensor scheduling can effectively extend network lifetime. To cover a set of targets with known locations when ground access in the remote area is prohibited, one solution is to deploy the sensors remotely, from...
891 CitationsSource
#1Piotr Berman (PSU: Pennsylvania State University)H-Index: 45
#2Gruia Calinescu (IIT: Illinois Institute of Technology)H-Index: 26
Last. Alexander Zelikovsky (GSU: Georgia State University)H-Index: 46
view all 4 authors...
Optimizing the energy consumption in wireless sensor networks has recently become the most important performance objective. We assume the sensor network model in which sensors can interchange idle and active modes. Given monitoring regions, battery life and energy consumption rate for each sensor, we formulate the problem of maximizing sensor network lifetime, i.e., time during which the monitored area is (partially or fully) covered. Our contributions include (1) an efficient data structure to ...
191 CitationsSource
#1Vijay Raghunathan (UCLA: University of California, Los Angeles)H-Index: 34
#2Curt Schurgers (UCLA: University of California, Los Angeles)H-Index: 25
Last. Mani SrivastavaH-Index: 108
view all 4 authors...
This article describes architectural and algorithmic approaches that designers can use to enhance the energy awareness of wireless sensor networks. The article starts off with an analysis of the power consumption characteristics of typical sensor node architectures and identifies the various factors that affect system lifetime. We then present a suite of techniques that perform aggressive energy optimization while targeting all stages of sensor network design, from individual nodes to the entire...
1,548 CitationsSource
#1Ian F. Akyildiz (Georgia Institute of Technology)H-Index: 131
#2Weilian Su (Georgia Institute of Technology)H-Index: 11
Last. Erdal Cayirci (Georgia Institute of Technology)H-Index: 17
view all 4 authors...
The advancement in wireless communications and electronics has enabled the development of low-cost sensor networks. The sensor networks can be used for various application areas (e.g., health, military, home). For different application areas, there are different technical issues that researchers are currently resolving. The current state of the art of sensor networks is captured in this article, where solutions are discussed under their related protocol stack layer sections. This article also po...
12.4k CitationsSource
#1Sasha Slijepcevic (UCLA: University of California, Los Angeles)H-Index: 6
#2Miodrag PotkonjakH-Index: 77
Wireless sensor networks have emerged recently as an effective way of monitoring remote or inhospitable physical environments. One of the major challenges in devising such networks lies in the constrained energy and computational resources available to sensor nodes. These constraints must be taken into account at all levels of the system hierarchy. The deployment of sensor nodes is the first step in establishing a sensor network. Since sensor networks contain a large number of sensor nodes, the ...
955 CitationsSource
Apr 1, 2001 in SIGCOMM (ACM Special Interest Group on Data Communication)
#1Alberto E. CerpaH-Index: 25
#2Jeremy ElsonH-Index: 29
Last. Jerry Zhao (ISI: Information Sciences Institute)H-Index: 10
view all 6 authors...
As new fabrication and integration technologies reduce the cost and size of micro-sensors and wireless interfaces, it becomes feasible to deploy densely distributed wireless networks of sensors and actuators. These systems promise to revolutionize biological, earth, and environmental monitoring applications, providing data at granularities unrealizable by other means. In addition to the challenges of miniaturization, new system architectures and new network algorithms must be developed to transf...
947 CitationsSource
#1Luca Benini (UNIBO: University of Bologna)H-Index: 114
#2Gabriella Castelli (Polytechnic University of Turin)H-Index: 14
Last. R. Scarsi (Polytechnic University of Turin)H-Index: 14
view all 6 authors...
In this paper, we introduce a discrete-time model for the complete power supply sub-system that closely approximates the behavior of its circuit-level (i.e., HSpice), continuous-time counterpart. The model is abstract and efficient enough to enable event-driven simulation of digital systems described at a very high level of abstraction and that include, among their components, also the power supply. Therefore, it can be successfully used for the purpose of battery life-time estimation during des...
141 CitationsSource
Aug 1, 1999 in MOBICOM (ACM/IEEE International Conference on Mobile Computing and Networking)
#1Deborah Estrin (ISI: Information Sciences Institute)H-Index: 133
#2Ramesh Govindan (ISI: Information Sciences Institute)H-Index: 102
Last. Satish K.S. Kumar (ISI: Information Sciences Institute)H-Index: 16
view all 4 authors...
Networked sensors-those that coordinate amongst themselves to achieve a larger sensing task-will revolutionize information gathering and processing both in urban environments and in inhospitable terrain. The sheer numbers of these sensors and the expected dynamics in these environments present unique challenges in the design of unattended autonomous sensor networks. These challenges lead us to hypothesize that sensor network coordination applications may need to be structured differently from tr...
2,685 CitationsSource
Cited By39
Newest
#1Raffaele Cerulli (UNISA: University of Salerno)H-Index: 17
#2Ciriaco D’Ambrosio (UNISA: University of Salerno)H-Index: 10
Last. Francesco Palmieri (UNISA: University of Salerno)H-Index: 38
view all 4 authors...
In wireless sensor networks applications involving a huge number of sensors, some of the sensor devices may result to be redundant. As a consequence, the simultaneous usage of all the sensors may lead to a faster depletion of the available energy and to a shorter network lifetime. In this context, one of the well-known and most important problems is Maximum Network Lifetime Problem (MLP). MLP consists in finding non-necessarily disjoint subsets of sensors (covers), which are autonomously able to...
Source
#1Francesco Carrabs (UNISA: University of Salerno)H-Index: 11
#2Raffaele Cerulli (UNISA: University of Salerno)H-Index: 17
Last. Andrea Raiconi (UNISA: University of Salerno)H-Index: 10
view all 4 authors...
We face the problem of scheduling optimally the activities in a wireless sensor network in order to ensure that, in each instant of time, the activated sensors can monitor all points of interest (targets) and route the collected information to a processing facility. Each sensor is allocated to a role, depending on whether it is actually used to monitor the targets, to forward information or kept idle, leading to different battery consumption ratios. We propose a column generation algorithm that ...
14 CitationsSource
#1Francesco Carrabs (UNISA: University of Salerno)H-Index: 11
#2Carmine Cerrone (UNIMOL: University of Molise)H-Index: 9
Last. Andrea Raiconi (UNISA: University of Salerno)H-Index: 10
view all 4 authors...
We aim to maximize the operational time of a network of sensors, which are used to monitor a predefined set of target locations. The classical approach proposed in the literature consists in individuating subsets of sensors (covers) that can individually monitor the targets, and in assigning appropriate activation times to each cover. Indeed, since sensors may belong to multiple covers, it is important to make sure that their overall battery capacities are not violated. We consider additional co...
7 CitationsSource
#1Francesco Carrabs (UNISA: University of Salerno)H-Index: 11
#2Raffaele Cerulli (UNISA: University of Salerno)H-Index: 17
Last. Andrea Raiconi (UNISA: University of Salerno)H-Index: 10
view all 4 authors...
The aim of the Connected Maximum Lifetime Problem is to define a schedule for the activation intervals of the sensors deployed inside a region of interest, such that at all times the activated sensors can monitor a set of interesting target locations and route the collected information to a central base station, while maximizing the total amount of time over which the sensor network can be operational. Complete or partial coverage of the targets are taken into account. To optimally solve the pro...
11 CitationsSource
#1Yi Hong (BIPT: Beijing Institute of Petrochemical Technology)H-Index: 8
#2Deying Li (RUC: Renmin University of China)H-Index: 21
Last. Alade O. Tokuta (NCCU: North Carolina Central University)H-Index: 12
view all 6 authors...
In camera sensor networks (CSNs), the target coverage problem is of special importance since a sensor with different viewing directions captures distinct views for the same target. Furthermore, mission-driven monitoring applications in CSNs usually have special network lifetime requirements in which the limited battery lifetime of sensors probably can not sustain for full coverage. In this paper, based on effective-sensing model, we address three new coverage problems in mission-driven camera se...
4 CitationsSource
#1Francesco Carrabs (UNISA: University of Salerno)H-Index: 11
#2Raffaele Cerulli (UNISA: University of Salerno)H-Index: 17
Last. Andrea Raiconi (UNISA: University of Salerno)H-Index: 10
view all 4 authors...
In this work, we consider a scenario in which we have to monitor some locations of interest in a geographical area by means of a wireless sensor network. Our aim is to keep the network operational for as long as possible, while preventing certain sensors from being active simultaneously, since they would interfere with one another causing data loss, need for retransmissions and overall affecting the throughput and efficiency of the network. We propose an exact approach based on column generation...
8 CitationsSource
#1Sasmita Dash (KIIT: KIIT University)H-Index: 2
Last. Amulya Ratna Swain (KIIT: KIIT University)H-Index: 8
view all 4 authors...
Wireless Sensor Network (WSN) mainly composed of a number of sensor nodes whose prime responsibility is to sense various events from the surrounding, do the processing on top of it and finally propagate the meaningful information to the observer through multiple intermediate nodes. Area coverage is one of the issues in WSN that guarantees the selected active nodes among all the deployed nodes should cover each point of the deployed area. The objective of complete area coverage is to find out red...
2 CitationsSource
#1Anxing Shan (Hangzhou Dianzi University)H-Index: 2
#2Xianghua Xu (Hangzhou Dianzi University)H-Index: 12
Last. Zongmao Cheng (Hangzhou Dianzi University)H-Index: 3
view all 3 authors...
Sensing coverage is a fundamental problem in wireless sensor networks (WSNs), which has attracted considerable attention. Conventional research on this topic focuses on the 0/1 coverage model, which is only a coarse approximation to the practical sensing model. In this paper, we study the target coverage problem, where the objective is to find the least number of sensor nodes in randomly-deployed WSNs based on the probabilistic sensing model. We analyze the joint detection probability of target ...
28 CitationsSource
#2Aron Laszka (Vandy: Vanderbilt University)H-Index: 19
#3Yevgeniy Vorobeychik (Vandy: Vanderbilt University)H-Index: 29
Last. Xenofon Koutsoukos (Vandy: Vanderbilt University)H-Index: 47
view all 4 authors...
In networked systems, monitoring devices such as sensors are typically deployed to monitor various target locations. Targets are the points in the physical space at which events of some interest, such as random faults or attacks, can occur. Most often, these devices have limited energy supplies, and they can operate for a limited duration. As a result, energy-efficient monitoring of various target locations through a set of monitoring devices with limited energy supplies is a crucial problem in ...
2 Citations
#1Zehui Xiong (HUST: Huazhong University of Science and Technology)H-Index: 23
#2Bang Wang (HUST: Huazhong University of Science and Technology)H-Index: 25
In this paper, we study the problem of minimizing the network coverage breach in a rechargeable wireless sensor network (RWSN). Due to the node density and charging capability constraint, it may happen that a RWSN cannot provide required area coverage some time, yet it may recover later on after obtaining enough recharged energy. To minimize the coverage breach, we propose a family of sensor scheduling algorithms, each of which uses an utility function to greedily choose an active node in each s...
1 CitationsSource