成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	蘇辰堯 Su, Chen-Yao
論文名稱：	基於深度強化式學習的5G網路切片資源配置方法 Slice-DQN, Using Binary Tree Multi-step DQN to Optimize Packing Efficiency in 5G Network Slice Management
指導教授：	蘇銓清 Sue, Chuan-Ching
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 資訊工程學系 Department of Computer Science and Information Engineering
論文出版年：	2023
畢業學年度：	111
語文別：	英文
論文頁數：	43
中文關鍵詞：	5G 、網路切片架構、網路切片調度、二維裝箱問題、深度強化式學習
外文關鍵詞：	5G, network slicing architecture, network slicing scheduling, bin packing problem, deep reinforcement learning
相關次數：	點閱：95 下載：0
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

近年來，隨著行動裝置的日益發展，使用者所需要的網路服務使用量也越來越高，如何使最多的使用者可以得到需求的服務成為一大問題。每個使用者所請求的服務都有不同的服務品質要求，對應到不同的資源需求。5G網路架構可以讓服務供應商使用網路切片區隔資源的特性，將其所持有的資源分割為使用者所需要的資源需求，來滿足使用者的服務品質要求，實現有效率的資源分配。因此，服務供應商如何配置網路切片能在滿足最多的使用者的服務品質要求時最大化服務供應商所持有的資源利用率會成為一個重要的問題。
本研究基於將服務供應商分配多個網路切片的資源與時間的問題定義成一種二維的裝箱問題，使用二元樹資料結構來記錄服務供應商的剩餘資源與時間，透過這樣的資料結構來保持切片配置互相緊貼使資源利用率最大化。為了改善使用啟發式演算法無法適應多變環境的問題，我們提出一種基於深度強化學習的方法，對新進服務需求所需資源與時間與考慮到未來需求的變化，動態決定配置方式，而非僅考慮目前的需求。實驗部分比較了與其他深度強化學習演算法和啟發式演算法在面對不同測試資料時表現上的差異。

In recent years, with the increasing development of mobile devices, the demand for network services from users has also been growing rapidly. Ensuring that the maximum number of users can receive the desired services has become a major challenge. Each user request has unique service requirements, and different requests have varying quality-of-service requirements. The 5G network architecture can leverage network slicing to provide pre-planned slices to users, efficiently allocating resources by segregating them using the characteristics of network slicing, while satisfying the users' quality-of-service requirements. Therefore, maximizing resource utilization while serving as many users as possible becomes an important problem for service providers.

This study defines the problem of allocating resources and time for multiple network slices as a 2D bin-packing problem. It utilizes a binary tree data structure to keep track of the remaining resources and time of service providers, ensuring compact packing of slice configurations to maximize resource utilization by avoiding the fragment. A deep reinforcement learning-based approach is proposed to dynamically determine the allocation of resources and time for incoming service requests, addressing the limitations of heuristic algorithms in adapting to changing environments. We conduct several experiments to compare the proposed approach with the other deep reinforcement learning method and some heuristic algorithms across different test scenarios.

中文摘要 I
Abstract II
致謝 III
Content IV
List of Figure V
List of Table VI
1. Introduction 1
2. Background and Related Work 4
2.1 5G Network Slicing Architecture 4
2.1.1 Network function Virtualization 4
2.1.2 5G Network Slicing Architecture 4
2.2 Bin Packing Problem 7
2.2.1 On-line and Off-line Bin Packing Problem 7
2.2.2 Dimensionality of BPP [17] 8
2.2.3 BPP Related Work 8
2.3 Deep Reinforcement Learning 9
2.4 Motivation 10
3. System Architecture 12
3.1 System Architecture 12
3.2 Problem Formulation 13
3.2.1 Definition of Bin and Item 13
3.2.2 Compactness、Accept Rate、PE 15
3.3 Binary tree Two-dimensional BPP 17
3.3.1 Definition of Binary Tree BPP 17
3.3.2 Tree-to-tensor 19
4. Packing Agent 21
4.1 Deep Reinforcement Learning Agent 21
4.1.1 State Space 21
4.1.2 Action Space 21
4.1.3 Reward Function 22
4.2 Binary Tree Packing Algorithm 22
4.2.1 Multi-step DQN[29] 23
4.3 Algorithm 24
5. Result Evaluation 26
5.1 Training, Testing Data Generation 26
5.2 Training, Testing Parameter 28
5.3 Testing Result Evaluation 31
5.4 Test Result Analysis 37
6. Conclusion 39
7. Reference 41

