Tóm Tắt TỐI ƯU HÓA ĐIỀU PHỐI TÁC VỤ TRONG ĐIỆN TOÁN BIÊN THÔNG QUA HỌC TĂNG CƯỜNG

Vì thế, một mô hình mở rộng của điện toán đám mây,điện toán biên đa truy cập Multi-access Edge Computing - MEC đã được đề xuất bởi Việntiêu chuẩn viễn thông châu Âu European Telecommunic

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC BÁCH KHOA HÀ NỘI

ĐỖ BẢO SƠN

TỐI ƯU HÓA ĐIỀU PHỐI TÁC VỤ TRONG

ĐIỆN TOÁN BIÊN THÔNG QUA HỌC TĂNG CƯỜNG

Ngành: Khoa học máy tính

Mã số: 9480101

TÓM TẮT LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH

Hà Nội - 2025

Công trình được hoàn thành tại:

Đại học Bách khoa Hà Nội

Người hướng dẫn khoa học:

Vào hồi giờ , ngày tháng năm

Có thể tìm hiểu luận án tại thư viện:

1 Thư viện Tạ Quang Bửu - Đại học Bách khoa Hà Nội

2 Thư viện Quốc gia Việt Nam

MỞ ĐẦU

Ngày nay, Internet vạn vật (Internet of Things - IoT) đã trở thành một công nghệ quan trọngđược ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau như y tế, lưới điện thông minh, giaothông, v.v Ví dụ, trong lĩnh vực y tế, IoT có thể được áp dụng để theo dõi sức khỏe của bệnhnhân từ xa và nâng cao quản lý dữ liệu y tế Trong lĩnh vực lưới điện thông minh, IoT giúptối ưu hóa việc sử dụng năng lượng và quản lý hệ thống điện hiệu quả hơn Trong mạng IoT,

số lượng thiết bị người dùng cuối (End User - EU) như điện thoại thông minh, đồng hồ thôngminh, cảm biến, v.v có sự tăng trưởng rất lớn Statista ước tính đến năm 2025 sẽ có khoảng 19

tỷ thiết bị IoT [1], mang lại giá trị kinh tế khổng lồ, với khoảng từ 3.9 đến 11.1 nghìn tỷ đô la

Mỹ [2] Bên cạnh những tiềm năng kinh tế, mạng IoT cũng phải đối mặt với các thách thức vềtài nguyên Các thiết bị IoT thường có giới hạn về dung lượng pin, bộ nhớ và khả năng xử lý

Do đó, các tác vụ, dữ liệu được sinh từ thiết bị IoT thường được gửi đến máy chủ đám mây đểlưu trữ và xử lý Điện toán đám mây cung cấp nền tảng lưu trữ và tính toán cho các tác vụ đượcsinh ra bởi các thiết bị IoT [3]

Tuy nhiên, do khoảng cách địa lý giữa các trung tâm đám mây và người dùng cuối, việctruyền dữ liệu qua mạng có thể gây ra độ trễ cao cho các ứng dụng yêu cầu phản hồi tức thìnhư các hệ thống IoT thời gian thực Vì thế, một mô hình mở rộng của điện toán đám mây,điện toán biên đa truy cập (Multi-access Edge Computing - MEC) đã được đề xuất bởi Việntiêu chuẩn viễn thông châu Âu (European Telecommunications Standards Institute - ETSI) [4].Trong MEC, các tài nguyên lưu trữ và tính toán được triển khai đến gần một số lượng lớn cácthiết bị IoT và dùng để xử lý một phần hoặc toàn bộ tác vụ, từ đó giảm độ trễ của các ứng dụngIoT Ngoài ra, những tiến bộ của các công nghệ trên phương tiện giao thông [5–7] mang đếntiềm năng mở rộng hệ thống máy chủ biên Điện toán biên trong giao thông (Vehicular EdgeComputing - VEC) [8] được giới thiệu giúp gia tăng sức mạnh tính toán của các máy chủ biên.VEC không chỉ có tài nguyên tính toán từ máy chủ biên và hạ tầng đám mây, công nghệ nàycòn tận dụng nguồn tài nguyên được đặt trên các phương tiện giao thông thông minh Sự khácbiệt quan trọng giữa MEC và VEC là trong VEC, ngoài việc xử lý dữ liệu tại các nút biên truyềnthống, các phương tiện di chuyển cũng có thể đóng vai trò như các máy chủ biên di động, giúpgia tăng sức mạnh tính toán của hệ thống và tối ưu hóa việc xử lý dữ liệu trong môi trường giaothông

