Đề tài Tối ưu sạc cho mạng không dây có thể sạc trong không gian

Tối ưu sạc cho mạng không dây có thể sạc trong không gian Nguyễn Đức Anh Nguyễn Thế Tùng Dương Chuaxin Zhao, Hengjing Zhang, Fulong Chen,∗ , Siguang Chen, Changzhi Wu, Taochun Wang, “Spatiotemporal charging scheduling in wireless rechargeable sensor networks” in Computer Communications , vol 152, pp. 155-170, 2020. 20172937 20173060 Nội dung Giới thiệu Nghiên cứu liên quan Mô hình hóa bài toán Giải pháp Kết quả Giới thiệu I. Giới thiệu Wireless Rechargeable Sensor Network (WRSN) Công nghệ mới Tận dụng việc cảm biến, truyền thông dữ liệu → nắm bắt được thông tin môi trường xung quanh Thành phần trong mạng: Các cảm biến Xe sạc Trạm cơ sở Dịch vụ định kỳ 2. Dịch vụ hỗn hợp I. Giới thiệu Ứng dụng: Giám sát vật thể, đối tượng trong vùng rộng Hỗ trợ trong nhiều mảng: nông nghiệp, xây dựng .. Vd: Smart city - kiểm soát cơ sở hạ tầng bằng cách thu thập dữ liệu → phòng tránh nguy cơ, dự đoán I. Giới thiệu Vấn đề Hệ thống: Luôn có nhu cầu sử dụng cảm biến Cảm biến: Khả năng làm việc → giới hạn bởi dung lượng pin Xe sạc: Khả năng sạc cho các cảm biến → giới hạn bởi dung lượng tối đa của xe Nhiều xe sạc → tốn kém ⇒ Cần phải có một lộ trình sạc hợp lý Thực tế, rất khó để thỏa mãn nhu cầu sạc khi có nhiều cảm biến gửi yêu cầu → Các cảm biến chết → thời gian sống của mạng Khó khăn I. Giới thiệu Làm thế nào để giảm số lượng cảm biến chết? Giảm tổng quãng đường Chọn vị trí xuất phát Lựa chọn vị trí dừng sạc Thời gian sạc cho mỗi cảm biến hiếm khi được đề cập (Charging time) Tối ưu thời gian di chuyển của xe sạc Không sạc đầy! Sạc đầy → Không tối ưu Mỗi cảm biến cần sạc bao nhiêu năng lượng → Thời gian sạc I. Giới thiệu Hướng 1: tối ưu đồng thời: Năng lượng di chuyển của xe Tổng công suất sạc cho các cảm biến Hướng 2: tối ưu đồng thời: Năng lượng di chuyển của xe Tổng số lượng cảm biến chết trong một chu kỳ II. Nghiên cứu liên quan II. Nghiên cứu liên quan Giải pháp tối ưu việc sạc và truyền thông dữ liệu đồng thời Tác giả [1] đã đề xuất việc thực thi đồng thời việc sạc và truyền thông dữ liệu nhằm tối ưu hiệu năng hệ thống Tác giả [2] đề xuất một khung công việc cho việc đi lại với chi phí di chuyển và ràng buộc dung tích Tiếp cận kế hoạch sạc làm việc với những đối tượng, mục tiêu khác Tác giả [3] đưa ra ý tưởng về việc sạc đồng thời nhiều cảm biến cùng lúc Tác giả [4] chọn việc thay đổi xe sạc thành máy bay không người lái để sạc, bỏ qua yếu tố địa hình [1] M. Zhao, J. Li, Y. Yang, A framework of joint mobile energy replenishment and data gathering in wireless rechargeable sensor networks (2014) [2] C. Wang, J. Li, F. Ye, et al., A mobile data gathering framework for wireless rechargeable sensor networks with vehicle movement costs and capacity constraints (2016) [3] Y. Ma, W. Liang, W. Xu, Charging utility maximization in wireless rechargeable sensor networks by charging multiple sensors simultaneously (2016) [4] T. Wu, P. Yang, H. Dai, P. Li, X. Rao, Near optimal bounded route association for drone-enabled rechargeable WSNs, Comput. Netw. 145 (2018) II. Nghiên cứu liên quan Một số vấn đề hạn chế Ưu tiên chọn hành trình sạc, sạc cho tất cả → hiệu suất sạc thấp Hiếm khi đề cập đến thời gian sạc Bỏ qua yếu tố dung lượng tối đa mỗi xe Khó thỏa mãn nhu cầu sạc tất cả các cảm biến ⇒ Nhắm vào việc phân bổ thời gian sạc và thiết lập lịch trình sạc để cải thiện chất lượng hoạt động của mạng lưới ở cả dịch vụ định kỳ và hỗn hợp Hướng tiếp cận thứ nhất Tối ưu năng lượng di chuyển xe sạc Tối ưu tổng công suất sạc III.1. Mô hình hóa bài toán III. Mô hình hóa bài toán Cơ chế hoạt động trong mạng lưới: Cảm biến: Tiêu thụ năng lượng → dựa trên năng suất tiêu thụ Gửi yêu cầu sạc khi năng lượng dưới ngưỡng Bmin Tiếp nhận năng lượng Xe sạc: Hoạt động mỗi chu kỳ T Mỗi chu kỳ T, đi sạc lần lượt kịp thời → Mô hình hóa hành vi trên III. Mô hình hóa bài toán Để mô phỏng, hệ thống được biểu diễn: T rên không gian 2D Các cảm biến, điểm xuất của xe sạc phát có tọa độ xác định → Tạo ra đồ thị G gồm các node đôi một liên kết với nhau và có khoảng cách xác định III. Mô hình hóa bài toán Cảm biến: Sở hữu năng lượng hiện có B Dung lượng pin tối đa: CV Quá trình tiếp nhận năng lượng: Tiêu thụ năng lượng: Năng lượng tiêu thụ “ec” khi gửi và nhận “ri” bit dữ liệu được tính bởi: [p]: Hằng thời gian [Di]: tập các node đích để gửi dữ liệu Năng lượng nhận về phụ thuộc vào thời gian sạc Xe sạc: Trong một chu kỳ T, năng lượng mà xe sạc cung cấp không vượt quá dung lượng tối đa của xe (C total ) III. Mô hình hóa bài toán Năng lượng di chuyển trong chu kỳ Thời gian di chuyển của xe trong chu kỳ Tổng năng lượng sạc cho N cảm biến (ti thời gian sạc cho cảm biến thứ i) III. Mô hình hóa bài toán Cảm biến: Cửa sổ thời gian [st,dt] của mỗi cảm biến st: thời điểm gửi yêu cầu dt: thời điểm chết Xe sạc: Từ thời điểm xe bắt đầu chạy Tstart, xe phải sạc kịp thời cho cảm biến thứ k Thời gian di chuyển và tổng thời gian sạc cho các cảm biến của xe không vượt quá chu kỳ T III. Mô hình hóa bài toán Để giảm số lượng cảm biến chết: Tối đa tổng năng lượng nhận về của các cảm biến → phân bổ thời gian sạc Cực tiểu chi phí đi lại của xe sạc khi sạc cho các cảm biến gửi yêu cầu → chọn ra thứ tự sạc Cặp biến (x,t): được thăm thứ i, với thời gian sạc ti Cột trên: thứ tự sạc, chỉ số của các cảm biến Cột dưới: thời gian sạc tương ứng III. Mô hình hóa bài toán Tìm ra cặp biến để tối ưu đồng thời tổng năng lượng nhận vào và chi phí đi lại IV.1. Giải pháp IV. Giải pháp Teaching and Learning Based Optimization (TLBO): Ý tưởng: Mô phỏng lại quá trình dạy và học trong lớp Giáo viên dạy học sinh Học sinh học hỏi lẫn nhau Điểm mạnh: Thuật toán đơn giản trong việc thực thi Chỉ yêu cầu 1 tham số Định nghĩa: Lớp học: quần thể Học sinh: cá thể Giáo viên: học sinh tốt nhất Giai đoạn Teaching Lai ghép học sinh với cô giáo → Giai đoạn Learning Lai ghép với học sinh tốt hơn với nhau → IV. Giải pháp IV. Giải pháp (Evolutional TLBO) Thuật toán TLBO cơ bản chỉ làm việc với số thực Trong khi biến trong bài toán cần giải là cả số nguyên và số thực: Thời gian sạc → các số thực Thứ tự sạc → các số nguyên ⇒ Cần phải điều chỉnh lại thuật toán TLBO để giải quyết bài toán đã đặt ra Các phép toán thay thế Biểu diễn Lai ghép Đột biến Thứ tự sạc (số nguyên) Chuỗi các thứ tự sạc - các hoán vị tráo đổi vùng cắt giữa 2 cá thể và thay thế những phần tử bị trùng Đổi vị trí 2 phần tử ngẫu nhiên trong cá thể Thời gian sạc (số thực) Chuỗi thời gian dừng sạc cho các thứ tự sạc ở trên 2 cá thể y,y’ được chọn để lại ghép: Chọn ngẫu nhiên 1 node Khởi tạo lại thời gian sạc Lai ghép 2 thứ tự sạc Partially mapped crossover Áp dụng TLBO đi kèm ràng buộc Các lời giải không phù hợp nếu có các ràng buộc ⇒ TLBO cho ra các lời giải không hợp lệ Hàm chỉnh sửa Đối với ràng buộc (7), (8) → Trực tiếp thay đổi thời gian sạc của một node ngẫu nhiên cho đến khi hợp lệ Hàm phạt Đối với ràng buộc (9) → Phức tạp vì đòi hỏi phải thỏa mãn tại mỗi cảm biến → Chấp nhận việc một số cảm biến sẽ chết ⇒ Sử dụng hàm phạt: [pc]: adjustable parameter [fc]: charging time of node i ⇒ Maximizing with Constraint (7) - (11) Lược đồ ETLBO IV. Giải pháp Sử dụng ETLBO cho các chế độ của hệ thống Hệ thống làm việc theo định kỳ (Offline): Dự đoán được thời điểm cảm biến chết Sử dụng trực tiếp ETLBO để đưa ra lịch trình sạc và thời gian sạc Hệ thống làm việc hỗn hợp: Việc chuyển dữ liệu khó đoán → khó dự đoán thời điểm cảm biến chết ⇒ Trong chu kỳ T, lúc xe hoạt động → tiếp tục có cảm biến gửi request New request!! IV. Giải pháp Thuật toán DIA (Dynamic Insertion Algorithm) Ý tưởng: Điều chỉnh lại lịch sạc khi có cảm biến yêu cầu Thêm cảm biến vào lịch sạc, tính lại hàm đánh giá → lựa chọn cảm biến có hàm đánh giá thấp nhất Sử dụng: Dùng ETLBO → lịch sạc lịch sạc → DIA → lịch sạc mới Triển khai - kết quả Tham số Kích cỡ quần thể: 200 Xác suất lai ghép: 0.3 Xác suất đột biến: 0.1 Tỉ lệ học sinh xuất sắc: 0.2 Dữ liệu: Tên dữ liệu: small-net Phân phối Grid Gồm các điểm tọa độ 2 chiều (các cảm biến) và vị trí xuất phát Kết quả so sánh ETLBO và ETLBO + DIA - số node chết trung bình Hướng tiếp cận thứ hai Tối ưu năng lượng di chuyển xe sạc Tối ưu tổng số lượng cảm biến chết trong một chu kỳ Hướng tiếp cận thứ 2 Giống: Sử dụng bộ chung một số thông số Năng lượng sạc Dung tích, tốc độ v.v Cùng một mục tiêu Khác: Cơ chế vận hành: Xe sẽ không đợi yêu cầu Xe chủ động sạc III.2. Mô hình hóa bài toán Mô hình hóa bài toán Tập hợp các node Base Station (Vị trí khởi đầu của thiết bị sạc) Năng lượng tối đa, tối thiểu để 1 node có thể hoạt động Công suất tiêu thụ của cảm biến Năng lượng ban đầu và khi kết thúc chu kì sạc của node Năng lượng của node trước khi thiết bị sạc đến Khoảng cách Euclidean giữa node i và node j Thời gian sạc tại node thứ i Trạng thái ( sống, chết) của node thứ i Độ giảm năng lượng của node thứ i khi bắt đầu và kết thúc 1 chu kì Năng lượng tối đa của thiết bị sạc Năng lượng mà thiết bị sạc dùng để di chuyển Tỷ lệ tiêu thụ năng lượng của xe khi di chuyển và khi sạc Vận tốc của xe Vecto Charging path Vecto charging time Mô hình hóa bài toán Giả sử đã hoàn thành chu trình sạc thứ k-1. Thiết bị sạc đang ở Base Station để nạp đầy năng lượng để chuẩn bị cho chu trình sạc thứ k Đầu vào: Tọa độ trạm cơ sở BS Tọa độ của n cảm biến Thông số của mỗi cảm biến bao gồm: Công suất tiêu thụ: Pi Năng lượng tối đa: Emax Năng lượng tối thiểu: Emin Năng lượng ban đầu: E Thông số của thiết bị sạc Năng lượng tối đa: Emc Công suất tiêu thụ khi di chuyển: Pm Công suất tiêu thụ khi sạc: U Vận tốc: V Đầu ra: Vector chu trình sạc Vector thời gian sạc Trạng thái 1 node Biến nhị phân z: z = 0: Node sống z = 1: Node chết Với: Hàm mục tiêu Năng lượng di chuyển Tổng số node chết Các ràng buộc Node j được sạc sau khi sạc node i else IV.1. Giải pháp IV. Giải pháp Bi-level Bi - level Giải quyết với 2 biến ở mức trên và dưới Mức trên: chuỗi hành trình sạc Mức dưới: thời gian sạc → Kết quả cho bài toán ở mức dưới phụ thuộc vào kết quả cho bài toán ở mức trên IV. Giải pháp Bi-level Ý tưởng: Mức trên: chuỗi hành trình sạc Mức dưới: thời gian dừng sạc tối ưu chuỗi hành trình sạc cho trước Áp dụng Bi-level: Sử dụng thuật toán tối ưu lồng nhau - Áp dụng GA ở cả 2 mức GA GA Thời gian sạc Chuỗi hành trình Các phép toán với cá thể cho trước Biểu diễn Lai ghép Đột biến Chuỗi hành trình sạc Hoán vị, random-key PMX Insert mutation Chuỗi thời gian sạc Chuỗi số thực Arithmetic-Crossover y1’ = y1.(1-r) + y2.r y2’ = y1.(1-r) + y2.r Swap mutation Hướng giải quyết 2 pha: Hành trình sạc: Xác định bởi 2 chiến lược khởi tạo Bi-level: với các node cần sạc Chọn các node để sạc Giải bài toán tối ưu áp dụng Bi-level Random key Sinh hoán vị ngẫu nhiên Mã hóa Random key Với mỗi node: Xác định trọng số ưu tiên của node: w = p/E Khởi tạo 1 số thực x bất kì trong (minw, maxw) Với minw = min(w1, w2, , wn) maxw = max(w1, w2,..., wn) Nếu x<=w thì node đó được sạc Khởi tạo chu trình sạc theo độ lớn của x Mã hóa hoán vị Cá thể được sinh ra: Chọn số m ngẫu nhiên Sinh hoán vị có độ dài m M - random permutation 1 permutation 2 permutation n ... GA - nested GA khởi tạo chuỗi hành trình Khởi tạo thời gian sạc cho cá thể tốt nhất (nested GA) Lai ghép ĐK dừng Thêm vào quần thể Đột biến Chọn lọc Cá thể tốt nhất ALGORITHM GA mức dưới Khởi tạo chuỗi hành trình GA mức trên Gán thời gian cho 1 chu trình sạc Thời gian sạc tại mỗi node được xác định theo công thức: Từ vecto chu trình sạc và thời gian sạc → Giá trị thích nghi của các cá thể V. Kết quả V. Kết quả Tập dữ liệu: Tên: small-grid 5 bộ: Phân phối Grid Số lượng cảm biến từng bộ: 200, 250, 300, 450, 500 Giá trị thực nghiệm: Emax: 10800 (J) Emin: 540 (J) Emc: 108000 (J) Pm: 1 (J/m) U: 5 (J/s) v: 5 (m/s) Kết luận Đọc bài báo cáo và cài đặt lại thuật toán Đề xuất thêm hướng giải quyết và cài đặt đưa ra so sánh Thank you!