Quelques résultats en cryptographie symétrique, pour les modèles de confiance dans les réseaux ambiants et la sécurité dans les réseaux de capteurs sans fil

Soit un réseau comprenant des lignes de communication qui échouent indépendamment, dans lequel tous ou certains sites, appelés terminaux, doivent être capables de communiquer entre eux. Dans le modèle stochastique statique classique le réseau est représenté par un graphe probabiliste dont les arêtes sont présentes selon des probabilités connues. La mesure de fiabilité classique (CLR) est la probabilité que les terminaux appartiennent à la même composante connexe. Dans plusieurs contextes il est utile d'imposer la condition plus forte que la distance entre deux terminaux quelconques soit bornée supérieurement par un paramètre d. La probabilité que ça se produise est connue comme la fiabilité diamètre-bornée (DCR). Il s'agit d'une extension de la CLR. Les deux problèmes appartiennent à la clase NP-difficile de complexité ; le calcul exact n'est possible que pour les instances de taille limitée ou topologies spécifiques. Dans cette thèse, nous contribuons des résultats concernant le problème du calcul et l'estimation de la DCR. Nous étudions la complexité de calcul de cas particuliers, paramétré par le nombre de terminaux, noeuds et le paramètre d. Nous passons en revue des méthodes pour le calcul exact et étudions des topologies particulières pour lesquelles le calcul de la DCR a une complexité polynomiale. Nous présentons des résultats de base sur le comportement asymptotique de la DCR lorsque le réseau se développe comme un graphe aléatoire. Nous discutons sur l'impact de la contrainte de diamètre dans l'utilisation des techniques de Monte Carlo, et adaptons et testons une famille de méthodes basées sur le conditionnement de l'espace d'échantillonnage en utilisant des structures nommées d-pathsets et d-cutsets. Nous définissons une famille de mesures de performabilité qui généralise la DCR, développons une méthode de Monte Carlo pour l'estimer, et présentons des résultats expérimentaux sur la performance de ces techniques Monte Carlo par rapport à l'approche naïve. Finalement, nous proposons une nouvelle technique qui combine la simulation Monte Carlo et l'interpolation polynomiale pour les mesures de fiabilité.

Cette thèse porte sur l'allocation de ressources dans les réseaux mobiles ad hoc basés sur les protocoles ARQ Hybrides (HARQ), qui offrent une souplesse de déploiement rapide pour des communications à court terme dans le cadre d'applications militaires ou de futurs réseaux intelligents. L'OFDMA (Orthogonal Frequency Division Multiple Access) est considérée en particulier, en tant que solution prometteuse dans les standards de communication sans fil les plus récents. Bien qu'une coordination centralisée des communications soit rendue possible grâce à une organisation en clusters, il est toutefois difficile de remonter au coordinateur des informations fiables sur l'état du canal en vertu de la latence due à l'organisation de ce réseau. Ainsi les performances des liens seront renforcées par des mécanismes de retransmission HARQ, qui permettent de gérer les variations rapides du canal. L'objectif principal de cette thèse est l'allocation des ressources OFDMA dans les réseaux mobiles ad hoc basés sur les protocoles HARQ, en utilisant uniquement les statistiques à long terme du canal. Pour répondre à un besoin industriel, des schémas de modulation et de codage pratiques seront considérés en lieu et place des outils de capacité hérités de la théorie de l'information. En particulier, nous concevons et analysons de nouveaux algorithmes qui optimisent l'attribution de puissance, de largeur de bande, d'ordre de modulation et de rendement de codage, pour les mécanismes HARQ insérés dans le schéma multi-utilisateurs proposé. En raison de la présence de protocoles HARQ dans le réseau, une partie de la thèse est dédiée à l'étude des performances de l'HARQ que nous étendons à de nouveaux contextes.

