summaryrefslogtreecommitdiffstats
path: root/vorlagen/thesis/src/kapitel_x.tex
blob: d1736206cb34e4dc172b9b858178bfa47e217434 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
2375
2376
2377
2378
2379
2380
2381
2382
2383
2384
2385
2386
2387
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
2455
2456
2457
2458
2459
2460
2461
2462
2463
2464
2465
2466
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
2514
2515
2516
2517
2518
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568
2569
2570
2571
2572
2573
2574
2575
2576
2577
2578
2579
2580
2581
2582
2583
2584
2585
2586
2587
2588
2589
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
2608
2609
2610
2611
2612
2613
2614
2615
2616
2617
2618
2619
2620
2621
2622
2623
2624
2625
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635
2636
2637
2638
2639
2640
2641
2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660
2661
2662
2663
2664
2665
2666
2667
2668
2669
2670
2671
2672
2673
2674
2675
2676
2677
2678
2679
2680
2681
2682
2683
2684
2685
2686
2687
2688
2689
2690
2691
2692
2693
2694
2695
2696
2697
2698
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716
2717
2718
2719
2720
2721
2722
2723
2724
2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
2744
2745
2746
2747
2748
2749
2750
2751
2752
2753
2754
2755
2756
2757
2758
2759
2760
2761
2762
2763
2764
2765
2766
2767
2768
2769
2770
2771
2772
2773
2774
2775
2776
2777
2778
2779
2780
2781
2782
2783
2784
2785
2786
2787
2788
2789
2790
2791
2792
2793
2794
2795
2796
2797
2798
2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
2856
2857
2858
2859
2860
2861
2862
2863
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
2889
2890
2891
2892
2893
2894
2895
2896
2897
2898
2899
2900
2901
2902
2903
2904
2905
2906
2907
2908
2909
2910
2911
2912
2913
2914
2915
2916
2917
2918
2919
2920
2921
2922
2923
2924
2925
2926
2927
2928
2929
2930
2931
2932
2933
2934
2935
2936
2937
2938
2939
2940
2941
2942
2943
2944
2945
2946
2947
2948
2949
2950
2951
2952
2953
2954
2955
2956
2957
2958
2959
2960
2961
2962
2963
2964
2965
2966
2967
2968
2969
2970
2971
2972
2973
2974
2975
2976
2977
2978
2979
2980
2981
2982
2983
2984
2985
2986
2987
2988
2989
2990
2991
2992
2993
2994
2995
2996
2997
2998
2999
3000
3001
3002
3003
3004
3005
3006
3007
3008
3009
3010
3011
3012
3013
3014
3015
3016
3017
3018
3019
3020
3021
3022
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032
3033
3034
3035
3036
3037
3038
3039
3040
3041
3042
3043
3044
3045
3046
3047
3048
3049
3050
3051
3052
3053
3054
3055
3056
3057
3058
3059
3060
3061
3062
3063
3064
3065
3066
3067
3068
3069
3070
3071
3072
3073
3074
3075
3076
3077
3078
3079
3080
3081
3082
3083
3084
3085
3086
3087
3088
3089
3090
3091
3092
3093
3094
3095
3096
3097
3098
3099
3100
3101
3102
3103
3104
3105
3106
3107
3108
3109
3110
3111
3112
3113
3114
3115
3116
3117
3118
3119
3120
3121
3122
3123
3124
3125
3126
3127
3128
3129
3130
3131
3132
3133
3134
3135
3136
3137
3138
3139
3140
3141
3142
3143
3144
3145
3146
3147
3148
3149
3150
3151
3152
3153
3154
3155
3156
3157
3158
3159
3160
3161
3162
3163
3164
3165
3166
3167
3168
3169
3170
3171
3172
3173
3174
3175
3176
3177
3178
3179
3180
3181
3182
3183
3184
3185
3186
3187
3188
3189
3190
3191
3192
3193
3194
3195
3196
3197
3198
3199
3200
3201
3202
3203
3204
3205
3206
3207
3208
3209
3210
3211
3212
3213
3214
3215
3216
3217
3218
3219
3220
3221
3222
3223
3224
3225
3226
3227
3228
3229
3230
3231
3232
3233
3234
3235
3236
3237
3238
3239
3240
3241
3242
3243
3244
3245
3246
3247
3248
3249
3250
3251
3252
3253
3254
3255
3256
3257
3258
3259
3260
3261
3262
3263
3264
3265
3266
3267
3268
3269
3270
3271
3272
3273
3274
3275
3276
3277
3278
3279
3280
3281
3282
3283
3284
3285
3286
3287
3288
3289
3290
3291
3292
3293
3294
3295
3296
3297
3298
3299
3300
3301
3302
3303
3304
3305
3306
3307
3308
3309
3310
3311
3312
3313
3314
3315
3316
3317
3318
3319
3320
3321
3322
3323
3324
3325
3326
3327
3328
3329
3330
3331
3332
3333
3334
3335
3336
3337
3338
3339
3340
3341
3342
3343
3344
3345
3346
3347
3348
3349
3350
3351
3352
3353
3354
3355
3356
3357
3358
3359
3360
3361
3362
3363
3364
3365
3366
3367
3368
3369
3370
3371
3372
3373
3374
3375
3376
3377
3378
3379
3380
3381
3382
3383
3384
3385
3386
3387
3388
3389
3390
3391
3392
3393
3394
3395
3396
3397
3398
3399
3400
3401
3402
3403
3404
3405
3406
3407
3408
3409
3410
3411
3412
3413
3414
3415
3416
3417
3418
3419
3420
3421
3422
3423
3424
3425
3426
3427
3428
3429
3430
3431
3432
3433
3434
3435
3436
3437
3438
3439
3440
3441
3442
3443
3444
3445
3446
3447
3448
3449
3450
3451
3452
3453
3454
3455
3456
3457
3458
\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 shall 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 AGPS receivers inside of smart phones.


\newpage
\section{Positioning techniques}
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 
devolopment 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. 
For the purposes of this thesis, the term ``Mobile Station'' will be used to designate the user one intends to locate.  
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 Base Transceiver
Station (BTS), one can roughly estimate the position of the Mobile Station (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. Handover is the process of switching from one BTS to another where the signal reception strength
is higher than on the currently-connected BTS. 
The basic principle is shown in figure \ref{img:cellid}. 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. 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 where a mobile user can be connected to only one BTS.}
\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 since TA multiplied by the speed of light produces the radius distance
of the circle. 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 antennas than one, then the MS location can be even more precisely specified. 
This can still be inaccurate, however, because of multipath 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 Received Signal Strength (RSS) position estimation technique, as the name states,
uses the signal strength measurement reports to localize the MS. RSS measurement 
reports in GSM networks are transmitted from the MS to the BTS and they
are used to determine if the handover process should be triggered or not \citep{Richard2011Master}. 

\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 seperate 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 detecable 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 equiped 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 accure 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{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 and the introduction 
of 3G/4G networks. These networks are clock-synchronized since 
high-bandwidth wireless services require synchronous working operation \citep{oscilloquartz} \citep{3gNetworkSpeed}.
AGPS receivers can decrease the waiting time required to estimate the position if the 
``exact'' time is known \citep[Chapter 4]{diggelen2009a-gps}.
It works by exploiting the existing
navigation satellite network. 
In the event where mobile users are in urban environments, the GPS satellite signals are blocked
by the buildings. 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.
The theoretical foundation of how GPS and AGPS receivers estimate the position is addressed 
in more detail in chapter \ref{gpsTheoryChatper}.
This method does not work on every cell phone as do the aforementioned methods. 
It requires the cell phones to be equiped with an AGPS receiver.
From this point on, cell phones with an AGPS receiver shall be refered 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, that estimates the position, and the network provider since
it delivers the required data for faster acquisition time.

\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 develiver 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 
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}[tp!]
\caption{Overview of the localization techniques.}
\label{tbl:overviewLoc}\centering 
%\rowcolor{2}{light-gray}{}
\fontfamily{iwona}\selectfont
\begin{tabular}{clccc}
\toprule 
%$D$&&$P_u$&$\sigma_N$\\
Method&Sync.&Advantage\&Disadvantage&Accuracy&Type\\\toprule
\rowcolor{light-gray}Cell-ID& No& Works on any cell phone,& Anywhere in cell& Network\\
\rowcolor{light-gray}       &   &Imprecise&&\\%\midrule
Cell-ID + TA& No& Works on any cell phone,& Anywhere in cell& Network\\
       &   &Imprecise but better& but with a radius\\ 
       &   &than Cell-ID alone&\\%\midrule
\rowcolor{light-gray}RSS    & No& Works on any cell phone,& $\approx 300$ m& Network\\
\rowcolor{light-gray}       &   &Depends on cell phone&&\\
\rowcolor{light-gray}       &   &model and environment&&\\ %\midrule
E-OTD  &Yes& Works on most new& $\approx 50-200$ m& Handset\\
       &   &cell phone models,&\\
       &   &Expensive because LMU&\\ %\midrule
\rowcolor{light-gray}UL-TDOA&Yes&Works on any cell phone& $\approx 50-300$ m& Network\\
\rowcolor{light-gray}       &   &Expensive because LMU&&\\ %\midrule 
AGPS&Yes/No&Works on some cell& $\approx 5-20$ m& Hybrid\\
       &   &phones with AGPS&\\
       &   &receivers, Very precise&\\ %\midrule
\rowcolor{light-gray}AOA    &Yes&Works on any cell phone,& Depends if MS is& Network\\
\rowcolor{light-gray}       &   &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}

\clearpage
\section{Goals 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.
%This work may be perceived as pioneer work from authors perspective

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 used in this work. The last section is a discussion
of the achieved results in the test environment and the author's conclusions.

Chapters 2 and 3 will provide a theoretical introduction of GPS and AGPS receivers 
as well as of the GSM operational principles 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 GPS and GSM 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 set up
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 USB stick with the source code developed 
during the work on this thesis.


\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 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 milliard 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 how the data are modulated before transmission, 
demodulated on the receiver, how the search space works, how the target user position is estimated and
the errors that can influence the overall working of the system.



In this paragraph the general idea shall be given of how GPS works and how the position is estimated.
Before all the details are revealed in the following sections,
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 is also known as time-of-arrival (TOA) method.
Once sufficient amount of measurements from different satellites were generated, 
the position of the receiver can be approximated. 
It is important to understand that the positions from the satellites
need to be known and same location reference system has to be used.
The general principle of this idea can be seen in figure
\ref{img:GPSSimplePrinciple}, picture (a) represents the idea
with spheres in 3D space and picture (b) the same idea but in 2D space.
The blue, yellow and green wireframes below the GPS satellites represent the spheres 
for a given range, between the satellite and the estimated position of the GPS user
for the given satellite. 
By intersecting all the three spheres, the position of the user is estimated.
In the next sections this general idea shall be developed in more details,
in an step by step approach, and the ideas shall be verified using the appropriate mathematical
models. 

\clearpage
\section{GPS data and signal modulation}
\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 athmosphere, they need to be modulated in order for the GPS receiver
to receive and demodulate them. 

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 (HOW) word 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}.
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 as well as parameters
used for the clock corrections on the receiver side. More details on these
parameters shall be given in section \ref{sec:SigDemod}. Subframe two and three
are made of \textit{ephemeris data}. Ephemeris
information are precise parameters for predicting the precise orbital
position of the GPS satellite. Using ephemeris data for the specific
system time stamp and the equations given in appendix section \ref{sec:gpsConsAndEq} 
the GPS receiver can precisely estimate the position $(x_s,y_s,z_s)$ of
the satellite. 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}.
\begin{figure}[ht!]
  \centering
  \includegraphics[scale=0.50]{img/GPSSubframe.pdf}
  \caption{Subframes always start with telemetry and handover words}
\label{img:gpssubframe}
\end{figure}
Fourth and fifth subframes include \textit{almanac data}, low-precision clock corrections, 
ionospheric model and UTC time calculation parameters. Almanac information are
rough coarse parameters for predicting the orbital position of the GPS satellites.
These low-precision parameters are used by the GPS receiver to estimate the rough
position of the GPS satellites and to reduce the searching space for the GPS satellite
transmission frequencies\footnote{Although all satellites transmit on the same one frequency, 
when the signals are received on Earth, they have a different frequency
from the transmitted one. This shall be further explained in more details in the following sections \ref{sec:Carrierdemod},
\ref{sec:CAdemod} and \ref{sec:2dSearch}.} and
obtaining the precise ephemeris data.
Ionospheric model and UTC time calculation parameters are required
by the GPS receiver to refine the calculation of delays through
the ionosphere \citep{9780817643904}. 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. 
 
The data are modulated using the binary phase shift keying (BPSK) technique. The
newly modulated signal is the \textit{L1} signal and it is emitted from the satellite
directed antennas towards 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 and immunity to noise and signal intereference for the price of
transfering data at low speed rates \citep[Chapter 1]{9780849316579}. The demodulation process
of L1 shall be discussed and analysed seperately in section \ref{sec:Carrierdemod}.

