# Heterogeneous Cellular Networks with Spatio-Temporal Traffic: Delay Analysis
and Scheduling

Yi Zhong, _Member, IEEE_ , Tony Q.S. Quek, _Senior Member, IEEE_ and Xiaohu
Ge, _Senior Member, IEEE_ Manuscript received Nov. 24, 2016. Yi Zhong and
Xiaohu Ge (corresponding author) are with School of Electronic Information and
Communications, Huazhong University of Science and Technology, Wuhan, P. R.
China. (e-mail<EMAIL_ADDRESS>xhge@mail.hust.edu.cn). Tony Q.S. Quek is
with Information Systems Technology and Design, Singapore University of
Technology and Design, Singapore (email: tonyquek@sutd.edu.sg). The authors
would like to acknowledge the support from the NSFC Major International Joint
Research Project (Grant No. 61210002), Hubei Provincial Science and Technology
Department under Grant 2016AHB006, the Fundamental Research Funds for the
Central Universities under the grant 2015XJGH011. This research is partially
supported by the EU FP7-PEOPLE IRSES, project acronym CROWN (grant no.
610524), China international Joint Research Center of Green Communications and
Networking (No. 2015B01008). This work was supported in part by the MOE ARF
Tier 2 under Grant MOE2015-T2-2-104 and the Zhejiang Provincial Public
Technology Research of China under Grant 2016C31063.

###### Abstract

Emergence of new types of services has led to various traffic and diverse
delay requirements in fifth generation (5G) wireless networks. Meeting diverse
delay requirements is one of the most critical goals for the design of 5G
wireless networks. Though the delay of point-to-point communications has been
well investigated, the delay of multi-point to multi-point communications has
not been thoroughly studied since it is a complicated function of all links in
the network. In this work, we propose a novel tractable approach to analyze
the delay in the heterogenous cellular networks with spatio-temporal random
arrival of traffic. Specifically, we propose the notion of _delay outage_ and
evaluated the effect of different scheduling policies on the delay
performance. Our numerical analysis reveals that offloading policy based on
cell range expansion greatly reduces the macrocell traffic while bringing a
small amount of growth for the picocell traffic. Our results also show that
the delay performance of round-robin scheduling outperforms first in first out
scheduling for heavy traffic, and it is reversed for light traffic. In
summary, this analytical framework provides an understanding and a rule-of-
thumb for the practical deployment of 5G systems where delay requirement is
increasingly becoming a key concern.

###### Index Terms:

Delay, heterogeneous cellular networks, scheduling, spatio-temporal traffic,
stochastic geometry

##  I Introduction

###  I-A Motivation

Evolution for high-speed data applications, such as high-quality wireless
video streaming, social networking, and machine-to-machine communications, has
led to the explosive growth of data traffic demand for 5G wireless networks.
It is envisioned that the average capacity requirement of 5G wireless networks
might reach $25$ Gbps/km2, which is $100$ times higher compared to the current
system capacity. Meanwhile, the delay requirements for different types of
traffic become more diversified due to the emergence of new types of
applications [1], such as latency-critical applications like command-and-
control of drones, advanced manufacturing, and tactile Internet [2, 3]. As
wireless networks evolve, the coupling between traffic and network services
becomes increasingly strong. The tremendous traffic and its dynamic variations
play increasingly crucial roles in affecting the delay performance of 5G
wireless networks. Therefore, theoretical analysis of delay in wireless
networks is imperative to guide us in our design and deployment.

Figure 1: Example for traffic in two-tier heterogeneous networks. The traffic
is consist of the spatial distribution of users and the temporal arrival of
packets.

Though the delay of point-to-point communication has been well investigated
using classical queueing theory, the delay of multi-point to multi-point
communications, such as multi-party video conference or multi-player online
gaming, has not been well studied. This is mainly due to the fact that delay
is a complicated function of all links in the network and is affected by a
variety of factors such as the traffic, the medium access protocol, the path
loss, and so on. In order to effectively analyze traffic and delay in
heterogeneous cellular networks [4, 5, 6, 7, 8, 9], a reasonable model to
characterize both the spatial distribution and the temporal variation of
traffic should first be established (see Fig. 1). The spatial distribution of
traffic could be described by the locations of users. If the mobility of users
is not considered, the temporal variation of traffic includes two parts, i.e.,
the random arrival process of packets for each user and the dynamic serving
process of arrived packets.

###  I-B Related Works

Most of the previous works only model one aspect of traffic, i.e., either only
model the spatial distribution of users or only model the temporal arrival
process of packets. In [10], the distribution proposed in [11] was used to
approximate the probability density function (pdf) of the area for Voronoi
cell formed by single-tier macrocell base stations (BSs). With the obtained
pdf, by modeling the locations of users as a homogeneous Poisson point process
(PPP) [12, 13, 14, 15], the probability distribution of the number of users in
each Voronoi cell was derived. The works [16, 17] extended such pdfs to the
case of multi-tier heterogeneous networks. On the other hand, the analysis of
temporal variation of traffic were generally based on queueing theory and
model the traffic as the function of random arrival of packets. For example,
in [18, 19, 20, 21, 22], a discrete-time slotted ALOHA system with multiple
terminals was considered, and each terminal maintains a buffer of infinite
capacity to store incoming packets. The statuses (idle or busy) of terminals
change over time due to the random arrival and serving of the traffic, and the
serving rates also rely on the statuses of terminals since the idle terminals
will not cause any interference.

Existing works that simultaneously model the spatio-temporal arrival of
traffic, such as [23, 24, 25], considered the traffic generated at random
spatial regions, other than modeling the flow at each independent user. The
analysis in these works was based on the granularity of total traffic in each
cell, i.e., the traffic generated in the coverage region of each BS is summed
up as the traffic arrived at the corresponding BS. For example, the work in
[23] modeled the spatio-temporal arrival of users as a homogeneous spatio-
temporal PPP, then the traffic arrived at each BS was characterized by the
amount of data all users demand in the coverage of associated BS. The main
deficiencies of such a model are four aspects. First, since the users are not
definitely characterized in these models, many network operations, such as
scheduling of users in each cell and offloading traffic between cells cannot
be well captured. Meanwhile, the metric for each independent user, such as
throughput and delay, cannot be well defined. Second, due to the diversity of
traffic, the quality of service (QoS) requirement and the arrival rate are
different for different users, which cannot be appropriately modeled. Third,
the interference and the interaction between the queues at different BSs are
either ignored or only analyzed by approximations. The interacting queues
problem [26] is notoriously difficult to cope with since the statuses of
queues and the serving rates are highly coupled (see Fig. 2). Lastly, these
models are not consistent with those used in the industrial simulations [27],
in which the users are generated randomly and the packets arrive independently
as a random process at each user.

Previous works using stochastic geometry to analyze the wireless networks
focus on performance metrics such as success probability and average
achievable rate by considering a snapshot of the network. However, these
approaches are incapable to deal with long term metrics like delay, due to the
difficulties such as the interacting queues problem, the spatial-temporal
random arrival of traffic, and the static property of networks [28, 29]. The
works [30, 31, 32, 33] analyzed the transmission of traffic with delay
constraint in heterogeneous cellular networks without considering the coupling
between traffic and network services.

Figure 2: Example of interacting queues problem of two cells in which the
serving processes of the two links are coupled. For example, if one queue is
empty, the corresponding transmitter do not cause interference to the other
link; thus the serving rate of the other link will become large.

###  I-C Contributions

In this work, we model the spatio-temporal traffic by combining the tools from
stochastic geometry and queueing theory. Specifically, we model the spatial
distribution of users by PPP and model the temporal arrival of packets at
individual users by independent Bernoulli processes. Then, the data flows for
different users could be considered independently. Meanwhile, since both the
traffic and the delay requirements are diversified for different users, we
model the packet arrival process and the delay requirements for each
individual user. The main contributions of this paper can be summarized as
follows:

  * •

Several tractable approaches, for example, considering the dominant system and
the modified system, are proposed to analyze and bound the statistical
distribution of the signal-to-interference ratio (SIR) and the delay in
heterogeneous cellular networks based on the combination of stochastic
geometry and queuing theory.

  * •

Delay outage (DO) is proposed to characterize whether the delay requirement
could be achieved. Furthermore, the effect of scheduling policies, i.e., the
random scheduling, the first-input-first-output (FIFO) scheduling, and the
round-robin scheduling, on the delay is evaluated, which to our knowledge has
not been explored using stochastic geometry due to analytical difficulty.

  * •

By numerical evaluations, statistics of traffic in heterogeneous cellular
networks are investigated, and effect of spatial distribution and temporal
variation of traffic on the delay is analyzed. Our proposed analytical
framework provides a useful guideline for the system design and deployment of
5G wireless systems where the delay requirement becomes the key concern.

Our results reveal that the delay performance of round-robin scheduling
outperforms FIFO scheduling for heavy traffic, and it is reversed for light
traffic. Moreover, it shows that the offloading policy based on cell range
expansion (CRE) greatly reduces the macrocell traffic while bringing a small
amount of growth for the picocell traffic.

The remaining part of the paper is organized as follows. Section II describes
the spatial distribution model, the arrival process, and the scheduling
policies. Sections III and IV evaluate the statistic of traffic, success
probability, and mean delay. Section V numerically analyzes the effect of the
spatial-temporal traffic on the statistical distribution of mean delay and the
delay outage. Finally, Section VI concludes the paper.

##  II System Model

We consider the downlink of a multi-tier heterogeneous cellular network with
$K$ tiers of BSs. The locations of the $k$th tier ($k=1,...,K$) BSs are
modeled as a homogeneous PPP $\Phi_{k}$ with intensity $\lambda_{k}$ BSs per
km2, and $\Phi_{1},\Phi_{2},...,\Phi_{K}$ are assumed to be independent. Let
$\Phi_{b}$ be the superposition of $\Phi_{1},\Phi_{2},...,\Phi_{K}$ as
follows:

$\Phi_{b}\triangleq\Phi_{1}\cup\Phi_{2}\cup...\cup\Phi_{K},$ (1)

which denotes the locations of all tiers of BSs in the network. The transmit
power of the BSs of the $k$th tier is fixed as $P_{k}$. We assume that the
time is slotted into discrete time slots.

The traffic model in the network consists of two parts: the spatial
distribution model of the users and the temporal arrival model of the packets
at each user. The mobility of the users is not modeled in the following, i.e.
the temporal variation of the locations of the users are not considered.
However, a variety of mobility models, such as random walk model, random
waypoint model, high mobility random walk model [34], could be applied to
extend this work. Therefore, our network model considered here is static since
the locations of the BSs and the users remain static during all time after
they are deployed [35, 36, 37]. We assume that the users are distributed as a
homogeneous PPP $\Phi_{u}=\\{x_{i}\\}$ with intensity $\lambda_{u}$ users per
m2. As for the temporal arrival of the downlink traffic at BSs, we assume that
the packets arrival process for each user $x_{i}\in\Phi_{u}$ is an independent
Bernoulli process of arrival rate $\xi_{i}$ (packets per time slot), i.e.,
$\xi_{i}$ is the probability of an arrival at user $x_{i}$ in any given time
slot. Without loss of generality, we assume that the size of each packet is
fixed and it requires exactly one time slot to transmit a packet. Each BS will
maintain an independent queue of infinite size for each user within the
coverage of associated BS to save the generated packets; thus the number of
queues at a BS equals to the number of users served by the associated BS. Due
to diverse latency requirements in future wireless network, we assume that the
mean delay requirement for user $x_{i}$ is $\beta_{i}$ (in number of time
slots), i.e., the mean delay of user $x_{i}$ should be less than $\beta_{i}$
time slots. With these notations, a user can be described by a triple
$(x_{i},\xi_{i},\beta_{i})$ with $x_{i}$ being the location, $\xi_{i}$ being
the arrival rate of packets, and $\beta_{i}$ being the mean delay requirement.
In the following, we assume that $\\{\xi_{i}\\}$ and $\\{\beta_{i}\\}$ are
independent identically distributed (i.i.d.) uniform random variables within
$[\xi_{\min},\xi_{\max}]$ and $[\beta_{\min},\beta_{\max}]$, respectively.
111Note that our analysis can be extended to the case of general probability
distributions for $\xi_{i}$ and $\beta_{i}$. Therefore, the traffic in the
network can be modeled by a marked Poisson process $\widetilde{\Phi}_{u}$
defined as follows:

$\widetilde{\Phi}_{u}\triangleq\\{(x_{i},\xi_{i},\beta_{i})\\}.$ (2)

The propagation loss is modeled by two parts, the path loss and the fading. A
deterministic path loss function $l(r)=Ar^{-\alpha}$ is used to model the path
loss, where $A>0$ is the reference path loss and $\alpha>2$ is the path loss
exponent. The fading is assumed to be Rayleigh block fading with unit mean,
i.e., the power fading coefficients in different time slots are i.i.d. and are
constant during one time slot. We consider the interference-limited regime and
ignore the thermal noise. If the signal-to-interference ratio (SIR) at a user
is larger than a certain threshold $\theta$, a packet will be successfully
decoded. Otherwise, if the acceptance of a packet fails, the packet will be
added into the head of the queue and wait to be rescheduled again. This model
is based on the Shannon’s theorem declaring that it is possible to communicate
digital information nearly error-free up to certain rate determined by the
SIR. We summarized several crucial system parameters in Table I.

TABLE I: System parameters Symbol | Description | Symbol | Description
---|---|---|---
$K$ | Number of tiers | $\Phi_{k}$ | Locations of $k$th tier BSs
$\lambda_{u}$ | Density of users | $A$ | Reference path loss
$\alpha$ | Path loss exponent | $\beta_{i}$ | Delay requirement for $x_{i}$
$\theta$ | SIR threshold | $\Phi_{u}$ | Locations of the users
$\xi_{i}$ | Arrival rate for $x_{i}$ | $P_{k}$ | Power of $k$th tier BSs

