Dissertations / Theses: 'Algorithmes ad'

1

Bessaoud, Karim. "Algorithmes auto-stabilisants pour les réseaux ad hoc." Versailles-St Quentin en Yvelines, 2013. http://www.theses.fr/2013VERS0048.

Full text

Abstract:

Dans cette thèse, nous proposons trois algorithmes auto-stabilisants pour les réseaux ad hoc sans fil. Le premier est un algorithme de construction d’un ensemble connexe dominant de poids faible, appelé backbone. Le backbone est utilisé pour créer une infrastructure logique dans un réseau ad hoc. Nous avons montré par simulation l’efficacité de cet algorithme dans différents contextes selon la sémantique donnée aux poids des nœuds : le backbone pouvant contenir par exemple les nœuds les plus chargés en énergie ou les moins mobiles. Les deux autres algorithmes traitent de l’économie d’énergie dans les réseaux de capteurs. Nous proposons deux solutions basées sur le contrôle de la topologie à travers la réduction des puissances de transmission, chacune dédié à un type de communication utilisé par les capteurs : communication entre tout couple de capteurs ou par diffusion. Tous les algorithmes présentés sont prouvés formellement et évalués par simulation
In this thesis, we propose three self-stabilizing algorithms for ad hoc wireless networks. The first one is an algorithm that builds a low weight connected dominating set, called backbone. The backbone is used to create a logical infrastructure in an ad hoc network. We show by simulation the efficiency of this algorithm in different contexts according to the semantics given to the weight of the nodes : the backbone may contain for instance the least mobile nodes or nodes with the highest battery level. The two other algorithms deal with energy conservation in wireless sensor networks. We propose two solutions based on topology control by reducing transmission powers, each one dedicated to a type of communication used by the sensors : communication between any pair of sensors or by diffusion. The proposed algorithms are formally proven and evaluated by simulation

APA, Harvard, Vancouver, ISO, and other styles

2

Guizani, Badreddine. "algorithmes de clustérisation et routage dans les réseaux Ad Hoc." Phd thesis, Université de Technologie de Belfort-Montbeliard, 2012. http://tel.archives-ouvertes.fr/tel-00703257.

Full text

Abstract:

Le passage à l'échelle des protocoles de routage est un des problèmes les plus critiques pour les réseauxmobiles sans fil à grande envergure. Dans ce cadre, le concept de clusterisation peut être mis à profit dans lafonction de routage afin d'améliorer les performances de ces réseaux. En premier lieu, cette thèse présentenotre algorithme de clusterisation à 1-saut alpha-SSCA (α-Stability Structure Clustering Algorithm) qui apour objectif d'améliorer la stabilité de la structure des clusters. Un algorithme générique de clusterisationà K-sauts est également proposé en ayant le même but de stabilité visé par alpha-SSCA tout en réduisant lenombre de clusters générés et en étant indépendant de la métrique d'élection des cluster-heads. Ensuite, nousprésentons notre proposition d'un protocole de routage à état des liens des clusters qui exploite les apports denotre mécanisme de clusterisation α-SSCA. Ce protocole, appelé CLSR (Cluster-based Link State Routing),vise à réduire le trafic de contrôle afin d'améliorer les performances du réseau à large échelle. Nous avonsproposé aussi une version hiérarchique du protocole CLSR. Ce protocole de routage introduit une hiérarchiedans la structure des clusters qui permet de réduire le nombre de clusters en groupement des clusters prochesdans un même cluster. L'objectif principal de ce protocole hiérarchique est d'améliorer la scalabilité de CLSRquand le nombre de noeuds dans le réseau augmente considérablement.

APA, Harvard, Vancouver, ISO, and other styles

3

Bricard-Vieu, Vincent. "Contrôle de topologie et qualité de service dans les réseaux ad hoc." Dijon, 2005. http://www.theses.fr/2005DIJOS056.

Full text

Abstract:

Cette thèse traite du contrôle de topologie (clustering) et de la qualité de service dans les réseaux ad hoc. Ces réseaux nécessitant des protocoles de routage robustes aux changements de topologie dus à la mobilité des nœuds, il faut les structurer. Les algorithmes de clustering proposés dans la littérature consistent à alterner des phases d'élection de chefs et de mise en grappe des nœuds avec des phases de maintenance pour garder une hiérarchie stable. Cependant, ils génèrent un gaspillage important, dégradant les performances. Pour améliorer celles-ci nous proposons dans cette thèse des algorithmes consistant à espacer les messages de signalisation envoyés par le chef et à estimer sa position à la place. De plus, certains de nos algorithmes proposent une élection locale des chefs, moins coûteuse qu'une élection globale. A l'aide du logiciel GloMoSim, nous réalisons des simulations pour évaluer les performances de nos algorithmes et les comparer avec celles d'autres algorithmes
This thesis deals with clustering and quality of service in mobile ad hoc networks. Node mobility in such networks induces a highly dynamical topology. Robust routing protocols are then required and organization of nodes is needed. Many clustering algorithms were proposed in the literature, consisting of phases of election of cluster-heads and construction of clusters, and phases of maintenance to preserve the stability of the hierarchy. However, that algorithms generate a significant overhead, damaging the performances. To improve these performances, we propose in this thesis, algorithms consisting of spacing the signalling messages sent by the cluster-head and replacing them by an estimate of its location. Moreover, some of our algorithms propose a local election, more efficient than a global one. Using the network simulator GloMoSim, simulations are conducted to evaluate our algorithm performances and compare them with existing ones

APA, Harvard, Vancouver, ISO, and other styles

4

Canourgues, Lucile. "Algorithmes de routage dans les réseaux mobile ad hoc tactique à grande échelle." Toulouse, INPT, 2008. http://ethesis.inp-toulouse.fr/archive/00000595/.

Full text

Abstract:

La Transformation qui s'opère depuis quelques années dans les réseaux militaires place le MANET comme une composante principale du domaine tactique. En effet, un MANET met en œuvre des nœuds de communication de grande mobilité, de grande réactivité et qui se déploient rapidement. De nombreuses applications militaires temps réel (ex : "situational awarness") reposent sur des communications de groupes et nécessitent donc l'existence d'un service multicast dans l'environnement tactique où le MANET est utilisé comme réseau de transit. L'objectif de cette thèse est d'étudier la mise en place d'un service multicast optimum dans l'environnement tactique MANET. Nous nous sommes premièrement attachés à définir l'architecture protocolaire multicast à déployer au sein du réseau tactique et plus particulièrement dans le MANET. Le MANET tactique est supposé être composé de plusieurs centaines de nœuds, ce qui implique que la contrainte de passage à l'échelle est déterminante dans le choix de l'architecture protocolaire du service multicast. Nous avons choisi le clustering comme solution de passage à l'échelle. Nous avons alors défini deux protocoles de routage multicast adaptés au MANET: STAMP, chargé des communications multicast à l'intérieur de chaque cluster et SAFIR, chargé des flux multicast entre les clusters. Ces deux protocoles agissent de concert pour fournir un service multicast performant et supportant le passage à l'échelle dans le MANET tactique. [. . . ]
The current Transformation of the military networks adopts the MANET as a main component of the tactical domain. Indeed, a MANET is the right solution to enable highly mobile, highly reactive and quickly deployable tactical networks. Many applications such as the Situational Awareness rely on group communications, underlying the need for a multicast service with the tactical environment where the MANET is employed as a transit network. The purpose of this thesis is to study the setting up of an optimal multicast service within this tactical environment. We firstly focus on defining the protocol architecture to carry out within the tactical network paying particular attention to the MANET. This network is interconnected within different types of networks based on IP technologies and implementing potentially heterogeneous multicast protocols. The tactical MANET is supposed to be made of several hundred of mobile nodes, which implies that the scalability is crucial in the multicast protocol architecture choice. Since the concept of clustering proposes interesting scalability features, we consider that the MANET is a clustered network. Thereby, we define two multicast routing protocols adapted to the MANET: firstly STAMP that is in charge of the multicast communications within each cluster and secondly SAFIR that handles multicast flows between the clusters. These two protocols that can be implemented independently, act in concert to provide an efficient and scalable multicast service for the tactical MANET

APA, Harvard, Vancouver, ISO, and other styles

5

Canourgues, Lucile Beylot André-Luc. "Algorithmes de routage dans les réseaux mobile ad hoc tactique à grande échelle." Toulouse : INP Toulouse, 2008. http://ethesis.inp-toulouse.fr/archive/00000595.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Drira, Kaouther. "Coloration d’arêtes ℓ-distance et clustering : études et algorithmes auto-stabilisants." Thesis, Lyon 1, 2010. http://www.theses.fr/2010LYO10335/document.

Full text

Abstract:

La coloration de graphes est un problème central de l’optimisation combinatoire. C’est un domaine très attractif par ses nombreuses applications. Différentes variantes et généralisations du problème de la coloration de graphes ont été proposées et étudiées. La coloration d’arêtes d’un graphe consiste à attribuer une couleur à chaque arête du graphe de sorte que deux arêtes ayant un sommet commun n’ont jamais la même couleur, le tout en utilisant le moins de couleurs possibles. Dans la première partie de cette thèse, nous étudions le problème de la coloration d’arêtes ℓ-distance, qui est une généralisation de la coloration d’arêtes classique. Nous menons une étude combinatoire et algorithmique du paramètre. L’étude porte sur les classes de graphes suivantes : les chaines, les grilles, les hypercubes, les arbres et des graphes puissances. Le paramètre de la coloration d’arêtes ℓ-distance permet de modéliser des problèmes dans des réseaux assez grands. Cependant, avec la multiplication du nombre de nœuds, les réseaux sont de plus en plus vulnérables aux défaillances (ou pannes). Dans la deuxième partie, nous nous intéressons aux algorithmes tolérants aux pannes et en particulier les algorithmes auto-stabilisants. Nous proposons un algorithme auto-stabilisant pour la coloration propre d’arêtes. Notre solution se base sur le résultat de vizing pour utiliser un minimum de couleurs possibles. Par la suite, nous proposons un algorithme auto-stabilisant de clustering destine a des applications dans le domaine de la sécurité dans les réseaux mobiles Ad hoc. La solution que nous proposons est un partitionnement en clusters base sur les relations de confiance qui existent entre nœuds. Nous proposons aussi un algorithme de gestion de clés de groupe dans les réseaux mobiles ad hoc qui s’appuie sur la topologie de clusters préalablement construite. La sécurité de notre protocole est renforcée par son critère de clustering qui surveille en permanence les relations de confiance et expulse les nœuds malveillants de la session de diffusion
Graph coloring is a famous combinatorial optimization problem and is very attractive for its numerous applications. Many variants and generalizations of the graph-coloring problem have been introduced and studied. An edge-coloring assigns a color to each edge so that no two adjacent edges share the same color. In the first part of this thesis, we study the problem of the ℓ-distance-edge-coloring, which is a generalization of the classical edge-coloring. The study focuses on the following classes of graphs : paths, grids, hypercubes, trees and some power graphs. We are conducting a combinatorial and algorithmic study of the parameter. We give a sequential coloring algorithm for each class of graph. The ℓ-distance-edge-coloring is especially considered in large-scale networks. However, with the increasing number of nodes, networks are increasingly vulnerable to faults. In the second part, we focus on fault-tolerant algorithms and in particular self-stabilizing algorithms. We propose a self-stabilizing algorithm for proper edge-coloring. Our solution is based on Vizing’s result to minimize number of colors. Subsequently, we propose a selfstabilizing clustering algorithm for applications in the field of security in mobile ad hoc networks. Our solution is a partitioning into clusters based on trust relationships between nodes. We also propose a group key-management algorithm in mobile ad hoc networks based on the topology of clusters previously built. The security of our protocol is strengthened by its clustering criterion which constantly monitors trust relationships and expels malicious nodes out of the multicast session

