臺灣博碩士論文加值系統

隨著工業4.0與即時敏感網路(TSN)日益普及，大量客制化製造(Mass customization production, MCP)需求逐漸受到重視，其產品製造須依前端客戶需求變化來動態調整後端的產線生產，以獲得廠商與消費者間利益最大化之目標。然而，此客製化模式使得工業網路面臨動態的網路配置需求，造成現有的靜態TSN網路路由機制將不適用於此應用情境。同時，本篇論文亦發現過去TSN路由機制僅考量部分資料流路由的最佳化，其僅能獲得一個區域性最佳解。為此，本篇論文擬提出一個基於蟻群優化法的動態路由演算法，其考量多種資料流的特性與演算法計算複雜度，以動態調整資料流的路徑並滿足所有資料流之需求。為驗證本篇論文所提出的演算法之效能表現，我們採用OMNet++/NeSTiNg網路模擬器並搭配真實網路參數來進行TSN網路模擬。實驗結果顯示，我們所提出之演算法能有效提升資料流的可排程率進而優化整體網路的最大承載量。

With Industrial 4.0 and Time Sensitive Network (TSN) being more andmore popular, the requirement of Mass Customization Production (MCP) isalsogrowing. Itsuggestsustoadjusttheproductionlinedynamicallyaccord-ing to the clients’ demands in order to maximize the benefit. However, MCPrequires the industrial network to be dynamic and allow online reconfigures,which makes current TSN static routing strategies unfeasible. Besides, wealso find that previous routing strategies only consider part of the streams,which makes them unable to find a global optimal solution. To overcome theaboveissue,weproposeanonlineroutingalgorithmbasedonAntColonyOp-timization (ACO). It considers cimputational complexity and multiple kindsof streams, adjusting the routing assignment to meet the application’s con-straints. We will use OMNet++/NeSTiNg to simulate the environment ofindustrialproduction. Theexperimentwillshowthatouralgorithm coulden-hance schedulability, making the system capable of handling more streams.

摘要 iii
Abstract v
1 Introduction 1
2 Related Works and Background 3
2.1 TT Scheduling Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 AVB Traffic Shaping . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 AVB Worst Case Delay . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 System Model and Problem Formulatioin 7
3.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Problem Formulatioin . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.3 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4 Routing Algorithm 11
4.1 Search Space Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2 Cost Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.2.1 Scheduling TT flows . . . . . . . . . . . . . . . . . . . . . . . . 12
4.2.2 AVB Schedulability . . . . . . . . . . . . . . . . . . . . . . . . 12
4.2.3 AVB Performance Estimate . . . . . . . . . . . . . . . . . . . . 13
4.2.4 Impact To Network . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.3 Ant Colony Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5 Experimental Evaluation 17
6 Conclusion 19
Bibliography 21

[1]S. S. Craciunas, R. S. Oliver, M. Chmelík, and W. Steiner. Scheduling real-timecommunication in ieee 802.1 qbv time sensitive networks. InProceedings of the24th International Conference on Real-Time Networks and Systems, pages183–192.ACM, 2016.
[2]A. R. Curtis, W. Kim, and P. Yalagandula. Mahout: Low-overhead datacenter trafficmanagementusingend-host-basedelephantdetection. InInfocom,volume11,pages1629–1637, 2011.
[3]M. Dorigo and G. Di Caro. Ant colony optimization: a new meta-heuristic. InProceedings of the 1999 congress on evolutionary computation-CEC99 (Cat. No.99TH8406), volume 2, pages 1470–1477. IEEE, 1999.
[4]V. Gavriluţ and P. Pop. Scheduling in time sensitive networks (tsn) for mixed-criticality industrial applications. In2018 14th IEEE International Workshop onFactory Communication Systems (WFCS), pages 1–4. IEEE, 2018.
[5]S. M. Laursen, P. Pop, and W. Steiner. Routing optimization of avb streams in tsnnetworks.ACM Sigbed Review, 13(4):43–48, 2016.
[6]N. G. Nayak, F. Dürr, and K. Rothermel. Routing algorithms for ieee802. 1qbvnetworks.ACM SIGBED Review, 15(3):13–18, 2018.
[7]R.S.Oliver,S.S.Craciunas,andW.Steiner. Ieee802.1qbvgatecontrollistsynthesisusing array theory encoding. In2018 IEEE Real-Time and Embedded Technologyand Applications Symposium (RTAS), pages 13–24. IEEE, 2018.21
[8]D. Pannell. Avb latency math.802.1 AVB Face to Face, 2010.
[9]M. L. Raagaard, P. Pop, M. Gutiérrez, and W. Steiner. Runtime reconfiguration oftime-sensitive networking (tsn) schedules for fog computing. In2017 IEEE FogWorld Congress (FWC), pages 1–6. IEEE, 2017.
[10]E. Schweissguth, P. Danielis, D. Timmermann, H. Parzyjegla, and G. Mühl. Ilp-based joint routing and scheduling for time-triggered networks. InProceedings ofthe 25th International Conference on Real-Time Networks and Systems, pages 8–17.ACM, 2017.
[11]S. Singh. Routing algorithms for time sensitive networks. Master’s thesis, 2017.
[12]T. Stützle and H. H. Hoos. Max–min ant system.Future generation computer sys-tems, 16(8):889–914, 200