A genetic approach to solve the emergent charging scheduling problem using multiple charging vehicles for wireless rechargeable sensor networks

Rei Heng Cheng, Cheng Jie Xu, Tung-Kuang Wu

Research output: Contribution to journalArticle

Abstract

Wireless rechargeable sensor networks (WRSNs) have gained much attention in recent years due to the rapid progress that has occurred in wireless charging technology. The charging is usually done by one or multiple mobile vehicle(s) equipped with wireless chargers moving toward sensors demanding energy replenishing. Since the loading of each sensor in a WRSN can be different, their time to energy exhaustion may also be varied. Under some circumstances, sensors may deplete their energy quickly and need to be charged urgently. Appropriate scheduling of available mobile charger(s) so that all sensors in need of recharge can be served in time is thus essential to ensure sustainable operation of the entire network, which unfortunately has been proven to be an NP-hard problem (Non-deterministic Polynomial-time hard). Two essential criteria that need to be considered concurrently in such a problem are time (the sensor’s deadline for recharge) and distance (from charger to the sensor demands recharge). Previous works use a static combination of these two parameters in determining charging order, which may fail to meet all the sensors’ charging requirements in a dynamically changing network. Genetic algorithms, which have long been considered a powerful tool for solving the scheduling problems, have also been proposed to address the charging route scheduling issue. However, previous genetic-based approaches considered only one charging vehicle scenario that may be more suitable for a smaller WRSN. With the availability of multiple mobile chargers, not only may more areas be covered, but also the network lifetime can be sustained for longer. However, efficiently allocating charging tasks to multiple charging vehicles would be an even more complex problem. In this work, a genetic approach, which includes novel designs in chromosome structure, selection, cross-over and mutation operations, supporting multiple charging vehicles is proposed. Two unique features are incorporated into the proposed algorithm to improve its scheduling effectiveness and performance, which include (1) inclusion of EDF (Earliest Deadline First) and NJF (Nearest Job First) scheduling outcomes into the initial chromosomes, and (2) clustering neighboring sensors demand recharge and then assigning sensors in a group to the same mobile charger. By including EDF and NJF scheduling outcomes into the first genetic population, we guarantee both time and distance factors are taken into account, and the weightings of the two would be decided dynamically through the genetic process to reflect various network traffic conditions. In addition, with the extra clustering step, the movement of each charger may be confined to a more local area, which effectively reduces the travelling distance, and thus the energy consumption, of the chargers in a multiple-charger environment. Extensive simulations and results show that the proposed algorithm indeed derives feasible charge scheduling for multiple chargers to keep the sensors/network in operation, and at the same time minimize the overall moving distance of the mobile chargers.

Original languageEnglish
Article number287
JournalEnergies
Volume12
Issue number2
DOIs
Publication statusPublished - 2019 Jan 17

Fingerprint

Sensor networks
Wireless Sensor Networks
Scheduling Problem
Scheduling
Sensor
Sensors
Earliest Deadline First
Chromosomes
Chromosome
Energy
Clustering
Population Genetics
Network Lifetime
Network Traffic
Deadline
NP-hard Problems
Sensor Networks
Energy Consumption
Weighting
Crossover

All Science Journal Classification (ASJC) codes

  • Renewable Energy, Sustainability and the Environment
  • Energy Engineering and Power Technology
  • Energy (miscellaneous)
  • Control and Optimization
  • Electrical and Electronic Engineering

Cite this

