Proposition et simulation d'un algorithme de partage de ressources dans les manets basé sur l'algorithme de Naimi et Tréhel

CONCLUSION

Dans ce chapitre nous avons présenté une vue générale des environnements mobiles et en particulier les réseaux AD HOC, nous avons également présenté des notions de base concernant le problème de l'exclusion mutuelle et son extension à K-ressources, enfin nous avons cité les catégories de solutions apportées à ces problèmes.

Dans le chapitre suivant, nous allons décrire notre algorithme proposé dans le cadre de la K-exclusion mutuelle dans les réseaux mobiles AD HOC.

SommAiRE

2.1 INTRoDucTioN	16
2.2 L'ALgoRiThmE	16
2.2.1 Structure logique utilisée	16
2.2.2 Le principe de fonctionnement	17
2.2.3 Hypothèses	18
2.2.4 Description de l'algorithme	18
2.2.4.1 Les variables locales	18
2.2.4.2 Les messages utilisés	19
2.2.4.3 Initialisation des variables	19
2.2.4.4 Les procédures de l'algorithme	19
2.3 MoDiFicATioN N°1	22
2.4 MoDiFicATioN N°2	23
CoNcLusioN	24

C

E chapitre à pour objectif de décrire et d'étudier un algorithme proposé dans le cadre de la K-exclusion mutuelle dans les réseaux AD HOC.

2.1 INTRODUCTiON

Le problème de la K-exclusion mutuelle n'est pas bien traité dans les réseaux mobiles AD HOC, c'est pourquoi il n y a pas beaucoup d'algorithmes qui sont proposés pour résoudre ce problème dans un tel environnement.

C'est la raison pour laquelle nous avons pensé à une nouvelle solution permettant de résoudre le problème de la K-EM dans les réseaux AD HOC.

Dans ce chapitre, nous décrivons le principe de fonctionnement de l'algorithme proposé.

2.2 L'ALGORiTHME

2.2.1 Structure logique utilisée

La structure logique qu'on a adoptée pour notre algorithme est inspirée de l'algorithme de Naimi et Trehel [NT87].

La structure logique de notre algorithme consiste à diviser les sites en K groupes indépendants.

Initialement, chaque groupe à un site détenant un jeton appelé Père, tous les sites du groupe pointe vers ce père, et forme ainsi une arborescence. Ces arbres ne couvrent pas la totalité des sites, par conséquent, certains sites peuvent au début n'appartenir à aucun arbre logique.

Chaque arborescence repose sur la construction dynamique de deux structures de données :

- 1^ère Structure (File de requête {Suivant}) : Consiste a placé toujours le dernier site qui a fait une requête pour la SC à la fin de la file. Alors que le site qui détient le jeton est toujours en tête de la file.

Cette structure est illustrée dans la figure 2.1 ci-dessous :

Figure 2.1 - Structure de la file des requêtes.

- 2^ème Structure (Arbre de chemins vers le dernier demandeur {Père}) : La racine de l'arbre est toujours le dernier demandeur c'est-à-dire le dernier élément de la file des requêtes. Une nouvelle requête est transmise à travers d'un chemin des pointeurs de Père jusqu'à la racine de l'arbre.

Chaque nouveau demandeur devient la nouvelle racine de l'arbre. Et Les sites dont le chemin compris entre la nouvelle et l'ancienne racine changent leur pointeur {Père} vers la nouvelle racine.

On peut illustrée cette structure dans la figure 2.2 :

Figure 2.2 - Structure d'arbre de chemins vers le dernier demandeur.

Les sites n'ont pas une vue globale sur ces structures, un site ne connait que son père et son suivant.