\begin{figure}[ht!]
  \centering
  \includegraphics[scale=0.50]{img/BPSKModulation.pdf}
  \caption{BPSK Modulation - First 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 navigation data 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 to identify
which satellite signal is being decoded, transmission of the data on the same frequency
as well as to enable the distance measuring mechanism between the satellite and the GPS receiver. 
Equivalent PRN sequence is generated on the
GPS receiver and it is compared with the received PRN sequence which is delayed (shifted) 
due to the distance. 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. 
The second important property of PRN sequences is the property of
orthogonality. This proberty 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 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 and producing the L1 signal. More details shall be given in the
C/A demodulation section \ref{sec:CAdemod}. 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} and it 
can be represented in 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 given in \ref{eq:GPSSignalReceived2}. It
represents the same equation but at the GPS receiver after traveling $\approx 20200 \, km$, where $d_{C/A}$
is the C/A data and $n(t)$ is the random noise at moment $t$ influenced by various factors that influence
electromagnetic waves.
\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}
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).
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.





\newpage
\section{GPS signal acquisition and demodulation}
\label{sec:SigDemod}
GPS satellites\footnote{Ssatellites are named as space vehicles 
in GPS terminology and the abrevation 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 equiped 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, refered 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\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}.}
and wave propagation, the transmitted signal arrives 
phase disordered at the receiver \citep{4560215}. 
This phase disorder is a consequence of the relationship 
between the instantaneous frequency and instantaneous phase
according to equations \eqref{eq:freqPhase} and \eqref{eq:phaseFreq}. 
\begin{equation}
\label{eq:freqPhase}
f(t)=\frac{1}{2\pi}\frac{\partial}{\partial t}\phi(t)
\end{equation}
\begin{equation}
\label{eq:phaseFreq}
\phi(t) = 2\pi \int_{-\infty}^{t} f(\tau) d\tau
\end{equation}

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}$ represents the known satellite
carrier wave phase, $\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 wideband 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 equivalent 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 for this is straightforward to understand by looking at the
 multiplication of two sine waves. The GPS L1 signal 
 demodulator at the receiver is depicted in figure
\ref{img:L1Demod}, the incoming signal L1 is multiplied with 
the synthesized sine wave (multiplication is the function of
a mixer, denoted as $\otimes$ in figure \ref{img:L1Demod}). 
For the purpose of easier analysis, cosine waves
shall be used istead of sine waves, the difference between them 
is only in the phase shift, as denoted in equation
\eqref{eq:sineEqCosine}. 
\begin{equation}
\label{eq:sineEqCosine}
\sin(\pm x) = \cos\bigg(\frac{\pi}{2} \pm x\bigg)
\end{equation}
Multiplication of two cosine waves, as in equation \eqref{eq:multCosin},
can be derived by adding $\cos(A+B)$ and $\cos(A-B)$ together, as respectively
given in equations \eqref{eq:cos1} and \eqref{eq:cos2}.
\begin{equation}
\label{eq:multCosin}
\cos(A)\cdot\cos(B) = \frac{1}{2}\cos(A-B)+\frac{1}{2}\cos(A+B)
\end{equation}
\begin{equation}
\label{eq:cos1}
\cos(A+B) = \cos(A)\cos(B)-\sin(A)\sin(B)
\end{equation}
\begin{equation}
\label{eq:cos2}
\cos(A-B) = \cos(A)\cos(B)+\sin(A)\sin(B)
\end{equation}
The incoming GPS L1 signal with a frequency $f_{1}$, given in figure \ref{img:L1Demod}, 
can be written as $d_{C/A}\cos(\omega_{1}t)$, a similar form is given in equation \eqref{eq:GPSSignalReceived2},
where $\omega_{1}=2\pi f_{1}$ is
the angle frequency and
$d_{C/A}$ is the C/A data (navigation message modulated with the PRN code),
$d_{C/A}=d_{PRN}\oplus d_{NAV}$.
If equation \eqref{eq:multCosin} is rewritten with the received GPS signal L1
and synthesized wave with frequency $f_{2}$, the equation results the one
given in \eqref{eq:cosResult}
\begin{equation}
\label{eq:cosResult}
d_{C/A}\cdot\cos(\omega_{1}t)\cos(\omega_{2}t) = \frac{1}{2}d_{C/A}\cdot\cos(\omega_{1}t-\omega_{2}t) + \frac{1}{2}d_{C/A}\cos(\omega_{1}t+\omega_{2}t)
\end{equation}
This leaves the resulting signal with two frequency terms, a low frequency 
term $(\omega_{1}t-\omega_{2}t)$
and a high frequency term $(\omega_{1}t+\omega_{2}t)$,
the $t$ can be taken in front of the bracket as it
is a common multiplier.
The high frequency term, $(\omega_{1}+\omega_{2})$, can be filtered out using
a low-pass filter\footnote{A low-pass filter passes
low frequency signals and attenuates
high frequency signals. In other words, signals higher than the
specified cutoff frequency of the low-pass filter, are cut off by reducing their amplitudes.}.
Ideally, the difference of the angle frequencies is zero,
as in equation \eqref{eq:delaOmega}, since $\cos(\Delta \omega)=\cos(0)=1$
and the remaining left signal is only the C/A code multiplied
with the DC term (zero frequency producing a constant voltage) leaving only $\frac{1}{2}d_{C/A}$.
\begin{equation}
\label{eq:delaOmega}
\Delta \omega = \omega_{1}-\omega_{2} = 0
\end{equation}
However, if the frequencies do not match, $f_{1}\neq f_{2}$,
then the output signal $\frac{1}{2}d_{C/A}$ shall be
modified by the residual frequency $f_{1}-f_{2}$, 
and subsequently this shall change the demodulated C/A output (also known as phase shift). Under those circumstances
the correlator shall be unable to match the C/A code with the
correct PRN code. An illustration of this phenomenon is depicted
in figure \ref{img:multCAPhase}. 

\begin{figure}[ht!]
  \centering
  \includegraphics[scale=0.5]{img/PRN-PhaseShiftAfterDemod.pdf}
  \caption{Effects of the low frequency term on the demodulated output
  C/A wave on the GPS receiver (the explanations and figures are from top to bottom).
  If the synthesized frequency is correct, $f_{1}=f_{2}$, the low 
  frequency term becomes a DC term and does not modify the output
  $d_{C/A}$ wave (first figure). If the frequency matches but the
  phase not, in this case the phase is shifted for $\pi$, then
  $d_{C/A}$ is inverted (second figure).
  If the phase shifts with time, then the amplitude and phase of $d_{C/A}$
  shall vary as well (third figure). Image courtesy of \citep{diggelen2009a-gps}.}
\label{img:multCAPhase}
\end{figure}


\newpage
\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 shall result in the time and navigation data.
Each tracked GPS satellite signal is demodulated seperately 
using the same PRN code, code chipping rate and carrier frequency-phase 
(which was determined above) for the given satellite
\citep[Chapter 4]{understandGPS}. 
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 described in
section \ref{sec:Carrierdemod}.
\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$. The chipping period $T_{c}$
can be derived from equation \eqref{eq:chipPeriod}. 
The amount of time required to find a matching PRN code shift, $\tau$,
on the receiverr is proportional to the amount of parallely working LFSRs on the system
\citep[Chapter 3]{bensky2008wireless}. Clearly with more LFSRs
the required time for finding the matching phase shift increases.
\begin{equation}
\label{eq:chipPeriod}
T_{c} = \frac{1}{f_{PRN}} = \frac{1}{1.023\cdot 10^6 \mathrm{Hz}}
\end{equation}

To determine whether the synthesized PRN code,
matches the incoming C/A code of the received satellite
signal, known correlation properties of PRN codes are used,
as described in section \ref{sec:gpsDataAndSignal}. 
Since the PRN code is modeled as a sequence of +1's and
-1's, the autocorrelation of
a signal is at its maximum if it is in phase, i.e. 
summing up the sequence products yields the absolute
maximum value for the case where each bit from one signal matches
the bit from the other signal. As an illustration of the idea, an example is
given in figure \ref{img:correlatingSignals}. The cross-correlation
of the incoming C/A code with the first synthesized PRN code produces a 
result of $-3=(+1)\cdot(-1)+(-1)\cdot(+1)+(+1)\cdot(-1)+(+1)\cdot(+1)+(-1)\cdot(+1)$,
whereas the cross-correlation of the incoming C/A code
and the second synthesized PRN code yields a result of 
$+5=(+1)\cdot(+1)+(-1)\cdot(-1)+(+1)\cdot(+1)+(+1)\cdot(+1)+(-1)\cdot(-1)$.

\begin{figure}[ht!]
  \centering
  \includegraphics[scale=0.50]{img/Correlation.pdf}
  \caption{Cross-correlation on three different signals. Image courtesy of \citep{understandGPS}.}
\label{img:correlatingSignals}
\end{figure}
The same principle applies to the transmitted C/A and 
generated PRN code sequences in the GPS receiver. Thus, this can be modeled using
the equation given in \eqref{eq:autocorrelationProperty}, 
where $G_{i}(t)$ is the C/A code\footnote{PRN generated code for GPS satellites 
is called Gold code sequences
since they were first discovered by Dr. Robert Gold.} as a
function of time $t$, for the GPS satellite $i$; $T_{C/A}$ is the
C/A chipping period of $977.5 \,ns$ and $\tau$ is the phase shift 
in the auto-correlation function \citep[Chapter 4]{understandGPS}.

\begin{equation}
\label{eq:autocorrelationProperty}
R_{i}(t) = \frac{1}{1023\cdot T_{C/A}} \int_{t=0}^{1022} G_{i}(t)G_{i}(t+\tau)d\tau
\end{equation}
Another correlation property of the PRN codes is used,
the fact that in the ideal case the cross-correlation of two
different PRN codes yields a result of zero. The ideal case of
PRN code can be modeled as in equation \eqref{eq:prnIdealCaseZero},
\begin{equation}
\label{eq:prnIdealCaseZero}
R_{ij}(\tau) = \int_{-\infty}^{+\infty} PRN_{i}(t)PRN_{j}(t+\tau)d\tau = 0
\end{equation}
where $PRN_{i}$ is the PRN code waveform for GPS satellite $i$ and 
$PRN_{j}$ is the PRN code waveform for every other GPS satellite other
than $i$, $i\neq j$ \citep[Chapter 4]{understandGPS}. Equation
\eqref{eq:prnIdealCaseZero} ``states that the PRN waveform of satellite
$i$ does not correlate with PRN waveform of any other satellite $j$ for
any phase shift $\tau$'' \citep[Chapter 4]{understandGPS}.
Without the property given in \eqref{eq:prnIdealCaseZero},
the GPS receiver would not be able to smoothly 
differentiate between different GPS satellite signals. 
Once the phase shift, $\tau$, has been found, the C/A code is modulated
(XORed) with it. The resulting binary code shall be the navigation message.
The implementation problem of finding correct C/A and carrier wave demodulation shall be
further explained in the following section \ref{sec:2dSearch}.

\subsection{Implementation of the 2D search space problem}
\label{sec:2dSearch}
In the following paragraphs an introduction shall be given on 
the implementation problems of the previously discussed concepts. 
As it can be seen, 
from subsections \ref{sec:Carrierdemod} and
\ref{sec:CAdemod}, decoding the GPS navigation message is a 2D 
search space problem for each GPS satellite
signal acquisition. The 2D search space is limited by well known
physical properties of the GNSS 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 (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}$ 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. 
The frequency search space is ``additionaly 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 (band) size is a function of the desired peak magnitude loss (signal to noise ratio)
due to the frequency mismatch and integration time period. Larger frequency
bands mean a smaller number of bins to search but
a greater correlation peak magnitude loss, i.e. with larger frequency bands
it becomes harder to identify the correlation peaks described in sections \ref{sec:gpsDataAndSignal} and \ref{sec:CAdemod}. 
The frequency search bin size can be
estimated using the frequency 
mimsmatch 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 mimsmatch 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 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 conbinations in the search space,
this can be derived from equation \eqref{eq:totalSearch}, visually shown 
in figure \ref{img:SearchSpace2d}.
\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 searching
for the GPS satellites. If no information are known,
when some information are known and when almost all information are
known. These three modes are known as \textit{cold} (as discussed earlier),
\textit{warm} and \textit{hot} start. They differ from each other by the amount of known
information by the GPS receiver. Cold start indicates the GPS receiver
has no almanac, ephemeris, 
oscillator offset and time data. In order to track the satellites faster next time
the GPS receiver is started, it stores the previously mentioned data (last known almanac, 
ephemeris, oscillator offset, time and position data) in its electrically erasable
programmable read only memory (EEPROM). This new type of start,
is known as a warm start,
provided that the data in the receivers' EEPROM are not older than 180 days and
its real time clock counter was constantly updated.
In this case, the receiver uses the previously saved information
to estimate the position of the satellites, therefore the Doppler effects can be roughly estimated. 
As a consequence of the known Doppler effect, the frequency bin where to start
the search first is known this time \citep[Chapter 3]{diggelen2009a-gps}.
Hot start works in the same manner, only the ephemeris data and time data are precisely
known (time ought to be known in accuracy of submilliseconds). 

