Bài giảng Bao phủ mạng không dây: Chương 3 - Bài toán Q-coverage và Q-connectivity 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 3 - Bài toán Q-coverage và Q-connectivity 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 Q-coverage và Q-connectivity; Các nghiên cứu liên quan; Mô hình bài toán Q-coverage và Q-connectivity;... 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 3 - Bài toán Q-coverage và Q-connectivity 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 3 Bài toán Q-coverage và Q-connectivity 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 4 Bài toán tối ưu thời gian bao phủ của mạng cảm biến 75 / 152 Bài toán Q-coverage  Bài toán tổng quát hơn của bài K-coverage: mỗi mục tiêu có độ quan trọng khác nhau. 76 / 152 Bài toán Q-coverage Hình 31: Mô hình mạng cảm biến Q-coverage 77 / 152 Bài toán Q-connectivity  Trong bài Q-coverage, mục tiêu được theo dõi bởi nhiều cảm biến, nhưng có thể chỉ có 1 đường kết nối đến trạm cơ sở.  Nếu một nút bất kỳ trên đường truyền bị chết, kết nối giữa mục tiêu và trạm cơ sở sẽ không còn  Để mạng thực sự có khả năng chịu lỗi, cần xây dựng nhiều đường đi hơn từ mục tiêu về trạm cơ sở.  Nhận xét: Nếu mạng cảm biến là Q-connectivity, mạng cũng là Q-coverage. 78 / 152 Bài toán Q-connectivity Hình 32: Mô hình mạng cảm biến Q-coverage kết hợp với Q-connectivity 79 / 152 Các nghiên cứu liên quan Trong nghiên cứu4 , tác giả đã trình bày:  Phát biểu và mô hình hóa Q-coverage trong mạng cảm biến không dây  Đề xuất thuật toán heuristic để giải quyết bài toán lập lịch cho các cảm biến từ tập n cảm biến và m mục tiêu cho trước để tối đa hóa thời gian sống của mạng và thoả mãn Q-coverage. 4 Manju Chaudhary, Arun K. Pujari, 'Q-Coverage Problem in Wireless Sensor Networks', In Proceedings of the 10th International Conference on Distributed Computing and Networking, 2009. 80 / 152 Các nghiên cứu liên quan Trong bài báo5 , tác giả mô hình hóa bài toán lập lịch cho các cảm biến để tối đa hóa thời gian sống của mạng và thoả mãn Q-coverage. 5 Alok Singha, André Rossib, Marc Sevauxb, 'Matheuristic approaches for Q-coverage problem versions in wireless sensor networks', Engineering Optimization, vol. 45, no. 5, pp. 609-626, Apr 2012. 81 / 152 Các nghiên cứu liên quan Trong nghiên cứu6 , tác giả đã xem xet các vấn đề:  Triển khai sensor cho 1, k, q − coverage.  Lên lịch bật tắt cho các cụm sensor. Tuy nhiên, phần triển khai còn đơn giản. 6 S. Mini, S. K. Udgata and S. L. Sabat, 'Sensor Deployment and Scheduling for Target Coverage Problem in Wireless Sensor Networks', in IEEE Sensors Journal, vol. 14, no. 3, pp. 636-644, March 2014. 82 / 152 Nhận xét Các nghiên cứu kể trên có đặc điểm chung:  Giải quyết bài toán lập lịch cho một số cảm biến đã được triển khai từ trước.  Chưa quan tâm đến vấn đề kết nối. Đề xuất:  Tự triển khai các sensor.  Quan tâm đến vấn đề kết nối 83 / 152 Mô hình bài toán  Cho miền cần theo dõi có kích thước WxH.  B = (Bx , By ) là tọa độ của trạm cơ sở.  T = {t1 , t2 , · · · , tNT } là tập mục tiêu cần theo dõi, với ti = (xi , yi ) là vị trí của mục tiêu ti .  Q = {q1 , q2 , · · · , qNT } với qi là mức độ quan trọng của mục tiêu ti .  Rs là bán kính cảm nhận của các cảm biến.  Rc là bán kính truyền của các cảm biến.  Yêu cầu: Tìm cách triển khai các cảm biến và nút chuyển tiếp sao cho mỗi mục tiêu ti có tối thiểu qi kết nối phân biệt (không chung bất kỳ nút trong nào) đến trạm cơ sở và tổng số cảm biến và nút chuyển tiếp được sử dụng là nhỏ nhất. 84 / 152 Giải thuật đề xuất Để giải quyết bài toán, ta chia bài toán thành 2 pha:  Pha I: Triển khai các cảm biến để tạo thành mạng Q-coverage.  Pha II: Từ các cảm biến đã triển khai, xây dựng Q-connectivity từ các mục tiêu về trạm cơ sở. 85 / 152 Giải thuật đề xuất Hình 33: Pha I: Triển khai Q-coverage 86 / 152 Giải thuật đề xuất Hình 34: Pha II: Xây dựng Q-connectivity 87 / 152 Pha I: Triển khai Q-coverage  Cho miền cần theo dõi có kích thước WxH.  T = {t1 , t2 , · · · , tNT } là tập mục tiêu cần theo dõi, với ti = (xi , yi ) là vị trí của mục tiêu ti .  Q = {q1 , q2 , · · · , qNT } với qi là mức độ quan trọng của mục tiêu ti .  Rs là bán kính cảm nhận của các cảm biến.  Yêu cầu: Tìm cách triển khai các cảm biến sao cho mỗi mục tiêu ti được bao phủ bởi tối thiểu qi cảm biến và số cảm biến được sử dụng là nhỏ nhất. 88 / 152 Giải thuật đề xuất Nhận xét:  Nếu có một lời giải tối ưu, ta luôn thu được một lời giải tối ưu khác bằng cách dịch chuyển các cảm biến sao cho có 2 mục tiêu nằm trên giới hạn phủ của cảm biến đó, trừ khi cảm biến bao phủ duy nhất một mục tiêu bị cô lập.  Gọi các điểm khả thi Oij là các điểm mà targeti , targetj nằm trên đường tròn tâm Oij , bán kính Rs . Với mỗi cặp targeti và targetj sẽ có thể có 0 hoặc 1 hoặc 2 điểm khả thi.  Nếu 1 mục tiêu không thể ghép cặp để tìm điểm khả thi thì ta sẽ tạo một điểm khả thi tại chính điểm đó.  Ta chỉ ...