Clusterisation et conservation d’énergie dans les réseaux ad hoc hybrides à grande échelle

Imen Jemili

Description

Sous la direction de Richard Castanet, Abdelfettah Belghith
Thèse soutenue le 13 juillet 2009: Bordeaux 1
Dans le cadre des réseaux ad hoc à grande envergure, le concept de clusterisation peut être mis à profit afin de faire face aux problèmes de passage à l'échelle et d'accroître les performances du système. Tout d’abord, cette thèse présente notre algorithme de clusterisation TBCA ‘Tiered based Clustering algorithm’, ayant pour objectif d’organiser le processus de clusterisation en couches et de réduire au maximum le trafic de contrôle associé à la phase d’établissement et de maintenance de l’infrastructure virtuelle générée. La formation et la maintenance d’une infrastructure virtuelle ne sont pas une fin en soi. Dans cet axe, on a exploité les apports de notre mécanisme de clusterisation conjointement avec le mode veille, à travers la proposition de l’approche de conservation d’énergie baptisée CPPCM ‘Cluster based Prioritized Power Conservation Mechanism’ avec deux variantes. Notre objectif principal est de réduire la consommation d’énergie tout en assurant l’acheminement des paquets de données sans endurer des temps d’attente importants aux niveaux des files d’attente des nœuds impliqués dans le transfert. Nous avons proposé aussi un algorithme de routage LCR ‘Layered Cluster based Routing’ se basant sur l’existence d’une infrastructure virtuelle. L’exploitation des apports de notre mécanisme TBCA et la limitation des tâches de routage additionnelles à un sous ensemble de nœuds sont des atouts pour assurer le passage à l’échelle de notre algorithme.
-Réseaux ad hoc
-Clusterisation
-Routage
-Conservation d’énergie
-Ensemble dominant connexe
Relying on a virtual infrastructure seems a promising approach to overcome the scalability problem in large scale ad hoc networks. First, we propose a clustering mechanism, TBCA ‘Tiered based Clustering algorithm’, operating in a layered manner and exploiting the eventual collision to accelerate the clustering process. Our mechanism does not necessitate any type of neighbourhood knowledge, trying to alleviate the network from some control messages exchanged during the clustering and maintenance process. Since the energy consumption is still a critical issue, we combining a clustering technique and the power saving mode in order to conserve energy without affecting network performance. The main contribution of our power saving approach lies on the differentiation among packets based on the amount of network resources they have been so far consumed. Besides, the proposed structure of the beacon interval can be adjusted dynamically and locally by each node according to its own specific requirements. We propose also a routing algorithm, LCR ‘Layered Cluster based Routing’. The basic idea consists on assigning additional tasks to a limited set of dominating nodes, satisfying specific requirements while exploiting the benefits of our clustering algorithm TBCA.
-Ad hoc networks
-Clustering
-Connected dominating set
-Power saving
-Routing
Source: http://www.theses.fr/2009BOR13818/document

Sujets

• Partitionnement de données
• Routage

Informations

• Publié par: Thesee
• Nombre de lectures: 71
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

N° d'ordre : 3818

THÈSE

PRESÉNTÉE À

L’UNIVERSITÉ DE BORDEAUX I

ÉCOLE DOCTORALE DE MATHÉMATIQUES ET
D’INFORMATIQUE

Par Imen JEMILI


POUR OBTENIR LE GRADE DE

DOCTEUR

SPÉCIALITÉ : INFORMATIQUE

