Connected Sensor Cover Self-Organization of Sensor Networks for Efficient Query Execution

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

Connected Sensor Cover:Self-Organization of Sensor Networks for Ef?cient Query Execution

Himanshu Gupta,Samir R.Das,Quinyi Gu

Department of Computer Science

State University of New Y ork

Stony Brook,NY11794

hgupta,samir,quinyigu@cs.sunysb.edu

ABSTRACT

Spatial query execution is an essential functionality of a sen-sor network,where a query gathers sensor data within a spe-ci?c geographic region.Redundancy within a sensor network can be exploited to reduce the communication cost incurred in execution of such queries.Any reduction in communi-cation cost would result in an e?cient use of the battery energy,which is very limited in sensors.One approach to reduce the communication cost of a query is to self-organize the network,in response to a query,into a topology that involves only a small subset of the sensors su?cient to pro-cess the query.The query is then executed using only the sensors in the constructed topology.

In this article,we design and analyze algorithms for such self-organization of a sensor network to reduce energy con-sumption.In particular,we develop the notion of a con-nected sensor cover and design a centralized approxima-tion algorithm that constructs a topology involving a near-optimal connected sensor cover.We prove that the size of the constructed topology is within an O(log n)factor of the optimal size,where n is the network size.We also develop a distributed self-organization version of our algorithm,and propose several optimizations to reduce the communication overhead of the algorithm.Finally,we evaluate the dis-tributed algorithm using simulations and show that our ap-proach results in signi?cant communication cost reduction.

Categories and Subject Descriptors

C.2.4[Distributed Systems]:Distributed Applications

General Terms

Algorithms,Performance

Keywords

Sensor networks,sensor coverage,sensor connectivity,query optimization,connected sensor cover

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro?t or commercial advantage and that copies bear this notice and the full citation on the?rst page.To copy otherwise,to republish,to post on servers or to redistribute to lists,requires prior speci?c permission and/or a fee.

MobiHoc’03,June1–3,2003,Annapolis,Maryland,USA.

Copyright2003ACM1-58113-684-6/03/0006...$5.00.1.INTRODUCTION

Recent advances in miniature computing with advent of e?cient short-range radios have given rise to strong inter-est in sensor networks[12,2].A sensor network consists of sensor nodes with a short-range radio and on-board process-ing capability.Each sensor can also sense certain physical phenomena like light,temperature,vibrations,or magnetic ?eld around its location.The purpose of a sensor network is to process some high-level sensing tasks in a collaborative fashion,and is periodically queried by an external source to report a summary of the sensed data/tasks.For example,a large number of sensors can be scattered in a battle?eld for surveillance purposes to detect certain objects of interest, say tanks.A typical query could be:Report the number of tank sightings at10minute intervals for the next24hours in a speci?c region within the battle?eld.

Several new design themes have emerged for sensor net-works.On one hand,the network must be self-con?guring and highly fault-tolerant as the sensors may be deployed in an“ad hoc”fashion.On the other hand,as each sen-sor has only limited battery energy,the network as a whole must minimize total energy usage in order to enable unteth-ered and unattended operation for an extended time.One technique to optimize energy usage during query execution would be for the network to self-organize,in response to a query,into a logical topology involving a minimum num-ber of sensor nodes that is su?cient to process the query. Only the sensors in the logical topology would participate (communicate with each other)during the query execution. This is a very e?ective strategy for energy conservation,es-pecially when there are many more sensors in the network than are necessary to process a given query.For example, two sensors in close enough proximity may generate the same or similar sensory data and it may be su?cient to involve only one of the sensors for query processing.The technique of self-organization exploits such redundancy e?ectively to conserve energy.

In order for the above technique to be of value,the num-ber of control messages used in the self-organization process must be small,so that the overhead of the technique does not o?set the expected bene?t completely.Note that the overhead is paid only once for a given query,but the ben-e?t is reaped during each execution of the query.Thus,a high overhead for such a technique could still be tolerated for highly redundant networks and/or long running queries. In this paper,we design and analyze competitive algo-rithms for the above problem of self-organization of a sensor

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

