Đề tài Xây dựng K-Barrier trong mạng cảm biến (WSN)

XÂY DỰNG K-BARRIER TRONG MẠNG CẢM BIẾN (WSN) Thành viên nhóm: Phạm Thị Minh Châu Bùi Việt Anh Lê Thị Vân GVHD: TS. Nguyễn Thị Bình Zhang, Y., Sun, X., & Yu, Z. (2018). K-barrier coverage in wireless sensor networks based on immune particle swarm optimisation.  International Journal of Sensor Networks ,  27 (4), 250-258. 1 Nội dung Giới thiệu bài toán Nghiên cứu liên quan Phát biểu bài toán Mô hình bài toán Sử dụng các giải thuật khác để giải quyết bài toán Kết quả thực nghiệm Kết luận 2 Nút cảm biến Trạm thông tin Cảm biến 3 Ứng dụng của mạng cảm biến 4 4 Giới thiệu bài toán Một số khái niệm liên quan: Barrier: hàng rào cảm biến từ biên này đến biên kia để phát hiện đối tượng xâm nhập Mạng bao phủ k-barrier: mọi đường xâm nhập đều bị phát hiện bởi ít nhất k cảm biến Vùng giám sát Đường xâm nhập Hàng rào cảm biến Sensor 5 Một số khái niệm liên quan: Giới thiệu bài toán Weak barrier coverage Strong barrier coverage 6 Giới thiệu bài toán Bao phủ 2-barrier (strong barrier) Ví dụ: 7 Ứng dụng của bao phủ rào chắn Bảo vệ biên giới Bảo vệ cơ sở Giám sát khu vực nguy hiểm 8 Nghiên cứu liên quan [1] Zhang, L., Tang, J., & Zhang, W. (2009, November). Strong barrier coverage with directional sensors. In GLOBECOM 2009-2009 IEEE Global Telecommunications Conference (pp. 1-6). IEEE. • Nghiên cứu strong barrier trong mạng cảm biến có hướng • Giới thiệu đ ồ thị rào chắn có hướng • Sử dụng giải thuật quy hoạch nguyên ILP, tập trung và phân tán [2] Yudong Zhang, Yan Jun, Geng Wei, Lenan Wu (2010). Find multi-objective paths in stochastic networks via chaotic immune PSO. Đề xuất ra cách mã hoá mới cho bài toán K-barrier và mô hình CIPSO [3] Wang, Z., Liao, J., Cao, Q., Qi, H., & Wang, Z. (2013, October). Barrier coverage in hybrid directional sensor networks. In 2013 IEEE 10th International Conference on Mobile Ad-Hoc and Sensor Systems (pp. 222-230). IEEE • Mô hình bài toán trên mạng có hướng lai vô hướng • Sử dụng giải thuật Hungary 9 Nghiên cứu liên quan [4] Wang, Z., Liao, J., Cao, Q., Qi, H., & Wang, Z. (2014). Achieving k-barrier coverage in hybrid directional sensor networks. IEEE Transactions on Mobile Computing, 13(7), 1443-1455. • Đưa ra 3 bài toán: Min-Num-Mobile(k), Max-Num-Barrier và Minimum cost barrier formation ( MCBF) • Sử dụng disjoint paths để giải [5] Wu, F., Gui, Y., Wang, Z., Gao, X., & Chen, G. (2016). A survey on barrier coverage with sensors. Frontiers of Computer Science, 10(6), 968-984. • Survey về mô hình sensor, các vấn đề và khó khăn trong bài toán bao phủ rào chắn [6] Zhang, Y., Sun, X., & Yu, Z. (2017). Solving-Barrier Coverage Problem Using Modified Gravitational Search Algorithm. Mathematical Problems in Engineering, 2017. • Sử dụng giải thuật PSO có trọng lực để giải 10 Phát biểu bài toán 11 Đầu vào: Kích thước vùng giám sát (L x W) Tập các sensor tĩnh đã triển khai trước Thuộc tính các sensor Đầu ra: Số sensor động tối thiểu cần thêm vào để tạo ra k-barrier k-barrier Mô hình bài toán Lập đồ thị WBG (Weighted Barrier Graph) G = (V, E, W) Trong đó: V: tập đỉnh bao gồm biên trái (s), biên phải (t) và sensor tĩnh E = {e(v i , v j )} : tập cạnh nối cặp 2 đỉnh bất kỳ W: E : tập trọng số mỗi cạnh w(v i , v j ): trọng số cạnh nối v i và v j - lượng sensor tối thiểu nằm giữa 2 đỉnh v i , v j 12 Lập đồ thị WBG Trong đó: d(v i , v j ) là khoảng cách Euclid giữa 2 sensor v i , v j l r là đoạn thẳng dài nhất giữa 2 điểm trong phạm vi sensor Mô hình bài toán 13 Biểu diễn bài toán: Trong đó: l một đường đi trong đồ thị (từ s đến t) Nếu w(u, v) thuộc đường đi l : x uvl = 1 Ngược lại: x uvl = 0 Mô hình bài toán 14 Đề xuất: Chiến lược mã hóa particle: Biểu diễn particle Zhang , Y., Jun, Y., Wei, G., & Wu, L. (2010). Find multi-objective paths in stochastic networks via chaotic immune PSO. Expert Systems with Applications, 37(3), 1911-1919 . Thuật toán tối ưu bầy đàn PSO kết hợp với Artificial immune (hệ miễn dịch nhân tạo): Sử dụng cho clone, crossover, mutation => Tăng tính đa dạng quần thể, tăng khả năng thoát khỏi tối ưu cục bộ Mô hình bài toán 15 Biểu diễn particle: Ví dụ: Bài toán xây dựng 3-barrier với 15 sensor Trong đó: Mỗi node: một sensor Nút đích t 1 , t 2 , t 3 Probability: Xác suất chọn nút Mô hình bài toán 16 Biểu diễn particle: Ví dụ: Bài toán xây dựng 3-barrier với 15 sensor Xây dựng đường đi: Với mỗi đường đi: Bắt đầu từ nút nguồn s Chọn nút có xác suất cao nhất vào đường đi Dừng lại khi đạt đến nút đích t Mô hình bài toán 17 Thuật toán PSO: Với particle X i có vận tốc V i tương ứng: Công thức cập nhật vận tốc: Công thức cập nhật vị trí: Trong đó: p ibest : vị trí tốt nhất cá thể đạt được trong quá khứ g ibest : cá thể tốt nhất trong bầy rand 1 , rand 2 : các hệ số ngẫu nhiên trong [0, 1] Mô hình bài toán 18 Artificial immune: Một số định nghĩa mới: Affinity: Trong đó: fit là hàm fitness: Density: Mô hình bài toán 19 Artificial immune: Một số định nghĩa mới: Xác suất tiến hóa P s : Với: Mô hình bài toán 20 Artificial immune: Các toán tử: Giả sử mỗi swarm có N particle Clone: Chọn 20% particle có giá trị affinity lớn nhất vào library Chọn ngẫu nhiên M particle từ library - Tính P s của N+M particle, chọn N particle cho thế hệ tiếp theo Mô hình bài toán 21 Artificial immune: Các toán tử: Crossover: Chọn 30% particle có giá trị affinity nhỏ nhất => twopoint crossover Mutation: Tính rand 1 , rand 2 theo công thức: Mô hình bài toán 22 Mô hình bài toán Giải thuật kết hợp AI-PSO: Bước 1: Khởi tạo swarm Bước 2: Mã hóa các particle Bước 3: Tính giá trị fitness Bước 4: Thực hiện clone Bước 5: Thực hiện crossover Bước 6: Thực hiện mutation Bước 7: Cập nhật vị trí, vận tốc với rand 1 , rand 2 đã tính ở bước trên Bước 8: Lặp lại các bước từ bước 3-7 cho đến khi tìm được lời giải 23 Để có hiểu biết sâu hơn cũng như so sánh được kết quả đã công bố của bài toán, nhóm giải bài toán theo 2 giải thuật khác: GA , PSO Mô hình bài toán: Đồ thị WBG Biểu diễn cá thể: Sử dụng chiến lược mã hóa như AI-PSO Sử dụng các giải thuật khác 24 Giải bài toán sử dụng GA B ư ớc 1: Khởi tạo tham số B ư ớc 2: Mã hoá quần thể B ư ớc 3: Lai ghép ox và đột biến đảo đoạn B ư ớc 4: Tìm k-barrier, tính fitness, sử dụng bánh xe Roulette chọn ra N cá thể cho thế hệ tiếp theo B ư ớc 5: Lặp lại b ư ớc 3 và 4 cho đến khi gặp điều kiện dừng 25 Giải bài toán sử dụng PSO Bước 1: Khởi tạo tham số Bước 2: Mã hóa quần thể Bước 3: Xây dựng k-barrier Bước 4: Tính fitness Bước 5: Cập nhật vận tốc, vị trí cho mỗi cá thể; pbest, gbest Bước 6: Lặp lại từ bước 3 đến bước 5 cho đến khi gặp điều kiện dừng 26 Bộ dữ liệu sử dụng Bộ dữ liệu đ ư ợc lấy từ nhóm Gồm 50, 80, 110, 140, 170, 200 đỉnh Góc  = 60, 180 Chiều rộng w, chiều cao h, số barrier tĩnh là n và góc  Vị trí toạ độ của sensor; bán kính hoạt động của sersor, góc (trong đó 2  =  ), góc  (góc hợp bởi đường phân giác của góc sensor hoạt động và đường Ox) 27 Kết quả thực nghiệm 28 Kết quả thực nghiệm 29 Kết quả thực nghiệm 30 Kết luận Các giải thuật thông th ư ờng như GA hay PSO đều cho ra kết quả không đ ư ợc tốt bằng AI-PSO bời vì kết quả chạy bằng cách giải thuật trên th ư ờng đi vào cục bộ, không đa dạng Thời gian chạy của cả 3 giải thuật đều lâu, ch ư a đi đến lời giải tối ư u của bài toán Kết hợp các giải thuật tiến hoá với các thuật toán heuristic để đạt hiệu quả cao h ơ n trong việc tìm lời giải tối ư u Tìm kiếm thêm các ph ư ơng pháp mã hoá mới 31 THANKS FOR LISTENING! 32