-----------------------------
Clusterisation et conservation d’énergie dans les réseaux ad hoc hybrides à
grande échelle
-----------------------------
Soutenue le : 13 Juillet 2009
Après avis des rapporteurs :
Béchir El Ayeb Professeur
David Simplot-Ryl Professeur
Devant la commission d’examen composée de :
Richard Castanet Professeur Co-Directeur de thèse
Mohamed Mosbah Professeur Co-Directeur de thèse
Abdelfettah Belghith Professeur Co-Directeur de thèse
Francine Krief Professeur Présidente
Béchir El Ayeb Professeur Rapporteur
David Simplot-Ryl Professeur Rapporteur
-2009 -
Résumé :
Dans le cadre des réseaux ad hoc à grande envergure, le concept de clusterisation peut être
mis à profit afin de faire face aux problèmes de passage à l'échelle et d'accroître les performances
du système. Tout d’abord, cette thèse présente notre algorithme de clusterisation TBCA ‘Tiered
based Clustering algorithm’, ayant pour objectif d’organiser le processus de clusterisation en
couches et de réduire au maximum le trafic de contrôle associé à la phase d’établissement et de
maintenance de l’infrastructure virtuelle générée. La formation et la maintenance d’une
infrastructure virtuelle ne sont pas une fin en soi. Dans cet axe, on a exploité les apports de notre
mécanisme de clusterisation conjointement avec le mode veille, à travers la proposition de
l’approche de conservation d’énergie baptisée CPPCM ‘Cluster based Prioritized Power
Conservation Mechanism’ avec deux variantes. Notre objectif principal est de réduire la
consommation d’énergie tout en assurant l’acheminement des paquets de données sans endurer
des temps d’attente importants aux niveaux des files d’attente des nœuds impliqués dans le
transfert. Nous avons proposé aussi un algorithme de routage LCR ‘Layered Cluster based
Routing’ se basant sur l’existence d’une infrastructure virtuelle. L’exploitation des apports de
notre mécanisme TBCA et la limitation des tâches de routage additionnelles à un sous ensemble
de nœuds sont des atouts pour assurer le passage à l’échelle de notre algorithme.
Mots clés : Réseaux ad hoc, clusterisation, ensemble dominant connexe, conservation
d’énergie, routage.


Abstract :
Relying on a virtual infrastructure seems a promising approach to overcome the
scalability problem in large scale ad hoc networks. First, we propose a clustering mechanism,
TBCA ‘Tiered based Clustering algorithm’, operating in a layered manner and exploiting the
eventual collision to accelerate the clustering process. Our mechanism does not necessitate any
type of neighbourhood knowledge, trying to alleviate the network from some control messages
exchanged during the clustering and maintenance process.
Since the energy consumption is still a critical issue, we combining a clustering technique
and the power saving mode in order to conserve energy without affecting network performance.
The main contribution of our power saving approach lies on the differentiation among packets
based on the amount of network resources they have been so far consumed. Besides, the proposed
structure of the beacon interval can be adjusted dynamically and locally by each node according
to its own specific requirements.
We propose also a routing algorithm, LCR ‘Layered Cluster based Routing’. The basic
idea consists on assigning additional tasks to a limited set of dominating nodes, satisfying
specific requirements while exploiting the benefits of our clustering algorithm TBCA.
Key words : Ad hoc networks, clustering, connected dominating set, power saving,
routing.





























A la mémoire de mon père,
A ma mère à qui je dois tout mon bonheur
pour son soutien sans faille et sa confiance,
A mes sœurs Alia et Asma,
A mes frères Sami, Salah et Naceur,
A mes anges Cyrine et Nadine,
A tous ceux qui me sont chers,
Qu’ils trouvent dans ce mémoire la preuve de mon
affection et attachement.
Imen
Remerciements