Trong môi trường VEC, việc điều phối tác vụ giữa các máy chủ, bao gồm máy chủ đámmây, máy chủ biên và máy chủ đặt trên phương tiện giao thông, đóng vai trò quan trọng trongviệc đảm bảo xử lý tác vụ với độ trễ thấp Luận án xem xét hai phương pháp tiếp cận để tối ưuhóa độ trễ trong VEC: (i) tối đa hóa số lượng tác vụ được xử lý đúng hạn [9], (ii) tối thiểu hóatổng thời gian quá hạn xử lý của các tác vụ [10]

Môi trường VEC có tính di động cao, phức tạp, đòi hỏi một bộ lập lịch hiệu quả cho tác vụ

độ trễ thấp Các thuật toán tham lam có thời gian tính toán nhanh nhưng đơn giản nên thườngkhông đảm bảo được chất lượng lời giải trong môi trường phức tạp như VEC Các thuật toánnhư thuật toán di truyền [11], thuật toán tối ưu bầy đàn [12], v.v cần nhiều thời gian và môitrường tĩnh để đưa ra quyết định điều phối tác vụ, vì vậy, chưa phù hợp với yêu cầu ra quyếtđịnh liên tục trong VEC Hơn nữa, các phương pháp này không xét đến độ ảnh hưởng của việcđiều phối tác vụ tại thời điểm hiện tại đến các thời điểm tiếp theo, dẫn đến hiệu quả tổng thểgiảm sút

Mặt khác, học tăng cường (Reinforcement Learning - RL) [13] có thể tận dụng các kinhnghiệm trong quá khứ để đưa ra các quyết định điều phối tác vụ nhanh và hiệu quả Các thuậttoán RL giúp tác nhân học các chiến lược ra quyết định hiệu quả qua việc tương tác với môitrường Bằng cách tận dụng RL, hệ thống VEC có thể thích nghi với các điều kiện môi trườngthay đổi và phân bổ tài nguyên tối ưu Điều này giúp giảm thiểu thời gian xử lý tác vụ và đápứng yêu cầu chất lượng dịch vụ

Mục tiêu nghiên cứu của luận án

Mục tiêu chính của luận án là nghiên cứu phát triển các thuật toán học tăng cường để tối ưuquá trình điều phối tác vụ trong VEC Trong VEC, một số tác vụ phức tạp được gửi đến máychủ biên để xử lý tạo thành mô hình hai tầng gồm thiết bị đầu cuối và máy chủ biên Đối vớicác bài toán yêu cầu khả năng tính toán cao, máy chủ đám mây có thể được sử dụng, do đó, tạothành mô hình ba tầng Luận án này nghiên cứu cả hai mô hình để tối ưu hóa quyết định điềuchuyển phù hợp với từng loại tác vụ Các mục tiêu cụ thể trong luận án là nghiên cứu bài toánđiều phối tác vụ nhằm:

1 Tối đa hóa số lượng tác vụ được xử lý đúng hạn trong điện toán biên hai tầng trong giaothông Trong mô hình hai tầng, tác vụ chủ yếu được xử lý tại máy chủ biên, nơi có tàinguyên hạn chế nhưng đảm bảo độ trễ thấp Do đó, mục tiêu là xử lý được nhiều tác vụđúng hạn nhất có thể, giúp tối ưu hóa tài nguyên hệ thống và nâng cao chất lượng dịch vụ

2 Tối thiểu hóa độ trễ xử lý các tác vụ trong điện toán biên ba tầng trong giao thông Trong

mô hình ba tầng, một số tác vụ phức tạp có thể được gửi đến máy chủ đám mây, nhưngđiều này có thể làm tăng độ trễ xử lý tác vụ Vì vậy, mục tiêu là giảm thiểu tổng thời gian

xử lý tác vụ, đảm bảo hệ thống vận hành hiệu quả và đáp ứng kịp thời các yêu cầu thờigian thực

Phạm vi nghiên cứu

• Luận án tập trung vào tối ưu hóa điều phối tác vụ cho hai kiến trúc điện toán biên tronggiao thông được giải thích như sau:

– Mặc dù quá trình điều phối tác vụ liên quan đến nhiều khía cạnh như lập lịch tác vụ

