Tối ưu hóa vị trí Edge Node giảm chi phí theo độ trễ - Luận văn RMIT

Nghiên cứu tối ưu hóa vị trí đặt nút biên nhận biết độ trễ người dùng nhằm giảm thiểu chi phí triển khai hệ thống mạng điện toán biên hiệu quả.

• Tác giả: Xiaoyu Zhang
• Người hướng dẫn: Prof. Zhifeng Bao
• Trường học: RMIT University
• Chuyên ngành: Khoa học máy tính
• Đề tài: User-Delay-Tolerance-Aware Edge Node Placement Optimization for Cost Minimization
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2022
• Địa điểm: Melbourne

Tóm tắt

I. Tổng quan tối ưu hóa đặt nút biên nhận biết độ trễ người dùng

Điện toán biên di động (MEC) đóng vai trò then chốt trong hạ tầng viễn thông hiện đại. Công nghệ này đưa tài nguyên tính toán đến gần người dùng cuối hơn. Mô hình giúp giảm tải áp lực cho mạng lõi đám mây truyền thống. Luận văn thạc sĩ khoa học của tác giả Xiaoyu Zhang tập trung giải quyết bài toán đặt nút biên (Edge Node - EN) hiệu quả. Mục tiêu cốt lõi là tối thiểu hóa tổng chi phí triển khai phần cứng. Chi phí này gồm phí thuê địa điểm đặt nút và phí đầu tư máy chủ tính toán. Đồng thời, hệ thống vẫn phải đảm bảo yêu cầu nghiêm ngặt về độ trễ trải nghiệm của các tác vụ. Người dùng di động ngày nay sử dụng nhiều dịch vụ thời gian thực như xe tự hành và thực tế ảo. Các ứng dụng này đòi hỏi tốc độ phản hồi cực nhanh cùng độ tin cậy vượt trội. Việc xem xét mức độ chấp nhận độ trễ (delay tolerance) giúp nhà mạng linh hoạt cấu hình tài nguyên. Nghiên cứu kết hợp lý thuyết truyền dẫn Shannon và mô hình tính toán máy chủ. Phương pháp tiếp cận này tạo ra bước tiến lớn trong thiết kế mạng viễn thông thế hệ mới.

1.1. Khái niệm và vai trò của nút biên trong mạng MEC

Nút biên là máy chủ thu nhỏ đặt gần các trạm thu phát sóng (Base Station - BS). Vị trí đặt nút biên quyết định hiệu năng của toàn bộ mạng lưới. Khi khoảng cách vật lý rút ngắn, tín hiệu truyền tải ít bị suy hao và nhiễu sóng. Người dùng có thể giảm thiểu độ trễ phản hồi khi gửi yêu cầu xử lý dữ liệu nặng. Tuy nhiên, việc xây dựng nút biên tại tất cả trạm gốc gây tốn kém ngân sách lớn. Nhà mạng cần chọn lọc vị trí chiến lược để đặt nút biên. Mỗi nút biên có thể phục vụ nhiều trạm gốc lân cận. Mô hình quy hoạch chuẩn xác vừa tiết kiệm vốn đầu tư ban đầu, vừa nâng cao chất lượng dịch vụ tổng thể.

1.2. Tầm quan trọng của độ trễ chấp nhận được đối với chi phí

Độ trễ chấp nhận được của người dùng là ngưỡng thời gian tối đa để hoàn thành tác vụ. Yếu tố này bao gồm độ trễ truyền dữ liệu qua kênh vô tuyến và độ trễ tính toán. Mỗi loại ứng dụng di động sở hữu một ngưỡng trễ khác biệt. Nếu nhà mạng bỏ qua thông số này, hệ thống sẽ phải phân bổ máy chủ dư thừa. Việc phân bổ dư thừa đẩy chi phí vận hành và mua sắm thiết bị lên cao. Tận dụng độ trễ cho phép phân bổ khối lượng công việc linh hoạt giữa các nút biên. Các trạm gốc có thể định tuyến tác vụ đến nút biên xa hơn nếu độ trễ còn cho phép. Cơ chế tối ưu giúp giảm số lượng máy chủ cần trang bị.

