Connected Sensor Cover Self-Organization of Sensor Networks(6)

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

Observation1.The maximum number of subelements in a2-dimensional plane with n disks is n(n−1)+1.If we have

n convex objects,each having l sides,then the maximum number of subelements is ln(n+1).2 From the observation,it is easy to see that Algorithm1

can be implemented in O(n3)time,where n is the total

number of sensors in the network,by building shortest com-munication paths for all pairs of sensors in O(n3)time at

the beginning.

Definition6.(Link Radius)The link radius of a sensor

network is defined as the maximum communication distance between any two sensors whose sensing regions intersect.2 Theorem 1.Algorithm1returns a connected sensor cover of size at most(r−1)(1+log d)|OP T|,where|OP T|is the

size of the optimal sensor cover(not necessarily connected), d is the maximum number of subelements in a sensing region,

and r is the link radius of the sensor network.From Obser-

vation1,the connected sensor cover size is within O(r log n) factor of the optimal.

Proof.Whenever,a candidate path of sensors P is se-lected for addition to M by Algorithm1,we charge the uncovered valid subelements covered by P with(|P|−1),

the number of the unselected(not in M)sensors in P.The

charge(|P|−1)is spread uniformly on each of the uncov-ered valid subelements covered by P.Hence,each uncovered

valid subelement gets charged by(|P|−1)/E P units,where E P is the number of uncovered valid subelements covered by P.

Let OP T be an optimal sensor cover for the given query region in the sensor network.Let us consider a sensor I i∈OP T and try to compute the maximum charge accumulated by the sensing region S i of I i during the entire course of Al-gorithm1.At each stage of the algorithm,some uncovered valid subelements in the sensing region S i get covered by the path of sensors P selected at that stage.Let e j be the number of uncovered valid subelements of S i after the j th it-eration of the while loop(j th stage)of the algorithm.Here, e0is the total number of valid subelements of S i.Now,the number of uncovered valid subelements of S i covered dur-ing the j th iteration is e j−1−e j.Note that e j−1−e j may be zero,if there are no uncovered valid subelements of S i covered in the j th iteration.

If P j is the candidate path selected for addition at the j th iteration and E P j is the number of uncovered valid subele-ments covered by P j,then the total charge T accumulated by S i during the entire course of the algorithm is:

T=

j=k

j=1

(e j−1−e j)∗(|P j|−1)/E P j,

assuming the loop runs for k iterations.As our goal is to only compute an upper bound on T,let us assume,with-out loss of generality,that all the terms in the above series are non-zero,i.e.,for all j,P j covers a non-zero number of uncovered valid subelements in S i.

Now,E P1/(|P1|−1)≥(e0−e1)/(r−1)and E P j/(|P j|−1)≥e j−1/(r−1)for j≥2,as I i(along with a candidate path of length at most r and benefit of at least e j−1/(r−1)) 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)≤1+

j=k

j=2

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

Using some algebra([8],Chapter35.3),the above gives T≤(r−1)(1+log e0),where e0<d is the total number of valid subelements in S i.As the total charge spread(on the sensing regions of the optimal sensor cover,OP T)during each stage of the algorithm is the number of new sensors added to M,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 size of the solution M returned by Algorithm1is at most(r−1)(1+log d)|OP T|.Note that both r and d are functions of network density.

Steiner Tree Based Approach:One way to solve the connected sensor cover problem would be to construct a sen-sor cover and then build a Steiner tree[3]to connect the sen-sors in the sensor cover.This Steiner tree based approach is conceptually simpler and yields the same theoretical bound (O(r log n))on the size of the solution returned.However, the distributed implementation of such an approach would require two phases–one to compute the sensor cover and then another to construct the Steiner tree,and thus will pos-sibly incur a higher communication cost than our proposed distributed algorithm in Section4.Nevertheless,Steiner tree based approach could be used in scenarios,where the sensors selected for coverage and those selected for connec-tivity incur different costs with the former paying higher, as the activity of sensing and related signal processing may incur energy costs.We are investigating the Steiner tree based algorithm for various possibilities of relative sensing and communication costs,as part of our future work.

3.1Weighted Version

Algorithm1can be generalized to handle the weighted version of the connected sensor coverage problem.In the weighted setting,each sensor has a weight associated and we wish to select a connected sensor cover with the minimum total weight.In practice,we would assign higher weights to sensors that have a lower battery life and/or are critical to the viability of the sensor network so that they have a lesser chance of being selected.

The benefit of a candidate path in the weighted case is defined as the total number of uncovered valid subelements covered by P divided by the total weight of the sensors that are in P,but not M.Thus,to handle the weighted case,the value of Benefit in the algorithm is computed as follows: Benefit=(Number of valid subelements covered by the re-gion((S i0∪S i1∪...S il∩R Q)−R M))/(l−1j=0w ij),where w ij is the weight of the sensor I ij.

Definition7.(Weighted Communication Distance; Weighted Link Radius)The weighted communication dis-tance between two sensors is the weight of the minimum weighted communication path between them.

The weighted link radius of a sensor network is defined as the maximum weighted communication distance between any two sensors whose sensing regions intersect.2