Luận án TS Trần Thị Hương: Tối ưu sạc cảm biến kéo dài thời gian sống WRSNs

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC BÁCH KHOA HÀ NỘI TRẦN THỊ HƯƠNG TỐI ƯU CHIẾN LƯỢC SẠC CHO CÁC CẢM BIẾN ĐỂ KÉO DÀI THỜI GIAN SỐNG CỦA MẠNG WRSNs LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH HÀ NỘI−2024 BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC BÁCH KHOA HÀ NỘI TRẦN THỊ HƯƠNG TỐI ƯU CHIẾN LƯỢC SẠC CHO CÁC CẢM BIẾN ĐỂ KÉO DÀI THỜI GIAN SỐNG CỦA MẠNG WRSNs Ngành: Khoa học máy tính Mã số: 9480101 LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH GIÁO VIÊN HƯỚNG DẪN KHOA HỌC: 1. HUỲNH THỊ THANH BÌNH 2. LÊ TRỌNG VĨNH HÀ NỘI−2024 LỜI CAM ĐOAN Tôi xin cam đoan các kết quả trình bày trong luận án là công trình nghiên cứu của bản thân nghiên cứu sinh trong thời gian học tập và nghiên cứu tại Đại học Bách khoa Hà Nội dưới sự hướng dẫn của tập thể hướng dẫn khoa học. Các số liệu, kết quả trình bày trong luận án là hoàn toàn trung thực.

Các kết quả sử dụng tham khảo đều đã được trích dẫn đầy đủ và theo đúng quy định. Hà Nội, ngày tháng năm 2024 Nghiên cứu sinh Trần Thị Hương GIÁO VIÊN HƯỚNG DẪN KHOA HỌC PGS. Huỳnh Thị Thanh Bình PGS. Lê Trọng Vĩnh i MỤC LỤC LỜI CAM ĐOAN.

ii DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT NGỮ. v DANH MỤC HÌNH VẼ. vi DANH MỤC BẢNG BIỂU. viii DANH MỤC KÝ HIỆU.

ix MỞ ĐẦU. Bài toán tối ưu. Các thuật toán tối ưu theo cách tiếp cận Meta-heuristic. Thuật toán di truyền.

Thuật toán tối ưu bầy đàn. Các thuật toán tối ưu theo cách tiếp cận học tăng cường. Học tăng cường. Thuật toán Q-learning.

Mạng cảm biến không dây. Mạng cảm biến có khả năng sạc không dây. Một số mô hình sạc năng lượng không dây. Mô hình sạc từng cảm cảm biến.

Mô hình sạc nhiều cảm biến đồng thời. Tối ưu chiến lược sạc trong mạng cảm biến sạc không dây. Hệ thống mạng và mô hình tiêu thụ năng lượng. Tối ưu chiến lược sạc trong mạng cảm biến sạc không dây.

Các nghiên cứu liên quan. Kết luận chương 1. 37 ii CHƯƠNG 2. TỐI ƯU CHIẾN LƯỢC SẠC CHO MÔ HÌNH SẠC TỪNG CẢM BIẾN.

Phát biểu bài toán. Mô hình bài toán. Thuật toán đề xuất. Thuật toán di truyền hai pha GACS.

Thuật toán sạc tối ưu hai mức BOEDA. Phân tích độ phức tạp của thuật toán. Kết quả thực nghiệm. Dữ liệu thực nghiệm.

Cài đặt thực nghiệm. Kết quả thực nghiệm. Xu hướng hội tụ. So sánh thời gian chạy.

Phân tích thống kê. Kết luận chương 2. TỐI ƯU CHIẾN LƯỢC SẠC CHO MÔ HÌNH SẠC NHIỀU CẢM BIẾN. Mô hình mạng.

Phát biểu bài toán. Mô hình bài toán. Đề xuất thuật toán tham lam xác định điểm sạc. Lược đồ sạc phân tán dựa trên giải thuật học tăng cường Q-learning cho nhiều thiết bị sạc.

Tổng quan thuật toán. Xác định thời gian sạc tối ưu. Thuật toán Q-learning xác định điểm sạc tối ưu. Đánh giá độ phức tạp thuật toán.

Thực nghiệm và đánh giá. Thiết lập mô phỏng. Đánh giá sự ảnh hưởng của các tham số. Đánh giá hiệu suất của thuật toán đề xuất.

