Đề tài K-Coverage problem and M-Connectivity problem

K-Coverage problem and M-Connectivity problem Sinh viên thực hiện: Nguyễn Văn Thanh - 20183632 Nguyễn Quang Huy - 20183554 2 Giảng viên Hướng dẫn: PGS.TS Huỳnh Thị Thanh Bình Nội Dung 3 Tổng quan Các nghiên cứu liên quan Mô hình bài toán Giải thuật đề xuất Thực nghiệm Kết luận Nội Dung 4 Tổng quan Các nghiên cứu liên quan Mô hình bài toán Giải thuật đề xuất Thực nghiệm Kết luận 5 1. Tổng quan – Giới thiệu mạng cảm biến Mạng cảm biến không dây - Wireless sensor network(WSN) 6 1. Tổng quan – Ứng dụng của mạng cảm biến 7 1. Tổng quan – Các vấn đề trong triển khai mạng cảm biến không dây Các vấn đề chính trong triển khai mạng cảm biến không dây: Năng lượng Bảo mật Bao phủ Kết nối Định tuyến 8 1. Tổng quan – Các vấn đề trong triển khai mạng cảm biến không dây Bao phủ: Bài toán bao phủ trong mạng cảm biến Bài toán bao phủ diện tích Bài toán bao phủ đối tượng Bài toán bao phủ rào chắn 9 1. Tổng quan – Các vấn đề trong triển khai mạng cảm biến không dây Kết nối: Nội Dung 10 Tổng quan 1.1 Giới thiệu bài toán 1.2 Ứng dụng bài toán Các nghiên cứu liên quan Mô hình bài toán Giải thuật đề xuất Thực nghiệm Kết luận Nội Dung 11 Tổng quan 1.1 Giới thiệu bài toán 1.2 Ứng dụng bài toán Các nghiên cứu liên quan Mô hình bài toán Giải thuật đề xuất Thực nghiệm Kết luận 12 1.1 Giới thiệu bài toán Giới thiệu bài toán K-coverage – M-connectivity Trong quá trình vận hành mạng cảm biến không dây, các cảm biến có thể bị chết (do hỏng hóc, hết năng lượng,...), đặt ra vấn đề về khả năng chịu lỗi. Khả năng chịu lỗi tương đương với số lượng cảm biến chết mà không ảnh hưởng đến tính bao phủ (kết nối) của mạng. Mục tiêu có độ quan trọng khác nhau nên yêu cầu độ bao phủ (hoặc số kết nối) khác nhau (giải quyết bài toán mục tiêu có độ quan trọng như nhau) : K -coverage: bài toán đảm bảo bao phủ. M -connectivity: bài toán đảm bảo kết nối. Nội Dung 13 Tổng quan 1.1 Giới thiệu bài toán 1.2 Ứng dụng bài toán Các nghiên cứu liên quan Mô hình bài toán Giải thuật đề xuất Thực nghiệm Kết luận 14 1.2 Ứng dụng bài toán Bài toán sử dụng để theo dõi, dám sát các đối tượng quan trọng trong điều kiện thời tiết môi trường khắc nghiệt luôn đảm bảo thông tin của các đối tượng được truyền về Base. Vì vậy mỗi đối tượng được theo dõi bởi K sensor phản biệt và có M đường truyền phân biệt về Base. VD: Theo dõi hoạt động của các lò phản ứng hạt nhân. Theo dõi khí thải tại các khu vực của nhà máy. Nội Dung 15 Tổng quan Các nghiên cứu liên quan Mô hình bài toán Giải thuật đề xuất Thực nghiệm Kết luận 16 2. Các nghiên cứu liên quan [1] Bài báo giải quyết vấn đề k coverage và m connectivity với số sensor cố định ( m connectivity là mỗi sensor có m kết nối tới các sensor khác) bằng giải thuật heuristic với 2 pha :  Pha 1 : Giải quyết k bao phủ Pha 2 : Giải quyết m kết nối  [1] S. Mini, Siba K. Udgata, Samrat L. Sabat, "𝑀-Connected Coverage Problem in Wireless Sensor Networks", International Scholarly Research Notices, vol. 2012  17 2. Các nghiên cứu liên quan [2] Bài báo giải quyết vấn đề triển khai sensor trong mạng thỏa mãn k bao phủ và tối ưu thời gian sống với số lượng sensor cho trước bằng giải thuật heuristic và GA. [2] S. Mini et al., “Sensor Deployment and Scheduling for Target Coverage Problem in Wireless Sensor Networks”, IEEE Sensors Journal, March 2014. 18 2. Các nghiên cứu liên quan [3] Bài báo giải quyết vấn đề triển khai sensor trong mạng thỏa mãn K bao phủ và M kết nối từ mỗi sensor và base bằng thuật toán GA. [3] Suneet Kumar Guptaa; Pratyay Kuila; Prasanta K. Janac , “Genetic algorithm approach for k-coverage and m-connected node placement in target based wireless sensor networks”, Computers and Electrical Engineering, November 2016. Đầu vào: Tập target T, tập điểm tiềm năng P, Base, K, M, WxH Đầu ra: Tập Sensor thỏa mãn yêu cầu bài toán. Thuật toán GA: Phương pháp mã hóa lời giải : Mã hóa nhị phân. Phương pháp lai tạo : Lai ghép một điểm cắt. Phương pháp đột biến : Đột biến đảo bit. Phương pháp chọn lọc cha mẹ : Chọn lọc ngẫu nhiên. Phương pháp đấu tranh sinh tồn : Lựa chọn theo thứ hạng(50% bố mẹ tốt nhất, 50% con tốt nhất). Nội Dung 19 Tổng quan Các nghiên cứu liên quan Mô hình bài toán Giải thuật đề xuất Thực nghiệm Kết luận 20 3. Mô hình bài toán Đầu vào :  Miền A = WxH Tập(target) T = {t₁, t₂, t₃, , t𝑚} trên miền A K, M là ràng buộc về bao phủ và kết nối ( K ≥ M ) Mỗi sensor có:  Rs : Bán kính bao phủ        Rc : Bán kính truyền tiếp kết nối Mỗi relay có: Rc : Bán kính truyền tiếp kết nối Base = (Bx, By) 21 3. Mô hình bài toán Đầu ra :  Tập S = {s₁, s₂, s₃, , s𝑛} Tập R = {r₁, r₂, r₃, , r𝑥} 22 3. Mô hình bài toán Rằng buộc :  Mỗi target có k bao phủ Mỗi target có m đường về Base Ràng buộc bao phủ giữa sensor và target : d(s,t) ≤Rs Ràng buộc kết nối : d(s,s) & d(s,r) & d(r,r) ≤ 2*Rc Mục tiêu:  Minimum : Cost = α*| R| +  β*| S| Với α , β : lần lượt là trong số chi phí cho relay và sensor. Trong bài toán này là 0.4 và 0,6 Nội Dung 23 Tổng quan Các nghiên cứu liên quan Mô hình bài toán Giải thuật đề xuất Thực nghiệm Kết luận Nội Dung 24 Tổng quan Các nghiên cứu liên quan Mô hình bài toán Giải thuật đề xuất 4.1. Bài toán K-coverage 4.2. Bài toán M-connectivity Thực nghiệm Kết luận 25 4. Giải thuật đề xuất CHIA BÀI TOÁN LÀM 2 PHA: Pha 1: Đề xuất giải thuật tham lam g iải quyết bài toán k-bao phủ( K-coverage): Tìm cách đặt một số l ư ợng ít nhất các sensor sao cho mỗi target đ ư ợc bao phủ bởi ít nhất K sensor. Thuật toán sử dụng: Tham lam và Heuristic . Pha 2: Đề xuất giải thuật heuristic giải quyết bài toán m-kết nối về base(M-connectivity): Tìm M đường đi phân biệt ngắn nhất từ mỗi Target về Base. Thuật toán sử dụng: Djikstra cải tiến và Heuristic. Kết quả bài toán thu được là vị trị đặt các sensor và relay sao cho thỏa mãn bài toán. Nội Dung 26 Tổng quan Các nghiên cứu liên quan Mô hình bài toán Giải thuật đề xuất 4.1. Bài toán K-coverage 4.2. Bài toán M-connectivity 5. Thực nghiệm 6. Kết luận 27 4.1 Bài toán K-coverage Đầu vào: Tập target Đầu ra: Tập sensor Ràng buộc: Mỗi target đ ư ợc bao phủ bởi ít nhất K sensor Mục tiêu: Tối thiểu hóa m (tổng các sensor) 28 4.1 Bài toán K-coverage Ký hiệu: Uncovered: tập các target ch ư a thỏa mãn K-coverage S: tập kết quả Các b ư ớc thực hiện: B 1 : Xây dựng tập ứng cử viên M( tập các sensor) B 2 : Lựa chọn sensor S i từ M Thêm S i vào S Cập nhật tập Uncovered B 3 : Nếu |Uncovered|  0, lặp lại B 2 29 4.1 Bài toán K-coverage Ký hiệu: Uncovered: tập các target ch ư a thỏa mãn K-coverage S: tập kết quả Các b ư ớc thực hiện: B 1 : Xây dựng tập ứng cử viên M( tập các sensor) B 2 : Lựa chọn sensor S i từ M Thêm S i vào S Cập nhật tập Uncovered B 3 : Nếu |Uncovered|  0, lặp lại B 2 30 4.1 Bài toán K-coverage Giả sử ta chọn K=3 B 1 : Xây dựng tập ứng cử viên M( tập các sensor) Target Sensor T1 T2 T3 S1 S5 S2 S3 S4 S6 31 4.1 Bài toán K-coverage Ký hiệu: Uncovered: tập các target ch ư a thỏa mãn K-coverage S: tập kết quả Các b ư ớc thực hiện: B 1 : Xây dựng tập ứng cử viên M( tập các sensor) B 2 : Lựa chọn sensor S i từ M Thêm S i vào S Cập nhật tập Uncovered B 3 : Nếu |Uncovered|  0, lặp lại B 2 32 4.1 Bài toán K-coverage Giả sử ta chọn K=3 Target Sensor T1 T2 T3 S1 S5 S3 S4 S6 B2: Lựa chọn sensor từ tập ứng cử viên Chọn sensor S i từ M sao cho S i bao phủ đ ư ợc nhiều target trong tập Uncovered nhất S1: T1, T2 = 2 S2: T1, T2 = 2 S3: T1, T2 = 2 S4: T3 = 1 S5: T3 = 1 S6: T3 = 1 Thêm vào S U={ T1, T2, T3 } S={ } U={ T1, T2, T3 } S={ S1 } U={ T3 } S={S1, S2, S3 } U={ T1, T2, T3 } S={S1, S2 } U={T3 } S={ S1, S2,S3,S4 } U={ T3 } S={S1, S2, S3 ,S4,S5} U={ T3 } S={S1, S2, S3 ,S4, S5 , S6} U={} S={S1, S2, S3 ,S4, S5 , S6} B3: Lặp lại cho đến khi U rỗng S2 33 4.1 Bài toán K-coverage T1 T2 Cách tiếp cận trên chỉ tận dụng được các sensor nằm trên vùng giao điểm của 2 target Khi có từ 3, 4, 5, vùng target giao nhau thì chúng không tận được T3 Giả sử K = 5 Với cách tiếp cận 1: 6 sensor Với cách tiếp cận 2: 5 sensor Cách tiếp cận: Tìm vùng giao nhau của nhiều target chưa được K bao phủ nhất. Sau đó chọn K điểm trong vùng đó. Nội Dung 34 Tổng quan Các nghiên cứu liên quan Mô hình bài toán Giải thuật đề xuất 4.1. Bài toán K-coverage 4.2. Bài toán M-connectivity 5. Thực nghiệm 6. Kết luận 35 4.2 . Bài toán M-connectivity Đầu vào: Tập Target  T = {t₁, t₂, t₃, , t𝑚} Tập Sensor S = {s₁, s₂, s₃, , s𝑛} Base B(x, y) Đầu ra: Tập Relay R = {r₁, r₂, r₃, , r𝑥} Ràng buộc: Mỗi target có M kết nối riêng biệt từ các sensor bao phủ về Base. Mục tiêu: Tối thiểu hóa x . 36 4.2 . Bài toán M-connectivity Các bước thực hiện: B1:Xây dựng đồ thị đầy đủ với các đỉnh là các sensor và base. Xóa bỏ các cạnh của đồ thị nếu 2 đỉnh của chúng cùng bao phủ một Target. B2: Chạy thuật toán Djikstra để tìm ra đường đi ngắn nhất từ mỗi sensor tới Base. B3: Chọn các đường đi từ sensor cùng bao phủ một target tới base sao cho chúng phân biệt với nhau. B4: Kết thúc thuật toán. 37 4.2 . Bài toán M-connectivity 3 5 0 4 2 1 8 6 7 9 10 Base B1: Xây dựng đồ thị đầy đủ với các đỉnh là các sensor và base. Xóa bỏ các cạnh của đồ thị nếu 2 đỉnh của chúng cùng bao phủ một Target. 38 4.2 . Bài toán M-connectivity 3 5 0 4 2 1 8 6 7 9 10 Base B2: Chạy thuật toán Djikstra để tìm ra đường đi ngắn nhất từ mỗi sensor tới Base. B3: Chọn các đường đi từ sensor cùng bao phủ một target tới base sao cho chúng phân biệt với nhau. 4. Thuật toán đề xuất 39 Độ phức tạp tính toán: Tiêu chí WGC WGCI Xấu nhất O(N^3) O(N^4) Trung bình O(N^3) O(N^2xLog(N)) Tốt nhất O(N^3) O(N^2) Nội Dung 40 Tổng quan Các nghiên cứu liên quan Mô hình bài toán Giải thuật đề xuất Thực nghiệm 5.1. Môi trường thực nghiệm 5.2. Dữ liệu thực nghiệm 5.3. Kết quả thực nghiệm 6. Kết luận Nội Dung 41 Tổng quan Các nghiên cứu liên quan Mô hình bài toán Giải thuật đề xuất Thực nghiệm 5.1. Môi trường thực nghiệm 5.2. Dữ liệu thực nghiệm 5.3. Kết quả thực nghiệm 6. Kết luận 42 5.1. Môi trường thực nghiệm CPU   Intel® Core™ i5-8265U 1.6GHz up 3.GHz Ram 16GB DDR4 2400MHz Ổ cứng 256GB SSD M.2 NVMe Màn hình   14.0″ Full HD (1920 x 1080) VGA   Intel® UHD Graphics 620 Lenovo Thinkpad T490S Nội Dung 43 Tổng quan Các nghiên cứu liên quan Mô hình bài toán Giải thuật đề xuất Thực nghiệm 5.1. Môi trường thực nghiệm 5.2. Dữ liệu thực nghiệm 5.3. Kết quả thực nghiệm 6. Kết luận 44 5.2 Dữ liệu thực nghiệm Bộ dữ liệu: STT Name Num. Targets N 1 S1-100 100 2 S1-150 150 3 S1-200 200 4 S1-250 250 5 S1-300 300 Nội Dung 45 Tổng quan Các nghiên cứu liên quan Mô hình bài toán Giải thuật đề xuất Thực nghiệm 5.1. Môi trường thực nghiệm 5.2. Dữ liệu thực nghiệm 5.3. Kết quả thực nghiệm 6. Kết luận 46 5.3. Kết quả thực nghiệm Các kịch bản thực nghiệm: Thay đổi số lượng target Thay đổi số bán kính kết nối RS Thay đổi bán kính truyền tiếp: RC Thay đổi số lượng sensor tối thiểu cần bao phủ một target: K 47 5.3.1 Kịch bản thay đổi số lượng Target STT Name Num. Targets N RS RC K M 1 S1-100 100 40 50 4 4 2 S1-150 150 40 50 4 4 3 S1-200 200 40 50 4 4 4 S1-250 250 40 50 4 4 5 S1-300 300 40 50 4 4 Bộ dữ liệu: 48 5.3.1 Kịch bản thay đổi số lượng Target Tham số cho thuật toán: WxH 2000x2000 K 4 M 4 Rs 40 Rc 50 (Bx, By) (5;5) α 0.4  β 0.6 49 5.3.1 Kịch bản thay đổi số lượng Target STT Name Num. Targets N RS RC K M WGC WGCI GA STT Name Num. Targets N RS Sensor Relay Cost Sensor Relay Cost Sensor Relay Cost 1 S1-100 100 40 50 4 4 229 957 562.2 219 754 433 240 740 440.0 2 S1-150 150 40 50 4 4 314 1486 782.8 281 1021 539.2 324 1048 628.0 3 S1-200 200 40 50 4 4 412 1713 932.4 327 1469 783,8 400 1102 680.8 4 S1-250 250 40 50 4 4 479 2445 1265.4 399 1470 827,4 463 1586 912.2 5 S1-300 300 40 50 4 4 573 2183 1217 425 1628 906,2 512 2052 1128.0 50 5.3.1 Kịch bản thay đổi số lượng Target Nhận xét: Đồ thị bên trái có dạng đi lên vì số lượng Target tăng thì số lượng Sensor cũng sẽ tăng lên để bao phủ chúng. Đồ thị bên phải có dạng đi lên vì số lượng Target tăng thì số lượng Relay cũng sẽ tăng lên. 51 5.3.1 Kịch bản thay đổi số lượng Target Nhận xét: Đồ thị có dạng đi lên vì số lượng Target tăng thì giá trị Cost cũng sẽ tăng lên. Đường biểu diễn thuận toán WGCI nằm dưới cùng cho thấy thuận toán WGCI tốt nhất, tiếp theo là GA và WGC WGCI tốt hơn GA và WGC lần lượt: 7.95% và 26.69%. Nguyên nhân là do thuật toán WGCI trong việc tìm kiếm các Sensor bao phủ các Target tận dụng được tối đa vùng chồng lấn của các Target để đặt các Sensor thay vì chỉ tận dụng được vùng chồng lấn của 2 Target như thuật toán WGC . 52 5.3.2 Thay đổi số bán kính kết nối RS STT Name Num. Targets N RS RC K M 1 S1-200 200 40 80 4 4 2 S1-200 200 50 80 4 4 3 S1-200 200 60 80 4 4 4 S1-200 200 70 80 4 4 5 S1-200 200 80 80 4 4 Bộ dữ liệu: 53 5.3.2 Thay đổi số bán kính kết nối RS Tham số cho thuật toán: WxH 2000x2000 Num of Target 200 K 4 M 4 Rs 40-50-60-70-80 Rc 80 (Bx, By) (5;5) α 0.4  β 0.6 54 5.3.2 Thay đổi số bán kính kết nối RS STT Name Num. Targets N RS RC K M WGC WGCI GA STT Name Num. Targets N RS Sensor Relay Cost Sensor Relay Cost Sensor Relay Cost 1 S1-200 200 40 80 4 4 412 1079 678.8 341 780 516.6 601 1587 996.4 2 S1-200 200 50 80 4 4 356 1011 618.2 275 713 450 449 1040 685.4 3 S1-200 200 60 80 4 4 332 1012 604.2 220 646 390.2 351 914 576.2 4 S1-200 200 70 80 4 4 306 1040 599.4 188 581 345.2 288 753 474.0 5 S1-200 200 80 80 4 4 297 994 576 171 593 340 226 637 390.0 55 5.3.2 Thay đổi số bán kính kết nối RS Nhận xét: Đồ thị có dạng đi xuống vì khi RS càng tăng lên thì số lượng Target mà một Sensor có thể bao phủ càng nhiều, do đó số Relay cũng giảm theo. 56 5.3.2 Thay đổi số bán kính kết nối RS Nhận xét: Đồ thị có đi xuống vì khi RS tang lên dẫn đến số lượng Sensor và Relay giảm làm Cost giảm theo. WGCI tốt hơn GA và WGC lần lượt: 22.89% và 33.98% Nguyên nhân là do khi RS tăng lên thì số lượng các vùng taget chồng lấn lên nhau càng nhiều nên thuật toán WGCI càng tỏ ra hiệu quả rõ rệt. Còn GA giảm nhanh nguyên nhân do khi RS tăng các điểm tiềm năng có thể bao phủ được nhiều target hơn. 57 5.3.3 Thay đổi số bán kính truyền tiếp RC STT Name Num. Targets N RS RC K M 1 S1-200 200 40 40 4 4 2 S1-200 200 40 50 4 4 3 S1-200 200 40 60 4 4 4 S1-200 200 40 70 4 4 5 S1-200 200 40 80 4 4 Bộ dữ liệu: 58 5.3.3 Thay đổi số bán kính truyền tiếp RC Tham số cho thuật toán: WxH 2000x2000 Num of Target 200 K 4 M 4 Rs 40 Rc 40-50-60-70-80 (Bx, By) (5;5) α 0.4  β 0.6 59 5.3.3 Thay đổi số bán kính truyền tiếp RC STT Name Num. Targets N RS RC K M WGC WGCI GA STT Name Num. Targets N RS Sensor Relay Cost Sensor Relay Cost Sensor Relay Cost 1 S1-200 200 40 40 4 4 412 2157 1109.4 341 1537 819.6 615 3500 1769.0 2 S1-200 200 40 50 4 4 412 1786 961.6 341 1214 702.4 630 2700 1463.6 3 S1-200 200 40 60 4 4 412 1493 844.4 341 1036 619.3 510 1956 1135.2 4 S1-200 200 40 70 4 4 412 1244 744.6 341 871 553.2 604 1737 1057.2 5 S1-200 200 40 80 4 4 412 1091 683.5 341 761 509.2 598 1594 996.0 60 5.3.3 Thay đổi số bán kính truyền tiếp RC Nhận xét: Do RC thay đổi không làm ảnh hưởng tới pha 1 của bài toán lên số lượng sensor 3 thuật toán tìm ra không thay đổi thi RC thay đổi. Khi RC thay đổi thì cần càng ít Relay làm nhiệm vụ kết nối các Sensor tới Base làm cho số lượng Relay giảm khi RC tăng. 61 5.3.3 Thay đổi số bán kính truyền tiếp RC Nhận xét: Đồ thị có đi xuống vì khi RC tăng lên dẫn đến số lượng Relay giảm làm Cost giảm theo. WGCI tốt hơn GA và WGC lần lượt: 50.1% và 26.19% Nguyên nhân: do WGCI có các điểm đặt sensor tốt hơn WGC cũng như GA. 62 5.3.4 Kịch bản thay đổi K STT Name Num. Targets N RS RC K M 1 S1-200 200 40 50 2 2 2 S1-200 200 40 50 3 3 3 S1-200 200 40 50 4 4 4 S1-200 200 40 50 5 5 5 S1-200 200 40 50 6 6 Bộ dữ liệu: 63 5.3.4 Kịch bản thay đổi K Tham số cho thuật toán: WxH 2000x2000 Num of Target 200 K 2-3-4-5-6 M 2-3-4-5-6 Rs 40 Rc 50 (Bx, By) (5;5) α 0.4  β 0.6 64 5.3.4 Kịch bản thay đổi K STT Name Num. Targets N RS RC K M WGC WGCI GA STT Name Num. Targets N RS Sensor Relay Cost Sensor Relay Cost Sensor Relay Cost 1 S1-200 200 40 50 2 2 203 893 479 170 663 367.3 350 1300 730 2 S1-200 200 40 50 3 3 309 1321 713.7 255 947 531.8 432 1636 913.6 3 S1-200 200 40 50 4 4 412 1780 959.3 342 1208 688.3 585 2373 1300.2 4 S1-200 200 40 50 5 5 515 2176 1179.3 428 1549 876.2 818 3946 2069.2 5 S1-200 200 40 50 6 6 636 2608 1425.1 512 1791 1023.6 1036 5004 2632.2 65 5.3.4 Kịch bản thay đổi K Nhận xét: Do K tăng lên số lượng Sensor và Relay cũng tăng lên. 66 5.3.4 Kịch bản thay đổi K Nhận xét: Đồ thị có dạng đi lên vì khi K tăng dẫn đến số Sensor tăng, số Relay tăng làm Cost tăng theo. WGCI tốt hơn GA và WGC lần lượt: 54.39%, 26.19% Khi K càng lớn thì thuật toán WGCI càng tỏ ra ưu việt hơn ( đồ thị mở rộng về cuối). 67 5.3 Kết quả thực nghiệm Nhận xét chung: Thuật toán WGC tốt hơn trong trường hợp: sử dụng trong trường hợp: Các target nằm xa nhau, số lượng Target bé, bán kính bao phủ Rs của sensor bé, và số lượng bao phủ K thấp(bé hơn 3) Thuật toán WGCI tốt hơn trong trường hợp: sử dụng trong trường hợp: Các target nằm gần nhau, số lượng Target lớn, bán kính bao phủ Rs của sensor trung bình lớn, và số lượng bao phủ K (lớn hơn hoặc bằng 3) Thuật toán GA tốt trong các trường hợp:Các target phản bố đều và dày trên miền, bán kính bao phủ RS của sensor trung bình lớn, và số lượng bao phủ K thấp. 68 5.3 Kết quả thực nghiệm Qua kết quả thực nghiệm cho thấy : Thuật toán WGCI (do nhóm đề xuất) tốt hơn thuật toán WGC(do nhóm đề xuất): 28.1% . Nguyên nhân: Do thuật toán WGCI tận dụng tối đa được vùng chồng lấn lên nhau của các Target và đặt các Sensor vào vùng đó làm giảm đáng kể số lượng Sensor từ đó làm giảm số lượng Relay cần sử dụng và làm giảm Cost tổng thể của bài toán. Thuật toán WGCI (do nhóm đề xuất) tốt hơn thuật toán GA(bài báo so sánh): 33.83%. Nguyên nhân: Do việc chọn các điểm tiềm năng của thuật toán GA là chọn đều trên miền lên không thể tận dụng được các điểm tiềm năng đặt tốt nhất như WGCI, cũng do các tham số của thuật toán GA đã được thay đổi so với bài báo ban đầu để phù hợp với dữ liệu của nhóm và các tham số này chưa được tối ưu tốt. Thuật toán WGC (do nhóm đề xuất) tốt hơn thuật toán toán GA(bài báo so sánh): 8.66%. Nguyên nhân: Do việc chọn các điểm tiềm năng của thuật toán GA là chọn đều trên miền lên không thể tận dụng được các điểm tiềm năng đặt tốt nhất như WGC, cũng do các tham số của thuật toán GA đã được thay đổi so với bài báo ban đầu để phù hợp với dữ liệu của nhóm và các tham số này chưa được tối ưu tốt. 5.3 Kết quả thực nghiệm 69 Tuy thuật toán WGCI tốt hơn nhưng nó sẽ đặt các sensor bao phủ chung cùng một Target vào rất gần nhau. Điều này làm cho chúng không thực tế vì khi có một tác động vào vùng đó thì rất nhiều sensor bị hỏng và Target đó sẽ bị mất hết các kết nối điều này không đáp ứng được yêu cầu thực tế đảm bảo các Target luôn được bao phủ. Hướng cải tiến: Cải tiến thuật toán WGCI: Thêm các hàm phạt về khoảng cách giữa các sensor cùng bao phủ một Target để chúng xa nhau tránh các sự cố tác động vào gây mất kết nối hoàn toàn các Target . Nhược điểm và hướng cải tiến: Nội Dung 70 Tổng quan Các nghiên cứu liên quan Mô hình bài toán Giải thuật đề xuất Thực nghiệm Kết luận 6. Kết luận 71 Tìm hiểu về WSN và ứng dụng thực tế. Nghiên cứu được bài toán K-coverage và M-connectivity đề xuất 2 thuật toán WGC và WGCI để giải quyết bài toán. Kết quả thực nghiệm trên 5 bộ dữ liệu và 4 kịch bản thử nghiệm Tìm hiểu thuật toán GA và code lại một bài báo để so sánh với thuật toán do nhóm đề xuất. Qua kết quả thực nghiệm cho thấy: Thuật toán WGCI (do nhóm đề xuất) tốt hơn thuật toán WGC(do nhóm đề xuất): 28.1%. Thuật toán WGCI (do nhóm đề xuất) tốt hơn thuật toán GA(bài báo so sánh): 33.83%. Thuật toán WGC (do nhóm đề xuất) tốt hơn thuật toán WGC(bài báo so sánh): 8.66%. THANK YOU ! 72