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.

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.

Rychlý vývoj v oblasti mobilní informatiky vyústil v nový, alternativní způsob mobilní komunikace, v němž mobilní uzly tvoří samoorganizující se bezdrátovou síť, jíž se říká mobilní síť ad hoc (Mobile Ad hoc Network, MANET). Specifické vlastnosti sítí MANET stavějí návrh síťového protokolu před řadu problémů na všech vrstvách protokolové sady . Příčinou jsou nepředvídatelné změny topologie a mobilní povaha těchto sítí. Nástrojem, který řeší problémy plynoucí z mobility uzlů, je predikce budoucích změn v topologii sítě. To má zásadní význam pro různé úlohy jako přesměrování. Tato disertační práce se zabývá dvěma metodami predikce mobility pro sítě MANET. První metoda se nazývá „predikce mobility s využitím virtuální mapy“ (mobility prediction using virtual map) a předpokládá, že každý uzel si dokáže vybudovat svou virtuální mapu v závislosti na svém umístění v průběhu času. Vyvinutý predikční algoritmus byl implementován do síťového simulátoru NS-2, aby jej bylo možné vyhodnotit. V této práci zkoumám stávající modely mobility a způsob, jakým v nich lze aplikovat tuto metodu predikce. Simulace sledují zlepšení výkonnosti, co se týče průměrného zpoždění na bázi end-to-end, poměru doručených paketů a propustnosti sítě. Navržený koncept predikce byl implementován pomocí směrovacího protokolu AODV(Ad Hoc On-Demand Distance Vector). Pro druhou metodu jsem vyvinula umělou neuronovou síť pro predikci pohybů v sítích MANET. Model pro predikci mobility vznikl na základě dat shromážděných ze vzorců umístění. K učení či trénování ANN byl využit bayesovský přístup. Ten byl implementován v softwaru pro trénování bayesovských neuronových sítí s názvem Model Manager. Nejlepším způsobem hodnocení závěrečného modelu je provedení predikcí a jejich srovnání s cílovými daty. Predikce vznikají na základě 50 vzorců jako vstupních proměnných. Dosažené výsledky prezentované s diskutované v práci se vyznačují zlepšením zásadních parametrů komunikační sítě, jako jsou propustnost, zpoždění, Poměr doručených paketů, až o 30% v porovnání s klasickým směrovacím protokolem AODV, kde není implementován predikční model.

L'utilisation intensive des services de données mobiles a de plus en plus augmenté la consommation de ressources sur les réseaux sans fil. La ressource principale utilisée pour la communication sans fil est le spectre de fréquence. À mesure que le trafic de données augmente brusquement, de nouvelles bandes du spectre de fréquences ne sont pas disponibles dans la même proportion, ce qui rend le spectre de fréquence de plus en plus rare et saturé. Plusieurs propositions ont été présentées pour optimiser l'allocation des canaux de fréquences afin d'atténuer les interférences entre les liaisons proches qui transmettent des données. Beaucoup d'entre eux utilisent un critère unique et ne considèrent pas le comportement de l'utilisateur pour guider le processus d'allocation de canaux. Les utilisateurs ont des cycles de routine et un comportement social. Ils passent au travail, à l'école, utilisent leurs appareils mobiles générant du trafic de données, et rencontrent des amis formant des groupes. Ces caractéristiques peuvent être explorées pour optimiser le processus d'allocation des canaux.Cette thèse présente une stratégie d'allocation de canaux pour les réseaux sans fil basée sur le comportement de l'utilisateur. Notre contribution principale consiste à considérer certaines caractéristiques du comportement de l'utilisateur, telles que la mobilité, le trafic et la popularité dans le processus d'allocation des canaux. De cette façon, nous priorisons l'allocation de canaux pour les nœuds qui resteront dans le réseau dans une fenêtre de temps future, avec un trafic plus élevé dans le réseau, et avec plus de popularité. Nous adoptons une approche distribuée qui permet de limiter le nombre de messages échangés dans le réseau tout en répondant rapidement aux changements de la topologie du réseau. Dans notre évaluation des performances, nous considérons des scénarios dans des réseaux ad hoc et véhiculaires, et nous utilisons des modèles de mobilité synthétique, tels que SLAW et Manhattan grid, et l'ensemble de données de traces de ville de Cologne. Dans les scénarios, nous comparons notre mécanisme avec différents types de techniques : une centralisée (nommée TABU), une autre aléatoire (nommée RANDOM), une avec la plus grande distance spectrale (appelée LD) et une avec un seul canal (appelée SC). Nous évaluons les métriques telles que le débit agrégé, le débit de livraison des paquets et le délai de bout en bout.Les simulations envisageant un scénario ad hoc avec un routage monodiffusion montrent que notre stratégie présente des améliorations en termes de débit de l'ordre de 14,81% par rapport à RANDOM et de 16,28% par rapport à l'allocation de canal LD. Dans le scénario véhiculaire, notre stratégie montre des gains de taux de livraison de paquets de l'ordre de 11,65% et de 17,18% par rapport aux méthodes RANDOM et SC, respectivement. Dans ces deux scénarios, la performance de notre stratégie est proche de la limite supérieure donnée par l'approche centralisée de TABU, mais avec l’envoie de moins des messages. / The intensive use of mobile data services has increasingly increased resource consumption over wireless networks. The main resource used for wireless communication is the frequency spectrum. As data traffic rises sharply, new bands of the frequency spectrum are not available in the same proportion, making the frequency spectrum increasingly scarce and saturated. Several proposals have been presented to optimize frequency channel allocation in order to mitigate interference between nearby links that are transmitting data. Many of them use a single criterion and does not consider the user behavior to guide the channel allocation process. Users have routine cycles and social behavior. They routinary move to work, to school, use their mobile devices generating data traffic, and they meet with friends forming clusters. These characteristics can be explored to optimize the channel allocation process.This thesis presents a channel allocation strategy for wireless networks based on user behavior. Our main contribution is to consider some characteristics of the user behavior, such as mobility, traffic, and popularity in the channel allocation process. In this way, we prioritize the channel allocation for the nodes that will remain in the network in a future time window, with higher traffic in the network, and with more popularity. We adopt a distributed approach that allows limiting the number of messages exchanged in the network while quickly responding to changes in the network topology. In our performance evaluation, we consider scenarios in ad hoc and vehicular networks, and we use some synthetic mobility models, such as SLAW and Manhattan grid, and the traces dataset of Cologne city. In the scenarios, we compare our mechanism with different types of approaches: i.e., a centralized (named TABU), a random (named RANDOM), a with largest spectral distance (named LD), and a with single channel (named SC). We evaluate metrics such as aggregated throughput, packet delivery rate, and end-to-end delay. Simulations considering ad hoc scenario with unicast routing show that our strategy presents improvements in terms of throughput at the order of 14.81% than RANDOM and 16.28% than LD channel allocation. In vehicular scenario, our strategy shows gains of packet delivery rate at the order of 11.65% and 17.18% when compared to RANDOM and SC methods, respectively. In both scenarios, the performance of our strategy is close to the upper bound search of the TABU centralized approach, but with lower overhead.