\newpage
\section{Distance and position estimation}
\label{sec:distanceAndPosition}
In this section the focus is set on distance and position estimation inside of the GPS receiver.
GPS system, as discussed earlier, takes advantage of the TOA ranging concept
to determine user position. Time is measured how long it takes for a signal to arrive from a
known location.
\begin{figure}[ht!]
  \centering
  \includegraphics[scale=0.50]{img/Localization.pdf}
  \caption{Basic distance estimation principle for one satellite. Image courtesy of \citep{understandGPS}.}
\label{img:SatLocalization}
\end{figure}
In figure \ref{img:SatLocalization}, an example concept can be seen, where $\vec{u}=(x_u,y_u,z_u)$ represents the unknown 
GPS user position vector with respect to Earth-Centered, Earth-Fixed\footnote{ECEF is a Cartesian coordinate system
where the point $(0,0,0)$ is defined as the center of mass of the Earth \citep{earthCoordinates}.} 
(ECEF) coordinate system,  $\vec{r}$ is the distance vector from the satellite to the user and  $\vec{s}=(x_s,y_s,z_s)$
represents the GPS satellite position with respect to ECEF at a timepoint. Vector $\vec{s}$ is computed from ephemeris data broadcasted
by the satellite. The distance vector $\vec{r}$, distance between the satellite and user, can be computed using equation \eqref{eq:r} and its magnitude is
given in equation \eqref{eq:rMag}.
\begin{equation}
\label{eq:r}
\vec{r}=\vec{s}-\vec{u}
\end{equation}
\begin{equation}
\label{eq:rMag}
r=\Vert s-u\Vert
\end{equation}
The geometric distance of $r$ is computed by measuring the signal propagation time, this is illustrated in figure \ref{img:TimingLoc}
and it was discussed in section \ref{sec:CAdemod}. The PRN code generated on the GPS satellite 
at time $t_1$ arrives at the time $t_2$, the difference between these two time stamps, $\Delta t$, represents the 
propagation time. By multiplying the propagation time, $\Delta t$, with the speed of light, $c$, the 
geometric distance $r$ is computed, as given in equation \eqref{eq:rDist}. 
\begin{figure}[ht!]
  \centering
  \includegraphics[scale=0.50]{img/TimingLoc.pdf}
  \caption{Estimating the distance by phase shift $\Delta t =t_2 - t_1 =\tau$. Image courtesy of \citep{understandGPS}.}
\label{img:TimingLoc}
\end{figure}
\begin{equation}
\label{eq:rDist}
r=c\Delta t
\end{equation}
Since the clocks are not synchronized, 
as described in sections \ref{sec:SigDemod} and \ref{sec:2dSearch},
clock error offsets have to be added to 
the geometric distance $r$. This new distance is called \textit{pseudorange}, $\rho$, because the range is 
determined using the difference of two nonsynchronized clocks (one on the GPS satellite and
the other one on the receiver) that generate PRN codes\footnote{pseudo - Not genuine; sham; not perfect.}. Pseudorange is calculated as given in equation \eqref{eq:rho}, where 
$t_{u}$ is the advance of the receiver clock with respect to the system time\footnote{System
time is the exact time on Earth and it is the most precise time known!} and $\delta t$ is the offset of the
satellite clock from the system time \citep{understandGPS}.
\begin{equation}
\label{eq:rho}
\rho=r + c(t_{u}-\delta t)
\end{equation}
Equation \eqref{eq:rMag} can be rewritten as \eqref{eq:rhoR} with respect to equation \eqref{eq:rho}.
\begin{equation}
\label{eq:rhoR}
\rho - c(t_{u}-\delta t) = \Vert s-u\Vert
\end{equation}
Offset of the satellite clock from the system time, $\delta t$, is updated from Earth, as discussed in \ref{sec:SigDemod}
and for that reason it can be removed for sake of simplicity, i.e. it is not an unknown term anymore,
then the eqaution \eqref{eq:rhoR} can be rewritten as \eqref{eq:rhoNew}.
\begin{equation}
\label{eq:rhoNew}
\rho - ct_{u} =  \Vert s-u\Vert
\end{equation}
In order to estimate the user (GPS receiver) position,
advance of the receiver clock with respect to the system time, $t_u$, has to be found, in other words equation \eqref{eq:rhoSats}
has to be solved, where $i$ is the index of visible satellites at the moment of signal reception \citep{understandGPS}.
\begin{equation}
\label{eq:rhoSats}
\rho_i= \Vert s_i-u\Vert + ct_u
\end{equation}
The estimated position of the user, $\vec{u}=(x_u,y_u,z_u)$, is a three dimensional vector and as stated
above the clock offset, $t_u$, is unknown as well. This four dimensional space requires to have at least four pseudorange
equations \eqref{eq:rhoSats} to find all the four unknown terms. 
As a result of this fact, at least four satellites have to be visible at 
the same time to estimate the position of the target user. Equation given in \eqref{eq:rhoSats} takes the form in
\eqref{eq:rhoSatsNew} because the coordinate system is Cartesian and  $\rho_i$ is nothing else but Euclidean distance
where $i=1,2,...,n$ such that $n\geq4$ and $\vec{s_i}=(x_i,y_i,z_i)$ is the satellite position estimated from the ephemeris data.
\begin{equation}
\label{eq:rhoSatsNew}
\rho_i= \sqrt{(x_i-x_u)^2+(y_i-y_u)^2+(z_i-z_u)^2} + ct_u
\end{equation}
Undoubtedly, the given equation in \eqref{eq:rhoSatsNew} is a nonlinear 
equation\footnote{Nonlinear
equations, also known as polynomial equations, are equations that can not satisfy both
of the linearity properties:
additivity $f(x+y)=f(x)+f(y)$ and homogeneity $f(\alpha x) = \alpha f(x)$, $\alpha \in \mathbb{R}$ \citep{nonlinear}.}.
It is not straightforward to find explicit solutions of nonlinear equations, it is more difficult than
compared to linear equations.
There are different techniques to solve sets of nonlinear equations \citep[Chapter 7]{understandGPS}
but in this work the linearization method\footnote{Linear approximation is a technique where a function
is approximated using a linear function.}
shall be presented to find the unknown terms $(x_u,y_u,z_u,t_u)$, i.e. out of an approximate position and clock
offset the true user position and the true clock offset shall be calculated.
\begin{equation}
\label{eq:rhoSatsNewFun}
\rho_i= \sqrt{(x_i-x_u)^2+(y_i-y_u)^2+(z_i-z_u)^2} + ct_u = f(x_u,y_u,z_u,t_u)
\end{equation}
Let the equation \eqref{eq:rhoSatsNew} for pseudoranges, be rewritten as a function $f$ of four
unknown terms $x_u$, $y_u$, $z_u$ and $t_u$, as
given in \eqref{eq:rhoSatsNewFun} \citep[Chapter 2]{understandGPS}. Suppose that the approximation of the
position and the clock offset are known,
denoted as $\hat{x_u}$, $\hat{y_u}$, $\hat{z_u}$ and $\hat{t_u}$, then equation \eqref{eq:rhoSatsNewFun}
can be rewritten as an approximate pseudorange \eqref{eq:rhoSatsNewFunApprox}.
\begin{equation}
\label{eq:rhoSatsNewFunApprox}
\hat{\rho_i}= \sqrt{(x_i-\hat{x_u})^2+(y_i-\hat{y_u})^2+(z_i-\hat{z_u})^2} + c\hat{t_u} = f(\hat{x_u},\hat{y_u},\hat{z_u},\hat{t_u})
\end{equation}
In other words, the unknown true position terms $x_u$, $y_u$, $z_u$ and the clock offset term $t_u$, of the GPS receiver,
shall be expressed by the approximate values and an incremental component as shown in equation \eqref{eq:userCoordinates} \citep{understandGPS}.
\begin{equation}
\label{eq:userCoordinates}
\begin{array}{l}
x_u = \hat{x_u}+\Delta x_u \\
y_u = \hat{y_u}+\Delta y_u \\
z_u = \hat{z_u}+\Delta z_u \\
t_u = \hat{t_u}+\Delta t_u
\end{array} 
\end{equation}
By inserting the terms from \eqref{eq:userCoordinates} into equation \eqref{eq:rhoSatsNewFun}, a new equation is derived
as in \eqref{eq:rhoSatsNewFunwithApprox}.
\begin{equation}
\label{eq:rhoSatsNewFunwithApprox}
f(x_u,y_u,z_u,t_u) = f(\hat{x_u}+\Delta x_u, \hat{y_u}+\Delta y_u, \hat{z_u}+\Delta z_,\hat{t_u}+\Delta t_u)
\end{equation}
In the next step the pseudorange function shall be approximated using Taylor series\footnote{Taylor
series ``is a representation of a
function as an infinite sum of terms that are calculated from the values of the function's
derivatives at a single point'' \citep[Chapter 11]{taylor}.} (linearization of the nonlinear equation). Taylor
series for a function $f(x)$ is given in equation \eqref{eq:taylor}, where as $a$ approaches $x$ the estimation
error shall be smaller and smaller, i.e. $f(x) = f(a)$ when $x=a$. The approximation error
depends on Taylor polynomial degree (the amount of terms or taken derivatives of the function)
and how far away the point $a$ is from $x$ \citep[Chapter 11.9]{taylor}.
The basic idea of the principle can be seen in figure \ref{img:taylorSeries}.
\begin{equation}
\label{eq:taylor}
f(x) = \sum_{n=0}^{\infty}\frac{f^{(n)}(a)}{n!}(x-a)^n = f(a) + \frac{f'(a)}{1!}(x-a)+\frac{f''(a)}{2!}(x-a)^2+...
\end{equation}

\begin{figure}[ht!]
  \centering
  \includegraphics[scale=0.50]{img/TaylorSeries.pdf}
  \caption{Taylor series approximation for a point $a=0.5$ where $n$ is the Taylor polynomial degree.}
\label{img:taylorSeries}
\end{figure}
Due to the four unknown terms, Taylor series for multivariables
have to be used. The general formula is given in
equation \eqref{eq:Multitaylor}, where vector $\mathbf{x}\in\mathbb{R}^n$ denotes
$n$ variables, $\nabla$ (nabla) is the Del\footnote{Del, $\nabla$,
is the vector differential operator.} operator given in \eqref{eq:Del} and $\mathbf{a}$ is the 
linearization point of interest
\citep{multiTaylor}.
\begin{equation}
\label{eq:Multitaylor}
f(\mathbf{x}) \approx f(\mathbf{a}) + \nabla f |_{\mathbf{x=a}} \cdot (x-a)
\end{equation}
\begin{equation}
\label{eq:Del}
\nabla^{T} = \left[\frac{\partial}{\partial x_{1}}...\frac{\partial}{\partial x_{n}}\right]
\end{equation}
One can note that in equation \eqref{eq:Multitaylor} the Taylor series polynomial is of the first degree.
This is because of one reason, it linearizes the approximation of the function $f(\mathbf{x})$ at point $\mathbf{a}$
and as a consequence it removes the nonlinearities \citep{understandGPS} \citep[Chapter 11.10]{taylor}, as seen
in figure \ref{img:taylorSeries}, for $n=1$ the resulting function is linear.
In the previously described step, one would calculate a hyperplane tangent to a
point $a$ in a $n$-Dimensional space. By inserting equation \eqref{eq:rhoSatsNewFunwithApprox} in 
equation \eqref{eq:Multitaylor}, it yields equation \eqref{eq:MultitaylorFour} where $\mathbf{x}=(x_u,y_u,z_u,t_u)$
and $\mathbf{a}=(\hat{x_u},\hat{y_u},\hat{z_u},\hat{t_u})$.
\begin{equation}
\label{eq:MultitaylorFour}
\begin{array}{l}
f(\hat{x_u}+\Delta x_u, \hat{y_u}+\Delta y_u, \hat{z_u}+\Delta z_,\hat{t_u}+\Delta t_u) \approx
		     f(\hat{x_u},\hat{y_u},\hat{z_u},\hat{t_u}) \\[0.5em]
		    + \dfrac{\partial f(\hat{x_u},\hat{y_u},\hat{z_u},\hat{t_u})}{\partial \hat{x_u}}\Delta x_u 
+\dfrac{\partial f(\hat{x_u},\hat{y_u},\hat{z_u},\hat{t_u})}{\partial \hat{y_u}}\Delta y_u \\
+\dfrac{\partial f(\hat{x_u},\hat{y_u},\hat{z_u},\hat{t_u})}{\partial \hat{z_u}}\Delta z_u 
+\dfrac{\partial f(\hat{x_u},\hat{y_u},\hat{z_u},\hat{t_u})}{\partial \hat{t_u}}\Delta t_u 
\end{array}
\end{equation}
The terms from equation \eqref{eq:MultitaylorFour} are solved individually in
equations \eqref{eq:MultitaylorDeriv} where $\sqrt{(x_i-\hat{x_u})^2+(y_i-\hat{y_u})^2+(z_i-\hat{z_u})^2}$
has been subsituted with $\hat{r_i}$.
\begin{equation}
\label{eq:MultitaylorDeriv}
\begin{array}{l}
\dfrac{\partial f(\hat{x_u},\hat{y_u},\hat{z_u},\hat{t_u})}{\partial \hat{x_u}} = \dfrac{1}{2}\dfrac{-2(x_{i}-\hat{x_{u}})}{\sqrt{(x_i-\hat{x_u})^2+(y_i-\hat{y_u})^2+(z_i-\hat{z_u})^2}}
=-\dfrac{x_i-\hat{x_u}}{\hat{r_i}}\\[0.9em]
\dfrac{\partial f(\hat{x_u},\hat{y_u},\hat{z_u},\hat{t_u})}{\partial \hat{y_u}} = \dfrac{1}{2}\dfrac{-2(y_{i}-\hat{y_{u}})}{\sqrt{(x_i-\hat{x_u})^2+(y_i-\hat{y_u})^2+(z_i-\hat{z_u})^2}}
=-\dfrac{y_i-\hat{y_u}}{\hat{r_i}}\\[0.9em]
\dfrac{\partial f(\hat{x_u},\hat{y_u},\hat{z_u},\hat{t_u})}{\partial \hat{z_u}} = \dfrac{1}{2}\dfrac{-2(z_{i}-\hat{z_{u}})}{\sqrt{(x_i-\hat{x_u})^2+(y_i-\hat{y_u})^2+(z_i-\hat{z_u})^2}}
=-\dfrac{z_i-\hat{z_u}}{\hat{r_i}}\\[0.9em]
\dfrac{\partial f(\hat{x_u},\hat{y_u},\hat{z_u},\hat{t_u})}{\partial \hat{t_u}} = c
\end{array}
\end{equation}
Then by substituting the equation terms from \eqref{eq:MultitaylorDeriv}, \eqref{eq:rhoSatsNewFun} and \eqref{eq:rhoSatsNewFunApprox}
into \eqref{eq:MultitaylorFour}, the resulting equation is given in \eqref{eq:MultitaylorDerivAfter}.
\begin{equation}
\label{eq:MultitaylorDerivAfter}
\begin{array}{l}
\rho_i = \hat{\rho_i} -\dfrac{x_i-\hat{x_u}}{\hat{r_i}}\Delta x_u -\dfrac{y_i-\hat{y_u}}{\hat{r_i}}\Delta y_u -\dfrac{z_i-\hat{z_u}}{\hat{r_i}}\Delta z_u + c\Delta t_u
\end{array}
\end{equation}
At this step, by solving equation \eqref{eq:MultitaylorFour}, the linearization of the nonlinear equations is completed. 
\begin{equation}
\label{eq:MultitaylorDerivAfterRearange}
\begin{array}{l}
\hat{\rho_i} - \rho_i = \dfrac{x_i-\hat{x_u}}{\hat{r_i}}\Delta x_u +\dfrac{y_i-\hat{y_u}}{\hat{r_i}}\Delta y_u +\dfrac{z_i-\hat{z_u}}{\hat{r_i}}\Delta z_u - c\Delta t_u
\end{array}
\end{equation}
\begin{equation}
\label{eq:SubsTerms1}
\Delta\rho = \hat{\rho_i} - \rho_i \\[0.7em]
\end{equation}
\begin{equation}
\label{eq:SubsTerms2}
\alpha_{xi} = \dfrac{x_i - \hat{x_u}}{\hat{r_i}} \hspace{1.5em} \alpha_{yi} = \dfrac{y_i - \hat{y_u}}{\hat{r_i}} \hspace{1.5em} \alpha_{zi} = \dfrac{z_i - \hat{z_u}}{\hat{r_i}}
\end{equation}
By rearanging the equation \eqref{eq:MultitaylorDerivAfter} one derives equation \eqref{eq:MultitaylorDerivAfterRearange}.
And then by substituting the terms in \eqref{eq:SubsTerms1} and \eqref{eq:SubsTerms2} into \eqref{eq:MultitaylorDerivAfterRearange}, 
the equation resembles the one given in \eqref{eq:userPosition}.
\begin{equation}
\label{eq:userPosition}
\Delta\rho_i = \alpha_{xi}\Delta x_u + \alpha_{yi}\Delta y_u + \alpha_{zi}\Delta z_u - c\Delta t_u
\end{equation}
There are four unknowns, $\Delta x_u$, $\Delta y_u$, $\Delta z_u$ and $\Delta t_u$, in equation \eqref{eq:userPosition}.
By solving this set of linear equations, which shall result in finding $\Delta x_u$, $\Delta y_u$, $\Delta z_u$ and $\Delta t_u$,
the GPS receiver position $(x_u, y_u, z_u)$ and clock offset $t_u$ is computed by replacing the
same into equations in \eqref{eq:userCoordinates}. Equation \eqref{eq:userPosition} can be rewritten for four satellites 
in the matrix form as in \eqref{eq:userPositionMatrix}.
\begin{equation}
\label{eq:userPositionMatrix}
\Delta\boldsymbol{\rho} = \boldsymbol{\alpha} \Delta \boldsymbol{x}
\end{equation}

\begin{equation}
\Delta\boldsymbol{\rho}=
\begin{bmatrix}
\Delta \rho_1 \\
\Delta \rho_2 \\
\Delta \rho_3 \\
\Delta \rho_4 
\end{bmatrix}
\hspace{1.5em}
\boldsymbol{\alpha}=
\begin{bmatrix}
\alpha_{x1} & \alpha_{y1} & \alpha_{z1} & 1 \\
\alpha_{x2} & \alpha_{y2} & \alpha_{z2} & 1 \\
\alpha_{x3} & \alpha_{y3} & \alpha_{z3} & 1 \\
\alpha_{x4} & \alpha_{y4} & \alpha_{z4} & 1 
\end{bmatrix}
\hspace{1.5em}
\Delta \boldsymbol{x}=
\begin{bmatrix} 
\Delta x_u \\
\Delta y_u \\
\Delta z_u \\
-\Delta ct_u 
\end{bmatrix}
\end{equation}
Finally, by multiplying both left sides\footnote{Matrix multiplication is not communitative, $\mathbf{AB\neq BA}$.} of the equation \eqref{eq:userPositionMatrix}
with the inverse term of $\boldsymbol{\alpha}$, it yields the result of the unknown terms, as given in equation \eqref{eq:userPositionMatrixFinal}.
\begin{equation}
\label{eq:userPositionMatrixInverseMult}
\boldsymbol{\alpha}^{-1}\Delta\boldsymbol{\rho} = \boldsymbol{\alpha}^{-1}\boldsymbol{\alpha} \Delta \boldsymbol{x}
\end{equation}
\begin{equation}
\label{eq:userPositionMatrixFinal}
\Delta \boldsymbol{x} = \boldsymbol{\alpha}^{-1} \Delta\boldsymbol{\rho}
\end{equation}
Linearization is repeated in a loop, where in the next round the approximate positions are set
to the just derived position values, that is, $\hat{x_u}=x_u$, $\hat{y_u}=y_u$, $\hat{z_u}=z_u$ and
$\hat{t_u}=t_u$. This process is repeated until the approximated positions converge to their final
values. It is not necessarily required that the initial positions are very accurate
and the results are usually obtained by 4-5 itterations \citep{pseudorangeError}. 
Risks exist that the solutions shall still be corrupted but there are different error avoiding 
mechanisms to solve these problems, like minimizing the error contribution using more than four satellite
measurements \citep{pseudorangeError} \citep[Chapter 7]{understandGPS}. 



\newpage
\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 are known 
at a 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 are 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 global navigation satellite system (GNSS) server, which is directly
connected to the GPS reference station. The GPS reference station delivers the GNSS server exact time stamps,
approximate location, satellite health as well as clock corrections, ionospheric and UTC model, almanac and ephemeris data 
\citep{springerlink:10.1007/s10291-002-0028-0}. 
\begin{figure}[ht!]
  \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 by the AGPS receiver in the smart phone
help it to estimate the positions of the GPS satellites. 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 (omnidirectional) 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} shall be presented here. This
algorithm benefits in speed the more assistance data is present. 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. 
Numerous AGPS algorithms exist, some do not require the exact time component and navigation data to
be present in the assistance data \citep{998892}.