The random arrival of traffic may greatly affect the performance of the
network. In order to improve the overall performance with random arrival of
traffic, we consider several mechanisms to manage the traffic. We first
consider the CRE in which a bias factor for each tier of BSs is determined for
offloading [38]. By setting different bias factors for different tiers of BSs,
the coverage region of the small cells can be extended to serve more users.
Meanwhile, the number of users served by the macro BSs can then be reduced.
Another mechanism is to improve the SIR at the users by mitigating the
interference through randomly muting the transmission of the BSs in each time
slot. In practical wireless network, in the muted time slots, only control
channels and cell-specific reference signals are transmitted with reduced
power, and no user data is transmitted. During these time slots, the
interference can be greatly reduced. The last mechanism is to introduce the
scheduling of users in each cell, i.e., the BS in each cell selects an
appropriate user to serve. Several scheduling mechanisms have been considered,
such as the random scheduling in which each user is selected to be served
randomly with equal probability, the FIFO scheduling in which the packets are
served in the manner of first come first serve, and the round-robin scheduling
in which the users are scheduled one by one.

As for the user association strategy, we assume that the CRE is employed,
where the association is based on the maximum average biased received power.
Let $B_{k}$ be the association bias for the $k$th tier of BSs. Thus, a user
located at $x$ will associate the BS $X(x)$ denoted by

$X(x)=\mathop{\arg\max}_{k\in\\{1,2,...,K\\},y\in\Phi_{k}}B_{k}P_{k}|y-x|^{-\alpha}.$
(3)

By setting $B_{k}=1,\forall k$, the association strategy is exactly based on
the maximum received power. For the BSs from $k$th tier with small transmit
power $P_{k}$, the association bias $B_{k}$ is set to be larger so that users
can be offloaded from the overload macro cells to the light loaded small
cells, and the overall interference in the network can also be reduced. With
these settings, the spatial tessellation of cells construes a weighted Voronoi
tessellation. Mathematically, the association region of a BS from the $k$th
tier located at $X_{k}$ is given by

$\mathcal{C}(X_{k})=\bigg{\\{}y\in\mathbb{R}^{2}:|y-X_{k}|\leq\bigg{(}\frac{B_{k}P_{k}}{B_{i}P_{i}}\bigg{)}^{1/\alpha}|y-z|,\\\
\forall i\in\\{1,2,...,K\\},\forall z\in\Phi_{i}\bigg{\\}}.$ (4)

As for the random muting, we assume that the blank time slots appear randomly
at each BS with probability $1-p\ (0\leq p\leq 1)$ and independently among
different BSs. With these assumptions, in each time slot, each BS will
suppress its transmission with probability $1-p$, thus postponing its own
transmission but reducing its interference to the network.

Since there are multiple users served by each BS and only one user in a cell
can be scheduled for transmission in each time slot, we consider three
scheduling strategies as follows:

####  II-1 Random Scheduling

In random scheduling, each active BS will randomly choose one user within the
coverage region of that BS to serve in each time slot. Since there are
multiple queues at each BS corresponding to multiple users served by that BS,
each queue will be scheduled with the same probability in each time slot. Due
to the retransmission mechanism, if a packet fails for transmission in the
scheduled time slot, the packet will be added into the head of the queue of
the corresponding user and wait to be rescheduled again.

####  II-2 FIFO Scheduling

In FIFO scheduling, the packets arrived at each BS are served by the manner of
FIFO, i.e., a packet arrived first will be scheduled first. The result of FIFO
scheduling only relies on the time when the packets arrive at a BS and is
irrelevant to the particular user a packet belonging to. Therefore, all queues
at a BS can be considered as a large queue, a packet arrived first will be
served first.

####  II-3 Round-robin Scheduling

In round-robin scheduling, the users served by each BS are scheduled one by
one. For example, if there are $N$ users served by a BS, $N$ time slots will
form a complete cycle in that cell, and the scheduling of each user will
occupy one of the $N$ time slots. Similarly, retransmission mechanism is
introduced for the failed packets. Note that each BS may suppress its
transmission in a time slot with probability $1-p$ due to the random muting,
the transmission of the scheduled user in that time slot will be suppressed.

Though several simple assumptions are used to make the analysis feasible, the
analytical framework proposed in this work could be easily extended to model
the particular scenarios and detailed technologies in wireless networks.

##  III Traffic Statistic

In this section, we evaluate the traffic statistic to characterize the spatio-
temporal traffic, which is characterized by the spatial distribution, the
temporal arrival rate, and the delay requirement for the users. In order to
characterize the traffic, we first introduce the following lemma.

######  Lemma 1.

The probability that the typical user associates to the BSs of the $k$th tier
is given by

$\mathcal{P}_{k}=\frac{\lambda_{k}(P_{k}B_{k})^{2/\alpha}}{\sum_{i=1}^{K}\lambda_{i}(P_{i}B_{i})^{2/\alpha}}.$
(5)

###### Proof.

The proof is similar to Lemma 1 in [16], and we present a simplified version
here for completeness. Let $Z_{i}$ be the distance between the typical user at
the origin and the nearest BS in the $i$th tier of BSs. The pdf of $Z_{i}$,
given by

$f_{Z_{i}}(z)=2\pi\lambda_{i}z\exp(-\pi\lambda_{i}z^{2}),$ (6)

can be obtained by the void probability of the PPP in a ball. The probability
that the typical user associates to the BSs of the $k$th tier is

$\displaystyle\mathcal{P}_{k}$ $\displaystyle=$
$\displaystyle\mathbb{P}\left(\bigcap_{i=1,i\neq
k}^{K}\\{P_{k}B_{k}Z_{k}^{-\alpha}>P_{i}B_{i}Z_{i}^{-\alpha}\\}\right)$ (7)
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}$
$\displaystyle\prod_{i=1,i\neq
k}^{K}\mathbb{P}(P_{k}B_{k}Z_{k}^{-\alpha}>P_{i}B_{i}Z_{i}^{-\alpha}),$

where $(a)$ follows from the independence of $\\{\Phi_{k}\\}$. Plugging in the
pdf of $Z_{i}$, we obtain (5). ∎

With the association probability given by Lemma 1, we obtain the following
lemma.

######  Lemma 2.

The pdf of the coverage area $S_{k}$ of a BS of the $k$th tier is approximated
as

$f_{S_{k}}(x)\simeq\frac{343}{15}\sqrt{\frac{3.5}{\pi}}\left(\frac{x\lambda_{k}}{\mathcal{P}_{k}}\right)^{2.5}\exp\left(-\frac{3.5x\lambda_{k}}{\mathcal{P}_{k}}\right)\frac{\lambda_{k}}{\mathcal{P}_{k}}.$
(8)

###### Proof.

The pdf of the area $S$ of a Voronoi cell for a PPP with intensity $\lambda$
is [10, 11]

$f_{S}(x)\simeq\frac{343}{15}\sqrt{\frac{3.5}{\pi}}(x\lambda)^{2.5}\exp\left(-3.5x\lambda\right)\lambda.$
(9)

Due to the ergodicity of the PPP, since $\mathcal{P}_{k}$ is the probability
that a user associates to the BSs of the $k$th tier, the average fraction of
total area covered by the BSs of the $k$th tier is also $\mathcal{P}_{k}$.
Therefore, the average coverage area of a BS of the $k$th tier is
${\mathcal{P}_{k}}/{\lambda_{k}}$. By replacing $\lambda$ with
${\lambda_{k}}/{\mathcal{P}_{k}}$ in (9), we get the approximated result (8).
∎

The following lemma gives the statistics for different kinds of users in each
cell.

######  Lemma 3.

Let $N_{k,\xi,\beta}$ be the number of users served by a BS of the $k$th tier
with arrival rates less than $\xi\in[\xi_{\rm min},\xi_{\rm max}]$ and with
delay requirements less than $\beta\in[\beta_{\rm min},\beta_{\rm max}]$. The
probability generating functions (PGFs) of $N_{k,\xi,\beta}$ are given by

$G_{N_{k,\xi,\beta}}(z)\simeq\left(1+C_{0}-C_{0}z\right)^{-\frac{7}{2}}.$ (10)

The probability mass functions (PMF) of $N_{k,\xi,\beta}$, denoted by
$\mathbb{P}(N_{k,\xi,\beta}=n)=\frac{1}{n!}G_{N_{k,\xi,\beta}}^{(n)}(0)$, is
given by

$\displaystyle\mathbb{P}(N_{k,\xi,\beta}=n)=\frac{(2n+5)!!}{15\cdot
n!}\Big{(}\frac{C_{0}}{2}\Big{)}^{n}(C_{0}+1)^{-n-\frac{7}{2}}.$ (11)

where $n!!$ is the double factorial and

$\displaystyle C_{0}=\frac{(\beta-\beta_{\rm min})(\xi-\xi_{\rm
min})}{(\beta_{\rm max}-\beta_{\rm min})(\xi_{\rm max}-\xi_{\rm
min})}\frac{\mathcal{P}_{k}}{\lambda_{k}}\frac{2}{7}\lambda_{u}.$ (12)

###### Proof.

Since the spatial distribution of users construes a PPP with intensity
$\lambda_{u}$, given the area $S_{k}$ of a cell, the number of users within
the cell with arrival rate less than $\xi$ and with delay requirement less
than $\beta$ is a Poisson random variable with mean $\frac{(\beta-\beta_{\rm
min})(\xi-\xi_{\rm min})\lambda_{u}S_{k}}{(\beta_{\rm max}-\beta_{\rm
min})(\xi_{\rm max}-\xi_{\rm min})}$. Thus, the PGF of $N_{k,\xi,\beta}$,
$G_{N_{k,\xi,\beta}}(z)=\mathbb{E}\left[z^{N_{k,\xi,\beta}}\right]$, is

$\displaystyle\\!\\!\\!\\!G_{N_{k,\xi,\beta}}(z)$ (13)
$\displaystyle\\!\\!=\\!\\!$
$\displaystyle\\!\\!\\!\\!\mathbb{E}_{S_{k}}\left[\exp\left(\frac{(\beta-\beta_{\rm
min})(\xi-\xi_{\rm min})\lambda_{u}S_{k}(z-1)}{(\beta_{\rm max}-\beta_{\rm
min})(\xi_{\rm max}-\xi_{\rm min})}\right)\right]$
$\displaystyle\\!\\!\simeq\\!\\!$
$\displaystyle\\!\\!\\!\\!\int_{0}^{\infty}\frac{343}{15}\sqrt{\frac{3.5}{\pi}}\left(\frac{\lambda_{k}}{\mathcal{P}_{k}}\right)^{3.5}x^{2.5}$
$\displaystyle\\!\\!\exp\left(-\frac{3.5\lambda_{k}}{\mathcal{P}_{k}}x+\frac{(\beta-\beta_{\rm
min})(\xi-\xi_{\rm min})\lambda_{u}(z-1)x}{(\beta_{\rm max}-\beta_{\rm
min})(\xi_{\rm max}-\xi_{\rm min})}\right)\mathrm{d}x$
$\displaystyle\\!\\!=\\!\\!$
$\displaystyle\\!\\!\\!\\!\left(1-\frac{(\beta-\beta_{\rm min})(\xi-\xi_{\rm
min})}{(\beta_{\rm max}-\beta_{\rm min})(\xi_{\rm max}-\xi_{\rm
min})}\frac{\mathcal{P}_{k}}{\lambda_{k}}\frac{2}{7}\lambda_{u}(z-1)\right)^{-3.5}.\quad$

The $n$th derivative of $G_{N_{k,\xi,\beta}}(z)$ is

$\displaystyle
G_{N_{k,\xi,\beta}}^{(n)}(z)=\frac{C_{0}^{n}}{2^{n}}\frac{(2n+5)!!}{15}(-C_{0}z+C_{0}+1)^{-n-\frac{7}{2}},$
(14)

where $C_{0}$ is given by (12) and $n!!$ is the double factorial. Therefore,
we get the PMF as follows

$\displaystyle\mathbb{P}(N_{k,\xi,\beta}=n)\\!\\!$
$\displaystyle\\!\\!=\\!\\!$
$\displaystyle\\!\\!\frac{1}{n!}G_{N_{k,\xi,\beta}}^{(n)}(0)$ (15)
$\displaystyle\\!\\!=\\!\\!$ $\displaystyle\\!\\!\frac{(2n+5)!!}{15\cdot
n!}\Big{(}\frac{C_{0}}{2}\Big{)}^{n}(C_{0}+1)^{-n-\frac{7}{2}}.\quad$

∎

Figure 3: PMFs of the number of users associating to different tiers of BSs in
the two tiered heterogeneous networks formed by macrocells and picocells. The
transmit powers, the densities and the bias factors for macro BSs and micro
BSs are set as $P_{1}=39$dBm and $P_{2}=24$dBm, $\lambda_{1}=0.00001$m-2 and
$\lambda_{2}=0.00005$m-2, $B_{1}=1$ and $B_{2}=1$ or $10$, respectively. Other
parameters are set as $\alpha=2.5$ and $\lambda_{u}=0.0001$m-2.

Figure 3 plots the PMFs of the number of users associating to different tiers
of BSs in the two tiered heterogeneous networks formed by macrocells and
picocells. When the bias factors for macrocells and picocells are the same
$(B_{1}=B_{2}=1)$, i.e., no bias exists, the macrocells will serve more users
than the picocells because they provide larger coverage. Figure 3 also
indicates that in the case where some users are offloaded from the macrocells
to the picocells $(B_{1}=1,B_{2}=10)$, the number of users served by each
macrocell is greatly reduced while that served by each picocell does not
increase much, implying that the offloading policy is potential for better
utilization of the idle resources of the small cells.

######  Remark 1.

From Lemma 3, we get the mean number of users served by a BS of the $k$th tier
with arrival rate less than $\xi$ and with delay requirement less than $\beta$
as

$\displaystyle\overline{N}_{k,\xi,\beta}\triangleq\mathbb{E}\left[{N_{k,\xi,\beta}}\right]=\frac{(\beta-\beta_{\rm
min})(\xi-\xi_{\rm min})\mathcal{P}_{k}}{(\beta_{\rm max}-\beta_{\rm
min})(\xi_{\rm max}-\xi_{\rm min})}\frac{\lambda_{u}}{\lambda_{k}}.$ (16)

