Luận án Tiến sĩ Khoa học máy tính: 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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:121

Thêm vào BST

Báo xấu

17
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận án "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" tập trung giải quyết vấn đề kéo dài thời gian sống của mạng WRSNs theo cách tiếp cận tối ưu chiến lược sạc cho các cảm biến. Trong đó, luận án sẽ quan tâm tới vấn đề tối ưu chiến lược sạc cho hai loại mô hình sạc: mô hình sạc từng cảm biến và mô hình sạc nhiều cảm biến đồng thời. Hai mô hình sạc này tương ứng với hai công nghệ truyền năng lượng không dây ở khoảng cách gần và khoảng cách xa phụ thuộc vào đặc điểm kiến trúc mạng, quy mô triển khai cũng như số lượng cảm biến trong mạng WRSNs.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ Khoa học máy tính: 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

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. PGS.TS. HUỲNH THỊ THANH BÌNH 2. PGS.TS. 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.TS. Huỳnh Thị Thanh Bình PGS.TS. Lê Trọng Vĩnh i
MỤC LỤC LỜI CAM ĐOAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i MỤC LỤC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 CHƯƠNG 1. CƠ SỞ LÝ THUYẾT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1. Bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2. Các thuật toán tối ưu theo cách tiếp cận Meta-heuristic. . . . . . . . . . . . 10 1.2.1. Thuật toán di truyền . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.2. Thuật toán tối ưu bầy đàn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3. Các thuật toán tối ưu theo cách tiếp cận học tăng cường . . . . . . . . . . . 15 1.3.1. Học tăng cường . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.3.2. Thuật toán Q-learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.4. Mạng cảm biến không dây . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.5. Mạng cảm biến có khả năng sạc không dây . . . . . . . . . . . . . . . . . . . . . . . . 27 1.6. Một số mô hình sạc năng lượng không dây . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.6.1. Mô hình sạc từng cảm cảm biến . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.6.2. Mô hình sạc nhiều cảm biến đồng thời . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.7. Tối ưu chiến lược sạc trong mạng cảm biến sạc không dây . . . . . . . . . 30 1.7.1. Hệ thống mạng và mô hình tiêu thụ năng lượng . . . . . . . . . . . . . . . . 30 1.7.2. Tối ưu chiến lược sạc trong mạng cảm biến sạc không dây. . . . . . 32 1.8. Các nghiên cứu liên quan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.9. 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.1. Phát biểu bài toán. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.2. Mô hình bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.3. Thuật toán đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.3.1. Thuật toán di truyền hai pha GACS . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.3.2. Thuật toán sạc tối ưu hai mức BOEDA . . . . . . . . . . . . . . . . . . . . . . . . 49 2.3.3. Phân tích độ phức tạp của thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.4. Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.4.1. Dữ liệu thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.4.2. Cài đặt thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 2.4.3. Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 2.4.4. Xu hướng hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 2.4.5. So sánh thời gian chạy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 2.4.6. Phân tích thống kê . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 2.5. Kết luận chương 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 CHƯƠNG 3. TỐI ƯU CHIẾN LƯỢC SẠC CHO MÔ HÌNH SẠC NHIỀU CẢM BIẾN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.1. Mô hình mạng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 3.2. Phát biểu bài toán. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.2.1. Mô hình bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.3. Đề xuất thuật toán tham lam xác định điểm sạc . . . . . . . . . . . . . . . . . . . 78 3.4. 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 3.4.1. Tổng quan thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 3.4.2. Xác định thời gian sạc tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.4.3. Thuật toán Q-learning xác định điểm sạc tối ưu. . . . . . . . . . . . . . . . 85 3.4.4. Đánh giá độ phức tạp thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 3.5. Thực nghiệm và đánh giá . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 3.5.1. Thiết lập mô phỏng. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 3.5.2. Đánh giá sự ảnh hưởng của các tham số . . . . . . . . . . . . . . . . . . . . . . . 90 3.5.3. Đánh giá hiệu suất của thuật toán đề xuất . . . . . . . . . . . . . . . . . . . . . 92 3.6. 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. . . . . . . . . . . . . . . . . . . . . . . . 17 1.2 Mạng cảm biến không dây. . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.3 Một số ứng dụng của mạng cảm biến không dây. . . . . . . . . . . . . 25 1.4 Minh họa một mạng cảm biến sạc không dây. . . . . . . . . . . . . . . 27 1.5 Kỹ thuật truyền năng lượng không dây dựa trên phát xạ điện từ . . . 28 1.6 Kỹ thuật truyền năng lượng không dây dựa trên cộng hưởng từ. . . . 28 1.7 Minh họa mô hình sạc nhiều cảm biến đồng thời trong mạng WRSNs.30 1.8 Phân loại chiến lược sạc dựa vào các đặc trưng của mạng. . . . . . . 33 2.1 Minh họa lai ghép một điểm cắt. . . . . . . . . . . . . . . . . . . . . . 45 2.2 Minh họa lai ghép PMX. . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.3 Minh họa toán tử đột biến CIM. . . . . . . . . . . . . . . . . . . . . . 46 2.4 Minh họa toán tử đột biến đổi chỗ . . . . . . . . . . . . . . . . . . . . 46 2.5 Thực hiện lai ghép cá thể. . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.6 Ví dụ phép đột biến trong pha xác định thời gian sạc. . . . . . . . . . 49 2.7 Một ví dụ về giải mã một lời giải của thuật toán BOEDA . . . . . . . 53 2.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ố α . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 2.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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 2.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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 2.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. . . . . . . . 65 2.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. . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 2.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. . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 2.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. . . . . . . . . . . . . . . . . . 69 2.15 Xu hướng hội tụ của thuật toán BOEDA . . . . . . . . . . . . . . . . 69 vi
3.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. . . . . . . . . . . . . . . . . . . . . . . . . 74 3.2 Tổng quan thuật toán đề xuất . . . . . . . . . . . . . . . . . . . . . . . 80 3.3 Minh họa bảng giá trị Q . . . . . . . . . . . . . . . . . . . . . . . . . . 85 3.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 . . 93 3.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 . . . . . . . . . . . 31 2.1 Các thông số của cảm biến và MC. . . . . . . . . . . . . . . . . . . . . 60 2.2 Các thông số cho thuật toán BOEDA. . . . . . . . . . . . . . . . . . . 61 2.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. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 2.4 So sánh thời gian chạy giữa các thuật toán (giây) . . . . . . . . . . . 70 2.5 Xếp hạng trung bình của các thuật toán. . . . . . . . . . . . . . . . . 70 2.6 z-values và p-values của phép thử Friedman . . . . . . . . . . . . . . . 71 2.7 z-values và p-values của phép thử Quade . . . . . . . . . . . . . . . . . 71 2.8 Các p-values được điều chỉnh cho kiểm định Friedman . . . . . . . . . 71 2.9 Các p-values được điều chỉnh cho kiểm định Quade . . . . . . . . . . 72 3.1 Các thông số của mô hình mạng. . . . . . . . . . . . . . . . . . . . . . 90 3.2 Tác động của α tới thời gian sống của mạng. . . . . . . . . . . . . . . 90 3.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 C Dung lượng pin tối thiểu để MC hoạt động 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.v [1, 2, 3]. 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ế. Rất nhiều giải pháp được đưa ra nhằm mục đích tối đa thời gian sống của mạng, trong đó, các giải pháp truyền thống chủ yếu tập trung vào cách tiếp cận giảm thiểu năng lượng tiêu thụ của cảm biến như tối ưu vị trí đặt cảm biến [6, 7], lập lịch bật/tắt thời gian hoạt động của cảm biến [8], sử dụng các nút chuyển tiếp dữ liệu [9], thu thập dữ liệu di động [4, 10]. Mặc dù, các giải pháp trên có thể giúp kéo dài thời gian sống của mạng thêm một khoảng thời gian 1
nhất định nhưng theo thời gian, năng lượng của các cảm biến vẫn dần tiêu hao do liên tục thực hiện các nhiệm vụ giám sát/kết nối, cuối cùng cạn kiệt và trở thành nút mạng chết. Những năm gần đây, sự đột phá trong công nghệ truyền năng lượng không dây đã mang đến một giải pháp tiềm năng cho phép cung cấp năng lượng cho các nút cảm biến trong mạng. Từ đây, một thế hệ mạng cảm biến mới ra đời được gọi là mạng cảm biến có khả năng sạc không dây (Wireless Rechargeable Sensor Networks - WRSNs), hoặc gọi tắt là mạng cảm biến sạc không dây [11]. Khác với mạng WSNs truyền thống, mạng WRSNs sử dụng thêm một hoặc một số thiết bị sạc di động (Mobile Chargers - MCs), trong đó MC có thể là rô-bốt di động hoặc xe tự vận hành được trang bị bộ sạc không dây để cung cấp năng lượng cho mạng. Bên cạnh đó, các cảm biến trong mạng WRSNs cũng được trang bị thêm một bộ phận nhận năng lượng không dây. Các MC có nhiệm vụ di chuyển xung quanh mạng để sạc lại năng lượng cho các cảm biến [12, 13] theo một trong hai mô hình sạc - mô hình sạc từng cảm biến và mô hình sạc nhiều cảm biến đồng thời. Trong mô hình sạc thứ nhất, MC sẽ dừng tại vị trí của từng cảm biến để sạc. Ngược lại, trong mô hình sạc thứ hai, MC sẽ di chuyển tới một số vị trí sạc nhất định để truyền năng cho nhiều cảm biến cùng lúc. Trong mạng WRSNs, chiến lược sạc của MC đóng vai trò quyết định tới thời gian sống của cảm biến do MC cần phải nạp lại năng lượng cho các cảm biến trước khi chúng cạn kiệt năng lượng. Vì vậy, luận án này sẽ tập trung vào vấn đề kéo dài thời gian sống của mạng WRSNs theo cách tiếp cận tối ưu chiến lược sạc của MC. Một chiến lược sạc hiệu quả cần xem xét tối ưu hai thành phần: hành trình sạc và thời gian sạc. Trong đó, hành trình sạc là một chuỗi vị trí các điểm sạc được sắp xếp theo thứ tự dừng sạc của MC, thời gian sạc là khoảng thời gian mà MC sẽ sạc tại mỗi điểm sạc. Điểm sạc có thể là vị trí của cảm biến hoặc một vị trí xác định trong mạng [14, 15]. Tối ưu chiến lược sạc được chứng minh là bài toán NP-khó, liên quan với cả yếu tố về không gian (hành trình sạc) và thời gian (thời gian sạc) [16, 17, 18]. Tuy nhiên, để giảm bớt độ phức tạp của bài toán, các nghiên cứu trước đây chủ yếu tập trung vào tối ưu hành trình sạc với các giả thiết về năng lượng của MC là vô hạn hoặc cực lớn [17, 19, 20, 21]. Họ thường sử dụng phương pháp sạc đầy, trong đó mỗi cảm biến luôn được sạc tới tối đa dung lượng pin [17, 19, 20, 21, 22, 23] hoặc một mức năng lượng cố định [24]. Nhận thấy, thời gian sạc cũng là yếu tố quan trọng quyết định tới thời gian sống của cảm biến. Nếu thời gian sạc quá dài có thể khiến những cảm biến chưa được sạc phải chờ một khoảng thời gian dài dẫn tới việc cạn kiệt năng lượng trước khi được sạc. Ngược lại, nếu thời gian sạc quá ngắn thì các cảm biến được 2
sạc không nhận được đủ năng lượng để duy trì hoạt động tới lần sạc tiếp theo. Vì vậy, luận án này tập trung nghiên cứu tối ưu chiến lược sạc của MC cho hai mô hình sạc mà xem xét tối ưu cả hành trình sạc và thời gian sạc dưới ràng buộc năng lượng hữu hạn của MC để tối đa thời gian sống của mạng WRSNs. Có hai cách tiếp cận để giải bài toán tối ưu chiến lược sạc: giải chính xác và giải gần đúng. Cách tiếp cận thứ nhất đảm bảo tìm ra lời giải chính xác của bài toán. Tuy nhiên, đối với bài toán có kích thước dữ liệu lớn thì cách tiếp cận này không khả thi do đòi hỏi chi phí và thời gian tính toán rất lớn. Đối với cách tiếp cận thứ hai, mặc dù chỉ tìm được các lời giải gần đúng, nhưng thời gian thực hiện thuật toán là chấp nhận được cho mọi bộ dữ liệu. Đây cũng là hướng tiếp cận chính của luận án. Các thuật toán tối ưu đề xuất sẽ được cài đặt, thực nghiệm trên đa dạng các kịch bản mạng mô phỏng, từ đó đưa ra những phân tích và đánh giá so sánh với các nghiên cứu liên quan. Mục tiêu của luận án Luận án tập trung giải quyết vấn đề kéo dài thời gian sống của mạng WRSNs theo cách tiếp cận tối ưu chiến lược sạc cho các cảm biến. Trong đó, luận án sẽ quan tâm tới vấn đề tối ưu chiến lược sạc cho hai loại mô hình sạc: mô hình sạc từng cảm biến và mô hình sạc nhiều cảm biến đồng thời. Hai mô hình sạc này tương ứng với hai công nghệ truyền năng lượng không dây ở khoảng cách gần và khoảng cách xa phụ thuộc vào đặc điểm kiến trúc mạng, quy mô triển khai cũng như số lượng cảm biến trong mạng WRSNs. Mục tiêu cụ thể của luận án bao gồm: • Nghiên cứu về vấn đề tối đa thời gian sống của mạng theo cách tiếp cận tối ưu chiến lược sạc trong mạng cảm biến sạc không dây cho hai mô hình sạc phổ biến: mô hình sạc từng cảm biến và mô hình sạc nhiều cảm biến đồng thời. • Nghiên cứu lớp các thuật toán gần đúng như các thuật toán heuristic và các thuật toán meta-heuristic để giải quyết bài toán nghiên cứu. • Nghiên cứu và ứng dụng các thuật toán học tăng cường để giải quyết bài toán nghiên cứu. Phạm vi nghiên cứu Theo [14, 25, 26], có nhiều định nghĩa khác nhau để tính thời gian sống của mạng, trong đó có hai định nghĩa được sử dụng phổ biến nhất là định nghĩa thời 3
gian sống của mạng dựa vào số lượng cảm biến chết (hoặc số lượng cảm biến còn sống) và thời gian sống được tính dựa vào vai trò của cảm biến trong nhiệm vụ giám sát, kết nối mạng. • Thời gian sống của mạng được tính dựa vào số lượng nút cảm biến chết trong mạng: xét một mạng bao gồm n nút cảm biến được triển khai trong một khu vực mục tiêu. Thời gian sống của mạng được tính từ thời điểm mạng triển khai cho tới khi có k nút trong mạng hết năng lượng (nút chết). • Thời gian sống của mạng được tính dựa vào vai trò của cảm biến trong nhiệm vụ giám sát, kết nối mạng: thời gian sống của mạng là khoảng thời gian từ khi mạng triển khai cho tới khi có ít nhất một mục tiêu không được giám sát (bao phủ) bởi bất kỳ một cảm biến nào hoặc không tồn tại đường truyền dữ liệu nào từ ít nhất một mục tiêu tới BS. Cách định nghĩa này được áp dụng cho các mạng cảm biến có nhiệm vụ giám sát các điểm mục tiêu và đảm bảo đường truyền dữ liệu từ các điểm mục tiêu tới BS (gọi là kết nối). Với định nghĩa thứ nhất, để kéo dài thời gian sống của mạng, các nghiên cứu thường tập trung vào việc tối thiểu số lượng nút cảm biến chết. Trong khi đó, với định nghĩa thứ hai, các nghiên cứu sẽ tập trung vào việc tối đa thời gian sống của cảm biến đầu tiên chết nhằm kéo dài thời gian sống của toàn mạng. Luận án này sẽ tập trung tối ưu chiến lược sạc để kéo dài thời gian sống của mạng WRSNs theo các định nghĩa trên cho hai mô hình sạc: mô hình sạc từng cảm biến và mô hình sạc nhiều cảm biến đồng thời. Cụ thể phạm vi nghiên cứu của luận án như sau: Trong mô hình sạc từng cảm biến, luận án giải quyết vấn đề tối đa thời gian sống của mạng bằng cách giải quyết bài toán tối ưu chiến lược sạc của MC nhằm tối thiểu sự cạn kiệt năng lượng của cảm biến. Đây là một mục tiêu có ý nghĩa quan trọng, trực tiếp tối đa thời gian sống của mạng theo định nghĩa thứ nhất được nêu ở trên. Tuy nhiên, rất ít các nghiên cứu trước đây trực tiếp quan tâm tối ưu mục tiêu này, thay vì đó họ thường xem xét tới các mục tiêu gián tiếp như tối thiểu chi phí di chuyển, chi phí sạc, độ trễ sạc, cực đại thời gian nghỉ ở trạm sạc [17, 20, 27, 28, 29, 30, 31, 32, 33]. Hơn nữa, họ thường chỉ tập trung vào tối ưu hành trình sạc của MC bằng cách xác định thứ tự sạc các nút cảm biến trong mạng. Yếu tố thời gian sạc thường được xem là không ảnh hưởng hoặc có thể xác định khi áp dụng phương pháp sạc đầy, trong đó cảm biến luôn luôn được sạc tối đa mức năng lượng của pin khi thiết bị sạc dừng 4
tại nút mạng đó. Phương pháp sạc này chỉ phù hợp với các mạng kích thước nhỏ với số lượng cảm biến ít đáng kể. Do đặc điểm của sạc không dây nên quá trình để sạc đầy pin cho một cảm biến có thể phải mất tới hàng giờ, từ đó kéo dài thời gian chờ sạc của các cảm biến chưa được sạc khác. Hệ quả là hàng loạt cảm biến sẽ cạn kiệt năng lượng và trở thành nút mạng chết. Nhận thấy, để xây dựng được một chiến lược sạc hiệu quả khi MC chỉ có năng lượng hữu hạn và phải tối thiểu sự cạn kiệt năng lượng của các cảm biến, luận án cần xem xét tối ưu cả hành trình và thời gian sạc của MC. Trong mô hình sạc nhiều cảm biến đồng thời, luận án kéo dài thời gian sống của mạng theo định nghĩa thứ hai bằng cách xem xét bài toán tối đa thời gian giám sát các điểm mục tiêu trong mạng WRSNs, đảm bảo đường kết nối dữ liệu từ các mục tiêu tới BS. Bài toán này có ý nghĩa thực tiễn trong rất nhiều ứng dụng, khi các điểm mục tiêu (có thể là điểm quan trắc trong ứng dụng giám sát môi trường hay kho vũ khí hóa học trong quân sự) cần giám sát liên tục. Đặc biệt, các dữ liệu giám sát cần định kỳ chuyển về BS để theo dõi, quản lý. Có thể thấy, những cảm biến chịu trách nhiệm giám sát các mục tiêu và tham gia vào các đường truyền dữ liệu tới BS đóng vai trò đặc biệt quan trọng tới hoạt động của toàn mạng. Việc dừng hoạt động của chỉ một cảm biến tham gia các nhiệm vụ trên có thể khiến cho toàn mạng bị mất chức năng giám sát và được coi là mạng chết. Các nghiên cứu hiện tại đều không xem xét tới vai trò của các cảm biến trong các nhiệm vụ trên [34, 35, 36, 37, 38, 39]. Một điểm đáng chú ý khác, luận án sẽ quan tâm tối ưu chiến lược sạc cho mô hình sạc nhiều cảm biến đồng thời. Khác với mô hình sạc từng cảm biến, MC chỉ có thể sạc ở khoảng cách gần, mô hình sạc nhiều cảm biến đồng thời cho phép MC có thể truyền năng lượng cho một số cảm biến trong một diện tích nhất định. Khi đó, mô hình sạc nhiều cảm biến thường được sử dụng cho các mạng có diện tích lớn với số lượng cảm biến lên tới hàng trăm hàng nghìn nút mạng. Tuy nhiên, việc đi sạc thường xuyên (định kỳ) và đáp ứng nhu cầu năng lượng cho một số lượng lớn các cảm biến khi chỉ sử dụng một thiết bị sạc là không khả thi. Hơn nữa, các nghiên cứu trước thường cố định trước các điểm dừng sạc và chủ yếu tập trung vào tối ưu hành trình sạc cho một thiết bị sạc với các giả thiết năng lượng của thiết bị sạc là rất lớn hoặc vô hạn [2, 40, 41, 42, 43, 44, 45]. Trong mô hình sạc nhiều cảm biến đồng thời, vị trí và số lượng điểm dừng sạc của MC quyết định tới năng lượng nhận sạc của cảm biến và hiệu suất sạc của toàn mạng. Có thể thấy, một vị trí sạc càng xa cảm biến thì năng lượng nhận sạc của cảm biến càng nhỏ và ngược lại. Bên cạnh đó, nếu có quá nhiều điểm dừng sạc thì MC sẽ tiêu hao một lượng lớn năng lượng cho quá trình di chuyển giữa các điểm sạc. 5
Để giải quyết các vấn đề trên, luận án sẽ nghiên cứu và xây dựng chiến lược sạc dựa vào yêu cầu sạc của cảm biến theo thời gian thực cho nhiều MC, trong đó xem xét các vấn đề tối ưu cả vị trí sạc, thời gian sạc và hành trình di chuyển của các MC. Các đóng góp của luận án Đóng góp chính của luận án là giải quyết hai bài toán tương ứng với hai chương chính như sau: Bài toán 1: tối ưu chiến lược sạc cho mô hình sạc từng cảm biến nhằm tối thiểu số lượng cảm biến bị cạn kiệt năng lượng. Khác với các cách tiếp cận trước đây, luận án sẽ tối ưu cả hai yếu tố hành trình sạc và thời gian sạc với ràng buộc về năng lượng của MC nhằm tối thiểu sự cạn kiệt năng lượng của cảm biến sau mỗi vòng sạc. Luận án đề xuất các thuật toán sạc theo cách tiếp cận giải gần đúng do bài toán nghiên cứu thuộc lớp bài toán NP-khó. Cụ thể: • Đề xuất cách tiếp cận tối ưu lần lượt hành trình sạc và thời gian sạc: chia bài toán ban đầu thành hai bài toán con dễ giải hơn và đề xuất một cách tiếp cận giải hai pha dựa vào giải thuật di truyền, được đặt tên là GACS. Trong đó, pha thứ nhất sẽ tìm ra hành trình sạc tốt nhất ưu tiên sạc trước cho các cảm biến có thời gian sống ngắn. Pha thứ hai của thuật toán sẽ tối ưu thời gian sạc theo hành trình đã được xác định ở pha thứ nhất. • Đề xuất cách tiếp cận tối ưu đồng thời hành trình sạc và thời gian sạc: theo cách tiếp cận đầu tiên, hành trình sạc tốt nhất ở pha một sẽ quyết định tới chất lượng lời giải của cả bài toán. Nếu hành trình tìm được ở pha thứ nhất chưa tối ưu thì sẽ ảnh hưởng tới thời gian sạc ở pha thứ hai. Vì vậy, luận án đưa ra đề xuất thứ hai dựa vào một cách tiếp cận lồng nhau cho phép tối ưu đồng thời cả hành trình sạc và thời gian sạc. Luận án đề xuất thuật toán BOEDA dựa trên sự kết hợp giữa thuật toán di truyền, phương pháp tham lam và thuật toán tối ưu hóa bầy đàn (PSO). Bài toán 2: tối ưu chiến lược sạc cho mô hình sạc nhiều cảm biến đồng thời nhằm tối đa thời gian giám sát mục tiêu đảm bảo kết nối trong mạng WRSNs. Đóng góp của luận án là đề xuất chiến lược sạc theo yêu cầu dựa vào việc kết hợp các giải thuật heuristic và thuật toán học tăng cường dựa vào giá trị. cụ thể như sau: • Đề xuất thuật toán tham lam để xác định vị trí điểm dừng sạc tối ưu cho các MC. 6
• Đề xuất thuật toán DTCM dựa vào sự kết hợp giữa thuật toán heuristic và thuật toán Q-learning để xác định ra vị trí sạc tiếp theo trong hành trình sạc của MC và thời gian sạc tại mỗi điểm dừng sạc. 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ương chính như sau: Chương 1: cơ sở lý thuyết. Chương này trình bày cơ sở lý thuyết của bài toán tối ưu, một số hướng tiếp cận giải bài toán tối ưu và trình bày chi tiết các thuật toán tối ưu theo hướng tiếp cận heuristic/meta-heuristic và các thuật toán học tăng cường. Ngoài ra, chương này cũng trình bày các kiến thức nền tảng về mạng cảm biến, mạng cảm biến sạc không dây, một số mô hình sạc không dây và bài toán tối ưu chiến lược sạc của các thiết bị sạc di động. Chương 2: tối ưu chiến lược sạc cho mô hình sạc từng cảm biến. Trong chương này, luận án nghiên cứu bài toán tối ưu chiến lược sạc từng cảm biến nhằm tối thiểu số lượng cảm biến bị cạn kiệt năng lượng sau mỗi chu kỳ sạc. Luận án đề xuất các thuật toán tối ưu theo hướng tiếp cận heuristic/meta- heuristic để giải quyết bài toán. So sánh các thuật toán sạc đề xuất với các nghiên cứu trước đó để chứng tỏ sự hiệu quả của đề xuất trên các độ đo về giá trị hàm mục tiêu, thời gian thực hiện, độ phức tạp tính toán. Chương 3: tối ưu chiến lược sạc cho mô hình sạc nhiều cảm biến. Trong chương này, luận án nghiên cứu bài toán tối ưu chiến lược sạc nhiều cảm biến đồng thời với nhiều thiết bị sạc nhằm tối đa thời gian giám sát các điểm mục tiêu và đảm bảo tính kết nối trong mạng WRSNs. Do số lượng cảm biến trong mạng rất lớn, nên một chiến lược sạc theo yêu cầu dựa vào sự kết hợp giữa các thuật toán heuristic và thuật toán học tăng cường được đề xuất. Các thực nghiệm lựa chọn tham số tối ưu cho thuật toán đề xuất, cũng như thực hiện các so sánh, phân tích với các nghiên cứu liên quan được trình bày chi tiết trong chương này. 7
Chương 1 CƠ SỞ LÝ THUYẾT Chương này sẽ trình bày các kiến thức cơ bản về bài toán tối ưu và một số cách tiếp cận giải quyết bài toán tối ưu, trong đó đi sâu vào hai hướng tiếp cận bao gồm hướng tiếp cận heuristic/meta-heuristic và hướng tiếp cận học tăng cường. Ngoài ra, chương này cũng trình bày về mạng cảm biến không dây, mạng cảm biến sạc không dây, vấn đề tối ưu chiến lược sạc trong các mạng cảm biến sạc không dây. 1.1. Bài toán tối ưu Trong rất nhiều tình huống thực tế, con người luôn phải tìm ra những giải pháp tốt nhất, hiệu quả nhất, tốn chi phí hoặc tiêu hao tài nguyên ít nhất. Việc lựa chọn trong một loạt các giải pháp khả thi để tìm giải pháp tốt nhất cho một mục đích nào đó được gọi là tối ưu. Để máy tính có thể giải quyết các vấn đề thực tế đó thì trước tiên phải mô hình các bài toán về dạng toán học [46]. Trong khoa học máy tính, các bài toán tìm giá trị của các biến để tìm giá trị lớn nhất (cực đại) hoặc nhỏ nhất (cực tiểu) cho mục tiêu cụ thể nào đó của bài toán được gọi là “bài toán tối ưu”. Bài toán tối ưu thường được phân loại thành hai lớp dựa vào miền giá trị của các biến là liên tục hay rời rạc: • Tối ưu hóa liên tục, trong đó miền giá trị của các biến là liên tục. • Tối ưu hóa rời rạc (tối ưu hóa tổ hợp), trong đó miền giá trị của các biến là rời rạc (số nguyên, hoán vị, đồ thị). Tối ưu hóa liên tục Nghiên cứu [46] đưa ra dạng tổng quan của một bài toán tối ưu hóa liên tục như sau: 8
Maximize/Minimize :f (x) (1.1) Các ràng buộc :gi (x) ≤ 0 i = 1, ..., q (1.2) hj (x) = 0 j = 1, ..., p (1.3) Trong đó: • x = (x1 , x2 , ..., xn ) với xi là một biến nhận giá trị liên tục. • f (x) : R → R là hàm mục tiêu của bài toán. • gi (x) ≤ 0 thể hiện các ràng buộc bất đẳng thức. • hj (x) = 0 thể hiện các ràng buộc đẳng thức. Tối ưu hóa rời rạc Bài toán tối ưu rời rạc tổng quát có thể phát biểu như sau: Maximize/Minimize : f (x) với x ∈ D ⊂ Rn , (1.4) D là tập các vectơ x = (x1 , x2 , ..., xn ) mà một số (hoặc tất cả) các thành phần của x chỉ nhận các giá trị rời rạc. Tập D thường được xác định bởi một hệ thống các phương trình và bất phương trình với điều kiện bổ sung về tính nguyên của các biến số sau đây: gi (x) = 0, i = 1, 2, .., m1 , (1.5) gi (x) ≤ 0, i = m1 + 1, .., m, (1.6) xj − nguyên, j = 1, 2, .., n1 (1.7) Bài toán (1.4) - (1.7) được gọi là bài toán quy hoạch nguyên. Nếu n1 = n ta có bài toán quy hoạch nguyên hoàn toàn, nếu n1 < n ta có bài toán quy hoạch nguyên bộ phận. Một trong lớp các bài toán quy hoạch nguyên quan trọng là quy hoạch nguyên tuyến tính thu được từ bài toán quy hoạch nguyên tổng quát khi các hàm f (x) và gi (x) là tuyến tính. Một số cách tiếp cận giải bài toán tối ưu Có hai phương pháp giải các bài toán tối ưu là phương pháp giải chính xác (exact method) và phương pháp giải gần đúng (approximate method). Với 9