\section{Error estimation}











\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 Standalone Dedicated Control Channel (SDCCH) is initialized to deliver data to cell phones. 
\newpage
\section{Overview of the Air interface}
In this section the reader shall be provided with principles how the GSM network operates. 
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 employed. The reason why different frequencies are used is because of intereference 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, EGSM900 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 25/35 MHz there are 124/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, the frequencies are shifted 45 MHz in EGSM900/GSM900 and
95 MHz in GSM1800 as it can be seen in figure \ref{img:GSMFreqRangChannel} for GSM900.
\begin {table}[hb]
\caption{GSM operating frequencies in Germany}
\label{tbl:GSMfreqs}\centering 
%\rowcolor{2}{light-gray}{}
\scriptsize\fontfamily{iwona}\selectfont
\begin{tabular}{ccccc}
\toprule 
%$D$&&$P_u$&$\sigma_N$\\
Frequency band&Uplink frequency (MHz)&Downlink frequency (MHz)& Channel number\\\toprule
GSM900&890 - 915&935 - 960& 1 - 124\\\midrule
EGSM900&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 is split up into eight time slots.
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$).}. Since new wireless services are
data oriented and the networks become packet networks this type of modulating data had to be changed, 
3G and 4G networks use different frequency ranges and technique to modulate and demodulate data.

TDMA applied on the FDMA technique constrains the GSM air interface to be of 
2D structure. 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 is split into 8 time slots. 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 channels (SCH). 
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
SCH 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 and associated
control 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 MS and the Base Transceiver Station (BTS)
\citep[Chapter 7]{0890064717}.


\newpage
\section{GSM Network structure}
\begin{figure}[ht!]
  \centering
  \includegraphics[scale=0.50]{img/GSMBig.pdf}
  \caption{Basic GSM network block diagram. Image courtesy of \citep{konrad} and \citep{dennis}.}
\label{img:GSMBig}
\end{figure}
\label{sec:GSMNetStruct}
BTS is the first hardware unit the cell phone is communicating with over the air interface
and provides a ``physical'' connection with the cell phone \citep[Chapter 3]{0890064717}. This physical connection between the
BTS and the cell phone is the \textit{$U_m$ interface}, as shown in figure \ref{img:GSMBig}. A BTS can serve up 
to seven users on one frequency in full duplex mode since one out of eight time slot is used for broadcasting of signalling and system information, 
transmitted in the broadcast control channel (BCCH). By sectorizing BTSs with different frequencies the number of seven mobile users
can be increased. BTS consists of a RF tranceiver, 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 the TDMA frames. The internal clock has to be sufficiently accure 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 generator signal from an atomic clock,
this is required for some of the position localization techniques, as described in section \ref{LMUSync}. 
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.}
\citep[Chapter 7]{0890064717} \citep{konrad} \citep[Chapter 4]{0470742984}. 

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 handover 
and controlling the power levels within channel \citep[Chapter 4]{0470742984} \citep{konrad} \citep[Chapter 3]{0890064717}.
BSC is connected to the Transcoding Rate and Adaptation Unit (TRAU). 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 responsibe 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 that
can be found in HLR: the unique International Mobile Subscriber Identity (IMSI) - that is stored on the SIM card of a mobile user; 
usage statistics; subscriber's number (MSISDN) and the current location of the mobile user acquired by knowing the location
of the BSC controlling the BTS that provides at the current moment the GSM air interface to the mobile user \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. i.e. if a MS 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 MS 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 MS from the BTS \citep[Chapter 3]{0470030704}. 
The keys located in AUC are also required for the MS 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}. 