@article{2ee348393ce747ae9a7d93e138d5572d,
title = "A genetic approach to solve the emergent charging scheduling problem using multiple charging vehicles for wireless rechargeable sensor networks",
abstract = "Wireless rechargeable sensor networks (WRSNs) have gained much attention in recent years due to the rapid progress that has occurred in wireless charging technology. The charging is usually done by one or multiple mobile vehicle(s) equipped with wireless chargers moving toward sensors demanding energy replenishing. Since the loading of each sensor in a WRSN can be different, their time to energy exhaustion may also be varied. Under some circumstances, sensors may deplete their energy quickly and need to be charged urgently. Appropriate scheduling of available mobile charger(s) so that all sensors in need of recharge can be served in time is thus essential to ensure sustainable operation of the entire network, which unfortunately has been proven to be an NP-hard problem (Non-deterministic Polynomial-time hard). Two essential criteria that need to be considered concurrently in such a problem are time (the sensor’s deadline for recharge) and distance (from charger to the sensor demands recharge). Previous works use a static combination of these two parameters in determining charging order, which may fail to meet all the sensors’ charging requirements in a dynamically changing network. Genetic algorithms, which have long been considered a powerful tool for solving the scheduling problems, have also been proposed to address the charging route scheduling issue. However, previous genetic-based approaches considered only one charging vehicle scenario that may be more suitable for a smaller WRSN. With the availability of multiple mobile chargers, not only may more areas be covered, but also the network lifetime can be sustained for longer. However, efficiently allocating charging tasks to multiple charging vehicles would be an even more complex problem. In this work, a genetic approach, which includes novel designs in chromosome structure, selection, cross-over and mutation operations, supporting multiple charging vehicles is proposed. Two unique features are incorporated into the proposed algorithm to improve its scheduling effectiveness and performance, which include (1) inclusion of EDF (Earliest Deadline First) and NJF (Nearest Job First) scheduling outcomes into the initial chromosomes, and (2) clustering neighboring sensors demand recharge and then assigning sensors in a group to the same mobile charger. By including EDF and NJF scheduling outcomes into the first genetic population, we guarantee both time and distance factors are taken into account, and the weightings of the two would be decided dynamically through the genetic process to reflect various network traffic conditions. In addition, with the extra clustering step, the movement of each charger may be confined to a more local area, which effectively reduces the travelling distance, and thus the energy consumption, of the chargers in a multiple-charger environment. Extensive simulations and results show that the proposed algorithm indeed derives feasible charge scheduling for multiple chargers to keep the sensors/network in operation, and at the same time minimize the overall moving distance of the mobile chargers.",
author = "Cheng, {Rei Heng} and Xu, {Cheng Jie} and Tung-Kuang Wu",
year = "2019",
month = "1",
day = "17",
doi = "10.3390/en12020287",
language = "English",
volume = "12",
journal = "Energies",
issn = "1996-1073",
publisher = "Multidisciplinary Digital Publishing Institute (MDPI)",
number = "2",

}

A genetic approach to solve the emergent charging scheduling problem using multiple charging vehicles for wireless rechargeable sensor networks. / Cheng, Rei Heng; Xu, Cheng Jie; Wu, Tung-Kuang.

In: Energies, Vol. 12, No. 2, 287, 17.01.2019.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A genetic approach to solve the emergent charging scheduling problem using multiple charging vehicles for wireless rechargeable sensor networks

AU - Cheng, Rei Heng

AU - Xu, Cheng Jie

AU - Wu, Tung-Kuang

PY - 2019/1/17

Y1 - 2019/1/17

