key: cord-0581207-nrndh1j4
authors: Saurav, Kumar; Vaze, Rahul
title: Online Energy Minimization Under A Peak Age of Information Constraint
date: 2021-03-30
journal: nan
DOI: nan
sha: 686c9fa3a3f50b7a656c4ada8e82bf15913a4d6d
doc_id: 581207
cord_uid: nrndh1j4

We consider a node where packets of fixed size are generated at arbitrary intervals. The node is required to maintain the peak age of information (AoI) at the monitor below a threshold by transmitting potentially a subset of the generated packets. At any time, depending on packet availability and current AoI, the node can choose the packet to transmit, and its transmission speed. We consider a power function (rate of energy consumption) that is increasing and convex in transmission speed, and the objective is to minimize the energy consumption under the peak AoI constraint at all times. For this problem, we propose a (customized) greedy policy, and analyze its competitive ratio (CR) by comparing it against an optimal offline policy by deriving some structural results. We show that for polynomial power functions, the CR upper bound for the greedy policy is independent of the system parameters, such as the peak AoI, packet size, time horizon, or the number of packets generated. Also, we derive a lower bound on the competitive ratio of any causal policy, and show that for exponential power functions (e.g., Shannon rate function), the competitive ratio of any causal policy grows exponentially with increase in the ratio of packet size to peak AoI.

In the times of COVID-19 pandemic, real-time networked applications such as autonomous vehicles, immersive gaming, telemedicine and telesurgery played a vital role in enabling people to maintain social-distancing while minimizing the loss in lives and productivity [1] . However, such applications need to maintain data-freshness at the nodes, which requires minimizing the age of latest data-packet (formally called the age of information (AoI) [2] ) at the nodes.

In practice, AoI minimization is a complicated task. Factors such as limited energy, unavailability of fresh data-packets, etc., often restrict the control options for minimizing AoI. For example, to maximize the operational life, devices with limited energy need to restrict the number of data-packets that they transmit, as well as their transmission rate (speed), thus leading to large AoI. Hence, there is an inherent AoI-energy tradeoff that any transmission policy must consider.

In prior work, AoI-energy tradeoff has been considered primarily for (i) energy harvesting model, and (ii) energy con-We acknowledge support of the Department of Atomic Energy, Government of India, under project no. RTI4001. servation model. In energy harvesting model, energy arrives at nodes intermittently, and at any time, depending on the energy level, the expected future energy arrivals, and packet availability, nodes need to make transmission decisions to minimize the AoI [3] - [6] . In the energy conservation model, there is no limit on the energy that a policy may consume, and the AoI-energy tradeoff is formulated as an optimization problem that seeks to minimize either (i) AoI (energy consumption) subject to energy (AoI) constraint [7] , [8] , or (ii) a linear combination of AoI and energy consumption [9] - [12] .

In this paper, we consider an energy conservation model, and the objective is to minimize the energy consumption subject to a peak AoI constraint, at all times over a fixed horizon of time. Essentially, we consider a node where data-packets (in short, packets) of fixed size (say, W bits) are generated at arbitrary time instants, with bounded inter-generation time, and the node requires that by transmitting these packets, the peak AoI at the monitor is maintained below a threshold at all times, while consuming minimum energy. Thus, for every generated packet, the node needs to decide whether to transmit it or not. If the node chooses to transmit a packet, the AoI drops at the instant the node finishes transmitting the entire W bits of the packet.

For the considered problem, at any time, if a new packet is generated, the node may discard (or, preempt) a packet already being transmitted, and switch to transmitting the new packet, thus seeking larger reduction in instantaneous AoI at the monitor, at the cost of wasting energy already consumed for partially transmitting the preempted packet. Note that the peak AoI constraint only requires that at any time t, the generation time of the latest packet that has been entirely transmitted (all W bits) by the node (until time t) is less than the peak AoI constraint. Moreover, once the node transmits a newly generated packet, it (node) does not need to transmit any old packet that it has not transmitted completely.

Additionally, we consider a tuneable/variable speed model (henceforth, called the speed scaling model), where at each time, the node can choose its transmission speed (in bits/sec) and correspondingly pay a price in terms of power/energy consumption. A large transmission speed reduces the AoI, however, at the cost of increased power consumption. We assume that the power consumed when transmitting at speed s is P (s) that is convex and increasing. Two popular examples are P (s) = s α and P (s) = 2 s − 1. Thus, there are two decisions to make at each time, whether to transmit an available packet, and at what speed.

In past, in the context of AoI, the speed scaling model has been considered in [4] , [13] . In particular, in [13] , a node controls the number of bits of packet delivered to the monitor in a fixed time slot by controlling transmission power. However, it cannot transmit a single packet over multiple time slots. Therefore, to decrease the AoI, a node should deliver a certain number of bits in a single time slot. In [4] , a node can control the transmission delay of packets by controlling the transmission power at the instant the packets are transmitted. However, [4] assumes all the packet generation times to be known in advance, which greatly simplifies the problem. The speed scaling model has also been considered in context of AoI-distortion tradeoff [9] , [14] , [15] , where a node controls the number of bits it transmits for each packet. Transmitting fewer bits take less time, and is assumed sufficient for minimizing AoI, but this results in distorted information at the monitor, where the level of distortion increases with decrease (increase) in the number of bits transmitted (transmission time).

The closest work to the considered problem in this paper, is on job scheduling with the speed scaling model [16] , [17] . In this model, jobs arrive at a server sequentially, and the server needs to process all the arriving jobs (with adaptive speed) before their corresponding deadlines, while consuming minimum energy. Note that the job scheduling problem allows policies to be preemptive, however, all jobs have to be completed by their deadlines. When power function is P (s) = s α (α > 1), [16] proposed a causal preemptive policy for which the competitive ratio (i.e., the ratio of the energy consumed by the causal policy to the energy consumed by an optimal offline policy, maximized over all inputs) is at most α α [17] . In the special case when the power function is P (s) = 2 s − 1, and all the packets are of equal size, with a common deadline, [18] , [19] gave a 3-competitive policy for the job scheduling problem.

The problem considered in [16] , [17] differs from what we consider in this paper in one key aspect. In [16] , [17] every job that arrives at the server needs to be processed completely, while in the considered problem, there is only a peak AoI constraint which could be satisfied by transmitting only a subset of the generated packets. Since the objective is to minimize total energy, subject to peak AoI constraint, an additional challenge compared to [16] , [17] (where only speed and the order of processing is to be decided) is to identify the subset of packets to transmit.

In this paper, we consider a very general setting, where the time horizon is finite, the packet generation times are arbitrary, and there is a peak AoI constraint. To put this into perspective, we briefly discuss them below. a) Finite Time Horizon: Most of the prior work pertaining to the AoI minimization problem considers infinite time horizon [2] , [3] , [9] , [11] . Infinite time horizon assumption makes it possible to utilize stochastic properties of the problem, such as distribution over the packet inter-generation times/energy arrival instants, etc. This also makes it possible to ignore the edge effects (such as initial AoI, cost/energy incurred at times close to 0 or time horizon T , etc.). However, in this paper, we consider finite time horizon (such as in [20] ), and fully acknowledge the edge effects.

