Đề tài Effective partial charging scheme for minimizing the energy depletion and charging cost in wirelessrechargeable sensor networks

Effective partial charging scheme for minimizingthe energy depletion and charging cost in wirelessrechargeable sensor networks  Tran Thi Huong ∗y , Le Van Cuong ∗ , Nguyen Ngoc Bao ∗ , Ngo Minh Hai ∗ , Huynh Thi Thanh Binh ∗  Nhóm 5: Đỗ Hoàng Việt - 20183665 Đỗ Nguyên Long - 20183580 Table of contents I. Giới thiệu II. Mô tả về bài toán III. Thuật toán IV. Đề xuất I. Giới thiệu Mạng cảm biến không dây ngày nay có vai trò rất quan trọng đối với cuộc sống của chúng ta. Một vài ví dụ tiêu biểu như là các cảm biến dùng trong dự báo thời tiết, quân sự, Các cảm biến này cần năng lượng để hoạt động và truyền dữ liệu cho trạm. I. Giới thiệu Hiện tại mạng cảm biến có thể sạc lại đang là ưu tiên. Các cảm biến được sạc bằng thiết bị sạc di động. Vì vậy việc lập được lịch sạc cho mạng cảm biến có ý nghĩa rất quan trọng để kéo dài tuổi thọ của cảm biến. Các phương pháp để lập lịch sạc cần: Tối ưu đường đi của các thiết bị sạc. Tối ưu thời gian sạc tại 1 cảm biến II. Mô tả về bài toán Input Một trạm cố định s o có tọa độ (x 0 , y 0 ) S = {s 1 , s 2 ,, s n } là tập các cảm biến. Mỗi cảm biến có tọa độ, năng lượng cực đại Emax và cực tiểu Emin Một xe sạc dùng để sạc các cảm biến, có năng lượng E MC , vận tốc V, công suất tiêu thụ P M Output Một chu trình sạc ℘ = {π 0 , π 1 , π 2 , . . . , π m , π 0 } t = {t1, . . . , tm} là thời gian sạc tại mỗi nút Mục tiêu bài toán Giảm thiểu tối đa số nút chết Tiết kiệm tối đa năng lượng cho xe sạc II. Mô tả về bài toán Để biết được nút nào sẽ chết sau chu trình sạc, chúng ta định nghĩa một biến nhị phân z i , sao cho: Z i = Từ đó, hàm mục tiêu của chúng ta trở thành: Tối thiểu f = + (4) II. Mô tả về bài toán Ràng buộc: Năng lượng tiêu hao của xe trong quá trình di chuyển và sạc không được lớn hơn năng lượng tối đa: Năng lượng của nút sạc sau khi sạc không được lớn hơn năng lượng tối đa của chúng: E depot i − a i × p i + t i × (U − p i ) ≤ E max III. Thuật toán Mục tiêu của bài toán là giảm thiểu số nút chết nên chúng ta sẽ đặt thứ tự ưu tiên sạc cho các nút dựa trên: Năng lượng dư còn thấp Tốc độ tiêu hao năng lượng cao Dùng thuật toán fuzzy-logic để tính trọng số ưu tiên của các nút Sau khi sử dụng thuật toán fuzzy logic, ta có W = {w s1 , w s2 , . . . , w sn } là tập trọng số điểm của các nút Tối ưu chu trình sạc với tập W và thuật toán GA III. Thuật toán: Tìm đường đi tốt nhất Encoding cá thể Mỗi cá thể được encode bởi vector x = {x 1 , x 2 , . . . , x n } với x i là 1 một số bất kì thuộc đoạn [0, 1] Nếu x i <= w si thì nút i sẽ được thêm vào chu trình sạc, như vậy các nút có trọng số càng cao thì sẽ xác suất được sạc lớn. III. Thuật toán: Tìm đường đi tốt nhất Gererates initial population Cross over (Simualted Binary) Mutation (Polynomial) Evaluated Population Report best solution Elitism Reach Max gen Yes No III. Thuật toán: Tìm đường đi tốt nhất 2. Evaluated Population Xác định thời gian sạc tại mỗi nút τ π i = τ charge × với τ charge là cận trên của tổng thời gian sạc: τ charge = Sau đó, đánh giá chu trình sạc π theo hàm mục tiêu : f = + III. Thuật toán: Tìm đường đi tốt nhất Triển khai binary tournament để chọn cha mẹ Sau đó, quần thể hiện tại sẽ bị loại bỏ và được thay thế bằng con của chúng  III. Thuật toán: Tối ưu thời gian sạc Sử dụng GA để tối ưu thời gian sạc tại mỗi nút Giả sử chúng ta thu được ℘ * = {π 0 * , π 1 * , π 2 * , . . . , π m * } là chu trình tối ưu được xác định bởi bước trên Rồi sử dụng Simulated Binary Crossover, tận dụng SPAH là sự kết hợp của Single-Point Crossover và Arithmetic Crossover và Polynomial Mutation để tối ưu thời gian sạc IV. Đề xuất Nhận xét: Bài báo trên tối ưu cho 1 xe, phù hợp với diện tích vừa và nhỏ Không phù hợp với bài toán có diện tích lớn, số lượng nút cảm biến nhiều Vì vậy cần xây dựng chiến lược sạc bằng nhiều xe đồng thời. IV. Đề xuất Input Một trạm cố định s o có tọa độ (x 0 , y 0 ) S = {s 1 , s 2 ,, s n } là tập các cảm biến. Mỗi cảm biến có tọa độ, năng lượng cực đại Emax và cực tiểu Emin K xe sạc dùng để sạc các cảm biến, mỗi xe có năng lượng E MC , vận tốc V, công suất tiêu thụ P M Output Từng chu trình sạc ℘ = {π 0 , π 1 , π 2 , . . . , π m , π 0 } tương ứng của mỗi xe t = {t1, . . . , tm} là thời gian sạc tại mỗi nút Mục tiêu bài toán Pha 1: chia thành K cụm Pha 2: Giảm thiểu tối đa số nút chết Tiết kiệm tối đa năng lượng cho xe sạc IV. Đề xuất Dùng giải thuật Kmeans để chia các cụm, mỗi cụm sẽ do 1 xe phụ trách việc sạc. Bài toán sẽ trở thành bài toán nhiều xe sạc. Dựa vào vị trí các điểm ban đầu, sau khi chia thành các cụm con nhỏ hơn ta áp dụng cách tính như bài báo trên cho 1 xe và 1 cụm nhỏ hơn đã chia được. IV. Đề xuất G R R R R R R R R Nhược điểm: Chia cụm theo khoảng cách không tối ưu Công thức: β *100 Với , β <= 1 vào β = 1 time i : thời gian sống của nút I d ij : khoảng cách giữa 2 nút i, j IV. Đề xuất Kết quả: Ta có hình vẽ biểu diễn sự phụ thuộc của số nút chết vào số cụm được chia. IV. Đề xuất Ưu điểm: Chia cụm theo Kmeans dễ thực hiện Nhược điểm: Chưa tối ưu do chia cụm theo khoảng cách không phải là cách tốt nhất Do vấn đề về chi phí và số lượng cảm biến trong 1 cụm nên dựa vào đồ thị trên có thể thấy K = 3 sẽ là số cụm hợp lý. Định hướng: Sẽ phát triển thêm các thuật toán khác với bài toán có nhiều cảm biến. IV. Đề xuất Các bài báo đã được công bố làm với nhiều xe sạc : Minimizing the Maximum Charging Delay of Multiple Mobile Chargers Under the Multi-Node Energy Charging Scheme ( Wenzheng Xu, Member, IEEE , Weifa Liang, Senior Member, IEEE , Xiaohua Jia, Fellow, IEEE ,Haibin Kan, Yinlong Xu, and Xinming Zhang, Member, IEEE ) -2020 Minimizing the Longest Charge Delay of Multiple Mobile Chargers for Wireless Rechargeable SensorNetworks by Charging Multiple Sensors Simultaneously ( Minimizing the Longest Charge Delay of MultipleMobile Chargers for Wireless Rechargeable Sensor Networks by Charging Multiple Sensors Simultaneously )-2019 Utility-Aware Charging Scheduling for Multiple Mobile Chargers in Large-Scale Wireless Rechargeable Sensor Networks (Wenyu Ouyang, Xuxun Liu, Member, IEEE, Mohammad S. Obaidat, Life Fellow, IEEE, Chi Lin, Member, IEEE, Huan Zhou, Member, IEEE, Tang Liu, Member, IEEE, Kuei-Fang Hsiao, Senior Member, IEEE ) - 2020