N2 - Wireless rechargeable sensor networks (WRSNs) have gained much attention in recent years due to the rapid progress that has occurred in wireless charging technology. The charging is usually done by one or multiple mobile vehicle(s) equipped with wireless chargers moving toward sensors demanding energy replenishing. Since the loading of each sensor in a WRSN can be different, their time to energy exhaustion may also be varied. Under some circumstances, sensors may deplete their energy quickly and need to be charged urgently. Appropriate scheduling of available mobile charger(s) so that all sensors in need of recharge can be served in time is thus essential to ensure sustainable operation of the entire network, which unfortunately has been proven to be an NP-hard problem (Non-deterministic Polynomial-time hard). Two essential criteria that need to be considered concurrently in such a problem are time (the sensor’s deadline for recharge) and distance (from charger to the sensor demands recharge). Previous works use a static combination of these two parameters in determining charging order, which may fail to meet all the sensors’ charging requirements in a dynamically changing network. Genetic algorithms, which have long been considered a powerful tool for solving the scheduling problems, have also been proposed to address the charging route scheduling issue. However, previous genetic-based approaches considered only one charging vehicle scenario that may be more suitable for a smaller WRSN. With the availability of multiple mobile chargers, not only may more areas be covered, but also the network lifetime can be sustained for longer. However, efficiently allocating charging tasks to multiple charging vehicles would be an even more complex problem. In this work, a genetic approach, which includes novel designs in chromosome structure, selection, cross-over and mutation operations, supporting multiple charging vehicles is proposed. Two unique features are incorporated into the proposed algorithm to improve its scheduling effectiveness and performance, which include (1) inclusion of EDF (Earliest Deadline First) and NJF (Nearest Job First) scheduling outcomes into the initial chromosomes, and (2) clustering neighboring sensors demand recharge and then assigning sensors in a group to the same mobile charger. By including EDF and NJF scheduling outcomes into the first genetic population, we guarantee both time and distance factors are taken into account, and the weightings of the two would be decided dynamically through the genetic process to reflect various network traffic conditions. In addition, with the extra clustering step, the movement of each charger may be confined to a more local area, which effectively reduces the travelling distance, and thus the energy consumption, of the chargers in a multiple-charger environment. Extensive simulations and results show that the proposed algorithm indeed derives feasible charge scheduling for multiple chargers to keep the sensors/network in operation, and at the same time minimize the overall moving distance of the mobile chargers.

AB - Wireless rechargeable sensor networks (WRSNs) have gained much attention in recent years due to the rapid progress that has occurred in wireless charging technology. The charging is usually done by one or multiple mobile vehicle(s) equipped with wireless chargers moving toward sensors demanding energy replenishing. Since the loading of each sensor in a WRSN can be different, their time to energy exhaustion may also be varied. Under some circumstances, sensors may deplete their energy quickly and need to be charged urgently. Appropriate scheduling of available mobile charger(s) so that all sensors in need of recharge can be served in time is thus essential to ensure sustainable operation of the entire network, which unfortunately has been proven to be an NP-hard problem (Non-deterministic Polynomial-time hard). Two essential criteria that need to be considered concurrently in such a problem are time (the sensor’s deadline for recharge) and distance (from charger to the sensor demands recharge). Previous works use a static combination of these two parameters in determining charging order, which may fail to meet all the sensors’ charging requirements in a dynamically changing network. Genetic algorithms, which have long been considered a powerful tool for solving the scheduling problems, have also been proposed to address the charging route scheduling issue. However, previous genetic-based approaches considered only one charging vehicle scenario that may be more suitable for a smaller WRSN. With the availability of multiple mobile chargers, not only may more areas be covered, but also the network lifetime can be sustained for longer. However, efficiently allocating charging tasks to multiple charging vehicles would be an even more complex problem. In this work, a genetic approach, which includes novel designs in chromosome structure, selection, cross-over and mutation operations, supporting multiple charging vehicles is proposed. Two unique features are incorporated into the proposed algorithm to improve its scheduling effectiveness and performance, which include (1) inclusion of EDF (Earliest Deadline First) and NJF (Nearest Job First) scheduling outcomes into the initial chromosomes, and (2) clustering neighboring sensors demand recharge and then assigning sensors in a group to the same mobile charger. By including EDF and NJF scheduling outcomes into the first genetic population, we guarantee both time and distance factors are taken into account, and the weightings of the two would be decided dynamically through the genetic process to reflect various network traffic conditions. In addition, with the extra clustering step, the movement of each charger may be confined to a more local area, which effectively reduces the travelling distance, and thus the energy consumption, of the chargers in a multiple-charger environment. Extensive simulations and results show that the proposed algorithm indeed derives feasible charge scheduling for multiple chargers to keep the sensors/network in operation, and at the same time minimize the overall moving distance of the mobile chargers.

UR - http://www.scopus.com/inward/record.url?scp=85060525288&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85060525288&partnerID=8YFLogxK

U2 - 10.3390/en12020287

DO - 10.3390/en12020287

M3 - Article

VL - 12

JO - Energies

JF - Energies

SN - 1996-1073

IS - 2

M1 - 287

ER -