Investigation of Wireless Local AreaNetwork Facilitated Angle of ArrivalIndoor LocationbyCarl Monway WongA THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF APPLIED SCIENCEinThe College of Graduate Studies(Applied Science)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)August, 2008c Carl Monway Wong 2008AbstractAs wireless devices become more common, the ability to position a wirelessdevice has become a topic of importance. Accurate positioning throughtechnologies such as the Global Positioning System is possible for outdoorenvironments. Indoor environments pose a di erent challenge, and researchcontinues to position users indoors. Due to the prevalence of wireless localarea networks (WLANs) in many indoor spaces, it is prudent to determinetheir capabilities for the purposes of positioning. Signal strength and timebased positioning systems have been studied for WLANs. Direction or angleof arrival (AOA) based positioning will be possible with multiple antennaarrays, such as those included with upcoming devices based on the IEEE802.11n standard. The potential performance of such a system is evaluated.The positioning performance of such a system depends on the accuracyof the AOA estimation as well as the positioning algorithm. Two di er-ent maximum-likelihood (ML) derived algorithms are used to determine theAOA 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 errorin estimating AOAs through the use of real wireless signals captured in anindoor o ce environment.The statistics of the AOA error are used in a positioning simulationto predict the positioning performance. A least squares (LS) technique aswell as the popular extended Kalman lter (EKF) are used to combine theAOAs to determine position. The position simulation shows that AOA-based positioning using WLANs indoors has the potential to position awireless user with an accuracy of about 2 m. This is comparable to otherpositioning systems previously developed for WLANs.iiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . xiList of Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . xvDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xviChapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . 11.1 Motivation and Applications . . . . . . . . . . . . . . . . . . 21.2 Wireless Positioning . . . . . . . . . . . . . . . . . . . . . . . 21.3 Indoor Wireless Positioning . . . . . . . . . . . . . . . . . . . 31.4 Network and Mobile Positioning . . . . . . . . . . . . . . . . 51.5 Wireless Local Area Networks . . . . . . . . . . . . . . . . . 61.6 Multiple-Input Multiple-Output . . . . . . . . . . . . . . . . 71.7 WLAN Positioning . . . . . . . . . . . . . . . . . . . . . . . 81.8 Research Objectives . . . . . . . . . . . . . . . . . . . . . . . 101.9 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . 121.10 Thesis Overview . . . . . . . . . . . . . . . . . . . . . . . . . 12iiiTable of ContentsChapter 2 Positioning . . . . . . . . . . . . . . . . . . . . . . . . 142.1 Positioning Methods . . . . . . . . . . . . . . . . . . . . . . . 142.1.1 Lines of Position . . . . . . . . . . . . . . . . . . . . . 152.1.2 Positioning Accuracy . . . . . . . . . . . . . . . . . . 162.2 Time of Arrival Positioning . . . . . . . . . . . . . . . . . . . 172.3 Time Di erence of Arrival Positioning . . . . . . . . . . . . . 192.4 Angle of Arrival Positioning . . . . . . . . . . . . . . . . . . 212.5 Received Signal Strength Positioning . . . . . . . . . . . . . 23Chapter 3 The Indoor Wireless Channel . . . . . . . . . . . . 253.1 Multipath and the Channel Impulse Response . . . . . . . . 253.2 Properties of the Wireless Channel . . . . . . . . . . . . . . . 273.2.1 Delay Spread and Time Density . . . . . . . . . . . . 273.2.2 Angle Spread . . . . . . . . . . . . . . . . . . . . . . . 283.3 Channel Sounding System . . . . . . . . . . . . . . . . . . . 293.3.1 Antenna Array . . . . . . . . . . . . . . . . . . . . . . 313.3.2 Transmitter . . . . . . . . . . . . . . . . . . . . . . . 313.3.3 Receiver . . . . . . . . . . . . . . . . . . . . . . . . . 333.3.4 Equipment Calibration . . . . . . . . . . . . . . . . . 333.3.5 Channel Impulse Response Estimation . . . . . . . . 363.4 Indoor Channel Measurements . . . . . . . . . . . . . . . . . 37Chapter 4 Angle of Arrival Estimation . . . . . . . . . . . . . 414.1 Signal Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 424.2 Cram er-Rao Lower Bound . . . . . . . . . . . . . . . . . . . 444.3 General Channel Parameter Estimation . . . . . . . . . . . . 474.3.1 Maximum Likelihood Channel Parameter Estimation 484.3.2 Expectation-Maximization Channel Parameter Esti-mation . . . . . . . . . . . . . . . . . . . . . . . . . . 504.3.3 Space-Alternating Generalized Expectation-MaximizationChannel Parameter Estimation . . . . . . . . . . . . . 524.3.4 SAGE Implementation . . . . . . . . . . . . . . . . . 544.3.5 Determining AOA from Channel Parameters . . . . . 55ivTable of Contents4.3.6 Estimation of Number of Multipath Arrivals . . . . . 564.4 Simpli ed ML AOA Implementation . . . . . . . . . . . . . . 574.5 ML Estimation Performance . . . . . . . . . . . . . . . . . . 594.6 SAGE Estimation Performance . . . . . . . . . . . . . . . . . 654.7 Estimation Performance Summary . . . . . . . . . . . . . . . 70Chapter 5 Positioning Simulation . . . . . . . . . . . . . . . . . 715.1 Random AOA Generation . . . . . . . . . . . . . . . . . . . . 715.2 AOA Least Squares Positioning . . . . . . . . . . . . . . . . 725.3 Extended Kalman Filter . . . . . . . . . . . . . . . . . . . . 755.4 AP Geometry Considerations . . . . . . . . . . . . . . . . . . 795.5 Positioning Performance . . . . . . . . . . . . . . . . . . . . 805.5.1 Fixed Position Estimation Performance . . . . . . . . 835.5.2 Trajectory Estimation Performance . . . . . . . . . . 89Chapter 6 Conclusions and Future Work . . . . . . . . . . . . 956.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 956.1.1 AOA Estimation . . . . . . . . . . . . . . . . . . . . . 956.1.2 Position Estimation . . . . . . . . . . . . . . . . . . . 986.2 Future Development . . . . . . . . . . . . . . . . . . . . . . . 996.2.1 Positioning Performance Improvements . . . . . . . . 996.2.2 Prototype Development . . . . . . . . . . . . . . . . . 101References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102AppendicesAppendix A: ML Estimation Statistics . . . . . . . . . . . . . . 110Appendix B: SAGE Estimation Statistics . . . . . . . . . . . . 117Appendix C: Positioning Simulation Results . . . . . . . . . . 122vList of Tables3.1 Transmitter and receiver locations for the various indoor mea-surement situations. . . . . . . . . . . . . . . . . . . . . . . . 403.2 Approximate SNR for the various indoor measurement situ-ations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.1 Example SAGE and ML estimated channel parameters for anLOS measurement, with actual AOA of 90 . . . . . . . . . . . 69A.1 Mean and standard deviation of the ML AOA estimates forthe indoor measurements. . . . . . . . . . . . . . . . . . . . . 111B.1 Mean and standard deviation of the SAGE AOA estimatesfor the indoor measurements. . . . . . . . . . . . . . . . . . . 118C.1 Fixed position simulation ARMSE for the various indoor mea-surement types. . . . . . . . . . . . . . . . . . . . . . . . . . . 123C.2 Trajectory simulation ARMSE for the various indoor mea-surement types. . . . . . . . . . . . . . . . . . . . . . . . . . . 124viList of Figures1.1 Multipath in an LOS situation between transmitter and re-ceiver. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2 Multipath in an NLOS situation between transmitter and re-ceiver. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.1 How DOP varies based on the intersection of the lines ofposition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.2 Example of circles of position for TOA-based positioning us-ing three APs. . . . . . . . . . . . . . . . . . . . . . . . . . . 182.3 Example of hyperbolas of position for TDOA-based position-ing using three APs. . . . . . . . . . . . . . . . . . . . . . . . 202.4 Example of lines of position for AOA-based positioning usingthree APs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.1 Example multipath in an indoor wireless channel in terms ofamplitude, delay and AOA. . . . . . . . . . . . . . . . . . . . 283.2 Example of amplitudes at various delays in an indoor wirelesschannel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.3 Example of AOAs at various delays in an indoor wireless chan-nel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.4 Autocorrelation of PN sequence of length K as a function ofsequence o set t. . . . . . . . . . . . . . . . . . . . . . . . . . 313.5 Photo of the four-antenna linear monopole array used fortransmission and reception. . . . . . . . . . . . . . . . . . . . 323.6 Ideal received signal from all transmit antennas after correla-tion with the transmit sequence. . . . . . . . . . . . . . . . . 33viiList of Figures3.7 Hardware con guration for the transmitter. . . . . . . . . . . 343.8 Photo of the transmitter equipment. . . . . . . . . . . . . . . 343.9 Hardware con guration for the receiver. . . . . . . . . . . . . 353.10 Photo of the receiver equipment. . . . . . . . . . . . . . . . . 353.11 Con guration for relative phase and amplitude calibrationbetween the receiver channels. . . . . . . . . . . . . . . . . . . 363.12 Example CIR generated from a channel measurement. . . . . 383.13 Map of University of Calgary Information and Communica-tions Technology building third oor with receiver and trans-mitter positions. . . . . . . . . . . . . . . . . . . . . . . . . . 394.1 Diagram of the arriving signal for multipath component l atthe four element linear monopole array. . . . . . . . . . . . . 434.2 AOA estimation error of ML algorithm in various indoor sit-uations at 300 MHz bandwidth. . . . . . . . . . . . . . . . . . 604.3 AOA estimation error of ML algorithm in various indoor sit-uations at 40 MHz bandwidth. . . . . . . . . . . . . . . . . . 604.4 AOA estimation error of ML algorithm in various indoor sit-uations at 40 MHz bandwidth with SNR lowered to 20 dB. . 624.5 The additional propagation distance to each receive antennagiven azimuth angle and elevation angle !. . . . . . . . . . 644.6 AOA estimation mean error of SAGE algorithm in variousindoor situations at 300 MHz bandwidth, using varying num-bers of total estimated multipath arrivals. . . . . . . . . . . . 664.7 AOA estimation error standard deviation of SAGE algorithmin various indoor situations at 300 MHz bandwidth, usingvarying numbers of total estimated multipath arrivals. . . . . 664.8 AOA estimation error of SAGE algorithm in various indoorsituations at 300 MHz bandwidth, using 3 total estimatedmultipath arrivals. . . . . . . . . . . . . . . . . . . . . . . . . 684.9 AOA estimation error of SAGE algorithm in various indoorsituations at 40 MHz bandwidth, using 3 total estimated mul-tipath arrivals. . . . . . . . . . . . . . . . . . . . . . . . . . . 68viiiList of Figures5.1 Example CDF generated from the PDF in Figure A.6(a). . . 725.2 DOP for the northing and easting directions for AOA posi-tioning in units of metres per radian. . . . . . . . . . . . . . . 815.3 DOP correlation and HDOP for AOA positioning. . . . . . . 815.4 Example estimated positions depending on correlation be-tween DOP in northing and easting directions. . . . . . . . . 825.5 LS initial position estimates based on approximate area. . . . 845.6 RMS position error in metres from 1000 Monte Carlo simu-lation trials, using AOA error generated from Figure A.5(a). . 865.7 Number of converged position estimates out of 1000 MonteCarlo simulation trials, using AOA error generated from Fig-ure A.5(a). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 865.8 RMS position error in metres from 1000 Monte Carlo simu-lation trials, using AOA error generated from Figure A.6(a). . 875.9 Number of converged position estimates out of 1000 MonteCarlo simulation trials, using AOA error generated from Fig-ure A.6(a). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 875.10 RMS position error divided by the AOA error standard devi-ation in metres per radian from 1000 Monte Carlo simulationtrials, using AOA error generated from Figure A.6(a). . . . . 885.11 Typical example trajectory simulation trial with LS and EKFusing AOA error from ML estimates PDF shown in FigureA.6(a). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 915.12 Worst case example trajectory simulation trial with LS andEKF using AOA error with signi cant outliers from SAGEalgorithm using the PDF shown in Figure B.4(a). . . . . . . . 915.13 Best case example trajectory simulation trial with LS andEKF using AOA error from ML estimates PDF shown in Fig-ure A.5(a). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 925.14 Example trajectory simulation run with EKF showing e ectof mobile movement not matching dynamic model. . . . . . . 93ixList of FiguresA.1 PDF of the ML AOA estimation error for the LOS measure-ments using 300 MHz bandwidth. . . . . . . . . . . . . . . . . 112A.2 PDF of the ML AOA estimation error for the single wallmeasurements using 300 MHz bandwidth. . . . . . . . . . . . 112A.3 PDF of the ML AOA estimation error for the double wallmeasurements using 300 MHz bandwidth. . . . . . . . . . . . 113A.4 PDF of the ML AOA estimation error for the LOS measure-ments using 40 MHz bandwidth. . . . . . . . . . . . . . . . . 113A.5 PDF of the ML AOA estimation error for the single wallmeasurements using 40 MHz bandwidth. . . . . . . . . . . . . 114A.6 PDF of the ML AOA estimation error for the double wallmeasurements using 40 MHz bandwidth. . . . . . . . . . . . . 114A.7 PDF of the ML AOA estimation error for the LOS measure-ments using 40 MHz bandwidth with SNR lowered to 20 dB. 115A.8 PDF of the ML AOA estimation error for the single wallmeasurements using 40 MHz bandwidth with SNR loweredto 20 dB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115A.9 PDF of the ML AOA estimation error for the double wallmeasurements using 40 MHz bandwidth with SNR loweredto 20 dB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116B.1 PDF of the SAGE AOA estimation error for the LOS mea-surements using 300 MHz bandwidth. . . . . . . . . . . . . . 119B.2 PDF of the SAGE AOA estimation error for the single wallmeasurements using 300 MHz bandwidth. . . . . . . . . . . . 119B.3 PDF of the SAGE AOA estimation error for the double wallmeasurements using 300 MHz bandwidth. . . . . . . . . . . . 120B.4 PDF of the SAGE AOA estimation error for the LOS mea-surements using 40 MHz bandwidth. . . . . . . . . . . . . . . 120B.5 PDF of the SAGE AOA estimation error for the single wallmeasurements using 40 MHz bandwidth. . . . . . . . . . . . . 121B.6 PDF of the SAGE AOA estimation error for the double wallmeasurements using 40 MHz bandwidth. . . . . . . . . . . . . 121xList of AbbreviationsAOA angle of arrivalAP access pointARMSE average root mean squared errorAWG arbitrary waveform generatorBLUE best linear unbiased estimatorBPF bandpass lterCDF cumulative density functionCIR channel impulse responseCRLB Cram er-Rao lower bounddB decibelsdBm decibels relative to 1 mWDOP dilution of precisionEDOP easting dilution of precisionEKF extended Kalman lterEM expectation-maximizationESPRIT estimation of signal parameters via rotational invariancetechniqueFCC Federal Communications CommisionFIM Fisher information matrixFPGA eld programmable gate arrayGNSS global navigation satellite systemGPS Global Positioning SystemHDOP horizontal dilution of precisionLAN local area networkLO local oscillatorLORAN Long Range NavigationxiList of AbbreviationsLOS line-of-sightLPF lowpass lterLS least squaresMEMS microelectromechanical systemsMIMO multiple-input multiple-outputMISO multiple-input single-outputML maximum likelihoodMUSIC multiple signal classi cationNDOP northing dilution of precisionNLOS non-line-of-sightOFDM orthogonal frequency division multiplexingPDF probability density functionPN pseudorandom noiseRF radio frequencyRMS root mean squareRSS received signal strengthRX receiverSAGE space-alternating generalized expectation-maximizationSIMO single-input multiple-outputSISO single-input single-outputSNR signal to noise ratioTDOA time di erence of arrivalTOA time of arrivalTX transmitterUWB ultrawidebandWLAN wireless local area networkxiiList of SymbolsIn the listed symbols b denotes a scalar parameter and b denotes a matrixor vector parameter.A design matrixa(t) autocorrelation function for transmitted signalbH Hermitian (complex conjugate and transpose)bT matrix transpose^b estimateb complex conjugateEfbg expected valueErms RMS position errorF Fisher Information Matrixh channel impulse response vectorh(t) channel impulse responseI identity matrixKn Kalman gain matrixL number of multipath arrivalsM number of receive antennasN independent complex white Gaussian noise processp(b) probability density functionPn ( ) state covariance matrix prior to inclusion of observationsPn (+) state covariance matrix after inclusion of observationsPu transmitted signal powerQ dynamic model error covariance matrixR observations error covariance matrixs signal for a single multipath arrivalxiiiList of SymbolsTu period of the transmitted sequencew misclosure vector^xn ( ) predicted state estimate before inclusion of observations^xn (+) state estimate after inclusion of observationsY received signal vectorYm 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 operationjbj absolute value dot product<fbg real partxivAcknowledgmentsI 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. Geo rey Messier andDr. Richard Klukas for their invaluable help and support, in guiding mesmoothly through my research.I would like to thank Glenn MacGougan, a PhD candidate at the SchulichSchool of Engineering at the University of Calgary in the Department ofGeomatics Engineering, for helping me perform the survey that allowed meto know the positions and orientations of the transmitter and receiver.xvDedicationDedicated to my family without whom my higher education would not havebeen possible.xviChapter 1IntroductionA large proportion of the electronic devices being introduced to the marketrequire, or are enhanced by, connection to a larger data network. In theinterest 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. Withthe proliferation of the NAVSTAR Global Positioning System (GPS), animplementation of a Global Navigation Satellite System (GNSS), the abilityto determine position and navigate has become expected. However, due tothe shortcomings of GPS, additional technology is needed to provide loca-tion information to the wireless user in situations when GPS is unavailableor inaccurate.The introduction to this thesis begins with the motivations and applica-tions of wireless positioning technology in section 1.1. A brief overview ofwireless 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 inclusionof multiple-input multiple-output (MIMO) technology, the positioning im-plications of which are discussed in section 1.6. Section 1.7 introduces pastand current research using WLANs to determine position. The objectivesof this thesis are presented in section 1.8, followed by the contributions ofthis study in section 1.9. Finally, the outline of the thesis is described insection 1.10.1Chapter 1. Introduction1.1 Motivation and ApplicationsPhase II of the Federal Communications Commission (FCC) Wireless E911mandate in the US [1] requires networks to be able to position cell phoneswithin their networks during emergency calls. This prompted a urry ofresearch into wireless positioning for cell phones. One solution is to includeGPS in every cell phone, which works well outdoors. Tests have been per-formed indoors using GPS, and found accuracy of about 100 m [2]. Thisis unsuitable for high accuracy applications and may not meet the E911phase II handset positioning accuracy requirements of 50 m and 100 mwith reliability of 67% and 95% respectively. Since most users are often in-doors or in areas without clear view of su cient numbers of GPS satellites,additional technology is necessary for higher accuracy positioning in thesesituations. The shortcomings of GPS for indoor use are caused by very lowsignal strength and additional errors caused by the lack of clear view of thesky. Since many indoor environments are out tted with WLANs, it makessense to evaluate whether WLAN infrastructure is useful in positioning theindoor 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 personalizedadvertising [6], social networking [7], personal navigation [8] and many oth-ers. The number of applications is rising steadily. The choice of positioningtechnology for a particular application is prioritized between accuracy, re-liability, exibility, size, power restrictions, deployment environment, andcost, among others.1.2 Wireless PositioningWireless positioning encompasses many di erent 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, which2Chapter 1. Introductionis then received at another device. Some aspect of the relative position ofthe devices is represented in the received signal. Because the received signalis the data used to facilitate positioning, the undesirable signal distortionthat occurs during wireless transmission is very important.A wireless positioning system generally consists of at least two di erentcomponents. The user or mobile, which is to be positioned; and the infras-tructure of access points (APs) with known positions, called the network. Inthe case of GPS, a widespread wireless positioning system, the mobile is theGPS receiver. The satellites orbiting the earth are the APs. Note that inthe GPS case, the positions of the orbiting satellite APs in the infrastructureare not constant, but known.Note that unlike most modern data communications systems, two-waycommunication is not strictly required for positioning.1.3 Indoor Wireless PositioningWireless positioning involves transmission of a wireless signal, and uponreception, some property of the received signal is used to determine therelative positions of the receiver or transmitter. Measured properties of thesignal commonly used for positioning are the received signal strength (RSS),time of signal reception, and the direction from which the signal is receivedor angle of arrival (AOA). Measurements using APs at di erent locationsare combined to determine position.All wireless signals re ect and scatter o objects in their environment,and transmitted wireless signals experience distortion when received. Copiesof the transmitted signal are received, each at di erent times and fromdi erent directions. This phenomenon is multipath and due to the densityand proximity of objects in an indoor environment, indoor signals can besigni cantly distorted. The destructive adding of the re ections can resultin lower strength, or fading, of the received signal.The wireless channel encompasses the overall e ect of objects in an envi-ronment between signal transmission and reception. The multipath wirelesschannel is di erent in situations where the transmitter and receiver have3Chapter 1. Introductionline of sight (LOS) and when they do not. This is shown in Figures 1.1and 1.2 respectively. The direct path is the portion of the signal relevantfor positioning since it represents the true direction and distance betweenthe transmitter and receiver. The measurements from the received signalmust be made on the part of the received signal corresponding to the directpath. When attenuated due to obstruction, the direct path is more di cultto identify, which can result in large errors in determining position. For in-stance, when measuring AOAs, if the direct path is attenuated enough suchthat it cannot be identi ed, then a re ection could be incorrectly selectedas the direct path. Since the direction of the re ection can be very di erentfrom that of the direct path, the measured AOA contains error.TransmitterReceiverObstructionDirect PathReflectionFigure 1.1: Multipath in an LOS situation between transmitter and receiver.TransmitterReceiverObstructionAttenuated Direct PathReflectionFigure 1.2: Multipath in an NLOS situation between transmitter and re-ceiver.4Chapter 1. Introduction1.4 Network and Mobile PositioningGPS 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 tohave many mobile devices simultaneously requesting position. This is toreduce the amount of computation required by the network. More impor-tantly, for GPS the transmission power requirements are very large due tothe immense distance between the satellites and the surface of the earth,which make it impractical for signals to be transmitted by the mobile. Italso makes sense since the mobile is interested in its own position, and noadditional 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 basestations have access to more computational resources, more sophisticatedantenna arrays and due to their height and distance from the mobile, themultipath e ects 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 thecomputational load on the network, and is most useful in instances whenconstant positioning of many mobiles is not necessary, such as when posi-tions are calculated on demand. In addition, if the number of positioningcomputations is very large, then a smaller mobile device may not be able toquickly compute its own position, and therefore this work is performed bythe network. Therefore it is useful for emergency systems when positions arenot often requested, or when the position information is useful to someoneother 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 hasstringent size and power limitations. The infrastructure generally has directaccess to large amounts of energy resources, so the transmission power from5Chapter 1. Introductionthe APs can be considerably larger than that possible by the mobile. Withhigher transmission power and therefore higher signal to noise ratio (SNR),greater positioning accuracy is expected. This is especially true for verylarge 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 forpositioning is large.1.5 Wireless Local Area NetworksWLANs are becoming ubiquitous indoors, as more and more users demandmobile 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. Theincreasing trend of being able to access data from anywhere is driving de-velopments in wireless data networks. The latest technology in the laterstages of development is based on the IEEE 802.11n standard [9]. Productsare appearing in the market based on the standard, since it is stable eventhough the standard has yet to be nalized. Like most upcoming wirelesstechnologies, the main improvements over older technologies are reliability,range, and higher data throughput. The maximum data rate is increased to300 Mbps over 54 Mbps for 802.11g [10].WLAN infrastructure consists of APs connected to a wired local areanetwork (LAN). The APs transmit and receive the wireless data signalsand communicate with the wireless devices in their vicinity. These APs areplaced in various positions, often at ceiling level, and are spread out in anindoor space such that a device should be able to receive WLAN signal fromat least one AP anywhere where service is intended. This usually results inoverlap to ensure complete coverage. The usable range of a typical WLANAP indoors is approximately 40 m. Devices based on the 802.11n standardare 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-6Chapter 1. Introductiontion. Since most APs are connected to the same data network, a computerwith su cient permission on the network should be able to gather posi-tioning information from the APs. This allows for the position of a smallmobile device to be calculated by a network device with more computationalresources.WLAN signals consist of two basic parts, the preamble and the data. Thepreamble is used for signal detection, timing synchronization, frequency o -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 longtraining symbols. The total number of training bits usable for positioningfor an 802.11a preamble is 144. The 802.11n preamble is similar althoughadditional training symbols can be inserted elsewhere in the signal [13] forthe purposes of additional channel estimation.The new IEEE 802.11n standard includes provisions for multiple-antennaarrays [9], which has been enabled by advances in computing such that theadditional cost is considered acceptable relative to the performance bene ts.Multiple antennas are optional for 802.11n, with up to four antennas in eacharray [10]. The inclusion of multiple antennas at each AP has the bene tof allowing for the determination of the direction from which signals arrive.Knowledge of the mobile’s direction at multiple APs in the network enablescomputation of the mobile’s position.1.6 Multiple-Input Multiple-OutputTo enhance the performance of wireless networks, various techniques areused. These include modulation and diversity. Diversity of the wirelessenvironment or channel can be exploited in terms of time, frequency andspace. Brie y, time diversity techniques take advantage of the variations inthe received signal over time caused by the objects in the wireless environ-ment. Frequency diversity is caused by the varying e ects of the wireless7Chapter 1. Introductionenvironment depending on the frequency of the signal. The popular orthog-onal frequency division multiplexing (OFDM) technique takes advantage offrequency diversity to handle adverse wireless conditions.Spatial diversity techniques use the variations in the wireless signal re-ceived at di erent points in space. To leverage the bene ts of spatial di-versity, multiple antennas are used at the transmitter and receiver, calledMIMO. 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 issingle-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 uctuations 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. Thedata throughput of a system is therefore improved [14].MIMO is beginning to be employed in di erent technologies, but is notpractical for some since it requires a larger antenna array and incurs addi-tional hardware cost. The hardware cost is increased not only due to theinclusion of multiple antennas, but the received signals must be combinedin an optimal fashion, making additional processing necessary. Many highspeed future wireless data systems are expected to use MIMO to reach de-sired throughput levels. MIMO can also be used to perform direction-basedpositioning in systems that feature them.1.7 WLAN PositioningDi erent techniques have been developed for positioning the indoor wirelessuser. Of those that utilize WLAN signals, most focus on RSS [15, 16]. Thesesystems require no changes to the hardware used, since the RSS measure-ments are already provided by most consumer WLAN devices. RSS-basedpositioning methods are broadly broken up into two groups: ngerprintingand propagation modeling.8Chapter 1. IntroductionFingerprinting involves generating an RSS map of the area of interest,noting the RSS for each AP for every position in the map. Determinationof user position involves reading the RSS of the signal from all the APs andusing a search to nd the best match in the RSS map. This transforms thepositioning process into a pattern recognition problem. The position esti-mation can be as accurate as 2 m [17]. Preserving this positioning accuracyinvolves resurveying the entire RSS map for all changes in the environmentwhich is not practical. Indoor environments are constantly changing, withobjects being removed and introduced. Therefore actual usage of such a sys-tem can be expected to perform worse than studies indicate over the longterm, 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 approximatingthe 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 re ned by usingknowledge about the indoor environment. This method is less accurate thanthe ngerprinting method, with accuracy of approximately 2.5 m [16].Systems that implement RSS WLAN positioning are already up andrunning, such as SkyHook [18], WhereNet [19] and Ekahau [20]. SkyHookclaims positioning accuracy of better than 20 m. Work has been done tocharacterize the statistical properties of the RSS measurements, which canbe used in a positioning algorithm to result in better positioning accuracy[21, 22].The motivation behind research into RSS methods is clear, as they arethe easiest to implement. They can be implemented using consumer hard-ware, and the positioning solution can be fully determined in software on amobile computer. RSS positioning is attractive as there is no need to makeany changes to existing WLAN infrastructure.Other research has looked at indoor positioning using the time-basedtime of arrival (TOA) or time di erence of arrival (TDOA) methods usingWLANs [12, 23, 24, 25]. Only a few have implemented such a system, andindicate better positioning accuracy than RSS-based systems [26]. Little re-search has been done for AOA positioning using WLANs due to the previous9Chapter 1. Introductionlack of antenna arrays capable of determining signal direction. The accu-racy of time-based positioning systems has historically been better than thatof both RSS and AOA-based systems, but time-based positioning requiressynchronization between the transmitters. In addition, the positioning per-formance of a TOA-based solution is heavily dependent on the bandwidthof the signal used. The bandwidth of WLAN signals is relatively small, andtherefore higher accuracy positioning might be possible using a di erenttechnique.There are other systems that allow for non-WLAN facilitated indoorpositioning. Systems implemented using ultrawideband (UWB) frequencyspectra have the potential for sub-meter level positioning accuracy [27].Companies such as Locata Corporation have developed TOA systems withGPS-like positioning capabilities [28]. They claim to be able to extend thepositioning to indoor environments [29].In addition, there has been research that integrates di erent positioningmethods. For instance, some take advantage of the integration of microelec-tromechanical systems (MEMS) inertial sensors with another positioningtechnique such as RSS [30]. Combining RSS WLAN positioning and GPSmeasurements to determine user position outdoors and indoors has also beeninvestigated [31].1.8 Research ObjectivesIndoor positioning using AOAs has not been investigated much in research.The usual premise is that it is less accurate in determining user positionthan time-based methods and requires higher computational and hardwarecosts. However, AOA positioning has the bene t of not requiring high accu-racy time synchronization. Future WLAN APs may feature MIMO antennaarrays, and thus allow for the possibility of AOA positioning. It there-fore seems to be an appropriate time to investigate AOA positioning usingWLANs. 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 AOA10Chapter 1. Introductionposition is based on the usage of positioning systems outdoors for long rangeapplications. AOA positioning systems become more accurate as the dis-tance between the positioning infrastructure and the mobile is decrased. Inan indoor environment where the wireless devices are closer in proximity toeach other, AOA could result in better positioning accuracy than in longrange outdoor environments. If the performance of AOA positioning usingWLANs is similar to that of other WLAN positioning systems, it meritsfurther study.The purpose of this research is to perform an evaluation of the potentialperformance using MIMO equipped WLAN APs in AOA-based positioningof the indoor wireless user. With an idea of what the potential performanceis, 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, amore 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 typicalo ce-type indoor space. The position of a WLAN user in the network isrequested, either by the user or network operator. Each AP in the networkwithin range of the mobile’s signal gets a snapshot of the received signal fromall of its receive antennas and estimates the AOA of the mobile. These AOAsare then sent to a central computer and used by a positioning algorithmto determine the position of the mobile. This process is continued for aslong as requested, to generate positions at certain time intervals, giving themobile’s time varying position or trajectory. While there are obvious privacyissues with this type of system and any positioning technology [32], only theperformance 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 realisticperformance metric, the error in the AOA measurements is determined fromreal MIMO indoor measurement data. A wireless channel measurement sys-tem developed by TR Labs Calgary is used that has four antennas, similar tothe number expected in upcoming WLAN APs. The statistical properties ofAOA estimates calculated using the measurements are then used in the posi-11Chapter 1. Introductiontioning simulation to gain insight into the operational system performance.Two di erent algorithms, a simple maximum likelihood (ML) and space-alternating generalized expectation-maximization (SAGE) [33], are testedto 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 lter (EKF) to come to conclusionsabout the performance of this type of system.1.9 ContributionsThe following are the contributions of this thesis: Characterization of AOA estimation performance in an indoor wirelessenvironment using a simple ML technique and the SAGE algorithm.This is performed on real indoor channel measurements using a limitednumber of receive antennas, as is expected to be featured with futureWLAN APs. Evaluation of the e ectiveness of direct path identi cation using MLand SAGE. Determination of the overall positioning accuracy of AOA-based WLANinfrastructure through simulation by incorporating the AOA errorstatistics from the measurement generated AOA estimates. Examination of the use of EKF over LS in improving the performanceof AOA positioning.1.10 Thesis OverviewThe rst few chapters of this thesis cover the necessary theory behind bothpositioning and wireless channel characterization. Chapter 2 is an overviewof general positioning methods and theory related to wireless positioning. Italso contains descriptions of some current and past technologies. Chapter3 follows with background to understand the e ects of the indoor wireless12Chapter 1. Introductionenvironment. Included is a detailed description of the channel measurementsystem used to generate the data that was used to estimate the AOA of thereceived signal. The measurements and the environment in which they weretaken are outlined.Chapter 4 describes the method by which the AOA of the transmittedsignal is estimated from the channel measurement data. First, the receivedsignal 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 astrict ML algorithm is also presented. An ML algorithm speci cally derivedfor estimating AOAs for positioning applications is described and the per-formance compared with SAGE. Implementation issues are addressed, suchthat practical and e cient implementation is possible. Finally the statisticalAOA 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, andtwo positioning algorithms, LS and EKF, are discussed. They are then usedwith simulated positions and a user trajectory. The AOA error statisticspresented in the previous chapter are incorporated to simulate noisy AOAestimates 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 ndings,and future research opportunities.13Chapter 2PositioningThere are many di erent types of position determination, used for manydi erent applications. In terms of modern technology, the most convenientand accurate positioning technologies are wireless. The ability to position anobject is very valuable for many applications, and in some cases is absolutelynecessary.Historically many signi cant wireless positioning technologies were ini-tially developed and used for military purposes. For example, GPS wasdeveloped and implemented by the United States Department of Defense.Government funding has led to signi cant advancements in the area of nav-igation technology.This chapter starts with an overview of positioning basics in section 2.1,describing brie y the di erent types of positioning and detailing positioningaccuracy. The fundamental concepts and history of the positioning methodsTOA, TDOA, AOA and RSS are then discussed in more depth in sections2.2 through 2.5.2.1 Positioning MethodsThere are three dominant positioning methods, each based on a di erentpositioning measurement: time-based, direction-based and RSS. The time-based methods include TOA and TDOA positioning, which relate the timeof propagation of the signal to a range or range di erence. Direction-basedmethods determine user position through AOA measurements, or the di-rection of the mobile from the received signal. RSS measurement methodsinclude ngerprinting and propagation modeling, which relate the strengthof the received signal to the position of the user. The measurement quanti-14Chapter 2. Positioningties are corrupted by noise and other distorting factors, so the measurementsmust be estimated from the signal. This process is called signal parameterestimation.In addition to these three basic techniques, others have been proposed aswell. An interesting positioning method is direct position determination [34]which does not have intermediate positioning measurements, but determinesthe position directly from the received signals. Measurement-based methodssuch as TOA/TDOA and AOA estimate the measurements independently,even though the position of the user is common for all measurements. Directposition determination applies this constraint to more accurately determineuser position. This is done by observing all of the received signals at theAPs and choosing the mobile position that best matches those signals basedon the propagation model. The search for the mobile position is a largemulti-dimensional problem. Because of this, direct position methods arecomputationally complex, and currently not feasible for implementation.A signi cant amount of research has gone into hybrid techniques wherebydi erent types of positioning measurements such as TOA and AOA [35];or TDOA and AOA [36] are integrated to determine user position. Theusage of di erent positioning measurements can allow for positioning withreduced numbers of APs, as shown in [37] using UWB signals and a singleAP measuring AOA and TOA with decimeter level precision in a close rangeLOS environment.2.1.1 Lines of PositionFor each positioning method, lines of position can be drawn which representthe potential positions of the mobile. The lines of position are di erent foreach type of positioning measurement, and ideally lines of position fromeach 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 inthe measurements, so the position computed is an estimate of the actualmobile position. The lines of position are used to visualize the positioningmethods. Example lines of position are shown for each positioning method15Chapter 2. Positioninglater in this chapter.2.1.2 Positioning AccuracyThe 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 thespeci cs of the hardware as well as the wireless environment. Harsher wire-less environments have more multipath which is discussed in Chapter 3. Thisdistorts the signal that is received and causes the positioning measurementsextracted to be less accurate.The system geometry, in terms of the relative placement of the APswith respect to the position of the mobile, has an e ect on the positioningaccuracy 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 thepositioning measurements. A statistical amount of measurement error em isrelated to the expected statistical position errorep using those measurementsby the corresponding DOP valueep = DOP em: (2.1)Therefore the DOP has units of position unit per unit of measurement. Forthis study the positioning is in metres using AOAs, so the DOP has unitsof metres per radian.The DOP and therefore the positioning performance varies based on thepositioning 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 couldbe the approximate error in the determination of the easting coordinate ofthe mobile, represented by the easting DOP (EDOP). Likewise, the northingDOP (NDOP) relates the measurement error to the approximate error indetermining the northing coordinate of the mobile. A non-directional posi-16Chapter 2. Positioningtion 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 DOPis larger and therefore the resulting position estimates are expected to beless 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 geometryis discussed in section 5.4.2.2 Time of Arrival PositioningTOA positioning involves the determination of the distance of the mobilefrom each AP by measuring the absolute propagation time of the signal. This rst requires highly accurate time synchronization between all the transmit-ters and receivers, so that the total propagation time for the signal can becalculated. With the knowledge of the speed of propagation, the time be-tween transmission and reception can be converted into a distance or rangemeasurement. Because of this, TOA positioning is also called ranging. Po-sitioning through the use of ranges is also referred to as trilateration. For2D positioning, a minimum of three APs is required.Once the distance from each AP has been calculated, the lines of positioncan be drawn, an example of which is shown in Figure 2.2. The lines ofposition are circles at the measured ranges R1, R2 and R3 centered on thecorresponding APs.TOA positioning generally has potential for high positioning accuracy.17Chapter 2. PositioningR1R2R3AP 1 (x1, y1)AP 2 (x2, y2)AP 3 (x3, y3)Mobile (xm, ym)yxFigure 2.2: Example of circles of position for TOA-based positioning usingthree APs.This depends mainly on the transmitted signal and the capabilities of thereceiver. The resolution with which the propagation time can be determinedis determined by two factors: the bandwidth of the transmitted signal, andthe sampling frequency at the receiver. The bandwidth is the limiting factorassuming that the sampling frequency is greater than the Nyquist rate. Alarge bandwidth signal allows for higher frequency components to exist inthe signal, which enables sharper signal transitions. These transitions aredetected to better determine propagation time.The best possible unbiased positioning variance is dictated mathemat-ically by the Cram er-Rao lower bound (CRLB). The CRLB in an NLOSsituation is shown in [38] for the di erent positioning methods. The NLOS18Chapter 2. Positioningmeasurement error is modeled and expressions for the CRLB are derived.It is important to note that the CRLB of the position estimates for allpositioning methods depend on the AP geometry.The CRLB for TOA positioning is inversely related to the SNR andsignal bandwidth. That is to say, time based positioning techniques showimprovements in positioning accuracy with large signal bandwidth, which iswhy UWB is becoming a popular choice in positioning research [39]. Increas-ing the SNR also improves positioning accuracy, which does not necessarilyhave to be accomplished by increasing the power of the transmitted signal.In a spread spectrum system where a sequence of higher frequency pulsesis used to spread signal energy over a wider bandwidth, correlation is usedto gather the signal energy and increase SNR. This is discussed further insection 3.3.2.3 Time Di erence of Arrival PositioningTDOA positioning is similar to TOA in that it uses the propagation timeinformation to determine the user position. However, while the APs in thepositioning infrastructure are time synchronized between each other, themobile is not. When the received signal is used to calculate a range usingthe receiver clock, the range contains the bias between the transmitter andreceiver clocks common to all the ranges. Therefore the range that can becalculated is called a pseudorange.The absolute range cannot be known due to the lack of receiver-transmittersynchronization. However, what is known about the user position is the dif-ference between the distances from di erent APs. Di erencing the pseudor-anges removes the unknown time of transmission, or clock bias between themobile and the APs, from the position calculation. Due to the additionalinformation to be estimated, the clock bias, TDOA positioning requires onemore AP than TOA positioning.Strictly speaking, TDOA positioning can be done in two ways, wherethe clock bias is estimated along with the position, as in the case of GPS;and where the transmission time di erences are used to determine position.19Chapter 2. PositioningWhen the clock bias is estimated, the lines of position are similar to those ofTOA, however the circles of position all have the same xed radius changegiven 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 thesame amount until the lines of position intersect appropriately. In the casewhere di erencing 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 di erencing TDOA system is shown inFigure 2.3.AP 1 (x1, y1)AP 2 (x2, y2)AP 3 (x3, y3)Mobile (xm, ym)yxFigure 2.3: Example of hyperbolas of position for TDOA-based positioningusing three APs.In terms of positioning accuracy, similar accuracy to TOA is possible20Chapter 2. Positioningwith all of the same limiting factors. NAVSTAR GPS is a common exampleof a clock estimating TDOA system. Additional methods exist to increasethe precision of the time measurements beyond what the bandwidth sug-gests such as GPS carrier phase tracking which results in higher positioningaccuracy [40]. For very weak spread spectrum signals, the SNR can be in-creased by observing the signal for longer periods of time. This enables theuse of GPS indoors by extending correlation times to multiple periods of thetraining sequence. This recovers signal information that is buried in receivernoise.Historic examples of TDOA positioning systems include Gee developedby the British in World War II for aircraft navigation [41]; and the subse-quent American developed Long Range Navigation (LORAN) which sportedgreater operating ranges [42]. The most recent LORAN system, enhancedor 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 signalbandwidth.2.4 Angle of Arrival PositioningAOA positioning, also called triangulation, is the determination of positionby the use of knowledge of the angles between the mobile and the APs, orvice versa. This can be performed in di erent ways. Mechanically, a narrowdirectional antenna can be used to sweep in all directions of interest, andrecord the direction where the received signal is strongest. Since a mechan-ically operated antenna array is slow, energy ine cient, and impractical,another method may be more useful. A method of much interest, and thesubject of this thesis, is the use of multiple antenna arrays. The additionalpropagation distance of the signal to each of the spatially separated anten-nas is used to determine the signal propagation direction. This appears inthe demodulated received signal as a phase shift di erence between signalsreceived at di erent antennas.Positioning in two dimensions requires a minimum of two APs, however21Chapter 2. Positioningthis results in very poor positioning near the line that is drawn connectingthe APs. For a practical system to be able to position a user, a minimumof three APs are used.The lines of position for AOA positioning are simply lines from the mobileor AP in the direction of the AOA. An example of these lines of position isshown in Figure 2.4.AP 1 (x1, y1)AP 2 (x2, y2)AP 3 (x3, y3)Mobile (xm, ym)yxA1A2A3Figure 2.4: Example of lines of position for AOA-based positioning usingthree APs.The positioning accuracy of an AOA system is usually inferior to that ofa TOA system, especially when the infrastructure is at large distances fromthe mobile. The performance of AOA positioning degrades with greater dis-tances [38] between the APs and the mobile, which is intuitive. The CRLBshows that the best obtainable unbiased positioning accuracy is enhanced22Chapter 2. Positioningby increasing the spacing between the antennas in the receive array as wellas the number of antennas and the signal SNR. This thesis investigates theperformance with an antenna array with relatively few elements, to mimicfuture available WLAN APs and assess their positioning potential. The po-sitioning performance is improved with reduced distance between the APsand the mobile. When used over short distances, AOA-based positioningcould provide reasonable accuracy.The con guration of the antenna array elements dictates the possibleangles which are able to be estimated. For example, a linear monopole arraycontains ambiguity in the angles, since the side of the array from which thesignal arrives is unknown. As well, a linear monopole array does not allowfor the estimation of the elevation angle of the signal.AOA-based positioning systems have been used for navigation purposes,although not usually in a exible manner, using xed beamforming antennaarrays. For example, in World War II the Germans used several AOA-basedtechnologies. Lorenz was used for navigating aircraft to proper xed land-ing trajectories [43]. This type of technology was subsequently incorporatedin Knickebein and later systems, used for accurate bombing of speci c tar-gets. Due to the only recent usage of multiple antenna arrays in commercialsystems, research indicates that there are few, if any, commercial purelyAOA-based positioning systems.2.5 Received Signal Strength PositioningRSS positioning encompasses several di erent positioning methods. All arebased on recording of the power in the received signal. This is most usefulwhen the extraction of other position measurements from the transmittedsignal is di cult, usually due to the signal itself not being tailored for po-sitioning purposes. The signal strength of existing data signals is the mostcommon usage of RSS positioning. Signals used in this manner are calledsignals of opportunity. These RSS measurements are typically used for po-sitioning in two di erent ways: propagation modeling and ngerprinting.Research has been split between ngerprinting and propagation modeling,23Chapter 2. Positioningwhere the higher positioning accuracy methods appear to favour ngerprint-ing.Propagation modeling mathematically translates the RSS measurementsinto 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 ofthis method is mostly dependent on how well the propagation model esti-mates the range from the RSS, in the environment where the system is tobe deployed and on the hardware on which it is implemented.Fingerprinting has been the focus of much research and involves creatinga map of the RSS from di erent APs. The possible positions of the userare surveyed, and at each position the RSS from each AP is recorded inthe map. The position of a user is determined by nding the best matchon the map for the RSS measurements observed by the user. The e cientdetermination of the best match is the focus of current research and themethods include simple Euclidean distance [44], neural networks [17], andkernels [15] among others [45, 46].RSS positioning is less accurate than time-based positioning, althoughfor ngerprinting 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 e ects of multipath.Also interesting is that [38] shows that the CRLB of the position estimatesdoes 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 theAPs. 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 methodshas the fewest available free parameters to improve positioning performance.24Chapter 3The Indoor Wireless ChannelThis chapter contains background about the indoor wireless channel anddetails the distortion of wireless signals. The background of the e ect of thewireless channel in terms of multipath is described in section 3.1. Propertiesof the multipath in wireless channels are presented in section 3.2. To un-derstand how the wireless channel a ects AOA estimation, MIMO measure-ments were collected. The con guration and speci cs of the measurementsetup as well as how measurements are used to characterize multipath arefound in section 3.3. The speci cs of the measured environment and themeasurements themselves follows in section 3.4.3.1 Multipath and the Channel ImpulseResponseThe indoor wireless environment consists of densely packed objects whichabsorb, re ect and scatter transmitted signals. This is similar to that ofthe outdoor wireless environment, but the objects are situated closer to thewireless devices and are more numerous. Therefore the number of re ectionsis higher, and due to the proximity of the transmitter and receiver, thepropagation time for each is low. At the receiver, many di erent copiesof the transmitted signal are received, at di erent times and from di erentdirections. Each copy is called a multipath arrival.A typical concern for data transmission is that these copies, when super-imposed upon reception, can cause signi cant reductions in signal strengthby adding destructively. This phenomenon is called fading, and is most se-vere for narrowband signals. This loss of signal results in interruptions in25Chapter 3. The Indoor Wireless Channelthe transmission of data, and therefore the lost data must be requested andsent 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 di er-ent for di erent positions of the receive and transmit antennas. ThereforeMIMO systems can be used to counteract the fading phenomenon. By us-ing antennas separated spatially, each experiences di erent multipath fading,and the probability of all the antennas experiencing simultaneous fades islowered. The signals received by each of the antennas can then be combinedto increase the SNR over that of an equivalent system equipped with onlya single antenna.The multipath component that follows the direct path between trans-mitter and receiver will not necessarily have the highest receive power, sincea strong re ection could have higher amplitude than an attenuated directpath. 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 evenexist depending on the environment. Finding the direct path is importantfor accurate AOA estimation. The e ectiveness and probability of correctlydetecting and identifying the direct multipath arrival will be evaluated byprocessing the MIMO channel measurements described later in this chapter.The e ect of the wireless channel can be described mathematically byits channel impulse response (CIR). The received signal r(t) is de ned asthe convolution between the transmitted signal s(t) and the CIR h(t), inthe same way as any other linear time invariant systemr(t) = h(t) s(t): (3.1)The CIR is described in terms of the L di erent copies of the transmittedsignal that arrive at a receive antennah(t) =LXl=1 l (t tl) (3.2)where l is the complex amplitude of the received signal for path l, (t)26Chapter 3. The Indoor Wireless Channelis the Dirac delta function and tl is the time between transmission andreception for path l. The delay tl can be expressed as a function of thedistance that the signal travels from transmitter to receiver dl where c is thespeed of light tl = dlc: (3.3)3.2 Properties of the Wireless ChannelIndoor wireless channels di er from those of outdoor wireless channels.These di erences 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 inthe ability to use a wireless signal for positioning.An example of the arrivals in an indoor multipath channel, in termsof the parameters of each arrival, is shown in Figure 3.1. Each multipatharrival has di erent amplitude, delay and AOA.3.2.1 Delay Spread and Time DensityThe delay spread of a wireless channel is a measure of how multipath arrivalsare spread out in time. For an outdoor wireless channel, the delay spreadis large since the propagation distances are typically large, on the order ofmicroseconds of propagation time. However, for an indoor wireless channel,the delay spread is smaller. An example of multipath delays estimated fromindoor wireless channel measurements is shown in Figure 3.2. There aredi erent ways of calculating delay spread, such as the di erence in delaybetween the longest and shortest propagation paths [47]. Calculated in thisway, this example has a delay spread of approximately 140 samples, whichat 2 GS/s translates to 70 ns delay spread.While all wireless channels experience multipath, their di erences in de-lay spread often lead to di erences in what will be referred to here as timedensity. Time density is a measure of the number of multipath arrivals perunit time. In an outdoor channel the time density is generally lower, since27Chapter 3. The Indoor Wireless ChannelFigure 3.1: Example multipath in an indoor wireless channel in terms ofamplitude, delay and AOA.the arrivals are spread out in time and indoor channels have higher timedensity, due to the short propagation distances.The impact of this time density is on the identi cation of each of thesearrivals in time. As the time density increases, the time between arrivalsdecreases and therefore it is more di cult to distinguish one multipath ar-rival from others. Depending on the signal bandwidth, the time resolutionmay cause the multipath arrivals to be inseparable in terms of delay.3.2.2 Angle SpreadThe angle spread of a wireless channel is a measure of the distribution of theAOAs of the multipath arrivals at an antenna array. An outdoor wirelesschannel typically has low angle spread. In situations of long distance be-tween transmitter and receiver, it can be less than 10 [48]. Indoors the angle28Chapter 3. The Indoor Wireless Channel0 20 40 60 80 100 120 140 16000.511.5x 10−3Delay (samples)AmplitudeFigure 3.2: Example of amplitudes at various delays in an indoor wirelesschannel.spread is usually larger. For example the 802.11n channel model assumesan angle spread standard deviation of between 15 and 50 [49].Example AOAs estimated from measurement data for an indoor wirelesschannel are shown in Figure 3.3. The angle spread in this example, if de nedsimply as the range of angles that exist in the channel, is approximately 100 .3.3 Channel Sounding SystemThe e ect of the indoor wireless channel on the transmitted signal was char-acterized using a wideband spread spectrum channel sounding system. Thesystem used for this research was developed by TRLabs Calgary, and con-sisted of a single matched transmitter and receiver [50]. The transmitter andreceiver each had a four antenna linear monopole array, used to transmitand receive a periodic signal at a carrier frequency of 5.66 GHz. The IEEE802.11n standard operates at a similar frequency of near 5 GHz [9]. Thissystem allows for the determination of 16 spatially diverse channel impulseresponses, one for each combination of transmit and receive antenna.The periodic spread spectrum signal transmitted is a pseudorandom29Chapter 3. The Indoor Wireless Channel0 20 40 60 80 100 120 140 160 18000.10.20.30.40.50.60.70.80.91x 10−3AOA (degrees)AmplitudeFigure 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 avalue of 1 or -1. The PN sequence used has the property that it correlateswith itself at o sets of multiples of the sequence length with a value equalto the sequence length, and is -1 at all other o sets. 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 bene t of using thesesignals is the ability to increase the SNR of the received signal by extendingthe 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 asimilar manner to this PN sequence. The training symbols are already usedfor channel parameter estimation [13]. Most will have fewer chips thanthe number used in this system, however the e ect of fewer chips can beapproximated by the reduction in the SNR of the signal captured by themeasurement system.30Chapter 3. The Indoor Wireless Channela(t)tK-1Figure 3.4: Autocorrelation of PN sequence of length K as a function ofsequence o set t.3.3.1 Antenna ArrayThe transmit and the receive antenna arrays are identical, consisting of alinear array of four separate monopole antennas located along a sliding trackin a truncated ground plane as shown in Figure 3.5. The use of a four elementarray is similar to what is expected from future WLAN APs. The antennasare set with a separation of 2.6cm corresponding to half wavelength of the5.66 GHz carrier frequency. The antennas have been tuned for operation at5.66 GHz with a usable bandwidth of several hundred MHz. The antennaarrays for both the transmitter and receiver are at the same height abovethe oor, approximately 1.5 m.3.3.2 TransmitterThe transmitter consists of two arbitrary waveform generators (AWGs) withtwo independent outputs each, capable of generating a signal based on asampling rate of 1 GS/s. The AWGs are all synchronized to the same clocksource such that 4 pseudo-orthogonal baseband PN sequences are generated,one for each transmit antenna channel. Pseudo-orthogonality is assuredby using staggered code delays of 414 chips between the transmitted PNcode sequences. For example, the second transmit antenna transmits thesame signal as the rst antenna but cyclically shifted by 414 chips. Each31Chapter 3. The Indoor Wireless ChannelFigure 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 ofshift between the transmitted signals is larger than the expected delay spreadof the system, and the phase shift between the fourth and rst transmittedPN sequences is 805, so that the CIRs can all be uniquely identi ed. Theideal received signal from all transmit antennas at a single receive antennaafter correlation with the transmit sequence is shown in Figure 3.6. Theshift between the transmitted copies of the PN sequences is demonstrated.The modulated signals are PN codes based on a 2047 maximum lengthsequence passed through a root raised cosine lter with an excess bandwidthof 0.4. The chipping rate of 200 MHz results in an approximate two-sidedbandwidth of 300 MHz. Each of the four signals is upconverted to 5.66 GHzcarrier frequency using a common local oscillator (LO). A simpli ed blockdiagram is shown in Figure 3.7 and a picture of the transmitter in Figure3.8. The power transmission level of 10 dBm is well within the linear rangeof the transmitter ampli ers to avoid compression issues.32Chapter 3. The Indoor Wireless ChanneltC(t)t0 t0 + 414t0 + 828t0 + 1242TX1 TX2 TX3 TX4Figure 3.6: Ideal received signal from all transmit antennas after correlationwith the transmit sequence.3.3.3 ReceiverThe receiver is built around a 4 channel 20 GS/s LeCroy WavePro 7300digital oscilloscope. The block diagram of the complete receiver is given inFigure 3.9. Figure 3.10 is a photo of the receiver equipment. The receivedsignals at the output of the four antennas are ltered to remove out of bandnoise, ampli ed and then downconverted to an intermediate frequency of500 MHz. The intermediate frequency signal is then ampli ed and lteredonce more before sampling. The signal sampling consists of accumulating50 000 samples at a 2 GS/s for each of the four received signals. This datais recorded by the Matlab scope application code and written to disk, alongwith setup information. The transmitter does not provide a synchronizationsignal to the receiver, so only relative timing in the received signal can bediscerned.3.3.4 Equipment CalibrationTesting delay, phase and power di erences between the receive chains is im-portant for AOA estimation since those di erences cause errors in the signalmodel used in the estimation process. The signal to one of the transmitantennas was directly connected using a power splitter to all of the receive33Chapter 3. The Indoor Wireless ChannelAWG #1AWG #2LPFLPFLPFLPFCH 1CH 2CH 1CH 2Clock SourceTriggerMixerMixerMixerMixer5.66 GHzLocal OscillatorPowerSplitterAmplifierAmplifierAmplifierAmplifierBPFBPFBPFBPFBasebandRadio Frequency 5.66 GHzTX1TX2TX3TX4Figure 3.7: Hardware con guration for the transmitter.Figure 3.8: Photo of the transmitter equipment.34Chapter 3. The Indoor Wireless ChannelLPFLPFLPFLPFMixerMixerMixerMixer5.16 GHzLocal OscillatorPowerSplitterAmplifierAmplifierAmplifierAmplifierBPFBPFBPFBPF500 MHz Intermediate FrequencyRadio Frequency 5.66 GHzAmplifierAmplifierAmplifierAmplifierDigital2 GS/s SamplingOscilloscopeRX1RX2RX3RX4Figure 3.9: Hardware con guration for the receiver.Figure 3.10: Photo of the receiver equipment.35Chapter 3. The Indoor Wireless Channelantennas using cables as shown in Figure 3.11. Attenuation of 60 dB wasnecessary due to the high transmit power saturating the receive ampli ers.The splitter used has a frequency range of up to 5.8 GHz, adequate for thetransmitted signal. Scope captures were taken at the same time on all fourchannels in the same manner as regular channel measurements.Once the calibration captures have been recorded, the relative power andphase di erences between the receive antenna signals are corrected when themeasurement data is processed. This is especially important for AOA mea-surement where both the phase and power di erences are used to estimatethe direction.From TX1 BPFPowerSplitter60 dB AttenuatorTo RX1 BPFTo RX2 BPFTo RX3 BPFTo RX4 BPFFigure 3.11: Con guration for relative phase and amplitude calibration be-tween the receiver channels.3.3.5 Channel Impulse Response EstimationThe estimated CIR for the channel between a transmit antenna and receiveantenna m is hm (t). It is recovered by correlating the received signal ym (t)with the transmitted pulse shaped PN sequence u(t)hm ( ) =Zym (t)u(t+ )dt: (3.4)This is possible by approximating the autocorrelation of the PN sequencewith a delta function. Since the received signal is the convolution of theCIR with the transmitted sequenceym(t) = hm(t) u(t); (3.5)36Chapter 3. The Indoor Wireless Channelthe correlation of the received signal with the transmitted sequence isym(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 rst. 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 thetransmitted sequence is a PN sequence, thenym(t) u(t) hm(t): (3.8)This estimated CIR is used wherever the CIR is required in the AOAestimation. For estimation purposes, the estimated CIR is assumed to becorrupted with an independent complex circular Gaussian noise process atthe receiver.After the received signal has been correlated with the transmitted pulseshaped PN sequence, the CIRs corresponding to each of the transmit anten-nas are required to be separated. This is done by detecting the four groupsof peaks that correspond to the CIRs for each of the transmit antennas. Theadditional 805 chip spacing after the fourth antenna transmit signal beforethe repeated signal from the rst antenna allows for unique identi cationof each. An example of an estimated channel impulse response is shown inFigure 3.12.3.4 Indoor Channel MeasurementsThe MIMO channel sounding system was used to characterize the indoorenvironment of the Information and Communications Technology buildingat the University of Calgary. The measurements were taken in the under-graduate labs on the third oor. Three di erent kinds of measurements37Chapter 3. The Indoor Wireless Channel0 50 100 150 200 250 3000100200300400500600700800900Time (ns)MagnitudeFigure 3.12: Example CIR generated from a channel measurement.were taken to represent the di erent situations of separation between thereceiver 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 ofthe transmitter and receivers are shown in Figure 3.13.The building was a concrete structure with gyprock walls and a 10 ftceiling. The labs were equipped with sparse equipment such as lab benchesand computers. Occasionally people were moving within the vicinity of themeasurement equipment. All doors shown in the map were closed duringmeasurement 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 thetransmitter and receiver along with the orientations of the antenna arrayswere assured by surveying points on the oor using a total station, a pre-cise optical positioning instrument o ering millimeter level precision. Thetransmitter and receiver antenna arrays were positioned on these points us-ing a plumb-bob. To ensure proper facing of the antenna arrays, one pointon either side of the antenna array was surveyed and positioned above thepoints on the oor. The points on the antenna array were about 40 cm38Chapter 3. The Indoor Wireless ChannelScale2.5 mLegendWallWindowWooden DoorTransmitter LocationReceiver LocationTX1TX2RX1RX2RX3Figure 3.13: Map of University of Calgary Information and CommunicationsTechnology building third oor with receiver and transmitter positions.apart. Measurements were taken with the antenna arrays directly facingeach 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 thepoints on the antenna arrays over the marks on the oor is assumed to havea 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 transmitantenna array is perpendicular to the direction of the receiver, results inAOA 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,39Chapter 3. The Indoor Wireless Channelis approximately 0:9 .Table 3.1: Transmitter and receiver locations for the various indoor mea-surement situations.Measurement Situation Transmitter location Receiver locationLOS TX2 RX3Single wall TX1 RX1Double wall TX1 RX2In each combination of measurement situation and receive antenna arrayrotation, 15 measurement les were recorded. Each measurement le wasseparated by about ve minutes, and consists of 50 time separated individualsignal captures. The time separation between digital signal captures wasseveral 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 forreceived SNR of approximately 30 dB. The transmit power was selected suchthat adequate signal was received while low enough such that the signal didnot saturate the ampli er at the receiver and cause clipping of the signal.The approximate SNR for each of the di erent measurement scenarios isshown in Table 3.2. It is important to recognize that the signal strengthof the system used in this study is slightly higher than a typical WLANsystem. 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 25Single wall 30Double wall 2540Chapter 4Angle of Arrival EstimationMany di erent algorithms exist to estimate the parameters in a wirelesschannel [52]. Popular methods include the superresolution algorithms suchas multiple signal classi cation (MUSIC) [53] which is a spectral subspacemethod using eigendecomposition of the received signal estimated covariancematrix; and estimation of parameters via rotational invariance techniques(ESPRIT) [54], a subspace-based technique that divides the antenna arrayinto several sub-arrays. Other algorithms include Matrix Pencil [25, 55] andML derived algorithms [33, 56].This chapter contains the derivation and evaluation of the algorithmsthat are used to perform channel parameter estimation and determine theAOA of the mobile from channel measurements. Firstly the signal modelthat the algorithms use is described in section 4.1, followed by the theoreti-cal best estimation performance in section 4.2. Two di erent algorithms areimplemented in Matlab and evaluated, both based on ML classical estima-tion principles. The rst is the SAGE algorithm, described in section 4.3,which estimates multiple spatially and temporally separated signals arrivingat the receiver. The second is presented in section 4.4 and is a simple MLestimator which attempts to choose the earliest detected signal arrival anddetermines the direction for only that arrival. The algorithm performanceis then summarized in terms of the ability of the algorithms to identify andestimate the direct path AOA from the channel measurements. The perfor-mance evaluations of the ML and SAGE algorithms are contained in sections4.5 and 4.6 respectively. The chapter concludes with some AOA estimationperformance generalizations in section 4.7.41Chapter 4. Angle of Arrival Estimation4.1 Signal ModelThis section describes the mathematical models of the transmitted and re-ceived signals as functions of the following channel parameters: complexamplitude, delay and angle. The propagation of the signal is assumed tobe con ned to the horizontal plane, the elevation of the multipath arrivalsis ignored. This is appropriate for outdoor environments where elevationangles 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 signalsmay have signi cant elevation, and the use of this signal model may causeerrors in the channel parameter estimates. The signal model is used by thealgorithms to estimate the properties of the wireless channel and receivedsignal.The transmitted signal u(t) is a periodic pulse shaped PN sequence withK 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 Mtotal antennas spaced apart at half of the carrier wavelength 2, the locationin [x;y] of the mth antenna (numbered starting at 1) is rm =h0; (M 2m+1) 4i.A diagram of the antenna array and the arriving signal for multipath l isshown in Figure 4.1. The transmitted signal propagates and arrives at theantenna array via L di erent paths.It is assumed that the signal from each path arrives at all the antennas inthe array, which is a simpli cation that can be justi ed given the relativelysmall size of the antenna array. The propagation time of the wave withinthe antenna array is assumed to be negligible relative to the sampling ofthe received signal, so that the additional distance travelled by the signal toeach subsequent antenna appears only in the phase of the received signal.Finally, the signal of a single arrival is considered to be parallel at eachreceive antenna, which is justi ed assuming that the size of the antennaarray relative to the distance from the source or re ector is very small.The contribution of the lth multipath arrival to the received signal atantenna m issm(t; l) = cm( l) lu(t l) (4.1)42Chapter 4. Angle of Arrival Estimationλ2φlm = 1234Multipath arrivallOriginxyFigure 4.1: Diagram of the arriving signal for multipath component l at thefour element linear monopole array.where cm( ) = fm( ) exp j2 e( ) rm and the vector of parameters of thelth arrival is l = [ l; l; l]. These are respectively the relative delay, angleof arrival, and complex magnitude of the lth multipath arrival. The unitvector pointing in the direction is e( ), and fm is the electric eld patternof antenna m, which for an omnidirectional antenna fm = 1;8m. This isslightly di erent from the signal model in [57] since the e ects of Dopplerfrequency shift are assumed negligible.The total signal received by the mth antenna, the superposition of all Lmultipaths, is thereforeYm(t) =LXl=1sm(t; l) +rN02 Nm(t) (4.2)where Nm(t) is complex white Gaussian noise independent with respect toeach antenna with unit spectral height in the independent real and imaginarycomponents. A positive constant N0 denotes the power of the receiver noise.The channel measurements were taken when the actual AOA of the direct43Chapter 4. Angle of Arrival Estimationpath signal was 90 and 45 .4.2 Cram er-Rao Lower BoundThe best possible unbiased estimation variance of the parameters is deter-mined by the CRLB. The CRLB is calculated in the case where there isone multipath arrival. Using the signal model (4.1), with L = 1, the signalmodel can be summarized asY (t; ) = s (t; ) +rN02 N (t) (4.3)where Y (t; ) = [Y1 (t; );:::;YM (t; )]T, s (t; ) = [s1(t; );:::;sM(t; )]Tand N (t) = [N1 (t);:::;NM (t)]T. The PDF assuming N (t) is a complexwhite gaussian noise process isp(Y; ) = 1 N0exp 1N0jY(t) s(t; )j2 : (4.4)The CRLB is calculated as the diagonal terms of F 1 ( ) where F is theFisher information matrix (FIM) [58]. The element at the kth row and k0thcolumn of the FIM is given byFk;k0 ( ) = E @@ k@@ k0ln(p(Y; )) : (4.5)As shown in [57]Fk;k0 ( ) = 2N0< Z @@ ksH (t; ) @@ k0s (t; )dt : (4.6)The CRLB for the delay is derived using (4.6)F ; ( ) = 2N0< Z @@ sH (t; ) @@ s (t; )dt : (4.7)44Chapter 4. Angle of Arrival EstimationThis expands toF ; ( ) = 2Mj j2N0@2@ 2Zu (t )u(t )dt (4.8)using the signal model (4.1). Since the delay in this case is with respect tothe transmitted sequence, = 0 and the Fisher information isF ; ( ) = 2Mj j2N0@2@ 2a( )j =0 (4.9)where a( ) is the autocorrelation function of the transmitted sequence. TheCRLB for the delay isCRLB = [F ; ( )] 1 = N02Mj j2 @2@ 2a( )j =0: (4.10)The CRLB for the AOA is derived in the same manner using (4.6)F ; ( ) = 2N0< Z @@ sH (t; ) @@ s (t; )dt (4.11)which expands toF ; ( ) = 2j j2PuN0@@ cH( ) @@ c( ) (4.12)where c( ) = [c1( );:::;cM( )]T = j2 cos m. For a uniform linear arrayspaced at 2, m = 2h(M+1)2 1;:::;(M+1)2 MiT. Therefore (4.12) can beexpanded toF ; ( ) = 2j j2PuN0 j2 sin mT j2 sin m : (4.13)The nal expression for the Fisher information isF ; ( ) = 2 sin2 j j2Pu2N0MXm=1(M 2m+ 1)2: (4.14)45Chapter 4. Angle of Arrival EstimationThe CRLB is the AOA is thenCRLB = [F ; ( )] 1 = 2N0 2 sin2 j j2PuPMm=1 (M 2m+ 1)2: (4.15)The CRLB for the amplitude is determined in the same manner as thedelay and AOA. The derivation is straightforward and results in the FisherinformationF ; ( ) = 4MPuN0: (4.16)The resulting CRLB for the amplitude isCRLB = [F ; ( )] 1 = N04MPu: (4.17)The CRLB shows some very important information about the expectedaccuracy of the AOA estimates. As would be expected the estimation per-formance is related to the amount of receiver noise which is speci ed by N0,with lower variance and thus better estimation accuracy as the amount ofnoise decreases. More importantly, for a linear antenna array, the estimationaccuracy is a ected heavily by the number of antennas in the receive arrayas well as the AOA of the signal. For the best AOA estimation performancethe system should use as many antennas as possible and the signal shouldbroadside the antenna array.The number of antennas is limited practically in terms of the additionalcomputation required to process additional signals as well as the space andcost required to build the array. Since 802.11n WLAN infrastructure isthe target hardware for this positioning system, the limit of the number ofantennas is set by the number of antennas on an 802.11n AP, which canbe as many as four. In addition, as the physical size of the array increases,the assumption that the antenna array size is signi cantly smaller than thedistance from the wireless signal source ceases to hold and results in largeerrors in the signal model.The bandwidth of the signal being used to estimate AOAs has a po-tentially large e ect on the estimation performance. As shown from the46Chapter 4. Angle of Arrival EstimationCRLBs, the delay depends on the curvature of the autocorrelation functionof the transmitter signal @2@t2a(t)jt=0. This curvature is determined by thebandwidth of the signal used. A larger bandwidth signal allows for bettertime resolution of multipath arrivals, and therefore better estimation per-formance. The CRLBs assume that the other channel parameters for anarrival have no e ect on the estimation performance of the others. However,practical use in AOA positioning dictates that they can have large e ectson the estimation performance. For instance, the delay must be determinedclosely for the direct path arrival, or the AOA estimated will be in error.Since the delay estimation is a ected by the bandwidth of the signal used,the AOA is a ected 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 dataduring the AOA estimation process. This means that a positioning systemof this type could use the data signals as signals of opportunity to facilitatepositioning as opposed to sending additional signals into the wireless chan-nel for the sole purpose of positioning. Devices conforming to the 802.11nstandard can operate in one of two modes, with bandwidth of 20MHz or40MHz [9]. For this research 40MHz was used to gauge the best case sce-nario positioning performance. The signals were also used with the fullavailable bandwidth to investigate the e ects of the bandwidth reduction onthe estimation performance.4.3 General Channel Parameter EstimationMany di erent algorithms exist for channel parameter estimation. Most arefor 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 channelequalization [59] or to understand the statistical properties of various envi-ronments such that systems can be developed to more e ectively operate inthose situations. They also have uses in positioning, but may not be wellsuited for that application.47Chapter 4. Angle of Arrival EstimationThe SAGE algorithm was chosen to study the e ectiveness of a generalchannel parameter estimation algorithm for use in AOA-based positioning.It was chosen due to its derivation from proven ML techniques, and itsproven e ectiveness in channel parameter estimation [57]. It is a simpli ca-tion on a EM estimator [56], which in turn is formulated from a true MLestimator. The progressive derivation of the SAGE algorithm is shown inthis section.4.3.1 Maximum Likelihood Channel Parameter EstimationML estimation is based upon nding the parameters which maximize thePDF given the observed data. For channel parameter estimation, this isfurther complicated by the fact that it is not known ahead of time howmany signi cant multipath arrivals are present. This number can either beestimated or set to some number which should allow for characterization ofall 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 de ned asp(a;b) = 12 2 exp 12 2 (a a)2 + (b b)2) (4.18)which can be simpli ed by considering the random variable as a complexone in which x = a+bj and therefore = Efxg= a +j b givingp(x) = 12 2 exp 12 2jx j2 : (4.19)This can be applied to our observed CIRs, using the signal model in (4.2)with the knowledge thatEfYm(t)g=LXl=1sm(t; l) (4.20)since Nm(t) is a zero mean noise process. The resulting PDF is parametrized48Chapter 4. Angle of Arrival Estimationby the channel parameters for all the arrivals = [ 1;:::; L]p(Y(t); ) = 1 N0exp24 1N0 Y(t) LXl=1s(t; l) 235 (4.21)where Y(t) = [Y1(t);:::;YM(t)] is the vector of received signal values ands(t; l) = [s1(t; l);:::;sM(t; l)] is the vector of signal contributions to allreceive antennas for arrival l.Given that jbj2 = bHb, this can be expanded top(Y(t); ) = 1 N0exp24 1N0 Y(t) LXl=1s(t; l)!H Y(t) LXl=1s(t; l)!35:(4.22)This simpli es further to give the following log-likelihood function (Y(t); )by taking the natural logarithm of (4.22) then factoring and discarding termswhich do not depend on the channel parameters and hence do not a ectmaximization of this function (Y(t); ) = 2<( LXl=1s(t; l)HY(t)) LXl=1s(t; l) 2: (4.23)In matrix notation where S(t; ) = PLl=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) jS(t; )j2: (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) = 2ZD < S(t; )HY(t)dt ZD jS(t; )j2 dt: (4.25)The maximum likelihood estimate of the parameters is the set of param-49Chapter 4. Angle of Arrival Estimationeters b given observed data Y(t)b = argmax f ( ; Y)g: (4.26)This requires a large amount of computation to maximize for large numbersof 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 twochannel parameters for each multipath arrival as shown in the next section.4.3.2 Expectation-Maximization Channel ParameterEstimationThe EM algorithm [56] is an iterative approach that simpli es an ML esti-mator using the knowledge that the parameter estimation process would beeasier with all of the complete data, which are the individual signals receivedfor each multipath arrival. The complete data allows for the estimation ofa complete set of parameters without knowledge of any of the parametersfrom other signals. The complete data is unavailable as all of the multipathsignals are added together to form the received signal, called the incompletedata. 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) =LXl=1xl(t): (4.27)The complete data with noise for an arrival l is de ned asxl(t) = s(t; l) +rN02LNl(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 convergence50Chapter 4. Angle of Arrival Estimationis achieved, such that all parameters have been estimated. The expecta-tion step is the estimation of the complete data given previously estimatedchannel parameters, and the maximization step generates new parameterestimates based on these complete data estimates. The formulation of thelog-likelihood function follows similarly from that of the incomplete datagiven in the ML section ( l; ^xl) = 2ZD < sH(t; l)^xl(t) dt ZD js(t; l)j2 dt: (4.29)The expectation step, also called signal decomposition, estimates thecomplete data using previously estimated channel parametersb =hb 1;:::;b Liand the observed incomplete data Y(t), and is^xl(t;b ) = s(t;b l) +24Y(t) LXp=1s(t;b p)35: (4.30)The maximization step maximizes the log likelihood function (4.29) togenerate new parameter estimates given a complete data estimateb l = argmax lf ( l; ^xl)g: (4.31)The complex amplitude is a closed form function of the other two channelparameters. Thus, the estimates of the delay and angle areh^ l; ^ li= argmax[ ; ]fjz( ; ; ^xl)jg (4.32)and the amplitude is calculated from them as^ l = 1I c( ^ l) 2TuPuz ^ l; ^ l; ^xl : (4.33)I is the length in periods of the PN sequence included in the received signal,51Chapter 4. Angle of Arrival EstimationTu is the period of the PN sequence, c( ) = [c1( );:::;cM( )]; andz( ; ; ^xl) = c( )HZD u(t ) ^xl(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 forall arrivals, ^x1;:::;^xL.3. Maximization Step: Maximize the log-likelihood function (4.31) foreach arrival using (4.32) and (4.33). The parameter values that maxi-mize the log-likelihood function for one arrival are the updated channelparameter estimates for that arrival.4. Threshold Compare: If the change in all parameter estimates from theprevious iteration is lower than a prede ned threshold then the currentestimates are the nal EM channel parameter estimates. Otherwisego back to step 2.The complexity has been reduced since instead of a single 2L dimensionalmaximization, the algorithm requires L separate 2 dimensional maximiza-tions.4.3.3 Space-Alternating GeneralizedExpectation-Maximization Channel ParameterEstimationThe SAGE algorithm [33] further reduces implementation complexity overthe EM algorithm. For channel parameter estimation this is done by sepa-rating the estimation of the channel parameters for each multipath arrivalinstead of estimating them together [57] as in (4.32). In addition, the expec-tation step is performed between the estimation of each arrival instead of52Chapter 4. Angle of Arrival Estimationafter all arrivals. Each maximization of a single set of parameters for a mul-tipath arrival is followed by another expectation step. The SAGE algorithmhas 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 multipatharrivals. Each maximization step is for a single arrival, which contains twoseparate maximizations performed in the order that they are listed followedby the calculation of the estimated amplitude^ 0l = argmax n z ; ^ l; ^xl t;b o(4.35)^ 0l = argmax n z ^ 0l; ; ^xl t;b o(4.36)^ 0l = 1I c ^ 0l 2TuPuz ^ 0l; ^ 0l; ^xl t;b (4.37)where ^ 0l, ^ 0l, and ^ 0l are the new parameter estimates for arrival l; ^ l, ^ l,and ^ l are the previous parameter estimates for the same arrival; and b isthe previous parameter estimates for all of the arrivals. The complete dataestimate calculated by (4.30) beforehand is ^xl using the previous parameterestimates.The algorithm process is as follows:1. Initialize: Initialize all channel parameter estimates. Start at the l = 1arrival.2. Expectation Step: Perform signal decomposition (4.30) for the lth ar-rival to obtain one complete data signal estimate, ^xl.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.53Chapter 4. Angle of Arrival Estimation5. Threshold Compare/Full Iteration: If the change in all the parameterestimates from the previous full iteration is lower than a prede nedthreshold then the current estimates are the EM channel parameterestimates. 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 2through to step 4.4.3.4 SAGE ImplementationThe SAGE algorithm, while requiring signi cantly less computation thanEM or ML estimation, in the mathematical form derived requires perform-ing correlation with the transmitted sequence at every stage. Since thisoperation is performed on the same data each time, the algorithm is imple-mented to save calculation by performing it once on each sequence of receivedchannel data. This simpli es the SAGE algorithm to operate on the CIRinstead of the received signals. Since correlation is a linear operation, thealgorithms are equivalent.The expectation step after correlating both sides with the transmittedsignal u(t) becomes^kl t;b = ^ lcT ^ l a(t) +24h(t) LXp=1^ pcT ^ p a(t)35: (4.38)wherea(t) is the autocorrelation ofu(t), the CIR vector h(t) = [h1(t);:::;hM(t)]and ^kl t;b 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 allthe 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 byz( ; ; ^kl) = c( )H^kl ;b (4.39)54Chapter 4. Angle of Arrival Estimation^ 0l = argmax n z ; ^ l; ^kl t;b o(4.40)^ 0l = argmax n z ^ 0l; ; ^kl t;b o(4.41)^ 0l = 1I c ^ 0l 2TuPuz ^ 0l; ^ 0l; ^kl t;b (4.42)respectively.The initialization process is arbitrary, but [57] proposes the followingwhich 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, ^kl.3. Maximization Step: Perform the sequential maximization outlinedabove except with^ 0l = argmax ^kl ;b H ^kl ;b (4.43)instead of (4.40) and^ 0l = argmax c( )H^kl(^ 0l;b ) 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 ParametersThe resulting information from these general channel parameter estimationalgorithms is an estimated set of channel parameters b l = [^ l; ^ l; ^ l] for a55Chapter 4. Angle of Arrival Estimationcertain number of multipath arrivals l = 1;::;L. For positioning purposes,the only arrivals of interest are those that have a high probability of arrivingfrom the same direction as the transmitter. These are the most probabledirect paths which have travelled the shortest distance from transmitter toreceiver and therefore will arrive at the earliest delays. To determine theAOA 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, theAOA 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 thatan adequate number of arrivals has been estimated such that the LOS ar-rival has been estimated is crucial. Since the SAGE algorithm as describedprioritizes the estimation in terms of the delay and angle in that order, bothof which are maximized in terms of the correlation between the receivedand expected signal, it is possible to miss the direct path if that arrival hassu ciently low amplitude.4.3.6 Estimation of Number of Multipath ArrivalsThe maximum likelihood derived algorithms as described above do not haveprovisions for how the number of estimated multipath arrivals is selected.The accuracy with which the algorithms will estimate a channel with mul-tipath e ects depends greatly on how many multipath arrivals parametersare estimated for. Used for purposes of positioning, where the most likelydirect path is the most important, too few multipath arrivals may causemis-estimation of the earliest arrival, therefore using an inaccurate AOA.Likewise, estimation of more multipath arrivals than are in the wirelesschannel can cause the estimation of arrivals that don’t exist in the channel,essentially estimating noise. These estimates potentially have delays earlierthan the line of sight, which causes large errors in the estimated AOA.It has been proposed to use an algorithm to estimate the number ofmultipath arrivals prior to performing channel parameter estimation. This56Chapter 4. Angle of Arrival Estimationcould be performed for example by using information theory [60]. Thesetechniques confer a higher probability of selecting the correct number ofmultipath arrivals, but can be computationally complex. Since the aim ofthis research is not to fully investigate the best possible channel parameterestimation but to give a practical performance measure, a xed number ofestimated arrivals will be selected. This number will be selected based onthe number of estimated arrivals that results in the best overall performanceindicated in the performance analysis in section 4.6. Implementing an algo-rithm to estimate the number of multipath arrivals is not investigated.4.4 Simpli ed ML AOA ImplementationGeneral 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 todetermine the AOA of the earliest detectable arrival. ML principles are ap-plied to this problem in a simpli ed ML implementation. In this way noadditional computation is used to estimate arrivals that have little or noimpact on the nal 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 canbe estimated. After computing the CIR from the received channel data, theearliest delay in the CIR can be used to determine an ML estimate of theAOA. Using the signal model (4.1), the channel impulse response is modeledashm (t) =LXl=1 l exp j2 e ( l) rm (t l) (4.45)57Chapter 4. Angle of Arrival Estimationwhich simpli es tohm (t) =LXl=1 l exp j (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 isonly one arrival at the earliest delay. In e ect it estimates the center of massof the AOA of the earliest delay in the CIR. The CIRs are normalized intothe sequenceHm = 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 meansthat the complex amplitude does not need to be estimated, and thereforethe only parameter is e ectively the AOA.Assuming the signal has been corrupted by an independent circularGaussian noise process with power N0 as shown in (4.19), the PDF forHm isp(Hm; ) = 1 N0exp 1N0jHm exp(j cos (m 1))j2 : (4.48)The PDF can be simpli ed to a log-likelihood function (Hm; ) bytaking the natural logarithm and removing all terms that do not depend onthe parameter (Hm; ) =jHm exp(j cos (m 1))j2: (4.49)Note that the negative in the exponential has been removed, which meansthat instead of maximizing this log-likelihood function, it will be minimized.Considering all M antennas where H = [H1;:::;HM] this becomes (H; ) =MXm=1jHm exp(j cos (m 1))j2: (4.50)58Chapter 4. Angle of Arrival EstimationThe estimate of the AOA ^ is calculated as^ = argmin f (H; )g: (4.51)The implementation of this algorithm is straightforward application ofthe log-likelihood function scanning through angles of from 0 to 180 ata resolution of 0:1 . The critical part is the determination of which arrivalcorresponds to the earliest one. It appears that a simple and e ective wayof doing this is to choose the rst delay with an amplitude above somethreshold, in this case 10 dB, above the noise. While this works for the datacollected, it may be unsuitable in situations where there is very low signalstrength or weak direct paths. In those situations the threshold may needto be reduced to adequately select the earliest delay.4.5 ML Estimation PerformanceThe simpli ed ML algorithm was used to generate AOA estimates using thechannel measurements. The basic statistics of the estimates, in terms of theerror mean and standard deviation from the actual AOAs in each indoorsituation, are shown in Figure 4.2. The full bandwidth of the CIRs wasused, and each situation consists of 3000 estimates. The same statistics,using the ML algorithm on 40 MHz bandlimited CIRs are shown in Figure4.3. The statistics are also included for reference in Table A.1.The estimation error mean and standard deviation can be interpretedin 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 directpath from the CIR. An error mean close to zero is a potential indicator ofgood accuracy. The standard deviation on the other hand is a measure of theestimation precision. For a positioning system both of these are importantand contribute to the positioning performance.It was expected that reduction in the signal bandwidth would signi -cantly degrade AOA estimation performance simply due to the loss of timeresolution between multipath arrivals. These results indicate that the band-59Chapter 4. Angle of Arrival Estimation0.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.60Chapter 4. Angle of Arrival Estimationwidth reduction from 300 MHz to 40 MHz does not negatively impact AOAestimation, and AOA estimation actually improves in the LOS case. Thismay be a result of the multipath time density. The lower time density inthe NLOS situations may allow the multipath arrivals to still be resolvedeven 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 tothe high time density, but the bandwidth reduction causes the time densearrivals to be mixed together.The e ect of the bandwidth limitation process on the AOA estimationcan be thought of as a weighted averaging or temporal smoothing of theAOAs of individual arrivals at similar delays, with the weights being theamplitudes of the arrivals. The multipath in this particular situation maybe such that the center of mass of the smoothed AOAs results in betterestimates. This property cannot be relied upon since it is very environmentdependent.The general performance of this algorithm is promising. For most sit-uations, the standard deviation is approximately 5 . The estimation meanindicates that by choosing the earliest detectable part of the CIR, the al-gorithm is able to successfully identify the arrival of the direct multipathcomponent in the NLOS situations studied when = 90 . In the speci cLOS situation studied however, the arrival is not easily resolved due to thetime density of the arrivals, but temporal smoothing caused by the band-width reduction of multipath arrivals improves estimation and allows forusable AOA estimates. Despite what the results indicate, higher bandwidthis still preferred, since it will likely result in better AOA estimation in mostenvironments. The ability to resolve the direct path is much more impor-tant than relying on the properties of the wireless environment to result in acenter of mass AOA that resembles the same AOA as the direct path. Moremeasurements in di erent indoor wireless environments would bear this out.Since the SNR of the received signals is higher than would be expectedin 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 themeasurements is shown in Table 3.2. Between 5 dB and 10 dB of noise was61Chapter 4. Angle of Arrival Estimationadded to the measurements. The ML algorithm was used to estimate AOAsand the AOA estimation statistics are shown in Figure 4.4 for the variousindoor situations. It shows that the AOA estimation error remains similarfor the double wall separation and LOS situations. The estimates from thesingle wall situation contain signi cantly more error, both in the mean andstandard 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 shownby the CRLB, especially in NLOS situations since the direct path has a sig-ni cantly lower amplitude and therefore is more susceptible to error. Thiscan be seen in the estimation error for the single wall separated measure-ments, where the estimation error standard deviation is increased with theaddition 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 maynot have signi cant e ect on the estimation performance. The estimatesfrom the LOS measurement data show this.The double wall and LOS measurements resulted in similar estimation62Chapter 4. Angle of Arrival Estimationperformance regardless of whether noise was added or not. Since the orig-inal SNR of those measurements was 25 dB, the addition of a relativelysmall amount (5 dB) of noise does not impact the estimation performancesigni cantly.Due to the way the algorithm is implemented by selecting the rst 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 casein the single wall separated situation, since the AOA estimation bias andprecision su ers with a decrease in the SNR.The AOA estimation error shows that certain situations, primarily whenthe antenna array is rotated by 45 , cause signi cant bias in the estimates.This can be caused by misidenti cation of the direct path arrival. It can alsobe caused by a characteristic of the signal model: the assumption that allthe signals are con ned to the horizontal plane. While the antenna arraysare at the same height, many of the multipath arrivals at the receive antennaarray arrive with non-zero elevation. Additional elevation causes bias in theestimates. Given a horizontal AOA or azimuth of and an elevation angleof !, the additional distance travelled by the signal d to each subsequentantenna 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 , analgorithm assuming no elevation would estimate an AOA of 44:1 . Likewise,for an indoor environment with a larger elevation angle of 30 at the sameazimuth, the AOA would be estimated as 35:3 . At an azimuth of 90 , theelevation has no e ect on the estimated AOA. In some cases of elevationand azimuth, the current signal model is not able to represent the incomingsignal with only azimuth. This occurs when cos cos! > 1. This contributes toadditional error in the signal model that cannot be accounted for. With thesignal arriving at all the receive antennas broadside, the elevation has noe ect on the relative delay of the arrivals. The signal model used is con-63Chapter 4. Angle of Arrival Estimationλ2φ∆dxyzωFigure 4.5: The additional propagation distance to each receive antennagiven azimuth angle and elevation angle !.structed for an outdoor environment where the elevation angles are typicallylow, and therefore the bias in the AOA estimates is negligible.For indoor AOA estimation it is therefore imperative to estimate theelevation in addition to the azimuth. Unfortunately this likely involves ad-ditional antenna elements in the vertical plane to perform the elevationestimation. The bene t is that positioning can then be performed in 3D.For 2D positioning, it could be possible to remove the bias caused by theelevation without estimating it directly, with knowledge about the expectedelevation angle of multipath arrivals. For accurate AOA estimation, changesto the antenna array in the form of additional antennas in the vertical planewould be necessary. Since MIMO equipped WLAN APs will likely have lin-ear antenna arrays by default, changes to those arrays would be necessaryfor use in AOA positioning.A more thorough description of the AOA error statistics is in terms oftheir PDFs, contained in Appendix A, which are derived from the estimatehistograms. The PDFs of the AOA estimation error for the full bandwidthmeasurements are shown in Figures A.1, A.2, and A.3. The PDFs of the64Chapter 4. Angle of Arrival EstimationAOA error from the 40 MHz bandlimited measurements are shown in FiguresA.4, A.5, and A.6. The PDFs of the AOA error from the 40 MHz bandlimitedmeasurements when noise was added are shown in Figures A.7, A.8, andA.9. The PDFs are generally well formed although in some cases containtwo lobes. This is an indication that another multipath arrival other thanthe direct path is being estimated. This appears in estimates from thebandlimited measurements as well as those that use the full bandwidth.4.6 SAGE Estimation PerformanceThe SAGE algorithm was used to generate estimates using the channel mea-surements. The estimates were made using between 1 and 9 estimated totalmultipath arrivals. The AOA estimation performance is shown in Figures4.6 and 4.7 as a function of the number of estimated arrivals.Precision and accuracy of the SAGE estimates vary considerably withthe number of estimated arrivals. The mean estimation performance is theleast variable, with the broadside AOA = 90 measurements resulting inconsistent estimation mean between 2 and 6 estimated multipath arrivals.This means that for that range of estimated arrivals, the earliest estimatedarrival or arrivals were consistently the same for each. With the receiveantenna rotated to = 45 it is clear that there is no consistent estimationerror mean. This is not surprising considering the expected reduction inAOA estimation performance as the AOA di ers from broadsiding the arraydue 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 seemsto indicate that the estimation of additional multipath arrivals degrades theoverall accuracy of the estimation of the other arrivals. This is likely due toerrors in the signal model, which accumulate as additional signals are usedin the expectation process.In the simplest implementation, a xed number of arrivals is estimated.A xed number of 3 multipath arrivals will be used to evaluate the SAGEalgorithm, as a balance between accuracy and precision. Estimating more65Chapter 4. Angle of Arrival Estimation1 2 3 4 5 6 7 8 9−1001020304050AOA estimation error mean (degrees)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 indoorsituations at 300 MHz bandwidth, using varying numbers of total estimatedmultipath arrivals.1 2 3 4 5 6 7 8 9051015202530AOA estimation error standard deviation (degrees) 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 invarious indoor situations at 300 MHz bandwidth, using varying numbers oftotal estimated multipath arrivals.66Chapter 4. Angle of Arrival Estimationarrivals than 3 appears to result in poorer estimation precision, while theestimation accuracy remains similar.The basic statistics of the estimates using the SAGE algorithm with 3estimated arrivals, in terms of the error from the actual AOAs in each indoorsituation, are shown in Figure 4.8. The full bandwidth of the CIRs wasused, and each situation consists of 3000 estimates. The same statistics forestimates generated using the SAGE algorithm with 3 estimated multipatharrivals with the CIRs bandlimited to 40 MHz are shown in Figure 4.9. Thestatistics are also contained in Appendix B.These results show the poor performance of the SAGE algorithm in anindoor environment in identifying the AOA of the direct path arrival. Theestimates 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 numberof multipath re ections in the channel increases, and the attenuation of thedirect path makes it di cult to identify. The bandlimiting process resultsin 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 theML implementation is in the LOS case when the full bandwidth of 300 MHzis used. However the accuracy su ers, which is likely due to accumulation oferrors in the signal model. The improved estimation precision over the MLestimator is because the direct path signal has a high amplitude and sincethe SAGE algorithm estimates multiple arrivals, even at the same delay, thedirect path can be separated from the time dense arrivals with similar delay.Faced with the same situation, the ML implementation makes no attempt toseparate and identify the direct path. For example, three SAGE estimatedchannel parameters as well as the corresponding ML estimate from one ofthe LOS measurements where the direct path AOA is 90 resulted in theestimates shown in Table 4.1. It is clear in this case that two multipatharrivals at the earliest delay have been resolved. By choosing the one withthe largest amplitude as the direct path, the estimation precision is greatly67Chapter 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 indoorsituations 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 indoorsituations at 40 MHz bandwidth, using 3 total estimated multipath arrivals.68Chapter 4. Angle of Arrival EstimationTable 4.1: Example SAGE and ML estimated channel parameters for anLOS measurement, with actual AOA of 90 .Arrival Delay (samples) Amplitude AOASAGE #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 clearwhen the multipaths at the earliest delay are numerous. Insight into theML algorithm is also demonstrated, as the ML algorithm simply estimatesthe center of mass of the AOAs. The AOA for arrival #1 causes the MLestimator to estimate a larger than expected AOA. Although this exampledemonstrates promise for the usage of the SAGE algorithm, at least in LOScases, a look at the PDFs in Appendix B shows that the SAGE algorithmis also easily fooled into estimating non-direct path arrivals as well, and ismore susceptible to errors in the signal model.The PDFs derived from the histograms of the AOA estimation error forthe SAGE algorithm are contained in Appendix B. The estimates from fullbandwidth measurements processed using the SAGE algorithm are shownin Figures B.1, B.2, and B.3. The PDFs of the AOA error from the 40MHz bandlimited measurements are shown in Figures B.4, B.5, and B.6.All estimates were generated with the SAGE algorithm estimating 3 totalmultipath arrivals.The PDFs show that the AOA estimation error is higher than the MLestimator especially when the signal bandwidth was reduced to 40 MHz.It is clear that the SAGE algorithm does not adequately and consistentlyestimate the earliest arriving multipath, as there are signi cant outliers (sta-tistically signi cant groups with larger error) in the PDFs and estimationbias. This is the case even for the LOS measurements where the estimationperformance is expected to be highest. The presence of multiple lobes in allthe PDFs indicates that there are other multipath arrivals which are beingchosen as the earliest estimated multipath.69Chapter 4. Angle of Arrival EstimationIt is important to note that while the SAGE algorithm does not ap-pear to be useful for channel parameter estimation for WLAN positioningpurposes especially compared to a less computationally expensive ML imple-mentation, its ability to estimate channel parameters is proven in outdoorenvironments [57]. However, for indoor use, inaccurate assumptions made inthe formulation of the signal model may cause errors in the AOA estimates.These modeling errors accumulate when multiple arrivals are estimated. Inaddition, since the same signal model as the ML algorithm is used, it su ersfrom problems estimating multipath arrivals with non-zero elevation.The SAGE algorithm is ine cient at estimating the AOA in terms ofthe computational load since much of the computation is wasted on theestimation of multipath arrivals far away from the early delays. Performanceover the simple ML estimator could be improved at low computational costby estimating delays closer to the beginning of the CIR.4.7 Estimation Performance SummaryThe measurements show that AOA estimation indoors appears to be pos-sible through the use of the simple ML algorithm or the SAGE algorithmdepending 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 NLOSsituations, and considering the high computational complexity, is ill suitedfor positioning purposes in its current formulation.The two algorithms show that for the situations studied, the single wallNLOS separation results in the best AOA estimates. The estimation per-formance is poorer in the LOS and double wall NLOS cases. This is likelythe result of two opposing e ects. The rst is the reduction in the signalstrength of the direct path component as distance increases. This makesit more di cult to identify the direct path, and therefore the AOA. Thesecond is the multipath time density. The density of multipath arrivals intime is higher in the cases when the separation between the transmitter andreceiver is low and results in poorer AOA estimates.70Chapter 5Positioning SimulationThe positioning performance using AOA measurements is evaluated througha positioning simulation. The simulations involve a 2D simulated user posi-tion and trajectory in a network of APs. At each user position, the actualAOAs to the each AP are calculated based on their known positions, andthen random error is added to those AOAs to simulate the e ects of thewireless channel and the AOA estimation. The noisy AOAs are then usedto estimate the known position. The error between the estimated positionand the known position is observed.The generation of the random AOAs is shown in section 5.1. These noisyAOAs are then used in a positioning algorithm to estimate the user position.Two di erent positioning algorithms are used: a linearized LS approach anda more sophisticated EKF, described in sections 5.2 and 5.3 respectively.The e ect of geometry is then discussed in section 5.4. The error in theestimated position relative to the actual position is evaluated and analyzedfor a xed position simulation as well as a moving mobile simulation insection 5.5.5.1 Random AOA GenerationFor each simulated mobile position random error is added to the actualAOAs at each AP. The errors in the AOAs are generated according to oneof the PDFs generated from the AOA estimation described in Chapter 4.The PDFs are contained in Appendices A and B, and are constructed fromthe histograms of the AOA estimates. For implementation in Matlab, AOAerror is generated from a PDF by rst calculating the cumulative density71Chapter 5. Positioning Simulationfunction (CDF). For a PDF f(x), the CDF F(x) is calculated asF(x) =Z x 1f(x0)dx0 (5.1)using x0 as the integration variable. The CDF has a value between 0 and1 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 1500.10.20.30.40.50.60.70.80.91AOA error (degrees)CDFFigure 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 togenerate a uniformly distributed random number in the interval [0;1]. Theresult of the rand() function is used as the value on the y-axis of the CDFto determine the amount of AOA error which is the corresponding x-axisvalue. This AOA error is added to the actual AOA of the mobile from theAP. This process is performed independently for each AOA generated.5.2 AOA Least Squares PositioningOne of the simplest algorithms with which to determine position from AOAsis LS. The basis of LS estimation is to nd the position that minimizes thesum of the squared error between the AOA observations and the expected72Chapter 5. Positioning SimulationAOA observations corresponding to the estimated position, given no knowl-edge of the noise distribution. Due to the non-linear relationship betweenthe AOA observations and the mobile position, a linearized LS algorithm isused [58].The relationship between the position of the mobile x = [xm;ym]T andAOA 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 ofthe 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 rst order Taylor expansion to iteratively performpositioning estimation. An initial estimate for x is required. Another esti-mator such as a best linear unbiased estimator (BLUE) [58] could be usedto generate an initial position, or other information available could be used.The choice of the initial position will be discussed later. Firstly the expectedobservations l = [l1;:::;lK]T for K APs given the current estimated position^x must be calculatedlk = gk (^x): (5.4)Next the design matrix A is calculated, by determining the rst orderpartial derivatives of gk for all APs with respect to x. It is linearized aboutthe current estimated position ^x. It has the formA = @@x26666664g1(x):::gK(x)37777775x=^x=26666664@g1@xm@g1@ym: :: :: :@gK@xm@gK@ym37777775x=^x: (5.5)73Chapter 5. Positioning SimulationThe partial derivatives are@gk@xm = yk x2k + y2k (5.6)@gk@ym = xk x2k + y2k: (5.7)Note that the denominator of the partial derivatives is the square of theestimated range between the mobile and AP.The amount of correction to the previous position estimate ^x to obtainthe new estimate ^x0 is dependent on the di erence between the expectedobservations l and the actual observations = [ 1;:::; K]T. This di erenceis called the misclosure vectorw = l: (5.8)The sum of the squares of the elements in the misclosure vector is the residualerror.The misclosure vector and the design matrix are used to compute acorrection 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 anew estimate^x0 = ^x + : (5.10)The process from the calculation of the expected observations to the newestimate is repeated. The new estimate is used in the next iteration as theprevious estimate until the correction becomes small in which case the LSalgorithm converges to a position estimate. If the correction never becomessmall 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 solution74Chapter 5. Positioning Simulationthat converges. The choice of the initial position estimate is therefore im-portant, and the LS algorithm generally works best when the initial positionestimate is close to the actual position. Also, poor AP geometry can causedivergence if it causes ATA to become nearly singular. For instance, thisoccurs when the APs and the mobile are nearly colinear.5.3 Extended Kalman FilterKalman ltering is an estimation algorithm that has become very importantfor many applications. It allows for the e cient combination of di erentsequential observations to perform state estimation. For time varying posi-tioning using AOAs, the Kalman lter uses current AOA observations, theprevious position estimate and a model about the movement of the mobileto estimate an updated position. The basis of a Kalman lter is similar toLS since it minimizes the sum of the squared error between the actual andexpected observations. In the same manner as the LS estimator, because therelationship between the position state of the system and the observationsis 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 theconstant velocity model. In this model, the state of the system consists of theinstantaneous position and velocities in all directions. For 2D positioning,the easting and northing directions will be considered. The velocities _xand _y in the easting and northing directions respectively, are assumed tobe constant, and therefore the position state transitions to the next stateaccordingly depending on the sampling time t. The current time sampleis n. The new estimate includes prediction through the model using theestimate from the previous sampling time n 1. The model de nes the75Chapter 5. Positioning Simulationstate to state behaviour from time sample n 1 to n asxn =266664xnyn_xn_yn377775= f (xn 1) =266664xn 1 + _xn 1 tyn 1 + _yn 1 t_xn 1_yn 1377775: (5.11)When the estimation begins, the EKF must be given an initial statebecause of the prediction process. In a practical system, the rst incomingobservations could be used to initialize the state to the position indicated bya LS estimator. However, for the simulation used in this thesis, the initialposition 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 newstate using an EKF. The previous state is rst used to predict the currentstate based on the dynamic model. The predicted state is then correctedusing the incoming observation or measurement data. Quantities based onthe predicted state are denoted with ( ), and those after application of thenew observations are denoted with (+).For the purposes of the model used here, the state transition model islinear and time invariant. If it was time varying, then the function for theappropriate time would be used. The previous state estimate ^xn 1 (+) isused to predict the state estimate for the next interval ^xn ( ) using thedynamic model^xn ( ) = f (^xn 1 (+)): (5.12)As with the LS estimator, there exists a function gk that relates thestate 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^xn ( ) as^ k;n = gk (^xn ( )): (5.13)To propagate the e ects of the prediction on the covariance matrix of the76Chapter 5. Positioning Simulationestimates, the dynamic model is linearized into the state transition matrix = @f@x =2666641 0 t 00 1 0 t0 0 1 00 0 0 1377775: (5.14)Since the dynamic model is linear and time invariant, this only needs to bedetermined once, otherwise it would be linearized about the current stateestimate for every run of the EKF.Similar to the LS estimator, the function gk relating the state to theposition must be linearized by taking the derivative with respect to thestate to obtain the measurement sensitivity matrixGn @@x26666664g1(x):::gK(x)37777775x=^xn( )=26666664@g1@xm@g1@ym 0 0: : : :: : : :: : : :@gK@xm@gK@ym 0 037777775x=^xn( ): (5.15)Since the position does not depend on the velocities, their partial derivativesare zero.An EKF depends heavily on the estimated covariance or error in allquantities that are used to determine the current state. Quantities withlarge estimated error contribute little to state estimates. The estimatederror is updated every time the EKF is used to generate a new set of stateestimates. Given the previous state covariance Pn 1 (+), the new statecovariance prior to incorporation of new observations Pn ( ) is calculatedasPn ( ) = Pn 1 (+) T + Q (5.16)based on the prediction of the state transition model as well as the errorcovariance of the model itself Q.The covariances are arbitrary and are selected according to how well77Chapter 5. Positioning Simulationcertain quantities are known. For example, if it is known beforehand thatthe constant velocity state transition model is inaccurate in terms of theprediction of the movement of the mobile, then the covariance is selectedto be large, such that the state transition model prediction is weightedless when combined with new observations. The covariance matrices of thestate transition model Q and the observations R are free parameters whichcan be used to optimize the performance of the EKF. There is usually noway to de nitively know these quantities, so the programmer of the EKFapproximates 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 inunits of radians squared, which corresponds to an AOA estimation standarddeviation of 5:7 which adequately represents the expected error in the MLprocessed AOA measurements. Q was chosen to beQ =2666641 0 0 00 1 0 00 0 2 00 0 0 2377775(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 thesimulation to cope with sudden changes in mobile direction. Experimentallythese covariances appeared to perform at least as well as any others that weretried. The error of 1 m for the positions was chosen due to the simulationinterval of 1 s, in which the moving user is not likely to experience a changein position of much larger than 1 m.The Kalman gain Kn is a measure of how much the observations areused to estimate the nal state estimate as opposed to the prediction of thedynamic model. It is computed asKn = Pn ( ) GTn GnPn ( ) GTn + R 1: (5.18)The new estimate of the covariance of the state estimate Pn (+) is thenupdated from Pn ( ) to take into account the error in the new observations78Chapter 5. Positioning SimulationPn (+) = I KnGn Pn ( ): (5.19)The predicted system state estimate can now be updated^xn (+) = ^xn ( ) + Kn n ^ n (5.20)depending on the error between the expected measurements ^ n =h^ 1;n;:::; ^ K;nipredicted 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 isrecorded at each time interval. Note that unlike the linearized LS estimator,the EKF is not iterative.5.4 AP Geometry ConsiderationsPositioning accuracy depends highly on the geometry of the APs. For AOA-based positioning, the positioning accuracy improves greatly as the distancebetween the APs and the mobile decreases. The positioning simulationconsists of four APs placed in the corners of a 30 m x 30 m square. Thiswas selected due to the typical deployment density of WLAN APs, and forthe favourable geometry which results in good overall expected positioningaccuracy. The whole simulation area is a 40m x 40m square centered at theorigin.The DOP metric describes how the geometry and measurement errora ect 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 mincrements in the simulation area are shown in Figure 5.2. The DOP valuesfor each position are calculated [62](ATA) 1 ="EDOP2 EDOP NDOP EDOP NDOP NDOP2#(5.21)where the design matrix A, as de ned in (5.5), is evaluated at the actual79Chapter 5. Positioning Simulationlocation of the mobile, and is the unitless correlation between the NDOPand EDOP. NDOP is the DOP in the northing direction and EDOP the DOPin the easting direction. Smaller DOP indicates lower positioning error dueto better geometry.The correlation is shown in Figure 5.3(a) and the overall horizontalDOP in Figure 5.3(b). The location of the APs are shown as green triangles.The HDOP indicates horizontal positioning performance and is calculatedasHDOP =pNDOP2 +EDOP2: (5.22)The HDOP shows that positioning performance is relatively poor in thehorizontal 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, whichoccurs when is 0, the error area becomes an ellipse. This is shown inFigure 5.4. Each dot represents an estimated position and all are estimatesof 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 theerror in the AOA measurements is 5 , then the geometry would need to besuch that the DOP in m=rad is less than 23. Using the AP geometry inthe simulation studied, the HDOP shown in Figure 5.3(b) indicates thatthis DOP requirement is approximately met at most positions inside thesquare made by the APs. Similarly, for the same desired positioning perfor-mance, but with more accurate measurements, the DOP requirement couldbe relaxed.5.5 Positioning PerformanceThe positioning performance of the LS and EKF algorithms is evaluatedusing a Monte Carlo positioning simulation. Two di erent simulations areused. The rst evaluates the mobile position at xed positions, and thesecond determines mobile position for a moving mobile user. In each simu-80Chapter 5. Positioning SimulationEasting (m)Northing (m) −20 −10 0 10 20−20−15−10−50510152005101520253035(a) Northing DOP.Easting (m)Northing (m) −20 −10 0 10 20−20−15−10−50510152005101520253035(b) Easting DOP.Figure 5.2: DOP for the northing and easting directions for AOA positioningin units of metres per radian.Easting (m)Northing (m) −20 −10 0 10 20−20−15−10−505101520−1−0.500.51(a) Unitless correlation between DOP innorthing and easting directions.Easting (m)Northing (m) −20 −10 0 10 20−20−15−10−5051015200510152025303540(b) Horizontal DOP in units of metres perradian.Figure 5.3: DOP correlation and HDOP for AOA positioning.81Chapter 5. Positioning Simulation(a) = 0. (b) < 0. (c) > 0.Figure 5.4: Example estimated positions depending on correlation betweenDOP in northing and easting directions.lation, for each position of the mobile, the actual AOAs at each of the APsis calculated. These actual AOAs are then corrupted with random erroraccording to one of the PDFs contained in Appendices A and B.A more complex simulation might apply random AOA error accordingto di erent PDFs at di erent APs. For instance, with PDFs from the samealgorithm but di erent receive antenna rotation and amount of obstructionbetween transmitter and receiver. The distance between transmitter andreceiver could be used to simulate likely obstruction. However, there aremany cases in which this doesn’t represent actual usage. The best, averageand worst case positioning performance can still be evaluated using a sin-gle PDF to generate AOA error for all APs, so addding complexity to thesimulation is unnecessary.The rst simulation estimates the position of the user for xed positionsin the simulation area. This is performed for all positions in the simulationarea in 1 m increments, and at each position the simulation is run 1000times. The resulting root mean square (RMS) position error at each positionis recorded. This is suited only to the LS positioning algorithm, since it isnot time varying. The LS positioning performance is assessed and veri esthe positioning error indicated by the DOP.In the second simulation, a single simulation run consists of a movingmobile with two-part constant velocity trajectory: from (-15 m, 0 m) to (0m, 15 m) and then to (15 m, 0 m). The length of the simulation is 80 s and82Chapter 5. Positioning Simulationthe position of the mobile is estimated every 1 s. Both the LS and EKFare used for the trajectory estimation. Each algorithm is run with 1000trials of the trajectory simulation. The RMS position error for each trial isrecorded. Since LS only uses the current AOA measurements to determinethe user position, and the EKF uses previous position and measurementinformation, this simulation serves to show the positioning improvementspossible by using more measurement data.The RMS position error Erms is computed asErms =vuut 1NNXn=1 (xn ^xn)2 + (yn ^yn)2 : (5.23)For a single xed position in the xed position simulation, the RMS positionerror is computed withnrepresenting the simulation trial, (xn;yn) the actualposition of the mobile, (^xn; ^yn) the estimated position for trial n, and Nthe number of total trials, 1000. The estimated mobile position is onlyincluded in the RMS calculation for position estimates that converge. Fora single estimated trajectory trial in the trajectory simulation, the RMSposition error is computed with n as the simulation epoch, (xn;yn) theactual mobile position at epoch n, (^xn; ^yn) the estimated position at epochn, and N the total simulation length in epochs. Position estimates in thetrajectory simulation are used in the RMS error calculation even if they didnot converge.The average RMS error (ARMSE) for the xed position simulation is theRMS position error averaged over all the possible positions of the mobile inthe simulation area. The ARMSE for the trajectory simulation is the RMSposition error averaged over 1000 trials of the trajectory simulation.5.5.1 Fixed Position Estimation PerformanceSince LS does not take into account the previous position or any previouspositioning measurements, the performance of the LS at each position canbe examined. The results from the xed positioning simulation in terms ofthe ARMSE are contained in Table C.1.83Chapter 5. Positioning SimulationThe results using the estimates from the ML algorithm are discussed inthis section, and some comments about the usage of the SAGE estimatesincluded.When performing the positioning simulations, it was observed that theinitial position estimates had a signi cant e ect on the convergence of theLS algorithm. A suitable method of easily determining the initial positionestimate was found to be by dividing the simulation area into smaller ar-eas as shown in Figure 5.5. Selecting the appropriate area was performedby observing the noisy AOAs, identifying them in terms of quadrants andmaking 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 areain 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 estimatesfor each area are shown as blue dots. The positions of the APs are shownas green triangles.Figure 5.5: LS initial position estimates based on approximate area.An example of the RMS positioning error using the LS algorithm forall positions in a simulation area of 40 m x 40 m centered at the origin is84Chapter 5. Positioning Simulationshown in Figure 5.6. The PDF Figure A.5(a) for the ML processed 40 MHzbandlimited measurements taken with single wall separation was used togenerate the random AOA error. This represents the best case positioningaccuracy. The plot of the number of the trials that resulted in convergingposition estimates is shown in Figure 5.7. The positions of the APs are shownas green triangles. The ARMSE, or RMS position error averaged over everyposition in the simulation area, results in an expected positioning error of0.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 doublewall separation is shown in Figures 5.8 and 5.9. This represents a moretypical expected positioning performance. The ARMSE for the simulationarea in this case is 2.82 m. There is a slight di erence in the gradient ofthe ARMSE in Figure 5.8 and the HDOP shown in Figure 5.3(b). Thisrotational 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 deviationof the measurement error PDF, resulting in Figure 5.10, which matches theHDOP closely.The convergence of the LS algorithm is poor in close proximity to theAPs. When near an AP, the matrix ATA becomes nearly singular andtherefore ill conditioned. This leads to the divergence of the LS positionestimate.Simulations incorporating random AOA error according to the PDFsfrom the ML generated estimates resulted in positioning estimates with errorbetter than 5 m, and in some cases better than 1 m. The only exceptionto this was the PDF from the LOS measurements taken when the receiveantenna was rotated by 45 at full bandwidth shown in Figure A.1(b). Asnoted in Table C.1, this was the only PDF from the ML estimates thathad signi cant outliers, with a group near 40 AOA error. For an overallperformance metric, the average of the ARMSEs of the position estimatesfrom the PDFs corresponding to the bandlimited ML estimates is 2.1 m.85Chapter 5. Positioning SimulationEasting (m)Northing (m) −20 −15 −10 −5 0 5 10 15 20−20−15−10−50510152000.511.5Figure 5.6: RMS position error in metres from 1000 Monte Carlo simulationtrials, using AOA error generated from Figure A.5(a).Easting (m)Northing (m) −20 −15 −10 −5 0 5 10 15 20−20−15−10−50510152001002003004005006007008009001000Figure 5.7: Number of converged position estimates out of 1000 Monte Carlosimulation trials, using AOA error generated from Figure A.5(a).86Chapter 5. Positioning SimulationEasting (m)Northing (m) −20 −15 −10 −5 0 5 10 15 20−20−15−10−50510152000.511.522.533.544.55Figure 5.8: RMS position error in metres from 1000 Monte Carlo simulationtrials, using AOA error generated from Figure A.6(a).Easting (m)Northing (m) −20 −15 −10 −5 0 5 10 15 20−20−15−10−50510152001002003004005006007008009001000Figure 5.9: Number of converged position estimates out of 1000 Monte Carlosimulation trials, using AOA error generated from Figure A.6(a).87Chapter 5. Positioning SimulationEasting (m)Northing (m) −20 −15 −10 −5 0 5 10 15 20−20−15−10−5051015200510152025303540Figure 5.10: RMS position error divided by the AOA error standard devi-ation in metres per radian from 1000 Monte Carlo simulation trials, usingAOA error generated from Figure A.6(a).Similarly, with the estimates from the SAGE algorithm, the PDFs withsigni cant outliers resulted in unusable position estimates. This con rmsthat a LS algorithm is a poor choice of positioning algorithm in the presenceof AOA error with signi cant outliers. Due to the inconsistency of the SAGEalgorithm in the various indoor measurement situations, the results from the xed position simulation reinforce that SAGE is unsuitable for positioningapplications.The positioning performance of the LS algorithm depends heavily on thePDF of the measurements. It is highly susceptible to high positioning errordue to outliers. The large error in the outliers causes the position estimateto diverge heavily, or converge to a poor position solution. This causes verylarge errors. The formulation of the LS algorithm results in these errors sincethe position estimate is selected to minimize the squared error between theexpected and actual observations. If one of the observations contains severeerror, the square of that error is considered in weighting the importance of88Chapter 5. Positioning Simulationthe observations. An already large error contributes even more to the nalposition estimate.There are di erent approaches to solving the problem caused by out-liers. Temporal smoothing allows for some reasonable changes in positionfrom 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 usein the position estimation process. High residual error between the expectedand actual observations for the nal LS position solution can indicate thepresence of outliers. With more observations than the minimum necessaryfor position estimation, subsets of the available observations can be usedto determine the outlying observation. For example in this simulation, LSsolutions can be computed for all combinations of observations from threeof the four available APs. The LS solution that is associated with the leastresidual error is chosen as the one that excludes the outlying observation.5.5.2 Trajectory Estimation PerformanceThe estimation of positions in the trajectory simulation is evaluated for boththe LS and EKF. The trajectory was simulated 1000 times, and the ARMSEof those simulations recorded. The ARMSEs corresponding to simulationsusing the AOA error from the di erent measurements are shown in TableC.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 FigureA.6(a) for the ML processed bandlimited measurements with = 90 . Forthis trajectory estimation trial, the RMS error for the LS position estimateswas 2.86 m and 1.91 m for the EKF position estimates. This was selectedto represent the average performance of the positioning system using MLestimates.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 shownin Figure 5.12. This PDF includes frequent outliers, and demonstrates thesigni cantly improved positioning of the EKF over that of the LS. The89Chapter 5. Positioning SimulationRMS error for the LS position estimates was 4.67 m and 2.89 m for theEKF estimates. Note that one of the LS estimated positions is outside ofthe simulation area, with large positioning error.The best case positioning performance is evaluated in the same manneras the xed position simulation. The PDF used corresponds to the MLestimates from the bandlimited single wall separated measurements shown inFigure A.5(a). The estimated trajectories using the LS and EKF algorithmsare shown in Figure 5.13. For this simulation trial, the RMS position errorfor 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 LSalgorithm, the trajectory estimates show the bene t of the prediction basedon the constant velocity model. From one position estimate to the next, theestimates from the EKF show better consistency, and are less erratic. Thatis, they change direction less often, and are less susceptible to large positionchanges. This is due partly to how well the constant velocity model matchesthe actual trajectory, which is also of constant velocity. The downside tothe incorporation of the prediction in an EKF is shown in Figure 5.14 wherethe sudden change in direction of the mobile causes the EKF to overshootthe turning point of the mobile trajectory. It takes a few additional positionestimates to correct the velocity and return closer to the actual trajectory.The dynamic prediction model may not be well suited to the expectedmovement of the mobile. In this case if the positioning performance is un-acceptable, the covariance of the dynamic model Q can be increased suchthat the prediction contributes less to the nal position estimates. The po-sition estimates are therefore in uenced mostly by the AOA measurements.For example, if the mobile is expected to move irregularly or undergo largeacceleration, either a new dynamic model could be used, or Q increased.An increase in Q diminishes the advantage of using an EKF over an LSestimator. A better choice is to improve the dynamic model such that itmore accurately models the movement of the mobile. An unsuitable choiceof dynamic model and poorly chosen Q results in less accurate positionestimates.The EKF clearly has better positioning performance, especially in the90Chapter 5. Positioning Simulation−20 −15 −10 −5 0 5 10 15 20−20−15−10−505101520Easting (m)Northing (m) ActualLS estimatedEKF estimatedAPFigure 5.11: Typical example trajectory simulation trial with LS and EKFusing AOA error from ML estimates PDF shown in Figure A.6(a).−20 −15 −10 −5 0 5 10 15 20−20−15−10−505101520Easting (m)Northing (m) ActualLS estimatedEKF estimatedAPFigure 5.12: Worst case example trajectory simulation trial with LS andEKF using AOA error with signi cant outliers from SAGE algorithm usingthe PDF shown in Figure B.4(a).91Chapter 5. Positioning Simulation−20 −15 −10 −5 0 5 10 15 20−20−15−10−505101520Easting (m)Northing (m) ActualLS estimatedEKF estimatedAPFigure 5.13: Best case example trajectory simulation trial with LS and EKFusing AOA error from ML estimates PDF shown in Figure A.5(a).presence of outliers. The improvement of the EKF over the LS shown inTable 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 wouldnot be used, but their inclusion underscores an important advantage of theEKF over an LS estimator. The EKF does not su er 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 estimatedtrajectory.Averaging the ARMSEs for the positioning simulation using PDFs fromthe bandlimited ML estimates results in a general positioning performanceof 2.1 m. It is coincidental that this is the same as the result from the xedposition simulation. Note that this positioning error is only valid for thisparticular mobile trajectory. However, this is assumed to be representativeof actual positioning performance since the beginning, middle and end ofthe trajectory are in areas where relatively poor positioning performance92Chapter 5. Positioning Simulation−20 −15 −10 −5 0 5 10 15 20−20−15−10−505101520Easting (m)Northing (m) ActualEKF estimatedAPFigure 5.14: Example trajectory simulation run with EKF showing e ect ofmobile movement not matching dynamic model.is expected, as indicated by the HDOP in Figure 5.3(b). In addition, theconstant velocity trajectory seems to be reasonably well suited to humanmovement.The performance of the LS and EKF are expected to become similaras the number of observations increases, in this case the number of APsand therefore AOAs. In the case of gaussian AOA error with only twoobservations for a stationary mobile, the positioning performance is expectedto be approximately 2.5 times better for an EKF over an LS estimator[63]. With PDFs that have outliers, the positioning performance is muchbetter using an EKF. Much of the performance bene t of the EKF overan LS algorithm depends on how well the model of the mobile’s movementmatches the actual mobile trajectory. The results of this thesis indicateEKF positioning performance increases upwards of 1.5 times better over anLS algorithm in terms of the ARMSE positioning error in the majority ofthe cases studied.The decision to use either EKF or LS to estimate the user position is de-93Chapter 5. Positioning Simulationpendent on the type of position required. For systems that simply computesingle instantaneous position estimates using a single set of observations, anLS algorithm is the most useful. For other systems which track user posi-tion over time, or integrate numerous observations, an EKF o ers the mostbene t.94Chapter 6Conclusions and FutureWork6.1 Conclusions6.1.1 AOA EstimationAOA estimation was evaluated using actual MIMO indoor channel measure-ment data. The system used and the environment characterized are bothsimilar to that of an 802.11n WLAN network deployment. Three di erentindoor propagation scenarios were studied: LOS, as well as with the receiverand transmitter separated by one and two walls. In each scenario measure-ments were taken when the direct path broadsided the receive antenna arrayas well as with the receive antenna array rotated by 45 . In addition, themeasurements were used both at the full recorded 300 MHz bandwidth, andbandlimited to 40 MHz, which better represents WLAN usage.The AOA of the signal was estimated from these measurements usingtwo di erent channel characterization algorithms, an ML implementationand SAGE. The ML algorithm is a computationally and conceptually simplealgorithm that estimates a single arrival at the earliest delay in the CIR. TheSAGE algorithm is signi cantly more complex, and attempts to estimatemultiple arrivals in the CIR. SAGE is also suitable for other types of channelparameter estimation unrelated to positioning. The two algorithms wereused to estimate AOAs from the measurement data, and the error betweenthe estimates and the actual known AOAs was observed.It was found that the ML algorithm resulted in AOA estimates withstandard deviation at times better than 5 . The ML algorithm also appeared95Chapter 6. Conclusions and Future Workto be una ected by the reduction in bandwidth. In the case where therewas LOS between transmitter and receiver, the AOA estimation improvedas the bandwidth was reduced. Additional measurements would need to betaken to determine whether this improvement is common, or is situationand environment speci c. The ML implementation used appears to be ableto resolve the direct multipath arrival frequently, and therefore results inuseful AOA estimates.Since the SNR of the measurements is higher than might be expectedfrom a WLAN system, noise was added to the measurements to lower theSNR by between 5 and 10 dB. The added noise had little e ect on the MLAOA estimation for the LOS and double wall separated measurements. Thisis attributed to those measurements having the least amounts of noise addedsince the SNR for those measurements was the lowest. The single wall sep-arated measurements had the most noise added and the resulting estimateswere impacted negatively. In addition to the usual e ects of noise causinginaccuracy in the AOA estimates, the added noise also causes error in theAOA estimates by making the selection of the direct multipath componentmore di cult. In the case when the selection of the direct path is madeimproperly, signi cant error appears in the AOA estimate.The SAGE algorithm, unlike the ML algorithm, estimates more thanone multipath arrival. The AOA estimation performance depends on thenumber of arrivals, and the AOA estimation was evaluated for various num-bers of multipath arrivals. The best overall AOA estimation resulted fromthe choice of three multipath arrivals, for the measurements and situationsstudied. In a practical system, the number of multipath arrivals would beestimated beforehand, and that number used in the SAGE estimation.The SAGE estimates were mostly poorer than those generated by theML algorithm. SAGE prioritizes the estimation of the multipath arrivalsby their amplitude. In cases where the direct path does not have a highamplitude, the SAGE algorithm estimates other multipaths instead and usestheir AOAs causing error. This is witnessed as larger error in the AOAestimates compared to the ML algorithm for the NLOS measurements. Itis also apparent in the AOA error PDFs, contained in Appendices A and96Chapter 6. Conclusions and Future WorkB, which show multiple lobes, indicating a series of di erent AOAs that areestimated. SAGE does have better AOA estimation precision, albeit withreduced accuracy, when compared to the ML algorithm in the LOS casewhen the bandwidth was 300 MHz however, since the direct path has a highamplitude. The ML algorithm makes no attempt to di erentiate betweenmultipath arrivals, assuming the presence of only one. The SAGE algorithm,by estimating multiple arrivals, is able to distinguish between arrivals withthe same or similar delay. This results in improved estimation performance.Also unlike the ML algorithm, the reduction in bandwidth had a verynoticeable negative e ect on the AOA estimates generated by SAGE. Thisis because the SAGE algorithm performance hinges on the ability to distin-guish multipath arrivals from each other. The reduced bandwidth causesthe multipath arrivals to mix together, and are therefore more di cult toseparate.Since the ML algorithm is signi cantly less computationally expensivecompared to the SAGE algorithm, and results in better AOA estimates inmost situations, it is the most likely candidate for practical implementa-tion. Improvements to target the SAGE algorithm speci cally for use inpositioning could make it a more attractive option. The results suggest thatgeneral parameter estimation algorithms such as SAGE are not well suitedfor positioning purposes.Common between the SAGE and ML estimates, was a signi cant biasin the AOA estimates, especially when the direct path signal impinged onthe rotated receive antenna array, when = 45 . This is a fault inherent tothe antenna array and signal model used. The signal model was constructedunder the assumption that the wireless signals were con ned to the horizon-tal plane, which is often not true in an indoor environment. This causes abias 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 theelevation of the signal, since the antennas are con ned to the horizontalplane themselves. An antenna array with elements in the vertical plane isnecessary to perform accurate AOA and elevation estimation.97Chapter 6. Conclusions and Future Work6.1.2 Position EstimationThe PDFs of the AOA error determined from the AOA estimation algo-rithms were used in a 2D positioning simulation to determine the expectedpositioning performance of this type of system. The positioning simulationinvolved the simulation of the mobile within a network of APs placed at thecorners of a square. For every simulated position of the mobile, the actualAOAs from each of the APs were calculated and subsequently corruptedwith random AOA error according to one of the PDFs generated from theAOA estimation process. These noisy AOAs were then used in a positioningestimation algorithm to determine the mobile position.Two types of positioning simulation were used, one where the mobilewas simulated at xed positions in the square simulation area, and anotherwhere the mobile was simulated to have a two-part constant velocity movingtrajectory. A linearized LS algorithm was the rst algorithm used to judgethe positioning performance. The LS estimator uses a single set of AOAmeasurements to determine a single mobile position, and was used for bothtypes of position simulation.The xed position simulation using the LS estimator showed positioningperformance of 2.1 m using the ML estimates. The SAGE algorithm esti-mates showed that the LS estimator performs very poorly in the presenceof statistically signi cant outliers. Using PDFs with those outliers, the po-sition estimates could not be relied on, and the ARMSE was larger than thesimulation area size, indicating that the position estimates were not useful.The trajectory estimation performance was evaluated using both the LSalgorithm and an EKF. The EKF estimates the trajectory of the mobileby using a dynamic model of its movement. In this simulation a constantvelocity model was used. The model predicts the movement of the mobileusing previous position estimates and uses the AOA observations to re nethose position estimates and update the state of the model. In this way,better positioning performance is attained when the mobile movement issimilar to that described by the model.Through the estimation of a trajectory, the poor performance of the LS98Chapter 6. Conclusions and Future Workalgorithm in the presence of outliers was rea rmed, and observed as verylarge deviations in the estimated trajectory. The EKF was shown to bemore resistant to the e ect of outliers, showing no signi cant deviations intrajectory. This is because the prediction process constrains the positionestimates such that it resists large changes in the mobile behaviour notconsistent with the dynamic model. Using the ML estimates, the EKFdemonstrated position performance of 2.1 m.This study performs a realistic analysis of the potential of 802.11n WLANAPs 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 di erent positioning appli-cations, speci cally those that require approximately room-level accuracy.RSS positioning techniques already o er approximately this level of accu-racy, and are simpler to implement. However an AOA-based system is morerobust to changes in the indoor environment. With more sophisticated sys-tems and more research, AOA-based WLAN positioning should be able tosurpass the performance indicated.6.2 Future DevelopmentFuture possible research in this area can be classi ed into two groups: de-velopments leading to positioning performance improvements; and hardwarevalidation of the positioning system using a prototype.6.2.1 Positioning Performance ImprovementsTo improve positioning performance, there several areas which can be tar-geted. One of the most important is the AOA estimation algorithm, whichcan be improved in a number of ways. This could include the biasing of ageneral channel parameter estimation algorithm to estimate multipaths atdelays as close to the earliest detectable delay as possible. This should resultin improved estimation accuracy. Improvements to the signal model would99Chapter 6. Conclusions and Future Workalso contribute to better AOA estimates, speci cally to more accurately rep-resent the propagation indoors since most signal models make assumptionsthat may not hold for an indoor environment. This includes the assumptionof horizontal propagation as well as the parallel signal arrivals. Implemen-tation of a method to estimate the number of multipaths in the channelcould result in improved estimation as well. Further investigation into howsuitable other general channel parameter estimation algorithms are for iden-ti cation of the direct path could result in enhanced accuracy. Modi cationof these algorithms as well as the development of new algorithms may benecessary, speci cally for the purposes of direct path identi cation.The e ectiveness of algorithms in estimating AOA can be improved witha better understanding of the indoor wireless channel. Additional channelmeasurements would be very useful in con rming some of the phenomenathat were observed with the limited set of measurement data available forthis study. Additional measurements that better mimic an actual WLANnetwork would be useful as well. This includes measurements where theAPs are at ceiling height, which is typical for most WLAN networks. Thiswould likely con rm that the estimation of the elevation angle is critical toaccurate AOA estimation.Also related to the positioning performance are improvements to thespeci cs of the system such as the addition of more antennas to improveAOA estimation, and the use of a non-linear antenna array to improve theAOA estimation for multipaths arriving at greater elevations. This wouldalso serve to resolve any ambiguity in the mobile direction. For instance,antennas in the vertical plane would allow for elevation estimation, which inturn is likely to improve AOA estimates. An example of a potential antennaarray is one that places antennas at the corners of a cube. This allows forthe estimation of the elevation as well as allowing for unambiguous AOAestimation. However, this requires eight antennas, which is more than canbe expected for a WLAN AP. A suitable antenna array could have antennasat the vertices of a tetrahedron, keeping the number of antennas the same asa WLAN AP and yet addresses both the ambiguity and elevation problem.100Chapter 6. Conclusions and Future Work6.2.2 Prototype DevelopmentThe nal step to proving the concept of a WLAN-based AOA positioningsystem is the construction of a hardware prototype. This involves the designand construction of multiple base stations to perform the task of the APs,each with a multiple antenna array. A single transmitter would be necessaryas well. For ease and exibility of making changes, programmable technolo-gies such as eld programmable gate arrays (FPGAs) and microcontrollerswould be good choices for implementation. The APs would be programmedwith the AOA estimation algorithms, and then either in real-time or o inethe AOAs would be used to determine the mobile position. This validatesthe positioning accuracy indicated through simulation.The positioning performance could then be characterized by using thesystem in various indoor environments and conditions. Two di erent sce-narios would be useful to characterize: when the AP geometry is similar tothat of an existing WLAN network, that is, not optimized for the purposesof positioning; and when the APs are placed in such a way as to obtain themost accurate positioning estimates.101References[1] Federal Communications Commision, \Wireless 911Services: FCC Consumer Facts", [Online], viewedMay 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-levelreliability monitoring in urban personal satellite-navigation", Aerospaceand 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 andevaluation 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’schallenges and opportunities", Computer, vol. 36, no. 5, pp. 30{37,May 2003.102References[7] Yao-Jen Chang, Hung-Huan Liu, Li-Der Chou, Yen-Wen Chen, andHaw-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-telecommunicationsand information exchange between systems-local and metropolitan areanetworks-speci c requirements-part 11: Wireless LAN medium accesscontrol (MAC) and physical layer (PHY) speci cations: Amendment4: Enhancements for higher throughput", IEEE Unapproved Draft StdP802.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- certi ed 802.11n draft 2.0: Longer-range, faster-throughput, multimedia-grade wi- 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 SystemsSoftware and Middleware, 2007. COMSWARE 2007. 2nd InternationalConference on, pp. 1{5, Jan. 2007.[13] Fei Peng and Jinyun Zhang, \On residual carrier frequency o set 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 overviewof MIMO communications - a key to gigabit wireless", Proceedings ofthe IEEE, vol. 92, no. 2, pp. 198{218, Feb 2004.103References[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 andMobile 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 indoorenvironment based on RSS ngerprinting and arti cial neural network",Telecommunications, 2007. ConTel 2007. 9th International Conferenceon, 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], viewedJune 18, 2008, available from the World Wide Web:<http://www.ekahau.com/?id=4200>.[21] K. Kaemarungsi and P. Krishnamurthy, \Properties of indoor receivedsignal strength for wlan location ngerprinting", Mobile and UbiquitousSystems: Networking and Services, 2004. MOBIQUITOUS 2004. TheFirst 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.104References[23] I. Oppermann, A. Karlsson, and H. Linderback, \Novel phase based,cross-correlation position estimation technique", Spread SpectrumTechniques 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 InternationalSymposium 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 andpositioning applications at 2.4, 5.2 and 5.8 GHz", Radio and WirelessSymposium, 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 lookat positioning aspects for future sensor networks", Signal ProcessingMagazine, 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 di cult 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 lters and low-costMEMS sensors", Positioning, Navigation and Communication, 2007.WPNC ’07. 4th Workshop on, pp. 1{7, 22-22 March 2007.105References[31] R. Singh, M. Guainazzo, and C.S. Regazzoni, \Location determina-tion using wlan in conjunction with gps network (global positioningsystem)", 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 Transactionson], 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-TsairChen, \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, \HybridTDOA/AOA indoor positioning and tracking using extended Kalman lters", 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.106References[39] Zhang Guoping and S.V. Rao, \Position localization with impulse ul-tra wide band", Wireless Communications and Applied ComputationalElectromagnetics, 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 ight 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 indoorposition location with wireless LANs", Personal, Indoor and Mobile Ra-dio Communications, 2002. The 13th IEEE International Symposiumon, vol. 2, pp. 720{724 vol.2, 15-18 Sept. 2002.[45] S. Severi, G. Liva, M. Chiani, and D. Dardari, \A new low-complexityuser tracking algorithm for wlan-based positioning systems", Mobileand Wireless Communications Summit, 2007. 16th IST, pp. 1{5, July2007.[46] A. Kushki, K.N. Plataniotis, A.N. Venetsanopoulos, and C.S. Regaz-zoni, \Radio map fusion for indoor positioning in wireless local areanetworks", Information Fusion, 2005 8th International Conference on,vol. 2, pp. 8 pp.{, July 2005.107References[47] D. Tse and P. Viswanath, Fundamentals of wireless communication,Cambridge University Press, rst edition, 2005.[48] K.I. Pedersen, P.E. Mogensen, and B.H. Fleury, \A stochastic model ofthe 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-elementarrays of circular patch antennas in indoor clustered mimo channels",Military Communications Conference, 2005. MILCOM 2005. IEEE, pp.13{19 Vol. 1, Oct. 2005.[50] Ka e P.L., Intarapanich A., Sesay A.B., McRory J., Davies R.J., andMcGibney G., \A wideband MIMO channel measurement system forindoor o ce environment", in Proceedings of World Wireless Congress2004, 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 angleand delay estimation using shift-invariance techniques", Signal Pro-cessing, IEEE Transactions on [see also Acoustics, Speech, and SignalProcessing, IEEE Transactions on], vol. 46, no. 2, pp. 405{418, Feb1998.108References[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, VolumeI: Estimation Theory, Prentice-Hall, rst 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 IEEETransactions 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 positioningsystems", Electronics Letters, vol. 42, no. 5, pp. 291{292, March 2006.[63] K. Spingarn, \Passive position location estimation using the extendedkalman lter", Aerospace and Electronic Systems, IEEE Transactionson, vol. AES-23, no. 4, pp. 558{567, July 1987.109Appendix A: ML EstimationStatisticsThis appendix includes the statistics for the simpli ed ML algorithm AOAestimates 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 theSNR lowered to 20 dB with the addition of noise. The rst and second or-der statistics, mean and standard deviation , are contained in Table A.1.The measurements that contain signi cant statistical outliers, those thathave additional lobes with large error far from the main lobes, are noted inthe comments. The PDFs derived from the histograms of the estimates areshown in Figures A.1 - A.9.110Appendix A: ML Estimation StatisticsTableA.1:MeanandstandarddeviationoftheMLAOAestimatesfortheindoormeasurements.Bandwidth(MHz)NoiseAddedObstruction ( )PDFFigure ( ) ( )Comments40LOS90A.7(a)-0.217.74YSinglewall90A.8(a)4.418.48OutliersDoublewall90A.9(a)-2.537.13LOS45A.7(b)5.156.14OutliersYSinglewall45A.8(b)7.364.63Doublewall45A.9(b)-1.174.75LOS90A.4(a)-1.388.05NSinglewall90A.5(a)0.451.72Doublewall90A.6(a)-1.536.39LOS45A.4(b)3.935.44OutliersNSinglewall45A.5(b)10.861.79Doublewall45A.6(b)-0.635.57300LOS90A.1(a)2.2610.86NSinglewall90A.2(a)0.871.67Doublewall90A.3(a)1.056.28LOS45A.1(b)6.1413.59OutliersNSinglewall45A.2(b)10.522.27Doublewall45A.3(b)0.506.30111Appendix A: ML Estimation Statistics−20−100 1020304002468AOA Estimation Error (degrees)f(x)(a) AOA of = 90 .−20 0 20 40012345678AOA 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 10051015AOA Estimation Error (degrees)f(x)(a) AOA of = 90 .0 5 1015202530051015AOA 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.112Appendix A: ML Estimation Statistics−20−10 0 10 200123456AOA Estimation Error (degrees)f(x)(a) AOA of = 90 .−20−10 0 10 2002468AOA 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−100 10203001234567AOA Estimation Error (degrees)f(x)(a) AOA of = 90 .−100 10203040012345678AOA 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.113Appendix A: ML Estimation Statistics−5 0 5051015AOA Estimation Error (degrees)f(x)(a) AOA of = 90 .0 5 10 15 2005101520AOA 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 2001234567AOA Estimation Error (degrees)f(x)(a) AOA of = 90 .−15−10−5 0 5 10150246810AOA 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.114Appendix A: ML Estimation Statistics−20−100 10203040012345AOA Estimation Error (degrees)f(x)(a) AOA of = 90 .−20 0 20 40012345678AOA 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 200123456AOA Estimation Error (degrees)f(x)(a) AOA of = 90 .−5 0 5 10152025012345678AOA 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.115Appendix A: ML Estimation Statistics−20−10 0 10 200123456AOA Estimation Error (degrees)f(x)(a) AOA of = 90 .−15−10−5 0 5 100246810AOA 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.116Appendix B: SAGEEstimation StatisticsThis appendix includes the statistics for the SAGE algorithm AOA esti-mates in the various indoor situations. The algorithm estimates a total of3 multipath arrivals. The estimates for the measurements used at 300 MHzand 40 MHz are included. The rst and second order statistics, mean andstandard deviation , are contained in Table B.1. The measurements thatcontain signi cant statistical outliers, those that have additional lobes withlarge error far from the main lobes, are noted in the comments. The PDFsderived from the histograms of the estimates are shown in Figures B.1 - B.6.117Appendix B: SAGE Estimation StatisticsTableB.1:MeanandstandarddeviationoftheSAGEAOAestimatesfortheindoormeasurements.Bandwidth(MHz)Obstruction ( )PDFFigure ( ) ( )Comments40LOS90B.4(a)6.7610.87OutliersSinglewall90B.5(a)6.485.39Doublewall90B.6(a)-5.9214.23OutliersLOS45B.4(b)15.152.06Singlewall45B.5(b)30.1022.17OutliersDoublewall45B.6(b)32.4533.29Outliers300LOS90B.1(a)5.414.39Singlewall90B.2(a)7.602.14Doublewall90B.3(a)-0.066.66LOS45B.1(b)19.2510.78OutliersSinglewall45B.2(b)29.4718.83OutliersDoublewall45B.3(b)19.8624.57Outliers118Appendix B: SAGE Estimation Statistics−5 0 5 10 150510152025AOA Estimation Error (degrees)f(x)(a) AOA of = 90 .102030405060700246810121416AOA 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 120510152025303540AOA Estimation Error (degrees)f(x)(a) AOA of = 90 .10 20 30 40 50 6005101520253035AOA Estimation Error (degrees)f(x)(b) AOA of = 45 .Figure B.2: PDF of the SAGE AOA estimation error for the single wallmeasurements using 300 MHz bandwidth.119Appendix B: SAGE Estimation Statistics−15−10−5 0 5 10150510152025AOA Estimation Error (degrees)f(x)(a) AOA of = 90 .0 20 40 60 8002468AOA Estimation Error (degrees)f(x)(b) AOA of = 45 .Figure B.3: PDF of the SAGE AOA estimation error for the double wallmeasurements using 300 MHz bandwidth.−100 10 20 30 400510152025AOA Estimation Error (degrees)f(x)(a) AOA of = 90 .10 12 14 16 18 200510152025AOA 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.120Appendix B: SAGE Estimation Statistics−5 0 5 10 15051015202530AOA Estimation Error (degrees)f(x)(a) AOA of = 90 .10 20 30 40 50 6005101520AOA Estimation Error (degrees)f(x)(b) AOA of = 45 .Figure B.5: PDF of the SAGE AOA estimation error for the single wallmeasurements using 40 MHz bandwidth.−60−40−200 20024681012AOA Estimation Error (degrees)f(x)(a) AOA of = 90 .0 20 40 60 800246810AOA Estimation Error (degrees)f(x)(b) AOA of = 45 .Figure B.6: PDF of the SAGE AOA estimation error for the double wallmeasurements using 40 MHz bandwidth.121Appendix C: PositioningSimulation ResultsThis appendix includes the positioning error for the two di erent simula-tions, using the PDFs contained in Appendices A and B.Table C.1 contains the simulation results in terms of the position ARMSEfor the xed 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 ARMSEfor the two-part constant velocity trajectory simulation. For this simulation,both the LS and EKF were used to estimate the mobile position. Theimprovement in positioning performance for the EKF over LS is shown aswell. When the improvement is very large, a ’+’ symbol is used.In both tables, ’-’ indicates very large positioning error, >> 40 m. In thetrajectory simulation, this large positioning error is caused by the inclusionof divergent positioning solutions in the RMS calculations. In addition, thePDFs that have been considered to have outliers are indicated.122Appendix C: Positioning Simulation ResultsTableC.1:FixedpositionsimulationARMSEforthevariousindoormeasurementtypes.EstimatorBandwidth(MHz)Obstruction ( )PDFFigureLSARMSE(m)PDFNotesML40LOS90A.4(a)3.0140Singlewall90A.5(a)0.7940Doublewall90A.6(a)2.8140LOS45A.4(b)2.5440Singlewall45A.5(b)4.4940Doublewall45A.6(b)1.85300LOS90A.1(a)4.31300Singlewall90A.2(a)0.85300Doublewall90A.3(a)2.68300LOS45A.1(b)-Outliers300Singlewall45A.2(b)4.64300Doublewall45A.3(b)2.02SAGE40LOS90B.4(a)5.36Outliers40Singlewall90B.5(a)3.6940Doublewall90B.6(a)-Outliers40LOS45B.4(b)7.1840Singlewall45B.5(b)-Outliers40Doublewall45B.6(b)-Outliers300LOS90B.1(a)2.67300Singlewall90B.2(a)3.42300Doublewall90B.3(a)2.87300LOS45B.1(b)17.84Outliers300Singlewall45B.2(b)-Outliers300Doublewall45B.3(b)-Outliers123Appendix C: Positioning Simulation ResultsTableC.2:TrajectorysimulationARMSEforthevariousindoormeasurementtypes.EstimatorBandwidth(MHz)Obstruction ( )PDFFigureARMSE(m)ARMSEPDFNotesLSEKFLS/EKFML40LOS90A.4(a)-2.17+40Singlewall90A.5(a)0.750.471.6040Doublewall90A.6(a)-1.76+40LOS45A.4(b)-1.94+40Singlewall45A.5(b)4.494.840.9340Doublewall45A.6(b)-1.16+300LOS90A.1(a)-3.11+300Singlewall90A.2(a)0.770.511.51300Doublewall90A.3(a)2.751.681.64300LOS45A.1(b)-4.01+Outliers300Singlewall45A.2(b)-4.62+300Doublewall45A.3(b)-1.30+SAGE40LOS90B.4(a)-3.38+Outliers40Singlewall90B.5(a)-2.81+40Doublewall90B.6(a)-4.24+Outliers40LOS45B.4(b)-6.52+40Singlewall45B.5(b)-20.95+Outliers40Doublewall45B.6(b)-27.61+Outliers300LOS90B.1(a)-2.30+300Singlewall90B.2(a)2.973.030.98300Doublewall90B.3(a)-1.75+300LOS45B.1(b)-8.12+Outliers300Singlewall45B.2(b)-16.84+Outliers300Doublewall45B.3(b)-13.34+Outliers124
- 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 | 2008 |
Date Issued | 2008-11-18T21:00:09Z |
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 |
File Format | application/pdf |
Language | eng |
Collection |
Electronic Theses and Dissertations (ETDs) 2008+ |
Date Available | 2008-11-18 |
Provider | Vancouver : University of British Columbia Library |
DOI | 10.14288/1.0066798 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of (Okanagan) |
Degree Grantor | University of British Columbia |
Graduation Date | 2008-11 |
Campus |
UBCO |
Scholarly Level | Graduate |
URI | http://hdl.handle.net/2429/2792 |
Aggregated Source Repository | DSpace |
Download
- Media
- ubc_2008_fall_wong_carl.pdf [ 2MB ]
- [if-you-see-this-DO-NOT-CLICK]
- Metadata
- JSON: 1.0066798.json
- JSON-LD: 1.0066798+ld.json
- RDF/XML (Pretty): 1.0066798.xml
- RDF/JSON: 1.0066798+rdf.json
- Turtle: 1.0066798+rdf-turtle.txt
- N-Triples: 1.0066798+rdf-ntriples.txt
- Original Record: 1.0066798 +original-record.json
- Full Text
- 1.0066798.txt
- Citation
- 1.0066798.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Country | Views | Downloads |
---|---|---|
United States | 25 | 1 |
Palestine | 11 | 0 |
Canada | 7 | 0 |
China | 6 | 10 |
India | 6 | 0 |
Russia | 3 | 0 |
Malaysia | 2 | 0 |
Germany | 2 | 5 |
Romania | 1 | 0 |
Australia | 1 | 0 |
Ukraine | 1 | 1 |
Unknown | 1 | 0 |
United Kingdom | 1 | 0 |
City | Views | Downloads |
---|---|---|
Ramallah | 11 | 0 |
Unknown | 11 | 6 |
Ashburn | 9 | 0 |
Ottawa | 6 | 0 |
Chennai | 5 | 0 |
Phoenix | 4 | 1 |
University Park | 3 | 0 |
Shanghai | 2 | 0 |
Ipoh | 2 | 0 |
Beijing | 2 | 0 |
Washington | 2 | 0 |
Shenzhen | 2 | 9 |
Stockholm | 1 | 0 |
{[{ mDataHeader[type] }]} | {[{ month[type] }]} | {[{ tData[type] }]} |
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0066798/manifest