# Maximum Eigenvalue Detection based Spectrum Sensing in RIS-aided System with
Correlated Fading

Nikhilsingh Parihar, Praful D. Mankar, and Sachin Chaudhari.

###### Abstract

Robust spectrum sensing is crucial for facilitating opportunistic spectrum
utilization for secondary users (SU) in the absense of primary users (PU).
However, propagation environment factors such as multi-path fading, shadowing,
and lack of line of sight (LoS) often adversely affect detection performance.
To deal with these issues, this paper focuses on utilizing reconfigurable
intelligent surfaces (RIS) to improve spectrum sensing in the scenario wherein
both the multi-path fading and noise are correlated. In particular, to
leverage the spatially correlated fading, we propose to use maximum eigenvalue
detection (MED) for spectrum sensing. We first derive exact distributions of
test statistics, i.e., the largest eigenvalue of the sample covariance matrix,
observed under the null and signal present hypothesis. Next, utilizing these
results, we present the exact closed-form expressions for the false alarm and
detection probabilities. In addition, we also optimally configure the phase
shift matrix of RIS such that the mean of the test statistics is maximized,
thus improving the detection performance. Our numerical analysis demonstrates
that the MED’s receiving operating characteristic (ROC) curve improves with
increased RIS elements, SNR, and the utilization of statistically optimal
configured RIS.

###### Index Terms:

Reconfigurable Intelligent Surfaces, Spectrum Sensing, Maximum Eigenvalue
Detector, Correlated Fading, etc.

††N. Parihar, P. D. Mankar, and S. Chaudhari are associated with Signal
Processing and Communication Research Centre, International Institute of
Information Technology Hyderabad (IIITH), India. Email:
<EMAIL_ADDRESS><EMAIL_ADDRESS>and
<EMAIL_ADDRESS>
##  I Introduction

Reconfigurable Intelligent Surfaces (RIS) are emerging as a viable solution
for next-generation wireless communication systems due to their ability to
provide reliable links, offering several advantages like extended coverage,
high data rates, and enhanced sensing abilities. RIS comprises a low-cost
uniform planar array (UPA) with numerous sub-wavelength-sized passive
metamaterial elements. These elements can adjust their physical properties
dynamically, allowing them to induce phase shifts in reflected signals. Such
property enables RIS to control the wireless propagation environment between
transmitter and receiver partially [1, 2, 3, 4]. This makes RIS attractive for
reliable communication and for enabling efficient sensing and localization [3,
5]. This paper aims to utilize the RIS for designing a robust spectrum sensing
technique to facilitate dynamic spectrum management in cognitive radio (CR)
networks.

###  I-A Related Works

Over the past two decades, significant research endeavors have been dedicated
to designing efficient spectrum sensing techniques in the literature for
conventional wireless communication systems. These techniques encompass energy
detection (ED), maximum eigenvalue detection (MED), matched filtering (MF),
and cyclostationary detection (CD). However, in such conventional
communication setups, achieving a high detection probability often
necessitates a large number of observation samples, especially when the number
of antennas at both the transmitter and receiver is limited and the wireless
fading is severe. Consequently, this limitation restricts the opportunistic
utilization of spectrum as a significant portion of the time is spent for
sensing the spectrum [6]. This problem can be solved by using an RIS for
spectrum sensing because of its ability to control the fading environment by
providing a reliable indirect link.

In this direction, a few papers study the benefits of using RIS for spectrum
sensing. For instance, [7] investigates RIS-enhanced ED for spectrum sensing.
Therein, the authors employ the Gamma distribution approximation and central
limit theorem to derive the closed-form expressions for the probability of
detection. The authors of [8] study the impact of active and passive RIS-aided
ED for spectrum sensing. The authors also analyze the number of configurations
and how many reflecting elements are needed for active and passive RIS to
achieve a detection probability close to 1. In [9], a RIS-aided weighted ED
(WED) is studied for spectrum sensing wherein the IRS reflection is considered
to dynamically change over time according to a designed codebook to vary the
received signal at the SU substantially. The analyses presented in [8] and [9]
heavily rely on the Gaussian approximation of test statistics, assuming a
large number of samples are available for sensing.

On the other hand, the authors of [10] employ MED scheme for spectrum sensing
using RIS under correlated fading, wherein the largest eigenvalue of the
sample covariance matrix of observed samples is used as the test statistics.
Similarly, the authors of [11] apply MED for spectrum sensing under correlated
noise. MED performs better than ED when the observed signal exhibits
correlation [12]. However, applying MED leads to deriving the distribution of
the largest eigenvalue of the sample covariance matrix that depends on the
system under consideration. The authors of [10, 11] show the resemblance of
the sample covariance matrix with the single spiked model from random matrix
theory and invoke the application of asymptotic distribution of largest
eigenvalue from [13] to obtain the detection and false alarm probabilities in
the asymptotic region where the number of antennas at SU and the number of
observation approaches to infinity. However, assuming the large number of
antennas at the SU is impractical, and the large number of observation samples
defeats the purpose of using RIS for efficient sensing, as discussed above.
Moreover, as mentioned earlier, the analyses mainly rely on the large
dimensional system, allowing for the convenient application of the law of
large numbers or asymptotic results to make the analysis tractable. However,
these analyses may merely serve as approximations for practical systems in
which the number of antennas and observations is small or moderate. Motivated
by this, our focus in this paper is to provide exact performance
characterization of MED for RIS-aided spectrum sensing.

###  I-B Contributions

This paper aims to design an efficient spectrum sensing for RIS-aided CR
networks. In particular, we consider sensing of a single antenna PU at the SU
equipped with multiple antennas and assisted by RIS. The SU is assumed to be
capable of configuring RIS phase shifts to improve the test statistics for the
detection. The main contributions of this paper are listed below.

  1. 1.

This paper proposes MED for spectrum sensing for RIS-aided CR networks in the
presence of correlated fading and correlated noise.

  2. 2.

The exact distribution of the largest eigenvalue of the central Wishart matrix
is derived, which is then used to obtain the proposed MED’s detection and
false alarm probabilities.

  3. 3.

We also present an approach to configure RIS phase shift optimally to maximize
the expected test statistics, i.e., the largest eigenvalue of the received
sample covariance matrix, under signal present hypothesis.

  4. 4.

Our numerical analysis demonstrates that increasing the number of RIS elements
and configuring RIS phase shifts optimally will enhance the ROC. Additionally,
we also demonstrate that the detection probability of MED approaches $1$ for a
moderate number of RIS elements, especially with optimally configured RIS.

##  II System Model

This paper considers a wireless communication system comprising a single-
antenna PU, an SU with $M$ antennas, and a RIS with $N$ elements, as shown in
Fig. 1. Considering that the RIS is deployed to enhance the spectrum sensing
capability, it is reasonable to assume that the RIS is strategically placed
such that it provides a strong LoS link to SU. Hence, we can model the channel
array response between the RIS and SU as [14]

$\displaystyle\mathbf{H}=\left[\mathbf{a}\left(\cos{\phi},N_{x}\right)\otimes\mathbf{a}\left(\sin{\phi}\cos{\varphi},N_{y}\right)\right]\mathbf{a}\left(\theta,M\right)^{T},$
$\displaystyle\text{where}\leavevmode\nobreak\ \leavevmode\nobreak\
\mathbf{a}\left(x,q\right)=q^{-\frac{1}{2}}\left[1,\leavevmode\nobreak\
e^{jx},\dots,\leavevmode\nobreak\ e^{j(q-1)x}\right]^{T},$

Figure 1: Illusration of the RIS-aided spectrum sensing system involving
single antenna PU, a RIS equipped with N elements and M antenna elements at
SU.

is a steering vector, $\otimes$ is the Kronecker product, $N_{x}$ and $N_{y}$
are the number of RIS elements placed horizontally and vertically,
respectively, such that $N_{x}\times N_{y}=N$. The $\phi$ and $\varphi$ are
the azimuth and elevation angles associated with the RIS departure link, and
$\theta$ is the angle of arrival at SU. Further, we consider that PU-SU and
PU-RIS links are independent and do not have a LoS component. To capture a
generalized scenario, we assume that 1) there exists a spatial correlation
between the RIS/SU antenna elements and 2) the noise components at SU antennas
are correlated. Thus, we model the PU-SU channel $\mathbf{d}$ and PU-RIS
channel $\mathbf{h}$ using correlated Rayleigh fading such that
$\mathbf{d}\sim\mathcal{CN}(0,\mathbf{R_{d}})$ and
$\mathbf{h}\sim\mathcal{CN}(0,\mathbf{R_{h}})$ where $\mathbf{R_{d}}$ and
$\mathbf{R_{h}}$ are the covariance matrices of $\mathbf{d}$ and $\mathbf{h}$,
respectively. The covariance matrices are constructed such that their
$(i,j)$-th element is given by $\mathbf{R}_{\mathbf{d},{ij}}={\rm{\rm
sinc}}\left({2d_{ij}}/{\lambda}\right)$ and
$\mathbf{R}_{\mathbf{h},{ij}}={\rm{\rm sinc}}\left({2r_{ij}}/{\lambda}\right)$
where $\lambda$ is the operational wavelength, and $d_{ij}$ and $r_{ij}$ are
the distances between $i$-th and $j$-th antennas of SU and RIS, respectively.
It is worth noting that this covariance model captures the spatial correlation
for UPA more accurately than a Kronecker-product-based model. For more
details, please refer to [15].

The spectrum sensing problem can be formulated as binary hypothesis testing
problem between hypothesis $\mathcal{H}_{0}$ denotes the null hypothesis and
hypothesis $\mathcal{H}_{1}$ denotes the presence of the PU. Thus, the
received signal under these hypotheses can be expressed as

$\mathbf{y}_{k}=\begin{cases}\mathbf{w}_{k},&\text{Under}\;\mathcal{H}_{0}\\\
\sqrt{\beta}\mathbf{d}_{k}\text{s}_{k}+\sqrt{\nu}\mathbf{H}\mathbf{\Phi}\mathbf{h}_{k}\text{s}_{k}+\mathbf{w}_{k},&\text{Under}\;\mathcal{H}_{1}\end{cases}$
(1)

for $k=1,\ldots,K$, where $\text{s}_{k}$ corresponds to the $k$-th symbol
transmitted by the PU, $\mathbf{w}_{k}$ is complex correlated Gaussian noise
$\mathbf{w}_{k}\sim{\mathcal{CN}(0,\mathbf{R_{w}})}$ and $\mathbf{R_{w}}$ is
the noise covariance matrix. In (1), $\beta=d_{o}^{-\xi}$ and
$\nu=(d_{1}+d_{2})^{-\xi}$ represent the path-losses along the direct and
indirect links, respectively, where $d_{o}$, $d_{1}$ and $d_{2}$ represent the
distances of the PU-SU, PU-RIS and RIS-SU links, respectively, and $\xi$ is
the path-loss exponent. The phase shift matrix of the passive RIS is denoted
by $\bm{\Phi}=\text{diag}\left(\bm{\psi}\right)$ such that
$\bm{\psi}^{H}=\left[e^{j\vartheta_{1}},\dots,e^{j\vartheta_{N}}\right]^{T}$
and $\vartheta_{\rm N}$ is the phase shift provided by the $n$-th RIS element.
We assume that the PU transmission power is $P_{s}$, i.e.,
$\mathbb{E}\left[\text{s}_{k}\text{s}_{k}^{H}\right]=P_{s}$.

##  III Sensing using Maximum Eigenvalue Detection

MED employs knowledge of the principal eigenvalues of sample covariance
matrices of observed signals for hypothesis testing. This method exhibits
superior performance compared to energy-based detection techniques,
particularly in scenarios where the received signal is correlated [12], as is
the case considered in this paper. Thus, we employ the MED approach for
spectrum sensing, assuming that both the multi-path fading and noise are
correlated. The sample covariance matrix associated with the received signal
can be defined as

$\hat{\mathbf{R}}_{\mathbf{y}}\triangleq\frac{1}{K}\sum\nolimits_{k=0}^{K-1}\mathbf{y}_{k}\mathbf{y}_{k}^{\textit{H}}.$
(2)

Applying MED for detection problem given (1), the test statistic is given as

${\rm TS}\triangleq\alpha_{\rm max},$ (3)

where $\alpha_{\max}$ is the largest eigenvalue of
$\hat{\mathbf{R}}_{\mathbf{y}}$. The decision rule is

$\displaystyle{\rm
TS}\mathop{\lessgtr}_{\mathcal{H}_{1}}^{\mathcal{H}_{0}}\eta,$ (4)

