\chapter{Introduction} \section{Motivation} Recent developments in the field of physics, chemistry and electronics have led to the cost-efficient manufacturing of diverse, compact single chip integrated solutions. As a consequence of this rapid development it became possible to integrate a GPS receiver into almost every cell phone without drastically increasing the price, physical size or weight of the cell phone. An example of this would be the GPS receiver chip inside the Apple iPhone 3GS. Its cost was estimated to be around \$2.25 USD \citep{GPSiphoneCost}. It is important to note that the number of wireless connections has increased as well; in 2011 there were 6 billion mobile connections worldwide \citep{gsmConnection}. In the following European countries, Germany, France, Spain, Italy and UK, 44\% of all GSM users own a smart phone, whereas in the US and Canada this number is slightly higher, 46\% \citep{smartPhoneUsage}. By the statistics of the Blur group, 47\% of all the cell phones on the world will be smart phones by 2015 \citep{smartPhone2015}. An emerging new market of Location-Based Services (LBS) has resulted and since then the telecommunication and marketing industry have undergone rapid change. In 2009, 63 million users owned LBS-capable phones. This number is expected to grow in 2012 to 468 million users worldwide \citep{smartPhone2015}. As social networks like Facebook, Twitter or Foursquare (a location-based social network) expand, it has become a trend for the users to share their location with their friends \citep{smartPhone2015}. It has been reported that LBS represents a bonanza opportunity for new startup companies and global industry analysts project by 2015 a global market worth \$21 USD billion ($\approx$ \euro17.142 billion) \citep{Bonanza}. New ideas and algorithms for tracking, navigation solutions, safety, security, searching for local business and payments shall emerge from the use of LBS technology \citep{Bonanza}. LBS have already been used for tracking people with dementia and Alzheimer's disease, as reported in a study performed by researchers at the University of Siegen \citep{Muller}. The Enhanced 911 (E911), an emergency service in the US for linking emergency callers with the appropriate service (police, firefighters and emergency room), is regulated by the US Federal Communication Commission (FCC), which sets the standards for all telecommunication providers, including the precision with which callers' locations are tracked \citep{novine}. Europe's emergency service has similar standards \citep{0849333490}. Next generation networks, Long Term Evolution (LTE) 4G networks, have been designed from the start to have LBS capabilities integrated in the system and have better LBS performance as well as higher accuracy compared to GSM networks \citep{lteLocation}. %In the introductory chapter, some of the most common positioning techniques in %wireless networks shall be presented and analysed, including Cell-ID, Time-of-Arrival, Angle-of-Arrival %and GPS positioning. The author shall then describe the goals of his thesis. In this thesis the author will provide the theoretical and practical knowledge required for building a localization system of mobile users inside of a 2G GSM network by taking advantage of the already-existing Assisted-GPS (AGPS) receivers inside of smart phones. Another reason why the AGPS method was preferred over other localization methods is because the position estimation is sufficiently precise and accurate compared to other methods. Further advantage over other positioning techniques is that smart phones with an AGPS receiver represent slightly less than 50\% of the total cell phone market in the most solvent EU economies and the US \citep{smartPhoneUsage}. This work may be seen as a scenario what kind of information can be gained by a third persons having access to a GSM network. This thesis may be perceived as pioneer work in the field of localizing mobile users by taking advantage of AGPS receivers in smart phones. \section{Overview of the thesis} %In this thesis the author shall provide theoretical and practical %background knowledge required for building a localization system of mobile users %inside of a 2G GSM network by taking the advantage of AGPS receivers inside of smart phones. %In the lab a 2G GSM network was set up similar to the real network environment %provided by network operators. Software for generating assistance data %was developed. Then the GSM software was modified to deliver requests and %assistance data to cell phones according to a protocol described in the thesis. %The functional aspects and %abuse risks of AGPS receivers in smart phones are relatively unknown, %no relevant studies have been found and thus will be further analysed in this work. %A certain privacy risk exists that it is possible to obtain the position of a mobile user %without its knowledge of being surveillanced. The thesis is divided into three parts. The first is a theoretical introduction to GSM and GPS systems as well as the protocol required for the positioning of mobile users. The second part provides more details on the software implementation and the hardware required to construct the equivalent setup. The last section is a discussion and analysis of the findings and accomplished results in the test environment. It is followed by the conclusion and provides a discussion of security issues. Chapters 2 and 3 will provide a theoretical introduction of the GSM operational principles as well as of the GPS and AGPS receivers required for understanding the basic functioning principles of the entire positioning system. The theoretical concepts of GPS receivers will be analysed and discussed in depth since they provide evidence for the advantages and limitations of this method. These two chapters will provide an explanation for the achieved and observed results in this thesis. Once the GSM and GPS working principles have been explained, the author shall proceed with introducing the reader to the Radio Resource Location Protocol (RRLP), responsible for transmission of assistance data and obtaining the position of the mobile user. More details on RRLP will be provided in chapter 4. In chapter 5, the reader will be introduced to the software development and implementation process. More details on the hardware connections and setup shall be provided in chapter 6. In chapter 7 test results and the test environment will be presented. Chapter 8 will provide a summary of the entire system. The appendix contains details for configuring the entire system and for obtaining the same results. This thesis includes a CD with the source code developed during the work on this thesis. \chapter{GSM} In the past two decades we have been witness to an increasing development of wireless communication technologies, one of the most rapidly developing fields of engineering. Global System for Mobile Communications\footnote{First time when the standard was developed, GSM meant \textit{Groupe Spéciale Mobile} \citep{0890064717}} (GSM) networks played a major role in wide-spreading wireless voice services in every corner of the planet \citep{gsmConnection}. According to the GSM Association (GSMA) in 2011 there have been 6 billion registered wireless connections world wide \citep{gsmConnection}. In this chapter more details shall be given on the second generation GSM network which was employed in this work for delivering GPS assistance data to cell phones. More information shall be provided on the general working principles of GSM and how a data channel is initialized to deliver data to cell phones. \section{GSM Network structure} \begin{figure}[ht!] \centering \includegraphics[scale=0.5]{img/GSMBig.png} \caption{Basic GSM network block diagram. Image courtesy of \citep{konrad} and \citep{dennis}.} \label{img:GSMBig} \end{figure} \label{sec:GSMNetStruct} Cell phones require special purpose hardware to build a wireless connections. This hardware is the Base Transceiver Station (BTS). BTS is the first hardware unit the cell phone is communicating with over the air interface and provides a connection with the cell phone \citep[Chapter 3]{0890064717}. This connection between the BTS and the cell phone is called the \textit{$U_m$ interface}, as shown in figure \ref{img:GSMBig}. A BTS can serve up to six users on one frequency in full duplex mode since two out of eight time slot are used for broadcasting of signalling and system information. %transmitted in the broadcast control channel (BCCH). By sectorising BTSs with different frequencies and by altering the configuration the number of six mobile users can be increased per sector. The BTS are divided into geographical regions\footnote{Usually they are represented as hexagons but it could take any other geometric shape.} by their signal coverage. A BTS consists of a RF transceiver, internal clock and modulator/demodulator. The function of the RF transceiver is to enable the reception and transmission on the uplink and downlink channel for the cell frequency where the BTS is located\footnote{Cell is the area covered with GSM signal and from which a cell phone can communicate with a BTS.}. The main function of the internal clock is to supply the BTS with a frequency such that the internal circuits can produce frames separated in time domain. The internal clock has to be sufficiently accurate for the GSM network to work, an accuracy of at least $\pm$5 ppm (parts per million) \citep{dennis}. If the GSM network is synchronized, this internal clock is not employed but an external clock generated signal from an atomic clock. The GSM network must be synchronized for some of the position localization techniques discussed in this chapter. Devices providing the synchronous clock are called Location Measurement Units (LMU). Modulator/demodulator main function is the modulation and demodulation of the received and transmitted signals. The transmission from the cell phone to the BTS is shifted for 3 time slots compared to the reception of the signal from the BTS\footnote{Timing advance factor is added to the three time slots. The numbering of the time slots remains the same, i.e. if time slot 0 is used for downlink, it is named 0 in the uplink as well although it is shifted.} \citep[Chapter 7]{0890064717} \citep{konrad} \citep[Chapter 4]{0470742984}. This frequency shift was introduced so that the cell phone has sufficient time to switch its reception unit to transmission unit \citep{dennis}. One or more BTSs are connected to the Base Station Controller (BSC). The main task of the BSC is to control the radio resources of the connected BTSs such as assigning radio channels to different BTS, frequency hopping in case of an \textit{handover} and controlling the power levels within channel \citep[Chapter 4]{0470742984} \citep{konrad} \citep[Chapter 3]{0890064717}. Handover is the process of switching\footnote{Disconnecting from the BTS currently connected to and connecting to the neighboring one with another frequency} from one BTS to another during an active connection when the signal reception strength is higher than on the currently-connected BTS. This signal reception strength is known as Received signal strength (RSS). RSS are measurement reports transmitted from the cell phone to the BTS. RSS is used to determine if the handover process should be triggered or not \citep{Richard2011Master}. BSC is connected to the Transcoding Rate, Adaptation Unit (TRAU) and Serving Mobile Location Center (SMLC). The SMLC node contains the functionality to support location services for the GSM network \citep{3GPPTS03.71}. This builds the Base Station Subsystem (BSS), as it can be seen in figure \ref{img:GSMBig}, on left side inside of the gray dashed line rectangle. Inside of the BSS, TRAU is responsible for compressing and decompressing speech between the cell phone and a speech signal from the other side, from 64 kbps to 16 or 8 kbps depending if it is a full or half rate channel. The next subsystem block is the Network Switching Subsystem (NSS), as it can be seen on figure \ref{img:GSMBig}, on right side inside of the gray dashed line rectangle. The main task of NSS is to connect the GSM with other telephony networks (GSM networks from other providers or the Public Switched Telephone Network) \citep[Chapter 4]{0470742984}. It consists of Mobile Switching Center (MSC), Gateway Mobile Switching Center (GMSC) and databases. MSC's main function is to route incoming and outgoing calls between the moving mobile users, ``the assignment of user channels toward the BSS'' \citep[Chapter 4]{0890064717} \citep{konrad}. GMSC is a type of MSC for external networks, GSM networks from other providers or telephone networks are routed through the GMSC\citep[Chapter 4]{0890064717}. There are four databases: Home Location Register (HLR), Visitor Location Register (VLR), Authentication Center (AUC) and Equipment Identity Register (EIR). HLR database stores data about the GSM subscribers of a network provider. The data, contained in the HLR database, are subscriber's unique International Mobile Subscriber Identity (IMSI) code, subscriber's phone numbers (MSISDN), subscriber's current location and subscriber's usage statistics. IMSI is the serial number of the Subscriber Identification Module (SIM) card. The SIM card is inserted in the cell phone. Subscriber's usage statistics are information that contain data for the billing system. The current location of a mobile user is acquired through the location of the BSC which controls the BTS currently serving the mobile user, i.e. the BTS to which the cell phone is connected now \citep{konrad}. VLR serves as a temporary data storage of important parts of HLR data (not all data known for the particular user) of all the visiting mobile subscribers served by the current MSC. For instance if a cell phone from its home MSC enters an area covered by the newly entered MSC, its VLR will request some of the HLR data from the HLR database of the MSC where the cell phone is registered \citep{dennis} \citep[Chapter 4]{0470742984}. AUC contains confidential keys for each mobile subscriber required for encrypting the data before they are transmitted to the cell phone from the BTS \citep[Chapter 3]{0470030704}. The keys located in AUC are also required for the cell phone to register in the network \citep{konrad}. EIR is an optional database but contains data about approved types of mobile equipment (not stolen cell phones), black listed cell phones (they are identified by their International Mobile Equipment Identity number which is unique for every manufactured cell phone) and cell phones which ought to be tracked if they register \citep[Chapter 4]{0890064717}. \section{Overview of the air interface (Um)} The main task of GSM networks was to enable wireless voice transmission between GSM and other GSM/telephone users inside of switched networks. It was not designed to be used with data services which are a necessity in today's standards. GSM networks are worldwide spread and work on different frequency spectrums depending on the country where the networks are deployed. The reason why different frequencies are used is because of interference with different wireless systems and used telecommunication standards. Particularly in Germany, the Federal Network Agency (German: $Bundesnetzagentur$) is the responsible organisation for assigning different frequencies to GSM operators since these frequencies belong to the group of licensed frequencies and are not allowed to be used by everyone. In Germany the used frequency bands are GSM900 and GSM1800, their frequency ranges can be seen in table \ref{tbl:GSMfreqs} \citep{konrad}. These frequency bands are divided into 200 KHz channels, for a frequency band range of 35 MHz there are 175 operating channels. This technique is called Frequency Division Multiple Access (FDMA) and supports using parallely more frequency channels inside of the same covered area with GSM RF signal. FDMA is employed when the frequency bandwidth is limited like in the GSM networks. By utilising FDMA the network throughput is used more efficiently since different users can send or receive information at different frequency slots instead of waiting for their turn. These frequency channels have a unique identifier number. They are named as Absolute Radio Frequency Channel Numbers (ARFCN). The basic idea of FDMA inside of the frequency spectrum GSM900 for GSM can be seen in figure \ref{img:GSMFreqRangChannel}, ARFCN numbers are assigned according to the frequencies which are employed. It is important to distinguish uplink and downlink frequencies. Uplink frequency is used when the cell phone transmits data to the network operator, whereas downlink from the network operator to the cell phone. GSM is a full duplex communication system, at the same time the cell phone or the network operator can send and receive data. Although the equivalent ARFCN number is used for uplink and downlink channels, the frequencies are shifted 45 MHz in GSM900 and 95 MHz in GSM1800 as it can be seen in figure \ref{img:GSMFreqRangChannel} for GSM900. \begin {table}[ht] \caption{GSM operating frequencies in Germany.} \label{tbl:GSMfreqs}\centering %\rowcolor{2}{light-gray}{} \scriptsize\fontfamily{iwona}\selectfont \begin{tabular}{lllll} \toprule %$D$&&$P_u$&$\sigma_N$\\ \textbf{Frequency band}&\textbf{Uplink frequency (MHz)}&\textbf{Downlink frequency (MHz)}&\textbf{Channel number}\\\toprule GSM900&880 - 915&925 - 960&0, 1 - 124, 975 - 1023\\\midrule GSM1800&1710 - 1785&1805 - 1880& 512 - 885\\\bottomrule \end {tabular} \end {table} \begin{figure}[ht!] \centering \includegraphics[scale=0.50]{img/GSMUpDownFreq.pdf} \caption{Frequency ranges of uplink and downlink channels in the GSM900 band. Each box represents a frequency band (channel). Image courtesy of \citep{konrad} and \citep{dennis}.} \label{img:GSMFreqRangChannel} \end{figure} \par Aside from using different frequency channels, each frequency channel (ARFCN) is split up into eight time slots \ref{img:GSMFreqTime}. This technique of dividing a frequency into time slots is named Time Division Multiple Access (TDMA). TDMA allows several users to share the same frequency channel but in different time slots. Using this technique the voice throughput is better utilised and a broader amount of users can be served at the ``same'' time, i.e. the capacity of parallely speaking GSM users is increased. TDMA was employed because the voice could be compressed with Linear Predictive Coding (LPC) without the human noting a difference in the call quality \citep{0824740408}. By taking advantage of LPC, instead of the 64 kbps required for transmission of voice it was possible to compress the voice without losing much of the call quality into 8 kbps for half rate and 16 kbps for full rate\footnote{Human speech has a frequency bandwidth between 0 and 4000 Hz \citep{humanFreq}. Human voice is by its nature analog and requires to be converted into a digital stream of ones and zeros. By Nyquist-Shannon sampling theorem the sampling frequency must be at least two times greater than the sampled frequency and with an 8 bit Analog to Digital Converter (ADC) this defines the 64 kbps required to transfer voice ($2\cdot4000 Hz\cdot8 = 64000$).}. \newpage The idea of employing TDMA on FDMA in the GSM900 band can be seen in figure \ref{img:GSMFreqTime}. Each time slot duration is $\approx$577 $\mu s$, all 8 time slots have a period of $\approx$ 4.615 $ms$ \citep{dennis} \citep{0890064717}. By applying this technique each GSM user can send data inside of the assigned time slot without disturbing users on different time slots. \begin{figure}[ht!] \centering \includegraphics[scale=0.50]{img/GSMFreqTime.pdf} \caption{Each frequency channel (ARFCN) is split into 8 time slots. With this approach more GSM users can be served at the ``same'' time. Image courtesy of \citep{0890064717}.} \label{img:GSMFreqTime} \end{figure} Eight time slots in GSM are called a TDMA frame. Each time slot in GSM is known as a physical channel, on the physical channels are built up the logical channels. Logical channels have a predefined pattern of time slot they are assigned. Logical channels can be divided in two groups, traffic channels (TCH) and signalling/controlling channels (CCH). User payload data like speech and message data are transmitted in the TCH channels whereas control data for control, synchronization and management of the GSM network are transmitted through the CCH channels \citep[Chapter 4]{0470030704}. \begin{figure}[ht!] \centering \includegraphics[scale=0.70]{img/GSMHierarchy.pdf} \caption{Hierarchy of the GSM frames. Image courtesy of \citep{0890064717}.} \label{img:GSMHierarchy} \end{figure} Every TDMA frame is assigned a unique integer number which is then repeated and reassigned every 3h:28m:53s:760ms, also known as \textit{hyperframe} \citep[Chapter 7]{0890064717}. In the hierarchy pyramid, a layer lower of the hyperframe is the \textit{superframe}. There are two types of superframes, consisting of two types of \textit{multiframes}, differing in their length \citep[Chapter 7]{0890064717}. The relations can be seen in figure \ref{img:GSMHierarchy} with their duration periods. The multiframe with 26 TDMA frames carries only traffic channels. The other multiframe type, with 51 TDMA frames carries solely signalling data. This hierarchy constrain was defined due to internal synchronization of the GSM network and cyphering between the cell phone and the BTS \citep[Chapter 7]{0890064717}. \section{Logical channels and the data channel} \label{sec:SDCCHChan} In this section more details will be given on logical channels and the procedure to initialize (open) a Stand-alone Dedicated Control Channel (SDCCH). As stated in section \ref{sec:GSMNetStruct}, logical channels can be divided in two groups, traffic channels (TCH) and signalling/controlling channels (CCH). The former are employed for transferring payload data like speech and message data and the latter for managing and synchronizing the GSM network \citep[Chapter 4]{0470030704}. For the purposes of this thesis, the term ``Mobile Station'' (MS) will be used to refer to a cell phone or to designate the user one intends to locate. Traffic and signalling channels can be split up by their usage, as given in tables \ref{tbl:tchChannels} and \ref{tbl:cchChannels}. \begin {table}[hb] \caption{Traffic channels on the air interface. Table courtesy of \citep{0890064717}.} \label{tbl:tchChannels}\centering %\rowcolor{2}{light-gray}{} \scriptsize\fontfamily{iwona}\selectfont \begin{tabular}{llll} \toprule %$D$&&$P_u$&$\sigma_N$\\ \textbf{Channel name}&\textbf{Abbreviation}&\textbf{Function}&\textbf{Direction}\\\toprule Traffic channel full rate &TCH/F & Full rate traffic transmission & MS$\leftrightarrow$BSS\\\midrule Traffic channel half rate&TCH/H& Half rate traffic transmission & MS$\leftrightarrow$BSS \\\bottomrule \end {tabular} \end {table} \begin {table}[hb!] \caption{Control channels on the air interface. Table courtesy of \citep{0890064717}.} \label{tbl:cchChannels}\centering %\rowcolor{2}{light-gray}{} \scriptsize\fontfamily{iwona}\selectfont \begin{tabular}{llll} \toprule %$D$&&$P_u$&$\sigma_N$\\ \textbf{Channel name}&\textbf{Abbreviation}&\textbf{Function}&\textbf{Direction}\\\toprule Frequency correction channel&FCCH &Frequency correction for oscillator on MS & MS$\leftarrow$BSS\\\midrule Synchronization channel&SCH&Synchronization information (TDMA frame& MS$\leftarrow$BSS\\ &&number to know current location in hyperframe)\\\midrule Broadcast common control channel&BCCH&Broadcast information about & MS$\leftarrow$BSS\\ &¤t BTS and its neighbouring cells\\\midrule Access grant channel&AGCH&Required to assign the MS an SDCCH& MS$\leftarrow$BSS\\ &&or TCH channels\\\midrule Paging channel&PCH &Paging request is sent out when MS has& MS$\leftarrow$BSS\\ &&incoming traffic (phone call, SMS, etc.)\\\midrule Cell broadcast channel&CBCH&Required to broadcast a message to all& MS$\leftarrow$BSS\\ &&MS inside of a MSC (e.q. weather forecast)\\\midrule Stand-alone dedicated control channel&SDCCH&Exchange of signalling information between&MS$\leftrightarrow$BSS\\ &&MS and BTS when no TCH is active\\\midrule Slow associated control channel&SACCH&Transmission of signalling data during an active&MS$\leftrightarrow$BSS\\ &&TCH connection (signal strength and sync. data)\\\midrule Fast associated control channel&FACCH&Transmission of signalling data during an active&MS$\leftrightarrow$BSS\\ &&connection but used only if necessary \\ &&(e.q. handover)\\\midrule Random access channel&RACH&Request from MS to BTS for a communication& MS$\rightarrow$BSS\\ &&channel (e.g. a phone call from MS) \\\bottomrule \end {tabular} \end {table} The protocol scenario occurring in this work can be seen in figure \ref{img:SDCCHReq} \citep{0470844574}. In order for the assistance data to be delivered to the MS, an SDCCH channel has to be initialized. This occurs in the following procedure, the BTS where the MS has been lastly active or idle broadcast a paging request (PCH channel) to the selected MS. After the MS obtains the paging request, the MS shall try to send a random access request (RACH channel) using the Slotted Aloha protocol. Another MS could transmit a random access request in the same time slot allowing collisions to occur. In case there was no collision, if the BTS successfully received the random access request and at the moment of reception has a free SDCCH channels, it will immediately reserve an SDCCH channel and send the MS an assignment request (AGCH channel) back. After the MS obtains the assignment request, the SDCCH channel is initialized and data can be transferred in both directions. In this particular case, in the thesis, assistance data are sent to the MS (BTS$\rightarrow$MS), whereas the acknowledgements, errors or the position are delivered to the BTS (BTS$\leftarrow$MS). In the case if all SDCCH channels are reserved, the network will queue an SDCCH request for later assignment or it may send an assignment reject. %Once the SDCCH channel connection has been established, data can be transmitted in both directions. While an active SDCCH connection exists, the MS will receive and transmit radio link control messages (signal strength and synchronization data) on the SACCH channel \citep{0470844574}. \begin{figure}[ht!] \centering \includegraphics[scale=0.50]{img/SDCCHRequest.pdf} \caption{Initializing an SDCCH channel. Image courtesy of \citep{0470844574}.} \label{img:SDCCHReq} \end{figure} \section{Positioning techniques in GSM networks} In this section, the current technologies for estimating the position of a mobile user shall be presented and their working principle. When the GSM network was designed, its primary goal was to enable wireless full duplex telephone service \citep{gsmTelephony}. Over the past decade the GSM and its derivative networks became more popular and mature compared to the initial GSM standard, so the demands grew for new services such as Internet connectivity and LBS. Emergency services wanted to be able to localize mobile users in emergency situations like snow avalanches or other non-typical daily emergency situations \citep{0849333490}. This demand led to the development of various approaches that differ in complexity and in the degree of accuracy of position fixes. However, the user positioning was limited by existing technology standards, and any improvement would require extremely expensive cost modifications to the existing network infrastructures. Several different ideas have been put forward to localize mobile users while avoiding these potential problems. They shall be presented in the following sections. First, however, it is important to distinguish between three different approaches to positioning mobile users, handset-based, network-based, and hybrid-based. With handset-based techniques, the handset itself tries to estimate its position on its own using the available information. In the network-based approach, the network makes all the required measurements and the handset itself is passive. The last, hybrid-based, approach uses resources from the handset and network together; both are active participants in the position estimation process. A few different methods, varying by their complexity and precision, shall be presented, in order of their complexity. \subsection{Cell-ID} The cell-identification method is the simplest known GSM positioning method \citep[Chapter 8]{0470092319}. By knowing the geographical location of the BTS, one can roughly estimate the position of the MS \citep[Chapter 4]{0470694513}. It is important to build maps where the BTS signal can be received and where the border \textit{handover} points are located. The basic principle is shown in figure \ref{img:cellid}. The MS is in the region of the currently-connected BTS and it could be at any point inside of the hexagon. Every BTS has a unique identifier code name and hence can be distinguished from other BTS's. \begin{figure}[ht!] \centering \includegraphics[scale=0.70]{img/CellID.pdf} \caption{Cell-ID position estimation technique.} \label{img:cellid} \end{figure} %Using this method even higher accuracies %can be achieved than the known shape of signal reception \citep[Chapter 8]{0470092319}, provided that the %\textit{timing advance} (TA) value is known. The TA is the rough prediction of the \textit{round trip time} (RTT), time %required for a data packet to be received and acknowledged by the MS. Using this measure a rough circle can be made between %the BTS and the bordering points of the Cell-ID region. %To obtain the TA value a connection between the MS and the BTS has to exist or a silent call can be made %where the GSM subscriber does not even notice that he/she is being called since there is no ringing %or any other sign that an idle connection is being performed on the MS \citep[Chapter 4]{3GPPTS03.71}. %If there are more than one antenna, then the MS location can be even more precisely specified. %This can still be inaccurate, however, because of multi-path signal reflections. %In urban environments it is usually the case that there is no optical line of sight between the BTS and MS, %so while the signal propagates from the BTS to the MS and vice versa it may be reflected by buildings %or other objects which add extra propagation time (extra range to the distance). The accuracy of this method is typically in a range of 200 m \citep{Zeimpekis}. This method can be seen both as a handset- and network-based position estimation technique, due to the fact that the user may run his/her own application on the cell phone or it can be applied by the network operator himself. This estimation technique does not require the MS to be a smart phone; it works with any type of cell phone. \subsection{Received Signal Strength} The RSS position estimation technique, as the name states, uses the signal strength measurement reports to localize the MS. \begin{figure}[ht!] \centering \includegraphics[scale=0.50]{img/RSS.pdf} \caption{Basic idea of the RSS estimation technique. One rectangle location is represented by two RSS measurements for two BTS, blue indicates BTS1 and red indicates BTS2.} \label{img:rssLoc} \end{figure} This method requires mapping the location blocks of the covered areas with RSS before it can be used \citep{Richard2011Master}. The basic idea can be seen in figure \ref{img:rssLoc}, where one location region is represented by two differently colored (blue and red) RSS measurements inside of one rectangle. By knowing the RSS in advance one can estimate the probability that the MS is located in the black rectangle. Since it is difficult to measure the RSS at every point, the map is interpolated with RSS using the Voronoin interpolation to calculate the expected RSS at places were the measurement have not been conducted \citep{Richard2011Master}. In the next step the probability distribution, the Bayes Theorem, is utilised to estimate the location of the MS by computing probabilities for all the points in the map. The precision of this method is limited to the amount of BTS in range and the manufacturer design of the RF front end in the cell phone. However, this method can be applied on any cell phone and does not require a smart phone. It is a network based estimation technique. \subsection{E-OTD and UL-TDOA} \label{LMUSync} E-OTD and UL-TDOA are two similar positioning techniques; both use the time difference of signal arrival and for this reason have been grouped together. E-OTD stands for Enhanced Observed Time Difference. This technique requires the GSM network to be clock-synchronized. The clock synchronization of the GSM network can be achieved with a Location Measurement Unit (LMU) \citep{ETSI.TS.125.111}. LMU's provide the precise time to the BTS's by having an atomic clock synchronized with the BTS on a separate location from the BTS or by providing a special GPS device at the BTS' location that can provide the precise time \citep{ETSI.TS.125.111}. The clock synchronization of the MS and the BTS is required because the E-OTD technique takes advantage of measuring signal propagation time. A data signal with precise up-to-date time information is transmitted from three or more spatially distinct BTS's at the same time and then propagation time is measured on the MS (all these BTS's must be detectable by the MS itself) \citep{200mRangeEOTD}. Once the difference in time is known between when the signal was transmitted and when it was received, it is easy to estimate the relative position to the BTS's with hyperbolic trilateration \citep{200mRangeEOTD} \citep[Chapter 4]{3GPPTS03.71}. In order to estimate the absolute position, one must first know the absolute location of the BTS's. The basic idea can be seen in figure \ref{img:eotdLoc}. \begin{figure}[ht!] \centering \includegraphics[scale=1.20]{img/EOTD.pdf} \caption{Basic idea of the E-OTD positioning technique. Current time information is transmitted from 3 different BTS's at the same time. Then the MS observes the difference of time when the information arrive and using trilateration technique calculates the relative position of the MS.} \label{img:eotdLoc} \end{figure} E-OTD requires the cell phone to be equipped with firmware to perform these measurements but does not require new or external hardware. The accuracy of this method lies in the range between 50-200 m, depending on the location of the MS \citep{malik2009rtls}. This method is can still be susceptible to the multipath signal problem, however. E-OTD is a handset-based position estimation technique. UL-TDOA (Up-Link Time Difference of Arrival) is a similar localization technique as E-OTD \citep{malik2009rtls}. The basic difference between UL-TDOA and E-OTD is that the signal propagation time is observed on the BTS's and not on the MS itself. To estimate the position of the MS, the BTS responsible for the MS forces the MS to request a handover to two or more BTS's nearby. The MS sends a handover burst signal and the neighboring BTS's measure the waiting time between the handover request signal itself and the transmitted burst from the MS. Using the observed time difference, the BTS's can compute the location of the MS. It is important to note that this position estimation technique takes place while there is an active call on the MS or the BTS makes a silent call to the MS where the mobile user is not aware of being tracked \citep{malik2009rtls}. This technique is slightly less accurate than E-OTD; the accuracy lies between 50-300 m \citep{200mRangeEOTD}. The unsynchronized operation of the GSM network makes these two techniques impossible without clock synchronization. One microsecond error would produce an error of around 300 m. The advantage of UL-TDOA over E-OTD lies in the fact that no extra software modifications have to be made to the cell phone and this technique works on every cell phone. UL-TDOA is a network-based position estimation technique. \subsection{Other techniques} The previously-mentioned localization techniques are not the only existing methods but are the standardized ones. In this section, two more techniques shall be briefly described: Angle-of-Arrival and Google Maps' WiFi tagging. \begin{figure}[ht!] \centering \includegraphics[scale=1.20]{img/AOA.pdf} \caption{Basic idea of the Angle-of-Arrival positioning technique. The angle of the reception signal on the BTS antenna is measured. By knowing at least two angles on two BTS's, it is possible to interpolate the intersection point where the MS is located.} \label{img:aoadLoc} \end{figure} Angle-of-Arrival (AOA) is a localization technique that exploits a geometric fact that by knowing at least two angles from two known points, i.e. BTS's, it is possible to construct the third triangle point (intersection point). The intersection point represents the location of the MS. The angle is derived by a burst signal transmitted from the MS and the time difference of arrival for different elements of the burst signal. Once the angle is computed, it is straightforward to find the intersection point. This technique requires the BTS's to be synchronized with LMU's and to be in line of sight with the BTS's, otherwise this method shall deliver poor position results. It belongs to the group of network based position estimation techniques. \begin{figure}[ht!] \centering \includegraphics[scale=0.50]{img/WiFiTag.pdf} \caption{Wireless Access Point tagging. The MS could be located anywhere where all three access points are visible, this area has a wavy background and is between access points 1, 2 and 4.} \label{img:WiFiTag} \end{figure} Another technique gaining in popularity is used by Google Maps to identify the position of the user by simply tagging an area with all visible wireless access points \citep{googleLBS}. Since each access point has a unique MAC address it is not hard to identify them while driving through urban areas with a WiFi scanning device. The basic idea is depicted in figure \ref{img:WiFiTag}, where the MS in this particular example is located where access points 1, 2 and 4 are visible at the same time stamp. This technique works efficiently indoors as well as outdoors in cities since reception ranges of 801.11 b/g wireless networks are not more than 30-150 m, though the new standard 801.11 n has a wider coverage area. A simple overview of all the discussed techniques is given in table \ref{tbl:overviewLoc}. \begin {table}[h] \caption{Overview of the localization techniques.} \label{tbl:overviewLoc}\centering %\rowcolor{2}{light-gray}{} \scriptsize\fontfamily{iwona}\selectfont \begin{tabular}{lllll} \toprule %$D$&&$P_u$&$\sigma_N$\\ \textbf{Technique}&\textbf{Sync.}&\textbf{Advantage\&Disadvantage}&\textbf{Accuracy}&\textbf{Type}\\\toprule Cell-ID& No& Works on any cell phone;& Anywhere in cell& Network\\ & &Imprecise&&\\%\midrule RSS & No& Works on any cell phone;& $\approx 300$ m& Network\\ & &Depends on cell phone&&\\ & &model and environment&&\\ \midrule E-OTD &Yes& Works on most new& $\approx 50-200$ m& Handset\\ & &cell phone models;&\\ & &Expensive because LMU&\\ \midrule UL-TDOA&Yes&Works on any cell phone& $\approx 50-300$ m& Network\\ & &Expensive because LMU&&\\ \midrule %AGPS&Yes/No&Works on some cell& $\approx 5-20$ m& Hybrid\\ % & &phones with AGPS&\\ % & &receivers; Very precise&\\ \midrule AOA &Yes&Works on any cell phone;& Depends if MS is& Network\\ & &Expensive because LMU&in line of sight&\\\midrule Google maps&No&Requires a smart phone&$\approx 5-30$ m& Handset\\ with WiFi& &with Google maps and& &with aid\\ & &Wireless 801.11 b/g/n;& &of\\ & &Does not work outside & &Network\\ & &of cities or missing \&& \\ & &unknown WiFi signal&\\\bottomrule \end {tabular} \end {table} \subsection{Assisted-GPS} Another positioning technique is Assisted-GPS (AGPS). It has recently gained popularity because of the great number of smart phones with an embedded AGPS receiver. AGPS receivers can drastically decrease the waiting time required to estimate the position compared to GPS receivers if ``exact time'' is known \citep[Chapter 4]{diggelen2009a-gps}. AGPS works by exploiting the existing navigation satellite network. This method does not work on every cell phone as do the aforementioned methods. It requires the cell phones to be equipped with an AGPS receiver. From this point on, cell phones with an AGPS receiver shall be referred to as smart phones since they have another potential use aside from the default communication application. The AGPS position estimation technique is a hybrid-based technique because the position is estimated with the help of the handset and the network provider. In other words, the handset estimates the position and the network provider delivers the required assistance data for faster acquisition time. The aim of this thesis is to employ this technique to get positions of GSM users with smart phones. %Further analyses showed that the received signals arrive at the cell phone %with errors because of multiple propagation reflection and are often hardly %distinguishable from noise \citep[Chapter 2]{diggelen2009a-gps}. %The power of received signals on a GPS receiver is in the range %of 100 attowatts\footnote{1 attowatt = $10^{-16} W$. %The reception quality depends on the receiver's antenna and RF front-end design as well.} %when the GPS receiver is outdoors. %The signal strength becomes even smaller by a factor of 10-1000 if the user is %between tall buildings or indoors \citep[Chapter 2]{diggelen2009a-gps}. All these factors %affect the acquisition of GPS signals and make the correct reception of GPS signals unrealisable %and impractical. %Instead of searching manually for the GPS satellites and waiting %for the orbiting parameters to arrive from the satellites, which are required to estimate the %position, information about the orbiting GPS satellites is transmitted over an existing GSM %network infrastructure. This provides the AGPS receiver additional data to track weak signals. %\setchapterpreamble[u]{% % \dictum[Stobaeus] {What use is knowledge if there is no understanding?} %} \chapter{GPS \& Assisted-GPS} \label{gpsTheoryChatper} \begin{figure}[ht!] \centering \includegraphics[scale=0.38]{img/satelliteRanges.pdf} \caption{GPS Simple working principle, a) example in 3D space with spheres b) example in 2D space with circles.} \label{img:GPSSimplePrinciple} \end{figure} In the new global economy age, GPS (Global Positioning System) positioning has become of important value for various services and businesses. It has been growing at a rate of 30\% in the past few years and the application market is expected to be worth \euro 240 Millard by 2020 only in Europe \citep{gpsMoney}. The goal of this chapter is to bring more details and insights of how GPS receivers work. The chapter is divided in few sections that explain what type of data are transmitted by the satellites. how they are modulated before transmission, demodulated on the receiver and how the search space works to track a GPS satellite.% and % how the target user position is estimated. It is important to understand the basic principle of GPS navigation. GPS positioning works by using the principle of \textit{trilateration}. Distances from the satellites to the GPS receiver are measured and from these distances receiver's position is estimated. The distances are estimated by measuring the signal propagation time between the satellites and the receiver, this position estimation technique belongs to the group of time-of-arrival (TOA) methods. Once sufficient amount of measurements from different satellites were generated, the position of the receiver can be approximated. %It is important to note that the satellite positions %need to be known before proceeding with any calculations. The general principle of this idea can be seen in figure \ref{img:GPSSimplePrinciple}, figure (a) shows the idea with spheres in 3D space and figure (b) the same idea but in 2D space. The blue, yellow and green wireframes below the GPS satellites represent the spheres for the given range between the satellites and the GPS user. By knowing the positions of the reference points, i.e. positions of GPS satellites, user's position can be estimated. By intersecting three spheres, the 2D position of the user can be estimated. The GPS satellites are positioned in orbits so that at every moment at any spot on Earth, at least four satellites are visible (a spot can be considered as a mountain peak since in the cities GPS signals are blocked by buildings). \section{GPS data and signal modulation/demodulation} \label{sec:gpsDataAndSignal} The aim of this section is to give the reader an overview of the transmitted GPS data and to understand what type of processing takes place on the GPS satellite itself. As discussed in the paragraph earlier, to estimate the position of the GPS receiver, it is important to know the position of the satellite at the moment of signal transmission. Prior to releasing the data in the atmosphere, they need to be modulated in order for the GPS receiver to receive the data. Each one of the GPS satellites transmits the same type of information. The transmitted data are called \textit{frames} \citep{9780817643904}. One frame of data can be seen in figure \ref{img:gpsframe}. Every of the 25 transmitted frames can be divided into five subframes of 300 bits length \citep{diggelen2009a-gps}. The data in the frames are called \textit{navigation data} because using them the GPS receiver can estimate user's position. \begin{figure}[ht!] \centering \includegraphics[scale=0.60]{img/NAV-Message.pdf} \caption{One frame of 1500 bits on L1 frequency carrier. Image courtesy of \citep{harper2010server-side}.} \label{img:gpsframe} \end{figure} Each subframe can be divided into three fields of data, as shown in figure \ref{img:gpssubframe}, Telemetry (TLM), Handover Word (HOW) and rest of the data (navigation data). TLM is the first word of the subframe and consists of a unique preamble used to synchronize and identify the subframes \citep{9780817643904}. HOW is the second word of the subframe and consists of the \textit{GPS system time} and subframe ID \citep{9780817643904}. GPS system time is the time the atomic clock on the satellite generates at the moment of subframe broadcast and it acts as a time stamp \citep{GPS-Interface-Specification}. These atomic clocks are calibrated and maintained on a daily basis by the U.S. Air Force \citep{GPS-Pentagon}. The time the atomic clock generates, denoted as $t_{SV}$, is generated at the moment of the subframe broadcast \citep{GPS-Interface-Specification}. The third segment of the subframe, indicated as rest of data in figure \ref{img:gpssubframe}, consists of the navigation data. The first subframe includes data about the satellite accuracy and health parameters as well as data used for the clock corrections on the GPS receiver. These clock correction parameters can be characterized as bias, drift and aging errors \citep{GPS-Interface-Specification}. Subframe two and three are made of \textit{ephemeris data}. Ephemeris information contain precise parameters for predicting the precise orbital position of the GPS satellite. Without the ephemeris data it is not possible for the GPS receiver to estimate its position. \begin{figure}[ht!] \centering \includegraphics[scale=0.50]{img/GPSSubframe.pdf} \caption{Subframes always start with telemetry and handover words, the rest are parameters for removing errors and for estimating satellite's position.} \label{img:gpssubframe} \end{figure} Fourth and fifth subframes include \textit{almanac data}, low-precision clock corrections, ionospheric model and UTC time calculation parameters. Ionospheric model and UTC time calculation parameters are required by the GPS receiver to refine the calculation of delays through the ionosphere \citep{9780817643904}. Almanac information is rough coarse parameters for predicting the orbital position of the GPS satellites. These low-precision parameters (almanac) are used by the receiver to estimate the rough position of the satellites which in return reduces the searching space of emitting satellite frequencies. Although all satellites transmit on the same frequency, when the signals are received on Earth, they have a different frequency from the transmitted one because of the Doppler effect \footnote{Doppler effect is a phenomenon that happens as a result of relative motion of the two bodies, transmitter and receiver, towards or away from each other and causes frequency shift of the electromagnetic wave \citep[Chapter 4]{3540727140}.}. Once the frequencies are known, the receiver can track the satellites and obtain ephemeris parameters which are required to estimate the position. The first three subframes are satellite dependent and do not change in the transmitted 25 frames aside from the system time stamp \citep{GPS-Guide}. The reason why there are 25 frames is because of the last two subframes, four and five. Subframes four and five have data which cycle through the 25 frames, i.e. almanac data are transmitted for all the 32 GPS satellites\footnote{24 satellites are used in the GPS system, the rest is used in case one of the 24 fails.} in case the receiver found only one satellite and once it collected all almanac data, it can search for other visible GPS satellites. These 25 frames create a masterframe. Once the 25 frames have been transmitted, the process is repeated again. %This shall be further explained in more details in the following sections \ref{sec:Carrierdemod}, %\ref{sec:CAdemod} and \ref{sec:2dSearch}. The data are modulated using the Binary Phase Shift Keying (BPSK) technique. The newly modulated signal, denoted as \textit{L1}, and it is emitted from the satellite's directed antennas toward Earth \citep{GPS-Guide}. The BPSK technique works by changing the phase of the carrier signal for $180^{\circ}$ at the moment of bit toggle (flipping) in the data \citep{GPS-Guide} \citep{9780817643904}. Basic principle of this technique can be seen in figure \ref{img:bpskmod}. The carrier wave for GPS BPSK modulation is centered at a frequency of 1575.42 MHz \citep{9780817643904}. These signals travel an average distance of $20200 \, km$ from the satellite to the GPS receiver and are affected by various sources of noise. BPSK modulation is mostly used for satellite links because of its simplicity, immunity to noise and signal interference for the cost of low speed data transfer rates \citep[Chapter 1]{9780849316579}. \begin{figure}[ht!] \centering \includegraphics[scale=0.50]{img/BPSKModulation.pdf} \caption{BPSK Modulation - First depicted signal is the carrier wave, and it is multiplied (mixed) with the second signal, which are the data to be transmitted. The resulting signal at the output of the satellite antenna is the third one.} \label{img:bpskmod} \end{figure} However, before the raw subframes enter the BPSK modulation process, they are XORed with Pseudo Random Noise (PRN) sequences for different satellites (each satellite owns a unique PRN sequence) \citep{9780817643904}. PRN sequences are used because they allow the identification of each satellite's transmitted data on the receiver, same satellite emitting frequency as well as to enable the distance measuring mechanism between the satellite and the GPS receiver. When the received signals are processed, equivalent PRN sequences are generated on the GPS receiver and then they are compared with the received PRN sequences which are delayed (shifted) due to the distance between the satellite and the receiver. This delay multiplied with the speed of light yields the distance between the satellite and the GPS receiver. PRN sequences have similar autocorrelation properties as noise, when it is shifted in time domain it has a low correlation value whereas when it is matched with exact image of itself it produces a high correlation peak \citep[Chapter 3]{bensky2008wireless}. This property is used for identifying the satellites and for finding the exact phase shift. This phase shift is a consequence of the relationship between the instantaneous frequency $f(t)$ and instantaneous phase $\phi(t)$ at time instance $t$, the relationship between frequency and phase can be seen in equations \eqref{eq:freqPhase} and \eqref{eq:phaseFreq}. In other words, due to the Doppler effect the phase of the PRN sequence is disordered. Without the exact phase shift it is not possible to demodulate the original data (TLM, HOW and navigation data) from the received signals. \begin{equation} \label{eq:freqPhase} f(t)=\frac{1}{2\pi}\frac{\partial}{\partial t}\phi(t) \end{equation} \begin{equation} \label{eq:phaseFreq} \phi(t) = 2\pi \int_{-\infty}^{t} f(t) dt \end{equation} The second important property of PRN sequences is the property of orthogonality. This property enables the reception of different data on the same frequency, also known as Code Division Multiple Access (CDMA). It is important to note that the PRN sequences must have a higher frequency rate than the data, i.e. the bit duration of a PRN sequence is much shorter than of the data \citep[Chapter 3]{bensky2008wireless}. Single bits in PRN sequences are called \textit{chips} and the complete sequence as \textit{code} \citep[Chapter 3]{bensky2008wireless}. This newly generated signal is called direct sequence spread spectrum (DSSS) \citep[Chapter 3]{bensky2008wireless}. In GPS terminology it is named as Code/Acquisition (C/A) code. C/A code is feed into the BPSK modulation process, where it is mixed with the carrier wave. The new produced signal is the L1. Transmission speed of the navigation message is 50 bps, therefore the reception of a complete masterframe requires around $\approx12.5$ minutes, i.e. $(1500 \, \mathrm{bits per frame}\, \cdot \, 25 \, \mathrm{frames}) / (50 \,\mathrm{bps} \, \cdot \, 60\, \mathrm{s})$. \begin{figure}[ht!] \centering \includegraphics[scale=0.50]{img/GPS-Modulation.pdf} \caption{Modulation of the GPS signal L1. Image courtesy of \citep{harper2010server-side}.} \label{img:gpsmod} \end{figure} The described GPS navigation data modulation can be seen in figure \ref{img:gpsmod}. The figure can be mathematically represented in the form of equation \eqref{eq:GPSSignalReceived1} \citep{1656803}, where $D(t)$ are the navigation data at the moment $t$, $C(t)$ is the PRN chip at the moment $t$, $cos(2\pi f_{c}+\varphi_{SV})$ is the generated carrier wave with frequency $f_c$ and phase $\varphi_{GPS}$, $P$ is output power of the transmitter amplifier. \begin{equation} \label{eq:GPSSignalReceived1} S(t) = PD(t)C(t)cos(2\pi f_{c}+\varphi_{GPS}) \end{equation} The equation \ref{eq:GPSSignalReceived1} shall be rewritten as shown in \ref{eq:GPSSignalReceived2}. It is the equivalent equation but at the GPS receiver, where $d_{C/A}$ is the C/A data and $n(t)$ is the random noise at moment $t$ generated by various factors that influence electromagnetic waves. In the next section, more details shall be revealed on the process of demodulating the GPS L1 signal and acquiring the correct time and position. \begin{equation} \label{eq:GPSSignalReceived2} S(t) = \sqrt{\frac{P}{2}}d_{C/A}cos(2\pi f_{c}+\varphi_{GPS}) + n(t) \end{equation} % \section{GPS signal acquisition and demodulation} % \label{sec:SigDemod} % GPS satellites\footnote{Satellites are named as space vehicles % in GPS terminology and the abbreviation SV is used in the equation notations % to denote a parameter related to the satellite itself.} % orbiting our planet, at a distance of approximately $20200 \, km$, % are equipped with precise atomic clocks \citep[Chapter 2.7]{diggelen2009a-gps}. % These atomic clocks are calibrated and maintained on % a daily basis by the U.S. Air Force \citep{GPS-Pentagon}. % The time the atomic clock generate, referred earlier as GPS % system time, denoted as $t_{SV}$, is generated as a time stamp at the moment % of the subframe broadcast \citep{GPS-Interface-Specification}. % In addition to the % broadcast time, subframe 1 contains parameters to account % for the deterministic clock errors embedded in the % broadcasted GPS system time stamp. These errors can be % characterized as bias, drift and aging errors % \citep{GPS-Interface-Specification}. The correct broadcast % time, denoted as $t$, can be estimated using the model given in equation % \eqref{eq:timecorrection1} \citep{GPS-Interface-Specification}. % In equation \eqref{eq:timecorrection2}, where the GPS % receiver is required to calculate the satellite clock % offset, denoted as $\Delta t_{SV}$, a number of unknown terms can be % seen. These terms are encapsulated inside of the transmitted frames. The polynomial % coefficients: $a_{f0}$ - \textit{clock offset}, $a_{f1}$ - % \textit{fractional frequency offset}, $a_{f2}$ - \textit{ % fractional frequency drift}; and % $t_{0c}$ - \textit{reference epoch} are encapsulated inside % of subframe 1. The only remaining unknown term left in equation % \eqref{eq:timecorrection2} is the \textit{relativistic correction % term}, denoted as $\Delta t_{r}$. $\Delta t_{r}$ can be evaluated % by applying the equation given in \eqref{eq:timecorrection3}. % $F$ is a constant calculated from the given parameters % in \eqref{eq:paramconst1} and \eqref{eq:paramconst2}, % whereas $e$, $\sqrt{A}$ and $E_{k}$ are orbit % parameters encapsulated in subframes 2 and 3 % \citep{GPS-Interface-Specification}. % % \begin{equation} % \label{eq:timecorrection1} % \centering % t=t_{SV}-\Delta t_{SV} % \end{equation} % \begin{alignat}{4} % & \Delta t_{SV} &= \;& a_{f0} + a_{f1}(t_{SV}-t_{oc}) + a_{f2}(t_{SV}-t_{oc})^{2} + \Delta t_{r} \label{eq:timecorrection2} \\ % & \Delta t_{r} &= \; & Fe\sqrt{A}\sin{E_{k}} \label{eq:timecorrection3} \\ % & F &= \;& \frac{-2\sqrt{\mu_{e}}} {c^{2}} = -4.442807633 \cdot 10^{-10} \frac{s}{\sqrt{m}} \label{eq:timecorrection4} % \end{alignat} % % Nevertheless, the broadcast satellite time % information is not sufficient to estimate the precise % time at the moment of the signal arrival. Even though the signal % arrives in approximately\footnote{Propagation time % depends on user and GPS satellite position.} $77 \, ms$, % the precision of the atomic clock is in the % range of 10 ns \citep[Chapter 2]{diggelen2009a-gps}. % Undoubtedly the signal propagation (travel) % time, denoted as $t_{prop}$, has to be taken into account. % In that case, the exact time at the moment of arrival is known, % denoted as $t_{exact}$ and is given in equation \eqref{eq:exactTime}. % %The signal propagation time must be known to % %estimate the distance from the satellite % %but is not sufficient to estimate the position of the GPS receiver. % Propagation time is computed by measuring the phase shift of the C/A % signal, more details shall be given in sections \ref{sec:CAdemod} % and \ref{sec:distanceAndPosition}. % More importantly, $t_{exact}$ time shall be later used % to synchronize various time dependent systems like the % GSM, LTE, GNSS or other communication and ranging systems. % \begin{equation} % \label{eq:exactTime} % t_{exact} = t_{prop}+t % \end{equation} \subsection{Carrier wave demodulation} \label{sec:Carrierdemod} In order to calculate the signal propagation time between the satellite and the receiver, the internal sine wave synthesizer inside of the receiver has to be synchronized with the carrier sine wave generator of the GPS satellite \citep{4560215}. In other words, the identical carrier wave replica has to be generated on the receiver as on the satellite \citep{736341}. However, the received signal is not the equivalent of the transmitted signal due to the nature of the Doppler effect and wave propagation properties. The transmitted signals arrive phase disordered at the receiver \citep{4560215}. Considering that the GPS satellites orbit the Earth with a speed of around $3.9 \, km/s$, the Earth rotates around its axis and the target user with the GPS receiver may move as well, the Doppler effect is unavoidable. The observed phase at the receiver antenna, denoted as $\varphi_{o}$, can be described using the equation given in \eqref{eq:phaseShift}, where $\varphi_{GPS}$ is the known satellite carrier wave phase (as specified in the standard), $\delta \varphi_{SV}$ the clock instabilities on the GPS satellite, $\varphi_{a}$ the phase shift error caused by propagation delays in the ionosphere and troposphere respectively, $\delta \varphi_{DE}$ the phase shift caused by the Doppler effect and $\delta \varphi_{w}$ is the wide-band noise phase shift. \begin{equation} \label{eq:phaseShift} \varphi_{o} = \varphi_{GPS}+ \delta\varphi_{SV} + \varphi_{a} +\delta \varphi_{DE} + \delta \varphi_{w} \end{equation} The task of the demodulation process is to generate a replica carrier wave with the matching phase shift and mix it with the incoming signal. In the ideal case the observed phase on the antenna and the generated phase on the receiver, denoted as $\varphi_{rec}$, cancel each other out, that is to say, equation \eqref{eq:phaseIdealCase} equals zero. \begin{equation} \label{eq:phaseIdealCase} \Delta \varphi = \varphi_{o} - \varphi_{rec} \end{equation} The circuit responsible for generating the same carrier wave is the Phase Locked Loop (PLL). The PLL circuit is a feedback loop that modifies the synthesized wave parameters such that $\Delta \varphi \approx 0$, a phase shift is shown in figure \ref{img:phaseShift}. \begin{figure}[ht!] \centering \includegraphics[scale=0.5]{img/Phase-Diff.pdf} \caption{Two carrier waves with the same frequency but different phase shift.} \label{img:phaseShift} \end{figure} \begin{figure}[ht!] \centering \includegraphics[scale=0.5]{img/L1-Demodulation.pdf} \caption{Demodulation of the L1 GPS signal.} \label{img:L1Demod} \end{figure} The reason why the equivalent carrier wave must be generated is explained in more detail in appendix \ref{sec:carWavDemod}. At this point, the C/A data (navigation message modulated with the PRN code) have been extracted, it is required to demodulate C/A data as well (remove the PRN code). \subsection{C/A wave demodulation} \label{sec:CAdemod} As a result of the previous step, one can continue with the demodulation of the C/A wave. Demodulating the C/A wave with the PRN code will result in the required data for estimating the position. Each tracked GPS satellite signal is demodulated separately using the same PRN code, code chipping rate and carrier frequency-phase for the given satellite \citep[Chapter 4]{understandGPS}. The carrier frequency-phase was determined in the previous step. The PRN codes for each GPS satellite is well defined and known by the GPS receiver. The receiver has to generate the equivalent PRN code with matching code chipping rate (phase) of the transmitted C/A code, this is depicted in figure \ref{img:prnCodeCompare} \citep[Chapter 5]{understandGPS}. This phase shift is again a consequence of the Doppler effect. \begin{figure}[ht!] \centering \includegraphics[scale=0.50]{img/PRN-ChipRate.pdf} \caption{Comparison between the original C/A code generated on the GPS satellite with two synthesized PRN codes with a different phase shift on the receiver. Image courtesy of \citep{understandGPS}.} \label{img:prnCodeCompare} \end{figure} For the particular example, the matching phase shift was achieved with the second replica PRN code, with a phase shift of $\tau=0$ but there could be a case with any other value of $\tau$, $\tau\in[0,1022]$. Implementation of the PRN code synthesizer depends on the GPS receiver manufacturer but it is usually implemented as a Linear Feedback Shift Registers (LFSR) that produces an output according to a predefined function $f(\tau)$. This function, $f(\tau)$, generates an PRN code, that is delayed in phase by $\tau$, where $\tau$ is a multiple of the chipping rate period $T_{c}=977.5 \,ns$. This demodulation process, of finding the correct chipping rate, is given in appendix \ref{sec:CAwaveDemodApend}. Both carrier wave and C/A wave demodulation have to be executed at the same time. This can be represented as a 2D search space problem. This problem will be further analyzed in the following section. % and it will provide an answer why %it takes so long to estimate a position. \newpage \section{Implementation of the 2D search space problem} \label{sec:2dSearch} The 2D search space is limited by well known physical properties of the GPS navigation system, such as the motion speed of GPS satellites and the receiver as well as the frequency oscillator on the receiver. GPS satellites move toward or away from the GPS receiver with a speed of $800 \, \mathrm{m/s}$ \citep[Chapter 3]{diggelen2009a-gps}. The Doppler effect on the frequency of the satellite can be estimated using equation \eqref{eq:dopplerEffectSpeed}, where $f_{e}$ is the emitting frequency (L1), $v_{SV}$ is the speed of the satellite towards or away from the receiver and $c$ is the speed of light. \begin{equation} \label{eq:dopplerEffectSpeed} f_{DE} = f_{e}\frac{v_{SV}}{c} \end{equation} By inserting the appropriate values in equation \eqref{eq:dopplerEffectSpeed} yields a result of $\approx4.2 \, \mathrm{kHz}$, for $800 \, \mathrm{m/s}$ and $\approx-4.2 \, \mathrm{kHz}$ (if the satellite moves away from the GPS receiver then the speed is taken as negative). This makes a total range of $\approx8.4 \, \mathrm{kHz}$. The Doppler effect of the GPS receiver motion can be ignored since for each $1 \, \mathrm{km/h}$ speed of movement, it affects the frequency range for $\approx 1.46 \,\mathrm{Hz}$. On the other hand, the frequency offset induced by the reference oscillator in the GPS receiver can not be ignored. Function of the reference oscillator is to give the GPS receiver the clock pulse required for all the computations and comparisons in the process of signal demodulation. The frequency search space is ``additionally affected for $1.575 \, \mathrm{kHz}$ of unknown frequency offset for each $1 \, \mathrm{ppm}$ (\textit{parts per million}) of the unknown receiver oscillator offset'' \citep[Chapter 3]{diggelen2009a-gps}. The reference oscillators in GPS receivers have typically an offset of $\pm0.5, \pm1, \pm2, \pm3, \mathrm{or} \pm5 \,\mathrm{ppm}$ \citep{daishinku}, \citep[Chapter 3]{diggelen2009a-gps}, the standard in smart phone design has been set to $\pm 2.5 \, \mathrm{ppm}$ \citep{oscillatorGPSSmarthPhone}. In the worst case this makes the unknown frequency to be in range of $10 \, \mathrm{kHz}-25 \, \mathrm{kHz}$. \begin{figure}[ht!] \centering \includegraphics[scale=0.70]{img/2D-SearchSpaceInk.pdf} \caption{Segment of the frequency/code delay search space for a single GPS satellite. Image courtesy of \citep{diggelen2009a-gps}.} \label{img:prnSearchSpace3d} \end{figure} A typical receiver searches in frequency bands (bins) of several hundred Hz \citep{1656803}. Commonly used frequency bin size is $500 \, \mathrm{Hz}$, therefore there are about 20-50 bins to search ($10000\, \mathrm{Hz}/500\, \mathrm{Hz} = 20$) \citep[Chapter 3]{diggelen2009a-gps}. The frequency search bin size is a function of the desired peak magnitude loss (signal to noise ratio) due to the frequency mismatch and integration time period. This means with larger frequency bands, it becomes harder to identify the correlation peaks required to obtain the GPS data, described in section \ref{sec:CAdemod}. % The frequency search bin size can be estimated using the frequency % mismatch loss \textit{sinc} function given in equation \eqref{eq:mistunigLoss} \citep{implSoftGPSRec}, % \citep[Chapter 6]{diggelen2009a-gps}, % where $\Delta f$ is the frequency mismatch in $\mathrm{Hz}$, % in other words it represents the difference % between the received signal frequency and % the synthesized carrier frequency on the receiver; % and $T_{ci}$ is the coherent integration time (usually $0.5\, ms$ according to \citep{implSoftGPSRec} % and \citep[Chapter 3]{diggelen2009a-gps} but depends on the implementation). % \begin{equation} % \label{eq:mistunigLoss} % D_{F} = \left\vert \frac{\sin(\pi \Delta fT_{ci})}{\pi \Delta fT_{ci}} \right\vert % \end{equation} % The frequency mismatch loss sinc function, $D_{F}$, is evaluated in dB, % therefore for a loss of $\approx 0.98 \,\mathrm{dB}$, the frequency mismatch ought to be % $\Delta f = 250\, \mathrm{Hz}$, % due to the fact that the maximum loss shall occur when the frequency is differing % by 1/2 of the bin spacing. That is to say, for a bin space of 500 Hz, it is 250 Hz. ``The total range of possible GPS code delays is $1\, ms$. This is because the GPS C/A PRN code is $1 \,ms$ long, and then it repeats. The PRN code chipping rate is $1.023 \,\mathrm{MHz}$, and there are 1023 chips in the complete $1\, ms$ epoch'' \citep[Chapter 3]{diggelen2009a-gps}. %Size of the frequency %bin is inversely proportional to the ratio between the amplitude of the detected %peak and other non-peak values, %the smaller the bins are the higher the peak will be. For the purpose of better understanding, a segment of the frequency/code delay search space is shown in figure \ref{img:prnSearchSpace3d}. The peak implies the correct Doppler frequency and code delay have been found. In figure \ref{img:prnSearchSpace3d} smaller frequency bins have been used so that the concept becomes understandable to the reader. The speed of searching the 2D search space (finding the peak) depends on the complexity and strategy of the implemented algorithm \citep[Chapter 6]{9780817643904}. In the worst case, there are in total 102300 combinations in the search space, this can be derived from equation \eqref{eq:totalSearch}. \begin{equation} \label{eq:totalSearch} \mathrm{Search \, Space} = 50 \,\mathrm{(bins)} \cdot 1023\, \mathrm{(C/A \,codes)} \cdot 2\, \mathrm{(Phases\, per\, C/A\, chip)} \end{equation} % \begin{figure}[ht!] % \centering % \includegraphics[scale=0.50]{img/2DSearchSpace.pdf} % \caption{The total search space.} % \label{img:SearchSpace2d} % \end{figure} % The common strategy is to start searching from the middle frequency bins and to jump % up and down until the entire search space has been exhausted (first 500 Hz, % second -500 Hz, then in the 1000 Hz bin and then in the -1000 Hz bin), % as shown in figure \ref{img:freqSearch} % \citep[Chapter 3]{diggelen2009a-gps}. % This procedure is performed when no extra information are known by the receiver (almanac data % are missing), i.e. % first time the GPS receiver is turned on. It is known under the name of cold start. % % \begin{figure}[ht!] % \centering % \includegraphics[scale=0.50]{img/frequencySearch.pdf} % \caption{Idea of the frequency searching algorithm.} % \label{img:freqSearch} % \end{figure} There are three different working modes when it comes to finding a solution to the 2D search space problem. If no information is known, when some information is known and when almost all information is known. These three modes are known as \textit{cold}, \textit{warm} and \textit{hot} start. Cold start indicates the GPS receiver has no almanac, ephemeris, oscillator offset and time data. In this case it is the cold start and the GPS receiver needs to obtain all these information manually using the described steps in this chapter. Once the receiver obtains all these information, it stores them in its Electrically Erasable Programmable Read Only Memory (EEPROM). In order for the GPS receiver to track the satellites faster next time it is started, it uses the previously stored information (last known almanac, oscillator offset, time and position data). This new type of start, is known as a warm start, provided that the data in the receiver's EEPROM are not older than 180 days and its real time clock counter was constantly updated\footnote{The almanac data are valid for 180 days.}. This way the GPS receiver can use the previously saved information to estimate the rough position of the satellites, therefore the Doppler effects can be roughly estimated. As a consequence of the known Doppler effect, the frequency bins to search through to obtain the correlation peak are this time limited \citep[Chapter 3]{diggelen2009a-gps}. Hot start works in the same manner as warm start however, the ephemeris data and time data are precisely known (time is known in accuracy of sub-milliseconds). The process of finding user's position is explained in detail in appendix section \ref{sec:distanceAndPosition}. \section{Assisted GPS in wireless networks} \label{sec:agps} In the following paragraphs Assisted-GPS (AGPS) shall be presented and how it works. AGPS receivers work on the equivalent idea as warm/hot start on GPS receivers. Instead of loading the recently saved data from the EEPROM, an external information transfer medium is used to deliver the equivalent type of information that is known at the warm/hot start \citep{755159}, \citep{901174}, \citep{springerlink:10.1007/s10291-002-0028-0}. In this work, the external transfer medium is air and the information is transferred using electromagnetic waves. The existing GSM interface was utilised for the purpose of delivering the data to the smart phone with an AGPS receiver. The basic scenario can be seen in figure \ref{img:agpsPrinciple}. The BTS station is connected to the GPS reference station. The GPS reference station delivers the GPS data: exact time stamps; approximate location; satellite health as well as clock corrections; ionospheric and UTC model; almanac and ephemeris data (data transmitted by the GPS satellites). These data are then transmitted to the MS with a position request. \citep{springerlink:10.1007/s10291-002-0028-0}. \begin{figure}[hb!] \centering \includegraphics[scale=0.50]{img/A-GPS.pdf} \caption{Basic AGPS principle.} \label{img:agpsPrinciple} \end{figure} Time stamp is not used in GSM networks since it can be off by several seconds and would require additional equipment for synchronizing the network \citep{springerlink:10.1007/s10291-002-0028-0}, \citep{901174}. However in CDMA networks the time stamp is accurate to within $100 \, \mu s$ \citep{springerlink:10.1007/s10291-002-0028-0}. Approximate location is typically taken to be the location of the BTS from which the target AGPS receiver acquires the assistance data. Ephemeris and navigation data obtained from the GSM network provider help the smart phone to estimate its position. This method can greatly enhance the sensitivity of the receiver especially in urban environments \citep{springerlink:10.1007/s10291-002-0028-0}. Conventional GPS receivers require at least up to extra $18$ to $30\,s$ to receive and decode the navigation data and to generate a location fix \citep{springerlink:10.1007/s10291-002-0028-0}. The bit error rate associated with gathering and decoding data dramatically decreases since the acquired signals can be attenuated by $10$ to $20\, \mathrm{dB}$ indoors \citep{springerlink:10.1007/s10291-002-0028-0} of the nominal $-130 \,\mathrm{dB}$ on a $3\, dBi$ ``linearly polarized user receiving antenna\footnote{3 dBi antenna indicates an antenna with a gain of $3\, \mathrm{dB}$ with respect to an isotropic (omni-directional) antenna \citep[Chapter 2]{diggelen2009a-gps}.} (located near ground) at worst normal orientation'' \citep{GPS-Interface-Specification}. A simplified AGPS algorithm given in \citep{springerlink:10.1007/s10291-002-0028-0} will be presented. This algorithm benefits the more assistance data are known. As the first satellites are tracked, the AGPS algorithm has an estimation of the feasible region where the target AGPS user might be located. Consequently, this feasible region shall shrink until the location has been fully estimated \citep{springerlink:10.1007/s10291-002-0028-0}. \begin{enumerate}[(i)] \item Visible satellites and their positions are identified and computed out of the delivered ephemeris and time data. \item For each visible satellite $SV_i$, the code phase, $\tau_i$, is estimated. \item Pseudoranges are calculated for each visible satellite $SV_i$. \item Trilaterate the position out of the pseudoranges $\rho_i$. \end{enumerate} Although the AGPS algorithms can be seen as a set of equations with more unknown terms being known. It is straightforward to solve a set of equations when all the terms are known. However, without assistance information which provide additional information to the GPS receiver, it takes more time to obtain (decode) assistance data from the satellite message. The set of equations to be solved is described in detail in appendix section \ref{sec:distanceAndPosition}. Numerous AGPS algorithms exist, some do not require the exact time component and navigation data to be present in the assistance data \citep{998892}. \chapter{Radio Resource Location Protocol} \label{rrlpChapt} This chapter examines the Radio Resource Location Protocol (RRLP) and provides a description how it works inside of the GSM network. RRLP is a protocol from the family of Location Services (LCS) which were not part of the initial GSM standard. It is a widely used protocol in other cellular networks like UMTS, it was later introduced to the GSM system as well \citep{3GPPTS03.71}. It was developed by the request of government and rescue organizations to fulfill the wireless enhanced 911 standard in the US, each mobile user had to be located within a range of 300 m in 95\% of cases and within 100 m in 67\% of cases \citep{E911Accuracy}. The RRLP protocol supports three positioning techniques: E-OTD, UL-TDOA and AGPS \citep{3GPPTS03.71}. The LCS process can be divided into two separate stages, signal measurements and position estimation from the derived data in the previous stage. \section{RRLP Request} RRLP represents the connection/protocol between the Serving Mobile Location Center (SMLC) and the stand-alone handset, in this case the MS \citep[Chapter 5]{harper2010server-side}. SMLC is located on the BSC \citep{3GPPTS03.71}. SMLC' primary function is to manage the overall coordination and scheduling of resources required to perform the localization of the MS. SMLC controls the LMU's as well but since in this work no LMU were available this part can be skipped as well as the description of E-OTD and UL-TDOA localization. Before an attempt is made, of requesting the SMLC to initialize an RRLP request, an SDCCH connection channel has to be initialized to the MS, this connection can not be seen by the MS user\footnote{However, it is possible to take into consideration that something is going on the cell phone if the MS' battery is drained faster because an active RF connection drains the battery faster than a passive MS connected to the GSM network.}. \begin{figure}[ht!] \centering \includegraphics[scale=0.50]{img/RRLPRequest.pdf} \caption{RRLP Request protocol. Assistance data can be sent before the request is made. If the assistance data are sent, their reception acknowledgement is sent as a response from the MS. Image courtesy of \citep{harper2010server-side} and \citep{04.31V8.18.0}.} \label{img:RRLPReqProt} \end{figure} Data sent inside of a protocol are called Protocol Data Unit (PDU). On different layer levels PDUs may take a different shape and size because of the encapsulation or splitting \citep{kozierok2005the} \citep{stevens1994tcp/ip}. In RRLP the PDUs sent from the SMLC are not allowed be greater than 244 bytes\footnote{Bytes of 8 bits!} \citep{04.31V8.18.0}. Although the standard defines that larger packets ought to be split into smaller pieces in lower layers, in this work the rule of 244 bytes has been obeyed due to crashing of the GSM operating software, thus each PDU packet was not greater than 211 bytes. In the RRLP standard terms, the messages are entitled as \textit{components} and fields in the messages (components) are labeled as \textit{information elements} (IE) \citep{04.31V8.18.0}. The SMLC may send only the request for the position of the MS or it may assist the MS with assistance data required to estimate its position. In case of an AGPS request, assistance data may be ephemeris, almanac, accurate timing data or other assistance data that may help the receiver to estimate its position in a shorter period of time. The RRLP protocol is shown in figure \ref{img:RRLPReqProt}. Dashed lines represent optionally transmitted data like the assistance data. If assistance data are present, an acknowledgement or error will be produced by the MS after every RRLP assistance packet has arrived. Once the MS obtains the RRLP request, after a period of processing time, the MS will send its response back to the SMLC. The response may contain the position of the MS, an error IE indicating what assistance data are missing or a reason why the MS could not return its position \citep{04.31V8.18.0} \citep{49.031V8.1.0}. In the response IE, it is exactly indicated what type of data ought to be sent back to the MS so that it can complete the RRLP request and deliver its position. To save bandwidth space in the communication between the SMLC and MS, it can be proceeded in such a manner that first the RRLP request is sent out for the position estimation. If the MS requires some of the assistance data, it will send back a request for the required assistance data. In the next step the SMLC could send the required assistance data back to the MS and expect an successful response from the MS. However, in this work the author had a different approach, first all the RRLP assistance data were sent and then the RRLP position request. This approach was chosen over the other because in the GSM network operating software (OpenBSC), it was required to access the database and fetch the response. For the simple reason, since this system is a real time system, waiting for the database to respond may have corrupted the state machine of the GSM network and this would led to the malfunction and eventually failure of the complete network! The structure of the RRLP messages (requests, assistance data and response) is well defined using Abstract Syntax Notation One (ASN.1) in the technical specifications 3GPP 04.31 and ETSI TS 144 031 \citep{49.031V8.1.0} \citep{ETSITS144031}. ASN.1 is a conventional notation for denoting the abstract syntax of data used inside of protocols or data structures \citep[Chapter 8]{sharp2008principles} \citep{ITU-TX.680}. In other words, using ASN.1 it is possible to describe data in an independent representation of programming languages in which a protocol is implemented. In this section, only some of the mostly important and used parts of the RRLP protocol inside of the thesis shall be presented, more details can be found in the technical specifications \citep{49.031V8.1.0} \citep{ETSITS144031}. It is important to understand the meaning of ASN.1 types before proceeding with an RRLP example. A short summary for the used ASN.1 types elements will be provided parallely to the RRLP message structure. Structure of the RRLP message encoding for transmission can be seen in listing \ref{lst:RRLP}. The IE from listing \ref{lst:RRLP} are variables that can take certain values. The domain of these values is shown in listing \ref{lst:RRLPReq}. The explanation of listings \ref{lst:RRLP} and \ref{lst:RRLPReq} will follow in short after the reader has been introduced to the ASN.1 and RRLP message format standard. %Without the explanation it is not possible to understand the message structure %and build RRLP packets. Then it will be followed by an example of an RRLP request packet. A type of \textbf{SEQUENCE} is used to reference a ``fixed, ordered list of types (some of which may be declared to be optional); each value of the sequence type is an ordered list of values, one from each component type'' \citep{ITU-TX.691} while the IE (fields) of \textbf{OPTIONAL} type do not need to be included and are not mandatory. Variables defined by \textbf{CHOICE} are used to reference ``a list of distinct types; each value of the choice type is derived from the value of one of the component types'' \citep{ITU-TX.691}, i.e. only one element is selected from the list and the elements of the list are defined according to their variable type. Variables of type \textbf{ENUMERATED} are ``simple types whose values are given distinct identifiers as part of the type notation'' \citep{ITU-TX.691}. These simple types are used to distinguish a choice by identifying it with an incremented number from the previous element where the first element is always of value zero. Variables defined by \textbf{INTEGER} are of the ``simple type with distinguished values which are the positive and negative whole numbers, including zero (as a single value)'' \citep{ITU-TX.691}. At this point, the meaning of RRLP data elements marked in red, blue and orange from listing \ref{lst:RRLP} will be explained. To construct an RRLP PDU sequence (packet) these fields need to be known: \textit{referenceNumber} and \textit{RRLP-Component}. \textbf{referenceNumber} specifies the reference number of the request and is used for the purpose of identifying the response from the MS. It can take any value between 0 and 7. \newpage \begin{lstlisting}[label=lst:RRLP, caption={\textbf{Structure of the RRLP message in ASN.1.}}, backgroundcolor=\color{light-gray}, basicstyle={\scriptsize\ttfamily}, escapechar=@, emph={}, emphstyle=\color{crvena}, emph={[2]}, emphstyle={[2]\color{plava}}] RRLP-Messages -- { RRLP-messages } DEFINITIONS AUTOMATIC TAGS ::= BEGIN IMPORTS MsrPosition-Req, MsrPosition-Rsp, AssistanceData, ProtocolError FROM RRLP-Components -- { RRLP-Components } ; PDU ::= SEQUENCE { @\textcolor{red}{referenceNumber INTEGER (0..7),}@ @\textcolor{blue}{component RRLP-Component}@ } RRLP-Component ::= CHOICE { @\textcolor{narandzasta}{msrPositionReq MsrPosition-Req,}@ msrPositionRsp MsrPosition-Rsp, assistanceData AssistanceData, assistanceDataAck NULL, protocolError ProtocolError, ..., posCapabilityReq PosCapability-Req, posCapabilityRsp PosCapability-Rsp } END \end{lstlisting} \textbf{component} is of the type RRLP-Component, which is a CHOICE list. RRLP-Component is used for defining what type of information the packet shall include (assistance data, request, response, error, etc.). For this particular example one chooses \textbf{msrPositionReq} that is of type MsrPosition-Req (marked in orange in listing \ref{lst:RRLP}), with this information the MS knows that its position is requested. MsrPosition-Req is a SEQUENCE, consisting out of one mandatory and few optional IE elements. At this point only the first choice will be explained from listing \ref{lst:RRLPReq}, \textbf{PositionInstruct}. The rest of the provided choices are used later for the assistance data. The choices are dependent on what type of information is going to be included inside of the RRLP packets. \textbf{PositionInstruct} consists of five elements but four are mandatory: \textit{methodType}, \textit{positionMethod}, \textit{measureResponseTime} and \textit{useMultipleSets}. They can be seen in the listing \ref{lst:RRLPReqData}. These four elements are the most compact representation of an inquiry for the MS to differentiate between all the possible position measurements it could perform, how long it is allowed to measure the position (time duration) and how many position estimations it is allowed to perform. If it is allowed to perform more position estimations then all of them will be included in the returned response. \newpage \begin{lstlisting}[label=lst:RRLPReq, caption={\textbf{Structure of the RRLP request in ASN.1.}}, backgroundcolor=\color{light-gray}, basicstyle=\scriptsize\ttfamily] -- Measurement Position request component MsrPosition-Req ::= SEQUENCE { positionInstruct PositionInstruct, referenceAssistData ReferenceAssistData OPTIONAL, msrAssistData MsrAssistData OPTIONAL, systemInfoAssistData SystemInfoAssistData OPTIONAL, gps-AssistData GPS-AssistData OPTIONAL, extensionContainer ExtensionContainer OPTIONAL, ..., -- Release 98 extension element rel98-MsrPosition-Req-extension Rel98-MsrPosition-Req-Extension OPTIONAL } \end{lstlisting} \textbf{methodType} defines where the position estimation calculation will be executed. Does it solely take place on the MS (\textit{msBased}), on the server\footnote{With server the BTS location is meant!} only (\textit{msAssisted}), or one method is preferred over the other depending if the MS can execute the preferred one method (\textit{msBasedPref} or \textit{msAssistedPref}). The uncertainty of the accuracy of the estimated position is only optional if the chosen method is \textit{msAssisted}, otherwise it must be included in the request message. This uncertainty of the accuracy, is an integer number and defines how certain the accuracy of the returned position has to be. It can be calculated using the equation \eqref{eq:uncerAccuracy}, where $K$ is the seven bit integer number and $r$ is the accuracy uncertainty in meters \citep{3gppequations}. The next three parameters to be defined are the position estimation technique (GPS, E-OTD or one of the two preferred by the MS), the position measurement time and how many measurements the MS has to report back to the SMLC. Since in this thesis the author exploits the AGPS method, GPS is chosen for \textbf{PositionMethod}. \textbf{MeasureResponseTime} is a three bit integer value that corresponds to the time period the MS is allowed to perform the position estimation. Otherwise, if it takes longer the MS to report back than the specified time period, the MS is allowed to disconnect (close the SDCCH channel) without responding back. This time period can be calculated using the equation given in \eqref{eq:responseTime}, where $N$ is the number of seconds the MS is allowed to perform the position estimation. After the ASN.1 parameters of an RRLP request have been understood, they can be chosen and set according to the position measurement request which the network operator wants to perform. In the next step the RRLP packet shall be encoded from ASN.1 notation to the Packed Encoding Rules (PER) notation. PER is one of the telecommunication standards used for encoding and decoding messages inside of protocols specified in the ASN.1 notation \citep{ITU-TX.691}. \begin{equation} \label{eq:uncerAccuracy} r=10((1.1)^{K}-1) \end{equation} \begin{equation} \label{eq:responseTime} MeasureResponseTimeBitValue=\frac{ln(N)}{ln(2)} \end{equation} \newpage \begin{lstlisting}[label=lst:RRLPReqData, caption={\textbf{Structure of the data types from RRLP request in ASN.1.}}, backgroundcolor=\color{light-gray}, basicstyle=\scriptsize\ttfamily] -- Position instructions PositionInstruct ::= SEQUENCE { -- Method type methodType MethodType, positionMethod PositionMethod, measureResponseTime MeasureResponseTime, useMultipleSets UseMultipleSets, environmentCharacter EnvironmentCharacter OPTIONAL } -- MethodType ::= CHOICE { msAssisted AccuracyOpt, -- accuracy is optional msBased Accuracy, -- accuracy is mandatory msBasedPref Accuracy, -- accuracy is mandatory msAssistedPref Accuracy -- accuracy is mandatory } -- Accuracy of the location estimation AccuracyOpt ::= SEQUENCE { accuracy Accuracy OPTIONAL } -- The values of this field are defined in 3GPP TS 03.32 (Uncertainty code) Accuracy ::= INTEGER (0..127) -- Position Method PositionMethod ::= ENUMERATED { eotd (0), gps (1), gpsOrEOTD (2) } -- Measurement request response time MeasureResponseTime ::= INTEGER (0..7) -- useMultiple Sets, FFS! UseMultipleSets ::= ENUMERATED { multipleSets (0), -- multiple sets are allowed oneSet (1) -- sending of multiple is not allowed } \end{lstlisting} PER is intended for use in circumstances where minimizing the bit length of values that can be represented is of major concern \citep{ITU-TX.691}. In other words, it compresses the data in the PDU packets by limiting the bit field length to the minimal number of bits required to represent the lowest and highest variable values. For instance to represent 8 distinct values between 0 and 7 or -1 and 6, at least three bits are required. There are two variations of PER, aligned and nonaligned \citep{ITU-TX.691}. In the RRLP protocol the nonaligned type of PER is used. The major difference between aligned and nonaligned PER lies in the fact that some data structures are aligned on octet boundaries in aligned PER, i.e. there are some wasted padding bits which are set to zero if not used according to the size of the packets. Construction of the RRLP request query is straightforward. The chosen values are simply concatenated into a binary string. A simple RRLP request in PER encoded form is shown in figure \ref{img:RRLPReqExplained}. As an illustration, in figure \ref{img:RRLPReqExplained} the bits have been colored with distinguishable colors with the intention to recognize easier the different variables in ASN.1 notation. The six red zeros define what type of data will be included in the current RRLP packet. This will become obvious by looking at the listing \ref{lst:RRLPReqPER}. On the left side of listing \ref{lst:RRLPReqPER} one can see the PER notation, whereas on the right side is the ASN.1 notation. After the concatenation it can be converted to the desired notation system (binary, hexadecimal, etc.). In this particular example, the RRLP request, can be represented in hexadecimal notation: \textbf{400178F8}. This RRLP message (packet) is transmitted to the MS via the opened SDCCH channel. However, before sending this request the assistance data can be sent. In the following section \ref{sec:rrlpassistance} more details of how assistance data are sent shall be provided. \begin{figure}[ht!] \centering \includegraphics[scale=0.70]{img/RRLPReqExplained.pdf} \caption{An example of constructing an RRLP request. Image courtesy of \citep{harper2010server-side}.} \label{img:RRLPReqExplained} \end{figure} \begin{lstlisting}[label=lst:RRLPReqPER, caption={\textbf{Encoding an RRLP request from ASN.1 to PER.}}, backgroundcolor=\color{light-gray}, escapechar=@, basicstyle=\scriptsize\ttfamily] RRLP Message: 40 @\textcolor{tamnozelena}{\textbf{010}}@..... referenceNumber = 2 component: ...@\textcolor{ljubicasta}{\textbf{0}}@.... Extension of RRLP-Component = 0 :Absent ....@\textcolor{blue}{\textbf{000}}@. RRLP-Component = 0 :msrPositionReq MsrPosition-Req: .......@\textcolor{ljubicasta}{\textbf{0}}@ Extension of MsrPosition-Req = 0 :Absent 01 @\textcolor{red}{\textbf{0}}@....... referenceAssistData = 0 :Absent .@\textcolor{red}{\textbf{0}}@...... msrAssistData = 0 :Absent ..@\textcolor{red}{\textbf{0}}@..... systemInfoAssistData = 0 :Absent ...@\textcolor{red}{\textbf{0}}@.... gps-AssistData = 0 :Absent ....@\textcolor{red}{\textbf{0}}@... extensionContainer = 0 :Absent PositionInstruct: .....@\textcolor{red}{\textbf{0}}@.. environmentCharacter = 0 :Absent MethodType: ......@\textcolor{tamnozelena}{\textbf{01}}@ MethodType = 1 :msBased Accuracy: 78 @\textcolor{blue}{\textbf{0111100}}@. Accuracy = 60 PositionMethod: .......@\textcolor{red}{\textbf{0}}@ PositionMethod = 1 :gps F8 @\textcolor{red}{\textbf{1}}@....... MeasureResponseTime: .@\textcolor{tamnozelena}{\textbf{111}}@.... MeasureResponseTime = 7 UseMultipleSets: ....@\textcolor{blue}{\textbf{1}}@... UseMultipleSets = 1 :oneSet .....@\textcolor{ljubicasta}{\textbf{000}}@ Spare Bits = 000b \end{lstlisting} \section{RRLP Assistance data} \label{sec:rrlpassistance} Assistance data are of the most important value when it comes to AGPS response time. If the assistance data are present, the response time may be shorter since the AGPS receiver knows the orbital information of the satellites and the exact time which allows the AGPS to find ``immediately'' the Doppler frequencies and phase shifts of the visible GPS satellites. In the assistance data packets, same as in the request packet, one has to specify what type of assistance information is included in the RRLP assistance packets. In this thesis, as assistance data, only the almanac, ephemeris, UTC model, ionospheric model and reference location are transmitted to the MS. There are also other assistance data like Differential GPS corrections (DGPS), real time integrity, acquisition assistance and reference time but none of these were available to the author, so they were avoided. The reasons for not including them are of cost and complexity nature. DGPS corrections give additional accuracy to the GPS positioning, then the accuracy varies between $1-3$ m \citep{489522}, however they are rarely used \citep[Chapter 4]{harper2010server-side}. Real time integrity is a list of satellites the AGPS receiver is not allowed to use in its position estimation because they have integrity problems \citep[Chapter 4]{harper2010server-side}. This helps the AGPS receiver to know why assistance data for satellites with errors are not included in the ephemeris or almanac data as well as to be aware of not using the old ephemeris or almanac cached data instead \citep[Chapter 4]{harper2010server-side}. Reference time can be considered as the ``most valuable'' data for the MS because it provides ``exact time'' to the AGPS receiver. This helps the AGPS receiver to better estimate the phase shift required to detect GPS signals. This phase shift estimation in return allows the AGPS receiver better integration period $\tau$ to detect weaker signals in cities or buildings %(see section \ref{sec:SigDemod} %and page \pageref{sec:CAdemod} for better understanding) \citep[Chapter 4]{harper2010server-side}. By knowing the reference time, it is straightforward for the AGPS receiver to predict the TLM and HOW starting words of the transmitted GPS packets from the satellites %(refer to section \ref{sec:gpsDataAndSignal}) required for synchronization and distance calculation. Reference time data can include the relationship between the GSM network and GPS time, as well as the GSM frame number to help the MS synchronize with the BTS (this was described earlier as time synchronized GSM networks which is required for methods like E-OTD) \citep[Chapter 4]{harper2010server-side}. Acquisition assistance data, as the name itself indicates provides the AGPS receiver directly with acquisition data. Acquisition data are the Doppler frequencies and phase shifts precalculated on the BTS for the MS. If this type of data are provided to the AGPS receiver, it does not require to compute and search on its on for Doppler frequencies and phase shifts from the provided reference time \citep[Chapter 4]{harper2010server-side}. This would speed up the process of getting a position and would help weak signals to be detected which in return would minimize the reception errors. As listed above, almanac, ephemeris, UTC model, ionospheric model and reference location are transmitted to the MS. Reference location is the location of the BTS and provides the MS with an proximate location which can be used for the position determination in equations given in appendix section \ref{sec:distanceAndPosition}. Furthermore, this limits the search space in time and frequency domain for satellites to lock on. For an illustration, if the AGPS receiver has access to these data it can not expect to see satellites which send signals on the opposite side of the Earth \citep[Chapter 4]{harper2010server-side}. With the reference location, one sends also the altitude and uncertainty of the included location data. As a consequence the AGPS receiver can limit the time and frequency search space even further. The ionospheric model includes data for correcting errors introduced by the radio wave transmission through the ionosphere \citep[Chapter 4]{harper2010server-side}. Ionosphere data are not satellite dependent thus they are not sent for each satellite separately but only once since they are valid for all satellites \citep[Chapter 4]{harper2010server-side}. Ephemeris data in RRLP terminology are named as navigation data. Ephemeris data contain more precise and accurate orbital information of the satellites. If the reader is interested in the exact description of the transmitted assistance data, they can be seen in the appendix, in following tables \ref{tbl:utcModel}, \ref{tbl:navMessage}, \ref{tbl:almanacMessage} and \ref{tbl:ionoModel}. \begin{lstlisting}[label=lst:GPSAssisData, caption={\textbf{Structure of data types of GPS assistance data in ASN.1.}}, backgroundcolor=\color{light-gray}, basicstyle=\scriptsize\ttfamily] -- Control header of the GPS assistance data ControlHeader ::= SEQUENCE { -- Field type Present information referenceTime ReferenceTime OPTIONAL, refLocation RefLocation OPTIONAL, dgpsCorrections DGPSCorrections OPTIONAL, navigationModel NavigationModel OPTIONAL, ionosphericModel IonosphericModel OPTIONAL, utcModel UTCModel OPTIONAL, almanac Almanac OPTIONAL, acquisAssist AcquisAssist OPTIONAL, realTimeIntegrity SeqOf-BadSatelliteSet OPTIONAL } \end{lstlisting} The packets are constructed in the same form as RRLP requests however, with a slight difference of selecting other RRLP components and including assistance data. In this particular example, only a packet with the reference location shall be presented, a ``complete'' 211 bytes PDU packet constructed by author's software would require at least four pages to be shown. Instead of RRLP request (\textit{msrPositionReq}) in \textbf{RRLP-Component} one has to choose assistance data (\textit{assistanceData}) (for the purpose of better understanding in this listening different colors have been used, this particular difference was bolded in listing \ref{lst:RRLPAssisPER}). Afterwards, one needs to specify for what positioning technique assistance data will be included, in this case it is GPS assistance data (\textit{gps-AssistData}, marked in red color in listing \ref{lst:RRLPAssisPER}). The assistance data will be listed in the order specified by the RRLP standard, listing \ref{lst:GPSAssisData}: reference time, reference location, DGPS corrections, navigation model, ionospheric model, UTC model, almanac, acquisition assistance and real time integrity (all marked with blue color in listing \ref{lst:RRLPAssisPER}). \begin{lstlisting}[label=lst:RRLPAssisPER, caption={\textbf{Encoding reference location from ASN.1 to PER.}}, backgroundcolor=\color{light-gray}, basicstyle=\scriptsize\ttfamily, escapechar=@, emph={gps-AssistData}, emphstyle=\color{red}, emph={[2]referenceTime,refLocation,dgpsCorrections, navigationModel,ionosphericModel,utcModel,almanac,acquisAssist,realTimeIntegrity}, emphstyle={[2]\color{blue}}] RRLP Message: 44 010..... referenceNumber = 2 component(RRLP-Component): ...0.... Extension of RRLP-Component = 0 :Absent @\textbf{....010.}@ @\textbf{RRLP-Component}@ @\textbf{=}@ @\textbf{2}@ @\textbf{:assistanceData}@ AssistanceData: .......0 Extension of AssistanceData = 0 :Absent 11 0....... referenceAssistData = 0 :Absent .0...... msrAssistData = 0 :Absent ..0..... systemInfoAssistData = 0 :Absent ...1.... @\textcolor{red}{gps-AssistData}@ = 1 :Present ....0... moreAssDataToBeSent = 0 :Absent .....0.. extensionContainer = 0 :Absent GPS-AssistData: ControlHeader: ......0. referenceTime = 0 :Absent .......1 refLocation = 1 :Present 00 0....... dgpsCorrections = 0 :Absent .0...... navigationModel = 0 :Absent ..0..... ionosphericModel = 0 :Absent ...0.... utcModel = 0 :Absent ....0... almanac = 0 :Absent .....0.. acquisAssist = 0 :Absent ......0. realTimeIntegrity = 0 :Absent RefLocation: threeDLocation(Ext-GeographicalInformation): .......0 @\textcolor{narandzasta}{Ext-GeographicalInformation length(octet)}@ = 13 :13 + 1 = 14 D9 1101.... ....1001 @\textcolor{narandzasta}{Ext-GeographicalInformation = 904445940594B200000707000700h}@ 04 00000100 . (binary data were removed because of length) 00 0000.... ....0000 Spare Bits = 0000b \end{lstlisting} The assistance data one wants to include in the RRLP packet have to be selected previously. Selecting is straightforward and one simply requires to set the appropriate bit to one (1=included in the packet, 0=not included in the packet). Since in this example only the reference location is included inside the RRLP PDU packet, the \textit{refLocation} bit is set to one. Once the variables have been set, the assistance data have to follow the given order as in listing \ref{lst:GPSAssisData}. The first selected variable (\textit{referenceTime}) would follow as the first and the last selected variable (\textit{realTimeIntegrity}) would be the last one included in the RRLP assistance PDU packet. The reference location has to be converted into an ellipsoid point with altitude and uncertainty ellipsoid as described in the standard \citep{3gppequations} under section \textit{7.3.6}. This is shown in figure \ref{img:refLocStandard} and described in the following paragraphs. \begin{figure}[ht!] \centering \includegraphics[scale=0.5]{img/ElipsoidPoint.pdf} \caption{Reference location is a 14 octet stream built according to the given rule as specified in the standard \citep{3gppequations} under section \textit{7.3.6}. Image courtesy of \citep{3gppequations}.} \label{img:refLocStandard} \end{figure} The reference location consists of longitude, latitude, altitude, uncertainty semi-major, uncertainty semi-minor, orientation of major axis, uncertainty of altitude and confidence level. \textbf{S} is sign of the latitude, it is set to zero if it is North and one if it is South. \textbf{D} is the altitude direction, it is set to zero if the altitude that follows is height (above mean sea level) and to one if it is depth (below mean sea level). Uncertainty semi-major and uncertainty semi-minor are uncertainties for longitude and latitude. Orientation of major axis is the orientation angle of the BTS between the major axis and North pole in degrees. These terms are depicted in figure \ref{img:earthElipsoid} by showing the World Geodetic System 1984 (WGS84). \begin{figure}[ht!] \centering \includegraphics[scale=0.5]{img/EarthElipsoid.pdf} \caption{World Geodetic System 1984. Image courtesy of \citep{harper2010server-side}.} \label{img:earthElipsoid} \end{figure} The latitude, longitude and altitude need to be encoded into a format recognized by the RRLP standard. This is straightforward and can be computed using the equations shown in \eqref{eq:latLong}, where $\varphi$ is the latitude and $\lambda$ is the longitude value in decimal degrees. The longitude is encoded as second compliment binary number \citep{3gppequations}. The altitude is encoded as it is, where one bit increments represent one meter increments. The uncertainties for latitude, longitude and altitude were not used since changing these variables did not affect the position estimation process. Orientation of major axis is not used in this work so it was set to zero, its modification did not affect the position estimation. Confidence describes the level by which the sent BTS reference location is known to be correct. The confidence is a 7 bit number but ought to take values between 0 and 100 since it represents a percentage. In this work it was set to zero, i.e. no information is available about the confidence for our reference location. It did not change the output behaviour from the MS. If the reference location is included in the RRLP assistance packet, it is important to specify the octet length of the reference location. The length of the reference location of an ellipsoid point with altitude and uncertainty ellipsoid is of 14 octets, as it can be seen from figure \ref{img:refLocStandard} (total number of rows). However, it is written as 13 octets in the RRLP PDU packet. Generally as a rule, it is always specified one number less since at least one octet has to be included in the reference location. There are other reference location standards inside of the RRLP protocol. Using this mechanism, the RRLP protocol knows where the data ends and where new data may start in case other assistance data follow. Which standard for defining the reference location was used, is included as well. It is defined by the first four bits of the reference location, in this case it is $1001$, as it can be seen from figure \ref{img:refLocStandard} in first row. This is an additional mechanism for error control, if the numbers do not match when the transmitted binary data have been decoded then the MS can return an error and ask for retransmission of the data. Information related to the reference location in the example listing \ref{lst:RRLPAssisPER} are marked with orange color. Once the assistance data have been transmitted to the MS, it will respond back with an acknowledgement or error. This response depends on the MS, if the data were correctly received and parsed. The acknowledgement is going to have the same reference number as the assistance packet which is not always the case for the error. In the next section, an RRLP response from the MS will be described and analysed. \begin{equation} \label{eq:latLong} \begin{array}{l} \begin{split} Lat = \frac{2^{23}}{90}\cdot\vert\varphi\vert \end{split} \quad\Longleftarrow\quad \begin{split} \mbox{Latitude} \end{split} \; \; \; \; \begin{split} Long = \frac{2^{24}}{360}\cdot\lambda \end{split} \quad\Longleftarrow\quad \begin{split} \mbox{Longitude} \end{split} \end{array} \end{equation} \section{RRLP Response} The RRLP response is constructed by the MS in the same manner as the RRLP request and assistance data by following ASN.1 rules precisely specified in the RRLP standard. The response may include the estimated position, data for estimating the position on the BTS (if MS-assisted method was chosen) or errors indicating that some of the assistance data are missing. Missing data and errors are specified inside of the RRLP response. The response data is PER encoded and requires to be decoded into the ASN.1 notation. For illustration, in listing \ref{lst:RRLPRespError}, an erroneous RRLP response is shown. To distinguish successful from erroneous responses, two different bits are used in the response message, \textit{locationInfo} and \textit{locationError}. The location error bit is set if the location of the MS is not present within the message (marked in red). The MS may include more information on the error if it can identify the error (newer models support this). In case the MS does support more information, an optional IE \textit{additionalAssistanceData} bit will be set (marked in cyan). \begin{lstlisting}[label=lst:RRLPRespError, caption={\textbf{Decoding an error RRLP response from Samsung Galaxy S3.}}, backgroundcolor=\color{light-gray}, basicstyle=\scriptsize\ttfamily, escapechar=@, emph={gps-AssistData}, emphstyle=\color{red}, emph={[2]referenceTime,refLocation,dgpsCorrections, navigationModel,ionosphericModel,utcModel,almanac,acquisAssist,realTimeIntegrity}, emphstyle={[2]\color{blue}}] RRLP Message: 42 010..... referenceNumber = 2 component(RRLP-Component): ...0.... Extension of RRLP-Component = 0 :Absent @\textbf{....001.}@ @\textbf{RRLP-Component}@ @\textbf{=}@ @\textbf{1}@ @\textbf{:msrPositionRsp}@ MsrPosition-Rsp: .......0 Extension of MsrPosition-Rsp = 0 :Absent 04 0....... multipleSets = 0 :Absent .0...... referenceIdentity = 0 :Absent ..0..... otd-MeasureInfo = 0 :Absent ...0.... locationInfo = 0 :Absent ....0... gps-MeasureInfo = 0 :Absent .....1.. @\textcolor{red}{locationError = 1 :Present}@ ......0. extensionContainer = 0 :Absent LocationError: .......0 Extension of LocationError = 0 :Absent 99 1....... @\textcolor{cyan}{additionalAssistanceData = 1 :Present}@ LocErrorReason: .0...... Extension of LocErrorReason = 0 :Absent ..0110.. @\textcolor{blue}{LocErrorReason = 6 :gpsAssDataMissing}@ AdditionalAssistanceData: ......0. Extension of AdditionalAssistanceData = 0 :Absent .......1 @\textcolor{magenta}{gpsAssistanceData = 1 :Present}@ 0B 0....... extensionContainer = 0 :Absent GPSAssistanceData: .000101. @\textcolor{narandzasta}{GPSAssistanceData length(octet)}@ = 5 :5 + 1 = 6 .......1 @\textcolor{narandzasta}{GPSAssistanceData = E80000000000h}@ . (binary data were removed because of length) 00 0000000. .......0 Spare Bits = 0b \end{lstlisting}\newpage In the case that more information of the error is known, it will be followed with a more detailed explanation of the error. For this particular example, not sufficient assistance data were present, \textit{LocErrorReason} (marked with blue color). There are other possible location error reasons as well. All location errors are listed in listing \ref{lst:RRLPPosError} (self-explanatory). Depending on the MS model, it can be even further specified what kind of GPS assistance data were missing. This is well specified by setting the IE \textit{gpsAssistanceData} bit, as shown in listing \ref{lst:RRLPRespError} (marked with magenta color). If this bit was set, the length of the IE for requested missing assistance data will be exactly specified as well as what assistance data are missing (marked in orange color). \begin{lstlisting}[label=lst:RRLPPosError, caption={\textbf{Possible location error reasons.}}, backgroundcolor=\color{light-gray}, basicstyle=\scriptsize\ttfamily] LocErrorReason ::= ENUMERATED { unDefined (0), notEnoughBTSs (1), notEnoughSats (2), eotdLocCalAssDataMissing (3), eotdAssDataMissing (4), gpsLocCalAssDataMissing (5), gpsAssDataMissing (6), methodNotSupported (7), notProcessed (8), refBTSForGPSNotServingBTS (9), refBTSForEOTDNotServingBTS (10), notEnoughGANSSSats (11), ganssAssDataMissing (12), refBTSForGANSSNotServingBTS (13) } \end{lstlisting} \begin{figure}[hb] \centering \includegraphics[scale=0.5]{img/ReqGPSAss.pdf} \caption{Requested AGPS assistance data to be delivered. Image courtesy of \citep{49.031V8.1.0}.} \label{img:RequestedGPSAss} \end{figure} The first two bytes of the IE \textit{GPSAssistanceData} contain the information for requested assistance data (marked in orange color). Information of missing assistance data can be seen in figure \ref{img:RequestedGPSAss} \citep{49.031V8.1.0}. If one of these bits from A to K is set, the MS requires more assistance data. The meaning of the bits in figure \ref{img:RequestedGPSAss} are explained in table \ref{tbl:RRLPReqAss}. In this particular example, the first two bytes are: \textbf{E800}, indicating acquisition assistance, reference time, reference location and the navigation model are requested by the MS as assistance data. The next RRLP response example, shown in listing \ref{lst:RRLPRespSucc}, is a response with a successfully estimated position! In the second byte, two mutually exclusive IE contain the information if the response was successful and contains the location information, \textit{locationInfo} bit must be set and \textit{locationError} must be zero (both marked in red color in listing \ref{lst:RRLPRespSucc}). \begin{lstlisting}[label=lst:RRLPRespSucc, caption={\textbf{Decoding a successful RRLP response from iPhone 3GS.}}, backgroundcolor=\color{light-gray}, basicstyle=\scriptsize\ttfamily, escapechar=@, emph={gps-AssistData}, emphstyle=\color{red}, emph={[2]referenceTime,refLocation,dgpsCorrections, navigationModel,ionosphericModel,utcModel,almanac,acquisAssist,realTimeIntegrity}, emphstyle={[2]\color{blue}}] RRLP Message: 42 010..... referenceNumber = 2 component(RRLP-Component): ...0.... Extension of RRLP-Component = 0 :Absent @\textbf{....001.}@ @\textbf{RRLP-Component = 1 :msrPositionRsp}@ MsrPosition-Rsp: .......0 Extension of MsrPosition-Rsp = 0 :Absent 11 0....... multipleSets = 0 :Absent .0...... referenceIdentity = 0 :Absent ..0..... otd-MeasureInfo = 0 :Absent ...1.... @\textcolor{red}{locationInfo = 1 :Present}@ ....0... gps-MeasureInfo = 0 :Absent .....0.. @\textcolor{red}{locationError = 0 :Absent}@ ......0. extensionContainer = 0 :Absent LocationInfo: .......1 gpsTOW = 1 :Present FF 11111111 refFrame = 65535 FF 11111111 61 01100001 gpsTOW = 6399000 A4 10100100 18 00011000 FixType: B6 1....... FixType = 1 :threeDFix posEstimate(Ext-GeographicalInformation): .01101.. @\textcolor{narandzasta}{Ext-GeographicalInformation length(octet)}@ = 13 :13 + 1 = 14 ......10 @\textcolor{narandzasta}{Ext-GeographicalInformation = 904445840594A6016316114F1D44h}@ . (binary data were removed because of length) 10 000100.. ......00 Spare Bits = 00b \end{lstlisting} If the IE \textit{locationInfo} bit is set and \textit{locationError} bit is zero, then the position of the MS is included in the response. Aside from the position information, the time when the position measurement was performed is included as well however, only the least significant bits in the range of milliseconds. The most significant bits ought to be derived by the SMLC using the GSM frame number, included in the IE \textit{refFrame}. In this thesis this is not known and used. \textit{refFrame} contains the GSM frame number as observed by the MS \citep{49.031V8.1.0}. The time of milliseconds can be found in the IE \textit{gpsTOW}. The included time is not in UTC format and would require additional conversions. The elements of \textit{locationInfo} can be seen in listing \ref{lst:RRLPLocInfo}. The IE \textit{fixType} contains the information if the performed measurement was 2D or 3D GPS fix. An 2D fix is when only 3 GPS satellites are used to estimate the position, the GPS receiver assumes it is on the earth surface located with the most recent known altitude from cache \citep{understandGPS}. 3D fix is a sign of at least 4 GPS satellites have been used to perform the position estimation \citep{understandGPS}. The position information is extracted with the inverse process as it was specified for the reference location, the reading is in the same format as earlier in figure \ref{img:refLocStandard}. Equations to return from the PER bit format to decimal degrees are given in equation \eqref{eq:latLongBack}. %\clearpage In the next chapter, more details are revealed how it was implemented. \begin {table}[ht] \caption{Requested AGPS assistance data bit meaning. Table courtesy of \citep{49.031V8.1.0}.} \label{tbl:RRLPReqAss}\centering %\rowcolor{2}{light-gray}{} \scriptsize\fontfamily{iwona}\selectfont \begin{tabular}{llll} \toprule %$D$&&$P_u$&$\sigma_N$\\ \textbf{Bit (IE)} & \textbf{Description}&\textbf{Bit (IE)} & \textbf{Description}\\\toprule $A$&Acquisition assistance requested&$G$&UTC model requested\\\midrule $B$&Reference time requested&$H$&Almanac data requested\\\midrule $C$&Reference location requested&$I$&Real time integrity requested\\\midrule $D$&DGPS corrections requested&$J$&Ephemeris extension requested\\\midrule $E$&Navigation model requested&$K$&Ephemeris extension check requested\\\midrule $F$&Ionospheric model requested \\\bottomrule \end {tabular} \end {table} \begin{lstlisting}[label=lst:RRLPLocInfo, caption={\textbf{Structure of data types of location info data in ASN.1.}}, backgroundcolor=\color{light-gray}, basicstyle=\scriptsize\ttfamily, escapechar=@] -- Location information IE LocationInfo ::= SEQUENCE { refFrame INTEGER (0..65535), -- Reference Frame number -- If refFrame is within (42432..65535), it shall be ignored by the receiver -- in that case the MS should provide GPS TOW if available gpsTOW INTEGER (0..14399999) OPTIONAL, -- GPS TOW fixType FixType, -- Note that applicable range for refFrame is 0 - 42431 -- Possible shapes carried in posEstimate are -- ellipsoid point, ellipsoid point with uncertainty circle, -- ellipsoid point with uncertainty ellipse, -- ellipsoid point with altitude and uncertainty ellipsoid posEstimate Ext-GeographicalInformation } FixType ::= INTEGER { twoDFix (0), threeDFix (1) } (0..1) \end{lstlisting} \begin{equation} \label{eq:latLongBack} \begin{array}{l} \begin{split} \varphi = \frac{90}{2^{23}}\cdot Lat \end{split} \quad\Longleftarrow\quad \begin{split} \mbox{Latitude in decimal degrees} \end{split}\\ \\ \begin{split} \lambda = \frac{360}{2^{24}}\cdot Long \end{split} \quad\Longleftarrow\quad \begin{split} \mbox{Longitude in decimal degrees} \end{split} \end{array} \end{equation} \chapter{Implementation} \label{Implementation} The aim of this chapter is to give the reader a review of the deployed hardware, testbed setup and the implemented software. The main ideas of author's approach how to attack the problem are discussed in this chapter as well as ways to deploy the RRLP protocol to obtain positions estimated on the smart phones. The testbed setup can be divided into two sections because two different hardware platforms were available to investigate. The first testbed setup was based on a platform without dedicated GSM hardware, whereas the second was based on dedicated GSM hardware. The second testbed setup can further be divided into two implementation stages. The first stage consists of the development of the application that generates RRLP assistance data. The second stage consists of modifying the existing open source GSM software by implementing the procedures for creating a data channel between the BTS and the MS. This channel was deployed for the transmission of assistance data to the MS and for obtaining the response from the MS. %\newpage \section{Undedicated GSM hardware testbed setup} Traditionally all radio communication systems are hard wired and the hardware is developed to do only one dedicated function. However, the author wanted to investigate if it is possible to obtain positions from smart phones without using expensive dedicated GSM hardware. On the other hand, instead of the dedicated hardware a Software Defined Radio (SDR) platform was used to emulate the GSM network. SDR is a hardware platform that enables the development and test of different radio communication systems as well as protocols using software that modifies the function of the hardware. In other words, the hardware may perform different functions in the range of its specified limitations. For an illustration those limitations can include the frequency range in which the SDR can transmit and receive radio waves; or the speed of sampling a radio wave signal. The basic idea is to use the fast performance of the CPU inside the computer to do the signal processing while the SDR hardware itself performs only the physical radio communication like emitting and receiving radio waves. Alternatively to the dedicated hardware, SDRs are cheaper and can be programmed to perform various functions e.g. an FM radio, a GPS receiver, GSM and etc. All of the stated ``emulated devices'' employ different modulation/demodulation techniques and frequency spectrums \citep{fmRadio} \citep{openBTS}. \subsection{Universal Software Radio Peripheral} The exploited SDR platform in this thesis was the Universal Software Radio Peripheral (USRP) by Ettus Research. Particularly for USRP, there was an existing implementation of GSM and RRLP software. \subsection{OpenBTS and first tests} The GSM network software employed on USRP was OpenBTS, a Linux application written in C++ utilising the SDR platform to provide a GSM air interface \citep{openBTS}. Initially, the system was tested with 2G cell phones (Nokia 3310 and Siemens M50) and its correctness was verified. While the system was tested with smart phones, strange behaviour had been discovered. Occasionally the smart phones ($iPhones$ $3GS$ and $4$) did not detect the created GSM network with OpenBTS, i.e. the network could not be found in the search menu where all GSM networks in range are shown. The reason for this strange phenomenon may be found in the unstable operation of the cheap clock oscillator. However, the clock's instability issue can not be confirmed by the author due to the missing hardware equipment to measure the actual frequency and its deviation. Nevertheless, these findings were consistent with the results of the OpenBTS developers with similar clock issues\footnote{GSM not detecting station, USRP1, FA-SY1, WBX, DBS \url{http://www.ruby-forum.com/topic/1876696} as well as \url{http://gnuradio.org/redmine/attachments/219/fordummies.pdf}}. As previously the author stated in the GSM chapter, the clock oscillator for the BTS is not allowed to deviate more than $\pm$5 ppm (parts per million). This finding, that older cell phones like Nokia 3310 and Siemens M50 have rather less problems connecting to the GSM network than the newer cell phones suggest that newer generation cell phones are not robust and resistant to the timing deviation issues. The deployed RRLP module for OpenBTS was written by Kurtis Heimerl in two different programming languages, Erlang and Common Gateway Interface (CGI)\footnote{Kurtis Heimerl's code can be found on \url{https://github.com/ttsou/RRLP}.}. The new GSM system configuration with the RRLP module in OpenBTS was examined. The first observation and finding was that not a single smart phone could connect to the GSM network. The log files contained information why the smart phones could not connect to the GSM network. Time-outs triggered by OpenBTS were the main reason why the smart phones could not enter the GSM network. The time-outs were triggered while the smart phones tried to get a position fix after the RRLP request was delivered. This result may be explained by analysing at what stage in the protocol the RRLP requests were sent. The RRLP request was immediately sent after the paging request had been obtained by the MS. Contrary to smart phones, the 2G phones continued their normal operation after the RRLP request have been received. This was due to the fact that 2G phones did not understand the RRLP request and therefore they skipped it. This evidence justifies the time-out behaviour. When the option, for sending RRLP requests while the paging is in progress, was disabled, this problem was solved! Next step was to manually send the RRLP requests from the OpenBTS terminal to smart phones. Contrary to expectations, the smart phones occasionally received the RRLP request as an SMS message and did not provide any response. In the case, where the smart phones did not receive the RRLP request as an SMS message, there was still no response sent back by the smart phones. One of the consequences of such behaviour was that the RRLP could not be tested inside of this setup because the system itself was unstable and had an unpredictable behaviour. The conducted tests with OpenBTS thus lead to a logical decision to employ dedicated BTS hardware with a tested and calibrated clock oscillator only for GSM. On the other hand, the Erlang RRLP module was a starting point to understand the RRLP protocol. The generated assistance data packets by the RRLP module were used for comparison and as a template to build the author's RRLP assistance data generator. \section{Dedicated GSM hardware testbed setup} The hardware components will be introduced according to their importance in building an operational and functional GSM network with GPS localization capabilities. Firstly the nanoBTS shall be introduced since it is the main hardware component used for building a basic GSM network infrastructure. Then a short insight into the used GPS receiver shall be given followed by the testbed setup configuration with connection scheme. \subsection{GSM BTS - nanoBTS} In recent years, there has been an increasing interest in the deployment of private cellular networks in remote areas which led to the development of diverse ``low-cost'' GSM hardware solutions. According to ip.access\footnote{http://www.ipaccess.com}, the manufacturer of nanoBTS, their hardware product is deployed for coverage of ``hard-to-reach places, in-buildings, remote areas, marine, aviation and public spaces''. Our University GSM network consists of three nanoBTS stations. The deployed nanoBTS in author's thesis works in the 1800 MHz frequency range, for which the University of Freiburg had obtained a licence from the Federal Network Agency (German: $Bundesnetzagentur$). The transmission frequencies range between 1805-1880 MHz, with 200 kHz channel spacing and the maximum output power of +23 dBm ($\approx$200 mW), whereas the receiving frequencies lie in the range between 1710-1785 MHz \citep{nanoGSM2007brochure}. The Ethernet cable with power supply is required to power the BTS and to connect its operating software (OpenBSC). The other ports are used to extend the GSM network performance operation but are not relevant to the work presented in this thesis. \begin{figure}[ht!] \centering \includegraphics[scale=0.10]{img/nanoBTSPorts.jpg} \caption{nanoBTS with its antennas.} \label{img:nanoBTSPorts} \end{figure} To determine the working state of the nanoBTS, an indicator status LED is located on the left side of the five ports area. After the nanoBTS is connected to the power supply with the Ethernet cable, it changes its color and blink speed according to the state it is in. The states are given in appendix and can be seen in the table given in \ref{tbl:LEDStatus} \citep{installnanoBTS}. One of the key limitations of gathering more technical data and the critical aspect of this description lies in the fact that nanoBTS is not an open source hardware platform and ip.access does not offer more details on their product. The lack of systematic hardware analysis can be seen as a major drawback of working with the nanoBTS hardware. However, the given technical data are sufficient for reproducing and conducting the RRLP tests described in this thesis. \subsection{GPS Receiver - NL-402U} \label{sec:gpsDevice} The Navilock NL-402U GPS receiver is based on the u-blox UBX-G5000 single chipset and is a one chip solution \citep{ubxDatasheet}. Receiver tracking sensitivity is -160 dBm ($10^{-16}$ mW). The GPS receiver was used as an indicator of whether there is any GPS signal in the tested room. \subsection{Testbed setup configuration} \label{sec:hardwareConfig} %At least 4 network cables with RJ45 connectors were required %and one switch or hub connected to the Internet. It is important to carefully %proceed with the cabling of the nanoBTS and the Ethernet switch or hub, since wrong %wiring with the power supply unit (PSU) could damage one of the devices. In Figure \ref{img:connectionDiagram}, the junction points are label according to the used configuration setting. %The Ethernet cables between the switch/hub, %PSU and nanoBTS should not be longer than 100 m \citep{installnanoBTS}. Author's test system operated on the ARFCN 877 channel. ARFCN 877 corresponds to the uplink frequency of 1,783.2 MHz and a downlink frequency of 1,878.2 MHz, where the uplink direction represents the direction from the nanoBTS to the MS and downlink the opposite direction. The decision to use the ARFCN 877 channel was based on the fact that our University has the licence for the frequency spectrum where the specified channel lies. Particularly this channel has been selected because it was free, measurements were carried out with a spectrum analyser built on the USRP hardware. The set up, installation and configuration are discussed in appendix \ref{sec:instConf}. \begin{figure}[ht!] \centering \includegraphics[scale=0.4]{img/hardwareConnection} \caption{Cable configuration diagram.} \label{img:connectionDiagram} \end{figure} \newpage \subsection{OpenBSC and its original RRLP implementation} OpenBSC is an open source implementation of a GSM network software by Harald Welte et al. It was developed for experimentation and security research of the GSM networks \citep{obsc1}. OpenBSC is ``implementing the minimal necessary parts to build a small, self-contained GSM network'' \citep{obsc}. This self-contained GSM network consists of the following functional components: Base Station Controller (BSC), Mobile Switching Center (MSC), Home Location Register (HLR), Authentication Center (AUC), Visitor Location Register (VLR) and Equipment Identity Register (EIR). OpenBSC was developed in C and operates on Linux. OpenBSC binds to the BTS using the Abis or Abis/IP interface. At the moment OpenBSC supports Voice calls, SMS, handovers, support for multiple BTS and other features not of interest to this work. OpenBSC has an implemented module for transmitting RRLP requests, however without assistance data. This module was tested but without successfully obtaining a position from the MS. While the tests have been performed, no results were obtained due to a watchdog time-out produced by OpenBSC. In order to send an RRLP request in OpenBSC, a silent SMS would be sent to the cell phone followed by the RRLP request. Silent SMS is the equivalent of a normal SMS but without notifying the user of its reception \citep{silentSMS}. When the silent SMS is received on the cell phone, the message content is not displayed to the user nor is it stored in the SMS inbox. In other words, its arrival remains completely unknown to the user to whom it was sent \citep{silentSMS}. An acknowledgement is sent back to the GSM network operator that the MS received the silent SMS. The watchdog timer in OpenBSC has been triggered because the acknowledgement was not received within a certain time limit while the MS was attempting to obtain a GPS position. To overcome this problem another approach had to be taken by the author to send RRLP assistance data with position requests. This shall be further analysed and explained in detail in the following sections. \subsection{RRLP assistance data generator} At this point of the thesis, two different RRLP implementations on two different hardware platforms have been examined without successfully obtaining a GPS localization. The next step in the attempt to obtain GPS positions from the MS was to gain better understanding of the RRLP protocol and RRLP assistance data. The RRLP data generated by Heimerl's application did not produce valid assistance data. In order to publish the RRLP assistance data generator as open source to be extended further or ported to another programming language, it was required to be written in a programming language understandable to a wider audience. Since the RRLP data generator application is independent of the GSM operating software, it was sound to write the RRLP assistance data generator in C++. Another reason why C++ was taken is due to the fact that OpenBSC was written in C and OpenBTS in C++. The main tasks here can be split up down to: verification of assistance data existence in the download folder and its age, download of the assistance data, conversion of the data, verification of assistance data correctness, construction of RRLP packets according to the ASN.1 standard, its conversion to PER and lastly saving in the hexadecimal form in a text file. The hexadecimal form was chosen because immediately the generated assistance data could be compared and verified online\footnote{RRLP message parser http://www.3gpp-message-analyser.com/decoder/misc.htm.}. In the almanac and ephemeris files, downloaded from the Navigation Center of the US Coast Guard and Trimble, assistance data for 32 different GPS satellites are present. Contrary to expectations, Heimerl's code produced RRLP assistance data valid for only one satellite. The rest of the assistance data were duplicates of the assistance data for one satellite. At this stage, it was important to have a fully working RRLP assistance data generator. This generator would be subsequently used to examine the RRLP protocol once OpenBSC was modified to open a data channel for transmitting the assistance data with the RRLP position request. Heimerl's code, written in Erlang, had to be fully understood to build a working replica RRLP assistance data generator. It was used as a template with the specified RRLP conversion standard itself. The downloaded assistance data were in formats known as Receiver Independent Exchange format (RINEX) for ephemeris data and Yuma for almanac data. RINEX is a format to exchange raw satellite navigation data from GPS receivers with an ability to output the same raw data. Although almanac data can be in RINEX form as well, the almanac data found online were in the Yuma format. The files with assistance data had to be first properly parsed and then converted into the format specified in the standard by ETSI TS 144 031 \citep{ETSITS144031}. The data included in the ephemeris file also contained the UTC model, and the ionospheric model. Other operational data were included in the configuration file like the reference location data. More details on the operational data can be found in the software appendix configuration section \ref{sec:appendSoft}. Once all data have been successfully parsed and converted, they had to be verified to be in the specified range (domain) as in the standard. Afterwards, the converted and verified assistance data were combined into binary series of data according to the RRLP standard as described in chapter \ref{rrlpChapt}. If the assistance data packet size in binary format was not divisible by eight then additional padding zeros were added until this condition was satisfied. Better comprehension of the RRLP assistance data generator can be gained by looking at the flowchart in figure \ref{img:RRLPAlgFlowchart}. \begin{figure}[ht] \centering \includegraphics[scale=0.39]{img/algorithmRRLP.png} \caption{Flowchart for the RRLP assistance data generator.} \label{img:RRLPAlgFlowchart} \end{figure} \newpage Since the ephemeris data refresh every two hours, the most recent generated data are appended at the end of the ephemeris file for one day\footnote{This is performed by Trimble, whose ephemeris data were used.}. It was common that the ephemeris assistance data contained errors which had to be detected in the data range verification step. To avoid disruption in operation of the developed application, once data out of range were detected they are immediately substituted with data for the same satellite but with two hours older ephemeris data. If the AGPS receiver in the MS uses the ephemeris data from that particular satellite then the distance estimation is affected and may contain errors! This problem is well known and confirmed by different studies \citep{Stanford-Ephem-Errors} \citep{NASA-Ephem-Errors}. A solution to this problem is proposed in the future work section \ref{sec:futWork}. Once the assistance data have been generated, converted to hexadecimal notation and saved to a text file, they can be used by OpenBSC to be sent to the MS. The decision to save the data to a text file, instead of storing to the database, was made because OpenBSC is a real-time system. If the database does not respond OpenBSC' real-time functionality might be lost and the system will malfunction. Since the text file is small and accessed only when an RRLP request is queued, it is faster than initializing the database driver, opening a socket connection to the database, making request queries to the database, obtaining the result and closing the socket connection. At this point, the assistance data are ready to be opened by OpenBSC and sent to the MS. \subsection{Creating a data channel in OpenBSC} To avoid the watchdog time-out triggered by OpenBSC when the RRLP requests have been sent originally, the solution was to create a dedicated data channel. The previously implemented approach by OpenBSC developers was to open a data channel with a silent SMS and then to send the RRLP request without any assistance data. However, this triggered always a time-out. The new approach, implemented by the author, can be split up into four steps: adding a command to launch an RRLP request; open a dedicated data channel (SDCCH) between the BTS and MS; open the text file generated with the RRLP assistance data generator in the previous step; send the RRLP packets; wait for the response from the MS and close the data channel. This will be explained in a sequential order of execution. The GSM network operator can connect to the Virtual Teletype (VTY) interface of OpenBSC using Telnet on port 4242 to issue commands and administer the GSM network. In order to send an RRLP requests from the VTY command interface, RRLP execution command had to be integrated. The function that integrates that command is named \textbf{\texttt{subscriber\_silent\_rrlp\_start()}} and is in the file \textit{vty\_interface\_layer3.c}. Four different commands can be executed by the operator from the VTY interface: RRLP request (send a position request without any assistance data); RRLP request with almanac data (send a position request with almanac as assistance data); RRLP request with ephemeris and other assistance data (send a position request with all available assistance data); or stop RRLP request (to stop the current execution of the RRLP request). Any of the first three commands, will call the function \textbf{\texttt{gsm\_rrlp\_operation\_start()}} in the file \textit{silent\_call.c}. Afterwards, the initializing of an SDCCH channel will start. Theoretically what takes place in background of this process, i.e. function \textbf{\texttt{gsm\_rrlp\_operation\_start()}}, was already discussed in \ref{sec:SDCCHChan}. For the particular situation, when the GSM operator can not wait for the RRLP response or wants to stop the execution of the RRLP request, the GSM operator can issue a command in the VTY interface to stop it, which will call the function \textbf{\texttt{gsm\_rrlp\_operation\_stop()}} in the file \textit{silent\_call.c}. If the channel was successfully opened, the function \textbf{\texttt{send\_rrlp\_req()}} will be executed which is responsible for opening the text file with parsed assistance data content, copying the content into the RRLP data structure and transmit it to the MS. The data structure is shown in \ref{lst:rrlpDatastructure}. The structure contains the length of the data packets, \textit{lengthOfPacket} as well as the content of the packets, \textit{packetContent} which never exceeds more than 211 bytes. \begin{lstlisting}[label=lst:rrlpDatastructure, caption={\textbf{Data structure containing the RRLP assistance data.}}, backgroundcolor=\color{light-gray}, basicstyle=\scriptsize\ttfamily, escapechar=@, emph={int, uint8_u, struct}, emphstyle={\color{ljubicasta}\bfseries}, emph={[2]int,lengthOfPacket,packetContent}, emphstyle={[2]\color{blue}}, emph={[3]gsm48_send_rr_app_info}, emphstyle={[3]\color{zelena}\bfseries}] struct rrlpPacket { int lengthOfPacket; uint8_u packetContent[211]; } \end{lstlisting} After the RRLP assistance data have been successfully loaded into the RRLP data structure, they are transmitted to the MS. In listing \ref{lst:sendingData} the function required to send assistance data is shown. The first arguments passed to the function provides the pointer to the opened SDCCH data channel connection. It is followed by the Application Protocol Data Unit identifier set to \texttt{0x00}. The third argument is the size of the transmitted packet. The last passed argument to the function is the starting address of the location where the packet content is located. Since there is more than one RRLP assistance packet to be transmitted, this function gets executed a few times in a loop defined by the packet counter variable \textit{packNum}. The responses sent back by the MS are obtained by the BTS and stored in the HLR database table \textit{ApduBlobs} in PER notation. A small utility was programmed to connect to the database, display the acquired data and the decoded position if it is contained in the RRLP response. \begin{lstlisting}[label=lst:sendingData, caption={\textbf{Function required to transmit assistance data.}}, backgroundcolor=\color{light-gray}, basicstyle=\scriptsize\ttfamily, escapechar=@, emph={int}, emphstyle={\color{ljubicasta}\bfseries}, emph={[2]int,lengthOfPacket,packetContent}, emphstyle={[2]\color{blue}}, emph={[3]gsm48_send_rr_app_info}, emphstyle={[3]\color{tamnozelena}\bfseries}] int response = gsm48_send_rr_app_info(conn, 0x00, AlmanacPackets[packNum].lengthOfPacket, AlmanacPacket[packNum].packetContent) \end{lstlisting} %Author's test system operated on the ARFCN 877 channel. ARFCN (Absolute Radio %Frequency Channel Number) defines the uplink and downlink channel frequency inside %the GSM network \citep{Richard2011Master}. ARFCN 877 corresponds to the uplink frequency %of 1,783.2 MHz and a downlink frequency of 1,878.2 MHz, where the uplink direction %represents the direction from the nanoBTS to the mobile stations and downlink the %opposite direction. The decision to use the ARFCN 877 channel was derived from %the fact that the channel was free, measurements were carried out with a %spectrum analyser built on the USRP hardware. \chapter{Results} In this chapter performed tests will be explained and how the results were obtained. Analysis of the results will be discussed as well as the geographical dislocation error will be shown. Smart phones used for the test are going to be introduced, followed by showing the location where the tests have been performed. After the results have been provided, a critical analysis demonstrates all the obstacles that may have emerged while the tests have been performed. The critical analysis may provide the answer why some results may be biased and it is a vital part of this thesis. It gives an additional insight into the complete operation of the built localization system in this thesis. %Aside from the given theoretical perspective of how AGPS works and why lack of %time synchronization inside GSM can be of critical value to correctly %evaluate the results. \section{Tests \& Results} \label{sec:tstRes} Although the main goal was to develop only a working positioning system, tests have been performed mostly inside of a closed building, inside of three different rooms in the mathematics computer pool of the University of Freiburg (German: $Mathematik$ $Rechenzentrum$) and outside of the computer pool. \subsection{Smart phones tested} The requirement for a cell phone to be considered for testing was its classification as a smart phone (having at least an AGPS receiver) and its availability (person's good will to share their smart phone for the purpose of testing). The following eleven models, shown in table \ref{tbl:smartphones} have satisfied the criterion and have been used to perform the tests. \begin {table}[ht] \caption{Smart phone models used for testing in the thesis.} \label{tbl:smartphones}\centering %\rowcolor{2}{light-gray}{} \scriptsize\fontfamily{iwona}\selectfont \begin{tabular}{llllll} \toprule %$D$&&$P_u$&$\sigma_N$\\ \textbf{No.}&\textbf{Cell phone} & \textbf{Manufacturer \& Country}&\textbf{No.}&\textbf{Cell phone} & \textbf{Manufacturer \& Country}\\\toprule 1&$Defy$&Motorola, USA&7&$Galaxy$ $Nexus$ $i9250$&Samsung, South Korea\\\midrule 2&$iPhone$ $4$&Apple, USA&8&$E71$&Nokia, Finland\\\midrule 3&$iPhone$ $3GS$&Apple, USA&9&$N95$&Nokia, Finland\\\midrule 4&$G1$&Google, USA&10&$Desire$ $S$&HTC, Taiwan\\\midrule 5&$Galaxy$ $S2$&Samsung, South Korea&11&$Blade$&ZTE, P.R. of China\\\midrule 6&$Galaxy$ $S3$&Samsung, South Korea \\\bottomrule \end {tabular} \end {table} \subsection{Performed tests} As stated in section \ref{sec:tstRes}, tests have been performed outside and inside of the computer pool building. Three different test modes were tried out, first only an RRLP request without any assistance data was sent. The second test included an RRLP request with almanac data only. The last test was an RRLP request with almanac, ephemeris, UTC model, ionospheric model and reference location data. The stated requests have been sent in an reverse order, to observe if the smart phones can actually exploit and benefit from the assistance data. The RRLP requests were manually sent from the Telnet interface from OpenBSC. Results delivered by the MS were stored in the database and the following analysis is based on the results. \begin{figure}[ht!] \centering \includegraphics[scale=0.3]{img/googlemapsResults.png} \caption{Test rooms as well as the results delivered by the smart phones. Image courtesy of Google Maps.} \label{img:googlemapsResults} \end{figure} The first tests took place on the ground-floor of the computer pool, in figure \ref{img:googlemapsResults} depicted with a green dot as Test room 1. The smart phones were horizontally lying on the table $50 cm$ away from the window in the first test and in the second test vertically parallel to the window. The results of two smart phones, $iPhone$ $3GS$ and $G1$, showed that their position did not make any influence on the test results. The delivered position coordinates in two performed tests were in range of the green rectangle labeled with a white one in the left corner. Although returned positions were points, rectangles had been used to depict the regions where the positions would appear for measured room test points. Two repeated measurements would yield a position in these rectangular areas. This might be considered as an precision ``problem'' of the GPS positioning system. According to Google Earth, Test room 1 has the following coordinates: latitude 48\textdegree 0'13.21"N and longitude 7\textdegree 50'53.53"E. The results were 5-20 m away from the real position according to Google Earth. The $iPhone$ $3GS$ sent only a response when assistance data have been delivered (almanac or almanac with ephemeris, UTC model, ionospheric model and reference location data), whereas the $G1$ only when the almanac data were provided as well as a simple RRLP request without assistance data. It is apparent from these facts that the $iPhone$ $3GS$ had used the assistance data to estimate its position. Otherwise the $iPhone$ $3GS$ would send its position back when only an RRLP position request was sent. Interestingly, the $G1$ did not provide any results when the ephemeris data have been delivered. These findings suggest that the AGPS receiver in $G1$ may suffer from not knowing how to employ the ephemeris data. This might be due to the fact that $G1$ is one of the first ``real'' smart phones on the market. Afterwards, evidence for smart phones not being able to utilise any of the assistance data, will be provided for other smart phones older than the $G1$. \begin{figure} ~ %add desired spacing between images, e. g. ~, \quad, \qquad etc. %(or a blank line to force the subfigure onto a new line) \centering \begin{subfigure}[b]{0.3\textwidth} \centering \includegraphics[height=\textwidth]{img/smartPhoneWindow.jpg} \caption{On the window.} \label{fig:window} \end{subfigure} ~ %add desired spacing between images, e. g. ~, \quad, \qquad etc. %(or a blank line to force the subfigure onto a new line) \begin{subfigure}[b]{0.3\textwidth} \centering \includegraphics[height=\textwidth]{img/smartRoomTable.jpg} \caption{On the table.} \label{fig:table} \end{subfigure} \caption{Test room 2 with the positions of the smart phones.}\label{fig:animals} \label{img:smartphonepositions} \end{figure} %\newpage The second tests took place in Test room 2. Test room 2 is located in the basement of the computer pool, with the following coordinates: latitude 48\textdegree 0'13.12"N and longitude 7\textdegree 50'53.50"E. The fact that the tests took place in the basement adds an additional obstacle to the AGPS receiver in the MS, the signal strengths of GPS signals are even weaker. The GPS signal strength was measured with an external GPS receiver connected to the computer and by its acquisition time it could be easily observed that the time required to track the satellites was much longer than in Test room 1. The results from Test room 2 are most valuable because they have provided additional evidence that even without line of sight it is possible to receive weak GPS signals and approximate the position. The line of sight was blocked by the surrounding buildings. The obtained results from Test room 2 can be seen in figure \ref{img:googlemapsResults}, two red rectangles labeled with a two in their left upper corner. It is somewhat surprising that different phone models delivered different positions (two different rectangle ranges) at different times of the day. This finding suggests that not an equal number of satellites may have been visible at the different time points when the tests were performed. By observing the results in figure \ref{img:googlemapsResults}, it is straightforward to see the deviations of the estimated positions, by comparing the tests performed in Test room 1 and 2. Albeit these two test rooms are geographically not far away from each other, the major difference is in their altitude and GPS signal strength reception. The estimated position deviation from the real position was dependent on GPS signal reception quality and satellites visibility. The majority of the performed tests in this work were performed in this room. Smart phones have been tested on the table which is $2 m$ away from the windows and on the window itself, as shown in figure \ref{img:smartphonepositions}. These small changes in position of the smart phone did not make any difference in the estimated position. The smart phones tested in Test room 2 are listed in table \ref{tbl:smartphones}. One unanticipated finding was that the ``newer generation'' smart phones did not deliver their position in any case but rather requested more assistance data like $iPhone$ $4$, $Galaxy$ $S2$ and $Galaxy$ $S3$. There are two possible explanations for this behaviour. This might be because the newer AGPS devices require more assistance data by relying on the network providers to have synchronized GSM systems or it is an security protection of the smart phone user. No information on the AGPS receiver chipset in the smart phones could be found online by the author. The previous two statements have to be considered with ambiguity. Another contrary to expectations, were the results with two Nokia ``smart phone'' models $E71$ and $N95$. The results were only delivered when an RRLP request was sent without any assistance data. Although it was stated in their specifications that both cell phones are equipped with an AGPS receiver \citep{nokiae71} \citep{nokian95}. However, RRLP requests with assistance data did not produce any output from these smart phones. The reason for this behaviour is not completely obvious but it might be due to the fact these are older models in comparison to other smart phones in the tests. At the time point when the two cell phones were released by Nokia the firmware for the phones might not have been fully developed since both models are from the same company. The third test took place in Test room 3, as shown in figure \ref{img:googlemapsResults} by the yellow dot. The third test room has the following coordinates: latitude 48\textdegree 0'12.26"N and longitude 7\textdegree 50'54.45"E. The smart phones were placed on the windows. In this room, the tested smart phones did not deliver any positions but only errors about missing assistance data and time-outs. While non of the smart phones delivered their position, the room was tested if a GPS position can be obtained with an external GPS receiver. The test was successful and after 12 minutes the position was obtained but the signal strength was weak according to the delivered GPS output. An implication emerging from this finding may be related to the GPS receiver high sensitivity (-160 dBm = $10^{−19}$ W) and an active patch antenna with a size of 2x2 cm \citep{ubxDatasheet}. The GPS receivers employed in smart phones have to be small in size to fit into the device and use a passive antenna because active antennas have an additional power consumption \citep{gpsAntenna}. To determine if the delivered results are taken from the cache or some other memory in the smart phone, the same test have been performed in the basement hallway where no windows exist right after the smart phones have successfully delivered their position in Test room 2. This test did not deliver any position but only time-outs or errors containing information that no satellites are visible. This test confirmed that the smart phones are always performing a position estimation at the moment when an RRLP request is sent to the MS. The last test has been carried out outside of the computer pool building. This test was conducted to confirm the argument that precision of the estimated position is related to the received GPS signal strength and number of visible satellites. As it can be seen in figure \ref{img:googlemapsResults}, the tests were performed at the blue dot and around it and the estimated positions were 1-5 m off of the real position. The estimated positions are shown in a blue rectangle with an O (letter O) in the left corner of it. \begin {table}[hb!] \caption{Smart phone RRLP test results from Test room 2.} \label{tbl:resultsByTest}\centering %\rowcolor{2}{light-gray}{} \scriptsize\fontfamily{iwona}\selectfont \begin{tabular}{lllll} \toprule %$D$&&$P_u$&$\sigma_N$\\ \textbf{Cell phone model}&\textbf{RRLP(E)}&\textbf{RRLP(A)}&\textbf{RRLP}&\textbf{Type of error (or missing data)}\\\toprule $Defy$&No&No&No&No response (time-out) \\\midrule $iPhone$ $4$&No&No&No&Reference time, Navigation Model,\\ &&&&Reference Location\\\midrule $iPhone$ $3GS$&Yes&Yes&No&/\\\midrule $G1$&No&Yes&Only occasionally&/\\\midrule $Galaxy$ $S2$&No&No&No&Acquisition Assistance\\\midrule $Galaxy$ $S3$&No&No&No&Reference Location, Reference Time,\\ &&&&Acquisition Assistance, Navigation Model\\\midrule $Galaxy$ $Nexus$ $i9250$&No&No&No&Did not respond, only ACKs\\\midrule $E71$&No&No&Yes&/\\\midrule $N95$&No&No&Yes&/\\\midrule $Desire$ $S$&Yes&No&No&/\\\midrule $Blade$&No&No&Yes&/ \\\bottomrule \end {tabular} \end {table} In table \ref{tbl:resultsByTest}, the list of all results from Test room 2 is shown. The abbreviations used in the table are explained in this paragraph. RRLP indicates the MS has delivered its position only when an RRLP position request without any assistance data has been sent. RRLP(E) indicates the MS has delivered its position only when an RRLP request contained almanac, ephemeris, UTC model, ionospheric model and reference location data has been sent. RRLP(A) indicates the MS has delivered its position when an RRLP request contained only almanac data. If there is no error description, then the smart phone delivered its position successfully. Otherwise, the stated data were requested by the smart phones. In case the positions were delivered by the smart phones, the waiting period was usually shorter than 3 minutes. The waiting time period of 3 minutes for the result is not discouraging provided that the assistance data like reference time (exact time, explained in section \ref{sec:rrlpassistance}) and acquisition assistance data (phase shift and Doppler effect frequency required by the AGPS, explained in section \ref{sec:rrlpassistance}) were not delivered to the MS. It is important to mention the strange behaviour by $Galaxy$ $Nexus$ $i9250$, the smart phone responded only with acknowledgements while the assistance data have been sent but after the reception it immediately closed the SDCCH channel. The $Blade$ closed the SDCCH channel after 4 transmitted assistance packets for the RRLP(E) test. The $Defy$ by Motorola did not produce any output at all and its behaviour was exact like of an 2G cell phone without a GPS receiver. To eliminate doubts and suspicion if the SDCCH channel was properly working and the generated time-outs were not by OpenBSC, 2G phones (Nokia 3310 and Siemens M50) have been used to perform the SDCCH test. An SDCCH channel has been initialized 10 times on different days with the 2G phones and left open for 10 minutes. The 2G phones reported the signal strengths of the initialized channel according to the defined standard. This provides a proof that if time-outs were generated, they were generated by the smart phones rather than OpenBSC. One important remark related to the tests has to be mentioned. Occasionally, $iPhone$ $3GS$ and $G1$ did not deliver their results the first time the RRLP request was sent but an time-out which lead to the disconnection of the SDCCH channel. Second time the same RRLP request were sent, the smart phones delivered their positions. This unexpected behaviour raises a suspicion that the smart phones do not behave according to the RRLP standard where it is well defined how much time they have to perform the localization. However, the previous statement ought to be considered with some uncertainty since it can not be proved without access to the hardware and firmware of the smart phones. The combination of described findings in this chapter and in table \ref{tbl:resultsByTest} provides some support for the premise that the RRLP standard is not yet a fully implemented standard by all manufacturers that claim AGPS functionality. Does the RRLP functionality depend on the AGPS chipset or RRLP itself, remains an open question. \section{Criticism of performed tests} Perhaps the most serious weakness of the presented results is that the author had no access to the firmware or the hardware of the MS while the tests have been performed. This would allow the author to see what type and how the assistance data are employed by the AGPS in the MS. If access could be gained, to the internal operation of the AGPS receiver, all doubts and bias about the deduced hypotheses could be eliminated. The whole system represents a black box where an input is delivered and an output is expected. Another drawback was the lack of hardware information inside of the MS (AGPS receivers and antennas). This does not allow an exact comparison between different cell phone models and if they can acquire any GPS signal in weak signal strength conditions like it was in Test room 3. Difficulties arise in assessment and comparing the results in this thesis with other relevant studies due to the lack of any research studies completed using the same hardware and equivalent type of assistance data. In the relevant studies different hardware test equipment is used while this thesis was carried out without that test equipment \citep{gpsTest2}. In addition, no research has been found that surveyed the amount of time required to get a position response from a MS where only almanac, ephemeris, UTC model, ionospheric model and reference location data have been delivered to the MS. Another limitation of the evaluated results lies in the fact that the tests have been only applied to the stated cell phones and it could not be tested with all possible models. The tests suffer from a major drawback as real time movement of satellites, the tests could not be conducted parallely but rather in serial manner in time. In other words, a satellite visible at the moment while the first test is being performed may not be visible the second time when the test is executed. The tests were performed in the morning 10:00-12:00 and in the afternoon 16:00-19:00, with morning being the period of day when it was difficult even for the external GPS device to track the satellites (by difficulty is meant the period of time required to get a position fix). GPS signal strength is vital for performing a position estimation due to the phase shift and Doppler frequencies. When the signal levels are lower than acquisition sensitivity of the GPS receiver inside the smart phone even assistance data can not help further. Antenna polarization and the position of the cell phone matter as well. Correctness of assistance data in almanac and ephemeris data can not be verified. The author had to rely and trust the Navigation Center of the US Coast Guard and Trimble as sources although errors were confirmed by different studies in \citep{Stanford-Ephem-Errors} \citep{NASA-Ephem-Errors}. Errors can be confirmed by the author in ephemeris data as well (URA values were out of specified range). These errors were not continual but appeared occasionally and these errors were inside of the assistance data provided by Navigation Center of the US Coast Guard (NVCS). Occasionally ephemeris data for some of the GPS satellites were missing as well. \section{Future work} \label{sec:futWork} The system could be extended with a GPS device that delivers raw GPS data instead of using the data provided by NVCS and Trimble. Obtained data by the GPS receiver could be compared to the data provided by NVCS or other GPS observation stations and verified for errors. By having more redundant sources of same information, mistakes in the GPS receiver output or transmission could be detected and eliminated since other sources of redundant data could indicate the correctness of assistance data. Another idea to extend this work would be to use an LMU and provide the reference time and acquisition assistance data. This feature would enhance the complete system. However, one ought to understand it would require large changes in the OpenBSC source code and interoperability between the BTS and LMU. Additionally, a tracking system of GSM users could be built by adding a timer that will trigger an RRLP request every few seconds or minutes. The successfully estimated positions could be considered as vertices on a map. By connecting vertices in succeeding manner, routes are created. Along the suggested idea, a machine learning algorithm ought to be used to process the path data and to predict the movement of GSM users for specific weekdays \citep{predictMovements}. After the machine learning algorithm has successfully learned the movement routes of the GSM user, the system could be used as an early warning system for the GSM user. For an illustration, if an GSM user takes one drive route every Monday and there is a traffic jam, an early warning SMS could be sent to the user to take another route. %Tests could be performed if it possible if it can be tricked out by the software Dennis mentioned (protect my privacy)! \chapter{Summary and security issues} %This thesis has investigated how difficult it is to integrate mobile assisted GPS localization in GSM %Networks. The aim of this work was set out to implement the ``first'' working open source RRLP %implementation in GSM networks, as well as to determine and evaluate the limits of this localization %technique. The research performed in this work has shown, it is not convoluted and burdensome to %estimate the position of GSM users even inside of buildings granted that required assistance %data can be provided by the GSM network operator. The findings of this study indicate that GSM users %of smart phones can be tracked accurately and precisely without their knowledge. An implication of these %evidence suggest it would be not complicated for German law enforcement agencies to employ this precise %surveillance technique to follow suspects. According to the German Interior Minister Hans-Peter Friedrich, %in 2011 silent SMS were employed with the UL-TDOA technique to track down suspects \citep{silentPolice} %\citep{silentPolice1}. The law is unclear if silent SMS can be considered communication taking into %consideration no information are sent to the GSM user and is a gray area from the legal point of view %\citep{silentPolice1}. "The state found that it was not one, since there is no content. This is useful, %because if it is not a communication, it does not fall under the framework of the inviolability of %telecommunications described in Article 10 of the German Constitution." said Mathias Monroy from %Heise Online \citep{silentPolice1}. The development of a working RRLP application and obtained %results from this work enhance the understanding of AGPS receivers and may be further used to %better understand how the assistance data influence the obtained results. %Finally, a number of important limitations in the obtained results need to be considered. %Not all assistance data were available and the tests have been performed at different time points of the day. %The amount of tested cell phones was not representative enough. However, this work has thrown up some %questions in need of further investigation but it is only a tip of the iceberg! A future study %investigating if further assistance data are provided to the cell phones would be very interesting. %The produced RRLP software and obtained results may be used to develop new strategies aimed at %protecting privacy of cell phone users. This thesis investigated the possibility to integrate mobile assisted GPS localization in GSM networks on undedicated and dedicated GSM hardware. The aim of this work was to implement the ``first'' working open source RRLP implementation in GSM networks, as well as to determine and evaluate the limits of this localization technique. Both goals were accomplished, a working RRLP protocol inside of data channels was successfully implemented. The evaluated results proved that out of 11 tested cell phone models, 6 successfully provided their GPS location. An analysis, with regards to accuracy and precision of the delivered positions, was discussed. The research performed in this work has shown that it is neither impossibly convoluted nor burdensome to estimate the position of GSM users even inside of buildings granted that required assistance data can be provided by the GSM network operator. The findings of this study indicate that GSM users of smart phones can be tracked accurately and precisely without their knowledge. One implication of this evidence is to suggest that it would not be complicated for German law enforcement agencies to employ this precise surveillance technique to follow suspects. According to the German Interior Minister Hans-Peter Friedrich, in 2011 silent SMS were employed with the UL-TDOA technique to track down suspects \citep{silentPolice}. The law is unclear if silent SMS can be considered communication when taking into consideration that no information is sent to the GSM user, and it remains a gray area from the legal point of view \citep{silentPolice}. "The state found that it was not communication, since there is no content. This is useful, because if it is not a communication, it does not fall under the framework of the inviolability of telecommunications described in Article 10 of the German Constitution." said Mathias Monroy from Heise Online \citep{silentPolice}. The development of a working RRLP application and the obtained results from this work enhance the understanding of AGPS receivers and may be further used to better understand how the assistance data influence the obtained results. Finally, a number of important limitations in the obtained results need to be considered. Not all assistance data were available, the tests were performed at different time points during the day, and the number of types of tested cell phones was not globally representative enough. This work has raised some questions in need of further investigation but it also illustrates that this is only a small revealed section of a larger hidden issue! A future study investigating the results of further assistance data being provided to the cell phones would be very interesting. The produced RRLP software and obtained results may be used to develop new strategies aimed at protecting the privacy of cell phone users. %\addcontentsline{toc}{chapter}{Dictionary of acronyms}