# A Statistical Characterization of Localization Performance in Millimeter-
Wave Cellular Networks

Jiajun He, Young Jin Chun This work was supported by in part by the City
University of Hong Kong (CityU), Startup Grant 7200618, and in part by the
CityU, Strategic Research Grant 21219520J. He and Y. J. Chun are with the
Department of Electrical Engineering, City University of Hong Kong, Hong Kong,
China (e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Millimeter-wave (mmWave) communication is a promising solution for achieving
high data rate and low latency in 5G wireless cellular networks. Since
directional beamforming and antenna arrays are exploited in the mmWave
networks, accurate angle-of-arrival (AOA) information can be obtained and
utilized for localization purposes. The performance of a localization system
is typically assessed by the Cram$\bf\acute{\rm e}$r-Rao lower bound (CRLB)
evaluated based on fixed node locations. However, this strategy only produces
a fixed value for the CRLB specific to the scenario of interest. To allow
randomly distributed nodes, stochastic geometry has been proposed to study the
CRLB for time-of-arrival-based localization. To the best of our knowledge,
this methodology has not yet been investigated for AOA-based localization. In
this work, we are motivated to consider the mmWave cellular network and derive
the CRLB for AOA-based localization and its distribution using stochastic
geometry. We analyze how the CRLB is affected by the node locations’ spatial
distribution, including the target and participating base stations. To apply
the CRLB on a network setting with random node locations, we propose an
accurate approximation of the CRLB using the $\lceil L/4\rceil$-th value of
ordered distances where $L$ is the number of participating base stations.
Furthermore, we derive the localizability of mmWave network, which is the
probability that a target is localizable, and examine how the network
parameters influence the localization performance. These findings provide us
deep insight into optimum network design that meets specified localization
requirements.

###### Index Terms:

Millimeter-wave, angle-of-arrival, localizability, Cram$\bf\acute{\rm e}$r-Rao
lower bound.

##  I Introduction

Due to the emergence of internet-of-things, positioning techniques have
received considerable attention, which can be utilized to enhance user
experience of location-based services, including navigation, mapping, and
intelligent transportation systems [1]. Fifth-generation (5G) wireless network
access interface together with its large bandwidth, high carrier frequency,
and massive antenna array offers excellent opportunities for accurate
localization, and millimeter-wave (mmWave) is a promising technology for the
5G wireless communication systems to meet such requirements. Wireless networks
enable us to obtain accurate location-bearing information from estimating the
channel parameters, such as time-of-arrival (TOA), time-difference-of-arrival
(TDOA), received signal strength (RSS), and angle-of-arrival (AOA). In mmWave
networks, we can exploit the large antenna array and highly directional
transmission to acquire the AOAs with high precision[2]. Large-scale
directional antenna arrays are leveraged due to the small wavelength of mmWave
signals, which can generate highly directional beams and provide large
beamforming gain[3]. In this paper, we analyze the localization performance of
the mmWave wireless network using the AOA measurements.

A target is localizable if its position can be determined without ambiguity
with a sufficient number of participating base stations (BSs). The AOA-based
positioning requires at least $2$ BSs to determine the location of the target
in a two-dimensional (2-D) plane [4]. Since the number of participating BSs
determines the accuracy of the localization, we introduce the notion of
$L$-localizability, which indicates the probability of at least $L$ BSs
participating in the localization procedure.

Furthermore, Cram$\bf\acute{\rm e}$r-Rao lower bound (CRLB) is a standard tool
to analyze the performance of localization algorithm, which provides a lower
bound for the position error of any unbiased estimator [4]. Conventionally,
CRLB assumes a fixed scenario, where the nodes are placed at a particular
geometry, and this assumption limits the applicability of CRLB as it cannot
properly reflect the impact of the random geometry. To evaluate the
localization error of a random network, we use stochastic geometry [5, 6] and
consider the ensemble average of the node spatial locations. Then the CRLB is
no longer a fixed value, but rather a random variable (RV) conditioned on the
number of participating BSs, where the randomness of CRLB is induced by the
randomness of the nodes. Based on the $L$-localizability and random CRLB, we
provide a deep insight for the network operator on how to deploy the BSs to
achieve a given localization requirement. The main contributions of this paper
are summarized as follows.

####  I-1 $L$-Localizability

We derive the tractable expression of $L$-localizability to study the number
of BSs who can participate in a localization procedure. In [7], the authors
studied on how the network parameters affect the localization performance of
the Long Term Evolution (LTE) cellular network. In this work, we derive the
$L$-localizability for the mmWave networks, where the impacts of the
directional antenna and Nakagami fading on mmWave-based localization systems
are assessed. Furthermore, we introduce asymptotic bounds and approximations
for the distribution of the $L$-localizability and CRLB to provide analytical
tools to track the performance of localization systems.

####  I-2 Random AOA-based CRLB

In the mmWave networks, accurate AOA measurements can be obtained by using
antenna arrays to locate the target of interest with high precision. In this
paper, we derive random CRLB for AOA-based positioning. Previous works [8, 9,
10] applied stochastic geometry to TOA-based localization, and to the best of
our knowledge, there is no prior work that investigates random geometry on
AOA-based localization systems. We derive the distribution of AOA-positioning
based CRLB for the mmWave networks by using stochastic geometry and order
statistics. The obtained distribution shows how the network parameters affect
localization performance in the mmWave wireless networks.

The rest of this paper is organized as follows. Relevant works are reviewed in
Section II, the system model is presented in Section III, and we analyze the
localization performance in Section IV. Numerical results are provided in
Section V and we conclude the paper in Section VI.

##  II Related Work

The major localization techniques in the LTE mobile network are TDOA [11, 12],
uplink TDOA [13], measurement report (MR) [14] and enhanced cell ID (E-CID)
[15]. Compared with the LTE mobile network, mmWave is regarded as a promising
candidate to meet demands for achieving accurate localization in the 5G mobile
network. Conventionally, the localization approaches can be divided into two
categories: direct and indirect localization. In the mmWave networks, we focus
on the latter due to the high computational complexity of the former. The
target of interest can be located in mmWave networks using the indirect
approach by estimating the channel parameters, including TOA, AOA, and RSS
[16]. Based on the processing methods of mmWave signals, localization
approaches can be categorized into proximity, fingerprinting, and geometry-
based [17]. In this paper, we mainly focus on the geometry-based positioning
approach because large-scale antenna arrays can provide high angular
resolution [18].

Localization performance is generally evaluated using CRLB for a fixed
geometry [4]. For considering all possible localization scenarios, we aim to
derive the network-wide distribution of localization performance, and there
are two important metrics, namely, the probability that a given number of BSs
can participate in a localization procedure, and the distribution of the CRLB
conditioned on the number of participating BSs. The first metric, which
includes finding the participation probability of a given number of BSs, was
studied in [7]. The authors modeled a cellular network with a homogeneous
Poisson point process (PPP) [5] and applied a “dominant interferer analysis”
to derive an expression for the probability of $L$-localizability. However,
this method is only suitable for LTE mobile networks. Compared with [7], we
derive an accurate expression of $L$-localizability using Alzer’s inequality
[19] for characterizing the localization performance of mmWave wireless
networks.

Regarding the second metric, there have been several attempts in the
literature to achieve this conditional distribution of CRLB. In [20],
approximations of this conditional distribution were presented for RSS and TOA
localization systems. However, these distributions are sensitive to the number
of participating BSs, and it is only accurate for numerous participating BSs.
In real-world scenarios, we prefer to measure the conditional distribution
using smaller number of participating BSs because this is more common in
cellular networks. Additionally, [8] presented an analysis of how the CRLB is
affected by the order statistics of internodal angles. This analysis reveals a
connection between the second largest internodal angle and the CRLB, leading
to an accurate approximation of the CRLB. However, only TOA-based localization
is considered in a general fading channel which takes the large-scale fading
into consideration. Motivated by these works, we explore the localization
performance using the AOA measurements and apply it in the mmWave-based
cellular network. Different from [8], we analyze how the CRLB is affected by
the ordered distances between BSs and target, and an accurate approximation of
the CRLB is provided using the $\lceil L/4\rceil$-th distance between these
ordered distances, where $L$ is the number of participating BSs in a
localization procedure.

##  III System Model

In this section, we describe the system model where the key notations used in
this paper are summarized in Table $1$.

###  III-A Network Model

We consider downlink transmission in a mmWave cellular network where the
locations of BSs are modeled using a homogeneous PPP[5]. As illustrated in
Fig. 1, we assume that the target is located at the origin O and the BSs are
randomly distributed over the $\mathbb{R}^{2}$ plane. The red triangle
represents the nearest BS to the target that is located inside the disk,
whereas the green triangle indicates the furthest BS from the target residing
in the disk. Furthermore, blue and yellow triangles represent the BSs that are
located inside and outside the disk, respectively. Let us denote the locations
of the BS as $\bm{\psi}_{l}=[x_{l},y_{l}]\in\mathbb{R}^{2}$ and the distance
between the $l$-th BS and target as $r_{l}=||\bm{\psi}_{l}||$. Based on the
system model, the probability density function (PDF) and cumulative
distribution function (CDF) of the $L$-th nearest BS are given by [21]

$\begin{split}f_{r_{L}}(r)&=\frac{2(\lambda\pi
r^{2})^{L}}{r(L-1)!}e^{-\lambda\pi r^{2}},\\\
F_{r_{L}}(r)&=1-\sum_{n=0}^{L-1}\frac{1}{n!}e^{-2\pi\lambda r^{2}}(2\pi\lambda
r^{2})^{n},\end{split}$ (1)

where $\lambda$ represents the BS density. Conditioned on the distance of the
$L$-th BS from O, the remaining BSs closer to the origin than the $L$-th BS
form a uniform binomial point process (BPP) on $\bm{b}(\textit{O},R_{L})$
[22], where the PDF and CDF of $r_{l}$ are given by

$f_{r_{l}}(r)=\frac{2r}{r_{L}^{2}-r_{1}^{2}},\quad
F_{r_{l}}(r)=\frac{r^{2}}{r_{L}^{2}-r_{1}^{2}},$ (2)

with $r_{1}\leq r_{l}\leq r_{L}$. In Section IV, we applied order statistic to
obtain the distribution of the ordered distances.

Table I: Summary of Notation Notation |  Meaning
---|---
T |  transpose
H |  conjugate transpose
$||\cdot||$ |  Euclidean norm
$\bm{\psi}_{l}$ |  location of $l$-th BS
$\bm{\psi}_{t}$ |  location of target
$r_{l}$ |  distance between $l$-th BS and target
$r_{1}$ |  distance between closest BS and target
$r_{L}$ |  distance between furthest BS and target
$\lambda$ |  BS density in the disk
$P_{t}$ |  BS and target transmit power
$N_{t}$ |  number of antenna elements
$N$ |  number of clusters
$\rho_{\bm{\psi}_{n}}$ |  small-scale fading gain
$d$ |  antenna spacing
$\lambda_{w}$ |  antenna wavelength
$\theta_{\bm{\psi}}$ |  AOA of BS at location $\bm{\psi}$
$n_{{\rm{AOA}},l}$ |  WGN with zero mean and variance of $\sigma_{{\rm{AOA}},l}^{2}$
$G_{1}$ |  main-lobe gain
$G_{2}$ |  side-lobe gain
$p_{a}$ |  probability of main-lobe gain is received
$p_{b}$ |  probability of side-lobe gain is received
$P_{T}$ |  total transmit power
$P_{m}$ |  power spectrum density of main-lobe
$P_{s}$ |  power spectrum density of side-lobe
$\sigma_{n}^{2}$ |  normalized noise power
$a_{i}$ |  network load indicator
$q$ |  probability of BS is activated
$\alpha$ |  path-loss exponent
$\Omega$ |  total number of activated BSs
$\tau$ |  signal-to-interference-plus-noise ratio threshold
$\gamma$ |  maximum number of selectable BSs
$\sigma_{\rm{AOA}}$ |  standard deviation of AOA measurement
$G_{c}$ |  average channel gain of mmWave network
$N_{0}$ |  spectral density of WGN
$W_{\rm{TOT}}$ |  total mmWave system bandwidth

###  III-B Channel Model

We assume that each BS is equipped with a directional antenna array composed
of $N_{t}$ elements and all BSs operate at a constant power $P_{t}$. In the
mmWave channel, the non-line-of-sight (NLOS) interference is negligible since
the channel gains of NLOS paths are typically 20 dB weaker than those from the
line-of-sight (LOS) [23]. The effect of path-loss can be reduced due to the
utilization of the directional antenna arrays, and it is also applied to
provide highly directional beams. The received signal from the $l$-th BS to
the origin is given by

$\begin{split}y(t)&=\sqrt{P_{t}\beta}\bm{h}_{\psi_{l}}\bm{w}_{\psi_{l}}r_{l}^{-\frac{\alpha}{2}}s_{\psi_{l}}(t)+n(t)\\\
&+\sum_{\bm{\psi}\in\bm{\psi}^{\prime}}\sqrt{P_{t}\beta}\bm{h}_{\bm{\psi}}\bm{w}_{\bm{\psi}}||\bm{\psi}||^{-\frac{\alpha}{2}}s_{\bm{\psi}}(t),\quad
t\in\left[0,T\right],\end{split}$ (3)

where $s_{\bm{\psi}}(t)$ is the transmit signal, $\bm{h}_{\bm{\psi}}$ is the
channel vector, $\alpha$ and $\beta$ respectively represent the path-loss
exponent and path-loss intercept, $\bm{w}_{\bm{\psi}}$ denotes the beamforming
vector of the node at location $\bm{\psi}$, and $n(t)$ represents the additive
white Gaussian noise (AWGN) with variance $\sigma^{2}$. Note that the
locations of the interfering transmitters are denoted as $\bm{\psi}^{\prime}$.

Due to high free-space path-loss, the mmWave propagation environment is well
characterized by a clustered channel model, known as the Saleh-Valenzuela
model[24]:

$\bm{h}_{\bm{\psi}}=\sqrt{N_{t}}\sum_{n=1}^{N}\rho_{\bm{\psi},{n}}\bm{a}_{t}^{H}(\theta_{\bm{\psi},{n}}),$
(4)

where $N$ is the number of clusters and $\rho_{\bm{\psi},{n}}$ represents the
complex small-scale fading coefficient of the $n$-th cluster. We assume that
the fading channel power gain follows a gamma distribution, i.e.,
$|\rho_{\bm{\psi}}|^{2}\sim\Gamma(M,\frac{1}{M})$, with Nakagami parameter
$M$. In this paper, we focus on LOS paths, i.e., $N=1$, and adopt a uniformly
random single path (UR-SP) channel model that is commonly used in the mmWave
network analysis [25]. The $\bm{a}_{t}(\theta_{\bm{\psi}})$ represents the
transmit array response vector corresponding to the AOA $\theta_{\bm{\psi}}$.
We consider a uniform linear array (ULA) with $N_{t}$ antenna elements, where
the transimt array response vectors are given by

$\bm{a}_{t}(\theta_{\bm{\bm{\psi}}})=\frac{1}{\sqrt{N_{t}}}\left[1,\ldots,e^{j2\pi
k\theta_{\bm{\psi}_{1}}},\ldots,e^{j2\pi(N_{t}-1)\theta_{\bm{\psi}}}\right]^{T},$
(5)

where $d$ is the antenna spacing, $\lambda_{w}$ represents the wavelength,
$\phi_{\bm{\psi}}$ denotes the AOA, $k\in\left[0,N_{t}\right]$ is the antenna
index, and $\theta_{\bm{\psi}}=\frac{d}{\lambda_{w}}\sin\phi_{\bm{\psi}}$ is
uniformly distributed over
$\left[-\frac{d}{\lambda_{w}},\frac{d}{\lambda_{w}}\right]$.

Fig. 1: System model of the mmWave wireless networks

Fig. 2: AOA-based positioning

Once the AOA measurements are obtained, we compute the location of the target,
where we assume LOS propagation. As shown in Fig. 2, we denote the AOA between
the target and $l$-th BS as $\theta_{l}$ and the location of target as
$\bm{\psi}_{t}=[x_{t},y_{t}]$,

$\tan(\theta_{l})=\frac{y_{l}-y_{t}}{x_{l}-x_{t}},\quad l=\\{1,\ldots,L\\}.$
(6)

The AOA measurement at the $l$-th BS is modeled as follows

$r_{{\rm{AOA}},l}=\theta_{l}+n_{{\rm{AOA}},l}=\tan^{-1}\left(\frac{y_{l}-y_{t}}{x_{l}-x_{t}}\right)+n_{{\rm{AOA}},l},$
(7)

where $n_{{\rm{AOA}},l}$ is the AWGN with variance
$\sigma_{{\rm{AOA}},l}^{2}$. The AOA measurements in (7) can be represented by
a vector form

${\bm{r}}_{\rm{AOA}}=\bm{f}_{AOA}(\bm{\psi})+\bm{n}_{{\rm{AOA}},l},$ (8)

where ${\bm{r}}_{\rm{AOA}}$, ${\bm{n}}_{\rm{AOA}}$, and
$\bm{f}_{AOA}(\bm{\psi})$ are respectively defined by

$\begin{split}{\bm{r}}_{\rm{AOA}}&=\left[r_{{\rm{AOA}},1},r_{{\rm{AOA}},2},\ldots,r_{{\rm{AOA}},L}\right]^{T},\\\
{\bm{n}}_{\rm{AOA}}&=\left[n_{{\rm{AOA}},1},n_{{\rm{AOA}},2},\ldots,n_{{\rm{AOA}},L}\right]^{T},\\\
\bm{f}_{AOA}(\bm{\psi})&=\left[\tan^{-1}\left(\frac{y_{1}-y_{t}}{x_{1}-x_{t}}\right),\ldots,\tan^{-1}\left(\frac{y_{L}-y_{t}}{x_{L}-x_{t}}\right)\right]^{T}.\end{split}$
(9)

###  III-C Analog Beamforming and Antenna Radiation Pattern

Assuming that the AOA of the channel between the BS at location
$\bm{\psi}_{l}$ and its serving user at location $\bm{\psi}_{t}$ is
$\theta_{\bm{\psi}_{l}}$, the beamforming vector is given by

$\bm{w}_{\bm{\psi}_{l}}=\bm{a}_{t}(\theta_{\bm{\psi}_{l}}),$ (10)

which means that the BS should align the beam direction exactly with the
propagation channel to obtain the maximum power gain. However, the beam
direction cannot always align with the transmit signal. Hence, we consider the
single main-lobe and single side-lobe at antennas of both BS and mobile user,
and all lobes are approximated by a flat-top antenna pattern[26]. That is, the
single main-lobe with beam-width $\theta_{1}$ has antenna gain $G_{1}$ and
each side lobe with identical beam-width $\theta_{2}$ has antenna gain
$G_{2}$. We assume that the power spectrum density (PSD) of the main-lobe and
side-lobe at a distance $r$ are denoted as $P_{m}$ and $P_{s}$. Hence, the
total transmit power $P_{T}$ consists of the main-lobe and side-lobe radiation
powers, which is given by [26]

$P_{T}=P_{m}2\pi r^{2}\left[1-\cos\frac{\theta_{1}}{2}\right]+N_{t}P_{s}2\pi
r^{2}\left[1-\cos\frac{\theta_{2}}{2}\right],$ (11)

where $P_{m}=G_{1}P_{T}/4\pi r^{2}$ and $P_{s}=G_{2}P_{T}/4\pi r^{2}$. Let us
denote $k=G_{2}/G_{1}$ where $k\in(0,1)$, i.e., $G_{2}=kG_{1}$.

For the associated signal transmission, we assume perfect alignment where both
the BS and user utilize the main-lobe, achieving the squared gain $G_{1}^{2}$.
For the interfering signal, the interfering BSs are randomly distributed in
$[0,2\pi)$. The transmit antenna gain $G_{Tx}$ at the transmitter and the
receive antenna gain $G_{Rx}$ at the receiver are randomly chosen from a
discrete set $\left\\{G_{1},G_{2}\right\\}$ with probability
$p_{a}=\frac{\theta_{1}}{2\pi}$ and $p_{b}=1-p_{a}$, respectively. Let
$G_{TRx}=G_{Tx}G_{Rx}$, we have

$G_{TRx}=\left\\{\begin{array}[]{ll}G_{1}^{2},&p_{1}=p_{a}^{2}\\\
G_{1}G_{2},&p_{2}=2p_{a}p_{b}\\\
G_{2}^{2},&p_{3}=p_{b}^{2}.\end{array}\right.$ (12)

Based on the antenna radiation pattern, the product of small-scale fading gain
and beamforming gain of the BS at location $\bm{\psi}$ is computed as:

$|\bm{h}_{\bm{\psi}}\bm{w}_{\bm{\psi}}|^{2}=N_{t}|\rho_{\bm{\psi}}|^{2}G_{TRx}.$
(13)

##  IV Performance Analysis

In this section, we analyze the performance of AOA-based localization over a
mmWave network. To evaluate the localization performance, we will introduce
two metrics; $L$-localizability and AOA-based random CRLB.

###  IV-A L-Localizability

A target is localizable if there are a sufficient number of participating BSs
such that the localization procedure can be conducted. We introduce
L-Localizability, which is a probability to have $L$ localizable BSs within
the network [7]. Conventionally, commonly-accepted minimum values of $L$ for
the unambiguous operation of a localization system are $2$, $3$, $3$ and $3$
for AOA, TOA or RSS, and TDOA, respectively [4]. If we treat the interference
originated from outside of the circular disk with radius $R_{L}$ as a noise,
the signal-to-interference-plus-noise ratio (SINR) of the link from the $k$-th
BSs to the target can be expressed as a function of $L$ as

${\rm{SINR}}_{k}(L)=\frac{G_{1}^{2}|\rho_{\bm{\psi}_{k}}|^{2}r_{k}^{-\alpha}}{\sigma_{n}^{2}+J},$
(14)

where $\sigma_{n}^{2}=\frac{\sigma_{T}^{2}+\sigma_{{\rm{out}}}^{2}}{\beta
P_{t}N_{t}}$ is the normalized noise power, including the thermal noise power
$\sigma_{T}^{2}$ and interference power $\sigma_{{\rm{out}}}^{2}$ outside the
circular disk. The interference from nodes inside the disk, denoted by $J$, is
expressed as:

$J=\sum_{i=1,i\neq
k}^{L-1}a_{i}G_{TRx,i}|\rho_{\bm{\psi}_{i}}|^{2}||\bm{\psi}_{i}||^{-\alpha},$
(15)

where $a_{i}\in\\{0,1\\}$ is utilized to simulate the network load. The
probability of $a_{i}=1$ equals $q$ which is the probability of a BS inside
the disk to be activated. The $a_{i}$ represents whether the BS is activated
in the localization procedure and we assume that the activation probability
$P\left(a_{i}=1\right)=q$ is fixed throughout the localization procedure.

For a given ${\bm{\psi}}\in\mathbb{R}^{2}$, a mobile device is said to be
$L$-localizable if at least $L$ BSs participate in the localization procedure.
Let us denote the SINR threshold as $\tau$ and the maximum number of BSs that
can participate in the localization procedure as $\gamma$, defined as

$\gamma={\mathop{\arg\max}_{L}}\left(L\cdot\prod_{k=1}^{L}\mathbb{I}\left({\rm{SINR}}_{k}(l)\geq\tau\right)\right),$
(16)

where $\mathbb{I}(.)$ is the indicator function. Then, the $L$-localizability,
denoted by $P_{L}$, is derived as:

$P_{L}=P\left(\gamma\geq
L\right)=\mathbb{E}\left[\prod_{k=1}^{L}\mathbb{I}\left({\rm{SINR}}_{k}(l)\geq\tau\right)\right].$
(17)

Since the SINR from a BS farther from the mobile device is lower than that of
the closer BS, the following inequality holds:
$\mathbb{I}({\rm{SINR}}_{k}(L)\geq\tau)\geq\mathbb{I}({\rm{SINR}}_{l}(L)\geq\tau)$
for all $k\geq l\geq L$. Then, the $L$-localizability $P_{L}$ can be computed
as follows

$\begin{split}P_{L}&=\mathbb{E}\left[\mathbb{I}({\rm{SINR}}_{L}(L)\geq\tau\right]=P\left({\rm{SINR}}_{L}(L)\geq\tau\right)\\\
&=1-P\left(|\rho_{\psi_{L}}|^{2}\leq\frac{\tau\leavevmode\nobreak\
r_{L}^{\alpha}}{G_{1}^{2}}\left(\sigma_{n}^{2}+J\right)\right)\\\
&\overset{a}{\simeq}1-\mathbb{E}_{r_{L}}\left[\left(1-e^{-\nu\frac{\tau}{G_{1}^{2}}r_{L}^{\alpha}\left(\sigma_{n}^{2}+J\right)}\right)^{M}\right]\\\
&\overset{b}{=}\mathbb{E}_{r_{L}}\left[\sum_{i=1}^{M}(-1)^{i+1}\binom{M}{i}e^{-s\sigma_{n}^{2}}\mathcal{L}_{I}(s)\right]\\\
&=\int_{0}^{\infty}f_{r_{L}}(r)\sum_{i=1}^{M}(-1)^{i+1}\binom{M}{i}e^{-s\sigma_{n}^{2}}\leavevmode\nobreak\
\mathcal{L}_{I}(s)dr\\\ \end{split}$ (18)

where $\nu=M(M!)^{-\frac{1}{M}}$, $s=i\nu\frac{\tau}{G_{1}^{2}}r_{L}^{\alpha}$
and $\mathcal{L}_{I}(s)=\mathbb{E}_{I}[e^{-sJ}]$ is the Laplace transform of
the interference. Step $(a)$ follows by the Alzer’s inequality and $(b)$ is
obtained based on the binomial expansion. The Laplace transform of the
interference is [27]

$\begin{split}\mathcal{L}_{I}(s)&=\mathbb{E}_{I}[e^{-sJ}]\\\
&=\exp\bigg{[}-2\pi\lambda
q\underbrace{\int_{r_{1}}^{r_{L}}(1-\mathbb{E}_{g_{{\bm{\psi}}}}[e^{-sJ}]){r}dr}_{\triangleq\Lambda}\bigg{]},\\\
\end{split}$ (19)

where $g_{{\bm{\psi}}}=G_{TRx}|\rho_{{\bm{\psi}}}|^{2}$ represents the
combined effect of antenna gain and channel gain at the location
${\bm{\psi}}$. The term $\Lambda$ is computed as:

$\begin{split}\Lambda&=\int_{r_{1}}^{r_{L}}\left(1-\mathbb{E}_{g_{{\bm{\psi}}}}[e^{-sJ}]\right)rdr\\\
&=-\frac{1}{2}\Big{[}r_{L}^{2}-\delta
r_{L}^{2}\mathbb{E}_{g_{{\bm{\psi}}}}\left[E_{1+\delta}\left(sg_{{\bm{\psi}}}r_{L}^{-\alpha}\right)\right]\\\
&\quad-r_{1}^{2}+\delta
r_{1}^{2}\mathbb{E}_{g_{{\bm{\psi}}}}\left[E_{1+\delta}\left(sg_{{\bm{\psi}}}r_{1}^{-\alpha}\right)\right]\Big{]},\end{split}$
(20)

where $\delta=\frac{2}{\alpha}$ and $E_{1+\delta}(.)$ is the generalized
exponential integral [28]. The term
$\mathbb{E}_{g_{{\bm{\psi}}}}[E_{1+\delta}(sg_{{\bm{\psi}}}r^{-\alpha})]$ is
given by

$\begin{split}&\mathbb{E}_{g_{{\bm{\psi}}}}[E_{1+\delta}(sg_{{\bm{\psi}}}r^{-\alpha})]\\\
=&\frac{s^{\delta}\Gamma\left(-\delta\right)}{r^{2}}\left[\mathbb{E}_{g_{\psi}}\left[g_{\psi}^{\delta}\right]+\frac{\alpha}{2}-\sum_{p=1}^{\infty}\frac{(-s)^{p}\cdot\mathbb{E}_{g_{\psi}}\big{[}g_{\psi}^{\delta}\big{]}}{r^{\alpha
p}\cdot p!\cdot(p-\delta)}\right],\end{split}$ (21)

and the fractional moment of $g_{{\bm{\psi}}}$ is derived as:

$\begin{split}&\mathbb{E}_{g_{{{\psi}}}}[g_{{{\psi}}}^{\delta}]=\mathbb{E}_{|\rho_{{\bm{\psi}}}|^{2},G_{TRx}}\left[\left(|\rho_{{\bm{\psi}}}|^{2}G_{TRx}\right)^{\delta}\right]\\\
&=\frac{\Gamma(M+\delta)}{\Gamma(M)M^{\delta}}\cdot\mathbb{E}_{G_{TRx}}(G_{TRx}^{\delta})\\\
&=\frac{\Gamma(M+\delta)}{\Gamma(M)M^{\delta}}\cdot\left[G_{1}^{2\delta}p_{a}^{2}+2(G_{1}G_{2})^{\delta}p_{a}p_{b}+G_{2}^{2\delta}p_{b}^{2}\right].\end{split}$
(22)

Hence, the $L$-localizability can be numerically evaluated by substituting
(19)-(22) into (18).

###  IV-B Approximation of Cram$\bf\acute{\rm e}$r-Rao Lower Bound

We derive the AOA-based random CRLB using the Fisher information matrix (FIM),
denoted by $\bm{{\rm{I}}}(\bm{\psi})$ [4]

$\bm{{\rm{I}}}(\bm{\psi})=\left(\frac{\partial{\bm{f}}_{\rm{AOA}}(\bm{\psi})}{\partial\bm{\psi}}\right)^{T}\bm{C}_{\rm{AOA}}^{-1}\frac{\partial{\bm{f}}_{\rm{AOA}}(\bm{\psi})}{\partial\bm{\psi}},$
(23)

where $\bm{C}_{\rm{AOA}}^{-1}$ represents the inverse of the noise covariance
matrix and the derivative of ${\bm{f}}_{\rm{AOA}}(\bm{\psi})$ which is the
angle vector with respect to $\bm{\psi}$ are given by

$\begin{split}\bm{C}_{\rm{AOA}}^{-1}&=\text{diag}\left(\frac{1}{\sigma_{{\rm{AOA}},1}^{2}},\frac{1}{\sigma_{{\rm{AOA}},2}^{2}},\cdots,\frac{1}{\sigma_{{\rm{AOA}},L}^{2}}\right),\\\
\newline \\\
\frac{\partial{\bm{f}}_{\rm{AOA}}(\bm{\psi})}{\partial\bm{\psi}}&=-\begin{bmatrix}\frac{y-y_{1}}{(x-x_{1})^{2}+(y-y_{1})^{2}}&\frac{x-x_{1}}{(x-x_{1})^{2}+(y-y_{1})^{2}}\\\
\frac{y-y_{2}}{(x-x_{2})^{2}+(y-y_{2})^{2}}&\frac{x-x_{2}}{(x-x_{2})^{2}+(y-y_{2})^{2}}\\\
\vdots&\vdots\\\
\frac{y-y_{L}}{(x-x_{L})^{2}+(y-y_{L})^{2}}&\frac{x-x_{L}}{(x-x_{L})^{2}+(y-y_{L})^{2}}\end{bmatrix}.\end{split}$
(24)

Without loss of generality, $\sigma_{\rm{AOA}}$ is considered to be a known
quantity and assumed to be identical for each BSs, i.e.,
$\sigma_{{\rm{AOA}},1}=\sigma_{{\rm{AOA}},2}=\cdots=\sigma_{{\rm{AOA}},L}$[8].
The numerical value of $\sigma_{\rm{AOA}}$ depends on the average SNR of the
mmWave networks, denoted by $\rm{\overline{SNR}}$, as follows

${\rm{\overline{SNR}}}=\frac{G_{c}P_{t}}{N_{0}W_{\rm{TOT}}}$ (25)

where $G_{c}$ is the average channel gain, $N_{0}$ is the spectral density of
the WGN, and $W_{\rm{TOT}}$ is the total system bandwidth [29, 30]. Hence,
$\bm{{\rm{I}}}(\bm{\psi})$ is

$\begin{split}&\bm{{\rm{I}}}_{\rm{AOA}}(\bm{\psi})\\\
=&\sigma_{\rm{AOA}}^{2}\begin{bmatrix}\sum_{i=1}^{L}\frac{(y-y_{i})^{2}}{r_{i}^{4}}&-\sum_{i=1}^{L}\frac{(x-x_{i})(y-y_{i})}{r_{i}^{4}}\\\
-\sum_{i=1}^{L}\frac{(x-x_{i})(y-y_{i})}{r_{i}^{4}}&\sum_{i=1}^{L}\frac{(x-x_{i})^{2}}{r_{i}^{4}}\end{bmatrix}.\end{split}$
(26)

To assess the distribution of the CRLB, we introduce the position error bound
(PEB), which is the square root of the CRLB [31]. We will denote the PEB by
$S$ and its closed-form expression can be obtained by using (26)

$\begin{split}S&\triangleq\sqrt{\rm{CRLB}}=\sqrt{{\rm{tr}}(\bm{I}_{\rm{AOA}}^{-1}(\bm{\psi}))}=\sigma_{\rm{AOA}}\frac{\sqrt{L}}{\sqrt{Q_{1}-Q_{2}}},\end{split}$
(27)

where $Q_{1}$ and $Q_{2}$ are

$\begin{split}Q_{1}&=\sum_{i=1}^{L}\frac{(y_{i}-y_{t})^{2}}{r_{i}^{4}}\sum_{j=1}^{L}\frac{(x_{j}-x_{t})^{2}}{r_{j}^{4}},\\\
Q_{2}&=\sum_{i=1}^{L}\frac{(x_{i}-x_{t})^{2}(y_{i}-y_{t})^{2}}{r_{i}^{8}}.\end{split}$
(28)

Since (27) and (28) are functions of $2L$ random variables, i.e.,
$\left(x_{i},y_{i}\right)$ for $1\leq i\leq L$, we need to simplify (28) using
its asymptotic bounds, which will enable us to characterize the distribution
of (27). In the following proposition, we derived a tight upper bound for
$Q_{1}-Q_{2}$ and through simulation, we verified that approximation error is
less than $5\%$ for $L\geq 8$.

######  Proposition 1.

The random variable $Q_{1}-Q_{2}$ from (27) can be upper bounded as follows

$Q_{1}-Q_{2}\leq\frac{1}{4}\left[\left(\sum_{i=1}^{L}\frac{1}{r_{i}^{2}}\right)^{2}-\sum_{i=1}^{L}\frac{1}{r_{i}^{4}}\right]$
(29)

###### Proof.

First, we derive the lower bound of $Q_{2}$ as follows

$\begin{split}Q_{2}&\overset{(a)}{\geq}\sum_{i=1}^{L}\frac{\frac{1}{4}[(x_{i}-x_{t})^{2}+(y_{i}-y_{t})^{2}]^{2}}{r_{i}^{8}}\overset{(b)}{=}\sum_{i=1}^{L}\frac{1}{4r_{i}^{4}},\end{split}$
(30)

where the inequality $(x_{i}-x_{t})^{2}+(y_{i}-y_{t})^{2}\geq
2(x_{i}-x_{t})(y_{i}-y_{t})$ is applied to step (a) and Cartesian coordinates
is converted to polar coordinate in step (b). As shown in Fig. 2, the polar
coordinate of $(x_{i},y_{i})$ is given by

$\begin{split}x_{i}-x_{t}=r_{i}\cos\left(\theta_{i}\right),\quad
y_{i}-y_{t}=r_{i}\sin\left(\theta_{i}\right).\end{split}$ (31)

Next, we derive the upper bound of $Q_{1}$

$\begin{split}Q_{1}&=\sum_{i=1}^{L}\frac{(y_{i}-y_{t})^{2}}{r_{i}^{4}}\sum_{j=1}^{L}\frac{(x_{j}-x_{t})^{2}}{r_{j}^{4}}\\\
&=\sum_{i=1}^{L}\frac{\sin^{2}\left(\theta_{i}\right)}{r_{i}^{2}}\sum_{j=1}^{L}\frac{\cos^{2}\left(\theta_{j}\right)}{r_{j}^{2}},\end{split}$
(32)

where we will maximize $Q_{1}$ with respect to the phase $\\{\theta_{i}\\}$
for a given distance $\\{\theta_{i}\\}$. Then, (32) can be expressed as

$\begin{split}Q_{1}&=\sum_{i=1}^{L}\frac{\sin^{2}\left(\theta_{i}\right)}{r_{i}^{2}}\sum_{j=1}^{L}\frac{1-\sin^{2}\left(\theta_{j}\right)}{r_{j}}=\xi\left(\sum_{j=1}^{L}\frac{1}{r_{j}^{2}}-\xi\right),\end{split}$
(33)

where we denote
$\xi\triangleq\sum_{i=1}^{L}\frac{\sin^{2}\left(\theta_{i}\right)}{r_{i}^{2}}$.
The first order derivative of $Q_{1}$ is zero when
$\xi^{\ast}=\frac{1}{2}\sum_{i=1}^{L}\frac{1}{r_{i}^{2}}$ and the second order
derivative of $Q_{1}$ has a negative value at $\xi^{\ast}$ as follows

$\begin{split}\frac{\partial
Q_{1}}{\partial\xi}&=\sum_{i=1}^{L}\frac{1}{r_{i}^{2}}-2\xi=0\leavevmode\nobreak\
\Rightarrow\leavevmode\nobreak\
\xi^{\ast}=\frac{1}{2}\sum_{i=1}^{L}\frac{1}{r_{i}^{2}},\\\
\frac{\partial^{2}Q_{1}}{\partial\xi^{2}}&=-2<0.\end{split}$ (34)

Hence, the upper bound of $Q_{1}$ is given by

$\begin{split}Q_{1}\leq\max_{\\{\theta_{i}\\}}Q_{1}\bigg{|}_{\xi=\xi^{\ast}}=\left(\frac{1}{2}\sum_{i=1}^{L}\frac{1}{r_{i}^{2}}\right)^{2}.\end{split}$
(35)

We obtain (29) by (30) and (35). This completes the proof. ∎

Based on Proposition 1, the PEB $S$ is lower bounded by

$\begin{split}S&\geq\frac{2\sigma_{\rm{AOA}}\cdot\sqrt{L}}{\sqrt{\left(\sum_{i=1}^{L}\frac{1}{r_{i}^{2}}\right)^{2}-\sum_{i=1}^{L}\frac{1}{r_{i}^{4}}}}=\frac{2\sigma_{\rm{AOA}}\cdot\sqrt{L}}{\sqrt{\sum\limits_{\begin{subarray}{c}\scriptstyle
i,j=1\\\ \scriptstyle i\neq
j\end{subarray}}^{L}\frac{1}{r_{i}^{2}r_{j}^{2}}}}.\end{split}$ (36)

In the following assumption, we introduced an approximation of (36), which
provides a tractable asymptotic bound of $S$. Through simulation, we justified
the approximation accuracy.

######  Assumption 1.

Assume that the link distances are sorted in an ascending order, i.e.,
$R=\left[r_{1},\cdots,r_{L}\right]$ and $r_{1}\leq r_{2}\leq\cdots\leq r_{L}$.
The denominator of (36) can be approximated as follows

$D\triangleq\sum\limits_{\begin{subarray}{c}\scriptstyle i,j=1\\\ \scriptstyle
i\neq
j\end{subarray}}^{L}\frac{1}{r_{i}^{2}r_{j}^{2}}\approx\frac{L(L-1)}{r_{\lceil
L/4\rceil}^{4}},$ (37)

where $r_{\lceil L/4\rceil}$ is the $\lceil L/4\rceil$-th link distance in the
ordered set $R=\left[r_{1},\cdots,r_{L}\right]$ and $L$ is the number of
participating BSs.

######  Remark 1.

We validated (37) through simulation, where we repeated the realization of the
anchor nodes $10$ million times. Since the set $R$ is sorted, the term $D$ in
(37) is bounded by

$\begin{split}\frac{L\left(L-1\right)}{r_{L}^{4}}\leq\sum\limits_{\begin{subarray}{c}\scriptstyle
i,j=1\\\ \scriptstyle i\neq
j\end{subarray}}^{L}\frac{1}{r_{i}^{2}r_{j}^{2}}\leq\frac{L\left(L-1\right)}{r_{1}^{4}}.\end{split}$
(38)

We attempt to find the $k$-th term $r_{k}$ in set $R$ that provides the most
accurate approximation to $D$. To solve this problem, we used heuristic
approach and evaluated the mutual information between $D$ and the random
variable $r_{k}$ for a given $L$ as follows

$\begin{split}\min_{1\leq k\leq
L}\mathbb{E}\left[\bigg{\lvert}D-\frac{L(L-1)}{r_{k}^{4}}\bigg{\rvert}^{2}\right]\leavevmode\nobreak\
\Leftrightarrow\leavevmode\nobreak\ \max_{1\leq k\leq
L}I(D;r_{k}|L=l),\end{split}$ (39)

where the mutual information conditioned on $L$ is defined as

$I\left(D;r_{k}|L=l\right)=h\left(D|L=l\right)-h\left(D|r_{k},L=l\right),$
(40)

and the differential entropies are given by

$\begin{split}h(D|L=l)&=-\sum\limits_{d\in\rm{D}}f_{D}(d|\mathit{l})\log_{2}{f_{D}(d|\mathit{l})},\\\
h(D|r_{k},L=l)&=-\sum\limits_{\begin{subarray}{c}r_{k}\in R_{k},\\\
d\in\rm{D}\end{subarray}}f_{D;r_{k}}(d|r,l)\log_{2}{f_{D}(d|r,l)},\end{split}$
(41)

where $R_{k}$ and $\rm{D}$ are the supports of $r_{k}$ and $d$,
respectively[32]. This approach, which was motivated by [33], can search for
the $r_{l}$ that contains the most information of $D$. Through an extensive
simulation across a range of $L$, we observed that the $\lceil L/4\rceil$-th
distance maximizes the mutual information as illustrated in Fig. 3, which
justifies Assumption 1, and thus we can use the $\lceil L/4\rceil$-th distance
to approximate $D$.

Fig. 3: Impact of distance selection on mutual information

Fig. 4: Probability of $K^{\prime}-\sigma_{K}\leq K\leq K^{\prime}+\sigma_{K}$

Fig. 5: Original CRLB compared with approximate CRLB

Based on (36) and (37), we can approximate $S$ by

$S\approx\frac{2\sigma_{\rm{AOA}}}{\sqrt{L-1}}\leavevmode\nobreak\ r_{\lceil
L/4\rceil}^{2},$ (42)

where $S$ is a function of $r_{\lceil L/4\rceil}$. In the following
proposition, we derived the distribution of $S$ using order statistic.

######  Proposition 2.

Assume that the number of participating BSs $L$, the variance of the range
error $\sigma_{\rm{AOA}}$, and the link distance to the closest node $r_{1}$
and furthest node $r_{L}$ are known. Then, the CDF of PEB $S$ is given by

$\begin{split}F_{S}\left(s|L,\sigma_{\rm{AOA}}\right)=F_{r_{\lceil
L/4\rceil}}\left[\sqrt{\frac{s}{2}\cdot\frac{\sqrt{L-1}}{\sigma_{\rm{AOA}}}}\leavevmode\nobreak\
\bigg{|}L,\sigma_{\rm{AOA}}\right],\end{split}$ (43)

where $F_{r_{n}}\left(r\right)$ is the CDF of the $n$-th order statistic.

###### Proof.

First, the PDF of the $n$-th order statistic $f_{r_{n}}(r)$ is [34]

$\begin{split}f_{r_{n}}(r)=Lf_{r_{l}}(r)\binom{L-1}{n-1}F_{r_{l}}(r)^{n-1}\left(1-F_{r_{l}}(r)\right)^{L-n},\end{split}$
(44)

where $f_{r_{l}}(r)$ and $F_{r_{l}}(r)$ are given in (2). The CDF
$F_{r_{n}}\left(r\right)$ can be derived by integrating (44) as follows

$\begin{split}F_{r_{n}}(r)&=\int_{0}^{r_{L}}f_{r_{n}}(r)dr\\\
&=\sum_{j=n}^{L}\binom{L}{j}F_{r_{l}}(r)^{j}\left(1-F_{r_{l}}(r)\right)^{L-j}\\\
&=\sum_{j=n}^{L}\binom{L}{j}\left(\frac{r^{2}}{r_{L}^{2}-r_{1}^{2}}\right)^{j}\left(1-\frac{r^{2}}{r_{L}^{2}-r_{1}^{2}}\right)^{L-j}.\end{split}$
(45)

Hence, the CDF of $S$, denoted by $F_{S}(s|L,\sigma_{aoa})=P[S\leq
s|L,\sigma_{aoa}]$ is readily computed as

$\begin{split}F_{S}\left(s|L,\sigma_{\rm{AOA}}\right)&=P\left[r_{n}\leq\sqrt{\frac{s}{2}\frac{\sqrt{L-1}}{\sigma_{\rm{AOA}}}}\bigg{|}L,\sigma_{\rm{AOA}}\right],\end{split}$
(46)

where the PDF of $S$ can be computed by differentiating (46). This completes
the proof. ∎

######  Remark 2.

We evaluated the approximation accuracy of (36) and (42) through Monte Carlo
simulation. Let us denote

$\begin{split}K=&\sum_{i=1}^{L}\frac{\sin^{2}\theta_{i}}{r_{i}^{2}}\sum_{j=1}^{L}\frac{\cos^{2}\theta_{j}}{r_{j}^{2}},\quad
K^{\prime}=\frac{1}{4}\left(\sum_{i=1}^{L}\frac{1}{r_{i}^{2}}\right)^{2},\end{split}$
(47)

where $K$ is equal to $Q_{1}$ in proposition 1 and $K^{\prime}$ represents the
upper bound of $Q_{1}$ in (35). We utilized Monte Carlo simulation of $10$
million realizations to compute the empirical distribution of $K$ and
determine the value of $P\left[K^{\prime}-\sigma_{K}\leq K\leq
K^{\prime}+\sigma_{K}\right]$, where the $\sigma_{K}$ is the standard
deviation of $K$. Fig. 5 shows the probability
$P\left[K^{\prime}-\sigma_{K}\leq K\leq K^{\prime}+\sigma_{K}\right]$ versus a
range of $L$. It is observed that $K^{\prime}$ can approximate $Q$ with high
accuracy. For $L\geq 10$, the approximation accuracy is above 96$\%$.

Furthermore, we compared the CRLB computed by using (27), (36), (42), the 1-st
and the L-th ordered distance in Fig. 5. It is observed that the
approximations of CRLB using the $L$-th and $1$-st distances cannot approach
the original CRLB. However, the asymptotic bound using (36) and the
approximation based on (42) closely match the original CRLB curve, which
justifies Proposition 1 and Assumption 1.

##  V Simulation Results

Fig. 6: Impact of the network load on $L$-localizability when $\alpha=4$,
$N_{t}=64$ and $M=5$

Fig. 7: Impact of path-loss on $L$-localizability when $\alpha=4$, $N_{t}=64$
and $q=0.75$

Fig. 8: Impact of Nakagami fading parameter on $L$-localizability when
$\alpha=2.1$, $N_{t}=64$ and $q=0.75$

Fig. 9: Impact of number of BSs on the distribution of $S$ when $\alpha=2$,
$N_{t}=64$, $M=5$ and $q=0.75$

Fig. 10: Impact of $M$ ($M=3,5,7$) on the distribution of $S$ when $\alpha=2$,
$N_{t}=64$, $L=5$, $q=0.75$ and the impact of $N_{t}$ ($N_{t}=32,64,128$) when
$\alpha=2$, $M=1$, $L=5$ and $q=0.75$

Fig. 11: Impact of path-loss on the distribution of $S$ when $L=5$,
$N_{t}=64$, $M=5$ and $q=0.75$

In this section, we evaluate the $L$-localizability and random AOA-based CRLB
for mmWave networks, compare the simulation results to numerical results, and
investigate the effect of network parameters on the localization performance.
We used MATLAB to randomly simulate a realization of the node deployment
$1\times 10^{6}$ times. It is assumed that the BSs are randomly distributed by
a homogeneous PPP with node density $\lambda=2/\sqrt{3}\times 500^{2}m^{2}$,
bandwidth $W_{\rm{TOT}}=1$ GHz, transmit power $P_{T}=1$ Watt, antenna spacing
$d=\lambda_{w}/4$, path-loss intercept
$\beta=\left(\lambda_{w}/4\pi\right)^{2}$, and main-lobe gain $G_{1}=1$ and
side-lobe gain $G_{2}=0.2$ with its associate probability $p_{a}=0.4$ and
$p_{b}=0.6$, respectively. Since the NLOS interference is ignored in our
model, we choose a $\sigma_{\rm{AOA}}$ that accounts for an angular spread
under NLOS conditions during simulation.

###  V-A $L$-localizability Analysis

In Figs. 11-11, we investigate how the network parameters, including network
loads, path-loss exponent and Nakagami fading parameter, affect the
performance of $L$-localizability. Fig. 11 compares the $L$-localizability
$P_{L}$ versus the SINR threshold for different network loads $q$. The
simulation results are plotted in dotted curves, where as the analytical
results are represented by solid curves with a marker. All of the numerical
results indicate that the analytical results accurately match the simulation
results, justifying the analytical derivation. We observed that increasing the
network load leads to a decrease in $P_{L}$. It means that network design
should be optimized so that there is a sufficient number of BSs to meet the
localization requirement. Fig. 11 demonstrates the impact of path-loss on the
$L$-localizability. As the path-loss exponent increases, the transmitted power
across the mmWave link will significantly decline, causing a significant drop
in $P_{L}$. In Fig. 11, we observe the impact of Nakagami fading parameter $M$
on $P_{L}$. Since the Nakagami channel becomes deterministic as the $M$
parameter increases, the $L$-localizability escalates with higher $M$ values.

###  V-B Random AOA-based CRLB Analysis

In Figs. 11-11, we evaluate the distribution of $S$ for various network
parameter configurations. Since the approximation of CRLB using $r_{\lceil
L/4\rceil}$ provides an accurate approximation to the original CRLB, we used
the approximation based on the $\lceil L/4\rceil$-th distance across Figs.
11-11. In Fig. 11, we examine the impact of the number of participating BSs
$L$ on the distribution of $S$. This is accomplished by varying the number of
activated BSs transmitting during a localization procedure. It is observed
that the value of $P[S\leq abscissa]$ increases for a larger $L$. Since the
localization error reduces as the number of BSs increases, a network designer
looking to improve the localization accuracy may aim to optimize the network
environment to ensure a sufficient number of BSs participate in the
localization procedure.

Fig. 11 compares the localization performance for various Nakagami fading
parameter $M$ and the number of antenna elements $N_{t}$. It is observed that
increasing $M$ parameter escalates $P[S\leq abscissa]$, which improves the
localization performance. Furthermore, we demonstrate how the number of
antenna elements $N_{t}$ affects the localization performance. As the number
of antenna elements increases, the normalized noise power
$\sigma_{n}^{2}=\frac{\sigma_{T}^{2}+\sigma_{{\rm{out}}}^{2}}{\beta
P_{t}N_{t}}$ will be reduced, which leads to an increase of $P[S\leq
abscissa]$. This indicates that the localization performance can be enhanced
by adding more antenna elements in the BSs, which raises the implementation
cost for each BS. Hence, the network designer should find an optimum trade-off
between choosing a suitable number of antennas in the BS and enhancing the
localization performance. Fig. 11 shows the impact of path-loss on the
performance of the mmWave-based localization systems. As the path-loss
exponent increases, the value of $P[S\leq abscissa]$ decline, which is a
similar pattern to Fig. 11.

##  VI Conclusion

This paper presents $L$-localizability and random AOA-based CRLB for mmWave
wireless network, where we used stochastic geometry to account for all
possible positioning scenarios. We derived the $L$-localizability and random
CRLB for AOA localization while considering the flat-top antenna radiation
pattern and Nakagami fading. We provided numerical results to validate the
analytical derivation and investigated the impact of various network
parameters, e.g., network load, path-loss, fading parameters, number of BSs,
number of antenna elements, on the localization performance. The analytical
framework developed in this paper offers an accurate tool to evaluate the
localization performance of mmWave wireless networks, without relying on
numerical simulation. The network operators can use the asymptotic bounds to
optimize the network parameters and find the best deployment of the BSs to
ensure the localization performance. In our future work, we will apply the
approximation method to evaluate the performances of TOA, TDOA and RSS based
localization and investigate the impact of various channel models.

## References

  * [1] F. Khelifi, A. Bradai, A. Benslimane, P. Rawat, M. Atri, "A Survey of Localization Systems in Internet of Things", _Mobile Network and Application_ , pp761–785, 2019.
  * [2] W. Roh, J. Seol, J. Park, B. Lee, J. Lee, Y. Kim, J. Cho, K. Cheun, F. Aryanfar, "Millimeter-wave beamforming as an enabling technology for 5G cellular communications: Theoretical feasibility and prototype results," _IEEE Communications Magazine_ , vol. 52, no. 2, pp. 106-113, Feb. 2014.
  * [3] A. Alkhateeb, S. Alex, P. Varkey, Y. Li, Q. Qu and D. Tujkovic, "Deep Learning Coordinated Beamforming for Highly-Mobile Millimeter Wave Systems," _IEEE Access_ , vol. 6, pp. 37328-37348, 2018.
  * [4] H. C. So, "Source localization: algorithms and analysis", _Handbook of Position Location: Theory, Practice and Advances_ , Chapter 3, S.A.Zekavat and M.Buehrer, Eds., Wiley-IEEE Press, 2019.
  * [5] M. Haenggi, "Stochastic Geometry for Wireless Networks," Cambridge, U.K.: Cambridge Univ. Press, 2013.
  * [6] Y. J. Chun, S. L. Cotton, H. S. Dhillon, F. J. Lopez-Martinez, J. F. Paris and S. K. Yoo, "A Comprehensive Analysis of 5G Heterogeneous Cellular Systems Operating Over $\kappa$–$\mu$ Shadowed Fading Channels," in _IEEE Transactions on Wireless Communications_ , vol. 16, no. 11, pp. 6995-7010, Nov. 2017.
  * [7] J. Schloemann, H. S. Dhillon and R. M. Buehrer, "Toward a Tractable Analysis of Localization Fundamentals in Cellular Networks," _IEEE Transactions on Wireless Communications_ , vol. 15, no. 3, pp. 1768-1782, March. 2016.
  * [8] C. E. O’Lone, H. S. Dhillon and R. M. Buehrer, "A Statistical Characterization of Localization Performance in Wireless Networks," _IEEE Transactions on Wireless Communications_ , vol. 17, no. 9, pp. 5841-5856, Sept. 2018.
  * [9] J. Khalife, C. Sevinç and Z. M. Kassas, "Performance Evaluation of TOA Positioning in Asynchronous Cellular Networks Using Stochastic Geometry Models," _IEEE Wireless Communications Letters_ , May. 2020.
  * [10] H. Elsawy, W. Dai, M. Alouini and M. Z. Win, "Base Station Ordering for Emergency Call Localization in Ultra-Dense Cellular Networks," _IEEE Access_ , vol. 6, pp. 301-315, 2018.
  * [11] K. Radnosrati, G. Hendeby, C. Fritsche, F. Gunnarsson and F. Gustafsson, "Performance of OTDOA positioning in narrowband IoT systems," in _2017 IEEE 28th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC)_ , Montreal, Canada, pp. 1-7, 2017.
  * [12] J. He and H. C. So, "A Hybrid TDOA-Fingerprinting-Based Localization System for LTE Network," in _IEEE Sensors Journal_ , vol. 20, no. 22, pp. 13653-13665, Nov. 2020.
  * [13] A. Pin, R. Rinaldo, A. Tonello, C. Marshall, M. Driusso, A. Biason, "LTE ranging measurement using uplink opportunistic signals and the SAGE algorithm," in _2019 27th European Signal Processing Conference (EUSIPCO)_ , A Coruna, Spain, pp. 1-5, 2019.
  * [14] L. Ma, N. Jin, Y. Cui and Y. Xu, "LTE user equipment RSRP difference elimination method using multidimensional scaling for LTE fingerprint-based positioning system," in _2017 IEEE International Conference on Communications (ICC)_ , Paris, France, pp. 1-6, 2017.
  * [15] G. Çelik, H. Çelebi and G. Tuna, "A novel RSRP-based E-CID positioning for LTE networks," in _2017 13th International Wireless Communications and Mobile Computing Conference (IWCMC)_ , Valencia, Spain pp. 1689-1692, 2017.
  * [16] F. Lemic, J. Martin, C. Yarp, D. Chan, V. Handziski, R. Brodersen, G. Fettweis, A. Wolisz, J. Wawrzynek, "Localization as a feature of mmWave communication," _2016 International Wireless Communications and Mobile Computing Conference (IWCMC)_ , Paphos, 2016, pp. 1033-1038.
  * [17] K. Pahlavan, "Indoor geolocation science and technology," _Communications Magazine, IEEE,_ vol. 40, no. 2, pp. 112–118, 2002.
  * [18] F. Wen, H. Wymeersch, B. Peng, W. P. Tay, H. C. So, and D. Yang, "A survey on 5G massive MIMO localization," _Digit. Signal Process,_ 2019\.
  * [19] H. Wang, C. Wang, T. Zheng and T. Q. S. Quek, "Impact of Artificial Noise on Cellular Networks: A Stochastic Geometry Approach," in _IEEE Transactions on Wireless Communications_ , vol. 15, no. 11, pp. 7390-7404, Nov. 2016.
  * [20] B. Huang, T. Li, B. D. O. Anderson and C. Yu, "On the performance limit of sensor localization," _2011 50th IEEE Conference on Decision and Control and European Control Conference_ , Orlando, FL, 2011, pp. 7870-7875.
  * [21] D. Moltchanov, "Distance distributions in random networks," _Ad Hoc Networks_ , vol. 10, no. 6, pp. 1146-1166, Aug. 2012.
  * [22] S. Srinivasa and M. Haenggi, “Distance distributions in finite uniformly random networks: Theory and applications,” _IEEE Trans. on Vehicular Technology,_ vol. 59, no. 2, pp. 940–949, 201
  * [23] M. R. Akdeniz, Y. Liu, M. K. Samimi, S. Sun, S. Rangan, T. S. Rappaport, E. Erkip, "Millimeter Wave Channel Modeling and Cellular Capacity Evaluation," _IEEE Journal on Selected Areas in Communications_ , vol. 32, no. 6, pp. 1164-1179, June. 2014.
  * [24] G. Lee, Y. Sung and J. Seo, "Randomly-Directional Beamforming in Millimeter-Wave Multiuser MISO Downlink," _IEEE Transactions on Wireless Communications_ , vol. 15, no. 2, pp. 1086-1100, Feb. 2016.
  * [25] G. Lee, Y. Sung and M. Kountouris, "On the Performance of Random Beamforming in Sparse Millimeter Wave Channels," _IEEE Journal of Selected Topics in Signal Processing_ , vol. 10, no. 3, pp. 560-575, April. 2016.
  * [26] Y. Wu and C. Han, "Interference and Coverage Analysis for Indoor Terahertz Wireless Local Area Networks," _2019 IEEE Globecom Workshops (GC Wkshps), Waikoloa,_ HI, USA, 2019, pp. 1-6.
  * [27] J. G. Andrews, F. Baccelli, and R. K. Ganti, "A tractable approach to coverage and rate in cellular networks," _IEEE Transactions on Wireless Communications_ , vol. 59, no. 11, pp. 3122–3134, Nov. 2011.
  * [28] D. Zwillinger, Table of Integrals, Series, and Products. Amsterdam, The Netherlands: Elsevier, 2014.
  * [29] M. Giordani, M. Mezzavilla, A. Dhananjay, S. Rangan and M. Zorzi, "Channel Dynamics and SNR Tracking in Millimeter Wave Cellular Systems," _22th European Wireless Conference,_ Oulu, Finland, 2016, pp. 1-8.
  * [30] R. Koirala, B. Denis, D. Dardari and B. Uguen, "Localization bound based beamforming optimization for multicarrier mmWave MIMO," _2017 14th Workshop on Positioning, Navigation and Communications (WPNC),_ Bremen, 2017, pp. 1-6.
  * [31] D. B. Jourdan, D. Dardari, and M. Z. Win, "Position error bound for UWB localization in dense cluttered environments," in Proc. _IEEE Int. Conf. Commun.,_ Istanbul, Turkey, Jun. 2006, pp. 3705–3710.
  * [32] T. M. Cover and J. A. Thomas, Elements of Information Theory. New York, NY, USA: Wiley, 1991, chapter. 2–9.
  * [33] J. Schloemann, H. S. Dhillon and R. M. Buehrer, "A Tractable Metric for Evaluating Base Station Geometries in Cellular Network Localization," in IEEE Wireless Communications Letters, vol. 5, no. 2, pp. 140-143, April 2016.
  * [34] H. A. David and H. N. Nagaraja, Order Statistics. Hoboken, NJ: John Wiley and Sons, Inc., 3rd ed. 2003.
  * [35] H. Elshaer, M. N. Kulkarni, F. Boccardi, J. G. Andrews and M. Dohler, "Downlink and Uplink Cell Association With Traditional Macrocells and Millimeter Wave Small Cells," in _IEEE Transactions on Wireless Communications,_ vol. 15, no. 9, pp. 6244-6258, Sept. 2016.
  * [36] D. B. Jourdan and N. Roy, "Optimal sensor placement for agent localization," in _Proc. IEEE/ION Position, Location, Navigat. Symp.,_ Coronado, CA, USA, Apr. 2006, pp. 128–139.
  * [37] C. Chang and A. Sahai, "Estimation bounds for localization," in _Proc. 1st Annu. IEEE Commun. Soc. Conf. Sensor Ad Hoc Commun. Netw.,_ Santa Clara, CA, USA, Oct. 2004, pp. 415–424.


# A further simplification of Tarski’s axioms of geometry

T. J. M. Makarios111mailto:tjm1983<EMAIL_ADDRESS>
###### Abstract

A slight modification to one of Tarski’s axioms of plane Euclidean geometry is
proposed. This modification allows another of the axioms to be omitted from
the set of axioms and proven as a theorem. This change to the system of axioms
simplifies the system as a whole, without sacrificing the useful modularity of
some of its axioms. The new system is shown to possess all of the known
independence properties of the system on which it was based; in addition,
another of the axioms is shown to be independent in the new system.

##  1 Background

Alfred Tarski’s axioms of geometry were first described in a course he gave at
the University of Warsaw in 1926–1927. Since then, they have undergone
numerous improvements, with some axioms modified, and other superfluous axioms
removed; for a history of the changes, see [TG99] (especially Section 2), or
for a summary, see Figure 2 in [Nar07].

The axioms rely on only one primitive notion — that of points — and two
primitive relations: betweenness and congruence. Congruence is denoted
$ab\equiv cd$, and can be interpreted as asserting that the line segment from
$a$ to $b$ is congruent to the line segment from $c$ to $d$. Betweenness is
denoted $\mathrm{B}abc$, and can be interpreted as asserting that $b$ lies on
the segment from $a$ to $c$ (and may be equal to $a$ or $c$).

The version of the axioms used in [SST83] (see pages 10–14) consists of ten
first-order axioms, together with either a first-order axiom schema, or a
single higher-order axiom. This version has been adopted in later
publications, such as [Mak12] (see Sections 2.3 and 2.4) and [Nar07] (see
Figure 3), and Victor Pambuccian has called it the “most polished form” of
Tarski’s axioms (see [Pam06], page 122).

This semi-canonical version of the system is the result of many
simplifications to the original system of twenty axioms plus one axiom schema.
At least one of these simplifications appears to have taken the form of a
slight alteration to one axiom in order to allow another axiom to be dropped
and subsequently proven as a theorem.

Specifically, in [Tar57] (see note 18), axiom (ix) is a version of what is
called the _axiom of Pasch_ , which states (modulo notational differences):

$\forall a,b,c,p,q.\;\mathrm{B}apc\wedge\mathrm{B}qcb\longrightarrow\exists
x.\;\mathrm{B}axq\wedge\mathrm{B}xpb$

In [Tar59], this has been replaced by axiom A9, which states (again, modulo
notational changes):

$\forall a,b,c,p,q.\;\exists
x.\;\mathrm{B}apc\wedge\mathrm{B}qcb\longrightarrow\mathrm{B}axq\wedge\mathrm{B}bpx$

The significant change between the two is the reversal of the order of points
in the final betweenness relation. They are easily shown to be equivalent
using the symmetry of betweenness, which states:

$\forall a,b,c.\;\mathrm{B}abc\longrightarrow\mathrm{B}cba$

The interesting thing is that in [Tar57], (1) is an axiom (axiom (iii)), but
in [Tar59], it has been removed from the list of axioms. Haragauri Gupta’s
proof of (1) (see [Gup65], Theorem 2.18) relies on the precise ordering of
points in the final betweenness relation in (1).

Also, Wolfram Schwabhäuser, Wanda Szmielew, and Alfred Tarski, on page 12 of
[SST83], draw attention to the ordering of points in their version of the
axiom of Pasch (labelled (• ‣ 2) in this paper), noting that it is important
until after the proof of (1) (which they call Satz 3.2). Again, their proof of
(1) (which is essentially the same as this paper’s proof of Lemma 4) relies on
the precise ordering of points in (• ‣ 2).

Therefore, although it does not appear to be explicitly acknowledged in the
published literature, it seems likely that the change from (1) to (1) was
necessary to allow the removal of (1) from the set of axioms. It may be the
case that (1) is a theorem even with (1), and that this was not known when it
was replaced by (1), or that it was known, but (1) allows a simpler proof.

In any case, it appears that Tarski was willing to reorder points in his
axioms to allow the simplification of the axiom system as a whole, either by
removing axioms or merely by simplifying proofs of theorems.

In the tradition of such simplifications, this paper presents one further
simplification of the axiom system; one of the axioms is slightly modified,
allowing another of the traditional axioms to be proven as a theorem, rather
than assumed as an axiom.

##  2 The axioms

Tarski’s axioms, as stated in [SST83], pages 10–14, are as follows. The names
are adopted from [Mak12] (Section 2.4), which provides some diagrams and
intuitive explanations for the axioms.

  * •

Reflexivity axiom for equidistance

$\forall a,b.\;ab\equiv ba$

  * •

Transitivity axiom for equidistance

$\forall a,b,p,q,r,s.\;ab\equiv pq\wedge ab\equiv rs\longrightarrow pq\equiv
rs$

  * •

Identity axiom for equidistance

$\forall a,b,c.\;ab\equiv cc\longrightarrow a=b$

  * •

Axiom of segment construction

$\forall a,b,c,q.\;\exists x.\;\mathrm{B}qax\wedge ax\equiv bc$

  * •

Five-segments axiom

$\displaystyle\forall a,b,c,d,a^{\prime},b^{\prime},c^{\prime},d^{\prime}.\;$
$\displaystyle{a\neq
b\wedge\mathrm{B}abc\wedge\mathrm{B}a^{\prime}b^{\prime}c^{\prime}}$
$\displaystyle\qquad\wedge ab\equiv a^{\prime}b^{\prime}\wedge bc\equiv
b^{\prime}c^{\prime}\wedge ad\equiv a^{\prime}d^{\prime}\wedge bd\equiv
b^{\prime}d^{\prime}$ $\displaystyle\longrightarrow cd\equiv
c^{\prime}d^{\prime}$ (FS)

  * •

Identity axiom for betweenness

$\forall a,b.\;\mathrm{B}aba\longrightarrow a=b$

  * •

Axiom of Pasch

$\forall a,b,c,p,q.\;\mathrm{B}apc\wedge\mathrm{B}bqc\longrightarrow\exists
x.\;\mathrm{B}pxb\wedge\mathrm{B}qxa$

  * •

Lower $2$-dimensional axiom

$\exists
a,b,c.\;\neg\mathrm{B}abc\wedge\neg\mathrm{B}bca\wedge\neg\mathrm{B}cab$

  * •

Upper $2$-dimensional axiom

$\forall a,b,c,p,q.\;p\neq q\wedge ap\equiv aq\wedge bp\equiv bq\wedge
cp\equiv cq\longrightarrow\mathrm{B}abc\vee\mathrm{B}bca\vee\mathrm{B}cab$

  * •

Euclidean axiom

$\forall a,b,c,d,t.\;\mathrm{B}adt\wedge\mathrm{B}bdc\wedge a\neq
d\longrightarrow\exists
x,y.\;\mathrm{B}abx\wedge\mathrm{B}acy\wedge\mathrm{B}xty$

  * •

Axiom of continuity

$\displaystyle\forall X,Y.\;$ $\displaystyle{(\exists a.\;\forall x,y.\;x\in
X\wedge y\in Y\longrightarrow\mathrm{B}axy)}$
$\displaystyle\longrightarrow(\exists b.\;\forall x,y.\;x\in X\wedge y\in
Y\longrightarrow\mathrm{B}xby)$ (Co)

This collection of eleven axioms, Tarski’s axioms of the continuous Euclidean
plane, will be denoted CE2. A similar collection of axioms, denoted
CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$, is obtained by removing (• ‣ 2)
from CE2 and replacing (FS) with

$\displaystyle\forall a,b,c,d,a^{\prime},b^{\prime},c^{\prime},d^{\prime}.\;$
$\displaystyle{a\neq
b\wedge\mathrm{B}abc\wedge\mathrm{B}a^{\prime}b^{\prime}c^{\prime}}$
$\displaystyle\qquad\wedge ab\equiv a^{\prime}b^{\prime}\wedge bc\equiv
b^{\prime}c^{\prime}\wedge ad\equiv a^{\prime}d^{\prime}\wedge bd\equiv
b^{\prime}d^{\prime}$ $\displaystyle\longrightarrow dc\equiv
c^{\prime}d^{\prime}$ (FS′)

The only difference between (FS) and (FS′) is the reversal of the first two
points in the last congruence relation.

This paper will show that CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$ is
equivalent to CE2, and will, in fact, show a stronger result — Theorem 7 —
about a smaller set of axioms.

One of the features of Tarski’s axiom system is its modularity: some texts
omit or delay the introduction of (Co) (see, for example, [Ehr97], page 61);
(• ‣ 2) can be replaced by another axiom in order to investigate hyperbolic
geometry, or omitted entirely, for absolute geometry (see [Pam02], pages
331–333); (• ‣ 2) and (• ‣ 2) can be replaced by other axioms that
characterize other dimensions (see [Tar59], footnote 5). For this reason, let
A denote the collection of axioms (• ‣ 2), (• ‣ 2), (• ‣ 2), (• ‣ 2), (FS), (•
‣ 2), and (• ‣ 2). These are Tarski’s axioms of absolute dimension-free
geometry without the axiom of continuity. Let A′ denote the collection of
axioms (• ‣ 2), (• ‣ 2), (• ‣ 2), (FS′), (• ‣ 2), and (• ‣ 2).

The stronger result that this paper shows is that A′ is equivalent to A. Thus,
the modularity of axioms (• ‣ 2), (• ‣ 2), (• ‣ 2), and (Co) is unaffected by
the proposed change to Tarski’s axiom system.

##  3 Proof of equivalence

######  Lemma 1.

If (• ‣ 2) and (• ‣ 2) hold, then given any points $a$ and $b$, we have
$ab\equiv ab$.

###### Proof.

Given $a$ and $b$, (• ‣ 2) lets us obtain a point $x$ such that $ax\equiv ab$.
Using this twice in (• ‣ 2) gives us $ab\equiv ab$. ∎

######  Lemma 2.

If (• ‣ 2) and (• ‣ 2) hold and $a$, $b$, $c$, and $d$ are points such that
$ab\equiv cd$, then $cd\equiv ab$.

###### Proof.

By Lemma 1, we have $ab\equiv ab$. Using $ab\equiv cd$ and $ab\equiv ab$, (• ‣
2) tells us that $cd\equiv ab$. ∎

######  Lemma 3.

If (• ‣ 2) and (• ‣ 2) hold, then given any points $a$ and $b$, we have
$\mathrm{B}abb$.

###### Proof.

Given $a$ and $b$, (• ‣ 2) lets us obtain a point $x$ such that
$\mathrm{B}abx$ and $bx\equiv bb$. Then (• ‣ 2) tells us that $b=x$, so
$\mathrm{B}abb$. ∎

######  Lemma 4.

(• ‣ 2), (• ‣ 2), (• ‣ 2), and (• ‣ 2) together imply (1).

###### Proof.

Suppose we are given points $a$, $b$, and $c$ such that $\mathrm{B}abc$. We
also have $\mathrm{B}bcc$, by Lemma 3. Then (• ‣ 2) lets us obtain a point $x$
such that $\mathrm{B}bxb$ and $\mathrm{B}cxa$. According to (• ‣ 2), the
former implies $b=x$, so the latter tells us that $\mathrm{B}cba$. ∎

######  Lemma 5.

A′ implies (• ‣ 2).

###### Proof.

Given arbitrary points $a$ and $b$, (• ‣ 2) lets us obtain a point $x$ such
that $\mathrm{B}bax$ and $ax\equiv ba$. We consider two cases: $x=a$ and
$x\neq a$.

If $x=a$, then $aa\equiv ba$. By Lemma 2, we have $ba\equiv aa$, so by (• ‣
2), we have $b=a$. Substituting this back into the congruence as necessary
gives us $ab\equiv ba$, as desired.

Suppose, on the other hand, that $x\neq a$. Lemma 4 and $\mathrm{B}bax$ tell
us that $\mathrm{B}xab$. Lemma 1 tells us that $xa\equiv xa$, $ab\equiv ab$,
and $aa\equiv aa$. We make the following substitutions in (FS′):
$a,a^{\prime}\mapsto x$; $b,b^{\prime},d,d^{\prime}\mapsto a$; and
$c,c^{\prime}\mapsto b$. Then all of the hypotheses of (FS′) are satisfied,
and its conclusion is that $ab\equiv ba$. ∎

######  Lemma 6.

If (• ‣ 2) and (• ‣ 2) hold, then (FS′) is equivalent to (FS).

###### Proof.

Because the hypotheses of (FS) and (FS′) are identical, we need only show that
their conclusions are equivalent.

(• ‣ 2) tells us that $cd\equiv dc$ and $dc\equiv cd$.

If $cd\equiv c^{\prime}d^{\prime}$, then $cd\equiv dc$ together with this fact
and (• ‣ 2) let us conclude that $dc\equiv c^{\prime}d^{\prime}$.

Similarly, if $dc\equiv c^{\prime}d^{\prime}$, then $dc\equiv cd$ together
with this fact and $\eqref{te}$ let us conclude that $cd\equiv
c^{\prime}d^{\prime}$.

Therefore (FS′) is equivalent to (FS). ∎

######  Theorem 7.

A′ is equivalent to A.

###### Proof.

By Lemmas 5 and 6, A′ implies (• ‣ 2) and (FS). A′ contains all of the other
axioms of A, so A′ implies A.

By Lemma 6, A implies (FS′), and it contains all of the other axioms of A′, so
A implies A′.

Therefore A′ is equivalent to A. ∎

As an immediate corollary, we have the following:

######  Corollary 8.

CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$ is equivalent to CE2. ∎

##  4 Independence results

The first part of Section 5 of [TG99] (see pages 199 and 200) concerns the
independence of Tarski’s axioms. One problem seen there is that the various
historical changes to Tarski’s axioms often force a reconsideration of
previously established independence results. This paper’s suggested
simplification of Tarski’s axioms is no exception, so this section aims to
establish which of the known independence results apply to the specific set of
axioms CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$.

Because CE2 and CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$ differ only in their
subsets A and A′, Theorem 7 tells us that the axioms in
CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$ but not in A′ are independent if and
only if they are independent in CE2. In fact, we can go further than this.

######  Theorem 9.

Suppose that (Ax) is an axiom of CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$
other than (• ‣ 2) or (FS′). If (Ax) is independent in CE2 then (Ax) is also
independent in CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$.

###### Proof.

Note that (Ax) is not (• ‣ 2), because this was explicitly excluded; nor is it
(• ‣ 2) or (FS), because these are not axioms of
CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$, from which (Ax) was chosen.
Therefore
$\textnormal{{{CE${}_{\mathnormal{\mathsf{2}}}$}}}\setminus\left\\{\textup{(Ax)}\right\\}$
contains (• ‣ 2), (• ‣ 2), and (FS), so by Lemma 6,
$\textnormal{{{CE${}_{\mathnormal{\mathsf{2}}}$}}}\setminus\left\\{\textup{(Ax)}\right\\}\vdash\eqref{fsp}$.

All of the axioms of CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$ other than
(FS′) are also axioms of CE2, so
$\textnormal{{{CE${}_{\mathnormal{\mathsf{2}}}$}}}\setminus\left\\{\textup{(Ax)}\right\\}\vdash\textnormal{{{CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$}}}\setminus\left\\{\textup{(Ax)}\right\\}$.
Therefore, if
$\textnormal{{{CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$}}}\setminus\left\\{\textup{(Ax)}\right\\}\vdash\textup{(Ax)}$,
then
$\textnormal{{{CE${}_{\mathnormal{\mathsf{2}}}$}}}\setminus\left\\{\textup{(Ax)}\right\\}\vdash\textup{(Ax)}$.
Taking the contrapositive of this statement, we see that if (Ax) is
independent in CE2 then it is independent in
CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$. ∎

This allows us to adopt almost all of the independence results known for CE2.

######  Corollary 10.

(• ‣ 2), (• ‣ 2), (• ‣ 2), (• ‣ 2), (• ‣ 2), and (Co) are each individually
independent in CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$.

###### Proof.

Schwabhäuser and his colleagues note the independence of each of these axioms
in CE2; see [SST83], page 26. ∎

The remaining independence result noted in [SST83] can also be adapted to
CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$:

######  Theorem 11.

(FS′) is independent in CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$.

###### Proof.

Schwabhäuser and his co-authors note the existence of a model $\mathcal{M}$
demonstrating the independence of (FS) in CE2; see [SST83], page 26. Because
$\mathcal{M}$ satisfies (• ‣ 2) and (• ‣ 2), but violates (FS), we can
conclude, using Lemma 6, that $\mathcal{M}$ also violates (FS′). $\mathcal{M}$
satisfies every other axiom of CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$,
because all such axioms are also axioms of CE2 (and are not equal to (FS));
therefore, $\mathcal{M}$ demonstrates the independence of (FS′) in
CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$. ∎

Because of the absence of (• ‣ 2) from
CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$, we can easily show the independence
of (• ‣ 2) in that axiom system:

######  Theorem 12.

(• ‣ 2) is independent in CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$.

###### Proof.

We proceed as is usual in independence proofs, by defining a model
$\mathcal{M}$ of every axiom of CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$
except (• ‣ 2). As in the real Cartesian plane (the standard model of CE2, and
hence of CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$), we take $\mathbb{R}^{2}$
to be the set of points, and define betweenness so that $\mathrm{B}abc$ if and
only if $b$ is a convex combination of $a$ and $c$. Departing from the
standard model, we define congruence so that $ab\equiv cd$ if and only if
$a=b$.

Because the real Cartesian plane is a model of
CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$, and $\mathcal{M}$ differs from the
real Cartesian plane only in its definition of congruence, we can conclude
that $\mathcal{M}$ is a model of all of the axioms of
CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$ that make no mention of congruence.
Those axioms are (• ‣ 2), (• ‣ 2), (• ‣ 2), (• ‣ 2), and (Co).

The definition of congruence ensures that $\mathcal{M}$ trivially satisfies (•
‣ 2).

Choosing $x=a$ ensures that (• ‣ 2) is satisfied.

The hypotheses of (FS′) include $a\neq b$ and $ab\equiv a^{\prime}b^{\prime}$,
which implies $a=b$; this contradiction in the hypotheses means that (FS′) is
vacuously true.

The hypotheses of (• ‣ 2) imply that $a=b=c=p$; it is always the case that
$\mathrm{B}ppp$, so (• ‣ 2) is satisfied.

Finally, in $\mathcal{M}$, it is the case that $(0,0)(0,0)\equiv(0,0)(0,1)$,
but not the case that $(0,0)(0,1)\equiv(0,0)(0,1)$, so $\mathcal{M}$ does not
satisfy (• ‣ 2).

Because $\mathcal{M}$ satisfies every axiom of
CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$ except (• ‣ 2), we can conclude that
(• ‣ 2) is independent in CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$. ∎

Notice that $\mathcal{M}$ in the proof of Theorem 12 also violates (• ‣ 2)
(because it is not the case that $(0,0)(0,1)\equiv(0,1)(0,0)$), so this model
would not demonstrate the independence of (• ‣ 2) in CE2, which is, as far as
the author is aware, still an open question.

We now have independence results for all of the axioms of
CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$ except (• ‣ 2) and (• ‣ 2). As far
as the author knows, the independence of these in CE2 is still an open
question (see also [TG99], pages 199 and 200), although there are independence
results relating to these axioms in other versions of Tarski’s axiom system.

Gupta shows the independence of (• ‣ 2) (his axiom A5; see [Gup65], pages 41
and 41a), but only in the context of a particular variant of Tarski’s axiom
system. This variant uses a weaker but more complicated form of the upper
$2$-dimensional axiom, Gupta’s A′12;222It seems that A′12 in Gupta’s thesis
ought to include $u\neq v$ among the hypotheses, as A12 does. Taken exactly as
it is printed, A′12 is violated by the real Cartesian plane whenever $x$, $y$,
and $z$ are any non-collinear points and $u=v$. his independence model for (•
‣ 2) also violates (• ‣ 2), which is trivially equivalent to his original
axiom A12.

Lesław Szczerba established the independence of a version of the axiom of
Pasch within a certain variant of Tarski’s axiom system (see [Szc70]). This
variant used, instead of (• ‣ 2), an axiom essentially asserting that any
three non-collinear points have a circumcentre.333There appears to be a
typographical error in the statement of this axiom in [Szc70] (page 492). His
axiom A8′ states (in our notation):  $\forall a,b,c.\;\exists
p.\;\neg(\mathrm{B}abc\vee\mathrm{B}bca\vee\mathrm{B}cab)\longrightarrow
ap\equiv bp\wedge bp\equiv cb$ It seems that the second congruence relation in
the consequent should state $bp\equiv cp$; see also [TG99], pages 199 and 184.

##  5 Conclusions

Although this paper has not answered the question of whether (• ‣ 2) is
independent in CE2, it has demonstrated that (• ‣ 2) is superfluous to
Tarski’s axioms of geometry. A slight modification to (FS) allows (• ‣ 2) to
be proven as a theorem, and therefore removed from the set of axioms. This
simplification of the axiom system (to
CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$) does not diminish its deductive
power or the important ways in which it exhibits modularity.

Besides removing one of the axioms not known to be independent in CE2,
CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$ allows an easy proof of the
independence of (• ‣ 2), which was also not known to be independent in CE2.
The two remaining independence questions for
CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$ are, as far as the author knows,
still open questions for CE2; furthermore, if either axiom is shown to be
independent in CE2, then Theorem 9 would immediately establish its
independence in CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$.

As well as trying to resolve these remaining independence questions, future
work might seek other slight modifications to the axioms that may allow even
known independent axioms to be dropped. That this may be possible can be seen
by considering Gupta’s fully independent version of Tarski’s axioms for plane
Euclidean geometry (see [Gup65], pages 41–41c).

His version had eleven axioms,444Strictly speaking, as he presented it, it had
infinitely many axioms, but if his axiom schema A′13 is replaced by a
comparable second-order axiom, then there are eleven axioms in total, and the
second-order axiom is shown to be independent by his example on page 41c. some
of which were deliberately made more complicated in order to allow easy proofs
of the independence of other axioms (see, for example, his note on the
independence of his axiom A7 on page 41b). CE2 already has simpler axioms than
Gupta’s system (which he used only for the demonstration that a fully
independent system is possible), but CE$\mathnormal{\mathsf{{}_{2}^{\prime}}}$
now shows that a reduction in the number of axioms is also possible, without
making any of them more complex, despite Gupta’s system being fully
independent.

## References

  * [Ehr97] Philip Ehrlich.  From completeness to Archimedean completeness: An essay in the foundations of Euclidean geometry.  Synthese, 110:57–76, 1997.  http://www.ohio.edu/people/ehrlich/FromCompletenessToArch.pdf.
  * [Gup65] Haragauri Narayan Gupta.  Contributions to the Axiomatic Foundations of Geometry.  PhD thesis, University of California, Berkeley, 1965.
  * [Mak12] Timothy James McKenzie Makarios.  A mechanical verification of the independence of Tarski’s Euclidean axiom.  Master’s thesis, Victoria University of Wellington, New Zealand, 2012\.  http://researcharchive.vuw.ac.nz/handle/10063/2315.
  * [Nar07] Julien Narboux.  Mechanical theorem proving in Tarski’s geometry.  In Francisco Botana and Tomas Recio, editors, Automated Deduction in Geometry, volume 4869 of Lecture Notes in Computer Science, pages 139–156. Springer Berlin / Heidelberg, 2007.
  * [Pam02] Victor Pambuccian.  Axiomatizations of hyperbolic geometry: A comparison based on language and quantifier type complexity.  Synthese, 133:331–341, 2002.
  * [Pam06] Victor Pambuccian.  Axiomatizations of hyperbolic and absolute geometries.  In András Prékopa and Emil Molnár, editors, Non-Euclidean Geometries, volume 581 of Mathematics and Its Applications, pages 119–153. Springer US, 2006.
  * [SST83] Wolfram Schwabhäuser, Wanda Szmielew, and Alfred Tarski.  Metamathematische Methoden in der Geometrie.  Springer-Verlag, 1983.
  * [Szc70] Lesław W. Szczerba.  Independence of Pasch’s axiom.  Bulletin de l’Academie Polonaise des Sciences, Série des Sciences Mathématiques, Astronomiques et Physiques, 18(8):491–498, 1970.
  * [Tar57] Alfred Tarski.  A decision method for elementary algebra and geometry.  Technical report, The RAND Corporation, 1957.  First published August 1948.
  * [Tar59] Alfred Tarski.  What is elementary geometry?  In Leon Henkin, Patrick Suppes, and Alfred Tarski, editors, The Axiomatic Method: with Special Reference to Geometry and Physics, pages 16–29. North-Holland Publishing Company, 1959.
  * [TG99] Alfred Tarski and Steven Givant.  Tarski’s system of geometry.  The Bulletin of Symbolic Logic, 5(2):175–214, June 1999.