research-article

Minimum-hot-spot query trees for wireless sensor networks

Authors:

Georgios Chatzimilioudis,

Demetrios Zeinalipour-Yazti,

Dimitrios GunopulosAuthors Info & Claims

MobiDE '10: Proceedings of the Ninth ACM International Workshop on Data Engineering for Wireless and Mobile Access

Pages 33 - 40

https://doi.org/10.1145/1850822.1850829

Published: 06 June 2010 Publication History

Abstract

We propose a distributed algorithm to construct a balanced communication tree that serves in gathering data from the network nodes to a sink. Our algorithm constructs a near-optimally balanced communication tree with minimum overhead. The balancing of the node degrees results in the minimization of packet collisions during query execution, that would otherwise require numerous retransmissions and reduce the lifetime of the network. We compare our simple distributed algorithm against previous work and a centralized solution and show that for most network layouts it outperforms competition and achieves tree balance very close to the centralized algorithm. It also has the smallest energy overhead possible to construct the tree, increasing the lifetime of the network even more.

References

[1]

P. Andreou, A. Pamboris, D. Zeinalipour-Yazti, P. K. Chrysantbis, and G. Samaras. Etc: Energy-driven tree construction in wireless sensor networks. In Mobile Data Management, pages 513--518, 2009.

Digital Library

[2]

R. E. Burkard, M. Dell' Amico, and S. Martello. Assignment Problems. SIAM, Philadelphia, 2009.

Digital Library

[3]

A. T. Campbell, S. B. Eisenman, N. D. Lane, E. Miluzzo, R. A. Peterson, H. Lu, X. Zheng, M. Musolesi, K. Fodor, and G.-S. Ahn. The rise of people-centric sensing. IEEE Internet Computing, 12:12--21, 2008.

Digital Library

[4]

G. J. Chang and P.-H. Ho. The β-assignment problem in general graphs. Comput. Oper. Res., 24(8):757--765, 1997.

Digital Library

[5]

R. S. Chang and R. C. T. Lee. On a scheduling problem where a job can be executed only by a limited number of processors. Comput. Oper. Res., 15(5):471--478, 1988.

Digital Library

[6]

Y. L. Chen and Y. H. Chin. Scheduling unit-time jobs on processors with different capabilities. Comput. Oper. Res., 16(5):409--417, 1989.

Digital Library

[7]

H. Dai and R. Han. A node-centric load balancing algorithm for wireless sensor networks. In Global Telecommunications Conference, volume 1, pages 548--552, December 2003.

[8]

B. Das and V. Bharghavan. Routing in ad-hoc networks using minimum connected dominating sets, pages 376--380, 1997.

[9]

W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy-efficient communication protocol for wireless microsensor networks. In HICSS Hawaii International Conference on System Sciences, Washington, DC, 2000.

Digital Library

[10]

J. C. G. Jacob. De investigando ordine systematis aequationum differentialum vulgarium cujuscunque. 5:193--216, 1890.

[11]

J. Kacer. Discrete event simulations with j-sim. In Intermediate Representation Engineering for virtual machines, pages 13--18, Dublin, Ireland, 2002.

Digital Library

[12]

S. Kim, R. Fonseca, P. Dutta, A. Tavakoli, D. Culler, P. Levis, S. Shenker, and I. Stoica. Flush: a reliable bulk transport protocol for multihop wireless networks. In SenSys'07, pages 351--365, Sydney, Australia, 2007.

Digital Library

[13]

S. Kim, S. Pakzad, D. E. Culler, J. Demmel, G. Fenves, S. Glaser, and M. Turon. Health monitoring of civil infrastructures using wireless sensor networks. In IPSN, pages 254--263, Cambridge, Massachusetts, USA, 2007.

Digital Library

[14]

J. F. Kurose and K. Ross. Computer Networking: A Top-Down Approach Featuring the Internet. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2002.

Digital Library

[15]

J. Li, A. Deshpande, and S. Khuller. On computing compression trees for data collection in sensor networks. CoRR, abs/0907.5442, 2009.

Digital Library

[16]

S. Lindsey, C. S. Raghavendra, and K. M. Sivalingam. Data gathering algorithms in sensor networks using energy metrics. IEEE Parallel Distrib. Syst., 13(9):924--935, 2002.

Digital Library

[17]

