Đề tài Tối ưu hóa thời gian sống của mạng cảm biến không dây

Tối ưu hóa thời gian sống của mạng cảm biến không dây Giảng viên hướng dẫn : PGS.TS Huỳnh Thị Thanh Bình Sinh viên thực hiện : Từ Hoàng Giang MSSV: 20183518 Nguyễn Duy Khánh MSSV: 20183564 3 Nội dung 1. Tổng quan về mạng cảm biến không dây 2. Giới thiệu bài toán 3. Các nghiên cứu liên quan 4. Mô hình bài toán 5. Giải thuật đề xuất 6. Thực nghiệm 7. Kết luận 4 Nội dung 1. Tổng quan về mạng cảm biến không dây 1.1 Giới thiệu về mạng cảm biến 1.2 Ứng dụng mạng cảm biến 2. Giới thiệu bài toán 3. Các nghiên cứu liên quan 4. Mô hình bài toán 5. Giải thuật đề xuất 6. Thực nghiệm 7. Kết luận 5 1.1 Giới thiệu về mạng cảm biến Hình 1 : Ví dụ về mạng cảm biến không dây (WSN – Wireless Sensor Network) 6 Nội dung 1. Tổng quan về mạng cảm biến không dây 1.1 Giới thiệu về mạng cảm biến 1.2 Ứng dụng mạng cảm biến 2. Giới thiệu bài toán 3. Các nghiên cứu liên quan 4. Mô hình bài toán 5. Giải thuật đề xuất 6. Thực nghiệm 7. Kết luận 7 1.2 Ứng dụng của mạng cảm biến không dây M ạ ng c ả m bi ến không dây đượ c ứ ng d ụ ng nhi ề u trong th ự c t ế như : G iám sát môi trườ ng C ảnh báo thiên tai Giao thông thông minh Theo dõi và chăm sóc sức khỏe Dây chuyền sản xuất 8 Nội Dung 1. Tổng quan về mạng cảm biến không dây 1.1 Giới thiệu về mạng cảm biến 1.2 Ứng dụng mạng cảm biến 2. Giới thiệu bài toán 3. Các nghiên cứu liên quan 4. Mô hình bài toán 5. Giải thuật đề xuất 6. Thực nghiệm 7. Kết luận 9 2. 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ỏ Hầu hết các công trình đều xác định thời gian tồn tại của mạng là thời gian khi nút cảm biến đầu tiên sử dụng hết năng lượng của nó Ý Tưởng : Triển khai các sensor xếp chồng lên nhau giúp tăng thời gian sống của mạng 10 Nội Dung 1. Tổng quan về mạng cảm biến không dây 1.1 Giới thiệu về mạng cảm biến 1.2 Ứng dụng mạng cảm biến 2. Giới thiệu bài toán 3. Các nghiên cứu liên quan 4. Mô hình bài toán 5. Giải thuật đề xuất 6. Thực nghiệm 7. Kết luận 11 3. Các Nghiên Cứu liên quan [1] S. Mini, Siba K. Udgata, and Samrat L. Sabat. (2014). Sensor Deployment and Scheduling for Target Coverage Problem in Wireless Sensor Networks, IEEE SENSORS JOURNAL, VOL. 14, NO. 3, MARCH 2014 [2] Mohamed El-Sherif, Yasmine Fahmy, Hanan Kamal (2018). Lifetime Maximization of Disjoint Wireless Sensor Networks using Multiobjective Genetic Algorithm, IET Research Journals, pp. 1–8 c The Institution of Engineering and Technology 2015 [3] Mohamed Elhoseny, Alaa Tharwat, Ahmed Farouk, and Aboul Ella Hassanien (2017) : K-Coverage Model based on Genetic Algorithm to extend WSN lifetime 12 3. Các Nghiên Cứu liên quan Trong nghiên cứu [1] tác giả tìm tập bao phủ lớn nhất và giải quyết vấn đề tiêu tốn năng lượng Trong nghiên cứu [2] tác giả đã : Triển khai cảm biến sao cho thời gian sống của mạng là lớn nhất Lập lịch cho cảm biến để tối ưu thời gian sống của mạng Trong nghiên cứu [3] tác giả đề xuất mô hình bao phủ K dựa trên Thuật toán di truyền (GA) để kéo dài thời gian tồn tại của WSN 13 Nội Dung 1. Tổng quan về mạng cảm biến không dây 1.1 Giới thiệu về mạng cảm biến 1.2 Ứng dụng mạng cảm biến 2. Giới thiệu bài toán 3. Các nghiên cứu liên quan 4. Mô hình bài toán 5. Giải thuật đề xuất 6. Thực nghiệm 7. Kết luận 14 4. Mô hình bài toán Đầu vào: Cho miền cần theo dõi có kích thước WxH (1000*1000). Tập target Tập sensor có bán kính cảm nhận Base Station đặt tại trung tâm của miền Đầu ra : Vị trí tập m sensor Số sensor chồng lên nhau ở mỗi vị trí 15 4. Mô hình bài toán Ràng buộc : Mỗi target được bao phủ bởi ít nhất 1 sensor Mục tiêu : Tối ưu thời gian sống của mạng dựa trên thời gian sống của mỗi sensor Công thức năng lượng của sensor Năng lượng ban đầu của mỗi sensor là Với : - là năng lượng nghỉ của sensor - l là số bit truyền đi mỗi s đến base - d là khoảng cách từ sensor tới base 16 4. Mô hình bài toán Chia bài toán làm 2 pha Pha 1 : Giải bài toán bao phủ mạng ( mỗi target được bao phủ bởi ít nhất 1 sensor) Tìm cách đặt sensor sao cho có thể bao phủ mạng và gần base-station nhất có thể Tối ưu số sensor hết mức có thể Pha 2 : Dùng GA để tạo ra cover tối ưu  Pha 3 : Dùng GA để cân bằng tải cho các sensor bao phủ cùng 1 target 17 Nội Dung 1. Tổng quan về mạng cảm biến không dây 1.1 Giới thiệu về mạng cảm biến 1.2 Ứng dụng mạng cảm biến 2. Giới thiệu bài toán 3. Các nghiên cứu liên quan 4. Mô hình bài toán 5 . Giải thuật đề xuất 5.1 Bài toán bao phủ mạng 5.2 Dùng GA để tạo cover tối ưu 5.3 Dùng GA để cân bằng tải  6. Thực nghiệm 7. Kết luận 18 5.1 Bài toán bao phủ mạng Các bước thực hiện  B1 : Xây dựng 1 tập vị trí các sensor tối ưu B2 : Lược bỏ sensor dư thừa B3 : Tìm ra các cover tối thiểu B4 : Lặp lại bước 3 để tìm ra nhiều cover khác nhau 19 5.1 Bài toán bao phủ mạng Xây dựng tập vị trí sensor tối ưu Giả sử tại mỗi targer đặt một đường tròn bán kính R Với mỗi cặp và giao nhau tại d điểm giao (d ∈ {1, 2}) 20 5.1 Bài toán bao phủ mạng Xây dựng tập vị trí sensor tối ưu Nếu không giao với đường tròn nào thì chọn vị trí đặt sensor bằng cách lấy giao của đường thẳng nối từ tâm của đường tròn đến base-station 21 5.1 Bài toán bao phủ mạng Xây dựng tập vị trí sensor tối ưu Công thức xác định vị trị tung độ cao nhất của miền (của 2 đường tròn giao nhau) Giả sử d1, d2 là các giao điểm của 2 đường tròn , với tọa độ tâm lần lượt là ( và ( TH1 : Nếu : | > R thì = max , ) ; = min , ) | < R thì = = TH2 : Ngược lại cho 22 5.1 Bài toán bao phủ mạng Xây dựng tập vị trí sensor tối ưu C hia nhỏ khoảng giao nhau bởi các đường thẳng song song với trục hoành Tỷ lệ chia giữa khoảng cách và số điểm tương ứng là 2R:1000khi đó khoảng cách giữa mỗi điểm là ta sẽ thu được số điểm tương ứng là * ( - 23 5.1 Bài toán bao phủ mạng Xây dựng tập vị trí sensor tối ưu Từ mỗi đường thẳng xác định điểm có khoảng cách nhỏ nhất đến base_station. Chọn điểm có khoảng cách đến base_station nhỏ nhất trong tất cả các đường thẳng để đặt sensor. 24 5.1 Bài toán bao phủ mạng Lược bỏ sensor dư thừa Bước 1 : Duyệt mỗi target để xác định các sensor bao phủ Bước 2 : Với mỗi tập duyệt mỗi sensor có trong tập để tìm ra tập các với j là ký hiệu của sensor tương ứng Bước 3 : Lược bỏ sensor Bước 4 : Quay lại bước 1 cho đến khi tất cả được duyệt 25 5.1 Bài toán bao phủ mạng Lược bỏ Sensor dư thừa Bước 1 : Duyệt mỗi target để xác định các sensor bao phủ (i tương ứng với sensor) = {1,2}, = {1,2}, = {2} 26 5.1 Bài toán bao phủ mạng Lược bỏ sensor dư thừa Bước 2 : Với mỗi tập duyệt mỗi sensor có trong tập để tìm ra tập các với j là ký hiệu của sensor tương ứng Với ta có : = {1,2}, = {1,2,3} 27 5.1 Bài toán bao phủ mạng Lược bỏ sensor dư thừa B3 : Lược bỏ sensor Từ các tập từ bước 2 tìm các tập là tập con của nhau (với mỗi ) Ví dụ : B1 ⸦ B2 TH1 : và là 2 sensor có cùng tập bao phủ - Nếu | - | > 1 thì : Giữ lại sensor nếu > Giữ lại sensor nếu < - Nếu | - | > 1 giữ nguyên cả 2 sensor TH2 : và là 2 sensor có tập bao phủ ⸦ Nếu ( - )> 1 thì bỏ Ví dụ : B1 ⸦ B2 và có ( - )> 1 ta lược bỏ sensor 28 5.1 Bài toán bao phủ mạng Lược bỏ Sensor dư thừa Kết quả : Tập vị trí các sensor S = {( , ) ,( , ), . . .,( , )} Ví dụ khi lược bỏ sensor dư thừa 29 5.1 Bài toán bao phủ mạng Tìm ra cover tối thiểu Đề xuất sử dụng thuật toán tham lam Các bước thực hiện : Bước 1 : Tính toán cho mỗi sensor 1 trọng số ưu tiên – weight assignment Bước 2 : Thêm sensor vào tập cover dựa theo trọng số ưu tiên Bước 3 : Cập nhật lại trọng số ưu tiên Bước 4 : Lặp lại bước 2 cho đến khi tìm được 1 cover 30 5.1 Bài toán bao phủ mạng Thuật toán tham lam tìm cover tối thiểu Ký hiệu : Mảng V gồm các phần tử tướng ứng là những target mà sensor bao phủ Ví dụ : V = {(0,1,2), (0,3,4), (1,5) ,.....} Hay : bao phủ target 1, 2, 3 bao phủ target 0, 3, 4 bao phủ target 1, 5 Covered : Mảng thể hiện số sensor bao phủ đối với mỗi target Ví dụ : Covered [9] = 2 => Target 9 có 2 sensor thuộc Cover bao phủ nó Cover : Mảng đầu ra gồm tập các sensor ( rút ra từ V) Lúc đầu cover rỗng không có phần tử nào 31 5.1 Bài toán bao phủ mạng Thuật toán tham lam Bước 1 : Tính độ ưu tiên cho mỗi phần tử trong VTS Ký hiệu :- là trọng số tương ứng của sensor - là số lượng target nằm trong nhưng chưa được bao phủ ; là số phần tử của - là tổng khoảng cách của các target chưa được bao phủ của phần tử đến base - khoảng cách của sensor đang xét đến base xác định bởi công thức : 32 5.1 Bài toán bao phủ mạng Thuật toán tham lam Bước 2 : Thêm phần tử vào Cover dựa theo độ ưu tiên Bước 3 : Cập nhật lại trọng số ưu tiên Cập nhật lại trọng số ưu tiên sau bước 2 Cập nhật lại mảng Covered Bước 4 : Lặp lại bước 2 cho đến khi tìm được 1 cover Khi các phần tử của mảng Covered đều >= 1 thì dừng thuật toán 33 Nội Dung 1. Tổng quan về mạng cảm biến không dây 1.1 Giới thiệu về mạng cảm biến 1.2 Ứng dụng mạng cảm biến 2. Giới thiệu bài toán 3. Các nghiên cứu liên quan 4. Mô hình bài toán 5 . Giải thuật đề xuất 5.1 Bài toán bao phủ mạng 5.2 Dùng GA để tạo cover tối ưu 5.3 Dùng GA để cân bằng tải  6. Thực nghiệm 7. Kết luận 34 5.2 Dùng GA để tìm cover tối ưu Bài toán xếp chồng sensor Đầu vào : Tập vị trí cần đặt sensor , cách cân bằng tải cho các vị trí đặt Đầu ra : Số lượng sensor chồng lên nhau tại mỗi vị trí Ví dụ : 35 5.2 Dùng GA để tìm cover tối ưu Ý tưởng Với mỗi một vị trí đặt sensor và 1 cách cân bằng tải sẽ có tương ứng 1 số lượng sensor xếp chồng lên nhau (có thể khác nhau ở mỗi ví trí ) M ỗi tập sensor xếp chồng như vậy, chỉ cho 1 sensor active một lúc, các sensor khác ở trạng thái nghỉ Khi sensor đang active bị hết năng lượng thì lại lấy 1 sensor trong số các sensor xếp trồng và kích hoạt nó 36 5.2 Dùng GA để tìm cover tối ưu Ý tưởng Với mỗi một vị trí đặt sensor và 1 cách cân bằng tải sẽ có tương ứng 1 số lượng sensor xếp chồng lên nhau (có thể khác nhau ở mỗi ví trí ) M ỗi tập sensor xếp chồng như vậy, chỉ cho 1 sensor active một lúc, các sensor khác ở trạng thái nghỉ Khi sensor đang active bị hết năng lượng thì lại lấy 1 sensor trong số các sensor xếp trồng và kích hoạt nó 37 5.2 Dùng GA để tìm cover tối ưu Các bước thực hiện Giả sử đã có cách chia tải cho các sensor cùng bao phủ 1 target, nhưng chưa có xếp chồng các sensor Ký hiệu : là số sensor xếp chồng lên nhau ở vị trí sensor i Tập N là tập gồm các B1 : Tính số KB của mỗi sensor phải gửi tới base sau 1 round B2 : Lấy một vị trí sensor i bất kì , đặt ni = 1 B3 : Tính thời gian tồn tại của vị trí sensor i, tìm được B4 : Với mỗi một vị trí sensor j trong mạng, tìm sao cho tj = ti B5: Tính S = sum(n1, n2, n3..) 38 5.2 Dùng GA để tìm cover tối ưu Các bước thực hiện B6 : Từ số tổng số sensor (N) đề bài cho trước tìm giá trị hi với công thức như sau = * N / S TH1 : | - | > 0.01 : Đặt = Th2 : | - | <= 0.01 : Làm lại từ bước 3 B7 : N = { , , ,. } , với mỗi giá trị , tính giá trị của int( ) và cho vào mảng T. Sắp xếp mảng T từ bé đến lớn, sắp xếp mảng N theo mảng T B8: Ta cần tính tổng phần sau dấu phẩy của mỗi phần tử trong tập N thu được giá trị x 39 5.2 Dùng GA để tìm cover tối ưu  Các bước thực hiện B9 : Thời gian tồn tại của mạng = T[x], F1 = T[x] B10 : Tính giá trị F2 như sau: Ban đầu F2 = 0 Với mỗi i trong N[:x] :  F2 += ceil(i) – i; Tính F1 và F2 để làm hàm đánh giá cho thuật toán GA để chia tải cho các sensor 40 5.2 Dùng GA tìm cover tối ưu   Thuật toán di truyền tìm cover tối ưu  Mục đích : Tìm ra Cover tối ưu để tối đa thời gian sông của mạng Population : Các cover tìm được từ Pha 1 Output : 1 Cover tối ưu 41 5.2 Dùng GA tìm cover tối ưu Thuật toán di truyền tìm cover tối ưu Biểu diễn Chromosome : Mỗi chromosome (tương ứng 1 Cover) biểu diễn dưới dạng mảng các VTS tối thiểu để bao phủ mạng Vd : C = {(72,13), (1,0,20) , (68,5),)} => Cover ứng với chromosome C 42 5.2 Dùng GA tìm cover tối ưu Thuật toán di truyền tìm cover tối ưu Hàm đánh giá (maximum): Để đánh giá 1 chromose ta làm như sau: Bước 1 : Tạo ra 200 cách cân bằng tải ứng với chromose đó Bước 2 : Với mỗi cách cân bằng tải trong 200 cách trên:  - Thực hiện thuật toán xếp chồng sensor để tính thời gian sống tương ứng - Lưu lại thời gian sống lớn nhất Bước 3 :  Hàm đánh giá có giá trị là thời gian sống lớn nhất 43 5.2 Dùng GA tìm cover tối ưu Thuật toán di truyền tìm cover tối ưu Cross over: Với cặp 2 chromosome : C1 và C2 Sinh ra 2 chromosome : C3 và C4 Các bước : B1 : C3 = C1, C4 = C2 B2 : Tìm chọn ngẫu nhiên 1 VTS có trong C1 mà không có trong C2 để thêm vào C4 B3 : Chọn ngẫu nhiên 1 VTS có trong C2 mà không có trong C1 để thêm vào C3 B4 : Trả về C3 và C4   44 Nội Dung 1. Tổng quan về mạng cảm biến không dây 1.1 Giới thiệu về mạng cảm biến 1.2 Ứng dụng mạng cảm biến 2. Giới thiệu bài toán 3. Các nghiên cứu liên quan 4. Mô hình bài toán 5 . Giải thuật đề xuất 5.1 Bài toán bao phủ mạng 5.2 Dùng GA để tạo cover tối ưu 5.3 Dùng GA để cân bằng tải  6. Thực nghiệm 7. Kết luận 45 5.2 Dùng GA để cân bằng tải  Thuật toán di truyền cân bằng tải   Mục đích : Sau khi tìm được cover tối ưu, cần phải tìm cách cân bằng tải cho cover đó để tối đa thời gian tồn tại mạng  Đầu vào : 1 cover  Đầu ra : Cách cân bằng tải tối ưu cho cover đó 46 5.2 Dùng GA để cân bằng tải  Thuật toán di truyền cân bằng tải   Biểu diễn Chromosome : Mỗi Chromosome tương ứng với 1 cách cân bằng tải  Biểu diễn chromosome dưới dạng 1 mảng các VTSS  VTSS: Là mảng băm chứa số bit thông tin phải truyền ứng với mỗi 1 target nằm trong 1 VTS  Vd : ((1: 200, 2 : 400 ) , (1 : 200 , 3 : 400, 5 : 400).) Có nghĩa là VTS1 phải truyền 200 bit thông tin về target 1 và 400 bit thông tin về target 2 47 5.2 Dùng GA để cân bằng tải  Thuật toán di truyền cân bằng tải   Hàm đánh giá:      Sử dụng Multiobjective GA, có 2 hàm đánh giá: Hàm F1 ( maximum) : Với F1 là thời gian tồn tại của mạng  Hàm F2 ( minimum) : Với F2 là độ dư thừa sensor - 2 Hàm này được tính bằng cách chạy thuật toán xếp chồng 48 Nội Dung 1. Tổng quan về mạng cảm biến không dây 1.1 Giới thiệu về mạng cảm biến 1.2 Ứng dụng mạng cảm biến 2. Giới thiệu bài toán 3. Các nghiên cứu liên quan 4. Mô hình bài toán 5. Giải thuật đề xuất 6. Thực nghiệm 6.1 Môi trường thực nghiệm 6.2 Dữ liệu thực nghiệm 6.3 Kết quả thực nghiệm 7. Kết luận 49 6.1 Môi trường thực nghiệm Môi Trường Thực nghiệm Dell Vostro 3590 CPU Intel Core i7-10510U 1.80 GHz Ram 8GB DDR4 2666 MHz Ổ cứng SSD 256 GB NVMe PCIe Màn hình 15.6“ Full HD (1920 x 1080) VGA Card rời, AMD Radeon 610R5, 2 GB 50 6.2 Dữ liệu thực nghiệm Dữ liệu thực nghiệm STT Name Num. Targets N Num. Sensor m R 1 S1-200 100 650 40 2 S1-250 150 650 40 3 S2-300 200 650 40 4 S2-350 250 650 40 5 S2-400 300 650 40 51 6.3 Kết quả thực nghiệm Các kịch bản thực nghiệm Thay đổi số lượng target Thay đổi bán kính kết nối R Thay đổi số lượng sensor 52 6.3.1 Thay đổi số lượng target Bộ dữ liệu STT Name Num. Targets N Num. Sensor m R 1 S1-200 100 650 40 2 S1-250 150 650 40 3 S2-300 200 650 40 4 S2-350 250 650 40 5 S2-400 300 650 40 53 6.3.1 Thay đổi số lượng target Kết quả STT Name Num. Targets N Num. Sensor m R Time 1 S1-200 100 650 40 2755970 2 S1-250 150 650 40 828880 3 S2-300 200 650 40 395846 4 S2-350 250 650 40 328747 5 S2-400 300 650 40 178712 54 6.3.1 Thay đổi số lượng target Number of target Time ( *10^4) 55 6.3.2 Thay đổi số lượng Sensor Bộ dữ liệu STT Name Num. Targets N Num. Sensor m R 1 S1-200 200 400 40 2 S1-250 200 45 0 40 3 S2-300 200 50 0 40 4 S2-350 2 00 55 0 40 5 S2-400 200 60 0 40 56 6.3.2 Thay đổi số lượng Sensor Kết quả STT Name Num. Targets N Num. Sensor m R Time 1 S1-200 200 400 40 178939 2 S2- 25 0 200 450 40 234589 3 S2-3 0 0 200 550 40 298753 4 S2- 35 0 200 600 40 355669 5 S2-4 0 0 200 650 40 395846 57 6.3.2 Thay đổi số lượng Sensor Time ( *10^4) Number of sensor 58 6.3.3 Thay đổi bán kính R Bộ dữ liệu STT Name Num. Targets N Num. Sensor m R 1 S1-200 200 650 40 2 S1-250 200 650 50 3 S2-300 200 650 60 4 S2-350 200 650 70 5 S2-400 200 650 80 6 S2-450 200 650 90 59 6.3.3 Thay đổi bán kính R Bộ dữ liệu STT Name Num. Targets N Num. Sensor m R Time 1 S1-200 200 650 40 395846 2 S1-250 200 650 50 413575 3 S2-300 200 650 60 439873 4 S2-350 200 650 70 446784 5 S2-400 200 650 80 456766 6 S2-450 200 650 90 461023 60 6.3.3 Thay đổi bán kính R Time ( *10^4) Bán kinh R 61 Nội Dung 1. Tổng quan về mạng cảm biến không dây 1.1 Giới thiệu về mạng cảm biến 1.2 Ứng dụng mạng cảm biến 2. Giới thiệu bài toán 3. Các nghiên cứu liên quan 4. Mô hình bài toán 5. Giải thuật đề xuất 6. Thực nghiệm 7. Kết luận 62 7. 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 tham lam và GA. 63 THANK YOU !