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

Theorem 2.For the weighted connected sensor coverage problem,the generalization of Algorithm1returns a con-nected sensor cover of total weight at most r(1+log d)|OP T|, where|OP T|is the total weight of an optimal sensor cover,

d is th

e maximum number o

f subelements in a sensin

g re-gion,and r is the weighted link radius of the sensor network.

Proof.The proof follows the proof of Theorem1.How-ever,in the weighted case,the total charge T accumulated by S i is given by:

T=

j=k

j=1

(e j−1−e j)∗(W P j−w il)/E P j,

where W P j is the total weight of the sensors in P j.Now, E P1/(W P1−w1l)≥(e0−e1)/r and E P j/(W P j−w il)≥e j−1/r for j≥2,as I i(along with a candidate path of weight at most r and benefit of at least e j−1/r)becomes a candidate sensor eligible for selection as soon as some valid subelement of I i gets covered by a sensor in M.Thus,

T/r≤1+

j=k

j=2

(e j−1−e j)/e j−1.

Similar to the previous proof,the above gives T≤r(1+ log e0),where e0is the total number of valid subelements in

S i.Note that the total charge accumulated on the sensing regions of all the sensors in OP T is equal to number of sensors in the solution returned by the algorithm.Thus,the total weight of the solution M returned by the algorithm is

at most r(1+log d)|OP T|.

4.DISTRIBUTED SELF-ORGANIZATION

ALGORITHM

In this section,we describe the self-organizing distributed version of Algorithm1.As stated before,one of the key features of our proposed approximation algorithm is that it lends to a very natural distributed algorithm.

Like the centralized algorithm,the self-organizing distributed algorithm goes through a sequence of stages to build a con-nected sensor cover within the sensor network for a given query.Throughout the course of the algorithm,the sensor network maintains the following values:

•M,a set of sensors that have already been selected for

inclusion in the connected sensor cover by the algo-

rithm.Like the centralized algorithm described in the

previous section,the distributed algorithm also incre-

ments M by adding a candidate path of sensors to M

at each stage.

•SP,a set of candidate paths.Recall that,a candidate

path is a sequence of sensors that form a communica-

tion path connecting a candidate sensor to some sen-

sor in M,where a candidate sensor is a sensor whose

sensing region intersects with some sensing region of a

sensor in M.Each candidate sensor has exactly one

candidate path associated with it.

•P,the most recently added candidate path,and C,the

candidate sensor associated with P.Each sensor in the network is aware of its membership in

M,or P,or in a candidate path in SP.Also,the most recently added candidate sensor C stores the values M,SP,

and P.Each stage of the distributed algorithm consists of the following sequence of transmission phases.

1.Candidate Path Search:The most recently added

candidate sensor C broadcasts a Candidate Path Search (CPS)message to all sensors within2r communica-tion hops,to select new candidate paths and candi-

date sensors.Here,r is the link radius of the sensor network.We choose2r(instead of r)so that the CPS

message from C reaches even those candidate sensors whose sensing disks intersect with that of other sensors

in P,the most recently added candidate path associ-ated with C.

2.Candidate Path Response:Any sensor I that re-

ceives a CPS message checks to see if it is a candidate sensor,i.e.,if I’s sensing region intersects with the

sensing region of some sensor in M.If I is a candidate sensor,it unicasts a Candidate Path Response(CPR)

message to the originating sensor C of the CPS mes-sage.The CPR message contains as candidate path P

the sequence of sensors(including I)that the received

CPS message passed through since its origination.

3.Selection of Best Candidate Path/Sensor:The

sensor C,which was the originator of the CPS mes-sages in the current stage,collects all the CPR mes-

sages sent to it by the candidate sensors.The candi-date path P contained in each received CPR message is added by C,after appropriate truncation,to SP,

the set of candidate paths being maintained by the sensor network.After having received all the CPR

messages sent to C during this stage,the sensor C se-lects the most beneficial candidate path P new among all the candidate paths in SP.Let,C new be the candi-

date sensor associated with the picked candidate path P new,and let I new be the set of sensors in the candi-date path P new.The sensor C unicasts a NewC mes-sage to C new with the following updated information: M=M∪I new;P=P new;SP=SP−P new.

Note that SP has also been augmented with all the candidate paths received in the CPR messages.

4.Repeat:The sensor C new receives the NewC message

sent to it by C.After receiving the message,C new up-

dates the value C to itself(i.e.,C=C new).That com-pletes the current stage of the algorithm.The above process repeats till the selected set of sensors M cover the entire query region in the sensor network.

The above distributed algorithm guarantees a self-organiza-

tion of the sensor network into a logical topology that repre-sents a connected sensor cover for the given query.To reduce the size of the CPS and NewC messages,we represent the set M by only the boundary sensors,i.e.,the sensors that are on the boundary of the region M covers.On an average, the number of boundary sensors should be the square root of the number of sensors in M.