Luận án tiến sĩ nghiên cứu phát triển một số thuật toán tối ưu hóa vùng phủ sóng

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------------------- Đặng Thanh Hải NGHIÊN CỨU PHÁT TRIỂN MỘT SỐ THUẬT TOÁN TỐI ƯU HÓA VÙNG PHỦ SÓNG VÀ NĂNG LƯỢNG CỦA MẠNG CẢM BIẾN KHÔNG DÂY TRONG MÔI TRƯỜNG 3 CHIỀU LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội, 2017 TIEU LUAN MOI download : skknchat@gmail.com ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------------------- Đặng Thanh Hải NGHIÊN CỨU PHÁT TRIỂN MỘT SỐ THUẬT TOÁN TỐI ƯU HÓA VÙNG PHỦ SÓNG VÀ NĂNG LƯỢNG CỦA MẠNG CẢM BIẾN KHÔNG DÂY TRONG MÔI TRƯỜNG 3 CHIỀU Chuyên ngành: Cơ sở toán cho tin học Mã số: 62460110 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. Lê Trọng Vĩnh 2. Lê Hoàng Sơn Hà Nội, 2017 TIEU LUAN MOI download : skknchat@gmail.com 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 chính mình 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 thông tin 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 từng đƣợ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. Nghiên cứu sinh Đặng Thanh Hải i TIEU LUAN MOI download : skknchat@gmail.com LỜI CẢM ƠN Lời đầu tiên, nghiên cứu sinh xin bày tỏ lòng biết ơn sâu sắc tới các thầy giáo hƣớng dẫn, PGS. Lê Trọng Vĩnh và TS. Lê Hoàng Sơn, đã định hƣớng khoa học và tận tâm giúp đỡ, chỉ bảo trong suốt quá trình hoàn thành luận án này tại trƣờng Đại học Khoa học Tự nhiên - Đại học Quốc gia Hà Nội.

Nghiên cứu sinh chân thành cảm ơn các nhà khoa học, tác giả các công trình nghiên cứu đƣợc trích dẫn, tham khảo trong luận án này, đây là những kiến thức cơ sở để Nghiên cứu sinh phát triển và hoàn thiện các công bố của mình. Nghiên cứu sinh xin chân thành cảm ơn Ban giám hiệu, lãnh đạo Khoa Toán- Cơ- Tin, các thầy cô giảng viên, đồng nghiệp Bộ môn Tin học, Trung tâm tính toán hiện năng cao, 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 thuận lợi nhất để nghiên cứu sinh hoàn thành chƣơng trình học tập và thực hiện luận án nghiên cứu khoa học của mình. Nghiên cứu sinh xin chân thành cảm ơn Ban giám hiệu trƣờng Đại học Đà Lạt, tập thể cán bộ, giảng viên Khoa Công nghệ Thông tin nơi nghiên cứu sinh công tác và các bạn bè thân thiết đã luôn tạo điều kiện, động viên, khuyến khích để Nghiên cứu sinh hoàn thành luận án này. Cuối cùng, nghiên cứu sinh chân thành bày tỏ lòng cảm ơn tới gia đình đã kiên trì, chia sẻ, động viên nghiên cứu sinh trong suốt quá trình học tập và hoàn thành luận án này.

Nghiên cứu sinh Đặng Thanh Hải ii TIEU LUAN MOI download : skknchat@gmail.com MỤC LỤC 0 MỞ ĐẦU. TỔNG QUAN MẠNG CẢM BIẾN KHÔNG DÂY. Mạng cảm biến không dây. Cấu trúc nút cảm biến.

Cấu trúc mạng cảm biến không dây. Mạng cảm biến trong môi trƣờng 3 chiều. Hố mạng và vật cản. Hai bài toán quan trọng trong mạng cảm biến không dây và các nghiên cứu liên quan.

Bài toán tối ƣu phủ sóng. Bài toán tối ƣu năng lƣợng mạng. Kết luận chƣơng. TỐI ƢU VÙNG PHỦ SÓNG MẠNG CẢM BIẾN KHÔNG DÂY TRÊN ĐỊA HÌNH 3 CHIỀU.

Đề xuất mô hình mạng cảm biến trong môi trƣờng 3 chiều. Bài toán tối ƣu vùng phủ sóng trong môi trƣờng 3 chiều. Nội suy độ cao của một điểm trong địa hình. Phƣơng pháp xác định vật cản LoS cải tiến.

