臺灣博碩士論文加值系統

隨著無線傳輸與嵌入式系統相關技術的進步，無線感測網路(Wireless Sensor Network, WSN)已成為具有高度發展性的資訊技術，在許多領域已被廣泛的應用與研究。軟體動態更新(Dynamic Update)機制在WSN的相關研究中，是個非常重要且具有挑戰性的議題。感測節點藉由軟體動態的更新，可以改進與増加軟體功能，符合更多實際環境的變化與不同應用的需求。許多研究使用Diff-based的動態更新方式，在更新時不需要傳送完整的程式映像檔，只需要傳送新舊檔案差異的部分，是個較有效率的更新方式。然而，Diff-based的動態更新方式比在更新的過程中傳遞完整的映像檔的方式在處理上複雜許多，尤其感測節點的資源是很有限的，如何降低對感測節點資源的消耗，並且有效率的完成動態更新的動作，即是本論文主要研究與探討的議題。
在本論文中，針對有資源限制的WSN環境下，基於Diff-based的動態更新方式，我們提出了一個新的且更有效率的元件動態更新機制，稱為Two-Stage Diff，目的是減少傳送更新資料的大小與提昇更新時的效率，同時考量Flash Memory的抹除(Erase)與寫入的特性，並設計與優化Diff Script，使我們的機制更適合使用在資源有限的WSN環境。
我們將所提的Two-Stage Diff元件動態更新機制實作於TinyOS系統上，我們主要是修改了在TinyOS上支援的Deluge動態更新機制來實作我們的Diff-based的動態更新方式。實驗結果顯示，當對感測節點進行動態更新時，我們的Two-Stage Diff可以有效地減少所需傳送的更新資料，且只需要Deluge的0.2%-49%的封包傳輸量。同時，感測節點執行更新的時間也大幅地降低，如在小量更新的情況下，比起Deluge效能更可以提升22.64倍。

As the advance of wireless communication and embedded system technologies, wireless sensor networks (WSNs) which consist of lots of sensor nodes with various sensing technologies nowadays have versatile applications in lots of fields and become a highly developed nature of information technology. Supporting dynamic software update mechanism is a very important and challenging topic in the related researches of WSNs. If a WSN platform can support remote dynamic update, software of sensor nodes can be dynamically updated or enhanced to adapt to changed environmental conditions or different requirements of applications. Many researches on dynamic updates use the diff-based approaches that do not transmit the whole new program image to sensor nodes for updating. Only the code difference needs to be transmitted to sensor nodes. Compared with the approaches basing on full image replacement, diff-based approaches are more effective whereas more complicated in processing. However, sensor nodes are often of limited energy, memory, processing power, and communication bandwidth. How to efficiently provide dynamic update in WSNs while reducing resource consumption of sensor nodes is the main concern of this thesis.
In this thesis, for the resource limited WSN environments, we propose a new and more effective diff-based approach named Two-Stage Diff to dynamically update software components in sensor nodes. This mechanism aims at effectively reducing the transmission size of the update data and improving the efficiency of the update processing. Especially, flash memory characteristics in erasing and data writing are considered in our design. Besides, the design of Diff Script format is optimized to further decrease the size of transmitted update data. Such that, our mechanism can reduce the resource consumption incurred by dynamic update mechanism and be more suitable for operating in resource limited WSN environments.
We have implemented the proposed Two-Stage Diff mechanism in TinyOS for component update. We mainly modify Deluge dynamic update mechanism to support our diff-based component update mechanism. Experiments show that when performing updates, our Two-Stage Diff can effectively reduce the size of transmitted update data and require only 0.2%-49% of packet transmission as compared with Deluge. At the same time, the update processing time can be largely reduced as well. For example, Two-State Diff can perform 22.64 times better than Deluge in the case of small amount of updating.

