伴隨著5G及物聯網的迅速成長，未來將會有愈來愈多的IOT裝置，然而這些IOT裝置的計算能力未必能跟上使用者需求，為此可以透過多接取邊緣計算(MEC)來克服。MEC 的伺服器比起雲計算來說，可以將伺服器放置在離使用者更近的地方，藉此縮短傳輸時間，然而，環境中大量的使用者與有限的伺服器可能導致計算資源和傳輸資源的分配產生問題。
本研究提出了一種基於旅行商問題 (TSP) 的方法，並搭配 MP-DQN，用於優化MEC中的計算卸載策略，基於MP-DQN的架構，可以避免對連續動作空間進行離散化，因此適用於同時具備離散動作空間和連續動作空間的場景。我們的MPDQN-TSP演算法通過限縮動作空間，減少了深度強化學習模型在動作空間中所需要的的探索時間，並提高了系統的任務完成率。

With the rapid growth of 5G and the Internet of Things (IoT), the number of IoT devices is expected to increase significantly. However, the computational capabilities of these IoT devices may not keep pace with user demands. To address this, Multi-Access Edge Computing (MEC) can be employed. Unlike cloud computing, MEC servers are deployed closer to users, reducing transmission time. However, the presence of a large number of users and limited servers in the environment may lead to challenges in the allocation of computational and transmission resources.
This thesis proposes a method based on the Traveling Salesman Problem (TSP), combined with MP-DQN, to optimize computation offloading strategies in MEC. The MP-DQN framework avoids the dis-cretization of continuous action spaces, making it suitable for scenarios that involve both discrete and continuous action spaces. Our MPDQN-TSP algorithm reduces the exploration time required by deep reinforcement learning model within the action space by constraining the action space, and also im-proving the task completion ratio of the system.

