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

200400600800100012001400234

56789

S i z e o f s e n s o r c o v e r (m )

Transmission radius (t)

n=1600n=2000n=3000n=4000

(a)Size of connected sensor cover (m )0.6

0.8

1

1.2

1.4

2

3

4

56

7

8

9

R a t i o (m /m _c ) o f t h e s e n s o r c o v e r s i z e s

Transmission radius (t)

n=1600n=2000n=3000n=4000

(b)Ratio m/m c

Figure 4:Size of the sensor cover (m )computed by the distributed algorithm and the its ratio with that computed by the centralized algorithm (m/m c ),shown for various transmission radii and number of sensors.1)for such dense networks.

Without going through a complex probabilistic analysis,it is not possible to accurately calculate the minimum number of random sensors required in a given area for a network to be dense (as defined above)with high probability.We do not feel that such an analysis is warranted as an accurate computation of r is not essential.For our evaluation,we simply consider networks with more than 4s/t sensors within a distance 2s (i.e.,with a linear density of 2/t )as dense.Since we are using a 100×100area,a dense network should have at least (200/t )2sensors.Thus,for dense networks with more than (200/t )2sensors,we use r =(2s/t +1).For a non-dense network,we simply use a proportionate density factor to “inflate”the value of r ,i.e.,for a network with n sensors where n <(200/t )2,we use r =(2s/t +1)∗((200/t )2/n ).A fractional value of the computed r is simulated by using a probablity for the last hop forwarding of the CPS message.For example,if r =2.3,the CPS massage on the third hop is forwarded with 30%probablity.

Simulation Results:Figure 4plots m and ratio m/m c for various values of n and transmission radius t ,where m and m c are the sizes of the connected sensor covers computed by the distributed algorithm and the centralized algorithm respectively.Note that m and m c are very small relative to the network size n except for low n and t when the commu-nication graph is very sparse and there is low redundancy in the network.Figure 4(b)depicts excellent performance of the distributed algorithm relative to the centralized version.The ratio m/m c always remains close to the ideal value of 1.Note here that the distributed algorithm includes opti-mizations mentioned in Section 4.1.Thus,the optimizations introduced in the distributed algorithm to reduce commu-nication cost do not impact the m/m c ratio,which remains close to the ideal.Also,the above observation validates our method for computation of r .In fact,lower values of r could be possibly used without impacting the m/m c ratio signifi-cantly,but reducing the communication cost D .Thus,the performance our algorithm could be further improved.

Figure 5(a)depicts how the communication cost D in the

distributed algorithm changes with n and t .The explanation for the cusp shape of the D vs.t plot is as follows.From the above discussion,there is a threshold value of t ,above which the network becomes dense for a constant n .This threshold is t θ=200/

√n ,t θis larger for smaller n .Hence,we see that the

minimum number of messages reached for 1600-2000number of sensors is at t =5,while for higher number of sensors (n )the minimum is reached at a lower transmission radius (t =3).

Figure 5(b)plots q θvs.n for different values of t .This plot is somewhat similar to the plot of D ,because of the strong dependency of q θon D .Notice that the value of q θis fairly small –almost always less than 7except when the communication graph is very sparse (low n together with low t ).This shows that except for very sparse networks,our self-organization technique will always save energy relative to the naive flooding approach,whenever the query runs for more than about 7times –longer runs giving more energy saving benefits.

6.RELATED WORK

The work most closely related to ours is that by Slijepc-sevic and Potkonjak [25],where the authors consider power-efficient organization of sensor networks.They introduce a heuristic that selects mutually exclusive sets of sensors,the members of each of those sets together completely cover the