On-Chip Thermal Monitoring: Design, Placement and Interconnection of Temperature Sensors

La temperatura es una preocupación que juega un papel protagonista en el diseño de circuitos integrados modernos. El importante aumento de las densidades de potencia que conllevan las últimas generaciones tecnológicas ha producido la aparición de gradientes térmicos y puntos calientes durante el funcionamiento normal de los chips. La temperatura tiene un impacto negativo en varios parámetros del circuito integrado como el retardo de las puertas, los gastos de disipación de calor, la fiabilidad, el consumo de energía, etc. Con el fin de luchar contra estos efectos nocivos, la técnicas de gestión dinámica de la temperatura (DTM) adaptan el comportamiento del chip en función en la información que proporciona un sistema de monitorización que mide en tiempo de ejecución la información térmica de la superficie del dado. El campo de la monitorización de la temperatura en el chip ha llamado la atención de la comunidad científica en los últimos años y es el objeto de estudio de esta tesis. Esta tesis aborda la temática de control de la temperatura en el chip desde diferentes perspectivas y niveles, ofreciendo soluciones a algunos de los temas más importantes. Los niveles físico y circuital se cubren con el diseño y la caracterización de dos nuevos sensores de temperatura especialmente diseñados para los propósitos de las técnicas DTM. El primer sensor está basado en un mecanismo que obtiene un pulso de anchura variable dependiente de la relación de las corrientes de fuga con la temperatura. De manera resumida, se carga un nodo del circuito y posteriormente se deja flotando de tal manera que se descarga a través de las corrientes de fugas de un transistor; el tiempo de descarga del nodo es la anchura del pulso. Dado que la anchura del pulso muestra una dependencia exponencial con la temperatura, la conversión a una palabra digital se realiza por medio de un contador logarítmico que realiza tanto la conversión tiempo a digital como la linealización de la salida. La estructura resultante de esta combinación de elementos se implementa en una tecnología de 0,35 _m. El sensor ocupa un área muy reducida, 10.250 nm2, y consume muy poca energía, 1.05-65.5nW a 5 muestras/s, estas cifras superaron todos los trabajos previos en el momento en que se publicó por primera vez y en el momento de la publicación de esta tesis, superan a todas las implementaciones anteriores fabricadas en el mismo nodo tecnológico. En cuanto a la precisión, el sensor ofrece una buena linealidad, incluso sin calibrar; se obtiene un error 3_ de 1,97oC, adecuado para tratar con las aplicaciones de DTM. Como se ha explicado, el sensor es completamente compatible con los procesos de fabricación CMOS, este hecho, junto con sus valores reducidos de área y consumo, lo hacen especialmente adecuado para la integración en un sistema de monitorización de DTM con un conjunto de monitores empotrados distribuidos a través del chip. Las crecientes incertidumbres de proceso asociadas a los últimos nodos tecnológicos comprometen las características de linealidad de nuestra primera propuesta de sensor. Con el objetivo de superar estos problemas, proponemos una nueva técnica para obtener la temperatura. La nueva técnica también está basada en las dependencias térmicas de las corrientes de fuga que se utilizan para descargar un nodo flotante. La novedad es que ahora la medida viene dada por el cociente de dos medidas diferentes, en una de las cuales se altera una característica del transistor de descarga |la tensión de puerta. Este cociente resulta ser muy robusto frente a variaciones de proceso y, además, la linealidad obtenida cumple ampliamente los requisitos impuestos por las políticas DTM |error 3_ de 1,17oC considerando variaciones del proceso y calibrando en dos puntos. La implementación de la parte sensora de esta nueva técnica implica varias consideraciones de diseño, tales como la generación de una referencia de tensión independiente de variaciones de proceso, que se analizan en profundidad en la tesis. Para la conversión tiempo-a-digital, se emplea la misma estructura de digitalización que en el primer sensor. Para la implementación física de la parte de digitalización, se ha construido una biblioteca de células estándar completamente nueva orientada a la reducción de área y consumo. El sensor resultante de la unión de todos los bloques se caracteriza por una energía por muestra ultra baja (48-640 pJ) y un área diminuta de 0,0016 mm2, esta cifra mejora todos los trabajos previos. Para probar esta afirmación, se realiza una comparación exhaustiva con más de 40 propuestas de sensores en la literatura científica. Subiendo el nivel de abstracción al sistema, la tercera contribución se centra en el modelado de un sistema de monitorización que consiste de un conjunto de sensores distribuidos por la superficie del chip. Todos los trabajos anteriores de la literatura tienen como objetivo maximizar la precisión del sistema con el mínimo número de monitores. Como novedad, en nuestra propuesta se introducen nuevos parámetros de calidad aparte del número de sensores, también se considera el consumo de energía, la frecuencia de muestreo, los costes de interconexión y la posibilidad de elegir diferentes tipos de monitores. El modelo se introduce en un algoritmo de recocido simulado que recibe la información térmica de un sistema, sus propiedades físicas, limitaciones de área, potencia e interconexión y una colección de tipos de monitor; el algoritmo proporciona el tipo seleccionado de monitor, el número de monitores, su posición y la velocidad de muestreo _optima. Para probar la validez del algoritmo, se presentan varios casos de estudio para el procesador Alpha 21364 considerando distintas restricciones. En comparación con otros trabajos previos en la literatura, el modelo que aquí se presenta es el más completo. Finalmente, la última contribución se dirige al nivel de red, partiendo de un conjunto de monitores de temperatura de posiciones conocidas, nos concentramos en resolver el problema de la conexión de los sensores de una forma eficiente en área y consumo. Nuestra primera propuesta en este campo es la introducción de un nuevo nivel en la jerarquía de interconexión, el nivel de trillado (o threshing en inglés), entre los monitores y los buses tradicionales de periféricos. En este nuevo nivel se aplica selectividad de datos para reducir la cantidad de información que se envía al controlador central. La idea detrás de este nuevo nivel es que en este tipo de redes la mayoría de los datos es inútil, porque desde el punto de vista del controlador sólo una pequeña cantidad de datos |normalmente sólo los valores extremos| es de interés. Para cubrir el nuevo nivel, proponemos una red de monitorización mono-conexión que se basa en un esquema de señalización en el dominio de tiempo. Este esquema reduce significativamente tanto la actividad de conmutación sobre la conexión como el consumo de energía de la red. Otra ventaja de este esquema es que los datos de los monitores llegan directamente ordenados al controlador. Si este tipo de señalización se aplica a sensores que realizan conversión tiempo-a-digital, se puede obtener compartición de recursos de digitalización tanto en tiempo como en espacio, lo que supone un importante ahorro de área y consumo. Finalmente, se presentan dos prototipos de sistemas de monitorización completos que de manera significativa superan la características de trabajos anteriores en términos de área y, especialmente, consumo de energía. Abstract Temperature is a first class design concern in modern integrated circuits. The important increase in power densities associated to recent technology evolutions has lead to the apparition of thermal gradients and hot spots during run time operation. Temperature impacts several circuit parameters such as speed, cooling budgets, reliability, power consumption, etc. In order to fight against these negative effects, dynamic thermal management (DTM) techniques adapt the behavior of the chip relying on the information of a monitoring system that provides run-time thermal information of the die surface. The field of on-chip temperature monitoring has drawn the attention of the scientific community in the recent years and is the object of study of this thesis. This thesis approaches the matter of on-chip temperature monitoring from different perspectives and levels, providing solutions to some of the most important issues. The physical and circuital levels are covered with the design and characterization of two novel temperature sensors specially tailored for DTM purposes. The first sensor is based upon a mechanism that obtains a pulse with a varying width based on the variations of the leakage currents on the temperature. In a nutshell, a circuit node is charged and subsequently left floating so that it discharges away through the subthreshold currents of a transistor; the time the node takes to discharge is the width of the pulse. Since the width of the pulse displays an exponential dependence on the temperature, the conversion into a digital word is realized by means of a logarithmic counter that performs both the timeto- digital conversion and the linearization of the output. The structure resulting from this combination of elements is implemented in a 0.35_m technology and is characterized by very reduced area, 10250 nm2, and power consumption, 1.05-65.5 nW at 5 samples/s, these figures outperformed all previous works by the time it was first published and still, by the time of the publication of this thesis, they outnumber all previous implementations in the same technology node. Concerning the accuracy, the sensor exhibits good linearity, even without calibration it displays a 3_ error of 1.97oC, appropriate to deal with DTM applications. As explained, the sensor is completely compatible with standard CMOS processes, this fact, along with its tiny area and power overhead, makes it specially suitable for the integration in a DTM monitoring system with a collection of on-chip monitors distributed across the chip. The exacerbated process fluctuations carried along with recent technology nodes jeop-ardize the linearity characteristics of the first sensor. In order to overcome these problems, a new temperature inferring technique is proposed. In this case, we also rely on the thermal dependencies of leakage currents that are used to discharge a floating node, but now, the result comes from the ratio of two different measures, in one of which we alter a characteristic of the discharging transistor |the gate voltage. This ratio proves to be very robust against process variations and displays a more than suficient linearity on the temperature |1.17oC 3_ error considering process variations and performing two-point calibration. The implementation of the sensing part based on this new technique implies several issues, such as the generation of process variations independent voltage reference, that are analyzed in depth in the thesis. In order to perform the time-to-digital conversion, we employ the same digitization structure the former sensor used. A completely new standard cell library targeting low area and power overhead is built from scratch to implement the digitization part. Putting all the pieces together, we achieve a complete sensor system that is characterized by ultra low energy per conversion of 48-640pJ and area of 0.0016mm2, this figure outperforms all previous works. To prove this statement, we perform a thorough comparison with over 40 works from the scientific literature. Moving up to the system level, the third contribution is centered on the modeling of a monitoring system consisting of set of thermal sensors distributed across the chip. All previous works from the literature target maximizing the accuracy of the system with the minimum number of monitors. In contrast, we introduce new metrics of quality apart form just the number of sensors; we consider the power consumption, the sampling frequency, the possibility to consider different types of monitors and the interconnection costs. The model is introduced in a simulated annealing algorithm that receives the thermal information of a system, its physical properties, area, power and interconnection constraints and a collection of monitor types; the algorithm yields the selected type of monitor, the number of monitors, their position and the optimum sampling rate. We test the algorithm with the Alpha 21364 processor under several constraint configurations to prove its validity. When compared to other previous works in the literature, the modeling presented here is the most complete. Finally, the last contribution targets the networking level, given an allocated set of temperature monitors, we focused on solving the problem of connecting them in an efficient way from the area and power perspectives. Our first proposal in this area is the introduction of a new interconnection hierarchy level, the threshing level, in between the monitors and the traditional peripheral buses that applies data selectivity to reduce the amount of information that is sent to the central controller. The idea behind this new level is that in this kind of networks most data are useless because from the controller viewpoint just a small amount of data |normally extreme values| is of interest. To cover the new interconnection level, we propose a single-wire monitoring network based on a time-domain signaling scheme that significantly reduces both the switching activity over the wire and the power consumption of the network. This scheme codes the information in the time domain and allows a straightforward obtention of an ordered list of values from the maximum to the minimum. If the scheme is applied to monitors that employ TDC, digitization resource sharing is achieved, producing an important saving in area and power consumption. Two prototypes of complete monitoring systems are presented, they significantly overcome previous works in terms of area and, specially, power consumption.