và phân bổ tài nguyên, luận án này tập trung vào bài toán tối ưu hóa điều chuyểntác vụ (task offloading), tức là xác định máy chủ (biên hoặc đám mây) xử lý tối ưunhằm giảm thiểu độ trễ và cải thiện hiệu suất hệ thống

– Kiến trúc điện toán biên hai tầng trong giao thông: gồm tầng biên và tầng người

dùng cuối Tầng biên gồm trạm gốc và các máy chủ biên (edge servers) được triểnkhai tại trạm gốc hoặc trên các phương tiện giao thông thông minh Các tác vụ từngười dùng cuối sẽ được xử lý tại các máy chủ biên để giảm độ trễ và cải thiện hiệusuất xử lý

– Kiến trúc điện toán biên ba tầng trong giao thông: mô hình này mở rộng kiến trúc

hai tầng bằng cách bổ sung thêm một tầng đám mây, trong đó các máy chủ đám mây(cloud servers) cung cấp khả năng tính toán và lưu trữ cao Tuy nhiên, tốc độ truyền

dữ liệu từ tầng đám mây đến các tầng khác bị giới hạn do khoảng cách về địa lý

• Luận án áp dụng mô hình truyền thông Shannon-Hartley [14] để tính toán tốc độ truyền

dữ liệu không dây giữa các máy chủ biên di động và các trạm thu phát tín hiệu Luận ánchỉ tập trung xem xét vào yếu tố khoảng cách giữa máy chủ biên di động và trạm thu pháttín hiệu Các yếu tố khác như băng thông, công suất truyền và mức độ nhiễu được cố định

để đơn giản hóa phân tích Việc này cho phép tập trung vào ảnh hưởng của khoảng cáchđến hiệu suất truyền dữ liệu

• Luận án xem xét các tác vụ IoT được sinh ra liên tục từ các thiết bị IoT Mỗi tác vụ khôngthể chia thành các phần nhỏ hơn Đồng thời, mỗi tác vụ là độc lập, do đó không có mốiquan hệ phụ thuộc giữa các tác vụ

• Các máy chủ biên được mô hình hóa với hàng đợi xử lý tác vụ theo mô hình M/M/1[15, 16] Các hàng đợi này tuân theo nguyên tắc “đến trước phục vụ trước” (FIFO), mộtphương pháp phổ biến trong các nghiên cứu về điện toán biên [17–20] Các giả định nàycho phép luận án tập trung vào việc tối ưu hóa điều phối tác vụ trong các môi trường điệntoán biên trong giao thông

Phương pháp nghiên cứu

Trong khuôn khổ nghiên cứu của đề tài, để đạt được các mục tiêu đã đề ra, luận án đã ápdụng một số phương pháp nghiên cứu cụ thể như sau:

• Nghiên cứu lý thuyết, phân tích tài liệu

• Phương pháp khảo sát được áp dụng để thu thập, tổng hợp và phân tích các công trìnhnghiên cứu đã được công bố trên một số nguồn cơ sở dữ liệu học thuật chính thống (nhưIEEE, ScienceDirect, Google Scholar, v.v.) có liên quan đến đề tài nhằm xác định khoảngtrống nghiên cứu

• Phương pháp so sánh được sử dụng nhằm phân tích và đánh giá mô hình đề xuất so vớicác mô hình truyền thống khác.

• Phương pháp kiểm chứng được áp dụng để mô phỏng phương pháp đề xuất dựa trên cácthực nghiệm của nghiên cứu liên quan

• Các kỹ thuật và công cụ phần mềm phục vụ cho việc thực nghiệm được triển khai bằngngôn ngữ lập trình Python

Các đóng góp của luận án

Để đạt được những mục tiêu nghiên cứu trên, luận án có các đóng góp chính như sau:

• Thứ nhất, bài toán tối ưu điều phối tác vụ để tối đa hóa số lượng tác vụ được xử lý đúng

hạn trong điện toán biên hai tầng trong giao thông Luận án đề xuất mô hình điện toán

biên hai tầng trong giao thông Mô hình xem xét tích hợp thêm các máy chủ biên di động,

từ đó tăng cường tính linh hoạt của tài nguyên tính toán so với mô hình điện toán biên chỉ

