Un modelo de encaminamiento en las redes móviles ad hoc con QoS

En la última década ha aumentado en gran medida el interés por las redes móviles Ad Hoc. La naturaleza dinámica y sin infraestructura de estas redes, exige un nuevo conjunto de algoritmos y estrategias para proporcionar un servicio de comunicación fiable extremo a extremo. En el contexto de las redes móviles Ad Hoc, el encaminamiento surge como una de las áreas más interesantes para transmitir información desde una fuente hasta un destino, con la calidad de servicio de extremo a extremo. Debido a las restricciones inherentes a las redes móviles, los modelos de encaminamiento tradicionales sobre los que se fundamentan las redes fijas, no son aplicables a las redes móviles Ad Hoc. Como resultado, el encaminamiento en redes móviles Ad Hoc ha gozado de una gran atención durante los últimos años. Esto ha llevado al acrecentamiento de numerosos protocolos de encaminamiento, tratando de cubrir con cada uno de ellos las necesidades de los diferentes tipos de escenarios. En consecuencia, se hace imprescindible estudiar el comportamiento de estos protocolos bajo configuraciones de red variadas, con el fin de ofrecer un mejor encaminamiento respecto a los existentes. El presente trabajo de investigación muestra precisamente una solución de encaminamiento en las redes móviles Ad Hoc. Dicha solución se basa en el mejoramiento de un algoritmo de agrupamiento y la creación de un modelo de encaminamiento; es decir, un modelo que involucra la optimización de un protocolo de enrutamiento apoyado de un mecanismo de agrupación. El algoritmo mejorado, denominado GMWCA (Group Management Weighted Clustering Algorithm) y basado en el WCA (Weighted Clustering Algorithm), permite calcular el mejor número y tamaño de grupos en la red. Con esta mejora se evitan constantes reagrupaciones y que los jefes de clústeres tengan más tiempo de vida intra-clúster y por ende una estabilidad en la comunicación inter-clúster. En la tesis se detallan las ventajas de nuestro algoritmo en relación a otras propuestas bajo WCA. El protocolo de enrutamiento Ad Hoc propuesto, denominado QoS Group Cluster Based Routing Protocol (QoSG-CBRP), utiliza como estrategia el empleo de clúster y jerarquías apoyada en el algoritmo de agrupamiento. Cada clúster tiene un jefe de clúster (JC), quien administra la información de enrutamiento y la envía al destino cuando esta fuera de su área de cobertura. Para evitar que haya constantes reagrupamientos y llamados al algoritmo de agrupamiento se consideró agregarle un jefe de cluster de soporte (JCS), el que asume las funciones del JC, siempre y cuando este haya roto el enlace con los otros nodos comunes del clúster por razones de alejamiento o por desgaste de batería. Matemáticamente y a nivel de algoritmo se han demostrado las mejoras del modelo propuesto, el cual ha involucrado el mejoramiento a nivel de algoritmo de clustering y del protocolo de enrutamiento. El protocolo QoSG-CBRP, se ha implementado en la herramienta de simulación Network Simulator 2 (NS2), con la finalidad de ser comparado con el protocolo de enrutamiento jerárquico Cluster Based Routing Protocol (CBRP) y con un protocolo de enrutamiento Ad Hoc reactivo denominado Ad Hoc On Demand Distance Vector Routing (AODV). Estos protocolos fueron elegidos por ser los que mejor comportamiento presentaron dentro de sus categorías. Además de ofrecer un panorama general de los actuales protocolos de encaminamiento en redes Ad Hoc, este proyecto presenta un procedimiento integral para el análisis de capacidades de la propuesta del nuevo protocolo con respecto a otros, sobre redes que tienen un alto número de nodos. Estas prestaciones se miden en base al concepto de eficiencia de encaminamiento bajo parámetros de calidad de servicio (QoS), permitiendo establecer el camino más corto posible entre un nodo origen y un nodo destino. Con ese fin se han realizado simulaciones con diversos escenarios para responder a los objetivos de la tesis. La conclusiones derivadas del análisis de los resultados permiten evaluar cualitativamente las capacidades que presenta el protocolo dentro del modelo propuesto, al mismo tiempo que avizora un atractivo panorama en líneas futuras de investigación. ABSTRACT In the past decade, the interest in mobile Ad Hoc networks has greatly increased. The dynamic nature of these networks without infrastructure requires a new set of algorithms and strategies to provide a reliable end-to-end communication service. In the context of mobile Ad Hoc networks, routing emerges as one of the most interesting areas for transmitting information from a source to a destination, with the quality of service from end-to-end. Due to the constraints of mobile networks, traditional routing models that are based on fixed networks are not applicable to Ad Hoc mobile networks. As a result, the routing in mobile Ad Hoc networks has experienced great attention in recent years. This has led to the enhancement of many routing protocols, trying to cover with each one of them, the needs of different types of scenarios. Consequently, it is essential to study the behavior of these protocols under various network configurations, in order to provide a better routing scheme. Precisely, the present research shows a routing solution in mobile Ad Hoc networks. This solution is based on the improvement of a clustering algorithm, and the creation of a routing model, ie a model that involves optimizing a routing protocol with the support of a grouping mechanism. The improved algorithm called GMWCA (Group Management Weighted Clustering Algorithm) and based on the WCA (Weighted Clustering Algorithm), allows to calculate the best number and size of groups in the network. With this enhancement, constant regroupings are prevented and cluster heads are living longer intra-cluster lives and therefore stability in inter-cluster communication. The thesis details the advantages of our algorithm in relation to other proposals under WCA. The Ad Hoc routing protocol proposed, called QoS Group Cluster Based Routing Protocol (QoSG-CBRP), uses a cluster-employment strategy and hierarchies supported by the clustering algorithm. Each cluster has a cluster head (JC), who manages the routing information and sends it to the destination when is out of your coverage area. To avoid constant rearrangements and clustering algorithm calls, adding a support cluster head (JCS) was considered. The JCS assumes the role of the JC as long as JC has broken the link with the other nodes in the cluster for common restraining reasons or battery wear. Mathematically and at an algorithm level, the improvements of the proposed model have been showed, this has involved the improvement level clustering algorithm and the routing protocol. QoSG-CBRP protocol has been implemented in the simulation tool Network Simulator 2 (NS2), in order to be compared with the hierarchical routing protocol Cluster Based Routing Protocol (CBRP) and with the reactive routing protocol Ad Hoc On Demand Distance Vector Routing (AODV). These protocols were chosen because they showed the best individual performance in their categories. In addition to providing an overview of existing routing protocols in Ad Hoc networks, this project presents a comprehensive procedure for capacity analysis of the proposed new protocol with respect to others on networks that have a high number of nodes. These benefits are measured based on the concept of routing efficiency under the quality of service (QoS) parameters, thus allowing for the shortest possible path between a source node and a destination node. To meet the objectives of the thesis, simulations have been performed with different scenarios. The conclusions derived from the analysis of the results to assess qualitatively the protocol capabilities presented in the proposed model, while an attractive scenario for future research appears.