II. Thách thức tối ưu hóa chi phí và mô hình hóa độ trễ nút biên

Bài toán tối ưu hóa chi phí đặt nút biên nhận biết độ trễ thuộc lớp bài toán NP-hard. Độ phức tạp tính toán gia tăng theo cấp số nhân khi số lượng trạm gốc mở rộng. Mô hình toán học cần cân bằng giữa hai thành phần trễ chính: trễ truyền dẫn và trễ tính toán. Trễ truyền dẫn chịu ảnh hưởng bởi băng thông kênh truyền và khoảng cách vật lý giữa trạm gốc và nút biên. Theo định lý Shannon, công suất nhiễu tăng tỷ lệ thuận với khoảng cách truyền sóng. Do đó, trạm gốc càng xa nút biên thì tốc độ truyền dữ liệu càng suy giảm. Trễ tính toán lại phụ thuộc trực tiếp vào khối lượng công việc và số lượng máy chủ lắp đặt. Nếu gán trạm gốc đến nút biên ở gần, trễ truyền dẫn thấp sẽ tạo dư địa cho trễ tính toán. Nhờ đó, nút biên cần ít máy chủ hơn mà vẫn đáp ứng giới hạn trễ cho phép. Thách thức lớn nằm ở việc tìm kiếm kế hoạch phân bổ tối ưu toàn cục. Kế hoạch này phải đồng thời xác định vị trí đặt nút và số lượng máy chủ tại từng vị trí.

2.1. Phân tích mô hình trễ truyền dẫn và tính toán chi tiết

Mô hình trễ tổng thể giữa trạm gốc và nút biên là tổng của trễ truyền dẫn và trễ tính toán. Trễ truyền dẫn được xác định bằng kích thước dữ liệu chia cho dung lượng kênh truyền. Dung lượng kênh phụ thuộc vào băng thông và tỷ số tín hiệu trên nhiễu theo công thức Shannon. Nhiễu kênh tăng theo khoảng cách địa lý giữa trạm và nút biên. Ngược lại, trễ tính toán bằng tổng khối lượng công việc chia cho tổng năng lực của các máy chủ. Mỗi máy chủ được giả định có năng lực tính toán đồng nhất. Việc phân bổ máy chủ rời rạc tạo ra tính chất phi tuyến tính trong bài toán tối ưu. Sự tương tác phức tạp giữa hai loại trễ đòi hỏi phương pháp mô hình hóa chuẩn xác.

2.2. Xung đột giữa chi phí hạ tầng và dung lượng phục vụ

Hàm mục tiêu chi phí bao gồm chi phí mở địa điểm nút biên và chi phí máy chủ. Chi phí mở nút biên là chi phí cố định cho mỗi vị trí được kích hoạt. Chi phí máy chủ tỷ lệ thuận với số lượng máy chủ được cài đặt. Việc kích hoạt nhiều nút biên giúp giảm khoảng cách truyền dẫn nhưng làm tăng chi phí mở địa điểm. Ngược lại, kích hoạt ít nút biên đòi hỏi lắp nhiều máy chủ tại mỗi nút để bù đắp trễ truyền dẫn cao. Sự đánh đổi này tạo ra không gian tìm kiếm khổng lồ với nhiều cục bộ tối ưu. Việc giải quyết xung đột đòi hỏi thuật toán có khả năng cân bằng tải thông minh giữa các vùng phủ sóng.

III. Giải pháp tối ưu hóa vị trí đặt nút biên giảm thiểu chi phí