sử dụng máy chủ biên cố định Phương pháp phổ biến để giải quyết bài toán điều phốitác vụ trong điện toán biên là sử dụng các thuật toán meta-heuristic (thuật toán di truyền,thuật toán bầy đàn, v.v.) [21, 22] Tuy nhiên, với máy chủ biên di động, môi trường biêntrở nên động và phức tạp hơn Vì thế, các thuật toán meta-heuristic khó đưa ra được lờigiải tốt trong môi trường điện toán biên [23] Luận án đưa ra các đề xuất sau để tối ưuđiều phối tác vụ trong môi trường phức tạp trên:

– Mô hình hóa bài toán tối ưu điều phối tác vụ để tối đa hóa số lượng tác vụ được xử

lý đúng hạn dưới dạng quá trình quyết định Markov

– Đề xuất thuật toán học tăng cường cân bằng tỷ lệ giữa khai thác - khám phá dựa trên

phần thưởng nhận được

– Đề xuất thuật toán học tăng cường kết hợp logic mờ nhằm đưa ra các quyết định tối

ưu từ giai đoạn đầu khi tác tử chưa được huấn luyện

– Logic mờ có thể hạn chế khả năng của hệ thống trong việc thích ứng với các thay

đổi lâu dài Để khắc phục điều này, luận án đã đề xuất một phương pháp cân bằnggiữa học tăng cường và logic mờ, nhằm duy trì hiệu quả tối ưu không chỉ trong giaiđoạn khởi đầu mà còn trong các điều kiện động dài hạn

• Thứ hai, bài toán tối ưu điều phối tác vụ để tối thiểu hóa độ trễ xử lý tác vụ trong điện

toán biên ba tầng trong giao thông Luận án đề xuất mô hình điện toán biên ba tầng trong

giao thông Mô hình này phức tạp hơn mô hình điện toán biên hai tầng trong giao thông

vì xem xét thêm máy chủ đám mây Vì vậy, các thuật toán meta-heuristic cũng không phùhợp cho mô hình này Trong bối cảnh này, luận án đề xuất thuật toán học tăng cường để

xử lý các thuộc tính biến động của tác vụ, qua đó nâng cao hiệu quả của quá trình học vàtối thiểu hóa độ trễ Các tác tử học tăng cường có thể quan sát sự chuyển đổi của trạngthái để ước tính giá trị của từng hành động mà tác tử có thể thực hiện Mỗi trạng thái sẽ

ảnh hưởng đến trạng thái kế tiếp Tuy nhiên, một số thuộc tính trong trạng thái hiện tại

có thể không tác động đến trạng thái ở thời điểm khác Do đó, luận án đưa ra các đề xuấtsau:

– Mô hình hóa bài toán tối ưu điều phối tác vụ để tối thiểu hóa độ trễ xử lý tác vụ dưới

dạng quá trình quyết định Markov

– Đề xuất thuật toán điều phối tác vụ theo định hướng lợi thế với sơ đồ mạng Dueling

Actor-Insulator (ADAI) - phương pháp học tăng cường dựa trên giá trị nhằm xử lýcác thuộc tính biến động của các tác vụ để quá trình học trở nên hiệu quả hơn

– Đề xuất thuật toán điều phối tác vụ dựa trên Actor Critic - phương pháp học tăng

cường dựa trên chính sách học trực tiếp chiến lược giảm tải tác vụ

Cấu trúc của luận án

Ngoài phần mở đầu và phần kết luận, nội dung của luận án được trình bày trong ba chươngchính như sau:

• Chương 1: Cơ sở lý thuyết và tổng quang bài toán điều phối tác vụ trong điện toán biên.Chương này trình bày cơ sở lý thuyết về điện toán biên, bài toán điều phối tác vụ và một

số hướng tiếp cận giải bài toán điều phối tác vụ Ngoài ra, chương này cũng trình bày cáckiến thức nền tảng về học tăng cường và chi tiết một số thuật toán học tăng cường

• Chương 2: Tối đa hóa số lượng tác vụ đúng hạn trong điện toán biên hai tầng trong giaothông Chương này nghiên cứu bài toán điều phối tác vụ tối đa hóa số lượng tác vụ được

xử lý đúng hạn trong điện toán biên hai tầng trong giao thông Luận án đề xuất thuật toánhọc tăng cường để đưa ra quyết định điều phối tác vụ hiệu quả khi chưa trải qua giai đoạnhuấn luyện

