Skip navigation

DSpace

機構典藏 DSpace 系統致力於保存各式數位資料(如:文字、圖片、PDF)並使其易於取用。

點此認識 DSpace
DSpace logo
English
中文
  • 瀏覽論文
    • 校院系所
    • 出版年
    • 作者
    • 標題
    • 關鍵字
  • 搜尋 TDR
  • 授權 Q&A
    • 我的頁面
    • 接受 E-mail 通知
    • 編輯個人資料
  1. NTU Theses and Dissertations Repository
  2. 電機資訊學院
  3. 電信工程學研究所
請用此 Handle URI 來引用此文件: http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/68382
完整後設資料紀錄
DC 欄位值語言
dc.contributor.advisor謝宏昀
dc.contributor.authorJian-Yuan Yuen
dc.contributor.author余建遠zh_TW
dc.date.accessioned2021-06-17T02:19:20Z-
dc.date.available2017-08-24
dc.date.copyright2017-08-24
dc.date.issued2017
dc.date.submitted2017-08-21
dc.identifier.citation[1] L. S. Committee et al., “Part 15.4: wireless medium access control (MAC) and physical layer (PHY) specifications for low-rate wireless personal area networks (LR-WPANs),” IEEE Computer Society, 2003.
[2] N. Accettura, E. Vogli, M. R. Palattella, L. A. Grieco, G. Boggia, and M. Dohler, “Decentralized traffic aware scheduling in 6TiSCH networks: De- sign and experimental evaluation,” IEEE Internet of Things Journal, vol. 2, no. 6, pp. 455–470, 2015.
[3] O. Durmaz Incel, A. Ghosh, B. Krishnamachari, and K. Chintalapudi, “Fast data collection in tree-based wireless sensor networks,” IEEE Transactions on Mobile Computing, vol. 11, no. 1, pp. 86–99, 2012.
[4] M. R. Palattella, N. Accettura, L. A. Grieco, G. Boggia, M. Dohler, and T. Engel, “On optimal scheduling in duty-cycled industrial IoT applications using IEEE802.15.4e TSCH, volume = 13, year = 2013,” IEEE Sensors Jour- nal, no. 10, pp. 3655–3666.
[5] H. Dai and R. Han, “A node-centric load balancing algorithm for wireless sensor networks,” in Global Telecommunications Conference, 2003. GLOBE- COM’03. IEEE, vol. 1. IEEE, 2003, pp. 548–552.
[6] Y. Jin, P. Kulkarni, J. Wilcox, and M. Sooriyabandara, “A centralized scheduling algorithm for IEEE 802.15.4e TSCH based industrial low power wireless networks,” in Wireless Communications and Networking Conference (WCNC), 2016 IEEE. IEEE, 2016, pp. 1–6.
[7] P. Thubert, R. Assimiti, and T. Watteyne, “An architecture for IPv6 over the TSCH mode of IEEE 802.15.4,” draft-ietf-6tisch-architecture-08 (work in progress), 2015.
[8] T. Winter, “RPL: IPv6 routing protocol for low-power and lossy networks,” 2012.
[9] Z. Shelby, K. Hartke, and C. Bormann, “The constrained application protocol (CoAP),” 2014.
[10] M. R. Palattella, N. Accettura, X. Vilajosana, T. Watteyne, L. A. Grieco, G. Boggia, and M. Dohler, “Standardized protocol stack for the internet of (important) things,” IEEE Communications Surveys and Tutorials, vol. 15, no. 3, pp. 1389–1406, 2013.
[11] J. Le Roux, “Path computation element (PCE) communication protocol (PCEP),” 2009.
[12] C. Schurgers and M. B. Srivastava, “Energy efficient routing in wireless sen- sor networks,” in Military communications conference, 2001. MILCOM 2001. Communications for network-centric operations: Creating the information force. IEEE, vol. 1. IEEE, 2001, pp. 357–361.
[13] M. Barcelo, A. Correa, X. Vilajosana, J. L. Vicario, and A. Morell, “Novel routing approach for the TSCH mode of IEEE 802.15. 14e in wireless sen- sor networks with mobile nodes,” in Vehicular Technology Conference (VTC Fall), 2014 IEEE 80th. IEEE, 2014, pp. 1–5.
[14] T. Watteyne, M. Palattella, and L. Grieco, “Using IEEE 802.15. 4e time- slotted channel hopping (TSCH) in the internet of things (IoT): Problem statement,” Tech. Rep., 2015.
[15] M. Ojo and S. Giordano, “An efficient centralized scheduling algorithm in IEEE802.15.4e TSCH networks,” in Standards for Communications and Net- working (CSCN), 2016 IEEE Conference on. IEEE, 2016, pp. 1–6.
[16] M. R. Palattella, T. Watteyne, Q. Wang, K. Muraoka, N. Accettura, D. Du- jovne, L. A. Grieco, and T. Engel, “On-the-fly bandwidth reservation for 6TiSCH wireless industrial networks,” IEEE Sensors Journal, vol. 16, no. 2, pp. 550–560, 2016.
[17] N. Accettura, M. R. Palattella, G. Boggia, L. A. Grieco, and M. Dohler, “De- centralized traffic aware scheduling for multi-hop low power lossy networks in the internet of things,” in World of Wireless, Mobile and Multimedia Networks (WoWMoM), 2013 IEEE 14th International Symposium and Workshops on
a. IEEE, 2013, pp. 1–6.
[18] S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, et al., “Optimization by simulated annealing,” science, vol. 220, no. 4598, pp. 671–680, 1983.
[19] M. Duque-Anto ́n, D. Kunz, and B. Ruber, “Channel assignment for cellular radio using simulated annealing,” IEEE Transactions on Vehicular Technol- ogy, vol. 42, no. 1, pp. 14–21, 1993.
[20] Y. G. Kim and M. J. Lee, “Scheduling multi-channel and multi-timeslot in time constrained wireless sensor networks via simulated annealing and particle swarm optimization,” IEEE Communications Magazine, vol. 52, no. 1, pp. 122–129, 2014.
[21] Y.-D. Tsai, C.-Y. Song, and H.-Y. Hsieh, “Joint optimization of clustering and scheduling for machine-to-machine communications in cellular wireless networks,” in Vehicular Technology Conference (VTC Spring), 2015 IEEE
81st. IEEE, 2015, pp. 1–5.
[22] B. Wah and T. Wang, “Simulated annealing with asymptotic convergence for nonlinear constrained global optimization,” in Principles and Practice of Constraint Programming–CP99. Springer, 1999, pp. 461–475.
[23] G. Gaillard, D. Barthel, F. Theoleyre, and F. Valois, “High-reliability schedul- ing in deterministic wireless multi-hop networks,” in Personal, Indoor, and Mobile Radio Communications (PIMRC), 2016 IEEE 27th Annual Interna- tional Symposium on. IEEE, 2016, pp. 1–6.
[24] A. Elsts, X. Fafoutis, J. Pope, G. Oikonomou, R. Piechocki, and I. Crad- dock, “Scheduling high-rate unpredictable traffic in IEEE 802.15. 4 TSCH networks.”
[25] I. Hosni, F. Th ́eoleyre, and N. Hamdi, “Localized scheduling for end-to-end delay constrained low power lossy networks with 6TiSCH,” in Computers and Communication (ISCC), 2016 IEEE Symposium on. IEEE, 2016, pp. 507–512.
[26] M. Min, Z. Yang, Y. Zhang, Y. Wang, and Z. Li, “Traffic aware mul- tiple slotframes scheduling algorithm in industrial IoT applications using IEEE802.15.4e TSCH,” in Communication Technology (ICCT), 2015 IEEE 16th International Conference on. IEEE, 2015, pp. 608–614.
[27] S. Duquennoy, B. Al Nahas, O. Landsiedel, and T. Watteyne, “Orchestra: Robust mesh networks through autonomously scheduled tsch,” in Proceedings of the 13th ACM conference on embedded networked sensor systems. ACM, 2015, pp. 337–350.
[28] X. Vilajosana, P. Tuset, T. Watteyne, and K. Pister, “Openmote: open-source prototyping platform for the industrial iot,” in International Conference on Ad Hoc Networks. Springer, 2015, pp. 211–222.
[29] C. Adjih, E. Baccelli, E. Fleury, G. Harter, N. Mitton, T. Noel, R. Pissard- Gibollet, F. Saint-Marcel, G. Schreiner, J. Vandaele, et al., “Fit iot-lab: A large scale open experimental iot testbed,” in Internet of Things (WF-IoT), 2015 IEEE 2nd World Forum on. IEEE, 2015, pp. 459–464.
[30]A.Dunkels,O.Schmidt,N.Finne,J.Eriksson,F.O ̈sterlind,N.Tsiftes,and M. Durvy, “The contiki os: The operating system for the internet of things,” Online], at http://www. contikios. org, 2011.
[31] A. Agarwal and P. Kumar, “Improved capacity bounds for wireless networks,” Wireless communications and mobile computing, vol. 4, no. 3, pp. 251–261, 2004.
[32] G. Brar, D. M. Blough, and P. Santi, “Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks,” in Proceedings of the 12th annual international conference on Mobile computing and networking. ACM, 2006, pp. 2–13.
[33] F. Xue, P. R. Kumar, et al., “Scaling laws for ad hoc wireless networks: an information theoretic approach,” Foundations and Trends in Networking, vol. 1, no. 2, pp. 145–270, 2006.
[34] P. Gupta and P. R. Kumar, “The capacity of wireless networks,” IEEE Trans- actions on information theory, vol. 46, no. 2, pp. 388–404, 2000.
[35] T. Winter, “RPL: IPv6 routing protocol for low-power and lossy networks,”
2012.
[36] P. Bahl, A. Adya, J. Padhye, and A. Walman, “Reconsidering wireless systems with multiple radios,” ACM SIGCOMM Computer Communication Review, vol. 34, no. 5, pp. 39–46, 2004.
[37] SimpleLink ultra-low power wireless MCU for Bluetooth low energy, Texas Instruments, 2 2015, rev. B.
[38] X. Vilajosana, Q. Wang, F. Chraim, T. Watteyne, T. Chang, and K. Pister, “A realistic energy consumption model for TSCH networks,” IEEE Sensors Journal, vol. 14, no. 2, pp. 482–489, 2014.
[39] A. Gibbons, Algorithmic graph theory. Cambridge university press, 1985.
[40] A. Smith, A. E. Smith, D. W. Coit, T. Baeck, D. Fogel, and Z. Michalewicz,
“Penalty functions,” 1997.
[41] G. Anastasi, M. Conti, and M. Di Francesco, “A comprehensive analysis of the MAC unreliability problem in IEEE 802.15.4 wireless sensor networks,” IEEE Transactions on Industrial Informatics, vol. 7, no. 1, pp. 52–65, 2011.
[42] A. Goldsmith, Wireless communications. Cambridge university press, 2005.
[43] X. Vilajosana and K. Pister, “Minimal 6TiSCH configuration,” 2013.
[44] J. A. McHugh, Algorithmic graph theory. Prentice Hall New Jersey, 1990.
[45] R. Soua, P. Minet, and E. Livolant, “Wave: a distributed scheduling algo- rithm for convergecast in IEEE 802.15. 4e TSCH networks,” Transactions on Emerging Telecommunications Technologies, vol. 27, no. 4, pp. 557–575, 2016.
dc.identifier.urihttp://tdr.lib.ntu.edu.tw/jspui/handle/123456789/68382-
dc.description.abstract延遲和可靠性是許多實時無線應用中考量的關鍵因素,尤其是在IEEE 802.15.4e目標中提出的TSCH模式下工業級應用。但是現在的方法只是專注于最少利用通信資源,而非利用到多信道來追求最低延遲。 此外,目前方法也僅僅適用於無傳輸失敗的理想情境。
本文中,我們先提出一個新方法來構造開銷平衡路徑算法(Cost balance tree routing)來構建樹的拓撲,結合特定排程算法,接近理論排程下限。然後,我們利用stochastic optimazation方法來探索最優的排程表(Schedule table)。為了達到這個目的,一方面,我們先探索如何構造最優序列,由此通過算法轉變為排程表;另外一方面,我們發現把限制條件加權加入最優方程,在指數級時間內能夠得到更快的收斂。為了讓我們的方法進一步適用於實際情境,我們分配冗餘資源給可能丟失的封包,同時引入並存多幀長機制(Multiple concuurent slotfram)來滿足多個延遲限制的問題。我們的模擬結果顯示,相較於現有方法,提出的方法能夠達到更低的平均延遲時間,同時也能減小關鍵節點的內存和功耗開銷。
zh_TW
dc.description.abstractDelay and reliability have been the key factors to consider in many real-time wireless applications, especially in industrial applications that the new TSCH mode proposed in IEEE 802.15.4e targets. However, existing methods focus on minimizing the use of communication resources, but they are unable to exploit the availability of channel multiplicity for achieving lower delay in TSCH networks. Besides, they provide reliability and delay-constraint transmission only under ideal situations. In this paper, we first propose a new method to construct cost-balanced routing trees that can utilize multiple interfaces at the coordinator, and then we propose a stochastic method to explore the best schedule table that satisfies the robust and in-time requirements. To achieve the lowest average delay, we seek for the best initial link sequence, which could be further converted into time- channel schedule table with the method of simulated annealing. We find that adding constraints into the optimal function could provide better converge cast in polynomial time. To further make our method adapt to realistic scenarios, we allocate redundancy cells to improve reliability and the multiple concurrent slot frames to meet different delay-constraint demands. Our simulation results demonstrate that compared to the existing methods, the proposed method is able to achieve low-delay data collection in TSCH networks, while reducing the cache size and overall energy consumption at kernel nodes.en
dc.description.provenanceMade available in DSpace on 2021-06-17T02:19:20Z (GMT). No. of bitstreams: 1
ntu-106-R03942125-1.pdf: 12133886 bytes, checksum: 4e8d7188f9b5577fe421a844080c0150 (MD5)
Previous issue date: 2017
en
dc.description.tableofcontentsABSTRACT ii
LIST OF TABLES v
LIST OF FIGURES vi
CHAPTER1 INTRODUCTION 1
CHAPTER 2 BACKGROUND AND RELATED WORK 4
2.1 TSCH and 6TiSCH 4
2.2 Related Work 10
2.2.1 Routing 10
2.2.2 Scheduling 10
2.2.3 Reliability and Delay Constraint 11
CHAPTER3 BALANCED-TREEROUTING 13
3.1 Network Scenario 13
3.2 Existing RPL Routing 18
3.3 Multiple Interfaces on the Sink 19
3.4 Communication Cost 19
3.5 Routing Tree 21
CHAPTER 4 OPTIMIZED SCHEDULING SEQUENCE 26
4.1 Drawbacks of Traffic Aware Scheduling Algorithm 26
4.2 Matching Metric 28
4.3 Optimal Matching Sequence 28
4.3.1 Simulation Annealing 30
4.3.2 Filling Algorithm with Simulated Annealing 30
4.3.3 Step and Neighborhood 31
4.3.4 Acceptance Probability 33
4.4 Constraint Simulation Annealing 33
4.4.1 Math Foundation 33
4.4.2 Configuration Space 33
4.4.3 Penalty Function 35
4.4.4 Neighborhood Structure 35
4.4.5 Acceptance Probability 37
4.4.6 Guided Local Search 38
4.4.7 Constraint SA Algorithm 38
CHAPTER 5 SCHEDULING WITH RELIABILITY AND DELAY- CONSTRAINTS 41
5.1 Composed Scheduling 41
5.2 Tentative Cells for Reliability 42
5.2.1 AMUS and Reverse Greedy Algorithms 43
5.2.2 Virtual Traffic 44
5.3 Multiple Concurrent Slotframes for Delay Constraints 45
CHAPTER6 PERFORMANCEE VALUATION 50
6.1 Simulation Setup 50
6.2 Simulation Results 52
6.2.1 Routing 52
6.2.2 Scheduling 57
6.2.3 Reliability and Delay Constraint 61
CHAPTER 7 CONCLUSION AND FUTURE WORK 65
REFERENCES 66
dc.language.isozh-TW
dc.title基於IEEE 802.15.4e分時跳頻機制的低延遲排程技術zh_TW
dc.titleLow-Delay Scheduling for IEEE 802.15.4e TSCH Networksen
dc.typeThesis
dc.date.schoolyear105-2
dc.description.degree碩士
dc.contributor.oralexamcommittee高榮鴻,蘇炫榮
dc.subject.keyword低延遲排程,IEEE 802.15.4e TSCH,平衡負載樹,隨機優化,多幀共存機制,zh_TW
dc.subject.keywordlow-delay scheduling,IEEE 802.15.4e TSCH,load balanced tree,stochastic optimization,multiple concurrent slot frame mechanism,en
dc.relation.page69
dc.identifier.doi10.6342/NTU201704142
dc.rights.note有償授權
dc.date.accepted2017-08-21
dc.contributor.author-college電機資訊學院zh_TW
dc.contributor.author-dept電信工程學研究所zh_TW
顯示於系所單位:電信工程學研究所

文件中的檔案:
檔案 大小格式 
ntu-106-1.pdf
  目前未授權公開取用
11.85 MBAdobe PDF
顯示文件簡單紀錄


系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。

社群連結
聯絡資訊
10617臺北市大安區羅斯福路四段1號
No.1 Sec.4, Roosevelt Rd., Taipei, Taiwan, R.O.C. 106
Tel: (02)33662353
Email: ntuetds@ntu.edu.tw
意見箱
相關連結
館藏目錄
國內圖書館整合查詢 MetaCat
臺大學術典藏 NTU Scholars
臺大圖書館數位典藏館
本站聲明
© NTU Library All Rights Reserved