Partially evaluated sensor networks: automatic specialization for heterogeneous wireless sensor & actuator networks

ABSTRACT

Wireless sensor and actuator networks consist of a large number of disparate computing devices that together aim to perform a common tasks. Management of large networks may become difficult, when the individual task of each of the devices is different from others, and memory restrictions prevent the devices from all carrying the same network-wide program. This paper presents a technique to specialize a single generic network-wide program into node-specific variants that are small enough to store in each device's memory and efficiently send across the network. We describe the details of our partial evaluation-based specializer and demonstrate that it achieves its goal of producing small device-specific programs, thereby making it a practical tool.

REFERENCES

• 1: Strohbach, M., Gellersen, H., Kortuem, G., Kray, C.: Cooperative artefacts: Assessing real world situations with embedded technology. In: Proceedings of the International Conference on Ubiquitous Computing (Ubicomp), Springer, Berlin, Heidelberg, New York (2004) 250--267
• 2: Evers, L., Havinga, P.J.M., Kuper, J., Lijding, M.E.M., Meratnia, N.: Sensorscheme: Supply chain management automation using wireless sensor networks. In: Proceedings of the 12th IEEE Conference on Emerging Technologies and Factory Automation, ETFA 2007, Patras, Greece, Los Alamitos, IEEE Computer Society Press (2007) 448--455
• 3: Decker, C., Beigl, M., Krohn, A., Robinson, P., Kubach, U.: eseal -- a system for enhanced electronic assertion of authenticity and integrity.
• 4: In Ferscha, A., Mattern, F., eds.: Pervasive. Volume 3001 of Lecture Notes in Computer Science., Springer (2004) 254--268
• 5: Nupur Kothari , Ramakrishna Gummadi , Todd Millstein , Ramesh Govindan, Reliable and efficient programming abstractions for wireless sensor networks, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 6: Li-Der Chou , Chun-Cheng Sheu , Home-Way Chen, Design and Prototype Implementation of A Novel Automatic Vehicle Parking System, Proceedings of the 2006 International Conference on Hybrid Information Technology, p.292-297, November 09-11, 2006 [doi>10.1109/ICHIT.2006.109]
• 7: Conner, W.S., Heidemann, J., Krishnamurthy, L., Wang, X., Yarvis, M.: Workplace applications of sensor networks. Technical report (2004)
• 8: Bestavros, A., Bradley, A., Kfoury, A., Ocean, M.: Snbench: a development and run-time platform for rapid deployment of sensor network applications. Broadband Networks, 2005 2nd International Conference on (2005) 957--966 Vol. 2
• 9: Steffan, J., Fiege, L., Cilia, M., Buchmann, A.: Towards multi-purpose wireless sensor networks (2005)
• 10: Moteiv: Tmote sky. (http://www.moteiv.com/products/tmotesky.php)
• 11: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 12: H. Abelson , R. K. Dybvig , C. T. Haynes , G. J. Rozas , N. I. Adams Iv , D. P. Friedman , E. Kohlbecker , G. L. Steele, Jr. , D. H. Bartley , R. Halstead , D. Oxley , G. J. Sussman , G. Brooks , C. Hanson , K. M. Pitman , M. Wand, Revised Report on the Algorithmic Language Scheme, Higher-Order and Symbolic Computation, v.11 n.1, p.7-105, August 1998 [doi>10.1023/A:1010051815785]
• 13: Jones, N., Sestoft, P., Sondergaard, H.: Mix: A self-applicable partial evaluator for experiments in compiler generation. Lisp and Symbolic Computation 2(1) (1989) 9--50.
• 14: Bondorf, A.: Similix manual, system version 4.0. Technical report (1991).
• 15: Charles Consel, A tour of Schism: a partial evaluation system for higher-order applicative languages, Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.145-154, June 14-16, 1993, Copenhagen, Denmark [doi>10.1145/154630.154645]
• 16: Erik Steven Ruf, Topics in online partial evaluation, Stanford University, Stanford, CA, 1993
• 17: Ryan Newton , Matt Welsh, Region streams: functional macroprogramming 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.1052213]
• 18: Ramakrishna Gummadi , Nupur Kothari , Ramesh Govindan , Todd Millstein, Kairos: a macro-programming system for wireless sensor networks, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom [doi>10.1145/1095810.1118600]
• 19: Hongzhou Liu , Tom Roeder , Kevin Walsh , Rimon Barr , Emin Gün Sirer, Design and implementation of a single system image operating system for ad hoc networks, Proceedings of the 3rd international conference on Mobile systems, applications, and services, June 06-08, 2005, Seattle, Washington [doi>10.1145/1067170.1067187]
• 20: Marcin Karpiński , Vinny Cahill, Stream-based macro-programming of wireless sensor, actuator network applications with SOSNA, Proceedings of the 5th workshop on Data management for sensor networks, August 24-24, 2008, Auckland, New Zealand [doi>10.1145/1402050.1402061]
• 21: Bischoff, U., Kortuem, G.: Rulecaster: A macroprogramming system for sensor networks. In: Proceedings OOPSLA Workshop on Building Software for Sensor Networks. (2006).
• 22: Amol Bakshi , Viktor K. Prasanna , Jim Reich , Daniel Larner, The Abstract Task Graph: a methodology for architecture-independent programming of networked sensor systems, Proceedings of the 2005 workshop on End-to-end, sense-and-respond systems, applications and services, June 05-05, 2005, Seattle, Washington

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Partial evaluation

General Terms:
Algorithms, Languages

Keywords:
partial evaluation, wireless sensor networks