Les communications par satellites sont l’aboutissement de recherches menées dans les domaines de télécommunications et des technologies spatiales depuis plus de 50 ans. Les premiers satellites souffraient d’un coût exorbitant pour des performances très limitées. Les avancées technologiques apparues dans ces domaines ont permis de rendre ce rapport satisfaisant et commercialement viable ce qui a permis de multiplier leurs lancements et ainsi de mettre en place de véritables réseaux de satellites. À ce jour, il existe de nombreuses constellations de satellites géostationnaires et d’orbites basses utilisées à des fins civiles ou militaires. De manière générale, le routage au sein de ces constellations s’effectue suivant un pré-calcul des routes existantes qui est alors utilisé sur une période donnée et rafraîchi si besoin. Ce type de routage n’étant optimal que sur des topologies déterministes, nous sommes donc amenés à considérer d’autres solutions si l’on relaxe cette hypothèse. L’objectif de cette thèse est d’explorer les alternatives possibles au routage pré-calculé. En tant que piste potentielle, nous proposons de vérifier l’adéquation des protocoles de routage à réplication issus du monde des réseaux tolérants au délai, DTN, aux constellations de satellites. Afin de nous offrir un cadre d’étude pertinent à la vue de cet objectif, nous nous focalisons sur une constellation particulière à caractère quasi-déterministe n’offrant pas une connectivité directe entre tous les nœuds du système. Dans une deuxième partie nous nous intéressons à la modélisation du protocole de routage Binary Spray and Wait. Nous développons un modèle capable de déterminer théoriquement la distribution du délai d’acheminement pour tout type de réseau, homogène et hétérogène. / Satellite communication is the achievement of more than 50 years of research in the fields of telecommunications and space technologies.First satellites had exorbitant costs for very limited performances. Technological advances occurred in these areas have helped them to become commercially feasible and satisfying. This enable the increase of satellite launches and thus, building complete satellite networks.Today, there are many GEO or LEO satellite constellations used for civilian or military applications. In general, routing in these constellations is done by pre-computing existing routes. These routes are then used for a given period and refreshed if needed. This type of routing is optimal only on deterministic topologies as a consequence we need to consider other solutions if we relax this assumption. The objective of this thesis is to explore alternatives to pre-computed routing. As a potential solution, we propose to assess the suitability of replication based routing protocols issued from the world of delay tolerant networks, DTN. To provide a relevant framework to study this topic, we focus on a particular constellation that present a quasi-deterministic nature and do not provide direct connectivity between all nodes of the system. In a second part, we focus on the modeling of the Binary Spray and Wait, routing protocol. We develop a model that can theoretically determine the distribution of end-to-end delay for any type of network, homogeneous and heterogeneous. Finally, we present a possible use of this model to conduct more in-depth theoretical analysis.

Made available in DSpace on 2015-04-11T14:03:00Z (GMT). No. of bitstreams: 1 Polianny Almeida Lima.pdf: 1135711 bytes, checksum: 18018c30e2dd4e938af7eadcae042cbe (MD5) Previous issue date: 2013-03-27 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Standard networking technologies are based on typical assumptions such as the existence of connectivity end-to-end between source and destination for the entire period of communication, low error rates, retransmission mechanisms to repair errors, and relatively small communication delays. If one or more of these assumptions are not achieved in practice, blinks occur in communication, creating challenges that must be overcome to ensure the successful transmission. In this context, came the delay-tolerant networks and disconnection (DTN - Delay Tolerant Networks), an emerging technology for communications when there is no network infrastructure and disconnections may occur frequently due to the mobility of nodes. To bypass the problem of disconnections, DTN networks use the concept of persistent storage, which becomes a problem because the nodes have limited capacity of the buffers. The question is how to select the messages that remain in buffers longer considering the unpredictable mobility of nodes, short contacts between pairs of nodes, storage nodes achieved by finite and so on. This paper proposes a buffer management that transmits messages adaptively based on entropy variation of mobility network. / Tecnologias de redes tradicionais baseiam-se em suposições típicas, como a existência de conectividade fim a fim entre origem e destino durante todo o período de comunicação, baixas taxas de erros, mecanismos de retransmissão para reparar erros, e atrasos de comunicação relativamente pequenos. Caso uma ou mais dessas suposições não sejam alcançadas na prática, ocorrem intermitências na comunicação, criando desafios que devem ser superados a fim de garantir o sucesso na transmissão. Nesse contexto, surgiram as redes tolerantes a atraso e desconexão (DTN - Delay Tolerant Networks), uma tecnologia emergente para comunicações quando não há infraestrutura de rede e desconexões podem ocorrer com frequência devido à mobilidade dos nodos. Para contornar o problema das desconexões, as redes DTN utilizam o conceito de armazenamento persistente, o que se torna um problema, pois os nodos tem capacidade de buffers limitada. A questão é selecionar as mensagens que ficarão nos buffers por mais tempo levando em consideração a mobilidade imprevisível dos nodos, contatos de curta duração entre pares de nodos, armazenamento finito realizado pelos nodos e assim por diante. Este trabalho apresenta uma proposta de gerenciamento de buffer que transmite mensagens de forma adaptativa baseada na variação de entropia de mobilidade da rede.

