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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:63

Thêm vào BST

Báo xấu

21
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầ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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ài toán K-coverage Ký hiệu: Uncovered: tập các mục tiêu chưa thoả mãn K-coverage. S: tập kết quả. Các bước thực hiện: Bước 1: Xây dựng tập ứng cử viên M. Bước 2: Lựa chọn cảm biến Si từ M: Thêm Si vào S. Cập nhật tập Uncovered. Bước 3: Nếu |Uncovered| > 0, lặp lại bước 2. 27 / 152
Bài toán K-coverage Xây dựng tập ứng cử viên M Giả sử tại mỗi mục tiêu ti , đặt một đường tròn Di bán kính R. Với mỗi cặp Di và Dj giao nhau tại d điểm giao (d ∈ {1, 2}, kết nạp vào tập M cảm biến đặt tại các vị trí: Giao của Di và Dj . k − d điểm bất kỳ trên Di hoặc Dj mà thuộc phần giao của Di và Dj (nếu k > d). Hình 9: Các ứng cử viên được kết nạp vào M 28 / 152
Bài toán K-coverage Xây dựng tập ứng cử viên M Nếu Di không giao với bất kỳ đường tròn nào, chọn ngẫu nhiên k điểm trên Di và kết nạp vào tập M k cảm biến đặt tại k điểm vừa chọn. Hình 10: Các ứng viên được kết nạp vào M 29 / 152
Bài toán K-coverage Lựa chọn cảm biến từ tập ứng viên Chọn cảm biến Si từ tập M sao cho Si bao phủ được nhiều mục tiêu trong tập Uncovered nhất. Ví dụ: Hình 11: Thêm cảm biến Si vào tập S Cập nhật: |S| = 1 |Uncovered| = 3 30 / 152
Bài toán K-coverage Lựa chọn cảm biến từ tập ứng viên Chọn cảm biến Si từ tập M sao cho Si bao phủ được nhiều mục tiêu trong tập Uncovered nhất. Ví dụ: Hình 12: Thêm cảm biến Si vào tập S Cập nhật: |S| = 2 |Uncovered| = 3 31 / 152