Achieving minimum coverage breach under bandwidth constraints in wireless sensor networks

Published on Mar 13, 2005 in INFOCOM (International Conference on Computer Communications)
· DOI :10.1109/INFCOM.2005.1498547
Maggie X. Cheng20
Estimated H-index: 20
(MU: University of Missouri),
Lu Ruan18
Estimated H-index: 18
(Iowa State University),
Weili Wu37
Estimated H-index: 37
Sources
Abstract
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 at any time. Active nodes are responsible for sensing, computing and communicating. While the coverage of each subset is an important metric for sensor organization, the size of each subset also plays an important role in sensor network performance because when active sensors periodically send data to base stations, contention for channel access must be considered. The number of available channels imposes a limit on the cardinality of each subset. Coverage breach happens when a subset of sensors cannot completely cover all the targets. To make efficient use of both energy and bandwidth with a minimum coverage breach is the goal of sensor network design. This paper presents the minimum breach problem using a mathematical model, studies the computational complexity of the problem, and provides two approximate heuristics. Effects of increasing the number of channels and increasing the number of sensors on sensor network coverage are studied through numerical simulations. Overall, the simulation results reveal that when the number of sensors increases, network lifetimes can be improved without loss of network coverage if there is no bandwidth constraint; with bandwidth constraints, network lifetimes may be improved further at the cost of coverage breach.
📖 Papers frequently viewed together
2 Authors
808 Citations
2005INFOCOM: International Conference on Computer Communications
4 Authors (Mihaela Cardei, ..., Weili Wu)
891 Citations
2001
2 Authors
955 Citations
References19
#1Himanshu Gupta (SUNY: State University of New York System)H-Index: 34
#2Zongheng Zhou (SUNY: State University of New York System)H-Index: 6
Last. Quinyi Gu (SUNY: State University of New York System)H-Index: 2
view all 4 authors...
Spatial query execution is an essential functionality of a sensor network, where a query gathers sensor data within a specific geographic region. Redundancy within a sensor network can be exploited to reduce the communication cost incurred in execution of such queries. Any reduction in communication cost would result in an efficient use of the battery energy, which is very limited in sensors. One approach to reduce the communication cost of a query is to self-organize the network, in response to...
401 CitationsSource
#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
#1Stefano Basagni (U of O: University of Ottawa)H-Index: 7
#2Marco Conti (FAU: Florida Atlantic University)H-Index: 3
Last. Ivan Stojmenovic (U of O: University of Ottawa)H-Index: 83
view all 4 authors...
In this chapter, area-based methods are reclassified within other groups, whereas neighbor-knowledge methods are divided into clustering-based, selecting forwarding neighbors, and internal-node-based methods. We present a comprehensive taxonomy of broadcasting schemes with the one-to-all model in mind (the other models can similarly be considered).
91 CitationsSource
#1Ting Yan (UVA: University of Virginia)H-Index: 17
#2Tian He (UVA: University of Virginia)H-Index: 75
Last. John A. Stankovic (UVA: University of Virginia)H-Index: 121
view all 3 authors...
For many sensor network applications such as military surveillance, it is necessary to provide full sensing coverage to a security-sensitive area while at the same time minimizing energy consumption and extending system lifetime by leveraging the redundant deployment of sensor nodes. It is also preferable for the sensor network to provide differentiated surveillance service for various target areas with different degrees of security requirements. In this paper, we propose a differentiated survei...
499 CitationsSource
#1Himanshu Gupta (SUNY: State University of New York System)H-Index: 34
#2Samir R. Das (SUNY: State University of New York System)H-Index: 61
Last. Quinyi Gu (SUNY: State University of New York System)H-Index: 2
view all 3 authors...
Spatial query execution is an essential functionality of a sensor network, where a query gathers sensor data within a specific geographic region. Redundancy within a sensor network can be exploited to reduce the communication cost incurred in execution of such queries. Any reduction in communication cost would result in an efficient use of the battery energy, which is very limited in sensors. One approach to reduce the communication cost of a query is to self-organize the network, in response to...
268 CitationsSource
#1Xiang-Yang Li (IIT: Illinois Institute of Technology)H-Index: 88
#2Peng-Jun Wan (IIT: Illinois Institute of Technology)H-Index: 59
Last. Ophir Frieder (IIT: Illinois Institute of Technology)H-Index: 54
view all 3 authors...
Sensor networks pose a number of challenging conceptual and optimization problems such as location, deployment, and tracking. One of the fundamental problems in sensor networks is the calculation of the coverage. In Meguerdichian et al. (2001), it is assumed that the sensor has uniform sensing ability. We provide efficient distributed algorithms to optimally solve the best-coverage problem raised in the above-mentioned article. In addition, we consider a more general sensing model: the sensing a...
469 CitationsSource
Nov 7, 2002 in INFOCOM (International Conference on Computer Communications)
#1M. Bhardwaj (MIT: Massachusetts Institute of Technology)H-Index: 12
#2Anantha P. Chandrakasan (MIT: Massachusetts Institute of Technology)H-Index: 127
A key challenge in ad-hoc, data-gathering, wireless sensor networks is achieving a lifetime of several years using nodes that carry merely hundreds of joules of stored energy. We explore the fundamental limits of energy-efficient collaborative data-gathering by deriving upper bounds on the lifetime of increasingly sophisticated sensor networks.
527 CitationsSource
#1Di Tian (U of O: University of Ottawa)H-Index: 5
#2Nicolas D. Georganas (U of O: University of Ottawa)H-Index: 27
In wireless sensor networks that consist of a large number of low-power, short-lived, unreliable sensors, one of the main design challenges is to obtain long system lifetime, as well as maintain sufficient sensing coverage and reliability. In this paper, we propose a node-scheduling scheme, which can reduce system overall energy consumption, therefore increasing system lifetime, by turning off some redundant nodes. Our coverage-based off-duty eligibility rule and backoff-based node-scheduling sc...
1,073 CitationsSource
#1Mihaela Cardei (UMN: University of Minnesota)H-Index: 28
#2David MacCallum (UMN: University of Minnesota)H-Index: 4
Last. Ding-Zhu Du (UMN: University of Minnesota)H-Index: 62
view all 7 authors...
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 the operational time. One important class of wireless sensor applications of deployment of large number of sensors in an area for environmental monitoring. The data collected by the sensors is s...
221 CitationsSource
#1Seapahn MegerianH-Index: 10
#2Farinaz Koushanfar (University of California, Berkeley)H-Index: 61
Last. Miodrag PotkonjakH-Index: 77
view all 5 authors...
Wireless ad hoc sensor networks have the potential to provide the missing interface between the physical world and the Internet, thus impacting a large number of users. This connection will enable computational treatments of the physical world in ways never before possible. In this far reaching scenario, Quality of Service can be expressed in terms of accuracy and/or latency of observing events and the overall state of the physical world. Consequently, one of the fundamental problems in sensor n...
175 CitationsSource
Cited By107
#1Pooja ChaturvediH-Index: 4
#2A. K. Daniel (Madan Mohan Malaviya University of Technology)H-Index: 7
Source
#1Gaurav Srivastava (University of Hyderabad)H-Index: 2
#2Pandiri Venkatesh (University of Hyderabad)H-Index: 4
Last. Alok Singh (University of Hyderabad)H-Index: 22
view all 3 authors...
Cover scheduling problem in wireless sensor networks (WSN-CSP) aims to find a schedule of covers which minimizes the longest continuous duration of time for which no sensor in the network is able to monitor a target. This problem arises in those sensing environments which permit the coverage breach, i.e., at any instant of time, all targets need not be monitored. The coverage breach may occur owing to either technical restrictions or intentionally. It is an $\mathcal {NP}-hard problem. This p... 2 CitationsSource #1Zhao Zhang (ZJNU: Zhejiang Normal University)H-Index: 13 #2Zaixin Lu (Washington State University Vancouver)H-Index: 13 Last. Ding-Zhu Du (UTD: University of Texas at Dallas)H-Index: 62 view all 5 authors... Many applications of wireless sensor networks require a quality of service including coverage and connectivity. However, both coverage and connectivity may be lost due to failure of sensors, in which case some holes appear. To heal holes, a hybrid wireless sensor system with mobile sensors has been proposed in the literature. Redundant mobile sensors can move to heal holes. Limited by energy supply, the largest distance that a mobile sensor can move cannot be too large. Such a consideration call... 2 CitationsSource #1Abdullah Al Zishan (BUET: Bangladesh University of Engineering and Technology)H-Index: 2 #2Imtiaz Karim (BUET: Bangladesh University of Engineering and Technology)H-Index: 3 Last. Ashikur Rahman (BUET: Bangladesh University of Engineering and Technology)H-Index: 12 view all 4 authors... Abstract We address “heterogeneous coverage” in visual sensor networks where coverage requirements of some randomly deployed targets vary from target to target. The main objective is to maximize the coverage of all the targets to achieve their respective coverage requirement by activating minimal sensors. The problem can be viewed as an interesting variation of the classical Max-Min problem (i.e., Maximum Coverage with Minimum Sensors (MCMS)). Therefore, we study the existing Integer Linear Prog... 4 CitationsSource #1J. Roselin (Anna University)H-Index: 1 #2P. Latha (Government College)H-Index: 3 Last. S. Benitta (Anna University)H-Index: 1 view all 3 authors... Wireless Sensor Network (WSN) is an emerging technology that is gaining much importance owing to its immense contribution in various day-to-day applications. A sensor is battery-operated, unattended low-cost device with limited computing, communication and storage capabilities. Thus the network lifetime has become the key characteristic for evaluating sensor networks in an application-specific way. There are certain approaches in literature which consider the lifetime maximization problem. Howev... 41 CitationsSource #1ManjuH-Index: 5 #2Satish Chand (JNU: Jawaharlal Nehru University)H-Index: 15 Last. Bijendra KumarH-Index: 11 view all 3 authors... In order to fulfill the coverage requirement, Maximum Network Lifetime Problem (MLP) is to maximize the network lifetime while providing full coverage over a predefined set of targets. There is a variant of coverage problem called α-coverage, where a fraction of targets allowed to be left uncovered to provide partial coverage. This variant of coverage is presented by Maximum Network α-Lifetime Problem (α-MLP) that is the special case of classical MLP. During α-coverage, there has been no choice ... 8 CitationsSource #1Alok Singh (University of Hyderabad)H-Index: 22 #2Andr RossiH-Index: 3 Last. Marc Sevaux (CNRS: Centre national de la recherche scientifique)H-Index: 23 view all 3 authors... Due to increasing threat perception and cheap availability of multimedia technologies, camera sensor networks are becoming more and more popular these days. Camera sensor networks pose some unique challenges in addition to the usual difficulties associated with any directional sensor network. This paper addresses the problem of maximizing the network lifetime in camera sensor networks under the full and the partial target coverage models. In the full target coverage model, all the targets are as... 6 CitationsSource #1Zhao Zhang (ZJNU: Zhejiang Normal University)H-Index: 13 #2James K V Willson (UTD: University of Texas at Dallas)H-Index: 78 Last. Ding-Zhu Du (UTD: University of Texas at Dallas)H-Index: 62 view all 6 authors... Energy efficiency is an important issue in the study of wireless sensor networks. Given a set of targets and a set of sensors with bounded lifetime, the maximum lifetime k-coverage problem is to schedule active/sleeping status of sensors to maximize the time period during which every target is covered by at least kactive sensors. Previously, it was known that when the sensing ranges are uniform, this problem has a polynomial-time (4+\varepsilon )-approximation for k=1and$(6+\varepsi...
22 CitationsSource
#1Mehdy Roayaei (AUT: Amirkabir University of Technology)H-Index: 1
In this paper, we study the problem of modifying a graph such that the resulting graph has a dominating set of size at most k. Solving this problem determines the minimum number of edges to be added to a given graph such that at most k vertices can dominate all vertices. We show that this problem is NP-hard, and therefore, has no polynomial-time algorithm (unless P = NP ). Also, we show that the problem is FPT parameterized by the treewidth of the input graph. Furthermore, we show that the probl...
1 CitationsSource
#1Deze Zeng (China University of Geosciences)H-Index: 25
#2Peng Li (University of Aizu)H-Index: 23
Last. Yong Xiang (Deakin University)H-Index: 40
view all 6 authors...
After a decade of extensive research on application-specific wireless sensor networks (WSNs), the recent development of information and communication technologies makes it practical to realize the software-defined sensor networks (SDSNs), which are able to adapt to various application requirements and to fully explore the resources of WSNs. A sensor node in SDSN is able to conduct multiple tasks with different sensing targets simultaneously. A given sensing task usually involves multiple sensors...
91 CitationsSource