network into an optimal logical topology in response to a query.In particular,we design an approximation algorithm that constructs such a topology in response to a query and show that the size of the topology returned by the algorithm is within an O(log n)factor of the size of an optimal topol-ogy,where n is the number of sensors in the network.We also design a distributed version of the proposed approxima-tion algorithm that is run by the sensors in the network and results in a self-organization of the network into a topology involving a near-optimal number of sensors.Through fur-ther analysis and experiments,we also show that the com-munication overhead of the distributed algorithm is reason-ably low which makes it very e?ective over a range of query and network parameters.

The rest of the paper is organized as follows.In Section 2,we provide a formulation of the problem with examples and discuss motivations.In Sections3and4,we present the design and analysis of our proposed centralized approxi-mation and the distributed self-organization algorithms.In Section5,we present the simulation results depicting the performance of our proposed algorithm.We end with dis-cussions on related work and concluding remarks in Sections 6and7,respectively.

2.PROBLEM FORMULATION AND MO-

TIV ATION

In this section,we describe the problem addressed in the article through an example,present motivation,and give a formal de?nition of the problem.We start with a description of a sensor network model.

A sensor network consists of a large number of sensors distributed randomly in a geographical region.Each sensor has a unique identi?er(ID)I and is capable of sensing a well-de?ned convex region S around itself called the sens-ing region.More will be said later about sensing regions. Each sensor also has an a radio interface and can communi-cate directly with some of the sensors around it.A query in a sensor network asks for a summarization of some sensed data/events over some time window and a geographical re-gion,which is a subset of the overall region covered by the sensing regions of all the sensors in the network.By default, the geographical region associated with a sensor network query is the overall region covered by all the sensors in the network.A query is typically run multiple times,possibly, for di?erent time windows.

Our article addresses the following optimization problem (formally de?ned later)that arises in sensor networks.Given a query over a sensor network,select a minimum set of sen-sors,called connected sensor cover,such that a)the sensing regions of the selected set of sensors cover the entire ge-ographical region of the query,and b)the selected set of sensors form a connected communication graph where there is an edge between any two sensors that can directly commu-nication with each other.The following example illustrates the problem.

EXAMPLE1.Consider the sensor network shown in Fig-ure1.Sensors are represented by small circular dots.We have numbered the relevant sensors with I1,I2,...,I9and shown sensing regions(circular S i disks)associated with some of them(the black nodes/sensors).Let the distance between sensors I1and I2be equal to t.We assume that any two sensors that are roughly less than t distance apart

the rectangle R in the?gure.

We can see that sensing regions associated with the black nodes(I1,I3,I5,I6,I8,I9)are su?cient to cover the query’s geographic region–the rectangle R Q.However,the set of black nodes does not form a connected communication graph,as the sensor nodes I1and I3cannot communicate. However,if we add the grey sensor nodes(I2,I4,I7)to the black nodes,we get a set of sensors that also forms a con-nected communication graph as shown in the?gure.Thus, the set of nine sensors I1to I9form a connected sensor cover. Our problem is to?nd a minimum such cover.2 2.1Motivation

The following two characteristics of sensor networks lend importance to the connected sensor coverage problem.

1.Spatial Queries:Due to the geographical distribu-

tion of sensors in a sensor network,each piece of data generated in the sensor network has a geographic lo-cation associated with it in addition to a timestamp[4,

13].Hence,to specify the data of interest over which

a query should be answered,each query in a sensor

network has a time-window and a geographical region associated with it[4].By default,the geographical region associated with such spatial queries is the full region covered by sensing regions of all the sensors in the sensor network.

2.Limited Battery Power:Sensors are miniscule com-

puting devices with a limited battery power.Also, as evidenced in some recent studies[23],the energy budget for communication is many times more than computation with the available technology.Therefore, minimizing communication cost incurred in answering

a query in a sensor network will result in longer lasting

sensor networks.Hence,communication-e?cient exe-cution of queries in a sensor network is of signi?cant interest.

The motivation for the connected sensor coverage prob-lem addressed in this article comes from the presence of spatial queries in a sensor network and the importance of

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