Luận văn đề xuất các phương pháp tiếp cận đa dạng để giải quyết bài toán tối ưu. Đầu tiên, phương pháp Quy hoạch số nguyên hỗn hợp (MIP) được xây dựng nhằm tìm nghiệm tối ưu tuyệt đối. MIP mô hình hóa chính xác các ràng buộc logic và giới hạn độ trễ. Tuy nhiên, MIP tiêu tốn nhiều tài nguyên tính toán khi kích thước mạng tăng cao. Để khắc phục nhược điểm về thời gian, kỹ thuật phân cụm kết hợp MIP (Cluster-based MIP) được áp dụng. Phương pháp này chia mạng lưới lớn thành các cụm nhỏ độc lập để giải quyết song song. Tiếp theo, tác giả phát triển thuật toán heuristic đột phá mang tên DA-CFS. Thuật toán này tích hợp kỹ thuật tìm kiếm chuyển tiếp nhận biết độ trễ để tăng tốc xử lý. Phiên bản cải tiến DA-CFS-F bổ sung bước tối ưu hóa chi tiết (fine-grained optimization). Nhờ đó, DA-CFS-F duy trì hiệu quả tiết kiệm chi phí vượt trội mà vẫn giữ tốc độ xử lý nhanh. Kết quả thử nghiệm trên hàng ngàn trạm gốc chứng minh tính khả thi thực tiễn.

3.1. Phương pháp quy hoạch số nguyên hỗn hợp MIP và phân cụm

Phương pháp quy hoạch số nguyên hỗn hợp (MIP) thiết lập chuẩn đối sánh cho bài toán. MIP thiết lập công thức toán học chặt chẽ với các biến nhị phân đại diện cho quyết định đặt nút. Thuật toán tìm ra giải pháp tối ưu toàn cục nhưng đòi hỏi thời gian tính toán rất lớn. Khi số lượng trạm gốc vượt quá quy mô vừa, MIP thuần túy trở nên bất khả thi. Kỹ thuật MIP phân cụm (Cluster-based MIP) giải quyết bài toán trên từng phân vùng không gian. Phương pháp này giảm thiểu số lượng biến số cần xử lý trong một phiên tính toán. Nhờ đó, hiệu năng tổng thể được cải thiện đáng kể trong khi chất lượng nghiệm vẫn ở mức cao.

3.2. Thuật toán Heuristic cải tiến DA CFS và DA CFS F

Thuật toán DA-CFS được thiết kế để giải quyết bài toán quy mô lớn trong thời gian ngắn. Thuật toán ưu tiên gán trạm gốc đến nút biên gần nhất để tối thiểu hóa trễ truyền dẫn. Khi trễ truyền dẫn thấp, nút biên có thêm quỹ thời gian cho việc tính toán dữ liệu. Điều này giúp giảm số lượng máy chủ cần trang bị tại mỗi vị trí nút. Biến thể DA-CFS-F kết hợp thêm giai đoạn tinh chỉnh chi tiết từng vị trí máy chủ. Cơ chế này loại bỏ các máy chủ dư thừa mà không vi phạm ràng buộc trễ. Thực nghiệm chứng minh DA-CFS-F đạt khả năng mở rộng vượt trội với hàng ngàn trạm gốc.

IV. Kết luận và ứng dụng thực tiễn của tối ưu hóa đặt nút biên

Nghiên cứu về tối ưu hóa vị trí đặt nút biên nhận biết độ trễ mang lại giá trị thực tiễn to lớn. Luận văn cung cấp khung giải pháp toàn diện cho việc thiết kế mạng biên di động hiệu quả kinh tế. Các nhà mạng viễn thông có thể áp dụng mô hình để lập kế hoạch triển khai hạ tầng 5G và 6G. Việc kết hợp thông minh giữa trễ truyền dẫn và trễ tính toán giúp giảm thiểu đáng kể chi phí vốn đầu tư. Đồng thời, chất lượng dịch vụ của các ứng dụng nhạy cảm với độ trễ được đảm bảo tuyệt đối. Thuật toán DA-CFS-F thể hiện tính khả thi cao khi ứng dụng vào các đô thị thông minh có mật độ trạm dày đặc. Hệ thống hỗ trợ xử lý mượt mà các tác vụ phức tạp như điều khiển giao thông tự động và giám sát an ninh. Ngoài ra, mô hình còn mở ra hướng nghiên cứu mới về quản lý năng lượng xanh tại các trung tâm dữ liệu biên. Đây là cơ sở khoa học vững chắc cho việc phát triển bền vững hạ tầng số tương lai.

4.1. Ứng dụng trong quy hoạch mạng 5G và đô thị thông minh

