In-network surface simplification for sensor fields

ABSTRACT

Recent research literature on sensor network databases has focused on finding ways to perform in-network aggregation of sensor readings to reduce the message cost. However, with these techniques information about the state at a particular location is lost. In many applications such as visualization, finite element analysis, and cartography, constructing a field from all sensor readings is very important. However, requiring all sensors to report their readings to a centralized station adversely impacts the life span of the sensor network. In this paper we focus on modeling sensor networks as a field deployed in a physical space and exploiting in-network surface simplification techniques to reduce the message cost. In particular, we propose two schemes for performing in-network surface simplification, namely (1) a hierarchical approach and (2) a triangulation based approach. We focus on a quad tree based method and a decimation method for the two approaches respectively. The quad tree based method employs an incremental refinement process during reconstruction using increasingly finer levels of detail sent by selected sensors. It has a guaranteed error bound. The decimation method starts with a triangulation of all sensors and probabilistically selects sensors not to report to prevent error accumulation. To demonstrate the performance, the two simplification techniques are compared with the naive approach of having all sensors report. Experimental results show that both techniques provide substantial message savings compared to the naivealgorithm, usually requiring less than 80% as many messages and less than 50% for some data sets. Furthermore, though the decimation algorithm does not provide a guaranteed error bound, for our experiments less than 4.5% of the interpolated values exceeded the given bound.

REFERENCES

• 1: Boulat A. Bash , John W. Byers , Jeffrey Considine, Approximately uniform random sampling in 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.1052206]
• 2: P. Bonnet, J. E. Gehrke, and P. Seshadri. Querying the physical world. IEEE Personal Communications, 2000.
• 3: Philippe Bonnet , Johannes Gehrke , Praveen Seshadri, Towards Sensor Database Systems, Proceedings of the Second International Conference on Mobile Data Management, p.3-14, January 08-10, 2001
• 4: Device Database Systems, Proceedings of the 16th International Conference on Data Engineering, p.194, February 28-March 03, 2000
• 5: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 6: Deepak Ganesan , Ben Greenstein , Denis Perelyubskiy , Deborah Estrin , John Heidemann, An evaluation of multi-resolution storage for sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958502]
• 7: S. Goel, A. Passarella, and T. Imielinski. Using buddies to live longer in a boring world, 2004. Rutgers Department of Computer Science Technical Report DCS-TR-558.
• 8: Ben Greenstein , Eddie Kohler , David Culler , Deborah Estrin, Distributed Techniques for Area Computation in Sensor Networks, Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks (LCN'04), p.533-541, November 16-18, 2004 [doi>10.1109/LCN.2004.45]
• 9: P. S. Heckbert and M. Garland. Survey of polygonal surface simplification algorithms. Technical report, 1997.
• 10: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 11: Xin Li , Young Jin Kim , Ramesh Govindan , Wei Hong, Multi-dimensional range queries in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958500]
• 12: 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]
• 13: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, The design of an acquisitional query processor for sensor networks, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872817]
• 14: Samuel Madden , Robert Szewczyk , Michael J. Franklin , David Culler, Supporting Aggregate Queries Over Ad-Hoc Wireless Sensor Networks, Proceedings of the Fourth IEEE Workshop on Mobile Computing Systems and Applications, p.49, June 20-21, 2002
• 15: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 16: William J. Schroeder , Jonathan A. Zarge , William E. Lorensen, Decimation of triangle meshes, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.65-70, July 1992
• 17: Mehdi Sharifzadeh , Cyrus Shahabi, Supporting spatial aggregation in sensor network databases, Proceedings of the 12th annual ACM international workshop on Geographic information systems, November 12-13, 2004, Washington DC, USA [doi>10.1145/1032222.1032248]
• 18: N. Trigoni, Y. Yao, A. Demers, J. Gehrke, and R. Rajaraman. WaveScheduling: Energy-Efficient Data Dissemination for Sensor Networks. Internet Draft, 2004.
• 19: Y. Yao and J. Gehrke. The cougar approach to in-network query processing in sensor networks. In SIGMOD, 2002.
• 20: Yong Yao , Johannes Gehrke, The cougar approach to in-network query processing in sensor networks, ACM SIGMOD Record, v.31 n.3, September 2002 [doi>10.1145/601858.601861]
• 21: Y. Yao and J. E. Gehrke. Query Processing in Sensor Networks. In Proc. of the First Biennial Conference on Innovative Data Systems Research (CIDR), 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Management, Performance

Keywords:
energy efficient, in-network surface simplification, sensor field