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

Connected Sensor Cover:Self-Organization of Sensor Networks for Efficient Query Execution

Himanshu Gupta,Samir R.Das,Quinyi Gu

Department of Computer Science

State University of New Y ork

Stony Brook,NY11794

hgupta,samir,quinyigu@cs.sunysb.edu

ABSTRACT

Spatial query execution is an essential functionality of a sen-sor network,where a query gathers sensor data within a spe-cific geographic region.Redundancy within a sensor network can be exploited to reduce the communication cost incurred in execution of such queries.Any reduction in communi-cation 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 pro-cess 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 con-sumption.In particular,we develop the notion of a con-nected sensor cover and design a centralized approxima-tion algorithm that constructs a topology involving a near-optimal connected sensor cover.We prove that the size of the constructed topology is within an O(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 dis-tributed algorithm using simulations and show that our ap-proach results in significant communication cost reduction.

Categories and Subject Descriptors

C.2.4[Distributed Systems]:Distributed Applications

General Terms

Algorithms,Performance

Keywords

Sensor networks,sensor coverage,sensor connectivity,query optimization,connected sensor cover

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on thefirst page.To copy otherwise,to republish,to post on servers or to redistribute to lists,requires prior specific permission and/or a fee.

MobiHoc’03,June1–3,2003,Annapolis,Maryland,USA.

Copyright2003ACM1-58113-684-6/03/0006...$5.00.1.INTRODUCTION

Recent advances in miniature computing with advent of efficient short-range radios have given rise to strong inter-est in sensor networks[12,2].A sensor network consists of sensor nodes with a short-range radio and on-board process-ing capability.Each sensor can also sense certain physical phenomena like light,temperature,vibrations,or magnetic field around its location.The purpose of a sensor network is to process some high-level sensing tasks in a collaborative fashion,and is periodically queried by an external source to report a summary of the sensed data/tasks.For example,a large number of sensors can be scattered in a battlefield for surveillance purposes to detect certain objects of interest, say tanks.A typical query could be:Report the number of tank sightings at10minute intervals for the next24hours in a specific region within the battlefield.

Several new design themes have emerged for sensor net-works.On one hand,the network must be self-configuring and highly fault-tolerant as the sensors may be deployed in an“ad hoc”fashion.On the other hand,as each sen-sor has only limited battery energy,the network as a whole must minimize total energy usage in order to enable unteth-ered and unattended operation for an extended time.One technique to optimize energy usage during query execution would be for the network to self-organize,in response to a query,into a logical topology involving a minimum num-ber of sensor nodes that is sufficient to process the query. Only the sensors in the logical topology would participate (communicate with each other)during the query execution. This is a very effective strategy for energy conservation,es-pecially when there are many more sensors in the network than are necessary to process a given query.For example, two sensors in close enough proximity may generate the same or similar sensory data and it may be sufficient to involve only one of the sensors for query processing.The technique of self-organization exploits such redundancy effectively to conserve energy.

In order for the above technique to be of value,the num-ber of control messages used in the self-organization process must be small,so that the overhead of the technique does not offset the expected benefit completely.Note that the overhead is paid only once for a given query,but the ben-efit is reaped during each execution of the query.Thus,a high overhead for such a technique could still be tolerated for highly redundant networks and/or long running queries. In this paper,we design and analyze competitive algo-rithms for the above problem of self-organization of a sensor