Contribución a los modelos de gestión de las redes móviles ad hoc

La capacidad de comunicación de los seres humanos ha crecido gracias a la evolución de dispositivos móviles cada vez más pequeños, manejables, potentes, de mayor autonomía y más asequibles. Esta tendencia muestra que en un futuro próximo cercano cada persona llevaría consigo por lo menos un dispositivo de altas prestaciones. Estos dispositivos tienen incorporados algunas formas de comunicación: red de telefonía, redes inalámbricas, bluetooth, entre otras. Lo que les permite también ser empleados para la configuración de redes móviles Ad Hoc. Las redes móviles Ad Hoc, son redes temporales y autoconfigurables, no necesitan un punto de acceso para que los nodos intercambien información entre sí. Cada nodo realiza las tareas de encaminador cuando sea requerido. Los nodos se pueden mover, cambiando de ubicación a discreción. La autonomía de estos dispositivos depende de las estrategias de como sus recursos son utilizados. De tal forma que los protocolos, algoritmos o modelos deben ser diseñados de forma eficiente para no impactar el rendimiento del dispositivo, siempre buscando un equilibrio entre sobrecarga y usabilidad. Es importante definir una gestión adecuada de estas redes especialmente cuando estén siendo utilizados en escenarios críticos como los de emergencias, desastres naturales, conflictos bélicos. La presente tesis doctoral muestra una solución eficiente para la gestión de redes móviles Ad Hoc. La solución contempla dos componentes principales: la definición de un modelo de gestión para redes móviles de alta disponibilidad y la creación de un protocolo de enrutamiento jerárquico asociado al modelo. El modelo de gestión propuesto, denominado High Availability Management Ad Hoc Network (HAMAN), es definido en una estructura de cuatro niveles, acceso, distribución, inteligencia e infraestructura. Además se describen los componentes de cada nivel: tipos de nodos, protocolos y funcionamiento. Se estudian también las interfaces de comunicación entre cada componente y la relación de estas con los niveles definidos. Como parte del modelo se diseña el protocolo de enrutamiento Ad Hoc, denominado Backup Cluster Head Protocol (BCHP), que utiliza como estrategia de encaminamiento el empleo de cluster y jerarquías. Cada cluster tiene un Jefe de Cluster que concentra la información de enrutamiento y de gestión y la envía al destino cuando esta fuera de su área de cobertura. Para mejorar la disponibilidad de la red el protocolo utiliza un Jefe de Cluster de Respaldo el que asume las funciones del nodo principal del cluster cuando este tiene un problema. El modelo HAMAN es validado a través de un proceso la simulación del protocolo BCHP. El protocolo BCHP se implementa en la herramienta Network Simulator 2 (NS2) para ser simulado, comparado y contrastado con el protocolo de enrutamiento jerárquico Cluster Based Routing Protocol (CBRP) y con el protocolo de enrutamiento Ad Hoc reactivo denominado Ad Hoc On Demand Distance Vector Routing (AODV). Abstract The communication skills of humans has grown thanks to the evolution of mobile devices become smaller, manageable, powerful, more autonomy and more affordable. This trend shows that in the near future each person will carry at least one high-performance device. These high-performance devices have some forms of communication incorporated: telephony network, wireless networks, bluetooth, among others. What can also be used for configuring mobile Ad Hoc networks. Ad Hoc mobile networks, are temporary and self-configuring networks, do not need an access point for exchange information between their nodes. Each node performs the router tasks as required. The nodes can move, change location at will. The autonomy of these devices depends on the strategies of how its resources are used. So that the protocols, algorithms or models should be designed to efficiently without impacting device performance seeking a balance between overhead and usability. It is important to define appropriate management of these networks, especially when being used in critical scenarios such as emergencies, natural disasters, wars. The present research shows an efficient solution for managing mobile ad hoc networks. The solution comprises two main components: the definition of a management model for highly available mobile networks and the creation of a hierarchical routing protocol associated with the model. The proposed management model, called High Availability Management Ad Hoc Network (HAMAN) is defined in a four-level structure: access, distribution, intelligence and infrastructure. The components of each level: types of nodes, protocols, structure of a node are shown and detailed. It also explores the communication interfaces between each component and the relationship of these with the levels defined. The Ad Hoc routing protocol proposed, called Backup Cluster Head Protocol( BCHP), use of cluster and hierarchies like strategies. Each cluster has a cluster head which concentrates the routing information and management and sent to the destination when out of cluster coverage area. To improve the availability of the network protocol uses a Backup Cluster Head who assumes the functions of the node of the cluster when it has a problem. The HAMAN model is validated accross the simulation of their BCHP routing protocol. BCHP protocol has been implemented in the simulation tool Network Simulator 2 (NS2) to be simulated, compared and contrasted with a hierarchical routing protocol Cluster Based Routing Protocol (CBRP) and a routing protocol called Reactive Ad Hoc On Demand Distance Vector Routing (AODV).

