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

4.1Optimizations to Reduce Number of Mes-

sages

The following optimization techniques have been used by the distributed algorithm to reduce the number of messages incurred during the self-organization.

1.To reduce the number of messages for coordination,

we reuse the candidate paths computed for candidate sensors at later stages of the algorithm.In contrast, the centralized algorithm recomputes the(best)candi-date paths for each candidate sensor at each stage and picks the most beneficial candidate path.However,the distributed algorithm does optimize already computed candidate paths by truncating them if some sensor in the candidate path has been newly added to M.Also, the distributed algorithm does recalculate the benefit of each candidate path in SP at each stage.

2.To compute the benefit of a candidate path,the dis-

tributed algorithm computes the area of the uncovered query region covered by the candidate path instead of the number of uncovered valid subelements covered by the candidate path.

3.To reduce the number of broadcast CPS messages,we

stipulate that if a sensor has already been selected in M then it does not broadcast a CPS message received from another sensor.Also,a sensor broadcasts a CPS broadcast message only once during any one stage of the algorithm.

We observed through extensive experiments(as shown later in Figure4(b))that the above optimizations do not increase the size of the connected sensor cover constructed. However,they do result in substantial savings in communi-cation cost.

Number of Messages:If the NewC messages are trans-mitted through an optimal path within M,it is not diffi-cult to show that the total number of messages transmit-ted during the entire course of the distributed algorithm is O(k(log m+b))for uniformly distributed sensors,where k is the number of stages the algorithm goes through before terminating,m is the size of connected sensor cover con-structed,b is the maximum number of sensors within2r communication hops of any sensor.Here,as in the simula-tion experiments in the next section,we assume piggyback-ing of CPR messages at each stage,i.e.,during the CPR phase each sensor waits sufficiently long to collect all CPR messages intended to pass through it,and then unicasts all the collected CPR messages to the C in one message.

5.PERFORMANCE EV ALUATION

We have constructed a simulator to evaluate the perfor-mance of the distributed self-organization algorithm,and contrast it with the naiveflooding-based approach(see Sec-tion2.1).The simulator uses randomly placed sensor nodes in a rectangular region.All sensor nodes have a circular sensing region of radius s associated with them.A commu-nication edge exists between two sensor nodes if they are within a certain distance,called transmission radius,from each other.The size of the rectangular region,number of nodes(n),sensing radius(s),and transmission radius(t) are input parameters of the simulator.The link radius(r)is computed in terms of the above parameters and will be described later.

The simulator only models message transmissions.It does not model any link layer protocol or wireless channel char-acteristics.Thus,all the messages in the simulator are transmitted in an error-free manner.2Also,the passage of time is modeled in a time-stepped fashion,wherein during each step,each node receives messages,performs appropri-ate computations in response to these messages,and then sends out messages as a result of these computations.While such a simulator models an idealized communication subsys-tem,it is sufficient for our purpose,as we are only interested in counting message transmissions.

As in Section2.1,let D be the number of messages needed to compute the connected sensor cover and m be the size of the computed connected sensor cover.We assume that the spatial query runs over the entire geographic region with a randomly selected sensor as the query source.The simula-tor computes D and m,for a given set of input parameters. Let us assume that the query runs q times.We evaluate the threshold value qθ,such that for q>qθthe overall message cost for the query using our distributed self-organization al-gorithm is lower than the message cost using the naive ap-proach.The number qθis obtained by equating D+2qm to 2qn and then solving for q,which gives

qθ=

D

2The effect of transmission errors or message losses is a part of our future work.Our algorithms can be extended to use local repair mechanisms to compensate for message losses.