Maintaining Sensing Coverage and Connectivity in Large Sensor Networks.

Published on Jan 1, 2005in Ad Hoc & Sensor Wireless Networks0.851
Honghai Zhang28
Estimated H-index: 28
Jennifer C. Hou44
Estimated H-index: 44
(UIUC: University of Illinois at Urbana–Champaign)
In this paper, we address the issues of maintaining sensing coverage and connectivity by keeping a minimum number of sensor nodes in the active mode in wireless sensor networks. We investigate the relationship between coverage and connectivity by solving the following two sub-problems. First, we prove that if the radio range is at least twice the sensing range, complete coverage of a convex area implies connectivity among the working set of nodes. Second, we derive, under the ideal case in which node density is sufficiently high, a set of optimality conditions under which a subset of working sensor nodes can be chosen for complete coverage. Based on the optimality conditions, we then devise a decentralized density control algorithm, Optimal Geographical Density Control (OGDC), for density control in large scale sensor networks. The OGDC algorithm is fully localized and can maintain coverage as well as connectivity, regardless of the relationship between the radio range and the sensing range. Ns-2 simulations show that OGDC outperforms existing density control algorithms [25, 26, 29] with respect to the number of working nodes needed and network lifetime (with up to 50% improvement), and achieves almost the same coverage as the algorithm with the best result.
Figures & Tables
📖 Papers frequently viewed together
2001MOBICOM: ACM/IEEE International Conference on Mobile Computing and Networking
3 Authors (Ya Xu, ..., Deborah Estrin)
2,630 Citations
3 Authors (Ting Yan, ..., John A. Stankovic)
499 Citations
11.9k Citations
Mar 24, 2004 in ICDCS (International Conference on Distributed Computing Systems)
#1C. Hu (UIUC: University of Illinois at Urbana–Champaign)H-Index: 1
#2Jennifer C. Hou (UIUC: University of Illinois at Urbana–Champaign)H-Index: 44
We present a novel and complementary mechanism, called link-indexed statistical traffic predictor (LISP) to improve IEEE 802.11 power saving mechanism (PSM). LISP employs a simple, light-weight traffic prediction mechanism and enables each node to seek the inherent correlation between ATIM.ACKs and incoming traffic. Thereby nodes en route can stay awake in the BI in which a packet is anticipated to arrive, thus bridging a "freeway" for the packet to rapidly traverse the route. Meanwhile, the num...
15 CitationsSource
#1Xiaorui Wang (WashU: Washington University in St. Louis)H-Index: 54
#2Guoliang Xing (WashU: Washington University in St. Louis)H-Index: 45
Last. Christopher Gill (WashU: Washington University in St. Louis)H-Index: 32
view all 6 authors...
An effective approach for energy conservation in wireless sensor networks is scheduling sleep intervals for extraneous nodes, while the remaining nodes stay active to provide continuous service. For the sensor network to operate successfully, the active nodes must maintain both sensing coverage and network connectivity. Furthermore, the network must be able to configure itself to any feasible degrees of coverage and connectivity in order to support different applications and environments with di...
1,204 CitationsSource
Jul 9, 2003 in INFOCOM (International Conference on Computer Communications)
#1Rong Zheng (UIUC: University of Illinois at Urbana–Champaign)H-Index: 37
#2Robin Kravets (UIUC: University of Illinois at Urbana–Champaign)H-Index: 41
Battery power is an important resource in ad hoc networks. It has been observed that in ad hoc networks, energy consumption does not reflect the communication activities in the network. Many existing energy conservation protocols based on electing a routing backbone for global connectivity are oblivious to traffic characteristics. In this paper, we propose an extensible on-demand power management framework for ad hoc networks that adapts to traffic load. Nodes maintain soft-state timers that det...
274 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
#1Rong Zheng (UIUC: University of Illinois at Urbana–Champaign)H-Index: 37
#2Jennifer C. Hou (UIUC: University of Illinois at Urbana–Champaign)H-Index: 44
Last. Lui Sha (UIUC: University of Illinois at Urbana–Champaign)H-Index: 67
view all 3 authors...
Due to the slow advancement of battery technology, power management in wireless networks remains to be a critical issue. Asynchronous wakeup has the merits of not requiring global clock synchronization and being resilient to network dynamics. This paper presents a systematic approach to designing and implementing asynchronous wakeup mechanisms in ad hoc networks. The optimal wakeup schedule design can be formulated as a block design problem in combinatorics. We propose a neighbor discovery and s...
423 CitationsSource
May 19, 2003 in ICDCS (International Conference on Distributed Computing Systems)
#1Fan Ye (UCLA: University of California, Los Angeles)H-Index: 32
#2Gary Zhong (UCLA: University of California, Los Angeles)H-Index: 6
Last. Lixia Zhang (UCLA: University of California, Los Angeles)H-Index: 99
view all 5 authors...
In this paper we present PEAS, a robust energy-conserving protocol that can build long-lived, resilient sensor networks using a very large number of small sensors with short battery lifetime. PEAS extends the network lifetime by maintaining a necessary set of working nodes and turning off redundant ones. PEAS operations are based on individual node's observation of the local environment and do not require any node to maintain per neighbor node state. PEAS performance possesses a high degree of r...
885 CitationsSource
Jan 1, 2003 in SIGCOMM (ACM Special Interest Group on Data Communication)
#1Jeremy Elson (UCLA: University of California, Los Angeles)H-Index: 29
#2Kay Römer (ETH Zurich)H-Index: 44
Wireless sensor networks (WSNs) consist of large populations of wirelessly connected nodes, capable of computation, communication, and sensing. Sensor nodes cooperate in order to merge individual sensor readings into a high-level sensing result, such as integrating a time series of position measurements into a velocity estimate. The physical time of sensor readings is a key element in this process called data fusion. Hence, time synchronization is a crucial component of WSNs. We argue that time ...
519 CitationsSource
#1Gregory J. Pottie (UCLA: University of California, Los Angeles)H-Index: 39
#2William J. Kaiser (UCLA: University of California, Los Angeles)H-Index: 70
Wireless Integrated Network Sensors (WINS) provide distributed network and Internet access to sensors, controls, and processors that are deeply embedded in equipment, facilities, and the environment. The WINS network is a new monitoring and control capability for applications in transportation, manufacturing, health care, environmental monitoring, and safety and security. WINS combine microsensor technology, low power signal processing, low power computation, and low power, low cost wireless net...
11 Citations
Dec 9, 2002 in OSDI (Operating Systems Design and Implementation)
#1Jeremy Elson (UCLA: University of California, Los Angeles)H-Index: 29
#2Lewis Girod (UCLA: University of California, Los Angeles)H-Index: 26
Last. Deborah Estrin (UCLA: University of California, Los Angeles)H-Index: 133
view all 3 authors...
Recent advances in miniaturization and low-cost, low-power design have led to active research in large-scale networks of small, wireless, low-power sensors and actuators. Time synchronization is critical in sensor networks for diverse purposes including sensor data fusion, coordinated actuation, and power-efficient duty cycling. Though the clock accuracy and precision requirements are often stricter than in traditional distributed systems, strict energy constraints limit the resources available ...
2,329 CitationsSource
Cited By1333
#1Atieh FanderH-Index: 1
#2Saeed YaghoubiH-Index: 10
Last. Javad TajikH-Index: 5
view all 3 authors...
Abstract The problem of coverage in two-dimensional (2D) wireless sensor networks is challenging and is still open. Precisely, determining the minimum sensor density (i.e, minimum number of sensors per unit area) that is required to cover a 2D field of interest (FoI), where every point in the field is covered by at least one sensor, is still under investigation. The problem of 2D k-coverage, which requires that every point in a 2D FoI be covered by at least k sensors, where k ≥ 1 , is more chall...
2 CitationsSource
#1Elham Golrasan (MUT: Malek-Ashtar University of Technology)H-Index: 1
#2Hossein Shirazi (MUT: Malek-Ashtar University of Technology)H-Index: 12
Last. Kourosh Dadashtabar (MUT: Malek-Ashtar University of Technology)H-Index: 1
view all 3 authors...
In this paper, the problem of full area coverage in wireless sensor networks is investigated by keeping the minimum number of heterogeneous sensor nodes. The coverage problem is considered for both deterministic and probabilistic heterogeneous sensors. We propose a new distributed game theory-based algorithm to maximize the area coverage while minimizing the number of activated sensors. Due to the energy limitations in sensor networks, we formulate the area coverage problem as a multi-player gam...
#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...
#1Banafsj Khalifa (UOS: University of Sharjah)H-Index: 3
#2Zaher Al Aghbari (UOS: University of Sharjah)H-Index: 14
Last. Ahmed M. Khedr (UOS: University of Sharjah)H-Index: 16
view all 3 authors...
Abstract The most fundamental task of the wireless sensor network (WSN) is to monitor a specified region of interest with sufficient sensor coverage. This task is jeopardized when coverage holes appear after the network's deployment. The emergence of coverage holes is unavoidable for many reasons such as sensor node energy depletion, physical damage, or external attacks. Therefore, it is important to have an ongoing mechanism for coverage maintenance because coverage holes can have debilitating ...
3 CitationsSource
#2A. Andrew RoobertH-Index: 4
view all 3 authors...
#2Anubhav Goel (IITR: Indian Institute of Technology Roorkee)H-Index: 1
Last. Germán Moltó (Polytechnic University of Valencia)H-Index: 16
view all 4 authors...
Internet of Things (IoT) is a new buzzword in information technology where real-world physical objects are made smart by integrating them with internet-enabled technologies. The things can sense information around them, communicate the sensed information over some protocol and employ the information to solve real-life problems. In IoT, several technologies are integrated under a common umbrella so that they can connect and exchange data over a network protocol. A huge amount of data is generated...
2 CitationsSource
#1Hanno HildmannH-Index: 10
#2Khouloud EledlebiH-Index: 3
Last. Abdel F. Isakovic (Colgate University)H-Index: 12
view all 4 authors...
#1Satya R. DasH-Index: 2
#2Koushik SinhaH-Index: 10
Last. Bhabani P. Sinha (Siksha O Anusandhan University)H-Index: 17
view all 4 authors...
Last. Vinita Tiwari (IIIT: Indian Institutes of Information Technology)H-Index: 4
view all 3 authors...
Wireless sensor networks are the collections of compact size, less expensive computational nodes that measure environmental conditions and other parameters and forward this information to a central point for processing. One can control homes, factories, vehicles, cities, and environment using WSNs. Area coverage and node connectivity pose as two of the most fundamental problems in wireless sensor networks since they are the key factors in the optimization of resources in a sensing field. In the ...