MIRACLE’s Ad-Hoc and Geographical IR Approaches for CLEF 2006

This paper presents the 2006 Miracle team’s approaches to the Ad-Hoc and Geographical Information Retrieval tasks. A first set of runs was obtained using a set of basic components. Then, by putting together special combinations of these runs, an extended set was obtained. With respect to previous campaigns some improvements have been introduced in our system: an entity recognition prototype is integrated in our tokenization scheme, and the performance of our indexing and retrieval engine has been improved. For GeoCLEF, we tested retrieving using geo-entity and textual references separately, and then combining them with different approaches.

MIRACLE at Ad-Hoc CLEF 2005: Merging and Combining Without Using a Single Approach

This paper presents the 2005 Miracle’s team approach to the Ad-Hoc Information Retrieval tasks. The goal for the experiments this year was twofold: to continue testing the effect of combination approaches on information retrieval tasks, and improving our basic processing and indexing tools, adapting them to new languages with strange encoding schemes. The starting point was a set of basic components: stemming, transforming, filtering, proper nouns extraction, paragraph extraction, and pseudo-relevance feedback. Some of these basic components were used in different combinations and order of application for document indexing and for query processing. Second-order combinations were also tested, by averaging or selective combination of the documents retrieved by different approaches for a particular query. In the multilingual track, we concentrated our work on the merging process of the results of monolingual runs to get the overall multilingual result, relying on available translations. In both cross-lingual tracks, we have used available translation resources, and in some cases we have used a combination approach.

Analysis of QoS Parameter in AODV a DSR in Mobile Ad Hoc Networks

Providing QoS in the context of Ad Hoc networks includes a very wide field of application from the perspective of every level of the architecture in the network. Saying It in another way, It is possible to speak about QoS when a network is capable of guaranteeing a trustworthy communication in both extremes, between any couple of the network nodes by means of an efficient Management and administration of the resources that allows a suitable differentiation of services in agreement with the characteristics and demands of every single application.The principal objective of this article is the analysis of the quality parameters of service that protocols of routering reagents such as AODV and DSR give in the Ad Hoc mobile Networks; all of this is supported by the simulator ns-2. Here were going to analyze the behavior of some other parameters like effective channel, loss of packages and latency in the protocols of routering. Were going to show you which protocol presents better characteristics of Quality of Service (QoS) in the MANET networks.

Analysis of ad hoc routing protocols for emergency and rescue scenarios.

A mobile ad hoc network MANET is a collection of wireless mobile nodes that can dynamically configure a network without a fixed infrastructure or centralized administration. This makes it ideal for emergency and rescue scenarios where information sharing is essential and should occur as soon as possible. This article discusses which of the routing strategies for mobile ad hoc networks: proactive, reactive and hierarchical, have a better performance in such scenarios. Using a real urban area being set for the emergency and rescue scenario, we calculate the density of nodes and the mobility model needed for validation. The NS2 simulator has been used in our study. We also show that the hierarchical routing strategies are beffer suited for this type of scenarios.

An energy efficient adaptive HELLO algorithm for mobile ad hoc networks

