Bài giảng Bao phủ mạng không dây: Chương 4 - Bài toán tối ưu thời gian bao phủ của mạng cảm biến

Bài giảng "Bao phủ mạng không dây: Chương 4 - Bài toán tối ưu thời gian bao phủ của mạng cảm biến" được biên soạn với các nội dung chính sau: 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 baseline;... 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 4 - Bài toán tối ưu thời gian bao phủ của mạng cảm biến 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 4 Bài toán tối ưu thời gian bao phủ của mạng cảm biến 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 Giải thuật đề xuất Thực nghiệm 128 / 152 Giới thiệu bài toán  Vấn đề tối đa hóa thời gian sống của Sensor Network cũng là một trong những vấn đề quan trọng trong nghiên cứu mạng cảm biến  Các cảm biến chỉ có một năng lượng nhỏ  Trong thực tế các cảm biến mất năng lượng nhiều vào việc di chuyển hơn là năng lượng để cảm biến các targets  Ý tưởng : Triển khai nhiều lần các sensor di động để đạt được thời gian sống của mạng là lớn nhất 129 / 152 Các nghiên cứu liên quan Trong nghiên cứu 7 , tác giả đã:  Chia bài toán triển khai sensors thành bao phủ mục tiêu (target coverage) và đảm bảo tính kết nối của mạng (network connectivity)  Chứng minh bài toán bao phủ mục tiêu là NP khó  Vấn đề bao phủ : đưa ra giải thuật TV-Greedy đựa trên phân vùng Voronoi của các target. Đưa ra giải thuật giải chính xác cho bài dựa trên phương pháp Hungarian cho trường hợp đặc biệt 7 Z. Liao, J. Wang, S. Zhang, J. Cao, and G. Min, ”Minimizing movement for target coverage and network connectivity in mobile sensor networks”, IEEE Transactions on Parallel and Distributed Systems, vol. 26, no. 7, pp. 1971–1983, Jul 2015 130 / 152 Các nghiên cứu liên quan Trong nghiên cứu 8 , tác giả đã đề cập đến các vấn đề:  Giải quyết vấn đề bao phủ  Giới thiệu thuật toán VABC kết hợp phân vùng Voronoi và tối ưu bầy ong (ABC)  Đưa ra giải thuật V-VABC cải tiến TV-Greedy trong [7] bằng thuật toán VABC 8 A.M. Jagtap*, N.Gomathi, ”Minimizing sensor movement in target coverage problem: A hybrid approach using Voronoi partition and swarm intelligenc”. Bulletin of the polish academy of sciences technical sciences, vol. 65, no. 2, 2017. 131 / 152 Các nghiên cứu liên quan Trong nghiên cứu 9 , tác giả đã giải quyết các vấn đề:  Đưa ra mô hình mạng cảm biến thuần nhất và không thuần nhất  Triển khai các sensor với ràng buộc về thời gian sống  Đưa ra giải thuật DCML cho vấn đề kết nối trong mạng  Mở rộng CCML và DCML ra cho bài bao phủ mục tiêu và bao phủ diện tích 9 Jun Guo, Hamid Jafarkhani, ”Movement-Efficient Sensor Deployment in Wireless Sensor Networks With Limited Communication Range”, IEEE Transactions on Wireless Communications, vol. 18 , no. 7, pp. 3469 - 3484, Jul 2019. 132 / 152 Nhận xét  Các nghiên cứu chưa giải quyết vấn đề tối đa hóa lifetime của mạng 133 / 152 System model Xét miền phẳng W ∗ H: Có m target T = {t1 , t2 , .., tm } đã biết vị trí và n mobile sensor S = {s1 , s2 , .., sn }. Các sensor được phân thành hai loại:  Các sensor đã triển khai trên miền để bao phủ các targets  Các sensor tự do Các sensor có thể chuyển từ trạng thái từ tự do sang đã triển khai, chiều ngược lại không đúng 134 / 152 Hình 49: Ví dụ với miền W × H = 200 × 200 135 / 152 System model Network model: Các sensor có cùng một bán kính cảm biến rs . Một sensor có thể bao phủ nhiều target và một target có thể được bao phủ bởi nhiều sensor. Target được bao phủ khi tồn tại ít nhất một sensor bao phủ nó. Mobility model: các sensor tự do có thể di chuyển và dừng lại tại bất kì vị trí nào trên miền để bao phủ các target. Khoảng cách di chuyển lớn nhất Dmax cần đảm bảo năng lượng di chuyển không vượt qua năng lượng ban đầu. 136 / 152 System model Năng lượng tiêu hao để cảm biến m bit/giây với khoảng cách d là: Es(m, d) =Eelect + Eamp ( m ∗ Eelec + m ∗ εfs ∗ d 2 (d < d0 ) = m ∗ Eelec + m ∗ εamp ∗ d 4 (d ≥ d0 ) efs : Năng lượng tiêu thụ của 1 bit trong vùng khoảng cách nhỏ hơn ngưỡng d0 eamp : Năng lượng tiêu thụ của một bit trong miền có khoảng cách lớn hơn ngưỡng p d0 d0 = efs /eamp Gọi công P suất tiêu thụ năng lượng cảm biến của Sensor sj là ej . ej = Es(mi , di ) với (mi , di ) phụ thuộc các target sensor cảm biến ⇒ Em + ej ∗ time ≤ E với time là thời gian sống của sensor 137 / 152 Mô hình toán học Đầu vào:  Miền A có độ rộng W × H trong mặt phẳng hai chiều  m target: T = {t1 , t2 , .., tm }  n mobile sensor S = {s1 , s2 , .., sn } : nc mobile sensor đã n triển khai o nc = |Sc| Sc = j | j ∈ N ∩ [1, n]; sj đã triển khai . nf mobile sensor tự n do o nf = |Sf | Sf = j | j ∈ N ∩ [1, n]; sj chưa triển khai .  E: năng lượng ban dầu của các sensor 138 / 152 Mô hình toán học Xét lần di chuyển sensor đầu tiên: Với αi là mốc thời gian target i không còn được bao phủ Sensor sj ( j ∈ Sf ) di chuyển tới vị trí mới Dj tại thời điểm βj mất Emj ...