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

Liang, W; Xu, Z; Xu, W; Shi, J; Mao, G; Das, SK

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

Liang, W Xu, Z Xu, W Shi, J Mao, G

Das, SK

Permalink

Publication Type:: Journal Article
Citation:: IEEE/ACM Transactions on Networking, 2017, 25 (5), pp. 3161 - 3174
Issue Date:: 2017-10-01

Closed Access

	Filename	Description	Size
	07999217.pdf	Published Version	2.14 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Liang, W	en_US
dc.contributor.author	Xu, Z	en_US
dc.contributor.author	Xu, W	en_US
dc.contributor.author	Shi, J	en_US
dc.contributor.author	Mao, G https://orcid.org/0000-0002-3598-4949	en_US
dc.contributor.author	Das, SK	en_US
dc.date.issued	2017-10-01	en_US
dc.identifier.citation	IEEE/ACM Transactions on Networking, 2017, 25 (5), pp. 3161 - 3174	en_US
dc.identifier.issn	1063-6692	en_US
dc.identifier.uri	http://hdl.handle.net/10453/123584
dc.description.abstract	© 1993-2012 IEEE. 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.	en_US
dc.relation.ispartof	IEEE/ACM Transactions on Networking	en_US
dc.relation.isbasedon	10.1109/TNET.2017.2723605	en_US
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject.classification	Networking & Telecommunications	en_US
dc.title	Approximation Algorithms for Charging Reward Maximization in Rechargeable Sensor Networks via a Mobile Charger	en_US
dc.type	Journal Article
utslib.citation.volume	5	en_US
utslib.citation.volume	25	en_US
utslib.for	0805 Distributed Computing	en_US
utslib.for	0906 Electrical and Electronic Engineering	en_US
utslib.for	1005 Communications Technologies	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Electrical and Data Engineering
pubs.organisational-group	/University of Technology Sydney/Strength - CRIN - Realtime Information Networks
utslib.copyright.status	closed_access	*
pubs.issue	5	en_US
pubs.publication-status	Published	en_US
pubs.volume	25	en_US

Abstract:

© 1993-2012 IEEE. 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.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/123584