{'fraction_non_alphanumeric': 0.05890303763249626, 'fraction_numerical': 0.012093618837589812, 'mean_word_length': 3.8325885183911996, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Achieving the Age-Energy Tradeoff with a Finite-Battery Energy Harvesting Source

We study the problem of minimizing the time-average expected Age of Information for status updates sent by an energy-harvesting source with a finite-capacity battery. In prior literature, optimal policies were observed to have a threshold structure under Poisson energy arrivals, for the special case of a unit-capacity battery. In this paper, we generalize this result to any (integer) battery capacity, and explicitly characterize the threshold structure. We obtain tools to derive the optimal policy for arbitrary energy buffer (i.e. battery) size. One of these results is the unexpected equivalence of the minimum average AoI and the optimal threshold for the highest energy state.


I. INTRODUCTION
The Age of Information (AoI) was proposed in [1], [2] as a performance metric that measures the freshness of information in status-update systems. For a flow of information updates sent from a source to a destination, status age is defined as the time elapsed since the newest update available was generated at the source. That is, if u(t) is the largest among the timestamps of all packets received by time t, status age is defined as: The Age of Information (AoI) usually refers to the timeaverage of ∆(t). AoI is a particularly relevant performance metric for status-update applications that have growing importance in social networks, remote monitoring [3], [4], machinetype communication (smart cities, industrial manufacturing, telerobotics, IoT). AoI was analyzed under various queueing system models, service disciplines and queue management policies in recent literature (e.g., [5]- [12]. The control and optimization of AoI for an active source that can generate updates at will, was studied in [13], [14].
The relation of energy and AoI was studied as early as 2015: The problem of AoI-optimal generation of status updates when the source is constrained by an arbitrary sequence of energy arrivals was formulated in [15], resulting in the optimal offline solution and an online policy. The study in [16] considered the optimization of AoI under a long-term average rate of energy harvesting, when update transmissions are subject to random delays in the network. Both studies observed that AoI-optimal policies tend to be lazy, in the sense that they may intentionally impose a waiting time before sending the next update. That is, for maximum freshness, one may sometimes send updates at a rate lower than one is allowed to-which may be counterintuitive at first sight.
The online problem in [15] was extended to a continuoustime formulation with Poisson energy arrivals, finite energy storage (battery) capacity, and random packet errors in the channel in [17]. An age-optimal threshold policy was proposed for the unit battery case, and the achievable AoI for arbitrary battery size was bounded for a channel with a constant error packet error probability. Optimal threshold policies for the unit battery and infinite battery capacity cases were found for a channel with no errors, in the concurrent study in [18]. The problem of characterizing optimal policies for arbitrary battery sizes remained open.
In [19], the offline results in [17] were extended considering fixed non-zero service time and the result is used to obtain a solution for the two-hop scenario. Another offline problem under energy harvesting was investigated in [20] where the transmission delay of an update is controlled by energy consumed on its transmission. This paper extends [17], making the following contributions: • A more general description of the policy space for ageoptimal scheduling, including threshold policies with agebased thresholds that are monotone in energy state, is formulated. • Following the study in [17], it was conjectured that for any battery size, the optimal threshold on the age for the highest energy state is actually equal to the minimum AoI. This conjecture is proved to be correct. • Optimal thresholds are obtained numerically for integer battery size up to 5.

II. SYSTEM MODEL
Consider an energy harvesting transmitter that sends update packets to a destination, as illustrated in Fig 1. Suppose that the transmitter has a finite battery which is capable of storing up to B units of energy. Transmission of each update packet consumes a unit of energy. Let E(t) denote the amount of energy stored in the battery at time t. The timing of status updates are controlled by a sampler which can monitor the battery level E(t) at all time t. We assume that when an update is given to the transmitter, it is instantaneously transmitted 1 .
Let N H (t) and N U (t) denote the number of energy units that have arrived and the number of updates that have sent out by time t, respectively. We assume that the energy arrival process is Poisson with a rate µ H . Energy arriving while the battery is full is lost (cannot be stored or used).
The system starts to operate at time t = 0. Let Z k denote the generation time of the k-th update packet such that 0 = Z 0 ≤ Z 1 ≤ Z 2 ≤ . . .. An update policy is defined by a sequence of update instants π = (Z 0 , Z 1 , Z 2 , ...). In many status-update systems (e.g., a sensor reporting temperature []), the update packets are only sent out sporadically and the packet size is quite small. Hence, the duration for transmitting a packet is much smaller than the difference between two subsequent update times. Motivated by this, we assume that the packet transmission time can be approximated as zero. With this assumption, the age at a status generation is zero, i.e. ∆(Z k ) = 0 for any k, and the age at any time t is: The battery level before the (k+1)-st update instant is given by the following: We first define the set of energy-causal update policies: A policy π is said to be energy-causal if no update packet is sent out when the battery is empty, i.e., The information available up to some time t is represented by which is the σfield generated by the sequence of energy arrivals and updates, i.e., {(N H (t ′ ), N U (t ′ )), 0 ≤ t ′ < t}. The set of online update policies is defined as follows: Definition 2. An energy-causal policy is said to be online if no update instant is determined based on future information, The goal of this paper is to find the optimal update policy for minimizing the time-average expected age, which is formulated as: min π∈Π∆ .

III. MAIN RESULTS
We begin with a result guaranteeing the existence of threshold-type policies that are optimal. We define such policies as follows: Definition 3. An online policy is said to be a threshold policy if: where τ ℓ denotes the threshold for sending an update when the battery level is ℓ for ℓ = 1, . . . , B.
Let Π T ⊂ Π be the set of threshold policies. First, we note the following: Theorem 1. There exists a threshold policy π ∈ Π T that solves (6).
In our search for an optimal policy, we can reduce the space of policies further, Let Π MT be the set of monotone threshold policies. The following is true: There exists a monotone threshold policy π ∈ Π MT that solves (6).
Theorem 2 implies that in the optimal update policy, update packets are sent out more frequently when the battery level is high.
To understand the time evolution of ∆(t) and E(t) for policies in Π MT , consider the illustration in Fig. 2. It can be seen from Fig. 2 that when Z + k = j, the next update of a policy π ∈ Π MT occurs before than some time t ′ ∈ [Z k + τ m , Z k + τ m−1 ] if and only if there occur m − j energy arrivals before than t ′ . Accordingly, for policies in Π MT , the cumulative distribution function (CDF) of inter-update can be expressed as: Hence, energy states sampled at update instants can be described as a DTMC with the transition probabilities in (9). When thresholds are finite, this DTMC is ergodic as any energy state is reachable from any other energy state with positive probability in B − 1 steps.
Next, we show the main structural result satisfied by the thresholds of any optimal policy in Π MT . Theorem 3. An optimal policy for solving (6) is a monotone threshold policy π * = (τ * 1 , . . . , τ * B ) that satisfies the following property: The threshold τ * B for sending an update packet when the battery is full is equal to the minimum time-average expected age, i.e., This follows from the following two results: is the CDF of a non-negative random variable for every i ∈ {1, ..., B}, then: Corollary 1. The inter-update intervals, X, for any π ∈ Π MT satisfy the following: Note that the transition probabilities (9) do not depend on τ B hence the steady-state probabilities obtained from (9) also do not depend on τ B . This leads to a property of τ B which is shown in Theorem 3. The unit-battery case , i.e., B = 1 case was solved in [18] and [17], hence we skip the case B = 1 and continue with the case B = 2 where we can show the result below: Theorem 4. When B = 2, the average age∆ can be expressed where

IV. NUMERICAL RESULTS
For battery sizes B = 1, 2, 3, 4, 5, the policies in Π MT are numerically optimized giving AoI versus energy arrival rate (Poisson) curves in  PSfrag replacements∆

V. CONCLUSION
This paper explored the age-energy tradeoff for status updates sent by a finite-battery source that is charged intermittently by Poisson energy arrivals. The objective was to design a policy for the source to send updates to minimizing average status age using the given energy harvests, known and used in an online manner. A threshold policy is one that transmits when age exceeds a particular threshold for any battery state. It is shown that there is an online energy-causal threshold policy with monotone thresholds that optimally solves the problem.
In particular, the smallest of the thresholds, the one used when the battery is full, has a value that matches the optimal average age.

A. The Proof of Theorem 1
Consider the problem in below for some h < ∞: In order to solve (13), let us define a cost function J h;w,Fw for some time w ≥ z which is defined as: This represents the minimum cumulative age in [w, w + h] that is achievable by online policies given F w . In fact, Proof. This is due to the following facts that , for any Z k+1 ≥ w, (1) given ∆(w) the cumulative age in [w, Z k+1 + h], i.e. Hence, we can use the notation J * h (a, ℓ) := J * h;w,Fw where a = ∆(w + ) and ℓ = E(w + ). Now, considering the case Z k+1 = w, define the following function: Notice that ∆(w + ) = 0 as w = Z k+1 , accordingly, by Lemma 2, J h is only a function of E(w + ), i.e., J h = J h (ℓ) where ℓ = E(w + ). Notice also, for any Z k+1 of a policy π ∈ Π and the equality is achieved for the policies that solve (13).
Accordingly, Z k+1 of the policy solving (13) is the optimal stopping time of the following stopping problem for a given z, h and F z : where M z is the family of stopping times such that M z = {w ≥ z : {w ≤ t} ∈ F t , ∀t ≥ z} and G = (G t ) t≥z is a stochastic process having the following definition: or alternatively, where J h (−1) := ∞.
If exists, the optimal stopping time w * for (17) is given by the following stopping rule [21, Theorem 2.2.]: where S is the Snell envelope [21] for G: Notice that the Snell envelope can be written by substituting (18) in (21) as follows: hence, Accordingly, using the definition of J * h (a, ℓ), we can write: Therefore, the optimal stopping rule in (20) is equivalent to: , E(w))}, (25) Next, we show that the stopping rule in (25) is a threshold rule in age. In order to show this, let us define the function ρ h (·) : {−1, 0, 1, ..., B} → [0, ∞) such that: h (a ′ , ℓ) for some a ′ ≥ ρ h (ℓ) which is larger than or equal to J * h (a, ℓ) as J * h (a, ℓ) is non-decreasing in a. On the other hand, J * h (a ′ , ℓ) is smaller than or equal to J h (ℓ − 1) for any a ≥ 0 as: where the inequality is true as the expectation is conditioned on policies with Z k+1 = w.
We showed that the stopping rule in (26) gives the optimal stopping time w * which equals to Z k+1 of a policy solving (13) for any finite h. Now, we show that the optimal stopping rule with the same structure also gives a solution to (6).

