TY - GEN
T1 - Finite-horizon energy allocation and routing scheme in rechargeable sensor networks
AU - Chen, Shengbo
AU - Sinha, Prasun
AU - Shroff, Ness B.
AU - Joo, Changhee
PY - 2011
Y1 - 2011
N2 - In this paper, we investigate the problem of maximizing the throughput over a finite-horizon time period for a sensor network with energy replenishment. The finite-horizon problem is important and challenging because it necessitates optimizing metrics over the short term rather than metrics that are averaged over a long period of time. Unlike the infinite-horizon problem, the fact that inefficiencies cannot be made to vanish to infinitesimally small values, means that the finite-horizon problem requires more delicate control. The finite-horizon throughput optimization problem can be formulated as a convex optimization problem, but turns out to be highly complex. The complexity is brought about by the "time coupling property", which implies that current decisions can influence future performance. To address this problem, we employ a three-step approach. First, we focus on the throughput maximization problem for a single node with renewable energy assuming that the replenishment rate profile for the entire finite-horizon period is known in advance. An energy allocation scheme that is equivalent to computing a shortest path in a simply-connected space is developed and proven to be optimal. We then relax the assumption that the future replenishment profile is known and develop an online algorithm. The online algorithm guarantees a fraction of the optimal throughput. Motivated by these results, we propose a low-complexity heuristic distributed scheme, called NetOnline, in a rechargeable sensor network. We prove that this heuristic scheme is optimal under homogeneous replenishment profiles. Further, in more general settings, we show via simulations that NetOnline significantly outperforms a state-of-the-art infinite-horizon based scheme, and for certain configurations using data collected from a testbed sensor network, it achieves empirical performance close to optimal.
AB - In this paper, we investigate the problem of maximizing the throughput over a finite-horizon time period for a sensor network with energy replenishment. The finite-horizon problem is important and challenging because it necessitates optimizing metrics over the short term rather than metrics that are averaged over a long period of time. Unlike the infinite-horizon problem, the fact that inefficiencies cannot be made to vanish to infinitesimally small values, means that the finite-horizon problem requires more delicate control. The finite-horizon throughput optimization problem can be formulated as a convex optimization problem, but turns out to be highly complex. The complexity is brought about by the "time coupling property", which implies that current decisions can influence future performance. To address this problem, we employ a three-step approach. First, we focus on the throughput maximization problem for a single node with renewable energy assuming that the replenishment rate profile for the entire finite-horizon period is known in advance. An energy allocation scheme that is equivalent to computing a shortest path in a simply-connected space is developed and proven to be optimal. We then relax the assumption that the future replenishment profile is known and develop an online algorithm. The online algorithm guarantees a fraction of the optimal throughput. Motivated by these results, we propose a low-complexity heuristic distributed scheme, called NetOnline, in a rechargeable sensor network. We prove that this heuristic scheme is optimal under homogeneous replenishment profiles. Further, in more general settings, we show via simulations that NetOnline significantly outperforms a state-of-the-art infinite-horizon based scheme, and for certain configurations using data collected from a testbed sensor network, it achieves empirical performance close to optimal.
UR - http://www.scopus.com/inward/record.url?scp=79960873534&partnerID=8YFLogxK
U2 - 10.1109/INFCOM.2011.5935044
DO - 10.1109/INFCOM.2011.5935044
M3 - Conference contribution
AN - SCOPUS:79960873534
SN - 9781424499212
T3 - Proceedings - IEEE INFOCOM
SP - 2273
EP - 2281
BT - 2011 Proceedings IEEE INFOCOM
T2 - IEEE INFOCOM 2011
Y2 - 10 April 2011 through 15 April 2011
ER -