• Chương 3: Tối thiểu hóa độ trễ xử lý các tác vụ trong điện toán biên ba tầng trong giaothông Chương này nghiên cứu bài toán điều phối tác vụ để tối thiểu hóa thời gian quáhạn xử lý của các tác vụ Luận án đề xuất thuật toán học tăng cường xem xét xử lý cácthuộc tính biến động ảnh hưởng đến quyết định điều phối tác vụ

Nội dung trình bày tại các chương 2 và 3 là các kết quả nghiên cứu chính của luận án Trướckhi trình bày chi tiết về các kết quả nghiên cứu chính và đóng góp mới cho khoa học của luận

án, các cơ sở lý thuyết nền tảng được giới thiệu để làm cơ sở đề xuất mô hình lý thuyết và thuậttoán giải quyết vấn đề

Chương 1

CƠ SỞ LÝ THUYẾT VÀ TỔNG QUAN BÀI TOÁN ĐIỀU PHỐI TÁC VỤ TRONG ĐIỆN TOÁN BIÊN

1.1 Điện toán biên

Điện toán biên (Edge Computing - EC) là một mô hình điện toán phân tán, trong đó các tàinguyên tính toán và lưu trữ được triển khai tại biên của mạng, gần với các thiết bị người dùngcuối hoặc thiết bị IoT [24] Mô hình này giúp giảm độ trễ và băng thông cần thiết để truyềntải dữ liệu về các trung tâm dữ liệu đám mây, từ đó cải thiện hiệu suất và tiết kiệm tài nguyênmạng Kiến trúc của điện toán biên thường có ba lớp chính minh họa trong Hình 1.1:

• Tầng đám mây (Cloud Layer) bao gồm các máy chủ đám mây hiệu năng cao được triểnkhai tập trung Các máy chủ đám mây có khả năng tính toán mạnh mẽ và dung lượng lưutrữ lớn, dẫn đến mức độ tiêu thụ năng lượng cao và chi phí hoạt động cao Tầng đám mây

sẽ được ưu tiên lưu trữ các dữ liệu quan trọng và xử lý các công việc lớn yêu cầu khả năngtính toán lớn

• Tầng biên (Edge Layer) bao gồm các nút biên (Edge Node - EN) nằm ở biên mạng (thànhphần của mạng máy tính gần với người dùng cuối nhất có nhiệm vụ quản lý lưu lượng,đảm bảo truyền tải dữ liệu và dịch vụ trơn tru đến các thiết bị cuối [25]) EN có thể đượctriển khai cố định tại một vị trí hoặc đặt trên các phương tiện di động Các EN được triểnkhai giữa các thiết bị cuối và đám mây như tại trung tâm mua sắm, công viên, v.v Các

EN hình thành hệ thống phân tán có khả năng ảo hóa, lưu trữ, xử lý dữ liệu

• Tầng thiết bị (Devices Layer) gần người dùng cuối Tầng này bao gồm các thiết bị kếtnối Internet như điện thoại thông minh, camera giám sát, ô tô thông minh, cảm biến, thiết

bị IoT, v.v Các thiết bị này tạo ra các tác vụ, dữ liệu và truyền những tác vụ, dữ liệu nàyđến tầng biên để xử lý hoặc lưu trữ Các thiết bị trong tầng này có khả năng kết nối khôngdây hoặc có dây với các nút biên

Với mỗi loại ứng dụng trong thực tế sẽ có mô hình điện toán phù hợp để tính toán, xử lý vàlưu trữ dữ liệu Các mô hình điện toán thường được sử dụng trong thực tế như điện toán sương

mù, điện toán đám mây và điện toán biên

Điện toán đám mây (Cloud Computing - CC) là mô hình tập trung, cung cấp tài nguyên vàdịch vụ thông qua các máy chủ từ xa trên Internet Mặc dù mang lại lợi ích về khả năng tính

Tầng thiết bị

Tầng biên

Tầng đám mây

Hình 1.1: Kiến trúc điện toán biên

toán, CC có thể gặp hạn chế trong việc đáp ứng các yêu cầu tính toán khối lượng dữ liệu lớn với