First, consider:
Lemma 3. The function ρ h (ℓ) is uniformly bounded such that: We will show that this lemma implies Pr(X k ≥ x) ∈ O(e −µH x ) when Z k+1 = w * . This follows from the fact that, when Z k+1 = w * , X k ≥ ρ max + x d for some x d > 0 is possible if and only if, for some time t, E(t) = 0 and ∆(t) = ρ max + x d , which occurs when there is no energy arrival during ρ max + x d units of time. This also shows that Pr(Z k+1 < ∞ | Z k = z) = 1.
The term for the condition Z k+1 ≥ h α vanishes as h → ∞, in order to see this consider: For Z k+1 = w * , the upper bound goes to zero when h → ∞ as Pr( As the inequality is true for any α ∈ (0, 1): (ii) For the case (≥), it can be seen that: Therefore, (28) is true and by (28) and (26), a solution to the following problem, satisfies: where ρ(ℓ) := lim h→∞ ρ h (ℓ).

D. The Proof of Lemma 6
Consider an energy state j in [0, B − 1]. We will show that any other energy state i is reachable from j in at most B − 1 steps with a positive probability. For i ≥ j, the higher energy state i is reachable from j in one step with a positive probability as for i = B − 1, Pr(Y B−j ≤ τ B−1 ) is strictly positive and for j ≤ i < B − 1: Similarly, the energy state i = j − 1 for j = 1, ...., B − 1 can be reached from j with a probability 1 − Pr(Y 1 ≤ τ j ) which is stricly positive as τ j is finite. This means that any state i < j can be reached from j in at most B − 1 steps with a positive probability. where Pr(E = j) is the steady-state probability for energy Proof. Consider: where L j is the number of ks in [0, n] such that E(Z k ) = j and X ℓ;j is a r.v. with the CDF Pr(X ℓ;j ≤ x) = Pr(X ℓ ≤ x | E(Z ℓ ) = j).
Proof. The proof is a generalization of Theorem 5.4.5 in [22] for the case where X k s are non-i.i.d. but the limits still exist (w.p.1.). When X k s are i.i.d. with E[X k ] < ∞ and E[X 2 k ] < ∞, the convergence (w.p.1.) of the limits is guaranteed.