Approximation Algorithms for Charging Reward Maximization in Rechargeable Sensor Networks Via a Mobile Charger

Abstract

Wireless energy transfer has emerged as a promising technology for wireless sensor networks to power sensors with controllable yet perpetual energy. In this paper, we study sensor energy replenishment by employing a mobile charger (charging vehicle) to charge sensors wirelessly in a rechargeable sensor network, so that the sum of charging rewards collected from all charged sensors by the mobile charger per tour is maximized, subject to the energy capacity of the mobile charger, where the amount of reward received from a charged sensor is proportional to the amount of energy charged to the sensor. The energy of the mobile charger will be spent on both its mechanical movement and sensor charging. We first show that this problem is NP-hard. We then propose approximation algorithms with constant approximation ratios under two different settings: one is that a sensor will be charged to its full energy capacity if it is charged; another is that a sensor can be charged multiple times per tour but the total amount of energy charged is no more than its energy demand prior to the tour. We finally evaluate the performance of the proposed algorithms through experimental simulations. The simulation results demonstrate that the proposed algorithms are very promising, and the solutions obtained are fractional of the optimum. To the best of our knowledge, the proposed algorithms are the very first approximation algorithms with guaranteed approximation ratios for the mobile charger scheduling in a rechargeable sensor network under the energy capacity constraint on the mobile charger.

Department(s)

Computer Science

Research Center/Lab(s)

Intelligent Systems Center

Second Research Center/Lab

Center for High Performance Computing Research

Comments

The work of W. Xu was supported by the National Natural Science Foundation of China under Grant 61602330.

Keywords and Phrases

Combinatorial optimization; Energy transfer; Heuristic algorithms; Inductive power transmission; Mobile computing; Mobile telecommunication systems; Optimization; Reinforcement; Scheduling; Wireless sensor networks; Wireless telecommunication systems; Combinatorial optimization problems; Mobile chargers; Mobile communications; Wireless communications; Wireless energy transfers; Approximation algorithms; Rechargeable wireless sensor networks; Sensor energy replenishments; Wireless energy transfer

International Standard Serial Number (ISSN)

1063-6692; 1558-2566

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2017 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.

Publication Date

01 Oct 2017

Link to Full Text

Share

 
COinS