HELLO protocol or neighborhood discovery is essential in wireless ad hoc networks. It makes the rules for nodes to claim their existence/aliveness. In the presence of node mobility, no fix optimal HELLO frequency and optimal transmission range exist to maintain accurate neighborhood tables while reducing the energy consumption and bandwidth occupation. Thus a Turnover based Frequency and transmission Power Adaptation algorithm (TFPA) is presented in this paper. The method enables nodes in mobile networks to dynamically adjust both their HELLO frequency and transmission range depending on the relative speed. In TFPA, each node monitors its neighborhood table to count new neighbors and calculate the turnover ratio. The relationship between relative speed and turnover ratio is formulated and optimal transmission range is derived according to battery consumption model to minimize the overall transmission energy. By taking advantage of the theoretical analysis, the HELLO frequency is adapted dynamically in conjunction with the transmission range to maintain accurate neighborhood table and to allow important energy savings. The algorithm is simulated and compared to other state-of-the-art algorithms. The experimental results demonstrate that the TFPA algorithm obtains high neighborhood accuracy with low HELLO frequency (at least 11% average reduction) and with the lowest energy consumption. Besides, the TFPA algorithm does not require any additional GPS-like device to estimate the relative speed for each node, hence the hardware cost is reduced.

Assessment of troughput performance under NS2 in Mobile Ad Hoc Networks (MANETs)

Providing QoS in the context of Ad Hoc networks includes a very wide field of application from the perspective of every level of the architecture in the network.In order for simulation studies to be useful, it is very important that the simulation results match as closely as possible with the test bed results. In this Paper, we study the throughput performance (parameter QoS) in Mobile Ad Hoc Networks (MANETs) and compares emulated test bed results with simulation results from NS2 (Network Simulator). The performance of the Mobile Ad Hoc Networks is very sensitive to the number of users and the offered load. When the number of users/offered load is high then the collisions increase resulting in larger wastage of the medium and lowering overall throughput. The aim of this research is to compare the throughput of Mobile Ad Hoc Networks using three different scenarios: 97, 100 and 120 users (nodes) using simulator NS2. By analyzing the graphs in MANETs, it is concluded When the number of users o nodes is increased beyond the certain limit, throughput decreases.

Behavior of Ad Hoc routing protocols, analyzed for emergency and rescue scenarios, on a real urban area

A mobile Ad Hoc network (MANET) is a collection of wireless mobile nodes that can dynamically configure a network without a fixed infrastructure or central administration. This makes it ideal for emergency and rescue scenarios, where sharing information is essential and should occur as soon as possible. This article discusses which of the routing strategies for mobile MANETs: proactive, reactive or hierarchical, has a better performance in such scenarios. By selecting a real urban area for the emergency and rescue scenario, we calculated the density of nodes and the mobility model needed for the validation study of AODV, DSDV and CBRP in the routing model. The NS2 simulator has been used for our study. We also show that the hierarchical routing strategies are better suited for this type of scenarios.

Strengthening communication skills in an innovative context of engineering project management learning

This document presents an innovative, formal educational initiative that is aimed at enhancing the development of engineering students’ specific competences when studying Project Management (PM) subject. The framework of the experience combines (1) theoretical concepts, (2) the development of a real-case project carried out by multidisciplinary groups of three different universities, (3) the use of software web 2.0 tools and (4) group and individual assignments of students that play different roles (project managers and team members). Under this scenario, the study focuses on monitoring the communication competence in the ever growing PM virtual environment. Factors such as corporal language, technical means, stage, and PM specific vocabulary among others have been considered in order to assess the students’ performance on this issue. As a main contribution, the paper introduces an ad-hoc rubric that, based on previous investigations, has been adapted and tested for the first time to this new and specific context. Additionally, the research conducted has provided some interesting findings that suggest further actions to improve and better define future rubrics, oriented to communication or even other competences. As specific PM subject concerns, it has been detected that students playing the role of Project Managers strengthen their competences more than those ones that play the role of Team Members. It has also been detected that students have more difficulty assimilating concepts related to risk and quality management. However those concepts related with scope, time or cost areas of knowledge have been better assimilated by the students.

Monitoring the communication competence in an innovative context of project management learning

This document presents an innovative, formal educational initiative that is aimed at enhancing the development of engineering students' specific competences. The subject of project management is the common theoretical and practical framework that articulates an experience that is carried out by multidisciplinary groups. Full utilization of Web 2.0 platforms and Project Based Learning constitutes the applied methodology. More specifically, this study focuses on monitoring communication competence when working in virtual environments, providing an ad-hoc rubric as a final result.

Desarrollo de aplicaciones de comunicaciones inalámbricas en sistemas de monitorización estructural desarrollados en aeronáutica.