độ trễ thấp, chi phí kết nối, khả năng hoạt động khi dịch vụ gián đoạn, quyền riêng tư và bảomật Để khắc phục những hạn chế này, EC đã xuất hiện như một mô hình phân tán, trong đó dữliệu được xử lý gần nguồn tạo ra, giảm thiểu độ trễ và tối ưu hóa băng thông EC đặc biệt hữuích cho các ứng dụng IoT yêu cầu phản hồi thời gian thực và xử lý dữ liệu cục bộ Ngoài ra, điệntoán sương mù (Fog Computing - FC) mở rộng khái niệm EC bằng cách thêm một hoặc nhiềulớp trung gian giữa thiết bị người dùng cuối và đám mây, cho phép xử lý và lưu trữ dữ liệu ởnhiều cấp độ trong mạng, tăng cường tính linh hoạt và khả năng mở rộng của hệ thống [26].Hai mô hình nổi bật trong điện toán biên là MEC và VEC

• MEC là một mô hình điện toán biên được phát triển bởi Viện tiêu chuẩn viễn thông châu

Âu (European Telecommunications Standards Institute - ETSI) [4], nhằm cung cấp cácdịch vụ tính toán và lưu trữ ngay tại biên của mạng truy cập MEC được triển khai tại cáctrạm cơ sở (base stations) hoặc các điểm truy cập trong các mạng viễn thông, giúp giảm

độ trễ và tối ưu hóa băng thông cho các ứng dụng yêu cầu thời gian thực, đặc biệt trongmôi trường di động như 5G và IoT

• VEC là một mô hình điện toán biên ứng dụng trong các hệ thống giao thông thông minh

và xe tự lái [8] Trong VEC, các phương tiện giao thông như ô tô đóng vai trò là các máychủ biên di động, cung cấp khả năng tính toán và xử lý dữ liệu ngay tại các thiết bị có thể

di động, giúp giảm độ trễ và tối ưu hóa hiệu suất cho các ứng dụng cần phản hồi nhanh

Điện toán biên đang ngày càng được ứng dụng vào nhiều lĩnh vực đời sống Một số ứng dụngphổ biến của điện toán biên như: lưới điện thông minh (Smart grids), nhà thông minh (Smart

home), hệ thống giao thông thông minh (Intelligent transport system), dịch vụ quản lý chăm sócsức khỏe (Healthcare management), nông nghiệp thông minh (Smart agriculture), dịch vụ giảitrí (Entertainment).

Điện toán biên có một số ưu điểm như sau [27]: độ trễ thấp và tương tác thời gian thực, tiếtkiệm băng thông, tính di động, phân tích dữ liệu phi tập trung, tính không đồng nhất, khả năngtương tác, bảo mật dữ liệu và bảo vệ quyền riêng tư, tiêu thụ năng lượng thấp

Điện toán biên là mô hình điện toán tiềm năng, có nhiều ứng dụng trong thực tế tuy nhiêntồn tại một số thách thức sau [27]: Quản lý kết nối các nút mạng trong điện toán biên, độ tin cậy

và sẵn sàng hoạt động, năng lượng, an ninh và chính sách riêng tư, điều phối tác vụ

Điện toán biên mang lại nhiều lợi ích nhưng cũng đặt ra một số thách thức mới, đặc biệt làtrong việc quản lý và điều phối các tác vụ Điều phối tác vụ hiệu quả giúp tối ưu hóa tài nguyên,cải thiện hiệu suất và đáp ứng yêu cầu độ trễ thấp của các ứng dụng Phần tiếp theo trình bày cụthể hơn về các đặc điểm của bài toán điều phối tác vụ trong điện toán biên

1.2 Điều phối tác vụ trong môi trường điện toán biên

Bài toán điều phối tác vụ (Task Offloading) trong điện toán biên là một dạng bài toán lậplịch trong tối ưu tổ hợp Mục tiêu của bài toán là đưa ra lịch cụ thể cho việc xử lý các tác vụđược gửi từ các thiết bị IoT, đồng thời đảm bảo đáp ứng các ràng buộc trong môi trường điệntoán biên [28] Tiếp theo, luận án trình bày các yếu tố trong bài toán điều phối tác vụ gồm: quyếtđịnh điều phối tác vụ, loại tác vụ, nút xử lý tác vụ, độ đo [29, 30]

a) Quyết định điều phối tác vụ

Quyết định điều phối tác vụ: là hành động xác định có nên thực hiện tác vụ tại thiết bị cuốihay gửi tác vụ đến máy chủ biên Quyết định điều phối tác vụ có thể là một trong các trườnghợp sau:

• Không điều phối tác vụ: thực hiện toàn bộ tác vụ tại thiết bị cuối

• Điều phối toàn bộ tác vụ: gửi toàn bộ tác vụ tới nút biên và xử lý tại đó

