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, and Linda Torczon, "Improvements to Graph Coloring Register Allocation," ACM Transactions on Programming Languages Systems, 16(3):428--455, May 1994.
[2]
Michel Berkelaar et al., LP solve 5.5.
[3]
Edgar H. Callaway, Jr. Wireless Sensor Networks: Architectures and Protocols, CRC Press, 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, and John Hennessy, "Register Allocation by Prioritybased Coloring," ACM SIGPLAN Symposium on Compiler Construction, pages 222--232, 1984.
[6]
Wei Dai, The Crypto++ Library, http://www.eskimo.com/ weidai/cryptlib.html .
[7]
Adam Dunkels, Niclas Finne, Joakim Eriksson, and Thiemo Voigt, "Run-Time Dynamic Linking for Reprogramming Wireless Sensor Networks," ACM International Conference on Embedded Networked Sensor Systems (SenSys), pages 15--28, 2006.
[8]
Prabal K. Dutta, Jonathan W. Hui, David C. Chu, and David E. Culler, "Securing the Deluge Network Programming System," International Symposium on Information Processing in Sensor Networks (IPSN), pages 326--333, 2006.
[9]
David W. Goodwin, and Kent D. Wilken, "Optimal and Near-optimal Global Register Allocations using 0/1 Integer Programming," Software: Practice and Experience, 26(8):929--965, 1996.
[10]
Lal George, and Andrew W. Appel, "Iterated Register Coalescing," ACM Transactions on Programming Languages and Systems, 18(3):300--324, 1996.
[11]
Jonathan W. Hui, and David E. Culler, "The Dynamic Behavior of a Data Dissemination Protocol for Network Programming at Scale," ACM International Conference on Embedded Networked Sensor Systems(SenSys), pages 81--94, 2004.
[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, and Daniel Rubenstein, "Energy Efficient Computing for Wildlife Tracking: Design Tradeoffs and Early Experiences with ZebraNet," ACM/IEEE International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 96--107, 2002.
[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, and Seth Copen Goldstein, "A Global Progressive Register Allocator," ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 204--215, 2006.
[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, and Limin Wang, "Mnp: Multihop Network Reprogramming Service for Sensor Networks," International Conference on Distributed Computing Systems (ICDCS), 2005.
[18]
P. E. Lanigan, R. Gandhi, and P. Narasimhan, "Sluice: Secure Dissemination of Code Updates in Sensor Networks," International Conference on Distributed Computing Systems (ICDCS), 2006.
[19]
Chunho Lee, Miodrag Potkonjak, and William H. Mangione-Smith, "MediaBench: A Tool for Evaluating and Synthesizing Multimedia and Communications Systems," International Symposium on Microarchitecture (MICRO), pages 330--335, 1997.
[20]
Philip Levis, and David Culler, "Mate: A Tiny Virtual Machine for Sensor Networks," International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 85--95, 2002.
[21]
Stan Liao, Srinivas Devadas, Kurt Keutzer, Steven Tjiang, and Alvert Wang, "Storage Assignment to Decrease Code Size," ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 235--253, 1995.
[22]
Mayur Naik, and Jens Palsberg, "Compiling with Code-size Constraints," ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES), pages 120--129, 2002.
[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, and Johan Eker, "Feedback Linking: Optimizing Object Code Layout for Updates," ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES), pages 2--11, 2006.
[27]
Massimiliano Poletto, and Vivek Sarkar, "Linear Scan Register Allocation," ACM Transactions on Programming Languages and Systems, 21(5):895--913, 1999.
[28]
Niels Reijers, and Koen Langendoen, "Efficient Code Distribution in Wireless Sensor Networks," International Workshop on Wireless Sensor Network Architecture, pages 60--67, 2003.
[29]
Victor Shnayder, Mark Hempstead, Ror-rong Chen, Geoff Werner Allen, and Matt Welsh, "Simulating the Power Consumption of Large-Scale Sensor Network Applications," ACM Conference on Embedded Networked Sensor Systems (SenSys), pages 188--200, 2004.
[30]
Mary P. Bivens, and Mary Lou Soffa, "Incremental Register Allocation," Software: Practice and Experience, 20(10):1015--1047, 1990.
[31]
TinyOS. http://www.tinyos.net/.
[32]
Ben L. Titzer, Daniel K. Lee, and Jens Palsberg, "Avrora: Scalable Sensor Network Simulation with Precise Timing," International Symposium on Information Processing in Sensor Networks (IPSN), pages 477--482, 2005.
[33]
Omri Traub, Glenn Holloway, and Michael D. Smith, "Quality and Speed in Linear-scan Register Allocation," ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 142--151, 1998.
[34]
Mica2 Wireless Measurement System. http://www.xbow.com/.
[35]
Fan Ye, Gary Zhong, Songwu Lu, and Lixia Zhang, "GRAdient Broadcast: A Robust Data Delivery Protocol for Large Scale Sens or Networks," ACM Wireless Networks, 11(2):285--298, 2005.
[36]
Xiaotong Zhuang, and Santosh Pande, "Differential Register allocation," ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 168--179, 2006.
Index Terms
- UCC: update-conscious compilation for energy efficiency in wireless sensor networks
Recommendations
UCC: update-conscious compilation for energy efficiency in wireless sensor networks
PLDI '07: Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and ImplementationWireless 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 ...
Towards update-conscious compilation for energy-efficient code dissemination in WSNs
Postdeployment code dissemination in wireless sensor networks (WSN) is challenging, as the code has to be transmitted via energy-expensive wireless communication. In this article, we propose novel update-conscious compilation (UCC) techniques to achieve ...
MNP: Multihop Network Reprogramming Service for Sensor Networks
ICDCS '05: Proceedings of the 25th IEEE International Conference on Distributed Computing SystemsReprogramming of sensor networks is an important and challenging problem as it is often necessary to reprogram the sensors in place. In this paper, we propose a multihop reprogramming service designed for Mica-2/XSM motes. One of the problems in ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2007508 pagesISBN:9781595936332DOI:10.1145/1250734- General Chair:
- Jeanne Ferrante,
- Program Chair:
- Kathryn S. McKinley
Copyright © 2007 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 10 June 2007
Published in SIGPLAN Volume 42, Issue 6
Check for updates
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations42Total Citations
- 494Total Downloads
- Downloads (Last 12 months)7
- Downloads (Last 6 weeks)0
Reflects downloads up to 31 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in