List of Figure
Figure 1. Different 5G network slices serve different use cases 5
Figure 2. Three layers of network slicing architecture 6
Figure 3. Three important role in network slicing architecture 7
Figure 4. System Architecture 12
Figure 5. Mapping of Network Slicing to the 2D Bin Packing Problem 14
Figure 6. Illustration of Compactness 15
Figure 7. Illustration of Accept Rate、 Packing Efficiency 16
Figure 8. The binary tree for the first Request Slice R1 17
Figure 9. Place a new Request Slice and modify available space information. 18
Figure 10. Using Tree-to-Tensor to record request information and current tree state 20
Figure 11. DQN Framework Learning process 23
Figure 12. Procedure for generating a filled bin slice 27
Figure 13. Training Reward Trend Chart 30
Figure 14. Training Accept Rate Trend Chart 30
Figure 15. Training Packing Efficiency Trend Chart 31
Figure 16. Line Graph of Testing Accept Rate for Each Algorithm 35
Figure 17. Line Graph of Testing PE for Each Algorithm 36
Figure 18. Algorithms using binary tree's accept rate% to different bin size 38

List of Table
Table 1. Hyper parameters 29
Table 2. Accept Rate Results for Each Algorithm 33
Table 3. PE Results for Each Algorithm 34
                                    