b) Arbitrary Packet Inter-generation Times: In prior work, packet inter-generation time patterns have been considered for following three models: (i) generate-at-will modela fresh packet is available at the node at all times (e.g., [21] ), (ii) stochastic arrival model -fresh packets are generated with inter-generation time following particular distribution (e.g., [11] ), and (iii) arbitrary arrival model -packet intergeneration times are arbitrary, and hence, need not follow any particular distribution or pattern (e.g., [9] ). Clearly, arbitrary arrival model is the most general one, and may even model adversarial inputs. c) Peak AoI Constraint: Primarily in AoI minimization problems, the actual metric being minimized is either

denotes the number of packets successful transmitted by the the node until time horizon T , while ∆ p (i) denotes the AoI just before the completion of i th transmission) [22] , [23] . However, in practice these metrics (that consider only average values), may not be sufficient for critical applications such as telesurgery, driverless car, etc. For such applications, peak AoI constraint is a more suitable choice as it guarantees that at any time the instantaneous AoI is below a given threshold.

The main contributions of this paper are as follows. 1) When all the generated packets are of same size (W bits), we derive a lower bound on the competitive ratio of any causal policy π that seeks to minimize energy consumption while satisfying a peak AoI constraint. We show that for convex power functions P (s(t)) (where s(t) denotes the transmission speed at time t), the competitive ratio of any causal policy π is CR π ≥ c 1 P (c 2ŝ )/P (c 3ŝ ), whereŝ denotes the ratio of packet size W to the maximum allowed peak AoI D, and c 1 , c 2 and c 3 are finite positive constants such that c 2 − c 3 ≥ 0.14 and c 2 /c 3 ≥ 1.07. Thus for any causal policy π, (i) if P (s) = 2 s − 1, the competitive ratio CR π ≥ c 1 2 0.14ŝ increases exponentially with increase in s, while (ii) if P (s) = s α (α > 1), the competitive ratio CR π ≥ c 1 1.07 α increases exponentially with increase in α. 2) We propose a simple non-preemptive causal greedy policy π g , and show that for convex power function P (s(t)), when the size of all the generated packets is equal to W bits, the competitive ratio of the proposed greedy policy π g is CR π g ≤ 2P (3ŝ)/P (ŝ) + 1. Consequently, we get that (i) for P (s) = s α (α > 1),

Note that the derived upper bound on CR π g has similar order of dependence on the system parameters as the lower bound discussed in point 1. For a non-preemptive causal greedy policy π g , such a competitive ratio is significant, as it shows that even an optimal causal policy (that can be much more complicated than π g , and may even preempt packets) cannot perform arbitrarily better (consume arbitrarily less energy) than π g . 3) When the generated packets are of arbitrary sizes in the range [w, W ] bits, we show that for ζ = W/w, and s = w/D (where D denotes the maximum allowed peak AoI) the competitive ratio of the proposed greedy policy π g is CR π g ≤ 2P (3ζs)/P (s) + 1. Moreover, if ζ is unbounded, the competitive ratio of any causal policy π is unbounded.

Consider a node where data-packets (in short, packets), each of size W bits are generated intermittently. In particular, the i th packet at the node is generated at time t i , where t i is determined by external factors (possibly adversarial), with inter-generation time X i = t i − t i−1 . A packet i is said to be delivered (at the monitor) at time τ i if the node finishes transmitting the W bits of packet i at time τ i .

At any time t, the age of information (AoI) at the monitor is equal to ∆(t) = t − µ(t), where µ(t) is the generation time of the latest packet that has been delivered to the monitor until time t. Further, in an interval [0, T ], peak AoI at the monitor is defined to be max t∈[0,T ] ∆(t). We consider a peak AoI constraint, i.e., for any given time horizon T , the node requires that the peak AoI at the monitor in the interval [0, T ] is less than D, where D is a known constant.

Remark 1: If inter-generation time X i > D for any i, then the peak AoI constraint is infeasible. Therefore, for the problem to be meaningful, we need the inter-generation time of packets to be bounded, and in particular, less than D. So, we assume that there exists some ǫ > 0 such that ∀i, X i < D − ǫ.

In fact, we also need the initial AoI ∆(0) to be less than D−ǫ.

Remark 2: At any time t, the peak AoI constraint only requires that µ(t), i.e., the generation time of the latest packet delivered to the monitor until time t is less than D time units old. Therefore, to satisfy the peak AoI constraint, it is not necessary to transmit every generated packet. For example, at time t, if packets i and j (with generation times t i and t j respectively) are available at the node (i.e., neither of the packets have been completely transmitted until time t), and t i < t j , then for satisfying the peak AoI constraint, it is sufficient to transmit packet j only, without transmitting packet i. Moreover, after packet j gets delivered to the monitor, transmitting packet i is no longer useful (and hence, need not be transmitted) because the peak AoI will still be determined by t j , i.e., the generation time of the latest packet delivered at the monitor.

Definition 1: A policy that at any time t, can preempt (discard) an undelivered packet (i.e., a packet that is either transmitted partially, or not transmitted at all), and begin transmitting a newly generated packet, is called a preemptive policy. Note that the class of preemptive policies, by definition, includes all non-preemptive policies, that never preempts any packet.

We consider a speed scaling model, where at any time t, the node can transmit a packet at speed s(t) ≥ 0 (in bits/sec) adaptively, i.e., the node can choose s(t) using causal information available at time t. Also, transmitting a packet at speed s(t) consumes power P (s(t)), which is an increasing and convex function of speed s(t), e.g., P (s) = s α (α > 1), or P (s) = 2 s − 1, motivated by Shannon's rate function. Therefore, if the node transmits packets at high speed, it incurs low AoI, but consumes large amount of energy. Hence, finding an optimal transmission speed is a non-trivial task.

Remark 3: Throughout this paper, we assume that when speed s(t) = 0, the power consumption is P (0) = 0. This assumption does not affect the results derived in this paper, but allows us to ignore the terms containing P (0) which merely appear as an offset.

In this paper, we consider the problem of finding a causal policy that chooses the packets to transmit (where preemption is allowed), the time interval over which the packets are transmitted, and their instantaneous transmission speed, so that the peak AoI is maintained below D at all times over a time horizon T , while consuming minimum energy. Formally, the objective can be stated as follows.

where Π is the set of all causal policies 1 for packet scheduling and the choice of speed s(t), and σ = {t 1 , t 2 , ...} is the sequence of packet generation times. Note that the choice of packet a policy transmits at any time t is inherently captured by (1a). Remark 4: In this paper, the set of all causal policies implicitly refer to the set of all preemptive causal policies that may preempt packets (Definition 1).

Definition 2: A policy π ⋆ is said to be offline optimal if it satisfies the peak AoI constraint (1b), and there exists no other policyπ that can simultaneously satisfy the peak AoI constraint (1b), and consume less energy than π ⋆ , even ifπ knows the generation time of all the packets in advance. Optimal offline policies are useful as they provide a lower bound on the energy consumed by any causal policy π.

From prior work [16] , [18] , [19] , it is known that finding an optimal causal policy for energy minimization problems under hard constraints (such as individual/common deadline for packets) is a challenging task. Hence, a usual approach is to find a causal policy π whose competitive ratio, defined as the ratio of the energy consumed by a causal policy π (to satisfy the peak AoI constraint) and the energy consumed by an optimal offline policy π ⋆ (Definition 2), maximized over all possible sequence of packet generation times σ, is small. Mathematically, the competitive ratio of policy π is

