Wireless Power Transfer (WPT) technology is considered as a promising approach to make Wireless Rechargeable Sensor Network (WRSN) work perpetually. In WRSN, a vehicle exists, termed a mobile charger, which can move close to sensor nodes and charge them wirelessly. Due to the mobile charger's limited traveling distance and speed, not every node that needs to be charged may be serviced in time. Thus, in such scenario, how to make a route plan for the mobile charger to determine which nodes should be charged first is a critical issue related to the network's Quality of Service (QoS). In this paper, we propose a mobile charger's scheduling algorithm to mitigate the data loss of network by considering the node's criticality in connectivity and energy. First, we introduce a novel metric named criticality index to measure node's connectivity contribution, which is computed as a summation of node's neighbor dissimilarity. Furthermore, to reflect the node's charging demand, an indicator called energy criticality is adopted to weight the criticality index, which is a normalized ratio of the node's consumed energy to its total energy. Then, we formulate an optimization problem with the objective of maximizing total weighted criticality indexes of nodes to construct a charging tour, subject to the mobile charger's traveling distance constraint. Due to the NP-hardness of the problem, a heuristic algorithm is proposed to solve it. The heuristic algorithm includes three steps, which is spanning tree growing, tour construction and tour improvement. Finally, we compare the proposed algorithm to the state-of-art scheduling algorithms. The obtained results demonstrate that the proposed algorithm is a promising one.
Keywords: criticality index; heuristic algorithm; mobile charger; recharge schedule; wireless rechargeable sensor network.