where $\eta$ is the decision threshold. Thus, the detection and false alarm
probabilities can be defined as

$\displaystyle\rm P_{D}(\mathbf{\eta})$ $\displaystyle\triangleq\rm
Pr(TS>\eta\,|\,\mathcal{H}_{1}),$ $\displaystyle\text{\leavevmode\nobreak\
and\leavevmode\nobreak\ }\rm P_{FA}(\mathbf{\eta})$
$\displaystyle\triangleq\rm Pr(TS>\eta\,|\,\mathcal{H}_{0}),$

respectively. For the detection problem, the goal is to maximize the
probability of detection $\rm P_{D}$ while minimizing the probability of false
alarm $\rm P_{FA}$. However, maximizing $\rm P_{D}$ comes at the cost of
raising $\rm P_{FA}$. This results in a trade-off between $\rm P_{D}$ and $\rm
P_{FA}$ that needs to be carefully handled by appropriately determining the
optimal choice of $\eta$. We will consider Neyman-Pearson’s criteria [16] for
finding the decision threshold that maximizes the $\rm P_{D}$ for a given
${\rm P_{FA}}$. For this, it is necessary to characterize $\rm P_{D}$ and
${\rm P_{FA}}$ analytically. It is paramount to determine the statistical
distribution of the test statistics under both the hypotheses. For the
considered system, the distributions of the received signals under both
hypotheses given in (1) can be determined as

$\displaystyle\mathbf{y}_{k}$
$\displaystyle\sim\begin{cases}\mathcal{CN}(0,\mathbf{R_{w}}),&\text{Under}\;\mathcal{H}_{0},\\\
{\mathcal{CN}(0,\mathbf{R_{s}(\mathbf{\Phi})}+\mathbf{R_{w}})},&\text{Under}\;\mathcal{H}_{1},\end{cases}$
(5)

where

$\mathbf{R_{s}}(\mathbf{\Phi})=\beta P_{s}\mathbf{R_{d}}+\nu
P_{s}\textbf{H}\bm{\Phi}\mathbf{R_{h}}\bm{\Phi}^{H}\textbf{H},$ (6)

is the covariance of the signal component for a given RIS phase shift
configuration matrix $\mathbf{\Phi}$. Leveraging the benefits of RIS, it makes
sense to configure it to maximize the mean value of the largest eigenvalue of
the sample covariance matrix $\hat{\mathbf{R}}_{\mathbf{y}}$ under
$\mathcal{H}_{1}$ so that the detection probability can be improved, i.e.,

$\displaystyle\max_{\mathbf{\bm{\psi}}}\;$
$\displaystyle\mathbb{E}\left[\alpha_{\max}|\mathcal{H}_{1}\right],$ (7a) such
that $\displaystyle\left|\mathbf{\bm{\psi}}_{i}\right|=1,\leavevmode\nobreak\
\text{for}\leavevmode\nobreak\ i=1,\dots,N,$ (7b)

where (7b) represents the unit modulus constraint of passive RIS. However,
this constraint makes the problem non-convex, making it difficult to solve
directly. Since $\hat{\mathbf{R}}_{\mathbf{y}}$ is a positive semidefinte, we
have $\alpha_{\max}<\text{Tr}(\hat{\mathbf{R}}_{\mathbf{y}})$, where
$\text{Tr}(\cdot)$ represents trace operator. Using this identity, we aim to
select $\mathbf{\Phi}$ optimally that maximizes the upper bound on
$\alpha_{\max}$, i.e.

$\mathbb{E}\left[\alpha_{\max}|\mathcal{H}_{1}\right]\leq\mathbb{E}[\text{Tr}(\hat{\mathbf{R_{y}}})|\mathcal{H}_{1}]=\text{Tr}(\mathbf{R_{s}}(\mathbf{\Phi}))+\text{Tr}(\mathbf{R_{w}}).$

Using [17, Appendix A] and $\mathbf{\Phi}={\rm diag}(\bm{\psi})$, we can write

$\displaystyle\text{Tr}(\mathbf{R_{s}(\mathbf{\Phi})})$ $\displaystyle=\beta
P_{s}\text{Tr}(\mathbf{R_{d}})+\nu P_{s}\text{Tr}(\mathbf{H\Phi
R_{h}}\mathbf{\Phi}^{H}\mathbf{H}^{H}),$ $\displaystyle=\beta
P_{s}\text{Tr}(\mathbf{R_{d}})+\nu
P_{s}\bm{\psi}^{H}\left((\mathbf{H}^{H}\mathbf{H})\odot\mathbf{R_{h}}\right)\bm{\psi},$

where $\odot$ is the Hadamard product. Thus, the above optimization problem
can be rewritten as

$\displaystyle\max_{\mathbf{\bm{\psi}}}\;$
$\displaystyle\bm{\psi}^{H}\left((\mathbf{H}^{H}\mathbf{H})\odot\mathbf{R_{h}}\right)\bm{\psi},$
(8a) such that $\displaystyle\left|\mathbf{\bm{\psi}}_{i}\right|=1.$ (8b)

Further, using [18, Theorem 4], we can directly obtain the optimal RIS phase
shift configuration as

$\bm{\psi}_{\rm opt}=e^{j\vartheta}\mathbf{1}_{N},$ (9)

where $\mathbf{1}_{N}$ a $N\times 1$ vector with unit entries and
$\vartheta\in[0,2\pi]$. Thus, for the optimally configured RIS phase-shift
matrix, the covariance matrix under $\mathcal{H}_{1}$ become

$\mathbf{R_{s}}(\mathbf{\Phi}_{\rm opt})=\beta P_{s}\mathbf{R_{d}}+\nu
P_{s}\mathbf{HR_{h}}\mathbf{H}^{H}.$ (10)

Note that the sample covariance matrix, as defined in (2), is random, which
makes the resulting largest eigenvalue a random variable. Thus, to obtain $\rm
P_{D}$ and $\rm P_{FA}$, it is crucial to first derive the distribution of the
largest eigenvalue under both $\mathcal{H}_{0}$ and $\mathcal{H}_{1}$. From
(2) and (5), it is clear that $\hat{\mathbf{R}}_{\mathbf{y}}$ is a central
Wishart matrix. This promotes the application of random matrix theory [13] to
derive the distribution of the largest eigenvalue of the central Wishart
matrix. On this line, huge research efforts are devoted in the literature to
characterize this distribution. However, the available results mostly focus on
1) the approximate distribution of the largest eigenvalue in the asymptotic
region and 2) the Wishart matrix with uncorrelated entries. For instance,
[13], characterize the distribution using Tracy-Widom in the asymptotic
region. An exact largest eigenvalue distribution is studied in [19] and then
thoroughly extended in [20] to obtain the close form results for the iid noise
case. However, these existing results do not apply to the considered system
setting as it includes a general case of correlated fading and correlated
noise with a reasonable/moderate number of receiving antennas. The exact
distribution of the largest eigenvalue of a central Wishart matrix is given in
the following theorem

######  Theorem 1.

Let $\mathbf{X}$ be a $p$ $\times$ $q$ matrix whose columns are $p$-variate
zero-mean complex Gaussian distributed, with covariance matrix
$\mathbf{\Sigma}$, i.e., $\mathbf{X}\sim\mathcal{CN}(0,\mathbf{\Sigma})$. Say
$n=\max(p,q)$ and $m=\min(p,q)$. Let $\mathbf{A}\triangleq\mathbf{XX^{H}}$ be
the central Wishart matrix and let $\alpha_{\rm 1},\alpha_{\rm
2},\dots,\alpha_{\rm m}$ be the ordered eigenvalues of matrix $\mathbf{A}$.
Let $\lambda_{1},\lambda_{2},\ldots,\lambda_{m}$ be the ordered eigenvalues of
$\mathbf{\Sigma^{-1}}$, then the CDF of the largest eigenvalue $\alpha_{m}$ of
$\mathbf{A}$ is given by

$\displaystyle{\rm Pr}(\alpha_{m}\leq\eta)$
$\displaystyle=\frac{c}{|\mathbf{V}|}{\rm
det}\left[\bm{\Lambda}(\eta,\lambda)\right],$ (11)

where $\gamma(\cdot\,,\cdot)$ is lower incomplete gamma function and
$(i,j)$-th element of $\bm{\Lambda}(\eta,\lambda)$ is

$\displaystyle\\{\bm{\Lambda}(\eta,\lambda)\\}_{ij}$
$\displaystyle=\frac{1}{\lambda^{n-i+1}}\gamma(n-i+1,\eta\lambda_{j}),$ (12)
$\displaystyle\text{and\leavevmode\nobreak\ }|\mathbf{V}|$
$\displaystyle=\prod\nolimits_{i,j=1,\dots,m,i<j}^{m}(\lambda_{i}-\lambda_{j}).$
(13)

###### Proof.

Please refer to Appendix V for the proof. ∎

Using Theorem 1, we can determine the largest eigenvalue distributions of
sample covariance matrices under $\mathcal{H}_{0}$ and $\mathcal{H}_{1}$, and
accordingly use them to evaluate the false alarm and detection probabilities,
as done in the following subsections.

###  III-A False alarm probability

Under the null hypothesis $\mathcal{H}_{0}$, where the signal is not
transmitted, the received signal solely comprises noise. Thus, the observed
sample covariance matrix becomes

$\hat{\mathbf{R}}_{\mathbf{y}}=\frac{1}{K}\sum\nolimits_{k=0}^{K-1}\textbf{w}_{k}\textbf{w}_{k}^{\rm
H},$ (14)

and the covariance matrix of $\mathbf{w}_{k}$ is $\mathbf{R_{w}}$. Hence, the
test statistics, as defined in (3), becomes the largest eigenvalue of (14).
Let
$0<\lambda_{1}^{\mathbf{w}}<\lambda_{2}^{\mathbf{w}}<\dots<\lambda_{m}^{\mathbf{w}}$
represent the ordered eigenvalues of $\mathbf{R}^{-1}_{\mathbf{w}}$. Using
Theorem 1 and substituting $\bm{\Sigma}^{-1}=\mathbf{R}^{-1}_{\mathbf{w}}$, we
can obtain the exact distribution of TS and thereby get a closed-form
expression for $\rm P_{FA}$ as

$\displaystyle\rm P_{FA}(\eta)$
$\displaystyle=1-\frac{c}{|\mathbf{V}_{\lambda^{\mathbf{w}}}|}{\rm
det}\left[\bm{\Lambda}(\eta,\lambda^{\mathbf{w}}_{j})\right],$ (15)

where $\bm{\Lambda}(\eta,\lambda^{\mathbf{w}})$ is given in (12) and
$|\mathbf{V}_{\lambda^{\mathbf{w}}}|$ can be obtained using (13) with
$\lambda_{i}=\lambda_{i}^{\mathbf{w}}$. To achieve a desired $\rm P_{FA}$, the
detection threshold $\eta$ can be obtained by inverting (15). We adopt a
numerical approach to invert (15) for obtaining $\eta$.

###  III-B Detection Probability

When a signal is present, i.e., hypothesis $\mathcal{H}_{1}$, the received
signal consists of both the PU signal and noise components. The sample
covariance matrix for this case is given as

$\hat{\mathbf{R}}_{\mathbf{y}}=\frac{1}{K}\sum_{k=0}^{K-1}\beta\mathbf{d}_{k}\mathbf{d}_{k}^{H}+\nu\mathbf{H}\mathbf{\Phi}\mathbf{h}_{k}\mathbf{h}_{k}^{H}\mathbf{\Phi}^{H}\mathbf{H}^{H}+\mathbf{w}_{k}\mathbf{w}^{H}_{k},$
(16)

where the covariance matrix of the received signal under $\mathcal{H}_{1}$ is
$\mathbf{R_{s}(\bm{\Phi}_{opt})+R_{w}}$, as defined in (5). The test
statistics is the maximum eigenvalue of (16). It is to be noted that the above
sample covariance matrix is observed with the optimally configured RIS phase
shifts, which aim to maximize the expected value of test statistics. Now,
using Theorem 1, we can evaluate the distribution of test statistics with
$\bm{\Sigma}^{-1}=\left(\mathbf{R_{s}(\bm{\Phi}_{opt})+R_{w}}\right)^{-1}$.
Let
$0<\lambda_{1}^{\mathbf{y}}<\lambda_{2}^{\mathbf{y}}<\dots<\lambda_{m}^{\mathbf{y}}$
be the ordered eigenvalues of
$\left(\mathbf{R_{s}(\bm{\Phi}_{opt})+R_{w}}\right)^{-1}$. Hence, the
distribution of the largest eigenvalue is given as