By definiton, a policy with small competitive ratio is robust.

In the rest of the paper, we will consider a particular nonpreemptive causal policy, and show that its competitive ratio is at most 2P (3ŝ)/P (ŝ) + 1, whereŝ = W/D. We will also derive a lower bound on the competitive ratio of any causal policy π, and show that for different power function of interest, the competitive ratio of the considered policy has similar characteristics (dependence on parameters) as the derived lower bound. Note that for a non-preemptive causal policy which is much simpler to implement than a general preemptive causal policy [24] , this is a significant result. Definition 3: At any time t, a packet i is defined to be fresh if its generation time t i ≤ t is greater than µ(t), i.e. t i > µ(t). Otherwise, the packet is stale.

The peak AoI constraint (1b) can also be interpreted as a deadline constraint, where a deadline is defined as follows.

Definition 4: At any time t, if µ(t) is the generation time of the latest packet that has been delivered to the monitor until time t, then the deadline at time t is defined as d(t) = µ(t) + D, which is the earliest time instant at which the peak AoI constraint (1b) will be violated if no packet is delivered to the monitor after time t. Equivalently, d(t) = t + (D − ∆(t)).

Remark 5: Note that d(t) = µ(t) + D is a non-decreasing function of t. In fact, deadline d(t) increases in steps whenever a fresh packet j (t j > µ(t); Definition 3) is delivered to the monitor. This happens because µ(t) (i.e., the generation time of the latest packet delivered until time t) increases discontinuously to the generation time t j of packet j, at the instant packet j is delivered to the monitor.

At any time t, since the deadline d(t) = t+(D −∆(t)), and the peak AoI constraint (1b) requires D − ∆(t) > 0, therefore the peak AoI constraint (1b) is equivalent to the following deadline constraint:

In other words, the peak AoI constraint (1b) is equivalent to the constraint that at any time t ∈ [0, T ], the current deadline d(t) must be in future. Hence, hereafter we consider the deadline constraint (3) (instead of peak AoI constraint (1b)) while minimizing the objective function (1a). Also, we define a feasible policy as follows. Definition 5: A policy π is defined to be feasible if it satisfies the deadline constraint (3) at all times t.

Proposition 1: At any time t ∈ [0, T ], if d(t) ≤ T , then for any feasible policy π, at least one fresh packet has to be delivered to the monitor in interval [t, d(t)).

Proof: If the deadline at time t ∈ [0, T ] is d(t) ≤ T , and no fresh packet is delivered to the monitor in interval [t, d(t)), then the deadline constraint (3) will be violated at time d(t) (follows from the definition of deadline; Definition 4). Hence, a feasible policy must deliver at least one fresh packet to the

Remark 6: In order to satisfy the deadline constraint (3), note that only fresh packets are needed/useful. Therefore, if a policy transmits a stale packet, it wastes energy. Hence, in rest of the paper, we only consider packets that are fresh, and at any time, the term 'packet' implicitly means a fresh packet.

Definition 6: For each packet i generated at time t i , we define d i = t i + D.

Convexity of power function implies the following property. Lemma 1: Energy consumed in transmitting w bits in a fixed interval [p, q) is minimum if the bits are transmitted at a constant speed s w (t) = w/(q − p). Also, the minimum energy consumed in interval [p, q) is P (w/(q − p))(q − p).

Proof: See Appendix A. Corollary 1: For fixed w, P (w/y)y decreases with increase in y.

Proof: See Appendix B.

III. LIMITATIONS OF A CAUSAL POLICY π Before we discuss a particular causal policy for minimizing the energy consumption (1a) (under the deadline constraint (3)), it is important to note the fundamental limitations of any causal policy π. Towards that end, Theorem 1 provides a lower bound on the competitive ratio of any causal policy π, and shows (in Corollary 2) that for certain power functions P (·), the competitive ratio of any causal policy π is an increasing function of W/D.

Theorem 1: For any causal policy π, its competitive ratio

where c 1 , c 2 and c 3 are finite positive constants, c 2 −c 3 ≥ 0.14, and c 2 /c 3 ≥ 1.07.

Proof Sketch: To prove Theorem 1, we consider a particular scenario where the AoI at the monitor at time t = 0 is ∆(0) = D/2, the time horizon T = 3D/2−δ (for δ → 0 + ), and the packets are generated according to one of the two instances of packet generation times σ: (i) σ 1 = {0, D/4, D/2}, and (ii) σ 2 = {0, D/4, 5D/6}. Then, for indexing all causal policies, we consider different cases based on the packet(s) that any causal policy may transmit in interval [0, D/2), and for each case, we compute the competitive ratio (2) , where the maximization is with respect to σ ∈ {σ 1 , σ 2 }. Finally, we take the minimum over the competitive ratio obtained for different cases considered above, and obtain (4), where c 1 , c 2 and c 3 are finite positive constants, c 2 − c 3 ≥ 0.14, and c 2 /c 3 ≥ 1.07. For detailed proof, see Appendix C.

Corollary 2: For any causal policy π,

In the next section, we propose a feasible non-preemptive (causal) greedy policy π g , and show that the competitive ratio

. Thus, we show that the dependence of the competitive ratio of π g on the system parameters is similar to the policy-independent lower bound (4) in Theorem 1.

Consider a greedy policy π g (Algorithm 1) that at any time t, if the node is idle (i.e., not transmitting any packet) and the deadline d(t) < T , transmits the latest available (fresh) packet with constant speed s g (t) (5), starting at time t, throughout until the W bits of the packet are delivered to the monitor (and waits otherwise),

Remark 7: Note that the greedy policy π g does not preempt any packet. However, this is not a constraint, and in general, a policy is allowed to preempt packets to solve (1a).

if d(t) ≤ T and node idle and packet available then transmit the latest packet with constant speed s g (t)

Although greedy policy π g appears obvious, the speed s g (t) (5) has been chosen carefully such that (i) π g is feasible (since s g (t) ≥ W/(d(t)−t), if π g begins to transmit a packet at time t, the packet will be delivered to the monitor before deadline d(t)), and (ii) speed s g (t) cannot be arbitrarily large (in fact, s g (t) cannot be greater than 3W/D), unless a particular event happens (defined in Proposition 2) with regard to the packet generation time and for which we can lower bound the energy consumed by the optimal offline policy π ⋆ (Lemma 4 in Appendix F).

Proposition 2: If π g begins to transmit a packet j at time t, then the speed s g (t) > 3W/D only if no packet was generated in interval [t − 2D/3, t).

Proof: Consider time t, when π g begins to transmit a packet j with speed s g (t) > 3W/D. To prove Proposition 2, we need to show that no packet must have been generated in interval [t − 2W/D, t). For this, let at least one packet be generated in the interval [t − 2D/3, t). Then we must have one of the following two cases:

a) There exists a packet i = j generated in interval [t − 2D/3, t) that π g begins to transmit at time r i < t: Recall that π g is a non-preemptive policy (Remark 7). Hence, π g must have delivered packet i (to the monitor) until time t. Also, by hypothesis, π g begins to transmit packet j at time t with speed s g (t) > 3W/D. Thus, from (5), it follows that d(t)−t < D/3. This implies that d(t) < t + D/3, which is possible only if no packet (including packet i) that was generated in interval [t − 2D/3, t) was delivered to the monitor until time t. This contradicts the fact that packet i was generated in interval [t−2D/3, t), and delivered until time t. Hence, there cannot be a packet generated in

