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

RéSUMé

C

E mémoire traite le problème de la K-exclusion mutuelle dans les réseaux mobiles AD HOC.

Dans ce mémoire nous allons d'abord introduire le concept des systèmes répartis et les réseaux AD HOC, ce qui va nous permettre de mettre l'accent sur le problème de l'exclusion mutuelle, et sa généralisation en K ressources.

Nous proposons également un algorithme traitant le problème de la K-exclusion mutuelle dans les réseaux AD HOC, cet algorithme sera amélioré et validé par une simulation en utilisant l'outil NS-2.

Un 2^ème algorithme qui traite le même problème sera proposé, ce nouvel algorithme permet d'assurer un nombre réduit de messages échangés. L'efficacité de cette solution est prouvée par rapport aux algorithmes déjà évalués.

Mots-clés : Réseaux AD HOC, algorithmique répartie, Exclusion mutuelle, K-exclusion mutuelle, Routage, Simulation, NS-2.

ABSTRACT

T

HIS thesis treats the K-mutual exclusion problem in the AD HOC networks.

In this thesis, we will first introduce the concept of distributed systems and the AD HOC networks, which will allow us to focus on the mutual exclusion problem and its generalization to K resources.

We also propose an algorithm that treats the K-mutual exclusion problem in the AD HOC networks, this algorithm will be improved and validated by a simulation using NS-2 tool.

A second algorithm that treats the same problem will be proposed, this new algorithm ensures a reduced number of messages exchanged. The effectiveness of this solution is proven compared to the algorithms already evaluated.

Key-words : Mobile AD HOC Network (MANET), Distributed algorithm, Mutual exclusion, K-mutual exclusion, Routing, Simulation, NS-2.

TABLE DEs MATièREs

TABLE DEs MATièREs vi

LisTE DEs FiGuREs ix

INTRoDucTioN GéNéRALE 1

1 NoTioNs GéNéRALEs 3

1.1 INTRoDucTioN 4

1.2 LEs sysTèMEs RépARTis 4

1.3 LEs RésEAux MoBiLEs 4

1.3.1 Les réseaux mobiles avec infrastructures 5

1.3.2 Les réseaux mobiles sans infrastructures (AD HOC) 5

1.3.2.1 Définition d'un réseau AD HOC 5

1.3.2.2 Les caractéristiques des réseaux AD HOC 6

1.3.2.3 Les avantages des réseaux AD HOC 7

1.3.2.4 Les inconvénients des réseaux AD HOC 7

1.3.2.5 Les domaines d'applications des réseaux AD HOC 7

1.3.2.6 Les problèmes liés aux réseaux AD HOC 9

1.3.3 Problème de routage dans les réseaux AD HOC 9

1.3.3.1 Définition d'un routage 9

1.3.3.2 Classification des protocoles de routage 9

1.3.3.2.a Les protocoles de routage proactifs 10

1.3.3.2.b Les protocoles de routage réactifs (à la demande) . 10

1.3.3.2.c Les protocoles de routage hybrides 10

1.4 L'ExcLusioN MuTuELLE DANs LEs RésEAux AD HOC 10

1.4.1 L'exclusion mutuelle en réparti 10

1.4.1.1 La notion de l'exclusion mutuelle 10

1.4.1.2 Les états d'un processus 11

1.4.1.3 Notions de base 11

1.4.1.4 Propriétés d'un algorithme d'exclusion mutuelle 11

1.4.1.5 Les classes de solutions d'exclusion mutuelle 12

1.4.1.5.a Algorithmes utilisant des permissions 12

1.4.1.5.b Algorithmes utilisant des jetons 12

1.4.2 Le problème de la K-exclusion mutuelle 12

1.4.2.1 Description du problème 12

1.4.2.2 Résolution du problème 13

1.4.2.2.a Solution utilisant des permissions 13

1.4.2.2.b Solution utilisant des jetons 13

1.4.3 Les solutions de l'EM dans les réseaux ADHOC 13

1.4.4 Les solutions de la K-EM dans les réseaux AD HOC 14

CoNcLusioN 14

2 PRoposiTioN D'uN ALgoRiThME BAsé suR L'ALgoRiThME DE NAiMi ET TREhEL 15

	2.1 2.2	INTRoDucTioN L'ALgoRiThME 2.2.1 Structure logique utilisée 2.2.2 Le principe de fonctionnement 2.2.3 Hypothèses 2.2.4 Description de l'algorithme	16 16 16 17 18 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
3	DiscussioN DEs RésuLTATs DE siMuLATioNs		25
	3.1	INTRoDucTioN	26
	3.2	LE siMuLATEuR NS-2	26
		3.2.1 Présentation de l'outil de simulation	26
	3.3	LEs éTApEs DE siMuLATioN	26
	3.4	CoMMENT RéALisER uNE siMuLATioN?	27
	3.5	LEs pARAMèTREs DE siMuLATioN	29
		3.5.1 Les paramètres fixes	29
		3.5.2 Les paramètres variables	29
	3.6	EvALuATioN DE pERFoRMANcEs	30
	3.7	LEs éTApEs D'uN scéNARio	31
	3.8	RésuLTATs ET iNTERpRéTATioNs	31
		3.8.1 Variation du nombre de requêtes	31
		3.8.2 Variation de la portée de communication	32
		3.8.3 Variation du nombre de ressources	32
		3.8.4 Variation de la vitesse de mouvement	33
		3.8.5 Variation du nombre de sites	33
	3.9	RésuLTATs DEs MoDiFicATioNs	34
		3.9.1 Variation du nombre de requêtes	34
		3.9.2 Variation de la portée de communication	34
		3.9.3 Variation du nombre de ressources	35
		3.9.4 Variation de la vitesse de mouvement	35
		3.9.5 Variation du nombre de sites	35
	CoNcLusioN		36
4	UN NouvEL ALgoRiThME BAsé suR LE pRoTocoLE DE RouTAgE AODV		37
	4.1	L'iDéE DE BAsE	38
	4.2	L'ALgoRiThME	38
		4.2.1 Hypothèses	39
		4.2.2 Description de l'algorithme	39
		4.2.2.1 Les variables locales	39
		4.2.2.2 Les messages utilisés	39
		4.2.2.3 Initialisation des variables	40
		4.2.2.4 Les procédures de l'algorithme	40
		4.2.3 Les paramètres de simulation	42

4.2.4 La comparaison de tous les résultats 43

4.2.4.1 Variation du nombre de requêtes 43

4.2.4.2 Variation de la portée de communication 43

4.2.4.3 Variation du nombre de ressources 43

4.2.4.4 Variation de la vitesse de mouvement 44

4.2.4.5 Variation du nombre de sites 44

CoNcLusIoN 44

CoNcLusIoN ET PERsPEcTIVEs 45

BIBLIoGRAPHIE 47

A ANNEXE : ScRIPT DE sIMuLATIoN 49

A.1 LE ScRIPT TCL 50

AcRoNYMEs 55