La pénétration du marché des appareils mobiles a connu une croissance impressionnante ces dernières années. Smartphones, tablettes et ordinateurs portables sont devenus soit producteurs soit consommateurs de contenus générés par les utilisateurs. Les communications opportunistes permettent une couverture étendue dans les endroits où il n'existe aucune infrastructure réseau disponible et des stratégies de délestage de données pour aider les opérateurs à soulager la charge de leurs infrastructures. Dans cette thèse, nous considérons le cas de la diffusion opportuniste de plusieurs grands contenus d'un point de vue expérimental. Dans la première partie nous commençons par implémenter EPICS, un protocole réseau conçu pour l'échange opportuniste de grands contenus, dans des terminaux Android. Après sa évaluation nous proposons DAD, un nouveau protocole, qui envoie une rafale de paquets de données de façon adaptative. Nous comparons les deux protocoles expérimentalement et, à l'aide des traces de contacts, soit réelles, soit synthétiques, nous obtenons des gains importants avec cette nouvelle approche. La deuxième partie est dédiée au passage à l'échelle des systèmes de surveillance passive. Nous proposons deux approches. La première est basée sur la similarité des traces et des algorithmes de détection de communautés. La deuxième est basée sur des mesures collaboratives. / The market penetration of mobile devices has experienced an impressive growth. Smartphones, tablets, and laptops have become both producers and consumers of user-generated contents. They also motivate novel communication paradigms such as the possibility to establish, in an opportunistic fashion, direct device-to-device links whenever two mobile nodes enter within the wireless range of each other. In this thesis, we consider the case of opportunistic dissemination of multiple large contents from an experimental point of view. This implies revisiting, among others, the common assumption that contacts have enough capacity to transfer any amount of data.In the first part of this thesis, we start from an Android implementation of EPICS, a network protocol designed for exchanging large contents in opportunistic networks, on off-the-shelf devices. After an deep analysis of application-level logs and captured wireless traces we found out limitations and uncovered improving possibilities. We then propose DAD, a new content dissemination protocol that adaptively sends bursts of data instead of the per-fragment transmission strategy of EPICS.The second part of this thesis deals with the scalability of legacy WLAN monitoring systems. We propose two original approaches. With the first one, based on trace similarity and community detection algorithms, we are able to identify how many monitor we need in a target area and where to place them. The second approach in based on collaborative measurements. In this case we face the risk of biased measures due attacks of malicious users generating adulterated traces. We then propose a method to detect such malicious behaviors.