Los Sistemas de SHM o de monitorización de la integridad estructural surgen ante la necesidad de mejorar los métodos de evaluación y de test no destructivos convencionales. De esta manera, se puede tener controlado todo tipo de estructuras en las cuales su correcto estado o funcionamiento suponga un factor crítico. Un Sistema SHM permite analizar una estructura concreta capturando de manera periódica el estado de la integridad estructural, que en este proyecto se ha aplicado a estructuras aeronáuticas. P.A.M.E.L.A. (Phase Array Monitoring for Enhanced Life Assessment) es la denominación utilizada para definir una serie de equipos electrónicos para Sistemas SHM desarrollados por AERNOVA y los Grupos de Diseño Electrónico de las universidades UPV/EHU y UPM. Los dispositivos P.A.M.E.L.A. originalmente no cuentan con tecnología Wi-Fi, por lo que incorporan un módulo hardware independiente que se encarga de las comunicaciones inalámbricas, a los que se les denomina Nodos. Estos Nodos poseen un Sistema Operativo propio y todo lo necesario para administrar y organizar la red Mallada Wi-Fi. De esta manera se obtiene una red mallada inalámbrica compuesta por Nodos que interconectan los Sistemas SHM y que se encargan de transmitir los datos a los equipos que procesan los resultados adquiridos por P.A.M.E.L.A. Los Nodos son dispositivos empotrados que llevan instalados un firmware basado en una distribución de Linux para Nodos (o Routers), llamado Openwrt. Que para disponer de una red mallada necesitan de un protocolo orientado a este tipo de redes. Entre las opciones de protocolo más destacadas se puede mencionar: DSDV (Destination Sequenced Distance Vector), OLSR (Optimized Link State Routing), B.A.T.M.A.N-Adv (Better Approach To Mobile Adhoc Networking Advance), BMX (una versión de B.A.T.M.A.N-Adv), AODV (Ad hoc On-Demand Distance Vector) y el DSR (Dynamic Source Routing). Además de la existencia de protocolos orientados a las redes malladas, también hay organizaciones que se dedican a desarrollar firmware que los utilizan, como es el caso del firmware llamado Nightwing que utiliza BMX, Freifunk que utiliza OLSR o Potato Mesh que utiliza B.A.T.M.A.N-Adv. La ventaja de estos tres firmwares mencionados es que las agrupaciones que las desarrollan proporcionan las imágenes precompiladas del sistema,listas para cargarlas en distintos modelos de Nodos. En este proyecto se han instalado las imágenes en los Nodos y se han probado los protocolos BMX, OLSR y B.A.T.M.A.N.-Adv. Concluyendo que la red gestionada por B.A.T.M.A.N.-Adv era la que mejor rendimiento obtenía en cuanto a estabilidad y ancho de banda. Después de haber definido el protocolo a usar, se procedió a desarrollar una distribución basada en Openwrt, que utilice B.A.T.M.A.N.-Adv para crear la red mallada, pero que se ajuste mejor a las necesidades del proyecto, ya que Nightwing, Freifunk y Potato Mesh no lo hacían. Además se implementan aplicaciones en lenguaje ANSI C y en LabVIEW para interactuar con los Nodos y los Sistemas SHM. También se procede a hacer alguna modificación en el Hardware de P.A.M.E.L.A. y del Nodo para obtener una mejor integración entre los dos dispositivos. Y por ultimo, se prueba la transferencia de datos de los Nodos en distintos escenarios. ABSTRACT. Structural Health Monitoring (SHM) systems arise from the need of improving assessment methods and conventional nondestructive tests. Critical structures can be monitored using SHM. A SHM system analyzes periodically a specific structure capturing the state of structural integrity. The aim of this project is to contribute in the implementation of Mesh network for SHM system in aircraft structures. P.A.M.E.L.A. (Phase Array Monitoring for Enhanced Life Assessment) is the name for electronic equipment developed by AERNOVA, the Electronic Design Groups of university UPV/EHU and the Instrumentation and Applied Acoustics research group from UPM. P.A.M.E.L.A. devices were not originally equipped with Wi-Fi interface. In this project a separate hardware module that handles wireless communications (nodes) has been added. The nodes include an operating system for manage the Wi-Fi Mesh Network and they form the wireless mesh network to link SHM systems with monitoring equipment. Nodes are embedded devices with an installed firmware based on special Linux distribution used in routers or nodes, called OpenWRT. They need a Mesh Protocol to stablish the network. The most common protocols options are: DSDV (Destination Sequenced Distance Vector), OLSR (Optimized Link State Routing), BATMAN-Adv (Better Approach To Mobile Ad-hoc Networking Advance), BMX (a version of BATMAN-Adv) AODV (Ad hoc on-Demand Distance Vector) and DSR (Dynamic Source Routing). In addition, there are organizations that are dedicated to develope firmware using these Mesh Protocols, for instance: Nightwing uses BMX, Freifunk use OLSR and Potato Mesh uses BATMAN-Adv. The advantage of these three firmwares is that these groups develop pre-compiled images of the system ready to be loaded in several models of Nodes. In this project the images were installed in the nodes. In this way, BMX, OLSR and BATMAN-Adv have been tested. We conclude that the protocol BATMAN-Adv has better performance in terms of stability and bandwidth. After choosing the protocol, the objective was to develop a distribution based on OpenWRT, using BATMAN-Adv to create the mesh network. This distribution is fitted to the requirements of this project. Besides, in this project it has been developed applications in C language and LabVIEW to interact with the Nodes and the SHM systems. The project also address some modifications to the PAMELA hardware and the Node, for better integration between both elements. Finally, data transfer tests among the different nodes in different scenarios has been carried out.

VISIONS Vehicular communication Improvement : solution based on IMS Operational Nodes and Services

