Energy synchronized task assignment in rechargeable sensor networks

Zheng Dong, Cong Liu, Lingkun Fu, Peng Cheng, Liang He, Yu Gu, Wei Gao, Chau Yuen, Tian He

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

Wireless rechargeable sensor networks have recently emerged as a promising platform that can effectively solve the power constraint problem suffered by traditional battery powered systems. The problem of determining the best charging routes for maximizing charging efficiency has been studied extensively. However, the task assignment problem, which plays a crucial role in efficiently utilizing the harvested energy and thus minimize the charging delay, has received rather limited attention. In this paper, we study the problem of assigning a given set of tasks in a wireless rechargeable sensor network while maximizing the charger's velocity to minimize the charging delay. We first propose an online task assignment algorithm, namely Lower Bound assignment (LB), that yields a quantifiable lower bound on the charging velocity while guaranteeing a feasible assignment. This algorithm further enables the transformation of our considered task assignment problem into a variation of the classical multiple knapsack problem. We then present a fully polynomial-time approximation scheme with a (2+ϵ)-approximation ratio, namely ACT, that is built upon an existing greedy algorithm designed for the original knapsack problem. Extensive experimental results presented herein demonstrate that ACT is able to achieve near-optimal performance in most cases, and can achieve more than 15% performance improvement compared to the baseline algorithms.

Original languageEnglish (US)
Title of host publication2016 13th Annual IEEE International Conference on Sensing, Communication, and Networking, SECON 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781509017324
DOIs
StatePublished - Nov 2 2016
Event13th Annual IEEE International Conference on Sensing, Communication, and Networking, SECON 2016 - London, United Kingdom
Duration: Jun 27 2016Jun 30 2016

Publication series

Name2016 13th Annual IEEE International Conference on Sensing, Communication, and Networking, SECON 2016

Other

Other13th Annual IEEE International Conference on Sensing, Communication, and Networking, SECON 2016
CountryUnited Kingdom
CityLondon
Period6/27/166/30/16

Fingerprint Dive into the research topics of 'Energy synchronized task assignment in rechargeable sensor networks'. Together they form a unique fingerprint.

  • Cite this

    Dong, Z., Liu, C., Fu, L., Cheng, P., He, L., Gu, Y., Gao, W., Yuen, C., & He, T. (2016). Energy synchronized task assignment in rechargeable sensor networks. In 2016 13th Annual IEEE International Conference on Sensing, Communication, and Networking, SECON 2016 [7732987] (2016 13th Annual IEEE International Conference on Sensing, Communication, and Networking, SECON 2016). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SAHCN.2016.7732987