Skip to main content
Article
Approximation Algorithms for Charging Reward Maximization in Rechargeable Sensor Networks Via a Mobile Charger
IEEE/ACM Transactions on Networking
  • Weifa Liang
  • Zichuan Xu
  • Wenzheng Xu
  • Jiugen Shi
  • Guoqiang Mao
  • Sajal K. Das, Missouri University of Science and Technology
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
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
10-1-2017
Publication Date
01 Oct 2017
Disciplines
Citation Information
Weifa Liang, Zichuan Xu, Wenzheng Xu, Jiugen Shi, et al.. "Approximation Algorithms for Charging Reward Maximization in Rechargeable Sensor Networks Via a Mobile Charger" IEEE/ACM Transactions on Networking Vol. 25 Iss. 5 (2017) p. 3161 - 3174 ISSN: 1063-6692; 1558-2566
Available at: http://works.bepress.com/sajal-das/32/