L’utilisation des communications multi-canaux au niveau des protocoles MAC (MAC multi-canaux) dans les réseaux sans fil peut améliorer significativement le débit du réseau par rapport aux protocoles MAC mono-canal en permettant à plusieurs transmissions concurrentes d’avoir lieu simultanément sans interférence sur différents canaux non recouverts. Cependant, l’environnement multicanaux ajoute une nouvelle dimension aux protocoles MAC qui nécessite un nouveau mécanisme appelé "le mécanisme d’allocation des canaux" pour coordonner l’utilisation des canaux. Le rôle de ce mécanisme est de permettre aux nœuds de s’accorder sur le canal qui doit être utilisé et à quel moment pour la transmission de données dans un contexte distribué. L’absence de ce mécanisme ou une mauvaise coordination de l’utilisation des canaux peut produire l’effet inverse de celui recherché. Ainsi, l’efficacité d’un protocole MAC multi-canaux dépend strictement de l’efficacité du mécanisme d’allocation des canaux, qui par ailleurs, doit offrir les garanties nécessaires au fonctionnement de la communication multi-canaux. Dans cette thèse, nous nous intéressons à la modélisation, l’analyse et la conception de nouveaux protocoles MAC multi-canaux dans les réseaux sans fil. Dans un premier temps, nous nous focalisons sur la spécification formelle et la vérification des propriétés fondamentales inhérentes aux activités de l’allocation des canaux et son impact sur le transfert de données des principales approches MAC multi-canaux proposées dans la littérature. Dans un second temps, nous visons à proposer, modéliser et à analyser formellement deux nouveaux protocoles MAC multicanaux résultants de l’analyse qualitative réalisée. Enfin, une étude quantitative et comparative est menée afin d’analyser les performances des protocoles proposés en terme de débit et d’impact du temps de commutation entre les canaux. / The use of multi-channel communications in MAC protocols (multi-channel MAC) for wireless networks can significantly improve the network throughput compared with single channel MAC protocols since concurrent transmissions can take place simultaneously on distinct non-overlapping channels without interfering. However, due to the multi-channel environment, a novel issue must be addressed in MAC protocols, which is called "the channel assignment mechanism" in order to coordinate the channels access. The role of this mechanism is to enable nodes to agree on which channel should be used and when for data transmission in a distributed way. The absence of this mechanism or a bad coordination of the channel usage can incur the opposite effect to that intended. Thus, the efficiency of a multi-channel MAC protocol depends strictly on the efficiency of the channel assignment mechanism, which also must provide the guarantees necessary to the good behavior of the multi-channel communications. In this thesis, we focus on the modeling, analysis, and design of new multi-channel MAC protocols in wireless networks. Firstly, we focus on the formal specification and verification of fundamental properties inherent to the activities of the channel assignment and its impact on the data transfer for the main multi-channel MAC approaches proposed in the literature. Secondly, we aim to propose, model and analyze formally two new multichannel MAC protocols, resulting from the qualitative analysis conducted. Finally, a quantitative and comparative study is conducted to analyze the performance of the proposed protocols in terms of the throughput and the impact of the switching time between channels.

