Sweeps over wireless sensor networks

ABSTRACT

We present a robust approach to data collection, aggregation, and dissemination problems in sensor networks. Our method is based on the idea of a sweep over the network: a wavefront that traverses the network, passes over each node exactly once, and performs the desired operation(s). We do not require global information about the sensor field such as node locations. Instead, in a preprocessing phase, we compute a potential function over the network whose gradients guide the sweep process. The sweep itself operates asynchronously, using only local operations to advance the wavefront. The gradient information provides a local ordering of the nodes that helps reduce the number of MAC-layer collisions as the wavefront advances, while also globally shaping the wavefront so as to conform to the sensor field layout. The approach is robust to both link volatility and node failures that may be present in real network conditions. The potential is computed by a stable diffusion process in which each node repeatedly set its potential to the average of the potentials of its neighbors. Aggregation paths are decided on-line as the sweep proceeds and no fixed tree structure is needed over the course of the computation. We present simulation results illustrating the correctness of the algorithm and comparing the performance of the sweep to aggregation trees under various network conditions.

REFERENCES

• 1: John Byers , Jeffrey Considine , Michael Mitzenmacher , Stanislav Rost, Informed content delivery across adaptive overlay networks, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 2: I. Chlamtac and O. Weinstein. The wave expansion approach to broadcasting in multihop radio networks. IEEE Transactions on Communications, 39(3):426--433, 1991.
• 3: Jeffrey Considine , Feifei Li , George Kollios , John Byers, Approximate Aggregation Techniques for Sensor Databases, Proceedings of the 20th International Conference on Data Engineering, p.449, March 30-April 02, 2004
• 4: Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
• 5: Q. Fang, J. Gao, L. Guibas, V. de Silva, and L. Zhang. GLIDER: Gradient landmark-based distributed routing for sensor networks. In Proc. IEEE Conference on Computer Communications (INFOCOM), 2005.
• 6: S. P. Fekete, A. Krller, D. Pfisterer, S. Fischer, and C. Buschmann. Neighborhood-based topology recognition in sensor networks. In the First International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS), 2004.
• 7: Michael S. Floater , Martin Reimers, Meshless parameterization and surface reconstruction, Computer Aided Geometric Design, v.18 n.2, p.77-92, March. 2001 [doi>10.1016/S0167-8396(01)00013-9 ]
• 8: Stefan Funke, Topological hole detection in wireless sensor networks and its applications, Proceedings of the 2005 joint workshop on Foundations of mobile computing, September 02-02, 2005, Cologne, Germany [doi>10.1145/1080810.1080819]
• 9: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 10: Jonathan W. Hui , David Culler, The dynamic behavior of a data dissemination protocol for network programming at scale, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031506]
• 11: D. Kotz, C. Newport, and C. Elliott. The mistaken axioms of wireless-network research. Technical report, Dartmouth College Computer Science Technical Report TR2003-467, 2003.
• 12: Alexander Kröller , Sándor P. Fekete , Dennis Pfisterer , Stefan Fischer, Deterministic boundary recognition and topology extraction for large sensor networks, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1000-1009, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109668]
• 13: Philip Levis , Nelson Lee , Matt Welsh , David Culler, TOSSIM: accurate and scalable simulation of entire tinyOS applications, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958506]
• 14: P. Levis, N. Patel, D. E. Culler, and S. Shenker. Trickle: A self-regulating algorithm for code propagation and maintenance in wireless sensor networks. In NSDI, pages 15--28, 2004.
• 15: 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]
• 16: Suman Nath , Phillip B. Gibbons , Srinivasan Seshan , Zachary R. Anderson, Synopsis diffusion for robust aggregation in sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031525]
• 17: Joseph Polastre , Jonathan Hui , Philip Levis , Jerry Zhao , David Culler , Scott Shenker , Ion Stoica, A unifying link abstraction for wireless sensor networks, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098928]
• 18: Ananth Rao , Christos Papadimitriou , Scott Shenker , Ion Stoica, Geographic routing without location information, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938996]
• 19: S. Ren, Q. Li, H. Wang, and X. Zhang. Design and analysis of wave sensing scheduling protocols for object-tracking applications. In DCOSS-Distributed Computing of Sensor Systems, pages 228--243, 2005.
• 20: J. G. T.K. Dey and S. Goswami. Shape segmentation and matching with flow discretization. In the 8th International Workshop on Algorithms and Data Structures (WADS), pages 25--36, 2003.
• 21: Niki Trigoni , Yong Yao , Alan Demers , Johannes Gehrke , Rajmohan Rajaraman, WaveScheduling: energy-efficient data dissemination for sensor networks, Proceeedings of the 1st international workshop on Data management for sensor networks: in conjunction with VLDB 2004, August 30-30, 2004, Toronto, Canada [doi>10.1145/1052199.1052209]
• 22: R. G. Yonggang Jerry Zhao and D. Estrin. Computing aggregates for monitoring wireless sensor networks. In The First IEEE International Workshop on Sensor Network Protocols and Applications (SNPA 03), Anchorage, AK, USA, May 11 2003.
• 23: D. Young. Interative methods for solving partial differential equations of elliptic type, 1950. Doctoral Thesis, Harvard University.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology; Network communications

General Terms:
Algorithms, Design

Keywords:
distributed protocols, sensor networks, topology