Tài liệu 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

ĐẠ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 ĐẠ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: Mã số: Cơ sở toán cho tin học 62460110 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. PGS.TS. Lê Trọng Vĩnh 2. TS. Lê Hoàng Sơn Hà Nội, 2017 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 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.TS. 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ánCơ- 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 MỤC LỤC 0 MỞ ĐẦU ............................................................................................................................ 1 1 CHƢƠNG 1. TỔNG QUAN MẠNG CẢM BIẾN KHÔNG DÂY.................................... 5 1.1. Mạng cảm biến không dây .......................................................................................... 5 1.1.1. Khái niệm............................................................................................................. 5 1.1.2. Cấu trúc nút cảm biến .......................................................................................... 5 1.1.3. Cấu trúc mạng cảm biến không dây .................................................................... 8 1.1.4. Mạng cảm biến trong môi trƣờng 3 chiều ......................................................... 10 1.1.5. Hố mạng và vật cản ........................................................................................... 11 1.2. 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........................................................................................................................... 14 1.2.1. Bài toán tối ƣu phủ sóng .................................................................................... 14 1.2.2. Bài toán tối ƣu năng lƣợng mạng ...................................................................... 20 1.3. Kết luận chƣơng........................................................................................................ 29 2 CHƢƠNG 2. 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................................................................................................ 30 2.1. Đề xuất mô hình mạng cảm biến trong môi trƣờng 3 chiều ..................................... 30 2.2. Bài toán tối ƣu vùng phủ sóng trong môi trƣờng 3 chiều ......................................... 35 2.2.1. Nội suy độ cao của một điểm trong địa hình ..................................................... 35 2.2.2. Phƣơng pháp xác định vật cản LoS cải tiến ....................................................... 36 2.2.3. Xác định hố mạng vật lý cho mô hình ............................................................... 38 2.3. 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 ........ 40 2.3.1. Sơ lƣợc về tối ƣu tiến hóa và thuật toán tối ƣu bầy đàn .................................... 40 2.3.2. Thuật toán PSO cho bài toán tối ƣu hóavùng phủ sóng .................................... 43 2.4. Đánh giá độ phức tạp của thuật toán PSO_3WSN ................................................... 46 2.5. Kết quả thực nghiệm ................................................................................................. 46 2.5.1. Đánh giá thuật toán xác định hố mạng vật lý .................................................... 46 2.5.2. Đánh giá thuật toán tối ƣu phủ sóng PSO_3WSN ............................................. 49 2.6. Kết luận chƣơng........................................................................................................ 57 iii 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................................................................................................ 58 3.1. 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 .............................................................................................................................. 59 3.2. 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 ....... 63 3.3. Thiết kế giải pháp tối ƣu năng lƣợng mạng cảm biến .............................................. 63 3.3.1. Ý tƣởng .............................................................................................................. 63 3.3.2. Thuật toán .......................................................................................................... 64 3.4. Thiết kế giải pháp tối ƣu năng lƣợng kết hợp chọn nút CH ..................................... 65 3.4.1. Ý tƣởng .............................................................................................................. 65 3.4.2. Thuật toán .......................................................................................................... 66 3.5. 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 ........................ 67 3.5.1. Ý tƣởng .............................................................................................................. 67 3.5.2. Thuật toán FCM- PSOEB .................................................................................. 68 3.6. Kết quả và đánh giá thực nghiệm ............................................................................. 69 3.6.1. Môi trƣờng thực nghiệm .................................................................................... 69 3.6.2. Đánh giá giải pháp tối ƣu năng lƣợng bằng phân cụm mờ ................................ 69 3.6.3. Đánh giá giải pháp tối ƣu năng lƣợng kết hợp lựa chọn nút chủ ....................... 77 3.6.4. Đá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 ................ 82 3.7. 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 ................................................................................................ 88 7 PHỤ LỤC A ..................................................................................................................... 99 iv 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 ........................................................ 7 Bảng 1-2. Thuật toán LEACH ............................................................................................. 22 Bảng 1-3. Thuật toán LEACH-C ......................................................................................... 24 Bảng 1-4. Thuật toán phân cụm dùng K-Means .................................................................. 26 Bảng 1-5. Thuật toán FCM .................................................................................................. 27 Bảng 2-1. Thuật toán LoS cải tiến ....................................................................................... 37 Bảng 2-2. Thuật toán xác định hố mạng vật lý .................................................................... 39 Bảng 2-3. Thuật toán PSO ................................................................................................... 42 Bảng 2-4. Ứng dụng thuật toán PSO tìm vị trí cảm biến tối ƣu .......................................... 44 Bảng 2-5. Hàm tính giá trị thích nghi .................................................................................. 45 Bảng 2-6. Kết quả thực nghiệm thuật toán phát hiện hố mạng vật lý ................................. 47 Bảng 2-7. Kết quả thuật toán phát hiện hố mạng vật lý với κ=370 ..................................... 48 Bảng 2-8. Kết quả thuật toán phát hiện hố mạng vật lý với ∆=6......................................... 49 Bảng 2-9. Mô tả các tham số đầu vào .................................................................................. 50 Bảng 2-10. Khả năng phủ sóng của thuật toán .................................................................... 52 Bảng 2-11. Khả năng phủ sóng của thuật toán với các phân phối khác nhau ..................... 53 Bảng 2-12. Khả năng phủ sóng của thuật toán với các tham số PSO khác nhau ................ 54 Bảng 2-13. 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 ....... 56 Bảng 3-1. Thuật toán FCM cải tiến gọi FCM-3WSN ......................................................... 64 Bảng 3-2. Thuật toán PSO chọn CH gọi là FCM-PSO........................................................ 66 Bảng 3-3. Thuật toán cân bằng năng lƣợng giữa các cụm FCM-PSOEB ........................... 68 Bảng 3-4. Các tham số của thuật toán ................................................................................. 69 Bảng 3-5. Năng lƣợng tiêu thụ của mạng với các thuật toán khác nhau (joule).................. 71 Bảng 3-6. Thời gian chạy của thuật toán ............................................................................. 71 Bảng 3-7. 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 ......... 74 Bảng 3-8. 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 ........ 76 Bảng 3-9. Thời gian chạy trung bình các thuật toán với số cụm khác nhau ........................ 77 Bảng 3-10. Tỉ lệ kết nối giữa các CH và BS với số cụm 20% số cảm biến ........................ 80 Bảng 3-11. 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 ................ 81 Bảng 3-12. Năng lƣợng tiêu thụ mạng với các thuật toán ................................................... 82 Bảng 7-1. Mô tả tóm tắt hình thái của các địa hình ........................................................... 100 v DANH MỤC HÌNH VẼ VÀ ĐỒ THỊ Hình 1-1. Mạng cảm biến không dây .................................................................................... 5 Hình 1-2. Các thành phần cơ bản của nút cảm biến .............................................................. 7 Hình 1-3. Mô hình cấu trúc hình sao ..................................................................................... 8 Hình 1-4. Mô hình cấu trúc phân cấp .................................................................................... 9 Hình 1-5. Mô hình cấu trúc tập trung .................................................................................. 10 Hình 1-6. Hai mô hình DEM thông dụng ............................................................................ 11 Hình 1-7. Cách xác định vật cản trong địa hình .................................................................. 14 Hình 1-8. Tối ƣu phủ sóng dùng sơ đồ Voronoi .................................................................. 15 Hình 1-9. Tối ƣu phủ sóng dùng hình học mẫu ................................................................... 15 Hình 1-10. Mô hình cảm biến trong môi trƣờng 3 chiều ..................................................... 16 Hình 1-11. Thuật toán Voronoi trong 3 chiều ..................................................................... 17 Hình 1-12. Tăng vùng phủ sóng bằng cách chỉnh hƣớng và góc ........................................ 18 Hình 1-13. Mô hình cảm biến với vật cản ........................................................................... 19 Hình 1-14. Mô hình cảm biến với khái niệm tầm nhìn........................................................ 19 Hình 2-1. Biểu diễn các góc của cảm biến trong môi trƣờng 3 chiều ................................. 31 Hình 2-2. Đại diện hố mạng trong địa hình ......................................................................... 32 Hình 2-3. Xác định hố mạng vật lý...................................................................................... 39 Hình 2-4. Hố mạng vậy lý đƣợc phát hiện trên một số địa hình ......................................... 48 Hình 2-5. Các phân phối điểm lƣới lấy mẫu trong địa hình ................................................ 51 Hình 2-6. Khả năng phủ sóng với các phân bố khác nhau .................................................. 54 Hình 2-7. Khả năng phủ sóng với các bộ tham số khác nhau thuật toán PSO .................... 55 Hình 2-8. Khả năng phủ sóng với tỉ lệ điểm lƣới lấy mẫu khác nhau ................................. 56 Hình 3-1. Lƣu đồ giải pháp xây dựng topo WSN tối ƣu năng lƣợng .................................. 59 Hình 3-2. Phân phối các cảm biến ....................................................................................... 70 Hình 3-3. Năng lƣợng tiêu thụ trung bình với các số cảm biến khác nhau (joule).............. 72 Hình 3-4. 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) .. 74 Hình 3-5. Năng lƣợng tiêu thụ trung bình với số cụm khác nhau(joule)............................. 76 Hình 3-6. Tỉ lệ phần trăm CH kết nối tới BS với số cảm biến khác nhau ........................... 78 Hình 3-7. 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 .................. 78 Hình 3-8. 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 Hình 3-9. 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 ............... 79 Hình 3-10. 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 ............. 79 Hình 3-11. Năng lƣợng tiêu thụ của mạng bởi các thuật toán(joule) .................................. 83 Hình 3-12. Giá trị trung bình tỉ lệ các kết nối ...................................................................... 83 Hình 7-1. Minh họa các địa hình DEM của Việt Nam ........................................................ 99 vii 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 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ố Cân bằng năng lƣợng 9 DWEHC 10 EB Energy balance 11 EEDC Energy efficient Dynamic Clustering Phân cụm động hiệu quả năng lƣợng 12 13 EELBC EEMS Energy Efficiency Load-Balancing Phân cụm cân bằng năng clustering lƣợng hiệu quả năng lƣợng 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 18 19 20 HEED H-LEACH LACBER Hybrid Energy-Efficient Distributed Phân cụm phân tán lai với Clustering hiệu quả năng lƣợng Hybrid-Low Energy Adaptive Phân cụm phân cấp thích ứng Clustering Hierarchy năng lƣợng thấp Location Aided Cluster Based Định tuyến hiệu quả dựa vào Energy Efficient Routing phân cụm vị trí 21 LCA Linked Cluster Algorithm Thuật toán phân cụm liên kết 22 LEACH Low Energy Adaptive Clustering Giao thức LEACH tập trung Hierarchy 23 LEACH-C Centralized LEACH Phân cụm tập trung 24 LoS Line-of-Sight Tầm nhìn 25 non-CH None Cluster Head Nút thành viên trong cụm 26 PBO Pollination Based Optimization Tối ƣu hóa thụ phấn 27 PEGASIS Power-Efficient Gathering in Sensor Một giao thức tập trung năng Information Systems lƣợng hiệu quả trong các hệ thống thông tin cảm biến 28 PSO Particle Swarm Optimization Thuật toán tối ƣu bầy đàn 29 SCEEP Single-hop Clustering and Energy Phân cụm mạng đơn bƣớc Efficient Protocol nhảy và hiệu quả năng lƣợng Sensor Protocol for Information via Giao thức định tuyến Negotiation thông tin dựa trên sự dàn xếp 30 SPIN dữ liệu 31 32 TCCA TEEN Time controlled Clustering Thuật toán phân cụm theo algorithm thời gian Threshold sensitive Energy Efficient Giao thức hiệu quả năng sensor Network protocol lƣợng với ngƣỡng cảm biến 33 Topo Topology Cấu trúc liên kết mạng 34 VEC Vector-Based Thuật toán dựa trên Vector 35 VOR Voronoi-Based Thuật toán dựa trên đa giác Voronoi 36 WSN Wireless Sensor Networks ix Mạng cảm biến không dây 0 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ệ, việc nghiên cứu mạng không dây đƣợc nhiều nhà khoa học tập trung nghiên cứu. Đặc biệt, mạng cảm biến không dây đang đƣợc nghiên cứu mạnh mẽ và đƣợc triển khai trong nhiều lĩnh vực khác nhau của đời sống. Các ứng dụng điển hình đƣợc triển khai nhƣ: nhà thông minh, thành phố thông minh; trong công nghiệp ứng dụng vào: các hệ thống giám sát máy móc, phát hiện lỗi trong các nhà máy cho đến các ứng dụng trong quân sự, y tế, nông nghiệp công nghệ cao, giao thông. Ngoài ra còn có các ứng mạng cảm biến không thể thiếu trong một xã hội phát triển nhƣ: theo dõi biến đổi môi trƣờng, dự báo thiên tai nhƣ các hệ thống dự báo lũ lụt, núi lửa, động đất, cháy rừng, v.v.[6, 46]. Trong tƣơng lai không xa các ứng dụng mạng cảm biến không dây sẽ trở thành một phần không thể thiếu trong cuộc sống của con ngƣời. Tuy nhiên, khi nghiên cứu về mạng cảm biến không dây gặp rất nhiều thách thức. Đặc biệt nghiên cứu triển khai mạng cảm biến không dây trong môi trƣờng 3 chiều đạt hiệu quả. Điều này có nghĩa là khi triển khai mạng cảm biến thì phải hiệu quả về khả năng phủ sóng khu vực mục tiêu. Sau đó cần phải xây dựng cấu trúc mạng để mạng cảm biến tiết kiệm năng lƣợng và kéo dài tuổi thọ trong môi trƣờng 3 chiều. Bài toán triển khai mạng cảm biến không dây nhằm mục đích xác định vị trí các cảm biến trong môi trƣờng để đạt đƣợc mục tiêu đề ra của mạng. Thông thƣờng, các nhà nghiên cứu giả thiết môi trƣờng triển khai mạng cảm biến không dây tƣơng đối tốt. Tuy nhiên, trong thực tế mạng cảm biến không dây đƣợc triển khai trong nhiều môi trƣờng đa dạng thậm chí con ngƣời không tiếp cận trực tiếp đƣợc nhƣ khu vực thiên tai, nhiễm hóa chất độc hại, v.v.[54]. Hơn thế nữa trong môi trƣờng luôn tồn tại hố mạng, nơi chúng ta không thể đặt cảm biến vào đƣợc hoặc đặt đƣợc cảm biến nhƣng chúng không thể phủ sóng cảm biến đƣợc do có vật cản che khuất vùng cần phủ sóng. Việc triển khai tốt một mạng cảm biến không dây giúp cho hệ thống mạng cảm biến có thể phủ sóng tối đa khu vực mục tiêu, đây là mục tiêu mà các nhà nghiên cứu mong muốn đạt đƣợc [75]. 1 Bài toán xây dựng cấu trúc mạng cảm biến không dây rất quan trọng, nó ảnh hƣởng đến tuổi thọ của mạng. Các cảm biến thông thƣờng sử dụng nguồn năng lƣợng là pin nên hạn chế về năng lƣợng. Trong mạng cảm biến, việc tiêu thụ năng lƣợng chủ yếu cho các hoạt động thu thập thông tin từ môi trƣờng, việc tổng hợp, truyền thông tin về trung tâm xử lý. Nhƣ vậy, một mạng cảm biến không dây đạt hiệu quả thì thời gian tồn tại của chúng trong khu vực mục tiêu phải lâu nhất và việc xây dựng cấu trúc mạng cảm biến sẽ ảnh hƣởng đến tuổi thọ của mạng [86]. Trên cơ sở đó, nghiên cứu sinh chọn đề tà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‖ làm đề tài nghiên cứu cho luận án Tiến sĩ của mình. Luận án hƣớng đến các mục tiêu sau: 1. Đề xuất mô hình toán học cho địa hình và mạng cảm biến không dây trong môi trƣờng 3 chiều. 2. Đề xuất thuật toán tối ƣu hóa vùng phủ sóng của mạng cảm biến không dây trong môi trƣờng 3 chiều. 3. Đề xuất thuật toán tối ƣu hóa năng lƣợng tiêu thụ, kéo dài tuổi của mạng cảm biến không dây trong môi trƣờng 3 chiều. Từ các mục tiêu nghiên cứu trên, luận án đƣợc cấu trúc bao gồm 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 3 chƣơng nhƣ sau: Chƣơng 1 ―Tổng quan mạng cảm biến không dây‖ sẽ trình bày các khái niệm, đặc điểm và các vấn đề mạng cảm biến không dây trong môi trƣờng 3 chiều; phát biểu bài toán tối ƣu hóa vùng phủ sóng, và tối ƣu hóa năng lƣợng tiêu thụ của mạng cảm biến không dây. Chƣơng 2 ―Tối ƣu vùng phủ sóng mạng cảm biến không dây trong môi trƣờng 3 chiều‖ sẽ đề xuất mô hình địa hình với các hố mạng, vật cản cùng mô hình mạng cảm biến trong môi trƣờng 3 chiều, đề xuất phƣơng pháp xác định hố mạng, phƣơng pháp tối ƣu hóa vùng phủ sóng của mạng cảm biến không dây và cuối cùng là phần đánh giá hiệu năng mạng. Kết quả chính đã đƣợc công bố trong các công trình 1, 3. 2 Chƣơng 3 ―Tối ƣu năng lƣợng tiêu thụ mạng cảm biến không dây trong môi trƣờng 3 chiều‖ trình bày mô hình năng lƣợng tiêu thụ của mạng cảm biến; đề xuất giải pháp xây dựng cấu trúc mạng cảm biến không dây trong môi trƣờng 3 chiều dựa trên phƣơng pháp phân cụm mờ với mục tiêu giảm thiểu năng lƣợng tiêu thụ và kéo dài thời gian sống của mạng cảm biến. Cuối cùng kết quả thực nghiệm đƣợc phân tích đánh giá để khẳng định tính hiệu quả của giải pháp đề xuất. Kết quả chính đã đƣợc công bố trong các công trình 2, 4, 5, 6. Đối tƣợng và phƣơng pháp nghiên cứu Trên cơ sở mục tiêu luận án, nghiên cứu sinh dựa trên các công cụ toán học để mô hình hóa các địa hình, mạng cảm biến không dây, năng lƣợng tiêu thụ của mạng cảm biến trong môi trƣờng 3 chiều. Nghiên cứu phát triển thuật toán tối ƣu bầy đàn cho bài toán tối ƣu hóa vùng phủ sóng của mạng cảm biến không dây; thuật toán phân cụm mờ cho bài toán xây dựng cấu trúc của mạng cảm biến không dây nhằm tiết kiệm năng lƣợng tiêu thụ, kéo dài tuổi thọ mạng cảm biến. Phƣơng pháp thực nghiệm đƣợc thực hiện trên nhiều bộ dữ liệu khác nhau, các phân bố và số lƣợng cảm biến khác nhau, các tham số đầu vào của các thuật toán để đánh giá tính hiệu quả và ổn định của giải pháp đề xuất. Ý nghĩa về khoa học và thực tiễn của luận án - Ý nghĩa về khoa học o Mô hình hóa toán học cho mạng cảm biến không dây trong môi trƣờng 3 chiều và địa hình phức tạp trong thực tế. o Nghiên cứu phát triển thuật toán tối ƣu bầy đàn cho phép triển khai mạng cảm biến với khả năng phủ sóng tối đa khu vực mục tiêu. o Nghiên cứu phát triển thuật toán phân cụm mờ, cân bằng năng lƣợng giữa các cụm nhằm tối ƣu năng lƣợng tiêu thụ của toàn mạng, kéo dài tuổi thọ của mạng cảm biến trong môi trƣờng 3 chiều. 3 - Ý nghĩa thực tiễn o Bộ dữ liệu địa hình trong môi trƣờng 3 chiều đƣợc thu thập từ các vùng miền khác nhau của Việt Nam. Kết quả thực nghiệm đánh giá đƣợc tính hiệu quả của mô hình và các giải pháp đã đề xuất. o Kết quả nghiên cứu có thể đƣợc dùng để triển khai một mạng cảm biến không dây trên địa hình phức tạp trong môi trƣờng 3 chiều với khả năng tối đa phủ sóng khu vực mục tiêu và kéo dài tuổi thọ của mạng cảm biến. 4 1 CHƢƠNG 1. TỔNG QUAN MẠNG CẢM BIẾN KHÔNG DÂY 1.1. Mạng cảm biến không dây 1.1.1 Khái niệm Mạng cảm biến không dây (Wireless Sensor Networks - WSN) bao gồm nhiều nút cảm biến đƣợc triển khai trong một vùng địa hình nào đó gọi là khu vực mục tiêu. Các cảm biến trong mạng đƣợc nối kết và trao đổi dữ liệu với nhau bằng sóng vô tuyến; chúng có nhiệm vụ thu thập các thông tin từ môi trƣờng. Các thông tin này đƣợc định tuyến đến trạm cơ sở (Base Station - BS) một cách trực tiếp hay gián tiếp thông qua các nút cảm biến lân cận. Tại trạm cơ sở các thông tin thu thập đƣợc phân tích, xử lý để đƣa ra các quyết định bởi ngƣời sử dụng nhƣ Hình 1-1[6]. Hình 1-1 Mạng cảm biến không dây 1.1.2 Cấu trúc nút cảm biến Mỗi nút cảm biến đƣợc cấu thành bởi 4 thành phần cơ bản: đơn vị cảm biến, đơn vị xử lý, đơn vị truyền dẫn và bộ nguồn nhƣ Hình 1-2. Ngoài ra, các cảm biến có thể có thêm thành phần khác nhƣ hệ thống định vị, bộ phận di động tùy thuộc vào các ứng dụng khác nhau [6]. 5 Đơn vị cảm biến bao gồm các cảm biến và bộ chuyển đổi tín hiệu số ADC. Các thông tin thu thập đƣợc bởi các cảm biến từ môi trƣờng ở tín hiệu tƣơng tự sẽ đƣợc chuyển sang tín hiệu số bởi ADC. Cuối cùng tín hiệu số đƣợc chuyển đến cho đơn vị xử lý. Đơn vị xử lý bao gồm bộ xử lý và bộ nhớ, có nhiệm vụ thực hiện các chức năng đƣợc cài đặt sẵn để xử lý dữ liệu nhận đƣợc. Đơn vị truyền dẫn là các bộ thu, phát sóng, và có nhiệm vụ phát hoặc thu dữ liệu từ các nút cảm biến khác trong mạng. Hệ thống định vị cung cấp thông tin về vị trí của thiết bị cảm biến trên địa hình và đƣợc bộ xử lý gởi tín hiệu về thông tin vị trí cho hệ thống mạng cảm biến. Bộ phận di động giúp thiết bị cảm biến có thể di chuyển đến các vị trí xác định đƣợc điều khiển bởi đơn vị xử lý khi cần thiết. Bộ nguồn có nhiệm vụ cung cấp năng lƣợng cho tất cả các thành phần của nút cảm biến. Do các cảm biến kết nối vào hệ thống mạng bằng sóng vô tuyến nên thông thƣờng bộ nguồn sử dụng pin. Khác với các loại mạng truyền thống, trong mạng cảm biến không dây, mỗi nút cảm biến có kích thƣớc nhỏ, có khả năng về năng lƣợng, tính toán, bộ nhớ hạn chế nên cấu trúc mạng thay đổi thƣờng xuyên do các nút cảm biến có thể hết năng lƣợng [6]. Cấu trúc của mạng cảm biến cũng khác với mạng truyền thống và có các đặc điểm sau: - Khả năng chịu lỗi: Mạng vẫn hoạt động bình thƣờng và duy trì những chức năng của nó ngay cả khi một số nút mạng không còn hoạt động. - Khả năng mở rộng: Trong một số ứng dụng, số lƣợng các nút cảm biến đƣợc triển khai có thể rất lớn. Do đó cấu trúc mạng cảm biến không dây có khả năng mở rộng để có thể làm việc với số lƣợng lớn các cảm biến. - Giá thành sản xuất : Do mỗi nút cảm biến có kích thƣớc nhỏ, năng lƣợng ít, nên chi phí sản xuất cảm biến có giá thành thấp. - Môi trƣờng hoạt động: Các nút cảm biến đƣợc triển khai dày đặc và đa dạng môi trƣờng nhƣ những vùng xa xôi, bên trong các máy móc lớn, ở dƣới lòng đại dƣơng, hoặc trong những vùng ô nhiễm hóa học hoặc sinh học, ở gia đình hoặc những tòa nhà lớn. 6 Hình 1-2 Các thành phần cơ bản của nút cảm biến Để phân loại các cảm biến theo khả năng cảm nhận của nó, ngƣời ta thƣờng so sánh thông qua các giác quan của con ngƣời nhƣ trong Bảng 1-1 [82]. Bảng 1-1 Phân loại cảm biến theo khả năng cảm nhận Giác quan Môi trƣờng Thị giác Ánh sáng , hình dạng, kích thƣớc, Cảm biến thu hình, cảm Xúc giác Thiết bị cảm biến vị trí xa gần, màu sắc biến quang Áp suất, nhiệt độ, cơn đau, ẩm, khô Nhiệt trở, cảm biến độ rung động Vị giác Ngọt, mặn, chua cay,… Đo lƣợng đƣờng trong máu Thính giác Sóng âm, âm lƣợng,… Cảm biến sóng siêu âm Khứu giác Mùi của chất khí, chất lỏng Đo độ cồn, thiết bị cảm nhận khí ga Mặc dù có nhiều loại cảm biến nhƣ trên, nhƣng luận án này chỉ quan tâm đến loại cảm biến đầu tiên đó là cảm biến ―thị giác‖. 7 1.1.3 Cấu trúc mạng cảm biến không dây Cấu trúc mạng cảm biến (còn gọi là topo của mạng cảm biến) là cấu trúc hình học thể hiện cách bố trí các cảm biến và hình thức liên kết các cảm biến trong mạng. Thông thƣờng, các nút của một mạng cảm biến không dây thƣờng đƣợc tổ chức thành một trong ba loại cấu trúc liên kết mạng nhƣ sau: cấu trúc hình sao, cấu trúc phân cấp và cấu trúc mạng tập trung. 1.1.3.1 Cấu trúc hình sao Trong cấu trúc hình sao (Hình 1-3) mỗi cảm biến đƣợc kết nối trực tiếp đến trạm cơ sở. Tất cả cảm biến trong mạng đều có vai trò và chức năng nhƣ nhau; các cảm biến cộng tác với nhau để thực hiện nhiệm thu thập thông tin từ môi trƣờng và chuyển về trạm cơ sở. Tuy nhiên, với cấu trúc này các cảm biến tiêu thụ năng lƣợng nhiều hơn do khoảng cách trực tiếp đến trạm cơ sở lớn. Hơn nữa, trạm cơ sở phải nằm trong phạm vi truyền thông của tất cả nút cảm biến trong mạng [30]. Hình 1-3 Mô hình cấu trúc hình sao 1.1.3.2 Cấu trúc phân cấp Trong cấu trúc phân cấp (Hình 1-4) mỗi nút cảm biến kết nối trực tiếp đến một nút ở cấp cao hơn trong cây nếu nhƣ nó nằm trong phạm vi truyền thông. Các nút ở cấp cao hơn sẽ đƣợc kết nối với trạm cơ sở. Đây đƣợc gọi là truyền thông đa hop (multi-hop). Trong cấu trúc này, ƣu điểm là có khả năng mở rộng: nếu nhƣ một nút bị lỗi, các nút ở xa có thể kết nối với các nút khác miễn là nằm trong phạm vi 8 truyền thông để chuyển dữ liệu đến trạm cơ sở. Tuy nhiên, nhƣợc điểm của cấu trúc này là các nút gần trạm cơ sở sẽ tiêu tốn năng lƣợng nhiều hơn do phải chuyển tiếp dữ liệu của các nút ở xa [30]. Hình 1-4 Mô hình cấu trúc phân cấp 1.1.3.3 Cấu trúc tập trung Trong cấu trúc tập trung (Hình 1-5) các cảm biến đƣợc chia thành cụm, trong mỗi cụm có một nút gọi là nút chủ (Cluster Head - CH), các nút còn lại là thành viên của cụm (non-CH) đƣợc kết nối trực tiếp đến nút CH. Các nút non-CH có nhiệm vụ thu thập các thông tin từ môi trƣờng và chuyển đến nút CH khi cần thiết, trong khi đó các nút CH có nhiệm vụ thu thập thông tin từ các non-CH, tổng hợp, phân tích loại bỏ thông tin dƣ thừa và chuyển tiếp đến trạm cơ sở. Trong cấu trúc này, để kéo dài tuổi thọ của mạng các nút trong cụm sẽ thay phiên nhau đóng vai trò nút CH, điều này cân bằng năng lƣợng tiêu thụ giữa tất cả các cảm biến trong cụm. Hơn nữa, việc loại bỏ các thông tin dƣ thừa của các nút CH sẽ làm giảm đáng kể năng lƣợng tiêu thụ và tránh quá tải cho quá trình chuyển dữ liệu đến trạm cơ sở [30]. Trong các cấu trúc liên kết mạng trên, cấu trúc tập trung đƣợc các nhà nghiên cứu quan tâm nhiều nhất. 9