Table of Contents V
List of Figures VII
List of Tables VII
Chapter 1 Introduction 1
Chapter 2 Background and Related Work 6
2.1 TinyOS 6
2.2 Dynamic Update Mechanisms 8
2.2.1 Full Image Replacement 8
2.2.1 .1 Crossbow In-Network Programming(XNP) 9
2.2.1 .2 Multi-hop Over-the-Air Programming (MOAP) 10
2.2.1.3 Deluge 11
2.2.2 Diff-based Approaches 13
2.2.2.1 Efficient Code Distribution 14
2.2.2.2 Incremental Network Programming 16
2.2.2.3 Remote Incremental Linking 17
2.2.2.4 FlexCup 19
2.2.3 Loadable Modules 21
2.3 Other Related Work 22
Chapter 3 System Design and Implementation 26
3.1 Motivation 27
3.2 Architecture Overview 31
3.3 Generate executable image for sensor node 37
3.4 The Proposed Dynamic Update Mechanism 43
3.4.1 The 1st Symbol Diff 43
3.4.2 The 2nd Symbol Diff and Content Diff 51
3.4.3 Diff-Script Format 56
3.5 The proposed Patch Agent 59
Chapter 4 Performance Evaluation 63
4.1 Experimental Environment 63
4.2 Experimental Setup 65
4.2.1 Selected Applications 65
4.2.2 Test Scenarios 66
4.3 Program Code Analysis 69
4.4 Size Comparison for Update Data 70
4.5 Comparison of Elapsed Time for Updating Sensor Node 72
Chapter 5 Conclusions and Future Work 75
References 77