L'efficacité énergétique constitue l'objectif clef pour la conception des protocoles de communication pour des réseaux de capteurs radio multi-sauts. Beaucoup d'efforts ont été réalisés à différents niveaux de la pile protocolaire à travers des algorithmes d'agrégation spatiale et temporelle des données, des protocoles de routage efficaces en énergie, et des couches d'accès au médium avec des mécanismes d'ordonnancement permettant de mettre la radio en état d'endormissement afin d'économiser l'énergie. Pour autant, ces protocoles utilisent de façon importante des paquets de contrôle et de découverte du voisinage qui sont coûteux en énergie. En outre, cela se fait très souvent sans aucune interaction entre les différentes couches de la pile. Ces travaux de thèse s'intéressent donc particulièrement à la problématique de l'énergie des réseaux de capteurs à travers des protocoles de routage et d'accès au médium. Les contributions de cette thèse se résument de la manière suivante : Nous nous sommes tout d'abord intéressés à la problématique de l'énergie au niveau routage. Dans cette partie, les contributions se subdivisent en deux parties. Dans un premier temps, nous avons proposé une analyse théorique de la consommation d'énergie des protocoles de routage des réseaux radio multi-sauts d'appréhender au mieux les avantages et les inconvénients des uns et des autres en présence des modèles de trafic variables, un diamètre du réseau variable également et un modèle radio qui permet de modéliser les erreurs de réception des paquets. À l'issue de cette première étude, nous sommes parvenus à la conclusion que pour être économe en énergie, un protocole de routage doit avoir des approches similaires à celle des protocoles de routage géographique sans message hello. Puis, dans un second temps, nous introduisons une étude de l'influence des stratégies de relayage dans un voisinage à 1 saut sur les métriques de performance comme le taux de livraison, le nombre de messages dupliqués et la consommation d'énergie. Cette étude est suivie par une première proposition de protocole de routage géographique sans message hello (Pizza-Forwarding (PF)) exploitant des zones de relayage optimisées et sans aucune hypothèse sur les propriétés du canal radio. Dans le but de réduire considérablement la consommation de PF, nous proposons de le combiner avec une adaptation d'un protocole MAC asynchrone efficace en énergie à travers une approche transversale. La combinaison de ces deux approches montre un gain significatif en terme d'économie d'énergie avec des très bon taux de livraison et cela quels que soient les scénarios et la nature de la topologique.

