FREQUENCY OFFSET ESTIMATION FOR GPS ENABLED WI-FI ACCESS POINTS by Tausif Ezaj Khan BEng, Queen Mary, University of London, UK, 2011 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE COLLEGE OF GRADUATE STUDIES (Electrical Engineering) THE UNIVERSITY OF BRITISH COLUMBIA (Okanagan) May 2015 © Tausif Ezaj Khan, 2015 ii ABSTRACT A method to estimate the frequency offset between the internal oscillators of two or more GPS RF front-ends is described and evaluated. The purpose of this is to allow a Non-Line-of-Sight (NLOS) GPS receiver to acquire and track satellite signals with assistance data provided by a Line-of-Sight (LOS) GPS receiver. This facilitates indoor positioning with GPS, which is used to accurately position 802.11 WLAN access points that will be used in an integrated indoor positioning system. The assistance data consists of the Doppler frequency and code phase of GPS satellites that the LOS GPS receiver can clearly view. Knowing this information at the NLOS GPS receiver significantly reduces the Doppler search space and code phase search space resulting in faster signal acquisition. To effectively use this assistance information, the NLOS GPS receiver oscillator must be synchronized to that of the LOS GPS receiver to within 10 ns. This frequency synchronization is accomplished by estimating the frequency offset between the two oscillators with a signal transmitted between the two receivers via a WLAN channel. COCC (Carrier Only Cross Correlation) and CCCC (Code + Carrier Cross Correlation) are two proposed techniques to estimate this frequency offset to within ±30 Hz. In COCC, a single carrier signal is sent by the LOS receiver at 10.23 MHz and cross-correlated with a replica signal generated at the NLOS receiver. This technique’s best performance (frequency estimation within ±30 Hz) is achieved at SNR > -4 dB in an AWGN channel and at SNR > 22 dB in a Rayleigh fading channel at a separation distance of 25 m. The CCCC technique has a 1023 chip PRN code at 1.023 Mega chips/sec modulated on the transmitted carrier signal and is cross-correlated with the replica code-modulated signal generated at the NLOS receiver. The optimum code sampling frequency for iii CCCC was found to be 10 MHz. It is shown that CCCC can estimate a frequency offset to within ±30 Hz at SNR > -14 dB in an AWGN channel and SNR > -10 dB in a Rayleigh fading channel at a separation distance of 35 m. iv PREFACE This thesis is a result of an NSERC Engage project with a company in Vancouver known as Rx Networks Inc. I was responsible for conducting a literature review and developing an algorithm to synchronize two or more oscillators as per the company’s requirements. All experiments in chapter 4 were conducted in EME 3216 on UBC’s Okanagan campus with the help of my supervisor Dr. Richard Klukas. v TABLE OF CONTENTS ABSTRACT ................................................................................................................................... ii PREFACE .................................................................................................................................... iv TABLE OF CONTENTS ............................................................................................................. v LIST OF TABLES ....................................................................................................................... xi LIST OF FIGURES .................................................................................................................... xii LIST OF SYMBOLS .................................................................................................................. xv ABBREVIATIONS .................................................................................................................... xix ACKNOWLEDGEMENTS ...................................................................................................... xxi DEDICATION.......................................................................................................................... xxiii CHAPTER 1: INTRODUCTION AND THESIS ORGANIZATION ..................................... 1 1.1 MOTIVATION ................................................................................................................ 2 1.2 OBJECTIVE .................................................................................................................... 3 1.3 THESIS ORGANIZATION ............................................................................................ 3 CHAPTER 2: PREVIOUS WORK ON INDOOR POSITIONING, INDOOR CHANNEL MODELS AND SOME IMPORTANT PARAMETERS ............ 5 2.1 IPS (INDOOR POSITIONING SYSTEM): AN OVERVIEW ....................................... 5 2.2 DIFFERENT IPS TECHNOLOGIES, METHODS AND TECHNIQUES .................... 6 2.2.1 Trilateration ........................................................................................................ 6 vi 2.2.2 Triangulation ...................................................................................................... 9 2.2.3 Vision Analysis .................................................................................................. 9 2.2.4 Fingerprinting Method ...................................................................................... 10 2.2.5 Weighted Centroid Localization (WCL) Method ............................................. 10 2.3 CATEGORIES OF INDOOR POSITIONING SYSTEMS........................................... 11 2.3.1 Network Based vs Non-Network Based IPS .................................................... 11 2.4 EVALUATION CRITERIA FOR IPS .......................................................................... 11 2.4.1 Cost ................................................................................................................... 12 2.4.2 User Preference................................................................................................. 12 2.4.3 System Performance ......................................................................................... 12 2.4.4 Privacy and Security ......................................................................................... 13 2.5 EXISTING INDOOR POSITIONING SYSTEMS ....................................................... 13 2.5.1 Ultra-sound Positioning System ....................................................................... 13 2.5.2 Infrared (IR) Positioning System ...................................................................... 14 2.5.3 Indoor Positioning Using Radio Frequency (RF) ............................................. 14 2.5.3.1 RFID (Radio Frequency Identification) ............................................. 15 2.5.3.2 Ultra-Wideband (UWB)..................................................................... 16 2.5.3.3 Bluetooth ............................................................................................ 16 2.5.3.4 Wireless Local Area Networking, WLAN ......................................... 17 2.5.4 Sensor Networks ............................................................................................... 17 vii 2.5.5 Vision/Image Based Positioning System .......................................................... 18 2.5.6 Positioning System Using Sound ..................................................................... 18 2.6 GPS FOR INDOOR POSITIONING SYSTEM ............................................................ 19 2.6.1 GPS System Structure ...................................................................................... 19 2.6.2 GPS Position Estimation Technique ................................................................ 20 2.6.2.1 GPS Signal Structure ......................................................................... 20 2.6.2.2 The Receiver ...................................................................................... 20 2.6.2.3 Mathematics for Code to Distance Conversion of GPS Signals ........ 21 2.6.3 Problems Associated with IPS using GPS Technology.................................... 23 2.6.4 Current Techniques to Mitigate the Problems of GPS for IPS ......................... 25 2.7 WLAN FOR INDOOR POSITIONING TECHNIQUE ................................................ 28 2.7.1 Position Estimation using WLAN .................................................................... 28 2.7.2 Advantages and Disadvantages of a WLAN based IPS ................................... 30 2.7.3 Recent Advancements in IPS using WLAN Method ....................................... 32 2.8 SUMMARY OF IPS ...................................................................................................... 33 2.9 CHANNEL MODELS AND IMPORTANT PARAMETERS ..................................... 35 2.9.1 Free-Space Path-loss Model (FSPL) ................................................................ 36 2.9.2 Empirical Path-loss Channel Model ................................................................. 37 2.9.2.1 Simplified Path-Loss Model .............................................................. 37 2.9.2.2 Simplified Path-loss Model with Shadow Fading ............................. 38 viii 2.9.3 AWGN Channel ............................................................................................... 40 2.9.4 Rayleigh Fading Channel ................................................................................. 42 2.9.5 Rician Fading Channel ..................................................................................... 44 2.9.6 Pseudo-Random Number (PRN) Code ............................................................. 45 2.9.6.1 Generating PRN Codes using LFSR .................................................. 45 2.9.7 Cross-Correlation and Auto-Correlation Function of Gold Codes ................... 48 2.9.8 Circular Shift .................................................................................................... 51 CHAPTER 3: FREQUENCY AND PHASE OFFSET ESTIMATION FOR IPS ................ 52 3.1 GPS SATELLITE CONSTELLATION ........................................................................ 52 3.2 IMPORTANCE OF SYNCHRONIZATION IN GPS TECHNOLOGY ...................... 52 3.3 GPS-WLAN AUGMENTED IPS AND ITS CHALLENGES ...................................... 54 3.4 REASONS FOR CLOCK DRIFT AND FREQUENCY DIFFERENCE ..................... 56 3.5 PROPOSED TECHNIQUES FOR FREQUENCY OFFSET ESTIMATION .............. 56 CHAPTER 4: EXPERIMENTS, RESULTS AND DISCUSSION ......................................... 60 4.1 COCC EXPERIMENTS, RESULTS AND DISCUSSION .......................................... 60 4.1.1 Experiment 1: Verification of Cross-correlation Process for Frequency Estimation. ....................................................................................................... 60 4.1.2 Experiment 2: Estimated Frequency Offset Error at Variable Clock Drifts. .... 62 4.1.3 Experiment 3: Estimated Frequency Offset Error for an AWGN Channel as a Function of SNR. .......................................................................................... 64 ix 4.1.4 Experiment 4: SNR Variations for a Simplified Path-Loss Model with Shadow Fading and AWGN at Different Distances. ....................................... 66 4.1.5 Experiment 5: Estimated Frequency Offset Error for a Rayleigh Fading Channel Model. ............................................................................................... 67 4.1.6 Experiment 6: Estimated Frequency Offset Error for a Rician Channel Model. .............................................................................................................. 68 4.1.7 Experiment 7: Effect of Phase Offset on Estimated Frequency Offset Error… ............................................................................................................. 70 4.1.8 Conclusion ........................................................................................................ 71 4.2 CCCC BASED EXPERIMENTS, RESULTS AND DISCUSSION ............................ 72 4.2.1 Experiment 1: Cross-correlation for Signal Detection at Receiver .................. 73 4.2.2 Experiment 2: Effect of Code Length on Estimated Frequency Offset Error… ............................................................................................................. 76 4.2.3 Experiment 3: Effect of Code Sampling Frequency on Estimated Frequency Offset Error ...................................................................................................... 78 4.2.4 Experiment 4: Estimated Frequency Offset Error in an AWGN Channel Only ................................................................................................................. 80 4.2.5 Experiment 5: Estimated Frequency Offset Error for Different Distances in a Simplified Path-loss Model with Shadowing ............................................... 82 4.2.6 Experiment 6: Estimated Frequency Offset Error in a Rayleigh Fading Channel ............................................................................................................ 84 x 4.2.7 Experiment 7: Estimated Frequency Offset Error in a Rician Channel ........... 87 4.2.8 Conclusion ........................................................................................................ 88 CHAPTER 5: CONCLUSIONS AND FUTURE WORK ....................................................... 91 5.1 CONCLUSIONS ........................................................................................................... 91 5.2 LIMITATIONS AND FUTURE WORK ...................................................................... 93 REFERENCES ............................................................................................................................ 94 xi LIST OF TABLES Table 2.1. Comparison Between Different IPS Methods. ....................................................... 34 Table 2.2. A Comparison Between Popular Positioning Systems Used for IPS. .................. 34 Table 2.3. Typical Path-Loss Exponents. ................................................................................. 38 Table 4.1. COCC Channel Parameter to Achieve the Desired Frequency Offset Estimation within a Maximum Allowable Estimation Error of ±30 Hz. .................................... 71 Table 4.2. Average Estimated Frequency Offset Error per Sampling Frequency. ..................... 79 Table 4.3. PRN Code Parameter for the CCCC Algorithm. ....................................................... 89 Table 4.4. CCCC Channel Parameter to Achieve the Desired Frequency Offset Estimation within a Maximum Allowable Estimation Error of ±30 Hz. ...................................... 89 xii LIST OF FIGURES Figure 2.1. An Overview of Trilateration Technique. ................................................................... 7 Figure 2.2. Trilateration of Point T. .............................................................................................. 8 Figure 2.3. 2-D Satellite Acquisition Search Space. ................................................................... 24 Figure 2.4. An Overview of A-GPS System Structure. .............................................................. 27 Figure 2.5. Received Signal Power vs Log of Distance for Shadow Fading and FSPL. ............ 39 Figure 2.6. High Level Block Diagram of an AWGN Channel.................................................. 40 Figure 2.7. Real Band-pass Noise PSD. ..................................................................................... 41 Figure 2.8. A sequence of 5 LFSRs. ........................................................................................... 46 Figure 2.9. 127 bit long Gold Code generated using the polynomial g(x) = 1+x1+x7. ............... 47 Figure 2.10. 127 bit long Gold Code generated using the polynomial g(x) = 1+x3+x7. ............... 48 Figure 2.11. Auto-correlation of a PRN code with the Prompt Replica. ..................................... 50 Figure 2.12. Auto-correlation Function for N=31 Gold sequence. .............................................. 50 Figure 3.1. High Level Block Diagram of COCC Method. ........................................................ 57 Figure 3.2. High Level Block Diagram of CCCC Method. ........................................................ 57 Figure 4.1. Correlation at the Correct Frequency Bin Using the COCC Algorithm. ................. 61 Figure 4.2. Estimated Frequency Offset Error in a Noise-Less Channel Using the COCC Algorithm. ................................................................................................................ 63 Figure 4.3. Estimated Frequency Offset Error in an AWGN Channel Using the COCC Algorithm. ................................................................................................................ 65 Figure 4.4. SNR as a Function of Distance for Simplified Path-Loss Model with Shadowing for COCC Algorithm. .............................................................................................. 66 xiii Figure 4.5. Estimated Frequency Offset Error in a Rayleigh Fading Channel Using the COCC Algorithm. .................................................................................................... 68 Figure 4.6. Estimated Frequency Offset Error in Rician Channel (Fixed distance of 25 m) Using the COCC Algorithm. .................................................................................... 69 Figure 4.7. Effect of Phase Offset on Frequency Estimation. .................................................... 70 Figure 4.8. Serial Search Acquisition of Satellite 1 PRN Code.................................................. 74 Figure 4.9. Serial Search Acquisition of Satellite 3 PRN Code.................................................. 75 Figure 4.10. Serial Search Acquisition of Satellite 10 PRN Code................................................ 75 Figure 4.11. Estimated Frequency Offset Error vs Code Sample Delay for Different Code Lengths for the CCCC Algorithm. .......................................................................... 77 Figure 4.12. Estimated Frequency Offset Error vs Code Sample Delay for Different Code Sampling Frequencies for the CCCC Algorithm. ................................................... 79 Figure 4.13. Estimated Frequency Offset Error vs SNR (-40 dB to 40 dB) in an AWGN Channel Using the CCCC Algorithm. ..................................................................... 81 Figure 4.14. Estimated Frequency Offset Error vs SNR (-30 dB to 40 dB) in an AWGN Channel Using the CCCC Algorithm. ..................................................................... 82 Figure 4.15. Estimated Frequency Offset Error vs Distance (1 m to 100 m) in a Simplified Path-Loss Model with Shadowing Using the CCCC Algorithm. ........................... 83 Figure 4.16. Estimated Frequency Offset Error vs Distance (1 m to 60 m) in a Simplified Path-Loss Model with Shadowing Using the CCCC Algorithm. ........................... 83 Figure 4.17. Estimated Frequency Offset Error vs SNR (dB) in a Rayleigh Fading Channel Using the CCCC Algorithm. ................................................................................... 85 xiv Figure 4.18. Estimated Frequency Offset Error vs SNR (-12 dB to 40 dB) in a Rayleigh Fading Channel Using the CCCC Algorithm. ......................................................... 85 Figure 4.19. Estimated Code Sample Delay Error vs SNR (dB) in a Rayleigh Fading Channel Using the CCCC Algorithm. ..................................................................... 86 Figure 4.20. Estimated Frequency Offset Error vs Rician k factor in a Rician Channel Using the CCCC Algorithm. .............................................................................................. 88 xv LIST OF SYMBOLS 𝛼 SNR B Bandwidth Bj Beacon signal bps Bits per second C Capacity c Speed of light d Distance between the transmitter and the receiver dB Decibels ?̂? The KNN estimated distance 𝑑𝑘 PSD of neighbor k 𝑑0 Reference distance 𝛿𝑡𝑅 Receiver clock bias 𝛿𝑡𝑆 Satellite clock bias 𝜀𝑘 Multipath, noise and other error measurement 𝑓 Frequency 𝑓𝑐 Centre frequency 𝐺𝑙 Antenna gain γ Path-loss exponent 𝜃 Phase angle between two signals 𝐼𝑘 Ionosphere effect 𝐼0 Modified Bessel function of the zeroth order xvi K Path loss component due to environment and antenna characteristics k Rician k factor 𝜆 Wavelength µ Micro M Mega ms Milliseconds N Integer ambiguity or whole number of wave cycles 𝑁0 Noise power n(t) Noise ns Nano second P Transmit power ppm Parts per million 𝑃?̅? Average received power Pr Received power Pt Transmit power 𝜋 pi q Indoor attenuation factor 𝑅(𝑘)(𝜏) Auto correlation of signal coming from satellite 𝑘 𝑅(𝑥,𝑦)(𝑡) Cross correlation of signals 𝑥 and 𝑦 𝑟𝐼 Random variable with non-zero mean 𝑟𝑄 Random variable with zero mean 𝑟𝑘 Geometric range from satellite k r(t) Received signal xvii 𝑟𝐿𝑃(𝑡) Equivalent low pass of signal r(t) 𝜌𝑘 Pseudo-range from satellite k s Standard deviation s(t) Transmit signal 𝑠2 Power in line of sight component σ Standard deviation σ2 Variance Σ Summation 𝑠𝑘 SSD of neighbor k 𝑇𝑘 Tropospheric effect t Time 𝜏 Propagation delay 𝜙(𝑡) Phase of GPS carrier signal 𝜙𝑢(𝑡) Phase of the receiver generated replica signal 𝜙𝑠(𝑡 − 𝜏) Phase of the signal received from the satellite at time t 𝑥(𝑘)(𝑡) Signal from satellite 𝑘 𝑥(𝑘)(𝑡 − 𝜏) Delayed version of 𝑥(𝑘)(𝑡) X Gaussian random variable X x Transmit signal ‘x’ Y Gaussian random variable Y y Received signal ‘y’ Ψ Ratio of transmit to received power 𝑤𝑘 Weighting factor for nearing k member xviii 𝑤𝑖.𝑗 Sum of weight factors ω Angular frequency (2𝜋f) ⊕ XOR operation xix ABBREVIATIONS A-GPS Assisted GPS AOA Angle of Arrival AP Access Point AWGN Additive White Gaussian Noise BPSK Binary Phase Shift Keying BS Base Station C/A Course Acquisition CCCC Code + Carrier Cross Correlation COCC Carrier Only Cross Correlation FSPL Free Space Path Loss GPS Global Positioning System GSM Global System for Mobile INS Inertial Navigation System IPS Indoor Positioning System IR Infra-Red KNN K Nearest-Neighbour LFSR Linear Feedback Shift Register LOS Line of Sight MCU Master Control Unit MSC Mobile Switching Centre MEMS Micro-Electro Mechanical Devices NLOS Non Line of Sight OFDM Orthogonal Frequency Division Multiplexing PL Path Loss PPM Parts Per Million PRN Pseudo Random Number PSD Power Spectral Density xx PVT Position Velocity Time RAM Random Access Memory RF Radio Frequency RFID Radio Frequency Identification RSS Received Signal Strength SNR Signal to Noise Ratio SPL Simplified Path-loss SSD Signal Space Distance SVN Space Vehicle Number TDOA Time Difference of Arrival TOA Time of Arrival TTFF Time to First Fix UWB Ultra Wide Band WCL Weighted Centroid Localization WLAN Wireless Local Area Network XOR Exclusive OR xxi ACKNOWLEDGEMENTS My first and foremost gratitude goes to my supervisor, Dr. Richard Klukas for his guidance, constant encouragement, and the advice he has provided me throughout my time as his student. He has drawn an end to all my delusions about graduate supervisors which were developed by depressing stories about graduate life and tales of horrifying professors. The constant support, friendship and unending level of endurance of my supervisor, Dr. Klukas, have been invaluable in my life on the frontiers of both academic and personal life, for which I am extremely grateful to him. He has supported and motivated me even in times of great turmoil and distress. Completing this work would have been very difficult were it not for all his support, his down to earth nature and his calm demeanour, which actually made me completely relaxed even at times when things were not going right. I consider myself to be extremely lucky to have a supervisor like him, who has cared so much for me as well as for my work. I was lucky to have a wonderful start to my graduate life because of a wonderful supervisor as Dr. Richard Klukas. I would also like to thank my committee members, Dr. Jahangir Hossain and Dr. Thomas Johnson for being a part of my supervisory committee. Thanks to Haris Afzal of Rx Networks. Inc. for his constant support on the project which later turned into my thesis. The countless phone conversations we had with him made me clear on what I had to do with my work. Also, the knowledge and wit that Haris has shared with me was invaluable. I must also express my gratitude towards my postgraduate friend, Zoheb Hassan for teaching me MATLAB® from scratch, which served as the vital simulation tool for my thesis. His constant patience, the time he took to teach me coding in MATLAB® and his unfathomable depth in digital communication helped me a get a crystal clear view of the work I did in my thesis. He truly is a brilliant and a wonderful guy. I xxii would also like to thank Abhinav and Nivedita for being such wonderful friends to me. They always stayed by my side whenever I needed someone to talk to. Last but not the least, I would like to thank my Mom, my Dad and my girlfriend, Nitia for their continued support and encouragement for my work. They were patient with me during my frustrations and helped me stay calm and get through with all the problems that came my way. The love and the warmth they have given me cannot be expressed in words, but rather can only be felt. I truly am lucky to have these people, who I call my family, in my life xxiii DEDICATION To my mother, my girlfriend, my supervisor and to the people in my life who have cared for me and supported me throughout the span of my work and my life.1 CHAPTER 1: INTRODUCTION AND THESIS ORGANIZATION From the hand held sextant to GPS satellites orbiting 20,200 km above earth’s surface, the field of navigation has taken a significant leap due to technological advancement. Among many satellite systems used for the purpose of navigation, the most popular and widely used navigational tool used in modern times is known as GPS or the Global Positioning System and is owned and maintained by the government of the USA. In this large navigational sector, lies a segment with immense potential and of great importance, known as indoor positioning systems or IPS. It is also a well-established fact that even though GPS works very well outdoors, it doesn’t work well in indoor environments [1] due to severe signal attenuation and multipath effects. A. Angrisano et al. in [1], after performing a thorough performance analysis of the operation of GPS in outdoor, indoor and dense urban areas, confirmed the poor performance of GPS (having an error ranging from 10m to 30m) in indoor environments when compared to its performance outdoors. Much work has been done in the field of IPS and although there exist several techniques for positioning and location finding for indoor environments, they often suffer from performance issues or high cost. The use of W-LAN or WLAN for internet usage has largely replaced the use of physical and bulky equipment and wires, and has become an invaluable part of our lives [2]. But this technology also suffers from poor performance in accuracy and precision (in the range of 3m-10m as confirmed by Zhan et al.) when used for positioning and location finding applications [2] [3]. This is because WLAN has been designed for the purpose of high speed communication, not positioning. Solutions to this problem have also been developed by many researchers. 2 One solution is to integrate two or more systems to achieve higher accuracy and precision, the consequence of which is increased device complexity and higher power consumption [4]. One such promising solution that balances cost and high power consumption is to link the popular GPS navigational tool with widely used WLAN for internet service to bring forth a better and more sophisticated indoor positioning system. This is because GPS provides an accuracy of better than 3.5 meter [5] outdoors whereas WLAN can be used for indoor positioning without the need for widespread deployment of infrastructure. Although this sounds very promising, surprisingly no significant work has been done to date to integrate these two systems. 1.1 MOTIVATION With the rapid increase in industries and factories throughout the world, it has become of significant importance to keep track of personnel and critical components using wireless technology. In this thesis and in conjunction with a company in Vancouver, called Rx Networks Inc. that specializes in cloud based positioning, an efficient algorithm that facilitates the linking of GPS with WLAN technology for indoor and real time location finding applications has been developed. Although WLAN has the required infrastructure, the system does not currently provide accurate position estimates because its routers, otherwise called Access Points (AP), are not well defined within a map or grid system. In order for the AP(s) to be dynamically located and hence well defined in a map system, a GPS RF front-end or a GPS receiver can be attached to it via the AP’s USB port. A GPS RF front-end is the part of the GPS receiver that is responsible for acquiring the GPS signal and conditioning the signal for signal processing. But as stated earlier, GPS suffers from attenuation indoors and, hence, the solution is to install an AP with a GPS RF front-end in a place with clear view of the sky (near a window for example) in order to help other AP(s) attached 3 with GPS RF front-ends buried deep within the building (NLOS GPS receiver) to acquire the appropriate GPS satellites. By providing assistance data to the NLOS GPS receiver, an accuracy of 3 meter for the position estimate of the AP can be achieved. Also, assisting the NLOS GPS receiver with baseband information helps in reducing the Doppler and code phase search spaces. This drastically reduces the computational power requirement and saves time. But in order for this assistance data to be used accurately, it is essential that all the GPS receivers in the network be synchronized with each other to within 10 ns. 1.2 OBJECTIVE The proposed way to do this is to send a sinusoid from the LOS GPS receiver modulated with a GPS PRN code to the NLOS GPS receiver via the WLAN network. OFDM modulation (the modulation scheme used in WLAN) will be used for this signal transmission. After demodulation at the receiving end, the received signal will be correlated with the replica generated by the NLOS GPS receiver. The correlation process will identify the frequency mismatch between the front-ends as well as the chip sample delay between them, thus enabling the internal oscillators of the front-ends to be tuned accordingly. The objective of this research is to develop an algorithm that can do this task to an accuracy of 10 ns for a number of different wireless propagation channels. This will have a significant impact as this method can be used in other types of positioning as well. 1.3 THESIS ORGANIZATION In this thesis, all significant previous work in indoor positioning to date is outlined in Chapter 2. Chapter 2 also includes the fundamentals of GPS and WLAN along with indoor channel models and some important parameter that are required to understand the proposed solution. The proposed idea along with its limitations and the proposed solution is discussed in Chapter 3. All the 4 experiments conducted are described, and their results discussed in Chapter 4. Finally, this thesis is concluded with conclusions in Chapter 5 followed by experiment limitations and some ideas for future work. 5 CHAPTER 2: PREVIOUS WORK ON INDOOR POSITIONING, INDOOR CHANNEL MODELS AND SOME IMPORTANT PARAMETERS This chapter discuss some of the methods developed for indoor positioning. Various technologies that are used for indoor positioning include ultrasound, IR (Infra-Red), RFID (Radio Frequency Identification), WLAN (Wireless Local Area Network/WLAN), UWB (Ultra Wide Band), Bluetooth, sensor networks and vision and audio analysis [6] [3] [7]. Like most technologies, each of these methods for IPS has its own advantages and disadvantages compared to the others. Hence, in order to deliver a solution for indoor positioning that depends on the users’ need, engineers and researchers have had to come up with design parameter where the pivotal factor was the performance of the system versus its complexity [8]. According to [8], it has been shown that integrating two or more positioning methods with one another greatly improves the accuracy of the positioning solution but is not cost effective. Therefore, a great deal of investigation and research is required to come up with a solution that deliver accuracy and is cost-effective. These investigations include system level performance analysis and identifying both the strengths and system constraints of various methods in order to design the most effective IPS that meets user requirements. 2.1 IPS (INDOOR POSITIONING SYSTEM): AN OVERVIEW This section deals with the basic attributes of the methods and technologies used for IPS with their proper evaluation criteria. A comparison and analysis is also conducted in this chapter between different technologies for IPS in conjunction with client demands and their usage. IPS is a system that uses sensors or a network of devices to compute a position estimate of the point of interest. A wireless IPS would locate the point of interest or people inside an enclosed 6 space such as buildings, offices, hospitals, underground garage, etc. Based on the requirements of the user, IPS can provide various types of positioning solution, the most common of which is providing absolute position information with respect to a co-ordinate system or map of the intended area of coverage [6]. 2.2 DIFFERENT IPS TECHNOLOGIES, METHODS AND TECHNIQUES Due to advancements in technology, the methods and techniques behind IPS also evolved, but the rudimentary elements or the core technology behind IPS remain the same. An IPS uses some very basic techniques such as trilateration, triangulation, vision analysis fingerprinting and weighted centroid methods [9, 10] to estimate the position information of clients. Another more complex method for IPS is using inertial navigation systems (INS). Even though INS systems based on MEMS technology drastically reduced the size and cost of this system, using INS for IPS is not practical because it has been reported that even with a high-grade IMU, the accuracy of the system drifts by 1.5 km within 1 hour of device operation [11]. The errors obtained with an INS based on low-quality MEMS technology will be even worse. Further details on the basic positioning principles for various location finding and positioning techniques are given in the following sub-sections. 2.2.1 Trilateration This method is one the most basic forms of position/location finding and is the positioning principle for many location finding and estimation technologies [12]. This is a process of determining absolute or relative locations of points by measuring distances and then using the geometry of circles, spheres or triangles [12]. The positioning solution for a 2-D system is obtained in two stages. In the first stage, the distances between the point of interest and several known 7 reference points of known locations are measured using methods such as received signal strength (RSS) or time of arrival (TOA). In the second stage, spheres of radius equal to the measured distances are drawn centered at the reference points. The common point of intersection of the spheres gives the positioning solution of the point of interest. In Figure 2.1, the point of interest is the ‘red dot’ found at the common point of intersection of the three spheres (represented as circles) centered on the satellites A, B and C. This method is used by GPS. Figure 2.1. An Overview of Trilateration Technique. In the TOA ranging method, the receiver can compute the propagation time of the signal by differencing the time of transmission from the time of reception of the signal. By multiplying the computed difference with the speed of light (3 × 108 𝑚/𝑠), the receiver can then calculate the range between the transmitter and the receiver. For trilateration in indoor environments, the aforementioned TOA method is the most accurate as this method can resolve multipath effectively depending on the signal structure used. However, for effective use of this method, the internal clock of all receivers need to be precisely synchronized. This increases device complexity and cost and hence is difficult to implement. 8 In contrast to TOA, RSS is an easier method to implement and requires less complex circuitry. The RSS technique can be used in a number of ways (proximity detection, fingerprinting, etc.), but the ranging method using RSS is very straight forward and includes measuring the received power and the transmit power and then computing the distance between the transmitter and receiver using some propagation model. However, RSS may not give the same level of accuracy as TOA because of changes in the propagation environment, details of which can be found in 4.2.1. Figure 2.2. Trilateration of Point T [13]. Consider Figure 2.2. Solving the mathematical model for trilateration, one can estimate the position of the point of interest, T (shown in red) having co-ordinates, 𝑋𝑡, 𝑌𝑡 𝑎𝑛𝑑 𝑍𝑡. First, the equations of the three spheres with radii 𝑑1, 𝑑2 𝑎𝑛𝑑 𝑑3 and having centre co-ordinates 𝐵1, 𝐵2 𝑎𝑛𝑑 𝐵3 respectively are defined as 𝑑12 = 𝑋𝑡2 + 𝑌𝑡2 + 𝑍𝑡2. (1) 𝑑22 = (𝑋𝑡 − 𝑐) + 𝑌𝑡2 + 𝑍𝑡2. 𝑑32 = (𝑋𝑡 − 𝑎) + (𝑌𝑡 − 𝑏) + 𝑍𝑡2. Solving the equations in (1), the co-ordinates of T, (𝑋𝑡, 𝑌𝑡 𝑎𝑛𝑑 𝑍𝑡) can be found as 9 𝑋𝑡 = 𝑑12 − 𝑑22 + 𝑐22𝑐. (2) 𝑌𝑡 = 𝑑12 − 𝑑32 + (𝑋𝑡 − 𝑎)22𝑏+𝑏2−(𝑑12 − 𝑑22 + 𝑐2)28𝑏𝑐2. 𝑍𝑡 = √𝑑12 − 𝑋𝑡2 − 𝑌𝑡2. 2.2.2 Triangulation Triangulation is a location finding and position estimation technique that measures the angles from two or more fixed known reference points to the point of interest. The measured angle is known as angle of arrival (AOA). In contrast to RSS and TOA methods, the method of AOA can use a minimum of only two known fixed reference points to determine or estimate the location or position of the point of interest [6, 12] in 2-D. However, in triangulation, the effect of an error in the AOA significantly decreases the accuracy of the position estimate as the point of interest moves further away from the fixed reference points [12]. 2.2.3 Vision Analysis Perhaps the most sophisticated technique for location finding and position estimation involves vision analysis. Vision analysis uses a camera or a camera array to collect images of a scene or an environment. It then analyzes the image to determine the position of the point of interest with respect to other objects in the image having known location co-ordinates [3]. However, the slightest change in the environment, such as light levels, may affect the system’s positioning accuracy. In addition, the locations of known points in the environment must obviously be determined a-priori and stored in a database. 10 2.2.4 Fingerprinting Method The term fingerprinting is a criminal investigation term. In positioning, it involves an algorithm that first collects the features of a scene or an environment and then estimates the position or location of the point of interest by matching the collected information (RSS value, for example) at that point with a-priori data (previously measured RSS values at particular points in that scene). However, the drawbacks of using this method for positioning are the necessity of collecting the a-priori data, which can be labour intensive, the requirement of a large database to store the a-priori information, and the possibility that this data becomes obsolete when the environment changes. Hence, the complexity level of this technique is high making it expensive to implement. 2.2.5 Weighted Centroid Localization (WCL) Method In simple proximity detection, the user location is approximated as the position of a known reference object or sensor (an AP for example). This method usually uses a dense network of antennas or sensors having well-known positions. When the user is detected by more than one antenna, the user is considered to be collocated with the antenna that receives the strongest signal. However, depending on the density of the network, position errors can range from of 5 – 10 m [14]. Therefore, this method in its simplest form is no longer used for indoor positioning that requires accuracies better than 5 m. A sophisticated extension to proximity detection is the weighted centroid localization method. In WCL, a signal is sent by the user to be located, to a number of reference points of known location. The position of the user is estimated by averaging the location coordinates of all reference points that detect the user’s signal, where each reference point is weighted by the RSS 11 of the signal received at that reference point. Hence, reference points that are near the user will experience a higher RSS and, therefore, their coordinates will be more heavily weighted in the averaging process. The RSS value, however, may not always directly correspond to the distance between the user and the reference point. For example, although the user and reference point may in fact be relatively close to each other, the RSS value may be very low due to signal attenuation caused by major obstructions in the environment. 2.3 CATEGORIES OF INDOOR POSITIONING SYSTEMS Indoor positioning systems can be categorized into two main types, one being network based indoor positioning and the other being non-network based indoor positioning. A brief comparison between these two is given in the following subsection. 2.3.1 Network Based vs Non-Network Based IPS Depending on the type of system used by an IPS to obtain its positioning solution, it can be categorized as either a network based approach or a non-network based approach. In a network based system, an IPS uses an existing or a new network infrastructure to obtain its positioning solution. An example is a system that uses WLAN for its operation. In a non-network based system, the IPS uses its own network infrastructure that is designed and fabricated by the designer according to the need of the user for accuracy and precision. Examples of such systems are those using UWB, RFID tag system, etc. 2.4 EVALUATION CRITERIA FOR IPS According to [3, 6], there exist several evaluation criteria that must be considered when designing an IPS. In this section, some of those evaluation criteria are briefly discussed. 12 2.4.1 Cost The main cost of an IPS comes from the components used in its infrastructure, electronics used per user to obtain the positioning solution and the total system installation and its maintenance cost. As stated earlier, an existing system infrastructure such as WLAN would reduce cost in terms of deployment but will suffer from inaccuracy and precision. This is because WLAN was originally designed for high-speed communication, not positioning. Other costs should also be taken into consideration such as the initial cost of the device that would be used by a user, its maintenance, lifetime and durability. Complicated electronics on the user’s receiver that does position computations increase the cost. Hence, the cloud-based system used by Rx Networks Inc. [15] is a cost effective solution to positioning as the positioning solution is computed by their cloud server and fed to the user (as they are connected within the same network). This enables the user’s receiver to be simple and less complicated, reducing cost. 2.4.2 User Preference User preference is one of the most vital aspects when designing a good IPS system. This evaluation criteria ensures that the device is compact (small) and lightweight for the comfort of the user. The user device must also be wireless so that it is easily moved and has low power consumption. However, it should also have powerful computational capability to deliver accurate and precise real time positioning solutions. 2.4.3 System Performance ‘Accuracy’ and ‘precision’ are the two main parameter that determine the performance of any IPS. These evaluation criteria determine whether an IPS is appropriate for user requirements in real life scenarios and whether it can deliver according to expectations. Accuracy relates to how 13 close the estimated result is to the true position of the intended object and can be quantified with averaging the distance error. Precision relates to the difference between multiple estimates of the same point and can be quantified with standard deviation. The time an IPS takes to compute the position solution is called ‘delay’ and also plays an important role in system performance. The total number of objects that an IPS can locate with its infrastructure is another parameter that should be looked at when evaluating the system’s performance. 2.4.4 Privacy and Security Every indoor positioning system (except INS) uses some kind of network that is either personal or commercial to send and receive (For example – GSM, WLAN) location information. Hence, security and privacy is of paramount importance when evaluating any IPS. A good IPS will protect the confidentiality of the users’ information (including position) by securely transmitting all sensitive information. 2.5 EXISTING INDOOR POSITIONING SYSTEMS To date, several indoor positioning systems have been proposed or developed. In this section, some of the most common IPS are introduced along with their advantages and disadvantages. Later in this chapter, the performance of each system is discussed and compared to that of other systems. 2.5.1 Ultra-sound Positioning System The concept of navigating using ultra sound came from studying how dolphins and whales navigate underwater. Ultra-sound is based on echo-location, where the positioning principle is ranging using the TOA method. It was then used by boats to navigate in water which later inspired researchers to come up with a solution of using this technology for navigating in indoor environments. Some positioning examples using ultra-sound are detailed in [16]. Ultra-sound 14 technology is an inexpensive method for navigation but suffers from serious accuracy issues (often several meters) [16] because of multiple reflections at the receiver. 2.5.2 Infrared (IR) Positioning System This positioning technology uses proximity detection with IR signals to compute the position estimate of the point of interest. An IR positioning system is a non-network based technology and is expensive to implement. This positioning system requires line of sight communication between the transmitter and receiver, making this system limited to within a room. Also, to obtain the absolute position estimation of an object or point of interest, interference from strong light sources such sunlight must be avoided [17]. In IR positioning, the object that is being tracked includes a proprietary emitter that periodically transmits a unique IR beacon. Specialized IR receivers (placed at known locations) throughout the positioning environment detect the beacon and determine the approximate location of the object because of the known locations of the IR receivers. Hence, complex algorithms such as noise cancelling and optical filtering are required during signal processing to cancel out the interference effect from sunlight as well as bright florescent light sources [17]. This increases cost and complexity and is considered a disadvantage. 2.5.3 Indoor Positioning Using Radio Frequency (RF) As the name suggests, this IPS method is based on radio waves in the frequency range from 125 kHz to 5 GHz. Like all electromagnetic waves, radio waves can travel through objects such as walls as well as humans with minimal distortion at close range. This is an obvious advantage for use in indoor positioning systems. Another vital advantage of using a RF based IPS is that it can utilize existing infrastructure that is based on RF technology (such as WLAN). Discussed below 15 are IPS systems that utilize RF technology for positioning in indoor environments. A detailed report on all RF based positioning solutions can be found in [6]. 2.5.3.1 RFID (Radio Frequency Identification) RFID, or radio frequency identification, is widely used. Because of the system’s accuracy and convenience, it is used for several applications such as theft protection of automobiles and merchandise, managing traffic, collecting bridge tolls without stopping the vehicle, vehicle parking, etc. [6]. RFID is commonly used in complex indoor environments. RFID systems work by using small tags worn by the object or person of interest. Each tag is unique [14], enabling the system to uniquely identify the object or person of interest within the tracking system. RFID uses proximity detection as its positioning principle. Several RFID scanners are installed at known locations throughout the positioning environment and scan the RFID tags attached to the objects or persons of interest. Each tag has a unique electronic code. A centralized station stores the codes for each tag as soon as they are scanned. Because the centralized station knows the location of the scanners placed throughout the facility (pre-stored), it can display the location of each tag in a grid system as the location of the nearest scanner. For example, when a person wearing an RFID tag enters a room, the positioning system indicates the existence of the person as soon as the RFID tag is detected. In this scenario, having one RFID scanner per room would limit the accuracy of the system to the size of the room. Although RFID is advantageous from the user’s perspective, the technology is dependent on the positioning of the RFID scanners (a greater number of scanners would improve accuracy but would increase cost of deployment) and requires various components to be installed in its infrastructure before deployment. The system requires constant maintenance [14]. Also, when it 16 comes to applications requiring high levels of accuracy and precision, RFID is not an appropriate solution as it delivers positioning solutions with a typical error of 5 – 10 m [14]. No frequency or time synchronization is required by this method. 2.5.3.2 Ultra-Wideband (UWB) In an IPS using UWB technology, both the aforementioned AOA and TOA methods may be used for determining a position estimate. Among the many performance criteria of an IPS, one is how well the IPS can mitigate multipath effects. UWB technology can resolve multipath by using extremely large bandwidth signals or, in other words, using extremely short pulse-widths (period less than 1 ns), to filter reflected signals from the original. An UWB based IPS is able to have accuracies on the centimeter level because of its extremely short pulse width. One particular UWB system offers a coverage area of about 400 m2 with a level of accuracy of about 15 cm in 3-D space [6, 18]. In comparison to other IPS systems, UWB offers many advantages such as superior multi-path mitigation, almost no interference with other signals and high levels of penetration [6, 18]. Although an UWB based IPS system has many advantages, the technology requires highly precise clock synchronization making the receiver design very complex, costly and impractical to implement in real life scenarios when compared to other systems such as Rx Network’s cloud based positioning system using GPS and WLAN. 2.5.3.3 Bluetooth Bluetooth technology is also known as the IEEE 802.15.1 standard and is based on RF technology. This positioning technology is focused on trilateration using RSS values for distance computations. A network of Bluetooth devices can be constructed for the purpose of indoor positioning. The advantage of using Bluetooth technology in an IPS is that the system is cost 17 effective as no new infrastructure for information transportation is required. In addition, the system can use devices that already have Bluetooth integrated in them. However, the drawback of using this system is that an accuracy of 4 – 10 m is achievable only after a minimum delay of 20 seconds. Another disadvantage of the system is that the operational range is only a few meters and the data rate is low [19]. 2.5.3.4 Wireless Local Area Networking, WLAN An IPS based on WLAN technology can incorporate either proximity detection (not so common today due its large variance in position estimation), fingerprinting or the weighted centroid method using RSS values. WLAN, most commonly known as Wi-Fi is used almost everywhere in the world and hence, an IPS based on this technology is cost effective as no new infrastructure need be installed for its operation. For the scope of this thesis, more details on how WLAN is used for position estimation using fingerprinting and the weighted centroid method are given in section 2.7.1. Since these methods are based on RSS, there is no requirement to have a frequency or time synchronized routers or AP(s). 2.5.4 Sensor Networks This sort of IPS technology uses sensor networks laid out in predefined known locations within an indoor environment. These sensors are devices that are sensitive to light, temperature, pressure, sound, etc. and generate proportional data when there is a slight change in the physical or environmental properties into which they are placed. The point of interest can be located using measurements taken from these sensors. Hence, the positioning principle of this technology is either fingerprinting or trilateration based on the data obtained by the sensors. Although an IPS using sensors appears promising due to emerging sensor network technology, there is a limitation 18 in processing capability and battery power because of the miniature structure of these sensors and their low price. Hence, when compared to other IPS, this system has poor location estimation accuracy [6]. 2.5.5 Vision/Image Based Positioning System Vision-based positioning systems use fingerprinting for positioning. Images or scenes of a particular environment are stored in a database as a-priori data to be later used for positioning by matching an image/scene captured during the positioning process, to those stored in the database. The advantage of this technology is that no device need be carried by the user of the system. The same, inexpensive cameras used to take the multiple images of the scene/environment that are stored in a database may be used to take the range of the user which is then compared to the images stored in the database. However, this method is not good when the privacy of people is a matter of consideration. Moreover, this system is also not reliable in a dynamically changing environment since images taken in the process of positioning may no longer resemble those saved in the database. Also, when multiple target objects or people of interest move in the same environment, it becomes a challenge for the IPS system to do position estimation since an extensive amount of computation capability is required. Details on vision-based systems can be found in [20]. 2.5.6 Positioning System Using Sound The concept of an audible sound 3-D positioning system called ‘Beep’ is discussed in [21]. In ‘Beep’, trilateration based on TOA measured by sensors are used. It has been reported in [21] that during an experiment in an environment of dimensions 20 m × 9 m × 3 m, an accuracy of around 0.4 m was achieved 90% of the time. The advantage of using such a system is the re-usability of existing wireless devices that emit audible sounds, such as mobile phones, PDA(s), 19 etc. to compute position estimates. Conversely, systems such as these also suffer from external interference such as noise when deployed in indoor public places like shopping malls. Also, since transmitting sound for positioning computation is a continuous process, it can be an irritant to people in closed indoor environments. 2.6 GPS FOR INDOOR POSITIONING SYSTEM In this section, the positioning estimation technique for GPS will be very briefly discussed. Recent advancements in using GPS for IPS shall also be discussed together with possible solutions to mitigate the common problems of using GPS in indoor environments. 2.6.1 GPS System Structure The entire GPS system consists of three segments, which are: i) Space Segment: Consists of 32 uniquely identifiable satellites in 6 orbital planes, orbiting 20,200 km above the earth’s surface (medium earth orbit) with a spare satellite in each orbit. ii) Control Segment: Among the many components within this segment, the most vital component is the Master Control Unit or MCU. This unit operates the entire system and provides command and control functions. Some other important tasks of the MCU are maintaining GPS time, the satellite orbits and their ephemerides, and updating the navigational message which includes satellite health. iii) User Segment: This segment consists of the GPS receivers whose positions are being estimated. 20 2.6.2 GPS Position Estimation Technique This section details very briefly the basic position estimation technique of the GPS system. This positioning estimation technique is used for both outdoor and indoor environments. 2.6.2.1 GPS Signal Structure GPS uses spread-spectrum signalling and the technique of trilateration to derive its position estimates. The technology of GPS works on the basic principle of radio wave propagation at the speed of light, 𝑐 = 3 × 108 m/s. Each satellite has its own unique PRN (Pseudo Random Number) code consisting of 1023 chips in one code period. This helps a GPS receiver identify the specific satellite it is observing. The navigational message is encoded onto these PRN codes at 50 bits/sec. The resulting GPS signal bandwidth is about 2 MHz. The signal is then transmitted by the satellites being BPSK modulated on to the L1 carrier frequency of 1575.42 MHz (C/A code at 1.023 Mega chips/sec for civilian use and P code at 10.23 Mega chips/sec for military use) and the L2 frequency of 1227.60 MHz (P code for military use). 2.6.2.2 The Receiver A GPS receiver has a set of all 32 satellite codes in its memory and identifies which satellite it is observing by cross-correlating the 32 different satellite codes with the received signal. This is known as code phase acquisition. Once the correct satellites are identified, demodulation of the signal takes place and the navigation message is retrieved to acquire the satellite ephemerides followed by the computation of the positioning solution. The range measurement is based on the TOA method where the positioning principle is trilateration. The pseudo-range between the receiver and a particular satellite is given by 21 𝜌𝑘 = 𝑟𝑘 + 𝑐(𝛿𝑡𝑅 − 𝛿𝑡𝑆) + 𝐼𝑘 + 𝑇𝑘 + 𝜀𝑘 . (3) Here, 𝜌𝑘 is the pseudo-range, 𝑟𝑘 is the true geometric range for the 𝑘𝑡ℎ satellite to the user, 𝛿𝑡𝑅 𝑎𝑛𝑑 𝛿𝑡𝑆 are the receiver and satellite clock biases respectively, c is the speed of light, 𝐼𝑘 and 𝑇𝑘 are the ionosphere and troposphere delays respectively and 𝜀𝑘 is multipath, noise and other random measurement errors. 2.6.2.3 Mathematics for Code to Distance Conversion of GPS Signals Position estimates of the point of interest using GPS signals can be found either with the code phase measurement (C/A code or P-code) using a DLL (delay locked loop), with the carrier phase measurement using a PLL (phase locked loop) or by using both (requires an advanced GPS receiver). Code Phase Measurement using C/A Code The chip width of a single chip in the C/A code is given by C/A code (civil use): 𝜆 = 𝑐𝑓 = 3 𝑥 1081.023 𝑀𝑒𝑔𝑎 𝑐ℎ𝑖𝑝𝑠/𝑠𝑒𝑐 ~ 300 𝑚. (4) i.e. - each chip in the 1023 chip code corresponds to 300 m in distance. The period of a single chip in the C/A code is Period of a single chip = 11.023 𝑀𝑒𝑔𝑎 𝑐ℎ𝑖𝑝𝑠/𝑠𝑒𝑐= 977.5 ns. (5) Now, in order to acquire a positioning accuracy of 3 m (as per the requirement of Rx Networks Inc., the received C/A code and the receiver generated replica code must be aligned with each other to a maximum allowable difference of 10 ns. This is because if the samples of the received C/A code and the replica code are misaligned by 10 ns, it would correspond to 3 m in positioning inaccuracy. This relation can be shown by 22 300 𝑚100 = 3 m ~ 9.775 ns ~ 10 ns. (6) Here, one chip, which is equivalent to 300 m is divided into 100 samples, making each sample of the chip equivalent to 3 m. This means that the equivalent period of one chip is also divided 100 times, making the period of each sample to be approximately 10 ns. Code Phase Measurement using P Code The chip width of a single chip in the P code is given by P code (military use): 𝜆 = 𝑐𝑓 = 3 𝑥 10810.23 𝑀𝐻𝑧 ~ 30 m. (7) i.e. – Each chip width in 1014 chips corresponds to 30 m in length. Hence, using the P code for position estimation would result in higher accuracy than using the C/A code. Carrier Phase Measurement using L1 Frequency In the carrier phase measurement, the difference in the phase between the receiver generated replica carrier signal and the carrier received from the satellite at the instant of the measurement is one component of the range estimate [12]. The second is the exact number of whole cycles of the carrier (wavenumber) between the satellite and the receiver and is known as the integer ambiguity. The carrier phase method is more prone to errors as the integer ambiguity can be difficult to identify (as every cycle looks identical). Signal continuity is required for efficient position estimation using this method as a loss in signal continuity would cause the estimation process to start from the beginning. When measuring the distance using the L1 carrier frequency, the wavelength of the carrier, 𝜆 is Using L1 Carrier: 𝜆 = 𝑐𝑓 = 3 𝑥 1081575.42 𝑀𝐻𝑧 ~ 19 𝑐𝑚. (8) 23 Using L2 Carrier: 𝜆 = 𝑐𝑓 = 3 𝑥 1081227.60 𝑀𝐻𝑧 ~ 25 𝑐𝑚. (9) Assuming there are no clock bias and measurement errors, the carrier phase measurement in units of cycles can be written as 𝜙(𝑡) = 𝜙𝑢(𝑡) − 𝜙𝑠(𝑡 − 𝜏) + 𝑁, (10) where, 𝜙𝑢(𝑡) is the phase of the receiver generated replica signal, 𝜙𝑠(𝑡 − 𝜏) is the phase of the signal received from the satellite at time t, 𝜏 is the propagation delay and N is the integer ambiguity. Simplifying equation (10) and writing the phase as the product of frequency and time gives 𝜙(𝑡) = 𝑓 ∙ 𝜏 + 𝑁 (11) =𝑟(𝑡,𝑡−𝜏)𝜆+ 𝑁. Here, 𝑓 and 𝜆 are the carrier frequency and wavelength and 𝑟(𝑡, 𝑡 − 𝜏) is the geometric range between the satellite and the user position at time t. Including the clock bias and other measurement errors, equation (11) can be re-written as 𝜙 = 𝜆−1[𝑟 + 𝐼𝜙 + 𝑇𝜙] +𝑐𝜆(𝛿𝑡𝑢 − 𝛿𝑡𝑠) + 𝑁 + 𝜀𝜙. (12) 2.6.3 Problems Associated with IPS using GPS Technology As stated earlier, the performance of GPS in indoor environments is very poor due to the signal attenuation of the satellite signals. According to Hui et al. in [3], GPS signals are severely attenuated due to blockage and reflections from walls, roofs, etc. As a result, the signal received by the receiver becomes too weak to detect. In addition, when multiple copies of the signal reach the receiver due to reflections, the signals add either constructively or destructively due to phase differences and this can also cause further attenuation of the signals. This results in the receiver taking a longer time to identify the satellites in view. For weak signals, the integration time for 24 satellite acquisition needs to be extended to improve the signal-to-noise-ratio (SNR). This inevitably increases the satellite acquisition time with the square of the integration period [22]. In addition, if the integration time is extended beyond 20 ms (the bit length of the 50 bps navigation message), important information required by the receiver to successfully acquire satellite signals will be lost. Without this a-priori data (the satellite ephemerides included in the GPS almanac in the navigation message) and a coarse estimate of its own position, the receiver needs to search for all possible satellites, at all possible Doppler frequencies (up to ±5 kHz) and at all code phases. This can be a time intensive process. The search space can be considered two-dimensional, as shown in Figure 2.3, with the dimensions of Doppler frequency and code phase. Figure 2.3. 2-D Satellite Acquisition Search Space. The search space is divided into bins. Two samples per code chip are used while searching for the correct bin in the code phase dimension. Hence, there are 2046 (1023 x 2) samples, and because there are two channels (I and Q), the total number of samples is 4092. Therefore, the 25 number of bins in the code phase dimension is equal to 4092. The frequency width (𝑓𝑐) of a bin in the Doppler frequency dimension is given by 𝑓𝑐 = 23𝑁, (13) where, N is the integration time period. The total number of bins in the search space can then be found from 𝑇𝑜𝑡𝑎𝑙 𝑏𝑖𝑛𝑠 = 4092 × (5000+5000𝑓𝑐) . (14) For example, when searching for a single satellite, without a-priori data, and using a 10 ms integration time, the total search space would consist of 6,13,800 bins. Searching this number of bins for each satellite results in very long acquistion times and a very large time to first fix (TTFF). The GPS satellites have very accurate and expensive atomic clocks on board, which are highly synchronized with each other and controlled by the GPS control segment. However, hand held GPS receivers for civilian use do not contain high precision clocks and these tend to drift in time. This time drift leads to large discrepancies in the estimated position solution as the codes in the code phase do not line up correctly. As shown earlier in equation (6), even a mismatch of 1/100 of a chip width in the code phase would lead to position error of 3 m, for which clock synchronization in the order of 10 ns is critical for efficient GPS operation. 2.6.4 Current Techniques to Mitigate the Problems of GPS for IPS Extensive research has been done by the GPS community to mitigate the problems experienced by GPS in indoor environments. The most promising solution to the indoor GPS problem is A-GPS or Assisted GPS technology. 26 A-GPS was developed to enable mobile phone users to obtain their location when a clear view of GPS satellites is not available. Recently, however, this technology has been further enhanced to support users in indoor environments. The basic architecture of the system consists of a GPS reference receiver (typically placed on the roof of buildings) and a server. The GPS reference receiver has a clear view of the sky and hence a clear view of the potential satellites within view. The user’s GPS receiver is connected to the same server (via a network for example) as the GPS reference receiver. The GPS reference receiver provides, to the server, the satellite orbit parameter, ionosphereic corrections, an accurate estimate of the local time, satellite clock corrections, an initial position estimate, information of the visible satellites in the vicinity, Doppler frequencies and any relative code delay offsets. The server then communicates this information to any users in the area for use by their GPS receivers that may not have a clear view of the sky. Having this a-priori information about the Doppler frequencies and the relative code delay offsets substantially reduces the search space in the user’s GPS receiver which consequently decreases the satellite acquisition time. Thus, the advantages of an A-GPS system include very fast TTFF and a very precise and accurate position estimate (5 – 50 m) [23, 24, 25]. 27 Figure 2.4. An Overview of A-GPS System Structure. In Figure 2.4, the mobile user receives GPS assistance information from mobile base stations (BS) (GSM network) which in turn receive GPS information from an A-GPS server. It is obvious that the user must be close enough to the A-GPS server such that it views the same set of satellites as the server. Here, the A-GPS server sees the GPS satellites, generates the assistance data and then transmits the data to the user through the BS. One disadvantage of A-GPS is the privacy of the user. Since the user’s location information is being passed to the user using a network, the network operator has the full ability to view sensitive user information and hence cause a breach in privacy. In addition, for A-GPS, the user needs to be within 150 km of the GPS reference receiver for accuracy [22]. Although A-GPS technology is a possible choice for IPS, it is costly because an A-GPS server needs to be deployed and placed strategically so as to always have a clear view of the sky. Also, in indoor environments, a user may be buried deep within a building where even a partial 28 view of the satellite may not be available, resulting in no position solution at all, or inaccuracies in any position estimate obtained. 2.7 WLAN FOR INDOOR POSITIONING TECHNIQUE In this section, the use of WLAN for indoor positioning technique is discussed. This section also details the advantages and disadvantages of using WLAN as an IPS solution. 2.7.1 Position Estimation using WLAN The basic principles used by WLAN for IPS are simple proximity detection, location fingerprinting and the weighted centroid localization method (WCL) [26]. The approximate location of the user using simple proximity detection is the location of the AP from which the user receives the strongest signal. This can result in an inaccurate position estimate having large variance from the actual user position. Hence, proximity detection has been recently discarded [26]. Therefore, the two most common techniques used by WLAN positioning are the fingerprinting method using empirical data to estimate the approximate location of the target object and the weighted centroid localization method (WCL). The fingerprinting method and the WCL methods are concisely detailed below. In fingerprinting, a local radio map of all the AP(s) is constructed manually by measuring the RSS of each AP(s) at known locations, otherwise called– calibration points. Each calibration point is given a unique ID. This phase is known as the offline phase or calibration phase and the RSS values in dBm are measured using a mobile device. In the online or the positioning phase, the location of the user is approximated by comparing the measured RSS values obtained by the user’s mobile device at an unknown location with that of the stored radio map [26]. A position estimation 29 algorithm is used to compute and plot the user’s location on the map. In this method, the modeling of complex radio signal propagation can be avoided. The WCL method is similar to proximity detection with the exception that the locations of more than one AP are used to estimate the user’s position. In this method, a weight is given to the co-ordinates of each AP based on the merit of how strong their RSS value is for a user at a particular point in comparison to other AP(s) within the vicinity. Hence, in this technique a subset of AP(s) with the strongest RSS values, are selected and weighted. A position estimate of the user is then found by averaging the weighted co-ordinates of the AP(s) in that selected subset. However, for the weighted centroid localization method to work, accurate a-priori knowledge of the location of the AP(s) is required. In the first phase of the process to estimate user position, all APs send a beacon signal Bj with their position (𝑥𝑗 , 𝑦𝑗) to all the APs in the network. In the second phase, the user calculates an approximation (𝑥і́ , 𝑦і́ ) of their own position, using the known positions of all APs (𝑥𝑗 , 𝑦𝑗) [27]. The centroid localization equation is given by (𝑥і́ , 𝑦і́ ) =1𝑛∑ (𝑥𝑗 , 𝑦𝑗)𝑛𝑗=1 , (15) where, ‘𝑛’ is the total number of APs in the network. In the centroid method described by equation (15), all APs have the same weight, 1. However, in WCL, the generalized version of equation (15), variable weights 𝑤𝑖.𝑗 are given to each AP within the vicinity based on the RSS of each AP’s beacon as measured by the user. A larger RSS implies a shorter distance between the user and the AP, which in turn implies a larger weight should be used for that particular AP. Therefore, the WCL equation computes the user’s position (𝑥𝑖˝ , 𝑦𝑖˝) as 30 (𝑥𝑖˝ , 𝑦𝑖˝) =∑ 𝑤𝑖,𝑗 ∙𝑛𝑗=1 (𝑥𝑗 , 𝑦𝑗)∑ 𝑤𝑖,𝑗𝑛𝑖=1, (16) where 𝑤𝑖.𝑗 is the weight of the jth AP for the purpose of estimating the position of the ith user. 2.7.2 Advantages and Disadvantages of a WLAN based IPS The Fingerprinting Method: An advantage of this method is that the radio map is stored in a database and can be accessed in offline mode. No line of sight requirement is necessary and the accuracy of the system is approximately 4 – 10 m [26]. This is deemed to be very good when balanced against cost and robustness. Another major advantage of this system is that it is very cost effective as no new hardware is required to be deployed in to the network and no frequency or time synchronization between the access points are required. However, the main disadvantage of a WLAN based IPS using fingerprinting for positioning is its non-dynamic nature. Since the radio map of the WLAN AP is constructed using pre-measured RSS values at different points, any change in the signal propagation environment would heavily affect the RSS values used in its creation [26]. So, if the map is not updated periodically with current RSS values, inaccuracy in the position estimate obtained using this method will increase. WCL Method: The main advantage of WCL over fingerprinting is its non-requirement of a large database to store an offline map along with the RSS values at pre-determined positions. This reduces the cost even more as the position estimates are now determined by weighting the co-ordinates of each AP according to how close the user is to that particular AP. 31 One of the factors that affects the accuracy of WCL is the mapping of RSS to a weight. In a very cluttered environment (particularly when there is no LOS path between an AP and the user) the RSS may not accurately reflect the distance between the user and the AP. For example, consider an AP that is very close to the user, but the LOS path between the two is blocked. The RSS will be low, resulting in a small weight for this AP when in fact it is quite close to the user and should have a large weight. Hence, APs need to be deployed very strategically. Another factor affecting the performance of the WCL method is the number of APs used in the averaging calculation as well as their deployment density within the positioning environment. The most commonly used RSS to distance conversion equation is given by 𝑅𝑆𝑆 = −(10𝑞𝑙𝑜𝑔10𝑑 + 𝛼), (17) where, 𝛼 refers to the RSS at 1 m distance to a certain AP, 𝑞 is the indoor signal attenuation exponent (typically ranging from 2 to 4 for indoor environments) and 𝑑 is the distance between the object and the AP. The accuracy of the position estimate of the user is also dependent on how accurate the positions of the APs are known with respect to their true co-ordinates. AP positions must be determined manually by visiting each AP, measuring its location via some technique, and recording its co-ordinates in a database. However, in a dynamic environment where a new AP needs to be installed or moved, the process is repeated over and over again which can be cumbersome and would not be cost effective. Hence, automatically determining the true co-ordinates of APs in this is advantageous, as manually entering the location co-ordinates of new APs or APs that are moved would be tedious and costly in large indoor (like a warehouse) applications. 32 2.7.3 Recent Advancements in IPS using WLAN Method In recent years, there have been significant advancements in WLAN based IPS. In this section, some of the latest research on WLAN based IPS, mainly focusing on fingerprinting and the WCL method, is presented. In [28], a method known as distance-based trilateration is discussed. In this method, the co-ordinates of three known APs detected by the user’s device, are used to estimate the user’s position. The distance computation between the user and an AP is done by knowing the signal path-loss, PL expressed by 𝑃𝐿 = 𝑃𝐿1𝑚 + 10𝑙𝑜𝑔10(𝑑γ) + 𝑠, (18) where, 𝑃𝐿1𝑚 is the signal pathloss over a 1 m distance, γ is the environment path-loss exponent determined empirically, 𝑑 is the distance between the receiver and the AP and s is the standard deviation of the signal strength variability. PL can be found by subtracting the RSS from the transmitted signal strength. Then, by using equation (18), the distance 𝑑 in meter can be computed which is the radius of a sphere centred on the AP on which the user is proposed to be located. Solving equation (18) for radius 𝑑 for the three APs nearest to the user, results in three spheres centred on the APs. Using the trilateration equations (1 and 2), the location of the user can be estimated by solving for the intersection point of the three spheres. According to Solomon et al, it has been reported in [28] that for fingerprint position estimation with WLAN signals, an improvement is required to correctly match the RSS with the fingerprint database. Suggestions in [28] to enhance the performance of the system include using certain database algorithms for correlation such as K-nearest-neighbor (KNN). 33 In the KNN method, a fixed number of 𝑘 neighbors are used to calculate the position of the AP. The nearest 𝑘 neighbors are found by the smallest signal space distance (SSD) from the user to the AP. Here, SSD is the signal distance converted from the RSS value according to equation (17). The weighting factor, 𝑤𝑘 for each 𝑘 neighbor is found by 𝑤𝑘 =𝑠𝑘∑ 𝑠𝑗𝐾𝑚𝑎𝑥𝑗=1 (19) = 1𝑤𝑘∑ 1𝑤𝑗𝐾𝑚𝑎𝑥𝑗=1 =1𝑠𝑘∑ 1𝑠𝑗𝐾𝑚𝑎𝑥𝑗=1, and ?̂? = ∑ 𝑤𝑘𝑑𝑘𝐾𝑚𝑎𝑥𝑘=1 . Here, 𝑤𝑘 is the weighting factor of neighbor 𝑘, 𝑠𝑘 is the SSD of neighbor 𝑘, ?̂? is the KNN estimated distance and 𝑑𝑘 is the power spectral density (PSD) of neighbor 𝑘. Hence, only the nearest 𝑘 APs in the fingerprinting database are used to deduce the location co-ordinate of the user. In this method, an increase in the 𝑘 members would increase the accuracy in the estimated position but the main drawback is the increased complexity to deduce the 𝑘 members for each sample. 2.8 SUMMARY OF IPS Table 1 summarizes the various IPS methods discussed in terms of positioning principle, approximate indoor accuracy that can be achieved, requirement of LOS, multipath effect and the cost of deployment. Table 2 compares different IPS systems, the accuracy that can be achieved indoors, coverage area of the systems along with the power requirement and the cost of deployment. 34 Table 2.1. Comparison Between Different IPS Methods [29]. Method Type Accuracy (Indoor) LOS/NLOS Multipath Effect Cost ToA/TDoA Time Difference of Arrival High LOS Yes High Directional (AoA) Angle of Arrival Medium LOS Yes High Fingerprinting RSS High Both Yes Medium Dead Reckoning (INS) Acceleration or Velocity Low NLOS Yes Low Table 2.2. A Comparison Between Popular Positioning Systems Used for IPS [29]. System Accuracy Technique Coverage Power Req. Cost GPS 10 – 20 m ToA Poor Indoor Medium High WLAN 2 – 5 m ToA, TDoA, RSS, Fingerprinting, WCL Excellent (Building Level) High Low Infra-Red 1 – 2 m Proximity, ToA Good Low Medium Ultrasound 3 cm-1 m ToA, AoA Only Indoor Low High Bluetooth 2 – 5 m ToA, TDoA, RSS, Fingerprinting Only Indoor Low High RFID 1 – 2 m Proximity, ToA, TDoA, RSS Only Indoor Low Low 35 From the above two tables, it can be deduced that WLAN fulfills the requirement of having an excellent coverage area in indoor environments. But, as stated in section 2.7.2, the problems associated with using WLAN as an IPS are the requirements of having a costly and labour intense database (fingerprinting), or automatically finding the location of APs in a dynamic environment for position estimation using WCL. Since Rx Networks Inc. does indoor positioning with WLAN using the WCL method, the idea proposed to overcome the problem of automatically locating APs is to locate those APs with GPS by integrating a GPS RF front end into every AP. 2.9 CHANNEL MODELS AND IMPORTANT PARAMETERS The wireless radio channel imposes many challenges that need to be dealt with to ensure reliable high-speed communication. These channels are not only susceptible to noise, but are also susceptible to interference and other phenomena that change over time in unpredictable ways due to user movements and dynamic environments [30]. In this section, the different channel models that will be used in the simulations to follow, are discussed. The chapter gives an overview of all the channel models that may apply for an indoor positioning application. For comparison, the models discussed in this chapter are applicable to frequencies ranging from 2 GHz to 30 GHz. Here, all the transmitted and received signals are considered to be real signals because the modulators are built using oscillators that generate real sinusoids, although the channels are modeled using complex frequency response for analytical simplicity. As the channel introduces an amplitude and phase change of the signal, the modulated and the demodulated signals are represented as the real part of the complex expression, where the complex part is the phase change associated with each frequency. 36 2.9.1 Free-Space Path-loss Model (FSPL) According to the definition given in [30], free-space path loss in telecommunications is defined as the loss in signal strength of an electromagnetic wave having a line of sight path with the receiver after propagating through air, with no nearby obstacles to cause any reflection or diffraction. This channel model does not take into account any power loss due to hardware imperfections or the effects of transmitter or receiver antenna gains. FSPL is proportional to the square of the distance between the transmitter and the receiver as well as the square of the frequency of the radio signal [30]. The FSPL is given by FPSL = 10𝑙𝑜𝑔10 ((4𝜋𝑑𝜆)2), and replacing λ = 𝑐𝑓, equation (20) can be re-written as (20) FSPL (frequency) (dB) = 10𝑙𝑜𝑔10 ((4𝜋𝑑𝑓𝑐)2). (21) The ratio of received power (𝑃𝑟) to transmit power (𝑃𝑡) is 𝑃𝑟𝑃𝑡= [√𝐺𝑙𝜆4𝜋𝑑]2. (22) In the equations from (20 to 22), 𝑑 is the separation distance between the transmitter and the receiver, 𝜆 is the wavelength of the transmit frequency and 𝑐 is the speed of light. In equation (22), assuming that the product of transmit and the received antenna gain is 1 (omnidirectional antenna), then √𝐺𝑙 = 1. Thus, rearranging equation (22), the transmit power is given by 𝑃𝑡 = 𝑃𝑟 ⌊4𝜋𝑑√𝐺𝑙𝜆⌋2. (23) 37 Equations (20 - 23) are of particular importance because they help a designer to adjust the transmit power of a signal to maintain the required power at the receiver based on the free-space-path-loss model. 2.9.2 Empirical Path-loss Channel Model Often, indoor wireless communication systems are subjected to complex propagation environments which cannot be modeled as FSPL and, therefore, a number of targeted path-loss models have been developed over the decades to accurately predict the path loss of wireless signals inside buildings [30]. These models are based on empirical data measured over a given a distance in a particular frequency range for particular environments. However, since these models are used in general indoor environments, and as the application of these models is not restricted to the area or environment where the measurements on which they are based were taken, their accuracy becomes an issue. Nevertheless, these models are widely used in wireless systems for general performance analysis [30]. Among many such empirical path-loss models, the two models most relevant to the context of this thesis are the simplified path-loss model without and with shadow fading. 2.9.2.1 Simplified Path-Loss Model According to A. Goldsmith in [30], the complexity of wireless signal propagation makes it very difficult to obtain any single model that accurately characterizes path loss across a range of different signal propagation environments. Hence, it is recommended to use a simple model that can capture the characteristics of signal propagation without resorting to complicated path-loss models. The simplified path-loss model that is used the most in indoor environments for wireless communications is given by 38 𝑃𝑟 = 𝑃𝑡𝐾 [𝑑𝑜𝑑]γ . (24) This model is a function of distance and has a variable γ which is an empirical value known as the path-loss exponent (given in Table 2.3). K is a unitless constant that is dependent on the antenna characteristics and the average channel attenuation and is given by equation (26). The parameter 𝑑𝑜 is the reference distance for the antenna far field. Equation (24) can be written in terms of dB as 𝑃𝑟 (𝑑𝐵𝑚) = 𝑃𝑡 (𝑑𝐵𝑚) + 𝐾(𝑑𝐵𝑚) − 10γ𝑙𝑜𝑔10 [𝑑𝑑𝑜], (25) where, K is found by 𝐾 (𝑑𝐵) = 20𝑙𝑜𝑔10 (𝜆 4𝜋𝑑𝑜) . (26) Table 2.3 below gives typical empirically obtained values of the path-loss exponent γ [30]. Table 2.3. Typical Path-Loss Exponents [30]. Environment 𝛄 Range Office Building (same floor) 1.6-3.5 Office Building (multiple floors) 2-6 Retail Store 1.8-2.2 Factory 1.6-3.3 Home 3 2.9.2.2 Simplified Path-loss Model with Shadow Fading It is typical for the received strength of a wireless signal to undergo random variations due to blockage by objects in its path. These signal strength variations, called fading, are mainly caused 39 by reflecting surfaces and scattering objects in the nearby environment. Hence, a channel model that accounts for this fading in the received signal strength is required. The most common model for this additional attenuation is known as log-normal shadowing and has been confirmed empirically to accurately model the variations in the received signal power for indoor signal propagation environments [30]. In log-normal shadowing, the ratio of the transmit to received power is given by ψ = 𝑃𝑡𝑃𝑟 , (27) where, ψ is assumed to be random with log-normal distribution, which when measured in dB, is a random variable that follows a Gaussian distribution. Shadowing effects are normally incorporated into a simplified path-loss model by the addition of a Gaussian random variable with zero mean and standard deviation σ, N (0, σ), where σ is estimated empirically [30]. This gives rise to a more accurate path-loss model given by 𝑃𝑟𝑃𝑡 (𝑑𝐵) = 10𝑙𝑜𝑔10𝐾 − 10γ𝑙𝑜𝑔10𝑑𝑑𝑜− ψ𝑑𝐵. (28) For later simulations incorporating the simplified path-loss model with shadow fading, a value of 3.91 was used for ψ [30]. Figure 2.5. Received Signal Power vs Log of Distance for Shadow Fading and FSPL [30]. 40 In Figure 2.5, the received power in dBm is shown as a function of the log of distance. As can be seen from Figure 2.5, the received power due to path loss (dotted line) decreases linearly as the separation distance between the transmitter and the receiver increases. In the same plot, the effect on the received power due to shadowing is also shown (green curve), which is seen to have large variance at smaller separation distances than at larger separation distances. This is because shadow fading is a random variable and is very much dependent on the signal propagation environment rather than distance alone. 2.9.3 AWGN Channel The name AWGN (Additive White Gaussian Noise) is given to this channel model because the noise being added to the signal is white, which refers to uniform noise power distribution across the frequency band of the signal and normally distributed noise in the time domain with an average value of zero (Gaussian distribution). The AWGN channel model is the simplest wireless communication mathematical model that incorporates the addition of noise. A high level block diagram of this channel model is shown in Figure 2.6. Figure 2.6. High Level Block Diagram of an AWGN Channel. In Figure 2.6, an incoming signal, s(t) is added to noise n(t), resulting in the received signal given by 𝑟(𝑡) = 𝑠(𝑡) + 𝑛(𝑡). (29) 41 The sources of white/wideband noise are mainly natural such as thermal variations of atoms in conductors (thermal noise), black-body radiation from hot objects and from the earth, shot noise and noise from celestial objects like the sun [31]. The power spectral density (PSD) gives the power of a random signal as a function of frequency, whereas the variance is a measure of the average power of the signal. For white noise, the power is the same at all frequencies within that signal, and hence, the PSD of an AWGN is always constant and given as 𝑁𝑜 Watt/Hz, whereas the variance is given as 𝑁𝑜2. This is because half of the noise power, 𝑁𝑜, is for positive frequencies and the other half is for negative frequencies. Figure 2.7 illustrates this. Figure 2.7. Real Band-pass Noise PSD. Consequently, the SNR (Signal to Noise Ratio) of an AWGN channel is given by 𝑆𝑁𝑅 = 𝑃𝑟𝑁𝑜𝐵 (dB), (30) where 𝑃𝑟 is the power of the received signal and B is the bandwidth. White Gaussian noise is added to a signal to also represent the noise generated by the receiver electronic components, cables and thermal noise. 42 2.9.4 Rayleigh Fading Channel The sort of fading that is experienced by a signal due to a large number of reflectors present in an area is called Rayleigh Fading, and is typical in environments such as urban areas or an office block for indoor navigation. A Rayleigh propagation model is most suitable for situations where there exist multiple signal paths due to reflection, refraction and scattering from various objects within an environment, none of which is dominant. Because of this, the signal paths will vary in propagation path as well as propagation time, and hence would have an impact on the overall signal at the receiver. The delays associated with the multiple signal paths in a multipath fading channel change in an unpredictable manner, and hence a statistical approach is required to analyze and characterize the overall nature of the radio communication channel. Rayleigh Faded Signal at the Receiver When a signal undergoes Rayleigh fading, it is typical to assume that multiple copies of the transmitted signal arrive at the receiver via multiple propagation paths. Hence, the signal at the input to the receiver is a combination of all the signals that have reached the receiver via different paths. Because the signals have travelled different paths, each will have a phase associated with its particular path. These signals, at the receiver, will add up either destructively or constructively. If the received signals have the same phase (typically not the case), all the signals at the receiver will undergo constructive interference when they combine and increase the strength of the overall received signal. When the signals differ in phase (by 180° in the worst case) they combine destructively resulting in a decrease in the overall received signal strength. The phase of a signal is a function of its propagation path length between the transmitter and the receiver, which may change due to relative motion between them or if the position of the reflecting object changes. Hence, it should be noted that the phase of a signal is of particular interest as it strengthens or 43 weakens a received signal composed of a number of such signals. A weak signal is more prone to higher distortion and degradation of its contents. Rayleigh Fading Channel When there are a large number of signal paths present, the central limit theorem can be applied for modeling the time-variant impulse response of the channel as a complex-valued Gaussian random process [30]. A Rayleigh fading channel is formed when the impulse response of the channel is modeled as a zero-mean complex valued Gaussian process. It can be shown that for any two Gaussian random variables, X and Y with zero mean and equal variance 𝜎2 𝑍 = √𝑋2+𝑌2 (31) is Rayleigh distributed, where 𝑍2 is exponentially distributed [30]. Hence, with variance 𝜎2 for both the in-phase and the quadrature components of a signal, that signal as given by ȥ(𝑡) = |𝑟(𝑡)| = √𝑟𝐼2(𝑡)+𝑟𝑄2(𝑡) (32) is Rayleigh distributed, having the distribution given by 𝑝𝑧(ȥ) =2ȥ𝑃?̅?𝑒𝑥𝑝 [−ȥ2𝑃?̅?] (33) = ȥσ2𝑒𝑥𝑝 [−ȥ22σ2], ȥ ≥ 0. Here, 2σ2 is the average received power of the signal based on path-loss and shadowing. Hence, the power distribution is obtained by replacing ȥ2(𝑡) = |𝑟(𝑡)|2in equation (35) resulting in 44 𝑝𝑧2(𝑥) =1𝑃𝑟̅̅ ̅𝑒−𝑥/𝑃𝑟̅̅ ̅ =12σ2𝑒−𝑥/2σ2𝑥 ≥ 0. (34) From equation (36) it can be concluded that the received power of the signal has an exponential distribution with mean 2σ2. The equivalent low-pass signal for 𝑟(𝑡) is given by 𝑟𝐿𝑃(t) = 𝑟𝐼(t) + 𝑗𝑟𝑄(𝑡). (35) 2.9.5 Rician Fading Channel Rician fading is experienced by a signal when a fixed LOS component (specular) exists along with multipath components (scatter). In Rician fading, we define 𝑟𝐼 as a random variable with non-zero mean, 𝑠, that corresponds to the LOS component. We define 𝑟𝑄 as a zero mean random variable corresponding to the multipath components. Both random variables have equal variance σ2.The received signal is a superposition of the LOS component with a complex Gaussian component [30]. The signal envelope, in this case, is Rician distributed [30] as defined by 𝑝𝑧(ȥ) =ȥσ2𝑒𝑥𝑝 [−(ȥ2+𝑠2)2σ2] 𝐼0 (ȥ𝑠σ2) , ȥ ≥ 0. (36) Here, 2σ2 is the average power in the NLOS components and 𝑠2 is the power in the LOS component. 𝐼0 is the modified Bessel function of the zeroth order. Thus, the average received power in a signal undergoing Rician fading is given by 𝑃?̅? = ∫ ȥ2𝑝𝑧(ȥ)𝑑ȥ = 𝑠2 + 2∞0σ2. (37) Rician fading is characterized by a fading parameter known as the Rician k factor, (k) and is given by 𝑅𝑖𝑐𝑖𝑎𝑛 𝑘 𝑓𝑎𝑐𝑡𝑜𝑟, 𝑘 = 10𝑙𝑜𝑔10 (𝑠22σ2) 𝑖𝑛 𝑑𝐵. (38) 45 This k is a ratio of the power of the LOS component of the signal to the power in the NLOS components (the multipath components) expressed in dB. Rayleigh fading occurs when the value of k is 0 and there is no fading when the value of k is ∞. Hence, k is a measure of the severity of fading a signal is likely to undergo [30], where a lower k value equates to severe fading. To compute the power in a Rician faded signal (equation (39)), 𝑠 and σ can be found by 𝑠 = √𝑘(𝑘+1) (39) σ = √12×(𝑘+1) (40) 2.9.6 Pseudo-Random Number (PRN) Code A PRN code, or pseudo random number code, is a sequence of bits produced by a process that exhibits statistical randomness but actually generates a very deterministic casual process. GPS uses PRN codes (C/A and P(Y) codes) for range measurement purposes as well as the satellite identification process. PRN codes are unique due to their auto and cross correlation properties. For GPS, these PRN codes are generated using a series of maximal length LFSR (Linear Feedback Shift Registers) sequences. 2.9.6.1 Generating PRN Codes using LFSR The C/A codes and the P(Y) codes used by GPS are produced by a combination of two maximal length LFSR sequences, which are also called m-sequences. The LFSRs (Linear Feedback Shift Register) are used to quickly generate non-sequential list of numbers (PRN codes) on microcontrollers. The generation of a PRN sequence only requires a right-shift and an XOR (exclusive OR) operation. The GPS C/A code repeats itself after every 1023 chips, but for 46 simplicity here, the length of the codes is chosen to be 31 chips. An example of generating a 31 chip long PRN code using one sequence produced by 5 LFSRs is shown in Figure 2.8. Figure 2.8. A sequence of 5 LFSRs. Each two bit long register, un can hold 2 values, which are +1 and -1, and hence the maximum possible states are given by 25 − 1 = 31 possible states (except all ‘zero’ state). A register’s input bit is a linear function (XOR) of its previous state. If the feedback function that is used to produce the input is well chosen (i.e. – placement of the XOR logic gates), the LFSR can be used to produce random values (PRN code) with very long cycle (maximal length or m-sequence). Designing of a maximal length LFSR is governed by a generator polynomial that dictates where the XOR gates need to be placed in order to produce a long cycle of random numbers. It is easy to replace the ‘-1’ with ‘1’ and ‘+1’ with a ‘0’ and replace the multiplication process with the exclusive OR (XOR) operation: 0⊕ 0 = 0; 0⊕ 1 = 1; 1⊕ 0 = 1; 1⊕ 1 = 0 47 GPS uses the properties of PRN codes to generate Gold Codes that essentially become the C/A code for each distinctive GPS satellite [12]. For any code length, N=2n -1 (where n is the number of LFSRs), usually more than one m-sequence (maximal length sequence) exists. In most cases, two distinct m-sequences are used to generate an entire family of sequences that have both good auto and cross correlation properties, and these special sequences are called the Gold Codes or Gold Sequence. By carefully choosing two 1023 length m-sequences, it is possible to construct a family of 33 Gold codes, assigning a unique Gold code for each of the 32 GPS satellites. Figure 2.9 and Figure 2.10 show two examples of creating Gold Codes of 127 chips length, using a series of D-flip flops. The two generator polynomials for generating such Gold codes are g(x) = 1+x1+x7 and g(x) = 1+x3+x7 (shown respectively). Figure 2.9. 127 bit long Gold Code generated using the polynomial g(x) = 1+x1+x7 [32]. 48 Figure 2.10. 127 bit long Gold Code generated using the polynomial g(x) = 1+x3+x7 [32]. 2.9.7 Cross-Correlation and Auto-Correlation Function of Gold Codes The Gold codes are unique for their auto and cross correlation properties. Auto-correlation measures the similarity between a waveform and time shifted version of itself. Cross-correlation measures the similarity between the two different signals or corrupted version of the same signal. Cross-Correlation Cross-correlation is a process that is used to measure the similarity between two different signals or the similarity of a signal with a corrupted version of itself. In this technique, samples of the received signal are multiplied by samples of the receiver generated signal and added. In this thesis, since the two signals might have two different frequencies (due to clock bias), the method used to measure the similarity between these two signals is cross-correlation. A higher cross-correlation value, 𝑅(𝑡) indicates a greater degree of similarity between the two signals. The mathematical model for cross-correlation is 𝑅(𝑥,𝑦)(𝜏) = ∫ 𝑥(𝑡)𝑦(𝑡 − 𝜏)𝑑𝑡𝑇0, (41) 49 where, 𝑥(𝑡) is the received signal and 𝑦(𝑡) is the receiver generated signal to be cross-correlated with 𝑥(𝑡). For discrete valued signals, 𝑥[𝑖] and 𝑦[𝑖], the cross-correlation between 𝑥[𝑖] and 𝑦[𝑖] for a shift of k samples in 𝑦[𝑖] with respect to 𝑥[𝑖] is = ∑ 𝑥[𝑚] − 𝑦[𝑚 + 𝑘]𝑁−1𝑚=0 , (42) where N is the number of samples in each of [𝑖] and 𝑦[𝑖]. Auto-Correlation Function Auto correlation is cross correlation of a signal with itself. It is a measure of the similarity between two versions of the same signal as a function of the time lag between them. The time averaged auto-correlation function for the code of the kth satellite, x(k) (t) is given by 𝑅(𝑘)(𝜏) =1𝑇∫ 𝑥(𝑘)(𝑡)𝑥(𝑘)(𝑡 − 𝜏)𝑑𝑡𝑇0. (43) It is clear from the auto-correlation equation above that the incoming signal x(t) is multiplied with a time shifted replica of itself and the product is integrated. If 𝑥(𝑘)(𝑡) is similar to 𝑥(𝑘)(𝑡 − 𝜏), then 𝑅(𝑘)(𝜏) will be large. The equation above is also identified as the periodic or circular auto-correlation function. Figure 2.11 shows the auto-correlation property of a code. It should be noted that the peak appears at 0 code offset (i.e. 𝜏(𝑡𝑖𝑚𝑒 𝑠ℎ𝑖𝑓𝑡) = 0). 50 Figure 2.11. Auto-correlation of a PRN code with the Prompt Replica. Figure 2.12. Auto-correlation Function for N=31 Gold sequence. Figure 2.12 is the auto-correlation result of a 31 chips long PRN code. It is shown in Figure 2.12 that a time delay of 0 chips would result in a perfect auto-correlation peak. In Figure 2.12 where an auto-correlation of only 31 chips long PRN code is shown as an example, the distinct peak in the middle allows the GPS receiver to measure the code phase with high precision. The sharp unique peak helps to distinguish the GPS signal arriving directly from the satellite from any other signal that has travelled using other propagation paths such as via 51 reflections or scattering [12]. If the reflected signals come delayed by more than one sample relative to the direct signal, then secondary peaks are entirely distinguishable from the main correlation peak. This enables the receiver to differentiate the two peaks and avoid errors due to multipath. 2.9.8 Circular Shift A circular shift is the rearranging of entries in an ordered list of n elements either by moving the last element to the first position while shifting all the other entries to their next position in the bit sequence, or moving the first element to the last position while shifting all the other entries to the previous position in the bit sequence. For example, consider an array of 5 elements, i = {a, b, c, d, e}. A circular shift of ‘i’ by 1 element to the right would be, i = {e, a, b, c, d}. A circular shift of ‘i’ by 2 element to the right would be, i = {d, e, a, b, c}. In MATLAB®, this action is implemented by the function ‘circshift’. This is used in the experiments to shift the samples of the code in the code modulated signal to measure the sample delay between the received signal and the receiver generated replica code. 52 CHAPTER 3: FREQUENCY AND PHASE OFFSET ESTIMATION FOR IPS In this chapter, the proposed frequency and phase offset estimation technique that facilitates GPS-WLAN augmented indoor positioning is presented along with the fundamentals required to do indoor positioning using a GPS RF front-end. 3.1 GPS SATELLITE CONSTELLATION The 32 GPS satellites orbit 20,200 km above the earth and have been placed in 6 orbitals planes such that at least 4 satellites are visible to a receiver anywhere on the earth at all times [12]. Although typically up to 11 satellites are visible to a GPS receiver at all locations (except at receivers located at very high altitudes), a minimum of four satellites are required by a GPS receiver to estimate the user’s latitude, longitude, altitude and receiver clock offset at any given instance. A complete GPS satellite constellation consists of 24 satellites with 4 satellites in each of 6 different orbital planes. The orbital planes are inclined at 55o and may also contain a spare satellite. The satellites are constantly moving in their orbital planes at a speed of 14,000 km/h [33] relative to an observer on earth and take about 12 hours to complete one revolution around the earth. 3.2 IMPORTANCE OF SYNCHRONIZATION IN GPS TECHNOLOGY Each GPS satellite transmits a signal containing information regarding its location and its current time. This operation is synchronized amongst all GPS satellites so that these repeating signals are transmitted at the same instant. In order for a GPS receiver to calculate a PVT (Position, 53 Velocity and Time) solution, the receiver first needs to determine which GPS satellites are in view. For this, the GPS receiver needs to know three things: 1. The receiver’s local time. 2. An approximation of its own location. 3. The satellite orbital information (provided from the Almanac and the ephemeris data). Almanac data contains the orbital information of all satellites and each satellite broadcasts this information for every satellite in the sky. Ephemeris data is satellite specific and contains that particular satellite’s orbital information and where it will that be at any time throughout the day. A GPS receiver uses this Almanac data to determine which satellites will be in view in its local sky at the receiver’s local time. The Almanac and the ephemeris data is contained in each satellite’s navigation message (transmitted at 50 bits/sec) and must be decoded, once the signal acquisition phase is complete, to compute the PVT of the GPS receiver. Information contained in the Almanac is usually valid for 6 months whereas the ephemeris information is valid for only 4 hours [12]. All GPS satellites are in constant motion in their orbital planes at all times. This means that the Doppler frequency of each satellite is different (usually ±5 kHz) [12]. So, once the receiver knows which satellites are visible, it then tries to acquire each satellite’s signal by predicting the satellite’s Doppler frequency (which it can roughly estimate given it knows where each satellite is, from the Almanac, and roughly where the receiver itself is) and code phase. Given this information, the two dimensional Doppler frequency and code phase search space will be relatively small allowing the receiver to quickly acquire the satellites. For indoor operation, a GPS receiver buried deep within a building (NLOS GPS receiver) will have difficulty acquiring the correct satellites because it will receive weak satellite signals [3, 7, 34] and, therefore, will require longer integration time to successfully cross-correlate the 54 received satellite PRN codes with its pre-stored replica codes. The longer integration time means that the receiver can’t receive the 50 bits/sec navigation message and, therefore, does not receive the Almanac. As a result, the GPS receiver does not know which satellites are visible and must search for all satellites at all possible Doppler frequencies and all possible code phases. This searching takes an excessively long time. Assistance data can help by providing the NLOS GPS receiver with the knowledge of which satellites are in view along with their Doppler frequencies and code phases. This assistance data can be provided by another GPS receiver that is close by and has a clear view of the sky. This technique is called Assisted GPS (AGPS). 3.3 GPS-WLAN AUGMENTED IPS AND ITS CHALLENGES The idea of using GPS and WLAN for indoor positioning is to connect a GPS RF front-end to a WLAN AP via the access point’s USB port. The GPS RF front-end can be used to position the AP’s location which will be stored in a database. Measurements of WLAN signals transmitted by APs (i.e. received signal strength, RSS) can be used to locate a user, provided the AP positions are known. The continued presence of the GPS front-end allows the AP’s location to be updated if the AP is moved. However, if an AP augmented with a GPS front-end is buried deep within a building, the probability of it receiving a strong GPS satellite signals (at least -139 dBm) are very minimal as has been verified in [3]. Even if the RF front-end attached to that AP receives a very weak GPS satellite signal (-159 dBm), it will take long time to produce a position estimate because of the need to search a wide range of Doppler frequencies and code phase bins to find the appropriate satellites in its range. This can be mitigated by helping the AP buried deep in the building by sending it assistance data from an AP connected to a GPS RF front-end that has good view of the 55 satellites. This assisting AP, for instance, can be placed near a window so that it has a good view of the sky, and hence the GPS satellites. Assuming that the assisting AP is relatively close to the NLOS GPS receiver, one can conclude that the GPS front-ends connected to these AP’s will receive signals from the same GPS satellites (although the GPS receiver in distress will receive these signals at a much lower power level such as -180 dBm). In that case, the assisting AP will be able to provide assistance data to the NLOS GPS receiver for the appropriate satellites. This assistance data, consisting of Doppler frequencies and code phases for particular satellites, can be used by the GPS front-end in distress to significantly reduce the time to acquire the satellite signals. However, in order for all NLOS GPS receivers to use this assistance data, the internal clocks of all the GPS RF front-ends need to be synchronized with that of the assisting GPS RF front-end to within 10 ns. This is because the Doppler and the code phase of the detected satellite (provided in the assistance data) are not only functions of relative motion and distance between the satellite and the receiver, but are also affected by the low cost and moderately accurate oscillators used in GPS receivers. For instance, if the oscillator used in a GPS receiver has an uncertainty of 2 ppm, at the GPS L1 carrier frequency this uncertainty would be equal to approx. ± 3 kHz (1575.42 MHz × 2 µs). Therefore, even if the assisting GPS receiver sends the assistance data of the currently in view satellites (their Doppler and code phase information) to the NLOS GPS receiver (equipped with a 2 ppm oscillator), the search space would again end up being ± 3 kHz centered at the Doppler transferred from the assisting GPS receiver. This diminishes the advantage of assistance data and hence, the oscillators of both the receivers must be synchronized to within 10 ns (one hundredth of a chip ~ 3 m). 56 3.4 REASONS FOR CLOCK DRIFT AND FREQUENCY DIFFERENCE It is very common for every oscillator to undergo a certain amount of drift [35]. The causes of clock drift and frequency differences are diverse and range from a mismatch between the clocks or differences in the environments they are subjected to, to an interjection of charges from external radiation [35]. The four main causes of frequency drifts are given below, further details of which can be found in [36, 35]. i) Temperature and Bias induced. ii) Phase noise and period jitter. iii) Implementation and design problems; Start-up latency. iv) Instabilities in the oscillation amplitude due to voltage fluctuations. 3.5 PROPOSED TECHNIQUES FOR FREQUENCY OFFSET ESTIMATION In this section, the two proposed techniques for frequency offset estimation are presented. In the first method, a single sinusoidal signal (generated by the LOS GPS receiver’s oscillator) is sent over the WLAN communication link by OFDM modulation to the NLOS GPS receiver. After OFDM demodulation at the receiving AP, the received signal at the NLOS GPS receiver is cross correlated with a replica signal generated by the NLOS GPS receiver. This method is termed as Carrier Only Cross Correlation (COCC). In the second method, the same sinusoidal signal is first modulated by a PRN code and then sent to the NLOS GPS receiver for cross-correlation with a replica. This method is termed as the Code + Carrier Cross Correlation (CCCC). In both the methods, the frequency of the sinusoidal signal is 10.23 MHz. High level block diagrams illustrating the COCC and the CCCC algorithms are shown in Figure 3.1 and Figure 3.2, respectively. 57 Figure 3.1. High Level Block Diagram of COCC Method. Figure 3.2. High Level Block Diagram of CCCC Method. OFDM as used in a WLAN communication link typically has 52 subcarriers (depends on the network designer) per channel and occupies a bandwidth of 16.25 MHz per channel at 2.4 GHz. The CCCC and COCC algorithms are to be transmitted over the WLAN communication channel by OFDM modulation from the LOS GPS receiver to the NLOS GPS receiver on one of the subcarriers as data packets. Assuming perfect OFDM demodulation at SNR > 10 dB [37], the COCC and CCCC signals (being sent as data packets) are to be reconstructed and used for cross-58 correlation at the NLOS GPS receiver with its generated replica signal. Because OFDM demodulation is near perfect at SNR > 10 dB [37], WLAN communication is not implemented in the simulations conducted in this work. Thus, the carrier frequency to be used for the CCCC and COCC algorithms for all simulations will be 10.23 MHz, the frequency at which the oscillator of the GPS receiver runs. In the CCCC method, a sinusoidal signal modulated with a GPS PRN code is sent on one of the subcarriers of the WLAN communication link (OFDM modulation technique) to other AP(s) in the WLAN network. The PRN code of 1023 chips is sampled at 10 samples per chip before modulating the carrier. The PRN code frequency in the CCCC algorithm is adjusted to 1.023 mega chips/sec (same as the GPS C/A code). After OFDM demodulation at the receiving AP and acquiring the carrier modulated PRN code, the signal then passes on to the NLOS GPS receiver for cross-correlation with its generated replica signal. The replica signal is the receiver generated carrier modulated with a replica GPS PRN code. In the cross-correlation process of the CCCC algorithm, the frequency of the receiver generated carrier is varied from 10 Hz to 100 kHz from the nominal transmit frequency in 10 Hz step sizes. At each receiver generated carrier frequency, a new replica carrier with the modulated code is generated and cross-correlated with the received signal. At every frequency bin, each sample of the code is shifted by one to the right (circular shift) and cross-correlation performed at every shift. This is done until all the samples have undergone a shift at that particular frequency bin to estimate the code delay between the oscillators. The highest cross-correlation value for all shifts at every frequency bin would indicate the correct frequency and code phase of the transmitted signal. This frequency information can be used to synchronize the oscillator in the NLOS GPS receiver with that in the assisting GPS front-end. 59 The COCC method can also estimate frequency offset by sending a single carrier (without any PRN code modulated on it) over the WLAN communication link to the NLOS GPS receivers and performing the same set of operations. All algorithms are implemented in MATLAB® and are able to find the carrier phase offset between the received and replica signals by incorporating the mathematical equation given by cos 𝜃 =〈𝑥,𝑦〉|𝑥||𝑦|, (44) were, 𝑥 is the transmitted signal, 𝑦 is the received signal, 〈𝑥, 𝑦〉 is the dot product of 𝑥 and 𝑦, 𝜃 is the phase offset between the two signals 𝑥 and 𝑦, |𝑥||𝑦| are the modulus of the signals 𝑥 and 𝑦 respectively. The COCC and CCCC algorithms simulated to test whether these algorithms meet the required ±30 Hz frequency offset estimation accuracy. Both of these algorithms were also tested under different channel types that include AWGN, Rayleigh and Rician fading channels. Both the COCC and the CCCC algorithms were also simulated with the simplified path-loss model to find the optimum separation distance between the LOS GPS receiver and the NLOS GPS receiver. The results of these simulations, and their discussions are presented in Chapter 4. 60 CHAPTER 4: EXPERIMENTS, RESULTS AND DISCUSSION In this chapter, all the experiments conducted in this research are discussed along with the results obtained and their analysis. The experiments conducted are divided into two subsections: I. Carrier Only Cross-Correlation (COCC). II. Carrier + Code Cross-Correlation (CCCC). 4.1 COCC EXPERIMENTS, RESULTS AND DISCUSSION In this section, experiments conducted are based on sending a single carrier signal from the assisting GPS RF front end to the NLOS GPS receiver buried deep within the building for the purpose of estimating frequency offset via cross-correlation. The transmitter, channel and receiver were implemented in MATLAB® in order to facilitate the running of a number of simulations. Different channel models (AWGN only, simplified path-loss with shadowing, Rayleigh fading and Rician fading) were used in order to evaluate the performance of the cross-correlation process for frequency estimation in various propagation environments. The nominal transmit frequency of the carrier signal, 𝑓1 for all the simulations performed is 10.23 MHz with a sampling frequency, 𝑓𝑠 of 40.92 MHz, four times that of the nominal frequency. In all experiments, the transmit power was set to 0 dBm. 4.1.1 Experiment 1: Verification of Cross-correlation Process for Frequency Estimation. The purpose of this simulation was to check whether the concept of cross-correlation can perform frequency estimation in a completely noiseless channel with no path-loss, shadowing or phase offsets. In this experiment, a clock drift of 90150 Hz was added to the nominal transmit frequency of 10.23 MHz, resulting in a carrier signal transmit frequency of 10.320150 MHz. At 61 the receiver, frequency estimation is performed using cross-correlation of the received signal with a replica carrier signal generated inside the receiver. The receiver oscillator frequency is varied from 10.22 MHz to 10.35 MHz in 10 Hz steps. The maximum cross-correlation value for every frequency bin is recorded. The outcome of the cross-correlation operation is a distinct peak at the receiver oscillator frequency bin with the maximum cross-correlation. Cross-correlating the received signal with a replica signal of the same frequency will result in a cross-correlation coefficient of 1. Figure 4.1. Correlation at the Correct Frequency Bin Using the COCC Algorithm. Figure 4.1 shows the result of the cross-correlation process as the replica frequency was varied from 10.22 MHz to 10.35 MHz. The frequency steps were 10 Hz, so that when the first frequency bin is 10.22 MHz, the next frequency bins are at 10.220010 MHz, 10.220020 MHz and all the way up to 10.35 MHz. For this particular simulation, the transmit frequency was 10.320150 62 MHz, which resulted in a perfect match with the replica signal at the 10.320150 MHz frequency bin with the maximum cross-correlation coefficient of 1. From Figure 4.1, it can be seen that the cross-correlation process was successful in correctly estimating the transmit frequency at 10.320150 MHz. It should, however, be noted that this estimation was under the condition that the clock drift was fixed to 90150 Hz in a perfectly noiseless channel with no path loss or shadowing. It should also be noted that the correct frequency falls into one of the correct frequency bins as determined by the correct frequency step size and the first replica frequency value. This confirms that the concept of cross-correlation for the purpose of frequency estimation can work in a perfect, noiseless channel. The frequency step size was set at 10 Hz increments for the entire frequency range. Hence, the total number of frequency bins the receiver must search was 13000, each time storing the maximum value for the cross-correlation operation. The total time taken to perform this operation was 5 seconds in an Intel Core i7 processor (1.9 GHz) with 6 GB of RAM. 4.1.2 Experiment 2: Estimated Frequency Offset Error at Variable Clock Drifts. In this experiment, the nominal transmit frequency of 10.23 MHz was changed by 20 different clock drift values (in the range of 20 Hz to 100 kHz) to simulate oscillator clock drift bias. Cross-correlation was then performed for every frequency bin (as described in the previous experiment) to match the receiver oscillator frequency to that of the transmitter oscillator. The estimated frequency offset error was then found by subtracting the estimated receiver oscillator frequency from the transmit frequency of 𝑓1 + transmitter clock drift bias as follows Est. Frequency. Offset Error = Receiver. Est. Frequency − Transmit Frequency. (45) 63 Figure 4.2. Estimated Frequency Offset Error in a Noise-Less Channel Using the COCC Algorithm. Figure 4.2 shows the estimated frequency offset error for each of the 20 transmitter clock drifts. The bars plotted in Figure 4.2 shows the magnitude of the frequency offset error incurred for each clock drift values. From Figure 4.2, it should to be noted that when the clock drift value is any multiple of 10 Hz (the frequency increment bin size), the estimated frequency offset error incurred is zero, meaning that the frequency estimation was perfect. However, it should also be noted that when the clock drift is skewed towards the higher or lower side of the mean of the frequency bin value (in this case any clock drift value ending with 5), the frequency estimation results in a positive or negative error respectively. From this experiment, it can be seen that that the maximum cross-correlation value was found in the frequency bin closest to the nominal frequency of 10.23MHz + clock drift value. For example, the estimated frequency at the receiver for a clock drift value of -5-4-3-2-1012345617 548 1470 2689 3105 4800 5362 6580 7023 9076 10010 11724 12359 14820 15625 30472 52387 74598 87412 90760Estimated Frequency Offset Error (Hz)Set clock Drift (Hz)64 11724 Hz was found at 10241720 Hz, resulting in an estimated frequency offset error of 10241720 (receiver frequency) - 10241724 (transmit frequency) = - 4 Hz. Hence, from Figure 4.2, it can be concluded that the COCC algorithm for estimating frequency for a completely noiseless channel with no phase offset or shadowing has a maximum error of ±5 Hz with a 10 Hz frequency increment size. This error can obviously be further reduced by using 1 Hz as the frequency increment size, which in turn would increase the time required for the algorithm. 4.1.3 Experiment 3: Estimated Frequency Offset Error for an AWGN Channel as a Function of SNR. In this experiment, the clock drift bias was fixed at 90760 Hz and the signal passed through an AWGN channel with SNR ranging from -20 dB to 40 dB. This SNR range was chosen because the WLAN communication link becomes severely corrupted at any SNR below 10 dB [37]. The COCC algorithm is transmitted in the form of data over the WLAN communication link (OFDM modulation) to the NLOS GPS receivers, which later will be demodulated and then cross-correlated for frequency estimation. Even though the COCC algorithm can be used for frequency estimation at SNRs below 10 dB (as will be seen from Figure 4.3), the data in the WLAN communication link gets severely degraded at SNRs below 10 dB. Consequently, the performance of the COCC algorithm will suffer at these low SNR values. Since the generation of noise using the MATLAB® function ‘AWGN’ is a random process, 100 simulations were performed for each SNR value. Absolute value of the estimated frequency offset error for 100 simulations at each SNR was taken and their mean calculated for each SNR. 65 Figure 4.3. Estimated Frequency Offset Error in an AWGN Channel Using the COCC Algorithm. Figure 4.3 shows the estimated frequency offset error for each of the 24 different SNRs for an AWGN channel only. The bars plotted in Figure 4.3 represent the average of the estimated frequency offset error magnitudes of the 100 simulations conducted at each SNR. From Figure 4.3, it can clearly be seen that estimated frequency offset error was larger for lower SNR values. The greatest frequency estimation error of 751 Hz was incurred for an SNR of -20 dB whereas a 30 Hz error in frequency estimation was found at SNRs above -4 dB. Therefore, the COCC algorithm can perform accurate frequency estimation (within ±30 Hz error) at SNR values as low as -4 dB, which is 14 dB lower than what is required for reliable WLAN communication [37]. The mean and the standard deviation of the estimated frequency offset error at SNR ranging from -12 dB to 26 dB is 46 Hz and 73 Hz respectively. 0100200300400500600700800-20 -18 -16 -14 -12 -10 -8 -6 -4 -2 0 2 4 6 8 10 12 14 16 18 20 22 24 26Estimated Frequency offset Error (Hz)SNR (dB)Estimted Frequency offset error66 4.1.4 Experiment 4: SNR Variations for a Simplified Path-Loss Model with Shadow Fading and AWGN at Different Distances. In this experiment, several SNR values were calculated in MATLAB® at different distances by passing the carrier sinusoidal signal through a simplified path-loss model with shadowing. In this experiment, different distances were first set and then the corresponding SNRs were found. The transmit power of the signal was set to 0 dBm. Figure 4.4. SNR as a Function of Distance for Simplified Path-Loss Model with Shadowing for COCC Algorithm. In Figure 4.4, the SNRs found as a function of the distance between the assisting GPS RF front-end and the NLOS GPS receiver are shown. The transmit power was kept constant at 0 dBm and the distance between the assisting GPS RF front-end and the NLOS GPS receiver varied from 1 m to 100 m, calculating the SNR at every corresponding distance point. For example, the SNR calculated at a distance of 20 m is -1.139 dB. 67 In experiment 3, it was shown that that for accurate frequency estimation, the SNR is required to be at least -4 dB. From Figure 4.4, we see that a received SNR of approximately -4 dB is obtained for a separation distance of 25 m between the assisting GPS RF front-end and the NLOS GPS receiver. Hence, it can be concluded that for accurate frequency estimation and then synchronization, the assisting GPS RF front end can be set at a maximum of 25 m from the NLOS GPS receiver, provided that the channel is simplified path loss with shadow fading and AWGN noise only. 4.1.5 Experiment 5: Estimated Frequency Offset Error for a Rayleigh Fading Channel Model. A Rayleigh fading channel is perhaps the worst type of fading a signal is likely to encounter in an indoor environment [30]. In this experiment, the transmitter clock drift was set to 90760 Hz. The experiment was designed to simulate the synchronizing signal travelling through a Rayleigh fading channel with variable SNR (-20 dB to 26 dB) and to analyze the effect of the channel on the estimated frequency offset error. 0100020003000400050006000-20 -18 -16 -14 -12 -10 -8 -6 -4 -2 0 2 4 6 8 10 12 14 16 18 20 22 24 26Estimated Frequency Offset Error (Hz)SNR (dB)Est_freq_error68 Figure 4.5. Estimated Frequency Offset Error in a Rayleigh Fading Channel Using the COCC Algorithm. Figure 4.5 shows the estimated frequency offset error for each of the 24 different SNRs in a Rayleigh fading channel. The bars plotted in Figure 4.5 shows the magnitude of the frequency offset error incurred for each SNR. For the same SNR, the estimated frequency offset error incurred due to a Rayleigh fading channel (Figure 4.5) is found to be higher than that due to the AWGN channel (Figure 4.3) by up to 4.2 kHz. This confirms the fact that the signal is severely degraded when passing through a Rayleigh fading channel and this significantly impacts the performance of the COCC algorithm. It can also be concluded from Figure 4.5 that for a Rayleigh fading channel, the COCC algorithm has relatively accurate frequency estimation when the SNR is above 22 dB. The estimated frequency offset error at SNRs above 22 dB are within the range of ± 20 Hz. The average estimated frequency offset error and the standard deviation obtained from this experiment between SNRs ranging from -12 dB to 26 dB is 147 Hz and 183 Hz respectively. This experiment is of particular importance because in an indoor environment such as an office, a wireless signal is very likely to encounter a Rayleigh fading channel due to large number of reflectors and scatters. 4.1.6 Experiment 6: Estimated Frequency Offset Error for a Rician Channel Model. This experiment was designed to simulate the effect on the estimated frequency offset error when the synchronization signal propagates through a Rician channel. This simulation has the same parameter as the Rayleigh fading simulation with the exception that the Rician k factor ranges from 1 dB to 100 dB. In Figure 4.6, the maximum estimated frequency error is plotted at each k factor between 1 dB and 100 dB, for a fixed distance of 25 m. As described in section 2.9.5, the Rician k factor is a measure of how strong the LOS signal is compared to the NLOS signal. 69 Figure 4.6. Estimated Frequency Offset Error in Rician Channel (Fixed distance of 25 m) Using the COCC Algorithm. It is seen from Figure 4.6 that an increase in the Rician k factor value results in a decrease in the estimated frequency offset error. This is to be expected given the higher k value, the stronger the LOS component compared to the NLOS components. This results in a less degraded signal and, therefore, better performance of the frequency estimation algorithm. The mean and the standard deviation of the estimated frequency offset error in Figure 5.6 is 11.6364 Hz and 43.7486 Hz respectively. This means that the frequency offset error would only deviate by ± 43.7486 Hz from the mean error and is considered to be good in terms of a favourable frequency estimate. From the standard deviation calculated, it can be concluded that when the LOS component is about 5 times stronger than the NLOS component, the estimated frequency offset error is greatly reduced from ± 6.5 kHz to ± 50 Hz. Rician k factor (dB) 70 4.1.7 Experiment 7: Effect of Phase Offset on Estimated Frequency Offset Error. This experiment was designed to investigate the effect of signal phase offset on the COCC frequency estimation technique. In this experiment, the nominal transmitted sinusoidal frequency of 10.23 MHz was corrupted by a 90760 Hz clock drift bias, making the transmit frequency 10.320160 MHz. The transmit signal was then given an arbitrary phase offset of 30o with respect to the replica signal at the receiver. The signal, however, was transmitted through a completely noiseless channel without any path-loss or shadowing. Cross-correlation was performed at the receiver with 10 Hz frequency steps. Figure 4.7. Effect of Phase Offset on Frequency Estimation. Figure 4.7 shows the result of the cross-correlation process as the replica signal’s frequency was varied from 10.22 MHz to 10.35 MHz with 10 Hz frequency step size. 71 The top and the bottom graphs of Figure 4.7 shows the output of the cross-correlation operation at the receiver without and with phase offset estimation, respectively. During the simulation that resulted in the top graph, the COCC algorithm did not estimate the phase offset of the received signal before the cross-correlation was performed. This caused an inaccurate frequency estimation. However, during the second simulation that resulted in the bottom graph, equation (19) was incorporated into the COCC algorithm and the algorithm correctly estimated the phase offset of the received signal. After the phase offset detection, the phase of the replica signal was changed by the amount of phase offset found (in this case 30o) before the cross-correlation was performed. The result is a perfect frequency estimation as can be seen in the bottom graph of Figure 4.7. 4.1.8 Conclusion Table 4.1 summarizes the requirements for each channel type in order to achieve, with the COCC algorithm, the required frequency offset estimation of ±30 Hz. From the experiments 1 to 7 conducted in this section, it can be said that the COCC algorithm can, under certain conditions, perform frequency offset estimation over different channel types assuming the requirements in Table 4.1 are met. Knowledge of the frequency offset estimation can then be later used to synchronize the two oscillators. Table 4.1. COCC Channel Parameter to Achieve the Desired Frequency Offset Estimation within a Maximum Allowable Estimation Error of ±30 Hz. Channel Type Requirement to Achieve Frequency Offset Estimation AWGN SNR > -4 dB Simplified Path-Loss Distance ≤ 25 m Rayleigh SNR > 22 dB 72 Rician Rician k factor, 𝑘 ≥ 5 However, although the two oscillators may be synchronized in frequency, this does not guarantee that the code generators driven by these oscillators will be synchronized in code phase. Therefore, sending a single sinusoidal carrier to perform frequency estimation would only help the NLOS GPS receiver oscillator gain Doppler knowledge, not code phase knowledge. As mentioned in section 2.7.2, the receiver cross-correlates the received signal with the replica signal for every sample (by circularly shifting it) in each frequency bin, and stores the maximum value of the operation for each sample per frequency bin. Assisting the NLOS GPS receiver GPS RF front-end with only frequency synchronization will only reduce the number of frequencies that must be searched. The code phase search space would remain the same. Hence, the acquisition time for the NLOS GPS receiver would be long and the GPS positioning output may still have questionable accuracy. As a result, the performance of the CCCC algorithm, which involves modulating the carrier signal with a PRN code, is evaluated next. 4.2 CCCC BASED EXPERIMENTS, RESULTS AND DISCUSSION In this section, the experiments conducted and the results obtained are based on sending a PRN code modulated on a sinusoidal carrier for cross-correlation at the receiver with the receiver generated replica. The receiver generated replica is a carrier sinusoidal signal generated by the receiver’s local oscillator and modulated by the same PRN code. This PRN code is 1023 chips long having a chip rate of 1.023 Mega chips/sec. This happens to be the same as the GPS satellite codes. In a completely frequency and code-phase synchronized transmitter and receiver oscillator scenario, the cross-correlation of the signal received from the transmitter with the receiver generated replica would yield a higher value than if there is even a slight mismatch between the 73 two signals. The slightest mismatch may be a frequency difference of only 1 Hz, a code-phase shift of only 1 sample or a mismatch in the phase of the carrier signals. 4.2.1 Experiment 1: Cross-correlation for Signal Detection at Receiver This experiment was designed to check whether the receiver can detect the correct PRN code in the signal that is being transmitted. In this experiment, the PRN code for GPS satellite number 1 (chosen arbitrarily) was sent as data over the WLAN communication link to the receiver. At the receiver, a sequential search of each sample of the code for all the possible Doppler frequencies (±5 kHz) was performed. The receiver has a replica of the code for each of the 32 different GPS satellites. When the receiver does a serial search, it cross-correlates the received code with one replica code at a time. Hence, the receiver detects the correct PRN code by starting with the cross-correlation process with PRN code 1 and then moving through each code at all frequencies and ending with PRN code 32. At the correct frequency and at the correct shift for the correct PRN code, there will be a distinct peak, showing that the correct PRN code has been found. The amount of shift in the code phase needed to find this peak represents the propagation delay, which can be used later for range measurements. In this particular experiment, the assisting GPS RF front-end transmits the PRN code of satellite number 1 to the NLOS GPS receiver. When the NLOS GPS receiver performs a serial search with its pre-stored 32 different satellite PRN codes, it will find a distinct peak when cross-correlating the received code with the PRN code of satellite 1, at a particular shift and at the correct frequency. For any other PRN codes, even at the correct frequency, the NLOS GPS receiver may find a peak but its value would not be as large as that obtained for the PRN code of satellite number 1. In this experiment, the PRN code was transmitted on a carrier of frequency of 5 MHz (without 74 Doppler) and with a sampling frequency of 12 MHz. A Doppler frequency of 7 kHz and code shift of 920 chips were then added to the signal. Figure 4.8. Serial Search Acquisition of Satellite 1 PRN Code. 75 Figure 4.9. Serial Search Acquisition of Satellite 3 PRN Code. Figure 4.10. Serial Search Acquisition of Satellite 10 PRN Code. 76 Figure 4.8, Figure 4.9 and Figure 4.10 are 3D graphical representations of the GPS satellite acquisition process in terms of both Doppler frequencies and code phase. This simulation involves acquisition of the satellite 1 (SVN 1) PRN code. Figure 4.9 and Figure 4.10 correspond to the satellite 3 (SVN 3) PRN code and the satellite 10 (SVN 10) PRN code which are shown as examples (i.e. all other PRN codes, except SVN 1, would have similar results). In Figure 4.8 a distinct peak, which stands out from the rest, is seen at the correct frequency of 5.007 MHz (with Doppler) and at a code shift of 920 chips. The magnitude of the distinct peak seen in Figure 4.8 is 9358. This is significantly higher than the highest peak values of 8924 and 6413 seen in Figure 4.9 and Figure 4.10, respectively, in which cases the received code was cross-correlated with PRN 3 and 10 respectively. Therefore, we easily conclude that PRN 1 was transmitted rather than PRN 3 and 10. Given the ease with which the correct PRN can be detected via cross-correlation, one can conclude that it would be beneficial to transmit a code and carrier as opposed to a carrier only. However, the process of serial search acquisition can be time-intensive as all 32 different PRN codes need to be cross-correlated for every frequency bin. In order to reduce this acquisition time, the transmitter and receiver can be programmed to use only one PRN code since multiple access is not required. This approach drastically reduces the time required as now only one PRN code need be cross-correlated at the receiver rather than 32 PRN codes., Therefore, only one PRN code is required for the CCCC algorithm. 4.2.2 Experiment 2: Effect of Code Length on Estimated Frequency Offset Error The PRN code used in the CCCC algorithm resembles that of a GPS satellite PRN code where the oscillators of the transmitter and the receiver run at 10.23 MHz (ignoring the natural 77 clock drift). The 1023 chip long PRN code frequency is 1.023 Mega chips/sec such that each chip of the code occupies 10 cycles of the sinusoidal carrier (equivalent to the L1 GPS carrier). Since the idea is to transmit a GPS PRN code over the WLAN communication link to the NLOS GPS receiver, the sampling frequency of the code is initially set to 10 samples per code chip. The code is then BPSK modulated onto the sinusoidal waveform before transmission. This experiment is designed to analyze the effect of different code lengths (i.e. - period of the PRN code in chips) on the estimated frequency offset error while keeping the sampling frequency constant at 10 samples per code chip. Figure 4.11. Estimated Frequency Offset Error vs Code Sample Delay for Different Code Lengths for the CCCC Algorithm. Figure 4.11 is a graphical representation of the estimated frequency offset error incurred for a range of predefined code sample delays for different PRN code lengths. Six different 102030405060708090100Estimated Frequency Offset Error (Hz)Code Sample Delay (Samples)CL=1023 ChipsCL=1000 ChipsCL=900 ChipsCL=800 ChipsCL=700 ChipsCL=600 Chips78 PRN code lengths (CL in the legend of the figure) are tested in this simulation and their results plotted. From Figure 4.11, it can be seen that a change in the code length does not have a significant impact on the estimated frequency offset error that is incurred. The error in the frequency estimation is a maximum of 40 Hz when the code length is 600 chips and only 20 Hz when the code length is 1023 chips. Since a frequency offset error of 20 Hz is well within the requirement of 30 Hz, the small decrease in frequency offset error that results from using a code length greater than 1023 does not warrant the additional circuitry and cost associated with increased code lengths. Therefore, for the remaining experiments, the code length is kept constant at 1023 chips. 4.2.3 Experiment 3: Effect of Code Sampling Frequency on Estimated Frequency Offset Error In this experiment, the effect of different code sampling frequencies on the estimated frequency offset error is analyzed. Here, the code frequency is kept constant at 1.023 Mega chips/sec. 79 Figure 4.12. Estimated Frequency Offset Error vs Code Sample Delay for Different Code Sampling Frequencies for the CCCC Algorithm. Figure 4.12 is a graphical representation of the estimated frequency offset error incurred for a range of predefined code sample delays for different code sampling frequencies (FS in the figure). Five different code frequencies are tested in this simulation and their results plotted. From Figure 4.12, it is evident that an increase in the sampling frequency decreases the estimated frequency offset error obtained for the given code sample delays. The average estimated frequency offset error for each sampling frequency is given in Table 4.2. Table 4.2. Average Estimated Frequency Offset Error per Sampling Frequency. Sampling Frequency (MHz) Average Estimated Frequency Offset Error (Hz) 10 3.75 020406080100120Estimated Frequency Offset Error (Hz)Code Sample Delay (Samples)FS=10 MHzFS=8 MHzFS=6 MHzFS=5 MHzFS=4 MHz80 8 8.125 6 15 5 20.31 4 32.5 The results of Table 4.2 are expected because an increase in the sampling frequency means there are a greater number of samples per chip to cross-correlate. This increases the resolution of the cross-correlation process. However, a very high sampling frequency is impractical in real life scenarios. This is because the electronic components required are expensive and extensive computational power is required. A very large sampling frequency also increases the computation time. As a result, after discussing the results of this experiment with Rx Networks Inc., it was decided that a code sampling frequency of 10 MHz is sufficient in terms of balancing the cost, power requirement and computational time with the frequency estimation and synchronization performance. For the remaining experiments, the code length is kept constant at 1023 chips, the code frequency is kept constant at 1.023 Mega chips/sec, and the code sampling frequency is kept constant at 10 MHz. 4.2.4 Experiment 4: Estimated Frequency Offset Error in an AWGN Channel Only In this experiment, the clock drift bias was fixed at 90760 Hz and the signal passed through an AWGN channel with SNR ranging from -50 dB to 40 dB. This experiment is similar to experiment 3 of section 4.1.3. Figure 4.13 and Figure 4.14 show the estimated frequency offset error for each of the different SNRs in an AWGN channel only. Both figures are based on the same results but Figure 5.14 only shows results for SNR values greater than -30 dB. 81 Figure 4.13. Estimated Frequency Offset Error vs SNR (-40 dB to 40 dB) in an AWGN Channel Using the CCCC Algorithm. 82 Figure 4.14. Estimated Frequency Offset Error vs SNR (-30 dB to 40 dB) in an AWGN Channel Using the CCCC Algorithm. From Figure 4.13, it can be deduced that with the signal that consists of the code modulated on a carrier, the estimated frequency error is greatly reduced for lower SNR values as compared to the COCC algorithm. Figure 4.14 is the enlarged version of Figure 4.13, where the estimated frequency offset errors are shown from -30 dB SNR to 40 dB SNR. The average error in an AWGN channel between -20 dB and 40 dB SNR for the COCC and the CCCC algorithms are -4.84 Hz and 2.6 Hz respectively. The standard deviations of the estimated frequency error for the COCC and the CCCC algorithms are 250.3 Hz and 15.05 Hz respectively. Thus, it can be said that the CCCC algorithm achieves the required frequency estimation accuracy of ±30 Hz at an SNR 10 dB lower than that of the COCC algorithm. 4.2.5 Experiment 5: Estimated Frequency Offset Error for Different Distances in a Simplified Path-loss Model with Shadowing For the COCC algorithm (experiment 4 in section 4.1.4), it was found that with a simplified path-loss model with shadowing, the maximum separation distance between the transmitter and the receiver for adequate frequency offset estimation accuracy was 25 m. Here, the same experiment is performed with the CCCC algorithm and the frequency offset error incurred as a function of the distance between the transmitter and receiver is determined. In this experiment, 100 simulations per distance were conducted and the average estimated frequency offset error per distance is reported. 83 Figure 4.15. Estimated Frequency Offset Error vs Distance (1 m to 100 m) in a Simplified Path-Loss Model with Shadowing Using the CCCC Algorithm. Figure 4.16. Estimated Frequency Offset Error vs Distance (1 m to 60 m) in a Simplified Path-Loss Model with Shadowing Using the CCCC Algorithm. 84 In Figure 4.15, the estimated frequency offset errors, found as a function of the distance between the LOS GPS receiver and the NLOS GPS receiver, are shown. Figure 4.16 is the enlarged version of Figure 4.15 where the estimated frequency offset error for separation distances of 1 m to 60 m is highlighted. The transmit power was kept constant at 0 dBm. As an example, the average estimated frequency offset error for a distance of 40 m was found to be 58 Hz. With the CCCC algorithm, it can be seen from Figure 4.16 that the frequency offset error incurred at distances of 30 – 35 m is well within the acceptable range of ±30 Hz. Hence, it can be deduced from the figure above that with the CCCC algorithm, the transmitter and the receiver can be separated by a maximum distance of 35 m while ensuring reliable frequency estimation. 4.2.6 Experiment 6: Estimated Frequency Offset Error in a Rayleigh Fading Channel In this experiment, the transmit signal (code + carrier) is passed through a Rayleigh fading channel. The corresponding estimated frequency offset error and the code sample delay are analyzed and discussed. 85 Figure 4.17. Estimated Frequency Offset Error vs SNR (dB) in a Rayleigh Fading Channel Using the CCCC Algorithm. Figure 4.18. Estimated Frequency Offset Error vs SNR (-12 dB to 40 dB) in a Rayleigh Fading Channel Using the CCCC Algorithm. 86 Figure 4.19. Estimated Code Sample Delay Error vs SNR (dB) in a Rayleigh Fading Channel Using the CCCC Algorithm. Figure 4.17 and Figure 4.19 are graphical representations of the estimated frequency offset errors and the estimated code sample delay, respectively, that occurred for a given set of SNRs in a Rayleigh fading channel. Figure 4.18 is the enlarged version of Figure 4.17 which highlights the estimated frequency offset error incurred when the SNR is within the range of -12 dB to 40 dB. Analyzing Figure 4.18 , it can be said that even in a Rayleigh fading channel, the CCCC algorithm works better when compared to the previous COCC algorithm in terms of estimating the frequency offset error at low SNRs. For the experiment in section 4.1.5, a reliable frequency estimation of ±30 Hz was obtained with the COCC algorithm for a minimum SNR of 22 dB. With the CCCC algorithm, however, accurate frequency estimates within ±30 Hz are obtained at SNRs as low as -10 dB. It should be noted that the WLAN communication link deteriorates at SNRs below 10 dB, but the COCC algorithm in a Rayleigh fading channel require SNRs above 22 dB for reliable frequency estimation. Hence, the CCCC algorithm can still outperform the COCC algorithm as it can do a frequency estimation at SNRs as low as -10 dB. The estimated code sample delay can be analyzed by looking at Figure 4.19. The estimated code sample delay is seen to be in error at SNRs below -16 dB. At SNRs greater than -16 dB, this error becomes zero. It should be noted that the estimated frequency offset error at -16 dB SNR in a Rayleigh channel is 78.3 kHz. Hence, it can be deduced that when there is a significant error in the estimated frequency offset, an error in the estimated code sample delay can be expected as well. Also, from this experiment, the mean of the estimated frequency offset error obtained by the CCCC algorithm for SNRs between -12 dB and 40 dB is 2 Hz with a standard deviation of 14.708 Hz. This is considered 87 to be much better when compared to the mean of -53 Hz and standard deviation of 745.5 Hz obtained with the COCC algorithm in experiment 5 of section 4.1.5. From this experiment, it can be said that this CCCC algorithm works better than COCC algorithm in that reliable frequency estimation is obtained with an SNR that is 32 dB lower. 4.2.7 Experiment 7: Estimated Frequency Offset Error in a Rician Channel The transmit signal in this experiment is passed through a Rician fading channel. As in experiment 6 in section 4.1.6, the corresponding estimated frequency offset error and the associated code sample delay are presented and discussed. This experiment was performed using Rician k factors ranging from 0 dB to 10 dB. Recall that experiment 6 of section 4.1.6 demonstrated that a LOS component five times stronger than the NLOS component yields a reliable frequency offset estimation. It should be noted that the higher the Rician k factor, the stronger is the LOS signal. One hundred simulations for each k factors were conducted and the average estimated frequency offset error for each k factor plotted in Figure 5.20 below. Rician k factor (dB) 88 Figure 4.20. Estimated Frequency Offset Error vs Rician k factor in a Rician Channel Using the CCCC Algorithm. Unlike Figure 4.6, in which the Rician k factor ranged from 1 dB to 100 dB, in this experiment k was varied from 1 dB to only 10 dB. This is because it was confirmed from Figure 4.6 that the COCC algorithm can perform very accurate frequency estimation at a Rician k factor value of 5 dB. Hence, to analyze the performance of the CCCC algorithm, the Rician k factor in this test has been chosen to be within 1 dB to 10 dB. Although the Rician k factor is a variable dependent on the indoor environment, it has been confirmed empirically in [38] that this Rician k factor is within the range of 2-10 in a typical indoor environment such as an office. From Figure 4.20, it can be seen that a 𝑘 value greater than or equal to 4 results in zero Hz error in the estimated frequency offset. This also demonstrates the superiority of the CCCC algorithm over the COCC algorithm given that a minimum 𝑘 value of 5 dB was required by the COCC algorithm to achieve zero Hz frequency offset estimation error. Note that the estimated frequency offset error in Figure 4.20 for 𝑘 = 3 𝑑𝐵 is only 10 Hz and for 𝑘 = 2 𝑑𝐵, it is 20 Hz, both within the required accuracy of ±30 Hz. Consequently, the CCCC algorithm performs reliably even in propagation environments where the LOS component is very weak. 4.2.8 Conclusion The major findings of the CCCC algorithm experiments are summarized in Table 4.3 and Table 4.4. Table 4.3 shows the parameter of the PRN code that result in a good balance between frequency offset estimation performance and complexity, cost, and computational intensity. Table 4.4 shows the requirements to achieve a frequency estimation offset error no bigger than ±30 Hz by the CCCC algorithm over each of the channel types tested. 89 Table 4.3. PRN Code Parameter for the CCCC Algorithm. PRN Parameter Requirement to Achieve Maximum Frequency Offset Estimation within ±30 Hz PRN Code Length 1023 Chips PRN Chip Rate 1.023 Mega chips/sec PRN Code Sampling Frequency 10 MHz Table 4.4. CCCC Channel Parameter to Achieve the Desired Frequency Offset Estimation within a Maximum Allowable Estimation Error of ±30 Hz. Channel Type and PRN Parameter Requirement to Achieve Frequency Offset Estimation AWGN SNR > -14 dB Simplified Path-Loss Distance ≤ 35 m Rayleigh SNR > -10 dB Rician Rician k factor, 𝑘 ≥ 4 In conclusion, by comparing Table 4.4 with Table 4.1, it can be concluded that the CCCC algorithm outperforms the COCC algorithm for frequency estimation. In addition, the CCCC algorithm is advantageous as it incorporates a PRN code (whose parameter are given in Table 4.3) which can be used for range measurements. Provided the parameter in are met, the CCCC algorithm is able to estimate frequency offset well within the range of ±30 Hz, and perform code sample delay estimation for every channel type. Thus, this algorithm would enable a GPS RF front-end with LOS view of GPS satellites to be synchronized with GPS RF front-ends buried deep within a building. Consequently, NLOS GPS receivers buried deep within a building will be able 90 to effectively use the assistance data provided by a LOS GPS receiver to quickly acquire GPS satellite signals and, therefore, accurately determine a position for the AP to which it is attached. 91 CHAPTER 5: CONCLUSIONS AND FUTURE WORK 5.1 CONCLUSIONS In this thesis, two new algorithms to estimate the frequency offset estimation between two or more GPS RF front ends have been proposed, simulated and analyzed. The two algorithms are called Carrier Only Cross Correlation (COCC) and Carrier + Code Cross Correlation (CCCC). In the COCC algorithm, a single sinusoidal carrier frequency was sent at 10.23 MHz + clock bias from the LOS GPS receiver and cross-correlated with a replica signal generated at the NLOS GPS receiver. Frequency estimation within ±30 Hz of the transmit frequency of the LOS GPS receiver was achieved at SNR > 4 dB in an AWGN channel and at SNR > 22 dB in a Rayleigh fading channel at a maximum separation distance of 25 m. In an AWGN channel, the estimated frequency offset error was reduced to zero at SNRs greater than 10 dB (the SNR below which Wi-Fi signals become severely degraded) and at SNRs above 30 dB in a Rayleigh fading channel. It was also found that for the COCC algorithm in a Rician fading channel, the LOS component needs to be at least 5 times stronger than the NLOS components to achieve the desired frequency offset estimation accuracy of ±30 Hz of the nominal transmit frequency. The COCC algorithm is best suited for applications where only frequency estimation and synchronization are required. The CCCC algorithm includes transmitting, over a WLAN link, a sinusoidal radio frequency signal at 10.23 MHz that is modulated by a GPS PRN code of 1.023 Mega chips/sec. This PRN code is sampled at 10 MHz and, at the receiver, this code-modulated signal is cross-correlated with a receiver generated replica signal. From the experimental results and their analysis, it can be concluded that the CCCC algorithm will perform the frequency offset estimation to the required accuracy of ±30 Hz. From the experiments in Chapter 4 section 4.2.2, it is 92 concluded that the optimum code length of the PRN code is 1023, as a shorter or a longer code length would not have any significant improvement in the estimated frequency offset error. It was also seen that increasing the number of samples enhances the performance and hence, a sampling frequency of 10 MHz was chosen. A sampling frequency greater than 10 MHz would increase the complexity and cost of the method whereas a lower sampling frequency would deteriorate the performance of the CCCC algorithm. It has been further shown in the experiments that the CCCC algorithm is able to perform frequency offset estimation with a margin of error of ±30 Hz in environments with no line of sight between the transmitter and the receiver, high multipath effects, and with SNRs as low as -10 dB. It has also been shown that the algorithm is distance dependent, where an optimal distance of 30 – 35 m apart (transmitter and receiver) was found at transmit power of 0 dBm. When the CCCC algorithm is simulated with a Rician fading channel, it was found that in order to obtain an estimated frequency offset accuracy within ±30 Hz, the LOS component needs to be 4 times stronger than the NLOS component. Hence, in conclusion and in comparison to the COCC technique, it can be said that the CCCC achieves the required frequency estimation accuracy of ±30 Hz at an SNR 10 dB lower than that of the COCC algorithm in an AWGN channel and, 32 dB lower in a Raleigh fading channel. The CCCC algorithm also demonstrates a 10 m improvement in the separation distance (now the separation distance can be 30 – 35 m) and a 1 dB improvement in a Rician fading channel. The added advantage of CCCC over COCC is that the PRN code used to modulate the carrier signal can also be used for range measurements. 93 5.2 LIMITATIONS AND FUTURE WORK In this thesis, the main limitation was the lack of real data collected in the field. In this work, only simulated data for the COCC and CCCC algorithms was used for experimental purposes. The proposed algorithms were not implemented in actual electronic devices and hence, the results obtained are based on theory. Also, since the experiments were all simulated in software, the parameter for the channel propagation models were all constructed based on empirically obtained data from other researchers doing experiments on indoor channel propagation environments. It should be noted that the propagation channel model is highly variable and very much dependent on the environment. Hence, in this work, the channel parameter were kept as close as possible to those encountered in a real life environment such as a busy office. However, the performance of these proposed algorithms may significantly change in environments different than those simulated here. Also, for this work both algorithms (COCC and CCCC) were simulated on an Intel Corei7 processor at 1.9 GHz and with 6 GB of RAM. However, for an IPS in a real life scenario and being used in real time, the micro-processor in the GPS receiver as well as the AP will likely have limited processing capability which will influence the algorithms’ performance. Therefore, a thorough and detailed analysis of the computational requirements of the proposed algorithms should be conducted and analyzed. The limited computational capability of micro-processors may limit the usability of the proposed algorithms for indoor positioning because the micro-processors may not be able to handle the computational complexity of the proposed algorithms. Hence, future work for the CCCC algorithm in particular is to practically implement the algorithm in real life scenarios and obtain experimental data to determine the algorithm’s actual performance. 94 REFERENCES [1] G. A. Angrisano and C. S. Gaglione, Performance assessment of GPS/GLONASS single point, Akadémiai Kiadó, Budapest, Hungary 2013: Springer, 15th January, 2013. [2] J. L. Zhan and Xingqun, "Characterization of Smart Phone Received Signal Strength Indication for WLAN Indoor Positioning Accuracy Improvement," Journal of Networks, vol. 9, no. 3, pp. 739-746, 2014. [3] H. Liu, H. Darabi, P. Banerjee and J. Liu, "Survery of Wireless Indoor Positioning Techniques and Systems," IEEE Transactions on Systems, MAN and Cybernetics-Part C: Applications and Reviews, vol. 37, no. 6, pp. 1067-1079, 2007. [4] K. Law, M. Tan and C. Look, "GPS and UWB Integration for Indoor Positioning," in International Conference on Information, Communications and Signal Processing, 2007. [5] "GPS.gov," Official U.S Government information about the GPS., September 2014. [Online]. Available: www.gps.gov. [6] Y. Gu, A. Lo and I. Niemegeers, "A Survey of Indoor Positioning Service for Wireless Personal Networks," IEEE, vol. 11, no. 1, pp. 13-32, 2009. [7] R. Mautz, "Overview of current indoor positioning systems," Geodezija ir Kartografija, vol. 35, no. 1, pp. 18-22, 2009. 95 [8] A. C. Patterson, R. R. Muntz and M. C. Pancake, "Challenges in location-aware computing," IEEE Pervasive Computing, vol. 2, no. 2, pp. 80-89, 2003. [9] G. Borriello and J. Hightower, "Location sensing techniques," Technical Report UW CSE 2001-07-30, Department of Computer Science, Seattle, USA, 2001. [10] P. Krishnamurthy and K. Kaemarungsi, "Properties of indoor received signal strength for WLAN location fingerprinting," in International Conference on Mobile and Ubiquitous Systems: Networking and Services, 2004. [11] P. D. Groves, Principles of GNSS, Inertial, and Multisensor Integrated Navigation Systems, Boston: Artech House, 2008. [12] P. Misra and P. Enge, Global Positioning System: Signals, Measurements, and Performance (Revised Second Edition), Ganga-Jamuna Press, December 1, 2010. [13] Y. Charlon, N. Fourty and E. Campo, "A Telemetry System Embedded in Clothes for Indoor Localization and Elderly Health Monitoring," MDPI: Sensors, vol. 13, no. 9, 2013. [14] L. M. Ni, Y. Liu, Y. C. Lau and A. P. Patil, "Landmarc: Indoor location sensing using active RFID," IEEE International Conference on Pervasive Computing and Communications, vol. 10, no. 6, pp. 701-710, November 2004. [15] "XYBrid Cloud," Rx Networks Inc., [Online]. Available: http://rxnetworks.com/indoor-solutions/xybrid-cloud/. [16] Y. Fukuju, M. Minami, H. Morikawa and T. Aoyama, "DOLPHIN: An Autonomous Indoor Positioning System," in IEEE Workshop on Software Technologies for Future, May 2003. 96 [17] R. Casas, D. Cuartielles, Á. Marco, H. J. Gracia and J. L. Falcó, "Hidden Issues in Deploying an Idoor Location System," IEEE: Pervasive Computing, vol. 6, no. 2, pp. 62-69, April-June, 2007. [18] M. S. Islam, "Indoor Positioning through Integration of Optical Angles of Arrival with an Inertial Measurement Unit," The University of British Columbia, Okanagan, Kelowna, September 2012. [19] J.-S. Lee, Y.-W. Su and C.-C. Shen, "A Comparative Study of Wireless Protocols: Bluetooth, UWB, ZigBee and Wi-Fi," in The 33rd Annual Conference of the IEEE Industrial Electronics Society (IECON), Taipei, Taiwan, Nov 5-8, 2007. [20] Krumm, John; Harris, Steve; Meyers, Brian; Brumitt, Barry; Hale, Michael; Shafer, Steve;, "Multi-Camera Multi-Person Tracking for Easy Living," in 3rd IEEE Intl Workshop Visual Surveillance, 2000. [21] A. Madhavapeddy, D. Scott and R. Sharp, "Context-aware computing with sound," in 5th International Conference on Ubiquitous Computing, Oct 2003. [22] G. Dedes and A. G. Dempster, "Indoor GPS Positioning," in Proceedings of the IEEE Semiannual Vehicular Technology Conference, 2005. [23] D. Rubino, "GPS vs. aGPS: A Quick Tutorial," 2009. [Online]. Available: http://www.windowscentral.com/gps-vs-agps-quick-tutorial. [24] "Radio-Electronics," 2009. [Online]. Available: http://www.radio-electronics.com/info/cellulartelecomms/location_services/assisted_gps.php. 97 [25] "Brew Developers, Qualcomm Technologies, Inc," Qualcomm Technologies, Inc, 2011-2015. [Online]. Available: https://developer.brewmp.com/resources/tech-guides/position-determination-technology-guide/position-determination-concepts. [26] G. Jekabsons, V. Kairish and V. Zuravlyov, "An Analysis of Wi-Fi Based Indoor Positioning Accuracy," Scientific Journal of Riga Technical University, vol. 47, pp. 131-137, 2011. [27] S. S., K. Herrmann, K. Rothermel, J. Blumenthal and D. Timmermann, "Improved Weighted Centroid Localization in Smart Ubiquitous Environments," in Ubiquitous Intelligence and Computing, Verlag Berlin Heidelberg, Springer, 2008, pp. 20-34. [28] S. Chan and G. Sohn, "Indoor localization using Wi-Fi based fingerprinting and trilateration techiques for LBS applications," in 7th International Conference on 3D Geoin formation, Quebec, Canada, May 2012. [29] Z. Farid, R. Nordin and M. Ismail, "Recent Advances in Wireless Indoor Localization Techniques and System," Journal of Comuputer Networks and Communication, vol. 2013, pp. 1-12, 17th August, 2013. [30] A. Goldsmith, Wireless Communications, 1 ed., Cambridge University Press;, August 8, 2005. [31] Mathworks, "MathWorks," 2014. [Online]. Available: http://www.mathworks.com/help/comm/ref/awgnchannel.html. 98 [32] T. M. Jamel and S. K. Gharken, "Design and Simulation of Base Band Direct Sequence Spread Spectrum (DS/SS) System Using Matlab Simulink," in Scientific Conference of Technical College, 2009. [33] Pogge, R., W.;, "Real-World Relativity: The GPS Navigation System," 10 April 2009. [Online]. Available: http://www.astronomy.ohio-state.edu/~pogge/Ast162/Unit5/gps.html. [34] P. A. Zandbergen, "Accuracy of iPhone locations: A comparison of assisted GPS, WiFi and cellular positioning," GIS, vol. 13, no. 1, pp. 5-26, 2009. [35] V. D. Smedt, G. Gielen and W. Dehaene, "Long-term Oscillator Stability," in Temperature- and Supply Voltage-Independent Time References for Wireless Sensor Networks, Springer, 8 November, 2014, pp. 91-135. [36] M. S. McCorquodale, G. A. Carichner, D. O. Justin, S. M. Pernia, S. Kubba, E. D. Marsman, J. J. Kuhn and R. B. Brown, "A 25-MHz self-referenced solid-state frequency source suitable for xoreplacement," Circuits and Systems I: Regular Papers, IEEE Transactions, no. May 2009, pp. 943-956, May 2009. [37] "Cisco Wireless Mesh Access Points, Design and Deployment Guide, Release 7.3," CISCO. [38] J.-J. Park, M.-D. Kim, H.-K. Chung and W. Kim, "Ricean K-factor Analysis of Indoor Channel Measurements at 3.7 GHz," in IEEE, Beijing, 25-27 Aug 2010. [39] "Finnish Geodetic Institute," [Online]. Available: http://www.fgi.fi/fgi/themes/indoor-navigation. 99 [40] D. Focken and R. Stiefelhagen, "Towards vision-based 3-D people tracking in a smart room," in 4th IEEE International Conference on Multimodal Interfaces, Oct 2002. [41] F. H. Raab, E. B. Blood, T. O. Steiner and H. R. Jones, "Magnetic Position and Orientation Tracking System," IEEE Trans. Aerospace and Electronic Systems, Vols. AES-15, no. 5, pp. 709-718, Sep 1979. [42] P. H. Dana, "The Global Positioning System," 2012. [Online]. Available: http://www.colorado.edu/geography/gcraft/notes/gps/gps_f.html.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Frequency offset estimation for GPS enabled Wi-Fi access...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Frequency offset estimation for GPS enabled Wi-Fi access points. Khan, Tausif Ezaj 2015
pdf
Page Metadata
Item Metadata
Title | Frequency offset estimation for GPS enabled Wi-Fi access points. |
Creator |
Khan, Tausif Ezaj |
Publisher | University of British Columbia |
Date Issued | 2015 |
Description | A method to estimate the frequency offset between the internal oscillators of two or more GPS RF front-ends is described and evaluated. The purpose of this is to allow a Non-Line-of-Sight (NLOS) GPS receiver to acquire and track satellite signals with assistance data provided by a Line-of-Sight (LOS) GPS receiver. This facilitates indoor positioning with GPS, which is used to accurately position 802.11 WLAN access points that will be used in an integrated indoor positioning system. The assistance data consists of the Doppler frequency and code phase of GPS satellites that the LOS GPS receiver can clearly view. Knowing this information at the NLOS GPS receiver significantly reduces the Doppler search space and code phase search space resulting in faster signal acquisition. To effectively use this assistance information, the NLOS GPS receiver oscillator must be synchronized to that of the LOS GPS receiver to within 10 ns. This frequency synchronization is accomplished by estimating the frequency offset between the two oscillators with a signal transmitted between the two receivers via a WLAN channel. COCC (Carrier Only Cross Correlation) and CCCC (Code + Carrier Cross Correlation) are two proposed techniques to estimate this frequency offset to within ±30 Hz. In COCC, a single carrier signal is sent by the LOS receiver at 10.23 MHz and cross-correlated with a replica signal generated at the NLOS receiver. This technique’s best performance (frequency estimation within ±30 Hz) is achieved at SNR > -4 dB in an AWGN channel and at SNR > 22 dB in a Rayleigh fading channel at a separation distance of 25 m. The CCCC technique has a 1023 chip PRN code at 1.023 Mega chips/sec modulated on the transmitted carrier signal and is cross-correlated with the replica code-modulated signal generated at the NLOS receiver. The optimum code sampling frequency for CCCC was found to be 10 MHz. It is shown that CCCC can estimate a frequency offset to within ±30 Hz at SNR > -14 dB in an AWGN channel and SNR > -10 dB in a Rayleigh fading channel at a separation distance of 35 m. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2015-05-21 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivs 2.5 Canada |
DOI | 10.14288/1.0074425 |
URI | http://hdl.handle.net/2429/53296 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Engineering, School of (Okanagan) |
Degree Grantor | University of British Columbia |
Graduation Date | 2015-09 |
Campus |
UBCO |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/2.5/ca/ |
Aggregated Source Repository | DSpace |
Download
- Media
- 24-ubc_2015_september_Khan_Tausif.pdf [ 2.25MB ]
- Metadata
- JSON: 24-1.0074425.json
- JSON-LD: 24-1.0074425-ld.json
- RDF/XML (Pretty): 24-1.0074425-rdf.xml
- RDF/JSON: 24-1.0074425-rdf.json
- Turtle: 24-1.0074425-turtle.txt
- N-Triples: 24-1.0074425-rdf-ntriples.txt
- Original Record: 24-1.0074425-source.json
- Full Text
- 24-1.0074425-fulltext.txt
- Citation
- 24-1.0074425.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0074425/manifest