executing such queries with minimal energy consumption. Given a query in a sensor network,we wish to select a small number of sensors that are su?cient to answer the query accurately.Also,the selected set of sensors should form a connected communication graph,so that they can form a logical routing topology for data gathering and transmis-sion to the query source.Hence,we wish to select an opti-mal set of sensors that satisfy the conditions of coverage as well as connectivity,i.e.,an optimal connected sensor cover as de?ned before.Constructing an optimal connected sen-sor cover for a query enables execution of the query in a very energy-e?cient manner,as we need to involve only the sensors in the computed connected sensor cover for process-ing the query without compromising on its accuracy.Note here that we wish to combine coverage and connectivity in a single algorithm instead of using an alternative approach of treating them as two separate subproblems,as the opti-mal solution for the combined problem will be always equal or better than the solution obtained by solving for optimal coverage?rst and then for optimal connectivity.The reason for this is obvious–the sensors selected for mere connectiv-ity in this alternative approach also contribute to coverage. Also,the alternative approach requires two phases and thus incurs possibly higher overheads.Further discussion on the alternative approach appears in Section3,where a Steiner Tree based approach has been discussed.

The following discussion illustrates the savings in com-munication achieved by computing a connected sensor cover prior to the execution of a query.

Comparison with the Naive Approach:Given a query over a sensor network,a naive way to run the query will be to simply?ood the network with the query.Each sensor node in the network broadcasts the query message exactly once and also remembers the ID of the sensor node it re-ceives the query from.If there are n sensors whose sensing regions intersect with the query’s region,then using about n message transmissions,a communication tree spanning the n sensors could be built within the network in a breadth-?rst manner.Each node in the built tree now responds to the query.The responses propagate upwards in the tree towards the root of the tree(the query source).This again incurs a cost of n message transmissions,assuming that responses are aggregated at each tree node.Thus,the total commu-nication cost incurred in answering q such queries over the same region(possibly with di?erent time windows)is2qn using the above?ooding approach.

Now,consider a connected sensor cover of size m sensors. As the connected sensor cover set induces a connected com-munication subgraph,the total cost incurred in executing q queries over the same region will be D+2qm,where D is the communication cost incurred in computing the connected sensor cover.If m is substantially less than n,as would be the case of reasonably dense sensor networks,construct-ing a connected sensor cover could result in large savings in communication cost even with an overhead D cost.

2.2Formal De?nition of the Problem

We now formally de?ne the connected sensor cover prob-lem addressed in this article.We start with a few de?nitions.

De?nition1.(Communication Graph;Communica-tion Distance)Given a sensor network consisting of a set of sensors I,the communication graph for the sensor network is the undirected1graph CG with I as the set of vertices and an edge between any two sensors if they can communicate directly with each other.The communication subgraph in-duced by a set of sensors M is the subgraph of CG involving only the vertices/sensors in M.

An edge in the communication graph is referred to as a communication edge between the two given sensors.A path of sensors between I1and I2in the communication graph is called a communication path between the sensors I1and I2. The communication distance between two sensors I1and I2 is the length of the shortest path between I1and I2in the communication graph(which is the number of sensors on the shortest path,including I1and I2).2 De?nition2.(Connected Sensor Cover;Sensor Cover)Consider a sensor network consisting of n sensors I1,I2,...,I n.Let S i be the sensing region associated with the sensor I i.Given a query Q over a region R Q in the net-work,a set of sensors M=I i

1

,I i

2

,...,I i

m

is said to be a connected sensor cover for Q if the following two conditions hold:

1.R Q?(S i1∪S i2∪...S i m)

2.the subgraph induced by M in CG is connected,where

CG is the communication graph of the sensor network.

In other words,any sensor I i

j

in the connected sensor cover can communicate with any other sensor I i

k

in the cover,possibly through other sensors in the selected set M.

A set of sensors that satis?es only the?rst condition is called a sensor cover for Q in the network.2 Connected Sensor Coverage Problem:Given a sensor network and a query over the network,the connected sensor coverage problem is to?nd the smallest connected sensor cover.

The connected sensor coverage problem is NP-hard as the less general problem of covering points using line segments is known to be NP-hard[16].Constructing a minimum con-nected sensor cover for a query in a sensor network enables the query to be computed by involving a minimum num-ber of sensors without compromising on the accuracy of the query result.

2.3A Note on Sensing Regions

The sensing region associated with a sensor signi?es an area for which the sensor can take the full responsibility for sensing a given physical phenomenon within a desired con?-dence.The real semantics of a sensing region is application speci?c.For example,for target detection/tracking applica-tions,the sensing region is a region around the sensor within which the sensor can detect a target with a pre-determined minimum con?dence.In such applications,the sensing re-gion for a sensor could be modeled as a circular region of radius d around itself,where d is the distance beyond which a target cannot be detected within a given con?dence.In some other applications,sensing regions are de?ned in terms of the resolution of the application queries or the correlation of the sensed data.For example,consider an application

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