• Điều phối một phần tác vụ: tác vụ được chia thành hai hay nhiều phần, một phần được

xử lý bởi thiết bị cuối và các phần còn lại được gửi đến các nút biên

tính toán, X (CPU cycles/bit) là số chu kỳ xung nhịp CPU xử lý một bit dữ liệu và Td(giây) làthời hạn xử lý tác vụ [31] Như đã trình bày ở mục a), có hai loại điều phối tác vụ trong điệntoán biên là điều phối toàn phần và điều phối từng phần Với điều phối toàn phần, các tác vụtính toán không thể phân chia và được xử lý tại thiết bị người dùng cuối hoặc một nút biên duynhất Với điều phối từng phần, một tác vụ có thể chia thành nhiều phần, các phần này thực hiệntrên một hoặc nhiều nút tính toán Những tác vụ độc lập có thể được thực hiện song song, chiếnlược điều phối các tác vụ này chỉ xem xét việc phân bổ tài nguyên tính toán Các tác vụ phụthuộc vào nhau có thể được đưa vào hàng đợi và được lên kế hoạch để xử lý.

c) Nút xử lý tác vụ

Xác định nút xử lý tác vụ là đầu ra của quá trình điều phối tác vụ Nút xử lý tác vụ có thể làmáy chủ biên hoặc máy chủ đám mây Các máy chủ biên có thể được cố định hoặc di động tùyvào mục đích, khả năng của nhà cung cấp dịch vụ điện toán biên Mô hình điện toán biên cơbản bao gồm các EN cố định được cài đặt tại các vị trí cố định Các EN này thường được triểnkhai cạnh các trạm cơ sở, điểm truy cập hay những thiết bị truyền thông Tuy nhiên, nếu ngay

từ đầu triển khai quá nhiều EN cố định có thể gây lãng phí, hoặc trong trường hợp cần dựng hệthống ở vị trí hiểm trở thì số lượng EN cố định bị giới hạn Giải pháp cho các trường hợp này lànhà cung cấp dịch vụ có thể triển khai các EN di động, từ đó hình thành nên mô hình điện toánbiên trong giao thông [32] Các EN di động thường được cài đặt trên các phương tiện di độngnhư xe buýt, tàu hỏa, thiết bị bay không người lái, v.v Nhờ vào khả năng di động, các EN cóthể được triển khai linh hoạt đến các vị trí cụ thể để xử lý và lưu trữ dữ liệu

d) Độ đo

Quá trình điều phối tác vụ cần đảm bảo được những yêu cầu từ người dùng cuối và nhàcung cấp dịch vụ điện toán biên Các chỉ số để đánh giá những yêu cầu này gồm chất lượng trảinghiệm người dùng, năng lượng, chất lượng dịch vụ và chi phí vận hành

Trong những năm gần đây, đã có một số nghiên cứu khảo sát về bài toán điều phối tác

vụ [33–36] Bài toán điều phối tác vụ có thể được mô hình hóa dưới dạng bài toán quy hoạchphi tuyến tính (Non-Linear Programming - NLP) khi các hàm mục tiêu, các biến và ràng buộcđều không nhất thiết phải ở dạng hàm tuyến tính Bài toán NLP cũng có thể coi là một bàitoán khá phức tạp và không dễ giải trong thời gian đa thức [11, 37, 38] Những phương phápphổ biến để giải quyết bài toán NLP phức tạp là meta-heuristic, logic mờ, lý thuyết trò chơi vàhọc tăng cường [23] Sau đây là các nghiên cứu liên quan đến việc áp dụng các phương phápmeta-heuristic, logic mờ, học tăng cường trong môi trường điện toán biên

a) Phương pháp metaheuristics

Mặc dù các thuật toán metaheuristic có khả năng tìm ra lời giải tối ưu trong khoảng thời gianchấp nhận được và ứng dụng để giải các bài toán tối ưu trong điện toán biên [21,22,39–45] Tuy

nhiên, các phương pháp này vẫn gặp phải một số hạn chế khi triển khai trong môi trường điệntoán biên [23, 46] Đó là, các thuật toán này thường thiếu khả năng thích nghi nhanh chóng vớimôi trường động và phân tán của điện toán biên, nơi mà điều kiện tài nguyên và tác vụ liên tụcthay đổi Thêm vào đó, khi kích thước bài toán và số lượng tài nguyên, yêu cầu gia tăng, việcđánh giá trực tiếp các lời giải của thuật toán metaheuristic có thể trở nên khó khăn, làm giảmkhả năng ứng dụng trong các hệ thống yêu cầu độ trễ thấp.