[EN] Intelligent Transportation Systems (ITS) can make transportation safer, more efficient, and more sustainable by applying various information and communication technologies. One of these technologies are \acfp{VN}. \acp{VN} combine different communication solutions such as cellular networks, \acfp{VANET}, or IEEE 802.11 technologies to provide connectivity among vehicles, and between vehicles and road infrastructure. This thesis focuses on VNs, and considers that the high speed of the nodes and the presence of obstacles like buildings, produces a highly variable network topology, as well as more frequent partitions in the network. Therefore, classical \ac{MANET} protocols do not adapt well to VANETs. Under these conditions, \ac{DTN} have been proposed as an alternative able to cope with these adverse characteristics. In DTN, when a message cannot be routed to its destination, it is not immediately dropped but it is instead stored and carried until a new route becomes available. The combination of VN and DTN is called \acp{VDTN}. In this thesis, we propose a new VDTN protocol designed to collect information from vehicular sensors. Our proposal, called \ac{MSDP}, combines information about the localization obtained from a GNSS system with the actual street/road layout obtained from a Navigation System (NS) to define a new routing metric. Both analytical and simulation results prove that MSDP outperforms previous proposals. Concerning the deployment of VNs and VANET technologies, technology already left behind the innovation and the standardization phases, and it is about time it reach the first early adopters in the market. However, most car manufacturers have decided to implement VN devices in the form of On Board Units (OBUs), which are expensive, heavily manufacturer dependent, and difficult to upgrade. These facts are delaying the deployment of VN. To boost this process, we have developed the GRCBox architecture. This architecture is based on low-cost devices and enables the establishment of V2X, \emph{i.e.} V2I and V2V, communications while integrating users by easing the use of general purpose devices like smartphones, tablets or laptops. To demonstrate the viability of the GRCBox architecture, we combined it with a DTN platform called Scampi to obtain actual results over a real VDTN scenario. We also present several GRCBox-aware applications that illustrate how developers can create applications that bring the potential of VN to user devices. / [ES] Los sistemas de transporte inteligente (ITS) son el soporte para el establecimiento de un transporte más seguro, más eficiente y más sostenible mediante el uso de tecnologías de la información y las comunicaciones. Una de estas tecnologías son las redes vehiculares (VNs). Las VNs combinan diferentes tecnologías de comunicación como las redes celulares, las redes ad-hoc vehiculares (VANETs) o las redes 802.11p para proporcionar conectividad entre vehículos, y entre vehículos y la infraestructura de carreteras. Esta tesis se centra en las VNs, en las cuales la alta velocidad de los nodos y la presencia de obstáculos como edificios producen una topología de red altamente variable, así como frecuentes particiones en la red. Debido a estas características, los protocolos para redes móviles ad-hoc (MANETs) no se adaptan bien a las VANETs. En estas condiciones, las redes tolerantes a retardos (DTNs) se han propuesto como una alternativa capaz de hacer frente a estos problemas. En DTN, cuando un mensaje no puede ser encaminado hacia su destino, no es inmediatamente descartado sino es almacenado hasta que una nueva ruta esta disponible. Cuando las VNs y las DTNs se combinan surgen las redes vehiculares tolerantes a retardos (VDTN). En esta tesis proponemos un nuevo protocolo para VDTNs diseñado para recolectar la información generada por sensores vehiculares. Nuestra propuesta, llamada MSDP, combina la información obtenida del servicio de información geográfica (GIS) con el mapa real de las calles obtenido del sistema de navegación (NS) para definir una nueva métrica de encaminamiento. Resultados analíticos y mediante simulaciones prueban que MSDP mejora el rendimiento de propuestas anteriores. En relación con el despliegue de las VNs y las tecnologías VANET, la tecnología ha dejado atrás las fases de innovación y estandarización, ahora es el momento de alcanzar a los primeros usuarios del mercado. Sin embargo, la mayoría de fabricantes han decidido implementar los dispositivos para VN como unidades de a bordo (OBU), las cuales son caras y difíciles de actualizar. Además, las OBUs son muy dependientes del fabricante original. Todo esto esta retrasando el despliegue de las VNs. Para acelerar la adopción de las VNs, hemos desarrollado la arquitectura GRCBox. La arquitectura GRCBox esta basada en un dispositivo de bajo coste que permite a los usuarios usar comunicaciones V2X (V2V y V2I) mientras utilizan dispositivos de propósito general como teléfonos inteligentes, tabletas o portátiles. Las pruebas incluidas en esta tesis demuestran la viabilidad de la arquitectura GRCBox. Mediante la combinación de nuestra GRCBox y una plataforma de DTN llamada Scampi hemos diseñado y probado un escenario VDTN real. También presentamos como los desarrolladores pueden crear nuevas aplicaciones GRCBox para llevar el potencial de las VN a los dispositivos de usuario. / [CA] Els sistemes de transport intel·ligent (ITS) poden crear un transport més segur, més eficient i més sostenible mitjançant l'ús de tecnologies de la informació i les comunicacions aplicades al transport. Una d'aquestes tecnologies són les xarxes vehiculars (VN). Les VN combinen diferents tecnologies de comunicació, com ara les xarxes cel·lulars, les xarxes ad-hoc vehiculars (VANET) o les xarxes 802.11p, per a proporcionar comunicació entre vehicles, i entre vehicles i la infraestructura de carreteres. Aquesta tesi se centra en les VANET, en les quals l'alta velocitat dels nodes i la presència d'obstacles, com els edificis, produeixen una topologia de xarxa altament variable, i també freqüents particions en la xarxa. Per aquest motiu, els protocols per a xarxes mòbils ad-hoc (MANET) no s'adapten bé. En aquestes condicions, les xarxes tolerants a retards (DTN) s'han proposat com una alternativa capaç de fer front a aquests problemes. En DTN, quan un missatge no pot ser encaminat cap a la seua destinació, no és immediatament descartat sinó que és emmagatzemat fins que apareix una ruta nova. Quan les VN i les DTN es combinen sorgeixen les xarxes vehicular tolerants a retards (VDTN). En aquesta tesi proposem un nou protocol per a VDTN dissenyat per a recol·lectar la informació generada per sensors vehiculars. La nostra proposta, anomenada MSDP, combina la informació obtinguda del servei d'informació geogràfica (GIS) amb el mapa real dels carrers obtingut del sistema de navegació (NS) per a definir una nova mètrica d'encaminament. Resultats analítics i mitjançant simulacions proven que MSDP millora el rendiment de propostes prèvies. En relació amb el desplegament de les VN i les tecnologies VANET, la tecnologia ha deixat arrere les fases d'innovació i estandardització, ara és temps d'aconseguir als primers usuaris del mercat. No obstant això, la majoria de fabricants han decidit implementar els dispositius per a VN com a unitats de bord (OBU), les quals són cares i difícils d'actualitzar. A més, les OBU són molt dependents del fabricant original. Tot això està retardant el desplegament de les VN. Per a accelerar l'adopció de les VN, hem desenvolupat l'arquitectura GRCBox. L'arquitectura GRCBox està basada en un dispositiu de baix cost que permet als usuaris usar comunicacions V2V mentre usen dispositius de propòsit general, com ara telèfons intel·ligents, tauletes o portàtils. Les proves incloses en aquesta tesi demostren la viabilitat de l'arquitectura GRCBox. Mitjançant la combinació de la nostra GRCBox i la plataforma de DTN Scampi, hem dissenyat i provat un escenari VDTN pràctic. També presentem com els desenvolupadors poden crear noves aplicacions GRCBox per a portar el potencial de les VN als dispositius d'usuari. / Martínez Tornell, S. (2016). Delay Tolerant Networks for Efficient Information Harvesting and Distribution in Intelligent Transportation Systems [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/68486

[ES] La disponibilidad y el rendimiento de las actuales tecnologías inalámbricas como WiFi o 4G, pueden tener serios problemas de congestión y propagación, especialmente en espacios muy concurridos, o bien ser inaccesibles en sitios remotos o con baja densidad de personas. La utilización de las Redes Oportunistas en este tipo de escenarios puede ser la solución a estos problemas. Estas redes se basan en la oportunidad de intercambiar mensajes utilizando algún tipo de tecnología de comunicación directa entre dispositivos móviles como son Bluetooth o WiFi. El rendimiento de las Redes Oportunistas depende principalmente de la movilidad de los nodos y los protocolos de enrutamiento utilizados, siendo estos últimos los encargados de decidir como son intercambiados los mensajes cuando un contacto ocurre, intentando encontrar la mejor ruta para que un mensaje alcance su destino. Por otra parte, la eficiencia de la difusión en estas redes está ligada especialmente a la movilidad de los usuarios y al comportamiento humano. Entonces, para el análisis y la evaluación del rendimiento de las Redes Oportunistas es necesario considerar tanto los aspectos técnicos relacionados con los protocolos de encaminamiento, como los aspectos de la movilidad humana. Esta tesis doctoral se centra principalmente en evaluar la diseminación de la información usando redes oportunistas en escenarios urbanos, en los que existen diferentes densidades y tasas de renovación de personas, es decir, con usuarios que puedan entrar y salir del escenario evaluado. Dado que la existencia de este tipo de trazas reales es muy limitada, en esta tesis se plantea la generación de este tipo de trazas de forma sintética. Para ello, mediante el uso de un simulador de movilidad peatonal, se han generado trazas realistas de movilidad con diferentes grados de densidad y tasas de renovación de usuarios con el objeto de evaluar diferentes aspectos de la difusión de mensajes en las Redes Oportunistas. El análisis de las características temporales y espaciales de estas trazas generadas refleja el realismo de los escenarios que se han considerado. Además, los experimentos relativos a la difusión de mensajes realizados con estas trazas, confirman que la tasa de renovación tiene un gran impacto en el rendimiento de los protocolos, lo que es particularmente evidente cuando el tamaño de los mensajes es mayor. Por otra parte, también se ha realizado el estudio, utilizando en este caso trazas reales, de la difusión de información a través de las Redes Oportunistas Vehiculares. Ya que de la misma manera la movilidad de estos vehículos está ligada al comportamiento humano, nos hemos centrado en la diseminación de la información en determinadas horas del día dependiendo del número de vehículos en circulación, debido a que este aspecto tiene un gran impacto en el reenvío de datos. Los resultados de estos experimentos confirman que los dos principales factores que afectan a la difusión de información son el grado de movilidad y el tamaño de mensaje. Aunque es bien sabido que al aumentar la densidad de nodos aumenta la velocidad de difusión, mostramos que, al mantener la densidad de nodos fija, las tasas de renovación más altas hacen que la relación de entrega disminuya. Además, descubrimos que la relación entre el tamaño del mensaje y la duración del contacto también es un factor clave, lo que demuestra que la transmisión de los mensajes grandes puede llevar a un rendimiento general muy bajo. Basándonos en todo lo expuesto anteriormente, se ha propuesto una mejora al protocolo Epidemic, a la que hemos denominado EpidemicX2, que se basa en la fragmentación de los datos a ser enviados con el fin de aprovechar la corta duración de los contactos para aumentar así la posibilidad de su entrega. Este protocolo es particularmente efectivo para la difusión de los mensajes grandes. Los resultados muestran que la tasa de entrega se increment / [CA] La disponibilitat i el rendiment de les actuals tecnologies sense fil com WiFi o 4G, poden tindre seriosos problemes de congestió i propagació, especialment en espais molt concorreguts, o bé ser inaccessibles en llocs remots o amb baixa densitat de persones. La utilització de les Xarxes Oportunistes en este tipus d'escenaris pot ser la solució a estos problemes. Estes xarxes es basen en l'oportunitat d'intercanviar missatges utilitzant algun tipus de tecnologia de comunicació directa entre dispositius mòbils com són Bluetooth o WiFi. El rendiment de les Xarxes Oportunistes depén principalment de la mobilitat dels nodes i els protocols d'enrutamiento utilitzats, sent estos últims els encarregats de decidir com són intercanviats els missatges quan un contacte ocorre, intentant trobar la millor ruta perquè un missatge abast el seu destí. D'altra banda, l'eficiència de la difusió en estes xarxes està lligada especialment a la mobilitat dels usuaris i al comportament humà. Llavors, per a l'anàlisi i l'avaluació del rendiment de les Xarxes Oportunistes és necessari considerar tant els aspectes tècnics relacionats amb els protocols d'acarrerament, com els aspectes de la mobilitat humana. Esta tesi doctoral se centra principalment a avaluar la disseminació de la informació usant xarxes oportunistes en escenaris urbans, en els que hi ha diferents densitats i taxes de renovació de persones, és a dir, amb usuaris que puguen entrar i eixir de l'escenari avaluat. Atés que l'existència d'este tipus de traces reals és molt limitada, en esta tesi es planteja la generació d'este tipus de traces de forma sintètica. Per a això, per mitjà de l'ús d'un simulador de mobilitat de vianants, s'han generat traces realistes de mobilitat amb diferents graus de densitat i taxes de renovació d'usuaris amb l'objecte d'avaluar diferents aspectes de la difusió de missatges en les Xarxes Oportunistes. L'anàlisi de les característiques temporals i espacials d'estes traces generades reflectix el realisme dels escenaris que s'han considerat. A més, els experiments relatius a la difusió de missatges realitzats amb estes traces, confirmen que la taxa de renovació té un gran impacte en el rendiment dels protocols, la qual cosa és particularment evident quan la grandària dels missatges és major. D'altra banda, també s'ha realitzat l'estudi, utilitzant en este cas traces reals, de la difusió d'informació a través de les Xarxes Oportunistes Vehiculares. Ja que de la mateixa manera la mobilitat d'estos vehicles està lligada al comportament humà, ens hem centrat en la disseminació de la informació en determinades hores del dia depenent del nombre de vehicles en circulació, pel fet que este aspecte té un gran impacte en el reexpedició de dades. Els resultats d'estos experiments confirmen que els dos principals factors que afecten la difusió d'informació són el grau de mobilitat i la grandària de missatge. Encara que és ben sabut que a l'augmentar la densitat de nodes augmenta la velocitat de difusió, mostrem que, al mantindre la densitat de nodes fixa, les taxes de renovació més altes fan que la relació d'entrega disminuïsca. A més, descobrim que la relació entre la grandària del missatge i la duració del contacte també és un factor clau, la qual cosa demostra que la transmissió dels missatges grans pot portar a un rendiment general molt davall. Basant-nos en tot el que exposa anteriorment, s'ha proposat una millora al protocol Epidemic, a la que hem denominat EpidemicX2, que es basa en la fragmentació de les dades a ser enviats a fi d'aprofitar la curta duració dels contactes per a augmentar així la possibilitat del seu entrega. Este protocol és particularment efectiu per a la difusió dels missatges grans. Els resultats mostren que la taxa d'entrega s'incrementa, el temps mitjana en l'entrega es reduïx, sense un substancial increment en termes de sobrecàrrega. / [EN] The availability and performance of current wireless technologies such as WiFi or 4G, can have severe problems of congestion and information diffusion, especially in crowded spaces, or, on the other side, be inaccessible in places with a low density of people. The use of Opportunistic Networks in these types of scenarios can be a solution to these problems. These networks are based on the opportunity to exchange messages using some type of direct communication technology between nearby mobile devices such as Bluetooth or WiFi. The performance of these networks depends mainly on the mobility of the nodes and the routing protocols used. The goal of these protocols is to decide how messages are exchanged when a pair of nodes are in contact, trying to find the best route for a message to reach its destination. The efficiency of the diffusion in these networks is related mainly to the mobility of users and human behaviour. Therefore, for the analysis and evaluation of the performance of the Opportunistic Networks, it is necessary to consider both the technical aspects related to the routing protocols, as well as the aspects of human mobility. This thesis mainly focuses on evaluating the dissemination of information using Opportunistic Networks in urban scenarios, in which there are different densities and renewal rates of people, that is, with users who can enter and leave the evaluated scenario. Given that the existence of this type of real traces is very limited, this thesis proposes the generation of realistic traces. For this, through the use of a pedestrian mobility simulator, realistic traces of mobility have been defined with different degrees of density and renewal rates of users to evaluate different aspects of the Opportunistic Network with this approach. The analysis of the temporal and spatial characteristics of these generated traces reflects the realism of the scenarios that have been considered. The experiments related to the diffusion of messages made with these traces, confirm that the renewal rate has a high impact on the performance of the protocols, which is particularly evident when the message size is longer. Furthermore, considering vehicular scenarios, a study has also been carried out using real traces, following the same methodology to evaluate the dissemination of information. Since in the same way the mobility of these vehicles is linked to human behaviour, we have focused on the dissemination of information at certain times of the day depending on the number of vehicles in circulation, since this aspect has a significant impact on data diffusion. The results of all these experiments show that the diffusion of contents is affected mainly by two factors: degree of mobility and message size. Although it is well known that increasing the density of nodes increases the speed of diffusion, we show that, by maintaining the density of fixed nodes, the higher renewal rates cause the delivery ratio to decrease. In addition, we discovered that the relationship between message size and contact duration is also a key factor, showing that large messages can lead to very reduced overall performance. Based on these results, an improvement to the Epidemic protocol has been proposed, called EpidemicX2, which is based on the fragmentation of the data to be sent in order to take advantage of the short duration of the contacts. This protocol is particularly effective for the dissemination of large messages. The results show that the delivery rate increases, the average time in the delivery is reduced, without a substantial increase in terms of overload. / Finalmente, quiero agradecer a la República del Ecuador junto con la “Secretaría de Educación Superior, Ciencia y Tecnología e Innovación” - SENESCYT, por su programa de apoyo y financiar mis estudios. / Chancay Garcia, LJ. (2019). Evaluación y Modelado de Redes Oportunistas [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/124339

Cette thèse apporte des contributions à la modélisation, compréhension ainsi qu'à la communication efficace d'information dans les réseaux dynamiques peuplant la périphérie de l'Internet. Par réseaux dynamiques, nous signifions les réseaux pouvant être modélisés par des graphes dynamiques dans lesquels noeuds et liens évoluent temporellement. Dans la première partie de la thèse, nous proposons un nouveau modèle de mobilité - STEPS - qui permet de capturer un large spectre de comportement de mobilité humains. STEPS mets en oeuvre deux principes fondamentaux de la mobilité humaine : l'attachement préférentiel à une zone de prédilection et l'attraction vers une zone de prédilection. Nous proposons une modélisation markovienne de ce modèle de mobilité. Nous montrons que ce simple modèle paramétrique est capable de capturer les caractéristiques statistiques saillantes de la mobilité humaine comme la distribution des temps d'inter-contacts et de contacts. Dans la deuxième partie, en utilisant STEPS, nous analysons les propriétés comportementales et structurelles fondamentales des réseaux opportunistes. Nous redéfinissons dans le contexte des réseaux dynamiques la notion de structure petit monde et montrons comment une telle structure peut émerger. En particulier, nous montrons que les noeuds fortement dynamiques peuvent jouer le rôle de ponts entre les composants déconnectés, aident à réduire significativement la longueur du chemin caractéristique du réseau et contribuent à l'émergence du phénomène petit-monde dans les réseaux dynamiques. Nous proposons une façon de modéliser ce phénomène sous STEPS. À partir d'un réseau dynamique régulier dans lequel les noeuds limitent leur mobilité à leurs zones préférentielles respectives. Nous recablons ce réseau en injectant progressivement des noeuds nomades se déplaçant entre plusieurs zones. Nous montrons que le pourcentage de tels nœuds nomades est de 10%, le réseau possède une structure petit monde avec un fort taux de clusterisation et un faible longueur du chemin caractéristique. La troisième contribution de cette thèse porte sur l'étude de l'impact du désordre et de l'irrégularité des contacts sur la capacité de communication d'un réseau dynamique. Nous analysons le degré de désordre de réseaux opportunistes réels et montrons que si exploité correctement, celui-ci peut améliorer significativement les performances du routage. Nous introduisons ensuite un modèle permettant de capturer le niveau de désordre d'un réseau dynamique. Nous proposons deux algorithmes simples et efficaces qui exploitent la structure temporelle d'un réseau dynamique pour délivrer les messages avec un bon compromis entre l'usage des ressources et les performances. Les résultats de simulations et analytiques montrent que ce type d'algorithme est plus performant que les approches classiques. Nous mettons également en évidence aussi la structure de réseau pour laquelle ce type d'algorithme atteint ses performances optimum. Basé sur ce résultat théorique nous proposons un nouveau protocole de routage efficace pour les réseaux opportunistes centré sur le contenu. Dans ce protocole, les noeuds maintiennent, via leurs contacts opportunistes, une fonction d'utilité qui résume leur proximité spatio-temporelle par rapport aux autres noeuds. En conséquence, router dans un tel contexte se résume à suivre le gradient de plus grande pente conduisant vers le noeud destination. Cette propriété induit un algorithme de routage simple et efficace qui peut être utilisé aussi bien dans un contexte d'adressage IP que de réseau centré sur les contenus. Les résultats de simulation montrent que ce protocole superforme les protocoles de routage classiques déjà définis pour les réseaux opportunistes. La dernière contribution de cette thèse consiste à mettre en évidence une application potentielle des réseaux dynamiques dans le contexte du " mobile cloud computing ". En utilisant les techniques d'optimisation particulaires, nous montrons que la mobilité peut augmenter considérablement la capacité de calcul des réseaux dynamiques. De plus, nous montrons que la structure dynamique du réseau a un fort impact sur sa capacité de calcul.

In this thesis we study several resource management problems in two classes of wireless networks. The thesis is in two parts, the first being concerned with game theoretic approaches for cellular networks, and the second with control theoretic approaches for mobile opportunistic networks. In Part I of the thesis, we first investigate optimal association and power control for the uplink of multichannel multicell cellular networks, in which each channel is used by exactly one base station (BS) (i.e., cell). Users have minimum signal to interference ratio(SINR) requirements and associate with BSs where least transmission powers are required. We formulate the problem as a non-cooperative game among users. We propose a distributed association and power update algorithm, and show its convergence to a Nash equilibrium of the game. We consider network models with discrete mobiles(yielding an atomic congestion game),as well as a continuum of mobiles(yielding a population game). We find that the equilibria need not be Pareto efficient, nor need they be system optimal. To address the lack of system optimality, we propose pricing mechanisms. We show that these prices weakly enforce system optimality in general, and strongly enforce it in special settings. We also show that these mechanisms can be implemented in distributed fashions. Next, we consider the hierarchical problems of user association and BS placement, where BSs may belong to the same(or, cooperating) or to competing service providers. Users transmit with constant power, and associate with base stations that yield better SINRs. We formulate the association problem as a game among users; it determines the cell corresponding to each BS. Some intriguing observations we report are:(i)displacing a BS a little in one direction may result in a displacement of the boundary of the corresponding cell to the opposite direction;(ii)A cell corresponding to a BS may be the union of disconnected sub-cells. We then study the problem of the placement of BSs so as to maximize service providers’ revenues. The service providers need to take into account the mobiles’ behavior that will be induced by the placement decisions. We consider the cases of single frequency band and disjoint frequency bands of operation. We also consider the networks in which BSs employ successive interference cancellation(SIC) decoding. We observe that the BS locations are closer to each other in the competitive case than in the cooperative case, in all scenarios considered. Finally, we study cooperation among cellular service providers. We consider networks in which communications involving different BSs do not interfere. If service providers jointly deploy and pool their resources, such as spectrum and BSs, and agree to serve each others’ customers, their aggregate payoff substantially increases. The potential of such cooperation can, however ,be realized only if the service providers intelligently determine who they would cooperate with, how they would deploy and share their resources, and how they would share the aggregate payoff. We first assume that the service providers can arbitrarily share the aggregate payoff. A rational basis for payoff sharing is imperative for the stability of the coalitions. We study cooperation using the theory of transferable payoff coalitional games. We show that the optimum cooperation strategy, which involves the acquisition of channels, and deployment and allocation of BSs to customers, is the solution of a concave or an integer optimization problem. We then show that the grand coalition is stable, i.e., if all the service providers cooperate, there is an operating point offering each service provider a share that eliminates the possibility of a subset of service providers splitting from the grand coalition; this operating point also maximizes the service providers’ aggregate payoff. These stabilizing payoff shares are computed by solving the dual of the above optimization problem. Moreover, the optimal cooperation strategy and the stabilizing payoff shares can be obtained in polynomial time using distributed computations and limited exchange of confidential information among the service providers. We then extend the analysis to the scenario where service providers may not be able to share their payoffs. We now model cooperation as a nontransferable payoff coalitional game. We again show that there exists a cooperation strategy that leaves no incentive for any subset of service providers to split from the grand coalition. To compute this cooperation strategy and the corresponding payoffs, we relate this game and its core to an exchange market and its equilibrium. Finally, we extend the formulations and the results to the case when customers are also decision makers in coalition formation. In Part II of this thesis, we consider the problem of optimal message forwarding in mobile opportunistic wireless networks. A message originates at a node(source), and has to be delivered to another node (destination). In the network, there are several other nodes that can assist in relaying the message at the expense of additional transmission energies. We study the trade-off between delivery delay and energy consumption. First, we consider mobile opportunistic networks employing two-hop relaying. Because of the intermittent connectivity, the source may not have perfect knowledge of the delivery status at every instant. We formulate the problem as a stochastic control problem with partial information, and study structural properties of the optimal policy. We also propose a simple suboptimal policy. We then compare the performance of the suboptimal policy against that of the optimal control with perfect information. These are bounds on the performance of the proposed policy with partial information. We also discuss a few other related open loop policies. Finally, we investigate the case where a message has to be delivered to several destinations, but we are concerned with delay until a certain fraction of them receive the message. The network employs epidemic relaying. We first assume that, at every instant, all the nodes know the number of relays carrying the packet and the number of destinations that have received the packet. We formulate the problem as a controlled continuous time Markov chain, and derive the optimal forwarding policy. As observed earlier, the intermittent connectivity in the network implies that the nodes may not have the required perfect knowledge of the system state. To address this issue, we then obtain an ODE(i.e., a deterministic fluid) approximation for the optimally controlled Markov chain. This fluid approximation also yields an asymptotically optimal deterministic policy. We evaluate the performance of this policy over finite networks, and demonstrate that this policy performs close to the optimal closed loop policy. We also briefly discuss the case where message forwarding is accomplished via two-hop relaying.

Cette thèse apporte des contributions à la modélisation, compréhension ainsi qu’à la communication efficace d’information dans les réseaux dynamiques peuplant la périphérie de l’Internet. Par réseaux dynamiques, nous signifions les réseaux pouvant être modélisés par des graphes dynamiques dans lesquels noeuds et liens évoluent temporellement. Dans la première partie de la thèse, nous proposons un nouveau modèle de mobilité - STEPS - qui permet de capturer un large spectre de comportement de mobilité humains. STEPS mets en oeuvre deux principes fondamentaux de la mobilité humaine : l’attachement préférentiel à une zone de prédilection et l’attraction vers une zone de prédilection. Nous proposons une modélisation markovienne de ce modèle de mobilité. Nous montrons que ce simple modèle paramétrique est capable de capturer les caractéristiques statistiques saillantes de la mobilité humaine comme la distribution des temps d’inter-contacts et de contacts. Dans la deuxième partie, en utilisant STEPS, nous analysons les propriétés comportementales et structurelles fondamentales des réseaux opportunistes. Nous redéfinissons dans le contexte des réseaux dynamiques la notion de structure petit monde et montrons comment une telle structure peut émerger. En particulier, nous montrons que les noeuds fortement dynamiques peuvent jouer le rôle de ponts entre les composants déconnectés, aident à réduire significativement la longueur du chemin caractéristique du réseau et contribuent à l’émergence du phénomène petit-monde dans les réseaux dynamiques. Nous proposons une façon de modéliser ce phénomène sous STEPS. À partir d’un réseau dynamique régulier dans lequel les noeuds limitent leur mobilité à leurs zones préférentielles respectives. Nous recablons ce réseau en injectant progressivement des noeuds nomades se déplaçant entre plusieurs zones. Nous montrons que le pourcentage de tels nœuds nomades est de 10%, le réseau possède une structure petit monde avec un fort taux de clusterisation et un faible longueur du chemin caractéristique. La troisième contribution de cette thèse porte sur l’étude de l’impact du désordre et de l’irrégularité des contacts sur la capacité de communication d’un réseau dynamique. Nous analysons le degré de désordre de réseaux opportunistes réels et montrons que si exploité correctement, celui-ci peut améliorer significativement les performances du routage. Nous introduisons ensuite un modèle permettant de capturer le niveau de désordre d’un réseau dynamique. Nous proposons deux algorithmes simples et efficaces qui exploitent la structure temporelle d’un réseau dynamique pour délivrer les messages avec un bon compromis entre l’usage des ressources et les performances. Les résultats de simulations et analytiques montrent que ce type d’algorithme est plus performant que les approches classiques. Nous mettons également en évidence aussi la structure de réseau pour laquelle ce type d’algorithme atteint ses performances optimum. Basé sur ce résultat théorique nous proposons un nouveau protocole de routage efficace pour les réseaux opportunistes centré sur le contenu. Dans ce protocole, les noeuds maintiennent, via leurs contacts opportunistes, une fonction d’utilité qui résume leur proximité spatio-temporelle par rapport aux autres noeuds. En conséquence, router dans un tel contexte se résume à suivre le gradient de plus grande pente conduisant vers le noeud destination. Cette propriété induit un algorithme de routage simple et efficace qui peut être utilisé aussi bien dans un contexte d’adressage IP que de réseau centré sur les contenus. Les résultats de simulation montrent que ce protocole superforme les protocoles de routage classiques déjà définis pour les réseaux opportunistes. La dernière contribution de cette thèse consiste à mettre en évidence une application potentielle des réseaux dynamiques dans le contexte du « mobile cloud computing ». / This thesis contributes to the modeling, understanding and efficient communication in dynamic networks populating the periphery of the Internet. By dynamic networks, we refer to networks that can be modeled by dynamic graphs in which nodes and links change temporally. In the first part of the thesis, we propose a new mobility model - STEPS - which captures a wide spectrum of human mobility behavior. STEPS implements two fundamental principles of human mobility: preferential attachment and attractor. We show that this simple parametric model is able to capture the salient statistical properties of human mobility such as the distribution of inter-contact/contact time. In the second part, using STEPS, we analyze the fundamental behavioral and structural properties of opportunistic networks. We redefine in the context of dynamic networks the concept of small world structure and show how such a structure can emerge. In particular, we show that highly dynamic nodes can play the role of bridges between disconnected components, helping to significantly reduce the length of network path and contribute to the emergence of small-world phenomenon in dynamic networks. We propose a way to model this phenomenon in STEPS. From a regular dynamic network in which nodes limit their mobility to their respective preferential areas. We rewire this network by gradually injecting highly nomadic nodes moving between different areas. We show that when the ratio of such nomadic nodes is around 10%, the network has small world structure with a high degree of clustering and a low characteristic path length. The third contribution of this thesis is the study of the impact of disorder and contact irregularity on the communication capacity of a dynamic network. We analyze the degree of disorder of real opportunistic networks and show that if used correctly, it can significantly improve routing performances. We then introduce a model to capture the degree of disorder in a dynamic network. We propose two simple and efficient algorithms that exploit the temporal structure of a dynamic network to deliver messages with a good tradeoff between resource usage and performance. The simulation and analytical results show that this type of algorithm is more efficient than conventional approaches. We also highlight also the network structure for which this type of algorithm achieves its optimum performance. Based on this theoretical result, we propose a new efficient routing protocol for content centric opportunistic networks. In this protocol, nodes maintain, through their opportunistic contacts, an utility function that summarizes their spatio-temporal proximity to other nodes. As a result, routing in this context consists in following the steepest slopes of the gradient field leading to the destination node. This property leads to a simple and effective algorithm routing that can be used both in the context of IP networks and content centric networks. The simulation results show that this protocol outperforms traditional routing protocols already defined for opportunistic networks. The last contribution of this thesis is to highlight the potential application of dynamic networks in the context of "mobile cloud computing." Using the particle optimization techniques, we show that mobility can significantly increase the processing capacity of dynamic networks. In addition, we show that the dynamic structure of the network has a strong impact on its processing capacity.