Tóm tắt Luận án Tiến sĩ Khoa học máy tính: Tối ưu chiến lược sạc cho các cảm biến để kéo dài thời gian sống của mạng WRSNs

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

Thêm vào BST

Báo xấu

4
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích nghiên cứu của tóm tắt luận án "Tối ưu chiến lược sạc cho các cảm biến để kéo dài thời gian sống của mạng WRSNs" là nghiên cứu về vấn đề tối đa thời gian sống của mạng theo cách tiếp cận tối ưu chiến lược sạc trong mạng cảm biến sạc không dây cho hai mô hình sạc phổ biến: mô hình sạc từng cảm biến và mô hình sạc nhiều cảm biến đồng thời; nghiên cứu lớp các thuật toán gần đúng như các thuật toán heuristic và các thuật toán meta-heuristic để giải quyết bài toán nghiên cứu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án Tiến sĩ Khoa học máy tính: Tối ưu chiến lược sạc cho các cảm biến để kéo dài thời gian sống của mạng WRSNs

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC BÁCH KHOA HÀ NỘI Trần Thị Hương TỐI ƯU CHIẾN LƯỢC SẠC CHO CÁC CẢM BIẾN ĐỂ KÉO DÀI THỜI GIAN SỐNG CỦA MẠNG WRSNs Ngành : Khoa học máy tính Mã số : 9480101 TÓM TẮT LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH Hà Nội - 2024
Công trình được hoàn thành tại: Đại học Bách khoa Hà Nội Người hướng dẫn khoa học: 1. PGS.TS Huỳnh Thị Thanh Bình 2. PGS.TS Lê Trọng Vĩnh Phản biện 1: Phản biện 2: Phản biện 3: Luận án được bảo vệ trước Hội đồng đánh giá luận án tiến sĩ cấp Đại học Bách khoa Hà Nội họp tại Đại học Bách khoa Hà Nội Vào hồi . . . . . . .. giờ, ngày . . . .. tháng . . . .. năm . . . . . . . . . Có thể tìm hiểu luận án tại thư viện: 1. Thư viện Tạ Quang Bửu - Đại học Bách khoa Hà Nội 2. Thư viện Quốc gia Việt Nam
DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA LUẬN ÁN 1. Tran Thi Huong, Phi Le Nguyen, Huynh Thi Thanh Binh, Kien Nguyen, Ngo Minh Hai, Le Trong Vinh (2020). “Genetic algorithm-based periodic charging scheme for energy depletion avoidance in WRSNs.” In 2020 IEEE Wireless Communications and Networking Conference (WCNC), pages 1-6. 2. Tran Thi Huong, Huynh Thi Thanh Binh, Phi Le Nguyen, Doan Cao Thanh Long, Vuong Dinh An, Le Trong Vinh (2020). “Optimizing Charging Locations and Charging Time for Energy Depletion Avoidance in Wireless Rechargeable Sensor Networks.” IEEE Congress on Evolutionary Computation (CEC) pages 1-8. 3. Tran Thi Huong, Le Van Cuong, Nguyen Bao Ngoc, Ngo Minh Hai, Huynh Thi Thanh Binh. “Effective partial charging scheme for minimizing the energy depletion and charging cost in wireless rechargeable sensor networks.” 2021 Congress on Evolutionary Computa- tion (CEC), IEEE, Poland, 2021, pages 1-8. 4. Le Van Cuong, Tran Thi Huong, Huynh Thi Thanh Binh. “A multi-task approach for maximum survival ratio problem in large-scale wireless rechargeable sensor networks.” 2021 Congress on Evolutionary Computation (CEC), IEEE, Poland, 2021, pages 1-8. 5. Nguyen Duc Anh, Tran Thi Huong, Nguyen Thanh Tung, Huynh Thi Thanh Binh, Frederica Free Nelson, Le Trong Vinh (2022). “Bi-level optimization for charging path and charging time in wireless rechargeable sensor networks.” Proceedings Volume 12113, Artificial Intelligence and Machine Learning for Multi-Domain Operations Applications IV. 6. Tran Thi Huong, Le Van Cuong, Ngo Minh Hai, Nguyen Phi Le, Le Trong Vinh, Huynh Thi Thanh Binh (2022). “A bi-level optimized charging algorithm for energy depletion avoidance in wireless rechargeable sensor networks.” Applied Intelligence, pages 1-23. 7. Nguyen Thanh Long, Tran Thi Huong, Nguyen Ngoc Bao, Huynh Thi Thanh Binh, Phi Le Nguyen, Kien Nguyen (2023) “Q-learning-based distributed multi-charging algorithm for large-scale WRSNs.” Nonlinear Theory and Its Applications, IEICE 14.1, pages 18-34 8. Vuong Dinh An, Tran Thi Huong, Hoang Nguyen Quang Pham, Quang Minh Bui, Trang Phuong Ngo, and Binh Thanh Thi Huynh (2024), “An adaptive charging scheme for large-scale wireless rechargeable sensor networks inspired by deep Q-network.” Neural Computing and Applications, pages 1-16 (ISI, Q1, IF=6.0).
GIỚI THIỆU Ngày nay, con người chứng kiến sự bùng nổ mạnh mẽ của mạng Internet, các mạng kết nối vạn vật (Internet of Things - IoTs) cùng sự tiến bộ trong công nghệ vi xử lý giúp quá trình thu thập, xử lý dữ liệu trở nên thông minh hơn. Đặc biệt, Mạng cảm biến không dây (Wireless Sensor Network - WSNs) được xem là kiến trúc cốt lõi trong phát triển hệ thống IoTs nhờ một loạt các ứng dụng từ dân sự tới quân sự [1, 2, 3]. Mạng WSN là mạng kết nối các nút cảm biến (sensor nodes) nhờ các liên kết không dây. Các cảm biến được triển khai trong một khu vực mục tiêu để thực hiện các nhiệm vụ cảm nhận và thu thập dữ liệu từ môi trường vật lý xung quanh rồi truyền về tới trạm cơ sở (Base Station - BS ). Người dùng cuối (users) có thể thông qua mạng Internet để đưa ra các bước xử lý, phân tích tiếp theo. Một trong những thách thức lớn nhất của mạng WSN là các cảm biến có năng lượng hữu hạn do sử dụng pin là nguồn cung cấp năng lượng chính [4, 5]. Khi pin của cảm biến cạn kiệt thì cảm biến sẽ mất chức năng hoạt động và trở thành nút mạng chết. Vì vậy, năng lượng của cảm biến có vai trò quyết định tới thời gian sống của mạng. Từ đó, kéo thời gian sống của mạng là nhiệm vụ quan trọng khi triển khai mạng WSN vào các ứng dụng thực tế. Các giải pháp truyền thống chủ yếu tập trung vào việc tối thiểu năng lượng tiêu thụ của cảm biến như tối ưu vị trí đặt cảm biến [6, 7], lập lịch bật/tắt thời gian hoạt động của cảm biến [8], sử dụng các nút chuyển tiếp dữ liệu [9], thu thập dữ liệu di động [4, 10]. Tuy nhiên, theo thời gian, năng lượng của các cảm biến vẫn dần cạn kiệt và trở thành nút mạng chết. Gần đây, một thế hệ mạng cảm biến mới ra đời được gọi là Mạng cảm biến có khả năng sạc không dây (Wireless Rechargeable Sensor Network - WRSNs), hoặc gọi tắt là mạng cảm biến sạc không dây [11] cho phép truyền năng lượng không dây tới các nút cảm biến. Mạng WRSNs sử dụng thêm một hoặc một số thiết bị sạc di động (Mobile Chargers - MCs), trong đó MC có thể là rô-bốt di động hoặc xe tự vận hành được trang bị bộ sạc không dây để cung cấp năng lượng cho mạng. Các cảm biến trong mạng WRSNs cũng được trang bị thêm một bộ phận nhận năng lượng không dây. Các MC có nhiệm vụ di chuyển xung quanh mạng để sạc lại năng lượng cho các cảm biến [12, 13] theo một trong hai mô hình sạc - mô hình sạc từng cảm biến và mô hình sạc nhiều cảm biến đồng thời. Trong mô hình sạc thứ nhất, MC sẽ dừng tại vị trí của từng cảm biến để sạc. Ngược lại, trong mô hình sạc thứ hai, MC sẽ di chuyển tới một số vị trí sạc nhất định để truyền năng cho nhiều cảm biến cùng lúc. Trong mạng WRSNs, chiến lược sạc của MC đóng vai trò quyết định tới thời gian sống của cảm biến do MC cần phải nạp 1
lại năng lượng cho các cảm biến trước khi chúng cạn kiệt năng lượng. Vì vậy, luận án này sẽ tập trung vào vấn đề kéo dài thời gian sống của mạng WRSNs theo cách tiếp cận tối ưu chiến lược sạc của MC. Một chiến lược sạc hiệu quả cần xem xét tối ưu hai thành phần: hành trình sạc và thời gian sạc. Trong đó, hành trình sạc là một chuỗi vị trí các điểm sạc được sắp xếp theo thứ tự dừng sạc của MC, thời gian sạc là khoảng thời gian mà MC sẽ sạc tại mỗi điểm sạc. Điểm sạc có thể là vị trí của cảm biến hoặc một vị trí xác định trong mạng [14, 15]. Tối ưu chiến lược sạc được chứng minh là bài toán NP-khó, liên quan với cả yếu tố về không gian (hành trình sạc) và thời gian (thời gian sạc) [16, 17, 18]. Tuy nhiên, để giảm bớt độ phức tạp của bài toán, các nghiên cứu trước đây chủ yếu tập trung vào tối ưu hành trình sạc với các giả thiết về năng lượng của MC là vô hạn hoặc cực lớn [17, 19, 20, 21]. Họ thường sử dụng phương pháp sạc đầy, trong đó mỗi cảm biến luôn được sạc tới tối đa dung lượng pin [17, 19, 20, 21, 22, 23] hoặc một mức năng lượng cố định [24]. Nhận thấy, thời gian sạc cũng là yếu tố quan trọng quyết định tới thời gian sống của cảm biến. Vì vậy, luận án này tập trung nghiên cứu tối ưu chiến lược sạc của MC cho hai mô hình sạc mà xem xét tối ưu cả hành trình sạc và thời gian sạc dưới ràng buộc năng lượng hữu hạn của MC để tối đa thời gian sống của mạng WRSNs. Do các bài toán nghiên cứu cuả luận án thuộc lớp NP-khó nên luận án sẽ đi theo hướng tiếp cận giải gần đúng. Các thuật toán tối ưu đề xuất sẽ được cài đặt, thực nghiệm trên đa dạng các kịch bản mạng mô phỏng, từ đó đưa ra những phân tích và đánh giá so sánh với các nghiên cứu liên quan. Mục tiêu của luận án Luận án tập trung giải quyết vấn đề kéo dài thời gian sống của mạng WRSNs theo cách tiếp cận tối ưu chiến lược sạc cho các cảm biến. Trong đó, luận án sẽ quan tâm tới vấn đề tối ưu chiến lược sạc cho hai loại mô hình sạc: mô hình sạc từng cảm biến và mô hình sạc nhiều cảm biến đồng thời. Hai mô hình sạc này tương ứng với hai công nghệ truyền năng lượng không dây ở khoảng cách gần và khoảng cách xa phụ thuộc vào đặc điểm kiến trúc mạng, quy mô triển khai cũng như số lượng cảm biến trong mạng WRSNs. Mục tiêu của luận án bao gồm: • Nghiên cứu về vấn đề tối đa thời gian sống của mạng theo cách tiếp cận tối ưu chiến lược sạc trong mạng cảm biến sạc không dây cho hai mô hình sạc phổ biến: mô hình sạc từng cảm biến và mô hình sạc nhiều cảm biến đồng thời. • Nghiên cứu lớp các thuật toán gần đúng như các thuật toán heuristic và các thuật toán meta-heuristic để giải quyết bài toán nghiên cứu. 2
• Nghiên cứu và ứng dụng các thuật toán học tăng cường để giải quyết bài toán nghiên cứu. Phạm vi nghiên cứu Theo [14, 25, 26], có nhiều định nghĩa khác nhau để tính thời gian sống của mạng, trong đó có hai định nghĩa được sử dụng phổ biến nhất là định nghĩa thời gian sống của mạng dựa vào số lượng cảm biến chết (hoặc số lượng cảm biến còn sống) và thời gian sống được tính dựa vào vai trò của cảm biến trong nhiệm vụ giám sát, kết nối mạng. • Thời gian sống của mạng được tính dựa vào số lượng nút cảm biến chết trong mạng: xét một mạng bao gồm n nút cảm biến được triển khai trong một khu vực mục tiêu. Thời gian sống của mạng được tính từ thời điểm mạng triển khai cho tới khi có k nút trong mạng hết năng lượng (nút chết). • Thời gian sống của mạng được tính dựa vào vai trò của cảm biến trong nhiệm vụ giám sát, kết nối mạng: thời gian sống của mạng là khoảng thời gian từ khi mạng triển khai cho tới khi có ít nhất một mục tiêu không được giám sát (bao phủ) bởi bất kỳ một cảm biến nào hoặc không tồn tại đường truyền dữ liệu nào từ ít nhất một mục tiêu tới BS. Cách định nghĩa này được áp dụng cho các mạng cảm biến có nhiệm vụ giám sát các điểm mục tiêu và đảm bảo đường truyền dữ liệu từ các điểm mục tiêu tới BS (gọi là kết nối). Với định nghĩa thứ nhất, để kéo dài thời gian sống của mạng, các nghiên cứu thường tập trung vào việc tối thiểu số lượng nút cảm biến chết. Trong khi đó, với định nghĩa thứ thứ hai, các nghiên cứu sẽ tập trung vào việc tối đa thời gian sống của cảm biển đầu tiên chết nhằm kéo dài thời gian sống của toàn mạng. Luận án này sẽ tập trung tối ưu chiến lược sạc để kéo dài thời gian sống của mạng WRSNs theo các định nghĩa trên cho hai mô hình sạc: mô hình sạc từng cảm biến và mô hình sạc nhiều cảm biến đồng thời. Cụ thể phạm vi nghiên cứu của luận án như sau: Trong mô hình sạc từng cảm biến, luận án giải quyết vấn đề tối đa thời gian sống của mạng bằng cách giải quyết bài toán tối ưu chiến lược sạc của MC nhằm tối thiểu sự cạn kiệt năng lượng của cảm biến. Các nghiên cứu trước đây chưa trực tiếp quan tâm tối ưu mục tiêu này, thay vì đó họ thường xem xét tới các mục tiêu gián tiếp như tối thiểu chi phí di chuyển, chi phí sạc, độ trễ sạc, cực đại thời gian nghỉ ở trạm sạc [17, 20, 27, 28, 29, 30, 31]. Hơn nữa, họ thường chỉ tập trung vào tối ưu hành trình sạc của MC bằng cách xác định thứ tự sạc các nút cảm biến trong mạng. Yếu tố thời gian sạc thường được xem là không ảnh hưởng hoặc có thể xác định khi áp dụng phương pháp sạc đầy, trong đó cảm biến luôn luôn được sạc tối đa mức năng lượng của pin khi thiết bị sạc dừng tại nút mạng. 3
Trong mô hình sạc nhiều cảm biến đồng thời, luận án kéo dài thời gian sống của mạng theo định nghĩa thứ hai bằng cách xem xét bài toán tối đa thời gian giám sát các điểm mục tiêu trong mạng WRSNs, đảm bảo đường kết nối dữ liệu từ các mục tiêu tới BS. Có thể thấy, những cảm biến chịu trách nhiệm giám sát các mục tiêu và tham gia vào các đường truyền dữ liệu tới BS đóng vai trò đặc biệt quan trọng tới hoạt động của toàn mạng. Việc dừng hoạt động của chỉ một cảm biến tham gia các nhiệm vụ trên có thể khiến cho toàn mạng bị mất chức năng giám sát và được coi là mạng chết. Tuy nhiên, các nghiên cứu trước đây đều không xem xét tới vai trò của các cảm biến trong các nhiệm vụ trên [32, 33, 34, 35, 36, 37]. Hơn nữa, trong mô hình sạc nhiều cảm biến đồng thời, vị trí và số lượng điểm dừng sạc của MC quyết định tới năng lượng nhận sạc của cảm biến và hiệu suất sạc của toàn mạng. Có thể thấy, một vị trí sạc càng xa cảm biến thì năng lượng nhận sạc của cảm biến càng nhỏ và ngược lại. Bên cạnh đó, nếu có quá nhiều điểm dừng sạc thì MC sẽ tiêu hao một lượng lớn năng lượng cho quá trình di chuyển giữa các điểm sạc. Để giải quyết các vấn đề trên, luận án sẽ nghiên cứu và xây dựng chiến lược sạc dựa vào yêu cầu sạc của cảm biến theo thời gian thực cho nhiều MC, trong đó xem xét các vấn đề tối ưu cả vị trí sạc, thời gian sạc và hành trình di chuyển của các MC. Các đóng góp của luận án Đóng góp chính của luận án là giải quyết hai bài toán tương ứng với hai chương chính như sau: Bài toán 1: tối ưu chiến lược sạc cho mô hình sạc từng cảm biến nhằm tối thiểu số lượng cảm biến bị cạn kiệt năng lượng. Khác với các cách tiếp cận trước đây, luận án sẽ tối ưu cả hai yếu tố hành trình sạc và thời gian sạc với ràng buộc về năng lượng của MC nhằm tối thiểu sự cạn kiệt năng lượng của cảm biến sau mỗi vòng sạc. Luận án đề xuất các thuật toán sạc theo cách tiếp cận giải gần đúng do bài toán nghiên cứu thuộc lớp bài toán NP-khó. Cụ thể: • Đề xuất cách tiếp cận tối ưu lần lượt hành trình sạc và thời gian sạc: chia bài toán ban đầu thành hai bài toán con dễ giải hơn và đề xuất một cách tiếp cận giải hai pha dựa vào giải thuật di truyền, được đặt tên là GACS. Trong đó, pha thứ nhất sẽ tìm ra hành trình sạc tốt nhất ưu tiên sạc trước cho các cảm biến có thời gian sống ngắn. Pha thứ hai của thuật toán sẽ tối ưu thời gian sạc theo hành trình đã được xác định ở pha thứ nhất. • Đề xuất cách tiếp cận tối ưu đồng thời hành trình sạc và thời gian sạc: theo cách tiếp cận đầu tiên, hành trình sạc tốt nhất ở pha một sẽ quyết định tới chất lượng 4
lời giải của cả bài toán. Nếu hành trình tìm được ở pha thứ nhất chưa tối ưu thì sẽ ảnh hưởng tới thời gian sạc ở pha thứ hai. Vì vậy, luận án đưa ra đề xuất thứ hai dựa vào một cách tiếp cận lồng nhau cho phép tối ưu đồng thời cả hành trình sạc và thời gian sạc. Luận án đề xuất thuật toán BOEDA dựa trên sự kết hợp giữa thuật toán di truyền, phương pháp tham lam và thuật toán tối ưu hóa bầy đàn (PSO). Bài toán 2: tối ưu chiến lược sạc cho mô hình sạc nhiều cảm biến đồng thời nhằm tối đa thời gian giám sát mục tiêu đảm bảo kết nối trong mạng WRSNs. Đóng góp của luận án là đề xuất chiến lược sạc theo yêu cầu dựa vào việc kết hợp các giải thuật heuristic và thuật toán học tăng cường dựa vào giá trị. cụ thể như sau: • Đề xuất thuật toán tham lam để xác định vị trí điểm dừng sạc tối ưu cho các MC. • Đề xuất thuật toán DTCM dựa vào sự kết hợp giữa thuật toán heuristic và thuật toán Q-learning để xác định ra vị trí sạc tiếp theo trong hành trình sạc của MC và thời gian sạc tại mỗi điểm dừng sạc. Cấu trúc của luận án Ngoài phần mở đầu và phần kết luận, nội dung của luận án được trình bày trong ba chương chính như sau: Chương 1: cơ sở lý thuyết. Chương này trình bày cơ sở lý thuyết của bài toán tối ưu, các thuật toán heuristic/meta-heuristic và học tăng cường, kiến thức về WSNs, WRSNs và vấn đề tối ưu chiến lược sạc. Chương 2: tối ưu chiến lược sạc cho mô hình sạc từng cảm biến. Trong chương này, luận án nghiên cứu bài toán tối ưu chiến lược sạc từng cảm biến nhằm tối thiểu số lượng cảm biến bị cạn kiệt năng lượng sau mỗi chu kỳ sạc. Luận án đề xuất các thuật toán tối ưu theo hướng tiếp cận heuristic/meta-heuristic để giải quyết bài toán. Chương 3: tối ưu chiến lược sạc cho mô hình sạc nhiều cảm biến. Trong chương này, luận án nghiên cứu bài toán tối ưu chiến lược sạc nhiều cảm biến đồng thời với nhiều thiết bị sạc nhằm tối đa thời gian giám sát các điểm mục tiêu và đảm bảo tính kết nối trong mạng WRSNs. 5
Chương 1 CƠ SỞ LÝ THUYẾT 1.1 Bài toán tối ưu Tối ưu hóa liên tục Nghiên cứu [38] đưa ra dạng tổng quan của một bài toán tối ưu hóa liên tục như sau: Maximize/Minimize :f (x) (1.1) Các ràng buộc :gi (x) ≤ 0 i = 1, ..., q (1.2) hj (x) = 0 j = 1, ..., p (1.3) Trong đó: • x = (x1 , x2 , ..., xn ) với xi là một biến nhận giá trị liên tục. • f (x) : R → R là hàm mục tiêu của bài toán. • gi (x) ≤ 0 thể hiện các ràng buộc bất đẳng thức. • hj (x) = 0 thể hiện các ràng buộc đẳng thức. Tối ưu hóa rời rạc Bài toán tối ưu rời rạc tổng quát có thể phát biểu như sau: Maximize/Minimize : f (x) với x ∈ D ⊂ Rn , (1.4) D là tập các vectơ x = (x1 , x2 , ..., xn ) mà một số (hoặc tất cả) các thành phần của x chỉ nhận các giá trị rời rạc. Tập D thường được xác định bởi một hệ thống các phương trình và bất phương trình với điều kiện bổ sung về tính nguyên của các biến số sau đây. gi (x) = 0, i = 1, 2, .., m1 , (1.5) gi (x) ≤ 0, i = m1 + 1, .., m, (1.6) xj − nguyên, j = 1, 2, .., n1 (1.7) Bài toán (1.4) - (1.7) được gọi là bài toán quy hoạch nguyên. Nếu n1 = n ta có bài toán quy hoạch nguyên hoàn toàn, nếu n1 < n ta có bài toán quy hoạch nguyên bộ phận. Có hai phương pháp giải các bài toán tối ưu là phương pháp giải chính xác và phương pháp giải gần đúng. Luận án tập trung vào các phương pháp gần đúng với hai cách tiếp cận là các phương pháp heuristic/meta-heuristic và học tăng cường. 6
1.2 Các thuật toán tiến hóa 1.2.1 Thuật toán di truyền Thuật toán di truyền được Holland đề xuất và được Michalevicz phát triển [39]. Thuật toán này thường được áp dụng để giải các bài toán tối ưu hóa. Thuật toán di truyền được xây dựng dựa trên quy luật tiến hóa sinh học hay phát triển tự nhiên của một quần thể sống. Các cá thể phải trải qua một quá trình phát triển và sinh sản để tạo ra những cá thể mới cho thế hệ tiếp theo. Trong quá trình tăng trưởng và phát triển những cá thể xấu (theo một tiêu chuẩn nào đó ví dụ như độ thích nghi với môi trường và mỗi cá thể sẽ có độ thích nghi với môi trường khác nhau) sẽ bị đào thải, đồng thời, những cá thể tốt sẽ được giữ lại (quá trình này gọi là quá trình chọn lọc) và được lai ghép (quá trình lai ghép) để tạo ra những cá thể mới cho thế hệ sau. Quá trình lai ghép được thực hiện ngẫu nhiên giữa các cá thể trong quần thể. Những cá thể mới được sinh ra mang những tính trạng của cá thể cha mẹ (di truyền). Các cá thể trong quá trình lai ghép có thể sẽ xảy ra hiện tượng đột biến và tạo ra các cá thể khác với cá thể cha mẹ. Các cá thể này có thể tốt hơn hoặc xấu hơn cá thể cha mẹ chúng. Tuy nhiên xác suất xảy ra hiện tượng đột biến là nhỏ hơn rất nhiều so với hiện tượng di truyền. Như vậy lai ghép và chọn lọc là hai quá trình cơ bản xuyên suốt quá trình tiến hóa tự nhiên. Vì vậy thuật toán di truyền là một trong những thuật toán tiến hóa, hình thành dựa trên quan niệm cho rằng, quá trình tiến hóa tự nhiên là quá trình hoàn hảo, hợp lý nhất, tự mang tính tối ưu. Điều này tuy chưa được chứng minh nhưng thuật toán phù hợp với thực tế khách quan. Tính tối ưu được thể hiện ở chỗ, thế hệ sau bao giờ cũng tốt hơn, hoàn thiện hơn thế hệ trước. Tuy nhiên, không phải tất cả các trường hợp đều như vậy, vẫn có một hoặc một số cá thể của thế hệ trước tốt hơn thế hệ sau vì vậy, trong khi sử dụng thuật toán di truyền, chúng ta phải lưu lại những cá thể tốt nhất ở mỗi thế hệ, trải qua số thế hệ nhất định (đây là tham số thiết kế) chúng ta đem so sánh những cá thể tốt nhất của thế hệ với nhau và chọn ra những cá thể tốt nhất giữa chúng. Đó có thể chính là lời giải tối ưu của bài toán hoặc hội tụ tới lời giải tối ưu của bài toán. Thuật toán di truyền sử dụng nhiều thuật ngữ của ngành sinh học như chọn lọc (selection), lai ghép (crossover ), đột biến (mutation), nhiễm sắc thể (chromosome). Thông thường một cá thể mang nhiều nhiễm sắc thể nhưng để đơn giản ta chỉ coi mỗi cá thể mang một nhiễm sắc thể và bộ mã gen của chúng mang đặc tính của cá thể, mỗi nhiễm sắc thể là một lời giải của bài toán [40][41]. 7
1.2.2 Thuật toán tối ưu bầy đàn Thuật toán tối ưu bầy đàn được giới thiệu đầu tiên vào năm 1995 bởi James Kennedy và C. Eberhart [42][43]. Thuật toán có nhiều ứng dụng quan trọng trong tất cả các lĩnh vực mà ở đó đòi hỏi giải quyết vấn đề tối ưu hóa. Thuật toán PSO được xây dựng dựa vào quá trình mô phỏng sinh học của đàn chim. Thuật toán PSO bao gồm ba bước chính được lặp đi lặp lại cho đến khi gặp điều kiện dừng [42]. 1. Bước 1: Đánh giá độ thích nghi của các cá thể, 2. Bước 2: Cập nhật các thể tốt nhất ở thời điểm hiện tại, và các cá thể tốt nhất qua các thế hệ, 3. Bước 3: Cập nhật vận tốc và vị trí của mỗi cá thể. 1.3 Các thuật toán học tăng cường 1.3.1 Thuật toán học tăng cường a) Học tăng cường Theo tác giả Sutton trong [44] định nghĩa học tăng cường là học những hành động mà tác nhân phải thực hiện để nhằm đạt được những mục tiêu cụ thể nào đó. Học ở đây cụ thể là học cách ánh xạ (mapping) giữa cái trạng thái của môi trường và hành động cần thực hiện. Câu hỏi quan trọng nhất trong học tăng cường là Làm thế nào để tác nhân đưa ra một hành động tốt? Ta sẽ dựa vào giá trị độ tốt đó để đưa ra quyết định. Như vậy, một thuật toán học tăng cường mà xác định hành động bằng cách căn cứ vào độ tốt của hành động thì được gọi là thuật toán học tăng cường dựa vào giá trị (Value-based Reinforcement Learning). b) Học tăng cường dựa vào giá trị Mục đích của học tăng cường là ra quyết định. Với mỗi đầu vào là một trạng thái của môi trường thì đầu ra là hành động tương ứng với trạng thái đó. Vậy làm thế nào để đưa ra được hành động? Hàm mục tiêu của thuật toán học tăng cường chính là cực đại tổng tích lũy dài hạn của phần thưởng và được biểu diễn như sau: ∞ n Gt = Rt+1 + γRt+1 + ... + γ Rn+1 = γ k Rk+1 (1.8) k=0 Công thức (1.8) cho thấy hàm giá trị mục tiêu ở thời điểm thứ t được tính bằng tổng giá trị lũy tích của phần thưởng nhận được sau khi thực hiện hành động ở thời điểm 8
thứ t và các thời điểm tiếp sau đó. Các thời điểm sau được nhân với một hệ số khấu hao γ (discount factor), trong đó 0 ≤ γ ≤ 1. Trong các thuật toán học tăng cường dựa vào giá trị, có hai hàm dùng để đánh giá độ tốt hành động hoặc trạng thái gọi là hàm giá trị hành động (action-value function) và hàm giá trị trạng thái (state-value function). c) Thuật toán Q-learning Thuật toán Q-learning được xây dựng từ một cách biến đổi khác của phương trình Bellman. Thuật toán Q-learning cập nhật giá trị Q(s, a) như sau: Q(s, a) ← (1 − α) × Q(s, a) + α(r + γmax Q(s′ , a′ ))) ′ (1.9) a 1.4 Mạng cảm biến không dây Mạng cảm biến không dây (Wireless Sensor Network - WSN) là mạng gồm một tập hợp các nút cảm biến (sensor nodes) có chức năng cảm nhận, thu thập dữ liệu từ môi trường xung quanh và định tuyến gửi tới trạm cơ sở (Base Station - BS). Các cảm biến được liên kết với nhau nhờ các liên kết không dây như sóng vô tuyến, sóng hồng ngoại hoặc quang học [45][46]. Các nút cảm biến sử dụng pin là nguồn cung cấp năng lượng chính, vì thế năng lượng của các cảm biến sẽ bị hạn chế và sau một thời gian sử dụng năng lượng sẽ bị cạn kiệt và trở thành các nút mạng chết. Việc thay thế pin cho các cảm biến cũng rất khó khăn, đặc biệt trong nhưng môi trường khắc nghiệt. Hơn nữa, năng lượng tiêu thụ của mỗi cảm biến cũng khác nhau. Những cảm biến gần trạm cơ sở sẽ chịu trách nhiệm chuyển tiếp dữ liệu nên sẽ tiêu thụ năng lượng nhiều hơn. Đây chính là thách thức chính trong quá trình triển khai và duy trì hoạt động của mạng cảm biến không dây trên các ứng dụng thực tế. Để giải quyết vấn đề năng lượng, các nghiên cứu chia thành hai hướng tiếp cận chính là tối thiểu năng lượng tiêu thụ của cảm biến và cung cấp năng lượng [17]. . 1.5 Mạng cảm biến sạc không dây mạng cảm biến có khả năng sạc không dây gọi tắt là mạng cảm biến sạc không dây bao gồm một tập các cảm biến có khả năng sạc lại và một hoặc một số các thiết bị sạc di động (Mobile Charger - MC) có thể truyền năng lượng không dây thông qua sóng điện từ. Các cảm biến trong mạng WRSNs có khả năng sạc lại nhờ được trang bị thêm một bộ phận nhận năng lượng không dây mà không cần bất kỳ một dây kết nối vật lý nào giữa bộ phát và bộ thu năng lượng. Nhiệm vụ của MC là di chuyển xung quanh 9
mạng và sạc lại năng lượng cho các cảm biến giúp duy trì trạng thái hoạt động của cảm biến từ đó kéo dài thời gian sống (thời gian hoạt động) của mạng [12, 13, 15]. 1.6 Một số mô hình sạc năng lượng không dây Mô hình sạc từng cảm biến cảm biến sử dụng công thức nhận năng lượng như sau: Prx = µ(d)Ptx (1.10) với µ(d) là hiệu suất truyền năng lượng theo khoảng cách d giữa M C và cảm biến. Giá trị µ(d) được tính theo công thức sau: µ(d) = −0.00958d2 − 0.0377d + 1 (1.11) Nếu MC dừng sạc tại vị trí của cảm biến thì d = 0, khi đó Prx = Ptx . Ptx còn được gọi là tốc độ sạc của MC và còn được ký hiệu là U [17, 19, 21]. Mô hình sạc không dây nhiều cảm biến đồng thời sử dụng công nghệ truyền năng lượng không dây dựa trên phát xạ điện từ cho phép truyền năng lượng ở một phạm vi nhất định. Mô hình sạc nhiều cảm biến đồng thời xây dựng theo phương trình không gian Friis [14, 15, 47, 48] như sau:  λ   , nếu d ≤ rcharge Prx = (d + β)2 (1.12)  0, nếu d > rcharge  2 G G η ζ với λ = tx rx Ptx , d là khoảng cách giữa cảm biến và MC, và rcharge là bán Lp 4π kính sạc tối đa của thiết bị sạc. 1.7 Tối ưu chiến lược sạc trong mạng WRSNs 1.7.1 Mô hình mạng Hệ thống mạng bao gồm bốn thành phần chính như sau: một tập n cảm biến có thể sạc lại không dây S = {s1 , s2 , ..., sn }, một tập m các thiết bị sạc di động M C = {M C1 , M C2 , ..., M Cm }, một trạm cơ sở BS (base station) s0 . Tất cả cảm biến được triển khai ngẫu nhiên trên một khu vực mục tiêu cần được giám sát. Các cảm biến luôn xác định được vị trí vật lý thông qua bộ định vị. Mỗi cảm biến tiêu thụ năng lượng cho nhiệm vụ thu thập dữ liệu, truyền và nhận dữ liệu. Luận án sử dụng mô hình tiêu thụ năng lượng trong [47] xác định mức năng lượng tiêu thụ khi cảm biến để nhận và truyền một bit dữ liệu. 10
Mỗi cảm biến đều có một bộ năng lượng (pin) với dung tích tối đa es (f ull) và phải i đảm bảo mức pin tối thiểu es (min) để thực hiện các chức năng hoạt động. Bộ truyền i năng lượng của MC có chức năng sạc lại cho các cảm biến thiếu hụt năng lượng bằng cách sử dụng cuộn lõi truyền điện [49] hoặc ăng-ten [50] để truyền năng lượng điện từ không dây. 1.7.2 Bài toán tối ưu chiến lược sạc Trong WRSNs, chiến lược sạc của MC đóng vai trò quyết định tới thời gian sống của cảm biến cũng như hiệu suất hoạt động của toàn mạng. Vì vậy, bài toán tối ưu chiến lược sạc cho MC có vai trò quan trọng nhằm tránh sự cạn kiệt năng lượng của cảm biến từ đó kéo dài thời gian sống của mạng. Theo [15], hiệu suất của một lược đồ sạc phụ thuộc vào hai yếu tố hành trình sạc và thời gian sạc. • Yếu tố thứ nhất là hành trình sạc - một chuỗi vị trí các điểm sạc được sắp xếp theo thứ tự dừng sạc của MC. Điểm sạc ở đây có thể là vị trí của cảm biến (đối với mô hình sạc từng cảm biến) hoặc là một vị trí xác định nào đó trong mạng (đối với mô hình sạc nhiều cảm biến đồng thời). • Yếu tố thứ hai là thời gian sạc là khoảng thời gian khi MC dừng lại và sạc tại mỗi điểm sạc. 1.8 Các nghiên cứu liên quan Dựa vào các đặc trưng của mạng WRSNs các chiến lược được phân loại theo thời gian phục vụ, phương pháp sạc hay diện tích triển khai. Theo thời gian phục vụ, MC có thể thực hiện nhiệm vụ sạc định kỳ (periodic charging) hoặc sạc dựa theo yêu cầu sạc từ các cảm biến. Đối với chiến lược sạc thứ nhất, MC sẽ định kỳ di chuyển xung quanh mạng và lần lượt sạc năng lượng cho các cảm biến theo một lộ trình được xác định trước tại BS [17, 19, 21, 51, 52, 53, 54, 55]. Từ lịch sử thông tin do cảm biến gửi (như năng lượng còn lại, thời điểm gửi gói tin), BS có thể ước lượng mức tiêu hao năng lượng trung bình, mức năng lượng còn lại của mỗi cảm biến để BS chủ động xây dựng lộ trình sạc cho MC. Ngược lại, đối với chiến lược theo yêu cầu, các cảm biến sẽ gửi yêu cầu sạc về BS khi năng lượng còn lại của chúng xuống dưới một ngưỡng năng lượng nhất định, khi đó BS sẽ lên kế hoạch sạc cho MC [16, 56, 57, 58, 59, 60, 61, 62]. Như vậy, lộ trình sạc của MC phụ thuộc vào yêu cầu sạc từ cảm biến. Đây là một yếu tố động, khó dự đoán và liên tục thay đổi theo thời gian. Theo phương pháp sạc, các nghiên cứu thường sử dụng phương pháp sạc đầy [10, 19, 20, 59, 60, 63, 64], hoặc sạc từng phần [48, 65]. Với phương pháp sạc đầy, mỗi lần sạc, MC luôn sạc tới tối đa dung lượng pin của cảm biến. Do truyền năng lượng không 11
dây nên có thể MC phải mất một thời gian dài đáng kể để sạc đầy pin cho một cảm biến. Trong khi đó, phương pháp sạc từng phần cho phép MC có thể sạc một mức năng lượng nhất định cho cảm biến giúp chúng duy trì hoạt động trong một khoảng thời gian trước khi được sạc lại trong lần sạc tiếp theo. Tùy theo diện tích và số lượng cảm biến trong mạng, một hoặc nhiều thiết bị sạc có thể được sử dụng nhằm đảm bảo cung cấp năng lượng hoạt động cho các cảm biến. Nhằm tiết kiệm chi phí, các mạng WRSNs có diện tích vừa/nhỏ hoặc số lượng cảm biến nhỏ thường chỉ cần sử dụng một MC, trong khi đó, các mạng diện tích rộng với hàng trăm nút mạng phải sử dụng nhiều MC để đáp ứng được các yêu cầu năng lượng. Thách thức lớn nhất trong việc tối ưu chiến lược sạc cho nhiều MC là sự phối hợp giữa các MC như thế nào để đạt được hiệu suất sạc lớn nhất. Các nghiên cứu trước đây về bài toán tối ưu chiến lược sạc trong mạng WRSNs thường xây dựng thuật toán sạc với giả thuyết xe sạc di động có năng lượng di chuyển hoặc năng lượng sạc là vô hạn. Bên cạnh đó, họ luôn áp dụng phương pháp sạc đầy cho các cảm biến trong một lần sạc vì vậy thời gian sạc của các cảm biến hằng số. Tuy nhiên, trên thực tế, do năng lượng xe sạc có hạn nên sẽ có rất nhiều nút cảm biến không nhận được mức năng lượng kịp thời, dẫn tới cạn kiệt năng lượng (chết) trước khi được sạc lại năng lượng. Hệ quả là toàn bộ khu vực mà cảm biến giám sát bị mất dữ liệu và ảnh hưởng tới hiệu suất của toàn bộ hệ thống. Từ những hạn chế trên, luận án sẽ đề xuất các chiến lược sạc hiệu quả hơn xem xét tối ưu đồng thời cả hành trình sạc và thời gian sạc của MC với ràng buộc về năng lượng hữu hạn của MC. Mục tiêu là kéo dài thời gian sống của mạng WRSNs. 1.9 Kết luận chương Chương này đã trình này một số cơ sở lý thuyết về bài toán tối ưu và một số hướng tiếp cận giải bài toán tối ưu bao gồm hướng tiếp cận heuritic/ meta-heuristic và hướng tiếp cận học tăng cường. Chương này cũng trình bày về các khái niệm cơ bản của mạng cảm biến không dây (WSN), mạng cảm biến sạc không dây (WRSNs), bài toán tối ưu chiến lược sạc cho mô hình sạc từng cảm biến và sạc nhiều cảm biến đồng thời, điểm qua các nghiên cứu nổi bật liên quan tới tối ưu chiến lược sạc trong WRSNs. 12
Chương 2 TỐI ƯU CHIẾN LƯỢC SẠC CHO MÔ HÌNH SẠC TỪNG CẢM BIẾN 2.1 Phát biểu bài toán Xét một mạng cảm biến có khả năng sạc không dây được triển khai trong một khu vực hai chiều có kích thước W ∗ H . Thiết bị sạc (MC) xuất phát tại trạm sạc (nằm tại BS), di chuyển xung quanh mạng và sạc cho các cảm biến sau đó MC quay trở về trạm cơ sở nạp lại năng lượng cho chu kỳ sạc tiếp theo. Giả sử MC đã hoàn thành chu kỳ sạc thứ k − 1 với k ≥ 1 và quay trở về trạm sạc (depot). Nhiệm vụ của bài toán là xác định lộ trình sạc ở chu kỳ sạc thứ k sao cho số lượng cảm biến bị cạn kiệt năng lượng (nút chết) là nhỏ nhất trong chu kỳ này. Cụ thể, lịch trình sạc bao gồm một hành trình sạc là thứ tự sạc của MC cho các cảm biến và thời gian sạc tại mỗi cảm biến tương ứng. Một cảm biến được định nghĩa là chết (ngừng hoạt động) nếu năng lượng hoạt động của chúng dưới mức năng lượng tối thiểu Emin . Để thuận tiện trong trình bày, luận án đặt tên cho bài toán quan tâm là EDAP (Energy Depletion Avoidance Problem). 2.2 Thuật toán đề xuất Bài toán tối ưu chiến lược sạc được chứng minh là một bài toán NP-khó [17, 19]. Để tìm được lời giải chính xác của bài toán, thuật toán chính xác phải xét tới tất cả hành trình sạc có thể là một tập tất cả các hoán vị của {s1 , ..., sn } và việc đòi hỏi chi phí tính toán rất lớn với các bộ dữ liệu kích thước lớn. Rõ ràng, theo hướng tiếp cận giải chính xác là không khả khi. Trong khi đó, các phương pháp gần đúng theo hướng heuristic và meta-heuristic được chứng minh là hiệu quả trong việc giải quyết các bài toán tối ưu với không gian tìm kiếm lớn và phức tạp. Các thuật toán heuristic/meta-heuristic có thể tìm lời giải đủ tốt trong thời gian chấp nhận được. Vì vậy luận án sẽ đề xuất hai thuật toán tối ưu theo heuristic và meta-heuristic, trong đó thuật toán thứ nhất được gọi là giải thuật di truyền hai pha (GACS - Genetic Algorithm Charging Scheme) và giải thuật tối ưu hai mức (BOEDA - Bilevel Optimization Energy Depletion Avoidance). Với mỗi đề xuất đều có những ưu điểm riêng trong cách tiếp cận. Tiếp theo, luận án sẽ trình bày chi tiết các đề xuất. 13
2.2.1 Thuật toán di truyền hai pha GACS a) Pha 1: Xác định hành trình sạc dựa vào kết giải thuật di truyền và giải thuật tham lam Về trực quan, ta nhận thấy để tránh cảm biến bị cạn kiệt năng lượng thì những cảm biến có thời gian sống ngắn sẽ được ưu tiên sạc trước. Nghĩa là những cảm biến nào có năng lượng còn lại nhỏ và tỷ lệ tiêu thụ năng lượng trung bình lớn sẽ cần được ưu tiên cung cấp năng lượng sớm hơn các cảm biến còn lại. Các toán tử di truyền Các toán tử di truyền trong thuật toán này được dựa trên [40] về bài toán người du lịch (Travelling Saleman Problem - TSP). Quần thể đầu tiên sẽ được sinh ngẫu nhiên gồm N cá thể, mỗi cá thể sẽ có 1 nhiễm sắc thể, với N là một tham số dương thay đổi được. Toán tử lai ghép Phép lai ghép PMX viết tắt của Paritally Mapped Crossover, hay phép lai ghép ánh xạ một phần [40]. Với lai ghép PMX, hai điểm cắt i và j sẽ được chọn ngẫu nhiên (với i, j ∈ [1, n]). Nhiễm sắc thể con O1 kế thừa toàn bộ đoạn gene πi , . . . , πj của nhiễm sắc thể I1 . Toán tử đột biến Thuật toán cũng sử dụng kết hợp hai phép đột biến là phép đột biến CIM và phép đột biến đổi chỗ [66] với tỷ lệ 6 : 4. Tỷ lệ xảy ra đột biến cũng tương đối nhỏ, chỉ khoảng từ 0% đến 20%. Chọn lọc Thuật toán di truyền sẽ dừng sau G thế hệ hoặc sau 200 thế hệ mà hàm thích nghi không thay đổi. b) Pha 2: Xác định thời gian sạc tối ưu ∗ ∗ Gọi Q = {π1 , . . . , πn } là hành trình sạc của MC được xác định trong pha 1 của thuật toán. Gọi {τπ1 , . . . , τπn } là chuỗi thời gian sạc tương ứng tại mỗi cảm biến trong Q. Nhiệm ∗ ∗ vụ tiếp theo là xác định chuỗi thời gian sạc trên để tối thiểu số lượng cảm biến cạn kiệt năng lượng sau một chu kỳ sạc. Biểu diễn cá thể và hàm thích nghi ∗ ∗ ∗ Hàm thích nghi đo chất lượng của mỗi cá thể {τπ1 , τπ2 . . . , τπn } là tổng số lượng nút ∗ ∗ chết mà xe đi theo hành trình {π1 , . . . , πn } Khởi tạo cá thể Khởi tạo một quần thể gồm Psize cá thể, với Psize > 0. Luận án đề xuất một phép lai ghép mới, được đặt tên là SPAH (Single-Point và AMXO Hybrid crossover), kết hợp ưu điểm của hai phép lai ghép Một điểm cắt và phương pháp Lai ghép Số học (AMXO) [67]. 14
2.2.2 Thuật toán sạc tối ưu hai mức BOEDA Có thể thấy, thuật toán GACS giải quyết bài toán ban đầu bằng cách chia nhỏ thành hai bài toán con và giải quyết theo hai pha, trong đó lời giải tốt nhất của pha đầu tiên sẽ là đầu vào của pha thứ hai. Tuy nhiên, do việc xem xét hai pha một cách riêng biệt, nên giải pháp tối ưu của pha trước có thể không được tối ưu hóa cho pha sau. Đề xuất thứ hai dưới đây xuất phát từ ý tưởng làm sao để tối ưu đồng thời cả hai pha trong đề xuất thứ nhất bằng cách tiếp cận lồng nhau với mã hóa lời giải hai thành phần. Đề xuất này lấy ý tưởng từ cách tiếp cận lồng nhau [68]. Thuật toán được đề xuất có hai đặc điểm mới chính so với tối ưu hóa hai mức truyền thống như sau: • Thứ nhất, thay vì tiêu thụ một lượng lớn tài nguyên tính toán để tối ưu hóa thời gian sạc cho tất cả các hành trình sạc được tạo ra (mỗi cá thể của quần thể cho tối ưu mức trên) như phương pháp lồng nhau truyền thống, ta chỉ thực hiện nhiệm vụ tối ưu hóa mức dưới (xác định thời gian sạc) cho hành trình tốt nhất trong quá trình tìm kiếm. • Thứ hai, tối ưu hóa mức dưới cần hội tụ ngay khi đảm bảo chất lượng giải pháp, từ đó giảm thiểu chi phí tính toán. Mã hóa lời giải Ta sẽ mã hóa lời giải bằng một ma trận 2 × n, trong đó hàng đầu tiên đại diện cho một hành trình sạc (một chuỗi các nút cảm biến được sắp xếp theo thứ tự sạc của MC) và hàng thứ hai cho thời gian sạc tại tất cả các cảm biến. Cụ thể, một giải pháp I được mã hóa như sau: π1 π2 . . . πn I= τ1 τ2 . . . τn trong đó {π1 , π2 , . . . , πn } là một hoán vị của tập chỉ số {1, 2, . . . , n} (tương đương với tập {s1 , s2 , . . . , sn }) và τ1 , τ2 , . . . , τn là thời gian sạc tại các cảm biến π1 , π2 , . . . , πn tương ứng. Áp dụng giải thuật di truyền cho nhiệm vụ tối ưu hóa mức trên Các toán tử di truyền Thuật toán sử dụng phép lai ghép OX (Ordered Crossover) [69] và phép lai ghép PMX (Partially Mapped Crossover) [70] với cùng một xác suất để tạo ra các cá thể con. Hai phép lai ghép này được áp dụng phổ biến đối với phương pháp biểu diễn hoán vị [71]. Đối với việc lựa chọn cha mẹ, nghiên cứu tham khảo phương pháp giải đấu nhị phân do tính hiệu quả và đơn giản [71]. Thuật toán sử dụng phép đột biến Chèn (Insertion) và đột biến Trao đổi (Swap) để tạo ra cá thể đột biến. 15
Áp dụng giải thuật tối ưu bầy đàn cho nhiệm vụ tối ưu hóa mức dưới Nhờ hiệu suất tính toán cao nên thuật toán PSO đã được áp dụng rộng rãi để giải quyết nhiều vấn đề tối ưu hóa thực tế [72, 73]. Ngoài ra, tốc độ hội tụ cao làm cho thuật toán PSO phù hợp hơn cho các bài toán tối ưu hai mức. Giả sử rằng ℘ = π0 → π1 → π2 → . . . → πn → π0 là hành trình sạc tốt nhất thu được sau một thế hệ của nhiệm vụ tối ưu hóa mức trên. Luận án sẽ sử dụng một phương pháp khởi tạo tham lam và điều chỉnh thuật toán PSO để tối ưu hóa thời gian sạc tại mỗi cảm biến trong khi giả định rằng MC đi theo hành trình sạc ℘. 2.2.3 Phân tích độ phức tạp của thuật toán BOEDA Đối với mỗi hành trình sạc, thuật toán tính toán năng lượng còn lại của mỗi cảm biến để xác định trạng thái hoạt động của cảm biến. Do đó, việc tính toán hàm mục tiêu yêu cầu O(n), trong đó n là số lượng cảm biến. Gọi Psize là số lượng cá thể trong quần thể và G là số thế hệ. Độ phức tạp của thuật toán BOEDA được tính như sau: • Một hành trình sạc được khởi tạo bằng phương pháp tham lam trong O(n log(n)), sau đó thực hiện với Psize lần. Do đó, tổng độ phức tạp là O(n log(n)Psize ). • Các toán tử lai ghép và đột biến của GA ở mức trên có độ phức tạp là O(nPsize ). • Đối với toán tử chọn lựa, thuật toán đánh giá chi phí của tất cả các cá thể con và sắp xếp tất cả các cá thể với độ phức tạp là O(Psize log(Psize )). • Nhiệm vụ tối ưu hóa ở mức dưới có độ phức tạp O(nPsize G), đó là độ phức tạp để tối ưu hóa thời gian sạc của hành trình sạc tốt nhất thu được ở mỗi thế hệ của nhiệm vụ tối ưu hóa mức trên. Do đó, tổng độ phức tạp của BOEDA là O(n log(n)Psize + Psize log(Psize )G + nPsize G). 2.3 Kết quả thực nghiệm 2.3.1 Kịch bản thực nghiệm - Triển khai cảm biến theo các ô lưới vuông [65]: chia diện tích mạng cảm biến có kích thước W × W thành 16 ô vuông. - Triển khai cảm biến theo phân phối chuẩn: Tọa độ (x, y) của mỗi cảm biến trong phương pháp này được thiết lập bằng một phân phối Gaussian. - Triển khai cảm biến theo phân phối đều: Tọa độ (x, y) của mỗi cảm biến được sinh ra theo phân phối đều. 2.3.2 Cài đặt thực nghiệm Các thực nghiệm được cài đặt bằng ngôn ngữ lập trình Java trên máy tính vi xử lý Intel® Core™ i5 3470, 8 GB RAM và hệ điều hành Windows 10 Pro 64-bit. Ngoài ra, 16
luận án sử dụng các thông số của mạng trong [17][74]. Thời gian mô phỏng của mạng là 72000 giây [59] với thời gian tối đa của một chu kỳ sạc không vượt quá 18000 giây. Sử dụng mô hình tiêu thụ năng lượng theo tài liệu [75]. 2.3.3 Kết quả thực nghiệm Trong phần này, nghiên cứu đánh giá hiệu suất của hai thuật toán đề xuất (GACS, BOEDA) với các thuật toán có liên quan nhất là thuật toán sạc định kỳ Hybrid Particle Swarm Optimization and Genetic Algorithm (HPSOGA) [17], và thuật toán sạc INMA [59]. a) Đánh giá phương pháp khởi tạo tham lam Trong phần này, nghiên cứu đánh giá hiệu suất của BOEDA dưới hai phương pháp khởi tạo: phương pháp tham lam được đề xuất và cơ chế ngẫu nhiên. Cụ thể, α nên dao động từ 0.4 đến 0.6. Dựa trên các phân tích trên, để đạt hiệu suất tốt nhất, nghiên cứu quyết định sử dụng phương pháp khởi tạo tham lam và giá trị của α = 0.5 cho thuật toán BOEDA trong tất cả các thí nghiệm tiếp theo. b) Đánh giá ảnh hưởng của các yếu tố trong mạng Đầu tiên, nghiên cứu đánh giá tác động của số lượng nút cảm biến và phương pháp triển khai cảm biến được sử dụng trong các mạng. Thực nghiệm này muốn đánh giá sự tác động của số lượng cảm biến tới hiệu suất của các thuật toán bằng cách tăng dần số lượng cảm biến lần lượt từ 25, 50, 75 lên 100 cảm biến. Nhận thấy xu hướng tỉ lệ nút chết tăng dần ở cả hai thuật toán khi số lượng cảm biến tăng từ 25 tới 100 khi dung lượng pin của MC là không đổi. Tỉ lệ cao nhất ghi nhận được là khoảng 40% kết quả của HPSOGA trong mạng phân phối đồng đều với 100 cảm biến. Tuy nhiên, tỉ lệ tăng khi số nút cảm biến tăng lên. Ví dụ, kết quả của INMA tăng từ 0% lên đến 26.3% khi số cảm biến tăng từ 25 lên 100. Sự tăng này là do khi số lượng cảm biến tăng, các kết nối giữa các cảm biến đã tăng đáng kể. Kết quả là tỉ lệ tiêu thụ năng lượng tại mỗi cảm biến tăng đáng kể. Hơn nữa, để tránh cạn kiệt năng lượng của các cảm biến với tỉ lệ tiêu thụ năng lượng lớn, MC cần sạc thêm thời gian. Tuy nhiên, chúng ta có thể nhận ra rằng BOEDA vượt trội hơn ba phương pháp khác trong tất cả các tình huống. Tiếp theo, tác giả nghiên cứu tác động của tỉ lệ tiêu thụ của các cảm biến đối với hiệu suất sạc. Tất cả các phương pháp đều cho thấy xu hướng tăng khi chúng ta tăng tỉ lệ tiêu thụ năng lượng trung bình của các cảm biến. Điều này là hợp lý vì một cảm biến có tỉ lệ tiêu thụ cao sẽ cạn kiệt năng lượng nhanh hơn. BOEDA giảm tỉ lệ nút chết đi 4.484%, 3.740%, 4.146% so với GACS, 8.940%, 11.303%, 11.390% so với INMA, và 26.440%, 29.388%, 28.619% so với HPSOGA trong các bộ g, n và u. 17