APA, Harvard, Vancouver, ISO, and other styles

7

Gawedzki, Ignacy. "Algorithmes distribués pour la sécurité et la qualité de service dans les réseaux ad hoc mobiles." Paris 11, 2008. http://www.theses.fr/2008PA112240.

Full text

Abstract:

Les protocoles de routage pour réseaux ad hoc actuels supposent l'absence totale de participants malveillants, alors que cette hypothèse est souvent contredite dans les applications. Nous avons cherché à enrichir les protocoles dits proactifs pour permettre aux nœuds de surveiller le réseau de manière distribuée et de mesurer la menace représentée par chacun des autres nœuds. Cette mesure sert à extraire une métrique de qualité de service utilisée ensuite par le protocole de routage pour contourner les nœuds les plus suspects d'après les différentes méthodes de détection utilisées. Nous proposons de détecter la perte de paquets de données, intentionnelle ou non. La détection est réalisée par une vérification distribuée du principe de conservation de flot, basée sur l'échange de compteurs de paquets entre voisins. Nous proposons également une méthode de diffusion de ces valeurs qui permet un meilleur passage à l'échelle. Cette détection ne sert qu'à maintenir un degré de suspicion local qui, une fois diffusé à tout le réseau et recombiné par les autres nœud, produit une métrique de suspicion globale envers chaque nœud. L'application au protocole OLSR est décrite et ses performances évaluées par simulation. Nous montrons que la solution est efficace et que l'impact du surcoût de contrôle sur la capacité du médium reste faible. Nous présentons enfin une plateforme expérimentale du protocole OLSR avec qualité de service et sécurité, servant à faire fonctionner nos solutions dans des mises en place réelles pour déceler les problèmes qui apparaissent lors de l'utilisation de matériel grand public
Currently available routing protocols for ad hoc networks assume the total absence of malicious participants, although this assumption is seldom true in practical applications. In this work, we look for a way to augment proactive protocols so as to let nodes watch over the network in a distributed fashion and measure the threat represented by every node. The measurement is used to extract a quality of service metric used in turn by the routing protocol to avoid the most suspected nodes, according to all the implemented detection methods. We propose to detect data packet loss, be it intentional or not. The detection is performed by a verification of the principle of flow conservation, based on the exchange of packet counters between neighbors. A scalable method of diffusion of these values is also proposed. The actual checking is used to maintain a local degree of distrust which is diffused in all the network and recombined by the nodes into a global metric of distrust in each node. The application to the OLSR protocol is described and its performance evaluated by simulation. We show that the solution is efficient and that the impact of the control overhead on the medium capacity remains low. Finally, an experimental platform of OLSR with quality of service and security is presented, which is aimed at making our solutions work in an actual real setup in order to reveal any potential problem that may appear with the use of commercial off-the-shelf hardware

APA, Harvard, Vancouver, ISO, and other styles

8

Drira, Kaouther. "Coloration d'arêtes ℓ-distance et clustering : études et algorithmes auto-stabilisants." Phd thesis, Université Claude Bernard - Lyon I, 2010. http://tel.archives-ouvertes.fr/tel-00736580.

Full text

Abstract:

La coloration de graphes est un problème central de l'optimisation combinatoire. C'est un domaine très attractif par ses nombreuses applications. Différentes variantes et généralisations du problème de la coloration de graphes ont été proposées et étudiées. La coloration d'arêtes d'un graphe consiste à attribuer une couleur à chaque arête du graphe de sorte que deux arêtes ayant un sommet commun n'ont jamais la même couleur, le tout en utilisant le moins de couleurs possibles. Dans la première partie de cette thèse, nous étudions le problème de la coloration d'arêtes ℓ-distance, qui est une généralisation de la coloration d'arêtes classique. Nous menons une étude combinatoire et algorithmique du paramètre. L'étude porte sur les classes de graphes suivantes : les chaines, les grilles, les hypercubes, les arbres et des graphes puissances. Le paramètre de la coloration d'arêtes ℓ-distance permet de modéliser des problèmes dans des réseaux assez grands. Cependant, avec la multiplication du nombre de nœuds, les réseaux sont de plus en plus vulnérables aux défaillances (ou pannes). Dans la deuxième partie, nous nous intéressons aux algorithmes tolérants aux pannes et en particulier les algorithmes auto-stabilisants. Nous proposons un algorithme auto-stabilisant pour la coloration propre d'arêtes. Notre solution se base sur le résultat de vizing pour utiliser un minimum de couleurs possibles. Par la suite, nous proposons un algorithme auto-stabilisant de clustering destine a des applications dans le domaine de la sécurité dans les réseaux mobiles Ad hoc. La solution que nous proposons est un partitionnement en clusters base sur les relations de confiance qui existent entre nœuds. Nous proposons aussi un algorithme de gestion de clés de groupe dans les réseaux mobiles ad hoc qui s'appuie sur la topologie de clusters préalablement construite. La sécurité de notre protocole est renforcée par son critère de clustering qui surveille en permanence les relations de confiance et expulse les nœuds malveillants de la session de diffusion.

APA, Harvard, Vancouver, ISO, and other styles

9

Hauspie, Michaël. "Contributions à l'étude des gestionnaires de services distribués dans les réseaux ad hoc." Phd thesis, Université des Sciences et Technologie de Lille - Lille I, 2005. http://tel.archives-ouvertes.fr/tel-00656359.

Full text

Abstract:

Les réseaux ad hoc sont des réseaux distribués, auto-organisés ne nécessitant pas d'infrastructure. Les entités formant un tel réseau doivent collaborer afin d'assurer le bon fonctionnement des services réseaux, tel que le routage. Dans un tel environnement, de nombreux algorithmes développés pour le monde filaire ne peuvent être adaptés de façon naïve sans entraîner une congestion importante du réseau qui va réduire son efficacité. Notre travail de thèse se penche sur l'étude de la gestion de services. En effet, sans application, le développement d'une architecture comme les réseaux ad hoc est inutile. La gestion de services consiste à fournir tout les moyens possibles pour faciliter et rendre fiable l'utilisation d'applications distribuées. Nos travaux contribuent à l'étude de deux points précis de la gestion de services. Premièrement, nous fournissons un algorithme permettant de répartir efficacement une information dans le réseau en sélectionnant certains objets du réseau pour être des réplicats de l'information. Cet algorithme peut alors être utilisé pour publier les informations relatives à un service afin de permettre sa recherche. Deuxièmement, nous avons étudié la prédiction de déconnexion entrainée par la mobilité des noeuds. Nous proposons trois solutions basées sur la recherche d'ensemble de chemins disjoints, la recherche de liens critiques et la recherche de noeuds critiques. Les recherches que nous proposons sont entièrement réalisées à partir d'informations locales. Les résultats obtenus fournissent une base au développement d'un gestionnaire de services distribués. De plus, certains de nos algorithmes (comme la recherche d'ensembles de chemins disjoints) peuvent être réutilisés dans d'autres applications, comme le routage QoS multi-chemins.

APA, Harvard, Vancouver, ISO, and other styles

10

Sahin, Serdar. "Advanced receivers for distributed cooperation in mobile ad hoc networks." Thesis, Toulouse, INPT, 2019. http://www.theses.fr/2019INPT0089.

Full text

Abstract:

Les réseaux ad hoc mobiles (MANETs) sont des systèmes de communication sans fil rapidement déployables et qui fonctionnent avec une coordination minimale, ceci afin d'éviter les pertes d'efficacité spectrale induites par la signalisation. Les stratégies de transmissions coopératives présentent un intérêt pour les MANETs, mais la nature distribuée de tels protocoles peut augmenter le niveau d'interférence avec un impact autant plus sévère que l'on cherche à pousser les limites des efficacités énergétique et spectrale. L'impact de l'interférence doit alors être réduit par l'utilisation d'algorithmes de traitement du signal au niveau de la couche PHY, avec une complexité calculatoire raisonnable. Des avancées récentes sur les techniques de conception de récepteurs numériques itératifs proposent d'exploiter l'inférence bayésienne approximée et des techniques de passage de message associés afin d'améliorer le potentiel des turbo-détecteurs plus classiques. Entre autres, la propagation d'espérance (EP) est une technique flexible, qui offre des compromis attractifs de complexité et de performance dans des situations où la propagation de croyance conventionnel est limité par sa complexité calculatoire. Par ailleurs, grâce à des techniques émergentes de l'apprentissage profond, de telles structures itératives peuvent être projetés vers des réseaux de détection profonds, où l'apprentissage des hyper-paramètres algorithmiques améliore davantage les performances. Dans cette thèse nous proposons des égaliseurs à retour de décision à réponse impulsionnelle finie basée sur la propagation d'espérance (EP) qui apportent des améliorations significatives, en particulier pour des applications à haute efficacité spectrale vis à vis des turbo-détecteurs conventionnels, tout en ayant l'avantage d'être asymptotiquement prédictibles. Nous proposons un cadre générique pour la conception de récepteurs dans le domaine fréquentiel, afin d'obtenir des architectures de détection avec une faible complexité calculatoire. Cette approche est analysée théoriquement et numériquement, avec un accent mis sur l'égalisation des canaux sélectifs en fréquence, et avec des extensions pour de la détection dans des canaux qui varient dans le temps ou pour des systèmes multi-antennes. Nous explorons aussi la conception de détecteurs multi-utilisateurs, ainsi que l'impact de l'estimation du canal, afin de comprendre le potentiel et le limite de cette approche. Pour finir, nous proposons une méthode de prédiction performance à taille finie, afin de réaliser une abstraction de lien pour l'égaliseur domaine fréquentiel à base d'EP. L'impact d'un modélisation plus fine de la couche PHY est évalué dans le contexte de la diffusion coopérative pour des MANETs tactiques, grâce à un simulateur flexible de couche MAC
Mobile ad hoc networks (MANETs) are rapidly deployable wireless communications systems, operating with minimal coordination in order to avoid spectral efficiency losses caused by overhead. Cooperative transmission schemes are attractive for MANETs, but the distributed nature of such protocols comes with an increased level of interference, whose impact is further amplified by the need to push the limits of energy and spectral efficiency. Hence, the impact of interference has to be mitigated through with the use PHY layer signal processing algorithms with reasonable computational complexity. Recent advances in iterative digital receiver design techniques exploit approximate Bayesian inference and derivative message passing techniques to improve the capabilities of well-established turbo detectors. In particular, expectation propagation (EP) is a flexible technique which offers attractive complexity-performance trade-offs in situations where conventional belief propagation is limited by computational complexity. Moreover, thanks to emerging techniques in deep learning, such iterative structures are cast into deep detection networks, where learning the algorithmic hyper-parameters further improves receiver performance. In this thesis, EP-based finite-impulse response decision feedback equalizers are designed, and they achieve significant improvements, especially in high spectral efficiency applications, over more conventional turbo-equalization techniques, while having the advantage of being asymptotically predictable. A framework for designing frequency-domain EP-based receivers is proposed, in order to obtain detection architectures with low computational complexity. This framework is theoretically and numerically analysed with a focus on channel equalization, and then it is also extended to handle detection for time-varying channels and multiple-antenna systems. The design of multiple-user detectors and the impact of channel estimation are also explored to understand the capabilities and limits of this framework. Finally, a finite-length performance prediction method is presented for carrying out link abstraction for the EP-based frequency domain equalizer. The impact of accurate physical layer modelling is evaluated in the context of cooperative broadcasting in tactical MANETs, thanks to a flexible MAC-level simulator

