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
