Minimizing the Maximum Charging Delay of Multiple Mobile Chargers Under the Multi-Node Energy Charging Scheme
Minimizing the Maximum Charging Delay of Multiple Mobile Chargers Under the Multi-Node Energy Charging Scheme
复制标题
最小化多节点能量充电方案下多个移动充电器的最大充电延迟
DOI：
10.1109/tmc.2020.2973979
复制
发表时间：
2021-05-01
影响因子：
7.9
通讯作者：
Zhang, Xinming
中科院分区：
文献类型：
--
作者：
Xu, Wenzheng;Liang, Weifa;Zhang, Xinming
在无线可充电传感器网络（WRSNs）中，无线能量充电已成为一种非常有前途的延长传感器寿命的技术。现有的研究主要集中在1对1充电方案上，即单个传感器每次都可以通过移动充电器进行充电，但这种充电方案存在充电可扩展性差、效率低的问题。最近，另一种充电方案成为主流，即允许多个传感器通过移动充电器同时充电的多节点充电方案，该方案可以降低充电的可扩展性，提高充电效率。然而，以往对这种多节点能量充电方案的研究大多集中在使用单个移动充电器同时为多个传感器充电。对于大规模的wrn，仅部署一个移动充电器来为许多寿命关键型传感器充电是不够的，因此传感器的失效时间将急剧增加。为了尽早对大型wrn中许多寿命关键型传感器进行充电，采用多个移动充电器对传感器进行充电是必然的，这样既可以加快传感器的充电速度，又可以减少传感器的失效时间。然而，这对合理安排多个移动充电器以最小化传感器之间的最长充电延迟提出了很大的挑战。一个重要的限制是，任何传感器都不能在任何时候由多个移动充电器充电，因为传感器不能从任何一个充电器接收任何能量，否则过度充电会损坏传感器的充电电池。因此，为多个充电器中的每一个找到一个闭合充电巡回，使最长的充电延迟最小化是至关重要的。在本文中，我们通过制定一个新的最长充电延迟最小化问题来解决这一挑战。我们首先证明这个问题是np困难的。然后，我们设计了具有可证明的近似比的问题的第一个近似算法。最后，我们通过实验模拟来评估所提出算法的性能。实验结果表明，该算法具有良好的应用前景，在各种环境下均优于现有算法。
Wireless energy charging has emerged as a very promising technology for prolonging sensor lifetime in wireless rechargeable sensor networks (WRSNs). Existing studies focused mainly on the one-to-one charging scheme that a single sensor can be charged by a mobile charger at each time, this charging scheme however suffers from poor charging scalability and inefficiency. Recently, another charging scheme, the multi-node charging scheme that allows multiple sensors to be charged simultaneously by a mobile charger, becomes dominant, which can mitigate charging scalability and improve charging efficiency. However, most previous studies on this multi-node energy charging scheme focused on the use of a single mobile charger to charge multiple sensors simultaneously. For large scale WRSNs, it is insufficient to deploy only a single mobile charger to charge many lifetime-critical sensors, and consequently sensor expiration durations will increase dramatically. To charge many lifetime-critical sensors in large scale WRSNs as early as possible, it is inevitable to adopt multiple mobile chargers for sensor charging that can not only speed up sensor charging but also reduce expiration times of sensors. This however poses great challenges to fairly schedule the multiple mobile chargers such that the longest charging delay among sensors is minimized. One important constraint is that no sensor can be charged by more than one mobile charger at any time due to the fact that the sensor cannot receive any energy from either of the chargers or the overcharging will damage the recharging battery of the sensor. Thus, finding a closed charge tour for each of the multiple chargers such that the longest charging delay is minimized is crucial. In this paper we address the challenge by formulating a novel longest charging delay minimization problem. We first show that the problem is NP-hard. We then devise the very first approximation algorithm with a provable approximation ratio for the problem. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithm is promising, and outperforms existing algorithms in various settings.