應用混合簡化群體正餘弦演算法於工業4.0智慧工廠雲/霧混和計算系統最佳化佈署問題之研究

Simplified Swarm Optimization-Sine Cosine Algorithm for Optimal Deployment of Hybrid Cloud/Fog Computing System of Industry 4.0 Smart Factory

蔡志昱(Jr-Yu Tsai)

指導教授 ： 葉維彰

國立清華大學/工學院/工業工程與工程管理學系/碩士(2019年)

摘要

科技不斷演進，互聯網、物聯網和人工智能…等等新興技術蓬勃發展，車聯網、智慧城市和智慧工廠…等等新型態應用環境不斷產生，伴隨而來數據的大量增加及對於即時回應的要求提高，霧計算概念便在此背景中誕生。霧計算作為雲計算概念的延伸，最早是在2011年由思科(Cisco)公司提出，在霧計算的模式中，資料將不再集中於雲端處理，而是分散到網路邊緣的設備中，不像雲計算需要性能強大的計算機進行集中化的運算，網路邊緣的單一設備不需要太強大的性能，但依賴其分散運算的效果，使其依然可以達成快速地處理資料之需求。
本研究根據過往文獻提出兩種不同模型，第一種模型是考量多樣感測設備的多階層式設施佈署問題模型，第二種模型是延續第一種模型並提出考量霧計算裝置彼此可相連傳輸的多階層式設施佈署問題模型。而設施佈署問題已被證明是NP-Hard問題，故本研究採用啟發式演算法來進行求解。本研究提出一新興的混合算法稱為混合簡化群體正餘弦演算法(Simplified Swarm Optimization-Sine Cosine Algorithm, SSO-SCA)，另外也使用其他著名啟發式演算法如:人工蜂群演算法(Artificial Bee Colony, ABC)、基因演算法(Genetic Algorithm, GA)及二進制粒子群演算法(Binary Particle Swarm Optimization, BPSO)及簡化群體法(Simplified Swarm Optimization, SSO)來進行結果比較及探討。
本研究的目的是在高度限制的整數規劃模型下，利用啟發式演算法在合理時間內找出成本較低之佈署方案。研究假設一智能工廠若考慮佈署雲/霧混和計算系統，主要決策佈署之裝置為閘道、霧計算裝置及邊緣裝置位置，同時提出三種不同規模大小問題來進行實驗，以期能找出最有效之方法幫助決策者建置智能工廠最佳雲/霧混和計算系統佈署。

關鍵字

混合簡化群體正餘弦演算法 ； 啟發式演算法 ； 多階層設施佈置問題 ； 雲/霧混和計算系統 ； 智能工廠

並列摘要

Technology is constantly evolving, and emerging technologies such as the Internet of Things (IoT), and Artificial Intelligence(AI) are booming. In addition, new forms of application environments such as Internet of Vehicle (IoV), Smart Cities and Smart Factories are steadily appearing. With the large increase in data and the increased demand for immediate response, the concept of fog computing was born. Fog computing was first proposed by Cisco in 2011. In fog computing, data processing will no longer be concentrated in the cloud, but distributed to devices at the edge of the network. Devices at the edge of network don’t need powerful performance, but relying on the effects of their decentralized computing, the system can still process data quickly.
This study proposes two different models based on the previous literature. One is a Hierarchical Facility Location Problem model that considers multiple sensing devices. Another extends the first model and considers that the fog computing devices can be connected to each other. The Facility Location Problem has been proved as an NP-Hard problem, so this study uses the heuristic algorithms to solve it. This study proposes an novel algorithm called Simplified Swarm Optimization-Sine Cosine Algorithm (SSO-SCA), and other well-known heuristic algorithms such as Artificial Bee Colony (ABC), Genetic Algorithm (GA), Binary Particle Swarm Optimization (BPSO), and Simplified Swarm Optimization (SSO) are also used to compare the results. The purpose of this study is to use heuristic algorithms to find min-cost deployment under highly restricted model in reasonable time. It is expected to find the most effective way to help decision makers build hybrid cloud/fog computing system in smart factories.

並列關鍵字

Simplified Swarm Optimization-Sine Cosine Algorithm ； Heuristic Algorithm ； Hierarchical Facility Location Problems ； Cloud/Fog Hybrid Computing System ； Smart Factory

參考文獻

[1] F. Bonomi, R. Milito, J. Zhu, and S. Addepalli, "Fog computing and its role in the internet of things," in Proceedings of the first edition of the MCC workshop on Mobile cloud computing, 2012, pp. 13-16: ACM.

[2] S. Sarkar and S. Misra, "Theoretical modelling of fog computing: A green computing paradigm to support IoT applications," IET Networks, vol. 5, no. 2, pp. 23-29, 2016.

[3] A. D. Shuo-Yan Chou, "智慧工廠簡介," 科儀新知, no. 208, pp. 5-15, 2016.

[4] J. Lee, T. Kwon, and J. Song, "Group connectivity model for industrial wireless sensor networks," IEEE Transactions on Industrial Electronics, vol. 57, no. 5, pp. 1835-1844, May 2010 2010.

[5] C.-C. Lin, D.-J. Deng, Z.-Y. Chen, and K.-C. Chen, "Key design of driving industry 4.0: Joint energy-efficient deployment and scheduling in group-based industrial wireless sensor networks," IEEE Communications Magazine, vol. 54, no. 10, pp. 46-52, October 2016 2016.