---
address: |
     $^{*}$Institute of Computer Science, University of Goettingen\
    37077 Goettingen, Germany\
    hardyjonathan@example.com\
    hardyjonathan@example.com\
    $^{\dagger}$Robert Bosch Car Multimedia GmbH\
    31139 Hildesheim, Germany\
    hardyjonathan@example.com\
    hardyjonathan@example.com 
author:
- 'Simon Ollander$^{*\dagger} $, Friedrich-Wilhelm Bode$^{\dagger}$, Marcus Baum$^{*}$'
bibliography:
- 'IEEEabrv.bib'
- 'MyListOfPapersENC.bib'
title: 'Simulation-based Analysis of Multipath Delay Distributions in Urban Canyons'
---

Introduction
============

Global navigation satellite systems (GNSS) allow their users to estimate their position with high precision, almost world-wide in outdoor areas. Their applications include navigation for vehicles and pedestrians, and the Internet of Things. The main GNSS positioning error is multipath (MP) and non-line-of-sight (NLOS), caused by buildings reflecting and blocking the signals, as depicted in Fig. \[fig:mpfig\]. MP and NLOS errors falsify the pseudorange measurements, which are critical to solve the navigation equations and determine the position of the receiver. Numerous methods have been proposed to minimize multipath errors @Bres16 [@Zhu18]. One category of these methods is based on detection @Olla19, with the purpose of excluding erroneous pseudorange measurements from the positioning algorithm. Excluding satellites is only feasible if at least four error-free (single path line-of-sight, SPLOS) satellites are available. Another category is mitigation @Olla20_2, which corrects erroneous pseudorange measurements. To do this, the reflection delay or the pseudorange error has be estimated, which is a complex task. However, the geometrical configuration of the reflecting buildings makes some reflection delay values more probable than others, which can be summarized using a probability density function (PDF). These PDFs can be used as a support for multipath mitigation methods, to be able to assess the environment-based probability of an estimated reflection delay.

![Urban canyons pose three different problems to satellite signals: they can completely block them, allow only a reflection to be received (non-line-of-sight, NLOS), allow the direct signal and a reflection to be received (multipath, MP), or only allow the direct signal (single path line-of-sight, SPLOS). The figure is adapted from @Olla18.<span data-label="fig:mpfig"></span>](fig_mp.pdf){width="45.00000%"}

Related work on multipath delay distributions includes two categories: measurements and simulations.

The first method, to measure multipath distributions, requires one to move a receiver capable of measuring reflections around a city @Stei03 [@Xie14; @Rehm12; @Medi18]. An advantage is that the results will be realistic and representative of the used environment. Disadvantages include problems to generalize for new environments, and that the hardware will limit the precision of the reflection measurements. Based on measurements in Shanghai, the delays follow a gamma distribution, where the shape parameter represents the number of times each signal is reflected on average @Wang18.

The second method, simulating multipath distributions, requires 3D-modeling of the environment and ray tracing to compute the reflections @Stei04 [@Lehn05; @Stei09; @Stei19; @Esbr04]. It has the advantage of allowing free variation of the environment, and it is fairly simple as long as the signals only reflect once. However, if the signals are reflected multiple times (multi-reflection), the simulation becomes computationally heavy.

In this paper, we present the results of a ray tracing simulation, that has been repeated for 12 environments with different mean building heights. As in related work, the reflections follow a gamma distribution, but in addition we show that the shape parameter decreases with increasing building height. Furthermore, a quadratic model is proposed to estimate the shape parameter using the number of available satellites, which is feasible for real-time applications.