\newpage
\section{Logical channels and the SDCCH channel}
\label{sec:SDCCHChan}
In this section more details will be given on logical channels and the procedure to initialize (open) an SDCCH channel (Standalone
Dedicated Control Channel). As stated in section \ref{sec:GSMNetStruct}, logical channels can be divided in two groups,
traffic channels (TCH) and signalling channels (SCH). The former are employed for transfering payload data like speech and message data
and the latter for managing and synchronizing the GSM network  \citep[Chapter 4]{0470030704}.
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}
\label{tbl:tchChannels}\centering 
%\rowcolor{2}{light-gray}{}
\scriptsize\fontfamily{iwona}\selectfont
\begin{tabular}{clccc}
\toprule 
%$D$&&$P_u$&$\sigma_N$\\
Channel name & Abbreviation & Function & 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}
\label{tbl:cchChannels}\centering 
%\rowcolor{2}{light-gray}{}
\scriptsize\fontfamily{iwona}\selectfont
\begin{tabular}{clccc}
\toprule 
%$D$&&$P_u$&$\sigma_N$\\
Channel name & Abbreviation & Function & 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\\
				&&current 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
Standalone 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 occuring 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 immediatelly 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 case assistance data to the MS and acknowledgements, errors or the position from the MS back 
to the BTS. 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. While the SDCCH channel connection has been established assistance data can be
transmitted to the MS. While an active SDCCH conecction 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 successful SDCCH channel. Image courtesy of \citep{0470844574}.}
\label{img:SDCCHReq}
\end{figure}












\chapter{Radio Resource Location Protocol}
\label{rrlpChapt}
This chapter shall focus on the Radio Resource Location Protocol (RRLP) and a description 
how it works inside of the GSM network shall be given. 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 standard supports three positioning mechanisms: E-OTD, UL-TDOA and AGPS \citep{3GPPTS03.71}. 
The LCS process can be divided into two seperate stages, signal measurements and
position estimation from the derived data in the previous stage. In this chapter
the description shall be given on how to make an RRLP request, how to send assistance
data and then more information shall be given on its response. 

\newpage
\section{RRLP Request}
In this section the RRLP protocol and its request shall be reviewed in more detail.
RRLP represents the connection/protocol between the Serving Mobile Location Center (SMLC) 
and the standalone handset, in this case the MS \citep[Chapter 5]{harper2010server-side}.
The SMLC node contains the functionaly to support 
location services for the GSM network \citep{3GPPTS03.71}. SMLCs primary function is to manage 
the overall coordination and scheduling of resources required to perform the localization of the MS
and it is located on the Base Station Controller (BSC) \citep{3GPPTS03.71}. 
SMLC controls the LMU's as well but since in this work no LMU were available this part
shall 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 MSs 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 PDU's may take a different shape and size because of the encapsulation or splitting \citep{kozierok2005the} \citep{stevens1994tcp/ip}. 
In RRLP, the PDU's sent from the SMLC ought to be not greater than 244 bytes\footnote{Bytes of 8 bits!},
although the standard defines that larger packets shall be split in lower layers, in this work the 
rule of 244 bytes has been obeyed and each PDU packet is not greater 
than 211 bytes \citep{04.31V8.18.0}. In the RRLP standard terms, the messages are entitled
as \textit{components} and fields in the messages (components) are labelled 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 the position (in case of an AGPS request, these data may be ephemeris, almanac, 
accurate timing data and similar data that help to estimate the position in a shorter period of time). 
The RRLP protocol is shown in figure \ref{img:RRLPReqProt}. Dashed lines represent optionally transmitted data 
like assistance data according to which an acknowledgement or error shall be produced. Once the MS obtains the RRLP request, 
after a period of processing time it shall respond to the SMLC with the position of the MS or with an error IE indicating what 
assistance data are missing or why it can not return the position \citep{04.31V8.18.0} \citep{49.031V8.1.0}. In the response component IE it is exactly indicated
what type of data ought to be sent to the MS so it can complete the RRLP request and give back 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 and then if the MS requires some of the assistance data,
it shall send a request for those data back to the SMLC and then the SMLC can send the required data and expect an 
successful response from the MS. However, in this work the author had a different approach in that sense, that first 
all the RRLP assistance data were sent and then the RRLP position request. This way, sending all assistance data,
was choosen over the other idea of waiting for the MS response because in OpenBSC it was not possible to access
directly the response data without querying the database directly. 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 indepedent 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}. Structure 
of the RRLP message encoding for transmission can be seen in listing \ref{lst:RRLP}. 
Further details on some of the unknown terms are given in listings
\ref{lst:RRLPReq} and \ref{lst:RRLPReqData}. An example how to build an RRLP request packet shall be given,
then it shall be encoded using Packed Encoding Rules (PER). 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}.
\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}
\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}
PER is intended for use in circumstances where
minimizing the size of the representation of values is the major concern
in the choice of encoding rules \citep{ITU-TX.691}. In other words, it compresses the data
in the PDU packets by limiting the bit field length to the minimal amount of 
bits required to define the minimal and maximal variable values defined in the standard. 
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. 

Before proceeding with an example, summary for the used ASN.1 type
elements shall be provided otherwise it is not possible to proceed with an example
RRLP request. 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} where 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 types
are used to distinguish a choice by identifying it with an incremented number from the previous
element where the
first element is 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} shall be given. 
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, in 
PER enocoding this requires at least a three bit representation since with three bits, 
eight different values can be represented ($2^3=8$). \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 shall know that its position is requested. MsrPosition-Req is a SEQUENCE,
consisting out of one mandatory and few optional IE elements. One choice shall be only considered,
\textbf{PositionInstruct}, the rest is used later for the assistance data and what
type of information is included inside of the PDU message. \textbf{PositionInstruct} consists 
of five elements but four are mandatory: \textit{methodType}, \textit{positionMethod}, 
\textit{measureResponseTime} and \textit{useMultipleSets}. 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 (time duration) it is allowed to measure 
the position and how many positions it should perform and return in its response.
\newpage
\textbf{methodType} defines where the position estimation calculation ought to be executed, 
shall it take place solely on the MS (\textit{msBased}), solely on the server\footnote{With server 
the BTS location is ment!} (\textit{msAssisted}),
or one is prefered over the other depending if the MS can execute the prefered one
(\textit{msBasedPref} or \textit{msAssistedPref}). The uncertainty of the accuracy 
of the estimated position is only optional if the choosen method is \textit{msAssisted}, 
otherwise it must be included in the message.
\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}
\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
This uncertainty of the accuracy, is an integer
number, that defines how certain the accuracy of the returned position ought 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 prefered by the MS),
the position measurement time and how many measurements the MS ought to report back to SMLC.
Since in this thesis the author exploits the AGPS method, GPS is choosen for \textbf{PositionMethod}.
\textbf{MeasureResponseTime} is a three bit integer value that corresponds to the time the MS is allowed
to perform the position estimation and to send a respose back to SMLC. Otherwise, if it takes longer the MS
than the specified time period, it shall disconnect the SDCCH channel without responding back. 
It 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 
choosen and set according to the position measurement request which the network operator wants to perform.
In the next step the RRLP request can be constructed and encoded using PER. To construct the RRLP request 
query from the above given ASN.1 specifications is straightforward. The choosen values are only concatenated
into a binary string. A simple
RRLP request in PER encoded form is shown in figure \ref{img:RRLPReqExplained} and the previous conversion 
process might become more clear, different variables have been colored with distinguishable colors to its neighbor
variables so that it is easy to recognize different variables. The five red zeros define what type of data
shall be included in the current RRLP packet. This becomes more understandable by looking at the listing \ref{lst:RRLPReqPER}.
After the concationation it can be converted to the 
desired notation system (binary, hexadecimal, etc.). In this particular example the RRLP request to be sent 
using the RRLP protocol in hexadecimal notation is: \textbf{400178F8}. This message is transmitted to the MS
via the opened SDCCH channel. However, before sending this request the assistance data can be sent. In the 
folowing section \ref{sec:rrlpassistance} more details of how assistance data are sent shall be presented. 
\begin{figure}[ht!]
  \centering
  \includegraphics[scale=0.80]{img/RRLPReqExplained.pdf}
  \caption{An example RRLP request. Constructing a binary RRLP request in PER from ASN.1. Yellow zero bits 
  are extension markers or spare bits. Image courtesy of \citep{harper2010server-side}.}
\label{img:RRLPReqExplained}
\end{figure}

\newpage
\begin{lstlisting}[label=lst:RRLPReqPER,
caption={\textbf{Encoding an RRLP request from ASN.1 to PER}},
backgroundcolor=\color{light-gray},
basicstyle=\scriptsize\ttfamily]
             RRLP Message:
40 010.....   referenceNumber = 2
              component:
   ...0....    Extension of RRLP-Component = 0 :Absent
   ....000.     RRLP-Component = 0 :msrPositionReq
                 MsrPosition-Req:
   .......0       Extension of MsrPosition-Req = 0 :Absent
01 0.......       referenceAssistData = 0 :Absent
   .0......       msrAssistData = 0 :Absent
   ..0.....       systemInfoAssistData = 0 :Absent
   ...0....       gps-AssistData = 0 :Absent
   ....0...       extensionContainer = 0 :Absent
                  PositionInstruct:
   .....0..        environmentCharacter = 0 :Absent
                   MethodType:
   ......01         MethodType = 1 :msBased
                     Accuracy:
78 0111100.           Accuracy = 60
                   PositionMethod:
   .......0         PositionMethod = 1 :gps
F8 1.......
                   MeasureResponseTime:
   .111....         MeasureResponseTime = 7
                   UseMultipleSets:
   ....1...         UseMultipleSets = 1 :oneSet
   .....000  Spare Bits = 000b
\end{lstlisting}

 
\newpage
\section{RRLP Assistance data}
\label{sec:rrlpassistance}
Assistance data are of the most important value when it comes to RRLP response time. 
If the assistance data are present, the response time ought to be shorter since 
the AGPS receiver knows the orbital information of the satellites and the exact time
which allows the AGPS to find immediatelly the Doppler frequency and phase shift of
the visible GPS satellite. In the assistance data packets, same as in the request
packet, one has to specify what type of assistance information are 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
this decision were explained earlier as cost and complexity issues.

DGPS corrections give additional accuracy to the GPS measurement reports between $1-3$ m \citep{489522} and they 
are rarely used \citep[Chapter 4]{harper2010server-side}. Real 
time integrity is a list of satellites the AGPS receiver ought not use because these satellites
have an 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 and to be aware not to use instead the old 
cached data \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
signal which 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}). 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 to 
synchronize with the BTS (earlier this was described 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 says provides the AGPS receiver directly with acquisition data. Acquisition data
are the Doppler frequencies and phase shift precalculated on the BTS for the MS. If this type of data is 
provided to the AGPS receiver, it does not require to compute and search for the given data from the provided time
on its on \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. 

More information on the assistance data transmitted within the RRLP protocol 
in this work shall be presented here. 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 approximate location which can be used 
for the position determination in equations given in section \ref{sec:distanceAndPosition}. 
Furthermore, this limits the search space in time and frequency domain for satellites 
to lock on, since 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 so that the AGPS receiver inside the MS can determine and 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}. These data are not satellite dependent therefore they 
are not sent for each satellite seperately but once and they are valid for
all satellites \citep[Chapter 4]{harper2010server-side}. Navigation data in RRLP terminology are the ephemeris data.
The transmitted assistance data can be seen in the following tables \ref{tbl:utcModel}, \ref{tbl:navMessage},
\ref{tbl:almanacMessage} and \ref{tbl:ionoModel}, on the following pages \pageref{tbl:utcModel},
\pageref{tbl:navMessage} and \pageref{tbl:almanacMessage}. How other 
data are encoded shall be given in the implementation chapter, chapter \ref{Implementation}.

The packets are constructed in the same manner as RRLP requests with a slight difference of selecting 
different 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}). Afterwords one
needs to specify what type of assistance the packet includes, in this case it is GPS assistance
data (\textit{gps-AssistData}, marked in red color in listing \ref{lst:RRLPAssisPER}). GPS assistance data were described in the 
two previous paragraphs and therefore shall be omitted here. They shall be only listed in the order as
specified in the RRLP standard for GPS assistance data, 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}). The assistance data one
wants to include in the RRLP packet have to be selected previously.
Selecting is straightforward and one only is required 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 transmitted 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 top variable data (\textit{referenceTime}) would follow as first and 
bottom variable (\textit{realTimeIntegrity}) would be the last to be 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}, as shown
in figure \ref{img:refLocStandard}.