By setting $\xi=\xi_{\rm max}$ and $\beta=\beta_{\rm max}$, we get the total
number of users served by a BS of the $k$th tier as $N_{k}=N_{k,\xi_{\rm
max},\beta_{\rm max}}$, whose PGF, PMF and mean value are

$\displaystyle
G_{N_{k}}(z)\simeq\left(1-\frac{\mathcal{P}_{k}}{\lambda_{k}}\frac{2}{7}\lambda_{u}(z-1)\right)^{-3.5},$
(17) $\displaystyle\mathbb{P}(N_{k}=n)=\frac{1}{n!}G_{N_{k}}^{(n)}(0),$ (18)
$\displaystyle\overline{N}_{k}\triangleq\mathbb{E}\left[{N_{k}}\right]=\frac{\mathcal{P}_{k}}{\lambda_{k}}\lambda_{u}.$
(19)

Letting $\xi_{k,\rm total}$ be the total arrival rate of the packets at a BS
of the $k$th tier, we get

$\displaystyle\overline{\xi}_{k,\rm total}\triangleq\mathbb{E}\left[\xi_{k,\rm
total}\right]=\frac{\xi_{\rm max}+\xi_{\rm
min}}{2}\frac{\mathcal{P}_{k}}{\lambda_{k}}\lambda_{u}.$ (20)

Figure 4: Total arrival rates at different BSs in the two tiered heterogeneous
networks formed by macrocells and picocells. The transmit powers and the
densities for macro BSs and micro BSs are set as $P_{1}=39$dBm and
$P_{2}=24$dBm, $\lambda_{1}=0.00001$m-2 and $\lambda_{2}=0.00005$m-2,
respectively. Other parameters are set as $B_{1}=1$, $\lambda_{u}=0.0001$m-2,
$\xi_{\rm min}=0.2$ and $\xi_{\rm max}=0.6$.

Figure 4 plots the total arrival rate at different BSs in the two tiered
heterogeneous networks formed by the macrocells and the picocells. It is
observed that when fixing the bias factor for macrocells and increasing the
bias factor for picocells, the total arrival rate at each macrocell decreases
dramatically while the total arrival rate at each picocell increases slowly,
indicating that the traffic for macrocells is effectively offloaded with a
little cost of increasing the traffic for each picocell. Meanwhile, Figure 4
also reveals that the propagation environment may greatly affect the
offloading of the traffic. For example, the coverage region of the macrocells
may shrink when increasing the path loss exponents $\alpha$, resulting in less
traffic for the macrocells.

##  IV Success Probability and Delay

In the following, we analyze the statistics of success probability and delay
in the heterogeneous networks. The success probability is the probability that
a scheduled packet can be successfully delivered. The delay consists of two
parts, one is the queueing delay, which measures the delay between the time
when a packet arrives at the queue and the time when it starts to be served;
the other is the service time, which is the time to transmit the given packet.
We assume that the delay mentioned here is evaluated in terms of number of
time slots. Since the considered network is static, i.e., the locations of the
BSs are deployed at first and keep unchanged during the following time, the
success probabilities for different links are different, resulting in
different mean delays for different queues. Thus, a suitable metric to
characterize the delay performance of the overall wireless network is the
statistical cumulative distribution function (cdf) of the mean delay of all
users in the network. From the ergodicity of the PPP, the ensemble averages
obtained by averaging over the point process equal the spatial averages
obtained by averaging over an arbitrary realization of the PPP over a large
region. Therefore, in order to obtain the statistical cdf of the mean delay
obtained from the spatial statistics of the mean delay samples of a large
number of transmissions in the network, we could analytically evaluate the cdf
of the mean delay at the typical transmission for different realizations of
the PPP.

Without loss of generality, we consider a typical user located at the origin,
denoted by $(x_{0},\xi_{0},\beta_{0})$ with $x_{0}=o$, and a typical BS
$y_{0}$ associated with the typical user. For each realization of the spatial
locations of BSs $\Phi_{b}$, we obtain a mean delay for the typical user. By
traversing all the realizations of $\Phi_{b}$, we obtain a statistical
distribution of the mean delay (for example, the cdf) for the typical user at
the origin. Thus, the cdf of the mean delay for the typical user equals the
statistical cdf of the mean delays of all users in the network. To avoid
confusion, we denote the mean delay of the typical user at the origin
conditioning on the realization of $\Phi_{b}$ as the conditional mean delay,
denoted by $\mathbf{D}_{\Phi_{b}}$, which it is a random variable uniquely
defined by $\Phi_{b}$ [39, Def. 1]. In the following discussions, we derive
the cdf of the conditional mean delay $\mathbf{D}_{\Phi_{b}}$, which is
suitable to characterize the delay performance of the large network since it
also gives the statistical cdf of the mean delays of all users in the network.

The typical user will associate the BS from the $k$th tier with probability
$\mathcal{P}_{k}$. Let $Z_{i}$ be the distance between the typical user at the
origin and the nearest BS in the $i$th tier of BSs. Let $y_{0}\in\Phi_{b}$ be
the serving BS; then $Z_{k}=|y_{0}|$ holds when a user associates to BS from
the $k$th tier. The following lemma gives the pdf of the link distance
$|y_{0}|$ conditioned on the user associating to BS from the $k$th tier.

######  Lemma 4.

Conditioned on the typical user associating to BS $y_{0}$ from the $k$th tier,
the pdf of the distance $Z_{k}=|y_{0}|$ between the typical user at the origin
and its serving BS $y_{0}$ is

$f_{Z_{k}\mid y_{0}\in\Phi_{k}}(r)=\frac{2\pi
r\lambda_{k}}{\mathcal{P}_{k}}\exp\left(-\frac{\pi
r^{2}\lambda_{k}}{\mathcal{P}_{k}}\right).$ (21)

###### Proof.

Conditioned on the typical user associating to BS from the $k$th tier, the cdf
of the distance between the typical user and its serving BS $y_{0}$ is

$\displaystyle\\!\\!\mathbb{P}\left(|y_{0}|\leq r\mid y_{0}\in\Phi_{k}\right)$
(22) $\displaystyle\\!\\!=\\!\\!$
$\displaystyle\\!\\!\frac{\mathbb{P}\left(|y_{0}|\leq
r,y_{0}\in\Phi_{k}\right)}{\mathbb{P}\left(y_{0}\in\Phi_{k}\right)}$
$\displaystyle\\!\\!=\\!\\!$
$\displaystyle\\!\\!\frac{1}{\mathcal{P}_{k}}{\mathbb{P}\bigg{(}\\{Z_{k}\leq
r\\}\bigcap\bigg{\\{}\bigcap_{i=1,i\neq
k}^{K}\\{P_{k}B_{k}Z_{k}^{-\alpha}>P_{i}B_{i}Z_{i}^{-\alpha}\\}\bigg{\\}}\bigg{)}}$
$\displaystyle\\!\\!=\\!\\!$
$\displaystyle\\!\\!\frac{1}{\mathcal{P}_{k}}\int_{0}^{r}\prod_{i=1,i\neq
k}^{K}\mathbb{P}(P_{k}B_{k}z^{-\alpha}>P_{i}B_{i}Z_{i}^{-\alpha})f_{Z_{k}}(z)\mathrm{d}z$
$\displaystyle\\!\\!=\\!\\!$ $\displaystyle\\!\\!1-\exp\left(-\pi
r^{2}\sum_{i=1}^{K}\lambda_{i}\left(\frac{P_{i}B_{i}}{P_{k}B_{k}}\right)^{2/\alpha}\right),$

where the last equation follows by plugging in the pdf of $Z_{i}$ given by
(6). By differentiating with respect to $r$, we get the result in the lemma. ∎

######  Remark 2.

The form of the conditional pdf given by (21) is very similar to the contact
distance distribution of the PPP given by (6). The only difference lies in
that the intensity of the PPP $\lambda_{i}$ is replaced by
$\frac{\lambda_{k}}{\mathcal{P}_{k}}$. Intuitively, it can be interpreted as
that, since $\mathcal{P}_{k}$ is the average fraction of total area covered by
BSs from the $k$th tier, the spatial distribution of the BSs from the $k$th
tier could be considered as a PPP of intensity
$\frac{\lambda_{k}}{\mathcal{P}_{k}}$.

In the following, we first condition on the realization of
$\Phi_{b}=\bigcup_{i=1}^{K}\Phi_{i}$ and derive the conditional mean delay
$\mathbf{D}_{\Phi_{b}}$. The statuses of BSs in the heterogeneous network
switch between idle and busy according to the random muting, the statues of
the queues, and the scheduling results at the BSs. In each time slot, a BS
will suppress its transmission and not cause interference if the BS is muted
or the queue of the scheduled user of the BS is empty. Let
$\zeta_{y,t}\in\\{0,1\\}$ be the indicator showing whether the BS located at
$y\in\Phi_{b}$ is idle $(\zeta_{y,t}=0)$ or busy $(\zeta_{y,t}=1)$ in the time
slot $t$. Then, if the typical user located at the origin associates to a BS
$y_{0}$ from the $k$th tier, the SIR at the user in the time slot $t$ is

$\mathrm{SIR}_{t}=\frac{P_{k}h_{y_{0}}|y_{0}|^{-\alpha}}{\sum_{i=1}^{K}\sum_{y\in\Phi_{i}\setminus
B(o,z_{ik})}\zeta_{y,t}P_{i}h_{y}|y|^{-\alpha}},$ (23)

where $h_{y}$ is the power fading coefficient between the typical user and the
BS located at $y$ with $h_{y}\sim\mathrm{Exp}(1)$, and $B(o,z_{ik})$ is a ball
centered at the origin with radius
$z_{ik}=\big{(}\frac{P_{i}B_{i}}{P_{k}B_{k}}\big{)}^{1/\alpha}|y_{0}|$.

The difficulty of the delay analysis lies in the fact that the SIR relies on
the statuses of the queues at all BSs, and on the other hand the SIR at the
users also affects the statuses of the queues. Decoupling the SIR analysis and
the statuses of the queues at all BSs is difficult; thus, we propose to bound
the SIR as follows:

  * •

Lower bound of SIR: Consider a dominant system in which the typical user and
its serving BS behave exactly the same as that in the original system;
however, for other BSs in the dominant system, we assume that when the queues
of the scheduled users at those BSs become empty, those BSs continue to
transmit “dummy” packets, thus continuing to cause interference to other users
no matter whether the scheduled queues are empty or not. The queue size at
each BS in the dominant system will never be smaller than that in the original
system, resulting in smaller SIR and larger delay. Therefore, the obtained SIR
under these assumptions will be a lower bound for the SIR in the original
system.

  * •

Upper bound of SIR: Consider a modified system as follows: the typical user
and its serving BS behave exactly the same as that in the original system;
however, if an arrived packet at an interfering BS is not scheduled or failed
for the transmission in current time slot, it will be dropped rather than
being retransmitted. In this way, since the interference in the modified
system is always smaller than that in the original system and the packets will
not accumulate at the interfering BSs, the obtained SIR will be an upper bound
for the SIR in the original system.

###  IV-A Statistic of Success Probability

By using the aforementioned bounding approaches, $\\{\zeta_{y,t}\\}$ become
independent random variables and are not related to the time slot index $t$.
In these cases, the SIRs at the typical user in different time slots, denoted
by $\\{\mathrm{SIR}_{t}\\}$, are independent random variables and also not
related to the time slot index $t$. For simplicity and without ambiguity, we
omit the subscript $t$ and use $\zeta_{y}$ and $\mathrm{SIR}$ when deriving
these bounds. Therefore, the success probability conditioned on $\Phi_{b}$
when the typical user is served by a BS $y_{0}$ from the $k$th tier with link
distance $Z_{k}=|y_{0}|$ is given by

$\mathbb{P}(\mathrm{SIR}>\theta\mid\Phi_{b},y_{0}\in\Phi_{k},Z_{k}=|y_{0}|)=\\\
\mathbb{P}\bigg{(}\frac{P_{k}h_{y_{0}}|y_{0}|^{-\alpha}}{\sum_{i=1}^{K}\sum_{y\in\Phi_{i}\setminus
B(o,z_{ik})}\zeta_{y}P_{i}h_{y}|y|^{-\alpha}}\\\
>\theta\mid\Phi_{b},y_{0}\in\Phi_{k},Z_{k}=|y_{0}|\bigg{)}.$ (24)

The probability of $\zeta_{y}=1$ relies on the bounding approaches and the
scheduling strategies. We first assume

$\mathbb{P}(\zeta_{y}=1)=q,$ (25)

and analyze the success probability; then we determine the values of $q$ for
different bounding approaches and scheduling strategies.

######  Lemma 5.

If each interfering BS is active independently with probability $q$, i.e.,
$\mathbb{P}(\zeta_{y}=1)=q$, the cdf of success probability for the typical
user conditioned on $\Phi_{b}$ when it associates to BS from $k$th tier,
denoted by $\mathbb{P}(\mathrm{SIR}>\theta\mid\Phi_{b},y_{0}\in\Phi_{k})$, is

$\mathbb{P}(\mathbb{P}(\mathrm{SIR}>\theta\mid\Phi_{b},y_{0}\in\Phi_{k})\leq
u)=\\\
\frac{1}{2}+\frac{1}{\pi{\mathcal{P}_{k}}}\int_{0}^{\infty}\frac{1}{\omega}\mathrm{Im}\big{\\{}u^{-j\omega}\kappa^{-1}(\omega,k,q)\big{\\}}\mathrm{d}\omega.$
(26)

where $\kappa(\omega,k,q)$ is defined as

