Investigation of Wireless Local Area Network Facilitated Angle of Arrival Indoor Location by Carl Monway Wong A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in The College of Graduate Studies (Applied Science) THE UNIVERSITY OF BRITISH COLUMBIA (Okanagan) August, 2008 c© Carl Monway Wong 2008 Abstract As wireless devices become more common, the ability to position a wireless device has become a topic of importance. Accurate positioning through technologies such as the Global Positioning System is possible for outdoor environments. Indoor environments pose a different challenge, and research continues to position users indoors. Due to the prevalence of wireless local area networks (WLANs) in many indoor spaces, it is prudent to determine their capabilities for the purposes of positioning. Signal strength and time based positioning systems have been studied for WLANs. Direction or angle of arrival (AOA) based positioning will be possible with multiple antenna arrays, such as those included with upcoming devices based on the IEEE 802.11n standard. The potential performance of such a system is evaluated. The positioning performance of such a system depends on the accuracy of the AOA estimation as well as the positioning algorithm. Two differ- ent maximum-likelihood (ML) derived algorithms are used to determine the AOA of the mobile user: a specialized simple ML algorithm, and the space- alternating generalized expectation-maximization (SAGE) channel parame- ter estimation algorithm. The algorithms are used to determine the error in estimating AOAs through the use of real wireless signals captured in an indoor office environment. The statistics of the AOA error are used in a positioning simulation to predict the positioning performance. A least squares (LS) technique as well as the popular extended Kalman filter (EKF) are used to combine the AOAs to determine position. The position simulation shows that AOA- based positioning using WLANs indoors has the potential to position a wireless user with an accuracy of about 2 m. This is comparable to other positioning systems previously developed for WLANs. ii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii List of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . xi List of Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . xv Dedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvi Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Motivation and Applications . . . . . . . . . . . . . . . . . . 2 1.2 Wireless Positioning . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Indoor Wireless Positioning . . . . . . . . . . . . . . . . . . . 3 1.4 Network and Mobile Positioning . . . . . . . . . . . . . . . . 5 1.5 Wireless Local Area Networks . . . . . . . . . . . . . . . . . 6 1.6 Multiple-Input Multiple-Output . . . . . . . . . . . . . . . . 7 1.7 WLAN Positioning . . . . . . . . . . . . . . . . . . . . . . . 8 1.8 Research Objectives . . . . . . . . . . . . . . . . . . . . . . . 10 1.9 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.10 Thesis Overview . . . . . . . . . . . . . . . . . . . . . . . . . 12 iii Table of Contents Chapter 2 Positioning . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1 Positioning Methods . . . . . . . . . . . . . . . . . . . . . . . 14 2.1.1 Lines of Position . . . . . . . . . . . . . . . . . . . . . 15 2.1.2 Positioning Accuracy . . . . . . . . . . . . . . . . . . 16 2.2 Time of Arrival Positioning . . . . . . . . . . . . . . . . . . . 17 2.3 Time Difference of Arrival Positioning . . . . . . . . . . . . . 19 2.4 Angle of Arrival Positioning . . . . . . . . . . . . . . . . . . 21 2.5 Received Signal Strength Positioning . . . . . . . . . . . . . 23 Chapter 3 The Indoor Wireless Channel . . . . . . . . . . . . 25 3.1 Multipath and the Channel Impulse Response . . . . . . . . 25 3.2 Properties of the Wireless Channel . . . . . . . . . . . . . . . 27 3.2.1 Delay Spread and Time Density . . . . . . . . . . . . 27 3.2.2 Angle Spread . . . . . . . . . . . . . . . . . . . . . . . 28 3.3 Channel Sounding System . . . . . . . . . . . . . . . . . . . 29 3.3.1 Antenna Array . . . . . . . . . . . . . . . . . . . . . . 31 3.3.2 Transmitter . . . . . . . . . . . . . . . . . . . . . . . 31 3.3.3 Receiver . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.3.4 Equipment Calibration . . . . . . . . . . . . . . . . . 33 3.3.5 Channel Impulse Response Estimation . . . . . . . . 36 3.4 Indoor Channel Measurements . . . . . . . . . . . . . . . . . 37 Chapter 4 Angle of Arrival Estimation . . . . . . . . . . . . . 41 4.1 Signal Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.2 Cramér-Rao Lower Bound . . . . . . . . . . . . . . . . . . . 44 4.3 General Channel Parameter Estimation . . . . . . . . . . . . 47 4.3.1 Maximum Likelihood Channel Parameter Estimation 48 4.3.2 Expectation-Maximization Channel Parameter Esti- mation . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.3.3 Space-Alternating Generalized Expectation-Maximization Channel Parameter Estimation . . . . . . . . . . . . . 52 4.3.4 SAGE Implementation . . . . . . . . . . . . . . . . . 54 4.3.5 Determining AOA from Channel Parameters . . . . . 55 iv Table of Contents 4.3.6 Estimation of Number of Multipath Arrivals . . . . . 56 4.4 Simplified ML AOA Implementation . . . . . . . . . . . . . . 57 4.5 ML Estimation Performance . . . . . . . . . . . . . . . . . . 59 4.6 SAGE Estimation Performance . . . . . . . . . . . . . . . . . 65 4.7 Estimation Performance Summary . . . . . . . . . . . . . . . 70 Chapter 5 Positioning Simulation . . . . . . . . . . . . . . . . . 71 5.1 Random AOA Generation . . . . . . . . . . . . . . . . . . . . 71 5.2 AOA Least Squares Positioning . . . . . . . . . . . . . . . . 72 5.3 Extended Kalman Filter . . . . . . . . . . . . . . . . . . . . 75 5.4 AP Geometry Considerations . . . . . . . . . . . . . . . . . . 79 5.5 Positioning Performance . . . . . . . . . . . . . . . . . . . . 80 5.5.1 Fixed Position Estimation Performance . . . . . . . . 83 5.5.2 Trajectory Estimation Performance . . . . . . . . . . 89 Chapter 6 Conclusions and Future Work . . . . . . . . . . . . 95 6.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 6.1.1 AOA Estimation . . . . . . . . . . . . . . . . . . . . . 95 6.1.2 Position Estimation . . . . . . . . . . . . . . . . . . . 98 6.2 Future Development . . . . . . . . . . . . . . . . . . . . . . . 99 6.2.1 Positioning Performance Improvements . . . . . . . . 99 6.2.2 Prototype Development . . . . . . . . . . . . . . . . . 101 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 Appendices Appendix A: ML Estimation Statistics . . . . . . . . . . . . . . 110 Appendix B: SAGE Estimation Statistics . . . . . . . . . . . . 117 Appendix C: Positioning Simulation Results . . . . . . . . . . 122 v List of Tables 3.1 Transmitter and receiver locations for the various indoor mea- surement situations. . . . . . . . . . . . . . . . . . . . . . . . 40 3.2 Approximate SNR for the various indoor measurement situ- ations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.1 Example SAGE and ML estimated channel parameters for an LOS measurement, with actual AOA of 90◦. . . . . . . . . . . 69 A.1 Mean and standard deviation of the ML AOA estimates for the indoor measurements. . . . . . . . . . . . . . . . . . . . . 111 B.1 Mean and standard deviation of the SAGE AOA estimates for the indoor measurements. . . . . . . . . . . . . . . . . . . 118 C.1 Fixed position simulation ARMSE for the various indoor mea- surement types. . . . . . . . . . . . . . . . . . . . . . . . . . . 123 C.2 Trajectory simulation ARMSE for the various indoor mea- surement types. . . . . . . . . . . . . . . . . . . . . . . . . . . 124 vi List of Figures 1.1 Multipath in an LOS situation between transmitter and re- ceiver. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Multipath in an NLOS situation between transmitter and re- ceiver. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1 How DOP varies based on the intersection of the lines of position. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 Example of circles of position for TOA-based positioning us- ing three APs. . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3 Example of hyperbolas of position for TDOA-based position- ing using three APs. . . . . . . . . . . . . . . . . . . . . . . . 20 2.4 Example of lines of position for AOA-based positioning using three APs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.1 Example multipath in an indoor wireless channel in terms of amplitude, delay and AOA. . . . . . . . . . . . . . . . . . . . 28 3.2 Example of amplitudes at various delays in an indoor wireless channel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.3 Example of AOAs at various delays in an indoor wireless chan- nel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.4 Autocorrelation of PN sequence of length K as a function of sequence offset t. . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.5 Photo of the four-antenna linear monopole array used for transmission and reception. . . . . . . . . . . . . . . . . . . . 32 3.6 Ideal received signal from all transmit antennas after correla- tion with the transmit sequence. . . . . . . . . . . . . . . . . 33 vii List of Figures 3.7 Hardware configuration for the transmitter. . . . . . . . . . . 34 3.8 Photo of the transmitter equipment. . . . . . . . . . . . . . . 34 3.9 Hardware configuration for the receiver. . . . . . . . . . . . . 35 3.10 Photo of the receiver equipment. . . . . . . . . . . . . . . . . 35 3.11 Configuration for relative phase and amplitude calibration between the receiver channels. . . . . . . . . . . . . . . . . . . 36 3.12 Example CIR generated from a channel measurement. . . . . 38 3.13 Map of University of Calgary Information and Communica- tions Technology building third floor with receiver and trans- mitter positions. . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.1 Diagram of the arriving signal for multipath component l at the four element linear monopole array. . . . . . . . . . . . . 43 4.2 AOA estimation error of ML algorithm in various indoor sit- uations at 300 MHz bandwidth. . . . . . . . . . . . . . . . . . 60 4.3 AOA estimation error of ML algorithm in various indoor sit- uations at 40 MHz bandwidth. . . . . . . . . . . . . . . . . . 60 4.4 AOA estimation error of ML algorithm in various indoor sit- uations at 40 MHz bandwidth with SNR lowered to 20 dB. . 62 4.5 The additional propagation distance to each receive antenna given azimuth angle φ and elevation angle ω. . . . . . . . . . 64 4.6 AOA estimation mean error of SAGE algorithm in various indoor situations at 300 MHz bandwidth, using varying num- bers of total estimated multipath arrivals. . . . . . . . . . . . 66 4.7 AOA estimation error standard deviation of SAGE algorithm in various indoor situations at 300 MHz bandwidth, using varying numbers of total estimated multipath arrivals. . . . . 66 4.8 AOA estimation error of SAGE algorithm in various indoor situations at 300 MHz bandwidth, using 3 total estimated multipath arrivals. . . . . . . . . . . . . . . . . . . . . . . . . 68 4.9 AOA estimation error of SAGE algorithm in various indoor situations at 40 MHz bandwidth, using 3 total estimated mul- tipath arrivals. . . . . . . . . . . . . . . . . . . . . . . . . . . 68 viii List of Figures 5.1 Example CDF generated from the PDF in Figure A.6(a). . . 72 5.2 DOP for the northing and easting directions for AOA posi- tioning in units of metres per radian. . . . . . . . . . . . . . . 81 5.3 DOP correlation and HDOP for AOA positioning. . . . . . . 81 5.4 Example estimated positions depending on correlation ρ be- tween DOP in northing and easting directions. . . . . . . . . 82 5.5 LS initial position estimates based on approximate area. . . . 84 5.6 RMS position error in metres from 1000 Monte Carlo simu- lation trials, using AOA error generated from Figure A.5(a). . 86 5.7 Number of converged position estimates out of 1000 Monte Carlo simulation trials, using AOA error generated from Fig- ure A.5(a). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 5.8 RMS position error in metres from 1000 Monte Carlo simu- lation trials, using AOA error generated from Figure A.6(a). . 87 5.9 Number of converged position estimates out of 1000 Monte Carlo simulation trials, using AOA error generated from Fig- ure A.6(a). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 5.10 RMS position error divided by the AOA error standard devi- ation in metres per radian from 1000 Monte Carlo simulation trials, using AOA error generated from Figure A.6(a). . . . . 88 5.11 Typical example trajectory simulation trial with LS and EKF using AOA error from ML estimates PDF shown in Figure A.6(a). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 5.12 Worst case example trajectory simulation trial with LS and EKF using AOA error with significant outliers from SAGE algorithm using the PDF shown in Figure B.4(a). . . . . . . . 91 5.13 Best case example trajectory simulation trial with LS and EKF using AOA error from ML estimates PDF shown in Fig- ure A.5(a). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 5.14 Example trajectory simulation run with EKF showing effect of mobile movement not matching dynamic model. . . . . . . 93 ix List of Figures A.1 PDF of the ML AOA estimation error for the LOS measure- ments using 300 MHz bandwidth. . . . . . . . . . . . . . . . . 112 A.2 PDF of the ML AOA estimation error for the single wall measurements using 300 MHz bandwidth. . . . . . . . . . . . 112 A.3 PDF of the ML AOA estimation error for the double wall measurements using 300 MHz bandwidth. . . . . . . . . . . . 113 A.4 PDF of the ML AOA estimation error for the LOS measure- ments using 40 MHz bandwidth. . . . . . . . . . . . . . . . . 113 A.5 PDF of the ML AOA estimation error for the single wall measurements using 40 MHz bandwidth. . . . . . . . . . . . . 114 A.6 PDF of the ML AOA estimation error for the double wall measurements using 40 MHz bandwidth. . . . . . . . . . . . . 114 A.7 PDF of the ML AOA estimation error for the LOS measure- ments using 40 MHz bandwidth with SNR lowered to 20 dB. 115 A.8 PDF of the ML AOA estimation error for the single wall measurements using 40 MHz bandwidth with SNR lowered to 20 dB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 A.9 PDF of the ML AOA estimation error for the double wall measurements using 40 MHz bandwidth with SNR lowered to 20 dB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 B.1 PDF of the SAGE AOA estimation error for the LOS mea- surements using 300 MHz bandwidth. . . . . . . . . . . . . . 119 B.2 PDF of the SAGE AOA estimation error for the single wall measurements using 300 MHz bandwidth. . . . . . . . . . . . 119 B.3 PDF of the SAGE AOA estimation error for the double wall measurements using 300 MHz bandwidth. . . . . . . . . . . . 120 B.4 PDF of the SAGE AOA estimation error for the LOS mea- surements using 40 MHz bandwidth. . . . . . . . . . . . . . . 120 B.5 PDF of the SAGE AOA estimation error for the single wall measurements using 40 MHz bandwidth. . . . . . . . . . . . . 121 B.6 PDF of the SAGE AOA estimation error for the double wall measurements using 40 MHz bandwidth. . . . . . . . . . . . . 121 x List of Abbreviations AOA angle of arrival AP access point ARMSE average root mean squared error AWG arbitrary waveform generator BLUE best linear unbiased estimator BPF bandpass filter CDF cumulative density function CIR channel impulse response CRLB Cramér-Rao lower bound dB decibels dBm decibels relative to 1 mW DOP dilution of precision EDOP easting dilution of precision EKF extended Kalman filter EM expectation-maximization ESPRIT estimation of signal parameters via rotational invariance technique FCC Federal Communications Commision FIM Fisher information matrix FPGA field programmable gate array GNSS global navigation satellite system GPS Global Positioning System HDOP horizontal dilution of precision LAN local area network LO local oscillator LORAN Long Range Navigation xi List of Abbreviations LOS line-of-sight LPF lowpass filter LS least squares MEMS microelectromechanical systems MIMO multiple-input multiple-output MISO multiple-input single-output ML maximum likelihood MUSIC multiple signal classification NDOP northing dilution of precision NLOS non-line-of-sight OFDM orthogonal frequency division multiplexing PDF probability density function PN pseudorandom noise RF radio frequency RMS root mean square RSS received signal strength RX receiver SAGE space-alternating generalized expectation-maximization SIMO single-input multiple-output SISO single-input single-output SNR signal to noise ratio TDOA time difference of arrival TOA time of arrival TX transmitter UWB ultrawideband WLAN wireless local area network xii List of Symbols In the listed symbols b denotes a scalar parameter and b denotes a matrix or vector parameter. A design matrix a(t) autocorrelation function for transmitted signal bH Hermitian (complex conjugate and transpose) bT matrix transpose b̂ estimate b∗ complex conjugate E{b} expected value Erms RMS position error F Fisher Information Matrix h channel impulse response vector h(t) channel impulse response I identity matrix Kn Kalman gain matrix L number of multipath arrivals M number of receive antennas N independent complex white Gaussian noise process p(b) probability density function Pn (−) state covariance matrix prior to inclusion of observations Pn (+) state covariance matrix after inclusion of observations Pu transmitted signal power Q dynamic model error covariance matrix R observations error covariance matrix s signal for a single multipath arrival xiii List of Symbols Tu period of the transmitted sequence w misclosure vector x̂n (−) predicted state estimate before inclusion of observations x̂n (+) state estimate after inclusion of observations Y received signal vector Ym signal received at antenna m α multipath arrival complex amplitude δ LS position correction δ(t) Dirac delta function θ channel parameters Λ likelihood function λ wavelength µ mean ρ correlation σ standard deviation σ2 variance τ multipath arrival delay φ multipath arrival angle of arrival ω multipath elevation angle ⊗ convolution operation correlation operation |b| absolute value • dot product <{b} real part xiv Acknowledgments I would like to thank TR Labs Calgary for the use of their channel charac- terization equipment which facilitated a large portion of my research. I would also like to thank my supervisors Dr. Geoffrey Messier and Dr. Richard Klukas for their invaluable help and support, in guiding me smoothly through my research. I would like to thank Glenn MacGougan, a PhD candidate at the Schulich School of Engineering at the University of Calgary in the Department of Geomatics Engineering, for helping me perform the survey that allowed me to know the positions and orientations of the transmitter and receiver. xv Dedication Dedicated to my family without whom my higher education would not have been possible. xvi Chapter 1 Introduction A large proportion of the electronic devices being introduced to the market require, or are enhanced by, connection to a larger data network. In the interest of convenience and mobility, many of these data networks are im- plemented using wireless communications. In addition to providing data ser- vice, many additional wireless services are becoming location-aware. With the proliferation of the NAVSTAR Global Positioning System (GPS), an implementation of a Global Navigation Satellite System (GNSS), the ability to determine position and navigate has become expected. However, due to the shortcomings of GPS, additional technology is needed to provide loca- tion information to the wireless user in situations when GPS is unavailable or inaccurate. The introduction to this thesis begins with the motivations and applica- tions of wireless positioning technology in section 1.1. A brief overview of wireless positioning leads into indoor positioning and a discussion of the dif- ference between mobile and network positioning in sections 1.2 through 1.4. The developments and prevalence of wireless local area networks (WLANs) are presented in section 1.5. One of the recent developments is the inclusion of multiple-input multiple-output (MIMO) technology, the positioning im- plications of which are discussed in section 1.6. Section 1.7 introduces past and current research using WLANs to determine position. The objectives of this thesis are presented in section 1.8, followed by the contributions of this study in section 1.9. Finally, the outline of the thesis is described in section 1.10. 1 Chapter 1. Introduction 1.1 Motivation and Applications Phase II of the Federal Communications Commission (FCC) Wireless E911 mandate in the US [1] requires networks to be able to position cell phones within their networks during emergency calls. This prompted a flurry of research into wireless positioning for cell phones. One solution is to include GPS in every cell phone, which works well outdoors. Tests have been per- formed indoors using GPS, and found accuracy of about 100 m [2]. This is unsuitable for high accuracy applications and may not meet the E911 phase II handset positioning accuracy requirements of 50 m and 100 m with reliability of 67% and 95% respectively. Since most users are often in- doors or in areas without clear view of sufficient numbers of GPS satellites, additional technology is necessary for higher accuracy positioning in these situations. The shortcomings of GPS for indoor use are caused by very low signal strength and additional errors caused by the lack of clear view of the sky. Since many indoor environments are outfitted with WLANs, it makes sense to evaluate whether WLAN infrastructure is useful in positioning the indoor wireless user. There are many applications for indoor positioning. Practical applica- tions of this technology include emergency services, tracking hospital pa- tients [3], asset tracking [4], network management [5], targeted personalized advertising [6], social networking [7], personal navigation [8] and many oth- ers. The number of applications is rising steadily. The choice of positioning technology for a particular application is prioritized between accuracy, re- liability, flexibility, size, power restrictions, deployment environment, and cost, among others. 1.2 Wireless Positioning Wireless positioning encompasses many different positioning methods. Op- tical based positioning is included in these, but only radio frequency (RF) methods which are usable in non-line of sight (NLOS) situations will be dis- cussed. Positioning is performed by the transmission of a radio signal, which 2 Chapter 1. Introduction is then received at another device. Some aspect of the relative position of the devices is represented in the received signal. Because the received signal is the data used to facilitate positioning, the undesirable signal distortion that occurs during wireless transmission is very important. A wireless positioning system generally consists of at least two different components. The user or mobile, which is to be positioned; and the infras- tructure of access points (APs) with known positions, called the network. In the case of GPS, a widespread wireless positioning system, the mobile is the GPS receiver. The satellites orbiting the earth are the APs. Note that in the GPS case, the positions of the orbiting satellite APs in the infrastructure are not constant, but known. Note that unlike most modern data communications systems, two-way communication is not strictly required for positioning. 1.3 Indoor Wireless Positioning Wireless positioning involves transmission of a wireless signal, and upon reception, some property of the received signal is used to determine the relative positions of the receiver or transmitter. Measured properties of the signal commonly used for positioning are the received signal strength (RSS), time of signal reception, and the direction from which the signal is received or angle of arrival (AOA). Measurements using APs at different locations are combined to determine position. All wireless signals reflect and scatter off objects in their environment, and transmitted wireless signals experience distortion when received. Copies of the transmitted signal are received, each at different times and from different directions. This phenomenon is multipath and due to the density and proximity of objects in an indoor environment, indoor signals can be significantly distorted. The destructive adding of the reflections can result in lower strength, or fading, of the received signal. The wireless channel encompasses the overall effect of objects in an envi- ronment between signal transmission and reception. The multipath wireless channel is different in situations where the transmitter and receiver have 3 Chapter 1. Introduction line of sight (LOS) and when they do not. This is shown in Figures 1.1 and 1.2 respectively. The direct path is the portion of the signal relevant for positioning since it represents the true direction and distance between the transmitter and receiver. The measurements from the received signal must be made on the part of the received signal corresponding to the direct path. When attenuated due to obstruction, the direct path is more difficult to identify, which can result in large errors in determining position. For in- stance, when measuring AOAs, if the direct path is attenuated enough such that it cannot be identified, then a reflection could be incorrectly selected as the direct path. Since the direction of the reflection can be very different from that of the direct path, the measured AOA contains error. Transmitter Receiver Obstruction Direct Path Reflection Figure 1.1: Multipath in an LOS situation between transmitter and receiver. Transmitter Receiver Obstruction Attenuated Direct Path Reflection Figure 1.2: Multipath in an NLOS situation between transmitter and re- ceiver. 4 Chapter 1. Introduction 1.4 Network and Mobile Positioning GPS is an example of a mobile-based positioning system. In a purely mobile- based positioning system, the infrastructure transmits the positioning sig- nals to the mobile, which receives the signal and determines its own posi- tion. This type of positioning is most useful for a system that expects to have many mobile devices simultaneously requesting position. This is to reduce the amount of computation required by the network. More impor- tantly, for GPS the transmission power requirements are very large due to the immense distance between the satellites and the surface of the earth, which make it impractical for signals to be transmitted by the mobile. It also makes sense since the mobile is interested in its own position, and no additional communication with the mobile is necessary. Network-based positioning systems are more rare. Most proposed cel- lular network positioning solutions are of this type since the cellular base stations have access to more computational resources, more sophisticated antenna arrays and due to their height and distance from the mobile, the multipath effects are less severe. As the name suggests, network-based po- sitioning involves the mobile transmitting the positioning signal to the net- work infrastructure. The network then computes the positioning measure- ments which are used to calculate the position of the user. This places the computational load on the network, and is most useful in instances when constant positioning of many mobiles is not necessary, such as when posi- tions are calculated on demand. In addition, if the number of positioning computations is very large, then a smaller mobile device may not be able to quickly compute its own position, and therefore this work is performed by the network. Therefore it is useful for emergency systems when positions are not often requested, or when the position information is useful to someone other than the mobile user. Mobile-based positioning systems can be expected to have a higher po- tential for positioning accuracy, at least in the cases where the mobile has stringent size and power limitations. The infrastructure generally has direct access to large amounts of energy resources, so the transmission power from 5 Chapter 1. Introduction the APs can be considerably larger than that possible by the mobile. With higher transmission power and therefore higher signal to noise ratio (SNR), greater positioning accuracy is expected. This is especially true for very large distances between the mobile and infrastructure as in the case of GPS. On the other hand, APs generally have greater access to computational re- sources which proves useful when the amount of computation required for positioning is large. 1.5 Wireless Local Area Networks WLANs are becoming ubiquitous indoors, as more and more users demand mobile data network access. Most are currently based on the IEEE stan- dards 802.11b, 802.11a and 802.11g, and are generally called Wi-Fi. The increasing trend of being able to access data from anywhere is driving de- velopments in wireless data networks. The latest technology in the later stages of development is based on the IEEE 802.11n standard [9]. Products are appearing in the market based on the standard, since it is stable even though the standard has yet to be finalized. Like most upcoming wireless technologies, the main improvements over older technologies are reliability, range, and higher data throughput. The maximum data rate is increased to 300 Mbps over 54 Mbps for 802.11g [10]. WLAN infrastructure consists of APs connected to a wired local area network (LAN). The APs transmit and receive the wireless data signals and communicate with the wireless devices in their vicinity. These APs are placed in various positions, often at ceiling level, and are spread out in an indoor space such that a device should be able to receive WLAN signal from at least one AP anywhere where service is intended. This usually results in overlap to ensure complete coverage. The usable range of a typical WLAN AP indoors is approximately 40 m. Devices based on the 802.11n standard are expected to double the operating range [11]. For full coverage of an area, WLAN APs are normally installed at higher densities than this. The presence of these APs in many indoor environments raises the ques- tion of their suitability for the purposes of determining mobile device posi- 6 Chapter 1. Introduction tion. Since most APs are connected to the same data network, a computer with sufficient permission on the network should be able to gather posi- tioning information from the APs. This allows for the position of a small mobile device to be calculated by a network device with more computational resources. WLAN signals consist of two basic parts, the preamble and the data. The preamble is used for signal detection, timing synchronization, frequency off- set estimation, automatic gain control and channel estimation. The pream- ble is the part of the received signal which is useful for positioning purposes. The preamble for the IEEE 802.11a standard consists of short training sym- bols followed by long training symbols [12]. Each symbol consists of mod- ulated bits, 8 in the case of the short training symbols and 32 for the long training symbols. The total number of training bits usable for positioning for an 802.11a preamble is 144. The 802.11n preamble is similar although additional training symbols can be inserted elsewhere in the signal [13] for the purposes of additional channel estimation. The new IEEE 802.11n standard includes provisions for multiple-antenna arrays [9], which has been enabled by advances in computing such that the additional cost is considered acceptable relative to the performance benefits. Multiple antennas are optional for 802.11n, with up to four antennas in each array [10]. The inclusion of multiple antennas at each AP has the benefit of allowing for the determination of the direction from which signals arrive. Knowledge of the mobile’s direction at multiple APs in the network enables computation of the mobile’s position. 1.6 Multiple-Input Multiple-Output To enhance the performance of wireless networks, various techniques are used. These include modulation and diversity. Diversity of the wireless environment or channel can be exploited in terms of time, frequency and space. Briefly, time diversity techniques take advantage of the variations in the received signal over time caused by the objects in the wireless environ- ment. Frequency diversity is caused by the varying effects of the wireless 7 Chapter 1. Introduction environment depending on the frequency of the signal. The popular orthog- onal frequency division multiplexing (OFDM) technique takes advantage of frequency diversity to handle adverse wireless conditions. Spatial diversity techniques use the variations in the wireless signal re- ceived at different points in space. To leverage the benefits of spatial di- versity, multiple antennas are used at the transmitter and receiver, called MIMO. Variations on this include a single antenna for reception, multiple- input single-output (MISO); and a single antenna for transmission, single- output multiple-input (SIMO). The simplest and most common scheme is single-input single-output (SISO) which uses a single antenna for both trans- mission and reception. The use of multiple antennas increases system performance by mitigat- ing the natural signal strength fluctuations caused by the wireless environ- ment. By intelligently combining the signal from spatially separated anten- nas, the probability that all the received signals are lost is lowered. The data throughput of a system is therefore improved [14]. MIMO is beginning to be employed in different technologies, but is not practical for some since it requires a larger antenna array and incurs addi- tional hardware cost. The hardware cost is increased not only due to the inclusion of multiple antennas, but the received signals must be combined in an optimal fashion, making additional processing necessary. Many high speed future wireless data systems are expected to use MIMO to reach de- sired throughput levels. MIMO can also be used to perform direction-based positioning in systems that feature them. 1.7 WLAN Positioning Different techniques have been developed for positioning the indoor wireless user. Of those that utilize WLAN signals, most focus on RSS [15, 16]. These systems require no changes to the hardware used, since the RSS measure- ments are already provided by most consumer WLAN devices. RSS-based positioning methods are broadly broken up into two groups: fingerprinting and propagation modeling. 8 Chapter 1. Introduction Fingerprinting involves generating an RSS map of the area of interest, noting the RSS for each AP for every position in the map. Determination of user position involves reading the RSS of the signal from all the APs and using a search to find the best match in the RSS map. This transforms the positioning process into a pattern recognition problem. The position esti- mation can be as accurate as 2 m [17]. Preserving this positioning accuracy involves resurveying the entire RSS map for all changes in the environment which is not practical. Indoor environments are constantly changing, with objects being removed and introduced. Therefore actual usage of such a sys- tem can be expected to perform worse than studies indicate over the long term, as the indoor environment changes. Also an RSS positioning technique, propagation modeling does not re- quire a map of the environment, and determines position by approximating the RSS from an AP as a distance from that AP. This is then used as dis- tance information to determine position, which can then be refined by using knowledge about the indoor environment. This method is less accurate than the fingerprinting method, with accuracy of approximately 2.5 m [16]. Systems that implement RSS WLAN positioning are already up and running, such as SkyHook [18], WhereNet [19] and Ekahau [20]. SkyHook claims positioning accuracy of better than 20 m. Work has been done to characterize the statistical properties of the RSS measurements, which can be used in a positioning algorithm to result in better positioning accuracy [21, 22]. The motivation behind research into RSS methods is clear, as they are the easiest to implement. They can be implemented using consumer hard- ware, and the positioning solution can be fully determined in software on a mobile computer. RSS positioning is attractive as there is no need to make any changes to existing WLAN infrastructure. Other research has looked at indoor positioning using the time-based time of arrival (TOA) or time difference of arrival (TDOA) methods using WLANs [12, 23, 24, 25]. Only a few have implemented such a system, and indicate better positioning accuracy than RSS-based systems [26]. Little re- search has been done for AOA positioning using WLANs due to the previous 9 Chapter 1. Introduction lack of antenna arrays capable of determining signal direction. The accu- racy of time-based positioning systems has historically been better than that of both RSS and AOA-based systems, but time-based positioning requires synchronization between the transmitters. In addition, the positioning per- formance of a TOA-based solution is heavily dependent on the bandwidth of the signal used. The bandwidth of WLAN signals is relatively small, and therefore higher accuracy positioning might be possible using a different technique. There are other systems that allow for non-WLAN facilitated indoor positioning. Systems implemented using ultrawideband (UWB) frequency spectra have the potential for sub-meter level positioning accuracy [27]. Companies such as Locata Corporation have developed TOA systems with GPS-like positioning capabilities [28]. They claim to be able to extend the positioning to indoor environments [29]. In addition, there has been research that integrates different positioning methods. For instance, some take advantage of the integration of microelec- tromechanical systems (MEMS) inertial sensors with another positioning technique such as RSS [30]. Combining RSS WLAN positioning and GPS measurements to determine user position outdoors and indoors has also been investigated [31]. 1.8 Research Objectives Indoor positioning using AOAs has not been investigated much in research. The usual premise is that it is less accurate in determining user position than time-based methods and requires higher computational and hardware costs. However, AOA positioning has the benefit of not requiring high accu- racy time synchronization. Future WLAN APs may feature MIMO antenna arrays, and thus allow for the possibility of AOA positioning. It there- fore seems to be an appropriate time to investigate AOA positioning using WLANs. The advancements in computational capacity also reduce the ad- ditional costs of AOA-based positioning. The argument that time-based positioning is more accurate than AOA 10 Chapter 1. Introduction position is based on the usage of positioning systems outdoors for long range applications. AOA positioning systems become more accurate as the dis- tance between the positioning infrastructure and the mobile is decrased. In an indoor environment where the wireless devices are closer in proximity to each other, AOA could result in better positioning accuracy than in long range outdoor environments. If the performance of AOA positioning using WLANs is similar to that of other WLAN positioning systems, it merits further study. The purpose of this research is to perform an evaluation of the potential performance using MIMO equipped WLAN APs in AOA-based positioning of the indoor wireless user. With an idea of what the potential performance is, the possible applications suited to such a system can be determined. Since the design and construction of such a system is too large in scope, a more limited practical investigation is performed. The system to be evaluated uses a network-based positioning method. The network consists of multiple MIMO-capable APs, and covers a typical office-type indoor space. The position of a WLAN user in the network is requested, either by the user or network operator. Each AP in the network within range of the mobile’s signal gets a snapshot of the received signal from all of its receive antennas and estimates the AOA of the mobile. These AOAs are then sent to a central computer and used by a positioning algorithm to determine the position of the mobile. This process is continued for as long as requested, to generate positions at certain time intervals, giving the mobile’s time varying position or trajectory. While there are obvious privacy issues with this type of system and any positioning technology [32], only the performance of such a system will be considered. Since the whole system cannot be implemented, the accuracy of the posi- tioning will be evaluated in simulation. However, to provide a more realistic performance metric, the error in the AOA measurements is determined from real MIMO indoor measurement data. A wireless channel measurement sys- tem developed by TR Labs Calgary is used that has four antennas, similar to the number expected in upcoming WLAN APs. The statistical properties of AOA estimates calculated using the measurements are then used in the posi- 11 Chapter 1. Introduction tioning simulation to gain insight into the operational system performance. Two different algorithms, a simple maximum likelihood (ML) and space- alternating generalized expectation-maximization (SAGE) [33], are tested to perform the estimation of the AOA on the measurement data. The posi- tioning simulation compares the positioning accuracy of both a least squares (LS) estimator and an extended Kalman filter (EKF) to come to conclusions about the performance of this type of system. 1.9 Contributions The following are the contributions of this thesis: • Characterization of AOA estimation performance in an indoor wireless environment using a simple ML technique and the SAGE algorithm. This is performed on real indoor channel measurements using a limited number of receive antennas, as is expected to be featured with future WLAN APs. • Evaluation of the effectiveness of direct path identification using ML and SAGE. • Determination of the overall positioning accuracy of AOA-based WLAN infrastructure through simulation by incorporating the AOA error statistics from the measurement generated AOA estimates. • Examination of the use of EKF over LS in improving the performance of AOA positioning. 1.10 Thesis Overview The first few chapters of this thesis cover the necessary theory behind both positioning and wireless channel characterization. Chapter 2 is an overview of general positioning methods and theory related to wireless positioning. It also contains descriptions of some current and past technologies. Chapter 3 follows with background to understand the effects of the indoor wireless 12 Chapter 1. Introduction environment. Included is a detailed description of the channel measurement system used to generate the data that was used to estimate the AOA of the received signal. The measurements and the environment in which they were taken are outlined. Chapter 4 describes the method by which the AOA of the transmitted signal is estimated from the channel measurement data. First, the received signal is modeled in terms of the transmitted signal and the channel pa- rameters. Using this signal model, the general channel parameter estima- tion algorithm SAGE, which is derived from the expectation-maximization (EM) algorithm, is described. The derivation of the EM algorithm from a strict ML algorithm is also presented. An ML algorithm specifically derived for estimating AOAs for positioning applications is described and the per- formance compared with SAGE. Implementation issues are addressed, such that practical and efficient implementation is possible. Finally the statistical AOA estimation performance of each algorithm for the various channel mea- surements is presented in the form of probability density functions (PDFs) calculated from histograms of the AOA error. In Chapter 5, the statistics of the AOA measurements are used in a po- sitioning simulation. The geometry of the AP placement is provided, and two positioning algorithms, LS and EKF, are discussed. They are then used with simulated positions and a user trajectory. The AOA error statistics presented in the previous chapter are incorporated to simulate noisy AOA estimates to determine the positioning accuracy of the system. The perfor- mance of the system is then generalized. This thesis concludes in Chapter 6 with a summary of the main findings, and future research opportunities. 13 Chapter 2 Positioning There are many different types of position determination, used for many different applications. In terms of modern technology, the most convenient and accurate positioning technologies are wireless. The ability to position an object is very valuable for many applications, and in some cases is absolutely necessary. Historically many significant wireless positioning technologies were ini- tially developed and used for military purposes. For example, GPS was developed and implemented by the United States Department of Defense. Government funding has led to significant advancements in the area of nav- igation technology. This chapter starts with an overview of positioning basics in section 2.1, describing briefly the different types of positioning and detailing positioning accuracy. The fundamental concepts and history of the positioning methods TOA, TDOA, AOA and RSS are then discussed in more depth in sections 2.2 through 2.5. 2.1 Positioning Methods There are three dominant positioning methods, each based on a different positioning measurement: time-based, direction-based and RSS. The time- based methods include TOA and TDOA positioning, which relate the time of propagation of the signal to a range or range difference. Direction-based methods determine user position through AOA measurements, or the di- rection of the mobile from the received signal. RSS measurement methods include fingerprinting and propagation modeling, which relate the strength of the received signal to the position of the user. The measurement quanti- 14 Chapter 2. Positioning ties are corrupted by noise and other distorting factors, so the measurements must be estimated from the signal. This process is called signal parameter estimation. In addition to these three basic techniques, others have been proposed as well. An interesting positioning method is direct position determination [34] which does not have intermediate positioning measurements, but determines the position directly from the received signals. Measurement-based methods such as TOA/TDOA and AOA estimate the measurements independently, even though the position of the user is common for all measurements. Direct position determination applies this constraint to more accurately determine user position. This is done by observing all of the received signals at the APs and choosing the mobile position that best matches those signals based on the propagation model. The search for the mobile position is a large multi-dimensional problem. Because of this, direct position methods are computationally complex, and currently not feasible for implementation. A significant amount of research has gone into hybrid techniques whereby different types of positioning measurements such as TOA and AOA [35]; or TDOA and AOA [36] are integrated to determine user position. The usage of different positioning measurements can allow for positioning with reduced numbers of APs, as shown in [37] using UWB signals and a single AP measuring AOA and TOA with decimeter level precision in a close range LOS environment. 2.1.1 Lines of Position For each positioning method, lines of position can be drawn which represent the potential positions of the mobile. The lines of position are different for each type of positioning measurement, and ideally lines of position from each AP intersect at only one point, which is the position of the mobile. In a real system, there isn’t a perfect single intersection due to errors in the measurements, so the position computed is an estimate of the actual mobile position. The lines of position are used to visualize the positioning methods. Example lines of position are shown for each positioning method 15 Chapter 2. Positioning later in this chapter. 2.1.2 Positioning Accuracy The accuracy to which a mobile can be positioned depends on several dif- ferent factors. Generally speaking these include the signal parameter esti- mation accuracy as well as the system geometry. Positioning accuracy is directly related to the signal parameter estima- tion accuracy. The signal parameter estimation is in turn dependent on the specifics of the hardware as well as the wireless environment. Harsher wire- less environments have more multipath which is discussed in Chapter 3. This distorts the signal that is received and causes the positioning measurements extracted to be less accurate. The system geometry, in terms of the relative placement of the APs with respect to the position of the mobile, has an effect on the positioning accuracy as well. This can be summarized in the form of dilution of precision (DOP). DOP roughly relates the error in the position to the error in the positioning measurements. A statistical amount of measurement error em is related to the expected statistical position error ep using those measurements by the corresponding DOP value ep = DOP · em. (2.1) Therefore the DOP has units of position unit per unit of measurement. For this study the positioning is in metres using AOAs, so the DOP has units of metres per radian. The DOP and therefore the positioning performance varies based on the positioning method [38], the geometry and the position error to be calcu- lated. DOP can relate the measurement error either a directional or non- directional positioning error. For instance, a directional position error could be the approximate error in the determination of the easting coordinate of the mobile, represented by the easting DOP (EDOP). Likewise, the northing DOP (NDOP) relates the measurement error to the approximate error in determining the northing coordinate of the mobile. A non-directional posi- 16 Chapter 2. Positioning tion error could be a circular measure such as the horizontal position error, where the horizontal DOP (HDOP) is used. Conceptually, DOP can be understood in terms of the lines of position. In directions where the overlap in the lines of position are greater, the DOP is larger and therefore the resulting position estimates are expected to be less accurate. This is shown in Figure 2.1. (a) Poor EDOP. (b) Good NDOP, good EDOP. (c) Poor NDOP. Figure 2.1: How DOP varies based on the intersection of the lines of position. How DOP values are calculated and how they vary based on geometry is discussed in section 5.4. 2.2 Time of Arrival Positioning TOA positioning involves the determination of the distance of the mobile from each AP by measuring the absolute propagation time of the signal. This first requires highly accurate time synchronization between all the transmit- ters and receivers, so that the total propagation time for the signal can be calculated. With the knowledge of the speed of propagation, the time be- tween transmission and reception can be converted into a distance or range measurement. Because of this, TOA positioning is also called ranging. Po- sitioning through the use of ranges is also referred to as trilateration. For 2D positioning, a minimum of three APs is required. Once the distance from each AP has been calculated, the lines of position can be drawn, an example of which is shown in Figure 2.2. The lines of position are circles at the measured ranges R1, R2 and R3 centered on the corresponding APs. TOA positioning generally has potential for high positioning accuracy. 17 Chapter 2. Positioning R1 R2 R3 AP 1 (x1, y1) AP 2 (x2, y2) AP 3 (x3, y3) Mobile (xm, ym) y x Figure 2.2: Example of circles of position for TOA-based positioning using three APs. This depends mainly on the transmitted signal and the capabilities of the receiver. The resolution with which the propagation time can be determined is determined by two factors: the bandwidth of the transmitted signal, and the sampling frequency at the receiver. The bandwidth is the limiting factor assuming that the sampling frequency is greater than the Nyquist rate. A large bandwidth signal allows for higher frequency components to exist in the signal, which enables sharper signal transitions. These transitions are detected to better determine propagation time. The best possible unbiased positioning variance is dictated mathemat- ically by the Cramér-Rao lower bound (CRLB). The CRLB in an NLOS situation is shown in [38] for the different positioning methods. The NLOS 18 Chapter 2. Positioning measurement error is modeled and expressions for the CRLB are derived. It is important to note that the CRLB of the position estimates for all positioning methods depend on the AP geometry. The CRLB for TOA positioning is inversely related to the SNR and signal bandwidth. That is to say, time based positioning techniques show improvements in positioning accuracy with large signal bandwidth, which is why UWB is becoming a popular choice in positioning research [39]. Increas- ing the SNR also improves positioning accuracy, which does not necessarily have to be accomplished by increasing the power of the transmitted signal. In a spread spectrum system where a sequence of higher frequency pulses is used to spread signal energy over a wider bandwidth, correlation is used to gather the signal energy and increase SNR. This is discussed further in section 3.3. 2.3 Time Difference of Arrival Positioning TDOA positioning is similar to TOA in that it uses the propagation time information to determine the user position. However, while the APs in the positioning infrastructure are time synchronized between each other, the mobile is not. When the received signal is used to calculate a range using the receiver clock, the range contains the bias between the transmitter and receiver clocks common to all the ranges. Therefore the range that can be calculated is called a pseudorange. The absolute range cannot be known due to the lack of receiver-transmitter synchronization. However, what is known about the user position is the dif- ference between the distances from different APs. Differencing the pseudor- anges removes the unknown time of transmission, or clock bias between the mobile and the APs, from the position calculation. Due to the additional information to be estimated, the clock bias, TDOA positioning requires one more AP than TOA positioning. Strictly speaking, TDOA positioning can be done in two ways, where the clock bias is estimated along with the position, as in the case of GPS; and where the transmission time differences are used to determine position. 19 Chapter 2. Positioning When the clock bias is estimated, the lines of position are similar to those of TOA, however the circles of position all have the same fixed radius change given by the clock bias. Since the clock bias is likely not initially known, there will be no common intersections of the circles, indicating no user posi- tion. Conceptually, the circles are all increased or decreased in radius by the same amount until the lines of position intersect appropriately. In the case where differencing is used, the lines of position for TDOA are hyperbolas, and this is why TDOA positioning is also known as hyperbolic positioning. An example of lines of position for a differencing TDOA system is shown in Figure 2.3. AP 1 (x1, y1) AP 2 (x2, y2) AP 3 (x3, y3) Mobile (xm, ym) y x Figure 2.3: Example of hyperbolas of position for TDOA-based positioning using three APs. In terms of positioning accuracy, similar accuracy to TOA is possible 20 Chapter 2. Positioning with all of the same limiting factors. NAVSTAR GPS is a common example of a clock estimating TDOA system. Additional methods exist to increase the precision of the time measurements beyond what the bandwidth sug- gests such as GPS carrier phase tracking which results in higher positioning accuracy [40]. For very weak spread spectrum signals, the SNR can be in- creased by observing the signal for longer periods of time. This enables the use of GPS indoors by extending correlation times to multiple periods of the training sequence. This recovers signal information that is buried in receiver noise. Historic examples of TDOA positioning systems include Gee developed by the British in World War II for aircraft navigation [41]; and the subse- quent American developed Long Range Navigation (LORAN) which sported greater operating ranges [42]. The most recent LORAN system, enhanced or eLORAN, is still in operation, but is infrequently used in favour of GPS. The CRLB for TDOA positioning shown in [38] shows the same relation- ship as TOA positioning between positioning performance, SNR and signal bandwidth. 2.4 Angle of Arrival Positioning AOA positioning, also called triangulation, is the determination of position by the use of knowledge of the angles between the mobile and the APs, or vice versa. This can be performed in different ways. Mechanically, a narrow directional antenna can be used to sweep in all directions of interest, and record the direction where the received signal is strongest. Since a mechan- ically operated antenna array is slow, energy inefficient, and impractical, another method may be more useful. A method of much interest, and the subject of this thesis, is the use of multiple antenna arrays. The additional propagation distance of the signal to each of the spatially separated anten- nas is used to determine the signal propagation direction. This appears in the demodulated received signal as a phase shift difference between signals received at different antennas. Positioning in two dimensions requires a minimum of two APs, however 21 Chapter 2. Positioning this results in very poor positioning near the line that is drawn connecting the APs. For a practical system to be able to position a user, a minimum of three APs are used. The lines of position for AOA positioning are simply lines from the mobile or AP in the direction of the AOA. An example of these lines of position is shown in Figure 2.4. AP 1 (x1, y1) AP 2 (x2, y2) AP 3 (x3, y3) Mobile (xm, ym) y x A1 A2 A3 Figure 2.4: Example of lines of position for AOA-based positioning using three APs. The positioning accuracy of an AOA system is usually inferior to that of a TOA system, especially when the infrastructure is at large distances from the mobile. The performance of AOA positioning degrades with greater dis- tances [38] between the APs and the mobile, which is intuitive. The CRLB shows that the best obtainable unbiased positioning accuracy is enhanced 22 Chapter 2. Positioning by increasing the spacing between the antennas in the receive array as well as the number of antennas and the signal SNR. This thesis investigates the performance with an antenna array with relatively few elements, to mimic future available WLAN APs and assess their positioning potential. The po- sitioning performance is improved with reduced distance between the APs and the mobile. When used over short distances, AOA-based positioning could provide reasonable accuracy. The configuration of the antenna array elements dictates the possible angles which are able to be estimated. For example, a linear monopole array contains ambiguity in the angles, since the side of the array from which the signal arrives is unknown. As well, a linear monopole array does not allow for the estimation of the elevation angle of the signal. AOA-based positioning systems have been used for navigation purposes, although not usually in a flexible manner, using fixed beamforming antenna arrays. For example, in World War II the Germans used several AOA-based technologies. Lorenz was used for navigating aircraft to proper fixed land- ing trajectories [43]. This type of technology was subsequently incorporated in Knickebein and later systems, used for accurate bombing of specific tar- gets. Due to the only recent usage of multiple antenna arrays in commercial systems, research indicates that there are few, if any, commercial purely AOA-based positioning systems. 2.5 Received Signal Strength Positioning RSS positioning encompasses several different positioning methods. All are based on recording of the power in the received signal. This is most useful when the extraction of other position measurements from the transmitted signal is difficult, usually due to the signal itself not being tailored for po- sitioning purposes. The signal strength of existing data signals is the most common usage of RSS positioning. Signals used in this manner are called signals of opportunity. These RSS measurements are typically used for po- sitioning in two different ways: propagation modeling and fingerprinting. Research has been split between fingerprinting and propagation modeling, 23 Chapter 2. Positioning where the higher positioning accuracy methods appear to favour fingerprint- ing. Propagation modeling mathematically translates the RSS measurements into ranges assuming some propagation model for the environment [16]. Af- ter the ranges have been calculated from the RSS measurements, the posi- tion is calculated in the same manner as TOA. The positioning accuracy of this method is mostly dependent on how well the propagation model esti- mates the range from the RSS, in the environment where the system is to be deployed and on the hardware on which it is implemented. Fingerprinting has been the focus of much research and involves creating a map of the RSS from different APs. The possible positions of the user are surveyed, and at each position the RSS from each AP is recorded in the map. The position of a user is determined by finding the best match on the map for the RSS measurements observed by the user. The efficient determination of the best match is the focus of current research and the methods include simple Euclidean distance [44], neural networks [17], and kernels [15] among others [45, 46]. RSS positioning is less accurate than time-based positioning, although for fingerprinting it depends on the granularity with which the map is gen- erated, and for propagation modeling it depends on the modeling accuracy. Fingerprinting is more robust since it accounts for the effects of multipath. Also interesting is that [38] shows that the CRLB of the position estimates does not depend on anything that can be manipulated by the system de- signer except for the AP geometry and the distance of the mobile from the APs. The factors that are not controllable are the fading and path loss prop- erties of the wireless channel. This means that a system using RSS methods has the fewest available free parameters to improve positioning performance. 24 Chapter 3 The Indoor Wireless Channel This chapter contains background about the indoor wireless channel and details the distortion of wireless signals. The background of the effect of the wireless channel in terms of multipath is described in section 3.1. Properties of the multipath in wireless channels are presented in section 3.2. To un- derstand how the wireless channel affects AOA estimation, MIMO measure- ments were collected. The configuration and specifics of the measurement setup as well as how measurements are used to characterize multipath are found in section 3.3. The specifics of the measured environment and the measurements themselves follows in section 3.4. 3.1 Multipath and the Channel Impulse Response The indoor wireless environment consists of densely packed objects which absorb, reflect and scatter transmitted signals. This is similar to that of the outdoor wireless environment, but the objects are situated closer to the wireless devices and are more numerous. Therefore the number of reflections is higher, and due to the proximity of the transmitter and receiver, the propagation time for each is low. At the receiver, many different copies of the transmitted signal are received, at different times and from different directions. Each copy is called a multipath arrival. A typical concern for data transmission is that these copies, when super- imposed upon reception, can cause significant reductions in signal strength by adding destructively. This phenomenon is called fading, and is most se- vere for narrowband signals. This loss of signal results in interruptions in 25 Chapter 3. The Indoor Wireless Channel the transmission of data, and therefore the lost data must be requested and sent again. This reduces the data throughput of the system. A solution to multipath for data transmission is to leverage diversity. The fading of the signal due to destructive multipath interference is differ- ent for different positions of the receive and transmit antennas. Therefore MIMO systems can be used to counteract the fading phenomenon. By us- ing antennas separated spatially, each experiences different multipath fading, and the probability of all the antennas experiencing simultaneous fades is lowered. The signals received by each of the antennas can then be combined to increase the SNR over that of an equivalent system equipped with only a single antenna. The multipath component that follows the direct path between trans- mitter and receiver will not necessarily have the highest receive power, since a strong reflection could have higher amplitude than an attenuated direct path. The direct path signal will have arrived at the earliest delay how- ever, but its detection is not guaranteed. A direct path signal may not even exist depending on the environment. Finding the direct path is important for accurate AOA estimation. The effectiveness and probability of correctly detecting and identifying the direct multipath arrival will be evaluated by processing the MIMO channel measurements described later in this chapter. The effect of the wireless channel can be described mathematically by its channel impulse response (CIR). The received signal r (t) is defined as the convolution between the transmitted signal s (t) and the CIR h (t), in the same way as any other linear time invariant system r (t) = h (t)⊗ s (t) . (3.1) The CIR is described in terms of the L different copies of the transmitted signal that arrive at a receive antenna h (t) = L∑ l=1 αlδ (t−∆tl) (3.2) where αl is the complex amplitude of the received signal for path l, δ(t) 26 Chapter 3. The Indoor Wireless Channel is the Dirac delta function and ∆tl is the time between transmission and reception for path l. The delay ∆tl can be expressed as a function of the distance that the signal travels from transmitter to receiver dl where c is the speed of light ∆tl = dl c . (3.3) 3.2 Properties of the Wireless Channel Indoor wireless channels differ from those of outdoor wireless channels. These differences are related to the multipath in the channel and the ar- rival of those multipath components with respect to time and direction. Two important concepts, delay spread and angle spread, play a large role in the ability to use a wireless signal for positioning. An example of the arrivals in an indoor multipath channel, in terms of the parameters of each arrival, is shown in Figure 3.1. Each multipath arrival has different amplitude, delay and AOA. 3.2.1 Delay Spread and Time Density The delay spread of a wireless channel is a measure of how multipath arrivals are spread out in time. For an outdoor wireless channel, the delay spread is large since the propagation distances are typically large, on the order of microseconds of propagation time. However, for an indoor wireless channel, the delay spread is smaller. An example of multipath delays estimated from indoor wireless channel measurements is shown in Figure 3.2. There are different ways of calculating delay spread, such as the difference in delay between the longest and shortest propagation paths [47]. Calculated in this way, this example has a delay spread of approximately 140 samples, which at 2 GS/s translates to 70 ns delay spread. While all wireless channels experience multipath, their differences in de- lay spread often lead to differences in what will be referred to here as time density. Time density is a measure of the number of multipath arrivals per unit time. In an outdoor channel the time density is generally lower, since 27 Chapter 3. The Indoor Wireless Channel Figure 3.1: Example multipath in an indoor wireless channel in terms of amplitude, delay and AOA. the arrivals are spread out in time and indoor channels have higher time density, due to the short propagation distances. The impact of this time density is on the identification of each of these arrivals in time. As the time density increases, the time between arrivals decreases and therefore it is more difficult to distinguish one multipath ar- rival from others. Depending on the signal bandwidth, the time resolution may cause the multipath arrivals to be inseparable in terms of delay. 3.2.2 Angle Spread The angle spread of a wireless channel is a measure of the distribution of the AOAs of the multipath arrivals at an antenna array. An outdoor wireless channel typically has low angle spread. In situations of long distance be- tween transmitter and receiver, it can be less than 10◦ [48]. Indoors the angle 28 Chapter 3. The Indoor Wireless Channel 0 20 40 60 80 100 120 140 160 0 0.5 1 1.5 x 10−3 Delay (samples) Am pl itu de Figure 3.2: Example of amplitudes at various delays in an indoor wireless channel. spread is usually larger. For example the 802.11n channel model assumes an angle spread standard deviation of between 15◦ and 50◦ [49]. Example AOAs estimated from measurement data for an indoor wireless channel are shown in Figure 3.3. The angle spread in this example, if defined simply as the range of angles that exist in the channel, is approximately 100◦. 3.3 Channel Sounding System The effect of the indoor wireless channel on the transmitted signal was char- acterized using a wideband spread spectrum channel sounding system. The system used for this research was developed by TRLabs Calgary, and con- sisted of a single matched transmitter and receiver [50]. The transmitter and receiver each had a four antenna linear monopole array, used to transmit and receive a periodic signal at a carrier frequency of 5.66 GHz. The IEEE 802.11n standard operates at a similar frequency of near 5 GHz [9]. This system allows for the determination of 16 spatially diverse channel impulse responses, one for each combination of transmit and receive antenna. The periodic spread spectrum signal transmitted is a pseudorandom 29 Chapter 3. The Indoor Wireless Channel 0 20 40 60 80 100 120 140 160 180 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 x 10−3 AOA (degrees) Am pl itu de Figure 3.3: Example of AOAs at various delays in an indoor wireless channel. noise (PN) sequence with 2047 binary values or chips. Each chip has a value of 1 or -1. The PN sequence used has the property that it correlates with itself at offsets of multiples of the sequence length with a value equal to the sequence length, and is -1 at all other offsets. This is similar to noise, and the correlation property makes it a good choice for channel characteriza- tion since it allows for the estimation of the CIR. The benefit of using these signals is the ability to increase the SNR of the received signal by extending the correlation of the PN sequence over multiple periods of the sequence. The autocorrelation of a PN sequence of length K is shown in Figure 3.4. The training symbols in a WLAN signal preamble can be used in a similar manner to this PN sequence. The training symbols are already used for channel parameter estimation [13]. Most will have fewer chips than the number used in this system, however the effect of fewer chips can be approximated by the reduction in the SNR of the signal captured by the measurement system. 30 Chapter 3. The Indoor Wireless Channel a(t) t K -1 Figure 3.4: Autocorrelation of PN sequence of length K as a function of sequence offset t. 3.3.1 Antenna Array The transmit and the receive antenna arrays are identical, consisting of a linear array of four separate monopole antennas located along a sliding track in a truncated ground plane as shown in Figure 3.5. The use of a four element array is similar to what is expected from future WLAN APs. The antennas are set with a separation of 2.6cm corresponding to half wavelength of the 5.66 GHz carrier frequency. The antennas have been tuned for operation at 5.66 GHz with a usable bandwidth of several hundred MHz. The antenna arrays for both the transmitter and receiver are at the same height above the floor, approximately 1.5 m. 3.3.2 Transmitter The transmitter consists of two arbitrary waveform generators (AWGs) with two independent outputs each, capable of generating a signal based on a sampling rate of 1 GS/s. The AWGs are all synchronized to the same clock source such that 4 pseudo-orthogonal baseband PN sequences are generated, one for each transmit antenna channel. Pseudo-orthogonality is assured by using staggered code delays of 414 chips between the transmitted PN code sequences. For example, the second transmit antenna transmits the same signal as the first antenna but cyclically shifted by 414 chips. Each 31 Chapter 3. The Indoor Wireless Channel Figure 3.5: Photo of the four-antenna linear monopole array used for trans- mission and reception. subsequent antenna experiences an equal additional shift. The amount of shift between the transmitted signals is larger than the expected delay spread of the system, and the phase shift between the fourth and first transmitted PN sequences is 805, so that the CIRs can all be uniquely identified. The ideal received signal from all transmit antennas at a single receive antenna after correlation with the transmit sequence is shown in Figure 3.6. The shift between the transmitted copies of the PN sequences is demonstrated. The modulated signals are PN codes based on a 2047 maximum length sequence passed through a root raised cosine filter with an excess bandwidth of 0.4. The chipping rate of 200 MHz results in an approximate two-sided bandwidth of 300 MHz. Each of the four signals is upconverted to 5.66 GHz carrier frequency using a common local oscillator (LO). A simplified block diagram is shown in Figure 3.7 and a picture of the transmitter in Figure 3.8. The power transmission level of 10 dBm is well within the linear range of the transmitter amplifiers to avoid compression issues. 32 Chapter 3. The Indoor Wireless Channel t C(t) t0 t0 + 414 t0 + 828 t0 + 1242 TX1 TX2 TX3 TX4 Figure 3.6: Ideal received signal from all transmit antennas after correlation with the transmit sequence. 3.3.3 Receiver The receiver is built around a 4 channel 20 GS/s LeCroy WavePro 7300 digital oscilloscope. The block diagram of the complete receiver is given in Figure 3.9. Figure 3.10 is a photo of the receiver equipment. The received signals at the output of the four antennas are filtered to remove out of band noise, amplified and then downconverted to an intermediate frequency of 500 MHz. The intermediate frequency signal is then amplified and filtered once more before sampling. The signal sampling consists of accumulating 50 000 samples at a 2 GS/s for each of the four received signals. This data is recorded by the Matlab scope application code and written to disk, along with setup information. The transmitter does not provide a synchronization signal to the receiver, so only relative timing in the received signal can be discerned. 3.3.4 Equipment Calibration Testing delay, phase and power differences between the receive chains is im- portant for AOA estimation since those differences cause errors in the signal model used in the estimation process. The signal to one of the transmit antennas was directly connected using a power splitter to all of the receive 33 Chapter 3. The Indoor Wireless Channel AWG #1 AWG #2 LPF LPF LPF LPF CH 1 CH 2 CH 1 CH 2 Clock Source Trigger Mixer Mixer Mixer Mixer 5.66 GHz Local Oscillator Power Splitter Amplifier Amplifier Amplifier Amplifier BPF BPF BPF BPF Baseband Radio Frequency 5.66 GHz TX1 TX2 TX3 TX4 Figure 3.7: Hardware configuration for the transmitter. Figure 3.8: Photo of the transmitter equipment. 34 Chapter 3. The Indoor Wireless Channel LPF LPF LPF LPF Mixer Mixer Mixer Mixer 5.16 GHz Local Oscillator Power Splitter Amplifier Amplifier Amplifier Amplifier BPF BPF BPF BPF 500 MHz Intermediate Frequency Radio Frequency 5.66 GHz Amplifier Amplifier Amplifier Amplifier Digital 2 GS/s Sampling Oscilloscope RX1 RX2 RX3 RX4 Figure 3.9: Hardware configuration for the receiver. Figure 3.10: Photo of the receiver equipment. 35 Chapter 3. The Indoor Wireless Channel antennas using cables as shown in Figure 3.11. Attenuation of 60 dB was necessary due to the high transmit power saturating the receive amplifiers. The splitter used has a frequency range of up to 5.8 GHz, adequate for the transmitted signal. Scope captures were taken at the same time on all four channels in the same manner as regular channel measurements. Once the calibration captures have been recorded, the relative power and phase differences between the receive antenna signals are corrected when the measurement data is processed. This is especially important for AOA mea- surement where both the phase and power differences are used to estimate the direction. From TX1 BPF Power Splitter 60 dB Attenuator To RX1 BPF To RX2 BPF To RX3 BPF To RX4 BPF Figure 3.11: Configuration for relative phase and amplitude calibration be- tween the receiver channels. 3.3.5 Channel Impulse Response Estimation The estimated CIR for the channel between a transmit antenna and receive antenna m is hm (t). It is recovered by correlating the received signal ym (t) with the transmitted pulse shaped PN sequence u (t) hm (τ) = ∫ ym (t)u (t+ τ) dt. (3.4) This is possible by approximating the autocorrelation of the PN sequence with a delta function. Since the received signal is the convolution of the CIR with the transmitted sequence ym(t) = hm(t)⊗ u(t), (3.5) 36 Chapter 3. The Indoor Wireless Channel the correlation of the received signal with the transmitted sequence is ym(t) u(t) = (hm(t)⊗ u(t)) u(t). (3.6) The correlation and convolution operations are linear and can be reordered. The correlation operation is performed first. Since u(t) u(t) is the auto- correlation of the transmitted sequence a(t) ym(t) u(t) = hm(t)⊗ a(t). (3.7) Therefore if a(t) can be approximated as δ(t), such as in the case when the transmitted sequence is a PN sequence, then ym(t) u(t) ≈ hm(t). (3.8) This estimated CIR is used wherever the CIR is required in the AOA estimation. For estimation purposes, the estimated CIR is assumed to be corrupted with an independent complex circular Gaussian noise process at the receiver. After the received signal has been correlated with the transmitted pulse shaped PN sequence, the CIRs corresponding to each of the transmit anten- nas are required to be separated. This is done by detecting the four groups of peaks that correspond to the CIRs for each of the transmit antennas. The additional 805 chip spacing after the fourth antenna transmit signal before the repeated signal from the first antenna allows for unique identification of each. An example of an estimated channel impulse response is shown in Figure 3.12. 3.4 Indoor Channel Measurements The MIMO channel sounding system was used to characterize the indoor environment of the Information and Communications Technology building at the University of Calgary. The measurements were taken in the under- graduate labs on the third floor. Three different kinds of measurements 37 Chapter 3. The Indoor Wireless Channel 0 50 100 150 200 250 300 0 100 200 300 400 500 600 700 800 900 Time (ns) M ag ni tu de Figure 3.12: Example CIR generated from a channel measurement. were taken to represent the different situations of separation between the receiver and transmitter. Sets of measurements were taken with the trans- mitter and receiver in LOS, with a single wall obstructing the direct path, and with two walls obstructing the direct path. The map of the locations of the transmitter and receivers are shown in Figure 3.13. The building was a concrete structure with gyprock walls and a 10 ft ceiling. The labs were equipped with sparse equipment such as lab benches and computers. Occasionally people were moving within the vicinity of the measurement equipment. All doors shown in the map were closed during measurement capture. The placement of the transmitter and receiver from the map for the dif- ferent indoor situations can be found in Table 3.1. The positions of the transmitter and receiver along with the orientations of the antenna arrays were assured by surveying points on the floor using a total station, a pre- cise optical positioning instrument offering millimeter level precision. The transmitter and receiver antenna arrays were positioned on these points us- ing a plumb-bob. To ensure proper facing of the antenna arrays, one point on either side of the antenna array was surveyed and positioned above the points on the floor. The points on the antenna array were about 40 cm 38 Chapter 3. The Indoor Wireless Channel Scale 2.5 m Legend Wall Window Wooden Door Transmitter Location Receiver Location TX1 TX2 RX1 RX2 RX3 Figure 3.13: Map of University of Calgary Information and Communications Technology building third floor with receiver and transmitter positions. apart. Measurements were taken with the antenna arrays directly facing each other, as well as with the receive antenna array rotated by 45◦. The combination of surveying and positioning of the antenna arrays in- troduces some error into the AOAs. The surveying and placement of the points on the antenna arrays over the marks on the floor is assumed to have a total position error of about 3 mm. Error in the position of the trans- mit antenna array, caused when the error in the position of the transmit antenna array is perpendicular to the direction of the receiver, results in AOA error of less than 0.02◦ for a separation distance between transmit- ter and receiver of 9 m and is considered negligible. The worst case error, which occurs upon maximum rotational error of the receive antenna array, 39 Chapter 3. The Indoor Wireless Channel is approximately 0.9◦. Table 3.1: Transmitter and receiver locations for the various indoor mea- surement situations. Measurement Situation Transmitter location Receiver location LOS TX2 RX3 Single wall TX1 RX1 Double wall TX1 RX2 In each combination of measurement situation and receive antenna array rotation, 15 measurement files were recorded. Each measurement file was separated by about five minutes, and consists of 50 time separated individual signal captures. The time separation between digital signal captures was several seconds. Each signal capture consists of 50 000 digital samples, enough to record just over two full periods of the transmitted PN sequence. This allows for 3000 CIRs to be calculated for each measurement situation- rotation combination, and therefore 3000 estimated AOAs. The transmit power was adjusted in each measurement situation for received SNR of approximately 30 dB. The transmit power was selected such that adequate signal was received while low enough such that the signal did not saturate the amplifier at the receiver and cause clipping of the signal. The approximate SNR for each of the different measurement scenarios is shown in Table 3.2. It is important to recognize that the signal strength of the system used in this study is slightly higher than a typical WLAN system. The SNR of a WLAN system can be as low as 20 dB [51]. Table 3.2: Approximate SNR for the various indoor measurement situations. Measurement Situation Approximate SNR (dB) LOS 25 Single wall 30 Double wall 25 40 Chapter 4 Angle of Arrival Estimation Many different algorithms exist to estimate the parameters in a wireless channel [52]. Popular methods include the superresolution algorithms such as multiple signal classification (MUSIC) [53] which is a spectral subspace method using eigendecomposition of the received signal estimated covariance matrix; and estimation of parameters via rotational invariance techniques (ESPRIT) [54], a subspace-based technique that divides the antenna array into several sub-arrays. Other algorithms include Matrix Pencil [25, 55] and ML derived algorithms [33, 56]. This chapter contains the derivation and evaluation of the algorithms that are used to perform channel parameter estimation and determine the AOA of the mobile from channel measurements. Firstly the signal model that the algorithms use is described in section 4.1, followed by the theoreti- cal best estimation performance in section 4.2. Two different algorithms are implemented in Matlab and evaluated, both based on ML classical estima- tion principles. The first is the SAGE algorithm, described in section 4.3, which estimates multiple spatially and temporally separated signals arriving at the receiver. The second is presented in section 4.4 and is a simple ML estimator which attempts to choose the earliest detected signal arrival and determines the direction for only that arrival. The algorithm performance is then summarized in terms of the ability of the algorithms to identify and estimate the direct path AOA from the channel measurements. The perfor- mance evaluations of the ML and SAGE algorithms are contained in sections 4.5 and 4.6 respectively. The chapter concludes with some AOA estimation performance generalizations in section 4.7. 41 Chapter 4. Angle of Arrival Estimation 4.1 Signal Model This section describes the mathematical models of the transmitted and re- ceived signals as functions of the following channel parameters: complex amplitude, delay and angle. The propagation of the signal is assumed to be confined to the horizontal plane, the elevation of the multipath arrivals is ignored. This is appropriate for outdoor environments where elevation angles may be low, as well as due to the inability of the linear antenna ar- ray to allow for elevation estimation. In an indoor environment the signals may have significant elevation, and the use of this signal model may cause errors in the channel parameter estimates. The signal model is used by the algorithms to estimate the properties of the wireless channel and received signal. The transmitted signal u(t) is a periodic pulse shaped PN sequence with K chips as described in section 3.3.2. The power of u(t) is Pu. Given a linear antenna array oriented parallel to the 2D y-axis with M total antennas spaced apart at half of the carrier wavelength λ2 , the location in [x, y] of the mth antenna (numbered starting at 1) is rm = [ 0, (M−2m+1)λ4 ] . A diagram of the antenna array and the arriving signal for multipath l is shown in Figure 4.1. The transmitted signal propagates and arrives at the antenna array via L different paths. It is assumed that the signal from each path arrives at all the antennas in the array, which is a simplification that can be justified given the relatively small size of the antenna array. The propagation time of the wave within the antenna array is assumed to be negligible relative to the sampling of the received signal, so that the additional distance travelled by the signal to each subsequent antenna appears only in the phase of the received signal. Finally, the signal of a single arrival is considered to be parallel at each receive antenna, which is justified assuming that the size of the antenna array relative to the distance from the source or reflector is very small. The contribution of the lth multipath arrival to the received signal at antenna m is sm(t;θl) = cm(φl)αlu(t− τl) (4.1) 42 Chapter 4. Angle of Arrival Estimation λ 2 φlm = 1 2 3 4 Multipath arrival lOrigin x y Figure 4.1: Diagram of the arriving signal for multipath component l at the four element linear monopole array. where cm(φ) = fm(φ) exp ( j2pie(φ)•rm λ ) and the vector of parameters of the lth arrival is θl = [τl, φl, αl]. These are respectively the relative delay, angle of arrival, and complex magnitude of the lth multipath arrival. The unit vector pointing in the direction φ is e(φ), and fm is the electric field pattern of antenna m, which for an omnidirectional antenna fm = 1, ∀m. This is slightly different from the signal model in [57] since the effects of Doppler frequency shift are assumed negligible. The total signal received by the mth antenna, the superposition of all L multipaths, is therefore Ym(t) = L∑ l=1 sm(t;θl) + √ N0 2 Nm(t) (4.2) where Nm(t) is complex white Gaussian noise independent with respect to each antenna with unit spectral height in the independent real and imaginary components. A positive constant N0 denotes the power of the receiver noise. The channel measurements were taken when the actual AOA of the direct 43 Chapter 4. Angle of Arrival Estimation path signal φ was 90◦ and 45◦. 4.2 Cramér-Rao Lower Bound The best possible unbiased estimation variance of the parameters is deter- mined by the CRLB. The CRLB is calculated in the case where there is one multipath arrival. Using the signal model (4.1), with L = 1, the signal model can be summarized as Y (t;θ) = s (t;θ) + √ N0 2 N (t) (4.3) where Y (t;θ) = [Y1 (t;θ) , ..., YM (t;θ)]T , s (t;θ) = [s1(t;θ), ..., sM (t;θ)]T and N (t) = [N1 (t) , ..., NM (t)]T . The PDF assuming N (t) is a complex white gaussian noise process is p (Y,θ) = 1 piN0 exp [ − 1 N0 |Y(t)− s(t;θ)|2 ] . (4.4) The CRLB is calculated as the diagonal terms of F−1 (θ) where F is the Fisher information matrix (FIM) [58]. The element at the kth row and k′th column of the FIM is given by Fk,k′ (θ) = −E { ∂ ∂θk ∂ ∂θk′ ln (p (Y,θ)) } . (4.5) As shown in [57] Fk,k′ (θ) = 2 N0 < {∫ ∂ ∂θk sH (t;θ) ∂ ∂θk′ s (t;θ) dt } . (4.6) The CRLB for the delay is derived using (4.6) Fτ,τ (θ) = 2 N0 < {∫ ∂ ∂τ sH (t;θ) ∂ ∂τ s (t;θ) dt } . (4.7) 44 Chapter 4. Angle of Arrival Estimation This expands to Fτ,τ (θ) = 2M |α|2 N0 ∂2 ∂τ2 ∫ u∗(t− τ)u(t− τ)dt (4.8) using the signal model (4.1). Since the delay in this case is with respect to the transmitted sequence, τ = 0 and the Fisher information is Fτ,τ (θ) = 2M |α|2 N0 ∂2 ∂τ2 a(τ)|τ=0 (4.9) where a(τ) is the autocorrelation function of the transmitted sequence. The CRLB for the delay is CRLBτ = [Fτ,τ (θ)]−1 = N0 2M |α|2 ∂2 ∂τ2 a(τ)|τ=0 . (4.10) The CRLB for the AOA is derived in the same manner using (4.6) Fφ,φ (θ) = 2 N0 < {∫ ∂ ∂φ sH (t;θ) ∂ ∂φ s (t;θ) dt } (4.11) which expands to Fφ,φ (θ) = 2|α|2Pu N0 ∂ ∂φ cH(φ) ∂ ∂φ c(φ) (4.12) where c(φ) = [c1(φ), ..., cM (φ)]T = j2piλ cosφm. For a uniform linear array spaced at λ2 , m = λ 2 [ (M+1) 2 − 1, ..., (M+1)2 −M ]T . Therefore (4.12) can be expanded to Fφ,φ (θ) = 2|α|2Pu N0 ( j2pi sinφ λ mT )( −j2pi sinφ λ m ) . (4.13) The final expression for the Fisher information is Fφ,φ (θ) = pi2 sin2 φ|α|2Pu 2N0 M∑ m=1 (M − 2m+ 1)2. (4.14) 45 Chapter 4. Angle of Arrival Estimation The CRLB is the AOA is then CRLBφ = [Fφ,φ (θ)]−1 = 2N0 pi2 sin2 φ|α|2Pu ∑M m=1 (M − 2m+ 1)2 . (4.15) The CRLB for the amplitude is determined in the same manner as the delay and AOA. The derivation is straightforward and results in the Fisher information Fα,α (θ) = 4MPu N0 . (4.16) The resulting CRLB for the amplitude is CRLBα = [Fα,α (θ)]−1 = N0 4MPu . (4.17) The CRLB shows some very important information about the expected accuracy of the AOA estimates. As would be expected the estimation per- formance is related to the amount of receiver noise which is specified by N0, with lower variance and thus better estimation accuracy as the amount of noise decreases. More importantly, for a linear antenna array, the estimation accuracy is affected heavily by the number of antennas in the receive array as well as the AOA of the signal. For the best AOA estimation performance the system should use as many antennas as possible and the signal should broadside the antenna array. The number of antennas is limited practically in terms of the additional computation required to process additional signals as well as the space and cost required to build the array. Since 802.11n WLAN infrastructure is the target hardware for this positioning system, the limit of the number of antennas is set by the number of antennas on an 802.11n AP, which can be as many as four. In addition, as the physical size of the array increases, the assumption that the antenna array size is significantly smaller than the distance from the wireless signal source ceases to hold and results in large errors in the signal model. The bandwidth of the signal being used to estimate AOAs has a po- tentially large effect on the estimation performance. As shown from the 46 Chapter 4. Angle of Arrival Estimation CRLBs, the delay depends on the curvature of the autocorrelation function of the transmitter signal ∂ 2 ∂t2 a(t)|t=0. This curvature is determined by the bandwidth of the signal used. A larger bandwidth signal allows for better time resolution of multipath arrivals, and therefore better estimation per- formance. The CRLBs assume that the other channel parameters for an arrival have no effect on the estimation performance of the others. However, practical use in AOA positioning dictates that they can have large effects on the estimation performance. For instance, the delay must be determined closely for the direct path arrival, or the AOA estimated will be in error. Since the delay estimation is affected by the bandwidth of the signal used, the AOA is affected as well. With interest in the potential use with 802.11n WLAN APs, the ap- propriate bandwidth for those signals was used from the measurement data during the AOA estimation process. This means that a positioning system of this type could use the data signals as signals of opportunity to facilitate positioning as opposed to sending additional signals into the wireless chan- nel for the sole purpose of positioning. Devices conforming to the 802.11n standard can operate in one of two modes, with bandwidth of 20MHz or 40MHz [9]. For this research 40MHz was used to gauge the best case sce- nario positioning performance. The signals were also used with the full available bandwidth to investigate the effects of the bandwidth reduction on the estimation performance. 4.3 General Channel Parameter Estimation Many different algorithms exist for channel parameter estimation. Most are for general use to determine the various properties of a wireless channel. These properties include the amplitude, delay and AOA of multipath ar- rivals in that channel. These properties can be used to perform channel equalization [59] or to understand the statistical properties of various envi- ronments such that systems can be developed to more effectively operate in those situations. They also have uses in positioning, but may not be well suited for that application. 47 Chapter 4. Angle of Arrival Estimation The SAGE algorithm was chosen to study the effectiveness of a general channel parameter estimation algorithm for use in AOA-based positioning. It was chosen due to its derivation from proven ML techniques, and its proven effectiveness in channel parameter estimation [57]. It is a simplifica- tion on a EM estimator [56], which in turn is formulated from a true ML estimator. The progressive derivation of the SAGE algorithm is shown in this section. 4.3.1 Maximum Likelihood Channel Parameter Estimation ML estimation is based upon finding the parameters which maximize the PDF given the observed data. For channel parameter estimation, this is further complicated by the fact that it is not known ahead of time how many significant multipath arrivals are present. This number can either be estimated or set to some number which should allow for characterization of all dominant arrivals. The PDF for a circular complex Gaussian with independent components [a, b] (each with variance σ2) for the real and imaginary components respec- tively is defined as p(a, b) = 1 2piσ2 exp [ − 1 2σ2 ( (a− µa)2 + (b− µb)2) )] (4.18) which can be simplified by considering the random variable as a complex one in which x = a+ bj and therefore µ = E{x} = µa + jµb giving p(x) = 1 2piσ2 exp [ − 1 2σ2 |x− µ|2 ] . (4.19) This can be applied to our observed CIRs, using the signal model in (4.2) with the knowledge that E{Ym(t)} = L∑ l=1 sm(t;θl) (4.20) since Nm(t) is a zero mean noise process. The resulting PDF is parametrized 48 Chapter 4. Angle of Arrival Estimation by the channel parameters for all the arrivals θ = [θ1, . . . ,θL] p(Y(t);θ) = 1 piN0 exp − 1 N0 ∣∣∣∣∣Y(t)− L∑ l=1 s(t;θl) ∣∣∣∣∣ 2 (4.21) where Y(t) = [Y1(t), . . . , YM (t)] is the vector of received signal values and s(t;θl) = [s1(t;θl), . . . , sM (t;θl)] is the vector of signal contributions to all receive antennas for arrival l. Given that |b|2 = bHb, this can be expanded to p(Y(t);θ) = 1 piN0 exp − 1 N0 ( Y(t)− L∑ l=1 s(t;θl) )H ( Y(t)− L∑ l=1 s(t;θl) ) . (4.22) This simplifies further to give the following log-likelihood function Λ(Y(t);θ) by taking the natural logarithm of (4.22) then factoring and discarding terms which do not depend on the channel parameters and hence do not affect maximization of this function Λ(Y(t);θ) = 2< { L∑ l=1 s(t;θl)HY(t) } − ∣∣∣∣∣ L∑ l=1 s(t;θl) ∣∣∣∣∣ 2 . (4.23) In matrix notation where S(t;θ) = ∑L l=1 s(t;θl) is the vector of all mul- tipath signal contributions, this can be generalized to Λ(Y(t);θ) = 2<{S(t;θ)HY(t)}− |S(t;θ)|2 . (4.24) Since the parameters are assumed to be independent of time in a sta- tionary (non-time-varying) channel then the function is integrated over D◦, an integer number of periods of the PN sequence, to remove the time de- pendency, and the log likelihood function is now Λ(θ; Y) = 2 ∫ D◦ <{S(t;θ)HY(t) dt}− ∫ D◦ |S(t;θ)|2 dt. (4.25) The maximum likelihood estimate of the parameters is the set of param- 49 Chapter 4. Angle of Arrival Estimation eters θ̂ given observed data Y(t) θ̂ = argmax θ {Λ(θ; Y)} . (4.26) This requires a large amount of computation to maximize for large numbers of arrivals L, as the maximization is approximately a 3L dimensional prob- lem. It can be shown that this can be reduced to a 2L dimensional problem, since the complex amplitude can be written as a function of the other two channel parameters for each multipath arrival as shown in the next section. 4.3.2 Expectation-Maximization Channel Parameter Estimation The EM algorithm [56] is an iterative approach that simplifies an ML esti- mator using the knowledge that the parameter estimation process would be easier with all of the complete data, which are the individual signals received for each multipath arrival. The complete data allows for the estimation of a complete set of parameters without knowledge of any of the parameters from other signals. The complete data is unavailable as all of the multipath signals are added together to form the received signal, called the incomplete data. The complete data is unobservable and the incomplete data is ob- servable. The complete data xl(t) is related to the incomplete data Y(t) Y(t) = L∑ l=1 xl(t). (4.27) The complete data with noise for an arrival l is defined as xl(t) = s(t;θl) + √ N0 2L Nl(t) (4.28) where Nl(t) is a vector of independent complex white Gaussian noise se- quence with unit variance. The noise in the set of complete data is a de- composition of the noise in the incomplete data. The EM algorithm has two distinct steps. There is an expectation step, which is followed by a maximization step. This is repeated until convergence 50 Chapter 4. Angle of Arrival Estimation is achieved, such that all parameters have been estimated. The expecta- tion step is the estimation of the complete data given previously estimated channel parameters, and the maximization step generates new parameter estimates based on these complete data estimates. The formulation of the log-likelihood function follows similarly from that of the incomplete data given in the ML section Λ(θl; x̂l) = 2 ∫ D◦ <{sH(t;θl)x̂l(t)} dt− ∫ D◦ |s(t;θl)|2 dt. (4.29) The expectation step, also called signal decomposition, estimates the complete data using previously estimated channel parameters θ̂ = [ θ̂1, . . . , θ̂L ] and the observed incomplete data Y(t), and is x̂l(t; θ̂) = s(t; θ̂l) + Y(t)− L∑ p=1 s(t; θ̂p) . (4.30) The maximization step maximizes the log likelihood function (4.29) to generate new parameter estimates given a complete data estimate θ̂l = argmax θl {Λ(θl; x̂l)} . (4.31) The complex amplitude is a closed form function of the other two channel parameters. Thus, the estimates of the delay and angle are[ τ̂l, φ̂l ] = argmax [τ,φ] {|z(τ, φ; x̂l)|} (4.32) and the amplitude is calculated from them as α̂l = 1 I ∣∣∣c(φ̂l)∣∣∣2 TuPu z ( τ̂l, φ̂l; x̂l ) . (4.33) I is the length in periods of the PN sequence included in the received signal, 51 Chapter 4. Angle of Arrival Estimation Tu is the period of the PN sequence, c(φ) = [c1(φ), . . . , cM (φ)] , and z(τ, φ; x̂l) = c(φ)H ∫ D◦ u(t− τ)∗x̂l(t) dt. (4.34) This is recognizable as beamforming. The algorithm process is as follows: 1. Initialize: Initialize all channel parameter estimates. 2. Expectation Step: Perform signal decomposition (4.30) with the cur- rent parameter estimates to obtain complete data signal estimates for all arrivals, x̂1, . . . , x̂L. 3. Maximization Step: Maximize the log-likelihood function (4.31) for each arrival using (4.32) and (4.33). The parameter values that maxi- mize the log-likelihood function for one arrival are the updated channel parameter estimates for that arrival. 4. Threshold Compare: If the change in all parameter estimates from the previous iteration is lower than a predefined threshold then the current estimates are the final EM channel parameter estimates. Otherwise go back to step 2. The complexity has been reduced since instead of a single 2L dimensional maximization, the algorithm requires L separate 2 dimensional maximiza- tions. 4.3.3 Space-Alternating Generalized Expectation-Maximization Channel Parameter Estimation The SAGE algorithm [33] further reduces implementation complexity over the EM algorithm. For channel parameter estimation this is done by sepa- rating the estimation of the channel parameters for each multipath arrival instead of estimating them together [57] as in (4.32). In addition, the expec- tation step is performed between the estimation of each arrival instead of 52 Chapter 4. Angle of Arrival Estimation after all arrivals. Each maximization of a single set of parameters for a mul- tipath arrival is followed by another expectation step. The SAGE algorithm has the ability to converge faster than the EM algorithm [33]. The result of this is that the complexity is reduced to 2L single dimen- sional maximizations to re-estimate all channel parameters for all multipath arrivals. Each maximization step is for a single arrival, which contains two separate maximizations performed in the order that they are listed followed by the calculation of the estimated amplitude τ̂ ′l = argmaxτ {∣∣∣z (τ, φ̂l; x̂l (t; θ̂))∣∣∣} (4.35) φ̂′l = argmax φ {∣∣∣z (τ̂ ′l , φ; x̂l (t; θ̂))∣∣∣} (4.36) α̂′l = 1 I ∣∣∣c(φ̂′l)∣∣∣2 TuPu z ( τ̂ ′l , φ̂ ′ l; x̂l ( t; θ̂ )) (4.37) where τ̂ ′l , φ̂ ′ l, and α̂ ′ l are the new parameter estimates for arrival l; τ̂l, φ̂l, and α̂l are the previous parameter estimates for the same arrival; and θ̂ is the previous parameter estimates for all of the arrivals. The complete data estimate calculated by (4.30) beforehand is x̂l using the previous parameter estimates. The algorithm process is as follows: 1. Initialize: Initialize all channel parameter estimates. Start at the l = 1 arrival. 2. Expectation Step: Perform signal decomposition (4.30) for the lth ar- rival to obtain one complete data signal estimate, x̂l. 3. Maximization Step: Perform the sequential maximization (4.35), (4.36), and (4.37) to generate new parameter estimates for the lth arrival. 4. Arrival Iteration: If l < L then l = l + 1 and go back to step 2. Otherwise l = 0 and continue on to step 5. 53 Chapter 4. Angle of Arrival Estimation 5. Threshold Compare/Full Iteration: If the change in all the parameter estimates from the previous full iteration is lower than a predefined threshold then the current estimates are the EM channel parameter estimates. Otherwise go back to step 2. A full iteration begins when entering step 2 from outside of steps 2-4, and ends when entering step 5. An arrival iteration is one pass from step 2 through to step 4. 4.3.4 SAGE Implementation The SAGE algorithm, while requiring significantly less computation than EM or ML estimation, in the mathematical form derived requires perform- ing correlation with the transmitted sequence at every stage. Since this operation is performed on the same data each time, the algorithm is imple- mented to save calculation by performing it once on each sequence of received channel data. This simplifies the SAGE algorithm to operate on the CIR instead of the received signals. Since correlation is a linear operation, the algorithms are equivalent. The expectation step after correlating both sides with the transmitted signal u (t) becomes k̂l ( t; θ̂ ) = α̂lcT ( φ̂l ) a(t) + h(t)− L∑ p=1 α̂pcT ( φ̂p ) a(t) . (4.38) where a(t) is the autocorrelation of u(t), the CIR vector h(t) = [h1(t), ..., hM (t)] and k̂l ( t; θ̂ ) is now the complete data, which is now the contribution of ar- rival l to the CIR. The complete data is what remains of the CIR when all the other estimated multipath components have been subtracted. The algorithm process is the same as described in Section 4.3.3, with (4.30) replaced by (4.38), and (4.34), (4.35), (4.36), and (4.37) replaced by z(τ, φ; k̂l) = c(φ)H k̂l ( τ ; θ̂ ) (4.39) 54 Chapter 4. Angle of Arrival Estimation τ̂ ′l = argmaxτ {∣∣∣z (τ, φ̂l; k̂l (t; θ̂))∣∣∣} (4.40) φ̂′l = argmax φ {∣∣∣z (τ̂ ′l , φ; k̂l (t; θ̂))∣∣∣} (4.41) α̂′l = 1 I ∣∣∣c(φ̂′l)∣∣∣2 TuPu z ( τ̂ ′l , φ̂ ′ l; k̂l ( t; θ̂ )) (4.42) respectively. The initialization process is arbitrary, but [57] proposes the following which was used in this study: 1. Set the initial parameter estimates all to 0. Start at the l = 1 arrival. 2. Expectation Step: Perform signal decomposition (4.38) including ar- rivals up until the lth arrival to obtain one complete data signal esti- mate, k̂l. 3. Maximization Step: Perform the sequential maximization outlined above except with τ̂ ′l = argmaxτ { k̂l ( τ ; θ̂ )H k̂l ( τ ; θ̂ )} (4.43) instead of (4.40) and φ̂′l = argmax φ {∣∣∣c(φ)H k̂l(τ̂ ′l ; θ̂)∣∣∣2} (4.44) instead of (4.41). 4. Arrival Iteration: If l < L then l = l + 1 and go back to step 2. Otherwise the initialization has been completed. 4.3.5 Determining AOA from Channel Parameters The resulting information from these general channel parameter estimation algorithms is an estimated set of channel parameters θ̂l = [τ̂l, φ̂l, α̂l] for a 55 Chapter 4. Angle of Arrival Estimation certain number of multipath arrivals l = 1, .., L. For positioning purposes, the only arrivals of interest are those that have a high probability of arriving from the same direction as the transmitter. These are the most probable direct paths which have travelled the shortest distance from transmitter to receiver and therefore will arrive at the earliest delays. To determine the AOA of the mobile from the AP, the multipath arrival with the smallest delay τ̂l is chosen. The AOA is the direction φ̂l for that multipath component. In the case when there is more than one arrival at the minimum delay, the AOA of the one with the largest complex amplitude is chosen. This underscores the most important issue with channel parameter esti- mation as it applies to positioning using AOAs. The ability to ensure that an adequate number of arrivals has been estimated such that the LOS ar- rival has been estimated is crucial. Since the SAGE algorithm as described prioritizes the estimation in terms of the delay and angle in that order, both of which are maximized in terms of the correlation between the received and expected signal, it is possible to miss the direct path if that arrival has sufficiently low amplitude. 4.3.6 Estimation of Number of Multipath Arrivals The maximum likelihood derived algorithms as described above do not have provisions for how the number of estimated multipath arrivals is selected. The accuracy with which the algorithms will estimate a channel with mul- tipath effects depends greatly on how many multipath arrivals parameters are estimated for. Used for purposes of positioning, where the most likely direct path is the most important, too few multipath arrivals may cause mis-estimation of the earliest arrival, therefore using an inaccurate AOA. Likewise, estimation of more multipath arrivals than are in the wireless channel can cause the estimation of arrivals that don’t exist in the channel, essentially estimating noise. These estimates potentially have delays earlier than the line of sight, which causes large errors in the estimated AOA. It has been proposed to use an algorithm to estimate the number of multipath arrivals prior to performing channel parameter estimation. This 56 Chapter 4. Angle of Arrival Estimation could be performed for example by using information theory [60]. These techniques confer a higher probability of selecting the correct number of multipath arrivals, but can be computationally complex. Since the aim of this research is not to fully investigate the best possible channel parameter estimation but to give a practical performance measure, a fixed number of estimated arrivals will be selected. This number will be selected based on the number of estimated arrivals that results in the best overall performance indicated in the performance analysis in section 4.6. Implementing an algo- rithm to estimate the number of multipath arrivals is not investigated. 4.4 Simplified ML AOA Implementation General parameter estimation algorithms may have problems providing ad- equate positioning AOA estimates, since they cannot guarantee the esti- mation of the direct path arrival. A simple approach instead might be to determine the AOA of the earliest detectable arrival. ML principles are ap- plied to this problem in a simplified ML implementation. In this way no additional computation is used to estimate arrivals that have little or no impact on the final AOA estimate when used for positioning. A strict ML algorithm for channel parameter estimation is far too com- putationally intensive to consider. However, the ML principles can be lever- aged to determine the most likely direct path AOA with low complexity. Since the AOA of the mobile from an AP depends only on the direct mul- tipath arrival, if this arrival can be chosen appropriately, then its AOA can be estimated. After computing the CIR from the received channel data, the earliest delay in the CIR can be used to determine an ML estimate of the AOA. Using the signal model (4.1), the channel impulse response is modeled as hm (t) = L∑ l=1 αl exp ( −j2pie (φl) • rm λ ) δ (t− τl) (4.45) 57 Chapter 4. Angle of Arrival Estimation which simplifies to hm (t) = L∑ l=1 αl exp ( −jpi (M − 2m+ 1) cos (φl) 2 ) δ (t− τl) (4.46) given the antenna spacing and placement of the system used. The ML implementation presented in this section assumes that there is only one arrival at the earliest delay. In effect it estimates the center of mass of the AOA of the earliest delay in the CIR. The CIRs are normalized into the sequence Hm = hm(min(τl)) h1(min(τl)) (4.47) such that H1 = 1+0j to start from a known phase, where min(τl) is the ear- liest delay in the CIR that has amplitude above some threshold. This means that the complex amplitude does not need to be estimated, and therefore the only parameter is effectively the AOA. Assuming the signal has been corrupted by an independent circular Gaussian noise process with power N0 as shown in (4.19), the PDF for Hm is p (Hm;φ) = 1 piN0 exp [ − 1 N0 |Hm − exp(jpi cosφ(m− 1))|2 ] . (4.48) The PDF can be simplified to a log-likelihood function Λ (Hm;φ) by taking the natural logarithm and removing all terms that do not depend on the parameter φ Λ (Hm;φ) = |Hm − exp(jpi cosφ(m− 1))|2 . (4.49) Note that the negative in the exponential has been removed, which means that instead of maximizing this log-likelihood function, it will be minimized. Considering all M antennas where H = [H1, ...,HM ] this becomes Λ (H;φ) = M∑ m=1 |Hm − exp(jpi cosφ(m− 1))|2 . (4.50) 58 Chapter 4. Angle of Arrival Estimation The estimate of the AOA φ̂ is calculated as φ̂ = argmin φ {Λ (H;φ)} . (4.51) The implementation of this algorithm is straightforward application of the log-likelihood function scanning through angles of φ from 0◦ to 180◦ at a resolution of 0.1◦. The critical part is the determination of which arrival corresponds to the earliest one. It appears that a simple and effective way of doing this is to choose the first delay with an amplitude above some threshold, in this case 10 dB, above the noise. While this works for the data collected, it may be unsuitable in situations where there is very low signal strength or weak direct paths. In those situations the threshold may need to be reduced to adequately select the earliest delay. 4.5 ML Estimation Performance The simplified ML algorithm was used to generate AOA estimates using the channel measurements. The basic statistics of the estimates, in terms of the error mean and standard deviation from the actual AOAs in each indoor situation, are shown in Figure 4.2. The full bandwidth of the CIRs was used, and each situation consists of 3000 estimates. The same statistics, using the ML algorithm on 40 MHz bandlimited CIRs are shown in Figure 4.3. The statistics are also included for reference in Table A.1. The estimation error mean and standard deviation can be interpreted in the following way. The mean demonstrates the accuracy of the system, which can be considered as how well the algorithm is able to select the direct path from the CIR. An error mean close to zero is a potential indicator of good accuracy. The standard deviation on the other hand is a measure of the estimation precision. For a positioning system both of these are important and contribute to the positioning performance. It was expected that reduction in the signal bandwidth would signifi- cantly degrade AOA estimation performance simply due to the loss of time resolution between multipath arrivals. These results indicate that the band- 59 Chapter 4. Angle of Arrival Estimation 0.00 5.00 10.00 15.00 LOS 90 degrees LOS 45 degrees Single wall 90 degrees Single wall 45 degrees Double wall 90 degrees Double wall 45 degrees Standard devia;on (degrees) Mean (degrees) Figure 4.2: AOA estimation error of ML algorithm in various indoor situa- tions at 300 MHz bandwidth. ‐5.00 0.00 5.00 10.00 15.00 LOS 90 degrees LOS 45 degrees Single wall 90 degrees Single wall 45 degrees Double wall 90 degrees Double wall 45 degrees Standard devia<on (degrees) Mean (degrees) Figure 4.3: AOA estimation error of ML algorithm in various indoor situa- tions at 40 MHz bandwidth. 60 Chapter 4. Angle of Arrival Estimation width reduction from 300 MHz to 40 MHz does not negatively impact AOA estimation, and AOA estimation actually improves in the LOS case. This may be a result of the multipath time density. The lower time density in the NLOS situations may allow the multipath arrivals to still be resolved even with the lower time resolution caused by the reduction in bandwidth. In an LOS situation, the ability to resolve the direct path is still poor due to the high time density, but the bandwidth reduction causes the time dense arrivals to be mixed together. The effect of the bandwidth limitation process on the AOA estimation can be thought of as a weighted averaging or temporal smoothing of the AOAs of individual arrivals at similar delays, with the weights being the amplitudes of the arrivals. The multipath in this particular situation may be such that the center of mass of the smoothed AOAs results in better estimates. This property cannot be relied upon since it is very environment dependent. The general performance of this algorithm is promising. For most sit- uations, the standard deviation is approximately 5◦. The estimation mean indicates that by choosing the earliest detectable part of the CIR, the al- gorithm is able to successfully identify the arrival of the direct multipath component in the NLOS situations studied when φ = 90◦. In the specific LOS situation studied however, the arrival is not easily resolved due to the time density of the arrivals, but temporal smoothing caused by the band- width reduction of multipath arrivals improves estimation and allows for usable AOA estimates. Despite what the results indicate, higher bandwidth is still preferred, since it will likely result in better AOA estimation in most environments. The ability to resolve the direct path is much more impor- tant than relying on the properties of the wireless environment to result in a center of mass AOA that resembles the same AOA as the direct path. More measurements in different indoor wireless environments would bear this out. Since the SNR of the received signals is higher than would be expected in a real WLAN system, additional noise was added to the 40 MHz ban- dlimited CIRs to achieve an SNR of 20 dB. The approximate SNR of the measurements is shown in Table 3.2. Between 5 dB and 10 dB of noise was 61 Chapter 4. Angle of Arrival Estimation added to the measurements. The ML algorithm was used to estimate AOAs and the AOA estimation statistics are shown in Figure 4.4 for the various indoor situations. It shows that the AOA estimation error remains similar for the double wall separation and LOS situations. The estimates from the single wall situation contain significantly more error, both in the mean and standard deviation. ‐5.00 0.00 5.00 10.00 15.00 LOS 90 degrees LOS 45 degrees Single wall 90 degrees Single wall 45 degrees Double wall 90 degrees Double wall 45 degrees Standard devia<on (degrees) Mean (degrees) Figure 4.4: AOA estimation error of ML algorithm in various indoor situa- tions at 40 MHz bandwidth with SNR lowered to 20 dB. The addition of noise should degrade AOA estimation accuracy as shown by the CRLB, especially in NLOS situations since the direct path has a sig- nificantly lower amplitude and therefore is more susceptible to error. This can be seen in the estimation error for the single wall separated measure- ments, where the estimation error standard deviation is increased with the addition of approximately 10 dB of noise. Given a high amplitude for the di- rect path component, such as in an LOS situation, the additional noise may not have significant effect on the estimation performance. The estimates from the LOS measurement data show this. The double wall and LOS measurements resulted in similar estimation 62 Chapter 4. Angle of Arrival Estimation performance regardless of whether noise was added or not. Since the orig- inal SNR of those measurements was 25 dB, the addition of a relatively small amount (5 dB) of noise does not impact the estimation performance significantly. Due to the way the algorithm is implemented by selecting the first multi- path 10 dB above the noise, it is possible that the direct path is not selected, and therefore a non-direct path arrival would be estimated. This is the case in the single wall separated situation, since the AOA estimation bias and precision suffers with a decrease in the SNR. The AOA estimation error shows that certain situations, primarily when the antenna array is rotated by 45◦, cause significant bias in the estimates. This can be caused by misidentification of the direct path arrival. It can also be caused by a characteristic of the signal model: the assumption that all the signals are confined to the horizontal plane. While the antenna arrays are at the same height, many of the multipath arrivals at the receive antenna array arrive with non-zero elevation. Additional elevation causes bias in the estimates. Given a horizontal AOA or azimuth of φ and an elevation angle of ω, the additional distance travelled by the signal ∆d to each subsequent antenna is ∆d = λ 2 cosφ cosω = λ 2 cos (4.52) where is the estimate of the AOA under the assumption of no elevation. The geometry is shown in Figure 4.5. For example given an elevation angle of 10◦, and an azimuth of 45◦, an algorithm assuming no elevation would estimate an AOA of 44.1◦. Likewise, for an indoor environment with a larger elevation angle of 30◦ at the same azimuth, the AOA would be estimated as 35.3◦. At an azimuth of 90◦, the elevation has no effect on the estimated AOA. In some cases of elevation and azimuth, the current signal model is not able to represent the incoming signal with only azimuth. This occurs when cosφcosω > 1. This contributes to additional error in the signal model that cannot be accounted for. With the signal arriving at all the receive antennas broadside, the elevation has no effect on the relative delay of the arrivals. The signal model used is con- 63 Chapter 4. Angle of Arrival Estimation λ 2 φ ∆d x y z ω Figure 4.5: The additional propagation distance to each receive antenna given azimuth angle φ and elevation angle ω. structed for an outdoor environment where the elevation angles are typically low, and therefore the bias in the AOA estimates is negligible. For indoor AOA estimation it is therefore imperative to estimate the elevation in addition to the azimuth. Unfortunately this likely involves ad- ditional antenna elements in the vertical plane to perform the elevation estimation. The benefit is that positioning can then be performed in 3D. For 2D positioning, it could be possible to remove the bias caused by the elevation without estimating it directly, with knowledge about the expected elevation angle of multipath arrivals. For accurate AOA estimation, changes to the antenna array in the form of additional antennas in the vertical plane would be necessary. Since MIMO equipped WLAN APs will likely have lin- ear antenna arrays by default, changes to those arrays would be necessary for use in AOA positioning. A more thorough description of the AOA error statistics is in terms of their PDFs, contained in Appendix A, which are derived from the estimate histograms. The PDFs of the AOA estimation error for the full bandwidth measurements are shown in Figures A.1, A.2, and A.3. The PDFs of the 64 Chapter 4. Angle of Arrival Estimation AOA error from the 40 MHz bandlimited measurements are shown in Figures A.4, A.5, and A.6. The PDFs of the AOA error from the 40 MHz bandlimited measurements when noise was added are shown in Figures A.7, A.8, and A.9. The PDFs are generally well formed although in some cases contain two lobes. This is an indication that another multipath arrival other than the direct path is being estimated. This appears in estimates from the bandlimited measurements as well as those that use the full bandwidth. 4.6 SAGE Estimation Performance The SAGE algorithm was used to generate estimates using the channel mea- surements. The estimates were made using between 1 and 9 estimated total multipath arrivals. The AOA estimation performance is shown in Figures 4.6 and 4.7 as a function of the number of estimated arrivals. Precision and accuracy of the SAGE estimates vary considerably with the number of estimated arrivals. The mean estimation performance is the least variable, with the broadside AOA φ = 90◦ measurements resulting in consistent estimation mean between 2 and 6 estimated multipath arrivals. This means that for that range of estimated arrivals, the earliest estimated arrival or arrivals were consistently the same for each. With the receive antenna rotated to φ = 45◦ it is clear that there is no consistent estimation error mean. This is not surprising considering the expected reduction in AOA estimation performance as the AOA differs from broadsiding the array due to the signal elevation. The AOA estimation accuracy of the SAGE algorithm appears to de- grade as the number of multipath arrivals increases beyond 3. This seems to indicate that the estimation of additional multipath arrivals degrades the overall accuracy of the estimation of the other arrivals. This is likely due to errors in the signal model, which accumulate as additional signals are used in the expectation process. In the simplest implementation, a fixed number of arrivals is estimated. A fixed number of 3 multipath arrivals will be used to evaluate the SAGE algorithm, as a balance between accuracy and precision. Estimating more 65 Chapter 4. Angle of Arrival Estimation 1 2 3 4 5 6 7 8 9 −10 0 10 20 30 40 50 AO A es tim at io n er ro r m ea n (de gre es ) Number of multipath arrivals LOS 90° NLOS single wall 90° NLOS double wall 90° LOS 45° NLOS single wall 45° NLOS double wall 45° Figure 4.6: AOA estimation mean error of SAGE algorithm in various indoor situations at 300 MHz bandwidth, using varying numbers of total estimated multipath arrivals. 1 2 3 4 5 6 7 8 9 0 5 10 15 20 25 30 AO A es tim at io n er ro r s ta nd ar d de via tio n (de gre es ) Number of multipath arrivals LOS 90° NLOS single wall 90° NLOS double wall 90° LOS 45° NLOS single wall 45° NLOS double wall 45° Figure 4.7: AOA estimation error standard deviation of SAGE algorithm in various indoor situations at 300 MHz bandwidth, using varying numbers of total estimated multipath arrivals. 66 Chapter 4. Angle of Arrival Estimation arrivals than 3 appears to result in poorer estimation precision, while the estimation accuracy remains similar. The basic statistics of the estimates using the SAGE algorithm with 3 estimated arrivals, in terms of the error from the actual AOAs in each indoor situation, are shown in Figure 4.8. The full bandwidth of the CIRs was used, and each situation consists of 3000 estimates. The same statistics for estimates generated using the SAGE algorithm with 3 estimated multipath arrivals with the CIRs bandlimited to 40 MHz are shown in Figure 4.9. The statistics are also contained in Appendix B. These results show the poor performance of the SAGE algorithm in an indoor environment in identifying the AOA of the direct path arrival. The estimates where the receive antenna array was rotated by 45◦ can be ig- nored due to the large bias contribution from the elevation of the signals. Generally, the SAGE AOA estimation performs worse with increasing sepa- ration between transmitter and receiver. This is expected since the number of multipath reflections in the channel increases, and the attenuation of the direct path makes it difficult to identify. The bandlimiting process results in even poorer AOA estimates, as the resolution between arrivals is reduced, reducing the algorithm’s estimation capabilities. One area where the SAGE algorithm results in higher precision than the ML implementation is in the LOS case when the full bandwidth of 300 MHz is used. However the accuracy suffers, which is likely due to accumulation of errors in the signal model. The improved estimation precision over the ML estimator is because the direct path signal has a high amplitude and since the SAGE algorithm estimates multiple arrivals, even at the same delay, the direct path can be separated from the time dense arrivals with similar delay. Faced with the same situation, the ML implementation makes no attempt to separate and identify the direct path. For example, three SAGE estimated channel parameters as well as the corresponding ML estimate from one of the LOS measurements where the direct path AOA is 90◦ resulted in the estimates shown in Table 4.1. It is clear in this case that two multipath arrivals at the earliest delay have been resolved. By choosing the one with the largest amplitude as the direct path, the estimation precision is greatly 67 Chapter 4. Angle of Arrival Estimation ‐10.00 0.00 10.00 20.00 30.00 40.00 LOS 90 degrees LOS 45 degrees Single wall 90 degrees Single wall 45 degrees Double wall 90 degrees Double wall 45 degrees Standard devia>on (degrees) Mean (degrees) Figure 4.8: AOA estimation error of SAGE algorithm in various indoor situations at 300 MHz bandwidth, using 3 total estimated multipath arrivals. ‐10.00 0.00 10.00 20.00 30.00 40.00 LOS 90 degrees LOS 45 degrees Single wall 90 degrees Single wall 45 degrees Double wall 90 degrees Double wall 45 degrees Standard devia>on (degrees) Mean (degrees) Figure 4.9: AOA estimation error of SAGE algorithm in various indoor situations at 40 MHz bandwidth, using 3 total estimated multipath arrivals. 68 Chapter 4. Angle of Arrival Estimation Table 4.1: Example SAGE and ML estimated channel parameters for an LOS measurement, with actual AOA of 90◦. Arrival Delay (samples) Amplitude AOA SAGE #1 27 1.13× 10−4 130.7◦ SAGE #2 27 1.49× 10−4 89.4◦ SAGE #3 34 1.44× 10−4 117.4◦ ML 100.2◦ improved over the ML estimator. The advantage of using SAGE is clear when the multipaths at the earliest delay are numerous. Insight into the ML algorithm is also demonstrated, as the ML algorithm simply estimates the center of mass of the AOAs. The AOA for arrival #1 causes the ML estimator to estimate a larger than expected AOA. Although this example demonstrates promise for the usage of the SAGE algorithm, at least in LOS cases, a look at the PDFs in Appendix B shows that the SAGE algorithm is also easily fooled into estimating non-direct path arrivals as well, and is more susceptible to errors in the signal model. The PDFs derived from the histograms of the AOA estimation error for the SAGE algorithm are contained in Appendix B. The estimates from full bandwidth measurements processed using the SAGE algorithm are shown in Figures B.1, B.2, and B.3. The PDFs of the AOA error from the 40 MHz bandlimited measurements are shown in Figures B.4, B.5, and B.6. All estimates were generated with the SAGE algorithm estimating 3 total multipath arrivals. The PDFs show that the AOA estimation error is higher than the ML estimator especially when the signal bandwidth was reduced to 40 MHz. It is clear that the SAGE algorithm does not adequately and consistently estimate the earliest arriving multipath, as there are significant outliers (sta- tistically significant groups with larger error) in the PDFs and estimation bias. This is the case even for the LOS measurements where the estimation performance is expected to be highest. The presence of multiple lobes in all the PDFs indicates that there are other multipath arrivals which are being chosen as the earliest estimated multipath. 69 Chapter 4. Angle of Arrival Estimation It is important to note that while the SAGE algorithm does not ap- pear to be useful for channel parameter estimation for WLAN positioning purposes especially compared to a less computationally expensive ML imple- mentation, its ability to estimate channel parameters is proven in outdoor environments [57]. However, for indoor use, inaccurate assumptions made in the formulation of the signal model may cause errors in the AOA estimates. These modeling errors accumulate when multiple arrivals are estimated. In addition, since the same signal model as the ML algorithm is used, it suffers from problems estimating multipath arrivals with non-zero elevation. The SAGE algorithm is inefficient at estimating the AOA in terms of the computational load since much of the computation is wasted on the estimation of multipath arrivals far away from the early delays. Performance over the simple ML estimator could be improved at low computational cost by estimating delays closer to the beginning of the CIR. 4.7 Estimation Performance Summary The measurements show that AOA estimation indoors appears to be pos- sible through the use of the simple ML algorithm or the SAGE algorithm depending on the indoor environment. The ML algorithm yielded AOA es- timates that should be useful in all situations, disregarding signal elevation. The SAGE algorithm showed poor AOA estimation performance in NLOS situations, and considering the high computational complexity, is ill suited for positioning purposes in its current formulation. The two algorithms show that for the situations studied, the single wall NLOS separation results in the best AOA estimates. The estimation per- formance is poorer in the LOS and double wall NLOS cases. This is likely the result of two opposing effects. The first is the reduction in the signal strength of the direct path component as distance increases. This makes it more difficult to identify the direct path, and therefore the AOA. The second is the multipath time density. The density of multipath arrivals in time is higher in the cases when the separation between the transmitter and receiver is low and results in poorer AOA estimates. 70 Chapter 5 Positioning Simulation The positioning performance using AOA measurements is evaluated through a positioning simulation. The simulations involve a 2D simulated user posi- tion and trajectory in a network of APs. At each user position, the actual AOAs to the each AP are calculated based on their known positions, and then random error is added to those AOAs to simulate the effects of the wireless channel and the AOA estimation. The noisy AOAs are then used to estimate the known position. The error between the estimated position and the known position is observed. The generation of the random AOAs is shown in section 5.1. These noisy AOAs are then used in a positioning algorithm to estimate the user position. Two different positioning algorithms are used: a linearized LS approach and a more sophisticated EKF, described in sections 5.2 and 5.3 respectively. The effect of geometry is then discussed in section 5.4. The error in the estimated position relative to the actual position is evaluated and analyzed for a fixed position simulation as well as a moving mobile simulation in section 5.5. 5.1 Random AOA Generation For each simulated mobile position random error is added to the actual AOAs at each AP. The errors in the AOAs are generated according to one of the PDFs generated from the AOA estimation described in Chapter 4. The PDFs are contained in Appendices A and B, and are constructed from the histograms of the AOA estimates. For implementation in Matlab, AOA error is generated from a PDF by first calculating the cumulative density 71 Chapter 5. Positioning Simulation function (CDF). For a PDF f(x), the CDF F (x) is calculated as F (x) = ∫ x −∞ f(x′)dx′ (5.1) using x′ as the integration variable. The CDF has a value between 0 and 1 due to the properties of PDFs. An example CDF is shown in Figure 5.1, computed using the PDF shown in Figure A.6(a). −15 −10 −5 0 5 10 15 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 AOA error (degrees) CD F Figure 5.1: Example CDF generated from the PDF in Figure A.6(a). After the calculation of the CDF, the Matlab rand() function is used to generate a uniformly distributed random number in the interval [0, 1]. The result of the rand() function is used as the value on the y-axis of the CDF to determine the amount of AOA error which is the corresponding x-axis value. This AOA error is added to the actual AOA of the mobile from the AP. This process is performed independently for each AOA generated. 5.2 AOA Least Squares Positioning One of the simplest algorithms with which to determine position from AOAs is LS. The basis of LS estimation is to find the position that minimizes the sum of the squared error between the AOA observations and the expected 72 Chapter 5. Positioning Simulation AOA observations corresponding to the estimated position, given no knowl- edge of the noise distribution. Due to the non-linear relationship between the AOA observations and the mobile position, a linearized LS algorithm is used [58]. The relationship between the position of the mobile x = [xm, ym] T and AOA at the kth AP is φk = gk (x) = tan−1 ( ∆xk ∆yk ) (5.2) where φk is the AOA of the mobile signal, xm is the easting coordinate of the mobile, ym is the northing coordinate of the mobile, and ∆xk = xm − xk,∆yk = ym − yk (5.3) where the position of the kth AP is xk = [xk, yk]. Since the relationship between the position and the AOAs is non-linear, linearization is applied by first order Taylor expansion to iteratively perform positioning estimation. An initial estimate for x is required. Another esti- mator such as a best linear unbiased estimator (BLUE) [58] could be used to generate an initial position, or other information available could be used. The choice of the initial position will be discussed later. Firstly the expected observations l = [l1, ..., lK ] T for K APs given the current estimated position x̂ must be calculated lk = gk (x̂) . (5.4) Next the design matrix A is calculated, by determining the first order partial derivatives of gk for all APs with respect to x. It is linearized about the current estimated position x̂. It has the form A = ∂ ∂x g1(x) . . . gK(x) x=x̂ = ∂g1 ∂xm ∂g1 ∂ym . . . . . . ∂gK ∂xm ∂gK ∂ym x=x̂ . (5.5) 73 Chapter 5. Positioning Simulation The partial derivatives are ∂gk ∂xm = ∆yk ∆x2k + ∆y 2 k (5.6) ∂gk ∂ym = −∆xk ∆x2k + ∆y 2 k . (5.7) Note that the denominator of the partial derivatives is the square of the estimated range between the mobile and AP. The amount of correction δ to the previous position estimate x̂ to obtain the new estimate x̂′ is dependent on the difference between the expected observations l and the actual observations φ = [φ1, ..., φK ] T . This difference is called the misclosure vector w = φ− l. (5.8) The sum of the squares of the elements in the misclosure vector is the residual error. The misclosure vector and the design matrix are used to compute a correction to the previous estimate assuming equal weight to all observations δ = ( ATA )−1 ATw. (5.9) The correction is then applied to the previous estimate to generate a new estimate x̂′ = x̂ + δ. (5.10) The process from the calculation of the expected observations to the new estimate is repeated. The new estimate is used in the next iteration as the previous estimate until the correction becomes small in which case the LS algorithm converges to a position estimate. If the correction never becomes small then the LS algorithm diverges and a position estimate is not found. LS convergence for positioning using AOAs depends on two main factors. A poorly chosen initial position estimate can cause the algorithm to diverge, whereas another initial position estimate may result in a position solution 74 Chapter 5. Positioning Simulation that converges. The choice of the initial position estimate is therefore im- portant, and the LS algorithm generally works best when the initial position estimate is close to the actual position. Also, poor AP geometry can cause divergence if it causes ATA to become nearly singular. For instance, this occurs when the APs and the mobile are nearly colinear. 5.3 Extended Kalman Filter Kalman filtering is an estimation algorithm that has become very important for many applications. It allows for the efficient combination of different sequential observations to perform state estimation. For time varying posi- tioning using AOAs, the Kalman filter uses current AOA observations, the previous position estimate and a model about the movement of the mobile to estimate an updated position. The basis of a Kalman filter is similar to LS since it minimizes the sum of the squared error between the actual and expected observations. In the same manner as the LS estimator, because the relationship between the position state of the system and the observations is non-linear, it must be linearized. This is performed using an EKF [61]. The EKF requires a model of the changes in the state of the system. In the case of a moving mobile device, an appropriate model could be the constant velocity model. In this model, the state of the system consists of the instantaneous position and velocities in all directions. For 2D positioning, the easting and northing directions will be considered. The velocities ẋ and ẏ in the easting and northing directions respectively, are assumed to be constant, and therefore the position state transitions to the next state accordingly depending on the sampling time ∆t. The current time sample is n. The new estimate includes prediction through the model using the estimate from the previous sampling time n − 1. The model defines the 75 Chapter 5. Positioning Simulation state to state behaviour from time sample n− 1 to n as xn = xn yn ẋn ẏn = f (xn−1) = xn−1 + ẋn−1∆t yn−1 + ẏn−1∆t ẋn−1 ẏn−1 . (5.11) When the estimation begins, the EKF must be given an initial state because of the prediction process. In a practical system, the first incoming observations could be used to initialize the state to the position indicated by a LS estimator. However, for the simulation used in this thesis, the initial position is set to the actual position, but the velocities are set to 0. There are two basic steps to add new measurements and estimate a new state using an EKF. The previous state is first used to predict the current state based on the dynamic model. The predicted state is then corrected using the incoming observation or measurement data. Quantities based on the predicted state are denoted with (−), and those after application of the new observations are denoted with (+). For the purposes of the model used here, the state transition model is linear and time invariant. If it was time varying, then the function for the appropriate time would be used. The previous state estimate x̂n−1 (+) is used to predict the state estimate for the next interval x̂n (−) using the dynamic model x̂n (−) = f (x̂n−1 (+)) . (5.12) As with the LS estimator, there exists a function gk that relates the state of the system to the observations. This is the same as equation (5.2). The expected observations φ̂k,n are calculated based on the predicted state x̂n (−) as φ̂k,n = gk (x̂n (−)) . (5.13) To propagate the effects of the prediction on the covariance matrix of the 76 Chapter 5. Positioning Simulation estimates, the dynamic model is linearized into the state transition matrix Φ = ∂f ∂x = 1 0 ∆t 0 0 1 0 ∆t 0 0 1 0 0 0 0 1 . (5.14) Since the dynamic model is linear and time invariant, this only needs to be determined once, otherwise it would be linearized about the current state estimate for every run of the EKF. Similar to the LS estimator, the function gk relating the state to the position must be linearized by taking the derivative with respect to the state to obtain the measurement sensitivity matrix Gn ≈ ∂ ∂x g1(x) . . . gK(x) x=x̂n(−) = ∂g1 ∂xm ∂g1 ∂ym 0 0 . . . . . . . . . . . . ∂gK ∂xm ∂gK ∂ym 0 0 x=x̂n(−) . (5.15) Since the position does not depend on the velocities, their partial derivatives are zero. An EKF depends heavily on the estimated covariance or error in all quantities that are used to determine the current state. Quantities with large estimated error contribute little to state estimates. The estimated error is updated every time the EKF is used to generate a new set of state estimates. Given the previous state covariance Pn−1 (+), the new state covariance prior to incorporation of new observations Pn (−) is calculated as Pn (−) = ΦPn−1 (+) ΦT + Q (5.16) based on the prediction of the state transition model as well as the error covariance of the model itself Q. The covariances are arbitrary and are selected according to how well 77 Chapter 5. Positioning Simulation certain quantities are known. For example, if it is known beforehand that the constant velocity state transition model is inaccurate in terms of the prediction of the movement of the mobile, then the covariance is selected to be large, such that the state transition model prediction is weighted less when combined with new observations. The covariance matrices of the state transition model Q and the observations R are free parameters which can be used to optimize the performance of the EKF. There is usually no way to definitively know these quantities, so the programmer of the EKF approximates these based on some statistics and are assumed to be constant. For the implementation used in this thesis, R was chosen to be 0.01I in units of radians squared, which corresponds to an AOA estimation standard deviation of 5.7◦ which adequately represents the expected error in the ML processed AOA measurements. Q was chosen to be Q = 1 0 0 0 0 1 0 0 0 0 2 0 0 0 0 2 (5.17) in units of m2 for the positions and in units of (m/s)2 for the velocities. The covariance of the velocity modeling error was chosen to be higher for the simulation to cope with sudden changes in mobile direction. Experimentally these covariances appeared to perform at least as well as any others that were tried. The error of 1 m for the positions was chosen due to the simulation interval of 1 s, in which the moving user is not likely to experience a change in position of much larger than 1 m. The Kalman gain Kn is a measure of how much the observations are used to estimate the final state estimate as opposed to the prediction of the dynamic model. It is computed as Kn = Pn (−) GTn [ GnPn (−) GTn + R ]−1 . (5.18) The new estimate of the covariance of the state estimate Pn (+) is then updated from Pn (−) to take into account the error in the new observations 78 Chapter 5. Positioning Simulation Pn (+) = ( I−KnGn ) Pn (−) . (5.19) The predicted system state estimate can now be updated x̂n (+) = x̂n (−) + Kn ( φn − φ̂n ) (5.20) depending on the error between the expected measurements φ̂n = [ φ̂1,n, ..., φ̂K,n ] predicted using (5.13) and the actual measurements φn = [φ1,n, ..., φK,n] ac- cording to the Kalman gain. This process is then repeated for every new set of observations that is recorded at each time interval. Note that unlike the linearized LS estimator, the EKF is not iterative. 5.4 AP Geometry Considerations Positioning accuracy depends highly on the geometry of the APs. For AOA- based positioning, the positioning accuracy improves greatly as the distance between the APs and the mobile decreases. The positioning simulation consists of four APs placed in the corners of a 30 m x 30 m square. This was selected due to the typical deployment density of WLAN APs, and for the favourable geometry which results in good overall expected positioning accuracy. The whole simulation area is a 40m x 40m square centered at the origin. The DOP metric describes how the geometry and measurement error affect the accuracy of position estimation. The basics of DOP are as de- scribed in section 2.1.2. The northing and easting DOP for positions in 1 m increments in the simulation area are shown in Figure 5.2. The DOP values for each position are calculated [62] (ATA)−1 = [ EDOP 2 ρ · EDOP ·NDOP ρ · EDOP ·NDOP NDOP 2 ] (5.21) where the design matrix A, as defined in (5.5), is evaluated at the actual 79 Chapter 5. Positioning Simulation location of the mobile, and ρ is the unitless correlation between the NDOP and EDOP. NDOP is the DOP in the northing direction and EDOP the DOP in the easting direction. Smaller DOP indicates lower positioning error due to better geometry. The correlation ρ is shown in Figure 5.3(a) and the overall horizontal DOP in Figure 5.3(b). The location of the APs are shown as green triangles. The HDOP indicates horizontal positioning performance and is calculated as HDOP = √ NDOP 2 + EDOP 2. (5.22) The HDOP shows that positioning performance is relatively poor in the horizontal and vertical lines connecting the APs. The correlation indicates how the position estimates are spread apart. Instead of the resulting positions conforming to a circular error area, which occurs when ρ is 0, the error area becomes an ellipse. This is shown in Figure 5.4. Each dot represents an estimated position and all are estimates of the same actual position. The DOP simply relates the measurement error to the positioning error. For example, if the positioning error is desired to be less than 2 m and the error in the AOA measurements is 5◦, then the geometry would need to be such that the DOP in m/rad is less than 23. Using the AP geometry in the simulation studied, the HDOP shown in Figure 5.3(b) indicates that this DOP requirement is approximately met at most positions inside the square made by the APs. Similarly, for the same desired positioning perfor- mance, but with more accurate measurements, the DOP requirement could be relaxed. 5.5 Positioning Performance The positioning performance of the LS and EKF algorithms is evaluated using a Monte Carlo positioning simulation. Two different simulations are used. The first evaluates the mobile position at fixed positions, and the second determines mobile position for a moving mobile user. In each simu- 80 Chapter 5. Positioning Simulation Easting (m) N or th in g (m ) −20 −10 0 10 20 −20 −15 −10 −5 0 5 10 15 20 0 5 10 15 20 25 30 35 (a) Northing DOP. Easting (m) N or th in g (m ) −20 −10 0 10 20 −20 −15 −10 −5 0 5 10 15 20 0 5 10 15 20 25 30 35 (b) Easting DOP. Figure 5.2: DOP for the northing and easting directions for AOA positioning in units of metres per radian. Easting (m) N or th in g (m ) −20 −10 0 10 20 −20 −15 −10 −5 0 5 10 15 20 −1 −0.5 0 0.5 1 (a) Unitless correlation between DOP in northing and easting directions. Easting (m) N or th in g (m ) −20 −10 0 10 20 −20 −15 −10 −5 0 5 10 15 20 0 5 10 15 20 25 30 35 40 (b) Horizontal DOP in units of metres per radian. Figure 5.3: DOP correlation and HDOP for AOA positioning. 81 Chapter 5. Positioning Simulation (a) ρ = 0. (b) ρ < 0. (c) ρ > 0. Figure 5.4: Example estimated positions depending on correlation ρ between DOP in northing and easting directions. lation, for each position of the mobile, the actual AOAs at each of the APs is calculated. These actual AOAs are then corrupted with random error according to one of the PDFs contained in Appendices A and B. A more complex simulation might apply random AOA error according to different PDFs at different APs. For instance, with PDFs from the same algorithm but different receive antenna rotation and amount of obstruction between transmitter and receiver. The distance between transmitter and receiver could be used to simulate likely obstruction. However, there are many cases in which this doesn’t represent actual usage. The best, average and worst case positioning performance can still be evaluated using a sin- gle PDF to generate AOA error for all APs, so addding complexity to the simulation is unnecessary. The first simulation estimates the position of the user for fixed positions in the simulation area. This is performed for all positions in the simulation area in 1 m increments, and at each position the simulation is run 1000 times. The resulting root mean square (RMS) position error at each position is recorded. This is suited only to the LS positioning algorithm, since it is not time varying. The LS positioning performance is assessed and verifies the positioning error indicated by the DOP. In the second simulation, a single simulation run consists of a moving mobile with two-part constant velocity trajectory: from (-15 m, 0 m) to (0 m, 15 m) and then to (15 m, 0 m). The length of the simulation is 80 s and 82 Chapter 5. Positioning Simulation the position of the mobile is estimated every 1 s. Both the LS and EKF are used for the trajectory estimation. Each algorithm is run with 1000 trials of the trajectory simulation. The RMS position error for each trial is recorded. Since LS only uses the current AOA measurements to determine the user position, and the EKF uses previous position and measurement information, this simulation serves to show the positioning improvements possible by using more measurement data. The RMS position error Erms is computed as Erms = √√√√ 1 N N∑ n=1 ( (xn − x̂n)2 + (yn − ŷn)2 ) . (5.23) For a single fixed position in the fixed position simulation, the RMS position error is computed with n representing the simulation trial, (xn, yn) the actual position of the mobile, (x̂n, ŷn) the estimated position for trial n, and N the number of total trials, 1000. The estimated mobile position is only included in the RMS calculation for position estimates that converge. For a single estimated trajectory trial in the trajectory simulation, the RMS position error is computed with n as the simulation epoch, (xn, yn) the actual mobile position at epoch n, (x̂n, ŷn) the estimated position at epoch n, and N the total simulation length in epochs. Position estimates in the trajectory simulation are used in the RMS error calculation even if they did not converge. The average RMS error (ARMSE) for the fixed position simulation is the RMS position error averaged over all the possible positions of the mobile in the simulation area. The ARMSE for the trajectory simulation is the RMS position error averaged over 1000 trials of the trajectory simulation. 5.5.1 Fixed Position Estimation Performance Since LS does not take into account the previous position or any previous positioning measurements, the performance of the LS at each position can be examined. The results from the fixed positioning simulation in terms of the ARMSE are contained in Table C.1. 83 Chapter 5. Positioning Simulation The results using the estimates from the ML algorithm are discussed in this section, and some comments about the usage of the SAGE estimates included. When performing the positioning simulations, it was observed that the initial position estimates had a significant effect on the convergence of the LS algorithm. A suitable method of easily determining the initial position estimate was found to be by dividing the simulation area into smaller ar- eas as shown in Figure 5.5. Selecting the appropriate area was performed by observing the noisy AOAs, identifying them in terms of quadrants and making a quick decision as to which area the mobile was most likely located. The initial position estimate was then selected to be the center of the area in which the mobile was determined to be located. In Figure 5.5 the bound- aries of the areas are shown as red lines and the initial position estimates for each area are shown as blue dots. The positions of the APs are shown as green triangles. Figure 5.5: LS initial position estimates based on approximate area. An example of the RMS positioning error using the LS algorithm for all positions in a simulation area of 40 m x 40 m centered at the origin is 84 Chapter 5. Positioning Simulation shown in Figure 5.6. The PDF Figure A.5(a) for the ML processed 40 MHz bandlimited measurements taken with single wall separation was used to generate the random AOA error. This represents the best case positioning accuracy. The plot of the number of the trials that resulted in converging position estimates is shown in Figure 5.7. The positions of the APs are shown as green triangles. The ARMSE, or RMS position error averaged over every position in the simulation area, results in an expected positioning error of 0.79 m. The ARMSE and convergence for the AOA error PDF in Figure A.6(a) of the ML processed 40 MHz bandlimited measurements taken with double wall separation is shown in Figures 5.8 and 5.9. This represents a more typical expected positioning performance. The ARMSE for the simulation area in this case is 2.82 m. There is a slight difference in the gradient of the ARMSE in Figure 5.8 and the HDOP shown in Figure 5.3(b). This rotational skewing is due to the bias in the measurement error PDF. The RMS position error of the LS algorithm such as that shown in Fig- ures 5.6 and 5.8 follows closely from the HDOP in Figure 5.3(b), as ex- pected. This is illustrated by scaling Figure 5.6 by the standard deviation of the measurement error PDF, resulting in Figure 5.10, which matches the HDOP closely. The convergence of the LS algorithm is poor in close proximity to the APs. When near an AP, the matrix ATA becomes nearly singular and therefore ill conditioned. This leads to the divergence of the LS position estimate. Simulations incorporating random AOA error according to the PDFs from the ML generated estimates resulted in positioning estimates with error better than 5 m, and in some cases better than 1 m. The only exception to this was the PDF from the LOS measurements taken when the receive antenna was rotated by 45◦ at full bandwidth shown in Figure A.1(b). As noted in Table C.1, this was the only PDF from the ML estimates that had significant outliers, with a group near 40◦ AOA error. For an overall performance metric, the average of the ARMSEs of the position estimates from the PDFs corresponding to the bandlimited ML estimates is 2.1 m. 85 Chapter 5. Positioning Simulation Easting (m) N or th in g (m ) −20 −15 −10 −5 0 5 10 15 20 −20 −15 −10 −5 0 5 10 15 20 0 0.5 1 1.5 Figure 5.6: RMS position error in metres from 1000 Monte Carlo simulation trials, using AOA error generated from Figure A.5(a). Easting (m) N or th in g (m ) −20 −15 −10 −5 0 5 10 15 20 −20 −15 −10 −5 0 5 10 15 20 0 100 200 300 400 500 600 700 800 900 1000 Figure 5.7: Number of converged position estimates out of 1000 Monte Carlo simulation trials, using AOA error generated from Figure A.5(a). 86 Chapter 5. Positioning Simulation Easting (m) N or th in g (m ) −20 −15 −10 −5 0 5 10 15 20 −20 −15 −10 −5 0 5 10 15 20 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 Figure 5.8: RMS position error in metres from 1000 Monte Carlo simulation trials, using AOA error generated from Figure A.6(a). Easting (m) N or th in g (m ) −20 −15 −10 −5 0 5 10 15 20 −20 −15 −10 −5 0 5 10 15 20 0 100 200 300 400 500 600 700 800 900 1000 Figure 5.9: Number of converged position estimates out of 1000 Monte Carlo simulation trials, using AOA error generated from Figure A.6(a). 87 Chapter 5. Positioning Simulation Easting (m) N or th in g (m ) −20 −15 −10 −5 0 5 10 15 20 −20 −15 −10 −5 0 5 10 15 20 0 5 10 15 20 25 30 35 40 Figure 5.10: RMS position error divided by the AOA error standard devi- ation in metres per radian from 1000 Monte Carlo simulation trials, using AOA error generated from Figure A.6(a). Similarly, with the estimates from the SAGE algorithm, the PDFs with significant outliers resulted in unusable position estimates. This confirms that a LS algorithm is a poor choice of positioning algorithm in the presence of AOA error with significant outliers. Due to the inconsistency of the SAGE algorithm in the various indoor measurement situations, the results from the fixed position simulation reinforce that SAGE is unsuitable for positioning applications. The positioning performance of the LS algorithm depends heavily on the PDF of the measurements. It is highly susceptible to high positioning error due to outliers. The large error in the outliers causes the position estimate to diverge heavily, or converge to a poor position solution. This causes very large errors. The formulation of the LS algorithm results in these errors since the position estimate is selected to minimize the squared error between the expected and actual observations. If one of the observations contains severe error, the square of that error is considered in weighting the importance of 88 Chapter 5. Positioning Simulation the observations. An already large error contributes even more to the final position estimate. There are different approaches to solving the problem caused by out- liers. Temporal smoothing allows for some reasonable changes in position from state to state and rejects those that are too large. If the outliers are in- frequent, then it is possible to detect the outliers and exclude them from use in the position estimation process. High residual error between the expected and actual observations for the final LS position solution can indicate the presence of outliers. With more observations than the minimum necessary for position estimation, subsets of the available observations can be used to determine the outlying observation. For example in this simulation, LS solutions can be computed for all combinations of observations from three of the four available APs. The LS solution that is associated with the least residual error is chosen as the one that excludes the outlying observation. 5.5.2 Trajectory Estimation Performance The estimation of positions in the trajectory simulation is evaluated for both the LS and EKF. The trajectory was simulated 1000 times, and the ARMSE of those simulations recorded. The ARMSEs corresponding to simulations using the AOA error from the different measurements are shown in Table C.2. An example of the estimated positions for one individual trajectory simu- lation is shown in Figure 5.11 using error generated using the PDF in Figure A.6(a) for the ML processed bandlimited measurements with φ = 90◦. For this trajectory estimation trial, the RMS error for the LS position estimates was 2.86 m and 1.91 m for the EKF position estimates. This was selected to represent the average performance of the positioning system using ML estimates. An example estimated position trajectory using the PDF in Figure B.4(a) for the SAGE estimates in the bandlimited LOS case with φ = 90◦ is shown in Figure 5.12. This PDF includes frequent outliers, and demonstrates the significantly improved positioning of the EKF over that of the LS. The 89 Chapter 5. Positioning Simulation RMS error for the LS position estimates was 4.67 m and 2.89 m for the EKF estimates. Note that one of the LS estimated positions is outside of the simulation area, with large positioning error. The best case positioning performance is evaluated in the same manner as the fixed position simulation. The PDF used corresponds to the ML estimates from the bandlimited single wall separated measurements shown in Figure A.5(a). The estimated trajectories using the LS and EKF algorithms are shown in Figure 5.13. For this simulation trial, the RMS position error for the LS estimates was 0.73 m and 0.47 m for the EKF estimates. In addition to the better RMS positioning error of the EKF over the LS algorithm, the trajectory estimates show the benefit of the prediction based on the constant velocity model. From one position estimate to the next, the estimates from the EKF show better consistency, and are less erratic. That is, they change direction less often, and are less susceptible to large position changes. This is due partly to how well the constant velocity model matches the actual trajectory, which is also of constant velocity. The downside to the incorporation of the prediction in an EKF is shown in Figure 5.14 where the sudden change in direction of the mobile causes the EKF to overshoot the turning point of the mobile trajectory. It takes a few additional position estimates to correct the velocity and return closer to the actual trajectory. The dynamic prediction model may not be well suited to the expected movement of the mobile. In this case if the positioning performance is un- acceptable, the covariance of the dynamic model Q can be increased such that the prediction contributes less to the final position estimates. The po- sition estimates are therefore influenced mostly by the AOA measurements. For example, if the mobile is expected to move irregularly or undergo large acceleration, either a new dynamic model could be used, or Q increased. An increase in Q diminishes the advantage of using an EKF over an LS estimator. A better choice is to improve the dynamic model such that it more accurately models the movement of the mobile. An unsuitable choice of dynamic model and poorly chosen Q results in less accurate position estimates. The EKF clearly has better positioning performance, especially in the 90 Chapter 5. Positioning Simulation −20 −15 −10 −5 0 5 10 15 20 −20 −15 −10 −5 0 5 10 15 20 Easting (m) N or th in g (m ) Actual LS estimated EKF estimated AP Figure 5.11: Typical example trajectory simulation trial with LS and EKF using AOA error from ML estimates PDF shown in Figure A.6(a). −20 −15 −10 −5 0 5 10 15 20 −20 −15 −10 −5 0 5 10 15 20 Easting (m) N or th in g (m ) Actual LS estimated EKF estimated AP Figure 5.12: Worst case example trajectory simulation trial with LS and EKF using AOA error with significant outliers from SAGE algorithm using the PDF shown in Figure B.4(a). 91 Chapter 5. Positioning Simulation −20 −15 −10 −5 0 5 10 15 20 −20 −15 −10 −5 0 5 10 15 20 Easting (m) N or th in g (m ) Actual LS estimated EKF estimated AP Figure 5.13: Best case example trajectory simulation trial with LS and EKF using AOA error from ML estimates PDF shown in Figure A.5(a). presence of outliers. The improvement of the EKF over the LS shown in Table C.2 is very large in all but a few instances. Much of the large improve- ment is caused by the inclusion of LS diverging position estimates when cal- culating the RMS error. In practice, diverging LS position estimates would not be used, but their inclusion underscores an important advantage of the EKF over an LS estimator. The EKF does not suffer from the same di- verging solutions problem as the LS since it is not an iterative approach. This results in more consistent position estimates for an entire estimated trajectory. Averaging the ARMSEs for the positioning simulation using PDFs from the bandlimited ML estimates results in a general positioning performance of 2.1 m. It is coincidental that this is the same as the result from the fixed position simulation. Note that this positioning error is only valid for this particular mobile trajectory. However, this is assumed to be representative of actual positioning performance since the beginning, middle and end of the trajectory are in areas where relatively poor positioning performance 92 Chapter 5. Positioning Simulation −20 −15 −10 −5 0 5 10 15 20 −20 −15 −10 −5 0 5 10 15 20 Easting (m) N or th in g (m ) Actual EKF estimated AP Figure 5.14: Example trajectory simulation run with EKF showing effect of mobile movement not matching dynamic model. is expected, as indicated by the HDOP in Figure 5.3(b). In addition, the constant velocity trajectory seems to be reasonably well suited to human movement. The performance of the LS and EKF are expected to become similar as the number of observations increases, in this case the number of APs and therefore AOAs. In the case of gaussian AOA error with only two observations for a stationary mobile, the positioning performance is expected to be approximately 2.5 times better for an EKF over an LS estimator [63]. With PDFs that have outliers, the positioning performance is much better using an EKF. Much of the performance benefit of the EKF over an LS algorithm depends on how well the model of the mobile’s movement matches the actual mobile trajectory. The results of this thesis indicate EKF positioning performance increases upwards of 1.5 times better over an LS algorithm in terms of the ARMSE positioning error in the majority of the cases studied. The decision to use either EKF or LS to estimate the user position is de- 93 Chapter 5. Positioning Simulation pendent on the type of position required. For systems that simply compute single instantaneous position estimates using a single set of observations, an LS algorithm is the most useful. For other systems which track user posi- tion over time, or integrate numerous observations, an EKF offers the most benefit. 94 Chapter 6 Conclusions and Future Work 6.1 Conclusions 6.1.1 AOA Estimation AOA estimation was evaluated using actual MIMO indoor channel measure- ment data. The system used and the environment characterized are both similar to that of an 802.11n WLAN network deployment. Three different indoor propagation scenarios were studied: LOS, as well as with the receiver and transmitter separated by one and two walls. In each scenario measure- ments were taken when the direct path broadsided the receive antenna array as well as with the receive antenna array rotated by 45◦. In addition, the measurements were used both at the full recorded 300 MHz bandwidth, and bandlimited to 40 MHz, which better represents WLAN usage. The AOA of the signal was estimated from these measurements using two different channel characterization algorithms, an ML implementation and SAGE. The ML algorithm is a computationally and conceptually simple algorithm that estimates a single arrival at the earliest delay in the CIR. The SAGE algorithm is significantly more complex, and attempts to estimate multiple arrivals in the CIR. SAGE is also suitable for other types of channel parameter estimation unrelated to positioning. The two algorithms were used to estimate AOAs from the measurement data, and the error between the estimates and the actual known AOAs was observed. It was found that the ML algorithm resulted in AOA estimates with standard deviation at times better than 5◦. The ML algorithm also appeared 95 Chapter 6. Conclusions and Future Work to be unaffected by the reduction in bandwidth. In the case where there was LOS between transmitter and receiver, the AOA estimation improved as the bandwidth was reduced. Additional measurements would need to be taken to determine whether this improvement is common, or is situation and environment specific. The ML implementation used appears to be able to resolve the direct multipath arrival frequently, and therefore results in useful AOA estimates. Since the SNR of the measurements is higher than might be expected from a WLAN system, noise was added to the measurements to lower the SNR by between 5 and 10 dB. The added noise had little effect on the ML AOA estimation for the LOS and double wall separated measurements. This is attributed to those measurements having the least amounts of noise added since the SNR for those measurements was the lowest. The single wall sep- arated measurements had the most noise added and the resulting estimates were impacted negatively. In addition to the usual effects of noise causing inaccuracy in the AOA estimates, the added noise also causes error in the AOA estimates by making the selection of the direct multipath component more difficult. In the case when the selection of the direct path is made improperly, significant error appears in the AOA estimate. The SAGE algorithm, unlike the ML algorithm, estimates more than one multipath arrival. The AOA estimation performance depends on the number of arrivals, and the AOA estimation was evaluated for various num- bers of multipath arrivals. The best overall AOA estimation resulted from the choice of three multipath arrivals, for the measurements and situations studied. In a practical system, the number of multipath arrivals would be estimated beforehand, and that number used in the SAGE estimation. The SAGE estimates were mostly poorer than those generated by the ML algorithm. SAGE prioritizes the estimation of the multipath arrivals by their amplitude. In cases where the direct path does not have a high amplitude, the SAGE algorithm estimates other multipaths instead and uses their AOAs causing error. This is witnessed as larger error in the AOA estimates compared to the ML algorithm for the NLOS measurements. It is also apparent in the AOA error PDFs, contained in Appendices A and 96 Chapter 6. Conclusions and Future Work B, which show multiple lobes, indicating a series of different AOAs that are estimated. SAGE does have better AOA estimation precision, albeit with reduced accuracy, when compared to the ML algorithm in the LOS case when the bandwidth was 300 MHz however, since the direct path has a high amplitude. The ML algorithm makes no attempt to differentiate between multipath arrivals, assuming the presence of only one. The SAGE algorithm, by estimating multiple arrivals, is able to distinguish between arrivals with the same or similar delay. This results in improved estimation performance. Also unlike the ML algorithm, the reduction in bandwidth had a very noticeable negative effect on the AOA estimates generated by SAGE. This is because the SAGE algorithm performance hinges on the ability to distin- guish multipath arrivals from each other. The reduced bandwidth causes the multipath arrivals to mix together, and are therefore more difficult to separate. Since the ML algorithm is significantly less computationally expensive compared to the SAGE algorithm, and results in better AOA estimates in most situations, it is the most likely candidate for practical implementa- tion. Improvements to target the SAGE algorithm specifically for use in positioning could make it a more attractive option. The results suggest that general parameter estimation algorithms such as SAGE are not well suited for positioning purposes. Common between the SAGE and ML estimates, was a significant bias in the AOA estimates, especially when the direct path signal impinged on the rotated receive antenna array, when φ = 45◦. This is a fault inherent to the antenna array and signal model used. The signal model was constructed under the assumption that the wireless signals were confined to the horizon- tal plane, which is often not true in an indoor environment. This causes a bias in the AOA estimates dependent on the elevation angle of the signals. Even with a new signal model, the system used is not able to estimate the elevation of the signal, since the antennas are confined to the horizontal plane themselves. An antenna array with elements in the vertical plane is necessary to perform accurate AOA and elevation estimation. 97 Chapter 6. Conclusions and Future Work 6.1.2 Position Estimation The PDFs of the AOA error determined from the AOA estimation algo- rithms were used in a 2D positioning simulation to determine the expected positioning performance of this type of system. The positioning simulation involved the simulation of the mobile within a network of APs placed at the corners of a square. For every simulated position of the mobile, the actual AOAs from each of the APs were calculated and subsequently corrupted with random AOA error according to one of the PDFs generated from the AOA estimation process. These noisy AOAs were then used in a positioning estimation algorithm to determine the mobile position. Two types of positioning simulation were used, one where the mobile was simulated at fixed positions in the square simulation area, and another where the mobile was simulated to have a two-part constant velocity moving trajectory. A linearized LS algorithm was the first algorithm used to judge the positioning performance. The LS estimator uses a single set of AOA measurements to determine a single mobile position, and was used for both types of position simulation. The fixed position simulation using the LS estimator showed positioning performance of 2.1 m using the ML estimates. The SAGE algorithm esti- mates showed that the LS estimator performs very poorly in the presence of statistically significant outliers. Using PDFs with those outliers, the po- sition estimates could not be relied on, and the ARMSE was larger than the simulation area size, indicating that the position estimates were not useful. The trajectory estimation performance was evaluated using both the LS algorithm and an EKF. The EKF estimates the trajectory of the mobile by using a dynamic model of its movement. In this simulation a constant velocity model was used. The model predicts the movement of the mobile using previous position estimates and uses the AOA observations to refine those position estimates and update the state of the model. In this way, better positioning performance is attained when the mobile movement is similar to that described by the model. Through the estimation of a trajectory, the poor performance of the LS 98 Chapter 6. Conclusions and Future Work algorithm in the presence of outliers was reaffirmed, and observed as very large deviations in the estimated trajectory. The EKF was shown to be more resistant to the effect of outliers, showing no significant deviations in trajectory. This is because the prediction process constrains the position estimates such that it resists large changes in the mobile behaviour not consistent with the dynamic model. Using the ML estimates, the EKF demonstrated position performance of 2.1 m. This study performs a realistic analysis of the potential of 802.11n WLAN APs in performing AOA-based indoor positioning. Similar signals and num- ber of receive antennas were used. The RMS positioning error is approxi- mately 2 m, which is comparable to other WLAN-based positioning schemes. This level of accuracy makes it useful for many different positioning appli- cations, specifically those that require approximately room-level accuracy. RSS positioning techniques already offer approximately this level of accu- racy, and are simpler to implement. However an AOA-based system is more robust to changes in the indoor environment. With more sophisticated sys- tems and more research, AOA-based WLAN positioning should be able to surpass the performance indicated. 6.2 Future Development Future possible research in this area can be classified into two groups: de- velopments leading to positioning performance improvements; and hardware validation of the positioning system using a prototype. 6.2.1 Positioning Performance Improvements To improve positioning performance, there several areas which can be tar- geted. One of the most important is the AOA estimation algorithm, which can be improved in a number of ways. This could include the biasing of a general channel parameter estimation algorithm to estimate multipaths at delays as close to the earliest detectable delay as possible. This should result in improved estimation accuracy. Improvements to the signal model would 99 Chapter 6. Conclusions and Future Work also contribute to better AOA estimates, specifically to more accurately rep- resent the propagation indoors since most signal models make assumptions that may not hold for an indoor environment. This includes the assumption of horizontal propagation as well as the parallel signal arrivals. Implemen- tation of a method to estimate the number of multipaths in the channel could result in improved estimation as well. Further investigation into how suitable other general channel parameter estimation algorithms are for iden- tification of the direct path could result in enhanced accuracy. Modification of these algorithms as well as the development of new algorithms may be necessary, specifically for the purposes of direct path identification. The effectiveness of algorithms in estimating AOA can be improved with a better understanding of the indoor wireless channel. Additional channel measurements would be very useful in confirming some of the phenomena that were observed with the limited set of measurement data available for this study. Additional measurements that better mimic an actual WLAN network would be useful as well. This includes measurements where the APs are at ceiling height, which is typical for most WLAN networks. This would likely confirm that the estimation of the elevation angle is critical to accurate AOA estimation. Also related to the positioning performance are improvements to the specifics of the system such as the addition of more antennas to improve AOA estimation, and the use of a non-linear antenna array to improve the AOA estimation for multipaths arriving at greater elevations. This would also serve to resolve any ambiguity in the mobile direction. For instance, antennas in the vertical plane would allow for elevation estimation, which in turn is likely to improve AOA estimates. An example of a potential antenna array is one that places antennas at the corners of a cube. This allows for the estimation of the elevation as well as allowing for unambiguous AOA estimation. However, this requires eight antennas, which is more than can be expected for a WLAN AP. A suitable antenna array could have antennas at the vertices of a tetrahedron, keeping the number of antennas the same as a WLAN AP and yet addresses both the ambiguity and elevation problem. 100 Chapter 6. Conclusions and Future Work 6.2.2 Prototype Development The final step to proving the concept of a WLAN-based AOA positioning system is the construction of a hardware prototype. This involves the design and construction of multiple base stations to perform the task of the APs, each with a multiple antenna array. A single transmitter would be necessary as well. For ease and flexibility of making changes, programmable technolo- gies such as field programmable gate arrays (FPGAs) and microcontrollers would be good choices for implementation. The APs would be programmed with the AOA estimation algorithms, and then either in real-time or offline the AOAs would be used to determine the mobile position. This validates the positioning accuracy indicated through simulation. The positioning performance could then be characterized by using the system in various indoor environments and conditions. Two different sce- narios would be useful to characterize: when the AP geometry is similar to that of an existing WLAN network, that is, not optimized for the purposes of positioning; and when the APs are placed in such a way as to obtain the most accurate positioning estimates. 101 References [1] Federal Communications Commision, “Wireless 911 Services: FCC Consumer Facts”, [Online], viewed May 8, 2008, available from the World Wide Web: <http://www.fcc.gov/cgb/consumerfacts/wireless911srvc.html>. [2] H. Kuusniemi, A. Wieser, G. Lachapelle, and J. Takala, “User-level reliability monitoring in urban personal satellite-navigation”, Aerospace and Electronic Systems, IEEE Transactions on, vol. 43, no. 4, pp. 1305– 1318, October 2007. [3] Ke Yu, J. Chen, and H.H. Refai, “WLAN-based, indoor medical resi- dents positioning system”, Wireless and Optical Communications Net- works, 2005. WOCN 2005. Second IFIP International Conference on, pp. 556–560, 6-8 March 2005. [4] R. Kaur, V. Defrancesco, and J. Enderle, “Design, development and evaluation of an asset tracking system”, Bioengineering Conference, 2005. Proceedings of the IEEE 31st Annual Northeast, pp. 110–111, April 2005. [5] A. Bhattacharya, S.S. Wang, and M.P. Green, “Early channel reser- vation based on mobile movement”, Global Telecommunications Con- ference, 2003. GLOBECOM ’03. IEEE, vol. 2, pp. 924–928 Vol.2, Dec. 2003. [6] H. Mohamed Yunos, J. Zeyu Gao, and S. Shim, “Wireless advertising’s challenges and opportunities”, Computer, vol. 36, no. 5, pp. 30–37, May 2003. 102 References [7] Yao-Jen Chang, Hung-Huan Liu, Li-Der Chou, Yen-Wen Chen, and Haw-Yun Shin, “A general architecture of mobile social network ser- vices”, Convergence Information Technology, 2007. International Con- ference on, pp. 151–156, Nov. 2007. [8] E. Foxlin, “Pedestrian tracking with shoe-mounted inertial sensors”, Computer Graphics and Applications, IEEE, vol. 25, no. 6, pp. 38–46, Nov.-Dec. 2005. [9] “IEEE draft standard for information technology-telecommunications and information exchange between systems-local and metropolitan area networks-specific requirements-part 11: Wireless LAN medium access control (MAC) and physical layer (PHY) specifications: Amendment 4: Enhancements for higher throughput”, IEEE Unapproved Draft Std P802.11n/D4.00, Mar 2008, 2008. [10] Broadcom Corporation, “802.11n: Next-generation wireless LAN tech- nology white paper”, Apr. 2006. [11] Wi-Fi Alliance, “Wi-fi certified 802.11n draft 2.0: Longer-range, faster- throughput, multimedia-grade wi-fi networks”, 2007. [12] Harish Reddy, M. Girish Chandra, P. Balamuralidhar, S.G. Harihara, K. Bhattacharya, and E. Joseph, “An improved time-of-arrival esti- mation for WLAN-based local positioning”, Communication Systems Software and Middleware, 2007. COMSWARE 2007. 2nd International Conference on, pp. 1–5, Jan. 2007. [13] Fei Peng and Jinyun Zhang, “On residual carrier frequency offset mit- igation for 802.11N”, Acoustics, Speech and Signal Processing, 2007. ICASSP 2007. IEEE International Conference on, vol. 3, pp. III–257– III–260, April 2007. [14] A.J. Paulraj, D.A. Gore, R.U. Nabar, and H. Bolcskei, “An overview of MIMO communications - a key to gigabit wireless”, Proceedings of the IEEE, vol. 92, no. 2, pp. 198–218, Feb 2004. 103 References [15] Azadeh Kushki, Konstantinos N. Plataniotis, and Anastasios N. Venet- sanopoulos, “Kernel-based positioning in wireless local area networks”, Mobile Computing, IEEE Transactions on, vol. 6, no. 6, pp. 689–705, June 2007. [16] A. Kotanen, M. Hannikainen, H. Leppakoski, and T.D. Hamalainen, “Positioning with IEEE 802.11b wireless LAN”, Personal, Indoor and Mobile Radio Communications, 2003. PIMRC 2003. 14th IEEE Pro- ceedings on, vol. 3, pp. 2218–2222 vol.3, 7-10 Sept. 2003. [17] M. Stella, M. Russo, and D. Begusic, “Location determination in indoor environment based on RSS fingerprinting and artificial neural network”, Telecommunications, 2007. ConTel 2007. 9th International Conference on, pp. 301–306, 13-15 June 2007. [18] Skyhook Wireless, “Skyhook Wireless: How It Works > Performance”, [Online], viewed May 8, 2008, available from the World Wide Web: <http://www.skyhookwireless.com/howitworks/performance.php>. [19] WhereNet, “WhereNet products - WhereLan”, [Online], viewed June 18, 2008, available from the World Wide Web: <http://www.wherenet.com/products wherelan.shtml>. [20] Ekahau, “Ekahau - Ekahau RTLS”, [Online], viewed June 18, 2008, available from the World Wide Web: <http://www.ekahau.com/?id=4200>. [21] K. Kaemarungsi and P. Krishnamurthy, “Properties of indoor received signal strength for wlan location fingerprinting”, Mobile and Ubiquitous Systems: Networking and Services, 2004. MOBIQUITOUS 2004. The First Annual International Conference on, pp. 14–23, Aug. 2004. [22] K. Kaemarungsi, “Distribution of wlan received signal strength indica- tion for indoor location determination”, Wireless Pervasive Computing, 2006 1st International Symposium on, pp. 6 pp.–, Jan. 2006. 104 References [23] I. Oppermann, A. Karlsson, and H. Linderback, “Novel phase based, cross-correlation position estimation technique”, Spread Spectrum Techniques and Applications, 2004 IEEE Eighth International Sympo- sium on, pp. 340–346, Aug.-2 Sept. 2004. [24] F. Izquierdo, M. Ciurana, F. Barcelo, J. Paradells, and E. Zola, “Perfor- mance evaluation of a TOA-based trilateration method to locate termi- nals in WLAN”, Wireless Pervasive Computing, 2006 1st International Symposium on, pp. 1–6, Jan. 2006. [25] A.A. Ali, O. Aly, and A.S. Omar, “High resolution WLAN indoor chan- nel parameter estimation and measurements for communication and positioning applications at 2.4, 5.2 and 5.8 GHz”, Radio and Wireless Symposium, 2006 IEEE, pp. 279–282, Jan. 2006. [26] S.A. Golden and S.S. Bateman, “Sensor measurements for Wi-Fi lo- cation with emphasis on time-of-arrival ranging”, Mobile Computing, IEEE Transactions on, vol. 6, no. 10, pp. 1185–1198, Oct. 2007. [27] S. Gezici, Zhi Tian, G.B. Giannakis, H. Kobayashi, A.F. Molisch, H.V. Poor, and Z. Sahinoglu, “Localization via ultra-wideband radios: a look at positioning aspects for future sensor networks”, Signal Processing Magazine, IEEE, vol. 22, no. 4, pp. 70–84, July 2005. [28] J. Barnes, C. Rizos, M. Kanli, and A. Pahwa, “A positioning technol- ogy for classically difficult GNSS environments from locata”, Position, Location, And Navigation Symposium, 2006 IEEE/ION, pp. 715–721, 25-27, 2006. [29] Locata Corporation, “Locata - beyond GPS”, [Online], viewed May 10, 2008, available from the World Wide Web: <http://www.locatacorp.com/technology.html>. [30] Hui Wang, H. Lenz, A. Szabo, J. Bamberger, and U.D. Hanebeck, “WLAN-based pedestrian tracking using particle filters and low-cost MEMS sensors”, Positioning, Navigation and Communication, 2007. WPNC ’07. 4th Workshop on, pp. 1–7, 22-22 March 2007. 105 References [31] R. Singh, M. Guainazzo, and C.S. Regazzoni, “Location determina- tion using wlan in conjunction with gps network (global positioning system)”, Vehicular Technology Conference, 2004. VTC 2004-Spring. 2004 IEEE 59th, vol. 5, pp. 2695–2699 Vol.5, May 2004. [32] M. Gruteser and Xuan Liu, “Protecting privacy, in continuous location- tracking applications”, Security & Privacy, IEEE, vol. 2, no. 2, pp. 28–34, Mar-Apr 2004. [33] J.A. Fessler and A.O. Hero, “Space-alternating generalized expectation- maximization algorithm”, Signal Processing, IEEE Transactions on [see also Acoustics, Speech, and Signal Processing, IEEE Transactions on], vol. 42, no. 10, pp. 2664–2677, Oct 1994. [34] A. Amar and A.J. Weiss, “Advances in direct position determination”, Sensor Array and Multichannel Signal Processing Workshop Proceed- ings, 2004, pp. 584–588, July 2004. [35] Jung-Chieh Chen, Pangan Ting, Ching-Shyang Maa, and Jiunn-Tsair Chen, “Wireless geolocation with TOA/AOA measurements using fac- tor graph and sum-product algorithm”, Vehicular Technology Confer- ence, 2004. VTC2004-Fall. 2004 IEEE 60th, vol. 5, pp. 3526–3529 Vol. 5, Sept. 2004. [36] Chin-Der Wann, Yi-Jing Yeh, and Chih-Sheng Hsueh, “Hybrid TDOA/AOA indoor positioning and tracking using extended Kalman filters”, Vehicular Technology Conference, 2006. VTC 2006-Spring. IEEE 63rd, vol. 3, pp. 1058–1062, May 2006. [37] S. Galler, W. Gerok, J. Schroeder, K. Kyamakya, and T. Kaiser, “Com- bined AOA/TOA UWB localization”, Communications and Informa- tion Technologies, 2007. ISCIT ’07. International Symposium on, pp. 1049–1053, Oct. 2007. [38] Yihong Qi, H. Kobayashi, and H. Suda, “Analysis of wireless geolo- cation in a non-line-of-sight environment”, Wireless Communications, IEEE Transactions on, vol. 5, no. 3, pp. 672–681, March 2006. 106 References [39] Zhang Guoping and S.V. Rao, “Position localization with impulse ul- tra wide band”, Wireless Communications and Applied Computational Electromagnetics, 2005. IEEE/ACES International Conference on, pp. 17–22, April 2005. [40] W. Zhuang, “Performance analysis of GPS carrier phase observable”, Aerospace and Electronic Systems, IEEE Transactions on, vol. 32, no. 2, pp. 754–767, Apr 1996. [41] R. Schroer, “Navigation and landing [a century of powered flight 1903- 2003]”, Aerospace and Electronic Systems Magazine, IEEE, vol. 18, no. 7, pp. 27–36, July 2003. [42] International LORAN Association, “LORAN basics”, [Online], viewed June 24, 2008, available from the World Wide Web: <http://www.loran.org/basics.html>. [43] Arthur O. Bauer, “Some historical and technical aspects of ra- dio navigation, in germany, over the period 1907 to 1945”, [On- line], viewed May 13, 2008, available from the World Wide Web: <http://www.xs4all.nl/ aobauer/Navigati.pdf>. [44] P. Prasithsangaree, P. Krishnamurthy, and P. Chrysanthis, “On indoor position location with wireless LANs”, Personal, Indoor and Mobile Ra- dio Communications, 2002. The 13th IEEE International Symposium on, vol. 2, pp. 720–724 vol.2, 15-18 Sept. 2002. [45] S. Severi, G. Liva, M. Chiani, and D. Dardari, “A new low-complexity user tracking algorithm for wlan-based positioning systems”, Mobile and Wireless Communications Summit, 2007. 16th IST, pp. 1–5, July 2007. [46] A. Kushki, K.N. Plataniotis, A.N. Venetsanopoulos, and C.S. Regaz- zoni, “Radio map fusion for indoor positioning in wireless local area networks”, Information Fusion, 2005 8th International Conference on, vol. 2, pp. 8 pp.–, July 2005. 107 References [47] D. Tse and P. Viswanath, Fundamentals of wireless communication, Cambridge University Press, first edition, 2005. [48] K.I. Pedersen, P.E. Mogensen, and B.H. Fleury, “A stochastic model of the temporal and azimuthal dispersion seen at the base station in out- door propagation environments”, Vehicular Technology, IEEE Trans- actions on, vol. 49, no. 2, pp. 437–447, Mar 2000. [49] A. Forenza and Jr. Heath, R.W., “Performance evaluation of 2-element arrays of circular patch antennas in indoor clustered mimo channels”, Military Communications Conference, 2005. MILCOM 2005. IEEE, pp. 13–19 Vol. 1, Oct. 2005. [50] Kafle P.L., Intarapanich A., Sesay A.B., McRory J., Davies R.J., and McGibney G., “A wideband MIMO channel measurement system for indoor office environment”, in Proceedings of World Wireless Congress 2004, San Francisco, USA, May 2004, pp. 95–100. [51] T.K. Paul and T. Ogunfunmi, “Wireless LAN comes of age: Under- standing the IEEE 802.11n amendment”, Circuits and Systems Maga- zine, IEEE, vol. 8, no. 1, pp. 28–54, Quarter 2008. [52] H. Krim and M. Viberg, “Two decades of array signal processing re- search: the parametric approach”, Signal Processing Magazine, IEEE, vol. 13, no. 4, pp. 67–94, Jul 1996. [53] R. Schmidt, “Multiple emitter location and signal parameter estima- tion”, Antennas and Propagation, IEEE Transactions on [legacy, pre - 1988], vol. 34, no. 3, pp. 276–280, Mar 1986. [54] A.-J. van der Veen, M.C. Vanderveen, and A. Paulraj, “Joint angle and delay estimation using shift-invariance techniques”, Signal Pro- cessing, IEEE Transactions on [see also Acoustics, Speech, and Signal Processing, IEEE Transactions on], vol. 46, no. 2, pp. 405–418, Feb 1998. 108 References [55] K. Bayat and R.S. Adve, “Joint TOA/DOA wireless position loca- tion using Matrix Pencil”, Vehicular Technology Conference, 2004. VTC2004-Fall. 2004 IEEE 60th, vol. 5, pp. 3535–3539 Vol. 5, Sept. 2004. [56] T.K. Moon, “The expectation-maximization algorithm”, Signal Pro- cessing Magazine, IEEE, vol. 13, no. 6, pp. 47–60, Nov 1996. [57] B.H. Fleury, M. Tschudin, R. Heddergott, D. Dahlhaus, and K. Inge- man Pedersen, “Channel parameter estimation in mobile radio environ- ments using the SAGE algorithm”, Selected Areas in Communications, IEEE Journal on, vol. 17, no. 3, pp. 434–450, Mar 1999. [58] Steven M. Kay, Fundamentals of statistical signal processing, Volume I: Estimation Theory, Prentice-Hall, first edition, 1993. [59] J.K. Tugnait, Lang Tong, and Zhi Ding, “Single-user channel estima- tion and equalization”, Signal Processing Magazine, IEEE, vol. 17, no. 3, pp. 16–28, May 2000. [60] M. Wax and T. Kailath, “Detection of signals by information theo- retic criteria”, Acoustics, Speech, and Signal Processing [see also IEEE Transactions on Signal Processing], IEEE Transactions on, vol. 33, no. 2, pp. 387–392, Apr 1985. [61] M. S. Grewal and A. P. Andrews, Kalman Filtering: Theory and Prac- tice Using MATLAB, Wiley-Interscience, second edition, 2001. [62] A.G. Dempster, “Dilution of precision in angle-of-arrival positioning systems”, Electronics Letters, vol. 42, no. 5, pp. 291–292, March 2006. [63] K. Spingarn, “Passive position location estimation using the extended kalman filter”, Aerospace and Electronic Systems, IEEE Transactions on, vol. AES-23, no. 4, pp. 558–567, July 1987. 109 Appendix A: ML Estimation Statistics This appendix includes the statistics for the simplified ML algorithm AOA estimates in the various indoor situations. The estimates for the measure- ments used at 300 MHz and 40 MHz are included, as well as those with the SNR lowered to 20 dB with the addition of noise. The first and second or- der statistics, mean µ and standard deviation σ, are contained in Table A.1. The measurements that contain significant statistical outliers, those that have additional lobes with large error far from the main lobes, are noted in the comments. The PDFs derived from the histograms of the estimates are shown in Figures A.1 - A.9. 110 Appendix A: ML Estimation Statistics T ab le A .1 : M ea n an d st an da rd de vi at io n of th e M L A O A es ti m at es fo r th e in do or m ea su re m en ts . B an dw id th (M H z) N oi se A dd ed O bs tr uc ti on φ (◦ ) P D F F ig ur e µ (◦ ) σ (◦ ) C om m en ts 40 L O S 90 A .7 (a ) -0 .2 1 7. 74 Y Si ng le w al l 90 A .8 (a ) 4. 41 8. 48 O ut lie rs D ou bl e w al l 90 A .9 (a ) -2 .5 3 7. 13 L O S 45 A .7 (b ) 5. 15 6. 14 O ut lie rs Y Si ng le w al l 45 A .8 (b ) 7. 36 4. 63 D ou bl e w al l 45 A .9 (b ) -1 .1 7 4. 75 L O S 90 A .4 (a ) -1 .3 8 8. 05 N Si ng le w al l 90 A .5 (a ) 0. 45 1. 72 D ou bl e w al l 90 A .6 (a ) -1 .5 3 6. 39 L O S 45 A .4 (b ) 3. 93 5. 44 O ut lie rs N Si ng le w al l 45 A .5 (b ) 10 .8 6 1. 79 D ou bl e w al l 45 A .6 (b ) -0 .6 3 5. 57 30 0 L O S 90 A .1 (a ) 2. 26 10 .8 6 N Si ng le w al l 90 A .2 (a ) 0. 87 1. 67 D ou bl e w al l 90 A .3 (a ) 1. 05 6. 28 L O S 45 A .1 (b ) 6. 14 13 .5 9 O ut lie rs N Si ng le w al l 45 A .2 (b ) 10 .5 2 2. 27 D ou bl e w al l 45 A .3 (b ) 0. 50 6. 30 111 Appendix A: ML Estimation Statistics −20 −10 0 10 20 30 40 0 2 4 6 8 AOA Estimation Error (degrees) f(x ) (a) AOA of φ = 90◦. −20 0 20 40 0 1 2 3 4 5 6 7 8 AOA Estimation Error (degrees) f(x ) (b) AOA of φ = 45◦. Figure A.1: PDF of the ML AOA estimation error for the LOS measure- ments using 300 MHz bandwidth. −5 0 5 10 0 5 10 15 AOA Estimation Error (degrees) f(x ) (a) AOA of φ = 90◦. 0 5 10 15 20 25 30 0 5 10 15 AOA Estimation Error (degrees) f(x ) (b) AOA of φ = 45◦. Figure A.2: PDF of the ML AOA estimation error for the single wall mea- surements using 300 MHz bandwidth. 112 Appendix A: ML Estimation Statistics −20 −10 0 10 20 0 1 2 3 4 5 6 AOA Estimation Error (degrees) f(x ) (a) AOA of φ = 90◦. −20 −10 0 10 20 0 2 4 6 8 AOA Estimation Error (degrees) f(x ) (b) AOA of φ = 45◦. Figure A.3: PDF of the ML AOA estimation error for the double wall mea- surements using 300 MHz bandwidth. −20 −10 0 10 20 30 0 1 2 3 4 5 6 7 AOA Estimation Error (degrees) f(x ) (a) AOA of φ = 90◦. −10 0 10 20 30 40 0 1 2 3 4 5 6 7 8 AOA Estimation Error (degrees) f(x ) (b) AOA of φ = 45◦. Figure A.4: PDF of the ML AOA estimation error for the LOS measure- ments using 40 MHz bandwidth. 113 Appendix A: ML Estimation Statistics −5 0 5 0 5 10 15 AOA Estimation Error (degrees) f(x ) (a) AOA of φ = 90◦. 0 5 10 15 20 0 5 10 15 20 AOA Estimation Error (degrees) f(x ) (b) AOA of φ = 45◦. Figure A.5: PDF of the ML AOA estimation error for the single wall mea- surements using 40 MHz bandwidth. −20 −10 0 10 20 0 1 2 3 4 5 6 7 AOA Estimation Error (degrees) f(x ) (a) AOA of φ = 90◦. −15 −10 −5 0 5 10 15 0 2 4 6 8 10 AOA Estimation Error (degrees) f(x ) (b) AOA of φ = 45◦. Figure A.6: PDF of the ML AOA estimation error for the double wall mea- surements using 40 MHz bandwidth. 114 Appendix A: ML Estimation Statistics −20 −10 0 10 20 30 40 0 1 2 3 4 5 AOA Estimation Error (degrees) f(x ) (a) AOA of φ = 90◦. −20 0 20 40 0 1 2 3 4 5 6 7 8 AOA Estimation Error (degrees) f(x ) (b) AOA of φ = 45◦. Figure A.7: PDF of the ML AOA estimation error for the LOS measure- ments using 40 MHz bandwidth with SNR lowered to 20 dB. −40 −20 0 20 0 1 2 3 4 5 6 AOA Estimation Error (degrees) f(x ) (a) AOA of φ = 90◦. −5 0 5 10 15 20 25 0 1 2 3 4 5 6 7 8 AOA Estimation Error (degrees) f(x ) (b) AOA of φ = 45◦. Figure A.8: PDF of the ML AOA estimation error for the single wall mea- surements using 40 MHz bandwidth with SNR lowered to 20 dB. 115 Appendix A: ML Estimation Statistics −20 −10 0 10 20 0 1 2 3 4 5 6 AOA Estimation Error (degrees) f(x ) (a) AOA of φ = 90◦. −15 −10 −5 0 5 10 0 2 4 6 8 10 AOA Estimation Error (degrees) f(x ) (b) AOA of φ = 45◦. Figure A.9: PDF of the ML AOA estimation error for the double wall mea- surements using 40 MHz bandwidth with SNR lowered to 20 dB. 116 Appendix B: SAGE Estimation Statistics This appendix includes the statistics for the SAGE algorithm AOA esti- mates in the various indoor situations. The algorithm estimates a total of 3 multipath arrivals. The estimates for the measurements used at 300 MHz and 40 MHz are included. The first and second order statistics, mean µ and standard deviation σ, are contained in Table B.1. The measurements that contain significant statistical outliers, those that have additional lobes with large error far from the main lobes, are noted in the comments. The PDFs derived from the histograms of the estimates are shown in Figures B.1 - B.6. 117 Appendix B: SAGE Estimation Statistics T ab le B .1 : M ea n an d st an da rd de vi at io n of th e SA G E A O A es ti m at es fo r th e in do or m ea su re m en ts . B an dw id th (M H z) O bs tr uc ti on φ (◦ ) P D F F ig ur e µ (◦ ) σ (◦ ) C om m en ts 40 L O S 90 B .4 (a ) 6. 76 10 .8 7 O ut lie rs Si ng le w al l 90 B .5 (a ) 6. 48 5. 39 D ou bl e w al l 90 B .6 (a ) -5 .9 2 14 .2 3 O ut lie rs L O S 45 B .4 (b ) 15 .1 5 2. 06 Si ng le w al l 45 B .5 (b ) 30 .1 0 22 .1 7 O ut lie rs D ou bl e w al l 45 B .6 (b ) 32 .4 5 33 .2 9 O ut lie rs 30 0 L O S 90 B .1 (a ) 5. 41 4. 39 Si ng le w al l 90 B .2 (a ) 7. 60 2. 14 D ou bl e w al l 90 B .3 (a ) -0 .0 6 6. 66 L O S 45 B .1 (b ) 19 .2 5 10 .7 8 O ut lie rs Si ng le w al l 45 B .2 (b ) 29 .4 7 18 .8 3 O ut lie rs D ou bl e w al l 45 B .3 (b ) 19 .8 6 24 .5 7 O ut lie rs 118 Appendix B: SAGE Estimation Statistics −5 0 5 10 15 0 5 10 15 20 25 AOA Estimation Error (degrees) f(x ) (a) AOA of φ = 90◦. 10 20 30 40 50 60 70 0 2 4 6 8 10 12 14 16 AOA Estimation Error (degrees) f(x ) (b) AOA of φ = 45◦. Figure B.1: PDF of the SAGE AOA estimation error for the LOS measure- ments using 300 MHz bandwidth. 4 6 8 10 12 0 5 10 15 20 25 30 35 40 AOA Estimation Error (degrees) f(x ) (a) AOA of φ = 90◦. 10 20 30 40 50 60 0 5 10 15 20 25 30 35 AOA Estimation Error (degrees) f(x ) (b) AOA of φ = 45◦. Figure B.2: PDF of the SAGE AOA estimation error for the single wall measurements using 300 MHz bandwidth. 119 Appendix B: SAGE Estimation Statistics −15 −10 −5 0 5 10 15 0 5 10 15 20 25 AOA Estimation Error (degrees) f(x ) (a) AOA of φ = 90◦. 0 20 40 60 80 0 2 4 6 8 AOA Estimation Error (degrees) f(x ) (b) AOA of φ = 45◦. Figure B.3: PDF of the SAGE AOA estimation error for the double wall measurements using 300 MHz bandwidth. −10 0 10 20 30 40 0 5 10 15 20 25 AOA Estimation Error (degrees) f(x ) (a) AOA of φ = 90◦. 10 12 14 16 18 20 0 5 10 15 20 25 AOA Estimation Error (degrees) f(x ) (b) AOA of φ = 45◦. Figure B.4: PDF of the SAGE AOA estimation error for the LOS measure- ments using 40 MHz bandwidth. 120 Appendix B: SAGE Estimation Statistics −5 0 5 10 15 0 5 10 15 20 25 30 AOA Estimation Error (degrees) f(x ) (a) AOA of φ = 90◦. 10 20 30 40 50 60 0 5 10 15 20 AOA Estimation Error (degrees) f(x ) (b) AOA of φ = 45◦. Figure B.5: PDF of the SAGE AOA estimation error for the single wall measurements using 40 MHz bandwidth. −60 −40 −20 0 20 0 2 4 6 8 10 12 AOA Estimation Error (degrees) f(x ) (a) AOA of φ = 90◦. 0 20 40 60 80 0 2 4 6 8 10 AOA Estimation Error (degrees) f(x ) (b) AOA of φ = 45◦. Figure B.6: PDF of the SAGE AOA estimation error for the double wall measurements using 40 MHz bandwidth. 121 Appendix C: Positioning Simulation Results This appendix includes the positioning error for the two different simula- tions, using the PDFs contained in Appendices A and B. Table C.1 contains the simulation results in terms of the position ARMSE for the fixed position simulation. Only the LS algorithm was used to deter- mine the mobile position. Table C.2 contains the simulation results in terms of the position ARMSE for the two-part constant velocity trajectory simulation. For this simulation, both the LS and EKF were used to estimate the mobile position. The improvement in positioning performance for the EKF over LS is shown as well. When the improvement is very large, a ’+’ symbol is used. In both tables, ’-’ indicates very large positioning error, >> 40 m. In the trajectory simulation, this large positioning error is caused by the inclusion of divergent positioning solutions in the RMS calculations. In addition, the PDFs that have been considered to have outliers are indicated. 122 Appendix C: Positioning Simulation Results T ab le C .1 : F ix ed po si ti on si m ul at io n A R M SE fo r th e va ri ou s in do or m ea su re m en t ty pe s. E st im at or B an dw id th (M H z) O bs tr uc ti on φ (◦ ) P D F F ig ur e L S A R M SE (m ) P D F N ot es M L 40 L O S 90 A .4 (a ) 3. 01 40 Si ng le w al l 90 A .5 (a ) 0. 79 40 D ou bl e w al l 90 A .6 (a ) 2. 81 40 L O S 45 A .4 (b ) 2. 54 40 Si ng le w al l 45 A .5 (b ) 4. 49 40 D ou bl e w al l 45 A .6 (b ) 1. 85 30 0 L O S 90 A .1 (a ) 4. 31 30 0 Si ng le w al l 90 A .2 (a ) 0. 85 30 0 D ou bl e w al l 90 A .3 (a ) 2. 68 30 0 L O S 45 A .1 (b ) - O ut lie rs 30 0 Si ng le w al l 45 A .2 (b ) 4. 64 30 0 D ou bl e w al l 45 A .3 (b ) 2. 02 SA G E 40 L O S 90 B .4 (a ) 5. 36 O ut lie rs 40 Si ng le w al l 90 B .5 (a ) 3. 69 40 D ou bl e w al l 90 B .6 (a ) - O ut lie rs 40 L O S 45 B .4 (b ) 7. 18 40 Si ng le w al l 45 B .5 (b ) - O ut lie rs 40 D ou bl e w al l 45 B .6 (b ) - O ut lie rs 30 0 L O S 90 B .1 (a ) 2. 67 30 0 Si ng le w al l 90 B .2 (a ) 3. 42 30 0 D ou bl e w al l 90 B .3 (a ) 2. 87 30 0 L O S 45 B .1 (b ) 17 .8 4 O ut lie rs 30 0 Si ng le w al l 45 B .2 (b ) - O ut lie rs 30 0 D ou bl e w al l 45 B .3 (b ) - O ut lie rs 123 Appendix C: Positioning Simulation Results T ab le C .2 : T ra je ct or y si m ul at io n A R M SE fo r th e va ri ou s in do or m ea su re m en t ty pe s. E st im at or B an dw id th (M H z) O bs tr uc ti on φ (◦ ) P D F F ig ur e A R M SE (m ) A R M SE P D F N ot es L S E K F L S/ E K F M L 40 L O S 90 A .4 (a ) - 2. 17 + 40 Si ng le w al l 90 A .5 (a ) 0. 75 0. 47 1. 60 40 D ou bl e w al l 90 A .6 (a ) - 1. 76 + 40 L O S 45 A .4 (b ) - 1. 94 + 40 Si ng le w al l 45 A .5 (b ) 4. 49 4. 84 0. 93 40 D ou bl e w al l 45 A .6 (b ) - 1. 16 + 30 0 L O S 90 A .1 (a ) - 3. 11 + 30 0 Si ng le w al l 90 A .2 (a ) 0. 77 0. 51 1. 51 30 0 D ou bl e w al l 90 A .3 (a ) 2. 75 1. 68 1. 64 30 0 L O S 45 A .1 (b ) - 4. 01 + O ut lie rs 30 0 Si ng le w al l 45 A .2 (b ) - 4. 62 + 30 0 D ou bl e w al l 45 A .3 (b ) - 1. 30 + SA G E 40 L O S 90 B .4 (a ) - 3. 38 + O ut lie rs 40 Si ng le w al l 90 B .5 (a ) - 2. 81 + 40 D ou bl e w al l 90 B .6 (a ) - 4. 24 + O ut lie rs 40 L O S 45 B .4 (b ) - 6. 52 + 40 Si ng le w al l 45 B .5 (b ) - 20 .9 5 + O ut lie rs 40 D ou bl e w al l 45 B .6 (b ) - 27 .6 1 + O ut lie rs 30 0 L O S 90 B .1 (a ) - 2. 30 + 30 0 Si ng le w al l 90 B .2 (a ) 2. 97 3. 03 0. 98 30 0 D ou bl e w al l 90 B .3 (a ) - 1. 75 + 30 0 L O S 45 B .1 (b ) - 8. 12 + O ut lie rs 30 0 Si ng le w al l 45 B .2 (b ) - 16 .8 4 + O ut lie rs 30 0 D ou bl e w al l 45 B .3 (b ) - 13 .3 4 + O ut lie rs 124
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Investigation of wireless local area network facilitated...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Investigation of wireless local area network facilitated angle of arrival indoor location Wong, Carl Monway 2008
pdf
Page Metadata
Item Metadata
Title | Investigation of wireless local area network facilitated angle of arrival indoor location |
Creator |
Wong, Carl Monway |
Publisher | University of British Columbia |
Date Issued | 2008 |
Description | As wireless devices become more common, the ability to position a wireless device has become a topic of importance. Accurate positioning through technologies such as the Global Positioning System is possible for outdoor environments. Indoor environments pose a different challenge, and research continues to position users indoors. Due to the prevalence of wireless local area networks (WLANs) in many indoor spaces, it is prudent to determine their capabilities for the purposes of positioning. Signal strength and time based positioning systems have been studied for WLANs. Direction or angle of arrival (AOA) based positioning will be possible with multiple antenna arrays, such as those included with upcoming devices based on the IEEE 802.11n standard. The potential performance of such a system is evaluated. The positioning performance of such a system depends on the accuracy of the AOA estimation as well as the positioning algorithm. Two different maximum-likelihood (ML) derived algorithms are used to determine the AOA of the mobile user: a specialized simple ML algorithm, and the space- alternating generalized expectation-maximization (SAGE) channel parameter estimation algorithm. The algorithms are used to determine the error in estimating AOAs through the use of real wireless signals captured in an indoor office environment. The statistics of the AOA error are used in a positioning simulation to predict the positioning performance. A least squares (LS) technique as well as the popular extended Kalman filter (EKF) are used to combine the AOAs to determine position. The position simulation shows that AOA- based positioning using WLANs indoors has the potential to position a wireless user with an accuracy of about 2 m. This is comparable to other positioning systems previously developed for WLANs. |
Extent | 2099293 bytes |
Subject |
Wireless local area network Angle of arrival based positioning Least squares technique Kalman filter Simulation |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2008-11-18 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0066798 |
URI | http://hdl.handle.net/2429/2792 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical Engineering |
Affiliation |
Applied Science, Faculty of Engineering, School of (Okanagan) |
Degree Grantor | University of British Columbia |
GraduationDate | 2008-11 |
Campus |
UBCO |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2008_fall_wong_carl.pdf [ 2MB ]
- Metadata
- JSON: 24-1.0066798.json
- JSON-LD: 24-1.0066798-ld.json
- RDF/XML (Pretty): 24-1.0066798-rdf.xml
- RDF/JSON: 24-1.0066798-rdf.json
- Turtle: 24-1.0066798-turtle.txt
- N-Triples: 24-1.0066798-rdf-ntriples.txt
- Original Record: 24-1.0066798-source.json
- Full Text
- 24-1.0066798-fulltext.txt
- Citation
- 24-1.0066798.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}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0066798/manifest