Xác định hố mạng vật lý cho mô hình. Thuật toán PSO cho bài toán tối ƣu vùng phủ sóng trong môi trƣờng 3 chiều. Sơ lƣợc về tối ƣu tiến hóa và thuật toán tối ƣu bầy đàn. Thuật toán PSO cho bài toán tối ƣu hóavùng phủ sóng.

Đánh giá độ phức tạp của thuật toán PSO_3WSN. Kết quả thực nghiệm. Đánh giá thuật toán xác định hố mạng vật lý. Đánh giá thuật toán tối ƣu phủ sóng PSO_3WSN.

Kết luận chƣơng. 57 iii TIEU LUAN MOI download : skknchat@gmail.com 3 CHƢƠNG 3. TỐI ƢU NĂNG LƢỢNG MẠNG CẢM BIẾN KHÔNG DÂY TRÊN ĐỊA HÌNH 3 CHIỀU. Mô hình hóa việc tiêu thụ năng lƣợng cho mạng cảm biến trong môi trƣờng 3 chiều.

Bài toán tối ƣu hóa năng lƣợng cho mạng cảm biến trong môi trƣờng 3 chiều. Thiết kế giải pháp tối ƣu năng lƣợng mạng cảm biến. Thiết kế giải pháp tối ƣu năng lƣợng kết hợp chọn nút CH. Thiết kế giải pháp tối ƣu năng lƣợng kết hợp cân bằng năng lƣợng.

Thuật toán FCM- PSOEB. Kết quả và đánh giá thực nghiệm. Môi trƣờng thực nghiệm. Đánh giá giải pháp tối ƣu năng lƣợng bằng phân cụm mờ.

Đánh giá giải pháp tối ƣu năng lƣợng kết hợp lựa chọn nút chủ. Đánh giá giải pháp tối ƣu năng lƣợng kết hợp cân bằng năng lƣợng. Kết luận chƣơng. 84 4 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN.

85 5 DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN. 87 6 TÀI LIỆU THAM KHẢO. 99 iv TIEU LUAN MOI download : skknchat@gmail.com DANH MỤC BẢNG Bảng 1-1. Phân loại cảm biến theo khả năng cảm nhận.

Thuật toán LEACH. Thuật toán LEACH-C. Thuật toán phân cụm dùng K-Means. Thuật toán FCM.

Thuật toán LoS cải tiến. Thuật toán xác định hố mạng vật lý. Thuật toán PSO. Ứng dụng thuật toán PSO tìm vị trí cảm biến tối ƣu.

Hàm tính giá trị thích nghi. Kết quả thực nghiệm thuật toán phát hiện hố mạng vật lý. Kết quả thuật toán phát hiện hố mạng vật lý với κ=370. Kết quả thuật toán phát hiện hố mạng vật lý với ∆=6.

Mô tả các tham số đầu vào. Khả năng phủ sóng của thuật toán. Khả năng phủ sóng của thuật toán với các phân phối khác nhau. Khả năng phủ sóng của thuật toán với các tham số PSO khác nhau.

Khả năng phủ sóng của thuật toán với tỉ lệ điểm lƣới lấy mẫu khác nhau. Thuật toán FCM cải tiến gọi FCM-3WSN. Thuật toán PSO chọn CH gọi là FCM-PSO. Thuật toán cân bằng năng lƣợng giữa các cụm FCM-PSOEB.

Các tham số của thuật toán. Năng lƣợng tiêu thụ của mạng với các thuật toán khác nhau (joule). Thời gian chạy của thuật toán. Thời gian chạy trung bình của các thuật toán với số cảm biến khác nhau.

Thời gian chạy trung bình của các thuật toán với các phân phối cảm biến. Thời gian chạy trung bình các thuật toán với số cụm khác nhau. Tỉ lệ kết nối giữa các CH và BS với số cụm 20% số cảm biến. Tỉ lệ kết nối giữa các non-CH và CH với số cụm 20% số cảm biến.

Năng lƣợng tiêu thụ mạng với các thuật toán. Mô tả tóm tắt hình thái của các địa hình. 100 v TIEU LUAN MOI download : skknchat@gmail.com DANH MỤC HÌNH VẼ VÀ ĐỒ THỊ Hình 1-1. Mạng cảm biến không dây.