[1] S. Mansoor, A. F. Molisch, P. J. Smith, T. Haustein, P. Zhu, P. D. Silva, F. Tufvesson, A. Benjebbour and G. Wunder, “5G: A tutorial overview of standards, trials, challenges, deployment, and practice”, IEEE journal on selected areas in communications, vol. 35, no. 6, pp. 1201-1221, 2017
[2] A. A. Barakabitze, A. Ahmad, R. Mijumbi and A. Hines, “5G network slicing using SDN and NFV: A survey of taxonomy, architectures and future challenges”, Computer Networks, vol. 167, pp.106984, 2020.
[3] G. Akhil and J. R. Kumar, “A survey of 5G network: Architecture and emerging technologies”, IEEE access, vol. 3, pp. 1206- 1232, 2015
[4] L. Mamushiane and S. Dlamini, “Leveraging SDN/NFV as key stepping stones to the 5G era in emerging markets”, 2017 Global Wireless Summit (GWS), Cape Town, pp. 23-27, 2017.
[5] M. Condoluci and T. Mahmoodi. “Softwarization and virtualization in 5G mobile networks: Benefits, trends and challenges”, Computer Networks vol. 146, pp. 65-84. 2018.
[6] S. Prashant, A. Abeer and P. PWC and R. Sabih and G. Nabil and I.Muhammad and A. Samrah, “Network slicing: a next generation 5G perspective”, EURASIP Journal on Wireless Communications and Networking, vol. 2021, no. 1, pp.102, 2021
[7] M. Rashid, S. Joan, G. Juan-Luis, B. Niels, D. T. Filip and B. Raouf, “Network function virtualization: State-of-the-art and research challenges”, IEEE Communications surveys & tutorials vol. 18. no.1 , pp.236-262 2015.
[8] Jhe-Wei Liu, “Network Slicing Orchestration in 5G Core Network Based on Utilization Forecasting”, Master Thesis, National Cheng Kung University, Tainan, Taiwan, R.O.C, Sep. 2021
[9] H. Ekram and H. Monowar, “5G cellular: key enabling technologies and research challenges". IEEE Instrumentation & Measurement Magazine vol. 18, no. 3, pp. 11-21, 2015.
[10] R. Jonathan, “Fundamentals of 5G mobile networks”, John Wiley & Sons, pp. 32, 2015
[11] O. Sunday O and F. Olabisi E, “5G network slicing: A multi-tenancy scenario”, 2017 Global Wireless Summit (GWS), IEEE, pp.88-92, 2017
[12] K. Yohan, K. Sunyong and L. Hyuk, “Reinforcement learning based resource management for network slicing”, Applied Sciences, vol. 9, no. 11, pp. 2361, 2019.
[13] M. Volodymyr, K. Koray, S. David,G. Alex, A. Ioannis, W. Daan and R. Martin, “Playing atari with deep reinforcement learning”, arXiv preprint arXiv:1312.5602, 2013.
[14] M. Volodymyr, K. Koray, S. David,G. Alex, A. Ioannis, W. Daan and R. Martin, “Human-level control through deep reinforcement learning”, nature, vol. 518, no. 7540, pp. 529-533, 2015
[15] F. Xenofon, P. Georgios, E. Ahmed and M. M. K, “Network slicing in 5G: Survey and challenges”, IEEE communications magazine vol. 55, no. 5, pp. 94-100, 2017.
[16] L. M. Sh, “Towards bin packing (preliminary problem survey, models with multiset estimates)”, CoRR, vol. abs/1605.07574, 2016
[17] D. Harald. “A typology of cutting and packing problems”, European journal of operational research vol. 44, no. 2, pp. 145-159, 1990.
[18] E. Pietrobuoni, “Two-dimensional bin packing problem with guillotine restrictions”, Ph.D. thesis, University of Bologna, Italy, 2015.
[19] S. Steven S. “On the online bin packing problem”, Journal of the ACM (JACM) vol. 49, no. 5, pp. 640-671, 2002.
[20] B. Brenda S and S. Jerald S, “Shelf algorithms for two-dimensional packing problems”, SIAM Journal on Computing, vol. 12, no. 3, pp. 508-525, 1983.
[21] W. Lijun, Z. Defu and C. Qingshan, “A least wasted first heuristic algorithm for the rectangular packing problem”, Computers & Operations Research, vol. 36, no. 5, pp. 1608-1614, 2009.
[22] K. Olyvia, D. Samrat and K. Swagat, “Deep-Pack: A Vision-Based 2D Online Bin Packing Algorithm with Deep Reinforcement Learning”, 2019 28th IEEE International Conference on Robot and Human Interactive Communication (RO-MAN), pp. 1-7, 2019.
[23] Z. Hang, S. Qijin, Z. Chenyang, Y. Yin and X. Kai, “Online 3D bin packing with constrained deep reinforcement learning”, Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, no. 1, 2021.
[24] H. V. Hasselt, “Double Q-learning”, Advances in neural information processing systems, vol. 23, 2010
[25] S. Sameerkumar, M. Raymond and F. Andrea, “A cloud-native approach to 5G network slicing”, IEEE Communications Magazine, vol. 55, no. 8, pp. 120-127, 2017
[26] E. G. Coffman, J. Y-T Leung and D.W. Ting, “Bin packing: Maximizing the number of pieces packed”, Acta Informatica vol. 9, pp. 263-271, 1978.
[27] C. Thomas H, L. Charles E, R. Ronald L and S. Clifford, “Introduction to algorithms second edition”, MIT press, pp. 112, 2001.
[28] W. Xingbo and S. Zhen, “Analytic formulas to calculate symmetric brothers of a node in a perfect binary tree”, Journal of Mathematics Research, vol. 10, no. 5, pp.45-48, 2018
[29] H. Matteo, M. Joseph, V. H. Hado, S. Tom, O. Georg, D. Will, H. Dan, P. Bilal, A. Mohammad and S. David, “Rainbow: Combining improvements in deep reinforcement learning”, Proceedings of the AAAI conference on artificial intelligence. vol. 32, no. 1, 2018.
[30] K. Diederik P and B. Jimmy, “Adam: A method for stochastic optimization”, arXiv preprint arXiv:1412.6980, 2014

校內：2028-08-23公開
校外：2028-08-23公開電子論文尚未授權公開，紙本請查館藏目錄

簡易檢索 / 詳目顯示

相關論文