Trong kỷ nguyên 5G, mạng biên di động là yếu tố quyết định để hiện thực hóa dịch vụ đô thị thông minh. Mô hình tối ưu hóa giúp các nhà khai thác viễn thông xác định chính xác vị trí đặt trung tâm dữ liệu biên. Các hệ thống điều khiển giao thông thông minh và camera an ninh đòi hỏi phản hồi thời gian thực với độ trễ dưới 10 mili giây. Nhờ thuật toán phân bổ hiệu quả, hệ thống phân phối luồng xử lý ổn định mà không gây quá tải cục bộ. Quy hoạch mạng tối ưu giảm thiểu áp lực đầu tư hạ tầng cho doanh nghiệp. Đồng thời, giải pháp nâng cao tính ổn định và độ tin cậy của toàn bộ mạng lưới truyền thông đô thị.

4.2. Hướng phát triển và mở rộng nghiên cứu trong tương lai

Nghiên cứu mở ra nhiều triển vọng phát triển cho các bài toán tối ưu hóa mạng biên trong tương lai. Một hướng đi tiềm năng là tích hợp tính di động động của người dùng vào mô hình phân bổ trễ. Việc người dùng di chuyển liên tục giữa các trạm phát sóng đòi hỏi cơ chế di trú tác vụ linh hoạt. Ngoài ra, việc bổ sung yếu tố tiêu thụ năng lượng xanh vào hàm mục tiêu chi phí là rất cần thiết. Các trung tâm dữ liệu biên sử dụng năng lượng tái tạo sẽ giúp giảm phát thải carbon hiệu quả. Sự kết hợp giữa trí tuệ nhân tạo và thuật toán heuristic hứa hẹn mang lại giải pháp tự thích ứng thời gian thực.

Trích đoạn nội dung tài liệu

User-Delay-Tolerance-Aware Edge Node Placement Optimization for Cost Minimization A thesis submitted in fulfillment of the requirements for the degree of Master of Science Xiaoyu Zhang School of Computing Technologies College of Science, Technology, Engineering and Maths RMIT University Melbourne, Victoria, Australia May, 2022 Declaration I certify that except where due acknowledgement has been made, this research is that of the author alone; the content of this research submission is the result of work which has been carried out since the official commencement date of the approved research program; any editorial work, paid or unpaid, carried out by a third party is acknowledged; and, ethics procedures and guidelines have been followed. In addition, I certify that this submission contains no material previously submitted for award of any qualification at any other university or institution, unless approved for a joint- award with another institution, and acknowledge that no part of this work will, in the future, be used in a submission in my name, for any other qualification in any university or other tertiary institution without the prior approval of the University, and where applicable, any partner institution responsible for the joint-award of this degree. I acknowledge that copyright of any published works contained within this thesis resides with the copyright holder(s) of those works. I give permission for the digital version of my research submission to be made available on the web, via the University’s digital research repository, unless permission has been granted by the University to restrict access for a period of time I acknowledge the support I have received for my research through the provision of an Australian Government Research Training Program Scholarship.

Xiaoyu Zhang School of Computing Technologies, RMIT University 07 March, 2022 Acknowledgement I would like to express my gratitude to my supervisors, Prof. Zhifeng Bao and Dr. Hai Dong, who guided me throughout this Master by Research study, for their excellent supervision, great engagement, and remarkable support in the last year. They offered me a precious and splendid research journey.

I would also like to thank my family and friends who always support my study. I wish to acknowledge the help provided by the staff in the School of Computing Technology of RMIT University. Contents Declaration ii Acknowledgement iii Contents iv List of Figures vii List of Tables viii Abstract 1 1 Introduction 3 1.1 MEC Network and Key Components .1 Delay Aware Edge Nodes Placement .2 Cost and Delay Aware Edge Node Placement. 14 3 Problem Formulation 16 iv CONTENTS v 3.2 Coarse-grained Formulation .3 Qualified EN Placement Plan .3 Fine-Grained Formulation .3 Qualified EN Placement Plan .4 Cost Minimization in MEC Edge Node Placement Problem.

