Luận án Một số thuật toán metaheuristic giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây

Tên luận án:

MỘT SỐ THUẬT TOÁN METAHEURISTIC GIẢI BÀI TOÁN BAO PHỦ DIỆN TÍCH VÀ ĐỐI TƯỢNG TRONG MẠNG CẢM BIẾN KHÔNG DÂY

Ngành:

Khoa học máy tính

Tóm tắt nội dung tài liệu:

Luận án tiến sĩ của Nguyễn Thị Hạnh, được bảo vệ tại Trường Đại học Bách khoa Hà Nội vào năm 2019, tập trung nghiên cứu và phát triển các thuật toán metaheuristic để giải quyết các bài toán bao phủ diện tích và đối tượng trong Mạng cảm biến không dây (WSNs). Nhận thức tầm quan trọng của WSNs đối với Internet vạn vật (IoT) và những thách thức cố hữu như năng lượng hạn chế, môi trường khắc nghiệt, khả năng mở rộng, chi phí, độ ổn định và bảo mật, luận án hướng tới tối ưu hóa các yếu tố này.

Mục tiêu chính bao gồm nghiên cứu WSNs, đặc biệt là các vấn đề bao phủ, kết nối và chịu lỗi. Cụ thể, luận án đi sâu vào việc cực đại hóa diện tích bao phủ trong mạng cảm biến không dây không đồng nhất và tối thiểu hóa số lượng nút triển khai để bao phủ đối tượng, đồng thời đảm bảo kết nối và chịu lỗi, kể cả trong mạng có sử dụng điểm thu phát di động. Các bài toán này được xác định là NP-Khó, do đó luận án tiếp cận bằng cách đề xuất các giải thuật heuristic và metaheuristic.

Các đóng góp chính bao gồm:

• Đề xuất các giải thuật metaheuristic cải tiến (DPSO, ICS, CFPA, MIGA) cho bài toán cực đại diện tích bao phủ trong mạng cảm biến không dây không đồng nhất, mang lại hiệu quả vượt trội về diện tích bao phủ, thời gian tính toán và độ ổn định so với các nghiên cứu trước đó.
• Phát triển mô hình và giải thuật (MIGA, IPSO) cho bài toán cực đại diện tích bao phủ trong mạng cảm biến không dây không đồng nhất có xét đến chướng ngại vật hình chữ nhật, phù hợp hơn với thực tế triển khai mạng.
• Đề xuất hai bài toán về bao phủ đối tượng: bao phủ đối tượng đảm bảo kết nối và chịu lỗi trong mạng cảm biến không dây, và bao phủ đối tượng đảm bảo kết nối trong mạng cảm biến không dây có sử dụng điểm thu phát di động. Luận án cũng đề xuất các giải thuật heuristic (USP, UTSP, PGA, SGA) để giải quyết các bài toán này, đồng thời xây dựng các kịch bản thực nghiệm để đánh giá ảnh hưởng của các yếu tố đầu vào.

Phương pháp nghiên cứu kết hợp lý thuyết, mô hình toán học và thực nghiệm để đánh giá các giải thuật đề xuất. Các kết quả nghiên cứu đã được công bố trên các tạp chí và hội nghị khoa học uy tín, góp phần nâng cao hiệu quả và tính ứng dụng của WSNs.

Mục lục chi tiết:

• Mở đầu

  Trình bày ý nghĩa, mục đích nghiên cứu của luận án, phương pháp nghiên cứu, phạm vi nghiên cứu, các đóng góp của luận án và cấu trúc của luận án.

• CHƯƠNG 1. CƠ SỞ LÝ THUYẾT

  • 1.1. Mạng cảm biến không dây
  • 1.2. Các mô hình bao phủ của cảm biến và mạng cảm biến không dây
  • 1.2.1. Mô hình bao phủ của cảm biến
  • 1.2.2. Bài toán bao phủ trong mạng cảm biến không dây
  • 1.4. Bài toán tối ưu
  • 1.5. Kết luận chương

• CHƯƠNG 2. BÀI TOÁN CỰC ĐẠI DIỆN TÍCH BAO PHỦ TRONG MẠNG CẢM BIẾN KHÔNG DÂY KHÔNG ĐỒNG NHẤT

  • 2.1. Phát biểu bài toán
  • 2.2. Giải thuật đề xuất
  • 2.2.1. Giải thuật tìm kiếm chim cuckoo cải tiến
  • 2.2.2. Giải thuật Democratic PSO
  • 2.2.3. Giải thuật thụ phấn cho hoa hỗn tạp
  • 2.2.4. Giải thuật di truyền cải tiến
  • 2.3. Kết quả thực nghiệm
  • 2.3.1. Dữ liệu thực nghiệm
  • 2.3.2. Tham số thực nghiệm
  • 2.4. Kết luận chương.

• CHƯƠNG 3. BÀI TOÁN CỰC ĐẠI DIỆN TÍCH BAO PHỦ TRONG MẠNG CẢM BIẾN KHÔNG DÂY KHÔNG ĐỒNG NHẤT CÓ RÀNG BUỘC CHƯỚNG NGẠI VẬT

  • 3.1. Phát biểu bài toán
  • 3.2. Giải thuật đề xuất
  • 3.2.1. Giải thuật di truyền cải tiến
  • 3.2.2. Giải thuật tối ưu hóa bầy đàn cải tiến
  • 3.3. Kết quả thực nghiệm
  • 3.3.1. Kịch bản thực nghiệm
  • 3.3.2. Tham số thực nghiệm
  • 3.3.3. So sánh đánh giá kết quả thực nghiệm
  • 3.4. Kết luận chương

• CHƯƠNG 4. BÀI TOÁN BAO PHỦ ĐỐI TƯỢNG ĐẢM BẢO KẾT NỐI VÀ CHỊU LỖI TRONG MẠNG CẢM BIẾN KHÔNG DÂY VÀ MẠNG CẢM BIẾN KHÔNG DÂY CÓ SỬ DỤNG ĐIỂM THU PHÁT DI ĐỘNG

  • 4.1 Bài toán bao phủ đối tượng đảm bảo kết nối và chịu lỗi trong mạng cảm biến không dây.
  • 4.1.1. Phát biểu bài toán
  • 4.1.2. Giải thuật đề xuất
  • 4.1.3. Kết quả thực nghiệm
  • 4.2. Bài toán bao phủ đối tượng đảm bảo kết nối trong mạng cảm biến không dây có sử dụng các điểm thu phát di động
  • 4.2.1. Phát biểu bài toán
  • 4.2.2. Giải thuật đề xuất
  • 4.2.3. Kết quả thực nghiệm

• KẾT LUẬN CHUNG

  Các đóng góp mới

  Hướng nghiên cứu tiếp