La multiplication de l'usage des équipements connectables à un réseau sans fil tels que les smartphones ou les objets connectés peut être mise à profit pour construire des réseaux reposant sur des communications de proximité : les appareils communiquent directement entre eux, sans le support d'une infrastructure centrale. On parle de réseau ad hoc. Ce type de réseau sans infrastructure est exploité dans de nombreux domaines comme le militaire ou la gestion de catastrophes naturelles. Pour certains cas d'utilisation, le passage à l'échelle, c'est-à-dire la capacité à fonctionner avec la croissance de la taille du réseau, est une propriété indispensable. Dans cette thèse, nous nous intéressons à la problématique du routage sous l'aspect du passage à l'échelle. Le routage est la fonction responsable de l'acheminement des données au sein du réseau. Pour cela, des informations de contrôle sont échangées entre les nœuds du réseau. Mais le trafic associé à ces échanges peut être un frein pour passer à l'échelle. Afin de le réduire, nous proposons d'agréger les informations concernant des nœuds géographiquement proches. Dans un premier temps, nous mettons en place une structuration de la zone de déploiement du réseau en régions hiérarchiques. Ces régions servent d'agrégateur de nœuds à travers un adressage de ces derniers selon les régions auxquelles ils appartiennent. Par la suite, nous proposons un protocole de routage combinant les approches topologique et géographique. Il s'agit, pour un nœud donné, de maintenir des routes menant, d’une part, vers d'autres nœuds dans un voisinage proche et, d'autre part, vers des zones géographiques de plus en plus étendues au fur et à mesure de l'éloignement. Cette dernière propriété est obtenue en profitant de la structuration hiérarchique précédente des zones d'agrégation. Les résultats montrent la faculté de notre proposition à monter à grande échelle par rapport aux protocoles de routage ad hoc classique et aussi sa capacité à adresser les problèmes propres aux protocoles de routage purement géographique. / The widespread use of wireless devices such as smartphones and connected objects leads to an increasing emergence of infrastructure-less networks relying on device-to-device communication: ad hoc networks. Applications of this type of network vary widely from military operations to emergency situations. Scalability is a key property for some use cases involving a large number of devices, also called nodes. We mean by scalability, the ability of the network to increase in size without drastic loss of performance and with a cost-effective network maintenance. In this thesis, we focus on the scalability from a routing perspective. Routing handles the delivery of data packets from a source to a destination across the network. This is achieved by the exchange of information between nodes. The corresponding traffic may represent a break for scalability in presence of numerous nodes. In this work, we propose an aggregation of routing information. First, we partition the deployment area into smaller hierachical regions based on geographical coordinates. Nodes are assigned hierachical address depending on the regions they are located in. Then, we propose a mixed topological and geographical-based routing protocol. A node maintains precise routing information to other nodes in close proximity and geographically aggregate information for nodes at greater distances. Regions are the units of nodes aggregation. The further the nodes are, the larger the regions referring to them are. The results show that our proposition outperforms regular ad hoc routing in terms of scalability and addresses more efficiently geographical routing-related issues compared to classical geographical routing.

Les systèmes de communications mobiles ont considérablement évolué durant ces dernières années. Ce fait a encouragé le déploiement de plusieurs systèmes ou réseaux cellulaires multi technologique. La qualité de service (QoS) offerte aux utilisateurs mobiles s’améliore d’un système à l’autre. Les systèmes de troisième génération (3G), comme l’UMTS, offrent une meilleure qualité de service par rapport à celle offerte par ceux de deuxième génération (2G), comme le GSM. Pour exemple, les systèmes de 3.5G (HSDPA) améliorent le débit du réseau de 3G sur le lien descendant afin de répondre aux exigences des nouveaux services. De plus, les réseaux de quatrième génération (4G), comme le WiMAX (IEEE802.16e) permettent, quant à eux, d’élargir la couverture cellulaire tout en offrant un débit supérieur. Cette nouvelle évolution améliore encore l’accessibilité aux services de l’Internet. La migration des services de l’Internet vers les réseaux mobiles, constitue un enjeu majeur de recherche en télécommunications. La thèse se divise en deux objectifs principaux ; le premier consiste à calculer et à évaluer les performances du système UMTS-WCDMA. Deux approches sont utilisées, l’approche exacte de l’analyse spectrale, et l’approche approximative de la perturbation singulière. Le deuxième objectif propose de nouveaux mécanismes de contrôle d’admission prenant en considération la mobilité intra et inter cellulaires des utilisateurs dans la gestion de la ressource radio. Ces mécanismes d’allocation de ressource concernent plus particulièrement les réseaux HSDPA et WiMAX. Ils se basent principalement sur les schémas de modulation et de codage adaptatif AMC (Adaptive Modulation and Coding) : la zone géographique est subdivisée en plusieurs régions concentriques. Avec nos mécanismes d’allocation des ressources, chaque appel accepté par le système voit son débit initial maintenu, et ce, indépendamment de la position de l’utilisateur dans la cellule / The mobile communication systems evolved considerably in the last few years. This fact encouraged the deployment of several systems or cellular networks in multi technological environment. The Quality of Service (QoS) offered to the mobile users improves from one system to another one. The systems of third generation (3G), like UMTS, offer a better quality of service compared to that offered by those of second generation (2G), like the GSM. For example, the systems of 3.5G (HSDPA) improve the throughput of the network of 3G in the downlink direction according to the requirements of the new services. Moreover, the networks of fourth generation (4G), like WiMax (IEEE802.16e), as for them, make it possible to widen the cover of the base station while offering a very important throughput in which supports the next generation applications or services already offered by the Internet. This new evolution still improves accessibility with the services of the Internet. The migration of the services of the Internet towards the mobile networks, constitutes a major stake of research in telecommunications. The thesis is divided into twomain aims. The first consists to compute the systemcapacity and to evaluate the performances of the UMTS-WCDMA system. Two approaches are used, one is of the spectral analysis, and other one is an approximation of the singular perturbation. The second goal of this thesis is to propose and develop the new mechanisms of call admission control (CAC) for HSDPA and IEEE802.16e networks based on the AMC (Adaptive Modulation and Coding) scheme : the geographical area of the cell is subdivided into several concentric regions. These CAC mechanisms maintain a same QoS (constant bit rate) for all users anywhere in the area of the cell and give priority to migrating or handoff calls by reserving the guard bandwidth than a new call in the intra cell and inter cell mobilities

