Nội dung

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ DƯ NG VI T HUY TỔNG HỢP DỮ LIỆU NHẰM TI T KIỆM NĂNG LƯỢNG TRONG MẠNG CẢM BI N KHÔNG DÂY LUẬN ÁN TI N S CÔNG NGHỆ THÔNG TIN HÀ NỘI – 2019 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ DƯ NG VI T HUY TỔNG HỢP DỮ LIỆU NHẰM TI T KIỆM NĂNG LƯỢNG TRONG MẠNG CẢM BI N KHÔNG DÂY Chuyên ngành: MẠNG MÁY T NH VÀ TRUYỀN THÔNG DỮ LIỆU Mã số: 9480102.01 LUẬN ÁN TI N S CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. N u Đ HÀ NỘI – 2019 V t LỜI CAM ĐOAN Luận án tiến sỹ của tôi với tên đề tài “Tổng hợp dữ liệu nhằm tiết kiệm năng lượng trong mạng cảm biến không dây” (tiếng Anh: Data fusion for energy efficiency in wireless sensor networks) là kết quả nghiên cứu của cá nhân tôi cùng với sự hƣớng dẫn tận tình của ngƣời hƣớng dẫn khoa học PGS.TS. Nguyễn Đình Việt. Nội dung luận án không sao chép từ các luận án cũng nhƣ công trình nghiên cứu khoa học khác. Các nội dung trích dẫn đƣợc tôi chỉ rõ nguồn tài liệu tham khảo ở trong luận án. Tôi cam đoan những điều trên là đúng sự thật, nếu có gì sai, tôi xin hoàn toàn chịu trách nhiệm. Hà nội, ngày tháng 4 năm 2019 Nghiên cứu sinh Dương Viết Huy MỤC LỤC MỤC LỤC ............................................................................................................................1 ANH MỤC C C THU T NG ....................................................................................4 ANH S CH ẢNG .........................................................................................................5 ANH S CH H NH V ....................................................................................................6 M ĐẦU ..............................................................................................................................8 CHƢƠNG 1. TỔNG QUAN VẤN ĐỀ NGHIÊN CỨU ............................................. 14 1.1. MẠNG CẢM I N KH NG DÂY ........................................................................... 14 1.1.1. Lịch s phát triển......................................................................................... 14 1.1.2. Kiến trúc mạng cảm biến và một số cách ph n loại................................. 17 1.1.2.1. Kiến trúc ................................................................................................ 17 1.1.2.2. Các thành phần chính của WSNs ....................................................... 17 1.1.2.3. Một số cách phân loại mạng................................................................ 18 1.2. CÁC VẤN ĐỀ CẦN GIẢI QUY T............................................................................. 20 1.2.1. Vấn đề tiêu thụ năng lƣợng ......................................................................... 20 1.2.2. Thiết ế no mạng cảm iến ..................................................................... 22 1.2.3. Tổ chức mạng và định tuyến ....................................................................... 22 1.2.4. Truyền và x l ữ liệu................................................................................ 22 1.2.5. Tổng hợp dữ liệu .......................................................................................... 23 1.2.6. X lý vấn đề ữ liệu ƣ thừa....................................................................... 24 1.3. CÔNG CỤ MÔ PHỎNG MẠNG CẢM BI N ............................................................... 25 1.3.1. Bộ mô phỏng NS-2...................................................................................... 25 1.3.2. NS-2 và phần mở rộng mô phỏng WSNs của MIT................................. 26 1.4. MÔ HÌNH TỔNG HỢP D LIỆU VÀ BÀI TOÁN THÀNH PHẦN ................................ 26 1.4.1. Mô hình tổng hợp dữ liệu ............................................................................ 27 1.4.2. Theo dõi mục tiêu và lựa chọn dữ liệu ...................................................... 28 1.4.2.1. Theo dõi mục tiêu dựa vào vị trí của nút ........................................... 29 1.4.2.2. Theo dõi mục tiêu dựa vào thời gian ................................................. 30 1.4.2.3. Lựa chọn dữ liệu và truyền đến CH ................................................... 33 1.4.3. Tổng hợp dữ liệu tại CH .............................................................................. 34 1.4.3.1. Định tuyến phân cụm thích ứng với năng lƣợng thấp ..................... 34 1.4.3.2. Tổng hợp dữ liệu tại nút cụm trƣởng ................................................. 36 1.5. LÝ THUY T T P THÔ ............................................................................................. 38 1.5.1. Các khái niệm về lý thuyết tập thô đƣợc s dụng .................................... 39 1.5.1.1. Hệ thống thông tin ................................................................................ 39 -1- 1.5.1.2. Hệ quyết định ........................................................................................ 39 1.5.1.3. Lớp con tƣơng đƣơng........................................................................... 39 1.5.1.4. Quan hệ không thể phân biệt đƣợc ..................................................... 40 1.5.1.5. Thuộc tính lõi, tập thuộc tính rút gọn................................................. 40 1.5.1.6. Sự phụ thuộc của thuộc tính ................................................................ 41 1.5.1.7. Độ quan trọng của thuộc tính .............................................................. 41 1.5.1.8. Luật quyết định, độ chắc chắn của luật quyết định .......................... 42 1.5.2. Ứng dụng lý thuyết tập thô trong tổng hợp dữ liệu .................................. 42 1.5.3. Ứng dụng để tiền x lý dữ liệu ................................................................... 43 CHƢƠNG 2. THEO ÕI MỤC TIÊU TI T KIỆM NĂNG LƢỢNG ..................... 45 2.1. T HEO ÕI MỤC TI U A VÀO KHOẢNG C CH ................................................ 46 2.1.1. Giới thiệu bài toán ........................................................................................ 46 2.1.2. Giải pháp ETR-DF ....................................................................................... 46 2.1.2.1. Khoảng cách .......................................................................................... 46 2.1.2.2. Sai số ...................................................................................................... 48 2.1.2.3. Vùng ƣu tiên.......................................................................................... 48 2.1.3. Thuật toán ...................................................................................................... 51 2.1.4. Mô phỏng và phân tích kết quả................................................................... 52 2.1.5. Kết luận về giải pháp ETR-DF ................................................................... 57 2.2. T HEO ÕI MỤC TI U TH CH NGHI THEO TH I GIAN .......................................... 58 2.2.1. Giới thiệu bài toán ........................................................................................ 58 2.2.2. Giải pháp ATTS-DF..................................................................................... 59 2.2.2.1. Điểm đo iến động ............................................................................... 59 2.2.2.2. Thời gian đo th ch ứng ......................................................................... 59 2.2.2.3. Ngƣỡng đo ............................................................................................. 60 2.2.2.4. Trạng thái ổn định đo lƣờng ................................................................ 61 2.2.2.5. ự đoán.................................................................................................. 61 2.2.3. Thuật toán ...................................................................................................... 63 2.2.4. Mô phỏng và phân tích kết quả................................................................... 65 2.2.5. Kết luận về giải pháp ATTS-DF................................................................. 69 CHƢƠNG 3. TI T KIỆM NĂNG LƢỢNG CỤM NÚT CẢM BI N BẰNG ỨNG DỤNG LÝ THUY T T P THÔ ......................................................................... 70 3.1. ỨNG DỤNG LÝ T HUY T T P THÔ TẠI CH ĐỂ TỔNG HỢP D LIỆU .................... 71 3.1.1. Mô tả bài toán DF nhiều nút cảm biến....................................................... 72 3.1.2. Quy trình ứng dụng RST để tổng hợp dữ liệu .......................................... 73 3.1.3. Ứng dụng Lý thuyết tập thô để quyết định tổng hợp dữ liệu .................. 76 -2- 3.1.3.1. Xây dựng tƣơng quan giữa lý thuyết tập thô và tổng hợp dữ liệu.. 77 3.1.3.2. Ứng dụng RST để giải ài toán F th o quy trình 8 ƣớc ............. 78 3.1.4. Kết luận về giải pháp ứng dụng lý thuyết tập thô..................................... 83 3.2. ỨNG DỤNG LÝ T HUY T T P TH ĐỂ TIỀN X L LIỆU ĐẦU VÀO ............... 85 3.2.1. Giải pháp DP-DF .......................................................................................... 88 3.2.1.1. Quy trình x lý dữ liệu......................................................................... 88 3.2.1.2. X lý dữ liệu bị mất (thiếu)................................................................. 89 3.2.1.3. X lý dữ liệu nhiễu (yếu) .................................................................... 90 3.2.1.4. Thuật toán x lý dữ liệu bị mất và dữ liệu bị nhiễu ......................... 91 3.2.1.5. X lý dữ liệu ƣ thừa ........................................................................... 93 3.2.2. Minh họa và phân tích kết quả .................................................................... 94 3.2.3. Kết luận về giải pháp DP-DF ...................................................................... 96 CHƢƠNG 4. S DỤNG HIỆU QUẢ TÀI NGUYÊN CỤM CẢM BI N .............. 98 4.1. L A CHỌN NÚT VÀ D LIỆU CỦA CỤM BẰNG C A SỔ TRƢỢT ......................... 99 4.1.1. Giới thiệu bài toán ........................................................................................ 99 4.1.2. Giải pháp DF-SWin.................................................................................... 100 4.1.2.1. C a sổ trƣợt ......................................................................................... 100 4.1.2.2. Bảng dữ liệu thuộc tính...................................................................... 101 4.1.2.3. T nh ch thƣớc c a sổ trƣợt ............................................................. 102 4.1.2.4. Dữ liệu để tổng hợp ............................................................................ 102 4.1.3. Thuật toán DF-SWin .................................................................................. 103 4.1.3.1. Lƣu đồ thuật toán................................................................................ 103 4.1.3.2. Cài đặt thuật toán ................................................................................ 105 4.1.4. Mô phỏng và phân tích kết quả................................................................ 107 4.1.5. Kết luận về giải pháp DF-SWin................................................................ 112 4.2. TỔNG HỢP LIỆU TI T KIỆM NĂNG LƢỢNG TẠI N T CH ............................. 113 4.2.1. Giới thiệu bài toán ..................................................................................... 113 4.2.2. Giải pháp DF-AMS ................................................................................... 114 4.2.2.1. Lấy mẫu ............................................................................................... 115 4.2.2.2. X lý dữ liệu ....................................................................................... 116 4.2.3. Thuật toán................................................................................................... 118 4.2.4. Mô phỏng và phân tích kết quả ............................................................... 120 4.2.5. Kết luận về giải pháp DF-AMS ............................................................... 126 K T LU N ..................................................................................................................... 127 DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ........................................................... 132 TÀI LIỆU THAM KHẢO ............................................................................................. 133 -3- DANH MỤC CÁC THUẬT NGỮ V tt t A-D AMPS ATTS-DF BS CDMA CH DF DF-AMS DP-DF DF-SWin ETR-DF FLAMA IEEE LEACH LEACH-C LOS LR-WPAN MAC MIT NS OSI PEGASIS PHY PTW PU RSSI RST SOFAR SOSUS STEM SU Tag TDMA TOA TRAMA WINS WPAN WSNs ằng ti ng Anh Analog – Digital Adaptive Multi-domain Power aware Sensors Adaptive Target Tracking Solutionfor multi-sensor Data Fusion in WSNs Base Station Code Division Multiple Access Cluster head Data fusion Data Fusion – Average Median Sampling Data Pre-processing for Data Fusion Sliding Windows for multi-sensor Data Fusion in WSNs Efficiency in TRacking to target in multi-sensor Data Fusion Flow-Aware Medium Access Institute of Electrical and Electronics Engineers Low Energy Adaptive Clustering Hierarchy LEACH Centralized Line of Sight Low Rate Wireless Personal Area Networks Media Access Control Massachusetts Institute of Technology Network Simulator Open Systems Interconnection Power Efficient Gathering in Sensor Information System Physical layer Pipelined Tone Wakeup Processing unit Received Signal Strength Indicator Rough Set Theory Sound Fixing and Ranging channel Sound Surveillance System Sparse Topology and Energy Management Sensing unit Target Time Division Multiple Access Time of arrival TRaffic-Adaptive Medium Access Wireless Integrated Network Sensors Wireless Personal Area Network Wireless Sensor Networks -4- DANH SÁCH BẢNG Bảng 2.1. Các tham số trong mô phỏng giải pháp ETR-DF ....................................... 53 Bảng 2.2. Hiệu quả của việc giảm số lƣợng gói tin của ETR-DF và LEACH ......... 56 Bảng 2.3. Phân bố xác suất trong m lần đo ................................................................... 63 Bảng 2.4. Các tham số chính của mô phỏng ................................................................. 65 Bảng 3.1. Hệ thống thông tin an đầu của WSNs ........................................................ 79 Bảng 3.2. Lớp tập con tƣơng đƣơng .............................................................................. 79 Bảng 3.3. Ma trận phân biệt ............................................................................................ 80 Bảng 3.4. Dữ liệu CH nhận của khung truyền F1 ......................................................... 86 Bảng 3.5. Dữ liệu CH nhận của khung truyền Fk ......................................................... 86 Bảng 3.6. IS tại thời điểm bắt đầu tiền x lý ................................................................ 88 Bảng 3.7. Giá trị của các thuộc tính Aj ........................................................................... 88 Bảng 3.8. Dữ liệu đo của mạng cảm biến...................................................................... 94 Bảng 3.9. Xác suất khi dữ liệu đo ị thiếu .................................................................... 95 Bảng 3.10. Xác suất khi dữ liệu đo ị nhiễu ................................................................. 95 Bảng 3.11. Dữ liệu đã x lý thiếu, nhiễu ....................................................................... 95 Bảng 3.12. Ma trận phân biệt .......................................................................................... 95 Bảng 3.13. Các phƣơng án ữ kiện đã đƣợc rút gọn để tổng hợp dữ liệu ................. 96 Bảng 4.1. Dữ liệu thuộc tính chƣa sắp xếp.................................................................. 101 Bảng 4.2. Dữ liệu thuộc tính đã đƣợc sắp xếp ............................................................ 101 Bảng 4.3. Quy ƣớc ký hiệu s dụng trong thuật toán ................................................ 104 Bảng 4.4. Các tham số chính s dụng trong mô phỏng DF-SWin ........................... 107 Bảng 4.5. Số cụm và số nút trong mỗi cụm trong quá trình mô phỏng ................... 108 Bảng 4.6. Kết quả mô phỏng tại thời điểm 80 giây và 320 giây .............................. 109 Bảng 4.7. Kết quả áp dụng trong thời gian mô phỏng ............................................... 110 Bảng 4.8. Dữ liệu đo tại thời điểm tổng hợp.............................................................. 116 Bảng 4.9. Mức đo, giá trị đo của các tham số ............................................................. 116 Bảng 4.10. Năng lƣợng của các nút trong c ụm........................................................... 123 Bảng 4.11. Dữ liệu cảm biến của cụm tại thời điểm 200s......................................... 124 -5- DANH SÁCH H NH V Hình 1.1. Kiến trúc ph n l ớp các giao thức mạng WSNs [36] ................................... 17 Hình 1.2. Mô hình mạng cảm biến không dây [13, 40] ............................................... 18 Hình 1.3. Hƣớng tiếp cận theo kiến trúc mạng [38]. ................................................... 19 Hình 1.4. Sơ đồ cung cấp năng lƣợng cho nút cảm biến [39, 56]. ............................. 21 Hình 1.5. Mức tiêu thụ năng lƣợng của các đơn vị chức năng của nút cảm iến 48 .................... 21 Hình 1.6. Tổng hợp dữ liệu nhiều nút cảm biến không dây ........................................ 23 Hình 1.7. So sánh lƣu lƣợng theo 2 mô hình truyền dữ liệu của WSNs.................... 24 Hình 1.8. Tỉ lệ s dụng các phần mềm mô phỏng [71] ............................................... 25 Hình 1.9. Mô hình tổng hợp dữ liệu và các bài toán thành phần............................... 27 Hình 1.10. Các phƣơng pháp th o i mục tiêu 13 . .................................................. 28 Hình 2.1. Vị trí của nút cảm biến so với CH và Tag.................................................... 48 Hình 2.2. Các vùng ƣu tiên và các mức ƣu tiên............................................................ 50 Hình 2.3. Tọa độ mục tiêu và các nút trong mặt ph ng hảo sát ............................... 53 Hình 2.4. Phân bố nút, CH và mục tiêu (Tag) ở giây thứ 80. ..................................... 54 Hình 2.5. Áp dụng để lựa chọn nút: a) Cụm 1: 48 nút; b) Cụm 4: 16 nút ................. 55 Hình 2.6. Áp dụng thuật giải đối với Cụm 7 thời điểm giây thứ 120. ....................... 56 Hình 2.7. So sánh việc s dụng năng lƣợng giữa ETR-DF và LEACH .................... 57 Hình 2.8. Các mốc thời gian và trạng thái làm việc của nút ....................................... 60 Hình 2.9. Thay đổi của thuộc t nh hi vƣợt ngƣỡng .................................................... 60 Hình 2.10. Mô hình chuyển trạng thái của nút cảm biến............................................. 61 Hình 2.11. Mô hình trạng thái thích ứng của giải pháp ATTS-DF ............................ 62 Hình 2.12. Số nút cảm biến tham gia mô phỏng ATTS-DF ....................................... 66 Hình 2.13. Truyền dữ liệu của các nút cảm biến trong thời gian mô phỏng............. 66 Hình 2.14. Đồ thị truyền dữ liệu của nút số 16 của LEACH ...................................... 66 Hình 2.15. Hiệu quả việc giảm dữ liệu truyền của ATTS-DF so với LEACH......... 67 Hình 2.16. So sánh mức tiêu thụ năng lƣợng của các nút giữa ATTS-DF và LEACH................. 68 Hình 3.1. Mô tả bài toán tổng hợp dữ liệu có s dụng RST. ...................................... 73 Hình 3.2. Mô hình x lý, tổng hợp dữ liệu tại nút CH ................................................ 74 Hình 3.3. Truyền dữ liệu theo khung tin (frame) và theo chu kỳ (T) ........................ 85 Hình 4.1. Lƣu đồ luồng dữ liệu giải pháp DF-SWin.................................................. 103 -6- Hình 4.2. So sánh kết quả mô phỏng đối với các phƣơng án thay đổi số nút ......... 111 Hình 4.3. So sánh mức dự trữ năng lƣợng giữa DF-SWin và LEACH ................... 111 Hình 4.4. Minh họa DF từ n nút cảm biến, mỗi nút đo l tham số về mục tiêu. ..... 114 Hình 4.5. Mô hình x lý dữ liệu của DF-AMS........................................................... 117 Hình 4.6. Tỉ lệ nút đƣợc khảo sát và tổng số nút còn hoạt động .............................. 120 Hình 4.7. So sánh năng lƣợng EAvg và E Med ................................................................. 121 Hình 4.8. Lựa chọn nút cảm biến thông qua ESelect ..................................................... 121 Hình 4.9. So sánh số lƣợng gói tin truyền bằng DF-AMS và LEACH ................... 122 Hình 4.10. Kết quả tổng hợp dữ liệu của 3 tham số đo lƣờng .................................. 125 -7-