$\displaystyle\rm P_{D}(\eta)$
$\displaystyle=1-\frac{c}{|\mathbf{V}_{\lambda^{\mathbf{y}}}|}{\rm
det}\left[\bm{\Lambda}(\eta,\lambda^{\mathbf{y}}_{j})\right],$ (17)

where $\bm{\Lambda}(\eta,\lambda^{\mathbf{y}})$ is given in (12) and
$|\mathbf{V}_{\lambda^{\mathbf{y}}}|$ can be obtained using (13) with
$\lambda_{i}=\lambda_{i}^{\mathbf{y}}$.

##  IV Numerical Results

This section presents a numerical analysis of the proposed MED for RIS-aided
spectrum sensing. In particular, we will verify the false alarm and detection
probabilities via simulations. Next, we will discuss how the proposed MED’s
ROC curve performs in terms of the various system design parameters. For
numerical analysis, we consider the number of received antenna $M=8$, the
number of RIS element $N=32$, the distance between subsequent RIS element
$d=\lambda/2$, the number of observations $K=10$, the transmission power of PU
$P_{s}=10\;$dBm, direct link distance $d_{o}=30$ m and path-loss exponent
$\xi=3$, unless we mention otherwise.

Recall that RIS phase shift is configured according to (9) to maximize the
mean of the observed largest eigenvalue under $\mathcal{H}_{1}$. The signal-
to-noise ratio (SNR) of the received signal is

$\displaystyle{\rm SNR}=\Upsilon\|\sqrt{\mu}\mathbf{H}\mathbf{\Phi}_{\rm
opt}\mathbf{h}+\mathbf{d}\|^{2},$

where $\Upsilon=\frac{\beta P_{S}}{\sigma_{W}^{2}}$ is the mean SNR received
per antenna on the direct link and $\mu=\frac{\nu}{\beta}$ represents the
ratio of path-losses of the indirect and direct links. Without the loss of
generality, we will consider that $d_{o}=\kappa(d_{1}+d_{2})$ where
$\kappa\in[0,1]$ and thus model the path-loss ratio as $\mu=\kappa^{\xi}$ to
capture the effect of the relative difference in path-losses observed by the
direct and indirect links. Further, we model the noise covariance matrix as
$\mathbf{R_{w,}}_{ij}=\rho^{\left|i-j\right|}\sigma_{W}^{2}$ such that
$\sigma_{W}^{2}$ is the noise variance and $\rho$ is the correlation
coefficient of $i$-th and $j$-th noise components. We consider
$\kappa=\frac{1}{3}$ and the correlation factor $\rho=0.2$.

Figure 2: Probabilities of false alarm $\rm P_{FA}$ and missed detection $\rm
P_{MD}=1-P_{D}$ vs. threshold $\eta$. The lines indicate the analytical
curves, whereas the circular markers represent the simulated results.

Fig. 2 verifies the derived false alarm and miss detection probabilities using
simulation results for $\Upsilon=-10\,\rm{dB}$. The simulation results
(denoted by markers) match exactly with the analytical results derived for the
${\rm P_{FA}}$ and ${\rm P_{MD}}$ (denoted by lines). As expected, these
probabilities exhibit the performance trade-off w.r.t. to the decision
threshold $\eta$. The figure also shows that the missed detection probability
${\rm P_{MD}}$ performs better when RIS is utilized for the sensing. It can be
seen that the ${\rm P_{MD}}$ reduces significantly with the increase in RIS
elements $N$ for a given $\eta$. Basically, by using a large dimensional RIS,
it is possible to increase the deflection coefficient [16] corresponding to
the test statistics distributions observed under $\mathcal{H}_{0}$ and
$\mathcal{H}_{1}$, which essentially will help to improve the performance of
ROC curves, as it will also be highlighted shortly.

Figure 3: ROC: $\rm{P_{D}}$ vs $\rm{P_{FA}}$ for various SNR $\Upsilon$.

Next, in Fig. 3, we show the ROC, i.e., $\rm P_{D}$ vs $\rm P_{FA}$ at
$\Upsilon=-10,\,-8,\,\text{and}\,-5$ dB. The figure shows that the performance
improves with an increase in $\Upsilon$, which is quite expected. However, it
can be seen that the MED performance without RIS for $\Upsilon=-10$ dB is very
poor. In contrast, including RIS with $N=32$ gives a significantly higher
detection probability for the same $\Upsilon$. This ensures that RIS can be
useful to improve the spectrum sensing performance without necessarily
increasing the transmission power or using more sophisticated/complex designs
for the receiver. Next, Fig. 4 shows that the ROC curve of the proposed MED
improves with the increase in the number of RIS elements. In particular, it
can be observed that the detection probability rises sharply with just
doubling the number of RIS elements. Therefore, it is possible to achieve the
detection probability close to $1$ for a very small probability of false alarm
using moderately large dimensional RIS.

Figure 4: ROC: $\rm{P_{D}}$ vs $\rm{P_{FA}}$ for different number of RIS
elements $N$.

Figure 5: Left: ROC for different $N$. Right: $\rm{P_{D}}$ vs. $N$ for
different $\Upsilon$.

Fig. 5 shows the benefit of using the optimally configured RIS when the
spacing between RIS elements is $d=\lambda/2$. Fig. 5 (Left) indicates the ROC
performance for various values of number of RIS elements $N$ when
$\Upsilon=-10$ dB. The figure shows that the ROC improves significantly when
optimally configured RIS is used, especially when $N$ is large. Note that the
enhancement is attributed to the fact that the optimally configured RIS
maximizes the trace of covariance matrix $\mathbf{R_{s}(\Phi)}$, which
encompasses the spatial correlation of fading and hence the correlated fading
aids the performance of MED. Fig. 5 (Right) shows that the detection
probability ${\rm P_{D}}$ (for ${\rm P_{FA}}=0.1$) improves with the increase
in $N$ for various values of $\Upsilon$. It can be observed that the ${\rm
P_{D}}$ approaches $1$ for smaller values of $N$ when the operating $\Upsilon$
is larger and vice-versa. In addition, the figure also verifies the enhanced
performance of ${\rm P_{D}}$ with optimally configured RIS. However, the
improvement diminishes with the increase in $\Upsilon$. This may be because
the overall SNR along the direct link is much higher, and utilizing optimally
configured RIS is unnecessary.

##  V Conclusion

In this paper, we investigate the performance of MED for RIS-aided spectrum
sensing. We consider that the PU-RIS and PU-SU link experience correlated
Rayleigh fading, and RIS is placed such that it has a strong LoS link with SU.
For this setup, we derived an exact distribution of the largest eigenvalue of
the sample covariance matrix, which we next utilized to derive the detection
and false alarm probabilities. In addition, we also configure the RIS phase
shift matrix optimally to maximize the mean of the test statistics under the
signal present hypothesis so that the detection probability can be improved.
It is worth noting that this paper is the first to present an exact analytical
characterization of MED for RIS-aided spectrum sensing when both the multi-
path fading and noise are correlated. Our numerical analysis demonstrates that
the ROC curve of the MED exhibits improvement with the increase in the number
of RIS elements and mean received SNR. It also shows that the detection
probability approaches unity for a moderate number of RIS elements, especially
when the optimally configured RIS phase shifts are used for low SNR.

Let $\alpha_{1},\alpha_{2},\ldots,\alpha_{m}$ be eigenvalues of $\mathbf{A}$,
and the joint density function of ($\alpha_{1},\alpha_{2},\ldots,\alpha_{m}$)
is given in [21]

$\displaystyle f(\alpha_{1},\alpha_{2},\ldots,\alpha_{m})$
$\displaystyle=\left|\mathbf{\Sigma}\right|^{-n}\mathcal{{}_{\text{0}}\widetilde{F}_{\text{0}}}(-\mathbf{\Sigma}^{-1},\mathbf{A})\frac{\pi^{m(m-1)}}{\widetilde{\Gamma}_{m}(n)\widetilde{\Gamma}_{m}(m)}$
(18)
$\displaystyle\times|\mathbf{A}|^{n-m}\prod\nolimits_{i,j=1,i<j}^{m}(\alpha_{i}-\alpha_{j})^{2},$

where $n=\text{max}\left(p,q\right)$ and $m=\text{min}\left(p,q\right)$,
$\mathcal{{}_{\text{0}}\widetilde{F}_{\text{0}}}(\cdot\,,\cdot)$ is the
hypergeometric function with matrix argument,

$\widetilde{\Gamma}_{s}(t)=\pi^{s(s-1)/2}\prod\nolimits_{i=1}^{s}\Gamma(t-i+1),$

and $\Gamma(\cdot)$ is gamma function. Now, from [22], we have the following
identity

$\mathcal{{}_{\text{0}}\widetilde{F}_{\text{0}}}(-\mathbf{\Sigma}^{-1},\mathbf{A})=\beta_{m}\frac{\left|\bm{\Lambda}(\alpha,\lambda)\right|}{\prod_{i,j=1,i<j}^{m}(\lambda_{i}-\lambda_{j})(\alpha_{i}-\alpha_{j})},$
(19)

where $\\{\bm{\Lambda}(\alpha,\lambda)\\}_{ij}=$
${}_{\text{0}}F_{\text{0}}(-\lambda_{j}\alpha_{i})$,
${}_{\text{0}}F_{\text{0}}(\cdot)$ is hypergeometric function with scalar
input, $\lambda_{j}$ is the $j$-th eigenvalue of $\Sigma^{-1}$ and

$\beta_{m}=\prod\nolimits_{a=1}^{m}(a-1)!.$

Now, substituting (19) in (18) gives us,

$\displaystyle f(\alpha_{1},\alpha_{2},\ldots,\alpha_{m})$
$\displaystyle=\frac{c}{|\mathbf{V}|}|\bm{\Lambda}(\alpha,\lambda)||\mathbf{W}|\prod\nolimits_{i=1}^{m}\alpha_{i}^{n-m}$
(20) $\displaystyle\text{where\leavevmode\nobreak\ }c$
$\displaystyle=\frac{|\mathbf{\Sigma}|^{-n}\beta_{m}}{\prod_{i=1}^{m}\Gamma(n-i+1)\Gamma(m-i+1)},$
$\displaystyle\text{and\leavevmode\nobreak\ }|\mathbf{V}|$
$\displaystyle=\prod\nolimits_{i,j=1,\dots,m,i<j}^{m}(\lambda_{i}-\lambda_{j}).$

Note that $\mathbf{V}$ and $\mathbf{W}$ are Vandermonde matrices such that

$\mathbf{V}=\left[\begin{matrix}\lambda_{1}^{m-1}&\lambda_{1}^{m-2}&\cdots&1\\\
\lambda_{2}^{m-1}&\lambda_{2}^{m-2}&\cdots&1\\\ \vdots&\vdots&\ddots&\vdots\\\
\lambda_{m}^{m-1}&\lambda_{m}^{m-2}&\cdots&1\end{matrix}\right],$ (21)

and $\mathbf{W}$ is defined in similar way as (21), with $\alpha_{i}$’s
instead of $\lambda_{i}$’s. To find the CDF of the largest eigenvalue
$\alpha_{m}$, we will have to integrate (20) over region
$D=\left[0<\alpha_{1}<\ldots<\alpha_{m}<\eta\right]$. Hence, the CDF will be
given by

Pr
$\displaystyle(\alpha_{m}\leq\eta)=\frac{c}{|\mathbf{V}|}\int_{D}\left|\bm{\Lambda}(\alpha,\lambda)\right|\left|\mathbf{W}\right|\prod_{i=1}^{m}\alpha_{i}^{n-m}\prod_{i=1}^{m}d\alpha_{i}$
(22)

Let
$I=\left|\bm{\Lambda}(\alpha,\lambda)\right|\left|\mathbf{W}\right|\prod_{i=1}^{m}\alpha_{i}^{n-m}$
be the integrand function in (22). The above product of two determinants can
be written as

$\displaystyle\left|\bm{\Lambda}(\alpha,\lambda)\right|\left|\mathbf{W}\right|=\sum_{(\sigma_{1},\dots,\sigma_{m})}\sum_{(i_{1},\dots,i_{m})}\operatorname{sign}(i_{1},\dots,i_{m})\times$
$\displaystyle\alpha_{\sigma_{1}}^{m-1}\,{}_{\text{0}}F_{\text{0}}(-\lambda_{i_{1}}\alpha_{\sigma_{1}})\alpha_{\sigma_{1}}^{m-2}\,{}_{\text{0}}F_{\text{0}}(-\lambda_{i_{2}}\alpha_{\sigma_{2}})\dots_{\text{0}}F_{\text{0}}(-\lambda_{i_{m}}\alpha_{\sigma_{m}}).$

