Scheduling Precedence Constraints among Charging Tasks in Wireless Rechargeable Sensor Networks
The development of wireless power transfer (WPT) facilitates wireless rechargeable sensor networks (WRSNs) receiving considerable attention in the sensor network research community. Most existing works mainly focus on general charging patterns and metrics while overlooking the precedence constraints...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-01-01
|
| Series: | Electronics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2079-9292/13/2/346 |
| _version_ | 1797344229815484416 |
|---|---|
| author | Lanlan Li Haipeng Dai Chen Chen Zilu Ni Shihao Li |
| author_facet | Lanlan Li Haipeng Dai Chen Chen Zilu Ni Shihao Li |
| author_sort | Lanlan Li |
| collection | DOAJ |
| description | The development of wireless power transfer (WPT) facilitates wireless rechargeable sensor networks (WRSNs) receiving considerable attention in the sensor network research community. Most existing works mainly focus on general charging patterns and metrics while overlooking the precedence constraints among tasks, resulting in charging inefficiency. In this paper, we are the first to advance the issue of scheduling wireless charging tasks with precedence constraints (SCPC), with the optimization objective of minimizing the completion time of all the charging tasks under the precedence constraints while guaranteeing that the energy capacity of the mobile charger (MC) is not exhausted and the deadlines of charging tasks are not exceeded. In order to address this problem, we first propose a priority-based topological sort scheme to derive a unique feasible sequence on a directed acyclic graph (DAG). Then, we combine the proposed priority-based topological sort scheme with the procedure of a genetic algorithm to obtain the final solution through a series of genetic operators. Finally, we conduct extensive simulations to validate our proposed algorithm under the condition of three different network sizes. The results show that our proposed algorithm outperformed the other comparison algorithms by up to <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>11.59</mn><mo>%</mo></mrow></semantics></math></inline-formula> in terms of completion time. |
| first_indexed | 2024-03-08T10:59:21Z |
| format | Article |
| id | doaj.art-955eb1bb942947bb8ea939be1f60de0c |
| institution | Directory Open Access Journal |
| issn | 2079-9292 |
| language | English |
| last_indexed | 2024-03-08T10:59:21Z |
| publishDate | 2024-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Electronics |
| spelling | doaj.art-955eb1bb942947bb8ea939be1f60de0c2024-01-26T16:13:59ZengMDPI AGElectronics2079-92922024-01-0113234610.3390/electronics13020346Scheduling Precedence Constraints among Charging Tasks in Wireless Rechargeable Sensor NetworksLanlan Li0Haipeng Dai1Chen Chen2Zilu Ni3Shihao Li4Department of Information Engineering, Nanjing University of Aeronautics and Astronautics Jincheng College, Nanjing 211156, ChinaState Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, ChinaDepartment of Information Engineering, Nanjing University of Aeronautics and Astronautics Jincheng College, Nanjing 211156, ChinaDepartment of Information Engineering, Nanjing University of Aeronautics and Astronautics Jincheng College, Nanjing 211156, ChinaDepartment of Information Engineering, Nanjing University of Aeronautics and Astronautics Jincheng College, Nanjing 211156, ChinaThe development of wireless power transfer (WPT) facilitates wireless rechargeable sensor networks (WRSNs) receiving considerable attention in the sensor network research community. Most existing works mainly focus on general charging patterns and metrics while overlooking the precedence constraints among tasks, resulting in charging inefficiency. In this paper, we are the first to advance the issue of scheduling wireless charging tasks with precedence constraints (SCPC), with the optimization objective of minimizing the completion time of all the charging tasks under the precedence constraints while guaranteeing that the energy capacity of the mobile charger (MC) is not exhausted and the deadlines of charging tasks are not exceeded. In order to address this problem, we first propose a priority-based topological sort scheme to derive a unique feasible sequence on a directed acyclic graph (DAG). Then, we combine the proposed priority-based topological sort scheme with the procedure of a genetic algorithm to obtain the final solution through a series of genetic operators. Finally, we conduct extensive simulations to validate our proposed algorithm under the condition of three different network sizes. The results show that our proposed algorithm outperformed the other comparison algorithms by up to <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>11.59</mn><mo>%</mo></mrow></semantics></math></inline-formula> in terms of completion time.https://www.mdpi.com/2079-9292/13/2/346wireless chargingWRSNsprecedence constraintsgenetic algorithm |
| spellingShingle | Lanlan Li Haipeng Dai Chen Chen Zilu Ni Shihao Li Scheduling Precedence Constraints among Charging Tasks in Wireless Rechargeable Sensor Networks Electronics wireless charging WRSNs precedence constraints genetic algorithm |
| title | Scheduling Precedence Constraints among Charging Tasks in Wireless Rechargeable Sensor Networks |
| title_full | Scheduling Precedence Constraints among Charging Tasks in Wireless Rechargeable Sensor Networks |
| title_fullStr | Scheduling Precedence Constraints among Charging Tasks in Wireless Rechargeable Sensor Networks |
| title_full_unstemmed | Scheduling Precedence Constraints among Charging Tasks in Wireless Rechargeable Sensor Networks |
| title_short | Scheduling Precedence Constraints among Charging Tasks in Wireless Rechargeable Sensor Networks |
| title_sort | scheduling precedence constraints among charging tasks in wireless rechargeable sensor networks |
| topic | wireless charging WRSNs precedence constraints genetic algorithm |
| url | https://www.mdpi.com/2079-9292/13/2/346 |
| work_keys_str_mv | AT lanlanli schedulingprecedenceconstraintsamongchargingtasksinwirelessrechargeablesensornetworks AT haipengdai schedulingprecedenceconstraintsamongchargingtasksinwirelessrechargeablesensornetworks AT chenchen schedulingprecedenceconstraintsamongchargingtasksinwirelessrechargeablesensornetworks AT ziluni schedulingprecedenceconstraintsamongchargingtasksinwirelessrechargeablesensornetworks AT shihaoli schedulingprecedenceconstraintsamongchargingtasksinwirelessrechargeablesensornetworks |