Simulations {#sec:sim}
===========

Each simulation consists of four steps: urban canyon generation, definition of antenna and satellite trajectories, and ray tracing. All simulations were sampled once per second.

Urban Canyon Generation {#sec:gen}
-----------------------

As a first step, 12 urban environments were generated, each consisting of nine city blocks. The city blocks are squares with side $b = 250 \, \text{m}$, separated by the road width $\Delta b = 30 \, \text{m}$, see Fig. \[fig:geo\]. Each building is defined by its width $w = 25 \, \text{m}$ and its height $h$, which follows a Rice distribution @Rice45 $$\begin{aligned}
h \sim \text{Rice}(\nu_h,\,\sigma_h),
\label{eq:geo}\end{aligned}$$ with non-centrality parameter $\nu_h$ and scale parameter $\sigma_h$. The Rice distribution was chosen because it is strictly positive and because its two parameters allow an adjustment of a mean and a standard deviation similarly to the Gaussian distribution.

![The urban canyon's dimensions are deterministic (left), while the width and height of each building follow a Rice distribution (right).<span data-label="fig:geo"></span>](fig_GEO.pdf){width="80.00000%"}

In Fig. \[fig:vissigmah20\], a generated geometry with $\nu_h = 25 \, \text{m}$ can be seen.

![An example of a randomly generated geometry with $\nu_h = 25 \, \text{m}$.<span data-label="fig:vissigmah20"></span>](vis_sigmah20-eps-converted-to.pdf){width="75.00000%"}

For the environments, the value of $\nu_h$ varied from $5 \, \text{m}$ to $60 \, \text{m}$ in steps of $ 5 \, \text{m}$, see Fig. \[fig:nuvalues\] (all with $\sigma_h = 5 \, \text{m}$). Since the Rice distribution only supports positive values, its mean $$\begin{aligned}
\mu_h = \sigma_h\sqrt{\frac{\pi}{2}} L_{1/2}\bigg(\frac{-\nu_h^2}{2\sigma_h^2}\bigg)
\label{eq:muh}\end{aligned}$$ is slightly higher than $\nu_h$, especially for lower values of $\nu_h$. Here, $L_{1/2}$ is the Laguerre polynomial of degree $1/2$. Hereafter, the mean building height $\mu_h$ will be used to represent the mean urban canyon depth (which is equivalent to mean building height).

![We simulated 12 environments with different mean building heights $\mu_h$. The mean building height is slightly higher than the $\nu_h$ parameter, since the Rice distribution only supports positive values.<span data-label="fig:nuvalues"></span>](nuvalues-eps-converted-to.pdf){width="85.00000%"}

Vehicle and antenna
-------------------

The vehicle was modeled as a cuboid with identical sides of $2 \, \text{m}$, and a height of $1.5 \, \text{m}$. The antenna was on its roof, with a distance over the roof of $\delta = 1 \, \text{cm}$. The vehicle moved with the velocity $\bar{v}_a$ and the speed $\| v_a \| = 5 \, \text{m/s}$. At the equator, the satellites reach a higher elevation than at extreme southern or northern latitudes, which is why we used a position near New York City: $\lambda = 40 ^\circ$, $\phi = -70 ^\circ$. At this location, $7.88$ satellites are above $15^{\circ}$ elevation on average, this is what the receiver would receive if the buildings were not there. The vehicle drove in the middle of the road, and performed a full turn around the central city block, see Fig. \[fig:geo\]. One simulation represents $224 \, \text{s}$ and a distance of $1.12 \, \text{km}$.

Satellite orbits
----------------

For each point in time, satellite positions of all 31 GPS satellites were generated. The scenario was repeated six times, each repetition starting two hours later than the previous repetition (since the satellite positions repeat themselves after ca. 12 hours). This fast-forwarding was done to average out different satellite constellations. The elevation of a satellite is $\theta$ and its azimuth angle is $\beta$.

Ray tracing
-----------

For each point in time, given a satellite position $s$ and the position of the vehicle antenna $a$, and given a plane (defined with a point of the plane $p$ and its normal $\bar{n}$), the reflections were computed. First, the mirror point $a_m$ of the antenna position was computed, see Fig. \[fig:refl\]: $$\begin{aligned}
a_m =  a + 2 \bar{n} \bigg(    \frac{( p - a) \cdot \bar{n}}{\bar{n} \cdot \bar{n}}  \bigg).
\label{eq:mirror}\end{aligned}$$

![The reflection point $r$ was computed using mirroring.<span data-label="fig:refl"></span>](fig_refl.pdf){width="35.00000%"}

Second, the reflection point in the plane was computed using projection: $$\begin{aligned}
r = s + \frac{(p-s) \cdot \bar{n}}{(a_m - s) \cdot \bar{n}} (a_m - s).
\label{eq:reflection}\end{aligned}$$ Third, a check was made whether $r$ was within the limits of the plane, to decide if it really was a reflection point. This was repeated for all the planes that were generated. Finally, the reflection delay $d$ was computed as the difference between the direct path and the path via the reflection point $$\begin{aligned}
d = \|r-s\| + \|a-r\| - \|a-s\|.
\label{eq:delay_def}\end{aligned}$$

Results and Discussion
======================

This section presents and discusses the results of the simulation. First, the reception modes are presented, followed by the delay distributions, and a model to estimate the delay distributions. The simulations identified a large number of small ($d < \delta = 1 \, \text{cm}$) car roof reflections. These values are too small to be relevant for reflection delay estimation, thus they were excluded from the subsequent analysis.

Reception modes {#sec:recmode}
---------------

First, it can be noted that the total number of reflections per time step tend to decrease with increasing mean building height, see Fig. \[fig:noRefls\].

![In general, fewer reflections are received in deeper urban canyons.<span data-label="fig:noRefls"></span>](noRefls-eps-converted-to.pdf){width="80.00000%"}

Second, with increasing values of building height, the satellites tend to switch from the category SPLOS to blocked, see Fig. \[fig:recModes\]. The multipath reception mode slightly decreases in frequency with urban canyon depth, while the NLOS mode becomes slightly more common. The reason is that increasing building height means not only that more satellites are blocked, but also that more reflections are blocked. If the simulation would allow the signals to reflect more than once these results could change, however these secondary reflections could be too weak to influence the receiver. The total number of received satellites $N_s$ is the sum of the modes SPLOS, MP, and NLOS. Somewhere between $\mu_h = 40 \, \text{m}$ and $\mu_h = 45 \, \text{m}$, less than four satellites are received, meaning that stand-alone 3D GNSS positioning becomes impossible.

![For deeper urban canyons, more satellites are blocked instead of being received as single path line-of-sight.<span data-label="fig:recModes"></span>](recModes-eps-converted-to.pdf){width="89.00000%"}

Reflection delay distributions
------------------------------

As found by @Wang18, a gamma distribution seems to fit the reflection delays well, see Fig. \[fig:delayPDF\]. In difference to @Wang18, where the scale parameter is between 2 and 3, the scale parameter is 1 in our results. One reason could be differences in geometry, such as the wider streets in Shanghai or a larger value of $\sigma_h$. Another possibility is that this simulation only allows signals to reflect once, whereas @Wang18 interpreted the measured signals to have been reflected between 2 and 3 times on average. A further difference to @Wang18 is that the simulated delays are in general shorter, which could be attributed to the fact that the simulation is a symmetric urban canyon, while the Shanghai streets are not always blocked by buildings on both sides.

When the scale parameter of the gamma distribution is equal to 1, the shape parameter $d_m$ is approximately equal to the median reflection delay, which decreases with increasing mean building height. A few outliers delays exceed $300 \, \text{m}$, which is why the median is used instead of the mean. For deeper urban canyons with higher buildings, only high-elevation satellites can be reflected, and these satellites create smaller reflection delays. As seen in Fig. \[fig:noRefls\], the higher values of $\nu_h$ result in fewer reflections, meaning that the empirical probability densities for these environments are less representative.

![In an open environment, the reflection delays are typically greater than in the deeper urban canyons. A few outlier reflections reach delay values of up to $350 \, \text{m}$, but they are not included in the figure, to make the delays below 100 m more visible.<span data-label="fig:delayPDF"></span>](delayPDF-eps-converted-to.pdf){width="\textwidth"}

Model to estimate reflection delay distributions
------------------------------------------------

The mean building height could be estimated using, e.g. 3D maps of the environment, however the number of satellites $N_s$ is always known by the receiver. We have that $N_s$ decreases with the mean building height. Likewise, the median reflection delay decreases with increasing building height. Thus, we can use the number of received satellites to estimate the median reflection delay, see Fig. \[fig:flowchart\] $$\begin{aligned}
\hat{d}_m = -0.23 N_s^2 +5.08 N_s -4.08 .
\label{eq:model}\end{aligned}$$

![By counting the number of satellites, passing this parameter in the quadratic model, and the using the result as the shape parameter of a gamma distribution, the reflection delay distributions are estimated.<span data-label="fig:flowchart"></span>](ENC_flowchart.pdf){width="90.00000%"}

This quadratic model was fitted using the least-squares algorithm, see Fig. \[fig:model\]. Its RMS estimation error of the median delay is $$\begin{aligned}
\sqrt{\frac{1}{N}\sum_{n=1}^{N}(\hat{d}_{m,n} - d_{m,n})^2  } = 0.33 \, \text{m}.
\label{eq:modelerr}\end{aligned}$$ This applies to GPS only receivers, for multi-constellations receivers with, e.g., GPS and Galileo, the coefficients of \[eq:model\] might need adjustment.

![The median reflection delay can be estimated using a quadratic function of the number of received satellites.<span data-label="fig:model"></span>](model-eps-converted-to.pdf){width="90.00000%"}

Conclusion
==========

As a conclusion, deeper urban canyons result in fewer reflections and shorter multipath delays. The delays follow a gamma distribution, whose shape parameter represents the median reflection delay. A simple quadratic model using the number of received satellites can estimate this median reflection delay. For the future, this information should be used in combination with multipath delay estimation methods, for improved performance. Furthermore, diffraction should be considered. Finally, it would be interesting to derive the median reflection delay based on the satellite elevation, which is a parameter that is easy to access. This could lead to more general results, that also apply to, i.e., unsymmetrical urban areas.

Conclusion
==========

Conclusions :

-   Typically around the minimum satellites received to compute a fix

-   Phase shift seems to be $\pi$ for all reflections

-   -   Which parameters actually depend on carrier frequency?

For future work, the analysis of the distributions should be done with more samples, ideally as a function of the satellite elevation. Furthermore, the geometry could be generalized be imported from the 3D buildings of, e.g., Google Earth. Additionally, a version in Python could be developed to give more users access to the tool. Finally, a user interface could be useful.

Appendix: Simulation Source Code
================================

The source code of this simulation is available at <https://github.com/Fusion-Goettingen>, for use as a benchmarking tool of multipath-resistant positioning algorithms. All the parameters described in this paper can be freely defined by the user. The satellite orbits were generated using "Satellite Constellation" @Riya18 (modified to support a custom sampling time and a custom start time of the day to allow fast-forwarding of the satellite constellation).

Introduction
============

This template provides authors with most of the formatting specifications needed for preparing electronic versions of their papers. The template is used to format your paper and style the text. It has been tailored for output on DIN A4-sized paper (width 210 mm, length 297 mm) with the following margins:

  -------------- --------
  Upper          25 mm
  Lower          25 mm
  Left & right   25 mm.
  -------------- --------

Please do NOT apply hyphenation, your own footers or headers …

Preparing Your Paper
====================

Define abbreviations and acronyms the first time they are used in the text, even after they have been defined in the abstract. Abbreviations such as IEEE, SI, MKS, CGS, sc, dc, and rms do not have to be defined. Do not use abbreviations in the title or heads unless they are unavoidable. You will need to determine whether or not your equation should be typed using either the Times New Roman or the Symbol font. You have to number equations consecutively. Equations should be entered inline $E=mc^2$ or in a separate line with equation numbering

$$\begin{aligned}
    w(n) = 0.54 - 0.46\cos \left( \frac{2\pi n}{N} \right)
    \label{eq:wn}\end{aligned}$$

Note that the equation is centered. Be sure that the symbols in your equation have been defined before or immediately following the equation. Use "", not "Eq. " or "equation ", except at the beginning of a sentence: "Equation  is …".

The colorful version of figures will be implemented in the USB stick with the conference proceedings. Figure captions should be below the figures; table heads should appear above the tables. Insert figures and tables after they are cited in the text. Use the abbreviation "Fig. \[fig:sample\]", even at the beginning of a sentence. Use words rather than symbols or abbreviations when writing Figure axis labels to avoid confusing the reader.

![Very important result.<span data-label="fig:sample"></span>](images/Figure.png){width="70.00000%"}

You have to number citations consecutively within brackets @mustermann10. Do not use Ref. @mustermann10 or reference @mustermann10 except at the beginning of a sentence: Reference @mustermann10 was the first ….

Important Remarks
=================

The electronic version must be submitted online in Acrobat PDF format to the conference organizers via the ENC 2020 website before the specified deadlines.

Maximum number of pages is limited to 10.

At least one author has to register and to pay the conference fee.

All final papers must be converted to PDF Format by the IEEE eXpress service.

Further information can be found on the web site: https://www.enc2020.eu

<span>88</span> X. Mustermann, Y. Wellknown, and Z. Pfiffig, "New research in radar field", *Proc. of 2010 Very Important Radar Conference*, Bigcity, Incountry, June 2010, vol. 3, pp. 210-214 H. R. Hertz, "Ueber sehr schnelle electrische Schwingungen", *Annalen der Physik*, May 1887, vol. 267, no. 7, pp. 421-448. J. C. Maxwell, "A Treatise on Electricity and Magnetism", 3rd ed., vol. 2. Oxford: Clarendon, 1892, pp. 68-73.

{'source': 'arXiv_out/2006'}