Basic Search / Detailed Display

Author: 謝官閔
Kuan-Min Hsieh
Thesis Title: 雲、邊緣、車輛務運算之垂直卸載:聯合架構以及排隊理論分析
Vertical Offloading between Cloud, Edge, and Vehicular-Fog Systems: Federated Architecture and Queueing Analysis
Advisor: 馮輝文
Huei-Wen Ferng
Committee: 林盈達
Ying-Dar Lin
Hung-Yun Hsieh
Degree: 碩士
Department: 電資學院 - 資訊工程系
Department of Computer Science and Information Engineering
Thesis Publication Year: 2020
Graduation Academic Year: 108
Language: 英文
Pages: 39
Keywords (in Chinese): 卸載聯合系統架構排隊理論車輛霧運算卸載機率最佳化
Keywords (in other languages): Federation, Offloading, Queueing Theory, Vehicular-Fog, QoS Violation Probability
Reference times: Clicks: 271Downloads: 2
School Collection Retrieve National Library Collection Retrieve Error Report

近年來,基於智慧型交通運輸系統(Intelligent Transportation System)之相關研究及應用已被提出並且用於用路安全改善以及高效率運輸;然而,大部分用戶設備(User Equipment)的運算能力並不足以達到高運算需求,所以,用戶設備須將運算任務卸載(Offload)至其他運算資源。於是,本論文提出了包含行動雲端運算(Mobile Cloud Computing)、行動邊緣運算(Mobile Edge Computing)以及車輛霧運算(Vehicular-Fog Computing)之聯合系統架構以解決此問題。我們首先運用排隊理論(Queueing Theory)來推導運算任務處理時間超過設定門檻(Threshold)的機率(QoS Violation Probability)做為約束函數(Constraint Function);接著,我們設計了一個演算法以得到最佳卸載機率來解決卸載決策制定之最佳化問題。最後,透過與不同聯合系統架構之比較,我們可顯示於運算任務到達率較高(Arrival Rate)的情況下,包含兩種不同車輛霧運算系統之聯合系統架構可比沒有包含任何車輛霧運算系統之聯合系統架構可大幅降低運算任務之等候時間(Waiting Time)。

Abstract – The related research and applications of the intelligent transportation system (ITS) have been proposed and studied over the past few years to archive safety and high efficiency of transportation. However, most of the user equipments (UEs) do not have enough computational power to reach the requirement of high-computing capability. Therefore, time-sensitive tasks should be offloaded to the other computation resources. Targeting at this goal, a federated system architecture with mobile cloud computing (MCC), mobile edge computing (MEC), and vehicular-fog computing (VFC) systems is proposed in this thesis to solve such an issue. Then, we derive the QoS violation probability that the task processing time exceeds the given threshold to serve as the constraint function by applying the queueing theory. Furthermore, we propose an algorithm to find the optimal offloading probabilities for the optimization problem of offloading decision making. Finally, we show that the average waiting time of the federated architecture with two vehicular-fogs can be greatly reduced as compared to the architecture without any vehicular-fog when the task arrival rate is high.

Chinese Abstract i Abstract ii Contents iii List of Figures iv List of Tables v 1 Introduction 1 2 Related Works 3 3 System Design and Problem formulation 5 3.1 Proposed System Architecture 6 3.2 Problem Formulation 7 3.2.1 System Model 7 3.2.2 Derivation of QoS Violation Probability 8 3.3 Average Waiting Time of Whole System 14 3.4 Problem Statement 14 4 Optimized Solution 15 4.1 Main Probability Estimation Algorithm 15 4.2 Sub Probability Estimation Algorithm 16 4.3 Changing State of VFC System 17 5 Numerical Results and Discussion 18 5.1 Parameter Setting 18 5.2 Validation of Analytical Method 19 5.3 Performance Analysis and Discussion 19 5.3.1 Offloading Probability 19 5.3.2 Variation with Edge Capacity 20 5.3.3 Variation with Fog arrival rate 21 5.3.4 Average Waiting Time 22 5.4 Experiments with Real Traffic 22 6 Conclusion 24 Bibliography 25 Appendix 27

[1] D. George and P. Demestichas, “Intelligent transportation systems,” IEEE Veh. Technol. Mag., vol. 5, no. 1, pp. 77–84, Mar. 2010.

[2] F. Wang, "Parallel control and management for intelligent transportation systems: Concepts, architectures, and applications," IEEE Transactions on Intelligent Transportation Systems, vol. 11, no. 3, pp. 630-638, Sept. 2010.