S. Madden, M. J. Franklin, J. Hellerstein, and W. Hong. Tag: a tiny aggregation service for ad-hoc sensor networks. In In OSDI, 2002.

Digital Library

[18]

S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong. Tinydb: an acquisitional query processing system for sensor networks. ACM Trans. Database Syst., 30(1):122--173, 2005.

Digital Library

[19]

R. Murty, A. Gosain, M. Tierney, A. Brody, A. Fahad, J. Bers, and M. Welsh. Citysense: A vision for an urban-scale wireless networking testbed. In International Conference on Technologies for Homeland Security, Waltham, MA, 2008.

[20]

N. A. Pantazis, D. J. Vergados, D. D. Vergados, and C. Douligeris. Energy efficiency in wireless sensor networks using sleep mode tdma scheduling. Ad Hoc Networks, 7(2):322--343, 2009.

Digital Library

[21]

S. Singh and C. S. Raghavendra. Pamas---power aware multi-access protocol with signalling for ad hoc networks. SIGCOMM Comput. Commun. Rev., 28(3):5--26, 1998.

Digital Library

[22]

R. Szewczyk, E. Osterweil, J. Polastre, M. Hamilton, A. M. Mainwaring, and D. Estrin. Habitat monitoring with sensor networks. Communications ACM, 47(6):34--40, 2004.

Digital Library

[23]

V. Tsaoussidis and H. G. Badr. Tcp-probing: Towards an error control schema with energy and throughput performance gains. In ICNP, pages 12--21, 2000.

Digital Library

[24]

Voltree-Power-Incorporated. http://www.voltreepower.com/.

[25]

Y. Xu, J. Heidemann, and D. Estrin. Geography-informed energy conservation for ad hoc routing. In Mobile computing and networking, pages 70--84, New York, NY, USA, 2001.

Digital Library

[26]

T. Yan, Y. Bi, L. Sun, and H. Zhu. Probability based dynamic load-balancing tree algorithm for wireless sensor networks. In Int. Conf. Networking and Mobile Computing, 2005.

Digital Library

[27]

Y. Yao and J. Gehrke. Query processing in sensor networks. In CIDR, Conf. on Innovative Data Systems Research, 2003.

[28]

W. Ye, J. Heidemann, and D. Estrin. Medium access control with coordinated adaptive sleeping for wireless sensor networks. IEEE/ACM Trans. Netw., 12(3):493--506, 2004.

Digital Library

[29]

D. Zeinalipour-Yazti, P. Andreou, P. K. Chrysanthis, and G. Samaras. Mint views: Materialized in-network top-k views in sensor networks. In MDM, pages 182--189, 2007.

Digital Library

[30]

D. Zeinalipour-Yazti, S. Lin, V. Kalogeraki, D. Gunopulos, and W. A. Najjar. Microhash: An efficient index structure for flash-based sensor devices. In FAST, pages 31--44, 2005.

Digital Library

[31]

P. Zhang, C. M. Sadler, S. A. Lyon, and M. Martonosi. Hardware design experiences in zebranet. In SenSys, pages 227--238, Baltimore, MD, USA, 2004.

Digital Library

[32]

Q. Zhang, Z. Xie, W. Sun, and B. Shi. Tree structure based data gathering for maximum lifetime in wireless sensor networks. In APWeb, Asia-Pacific Web Conference, pages 513--522, Shanghai, China, 2005. Springer.

Digital Library

Cited By

Pearl Datta STiwari K(2024)A SURVEY ON STRATEGIES TO MITIGATE HOT SPOT PROBLEM IN WIRELESS SENSOR NETWORKSShodhKosh: Journal of Visual and Performing Arts10.29121/shodhkosh.v5.i5.2024.18555:5Online publication date: 31-May-2024
https://doi.org/10.29121/shodhkosh.v5.i5.2024.1855
B RKayiram KLalitha R(2021)Query Optimization Techniques in Wireless Sensor Network: A Review2021 6th International Conference on Communication and Electronics Systems (ICCES)10.1109/ICCES51350.2021.9488988(1053-1059)Online publication date: 8-Jul-2021
https://doi.org/10.1109/ICCES51350.2021.9488988
Draz UAli TYasin SBukhari SKhan MHamdi MRahman SJung LAli A(2021)An Optimal Scheme for UWSAN of Hotspots Issue Based on Energy-Efficient Novel Watchman NodesWireless Personal Communications10.1007/s11277-021-08624-8Online publication date: 29-Jun-2021
https://doi.org/10.1007/s11277-021-08624-8
Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MobiDE '10: Proceedings of the Ninth ACM International Workshop on Data Engineering for Wireless and Mobile Access

