# Scheduling of Wireless Edge Networks for Feedback-Based Interactive
Applications

Samuele Zoppi1, Jaya Prakash Champati2, James Gross3, and Wolfgang Kellerer1
1Chair of Communication Networks, Technical University of Munich, Germany
2IMDEA Networks Institute, Spain
3School of Electrical Engineering and Computer Science, KTH Royal Institute of
Technology, Sweden
Email: {samuele.zoppi<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

Interactive applications with automated feedback will largely influence the
design of future networked infrastructures. In such applications, status
information about an environment of interest is captured and forwarded to a
compute node, which analyzes the information and generates a feedback message.
Timely processing and forwarding must ensure the feedback information to be
still applicable; thus, the quality-of-service parameter for such applications
is the end-to-end latency over the entire loop. By modelling the communication
of a feedback loop as a two-hop network, we address the problem of allocating
network resources in order to minimize the delay violation probability (DVP),
i.e. the probability of the end-to-end latency exceeding a target value. We
investigate the influence of the network queue states along the network path
on the performance of semi-static and dynamic scheduling policies. The former
determine the schedule prior to the transmission of the packet, while the
latter benefit from feedback on the queue states as time evolves and
reallocate time slots depending on the queue’s evolution. The performance of
the proposed policies is evaluated for variations in several system parameters
and comparison baselines. Results show that the proposed semi-static policy
achieves close-to-optimal DVP and the dynamic policy outperforms the state-of-
the-art algorithms.

###### Index Terms:

Feedback applications, end-to-end delay, delay violation probability, network
state information, semi-static scheduling, dynamic scheduling, MDP.

##  I Introduction

Interactive applications with automated feedback are arguably one of the most
discussed application class when it comes to large-scale impact in future
networked infrastructures today [1]. In the literature, we can broadly
distinguish two sub-cases of this new application class, namely cyber-physical
systems (CPS) and human-in-the-loop systems [2, 3, 4]. In both cases, however,
the underlying principle is the same: status information about a plant or an
environment of interest is captured, and forwarded to a compute node, where
the information is analyzed and potentially a feedback is generated in form of
an actuation command or an augmentation/perceptual feedback; see Fig. 1. In
CPS, we encounter applications where direct actuation is applied to a physical
object, for instance, in the context of industrial automation and automated
driving. In contrast, augmented reality, cognitive assistance, and also to
some extent virtual reality fall under the category of human-in-the-loop
systems, where no direct actuation results from the feedback; instead, a human
is presented perceptual feedback which potentially triggers some human
reaction [4].

Key features about these applications is their tight integration with reality
as well as the degree of automation that they allow. Furthermore, by
offloading these applications to networked infrastructures, an almost
ubiquitous availability of corresponding services will be enabled in the
future. However, the successful deployment of such applications rests
crucially on a timely processing and forwarding along the pipeline to ensure
that the feedback information is timely with respect to the original sensing
data. Thus, the quality-of-service (QoS) parameter for interactive
applications is the latency over the entire loop, i.e. from capturing the
status information until the point in time when the corresponding feedback
information is exposed [5]. For instance, motion-to-photon latency in virtual
reality is a well-known concept that captures this QoS parameter. Loosely
speaking, one might refer to this QoS parameter as the end-to-end latency with
the crucial differentiation that a flow conversion occurs at the point of
computation. In fact, depending on the application, for a certain fraction of
sensing data no feedback is generated at all, for instance in the case of
cognitive assistance. Finally, different applications may also require time-
varying end-to-end latencies. For instance, in CPS it is known that the
criticality of sensing information can vary, leading to time-varying end-to-
end latency constraints as the plant dynamics evolve.

Figure 1: Architecture of interactive applications with automated feedback.
Sensor (S), controller (C), and actuator (A) operate in a closed loop via a
two-hop wireless network path.

Given the relevance of interactive applications, as well as their novel QoS
requirements, a central question relates to the optimal support of such
applications by networked infrastructures. Truly ubiquitous service offering
mandates wireless connectivity to the point of computation. Furthermore,
general latency requirements mandate near-by computational service, typically
provided by edge computing [6]. Hence, a networked infrastructure realizing an
interactive application needs to provide bounded end-to-end latencies over a
concatenated, heterogeneous network path with at least one compute element
incorporated [1]. This complicates the provisioning of end-to-end latencies,
as the individual elements of the network path are typically subject to
multiple random effects, such as fading in case of the wireless links,
operating system scheduling effects in case of the compute backend, and/or
cross-traffic for both the communication and computation elements [7]. As a
consequence, the end-to-end latency becomes essentially a random variable,
which also depends on parameterizations of the network path such as resource
allocation, task prioritization etc. In order to steer the parameterization of
the network path facing the uncertainty from different effects, a suitable
metric is to minimize the delay violation probability (DVP), defined as the
probability of the end-to-end latency exceeding a (constant or varying) target
value. The key question then is to manage network path resources to minimize
the DVP. Addressing this question is at the heart of this work.

Acknowledging the fact that latency targets might vary over time, as well as
cross-traffic contributing to the utilization of the individual elements of
the path, we are interested in the fundamental question if initial conditions
of the network path should influence the path parameterization. By initial
conditions, we refer to the queue states along the network path, which is
modelled as a concatenated queuing network. This might be included in at least
two different ways. On the one hand, once a new sensor reading is available, a
_semi-static_ resource allocation might be determined which is kept during the
subsequent evolution of the system until the corresponding actuation command
is delivered to the actuator. On the other hand, a _dynamic_ policy constantly
adjusts the resource allocation during the evolution of the system until the
actuation command is delivered. Obviously, a constant adaptation of the
resource allocation should provide a better performance in terms of observed
delay violations at the price of increased signaling load. But exactly how
such algorithms should work, which complexity they bring, and which
performance differences they imply for interactive applications is to the best
of our knowledge open to date.

In this paper, the above questions are investigated for a two-hop network path
incorporating the loop communication of the status information to a compute
node and of the feedback message to an actuator, cf. Fig. 1. The two-hop
system follows an uplink/downlink model where network resources need to be
assigned _in competition_. This applies to communication systems where time
resources are typically shared between uplink and downlink, such as
WirelessHART, LTE TDD, and 5G TDD NR. The end-to-end latency of packets is
dominated by the random delay caused by the retransmission of lost packets and
thus the processing delay introduced by the compute node is assumed to be
negligible. Packet transmission follows a time-slotted medium access where
network resources are organized in frames. In each frame, the available time
slots are entirely allocated to the two links that compete for resources.
Therefore, given the initial queue states of the two links, we investigate
scheduling policies that allocate time slots of each frame to the links in
order to minimize the DVP of packets belonging to interactive applications.

The main contributions of this paper are summarized in the following:

  * •

We show that the closed-form expression of DVP is intractable and derive two
upper bounds for the DVP of packets traversing a two-hop network path given
the initial network conditions.

  * •

Novel heuristic scheduling policies that compute a semi-static resource
allocation are proposed.

  * •

Noting that DVP cannot be directly used for dynamic resource allocation, a
dynamic heuristic scheduling policy that maximizes the network’s throughput is
proposed.

  * •

A simulation study of semi-static scheduling policies as well as a comparison
between the dynamic scheduling policy, the classical Backpressure (BP) [8],
Max Weight (MW) [9], and Weighted-Fair Queuing (WFQ) [10] scheduling policies
is presented.

The rest of the paper is structured as follows. Sec. II provides a discussion
of the related work. Sec. III defines the model of the two-hop network path
and the problem statement. Sec. IV provides a general derivation of DVP and
discusses its application for scheduling. In Sec. V heuristic semi-static
scheduling policies are derived, while Sec. VI describes an MDP-based
heuristic dynamic scheduler. Sec. VII evaluates the performance of the
proposed scheduling methods and provides a discussion on their applicability
in different scenarios. Finally, we conclude in Sec. VIII.

##  II Related Work

Several existing works tackle the problem of resource allocation in a multi-
hop wireless network to support time-critical applications. Methods that make
use of the queue state to allocate network resources follow a _theoretical_
approach [11, 8, 12]. In their pioneering work [11], Tassiulas et al. derived
the Max Weight scheduling policy, which allocates resources based on the
transmitters’ backlogs and achieves maximum throughput and minimum delay.
Their scenario, however, is different from the one in this work as they only
considered a single-hop network. For a multi-hop network, maximum throughput
was achieved by the backpressure algorithm [8], which allocates resources
based on the backpressure of queues in the network. Differently than this work
that minimizes the DVP of time-critical packets, their scheduling policy
focused on throughput optimality. Singh et al. [12] exploited information
about the queue state to schedule transmissions in order to maximize
throughput under delay constraints. Their approach, however, considers the
steady-state performance of packets and, differently than our approach, does
not allocate resources to optimize the network for a single time-critical
arrival.

From a different perspective, many practical works investigate resource
allocation methods for real-time flows in Industrial Wireless Sensor Networks
(IWSN). Some of them compute schedules to allow several time-constrained
applications to meet their deadlines assuming _deterministic transmission
outcomes_ [13, 14, 15, 16, 17, 18]. Saifullah et al. [13, 14] investigated the
problem of real-time scheduling subject to end-to-end deadlines between
sensors and actuators. Differently than our work, however, communication
between sensors and actuators is deterministic and packet loss is not
considered. In their recent works [15, 16], communication failures due to
packet loss are considered and retransmissions are used. In contrast to our
work, however, the only provide a deterministic delay model for the
communication between sensors, controller, and actuators. Similarly, Wang et
al. [17] calculated schedules to ensure the worst-case delay of packets in a
flow, however, without assuming random packet loss. Modekurthy et al. [18]
derived a distributed deadline-based scheduling algorithm based on the
Earliest Deadline First policy. Also in this case, differently than our
scenario, packet loss is not considered and the random end-to-end delay of
packets in the network is not characterized.

Other IWSN works tackle the problem of reliable communication in presence of
_random packet loss_ [19, 20, 21]. Dobslaw et al. [20], allocated resources to
each transmitter in a path based on the required number of retransmissions to
fulfil a given reliability constraint. Differently than our model, however,
their work did not consider a deadline for the packets. Following a similar
approach, Gaillard et al. [21] extended the pioneer traffic-aware centralized
scheduler TASA [22] including retransmissions to guarantee flow reliability
requirements. Also in this case, however, traffic is not time-constrained. Yan
et al. [19] developed a scheduling method that allocates time slots to the
transmitters in order to maximize the network reliability under delay
constraints. A major difference of their work, which is common to Dobslaw and
Gaillard et al., is that reliability constraints are defined for all the flows
in the network. Our approach instead optimizes the network resources to
maximize the application reliability of each time-critical packet.

Recent works tackle investigate resource allocation methods providing _per-
packet_ delay and reliability performance [23, 24, 25, 26]. Similarly to DVP,
Chen et al. [23] computed, for each packet, the number of transmissions
required to fulfil the application deadline with a given probability. Their
work, however, only considered a single-hop scenario and cannot be applied to
the considered two-hop network path. Brummet et al. [24] developed a method to
dynamically allocate retransmissions to each packet and at each network hop
subject to delay and reliability requirements. They followed a different
approach as their schedules are designed to fulfil the requirements and limit
the maximum number of retransmissions. Therefore, their scenario did not
optimize network resources to maximize the per-packet DVP. A similar approach
was used by Gong et al. [25], which allocated time slots to transmitters
fulfilling per-packet delay and reliability constraints while minimizing the
number of resources. Also in this case, however, they considered a finite
number of retransmissions and the network resources are not optimized to
minimize DVP. On the contrary, Soldati et al. [26] allocated time slots over
multiple hops maximizing the end-to-end reliability of each time-critical
packet subject to a deadline. Differently than our approach that characterizes
the distribution of end-to-end delay considering the correlation of
transmission outcomes over consecutive transmitters, their scenario assumes
that resource allocations of consequent transmitters are independent.

This work extends our previous work [27] by deriving semi-static scheduling
policies and investigating the impact of queue state information on the
minimum achievable DVP. We achieve this thanks to a transient queuing model of
the network and by modelling the end-to-end delay of each packet of
interactive applications. This is different from the available state-of-the-
art for multiple reasons. Instead of considering QoS for a stationary flow, we
analyse the random end-to-end delay incurred for each time-critical arrival.
The considered queuing model allows us to derive scheduling policies taking
into account the correlation between subsequent transmitters introduced by
random transmission outcomes. This is different from the related work as
existing scheduling policies optimize network resources based on the
interaction of multiple independent flows sharing the network. Furthermore, by
allocating a finite amount of retransmissions, all the existing methods allow
application packets to be dropped, which may result in critical failures of
feedback systems. Finally, we investigate the impact of queue state
information on semi-static and dynamic scheduling policies, which, to the best
of the knowledge of the authors, was never tackled in the literature for a
two-hop network path.

##  III System Model and Problem Statement

We study the communication scheduling problem of a feedback system consisting
of a sensor, a control logic, and an actuator. The two-hop data communication
from the sensor to the controller, and the controller to the actuator is
performed via error-prone wireless links. We now describe the details of the
model and the network elements, and present the formulation of the scheduling
problem.

###  III-A Arrivals, Backlogs, and Departures

We model the sensor-controller link, and controller-actuator link using a
packet-flow, discrete-time, two-queue lossy wireless network with first-come-
first-serve discipline, cf. Fig. 2. The time is discretized into slots, which
are grouped in frames. A sequence of $y$ packets arrives at the first queue in
frame $0$111We consider frame $0$ for notational simplicity; nevertheless, our
analysis is equally valid starting the system with any other frame.. These
packets are time critical with a requirement that they depart the second queue
within next $w$ frames, where $w$ is finite. These packets, for instance, may
belong to a time-critical message whose latency could significantly impact the
application performance, i.e. the stability/safety of a feedback system. We
are thus interested in analyzing the two-queue network path for the time
frames $k\in\\{0,1,\ldots,w-1\\}$. In this transient regime, the delay
incurred by the time-critical packets depends on the initial backlogs in the
queues at frame $0$, and the temporal variations in the service received by
the queues.

Figure 2: Network model of the two-hop network path. The available time slots
are entirely allocated to the two queues at each frame until the deadline.

We use $i\in\\{1,2\\}$ to index the queues. Let $x_{i}$ denote the backlog in
queue $i$ in frame $0$. Let ${A}^{i}(k)$ and ${D}^{i}(k)$ denote the
cumulative arrivals and departures at queue $i$, in frame $k$. For $k=0$, all
the quantities are set to zero. For $k\geq 1$, we define

$\displaystyle A^{\text{1}}(k)$ $\displaystyle=y+x_{1},$ (1) $\displaystyle
A^{\text{2}}(k)$ $\displaystyle=D^{\text{1}}(k-1)+x_{2},$ (2)
$\displaystyle{D}^{i}(k)$ $\displaystyle=\sum_{j=0}^{k-1}d^{i}_{j},$ (3)

where $d^{i}_{j}$ is the number of packets departed queue $i$ in frame $j$. In
Eq. (2) a one-step delay is introduced between the reception of a packet and
its service at the second queue indicating that packets must be fully received
before being relayed. In the following, we use $A(k)=A^{\text{1}}(k)$ and
$D(k)=D^{\text{2}}(k)$. For analytical simplicity, we assume that a packet
received by the controller is processed within the same frame of reception,
i.e. processing latencies are negligible, and results in a new packet carrying
the feedback information. Sensor and actuator messages can assume arbitrary
size, however, we assume that their size is fixed to a maximum size of $B$
bits.

The end-to-end virtual delay, denoted by $W(k)$, is defined as

$\displaystyle W(k)=\inf\left\\{u\geq 1:{A}(k)+x_{2}\leq{D}(k+u-1)\right\\}.$
(4)

It quantifies the delay faced by the cumulative arrivals till frame $k-1$.

###  III-B Lossy Wireless Network Model

At the link layer, we consider an error-prone time-slotted system where
multiple frequencies can be used for transmission. Packet loss is caused by
fading in the received signal, which can arise, for instance, from shadowing,
mobility, or external interference. We assume that a frequency diversity
mechanism is used in the network and sequential packet transmissions are
characterized by uncorrelated channel fades. Whenever critical messages are
transmitted via unreliable wireless links, it is a common approach to deploy
frequency diversity techniques, such as frequency hopping or frequency
scheduling, to avoid sequential packet drops due to correlated channel fades.
Thus, we restrict our analysis to the time domain.

We model the random service provided for a single packet transmission as a
Bernoulli r.v. according to an average Packet Error Rate (PER) of the
communication link. That is, a packet is lost with probability $p_{e}$ and
received with probability $1-p_{e}$. The PER is determined by the average
Signal-to-Noise-and-Interference-Ratio (SINR) which in turn is determined by
the combination of the propagation environment and the modulation and coding
scheme used for transmission.

Each frame comprises of $N$ time slots to be shared between the transmissions
of packets from the two queues in the uplink and the downlink, cf. Fig. 2. In
frame $k$, let $n_{k}^{\text{1}}$ and $n_{k}^{\text{2}}=N-n_{k}^{\text{1}}$
denote the slots used for transmitting the packets from the first queue and
the second queue, respectively. Given this frame allocation, the service
offered by the $i$-th link at frame $k$ is distributed as a Binomial r.v.
given by

$\displaystyle
b_{k}^{i}(n_{k}^{i})\sim{\mathcal{B}}\left(n^{i}_{k},1-p_{e}\right).$ (5)

The cumulative service provided on the link at queue $i$ in $k$ consecutive
frames is equal to a summation of Binomial random variables with parameters
$1-p_{e}$, which is also a Binomial r.v. given by

$\displaystyle\IEEEeqnarraymulticol{3}{l}{{S}^{i}(k)=\sum_{j=0}^{k-1}b^{i}_{j}(n^{i}_{j})\sim{\mathcal{B}}\left(\sum_{j=0}^{k-1}n^{i}_{j},1-p_{e}\right).}$
(6)

###  III-C Problem Statement

We are interested in optimizing the dynamic service offered by the wireless
links of sensor and controller to minimize the end-to-end delay of a time-
critical arrival while it traverses the network. In particular, in order to
investigate scheduling policies that exploit initial network conditions, we
study the impact of queue state information on the achievable performance of
semi-static and dynamic resource allocations.

We define a scheduling policy $\pi$ as the allocation of time slots to both
queues in every frame until the deadline, i.e.
$\pi\triangleq\mathbf{n}^{1}=\\{n^{\text{1}}_{0},n^{\text{1}}_{1},\ldots,n^{\text{1}}_{w-1}\\}$,
equivalently $\pi\triangleq\mathbf{n}^{2}=N-\mathbf{n}^{1}$. Different
scheduling algorithms are computed based on the queue state information
$\mathbf{q}_{k}=(q^{\text{1}}_{k},q^{\text{2}}_{k})$, where $q^{\text{1}}_{k}$
and $q^{\text{2}}_{k}$ denote the lengths of first and second queues in frame
$k$, respectively.

In the following, we consider scheduling policies that compute semi-static and
dynamic resource allocations. On the one hand, a semi-static scheduling
policy, denoted by $\pi_{S}$, computes a schedule based on the initial state
$\mathbf{q}_{0}$. Semi-static policies can be applied, for instance, to
resource-constrained wireless networks such as WSN, where updating the network
allocation over time is difficult due to the availability of a single radio
interface and unreliable feedback channels. On the other hand, a dynamic
scheduling policy, denoted by $\pi_{D}(\mathbf{q}_{k})$, relies on the
availability of the queue state $\mathbf{q}_{k}$ at a centralized network
logic, which is used to determine the allocation of slots for the next frame,
i.e. at $k$-th frame $n^{1}_{k}=\pi_{D}(\mathbf{q}_{k})$. An exemplary
application of dynamic policies is in cellular networks, where reliable
feedback channels can timely deliver new queue states to the network
coordinator and resource allocations to the devices.

Given the end-to-end deadline $w$, we define the Delay Violation Probability
(DVP) of a sequence of time-critical packets that arrived in frame $0$ as the
probability that one or more packets of the sequence do not depart the second
queue by the end of frame $w$. For initial backlogs $x_{1}$, $x_{2}$ this is
denoted by $\text{DVP}\left(w,y,x_{1},x_{2}\right)$ and is given by

$\displaystyle\text{DVP}\left(w,y,x_{1},x_{2}\right)$
$\displaystyle\coloneqq{\mathbb{P}}\left\\{W(1)>w\right\\}.$ (7)

The above equivalence is obtained using Eq. (4), where the event
$\\{W(1)>w\\}$ implies that the cumulative departures by the end of frame $w$
are smaller than the total number of packets in frame $0$. Note that DVP could
potentially be used as QoS in networked feedback systems; for example, given a
deadline of $w$ frames, DVP represents the probability that a packet (carrying
control command) in response to a packet generated by the sensor is delivered
to the actuator within the deadline.

We are interested in finding semi-static and dynamic scheduling policies that
minimize the DVP of packets belonging to interactive applications. The
policies are obtained by formulating and solving the following optimization
problems. Let $\Pi_{S}$ and $\Pi_{D}$ denote the sets of all possible semi-
static and dynamic scheduling policies222These sets are non-empty; an example
policy allocates slots equally to both links in all frames.. Given $y$
application packets arrived in frame $0$, an optimal semi-static policy
$\pi_{S}$ is obtained solving

$\displaystyle\underset{\pi_{S}\in\Pi_{S}}{\text{minimize}}\quad\text{DVP}\left(w,y,x_{1},x_{2}\right).$
(8)

A dynamic scheduling policy $\pi_{D}$ is obtained solving

$\displaystyle\underset{\pi_{D}\in\Pi_{D}}{\text{minimize}}\quad\text{DVP}\left(w,y,x_{1},x_{2}\right).$
(9)

In Eq. (8) and Eq. (9), $\Pi_{S},\Pi_{D}$ denote the sets of all possible
semi-static and dynamic scheduling policies, and are non-empty as each
resulting slot allocation is valid.

In the sequel, we will be using the following definitions. Given a set of
events $E_{1},E_{2},\dots$ the _union bound_ is given by

$\displaystyle{\mathbb{P}}\left\\{\bigcup_{i}E_{i}\right\\}\leq{\mathbb{P}}\left\\{\sum_{i}E_{i}\right\\}.$

Furthermore, given a random variable $X$, for every $t>0$, the _Chernoff
bound_ is given by

$\displaystyle{\mathbb{P}}\left\\{X\geq
x\right\\}\leq\frac{{\mathbb{E}}[e^{tX}]}{e^{tx}},$

where ${\mathbb{E}}[\cdot]$ denotes the expectation operator.

##  IV Derivation of Delay Violation Probability

We characterize DVP using Stochastic Network Calculus (SNC) [28]. From Eq.
(4), DVP can be obtained in terms of the virtual delay of the network

$\displaystyle\text{DVP}\left(w,y,x_{1},x_{2}\right)$
$\displaystyle={\mathbb{P}}\left\\{W(1)>w\right\\}$
$\displaystyle\,={\mathbb{P}}\left\\{{D}(w)<y+x_{1}+x_{2}\right\\}.$ (10)

Applying the input-output relation for a queue with a dynamic server

${D}(k)\geq\min_{0\leq u\leq k}\left[{A}(u)+{S}(k-u)\right],$ (11)

we can derive the exact expression of DVP.

######  Proposition 1.

The delay violation probability (DVP) of a time critical arrival of $y$
packets at $k=0$, given initial queue backlogs $x_{1},x_{2}$ is

$\displaystyle\IEEEeqnarraymulticol{3}{l}{\text{\emph{DVP}}(w,y,x_{1},x_{2})=}$
$\displaystyle{\mathbb{P}}\Big{\\{}\\!\left\\{{S}^{2}(w)\\!<\\!y+x_{1}+x_{2}\right\\}\cup\left\\{{S}^{2}(w-1)\\!<\\!y+x_{1}\right\\}\cup$
(12)
$\displaystyle\bigcup_{u=2}^{w}\left\\{{S}^{2}(w-u)+{S}^{1}(u-1)<y+x_{1}\right\\}\Big{\\}}.$

###### Proof.

The proof can be found in Appendix -A ∎

From Eq. (12), we observe that the calculation of DVP is highly non-trivial.
The DVP computation requires the knowledge of future, i.e. both the
allocations $n^{1}_{k}$ and the resulting queue states, in order to calculate
the cumulative services. Thus, it is impossible to use DVP to obtain a
scheduling policy which causally allocates the time slots at each frame within
the deadline using only the past information. Furthermore, computing the exact
value of DVP is not tractable as it requires the calculation of the
probability of union of $w$ events that are not mutually disjoint.

In this work, we address this issue by deriving upper bounds for DVP which are
then used to design semi-static and dynamic schedulers. In Sec. V, we
investigate _semi-static_ scheduling policies based on two upper bounds of Eq.
(12) to determine the allocation of slots until the deadline solely relying on
the initial queue states. Then, in Sec. VI, a _dynamic_ scheduling policy is
derived based on another upper bound for DVP that reallocates the network
resources according to the changes in the queue states.

##  V Semi-static Scheduling Policies

In this section, we derive an upper bound for DVP, referred to as DVPUB, and
formulate an upper bound minimization problem, which is then used to compute
the proposed semi-static policies.

Using the union bound for DVP in (12), we obtain DVPUB, given by

$\displaystyle\text{DVPUB}(w,y,x_{1},x_{2})={\mathbb{P}}\left\\{{S}^{2}(1+w)\\!<\\!y+x_{1}+x_{2}\right\\}+$
$\displaystyle\sum_{u=1}^{1+w}{\mathbb{P}}\left\\{{S}^{2}(1+w-u)+{S}^{1}(u-1)<y+x_{1}\right\\}$
$\displaystyle={\mathbb{P}}\left\\{{S}^{2}(1+w)\\!\leq\\!y+x_{1}+x_{2}-1\right\\}+$
$\displaystyle\sum_{u=1}^{1+w}{\mathbb{P}}\left\\{{S}^{2}(1+w-u)+{S}^{1}(u-1)\leq\\!y+x_{1}-1\right\\}.$
(13)

Applying Eq. (6) to Eq. (13), the DVPUB resulting from the allocation of
$\mathbf{n}^{1}=\\{n^{1}_{0},\dots,n^{1}_{w}-1\\}$ slots at the second
transmitter and $\mathbf{n}^{2}=N-\mathbf{n}^{1}$ slots at the first one is
given by

$\displaystyle\text{DVPUB}(w,y,x_{1},x_{2},\mathbf{n}^{2})=\sum_{x=0}^{y+x_{1}+x_{2}-1}{\mathbb{P}}\left\\{\sum_{i=0}^{w}b_{i}^{2}\left(n_{i}^{2}\right)=x\right\\}$
$\displaystyle+\sum_{u=1}^{1+w}\sum_{z=0}^{y+x_{1}-1}{\mathbb{P}}\left\\{\sum_{j=0}^{w-u}b_{j}^{2}\left(n_{j}^{2}\right)+\sum_{k=0}^{u-2}b_{k}^{1}\left(n_{k}^{1}\right)=z\right\\}$
$\displaystyle\stackrel{{\scriptstyle\text{(a)}}}{{=}}\sum_{x=0}^{y+x_{1}+x_{2}-1}\left(\frac{1}{p_{e}}-1\right)^{x}{\sum_{i=0}^{w}n_{i}^{2}\choose
x}p_{e}^{\sum_{i=0}^{w}n_{i}^{2}}$
$\displaystyle+\sum_{u=1}^{1+w}\sum_{z=0}^{y+x_{1}-1}\left(\frac{1}{p_{e}}-1\right)^{z}p_{e}^{\sum_{j=0}^{w-u}n_{j}^{2}-\sum_{k=0}^{u-2}n_{k}^{2}+(u-1)N}\cdot$
$\displaystyle{\sum_{j=0}^{w-u}n_{i}^{2}-\sum_{k=0}^{u-2}n_{j}^{2}+(u-1)N\choose
z}.$ (14)

In step (a), we used the fact that $S^{i}(k)$ is distributed as a Binomial
r.v. as shown in Eq. (6).

We are interested in minimizing the DVPUB to find semi-static scheduling
policies. However, this is highly non trivial for different reasons.
Minimizing DVPUB is a combinatorial problem and finding a heuristic solution
by relaxing the domain of $\mathbf{n}^{2}$ is challenging as DVPUB consists of
the sum of several binomial coefficients. Thus, it is highly non trivial to
study its convexity. Therefore, following a similar approach as in [7] a
looser convex bound, referred to as Wireless Transient Bound (WTB), is
obtained by applying the _Chernoff bound_ to Eq. (13).

$\displaystyle\text{WTB}(w,y,x_{1},x_{2})=\min_{s>0}\Big{\\{}{\mathbb{E}}\left[e^{-s\,{S}^{2}(1+w)}\right]e^{s\,(y+x_{1}+x_{2}-1)}+$
$\displaystyle\quad\sum_{u=1}^{1+w}{\mathbb{E}}\left[e^{-s\left[{S}^{1}(u-1)+{S}^{2}(1+w-u)\right]}\right]e^{s\,(y+x_{1}-1)}\Big{\\}}.$
(15)

The calculation of WTB for a wireless transmitter is obtained by computing the
Mellin transform of the cumulative service of Eq. (6), given by

$\displaystyle\mathbb{E}\left[e^{-s\,{S}(m,\mathbf{n})}\right]$
$\displaystyle=\mathbb{E}\left[e^{-s\,\sum_{i=0}^{-1+\sum_{j=0}^{m-1}n_{j}}b_{i}}\right]$
$\displaystyle=\mathbb{E}\left[\left(e^{-s\,b_{i}}\right)^{\sum_{i=0}^{m-1}n_{i}}\right]$
$\displaystyle=\left[(1-p_{e})e^{-s}+p_{e}\right]^{\sum_{i=0}^{m-1}n_{i}},$
(16)

where $b_{i}$ are i.i.d. Bernoulli random variables for transmission outcomes.
Finally, combining Eq. (15) and (16), we obtain

$\displaystyle\text{WTB}(w,y,x_{1},x_{2},\mathbf{n}^{2})=$
$\displaystyle\min_{s>0}\Big{\\{}\left[(1-p_{e})e^{-s}+p_{e}\right]^{\sum_{i=0}^{w}n_{i}^{2}}e^{s\,(y+x_{1}+x_{2}-1)}+$
$\displaystyle\sum_{u=1}^{1+w}\\!\left[(1\\!-\\!p_{e})e^{-s}\\!\\!+p_{e}\right]^{(u-1)N-\sum_{j=0}^{u-2}n_{j}^{2}+\sum_{i=0}^{w-u}n_{i}^{2}}\\!e^{s\,(y+x_{1}-1)}\Big{\\}}.$
(17)

Given the initial queue backlogs
$\mathbf{q}_{0}=\left\\{x_{1},x_{2}\right\\}$, we aim to solve the upper bound
minimization problem below

$\operatorname*{arg\,min}_{\mathbf{n}^{2}\in\left\\{1,\dots,N-1\right\\}^{w}}\text{WTB}(w,y,x_{1},x_{2},\mathbf{n}^{2}).$
(18)

To solve the integer-programming problem (18), one may employ exact algorithms
(such as branch-and-bound), which however has run-time that scales
exponentially with $N$ and $w$. Instead, we relax the integer constraints,
show that the relaxed problem is convex, and use different methods to round
the continuous values of the solution and obtain multiple heuristics for the
minimization of DVPUB.

Let $\widetilde{\pi}^{\star}_{S}$ denote the optimal solution for the relaxed
problem of (18) which is given by

$\widetilde{\pi}^{\star}_{S}\,=\operatorname*{arg\,min}_{\mathbf{n}^{2}\in\left[1,N-1\right]^{w}}\text{WTB}(w,y,x_{1},x_{2},\mathbf{n}^{2}).$
(19)

######  Theorem 1.

The optimization problem in (19) is convex.

###### Proof.

The proof is given in Appendix -B. ∎

Thanks to Theorem 1, well-known convex optimization algorithms, such as the
subgradient or interior-point can be used, which provide scalability for an
increasing number of slots $N$ and frames within the deadline $w$. In this
work, (19) is solved using the nonlinear programming solver _fmincon_
available in Matlab™ employing the sequential quadratic programming (SQP)
algorithm. Once $\widetilde{\pi}^{\star}_{S}$ is found, a conversion to the
integer domain is needed in order to determine a feasible solution, which we
refer by $\hat{\pi}^{\star}_{S}$. Although the optimal selection of an integer
solution would require the exploration of the entire problem’s domain,
heuristic methods can be applied to find a solution in the neighbourhood of
$\widetilde{\pi}^{\star}_{S}$. To this end, we investigate different neighbour
search methods in order to achieve near-optimal performances.

The simplest way to derive $\hat{\pi}^{*}_{S}$ is to round each frame
allocation of $\widetilde{\pi}^{\star}_{S}$ to its closest integer value. We
refer to this method as WTB-R. Alternatively, a heuristic policy can be found
as follows. For each frame allocation
$n^{1}_{i}\in\widetilde{\pi}^{\star}_{S}$, two integer values are derived
applying the floor and ceiling functions. A search space is constructed by
computing all the combinations of the integer values for each frame until the
deadline which leads to a total of $2^{w}$ combinations. As final step, Eq.
(14) and (17) are used to evaluate each combination and identify the best one.
The semi-static policies corresponding to the evaluation of Eq. (14) and (17)
over this search space are referred to as WTB-D and WTB-W, respectively.

The performances of the different heuristics have been evaluated via extensive
simulations over a broad range of values for each system parameter, i.e. for
$x_{1},x_{2}$ $\in$ $\left\\{0,1,2\right\\}$, $w$ $\in$
$\left\\{2,3,4,5,6\right\\}$, $N$ $\in$ $\left\\{2,3,4,5\right\\}$, and
$p_{e}$ $\in$ $\left\\{0.2,0.33,0.4,0.5\right\\}$. For performance comparison,
two additional schedulers have been evaluated, eDVPUB and eWTB, which
exhaustively explore the problem’s domain to find the policies that
respectively achieve the minimum values of DVPUB, cf. Eq. (14), and WTB, cf.
Eq. (17). Furthermore, the performance of each scheduler is compared with the
performance of the policy that achieves the minimum DVP. This optimal policy
is found by exploring the DVP of all possible policies via simulations and
then, for each policy, simulations are used to compute its DVP.

Fig. 3 shows the performance of the proposed semi-static schedulers by
computing, for each scheduler and system configuration, the percentage of
feasible policies that achieve higher DVP. As expected, the exhaustive search
methods eWTB and eDVPUB achieve the best results, with eDVPUB finding, in the
large majority of cases, the top $10\%$ semi-static policies. The performance
gap between eWTB and eDVPUB is introduced by the Chernoff bound in Eq. (16).
These methods, however, do not represent a feasible way of computing policies
as they require the exhaustive exploration of the entire problem domain.
Differently, the heuristic methods WTB-R/W/D can be used to efficiently find
semi-static policies for arbitrary parameters. The low complex WTB-R achieves
the worst performance. WTB-W and WTB-D achieve similar performances and show a
small performance penalty with respect to the exhaustive methods, with WTB-W
achieving better performances. This can be explained by the fact that, in
WTB-D, Eq. (17) is used to solve the relaxed problem, while Eq. (14) to find
the integer solution. For this reason, only WTB-W is presented in the
numerical section.

Figure 3: Performance of the proposed semi-static schedulers for different
system parameters. For each scheduler, the percentage of existing policies
that achieve higher DVP is evaluated.

##  VI Dynamic Scheduling Policy

In order to compute the DVP of time-critical packets, cf. Eq. (12), the
knowledge of future allocation and queue states is needed. Thus, it is
impossible to use DVP to obtain a dynamic scheduling policy which causally
allocates the time slots using only the past information. To address this
problem, we obtain an upper bound for DVP using Markov’s inequality:

$\displaystyle\text{DVP}(w,y,x_{1},x_{2})$
$\displaystyle={\mathbb{P}}\\{{D}(w)<y+x_{1}+x_{2}\\}$
$\displaystyle={\mathbb{P}}\\{{D}(w)\leq y+x_{1}+x_{2}-1\\}$
$\displaystyle={\mathbb{P}}\\{1/{D}(w)\geq 1/(y+x_{1}+x_{2}-1)\\}$
$\displaystyle\leq(y+x_{1}+x_{2}){\mathbb{E}}[1/{D}(w)].$ (20)

From Eq. (20) we infer that minimizing the expectation of the inverse of the
cumulative departures (throughput) of the network minimizes the upper bound of
the DVP and thus potentially reduces DVP. Using this insight, in the
following, we compute a heuristic schedule by solving the expected throughput
maximization problem stated below:

$\displaystyle\underset{\pi_{D}\in\Pi_{D}}{\text{maximize}}\quad{\mathbb{E}}[{D}(w)]=\sum_{k=0}^{w-1}{\mathbb{E}}\left[d^{i}_{k}\right].$
(21)

In order to solve the optimization problem in Eq. (21), we formulate a
discrete-time, finite-horizon MDP. We use $\mathbf{q}_{k}$ to denote the state
of the system and $n^{\text{1}}_{k}$ to denote the action in frame $k$. The
maximum number of slots in a frame is $N$ and therefore
$n^{\text{1}}_{k}\in\\{0,1,\ldots,N\\}$. Given $n^{\text{1}}_{k}$, from (6) we
have

$\displaystyle\mathbb{P}\\{s_{k}^{\text{1}}=r\\}$
$\displaystyle=\binom{n^{\text{1}}_{k}}{r}(1-p_{e})^{r}p_{e}^{n^{\text{1}}_{k}-r},$
$\displaystyle\mathbb{P}\\{s_{k}^{\text{2}}=r\\}$
$\displaystyle=\binom{N-n^{\text{1}}_{k}}{r}(1-p_{e})^{r}p_{e}^{N-n^{\text{1}}_{k}-r}.$

The queues evolve as below:

$\displaystyle q^{\text{1}}_{k+1}$
$\displaystyle=\max(q^{\text{1}}_{k}-s_{k}^{\text{1}},0),$ (22) $\displaystyle
q^{\text{2}}_{k+1}$
$\displaystyle=\max(q^{\text{2}}_{k}-s_{k}^{\text{2}},0)+\min(q^{\text{1}}_{k},s_{k}^{\text{1}}).$
(23)

Note that the number of departures from the first queue in frame $k$ equals
$\min(q^{\text{1}}_{k},s_{k}^{\text{1}})$, which are added to the second queue
to be served in frame $k+1$.

In the following, we formulate the transition probabilities for the states.
Note that the initial backlogs in the queues are $(y+x_{1},x_{2})$, where $y$
is due to the message of interest. We have $q^{\text{1}}_{0}=y+x_{1}$ and
$q^{\text{2}}_{0}=x_{2}$. We now analyse the set of possible states in our
system. In any frame $k$, a feasible state
$(q^{\text{1}}_{k},q^{\text{2}}_{k})$ should satisfy the following conditions:

$\displaystyle q^{\text{1}}_{k}$ $\displaystyle\leq q^{\text{1}}_{k-1},$ (24)
$\displaystyle q^{\text{1}}_{k}+q^{\text{2}}_{k}$ $\displaystyle\leq
q^{\text{1}}_{k-1}+q^{\text{2}}_{k-1}.$ (25)

Conditions Eq. (24) and Eq. (25) follow from the fact that we ignore arrivals
after the message of interest and in every frame each queue will receive
certain service. Note that while the length of the first queue can only
decrease as the packets are served, the length of the second queue may
increase up to $y+x_{1}+x_{2}$ as departures from first queue are added to the
second queue. Therefore, for every state $\mathbf{q}_{k}$ in the state space,
say $\mathcal{Q}$, $q^{\text{1}}_{k}\in\\{0,1,\ldots,y+x_{1}\\}$ and
$q^{\text{2}}_{k}\in\\{0,1,\ldots,y+x_{1}+x_{2}\\}$. This implies that
$\mathcal{Q}$ can contain at most $(y+x_{1}+1)(y+x_{1}+x_{2}+1)$ possible
states.

Consider that in frame $k$, $q^{\text{1}}_{k}=l^{1}$ and
$q^{\text{2}}_{k}=l^{2}$. We would like to present the transition
probabilities to the states $q^{\text{1}}_{k+1}=l^{1}_{+}$ and
$q^{\text{2}}_{k+1}=l^{2}_{+}$. We have the following cases.

Case 1: $l^{1}_{+}>l^{1}$ or $l^{1}_{+}+l^{2}_{+}>l^{1}+l^{2}$. From Eq. (24)
and Eq. (25), we infer that

$\displaystyle\mathbb{P}\\{q^{\text{1}}_{k+1}=l^{1}_{+},q^{\text{2}}_{k+1}=l^{2}_{+}|q^{\text{1}}_{k}=l^{1},q^{\text{2}}_{k}=l^{2}\\}=0.$

Case 2: $0<l^{1}_{+}\leq l^{1}$, $0<l^{2}_{+}$, and $l^{1}_{+}+l^{2}_{+}\leq
l^{1}+l^{2}$. In this case $s_{k}^{\text{1}}<q^{\text{1}}_{k}=l^{1}$ and
$s_{k}^{\text{2}}<q^{\text{2}}_{k}=l^{2}$. From Eq. (22) we have

$\displaystyle
q^{\text{1}}_{k+1}=q^{\text{1}}_{k}-s_{k}^{\text{1}}\quad\Rightarrow\quad
s_{k}^{\text{1}}=l^{1}-l^{1}_{+}.$

The number of packets served from the second queue are computed from Eq. (23).

$\displaystyle
q^{\text{2}}_{k+1}=q^{\text{2}}_{k}-s_{k}^{\text{2}}+s_{k}^{\text{1}}\quad\Rightarrow
s_{k}^{\text{2}}=l^{2}-l^{2}_{+}+l^{1}-l^{1}_{+}.$

Therefore,

$\displaystyle\mathbb{P}\\{q^{\text{1}}_{k+1}$
$\displaystyle=l^{1}_{+},q^{\text{2}}_{k+1}=l^{2}_{+}|q^{\text{1}}_{k}=l^{1},q^{\text{2}}_{k}=l^{2}\\}$
$\displaystyle=\mathbb{P}\\{s_{k}^{\text{1}}=l^{1}-l^{1}_{+},s_{k}^{\text{2}}=l^{2}-l^{2}_{+}+l^{1}-l^{1}_{+}\\}.$

Case 3: $l^{1}_{+}=0$, $0<l^{2}_{+}$, and $l^{2}_{+}\leq l^{1}+l^{2}$. In this
case all $l^{1}$ packets from the first queue are served. This implies
$s_{k}^{\text{1}}\geq q^{\text{1}}=l^{1}$. Using similar analysis as above, we
obtain

$\displaystyle\mathbb{P}\\{q^{\text{1}}_{k+1}=0,q^{\text{2}}_{k+1}=l^{2}_{+}|q^{\text{1}}_{k}=l^{1},q^{\text{2}}_{k}=l^{2}\\}$
$\displaystyle=\mathbb{P}\\{s_{k}^{\text{1}}\geq
l^{1},s_{k}^{\text{2}}=l^{2}-l^{2}_{+}+l^{1}\\}.$

Case 4: $l^{1}_{+}=l^{1}$, $l^{2}_{+}=0$. In this case we have
$s_{k}^{\text{1}}=0$, and all $l^{2}$ packets from the second queue are
served, i.e. $s_{k}^{\text{2}}\geq q^{\text{2}}=l^{2}$. From Eq. (23), we have

$\displaystyle\mathbb{P}\\{q^{\text{1}}_{k+1}$
$\displaystyle=l^{1},q^{\text{2}}_{k+1}=0|q^{\text{1}}_{k}=l^{1},q^{\text{2}}_{k}=l^{2}\\}$
$\displaystyle=\mathbb{P}\\{s_{k}^{\text{1}}=0,s_{k}^{\text{2}}\geq l^{2}\\}.$

Note that the case $0\leq l^{1}_{+}<l^{1}$ and $l^{2}_{+}=0$ cannot happen as
$l^{1}-l^{1}_{+}$ packets will be added to the second queue in the current
slot. All the above cases are written assuming that $l^{1}>0$ and $l^{2}>0$.
If either of them is zero, then the transition probability only involves the
probability for service received by the non-empty queue.

Given the initial state $\mathbf{q}_{0}=(y+x_{1},x_{2})$, we are interested in
finding a scheduling policy $\pi^{\star}_{D}$ that solves the maximization
problem of Eq. (21). For this, we define the reward $r_{k}$ of a policy
$\pi_{D}$ for a given state $\mathbf{q}_{k}$ as the expected number of
departures from the system, i.e. the expected number of packets that are
served at the second queue under this policy, and is given by

$\displaystyle r_{k}\left(\mathbf{q}_{k},\pi_{D}(\mathbf{q}_{k})\right)$
$\displaystyle={\mathbb{E}}\left[d^{i}_{k}|\,\pi_{D}(\mathbf{q}_{k})\right]$
$\displaystyle={\mathbb{E}}\left[\min\left(q^{\text{2}}_{k},s_{k}^{\text{2}}\right)|\,\pi_{D}(\mathbf{q}_{k})\right].$
(26)

The total reward, obtained evaluating Eq. (VI) over a horizon of $w$ frames,
is equal to Eq. (21). Therefore, the objective of the MDP is equal to the
objective of Eq. (21).

Value iteration algorithms solve the MDP optimization recursively computing a
value function $J$ based on the Bellman’s equation [29]. The optimal value
function $J(\mathbf{q}_{k})$ given a state $\mathbf{q}_{k}$ is

$\displaystyle J_{k}(\mathbf{q}_{k})=$
$\displaystyle\,\underset{\pi_{D}\in\Pi_{D}}{\text{maximize}}\,\,\,\,r_{k}(\mathbf{q}_{k},\pi_{D}(\mathbf{q}_{k}))\,+$
$\displaystyle\sum_{\mathbf{q}_{k+1}\in\mathcal{Q}_{k+1}}{\mathbb{P}}\\{\mathbf{q}_{k+1}|\mathbf{q}_{k},\pi_{D}(\mathbf{q}_{k})\\}J_{k+1}(\mathbf{q}_{k+1}),$
(27)

where $\mathbb{P}\\{\mathbf{q}_{k+1}|\mathbf{q}_{k}\pi_{D}(\mathbf{q}_{k})\\}$
is the transition probability from state $\mathbf{q}_{k}$ to state
$\mathbf{q}_{k+1}$ in one time step using $\pi_{D}(\mathbf{q}_{k})$,
$\mathcal{Q}_{k+1}$ denotes the set of all states reachable from
$\mathbf{q}_{k}$ with one time step transition.

By the construct of the MDP, it is easy to see that $\pi_{D}^{\star}$ is
optimal for Eq. (21) which is stated in the following theorem.

######  Theorem 2.

$\pi_{D}^{\star}$ is throughput optimal, i.e.

$\displaystyle\pi_{D}^{\star}=\underset{\pi_{D}\in\Pi_{D}}{\operatorname*{arg\,max}}\quad{\mathbb{E}}\left[{D}(w)\right].$

For a finite number of states and actions, the optimal policy
$\pi_{D}^{\star}$ for the MDP can be found by computing the optimal value
function in Eq. (27) by backward recursion (cf. [29]). The calculation of the
optimal dynamic scheduling policy satisfying Theorem 2 can be performed using
the finite-horizon value iteration algorithm. For each epoch $k$ until the
deadline $w$ and state $\mathbf{q}_{k}$, the value function in Eq. (27) is
computed for all possible actions. Therefore, computing the optimal dynamic
policy requires $\mathcal{O}\left(\left(N+1\right)|\mathcal{Q}|w\right)$
operations. We note that optimal actions for all the states in $\mathcal{Q}$
can be computed a priori and stored in a table, and for a queue state observed
in a frame the corresponding optimal action can be retrieved from the table.

##  VII Performance Evaluation of Semi-static and Dynamic Scheduling Policies

In this section, the performance of semi-static and dynamic scheduling
policies are evaluated numerically. The evaluations leverage C, Matlab™ and
python to compute the performance of, respectively, semi-static and dynamic
policies and comparison baselines. We evaluate the schemes for variations in
several main system parameters: (1) Different initial queue backlogs
$x_{1},x_{2}$; (2) Application deadlines $w$; (3) Number of slots per frame
$N$; and (4) Average service PERs $p_{e}$. In Sec. VII-A, we present first a
performance comparison of purely semi-static scheduling policies. In Sec.
VII-B, we then move to purely dynamic policies. Finally, in Sec. VII-C, we
present results on the performance gap between the proposed semi-static and
dynamic scheduling policies.

Figure 4: DVP achieved by semi-static schedulers for different deadlines $w$,
increasing backlogs $x_{1},x_{2}$, $N=4$, $p_{e}=0.2$.

Figure 5: DVP achieved by semi-static schedulers for different frame sizes
$N$, increasing backlogs $x_{1},x_{2}$, $w=5$, $p_{e}=0.2$.

Figure 6: DVP achieved by semi-static schedulers for different backlogs
$x_{1}$ and deadlines $w$, $x_{2}=1$, $N=4$, $p_{e}=0.2$.

Figure 7: DVP achieved by semi-static schedulers for different backlogs
$x_{2}$ and deadlines $w$, $x_{1}=1$, $N=4$, $p_{e}=0.2$.

###  VII-A Semi-static Scheduling Policies

As discussed, semi-static scheduling policies in this work take the initial
queue state at the moment of the arrival of a time-critical packet into
account. The semi-static schedule is then determined prior to the transmission
of the corresponding packet and defines the allocation of slots until the
deadline of the packet. We compare the DVP achieved by the proposed WTB-W
scheduler, cf. Sec. V, with the exhaustive search methods eDVPUB and Optimum,
which compute semi-static policies, respectively, evaluating Eq. (8) and via
simulations. Due to its high complexity, the performances of the optimal
policy is shown for smaller parameter sets. Exhaustive schemes are shown to
evaluate the performance of WTB-B and do not represent a feasible way of
computing semi-static scheduling policies. The last comparison scheme is a
agnostic allocation of half of the slots for uplink and half of the slots for
downlink transmission. We refer to this scheme as 50/50333In the case of an
odd number of slots, one extra slot is allocated to the first link..
Throughout the evaluation of the semi-static schemes, we keep the channel
error rate $p_{e}$ at $0.2$.

Fig. 5 shows the DVP for different application deadlines, backlogs, while the
frame configuration is fixed with $N$ $=$ $4$. WTB-W and eDVPUB achieve close-
to-optimal DVP for all backlog sizes and deadlines. Thus, taking the initial
queue states into account is beneficial and provides up to one order of
magnitude improvement compared to the agnostic 50/50 scheme. As the deadline
$w$ increases, the performance gap of the proposed polices in comparison to
the 50/50 scheme increases. For backlogs $x_{1}$ and $x_{2}$ equaling $1$,
eDVPUB provides a minor improvement in DVP with respect to WTB-W at the
expense of higher computational complexity, while for higher backlogs, the
performance difference between the two is negligible.

In Fig. 5 we study the impact of different frame lengths, backlogs, while
keeping the deadline fixed with $w$ $=$ $5$. Again, the improvement in DVP of
the proposed semi-static schedulers with respect to the agnostic 50/50 scheme
is confirmed. The “stepped” behaviour of the 50/50 scheme is caused by the
different ratios of allocated slots to the two links for even and odd frame
lengths. Otherwise, the results show a minor difference between WTB-W and
eDVPUB, while the optimality gap increases slightly for increasing $N$ when
$x_{1}$ and $x_{2}$ are equal to $1$.

Fig. 7 and Fig. 7 show the impact of initial backlog on the DVP for different
deadlines and a fixed frame configuration with $N$ $=$ $4$. Increasing $x_{1}$
has a stronger impact than $x_{2}$ on the achievable DVP. This is intuitive as
packets backlogged in $x_{1}$ must be sent by both links. We note that the gap
between the proposed semi-static schedulers and the agnostic 50/50 scheme
increases with an increasing backlog $x_{2}$. In both figures, we observe
again that exploiting the initial queue states leads to a gain of
approximately half order of magnitude with respect to the agnostic 50/50
scheme with increasing initial backlogs. As shown in Fig. 7, eDVPUB achieves
near-optimal DVP and the performance gap with respect to WTB-W is constant
with increasing $x_{1}$. In contrast, in Fig. 7, the gap between the proposed
schedulers and the optimal policy decreases with increasing $x_{2}$, achieving
close-to-optimal DVP.

Figure 8: DVP achieved by dynamic schedulers for different deadlines $w$,
increasing backlogs $x_{1},x_{2}$, $N=6$, $p_{e}=0.4$.

Figure 9: DVP achieved by dynamic schedulers for different frame sizes $N$,
increasing backlogs $x_{1},x_{2}$, $w=6$, $p_{e}=0.4$.

Figure 10: DVP achieved by dynamic schedulers for different backlogs $x_{1}$
and deadlines $w$, $x_{2}=1$, $N=4$, $p_{e}=0.4$.

Figure 11: DVP achieved by dynamic schedulers for different backlogs $x_{2}$
and deadlines $w$, $x_{1}=1$, $N=4$, $p_{e}=0.4$.

###  VII-B Dynamic Scheduling Policies

In contrast to the semi-static schemes, dynamic schedulers benefit from
feedback on the queue states as time evolves, giving them the opportunity to
reallocate time slots depending on the queue’s backlog evolution. This makes
dynamic schedulers causing more overhead and complexity, with the advantage of
potentially achieving a higher performance. Initially, we are only turning to
different dynamic schedulers in this section. Concretely, we consider the
following schemes:

  * •

MDP: Our proposed dynamic scheduler from Section VI.

  * •

Max Weight (MW): Under MW, all slots are allocated to the link with the
maximum backlog [9].

  * •

Weighted-Fair Queuing (WFQ): Under WFQ, slots are allocated to the links in
proportion to the ratio between their queue sizes [10].

  * •

Backpressure (BP): Under BP, slots are allocated to the link with maximum
backpressure, where the backpressure at the first link is equal to
$x_{1}-x_{2}$ while at the second link it is equal to $x_{2}$ [8].

In all the figures below, the value of $p_{e}$ is set to $0.4$.

Fig. 9 shows the DVP achieved by the dynamic schedulers for different
application deadlines, backlogs, and a fixed frame configuration with $N$ $=$
$6$. We observe that the proposed MDP-based scheduler outperforms all the
other methods. BP and MW achieve higher DVP as they allocate all the slots to
a single link in each frame. Similar to MDP, WFQ allows a granular allocation
of slots to the links and achieves the smallest performance gap.

Fig. 9 presents DVP achieved by different policies for different frame
lengths, backlogs, and a fixed deadline $w$ $=$ $6$. Again, MDP achieves lower
DVP while the performances of the other schemes are in line with the previous
scenario. Furthermore, the performance advantage of MDP, with respect to the
comparison schemes, increases with increasing frame length. This advantage
arises from the fact that the action space of MDP is larger for large $N$,
which results in more accurate slot allocations.

Figure 12: DVP achieved by semi-static and dynamic schedulers for different
deadlines $w$, increasing backlogs $x_{1},x_{2}$, $N=6$, $p_{e}=0.4$.

Figure 13: DVP achieved by semi-static and dynamic schedulers for different
frame sizes $N$, increasing backlogs $x_{1},x_{2}$, $w=6$, $p_{e}=0.4$.

Figure 14: DVP achieved by semi-static and dynamic schedulers for different
backlogs $x_{1}$ and deadlines $w$, $x_{2}=1$, $N=6$, $p_{e}=0.4$.

Figure 15: DVP achieved by semi-static and dynamic schedulers for different
backlogs $x_{2}$ and deadlines $w$, $x_{1}=1$, $N=6$, $p_{e}=0.4$.

Fig. 11 and Fig. 11 show the impact of the initial backlogs on the DVP
achieved by different policies for different deadlines and with a fixed frame
configuration $N$ $=$ $4$. Again, increasing $x_{1}$ has a higher impact on
DVP compared to $x_{2}$. Due to the allocation of all slots to a link in a
frame, the performance gap of BP and MW increases as $x_{1}$ and $x_{2}$
increase. WFQ, however, maintains a constant gap, being able to adapt the
allocations to different initial backlog scenarios.

###  VII-C Impact of Network State Information

A direct comparison of the proposed semi-static and dynamic scheduling
policies allows to quantify the performance improvement achieved by exploiting
up-to-date queue states. In the following we limit this comparison to the
proposed schemes of this paper, WTB-W and MDP, and additionally show eDVPUB to
represent the close-to-optimal performances of semi-static policies.
Therefore, the semi-static schemes WTB-W and eDVPUB are benchmarked with the
dynamic MDP scheme. In all following figures, the value of $p_{e}$ is set to
$0.4$.

In Fig. 13 the DVP achieved by the proposed scheduling policies is presented
for different deadlines, backlogs, and fixed frame configuration $N$ $=$ $4$.
Most importantly, we witness a significant performance advantage of MDP in
comparison to WTB-W and eDVPUP. This advantage increases with increasing
deadlines, reaching multiple orders of magnitudes. This effect is intuitive
as, at each frame, dynamic scheduling benefits from up-to-date queue states. A
similar effect can be observed in Fig. 13 where the DVP performance is shown
for different frame lengths, backlogs, and a fixed deadline $w$ $=$ $6$.
Finally, Fig. 15 and 15 show the impact of initial backlog on the DVP for
different deadlines and a fixed frame configuration $N$ $=$ $6$. For fixed
system parameters, increasing the initial backlogs results in an increasing
DVP, which translates into smaller performance gaps between semi-static and
dynamic scheduling schemes.

##  VIII Conclusions

In this work, we investigated semi-static and dynamic scheduling policies to
support the feedback-based communication of interactive applications. In
particular, we proposed scheduling policies aimed at minimizing the end-to-end
latency experienced by individual messages traversing the feedback loop, i.e.
the delay from capturing the status information until the point in time when
the corresponding feedback information is exposed. The proposed scheduling
policies allocate time slots to the transmitters in order to minimize the
delay violation probability (DVP) taking the network queue states into
account. On the one hand, _semi-static_ policies compute schedules based on
the initial queue states by efficiently minimizing the WTB, which is derived
applying the union and Chernoff bounds. On the other hand, _dynamic_ policies
solve a throughput-optimal MDP, which allocates time slots depending on the
queue’s backlog evolution. Via simulations of several main system parameters
and comparison baselines, we demonstrate the effectiveness of the proposed
methods in reducing DVP. The results show that the proposed WTB-W semi-static
scheduling policy achieves up to one order of magnitude improvement compared
to a queue-agnostic scheme and close-to-optimal DVP. Furthermore, simulations
prove the superiority of the proposed MDP dynamic scheduler in reducing DVP
compared to the existing Backpressure, Max Weight, and Weighted-Fair Queuing
algorithms. Finally, we quantified the performance improvement achieved by
exploiting up-to-date queue states with a direct comparison of the proposed
semi-static and dynamic scheduling policies. MDP achieves a significant
performance advantage in comparison to WTB-W reaching multiple orders of
magnitude.

The contributions of this paper leave space for interesting future work. The
proposed scheduling policies can be investigated for more complex systems, for
instance taking into account flow transformation within the feedback loop,
asymmetric transmitter PERs, and non-stationary link qualities. Furthermore,
the problem can be extended considering multiple feedback loops sharing the
same network, thus minimizing the DVP of packets from multiple applications.
Finally, an interesting next step is to investigate the application of the
proposed scheduling policies in the existing wireless systems, such as NCS
operating in IWSN or in 5G cellular networks.

###  -A Proof of Proposition 1

Combining (10) and (11), the DVP can be calculated as

$\displaystyle\IEEEeqnarraymulticol{3}{l}{\text{DVP}(w,y,x_{1},x_{2})=}$
$\displaystyle=$ $\displaystyle{\mathbb{P}}\\{{D}(w)<y+x_{1}+x_{2}\\}$
$\displaystyle=$ $\displaystyle{\mathbb{P}}\left\\{\underset{0\leq u\leq
w}{\min}\left[{S}^{2}(w-u)+{A}^{2}(u)<y+x_{1}+x_{2}\right]\right\\}$
$\displaystyle=$ $\displaystyle{\mathbb{P}}\Big{\\{}\underset{0\leq u\leq
w}{\min}\left[{S}^{2}(w-u)+{D}^{1}(u-1)+x_{2}\right]$
$\displaystyle\qquad\qquad\qquad<y+x_{1}+x_{2}\Big{\\}}$ $\displaystyle=$
$\displaystyle{\mathbb{P}}\Big{\\{}\\!\left\\{{S}^{2}(w)\\!<\\!y+x_{1}+x_{2}\right\\}\cup\left\\{{S}^{2}(w-1)\\!<\\!y+x_{1}\right\\}\cup$
$\displaystyle\quad\bigcup_{u=2}^{w}\big{\\{}\underset{0\leq v\leq
u-1}{\min}[{S}^{2}(w-u)+{S}^{1}(u-1-v)+$
$\displaystyle\qquad\qquad\qquad{A}(v)<y+x_{1}]\big{\\}}\Big{\\}}$
$\displaystyle=$
$\displaystyle{\mathbb{P}}\Big{\\{}\\!\left\\{{S}^{2}(w)\\!<\\!y+x_{1}+x_{2}\right\\}\cup\left\\{{S}^{2}(w-1)\\!<\\!y+x_{1}\right\\}\cup$
$\displaystyle\quad\bigcup_{u=2}^{w}\left\\{{S}^{2}(w-u)+{S}^{1}(u-1)<y+x_{1}\right\\}\Big{\\}}.$

###  -B Proof of Theorem 1

To simplify the analysis of Eq. (17), we use $\alpha=(1-p_{e})e^{-s}+p_{e}$
and $\beta=k_{a}+x_{1}-1$

$\displaystyle\text{WTB}(\mathbf{n}^{2})$ $\displaystyle=$
$\displaystyle\min_{s>0}\alpha^{\sum_{i=0}^{w}n^{i}}e^{s\,(\beta+x_{2})}+$
(28)
$\displaystyle\sum_{u=1}^{1+w}\alpha^{(u-1)N-\sum_{j=0}^{u-2}n^{j}+\sum_{k=0}^{w-u}n^{k}}e^{s\,\beta}$
$\displaystyle=$
$\displaystyle\min_{s>0}e^{s\,\beta}\Bigg{[}\alpha^{\sum_{i=0}^{w}n^{i}}e^{sx_{2}}+$
$\displaystyle\sum_{u=1}^{1+w}\alpha^{(u-1)N-\sum_{j=0}^{u-2}n^{j}+\sum_{k=0}^{w-u}n^{k}}\Bigg{]}.$

Applying the definition of convexity to Eq. (28),
$\forall\mathbf{n},\mathbf{m}\in\mathbb{N}^{1\times
w},\lambda\in\left[0,1\right]$ we obtain Eq. (29). From Eq. (29), (1) we have
applied the definition of convexity to the exponentials
$\alpha^{f(\lambda\mathbf{n^{1}}+(1-\lambda)\mathbf{n^{2}})}$ knowing that
they are convex and (2) we have used the fact that the minimum of the sum is
smaller or equal of the sum of the minima.

$\displaystyle\text{WTB}\left(\lambda\mathbf{n}+(1-\lambda)\mathbf{m}\right)$
$\displaystyle=\min_{s>0}e^{s\,\beta}\left[\alpha^{\sum_{i=0}^{w}\lambda
n^{1}_{i}+(1-\lambda)n^{2}_{i}}e^{sx_{2}}+\sum_{u=1}^{1+w}\alpha^{(u-1)N-\sum_{j=0}^{u-2}\lambda
n^{1}_{j}+(1-\lambda)n^{2}_{j}+\sum_{k=0}^{w-u}\lambda
n^{1}_{k}+(1-\lambda)n^{2}_{k}}\right]$
$\displaystyle\stackrel{{\scriptstyle\text{(1)}}}{{\leq}}\min_{s>0}e^{s\,\beta}\left[e^{sx_{2}}\left(\lambda\alpha^{\sum_{i=0}^{w}n^{1}_{i}}+(1-\lambda)\alpha^{\sum_{i=0}^{w}n^{2}_{i}}\right)+\right.$
$\displaystyle\left.\qquad\qquad\quad\sum_{u=1}^{1+w}\alpha^{(u-1)N}\left(\lambda\alpha^{-\sum_{j=0}^{u-2}n^{1}_{j}}+(1-\lambda)\alpha^{-\sum_{j=0}^{u-2}n^{2}_{j}}+\lambda\alpha^{\sum_{k=0}^{w-u}n^{1}_{k}}+(1-\lambda)\alpha^{\sum_{k=0}^{w-u}n^{2}_{k}}\right)\right]$
$\displaystyle=\min_{s>0}e^{s\,\beta}\left[\lambda\left(\alpha^{\sum_{i=0}^{w}n^{1}_{i}}e^{sx_{2}}+\sum_{u=1}^{1+w}\alpha^{(u-1)N}\alpha^{-\sum_{j=0}^{u-2}n^{1}_{j}}\alpha^{-\sum_{j=0}^{u-2}n^{1}_{j}}\right)+\right.$
$\displaystyle\left.\qquad\qquad\quad(1-\lambda)\left(\alpha^{\sum_{i=0}^{w}n^{2}_{i}}e^{sx_{2}}+\sum_{u=1}^{1+w}\alpha^{(u-1)N}\alpha^{-\sum_{j=0}^{u-2}n^{2}_{j}}\alpha^{-\sum_{j=0}^{u-2}n^{2}_{j}}\right)\right]$
$\displaystyle\stackrel{{\scriptstyle\text{(2)}}}{{\leq}}\lambda\min_{s>0}e^{s\,\beta}\left[\alpha^{\sum_{i=0}^{w}n^{1}_{i}}e^{sx_{2}}+\sum_{u=1}^{1+w}\alpha^{(u-1)N}\alpha^{-\sum_{j=0}^{u-2}n^{1}_{j}}\alpha^{-\sum_{j=0}^{u-2}n^{1}_{j}}\right]+$
$\displaystyle\quad(1-\lambda)\min_{s>0}e^{s\,\beta}\left[\alpha^{\sum_{i=0}^{w}n^{2}_{i}}e^{sx_{2}}+\sum_{u=1}^{1+w}\alpha^{(u-1)N}\alpha^{-\sum_{j=0}^{u-2}n^{2}_{j}}\alpha^{-\sum_{j=0}^{u-2}n^{2}_{j}}\right]$
$\displaystyle=\lambda\text{WTB}\left(\mathbf{n}\right)+(1-\lambda)\text{WTB}\left(\mathbf{m}\right).$
(29)

## Acknowledgment

This work was supported by the DFG Priority Programme 1914 grant number
KE1863/5-1.

## References

  * [1] W. Saad, M. Bennis, and M. Chen, “A Vision of 6G Wireless Systems: Applications, Trends, Technologies, and Open Research Problems,” _IEEE Network_ , vol. 34, no. 3, pp. 134–142, 2020.
  * [2] R. Rajkumar, I. Lee, L. Sha, and J. Stankovic, “Cyber-physical systems: The next computing revolution,” in _Design Automation Conference_ , 2010, pp. 731–736.
  * [3] G. Schirner, D. Erdogmus, K. Chowdhury, and T. Padir, “The Future of Human-in-the-Loop Cyber-Physical Systems,” _Computer_ , vol. 46, no. 1, pp. 36–45, 2013.
  * [4] K. Ha, Z. Chen, W. Hu, W. Richter, P. Pillai, and M. Satyanarayanan, “Towards Wearable Cognitive Assistance,” in _Proceedings of the 12th Annual International Conference on Mobile Systems, Applications, and Services_ , 2014, p. 68–81.
  * [5] L. Zhang, H. Gao, and O. Kaynak, “Network-induced constraints in networked control systems-A survey,” _IEEE Transactions on Industrial Informatics_ , vol. 9, no. 1, pp. 403–416, 2013.
  * [6] W. Shi, J. Cao, Q. Zhang, Y. Li, and L. Xu, “Edge Computing: Vision and Challenges,” _IEEE Internet of Things Journal_ , vol. 3, no. 5, pp. 637–646, 2016.
  * [7] J. P. Champati, H. Al-Zubaidy, and J. Gross, “Transient Analysis for Multihop Wireless Networks under Static Routing,” _IEEE/ACM Transactions on Networking_ , vol. 28, no. 2, pp. 722–735, 4 2020.
  * [8] L. Tassiulas and A. Ephremides, “Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks,” in _Proceedings of the IEEE Conference on Decision and Control_ , vol. 4. Publ by IEEE, 1990, pp. 2130–2132.
  * [9] M. J. Neely, “Stochastic network optimization with application to communication and queueing systems,” _Synthesis Lectures on Communication Networks_ , vol. 3, no. 1, 2010.
  * [10] A. K. Parekh and R. G. Gallager, “A generalized processor sharing approach to flow control in integrated services networks: the single-node case,” _IEEE/ACM Transactions on Networking_ , vol. 1, no. 3, June 1993.
  * [11] L. Tassiulas and A. Ephremides, “Dynamic Server Allocation to Parallel Queues with Randomly Varying Connectivity,” _IEEE Transactions on Information Theory_ , vol. 39, no. 2, pp. 466–478, 1993.
  * [12] R. Singh and P. R. Kumar, “Throughput optimal decentralized scheduling of multihop networks with end-to-end deadline constraints: Unreliable links,” _IEEE Transactions on Automatic Control_ , vol. 64, no. 1, pp. 127–142, 1 2019.
  * [13] A. Saifullah, Y. Xu, C. Lu, and Y. Chen, “Real-time scheduling for WirelessHART networks,” in _Proceedings - Real-Time Systems Symposium_ , 2010, pp. 150–159.
  * [14] A. Saifullah, Y. Xu, C. Lu, and Y. Chen, “End-to-End Delay Analysis for Fixed Priority Scheduling in WirelessHART Networks,” in _2011 17th IEEE Real-Time and Embedded Technology and Applications Symposium_ , 2011, pp. 13–22.
  * [15] A. Saifullah, P. Babu Tiwari, B. Li, C. Lu, and P. Babu, “Accounting for Failures in Delay Analysis for WirelessHART Accounting for Failures in Delay Analysis for WirelessHART Networks Networks Recommended Citation Recommended Citation ”Accounting for Failures in Delay Analysis for WirelessHART Networks ” Report,” Tech. Rep., 1 2012.
  * [16] A. Saifullah, Y. Xu, C. Lu, and Y. Chen, “End-to-end communication delay analysis in industrial wireless networks,” _IEEE Transactions on Computers_ , vol. 64, no. 5, pp. 1361–1374, 5 2015.
  * [17] Q. Wang, K. Jaffres-Runser, Y. Xu, and J. L. Scharbarg, “A certifiable resource allocation for real-time multi-hop 6TiSCH wireless networks,” _IEEE International Workshop on Factory Communication Systems - Proceedings, WFCS_ , pp. 1–9, 2017.
  * [18] V. P. Modekurthy, A. Saifullah, and S. Madria, “DistributedHART: A distributed real-time scheduling system for WirelessHART Networks,” in _Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS_ , vol. 2019-April, 4 2019, pp. 216–227.
  * [19] M. Yan, K. Y. Lam, S. Han, E. Chan, Q. Chen, P. Fan, D. Chen, and M. Nixon, “Hypergraph-based data link layer scheduling for reliable packet delivery in wireless sensing and control networks with end-to-end delay constraints,” _Information Sciences_ , vol. 278, 2014.
  * [20] F. Dobslaw, T. Zhang, and M. Gidlund, “End-to-End Reliability-Aware Scheduling for Wireless Sensor Networks,” _IEEE Transactions on Industrial Informatics_ , vol. 12, no. 2, pp. 758–767, 2016.
  * [21] G. Gaillard, D. Barthel, F. Theoleyre, and F. Valois, “High-reliability scheduling in deterministic wireless multi-hop networks,” in _IEEE PIMRC_ , Sep 2016.
  * [22] M. R. Palattella, N. Accettura, M. Dohler, L. A. Grieco, and G. Boggia, “Traffic aware scheduling algorithm for reliable low-power multi-hop ieee 802.15.4e networks,” in _2012 IEEE 23rd International Symposium on Personal, Indoor and Mobile Radio Communications - (PIMRC)_ , 2012, pp. 327–332.
  * [23] Y. Chen, H. Zhang, N. Fisher, L. Y. Wang, and G. Yin, “Probabilistic per-packet real-time guarantees for wireless networked sensing and control,” _IEEE Transactions on Industrial Informatics_ , vol. 14, no. 5, pp. 2133–2145, 5 2018.
  * [24] R. Brummet, D. Gunatilaka, D. Vyas, O. Chipara, and C. Lu, “A Flexible Retransmission Policy for Industrial Wireless Sensor Actuator Networks,” in _Proceedings - 2018 IEEE International Conference on Industrial Internet, ICII 2018_ , 11 2018, pp. 79–88.
  * [25] T. Gong, T. Zhang, X. S. Hu, Q. Deng, M. Lemmon, and S. Han, “Reliable dynamic packet scheduling over lossy real-time wireless networks,” in _Leibniz International Proceedings in Informatics, LIPIcs_ , vol. 133, 7 2019\.
  * [26] P. Soldati, H. Zhang, Z. Zou, and M. Johansson, “Optimal routing and scheduling of deadline-constrained traffic over lossy networks,” in _GLOBECOM - IEEE Global Telecommunications Conference_ , 2010.
  * [27] S. Zoppi, J. P. Champati, J. Gross, and W. Kellerer, “Dynamic Scheduling for Delay-Critical Packets in a Networked Control System Using WirelessHART,” in _ICC 2020 - 2020 IEEE International Conference on Communications (ICC)_ , Jun 2020, pp. 1–7.
  * [28] Y. Jiang, “A Basic Stochastic Network Calculus,” in _Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications_ , Aug 2006.
  * [29] M. L. Puterman, _Markov Decision Processes: Discrete Stochastic Dynamic Programming_. John Wiley & Sons, 1994\.


# Single Crystal Study of Competing Rhombohedral and Monoclinic Order in Lead
Zirconate Titanate

D. Phelan1, X. Long2, Y. Xie2, Z.-G. Ye2, A. M. Glazer3, H. Yokota4, P. A.
Thomas5, P. M. Gehring1 1NIST Center for Neutron Research, National Institute
of Standards and Technology, Gaithersburg, Maryland 20899, USA
2Department of Chemistry, Simon Fraser University, Burnaby, BC, V5A 1S6,
Canada
3Clarendon Laboratory, Department of Physics, University of Oxford, Parks
Road, Oxford OX1 3PU, United Kingdom
4Department of Bioengineering, University of Tokyo, Tokyo 113-8656, Japan
5Department of Physics, University of Warwick, Coventry CV4 7AL, United
Kingdom

###### Abstract

Neutron diffraction data obtained on single crystals of PbZr1-xTixO3 with x =
0.325 and x = 0.460, which lie on the pseudorhombohedral side of the
morphotropic phase boundary, suggest a coexistence of rhombohedral (R3m/R3c)
and monoclinic (Cm) domains and that monoclinic order is enhanced by Ti
substitution. A monoclinic phase with a doubled unit cell (Cc) is ruled out as
the ground state.

A hallmark of highly piezoelectric perovskite materials, such as PbZr1-xTixO3
(PZT), is a morphotropic phase boundary (MPB) that segregates two
compositional regimes into different ferroelectric states and pinpoints the
range of substitutions for which the piezoelectric response is optimal. For
PZT (and other Pb-based materials), the MPB ostensibly divides regions of Ti-
poor rhombohedral (R3m) and Ti-rich tetragonal (P4mm) order. The discovery of
an intermediate monoclinic phase within a narrow compositional range near the
MPB [1,2] provided a mechanism whereby PZT could transform from R3m to P4mm
via a common subgroup, Cm. This led to the idea that enhanced piezoelectricity
at the MPB arises from the freedom of the Pb atom to move within the mirror
plane of the monoclinic phase, thus allowing the electric polarization to
rotate [3,4]. Alternatively, the adaptive-phases model, proposes that the
lower symmetry allows for complex domain structures in which the net
polarization can be made to change direction via domain populations [5]. These
mechanisms remain controversial as how the phase symmetry is transformed
across the phase diagram remains unclarified.

The most recent measurements identify no clear phase boundary between
rhombohedral and monoclinic phases [6]. Instead the anisotropic Pb
displacement ellipsoid is highly flattened perpendicular to the polar
displacement direction, which led to the suggestion that some kind of disorder
[7,8] or local monoclinic displacements [9] are present in the rhombohedral
phases. From this followed the idea that the local symmetries are monoclinic,
but that the coherence lengths are limited to just a few unit cells so that
diffraction methods yield only rhombohedral symmetries for Ti-poor
compositions [10]. While this model is able to explain the lack of an R-M
phase boundary, two different explanations were recently put forth. The first,
based on refinements of synchrotron data, replaces the rhombohedral phases
with a high-temperature monoclinic Cm and a low-temperature monoclinic Cc
phase (the Cc phase superimposes antiferrodistortive displacements with the
ferroelectric displacements of Cm, causing the unit cell to double as depicted
in Ref. [11]) [11,12]. The second, based on a separate set of neutron
diffraction refinements favors a coexistence of rhombohedral R3c and
monoclinic Cm (but not Cc) phases at room temperature in the Ti-poor region
[6]. The present results resolve this issue conclusively.

A hindrance to precise symmetry determination of PZT has been the difficulty
to grow single crystals. Therefore, structural studies near the MPB have been
limited to powders and ceramics. A major problem with Rietveld refinement of
highly pseudosymmetric polycrystalline materials is that many models refine to
similar agreement factors, which makes it nearly impossible to choose between
them. Very recently, single crystals were grown at Simon Fraser University
using a top-seeded solution growth technique. The crystals measured here have
compositions of x = 0.325 (dimensions 3.3 mm $\times$ 2.1 mm $\times$ 1.1 mm)
and x = 0.460 (3.0 mm $\times$ 2.7 mm $\times$ 0.6 mm). The measurements were
performed at the NIST Center for Neutron Research (NCNR) on thermal (BT-9) and
cold (SPINS) triple-axis spectrometers. Various instrumental configurations
were employed and are given in the figure captions. The samples were measured
under vacuum in a closed-cycle helium refrigerator. Miller indices are
expressed with respect to the aristotype cubic cell with a lattice parameter a
$\approx$ 4.1 Å.

Structural transitions in each crystal were characterized by measurements of
the 200 Bragg reflection as a function of temperature (see Fig. 1). For x =
0.325, two phase transitions were identified corresponding to paraelectric-
ferroelectric and ferroelectric-ferroelectric transitions. One occurs near 370
K and is marked by a change in the slope of the temperature dependence of the
rocking curve width, a strong shift in the peak position of the rocking scan,
and a change from positive to negative volume thermal expansion. A second near
590 K is evident from the large change in intensity resulting from a release
of secondary extinction, a leveling out of the width of the rocking curve, and
a return to positive volume thermal expansion. Similar measurements for x =
0.460 revealed more complicated behavior. Possible phase transitions are seen
at 220, 410, 480, 540, and 650 K. Between 480 and 540 K the volume thermal
expansion is $\approx$ 9.1 $\times$ 10-5 1/K, or roughly 1 order of magnitude
larger than normally observed in oxides; above 540 K a steep negative volume
thermal expansion ($\approx$ -4.9 $\times$ 10-5 1/K) is observed. A huge
release of extinction occurs upon cooling below the cubic phase. The large
number of anomalies is consistent with the fact that the crystal has a
composition very close to the MPB. A similarly complex series of phase
transitions has been suggested [13] based on powder neutron data [14].

One approach to identify the structural symmetry is to look for superlattice
peaks that appear when the primitive unit cell is doubled. The R3c phase
generates superlattice reflections that result from correlated rotations of
the oxygen octahedra, but only at the $R_{2}$ points
$\frac{h}{2}\frac{\overline{k}}{2}\frac{k}{2}$, where h and k are odd and h
$\neq$ k (for twinned crystals, $\frac{h}{2}\frac{\overline{k}}{2}\frac{k}{2}$
and $\frac{h}{2}\frac{k}{2}\frac{k}{2}$ are not distinct). This is the only
type of superlattice peak that has been observed in x-ray and neutron powder
diffraction measurements [6,15,16]. Other superlattice reflections have been
observed using electron diffraction methods [15,17-20]; however, these have
been argued to result from surface effects or local inhomogeneities, with only
$R_{2}$ attributed to the bulk [15]. On the other hand, a phase with Cc
symmetry [11,12] would generate weak superlattice reflections at the $R_{1}$
points $\frac{h}{2}\frac{h}{2}\frac{h}{2}$, where h is odd. We looked for
superlattice reflections in the x = 0.325 crystal in the (hk0) and (hkk)
scattering planes at 35 K (see Fig. 2). No peaks were found at the $X$ points
$\frac{1}{2}$00 and $\frac{3}{2}$00, or at the $M$ points
$\frac{1}{2}\frac{1}{2}$0 and $\frac{3}{2}\frac{1}{2}$0, however, several
$R_{2}$ peaks were observed. The order parameter measurement shown in Fig.
2(f) indicates that the $R_{2}$ peaks vanish at the low-temperature phase
transition identified in Fig. 1(a) ($\approx$ 370 K). Weaker $R_{2}$ peaks
were observed in the x = 0.460 crystal that vanish above the lowest transition
temperature identified in Fig. 1(b) ($\approx$ 220 K). We also observed
superlattice peaks at the $R_{1}$ points $\frac{1}{2}\frac{1}{2}\frac{1}{2}$
and $\frac{3}{2}\frac{3}{2}\frac{3}{2}$, which showed temperature dependences
similar to those of the $R_{2}$ points. Because these peaks could be caused by
double scattering as for SrTiO3 [21], we performed a standard test in which
the peak intensity was measured as a function of the neutron wavelength.
Figure 2(e) shows measurements performed with cold neutrons at two different
wavelengths. A very strong $R_{1}$ peak was observed at
$\frac{1}{2}\frac{1}{2}\frac{1}{2}$ when $\lambda$ = 4.045 Å; however, when
the wavelength was increased to 5.222 Å, so that all $R_{2}$ reflections fell
outside the Ewald sphere, this $R_{1}$ peak completely disappeared. Hence, we
can definitively conclude that the observed $R_{1}$ peak results from double
scattering. We have determined with 99% statistical confidence that the
maximum ratio of the peak intensity $\frac{1}{2}\frac{1}{2}\frac{1}{2}$
compared with that of 100 is 0.002% (x = 0.325) and 0.003% (x = 0.460). These
are extremely severe limits: for the refinement listed in Ref. [22], which is
for a sample with x = 0.48 at 10 K, the calculated intensity ratio is 0.13%
(nearly 40 times larger than our limit for x = 0.46), while refinement for a
sample with x = 0:30 at 300 K [23] gives a ratio of 3.8% (more than 1000 times
larger). Therefore, our superlattice survey is consistent with an R3c ground
state and effectively rules out the presence of any phase, such as Cc or even
triclinic symmetry, that would generate $R_{1}$ superlattice peaks for either
sample.

Symmetries were further studied by high resolution radial measurements of
several Bragg reflections, which is possible because the crystals are
multidomain. The 200 reflection can be used to distinguish between Cm and
R3m/R3c phases because it splits into a doublet under Cm but remains a singlet
for R3m/R3c. We achieved extraordinary wave-vector resolution for this peak by
employing a perfect single crystal of Ge as analyzer and exploiting the fact
that the Ge 220 reflection d spacing almost exactly matches that of the PZT
200 Bragg peak. A peculiarity of this special setup is that the radial
linewidth becomes coupled to the sample mosaicity [24], particularly in the
regime where the mosaic spread is less than 20’. As shown in Fig. 3(a), a
narrow radial linewidth was observed at 200 in the cubic phase (640 K) for x =
0.325 that is nonetheless significantly broader than that measured on a single
crystal of SrTiO3. The extra linewidth is well accounted for by the small, but
non-negligible mosaic width of the x = 0.325 PZT crystal (11’) that was
measured under the same conditions in a rocking scan, and which is taken into
account in the resolution calculation. From Fig. 1(a) we know that the mosaic
width increases as the temperature is lowered; thus the 200 radial linewidth
will necessarily broaden as the temperature decreases. Indeed, the 200 radial
linewidth at 450K is 12% broader than that at 640 K, but this agrees almost
perfectly with the resolution calculation for the broadened mosaic width;
hence the radial linewidth of 200 at 450 K is consistent with a resolution-
limited peak as would be expected for R3m. However, at 40 K the peak has
broadened by an additional 10% from its value at 450 K, while our resolution
calculation predicts a change of only 2%. Given the larger intrinsic mosaic
width of the x = 0.460 its 200 reflection was measured using very tight beam
collimations and a conventional PG analyzer, for which the resolution is
essentially decoupled from the mosaic width. These data, shown in Fig. 3(b),
reveal a broadening of 200 as the temperature is lowered that is even larger
than that for x = 0.325.

The broadened 200 Bragg peaks could result from microscopic strain, finite
domain sizes, or a very small Cm distortion [6]. Microscopic strain and
unresolved monoclinic distortions have the same Q dependence and are
impossible to distinguish in our measurements. However, the intrinsically
broad 200 linewidths are consistent with recent neutron powder diffraction
studies that indicate that the best refinements are obtained with a model of
coexisting R3c and Cm phases [6]. It is difficult to extract quantitative
information about the Cm phase because the 200 Bragg peak is only slightly
broader than the instrumental resolution and can be fit in many different
ways. However, we can extract important information about the R3c phase
because it generates a superlattice peak that depends only on the rhombohedral
structural correlations. To this end we measured radial scans through the
$R_{2}$ superlattice peak for both compositions with tight beam collimations
at low temperature, as shown in Fig. 4. The two crystals exhibit markedly
different linewidths: the peak for x = 0.325 is narrow and close to the
resolution limit whereas that for x = 0.460 is severely broadened. A
superposition of two resolution-limited Gaussians cannot reproduce this
broadening. Instead, the broadening implies the presence of either finite
regions of correlated octahedral rotations or microstrain. Generally, there is
no microstrain associated with oxygen octahedral rotations. Thus, the most
likely explanation for the change in linewidth is that the coherence length of
the rotations is diminished. This is an intriguing result, especially when
considered in conjunction with the broadened 200 Bragg peaks, because it
suggests that the structural correlations in PZT gradually evolve with Ti
content from being predominantly longrange rhombohedral for compositions far
from the MPB to being predominantly long-range monoclinic for compositions
close to the MPB.

The radial line shapes of 200, the appearance of superlattice peaks at $R_{2}$
points at low temperature, and the absence of superlattice peaks at R1 points
are consistent with a purely R3m high-temperature ferroelectric phase for x =
0.325 and coexisting (R3m) and (Cm) phases for x = 0.460, and coexisting R3c
and Cm ground-state ferroelectric phases for both compositions. In addition,
the marked broadening of the superlattice peak at
$\frac{3}{2}\frac{1}{2}\frac{1}{2}$, which is generated by R3c symmetry,
suggests a scenario of competing rhombohedral and monoclinic order in highly
piezoelectric compositions in which the rhombohedral correlations become
increasingly short-range upon approaching the MPB. This picture lends support
to the recent theoretical ideas that the tendency to form macroscopic
monoclinic phases facilitates the mechanism of polarization rotation [25],
achieved either by having the freedom to change the direction of Pb
displacements within monoclinic unit cells or through the change in the
population of twinned monoclinic components under an applied stress or
electric field. The elucidation of the correct symmetries of PZT close to the
MPB is critical to the theory of the origin of the high piezoelectricity in
this and other materials, since it affects the discussion of the numbers and
types of microdomains expected as well as the microscopic mechanisms for
polarization rotation.

A. M. G. and P. A. T. are grateful for funding from the Engineering and
Physical Sciences Research Council (EPSRC) and from the National Science
Foundation (NSF). X. L., Y. X, and Z.-G.Y. acknowledge support from the U.S.
Office of Naval Research (Grant No. N00014-06-1- 0166). This work utilized
facilities supported in part by the NSF under Agreement No. DMR-0944772.

## References

  * Noheda et al. (2000) B. Noheda, D. E. Cox, G. Shirane, R. Guo, B. Jones, and L. E. Cross, Phys. Rev. B 63, 014103 (2000).
  * Noheda et al. (1999) B. Noheda, D. E. Cox, G. Shirane, J. A. Gonzalo, L. E. Cross, and S. E. Park, Appl. Phys. Lett. 74, 2059 (1999).
  * Bellaiche et al. (2000) L. Bellaiche, A. Garcia, and D. Vanderbilt, Phys. Rev. Lett. 84, 5427 (2000).
  * Fu and Cohen (2000) H. Fu and R. E. Cohen, Nature (London) 403, 281 (2000).
  * Jin et al. (2003) Y. M. Jin, Y. U. Wang, A. G. Khachaturian, J. Li, and D. Viehland, J. Appl. Phys. 94, 3629 (2003).
  * Yokota et al. (2009) H. Yokota, N. Zhang, A. E. Taylor, P. A. Thomas, and A. M. Glazer, Phys. Rev. B 80, 104109 (2009).
  * Mabud (1980) S. A. Mabud, J. Appl. Crystallogr. 13, 211 (1980).
  * Glazer et al. (1978) A. M. Glazer, S. A. Mabud, and R. Clarke, Acta Cryst. B 34, 1060 (1978).
  * Corker et al. (1998) D. L. Corker, A. M. Glazer, R. W. Whatmore, A. Stallard, and F. Fauth, J. Phys. Condens. Matter 10, 6251 (1998).
  * Glazer et al. (2004) A. M. Glazer, P. A. Thomas, K. Z. Baba-Kishi, G. K. H. Pang, and C. W. Tai, Phys. Rev. B 70, 184123 (2004).
  * Pandey et al. (2008) D. Pandey, A. K. Singh, and S. Baik, Acta Crystallogr. Sect. A 64, 192 (2008).
  * Hatch et al. (2002) D. M. Hatch, H. T. Stokes, R. Ranjan, Ragini, S. K. Mishra, D. Pandey, and B. J. Kennedy, Phys. Rev. B 65, 212101 (2002).
  * Frantii (2008) J. Frantii, J. Phys. Chem. B 112, 6521 (2008).
  * Frantii et al. (2003) J. Frantii, S. Eriksson, S. Hull, V. Lantto, H. Rundlof, and M. Kakihana, J. Phys. Condens. Matter 15, 6031 (2003).
  * Ricote et al. (1998) J. Ricote, D. L. Corker, R. W. Whatmore, S. A. Impey, A. M. Glazer, J. Dec, and K. Roleder, J. Phys. Condens. Matter 10, 1767 (1998).
  * Pandey and Ragini (2003) D. Pandey and Ragini, Z. Kristallogr. 218, 1 (2003).
  * Viehland (1995) D. Viehland, Phys. Rev. B 52, 778 (1995).
  * Dai et al. (1995) X. Dai, Z. Xu, and D. Viehland, J. Am. Ceram. Soc. 78, 2815 (1995).
  * Noheda et al. (2002) B. Noheda, L. Wu, and Y. Zhu, Phys. Rev. B 66, 060103 (2002).
  * Ragini et al. (2001) Ragini, S. K. Mishra, D. Pandey, H. Lemmens, and G. Van Tendeloo, Phys. Rev. B 64, 054101 (2001).
  * Shirane et al. (2002) G. Shirane, S. M. Shapiro, and J. M. Tranquada, _Neutron scattering with a triple-axis spectrometer_ (Cambridge University Press, Cambridge, England, 2002).
  * Ranjan et al. (2005) R. Ranjan, A. K. Singh, Ragini, and D. Pandey, Phys. Rev. B 71, 092101 (2005).
  * (23) D. Pandey, Private Communication.
  * Xu et al. (2004) G. Xu, P. M. Gehring, V. J. Ghosh, and G. Shirane, Acta Crystallogr. Sect. A 60, 598 (2004).
  * Bell (2006) A. J. Bell, J. Mater. Sci. 41, 13 (2006).

Figure Captions:

Fig. 1:
Temperature dependence of the 200 Bragg reflection for (a) x = 0.325 and (b) x
= 0.460. Shown are the integrated intensity, full-width-at-half-maximum
(FWHM), and peak position ($\omega_{s}$) of Gaussian fits to rocking
(transverse) scans through the Bragg peak. Also shown is the average unit cell
volume (aristotype) determined from Gaussian fits to radial scans through the
Bragg peak. Apparent phase transition temperatures are marked by dashed lines.
Error bars correspond to uncertainties of 1$\sigma$ in the fitted parameters.
Measurements were performed on BT-9 with horizontal beam collimations of
40’-47’-40’-80’ and a single PG filter.

Fig. 2:
(a)-(c) Radial scans through the $X$, $M_{1}$, and $M_{2}$ points reveal no
superlattice reflections for x = 0.325 at 35 K. (d) Scans through one $R_{2}$
point at various temperatures for x = 0.325. (e) Scans performed using two
wavelengths through an $R_{1}$ point for x = 0.325. (f) The order parameters
of the superlattice phases are given by the peak intensity of the
$\frac{5}{2}\frac{1}{2}\frac{1}{2}$ reflection. Error bars represent an
uncertainty of 1$\sigma$ in the measured intensities. Scans in (a)-(d) and (f)
were made using collimations of 40’-47’-40’-80’, 3 PG filters, and $\lambda$ =
2.359 Å on BT-9. The scans in (e) were made on SPINS with collimations of
80’-80’ and two Be filters.

Fig. 3:
(a) Radial scans through the 200 Bragg reflection of the x = 0.325 crystal at
selected temperatures. The measurements were performed on BT-9 with $\lambda$
= 2.359 Å, collimations of 15’-47’-10’-20’, a single PG filter, and the Ge 220
analyzer. Also shown is a measurement of single crystal SrTiO3 (data from Ref.
[24] represented by green triangles) obtained with collimations of
10’-40’-20’-40’. (b) Radial scans through 200 for the x = 0.460 crystal using
the PG 002 analyzer, 3 PG filters, and collimations of 15’-10’-10’-10’.

Fig. 4:
High resolution radial scans performed through the $R_{2}$ point on SPINS
using collimations of G (39’)- 40’-10’-20’, two Be filters, and with $\lambda$
= 4.045 Å.