APA, Harvard, Vancouver, ISO, and other styles

11

Iguchi-Cartigny, Julien. "Contributions à la diffusion dans les réseaux ad hoc." Lille 1, 2003. https://pepite-depot.univ-lille.fr/LIBRE/Th_Num/2003/50376-2003-229.pdf.

Full text

Abstract:

Les technologies sans fils ont atteint une place dominante ces demières années. Le fait de laisser à l'utilisateur une totale liberté de mouvement et des débits grandissants ont popularisé ce moyen de communication. Pourtant, cette liberté est loin d'être, car eIle est reliée à un point fixe de coordination des communications (une borne d'accès fixe dans le cas du système Wifi ou du GSM). Les réseaux ad hoc proposent une vision sans infrastructure, où le réseau est supporté par l'ensemble des utilisateurs mobiles. Dans un tel système, chaque mobile peut relayer un message de ses voisins, dans le but de pennettre à chacun des noeuds de pouvoir joindre n'importe qui d'autre dans le réseau, à condition qu'il existe des noeuds sur le chemin pouvant relayer le message. L'opération de diffusion (ou brodcast) est une opération courante dans de tels réseaux. Elle consiste à envoyer un message à l'ensemble des mobiles participants au réseau ad hoc. A cause de la mobilité, des possibilités de collision radio, de la connaissance limitée du voisinage et de la nature distribuée des algorithmes utilisés dans chaque noeud, cette opération peut se révéler coûteuse si elle est effectuée de manière nai͏̈ve. Dans la première partie du travail de recherche exposé, l'objectif est de réduire le nombre de messages émis par l'ensemble du réseau, de manière à réduire les risques de collisions tout en assurant une couverture complète. Le protocole BRP est un algorithme probabiliste dont la décision de réémission est biaisée par l'étude du voisinage commun entre deux noeuds. Le protocole RRS utilise l'algorithme de réduction de graphe pour réduire le voisinage de chaque noeud et ainsi permettre une prise de décision à partir d'un nombre limité de voisins. Dans la deuxième partie, l'étude est portée sur la réduction du coût énergétique, qui dépend en grande partie des communications radios. Avec des antennes omnidirectionnelles, chaque mobile peut réduire sa portée. RBOP et LBOP tirent avantage de ce procédé en utilisant les algorithmes de réduction de graphe RNG et LMST afin de réduire la consommation tout en gardant un réseau connexe. Le cas des antennes directionnelles est également envisagé, avec la proposition d'un algorithme hybride ADLBOP utilisant une communication un-vers-un ou un-vers-tous en fonction du modèle énergétique affecté au coût de la transmission et de la topologie locale.

APA, Harvard, Vancouver, ISO, and other styles

12

Miranda, Karen. "Algorithmes d'auto-déploiement adaptatifs pour des réseaux de substitution mobiles sans fil." Phd thesis, Université des Sciences et Technologie de Lille - Lille I, 2013. http://tel.archives-ouvertes.fr/tel-00918017.

Full text

Abstract:

En cas de sinistre, les infrastructures de communication peuvent être partiellement ou totalement détruites, ou devenir inefficaces en raison du trafic élevé. Néanmoins, il est nécessaire d'assurer la connexité entre les équipes de secours et le centre de commandement. Par conséquent, des solutions de communication temporaires sont essentielles jusqu'à ce que l'infrastructure soit rétablie. Dans cette thèse, nous nous concentrons sur le déploiement d'une solution de communication appelée réseaux de substitution. Ainsi, nous proposons un algorithme d'auto - déploiement pour permettre aux routeurs mobiles, composant un réseau de substitution, de se répartir pour couvrir la zone cible. Notre algorithme surveille les conditions du réseau pour décider si le routeur doit ou non se déplacer, il règle la position de ce dernier en fonction des informations provenant des nœuds voisins à un saut au moyen de la mesure active, c'est à dire, les paquets sondes. Ces paquets sondes permettent à l'algorithme de surveiller le canal et ses éventuels changements au fil du temps. Nous comparons les différents paramètres pour évaluer la qualité du lien et nous observons le comportement de notre algorithme de déploiement considérant chaque paramètre séparément. Par ailleurs, nous étudions comment la mobilité contrôlée des routeurs affecte la performance du réseau au moyen des simulations. Afin d'évaluer la qualité de la liaison, la plupart des algorithmes de déploiement utilisent des techniques de la mesure active. Ces techniques nécessitent que les nœuds envoyent des paquets sondes sur le réseau pour obtenir des mesures. La précision de telles mesures dépend de la fréquence des paquets sondes transmis. Cette précision est importante lorsque les caractéristiques du canal changent au fil du temps. Néanmoins, il existe un compromis entre le taux de transmission des paquets sondes et la précision des mesures. Si le taux de transmission des paquets est suffisamment élevé, les connaissances obtenues seront exactes, cependant, le coût augmentera proportionnellement en consommant plus de ressources réseau. D'ailleurs, puisque notre algorithme de déploiement dépend de la mesure de la qualié du lien pour prendre une décision, si on réduit le taux de transmission des paquets sondes, on augmente le temps nécessaire au routeur pour rassembler des informations pour prendre la décision de mouvement et, en conséquence on augmente le temps de déploiement. C'est pourquoi, nous proposons d'utiliser des données de substitution obtenues au moyen d'un estimateur autorégressif pour réduire la surcharge sans impacter notre algorithme de déploiement. Nous montrons par simulation l'efficacité des deux algorithmes et de leurs performances en termes de temps de déploiement, de délai, de gigue et de débit.

APA, Harvard, Vancouver, ISO, and other styles

13

Miranda, Campos Karen Samara. "Algorithmes d'auto-déploiement adaptatifs pour des réseaux de substitution mobiles sans fil." Thesis, Lille 1, 2013. http://www.theses.fr/2013LIL10147/document.

Full text

Abstract:

En cas de sinistre, les infrastructures de communication peuvent être partiellement ou totalement détruites, ou inefficaces en raison du trafic élevé. Néanmoins, il est nécessaire d'assurer la connectivité entre les équipes de secours et le centre de commandement. Par conséquent, les solutions de communication temporaires sont essentielles jusqu'à ce que l'infrastructure soit rétablie. Dans cette thèse, nous nous concentrons sur le déploiement d’une solution de communication appelée réseaux de substitution. Ainsi, nous proposons un algorithme d'auto - déploiement pour permettre aux routeurs mobiles et répartis composant un réseau de substitution de couvrir la zone cible. Notre algorithme surveille les conditions du réseau pour décider si le routeur doit ou non se déplacer, ajustant la position de ce dernier en fonction des informations à un saut au moyen de la mesure active, c'est à dire, les paquets sondes. Ces paquets sondes permettent à l'algorithme de surveiller le canal et ses éventuels changements au fil du temps. Si le taux de transmission des paquets est suffisamment élevé, les connaissances obtenues seront exactes, cependant, le coût augmentera proportionnellement en consommant plus de ressources réseau. Par conséquent, nous proposons d'utiliser des données de substitution obtenus au moyen d'un estimateur autorégressif pour réduire la surcharge sans impacter notre algorithme de déploiement. Nous montrons par simulation l'efficacité des deux algorithmes et leurs performances en termes de temps de déploiement, de délai, de gigue et de débit
In case of a disaster, the communication infrastructure may be partially or totally destroyed, or insufficient due to the high data traffic. Despite this, it is necessary to provide connectivity between the rescue teams and the command center. Therefore, temporary communication solutions are crucial until the infrastructure is restored. In this thesis, we focus on the deployment of communication solution called substitution networks. Thus, we propose a self-deployment algorithm to allow mobile routers that compose a substitution network spread out to cover the target area. Our algorithm monitors the network conditions to decide whether the router should move or not, adjusting its position based on one-hop information by means of active measurement, i.e., probe packets. Such probe packets allows the algorithm to monitor the channel and its eventual changes over time. If the probe transmission rate is enough high, the insights obtained will be accurate, however, the overhead will increase proportionally consuming network resources. Hence, we propose to use surrogate data obtained by means of an autoregressive estimator to reduce the overhead without impacting our deployment algorithm. We show by simulation the efficiency of both algorithms and their performance in terms of deployment time, delay, jitter, and throughput

APA, Harvard, Vancouver, ISO, and other styles

14

Morales, Varela Nelson Víctor. "Algorithmique des réseaux de communication radio modélisés par de [sic] graphes." Nice, 2007. http://www.theses.fr/2007NICE4032.

Full text

Abstract:

Cette thèse concerne l'étude de l'algorithmique et de la complexité des communications dans les réseaux radio. La particularité des réseaux radio est que la distance de transmission est limitée et que les transmissions interfèrent entre elles (phénomènes de brouillage). Nous modélisons ces contraintes en disant que deux sommets (équipements radio) peuvent communiquer s'ils sont à distance au plus d_T et qu'un noeud interfère avec un autre si leur distance est au plus d_I. Les distances sont considérées soit dans un graphe représentant le réseau, soit dans le plan euclidien. Une étape de communication consistera en un ensemble de transmissions compatibles (n'interférant pas). Nous nous sommes intéressés au problème de rassembler les informations des sommets du réseau en un noeud central appelé puits. Notre objectif est de trouver le nombre minimum d'étapes nécessaires pour réaliser un tel rassemblement et de concevoir des algorithmes réalisant ce minimum. Ce problème est motivé par une question de France Telecom "comment amener Internet dans les villages". Les sommets représentent les maisons des villages qui communiquent entre elles par radio, le but étant d'atteindre une passerelle centrale connectée à Internet par une liaison satellite. Le même problème se rencontre dans les réseaux de senseurs ou il s'agit de collecter les informations des senseurs dans une station de base. Nous avons considéré le cas où chaque sommet a un nombre fixé de paquets à transmettre et où les distances sont mesurées sur le graphe. Nous avons montré que trouver une solution optimale est en général un problème NP-difficile. Nous avons donné un algorithme 4-approché pour un graphe quelconque. Nous avons aussi établi des résultats optimaux ou quasi optimaux pour des topologies particulières comme la grille ou le chemin. Nous avons aussi considéré le cas systolique où on veut transmettre continuellement des paquets, l'objectif étant de minimiser l'écart entre l'envoi de deux paquets d'un même noeud. Nous avons étudié ce problème quand les distances sont mesurées sur le graphe et aussi dans le cas de sommets dans le plan avec distances euclidiennes. Nous avons montré que ce problème était NP-difficile, avons établi un algorithme 4-approché et obtenu des solutions quasi optimales pour les chemins, arbres et grilles
This thesis studies the algorithmics anc complexity of communications in a radio network. Radio networks are particular, because the transmission distance is limited and because certain transmissions may interfere with each other. We model this constraints by assuming that two nodes (radio equipment) can communicate with each other if they are at a distance smaller or equal than d_T and that a node interferes with any other that is at a distance smaller or equal than "d_I. This distances are considered in both cases: when they nodes belong to the Euclidean space and the distance between the nodes is the usual Euclidean distance, and when the distances are measured over a graph representing the network. A round being a set of transmissions that are compatible (do not interfere) we interest ourselves in the problem of gathering information originated at the nodes in the network into a central node called the sink. Our goal is to find the minimum number of rounds required to gather all the information and to devise algorithms that calculate this minimum. This problem is motivated by a question asked by France Telecom about providing internet to villages in France (internet dans les villages). The nodes represent houses (clients) that communicate with each other by means of radio signals, their objective being to access internet using a central gateway which, in turn, is connected to the internet with by satellite. The same problem is found in sensor networks, where information is collected in sensors (the nodes) and has to be gathered in a base station. We considered the case where each node has a fixed number of packets to transmit and the distances are measured over a base-graph. We have shown that the problem of finding an optimal solution is Np-Hard in the general case, but we provided a four approximation algorithm, valid for any base-graph. We have also studied either optimal or nearly optimal solutions for particular topologies like the path and the 2-D grid. We have also studied the systolic case where packets are transmitted permanently, the objective being to satisfy arbitrary traffic demands, per unit of time, with the smallest possible delay. We have studied this variant of the problem in the case where distances are measured on a graph, but also then they are measured in the Euclidean space. We have shown that the problem is NP-Hard, have established a four approximation and obtained either optimal or nearly optimal solutions for the path, trees and subsets of the 2-D grid

APA, Harvard, Vancouver, ISO, and other styles

15

Casteigts, Arnaud. "Contribution à l'algorithmique distribuée dans les réseaux mobiles ad hocCalculs locaux et réétiquetages de graphes dynamiques." Bordeaux 1, 2007. http://www.theses.fr/2007BOR13430.

Full text

Abstract:

Les réseaux mibiles ad hoc sont par nature instables et imprévisibles. De ces caractéristiques découle la difficulté à concevoir et analyser des algorithmes distribués garantissant certaines propriétés. C'est sur ce point que porte la contribution majeure de cette thèse. Pour amorcer cette étude, nous avons étudié quelques problèmes fondamentaux de l'algorithmique distribuée dans ce type d'environnement. Du fait de la nature de ces réseaux, nous avons considéré des modèles de calculs, où chaque étape ne fait collaborer que des noeuds directement voisins. Nous avons notamment proposé un nouveau cadre d'analyse, combinant réétiquetages de graphes dynamiques et graphes évolutifs (modèle combinatoire pour els réseaux dynamiques). Notre approche permet de caractériser les conditions d'un succès ou d'échec d'un algorithme en fonction de la dynamique du réseau, autrement dit, en fonction de conditions nécessaires et/ou suffisantes sur les graphes évolutifs correspondants. Nous avons également étudié la synchronisation sou-jacente aux calculs, ainsi que la manière dont une application réelle peut reposer sur un algorithme de réétiquetage. Un certain nombre de logiciels ont également été réalisés autour de ces travaux, notamment un simulateur de réétiquetage de graphes dynamiques et un vérificateur de propriétés sur les graphes évolutifs.

APA, Harvard, Vancouver, ISO, and other styles

16

Rachedi, Abderrezak. "Contributions à la sécurité dans les réseaux mobiles ad Hoc." Phd thesis, Université d'Avignon, 2008. http://tel.archives-ouvertes.fr/tel-00683602.

Full text

Abstract:

La thèse se focalise sur la sécurité dans les réseaux mobiles ad hoc (MANET : Mobile Ad hoc NETwork) [RFC 2501]. L'absence d'une gestion centrale des fonctionnalités du réseau rend ces réseaux beaucoup plus vulnérables aux attaques que les réseaux sans ﬁl (WLAN) et ﬁlaires (LAN). Malheureusement, les protocoles de sécurité qui existent actuellement ne sont pas conçus pour un tel environnement (dynamique). Ils ne prennent pas la contrainte des ressources en considération car non seulement l'environnement est dynamique, mais les ressources sont aussi limitées (mémoire, capacité de calcul et surtout énergie), ce qui complique davantage la problématique, car on sait bien que les solutions de sécurité sont gourmandes en terme de ressources. Cependant, en raison de l'importance des domaines d'application des réseaux mobiles ad hoc comme les opérations militaires (communication entre les avions, les voitures et le personnel et opérations de secours, situations d'urgence en cas de sinistre, etc . . .), il faut relever le déﬁ, car concevoir un mécanisme de sécurité infaillible pour les réseaux mobiles ad hoc est nécessaire. L'objectif principal de la thèse consiste à étudier les solutions susceptibles d'assurer la sécurité dans les réseaux mobiles ad hoc, en proposant une architecture hiérarchique distribuée qui permet d'établir une infrastructure dynamique à clé publique. Cette architecture doit supporter les différentes caractéristiques de ces réseaux (absence d'une unité centrale de gestion de réseau, topologie réseau dynamique, etc . . .). Dans ce but, un modèle de conﬁance adapté à l'environnement dynamique pour assurer l'évolution des niveaux de conﬁance des nœuds est établi. De plus, les vulnérabilités au niveau des autorités de certiﬁcation sont prises en compte dans le nouveau concept de DDMZ (zone dynamique démilitarisée) que nous proposons. Dans le but de sécuriser les nœuds dont le rôle est crucial au sein du réseau, leur identité doit être cachée. C'est pourquoi le concept d'anonymat est introduit. Un protocole d'authentiﬁcation anonyme est proposé. De plus, nous nous inspirons du modèle militaire pour mettre en place un mécanisme de camouﬂage qui cache le rôle des nœuds sensibles. Pour entretenir le modèle de conﬁance, un mécanisme de surveillance est indispensable. Il est adapté aux contraintes de l'environnement sans ﬁl dynamique et réduit le taux de fausses alarmes (faux positifs). Il est fondé sur une approche inter-couches et un modèle probabiliste pour améliorer l'observation du nœud surveillant. Pour faire face aux attaques intelligentes de type inter-couches, une étude des vulnérabilités au niveau des couches inférieures comme la couche MAC est menée. Ensuite, des mécanismes de prévention et de détection sont analysés et évalués. La performance de ces mécanismes est évaluée avec la prise en compte des métriques primordiales pour les réseaux mobiles ad hoc, telles que la consommation d'énergie, la mobilité, la densité des nœuds et du traﬁc, etc . . .

