Domaines d’application des réseaux ad hoc

Grands réseaux d’interactions

Domaines d’application des réseaux ad hoc

Les applications des réseaux ad hoc sont nombreuses, l’exemple classique de leur application est dans le domaine militaire et les autres applications de tactique comme les opérations de secours et les missions d’exploration.
Cependant, avec l’avancement des recherches dans le domaine des réseaux et l’émergence des technologies sans fil, d’autres applications civiles sont apparues. On peut distinguer :
Les services d’urgence : opération de recherche et de secours des personnes, tremblement de terre, feux, inondation, dans le but de remplacer l’infrastructure filaire.
Le travail collaboratif et les communications dans des entreprises ou bâtiments : dans le cadre d’une réunion ou d’une conférence par exemple.
Home Network : partage d’applications et communications des équipements mobiles.
Applications commerciales : pour un paiement électronique distant (taxi) ou pour l’accès mobile à l’Internet, où service de guide en fonction de la position de l’utilisateur (GPS sur téléphone mobile).
Réseaux de senseurs (appareils dotés de mécanismes pour relever des informations sur son environnement): pour des applications environnementales (climat, activité de la terre, suivi des mouvements des animaux, etc.) ou domestiques (contrôle des équipements à distance).
Réseaux en mouvement : informatique embarquée et véhicules communicants.
Réseaux Mesh ou Réseaux maillés : c’est une technologie émergente qui permet d’étendre la portée d’un réseau ou de le densifier afin d’accroître la tolérance à d’éventuelles pannes ou interférences.

Caractéristiques et contraintes

Malgré leurs apports, les réseaux ad hoc héritent des mêmes propriétés et problèmes liés aux réseaux sans fil. En effet, le canal radio est limité en termes de capacité, plus exposé aux pertes (comparé au médium filaire), et sujet à des variations dans le temps : la superposition de toutes ces contraintes peut se révéler critique.
On peut tout d’abord citer les problématiques les plus courantes et classiques dont héritent les réseaux ad hoc des réseaux sans fil :
Bande passante limitée : le partage du médium de communication fait que la bande passante allouée à un nœud est faible.
Perte de données et de routes pouvant être générées, entre autres, par les interférences, les collisions et/ou la désactivation/mort d’un nœud se trouvant sur le chemin.
Sécurité limitée : écoute du réseau et en particulier pour récupérer à la volée des informations sensibles lorsqu’elles ne sont pas chiffrées.
Erreurs de transmission ou données erronées dues à rapport signal sur bruit excessivement faible.

Topologies virtuelles dans les réseaux Ad hoc

Différents protocoles de communication, tels que le routage, le partage de ressources, découverte de services, de prédictions … utilisent l’inondation simple pour diffuser ou rassembler de l’information. Pour cette raison, des récents travaux tentent d’optimiser ces échanges de flux de données. Plusieurs études ont proposé de construire et de maintenir des topologies virtuelles dynamiques sur le réseau. Ceci permet d’obtenir une meilleure organisation du réseau. Les avantages d’utilisation de ces structures sont : Diminution de l’impact de la mobilité. En effet, si une couche intermédiaire (une topologie virtuelle) peut offrir une certaine organisation du réseau, la conception des applications pourrait devenir plus facile(en considérant la mobilité).
Optimisation de l’inondation. L’élection de quelques nœuds pour rediffuser les messages, diminue largement le cout de cette dernière.
Amélioration du passage à l’échelle : une conséquence directe des deux points précédents : Une bonne organisation du réseau ne rend son passage à l’échelle que plus efficace. Réduction du temps de réponse. Prise en considération des mécanismes d’équilibrage de charge.

Construction de l’ensemble MIS du graphe G

Plusieurs méthodes ont été proposées pour construire un ensemble MIS d’un graphe. Ces méthodes consistent à extraire un ensemble maximal de nœuds noté MIS tel qu’aucune paire de nœuds de l’ensemble MIS ne se trouvent adjacents dans le graphe, et aucun ensemble indépendant du graphe ne le contient (ensemble indépendant de cardinalité maximale).
Pour construire cet ensemble, on s’inspire de l’algorithme de Goddar et al. qui est un algorithme auto stabilisant en un temps polynomial, ce qui est une bonne propriété dans le contexte des réseaux Ad hoc.
L’Auto-stabilisation est un paradigme pour les systèmes distribués qui permet au système d’atteindre, sans intervention extérieure, un état global correct à partir d’un état quelconque. Ainsi, ces systèmes peuvent partir d’une configuration quelconque pouvant contenir des incohérences introduites par des fautes survenues dans le système et retrouver un comportement correct au bout d’un temps fini.
Chaque nœud u a une variable binaire unique M (u). La règle 1 permet à un nœud de modifier sa valeur si tous les nœuds dans son voisinage fermé (ensemble de ces voisins y compris lui-même) ont la même valeur. La règle 2 permet de modifier sa valeur s’il existe au moins un nœud de son voisinage qui a la même valeur que lui.

Complexité

Nous allons évaluer la complexité totale de notre approche de découverte de communautés d’intérêts dans les réseaux ad hoc, en donnant les complexités des différents algorithmes intervenant dans cette approche, à savoir, l’algorithme de construction de l’ensemble MIS du graphe G(V, E) modélisant le réseau , puis l’algorithme de construction du graphe de couverture de la communauté d’intérêt, et en fin l’algorithme de construction du Karbre couvrant de la communauté.
L’algorithme qu’on a utilisé pour la construction de l’ensemble MIS du graphe G est un algorithme auto stabilisant , les auteurs ont prouvé que cet algorithme retourne un ensemble MIS du graphe au bout d’un temps fini. La complexité en nombre de messages de cet algorithme est O(n), avec n=|V|, le nombre des nœuds du graphe G.
Pour la construction du graphe de couverture de communauté, on a proposé un algorithme distribué dont la complexité en nombre de message est O(n. 2), avec , représente le degré maximum dans le graphe.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela chatpfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Introduction générale
1. Grands réseaux d’interactions
1.1 Introduction
1.2 Domaines concernés
1.3 Propriétés communes
1.4 Conclusion
2. Découverte de communautés
2.1 Introduction
2.2 Définitions communauté
2.3 Représentation graphique des communautés
2.4 Mesures de la qualité de partition d’un réseau en communauté
2.5 Méthodes de découverte de communauté
2.5.1 Approches classiques
2.5.2 Approches séparatives
2.5.3 Approches agglomératives
2.5.4 Autres approches
2.6 Conclusion
3. Topologies virtuelles dans les réseaux ad hoc
3.1 Introduction
3.2 Définition
3.3 Modélisation d’un réseau ad hoc
3.4 Domaines d’application des réseaux ad hoc
3.5 Caractéristiques et contraintes
3.6 Topologies virtuelles dans les réseaux Ad hoc
3.7 Classification des topologies virtuelles dans les réseaux ad hoc
3.7.1 Ensemble de nœuds couvrants
3.7.2 Structures basées liens
3.8 Conclusion
4. Algorithme distribué pour la découverte de communautés d’intérêts dans les réseaux ad hoc
4.1 Introduction
4.2 Modélisation et formulation du problème
4.3 Proposition
4.3.1 Construction de l’ensemble MIS du graphe G
4.3.2 Construction de la topologie virtuelle : graphe de couverture de la communauté CIR
4.3.3 Construction du K-arbre couvrant du graphe de couverture de communauté CIR
4.4 Exemple de déroulement
4.5 Complexité
Conclusion et perspectives