[1] Jorge Navarro-Ortiz, Pablo Romero-Diaz, Sandra Sendra, Pablo Ameigeiras, Juan J. Ramos-Munoz, Juan M. Lopez-Soler, “A Survey on 5G Usage Scenarios and Traffic Models”, IEEE Communications Surveys & Tutorials, pp. 905-929, 2020.
[2] Tiejun Lv, Yuyu Ma, Jie Zeng, P. Takis Mathiopoulos, “Millimeter-Wave NOMA Transmission in Cellular M2M Communications for Internet of Things”, IEEE Internet of Things Journal, vol. 5, no. 3, pp. 1989-2000, June 2018.
[3] Anutusha Dogra, Rakesh Kumar Jha, Shubha Jain, “A Survey on Beyond 5G Network With the Advent of 6G: Architecture and Emerging Technologies”, IEEE Access, vol. 9, pp. 67512-67547, 2021.
[4] Tarik Taleb, Konstantinos Samdanis, Badr Mada, Hannu Flinck, Sunny Dutta, Dario Sabella, “On Multi-Access Edge Computing: A Survey of the Emerging 5G Network Edge Cloud Architecture and Orchestration”, vol. 19, no. 3, pp. 1657-1681, thirdquarter 2017.
[5] Pawani Porambage, Jude Okwuibe, Madhusanka Liyanage, Mika Ylianttila, Tarik Taleb, “Survey on Multi-Access Edge Computing for Internet of Things Realization”, vol. 20, no. 4, pp. 2961-2991, Fourthquarter 2018.
[6] Weisong Shi, Jie Cao, Quan Zhang, Youhuizi Li, Lanyu Xu, “Edge computing: Vision and challenges”, vol. 3, no. 5, pp. 637-646, Oct. 2016.
[7] Ji Li, Hui Gao, Tiejun Lv, Yueming Lu, “Deep reinforcement learning based computation offloading and resource allocation for MEC”, 2018 IEEE Wireless Communications and Networking Conference (WCNC), pp. 1-6, 2018.
[8] Huan Zhou, Kai Jiang, Xuxun Liu, Xiuhua Li, Victor C. M. Leung, “Deep Reinforcement Learning for Energy-Efficient Computation Offloading in Mobile-Edge Computing”, IEEE Internet of Things Journal, vol. 9, no. 2, pp. 1517-1530, 15 Jan.15, 2022.
[9] Laha Ale, Ning Zhang, Xiaojie Fang, Xianfu Chen, Shaohua Wu, Longzhuang Li, “Delay-Aware and Energy-Efficient Computation Offloading in Mobile-Edge Computing Using Deep Reinforcement Learning”, IEEE Transactions on Cognitive Communications and Networking, vol. 7, no. 3, pp. 881-892, Sept. 2021.
[10] Tao Zheng, Jian Wan, Jilin Zhang , Congfeng Jiang, “Deep Reinforcement Learning-Based Workload Scheduling for Edge Computing”, J Cloud Comp vol.11, no.3, pp. 1-13, 2022.
[11] Haodong Lu, Xiaoming He, Miao Du, Xiukai Ruan, Yanfei Sun, Kun Wang, “Edge QoE: Computation Offloading With Deep Reinforcement Learning for Internet of Things”, in IEEE Internet of Things Journal, vol. 7, no. 10, pp. 9255-9265, Oct. 2020.
[12] Zhao Chen, Xiaodong Wang, “Decentralized computation offloading for multi-user mobile edge computing: a deep reinforcement learning approach”, EURASIP J. Wireless Commun. Netw., vol. 2020, no. 1, pp. 1–21, 2020.
[13] Xincao Xu, Kai Liu, Penglin Dai, Feiyu Jin, Hualing Ren, Choujun Zhan, Songtao Guo, “Joint task offloading and resource optimization in NOMA-based vehicular edge computing: A game-theoretic DRL approach”, J.Syst.Archit., vol.134, pp. 102780, 2023.
[14] Shuoyao Wang, Suzhi Bi, Ying-Jun Angela Zhang, “Deep Reinforcement Learning With Communication Transformer for Adaptive Live Streaming in Wireless Edge Networks”, in IEEE Journal on Selected Areas in Communications, vol. 40, no. 1, pp. 308-322, Jan. 2022.
[15] Liang Huang, Suzhi Bi, Ying-Jun Angela Zhang, “Deep Reinforcement Learning for Online Computation Offloading in Wireless Powered Mobile-Edge Computing Networks”, IEEE Transactions on Mobile Computing , pp.2581-2593, 2019.
[16] Jing Tan, Ramin Khalili, Holger Karl, Artur Hecker, “Multi-Agent Distributed Reinforcement Learning for Making Decentralized Offloading Decisions”, IEEE INFOCOM 2022 - IEEE Conference on Computer Communications, London, United Kingdom, pp. 2098-2107, 2022.
[17] Chen Chen, Yuru Zhang, Zheng Wang, Shaohua Wan, Qingqi Pei, “Distributed computation offloading method based on deep reinforcement learning in ICV”, Appl. Soft Comput., vol. 103, May 2021.
[18] Liang Zhao, Zijia Zhao, Enchao Zhang, Ammar Hawbani, Ahmed Y. Al-Dubai, Zhiyuan Tan, Amir Hussain, “A Digital Twin-Assisted Intelligent Partial Offloading Approach for Vehicular Edge Computing”, IEEE Journal on Selected Areas in Communications, 2023.
[19] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg & Demis Hassabis, “Human-level control through deep reinforcement learning”, Nature, vol. 518, pp. 529-523, 2015.
[20] Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess,Tom Erez, Yuval Tassa, David Silver, Daan Wierstra, “Continuous control with deep reinforcement learning”, arXiv preprint arXiv:1509.02971, 2015.
[21] Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel and Sergey Levine, “Soft Actor-Critic Algorithms and Applications”, arXiv preprint arXiv:1812.05905, 2018.
[22] Jiechao Xiong, Qing Wang, Zhuoran Yang, Peng Sun, Lei Han, Yang Zheng, Haobo Fu, Tong Zhang, Ji Liu, Han Liu, “Parametrized Deep Q-Networks Learning: Reinforcement Learning with Discrete-Continuous Hybrid Action Space”, arXiv preprint arXiv:1810.06394, 2018.
[23] Zhou Fan, Rui Su, Weinan Zhang, Yong Yu, “Hybrid Actor-Critic Reinforcement Learning in Parameterized Action Space”, arXiv preprint arXiv:1903.01344, 2019.
[24] Boyan Li, Hongyao Tang, Yan Zheng, Jianye Hao, Pengyi Li, Zhen Wang, Zhaopeng Meng, Li Wang, “Hyar: Addressing discrete-continuous action reinforcement learning via hybrid action representation”, arXiv preprint arXiv:2109.05490, 2021.
[25] Craig J. Bester, Steven D. James, George D. Konidaris, “Multi-Pass Q-Networks for Deep Reinforcement Learning with Parameterised Action Spaces”, arXiv preprint arXiv:1905.04388, 2019.
[26] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C.,” Introduction to Algorithms (3rd ed.)”, MIT Press, 2009.
[27] Thomas ST ̈UTZLE, Marco DORIGO, “ACO Algorithms for the Traveling Salesman Problem”, Evolutionary algorithms in engineering and computer science, 4, pp. 163-183, 1999.
[28] Noraini Mohd Razali, John Geraghty, “Genetic algorithm performance with different selection strategies in solving TSP”, In: Proceedings of the world congress on engineering. Hong Kong, China: International Association of Engineers, pp. 1-6, 2011.
[29] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zach DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai and Soumith Chintala, “Pytorch: An imperative style, high-performance deep learning library”, Advances in neural information processing systems, vol. 32, 2019.
[30] Kartik Ramesh Patel; Sanjay Dasrao Deshmukh , “2S (Superposition Coding, Successive Interference Cancellation) Operations in NOMA Technology for 5G Networks: Review and Implementation”, 2023 IEEE 8th International Conference for Convergence in Technology (I2CT), Lonavla, India, 2023, pp. 1-6, 2023.