23 4 Hardness Analysis 24 5 Solutions 26 5.1 MIP-based Methods .1 Mixed-Integer Programming (MIP) .2 Cluster-based MIP .2 Heuristic-based Methods .1 Coverage First Search (CFS) .2 Distance Aware Coverage First Search (DA-CFS) .3 Fine-grained Optimization .3 Methods for Comparison .3 Discussion on Scalability .4 Transmission and Computation Delay in θ .5 The Impact of θ .7 Clustering Results for MIP+Cluster .8 Ablation Study on τ for DA-CFS. 49 7 Conclusion 50 Appendices 51 Credits. 51 Bibliography 52 List of Figures 1.1 Mobile Cloud Computing Network Architecture .2 Mobile Edge (Multi-Access) Computing Network Architecture .3 Example of Optimal EN Deployment under Different Delay Tolerance .1 Effectiveness and efficiency with different BS input scale .2 Cost generated by MIP+Cluster with running time limit of 10min and 1h per cluster 41 6.3 Distribution of BSs with different transmission delay proportions on θ .4 Effectiveness and efficiency with different θ value .5 Deployment cost: Peak vs.6 Visualise clusters on Shanghai Telecom Dataset. 47 vii List of Tables 1.1 Example of fine-grained workload in BS and EN .1 Literature review of delay minimization problems .2 Literature review of cost minimization problems .1 Table of notations .2 Estimated EN coverage with different θ value .3 Cluster results on different BS input scale .4 Cost and # of EN selected with different τ in DA-CFS.

48 viii Abstract With the prosperity of 5G technologies, Mobile (or Multi-Access) edge computing (MEC) has emerged as the next generation of network architecture. Compared with the previous Mobile Cloud Computing (MCC) architecture, MEC’s decentralising network architecture empowered it amplify user accessible resource and low-latency access. Investigating how to effectively place edge nodes, which are also known as edge servers, has become a trendy research topic and attracted wide attention among researchers. Among existing studies in this research field, most of the works aim to minimize delays experienced by mobile users, which can be achieved by reaching a workload balance between edge nodes, such that the computation capacity from edge nodes can be fully used.

However, considering the real use cases, cost-saving, rather than the extremely low network latency, is the prime goal that a service provider (i. the telecom companies) pursue when deploying edge nodes to a network as users have their delay tolerance within a threshold rather than pursuing a zero-latency network. Therefore, how to place edge nodes with the minimum cost, including the construction cost for setting up the edge nodes and the server cost for adding server units to the sites, is still worth further study. Although extensive studies have been conducted to find the optimal edge node deployment strategies with the objective of cost minimization, the formulation of such a problem is not close enough to the real-world cases.

First, they barely take into account the relationship between the allocation of corresponding computation resources and users’ delay tolerance. To be more specific, instead of achieving a workload balance on each homogeneous capacitated edge node, the edge nodes can have the heterogeneous capacity, depending on the number of users they would serve and the corresponding workload. Second, the delay has not been addressed precisely enough, as most of the existing work only considers the transmission delay while ignoring the computation delay 1 which is decided by the edge node capacity and the workload together. In our work, we define a Cost Minimization in MEC Edge Node Placement (CMMENP) problem to find an optimal edge node deployment strategy such that the cost can be minimized without exceeding users’ delay tolerance.

We precisely define the delay with both transmission delay and computation delay. We prove the NP-hardness of this problem and propose a series of solutions, including Cluster- based Mixed Integer Programming, Coverage First Search, and Distance-Aware Coverage First Search. Intuitively, the Cluster-based Mixed Integer Programming solves the efficiency issue in the pure MIP solution by sacrificing some degree of accuracy, while the Coverage First Search is an efficiency prioritized solution with Distance-Aware Coverage First Search to further improve its effectiveness without loss of efficiency. In addition, we propose a fine-grained optimization strategy to delicately allocate computation resources to edge nodes at the user service request level, which can remarkably decrease the deployment cost.

