Currentcy Conserving Allocation

There are a number of ways to deal with the residual energy problem. One is to adjust the overall allocation level when the system detects that the battery is not being drained at the expected rate. If there is a consistent pattern of underspending by some tasks, the total allocation will grow, slowly at first, and be proportionally distributed to all tasks. Thus, needy tasks will benefit from receiving their share of a larger overall allocation.

Another approach is to explicitly redistribute excess currentcy to other tasks with insufficient currentcy for their energy demands. As a result of this approach, a task with a small energy share, determining its per-epoch allocation, may receive a large amount of excess currentcy. In this case, the task should have a large cap on its account balance to hold the extra currentcy. Similarly, for the tasks that consistently spend only a fraction of their energy share, the cap can be decreased to free the currentcy to the needy tasks. Specifically, we propose a two-step policy that first dynamically adjusts the per-task cap to reflect each task's energy needs (captured as the level of currentcy spent in previous epochs) as well as its specified share. The new cap is based on an exponential weighted average of currentcy expenditures in previous epochs. If the level of currentcy spent in the most recent epoch is low relative to its history, then a lower weight factor ($\alpha_l$) is used than otherwise ($\alpha_h$). We have found that assigning weights that increase the cap quickly ( $\alpha_h = 0.7$) and decrease it slowly ( $\alpha_l = 0.1$) produces desirable behavior.

Second, the system redistributes currentcy amounts that overflow some task's cap to other tasks whose limits have not been reached. Specifically, our allocation algorithm behaves as follows: a) Every epoch, all containers receive currentcy proportionally unless their caps are reached. b) No currentcy is thrown away unless all containers reach their caps. c) Any currentcy overflow from a container is redistributed to other containers with unfilled capacity. For instance, for a total of containers, if (where ) containers reach their caps, the currentcy not allocated to the containers is redistributed to the other containers, proportional to their shares. The first step of our our allocation algorithm is to sort containers so that for any (for ), will not reach its cap unless reaches its cap first. The rest of the algorithm simply walks through the container list and does the following for each , such that :

1. Calculate the entitled currentcy according to its energy share:

   where was initialized to be the total overall currentcy available in this epoch.

2. Calculate the allocated currentcy as the smaller of its entitled currentcy and the amount required to reach its cap: .

   is the leftover currentcy in the container at the beginning of the epoch and is the maximum amount of new currentcy can be added to the container.

3. Calculate the available currentcy for the rest of containers, gathering excess currentcy from the containers at the top of the sorted list: .

The overall consumption should more closely match the overall allocation with this redistribution (at the risk of upsetting proportionality, considered in Section 5), thus reducing the residual energy. We refer to this algorithm as the Currentcy Conserving (CC) allocation policy.