Bài giảng Đảm bảo K bao phủ trong bao phủ đối tượng nhằm kéo dài thời gian sống của mạng cảm biến

Đ ảm bảo K bao phủ trong bao phủ đối tượng nhằm kéo dài thời gian sống của mạng cảm biến 1/16/2022 1 Trình bày: Nguyễn Thị Trang Nguyễn Văn Sơn Người hướng dẫn: PGS.TS Huỳnh Thị Thanh Bình 2 Nội dung 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 3 Nội dung 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 1. Các nghiên cứu liên quan [1] Tác giả đã đề xuất giải thuật MUTSP giải quyết vấn đề bao phủ đối tượng đảm bảo kết nối và chịu lỗi trong WSNs. Pha 1: Tìm tập cảm biến với số lượng nhỏ nhất để bao phủ tập đối tượng . Pha 2 : Tìm và thêm các nút chuyển tiếp vào mạng để đảm bảo tính kết nối và chịu lỗi. 4 [1]. Hanh Nguyen Thi, Binh Huynh Thi Thanh, Son Nguyen Van and Lan Phan Ngoc. (2019). Minimal Node Placement for Ensuring Target Coverage With Network Connectivity and Fault Tolerance Constraints in Wireless Sensor Networks, 2019 IEEE Congress on Evolutionary Computation Conference (CEC 2019). 1. Các nghiên cứu liên quan 5 [2] Tác giả tìm số tập bao phủ lớn nhất và giải quyết vấn đề lãng phí năng lượng. [2]. Mohamed El-Sherif, Yasmine Fahmy, Hanan Kamal (2018). Lifetime Maximization of Disjoint Wireless Sensor Networks using Multiobjective Genetic Algorithm , IET Research Journals, pp. 1–8 c The Institution of Engineering and Technology 2015. 1. Các nghiên cứu liên quan 6 [3] Triển khai cảm biến sao cho thời gian sống của mạng là lớn nhất Lập lịch cho cảm biến để tối ưu thời gian sống của mạng. [3]. S. Mini, Siba K. Udgata, and Samrat L. Sabat. (2014). Sensor Deployment and Scheduling for Target Coverage Problem in Wireless Sensor Networks, IEEE SENSORS JOURNAL, VOL. 14, NO. 3, MARCH 2014 1. Các nghiên cứu liên quan 7 Tuy nhiên, [1] chưa xét đến vấn đề năng lượng. -> Sử dụng mô hình trong [3], tạo tập độc lập lớn nhất,  và áp dụng GA hoán vị để giải quyết.  8 Nội dung 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 2 . Mô hình bài toán 9 Miền W x H. Tập target Các sensor có: bán kính R năng l ư ợng b tốc độ tiêu thụ năng l ư ợng e Ràng buộc: Mỗi target đ ư ợc bao phủ bới ít nhất 1 sensor . Mục tiêu: Tìm cách đặt một số l ư ợng ít nhất các sensor. Lập lịch hoạt động cho các sensor để tối đa thời gian sống của mạng. 2 . Mô hình bài toán 10 Ý tưởng chung: Vì chúng ta vừa cần tối thiểu số lượng sensor, vừa cần tối đa thời gian sống của mạng, nên ta cần tìm một ngưỡng để dung hòa 2 mục tiêu này. => Đặt thêm một số lượng sensor chấp nhận được để tăng thời gian sống của mạng. 2 . Mô hình bài toán 11 Chia bài toán làm 2 pha: Pha 1: Giả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. Pha 2: Giải quyết bài toán số tập độc lập cực đại( Maximum Disjoint Set Cover): Tìm cách chia tập các sensor thu được từ pha 1 thành một số l ư ợng lớn nhất các tập con không giao nhau, sao cho mỗi tập con đều bao phủ toàn bộ target. Số lượng các tập con chính là thời gian sống của mạng. Thuật toán sử dụng: tham lam, di truyền. Kết quả bài toán thu được từ pha 2 bằng cách loại bỏ các sensor không thuộc một tập con nào. 12 Nội dung 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 13 Nội dung Các nghiên cứu liên quan Mô hình bài toán Giải thuật đề xuất 3.1. Bài toán K-coverage 3.2. Bài toán Maximun Disjoint Set Cover Thực nghiệm Kết luận 14 Nội dung Các nghiên cứu liên quan Mô hình bài toán Giải thuật đề xuất 3.1. Bài toán K-coverage 3.2. Bài toán Maximun Disjoint Set Cover Thực nghiệm Kết luận 3 . Bài toán K-coverage 15 Đầ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 ( 1  K  m ) Mục tiêu: Tối thiểu hóa m . 16 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 3. Bài toán K-coverage 17 Xây dựng tập ứng cử viên M Giả sử tại mỗi target i, đặt một đ ư ờng tròn D i bán kính R( bán kính sensor) Với mỗi cặp D i và D j ( ) giao nhau tại d điểm giao( d  {1, 2}), kết nạp vào M sensor tại các vị trí: Giao của D i và D j k - d điểm bất kỳ trên D i hoặc D j mà thuộc phần giao của D i và D j ( nếu k  d ) Các Sensor đ ư ợc kết nạp vào M Target K = 5 3. Bài toán K-coverage 18 Xây dựng tập ứng cử viên M Nếu D i không giao với bất kỳ đ ư ờng tròn nào, chọn ngẫu nhiên k điểm trên D i , kết nạp vào M k sensor đặt tại k điểm vừa chọn. 3. Bài toán K-coverage 19 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 Với K = 3 : |S| = 1 |Uncovered| = 3 3. Bài toán K-coverage 20 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 Với K = 3 : |S| = 2 |Uncovered| = 3 3. Bài toán K-coverage 21 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 Với K = 3 : |S| = 3 |Uncovered| = 1 3. Bài toán K-coverage 22 Nội dung Các nghiên cứu liên quan Mô hình bài toán Giải thuật đề xuất 3.1. Bài toán K-coverage 3.2. Bài toán Maximun Disjoint Set Cover Thực nghiệm Kết luận 4 . Bài toán Maximum Disjoint Set Cover 23 Đầu vào: Tập target Tập sensor Đầu ra: Tập C = {C 1 , C 2 ,, C z } Trong đó: C i tập các sensor ( 1  i  z ) C i  C j =  ( 1  i  j  z) Ràng buộc: Mỗi target đ ư ợc bao phủ bởi ít nhất 1 sensor thuộc C i  i  {1, 2,, z} Mục tiêu: Tối đa hóa z 24 4.1 . Thuật toán tham lam 4.2 . Thuật toán di truyền 4. Bài toán Maximum Disjoint Set Cover 25 4.1 . Thuật toán tham lam Các b ư ớc thực hiện: B 1 : Tính toán cho mỗi sensor một trọng số thể hiện thứ tự ư u tiên - Weight assignment. B 2 : Xây dựng các Set Cover - Cover formation. B 3 : Tối ư u các Set Cover - Cover optimization. B 4 : Nếu có thể tạo thêm set cover từ các sensor ch ư a sử dụng, lặp lại từ B 1 4. Bài toán Maximum Disjoint Set Cover 26 4.1 . Thuật toán tham lam Weight assignment : Ký hiệu: W target[i] : Số l ượng các s ensor bao phủ t arget i. W sensor[i] : Trọng số của sensor i . 4. Bài toán Maximum Disjoint Set Cover 27 4.1 . Thuật toán tham lam Weight assignment: W sensor[i] được tính theo công thức : Trong đó : n : Số t argets. SC i : Tập các t argets mà s ensor i bao phủ.  W sensor[i] càng lớn, sensor i có độ ư u tiên càng cao 4. Bài toán Maximum Disjoint Set Cover 28 4.1 . Thuật toán tham lam Weight assignment: Ví dụ: 4. Bài toán Maximum Disjoint Set Cover 29 4.1 . Thuật toán tham lam Weight assignment : Tính số lượng sensor bao phủ mỗi target: 4. Bài toán Maximum Disjoint Set Cover 30 4.1 . Thuật toán tham lam Weight assignment: Tính weight cho từng sensor: 4. Bài toán Maximum Disjoint Set Cover 31 4.1 . Thuật toán tham lam Weight assignment: Kết quả thu được: 4. Bài toán Maximum Disjoint Set Cover 32 4 .1 . Thuật toán tham lam Cover formation: Đầu vào: Tập các target. Tập các sensor và trọng số tính đ ư ợc ở Weight assignment. Đầu ra: Cover C i . 4. Bài toán Maximum Disjoint Set Cover 33 4 .1 . Thuật toán tham lam Các bước thực hiện: B 1 : Sắp xếp các sensor theo thứ tự giảm dần của trọng số tính đ ư ợc  4 3 2 1 5 7 9 8 6 4. Bài toán Maximum Disjoint Set Cover 34 4 .1 . Thuật toán tham lam Các bước thực hiện: B 2 : Thêm lần lượt các sensor vào C i theo thứ tự đã sắp xếp đến khi C i thỏa mãn tính báo phủ . 4. Bài toán Maximum Disjoint Set Cover 35 4 .1 . Thuật toán tham lam Các bước thực hiện: B 2 : Thứ tự duyệt sensor: 4 3 2 1 5 7 9 8 6 C i = {4} Tập target đã bao phủ: {1, 3} 4. Bài toán Maximum Disjoint Set Cover 36 4 .1 . Thuật toán tham lam Các bước thực hiện: B 2 : Thứ tự duyệt sensor: 3 2 1 5 7 9 8 6 C i = {4, 3} Tập target đã bao phủ: {1, 3, 4} 4. Bài toán Maximum Disjoint Set Cover 37 4 .1 . Thuật toán tham lam Các bước thực hiện: B 2 : Thứ tự duyệt sensor: 2 1 5 7 9 8 6 Sensor 2, 1, 5 không bao phủ thêm target nào  C i = {4, 3} Tập target đã bao phủ: {1, 3, 4} 4. Bài toán Maximum Disjoint Set Cover 38 4 .1 . Thuật toán tham lam Các bước thực hiện: B2: Thứ tự duyệt sensor: 7 9 8 6 C i = {4, 3, 7} Tập target đã bao phủ: {1, 3, 4, 2}  Thỏa mãn 4. Bài toán Maximum Disjoint Set Cover 39 4 .1 . Thuật toán tham lam Cover Optimization: Đầu vào: Cover C i thu đ ư ợc từ Cover Formation. Đầu ra: Opt_cover. 4. Bài toán Maximum Disjoint Set Cover 40 4 .1 . Thuật toán tham lam Cover Optimization : B1: Duyệt các sensor trong C i theo thứ tự ng ư ợc lại với thứ tự khi thêm C i = { 4, 3, 7} Opt_cover = { . 4. Bài toán Maximum Disjoint Set Cover 41 4.1 . Thuật toán tham lam Cover Optimization : B2: Khi duyệt đến sensor S j , nếu việc bỏ S j không làm mất tính bao phủ của C i , loại S j khỏi C i C i = { 4 , 3 , 7 } Xét Sensor 7 => Opt_cover = { , 4. Bài toán Maximum Disjoint Set Cover 42 4.1 . Thuật toán tham lam Cover Optimization : B2 : Nếu việc bỏ S j làm mất tính bao phủ của Ci, Thêm S j vào Opt_cover C i = { 4, 3 , 7} Xét Sensor 3 => Opt_cover = {7, . 4. Bài toán Maximum Disjoint Set Cover 43 4.1 . Thuật toán tham lam Cover Optimization : B2: Nếu việc bỏ S j làm mất tính bao phủ của Ci, Thêm S j vào Opt_cover C i = { 4 ,3,7} Xét Sensor 8 => Opt_cover = { . 4. Bài toán Maximum Disjoint Set Cover 44 4.1 . Thuật toán tham lam Cover Optimization : Kết quả: Opt_cover = { 4. Bài toán Maximum Disjoint Set Cover 45 4.2. Thuật toán di truyền Biểu diễn chromosome Toán tử di truyền Thuật toán heuristic loại bỏ sensor d ư thừa 4. Bài toán Maximum Disjoint Set Cover 46 4.2. Thuật toán di truyền Biểu diễn Chromosome: Mỗi Chromosome đ ư ợc biểu diễn d ư ới dạng mảng m chiều( m ứng với số l ư ợng sensor) Mỗi Chromosome thể hiện một thứ tự duyệt sensor để xây dựng set cover 4. Bài toán Maximum Disjoint Set Cover 47 4.2. Thuật toán di truyền Toán tử di truyền: Selection: Tournament selection Crossover: One point crossover Mutation: Swap mutation Fitness của mỗi chromosome là số set cover m à chromosome đó tạo đ ư ợc 4. Bài toán Maximum Disjoint Set Cover 48 4.2. Thuật toán di truyền Thuật toán Heuristic loại bỏ sensor d ư thừa: Ta có thể tối ư u mỗi set cover bằng cách bỏ đi các sensor mà không ảnh h ư ởng tới ràng buộc bao phủ. Việc loại bỏ đ ư ợc áp dụng cho mỗi chromosome sau các b ư ớc crossover và mutation ở mỗi thế hệ. Các b ư ớc thực hiện: Với mỗi set cover trong chromosome, thực hiện duyệt các sensor theo thứ tự từ cuối. Nếu việc loại bỏ sensor đang xét không làm mất đi tính bao phủ của set cover, chuyển sensor đó sang set cover tiếp theo. Thực hiện loại sensor d ư thừa trên set cover tiếp theo. 4. Bài toán Maximum Disjoint Set Cover 49 4.2. Thuật toán di truyền Thuật toán Heuristic loại bỏ sensor d ư thừa: Các b ư ớc thực hiện: Với mỗi set cover trong chromosome, thực hiện duyệt các sensor theo thứ tự từ cuối . Xét chromosome: 4. Bài toán Maximum Disjoint Set Cover 50 4.2. Thuật toán di truyền Thuật toán Heuristic loại bỏ sensor d ư thừa: Các b ư ớc thực hiện: Nếu việc loại bỏ sensor đang xét không làm mất đi tính bao phủ của set cover, chuyển sensor đó sang set cover tiếp theo. chromosome : 4. Bài toán Maximum Disjoint Set Cover 51 4.2. Thuật toán di truyền Thuật toán Heuristic loại bỏ sensor d ư thừa: Các b ư ớc thực hiện: Nếu việc loại bỏ sensor đang xét không làm mất đi tính bao phủ của set cover, chuyển sensor đó sang set cover tiếp theo. chromosome: 4. Bài toán Maximum Disjoint Set Cover 52 4.2. Thuật toán di truyền Thuật toán Heuristic loại bỏ sensor d ư thừa: Các b ư ớc thực hiện: Nếu việc loại bỏ sensor đang xét không làm mất đi tính bao phủ của set cover, chuyển sensor đó sang set cover tiếp theo . chromosome: 4. Bài toán Maximum Disjoint Set Cover 53 4.2. Thuật toán di truyền Thuật toán Heuristic loại bỏ sensor d ư thừa: Các b ư ớc thực hiện: Nếu việc loại bỏ sensor đang xét không làm mất đi tính bao phủ của set cover, chuyển sensor đó sang set cover tiếp theo. chromosome: 4. Bài toán Maximum Disjoint Set Cover 54 4.2. Thuật toán di truyền Thuật toán Heuristic loại bỏ sensor d ư thừa: Các b ư ớc thực hiện: Nếu việc loại bỏ sensor đang xét không làm mất đi tính bao phủ của set cover, chuyển sensor đó sang set cover tiếp theo . chromosome: 4. Bài toán Maximum Disjoint Set Cover 55 4.2. Thuật toán di truyền Loại bỏ sensor d ư thừa: Các b ư ớc thực hiện: Nếu việc loại bỏ sensor đang xét không làm mất đi tính bao phủ của set cover, chuyển sensor đó sang set cover tiếp theo . chromosome: 4. Bài toán Maximum Disjoint Set Cover 56 Nội dung 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 . Thực nghiệm 57 Bộ dữ liệu: diện tích 2000m x 2000m 58 Tham số thuật toán GA: 5. Thực nghiệm 59 5.1 . Kết quả bài toán K-coverage Thử nghiệm với K = 5 5.2 . Kết quả bài toán Maximum Disjoint Set Cover Thử nghiệm với hai thuật toán: tham lam và di truyền Thử nghiệm với K = 5 5. Thực nghiệm 60 5.1 . Kết quả bài toán K-coverage 5-coverage: 5. Thực nghiệm 61 5.2. Kết quả Maximum Disjoint Set Cover 5-coverage: 5. Thực nghiệm 62 5.2. Kết quả Maximum Disjoint Set Cover 5-coverage: 5. Thực nghiệm 63 5.2. Kết quả Maximum Disjoint Set Cover 5-coverage: 5. Thực nghiệm 64 Nội dung Các nghiên cứu liên quan Mô hình bài toán đề xuất Giải thuật đề xuất Thực nghiệm Kết luận 6 . Kết luận 65 Đối với pha 1, thuật toán tham lam đã cho kết quả t ư ơng đối tốt, số l ư ợng sensor sử dụng nhỏ h ơ n nhiều so với k lần số l ư ợng target. Đối với pha 2, thuật toán di truyền cho kết quả về thời gian sống của mạng tốt h ơ n so với thuật toán tham lam, tuy nhiên phải sử dụng nhiều sensor h ơ n. Tài liệu tham khảo 66 Hanh Nguyen Thi, Binh Huynh Thi Thanh, Son Nguyen Van and Lan Phan Ngoc. (2019). Minimal Node Placement for Ensuring Target Coverage With Network Connectivity and Fault Tolerance Constraints in Wireless Sensor Networks . Mohamed El-Sherif, Yasmine Fahmy, Hanan Kamal Lifetime. (2018). Maximization of Disjoint Wireless Sensor Networks using Multiobjective Genetic Algorithm . S. Mini, Siba K. Udgata, and Samrat L. Sabat. (2014). Sensor Deployment and Scheduling for Target Coverage Problem in Wireless Sensor Networks. 67