$\kappa(\omega,k,q)=-2\sum_{i=1}^{K}\frac{\lambda_{i}}{\lambda_{k}}\Big{(}\frac{P_{i}B_{i}}{P_{k}B_{k}}\Big{)}^{\delta}\\\
\times\int_{0}^{1}\Big{(}1-\Big{(}\frac{q}{1+\theta
y^{\alpha}\frac{B_{k}}{B_{i}}}+1-q\Big{)}^{j\omega}\Big{)}y^{-3}\mathrm{d}y-\frac{1}{\mathcal{P}_{k}}\\\
=\delta\sum_{i=1}^{K}\frac{\lambda_{i}}{\lambda_{k}}\sum_{n=1}^{\infty}\binom{j\omega}{n}\Big{(}\frac{B_{i}}{B_{k}}\Big{)}^{\delta-n}\Big{(}\frac{P_{i}}{P_{k}}\Big{)}^{\delta}\\\
\frac{(-q\theta)^{n}}{n-\delta}{{}_{2}F_{1}\Big{(}n,n-\delta;n-\delta+1;-\theta\frac{B_{k}}{B_{i}}\Big{)}}-\frac{1}{\mathcal{P}_{k}}.$
(27)

###### Proof.

See Appendix A. ∎

Figure 5: Cdf of success probabilities for different tiers of BSs in the two
tiered heterogeneous networks formed by macrocells and picocells. The transmit
powers and the densities for macro BSs and micro BSs are set as $P_{1}=39$dBm
and $P_{2}=24$dBm, $\lambda_{1}=0.00001$m-2 and $\lambda_{2}=0.00005$m-2,
respectively. The bias factor for macrocell is $B_{1}=1$.

Figure 5 plots the cdf of success probabilities for different tiers of BSs in
the two tiered heterogeneous networks formed by macrocells and picocells. If
there is no bias $(B_{1}=B_{2}=1)$, the cdfs of the success probabilities for
macrocell users and picocell users coincide, implying that the statistical
success probability of users associating to different tiers of BSs is the same
for the maximum average received power association. The cdfs given by Figure 5
shows that when increasing the bias factor for picocells $(B_{1}=1,B_{2}=4)$,
the proportion of picocell users with small success probability increases
since the offloaded users are distributed at the edge of the picocells and may
experience poor SIR performance. For the case of large path loss exponent, the
electromagnetic signal attenuates fast, thus suppressing the inter-cell
interference and increasing the success probability for both macrocell and
picocell users. This observation indicates that offloading is more effective
when the signal attenuates fast.

Define the success probability of the typical user conditioned on $\Phi_{b}$
as

$\mathbf{P}_{\Phi_{b}}\triangleq\mathbb{P}(\mathrm{SIR}>\theta\mid\Phi_{b}).$
(28)

Then, $\mathbf{P}_{\Phi_{b}}$ is a random variable uniquely determined by the
realization of $\Phi_{b}$. By traversing all the realizations of $\Phi_{b}$,
we get the cdf of $\mathbf{P}_{\Phi_{b}}$. Due to the ergodicity of the PPP,
the cdf of $\mathbf{P}_{\Phi_{b}}$ also gives the statistical cdf of the
success probabilities of all users within a large region. Therefore, we get
the following theorem.

######  Lemma 6.

If each interfering BS is active independently with probability $q$, i.e.,
$\mathbb{P}(\zeta_{y}=1)=q$, the statistical cdf of success probabilities of
all users in the network equals the cdf of the success probability of the
typical user conditioned on $\Phi_{b}$, which is

$\mathbb{P}\left(\mathbf{P}_{\Phi_{b}}\leq u\right)=F(u,q)\\\
\triangleq\frac{1}{2}+\frac{1}{\pi}\sum_{k=1}^{K}\int_{0}^{\infty}\frac{1}{\omega}\mathrm{Im}\big{\\{}u^{-j\omega}\kappa^{-1}(\omega,k,q)\big{\\}}\mathrm{d}\omega.$
(29)

###### Proof.

Combining Lemma 5 and using the total probability formula

$\mathbb{P}\left(\mathbf{P}_{\Phi_{b}}\leq
u\right)=\sum_{k=1}^{K}\mathcal{P}_{k}\mathbb{P}(\mathbb{P}(\mathrm{SIR}>\theta\mid\Phi_{b},y_{0}\in\Phi_{k})\leq
u),$ (30)

we obtain the theorem. ∎

######  Remark 3.

Particularly, in single tier cellular network, i.e., $K=1$, the statistical
cdf of success probabilities of all users in the network is

$\mathbb{P}\left(\mathbf{P}_{\Phi_{b}}\leq
u\right)=\frac{1}{2}+\frac{1}{\pi}\int_{0}^{\infty}\frac{1}{\omega}\mathrm{Im}\bigg{\\{}\\\
\frac{u^{-j\omega}}{\delta\sum_{n=1}^{\infty}\binom{j\omega}{n}\frac{(-q\theta)^{n}}{n-\delta}{{}_{2}F_{1}(n,n-\delta;n-\delta+1;-\theta)}-1}\bigg{\\}}\mathrm{d}\omega.$
(31)

The cdf of the success probability given by Lemma 6,
$\mathbb{P}\left(\mathbf{P}_{\Phi_{b}}\leq u\right)$, equals the proportion of
number of users whose success probabilities are less than $u$ in the network.
Lemma 6 reveals that, in the $K$-tier heterogeneous network, the cdf of the
success probability $\mathbf{P}_{\Phi_{b}}$ only relies on the ratios of the
densities of BSs, the bias factors and the transmit powers among different
tiers. For the single tier network ($K=1$), the cdf of the success probability
is not related to the densities of BSs, the bias factors or the transmit
powers of BSs. These observations indicate that the statistical distribution
of the success probabilities of all users in the single-tiered interference-
limited heterogeneous network with much randomness in the deployment is only
slightly correlated to the exact value of a number of system parameters, such
as the densities of BSs or the transmit powers of BSs. This result is
coincident with the conclusion for the coverage probability in the networks
modeled by the PPPs [40].

###  IV-B Statistic of Delay

In the following, we discuss the statistics of the delay for different
scheduling policies.

####  IV-B1 Random Scheduling

In the random scheduling, each active BS will randomly choose one user from
all users within the coverage region of that BS to serve in each time slot.
Let $N$ be the number of users served by the BS. Considering the random muting
mechanism that each BS is idle with probability $1-p$ in each time slot, the
average service rate (number of packets transmitted successfully per time
slot) of the typical user conditioned on $\Phi_{b}$ is

$\mu=\frac{p}{N}\mathbb{P}(\mathrm{SIR}>\theta\mid\Phi_{b})=\frac{p}{N}\mathbf{P}_{\Phi_{b}}.$
(32)

The probability for a packet at the typical user being scheduled and
successfully transmitted in a time slot is $\mu$ given by (32). Since the
transmissions of the typical user in different time slots are independent in
the random scheduling, the probability for successfully transmitting a packet
in any time slot is also $\mu$. Therefore, the queueing system at the typical
transmitter is equivalent to a Geo/G/1 queue, or a discrete-time single server
retrial queue [41], [42]. In the equivalent Geo/G/1 queue, the time is slotted
and the packets arrive according to a Bernoulli process with intensity
$\xi_{0}$ packets per time slot. The arrival process is also called geometric
arrival process since the probability that a packet arrives in a time slot is
$\xi_{0}$, and the number of time slots between two adjacent arrivals is a
geometric random variable. The success probability is $\mu$ and the service
times of packets are i.i.d. with geometric distribution. From [41], we get the
conditional mean delay $\mathbf{D}_{\Phi_{b}}$ in random scheduling as

