Đề tài Đảm bảo Q – Coverage nhằm tối ưu thời gian sống của mạng và cân bằng tải trong mạng

Đảm bảo Q – Coverage nhằm tối ưu thời gian sống của mạng và cân bằng tải trong mạng Nhóm thực hiện: Nguyễn Trung Đức Nguyễn Thịnh Vượng GVHD: PGS.TS.Huỳnh Thị Thanh Bình Nội dung Giới thiệu bài toán Các nghiên cứu liên quan Xây dựng mô hình bài toán Phương án đề xuất Thực nghiệm Kết luận Giới thiệu bài toán Hình 1: Ví dụ một mạng cảm biến không dây Giới thiệu bài toán Giới thiệu bài toán Ứng dụng chính của mạng cảm biến là theo dõi các target bằng cách triển khai các sensor. Một target được bao phủ nếu nó nằm trong vùng bán kính cảm nhận của 1 cảm biến. Tuy nhiên mỗi sensor thì sẽ có một giới hạn năng l ư ợng nhất định, và mỗi điểm target thì có 1 mức độ quan trọng nhất định. Giới thiệu bài toán Vì vậy nên mạng cảm biến Q-coverage đ ư ợc triển khai để đảm bảo cho từng mục tiêu với mức độ quan trọng khác nhau, công suất hoạt động khác nhau sẽ đ ư ợc bao phủ bởi 1 số l ư ợng cảm biến khác nhau. Gọi vector Q={q 1 , q 2 ,,q m } là yêu cầu bao phủ cho m target, bài toán Q- coverage có liên quan đến việc tối đa hóa tuổi thọ của mạng khi có ít nhất q j sensor bao phủ target thứ j tại mọi thời điểm. Q-coverage là bài toán NP-complete và đ ư ợc giải quyết bằng một thuật toán heuristic. Nội dung Giới thiệu bài toán Các nghiên cứu liên quan Xây dựng mô hình bài toán Phương án đề xuất Thực nghiệm Kết luận Các nghiên cứu liên quan [1]. Manju Chaudhary and Arun K. Pujari, Q-Coverage Problem in Wireless Sensor Networks . International Conference on Distributed Computing and Networking (2008) Phát biểu và mô hình hóa vấn đề Q-coverage trong WSNs, và đề xuất 1 thuật toán heuristic để giải quyết bài toán xây dựng và chọn sử dụng ra tập các Q-cover từ tập n sensor đầu vào và m target đầu vào để tối đa hóa thời gian sống của mạng. Các nghiên cứu liên quan [ 2]. Matheuristic approaches for Q-coverage problem versions in wireless sensor networks Alok Singha, André Rossib and Marc Sevauxb in Engineering Optimization. (2013) Tác giả mô hình hóa vấn đề Q-coverage problem và lên lịch hoạt động của các cảm biến theo cách sao cho tuổi thọ của mạng được tối đa hóa theo giới hạn đó, trong toàn bộ thời gian tồn tại, mỗi mục tiêu k được bao phủ bởi ít nhất q k cảm bi ến . Và mô hình hóa theo 3 phiên bản. Nội dung Giới thiệu bài toán Các nghiên cứu liên quan Xây dựng mô hình bài toán Phương án đề xuất Thực nghiệm Kết luận Xây dựng mô hình bài toán Xây dựng bài toán chia thành 2 pha: Pha 1: Tối ưu thời gian sống của mạng thỏa mãn Q – Coverage. Pha 2: Kết nối Sensor với Sink giúp cân bằng tải trong mạng. Xây dựng mô hình bài toán Hình 3: Mô hình mạng bao phủ mục tiêu Q - Coverage Pha 1: Tối ưu thời gian sống của mạng thỏa mãn Q – Coverage. Đầu vào: A = WxH Miền diện tích cần theo dõi T = { t 1 , t 2 , t 3 ,, t m } là tập target đầu vào. Với t i = { t ix ,t iy } là tọa độ 2 chiều của t i. Q = { q 1 ,q 2 ,,q m } tập giá trị sao cho q i là số sensor tối thiểu mà target t i đ ư ợc bao phủ. B = {b 1 , b 2 , b 3 ,, b k } là tập giá trị sao cho b i là năng lượng ban đầu cấp cho cảm biến s i . R là bán kính cảm nhận của sensor Đầu ra: Vị trí triển khai các cảm biến S = { s 1 , s 2 ,,s n } Ràng buộc: Target t i đ ư ợc q i sensor bao phủ Mục tiêu: Tối ưu thời gian sống của mạng thỏa mãn điều kiện Q - Coverage  Ví dụ: Q-coverage với Q={3,3,2,1,4}  Pha 2: Kết nối Sink giúp cân bằng tải trong mạng. Đầu vào : Vị trí các cảm biến đã triển khai sau pha 1: S ={s 1 ,s 2 ,,s n } Sensing range: bán kính truyền R Tập ràng buộc Q Tập các Sink: C={c 1 ,c 2 ,,c k } Đầu ra: Ma trận cho biết kết nối của sensor tới sink tương ứng Mục tiêu: Cân bằng tải trong mạng Ràng buộc: Tất cả các sensor bao phủ 1 target không cùng kết nối với 1 sink Nội dung Giới thiệu bài toán Các nghiên cứu liên quan Xây dựng mô hình bài toán Phương án đề xuất Thực nghiệm Kết luận Pha 1: Heuristic with High Energy and Small Lifetime (HESL) Định nghĩa ma trận M: Pha 1: Heuristic with High Energy and Small Lifetime (HESL) Một Q -Cover S là nhỏ nhất nếu đối với bất kỳ phủ Q nào S ′ ⊆ S khi và chỉ khi S ′ = S Tuổi thọ tối đa cho phép của Q-cover S là tuổi thọ nhỏ nhất hiện có cảm biến của nó. Như vậy : Pha 1: Heuristic with High Energy and Small Lifetime (HESL) Bước 1: Ban đầu, ta chỉ định lượng pin khả dụng cho mỗi cảm biến. Heuristic tạo ra Q-cover bằng cách chọn lặp đi lặp lại các cảm biến có thời lượng pin còn lại cao nhất cho đến khi tất cả các mục tiêu được bao phủ theo vectơ phủ Q . Q – Cover thu được không phải là nhỏ nhất, vì vậy chúng ta tối giản hóa nó bằng cách loại bỏ một cảm biến tại một thời điểm và sau đó kiểm tra xem nó có phải là Q-cover hay không. Pha 1: Heuristic with High Energy and Small Lifetime (HESL) Bước 2 : Để tránh việc tạo lặp lại cùng một phủ Q trong các lần lặp lại liên tiếp, mức độ ưu tiên của cảm biến giảm khi nó đã được sử dụng trong phủ Q khác. D o đó , cấu trúc tham lam của phủ Q trong lần lặp tiếp theo sẽ cố gắng tránh cảm biến này . Pha 1: Heuristic with High Energy and Small Lifetime (HESL) Ví dụ: Đầu vào: Q = {1, 2, 4, 5, 6} B = {1, 1, 1, 1,, 1, 1} Ma trận M: Pha 1: Heuristic with High Energy and Small Lifetime (HESL) Pha 1: Heuristic with High Energy and Small Lifetime (HESL) Pha 1: Heuristic with High Energy and Small Lifetime (HESL) Pha 2: Giải thuật di truyền Khởi tạo quần thể Đánh giá độ thích nghi Sinh quần thể mới Chọn lọc Kiểm tra điều kiện dừng Kết thúc Pha 2: Giải thuật di truyền Gọi m là số cảm biến có được sau pha 1 . Mã hóa cá thể Một cá thể được mã hóa thành một ma trận X [m ][k] Trong đó: Mỗi phần tử trong ma trận X đại diện cho cảm biến si có kết nối đến sink j hay không. Pha 2: Giải thuật di truyền Xây dựng hàm thích nghi(fitness) . Mỗi một cá thể cần có một hàm đánh giá để đánh giá xem cá thể đó có thực sự tốt hay không. Ở đây, hàm đánh giá được tính bằng cách lấy năng lượng cao nhất trừ đi năng lượng thấp nhất trong 1 cá thể. Hàm phạt P() khi nhiều sensor trong 1 vùng phủ cùng nối đến 1 sink. cost = (MaxE - MinE) + P() Pha 2: Giải thuật di truyền Bước 1: Khởi tạo quần thể 1 cách ngẫu nhiên Ở phần này mỗi ma trận X sẽ có các phần tử X [i ][j] được khởi tạo ngẫu nhiên theo binary-bit 0,1. Đánh giá độ thích nghi của quần thể khởi tạo (bestfit_init) Pha 2: Giải thuật di truyền Bước 2: Lai ghép Hình 4 : Chọn block lai ghép Pha 2: Giải thuật di truyền Bước 2: Lai ghép Hình 5 : Sau khi lai ghép Pha 2: Giải thuật di truyền Bước 2: Lai ghép Sau khi lai ghép có quần thể mới => Sắp xếp cá thể theo độ thích nghi => Chọn 50% cá thể tốt nhất Hoặc chọn lọc theo vòng quay roulette Pha 2: Giải thuật di truyền Bước 3: Đột biến (trên 1/n cá thể) Chọn ngẫu nhiên 2 block trong cá thể và hoán vị 2 block đó. Trước đột biến: Pha 2: Giải thuật di truyền Bước 3: Đột biến() Sau đột biến: Pha 2: Giải thuật di truyền Bước 4: Kiểm tra điều kiện hội tụ Nếu đã hội tụ => Đưa ra kết quả Nếu chưa hội tụ => Tiếp tục tiến hóa quần thể Nếu chưa hội tụ sau rất nhiều vòng lặp hoặc có dấu hiệu không hội tụ => Kiểm tra lại thuật toán Nội dung Giới thiệu bài toán Các nghiên cứu liên quan Xây dựng mô hình bài toán Phương án đề xuất Thực nghiệm Kết luận Môi trường Chip : i7 – 8700 (~3.5GHz) Ram : 8Gb Card: GTX 1060 Ngôn ngữ: Python IDE: Pycharm Dữ liệu thực nghiệm và kết quả Bộ dữ liệu được sinh ngẫu nhiên: + Tọa độ được sinh đảm bảo bao phủ các trường hợp khác nhau + Tập Q được sinh 1 cách ngẫu nhiên thực sự Tuy chưa so sánh được với các nghiên cứu đã có nhưng đã bao phủ hầu hết các trường hợp. Kết quả Hình 6: Kết quả thực tế của pha 1 Kết quả Hình 7: Kết quả khi bỏ phần diện tích phủ của Sensor Kết quả Hình 8: Kết quả với số Target tăng dần Kết quả Hình 9: Kết quả vói số Sensor tăng dần Kết quả Hình 10: Kết quả của quá trình tiến hóa Kết quả Hình 10: Kết quả thực tế của pha 2 Nội dung Giới thiệu bài toán Các nghiên cứu liên quan Xây dựng mô hình bài toán Phương án đề xuất Thực nghiệm Kết luận Kết luận Trong bài toán này chúng ta đã giải quyết bài toán NP - đầy đủ bằng thuật toán heuristic HESL. Chúng em đề xuất thuật toán di truyền để bổ sung thêm kết nối từ sensor tới các sink giúp cân bằng tải trong mạng và tối ưu thời gian sống của mạng. THANK YOU FOR YOUR ATTENTION!