is transmitted by π g starting at any timet < t: Since π g never idles if a fresh packet is available, this case is possible only if π g remains busy in the entire interval [t − 2D/3, t), transmitting packets that were generated before time t − 2D/3. However, such an event cannot happen. To show this, let packet i be the latest packet generated before time t − 2D/3 (say, at time t i = t − 2D/3 − δ, where δ > 0). Because π g only transmits a fresh packet, in interval [t − 2D/3, t), π g may transmit at most two packets generated before t − 2D/3 -(i) a packetî that was being transmitted by π g when packet i was generated at time t i , and (ii) packet i itself. Since π g transmits a packet with speed at least 3W/D (Eq.(5)), it takes at most D/3 time units to completely transmit (deliver) a packet. Therefore, π g would finish transmitting both packetî and packet i before t i + 2D/3 = t − δ, and hence, must begin to transmit a packet generated in

thus proving that this case is not possible.

Thus, we conclude that none of the above two cases are possible. This contradicts the assumption that a packet was generated in interval [t − 2D/3, t).

Corollary 3: If π g transmits a packet j with speed greater than 3W/D, then it must have begun to transmit packet j immediately after it was generated at time t j , and completed the transmission at time d(t j ).

Proof: See Appendix D. We next provide some intuition for the choice of speed s g (t) (5) used by the greedy policy π g , that is at least equal to 3W/D. For a greedy policy such as Algorithm 1, it is critical to have s g (t) ≥ 3W/D, because as shown in Example 1 below, a smaller value of speed such as 2W/D may require π g to transmit some packets at much higher speed (compared to an optimal offline policy π ⋆ ), thus consuming large amount of energy (compared to the offline optimal policy π ⋆ ).

Example 1: Let at t = 0, ∆(0) = 0, D = 2, and T = 3 + δ/2, where δ → 0 + . Also, let three packets be generated at time t = 0, t = δ, and t = 1 + δ, respectively. Then, an optimal offline policy π ⋆ will only transmit the third packet, with constant speed W/(1 − δ) for (1 − δ) time units, whereas the greedy policy π g (Algorithm 1) with speed s g (t) = max{W/(d(t) − t), 3W/D} will transmit all three packets with constant speed 3W/D (each for D/3 time units).

However, if the speed choice s g (t) (5) for π g is replaced withŝ g (t) = max{W/(d(t) − t), 2W/D} (where t is the time when transmission of packet begins), then π g will still transmit all three packets, but the third packet will be transmitted with a constant speed W/δ → ∞.

A. Competitive Ratio of the Greedy Policy π g Theorem 2: Letŝ = W/D. Then, the competitive ratio (CR π g ) of greedy policy π g is bounded as follows.

Remark 8: Recall Theorem 1 that states that for any causal policy π, CR π ≥ c 1 P (c 2ŝ )/P (c 3ŝ ), where c 1 , c 2 , c 3 > 0, and c 2 − c 3 ≥ 0.14, and c 2 /c 3 ≥ 1.07. Theorem 2 shows that the dependence of CR π g on the system parameters is similar to the lower bound on CR π in Theorem 1. So, for any (convex) P (s) andŝ (i.e., W/D), if there exists a causal policy π with bounded competitive ratio CR π , then CR π g is also bounded.

Remark 9: In (6), if P (s) = s α (α > 1), CR π g ≤ 2 · 3 α + 1, while if P (s) = 2 s −1, CR π g ≤ 2(2 3W/D −1)/(2 W/D −1)+1.

To prove Theorem 2, we need some structural results for an optimal offline policy π ⋆ , which we derive as follows.

Consider an optimal offline policy π ⋆ . In this section, for simplicity, we only consider the packets that are transmitted by π ⋆ in interval [0, T ], and index them as 1, 2, 3, ... in ascending order of their generation times (i.e., t 1 < t 2 < t 3 < ...). Therefore, between the generation time of packets i − 1 and i, many other packets might have been generated, however, they are not transmitted by π ⋆ .

Lemma 2: If π ⋆ chooses to transmit packet i, and

, π ⋆ transmits at least two packets completely (i.e., 2W bits).

Proof: Note that if π ⋆ delivers packet i at τ i , then the deadline at τ i is d(

π ⋆ transmits at least two complete packets i and i + 1 (i.e., 2W bits), as shown in Figure 2 (a) (for i = 2). Thus, Lemma 2 implies that for π ⋆ , the intervals [t i , d i ) are special, and hence, we call them periods, defined rigorously next.

Definition 7: With respect to π ⋆ , the interval

(a) Typical speed profile in a period. Here, a packet generated at ti is scheduled for transmission at ri, and delivered to the monitor at τi.

Time-axis as union of disjoint intervals (frames). By definition, a period starts at the generation time of a packet transmitted packet by π ⋆ , and in each period i, π ⋆ transmits at least two packets (from Lemma 2). Thus, consecutive periods overlap as shown in Figure 2 (b). Hence, it is difficult to generalize Lemma 2 directly to the whole interval [0, T ]. Therefore, we further define frames (that are non-overlapping) with respect to π ⋆ as follows.

Remark 10: As shown in Figure 2 (b), consecutive frames partition the time-axis between [0, T ] (assuming the first frame I 0 starts at time t = 0). Therefore, ∀i = j, I i ∩ I j = φ, and there exists consecutive frames 0, 1, ..., m, such that T lies in frame m, and [0, T ] ⊆ ∪ m i=1 I i . So, the properties of π ⋆ in a frame can be easily generalized to the entire interval [0, T ].

In Definition 7 and Definition 8, note that periods and frames are defined with respect to the packets transmitted by an optimal offline policy π ⋆ . Also, note that frame i

Hence, length of a frame is always less than d i − t i = D. Figure 2(a) shows a typical relation between periods and frames, where at time t 2 , the deadline is d 0 , and packet 1 is delivered to the monitor at time τ 1 < d 0 . Thus the deadline is updated at time τ 1 to d 1 . Then, the interval

is called frame 1. Similarly, within interval I 1 , packet 2 (with generation time t 2 ) is delivered to the monitor at time τ 2 < d 1 . Therefore, at time τ 2 , the deadline gets updated to d 2 , and the interval I 2 = [d 1 , d 2 ) is called frame 2.

Remark 11: Although Figure 2 (a) shows typical properties of frames and periods defined with respect to the packets transmitted by π ⋆ , the speed profile shown in Figure 2(a) is not necessarily the speed chosen by π ⋆ , since that (π ⋆ ) is unknown. We show in Proposition 3 that within a frame, speed of π ⋆ exhibits several structural properties.

The optimal offline policy π ⋆ 1) transmits the W bits of a packet with constant speed, 2) never preempts a packet, 3) delivers packet i + 1 in frame i (∀i), and 4) never decreases the transmission speed within a frame.

Proof: See Appendix E. Remark 12: The third property in Proposition 3 follows due to optimality of π ⋆ , and not from definition of frames. To understand this, note that frame i depends only on packet i−1 and i transmitted by π ⋆ , and does not restrict packet i+2 from being transmitted in frame i, in addition to packet i + 1.