$\displaystyle\mathbf{D}_{\Phi_{b}}=\left\\{\begin{array}[]{ll}\frac{1-\xi_{0}}{\mu-\xi_{0}}&\textrm{if
$\mu>\xi_{0}$}\\\ \infty&\textrm{if $\mu\leq\xi_{0}$}.\end{array}\right.$ (35)

Therefore, we obtain the following theorem.

######  Lemma 7.

In random scheduling, if each interfering BS is active independently with
probability $q$, i.e., $\mathbb{P}(\zeta_{y}=1)=q$, the statistical cdf of the
mean delay of all users in the network equals the cdf of mean delay of the
typical user conditioned on $\Phi_{b}$, which is

$\mathbb{P}\left(\mathbf{D}_{\Phi_{b}}\leq
T\right)=H_{1}(T,q)\triangleq\frac{1}{2}-\frac{1}{\pi}\sum_{k=1}^{K}\int_{0}^{\infty}\frac{1}{\omega}\mathrm{Im}\Big{\\{}\\\
\frac{{p}^{j\omega}}{\kappa(\omega,k,q)}\mathbb{E}_{N_{k},\xi_{0}}\Big{[}{N_{k}^{-j\omega}\Big{(}\frac{1}{T}+\frac{T-1}{T}\xi_{0}\Big{)}}^{-j\omega}\Big{]}\Big{\\}}\mathrm{d}\omega.$
(36)

###### Proof.

See Appendix B. ∎

Particularly, by the previous mentioned bounding approaches, we obtain the
following theorem which gives the bounds for the cdf of success probability
and mean delay in random scheduling.

######  Theorem 1.

In random scheduling, the statistical cdf of success probability and mean
delay of all users in the network are bounded by

$\displaystyle F(u,p)\leq\mathbb{P}\left(\mathbf{P}_{\Phi_{b}}\leq
u\right)\leq F(u,\frac{\xi_{\rm max}+\xi_{\rm min}}{2}p),$ (37) $\displaystyle
H_{1}(T,p)\leq\mathbb{P}\left(\mathbf{D}_{\Phi_{b}}\leq T\right)\leq
H_{1}(T,\frac{\xi_{\rm max}+\xi_{\rm min}}{2}p).$ (38)

###### Proof.

By considering the aforementioned dominant system ($q=p$), we obtain a lower
bound of SIR, which results in lower bounds for the success probability and
the cdf of the mean delay. By considering the modified system
($q=\frac{\xi_{\rm max}+\xi_{\rm min}}{2}p$), we obtain an upper bound of SIR,
which results in upper bounds for the success probability and the cdf of the
mean delay. ∎

####  IV-B2 FIFO Scheduling

In the FIFO scheduling, each active BS will schedule the earliest arriving
packet at that BS in each time slot, and all queues at a BS could be
considered as a single large queue. Notice that the delay of the typical user
equals the delay of the packets arriving at the large queue. The average
service rate of the large queue conditioned on $\Phi_{b}$ is

$\mu=p\mathbb{P}(\mathrm{SIR}>\theta\mid\Phi_{b})=p\mathbf{P}_{\Phi_{b}}.$
(39)

Generally, the probability that more than two packets arrive simultaneously at
the large queue is very small. Thus, the arrival process at the large queue
can be considered as Bernoulli arrival with arrival rate
$\sum_{i=0}^{N-1}\xi_{i}$, where $N$ is the number of users (including the
typical user at $x_{0}$) and $\xi_{i}$ is the arrival rate of the $i$th user.
The queueing process at the BS is equivalent to a Geo/G/1 queueing system.
Therefore, the conditional mean delay $\mathbf{D}_{\Phi_{b}}$ in FIFO
scheduling is

$\displaystyle\mathbf{D}_{\Phi_{b}}=\left\\{\begin{array}[]{ll}\frac{1-\sum_{i=0}^{N-1}\xi_{i}}{\mu-\sum_{i=0}^{N-1}\xi_{i}}&\textrm{if
$\mu>\sum_{i=0}^{N-1}\xi_{i}$}\\\ \infty&\textrm{if
$\mu\leq\sum_{i=0}^{N-1}\xi_{i}$}.\end{array}\right.$ (42)

Therefore, we obtain the following lemma and theorem.

######  Lemma 8.

In FIFO scheduling, if each interfering BS is active independently with
probability $q$, i.e., $\mathbb{P}(\zeta_{y}=1)=q$, the statistical cdf of the
mean delay of all users in the network equals the cdf of the mean delay of the
typical user conditioned on $\Phi_{b}$, which is

$\mathbb{P}\left(\mathbf{D}_{\Phi_{b}}\leq
T\right)=H_{2}(T,q)\triangleq\frac{1}{2}-\frac{1}{\pi}\sum_{k=1}^{K}\int_{0}^{\infty}\frac{1}{\omega}\mathrm{Im}\Big{\\{}\\\
\frac{{p}^{j\omega}}{\kappa(\omega,k,q)}\mathbb{E}_{N_{k},\\{\xi_{i}\\}}\Big{[}\Big{(}\frac{1}{T}+\frac{T-1}{T}\sum_{i=0}^{N_{k}-1}\xi_{i}\Big{)}^{-j\omega}\Big{]}\Big{\\}}\mathrm{d}\omega.$
(43)

###### Proof.

The proof is similar to that of Lemma 7. ∎

######  Theorem 2.

In FIFO scheduling, the statistical cdf of success probability and mean delay
of all users in the network are bounded by

$F(u,p)\leq\mathbb{P}\left(\mathbf{P}_{\Phi_{b}}\leq u\right)\\\ \leq
F\Big{(}u,\min\Big{\\{}1,\frac{p}{2}(\xi_{\rm max}+\xi_{\rm min})\min_{1\leq
k\leq K}\overline{N}_{k}\Big{\\}}\Big{)},$ (44)
$H_{2}(T,p)\leq\mathbb{P}\left(\mathbf{D}_{\Phi_{b}}\leq T\right)\leq\\\
H_{2}\Big{(}T,\min\Big{\\{}1,\frac{p}{2}(\xi_{\rm max}+\xi_{\rm
min})\min_{1\leq k\leq K}\overline{N}_{k}\Big{\\}}\Big{)}.$ (45)

###### Proof.

The proof is similar to that of Theorem 1. The upper bound is obtained by
choosing the minimum active probability of all tiers of BSs. ∎

####  IV-B3 Round-robin Scheduling

In the round-robin scheduling, if there are $N$ users within the typical cell,
a complete cycle will occupy $N$ time slots. Therefore, the duration between
two scheduled time slots for the typical user is $N$. If we only consider the
time slots that the typical user is scheduled, the serving of the typical user
could be considered as a new queueing system with the serving rate given by

$\mu=p\mathbb{P}(\mathrm{SIR}>\theta\mid\Phi_{b})=p\mathbf{P}_{\Phi_{b}}.$
(46)

The new queueing system is also a Geo/G/1 queueing system. Let $D_{\rm RR}$ be
the mean delay of the new queueing system, which is the mean number of
scheduled time slots required for the typical user to successfully transmit a
packet. Then, we have

$\displaystyle D_{\rm
RR}=\left\\{\begin{array}[]{ll}\frac{1-\xi_{0}}{\mu-\xi_{0}}&\textrm{if
$\mu>\xi_{0}$}\\\ \infty&\textrm{if $\mu\leq\xi_{0}$}.\end{array}\right.$ (49)

For the typical user, note that $N/2$ time slots are required on average if a
packet is successfully delivered in the first scheduled time slot; otherwise,
the additional time slots required should be the additional number of
scheduled time slots multiplied by $N$. Therefore, the conditional mean delay
$\mathbf{D}_{\Phi_{b}}$ in round-robin scheduling is

$\displaystyle\mathbf{D}_{\Phi_{b}}$ $\displaystyle=$ $\displaystyle N(D_{\rm
RR}-1)+\frac{N}{2}$ (52) $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}\frac{1-\xi_{0}}{\mu-\xi_{0}}N-\frac{N}{2}&\textrm{if
$\mu>\xi_{0}$}\\\ \infty&\textrm{if $\mu\leq\xi_{0}$}.\end{array}\right.$

The following lemma and theorem give the bounds for the cdf of the conditional
mean delay $\mathbf{D}_{\Phi_{b}}$ in round-robin scheduling.

######  Lemma 9.

In round-robin scheduling, if each interfering BS is active independently with
probability $q$, i.e., $\mathbb{P}(\zeta_{y}=1)=q$, the statistical cdf of the
mean delay of all users in the network equals the cdf of the mean delay of the
typical user conditioned on $\Phi_{b}$, which is

$\mathbb{P}\left(\mathbf{D}_{\Phi_{b}}\leq
T\right)=H_{3}(T,q)\triangleq\frac{1}{2}-\frac{1}{\pi}\sum_{k=1}^{K}\int_{0}^{\infty}\frac{1}{\omega}\mathrm{Im}\Big{\\{}\\\
\frac{{p}^{j\omega}}{\kappa(\omega,k,q)}\mathbb{E}_{N_{k},\xi_{0}}\Big{[}\Big{(}\xi_{0}+\frac{1-\xi_{0}}{1/2+T/N_{k}}\Big{)}^{-j\omega}\Big{]}\Big{\\}}\mathrm{d}\omega.$
(53)

###### Proof.

The proof is similar to that of Lemma 7. ∎

######  Theorem 3.

In round-robin scheduling, the statistical cdf of success probability and mean
delay of all users in the network are bounded by

$\displaystyle F(u,p)\leq\mathbb{P}\left(\mathbf{P}_{\Phi_{b}}\leq
u\right)\leq F(u,\frac{\xi_{\rm max}+\xi_{\rm min}}{2}p),$ $\displaystyle
H_{3}(T,p)\leq\mathbb{P}\left(\mathbf{D}_{\Phi_{b}}\leq T\right)\leq
H_{3}(T,\frac{\xi_{\rm max}+\xi_{\rm min}}{2}p).$ (54)

###### Proof.

The proof is similar to that of Theorem 1. ∎

Other user scheduling mechanisms, such as FDMA, could also be analyzed
similarly. In the case of FDMA, all users served by a same BS will be served
simultaneously using orthogonal sub-channels. Since not all sub-channels are
used at a BS, the set of BSs that cause interference to the typical link will
be only a subset of all BSs, i.e., the interfering BSs construe a thinning
version of the original BSs. Therefore, the approaches used in our work can be
also applied in the FDMA case, with the difference being that the interference
is thinned, and the user scheduling is simplified.

###  IV-C Delay Outage

In the design of practical wireless network, an intuitive and meaningful
metric is the proportion of users whose delay requirements cannot be achieved.
The delay requirement of a user $x_{i}$ cannot be achieved if the practical
mean delay of the user is larger than the mean delay requirement $\beta_{i}$
of the user. Therefore, we propose the notion of _delay outage_ which means
that the delay requirement of a user cannot be achieved. The user $x_{i}$ is
delay outage if and only if its mean delay is larger than $\beta_{i}$. We
further evaluate the delay outage probability, which is the proportion of
users that are delay outage in the wireless network, as

$\displaystyle\eta_{\mathrm{DO}}$ $\displaystyle\triangleq$
$\displaystyle\mathbb{E}_{\beta_{i}}\left(\mathbb{P}\left(\mathbf{D}_{\Phi_{b}}\geq\beta_{i}\right)\right)$
(55) $\displaystyle=$
$\displaystyle\frac{1}{\beta_{\max}-\beta_{\min}}\int_{\beta_{\min}}^{\beta_{\max}}\mathbb{P}\left(\mathbf{D}_{\Phi_{b}}\geq\beta_{i}\right)\mathrm{d}\beta_{i}.$

The previous results could be plugged into (55) to bound the delay outage
probability $\eta_{\mathrm{DO}}$.

##  V Numerical Evaluation

To gain insight, we discuss the statistical cdf of mean delay and the delay
outage numerically.

Figure 6: Upper and lower bounds for the cdfs of the mean delay of all queues
in the two tiered heterogeneous networks formed by macrocells and picocells.
The parameters are set as $P_{1}=39$dBm, $P_{2}=24$dBm,
$\lambda_{1}=0.00001$m-2, $\lambda_{2}=0.00005$m-2, $B_{1}=B_{2}=1$, $p=0.5$
and $\lambda_{u}=0.00005$m-2.

Figure 6 plots the upper and lower bounds for the statistical cdfs of the mean
delay of all queues in the heterogeneous networks formed by macrocells and
picocells. It is observed that the bounds are tight for large arrival rates of
the packets, which can be interpreted as that our proposed simplified system
and dominant system when deriving the bounds tend to be the same system for
large arrival rates. Comparing the curves for different arrival rates, we
observe that the delay performance of random scheduling is the worst while the
delay performance of round-robin scheduling outperforms FIFO scheduling when
the traffic is heavy, and it is reversed for light traffic. This is because
when the traffic is light, applying round-robin scheduling may waste some time
slots to schedule the empty queues, and when the traffic is heavy, in the FIFO
scheduling, the scheduling may be blocked at the users with poor link quality,
resulting in large delay for the packets. Figure 6 shows that the cdf of the
mean delay will not increase to one when increasing the value of the mean
delay, due to the fact that some users may be affected by strong interference,
and their queues increase to infinite resulting in infinite mean delay. We
also observe that certain percentage of users in the network experience very
low mean delay, i.e., the mean delay for those users approaches to two ($1/p$)
time slots, indicating that there are always certain percentage of users that
experience a small interference and a low mean delay.

Figure 7: Upper and lower bounds for the delay outage probability as functions
of bias factor $B_{2}$ in the two tiered heterogeneous networks formed by
macrocells and picocells. The parameters are set as $P_{1}=39$dBm,
$P_{2}=24$dBm, $\lambda_{1}=0.00001$m-2, $\lambda_{2}=0.00005$m-2, $\xi_{\rm
min}=0.7$, $\xi_{\rm max}=0.8$, $\beta_{\rm min}=18$, $\beta_{\rm max}=20$,
$B_{1}=1$, $p=1$ and $\lambda_{u}=0.00005$m-2.

Figure 7 plots the upper and lower bounds for the delay outage probability as
functions of the bias factor for the picocells $B_{2}$ in the two tiered
heterogeneous networks formed by macrocells and picocells for heavy traffic.
For all scheduling policies, when beginning to increase $B_{2}$ from $1$, the
delay outage probability in the network decreases, indicating that offloading
helps to reduce the traffic in the macrocells and effectively utilize the
resources in the picocells. Meanwhile, it is observed that as $B_{2}$
continues to increase, the delay outage probability of random scheduling and
FIFO scheduling tends to be constant while that of round-robin scheduling
first decreases then increases. It can be interpreted as that in the case of
random scheduling and FIFO scheduling, due to the heavy traffic, the
scheduling for the macrocells and several picocells experiencing poor channel
quality may be blocked and resulting in large delay, and only those users
served by the picocells with good channel quality satisfy the delay
requirement. However, for the round-robin scheduling, all users are ensured to
be served in each scheduling period. If most of the users are offloaded from
the macrocells to the picocells, the resources at the macrocells cannot be
fully utilized, and the delay outage probability will start to increase for
large $B_{2}$.

Figure 8: Upper and lower bounds for the delay outage as functions of active
probability $p$ in the two tiered heterogeneous networks formed by macrocells
and picocells. The parameters are set as $P_{1}=39$dBm, $P_{2}=24$dBm,
$\lambda_{1}=0.00001$m-2, $\lambda_{2}=0.00005$m-2, $B_{1}=B_{2}=1$, $\xi_{\rm
min}=0$, $\xi_{\rm max}=0.1$, $\beta_{\rm min}=18$, $\beta_{\rm max}=20$, and
$\lambda_{u}=0.00005$m-2. Figure 9: Upper and lower bounds for the delay
outage as functions of user density $\lambda_{u}$ for different number of
tiers in heterogeneous networks. The parameters are set as $P_{1}=39$dBm,
$P_{2}=24$dBm, $P_{3}=20$dBm, $\lambda_{1}=0.00001$m-2,
$\lambda_{2}=0.00005$m-2, $\lambda_{3}=0.0001$m-2, $B_{1}=B_{2}=B_{3}=1$,
$\xi_{\rm min}=0$, $\xi_{\rm max}=0.1$, $\beta_{\rm min}=18$, and $\beta_{\rm
max}=20$.

Figure 8 plots the upper and lower bounds for the delay outage probability as
functions of the active probability $p$ in the two tiered heterogeneous
networks formed by macrocells and picocells for light traffic ($\xi_{\rm
min}=0$, $\xi_{\rm max}=0.1$). Generally, increasing $p$ will decrease the
delay outage probability since the opportunity to schedule a packet is
increased for large $p$; meanwhile, the interference will not increase much
due to the light traffic. It is observed that the bounds are tight for small
$p$ and loose for large $p$. This is because when deriving the upper bound, we
introduced the dominant system where the interfering transmitters are assumed
to be backlogged. The busy probability of the BSs in the dominant system for
small $p$ is much closer to the busy probability in the original system than
that for large $p$.

Figure 9 plots the upper and lower bounds for the delay outage probability as
functions of user density $\lambda_{u}$ for different number of tiers in
heterogeneous cellular networks. The figure reveals that the delay outage
probability first decreases then increases as the increasing of user density.
This counterintuitive result can be interpreted as follows. When the user
density $\lambda_{u}$ is much smaller than the density of BSs, many cells are
empty and serve no user. Since we only consider the cells serving at least one
user, slightly increasing $\lambda_{u}$ will increase the proportion between
the number of cells serving one user and that of cells serving more than one
users. Noting that the cells with only one user experience much smaller delay
outage probability than that with more than one users, the overall delay
outage probability will decrease when slightly increasing the user density
$\lambda_{u}$ in the case where $\lambda_{u}$ is much smaller than the density
of BSs. Figure 9 also reveals that deploying more tiers of BSs helps to
decrease the delay outage probability only when the user density is large.

##  VI Conclusion

In this paper, a tractable approach is proposed to analyze the delay in the
heterogeneous cellular networks with spatio-temporal random arrival of
traffic. Meanwhile, the statistic of spatio-temporal traffic with offloading
policy is evaluated. The notion of delay outage is proposed to evaluate the
effect of different scheduling policies, such as random scheduling, FIFO
scheduling and round-robin scheduling. The obtained upper and lower bounds are
useful to evaluate the delay performance of the large wireless networks. The
numerical analysis shows that those bounds are tight especially for the case
of heavy traffic and small active probability.

The results reveal that the offloading policy based on cell range expansion
greatly reduces the macrocell traffic while bring a small amount of growth for
the picocell traffic, implying that the offloading policy is potential for
better utilization of the idle resources of the small cells. Our results also
show that the delay performance of round-robin scheduling outperforms FIFO
scheduling when the traffic is heavy, and it is reversed for light traffic
since applying round-robin scheduling may waste some time slots to schedule
the empty queues for light traffic, while in the FIFO scheduling, the
scheduling may be blocked at the users with poor channel quality for heavy
traffic, resulting in large delay.

##  Appendix A Proof of Lemma 5

###### Proof.

The success probability conditioned on $\Phi_{b}$ when the typical user is
served by a BS $y_{0}$ from the $k$th tier with link distance $Z_{k}=|y_{0}|$
is

$\displaystyle\\!\\!\mathbb{P}(\mathrm{SIR}>\theta\mid\Phi_{b},y_{0}\in\Phi_{k},Z_{k}=|y_{0}|)$
(56) $\displaystyle\\!\\!=\\!\\!$
$\displaystyle\\!\\!\mathbb{P}\bigg{(}\frac{P_{k}h_{y_{0}}|y_{0}|^{-\alpha}}{\sum_{i=1}^{K}\sum_{y\in\Phi_{i}\setminus
B(o,z_{ik})}\zeta_{y}P_{i}h_{y}|y|^{-\alpha}}$
$\displaystyle\\!\\!>\theta\mid\Phi_{b},y_{0}\in\Phi_{k},Z_{k}=|y_{0}|\bigg{)}$
$\displaystyle\\!\\!=\\!\\!$
$\displaystyle\\!\\!\mathbb{E}\bigg{[}\exp\bigg{(}-\frac{\theta|y_{0}|^{\alpha}}{P_{k}}{\sum_{i=1}^{K}\sum_{y\in\Phi_{i}\setminus
B(o,z_{ik})}\zeta_{y}P_{i}h_{y}|y|^{-\alpha}}\bigg{)}$
$\displaystyle\\!\\!\mid\Phi_{b},y_{0}\in\Phi_{k},Z_{k}=|y_{0}|\bigg{]}$
$\displaystyle\\!\\!=\\!\\!$
$\displaystyle\\!\\!\prod_{i=1}^{K}\prod_{y\in\Phi_{i}\setminus
B(o,z_{ik})}\bigg{(}\frac{q}{1+\theta|y_{0}|^{\alpha}|y|^{-\alpha}P_{i}/P_{k}}+1-q\bigg{)}.\qquad$

The moment generating function of
$Y\stackrel{{\scriptstyle\Delta}}{{=}}\ln\left(\mathbb{P}(\mathrm{SIR}>\theta\mid\Phi_{b},y_{0}\in\Phi_{k},Z_{k}=|y_{0}|)\right)$
is

$\displaystyle M_{Y}(s)\\!\\!$ $\displaystyle\\!\\!=\\!\\!$
$\displaystyle\\!\\!\mathbb{E}\left[\exp\left(sY\right)\right]$ (57)
$\displaystyle\\!\\!=\\!\\!$
$\displaystyle\\!\\!\mathbb{E}\left[\left(\mathbb{P}(\mathrm{SIR}>\theta\mid\Phi_{b},y_{0}\in\Phi_{k},Z_{k}=|y_{0}|)\right)^{s}\right]$
$\displaystyle\\!\\!\stackrel{{\scriptstyle(a)}}{{=}}\\!\\!$
$\displaystyle\\!\\!\prod_{i=1}^{K}\mathbb{E}_{\Phi_{i}}\bigg{[}\prod_{y\in\Phi_{i}\setminus
B(o,z_{ik})}$
$\displaystyle\\!\\!\left(\frac{q}{1+\theta|y_{0}|^{\alpha}|y|^{-\alpha}P_{i}/P_{k}}+1-q\right)^{s}\bigg{]}$
$\displaystyle\\!\\!\stackrel{{\scriptstyle(b)}}{{=}}\\!\\!$
$\displaystyle\\!\\!\prod_{i=1}^{K}\exp\Big{(}-2\pi\lambda_{i}\int_{z_{ik}}^{\infty}\Big{(}1-$
$\displaystyle\\!\\!\Big{(}\frac{q}{1+\theta|y_{0}|^{\alpha}r^{-\alpha}P_{i}/P_{k}}+1-q\Big{)}^{s}\Big{)}r\mathrm{d}r\Big{)},$

where $(a)$ follows from the independence between different tiers of BSs, and
$(b)$ follows from the probability generating functional (PGFL) of the PPP.
Then, we have

$\displaystyle M_{Y}(s)\\!\\!$ $\displaystyle\\!\\!=\\!\\!$
$\displaystyle\\!\\!\exp\Big{(}-2\pi\sum_{i=1}^{K}\lambda_{i}\int_{z_{ik}}^{\infty}\Big{(}1-$
(58)
$\displaystyle\\!\\!\Big{(}\frac{q}{1+\theta|y_{0}|^{\alpha}r^{-\alpha}P_{i}/P_{k}}+1-q\Big{)}^{s}\Big{)}r\mathrm{d}r\Big{)}$
$\displaystyle\\!\\!=\\!\\!$
$\displaystyle\\!\\!\exp\Big{(}-2\pi\sum_{i=1}^{K}\lambda_{i}\int_{z_{ik}}^{\infty}\sum_{n=1}^{\infty}\binom{s}{n}(-1)^{n+1}$
$\displaystyle\\!\\!\left(\frac{q\theta|y_{0}|^{\alpha}r^{-\alpha}P_{i}/P_{k}}{1+\theta|y_{0}|^{\alpha}r^{-\alpha}P_{i}/P_{k}}\right)^{n}r\mathrm{d}r\Big{)}$
$\displaystyle\\!\\!=\\!\\!$
$\displaystyle\\!\\!\exp\Big{(}-\pi\delta\sum_{i=1}^{K}\lambda_{i}\sum_{n=1}^{\infty}\binom{s}{n}(-1)^{n+1}$
$\displaystyle\\!\\!(q\theta|y_{0}|^{\alpha}P_{i}/P_{k})^{n}\int_{z_{ik}^{\alpha}}^{\infty}\frac{u^{\delta-1}}{\left(u+\theta|y_{0}|^{\alpha}P_{i}/P_{k}\right)^{n}}\mathrm{d}u\Big{)}$
$\displaystyle\\!\\!=\\!\\!$
$\displaystyle\\!\\!\exp\bigg{(}-\pi\delta\sum_{i=1}^{K}\lambda_{i}\sum_{n=1}^{\infty}\binom{s}{n}(-1)^{n+1}\Big{(}q\theta|y_{0}|^{\alpha}\frac{P_{i}}{P_{k}}\Big{)}^{n}$
$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\times\frac{z_{ik}^{\alpha(\delta-n)}}{n-\delta}{{}_{2}F_{1}\Big{(}n,n-\delta;n-\delta+1;-\frac{\theta|y_{0}|^{\alpha}P_{i}}{z_{ik}^{\alpha}P_{k}}\Big{)}}\bigg{)}.\quad$

The cdf of $Y$, denoted by $F_{Y}(y)=\mathbb{P}\left(Y\leq y\right)$, follows
from the Gil-Pelaez Theorem [43] as

$\displaystyle
F_{Y}(y)=\frac{1}{2}-\frac{1}{\pi}\int_{0}^{\infty}\frac{\mathrm{Im}\\{e^{-j\omega
y}M_{Y}(j\omega)\\}}{\omega}\mathrm{d}\omega.$ (59)

The cdf of
$\mathbb{P}(\mathrm{SIR}>\theta\mid\Phi_{b},y_{0}\in\Phi_{k},Z_{k}=|y_{0}|)$
is evaluated as

$\displaystyle\mathbb{P}\left(\mathbb{P}(\mathrm{SIR}>\theta\mid\Phi_{b},y_{0}\in\Phi_{k},Z_{k}=|y_{0}|)\leq
u\right)$ (60) $\displaystyle=$
$\displaystyle\mathbb{P}\left(\ln(\mathbb{P}(\mathrm{SIR}>\theta\mid\Phi_{b},y_{0}\in\Phi_{k},Z_{k}=|y_{0}|))\leq\ln
u\right)$ $\displaystyle=$ $\displaystyle F_{Y}({\ln u})$ $\displaystyle=$
$\displaystyle\frac{1}{2}-\frac{1}{\pi}\int_{0}^{\infty}\frac{1}{\omega}\mathrm{Im}\bigg{\\{}\exp\bigg{(}-j\omega{\ln
u}$
$\displaystyle-\pi\delta\sum_{i=1}^{K}\lambda_{i}\sum_{n=1}^{\infty}\binom{j\omega}{n}(-1)^{n+1}\Big{(}q\theta|y_{0}|^{\alpha}\frac{P_{i}}{P_{k}}\Big{)}^{n}\frac{z_{ik}^{\alpha(\delta-n)}}{n-\delta}$
$\displaystyle\times{{}_{2}F_{1}\Big{(}n,n-\delta;n-\delta+1;-\frac{\theta|y_{0}|^{\alpha}P_{i}}{z_{ik}^{\alpha}P_{k}}\Big{)}}\bigg{)}\bigg{\\}}\mathrm{d}\omega.$

Plugging in
$z_{ik}=\big{(}\frac{P_{i}B_{i}}{P_{k}B_{k}}\big{)}^{1/\alpha}|y_{0}|$, we
obtain

$\displaystyle\mathbb{P}\left(\mathbb{P}(\mathrm{SIR}>\theta\mid\Phi_{b},y_{0}\in\Phi_{k},Z_{k}=|y_{0}|)\leq
u\right)$ (61) $\displaystyle=$
$\displaystyle\frac{1}{2}-\frac{1}{\pi}\int_{0}^{\infty}\frac{1}{\omega}\mathrm{Im}\bigg{\\{}\exp\bigg{(}-j\omega{\ln
u}$
$\displaystyle+\pi\delta\sum_{i=1}^{K}\lambda_{i}\sum_{n=1}^{\infty}\binom{j\omega}{n}\Big{(}\frac{B_{i}}{B_{k}}\Big{)}^{\delta-n}\Big{(}\frac{P_{i}}{P_{k}}\Big{)}^{\delta}|y_{0}|^{2}$
$\displaystyle\times\frac{(-q\theta)^{n}}{n-\delta}{{}_{2}F_{1}\Big{(}n,n-\delta;n-\delta+1;-\theta\frac{B_{k}}{B_{i}}\Big{)}}\bigg{)}\bigg{\\}}\mathrm{d}\omega.\qquad$

The cdf of $\mathbb{P}(\mathrm{SIR}>\theta\mid\Phi_{b},y_{0}\in\Phi_{k})$ is
obtained by the total probability formula as

$\displaystyle\mathbb{P}\left(\mathbb{P}(\mathrm{SIR}>\theta\mid\Phi_{b},y_{0}\in\Phi_{k})\leq
u\right)$ (62) $\displaystyle=$
$\displaystyle\int_{0}^{\infty}\mathbb{P}\left(\mathbb{P}(\mathrm{SIR}>\theta\mid\Phi_{b},y_{0}\in\Phi_{k},Z_{k}=|y_{0}|)\leq
u\right)$ $\displaystyle\times f_{Z_{k}\mid y_{0}\in\Phi_{k}}(r)\mathrm{d}r$
$\displaystyle=$
$\displaystyle\frac{2\pi\lambda_{k}}{\mathcal{P}_{k}}\int_{0}^{\infty}\mathbb{P}\left(\mathbb{P}(\mathrm{SIR}>\theta\mid\Phi_{b},y_{0}\in\Phi_{k},Z_{k}=r)\leq
u\right)$ $\displaystyle\times e^{-{\pi
r^{2}\lambda_{k}}/{\mathcal{P}_{k}}}r\mathrm{d}r.\quad$

Plugging in (61) and calculating the integral with respective to $r$, we
obtain the theorem. ∎

##  Appendix B Proof of Lemma 7

###### Proof.

By the total probability formula, we obtain

$\displaystyle\mathbb{P}\left(\mathbf{D}_{\Phi_{b}}\leq T\right)\\!\\!$
$\displaystyle\\!\\!=\\!\\!$
$\displaystyle\\!\\!\sum_{k=1}^{K}\mathcal{P}_{k}\mathbb{P}\left(\mathbf{D}_{\Phi_{b}}\leq
T\mid y_{0}\in\Phi_{k}\right).$ (63)

Plugging in (32) and (35), we get the cdf as

$\displaystyle\mathbb{P}\left(\mathbf{D}_{\Phi_{b}}\leq T\right)\\!\\!$
$\displaystyle\\!\\!=\\!\\!$
$\displaystyle\\!\\!\sum_{k=1}^{K}\mathcal{P}_{k}\mathbb{E}_{N_{k},\xi_{0}}\left[\frac{1-\xi_{0}}{\mu-\xi_{0}}\leq
T\mid y_{0}\in\Phi_{k}\right]$ (64) $\displaystyle\\!\\!=\\!\\!$
$\displaystyle\\!\\!\sum_{k=1}^{K}\mathcal{P}_{k}\mathbb{E}_{N_{k},\xi_{0}}\Big{[}\mathbb{P}\Big{(}\mathbb{P}(\mathrm{SIR}>\theta\mid\Phi_{b},y_{0}\in\Phi_{k})$
$\displaystyle\\!\\!\geq\frac{N_{k}}{p}\Big{(}\xi_{0}+\frac{1-\xi_{0}}{T}\Big{)}\Big{)}\Big{]}.$

From Lemma 5, we have

$\mathbb{P}\left(\mathbf{D}_{\Phi_{b}}\leq
T\right)=\frac{1}{2}-\frac{1}{\pi}\sum_{k=1}^{K}\Big{[}\int_{0}^{\infty}\frac{1}{\omega}\mathrm{Im}\Big{\\{}p^{j\omega}\\\
\mathbb{E}_{N_{k},\xi_{0}}\Big{[}\Big{(}{N_{k}\Big{(}\xi_{0}+\frac{1-\xi_{0}}{T}\Big{)}}\Big{)}^{-j\omega}\Big{]}\kappa^{-1}(\omega,k,q)\Big{\\}}\mathrm{d}\omega\Big{]}.$
(65)

Therefore, we obtain the results. ∎

## References

  * [1] J. G. Andrews, S. Buzzi, W. Choi, S. V. Hanly, A. Lozano, A. C. K. Soong, and J. C. Zhang, “What Will 5G Be?” _IEEE J. on Sel. Areas in Commun._ , vol. 32, no. 6, pp. 1065–1082, Jun. 2014.
  * [2] M. Simsek, A. Aijaz, M. Dohler, J. Sachs, and G. Fettweis, “5G-enabled tactile Internet,” _IEEE J. on Sel. Areas in Commun._ , vol. 34, no. 3, pp. 460–473, Feb. 2016.
  * [3] G. P. Fettweis, “The tactile Internet: applications and challenges,” _IEEE Vehic. Tech. Magazine_ , vol. 9, no. 1, pp. 64–70, Mar. 2014.
  * [4] M. Wildemeersch, T. Q. Quek, C. H. Slump, and A. Rabbachin, “Cognitive small cell networks: Energy efficiency and trade-offs,” _IEEE Trans. on Commun._ , vol. 61, no. 9, pp. 4016–4029, Sep. 2013.
  * [5] W. C. Cheung, T. Q. Quek, and M. Kountouris, “Throughput optimization, spectrum allocation, and access control in two-tier femtocell networks,” _IEEE J. on Sel. Areas in Commun._ , vol. 30, no. 3, pp. 561–574, Mar. 2012\.
  * [6] D. Lopez-Perez, I. Guvenc, G. De la Roche, M. Kountouris, T. Q. Quek, and J. Zhang, “Enhanced intercell interference coordination challenges in heterogeneous networks,” _IEEE Wireless Commun._ , vol. 18, no. 3, pp. 22–30, Jun. 2011.
  * [7] D. C. Chen, T. Q. Quek, and M. Kountouris, “Backhauling in heterogeneous cellular networks: Modeling and tradeoffs,” _IEEE Trans. on Wireless Commun._ , vol. 14, no. 6, pp. 3194–3206, Feb. 2015.
  * [8] J. Lee and T. Q. Quek, “Hybrid full-/half-duplex system analysis in heterogeneous wireless networks,” _IEEE Trans. on Wireless Commun._ , vol. 14, no. 5, pp. 2883–2895, Jan. 2015.
  * [9] G. Zhang, T. Q. Quek, A. Huang, and H. Shan, “Delay and Reliability Tradeoffs in Heterogeneous Cellular Networks,” _IEEE Trans. on Wireless Commun._ , vol. 15, no. 2, pp. 1101–1113, Sep. 2016.
  * [10] Y. Zhong and W. Zhang, “Multi-channel hybrid access femtocells: A stochastic geometric analysis,” _IEEE Trans. on Commun._ , vol. 61, no. 7, pp. 3016–3026, Jul. 2013.
  * [11] J.-S. Ferenc and Z. Néda, “On the size distribution of Poisson Voronoi cells,” _Physica A: Statistical Mechanics and its Applications_ , vol. 385, no. 2, pp. 518–526, 2007.
  * [12] M. Haenggi, J. Andrews, F. Baccelli, O. Dousse, and M. Franceschetti, “Stochastic geometry and random graphs for the analysis and design of wireless networks,” _IEEE J. on Sel. Areas in Commun._ , vol. 27, no. 7, pp. 1029–1046, Sep. 2009.
  * [13] J. Andrews, F. Baccelli, and R. Ganti, “A tractable approach to coverage and rate in cellular networks,” _IEEE Trans. on Commun._ , no. 99, pp. 1–13, Nov. 2010.
  * [14] F. Baccelli, P. M$\ddot{\mathrm{u}}$hlethaler, and B. Blaszczyszyn, “Stochastic analysis of spatial and opportunistic ALOHA,” _IEEE J. on Sel. Areas in Commun._ , vol. 27, no. 7, pp. 1105–1119, Sep. 2009.
  * [15] M. Haenggi, _Stochastic Geometry for Wireless Networks_. Cambridge University Press, 2012.
  * [16] S. Singh, H. S. Dhillon, and J. G. Andrews, “Offloading in Heterogeneous Networks: Modeling, Analysis, and Design Insights,” _IEEE Trans. on Wireless Commun._ , vol. 12, no. 5, pp. 2484–2497, Apr. 2013.
  * [17] H.-S. Jo, Y. J. Sang, P. Xia, and J. G. Andrews, “Heterogeneous cellular networks with flexible cell association: A comprehensive downlink SINR analysis,” _IEEE Trans. on Wireless Commun._ , vol. 11, no. 10, pp. 3484–3495, Aug. 2012.
  * [18] R. R. Rao and A. Ephremides, “On the stability of interacting queues in a multiple-access system,” _IEEE Trans. on Inf. Theory_ , vol. 34, no. 5, pp. 918–930, Sep. 1988.
  * [19] B. S. Tsybakov and V. A. Mikhailov, “Ergodicity of a slotted ALOHA system,” _Problemy Peredachi Informatsii_ , vol. 15, no. 4, pp. 73–87, 1979.
  * [20] W. Szpankowski, “Stability conditions for some distributed systems: Buffered random access systems,” _Advances in Applied Probability_ , pp. 498–515, Jun. 1994.
  * [21] V. Anantharam, “The stability region of the finite-user slotted ALOHA protocol,” _IEEE Trans. on Inf. Theory_ , vol. 37, no. 3, pp. 535–540, May 1991.
  * [22] W. Luo and A. Ephremides, “Stability of N interacting queues in random-access systems,” _IEEE Trans. on Inf. Theory_ , vol. 45, no. 5, pp. 1579–1587, Jul. 1999.
  * [23] B. Blaszczyszyn, M. Jovanovic, and M. K. Karray, “Performance laws of large heterogeneous cellular networks,” in _IEEE WiOpt_ , 2015, pp. 597–604.
  * [24] N. Abbas, T. Bonald, and B. Sayrac, “How Mobility Impacts the Performance of Inter-cell Coordination in Cellular Data Networks,” in _IEEE Globecom_ , 2015.
  * [25] N. Sapountzis, T. Spyropoulos, N. Nikaein, and U. Salim, “An Analytical Framework for Optimal Downlink-Uplink User Association in HetNets with Traffic Differentiation,” in _IEEE Globecom_ , 2015.
  * [26] A. Ephremides and R.-Z. Zhu, “Delay analysis of interacting queues with an approximate model,” _IEEE Trans. on Commun._ , vol. 35, no. 2, pp. 194–201, Jan. 1987.
  * [27] Evolved Universal Terrestrial Radio Access, “Further advancements for E-UTRA physical layer aspects,” 3GPP TR 36.814, Tech. Rep., 2010.
  * [28] Y. Zhong, W. Zhang, and M. Haenggi, “Managing interference correlation through random medium access,” _IEEE Trans. on Wireless Commun._ , vol. 13, no. 2, pp. 928–941, Jan. 2014.
  * [29] Y. Zhong, M. Haenggi, T. Q. S. Quek, and W. Zhang, “On the Stability of Static Poisson Networks Under Random Access,” _IEEE Trans. on Commun._ , vol. 64, no. 7, pp. 2985–2998, July 2016.
  * [30] J. Wu, B. Cheng, M. Wang, and J. Chen, “Energy-Efficient Bandwidth Aggregation for Delay-Constrained Video over Heterogeneous Wireless Networks,” _IEEE J. on Sel. Areas in Commun._ , vol. 35, no. 1, pp. 30–49, 2017.
  * [31] B. Cheng, J. Yang, S. Wang, and J. Chen, “Adaptive Video Transmission Control System Based on Reinforcement Learning Approach Over Heterogeneous Networks,” _IEEE Trans. on Automation Science and Engineering_ , vol. 12, no. 3, pp. 1–10, 2015.
  * [32] J. Wu, B. Cheng, M. Wang, and J. Chen, “Delivering High-Frame-Rate Video to Mobile Devices in Heterogeneous Wireless Networks,” _IEEE Trans. on Commun._ , vol. 64, no. 11, pp. 4800–4814, 2017.
  * [33] J. Wu, B. Cheng, and M. Wang, “Energy minimization for quality-constrained video with multipath tcp over heterogeneous wireless networks,” in _IEEE ICDCS_ , 2016, pp. 487–496.
  * [34] X. Ge, J. Ye, Y. Yang, and Q. Li, “User Mobility Evaluation for 5G Small Cell Networks Based on Individual Mobility Model,” _IEEE J. on Sel. Areas in Commun._ , vol. 34, no. 3, pp. 528–541, Feb. 2016.
  * [35] M. Haenggi, “The Local Delay in Poisson Networks,” _IEEE Trans. on Inf. Theory_ , vol. 59, no. 3, pp. 1788–1802, Mar. 2013.
  * [36] Y. Zhong, W. Zhang, and M. Haenggi, “Stability analysis of static Poisson networks,” in _IEEE ISIT_ , 2015, pp. 2812–2816.
  * [37] M. Haenggi, “The Meta Distribution of the SIR in Poisson Bipolar and Cellular Networks,” _IEEE Trans. on Wireless Commun._ , vol. 15, no. 4, pp. 2577–2589, April 2016.
  * [38] A. Damnjanovic, J. Montojo, Y. Wei, T. Ji, T. Luo, M. Vajapeyam, T. Yoo, O. Song, and D. Malladi, “A survey on 3GPP heterogeneous networks,” _IEEE Wireless Commun._ , vol. 18, no. 3, pp. 10–21, Jun. 2011.
  * [39] Y. Zhong, W. Zhang, and M. Haenggi, “Delay analysis in static Poisson network,” in _IEEE/CIC ICCC_ , Nov 2015, pp. 1–5.
  * [40] X. Ge, S. Tu, G. Mao, C.-X. Wang, and T. Han, “5G ultra-dense cellular networks,” _IEEE Wireless Commun._ , vol. 23, no. 1, pp. 72–79, Mar. 2016\.
  * [41] I. Atencia and P. Moreno, “A discrete-time Geo/G/1 retrial queue with general retrial times,” _Queueing Systems_ , vol. 48, no. 1-2, pp. 5–21, Sep. 2004\.
  * [42] G. Falin, “A survey of retrial queues,” _Queueing systems_ , vol. 7, no. 2, pp. 127–167, Jun. 1990.
  * [43] J. Wendel _et al._ , “The non-absolute convergence of Gil-Pelaez’ inversion integral,” _The Annals of Mathematical Statistics_ , vol. 32, no. 1, pp. 338–339, Apr. 1961.

|  Yi Zhong received his B.S. and Ph.D. degree in Electronic Engineering from
University of Science and Technology of China (USTC) in 2010 and 2015
respectively. From August to December 2012, he was a visiting student in Prof.
Martin Haenggi’s group at University of Notre Dame. From July to October 2013,
he was an research intern with Qualcomm Incorporated, Corporate Research and
Development, Beijing. From July 2015 to December 2016, he was a Postdoctoral
Research Fellow with the Singapore University of Technology and Design (SUTD)
in the Wireless Networks and Decision Systems (WNDS) Group led by Prof. Tony
Q.S. Quek. Now, he is an assistant professor with School of Electronic
Information and Communications, Huazhong University of Science and Technology,
Wuhan, China. His main research interests include heterogeneous and femtocell-
overlaid cellular networks, wireless ad hoc networks, stochastic geometry and
point process theory.
---|---
|  Tony Q.S. Quek (S’98-M’08-SM’12) received the B.E. and M.E. degrees in
Electrical and Electronics Engineering from Tokyo Institute of Technology,
respectively. At MIT, he earned the Ph.D. in Electrical Engineering and
Computer Science. Currently, he is a tenured Associate Professor with the
Singapore University of Technology and Design (SUTD). He also serves as the
Associate Head of ISTD Pillar and the Deputy Director of the SUTD-ZJU IDEA.
His main research interests are the application of mathematical, optimization,
and statistical theories to communication, networking, signal processing, and
resource allocation problems. Specific current research topics include
heterogeneous networks, green communications, wireless security, internet-of-
things, and big data processing. Dr. Quek has been actively involved in
organizing and chairing sessions, and has served as a member of the Technical
Program Committee as well as symposium chairs in a number of international
conferences. He is serving as the Workshop Chair for IEEE Globecom in 2017,
the Tutorial Chair for the IEEE ICCC in 2017, and the Special Session Chair
for IEEE SPAWC in 2017. He is currently an Editor for the IEEE Transactions on
Communications and an elected member of IEEE Signal Processing Society SPCOM
Technical Committee. He was an Executive Editorial Committee Member for the
IEEE Transactions on Wireless Communications and an Editor for the IEEE
Wireless Communications Letters. He is a co-author of the book “Small Cell
Networks: Deployment, PHY Techniques, and Resource Allocation” published by
Cambridge University Press in 2013 and the book “Cloud Radio Access Networks:
Principles, Technologies, and Applications” by Cambridge University Press in
2017. Dr. Quek was honored with the 2008 Philip Yeo Prize for Outstanding
Achievement in Research, the IEEE Globecom 2010 Best Paper Award, the 2012
IEEE William R. Bennett Prize, the IEEE SPAWC 2013 Best Student Paper Award,
the IEEE WCSP 2014 Best Paper Award, the 2015 SUTD Outstanding Education
Awards – Excellence in Research, the 2016 Thomson Reuters Highly Cited
Researcher, and the 2016 IEEE Signal Processing Society Young Author Best
Paper Award.
---|---
|  Xiaohu Ge (M’09-SM’11) is currently a full Professor with the School of
Electronic Information and Communications at Huazhong University of Science
and Technology (HUST), China. He is an adjunct professor with with the Faculty
of Engineering and Information Technology at University of Technology Sydney
(UTS), Australia. He is the director of China International Joint Research
Center of Green Communications and Networking. He received his PhD degree in
Communication and Information Engineering from HUST in 2003. He has worked at
HUST since Nov. 2005. Prior to that, he worked as a researcher at Ajou
University (Korea) and Politecnico Di Torino from Jan. 2004 to Oct. 2005. His
research interests are in the area of mobile communications, traffic modeling
in wireless networks, green communications, and interference modeling in
wireless communications. He has published more than 130 papers in refereed
journals and conference proceedings and has been granted about 15 patents in
China. He received the Best Paper Awards from IEEE Globecom 2010. Dr. Ge is a
Senior Member of the China Institute of Communications and a member of the
National Natural Science Foundation of China and the Chinese Ministry of
Science and Technology Peer Review College. He has been actively involved in
organizing more the ten international conferences since 2005. He served as the
general Chair for the 2015 IEEE International Conference on Green Computing
and Communications (IEEE GreenCom 2015). He serves as an Associate Editor for
the IEEE Trancation on Green Communications and Networking, etc.
---|---


* [21] Francesco Guerra and Fabio Lucio Toninelli.  The high temperature region of the Viana-Bray diluted spin glass model.  Journal of statistical physics, 115:531–555, 2004.
  * [22] Yasunari Higuchi.  Remarks on the limiting Gibbs states on a (d+ 1)-tree.  Publications of the Research Institute for Mathematical Sciences, 13(2):335–348, 1977.
  * [23] Dmitry Ioffe.  On the extremality of the disordered state for the Ising model on the Bethe lattice.  Letters in Mathematical Physics, 37:137–143, 1996.
  * [24] Harry Kesten and Bernt P Stigum.  Additional limit theorems for indecomposable multidimensional Galton-Watson processes.  The Annals of Mathematical Statistics, 37(6):1463–1481, 1966.
  * [25] Marc Mézard and Andrea Montanari.  Reconstruction on trees and spin glass transition.  Journal of statistical physics, 124:1317–1350, 2006.
  * [26] Michael Molloy.  The freezing threshold for k-colourings of a random graph.  In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 921–930, 2012.
  * [27] Giorgio Parisi.  Infinite number of order parameters for spin-glasses.  Physical Review Letters, 43(23):1754, 1979.
  * [28] David Sherrington and Scott Kirkpatrick.  Solvable model of a spin-glass.  Physical review letters, 35(26):1792, 1975.
  * [29] Allan Sly.  Reconstruction of random colourings.  Communications in Mathematical Physics, 288(3):943–961, 2009.
  * [30] Daniel L Stein and Charles M Newman.  Spin glasses and complexity, volume 4.  Princeton University Press, 2013.
  * [31] Lenka Zdeborová and Florent Krzakala.  Statistical physics of inference: Thresholds and algorithms.  Advances in Physics, 65(5):453–552, 2016.

##  Appendix A Equivalence of Indicator and Product Gibbs distribution

Let $G=(V,E)$ be a graph, and let $\\{J_{e}:e\in E\\}$ be arbitrary couplings
over the edges of $G$. For $\beta>0$, let us write $\mu_{I}$, and $\mu_{P}$
for the Gibbs distributions over $\\{\pm 1\\}^{V}$, defined by the indicator,
and product formulation, respectively. That is, for every $\sigma\in\\{\pm
1\\}^{V}$, we have

$\displaystyle\mu_{I}(\beta;\sigma)$
$\displaystyle\propto\exp\left(\beta\cdot\sum_{\\{u,w\\}\in E}{\bf
1}\\{\sigma(u)=\sigma(w)\\}\cdot{\mathbold{J}}_{\\{u,w\\}}\right)\enspace,$
$\displaystyle\mu_{P}(\beta;\sigma)$
$\displaystyle\propto\exp\left(\beta\cdot\sum_{\\{u,w\\}\in
E}\sigma(u)\sigma(w)\cdot{\mathbold{J}}_{\\{u,w\\}}\right)\enspace.$

We will prove that $\mu_{P}(\beta;\sigma)=\mu_{I}(2\beta;\sigma)$, for every
$\sigma\in\\{\pm 1\\}^{V}$. Indeed, let $\sigma\in\\{\pm 1\\}^{V}$ be
arbitrary, then

$\displaystyle\mu_{P}(\beta;\sigma)$
$\displaystyle\propto\exp\left(\beta\cdot\sum_{\\{u,w\\}\in
E}\sigma(u)\sigma(w)\cdot{\mathbold{J}}_{\\{u,w\\}}\right)$
$\displaystyle=\exp\left(\beta\cdot\sum_{\\{u,w\\}\in E}(2\cdot{\bf
1}\\{\sigma(u)=\sigma(w)\\}-1)\cdot{\mathbold{J}}_{\\{u,w\\}}\right)$
$\displaystyle=\exp\left(2\beta\cdot\sum_{\\{u,w\\}\in E}{\bf
1}\\{\sigma(u)=\sigma(w)\\}\cdot{\mathbold{J}}_{\\{u,w\\}}\right)\cdot\exp\left(-\beta\cdot\sum_{\\{u,w\\}\in
E}{\mathbold{J}}_{\\{u,w\\}}\right)$
$\displaystyle\propto\exp\left(2\beta\cdot\sum_{\\{u,w\\}\in E}{\bf
1}\\{\sigma(u)=\sigma(w)\\}\cdot{\mathbold{J}}_{\\{u,w\\}}\right)=\mu_{I}(2\beta;\sigma)\enspace.$

Since $\mu_{P}$, $\mu_{I}$, are probability measures, we conclude that
$\mu_{P}(\beta;\sigma)=\mu_{I}(2\beta;\sigma)$, as desired.

##  Appendix B KS-Bound Derivation

First, note that since ${\mathbold{M}}$ is symmetric,
${\mathbold{M}}\otimes{\mathbold{M}}$ must be symmetric as well. In
particular, we have that

${\mathbold{M}}\otimes{\mathbold{M}}=\frac{1}{\left(1+e^{\beta{\mathbold{J}}}\right)^{2}}\begin{pmatrix}e^{2\beta{\mathbold{J}}}&e^{\beta{\mathbold{J}}}&e^{\beta{\mathbold{J}}}&1\\\\[2.0pt]
e^{\beta{\mathbold{J}}}&e^{2\beta{\mathbold{J}}}&1&e^{\beta{\mathbold{J}}}\\\\[2.0pt]
e^{\beta{\mathbold{J}}}&1&e^{2\beta{\mathbold{J}}}&e^{\beta{\mathbold{J}}}\\\\[2.0pt]
1&e^{\beta{\mathbold{J}}}&e^{\beta{\mathbold{J}}}&e^{2\beta{\mathbold{J}}}\end{pmatrix}\enspace,$
(78)

It is also easy to check that the for any matrix with the same pattern on its
entries we have the following

######  Observation B.1.

The spectrum of every $4\times 4$ matrix, $B$, of the following form

$B=\begin{pmatrix}a&b&b&c\\\ b&a&c&b\\\ b&c&a&b\\\ c&b&b&a\\\
\end{pmatrix}\enspace,\text{ with }a,b,c,d\in\mathbb{R}\enspace,$ (79)

is precisely
$\\{\\{\lambda_{1}:=(a+2b+c),\;\lambda_{2}:=(a-c),\;\lambda_{3}:=(a-c)\;\lambda_{4}:=(a-2b+c),\\}\\}$.
In particular, every eigenvalue of $B$ is a linear combination of its
elements.

Note that both ${\mathbold{M}}\otimes{\mathbold{M}}$, and
$\mathbb{E}[{\mathbold{M}}\otimes{\mathbold{M}}]$, are of the form (79). In
the following lemma we show that Observation B.1 allows us to change the order
of averaging and taking eigenvalues of ${\mathbold{M}}\otimes{\mathbold{M}}$.

######  Lemma B.2.

Let $\lambda_{1},\lambda_{2},\lambda_{3},\lambda_{4}$, be as in Observation
B.1. Then, for every $1\leq k\leq 4$ we have that

$\lambda_{k}\left(\mathbb{E}\left[{\mathbold{M}}\otimes{\mathbold{M}}\right]\right)=\mathbb{E}\left[\lambda_{k}\left({\mathbold{M}}\otimes{\mathbold{M}}\right)\right]\enspace.$
(80)

###### Proof.

Since both ${\mathbold{M}}\otimes{\mathbold{M}}$, and
$\mathbb{E}[{\mathbold{M}}\otimes{\mathbold{M}}]$, are of the form (79), each
$\lambda_{k}$ is a linear combination of their entries, and thus, the result
follows by the linearity of expectation. ∎

Let us now recall that equation (10) defins $\Delta_{\rm KS}$ as follows

$\Delta_{\rm
KS}=\left(\max_{x\in{\mathcal{E}}:\left|\left|x\right|\right|=1}\langle\Xi
x,x\rangle\right)^{-1}\enspace,$

where
${\mathcal{E}}=\left\\{z\in\mathbb{R}^{{\mathcal{A}}}\otimes\mathbb{R}^{{\mathcal{A}}}:\forall
y\in\mathbb{R}^{{\mathcal{A}}}\langle z,{\bf 1}\otimes y\rangle=\langle
z,y\otimes{\bf 1}\rangle=0\right\\}$, and
$\Xi=\mathbb{E}[{\mathbold{M}}\otimes{\mathbold{M}}]$. Since $\Xi$ is of the
form (79), and in particular symmetric, it is easy to argue, e.g. using
Courant-Fisher theorem, that the solution to the maximisation in (10) must be

$\max_{x\in{\mathcal{E}}:\left|\left|x\right|\right|=1}\langle\Xi
x,x\rangle=\lambda_{4}(\Xi)\enspace.$ (81)

Using now Lemma B.2 we get that $\Delta_{\rm
KS}=(\lambda_{4}(\Xi))^{-1}=(\mathbb{E}\left[\lambda_{4}\left({\mathbold{M}}\otimes{\mathbold{M}}\right)\right])^{-1}$.
Substituting the entries of ${\mathbold{M}}\otimes{\mathbold{M}}$ from (78),
yields $\Delta_{\rm
KS}=\textstyle\left(\mathbb{E}\left[\left(\frac{1-\exp(\beta{\mathbold{J}})}{1+\exp(\beta{\mathbold{J}})}\right)^{2}\right]\right)^{-1}$,
as desired.

##  Appendix C Proof of Lemma 6.1

###### Proof.

First, let us recall that we denote with $\Lambda$ the set of vertices at
distance $h$ from the root $r$. Also, for $s\in\\{\pm 1\\}$ and $\tau\in\\{\pm
1\\}^{\Lambda}$, we write $\mu_{r}^{\Lambda,\tau}$, and $\mu_{\Lambda}^{s}$,
for the marginal of $\mu$ on the root, conditioned on
${\mathbold{\sigma}}(\Lambda)=\tau$, and the marginal of $\mu$ on the the set
$\Lambda$, conditioned on ${\mathbold{\sigma}}(r)=s$, respectively. We now
have that

$\displaystyle\left\|\mu_{\Lambda}^{+}(\cdot)-\mu_{\Lambda}^{-}(\cdot)\right\|_{\rm
TV}$ $\displaystyle=\frac{1}{2}\sum_{\tau\in\\{\pm
1\\}^{\Lambda}}\left|\mu_{\Lambda}^{+}(\tau)-\mu_{\Lambda}^{-}(\tau)\right|$
$\displaystyle=\frac{1}{2}\sum_{\tau\in\\{\pm
1\\}^{\Lambda}}\left|\mu_{r}^{\Lambda,\tau}\left(+1\right)\frac{\mu({\mathbold{\sigma}}(\Lambda)=\tau)}{\mu({\mathbold{\sigma}}(r)=+1)}-\mu_{r}^{\Lambda,\tau}\left(-1\right)\frac{\mu({\mathbold{\sigma}}(\Lambda)=\tau)}{\mu({\mathbold{\sigma}}(r)=-1)}\right|$
(82) $\displaystyle=\sum_{\tau\in\\{\pm
1\\}^{\Lambda}}\left|\mu_{r}^{\Lambda,\tau}\left(+1\right)-\mu^{\Lambda,\tau}_{r}\left(-1\right)\right|\cdot{\mu({\mathbold{\sigma}}(\Lambda)=\tau)}$
(83)
$\displaystyle=\mathbb{E}_{\tau\sim\mu_{\Lambda}}\left[\left|\mu_{r}^{\Lambda,\tau}\left(+1\right)-\mu^{\Lambda,\tau}_{r}\left(-1\right)\right|\right]\enspace,$

where (82) follows from Bayes’ rule, and (83) is due to the fact that
$\mu({\mathbold{\sigma}}(r)=-1)=\mu({\mathbold{\sigma}}(r)=+1)={1}/{2}$. Next,
we observe that

$\displaystyle\mathbb{E}_{\tau\sim\mu_{\Lambda}}\left[\left(\mu_{r}^{\Lambda,\tau}(+1)\right)^{2}\right]$
$\displaystyle=\mathbb{E}_{\tau\sim\mu_{\Lambda}}\left[\left(1-\mu_{r}^{\Lambda,\tau}(-1)\right)^{2}\right]$
$\displaystyle=1-2\mathbb{E}_{\tau\sim\mu_{\Lambda}}\left[\mu_{r}^{\Lambda,\tau}(-1)\right]+\mathbb{E}_{\tau\sim\mu_{\Lambda}}\left[\left(\mu_{r}^{\Lambda,\tau}(-1)\right)^{2}\right]$
$\displaystyle=1-2\cdot\mu({\mathbold{\sigma}}(r)=+1)+\mathbb{E}_{\tau\sim\mu_{\Lambda}}\left[\left(\mu_{r}^{\Lambda,\tau}(-1)\right)^{2}\right]$
$\displaystyle=\mathbb{E}_{\tau\sim\mu_{\Lambda}}\left[\left(\mu_{r}^{\Lambda,\tau}(-1)\right)^{2}\right]\enspace.$
(84)

Using the above, we also get that

$\displaystyle\left\|\mu_{\downarrow\uparrow}^{+}(\cdot)-\mu_{\downarrow\uparrow}^{-}(\cdot)\right\|_{\rm
TV}$
$\displaystyle=\left|\mu_{\downarrow\uparrow}^{+}(+1)-\mu_{\downarrow\uparrow}^{-}(+1)\right|$
$\displaystyle=\left|\sum_{\tau\in\\{\pm
1\\}^{\Lambda}}\mu^{+}_{\Lambda}(\tau)\mu_{r}^{\Lambda,\tau}(+1)-\mu^{-}_{\Lambda}(\tau)\mu_{r}^{\Lambda,\tau}(+1)\right|$
(85) $\displaystyle=\left|\sum_{\tau\in\\{\pm
1\\}^{\Lambda}}\left(\mu_{r}^{\tau,\Lambda}(+1)-\mu_{r}^{\tau,\Lambda}(-1)\right)\cdot
2\cdot\mu\left({\mathbold{\sigma}}(\Lambda)=\tau\right)\cdot\mu_{r}^{\Lambda,\tau}(+1)\right|$
(86)
$\displaystyle=\left|2\cdot\mathbb{E}_{\tau\sim\mu_{\Lambda}}\left[\left(\mu_{r}^{\Lambda,\tau}(+1)\right)^{2}\right]-2\cdot\mathbb{E}_{\tau\sim\mu_{\Lambda}}\left[\mu_{r}^{\Lambda,\tau}(+1)\mu_{r}^{\Lambda,\tau}(-1)\right]\right|$
$\displaystyle=\left|\mathbb{E}_{\tau\sim\mu_{\Lambda}}\left[\left(\mu_{r}^{\Lambda,\tau}(+1)-\mu_{r}^{\Lambda,\tau}(+1)\right)^{2}\right]\right|$
(87)
$\displaystyle=\mathbb{E}_{\tau\sim\mu_{\Lambda}}\left[\left|\mu_{r}^{\Lambda,\tau}(+1)-\mu_{r}^{\Lambda,\tau}(-1)\right|^{2}\right]\enspace,$

where (85) follows from (34), while (86) is due to the Bayes’ rule, and the
fact that
$\mu({\mathbold{\sigma}}(r)=-1)=\mu({\mathbold{\sigma}}(r)=+1)={1}/{2}$.
Finally, we get (87) from the observation (84). The result now follows from
the Cauchy-Schwartz inequality. ∎