# Connected sensor cover: self-organization of sensor networks for efficient query execution

Published on Jun 1, 2003
· DOI :10.1145/778415.778438
Himanshu Gupta34
Estimated H-index: 34
(SUNY: State University of New York System),
Samir R. Das61
Estimated H-index: 61
(SUNY: State University of New York System),
Quinyi Gu2
Estimated H-index: 2
(SUNY: State University of New York System)
Sources
Abstract
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 a query, into a topology that involves only a small subset of the sensors sufficient to process the query. The query is then executed using only the sensors in the constructed topology.In this article, we design and analyze algorithms for such self-organization of a sensor network to reduce energy consumption. In particular, we develop the notion of a connected sensor cover and design a centralized approximation algorithm that constructs a topology involving a near-optimal connected sensor cover. We prove that the size of the constructed topology is within an log n factor of the optimal size, where n is the network size. We also develop a distributed self-organization version of our algorithm, and propose several optimizations to reduce the communication overhead of the algorithm. Finally, we evaluate the distributed algorithm using simulations and show that our approach results in significant communication cost reduction.
📖 Papers frequently viewed together
2003
3 Authors (Ting Yan, ..., John A. Stankovic)
2001MOBICOM: ACM/IEEE International Conference on Mobile Computing and Networking
4 Authors (Benjie Chen, ..., Robert Morris)
2 Authors
References23
Nov 7, 2002 in INFOCOM (International Conference on Computer Communications)
#1Alberto E. Cerpa (UCLA: University of California, Los Angeles)H-Index: 26
#2Deborah Estrin (UCLA: University of California, Los Angeles)H-Index: 131
Advances in micro-sensor and radio technology will enable small but smart sensors to be deployed for a wide range of environmental monitoring applications. The low per-node cost will allow these wireless networks of sensors and actuators to be densely distributed. The nodes in these dense networks will coordinate to perform the distributed sensing tasks. Moreover, as described in this paper, the nodes can also coordinate to exploit the redundancy provided by high density, so as to extend overall...
#1Yuanzhu Peter Chen (UBC: University of British Columbia)H-Index: 13
#2Arthur L. Liestman (UBC: University of British Columbia)H-Index: 23
We present a series of approximation algorithms for finding a smallweakly-connected dominating set (WCDS) in a given graph to be usedin clustering mobile ad hoc networks. The structure of a graph canbe simplified using WCDS's and made more succinct for routing in adhoc networks. The theoretical performance ratio of these algorithmsis O(ln Δ) compared to the minimum size WCDS, whereΔ is the maximum degree of the input graph. The first twoalgorithms are based on the centralized approximation algor...
#1Khaled M. AlzoubiH-Index: 9
#2Peng-Jun WanH-Index: 57
Last. Ophir FriederH-Index: 53
view all 3 authors...
A connected dominating set (CDS) for a graph G(V,E) is a subset V1 of V, such that each node in V--V1 is adjacent to some node in V1, and V1 induces a connected subgraph. A CDS has been proposed as a virtual backbone for routing in wireless ad hoc networks. However, it is NP-hard to find a minimum connected dominating set (MCDS). Approximation algorithms for MCDS have been proposed in the literature. Most of these algorithms suffer from a very poor approximation ratio, and from high time complex...
#1Jie Wu (FAU: Florida Atlantic University)H-Index: 128
#2Hailan Li (FAU: Florida Atlantic University)H-Index: 2
Efficient routing among a set of mobile hosts (also called nodes) is one of the most important functions in ad hoc wireless networks. Routing based on a connected dominating set is a promising approach, where the searching space for a route is reduced to nodes in the set. A set is dominating if all the nodes in the system are either in the set or neighbors of nodes in the set. In this paper, we propose a simple and efficient distributed algorithm for calculating connected dominating set in ad ho...
Jul 16, 2001 in MOBICOM (ACM/IEEE International Conference on Mobile Computing and Networking)
#1Seapahn Meguerdichian (UCLA: University of California, Los Angeles)H-Index: 6
#2Farinaz Koushanfar (University of California, Berkeley)H-Index: 63
Last. Miodrag Potkonjak (UCLA: University of California, Los Angeles)H-Index: 77
view all 4 authors...
Wireless ad-hoc sensor networks will provide one of the missing connections between the Internet and the physical world. One of the fundamental problems in sensor networks is the calculation of coverage. Exposure is directly related to coverage in that it is a measure of how well an object, moving on an arbitrary path, can be observed by the sensor network over a period of time. In addition to the informal definition, we formally define exposure and study its properties. We have developed an eff...
#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 ...
Apr 22, 2001 in INFOCOM (International Conference on Computer Communications)
#1Seapahn Meguerdichian (UCLA: University of California, Los Angeles)H-Index: 6
#2Farinaz KoushanfarH-Index: 63
Last. Mani SrivastavaH-Index: 106
view all 4 authors...
Wireless ad-hoc sensor networks have recently emerged as a premier research topic. They have great long-term economic potential, ability to transform our lives, and pose many new system-building challenges. Sensor networks also pose a number of new conceptual and optimization problems. Some, such as location, deployment, and tracking, are fundamental issues, in that many applications rely on them for needed information. We address one of the fundamental problems, namely coverage. Coverage in gen...
#1Philippe Bonnet (Cornell University)H-Index: 23
#2Johannes Gehrke (Cornell University)H-Index: 81
Last. Praveen Seshadri (Cornell University)H-Index: 5
view all 3 authors...
Sensor networks are being widely deployed for measurement, detection and surveillance applications. In these new applications, users issue long-running queries over a combination of stored data and sensor data. Most existing applications rely on a centralized system for collecting sensor data. These systems lack flexibility because data is extracted in a predefined way; also, they do not scale to a large number of devices because large volumes of raw data are transferred regardless of the querie...
#1TH CormenH-Index: 2
#2CE LeisersonH-Index: 2
Last. Cliff SteinH-Index: 21
view all 4 authors...
#1V. S. Anil KumarH-Index: 29
#2Sunil Arya (HKU: University of Hong Kong)H-Index: 26
Last. H. Ramesh (IISc: Indian Institute of Science)H-Index: 6
view all 3 authors...
We consider a restricted version of the general Set Covering problem in which each set in the given set system intersects with any other set in at most 1 element. We show that the Set Covering problem with intersection 1 cannot be approximated within a o(log n) factor in random polynomial time unless N P ⊆ ZTIME(nO(log log n)). We also observe that the main challenge in derandomizing this reduction lies in finding a hitting set for large volume combinatorial rectangles satisfying certain interse...
Cited By268
#1Yingli Ran (ZJNU: Zhejiang Normal University)H-Index: 5
#2Xiaohui Huang (ZJNU: Zhejiang Normal University)H-Index: 6
Last. Ding-Zhu Du (UTD: University of Texas at Dallas)H-Index: 61
view all 4 authors...
In this paper, we consider the wireless sensor network in which the power of each sensor is adjustable. Given a set of sensors and a set of targets, we study a problem of minimizing the total power such that the coverage of targets meets partial multi-cover requirement, that is, there are at least a given number of targets each covered by a given number of sensors (this number is called the covering requirement for the target). This is called the minimum power partial multi-cover problem (MinPow...
#1Weili WuH-Index: 37
#2Zhao ZhangH-Index: 13
Last. Ding-Zhu DuH-Index: 61
view all 4 authors...
The connected sensor cover was first studied by Cardei et al. The minimum connected sensor cover problem (Problem 1.3.2) was first proposed by Gupta, Das, and Gu. They presented a greedy algorithm with performance ratio $$O(r \ln n)$$ where n is the number of sensors and r is the link radius of the sensor network, i.e., for any two sensors s and s′ with a sensing point in common, there exists a path between s and s′ with hop distance at most r in communication network. Zhang and Hou studied the ...
#1Govind P. Gupta (NITRR: National Institute of Technology, Raipur)H-Index: 12
#2Sonu Jha (NITRR: National Institute of Technology, Raipur)H-Index: 2
In wireless sensor networks, coverage and connectivity are the fundamental problems for monitoring the targets and guaranteed information dissemination to the far away base station from each node which covers the target. This problem has been proved NP-complete problem, where a set of target points are given, the objective is to find optimal number of suitable positions to organize sensor nodes such that it must satisfy both k-coverage and m-connectivity requirements. In this paper, a biogeograp...
#2Li WeiH-Index: 11
Localization by wireless sensor network is an important application of IoT technology. Beacon node placement, node-to-node measurement, and target node positioning are the three key steps for a beacon-based localization process. However, compared with the other two steps, beacon node placement still lacks of a comprehensive, systematic study in research literatures. To fill this gap, we address Beacon Node Placement (BNP) problem that deploys beacon nodes for minimal localization error in this p...
#1Kuei-Ping Shih (TKU: Tamkang University)H-Index: 19
#2Chi-Ming Yang (TKU: Tamkang University)H-Index: 2
Wireless rechargeable sensor networks are becoming crucial and important in recent years for the advancement of wireless energy transmission technology. The previous research showed that not all of sensors can be recharged due to the limitation of energy capacity that mobile chargers can carry. If a sensor playing a critical role in a sensing task cannot function as usual due to exhausted energy, then the sensing task will be interrupted. Therefore, this paper proposes a novel recharging mechani...
#1Yingfan L. Du (Columbia University)H-Index: 1
#2Lidong Wu (UT Tyler: University of Texas at Tyler)H-Index: 1
Given a target region Ω and a set of n homogeneous sensors, we study the problem of finding a minimum subset of sensors such that they induce a connected graph and cover Ω. We present a new method to replace the target region Ω by a set of target points, $$\mathcal {P}$$. In addition, we will give a new analysis for some existing approximation algorithms of the above minimum connected sensor cover problem. The new analysis will give better approximation performance ratios.
#1Yanmin Zhu (SJTU: Shanghai Jiao Tong University)H-Index: 40
#2Lionel M. Ni (HKUST: Hong Kong University of Science and Technology)H-Index: 88
It is of significant importance to provide network-wide Quality of Service (QoS) for a wide range of event detection applications in wireless sensor networks. This paper investigates the important problem of QoS provision to abnormal event detection. For event detection applications, there are two key performance metrics, i.e., detection probability and detection latency. This paper considers both metrics, aiming to provide statistical QoS for abnormal event detection. It is, however, a challeng...
#1Lidong WuH-Index: 10
#2Weili Wu (UTD: University of Texas at Dallas)H-Index: 37
Nowadays, the sensor exists everywhere. The wireless sensor network has been studied extensively. In view of this type of networks, there are two most important properties, coverage and connectivity. In fact, the sensor is often used for collecting information, and hence, its sensing area has to cover the target (points or area). Usually, for a wireless sensor, its sensing area is a disk with the center at the sensor. The radius of this disk is called the sensing radius. After information is col...
#1Bin Xia (Soochow University (Suzhou))
#2Zuoming Yu (Jiangsu University)
Coverage theory plays an important role not only in Topology but also in information science. In this paper, we study a novel coverage model, named bi-directional coverage. We characterize it with matrix. As an application, we prove that connectivity of sensor network is a special kind of bi-directional coverage by digraph theory.
#1Ahmed M. Khedr (UOS: University of Sharjah)H-Index: 16
Recently, there has been much focus on mobile sensor networks, and we have even seen the development of small-profile sensing devices that are able to control their own movement. Although it has been shown that mobility alleviates several issues relating to sensor network coverage and connectivity, many challenges remain. Among these, the need for position estimation is perhaps the most important. It is too expensive to include a GPS receiver with every sensor node. Hence, localization schemes f...