APA, Harvard, Vancouver, ISO, and other styles

17

Khalfallah, Sofiane. "Algorithmique best-effort pour les réseaux dynamiques." Compiègne, 2010. http://www.theses.fr/2010COMP1889.

Full text

Abstract:

Les réseaux dynamiques posent de nouvelles difficultés pour la construction d'applications réparties (mobilité, absence d'infrastructure, communication sans-fil, etc. ). Les réseaux ad hoc de véhicules (VANET) représentent un des cas d'étude des réseaux dynamiques. Nous avons commencé les travaux par un état des projets européens concernant les VANETs. Ensuite, nous avons modélisé la norme IEEE 802. 11, qui s'impose comme une technologie sans-fil standard pour la communication entre noeuds mobiles. Nous avons présenté l'algorithmique best-effort qui permet de compléter le concept d'auto-stabilisation afin de gérer la dynamique du réseau. C'est pourquoi nous avons introduit le concept de convergence continue. Ce concept est à rapprocher de la super-stabilisation. L'idée d'une métrique de la dynamique nous est apparue importante (comme la notion de durée d'une ronde continue). Nous avons proposé une application de l'algorithmique best-effort, à savoir un algorithme auto-stabilisant ayant une convergence continue pour la gestion de groupe. Nous avons présenté nos contributions dans la suite logicielle Airplug pour aboutir à une plate-forme complète pour l'évaluation de performances et un prototypage rapide des protocoles best-effort. Nous avons implémenté le protocole réparti GRP qui permet la gestion de groupe dans les réseaux dynamiques et évalué ses performances dans le mode Airplug-ns. Nous avons proposé des métriques appropriées, qui décrivent la stabilité des groupes, pour évaluer les performances de notre protocole
Many problems are open in the design of distributed applications (mobility, ad hoc communication, wireless technology, etc. ). We focus our work on a specific case study of dynamic networks, which is Vehicular ad-hoc networks (VANET). We first establish a state-of-the-art for this field based on the European projects in the VANETs. Second, we model the IEEE 802. 11 standard that tends to be a standard for mobile communication. Best-effort algorithmics allowing to complete the concept of auto-stabilization in the management of dynamic networks are presented. For that aim, we introduce the concept of service continuity. This concept is close to the super-stabilization. We believe that the idea of metrics studying dynamic topologies is important (as the notion of duration of a continuous round). The proposed algorithm works in dynamic and distributed systems. It globally ensures a kind of service continuity to applications while the system is still converging, except if a huge number of topology changes happen. After that, we present our contributions in the Airplug software, as well as in the design and the implementation of a complete platform for performance evaluation and fast prototyping of best-effort protocols. An implementation is done of the distributed protocol GRP to estimate its performances in the Airplug-ns mode. Finally, we propose appropriate metrics that describe the stability of groups in order to evaluate the performance of our protocol

APA, Harvard, Vancouver, ISO, and other styles

18

Ghedira, Mohamed Chadli. "Le guidage routier et les algorithmes de routage dans les réseaux véhiculaires." Thesis, Evry, Institut national des télécommunications, 2011. http://www.theses.fr/2011TELE0019.

Full text

Abstract:

Dans cette thèse, nous nous intéressons à deux types d’architectures dans les réseaux véhiculaires : les réseaux à infrastructure et les réseaux sans infrastructure. L’objectif de ce travail est de définir des solutions améliorant la connectivité des passagers des véhicules dans des environnements à densité variable en points d’accès. Pour ceci, dans un premier temps, nous nous intéressons aux algorithmes de guidage routier (dont l’objet est de guider un véhicule d’un point de départ vers un point d’arrivée) en prenant en compte les emplacements des points d’accès le long des routes. Notre première contribution est de définir un algorithme de guidage qui offre une connectivité supérieure au chemin par défaut (en général le plus court chemin) tout en maintenant une distance parcourue raisonnable pour les passagers du véhicule. Nous nous intéressons également à la minimisation du nombre de handovers afin d’améliorer la qualité de service du réseau. Nous avons évalué notre algorithme en termes de distance couverte et du nombre de handovers, tout en s’assurant de garder une distance totale parcourue raisonnable. Nous avons étudié dans un deuxième temps l’impact du choix de l’algorithme du guidage routier sur les performances de la couche réseau, où nous avons pris en compte deux types de protocoles de routage de données : réactif et proactif. Ensuite, nous avons étudié une problématique récurrente dans les réseaux véhiculaires qui est le routage des données de véhicule à véhicule. Ceci est particulièrement utile en absence d’une infrastructure disponible sur la route. Nous proposons une solution inter-couches («cross-layer») qui tire profit des caractéristiques des réseaux sans fil pour offrir un protocole de routage multi-sauts. Contrairement à la plupart des propositions de protocoles de routage, notre solution ne requiert pas un échange de messages de signalisation entre les voisins, ce qui améliore les performances du réseau en termes de charge utile et efficacité, surtout pour un réseau à forte mobilité comme c’est le cas pour des réseaux véhiculaires où les voisins changent d’une seconde à une autre, rendant problématique la mise à jour des informations de chaque nœud mobile sur son entourage
In this thesis, we focus on two types of architectures in vehicular networks: infrastructure networks and networks without infrastructure. The goal of this work is to define solutions to improve connectivity for passengers of vehicles in environments with variable density of access points. For this, we start by studying route guidance systems (whose purpose is to guide a vehicle from a starting point to a destination point), taking into account the locations of access points along roads. Our first contribution is to define a route guidance algorithm that offers superior connectivity compared to the default path (usually the shortest path) while maintaining a reasonable distance for passengers. We dealt also another issue which consists in minimizing the number of handovers to improve the quality of network service. We evaluated our algorithm in terms of covered distance and the number of handovers, while making sure to keep a reasonable traveled distance. After that, we studied the impact of the choice of route guidance algorithm in the performance of the network layer, where we took into account two types of routing protocols data: reactive and proactive. Next, we studied a recurrent problem in vehicular networks which is routing data from vehicle to vehicle. This is particularly useful in the absence of available infrastructure on the road. We propose a cross-layer architecture that takes advantage of the characteristics of wireless networks to design a multi-hops routing protocol. Unlike most proposals for routing protocols, our solution does not require an exchange of signaling messages between neighbors, and so improves network performance in terms of overhead and efficiency, especially for networks with high mobility such as vehicular networks, where neighbors change frequently, making it difficult to update information from each mobile node on its surroundings