[1]A. Arora et al, “A Line in the Sand: A Wireless Sensor Network for Target Detection, Classification and Tracking,” Military Communications Systems and Technologies, Volume 46, Issue 5, pp. 605-634, Computer Networks, 5, December 2004.
[2]K. Lorincz, D. Malan, T. Fulford-Jones, A. Nawoj, A. Clavel, V. Shnayder, M. Welsh, and S. Moulton, “Sensor Networks for Emergency Response: Challenges and Opportunities,” IEEE Pervasive Computing, v.3 n.4, pp.16-23, October 2004.
[3]J. D. Lundquist, D. R. CAyan, and M. D. Dettinger, “Meteorology and Hydrology in Yosemite National Park: A Sensor Network Application,” Information Processing in Sensor Networks, pp. 518-528. Springer-Verlag, 2003.
[4]T.Y. Huang, K.Y. Hou, H.Y. Yu, E. Chu, and C.T. King, “LA-TinyOS: A Locality-aware Operating System for Wireless Sensor Networks,” in Proc. SAC’07, Mar. 2007.
[5]J. Koshy and R. Pandey, “Remote incremental linking for energy-efficient reprogramming of Sensor networks,” In Proc. of the 2nd European Workshop on Wireless Sensor Networks, pp. 354-365, 2005.
[6]J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, and K. Pister, “System architecture directions for networked sensors,” In Proc. of the 9th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems, pp. 93-104, 2000.
[7]D. Gay, P. Levis, R. von Behren, M. Welsh, E. Brewer, and D. Culler, “The nesC language: A holistic approach to networked embedded systems,” In: Proc. of the ACM SIGPLAN 2003 Conf. on Programming Language Design and Implementation, pp. 1-11, 2003.
[8]Crossbow Technology Inc., IRIS Motes, http://www.xbow.com.
[9]Crossbow Technology Inc. Mote In-Network Programming User Reference, 2003. http://www.xbow.com.
[10]T. Stathopoulos, J. Heidemann, and D. Estrin, “A remote code update mechanism for wireless Sensor networks,” Technical Report CENS-TR-30, University of California, Los Angeles, Center for Embedded Networked Computing, November 2003.
[11]J. W. Hui and D. Culler, “The dynamic behavior of a data dissemination protocol for network programming at scale,” 2nd Intl. Conf. on Embedded Networked Sensor Systems, pp. 81-94, 2004.
[12]N. Reijers and K. Langendoen, “Efficient code distribution in wireless Sensor networks,” Proc. of the 2nd ACM Intl. Conf. on Wireless Sensor Networks and Applications, pp. 60-67, 2003.
[13]J. Jong and D. Culler, “Incremental network programming for wireless sensors,” First IEEE International Conference on Sensor and Ad Hoc Communications and Networks, Oct. 2004.
[14]Andrew Tridgell, “Efficient Algorithms for Sorting and Synchronization,” PhD thesis, Australian National University, 1999.
[15]R. Quong and M. Linton, “Linking programs incrementally,” ACM Transactions on Programming Languages and Systems, 13(1), pp. 1-20, 1991.
[16]J. MacDonald, “File system support for delta compression,” Master thesis, Department of Electrical Engineering and Computer Science, University of California at Berkeley, 2000.
[17]P. Marr´on et al., “FlexCup: A flexible and efficient code update mechanism for Sensor networks,” in European Workshop on Wireless Sensor Networks, 2006.
[18]C. Han, R. K. Rengaswamy, R. Shea, E. Kohler, and M. Srivastava, “SOS: A dynamic operating system for Sensor networks,” in MobiSys’ 05, 2005.
[19]T. Liu, M. Martonosi, “Impala: A middleware system for managing autonomic, parallel Sensor systems,” In Proc. of the 9th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming, pp. 107-118, 2003.
[20]A. Dunkels, B. Gr¨onvall, and T. Voigt, “Contiki - a lightweight and flexible operating system for tiny networked sensors,” In Proceedings of the First IEEE Workshop on Embedded Networked Sensors, 2004 (IEEE EmNetS-I).
[21]W. Dong, C. Chen, X. Liu, K. Zheng, and J. Bu, “SenSpire OS: A Predictable, Flexible, and Efficient OS for Wireless Sensor Networks,” Technical report, ZJUCS-2008-01, Zhejiang University, 2008.
[22]R. K. Panta, S. Bagchi, and S. P. Midkiff, “Zephyr: Efficient Incremental Reprogramming of Sensor Nodes using Function Call Indirections and Difference Computation,” In Proceedings of USENIX Annual Technical Conference, 2009.
[23]P. Levis and D. Culler, “Mat´e: a tiny virtual machine for Sensor networks,” In Proceedings of the Eleventh Conference on Architectural Support for Programming Languages and Operating Systems, pp. 85-95, Oct. 2002.
[24]N. Tsiftes, A. Dunkels, and T. Voigt, “Efficient Sensor Network Reprogramming through Compression of Executable Modules,” In IEEE SECON, 2008.
[25]H. Lekatsas and W. Wolf, “Code compression for embedded systems,” in Design Automation Conference, 1998, pp. 516–521.
[26]Pascal von Rickenbach and Roger Wattenhofer, “Differential Code Updates in Wireless Sensor Networks” , http://dcg.ethz.ch/publications/techreport280.pdf
[27]J. J. Hunt, K.-P. Vo, and W. F. Tichy, “Delta Algorithms: An Empirical Analysis,” ACM Trans. Software Engineer-ing and Methodology, vol. 7, no. 2, pp. 192–214, 1998.
[28]Rahul Kapur, Tom Yeh, and Ujjwal Lahoti, “Differential Wireless Reprogramming of Sensor Networks,” UCLA CS213 Project Report, December 2003.
[29]Qing Cao, Tarek Abdelzaher, John Stankovic, and Tian He, “The LiteOS Operating System: Towards Unix-Like Abstractions for Wireless Sensor Networks,” Proceedings of the 7th international conference on Information processing in Sensor networks, pp.233-244, April 22-24, 2008.
[30]P. Levis, N. Patel, D. Culler, and S. Shenker, “Trickle: A self-regulating algorithm for code propagation and maintenance in wireless Sensor networks,” in Proc. NSDI’04, Mar. 2004.
[31]C. Percival, “Naive Differences of Executable Code,” Draft Paper, http://www.daemonology.net/bsdiff.
[32]SourceForge Technology Inc., TinyOS CVS repository, http://tinyos.cvs.sourceforge.net/viewvc/tinyos/
[33]王彥程, “一個有效率的無線感測網路動態更新機制”, 國立中興大學資訊科學研究所碩士論文, 2006.