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

1 2 34Associated Candidate Paths: P 1, P 2, P 3, P 4

P 1 = < C 1, I 1> P 2 = < C 2, I 2, C 1, I 1>

R Q (a)

Figure 3:Working of The benefit of a candidate path P is the total number of uncovered valid subelements covered by the sensors in P divided by the number of sensors that are in P but not in M .The most beneficial candidate path is the candidate path that has the most benefit among the given set of candidate paths.2EXAMPLE 2.Figure 3shows a set sensors M (solid cir-cular dots),the region covered by M ,query region R Q ,and sensing disks corresponding to some of the sensors not in M (hollow circular dots).Figure 3(a)and (b)depict two consecutive stages of the algorithm.

Let us consider the stage of the algorithm shown in Fig-ure 3(a).At this stage,there are at least four candidate sensors viz.C 1,C 2,C 3,C 4,as shown in the figure.The can-didate paths associated with the candidate sensors are re-spectively P 1,P 2,P 3,P 4as shown.For sake of clarity,we have not shown the set of sensors involved in the candidate paths P 3and P 4,but the figure shows the actual communi-cation edges and sensors involved in the candidate paths P 1and P 2.Let us assume that the most beneficial candidate path at this stage is P 2.The algorithm then chooses P 2as P and adds the sensors C 1,I 2,and C 2to the set M .

The addition of sensors C 1,I 2,C 2to M yields the next stage of the algorithm shown in Figure 3(b).At this stage,the sensor I 5becomes a candidate sensor,while C 1no longer remains a candidate sensor.Also,the figure shows the re-calculated and new candidate paths connecting each of the candidate sensors C 3,C 4,I 5to some sensor in M .Here,we have assumed that the candidate path P 4doesn’t change from the previous stage,while the candidate path P 3changes to the communication edge (C 3,C 2).Now,at this stage,if P 3is the most beneficial path at this stage,the algorithm would add the sensor C 3to M ,which yields the next stage (now shown in the figure).Finally,if the algorithm adds to M a candidate path P 4connecting C 4to some sensor in M ,the set of sensors M would now cover the entire query region and the algorithm returns the new M (obtained by adding C 3,C 4,and other sensors in P 4to the M shown in

Figure 3(b))as the connected set cover.2

Algorithm 1.

Centralized Algorithm

Benefit :=0;for each C i ∈SC

Find the most beneficial candidate path P i for the candidate sensor C i ,i.e.,a candidate path P i with maximum benefit such that P i =<I i 0,I i 1,I i 2,...,I il >for some l ,where I il ∈M,I i 0=C i ,

and I ij can communicate directly to I i (j −1).Benefit :=(No.of valid subelements covered by the region ((S i 0∪S i 1∪...S il )−R M ))/l ;if (Benefit >Max

Benefit :=Benefit;P :=P i ;end if;end for;

M :=M ∪P ;end while;RETURN M ;END.

3