Digital services and communications in vehicular scenarios provide the essential assets to improve road transport in several ways like reducing accidents, improving traffic efficiency and optimizing the transport of goods and people. Vehicular communications typically rely on VANET (Vehicular Ad hoc Networks). In these networks vehicles communicate with each other without the need of infrastructure. VANET are mainly oriented to disseminate information to the vehicles in certain geographic area for time critical services like safety warnings but present very challenging requirements that have not been successfully fulfilled nowadays. Some of these challenges are; channel saturation due to simultaneous radio access of many vehicles, routing protocols in topologies that vary rapidly, minimum quality of service assurance and security mechanisms to efficiently detect and neutralize malicious attacks. Vehicular services can be classified in four important groups: Safety, Efficiency, Sustainability and Infotainment. The benefits of these services for the transport sector are clear but many technological and business challenges need to be faced before a real mass market deployment. Service delivery platforms are not prepared for fulfilling the needs of this complex environment with restrictive requirements due to the criticism of some services To overcome this situation, we propose a solution called VISIONS “Vehicular communication Improvement: Solution based on IMS Operational Nodes and Services”. VISIONS leverages on IMS subsystem and NGN enablers, and follows the CALM reference Architecture standardized by ISO. It also avoids the use of Road Side Units (RSUs), reducing complexity and high costs in terms of deployment and maintenance. We demonstrate the benefits in the following areas: 1. VANET networks efficiency. VISIONS provide a mechanism for the vehicles to access valuable information from IMS and its capabilities through a cellular channel. This efficiency improvement will occur in two relevant areas: a. Routing mechanisms. These protocols are responsible of carrying information from a vehicle to another (or a group of vehicles) using multihop mechanisms. We do not propose a new algorithm but the use of VANET topology information provided through our solution to enrich the performance of these protocols. b. Security. Many aspects of security (privacy, key, authentication, access control, revocation mechanisms, etc) are not resolved in vehicular communications. Our solution efficiently disseminates revocation information to neutralize malicious nodes in the VANET. 2. Service delivery platform. It is based on extended enablers, reference architectures, standard protocols and open APIs. By following this approach, we reduce costs and resources for service development, deployment and maintenance. To quantify these benefits in VANET networks, we provide an analytical model of the system and simulate our solution in realistic scenarios. The simulations results demonstrate how VISIONS improves the performance of relevant routing protocols and is more efficient neutralizing security attacks than the widely proposed solutions based on RSUs. Finally, we design an innovative Social Network service based in our platform, explaining how VISIONS facilitate the deployment and usage of complex capabilities. RESUMEN Los servicios digitales y comunicaciones en entornos vehiculares proporcionan herramientas esenciales para mejorar el transporte por carretera; reduciendo el número de accidentes, mejorando la eficiencia del tráfico y optimizando el transporte de mercancías y personas. Las comunicaciones vehiculares generalmente están basadas en redes VANET (Vehicular Ad hoc Networks). En dichas redes, los vehículos se comunican entre sí sin necesidad de infraestructura. Las redes VANET están principalmente orientadas a difundir información (por ejemplo advertencias de seguridad) a los vehículos en determinadas zonas geográficas, pero presentan unos requisitos muy exigentes que no se han resuelto con éxito hasta la fecha. Algunos de estos retos son; saturación del canal de acceso de radio debido al acceso simultáneo de múltiples vehículos, la eficiencia de protocolos de encaminamiento en topologías que varían rápidamente, la calidad de servicio (QoS) y los mecanismos de seguridad para detectar y neutralizar los ataques maliciosos de manera eficiente. Los servicios vehiculares pueden clasificarse en cuatro grupos: Seguridad, Eficiencia del tráfico, Sostenibilidad, e Infotainment (información y entretenimiento). Los beneficios de estos servicios para el sector son claros, pero es necesario resolver muchos desafíos tecnológicos y de negocio antes de una implementación real. Las actuales plataformas de despliegue de servicios no están preparadas para satisfacer las necesidades de este complejo entorno con requisitos muy restrictivos debido a la criticidad de algunas aplicaciones. Con el objetivo de mejorar esta situación, proponemos una solución llamada VISIONS “Vehicular communication Improvement: Solution based on IMS Operational Nodes and Services”. VISIONS se basa en el subsistema IMS, las capacidades NGN y es compatible con la arquitectura de referencia CALM estandarizado por ISO para sistemas de transporte. También evita el uso de elementos en las carreteras, conocidos como Road Side Units (RSU), reduciendo la complejidad y los altos costes de despliegue y mantenimiento. A lo largo de la tesis, demostramos los beneficios en las siguientes áreas: 1. Eficiencia en redes VANET. VISIONS proporciona un mecanismo para que los vehículos accedan a información valiosa proporcionada por IMS y sus capacidades a través de un canal de celular. Dicho mecanismo contribuye a la mejora de dos áreas importantes: a. Mecanismos de encaminamiento. Estos protocolos son responsables de llevar información de un vehículo a otro (o a un grupo de vehículos) utilizando múltiples saltos. No proponemos un nuevo algoritmo de encaminamiento, sino el uso de información topológica de la red VANET a través de nuestra solución para enriquecer el funcionamiento de los protocolos más relevantes. b. Seguridad. Muchos aspectos de la seguridad (privacidad, gestión de claves, autenticación, control de acceso, mecanismos de revocación, etc) no están resueltos en las comunicaciones vehiculares. Nuestra solución difunde de manera eficiente la información de revocación para neutralizar los nodos maliciosos en la red. 2. Plataforma de despliegue de servicios. Está basada en capacidades NGN, arquitecturas de referencia, protocolos estándar y APIs abiertos. Siguiendo este enfoque, reducimos costes y optimizamos procesos para el desarrollo, despliegue y mantenimiento de servicios vehiculares. Para cuantificar estos beneficios en las redes VANET, ofrecemos un modelo de analítico del sistema y simulamos nuestra solución en escenarios realistas. Los resultados de las simulaciones muestran cómo VISIONS mejora el rendimiento de los protocolos de encaminamiento relevantes y neutraliza los ataques a la seguridad de forma más eficientes que las soluciones basadas en RSU. Por último, diseñamos un innovador servicio de red social basado en nuestra plataforma, explicando cómo VISIONS facilita el despliegue y el uso de las capacidades NGN.

Algoritmos de agrupación para flujos de datos en entornos centralizados y distribuidos

Los avances en el hardware permiten disponer de grandes volúmenes de datos, surgiendo aplicaciones que deben suministrar información en tiempo cuasi-real, la monitorización de pacientes, ej., el seguimiento sanitario de las conducciones de agua, etc. Las necesidades de estas aplicaciones hacen emerger el modelo de flujo de datos (data streaming) frente al modelo almacenar-para-despuésprocesar (store-then-process). Mientras que en el modelo store-then-process, los datos son almacenados para ser posteriormente consultados; en los sistemas de streaming, los datos son procesados a su llegada al sistema, produciendo respuestas continuas sin llegar a almacenarse. Esta nueva visión impone desafíos para el procesamiento de datos al vuelo: 1) las respuestas deben producirse de manera continua cada vez que nuevos datos llegan al sistema; 2) los datos son accedidos solo una vez y, generalmente, no son almacenados en su totalidad; y 3) el tiempo de procesamiento por dato para producir una respuesta debe ser bajo. Aunque existen dos modelos para el cómputo de respuestas continuas, el modelo evolutivo y el de ventana deslizante; éste segundo se ajusta mejor en ciertas aplicaciones al considerar únicamente los datos recibidos más recientemente, en lugar de todo el histórico de datos. En los últimos años, la minería de datos en streaming se ha centrado en el modelo evolutivo. Mientras que, en el modelo de ventana deslizante, el trabajo presentado es más reducido ya que estos algoritmos no sólo deben de ser incrementales si no que deben borrar la información que caduca por el deslizamiento de la ventana manteniendo los anteriores tres desafíos. Una de las tareas fundamentales en minería de datos es la búsqueda de agrupaciones donde, dado un conjunto de datos, el objetivo es encontrar grupos representativos, de manera que se tenga una descripción sintética del conjunto. Estas agrupaciones son fundamentales en aplicaciones como la detección de intrusos en la red o la segmentación de clientes en el marketing y la publicidad. Debido a las cantidades masivas de datos que deben procesarse en este tipo de aplicaciones (millones de eventos por segundo), las soluciones centralizadas puede ser incapaz de hacer frente a las restricciones de tiempo de procesamiento, por lo que deben recurrir a descartar datos durante los picos de carga. Para evitar esta perdida de datos, se impone el procesamiento distribuido de streams, en concreto, los algoritmos de agrupamiento deben ser adaptados para este tipo de entornos, en los que los datos están distribuidos. En streaming, la investigación no solo se centra en el diseño para tareas generales, como la agrupación, sino también en la búsqueda de nuevos enfoques que se adapten mejor a escenarios particulares. Como ejemplo, un mecanismo de agrupación ad-hoc resulta ser más adecuado para la defensa contra la denegación de servicio distribuida (Distributed Denial of Services, DDoS) que el problema tradicional de k-medias. En esta tesis se pretende contribuir en el problema agrupamiento en streaming tanto en entornos centralizados y distribuidos. Hemos diseñado un algoritmo centralizado de clustering mostrando las capacidades para descubrir agrupaciones de alta calidad en bajo tiempo frente a otras soluciones del estado del arte, en una amplia evaluación. Además, se ha trabajado sobre una estructura que reduce notablemente el espacio de memoria necesario, controlando, en todo momento, el error de los cómputos. Nuestro trabajo también proporciona dos protocolos de distribución del cómputo de agrupaciones. Se han analizado dos características fundamentales: el impacto sobre la calidad del clustering al realizar el cómputo distribuido y las condiciones necesarias para la reducción del tiempo de procesamiento frente a la solución centralizada. Finalmente, hemos desarrollado un entorno para la detección de ataques DDoS basado en agrupaciones. En este último caso, se ha caracterizado el tipo de ataques detectados y se ha desarrollado una evaluación sobre la eficiencia y eficacia de la mitigación del impacto del ataque. ABSTRACT Advances in hardware allow to collect huge volumes of data emerging applications that must provide information in near-real time, e.g., patient monitoring, health monitoring of water pipes, etc. The data streaming model emerges to comply with these applications overcoming the traditional store-then-process model. With the store-then-process model, data is stored before being consulted; while, in streaming, data are processed on the fly producing continuous responses. The challenges of streaming for processing data on the fly are the following: 1) responses must be produced continuously whenever new data arrives in the system; 2) data is accessed only once and is generally not maintained in its entirety, and 3) data processing time to produce a response should be low. Two models exist to compute continuous responses: the evolving model and the sliding window model; the latter fits best with applications must be computed over the most recently data rather than all the previous data. In recent years, research in the context of data stream mining has focused mainly on the evolving model. In the sliding window model, the work presented is smaller since these algorithms must be incremental and they must delete the information which expires when the window slides. Clustering is one of the fundamental techniques of data mining and is used to analyze data sets in order to find representative groups that provide a concise description of the data being processed. Clustering is critical in applications such as network intrusion detection or customer segmentation in marketing and advertising. Due to the huge amount of data that must be processed by such applications (up to millions of events per second), centralized solutions are usually unable to cope with timing restrictions and recur to shedding techniques where data is discarded during load peaks. To avoid discarding of data, processing of streams (such as clustering) must be distributed and adapted to environments where information is distributed. In streaming, research does not only focus on designing for general tasks, such as clustering, but also in finding new approaches that fit bests with particular scenarios. As an example, an ad-hoc grouping mechanism turns out to be more adequate than k-means for defense against Distributed Denial of Service (DDoS). This thesis contributes to the data stream mining clustering technique both for centralized and distributed environments. We present a centralized clustering algorithm showing capabilities to discover clusters of high quality in low time and we provide a comparison with existing state of the art solutions. We have worked on a data structure that significantly reduces memory requirements while controlling the error of the clusters statistics. We also provide two distributed clustering protocols. We focus on the analysis of two key features: the impact on the clustering quality when computation is distributed and the requirements for reducing the processing time compared to the centralized solution. Finally, with respect to ad-hoc grouping techniques, we have developed a DDoS detection framework based on clustering.We have characterized the attacks detected and we have evaluated the efficiency and effectiveness of mitigating the attack impact.