Figure2:Subelements and Valid Subelements. that gathers temperature samples in a geographical region monitored by a sensor network.Now,due to the spatial na-ture of temperature,temperature values at any two points that are less than d distance apart may be highly correlated. In such a case,we can again de?ne sensing regions of circular radius d around each sensor.

As discussed above,typically,we can determine the sens-ing region for each sensor either as a static approximation of the sensor’s location and capabilities,or as a function of query’s resolution,or application’s con?dence requirements. The concept of sensing region similar to ours has been used in recent research,for example,by Slijepcevic and Potkon-jak in[25],which addresses a closely related problem,and more recently,by Shakkottai et al.in[24].

If the sensing region is not known a priori,we can solve the connected sensor coverage problem iteratively for increasing sensing regions and pick the minimum solution whose gath-ered data is su?ciently accurate in comparison with the collective data of all the sensors.Otherwise,without the assumption of sensing regions,the connected sensor cover-age problem could be formulated as a problem of selecting a minimum connected set of sensors such that every point in the query region gets a minimum amount of“exposure”from the selected set of sensors.Such a concept of exposure has been de?ned in[22]albeit in a di?erent context.

In our treatment,the sensing regions can take any convex shape.The convexity assumption is needed to make Obser-vation1(de?ned later).The convexity assumption will be true in practice,unless there are impregnable obstacles in the sensor network region.For ease of presentation,we have shown circular sensing regions in the?gures throughout this article.

3.CENTRALIZED APPROXIMATION AL-

GORITHM

In this section,we present the approximation algorithm for the connected sensor coverage problem.The algorithm runs in polynomial time and guarantees a solution whose size is within O(r log n)of the optimal,where r is the link radius of the sensor network and is de?ned later.One of the important features of our algorithm is that it can be easily transformed into a distributed version that has low communication overhead.

De?nition3.(Subelement;Valid Subelements)Con-sider a geographic region with a number of sensing regions.

A subelement is a set of points.Two points belong to same subelement i?they are covered by the same set of sensing regions.In other words,a subelement is a minimal region that is formed by an intersection of a number of sensing re-gions.Given a query region R Q,a subelement is valid if its region intersects with R Q.

In Figure2,where R Q is the given query region,there are fourteen subelements numbered1to14,of which only1to 11are valid subelements.2 Algorithm Description:We designed a greedy algorithm to select a connected sensor cover of near-optimal size.In short,the greedy algorithm works by selecting,at each stage, a path(communication path)of sensors that connects an already selected sensor to a partially covered sensor.The selected path is then added to the already selected sensors at that stage.The algorithm terminates when the selected set of sensors completely cover the given query region.

A more formal and complete description of the designed greedy algorithm is as follows.Let us assume that M is the set of sensors already selected for inclusion in the connected sensor cover by the greedy algorithm at any stage.Initially, M is an empty set.The algorithm starts with including in M an arbitrary sensor that lies within the query’s region.At each stage,the greedy algorithm selects a sensor C(based on a criteria described later)along with a path/sequence of sensors P that forms a communication path between C and some sensor in M.The selected path of sensors P, which includes C,is then added to M.Thus,at any stage of the algorithm,the communication subgraph induced by M is connected.Also,if at each stage,the selected path of sensors P covers some yet uncovered(by M)area of the query’s region,then the algorithm will eventually terminate with M as the connected sensor cover.

We now describe the criteria used in selection of C and P at any given stage of the algorithm.Any sensor C i/∈M whose sensing region contains a valid subelement,that has been covered by a sensor in M,becomes a candidate sen-sor,i.e.,a potential candidate for selection as C.For each such candidate sensor C i,we construct a candidate path P i of sensors that forms a communication path connecting C i to some sensor in M.The candidate path P i that covers the maximum number of uncovered valid subelements per sensor(de?ned as bene?t of P i)is added to M at that stage of the algorithm.We will illustrate the working of the al-gorithm through an example(Example2)and describe the algorithm formally in Algorithm1.First,we de?ne some terms introduced in the above description.