\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 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 and to one if it is depth. 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). The latitude,
longitude and altitude need to be encoded into a format recognized by the RRLP standard. This is 
straightforward and can be proceeded using the equations shown in \eqref{eq:latLong}, where $\varphi$
is the latitude and $\lambda$ is the longitude value in decimal degrees. 
Longitude is encoded as second compliment binary number \citep{3gppequations}.
\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}
\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 altitude is encoded as it is where one bit increments represent one meter incerements. 
The uncertainties for latitude, longitude and altitude are encoded using the equation 
given in \eqref{eq:uncerAltitudeStand}, where $r$ is the uncertainty in meters for 
latitude and longitude, and $h$ is the uncertainty in meters for altitude of the BTS.
Both values, $U_L$ and $U_A$, are 7 bit numbers in the range between 0 and 127.
Orientation of major axis is not used in this work so it was set to zero. 
Confidence describes the level by which the sent BTS reference position is 
known to be correct. The confidence is a 7 bit number but ought to take values 
between 0 and 100 since it represents the 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 length 14 octets, 
as it can be seen in figure \ref{img:refLocStandard} (amount of rows), it is written as 13 octets
in the RRLP PDU packet.
It is always specified as 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. 
This way the RRLP protocol knows where the data end and where new data may start if they are included.
What type of reference location is include is defined by the first four bits of the reference location,
in this case it is $1001$, as it can be seen in figure \ref{img:refLocStandard}. 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 shall respond back with an acknowledgement or error depending if the 
data were correctly received and parsed by the MS. The acknowledgement shall have the same reference number 
as the assistance packet. This can be seen as well in figure \ref{img:RRLPReqProt}.
In the next section more details shall be given on the RRLP response from the MS.
\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}

\begin{equation}
\label{eq:uncerAltitudeStand}
\begin{array}{l}
\begin{split}
  U_L=\bigg\lceil\frac{ln(\frac{r}{10}+1)}{ln(1.1)}\bigg\rceil \bigg| U_A \in [0,127]
  \end{split}
\quad\Longleftarrow\quad
  \begin{split}
    \mbox{Uncertainty for latitude and longitude}
  \end{split}\\
  \\
\begin{split}
  U_A=\bigg\lceil\frac{ln(\frac{h}{45}+1)}{ln(1.025)}\bigg\rceil \bigg| U_A \in [0,127]
  \end{split}
\quad\Longleftarrow\quad
  \begin{split}
    \mbox{Uncertainty for altitude}
  \end{split}
\end{array} 
\end{equation}

\begin {table}[hb]
\caption{GPS UTC Model content}
\label{tbl:utcModel}\centering 
%\rowcolor{2}{light-gray}{}
\scriptsize\fontfamily{iwona}\selectfont
\begin{tabular}{clccc}
\toprule 
%$D$&&$P_u$&$\sigma_N$\\
Field (IE) & Description\\\toprule
$A_{1}$&Drift coefficient of GPS time scale relative\\
&to UTC time scale\\\midrule
$A_{0}$&Bias coefficient of GPS time scale relative\\
&to UTC time scale\\\midrule
$t_{ot}$&Time data reference time of week\\\midrule
$\Delta t_{LS}$&Current or past leap second count\\\midrule
$WN_{0}$&Time data reference week number\\\midrule
$WN_{LSF}$&Leap second reference week number\\\midrule
$DN$&Leap second reference day number\\\midrule
$\Delta t_{LSF}$&Current of future leap second count
\\\bottomrule
\end {tabular}
\end {table}

\begin {table}[ht!]
\caption{Navigation message (ephemeris) content}
\label{tbl:navMessage}\centering 
%\rowcolor{2}{light-gray}{}
\scriptsize\fontfamily{iwona}\selectfont
\begin{tabular}{clccc}
\toprule 
%$D$&&$P_u$&$\sigma_N$\\
Field (IE) & Description\\\toprule
Satellite ID&This is the satellite ID that is in the range of 0 to 63. PRN=SatelliteID + 1\\\midrule
Satellite status&This is an indicator of whether this is a new or existing satellite and whether\\
&the navigation model is new or the same.\\\midrule
C/A or P on L2&Code(s) on L2 channel\\\midrule
URA Index&User range accuracy\\\midrule
SV Health&Satellite health\\\midrule
IODC&Issue of data, clock\\\midrule
L2 P Data flag& \\\midrule
SF 1 Reserved& \\\midrule
$T_{GD}$&Estimated group delay differential\\\midrule
$t_{oc}$&Apparent clock correction\\\midrule
$a_{f2}$&Apparent clock correction\\\midrule
$a_{f1}$&Apparent clock correction\\\midrule
$a_{f0}$&Apparent clock correction\\\midrule
$C_{rs}$&Ampltitude of the sine harmonic correction term to the orbit radius (meters)\\\midrule
$\Delta n$&Mean motion difference from computed value (semicircles/second)\\\midrule
$M_{0}$&Mean anomaly at reference time (semicircles)\\\midrule
$C_{uc}$&Ampltitude of the cosine harmonic correction term to the\\
&argument of latitude (radians)\\\midrule
$e$&Eccentricity\\\midrule
$C_{us}$&Amplitude of the sine harmonic correction term to the argument of latitude\\
&(radians)\\\midrule
$A^{1/2}$&Square root of semi-major axis (meters)\\\midrule
$t_{oe}$&Reference time ephemeris\\\midrule
Fit Interval Flag&\\\midrule
AODO&Age of data offset\\\midrule
$C_{ic}$&Amplitude of the cosine harmonic correction term to the angle of inclination\\
&(radians)\\\midrule
$\Omega_0$&Longitude of ascending node of orbit plane at weekly epoch (semicircles)\\\midrule
$C_{is}$&Amplitude of the cosine harmonic correction term to the angle of inclination\\
&(radians)\\\midrule
$i_{0}$&Inclination angle at reference time (semicircles)\\\midrule
$C_{rc}$&Amplitude of the cosine harmonic correction term to the orbit radius (meters)\\\midrule
$\omega$&Argument of perigee (semicircles)\\\midrule
OMEGAdot&Rate of right ascension (semicircles/second)\\\midrule
Idot&Rate of inclination angle (semicircles/second)
\\\bottomrule
\end {tabular}
\end {table}

\begin {table}[hb]
\caption{Almanac message content}
\label{tbl:almanacMessage}\centering 
%\rowcolor{2}{light-gray}{}
\scriptsize\fontfamily{iwona}\selectfont
\begin{tabular}{clccc}
\toprule 
%$D$&&$P_u$&$\sigma_N$\\
Field (IE) & Description\\\toprule
SatelliteID&This is the satellite ID that is in the range of 0 to 63. PRN=SatelliteID + 1\\\midrule
SV Health&Satellite health (e.q. 000 means the satellite is fully operational)\\\midrule
$e$&``Eccentricity shows the amount of the orbit deviation from circular (orbit).\\
&It is the distance between the foci divided by the length of the semi-major axis'' \citep{ubxGPSDict}\\\midrule
TOA&Time of applicability, reference time for orbit and clock parameters (seconds).\\
&``The number of seconds in the orbit when the almanac data were generated'' \citep{ubxGPSDict}\\\midrule
OI&Orbital inclination (radians). The angle to which the SV orbit meets\\
&the equator \citep{ubxGPSDict}\\\midrule
RORA&Rate or right ascension (radians/second). ``Rate of change of the angle of right ascension\\
&as defined in the Right Ascension mnemonic'' \citep{ubxGPSDict}\\\midrule
$A^{1/2}$& Square root of semi-major axis (meters$^{1/2}$). `` This is defined as the measurement\\
&from the center of the orbit to either the point of apogee or the point of perigee'' \citep{ubxGPSDict}\\\midrule
$\Omega_0$& Right Ascension at Week (radians). Longitude of ascending node of orbit plane at\\
&weekly epoch\\\midrule
$\omega$&Argument of perigee (semicircles).  ``An angular measurement along the orbital path\\
&measured from the ascending node to the point of perigee, measured in the direction of\\
&the SV's motion'' \citep{ubxGPSDict}\\\midrule
$M_0$&Mean anomaly (radians)\\\midrule
$a_{f0}$&Satellite clock bias (seconds). Satellite clock error at reference time\\\midrule
$a_{f1}$&Satellite clock drift (seconds per second). Satellite clock error rate\\\midrule
Week&Week number since the last reset (i.e. since year 1980 modulo 1024 weeks)
\\\bottomrule
\end {tabular}
\end {table}

\begin {table}[hb]
\caption{GPS Ionosphere Model content}
\label{tbl:ionoModel}\centering 
%\rowcolor{2}{light-gray}{}
\scriptsize\fontfamily{iwona}\selectfont
\begin{tabular}{clccc}
\toprule 
%$D$&&$P_u$&$\sigma_N$\\
Field (IE) & Description\\\toprule
$\alpha_{0}$&Coefficient 0 of vertical delay\\\midrule
$\alpha_{1}$&Coefficient 1 of vertical delay\\\midrule
$\alpha_{2}$&Coefficient 2 of vertical delay\\\midrule
$\alpha_{3}$&Coefficient 3 of vertical delay\\\midrule
$\beta_{0}$&Coefficient 0 of period of the model\\\midrule
$\beta_{1}$&Coefficient 1 of period of the model\\\midrule
$\beta_{2}$&Coefficient 2 of period of the model\\\midrule
$\beta_{3}$&Coefficient 3 of period of the model
\\\bottomrule
\end {tabular}
\end {table}

\clearpage
\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
44 01000100
59 01011001
40 01000000
59 01011001
4B 01001011
20 00100000
00 00000000
00 00000000
70 01110000
70 01110000
00 00000000
70 01110000
00 0000....

   ....0000  Spare Bits = 0000b
\end{lstlisting}
\clearpage
\section{RRLP Response}
In this section the RRLP response from the MS shall be analysed. The RRLP response is  
constructed in the same manner as the RRLP request and assistance data by following
ASN.1 rules precisely specified in the RRLP standard. RRLP response is produced by the MS itself.
It may include the estimated position, data for estimating the position on the BTS (if MS assisted was
choosen as the prefered method) or errors indicating that some of the 
previously stated assistance data are missing. Missing data and errors are 
specified inside of the RRLP response. The response data shall be PER encoded and require
to be decoded into the ASN.1 notation. In listing \ref{lst:RRLPRespError} an example of an 
RRLP response with an error can be seen. The location error bit is set if the location 
of the MS is not present within the message (marked in red). The MS may sometimes supply more
information on the error if the MS knows this information (newer models support this).
In case it does support more information, it shall set an optional IE \textit{additionalAssistanceData} bit 
(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}@
D0 11010000
00 00000000
00 00000000
00 00000000
00 00000000
00 0000000.
   .......0  Spare Bits = 0b
\end{lstlisting}
This is followed with a more detailed explanation of the error that not sufficient
assistance data were present, \textit{LocErrorReason} (marked with blue color). There 
are other possible location error reasons as well and they are listed in listing 
\ref{lst:RRLPPosError}. Depending on the MS model, it can even further specify 
what kind of GPS assistance data are missing. This shall be well specified by setting 
the IE \textit{gpsAssistanceData} bit, this is shown in listing \ref{lst:RRLPRespError}
(marked with magenta color). If this bit is set, the length of the IE for requested missing assistance 
data shall 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}
\label{img:RequestedGPSAss}
\end{figure}
The first two bytes of the IE \textit{GPSAssistanceData} contain the information for requested
assistance AGPS data (marked in orange color). They 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}
is given 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 requsted
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! A successful or erroneous position response
is of RRLP measurement responses type, this can be seein in listing \ref{lst:RRLPRespSucc}
(bolded, in listing \ref{lst:RRLPRespError} it is bolded as well). It can not be
distinguished by analysing the first byte of the response stream! In the second byte, two mutually exclusive IE
contain the information if the response contains the location information or not, \textit{locationInfo} bit must
be set and \textit{locationError} must be unset (both marked in red color in listing \ref{lst:RRLPRespSucc}).
If the IE \textit{locationInfo} bit is one and \textit{locationError} bit 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 miliseconds. The 
most significant bits shall be derived by the SMLC using the GSM frame number, included in the IE \textit{refFrame}.
\textit{refFrame} contains the GSM frame number as observed by the MS without the TA factor taken into account \citep{49.031V8.1.0}!
The time of miliseconds 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.
\begin {table}[ht]
\caption{Requested AGPS assistance data bit meaning}
\label{tbl:RRLPReqAss}\centering 
%\rowcolor{2}{light-gray}{}
\scriptsize\fontfamily{iwona}\selectfont
\begin{tabular}{clccc}
\toprule 
%$D$&&$P_u$&$\sigma_N$\\
Bit (IE) & Description\\\toprule
$A$&Acquisition assistance requested\\\midrule
$B$&Reference time requested\\\midrule
$C$&Reference location requested\\\midrule
$D$&DGPS corrections requested\\\midrule
$E$&Navigation model requested\\\midrule
$F$&Ionospheric model requested\\\midrule
$G$&UTC model requested\\\midrule
$H$&Almanac data requested\\\midrule
$I$&Real time integrity requested\\\midrule
$J$&Ephemeris extension requested\\\midrule
$K$&Ephemeris extension check 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}
The position information is extracted with the inverse process as it was specified for the reference location. 
Equations to return from the bit format to decimal degrees are given in equation \eqref{eq:latLongBack}. %\clearpage
In the next chapter, more details shall be given on the implementation of the complete system.
\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}@
41 01000001
11 00010001
16 00010110
10 00010000
16 00010110
52 01010010
98 10011000
05 00000101
8C 10001100
58 01011000
45 01000101
3C 00111100
75 01110101
10 000100..
   ......00  Spare Bits = 00b
