Title: Optimal $k$-Coverage Charging Problem,
Abstract: Wireless rechargeable sensor networks, consisting of sensor nodes with
rechargeable batteries and mobile chargers to replenish their batteries, have
gradually become a promising solution to the bottleneck of energy limitation
that hinders the wide deployment of wireless sensor networks (WSN). In this
paper, we focus on the mobile charger scheduling and path optimization scenario
in which the $k$-coverage ability of a network system needs to be maintained.
We formulate the optimal $k$-coverage charging problem of finding a feasible
path for a mobile charger to charge a set of sensor nodes within their
estimated charging time windows under the constraint of maintaining the
$k$-coverage ability of the network system, with an objective of minimizing the
energy consumption on traveling per tour. We show the hardness of the problem
that even finding a feasible path for the trivial case of the problem is an
NP-complete one with no polytime constant-factor approximation algorithm.