De?nition4.(Candidate Sensor;Candidate Path) Let M be the set of sensors already selected by the algo-rithm.A sensor C is called as a candidate sensor if C/∈M and the sensing region of C intersects with the sensing region of some sensor in M.A candidate path is a sequence/path of sensors that form a communication path connecting a candi-date sensor C with some sensor in M.We use|P|to denote the length of a candidate path P.2 De?nition5.(Uncovered Valid Subelements;Bene-?t of a Candidate Path)An uncovered valid subelement is a valid subelement that is not covered by any sensing re-gion of a sensor in M,the set of sensors already selected for inclusion in the connected sensor cover by the algorithm.In Figure2,if M contains the sensors corresponding to the two left-most sensing disks S and S′,then the uncovered valid subelements are8,9,10,and11.

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 bene?t 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 bene?cial candidate path is the candidate path that has the most bene?t 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 ?gure.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 ?gure shows the actual communi-cation edges and sensors involved in the candidate paths P 1and P 2.Let us assume that the most bene?cial 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 ?gure 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 bene?cial path at this stage,the algorithm would add the sensor C 3to M ,which yields the next stage (now shown in the ?gure).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

Bene?t :=0;for each C i ∈SC

Find the most bene?cial candidate path P i for the candidate sensor C i ,i.e.,a candidate path P i with maximum bene?t 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).Bene?t :=(No.of valid subelements covered by the region ((S i 0∪S i 1∪...S il )?R M ))/l ;if (Bene?t >Max

Bene?t :=Bene?t;P :=P i ;end if;end for;

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

3

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.

De?nition6.(Link Radius)The link radius of a sensor

network is de?ned 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 bene?t 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 di?erent 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 bene?t of a candidate path in the weighted case is de?ned 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: Bene?t=(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.

De?nition7.(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 de?ned as the maximum weighted communication distance between any two sensors whose sensing regions intersect.2

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 bene?t 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 bene?cial 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.

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 bene?cial 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 bene?t of each candidate path in SP at each stage.

2.To compute the bene?t 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 di?-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 su?ciently 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 naive?ooding-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 su?cient 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 e?ect 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.

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 de?ned 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 “in?ate”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 signi?-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 di?erent 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 ?ooding approach,whenever the query runs for more than about 7times –longer runs giving more energy saving bene?ts.

6.RELATED WORK

The work most closely related to ours is that by Slijepc-sevic and Potkonjak [25],where the authors consider power-e?cient 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

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

102030405060702

3

4

5678

9

N o . o f m e s s a g e s (D ) i n t h o u s a n d s

Transmission radius (t)

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

(a)Communication cost (D )05

101520253035404550552

3

4

56

7

89

T h r e s h o l d v a l u e o f q

Transmission radius (t)

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

(b)Threshold value q θ

Figure 5:The communication cost (D )for the distributed algorithm and the threshold value of q (q θ)shown for various transmission radii and number of sensors.monitored/query area.As only one set of sensors need to be active at any time,their technique results in energy savings while preserving coverage.They only present a centralized algorithm which does not extend easily to a distributed algo-rithm.Moreover,they do not consider the communication cost incurred in the execution of their heuristic or the query.Hence,they do not require the selected sets to be connected.We should note that a repeated execution of our algorithm gives a good heuristic for the problem addressed in their work.In other closely related work,Shakkottai et al.in [24]consider an unreliable sensor grid-network and derive neces-sary and su?cient conditions for the coverage of the region and connectivity of the network in terms of the transmission radius,sensing radius,and failure rate of the sensors.

In [21],the authors formulate coverage problems to ad-dress the quality of service (surveillance)provided by a sen-sor network.In particular,they address the problem of ?nd-ing maximal paths of lowest and highest observabilities in a sensor network,which is very di?erent than our connected sensor coverage problem.The work in [19]addresses the problem of selecting a set of k base stations from a given set of n stations to maximize radio coverage.The issue of connectivity,query execution,or energy-e?ciency does not arise in the radio coverage setting.

There has been a signi?cant amount of work on developing e?cient mechanisms to broadcast a message in a mobile ad hoc network.The idea here is to suppress redundant broad-casts by using only a small number of nodes to broadcast but ensuring that all the nodes in the network receive the broadcast message.The above described problem of select-ing a minimum number of nodes such that each node in the network is either selected or a neighbor of a selected node is known as the minimum dominating connected set (MDCS)problem [14].The work in wireless network research com-munity [9,18,26,1,7]has primarily focussed on developing energy-e?cient distributed algorithms to construct a near-optimal dominating connected set.However,the notion of dominating set is signi?cantly di?erent than that of sensor cover.

Other related problems based on various other notions of coverage are as follows.The Art Gallery Problem [20,10]considers placement of observers in a room such that each point in the room is “seen”by at least one observer.The Art Gallery Problem was solved optimally in 2D and shown to be NP-hard in 3D case.The essential di?erence of the Art Gallery and the related problems with our connected sensor coverage problem is that the Art Gallery and related prob-lems require an optimal placement of observers,while our problem deals with an optimal selection of already placed sensors.From that perspective,the geometric variations [16,17,5]of the classic set cover problem are more related to our problem.However,none of the geometric set cover variations addressed in the literature deal with the notion of connectivity.For the disk-cover problem [5],there is a poly-nomial algorithm that delivers a constant-factor approxima-tion,however,the approximation algorithm does not gener-alize to other geometric regions (not even rectangles)and due to involved computation required,the straightforward distributed implementation would incur a very large number of messages.

There has been some other work done on optimizing en-ergy consumption in sensor networks.For example,in [6],heuristic techniques have been designed to put sensor net-work nodes in inactive states based on the observed con-nectivity in the network and loss of messages.In [15],a randomized clustering algorithm has been devised to select cluster heads in a sensor network so that the energy budget for relaying information to a gateway is distributed evenly among sensor nodes.None of the above work deals with the notions of spatial coverage or connectivity.

7.CONCLUSIONS

We have designed e?cient algorithms for self-organization in sensor networks.The self-organization algorithms exploit the redundancy in the sensor network to select a small subset of sensors (called connected sensor cover )that is su?cient to process a given query.The motivation is to conserve the overall battery power of the network.We show that the

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

centralized algorithm computes a near-optimal solution–within logarithmic bound of the optimal.The distributed version uses certain optimizations to reduce message over-heads and the simulations show that the size of the solution delivered is of almost the same size as the centralized algo-rithm.

The sensors that are not selected in the connected sensor cover are not used during query execution,but may be used during the self-organization phase.Since the communica-tion cost incurred in a query execution is proportional to the number of sensors involved,our scheme is able to reduce communication cost substantially.The cost savings are pro-portional to(i)the density of the network(which re?ects on the redundancy)and(ii)the number of times the query is run–longer running queries result in greater cost savings as it reduces the amortized overhead cost of running the self-organization algorithm.We show through simulations that the overhead cost is indeed small enough that running queries for more than a few times(about7)starts generating cost savings for a wide range of sensor network parameters. The weighted version algorithm takes into account the re-maining battery power in the sensors so that sensors running low on battery has a smaller chance of being selected in the connected sensor cover.This gives a tremendous?exibil-ity for balancing the available energy budget in the network among all sensors,thus providing a longer operational life time.It also worthwhile to note that while we focused pri-marily on communication cost savings as a method to con-serve battery power,our technique can potentially provide further savings depending on the architecture of the sen-sor.For example,the sensors not in the connected sensor cover can be put to sleep for the duration of time the query is to run(assuming,of course,that they are not used for other concurrent queries).Our technique can also be used to compute multiple disjoint connected sensor covers in a distributed manner.Multiple connected sensor covers can be useful for very long running queries;di?erent covers can be used at di?erent times to balance the battery drain over di?erent sensors.

8.ACKNOWLEDGEMENTS

Samir Das’s work has been partially supported by NSF grant ANI-0308631.

9.REFERENCES

[1]K.M.Alzoubi,P.-J.Wan,and O.Frieder.

Message-optimal connected dominating sets in mobile ad hoc networks.In Proc.of the Symp.on Mobile ad

hoc networking and computing,2002.

[2]B.Badrinath,M.Srivastava,K.Mills,J.Scholtz,and

K.Sollins,editors.Special Issue on Smart Spaces and Environments,IEEE Personal Communications,2000.

[3]P.Berman and V.Ramaiyer.Improved approximation

algorithms for the steiner tree problem.J.Algorithms, 1994.

[4]P.Bonnet,J.Gehrke,and P.Seshadri.Towards sensor

database systems.In Proc.of Intl.Conf.on Mobile

Data Management,2001.

[5]H.Bonnimann and M.Goodrich.Almost optimal set

covers in?nite vc-dimension.Discrete Computational

Geometry,14,1995.

[6]A.Cerpa and D.Estrin.Ascent:Adaptive

self-con?guring sensor networks topologies.In Proc.of the Conf.on Computer Communications

(INFOCOM),2002.

[7]Y.Chen and A.Liestman.Approximating minimum

size weakly-connected dominating sets for clustering

mobile ad hoc networks.In Proc.of the Symp.on

Mobile ad hoc networking and computing,2002.

[8]T.Cormen,C.Lieserson,R.Rivest,and C.Stein.

Introduction to Algorithms.McGraw Hill,2001.

[9]B.Das,R.Sivakumar,and V.Bhargavan.Routing in

ad hoc networks using a spine.In Proceedings of the

Intl.Conf.on Computer Communications and

Networks(IC3N),1997.

[10]M.de Berg,M.van Kreveld,M.Overmans,and

putational Geometry:Algorithms and Applications.Springer-Verlag,2000.

[11]B.Deb,S.Bhatnagar,and B.Nath.Multiresolution

state retrieval in sensor networks.In Proceedings of

International Workshop on Sensor Network Protocols and Applications(SNPA),2003.

[12]D.Estrin,R.Govindan,and J.Heidemann,editors.

Special Issue on Embedding the Internet,

Communications of the ACM,volume43,2000. [13]R.Govindan,J.Hellerstein,W.Hong,S.Madden,

M.Franklin,and S.Shenker.The sensor network as a database.Technical report,University of Southern

California,Computer Science Department,2002. [14]S.Guha and S.Khuller.Approximation algorithms for

connected dominating sets.Algorithmica,20(4),1998.

[15]W.R.Heinzelman,A.Chandrakasan,and

H.Balakrishnan.Energy-e?cient communication

protocol for wireless microsensor networks.In Proc.of Intl.Conf.on System Sciences(HICSS),2000. [16]V.S.A.Kumar,S.Arya,and H.Ramesh.Hardness of

set cover with intersection1.In Automata,Languages and Programming,2000.

[17]V.S.A.Kumar and H.Ramesh.Covering rectilinear

polygons with axis-parallel rectangles.In ACM-SIAM Symp.on Theory of Computing,1999.

[18]ouiti,A.Qayyum,and L.Viennot.Multipoint

relaying:An e?cient technique for?ooding in mobile wireless networks.In Proc.of the Hawaii Intl.Conf.

on System Sciences(HICSS),2002.

[19]K.Lieska,itinen,and hteenmaki.Radio

coverage optimization with genetic algorithms.In

Proc.of IEEE Int.Symp.on Personal,Indoor,and

Mobile Radio Communications(PIMRC),1998. [20]M.Marengoni,B.Draper,A.Hanson,and

R.Sitaraman.System to place observers on a

polyhedral terrain in polynomial time.Image and

Visual Computing,1996.

[21]S.Meguerdichian,F.Koushanfar,M.Potkonjak,and

M.Srivastava.Coverage problems in wireless ad-hoc

sensor networks.In Proc.of the Conf.on Computer

Communications(INFOCOM),2001.

[22]S.Meguerdichian,F.Koushanfar,G.Qu,and

M.Potkonjak.Exposure in wireless ad-hoc sensor

networks.In Proceedings of the International

Conference on Mobile Computing and Networking

(MobiCom),2001.

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

[23]G.Pottie and W.Kaiser.Wireless sensor networks.

Communications of the ACM,43,2002.

[24]S.Shakkottai,R.Srikant,and N.Shro?.Unreliable

sensor grids:Coverage,connectivity and diameter.In Proceedings of INFOCOM(to appear),2003.

[25]S.Slijepcevic and M.Potkonjak.Power e?cient

organization of wireless sensor networks.In Proc.of

IEEE Intl.Conf.on Communications(ICC),2001.

[26]J.Wu and H.Li.A dominating-set-based routing

scheme in ad hoc wireless networks.

Telecommunication Systems Journal,3,2001.

本文来源：https://www.bwwdw.com/article/3g5j.html