Luận án tiến sĩ 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 th

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.TS Huỳnh Thị Thanh Bình 2.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 .1 Bài toán tối ưu đơn mục tiêu .2 Bài toán tối ưu đa mục tiêu .2 Một số thuật toán giải bài toán tối ưu đơn mục tiêu .1 Thuật toán di truyền .2 Thuật toán tiến hóa đa nhân tố .3 Một số thuật toán giải bài toán tối ưu đa mục tiêu .1 Thuật toán di truyền sắp xếp không trội .2 Thuật toán tiến hóa đa mục tiêu dựa trên phân rã .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 .1 Định nghĩa thời gian sống của mạng .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 .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 .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.2 Phát biểu bài toán .1 Mô hình hóa bài toán .2 Mô hình quy hoạch nguyên .3 Thuật toán đề xuất .1 Thuật toán tìm kiếm chùm tia với hàm Genitor .2 Thuật toán di truyền với khởi tạo dựa trên phâm cụm .3 Thuật toán tìm kiếm chùm tia và cặp ghép trong đồ thị .1 Dữ liệu thực nghiệm .2 Cài đặt thực nghiệm .3 Tiêu chí đánh giá .4 So sánh và đánh giá kết quả thực nghiệm .5 Đánh giá độ phức tạp thuật toán .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.2 Mô hình bài toán trong địa hình ba chiều .1 Dữ liệu độ cao số .2 Mô hình bài toán .3 Mô hình quy hoạch nguyên .3 Thuật toán tìm kiếm cục bộ .1 Biểu diễn lời giải .2 Lượng giá lời giải .3 Tìm kiếm các láng giềng .4 Khởi tạo lời giải .5 Thuật toán leo đồi ngẫu nhiên .4 Thuật toán tối ưu đa mục tiêu dựa trên phân rã .1 Chuẩn hóa các hàm mục tiêu .2 Thuật toán đa mục tiêu dựa trên phân rã các mục tiêu .4 Đánh giá độ phức tạp thuật toán .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 .1 Biểu diễn lời giải .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 .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.2 Giá trị của các tham số truyền thông trong mạng.1 Các tham số về địa hình.2 Các tham số bài toán.3 Các tham số của thuật toán.4 Tiêu chí đánh giá.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.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.7 Giá trị tổn thất truyền thông trung bình với các giá trị tt khác nhau.8 So sánh kết quả thu được của các thuật toán trên kịch bản 1.9 So sánh kết quả thu được của các thuật toán trên kịch bản 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 .11 So sánh kết quả thu được của các thuật toán trên kịch bản 4 .12 So sánh kết quả thu được của các thuật toán trên kịch bản 5 .13 So sánh kết quả thu được của các thuật toán trên kịch bản 6 .14 Tóm tắt kết quả đạt được của các thuật toán.15 So sánh độ phức tạp của các thuật toán.1 Mô tả tóm tắt các hình thái địa hình.2 Tham số cho các địa hình.3 Tiêu chí đánh giá.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 .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 .6 Kết quả thu được trên các tập dữ liệu Type 1s, Type 2s, Type 3s.7 Kết quả thu được trên các tập dữ liệu Type 1l, Type 2l, Type 3l.8 Kết quả thu được trên các tập dữ liệu Type 3s, Type 4s, Type 5s.9 Kết quả thu được trên các tập dữ liệu Type 3l, Type 4l, Type 5l.10 Tham số thuật toán MOEA-LS .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 δ .12 So sánh các thuật toán tiến hóa đa mục tiêu dựa trên độ đo ∆.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 .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 .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 .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).17 So sánh thuật toán MOEA-LS và thuật toán FCLS dựa trên độ đo S .18 Độ phức tạp của các thuật toán đa mục tiêu.19 Tham số cho bài toán RSS và RSM.20 Các bộ dữ liệu cho bài toán RSM.21 Các bộ dữ liệu cho bài toán RSS.22 Các tiêu chí đánh giá .23 Tham số cho các thuật toán .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.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.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.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.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.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ế.2 Minh họa không gian thiết kế và không gian mục tiêu.3 Ví dụ về tối ưu Pareto và tối ưu Pareto yếu.4 Sơ đồ khối của thuật toán di truyền.5 Minh họa việc sắp xếp không trội .6 Ma trận trội.7 Minh họa khoảng cách quy tụ .8 Minh họa việc lựa chọn các cá thể để đưa vào quần thể Pt+1 .9 Minh họa cách tiếp cận dựa trên biên .10 Minh họa độ đo HV cho bài toán tối ưu hai mục tiêu.11 Truyền thông trong mạng cảm biến không dây ngầm.1 Minh họa cho hàm Genitor với bias = 2.2 Minh họa thuật toán BGS.3 Biểu diễn cá thể.4 Ví dụ của đồ thị G với khả năng thông qua .5 Minh họa toán tử lai ghép của thuật toán MXFGA.6 Minh họa toán tử đột biến của thuật toán MXFGA.7 Đánh giá ảnh hưởng của tỉ lệ khởi tạo.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.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.