Các thành phần cơ bản của nút cảm biến. Mô hình cấu trúc hình sao. Mô hình cấu trúc phân cấp. Mô hình cấu trúc tập trung.

Hai mô hình DEM thông dụng. Cách xác định vật cản trong địa hình. Tối ƣu phủ sóng dùng sơ đồ Voronoi. Tối ƣu phủ sóng dùng hình học mẫu.

Mô hình cảm biến trong môi trƣờng 3 chiều. Thuật toán Voronoi trong 3 chiều. Tăng vùng phủ sóng bằng cách chỉnh hƣớng và góc. Mô hình cảm biến với vật cản.

Mô hình cảm biến với khái niệm tầm nhìn. Biểu diễn các góc của cảm biến trong môi trƣờng 3 chiều. Đại diện hố mạng trong địa hình. Xác định hố mạng vật lý.

Hố mạng vậy lý đƣợc phát hiện trên một số địa hình. Các phân phối điểm lƣới lấy mẫu trong địa hình. Khả năng phủ sóng với các phân bố khác nhau. Khả năng phủ sóng với các bộ tham số khác nhau thuật toán PSO.

Khả năng phủ sóng với tỉ lệ điểm lƣới lấy mẫu khác nhau. Lƣu đồ giải pháp xây dựng topo WSN tối ƣu năng lƣợng. Phân phối các cảm biến. Năng lƣợng tiêu thụ trung bình với các số cảm biến khác nhau (joule).

Năng lƣợng tiêu thụ trung bình với các phân phối cảm biến khác nhau(joule). Năng lƣợng tiêu thụ trung bình với số cụm khác nhau(joule). Tỉ lệ phần trăm CH kết nối tới BS với số cảm biến khác nhau. Tỉ lệ phần trăm non-CH kết nối tới CH với số cảm biến khác nhau.

Tỉ lệ phần trăm CH kết nối tới BS với các phân phối khác nhau. 79 vi TIEU LUAN MOI download : skknchat@gmail. Tỉ lệ phần trăm non-CH kết nối tới CH với các phân phối khác nhau. Tỉ lệ phần trăm non-CH kết nối tới CH với các phân phối khác nhau.

Năng lƣợng tiêu thụ của mạng bởi các thuật toán(joule). Giá trị trung bình tỉ lệ các kết nối. Minh họa các địa hình DEM của Việt Nam. 99 vii TIEU LUAN MOI download : skknchat@gmail.com DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT STT Viết tắt Tiếng Anh Tiếng Việt 1 ACO Ant Colony Optimization Thuật toán tối ƣu đàn kiến 2 AHP Analytical Hierarchy Process Quá trình phân tích phân cấp 3 APTEEN Adaptive Periodic Threshold Giao thức hiệu quả năng Energy Efficient Sensor Network lƣợng thích ứng ngƣỡng Protocol cảm biến 4 BS Base Station Trạm cơ sở 5 BSDCP Base-Station Controlled Dynamic Giao thức phân cụm động Clustering các BS Protocol 6 CH Cluster Head Nút chủ 7 DEM Digital Elevation Model Mô hình độ cao số 8 DHAC Distributed Hierarchical Kỹ thuật phân cụm tích lũy Agglomerative Clustering phân cấp phân tán 9 DWEHC distributed weight-based energy- Giao thức phân cụm phân efficient hierarchical clustering cấp hiệu quả năng lƣợng protocol dựa trên trọng số 10 EB Energy balance Cân bằng năng lƣợng 11 EEDC Energy efficient Dynamic Clustering Phân cụm động hiệu quả năng lƣợng 12 EELBC Energy Efficiency Load-Balancing Phân cụm cân bằng năng clustering lƣợng hiệu quả năng lƣợng 13 EEMS Energy-efficient multi-level Thuật toán phân cụm đa cấp clustering algorithm hiệu quả năng lƣợng 14 FCM Fuzzy C-Means Phân cụm mờ 15 GPS Global Positioning System Hệ thống định vị toàn cầu 16 HAC Hierarchical Agglomerative Phân cụm tích lũy phân cấp Clustering 17 H-DHAC Hybrid Distributed Hierarchical Kỹ thuật phân cụm tích lũy Agglomerative Clustering phân cấp phân tán lai viii TIEU LUAN MOI download : skknchat@gmail.