In this thesis we analyze the performance of communication networks using game theoretic approaches. The thesis is in two parts. The first part studies the performance of Ad hoc, cellular and transportation networks taking into consideration spatial effects. The second part studies economic issues in the communication networks related to the 'net neutrality' regulations. Here we study price competition and revenue sharing mechanisms between the network service providers. In the first part, we use Medium Access Control (MAC) game and Jamming game models to study the performance of a Mobile Ad hoc NETwork (MANET), and routing games to study the performance of a transportation network. In the cellular networks, we study the effect of reducing the spatial density of base stations on the amount of radiation to human body (green networking). We use tools from stochastic geometry to model spatial characters. We begin with the study of MAC game in a MANET where the nodes are noncooperative, and their locations form a Poisson point process. The nodes use Aloha protocol to access the channel, and choose their Medium Access Probability (MAP) such that it optimizes their utility. The utility of each node is defined as weighted difference between a performance metric (expected goodput or expected delay) and transmission costs. We first consider a scenario in which nodes can be priced for channel access. We show that by using a simple (linear) pricing mechanism and setting the price 'appropriately', the selfish behavior of the nodes can be used to achieve the same performance as social optima at equilibrium. In the case where channel access is free, we consider transmission energy costs and analyze the Price of Anarchy (PoA). For the game with goodput based utility, we show that the PoA is infinite at the price that achieves the global optimal goodput. We then study the performance of MANET in the presence of a Jammer while all the nodes cooperate by using a MAP that is assigned by a network an Operator. The objective of the Jammer is to degrade the spatial performance of the MANET by causing interference, whereas the objective of the Operator is to set a MAP to optimize it. We model the interaction between the Jammer and the Operator taking into account the transmission energy costs. We transform the resulting non zero sum game into a zero sum game by constructing an anti-potential, and show that for a given Jammer's transmission cost, if the nodes transmit at a power higher than certain threshold, then the Jammer has no incentive to jam, i.e., the nodes can operate as if there is no Jammer. Next, we consider cellular networks. We study energy saving by switching off a fraction of the base stations (BSs). This saving comes at some cost: the coverage is reduced, and the uplink transmission power of mobiles may increase. This implies exposure of the human body to stronger electromagnetic fields. We quantify this through the deactivation of base stations under the assumptions that the random location of base stations and mobiles form a Poisson processes. We consider the case of sparse network where the interference is negligible, and the case where it is non negligible. We observe that when the mobiles have no power constraints, unlike in the case of negligible interference, switching off base stations reduces the uplink power. Finally, we study a dynamic routing game by adding temporal dimension to the classical routing problem. We consider a scenario where each user have to ship a fixed demand on a shared link. The users can delay shipping their demand, but need to ship within T days, and each time they delay, a delay cost is incurred. We study the effect of delay costs on the user strategies by translating the time dimension into space dimension. Considering both atomic and non-atomic game models and polynomial congestion costs, we show that there exists a threshold time T T before which all users ship their demand at equilibrium, and during this period total demand on the link is decreasing in time. Further, we extend the analysis to the case when the demand of each user arrives randomly. In the second part of the thesis, we study economics aspects in communication networks. Representatives of several Internet access providers (ISPs) have expressed their wish to see a substantial change in the pricing policies in the Internet. In particular, they would like to see content providers (CPs) pay for use of the network, given the large amount of resources they use. This would be in clear violation of the "network neutrality" principle that had characterized the development of the wireline Internet. Our first goal here is to propose and study possible ways of implementing payments in a nonneutral network. We introduce a model that includes the users' behavior, the utilities of the ISP and of the CPs, and the monetary flow that involves the users, an ISP and CPs, and CP's revenues from advertisements. We consider various game models and obtain the resulting equilibrium prices. We show that if a regulator decides the amount of money that CPs pays to the ISP, rather it is decided by the ISP or the CPs, then it results in a favorable situation for all the players. Thus, we demonstrate the necessary for regulation of the monetary transactions between the ISP and the CPs in the nonneutral regime. The mechanism we propose for monetary interaction is based on the Nash bargaining solution. One of the central issues in the debate on network neutrality has been whether one should allow or prevent preferential treatment by an ISP. This raised the question of whether to allow an ISP to have exclusive agreement with a content provider (CP). We study the impact of exclusive contracts between a CP and an ISP in a nonneutral network. We consider a simple case of collusion where a CP and an ISP aim to maximize their sum of revenues, and show that such a collusion may not always be beneficial. We derive an explicit condition in terms of the advertisement revenues of the CPs which tells when a collusion is profitable to the colluding entities. Finally, we consider discrimination in the opposite direction, i.e., CP discriminating the ISPs. We derive models for studying the impact that the CP can have on the utilities of the ISPs by favoring one of them through exclusively revealing its private information on the demand. For a special case of linear demand function, we show that such preferential treatment always benefits the ISPs. However, if the CP charges the ISPs for providing the private information, then the ISP obtaining preferential treatment may not always gain. We then propose mechanisms based on weighted proportional fairness for deciding the payments between the CP and the ISP and compare them by proposing a new metric termed Price of Partial Bargaining.

