請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/79028完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 郭大維(Tei-Wei Kuo) | |
| dc.contributor.author | Wei-Che Tsai | en |
| dc.contributor.author | 蔡維哲 | zh_TW |
| dc.date.accessioned | 2021-07-11T15:37:52Z | - |
| dc.date.available | 2025-08-18 | |
| dc.date.copyright | 2020-09-14 | |
| dc.date.issued | 2020 | |
| dc.date.submitted | 2020-08-18 | |
| dc.identifier.citation | [1] Farzad Samie, Lars Bauer, and Jörg Henkel. IoT technologies for embedded computing: A survey. In Proc. of IEEE/ACM CODES, 2016. [2] Josiah Hester and Jacob Sorber. The future of sensing is batteryless, intermittent, and awesome. In Proc. of ACM SenSys, 2017. [3] Hrishikesh Jayakumar, Kangwoo Lee, Woo Suk Lee, Arnab Raha, Younghyun Kim, and Vijay Raghunathan. Powering the internet of things. In Proc. of ACM ISLPED, page 375–380, 2014. [4] Kaisheng Ma, Yang Zheng, Shuangchen Li, Karthik Swaminathan, Xueqing Li, Yongpan Liu, Jack Sampson, Yuan Xie, and Vijaykrishnan Narayanan. Architecture exploration for ambient energy harvesting nonvolatile processors. In Proc. of IEEE HPCA, pages 526–537, 2015. [5] C.K. Kang, H. R. Mendis, C.H. Lin, M.S. Chen, and P.C. Hsiu. Everything leaves footprints: Hardware accelerated intermittent deep inference. IEEE TCAD, 39(11):3479–3491, 2020. [6] Graham Gobieski, Nathan Beckmann, and Brandon Lucia. Intelligence beyond the edge: Inference on intermittent embedded systems. In Proc. of ACM ASPLOS, pages 199–213, 2019. [7] Kasım Sinan Yıldırım, Amjad Yousef Majid, Dimitris Patoukas, Koen Schaper, Przemyslaw Pawelczak, and Josiah Hester. InK: Reactive kernel for tiny batteryless sensors. In Proc. of ACM SenSys, page 41–53, 2018. [8] Hashan Roshantha Mendis and PiCheng Hsiu. Accumulative display updating for intermittent systems. ACM TECS, 18(5s), 2019. [9] H. T. Kung and John T. Robinson. On optimistic methods for concurrency control. ACM TODS, 6(2):213–226, June 1981. [10] Butler W. Lampson. Atomic transactions. In Distributed Systems Architecture and Implementation, An Advanced Course, pages 246–265. Springer, 1980. [11] Joost S. M. Verhofstad. Recovery techniques for database systems. ACM CSUR, 10(2):167–195, 1978. [12] Philip A. Bernstein, Vassos Hadzilacos, and Nathan Goodman. Concurrency Control and Recovery in Database Systems. AddisonWesley, 1987. [13] Philip A. Bernstein and Nathan Goodman. Concurrency control in distributed database systems. ACM CSUR, 13(2):185–221, 1981. [14] Jim Gray. Notes on data base operating systems. In Operating Systems, An Advanced Course, page 393–481, 1978. [15] Nathan Goodman, Dale Skeen, Arvola Chan, Umeshwar Dayal, Stephen Fox, and Daniel Ries. A recovery algorithm for a distributed database system. In Proc. of ACM PODS, page 8–15, 1983. [16] Benjamin Ransford, Jacob Sorber, and Kevin Fu. Mementos: System support for long running computation on rfid scale devices. In Proc. of ACM ASPLOS, page 159–170, 2011. [17] Kiwan Maeng and Brandon Lucia. Adaptive dynamic checkpointing for safe efficient intermittent computing. In Proc. of USENIX OSDI, page 129–144, 2018. [18] H. Jayakumar, A. Raha, and V. Raghunathan. Quickrecall: A low overhead HW/ SW approach for enabling computations across power cycles in transiently powered computers. In Proc. of IEEE VLSID, pages 330–335, 2014. [19] D. Balsamo, A. S. Weddell, A. Das, A. R. Arreola, D. Brunelli, B. M. AlHashimi, G. V. Merrett, and L. Benini. Hibernus++: A self calibrating and adaptive system for transiently powered embedded devices. IEEE TCAD, 35(12):1968–1980, 2016. [20] J. Choi, H. Joe, Y. Kim, and C. Jung. Achieving stagnation free intermittent computation with boundary free adaptive execution. In Proc. of IEEE RTAS, pages 331–344, 2019. [21] Brandon Lucia and Benjamin Ransford. A simpler, safer programming and execution model for intermittent systems. In Proc. of ACM PLDI, page 575–585, 2015. [22] M. Xie, M. Zhao, C. Pan, Jingtong Hu, Y. Liu, and C. J. Xue. Fixing the broken time machine: Consistency aware checkpointing for energy harvesting powered nonvolatile processor. In Proc. of ACM/IEEE DAC, pages 1–6, 2015. [23] ChihKai Kang, ChunHan Lin, PiCheng Hsiu, and MingSyan Chen. Homerun: HW/SW co-design for program atomicity on self powered intermittent systems. InProc. of ACM/IEEE ISLPED, pages 29:1–29:6, 2018. [24] WeiMing Chen, YiTing Chen, PiCheng Hsiu, and TeiWei Kuo. Multiversion concurrency control on intermittent systems. In Proc. of ACM/IEEE ICCAD, pages 1–8, 2019. [25] Alexei Colin and Brandon Lucia. Chain: Tasks and channels for reliable intermittent programs. In Proc. of ACM OOPSLA, pages 514–530, 2016. [26] Kiwan Maeng, Alexei Colin, and Brandon Lucia. Alpaca: Intermittent execution without checkpoints. Proc. ACM Program. Lang., 1(OOPSLA), 2017. [27] S. Liu, W. Zhang, M. Lv, Q. Chen, and N. Guan. Latics: A low overhead adaptivetask based intermittent computing system. IEEE TCAD, 39(11):3711–3723, 2020. [28] W. Chen, P. Hsiu, and T. Kuo. Enabling failure resilient intermittently powered systems without runtime checkpointing. In Proc. of of ACM/IEEE DAC, pages 1–6,2019. [29] Kiwan Maeng and Brandon Lucia. Supporting peripherals in intermittent systems with just in time checkpoints. In Proc. of ACM PLDI, pages 1101–1116, 2019. [30] G. Berthou, T. Delizy, K. Marquet, T. Risset, and G. Salagnac. Sytare: A lightweight kernel for NVRAM based transiently powered systems. IEEE TC, 68(9):1390–1403, 2019. [31] Y. Lin, P. Hsiu, and T. Kuo. Autonomous I/O for Intermittent IoT Systems. In Proc. of IEEE/ACM ISLPED, pages 1–6, 2019. [32] Alessandro Torrisi, Davide Brunelli, and Kasim Sinan Yildirim. Zero power energy aware communication for transiently powered sensing systems. In Proc. of ENSsys,page 43–49, 2020. [33] Y. Wu, Z. Jia, F. Fang, and J. Hu. Cooperative communication between two transiently powered sensor nodes by reinforcement learning. IEEE TCAD, pages 1–1, 2021. [34] Kai Geissdoerfer and Marco Zimmerling. Bootstrapping batteryfree wireless networks. In Proc. of USENIX NSDI, 2021. [35] An Intermittent Operating System. https://github.com/EMCLabSinica/IntermittentOS. [36] Texas Instruments. MSP430FR5994 MCU. https://www.ti.com/product/MSP430FR5994. [37] Prem Prakash Jayaraman, Ali Yavari, Dimitrios Georgakopoulos, Ahsan Morshed, and Arkady Zaslavsky. Internet of things platform for smart farming: Experiences and lessons learnt. MDPI Sensors, 16(11), 2016. [38] Ramez Elmasri and Shamkant B. Navathe. Fundamentals of Database Systems. Pearson, 7th edition, 2015. [39] W. M. Chen, T. W. Kuo, and P. C. Hsiu. Enabling failure resilient intermittent systems without runtime checkpointing. IEEE TCAD, 39(12):4399–4412, 2020. [40] Jim Gray and Andreas Reuter. Transaction Processing: Concepts and Techniques. Morgan Kaufmann Publishers Inc., 1st edition, 1992. [41] Jasper de Winkel, Carlo Delle Donne, Kasim Sinan Yildirim, Przemysław Pawełczak, and Josiah Hester. Reliable timekeeping for intermittent computing. In Proc. of ACM ASPLOS, page 53–67, 2020. [42] Texas Instruments. LowPower Sub1 GHz RF transceiver datasheet. https://www.ti.com/lit/ds/symlink/cc1101.pdf. [43] An Intermittent Operating System for Intermittent Networks. https://anonymous.4open.science/r/7603c3cd0818414f94600e0a10e51a57/. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/79028 | - |
| dc.description.abstract | 智慧型的輕量分散式裝置所提供的應用已經在物聯網及無線感測網路等領域被大量使用，由於這些裝置的數量不斷成長，如何為這些裝置供電已成為關鍵挑戰。近年來，使用新興的能量攫取技術製成的自供電系統已成為替代電池的一項潛力替代方案。但由於些類能源本質上的不穩定，使得這樣的自供電系統呈現間歇運作的現象，因此也帶來在間歇運行下系統設計的挑戰。包括在間歇性運算下能實現並行運算、、非揮發性記憶體與處理器之間的資料一致性問題，及在分散式系統中，節點斷電導致整體性能下降的問題。我們首先採用了以時間序列為基礎的工作排程最佳化演算法，用以確保在分散式系統中併行工作的正確性。為了解決資料一致性問題，我們使用了可序列化驗證及分散式原子提交來保證提交的資料與處理器進度一致。接著我們分析間歇性在分散式系統中的行為，觀察節點斷電時可能導致的性能下降問題。並提出以替代資料來解決在資料存取上的性能下降問題。具體地說，該方法會在資料節點斷電時，自動尋找系統中其它有同樣資料的節點為替代。另外我們提出可累積式驗證提交，用以解決在驗證可序列化併行及提交改變時，節點斷電造成的效能下降。這個方法使得讓驗證及提交時的工作不會因為斷電而需要重做，以減少執行的時間。我自將這些設計在開源的即時作業系統上實作，並在實驗中增加最多百分之三十三的工作效率，以及降低百分之四十一的資料存取等待時間。 | zh_TW |
| dc.description.abstract | Internet of Things (IoT) devices are gradually adopting batteryless, energy harvesting solutions, thereby driving the development of an intermittent computing paradigm to accumulate computation progress across multiple power cycles. While many attempts have been made to enable standalone intermittent systems, less attention has focused on IoT networks formed by intermittent devices. We observe that the computation progress improved by distributed task concurrency in an intermittent network can be significantly offset by data unavailability due to frequent power failures. This paper presents an intermittentaware distributed concurrency control protocol which leverages existing data copies inherently created in the network to improve the computation progress of concurrently executed tasks. In particular, we propose a borrowingbased data management method to increase data availability and an intermittent twophase commit procedure incorporated with distributed backward validation to ensure data consistency in the network. The proposed protocol was integrated into a FreeRTOSextended intermittent operating system running on Texas Instruments devices. Experimental results across varied power sources and network sizes show that the computation progress can be significantly improved, and this improvement is more apparent under weaker power, where more devices will remain offline for longer duration. | en |
| dc.description.provenance | Made available in DSpace on 2021-07-11T15:37:52Z (GMT). No. of bitstreams: 1 U0001-1808202002153600.pdf: 3527927 bytes, checksum: cf197da5a9eb1682d87e20532be485ba (MD5) Previous issue date: 2020 | en |
| dc.description.tableofcontents | 口試委員會審定書 i 致謝 ii 中文摘要iii Abstract iv Contents v List of Figures vii List of Tables viii 1 Introduction 1 2 Background 5 2.1 Distributed Concurrency Control . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Intermittentaware Concurrency Control . . . . . . . . . . . . . . . . . . 6 3 Observation and Motivation 9 4 Intermittentaware Distributed Concurrency Control 11 4.1 Design Rationale and Challenges . . . . . . . . . . . . . . . . . . . . . . 11 4.2 Borrowingbased Data Management . . . . . . . . . . . . . . . . . . . . 12 4.2.1 Data Versions and Copies . . . . . . . . . . . . . . . . . . . . . 12 4.2.2 Borrowing Strategy . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.3 Intermittent Twophase Commit . . . . . . . . . . . . . . . . . . . . . . 14 4.3.1 Atomic Commit and Instant Recovery . . . . . . . . . . . . . . . 14 4.3.2 Atomicity and Durability Enforcement . . . . . . . . . . . . . . 15 4.4 Distributed Validation with Task Dependency . . . . . . . . . . . . . . . 16 v 4.4.1 Task Dependency Check . . . . . . . . . . . . . . . . . . . . . . 16 4.4.2 Distributed Backward Validation . . . . . . . . . . . . . . . . . . 17 4.4.3 Serializability Enforcement . . . . . . . . . . . . . . . . . . . . 18 5 An Operating System for Intermittent Networks 20 5.1 Data Manager . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 5.2 Validation Handler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5.3 Node Communications . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 6 Performance Evaluation 24 6.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 6.2 Forward Progress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 6.3 Blocking Time and Communication Overhead . . . . . . . . . . . . . . . 28 7 Discussion 31 8 Conclusion 32 Bibliography 33 | |
| dc.language.iso | en | |
| dc.subject | 自供電系統 | zh_TW |
| dc.subject | 物聯網 | zh_TW |
| dc.subject | 併行控制 | zh_TW |
| dc.subject | 間歇性系統 | zh_TW |
| dc.subject | 分散式系統 | zh_TW |
| dc.subject | data consistency | en |
| dc.subject | intermittent networks | en |
| dc.subject | batteryless devices | en |
| dc.subject | Distributed task concurrency | en |
| dc.title | 用於間歇性分散式嵌入式系統的併行控制方法 | zh_TW |
| dc.title | Intermittency-aware Concurrency Control for Distributed Embedded Systems | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 108-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.coadvisor | 修丕承(Pi-Cheng Hsiu) | |
| dc.contributor.oralexamcommittee | 徐慰中(Wei-Chung Hsu),洪士灝(Shih-Hao Hung),葉彌妍(Mi-Yen Yeh) | |
| dc.subject.keyword | 自供電系統,間歇性系統,併行控制,分散式系統,物聯網, | zh_TW |
| dc.subject.keyword | Distributed task concurrency,data consistency,batteryless devices,intermittent networks, | en |
| dc.relation.page | 37 | |
| dc.identifier.doi | 10.6342/NTU202003906 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2020-08-19 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊網路與多媒體研究所 | zh_TW |
| dc.date.embargo-lift | 2025-08-18 | - |
| 顯示於系所單位： | 資訊網路與多媒體研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| U0001-1808202002153600.pdf 未授權公開取用 | 3.45 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。