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

executing such queries with minimal energy consumption. Given a query in a sensor network,we wish to select a small number of sensors that are sufficient to answer the query accurately.Also,the selected set of sensors should form a connected communication graph,so that they can form a logical routing topology for data gathering and transmis-sion to the query source.Hence,we wish to select an opti-mal set of sensors that satisfy the conditions of coverage as well as connectivity,i.e.,an optimal connected sensor cover as defined before.Constructing an optimal connected sen-sor cover for a query enables execution of the query in a very energy-efficient manner,as we need to involve only the sensors in the computed connected sensor cover for process-ing the query without compromising on its accuracy.Note here that we wish to combine coverage and connectivity in a single algorithm instead of using an alternative approach of treating them as two separate subproblems,as the opti-mal solution for the combined problem will be always equal or better than the solution obtained by solving for optimal coveragefirst and then for optimal connectivity.The reason for this is obvious–the sensors selected for mere connectiv-ity in this alternative approach also contribute to coverage. Also,the alternative approach requires two phases and thus incurs possibly higher overheads.Further discussion on the alternative approach appears in Section3,where a Steiner Tree based approach has been discussed.

The following discussion illustrates the savings in com-munication achieved by computing a connected sensor cover prior to the execution of a query.

Comparison with the Naive Approach:Given a query over a sensor network,a naive way to run the query will be to simplyflood the network with the query.Each sensor node in the network broadcasts the query message exactly once and also remembers the ID of the sensor node it re-ceives the query from.If there are n sensors whose sensing regions intersect with the query’s region,then using about n message transmissions,a communication tree spanning the n sensors could be built within the network in a breadth-first manner.Each node in the built tree now responds to the query.The responses propagate upwards in the tree towards the root of the tree(the query source).This again incurs a cost of n message transmissions,assuming that responses are aggregated at each tree node.Thus,the total commu-nication cost incurred in answering q such queries over the same region(possibly with different time windows)is2qn using the aboveflooding approach.

Now,consider a connected sensor cover of size m sensors. As the connected sensor cover set induces a connected com-munication subgraph,the total cost incurred in executing q queries over the same region will be D+2qm,where D is the communication cost incurred in computing the connected sensor cover.If m is substantially less than n,as would be the case of reasonably dense sensor networks,construct-ing a connected sensor cover could result in large savings in communication cost even with an overhead D cost.

2.2Formal Definition of the Problem

We now formally define the connected sensor cover prob-lem addressed in this article.We start with a few definitions.

Definition1.(Communication Graph;Communica-tion Distance)Given a sensor network consisting of a set of sensors I,the communication graph for the sensor network is the undirected1graph CG with I as the set of vertices and an edge between any two sensors if they can communicate directly with each other.The communication subgraph in-duced by a set of sensors M is the subgraph of CG involving only the vertices/sensors in M.

An edge in the communication graph is referred to as a communication edge between the two given sensors.A path of sensors between I1and I2in the communication graph is called a communication path between the sensors I1and I2. The communication distance between two sensors I1and I2 is the length of the shortest path between I1and I2in the communication graph(which is the number of sensors on the shortest path,including I1and I2).2 Definition2.(Connected Sensor Cover;Sensor Cover)Consider a sensor network consisting of n sensors I1,I2,...,I n.Let S i be the sensing region associated with the sensor I i.Given a query Q over a region R Q in the net-work,a set of sensors M=I i

1

,I i

2

,...,I i

m

is said to be a connected sensor cover for Q if the following two conditions hold:

1.R Q⊂(S i1∪S i2∪...S i m)

2.the subgraph induced by M in CG is connected,where

CG is the communication graph of the sensor network.

In other words,any sensor I i

j

in the connected sensor cover can communicate with any other sensor I i

k

in the cover,possibly through other sensors in the selected set M.

A set of sensors that satisfies only thefirst condition is called a sensor cover for Q in the network.2 Connected Sensor Coverage Problem:Given a sensor network and a query over the network,the connected sensor coverage problem is tofind the smallest connected sensor cover.

The connected sensor coverage problem is NP-hard as the less general problem of covering points using line segments is known to be NP-hard[16].Constructing a minimum con-nected sensor cover for a query in a sensor network enables the query to be computed by involving a minimum num-ber of sensors without compromising on the accuracy of the query result.

2.3A Note on Sensing Regions

The sensing region associated with a sensor signifies an area for which the sensor can take the full responsibility for sensing a given physical phenomenon within a desired confi-dence.The real semantics of a sensing region is application specific.For example,for target detection/tracking applica-tions,the sensing region is a region around the sensor within which the sensor can detect a target with a pre-determined minimum confidence.In such applications,the sensing re-gion for a sensor could be modeled as a circular region of radius d around itself,where d is the distance beyond which a target cannot be detected within a given confidence.In some other applications,sensing regions are defined in terms of the resolution of the application queries or the correlation of the sensed data.For example,consider an application