Optimizing the service policy of a wireless access point on the move with renewable energy

摘要

Inspired by recent industry efforts toward providing Internet access to areas of the world devoid of regular telecommunications infrastructure, an online resource allocation problem for a mobile access point (AP) is studied. While prudently managing its available energy, the AP allocates its resources to maximize the total utility (reward) provided to the users demanding service. The problem is formulated as a 0/1 dynamic knapsack problem with incremental capacity in a finite time horizon, the solution of which is quite open in the literature. The problem is approached from through stochastic and deterministic formulations. For the stochastic case, using a dynamic programming setup, the optimality of a threshold based solution is exhibited, and a simple threshold based policy which performs closely to optimal is obtained via the expected threshold method. For the deterministic formulation, several online heuristics based on an instantaneous threshold that can adapt to short-time-scale dynamics are proposed, including one with an optimal competitive ratio under a certain condition. The performance of all heuristics are comparatively studied.