Now, using this, we can simplify $I$ as

$I=|\bm{\Lambda^{{}^{\prime}}}(\alpha,\lambda)|,$

where
$\\{\bm{\Lambda^{\prime}}(\alpha,\lambda)\\}_{ij}=\alpha_{i}^{n-i}{{}_{\text{0}}F_{\text{0}}}(-\lambda_{j}\alpha_{i})$.
Further by substituting $I$ in (22) we get,

$\text{Pr}(\alpha_{m}\leq\eta)=\frac{c}{|\mathbf{V}|}\int_{D}\left|\bm{\Lambda^{\prime}}(\alpha,\lambda)\right|\prod_{i=1}^{m}d\alpha_{i}.$

Next, by applying [23, Lemma 1], we can write

$\text{Pr}(\alpha_{m}\leq\eta)=\frac{c}{|\mathbf{V}|}\left|\int_{0}^{\eta}\bm{\Lambda}(y,\lambda)dy\right|,$
(23)

where
$\\{\bm{\Lambda}(y,\lambda)\\}_{ij}=y^{n-i}{{}_{\text{0}}F_{\text{0}}(-\lambda_{j}\alpha_{i})}$.
Note that the ${}_{\text{0}}F_{\text{0}}$ is a special case hypergeometric
function which can be written as

${}_{\text{0}}F_{\text{0}}(-\lambda_{j}\alpha_{i})=e^{-y\lambda_{j}}.$

Finally, applying the above identity, we can simplify the integral in (23) as

$\displaystyle\int_{0}^{\eta}\\{\bm{\Lambda}(y,\lambda)\\}_{ij}dy$
$\displaystyle=\int_{0}^{\eta}y^{n-i}e^{-y\lambda_{j}}dy,$ (24)

which will give us (12) and further substituting it into (23) will complete
the proof.

## References

  * [1] Q. Wu and R. Zhang, “Towards smart and reconfigurable environment: Intelligent reflecting surface aided wireless network,” _IEEE Communications Magazine_ , vol. 58, no. 1, pp. 106–112, 2020.
  * [2] E. Basar, M. Di Renzo, J. De Rosny, M. Debbah, M.-S. Alouini, and R. Zhang, “Wireless communications through Reconfigurable Intelligent Surfaces,” _IEEE Access_ , vol. 7, pp. 116 753–116 773, 2019.
  * [3] E. Björnson, H. Wymeersch, B. Matthiesen, P. Popovski, L. Sanguinetti, and E. de Carvalho, “Reconfigurable intelligent surfaces: A signal processing perspective with wireless applications,” _IEEE Signal Processing Magazine_ , vol. 39, no. 2, pp. 135–158, 2022.
  * [4] O. Ozdogan, E. Bjornson, and E. G. Larsson, “Intelligent reflecting surfaces: Physics, propagation, and pathloss modeling,” _IEEE Wireless Communications Letters_ , vol. 9, no. 5, pp. 581–585, 2020.
  * [5] M. Di Renzo, A. Zappone, M. Debbah, M.-S. Alouini, C. Yuen, J. de Rosny, and S. Tretyakov, “Smart radio environments empowered by reconfigurable intelligent surfaces: How it works, state of research, and the road ahead,” _IEEE Journal on Selected Areas in Communications_ , vol. 38, no. 11, pp. 2450–2525, 2020.
  * [6] Y.-C. Liang, Y. Zeng, E. C. Peh, and A. T. Hoang, “Sensing-throughput tradeoff for cognitive radio networks,” _IEEE Transactions on Wireless Communications_ , vol. 7, no. 4, pp. 1326–1337, 2008.
  * [7] W. Wu, Z. Wang, L. Yuan, F. Zhou, F. Lang, B. Wang, and Q. Wu, “IRS-enhanced energy detection for spectrum sensing in cognitive radio networks,” _IEEE Wireless Communications Letters_ , vol. 10, no. 10, pp. 2254–2258, 2021.
  * [8] H. Xie, D. Li, and B. Gu, “Enhancing Spectrum Sensing via Reconfigurable Intelligent Surfaces: Passive or Active Sensing and How Many Reflecting Elements are Needed?” _arXiv e-prints_ , p. arXiv:2306.13874, Jun. 2023.
  * [9] S. Lin, B. Zheng, F. Chen, and R. Zhang, “Intelligent reflecting surface-aided spectrum sensing for cognitive radio,” _IEEE Wireless Communications Letters_ , vol. 11, no. 5, pp. 928–932, 2022.
  * [10] J. Ge, Y.-C. Liang, S. Li, and Z. Bai, “RIS-enhanced spectrum sensing: How many reflecting elements are required to achieve a detection probability close to 1?” _IEEE Transactions on Wireless Communications_ , vol. 21, no. 10, pp. 8600–8615, 2022.
  * [11] S. K. Sharma, S. Chatzinotas, and B. Ottersten, “Maximum eigenvalue detection for spectrum sensing under correlated noise,” in _IEEE ICASSP_ , 2014, pp. 7268–7272.
  * [12] Y. Zeng, C. L. Koh, and Y.-C. Liang, “Maximum eigenvalue detection: Theory and application,” in _2008 IEEE International Conference on Communications_ , 2008, pp. 4160–4164.
  * [13] J. Ge, Y.-C. Liang, Z. Bai, and G. Pan, “Large-dimensional random matrix theory and its applications in deep learning and wireless communications,” _Random Matrices: Theory and Applications_ , vol. 10, no. 04, p. 2230001, 2021.
  * [14] P. Wang, J. Fang, H. Duan, and H. Li, “Compressed channel estimation for intelligent reflecting surface-assisted millimeter wave systems,” _IEEE Signal Processing Letters_ , vol. 27, pp. 905–909, 2020.
  * [15] E. Björnson and L. Sanguinetti, “Rayleigh fading modeling and channel hardening for reconfigurable intelligent surfaces,” _IEEE Wireless Communications Letters_ , vol. 10, no. 4, pp. 830–834, 2021.
  * [16] S. M. Kay, _Fundamentals of statistical processing, Volume 2: Detection theory_. Pearson Education India, 2009.
  * [17] G. Taricco, “Asymptotic mutual information statistics of separately correlated rician fading MIMO channels,” _IEEE Transactions on Information Theory_ , vol. 54, no. 8, pp. 3490–3504, 2008.
  * [18] K. K. Kota, M. S. S. Manasa, P. D. Mankar, and H. S. Dhillon, “Statistically optimal beamforming and ergodic capacity for RIS-aided MISO systems,” 2023, arXiv: 2307.00230.
  * [19] C. G. Khatri, “Distribution of the largest or the smallest characteristic root under null hypothesis concerning complex multivariate normal populations,” _The Annals of Mathematical Statistics_ , vol. 35, no. 4, pp. 1807–1810, 1964.
  * [20] M. Chiani, “Distribution of the largest eigenvalue for real wishart and gaussian random matrices and a simple approximation for the tracy-widom distribution,” _Journal of Multivariate Analysis_ , vol. 129, pp. 69–81, Aug. 2014.
  * [21] A. T. James, “Distributions of Matrix Variates and Latent Roots Derived from Normal Samples,” _The Annals of Mathematical Statistics_ , vol. 35, no. 2, pp. 475 – 501, 1964.
  * [22] K. I. Gross and D. S. P. Richards, “Total positivity, spherical series, and hypergeometric functions of matrix argument,” _Journal of Approximation theory_ , vol. 59, no. 2, pp. 224–246, 1989.
  * [23] C. G. Khatri, “Non-central distributions of ith largest characteristic roots of three matrices concerning complex multivariate normal populations,” _Annals of the Institute of Statistical Mathematics_ , vol. 21, no. 1, pp. 23–32, December 1969.


#  Coffee: Cost-Effective Edge Caching
for 360 Degree Live Video Streaming

Chen Li, Tingwei Ye, Tongyu Zong, Liyang Sun, Houwei Cao, and Yong Liu C. Li,
T. Ye, T. Zong, L. Sun and Y. Liu are with the Department of Electrical and
Computer Engineering, New York University, Brooklyn, NY, 11201 USA e-mail:
({chen.lee,ty2281,tz1178,ls3817,yongliu}@nyu.edu).H. Cao is with New York
Institute of Technology, NY, USA e-mail<EMAIL_ADDRESS>
###### Abstract

While live 360 degree video streaming delivers immersive viewing experience,
it poses significant bandwidth and latency challenges for content delivery
networks. Edge servers are expected to play an important role in facilitating
live streaming of 360 degree videos. In this paper, we propose a novel
predictive edge caching algorithm (Coffee) for live 360 degree video that
employ collaborative FoV prediction and predictive tile prefetching to reduce
bandwidth consumption, streaming cost and improve the streaming quality and
robustness. Our light-weight caching algorithms exploit the unique tile
consumption patterns of live 360 degree video streaming to achieve high tile
caching gains. Through extensive experiments driven by real 360 degree video
streaming traces, we demonstrate that edge caching algorithms specifically
designed for live 360 degree video streaming can achieve high streaming cost
savings with small edge cache space consumption. Coffee, guided by viewer FoV
predictions, significantly reduces back-haul traffic up to 76% compared to
state-of-the-art edge caching algorithms. Furthermore, we develop a
transcoding-aware variant (TransCoffee) and evaluate it using comprehensive
experiments, which demonstrate that TransCoffee can achieve 63% lower cost
compared to state-of-the-art transcoding-aware approaches.

###### Index Terms:

edge caching, 360 degree video live streaming, trans-coding, FoV prediction

##  I Introduction

A live event can be captured and streamed as a 360 degree video to deliver
immersive viewing experience. A viewer dynamically changes her Field-of-View
(FoV) by making three-degree-of-freedom (3-DoF) head rotational movements
(pitch, yaw, roll). Meanwhile, live 360 degree video broadcast consumes
considerably higher bandwidth than the traditional 2D planar video broadcast.
FoV-adaptive streaming, which partitions a 360 degree video frame into non-
overlapping tiles and only streams tiles falling into the viewer’s FoV, can
significantly reduce the bandwidth consumption. Edge servers are in a unique
position to strategically combine communication and computing resources to
process and stream 360 degree videos, providing robust and high-quality
Quality-of-Experience (QoE) for viewers. Edge-based 360 degree video multicast
and caching can support high-throughput and low-latency multi-user delivery.
For on-demand 360 degree video streaming, tiles downloaded to an edge server
can be cached to serve requests from future viewers. Live 360 degree video
streaming can additionally benefit from temporal locality. Viewers of a live
broadcast event are loosely synchronized in time: after a 360 degree video
frame is captured, it should be delivered to all the viewers within the
maximum tolerable playback latency. Due to heterogeneity of devices and
networks, viewers watching the same live event may experience different levels
of video quality and incur different playback latencies. To take advantage of
the temporal locality of viewers, an edge server can act as a local live
streaming proxy to gain the benefits of multicasting. It is usually thought
that live content is “uncacheable”. However, the small playback latency gaps
among viewers create a niche opportunity to achieve a high caching gain with a
low storage cost. Furthermore, by utilizing the computing power on the edge
server, an additional caching gain can be achieved by transcoding tiles. For
example, a cached tile at one quality level can be transcoded to fulfill
requests for the same tile at other quality levels.

In this paper, we investigate predictive edge caching for live 360 degree
video streaming, which utilizes collaborative FoV prediction, predictive tile
prefetching, and transcoding-aware caching to reduce bandwidth consumption and
improve streaming quality and robustness. To the best of our knowledge, this
is the first work to design customized edge caching algorithms to reduce live
360 degree video streaming cost. We address two key challenges: (1) how to
design streaming-aware edge caching algorithms to achieve high caching hit
ratios with low storage consumption? and (2) how to effectively utilize the
transcoding capability of edge server to further improve live 360 degree video
caching efficiency? Edge cache boxes have much smaller storage space than the
traditional cache boxes, which poses a significant challenge for caching the
sheer volume of 360 degree video. To achieve high caching gain, it is critical
to accurately predict contents that will be popular in the near future. The
unique tile consumption patterns of live 360 degree video point to promising
directions for accurate predictive edge tile caching algorithms with low
storage cost: (1) Given the video playback start time, one can accurately
predict which video frame a viewer will watch at a future time instant; (2)
For each 360 degree video frame, a viewer only watches a subset of tiles
falling into her FoV, which can be accurately predicted using various FoV
prediction algorithms; (3) Viewers of the same live event typically share
common viewing interests, which can be leveraged for collaborative FoV
prediction; (4) Live video tiles have short life-spans, so there is no need to
cache old tiles that all viewers have finished watching; (5) Tile transcoding
eliminates the need to store multiple versions of the same tile, as a cached
tile can be transcoded to serve requests for the same tile at lower qualities.