Transformation�based implementation and optimization of programs exploiting the basic Andorra model.

The characteristics of CC and CLP systems are in principle very dierent However a recent trend towards convergence in the implementation techniques for these systems can be observed While CLP and Prolog systems have been incorporating capabilities to deal with userdened suspension and coroutining CC compilers have been trying to coalesce negrained tasks into coarsergrained sequential threads This convergence of techniques opens up the possibility of having a general purpose kernel language and abstract machine to serve as a compilation target for a variety of userlevel languages We propose a transformation technique directed towards such an objective In particular we report on techniques to support the Andorra computational model essentially emulating the AndorraI system via program transformation into a sequential language with delay primitives The system is automatic comprising an optional program analyzer and a basic transformer to the kernel language It turns out that a simple parallel CLP or Prolog system with dynamic scheduling is sucient as a kernel language for this purpose The preliminary results are quite encouraging performance of the resulting system is comparable to the current AndorraI implementation.

Improved static analysis and verification of energy consumption and other resources via abstract interpretation

Resource analysis aims at inferring the cost of executing programs for any possible input, in terms of a given resource, such as the traditional execution steps, time ormemory, and, more recently energy consumption or user defined resources (e.g., number of bits sent over a socket, number of database accesses, number of calls to particular procedures, etc.). This is performed statically, i.e., without actually running the programs. Resource usage information is useful for a variety of optimization and verification applications, as well as for guiding software design. For example, programmers can use such information to choose different algorithmic solutions to a problem; program transformation systems can use cost information to choose between alternative transformations; parallelizing compilers can use cost estimates for granularity control, which tries to balance the overheads of task creation and manipulation against the benefits of parallelization. In this thesis we have significatively improved an existing prototype implementation for resource usage analysis based on abstract interpretation, addressing a number of relevant challenges and overcoming many limitations it presented. The goal of that prototype was to show the viability of casting the resource analysis as an abstract domain, and howit could overcome important limitations of the state-of-the-art resource usage analysis tools. For this purpose, it was implemented as an abstract domain in the abstract interpretation framework of the CiaoPP system, PLAI.We have improved both the design and implementation of the prototype, for eventually allowing an evolution of the tool to the industrial application level. The abstract operations of such tool heavily depend on the setting up and finding closed-form solutions of recurrence relations representing the resource usage behavior of program components and the whole program as well. While there exist many tools, such as Computer Algebra Systems (CAS) and libraries able to find closed-form solutions for some types of recurrences, none of them alone is able to handle all the types of recurrences arising during program analysis. In addition, there are some types of recurrences that cannot be solved by any existing tool. This clearly constitutes a bottleneck for this kind of resource usage analysis. Thus, one of the major challenges we have addressed in this thesis is the design and development of a novel modular framework for solving recurrence relations, able to combine and take advantage of the results of existing solvers. Additionally, we have developed and integrated into our novel solver a technique for finding upper-bound closed-form solutions of a special class of recurrence relations that arise during the analysis of programs with accumulating parameters. Finally, we have integrated the improved resource analysis into the CiaoPP general framework for resource usage verification, and specialized the framework for verifying energy consumption specifications of embedded imperative programs in a real application, showing the usefulness and practicality of the resulting tool.---ABSTRACT---El Análisis de recursos tiene como objetivo inferir el coste de la ejecución de programas para cualquier entrada posible, en términos de algún recurso determinado, como pasos de ejecución, tiempo o memoria, y, más recientemente, el consumo de energía o recursos definidos por el usuario (por ejemplo, número de bits enviados a través de un socket, el número de accesos a una base de datos, cantidad de llamadas a determinados procedimientos, etc.). Ello se realiza estáticamente, es decir, sin necesidad de ejecutar los programas. La información sobre el uso de recursos resulta muy útil para una gran variedad de aplicaciones de optimización y verificación de programas, así como para asistir en el diseño de los mismos. Por ejemplo, los programadores pueden utilizar dicha información para elegir diferentes soluciones algorítmicas a un problema; los sistemas de transformación de programas pueden utilizar la información de coste para elegir entre transformaciones alternativas; los compiladores paralelizantes pueden utilizar las estimaciones de coste para realizar control de granularidad, el cual trata de equilibrar el coste debido a la creación y gestión de tareas, con los beneficios de la paralelización. En esta tesis hemos mejorado de manera significativa la implementación de un prototipo existente para el análisis del uso de recursos basado en interpretación abstracta, abordando diversos desafíos relevantes y superando numerosas limitaciones que éste presentaba. El objetivo de dicho prototipo era mostrar la viabilidad de definir el análisis de recursos como un dominio abstracto, y cómo se podían superar las limitaciones de otras herramientas similares que constituyen el estado del arte. Para ello, se implementó como un dominio abstracto en el marco de interpretación abstracta presente en el sistema CiaoPP, PLAI. Hemos mejorado tanto el diseño como la implementación del mencionado prototipo para posibilitar su evolución hacia una herramienta utilizable en el ámbito industrial. Las operaciones abstractas de dicha herramienta dependen en gran medida de la generación, y posterior búsqueda de soluciones en forma cerrada, de relaciones recurrentes, las cuales modelizan el comportamiento, respecto al consumo de recursos, de los componentes del programa y del programa completo. Si bien existen actualmente muchas herramientas capaces de encontrar soluciones en forma cerrada para ciertos tipos de recurrencias, tales como Sistemas de Computación Algebraicos (CAS) y librerías de programación, ninguna de dichas herramientas es capaz de tratar, por sí sola, todos los tipos de recurrencias que surgen durante el análisis de recursos. Existen incluso recurrencias que no las puede resolver ninguna herramienta actual. Esto constituye claramente un cuello de botella para este tipo de análisis del uso de recursos. Por lo tanto, uno de los principales desafíos que hemos abordado en esta tesis es el diseño y desarrollo de un novedoso marco modular para la resolución de relaciones recurrentes, combinando y aprovechando los resultados de resolutores existentes. Además de ello, hemos desarrollado e integrado en nuestro nuevo resolutor una técnica para la obtención de cotas superiores en forma cerrada de una clase característica de relaciones recurrentes que surgen durante el análisis de programas lógicos con parámetros de acumulación. Finalmente, hemos integrado el nuevo análisis de recursos con el marco general para verificación de recursos de CiaoPP, y hemos instanciado dicho marco para la verificación de especificaciones sobre el consumo de energía de programas imperativas embarcados, mostrando la viabilidad y utilidad de la herramienta resultante en una aplicación real.