We prove Theorem 2 in two steps. In step 1, we show that CR π g ≤ 2P (3ŝ)/P (ŝ) + 1, while in step 2, we show that 1.5P (3ŝ)/P (1.5ŝ) ≤ CR π g .

Step 1: Upper Bound on CR π g Consider an arbitrary sequence of packet generation times σ. From Remark 10, we know that the time axis can be partitioned into frames defined with respect to π ⋆ (Definition 8). Therefore, consider the consecutive frames 0, 1, ..., m such that the total time horizon interval [0, T ] is a subset of the union of frames 0 to m, and time horizon T lies in frame m (as shown in Figure 2 (b) for m = 5). Note that if m = 0 (i.e., T is less than the initial deadline d(0)), then neither π g , nor π ⋆ transmits any packet because the deadline constraint (3) is trivially satisfied in the interval [0, T ]. Hence, we only consider the case of m ≥ 1.

Since length of a frame is always less than D (the length of a period that is equal to the peak AoI constraint), the time horizon T < (m + 1)D. Therefore, in interval [0, T ], if π g transmits x g ≥ 0 number of packets with speed 3W/D consuming E g x units of energy, then E g x < P (3W/D)(m+1)D (product of power consumption and upper bound on the length of time interval [0, T ]). So, if y g ≥ 0 denotes the number of packets that π g transmits with speed greater than 3W/D (recall that π g transmits an entire packet at a constant speed), and E g y denotes the total energy consumed by π g in transmitting these y g packets, then the total energy consumed by π g in interval [0, T ] is 2

Remark 13: Since π g transmits each of the y g packets at a constant speed greater than 3W/D, the energy consumed by π g in transmitting the y g number of packets is E g y > y g P (3W/D)D/3.

From Proposition 3 (Property 3), it follows that π ⋆ delivers exactly one packet in each frame i = 0, 1, 2, ..., m − 1. Thus, π ⋆ transmits m packets in interval [0, T ]. 3 Also, the length of each frame is less than D (length of a period). Hence, the energy consumed by π ⋆ in transmitting each of these m packets is at least P (W/D)D. Next, we show in Lemma 3 that there exists a subset Z of y g number of packets such that π ⋆ consumes at least E g y units of energy in transmitting the packets in Z.

Lemma 3: There exists a subset of packets Z with cardinality y g , such that π ⋆ transmits all the packets in Z, and consumes at least E g y units of energy in transmitting the packets in Z.

Proof: Note that for y g = 0, the claim is trivially satisfied. So, for the rest of the proof, we assume y g ≥ 1. Recall that π g transmits y g number of packets at speed greater than 3W/D, consuming E g y units of energy. Without loss of generality, let the packets be indexed as 1, 2, ..., y g . Also, let π g transmits a packet j ∈ {1, 2, ..., y g } over the time interval U j , and consumes energy e j (in transmitting packet j). Since π g transmits only one packet at a time, U i ∩ U j = φ for i = j. Therefore, to prove Lemma 3, it is sufficient to show that in interval U j (for j ∈ {1, 2, ..., y g }), π ⋆ transmits at least one packet completely (entire W bits), consuming at least e j units of energy. This follows from Lemma 4 (in Appendix F), where we show that for each packet j that π g transmits with speed greater than 3W/D, π ⋆ transmits at least one packetĵ (where packet j andĵ may be same) completely during the time interval when π g transmits packet j, at a constant speed at least equal to the constant speed with which π g transmits packet j.

Remark 14: π ⋆ transmits a total of m packets in interval [0, T ] (exactly one packet in each of the frames 0, 1, 2, ..., m− 1). Also, from Lemma 3, it follows that π ⋆ transmits at least y g number of packets. Therefore, y g ≤ m.

Hence, the total energy consumed by π ⋆ in interval [0, T ] is

Hence, from (7) and (8), we obtain an upper bound on the competitive ratio (2) for π g as follows. 

where in (a), we have used the fact that E g y > y g P (3W/D)D/3 (Remark 13), (b) follows because P (3W/D)D/3 ≥ P (W/D)D (transmitting W bits at speed 3W/D consumes more energy than transmitting W bits at speed W/D), and we get (c) by maximizing the R.H.S. of (9) with respect to m ≥ 1. Withŝ = W/D, we get the result.

Step 2: Lower Bound on CR π g Let δ → 0 + , and for a fixed D, consider the following problem instance, where T = 4D/3 + δ/2, initial AoI ∆(0) = 0, and three packets are generated at time t = 0, t = D/3 and t = D/3+δ, respectively. Optimal offline policy π ⋆ transmits only the third packet, with speed W/(2D/3 − δ) over the interval [D/3 + δ, D). On the other hand, π g transmits all three packets with speed 3W/D, over the intervals [0, D/3), [D/3, 2D/3) and [2D/3, D), respectively. Therefore, CR π g ≥ 3P (3W/D)(D/3)/(P (W/(2D/3−δ))(2D/3− δ)) → 1.5P (3ŝ)/P (1.5ŝ), whereŝ = W/D.

In Section II, we assumed that each packet generated at the node is of size W bits, where W is a constant. However, this need not be true in practice. So, if the system model considered in Section II is relaxed to allow packets of arbitrary sizes, then we have the following results.

Theorem 3: Among all the packets generated in the interval [0, T ], let the size of the smallest packet be w bits, and the size of the largest packet be W bits.

1) The competitive ratio of the greedy policy π g (Algorithm 1) is CR π g ≤ 2P (3ζw/D)/P (w/D) + 1, where ζ = W/w. 2) When W/w → ∞, the competitive ratio of any causal policy will be unbounded.

Proof: See Appendix G. The second result of Theorem 3 implies that if the packet sizes can vary arbitrarily, then the competitive ratio of any causal policy is unbounded. This is primarily because unlike causal policies, an optimal offline policy π ⋆ knows the generation time of all the packets in advance, and hence, can avoid transmitting large size packets, while satisfying the peak AoI constraint (1b).

If in addition to packets having arbitrary sizes, it is required that each generated packet has to be transmitted, then the offline optimal policy π ⋆ no longer has this advantage (i.e., π ⋆ cannot avoid transmitting large sized packets). In fact, if the packets are required to be transmitted on First-Come-First-Serve (FCFS) basis 4 , then a causal transmission policy with bounded competitive ratio can be obtained for particular power functions P (s) as follows.

Theorem 4: In the optimization problem (1a) with deadline constraint (3) and arbitrary packet sizes, if an additional FCFS constraint is imposed and all packets have to be delivered to the monitor, then for power function P (s) = s α (α > 1), the competitive ratio of Algorithm 2 has competitive ratio at most α α .

Proof: To prove Theorem 4, we model the optimization problem (1a) with deadline constraint (3) and FCFS constraint, as an equivalent job scheduling problem, and use the existing results [17] for job scheduling problems to conclude the proof.

When all the packets generated in interval [0, T ] are to be transmitted on FCFS basis, at the instant the node begins to transmit a packet i (generated at time t i < T ), the latest packet delivered to the monitor is packet i − 1. Hence, the deadline for packet i is always d i−1 = t i−1 + D. So, each packet i can be considered as a job that needs to be processed before the deadline d i−1 , such that the overall energy consumption is minimized.

This equivalent job scheduling problem is a special case of the problem considered in [16] , and when the power function is P (s) = s α (α > 1), [17] showed that for the problem in [16] , Algorithm 2 has competitive ratio at most α α (irrespective of packet sizes).

At any time t, transmit the available (undelivered) packet with earliest deadline, at speed

where t i ≤ t denotes the generation time of packet i that has not been delivered until time t, while w(t, t i + D) is the total number of bits of packets available at the node at time t, with deadline at most t i + D.

Remark 15: Essentially, at any time t, Algorithm 2 assumes that no packet will be generated in the future, and transmits the available packets with speed such that the the deadline constraint (3) for the available packets are satisfied, while consuming minimum energy. Figure 3 shows the AoI plot for π g when size of packets is W = 1 Mbit, peak AoI is D = 3 msec, and inter-generation time X of packets follow uniform distribution with values in interval (0, 2.5). 5 Also, the stem plot in Figure 3 shows the generation time of packets, and the speed with which they were transmitted by π g . The transmission speed of a packet is 0 if it is not transmitted, otherwise the speed is at least 3W/D = 1 Gbit/sec. Note that the speed is large (greater than 1) only if inter-generation time of packets is large (greater than 2D/3).

To further understand the effect of inter-generation time of packets on energy consumption, Figure 4 plots the energy consumed by π g as a function of inter-generation time X (where X is deterministic, packets are of size W = 1 Mbit, and peak AoI and time horizon are D = 5 msec and T = 100 msec respectively). When X ≤ D/3 ≈ 1.7 msec, π g is always has a fresh packet to transmit, and hence, remains busy throughout the interval [0, T ] transmitting packets with speed 3W/D = 3/5 Gbits/sec. So, as long as X ≤ D/3, energy consumption remains constant. When X ∈ (D/3, 2D/3], π g transmits fewer packets, but with same speed 3W/D, and hence, consumes lesser energy. However, when X > 2D/3, π g transmits fewer packets, but at speed larger than 3W/D. So, energy consumption starts to increase with increase in X, and becomes unbounded at values of X close to D.

Next, consider Theorem 5 below that provides a lower bound on the energy consumption of any policy (causal/offline) as a function of the ratio the packet size W and peak AoI D.

Theorem 5: In interval [0, T ], the energy consumed by any policy π that satisfies the deadline constraint (3) is at least max{0, P (2W/D)(T − D)}.

Proof: See Appendix H. Remark 16: Note that the lower bound on the energy consumption of any causal policy provided in Theorem 5 is independent of the actual packet generation times, and hence, we call it as Universal Lower Bound (ULB). Since ULB is agnostic of actual packet generation times, it is not useful in computing competitive ratio of a causal policy. However, it is helpful in understanding the dependence of energy consumption of an optimal offline policy π ⋆ on critical parameters like packet size W and peak AoI D. From Theorem 5, it follows that the energy consumption of any causal policy increases with increases in W/D. So, to visualize this numerically, Figure 5 plots the energy consumption of π g against values of W/D (when initial AoI ∆(0) = 0, time horizon T = 100 msec, and inter-generation time of packets is uniformly distributed in interval [0, 4.5] msec.). Note that for varying W/D, we fixed D = 5 msec, and varied W . Clearly, the energy consumption of π g increases with increase in W/D, and in fact, it grows exponentially when the power function is P (s) = 2 s − 1.

Finally we conclude this section by analyzing the effect of D (maximum allowed AoI) on the energy consumed by π g . Note that if D is large, π g gets more time to transmit individual packets. So, π g transmits the packets with minimum speed 3W/D (which is also small if D is large). Hence, the energy consumed by π g decreases as D increases (other parameters being fixed). Figure 6 verifies this argument as it shows the plot of energy consumed as a function of peak AoI (D) when initial AoI ∆(0) = 0, size of packets is W = 1 Mbit, time horizon T = 100 msec, and inter-generation time of packets is uniformly distributed in interval [0, 3] msec. Note that as D → T , energy consumption of π g converges to 0 because fewer packets (transmitted at slower speed) are sufficient to satisfy the peak AoI constraint (1b).

In this paper, we considered a node where packets of fixed size are generated with arbitrary (but bounded) inter-generation time. The node is required to maintain peak age of information (AoI) at the monitor below a given threshold (throughout a given interval of time) by transmitting these packets and controlling their transmission speed, and the objective is to minimize the total energy consumption. We proposed a (customized) greedy policy, and bounded its competitive ratio (CR) by comparing it against an optimal offline policy by deriving some structural results. Importantly, for polynomial power functions, the CR upper bound is independent of the system parameters (such as packet size, peak AoI, time horizon, and number of packets generated). For exponential power functions, we showed that the competitive ratio of any causal policy grows exponentially with increase in the ratio of the packet size and the peak AoI, and showed that the proposed greedy policy achieves a competitive ratio of the similar order as the lower bound.

Let a policy π transmits w bits in interval [p, q) with constant speed s w (t) = w/(q − p). Also, consider a general policy π ′ that transmits w bits in interval [p, q) with arbitrary speed s(t) ∀t ∈ [p, q). The energy consumed by π is

where in (a), we used Jensen's inequality (P (·) is a convex function). Therefore, π consumes at most as much energy as any other policy π ′ that transmits w bits in interval [p, q). Further, the minimum energy consumed in interval [p, q) is P (w/(q − p))(q − p) (equal to the energy consumed by π in interval [p, q)).

To prove Corollary 1, it is sufficient to show that for fixed w and y 1 < y 2 , P (w/y 1 )y 1 > P (w/y 2 )y 2 . Without loss of generality, let a causal policy π can transmit w bits in interval [0, y 2 ). Therefore, from Lemma 1, we know that minimum energy (equal to P (w/y 2 )y 2 ) is consumed in interval [0, y 2 ) if the w bits are transmitted with constant speed (equal to 1/y 2 )) over the entire interval [0, y 2 ). This implies that if another policy π ′ transmits these w bits over the interval [0, y 1 ) (where y 1 < y 2 ) with constant speed 1/y 1 (and zero speed over the interval [y 1 , y 2 )), it consumes energy P (w/y 1 )y 1 > P (w/y 2 )y 2 , because for π ′ , the speed is not constant in interval [0, y 2 ). So, if y 1 < y 2 , then P (w/y 1 )y 1 > P (w/y 2 )y 2 .

Consider the scenario, where the AoI at the monitor at time t = 0 is ∆(0) = D/2 (thus, d(0) = D − ∆(0) = D/2), the time horizon T = 3D/2 − δ (for δ → 0 + ), and the packets are being generated according to one of the following two instances of packet generation times σ: (i) σ 1 = {0, D/4, D/2}, and (ii) σ 2 = {0, D/4, 5D/6}. An optimal offline policy π ⋆ knows the actual instance σ according to which the packets are being generated. Therefore, if the actual instance is σ = σ 1 , then π ⋆ would consume at most P (2W/D)D units of energy. This is because P (2W/D)D units of energy is sufficient to satisfy the deadline constraint (3) Similarly, if the actual instance σ = σ 2 , then π ⋆ consumes at most P (12W/5D)5D/4 units of energy, required to transmit the three packets generated at time t = 0, t = D/4 and t = 5D/6 with constant speed 12W/5D over the intervals [0, 5D/12), [5D/12, 5D/6) and [5D/6, 5D/4) respectively (because it satisfies the deadline constraint (3)).

However, a causal policy π does not know the actual instance of packet generation times in advance. Therefore, until time t = D/2, π cannot distinguish if the packets are being generated according to σ 1 or σ 2 . Also, π needs to deliver at least one of the packets generated in interval [0, D/2) before time t = d(0) = D/2 (to satisfy the deadline constraint (3) 

b) π delivers packet 1, and transmits γW bits of packet 2 (where γ ∈ [0, 1)) until the initial deadline d(0) = D/2: then, energy consumed by π in interval [0, D/2) is at least P (2(1 + γ)W/D)D/2, and there are following two possible sub-cases.

(1) γ ≥ 0.07: let σ = σ 1 (i.e., packet 3 is generated at time t = D/2).

(i) If π preempts packet 2, and begins to transmit packet 3, still it (π) would consume at least P (2W/D)D/2 units of energy in interval [D/2, T ] (required to transmit packet 3 over the interval [D/2, D) with constant speed 2W/D). So, the total energy consumed by π in interval [0, T ] is P (2(1 + γ)W/D)D/2 + P (2W/D)D/2 ≥ P (2.14W/D)D/2 + P (2W/D)D/2 (for γ = 0.07).

(ii) If π delivers packet 2 at any time t = τ 2 < D, still it would need to transmit packet 3 (because at τ 2 , the deadline would be d 2 = t 2 + D = D/4 + D < T ). Therefore, in this case, if π transmits packet 3 over the interval [τ 2 , d 2 ), then the total energy that π would consume in interval [0, T ] would be

Minimizing (13) with respect to γ ≥ 0.07 and τ 2 ∈ [D/2, d 1 ) (where d 1 = 0 + D), we get E π ≥ P (12W/5D)(5D/4) (with equality if γ = 0.2 and τ 2 = 5D/6). Therefore, the ratio of energy consumed by π and π ⋆ in (2) γ < 0.07: let σ = σ 2 (i.e., packet 3 is generated at time t = 5D/6).

(i) If π preempts packet 2 (does not deliver packet 2), then it must deliver packet 3 before d 1 = 0 + D. Therefore, π consumes at least P (W/(D − 5D/6))(D − 5D/6) units of energy in interval [D/2, T ] (required to transmit packet 3 over the interval [5D/6, D), with constant speed 6W/D). Thus, total energy consumed in interval [0, T ] is E π ≥ P (2(1 + γ)W/D)(D/2) + P (6W/D)(D/6) ≥ P (2W/D)(D/2) + P (6W/D)(D/6) (for γ = 0).

(ii) If π delivers packet 2 at any time t = τ 2 (since only γW < 0.07W bits of packet 2 are transmitted until time D/2, τ 2 > D/2), followed by packet 3 (deadline constraint (3) cannot be satisfied in interval [D, T ] without transmitting packet 3 (generated at time t = 5D/6). Therefore, the energy consumed by π in interval [D/2, T ) is at least P ((1 + 0.93)W/(5D/4 − D/2)), required to transmit the remaining bits of packet 2 (which is at least 0.93W ), and W bits of packet 3 over the interval [D/2, 5D/4) (note that d 2 = t 2 + D = D/4 + D = 5D/4, and hence, to satisfy the deadline constraint (3), π must transmit the W bits of packet 3 before 5D/4). So, total energy consumed by π in interval [0, T ] is E π ≥ P (2(1 + γ)W/D)(D/2) + P ((1 + 0.93)W/(5D/4 − D/2))(5D/4 − D/2) ≥ P (2W/D)(D/2)+ P (7.72W/3D)(3D/4) (for γ = 0). Therefore, the ratio of energy consumed by π and π ⋆ in interval [0, T ] is E π E π ⋆ ≥ min P (2W/D)(D/2) + P (6W/D)(D/6) P (12W/5D)(5D/4) , P (2W/D)(D/2) + P (7.72W/3D)(3D/4) P (12W/5D)(5D/4) ,

From (12), (14) and (15), we conclude that

where c 1 , c 2 and c 3 are finite positive constants, c 2 −c 3 ≥ 0.14, and c 2 /c 3 ≥ 1.07.

Let transmission of packet j begins at time t. So, t j ≤ t, where t j is the generation time of packet j. From Proposition 2, we know that no packet is generated in interval [t−2D/3, t). Also, it has been shown in proof of Proposition 2 that the transmission of packets generated before t − 2D/3 (that are transmitted by π g ) gets completed before time t, and hence, t j cannot be less than t − 2D/3 (because transmission of packet j begins at time t). Hence, we must have t j = t.

Further, π g transmits packet j with constant speed

a) Proof of Property 1: Let π ⋆ transmits the W bits of a packet i with speed that varies with time. Now, consider another policy π ′ , identical to π ⋆ , except that it (π ′ ) transmits the W bits of packet i with constant speed over the same timeinterval where π ⋆ transmits packet i. But, due to convexity of power function P (·), we know that over any given interval of time, transmitting a packet with constant speed consumes minimum energy. Therefore, π ′ consumes less energy than π ⋆ . But this cannot be true, because π ⋆ is an optimal offline policy. Hence, π ⋆ must transmit the W bits of each packet i with constant speed. b) Proof of Property 2: Since π ⋆ knows the generation time of all the packets in advance, it never transmits any packet partially (because transmitting a packet partially consumes energy, without meeting the deadline constraint (3)). Also, π ⋆ only transmits fresh packets (Remark 6). Therefore, it never preempts a packet to transmit it later. Hence, π ⋆ never preempts a packet.

c) Proof of Property 3: Note that when π ⋆ begins to transmit packet i + 1 at time r i+1 , the deadline is d i (the latest delivered packet at r i+1 is packet i). Therefore, τ i+1 < d i , where τ i+1 is the time when packet i + 1 is delivered. Therefore, packet i + 1 is delivered in one of the frames 0 to i. Hence, for i = 0, the only possibility is that packet 1 is delivered in frame 0. Next, using induction, we show that for all i, π g delivers packet i + 1 in frame i. Let packet i is delivered in frame i − 1. Then, there are two possible cases: (i) packet i + 1 is delivered in frame i, and (ii) packet i + 1 is delivered in frame i − 1 (since packet i is delivered in frame i − 1, packet i + 1 cannot have been delivered in a frame previous to frame i − 1). Note that if packet i + 1 is delivered in frame i − 1, then there would be two packets (packet i and packet i + 1) that are delivered in frame i − 1, at time τ i and τ i+1 respectively. However, in this case, transmission of packet i will be redundant because at the start of frame i − 1 (i.e., time d i−2 ), the deadline is d i−1 , and due to Proposition 1, we know that delivery of a single packet is sufficient in interval [d i−2 , d i−1 ). Hence, π ⋆ being an optimal offline policy, will not waste energy delivering both packets i and i + 1 in frame i − 1. Thus, we conclude that for all i, π ⋆ delivers packet i + 1 in frame i. d) Proof of Property 4: From Property 3, we know that exactly one packet (packet i + 1) is delivered in frame i. Also, packet i + 1 is transmitted with constant speed (Property 1). Therefore, transmission speed may decrease only after packet i+1 is delivered. However, π ⋆ being an optimal offline policy, instead of delivering packet i + 1 before the deadline d i (end of frame i), and decreasing the speed, it (π ⋆ ) would transmit packet i + 1 itself at lesser speed, over a larger interval. This follows due to convexity of power function P (·).

