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 reflects 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 tremendousflexibil-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;different covers can be used at different times to balance the battery drain over different 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 infinite vc-dimension.Discrete Computational

Geometry,14,1995.

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

self-configuring 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-efficient 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 efficient technique forflooding 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.