Les terminaux mobiles (smartphones et tablettes) sont devenus les terminaux les plus populaires pour accéder à Internet. Cependant, l'écosystème incluant les terminaux mobiles est maintenu opaque à cause des intérêts financiers des différents acteurs : les concepteurs des systèmes d'exploitation et des applications, les opérateurs des "stores", et les FAI. Cette opacité est renforcée par le peu de contrôle qu'ont les utilisateurs sur les informations échangées par leur terminal. Pour résoudre ce problème d'opacité et de manque de contrôle, on a créé une plate-forme, Meddle, qui utilise la redirection de trafic des terminaux mobiles pour analyser et modifier ce trafic. Contrairement aux solutions qui nécessitent d'être implémentées sur le terminal, Meddle combine les techniques de VPN et de "middlebox" pour offrir une solution indépendante de l'OS, du FAI et de l'accès radio. On a utilisé Meddle pour des expérimentations contrôlées et pour une étude utilisateurs approvée par un IRB. On a observé que des applications populaires sous iOS et Android exposaient des informations personnelles dans le traffic réseau en clair et chiffré. On a ensuite exploité Meddle pour prévenir ces fuites d'informations privées. On a également utilisé Meddle pour étudier les caractéristiques réseaux du trafic vidéo sur Internet. On a trouvé que ce trafic dépend fortement du type de terminal, de l'application utilisée pour regarder la vidéo (application native ou navigateur Web) et du contenant (HTML5, Flash, Silverlight). Ce résultat montre qu'un changement dans le terminal, l'application ou le contenant peut avoir un impact important sur le réseau.

La nécessité de maximiser la durée de vie du réseau sans fil dans les réseaux ad hoc et en particulier dans les réseaux de capteurs sans fil nécessite l'utilisation d'algorithmes d'efficacité énergétique. Motivée par le fait qu'un noeud consomme le moins d'énergie lorsqu'il est en veille, nous réalisons l'efficacité énergétique vi des algorithmes d'ordonnancement des activités des noeuds. Les noeuds reçoivent des slots temporels durant lesquels ils peuvent transmettre et ils peuvent éteindre leur radio quand ils ne sont ni en train de transmettre, ni en train de recevoir. Par rapport au TDMA classique, l'utilisation de la bande passante est optimisée: deux noeuds interférents ne partagent pas les mêmes slots. Dans notre travail sur l'ordonnancement, deux cas sont étudiés. Tout d'abord, lorsque les nœuds nécessitent le même temps d'accès au canal, nous utilisons le coloriage des nœuds. Deuxièmement, lorsque les nœuds requièrent des débits hétérogènes, nous utilisons une allocation de slots " traffic aware ". Contrairement à la majorité des travaux antérieurs, nous généralisons la définition du coloriage des noeuds et les problèmes d'attribution des slots. En effet, nous considérons que la distance maximale entre deux nœuds interférents est un paramètre de ces problèmes. Nous prouvons qu'ils sont NP-complets, ce qui rend inévitable l'utilisation des heuristiques dans la pratique. Une directive centrale de cette thèse est de concevoir des solutions auto-adaptatives. Cette adaptabilité concerne de nombreux aspects tels que la mission confiée par l'application, l'hétérogénéité des demandes de trafic de nœuds, la densité du réseau, de la régularité de la topologie du réseau, et la non fiabilité des liens sans fil.

Beaucoup de protocoles et d'applications nécessitent un mécanisme de découverte pour permettre à des clients de localiser un ou plusieurs noeuds spécifiques engagés dans la même communication. Ces noeuds spécifiques qui peuvent être des routeurs ou des machines hôtes sont usuellement appelés agents. Il n'existe pas actuellement de protocole de recherche d'agent prêt à remplir ce service au niveau de la couche réseau. Chaque protocole implémente habituellement sa propre solution. En particulier les protocoles multipoints utilisent souvent une technique de recherche appelés recherche par anneaux croissants. Cette méthode recherche des noeuds spécifiques dans toutes les directions et donc utilise beaucoup de bande passante. Cependant une recherche typique peut habituellement se limiter à une direction spécifique. Pour répondre à ce problème, nous proposons un service de recherche au niveau réseau en remplacement de la recherche par anneaux croissants. Ce service est basé sur un protocole de diffusion multipoint orientée de façon à obtenir une efficacité plus élevée que celle de la recherche par anneaux croissants. Le principe de la diffusion multipoint orientée est de canaliser la diffusion multipoint des paquet de recherche en direction d'un noeud spécial impliqué dans la communication de façon à balayer seulement une zone limitée du réseau. Nous décrivons le service et le protocole dynamique de recherche d'agent au niveau réseau ainsi que le protocole de diffusion multipoint orientée et nous fournissons des résultats de simulations comparatifs entre notre service et la recherche par anneaux croissants.