Dans ce travail, nous nous intéressons à une topologie pour les réseaux de capteurs sans fil. Un réseau de capteurs sans fil peut être modélisé comme un graphe non orienté G = (V,E). Chaque sommet de V représente un capteur et une arête e = {u, v} dans E indique une transmission directe possible entre deux capteurs u et v. Contrairement aux dispositifs filaires, les capteurs sans fil ne sont pas a priori agencé en réseau. Une topologie doit être créée en sélectionnant des noeuds "dominants" qui vont gérer les transmissions. Les architectures qui ont été examinées dans la littérature reposent essentiellement sur les ensembles dominants connexes et les ensembles dominants faiblement connexes. Cette étude est consacrée aux ensembles indépendants faiblement connexes. Un indépendant S ⊂ V est dit faiblement connexe si le graphe GS = (V, [S, V \S]) est connexe, où [S, V \S] est l’ensemble des arêtes e = {u, v} de E avec u ∈ S et v ∈ V \S. Une topologie basée sur les ensembles faiblement connexes permet de partitionner l’ensemble des capteurs en trois groupes, les esclaves, les maîtres et les intermédiaires. Les premiers effectuent les mesures, les seconds rassemblent les données collectées et les troisièmes assurent les communications inter-groupes. Nous donnons d’abord quelques propriétés de cette structure combinatoire lorsque le graphe non orienté G est connexe. Puis nous proposons des résultats de complexité pour le problème de la recherche de l’indépendant faiblement connexe de cardinalité minimale (MWCISP). Nous décrivons également un algorithme d’énumération exact de complexité O∗(1.4655|V |) pour le MWCISP. Des tests numériques de cette procédure exacte sont présentés. Nous formulons ensuite le MWCISP comme un programme linéaire en nombres entiers. Le polytope associé aux solutions de ce problème est complètement caractérisé lorsque G est un cycle impair. Nous étudions des opérations de composition de graphes et leurs conséquences polyédrales. Nous introduisons des inégalités valides notamment les contraintes dites de multibord. Par la suite, nous développons un algorithme de coupes et branchement sous CPLEX pour résoudre ce problème en utilisant des heuristiques pour la séparation de nos familles de contraintes. Des résultats expérimentaux de ce programme sont exposés. / In this work, we focus on a topology for Wireless Sensor Networks (WSN). A wireless sensor network can be modeled as an undirected graph G = (V,E). Each vertex of V represents a sensor and an edge e = {u, v} in E implies a direct transmission between the two sensors u and v. Unlike wired devices, wireless sensors are not a priori arranged in a network. Topology should be made by selecting some sensor as dominators nodes who manage transmissions. Architectures that have been studied in the literature are mainly based on connected dominating sets and weakly connected dominating sets.This study is devoted to weakly connected independent sets. An independent set S ⊂ V is said Weakly Connected if the graph GS = (V, [S, V \S]) is connected, where [S, V \S] is the set of edges with exactly one end in S. A sensor network topology based on weakly connected sets is partition into three groups, slaves, masters and bridges. The first performs the measurements, the second gathers the collected data and the later provides the inter-group communications. We first give some properties of this combinatorial structure when the undirected graph G is connected. Then we provide complexity results for the problem of finding the minimum weakly connected independent set problem (MWCISP). We also describe an exact enumeration algorithm of complexity O∗(1.4655|V |) (for the (MWCISP)). Numerical tests of this exact procedure are also presented. We then present an integer programming formulation for the minimum weakly connected independent set problem and discuss its associated polytope. Some classical graph operations are also used for defining new polyhedra from pieces. We give valid inequalities and describe heuristical separation algorithms for them. Finally, we develop a branch-and-cut algorithm and test it on two classes of graphs.

