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

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

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科Connected Sensor Cover Self-Organization of Sensor Networks for Efficient Query Execution(21)全文阅读和word下载服务。