L'Internet est devenu sans conteste en trois décades le support matériel majeur de l'ère de l'information. Durant cette courte période, il a subi deux mutations importantes. Tout d'abord, il a subi une mutation de taille : de quelques dizaines de systèmes interconnectés suivant une topologie fixée et bien connue, l'Internet est passé à une taille phénoménale de plus de 285 millions d'hôtes suivant une topologie désormais à dimension libre dûe au fait que son développement n'est plus centralisé. De plus, il a subi une mutation de forme : nous sommes passés des gros systèmes interconnectés par de simples lignes téléphoniques à des ordinateurs personnels mobiles interconnectés par des technologies radio en bordure de réseau et par des routeurs gigabits reliés par fibre optique en coeur de réseau. Ces deux mutations entraînent deux défis importants pour les chercheurs qui oeuvrent à l'amélioration de l'Internet. Premièrement, il est nécessaire de connaître avec le plus de précision possible, la topologie de l'Internet. Seules des méthodes macroscopiques et statistiques permettent désormais de connaître cette topologie car plus personne n'a autorité sur l'organisation et l'expansion du réseau Internet. De plus, étant donné sa dynamicité, il est aussi souhaitable que cette topologie soit mise à jour fréquemment. Deuxièmement, l'évolution rapide des technologies a fait que les paradigmes qui sous-tendaient à la création des protocoles initiaux de l'Internet ne sont plus valables à l'heure actuelle. Les notions de mobilité, de sécurité et de diffusion quasi-inexistantes à l'origine sont désormais ardemment souhaitées par les utilisateurs mais difficiles à mettre en oeuvre dans les protocoles actuels. Il faut donc trouver les moyens d'offrir ces nouvelles fonctionnalités en conservant les propriétés initiales des protocoles qui ont fait le succès d'Internet. Dans ce mémoire d'habilitation, nous présentons des contributions qui tentent de répondre à certains aspects de ces deux défis majeurs. Nous nous concentrons tout particulièrement sur la cartographie de l'Internet, le stockage d'états dans les routeurs exécutant des protocoles multipoints, l'implémentation de fonctionnalités réseaux dans les hôtes et la conception de réseaux recouvrants.

Les réseaux sans-fil multisaut représentent une partie essentielle du futur Internet. Depuis quelques années, nous observons une convergence vers des réseaux tout IP. En particulier, l'Internet des Choses a pour but d'interconnecter des objets intelligents (capteurs, actionneurs, tags RFID) directement à Internet. De même, les réseaux maillés peuvent servir de dorsale sans-fil collectant tout ce trafic. Ce type de réseau est essentiel pour disséminer l'intelligence et décentraliser les décision par exemple dans les villes intelligentes. Le fil conducteur de tous mes travaux explore l'algorithmie distribuée et les protocoles pour les réseaux radio multisaut. Je me suis principalement focalisé sur l'accès au médium : que ce soit dans les réseaux de capteurs ou dans les réseaux maillés, les défis se ressemblent. Les solutions suivent des démarches similaires, même si naturellement les réseaux de capteurs intègrent une contrainte énergétique supplémentaire. Parce que l'accès au médium n'est pas suffisant en tant que tel, j'ai également étudié l'exploitation efficace de ce partage d'accès, en regardant notamment comment construire des routes efficaces au dessus de ces solutions. Les travaux que j'ai développés avec tous les chercheurs ayant accepté de travailler avec moi s'articulent autour de 3 grands axes : - l'organisation des transmissions au sein de la couche MAC pour une meilleure efficacité, - l'exploitation de plusieurs canaux en parallèle pour solutionner plusieurs problèmes dus aux topologies multisaut - l'optimisation conjointe MAC / routage.