APA, Harvard, Vancouver, ISO, and other styles

19

Riahla, Mohamed Amine. "Contributions au routage et l'anonymat des échanges dans les réseaux dynamiques." Limoges, 2013. http://aurore.unilim.fr/theses/nxfile/default/092038da-e61a-46b8-81d6-5690d2cbece3/blobholder:0/2013LIMO4051.pdf.

Full text

Abstract:

L'évolution rapide des technologies d'internet a permis l'émergence de nouveaux types de réseaux très dynamiques avec des architectures fortement décentralisées et dont les services sont organisés de manière autonome. Ces spécificités ont un réel avantage : le déploiement et la mise en place rapide et peu coûteux de ce type de réseaux. Mais en contrepartie, ces réseaux peuvent engendrer des difficultés lors de la mise en œuvre de certains services tel que le routage et la sécurité en général. Dans le cadre de cette thèse, nous avons pris comme cas d'étude les réseaux P2P et les réseaux ad hoc. Nous proposons dans ce mémoire un ensemble de contributions que nous classons en deux parties : l'anonymat des échanges dans un réseau P2P et le routage dans les réseaux ad hoc
The quick development of internet technologies gave birth to new types of network architectures with highly decentralized services that are organized independently. These characteristics have a real advantage : the deployment and implemetion are rapid and inexpensive for this type of networks. But in return, these networks can lead to difficulties when setting-up some services such as routing and security in general. In this thesis, we have taken as a case study P2P networks and ad hoc networks. We propose in this paper a set of contributions that we classify into two parts : the exchange anonymity in a P2P network and routing in an ad hoc networks

APA, Harvard, Vancouver, ISO, and other styles

20

Lagos, Jenschke Tomas. "Toward reliable and bounded latency for internet of things." Thesis, Ecole nationale supérieure Mines-Télécom Atlantique Bretagne Pays de la Loire, 2020. http://www.theses.fr/2020IMTA0222.

Full text

Abstract:

Les Low Power and Lossy Network (LLN) sont des technologies Internet of Things (IoT) sans fil qui fonctionnent avec une puissance de traitement, une mémoire ou une puissance limitées. En outre, ils ont des liens caractérisés par des taux de perte élevés. Toutefois, en raison de leur faible coût et de leur facilité de manipulation, elles sont devenues populaires dans l'industrie 4.0. Par conséquent, pour que ces technologies puissent être intégrées dans l’industrie, elles doivent assurer une transmission fiable, rapide et stable. Le IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL) est un protocole de routage vectoriel à distance spécialisé dans ces applications IoT. Son adaptabilité en a fait l’un des protocoles les plus populaires pour les LLNs. Cependant, sa transmission unidirectionnelle en amont n’est pas suffisante pour garantir la fiabilité de la transmission. Il en résulte un défi pour l’industrie et différentes fonctions et stratégies ont été proposées pour résoudre ce problème. Malheureusement, nombre de ces stratégies ne peuvent être reproduites pour différents environnements et nécessitent des compromis dans d’autres domaines. Dans cette thèse, notre objectif est de fournir une RPL personnalisée afin qu’elle puisse assurer la fiabilité de la transmission tout en maintenant un faible retard et une faible fluctuation. À cette fin, nous proposons différentes fonctions et algorithmes qui permettent l’extension des multitrajets en RPL
The Low Power and Lossy Network (LLN) are wireless Internet of Things (IoT) technologies that operate with limited processing power, memory, or power. Furthermore, they have links characterized by high loss rates. However, due to their low cost and easy handling, they have become popular in the industry 4.0. Therefore, for these technologies to be incorporated into the industry, they need to ensure reliable, fast, and stable transmission. The IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL) is a distance vector routing protocol specialized in these IoT applications. Its adaptability has made it one of the most popular protocols for LLNs. However,its one-way upstream transmission is not sufficient to guarantee transmission reliability. This has resulted in a challenge to the industry and different functions and strategies have been proposed to address this problem. Unfortunately, many of these strategies cannot be replicated for different environments and require trade-offs in other areas. In this thesis,our goal is to provide a customized RPL so that it can ensure transmission reliability while maintaining a low delay and fluctuation. For this purpose, we propose different functions and algorithms that allow the extension of multi-path in RPL

APA, Harvard, Vancouver, ISO, and other styles

21

Kouassi, Kouakou. "Modélisation et optimisation des transmissions ultra-large bande à impulsions radio dans les réseaux ad hoc." Thesis, Lille 1, 2012. http://www.theses.fr/2012LIL10197/document.

Full text

Abstract:

Cette thèse s’articule autour des transmissions ultra-large bande à impulsions radio dans les réseaux de capteurs. Ces réseaux dotés de la structure point à point sont capables de générer une quantité suffisamment élevée d’interférences pour rendre les communications peu fiables. La technique utilisée pour séparer les données est la modulation par position d’impulsion qui distingue les données en leur attribuant des décalages temporels différents. Il s’agit, dans ce travail, de faire des propositions pour réduire ces interférences tout en respectant les réglementations (masques spectrales) sur les fréquences radioélectriques, imposées dans les pays où ces réseaux seront amenés à être utilisés. A titre indicatif, cette thèse ne fait référence qu’au masque États-Unien. Toutefois, les résultats obtenus sont applicables à tout autre masque. Les masques étant fortement restrictifs, nous nous sommes donc intéressés, de prime-abord, à l’aménagement du spectre des signaux émis, afin de permettre une utilisation optimale du peu de puissance disponible. La proposition que nous faite, à cette fin, donne des résultats intéressants. Ensuite une modélisation analytique prenant en compte la précédente alternative permet d’évaluer numériquement les performances. Ces dernières sont comparées à celles obtenues par des simulations de type Monte-Carlo. Il s’avère que le modèle est suffisamment précis pour servir de base à une optimisation, à la fois, des performances et de l’occupation spectrale. Les résultats obtenus montrent que notre proposition permet de fiabiliser les transmissions au sein des réseaux de capteurs sujets à de fortes perturbations dues à l’accès multiple
This thesis focuses on impulse radio Ultra-Wide Band (UWB) transmissions in ad hoc sensor network. Such networks are able to generate strong enough multiple access interference to be less reliable. The method used to distinguish data is the Pulse Position Modulation where different delay is assign to each data type. The purpose of this study is to suggest proposals to mitigate this issue while fitting with the radio waves regulations in the countries where these networks will operate. As a rough guide, this thesis only refers to the American UWB regulation. However, the obtained results are relevant to any kind of mask. The masks are highly restrictive, we therefore interested to the transmitted signals spectrum shapes, first, in order to guarantee an optimal use of the available power. The proposal we made for this purpose reveals highly interesting. Then an analytical model taking into account the last suggestion is built to numerically evaluate the performances. These performances are compared to the ones obtained with Monte-Carlo simulations. It appears that the model is accurate enough to be used in an optimisation process. This process aims to find data signals that give the best performances and the optimal spectral occupancies, at the same time. The obtained results show that our proposal allows to make more reliable transmissions in dense ad hoc sensor networks

APA, Harvard, Vancouver, ISO, and other styles

22

El, Ali Farah. "Communication unicast dans les réseaux mobiles dynamiques." Phd thesis, Université de Technologie de Compiègne, 2012. http://tel.archives-ouvertes.fr/tel-00795923.

Full text

Abstract:

Les communications sont difficiles à maintenir dans les réseaux informatiques quand ils sont dynamiques. Les réseaux de véhicules sont un exemple direct de ces réseaux ad hoc dynamiques. Dans ce manuscrit, nous nous intéressons aux communications unicast dans les réseaux ad hoc dynamiques (réseaux véhiculaires en particulier). Nous avons effectué des tests sur route afin d'analyser les performances de ces réseaux. Les résultats nous ont permis de proposer des améliorations aux communications V2I et V2V. Vue l'étude des performances, nous avons opté pour une architecture opportuniste pour les communications V2I (remontée des données du réseau véhiculaire vers l'infrastructure via une passerelle). Pour les communications V2V, la source et la destination sont mobiles. La communication est alors menacée d'être interrompue. Nous proposons un algorithme de maintien de chemin qui garantit l'acheminement des messages entre les deux entités en mouvement dans le réseau. Cet algorithme utilise les échanges locaux pour ajuster le chemin, et s'affranchit ainsi de la dynamique du réseau. Pour mieux comprendre les limites du routage en général et de notre algorithme de maintien de chemin en particulier, nous utilisons l'approche " best effort " qui formalise un compromis entre la dynamique du réseau et les propriétés d'un algorithme. Nous introduisons les graphes p-dynamiques pour caractériser la dynamique. Ils permettent alors d'exprimer une propriété dite topologique, qui est nécessaire pour garantir une propriété dite de continuité du service offert par l'algorithme. Cette approche de modélisation constitue un premier pas vers une métrique algorithmique de la dynamique des réseaux.

APA, Harvard, Vancouver, ISO, and other styles

23

Kaisser, Florent. "Communications dans les réseaux fortement dynamiques." Phd thesis, Université Paris Sud - Paris XI, 2010. http://tel.archives-ouvertes.fr/tel-00512021.

Full text

Abstract:

Les réseaux de véhicules sont une technologie émergente intégrant les dernières techniques de communication. Sans infrastructure, le réseau est un réseau dit ad hoc, un protocole de routage doit donc être utilisé pour assurer les communications inter-véhiculaires. Nous appelons ce type de réseau, un réseau ad hoc de véhicules. Nos travaux s'articulent autour de deux axes : le passage à l'échelle et la gestion de la mobilité dans un contexte autoroutier. Pour cela, nous avons proposé une extension du protocole de routage ad hoc DSR pour les réseaux ad hoc hybride (comportant une infrastructure fixe). Des simulations à l'aide de JiST/SWANS ont montré une amélioration des performances en terme de passage à l'échelle, connectivité et capacité du réseau. Nous avons également établi un modèle analytique pour comparer le passage à l'échelle de deux classes de protocoles de routage : réactif et géographique. Nous concluons que l'utilisation d'un protocole géographique et ses optimisations améliore de manière significative le passage à l'échelle. Enfin, nous proposons un algorithme répartie de formation de convois de véhicules afin d'améliorer la gestion de la mobilité dans un contexte de réseau ad hoc hybride de véhicules sur autoroute. Nous avons évalué cet algorithme à l'aide de simulations et conclu à une bonne qualité de formation des convois.

APA, Harvard, Vancouver, ISO, and other styles

24

Günther, Marco. "Algorithmen und Techniken in Ad-Hoc-Netzwerken." Universitätsbibliothek Chemnitz, 2002. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-200200386.

Full text

Abstract:

Gemeinsamer Workshop von Universitaetsrechenzentrum und Professur Rechnernetze und verteilte Systeme der Fakultaet fuer Informatik der TU Chemnitz. Der Vortrag bietet eine kurze Einführung in die Welt der Ad-Hoc-Netzwerke.

APA, Harvard, Vancouver, ISO, and other styles

25

Yeung, Chun. "A PERFORMANCE COMPARISON OF CLUSTERING ALGORITHMS IN AD HOCNETWORKS." Master's thesis, University of Central Florida, 2006. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/2393.

Full text

Abstract:

An ad hoc network is comprised of wireless mobile nodes without the need of wired network infrastructure. Due to the limited transmission range of nodes, the exchange of data between them may not be possible using direct communication. Partitioning the network into clusters and electing a clusterhead for each cluster to assist with the resource allocation and data packet transmissions among its members and neighboring clusterheads is one of the most common ways of providing support for the existing ad hoc routing protocols. This thesis presents the performance comparison of four ad hoc network clustering protocols: Dynamic Mobile Adaptive Clustering (DMAC), Highest-Degree and Lowest-ID algorithms, and Weighted Clustering Algorithm (WCA). Yet Another Extensible Simulation (YAES) was used as the simulator to carry out the simulations.
M.S.Cp.E.
School of Electrical Engineering and Computer Science
Engineering and Computer Science
Computer Engineering

APA, Harvard, Vancouver, ISO, and other styles

26

Xie, Qiling. "Energy efficient routing in ad hoc networks /." View Abstract or Full-Text, 2003. http://library.ust.hk/cgi/db/thesis.pl?ELEC%202003%20XIE.

Full text

Abstract:

Thesis (M. Phil.)--Hong Kong University of Science and Technology, 2003.
Includes bibliographical references (leaves 76-79). Also available in electronic version. Access restricted to campus users.

APA, Harvard, Vancouver, ISO, and other styles

27

Srivastava, Gaurav. "Efficient topology control algorithms for ad hoc networks." Access electronically, 2006. http://www.library.uow.edu.au/adt-NWU/public/adt-NWU20080506.144718/index.html.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Nguyen, Le Huy. "Auto-stabilisation et partitionnement dans les réseaux Ad Hoc." Paris 11, 2007. http://www.theses.fr/2007PA112205.

Full text

Abstract:

Le problème de partitionnement consiste à partitionner les nœuds d’un réseau en grappes donc donner au réseau une organisation hiérarchique. L’auto-stabilisation est une approche qui tolère les défaillances transitoires. Cette approche tolère une interruption temporaire du service du système et un comportement inconsistant de certains processeurs, mais garantit un retour à la normale au bout d’un temps fini. Basagni a proposé deux algorithmes de partitionnement (appelés DMAC et GDMAC) dans un réseau ad hoc. Cependant ils ne sont pas auto-stabilisants. Dans un premier temps nous avons proposé une version auto-stabilisante de DMAC et GDMAC. Dans l’auto-stabilisation, aucune propriété n’est garantie durant la phase de convergence. Donc le système peut avoir un comportement complètement arbitraire durant toute la phase de convergence. Dans un deuxième temps nous avons présenté une version robuste de l’algorithme auto-stabilisant GDMAC. La propriété de robustesse garantit que, à partir d’un état arbitraire, très rapidement le réseau est partitionné en grappes. Ensuite, le système continue à construire une partition optimale. Dans le dernier temps nous avons proposé le premier algorithme auto-stabilisant de partitionnement où les grappes ont une taille bornée. Une borne sur la taille d’une grappe assure que les leaders ne sont pas surchargés par leurs tâches de leader
The clustering problem consists in partitioning network nodes into groups called clusters, thus giving at the network a hierarchical organization. The self-stabilization is an approach which tolerates to the transient faults. This approach tolerates a temporary interruption of the system service and an inconsistent behavior of several processors, but guarantees a return to the normal in finite time. Basagni proposed two clustering algorithms (called DMAC and GDMAC) in an Ad Hoc network. However they are not self-stabilizing. In the first time we proposed a self-stabilizing version of DMAC and GDMAC. In the self-stabilization, no property is guaranteed during the phase of convergence. In the second time we presented a robust version of the self-stabilizing algorithm GDMAC. The property of robustness guarantees that, starting from an arbitrary state, very quickly the network is partitioned into clusters. Then the system continues to build an optimal partition. In the last time we proposed the first self-stabilizing clustering algorithm where the clusters have a bounded size. A bound on the size of a cluster ensures that the leaders are not overloaded by their tasks of leader

APA, Harvard, Vancouver, ISO, and other styles

29

Liu, Zhenyu. "Swarm-based routing algorithms for mobile ad hoc networks." Thesis, University of Birmingham, 2007. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.487220.

Full text

Abstract:

There have been many approaches to solving the routing problem for mobile ad hoc networks. In existing approaches, routing information is disseminated at the network-scale level to maintain routing connectivity, which leads to the scalability problem as the network size increases. In this thesis, we present an innovative, self-organised routing infrastructure called EARA (Emergent Ad hoc Routing Algorithm), inspired by the foraging behaviour of ant colonies, for mobile ad hoc networks. This routing scheme uses the self-organising mechanisms of positive/negative feedback and random fluctuations to reinforce good quality paths by means of local interaction, without using global network-scale message dissemination. We demonstrate that the proposed routing scheme improves algorithm scalability. Moreover, optimisations employing aspects of the crosslayer design and service-classification based queuing strategy are also investigated in order to address the congestion control and Quality-of-Service provisioning. The thesis presents not only the design of the swarm-based routing algorithms, but also the empirical analysis of performance of the proposed algorithms under a variety of scenarios using simulations.

APA, Harvard, Vancouver, ISO, and other styles

30

Ng, Kok-Poh. "Energy-efficient algorithms for ad hoc wireless sensor networks." Thesis, University of Newcastle upon Tyne, 2018. http://hdl.handle.net/10443/4028.

Full text

Abstract:

The interest in ad hoc Wireless Sensor Networks (WSN) has been growing rapidly in the past few years due to its wide range of applications in Environment Monitoring and Forecasting, Health and Medical Care, Underwater Communications, Smart Energy, and Building and Home Automation industries. The performance of different network protocols, as well as their sensitivity and the effect of different network parameters, needs to be studied and evaluated for the implementation of WSN with the right protocols and optimal parameters. With the increasing deployment of unmanned and energy-constrained sensor devices in large-scale wireless sensor networks, energy efficiency and network lifetime have become key considerations in designing WSN routing protocols. In this work, we propose a fully distributed, multi-path load-balancing routing protocol based on Dynamic Source Routing (DSR) to improve network lifetime performance. The new protocol is simulated in ns-2 and compared with the commonly used Destination- Sequenced Distance Vector (DSDV), Ad hoc On-Demand Distance Vector (AODV) and DSR protocols. The simulation results show that the new routing protocol improves network lifetime significantly without sacrificing packet delivery performance. Another major source of energy wastage is the idle listening of sensor nodes in the MAC layer. Different variants of synchronous duty-cycle MAC protocols have been designed for WSNs to reduce MAC layer energy consumption. However, the synchronisation process of theses protocols remains a significant contributor to the energy consumption. Energy consumption models of duty-cycle MAC protocols in single-hop neighbourhoods are first developed and analysed. A new synchronisation algorithm, 1-Sync, is proposed to address the high energy consumption problem of the existing fixed periodic synchronisation (F-Sync) algorithm, and the Intelligent Network Synchronisation (INS) algorithm. The analysis and simulation results have shown that the proposed 1-Sync algorithm yields better energy performance than the F-Sync and INS algorithms in both low and high density neighbourhoods. ii In large multi-neighbourhood networks, the above synchronisation algorithms are inadequate in handling high density, high drift, and low duty-cycle operations. An adaptive energy-efficient synchronisation algorithm referred to as C-Sync, is proposed. C-Sync reduces energy consumption by adaptively regulating the synchronisation traffic and the wakeup period based on the changing network neighbourhood conditions through counter-based and exponential-smoothing algorithms. Extensive simulations of multi-hop multi-neighbourhood network scenarios are performed using ns-2; the simulation results have shown that C-Sync outperforms F-Sync and 1-Sync in energy efficiency, packet delivery ratio, and end-to-end packet delay over a wide range of node densities, drift rates and duty cycles.

APA, Harvard, Vancouver, ISO, and other styles

31

Yu, Dongxiao, and 于东晓. "Distributed algorithmic studies in wireless ad hoc networks." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2014. http://hdl.handle.net/10722/206656.

Full text

Abstract:

It has been envisioned that in the near future, wireless ad hoc networks would populate various application fields, ranging from disaster relief, environmental monitoring, surveillance, to medical applications, the observation of chemical and biological processes and community mesh networks. The decentralized and self-organizing nature of wireless ad hoc networks makes distributed algorithms fit very well in these networks, which however pose great challenges to the algorithm designers as they try to achieve optimal efficiency in communications. In this thesis, I develop a set of distributed algorithms addressing these challenges and solving some fundamental communication problems in wireless ad hoc networks. Communications in wireless ad hoc networks happen on a shared medium, and consequently are subject to interference. The first part of the thesis focuses on disseminating information on multiple-access channels while avoiding collisions. For both single-channel and multi-channel networks, the complexity of information dissemination is investigated, and nearly optimal distributed algorithms are proposed. The second part of the thesis focuses on designing efficient distributed algorithms for some fundamental problems under the physical Signal-to-Interference-plus-Noise-Ratio (SINR) interference model. The SINR model defines global fading interference with which the success of a signal reception depends on all simultaneous transmissions. Compared with graph based models, the SINR model reflects the fading and cumulative nature of radio signals. Hence, the SINR model represents the physical reality more precisely. However, the global nature of the SINR model makes the analysis of distributed algorithms much more challenging. Two types of fundamental problems are addressed in this part. The first type is closely related to communication coordination, including the wireless link scheduling problem and the node coloring problem. The second type of problems are about basic communication primitives, including the local broadcasting problem and the multiple-message broadcast problem. I investigate the complexity of these fundamental problems under the SINR interference model, and present efficient or optimal distributed algorithms. In the third part of the thesis, I propose a general interference model that can include commonly adopted interference models as special cases, and study whether efficient distributed algorithms can still be designed and analyzed in such a general model. Specifically, the affectance model is proposed in this part, which depicts the relative interference (affectance) on communication links caused by transmitting nodes. Both graph based models and the SINR model can be transformed into the affectance model. Under this general model, distributed algorithms with worst-case guarantees for the local broadcasting problem are presented. I also show how to make use of the developed techniques to get nearly optimal algorithms under the graph based model and the SINR model.
published_or_final_version
Computer Science
Doctoral
Doctor of Philosophy

APA, Harvard, Vancouver, ISO, and other styles

32

Sun, Yijiang. "Distributed scheduling in multihop ad hoc networks." Click to view the E-thesis via HKUTO, 2008. http://sunzi.lib.hku.hk/HKUTO/record/B39558289.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Sun, Yijiang, and 孫一江. "Distributed scheduling in multihop ad hoc networks." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2008. http://hub.hku.hk/bib/B39558289.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Ahmed, Tarek Helmi Abd el-Nabi Ali. "Modeling and simulation of routing protocol for ad hoc networks combining queuing network analysis and ANT colony algorithms." [S.l. : s.n.], 2005. http://deposit.ddb.de/cgi-bin/dokserv?idn=974552534.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Pradhan, Pushkar P. "Efficient group membership algorithm for ad hoc networks." [Gainesville, Fla.] : University of Florida, 2002. http://purl.fcla.edu/fcla/etd/UFE0000593.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Monti, Gabriele <1978&gt. "Management and routing algorithms for ad-hoc and sensor networks." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2008. http://amsdottorato.unibo.it/928/.

Full text

Abstract:

Large scale wireless adhoc networks of computers, sensors, PDAs etc. (i.e. nodes) are revolutionizing connectivity and leading to a paradigm shift from centralized systems to highly distributed and dynamic environments. An example of adhoc networks are sensor networks, which are usually composed by small units able to sense and transmit to a sink elementary data which are successively processed by an external machine. Recent improvements in the memory and computational power of sensors, together with the reduction of energy consumptions, are rapidly changing the potential of such systems, moving the attention towards datacentric sensor networks. A plethora of routing and data management algorithms have been proposed for the network path discovery ranging from broadcasting/floodingbased approaches to those using global positioning systems (GPS). We studied WGrid, a novel decentralized infrastructure that organizes wireless devices in an adhoc manner, where each node has one or more virtual coordinates through which both message routing and data management occur without reliance on either flooding/broadcasting operations or GPS. The resulting adhoc network does not suffer from the deadend problem, which happens in geographicbased routing when a node is unable to locate a neighbor closer to the destination than itself. WGrid allow multidimensional data management capability since nodes' virtual coordinates can act as a distributed database without needing neither special implementation or reorganization. Any kind of data (both single and multidimensional) can be distributed, stored and managed. We will show how a location service can be easily implemented so that any search is reduced to a simple query, like for any other data type. WGrid has then been extended by adopting a replication methodology. We called the resulting algorithm WRGrid. Just like WGrid, WRGrid acts as a distributed database without needing neither special implementation nor reorganization and any kind of data can be distributed, stored and managed. We have evaluated the benefits of replication on data management, finding out, from experimental results, that it can halve the average number of hops in the network. The direct consequence of this fact are a significant improvement on energy consumption and a workload balancing among sensors (number of messages routed by each node). Finally, thanks to the replications, whose number can be arbitrarily chosen, the resulting sensor network can face sensors disconnections/connections, due to failures of sensors, without data loss. Another extension to {WGrid} is {W*Grid} which extends it by strongly improving network recovery performance from link and/or device failures that may happen due to crashes or battery exhaustion of devices or to temporary obstacles. W*Grid guarantees, by construction, at least two disjoint paths between each couple of nodes. This implies that the recovery in W*Grid occurs without broadcasting transmissions and guaranteeing robustness while drastically reducing the energy consumption. An extensive number of simulations shows the efficiency, robustness and traffic road of resulting networks under several scenarios of device density and of number of coordinates. Performance analysis have been compared to existent algorithms in order to validate the results.

APA, Harvard, Vancouver, ISO, and other styles

37

Kim, Jinguk. "Energy-time efficient routing algorithms for mobile ad hoc networks." Thesis, Goldsmiths College (University of London), 2013. http://research.gold.ac.uk/9613/.

Full text

Abstract:

Mobile Ad Hoc Networks (MANETs) are one of the fastest growing technologies in wireless communication. Many routing algorithms have been proposed and developed to find and maintain routes between two mobile nodes. The most well known reactive routing algorithms, such as Dynamic Source Routing (DSR) and Ad hoc On demand Distance Vector (AODV), use a so-called Expanding Ring Search (ERS) technique in the route discovery process to find a valid route. However, in ERS, each time a source node fails to find the destination node, the source node needs to broadcast a Route Request (RREQ) packet and start the flooding procedure over again. Moreover, the ERS cannot stop the propagation of the RREQ packet until the pre defined Time-To-Live (TTL) value of ERS has expired (i.e when the TTL value reaches to zero). Finally, ERS does not consider any movements of the nodes. In this thesis, energy-time efficient routing algorithms are investigated for the route discovery process. Two efficient routing algorithms are developed, namely Blocking Expanding Ring Search (BERS) and Mobility Based Blocking Expanding Ring Search (MBERS). The BERS is proposed to reduce some energy waste in ERS during route discovery process. The MBERS is proposed to take into consideration of node movements, and was developed to save energy and time by controlling the transmission range, and the use of the maximum lifetime of the route. The performance of the two proposed routing algorithms are evaluated using both mathematical and simulation methods. The results show that the two proposed algorithms are more efficient than the ERS in terms of saving energy and time. The contributions of the thesis can be summarized as follows: 1. The tradeoff between the energy efficiency and time delay is discussed and two models, namely the Cost Model and Trade Model, are proposed to quantify the combined effect of energy-time efficiency. 2. The route discovery algorithm “BERS” is proposed to decrease energy consumption by reducing the number of packets sent over the network. The performance evaluations of the ERS and BERS are provided in terms of energy consumption, time delay, and energy-time efficiency. An analysis is performed between the Dual Tier Chase (DTC) algorithm and BERS as an initial attempt. 3. The route discovery algorithm “MBERS” is proposed to take into consideration the node movements and the selection of a maximum lifetime of the route which were not considered in BERS. The performance evaluations of the BERS and the MBERS algorithms are provided in terms of energy consumption, time delay, and energy-time efficiency.

APA, Harvard, Vancouver, ISO, and other styles

38

Mohan, Divya. "Dynamic spectrum allocation algorithms in large wireless ad hoc networks." Thesis, University of Bristol, 2018. https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.738326.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Di, Caro Gianni. "Ant colony optimization and its application to adaptive routing in telecommunication networks." Doctoral thesis, Universite Libre de Bruxelles, 2004. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/211149.

Full text

Abstract:

In ant societies, and, more in general, in insect societies, the activities of the individuals, as well as of the society as a whole, are not regulated by any explicit form of centralized control. On the other hand, adaptive and robust behaviors transcending the behavioral repertoire of the single individual can be easily observed at society level. These complex global behaviors are the result of self-organizing dynamics driven by local interactions and communications among a number of relatively simple individuals.

The simultaneous presence of these and other fascinating and unique characteristics have made ant societies an attractive and inspiring model for building new algorithms and new multi-agent systems. In the last decade, ant societies have been taken as a reference for an ever growing body of scientific work, mostly in the fields of robotics, operations research, and telecommunications.

Among the different works inspired by ant colonies, the Ant Colony Optimization metaheuristic (ACO) is probably the most successful and popular one. The ACO metaheuristic is a multi-agent framework for combinatorial optimization whose main components are: a set of ant-like agents, the use of memory and of stochastic decisions, and strategies of collective and distributed learning.

It finds its roots in the experimental observation of a specific foraging behavior of some ant colonies that, under appropriate conditions, are able to select the shortest path among few possible paths connecting their nest to a food site. The pheromone, a volatile chemical substance laid on the ground by the ants while walking and affecting in turn their moving decisions according to its local intensity, is the mediator of this behavior.

All the elements playing an essential role in the ant colony foraging behavior were understood, thoroughly reverse-engineered and put to work to solve problems of combinatorial optimization by Marco Dorigo and his co-workers at the beginning of the 1990's.

From that moment on it has been a flourishing of new combinatorial optimization algorithms designed after the first algorithms of Dorigo's et al. and of related scientific events.

In 1999 the ACO metaheuristic was defined by Dorigo, Di Caro and Gambardella with the purpose of providing a common framework for describing and analyzing all these algorithms inspired by the same ant colony behavior and by the same common process of reverse-engineering of this behavior. Therefore, the ACO metaheuristic was defined a posteriori, as the result of a synthesis effort effectuated on the study of the characteristics of all these ant-inspired algorithms and on the abstraction of their common traits.

The ACO's synthesis was also motivated by the usually good performance shown by the algorithms (e.g. for several important combinatorial problems like the quadratic assignment, vehicle routing and job shop scheduling, ACO implementations have outperformed state-of-the-art algorithms).

The definition and study of the ACO metaheuristic is one of the two fundamental goals of the thesis. The other one, strictly related to this former one, consists in the design, implementation, and testing of ACO instances for problems of adaptive routing in telecommunication networks.

This thesis is an in-depth journey through the ACO metaheuristic, during which we have (re)defined ACO and tried to get a clear understanding of its potentialities, limits, and relationships with other frameworks and with its biological background. The thesis takes into account all the developments that have followed the original 1999's definition, and provides a formal and comprehensive systematization of the subject, as well as an up-to-date and quite comprehensive review of current applications. We have also identified in dynamic problems in telecommunication networks the most appropriate domain of application for the ACO ideas. According to this understanding, in the most applicative part of the thesis we have focused on problems of adaptive routing in networks and we have developed and tested four new algorithms.

Adopting an original point of view with respect to the way ACO was firstly defined (but maintaining full conceptual and terminological consistency), ACO is here defined and mainly discussed in the terms of sequential decision processes and Monte Carlo sampling and learning.

More precisely, ACO is characterized as a policy search strategy aimed at learning the distributed parameters (called pheromone variables in accordance with the biological metaphor) of the stochastic decision policy which is used by so-called ant agents to generate solutions. Each ant represents in practice an independent sequential decision process aimed at constructing a possibly feasible solution for the optimization problem at hand by using only information local to the decision step.

Ants are repeatedly and concurrently generated in order to sample the solution set according to the current policy. The outcomes of the generated solutions are used to partially evaluate the current policy, spot the most promising search areas, and update the policy parameters in order to possibly focus the search in those promising areas while keeping a satisfactory level of overall exploration.

This way of looking at ACO has facilitated to disclose the strict relationships between ACO and other well-known frameworks, like dynamic programming, Markov and non-Markov decision processes, and reinforcement learning. In turn, this has favored reasoning on the general properties of ACO in terms of amount of complete state information which is used by the ACO's ants to take optimized decisions and to encode in pheromone variables memory of both the decisions that belonged to the sampled solutions and their quality.

The ACO's biological context of inspiration is fully acknowledged in the thesis. We report with extensive discussions on the shortest path behaviors of ant colonies and on the identification and analysis of the few nonlinear dynamics that are at the very core of self-organized behaviors in both the ants and other societal organizations. We discuss these dynamics in the general framework of stigmergic modeling, based on asynchronous environment-mediated communication protocols, and (pheromone) variables priming coordinated responses of a number of ``cheap' and concurrent agents.

The second half of the thesis is devoted to the study of the application of ACO to problems of online routing in telecommunication networks. This class of problems has been identified in the thesis as the most appropriate for the application of the multi-agent, distributed, and adaptive nature of the ACO architecture.

Four novel ACO algorithms for problems of adaptive routing in telecommunication networks are throughly described. The four algorithms cover a wide spectrum of possible types of network: two of them deliver best-effort traffic in wired IP networks, one is intended for quality-of-service (QoS) traffic in ATM networks, and the fourth is for best-effort traffic in mobile ad hoc networks.

The two algorithms for wired IP networks have been extensively tested by simulation studies and compared to state-of-the-art algorithms for a wide set of reference scenarios. The algorithm for mobile ad hoc networks is still under development, but quite extensive results and comparisons with a popular state-of-the-art algorithm are reported. No results are reported for the algorithm for QoS, which has not been fully tested. The observed experimental performance is excellent, especially for the case of wired IP networks: our algorithms always perform comparably or much better than the state-of-the-art competitors.

In the thesis we try to understand the rationale behind the brilliant performance obtained and the good level of popularity reached by our algorithms. More in general, we discuss the reasons of the general efficacy of the ACO approach for network routing problems compared to the characteristics of more classical approaches. Moving further, we also informally define Ant Colony Routing (ACR), a multi-agent framework explicitly integrating learning components into the ACO's design in order to define a general and in a sense futuristic architecture for autonomic network control.

Most of the material of the thesis comes from a re-elaboration of material co-authored and published in a number of books, journal papers, conference proceedings, and technical reports. The detailed list of references is provided in the Introduction.

Doctorat en sciences appliquées
info:eu-repo/semantics/nonPublished

APA, Harvard, Vancouver, ISO, and other styles

40

Li, Xiaoli. "A map-growing localization algorithm for ad-hoc sensor networks /." free to MU campus, to others for purchase, 2003. http://wwwlib.umi.com/cr/mo/fullcit?p1418044.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Fritsch, Serena. "Erweiterung eines adaptiven und interaktiven Systems für die Analyse von Algorithmen zur Datenverwaltung in mobilen Ad-hoc-Netzen." [S.l. : s.n.], 2004. http://www.bsz-bw.de/cgi-bin/xvms.cgi?SWB11730066.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Hähner, Jörg. "Consistent data replication in mobile ad hoc networks." [S.l. : s.n.], 2007. http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-29798.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Dhillon, Santpal Singh. "Ant routing, searching and topology estimation algorithms for ad hoc networks /." Amsterdam : IOS Press, 2008. http://opac.nebis.ch/cgi-bin/showAbstract.pl?u20=9781586039011.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Guo, Song. "Energy-efficient broadcast and multicast algorithms in wireless ad hoc networks." Thesis, University of Ottawa (Canada), 2006. http://hdl.handle.net/10393/29331.

Full text

Abstract:

This thesis systematically explores two fundamental classes of energy-efficient broadcast/multicast problem: the BPM/MPM (Broadcast/Multicast Power Minimization) problem and the BLM/MLM (Broadcast/Multicast Lifetime Maximization) problem. For the first class of problem, we have developed a general analytical MILP (Mixed Integer Linear Programming) model for the MPM problem in an ad hoc network with adaptive antennas, and also implemented a group of polynomial-time algorithms practically to handle significantly large networks for which the MILP model may not be computationally efficient. For the second problem, we have first used theoretical analysis to derive two polynomial-time optimal algorithms for the MLM/BLM problem in the omni-directional antenna scenarios. We then study the same problem with directional antennas, and conjecture that this problem is NP-hard. Based on the same analytical model, we have developed a constraint formulation for the MLM/BLM problem in terms of MILP, and also implemented a group of polynomial-time algorithms practically. Finally, we consider the same problems in mobile ad hoc networks (MANETs) and propose several distributed algorithms. Several localized operations are presented for our distributed algorithms, in which each node requires only the knowledge of its distance to all neighboring nodes and distances between its neighboring nodes. Through extensive simulation study, we show that these distributed algorithms are very efficient both in terms of energy (power or lifetime) and operation overhead.

APA, Harvard, Vancouver, ISO, and other styles

45

Al-Rodhaan, Mznah A. "Traffic locality oriented route discovery algorithms for mobile ad hoc networks." Thesis, University of Glasgow, 2009. http://theses.gla.ac.uk/899/.

Full text

Abstract:

There has been a growing interest in Mobile Ad hoc Networks (MANETs) motivated by the advances in wireless technology and the range of potential applications that might be realised with such technology. Due to the lack of an infrastructure and their dynamic nature, MANETs demand a new set of networking protocols to harness the full benefits of these versatile communication systems. Great deals of research activities have been devoted to develop on-demand routing algorithms for MANETs. The route discovery processes used in most on-demand routing algorithms, such as the Dynamic Source Routing (DSR) and Ad hoc On-demand Distance Vector (AODV), rely on simple flooding as a broadcasting technique for route discovery. Although simple flooding is simple to implement, it dominates the routing overhead, leading to the well-known broadcast storm problem that results in packet congestion and excessive collisions. A number of routing techniques have been proposed to alleviate this problem, some of which aim to improve the route discovery process by restricting the broadcast of route request packets to only the essential part of the network. Ideally, a route discovery should stop when a receiving node reports a route to the required destination. However, this cannot be achieved efficiently without the use of external resources; such as GPS location devices. In this thesis, a new locality-oriented route discovery approach is proposed and exploited to develop three new algorithms to improve the route discovery process in on-demand routing protocols. The proposal of our algorithms is motivated by the fact that various patterns of traffic locality occur quite naturally in MANETs since groups of nodes communicate frequently with each other to accomplish common tasks. Some of these algorithms manage to reduce end-to-end delay while incurring lower routing overhead compared to some of the existing algorithms such as simple flooding used in AODV. The three algorithms are based on a revised concept of traffic locality in MANETs which relies on identifying a dynamic zone around a source node where the zone radius depends on the distribution of the nodes with which that the source is “mostly” communicating. The traffic locality concept developed in this research form the basis of our Traffic Locality Route Discovery Approach (TLRDA) that aims to improve the routing discovery process in on-demand routing protocols. A neighbourhood region is generated for each active source node, containing “most” of its destinations, thus the whole network being divided into two non-overlapping regions, neighbourhood and beyond-neighbourhood, centred at the source node from that source node prospective. Route requests are processed normally in the neighbourhood region according to the routing algorithm used. However, outside this region various measures are taken to impede such broadcasts and, ultimately, stop them when they have outlived their usefulness. The approach is adaptive where the boundary of each source node’s neighbourhood is continuously updated to reflect the communication behaviour of the source node. TLRDA is the basis for the new three route discovery algorithms; notably: Traffic Locality Route Discovery Algorithm with Delay (TLRDA D), Traffic Locality Route Discovery Algorithm with Chase (TLRDA-C), and Traffic Locality Expanding Ring Search (TL-ERS). In TLRDA-D, any route request that is currently travelling in its source node’s beyond-neighbourhood region is deliberately delayed to give priority to unfulfilled route requests. In TLRDA-C, this approach is augmented by using chase packets to target the route requests associated with them after the requested route has been discovered. In TL-ERS, the search is conducted by covering three successive rings. The first ring covers the source node neighbourhood region and unsatisfied route requests in this ring trigger the generation of the second ring which is double that of the first. Otherwise, the third ring covers the whole network and the algorithm finally resorts to flooding. Detailed performance evaluations are provided using both mathematical and simulation modelling to investigate the performance behaviour of the TLRDA D, TLRDA-C, and TL-ERS algorithms and demonstrate their relative effectiveness against the existing approaches. Our results reveal that TLRDA D and TLRDA C manage to minimize end-to-end packet delays while TLRDA-C and TL-ERS exhibit low routing overhead. Moreover, the results indicate that equipping AODV with our new route discovery algorithms greatly enhance the performance of AODV in terms of end to end delay, routing overhead, and packet loss.

APA, Harvard, Vancouver, ISO, and other styles

46

Denson, D. Paul. "Modeling and performance analysis for mobile group localization and formation." Laramie, Wyo. : University of Wyoming, 2008. http://proquest.umi.com/pqdweb?did=1594486491&sid=1&Fmt=2&clientId=18949&RQT=309&VName=PQD.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Lai, Kai-Ming. "Strategic message forwarding on wireless ad-hoc networks /." View abstract or full-text, 2008. http://library.ust.hk/cgi/db/thesis.pl?ECED%202008%20LAI.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Yuan, Yin. "Transmission power control in wireless ad-hoc networks /." View abstract or full-text, 2008. http://library.ust.hk/cgi/db/thesis.pl?ECED%202008%20YUAN.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Lim, Léon. "Gestion de groupe partitionnable dans les réseaux mobiles spontanés." Thesis, Evry, Institut national des télécommunications, 2012. http://www.theses.fr/2012TELE0032/document.

Full text

Abstract:

Dans les réseaux mobiles spontanés (en anglais, Mobile Ad hoc NETworks ou MANETs), la gestion de groupe partitionnable est un service de base permettant la construction d'applications réparties tolérantes au partitionnement. Aucune des spécifications existantes ne satisfait les deux exigences antagonistes suivantes : 1) elle doit être assez forte pour fournir des garanties utiles aux applications réparties dans les systèmes partitionnables ; 2) elle doit être assez faible pour être résoluble. Dans cette thèse, nous proposons une solution à la gestion de groupe partitionnable en environnements réseaux très dynamiques tels que les MANETs. Pour mettre en œuvre notre solution, nous procédons en trois étapes. Tout d'abord, nous proposons un modèle de système réparti dynamique qui caractérise la stabilité dans les MANETs. Ensuite, nous adaptons pour les systèmes partitionnables l'approche Paxos à base de consensus Synod. Cette adaptation résulte en la spécification d'un consensus abandonnable AC construit au-dessus d'un détecteur ultime des α participants d'une partition ♢PPD et d'un registre ultime par partition ♢RPP. ♢PPD garantit la vivacité dans une partition même si la partition n'est pas complètement stable tandis que ♢RPP préserve la sûreté dans la même partition. Enfin, la gestion de groupe partitionnable est résolue en la transformant en une séquence d'instances de AC. Chacun des modules ♢PPD, ♢RPP, AC et gestion de groupe partitionnable est implanté et prouvé. Par ailleurs, nous analysons les performances de ♢PPD par simulation
In Mobile Ad hoc NETworks or MANETs, partitionable group membership is a basic service for building partition-tolerant applications. None of the existing specifications satisfy the two following antagonistic requirements: 1) it must be strong enough to simplify the design of partition-tolerant distributed applications in partitionable systems; 2) it must be weak enough to be implantable. In this thesis, we propose a solution to partitionable group membership in very dynamic network environment such as MANETs. To this means, we proceed in three steps. First, we develop a dynamic distributed system model that characterises stability in MANETs. Then, we propose a solution to the problem of partitionable group membership by adapting Paxos for such systems. This adatation results in a specification of abortable consensus AC which is composed of an eventual α partition-participants detector ♢PPD and an eventual register per partition ♢RPP. ♢PPD guarantees liveness in a partition even if the partition is not completely stable whereas ♢RPP ensures safety in the same partition. Finally, partitionable group membership is solved by transforming it into a sequence of abortable consensus instances AC. Each of the modules ♢PPD, ♢RPP, AC, and partitionable group membership is implanted and proved. Next, we analyse the performances of ♢PPD by simulation