Exploiting these unique opportunities, we make the following contributions
towards developing novel edge caching algorithms for live 360 degree
streaming:

  1. 1.

We predict what a viewer’s FoV will be in the near future based on her past
FoV trajectory and the FoV trajectories of viewers with a shorter playback
latency.

  2. 2.

With the playback time prediction for a tile, we design a realtime predictive
caching score that quantifies how likely a tile will fall into the FoVs of the
future viewers.

  3. 3.

We further develop transcoding-aware tile caching algorithms that predict the
gain of caching a tile at a certain quality level based on not only how likely
it will be requested by future viewers, but also how likely it can be
transcoded to serve future requests.

  4. 4.

Through extensive experiments driven by real 360 degree video streaming
traces, we demonstrate that edge caching algorithms specially designed for
live 360 degree video streaming can achieve high bandwidth savings with small
edge cache space consumption. Our predictive caching algorithms (Coffee and
Transcoffee) guided by viewer FoV predictions significantly outperform the
state-of-the-art edge caching algorithms.

The rest of the paper is structured as follows. Section II provides an
overview of related work. Section III introduces the edge-assisted live 360
degree video streaming framework. Section IV develops predictive edge caching
algorithms guided by collaborative FoV prediction. Section V explains how we
design the transcoding-aware edge caching algorithm. Section VI presents the
evaluation results. Finally, Section VII outlines future work.

##  II related work

Edge content caching helps deliver contents at low-latency and high-throughput
by caching popular contents, so that the traffic in the core/back-haul network
can be significantly reduced. However, edge cache boxes have smaller storage
space than the traditional CDN servers, and serve just a small number of
users, whose aggregate content request patterns are much more dynamic. Naive
caching strategies such as Least-Recently-Used (LRU) or Least-Frequently-Used
(LFU) are insufficient to get good caching performance. To deal with this
challenge, many existing studies proposed various algorithms including both
heuristic-based [1, 2] and learning-based methods [3, 4, 5, 6] to achieve good
edge-caching performance. In [7, 8], deep reinforcement learning is also used
for edge caching. Previously, some studies focused on edge caching-assisted
on-demand video streaming [9]. However, there are only very few studies on
edge caching for live 360 degree video multicasting [10, 11]. In [11], LSTM
network is used to predict the evolution of the popularity of video tiles in
future GOPs in tile-based live 360 degree video streaming but no transcoding
is considered when making the caching decision. Live 360 degree video
multicast can benefit from the caching and transcoding capabilities of edge
servers. Trans-coding is usually applied in 360 streaming systems. [12]
leverage a DRL-based model to make caching and transcoding decisions to reduce
delay, transmission cost and quality mismatch level with limited cache size
and computational power. In [13], multi-agent RL is proposed for a
transcoding-enable edge caching model to minimize communication and
transcoding latency with a constrained transcoding power. However, the cost of
transcoding can not be ignored. In our work, TransCoffee minimizes total cost
of communication and transcoding in live 360 degree video streaming system
using a lightweight model. In addition, FoV prediction is a necessary part for
360 degree video streaming, no matter for on-demand or live systems.
Impressive research have been accomplished for FoV prediction [14, 15], and
edge-assisted delivery [16, 17, 18] of 360o video recently. Collaborative FoV
prediction is proposed in [19] which predict a user’s FoV by other users’
viewing directions, but they are designed for on-demand 360 degree video
streaming. Collaborative FoV prediction for live 360 degree video streaming
was investigated in [10] under the framework of “user flocking”. However, it
was not used to design special edge caching algorithms and FoV prediction
accuracy will drop for long-term prediction. The focus of our work is to
design novel edge caching algorithms exploiting long-term collaborative FoV
prediction and edge-based tile transcoding to achieve high bandwidth savings
in live 360 degree video streaming with low edge cache storage consumption. To
the best of our knowledge, this is the first work to use edge-caching to
minimize total communication and transcoding cost in live 360 degree video
streaming.

Figure 1: System Workflow of Edge-assisted Live 360 Degree Video Streaming.

##  III Edge-Assisted Live 360 Degree
Video Streaming

Before diving into the detailed caching algorithm designs, we present an
overview of how live 360 degree video streaming can benefit from caching and
transcoding on edge boxes. A live event is captured as a 360 degree video
whose frames are temporally grouped into Group-of-Pictures (GoPs). Each GoP is
spatially partitioned into tiles, each of which contains video along a certain
direction. Each tile is encoded into multiple quality levels. Adaptive
streaming dynamically selects the quality level to be streamed to match the
available bandwidth. We focus on a group $\mathcal{V}$ of viewers of the live
event served by a common local edge box. When viewer $i$ joins the live
broadcast, she chooses an initial playback latency $l_{i}$ and streaming
buffer length $b_{i}<l_{i}$ based on her network condition. In general,
viewers with stronger/more stable network connections can afford to select
shorter $l_{i}$ and $b_{i}$. At time $t$, viewer $i$ plays tiles captured at
time $t-l_{i}$, while downloading tiles captured at time $t-l_{i}+b_{i}$. We
define $d_{i}\triangleq l_{i}-b_{i}$ as the tile download lag of viewer $i$.
To reduce bandwidth consumption, only tiles inside the viewer’s FoV are
downloaded. To facilitate this, viewer $i$’s FoV for video at $t-l_{i}+b_{i}$
is predicted based on her FoV trajectory for the video up to $t-l_{i}$, and
the tiles in the predicted FoV will be downloaded. Instead of requesting tiles
directly from the original streaming server, viewer $i$ uses the edge box as
her streaming proxy. If a requested tile is already in the edge cache, the
tile can be directly streamed from the edge box, without generating traffic in
the core/backbone network. If the requested quality version is lower than the
cached version, transcoding will be conducted and the transcoded tile will be
streamed to the viewer. Fig. 1 illustrates how different streaming and caching
functions work together:

  1. 1.

A viewer joins the live 360 degree video broadcast with initial playback
latency and streaming buffer length.

  2. 2.

The viewer’s FoV trajectory is fed to a FoV prediction module to predict her
future FoV.

  3. 3.

Based on the FoV prediction, the future tile popularity is estimated for the
viewer.

  4. 4.

Tile caching scores are calculated according to the tile popularity, as
detailed in Section IV-D and transcoding-aware variant in Secton V.

  5. 5.

Tiles in the predicted FoV will be requested. Tile downloading requests are
directed to the edge server, which will check whether the requested tile is in
cache or not.

  6. 6.

If the requested tile is cached (potentially after transcoding), the tiles
will be sent to the viewer’s local streaming buffer.

  7. 7.

If the requested tile is not cached, a new request is sent to the remote
server and download the missed tile from remove server to local edge cache.

  8. 8.

The viewer plays tiles from the head of the buffer. We assume that each viewer
will always download a base layer tile with a low resolution, but it will
encompass the entire 360 degrees scene.

  9. 9.

The updating module will consult the caching scores generated by the caching
policy to update the cache. It notes that whenever a new tile request is
received, the associated caching scores will be updated.

##  IV Edge Tile Caching based on Collaborative FoV Prediction

###  IV-A Live 360 Degree Video Tile Caching

Among a group $\mathcal{V}$ of viewers, the video tile captured at time $t$
will be requested first by the viewer with the shortest tile download lag at
time $t+min_{i\in\mathcal{V}}d_{i}$. The tile will be streamed from the remote
streaming server and can be cached in the local edge server to serve the other
viewers. The last request for this tile will be generated by a viewer at time
$t+max_{i\in\mathcal{V}}d_{i}$. A naive tile caching solution is to store the
tile for the duration of
$max_{i\in\mathcal{V}}d_{i}-min_{i\in\mathcal{V}}d_{i}$ so that all subsequent
requests for the tile can be served from the edge cache. We call this base
caching algorithm as Caching-All. We will compare its performance with our
proposed caching algorithms in Fig. 6 in Section VI. A major disadvantage of
Caching-All is that, since different viewers have different interests, if a
tile is not viewed by any subsequent viewers, the cache space is wasted. To
efficiently use edge cache space, we predict the probability of a newly
downloaded tile being watched by future viewers, and only cache tiles that are
predicted to be highly popular. We will use collaborative viewer FoV
predictions to generate accurate estimates of future tile popularity.

###  IV-B Collaborative Viewer FoV Prediction

During the live streaming session, the viewer’s FoV is recorded for each
frame. We quantify the viewer’s interest for each tile of a GoP as the average
overlap ratio of the tile with the viewer’s FoV for each frame in the GoP. At
a given time $t$, we have the ground-truth of the viewer $i$’s interests for
video up to $t-l_{i}$. To pre-fetch video at $t-d_{i}$, we need to predict the
viewer’s interest for video at $t-d_{i}$, with the streaming buffer length
$b_{i}=l_{i}-d_{i}$ being the prediction interval. In addition to the viewer
$i$’s own past tile interests, we also have the ground-truth viewing interests
for viewers who have already played video segment $t-d_{i}$, namely, all
viewers with playback latency $l_{j}<d_{i}$. Since viewers of the same event
often share common viewing interests, those viewers’ tile interests are also
used to predict the target viewer’s tile interests. As illustrated in Fig 2,
we adopt a collaborative FoV prediction algorithm from [10]. The prediction
has two parts: 1) Truncated Linear Prediction (TLP) based on the target
viewer’s past FoV trajectory for video up to $t-l_{i}$, 2) a weighted sum of
similar viewers’ tile interests for video segment $t-d_{i}$. The similarity
between a pair of viewers is measured by the distance between their FoV
trajectories for the last one second using the Dynamic Time Warping (DTW)
algorithm.

###  IV-C Tile Request Time Prediction

Due to the limited size of the edge caching memory, it is essential to place
the correct content at the appropriate time. We not only forecast whether a
tile will be requested by a viewer, but also when the viewer will request it,
so that we can adjust the cached content in a timely manner. Predicting the
time of content requests is usually a difficult task for general edge content
caching. In live streaming, a viewer usually downloads and plays video
segments sequentially. Given a download delay $d_{i}$, viewer $i$ will
download tiles from the video segment $t-d_{i}$ at time $t$ with a stable
network connection. We are concentrating on a cost-efficient edge caching
system, similar to [20, 21, 22], where we assume that users have a reliable
network connection and all requests can be fulfilled from either the edge
caching server or the remote server. By combining the prediction of viewer
$i$’s tile interests for video segment $t-d_{i}$ with this, we can generate
high-quality real-time caching scores for all active tiles.

###  IV-D Tile Caching Score based on FoV Prediction

For the group of viewers who are using a same edge server, we predict the
popularity of a tile within a video segment by aggregating the predicted
viewing interests of all viewers who have not watched this video segment. If
we predict that a viewer will watch tile $c$ at future time $\tau$, we will
generate a per-user predictive caching score as:

$\mathcal{S}(u,c,t)=\delta(t-\tau),$ (1)

where $\delta(\cdot)$ is the unit impulse function as illustrated in Fig. 3.
To get the caching score for a tile, we aggregate the predictive caching
scores from all viewers who have not watched this segment, which is
$\mathcal{V^{\prime}}$:

$\mathcal{S}_{a}(c,t)=\sum_{u\in\mathcal{V}^{\prime}}S(u,c,t)$ (2)

Figure 2: In a streaming system, if the current time is $\tau$, $u_{3}$ is the
user with the shortest playback latency and will watch segment $t-2$. $u_{2}$
will watch the segment $t-3$, and $u_{1}$ will watch the segment $t-6$. If the
buffer length is 2, $u_{1}$ needs to predict FoV for the segment $t-4$, which
has been watched by $u_{2}$ and $u_{3}$. Therefore, we can use the FoVs of
$u_{2}$ and $u_{3}$ on the segment $t-4$ for collaborative FoV prediction. The
weight used to combine the FoV information from $u_{2}$ and $u_{3}$ is based
on the similarity between $u_{1}$ and these two users.

Figure 3: The aggregation of scores from $n$ viewers for a tile $c$ yields a
caching score $S_{a}(c,t)$ at the current time $t$. Each viewer has a single
contribution $S(u,c,t)$ to the score.

Considering that the accuracy of FoV forecasting diminishes as the prediction
horizon increases, we compute the ultimate caching score as the integral of
$S_{a}(c,t)$ weighted by a time-decaying penalty function:

$\mathcal{S}_{f}(c)=\int_{t}^{t+T}S_{a}(c,\tau)P(\tau)\,d\tau,$ (3)

where a linearly decaying function $P(\tau)=T-\tau+t$ is used in our
experiments. An illumination is shown in Figure. 4. Note that $S(u,c,t)$ will
be updated after each new tile request from each viewer. So the final caching
score $S_{f}(c)$ is also dynamically updated as new FoV predictions are
generated. Another potential advantage of the penalty function is that we do
not rely on the predicted FoV beyond the time horizon $T$, because predictions
beyond $T$ have no impact on $S_{f}(c)$.

Figure 4: Once an aggregated predictive caching score has been obtained, a
penalty curve will be applied to penalize scores at extended prediction
horizons, as accuracy may decrease at these points.

###  IV-E Predictive Tile Caching

Based on the predictive tile caching score $S_{f}(c)$, we design a caching
policy for live 360 degree video streaming, as demonstrated in Algorithm. 1.

Algorithm 1 Predictive Edge Tile Caching

1:Input: user $u$ requests content $c_{i}$, i indicates item/tile, time is $t$

2:Output: refreshed items in cache.

3:if tile $c_{i}$ in cache then

4: $hit++$

5:else

6: add $c_{i}$ in cache

7:end if

8:remove all tiles of segments $\tau$ in cache, where $\tau<t-d_{max}$

9:while total tile size in cache $>$ Cache Size do

10: get the lowest $S_{f}(c_{j})$ from cache

11: remove $c_{j}$ from cache

12:end while

The predictive caching score $S_{f}(c)$ is employed in cache replacement. When
the cache is full, tiles with the lowest $S_{f}(c)$ will be evicted.
Additionally, all tiles of segment $t-d_{max}$ will be taken out of the cache
at time $t$, since no viewer will ask for it in the future. In reality,
different viewers have different access networks with varying bandwidths and
rendering devices with different maximum resolutions. Different viewers may
request the same tile at different quality levels. Without transcoding on the
edge, the tile at each quality level is considered as a distinct item in
caching score update and cache replacement using Algorithm 1.

##  V Transcoding-aware Caching

Recently, edge servers have been increasingly utilized for content delivery.
They are equipped with computing resources to support real-time transcoding
for 360 degree videos. Despite the growing computational power of edge
servers, the cost of transcoding can still not be ignored. For example, by AWS
Elemental MediaConvert Pricing [23], the per minute transcoding cost for 4K
video can be $0.045. On the other hand, the storage cost is relatively low
compared to the bandwidth and transcoding costs [24]. For instance, a cache
node cache.m5.12xlarge, with 48 vCPUs and 157.12 GB of memory, costs $3.744
per hour. However, a single high-resolution 360 degree video can reach 3.29
Gbit/s [25]. At the same time, extra large caching memory is slow and edge
servers usually have limited storage capacity. Therefore, it is essential to
consider how to do edge caching with a limited cache size, especially as file
sizes become larger in the future.

We present TransCoffee, a transcoding-aware, cost-effective edge caching
policy for live 360-degree video streaming that takes into account transcoding
costs. The TransCoffee caching score $S_{Tcf}$ is transcoding-aware, meaning
that the caching gain for each tile at one quality level depends on whether
the same tile has been cached at other quality levels. For instance, if a high
quality tile is cached, caching lower versions of the tile may not be
necessary since they can be obatined through transcoding from the cached high
quality tile. As a result, we need to estimate the additional gain of caching
a tile at certain quality level given the cached quality levels. We resort to
the Shapley Value [26] to fairly divide the profits from cooperation when
multiple versions of a tile are required to be cached. This is an average of
the marginal contributions from all possible permutations of cached versions.
However, in a real-time caching system, we need an instant gain of each tile,
so we use the instant marginal contribution [27] from the Shapley value. If
the cache system is not real-time, the expectation of marginal contribution
may be necessary.

First, we have $M$ quality versions for each tile, the size of version $r$ is
$w(r)$ and let’s say: $w(0)<w(1)<...<w(r)<...w(M)$. For each tile $c$ at
resolution $r$, we use Equation 4 to represent the final transcoding-aware
caching gain for $c_{r}$, which evaluates the unit caching gain of caching
this tile $c_{r}$ at time $t$. It is noted that all the variables related to
caching gain are time dependent; however, for the sake of simplicity, the time
variable $t$ is omitted in the notation, for example, $S_{Tcf}(c_{r},t)$ is
written as $S_{Tcf}(c_{r})$.

$S_{Tcf}(c_{r})=\frac{G_{Tcf}(R_{in}\cup c_{r})-G_{Tcf}(R_{in})}{w(r)},$ (4)

where $G_{Tcf}(X_{c})$ represents how much gain we can get if we cache the
tile set $X_{c}$, where $X_{c}$ is an arbitrary set of resolution levels for a
tile $c$. $R_{in}^{(c,r)}$ is the set of the other cached resolution levels
except level $i$. We mark it as $R_{in}$ for simplification. Similarly,
$R_{out}^{(c,r)}$ is the set of the other non-cached resolution levels except
level $r$, and we mark it as $R_{out}$. For one tile $c$, $R_{in}\cup
R_{out}\cup c_{r}=\\{c_{0},c_{1},...,c_{M}\\}$.
The cost of transcoding, as demonstrated in the test in [28] and the pricing
of commercial transcoding services such as AWS Elemental MediaConvert [23], is
largely dependent on the target resolution level. Therefore, we define the
cost of transcoding to target level $k$ as $T_{k}$ regardless of the original
resolution. Additionally, the bandwidth overhead is another factor to consider
and we define the unit downloading cost as $B_{c}$, which indicates the amount
of money spent on downloading one unit size of the content. The total caching
gain after adding the resolution level $r$ to the currently cached resolution
levels is:

$\begin{split}G_{Tcf}(R_{in}\cup c_{r})&=\sum_{j\in R_{in}}P_{j}*w(j)*B_{c}\\\
&+P_{r}*w(r)*B_{c}\\\ &+\sum_{k\in
R_{trans}}P_{k}*(w(k)*B_{c}-T_{k}),\end{split}$ (5)

where $P_{r}$ is the popularity of tile $c$ at resolution level $r$ and it can
be predicted by $\mathcal{S}_{f}(c)$ in Equation. 3. The first two terms are
the bandwidth cost saving from serving directly from cached tiles without
transcoding. The last term is the net cost saving resulted from serving
requests after transcoding cached tiles, which is the bandwidth cost saving
minus the transcoding cost. $R_{trans}$ is the set of resolution levels that
are currently not cached, but can be served by transcoding the cached
resolution levels:

$R_{trans}\triangleq\\{c_{m}:c_{m}\in R_{out},m<pivot\\}$ (6)

where $pivot=\max$ resolution level in $\\{R_{in}\cup c_{r}\\}$. We call
$R_{trans}$ the set of resolutions covered by transcoding.

Similarly, the caching gain of the other cached tiles except level $r$ is:

$\begin{split}G_{Tcf}(R_{in})&=\sum_{j\in R_{in}}P_{j}*w(j)*B_{c}\\\
&+\sum_{k\in R_{trans^{\prime}}}P_{k}*(w(k)*B_{c}-T_{k})\end{split}$ (7)

where

$R_{trans^{\prime}}\triangleq\\{c_{m}:c_{m}\in R_{out}\cup
c_{r},m<pivot^{\prime}\\}$ (8)

and $pivot^{\prime}=\max$ resolution level in $\\{R_{in}\\}$.
Compared to Equation 5, version $i$ cannot be served directly from the cache,
but if a higher version is in the cache, version $r$ can still be served after
transcoding. Overall, the set of transcoding-covered resolutions may shrink if
we remove the current resolution $c_{r}$. Therefore, the caching gain of
adding level $r$ to the current cache is:

$\begin{split}S_{Tcf}(c_{r})*w(r)&=P_{r}*w(r)*B_{c}\\\
&+\sum_{k\in\\{R_{trans}\\}}P_{k}*(w(k)*B_{c}-T_{k})\\\
&-\sum_{k\in\\{R_{trans^{\prime}}\\}}P_{k}*(w(k)*B_{c}-T_{k})\end{split}$ (9)

To further simplify $S_{Tcf}(r_{r})$, we define $R^{r+}$ as the set of cached
tiles with a resolution level higher than $r$, and $R^{r-}$ as the set of
cached tiles with a resolution level lower than $r$. Thus, $R_{in}$ is the
union of $R^{r-}$ and $R^{r+}$.
If $R^{r+}\neq\emptyset$, which means that there is a higher level of tile in
the cache and then:

$R_{trans^{\prime}}=R_{trans}\cup c_{r}$ (10)
$\begin{split}S_{Tcf}(c_{r})&=P_{r}*B_{c}-P_{r}*(B_{c}-\frac{T_{r}}{w(r)})\\\
&=P_{r}*\frac{T_{r}}{w(r)}\end{split}$ (11)

If $R^{r+}=\emptyset$, which means $c_{r}$ is the highest level, then

$R_{trans}-R_{trans^{\prime}}\triangleq\\{c_{m}:c_{m}\in
R_{out},pivot^{\prime}<m<r\\}$ (12)

$\begin{split}S_{Tcf}(c_{r})&=P_{r}*B_{c}\\\
&+\frac{1}{w(r)}\sum_{k\in\\{R_{trans}-R_{trans^{\prime}}\\}}P_{k}*(w(k)*B_{c}-T_{k})\end{split}$
(13)

Besides, if we use real transcoding and download cost, sometimes, transcoding
cost can larger than downloading cost, so we only execute transcoding when
$B_{c}>\frac{T_{r}}{w(r)}$. So the final unit transcoding gain is:

We have:

$\begin{split}S_{Tcf}(c_{r})&=P_{r}*B_{c}-P_{r}*\max\\{(B_{c}-\frac{T_{r}}{w(r)}),0\\}\\\
\end{split}$ (14)

So

$\begin{split}&S_{Tcf}(c_{r})=P_{r}*B_{c}\\\
&+\frac{1}{w(r)}\sum_{k\in\\{R_{trans}-R_{trans^{\prime}}\\}}\max\\{P_{k}*(w(k)*B_{c}-T_{k}),0\\}\end{split}$
(15)

As long as we possess a TransCoffee score $S_{Tcf}(c_{r})$, we will update the
cache by utilizing Algorithm 2. Note that to simplify the expression, we omit
subscript $t$ in TransCoffee score $S_{Tcf}(c_{r})$, which is dynamic and will
be updated over time for real time edge caching. Besides, the latency of
transcoding is usually insignificant and can be accommodated in the user’s
streaming buffer[28], such as two seconds.

Algorithm 2 Transcoding-aware Edge Caching Update Policy

1:Input: user $u$ requests content $c_{i,r}$, i indicates item/tile, where r
indicates resolution of this tile. $T_{c}$ and $D_{c}$ indicates transcoding
and downloading cost of tile $c$. Real-time caching score $S(c,t)$ at time $t$
of tile $c$.

2:Output: refreshed items in cache.

3:if $c_{i,r}$ $\in$ cache then

4: $hit++$

5:else if tile $c_{i,h}$ $\in$ cache, where $h>r$ and
$T_{c_{i,r}}<D_{c_{i,r}}$ then

6: transcode $c_{i,h}$ to $c_{i,r}$

7: add $c_{i,r}$ in cache

8: $hit++$

9:else

10: download $c_{i,r}$ from remote server and add it to cache

11:end if

12:while total tile size in cache $>$ Cache Size do

13: get the $c_{j,k}$ with lowest $S_{Tcf}(*)$ from cache

14: remove $c_{j,k}$ from cache

15:end while

##  VI Performance Evaluation

We simulate edge caching assisted live 360 degree video streaming to assess
the effectiveness of the proposed algorithms.

###  VI-A Dataset

We utilize a public 360-degree video dataset from [29], which consists of 48
viewers (24 males and 24 females) watching sphere videos. The first three
videos from different categories are chosen and their details are presented in
Table I. Unless otherwise specified, single-video experiments are conducted in
video0. We assume that each video is divided into GOPs of 1 second and each
GOP is spatially partitioned into 30 tiles (5*6). The viewer’s request for
each GOP is generated based on her average interest ratio for the 30 frames in
the GOP. A viewer will request a tile if it has overlap with the predicted
FoV. We assign a playback latency of $l_{i}$ to all users, with a uniform
distribution over a period of 20 seconds. Following the 360-degree video
resolution in [30], we set the entire 360-degree video coded in 100, 500,
1000, 1500, 2000, and 2500 Mbps.

Video Index | Video Name | Video Category
---|---|---
video0 | Conan360-Sandwich | Performance
video1 | Freestyle Skiing | Sports
video2 | Google Spotlight-HELP | Film
TABLE I: We use three videos from different categories, where viewers have
different FoV patterns.

