UCC: update-conscious compilation for energy efficiency in wireless sensor networks

ABSTRACT

Wireless sensor networks (WSN), composed of a large number of low-cost, battery-powered sensors, have recently emerged as promising computing platforms for many non-traditional applications. The preloaded code on remote sensors often needs to be updated after deployment in order for the WSN to adapt to the changing demands from the users. Post-deployment code dissemination is challenging as the data are transmitted via battery-powered wireless communication. Recent studies show that the energy for sending a single bit is about the same as executing 1000 instructions in aWSN. Therefore it is important to achieve energy efficiency in code dissemination.

In this paper, we propose novel update-conscious compilation(UCC) techniques for energy-efficient code dissemination in WSNs. An update-conscious compiler, when compiling the modified code, includes the compilation decisions that were made when generating the old binary. The compiler employs a detailed energy model and strives to match the old decisions for a more energy-efficient result. In most cases, matching the previous decisions improves the binary code similarity, reduces the amount of data to be transmitted to remote sensors, and thus, consumes less energy. In this paper, we develop update-conscious register allocation and data layout algorithms. Our experimental results show that they can achieve great improvements over the traditional, update-oblivious approaches.

REFERENCES

• 1: Preston Briggs , Keith D. Cooper , Linda Torczon, Improvements to graph coloring register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.428-455, May 1994 [doi>10.1145/177492.177575]
• 2: Michel Berkelaar et al., LP solve 5.5.
• 3: Edgar H. Callaway, Wireless Sensor Networks: Architectures and Protocols, CRC Press, Inc., Boca Raton, FL, 2003
• 4: Gregory J. Chaitin,Marc A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins, and Peter W. Markstein, "Register Allocation via Coloring," Computer Languages, 6:45--57, 1981.
• 5: Frederick Chow , John Hennessy, Register allocation by priority-based coloring, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.222-232, June 17-22, 1984, Montreal, Canada
• 6: Wei Dai, The Crypto++ Library, http://www.eskimo.com/ weidai/cryptlib.html .
• 7: Adam Dunkels , Niclas Finne , Joakim Eriksson , Thiemo Voigt, Run-time dynamic linking for reprogramming wireless sensor networks, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182810]
• 8: Prabal K. Dutta , Jonathan W. Hui , David C. Chu , David E. Culler, Securing the deluge Network programming system, Proceedings of the fifth international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127826]
• 9: David W. Goodwin , Kent D. Wilken, Optimal and near-optimal global register allocations using 0–1 integer programming, Software—Practice & Experience, v.26 n.8, p.929-965, Aug. 1996 [doi>10.1002/(SICI)1097-024X(199608)26:8<929::AID-SPE40>3.3.CO;2-K]
• 10: Lal George , Andrew W. Appel, Iterated register coalescing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.3, p.300-324, May 1996 [doi>10.1145/229542.229546]
• 11: 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]
• 12: Jaein Jeong, and David E. Culler, "Incremental Network Programming for Wireless Sensors," IEEE Sensor and Ad Hoc Communications and Networks (SECON), pages 25--33, 2004.
• 13: Philo Juang , Hidekazu Oki , Yong Wang , Margaret Martonosi , Li Shiuan Peh , Daniel Rubenstein, Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with ZebraNet, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 14: Joseph M. Kahn, Randy Howard Katz, and Kristofer S. J. Pister, "Emerging Challenges: Mobile Networking for 'Smart Dust' " Journal of Communications and Networks, 2(3):188--196, 2000.
• 15: David Ryan Koes , Seth Copen Goldstein, A global progressive register allocator, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 16: Joel Koshy, and Raju Pandey, "Remote Incremental Linking for Energy-Efficient Reprogramming of Sensor Networks," European Workshop on Wireless Sensor Networks, pages 354--365, 2005.
• 17: Sandeep S. Kulkarni , Limin Wang, MNP: Multihop Network Reprogramming Service for Sensor Networks, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems (ICDCS'05), p.7-16, June 06-10, 2005 [doi>10.1109/ICDCS.2005.50]
• 18: Patrick E. Lanigan , Rajeev Gandhi , Priya Narasimhan, Sluice: Secure Dissemination of Code Updates in Sensor Networks, Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, p.53, July 04-07, 2006 [doi>10.1109/ICDCS.2006.77]
• 19: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 20: Philip Levis , David Culler, Maté: a tiny virtual machine for sensor networks, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 21: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang , Albert Wang, Storage assignment to decrease code size, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.186-195, June 18-21, 1995, La Jolla, California, United States
• 22: Mayur Naik , Jens Palsberg, Compiling with code-size constraints, Proceedings of the joint conference on Languages, compilers and tools for embedded systems: software and compilers for embedded systems, June 19-21, 2002, Berlin, Germany
• 23: Pedro Jose Marron, Matthias Gauger, Andreas Lachenmann, Daniel Minder, Olga Saukh, and Kurt Rothermel, "FlexCup: A Flexible and Efficient Code Update Mechanism for Sensor Networks," European Workshop on Wireless Sensor Networks (EWSN), pages 212--227, 2006.
• 24: Nonlinear Mixed Integer Programming. http://projects.coinor.org/Bonmin.
• 25: Rajesh K. Panta, Issa Khalil, and Saurabh Bagchi, "Stream: Low Overhead Wireless Reprogramming for Sensor Networks," IEEE Conference on Computer Communications (Infocom), 2007.
• 26: Carl von Platen , Johan Eker, Feedback linking: optimizing object code layout for updates, Proceedings of the 2006 ACM SIGPLAN/SIGBED conference on Language, compilers, and tool support for embedded systems, June 14-16, 2006, Ottawa, Ontario, Canada
• 27: Massimiliano Poletto , Vivek Sarkar, Linear scan register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.5, p.895-913, Sept. 1999 [doi>10.1145/330249.330250]
• 28: Niels Reijers , Koen Langendoen, Efficient code distribution in wireless sensor networks, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941350.941359]
• 29: Victor Shnayder , Mark Hempstead , Bor-rong Chen , Geoff Werner Allen , Matt Welsh, Simulating the power consumption of large-scale sensor network applications, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031518]
• 30: M. P. Bivens , M. L. Soffa, Incremental register reallocation, Software—Practice & Experience, v.20 n.10, p.1015-1047, Oct. 1990 [doi>10.1002/spe.4380201005]
• 31: TinyOS. http://www.tinyos.net/.
• 32: Ben L. Titzer , Daniel K. Lee , Jens Palsberg, Avrora: scalable sensor network simulation with precise timing, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 33: Omri Traub , Glenn Holloway , Michael D. Smith, Quality and speed in linear-scan register allocation, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.142-151, June 17-19, 1998, Montreal, Quebec, Canada
• 34: Mica2 Wireless Measurement System. http://www.xbow.com/.
• 35: Fan Ye , Gary Zhong , Songwu Lu , Lixia Zhang, GRAdient broadcast: a robust data delivery protocol for large scale sensor networks, Wireless Networks, v.11 n.3, p.285-298, May 2005 [doi>10.1007/s11276-005-6612-9]
• 36: Xiaotong Zhuang , Santosh Pande, Differential register allocation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

General Terms:
Design, Languages, Performance

Keywords:
code dissemination, register allocation, sensor networks