APA, Harvard, Vancouver, ISO, and other styles

50

Miranda, Hugo. "Gossip-Based Data Distribution in Mobile Ad Hoc Networks." Doctoral thesis, Department of Informatics, University of Lisbon, 2007. http://hdl.handle.net/10451/14290.

Full text

Abstract:

Wireless networks are useful in many different scenarios. They allow to create emergency networks for catastrophe response, wide area surveillance networks in hostile environments, or simply permit users to share information, play on-line games, and surf the Web. Mobile ad hoc networks are a particular case of wireless networks characterised by the absence of a supporting infrastructure.The thesis addresses the problem of building middleware services that permit to fully exploit the opportunities offered by mobile ad hoc networks. For that purpose, it is required to design algorithms that account for the limitations of mobile devices and that make a careful use of the scarce resources available in ad hoc networks. A central middleware service for mobile applications is data sharing. The thesis addresses the use of data replication as a technique to improve data availability and resource savings in mobile ad hoc networks. In particular, the thesis proposes the use of epidemic protocols to achieve these goals. In this context, the thesis presents the following contributions. It presents and evaluates $\i)$ an algorithm to reduce the number of transmissions required in a broadcast, $\ii)$ an algorithms for the geographical distribution of replicas of data items, and $\iii)$ algorithms to attenuate the impact of node movement in the geographical distribution. Finally, the thesis describes an application of the algorithms to build a concrete application, a version of the Session Initiation Protocol for wireless networks

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic 'Algorithmes ad'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles