Scalable Incremental Network Programming for Multihop Wireless Sensors

Jaein Jeong, David Culler

Cisco Systems, San Jose, USA.
University of California, Berkeley, USA.

DOI: 10.4236/ijcns.2013.61005                

Abstract

We present a network programming mechanism that can flexibly and quickly re-task a large multi-hop network of wireless sensor nodes. Our mechanism allows each sensor node to be incrementally reprogrammed with heterogeneous images of native program code using Rsync block comparison algorithm, point-to-point routing with the BLIP IPv6 stack, and image volume management with Deluge2. With our re-tasking method, we demonstrate an order of magnitude speed-up on small code changes over non-incremental delivery. Our mechanism also scales sub-linearly in the diameter of the network. Collectively, these advancements qualitatively change the software life cycle of the embedded networked systems.

Keywords

Network Programming; Incremental Update; Multihop Networks; Heterogeneous Images

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	C.-J. M. Liang and R. Musaloiu-E., “Deluge t2—Programming Manual,” 2008. http://www.tinyos.net/tinyos-2.x/doc/html/deluge-t2-manual.html
[2]	S. Dawson-Haggerty, “Design, Implementation, and Evaluation of an Embedded ipv6 Stack,” M.S. Thesis, University of California, Berkeley, 2010.
[3]	A. Tridgell, “Efficient Algorithms for Sorting and Synchronization,” Ph.D. Thesis, Australian National University, Canberra, 1999.
[4]	Crossbow Technology, “Mote in Network Programming User Reference,” 2003. http://webs.cs.berkeley.edu/tos/tinyos-1.x/doc/Xnp.pdf
[5]	T. Stathopoulos, J. Heidemann and D. Estrin, “A Remote Code Update Mechanism for Wireless Sensor Networks, Cens Technical Report #30,” 2003. http://lecs.cs.ucla.edu/~thanos/moap-TR.pdf
[6]	J. W. Hui and D. Culler, “The Dynamic Behavior of a Data Dissemination Protocol for Network Programming at Scale,” ACM, New York, 2004.
[7]	D. E. Culler and J. Hui, “Eecs-194 sp08, Lab 1—Embedded Internet,” 2008. http://www.cs.berkeley.edu/~culler/eecs194/labs/lab1/EECS194Lab01.html
[8]	S. S. Kulkarni and L. Wang, “Multihop Network Reprogramming Service for Sensor Networks,” Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, Columbus, 10 June 2005, pp. 7-16.
[9]	P. Levis, N. Patel, S. Shenker and D. Culler, “Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks,” Proceedings of the First USENIX/ACM Symposium on Networked Systems Design and Implementation, San Francisco, March 2004, pp. 15-28.
[10]	P. Levis and D. Culler, “Maté: A Tiny Virtual Machine for Sensor Networks,” Proceedings of the 10th Annual Conference on Architectural Support for Programming Languages and Operating Systems, Vol. 30, No. 5, 2002, pp. 85-95.
[11]	J. Koshy and R. Pandey, “Vmstar: Synthesizing Scalable Runtime Environments for Sensor Networks,” Conference on Embedded Networked Sensor Systems, San Diego, 2-4 November 2005, pp. 243-254.
[12]	J. Koshy and R. Pandey, “Remote Incremental Linking for Energy Efficient Reprogramming of Sensor Networks,” Proceedings of the 2nd European Workshop on Wireless Sensor Networks, Istanbul, 31 January-2 February 2005, pp. 354-365.
[13]	N. Reijers and K. Langendoen, “Efficient Code Distribution in Wireless Sensor Networks,” Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and Applications, San Diego, 19 September 2003, pp. 60-67.
[14]	A. Dunkels, N. Finne, J. Eriksson and T. Voigt, “Run-Time Dynamic Linking for Reprogramming Wireless Sensor Networks,” ACM Press, New York, 2006, pp. 15-28.
[15]	W. Dong, C. Chen, X. Liu, J. Bu and Y. Gao, “A Lightweight and Density-Aware Reprogramming Protocol for Wireless Sensor Networks,” IEEE Transactions on Mobile Computing, Vol. 10, No. 10, 2011, pp. 1403-1415.
[16]	R. K. Panta and S. Bagchi, “Mitigating the Effects of Software Component Shifts for Incremental Reprogramming of Wireless Sensor Networks,” IEEE Transactions on Parallel and Distributed Systems, Vol. 23, No. 10, 2012, pp. 1882-1894. doi:10.1109/TPDS.2012.55
[17]	P. J. Marron, M. Gauger, A. Lachenmann, D. Minder, O. Saukh and K. Rothermel, “Flexcup: A Flexible and Efficient Code Update Mechanism for Sensor Networks,” in EWSN ‘06, Feb 2006.
[18]	K. Klues, C.-J. M. Liang, J. Paek, R. Musaloiu-E, P. Levis, A. Terzis and R. Govindan, “Tosthreads: Thread-Safe and Non-Invasive Preemption in Tinyos,” Proceedings of the 3rd European Workshop on Wireless Sensor Networks, Cork, 4-6 November 2009.
[19]	A. Muthitacharoen, B. Chen and D. Maziéres, “A Low- Bandwidth Network File System,” SOSP’01 Proceedings of the 18th ACM symposium on Operating Systems principles, Vol. 35, No. 5, 2001, pp. 174-187.
[20]	P. Deutsch, “Rfc 1950: Zlib Compressed Data Format Specification Version 3.3,” 1996. http://tools.ietf.org/html/rfc1950
[21]	R. Rivest, “The md5 Message-Digest Algorithm,” 1992. http://tools.ietf.org/html/rfc1321
[22]	J. Polastre, R. Szewczyk and D. Culler, “Telos: Enabling Ultra-Low Power Wireless Research,” 4th International Symposium on Information Processing in Sensor Networks, Los Angeles, 15 April 2005, pp. 364-369.
[23]	T. Yeh, H. Yamamoto and T. Stathopolous, “Over-The-Air Reprogramming of Wireless Sensor Nodes, Ucla ee202a Project Report,” 2003. http://www.cs.ucla.edu/~tomyeh/ee202a/project/EE202a final writeup.doc