Luận án Tiến sĩ Khoa học máy tính: Tối ưu hóa thời gian sống của một lớp mạng cảm biến không dây theo hướng tiếp cận xấp xỉ

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

Thêm vào BST

Báo xấu

17
lượt xem 7
download

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

Luận án Tiến sĩ Khoa học máy tính "Tối ưu hóa thời gian sống của một lớp mạng cảm biến không dây theo hướng tiếp cận xấp xỉ" trình bày các nội dung chính sau: Tối ưu hóa thời gian sống của mạng cảm biến không dây dựa trên mô hình tổn thất truyền thông; Tối ưu hóa thời gian sống của mạng cảm biến không dây dựa trên mô hình suy hao năng lượng.

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 hóa thời gian sống của một lớp mạng cảm biến không dây theo hướng tiếp cận xấp xỉ

BỘ GIÁO DỤC ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI Nguyễn Thị Tâm TỐI ƯU HÓA THỜI GIAN SỐNG CỦA MỘT LỚP MẠNG CẢM BIẾN KHÔNG DÂY THEO HƯỚNG TIẾP CẬN XẤP XỈ LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH Hà Nội - 2021
BỘ GIÁO DỤC ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI Nguyễn Thị Tâm TỐI ƯU HÓA THỜI GIAN SỐNG CỦA MỘT LỚP MẠNG CẢM BIẾN KHÔNG DÂY THEO HƯỚNG TIẾP CẬN XẤP XỈ 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 NGƯỜI 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 - 2021
Lời cam đoan Nghiên cứu sinh cam đoan luận án này là công trình nghiên cứu của nghiên cứu sinh dưới sự hướng dẫn của tập thể cán bộ hướng dẫn. Luận án có sử dụng những thông tin được trích dẫn từ nhiều nguồn tham khảo khác nhau và các thông tin trích dẫn được ghi rõ nguồn gốc. Các số liệu, kết quả trong luận án là trung thực và chưa được công bố trong các công trình nghiên cứu của bất kỳ tác giả nào khác. Hà Nội, ngày 08 tháng 06 năm 2021 Tập thể giáo viên hướng dẫn Nghiên cứu sinh PGS.TS Huỳnh Thị Thanh Bình Nguyễn Thị Tâm PGS.TS Lê Trọng Vĩnh i
Lời cảm ơn Đầu tiên, tôi xin được gửi lời cảm ơn chân thành nhất đến thầy cô giáo hướng dẫn của tôi, PGS.TS Huỳnh Thị Thanh Bình và PGS.TS Lê Trọng Vĩnh. Thầy cô đã định hướng, giúp đỡ, và đồng hành cùng tôi trong suốt thời gian thực hiện luận án. Tôi cũng bày tỏ sự biết ơn sâu sắc của mình đến các thầy cô giáo tại Viện Công nghệ thông tin và Truyền thông, Trường Đại học Bách khoa Hà Nội đã truyền đạt cho tôi những kiến thức quý báu để tôi có thể có được nền tảng vững chắc trong quá trình hoàn thành luận án. Xin được cảm ơn PGS.TS Nguyễn Đắc Trung và các thầy cô giáo ở Phòng Đào tạo, Trường Đại học Bách khoa Hà Nội đã nhiệt tình giúp đỡ, theo sát, và hỗ trợ tôi trong quá trình học tập. Tôi xin trân trọng cảm ơn Quỹ học bổng đổi mới sáng tạo Vingroup đã không chỉ tạo điều kiện về vật chất để tôi có thể yên tâm học tập mà còn là nguồn động lực để tôi có thể hoàn thành được những mục tiêu đề ra. Tôi xin chân thành cảm ơn Ban lãnh đạo Phòng thí nghiệm Khoa học Dữ liệu và Bộ môn Tin học, Khoa Toán - Cơ - Tin học, Trường Đại học Khoa học Tự nhiên, Đại học quốc gia Hà Nội đã tạo điều kiện, động viên, khuyến khích để tôi có thể hoàn thành được luận án này. Cuối cùng, tôi muốn gửi lời cảm ơn sâu sắc đến gia đình và bạn bè đã là những điểm tựa vững chắc và đồng hành cùng tôi trong suốt những năm học tập vừa qua. Hà Nội, ngày 08 tháng 06 năm 2021 Nghiên cứu sinh Nguyễn Thị Tâm ii
MỤC LỤC DANH MỤC THUẬT NGỮ VÀ TỪ VIẾT TẮT vi DANH MỤC BẢNG BIỂU vii DANH MỤC HÌNH ẢNH x GIỚI THIỆU 1 Chương 1 CƠ SỞ LÝ THUYẾT 8 1.1 Bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.1 Bài toán tối ưu đơn mục tiêu . . . . . . . . . . . . . . . . . . 8 1.1.2 Bài toán tối ưu đa mục tiêu . . . . . . . . . . . . . . . . . . . 9 1.2 Một số thuật toán giải bài toán tối ưu đơn mục tiêu . . . . . . . . 15 1.2.1 Thuật toán di truyền . . . . . . . . . . . . . . . . . . . . . . 15 1.2.2 Thuật toán tiến hóa đa nhân tố . . . . . . . . . . . . . . . . 19 1.3 Một số thuật toán giải bài toán tối ưu đa mục tiêu . . . . . . . . . 24 1.3.1 Thuật toán di truyền sắp xếp không trội . . . . . . . . . . . 25 1.3.2 Thuật toán tiến hóa đa mục tiêu dựa trên phân rã . . . . . 31 1.3.3 Các độ đo đa mục tiêu . . . . . . . . . . . . . . . . . . . . . . 36 1.4 Bài toán tối ưu thời gian sống của mạng cảm biến không dây . . . 38 1.4.1 Định nghĩa thời gian sống của mạng . . . . . . . . . . . . . . 38 1.4.2 Bài toán tối ưu thời gian sống cho mạng cảm biến không dây ngầm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 1.4.3 Bài toán tối ưu thời gian sống cho mạng cảm biến không dây địa hình ba chiều . . . . . . . . . . . . . . . . . . . . . . 44 1.5 Kết luận chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 Chương 2 TỐI ƯU HÓA THỜI GIAN SỐNG CỦA MẠNG CẢM BIẾN KHÔNG DÂY DỰA TRÊN MÔ HÌNH TỔN THẤT TRUYỀN THÔNG 48 2.1 Đặt vấn đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.2 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.2.1 Mô hình hóa bài toán . . . . . . . . . . . . . . . . . . . . . . 50 2.2.2 Mô hình quy hoạch nguyên . . . . . . . . . . . . . . . . . . . 51 iii
2.3 Thuật toán đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.3.1 Thuật toán tìm kiếm chùm tia với hàm Genitor . . . . . . . 53 2.3.2 Thuật toán di truyền với khởi tạo dựa trên phâm cụm . . . 57 2.3.3 Thuật toán tìm kiếm chùm tia và cặp ghép trong đồ thị . . 64 2.4 Thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 2.4.1 Dữ liệu thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . 70 2.4.2 Cài đặt thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . 71 2.4.3 Tiêu chí đánh giá . . . . . . . . . . . . . . . . . . . . . . . . . 72 2.4.4 So sánh và đánh giá kết quả thực nghiệm . . . . . . . . . . . 73 2.4.5 Đánh giá độ phức tạp thuật toán . . . . . . . . . . . . . . . 85 2.5 Kết luận chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 Chương 3 TỐI ƯU HÓA THỜI GIAN SỐNG CỦA MẠNG CẢM BIẾN KHÔNG DÂY DỰA TRÊN MÔ HÌNH SUY HAO NĂNG LƯỢNG 88 3.1 Đặt vấn đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 3.2 Mô hình bài toán trong địa hình ba chiều . . . . . . . . . . . . . . 89 3.2.1 Dữ liệu độ cao số . . . . . . . . . . . . . . . . . . . . . . . . . 89 3.2.2 Mô hình bài toán . . . . . . . . . . . . . . . . . . . . . . . . . 90 3.2.3 Mô hình quy hoạch nguyên . . . . . . . . . . . . . . . . . . . 93 3.3 Thuật toán tìm kiếm cục bộ . . . . . . . . . . . . . . . . . . . . . . 94 3.3.1 Biểu diễn lời giải . . . . . . . . . . . . . . . . . . . . . . . . . 94 3.3.2 Lượng giá lời giải . . . . . . . . . . . . . . . . . . . . . . . . . 95 3.3.3 Tìm kiếm các láng giềng . . . . . . . . . . . . . . . . . . . . . 97 3.3.4 Khởi tạo lời giải . . . . . . . . . . . . . . . . . . . . . . . . . 98 3.3.5 Thuật toán leo đồi ngẫu nhiên . . . . . . . . . . . . . . . . . 98 3.3.6 Thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 3.4 Thuật toán tối ưu đa mục tiêu dựa trên phân rã . . . . . . . . . . 105 3.4.1 Chuẩn hóa các hàm mục tiêu . . . . . . . . . . . . . . . . . . 106 3.4.2 Thuật toán đa mục tiêu dựa trên phân rã các mục tiêu . . . 106 3.4.3 Thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 3.4.4 Đánh giá độ phức tạp thuật toán . . . . . . . . . . . . . . . 119 3.5 Thuật toán tiến hóa đa nhân tố giải bài toán tối ưu trên các loại mạng khác nhau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 iv
3.5.1 Biểu diễn lời giải . . . . . . . . . . . . . . . . . . . . . . . . . 125 3.5.2 Thuật toán tiến hóa đa nhân tố giải bài toán tối ưu thời gian sống cho hai loại mạng . . . . . . . . . . . . . . . . . . . 127 3.5.3 Thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 3.6 Kết luận chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 Chương 4 KẾT LUẬN 139 DANH MỤC CÔNG TRÌNH CÔNG BỐ 141 TÀI LIỆU THAM KHẢO 143 v
DANH MỤC THUẬT NGỮ VÀ TỪ VIẾT TẮT STT Từ viết tắt Tên đầy đủ 1 BGS Beam Genitor Search 2 BMBM Beam Boltzmann Search and Maximum Bipartite Matching Sensor Nodes Reassignment 3 BS Beam Search 4 CluRNS Clustering-based heuristic for Relay Node Selection 5 FCLS Flow Capacity Local Search 6 LBSNA Load Balanced Sensor Node Assignment 7 LURNS Load Unrestricted Relay Node Selection 8 MBFS Maxium Flow Binary Search 9 MBM-RS Maximum Bipartite Matching Sensor Nodes Reassignment 10 MFEA Multif actorial Evolutionary Algorithm 11 MOEAs Multiobjective Evolutionary Algorithms 12 MOEAD Multiobjective Evolutionary Algorithm based on Decomposition 13 MRP Min-Max Relay Placement 14 MXFBS Maxium Flow Binary Search 15 MXF-MC Maxium Flow with Min-max Cost 16 MXFGA Maxium Flow-based Genetic Algorithm 17 NSGA-II Non-dominated Sorting Genetic Algorithm II 18 ORP3D Optimal Relay Node Placement in 3D terrains 19 OSA3D Optimal Sensor Assignment in 3D terrains 20 WSNs Wireless Sensor Networks 21 WUSNs Wireless Underground Sensor Networks 22 RNs Relay Nodes 23 SNs Sensor Nodes vi
DANH MỤC BẢNG BIỂU 1.1 Giá trị cp và Dp được tính từ ma trận trội. . . . . . . . . . . . . . . 27 1.2 Giá trị của các tham số truyền thông trong mạng. . . . . . . . . . 45 2.1 Các tham số về địa hình. . . . . . . . . . . . . . . . . . . . . . . . . 70 2.2 Các tham số bài toán. . . . . . . . . . . . . . . . . . . . . . . . . . . 70 2.3 Các tham số của thuật toán. . . . . . . . . . . . . . . . . . . . . . . 72 2.4 Tiêu chí đánh giá. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 2.5 Giá trị tổn thất truyền thông trung bình với kích thước chùm tia khác nhau. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 2.6 So sánh thời gian thực hiện thuật toán BMBM với kích thước chùm tia khác nhau. . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 2.7 Giá trị tổn thất truyền thông trung bình với các giá trị tt khác nhau. 76 2.8 So sánh kết quả thu được của các thuật toán trên kịch bản 1. . . . 77 2.9 So sánh kết quả thu được của các thuật toán trên kịch bản 2. . . . 78 2.10 So sánh kết quả thu được của các thuật toán trên kịch bản 3 . . . 80 2.11 So sánh kết quả thu được của các thuật toán trên kịch bản 4 . . . 81 2.12 So sánh kết quả thu được của các thuật toán trên kịch bản 5 . . . 82 2.13 So sánh kết quả thu được của các thuật toán trên kịch bản 6 . . . 83 2.14 Tóm tắt kết quả đạt được của các thuật toán. . . . . . . . . . . . . 85 2.15 So sánh độ phức tạp của các thuật toán. . . . . . . . . . . . . . . . 86 3.1 Mô tả tóm tắt các hình thái địa hình. . . . . . . . . . . . . . . . . . 99 3.2 Tham số cho các địa hình. . . . . . . . . . . . . . . . . . . . . . . . 100 3.3 Tiêu chí đánh giá. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 3.4 Kết quả khởi tạo MBFS và khởi tạo ngẫu nhiên trên tập dữ liệu Type 3s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 vii
3.5 Kết quả khởi tạo MBFS và khởi tạo ngẫu nhiên trên tập dữ liệu Type 3l . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 3.6 Kết quả thu được trên các tập dữ liệu Type 1s, Type 2s, Type 3s. 103 3.7 Kết quả thu được trên các tập dữ liệu Type 1l, Type 2l, Type 3l. . 103 3.8 Kết quả thu được trên các tập dữ liệu Type 3s, Type 4s, Type 5s. 104 3.9 Kết quả thu được trên các tập dữ liệu Type 3l, Type 4l, Type 5l. . 104 3.10 Tham số thuật toán MOEA-LS . . . . . . . . . . . . . . . . . . . . 112 3.11 So sánh thuật toán MOEA-LS và các thuật toán tiến hóa đa mục tiêu dựa trên độ đo δ . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 3.12 So sánh các thuật toán tiến hóa đa mục tiêu dựa trên độ đo ∆. . . 114 3.13 So sánh các thuật toán tiến hóa đa mục tiêu khác dựa trên độ đo S .115 3.14 So sánh các thuật toán tiến hóa đa mục tiêu khác dựa trên độ đo N DS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 3.15 So sánh số lượng bộ dữ liệu mà thuật toán MOEA-LS tốt hơn thuật toán tiến hóa đa mục tiêu khác . . . . . . . . . . . . . . . . . 116 3.16 So sánh năng lượng tiêu thụ của các thuật toán khác nhau (đơn vị mJ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 3.17 So sánh thuật toán MOEA-LS và thuật toán FCLS dựa trên độ đo S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 3.18 Độ phức tạp của các thuật toán đa mục tiêu. . . . . . . . . . . . . 121 3.19 Tham số cho bài toán RSS và RSM. . . . . . . . . . . . . . . . . . . 131 3.20 Các bộ dữ liệu cho bài toán RSM. . . . . . . . . . . . . . . . . . . . 131 3.21 Các bộ dữ liệu cho bài toán RSS. . . . . . . . . . . . . . . . . . . . 131 3.22 Các tiêu chí đánh giá . . . . . . . . . . . . . . . . . . . . . . . . . . 131 3.23 Tham số cho các thuật toán . . . . . . . . . . . . . . . . . . . . . . 132 3.24 So sánh năng lượng tiêu thụ tìm được trên bài toán RSM với các giá trị rmp khác nhau. . . . . . . . . . . . . . . . . . . . . . . . . . . 133 3.25 So sánh năng lượng tiêu thụ tìm được trên bài toán RSS với các giá trị rmp khác nhau. . . . . . . . . . . . . . . . . . . . . . . . . . . 133 3.26 So sánh năng lượng tiêu thụ trên bài toán RSM với số lượng tác vụ khác nhau. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 3.27 So sánh năng lượng tiêu thụ trên bài toán RSS với số lượng tác vụ khác nhau. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 viii
3.28 Đánh giá hiệu quả của thuật toán trên bài toán RSM với bán kính khác nhau. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 3.29 Đánh giá hiệu quả của thuật toán trên bài toán RSS với bán kính khác nhau. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 ix
DANH MỤC HÌNH ẢNH 1.1 Minh họa hai hàm mục tiêu f1 , f2 trong không gian thiết kế. . . . . 10 1.2 Minh họa không gian thiết kế và không gian mục tiêu. . . . . . . . 12 1.3 Ví dụ về tối ưu Pareto và tối ưu Pareto yếu. . . . . . . . . . . . . . 15 1.4 Sơ đồ khối của thuật toán di truyền. . . . . . . . . . . . . . . . . . 17 1.5 Minh họa việc sắp xếp không trội . . . . . . . . . . . . . . . . . . . 26 1.6 Ma trận trội. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.7 Minh họa khoảng cách quy tụ . . . . . . . . . . . . . . . . . . . . . 29 1.8 Minh họa việc lựa chọn các cá thể để đưa vào quần thể Pt+1 . . . . 31 1.9 Minh họa cách tiếp cận dựa trên biên . . . . . . . . . . . . . . . . . 33 1.10 Minh họa độ đo HV cho bài toán tối ưu hai mục tiêu. . . . . . . . 37 1.11 Truyền thông trong mạng cảm biến không dây ngầm. . . . . . . . . 41 2.1 Minh họa cho hàm Genitor với bias = 2. . . . . . . . . . . . . . . . . 56 2.2 Minh họa thuật toán BGS. . . . . . . . . . . . . . . . . . . . . . . . 56 2.3 Biểu diễn cá thể. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.4 Ví dụ của đồ thị G với khả năng thông qua . . . . . . . . . . . . . 61 2.5 Minh họa toán tử lai ghép của thuật toán MXFGA. . . . . . . . . 63 2.6 Minh họa toán tử đột biến của thuật toán MXFGA. . . . . . . . . 63 2.7 Đánh giá ảnh hưởng của tỉ lệ khởi tạo. . . . . . . . . . . . . . . . . 74 2.8 Tỉ lệ % các thuật toán đề xuất cải thiện so với Yuan trên kịch bản 1. 77 2.9 Tỉ lệ % các thuật toán đề xuất cải thiện so với Yuan trên kịch bản 2. 78 2.10 Tỉ lệ % các thuật toán đề xuất cải thiện so với Yuan trên kịch bản 3. 79 2.11 Tỉ lệ % các thuật toán đề xuất cải thiện so với Yuan trên kịch bản 4. 80 2.12 Tỉ lệ % các thuật toán đề xuất cải thiện so với Yuan trên kịch bản 5. 82 2.13 Tỉ lệ % các thuật toán đề xuất cải thiện so với Yuan trên kịch bản 6. 83 x
3.1 Ví dụ về đồ thị luồng được xây dựng từ các nút chuyển tiếp và các nút cảm biến. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 3.2 Ví dụ về các phép dịch chuyển. . . . . . . . . . . . . . . . . . . . . . 97 3.3 Minh họa một số địa hình. . . . . . . . . . . . . . . . . . . . . . . . 100 3.4 So sánh số lượng nút chuyển tiếp và năng lượng tiêu thụ (J) trên các tập dữ liệu Type 3s, Type 4s, Type 5s. . . . . . . . . . . . . . . 105 3.5 So sánh số lượng nút chuyển tiếp và năng lượng tiêu thụ (J) trên các tập dữ liệu Type 3l, Type 4l, Type 5l. . . . . . . . . . . . . . . 105 3.6 Ví dụ cách mã hóa cá thể. . . . . . . . . . . . . . . . . . . . . . . . 108 3.7 Ví dụ về các phép toán di truyền. . . . . . . . . . . . . . . . . . . . 110 3.8 Minh họa phương pháp giảm năng lượng cho các nút chuyển tiếp. 112 3.9 Số lượng nút chuyển tiếp sử dụng trong kịch bản 1. . . . . . . . . . 117 3.10 Số lượng nút chuyển tiếp sử dụng trong kịch bản 2. . . . . . . . . . 117 3.11 So sánh độ đo HV giữa thuật toán đề xuất và thuật toán đơn mục tiêu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 3.12 Ví dụ cho bài toán RSS. . . . . . . . . . . . . . . . . . . . . . . . . . 123 3.13 Ví dụ cho bài toán RSM. . . . . . . . . . . . . . . . . . . . . . . . . 124 3.14 Biểu diễn lời giải với mã hóa netkeys. . . . . . . . . . . . . . . . . . 125 3.15 Quá trình xây dựng cây. . . . . . . . . . . . . . . . . . . . . . . . . . 126 3.16 Giải mã cá thể cho từng tác vụ. . . . . . . . . . . . . . . . . . . . . 128 3.17 Ví dụ về phép lai ghép . . . . . . . . . . . . . . . . . . . . . . . . . . 129 3.18 Ví dụ minh họa phép đột biến. . . . . . . . . . . . . . . . . . . . . . 130 3.19 Sự cải thiện kết quả của thuật toán MFRPEA so với các thuật toán khác trên bài toán RSS và bài toán RSM. . . . . . . . . . . . 136 xi
MỞ ĐẦU Trong những năm gần đây, cùng với sự phát triển nhanh chóng của khoa học công nghệ, mạng cảm biến không dây (wireless sensor networks - WSNs) đã được nhiều nhà khoa học quan tâm nghiên cứu. WSNs là mạng liên kết các nút cảm biến (sensor nodes) với nhau nhờ các liên kết không dây như sóng vô tuyến, hồng ngoại [1]. Mỗi nút cảm biến có chức năng cảm nhận, thu thập, xử lý và truyền dữ liệu. Các nút này thường là các thiết bị đơn giản, nhỏ gọn, giá thành thấp được phân bố trên một phạm vi rộng lớn thường gọi là các khu vực cảm biến (sensor fields). Trong mạng cảm biến, dữ liệu sau khi được thu thập bởi các nút cảm biến sẽ được định tuyến đến các trạm cơ sở (base stations). Các trạm cơ sở sẽ gửi dữ liệu đến người dùng thông qua Internet hay vệ tinh. Các đặc tính như triển khai nhanh chóng, khả năng tự tổ chức và chịu lỗi đã cho thấy mạng cảm biến không dây là một công nghệ đầy triển vọng. Ngày nay, mạng cảm biến không dây được áp dụng trong các lĩnh vực khác của đời sống, từ các ứng dụng trong dân sự như: nông nghiệp, môi trường đến những ứng dụng trong quân sự như giám sát chiến trường, phát hiện vũ khí hóa học [2]. Một trong những đặc trưng riêng biệt của mạng cảm biến không dây chính là hạn chế về khả năng tính toán và năng lượng của các nút cảm biến, do các nút này sử dụng nguồn năng lượng pin hoặc ắc quy để tồn tại. Sau khi triển khai mạng, việc tiếp thêm năng lượng cho các nút cảm biến là không khả thi trong trường hợp mạng được triển khai trong những địa hình khắc nghiệt. Do đó, năng lượng của các cảm biến đóng một vai trò quan trọng, quyết định thời gian sống (thời gian tồn tại) của mạng. Trong nghiên cứu [3], các tác giả đưa ra nhiều định nghĩa khác nhau để tính thời gian sống của mạng dựa vào số lượng các nút còn hoạt động (còn sống) trong mạng. Trong đó, cách định nghĩa thời gian sống của mạng là thời gian từ khi khởi tạo mạng cho đến khi nút đầu tiên trong mạng hết năng lượng được nhiều tác giả sử dụng. Cách định nghĩa này phù hợp đối với các mạng mà vai trò của các nút cảm biến là như nhau, nếu một nút hết năng lượng thì việc phân tích dữ liệu thu thập được sẽ không còn chính xác. Hầu hết các nghiên cứu đã có đều tập trung vào việc tối ưu thời gian sống cho mạng cảm biến không dây trong địa hình hai chiều. Giả định này hợp lý 1
đối với các ứng dụng mà các nút cảm biến được triển khai trên một địa hình tương đối đồng đều, độ cao của các nút không đáng kể so với bán kính truyền thông. Tuy nhiên, trong nhiều ứng dụng thực tế, khi triển khai mạng cần xem xét đến độ cao và độ sâu các nút mạng. Vì vậy, trong luận án này, tác giả tập trung nghiên cứu bài toán tối ưu thời gian sống cho hai loại mạng: mạng cảm biến không dây ngầm (wireless underground sensor networks - WUSNs) với các nút cảm biến được đặt dưới đất và mạng cảm biến không dây trong địa hình ba chiều (wireless sensor networks in three dimensional terrains - WSN3D) với các nút cảm biến được đặt trong địa hình ba chiều. Nhiều bài toán tối ưu thời gian sống cho mạng WUSNs và mạng WSN3D là bài toán NP-hard. Có hai cách tiếp cận để giải bài toán dạng này: sử dụng thuật toán chính xác và sử dụng thuật toán xấp xỉ. Các thuật toán chính xác đảm bảo tìm được lời giải chính xác cho các bài toán tối ưu thời gian sống của mạng. Tuy nhiên, đối với những bài toán có kích thước dữ liệu lớn, phương pháp này là không khả thi. Việc áp dụng các thuật toán xấp xỉ được ưu tiên sử dụng. Mặc dù các thuật toán xấp xỉ chỉ tìm đượ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. Mục tiêu nghiên cứu của luận án Trên cơ sở phân tích ở trên, tác giả chọn đề tài “Tối ưu hóa thời gian sống của một lớp mạng cảm biến không dây theo hướng tiếp cận xấp xỉ ” làm đề tài nghiên cứu cho luận án Tiến sĩ. Luận án hướng đến việc sử dụng các thuật toán meta-heuristic (một lớp các thuật toán xấp xỉ) để giải quyết bài toán tối ưu thời gian sống cho hai loại mạng: mạng WUSNs và mạng WSN3D. Các mục tiêu cụ thể trong luận án bao gồm: Mục tiêu thứ nhất của luận án là nghiên cứu về mạng cảm biến không dây, vấn đề tối ưu thời gian sống trong mạng cảm biến không dây. Đặc biệt, luận án đi sâu vào giải quyết vấn đề tối ưu thời gian sống của hai lớp mạng cảm biến không dây: WUSNs và WSN3D bằng việc sử dụng các nút chuyển tiếp. Mục tiêu thứ hai của luận án là nghiên cứu các kỹ thuật để giải quyết bài toán tối ưu thời gian sống cho hai lớp mạng ở trên. Bởi vì các bài toán được nghiên cứu trong luận án đều là các bài toán NP-hard nên tác giả tiếp cận các giải thuật gần đúng để giải quyết các bài toán này. 2
Mục tiêu thứ ba của luận án là nghiên cứu các phương pháp xây dựng kịch bản mạng, xây dựng các bộ dữ liệu, xây dựng các kịch bản thực nghiệm để đánh giá được hiệu quả của các thuật toán đề xuất. Phạm vi nghiên cứu Trong mạng cảm biến không dây, các nút cảm biến gần nút nguồn/trạm cơ sở có khả năng bị cạn kiệt nguồn năng lượng nhanh hơn do chúng phải định tuyến dữ liệu nhiều hơn. Phương pháp định tuyến truyền thống được sử dụng là phương pháp phân cụm. Trong phương pháp này, các cảm biến sẽ được phân thành các cụm, trong mỗi cụm sẽ có một nút đóng vai trò là cụm đầu. Dữ liệu từ các cảm biến thay vì được gửi trực tiếp đến trạm cơ sở hoặc các nút nguồn sẽ được gửi thông qua các cụm đầu. Cụm đầu chịu trách nhiệm điều hướng hoạt động của các thành viên trong cụm và giao tiếp với các cụm đầu khác hoặc trạm cơ sở. Tuy nhiên, cụm đầu phải chuyển tiếp dữ liệu của tất cả các nút trong cụm sẽ dẫn đến tiêu hao năng lượng nhanh hơn các nút khác. Gần đây, các phương pháp sử dụng các nút chuyển tiếp (relay nodes) để kéo dài thời gian sống của mạng đã được các nhà nghiên cứu quan tâm. Ý tưởng của phương pháp này là sử dụng nút chuyển tiếp để giảm khoảng cách truyền thông từ các nút cảm biến đến trạm cơ sở, từ đó có thể giảm năng lượng tiêu thụ. Các nút chuyển tiếp có nguồn năng lượng giới hạn nên cần cân bằng tải giữa chúng để đảm bảo không có nút nào bị quá tải. Trong các nghiên cứu trước đó, vấn đề này bị bỏ qua, các nút cảm biến được tự động gán cho các nút chuyển tiếp có khoảng cách ngắn nhất hoặc sự suy hao trong quá trình truyền dẫn là ít nhất. Điều này dẫn đến sự phân bố không đồng đều của các nút. Một vài nút chuyển tiếp sẽ phải xử lý nhiều do ở gần nhiều nút cảm biến hơn. Trong khi đó, một vài nút chuyển tiếp khác có thể không có bất kì các nút cảm biến nào được kết nối đến. Cân bằng tải là cách tiếp cận tốt nhất để tăng thông lượng và làm giảm tắc nghẽn trong mạng. Ý tưởng cân bằng tải là chỉ định một khối lượng công việc như nhau cho tất cả các nút chuyển tiếp. Hai cách cân bằng tải cho nút chuyển tiếp có thể có là cân bằng tải về số lượng và cân bằng tải về năng lượng. Trong cách cân bằng tải về số lượng, mỗi nút chuyển tiếp sẽ thực hiện việc tập hợp dữ liệu của một số các nút cảm biến như nhau. Trong cách cân bằng tải về năng lượng, các nút chuyển tiếp sẽ tiêu thụ một lượng năng lượng như nhau. Các nghiên cứu liên quan đến việc triển khai nút chuyển tiếp để kéo dài thời gian sống của 3
mạng có thể chia thành hai loại: có ràng buộc và không có ràng buộc. Các bài toán không có ràng buộc là bài toán triển khai các nút chuyển tiếp tại các vị trí bất kỳ trên địa hình. Ngược lại, trong bài toán triển khai có ràng buộc, các nút chuyển tiếp chỉ được triển khai tại các vị trí xác định trước trên địa hình. Các vị trí này không nằm trong các lỗ hổng vật lý của mạng như sông, suối, ao, hồ,... Từ khía cạnh cấu trúc định tuyến, việc triển khai nút chuyển tiếp theo cách này được phân thành hai loại: kiến trúc đơn tầng (single-tiered ) và kiến trúc hai tầng (two-tiered ). Trong kiến trúc đơn tầng, cả nút cảm biến (SNs) và nút chuyển tiếp (RNs) đều có thể gửi gói tin. Trong khi đó, đối với kiến trúc hai tầng chỉ RNs chuyển tiếp gói tin và SNs chỉ có vai trò thu thập dữ liệu và truyền dữ liệu đến RNs (hoặc BS nếu chúng có thể kết nối trực tiếp đến BS). Luận án tập trung vào giải quyết bài toán có ràng buộc theo cả hai loại kiến trúc mạng. Chi tiết về phạm vi nghiên cứu của luận án được đưa ra như sau: Tối ưu hóa thời gian sống của mạng WUSNs: luận án nghiên cứu bài toán tối ưu thời gian sống của mạng WUSNs với kiến trúc mạng hai tầng dựa trên mô hình tổn thất truyền thông. Mô hình này thường được sử dụng trong các loại mạng cảm biến không dây ngầm. Việc tối ưu thời gian sống của mạng cảm biến không dây dựa trên mô hình tổn thất truyền thông được nhiều các nhà nghiên cứu quan tâm [4, 5, 6, 7]. Lý do cho việc sử dụng mô hình này là do năng lượng tiêu thụ của các nút cảm biến tỉ lệ thuận với tổn thất truyền thông. Việc tối ưu tổn thất truyền thông sẽ dẫn đến tối ưu năng lượng tiêu thụ của các nút, nhờ đó kéo dài thời gian sống của mạng. Đối với với các mạng cảm biến không dây ngầm, việc truyền tín hiệu trong đa môi trường sẽ dẫn đến sự suy giảm của tín hiệu do sự hấp thụ của nhiều yếu tố trong đất và sự phản xạ, khúc xạ ở bền mặt. Sự suy giảm trong môi trường đất phụ thuộc vào một số yếu tố như thành phần của đất, mật độ, hàm lượng nước và thể tích. Ngoài ra, các đặc tính lan truyền của sóng điện từ ở trong đất cũng khác biệt khá nhiều so với trong không khí. Sóng điện từ sẽ bị suy hao do ảnh hưởng của khoảng cách truyền thông. Tối ưu hóa thời gian sống của mạng WSN3D: luận án nghiên cứu bài toán tối ưu hóa thời gian sống của mạng WSN3D theo cả hai loại kiến trúc mạng: đơn tầng và hai tầng dựa trên mô hình suy hao năng lượng. Năng lượng của một nút cảm biến tiêu thụ chủ yếu cho các nhiệm vụ: truyền thông, xử lý dữ liệu, cảm biến dữ liệu [8]. Có nhiều mô hình suy hao năng lượng đã được 4
đề xuất, trong đó mô hình suy hao năng lượng dựa vào khoảng cách đã được nhiều nhà nghiên cứu sử dụng [9, 10, 11, 12]. Trong mô hình này, năng lượng tiêu thụ chủ yếu được tính dựa vào sự suy hao năng lượng khi truyền dữ liệu trong một khoảng cách nhất định. Mô hình này dùng cho các mạng cảm biến được triển khai ở phía trên mặt đất trong địa hình ba chiều. Ngoài ra, trong giao tiếp không dây, hai nút có thể không kết nối được với nhau do hai nguyên nhân chính. Lý do thứ nhất là khoảng cách giao tiếp quá lớn. Lý do thứ hai là đường tầm nhìn (line-of-sight) giữa hai nút có nhiều vật cản. Luận án tuân theo giả định đầu tiên, có nghĩa là, hai nút trong mạng có thể kết nối được với nhau nếu khoảng cách giữa chúng không quá lớn (khoảng cách giữa hai nút nhỏ hơn bán kính truyền thông). Các đóng góp chính của luận án Bài toán 1: tối ưu hóa việc triển khai các nút chuyển tiếp để kéo dài thời gian sống của mạng cảm biến không dây ngầm (WUSNs) dựa trên mô hình tổn thất truyền thông (bài toán MRP). Bài toán này sẽ xem xét ràng buộc cân bằng tải về số lượng cho các nút chuyển tiếp. Trong nghiên cứu [7], các tác giả đề xuất cách tiếp cận hai pha với sáu thuật toán heuristic để giải quyết bài toán MRP. Nhược điểm của các thuật toán đề xuất là chia bài toán thành hai pha riêng biệt, các nút chuyển tiếp đã được lựa chọn trong pha thứ nhất sẽ không thể được thay đổi trong pha thứ hai. Điều này dẫn đến việc, nếu chọn các vị trí không tốt để đặt các nút chuyển tiếp sẽ dẫn đến một lời giải có chất lượng không tốt. Do đó, luận án đề xuất các thuật toán để khắc phục nhược điểm của 6 thuật toán đã có: Đề xuất thuật toán tham lam dựa trên tìm kiếm chùm tia với hàm Genitor (BGS) để tạo ra nhiều lời giải cho bài toán MRP. Tuy nhiên, thuật toán BGS có hạn chế là cách lựa chọn các nút cảm biến để kết nối đến nút chuyển tiếp trong mỗi bước là tham lam. Cách lựa chọn tham lam này chưa chắc đã dẫn đến một lời giải tối ưu toàn cục. Từ hạn chế của thuật toán BGS, luận án đề xuất thuật toán di truyền với khởi tạo phân cụm (MXFGA) để giải quyết bài toán. Ý tưởng của cách tiếp cận này là nếu biết chính xác các vị trí được lựa chọn để đặt nút chuyển tiếp, chúng ta có thể tìm được cách kết nối giữa các nút chuyển tiếp và các nút cảm biến sao cho giá trị tổn thất truyền thông lớn nhất của các 5
cặp kết nối tìm được là nhỏ nhất. Thuật toán MXFGA có hạn chế là thời gian chạy khá lâu do độ phức tạp của khởi tạo phân cụm và thuật toán di truyền. Ngoài ra, các toán tử lai ghép và đột biến cũng làm thay đổi khá nhiều cấu trúc cụm ban đầu. Để khắc phục hạn chế của BGS và MXFGA, luận án đề xuất thuật toán BMBM dựa trên sự kết hợp của thuật toán tìm kiếm chùm tia với hàm phân phối Boltzmann để tạo ra các phương án khả thi cho bài toán tối ưu hóa thời gian sống của mạng. Các cặp kết nối giữa các nút cảm biến và các nút chuyển tiếp sẽ được tìm chính xác bằng cách đưa về bài toán tìm cặp ghép trên đồ thị. Bài toán 2: tối ưu hóa đa mục tiêu việc triển khai các nút chuyển tiếp để kéo dài thời gian sống của mạng cảm biến không dây địa hình ba chiều (bài toán ORP3D) dựa trên mô hình suy hao năng lượng. Bài toán này sẽ xem xét việc cân bằng tải về năng lượng cho các nút chuyển tiếp. Hai cách tiếp cận được đề xuất để giải quyết bài toán này: Đề xuất phương pháp dựa trên tổng trọng số để đưa bài toán đa mục tiêu ORP3D về bài toán tối ưu hóa đơn mục tiêu (OSA3D). Luận án đề xuất mô hình quy hoạch nguyên để tìm được cận dưới của lời giải. Cuối cùng, thuật toán tìm kiếm cục bộ dựa trên luồng cực đại được đề xuất để giải bài toán OSA3D. Đề xuất thuật toán tiến hóa đa mục tiêu dựa trên phân rã để tìm biên Pareto xấp xỉ biên tối ưu. Bài toán 3: tối ưu hóa thời gian sống cho các loại mạng cảm biến không dây trong địa hình ba chiều với các cấu trúc mạng khác nhau. Luận án đề xuất thuật toán tiến hóa đa nhân tố với cách mã hóa Netkeys để giải quyết bài toán. 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 luận án được trình bày trong ba chương 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, các phương pháp giải bài toán tối ưu đơn mục tiêu và đa mục tiêu. Ngoài ra, các nghiên cứu liên quan đến bài toán tối ưu hóa thời gian sống của mạng cảm biến không dây cũng được trình bày. Chương 2: tối ưu hóa thời gian sống của mạng cảm biến không dây dựa trên mô hình tổn thất truyền thông. Trong chương này, luận án 6
nghiên cứu bài toán triển khai các nút chuyển tiếp để tối ưu thời gian sống của mạng cảm biến không dây ngầm dựa trên mô hình tổn thất truyền thông nhằm đảm bảo ràng buộc cân bằng tải về số lượng giữa các nút chuyển tiếp. Luận án đề xuất ba cách tiếp cận để giải quyết bài toán. So sánh các cách tiếp cận đề xuất với các nghiên cứu trước đó về: giá trị của hàm mục tiêu, độ phức tạp của thuật toán và thời gian thực hiện. Chương 3: tối ưu hóa thời gian sống của mạng cảm biến không dây dựa trên mô hình suy hao năng lượng. Trong chương này, luận án nghiên cứu hai bài toán. Bài toán thứ nhất là bài toán đa mục tiêu triển khai các nút chuyển tiếp để tối ưu hóa thời gian sống của mạng trong địa hình ba chiều. Bài toán này có hai mục tiêu chính: tối thiểu số lượng các nút chuyển tiếp được sử dụng và tối thiểu giá trị tiêu thụ năng lượng tối đa của các nút trong mạng. Để giải quyết bài toán này, hai cách tiếp cận được đề xuất. Cách tiếp cận đầu tiên dựa trên tổng trọng số. Ý tưởng của cách tiếp cận này là đưa bài toán đa mục tiêu về bài toán đơn mục tiêu bằng cách thêm trọng số cho các hàm mục tiêu. Thuật toán tìm kiếm cục bộ dựa trên luồng cực đại được đề xuất để giải quyết bài toán đơn mục tiêu này. Cách tiếp cận thứ hai dựa trên các thuật toán tối ưu đa mục tiêu để tìm một biên Pareto xấp xỉ cho bài toán. Bài toán thứ hai là bài toán tối ưu thời gian sống của các mạng có cấu trúc khác nhau: mạng đơn tầng và mạng hai tầng. Luận án đề xuất thuật toán tiến hóa đa nhân tố để giải quyết bài toán này. 7