\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 employed hardware and the software implementation.
The main idea of author's approach to the problem is discussed in this chapter. 
The implementation can be divided into two stages. The first stage being the inital phase of 
the thesis where the initial system has been set up to perform RRLP tests. 
The second stage can be divided into two implemantation parts. The 
first part of the second stage consists of the development of the application
that generates RRLP assistance data. The second part of the second stage 
consists of modifying the existing open source GSM software and implementing the 
procedures for creating a data channel between the BTS and MS. This channel 
was deployed for the transmission of assistance data to the MS and for obtaining 
the response from the MS. 

\section{Initial phase}
Traditionally all radio communication systems are hard wired and 
the hardware is developed to do only one fixed function as the 
nanoBTS, to serve as a BTS. nanoBTS is a dedicated BTS hardware, 
used to set up the GSM network with OpenBSC (more details on 
the nanoBTS can be found in the hardware description). However, 
at the start of the thesis, the author had no access to the nanoBTS.
On the other hand, instead of the nanoBTS a software defined radio 
(SDR) platform was available and used to emulate the GSM network. 
SDR is a hardware platfrom that enables the development and test 
of different radio communication systems and 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. Those limitations 
can be the frequency on which the SDR can transmit and receive radio waves,
the speed of sampling a radio wave signal and other properties. 
The basic idea is to use the fast performace of a CPU from the 
computer to do the software 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 can be programmed to perform various 
functions e.q. an FM radio, a GPS receiver, GSM and etc.,
all of them employing different modulation/demodulation procedures and frequency spectrums
\citep{fmRadio} \citep{openBTS}. Theoretically ``anything'' can be 
built using an SDR platform that is within the domain of the SDR hardware. 

The exploited SDR platform in this thesis was the Universal Software 
Radio Peripheral (USRP) by Ettus Research. USRP had already a GSM and RRLP software
implementation. The GSM network software used on USRP was OpenBTS, a Linux 
application written in C++ employing the SDR platform to provide a GSM air interface \citep{openBTS}. Once the 
system has been successfully configured and set in operation it was followed by tests
to verify if it was operating correctly. 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, a strange behaviour could be noticed. 
Sometimes the smart phones ($iPhones$ $3GS$ and $4$) could not detect existance of the 
GSM network at all, 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. Although the clock unstability 
issue can not be confirmed by the author due to the missing hardware equipment to measure
the actual frequency and its deviation. Nevertheless, these results 
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 previously 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. 
Meanwhile the RRLP module was downloaded and installed. The module 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}}.
Once the RRLP module was configured and installed, the new GMS system configuration 
was examined. The first observation and finding was that not a single smart phone could 
connect to the GSM network. In the log files it could be seen a time out was triggered 
by OpenBTS. This timeout was triggered while the smart phones tried to get a 
position fix after the RRLP request was delivered to the MS. This result may be 
explained by analysing at what stage in the protocol the RRLP request was sent. 
The RRLP request was immediatelly sent after the paging request has been obtained by the MS.
This evidence justifies the time out behaviour. Once 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 sometimes 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, still no response was produced. 
One of the consequences of such behaviour was that the RRLP could not be tested 
inside of this set up because the system itself was unstable and had an unpredictive
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 module were used 
for comparison and a template to build author's RRLP assistance data generator. The nanoBTS 
is operated by OpenBSC which is explained in the following section.

\section{OpenBSC and its original RRLP implementation}
OpenBSC is an open source implementation of a GSM network software by Osmocom.
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 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 written 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 the interest for 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 
neither 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 more 
details in the following sections. 

\section{RRLP assistance data generator}
At the point of working on this 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 MS was to 
gain better understanding of the RRLP protocol and RRLP assistance data.
The RRLP assistance 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 wider extended or ported to another 
programming language, it was required to be written in a programming language
understandale by wider audience. It was sound to write the RRLP assistance 
data generator in C++ because OpenBSC was written in C and OpenBTS in C++. 
The main tasks here can be split up down to: verify the existance and age of 
assistance data download of the assistance data, conversion of the data, 
verification of their correctness, construction of RRLP packets according to 
the ASN.1 standard, conversion of it to PER and at last saving in the 
hexadecimal form in a text file.

In the almanac 
and ephemeris files, downloaded from NASA and Trimble, assistance data were stored
for 32 different GPS satellites. Contrary to expectations after the generated
RRLP packets have been analysed, Heimerl's code produced RRLP assistance 
data packets with only valid data for one satellite but duplicated 32 times. 
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 that have an ability to output them. 
Although almanac data can be in RINEX form as well, the almanac data 
found online were in the Yuma format. The read 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 contained also UTC model, 
and the ionospheric model. Other operational data were included in the 
configuration file like the reference location data, more details 
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 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.pdf}
  \caption{Flowchart for the RRLP assistance data generators}
\label{img:RRLPAlgFlowchart}
\end{figure}

Since the ephemeris data refresh every two hours, the latest generated data
are appended at the end of the file for the current reading\footnote{This
is performed by Trimble, whose ephemeris data were used.}.
It was common that the ephemeris assistance data contained errors which
were detected in the data range verification step. To avoid disruption 
in operation of the written software, once data out of range were detected
they are immediatelly 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 transmitted 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 step 
the assistance data are ready to be opened by OpenBSC and sent to the MS.

\section{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 open a data
channel. The original idea was to open a data channel with a silent
SMS and then to send the RRLP request. The opening of a data channel 
(SDCCH) and what is on going in OpenBSC can be split up into 4 
stages: adding a Virtual Teletype (VTY) interface to execute an 
RRLP request, open a physical data channel between the BTS and MS, 
opening the text file with assistance data and sending the data as 
well as parsing the RRLP packets, waiting for the response back and 
disconnecting. This will be explained in an sequential order of 
execution. 

The GSM network operator can connect to the VTY interface of OpenBSC 
using Telnet on port 4242 to issue commands and administer the GSM 
network. In order to send RRLP requests from the VTY command interface,
RRLP execution command had to be integrated. Function that integrates
that command is named \textbf{\texttt{subscriber\_silent\_rrlp\_start()}} 
and is in the file \textit{vty\_interface\_layer3.c}. Once the operator
executes on of the four implemented commands: RRLP request, RRLP request
with almanac data, RRLP request with ephemeris and other assistance data
or to end the execution of the RRLP request. For the first three commands,
the next executed function is \textbf{\texttt{gsm\_rrlp\_operation\_start()}} in 
the file \textit{silent\_call.c}. Any of the three commands will iniate 
the opening of an SDCCH channel (what in \textbf{\texttt{gsm\_rrlp\_operation\_start()}}
function takes place was already explained in \ref{sec:SDCCHChan}). In the case,
when the GSM operator can not wait for the RRLP request answer or wants 
to stop the execution of the RRLP request, he can issue a command in the VTY
interface to stop it, which will execute \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 that is responsible
for opening the text file with assistance data, copying the assistance data
into the RRLP data structure and transmitting 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 insdide 
%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{Hardware}
In the following chapter the author shall introduce the reader to the hardware
components used in the thesis. The hardware components shall be presented
according to their importance of 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. Additionally the mobile stations used for
testing of the system shall be reviewed. Finally, a hardware connection diagram
shall be given.
 
\section{GSM BTS - nanoBTS}
In recent years, there has been an increasing interest in deployment of
private cellular networks in remote areas or for research which lead to
the devolopment 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 and aviation; and public spaces''.
A nanoBTS with its plastic cover can be seen in Figure \ref{img:nanoBTSPlastic}. 
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 maximal output power
of +13 dBm ($\approx$20 mW)\todo{Check the output powere 20 dBm}, whereas the receiving frequencies
lie in the range between 1710-1785 MHz and same channel spacing as for transmission
of 200 kHz \citep{nanoGSM2007brochure}. \todo{Add the Abis over IP protocol}

\begin{figure}[ht!]
  \centering
  \includegraphics[scale=0.50]{img/nanoBTS.jpg}
  \caption{nanoBTS with its plastic cover. Image courtesy of ip.access ltd}
\label{img:nanoBTSPlastic}
\end{figure}

The nanoBTS is equiped with an internal 0 dBi (nominal) omni-directional antenna. However, 
two external antennas sized 30x36 mm, one for transmission (TX) and the other one for
reception (RX) of radio waves were used to extend the coverage area. These
antennas are connected via the SMA connectors. By using an RF amplifier
and larger antennas, for these frequency ranges, the covered area with the GSM signal
reception can be increased. For the gain estimation and radiation angle of the used antennas
the measurement equipment was missing and therefore was not conducted and described
in this work.\todo{Check for what NWL is}

At the bottom of the nanoBTS there are 5 ports, as seen in Figure \ref{img:nanoBTSPorts}.
The ports from left to right are: voltage supply, ethernet cable with power supply, USB
port, TIB-IN and TIB-OUT. In the next paragraph a brief overview of each port shall be given. 

\begin{figure}[ht!]
  \centering
  \includegraphics[scale=0.15]{img/nanoBTSPorts.jpg}
  \caption{nanoBTS with two external antennas and five connection ports}
\label{img:nanoBTSPorts}
\end{figure}

The left most port is the power supply port used for supplying the nanoBTS with 48 V DC
and is optionally used depending on the cable configuration. In author's hardware
configuration the power supply port is not used. The following port is for the ethernet
connection with 48 V DC power supply. This port is connected to a power supply
that is supplied with the nanoBTS. It extends the ethernet connection with 48 V DC 
for the normal operation mode of the nanoBTS which is in the range between 38-50 V DC.
The power consumption of the nanoBTS is 13 W. More details on how to interconnect the cables
shall be given in section \ref{sec:hardwareConfig}. In the middle of the five port region,
the mini USB port can be found. It is used by the manufacturer to write the firmware software
to the nanoBTS. The last two ports are the TIB-IN and TIB-OUT port\footnote{TIB stands
for Timing Interface Bus}. These two ports are used if the GSM network operator requires more
than 11 channels to increase the overall capacity of the network. 
``Up to 4 nanoBTS can be combined into a multiple TRX cell, increasing the number of 
supported users per TRX by up to 200\%. The TIB-OUT from the Master TRX must be connected to
the TIB-IN of the slave TRX. This in turn has its TIB-OUT connected to the next TRX in the chain''
\citep{multipleTRX}. The multiple TRX cell configuration shall not be further discussed in this work
since the purpose of the work was not to boost the capacity of a GSM network but implementation 
and testing of the RRLP protocol.

To determine the working state of the nanoBTS, an indicator status LED is located on the
left side of the five ports region. After the nanoBTS is connected to the power suplly
with the ethernet cable, it shall change its color and blink speed according to the state
it is in. The states 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. 


\begin {table}[hb]
\caption{Indicator LED status on the nanoBTS}
\label{tbl:LEDStatus}\centering 
%\rowcolor{2}{light-gray}{}
\scriptsize\fontfamily{iwona}\selectfont
\begin{tabular}{cccc}
\toprule 
%$D$&&$P_u$&$\sigma_N$\\
State&Color \& Pattern&When&Precedence\\\toprule
Self-test failure&Red - Steady       &In boot or application code when a power&1 (High) \\
				     &&on self-test fails\\\midrule
Unspecified failure&Red - Steady &On software fatal errors&2\\\midrule
No ethernet&Orange - Slow flash &Ethernet disconnected&3\\\midrule
Factory reset&Red - Fast blink       &Dongle detected at start up and the&4\\
				     &&factory defaults have been applied\\\midrule
Not configured&Alternating Red/&The unit has not been configured&5\\
	       &Green Fast flash\\\midrule
Downloading code&Orange - Fast flash &Code download procedure is in progress&6\\\midrule
Establishing XML&Orange - Slow blink &A management link has not yet been established&7\\
				      &&but is needed for the TRX to become operational.\\
				      &&Specifically: for a master a Primary OML or\\
				      &&Secondary OML is not yet established; for a\\
				      &&slave an IML to its master or a Secondary \\
				      &&OML is not yet established. \\\midrule
Self-test &Orange - Steady            &From power on until end of backhaul&8\\
				      &&power on self-test\\\midrule
NWL-test 	 &Green - Fast flash& OML established, NWL test in progress&9\\\midrule
OCXO Calibration &Alternating Green/& The unit is in the fast calibrating state [SYNC]&10\\
	         &Orange - Slow blink\\\midrule
Not transmitting &Green - Slow flash & The radio carrier is not being transmitted &11\\\midrule
Operational &Green - Steady & Default condition if none of the above apply&12 (Low)\\\bottomrule
\end {tabular}
\end {table}


%\begin{table}[h!t!p!]
%\begin{center}
%\caption{Indicator LED status on the nanoBTS}
%\begin{tabular}{|c||p{3cm}|p{5cm}|c|c|}
%\hline
%% \T and \B would not work if it is placed here (needs to go inside cell)
% State&Color \& Pattern&When&Precedence \\ \hline\hline
% Self-test failure&Red - Steady&In boot or application code when a power on self-test fails&1 (High) \\ \hline
% Unspecified failure&Red - Steady &On software fatal errors&2 \\ \hline
% No ethernet&Orange - Slow flash &Ethernet disconnected&3 \\ \hline
% Factory reset&Red - Fast blink &Dongle detected at start up and the factory defaults have been applied&4 \\ \hline
% Not configured&Alternating Red/Green - Fast flash &The unit has not been configured&5 \\ \hline
% Downloading code&Orange - Fast flash &Code download procedure is in progress&6 \\ \hline
% Establishing XML&Orange - Slow blink &A management link has not yet been established&7\\
%				      &&but is needed for the TRX to become operational.\\
%				      &&Specifically: for a master a Primary OML or\\
%				      &&Secondary OML is not yet established; for a\\
%				      &&slave an IML to its master or a Secondary \\
%				      &&OML is not yet established. \\ \hline
% Self-test &Orange - Steady & From power on until end of backhaul powe on self-test&8 \\ \hline
% NWL-test &Green - Fast flash & OML established, NWL test in progress&9 \\ \hline
% OCXO Calibration &Alternating Green/Orange - Slow blink & The unit is in the fast calibrating state [SYNC]&10 \\ \hline
% Not transmitting &Green - Slow flash & The radio carrier is not being transmitted &11 \\ \hline
% Operational &Green - Steady & Default condition if none of the above apply&12 (Low) \\ \hline
% 
%\end{tabular}
%\end{center}
%\label{tbl:LEDStatus} 
%\end{table}


\newpage
\section{GPS Receiver - NL-402U}
\label{sec:gpsDevice}
In the next paragraphs the used GPS device shall be described. 
In contrast to the earlier described hardware, nanoBTS, which the University of Freiburg
already owned, the budget for the GPS receiver was limited and the Navilock NL-402U
was bought considering only the single criterion, the price. The Navilock NL-402U
GPS receiver is based on the u-blox UBX-G5000 single chipset and is a one 
chip solution \citep{ubxDatasheet}. It can be seen on Figure \ref{img:gpsNavilock}
with its passive ceramic patch antenna. 1575,42 MHz is the operating frequency of
the receiver which corresponds to the L1 civil frequencies and Coarse/Acquisition (C/A) code.
The GPS chipset consists of 50 channels,
each channel tracks the transmission from a single satellite \citep{understandGPS}.
It is important to note, the number of channels inside a GPS receiver interrelates 
with the amount of time required to obtain the first fix. Receiver tracking sensitivity is 
-160 dBm ($10^{-16}$ mW). 
The GPS receiver communicates with the computer ovet the USB port.
Although the GPS receiver uses an USB interface, on the computer it emulates 2 UART ports, 
which are serial communication interfaces.


\begin{figure}[ht!]
  \centering
  \includegraphics[scale=0.12]{img/gpsNavlock.jpg}
  \caption{Navilock NL-402U, opened up with the antenna and USB cable}
\label{img:gpsNavilock}
\end{figure}

\section{Cable configuration}
\label{sec:hardwareConfig}
In the next section, the author shall focus on properly connecting the hardware. 
At least 4 ethernet cables with RJ45 connectors, on both sides, were required
and one switch or hub connected to the internet. One should
take notice of the cabling between the nanoBTS and the ethernet switch or hub,
since wrong cabling 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}.