Contribution to the analysis and design of reflectarray antennas for reconfigurable beam applications at frequencies above 100 GHz using liquid crystal technology

El trabajo contenido en esta tesis doctoral está encuadrado en el desarrollo de antenas reconfigurables electrónicamente capaces de proporcionar prestaciones competitivas a las aplicaciones cada vez más comunes que operan a frecuencias superiores a 60 GHz. En concreto, esta tesis se centra en el estudio, diseño, e implementación de las antenas reflectarray, a las que se introduce la tecnología de cristal líquido como elemento característico con el que se consigue reconfigurabilidad de haz de forma electrónica. Desde un punto de vista muy general, se puede describir un cristal líquido como un material cuya permitividad eléctrica es variable y controlada por una excitación externa, que generalmente suele corresponderse con un campo eléctrico quasi-estático (AC). Las antenas reflectarray de cristal líquido se han escogido como objeto de estudio por varias razones. La primera de ellas tiene que ver con las ventajas que los reflectarrays, y en especial aquellos realizados en configuración planar, proporcionan con respecto a otras antenas de alta ganancia como los reflectores o los “phased-arrays”. En los reflectarrays, la alimentación a través de una fuente primaria común (característica de reflectores) y el elevado número de grados de libertad de las celdas que los componen (característica de arrays) hacen que estas antenas puedan proporcionar prestaciones eléctricas iguales o mejores que las anteriores, a un coste más reducido y con estructuras de antena más compactas. La segunda razón radica en la flexibilidad que ofrece el cristal líquido a ser confinado y polarizado en recintos de geometría variada, como consecuencia de su fluidez (propiedad de los líquidos). Por ello, la tecnología de cristal líquido permite que el propio elemento reconfigurable en las celdas de reflectarray se adapte a la configuración planar de manera que en sí mismo, el cristal líquido sea una o varias de las capas características de esta configuración. Esto simplifica de forma drástica la estructura y la fabricación de este tipo de antenas, incluso si se comparan con reflectarrays reconfigurables basados en otras tecnologías como diodos, MEMS, etc. Por tanto, su coste y desarrollo es muy reducido, lo que hace que se puedan fabricar reflectarrays reconfigurables eléctricamente grandes, a bajo coste, y en producción elevada. Un ejemplo claro de una estructura similar, y que ha tenido éxito comercial, son las pantallas de cristal líquido. La tercera razón reside en el hecho de que el cristal líquido es, hasta la fecha, de las pocas tecnologías capaces de ofrecer reconfigurabilidad del haz a frecuencias superiores a 60 GHz. De hecho, el cristal líquido permite reconfigurabilidad en un amplio margen de frecuencias, que va desde DC a frecuencias del espectro visible, incluyendo las microondas y los THz. Otras tecnologías, como los materiales ferroeléctricos, el grafeno o la tecnología CMOS “on chip” permiten también conmutar el haz en estas frecuencias. Sin embargo, la tecnología CMOS tiene un elevado coste y actualmente está limitada a frecuencias inferiores a 150 GHz, y aunque los materiales ferroeléctricos o el grafeno puedan conmutar a frecuencias más altas y en un rango más amplio, tienen serias dificultades que los hacen aún inmaduros. En el caso de los materiales ferroeléctricos, los elevados voltajes para conmutar el material los hacen poco atractivos, mientras que en el caso del grafeno, su modelado aún está en discusión, y todavía no se han arrojado resultados experimentales que validen su idoneidad. Estas tres razones hacen que los reflectarrays basados en cristal líquido sean atractivos para multitud de aplicaciones de haz reconfigurable a frecuencias superiores a 60 GHz. Aplicaciones como radar de escaneo de imágenes de alta resolución, espectroscopia molecular, radiómetros para observación atmosférica, o comunicaciones inalámbricas de alta frecuencia (WiGig) son algunas de ellas. La tesis está estructurada en tres partes. En la primera de ellas se describen las características más comunes de los cristales líquidos, centrándonos en detalle en aquellas propiedades ofrecidas por este material en fase nemática. En concreto, se estudiará la anisotropía dieléctrica (Ae) de los cristales líquidos uniaxiales, que son los que se emplean en esta tesis, definida como la diferencia entre la permitividad paralela (£//) y la perpendicular (e±): Ae = e,, - e±. También se estudiará la variación de este parámetro (Ae) con la frecuencia, y el modelado electromagnético macroscópico más general que, extraído a partir de aquella, permite describir el cristal líquido para cada tensión de polarización en celdas de geometría planar. Este modelo es de suma importancia para garantizar precisión en el desfasaje proporcionado por las diferentes celdas reconfigurables para reflectarrays que se describirán en la siguiente parte de la tesis. La segunda parte de la tesis se centra en el diseño de celdas reflectarray resonantes basadas en cristal líquido. La razón por la que se escogen estos tipos de celdas reside en el hecho de que son las únicas capaces de proporcionar rangos de fase elevados ante la reducida anisotropía dieléctrica que ofrecen los cristales líquidos. El objetivo de esta parte trata, por tanto, de obtener estructuras de celdas reflectarray que sean capaces de proporcionar buenas prestaciones eléctricas a nivel de antena, mejorando sustancialmente las prestaciones de las celdas reportadas en el estado del arte, así como de desarrollar una herramienta de diseño general para aquellas. Para ello, se estudian las prestaciones eléctricas de diferentes tipos de elementos resonantes de cristal líquido que van, desde el más sencillo, que ha limitado el estado de la técnica hasta el desarrollo de esta tesis y que está formado por un sólo resonador, a elementos que constan de varios resonadores (multi-resonantes) y que pueden ser monocapa o multicapa. En un primer paso, el procedimiento de diseño de estas estructuras hace uso de un modelo convencional de cristal líquido que ha venido siendo usado en el estado del arte para este tipo de celdas, y que considera el cristal líquido como un material homogéneo e isótropo cuya permitividad varía entre (e/7) y (e±). Sin embargo, en esta parte de la tesis se demuestra que dicho modelado no es suficiente para describir de forma genérica el comportamiento del cristal líquido en las celdas tipo reflectarray. En la tesis se proponen procedimientos más exactos para el análisis y diseño basados en un modelo más general que define el cristal líquido como un material anisótropo e inhomogeneo en tres dimensiones, y se ha implementado una técnica que permite optimizar celdas multi-resonantes de forma eficiente para conseguir elevadas prestaciones en cuanto a ancho de banda, rango de fase, pérdidas, o sensibilidad al ángulo de incidencia. Los errores cometidos en el uso del modelado convencional a nivel de celda (amplitud y fase) se han analizado para varias geometrías, usando medidas de varios prototipos de antena que usan un cristal líquido real a frecuencias superiores a 100 GHz. Las medidas se han realizado en entorno periódico mediante un banco cuasi-óptico, que ha sido diseñado especialmente para este fin. Uno de estos prototipos se ha optimizado a 100 GHz para conseguir un ancho de banda relativamente elevado (10%), pérdidas reducidas, un rango de fase mayor de 360º, baja sensibilidad al ángulo de incidencia, y baja influencia de la inhomogeneidad transversal del cristal líquido en la celda. Estas prestaciones a nivel de celda superan de forma clara aquellas conseguidas por otros elementos que se han reportado en la literatura, de manera que dicho prototipo se ha usado en la última parte de la tesis para realizar diversas antenas de barrido. Finalmente, en esta parte se presenta una estrategia de caracterización de la anisotropía macroscópica a partir de medidas de los elementos de reflectarray diseñados en banco cuasi-óptico, obteniendo resultados tanto en las frecuencias de interés en RF como en AC, y comparándolas con aquellas obtenidas mediante otros métodos. La tercera parte de la tesis consiste en el estudio, diseño, fabricación y medida de antenas reconfigurables basadas en cristal líquido en configuraciones complejas. En reflectarrays pasivos, el procedimiento de diseño de la antena se limita únicamente al ajuste en cada celda de la antena de las dimensiones de las metalizaciones que se emplean para el control de fase, mediante procesos de optimización bien conocidos. Sin embargo, en el caso de reflectarrays reconfigurables basados en cristal líquido, resulta necesario un paso adicional, que consiste en calcular de forma adecuada las tensiones de control en cada celda del reflectarray para configurar la fase requerida en cada una de ellas, así como diseñar la estructura y los circuitos de control que permitan direccionar a cada elemento su tensión correspondiente. La síntesis de tensiones es por tanto igual o más importante que el diseño de la geometría de las celdas, puesto que éstas son las que están directamente relacionadas con la fase. En el estado del arte, existen varias estrategias de síntesis de tensiones que se basan en la caracterización experimental de la curva de fase respecto al voltaje. Sin embargo, esta caracterización sólo puede hacerse a un solo ángulo de incidencia y para unas determinadas dimensiones de celda, lo que produce que las tensiones sintetizadas sean diferentes de las adecuadas, y en definitiva que se alcancen errores de fase mayores de 70º. De esta forma, hasta la fecha, las prestaciones a nivel de antena que se han conseguido son reducidas en cuanto a ancho de banda, rango de escaneo o nivel de lóbulos secundarios. En esta última parte de la tesis, se introduce una nueva estrategia de síntesis de tensiones que es capaz de predecir mediante simulaciones, y con alta precisión, las tensiones que deben introducirse en cada celda teniendo en cuenta su ángulo de incidencia, sus dimensiones, la frecuencia, así como la señal de polarización definida por su frecuencia y forma de onda AC. Esta estrategia se basa en modelar cada uno de los estados de permitividad del cristal líquido como un sustrato anisótropo con inhomogeneidad longitudinal (1D), o en ciertos casos, como un tensor equivalente homogéneo. La precisión de ambos modelos electromagnéticos también se discute. Con el objetivo de obtener una herramienta eficiente de cálculo de tensiones, también se ha escrito e implementado una herramienta de análisis basada en el Método de los Momentos en el Dominio Espectral (SD-MoM) para sustratos estratificados anisótropos, que se usa en cada iteración del procedimiento de síntesis para analizar cada una de las celdas de la antena. La síntesis de tensiones se ha diseñado además para reducir al máximo el efecto del rizado de amplitud en el diagrama de radiación, que es característico en los reflectarrays que están formados por celdas con pérdidas elevadas, lo que en sí, supone un avance adicional para la obtención de mejores prestaciones de antena. Para el cálculo de los diagramas de radiación empleados en el procedimiento de síntesis, se asume un análisis elemento a elemento considerando periodicidad local, y se propone el uso de un método capaz de modelar el campo incidente de forma que se elimine la limitación de la periodicidad local en la excitación. Una vez definida la estrategia adecuada de cálculo de las tensiones a aplicar al cristal líquido en cada celda, la estructura de direccionamiento de las mismas en la antena, y diseñados los circuitos de control, se diseñan, fabrican y miden dos prototipos diferentes de antena de barrido electrónico a 100 GHz usando las celdas anteriormente presentadas. El primero de estos prototipos es un reflectarray en configuración “single offset” con capacidad de escaneo en un plano (elevación o azimut). Aunque previamente se realizan diseños de antenas de barrido en 2D a varias frecuencias en el rango de milimétricas y sub-milimétricas, y se proponen ciertas estrategias de direccionamiento que permiten conseguir este objetivo, se desarrolla el prototipo con direccionamiento en una dimensión con el fin de reducir el número de controles y posibles errores de fabricación, y así también validar la herramienta de diseño. Para un tamaño medio de apertura (con un numero de filas y columnas entre 30 y 50 elementos, lo que significa un reflectarray con un número de elementos superior a 900), la configuración “single offset” proporciona rangos de escaneo elevados, y ganancias que pueden oscilar entre los 20 y 30 dBi. En concreto, el prototipo medido proporciona un haz de barrido en un rango angular de 55º, en el que el nivel de lóbulos secundarios (SLL) permanece mejor de -13 dB en un ancho de banda de un 8%. La ganancia máxima es de 19.4 dBi. Estas prestaciones superan de forma clara aquellas conseguidas por otros autores. El segundo prototipo se corresponde con una antena de doble reflector que usa el reflectarray de cristal líquido como sub-reflector para escanear el haz en un plano (elevación o azimut). El objetivo básico de esta geometría es obtener mayores ganancias que en el reflectarray “single offset” con una estructura más compacta, aunque a expensas de reducir el rango de barrido. En concreto, se obtiene una ganancia máxima de 35 dBi, y un rango de barrido de 12º. Los procedimientos de síntesis de tensiones y de diseño de las estructuras de las celdas forman, en su conjunto, una herramienta completa de diseño precisa y eficiente de antenas reflectarray reconfigurables basados en cristales líquidos. Dicha herramienta se ha validado mediante el diseño, la fabricación y la medida de los prototipos anteriormente citados a 100 GHz, que consiguen algo nunca alcanzado anteriormente en la investigación de este tipo de antenas: unas prestaciones competitivas y una predicción excelente de los resultados. El procedimiento es general, y por tanto se puede usar a cualquier frecuencia en la que el cristal líquido ofrezca anisotropía dieléctrica, incluidos los THz. Los prototipos desarrollados en esta tesis doctoral suponen también unas de las primeras antenas de barrido real a frecuencias superiores a 100 GHz. En concreto, la antena de doble reflector para escaneo de haz es la primera antena reconfigurable electrónicamente a frecuencias superiores a 60 GHz que superan los 25 dBi de ganancia, siendo a su vez la primera antena de doble reflector que contiene un reflectarray reconfigurable como sub-reflector. Finalmente, se proponen ciertas mejoras que aún deben se deben realizar para hacer que estas antenas puedan ser un producto completamente desarrollado y competitivo en el mercado. ABSTRACT The work presented in this thesis is focused on the development of electronically reconfigurable antennas that are able to provide competitive electrical performance to the increasingly common applications operating at frequencies above 60 GHz. Specifically, this thesis presents the study, design, and implementation of reflectarray antennas, which incorporate liquid crystal (LC) materials to scan or reconfigure the beam electronically. From a general point of view, a liquid crystal can be defined as a material whose dielectric permittivity is variable and can be controlled with an external excitation, which usually corresponds with a quasi-static electric field (AC). By changing the dielectric permittivity at each cell that makes up the reflectarray, the phase shift on the aperture is controlled, so that a prescribed radiation pattern can be configured. Liquid Crystal-based reflectarrays have been chosen for several reasons. The first has to do with the advantages provided by the reflectarray antenna with respect to other high gain antennas, such as reflectors or phased arrays. The RF feeding in reflectarrays is achieved by using a common primary source (as in reflectors). This arrangement and the large number of degrees of freedom provided by the cells that make up the reflectarray (as in arrays), allow these antennas to provide a similar or even better electrical performance than other low profile antennas (reflectors and arrays), but assuming a more reduced cost and compactness. The second reason is the flexibility of the liquid crystal to be confined in an arbitrary geometry due to its fluidity (property of liquids). Therefore, the liquid crystal is able to adapt to a planar geometry so that it is one or more of the typical layers of this configuration. This simplifies drastically both the structure and manufacture of this type of antenna, even when compared with reconfigurable reflectarrays based on other technologies, such as diodes MEMS, etc. Therefore, the cost of developing this type of antenna is very small, which means that electrically large reconfigurable reflectarrays could be manufactured assuming low cost and greater productions. A paradigmatic example of a similar structure is the liquid crystal panel, which has already been commercialized successfully. The third reason lies in the fact that, at present, the liquid crystal is one of the few technologies capable of providing switching capabilities at frequencies above 60 GHz. In fact, the liquid crystal allows its permittivity to be switched in a wide range of frequencies, which are from DC to the visible spectrum, including microwaves and THz. Other technologies, such as ferroelectric materials, graphene or CMOS "on chip" technology also allow the beam to be switched at these frequencies. However, CMOS technology is expensive and is currently limited to frequencies below 150 GHz, and although ferroelectric materials or graphene can switch at higher frequencies and in a wider range, they have serious difficulties that make them immature. Ferroelectric materials involve the use of very high voltages to switch the material, making them unattractive, whereas the electromagnetic modelling of the graphene is still under discussion, so that the experimental results of devices based on this latter technology have not been reported yet. These three reasons make LC-based reflectarrays attractive for many applications that involve the use of electronically reconfigurable beams at frequencies beyond 60 GHz. Applications such as high resolution imaging radars, molecular spectroscopy, radiometers for atmospheric observation, or high frequency wireless communications (WiGig) are just some of them. This thesis is divided into three parts. In the first part, the most common properties of the liquid crystal materials are described, especially those exhibited in the nematic phase. The study is focused on the dielectric anisotropy (Ac) of uniaxial liquid crystals, which is defined as the difference between the parallel (e/7) and perpendicular (e±) permittivities: Ae = e,, - e±. This parameter allows the permittivity of a LC confined in an arbitrary volume at a certain biasing voltage to be described by solving a variational problem that involves both the electrostatic and elastic energies. Thus, the frequency dependence of (Ae) is also described and characterised. Note that an appropriate LC modelling is quite important to ensure enough accuracy in the phase shift provided by each cell that makes up the reflectarray, and therefore to achieve a good electrical performance at the antenna level. The second part of the thesis is focused on the design of resonant reflectarray cells based on liquid crystal. The reason why resonant cells have been chosen lies in the fact that they are able to provide enough phase range using the values of the dielectric anisotropy of the liquid crystals, which are typically small. Thus, the aim of this part is to investigate several reflectarray cell architectures capable of providing good electrical performance at the antenna level, which significantly improve the electrical performance of the cells reported in the literature. Similarly, another of the objectives is to develop a general tool to design these cells. To fulfill these objectives, the electrical yields of different types of resonant reflectarray elements are investigated, beginning from the simplest, which is made up of a single resonator and limits the state of the art. To overcome the electrical limitations of the single resonant cell, several elements consisting of multiple resonators are considered, which can be single-layer or multilayer. In a first step, the design procedure of these structures makes use of a conventional electromagnetic model which has been used in the literature, which considers that the liquid crystal behaves as homogeneous and isotropic materials whose permittivity varies between (e/7) y (e±). However, in this part of the thesis it is shown that the conventional modelling is not enough to describe the physical behaviour of the liquid crystal in reflectarray cells accurately. Therefore, a more accurate analysis and design procedure based on a more general model is proposed and developed, which defines the liquid crystal as an anisotropic three-dimensional inhomogeneous material. The design procedure is able to optimize multi-resonant cells efficiently to achieve good electrical performance in terms of bandwidth, phase range, losses, or sensitivity to the angle of incidence. The errors made when the conventional modelling (amplitude and phase) is considered have been also analysed for various cell geometries, by using measured results from several antenna prototypes made up of real liquid crystals at frequencies above 100 GHz. The measurements have been performed in a periodic environment using a quasi-optical bench, which has been designed especially for this purpose. One of these prototypes has been optimized to achieve a relatively large bandwidth (10%) at 100 GHz, low losses, a phase range of more than 360º, a low sensitivity to angle of incidence, and a low influence of the transversal inhomogeneity of the liquid crystal in the cell. The electrical yields of this prototype at the cell level improve those achieved by other elements reported in the literature, so that this prototype has been used in the last part of the thesis to perform several complete antennas for beam scanning applications. Finally, in this second part of the thesis, a novel strategy to characterise the macroscopic anisotropy using reflectarray cells is presented. The results in both RF and AC frequencies are compared with those obtained by other methods. The third part of the thesis consists on the study, design, manufacture and testing of LCbased reflectarray antennas in complex configurations. Note that the design procedure of a passive reflectarray antenna just consists on finding out the dimensions of the metallisations of each cell (which are used for phase control), using well-known optimization processes. However, in the case of reconfigurable reflectarrays based on liquid crystals, an additional step must be taken into account, which consists of accurately calculating the control voltages to be applied to each cell to configure the required phase-shift distribution on the surface of the antenna. Similarly, the structure to address the voltages at each cell and the control circuitry must be also considered. Therefore, the voltage synthesis is even more important than the design of the cell geometries (dimensions), since the voltages are directly related to the phase-shift. Several voltage synthesis procedures have been proposed in the state of the art, which are based on the experimental characterization of the phase/voltage curve. However, this characterization can be only carried out at a single angle of incidence and at certain cell dimensions, so that the synthesized voltages are different from those needed, thus giving rise to phase errors of more than 70°. Thus, the electrical yields of the LCreflectarrays reported in the literature are limited in terms of bandwidth, scanning range or side lobes level. In this last part of the thesis, a new voltage synthesis procedure has been defined and developed, which allows the required voltage to be calculated at each cell using simulations that take into account the particular dimensions of the cells, their angles of incidence, the frequency, and the AC biasing signal (frequency and waveform). The strategy is based on the modelling of each one of the permittivity states of the liquid crystal as an anisotropic substrate with longitudinal inhomogeneity (1D), or in certain cases, as an equivalent homogeneous tensor. The accuracy of both electromagnetic models is also discussed. The phase errors made by using the proposed voltage synthesis are better than 7º. In order to obtain an efficient tool to analyse and design the reflectarray, an electromagnetic analysis tool based on the Method of Moments in the spectral domain (SD-MoM) has also written and developed for anisotropic stratified media, which is used at each iteration of the voltage synthesis procedure. The voltage synthesis is also designed to minimize the effect of amplitude ripple on the radiation pattern, which is typical of reflectarrays made up of cells exhibiting high losses and represents a further advance in achieving a better antenna performance. To calculate the radiation patterns used in the synthesis procedure, an element-by-element analysis is assumed, which considers the local periodicity approach. Under this consideration, the use of a novel method is proposed, which avoids the limitation that the local periodicity imposes on the excitation. Once the appropriate strategy to calculate the voltages to be applied at each cell is developed, and once it is designed and manufactured both the structure to address the voltages to the antenna and the control circuits, two complete LC-based reflectarray antennas that operate at 100 GHz have been designed, manufactured and tested using the previously presented cells. The first prototype consists of a single offset reflectarray with beam scanning capabilities on one plane (elevation and azimuth). Although several LC-reflectarray antennas that provide 2-D scanning capabilities are also designed, and certain strategies to achieve the 2-D addressing of the voltage are proposed, the manufactured prototype addresses the voltages in one dimension in order to reduce the number of controls and manufacturing errors, and thereby validating the design tool. For an average aperture size (with a number of rows and columns of between 30 and 50 elements, which means a reflectarray with more than 900 cells), the single offset configuration provides an antenna gain of between 20 and 30 dBi and a large scanning range. The prototype tested at 100 GHz exhibits an electronically scanned beam in an angular range of 55º and 8% of bandwidth, in which the side lobe level (SLL) remains better than -13 dB. The maximum gain is 19.4 dBi. The electrical performance of the antenna is clearly an improvement on those achieved by other authors in the state of the art. The second prototype corresponds to a dual reflector antenna with a liquid crystal-based reflectarray used as a sub-reflector for beam scanning in one plane (azimuth or elevation). The main objective is to obtain a higher gain than that provided by the single offset configuration, but using a more compact architecture. In this case, a maximum gain of 35 dBi is achieved, although at the expense of reducing the scanning range to 12°, which is inherent in this type of structure. As a general statement, the voltage synthesis and the design procedure of the cells, jointly make up a complete, accurate and efficient design tool of reconfigurable reflectarray antennas based on liquid crystals. The tool has been validated by testing the previously mentioned prototypes at 100 GHz, which achieve something never reached before for this type of antenna: a competitive electrical performance, and an excellent prediction of the results. The design procedure is general and therefore can be used at any frequency for which the liquid crystal exhibits dielectric anisotropy. The two prototypes designed, manufactured and tested in this thesis are also some of the first antennas that currently operate at frequencies above 100 GHz. In fact, the dual reflector antenna is the first electronically scanned dual reflector antenna at frequencies above 60 GHz (the operation frequency is 100 GHz) with a gain greater than 25 dBi, being in turn the first dual-reflector antenna with a real reconfigurable sub-reflectarray. Finally, some improvements that should be still investigated to make these antennas commercially competitive are proposed.

A real case of a cognitive multiplayer game: design and development of the iOS client in Swift and its cloud architecture

as tecnologías emergentes como el cloud computing y los dispositivos móviles están creando una oportunidad sin precedentes para mejorar el sistema educativo, permitiendo tanto a los educadores personalizar y mejorar la experiencia de aprendizaje, como facilitar a los estudiantes que adquieran conocimientos sin importar dónde estén. Por otra parte, a través de técnicas de gamificacion será posible promover y motivar a los estudiantes a que aprendan materias arduas haciendo que la experiencia sea más motivadora. Los juegos móviles pueden ser el camino correcto para dar soporte a esta experiencia de aprendizaje mejorada. Este proyecto integra el diseño y desarrollo de una arquitectura en la nube altamente escalable y con alto rendimiento, así como el propio cliente de iOS, para dar soporte a una nueva version de Temporis, un juego móvil multijugador orientado a reordenar eventos históricos en una línea temporal (e.j. historia, arte, deportes, entretenimiento y literatura). Temporis actualmente está disponible en Google Play. Esta memoria describe el desarrollo de la nueva versión de Temporis (Temporis v.2.0) proporcionando detalles acerca de la mejora y adaptación basados en el Temporis original. En particular se describe el nuevo backend hecho en Go sobre Google App Engine creado para soportar miles de usuarios, asó como otras características por ejemplo como conseguir enviar noticaciones push desde la propia plataforma. Por último, el cliente de iOS en Temporis v.2.0 se ha desarrollado utilizando las últimas y más relevantes tecnologías, prestando especial atención a Swift (el lenguaje de programación nuevo de Apple, que es seguro y rápido), el Paradigma Funcional Reactivo (que ayuda a construir aplicaciones altamente interactivas además de a minimizar errores) y la arquitectura VIPER (una arquitectura que sigue los principios SOLID, se centra en la separación de asuntos y favorece la reutilización de código en otras plataformas). ABSTRACT Emerging technologies such as cloud computing and mobile devices are creating an unprecedented opportunity for enhancing the educational system, letting both educators customize and improve the learning experience, and students acquire knowledge regardless of where they are. Moreover, through gamification techniques it would be possible to encourage and motivate students to learn arduous subjects by making the experience more motivating. Mobile games can be a perfect vehicle to support this enhanced learning experience. This project integrates the design and development of a highly scalable and performant cloud architecture, as well as the iOS client that uses it, in order to provide support to a new version of Temporis, a mobile multiplayer game focused on ordering time-based (e.g. history, art, sports, entertainment and literature) in a timeline that currently is available on Google Play. This work describes the development of the new Temporis version (Temporis v.2.0), providing details about improvements and details on the adaptation of the original Temporis. In particular, the new Google App Engine backend is described, which was created to support thousand of users developed in Go language are provided, in addition to other features like how to achieve push notications in this platform. Finally, the mobile iOS client developed using the latest and more relevant technologies is explained paying special attention to Swift (Apple's new programming language, that is safe and fast), the Functional Reactive Paradigm (that helps building highly interactive apps while minimizing bugs) and the VIPER architecture (a SOLID architecture that enforces separation of concerns and makes it easy to reuse code for other platforms).

Applications of Formal Languages to Management of Manned and Unmanned Aircraft

En el futuro, la gestión del tráfico aéreo (ATM, del inglés air traffic management) requerirá un cambio de paradigma, de la gestión principalmente táctica de hoy, a las denominadas operaciones basadas en trayectoria. Un incremento en el nivel de automatización liberará al personal de ATM —controladores, tripulación, etc.— de muchas de las tareas que realizan hoy. Las personas seguirán siendo el elemento central en la gestión del tráfico aéreo del futuro, pero lo serán mediante la gestión y toma de decisiones. Se espera que estas dos mejoras traigan un incremento en la eficiencia de la gestión del tráfico aéreo que permita hacer frente al incremento previsto en la demanda de transporte aéreo. Para aplicar el concepto de operaciones basadas en trayectoria, el usuario del espacio aéreo (la aerolínea, piloto, u operador) y el proveedor del servicio de navegación aérea deben negociar las trayectorias mediante un proceso de toma de decisiones colaborativo. En esta negociación, es necesaria una forma adecuada de compartir dichas trayectorias. Compartir la trayectoria completa requeriría un gran ancho de banda, y la trayectoria compartida podría invalidarse si cambiase la predicción meteorológica. En su lugar, podría compartirse una descripción de la trayectoria independiente de las condiciones meteorológicas, de manera que la trayectoria real se pudiese calcular a partir de dicha descripción. Esta descripción de la trayectoria debería ser fácil de procesar usando un programa de ordenador —ya que parte del proceso de toma de decisiones estará automatizado—, pero también fácil de entender para un operador humano —que será el que supervise el proceso y tome las decisiones oportunas—. Esta tesis presenta una serie de lenguajes formales que pueden usarse para este propósito. Estos lenguajes proporcionan los medios para describir trayectorias de aviones durante todas las fases de vuelo, desde la maniobra de push-back (remolcado hasta la calle de rodaje), hasta la llegada a la terminal del aeropuerto de destino. También permiten describir trayectorias tanto de aeronaves tripuladas como no tripuladas, incluyendo aviones de ala fija y cuadricópteros. Algunos de estos lenguajes están estrechamente relacionados entre sí, y organizados en una jerarquía. Uno de los lenguajes fundamentales de esta jerarquía, llamado aircraft intent description language (AIDL), ya había sido desarrollado con anterioridad a esta tesis. Este lenguaje fue derivado de las ecuaciones del movimiento de los aviones de ala fija, y puede utilizarse para describir sin ambigüedad trayectorias de este tipo de aeronaves. Una variante de este lenguaje, denominada quadrotor AIDL (QR-AIDL), ha sido desarrollada en esta tesis para permitir describir trayectorias de cuadricópteros con el mismo nivel de detalle. Seguidamente, otro lenguaje, denominado intent composite description language (ICDL), se apoya en los dos lenguajes anteriores, ofreciendo más flexibilidad para describir algunas partes de la trayectoria y dejar otras sin especificar. El ICDL se usa para proporcionar descripciones genéricas de maniobras comunes, que después se particularizan y combinan para formar descripciones complejas de un vuelo. Otro lenguaje puede construirse a partir del ICDL, denominado flight intent description language (FIDL). El FIDL especifica requisitos de alto nivel sobre las trayectorias —incluyendo restricciones y objetivos—, pero puede utilizar características del ICDL para proporcionar niveles de detalle arbitrarios en las distintas partes de un vuelo. Tanto el ICDL como el FIDL han sido desarrollados en colaboración con Boeing Research & Technology Europe (BR&TE). También se ha desarrollado un lenguaje para definir misiones en las que interactúan varias aeronaves, el mission intent description language (MIDL). Este lenguaje se basa en el FIDL y mantiene todo su poder expresivo, a la vez que proporciona nuevas semánticas para describir tareas, restricciones y objetivos relacionados con la misión. En ATM, los movimientos de un avión en la superficie de aeropuerto también tienen que ser monitorizados y gestionados. Otro lenguaje formal ha sido diseñado con este propósito, llamado surface movement description language (SMDL). Este lenguaje no pertenece a la jerarquía de lenguajes descrita en el párrafo anterior, y se basa en las clearances (autorizaciones del controlador) utilizadas durante las operaciones en superficie de aeropuerto. También proporciona medios para expresar incertidumbre y posibilidad de cambios en las distintas partes de la trayectoria. Finalmente, esta tesis explora las aplicaciones de estos lenguajes a la predicción de trayectorias y a la planificación de misiones. El concepto de trajectory language processing engine (TLPE) se usa en ambas aplicaciones. Un TLPE es una función de ATM cuya principal entrada y salida se expresan en cualquiera de los lenguajes incluidos en la jerarquía descrita en esta tesis. El proceso de predicción de trayectorias puede definirse como una combinación de TLPEs, cada uno de los cuales realiza una pequeña sub-tarea. Se le ha dado especial importancia a uno de estos TLPEs, que se encarga de generar el perfil horizontal, vertical y de configuración de la trayectoria. En particular, esta tesis presenta un método novedoso para la generación del perfil vertical. El proceso de planificar una misión también se puede ver como un TLPE donde la entrada se expresa en MIDL y la salida consiste en cierto número de trayectorias —una por cada aeronave disponible— descritas utilizando FIDL. Se ha formulado este problema utilizando programación entera mixta. Además, dado que encontrar caminos óptimos entre distintos puntos es un problema fundamental en la planificación de misiones, también se propone un algoritmo de búsqueda de caminos. Este algoritmo permite calcular rápidamente caminos cuasi-óptimos que esquivan todos los obstáculos en un entorno urbano. Los diferentes lenguajes formales definidos en esta tesis pueden utilizarse como una especificación estándar para la difusión de información entre distintos actores de la gestión del tráfico aéreo. En conjunto, estos lenguajes permiten describir trayectorias con el nivel de detalle necesario en cada aplicación, y se pueden utilizar para aumentar el nivel de automatización explotando esta información utilizando sistemas de soporte a la toma de decisiones. La aplicación de estos lenguajes a algunas funciones básicas de estos sistemas, como la predicción de trayectorias, han sido analizadas. ABSTRACT Future air traffic management (ATM) will require a paradigm shift from today’s mainly tactical ATM to trajectory-based operations (TBOs). An increase in the level of automation will also relieve humans —air traffic control officers (ATCOs), flight crew, etc.— from many of the tasks they perform today. Humans will still be central in this future ATM, as decision-makers and managers. These two improvements (TBOs and increased automation) are expected to provide the increase in ATM performance that will allow coping with the expected increase in air transport demand. Under TBOs, trajectories are negotiated between the airspace user (an airline, pilot, or operator) and the air navigation service provider (ANSP) using a collaborative decision making (CDM) process. A suitable method for sharing aircraft trajectories is necessary for this negotiation. Sharing a whole trajectory would require a high amount of bandwidth, and the shared trajectory might become invalid if the weather forecast changed. Instead, a description of the trajectory, decoupled from the weather conditions, could be shared, so that the actual trajectory could be computed from this trajectory description. This trajectory description should be easy to process using a computing program —as some of the CDM processes will be automated— but also easy to understand for a human operator —who will be supervising the process and making decisions. This thesis presents a series of formal languages that can be used for this purpose. These languages provide the means to describe aircraft trajectories during all phases of flight, from push back to arrival at the gate. They can also describe trajectories of both manned and unmanned aircraft, including fixedwing and some rotary-wing aircraft (quadrotors). Some of these languages are tightly interrelated and organized in a language hierarchy. One of the key languages in this hierarchy, the aircraft intent description language (AIDL), had already been developed prior to this thesis. This language was derived from the equations of motion of fixed-wing aircraft, and can provide an unambiguous description of fixed-wing aircraft trajectories. A variant of this language, the quadrotor AIDL (QR-AIDL), is developed in this thesis to allow describing a quadrotor aircraft trajectory with the same level of detail. Then, the intent composite description language (ICDL) is built on top of these two languages, providing more flexibility to describe some parts of the trajectory while leaving others unspecified. The ICDL is used to provide generic descriptions of common aircraft manoeuvres, which can be particularized and combined to form complex descriptions of flight. Another language is built on top of the ICDL, the flight intent description language (FIDL). The FIDL specifies high-level requirements on trajectories —including constraints and objectives—, but can use features of the ICDL to provide arbitrary levels of detail in different parts of the flight. The ICDL and FIDL have been developed in collaboration with Boeing Research & Technology Europe (BR&TE). Also, the mission intent description language (MIDL) has been developed to allow describing missions involving multiple aircraft. This language is based on the FIDL and keeps all its expressive power, while it also provides new semantics for describing mission tasks, mission objectives, and constraints involving several aircraft. In ATM, the movement of aircraft while on the airport surface also has to be monitored and managed. Another formal language has been designed for this purpose, denoted surface movement description language (SMDL). This language does not belong to the language hierarchy described above, and it is based on the clearances used in airport surface operations. Means to express uncertainty and mutability of different parts of the trajectory are also provided. Finally, the applications of these languages to trajectory prediction and mission planning are explored in this thesis. The concept of trajectory language processing engine (TLPE) is used in these two applications. A TLPE is an ATM function whose main input and output are expressed in any of the languages in the hierarchy described in this thesis. A modular trajectory predictor is defined as a combination of multiple TLPEs, each of them performing a small subtask. Special attention is given to the TLPE that builds the horizontal, vertical, and configuration profiles of the trajectory. In particular, a novel method for the generation of the vertical profile is presented. The process of planning a mission can also be seen as a TLPE, where the main input is expressed in the MIDL and the output consists of a number of trajectory descriptions —one for each aircraft available in the mission— expressed in the FIDL. A mixed integer linear programming (MILP) formulation for the problem of assigning mission tasks to the available aircraft is provided. In addition, since finding optimal paths between locations is a key problem to mission planning, a novel path finding algorithm is presented. This algorithm can compute near-shortest paths avoiding all obstacles in an urban environment in very short times. The several formal languages described in this thesis can serve as a standard specification to share trajectory information among different actors in ATM. In combination, these languages can describe trajectories with the necessary level of detail for any application, and can be used to increase automation by exploiting this information using decision support tools (DSTs). Their applications to some basic functions of DSTs, such as trajectory prediction, have been analized.