Je souhaite remercier Francine Krief, Professeur à l’Ecole Nationale
Supérieure d’Electricité, Informatique, Télécommunications, Mathématique et
Mécanique de Bordeaux, pour m’avoir fait l’honneur d’accepter la position de
Président du jury.
Je remercie également Béchir El Ayeb, Professeur à l’Université de
Monastir, et David Simplot-Ryl, Professeur à l’Université de Lille 1, pour avoir
accepté la charge de rapporteur et pour leurs remarques pertinentes concernant mon
mémoire.
Mon parcours durant cette thèse n’aurait jamais pu aboutir sans l’intervention
de plusieurs personnes, auxquelles j’adresse ma gratitude la plus sincère. Tout
d’abord, j’exprime mes profonds remerciements à mes directeurs de thèse, au sein
du pôle HANA et au sein du LaBRI. Mes premiers remerciements vont au
Professeur Abdelfettah Belghith pour son soutien et sa vision pragmatique des
problèmes. En de nombreuses occasions, son recul et sa vision d'ensemble du
monde des réseaux se sont avérés essentiels pour trouver de nouvelles solutions et
dégager des perspectives de recherche. C’est grâce au Professeur Mohamed
Mosbah que je me suis intéressée à l’algorithmique distribuée. Outre ses remarques
et suggestions techniques, académiques et professionnelles, qui m’ont été
inestimables, son suivi personnel m’a beaucoup touché. Je tiens aussi à remercier le
Professeur Richard Castanet, mon directeur de thèse, pour m’avoir accordé
l’occasion de réaliser cette thèse et d’avoir soutenu mon travail tout au long de ces
années.
Merci également à tous ceux qui m'ont accompagné et soutenu dans cette
grande expérience de la vie que constitue une thèse. Mes remerciements vont aussi
à tous mes amis du pôle HANA, Hanen, Naouel, Achraf, Wafa et Rafaa, qui ont
contribué de prés ou de loin dans ce travail, par leur amitié et l’entraide qui régnait
dans notre groupe. Je tiens à saluer mes meilleures amies pour leur encouragement,
en particulier Hanen. Je ne peux oublier mes amis d’outre-mer, je m’adresse
particulièrement à Hejer pour son soutien et sa présence et toutes les personnes que
j’ai connues durant mes séjours au LaBRI. Je n’oublie pas le personnel
administratif du LaBRI que j’ai du solliciter à maintes reprises et aussi au sein de
l’ENSI. Je ne peux oublier finalement de saluer l'encouragement de ma famille, tantes
et cousines qui n'ont cessé de croire en moi. J’adresse enfin mes remerciements à
tous ceux qui, par leur courtoise et sympathie, m’ont aidé, encouragé et soutenu.

.T.able.des.mati?res.T.able.des.gures.v.Listesansdes.tableauxgatewix.In.troCo?tsduction.G?n?rale.1.Chapitre.12ClusterisationConstructiondans.lesetr?seaux.A.d.ho.c.7.1.1.D?nition.de.la.clusterisation..1.5...........algorithme.v.dominan.....2.1.1.mem...D?claration.......la...............25.la..7.1.2.Classication.des.algorithmes.de.clusterisation......................30.osition.clusterisation.sance.33.l'ensem.connexe......8.1.2.1.Clusterisationdesanov.ec.les.ensem35blesnodominanysts.ind?p.endan.ts....40.clusterisation............10.1.2.2.Clusterisation.a.v.ec.les.ensem.bles.dominan1.4tsde.clusterisation...............................2814Conclusion1.2.3.Clusterisation.a.v.ec.les.ensem.bles.dominan.ts.connexes....................Chapitre.Prop.d'un15de1.2.4distribu?Clusterisationconnais-aduvoisinageec2.1lesdeensembleblestdominan.ts.connexes.faiblemen.t...........20351.2.5D?clarationClusterisationClusterheadsadesveudsecbresles.ensem.bles.dominan.ts.?.k2.1.2sautsdes.euds.a..................21.1.3.In.t?r?tside.Tlesable.des.mati?r.es.2.1.2.1.D?claration.des79candGW.normaux......v.de.....A.he.............dicit?....40.2.1.2.2.D?claration.des.candGW.s.aourvlaec.unconservCH.inconn.u....Ev...4.3.....m?canismes.Appro....43jour2.1.3.PhaseEtapdedensit?v.?rication........................de.d'?nergie.81.la...Impact.l'ecacit?...........M?canisme.........erformances..47.2.1.4.Main.tenance........5.conserv.ho.prioritisation.......p.mise.......72.3.de.............3.4.mobilit?................523.52.1.5.Preuv.es................4.clusterisation.conserv.les.ho.Exploitation.p.ation.....87.l'appro.clusterisation.m?canisme.tion...................89.AN+........54.2.2.D?l?gation.du91r?ledede.DN................................105.osition.our.d'?nergie.A.107.he.trac.....