\begin{figure}[ht!]
  \centering
  \includegraphics[scale=0.5]{img/hardwareConnection}
  \caption{Cable connections, showing interconnection diagram}
\label{img:connectionDiagram}
\end{figure}

\chapter{Results}
One of the most important parts of this thesis are the results that
shall be presented in this chapter. Tests will be explained and how the results 
were obtained. Analysis of the results by the time required to perform a 
localization of a GSM user and the geographical dislocation error using 
Google maps are going to be discussed. Smart phones used 
for the test are going to be introduced and followed by the location
of the tests. After the results have been provided,
a section with criticism demonstrates all the obstacles that may have appeared
while the tests have been performed and why some of the results may be biased. The criticism
section is a vital part of this thesis, aside from the given theoretical and
mathematical perspective of how AGPS works and why lack of time synchronization inside
GSM can be of critical value to correctly evaluate the results. It gives an additional 
insight into the complete operation of the built localization system in this thesis. 

\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. 

\newpage
\subsection{Smart phones tested}
The requirement for a cell phone to be taken into account 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 have satisfied the 
criterion and have been used to perform the tests, as given in 
table \ref{tbl:smartphones}. 

\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}{clccc}
\toprule 
%$D$&&$P_u$&$\sigma_N$\\
Cell phone & Manufacturer \& Country\\\toprule
$Defy$&Motorola, USA\\\midrule
$iPhone$ $4$&Apple, USA\\\midrule
$iPhone$ $3GS$&Apple, USA\\\midrule
$G1$&Google, USA\\\midrule
$Galaxy$ $S2$&Samsung, South Korea\\\midrule
$Galaxy$ $S3$&Samsung, South Korea\\\midrule
$Galaxy$ $Nexus$ $i9250$&Samsung, South Korea\\\midrule
$E71$&Nokia, Finland\\\midrule
$N95$&Nokia, Finland\\\midrule
$Desire$ $S$&HTC, Taiwan\\\midrule
$Blade$&ZTE, P.R. of China
\\\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, UTC model, ionospheric model and 
reference location data. 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 make an usage of the assistance data. 
The RRLP requests were manually sent from the telnet interface from OpenBSC after they have been
implemented by the author. Results delivered by the MS were stored in the database and the 
following analysis is based on them and on the time out results which were not stored in the 
database but notices by the author. 

\begin{figure}[ht!]
  \centering
  \includegraphics[scale=0.38]{img/googlemapsResults.pdf}
  \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 this two smart phone 
position tests in the room showed that smart phone position did not
make any influence on the test results. The delivered position coordinates by the smart
phones in all performed tests were in range of the green rectangle labeled with a white one. 
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 smart phones that provided these results
were the $iPhone$ $3GS$ and $G1$. The $iPhone$ $3GS$ sent only a response when all assistance data 
(almanac, ephemeris, UTC model, ionospheric model and reference location data) have been delivered
whereas the $G1$ only when the assistance data without ephemeris data were delivered or by only sending
an RRLP request without any assistance data. It is apparent from these facts that the $iPhone$ $3GS$ 
had used the assistance data to estimate its position otherwise it would send it is position back also
when only an RRLP position request was sent. Interestingly, the $G1$ did not deliver any results
when the ephemeris data have been delivered to it. These findings suggest that the AGPS receiver in 
$G1$ may not know how to employ the ephemeris data because it is one of the first ``real'' smart phones on the 
market. Later on it can be seen other smart phones that are even older than the $G1$ can not employ any of the 
assistance data.

\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[width=\textwidth]{img/smartPhoneWindow.jpg}
                \caption{Smart phones 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[width=\textwidth]{img/smartRoomTable.jpg}
                \caption{Smart phones 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}

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 tests took place in the basement adds
an additional obstacle to the AGPS receiver in the MS, the signal strength of GPS
signals is 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 a few times longer than in the 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 obtained results from
the tests in Test room 2 can be seen in figure \ref{img:googlemapsResults}, two 
red rectangles labeled with a two in the left upper corner. 
It is somewhat surprising that different cell phone models delivered different 
positions (two different rectangle ranges) at different times of the day. 
This finding suggests that not the equal number of satellites were visible 
at the different time points when the tests have been performed. 
By observing the results in figure \ref{img:googlemapsResults}, 
it is straightforward to see deviation 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 greater 
with the GPS signal reception quality and with reduced 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 $3 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 resulting estimated position. The smart phones tested in Test 
room 2 were all the listed ones 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 result.
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 and author's given statements 
have to be considered with ambiguity. Another contrary to expectations, were the 
results with two Nokia ``smart phone'' models $E71$ and $N95$, results were only 
delivered when an RRLP request was sent without any assistance data. Although it was 
stated in their specifications both are equiped with an AGPS receiver 
RRLP requests with assistance data did not produce any output from these smart phones
\citep{nokiae71} \citep{nokian95}. The reason for this is not clear 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 they were released by Nokia the firmware for the phones
might not have been fully evolved and 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 smart phones tested did not deliver any positions but only errors about 
missing assistance data and time outs. While no MS delivered its 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^{16}$ mW)
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 just after the smart phones delivered successfully 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 provided and confirmed that the smart phones are always performing a 
postion estimation at the moment when an RRLP request is sent to the MS.

The last test has been performed 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 
in the left corner of it. 

\begin {table}[ht]
\caption{Smart phone RRLP test results}
\label{tbl:resultsByTest}\centering 
%\rowcolor{2}{light-gray}{}
\scriptsize\fontfamily{iwona}\selectfont
\begin{tabular}{lllll}
\toprule 
%$D$&&$P_u$&$\sigma_N$\\
Cell phone model&RRLP(E)&RRLP(A)&RRLP&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&Sometimes&/\\\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 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) indicated the MS has delivered its position only when an RRLP request contained 
almanac, UTC model, ionospheric model and reference location data has been sent (the difference
from RRLP(E) is in the fact that no ephemeris data are included). If there is no error description
then the stated data were requested to be delivered to the MS. If the position was delivered the 
position estimation by the smart phones took never longet 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 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 MS responded only with 
acknowledgements while the assistance data have been sent but after the reception it 
immediatelly 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 behaved like a 2G cell phone without a GPS receiver. To eliminate any doubts and 
suspicion if the SDCCH channel was properly working and not producing the time outs, 
2G phones (Nokia 3310 and Siemens M50) have been used to perform tests. An SDCCH channel 
has been initialized 10 times at 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 for the cases where the time out appeared, 
it was not produced by the BTS but rather by the smart phone. One important remark related
to the tests ought to be mentioned. While the $iPhone$ $3GS$ and $G1$ provided the results in
the tests, sometimes it was the case they did not deliver the results the first time 
the RRLP request was executed but an time out. Second time the same RRLP request was 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 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 the manufacturers that claim AGPS functionality. Does it 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 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 about the hardware 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. 

Difficulties arise in assessment and comparing the results in this 
thesis with other relevant studies due to the lack of any research 
studies compleyed using the equivalent hardware and 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 it has 
only been 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. GPS signal strength is a vital 
measurement information, where the signal levels are lower than a 
predefined acquisition sensitivity even assistance data can not help.
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 NASA 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 range specified by the standard).
These errors were not continual but appeared occasionally and these errors
were inside of the assistance data provided by NASA. 

\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 NASA and Trimble. Obtained data by the GPS
could be compared to the data provided by NASA or other GPS observation stations
and verified for errors. By having more redundant sources of same information, 
mistakes in the output could be eliminated. More 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 great changes 
in the OpenBSC source code and interoperability between the BTS and LMU.

Additionally a position tracking system could be built. By adding a timer that will
execute an RRLP request every few minutes. The successfully estimated positions could
be connected into a path and displayed where the GSM user spends his time. Along the 
described method, a machine learning algorithm could be developed to predict the 
movement of GSM users \citep{predictMovements}.

%Tests could be performed if it possible  if it can be tricked out by the software Dennis mentioned (protect my privacy)!

\chapter{Summary and discussion}
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. 




\chapter*{Dictionary of acronyms}
\begin{itemize}
\item \emph{ARFCN} - Absolute Radio Frequency Channel Number - The channel number specifies the physical frequency channel used for transmission and reception of radio waves inside of an BTS covered area.
\item \emph{BTS} - Base Transceiver Station - 
\item \emph{DC} - Direct Current
\item \emph{GNSS} - Global Navigation Satellite System - A satellite navigation system that allows a specialized receive to determine its location on Earth.
\item \emph{LED} - Light Emitting Diode - A diode that emitts light.
\item \emph{IP Address} - \todo{Write what an IP address is}.
\item \emph{PCB} - Printed Circuit Board - The board where electronic components are soldered onto and wired through conductive tracks.
\item \emph{RRLP} - Radio Resource Location Protocol - The employed protocol in GSM, UMTS and other wireless networks for providing and exchange of geolocation information. 
\item \emph{SMA} - SubMiniature version A - SMA is a connector used for interconnecting coaxial cables or PCB electronics that work in the frequency range between 0-18 GHz.
\item \emph{TIB} - Time Interface Bus - The TIB is used to provide the synchronization of the clock, frequency and frame number between the nanoBTS when operating in a single 2-4 BTS configuration.
\item \emph{TRX} - 
\item \emph{UART} - Universal Asynchronous Receiver Transmitter - A serial communication interface used by computers or other peripheral devices to communicate.
\item \emph{UMTS} - Universal Mobile Telecommunications System - Third generation mobile network based on the GSM standards. 
\end{itemize}