###  VI-B Live Streaming System Configurations

In live streaming, tiles have short life spans, meaning that after a certain
period of time, no viewers will request them. The playback latency for
streaming services, such as those offered by sports networks and platforms
like ESPN, NBC Sports, and CBS Sports, can be as long as 40 seconds [31],
while for cable and satellite, it can be around 5 seconds. In our experiments,
we set the maximum viewer download time lag as $d_{max}=20$ second. A tile is
considered inactive after it has been viewed for the first time and 20 seconds
have elapsed. We set the cache size from 0 to a sufficiently large size, at
which the cache memory can store all the active tiles. We normalize the cache
size by the memory needed to cache all active tiles at the highest resolution:
given the longest download time lag is $d_{max}$, the number of tiles in each
GOP is $M$, and the highest resolution tile size is $S$, the maximum cache
size is $F=d_{max}*M*S$. In our experiments, $F=187.5GB$ for one video. Unless
otherwise specified, the cache size in a figure represents the ratio over the
maximum cache size. The buffer length of the live streaming system is 2
seconds, unless otherwise noted. The $T$ in Equation. 3 is set as 15 seconds +
buffer length.

###  VI-C FoV Prediction Accuracy

In this section, we evaluate the accuracy of FoV prediction with different
prediction approaches. We evaluate these three approaches:

  * •

Truncated linear prediction(TLP) is a simple linear prediction method that
predicts a viewer’s future FoV trajectory by extrapolating from the recent
monotone linear pattern in the nearest truncated FoV history of the viewer.

  * •

ColPB: Collaborative FoV prediction with boundary constraint, a FoV prediction
method that predicts a user’s next tile based on the collaborative FoV
prediction algorithm of [10]. FoV of the target viewer for an upcoming video
segment is predicted using the target viewer’s own trajectory as well as the
trajectories of viewers who have watched this video segment. The prediction
gives a higher weight to the target viewer’s own trajectory with

$\max\left\\{\frac{1}{1+sum(similarities)},0.8\right\\},$ (16)

where $sum(similarities)$ is the sum of similarity of all viewers who have
watched the segment. The weight given to the other viewers is one minus the
weight to the target viewer.

  * •

ColP-Long: We customize ColPB [10] for long-term FoV prediction necessary for
360-degree live video caching. We remove the lower bound of 0.8 in (16). This
is because a longer prediction horizon is needed than that of ColPB. TLP-based
self-prediction does not perform well when predicting at a long horizon. By
removing the lower bound of 0.8, if the summation of similarities with the
front viewers is high, more reliance is placed on the front viewer’s
information rather than the viewer’s self-trajectory for collaborative
prediction. Additionally, instead of prefetching the top k tiles as in ColP,
we select a FoV whose coverage of tiles can maximize the total tile weight
within that FoV to calibrate the tile distribution prediction.

Figure 5: The y-axis in Fig.a is the ratio of overlap between the actual FoV
of the viewer and the predicted FoV at different prediction horizon lengths.
In Fig.b, we calculate the L2 loss between the predicted tile probability and
the tile distribution in the viewer’s actual FoV. If a tile is partially
overlapped with the FoV, the value for the tile is the fraction of tile pixels
in the FoV. If a tile is completely in the FoV, the value is 1. After
normalization, we obtain a distribution of all tiles for the user’s actual
FoV. We compare the L2 loss between these two distributions in Fig.b. Since we
have a buffer length of 2 seconds, we only consider the prediction accuracy
after the buffer length.

We conducted experiments to compare the accuracy of three FoV prediction
methods. We used the target viewer’s FoV trajectory in the last GoP to predict
the future trajectory for TLP. Figure 5 shows the evaluation of the overlap
ratio with the viewer’s actual FoV in video 0. The x axis is the length of the
prediction horizon. Figure 5 (a) illustrates the fraction of tiles in the
viewer’s actual FoV that can be covered by the downloaded tiles based on the
FoV predictions. We can see ColP-Long has consistently higher overlapping
ratios than TLP and ColPB at all prediction horizons. This is important to
generate accurate predictive caching scores.

###  VI-D Caching without Transcoding

We begin by utilizing our prediction module and pre-user caching score for
non-transcoding scenarios. We set different resolutions for tiles to compare
with the transcoding cases in the next section. Each viewer has a specific
resolution on her device and can only request that resolution. The edge server
does not have transcoding ability and considers different versions of the same
tile as distinct content items. Algorithm 1 is employed for non-transcoding
caching. We compare our algorithm with three live 360 degree video caching
baselines using different tile caching scores.

  * •

LRU-live: a caching replacement policy that evicts content based on the time
elapsed since the last request for a tile and with similar tile eviction after
$d_{max}$. It eliminates a tile from the cache after the longest download wait
time $d_{max}$ (20 seconds in this case). As after 20s, the tile will never be
asked for111We also tested on LFU-live, which yielded much poorer results than
LRU-live, as the lifespan of live video tiles is brief..

  * •

NOC-live, as described in [32], is designed to minimize the difference between
the performance of an online learning algorithm and the best dynamic policy
that could have been chosen in hindsight. To adapt to fast popularity changes
of live video tiles, the step size delta is set to 0.9. After $d_{max}$
seconds, tiles will no longer be requested and will be removed from the live
streaming cache.

  * •

Latency-FoV (LF)*. In [10], a 360 degree live video streaming caching policy
was proposed, which is based on the Least Recently Used (LRU) approach. It
groups users based on their FoV trajectory similarity, and then marks users
with the longest latency witin each group, and ignores the content downloaded
by those users. In contrast, we put all users in the same group, and mark
users with the longest 25% latency and not cache content downloaded by these
users, since only a few future users can benefit from them.

  * •

Coffee: This is our caching scheme without transcoding. It eliminates content
based on the dedicated caching score, which is determined by the collaborative
FoV prediction approach. Specifically, ColP-long is chosen for FoV prediction
as it is more effective than TLP and ColP. The caching score is
$\mathcal{S}_{f}(c)$ in Equation 3.

Figure 6: The back-haul load reduction ratio for Video0 without trans-coding is compared for different cache sizes. The x axis of the graph ranges from 0 to 262GB, with the unit cache size being 187.5GB. Our method outperforms all benchmarks, and can almost double the back-haul load reduction, due to the precise predictive caching scores generated by the per-viewer FoV prediction. For example, Coffee will reduces the back-haul traffic up to 76% compared to LF* when cache size is 0.4. The area on the right hand side indicate the Caching-All, which means cache size is large enough to cache all tiles. TABLE II: Back-haul load reduction for Ours, NOC-live, LRU-live on different cache size and videos. Scenarios | Cache Size=0.4 | Cache Size=0.8 | Cache Size=1.2
---|---|---|---
Method | Video0 | Video1 | Video2 | Video0 | Video1 | Video2 | Video0 | Video1 | Video2
LRU-live | 0.2628 | 0.2443 | 0.2447 | 0.4441 | 0.4521 | 0.4165 | 0.6729 | 0.6346 | 0.6565
NOC-live | 0.2622 | 0.2547 | 0.2372 | 0.4596 | 0.4292 | 0.4157 | 0.6472 | 0.5979 | 0.5864
LF* | 0.2243 | 0.2183 | 0.2047 | 0.5145 | 0.4839 | 0.5238 | 0.7107 | 0.6932 | 0.6762
Coffee | 0.3951 | 0.4228 | 0.3879 | 0.6632 | 0.6397 | 0.6428 | 0.7483 | 0.7024 | 0.7289

The reduction ratio in back-haul bandwidth, which is the bandwidth consumption
in the connection between the edge server and the original content server,
with different cache sizes for video0 is depicted in Fig. 6. Our method
consistently outperforms the baselines. When the cache size is unlimited, all
caching policies will have the same performance by caching everything they
encounter. Nevertheless, since the high resolution of 360 videos can be very
large, it is still important to reduce the back-haul bandwidth using as little
cache space as possible. Our approach is aware of which resolution a viewer
will request, and this also boosts its performance since different versions of
a tile are distinct content items without transcoding. We have similar results
in other videos, as summarized in Table.II.

Furthermore, it only takes $0.019067$ second to finish each prediction of user
content interest (10 seconds horizon) and the cache score aggregation. Our
predictive algorithms are efficient and can be implemented in real time.

###  VI-E Transcoding-aware Caching

We evaluate the effectiveness of our Transcoffee system with various caching
policies by utilizing transcoding-aware Algorithm 2.

Baseline:

  * •

TransCoffee: We propose a Transcoding-aware cost-effective edge caching
technique that eliminates content based on the anticipated popularity of the
tile. This approach is derived from the ColP-long FoV prediction approach and
a specialized transcoding-aware tile score.

  * •

Coffee: The Coffee method does not have the capacity to transcode. It applies
the same FoV prediction model and the caching score without the transcoding
term, as indicated in Equation 3.

  * •

LRU-live-T: It is an LRU-live-based transcoding-variant method and caching
policy based on Algorithm 2. When the cache is full, contents are evicted
using their LRU scores.

  * •

E-Transcoding[10]: Always cache the highest-level tile and run transcoding all
the time. This approach requires only one level of tile in the cache, and we
use ColP-long to predict the future popularity of tiles, based on which we use
(3) to calculate their caching scores for eviction.

  * •

LF*-T. We use a transcoding version of modified Latency-FoV in [10], and cache
updating follows Algorithm 2.

  * •

NOC-live-T: It’s a NOC-live-based caching method [32] with transcoding
resources, and follows the cache updating Algorithm 2.

  * •

ETE_0C: End-to-end baseline with zero cache size, like [33], this approach
just delivers tiles to users directly without cache to bound the caching
performance.

####  VI-E1 Transcoding and downloading cost

We assess the performance of TransCoffee by considering the transcoding and
downloading costs from the latest AWS Elemental MediaConvert Pricing [23] for
transcoding and Amazon EC2 On-Demand Pricing [34] for downloading cost. The
cost of transcoding (per minute) for each tile depends on the resolution: 4K
is $0.045, HD is $0.0225 and SD is $0.0113. The downloading cost is based on
the coded tile size and is $0.09 per GB. Additionally, from [28] [23],
transcoding cost is mostly determined by the target resolution level. To fully
evaluate the effect of the transcoding cost, we also have different
transcoding/downloading cost ratios(T/D ratios), which will be discussed in
Section VI-E3.

####  VI-E2 Streaming cost

Figure 7: The total cost per user for each method is shown in the subfigures,
with the x-axis representing the cache size and the y-axis representing the
cost in dollars. The cost of transcoding and downloading is based on the
prices of AWS. TransCoffee constantly outperforms all state-of-the-art
baselines on different cache sizes and different videos, and the cost
reduction compared to LF*-T can reach 63% when the cache size is 0.5 on video
0.

(a)

(b)

(c)

Figure 8: Fig. (a) shows the total cost over time for video 0 when using AWS
pricing and a cache size of 0.75. Fig. (b) displays the total cost per user
for different ratios of transcoding and downloading costs. Fig. (c)
illustrates the transcoding traffic with the transcoding and downloading cost
ratio. Figure 9: The viewer’s interest hit byte ratio over time for video 0,
with the x-axis representing the stream time in seconds and the y-axis
representing the fraction of tiles in the viewer’s actual FoV that can be
rendered using the tiles downloaded in the streaming buffer.

We evaluate caching performance with varying cache sizes for different videos
in Fig. 7. TransCoffee outperforms the other benchmarks. Fig.8(a) illustrates
the cost with time for all methods when the cache size is 0.5 and the
streaming cost is based on the AWS price. TransCoffee manages to achieve the
lowest cost throughout the streaming process.

####  VI-E3 Performance on different T/D ratio

We evaluated the effect of transcoding cost and the robustness of our method
by conducting extra experiments on different transcoding and downloading cost
ratios. We fixed the downloading cost using the AWS bandwidth price and
proportionally changed the transcoding cost to get different T/D ratios. In
Fig. 8(b), it is shown that the total cost per user with different T/D ratios
when the cache size is 0.5. TransCoffee has the lowest streaming cost compared
to all the baselines, and its performance can converge towards E-Transcoding
when the transcoding cost is low (always transcoding) and to Coffee (no
transcoding) when the transcoding cost is higher than the downloading cost.
Between 0 to 1, TransCoffee has a much lower cost compared to the other
methods, demonstrating the robustness of our method with different T/D cost
ratios. In Fig. 8(c), we evaluated transcoding traffic with different T/D
ratios when the cache size is 0.5. Transcoding traffic of TransCoffee
decreases with increasing T/D ratio. When the transcoding cost is 0,
TransCoffee utilizes transcoding as much as possible to save streaming cost,
and when the transcoding cost is equal to the downloading cost, no more
transcoding will be used to save streaming cost. The adaptation of transcoding
traffic is consistent with Fig. 8(b), indicating that TransCoffee can
adaptively utilize transcoding resources by referring to our transcoding-aware
caching score, thus reducing the total streaming cost.