[pt] Com o crescimento da utilização das redes celulares para a transmissão de dados, as operadoras de telefonia móvel estão enfrentando um aumento dramático na utilização do recurso rádio para suprir esta nova necessidade. Com isto, estão sendo obrigadas a migrarem para novas tecnologias que propiciem uma alta eficiência espectral, permitindo assim uma melhor utilização do espectro disponível. Este trabalho descreve uma ferramenta de simulação desenvolvida para analisar o gerenciamento dos recursos de rádio, além de propor um novo algoritmo de alocação de canais de dados para sistemas móveis pessoais, permitindo a transmissão de voz e dados sobre a mesma interface aérea. É sabido que é extremamente difícil levar em conta todos os parâmetros que devem ser considerados em um sistema móvel real. Procurou-se então adotar os mais conhecidos modelos de propagação, de mobilidade e de tráfego de voz e de dados disponíveis na literatura, de forma a tentar aproximar a ferramenta de simulação o máximo possível do caso real. A contribuição deste trabalho é oferecer uma ferramenta de simulação para as redes GSM/HSCSD que permita a otimização da eficiência no uso do espectro disponível para transmissão. Esta ferramenta possibilita ao usuário, além de analisar a capacidade do sistema, o controle de potência e estratégias de handover, avaliar novos algoritmos de alocação de canal para o tráfego de voz e dados em conjunto. Ao final desta dissertação serão apresentados os resultados obtidos com a utilização de um novo algoritmo de alocação de canais para o tráfego de dados, além de realizar algumas outras simulações buscando maximizar a eficiência espectral do sistema utilizando deste novo algoritmo. / [en] Due to the increasing use of cellular networks for data transmission, mobile telephone operators are facing a dramatic raise in using radio resources to supply their demand. As a result, they are being forced to migrate to new technologies that provide high spectral efficiency, allowing an optimized use of available spectrum. This work describes the development of an advanced tool to analyze the operator management of radio transmission for personal mobile systems. The model was built considering well-known propagation, mobility, voice and data traffic for transmission assumptions, in order to approximate the developed tool to the real world mobile systems. The simulation tool is suited for GSM/HSCSD networks allowing engineers to optimize the efficient use of the available spectrum. It also permits the evaluation of system capacity as well as the analysis of power control and handover strategies. Another application exploited in this work is the investigation of resource allocation algorithms. A new algorithm for resource allocation in integrated voice and data environments was proposed and its performance was evaluated using the simulation tool.

[pt] Com o advento dos sistemas celulares de segunda e terceira gerações é esperado que as operadoras se vejam obrigadas a enfrentar um aumento dramático na carga de sinalização que trafega sobre a parte fixa da rede móvel. Apesar disso, são raros os provedores de serviços de comunicações móveis que possuem atualmente a capacidade de prever com relativa precisão o montante desse aumento. Este trabalho apresenta as etapas do desenvolvimento de uma ferramenta de simulação para análise de desempenho de redes de comunicação móvel celular com base na carga de sinalização gerada pelos procedimentos que a mantém em operação. A plataforma de simulação inclui um modelo de mobilidade e teletráfego para caracterizar o processo de geração dos cenários típicos de uma rede móvel celular e um modelo de retardos para representação da rede de sinalização. Ao final do estudo,são apresentados exemplos de aplicação da ferramenta na obtenção de resultados sobre gerência de status, gerência de localização, avaliação da carga de sinalização,dimensionamento da rede de sinalização e análise de desempenho para diferentes configurações de rede. / [en] The advent of second and third generation cellular systems make cellular operators face dramatic increase in the signaling traffic over the fixed part of the mobile network. In spite of this, rare mobile communications service providers are able to forecast the above mention increase and quantify it with reasonable precision. This work describes the development process of a simulation tool for performance analysis of cellular mobile network based on the signaling load generated by the procedures that keeps it working. The simulation platform inlcudes a mobility and teletraffic model to describe the generation process of cellular mobile networks tipical scenarios and a delay model to represent the signaling network. At the end, examples showing the application of the simulation tool to obtain results about status and location management, signaling load evaluation, signaling network planning and performance analysis for different network configurations are presented.