Contribuciones al análisis de problemas supercomplejos de toma de decisiones

Los fundamentos de la Teoría de la Decisión Bayesiana proporcionan un marco coherente en el que se pueden resolver los problemas de toma de decisiones. La creciente disponibilidad de ordenadores potentes está llevando a tratar problemas cada vez más complejos con numerosas fuentes de incertidumbre multidimensionales; varios objetivos conflictivos; preferencias, metas y creencias cambiantes en el tiempo y distintos grupos afectados por las decisiones. Estos factores, a su vez, exigen mejores herramientas de representación de problemas; imponen fuertes restricciones cognitivas sobre los decisores y conllevan difíciles problemas computacionales. Esta tesis tratará estos tres aspectos. En el Capítulo 1, proporcionamos una revisión crítica de los principales métodos gráficos de representación y resolución de problemas, concluyendo con algunas recomendaciones fundamentales y generalizaciones. Nuestro segundo comentario nos lleva a estudiar tales métodos cuando sólo disponemos de información parcial sobre las preferencias y creencias del decisor. En el Capítulo 2, estudiamos este problema cuando empleamos diagramas de influencia (DI). Damos un algoritmo para calcular las soluciones no dominadas en un DI y analizamos varios conceptos de solución ad hoc. El último aspecto se estudia en los Capítulos 3 y 4. Motivado por una aplicación de gestión de embalses, introducimos un método heurístico para resolver problemas de decisión secuenciales. Como muestra resultados muy buenos, extendemos la idea a problemas secuenciales generales y cuantificamos su bondad. Exploramos después en varias direcciones la aplicación de métodos de simulación al Análisis de Decisiones. Introducimos primero métodos de Monte Cario para aproximar el conjunto no dominado en problemas continuos. Después, proporcionamos un método de Monte Cario basado en cadenas de Markov para problemas con información completa con estructura general: las decisiones y las variables aleatorias pueden ser continuas, y la función de utilidad puede ser arbitraria. Nuestro esquema es aplicable a muchos problemas modelizados como DI. Finalizamos con un capítulo de conclusiones y problemas abiertos.---ABSTRACT---The foundations of Bayesian Decisión Theory provide a coherent framework in which decisión making problems may be solved. With the advent of powerful computers and given the many challenging problems we face, we are gradually attempting to solve more and more complex decisión making problems with high and multidimensional uncertainty, múltiple objectives, influence of time over decisión tasks and influence over many groups. These complexity factors demand better representation tools for decisión making problems; place strong cognitive demands on the decison maker judgements; and lead to involved computational problems. This thesis will deal with these three topics. In recent years, many representation tools have been developed for decisión making problems. In Chapter 1, we provide a critical review of most of them and conclude with recommendations and generalisations. Given our second query, we could wonder how may we deal with those representation tools when there is only partial information. In Chapter 2, we find out how to deal with such a problem when it is structured as an influence diagram (ID). We give an algorithm to compute nondominated solutions in ID's and analyse several ad hoc solution concepts.- The last issue is studied in Chapters 3 and 4. In a reservoir management case study, we have introduced a heuristic method for solving sequential decisión making problems. Since it shows very good performance, we extend the idea to general problems and quantify its goodness. We explore then in several directions the application of simulation based methods to Decisión Analysis. We first introduce Monte Cario methods to approximate the nondominated set in continuous problems. Then, we provide a Monte Cario Markov Chain method for problems under total information with general structure: decisions and random variables may be continuous, and the utility function may be arbitrary. Our scheme is applicable to many problems modeled as IDs. We conclude with discussions and several open problems.