!"#" $!%&’& GNSS Array-based Acquisition: !"##$% &’"’$ (#)*+,"’-*# "#. /*-#’ 0+"#1,-’’$+23$ $-5$+ 6$1-7# -# Theory and Implementation 89%’-2:#’$##" &;1’$,1 Ph.D. Dissertation !"#$%& ’"$’($)*+ !*-.+/%"/ 01(+$%+& 2%34(5!/- 6’5/-7*5!’*+8/%’6*’0/9 2%3 ’*.3)6/%/9:/(%* Javier Arribas L´azaro Centre Tecnol`ogic de Telecomunicacions de Catalunya (CTTC) Parc Mediterrani de la Tecnologia %%*;*’04!-"( #*’’/-)%$ /++(’5<%$!= Av. Carl Friedrich Gauss 7 B4 2/=*%">/’"$?@(5’*-A#/$%;*’0B$>>!’( *"($’+ 08860 Castelldefels, Barcelona (SPAIN) C’(1/%+("*")$-("D/ ’( *0/B*"*-!’;* e-mail: [email protected] E*% /-$’*F2/ />G/%HIIJ Ph.D. Thesis Advisor: Dr. Carles Fern´andez–Prades Centre Tecnol`ogic de Telecomunicacions de Catalunya (CTTC) Av. Carl Friedrich Gauss 7 B4 08860 Castelldefels, Barcelona (SPAIN) e-mail: [email protected] Ph.D. Thesis Tutor: Dra. Ana Isabel P´erez-Neira Full Professor Universitat Polit`ecnica de Catalunya (UPC) Campus Nord UPC, Edifici D5 c/ Jordi Girona, 1-3 08034 Barcelona (SPAIN) e-mail: [email protected] July 5, 2012 A mis abuelas Silvina y Salom´e. iv Abstract This Dissertation addresses the signal acquisition problem using antenna arrays in the general framework of Global Navigation Satellite Systems (GNSS) receivers. The term GNSS classifies those navigation systems based on a constellation of satellites, which emit ranging signals use- ful for positioning. Although the American GPS is already available, which coexists with the renewedRussianGlonass, theforthcomingEuropeancontribution(Galileo)alongwiththeChi- nese Compass will be operative soon. Therefore, a variety of satellite constellations and signals will be available in the next years. GNSSs provide the necessary infrastructures for a myriad of applications and services that demand a robust and accurate positioning service. The position- ing availability must be guaranteed all the time, specially in safety-critical and mission-critical services. Examining the threats against the service availability, it is important to take into account that all the present and the forthcoming GNSSs make use of Code Division Multiple Access (CDMA) techniques. The ranging signals are received with very low pre-correlation signal-to- noiseratio(intheorderof 22dBforareceiveroperatingattheEarthsurface). Despitethatthe − GNSS CDMA processing gain offers limited protection against Radio Frequency Interferences (RFI),aninterferencewithainterference-to-signalpowerratiothatexceedstheprocessinggain can easily degrade receivers’ performance or even deny completely the GNSS service, specially conventional receivers equipped with minimal or basic level of protection towards RFIs. As a consequence, RFIs (either intentional or unintentional) remain as the most important cause of performance degradation. A growing concern of this problem has appeared in recent times. Focusing our attention on the GNSS receiver, it is known that signal acquisition has the lowestsensitivityofthewholereceiveroperation,and,consequently,itbecomestheperformance bottleneck in the presence of interfering signals. A single-antenna receiver can make use of time and frequency diversity to mitigate interferences, even though the performance of these techniques is compromised in low SNR scenarios or in the presence of wideband interferences. On the other hand, antenna arrays receivers can benefit from spatial-domain processing, and thusmitigatetheeffectsofinterferingsignals. Spatialdiversityhasbeentraditionallyappliedto thesignaltrackingoperationofGNSSreceivers. However, initialtrackingconditionsdependon signal acquisition, and there are a number of scenarios in which the acquisition process can fail as stated before. Surprisingly, to the best of our knowledge, the application of antenna arrays to GNSS signal acquisition has not received much attention. This Thesis pursues a twofold objective: on the one hand, it proposes novel array-based acquisition algorithms using a well-established statistical detection theory framework, and on the other hand, it demonstrates both their real-time implementation feasibility and their per- formance in realistic scenarios. The Dissertation starts with a brief introduction to GNSS receivers fundamentals, providing some details about the navigation signals structure and the receiver’s architecture of both GPS and Galileo systems. It follows with an analysis of GNSS signal acquisition as a detection problem, using the Neyman-Pearson (NP) detection theory framework and the single-antenna acquisition signal model. The NP approach is used here to derive both the optimum detector (known as clairvoyant detector) and the so-called Generalized Likelihood Ratio Test (GLRT) detector, which is the basis of almost all of the current state-of-the-art acquisition algorithms. Going further, a novel detector test statistic intended to jointly acquire a set of GNSS satellites v vi is obtained, thus reducing both the acquisition time and the required computational resources. The effects of the front-end bandwidth in the acquisition are also taken into account. Then, the GLRT is extended to the array signal model to obtain an new detector which is abletomitigatetemporallyuncorrelatedinterferencesevenifthearrayisunstructuredandmod- eratelyuncalibrated, thusbecomingoneofthemaincontributionsofthisDissertation. Thekey statisticalfeatureistheassumptionofanarbitraryandunknowncovariancenoisematrix,which attemptstocapturethestatisticalbehavioroftheinterferencesandothernon-desirablesignals, while exploiting the spatial dimension provided by antenna arrays. Closed form expressions for thedetectionandfalsealarmprobabilitiesareprovided. Performanceandinterferencerejection capabilityaremodeledandcomparedbothtotheirtheoreticalbound. Theproposedarray-based acquisition algorithm is also compared to conventional acquisition techniques performed after blindnull-steeringbeamformerapproaches,suchasthepowerminimizationalgorithm. Further- more, the detector is analyzed under realistic conditions, accounting for the presence of errors in the covariance matrix estimation, residual Doppler and delay errors, and signal quantization effects. Theoretical results are supported by Monte Carlo simulations. As another contribution of this Dissertation, the second part of the work deals with the designandtheimplementationofanovelFieldProgrammableGateArray(FPGA)-basedGNSS real-time antenna-array receiver platform. The platform is intended to be used as a research tool tightly coupled with software defined GNSS receivers. A complete signal reception chain includingtheantennaarrayandthemultichannelphase-coherentRFfront-endfortheGPSL1/ GalileoE1wasdesigned,implementedandtested. Thedetailsofthedigitalprocessingsectionof theplatform,suchasthearraysignalstatisticsextractionmodules,arealsoprovided. Thedesign trade-offs and the implementation complexities were carefully analyzed and taken into account. As a proof-of-concept, the problem of GNSS vulnerability to interferences was addressed using the presented platform. The array-based acquisition algorithms introduced in this Dissertation wereimplementedandtestedunderrealisticconditions. Theperformanceofthealgorithmswere compared to single antenna acquisition techniques, measured under strong in-band interference scenarios, including narrow/wide band interferers and communication signals. The platform was designed to demonstrate the implementation feasibility of array-based acquisition algorithms, leaving the rest of the receiver operations (mainly, tracking, navigation message decoding, code and phase observables, and basic Position, Velocity and Time (PVT) solution)toaSoftwareDefinedRadio(SDR)receiverrunninginapersonalcomputer,processing inreal-timethespatially-filteredsignalsamplestreamcomingfromtheplatformusingaGigabit Ethernet bus data link. In the last part of this Dissertation, we close the loop by designing and implementing such software receiver. Theproposedreceivertargetsmulti-constellation/multi-frequencyarchitectures,pursuingthe goals of efficiency, modularity, interoperability, and flexibility demanded by user domains that require non-standard features, such as intermediate signals or data extraction and algorithms interchangeability. In this context, we introduce an open-source, real-time GNSS software de- fined receiver (so-named GNSS-SDR) that contributes with several novel features such as the use of software design patterns and shared memory techniques to manage efficiently the data flow between receiver blocks, the use of hardware-accelerated instructions for time-consuming vector operations like carrier wipe-off and code correlation, and the availability to compile and run on multiple software platforms and hardware architectures. At this time of writing (April 2012), the receiver enjoys of a 2-dimensional Distance Root Mean Square (DRMS) error lower than 2 meters in a GPS L1 C/A scenario with 8 satellites in lock and a Horizontal Dilution Of Precision (HDOP) of 1.2. Resumen Estatesisabordaelproblemadelaadquisici´ondelasen˜alusandoarraysdeantenasenelmarco general de los receptores de Sistemas Globales de Navegaci´on por Sat´elite (GNSS). El t´ermino GNSS engloba aquellos sistemas de navegaci´on basados en una constelaci´on de sat´elites que emiten sen˜ales u´tiles para el posicionamiento. Aunque el GPS americano ya est´a disponible, coexistiendo con el renovado sistema ruso GLONASS, actualmente se esta realizando un gran esfuerzo para que la contribuci´on europea (Galileo), junto con el nuevo sistema chino Com- pass, est´en operativos en breve. Por lo tanto, una gran variedad de constelaciones de sat´elites y sen˜ales estar´an disponibles en los pr´oximos an˜os. Estos sistemas proporcionan las infraestruc- turas necesarias para una multitud de aplicaciones y servicios que demandan un servicio de posicionamiento confiable y preciso. La disponibilidad de posicionamiento se debe garantizar en todo momento, especialmente en los servicios cr´ıticos para la seguridad de las personas y los bienes. CuandoexaminamoslasamenazasdeladisponibilidaddelservicioqueofrecenlosGNSSs,es importantetenerencuentaquetodoslossistemaspresentesylossistemasfuturosyaplanificados hacenusodet´ecnicasdemultiplexaci´onpordivisi´ondec´odigo(CDMA).Lassen˜alestransmitidas por los sat´elites son recibidas con una relaci´on sen˜al-ruido (SNR) muy baja, medida antes de la correlaci´on(delordende-22dBparaunreceptorubicadoenlasuperficiedelatierra).Apesarde que la ganancia de procesado CDMA ofrece una proteccio´n inherente contra las interferencias de radiofrecuencia (RFI), esta protecci´on es limitada. Una interferencia con una relaci´on de potencia de interferencia a potencia de la sen˜al que excede la ganancia de procesado puede degradar el rendimiento de los receptores o incluso negar por completo el servicio GNSS. Este riesgo es especialmente importante en receptores convencionales equipados con un nivel m´ınimo ob´asicodeprotecci´onfrentelasRFIs.Comoconsecuencia,lasRFIs(yaseanintencionadasono intencionadas), se identifican como la causa m´as importante de la degradaci´on del rendimiento enGNSS.Elproblemaestacausandounapreocupaci´oncrecienteenlosu´ltimostiempos,yaque cada vez hay m´as servicios que dependen de los GNSSs. Sicentramoslaatenci´onenelreceptorGNSS,esconocidoquelaadquisici´ondelasen˜altiene lamenorsensibilidaddetodaslasoperacionesdelreceptor,y,enconsecuencia,seconvierteenel factor limitador en la presencia de sen˜ales interferentes. Un receptor de una sola antena puede hacer uso de la diversidad en tiempo y frecuencia para mitigar las interferencias, aunque el rendimiento de estas t´ecnicas se ve comprometido en escenarios con baja SNR o en presencia de interferencias de banda ancha. Por otro lado, los receptores basados en mu´ltiples antenas se pueden beneficiar del procesado espacial, y por lo tanto mitigar los efectos de las sen˜ales interferentes. La diversidad espacial se ha aplicado tradicionalmente a la operaci´on de tracking delasen˜alenreceptoresGNSS.Sinembargo,lascondicionesinicialesdeltrackingdependendel resultadode laadquisici´on dela sen˜al,y como hemosvisto antes,hayun nu´merode situaciones en las que el proceso de adquisici´on pueden fallar. En base a nuestro grado de conocimiento, la aplicaci´on de los arrays de antenas a la adquisici´on de la sen˜al GNSS no ha recibido mucha atenci´on, sorprendentemente. El objetivo de esta tesis doctoral es doble: por un lado, proponer nuevos algoritmos para la adquisici´on basados en arrays de antenas, usando como marco la teor´ıa de la detecci´on de sen˜al estad´ıstica,yporotrolado,demostrarlaviabilidaddesuimplementaci´onyejecuci´onentiempo real, as´ı como su medir su rendimiento en escenarios realistas. vii viii La tesis comienza con una breve introducci´on a los fundamentos de los receptores GNSS, proporcionandoalgunosdetallessobrelaestructuradelassen˜alesdenavegaci´onylaarquitectura del receptor aplicada a los sistemas GPS y Galileo. Continua con el an´alisis de la adquisici´on GNSS como un problema de detecci´on, aplicando la teor´ıa del detector Neyman-Pearson (NP) y el modelo de sen˜al de una u´nica antena. El marco te´orico del detector NP se utiliza aqu´ı para derivar tanto el detector ´optimo (conocido como detector clarividente) como la denominada Prueba Generalizada de la Raz´on de Verosimilitud (en ingl´es, Generalized Likelihood Ratio Test (GLRT)), que forma la base de pr´acticamente todos los algoritmos de adquisici´on del estado del arte actual. Yendo m´as lejos, proponemos un nuevo detector disen˜ado para adquirir simult´aneamente un conjunto de sat´elites, por lo tanto, obtiene una reducci´on del tiempo de adquisici´on y de los recursos computacionales necesarios en el proceso, respecto a las t´ecnicas convencionales. El efecto del ancho de banda del receptor tambi´en se ha tenido en cuenta en los an´alisis. A continuaci´on, el detector GLRT se extiende al modelo de sen˜al de array de antenas para obtener un detector nuevo que es capaz de mitigar interferencias no correladas temporalmente, inclusoutilizandoarraysnoestructuradosymoderadamentedescalibrados,convirti´endoseas´ıen una de las principales aportaciones de esta tesis. La clave del detector es asumir una matriz de covarianza de ruido arbitraria y desconocida en el modelo de sen˜al, que trata de captar el comportamientoestad´ısticodelasinterferenciasyotrassen˜alesnodeseadas,mientrasqueutiliza la dimensi´on espacial proporcionada por los arrays de antenas. Se han derivado las expresiones que modelan la probabilidades te´oricas de detecci´on y falsa alarma. El rendimiento del detector y su capacidad de rechazo a interferencias se han modelado y comparado con su l´ımite te´orico. El algoritmo propuesto tambi´en ha sido comparado con t´ecnicas de adquisici´on conven- cionales, ejecutadas utilizando la salida de conformadores de haz que utilizan algoritmos de filtrado de interferencias, como el algoritmo de minimizaci´on de la potencia. Adem´as, el detec- tor se ha analizado bajo condiciones realistas, representadas con la presencia de errores en la estimaci´on de covarianzas, errores residuales en la estimaci´on del Doppler y el retardo de sen˜al, y los efectos de la cuantificaci´on. Los resultados te´oricos se apoyan en simulaciones de Monte Carlo. Como otra contribuci´on principal de esta tesis, la segunda parte del trabajo trata sobre el disen˜oylaimplementaci´ondeunanuevaplataformaparareceptoresGNSSentiemporealbasa- dos en array de antenas que utiliza la tecnolog´ıa de matriz programable de puertas l´ogicas (en ingles Field Programmable Gate Array (FPGA)). La plataforma est´a destinada a ser utilizada como una herramienta de investigaci´on estrechamente acoplada con receptores GNSS definidos por software. Se ha disen˜ado, implementado y verificado la cadena completa de recepci´on, incluyendo el arraydeantenasyelfront-endmulti-canalparalassen˜alesGPSL1yGalileoE1.Eldocumento explica en detalle el procesado de sen˜al que se realiza, como por ejemplo, la implementaci´on del m´odulodeextracci´ondeestad´ısticasdelasen˜al.Loscompromisosdedisen˜oylascomplejidades derivadas han sido cuidadosamente analizadas y tenidas en cuenta. La plataforma ha sido utilizada como prueba de concepto para solucionar el problema pre- sentado de la vulnerabilidad del GNSS a las interferencias. Los algoritmos de adquisici´on intro- ducidos en esta tesis se implementaron y probaron en condiciones realistas. El rendimiento de losalgoritmossecompar´oconlast´ecnicasdeadquisici´onbasadasenunasolaantena.Sehanre- alizadopruebasenescenariosquecontieneninterferenciasdentrodelabandaGNSS,incluyendo interferencias de banda estrecha y banda ancha y sen˜ales de comunicaci´on. La plataforma fue disen˜ada para demostrar la viabilidad de la implementaci´on de nuevos algoritmos de adquisici´on basados en array de antenas, dejando el resto de las operaciones del receptor (principalmente, los m´odulos de tracking, decodificaci´on del mensaje de navegaci´on, los observables de c´odigo y fase, y la soluci´on b´asica de Posici´on, Velocidad y Tiempo (PVT)) a un receptor basado en el concepto de Radio Definida por Software (SDR), el cual se ejecuta en un ordenador personal. El receptor procesa en tiempo real las muestras de la sen˜al filtradas espacialmente, transmitidas usando el bus de datos Gigabit Ethernet. En la u´ltima parte de esta Tesis, cerramos ciclo disen˜ando e implementando completamente ix estereceptorbasadoensoftware.Elreceptorpropuestoest´adirigidoalasarquitecturasdemulti- constalaci´on GNSS y multi-frecuencia, persiguiendo los objetivos de eficiencia, modularidad, interoperabilidad y flexibilidad demandada por los usuarios que requieren caracter´ısticas no est´andar,talescomolaextracci´ondesen˜alesintermediasodedatosyintercambiodealgoritmos. En este contexto, se presenta un receptor de c´odigo abierto que puede trabajar en tiempo real, llamado GNSS-SDR, que contribuye con varias caracter´ısticas nuevas. Entre ellas destacan el uso de patrones de disen˜o de software y t´ecnicas de memoria compartida para administrar de manera eficiente el flujo de datos entre los bloques del receptor, el uso de la aceleraci´on por hardware para las operaciones vectoriales m´as costosas, como la eliminaci´on de la frecuencia Doppler y la correlaci´on de c´odigo, y la disponibilidad para compilar y ejecutar el receptor en mu´ltiples plataformas de software y arquitecturas de hardware. A fecha de la escritura de esta Tesis(abrilde2012),elreceptorobtieneunrendimientobasadoenlamedidadelara´ızcuadrada delerrorcuadr´aticomedioenladistanciabidimensional(eningl´es,2-dimensionalDistanceRoot Mean Square (DRMS) error) menor de 2 metros para un escenario GPS L1 C/A con 8 sat´elites visibles y una diluci´on de la precisi´on horizontal (en ingl´es, Horizontal Dilution Of Precision (HDOP)) de 1.2. x