Les réseaux sans fil 802.11 sont en train d'être considérés comme étant la pierre angulaire des systèmes de communication autonomes. En permettant aux usagers de communiquer les uns avec les autres avec les stations de base fixées a des endroits bien précis par l'intermédiaire de protocoles de communication comme les protocole de routage ad hoc. Le standard IEEE 802.11 propose des spéciations pour les deux couches basses (MAC et Physique) du modelé OSI. La couche MAC (Medium Access Control) introduit deux mécanismes d'accès au médium sans fil qui sont différents l'un de l'autre. Le mécanisme DCF (accès au canal distribue ou Distributed Coordination Function), l'accès au canal s'exécute dans chaque station sans faire appel à une unité centrale. Le mécanisme PCF (Point Coordination Function), contrairement au mécanisme DCF l'accès au canal se fait à l'aide d'une unité centrale. Le mécanisme le plus utilise par la norme 802.11 est DCF vu qu'il ne nécessite pas d'infrastructure au déploiement. Pour améliorer la qualité de service dans les réseaux sans multi- sauts, cette thèse aborde cette problématique dans deux couches de la pile protocolaire, à savoir la couche routage et la couches MAC. Elle améliore le routage a QoS en utilisant le protocole de routage a état de lien optimisé (OLSR) et améliore aussi l'efficacité de l'accès au médium sans fil lors du fonctionnement de la couche MAC en mode le plus courant DCF. Pour l'amélioration de routage, nous proposons une approche basée sur le graphe de conflit pour l'estimation de la bande passante partagée entre les nœuds adjacents. Pour la couche MAC, nous proposons un nouveau schéma de Backoff nomme l'algorithme Backoff de Padovane (PBA), pour améliorer l'efficacité de l'accès au médium sans fil dans les réseaux sans fil mobiles Ad Hoc (MANETs). / IEEE 802.11 based wireless networks are considered the cornerstone of autonomous communication systems. These networks allow users to communicate with each others via base stations deployed in specic locations through a set of dedicated communication protocols like Ad Hoc routing protocols. The IEEE 802.11 standard proposes specications for both physical and MAC layers of the OSI model. MAC layer denes dierent types of access to the wireless medium as explained below. The DCF (Distributed Coordination Function) mechanism, in which the access to the medium is executed localy in each station. The PCF (Point Coordination Function) method, unlike DCF mechanism the access the medium is managed by a central unit. The most widespread mechanism among them is the DCF mode as it does not require any infrastructure deployment. To improve the Quality of Service (QoS) oered to the dierent applications in multihop wireless networks, this thesis proposes original solutions to enhance the eciency of certain protocols in two dierent layers of OSI, i.e., routing and MAC layers. More specically, our proposed solutions enable higher eciency of OLSR protocol and ensure more ecient usage of the available bandwidth through the designed Padovan based medium access scheme operating in DCF mode. The routing approach used in OLSR is improved by applying the conict graphs to acquire more accurate estimation of the bandwidth shared with the adjacent nodes. At MAC layer, the number of collisions in dense networks is signicantly reduced by designing new backo scheme dubbed Padovan Backo Algorithm (BEB).

Le protocole IEEE 802.11, basé sur les principes CMSA/CA, est largement déployé dans les communications sans fil actuelles, principalement en raison de sa simplicité et sa mise en œuvre à faible coût. Une utilisation intéressante de ce protocole peut être trouvée dans les réseaux sans fil multi-sauts, où les communications entre les nœuds peuvent impliquer l'emploi de nœuds relais. Une topologie simple de ces réseaux impliquant une source et une destination est communément connue en tant que chaîne. Dans cette thèse, un modèle hiérarchique, composé de deux niveaux, est présenté dans le but d'analyser la performance associée à ces chaînes. Le niveau supérieur modélise la topologie de la chaîne et le niveau inférieur modélise chacun de ses nœuds. On estime les performances de la chaîne, en termes de débit obtenu et de pertes de datagrammes, en fonction de différents modes de qualité du canal. En termes de précision, le modèle offre, en général, des résultats justes. Par ailleurs, le temps nécessaire à sa résolution reste très faible. Le modèle proposé est ensuite appliqué aux chaînes avec deux, trois et quatre nœuds, en présence de stations cachées potentielles, de tampons finis et d'une couche physique non idéale. Par ailleurs, l'utilisation du modèle proposé permet de mettre en évidence certaines propriétés inhérentes à ces réseaux. Par exemple, on peut montrer que la chaîne présente un maximum de performance (en ce qui concerne le débit atteint) en fonction du niveau de charge de du système, et que cette performance s'effondre par l'augmentation de cette charge. Cela représente un comportement non trivial des réseaux sans fil et il ne peut pas être facilement identifié. Cependant, le modèle capture cet effet non évident. Finalement, certains impacts sur les performances des chaînes occasionnés par les mécanismes IEEE 802.11 sont analysés et détaillés. La forte synchronisation entre les nœuds d'une chaîne et comment cette synchronisation représente un défi pour la modélisation de ces réseaux sont décrites. Le modèle proposé permet de surmonter cet obstacle et d'assurer une évaluation facile des performances de la chaîne / The IEEE 802.11 protocol, based on the CMSA/CA principles, is widely deployed in current communications, mostly due to its simplicity and low cost implementation. One common usage can be found in multi-hop wireless networks, where communications between nodes may involve relay nodes. A simple topology of these networks including one source and one destination is commonly known as a chain. In this thesis, a hierarchical modeling framework, composed of two levels, is presented in order to analyze the associated performance of such chains. The upper level models the chain topology and the lower level models each of its nodes. It estimates the performance of the chain in terms of the attained throughput and datagram losses, according to different patterns of channel degradation. In terms of precision, the model delivers, in general, accurate results. Furthermore, the time needed for solving it remains very small. The proposed model is then applied to chains with 2, 3 and 4 nodes, in the presence of occasional hidden nodes, finite buffers and non-perfect physical layer. Moreover, the use of the proposed model allows us to highlight some inherent properties to such networks. For instance, it is shown that a chain presents a performance maximum (with regards to the attained throughput) according to the system workload level, and this performance collapses with the increase of the workload. This represents a non-trivial behavior of wireless networks and cannot be easily identified. However, the model captures this non-trivial effect. Finally, some of the impacts in chains performance due to the IEEE 802.11 mechanisms are analyzed and detailed. The strong synchronization among nodes of a chain is depicted and how it represents a challenge for the modeling of such networks. The proposed model overcomes this obstacle and allows an easy evaluation of the chain performance

Fréquemment exploités pour venir en complément aux réseaux mobiles traditionnels, les réseaux sans-fil multi-sauts, aussi appelés réseaux ad-hoc, sont particulièrement mis à profit dans le domaine des communications d'urgence du fait de leur capacité à s'affranchir de toute infrastructure. Néanmoins, la capacité de ces réseaux étant limitée dès lors que le nombre d'utilisateurs augmente, la communauté scientifique s'efforce à en redéfinir les contours afin d'étendre leur utilisation aux communications civiles. La gestion des interférences, considérée comme l'un des principaux défis à relever pour augmenter les débits atteignables dans les réseaux sans-fil multi-sauts, a notamment connu un changement de paradigme au cours des dernières années. Alors qu'historiquement cette gestion est régie par les protocoles de la couche d'accès dont l'objectif consiste à éviter les interférences entre utilisateurs, il est désormais possible, grâce à différentes techniques avancées de communication numérique, de traiter ces interférences, et même de les exploiter. Ces techniques de transmission, dites techniques de gestion des interférences, viennent alors concurrencer les mécanismes d'ordonnancement traditionnels en autorisant plusieurs transmissions simultanées et dans la même bande de fréquence vers un même récepteur. Dans cette thèse, nous nous intéressons à l'une de ces techniques, le Physical-Layer Network Coding (PLNC), en vue de son intégration dans des réseaux ad-hoc composés de plusieurs dizaines de nœuds. Les premiers travaux se concentrant principalement sur des petites topologies, nous avons tout d'abord développé un framework permettant d'évaluer les gains en débit à large échelle du PLNC par rapport à des transmissions traditionnelles sans interférence. Motivés par les résultats obtenus, nous avons ensuite défini un nouveau cadre d'utilisation à cette technique visant à élargir sa sphère d'application. Le schéma de PLNC proposé, testé à la fois sur de vrais équipements radio et par simulation, s'est alors révélé offrir des gains significatifs en débit et en fiabilité en comparaison aux solutions existantes. / Frequently used to complement the traditional mobile networks, multi-hop wireless networks, also referred to as ad-hoc networks, are particularly useful in emergency situations due to the fact that they do not rely on any infrastructure. Nevertheless, as the capacity of such networks does not scale with the number of users, the scientific community has strived to rethink their use in order to extend their application to civil communications. For instance, long considered as one of the most formidable challenges in multi-hop wireless networks, interference management has recently undergone a paradigm shift. While interference management is traditionally carried out by the access layer protocols whose objective is to avoid interference between users, it is now possible to exploit the interference thanks to new advanced communication techniques. These transmission techniques, so-called interference management techniques, go against the communication paradigm underlying existing scheduling mechanisms by allowing multiple simultaneous transmissions to a common receiver in the same frequency band. In this thesis, we focus on one of these techniques, namely the Physical-Layer Network (PLNC), with the objective of integrating it in ad-hoc networks. Mostly studied from both the theoretical and practical perspective in small topologies, we first design a framework for quantifying the large-scale PLNC gains over the traditional interference-free transmissions. Driven by the obtained results, we introduce a solution to increase the PLNC sphere of operation in large multi-hop wireless networks. Our comprehensive evaluation methodology, including experimental testbed validations for credibility, as well as realistic simulations, show that the proposed PLNC scheme brings important gains in terms of throughput and reliability when compared to state-of-the-art approaches.

