intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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
15
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

  1. 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
  2. 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
  3. Giới thiệu bài toán K-coverage Hình 8: Mạng cảm biến 2-coverage 14 / 152
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  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 Bài toán K-Coverage Bài toán Maximun Disjoint Set Cover  Thực nghiệm  Kết luận 23 / 152
  13. 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
  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 Bài toán K-Coverage Bài toán Maximun Disjoint Set Cover  Thực nghiệm  Kết luận 25 / 152
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2