Article

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

Authors:

Jiang ZhengAuthors Info & Claims

PLDI '07: Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 383 - 393

https://doi.org/10.1145/1250734.1250778

Published: 10 June 2007 Publication History

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.

Digital Library

[2]

Michel Berkelaar et al., LP solve 5.5.

[3]

Edgar H. Callaway, Jr. Wireless Sensor Networks: Architectures and Protocols, CRC Press, 2003.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[10]

Lal George, and Andrew W. Appel, "Iterated Register Coalescing," ACM Transactions on Programming Languages and Systems, 18(3):300--324, 1996.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[27]

Massimiliano Poletto, and Vivek Sarkar, "Linear Scan Register Allocation," ACM Transactions on Programming Languages and Systems, 21(5):895--913, 1999.

Digital Library

[28]

Niels Reijers, and Koen Langendoen, "Efficient Code Distribution in Wireless Sensor Networks," International Workshop on Wireless Sensor Network Architecture, pages 60--67, 2003.

Digital Library

[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.

Digital Library

[30]

Mary P. Bivens, and Mary Lou Soffa, "Incremental Register Allocation," Software: Practice and Experience, 20(10):1015--1047, 1990.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[36]

Xiaotong Zhuang, and Santosh Pande, "Differential Register allocation," ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 168--179, 2006.

Digital Library

Cited By

Kachman OBalaz MMalik P(2019)Universal framework for remote firmware updates of low-power devicesComputer Communications10.1016/j.comcom.2019.03.014Online publication date: Apr-2019
https://doi.org/10.1016/j.comcom.2019.03.014
Zhang CAhn WZhang YChilders B(2016)Live code update for IoT devices in energy harvesting environments2016 5th Non-Volatile Memory Systems and Applications Symposium (NVMSA)10.1109/NVMSA.2016.7547182(1-6)Online publication date: Aug-2016
https://doi.org/10.1109/NVMSA.2016.7547182
Qiu JHunag LQian L(2016)LiREP: Lightweight incremental reprogramming of sensor nodes based on in-situ modification2016 International Conference on Computing, Networking and Communications (ICNC)10.1109/ICCNC.2016.7440699(1-6)Online publication date: Feb-2016
https://doi.org/10.1109/ICCNC.2016.7440699
Show More Cited By

Index Terms

UCC: update-conscious compilation for energy efficiency in wireless sensor networks
1. Networks
  1. Network services
    1. Network management
2. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

UCC: update-conscious compilation for energy efficiency in wireless sensor networks
Proceedings of the 2007 PLDI conference

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 ...
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 Systems

Reprogramming 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

cover image ACM Conferences

PLDI '07: Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation

June 2007

508 pages

ISBN:9781595936332

DOI:10.1145/1250734

General Chair:
Jeanne Ferrante
University of California, San Diego, USA
,
Program Chair:
Kathryn S. McKinley
University of Texas at Austin, USA

ACM SIGPLAN Notices Volume 42, Issue 6
Proceedings of the 2007 PLDI conference
June 2007
491 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1273442
Issue’s Table of Contents

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PLDI '07

Sponsor:

PLDI '07: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 10 - 13, 2007

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

41
Total Citations
View Citations
494
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kachman OBalaz MMalik P(2019)Universal framework for remote firmware updates of low-power devicesComputer Communications10.1016/j.comcom.2019.03.014Online publication date: Apr-2019
https://doi.org/10.1016/j.comcom.2019.03.014
Zhang CAhn WZhang YChilders B(2016)Live code update for IoT devices in energy harvesting environments2016 5th Non-Volatile Memory Systems and Applications Symposium (NVMSA)10.1109/NVMSA.2016.7547182(1-6)Online publication date: Aug-2016
https://doi.org/10.1109/NVMSA.2016.7547182
Qiu JHunag LQian L(2016)LiREP: Lightweight incremental reprogramming of sensor nodes based on in-situ modification2016 International Conference on Computing, Networking and Communications (ICNC)10.1109/ICCNC.2016.7440699(1-6)Online publication date: Feb-2016
https://doi.org/10.1109/ICCNC.2016.7440699
Gao YYang YZhen YDai Q(2015)Depth Error Elimination for RGB-D CamerasACM Transactions on Intelligent Systems and Technology10.1145/27359596:2(1-16)Online publication date: 22-Apr-2015
https://dl.acm.org/doi/10.1145/2735959
Tang ALu KWang YHuang JLi H(2015)A Real-Time Hand Posture Recognition System Using Deep Neural NetworksACM Transactions on Intelligent Systems and Technology10.1145/27359526:2(1-23)Online publication date: 31-Mar-2015
https://dl.acm.org/doi/10.1145/2735952
Kyan MSun GLi HZhong LMuneesawang PDong NElder BGuan L(2015)An Approach to Ballet Dance Training through MS Kinect and Visualization in a CAVE Virtual Reality EnvironmentACM Transactions on Intelligent Systems and Technology10.1145/27359516:2(1-37)Online publication date: 31-Mar-2015
https://dl.acm.org/doi/10.1145/2735951
Chen CCai JZheng JCham TShi G(2015)Kinect Depth Recovery Using a Color-Guided, Region-Adaptive, and Depth-Selective FrameworkACM Transactions on Intelligent Systems and Technology10.1145/27004756:2(1-19)Online publication date: 31-Mar-2015
https://dl.acm.org/doi/10.1145/2700475
Huang SMa JCheng PWang S(2015)A Hybrid Multigroup Coclustering Recommendation Framework Based on Information FusionACM Transactions on Intelligent Systems and Technology10.1145/27004656:2(1-22)Online publication date: 31-Mar-2015
https://dl.acm.org/doi/10.1145/2700465
Fire MElovici Y(2015)Data Mining of Online Genealogy Datasets for Revealing Lifespan Patterns in Human PopulationACM Transactions on Intelligent Systems and Technology10.1145/27004646:2(1-22)Online publication date: 31-Mar-2015
https://dl.acm.org/doi/10.1145/2700464
Huang YZhao MXue C(2015)Joint WCET and Update Activity Minimization for Cyber-Physical SystemsACM Transactions on Embedded Computing Systems10.1145/268053914:1(1-21)Online publication date: 21-Jan-2015
https://dl.acm.org/doi/10.1145/2680539
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents