# Sleep, Sense or Transmit: Energy-Age Tradeoff for Status Update with Two-
Thresholds Optimal Policy

Jie Gong, , Jianhang Zhu, Xiang Chen, , and Xiao Ma J. Gong, J. Zhu and X. Ma
are with the School of Computer Science and Engineering, and the Guangdong Key
Laboratory of Information Security Technology, Sun Yat-sen University,
Guangzhou 510006, China. Emails<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Chen is with the School
of Electronics and Information Engineering, Sun Yat-sen University, Guangzhou
510006, China. Email<EMAIL_ADDRESS>
###### Abstract

Age-of-Information (AoI), or simply age, which measures the data freshness, is
essential for real-time Internet-of-Things (IoT) applications. On the other
hand, energy saving is urgently required by many energy-constrained IoT
devices. This paper studies the energy-age tradeoff for status update from a
sensor to a monitor over an error-prone channel. The sensor can sleep, sense
and transmit a new update, or retransmit by considering both sensing energy
and transmit energy. An infinite-horizon average cost problem is formulated as
a Markov decision process (MDP) with the objective of minimizing the weighted
sum of average AoI and average energy consumption. By solving the associated
discounted cost problem and analyzing the Markov chain under the optimal
policy, we prove that there exists a threshold optimal stationary policy with
only two thresholds, i.e., one threshold on the AoI at the transmitter (AoIT)
and the other on the AoI at the receiver (AoIR). Moreover, the two thresholds
can be efficiently found by a line search. Numerical results show the
performance of the optimal policies and the tradeoff curves with different
parameters. Comparisons with the conventional policies show that considering
sensing energy is of significant impact on the policy design, and introducing
sleep mode greatly expands the tradeoff range.

###### Index Terms:

Age-of-information, sleep mode, energy-age tradeoff, Markov decision process

##  I Introduction

With the continuous increase of real-time Internet-of-Things (IoT)
applications such as remote monitoring and control, phase data update in smart
grid, environment monitoring for autonomous driving and etc., timely status
information is strictly required to guarantee a fast and accurate response
[1]. Thus, it is essential to persistently obtain fresh data. The _age-of-
information_ (AoI), or simply _age_ , defined as the time elapsed since the
generation of the latest received update [2], is a candidate performance
metric for data freshness. Different from the conventional delay performance,
AoI captures the impact of both transmission delay and data generation
frequency.

On the other hand, the sensors gathering status information are usually
energy-constrained. Thus, it is also vital to reduce the sensors’ energy
consumption. However, the two objectives, keeping data fresh and reducing
energy consumption, can not be achieved simultaneously in general. To minimize
AoI, the sensors should sense and transmit new status in time. To reduce
energy consumption, “lazy” policy is preferred, i.e., the sensors may sense
with a low frequency and turn to sleep mode. Therefore, there exists a
fundamental tradeoff between AoI and energy consumption, which is of great
significance to provide a guidance to determine the sensing and transmission
policy in energy-constrained status update communications.

In this paper, to exploit the energy-age tradeoff, we consider a status update
system where a sensor generates and transmits status packets to a monitor over
an error-prone channel. In this system, a data transmission may fail due to a
channel error, and the sensor is aware of the transmission success/failure via
ACK/NACK feedback protocol. If the transmission succeeds, the data at the
monitor is refreshed and the AoI is reduced. As both status sensing and data
transmission consume energy, a fundamental problem is when to sleep, sense,
and transmit to balance data freshness and energy consumption. Intuitively,
when a fresh data is successfully transmitted, the sensor may sleep to save
energy. If the data becomes stale on the contrary, new data should be sensed
and transmitted to reduce AoI. The main goal of this paper is to find the
optimal policy to achieve the tradeoff between energy and age.

###  I-A Related Work

The energy and age related research is originated from [3], where an energy
harvesting source was considered. In this early work, _zero-wait policy_ was
introduced, which generates a fresh update just as the prior update is
delivered and the channel becomes idle. The optimality of zero-wait policy was
analyzed in [4]. Then, the age-optimal policies were extensively studied by
assuming infinite battery [5], unit battery [6] and finite battery [7, 8],
respectively. Transmit power control under an energy harvesting constraint was
introduced in [9]. With random arrival of status updates and energy units, the
average AoI performance with finite battery was analyzed in [10, 11].
Reinforcement learning approach was adopted to minimize the average AoI for a
single energy harvesting sensor [12] and multiple wireless powered sources
[13], respectively. Joint sampling and updating for wireless powered
communication systems considering time and energy costs for sensing was
studied in [14]. Peak AoI minimization with random energy arrivals was studied
in [15] considering both sensing and transmission energy. The above works
usually aim to optimize the AoI under a certain energy constraint. Different
from them, in energy-age tradeoff problem, age can be sacrificed to reduce
energy and vice versa.

Status update over error-prone channels has been extensively studied in the
literature. Timely updates over an erasure channel for infinite incremental
redundancy and fixed redundancy were considered in [16]. The optimal status
update policy without feedback was studied in [17]. With ACK/NACK feedback,
automatic repeat-request (ARQ) and hybrid ARQ (HARQ) protocols were adopted to
keep the data fresh [18, 19, 20, 21, 22, 23, 24, 25]. The most relevant paper
to our work is [23], where the age-optimal policy under a resource constraint
was obtained for ARQ and HARQ protocols. However, the sensing energy is not
considered, which is non-negligible in many applications and is even larger
than the transmit energy (see [26] and references therein). More importantly,
the consideration of sensing energy in policy design will induce significant
difference. Specifically, if the sensing energy is not considered, sensing and
transmitting a new packet can always reduce AoI without additional cost
compared with retransmission. On the contrary, if the sensing energy is non-
negligible, there exists a fundamental tradeoff between AoI reduction by
sensing a new data and energy saving by retransmission. Thus, different from
[23], one of the main challenges to be tackled in this paper is how to balance
the energy cost between sensing and transmission.

Recently, the energy-age tradeoff analysis has drawn more and more attention.
The energy-age tradeoff in an error-prone channel was revealed in [27]. Then,
the analysis was extended to the fading channel [28]. The impact of coding on
the tradeoff performance was analyzed in [29]. Without ACK/NACK feedback, the
energy-age tradeoff for random update generation was also found in [30]. The
tradeoff between energy efficiency and AoI in a multicast system was optimized
in [31]. However, sleep mode is not considered in these works, although it is
promising for energy saving as was shown in the conventional studies on
energy-delay tradeoff [32, 33, 34]. Since age and delay are closely related,
it is crucial to consider sleep mode, which however, makes the study on the
energy-age tradeoff very challenging.

###  I-B Main Results

Based on Markov decision process (MDP) [35], an infinite-horizon average cost
problem is formulated with the objective of minimizing a weighted sum of
average AoI and average energy consumption. The sensor stores only the latest
sensed data packet. It can either sleep, retransmit the stored packet, or
sense and transmit a new one depending on the ACK/NACK feedback and the
instantaneous AoI. To characterize the system state, the AoI at the
transmitter side (AoIT) and the AoI at the receiver side (AoIR) are
introduced. We show that there exists a threshold optimal policy to solve the
MDP problem. It is remarkable that threshold optimal structure has been found
in many works (e.g., [12, 13, 14, 36]). However, how to find the optimal
thresholds is quite challenging as they are usually state-dependent. Different
from the existing works, we show that the optimal policy is determined by only
two thresholds, and one of them can be expressed by the other in closed-form.
Moreover, these two thresholds can be efficiently found by a line search. In
summary, the main contributions are listed as follows.

  * •

We prove that there exists a _two-thresholds_ optimal stationary policy for
the average cost problem. In particular, given the optimal thresholds
$\theta_{\mathrm{t}}$ and $\theta_{\mathrm{r}}$, the sensor

    * –

senses and transmits a new packet if AoIT $\geq\theta_{\mathrm{t}}$ and AoIR
$\geq\theta_{\mathrm{r}}$,

    * –

re-transmits the stored packet if AoIT $<\theta_{\mathrm{t}}$ and AoIR
$\geq\theta_{\mathrm{r}}$,

    * –

stays in sleep mode if AoIR $<\theta_{\mathrm{r}}$.

  * •

To obtain the above result, we firstly show that the optimal policy for the
average cost problem is a limit of the optimal policies for the associated
discounted cost problem with discount factors tending to 1. Then, we prove
that there exists a threshold optimal stationary policy for the discounted
problem. Thus, the optimal policy for the average cost problem is also
threshold-based. Finally, we show that the minimum average cost can be
expressed in closed-form by only two thresholds, which results in the two-
thresholds optimal policy.

  * •

Furthermore, we show that $\theta_{\mathrm{r}}$ can be expressed as a closed-
form function of $\theta_{\mathrm{t}}$, and the optimal $\theta_{\mathrm{t}}$
is upper bounded. Accordingly, an efficient line search algorithm is proposed
to find the optimal thresholds.

  * •

We characterize the energy-age tradeoff under the optimal policy via numerical
simulations, and show the impact of system parameters on the tradeoff curves.
We also compare with the existing policies to show the performance gain of our
policy.

The rest of this paper is organized as follows. The system model and problem
formulation is given in Sec. II. The associated discounted cost problem is
presented in Sec. III. Sec. IV proves the optimal threshold policy, and the
optimal thresholds are obtained in Sec. V. Numerical results are shown in Sec.
VI. Finally, Sec. VII concludes the paper.

##  II System Model and Problem Formulation

Consider a status update system in Fig. 1, where a sensor generates and
transmits status packets to a monitor over an error-prone channel. Assume the
system is slotted, and without loss of generality, the slot length is set to
1. At the beginning of each slot, the sensor can either sense or not. If it
senses, a new packet conveying the latest status is generated. Denote the
sensing energy consumption by $E_{\mathrm{s}}$, and assume the time for
sensing is negligible. The assumption is reasonable in many sensing
applications such as taking real-time pictures by a camera with high shutter
speed. The sensor only stores the latest sensed data packet. If the sensor
does not sense, the last sensed data packet remains there. Otherwise, it is
replaced by the newly sensed packet. During each slot, at most one packet can
be transmitted. Denote the energy consumption for transmitting a packet by
$E_{\mathrm{t}}$. The transmitted packet may not be successfully received by
the monitor due to channel error. Denote the channel error probability by
$p\in(0,1)$, which is identical and independent among slots. If the packet is
successfully received by the monitor, an ACK is sent back to the sensor via an
error-free feedback channel. Otherwise, a NACK is sent back. Depending on the
feedback, the sensor decides its action in the next slot.

Figure 1: Status update system over an error-prone channel with feedback.

Denote by $s_{k}=1$ if a new packet is generated at the beginning of slot $k$,
and $s_{k}=0$ otherwise. Denote by $t_{k}=1$ if the stored packet is
transmitted in slot $k$, and $t_{k}=0$ otherwise. Thus, the sensor has four
possible actions in each slot: (1) sleep (neither sense nor transmit), i.e.,
$s_{k}=0,t_{k}=0$; (2) sense the latest status but do not transmit, i.e.,
$s_{k}=1,t_{k}=0$; (3) do not sense but retransmit the stored packet, i.e.,
$s_{k}=0,t_{k}=1$; (4) sense and transmit a new packet, i.e.,
$s_{k}=1,t_{k}=1$. The actions are taken by jointly considering the
information freshness and the sensor’s energy consumption. Intuitively, the
second action is not a good option as it consumes energy but does not
contribute to AoI. In fact, as proved later in Lemma 2, the optimal policy
does not contain this action. Next, we give some definitions before the
problem formulation.

###  II-A Definitions of AoI

The definitions of AoI, AoIT, and AoIR are given as follows.

######  Definition 1.

At time $t$, if the observed latest packet is generated at time $U(t)$, the
AoI is

$\displaystyle\Delta(t)=t-U(t).$ (1)

######  Definition 2.

The AoIT, denoted by $\Delta_{T}(t)$, is the AoI observed at the transmitter
side.

######  Definition 3.

The AoIR, denoted by $\Delta_{R}(t)$, is the AoI observed at the receiver
side.

An example of AoIT and AoIR curves is depicted in Fig. 2. As both AoIT and
AoIR grow linearly during each slot, it is sufficient to characterize the AoIT
and AoIR curves by the instantaneous AoIs at the beginning of each slot. In
particular, denote $a_{\mathrm{t},k}$ and $a_{\mathrm{r},k}$ as the
instantaneous AoIT and AoIR at the beginning of slot $k$ (before taking any
action), respectively. The evolution from
$(a_{\mathrm{t},k},a_{\mathrm{r},k})$ to
$(a_{\mathrm{t},k+1},a_{\mathrm{r},k+1})$ depends on the action. If the sensor
does not generate a new packet, i.e., $s_{k}=0$, the packet at the transmitter
side is not updated. Hence, the AoIT grows linearly. If a new packet is
generated at the beginning of slot $k$, i.e., $s_{k}=1$, the AoIT at the
beginning of slot $k+1$ becomes 1. Similarly, the packet at the receiver side
is not updated if the sensor does not transmit ($t_{k}=0$) or transmits
($t_{k}=1$) but fails. In this case, the AoIR grows linearly. If the
transmission succeeds, the AoIR becomes the same as the AoIT because the data
at both sides are the same. In summary, we have

