Alternating multiple tributaries + deltas

ABSTRACT

This work addresses the problem of trading off the latency in delivering the answer to the sink at the benefit of balancing the spatial dispersion of the energy consumption among the nodes and, consequently, prolonging the lifetime in sensor networks. Typically, in response to a query that pertains to the data from some geographic region, a tree structure is constructed and, when possible, some in-network aggregation is performed. On the other hand, in order to increase the robustness and/or balance the load, multipath routing is employed. Motivated by earlier work that combined trees and multipaths [19], in this paper we explore the possibility, and the impact, of combining multiple trees and multiple multipaths for routing, when processing a query with respect to a given region of interest. We present and evaluate two approaches that enable load-balancing in terms of alternating among a collection of routing structures.

REFERENCES

• 1: K. Akkaya and M. Younis. A survey on routing protocols for wireless sensor networks. Ad Hoc Networks, 3(3), 2005.
• 2: Panayiotis Andreou , Demetrios Zeinalipour-Yazti , Panos K. Chrysanthis , George Samaras, Workload-Aware Query Routing Trees in Wireless Sensor Networks, Proceedings of the The Ninth International Conference on Mobile Data Management (mdm 2008), p.189-196, April 27-30, 2008 [doi>10.1109/MDM.2008.13]
• 3: Sergei Bespamyatnikh , David Kirkpatrick , Jack Snoeyink, Generalizing ham sandwich cuts to equitable subdivisions, Proceedings of the fifteenth annual symposium on Computational geometry, p.49-58, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304909]
• 4: Prosenjit Bose , Erik D. Demaine , Ferran Hurtado , John Iacono , Stefan Langerman , Pat Morin, Geodesic ham-sandwich cuts, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997821]
• 5: Nirupama Bulusu , John Heidemann , Deborah Estrin , Tommy Tran, Self-configuring localization systems: Design and Experimental Evaluation, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.1, p.24-60, February 2004 [doi>10.1145/972627.972630]
• 6: C. Buragohain, S. Gandhi, J. Hershberger, and S. Suri. Contour approximation in sensor networks. In DCOSS, 2006.
• 7: Qing Cao , Tarek Abdelzaher , Tian He , John Stankovic, Towards optimal sleep scheduling in sensor networks for rare-event detection, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 8: Crossbow Technology Inc. Mica2 wireless measurement sheet, http://www.xbow.com/.
• 9: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 10: Deepak Ganesan , Ramesh Govindan , Scott Shenker , Deborah Estrin, Highly-resilient, energy-efficient multipath routing in wireless sensor networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.5 n.4, October 2001 [doi>10.1145/509506.509514]
• 11: Y. Ganjali and A. Keshavarzian. Load balancing in ad hoc networks: Single-path routing vs. multi-path routing. In INFOCOM, 2004.
• 12: Michael T. Goodrich , Roberto Tamassia, Dynamic ray shooting and shortest paths in planar subdivisions via balanced geodesic triangulations, Journal of Algorithms, v.23 n.1, p.51-73, April 1997 [doi>10.1006/jagm.1995.0797]
• 13: A. Kaneko and M. Kano. Discrete geometry on red and blue points in the plane - a survey, 2003. http://gorogoro.cis.ibaraki.ac.jp/web/papers/kano2003-48.pdf.
• 14: Fabian Kuhn , Roger Wattenhofer , Aaron Zollinger, An algorithmic approach to geographic routing in ad hoc and sensor networks, IEEE/ACM Transactions on Networking (TON), v.16 n.1, p.51-62, February 2008 [doi>10.1109/TNET.2007.900372]
• 15: S. Lee and M. Gerla. Split multipath routing with maximally disjoint paths in ad hoc networks. In IEEE-ICC, 2001.
• 16: W. Luo, W. Liu, and Y. Zhang. Performance optimizatin using multipath routing in mobile ad hoc and wireless sensor networks. Combinatorial Optimization in Communication Networks, 2, 2005.
• 17: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for Ad-Hoc sensor networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060303]
• 18: Samuel R. Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TinyDB: an acquisitional query processing system for sensor networks, ACM Transactions on Database Systems (TODS), v.30 n.1, p.122-173, March 2005 [doi>10.1145/1061318.1061322]
• 19: Amit Manjhi , Suman Nath , Phillip B. Gibbons, Tributaries and deltas: efficient and robust aggregation in sensor network streams, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066191]
• 20: Dragos Niculescu , Badri Nath, Trajectory based forwarding and its applications, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939012]
• 21: G. Parissidis, V. Lenders, M. May, and B. Plattner. Multi-path routing protocols in wireless mobile and ad hoc networks: A quantitative comparison. In NEW2AN, 2006.
• 22: P. Thulasiraman, S. Ramasubramanian, and M. Krunz. Disjoint multipat routing to two distinct drains in a multi-drain sensor network. In INFOCOM, 2007.
• 23: Shibo Wu , K. Selçuk Candan, Power-aware single- and multipath geographic routing in sensor networks, Ad Hoc Networks, v.5 n.7, p.974-997, September, 2007 [doi>10.1016/j.adhoc.2006.04.007]
• 24: Yang Yang , Hui-Hai Wu , Hsiao-Hwa Chen, SHORT: shortest hop routing tree for wireless sensor networks, International Journal of Sensor Networks, v.2 n.5/6, p.368-374, July 2007 [doi>10.1504/IJSNET.2007.014360]
• 25: V. Zadorozhny, P. Chrysanthis, and A. Labrinidis. Algebraic optimization of data delivery patterns in mobile sensor networks. In MDDS Workshop, 2004.
• 26: W. Zhang and G. Cao. Optimizing tree reconifguration for mobile target tracking in sensor networks. In IEEE INFOCOM, 2004.
• 27: Wensheng Zhang , Guohong Cao , Tom La Porta, Dynamic proxy tree-based data dissemination schemes for wireless sensor networks, Wireless Networks, v.13 n.5, p.583-595, October 2007 [doi>10.1007/s11276-006-6254-6]
• 28: A. Zollinger. Geographic routing. In Algorithms for Sensor and Ad Hoc Networks, pages 161--185, 2007.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Keywords:
routing, sensor network