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

network into an optimal logical topology in response to a query.In particular,we design an approximation algorithm that constructs such a topology in response to a query and show that the size of the topology returned by the algorithm is within an O(log n)factor of the size of an optimal topol-ogy,where n is the number of sensors in the network.We also design a distributed version of the proposed approxima-tion algorithm that is run by the sensors in the network and results in a self-organization of the network into a topology involving a near-optimal number of sensors.Through fur-ther analysis and experiments,we also show that the com-munication overhead of the distributed algorithm is reason-ably low which makes it very effective over a range of query and network parameters.

The rest of the paper is organized as follows.In Section 2,we provide a formulation of the problem with examples and discuss motivations.In Sections3and4,we present the design and analysis of our proposed centralized approxi-mation and the distributed self-organization algorithms.In Section5,we present the simulation results depicting the performance of our proposed algorithm.We end with dis-cussions on related work and concluding remarks in Sections 6and7,respectively.

2.PROBLEM FORMULATION AND MO-

TIV ATION

In this section,we describe the problem addressed in the article through an example,present motivation,and give a formal definition of the problem.We start with a description of a sensor network model.

A sensor network consists of a large number of sensors distributed randomly in a geographical region.Each sensor has a unique identifier(ID)I and is capable of sensing a well-defined convex region S around itself called the sens-ing region.More will be said later about sensing regions. Each sensor also has an a radio interface and can communi-cate directly with some of the sensors around it.A query in a sensor network asks for a summarization of some sensed data/events over some time window and a geographical re-gion,which is a subset of the overall region covered by the sensing regions of all the sensors in the network.By default, the geographical region associated with a sensor network query is the overall region covered by all the sensors in the network.A query is typically run multiple times,possibly, for different time windows.

Our article addresses the following optimization problem (formally defined later)that arises in sensor networks.Given a query over a sensor network,select a minimum set of sen-sors,called connected sensor cover,such that a)the sensing regions of the selected set of sensors cover the entire ge-ographical region of the query,and b)the selected set of sensors form a connected communication graph where there is an edge between any two sensors that can directly commu-nication with each other.The following example illustrates the problem.

EXAMPLE1.Consider the sensor network shown in Fig-ure1.Sensors are represented by small circular dots.We have numbered the relevant sensors with I1,I2,...,I9and shown sensing regions(circular S i disks)associated with some of them(the black nodes/sensors).Let the distance between sensors I1and I2be equal to t.We assume that any two sensors that are roughly less than t distance apart

the rectangle R in thefigure.

We can see that sensing regions associated with the black nodes(I1,I3,I5,I6,I8,I9)are sufficient to cover the query’s geographic region–the rectangle R Q.However,the set of black nodes does not form a connected communication graph,as the sensor nodes I1and I3cannot communicate. However,if we add the grey sensor nodes(I2,I4,I7)to the black nodes,we get a set of sensors that also forms a con-nected communication graph as shown in thefigure.Thus, the set of nine sensors I1to I9form a connected sensor cover. Our problem is tofind a minimum such cover.2 2.1Motivation

The following two characteristics of sensor networks lend importance to the connected sensor coverage problem.

1.Spatial Queries:Due to the geographical distribu-

tion of sensors in a sensor network,each piece of data generated in the sensor network has a geographic lo-cation associated with it in addition to a timestamp[4,

13].Hence,to specify the data of interest over which

a query should be answered,each query in a sensor

network has a time-window and a geographical region associated with it[4].By default,the geographical region associated with such spatial queries is the full region covered by sensing regions of all the sensors in the sensor network.

2.Limited Battery Power:Sensors are miniscule com-

puting devices with a limited battery power.Also, as evidenced in some recent studies[23],the energy budget for communication is many times more than computation with the available technology.Therefore, minimizing communication cost incurred in answering

a query in a sensor network will result in longer lasting

sensor networks.Hence,communication-efficient exe-cution of queries in a sensor network is of significant interest.

The motivation for the connected sensor coverage prob-lem addressed in this article comes from the presence of spatial queries in a sensor network and the importance of