[3] J. Guerrero-Iba´nez, S. Zeadally, and J. Contreras-Castillo, “Sensor technologies for intelligent transportation systems,” Sensors, vol. 18, no. 4, 2018.

[4] H. T. Dinh, C. Lee, D. Niyato, and P. Wang, “A survey of mobile cloud computing: Architecture, applications, and approaches,” Wireless Commun. Mobile Comput., vol. 13, no. 18, pp. 1587–1611, 2013

[5] J. Zheng, Y. Cai, Y. Wu and X. Shen, "Dynamic computation offloading for mobile cloud computing: A stochastic game-theoretic approach," IEEE Transactions on Mobile Computing, vol. 18, no. 4, pp. 771-786, 1 April 2019

[6] K. Akherfi, M. Gerndt, and H. Harroud, ‘‘Mobile cloud computing for computation offloading: Issues and challenges,’’ Appl. Comput. Informat., vol. 14, no. 1, pp. 1–16, 2018.

[7] Y. Mao, C. You, J. Zhang, K. Huang, and K. B. Letaief, “A survey on mobile edge computing: The communication perspective,” IEEE Commun. Survey Tuts., vol. 19, no. 4, pp. 2322–2358, 4th Quart., 2017

[8] P. Mach and Z. Becvar, “Mobile edge computing: A survey on architecture and computation offloading,” IEEE Commun. Surveys Tuts., vol. 19, no. 3, pp. 1628–1656, 3rd Quart., 2017.

[9] H. Guo, J. Liu, J. Zhang, W. Sun, and N. Kato, “Mobile-edge computation offloading for ultra-dense IoT networks,” IEEE Internet Things J., vol. 5, no. 6, pp. 4977–4988, Dec. 2018.

[10] X. Hou, Y. Li, M. Chen, D. Wu, D. Jin and S. Chen, “Vehicular fog computing: A viewpoint of vehicles as the infrastructures,” IEEE Trans. Veh. Technol., vol. 65, no. 6, pp. 3860–3873, Jun. 2016.

[11] Z. Zhou, P. Liu, J. Feng, Y. Zhang, S. Mumtaz, and J. Rodriguez, “Computation resource allocation and task assignment optimization in vehicular fog computing: A contract-matching approach,” IEEE Trans. Veh. Technol., vol. 68, no. 4, pp. 3113–3125, Apr. 2019.

[12] Y. Zhang, C.-Y. Wang, and H.-Y. Wei, “Parking reservation auction for parked vehicle assistance in vehicular fog computing,” IEEE Trans. Veh. Technol., vol. 68, no. 4, pp. 3126–3139, Apr. 2019

[13] D. Huang, P. Wang, and D. Niyato “A dynamic offloading algorithm for mobile computing” IEEE Transactions on Wireless Communications, vol. 11, no. 6, pp. 1991-1995, June 2012.

[14] L. Liu, Z. Chang, X. Guo, and T. Ristaniemi, “Multiobjective optimization for computation offloading in fog computing” 2017 IEEE Symposium on Computers and Communications (ISCC), Heraklion, 2017, pp. 832-837.

[15] Y.-D. Lin, J.-C. Hu, B. Kar, and L.-H. Yen “Cost minimization with offloading to vehicles in two-tier federated edge and vehicular-fog systems” in Proc. IEEE 90th Vehicular Technology (VTC) Conference pp. 22-25, Sept. 2019.

[16] X. Chen, L. Jiao and W. Li “Efficient multi-user computation offloading for mobile-edge cloud computing” IEEE/ACM Transactions on Networking, vol. 24, no. 5, pp. 2795-2808, October 2016.

[17] X. Chen “Decentralized computation offloading game for mobile cloud computing” IEEE Transactions on Parallel and Distributed Systems, vol. 26, no. 4, pp. 974-983, Apr. 2015.

[18] R.-H. Hwang, Y.-C. Lai and Y.-D. Lin “Offloading optimization with delay distribution in the 3-tier federated cloud, edge, and fog systems” in Proc. IEEE International Symposium on Cloud and Services Computing (IEEE SC2 2019), Kao-Hsiung, Taiwan, Nov. pp. 18-21, 2019.

[19] P. V. O’Neil, Advanced Engineering Mathematics, 4th ed. Pacific Grove, CA: Brooks/Cole, 1995.

[20] D. Gross and C. Harris, Fundamentals of Queueing Theory. Hoboken, NJ, USA: Wiley, 1985.

[21] Taichung City Realtime Traffic Information,