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

Figure2:Subelements and Valid Subelements. that gathers temperature samples in a geographical region monitored by a sensor network.Now,due to the spatial na-ture of temperature,temperature values at any two points that are less than d distance apart may be highly correlated. In such a case,we can again define sensing regions of circular radius d around each sensor.

As discussed above,typically,we can determine the sens-ing region for each sensor either as a static approximation of the sensor’s location and capabilities,or as a function of query’s resolution,or application’s confidence requirements. The concept of sensing region similar to ours has been used in recent research,for example,by Slijepcevic and Potkon-jak in[25],which addresses a closely related problem,and more recently,by Shakkottai et al.in[24].

If the sensing region is not known a priori,we can solve the connected sensor coverage problem iteratively for increasing sensing regions and pick the minimum solution whose gath-ered data is sufficiently accurate in comparison with the collective data of all the sensors.Otherwise,without the assumption of sensing regions,the connected sensor cover-age problem could be formulated as a problem of selecting a minimum connected set of sensors such that every point in the query region gets a minimum amount of“exposure”from the selected set of sensors.Such a concept of exposure has been defined in[22]albeit in a different context.

In our treatment,the sensing regions can take any convex shape.The convexity assumption is needed to make Obser-vation1(defined later).The convexity assumption will be true in practice,unless there are impregnable obstacles in the sensor network region.For ease of presentation,we have shown circular sensing regions in thefigures throughout this article.

3.CENTRALIZED APPROXIMATION AL-

GORITHM

In this section,we present the approximation algorithm for the connected sensor coverage problem.The algorithm runs in polynomial time and guarantees a solution whose size is within O(r log n)of the optimal,where r is the link radius of the sensor network and is defined later.One of the important features of our algorithm is that it can be easily transformed into a distributed version that has low communication overhead.

Definition3.(Subelement;Valid Subelements)Con-sider a geographic region with a number of sensing regions.

A subelement is a set of points.Two points belong to same subelement iffthey are covered by the same set of sensing regions.In other words,a subelement is a minimal region that is formed by an intersection of a number of sensing re-gions.Given a query region R Q,a subelement is valid if its region intersects with R Q.

In Figure2,where R Q is the given query region,there are fourteen subelements numbered1to14,of which only1to 11are valid subelements.2 Algorithm Description:We designed a greedy algorithm to select a connected sensor cover of near-optimal size.In short,the greedy algorithm works by selecting,at each stage, a path(communication path)of sensors that connects an already selected sensor to a partially covered sensor.The selected path is then added to the already selected sensors at that stage.The algorithm terminates when the selected set of sensors completely cover the given query region.

A more formal and complete description of the designed greedy algorithm is as follows.Let us assume that M is the set of sensors already selected for inclusion in the connected sensor cover by the greedy algorithm at any stage.Initially, M is an empty set.The algorithm starts with including in M an arbitrary sensor that lies within the query’s region.At each stage,the greedy algorithm selects a sensor C(based on a criteria described later)along with a path/sequence of sensors P that forms a communication path between C and some sensor in M.The selected path of sensors P, which includes C,is then added to M.Thus,at any stage of the algorithm,the communication subgraph induced by M is connected.Also,if at each stage,the selected path of sensors P covers some yet uncovered(by M)area of the query’s region,then the algorithm will eventually terminate with M as the connected sensor cover.

We now describe the criteria used in selection of C and P at any given stage of the algorithm.Any sensor C i/∈M whose sensing region contains a valid subelement,that has been covered by a sensor in M,becomes a candidate sen-sor,i.e.,a potential candidate for selection as C.For each such candidate sensor C i,we construct a candidate path P i of sensors that forms a communication path connecting C i to some sensor in M.The candidate path P i that covers the maximum number of uncovered valid subelements per sensor(defined as benefit of P i)is added to M at that stage of the algorithm.We will illustrate the working of the al-gorithm through an example(Example2)and describe the algorithm formally in Algorithm1.First,we define some terms introduced in the above description.

Definition4.(Candidate Sensor;Candidate Path) Let M be the set of sensors already selected by the algo-rithm.A sensor C is called as a candidate sensor if C/∈M and the sensing region of C intersects with the sensing region of some sensor in M.A candidate path is a sequence/path of sensors that form a communication path connecting a candi-date sensor C with some sensor in M.We use|P|to denote the length of a candidate path P.2 Definition5.(Uncovered Valid Subelements;Bene-fit of a Candidate Path)An uncovered valid subelement is a valid subelement that is not covered by any sensing re-gion of a sensor in M,the set of sensors already selected for inclusion in the connected sensor cover by the algorithm.In Figure2,if M contains the sensors corresponding to the two left-most sensing disks S and S′,then the uncovered valid subelements are8,9,10,and11.