June 2010

97 pages

ISBN:9781450301510

DOI:10.1145/1850822

General Chairs:
Phillip B. Gibbons
Intel Labs Pittsburgh
,
Demetris Zeinalipour
University of Cyprus
,
Program Chairs:
Hui Lei
IBM T.J. Watson Research Center
,
Suman Nath
Microsoft Research

Copyright © 2010 ACM.

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 profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

MobiDE'10

Sponsor:

SIGMOD

MobiDE'10: Ninth International ACM Workshop on Data Engineering for Wireless and Mobile Access

June 6, 2010

Indiana, Indianapolis

Acceptance Rates

Overall Acceptance Rate 23 of 59 submissions, 39%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
136
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Pearl Datta STiwari K(2024)A SURVEY ON STRATEGIES TO MITIGATE HOT SPOT PROBLEM IN WIRELESS SENSOR NETWORKSShodhKosh: Journal of Visual and Performing Arts10.29121/shodhkosh.v5.i5.2024.18555:5Online publication date: 31-May-2024
https://doi.org/10.29121/shodhkosh.v5.i5.2024.1855
B RKayiram KLalitha R(2021)Query Optimization Techniques in Wireless Sensor Network: A Review2021 6th International Conference on Communication and Electronics Systems (ICCES)10.1109/ICCES51350.2021.9488988(1053-1059)Online publication date: 8-Jul-2021
https://doi.org/10.1109/ICCES51350.2021.9488988
Draz UAli TYasin SBukhari SKhan MHamdi MRahman SJung LAli A(2021)An Optimal Scheme for UWSAN of Hotspots Issue Based on Energy-Efficient Novel Watchman NodesWireless Personal Communications10.1007/s11277-021-08624-8Online publication date: 29-Jun-2021
https://doi.org/10.1007/s11277-021-08624-8
Chatzimilioudis GCosta CZeinalipour-Yazti DLee W(2017)Crowdsourcing emergency data in non-operational cellular networksInformation Systems10.1016/j.is.2015.11.00464:C(292-302)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1016/j.is.2015.11.004
Kim YBok KSon IPark JLee BYoo J(2017)Positioning sensor nodes and smart devices for multimedia data transmission in wireless sensor and mobile P2P networksMultimedia Tools and Applications10.1007/s11042-016-3794-376:16(17193-17211)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1007/s11042-016-3794-3
Park JPark HSeong DYoo J(2013)A Sensor Positioning Scheme with High Accuracy in Nonuniform Wireless Sensor NetworksInternational Journal of Distributed Sensor Networks10.1155/2013/5076059:6(507605)Online publication date: Jan-2013
https://doi.org/10.1155/2013/507605
Chatzimilioudis GCuzzocrea AGunopulos DMamoulis N(2013)A novel distributed framework for optimizing query routing trees in wireless sensor networks via optimal operator placementJournal of Computer and System Sciences10.1016/j.jcss.2012.09.01379:3(349-368)Online publication date: 1-May-2013
https://dl.acm.org/doi/10.1016/j.jcss.2012.09.013
Abdulla ANishiyama HAnsari NKato N(2013)Energy-Aware Routing for Wireless Sensor NetworksThe Art of Wireless Sensor Networks10.1007/978-3-642-40009-4_7(201-234)Online publication date: 14-Dec-2013
https://doi.org/10.1007/978-3-642-40009-4_7
Kleerekoper AFiler N(2012)Trading latency for load balancing in many-to-one wireless networksWireless Telecommunications Symposium 201210.1109/WTS.2012.6266133(1-9)Online publication date: Apr-2012
https://doi.org/10.1109/WTS.2012.6266133
Valkanas GGunopulos DGalpin IGray AFernandes A(2011)Extending query languages for in-network query processingProceedings of the 10th ACM International Workshop on Data Engineering for Wireless and Mobile Access10.1145/1999309.1999318(34-41)Online publication date: 12-Jun-2011
https://dl.acm.org/doi/10.1145/1999309.1999318
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten