Bài giảng Bao phủ mạng không dây: Chương 2 - Bài toán K-coverage trong mạng cảm biến không dây

Bài giảng "Bao phủ mạng không dây: Chương 2 - Bài toán K-coverage trong mạng cảm biến không dây" được biên soạn với các nội dung chính sau: Giới thiệu bài toán K-coverage; Các nghiên cứu liên quan; Mô hình bài toán K-coverage;... Mời các bạn cùng tham khảo bài giảng!
Nội dung trích xuất từ tài liệu:
Bài giảng Bao phủ mạng không dây: Chương 2 - Bài toán K-coverage trong mạng cảm biến không dây Nội dung 1 Tổng quan 2 Bài toán K-coverage trong mạng cảm biến không dây Giới thiệu 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 3 Bài toán Q-coverage và Q-connectivity trong mạng cảm biến không dây 4 Bài toán tối ưu thời gian bao phủ của mạng cảm biến 12 / 152 Giới thiệu bài toán K-coverage  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: Q-coverage: bài toán đảm bảo bao phủ. Q-connectivity: bài toán đảm bảo kết nối.  Với bài toán bao phủ các mục tiêu có mức độ quan trọng như nhau, ta sẽ có bài toán K-coverage. 13 / 152 Giới thiệu bài toán K-coverage Hình 8: Mạng cảm biến 2-coverage 14 / 152 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 15 / 152 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 16 / 152 Các nghiên cứu liên quan Trong nghiên cứu 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 thêm các nút chuyển tiếp vào mạng để đảm bảo tính kết nối và tính chịu lỗi. 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) 17 / 152 Các nghiên cứu liên quan Trong nghiên cứu 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. Trong nghiên cứu 3 , tác giả đã:  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. 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 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 18 / 152 Nhận xét  Nghiên cứu 1 chưa xét đến vấn đề năng lượng.  Sử dụng mô hình 3, tạo tập độc lập lớn nhất và áp dụng giải thuật di truyền hoán vị để giải quyết. 19 / 152 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 20 / 152 Mô hình bài toán  Cho miền cần theo dõi có kích thước WxH.  T = {(xt1 , yt1 ), (xt2 , yt2 ), . . . (xtn , ytn )} là tập mục tiêu cần theo dõi.  R là bán kính cảm nhận của các cảm biến.  Ràng buộc: Mỗi mục tiêu được bao phủ bởi ít nhất 1 cảm biến.  Yêu cầu: Tìm cách triển khai dùng ít cảm biến nhất. Lập lịch hoạt động cho các cảm biến để tối đa hoá thời gian sống của mạng. 21 / 152 Mô hình bài toán Ý tưởng: Bài toán có 2 mục tiêu là tối thiểu số cảm biến và tối đa hoá thời gian sống của mạng, nên ta cần tìm một ngưỡng để dung hoà 2 mục tiêu: Chấp nhận đặt thêm một số cảm biến để tăng thời gian sống của mạng. 22 / 152 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 Bài toán K-Coverage Bài toán Maximun Disjoint Set Cover  Thực nghiệm  Kết luận 23 / 152 Giải thuật đề xuất Chia bài toán làm 2 pha:  Pha 1: Giải bài toán k-coverage. Tìm cách triển khai dùng ít cảm biến nhất. Sử dụng thuật toán tham lam.  Pha 2: Giải bài toán tối đa số tập phủ độc lập cực đại (Maximum Disjoint Set Cover). Tìm cách chia các cảm 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ộ các mục tiêu. Số lượng tập con là thời gian số của mạng. Sử dụng thuật toán tham lam và giải thuật di truyền.  Tinh chỉnh: Loại bỏ các cảm biến không thuộc tập phủ độc lập nào. 24 / 152 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 Bài toán K-Coverage Bài toán Maximun Disjoint Set Cover  Thực nghiệm  Kết luận 25 / 152 Bài toán K-coverage  Đầu vào: Tập các mục tiêu T = {(xt1 , yt1 ), (xt2 , yt2 ), . . . (xtn , ytn )}.  Đầu ra: Tập các cảm biến S = {(xs1 , ys1 ), (xs2 , ys2 ), . . . (xsm , ysm )}  Ràng buộc: Mỗi mục tiêu được bao phủ bởi ít nhất K cảm biến.  Mục tiêu: Tối thiểu hoá m. 26 / 152 B ...