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

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

Thêm vào BST

Báo xấu

13
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 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!

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 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 E −Em năng lượng Sensor sj có thời gian sống tiếp là δj = ej j Γi là tập các j mà sj tại vị trí Dj bao phủ target i ni1 = max {βj + δj , αi } ∀j ∈ Γi , i = 1, 2, ..., n Chuyển chỉ số của các sensor di chuyển để bao phủ target từ Sf sang Sc Lần di chuyển n sensor thứo k: k k−1 ni = max βj + δj , ni ∀j ∈ Γi tại lần di chuyển thứ k Mục tiêu: maximize p = minnK i ∀i = 1, 2, .., n; K: lần di chuyển cuối có thể kéo dài thời gian bao phủ của mạng 139 / 152
Nhận xét Xuất phát từ ý tưởng : "Nếu tồn tại một cách di chuyển để thời gian sống là p2 thì cũng tồn tại cách cách di chuyển để thời gian sống của mạng là p1 < p2" Kiểm tra sự tồn tại của một cách di chuyển trong thời gian p bằng cách Heuristic Coi việc di chuyển với khoảng cách nhỏ nhất sẽ cho thời gian sống tốt, từ đó so sánh với giá trị p Nếu lớn hơn p thì tức là tồn tại cách di chuyển trong thời gian p 140 / 152
Thuật toán chặt nhị phân xác định thời gian sống tối đa Algorithm 2: Tối đa thời gian sống trong 1 lần triển khai Result: Write here the result Khởi tạo vị trí đặt các cảm biến; Khởi tạo vị trí đặt các mục tiêu; min = 0, max = timeMax ; while (max - min) < do p = (min + max)/2 ; if Tồn tại một cách triển khai cảm biến trong thời gian p then min = p ; else max = p; end end 141 / 152
Giải thuật base-line dùng trong hàm kiểm tra Heuristic Tối thiểu quãng đường di chuyển của cảm biến bằng cách tối thiểu số lượng cảm biến phải di chuyển Tại thời điểm ban đầu thì một số mục tiêu đã được bao phủ Bỏ qua các mục tiêu đã được bao phủ khi mới triển khai Đối với các mục tiêu chưa được bao phủ, ta tìm các clique. Sau khi tìm các clique thì với mỗi clique chỉ dùng 1 cảm biến đến để bao phủ clique đó. Ở đây dùng thuật toán Hungarian mở rộng. Bằng cách này thì các cảm biến dùng để triển khai là nhỏ nhất 142 / 152
Giải thuật baseline Hình 50: Vị trí khởi tạo và lời giải của thuật toán baseline 143 / 152
Giải thuật base-line Hình 51: Thuật toán có thể không tối ưu 144 / 152
Một thuật toán Heuristic cho TCOV Một số bài báo đã đề xuất các giải thuật cho bài toán tối thiểu di chuyển của cảm biến Thuật toán TV-Greedy : Phân vùng Voronoi các mục tiêu sau đó bao, sau đó bao phủ mục tiêu bằng cảm biến gần nhất Thuật toán V-VABC : Cải tiến thuật toán TV-Greedy trong một số trường hợp bằng thuật toán VABC 145 / 152
Phân vùng Voronoi Định nghĩa : Cho P là tập hợp các điểm nằm trên mặt phẳng Biểu đồ Voronoi của P là một cách phân tách mặt phẳng ra thành nhiều miền, mỗi điểm ứng với một miền Voronoi Các điểm thuộc miền Voronoi của s là tập hợp các điểm có khoảng cách gần s hơn các điểm tỏng tập P Tính chất Các điểm thuộc Voronoi của một vùng thì gần tâm của vùng Voronoi đó hơn là các tâm của vùng Voronoi khác Hai điểm gần nhất trong tập hợp các điểm ứng với 2 ô Voronoi liền kề nhau 146 / 152
Phân vùng Voronoi Hình 52: Ví dụ phân cùng Voronoi 147 / 152