Durant ces dernières années, nous avons observe une expansion progressive et continue des réseaux mobile sans-fil centres sur l’être humain. L’apparition de ces réseaux a encouragé les chercheurs à réfléchir à de nouvelles solutions pour assurer une évaluation efficace et une conception adéquate des protocoles de communication. En effet, ces réseaux sont sujets à de multiples contraintes telles que le manque d’infrastructure, la topologie dynamique, les ressources limitées ainsi que la qualité de service et la sécurité des informations précaires. Nous nous sommes spécialement intéressés à l’aspect dynamique du réseau et en particulier à la mobilité humaine. La mobilité humaine a été largement étudiée pour pouvoir extraire ses propriétés intrinsèques et les exploiter pour des approches plus adaptées à cette mobilité. Parmi les propriétés les plus intéressantes soulevées dans la littérature, nous nous sommes focalisés sur l’impact des interactions sociales entre les entités du réseau sur la mobilité humaine et en conséquence sur la structure du réseau. Pour recueillir des informations structurelles sur le réseau, plusieurs métriques et techniques ont été empruntées de l’analyse des réseaux sociaux (SNA). Cet outil peut être assimilé à une autre alternative pour mesurer des indicateurs de performance du réseau. Plus précisément, il extrait des informations structurelles du réseau et permet aux protocoles de communication de bénéficier d’indications utiles telles que la robustesse du réseau, les nœuds centraux ou encore les communautés émergentes. Dans ce contexte, la SNA a été largement utilisée pour prédire les liens dans les réseaux sociaux en se basant notamment sur les informations structurelles. Motivés par l’importance des liens sociaux dans les réseaux mobiles sans-fil centres sur l’être humain et par les possibilités offertes par la SNA pour prédire les liens, nous nous proposons de concevoir la première méthode capable de prédire les liens dans les réseaux sans-fil mobiles tels que les réseaux ad-hoc mobiles (MANETs) et les réseaux tolérants aux délais (DTNs). Notre proposition suit l’évolution de la topologie du réseau sur T périodes à travers un tenseur (en ensemble de matrices d’adjacence et chacune des matrices correspond aux contacts observés durant une période bien spécifique). Ensuite, elle s’appuie sur le calcul de la mesure sociométrique de Katz pour chaque paire de nœuds pour mesurer l’étendue des relations sociales entre les différentes entités du réseau. Une telle quantification donne un aperçu sur les liens dont l’occurrence est fortement pressentie à la période T+1 et les nouveaux liens qui se créent dans le futur sans pour autant avoir été observés durant le temps de suivi. Pour attester l’efficacité de notre proposition, nous l’appliquons sur trois traces réelles et nous comparons sa performance à celles d’autres techniques de prédiction de liens présentées dans la littérature. Les résultats prouvent que notre méthode est capable d’atteindre le meilleur niveau d’efficacité et sa performance surpasse celles des autres techniques. L’une des majeures contributions apportées par cette proposition met en exergue la possibilité de prédire les liens d’une manière décentralisée. En d’autres termes, les nœuds sont capables de prédire leurs propres liens dans le futur en se basant seulement sur la connaissance du voisinage immédiat (voisins à un et deux sauts). En outre, nous sommes désireux d’améliorer encore plus la performance de notre méthode de prédiction de liens. Pour quantifier la force des relations sociales entre les entités du réseau, nous considérons deux aspects dans les relations : la récence des interactions et leur fréquence. À partir de là, nous nous demandons s’il est possible de prendre en compte un troisième critère pour améliorer la précision des prédictions […] / During the last years, we have observed a progressive and continuous expansion of human-centered mobile wireless networks. The advent of these networks has encouraged the researchers to think about new solutions in order to ensure efficient evaluation and design of communication protocols. In fact, these networks are faced to several constraints as the lack of infrastructure, the dynamic topology, the limited resources and the deficient quality of service and security. We have been interested in the dynamicity of the network and in particular in human mobility. The human mobility has been widely studied in order to extract its intrinsic properties and to harness them to propose more accurate approaches. Among the prominent properties depicted in the literature, we have been specially attracted by the impact of the social interactions on the human mobility and consequently on the structure of the network. To grasp structural information of such networks, many metrics and techniques have been borrowed from the Social Network Analysis (SNA). The SNA can be seen as another network measurement task which extracts structural information of the network and provides useful feedback for communication protocols. In this context, the SNA has been extensively used to perform link prediction in social networks relying on their structural properties. Motivated by the importance of social ties in human-centered mobile wireless networks and by the possibilities that are brought by SNA to perform link prediction, we are interested by designing the first link prediction framework adapted for mobile wireless networks as Mobile Ad-hoc Networks (MANETs) and Delay/Disruption Tolerant Networks (DTN). Our proposal tracks the evolution of the network through a third-order tensor over T periods and computes the sociometric Katz measure for each pair of nodes to quantify the strength of the social ties between the network entities. Such quantification gives insights about the links that are expected to occur in the period T+1 and the new links that are created in the future without being observed during the tracking time. To attest the efficiency of our framework, we apply our link prediction technique on three real traces and we compare its performance to the ones of other well-known link prediction approaches. The results prove that our method reaches the highest level of accuracy and outperforms the other techniques. One of the major contributions behind our proposal highlights that the link prediction in such networks can be made in a distributed way. In other words, the nodes can predict their future links relying on the local information (one-hop and two-hop neighbors) instead of a full knowledge about the topology of the network. Furthermore, we are keen to improve the link prediction performance of our tensor-based framework. To quantify the social closeness between the users, we take into consideration two aspects of the relationships: the recentness of the interactions and their frequency. From this perspective, we wonder if we can consider a third criterion to improve the link prediction precision. Asserting the heuristic that stipulates that persistent links are highly predictable, we take into account the stability of the relationships (link and proximity stabilities). To measure it, we opt for the entropy estimation of a time series proposed in the Lempel-Ziv data compression algorithm. As we think that our framework measurements and the stability estimations complement each other, we combine them in order to provide new link prediction metrics. The simulation results emphasize the pertinence of our intuition. Providing a tensor-based link prediction framework and proposing relative enhancements tied to stability considerations represent the main contributions of this thesis. Along the thesis, our concern was also focused on mechanisms and metrics that contribute towards improving communication protocols in these mobile networks […]

