Name
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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1109/SAHCN.2016.7732987 | 2016 13th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON) |
Keywords | Field | DocType |
energy synchronized task assignment,wireless rechargeable sensor networks,power constraint problem,battery powered systems,charging routes,charging efficiency,harvested energy,charging delay,online task assignment algorithm,lower bound assignment,charging velocity,multiple knapsack problem,polynomial-time approximation scheme,approximation ratio,ACT,greedy algorithm | Weapon target assignment problem,Mathematical optimization,Wireless,Upper and lower bounds,Computer science,Greedy algorithm,Assignment problem,Knapsack problem,Wireless sensor network,Performance improvement,Distributed computing | Conference |
ISBN | Citations | PageRank |
978-1-5090-1733-1 | 3 | 0.38 |
References | Authors | |
21 | 9 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zheng Dong | 1 | 51 | 9.62 |
| Cong Liu | 2 | 780 | 56.17 |
| Lingkun Fu | 3 | 200 | 10.45 |
| Peng Cheng | 4 | 131 | 11.86 |
| Liang He | 5 | 434 | 29.93 |
| Yu Gu 0001 | 6 | 333 | 22.96 |
| Wei Gao | 7 | 311 | 19.34 |
| Chau Yuen | 8 | 4493 | 263.28 |
| Tian He | 9 | 6869 | 447.17 |