summaryrefslogtreecommitdiffstats
path: root/vorlagen/thesis/src/kapitel_x.tex
diff options
context:
space:
mode:
authorRefik Hadzialic2012-06-30 18:27:59 +0200
committerRefik Hadzialic2012-06-30 18:27:59 +0200
commitf0201f3c27b71a2aad945922736d93bec8102a04 (patch)
treeb11e2d6a8c5e84a29133a6712b21265e932ad394 /vorlagen/thesis/src/kapitel_x.tex
parentWriting GPS position estimation (diff)
downloadmalign-f0201f3c27b71a2aad945922736d93bec8102a04.tar.gz
malign-f0201f3c27b71a2aad945922736d93bec8102a04.tar.xz
malign-f0201f3c27b71a2aad945922736d93bec8102a04.zip
Explaining the derivation of the distance
Diffstat (limited to 'vorlagen/thesis/src/kapitel_x.tex')
-rw-r--r--vorlagen/thesis/src/kapitel_x.tex188
1 files changed, 170 insertions, 18 deletions
diff --git a/vorlagen/thesis/src/kapitel_x.tex b/vorlagen/thesis/src/kapitel_x.tex
index 9acca55..ecac181 100644
--- a/vorlagen/thesis/src/kapitel_x.tex
+++ b/vorlagen/thesis/src/kapitel_x.tex
@@ -49,7 +49,7 @@ S(t) = \sqrt{\frac{P}{2}}d_{C/A}cos(2\pi f_{c}+\varphi_{SV}) + n(t)
-\section{GPS signal demodulation}
+\section{GPS signal acquisition and demodulation}
\label{sec:SigDemod}
The GPS satellites\footnote{Satellites are named as space vehicles
and the abrevation SV is used in the equation notations
@@ -148,7 +148,7 @@ between the instantaneous frequency and instantaneous phase
according to equations \eqref{eq:freqPhase} and \eqref{eq:phaseFreq}.
\begin{equation}
\label{eq:freqPhase}
-f(t)=\frac{1}{2\pi}\frac{d}{dt}\phi(t)
+f(t)=\frac{1}{2\pi}\frac{\partial}{\partial t}\phi(t)
\end{equation}
\begin{equation}
\label{eq:phaseFreq}
@@ -518,22 +518,22 @@ known in accuracy of submilliseconds.
\section{Distance and position estimation}
-This section will focus on examining the distance and position estimation inside of the GPS system.
+This section will focus on examining the distance and position estimation inside of the GPS receiver.
GPS system, as mentioned earlier, takes advantage of the time of arrival (TOA) ranging concept
to determine user position. Time is measured how long it takes for a signal to arrive from a
-known location. Satellite locations can be estimated using the ephemeris data and the exact time.
+known location.
\begin{figure}[ht!]
\centering
\includegraphics[scale=0.60]{img/Localization.pdf}
- \caption[]{}
+ \caption[]{Basic position estimation principle for one satellite}
\label{img:SatLocalization}
\end{figure}
In figure \ref{img:SatLocalization} an example concept can be seen where $\vec{u}=(x_u,y_u,z_u)$ represents the
GPS user position vector with respect to Earth-Centered, Earth-Fixed\footnote{ECEF is a Cartesian coordinate system
where the point $(0,0,0)$ is defined as the center of mass of the Earth \citep{earthCoordinates}.}
-(ECEF) coordinate system, $\vec{r}$ is the offset vector from the satellite to the user and $\vec{s}=(x_s,y_s,z_s)$
-represents the GPS satellite position with respect to ECEF. Vector $\vec{s}$ is computed from ephemeris data broadcasted
-by the satellite. Vector $\vec{r}$, satellite to user vector, can be computed using equation \eqref{eq:r} and its magnitude is
+(ECEF) coordinate system, $\vec{r}$ is the distance vector from the satellite to the user and $\vec{s}=(x_s,y_s,z_s)$
+represents the GPS satellite position with respect to ECEF at a timepoint. Vector $\vec{s}$ is computed from ephemeris data broadcasted
+by the satellite. Distance vector $\vec{r}$, satellite to user, can be computed using equation \eqref{eq:r} and its magnitude is
given in equation \eqref{eq:rMag}.
\begin{equation}
\label{eq:r}
@@ -543,8 +543,8 @@ given in equation \eqref{eq:rMag}.
\label{eq:rMag}
r=\Vert s-u\Vert
\end{equation}
-Geometric distance $r$ is computed by measuring the signal propagation time, this is illustrated in figure \ref{img:TimingLoc}
-and explained in section \ref{sec:CAdemod}. The PRN code generated on the GPS satellite
+The geometric distance of $r$ is computed by measuring the signal propagation time, this is illustrated in figure \ref{img:TimingLoc}
+and it was mentioned in section \ref{sec:CAdemod}. The PRN code generated on the GPS satellite
at time $t_1$ arrives at the time $t_2$, the difference between these two time stamps, $\Delta t$, represents the
propagation time. By multiplying the propagation time, $\Delta t$, with the speed of light, $c$, the
geometric distance $r$ is computed, as given in equation \eqref{eq:rDist}.
@@ -563,8 +563,9 @@ as described in sections \ref{sec:SigDemod} and \ref{sec:2dSearch},
clock error offsets have to be added to
the geometric distance $r$. This new distance is called pseudorange, $\rho$, because the range is
determined using the difference of two nonsynchronized clocks (one on the GPS satellite and
-the other one on the receiver). Pseudorange is calculated as given in equation \eqref{eq:rho}, where
-$t_{u}$ is the advance of the receiver clock with respect to the system time and $\delta t$ is the offset of the
+the other one on the receiver) that generate PRN codes. Pseudorange is calculated as given in equation \eqref{eq:rho}, where
+$t_{u}$ is the advance of the receiver clock with respect to the system time\footnote{System
+time is the exact time on Earth and it is the most precise time known!} and $\delta t$ is the offset of the
satellite clock from the system time \citep{understandGPS}.
\begin{equation}
\label{eq:rho}
@@ -576,29 +577,180 @@ Therefore equation \eqref{eq:rMag} can be rewritten as \eqref{eq:rhoR} with resp
\rho - c(t_{u}-\delta t) = \Vert s-u\Vert
\end{equation}
Offset of the satellite clock from the system time, $\delta t$, is updated from Earth, as mentioned in \ref{sec:SigDemod}
-and for that reason it can be removed (i.e. it is not an unknown term anymore),
-the eqaution \eqref{eq:rhoR} can be rewritten as \eqref{eq:rhoNew}.
+and for that reason it can be removed for sake of simplicity, i.e. it is not an unknown term anymore,
+then the eqaution \eqref{eq:rhoR} can be rewritten as \eqref{eq:rhoNew}.
\begin{equation}
\label{eq:rhoNew}
\rho - ct_{u} = \Vert s-u\Vert
\end{equation}
In order to estimate the user (GPS receiver) position,
-advance of the receiver clock with respect to the system time , $t_u$, has to be found, i.e. equation \eqref{eq:rhoSats}
+advance of the receiver clock with respect to the system time, $t_u$, has to be found, in other words equation \eqref{eq:rhoSats}
has to be solved, where $i$ is the index of visible satellites at the moment of signal reception \citep{understandGPS}.
\begin{equation}
\label{eq:rhoSats}
\rho_i= \Vert s_i-u\Vert + ct_u
\end{equation}
The estimated position of the user, $\vec{u}=(x_u,y_u,z_u)$, is a three dimensional vector and as mentioned
-earlier the offset, $t_u$ is also an unknown term, then it is required to have at least four equations \eqref{eq:rhoSats}
-to find all the four unknown terms. As a result of this fact, at least four satellites have to be visible at
-the same time to estimate the position of the target user. Equation given in \eqref{eq:rhoSats} takes the form given in
+above the clock offset, $t_u$, is unknown as well. This four dimensional space requires to have at least four pseudorange
+equations \eqref{eq:rhoSats} to find all the four unknown terms.
+As a result of this fact, at least four satellites have to be visible at
+the same time to estimate the position of the target user. Equation given in \eqref{eq:rhoSats} takes the form in
\eqref{eq:rhoSatsNew} because the coordinate system is Cartesian and $\rho_i$ is nothing else but Euclidean distance
where $i=1,2,...,n$ such that $n\geq4$ and $\vec{s_i}=(x_i,y_i,z_i)$ is the satellite position estimated from the ephemeris data.
\begin{equation}
\label{eq:rhoSatsNew}
\rho_i= \sqrt{(x_i-x_u)^2+(y_i-y_u)^2+(z_i-z_u)^2} + ct_u
\end{equation}
+Undoubtedly, the given equation in \eqref{eq:rhoSatsNew} is a nonlinear
+equation\footnote{Nonlinear
+equations, also known as polynomial equations, are equations that cannot satisfy both
+of the linearity properties:
+additivity $f(x+y)=f(x)+f(y)$ and homogeneity $f(\alpha x) = \alpha f(x)$, $\alpha \in \mathbb{R}$ \citep{nonlinear}.}.
+It is not possible easily to find an explicit solution to nonlinear as for linear equations.
+There are different techniques to solve sets of nonlinear equations \citep[Chapter 7]{understandGPS}
+but in this work the linearization method\footnote{Linear approximation is a technique where a function
+is approximated using a linear function.}
+will be presented to find the unknown terms $(x_u,y_u,z_u,t_u)$, i.e. out of an approximate position and clock
+offset the true user position and the true clock offset will be calculated.
+\begin{equation}
+\label{eq:rhoSatsNewFun}
+\rho_i= \sqrt{(x_i-x_u)^2+(y_i-y_u)^2+(z_i-z_u)^2} + ct_u = f(x_u,y_u,z_u,t_u)
+\end{equation}
+Let the equation \eqref{eq:rhoSatsNew} for pseudoranges, be rewritten as a function $f$ of four
+unknown terms $x_u$, $y_u$, $z_u$ and $t_u$, as
+given in \eqref{eq:rhoSatsNewFun} \citep[Chapter 2]{understandGPS}. Suppose that the approximation of the
+position and the clock offset are known,
+denoted as $\hat{x_u}$, $\hat{y_u}$, $\hat{z_u}$ and $\hat{t_u}$, then equation \eqref{eq:rhoSatsNewFun}
+can be rewritten as an approximate pseudorange \eqref{eq:rhoSatsNewFunApprox}.
+\begin{equation}
+\label{eq:rhoSatsNewFunApprox}
+\hat{\rho_i}= \sqrt{(x_i-\hat{x_u})^2+(y_i-\hat{y_u})^2+(z_i-\hat{z_u})^2} + c\hat{t_u} = f(\hat{x_u},\hat{y_u},\hat{z_u},\hat{t_u})
+\end{equation}
+In other words, the unknown true position terms $x_u$, $y_u$, $z_u$ and the clock offset term $t_u$, of the GPS receiver,
+will be expressed by the approximate values and an incremental component as shown in equation \eqref{eq:userCoordinates} \citep{understandGPS}.
+\begin{equation}
+\label{eq:userCoordinates}
+\begin{array}{l}
+x_u = \hat{x_u}+\Delta x_u \\
+y_u = \hat{y_u}+\Delta y_u \\
+z_u = \hat{z_u}+\Delta z_u \\
+t_u = \hat{t_u}+\Delta t_u
+\end{array}
+\end{equation}
+By inserting the terms from \eqref{eq:userCoordinates} into equation \eqref{eq:rhoSatsNewFun}, a new equation is derived
+as in \eqref{eq:rhoSatsNewFunwithApprox}.
+\begin{equation}
+\label{eq:rhoSatsNewFunwithApprox}
+f(x_u,y_u,z_u,t_u) = f(\hat{x_u}+\Delta x_u, \hat{y_u}+\Delta y_u, \hat{z_u}+\Delta z_,\hat{t_u}+\Delta t_u)
+\end{equation}
+In the next step the pseudorange function will be approximated using Taylor series\footnote{Taylor
+series ``is a representation of a
+function as an infinite sum of terms that are calculated from the values of the function's
+derivatives at a single point'' \citep[Chapter 11]{taylor}.} (linearization of the nonlinear equation). Taylor
+series for a function $f(x)$ is given in equation \eqref{eq:taylor}, where as $a$ approches $x$ the estimation
+error will be smaller and smaller, i.e. $f(x) = f(a)$ when $x=a$. The approximation error
+depends on Taylor polynomial degree (the amount of terms or taken derivatives of the function)
+and how far away the point $a$ is from $x$ \citep[Chapter 11.9]{taylor}.
+The basic idea of the principle can be seen in figure \ref{img:taylorSeries}.
+\begin{equation}
+\label{eq:taylor}
+f(x) = \sum_{n=0}^{\infty}\frac{f^{(n)}(a)}{n!}(x-a)^n = f(a) + \frac{f'(a)}{1!}(x-a)+\frac{f''(a)}{2!}(x-a)^2+...
+\end{equation}
+\begin{figure}[ht!]
+ \centering
+ \includegraphics[scale=0.50]{img/TaylorSeries.pdf}
+ \caption[]{Taylor series approximation for a point $a=0.5$ where $n$ is the Taylor polynomial degree}
+\label{img:taylorSeries}
+\end{figure}
+Due to the four unknown terms, Taylor series for multivariables
+have to be used. The general formula is given in
+equation \eqref{eq:Multitaylor}, where vector $\mathbf{x}\in\mathbb{R}^n$ denotes
+$n$ variables, $\nabla$ (nabla) is the Del\footnote{Del, $\nabla$,
+is the vector differential operator.} operator given in \eqref{eq:Del} and $\mathbf{a}$ is the
+linearization point of interest
+\citep{multiTaylor}.
+\begin{equation}
+\label{eq:Multitaylor}
+f(\mathbf{x}) \approx f(\mathbf{a}) + \nabla f |_{\mathbf{x=a}} \cdot (x-a)
+\end{equation}
+\begin{equation}
+\label{eq:Del}
+\nabla^{T} = \left[\frac{\partial}{\partial x_{1}}...\frac{\partial}{\partial x_{n}}\right]
+\end{equation}
+One can note that in equation \eqref{eq:Multitaylor} the Taylor series polynomial is of the first degree.
+This is because of one reason, it linearizes the approximation of the function $f(\mathbf{x})$ at point $\mathbf{a}$
+and as a consequence it removes the nonlinearities \citep{understandGPS} \citep[Chapter 11.10]{taylor}, as seen
+in figure \ref{img:taylorSeries}, for $n=1$ the resulting function is linear.
+In the previously described step, one would calculate a hyperplane tangent to a
+point $a$ in a $n$-Dimensional space. By inserting equation \eqref{eq:rhoSatsNewFunwithApprox} in
+equation \eqref{eq:Multitaylor}, it yields equation \eqref{eq:MultitaylorFour} where $\mathbf{x}=(x_u,y_u,z_u,t_u)$
+and $\mathbf{a}=(\hat{x_u},\hat{y_u},\hat{z_u},\hat{t_u})$.
+\begin{equation}
+\label{eq:MultitaylorFour}
+\begin{array}{l}
+f(\hat{x_u}+\Delta x_u, \hat{y_u}+\Delta y_u, \hat{z_u}+\Delta z_,\hat{t_u}+\Delta t_u) \approx
+ f(\hat{x_u},\hat{y_u},\hat{z_u},\hat{t_u}) \\[0.3em]
+ + \dfrac{\partial f(\hat{x_u},\hat{y_u},\hat{z_u},\hat{t_u})}{\partial \hat{x_u}}\Delta x_u
++\dfrac{\partial f(\hat{x_u},\hat{y_u},\hat{z_u},\hat{t_u})}{\partial \hat{y_u}}\Delta y_u \\
++\dfrac{\partial f(\hat{x_u},\hat{y_u},\hat{z_u},\hat{t_u})}{\partial \hat{z_u}}\Delta z_u
++\dfrac{\partial f(\hat{x_u},\hat{y_u},\hat{z_u},\hat{t_u})}{\partial \hat{t_u}}\Delta t_u
+\end{array}
+\end{equation}
+The terms from equation \eqref{eq:MultitaylorFour} are solved individually in
+equations \eqref{eq:MultitaylorDeriv} where $\sqrt{(x_i-\hat{x_u})^2+(y_i-\hat{y_u})^2+(z_i-\hat{z_u})^2}$
+has been subsituted with $\hat{r_i}$.
+\begin{equation}
+\label{eq:MultitaylorDeriv}
+\begin{array}{l}
+\dfrac{\partial f(\hat{x_u},\hat{y_u},\hat{z_u},\hat{t_u})}{\partial \hat{x_u}} = \dfrac{1}{2}\dfrac{-2(x_{i}-\hat{x_{u}})}{\sqrt{(x_i-\hat{x_u})^2+(y_i-\hat{y_u})^2+(z_i-\hat{z_u})^2}}
+=-\dfrac{x_i-\hat{x_u}}{\hat{r_i}}\\[0.9em]
+\dfrac{\partial f(\hat{x_u},\hat{y_u},\hat{z_u},\hat{t_u})}{\partial \hat{y_u}} = \dfrac{1}{2}\dfrac{-2(y_{i}-\hat{y_{u}})}{\sqrt{(x_i-\hat{x_u})^2+(y_i-\hat{y_u})^2+(z_i-\hat{z_u})^2}}
+=-\dfrac{y_i-\hat{y_u}}{\hat{r_i}}\\[0.9em]
+\dfrac{\partial f(\hat{x_u},\hat{y_u},\hat{z_u},\hat{t_u})}{\partial \hat{z_u}} = \dfrac{1}{2}\dfrac{-2(z_{i}-\hat{z_{u}})}{\sqrt{(x_i-\hat{x_u})^2+(y_i-\hat{y_u})^2+(z_i-\hat{z_u})^2}}
+=-\dfrac{z_i-\hat{z_u}}{\hat{r_i}}\\[0.9em]
+\dfrac{\partial f(\hat{x_u},\hat{y_u},\hat{z_u},\hat{t_u})}{\partial \hat{t_u}} = c
+\end{array}
+\end{equation}
+Then by substituting the equation terms from \eqref{eq:MultitaylorDeriv}, \eqref{eq:rhoSatsNewFun} and \eqref{eq:rhoSatsNewFunApprox}
+into \eqref{eq:MultitaylorFour}, the resulting equation is given in \eqref{eq:MultitaylorDerivAfter}.
+\begin{equation}
+\label{eq:MultitaylorDerivAfter}
+\begin{array}{l}
+\rho_i = \hat{\rho_i} -\dfrac{x_i-\hat{x_u}}{\hat{r_i}}\Delta x_u -\dfrac{y_i-\hat{y_u}}{\hat{r_i}}\Delta y_u -\dfrac{z_i-\hat{z_u}}{\hat{r_i}}\Delta z_u + c\Delta t_u
+\end{array}
+\end{equation}
+At this step, by solving equation \eqref{eq:MultitaylorFour}, the linearization of the nonlinear equations is completed.
+\begin{equation}
+\label{eq:MultitaylorDerivAfterRearange}
+\begin{array}{l}
+\hat{\rho_i} - \rho_i = \dfrac{x_i-\hat{x_u}}{\hat{r_i}}\Delta x_u +\dfrac{y_i-\hat{y_u}}{\hat{r_i}}\Delta y_u +\dfrac{z_i-\hat{z_u}}{\hat{r_i}}\Delta z_u - c\Delta t_u
+\end{array}
+\end{equation}
+\begin{equation}
+\label{eq:SubsTerms1}
+\Delta\rho = \hat{\rho_i} - \rho_i \\[0.7em]
+\end{equation}
+\begin{equation}
+\label{eq:SubsTerms2}
+\alpha_{xi} = \dfrac{x_i - \hat{x_u}}{\hat{r_i}} \hspace{1.5em} \alpha_{yi} = \dfrac{y_i - \hat{y_u}}{\hat{r_i}} \hspace{1.5em} \alpha_{zi} = \dfrac{z_i - \hat{z_u}}{\hat{r_i}}
+\end{equation}
+By rearanging the equation \eqref{eq:MultitaylorDerivAfter}
+and by substituting the terms in \eqref{eq:SubsTerms1} and \eqref{eq:SubsTerms2} into \eqref{eq:MultitaylorDerivAfterRearange},
+the equation \eqref{eq:MultitaylorDerivAfterRearange} resembles the one given in \eqref{eq:userPosition}.
+\begin{equation}
+\label{eq:userPosition}
+\Delta\rho_i = \alpha_{xi}\Delta x_u + \alpha_{yi}\Delta y_u + \alpha_{zi}\Delta z_u - c\Delta t_u
+\end{equation}
+
+
+
+
+
+
+
+
+
+
\section{Assisted GPS in Wireless networks}
\label{sec:agps}
In the following paragraphs Assisted GPS (A-GPS) will be presented and how it works.