Kết luận chương 3. 95 iii KẾT LUẬN. 96 DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ. 98 TÀI LIỆU THAM KHẢO.

100 iv DANH MỤC THUẬT NGỮ VÀ TỪ VIẾT TẮT STT Từ viết tắt Tên đầy đủ 1 BS Base Station 2 BOEDA Bi-level Optimized Algorithm For Energy Depletion Avoidance 3 DTCM Distributed charging scheme under Target coverage and Connectivity constraints for Multiple chargers 4 EDAP Energy Depletion Avoidance Problem 5 GA Genetic Algorithm 6 GACS Genetic Algorithm-based Charging Scheme 7 HPSOGA Hybrid the Particle Swarm Optimization and Genetic 8 INMA Invalid Node Minimized Algorithm 9 MC Mobile Charger 10 PSO Particle Swarm Optimization 11 PA Probability based Algorithm 12 TSP Travelling Salesman Problem 13 Q-learning Q-learning Algorithm 14 RL Reinforcement Learning 15 WSNs Wireless Sensor Networks 16 WRSNs Wireless Rechargeable Sensor Networks v DANH MỤC HÌNH VẼ 1.1 Tổng quan về học tăng cường.2 Mạng cảm biến không dây.3 Một số ứng dụng của mạng cảm biến không dây.4 Minh họa một mạng cảm biến sạc không dây.5 Kỹ thuật truyền năng lượng không dây dựa trên phát xạ điện từ .6 Kỹ thuật truyền năng lượng không dây dựa trên cộng hưởng từ.7 Minh họa mô hình sạc nhiều cảm biến đồng thời trong mạng WRSNs.8 Phân loại chiến lược sạc dựa vào các đặc trưng của mạng.1 Minh họa lai ghép một điểm cắt.2 Minh họa lai ghép PMX.3 Minh họa toán tử đột biến CIM.4 Minh họa toán tử đột biến đổi chỗ .5 Thực hiện lai ghép cá thể.6 Ví dụ phép đột biến trong pha xác định thời gian sạc.7 Một ví dụ về giải mã một lời giải của thuật toán BOEDA .8 Hiệu suất của BOEDA trên các phương thức khởi tạo khác nhau và tham số α .9 Hành trình sạc được xác định bởi thuật toán BOEDA trên bộ dữ liệu g_25_01 .10 Số lượng cảm biến ảnh hưởng đến tỉ lệ nút chết theo ba cách triển khai g, n, u .11 Ảnh hưởng của năng lượng tiêu thụ trung bình của cảm biến tới tỉ lệ nút chết ứng với ba phương pháp triển khai g, n, u.12 Tốc độ sạc của MC ảnh hưởng đến tỉ lệ nút chết theo ba phương pháp triển khai g, n, u.13 Dung lượng của MC ảnh hưởng đến tỉ lệ nút chết theo ba phương pháp triển khai g, n, u.14 Tốc độ sạc và dung lượng của MC ảnh hưởng đến tỉ lệ nút chết theo ba phương pháp triển khai g, n, u.15 Xu hướng hội tụ của thuật toán BOEDA .1 Minh họa mạng cảm biến sạc không dây giám sát các mục tiêu quan trọng đảm bảo kết nối.2 Tổng quan thuật toán đề xuất .3 Minh họa bảng giá trị Q .4 Sự ảnh hưởng của số lượng mục tiêu tới thời gian sống của mạng .5 Sự ảnh hưởng của số lượng cảm biến tới thời gian sống của mạng. 94 vii DANH MỤC BẢNG 1.1 Các tham số trong mô hình tiêu thụ của cảm biến .1 Các thông số của cảm biến và MC.2 Các thông số cho thuật toán BOEDA.3 Trung bình tỷ lệ nút chết khi thay đổi số lượng cảm biến theo ba cách triển khai mạng.4 So sánh thời gian chạy giữa các thuật toán (giây) .5 Xếp hạng trung bình của các thuật toán.6 z-values và p-values của phép thử Friedman .7 z-values và p-values của phép thử Quade .8 Các p-values được điều chỉnh cho kiểm định Friedman .9 Các p-values được điều chỉnh cho kiểm định Quade .1 Các thông số của mô hình mạng.2 Tác động của α tới thời gian sống của mạng.3 Tác động của γ tới thời gian sống của mạng. 91 viii DANH MỤC KÝ HIỆU Ký hiệu Ý nghĩa S Tập hợp các cảm biến trong mạng si Cảm biến thứ i trong tập S , i = 1, n s0 Trạm cơ sở emax Dung lượng pin tối đa của cảm biến emin Dung lượng pin tối thiểu của cảm biến einit i Năng lượng còn lại của cảm biến si ở thời điểm bắt đầu của chu kỳ sạc đang xét edepot i Năng lượng còn lại của cảm biến si tại thời điểm kết thúc chu kỳ sạc đang xét eremain i Năng lượng còn lại của cảm biến si khi MC đến si dih Khoảng cách Euclid giữa hai cảm biến si và sh ℘ Hành trình sạc của MC đi qua tất cả các cảm biến {π1 , π2 , ., πn } Hoán vị của tập gồm n cảm biến {s1 , s2 , ., sn } π0 , πn+1 Trạm cơ sở (điểm xuất phát và kết thúc của ℘) EM C Dung lượng pin tối đa của MC min EM Dung lượng pin tối thiểu để MC hoạt động C Emove Tổng năng lượng MC tiêu hao cho việc di chuyển Echarge Tổng năng lượng MC tiêu hao để sạc cho cảm biến PM Năng lượng tiêu thụ trong 1 giây khi MC di chuyển U Tốc độ sạc của MC trong một giây V Vận tốc di chuyển của MC CT Khoảng thời gian tối đa của một chu kỳ t = {τ1 , ., τn } Chuỗi thời gian sạc tại n cảm biến τ Tổng thời gian sạc tại tất cả cảm biến zi Biến nhị phân biểu diễn trạng thái của si ∆i Mức giảm năng lượng của cảm biến si tại hai thời điểm: bắt đầu và kết thúc chu kỳ sạc Dv Điểm dừng sạc thứ v Tv Thời gian sạc tại điểm sạc Dv ix MỞ ĐẦU Từ sau đại dịch COVID-19, con người chứng kiến sự bùng nổ mạnh mẽ của mạng Internet, các mạng kết nối vạn vật (Internet of Things - IoTs) cùng sự tiến bộ trong công nghệ vi xử lý giúp quá trình thu thập, xử lý dữ liệu trở nên thông minh hơn. Đặc biệt, mạng cảm biến không dây (Wireless Sensor Networks - WSNs) được xem là kiến trúc cốt lõi trong phát triển hệ thống IoTs nhờ một loạt các ứng dụng và lợi ích từ dân sự như cảnh báo cháy rừng, giám sát giao thông thông minh, tới các ứng dụng trong quân sự như theo dõi các mục tiêu, phát hiện đối tượng xâm nhập mạng, v.