Depuis 2001, le codage réseau a devenu une technique de communication qui permet des meilleures performances réseaux. Au lieu de relayer les paquets séparément, le codage réseau permet aux noeuds réseaux de combiner plusieurs paquets natifs en un seul paquet codé. Le réseau peut réduire le nombre de transmissions, réduire le temps de transfert et augmenter le débit de transmission. Le codage réseau ne suit pas l'hypothèse dans laquelle l'information reste séparée et invariable dans chaque paquet de la source à la destination. Dans le codage réseau, les informations transportées dans les paquets ne doivent pas être endommagées mais elles peuvent être mixées et transformées. Dans le contexte de cette thèse, nous contribuons dans deux directions: l'augmentation de la capacité du réseau et la fiabilité de la transmission contre les erreurs aléatoires. Pour augmenter la capacité du réseau, nous avons défini des nouvelles conditions de codage dans le codage réseau inter-flux. Pour fournir la fiabilité de la transmission, nous avons proposé de nouveaux protocoles de codage réseau. Les résultats de simulations via NS-2 ont montré les améliorations importantes des performances. / Since its first introduction in 2001, network coding has gained a significant attention from the research communities in the need of improving the way of communication in computer networks. In short, network coding is a technique which allows the nodes to combine several native packets into one coded packet for transmission (i.e, coding packets) instead of simply forwarding packets one by one. With network coding, a network can save the number of transmissions to reduce data transfer time and increase throughput. This breaks the great assumption about keeping information separate and whole. Information must not be tampered but it can be mixed, and transformed. In the scope of the thesis, we focus on two main benefits of network coding: throughput improvement and transmission reliability against random losses. For the throughput improvement, we use inter-flow network coding and extend the coding conditions. For transmission reliability, we use intra-flow network coding and suggest new coding schemes. The obtained results via NS-2 simulations are quite promising.