b) Logic mờ

Các phương pháp ra quyết định điều phối tác vụ dựa trên logic mờ đã thu hút sự quan tâmcủa cộng đồng nghiên cứu và được ứng dụng để giải quyết bài toán trong môi trường điện toánbiên [47–50] Phần lớn các chiến lược dựa trên logic mờ tập trung vào các khía cạnh như phủ

mờ hóa (fuzzification), giải mờ hóa (defuzzification) và thiết kế quy tắc suy luận với một vàitham số hệ thống Việc thiết lập các quy tắc suy luận đòi hỏi kiến thức chuyên gia về bài toán.Quá trình này tốn nhiều thời gian và công sức, đặc biệt cho các bài toán phức tạp với nhiều tham

số Khó khăn trong việc điều chỉnh các quy tắc để thích ứng với các thay đổi trong môi trườnghoặc yêu cầu của hệ thống

c) Học tăng cường

Các thuật toán học tăng cường [13] là lựa chọn phù hợp để giải quyết bài toán điều phối tác

vụ trong điện toán biên [10, 51–61] do:

• Khả năng thích nghi

• Học từ kinh nghiệm

• Tối ưu hóa chính sách trong thời gian thực

Bên cạnh đó, các thuật toán học tăng cường cũng gặp phải một số thách thức:

• Cân đối giữa khám phá và khai thác

• Không gian trạng thái liên tục

1.3.2 Các thành phần của học tăng cường

Một bài toán học tăng cường chứa nhiều thành phần khác nhau như các trạng thái (states),các hành động (actions), các chuyển tiếp (transitions), các phần thưởng (rewards), các chínhsách (policies) và các giá trị (values)

Quá trình quyết định Markov (MDP) đã được nghiên cứu từ những năm 1950 và được sửdụng rộng rãi trong kinh tế học, lý thuyết điều khiển [62] MDP được định nghĩa là một bộ 5thành phần <S , A , P, R, γ > S là tập trạng thái của tác tử A là tập hành động của tác tử

và phần thưởng tức thời Rt = R(St, At) P là ma trận chuyển trạng thái Chính sách π là kýhiệu cho cách mà tác tử hành động dựa trên quan sát của tác tử về môi trường Đó là ánh xạ củamỗi trạng thái s ∈ S và hành động a ∈ A Giá trị kỳ vọng trả về (Expected Return - ER) là

kỳ vọng về phần thưởng trả về theo một chính sách Mục tiêu của việc học tăng cường là tìm ra

ER cao hơn bằng cách cải thiện chính sách

Trong MDP, hàm giá trị hành động dùng để xác định độ hiệu quả của hành động Hàm này

phụ thuộc vào cả trạng thái và hành động vừa được tác tử thực hiện Ký hiệu Qπ(s, a) là giá trịhành động theo chính sách π, được định nghĩa là:

Qπ(s, a) phụ thuộc vào π Nếu π thay đổi thì Qπ(s, a) tương ứng cũng sẽ thay đổi tương ứng

Trong học tăng cường, một “mô hình” (model) là một tập hợp các kiến thức về môi trường

mà tác tử thu được Có hai cách để tác tử đạt được quá trình học môi trường là: học dựa trên

mô hình và học không dựa trên mô hình

Học dựa trên mô hình (model-based): trong phương pháp này, tác tử cố gắng dự đoán các

yếu tố của môi trường bằng cách xây dựng mô hình của nó

Học không dựa trên mô hình (model-free): trong các phương pháp không dựa trên mô

hình, tác tử tương tác trực tiếp với môi trường và cải thiện hiệu suất của nó dựa trên các mẫu đãkhám phá Các thuật toán học không dựa trên mô hình được chia thành hai nhóm phương phápchính: dựa trên giá trị và dựa trên chính sách

• Phương pháp học dựa trên giá trị (value-based) tập trung vào việc ước tính hàm giá trị(value function), thể hiện giá trị của mỗi trạng thái hoặc cặp trạng thái-hành động

• Phương pháp học dựa trên chính sách (policy-based) tập trung vào việc học một chínhsách (policy), là một quy tắc xác định cách chọn hành động trong mỗi trạng thái