Mạng WSNs là mạng kết nối các nút cảm biến (sensor nodes) nhờ các liên kết không dây như sóng vô tuyến hoặc sóng hồng ngoại. Các cảm biến được triển khai trong một phạm vi rộng lớn thường gọi là khu vực mục tiêu để thực hiện các nhiệm vụ cảm nhận và thu thập dữ liệu từ môi trường vật lý xung quanh. Dữ liệu sau khi thu thập sẽ được định tuyến tới trạm cơ sở (Base Station - BS ), từ đó người dùng cuối (users) có thể thông qua mạng Internet để đưa ra các bước xử lý, phân tích tiếp theo. Một trong những đặc trưng riêng biệt của mạng WSNs là các cảm biến bị hạn chế năng lượng hoạt động do các nút mạng sử dụng pin là nguồn cung cấp năng lượng chính [4, 5].

Khi pin của cảm biến cạn kiệt thì cảm biến sẽ mất chức năng hoạt động và trở thành nút mạng chết. Hệ quả là, một hoặc nhiều vùng quan trọng trong mạng không được theo dõi, giám sát hoặc mất kết nối. Trong nhiều ứng dụng đòi hỏi sự hợp tác và truyền thông giữa tất cả các nút trong mạng thì việc một cảm biến bị chết có thể làm gián đoạn hàng loạt các đường truyền dữ liệu về BS, gây ảnh hưởng nghiêm trọng tới hoạt động của mạng. Có thể thấy, năng lượng của cảm biến có vai trò quan trọng, quyết định tới thời gian sống của mạng.

Khi đó, kéo dài thời gian sống của mạng đã trở thành một thách thức lớn khi triển khai mạng WSN vào các ứng dụng thực tế.