Les réseaux sans fil 802.11 sont en train d'être considérés comme étant la pierre angulaire des systèmes de communication autonomes. En permettant aux usagers de communiquer les uns avec les autres avec les stations de base fixées a des endroits bien précis par l'intermédiaire de protocoles de communication comme les protocole de routage ad hoc. Le standard IEEE 802.11 propose des spéciations pour les deux couches basses (MAC et Physique) du modelé OSI. La couche MAC (Medium Access Control) introduit deux mécanismes d'accès au médium sans fil qui sont différents l'un de l'autre. Le mécanisme DCF (accès au canal distribue ou Distributed Coordination Function), l'accès au canal s'exécute dans chaque station sans faire appel à une unité centrale. Le mécanisme PCF (Point Coordination Function), contrairement au mécanisme DCF l'accès au canal se fait à l'aide d'une unité centrale. Le mécanisme le plus utilise par la norme 802.11 est DCF vu qu'il ne nécessite pas d'infrastructure au déploiement. Pour améliorer la qualité de service dans les réseaux sans multi- sauts, cette thèse aborde cette problématique dans deux couches de la pile protocolaire, à savoir la couche routage et la couches MAC. Elle améliore le routage a QoS en utilisant le protocole de routage a état de lien optimisé (OLSR) et améliore aussi l'efficacité de l'accès au médium sans fil lors du fonctionnement de la couche MAC en mode le plus courant DCF. Pour l'amélioration de routage, nous proposons une approche basée sur le graphe de conflit pour l'estimation de la bande passante partagée entre les nœuds adjacents. Pour la couche MAC, nous proposons un nouveau schéma de Backoff nomme l'algorithme Backoff de Padovane (PBA), pour améliorer l'efficacité de l'accès au médium sans fil dans les réseaux sans fil mobiles Ad Hoc (MANETs). / IEEE 802.11 based wireless networks are considered the cornerstone of autonomous communication systems. These networks allow users to communicate with each others via base stations deployed in specic locations through a set of dedicated communication protocols like Ad Hoc routing protocols. The IEEE 802.11 standard proposes specications for both physical and MAC layers of the OSI model. MAC layer denes dierent types of access to the wireless medium as explained below. The DCF (Distributed Coordination Function) mechanism, in which the access to the medium is executed localy in each station. The PCF (Point Coordination Function) method, unlike DCF mechanism the access the medium is managed by a central unit. The most widespread mechanism among them is the DCF mode as it does not require any infrastructure deployment. To improve the Quality of Service (QoS) oered to the dierent applications in multihop wireless networks, this thesis proposes original solutions to enhance the eciency of certain protocols in two dierent layers of OSI, i.e., routing and MAC layers. More specically, our proposed solutions enable higher eciency of OLSR protocol and ensure more ecient usage of the available bandwidth through the designed Padovan based medium access scheme operating in DCF mode. The routing approach used in OLSR is improved by applying the conict graphs to acquire more accurate estimation of the bandwidth shared with the adjacent nodes. At MAC layer, the number of collisions in dense networks is signicantly reduced by designing new backo scheme dubbed Padovan Backo Algorithm (BEB).