In this section, let the packets be indexed in the order they are generated, irrespective of whether they are transmitted by π ⋆ or not (because here we may need to consider packets that are transmitted by π g but not by π ⋆ ). Also, in this section, let the deadline d(t) at any time t be defined according to π g . 6 Let π g transmits a packet j with speed greater than 3W/D. Then, from Corollary 3, we know that the transmission of packet j must have begun at time t j (where t j is the generation time of packet j), and got completed at time d(t j ). Therefore, in interval [t j , d(t j )), π g transmits packet j with constant speed W/(d(t j )−t j ). Lemma 4 shows that the optimal offline policy π ⋆ also transmits an entire packet in interval [t j , d(t j )).

Lemma 4: For each packet j (W bits) transmitted by π g in interval [t j , d(t j )) with constant speed s g (t) = W/(d(t j ) − t j ) > 3W/D, there exists a packetĵ such that π ⋆ transmits the W bits of packetĵ in interval [t j , d(t j )), with constant speed at least equal to W/(d(t j ) − t j ).

Proof: Let π g transmits a packet j with speed greater than 3W/D. From Proposition 2, it follows that no packet is generated in interval [t j −2D/3, t j ), where t j is the generation time of packet j. Without loss of generality, let packet ℓ be the latest packet that is generated before time t j − 2D/3. Since no packet is generated in interval (t ℓ , t j ), packet ℓ remains fresh until time t j . Also, note that π g takes at most D/3 time units to deliver W bits (because s g (t) ≥ 3W/D), and t j − t ℓ > 2D/3. Therefore, even if π g was transmitting a previous packet when packet ℓ was generated at time t ℓ , it (π g ) delivers packet ℓ before time t j . Therefore, the deadline at time t j for π g is d(t j ) = d ℓ .

Since no packet is generated in interval (t ℓ , t j ), the generation time of latest packet delivered by π ⋆ until time t j can at most be t ℓ . Hence, the deadline for π ⋆ at time t j is at most equal to d ℓ . Due to Proposition 1, π ⋆ must deliver a packet (i.e., transmit W bits) in interval [t j , d ℓ ). Since d ℓ = d(t j ), this implies that π ⋆ must transmit at least W bits of some packetĵ in interval [t j , d(t j )). From Proposition 3 (Property 1), we know that that π ⋆ transmits the W bits of a packet with constant speed. Therefore, π ⋆ transmits packetĵ within some sub-interval of interval [t j , d(t j )), with constant speed at least equal to W/(d(t j ) − t j ).

(1) The first result follows directly from Theorem 2, assuming that the packets transmitted by the offline optimal policy π ⋆ has minimum size w, while the packets transmitted by the greedy policy π g has maximum size W .

(2) To prove the second result, consider the scenario where ∆(0) = 0 (i.e., d(0) = D − ∆(0) = D) and T = D + δ/2 (where δ → 0 + ). For some η > 1, and j ∈ {1, 2, 3, ...}, consider the instances of packet generation process σ j = {(δ, W ), (D(1 − 1/η j ), W/η j )}, where a tuple (t i , w i ) denote the generation time t i and packet size w i of packet i. So, under instance σ j , two packets are generated: (i) packet 1 of size W is generated at time δ, and (ii) packet 2 of size W/η j at time D(1 − 1/η j ). Further, let σ 0 = {(δ, W )} denote the instance of packet generation process, where a single packet is generated at time t = δ of size W bits. Note that packet 1 (δ, W ) is common in all these instances σ j (j ≥ 0) of packet generation process.

Note that a causal policy π does not know the actual instance of packet generation process according to which the packets are being generated. So, after packet 1 (δ, W ) is generated (packet 1 is common in all instances σ j (j ≥ 0) of packet generation process), if π does not deliver packet 1, waiting for packet 2 to get generated, and if the packets are being generated according to packet generation instance σ 0 , then packet 2 will never be generated. Hence, such policy π will not be able to satisfy the deadline constraint (3). So, any causal policy π must begin to transmit packet 1 at some time t = r 1 < D. Also, π must continue to transmit packet 1, at least until a new packet is generated. So, let π begins to transmit packet 1, and transmits W (1 − 1/η) bits of packet 1 until time D(1 − 1/η i ) (for some i ≥ 1), and the actual instance of packet generation process (according to which the packets are being generated) is 

where we got (a) using Corollary 1, and the fact that D(1 − 1/η i ) − δ < D(1 − 1/η i ) (because δ > 0). Also, (b) holds because P (·) in an increasing function, and for η > 1 and i ≥ 1, W (1 − 1/η)/(D(1 − 1/η i )) > 1.

Since the lower bound (17) on the competitive ratio of any causal policy π increases with η, taking η → ∞, we get the second result.

In each period i, optimal offline policy π ⋆ transmits at least 2W bits (Lemma 2). Since length of each period is D, therefore, minimum energy is consumed in a period if π ⋆ transmits the 2W bits with constant speed 2W/D throughout the period. Also, periods are overlapping. Therefore, if t 1 is the generation time of first packet that is transmitted by π ⋆ in interval [0, T ], and τ ℓ is the time at which the last packet transmitted by π ⋆ before T is delivered to the monitor, then minimum energy is consumed by π ⋆ in interval [0, T ] if π ⋆ transmits at a constant speed of 2W/D in the interval [t 1 , τ ℓ ). However, note that the initial deadline d(0) = D − ∆(0) ≤ D. Therefore, packet 1 must be delivered by time D. Also, the generation time of last packet must be greater than T − D (so that d ℓ > T ). Therefore, minimum energy is consumed while satisfying the deadline constraint (3) if t 1 = D/2, and τ ℓ = T − D/2. Moreover, the minimum energy consumed is max{0, P (2W/D)(T − D)}, which is a lower bound on the energy consumed by any feasible policy π in interval [0, T ], for any instance of packet generation times.

10 technology trends to watch in the covid-19 pandemic

Real-time status: How often should one update

Lazy is timely: Status updates by an energy harvesting source

Age minimization in energy harvesting communications: Energy-controlled delays

Age of information under energy replenishment constraints

Scheduling status updates to minimize age of information with an energy harvesting sensor

Optimal sampling cost in wireless networks with age of information constraints

Minimizing age of information with power constraints: Opportunistic scheduling in multi-state timevarying networks

Not just age but age and quality of information

Online energy-efficient scheduling for timely information downloads in mobile networks

Minimizing the sum of age of information and transmission cost under stochastic arrival model

Optimal real-time monitoring of an information source under communication costs

Throughput maximization with an average age of information constraint in fading channels

Age of information for updates with distortion: Constant and age-dependent distortion constraints

A scheduling model for reduced cpu energy

Speed scaling to manage energy and temperature

Online energy-efficient packet scheduling for a common deadline with and without energy harvesting

Deadline constrained packet scheduling in the presence of an energy harvesting jammer

Minimizing age of information with soft updates

Update or wait: How to keep your data fresh

Age of information with packet management

Optimizing information freshness in wireless networks under general interference constraints

Controlling packet drops to improve freshness of information