Comprehensive experiments have been conducted on a large-scale real-world dataset, which demonstrates the competitiveness of our solutions in terms of efficiency, effectiveness and scalability compared with the state-of-art work. 2 Chapter 1 Introduction Mobile (or Multi-Access) Edge Computing (MEC) emerges as a novel computing paradigm ac- companying the rise of 5G technology. In terms of the three use cases of 5G network: enhanced mobile broadband, ultra-reliable and low latency, and massive machine-type communications, it requires higher network performance to support those use cases [1]. The previous Mobile Cloud Computing (MCC) can no longer satisfy the requirement of the 5G network, which is limited by its centralized network architecture as shown in Fig 1.

In MCC, computing resources are centralized at the cloud and such architecture has the following shortages [2]: (1) Clouds are usually far away from end-users (some of them even across continents), which inevitably causes high transmission delay. (2) even though the cloud has plenty of computation resources and has extra strong computation capacity, as the cloud is shared by a very large number of users, the resources allocated to each user are actually limited, which will cause high computation delay. MEC is proposed to leverage the performance gap of MCC. Compare with MCC, MEC has the following advantages that are beneficial from its decentralized architecture [3], as shown in Fig 1.

Edge nodes are close to end-users (usually less than 5km), thus it will incur low transmission delay. (2) although each of the edge servers has limited computation resources, as it is shared by only a small group of users, the resource allocated to each user is richer than MCC does. Thus, it 3 CHAPTER 1. INTRODUCTION 4 incurs low computation delay accordingly.

Cloud Base Base Base Station Station Station Figure 1.1: Mobile Cloud Computing Network Architecture Base Station Base Base Station Station Edge Node Edge Node Base Station Edge Node Base Station Figure 1.2: Mobile Edge (Multi-Access) Computing Network Architecture Inspired the distributed property of the MEC and its high expectation for network perfor- mance, in this thesis, we study the problem of optimal edge node deployment, aiming to provide qualified and low-latency services to massive mobile users citywide with minimum cost. There Motivation 5 are three primary factors that require to be considered during the decision-making process of edge node deployment: First, guaranteeing the Quality of Service (QoS) is a fundamental requirement of the net- work deployment [2]. For example, latency, as one of the most important QoS factors, should not exceed users’ tolerance [4, 5, 6, 7, 8]. Second, minimizing the deployment cost is always prioritized and should never be neglected [9, 10, 11, 12].

There are many factors that can affect the cost, including edge node site selection, computation resource allocation, computation tasks assignment, etc. Third, since the resource is limited, while MEC is designed to provide users with richer resources, it should be optimized for higher productivity [13, 14, 15, 16, 17, 18, 19]. It is always the ideal case that the selected edge nodes are allocated with “just enough” com- putation resources.1 Motivation When it comes to deploy edge nodes to the network, there is always a trade-off between the edge node deployment cost and the delay experienced by mobile users [20]. Such a trade-off is highly related to edge node site selection and corresponding resource allocation.

Deploy- ing more edge nodes can potentially reduce the transmission delay by decreasing the average distance between base stations and edge nodes. Also, adding more servers (i. computing re- sources) into edge nodes can cut down the computation delay as edge nodes would have higher computation capacity. However, both cases will inflate the overall deployment cost.

Fortu- nately, users would never expect a zero-latency network and instead have tolerance thresholds on the delay. Thus, by leveraging the threshold, we have an opportunity to optimize the edge node deployment strategy with the minimum overall deployment cost. The following sample scenario demonstrates how the edge node selection and the corresponding resource allocation matter to the deployment cost under various user’s delay tolerance values.3 demonstrates how users’ tolerance on service delay affects the optimal edge node deployment when considering cost-efficiency. In this figure, the blue numbers represent the distance while the black numbers represent the workload of base stations and Motivation 6 edge nodes.

The workload and the distance together decide the transmission latency, while the workload matters to the computation delay.3a shows the initial connections between base stations which are candidate potential locations to deploy edge nodes (i., edge nodes co-locate with base stations). Developing an edge node within a base station will introduce a setup cost, while adding servers to an edge node to increase its computing capacity will generate server purchase costs. Given users’ delay tolerance threshold and the goal of cost minimization, placing edge nodes at appropriate base stations with a right number of servers can significantly reduce the overall cost. With the objective of minimizing the total cost, the optimal edge node deployment strategy would vary under different users’ delay tolerance.