$\displaystyle(a_{\mathrm{t},k+1},a_{\mathrm{r},k+1})=\left\\{\begin{array}[]{ll}(a_{\mathrm{t},k}\\!+\\!1,a_{\mathrm{r},k}\\!+\\!1),&\textrm{if~{}}s_{k}\\!=\\!t_{k}\\!=\\!0,\textrm{~{}or~{}}s_{k}\\!=\\!0,t_{k}\\!=\\!1\textrm{~{}and~{}fails},\\\
(a_{\mathrm{t},k}\\!+\\!1,a_{\mathrm{t},k}\\!+\\!1),&\textrm{if~{}}s_{k}\\!=\\!0,t_{k}\\!=\\!1\textrm{~{}and~{}succeeds},\\\
(1,a_{\mathrm{r},k}\\!+\\!1),&\textrm{if~{}}s_{k}\\!=\\!1,t_{k}\\!=\\!0,\textrm{~{}or~{}}s_{k}\\!=\\!t_{k}\\!=\\!1\textrm{~{}and~{}fails},\\\
(1,1),&\textrm{if~{}}s_{k}\\!=\\!1,t_{k}\\!=\\!1\textrm{~{}and~{}succeeds}.\end{array}\right.$
(6)

Figure 2: Evolution of AoIT $\Delta_{T}(t)$ (blue dashed curve) and AoIR
$\Delta_{R}(t)$ (black bold curve).

###  II-B Energy-Age Tradeoff Problem

To maintain a low AoIR, a new packet should be generated and transmitted in
every slot. To reduce the energy consumption, on the other hand, the sensor
should reduce the number of sensing and transmission actions. Therefore, there
is a tradeoff between energy and age.

From the age perspective, the average AoIR is defined as [2]

$\displaystyle\bar{\Delta}=\lim_{\tau\rightarrow\infty}\frac{1}{\tau}\int_{0}^{\tau}\Delta_{R}(t)\mathrm{d}t.$
(7)

It can be geometrically computed as the sum of the area of the trapezoid
$Q_{k}$ as in Fig. 2 divided by the total time. As the slot length equals to
one, we have

$\displaystyle\bar{\Delta}=\lim_{K\rightarrow\infty}\frac{1}{K}\mathbb{E}\left[\sum_{k=1}^{K}Q_{k}\right]=\lim_{K\rightarrow\infty}\frac{1}{K}\mathbb{E}\left[\sum_{k=1}^{K}\frac{a_{\mathrm{r},k}+(a_{\mathrm{r},k}\\!+\\!1)}{2}\right]=\lim_{K\rightarrow\infty}\frac{1}{K}\mathbb{E}\left[\sum_{k=1}^{K}a_{\mathrm{r},k}\right]+\frac{1}{2},$
(8)

where the expectation $\mathbb{E}$ is taken over all possible channel
realizations over all the slots.

The average energy consumption of the sensor can be calculated as

$\displaystyle\bar{E}=\lim_{K\rightarrow\infty}\frac{1}{K}\mathbb{E}\left[\sum_{k=1}^{K}(s_{k}E_{\mathrm{s}}+t_{k}E_{\mathrm{t}})\right].$
(9)

Our objective is to exploit the tradeoff between the average AoIR and the
average energy consumption. Similar to [37], we consider minimizing the
weighted sum of the average AoIR and the average energy consumption by
deciding when to sleep, sense and transmit, i.e.,

$\displaystyle\min_{\\{s_{k},t_{k}\\}_{k=1}^{\infty}}\lim_{K\rightarrow\infty}\frac{1}{K}\mathbb{E}\left[\sum_{k=1}^{K}\left(a_{\mathrm{r},k}+\omega(s_{k}E_{\mathrm{s}}+t_{k}E_{\mathrm{t}})\right)\right]+\frac{1}{2},$
(10)

where $\omega>0$ is a pre-defined weighting factor indicating the importance
of energy over age. By solving (10) for a set of $\omega$’s, the tradeoff
pairs of age and energy can be obtained. In practice, the weighting factor can
be dynamically tuning depending on the available energy. In the rest of this
paper, the constant factor $\frac{1}{2}$ in (10) is ignored as it does not
influence the policy design.

Remark 1. We should emphasize here that the proposed solution for the above
optimization problem (10) can be directly applied to the multi-sensor IoT
systems when the sensors are allocated with orthogonal frequency bands. It can
also be extended to the case that the sensors are scheduled by the round-robin
algorithm. In particular, our result can be applied to each sensor by
redefining a slot as a scheduling round. As the actual AoI is a linear
function of the redefined slots since generation, the structure of the
proposed solution does not change.

Remark 2. The energy-age tradeoff can also be characterized by considering the
constrained problem $\min\limits_{\bar{E}\leq E_{\max}}\bar{\Delta}$. In fact,
it can be solved based our solution. In particular, if there exists an
$\omega^{*}$ such that the corresponding average energy consumption in the
minimum weighted sum is $E_{\max}$, the optimal policy to minimize the
weighted sum also minimizes $\bar{\Delta}$ under constraint $\bar{E}\leq
E_{\max}$. Otherwise, there exists a randomized policy to solve the
constrained problem that is a combination of the optimal policies for two
weighted sum problems, one with the corresponding energy consumption smaller
than $E_{\max}$, and the other with the energy larger than $E_{\max}$ [38].

###  II-C MDP Problem Formulation

The problem (10) can be reformulated as an MDP. A general MDP is characterized
by four key components: state, action, state transition and per-stage cost.
Firstly, the stage in our problem refers to the time slot. For ease of
description, slot and stage can be used interchangeably in the rest of this
paper. The state in stage $k$ includes both AoIT and AoIR at the beginning of
slot $k$, which can be denoted by
$x_{k}=(a_{\mathrm{t},k},a_{\mathrm{r},k})\in\mathcal{A}$, where the state
space can be denoted by $\mathcal{A}=\\{(i,j)|i\leq
j,i,j\in\\{1,2,\cdots\\}\\}$. Notice that we have $a_{\mathrm{t},k}\leq
a_{\mathrm{r},k}$ as the packet at the receiver is always “older” than the one
at the transmitter.

The action to be taken includes sensing decision and transmission decision,
i.e., $u_{k}=(s_{k},t_{k})\in\mathcal{U}$, where the action space can be
denoted by $\mathcal{U}=\\{(0,0),(0,1),(1,0),(1,1)\\}$.

The state transition probability
$p_{(i,j)\rightarrow(i^{\prime},j^{\prime})}(u)=\mathrm{Pr}(x_{k+1}=(i^{\prime},j^{\prime})|x_{k}=(i,j),u_{k}=u)$
can be calculated as

$\displaystyle
p_{(i,j)\rightarrow(i^{\prime},j^{\prime})}(u)=\left\\{\begin{array}[]{ll}1,&\textrm{if~{}}i\leq
j,i^{\prime}=i+1,j^{\prime}=j+1,u=(0,0),\\\
{}&\quad\textrm{or~{}}i=j,i^{\prime}=j^{\prime}=i+1,u=(0,1),\\\
{}&\quad\textrm{or~{}}i\leq j,i^{\prime}=1,j^{\prime}=j+1,u=(1,0),\\\
p,&\textrm{if~{}}i<j,i^{\prime}=i+1,j^{\prime}=j+1,u=(0,1),\\\
{}&\quad\textrm{or~{}}i\leq j,i^{\prime}=1,j^{\prime}=j+1,u=(1,1),\\\
1-p,&\textrm{if~{}}i<j,i^{\prime}=j^{\prime}=i+1,u=(0,1),\\\
{}&\quad\textrm{or~{}}i\leq j,i^{\prime}=j^{\prime}=1,u=(1,1),\\\
0,&\textrm{else.}\end{array}\right.$ (19)

The cost per stage can be expressed as

$\displaystyle
g(x_{k},u_{k})=a_{\mathrm{r},k}+\omega(s_{k}E_{\mathrm{s}}+t_{k}E_{\mathrm{t}}).$
(20)

Thus, the problem (10) can be reformulated as

$\displaystyle\min_{\pi}\;J_{\pi}(x_{0})\overset{\textrm{def}}{=}\lim_{K\rightarrow\infty}\frac{1}{K}\mathbb{E}\left(\sum_{k=0}^{K-1}g(x_{k},\mu_{k}(x_{k}))\Bigg{|}x_{0}\right),$
(21)

where $x_{0}$ is the initial state, and $\pi=\\{\mu_{0},\mu_{1},\cdots\\}$ is
the policy. In general, $\mu_{k}$ is possibly randomized and follows a
conditional probability distribution of the action $u_{k}$ under the condition
of a given state $x_{k}$, i.e. $\mu_{k}\sim p_{k}(u_{k}|x_{k})$, where $0\leq
p_{k}(u_{k}|x_{k})\leq 1$ and
$\sum_{u_{k}\in\mathcal{U}}p_{k}(u_{k}|x_{k})=1,\forall x_{k}$. A policy is
called _stationary_ if the distribution $p_{k}(u_{k}|x_{k})$ does not change
over stage $k$, which can be denoted as $\mu_{k}=\mu\sim
p(u_{k}|x_{k}),\forall k$. Furthermore, a policy is _deterministic_ if
$p_{k}(u_{k}|x_{k})\in\\{0,1\\}$. In this case,
$\mu_{k}:\mathcal{A}\rightarrow\mathcal{U}$ is a mapping from the state space
to the action space with $u_{k}=\mu_{k}(x_{k})$ if $p_{k}(u_{k}|x_{k})=1$.

It is remarkable that the state space $\mathcal{A}$ is countably infinite and
the per-stage cost is unbounded. Hence, the conventional iterative algorithms
such as policy iteration or value iteration are difficult to be applied
directly in practice. To tackle this difficulty, we next exploit the
structural properties of our problem to find the optimal policy. To this end,
we firstly associate the average cost minimization problem with its discounted
version. Then, we prove the structural properties for the discounted problem,
which turn out to hold for the average cost problem as well.

##  III Associated Discounted Cost Problem

It is well-known that the average cost MDP problem is closely related to its
discounted version [39]. Thus, we start by considering an infinite horizon
discounted cost MDP problem as

$\displaystyle\min_{\pi}\;J_{\alpha,\pi}(x_{0})\overset{\textrm{def}}{=}\lim_{K\rightarrow\infty}\mathbb{E}\left(\sum_{k=0}^{K-1}\alpha^{k}g(x_{k},\mu_{k}(x_{k}))\Bigg{|}x_{0}\right),$
(22)

where $\alpha\in(0,1)$. Since the AoIR grows at most linearly versus the stage
$k$ and $g(x_{k},\mu_{k})\leq
a_{\mathrm{r},k}+\omega(E_{\mathrm{s}}+E_{\mathrm{t}})$, we have

$\displaystyle
J_{\alpha,\pi}(x_{0})\leq\sum_{k=0}^{\infty}\alpha^{k}(a_{\mathrm{r},0}+k+\omega(E_{\mathrm{s}}+E_{\mathrm{t}}))=\frac{1}{1-\alpha}\left(a_{\mathrm{r},0}+\omega(E_{\mathrm{s}}+E_{\mathrm{t}})+\frac{\alpha}{1-\alpha}\right)<\infty.$
(23)

Hence, for any given initial state $x_{0}$ and discount factor $\alpha$,
$J_{\alpha,\pi}(x_{0})$ is well-defined for all policies. Given the initial
state $x_{0}=(i,j)$, denote the minimum expected discounted cost as

$\displaystyle
J_{\alpha}(i,j)=J_{\alpha}(x_{0})=\min_{\pi}J_{\alpha,\pi}(x_{0}).$ (24)

In the following, we will show the existence of an optimal stationary
deterministic policy for the discounted cost problem (22) and its convergence
to the average cost problem (21). Thus, if there is a threshold optimal policy
for the discounted version, the optimal policy for the average cost problem is
also threshold-based.

For an infinite horizon discounted cost problem with finite state space and
bounded per-stage cost, it is guaranteed that the optimal discounted cost can
be achieved by dynamic programming (DP) algorithm [35, Prop. 1.2.1], and there
exists a stationary deterministic policy to attain the minimum [35, Prop.
1.2.3]. However, as the problem (22) has a countably infinite state space and
unbounded per-stage cost, the convergence of the DP algorithm and the
existence of a stationary policy need to be reconsidered. In fact, observing
that the AoIR increases at most linearly with stage $k$, the convergence of
the DP algorithm can still be proved by modifying some lines in the proof of
[35, Prop. 1.2.1], and there is also a stationary deterministic policy. The
results are summarized as follows.

######  Proposition 1.

Define a sequence of functions for all $x\in\mathcal{A}$ as

$\displaystyle J_{n}(x)$
$\displaystyle=\min_{u\in\mathcal{U}}\left(g(x,u)+\alpha\sum_{x^{\prime}\in\mathcal{A}}p_{x\rightarrow
x^{\prime}}(u)J_{n-1}(x^{\prime})\right),\quad n\geq 1$ (25)

where $J_{0}(x)=0$, $g(x,u)$ is given as (20) and $p_{x\rightarrow
x^{\prime}}(u)$ is given as (19). We have

$\displaystyle\lim_{n\rightarrow\infty}J_{n}(x)=J_{\alpha}(x),$ (26)

where $J_{\alpha}(x)$ is given as (24). In addition, the Bellman’s Equation
holds as

$\displaystyle
J_{\alpha}(x)=\min_{u\in\mathcal{U}}\left(g(x,u)+\alpha\sum_{x^{\prime}\in\mathcal{A}}p_{x\rightarrow
x^{\prime}}(u)J_{\alpha}(x^{\prime})\right),$ (27)

and the stationary policy $\mu_{\alpha}$, where $u=\mu_{\alpha}(x)$ attaining
the minimum of (27), is optimal.

###### Proof.

See Appendix -A. ∎

The following lemma shows that $J_{n}(x)$ is monotonic versus each component
of $x$.

######  Lemma 1.

For any $n\geq 1$ and $x=(i,j)\in\mathcal{A}$, the function $J_{n}(x)$ defined
in (25) satisfies

$\displaystyle J_{n}(i,j+1)-J_{n}(i,j)$ $\displaystyle\geq 1,$ (28)
$\displaystyle J_{n}(i+1,j)-J_{n}(i,j)$ $\displaystyle\geq 0.$ (29)

###### Proof.

See Appendix -B. ∎

Now, we relate the average cost minimization problem to its discounted
version. It is shown in [39] that a stationary policy for an average cost
problem exists under some conditions, and can be obtained by letting $\alpha$
tend to 1 in the associated discounted cost problem. According to the main
results and conditions given in [39], we can have the following proposition.

######  Proposition 2.

Let $\alpha_{n}$ be any sequence of discount factors converging to 1 with the
associated optimal stationary policy $\mu_{\alpha_{n}}$ for the discounted
cost problem (22). There exists a subsequence of $\alpha_{n}$ denoted by
$\beta_{n}$ and a stationary policy $\mu$ that is a limit of
$\mu_{\beta_{n}}$. That is, for every state $x$, there exists an integer
$N(x)$ such that $\mu_{\beta_{n}}(x)=\mu(x)$ for all $n\geq N(x)$. In
addition, the stationary policy $\mu$ is optimal for the average cost
minimization problem (21).

###### Proof.

See Appendix -C. ∎

Based on Proposition 2, if some structural property of the discounted cost
problem can be found, it must hold for the corresponding average cost problem.
Furthermore, a quick observation in the following lemma helps to reduce the
size of the action space.

######  Lemma 2.

The optimal stationary policy $\mu_{\alpha}$ for the problem (22) satisfies

$\displaystyle\mu_{\alpha}(x)\neq(1,0),\quad\forall x\in\mathcal{A}$ (30)

###### Proof.

See Appendix -D. ∎

Based on Proposition 2, we can further prove that $\mu(x)\neq(1,0),\forall
x\in\mathcal{A}$. Therefore, only the actions $(0,0),(0,1)$, and $(1,1)$ need
to be considered. For simplicity, in the rest of this paper, the action is re-
denoted as $u_{k}=s_{k}+t_{k}$ and the action space is
$\mathcal{U}=\\{0,1,2\\}$. Then, the DP algorithm for the problem (22) can be
explicitly described as follows.

$\displaystyle J_{n}(i,j)$
$\displaystyle=\min_{u\in\\{0,1,2\\}}\left\\{Q_{n}(i,j,u)\right\\},\quad n\geq
1,$ (31)

where $J_{0}(i,j)=0$, and

$\displaystyle Q_{n}(i,j,0)$ $\displaystyle=j+\alpha J_{n-1}(i+1,j+1),$ (32)
$\displaystyle Q_{n}(i,j,1)$ $\displaystyle=j+\omega E_{\mathrm{t}}+\alpha
pJ_{n-1}(i+1,j+1)+\alpha(1-p)J_{n-1}(i+1,i+1),$ (33) $\displaystyle
Q_{n}(i,j,2)$ $\displaystyle=j+\omega E_{\mathrm{t}}+\omega
E_{\mathrm{s}}+\alpha pJ_{n-1}(1,j+1)+\alpha(1-p)J_{n-1}(1,1).$ (34)

Denote by

$\displaystyle\mu_{n}(i,j)=\arg\min_{u\in\\{0,1,2\\}}\left\\{Q_{n}(i,j,u)\right\\}$
(35)

According to Proposition 1, we have
$J_{\alpha}(i,j)=\lim_{n\rightarrow\infty}J_{n}(i,j),\mu_{\alpha}(i,j)=\lim_{n\rightarrow\infty}\mu_{n}(i,j)$.
Denote by
$Q_{\alpha}(i,j,u)=\lim_{n\rightarrow\infty}Q_{n}(i,j,u),u\in\\{0,1,2\\}$. In
the next section, we will show the threshold optimal policy by exploiting the
properties of the above DP iteration.

##  IV Threshold Optimal Policy

To show the structural property of the discounted cost problem, we denote
$\mathcal{A}_{\mathrm{ext}}=\\{(i,j)|i,j\in\\{1,2,\cdots\\}\\}$. With the
extended state space $\mathcal{A}_{\mathrm{ext}}$ without constraint $i\leq
j$, the monotonicity in Lemma 1 still holds and the DP iteration (31) still
converges to the optimal cost of the problem (22) for $(i,j)\in\mathcal{A}$ as
the cost function for state $(i,j)\in\mathcal{A}$ does not rely on any state
in $\mathcal{A}_{\mathrm{ext}}\setminus\mathcal{A}$. Then, we exploit the
properties of $J_{n}(i,j)$ and $J_{\alpha}(i,j)$ for
$(i,j)\in\mathcal{A}_{\mathrm{ext}}$.

######  Lemma 3.

For any $n\geq 1$, if $i\geq
i_{0}\overset{\textrm{def}}{=}\left\lceil\dfrac{\omega
E_{\mathrm{s}}}{\alpha\left(1-p\right)}\right\rceil$ or $i\geq j$, we have

$\displaystyle\mu_{n}(i,j)$ $\displaystyle=\mu_{n}(i+1,j)\in\\{0,2\\},$ (36)
$\displaystyle J_{n}(i,j)$ $\displaystyle=J_{n}(i+1,j).$ (37)

###### Proof.

See Appendix -E. ∎

######  Lemma 4.

For any $n\geq 2$ and $j\geq
j_{0}\overset{\text{def}}{=}\left\lceil\dfrac{\omega E_{\mathrm{t}}+\omega
E_{\mathrm{s}}}{\alpha\left(1-p\right)}\right\rceil$, there exists $i_{n}$
such that

$\displaystyle\mu_{n}(i,j)=\left\\{\begin{array}[]{ll}1,&i<i_{n}\\\ 2,&i\geq
i_{n}\end{array}\right.$ (40) $\displaystyle
J_{n}(i,j+1)-J_{n}(i,j)=\dfrac{1-\left(\alpha p\right)^{n}}{1-\alpha p},$ (41)

###### Proof.

See Appendix -F. ∎

Based on Lemma 3 and Lemma 4, as
$J_{\alpha}(i,j)=\lim_{n\rightarrow\infty}J_{n}(i,j),\mu_{\alpha}(i,j)=\lim_{n\rightarrow\infty}\mu_{n}(i,j)$,
similar properties hold for the optimal policy and the optimal cost. The
results are summarized as follows.

######  Corollary 1.

If $i\geq i_{0}$ or $i\geq j$, we have

$\displaystyle\mu_{\alpha}(i,j)$
$\displaystyle=\mu_{\alpha}(i+1,j)\in\\{0,2\\},$ (42) $\displaystyle
J_{\alpha}(i,j)$ $\displaystyle=J_{\alpha}(i+1,j).$ (43)

If $j\geq j_{0}$, there exists $i_{\alpha}$ such that

$\displaystyle\mu_{\alpha}(i,j)=\left\\{\begin{array}[]{ll}1,&i<i_{\alpha}\\\
2,&i\geq i_{\alpha}\end{array}\right.$ (46) $\displaystyle
J_{\alpha}(i,j+1)-J_{\alpha}(i,j)=\dfrac{1}{1-\alpha p}.$ (47)

Figure 3: The structure of the optimal policy for the discounted cost problem.

Based on Corollary 1, as $\mu_{\alpha}(i,j)\in\\{0,2\\}$ for $i\geq i_{0}$ and
$\mu_{\alpha}(i,j)\in\\{1,2\\}$ for $j\geq j_{0}$, we have
$\mu_{\alpha}(i,j)=2$ for $i\geq i_{0},j\geq j_{0}$. Hence, according to (46),
we have $i_{\alpha}\leq i_{0}$, and $\mu_{\alpha}(i,j)=2$ for $i\geq
i_{\alpha},j\geq j_{0}$, $\mu_{\alpha}(i,j)=1$ for $i<i_{\alpha},j\geq j_{0}$.
Therefore, the structure of the optimal policy for $j\geq j_{0}$ is
determined, as illustrated in Fig. 3. Then, we examine the case for $j<j_{0}$.
According to (42), the optimal policy in each column is the same (0 or 2) for
$i\geq i_{0}$. Thus, denote by

$\displaystyle
j_{\alpha}=\max\\{j:\mu_{\alpha}(i,j-1)=0,\mu_{\alpha}(i,j)=\mu_{\alpha}(i,j+1)=\cdots=\mu_{\alpha}(i,j_{0})=2,\forall
i\geq i_{0}\\}.$ (48)

By definition, we have $\mu_{\alpha}(i,j)=2$ for $i\geq i_{0},j\geq
j_{\alpha}$. In the following, we will show that $\mu_{\alpha}(i,j)=1$ for all
$i<i_{\alpha},j\geq j_{\alpha}$, and $\mu_{\alpha}(i,j)=2$ for all $i\geq
i_{\alpha},j\geq j_{\alpha}$. While for $j<j_{\alpha}$, the optimal policy is
threshold-based between actions 0 and 1. Before that, denote by

$\displaystyle L_{\alpha}(i,j)$
$\displaystyle=J_{\alpha}(i+1,j)-J_{\alpha}(i,j),$ (49) $\displaystyle
D_{\alpha}(i)$ $\displaystyle=J_{\alpha}(i+1,i+1)-J_{\alpha}(i,i).$ (50)

We have the following lemma.

######  Lemma 5.

For any $i\geq 1,j\geq j_{0}$, we have

$\displaystyle D_{\alpha}(i+1)\leq D_{\alpha}(i),$ (51) $\displaystyle
L_{\alpha}(i,j)=L_{\alpha}(i,j+1)<D_{\alpha}(i),$ (52)

###### Proof.

See Appendix -G. ∎

Then, we can show the structure of the optimal policy in the whole state space
$\mathcal{A}_{\mathrm{ext}}$.

######  Lemma 6.

Eqs. (46), (47) and (52) hold for any $i\geq 1,j\geq j_{\alpha}$.

###### Proof.

See Appendix -H. ∎

######  Lemma 7.

For any $j<j_{\alpha}$, there exist $I_{\alpha}(1)\leq
I_{\alpha}(2)\leq\cdots\leq I_{\alpha}(j_{\alpha}-1)\leq i_{\alpha}$ so that

$\displaystyle\mu_{\alpha}(i,j)=\left\\{\begin{array}[]{ll}0,&i\geq
I_{\alpha}(j),\\\ 1,&i<I_{\alpha}(j).\end{array}\right.$ (55)

###### Proof.

See Appendix -I. ∎

Now, we can present the optimal policy for the average cost problem (21) as
follows.

######  Proposition 3.

There exists a threshold optimal stationary policy for the average cost
problem (21). In particular, with thresholds satisfying
$\theta(1)\leq\cdots\leq\theta(\theta_{\mathrm{r}}-1)\leq\theta_{\mathrm{t}}\leq\theta_{\mathrm{r}}$,
we have

$\displaystyle\mu(i,j)=\left\\{\begin{array}[]{ll}0,&\textrm{if~{}}i\geq\theta(j),j<\theta_{\mathrm{r}},\\\
1,&\textrm{if~{}}i<\theta(j),j<\theta_{\mathrm{r}}\textrm{~{}or~{}}i<\theta_{\mathrm{t}},j\geq\theta_{\mathrm{r}},\\\
2,&\textrm{if~{}}i\geq\theta_{\mathrm{t}},j\geq\theta_{\mathrm{r}}.\end{array}\right.$
(59)

###### Proof.

See Appendix -J. ∎

##  V Finding the Optimal Thresholds

We have shown that the optimal policy for the average cost problem (21) is
threshold based. Thus, given the thresholds
$\theta_{\mathrm{t}},\theta_{\mathrm{r}}$, and $\theta(j),1\leq
j<\theta_{\mathrm{r}}$, a Markov chain can be obtained, as depicted in Fig. 4.
Denote by $\tilde{\mathcal{A}}=\\{(i,i)|1\leq
i\leq\theta_{\mathrm{r}}\\}\cup\\{(i,j)|1\leq
i\leq\theta_{\mathrm{t}},j=\theta_{\mathrm{r}}+k\theta_{\mathrm{t}}+i,k\geq
0\\}$. It contains all the states in the Markov chain. We have the following
lemma.

Figure 4: Markov chain under the threshold optimal policy.

######  Lemma 8.

Under the threshold policy (59), all the states in
$\mathcal{A}\setminus\tilde{\mathcal{A}}$ are transient.

###### Proof.

With all the possible actions 0, 1, and 2, the state
$(i,j)\in\mathcal{A}\setminus\tilde{\mathcal{A}}$ will transit to either
$(1,1)$, $(i+1,i+1)$ or $(N,j+1)$, where $N=1$ or $i+1$. Notice that to
transit to the state $(i+1,i+1)$, the action 1 is taken, which means
$i<\theta_{\mathrm{t}}\leq\theta_{\mathrm{r}}$ according to the threshold
policy. Thus, $(i+1,i+1)\in\tilde{\mathcal{A}}$. As
$(1,1)\in\tilde{\mathcal{A}}$, if $(i,j)$ transients to either $(1,1)$ or
$(i+1,i+1)$, the system state will transit within $\tilde{\mathcal{A}}$
afterwards. Otherwise, the AoIR will increase by 1. Repeating the process, the
state transition ends up either within $\tilde{\mathcal{A}}$, or with the AoIR
going to infinity. For both cases, $(i,j)$ will never be revisited. ∎

Based on Lemma 8 and the fact that the stationary probabilities of transient
states are all zero, to calculate the optimal average cost, we only need to
calculate the stationary distribution for the states in $\tilde{\mathcal{A}}$.
Thus, we have the following result.

######  Theorem 1.

The average AoIR and the average energy consumption for the problem (21) with
the threshold policy (59) can be expressed as

$\displaystyle\bar{\Delta}$
$\displaystyle=\frac{\theta_{\mathrm{t}}}{2}+\frac{\theta_{\mathrm{r}}(\theta_{\mathrm{r}}-\theta_{\mathrm{t}})(1-p^{\theta_{\mathrm{t}}})}{2(\theta_{\mathrm{r}}(1-p^{\theta_{\mathrm{t}}})+\theta_{\mathrm{t}}p^{\theta_{\mathrm{t}}})}+\frac{1}{1-p},$
(60) $\displaystyle\bar{E}$
$\displaystyle=\frac{1}{\theta_{\mathrm{r}}(1-p^{\theta_{\mathrm{t}}})+\theta_{\mathrm{t}}p^{\theta_{\mathrm{t}}}}\left(\frac{1-p^{\theta_{\mathrm{t}}}}{1-p}E_{\mathrm{t}}+E_{\mathrm{s}}\right).$
(61)

###### Proof.

See Appendix -K. ∎

Theorem 1 shows that the average cost is only relative to
$\theta_{\mathrm{t}}$ and $\theta_{\mathrm{r}}$. The reason is that the state
set related to the thresholds $\theta(j)$ can be expressed as
$\hat{\mathcal{A}}=\\{(i,j)|1\leq i<\theta_{\mathrm{t}},1\leq
j<\theta_{\mathrm{r}},i<j\\}$. Since
$\hat{\mathcal{A}}\subset\mathcal{A}\setminus\tilde{\mathcal{A}}$, all the
states in $\hat{\mathcal{A}}$ are transient, which do not contribute to the
infinite horizon average cost. Thus, the values of $\theta(j)$ in the optimal
policy can be arbitrarily set. For simplicity, a _two-thresholds_ optimal
policy can be obtained by setting
$\theta(1)=\cdots=\theta(\theta_{\mathrm{r}}-1)=1$, as summarized in the
following theorem.

######  Theorem 2.

There exists a two-thresholds optimal stationary policy for the average cost
problem (21) as follows

$\displaystyle\mu(i,j)=\left\\{\begin{array}[]{ll}0,&\textrm{if~{}}j<\theta_{\mathrm{r}},\\\
1,&\textrm{if~{}}i<\theta_{\mathrm{t}},j\geq\theta_{\mathrm{r}},\\\
2,&\textrm{if~{}}i\geq\theta_{\mathrm{t}},j\geq\theta_{\mathrm{r}}.\end{array}\right.$
(65)

It turns out that the two-thresholds policy is quite intuitive and easy to be
implemented. During transmission, it follows the truncated ARQ protocol [27].
That is, a packet is retransmitted after a channel failure until either a
successful transmission or the number of retransmissions reaches
$\theta_{\mathrm{t}}-1$. In the latter case, a new packet is generated and is
transmitted following the truncated ARQ protocol as well. The difference is
that after a successful transmission, the sensor turns to sleep mode until the
AoIR increases to $\theta_{\mathrm{r}}$. Then, another packet is generated and
the truncated ARQ protocol restarts.

Furthermore, the optimal threshold $\theta_{\mathrm{r}}$ can be expressed in
closed-form in terms of $\theta_{\mathrm{t}}$.

######  Theorem 3.

The optimal threshold $\theta_{\mathrm{r}}$ for the problem (21) satisfies

$\displaystyle\theta_{\mathrm{r}}\in\\{\max\\{\theta_{\mathrm{t}},\lceil\sqrt{A^{2}+\theta_{\mathrm{t}}A+2\omega
B}-A\rceil\\},\max\\{\theta_{\mathrm{t}},\lfloor\sqrt{A^{2}+\theta_{\mathrm{t}}A+2\omega
B}-A\rfloor\\}\\},$ (66)

where
$A=\frac{\theta_{\mathrm{t}}p^{\theta_{\mathrm{t}}}}{1-p^{\theta_{\mathrm{t}}}},B=\frac{1}{1-p}E_{\mathrm{t}}+\frac{1}{1-p^{\theta_{\mathrm{t}}}}E_{\mathrm{s}}$.

###### Proof.

Denote
$F(\theta_{\mathrm{t}},\theta_{\mathrm{r}})=\bar{\Delta}+\omega\bar{E}.$ We
have

$\frac{\partial
F}{\partial\theta_{\mathrm{r}}}=\frac{\theta_{\mathrm{r}}^{2}+2A\theta_{\mathrm{r}}-\theta_{\mathrm{t}}A-2\omega
B}{2(\theta_{\mathrm{r}}+A)^{2}}.$

The positive zero point is
$\theta_{\mathrm{r}}^{*}=\sqrt{A^{2}+\theta_{\mathrm{t}}A+2\omega B}-A$, and
$\frac{\partial F}{\partial\theta_{\mathrm{r}}}<0$ for
$0<\theta_{\mathrm{r}}<\theta_{\mathrm{r}}^{*}$, $\frac{\partial
F}{\partial\theta_{\mathrm{r}}}>0$ for
$\theta_{\mathrm{r}}>\theta_{\mathrm{r}}^{*}$. Therefore, to minimize $F$ with
$\theta_{\mathrm{r}}\in\\{1,2,\cdots\\}$ and
$\theta_{\mathrm{r}}\geq\theta_{\mathrm{t}}$, we have (66). ∎

The optimal thresholds are determined by the energy consumption model
parameters $E_{\mathrm{s}}$ and $E_{\mathrm{t}}$, the channel parameter $p$,
and the available energy condition implicitly indicated by $\omega$. Different
sensors may have different thresholds, although the threshold structure is the
same. Notice that [23, Lemma 2] is a special case of Theorem 3 when
$E_{\mathrm{s}}=0$. In this case, the action 2 is superior to the action 1 as
the former possibly attains a lower AoIR without additional energy cost.
Therefore, $\theta_{\mathrm{t}}=1$, i.e., only the actions 0 and 2 are
possibly taken.

Based on Theorems 1 and 3, the optimal thresholds $\theta_{\mathrm{r}}$ and
$\theta_{\mathrm{t}}$ to minimize $\bar{\Delta}+\omega\bar{E}$ can be found by
a line search over $\theta_{\mathrm{t}}$ and a comparison for the two values
of $\theta_{\mathrm{r}}$ as in (66). Furthermore, when
$\theta_{\mathrm{t}}\rightarrow\infty$, we have
$p^{\theta_{\mathrm{t}}}\rightarrow 0$, and hence,
$\sqrt{A^{2}+\theta_{\mathrm{t}}A+2\omega
B}-A\rightarrow\sqrt{2\omega((1-p)^{-1}E_{\mathrm{t}}+E_{\mathrm{s}})}$. Thus,
there exists a constant
$C>\sqrt{2\omega((1-p)^{-1}E_{\mathrm{t}}+E_{\mathrm{s}})}$ such that when
$\theta_{\mathrm{t}}\geq C$, we have $\theta_{\mathrm{r}}=\theta_{\mathrm{t}}$
and
$\bar{\Delta}+\omega\bar{E}\approx\frac{1}{1-p}+\frac{\theta_{\mathrm{t}}}{2}+\omega\frac{(1-p)^{-1}E_{\mathrm{t}}+E_{\mathrm{s}}}{\theta_{\mathrm{t}}}$.
As the average cost is non-decreasing over $\theta_{\mathrm{t}}\geq C$, the
line search in the range $\theta_{\mathrm{t}}\leq C$ is sufficient. In
practice, when $p<0.5$, $C\geq 50$ is sufficient for line search as
$p^{50}<10^{-16}$.

##  VI Numerical Results

In this section, numerical results are provided to verify our analytical
conclusions. Firstly, Fig. 5 shows the optimal policies for the average cost
problem (21) with different parameters. In Fig. 5(a), with $\omega=2$, the
optimal thresholds are $\theta_{\mathrm{t}}=1,\theta_{\mathrm{r}}=3$. With
$\omega=15$ as in Fig. 5(b), we have
$\theta_{\mathrm{t}}=3,\theta_{\mathrm{r}}=8$. The reason is that the
weighting factor $\omega$ indicates the relative importance of the energy
consumption over the AoI. As $\omega$ increases, the optimal policy tends to
be “lazy” to save energy. Therefore, larger thresholds are adopted to have
more chance to sleep. Comparing Fig. 5(b) with Fig. 5(c), we can see that as
$E_{\mathrm{t}}$ increases, $\theta_{\mathrm{t}}$ decreases but
$\theta_{\mathrm{r}}$ increases. The increase of $\theta_{\mathrm{r}}$ is
because the sensor tends to sleep to save energy as the relative importance of
energy increases. The decrease of $\theta_{\mathrm{t}}$ is because when the
sensor should transmit, transmitting a new packet is more preferred than
retransmission as the ratio between the transmit energy and the sensing energy
increases.

Figure 5: The optimal policies for the average cost problem (21) with
different parameters. (a) $p=0.2,E_{\mathrm{t}}=E_{\mathrm{s}}=1,\omega=2$;
(b) $p=0.2,E_{\mathrm{t}}=E_{\mathrm{s}}=1,\omega=15$; (c)
$p=0.2,E_{\mathrm{t}}=2,E_{\mathrm{s}}=1,\omega=15$.

The minimum weighted sum cost performance is depicted in Fig. 6. Firstly, it
is shown that the weighted sum cost is an increasing and concave function of
the weighting factor. Secondly, the weighted sum cost increases as $p$
increases which causes the increase of transmission failures. In this case,
both the average AoI and the average energy consumption may be larger due to
more retransmissions. Finally, when $E_{\mathrm{s}}$ increases, the weighted
sum cost increases as well because the total energy consumption increases.

Figure 6: The minimum weighted sum $\bar{\Delta}+\omega\bar{E}$ versus the
weighting factor $\omega$.

The impacts of the channel parameter $p$ and the energy model parameters
$E_{\mathrm{s}}$ and $E_{\mathrm{t}}$ on the energy-age tradeoff are shown in
Figs. 7 and 8, respectively. In these figures, we compare our proposed two-
thresholds policy with the single-threshold policy proposed in [23] and the
truncated ARQ policy proposed in [27]. In the single-threshold policy, the
sensor always senses and transmits a new packet when the AoIR exceeds the
optimal threshold, and sleeps otherwise. Retransmission action is not
included. In the truncated ARQ policy, the sensor transmits the same packet
until either it is successfully received or the number of retransmissions
reaches a threshold $M$. Then, a new packet is generated and transmitted.
Thus, sleep mode is not considered.

In Fig. 7, we set $E_{\mathrm{t}}=E_{\mathrm{s}}=1$. With the increase of $p$,
the tradeoff curve shifts towards upper right as the increase of channel
failures causes both larger age and larger energy consumption. We also find
that our policy performs better than the single-threshold policy. The reason
is that the latter does not take retransmission action which can reduce energy
cost when the sensing energy is large. In addition, the tradeoff range of our
policy is far more wider than the truncated ARQ policy. This is because the
truncated ARQ policy can only tradeoff age with energy by tuning $M$. While as
sleep action is introduced in our policy, the tradeoff is more flexible.

Figure 7: The energy-age tradeoff curve for different values of $p$.
$E_{\mathrm{t}}=E_{\mathrm{s}}=1$.

In Fig. 8, we set $p=0.3$ and the total energy
$E_{\mathrm{t}}+E_{\mathrm{s}}=2$ to see the impact of sensing energy and
transmit energy. It can be found that with the increase of the ratio
$E_{\mathrm{s}}/E_{\mathrm{t}}$, the tradeoff curve is shifted towards left
lower, meaning that our policy is more effective when the sensing energy
dominates the transmit energy. The single-threshold policy with any ratio
$E_{\mathrm{s}}/E_{\mathrm{t}}$ performs the same since the sensing action and
the transmit action are bonded together. It performs the same as our policy
with $E_{\mathrm{t}}=0,E_{\mathrm{s}}=2$, which validates the conclusion
presented after Theorem 3. Finally, similar to Fig. 7, the truncated ARQ
policy results in a narrow tradeoff range.

Figure 8: The energy-age tradeoff curve for different energy models. $p=0.3$.

##  VII Conclusion

In this paper, the tradeoff between AoI and energy consumption over an error-
prone channel considering sleep and retransmission has been studied. We proved
that there exists a threshold optimal stationary policy for the average cost
minimization problem. In addition, the minimum cost only rely on two
thresholds $\theta_{\mathrm{t}}$ and $\theta_{\mathrm{r}}$, and
$\theta_{\mathrm{r}}$ can be expressed in closed-form in terms of
$\theta_{\mathrm{t}}$. Thus, the optimal policy can be easily obtained by a
line search over $\theta_{\mathrm{t}}$, and a two-thresholds optimal policy
can be obtained. Then, we numerically illustrate the tradeoff between the
average AoI and the average energy consumption. Compared with the truncated
ARQ protocol, our optimal policy attains a tradeoff curve towards left lower,
and the tradeoff range is substantially expanded. Future work can exploit the
practical channel correlations by introducing channel training, and consider
transmit power control and data rate adaptation.

###  -A Proof of Proposition 1

Due to the optimality of the DP algorithm for a finite horizon problem, it can
be verified by induction that $J_{n}(x)$ is the optimal cost for the $n$-stage
discounted problem with initial state $x$, per-stage cost $g$ and terminal
cost 0, i.e.,

$\displaystyle
J_{n}(x)=\min_{\pi_{n}}J_{\pi_{n}}^{(n)}(x)=\min_{\pi_{n}}\mathbb{E}\left(\sum_{k=0}^{n-1}\alpha^{k}g(x_{k},\mu_{k}(x_{k}))\Bigg{|}x_{0}=x\right),$

where $\pi_{n}=\\{\mu_{0},\cdots,\mu_{n-1}\\}$.

Secondly, we follow the lines of proof of [35, Prop. 1.2.1] to show the
convergence of $J_{n}(x)$. For every positive integer $n$, initial state
$x_{0}=(i,j)\in\mathcal{A}$ and policy $\pi=\\{\mu_{0},\mu_{1},\cdots\\}$,
consider the “tail” cost after stage $n$, we have

$\displaystyle\left|J_{\alpha,\pi}(x_{0})-J_{\pi_{n}}^{(n)}(x_{0})\right|$
$\displaystyle=\left|\lim_{K\rightarrow\infty}\mathbb{E}\left(\sum_{k=n}^{K-1}\alpha^{k}g(x_{k},\mu_{k}(x_{k}))\right)\right|$
$\displaystyle\leq\lim_{K\rightarrow\infty}\sum_{k=n}^{K-1}\alpha^{k}\left(j+k+\omega(E_{\mathrm{s}}+E_{\mathrm{t}})\right)=\left(M(x_{0})+n\right)\frac{\alpha^{n}}{1-\alpha},$
(67)

where $\pi_{n}$ equals to the first $n$ stage policy of $\pi$,
$M(x_{0})=j+\omega(E_{\mathrm{s}}+E_{\mathrm{t}})+\frac{\alpha}{1-\alpha}$,
and the inequality holds as the AoIR grows at most linearly versus $k$.
Therefore, we have

$\displaystyle
J_{\alpha,\pi}(x_{0})-\left(M(x_{0})+n\right)\frac{\alpha^{n}}{1-\alpha}\leq
J_{\pi_{n}}^{(n)}(x_{0})\leq
J_{\alpha,\pi}(x_{0})+\left(M(x_{0})+n\right)\frac{\alpha^{n}}{1-\alpha}.$

By taking the minimum over $\pi_{n}$ and $\pi$, we have

$\displaystyle
J_{\alpha}(x_{0})-\left(M(x_{0})+n\right)\frac{\alpha^{n}}{1-\alpha}\leq
J_{n}(x_{0})\leq
J_{\alpha}(x_{0})+\left(M(x_{0})+n\right)\frac{\alpha^{n}}{1-\alpha}.$

By taking $n\rightarrow\infty$,
$\left(M(x_{0})+n\right)\frac{\alpha^{n}}{1-\alpha}\rightarrow 0$. Therefore,
we have $J_{\alpha}(x_{0})\leq\lim_{n\rightarrow\infty}J_{n}(x_{0})\leq
J_{\alpha}(x_{0})$, which means
$J_{\alpha}(x_{0})=\lim_{n\rightarrow\infty}J_{n}(x_{0}).$

Then, following the proofs of [35, Prop. 1.2.2] and [35, Prop. 1.2.3], we can
show that the optimal cost $J_{\alpha}(x_{0})$ satisfies the Bellman’s
Equation (27), and the optimal solution $\mu_{\alpha}$ for (27) forms the
optimal stationary policy.

###  -B Proof of Lemma 1

Firstly, we prove (28) by induction.

(a) It can be easily obtained that $J_{1}(i,j)=j,\forall(i,j)\in\mathcal{A}$.
Therefore, (28) holds for $n=1$.

(b) Suppose $J_{n}(i,j+1)-J_{n}(i,j)\geq 1$ holds for $n\leq k$. Thus,
$J_{k}(i,j+1)\geq J_{k}(i,j)$ for any $1\leq i\leq j$. We consider $n=k+1$.
Denote
$u_{k+1}^{*}=\arg\min_{u\in\mathcal{U}}\left[g(x,u)+\alpha\sum_{x^{\prime}\in\mathcal{A}}p_{x\rightarrow
x^{\prime}}(u)J_{k}(x^{\prime})\right]$. If $u_{k+1}^{*}=(0,0)$, we have

$\displaystyle J_{k+1}(i,j+1)=j+1+\alpha J_{k}(i+1,j+2)\geq j+1+\alpha
J_{k}(i+1,j+1)\geq 1+J_{k+1}(i,j),$

where the second inequality is due to the optimality of $J_{k+1}(i,j)$ over
all possible actions. Similarly, we can prove that the inequality
$J_{k+1}(i,j+1)-J_{k+1}(i,j)\geq 1$ holds for any $u_{k+1}^{*}\in\mathcal{U}$.
Therefore, (28) holds for any $n\geq 1$.

The inequality (29) can be proved in the same way. This completes the proof.

###  -C Proof of Proposition 2

The convergence of $\mu_{\beta_{m}}$ and the existence of the stationary
policy $\mu$ is given by [39, Lemma]. According to [39, Theorem], to prove
that $\mu$ is the optimal policy for the average cost minimization problem,
the following conditions should be satisfied:

1) $J_{\alpha}(x)$ is finite for every $x$ and $\alpha$.

2) There exists a nonnegative $N$ such that
$h_{\alpha}(x)=J_{\alpha}(x)-J_{\alpha}(\hat{x})\geq-N$ for all $x$ and
$\alpha$, where $\hat{x}$ is any fixed state.

3) There exists nonnegative $M_{x}$, such that $h_{\alpha}(x)\leq M_{x}$ for
every $x$ and $\alpha$. Moreover, for every $x$, there exists an action $u$
such that $\sum_{x^{\prime}}p_{x\rightarrow
x^{\prime}}(u)M_{x^{\prime}}<\infty$.

We verify the above conditions one by one.

_Validity of condition 1):_ Denote by $J_{\alpha,\pi}(x)$ the discounted cost
under the policy $\pi$. Due to the optimality of $J_{\alpha}(x)$, we have
$J_{\alpha}(x)\leq J_{\alpha,\pi}(x)<\infty$ for any $x$ and $\alpha$
according to (23).

_Validity of condition 2):_ By setting $\hat{x}=(1,1)$ and $N=0$, according to
Lemma 1, we have $J_{\alpha}(x)\geq J_{\alpha}(\hat{x}),\forall
x\in\mathcal{A}$. Therefore, we have
$h_{\alpha}(x)=J_{\alpha}(x)-J_{\alpha}(\hat{x})\geq 0.$

_Validity of condition 3):_ We set $\hat{x}=(1,1)$, define
$K_{\min}=\min\\{k:k\geq 1,x_{k}=(1,1)\\}$, and consider the policy
$\hat{\pi}=\\{\hat{\mu}_{0},\hat{\mu}_{1},\cdots\\}$ that always adopts the
action $(1,1)$ until the $K_{\min}$-th slot, and then is the same as the
optimal stationary policy $\mu$. Denote $G(x,\hat{x})$ as the expected sum
cost of the first passage from any state $x=(i,j)$ to $\hat{x}$ under policy
$\hat{\pi}$. Notice that $\mathrm{Pr}(K_{\min}=k)=(1-p)p^{k-1}$, and the cost
is fixed for a given $K_{\min}$. Then, $G(x,\hat{x})$ can be computed as

$\displaystyle G(x,\hat{x})$
$\displaystyle=\mathbb{E}\left(\sum_{k=0}^{K_{\min}\\!-\\!1}g(x_{k},\hat{\mu}_{k})\bigg{|}x_{0}=x,\hat{\pi}\right)=\sum_{k=1}^{\infty}(1-p)p^{k-1}\left(\sum_{m=0}^{k-1}\left(j+m+\omega(E_{\mathrm{s}}+E_{\mathrm{t}})\right)\right)$
$\displaystyle=\frac{j-\frac{1}{2}+\omega(E_{\mathrm{s}}+E_{\mathrm{t}})}{1-p}+\frac{1+p}{2(1-p)^{2}},$

Thus, we have

$\displaystyle J_{\alpha}(x)\leq$
$\displaystyle{~{}}\mathbb{E}\\!\left(\sum_{k=0}^{K_{\min}-1}\alpha^{k}g(x_{k},\hat{\mu}_{k}(x_{k}))\bigg{|}x_{0}\\!=\\!x,\hat{\pi}\right)\\!+\\!\lim_{K\rightarrow\infty}\mathbb{E}\\!\left(\sum_{k=K_{\min}}^{K}\alpha^{k}g(x_{k},\hat{\mu}_{k}(x_{k}))\bigg{|}x_{K_{\min}}\\!=\\!\hat{x},\hat{\pi}\right)$
$\displaystyle\leq$
$\displaystyle{~{}}\mathbb{E}\left(\sum_{k=0}^{K_{\min}-1}g(x_{k},\hat{\mu}_{k}(x_{k}))\bigg{|}x_{0}\\!=\\!x,\hat{\pi}\right)\\!+\\!\lim_{K\rightarrow\infty}\mathbb{E}\left(\sum_{k=0}^{K}\alpha^{k}g(x_{k},{\mu}(x_{k}))\bigg{|}x_{0}\\!=\\!\hat{x},{\mu}\right)$
$\displaystyle=$ $\displaystyle{~{}}G(x,\hat{x})\\!+\\!J_{\alpha}(\hat{x}).$

By setting $M_{x}=G(x,\hat{x})$, we have
$h_{\alpha}(x)=J_{\alpha}(x)-J_{\alpha}(\hat{x})\leq G(x,\hat{x})=M_{x}$ for
every $x$ and $\alpha$. In addition, by taking $u=(0,0)$ in state $x=(i,j)$,
we have $\sum_{x^{\prime}}p_{x\rightarrow
x^{\prime}}(u)M_{x^{\prime}}=M_{(i+1,j+1)}<\infty$.

In summary, all the assumptions in [39, Theorem] hold. This completes the
proof.

###  -D Proof of Lemma 2

We prove it by contradiction. Suppose for a certain state $x=(i,j)$ we have
$\mu_{\alpha}(x)=(1,0)$. Without loss of generality, we set $x_{0}=x$ and the
optimal action is $u_{0}=(1,0)$. Denote $N=\min\\{k:k>0,u_{k}\neq(0,0)\\}$ as
the stage where the first non-idle action is taken under the optimal policy.
Then, $u_{N}$ has three possible choices.

_Case 1:_ If $u_{N}=(1,0)$, consider the policy $\pi^{\prime}$ in which the
action $(0,0)$ is taken in stage 0, and the optimal policy is taken
afterwards, we have

$\displaystyle J_{\alpha}(i,j)$ $\displaystyle=(j+\omega
E_{\mathrm{s}})+\sum_{k=1}^{N-1}\alpha^{k}(j+k)+\alpha^{N}(j+N+\omega
E_{\mathrm{s}})+\alpha^{N+1}J_{\alpha}(1,j+N+1)$
$\displaystyle>\sum_{k=0}^{N-1}\alpha^{k}(j+k)+\alpha^{N}(j+N+\omega
E_{\mathrm{s}})+\alpha^{N+1}J_{\alpha}(1,j+N+1)=J_{\alpha,\pi^{\prime}}(i,j).$

_Case 2:_ If $u_{N}=(0,1)$, consider the policy $\pi^{\prime}$ in which the
action $(0,0)$ is taken in stages $k=0,1,\cdots,N-1$, the action $(1,1)$ is
taken in stage $N$, and the optimal policy is taken afterwards, we have

$\displaystyle J_{\alpha}(i,j)$ $\displaystyle=(j+\omega
E_{\mathrm{s}})+\sum_{k=1}^{N-1}\alpha^{k}(j+k)+\alpha^{N}(j+N+\omega
E_{\mathrm{t}})$
$\displaystyle\qquad\qquad+\alpha^{N+1}\left(pJ_{\alpha}(N+1,j+N+1)+(1-p)J_{\alpha}(N+1,N+1)\right).$
$\displaystyle>\sum_{k=0}^{N-1}\alpha^{k}(j\\!+\\!k)\\!+\\!\alpha^{N}(j\\!+\\!N\\!+\\!\omega
E_{\mathrm{s}}\\!+\\!\omega
E_{\mathrm{t}})\\!+\\!\alpha^{N+1}\left(pJ_{\alpha}(1,j\\!+\\!N\\!+\\!1)\\!+\\!(1\\!-\\!p)J_{\alpha}(1,1)\right)$
$\displaystyle=J_{\alpha,\pi^{\prime}}(i,j)$

as $J_{\alpha}(i,j)$ is nondecreasing versus $i$ and $j$ according to Lemma 1.

_Case 3:_ If $u_{N}=(1,1)$, consider the same policy $\pi^{\prime}$ as in case
2, we also have $J_{\alpha,\pi^{\prime}}(i,j)<J_{\alpha}(i,j)$ as the policy
$\pi^{\prime}$ reduces the cost in stage $k=0$ without impacting the future
costs.

In summary, we end up with a contradiction that $\mu_{\alpha}(x)=(1,0)$ is not
optimal. Therefore, the optimal policy must not contain the action $(1,0)$.

###  -E Proof of Lemma 3

We prove the lemma by induction.

(a) For $n=1$, (36) and (37) hold as $\mu_{1}(i,j)=0$ and $J_{1}(i,j)=j$ for
all $i\geq 1,j\geq 1$.

(b) Suppose (36) and (37) hold for $n\leq k$, we consider $n=k+1$. Firstly, we
prove $\mu_{k+1}(i,j)\in\\{0,2\\}$. Denote by

$\displaystyle A_{n}^{u-v}(i,j)$
$\displaystyle=Q_{n}(i,j,u)-Q_{n}(i,j,v),\quad n\geq 1,u,v\in\\{0,1,2\\}.$
(68)

If $i\geq i_{0}$, according to Lemma 1, we have

$\displaystyle A_{k+1}^{1-2}(i,j)$ $\displaystyle=\alpha
p\left(J_{k}(i\\!+\\!1,j\\!+\\!1)-J_{k}(1,j\\!+\\!1)\right)+\alpha\left(1-p\right)\left(J_{k}(i\\!+\\!1,i\\!+\\!1)-J_{k}(1,1)\right)-\omega
E_{\mathrm{s}}$
$\displaystyle\geq\alpha\left(1-p\right)\left(J_{k}(1,i+1)-J_{k}(1,1)\right)-\omega
E_{\mathrm{s}}>\alpha\left(1-p\right)i-\omega E_{\mathrm{s}}>0,$

which means $Q_{k+1}(i,j,1)>Q_{k+1}(i,j,2)$. Hence,
$\mu_{k+1}(i,j)\in\\{0,2\\}$. Similarly, if $j\leq i$,

$\displaystyle A_{k+1}^{0-1}(i,j)$
$\displaystyle=\alpha(1-p)(J_{k}(i+1,j+1)-J_{k}(i+1,i+1))-\omega
E_{\mathrm{t}}\leq-\omega E_{\mathrm{t}}<0.$

Thus, we also have $\mu_{k+1}(i,j)\in\\{0,2\\}$ if $i\geq j$.

Secondly, we prove $\mu_{k+1}(i,j)=\mu_{k+1}(i+1,j)$. As (37) holds for $n=k$,
we have

$\displaystyle A_{k+1}^{0-2}(i,j)$ $\displaystyle=\alpha J_{k}(i+1,j+1)-\alpha
pJ_{k}(1,j+1)-\alpha\left(1-p\right)J_{k}(1,1)-\omega E_{\mathrm{t}}-\omega
E_{\mathrm{s}}$ $\displaystyle=\alpha J_{k}(i+2,j+1)-\alpha
pJ_{k}(1,j+1)-\alpha\left(1-p\right)J_{k}(1,1)-\omega E_{\mathrm{t}}-\omega
E_{\mathrm{s}}$ $\displaystyle=A_{k+1}^{0-2}(i+1,j).$

Therefore, we have $\mu_{k+1}(i,j)=\mu_{k+1}(i+1,j)$. Thus, (36) holds for
$n=k+1$.

Next, we prove (37). As (36) holds for $n=k+1$, there are two possible cases.

If $\mu_{k+1}(i,j)=\mu_{k+1}(i+1,j)=2$, we have

$\displaystyle J_{k+1}(i,j)=j+\omega E_{\mathrm{t}}+\omega
E_{\mathrm{s}}+\alpha pJ_{k}(1,j+1)+\alpha(1-p)J_{k}(1,1)=J_{k+1}(i+1,j).$

If $\mu_{k+1}(i,j)=\mu_{k+1}(i+1,j)=0$, we have

$\displaystyle
J_{k+1}(i,j)-J_{k+1}(i+1,j)=\alpha\left(J_{k}(i+1,j+1)-J_{k}(i+2,j+1)\right)=0.$

Therefore, (37) holds for $n=k+1$. This completes the proof.

###  -F Proof of Lemma 4

We prove the lemma by induction.

(a) For $n=2$, $\mu_{2}(i,j)$ can be directly calculated as

$\displaystyle\mu_{2}(i,j)=\left\\{\begin{array}[]{ll}0,&\textrm{if~{}}i<i_{0},j<\Big{\lceil}\dfrac{\omega
E_{\mathrm{t}}}{\alpha(1-p)}\Big{\rceil}+i\textrm{~{}or~{}}i\geq
i_{0},j<j_{0},\\\ 1,&\textrm{if~{}}i<i_{0},j\geq\Big{\lceil}\dfrac{\omega
E_{\mathrm{t}}}{\alpha(1-p)}\Big{\rceil}+i,\\\ 2,&\textrm{if~{}}i\geq
i_{0},j\geq j_{0}.\end{array}\right.$

Then, it can be easily obtained that for $j\geq j_{0}$,
$J_{2}(i,j+1)-J_{2}(i,j)=1+\alpha p$. Hence, (40) and (41) hold for $n=2,j\geq
j_{0}$ with $i_{2}=i_{0}$.

(b) Suppose (40) and (41) hold for $n\leq k$, we consider $n\\!=\\!k\\!+\\!1$.
Based on Lemma 1, we have

$\displaystyle A_{k\\!+\\!1}^{0\\!-\\!2}(i,j)$ $\displaystyle=\alpha
p(J_{k}(i\\!+\\!1,j\\!+\\!1)\\!-\\!J_{k}(1,j\\!+\\!1))\\!+\\!\alpha(1\\!-\\!p)(J_{k}(i\\!+\\!1,j\\!+\\!1)\\!-\\!J_{k}(1,1))\\!-\\!\omega
E_{\mathrm{t}}\\!-\\!\omega E_{\mathrm{s}}$
$\displaystyle\geq\alpha(1\\!-\\!p)(J_{k}(1,j\\!+\\!1)\\!-\\!J_{k}(1,1))\\!-\\!\omega
E_{\mathrm{t}}\\!-\\!\omega E_{\mathrm{s}}\geq\alpha(1\\!-\\!p)j\\!-\\!\omega
E_{\mathrm{t}}\\!-\\!\omega E_{\mathrm{s}}>0$

if $j\geq j_{0}$, where $A_{k+1}^{0-2}(i,j)$ is defined in (68). Thus, we have
$Q_{n}(i,j,0)>Q_{n}(i,j,2)$, which means $\mu_{k+1}(i,j)\in\\{1,2\\}$. Then,
as (41) holds for $n=k$, we have

$\displaystyle
A_{k\\!+\\!1}^{1\\!-\\!2}(i,j)\\!-\\!A_{k\\!+\\!1}^{1\\!-\\!2}(i,j\\!+\\!1)=\alpha
p\left(J_{k}(i\\!+\\!1,j\\!+\\!1)\\!-\\!J_{k}(i\\!+\\!1,j\\!+\\!2)\\!-\\!\left(J_{k}(1,j\\!+\\!1)\\!-\\!J_{k}(1,j\\!+\\!2)\right)\right)=0.$

Therefore, $\mu_{k+1}(i,j)=\mu_{k+1}(i,j+1)$ for $j\geq j_{0}$. As

$\displaystyle A_{k+1}^{1-2}(i,j)=\alpha
p(J_{k}(i\\!+\\!1,j\\!+\\!1)\\!-\\!J_{k}(1,j\\!+\\!1))\\!+\\!\alpha(1\\!-\\!p)(J_{k}(i\\!+\\!1,i\\!+\\!1)\\!-\\!J_{k}(1,1))\\!-\\!\omega
E_{\mathrm{s}}$

is strictly increasing versus $i$, there exists $i_{k+1}$ so that
$A_{k+1}^{1-2}(i,j)<0$ for $i<i_{k+1}$ and $A_{k+1}^{1-2}(i,j)>0$ for $i\geq
i_{k+1}$. Therefore, (40) holds for $n=k+1$.

As (40) holds for $n=k+1$ and (41) holds for $n=k$, we have

$\displaystyle J_{k+1}(i,j+1)-J_{k+1}(i,j)=1+\alpha
p\left(J_{k}(N,j+2)-J_{k}(N,j+1)\right)=\dfrac{1-\left(\alpha
p\right)^{k+1}}{1-\alpha p},$

where $N=1$ if $\mu_{k+1}(i,j)=\mu_{k+1}(i,j+1)=2$ and $N=i+1$ if
$\mu_{k+1}(i,j)=\mu_{k+1}(i,j+1)=1$. Therefore, (41) holds for $n=k+1$. This
completes the proof.

###  -G Proof of Lemma 5

Firstly, we prove by induction that

$\displaystyle J_{n}(i,j+2)-J_{n}(i,j+1)\leq J_{n}(i,j+1)-J_{n}(i,j).$ (69)

(a) As $J_{1}(i,j)=j$, (69) holds for $n=1$.

(b) Suppose (69) holds for $n\leq k$, we consider $n=k+1$. If
$\mu_{k+1}(i,j+1)=0$, we have $J_{k+1}(i,j+1)=Q_{k+1}(i,j+1,0)$. Due to the
optimality of $J_{k+1}(i,j)$, we have

$\displaystyle{~{}}J_{k+1}(i,j+2)-J_{k+1}(i,j+1)-\left(J_{k+1}(i,j+1)-J_{k+1}(i,j)\right)$
$\displaystyle=$
$\displaystyle{~{}}J_{k+1}(i,j+2)-Q_{k+1}(i,j+1,0)-\left(Q_{k+1}(i,j+1,0)-J_{k+1}(i,j)\right)$
$\displaystyle\leq$
$\displaystyle{~{}}Q_{k+1}(i,j+2,0)-Q_{k+1}(i,j+1,0)-\left(Q_{k+1}(i,j+1,0)-Q_{k+1}(i,j,0)\right)$
$\displaystyle=$
$\displaystyle{~{}}\alpha\left(J_{k}(i+1,j+3)-J_{k}(i+1,j+2)-\left(J_{k}(i+1,j+2)-J_{k}(i+1,j+1)\right)\right)\leq
0.$

If $\mu_{k+1}(i,j+1)=1$ or $\mu_{k+1}(i,j+1)=2$, the inequality can be proved
in the same way. Therefore, (69) holds for all $n\geq 1$. As
$n\rightarrow\infty$, we have

$\displaystyle J_{\alpha}(i,j+2)-J_{\alpha}(i,j+1)\leq
J_{\alpha}(i,j+1)-J_{\alpha}(i,j).$ (70)

According to Corollary 1, we have $J_{\alpha}(i,j)=J_{\alpha}(i+1,j)$ for any
$j\leq i$. Therefore,

$\displaystyle D_{\alpha}(i+1)$
$\displaystyle=J_{\alpha}(i+2,i+2)-J_{\alpha}(i+1,i+1)=J_{\alpha}(i+2,i+2)-J_{\alpha}(i+2,i+1)$
$\displaystyle\leq
J_{\alpha}(i+2,i+1)-J_{\alpha}(i+2,i)=J_{\alpha}(i+1,i+1)-J_{\alpha}(i,i)=D_{\alpha}(i),$

where the inequality holds according to (70). Hence, (51) is proved.

According to (47), we have

$\displaystyle L_{\alpha}(i,j)-L_{\alpha}(i,j+1)$
$\displaystyle=J_{\alpha}(i+1,j)-J_{\alpha}(i,j)-\left(J_{\alpha}(i+1,j+1)-J_{\alpha}(i,j+1)\right)$
$\displaystyle=J_{\alpha}(i+1,j)-J_{\alpha}(i+1,j+1)-\left(J_{\alpha}(i,j)-J_{\alpha}(i,j+1)\right)=0.$

Thus, we have $L_{\alpha}(i,j)=L_{\alpha}(i,j+1)$.

Finally, we prove that $L_{\alpha}(i,j)<D_{\alpha}(i)$. Based on Lemma 1, we
have $D_{\alpha}(i)\geq 1$. Thus, for $i\geq i_{\alpha},j\geq j_{0}$, as
$\mu_{\alpha}(i,j)=2$, we have

$\displaystyle
L_{\alpha}(i,j)=Q_{\alpha}(i+1,j,2)-Q_{\alpha}(i,j,2)=0<D_{\alpha}(i).$

For $i\leq i_{\alpha},j\geq j_{0}$, we prove the inequality
$L_{\alpha}(i,j)<D_{\alpha}(i)$ by induction.

(a) The inequality holds for $i=i_{\alpha}$.

(b) Suppose the inequality holds for $i\geq k$, where $1<k\leq i_{\alpha}$,
and consider $i=k-1$. As $\mu_{\alpha}(k-1,j)=1$ according to (46), we have

$\displaystyle L_{\alpha}(k-1,j)$ $\displaystyle\leq
Q_{\alpha}(k,j,1)-Q_{\alpha}(k-1,j,1)=\alpha
pL_{\alpha}(k,j+1)+\alpha\left(1-p\right)D_{\alpha}(k)$ $\displaystyle<\alpha
pD_{\alpha}(k)+\alpha\left(1-p\right)D_{\alpha}(k)=\alpha
D_{\alpha}(k)<D_{\alpha}(k-1).$

Therefore, the inequality holds for $i=k-1$. This completes the proof.

###  -H Proof of Lemma 6

Based on Lemma 4 and Lemma 5, (46), (47) and (52) hold for $j\geq j_{0}$.

For $j_{\alpha}\leq j\leq j_{0}$, we prove by induction. Firstly, (46), (47)
and (52) hold for $j=j_{0}$. Secondly, suppose the equations hold for $j\geq
k$, where $j_{\alpha}<k\leq j_{0}$, and consider $j=k-1$. The proof of (46) is
divided into the following four steps.

(a) For $i\geq i_{0}$, by definition, we have $\mu_{\alpha}(i,k-1)=2$. Hence,
$J_{\alpha}(i,k)-J_{\alpha}(i,k-1)=1+\alpha
p(J_{\alpha}(1,k+1)-J_{\alpha}(1,k))=\frac{1}{1-\alpha p}$. In addition,
$L_{\alpha}(i,k-1)=L_{\alpha}(i,k)=0<D_{\alpha}(i)$. Therefore, the lemma
holds for $j=k-1$ when $i\geq i_{0}$.

(b) Denote by
$A_{\alpha}^{u-v}(i,j)=\lim_{n\rightarrow\infty}A_{n}^{u-v}(i,j).$ For
$i_{\alpha}\leq i\leq i_{0}$, since $\mu_{\alpha}(i,k)=2$, we have
$A_{\alpha}^{0-2}(i,k)>0$ and
$J_{\alpha}(i_{\alpha},k)=J_{\alpha}(i_{\alpha}+1,k)=\cdots=J_{\alpha}(i_{0},k)$.
As

$\displaystyle A_{\alpha}^{0-2}(i,j)=\alpha J_{\alpha}(i+1,j+1)-\alpha
pJ_{\alpha}(1,j+1)-\alpha\left(1-p\right)J_{\alpha}(1,1)-\omega
E_{\mathrm{t}}-\omega E_{\mathrm{s}},$ (71)

we have
$A_{\alpha}^{0-2}(i_{\alpha}-1,k-1)=A_{\alpha}^{0-2}(i_{\alpha},k-1)=\cdots=A_{\alpha}^{0-2}(i_{0},k-1)>0$.
Therefore, $\mu_{\alpha}(i,k-1)\in\\{1,2\\}$ for $i_{\alpha}-1\leq i\leq
i_{0}$.

(c) As (52) holds for $j\geq k$, we have

$\displaystyle A_{\alpha}^{1-2}(i,k-1)$ $\displaystyle=\alpha
p(J_{\alpha}(i+1,k)-J_{\alpha}(1,k))+\alpha(1-p)(J_{\alpha}(i+1,i+1)-J_{\alpha}(1,1))-\omega
E_{\mathrm{s}}$ $\displaystyle=\alpha
p\sum_{m=1}^{i}L_{\alpha}(m,k)+\alpha\left(1-p\right)\sum_{m=1}^{i}D_{\alpha}(m)-\omega
E_{\mathrm{s}}$ $\displaystyle=\alpha
p\sum_{m=1}^{i}L_{\alpha}(m,k+1)+\alpha\left(1-p\right)\sum_{m=1}^{i}D_{\alpha}(m)-\omega
E_{\mathrm{s}}=A_{\alpha}^{1-2}(i,k).$ (72)

As (46) holds for $j=k$, we have $A_{\alpha}^{1-2}(i,k)>0$ for $i\geq
i_{\alpha}$. Thus, $A_{\alpha}^{1-2}(i,k-1)>0$ and hence,
$\mu_{\alpha}(i,k-1)\in\\{0,2\\}$ for $i\geq i_{\alpha}$. Joint with (b), we
have $\mu_{\alpha}(i,k-1)=2$ for $i\geq i_{\alpha}$.

(d) For $i<i_{\alpha}$, we prove that $\mu_{\alpha}(i,k-1)=1$ by
contradiction. Suppose $\mu_{\alpha}(i,k-1)=1$ and $\mu_{\alpha}(i-1,k-1)=0$.
On one hand, we have

$\displaystyle L_{\alpha}(i-1,k-1)\leq
Q_{\alpha}(i,k-1,0)-Q_{\alpha}(i-1,k-1,0)=\alpha L_{\alpha}(i,k).$

On the other hand, as $L_{\alpha}(i,k)<D_{\alpha}(i)$,

$\displaystyle L_{\alpha}(i-1,k-1)$ $\displaystyle\geq
Q_{\alpha}(i,k-1,1)-Q_{\alpha}(i-1,k-1,1)=\alpha
pL_{\alpha}(i,k)+\alpha\left(1-p\right)D_{\alpha}(i)$ $\displaystyle>\alpha
pL_{\alpha}(i,k)+\alpha\left(1-p\right)L_{\alpha}(i,k)=\alpha
L_{\alpha}(i,k).$

Thus, we have $\alpha L_{\alpha}(i,k)<\alpha L_{\alpha}(i,k)$, which is a
contradiction. Therefore, if $\mu_{\alpha}(i,k-1)=1$, we must have
$\mu_{\alpha}(i-1,k-1)\neq 0$. According to (c), we have
$A_{\alpha}^{1-2}(i,k-1)<0$ for $i<i_{\alpha}$. Hence,
$\mu_{\alpha}(i,k-1)\in\\{0,1\\}$. Joint with (b), we have
$\mu_{\alpha}(i_{\alpha}-1,k-1)=1$. Hence, we have $\mu_{\alpha}(i,k-1)=1$ for
any $i<i_{\alpha}$. Thus, (46) holds for $j=k-1$.

As $\mu_{\alpha}(i,k-1)=\mu_{\alpha}(i,k)\in\\{1,2\\}$, we have

$\displaystyle J_{\alpha}(i,k)-J_{\alpha}(i,k-1)=1+\alpha
p\left(J_{\alpha}(N,k+1)-J_{\alpha}(N,k)\right)=\frac{1}{1-\alpha p},$

where $N=1$ if $\mu_{\alpha}(i,k)=2$ and $N=i+1$ if $\mu_{\alpha}(i,k)=1$.
Thus, (47) holds for $j=k-1$.

Similar to the proof of Lemma 5, (52) holds for $j=k-1$. This completes the
proof.

###  -I Proof of Lemma 7

We introduce an auxiliary equation

$\displaystyle L_{\alpha}(i,j)\leq L_{\alpha}(i,j+1)<D_{\alpha}(i),$ (73)

and prove (55) and (73) for $j<j_{\alpha}$ by induction.

(a) Firstly, we prove (55) and (73) hold for $j=j_{\alpha}-1$.

(a.1) According to the definition of $j_{\alpha}$, we have
$\mu_{\alpha}(i,j_{\alpha}-1)=0$ for $i\geq i_{0}$. Therefore,
$A_{\alpha}^{0-2}(i,j_{\alpha}-1)\leq A_{\alpha}^{0-2}(i_{0},j_{\alpha}-1)<0$
for $i<i_{0}$ as $A_{\alpha}^{0-2}(i,j)$ is non-decreasing in $i$ according to
(71). We have $\mu_{\alpha}(i,j_{\alpha}-1)\in\\{0,1\\},i<i_{0}$. According to
Lemma 6, (52) holds for $j=j_{\alpha}$. Then, we have
$A_{\alpha}^{1-2}(i,j_{\alpha}-1)=A_{\alpha}^{1-2}(i,j_{\alpha})$ according to
(72). For $i\geq i_{\alpha}$, as (46) holds, we have
$A_{\alpha}^{1-2}(i,j_{\alpha}-1)=A_{\alpha}^{1-2}(i,j_{\alpha})>0$, which
means $\mu_{\alpha}(i,j_{\alpha}-1)\neq 1$. Therefore, we have
$\mu_{\alpha}(i,j_{\alpha}-1)=0$ for any $i_{\alpha}\leq i<i_{0}$.

(a.2) As $L_{\alpha}(i,j_{\alpha})<D_{\alpha}(i)$, similar to subsection (d)
in the proof of Lemma 6, we have $\mu_{\alpha}(i-1,j_{\alpha}-1)\neq 0$ if
$\mu_{\alpha}(i,j_{\alpha}-1)=1$. As
$\mu_{\alpha}(i,j_{\alpha}-1)\in\\{0,1\\}$, we have
$\mu_{\alpha}(i-1,j_{\alpha}-1)=1$ if $\mu_{\alpha}(i,j_{\alpha}-1)=1$. Hence,
there exists $I_{\alpha}(j_{\alpha}-1)\leq i_{\alpha}$ so that (55) holds for
$j=j_{\alpha}-1$.

(a.3) As (55) holds for $j=j_{\alpha}-1$, if $\mu_{\alpha}(i,j_{\alpha}-1)=0$,
we have $\mu_{\alpha}(i+1,j_{\alpha}-1)=0$. Hence,

$\displaystyle L_{\alpha}(i,j_{\alpha}-1)=\alpha
L_{\alpha}(i+1,j_{\alpha})<\alpha
pL_{\alpha}(i+1,j_{\alpha})+\alpha\left(1-p\right)D_{\alpha}(i+1)$

as $L_{\alpha}(i,j_{\alpha})<D_{\alpha}(i)$. If
$\mu_{\alpha}(i,j_{\alpha}-1)=1$, as $J_{\alpha}(i,j)\leq Q_{\alpha}(i,j,1)$,
we have

$\displaystyle L_{\alpha}(i,j_{\alpha}\\!-\\!1)\leq
Q_{\alpha}(i+1,j_{\alpha}\\!-\\!1,1)-Q_{\alpha}(i,j_{\alpha}\\!-\\!1,1)=\alpha
pL_{\alpha}(i+1,j_{\alpha})+\alpha\left(1-p\right)D_{\alpha}(i+1).$

In both cases, we have

$\displaystyle L_{\alpha}(i,j_{\alpha}-1)$ $\displaystyle\leq\alpha
pL_{\alpha}(i+1,j_{\alpha})+\alpha\left(1-p\right)D_{\alpha}(i+1)$
$\displaystyle=\alpha
pL_{\alpha}(i+1,j_{\alpha}+1)+\alpha\left(1-p\right)D_{\alpha}(i+1)=L_{\alpha}(i,j_{\alpha})$

for $i<i_{\alpha}-1$ as $L_{\alpha}(i,j_{\alpha})=L_{\alpha}(i,j_{\alpha}+1)$
and $\mu_{\alpha}(i+1,j_{\alpha})=\mu_{\alpha}(i,j_{\alpha})=1$ based on Lemma
6.

For $i\geq i_{\alpha}$,
$L_{\alpha}(i,j_{\alpha}-1)=\alpha\left(J_{\alpha}(i+2,j_{\alpha})-J_{\alpha}(i+1,j_{\alpha})\right)=0$
as $\mu_{\alpha}(i,j_{\alpha}-1)=0$ and $\mu_{\alpha}(i,j_{\alpha})=2$.
Similarly, $L_{\alpha}(i_{\alpha}-1,j_{\alpha}-1)=0$ if
$\mu_{\alpha}(i_{\alpha}-1,j_{\alpha}-1)=0$. If
$\mu_{\alpha}(i_{\alpha}-1,j_{\alpha}-1)=1$,

$\displaystyle
J_{\alpha}(i_{\alpha}\\!-\\!1,j_{\alpha})\\!-\\!J_{\alpha}(i_{\alpha}\\!-\\!1,j_{\alpha}\\!-\\!1)$
$\displaystyle=Q_{\alpha}(i_{\alpha}-1,j_{\alpha},1)-Q_{\alpha}(i_{\alpha}-1,j_{\alpha}-1,1)$
$\displaystyle=1+\alpha
p(J_{\alpha}(i_{\alpha},j_{\alpha}+1)-J_{\alpha}(i_{\alpha},j_{\alpha}))$
$\displaystyle=1+\alpha
p(J_{\alpha}(1,j_{\alpha}+1)-J_{\alpha}(1,j_{\alpha}))$
$\displaystyle=Q_{\alpha}(i_{\alpha},j_{\alpha},2)\\!-\\!Q_{\alpha}(i_{\alpha},j_{\alpha}\\!-\\!1,2)$
$\displaystyle\leq
J_{\alpha}(i_{\alpha},j_{\alpha})\\!-\\!J_{\alpha}(i_{\alpha},j_{\alpha}\\!-\\!1)$

as (47) holds for $j\geq j_{\alpha}$. Therefore,
$L_{\alpha}(i_{\alpha}-1,j_{\alpha}-1)\leq
L_{\alpha}(i_{\alpha}-1,j_{\alpha})$. Hence, we have
$L_{\alpha}(i,j_{\alpha}-1)\leq L_{\alpha}(i,j_{\alpha})$ for all $i$.
According to Lemma 6, we have $L_{\alpha}(i,j_{\alpha})<D_{\alpha}(i)$. Thus,
(73) holds for $j=j_{\alpha}-1$.

(b) Suppose (55) and (73) hold for $j\geq k$, where $1<k<j_{\alpha}$ and
$I_{\alpha}(k)\leq I_{\alpha}(k+1)\leq\cdots\leq i_{\alpha}$, consider
$j=k-1$.

(b.1) As $\mu_{\alpha}(i,k)=0$ for $i\geq I_{\alpha}(k)$, as
$A_{\alpha}^{0-1}(i,j)=\alpha(1-p)(J_{\alpha}(i+1,j+1)-J_{\alpha}(i+1,i+1))-\omega
E_{\mathrm{t}}$ increases with $j$,we have
$A_{\alpha}^{0-1}(i,k-1)<A_{\alpha}^{0-1}(i,k)<0$. Thus,
$\mu_{\alpha}(i,k-1)\in\\{0,2\\}$ for $i\geq I_{\alpha}(k)$. As (73) holds for
$j=k$, we have

$\displaystyle A_{\alpha}^{0\\!-\\!2}(i,k\\!-\\!1)$ $\displaystyle=\alpha
p\sum_{m=1}^{i}L_{\alpha}(m,k)\\!+\\!\alpha\left(1\\!-\\!p\right)\left(J_{\alpha}(i\\!+\\!1,k)\\!-\\!J_{\alpha}(1,1)\right)\\!-\\!\omega
E_{\mathrm{t}}\\!-\\!\omega E_{\mathrm{s}}$ $\displaystyle\leq\alpha
p\sum_{m=1}^{i}L_{\alpha}(m,k\\!+\\!1)\\!+\\!\alpha\left(1\\!-\\!p\right)\left(J_{\alpha}(i\\!+\\!1,k\\!+\\!1)\\!-\\!J_{\alpha}(1,1)\right)\\!-\\!\omega
E_{\mathrm{t}}\\!-\\!\omega E_{\mathrm{s}}=A_{\alpha}^{0\\!-\\!2}(i,k),$

As (55) holds for $j=k$, we have $A_{\alpha}^{0-2}(i,k-1)\leq
A_{\alpha}^{0-2}(i,k)<0$. Hence, we have $\mu_{\alpha}(i,k-1)=0$ for $i\geq
I_{\alpha}(k)$. In addition, as $A_{\alpha}^{0-2}(i,j)$ in non-decreasing in
$i$, we have $A_{\alpha}^{0-2}(i,k-1)\leq
A_{\alpha}^{0-2}(I_{\alpha}(k),k-1)<0$ for $i<I_{\alpha}(k)$. Thus,
$\mu_{\alpha}(i,k-1)\in\\{0,1\\}$ for $i<I_{\alpha}(k)$.

(b.2) Similar to (a.2), we have $\mu_{\alpha}(i-1,k-1)\neq 0$ if
$\mu_{\alpha}(i,k-1)=1$ as $L_{\alpha}(i,k)<D_{\alpha}(i)$. Thus, according to
(b.1), there exists $I_{\alpha}(k-1)\leq I_{\alpha}(k)$ so that (55) holds.

(b.3) We now prove (73) for $j=k-1$. By assumption, we have
$L_{\alpha}(i,k)<D_{\alpha}(i)$. Then, we prove $L_{\alpha}(i,k-1)\leq
L_{\alpha}(i,k)$ for all three cases.

  1. I.

If $\mu_{\alpha}(i,k)=\mu_{\alpha}(i+1,k)=0$, since $I_{\alpha}(i,k-1)\leq
I_{\alpha}(i,k)$, we have $\mu_{\alpha}(i,k-1)=\mu_{\alpha}(i+1,k-1)=0$. As
(73) holds for $j=k$, we have

$\displaystyle L_{\alpha}(i,k-1)=\alpha L_{\alpha}(i+1,k)\leq\alpha
L_{\alpha}(i+1,k+1)=L_{\alpha}(i,k).$

  2. II.

If $\mu_{\alpha}(i,k)=\mu_{\alpha}(i+1,k)=1$, there are two possible cases.

    1. i.

$\mu_{\alpha}(i,k-1)=\mu_{\alpha}(i+1,k-1)=0$, we have

$\displaystyle L_{\alpha}(i,k-1)=\alpha L_{\alpha}(i+1,k)<\alpha
pL_{\alpha}(i+1,k)+\alpha\left(1-p\right)D_{\alpha}(i+1).$

    2. ii.

$\mu_{\alpha}(i,k-1)=1,\mu_{\alpha}(i+1,k-1)\in\\{0,1\\}$, as
$J_{\alpha}(i,j)\leq Q_{\alpha}(i,j,1)$, we have

$\displaystyle L_{\alpha}(i,k\\!-\\!1)\leq
Q_{\alpha}(i\\!+\\!1,k\\!-\\!1,1)\\!-\\!Q_{\alpha}(i,k\\!-\\!1,1)=\alpha
pL_{\alpha}(i\\!+\\!1,k)\\!+\\!\alpha\left(1\\!-\\!p\right)D_{\alpha}(i\\!+\\!1).$

In both cases, since $L_{\alpha}(i,k)\leq L_{\alpha}(i,k+1)$, we have

$\displaystyle L_{\alpha}(i,k-1)\leq\alpha
pL_{\alpha}(i+1,k+1)+\alpha\left(1-p\right)D_{\alpha}(i+1)=L_{\alpha}(i,k).$

  3. III.

$\mu_{\alpha}(i,k)=1,\mu_{\alpha}(i+1,k)=0$. We have $\mu_{\alpha}(i+1,k-1)=0$
as $I_{\alpha}(k-1)\leq I_{\alpha}(k)$. Thus, $\mu_{\alpha}(i,k-1)$ has two
possible values.

    1. i.

$\mu_{\alpha}(i,k-1)=0$, due to the optimality of $J_{\alpha}(i,j)$, we have

$\displaystyle L_{\alpha}(i,k)$ $\displaystyle\geq
Q_{\alpha}(i+1,k,0)-Q_{\alpha}(i,k,0)=\alpha L_{\alpha}(i+1,k+1)$
$\displaystyle\geq\alpha
L_{\alpha}(i+1,k)=Q_{\alpha}(i+1,k-1,0)-Q_{\alpha}(i,k-1,0)$
$\displaystyle=L_{\alpha}(i,k-1).$

    2. ii.

$\mu_{\alpha}(i,k-1)=1$, we have

$\displaystyle{~{}}L_{\alpha}(i,k)-L_{\alpha}(i,k-1)$ $\displaystyle=$
$\displaystyle{~{}}Q_{\alpha}(i+1,k,0)-Q_{\alpha}(i,k,1)-\left(Q_{\alpha}(i+1,k-1,0)-Q_{\alpha}(i,k-1,1)\right)$
$\displaystyle=$
$\displaystyle{~{}}\alpha\left(J_{\alpha}(i+2,k+1)-J_{\alpha}(i+2,k)\right)-\alpha
p\left(J_{\alpha}(i+1,k+1)-J_{\alpha}(i+1,k)\right)$ $\displaystyle>$
$\displaystyle{~{}}\alpha\left(J_{\alpha}(i+2,k+1)-J_{\alpha}(i+2,k)-J_{\alpha}(i+1,k+1)+J_{\alpha}(i+1,k)\right)$
$\displaystyle=$
$\displaystyle{~{}}\alpha\left(L_{\alpha}(i+1,k+1)-L_{\alpha}(i+1,k)\right)\geq
0.$

For all possible cases, we proved that (73) hold for $j=k-1$. This completes
the proof.

###  -J Proof of Proposition 3

Firstly, according to Lemma 6 and Lemma 7, the optimal policy for the problem
(22) with the extended state set $\mathcal{A}_{\mathrm{ext}}$ is

$\displaystyle\mu_{\alpha}(i,j)=\left\\{\begin{array}[]{ll}0,&\textrm{if~{}}i\geq
I_{\alpha}(j),j<j_{\alpha},\\\
1,&\textrm{if~{}}i<I_{\alpha}(j),j<j_{\alpha}\textrm{~{}or~{}}i<i_{\alpha},j\geq
j_{\alpha},\\\ 2,&\textrm{if~{}}i\geq i_{\alpha},j\geq
j_{\alpha},\end{array}\right.$ (77)

where $I_{\alpha}(1)\leq I_{\alpha}(2)\leq\cdots\leq
I_{\alpha}(j_{\alpha}-1)\leq i_{\alpha}$. Furthermore, as
$A_{\alpha}^{0-1}(i,i)=-\omega E_{\mathrm{t}}<0$, we have
$\mu_{\alpha}(i,i)\in\\{0,2\\}$ for all $i\geq 1$. Hence, we have
$i_{\alpha}\leq j_{\alpha}$. Therefore, the optimal policy for the problem
(22) with state set $\mathcal{A}$ is the same as (77).

Then, we consider the average cost problem (21). Note that there must exist
some state $(i^{\prime},j^{\prime})$ such that $\mu(i^{\prime},j^{\prime})=2$
since otherwise, the average cost is infinity as the AoIR grows to infinity
with probability 1, which is obviously not optimal. According to Proposition
2, there is a sequence of discount factors $\\{\beta_{n}\\}$ such that
$\mu_{\beta_{n}}(i,j)\rightarrow\mu(i,j)$. Then, there is an integer
$N^{\prime}$ such that
$\mu_{\beta_{n}}(i^{\prime},j^{\prime})=\mu(i^{\prime},j^{\prime})=2$ for all
$n\geq N^{\prime}$. Since $\mu_{\beta_{n}}(i,j)$ is a threshold policy as in
(77), we have $\mu_{\beta_{n}}(i,j)=2$ for all $i\geq i^{\prime},j\geq
j^{\prime}$ and $n\geq N^{\prime}$. Therefore, $\mu(i,j)=2$ for all $i\geq
i^{\prime},j\geq j^{\prime}$.

For each state $(i,j)\in\mathcal{A}^{\prime}=\\{(i,j)\in\mathcal{A}|j\leq
j^{\prime}\\}$, there exists an integer $N(i,j)$ such that
$\mu_{\beta_{n}}(i,j)=\mu(i,j)$ for all $n\geq N(i,j)$. As
$\mathcal{A}^{\prime}$ is finite, by setting
$N_{\max}=\max_{(i,j)\in\mathcal{A}^{\prime}}N(i,j)$, we have for any $n\geq
N_{\max}$, $\mu_{\beta_{n}}(i,j)=\mu(i,j)$ for all
$(i,j)\in\mathcal{A}^{\prime}$. As $\mu_{\beta_{n}}(i^{\prime},j^{\prime})=2$,
we have $j_{\beta_{n}}\leq j^{\prime}$. Therefore, there exist
$\theta(1)\leq\cdots\leq\theta(\theta_{\mathrm{r}})\leq\theta_{\mathrm{t}}\leq\theta_{\mathrm{r}}\leq
j^{\prime}$ such that $\mu(i,j)$ is expressed as (59) for
$(i,j)\in\mathcal{A}^{\prime}$.

According to the above, for $n\geq N_{\max}$, we have
$\mu_{\beta_{n}}(i,j^{\prime})=\mu(i,j^{\prime})=1$ for
$i<\theta_{\mathrm{t}}$ and
$\mu_{\beta_{n}}(i,j^{\prime})=\mu(i,j^{\prime})=2$ for
$i\geq\theta_{\mathrm{t}}$. As $\mu_{\beta_{n}}(i,j)$ is a threshold policy,
we have $\mu_{\beta_{n}}(i,j)=1$ for all $i<\theta_{\mathrm{t}},j\geq
j^{\prime}$ and $\mu_{\beta_{n}}(i,j)=2$ for all
$i\geq\theta_{\mathrm{t}},j\geq j^{\prime}$. Therefore, $\mu(i,j)=1$ for all
$i<\theta_{\mathrm{t}},j\geq j^{\prime}$ and $\mu(i,j)=2$ for all
$i\geq\theta_{\mathrm{t}},j\geq j^{\prime}$.

In summary, (59) holds for all $(i,j)\in\mathcal{A}$. This completes the
proof.

###  -K Proof of Theorem 1

As the second element of the state $(i,j)\in\tilde{\mathcal{A}}$ is unique, we
can re-index the state $(i,j)$ by $j$ for convenience. The state transition
probability from $j$ to $k$ can be expressed as

$\displaystyle
p_{jk}=\left\\{\begin{array}[]{ll}1,&\textrm{if~{}}k=j+1\textrm{~{}and~{}}1<j<\theta_{\mathrm{r}},\\\
p,&\textrm{if~{}}k=j+1\textrm{~{}and~{}}j\geq\theta_{\mathrm{r}},\\\
1-p,&\textrm{if~{}}j=\theta_{\mathrm{r}}+m\theta_{\mathrm{t}}+k-1\textrm{~{}and~{}}m\geq
0,1\leq k\leq\theta_{\mathrm{t}},\\\ 0,&\textrm{else}.\end{array}\right.$

By solving $\pi=\pi\mathbf{P}$, where $\pi=(\pi_{1},\pi_{2},\cdots)$ with
$\pi_{j}$ denoting the stationary probability of the $j$-th state, and
$\mathbf{P}$ is the state transition matrix with elements $p_{jk},\forall
j\geq 1,k\geq 1$, we have

$\displaystyle\pi_{j}=\left\\{\begin{array}[]{ll}\frac{1-p^{j}}{1-p^{\theta_{\mathrm{t}}}}\pi_{0},&1\leq
j\leq\theta_{\mathrm{t}},\\\
\pi_{0},&\theta_{\mathrm{t}}<j\leq\theta_{\mathrm{r}},\\\
p^{j-\theta_{\mathrm{r}}}\pi_{0},&j>\theta_{\mathrm{r}},\end{array}\right.$
(81)

where
$\pi_{0}=\dfrac{1-p^{\theta_{\mathrm{t}}}}{\theta_{\mathrm{r}}(1-p^{\theta_{\mathrm{t}}})+\theta_{\mathrm{t}}p^{\theta_{\mathrm{t}}}}$.
Then, the average AoIR and the average energy consumption can be calculated as

$\displaystyle\bar{\Delta}$
$\displaystyle=\sum_{j=1}^{\infty}j\pi_{j}+\frac{1}{2},$ (82)
$\displaystyle\bar{E}$
$\displaystyle=\sum_{m=0}^{\infty}(E_{\mathrm{t}}+E_{\mathrm{s}})\pi_{\theta_{\mathrm{r}}+m\theta_{\mathrm{t}}}+\sum_{m=0}^{\infty}\sum_{n=1}^{\theta_{\mathrm{t}}-1}E_{\mathrm{t}}\pi_{\theta_{\mathrm{r}}+m\theta_{\mathrm{t}}+n}.$
(83)

Substituting (81) into (82) and (83), we can obtain (60) and (61). This
completes the proof.

## References

  * [1] M. A. Abd-Elmagid, N. Pappas, and H. S. Dhillon, “On the role of age of information in the internet of things,” _IEEE Commun. Mag._ , vol. 57, no. 12, pp. 72–77, Dec. 2019.
  * [2] S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should one update?” in _IEEE INFOCOM_ , Mar. 2012, pp. 2731–2735.
  * [3] R. D. Yates, “Lazy is timely: Status updates by an energy harvesting source,” in _IEEE Int. Symp. Inf. Theory (ISIT)_ , Jun. 2015, pp. 3008–3012.
  * [4] Y. Sun, E. Uysal-Biyikoglu, R. D. Yates, C. E. Koksal, and N. B. Shroff, “Update or wait: How to keep your data fresh,” _IEEE Trans. Inf. Theory_ , vol. 63, no. 11, pp. 7492–7508, Nov. 2017.
  * [5] B. T. Bacinoglu, E. T. Ceran, and E. Uysal-Biyikoglu, “Age of information under energy replenishment constraints,” in _Inf. Theory and Appl. Workshop (ITA)_ , Feb. 2015, pp. 25–31.
  * [6] B. T. Bacinoglu and E. Uysal-Biyikoglu, “Scheduling status updates to minimize age of information with an energy harvesting sensor,” in _IEEE Int. Symp. Inf. Theory (ISIT)_ , Jun. 2017, pp. 1122–1126.
  * [7] B. T. Bacinoglu, Y. Sun, E. Uysal, and V. Mutlu, “Optimal status updating with a finite-battery energy harvesting source,” _Journal of Communications and Networks_ , vol. 21, no. 3, Jun. 2019.
  * [8] A. Arafa, J. Yang, S. Ulukus, and H. V. Poor, “Age-minimal transmission for energy harvesting sensors with finite batteries: Online policies,” _IEEE Trans. Inf. Theory_ , vol. 66, no. 1, pp. 534–556, Jan. 2020.
  * [9] A. Arafa and S. Ulukus, “Age minimization in energy harvesting communications: Energy-controlled delays,” in _Asilomar Conf. Signals, Systems, and Computers_ , Oct. 2017, pp. 1801–1805.
  * [10] S. Farazi, A. G. Klein, and D. R. Brown, “Age of information in energy harvesting status update systems: When to preempt in service?” in _IEEE Int. Symp. Inf. Theory (ISIT)_ , Jun. 2018, pp. 2436–2440.
  * [11] ——, “Average age of information for status update systems with an energy harvesting server,” in _IEEE Conf. Computer Commun. Workshops (INFOCOM WKSHPS)_ , Apr. 2018, pp. 112–117.
  * [12] E. T. Ceran, D. Gündüz, and A. György, “Reinforcement learning to minimize age of information with an energy harvesting sensor with harq and sensing cost,” in _IEEE Conf. Computer Commun. Workshops (INFOCOM WKSHPS)_ , May 2019, pp. 656–661.
  * [13] M. A. Abd-Elmagid, H. S. Dhillon, and N. Pappas, “A reinforcement learning framework for optimizing age of information in RF-powered communication systems,” _IEEE Trans. Commun._ , vol. 68, no. 8, pp. 4747–4760, Aug. 2020.
  * [14] ——, “Aoi-optimal joint sampling and updating for wireless powered communication systems,” _IEEE Trans. Veh. Techn._ , vol. 69, no. 11, pp. 14 110–14 115, Nov. 2020.
  * [15] O. Ozel, “Timely status updating through intermittent sensing and transmission,” in _IEEE Int. Symp. Inf. Theory (ISIT)_ , Jun. 2020, pp. 1788–1793.
  * [16] R. D. Yates, E. Najm, E. Soljanin, and J. Zhong, “Timely updates over an erasure channel,” in _IEEE Int. Symp. Inf. Theory (ISIT)_ , Jun. 2017, pp. 316–320.
  * [17] A. Arafa, J. Yang, S. Ulukus, and H. V. Poor, “Online timely status updates with erasures for energy harvesting sensors,” in _Annual Allerton Conf. Commun., Control, and Computing (Allerton)_ , Oct. 2018, pp. 966–972.
  * [18] K. Chen and L. Huang, “Age-of-information in the presence of error,” in _IEEE Int. Symp. Inf. Theory (ISIT)_ , Jul. 2016, pp. 2579–2583.
  * [19] E. Najm, R. Yates, and E. Soljanin, “Status updates through M/G/1/1 queues with HARQ,” in _IEEE Int. Symp. Inf. Theory (ISIT)_ , Jun. 2017, pp. 131–135.
  * [20] P. Parag, A. Taghavi, and J. Chamberland, “On real-time status updates over symbol erasure channels,” in _IEEE Wireless Commun. Netw. Conf. (WCNC)_ , Mar. 2017, pp. 1–6.
  * [21] H. Sac, T. Bacinoglu, E. Uysal-Biyikoglu, and G. Durisi, “Age-optimal channel coding blocklength for an M/G/1 queue with HARQ,” in _IEEE Int. Workshop on Signal Processing Advances in Wireless Communications (SPAWC)_ , Jun. 2018, pp. 1–5.
  * [22] A. Arafa, K. Banawan, K. G. Seddik, and H. V. Poor, “On timely channel coding with hybrid ARQ,” in _IEEE Global Commun. Conf. (GLOBECOM)_ , Dec. 2019, pp. 1–6.
  * [23] E. T. Ceran, D. Gündüz, and A. György, “Average age of information with hybrid ARQ under a resource constraint,” _IEEE Trans. Wireless Commun._ , vol. 18, no. 3, pp. 1900–1913, Mar. 2019.
  * [24] D. Li, S. Wu, Y. Wang, J. Jiao, and Q. Zhang, “Age-optimal HARQ design for freshness-critical satellite-IoT systems,” _IEEE Internet of Things Journal_ , vol. 7, no. 3, pp. 2066–2076, Mar. 2020.
  * [25] K. Huang, W. Liu, M. Shirvanimoghaddam, Y. Li, and B. Vucetic, “Real-time remote estimation with hybrid ARQ in wireless networked control,” _IEEE Trans. Wireless Commun._ , vol. 19, no. 5, pp. 3490–3504, May 2020.
  * [26] W. Liu, X. Zhou, S. Durrani, H. Mehrpouyan, and S. D. Blostein, “Energy harvesting wireless sensor networks: Delay analysis considering energy costs of sensing and transmission,” _IEEE Trans. Wireless Commun._ , vol. 15, no. 7, pp. 4635–4650, Jul. 2016.
  * [27] J. Gong, X. Chen, and X. Ma, “Energy-age tradeoff in status update communication systems with retransmission,” in _IEEE Global Communcations Conference_ , Dec. 2018, pp. 1–6.
  * [28] H. Huang, D. Qiao, and M. C. Gursoy, “Age-energy tradeoff in fading channels with packet-based transmissions,” in _IEEE Infocom Workshop on AoI_ , Jul. 2020, pp. 1–6.
  * [29] M. Xie, Q. Wang, J. Gong, and X. Ma, “Age and energy analysis for LDPC coded status update with and without ARQ,” _IEEE Internet of Things Journal_ , vol. 7, no. 10, pp. 10 388–10 400, Oct. 2020.
  * [30] Y. Gu, H. Chen, Y. Zhou, Y. Li, and B. Vucetic, “Timely status update in internet of things monitoring systems: An age-energy tradeoff,” _IEEE Internet of Things Journal_ , vol. 6, no. 3, Jun. 2019.
  * [31] S. Nath, J. Wu, and J. Yang, “Optimum energy efficiency and age-of-information tradeoff in multicast scheduling,” in _IEEE Int. Conf. Commun. (ICC)_ , 2018, pp. 1–6.
  * [32] J. Wu, S. Zhou, and Z. Niu, “Traffic-aware base station sleeping control and power matching for energy-delay tradeoffs in green cellular networks,” _IEEE Trans. Wireless Commun._ , vol. 12, no. 8, pp. 4196–4209, Aug. 2013\.
  * [33] Z. Niu, X. Guo, S. Zhou, and P. R. Kumar, “Characterizing energy-delay tradeoff in hyper-cellular networks with base station sleeping control,” _IEEE J. Sel. Areas Commun._ , vol. 33, no. 4, pp. 641–650, Apr. 2015.
  * [34] J. Wu, Y. Bao, G. Miao, S. Zhou, and Z. Niu, “Base-station sleeping control and power matching for energy-delay tradeoffs with bursty traffic,” _IEEE Trans. Veh. Technol._ , vol. 65, no. 5, pp. 3657–3675, May 2016.
  * [35] D. P. Bertsekas, _Dynamic programming and optimal control, Volume II,_3rd edition__. Athena Scientific Belmont, MA, 2005.
  * [36] Y. P. Hsu, E. Modiano, and L. Duan, “Scheduling algorithms for minimizing age of information in wireless broadcast networks with random arrivals,” _IEEE Trans. Mobile Computing_ , vol. 19, no. 12, pp. 2903–2915, Dec. 2020.
  * [37] R. Berry and R. Gallager, “Communication over fading channels with delay constraints,” _IEEE Trans. Inf. Theory_ , vol. 48, no. 5, pp. 1135–1149, May 2002.
  * [38] L. I. Sennott, “Constrained average cost Markov decision chains,” _Probab. Eng. Inf. Sciences_ , vol. 7, no. 1, pp. 69–83, Jan. 1993.
  * [39] ——, “Average cost optimal stationary policies in infinite state markov decision processes with unbounded costs,” _Operations Research_ , vol. 37, no. 4, pp. 626–633, 1989.