###  VI-F Hit Ratios for Different Groups of Viewers

The prediction module of our system predicts the popularity of tiles based on
viewers with shorter playback latency. This allows the subsequent viewers to
benefit from the pre-downloaded tiles of the front viewers. Table III shows
the hit-byte ratio among different viewer groups. The viewer’s index is based
on the ranking of their playback latency in the live video broadcast. User0 is
the one with the shortest playback latency, and user47 has the longest
playback latency. The hit-byte ratio for the first group (user 0-5) is low
because they are the “front-runners” in the live broadcast and there are not
many pre-downloaded tiles in the cache to serve them. The following user
groups (e.g. user 6-17) can have a high hit-byte ratio if the correct tiles
are cached. However, for the later user groups, their hit-byte ratio can be
low again. This is because they are at the end of the live video broadcast,
and the tiles they request will not be requested in the future, and the
’caching gain’ for these tiles will be low. To make the best use of cache
space, our caching policy chooses to sacrifice these tiles to reserve space
for the tiles that will become ‘more popular’ in the near future. The smaller
the cache size, the more obvious this phenomenon is. This makes sense because
our goal is to reduce the whole back-haul traffic by using caching for all of
the users together, and requests with a lower hit-byte ratio can still be
satisfied by sending requests to the remote server.

user group cache size | 0.1 | 0.3 | 0.6
---|---|---|---
0-5 | 0.2485 | 0.3214 | 0.3339
6-11 | 0.7794 | 0.9201 | 0.9496
12-17 | 0.67638 | 0.9537 | 0.97807
18-23 | 0.0248 | 0.9500 | 0.9949
24-29 | 0 | 0.8772 | 0.9854
30-35 | 0 | 0.7041 | 0.9749
36-41 | 0 | 0.0551 | 0.9856
42-47 | 0 | 0 | 0.3232
TABLE III: Tile hit ratios for users with different playback latencies at
different cache sizes.

###  VI-G Viewer’s Interest Hit Byte Ratio

We assess the viewer’s interest hit byte ratio for a portion of video0. Figure
9 illustrates the fraction of tiles within a viewer’s actual FoV that can be
rendered using tiles downloaded in the streaming buffer. The average viewer’s
interest hit byte ratio is greater than 93%, indicating that we can provide a
satisfactory viewing experience to viewers using pre-fetched tiles in our
experiments.

##  VII Conclusion

This paper has demonstrated that the predictability of a viewer’s FoV and the
sequential tile download patterns of live 360 degree video streaming can be
exploited to design accurate predictive edge tile caching algorithms that
achieve high bandwidth savings with low storage consumption. We further showed
that transcoding-aware caching algorithms can improve edge caching efficiency.
Experiments conducted with real 360 video streaming traces of 48 viewers
demonstrated that our algorithms can reduce the bandwidth consumption of live
360 degree video streaming by up to 76% compared to streaming without caching.
Higher bandwidth reductions are expected with more viewers served by the same
edge cache box. Additionally, our transcoding-aware caching
algorithms(TransCoffee) outperformed the state-of-the-art edge caching
algorithm by up to 63%.

## References

  * [1] X. Wei, J. Liu, Y. Wang, C. Tang, and Y. Hu, “Wireless edge caching based on content similarity in dynamic environments,” _Journal of Systems Architecture_ , vol. 115, p. 102000, 2021.
  * [2] B. Abolhassani, J. Tadrous, and A. Eryilmaz, “Single vs distributed edge caching for dynamic content,” _IEEE/ACM Transactions on Networking_ , 2021\.
  * [3] Z. Song, D. S. Berger, K. Li, A. Shaikh, W. Lloyd, S. Ghorbani, C. Kim, A. Akella, A. Krishnamurthy, E. Witchel _et al._ , “Learning relaxed belady for content distribution network caching,” in _17th $USENIX$ Symposium on Networked Systems Design and Implementation ($NSDI$ 20)_, 2020, pp. 529–544.
  * [4] Q. Fan, X. Li, J. Li, Q. He, K. Wang, and J. Wen, “Pa-cache: Evolving learning-based popularity-aware content caching in edge networks,” _IEEE Transactions on Network and Service Management_ , vol. 18, no. 2, pp. 1746–1757, 2021.
  * [5] F. Wang, F. Wang, J. Liu, R. Shea, and L. Sun, “Intelligent video caching at network edge: A multi-agent deep reinforcement learning approach,” in _IEEE INFOCOM 2020-IEEE Conference on Computer Communications_. IEEE, 2020, pp. 2499–2508.
  * [6] J. Ye, Z. Li, Z. Wang, Z. Zheng, H. Hu, and W. Zhu, “Joint cache size scaling and replacement adaptation for small content providers,” in _IEEE INFOCOM 2021-IEEE Conference on Computer Communications_. IEEE, 2021, pp. 1–10.
  * [7] H. Tian, X. Xu, T. Lin, Y. Cheng, C. Qian, L. Ren, and M. Bilal, “Dima: Distributed cooperative microservice caching for internet of things in edge computing by deep reinforcement learning,” _World Wide Web_ , vol. 25, no. 5, pp. 1769–1792, 2022.
  * [8] T. Zong, C. Li, Y. Lei, G. Li, H. Cao, and Y. Liu, “Cocktail edge caching: Ride dynamic trends of content popularity with ensemble learning,” _IEEE/ACM Transactions on Networking_ , 2022.
  * [9] S. Han, H. Su, C. Yang, and A. F. Molisch, “Proactive edge caching for video on demand with quality adaptation,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 1, pp. 218–234, 2019.
  * [10] L. Sun, Y. Mao, T. Zong, Y. Liu, and Y. Wang, “Flocking-based live streaming of 360-degree video,” in _Proceedings of the 11th ACM Multimedia Systems Conference_ , 2020, pp. 26–37.
  * [11] P. Maniotis and N. Thomos, “Tile-based edge caching for 360° live video streaming,” _IEEE Transactions on Circuits and Systems for Video Technology_ , vol. 31, no. 12, pp. 4938–4950, 2021.
  * [12] T. Yang, Z. Tan, Y. Xu, and S. Cai, “Collaborative edge caching and transcoding for 360° video streaming based on deep reinforcement learning,” _IEEE Internet of Things Journal_ , vol. 9, no. 24, pp. 25 551–25 564, 2022\.
  * [13] H. Xiao, C. Xu, Z. Feng, R. Ding, S. Yang, L. Zhong, J. Liang, and G.-M. Muntean, “A transcoding-enabled 360 vr video caching and delivery framework for edge-enhanced next-generation wireless networks,” _IEEE Journal on Selected Areas in Communications_ , vol. 40, no. 5, pp. 1615–1631, 2022.
  * [14] J. Li, L. Han, C. Zhang, Q. Li, and Z. Liu, “Spherical convolution empowered viewport prediction in 360 video multicast with limited fov feedback,” _ACM Transactions on Multimedia Computing, Communications and Applications_ , vol. 19, no. 1, pp. 1–23, 2023.
  * [15] A. Yaqoob and G.-M. Muntean, “A combined field-of-view prediction-assisted viewport adaptive delivery scheme for 360° videos,” _IEEE Transactions on Broadcasting_ , vol. 67, no. 3, pp. 746–760, 2021.
  * [16] A. Sarkar, J. Murray, M. Dasari, M. Zink, and K. Nahrstedt, “L3bou: Low latency, low bandwidth, optimized super-resolution backhaul for 360-degree video streaming,” in _2021 IEEE International Symposium on Multimedia (ISM)_. IEEE, 2021, pp. 138–147.
  * [17] L. Zhong, X. Chen, C. Xu, Y. Ma, M. Wang, Y. Zhao, and G.-M. Muntean, “A multi-user cost-efficient crowd-assisted vr content delivery solution in 5g-and-beyond heterogeneous networks,” _IEEE Transactions on Mobile Computing_ , 2022.
  * [18] M. Wang, X. Chen, X. Yang, S. Peng, Y. Zhao, M. Xu, and C. Xu, “Colive: Edge-assisted clustered learning framework for viewport prediction in 360∘ live streaming,” _IEEE Transactions on Multimedia_ , pp. 1–13, 2023.
  * [19] Y. Ban, L. Xie, Z. Xu, X. Zhang, Z. Guo, and Y. Wang, “Cub360: Exploiting cross-users behaviors for viewport prediction in 360 video adaptive streaming,” in _2018 IEEE International Conference on Multimedia and Expo (ICME)_. IEEE, 2018, pp. 1–6.
  * [20] P. Maniotis and N. Thomos, “Tile-based edge caching for 360° live video streaming,” _IEEE Transactions on Circuits and Systems for Video Technology_ , vol. 31, no. 12, pp. 4938–4950, 2021.
  * [21] G. Papaioannou and I. Koutsopoulos, “Tile-based caching optimization for 360° videos,” in _Proceedings of the Twentieth ACM International Symposium on Mobile Ad Hoc Networking and Computing_ , ser. Mobihoc ’19. New York, NY, USA: Association for Computing Machinery, 2019, p. 171–180. [Online]. Available: https://doi.org/10.1145/3323679.3326515
  * [22] P. Maniotis, E. Bourtsoulatze, and N. Thomos, “Tile-based joint caching and delivery of 360° videos in heterogeneous networks,” _IEEE Transactions on Multimedia_ , vol. 22, no. 9, pp. 2382–2395, 2020.
  * [23] “Aws elemental mediaconvert pricing,” https://aws.amazon.com/mediaconvert/pricing/.
  * [24] “Amazon ec2 on-demand pricing,” https://aws.amazon.com/elasticache/pricing/.
  * [25] Huawei, “Whitepaper on the VR-Oriented Bearer Network Requirement (2016),” Huawei Technology, Tech. Rep., 2016, available at http://www-file.huawei.com/
media/CORPORATE/PDF/white%20paper/whitepaper-on-the-vr-oriented-bearer-
network-requirement-en.pdf.

  * [26] E. Winter, “Chapter 53 the shapley value,” ser. Handbook of Game Theory with Economic Applications. Elsevier, 2002, vol. 3, pp. 2025–2054. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1574000502030163
  * [27] S. Ieong and Y. Shoham, “Marginal contribution nets: A compact representation scheme for coalitional games,” in _Proceedings of the 6th ACM Conference on Electronic Commerce_ , ser. EC ’05. New York, NY, USA: Association for Computing Machinery, 2005, p. 193–202. [Online]. Available: https://doi.org/10.1145/1064009.1064030
  * [28] H. Xiao, C. Xu, Z. Feng, R. Ding, S. Yang, L. Zhong, J. Liang, and G.-M. Muntean, “A transcoding-enabled 360° vr video caching and delivery framework for edge-enhanced next-generation wireless networks,” _IEEE Journal on Selected Areas in Communications_ , vol. 40, no. 5, pp. 1615–1631, 2022\.
  * [29] C. Wu, Z. Tan, Z. Wang, and S. Yang, “A dataset for exploring user behaviors in vr spherical video streaming,” in _Proceedings of the 8th ACM on Multimedia Systems Conference_ , ser. MMSys’17. New York, NY, USA: Association for Computing Machinery, 2017, p. 193–198. [Online]. Available: https://doi.org/10.1145/3083187.3083210
  * [30] “360° / vr videos from a-z: Everything you need to know,” https://mobfish.net/blog/vr-videos/.
  * [31] “If you’re streaming the super bowl, expect to lag behind twitter and cable,” https://www.cnet.com/tech/services-and-software/if-youre-streaming-the-super-bowl-expect-to-lag-behind-twitter-and-cable/.
  * [32] S. Zhou, Z. Wang, C. Hu, Y. Mao, H. Yan, C. Wu, S. Zhang, and W. Zhu, “Caching in dynamic environments: a near-optimal online learning approach,” _IEEE Transactions on Multimedia_ , 2021.
  * [33] A. Mahzari, A. Taghavi Nasrabadi, A. Samiei, and R. Prakash, “Fov-aware edge caching for adaptive 360 video streaming,” in _2018 ACM Multimedia Conference on Multimedia Conference_. ACM, 2018, pp. 173–181.
  * [34] “Amazon ec2 on-demand pricing,” https://aws.amazon.com/ec2/pricing/on-demand/.