REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET POPULAIRE

MINISTERE DE L’ENSEIGNEMENT SUPERIEURE ET DE LA RECHERCHE SCIENTIFIQUE

UNIVERSITE IBN KHALDOUN - TIARET

MEMOIRE
Présenté à :

FACULTÉ MATHEMATIQUES ET INFORMATIQUE

DÉPARTEMENT D’INFORMATIQUE

Pour l’obtention du diplôme de :

MASTER
Spécialité : Réseau et Télécommunications

Par :

 KHELIFI Mohamed
 GUENDOUZ Lakhdar

Sur le thème

Un algorithme génétique pour la couverture des cibles

dans les réseaux de Capteurs sans fil

Soutenu publiquement le.. /.. / 20xx à Tiaret devant le jury composé de :

Mr BOUALEM Adda Grade Université M.A.A Président

Mr BENGHENI Abdelmalek Grade Université M.C.B Encadreur
Mr BAKKAR Khaled Grade Université M.A.A Examinateur

Année universitaire 2019 – 2020

 Remerciements

Nous remercions avant tout ALLAH le tout-

puissant qui nous a donné la force, la volonté et la
patience pour achever ce modeste travail.
Nous remercions Dr. BENGHENI Abdelmalek notre
encadreur d’avoir bien dirigé ce travail, avec ses
judicieux conseils dont il a fait preuve durant
l’élaboration de notre étude.
Je souhaite remercier toutes les personnes qui
m’ont aidé d’une façon directe ou indirecte à la
réalisation de ce mémoire. Nos remerciements aux
membres du jury, d’avoir accepté de juger notre
travail.
 Dédicaces

Je dédie ce travail ;
À mes parents qui m’ont toujours offert le
bonheur. Je le dédie à mes sœurs, mes frères, aux
petits enfants de la famille, et à ma grande famille,
À tous mes amis et mes collègues.
À la promotion 2019/2020 d’informatique.
Enfin, à toutes celles et tous ceux qui ont contribué
de près ou de loin à l’accomplissement de ce
travail.
 Tables des matières

Tables des matières

Liste des figures
Liste des abréviations
Résumé
Introduction Générale……………………………………………………………………………………...…..……..........1

Chapitre I : Les Réseaux de capteurs sans fil

I.1- Introduction……………………………………………………………………………………………………….…….…3
I.2- Définition d’un réseau de capteurs sans fil…………………..………...………………...………...…………3
I.3- Architecture d’un nœud capteur…………………………………..…………………………….……..……….…3
I.4-Caractéristiques des réseaux de capteurs…………………………..……………………….………..………..4
I.4.1- ARCHITECTURE D’UN RESEAU DE CAPTEURS ……….………………..…………………..……4
I.4.2- QUELQUES DIFFERENTS FACTEURS DE CONCEPTION……………………………………... 5
I.4.3-ARCHITECTURE PROTOCOLAIRE……………………………………………………………..………..7
I.5-Applications des réseaux de capteurs sans fil …………………………………………………...…………..8
I.5.1-APPLICATIONS MILITAIRES…………………..……………………………………..….…….…………...8
I.5.2-APPLICATIONS ORIENTEES EVENEMENTS ……….…………………………………….………….8
I.5.3-APPLICATIONS ORIENTEES REQUETES ……………….…………………………..…………………8
I.5.4-APPLICATIONS HYBRIDES …….…………………...…………………………….………..……………….9
I.6-Accès medium dans les réseaux de capteurs sans fil ……………………………………..………………9
I.6.1-LA RETRANSMISSION ………………….…………….………………………………………………………9
I.6.2-L'ECOUTE ACTIVE ………………………….………………..………………………………………………..9
I.6.3-LA SURÉCOUTE ……………………………….………………………………………………………………10
I.6.4-LA SURCHARGE ………………………………………………………………………………………………10
I.6.5- LA SUREMISSION ……………………………………………………………………………………………10
I.6.6-LA TAILLE DES PAQUETS … ……………………………………………………………………………10
I.7- Modèle de calcul d’énergie….…………………………………………………...……….………………………..10
I.8- La Couverture……………….……………………………..………………………….……..………………………….12
I.9- La Connectivité……..………….…………………,..……………………………….……….…………………………12
I.10- Conclusion ……………………………………………………………………………….……………………………..14
Chapitre II : La couverture dans les réseaux de capteurs sans fil
II.1-Introduction.………………………………………………………………………………………………………………15
II.2-La notion de la couverture…………………………………………………………………………………………..15
II.2.1- LA DEFINITION DE LA COUVERTURE…..…………………………………………………………15
II.2.2- LE BUT DE LA COUVERTURE………………………………………………………………………….16
II.3-Les différents types de couverture……………………………………………………………………………….16

Tables des matières

 Tables des matières

II.3.1- LA COUVERTURE DE CIBLES....……………………………………………………………………….16

II.3.2-LA COUVERTURE DE ZONES.………………………………………………………………………….17
II.3.3-LA COUVERTURE DE BARRIERE..…………………………………………………………………….17
II.4-La problématique de la couverture………………………………………………………………………………17
II.5-Les paramètre de la couverture dans les RCSF…………………………….………………………………..18
II.6-Les critères attachés à la couverture dans les RCSF………………………………………………………18
II.7-Les protocoles de la couverture de surfaces…………………………………………………………………20
II.7.1- LE PROTOCOLE PEAS...…………………………………………………………………………………..20
II.7.2-LE PROTOCOLE Gallais…….……………………………………………………………………………..20
II.7.3-LE PROTOCOLE DCovPDS.………………………………………………………………………………21
II.7.4- LE PROTOCOLE CCSID…………………………………………………………………………………...21
II.7.5- LE PROTOCOLE PECAS…………………………………………………………………………………..21
II.7.6- LE PROTOCOLE ACOS…………………………………………………………………………………….22
II.4-CONCLUSION……………………………………………………………………………………………………………..22
Chapitre III : Les Algorithmes Génétiques
III.1-Introduction ……………………………………………………………………………………..………………………23
III.2-Définition d'une heuristique …………………………………….………………………..………………………23
III.3-Introduction de méta-heuristique………………………………………………………………………………23
III.4-Les métaheuristiques pour l’optimisation difficile …………….……………….……………………….24
III.4.1-OPTIMISATION « DIFFICILE »………………………………………………………………………..24
III.4.2- ALGORITHME D’OPTIMISATION APPROCHÉE ………………………………………………24
III.5-Les Algorithmes génétiques (AG) ……………………………………………..……………………………….25
III.5.1-INTRODUCTION ………………………………………………………...……………………………….25
III.5.2- LES OUTILS EVOLUTIONNAIRES DE BASE D’UN (AG) ……………..…………………….26
III.5.3- OPTIMISATION PAR LES ALGORITHMES GÉNÉTIQUES………………..………………..26
III.5.4- MECANISMES DE FONCTIONNEMENT D’UN (AG) ………………………..………………..27
III.6-Quelques travaux existants "les AGs pour la couverture des RCSF" ……………………………34
III.6.1- Coverage and connectivity aware energy efficient scheduling in target based
wireless sensor networks: an improved genetic algorithm based....................................……34

III.6.2- Sensor Technology : Un Clustering centralisé et dynamique basé sur les AGs
pour une consommation d'énergie minimale dans les réseaux de capteurs sans fil : ..…35
III.6.3- Minimisation de la consommation d’énergie des réseaux de capteurs dans les
applications de couverture de cibles :………………………………………..…………………………...…35

III.6.4- Optimisation de la durée de vie dans les réseaux de capteurs sans fil sous
contraintes de couverture et de connectivité réseau :…………………………………..… ………..36

III.7-Conclusion……………………………………..………………………………………………………………………36

Tables des matières

 Tables des matières

Chapitre IV : Implémentation
IV.1-Introduction …………………………………………………...…………………………………………………………37
IV.2-L’environnement de simulation …………….……….…………………………………………………37
IV.2.1- DEFINTION DE MATLAB ………………………………………………………………………………37
IV.2.2- LES PERTICULARITES DU MATLAB …………..…..………………………………………………37
IV.3-L’implémentation……………………………………………………………………………………………………….38
IV.3.1- LES PARAMETRES DE L'ALGORITHME GENETIQUE UTILISES ……….………………40
IV.3.2- LES PARAMETRES DU RCSF UTILISES ……………………………………………….….………40
IV.3.3- FONCTIONNEMENT DE SIMUALTEUR REALISE ………………………..…………….……..40
IV.3.4- LA DESCRIPTION DU SIMULATEUR REALISE ……………………………..………….………41
IV.4-Les différentes expérimentations réalisées………………….……………………………………..……….43
IV.5-L’analyse des résultats trouvés ………………………………………………………………………………….46
IV.6-Conclusion ………………………………………………………………………………………………………..………47
Conclusion générale………………………………………………………………………………………………..………48
Bibliographie

Tables des matières

 Liste des figures
Figure I-1: Architecture d’un nœud capteur………….…………………………………..………….3

Figure I-2: Architecture d'un réseau de capteurs..………………………………………...………5

Figure I-3 : La pile protocolaire d’un réseau de capteurs…………………...………………….7

Figure I-4: La sur écoute dans une transmission.……………………………………………..…10

Figure I-5: Modèle d’énergie…………………………...…………………………………….…………..11

Figure I-6 : Les deux zones de couverture d’un capteur………………………………….….12

Figure II .1 : Couverture de cibles…………………………….………………………………….…….16

Figure II .2 : Couverture d’une zone…………………………………………………………….…….17

Figure II .3 : La couverture de barrière……………………………………………………….……..17

Figure III- 1 : Organigramme général d'un algorithme génétique…………………...…..27

Figure III- 2 : la table d’individu…………………………………………………………….….……...29

Figure III- 3 : Croisement à un site……………………………………………………….….………..32

Figure III- 4 : Croisement à k sites………………………………………………………….….………32

Figure III- 5 : Mutation dans un chromosome…………………….……………..….……….…..33

Figure IV.1 : Fonctionnement du simulateur réalisé………………………….….…...………41

Figure IV.2 : Interface principale………………………………………………………………....…...42

Figure IV.3 : le déploiement des nœuds de capteurs se forme aléatoire…..………….43

Figure IV.4 : la liste des nœuds voisins……………………………………………………...……...44

Figure IV.5 : La première expérimentation avec 60 nœuds de capteur et 20

cibles déployés ……………………………………………………………………....………………..………45

Figure IV.6 : La première expérimentation avec 80 nœuds de capteur et 20 cibles

déployés………………………………………………………………………………………….…………........46

Figure IV.7 : La première expérimentation avec 100 nœuds de capteur et 20 cibles

déployés………………………………………………………………………………….…………………….…47

Liste des figures

 Liste des figures
Figure IV.8 :les différentes valeurs d’énergie obtenues dans les différents RCSF
simulés………………………………………………………………………………………………….…………..47
Tableaux IV.1 : Paramètre du RCSF……………………………………………..……….……………...41

Liste des figures

 LISTE DES ABREVIATIONS

WSN : Wireless Sensor Network.

AD HOC : Advanced Developers Hands-On Conference.

GPS : Global Positioning System.

MAC : Media Access Control.

RCSF : Réseau de Capteurs Sans Fil.

DARPA : Defence Advanced Research Projects Agency.

SR : Rayon de Transmission.

CR : Rayon de Capture.

QOS : Quality Of Service.

PEAS : Probing Environment And Adaptive Sleeping.

DCovPDS : Distributed Coverage Preserving based on

Dominating Set.

EDM : Ensemble Dominant Minimal.

CCSID : Connected Cover Set based on Identité of node.

EDCM : Ensemble Dominant Connecté Minimal.

PECAS : Probing Environment and Collaborating Adaptive

Sleeping.

ACOS : Area-based Collaborative Sleeping.

GA : Génétique Algorithme.
 ‫ملخص‬
‫( لما‬RCSF) ‫تعتبر مشكلة التغطية من المشاكل األساسية لشبكات االستشعار الالسلكية‬
‫ يمكن أن تشير‬.‫لها من تأثير مباشر على استهالك الطاقة ألجهزة االستشعار وعمر الشبكة‬
‫ هناك عدة طرق لتصنيف‬.‫مشكلة التغطية عادة إلى كيفية مراقبة مجال الشبكة بشكل فعال‬
، ‫يمكن تصنيف قضايا التغطية المستمرة بشكل أكبر‬. RCSF ‫مشكالت التغطية في شبكات‬
، ‫ وتغطية النقطة‬، ‫ تغطية المنطقة‬:‫ إلى ثالثة أنواع‬، ‫اعتمادًا على منطقة االهتمام بالمراقبة‬
‫ اعتمادًا على درجة‬، ‫ يمكن تصنيف قضايا التغطية‬، ‫ عالوة على ذلك‬.‫وتغطية الحاجز‬
‫ فإن الهدف من هذه المذكرة هو‬، ‫ لذلك‬k ‫ أو تغطية‬1 ‫ إلى قضايا تغطية‬، ‫التغطية المطلوبة‬
‫ مع‬RCSF ‫) في‬1 ‫استخدام خوارزمية جينية لتحسين تغطية األهداف (مشكلة التغطية‬
RCSF ‫ االتصال وعمر‬:‫ مثل‬RCSF ‫مراعاة القيود المختلفة لـ‬
،‫(؛التغطية‬AG) ‫(؛ خوارزمية جينية‬RCSF) ‫شبكة اإلستشعار الالسلكية‬: ‫الكلمات المفتاحية‬
‫اإلتصال؛ عمر شبكة اإلستشعار الالسلكية‬
Résumé
Le problème de couverture est l’un des problèmes fondamentaux des réseaux de
capteurs sans fil (RCSF) car il a un impact direct sur la consommation d’énergie des
capteurs et la durée de vie du réseau. Le problème de couverture peut généralement
indiquer comment surveiller efficacement le champ de réseau. Il existe plusieurs façons
de classer les problèmes de couverture dans les RCSF. Les problèmes de couverture
continue peuvent être classés plus avant, en fonction de la région d'intérêt pour la
surveillance, en trois types: couverture de zone, couverture de point et couverture de
barrière. En outre, les problèmes de couverture peuvent être classés, en fonction du
degré de couverture requis, en problèmes de 1-couverture ou en k-couverture. De ce
fait, l’objectif de ce mémoire est l’utilisation d’un algorithme génétique pour
l’optimisation de la couverture de cibles (problème de 1-couverture) dans le RCSF tous
en respectant les différentes contraintes du RCSF telles que: la connectivité dans le RCSF
et la durée de vie du RCSF.

Mots–clé: réseau de capteurs sans fil (RCSF), Algorithme Génétique (AG), La

couverture, la connectivité, la durée de vie du RCSF.

Abstract
The coverage problem is one of the fundamental problems of wireless sensor
networks (RCSF) because it has a direct impact on the energy consumption of the
sensors and the life of the network. The coverage problem can usually indicate how to
effectively monitor the network field. There are several ways to classify coverage issues
in CWNs. Continuous coverage issues can be further categorized, depending on the
region of interest for surveillance, into three types: area coverage, point coverage, and
barrier coverage. Further, coverage issues can be classified, depending on the degree of
coverage required, in 1-coverage issues or k-coverage. Therefore, the objective of this
thesis is the use of a genetic algorithm for the optimization of the coverage of targets
(problem of 1-coverage) in the RCSF while respecting the various constraints of the
RCSF such as: connectivity in the RCSF and the lifetime of the RCSF.

Keywords: wireless sensor network (RCSF), Genetic Algorithm (AG), Coverage,

connectivity, lifetime of the RCSF.
Introduction Générale
 INTRODUCTION GÉNÉRALE

Depuis leur création, les réseaux de communication sans fil ont

connu un succès sans cesse croissant au sein des communautés
scientifiques et industrielles. Grâce à ses divers avantages, cette
technologie a pu s’instaurer comme acteur incontournable dans les
architectures réseau actuelles. Durant cette dernière décennie, une
architecture nouvelle a vu le jour : le réseau de capteurs sans fil. Ce
type de réseau peut être vu comme un réseau de microsystèmes
disséminés dans un espace donné et communicant entre eux via une
liaison sans fil. L’espace où agissent les capteurs s’appelle un champ
de captage. Ce qui est intéressant dans les réseaux de capteurs, c’est
que les nœuds sont souvent composés d’un grand nombre de micro-
capteurs capables de récolter et de transmettre des données
environnementales d’une manière autonome.

Les capteurs sans fil sont généralement conçus pour être

déployés en forte densité dans des endroits hostiles et inaccessibles,
ils deviennent alors à usage autonome en raison de l’impossibilité de
remplacer ou recharger leurs batteries. La consommation d’énergie
est alors distribuée en exploitant la redondance induite par le
déploiement aléatoire; des nœuds sont actifs tandis que d’autres
demeurent inactifs, économisant ainsi leur énergie. Cette topologie
dynamique ne doit pourtant pas mettre en péril l’application de
surveillance. C’est pourquoi les nœuds actifs doivent couvrir une
zone aussi large que l’ensemble des capteurs déployés. De plus, il est
indispensable d’assurer l’acheminement des rapports en provenance
des capteurs vers les stations puits chargées de stocker et de traiter
les données. L’ensemble des nœuds actifs doit également être
connecté.

Dans le but d’exploiter le déploiement aussi longtemps que

possible, une gestion de ressource rigoureuse en termes d’énergie
sera exigée. Pour ce faire, l’activité des capteurs est ordonnancée,
certains sont en mode sommeil et économisent leur énergie pendant
que d’autres participent à la surveillance. Parmi les critères de
tabulation, on citera la couverture de surface qui est l’une des
mesures, les plus importantes, pour évaluer la qualité de surveillance
produite par un réseau de capteurs dans une zone géographique. Une

INTRODUCTION GÉNÉRALE Page 1

 INTRODUCTION GÉNÉRALE

zone est dite couverte, si tous les points qu’elle inclut sont observés
par au moins un capteur.

Dans ce travail, on utilise un algorithme génétique adopté pour

le problème de couverture simple (1-couverture) des cibles dans le
RCSF afin de prolonger leur durée de vie en choisissant un nombre
minimum de nœuds de capteurs actifs parmi un grand nombre de
nœuds de capteurs répartis aléatoirement. Les nœuds de capteurs
choisis doivent couvrir tout le nombre prédéfini complet de points
cibles, de manière intermittente ou continue. En même temps, ces
nœuds de capteurs actifs doivent maintenir la connectivité entre eux
et la station de base (SB) de sorte que les précieuses données
détectées puissent être transférées à la SB sur le chemin le plus court.

Ce travail est organisé en quatre chapitres :

 Dans le premier chapitre intitulé « Les Réseaux de capteurs

sans fil », nous décrivons les réseaux de capteurs sans fil, leurs
architectures, leurs caractéristiques, leurs domaines
d’application, ainsi que la couverture et la connectivité.

 Dans le deuxième chapitre intitulé «la couverture dans les

réseaux de capteurs sans fil », nous décrivons la problématique,
les paramètres et les protocoles de la couverture.

 Le troisième chapitre, est consacré à la présentation des

algorithmes génétiques.

 Dans le dernier chapitre, nous expliquerons en détail la

simulation que nous avons conçue dans MATLAB.

 L’objectif du dernier chapitre décrit notre implémentation, la

modélisation formelle utilisée par l’algorithme génétique à la
couverture (1-couverture) dans le RCSF ainsi que
l’interprétation des différents résultats trouvés.

 Nous achevons ce mémoire en donnant une conclusion

générale, et quelques perspectives futures en vue d’améliorer
et d’étendre ce travail.

INTRODUCTION GÉNÉRALE Page 2

 Chapitre I :
Les Réseaux de capteurs sans fil
Chapitre I : Les Réseaux de capteurs sans fil

I.1-Introduction :

Le réseau de capteurs sans fil, est une révolution scientifique, car il a

ouvert la voie à la création d'une nouvelle génération d'application dans
divers domaines.

Dans ce chapitre, nous décrivons les réseaux de capteurs sans fil, leurs
architectures, leurs caractéristiques, leurs domaines d’application, l'accès
médium, le modèle de calcul d’énergie, ainsi que la couverture et la
connectivité.

I.2-Définition d’un réseau de capteurs sans fil :

Un réseau de capteurs sans fil est un réseau ad hoc d'un grand nombre
de nœuds, qui sont des micro-capteurs capables de recueillir et de
transmettre des données d'une manière autonome. La position de ces
nœuds n'est pas obligatoirement prédéterminée. Ils peuvent être
aléatoirement répartis dans une zone géographique, intitulée « champ de
captage » correspondant au terrain concerné pour le phénomène capté [1].

I.3- Architecture d’un nœud capteur :

Un capteur est composé de quatre éléments de base : une unité de
perception, de traitement, de communication et une unité de contrôle
d’énergie (batterie) [2].

Figure I-1: Architecture d’un nœud capteur [3].

Chapitre I Page 3
Chapitre I : Les Réseaux de capteurs sans fil

1- L’unité de capture :

L’unité de capture est composée généralement de deux sous-unités : le

capteur lui- même et un convertisseur Analogique/Numérique .Le capteur
est chargé de fournir des signaux analogiques, basés sur le phénomène
observé, au convertisseur. Ce dernier transforme ces signaux en un signal
numérique transmis à l’unité de traitement pour effectuer des analyses [4].

2- L’unité de traitement :

L’unité de traitement, comprend un processeur associé généralement à

une petite unité de stockage et fonctionne à l’aide d’un système
d’exploitation spécialement conçu pour les micro-capteurs. Cette unité est
chargée d’exécuter les protocoles de communication qui permettent la
collaboration entre les capteurs du réseau [5].

3- L’unité de transmission :

L’unité de transmission est chargée d’effectuer toutes les émissions et

réceptions des données sur un médium sans fil. Elle peut être du type
optique (laser), infrarouge ou fréquence radio.

4- L’unité de contrôle d’énergie :

Elle alimente les unités que nous avons citées en dessus.

Généralement, elle n’est ni rechargeable ni remplaçable. La capacité
d’énergie limitée au niveau des capteurs représente la contrainte principale
lors de conceptions de protocoles pour les réseaux de capteurs.

I.4-Caractéristiques des réseaux de capteurs :

I.4.1- Architecture d’un réseau de capteurs :
Un réseau de capteurs est généralement constitué de nombreux nœuds
répartis dans une zone (sensor Field). Ces nœuds sont reliés à une ou
plusieurs passerelles (sink) qui permettent l'interconnexion avec d'autres
réseaux (internet, satellite…) [6].

Chapitre I Page 4
Chapitre I : Les Réseaux de capteurs sans fil

Figure I-2: Architecture d'un réseau de capteurs [7].

I.4.2-Quelques différents facteurs de conception :

La conception des réseaux de capteurs est influencée par de nombreux
facteurs comme la tolérance aux pannes, les coûts de production, la
consommation d'énergie, l'environnement ou la topologie du réseau. Ces
facteurs représentent la base de la conception de protocoles ou
d'algorithmes pour les réseaux de capteurs [6] [8].

a- Tolérance aux pannes :

Le fonctionnement d'un ou plusieurs capteurs peut être interrompu
pendant le cycle de vie du réseau. Il y a plusieurs causes à ces échecs :
- manque en ressources énergétiques
- dégâts matériels
- interférences environnementales
- compromission des nœuds

Ces pannes ne doivent pas affecter le fonctionnement global du réseau.

La tolérance aux pannes se définit alors comme la capacité du réseau à
continuer à fonctionner normalement sans interruption même après le
dysfonctionnement d’un ou de plusieurs de ses nœuds capteur [9].

Chapitre I Page 5
Chapitre I : Les Réseaux de capteurs sans fil

b- Coût de fabrication :
Le coût de production d’un seul micro capteur est très important pour
l’évaluation du coût global du réseau, si ce dernier est supérieur à celui
nécessaire pour le déploiement des capteurs classiques, l’utilisation de cette
nouvelle technologie ne serait pas financièrement justifiée. Par conséquent,
réduire le coût de production jusqu'à moins de 1$ par nœud est un objectif
important pour la faisabilité de la solution des réseaux de capteurs sans fil.

La technologie Bluetooth a pu offrir un système radio connu d’être le

moins chère du marché pour un coût de 10$, ce qui est dix fois plus chère
que le coût désiré pour un nœud capteur. Ceci, sachant qu’un nœud contient
d’autres systèmes que celui de transmission radio tel que les unités de
captage et de traitement de données. De plus, le nœud peut être équipé
d’éléments additionnels tel qu’un system de localisation GPS, ou un système
de rechargement d’énergie. Dès lors, la minimisation du coût de production
du nœud [10].

c- Topologie du réseau :
En raison de leur forte densité dans la zone à observer, il faut que les
nœuds-capteurs soient capables d’adapter leur fonctionnement afin de
maintenir la topologie souhaitée On distingue généralement trois phases
dans la mise en place et l’évolution d’un réseau :
- Déploiement : les nœuds sont soit réparti de manière pré définie soit de
manière aléatoire.
- Post-déploiement-exploitation : durant la phase d’exploitation, la topologie
du réseau peut être soumise à des changements dus à des modifications de
la position des nœuds ou bien à des pannes.
- Redéploiement : L'ajout des nouveaux capteurs dans un réseau existant
implique aussi une remise à jour de la topologie [6].

d- Consommation d’énergie :
Détecter les évènements dans l’environnement capté, élaborer un
traitement de données local et rapide, et transmettre les résultats à
l’utilisateur sont les principales tâches d’un nœud dans un réseau de
capteurs. Les étapes de consommation d’énergie par ce nœud peuvent être,

Chapitre I Page 6
Chapitre I : Les Réseaux de capteurs sans fil

dès lors, divisées en trois phases : le captage, la communication et le

traitement de données [6].

I.4.3- Architecture protocolaire :

La pile de protocoles utilisée par le puits (Sink) ainsi que par tous les
nœuds-capteurs est donnée dans la Figure I-3. Cette pile de protocoles
combine routage et gestion d'énergie et intègre les données avec les
protocoles réseau. Elle communique de manière efficace (en termes
d'énergie) à travers le support sans fil et favorise les efforts de coopération
entre les nœuds-capteurs. La pile de protocoles comprend une couche
application, une couche transport, une couche réseau, une couche liaison de
données, une couche physique, un plan de gestion d'énergie, un plan de
gestion de mobilité et un plan de gestion des tâches. Selon les tâches de
détection, différents types de logiciels d'application peuvent être construits
et utilisés dans la couche application. La couche transport contribue au
maintien du flux de données si l'application du réseau de capteurs l'exige.
La couche réseau s'occupe de l'acheminement des données fournies
par la couche transport. Comme l'environnement est sujet au bruit et que
les nœuds-capteurs peuvent être mobiles, le protocole MAC doit tenir
compte de la consommation d'énergie et doit être en mesure de réduire les
collisions entre les nœuds voisins lors d'une diffusion par exemple. La
couche physique répond aux besoins d'une modulation simple mais
robuste, et de techniques de transmission et de réception.

Figure I-4 : La pile protocolaire d’un réseau de capteurs [12].

Chapitre I Page 7
Chapitre I : Les Réseaux de capteurs sans fil

En outre, les plans de gestion d'énergie, de mobilité et des tâches

surveillent et gèrent la consommation d'énergie, les mouvements, et la
répartition des tâches entre les nœuds-capteurs. Ces plans aident les
nœuds-capteurs à coordonner les tâches de détection et à réduire
l'ensemble de la consommation d'énergie [11].
I.5-Applications des réseaux de capteurs sans fil :
I.5.1-Applications militaires :
Les réseaux de capteurs sans fil proviennent principalement de la
recherche militaire. Les réseaux de capteurs indépendants sont un élément-
clé de cette évolution vers des systèmes de guerre sans fil. Ils peuvent être
déployés et utilisés rapidement pour surveiller le champ de bataille et
fournir des informations sur l'emplacement, le nombre, le mouvement et
l'identité des soldats et des véhicules. Une croissance très rapide a abouti à
la recherche et au développement de réseaux de capteurs sans fil par des
programmes financés par l'Agence des États-Unis pour les projets de
recherche de défense avancés (DARPA) [13].
I.5.2-Applications orientées évènements :
Les capteurs envoient leurs données seulement si un événement
spécifique se produit. On peut citer l'exemple de surveillance des feux dans
les forêts où un capteur envoie des alarmes à la station de base dès que la
température dépasse un certain seuil. Au départ, cette classe d'application
était conçue à des fins militaires, comme la surveillance du déplacement
d'objets dans le champ de bataille. Par la suite, cette classe a rapidement
trouvé, de nouvelles perspectives comme le contrôle industriel, le contrôle
médical des patients, la surveillance d'édifices (barrages, ponts, voies de
chemins de fer, etc...) [14].
I.5.3-Applications orientées requêtes :
Dans ce cas, un capteur envoie de l'information uniquement suite à une
demande explicite de la station de base. Cette classe d'application est
destinée aux applications adaptées à l'utilisateur. Ce dernier peut requérir
des informations à partir de certaines régions dans le réseau ou interroger
les capteurs pour acquérir des mesures d'intérêts. Dans ce cas, des
connaissances sur la topologie du réseau et l'emplacement des capteurs
sont nécessaires [15].

Chapitre I Page 8
Chapitre I : Les Réseaux de capteurs sans fil

I.5.4-Applications Hybrides :
Ce type d’application met en œuvre les trois modes de fonctionnement
décrits précédemment. Par exemple, dans un réseau conçu pour le suivi
d’objets, le réseau peut combiner entre un réseau de surveillance (time
driven) et un réseau de collecte de données par événements (event driven).
Par exemple, pendant les longues périodes d’inactivité des capteurs et
lorsque aucun objet n’est présent, le réseau peut assurer une fonction de
surveillance [16].

I.6-Accès médium dans les réseaux de capteurs sans fil :

La sous couche MAC assure l’accès au support de transmission, la
fiabilité de transmission, le contrôle de flux, la détection d’erreurs et la
retransmission des paquets. Puisque les nœuds partagent le même médium
de transmission, la sous-couche MAC joue un rôle important pour la
coordination entre les nœuds et la minimisation de la consommation
d’énergie. En effet, minimiser les collisions entre les nœuds permet de
réduire la perte d’énergie. Dans ce qui suit, nous analyserons les
principales causes de consommation d’énergie au niveau de la couche
MAC [17].

I.6.1-LA RETRANSMISSION :
Les nœuds capteurs possèdent en général une seule antenne radio et
partagent le même canal de transmission. Par ailleurs, la transmission
simultanée des données provenant de plusieurs capteurs peut produire des
collisions et ainsi une perte de l’information transmise.

La retransmission des paquets perdus peut engendrer une perte

significative de l’énergie.

I.6.2-L’ECOUTE ACTIVE :
L’écoute active (idle listening) du canal pour une éventuelle réception
de paquet qui ne sera pas reçu peut engendrer une perte importante de la
capacité des nœuds en énergie.

Pour éviter ce problème, il faut basculer les nœuds dans le mode

sommeil le plus longtemps possible.

Chapitre I Page 9
Chapitre I : Les Réseaux de capteurs sans fil

I.6.3-LA SUR ÉCOUTE :

Le phénomène de sur écoute (overhearing) se produit quand un nœud
reçoit des paquets qui ne lui sont pas destinés. La sur écoute conduit à une
perte d’énergie additionnelle à cause de l’implication des autres capteurs
dans la réception des données.

Figure I-5: La sur écoute dans une transmission [18].

I.6.4-LA SURCHARGE :
Plusieurs protocoles de la couche MAC fonctionnent par échange de
messages de contrôle (over Head) pour assurer différentes fonctionnalités :
signalisation, connectivité, établissement de plan d’accès et évitement de
collisions. Tous ces messages nécessitent une énergie additionnelle.

I.6.5-LA SUREMISSION :
Le phénomène de surémission (Overe mitting) se produit quand un
nœud capteur envoie les données à un destinataire qui n’est pas prêt à les
recevoir. En effet, les messages envoyés sont considérés inutiles et
consomment une énergie additionnelle.

I.6.6-LA TAILLE DES PAQUETS :

La taille des messages échangés dans le réseau a un effet sur la
consommation d’énergie des nœuds émetteurs et récepteurs. Ainsi, la taille
des paquets ne doit être ni trop élevée ni trop faible. En effet, si elle est
petite, le nombre de paquets de contrôle (acquittement) généré augmente
l’over Head. Dans le cas contraire, une grande puissance de transmission
est nécessaire pour des paquets de grande taille.

I.7-Modèle de calcul d’énergie :

Nous évaluons l’énergie consommée par un nœud capteur (nᵢ),
notée EC(nᵢ), pour réaliser à la fois les fonctions de capture, de traitement
et de communication par l’équation suivante :
Chapitre I Page 10
Chapitre I : Les Réseaux de capteurs sans fil

EC(nᵢ) = E(Sᵢ) + E(Pᵢ) + E(TRANSᵢ) (1)

Avec :

E(Sᵢ) = 𝑒ₛ‚ᵢ désigne l′ énergie dépensée lors de l′ operationde capture

E(Pᵢ) égale eₚ‚ᵢ désigne l′ énergie consommée pendant le traitement au niveau du microcontrôleur

E(TRANSᵢ) désigne l′ énergie nécessaire pour la transmission et la réception d′ un Paquet de d

E(TRANSᵢ) peut être exprimée par ∶

E(TRANSᵢ) = E(Cтх‚ᵢ) + E(Crх‚ј) (2)

Figure I-6: Modèle d’énergie

Ainsi, la quantité d’énergie nécessaire pour transmettre k bits du nœud

capteur 𝑛ᵢ au nœud capteurs 𝑛ј, avec 𝑑(𝑛ᵢ , 𝑛ј) notée par 𝑑ᵢ‚ј désigne la
distance qui les sépare, est donnée par :
E(TRANSᵢ) = 2 ∗ Eelec ∗ k + amp ∗ k ∗ dᵢ² (3)

L’équation (3) devient :

EC(nᵢ) = 2 ∗ Eelec ∗ k + εamp ∗ k ∗ dᵢ2 ј + eₚ‚ᵢ + eₚ‚ᵢ (4)

Comme
eₚ‚ᵢ et eₚ‚ᵢ sont deux termes indépendants de la distance d, on note
eₚ‚ᵢ + eₚ‚ = T , l’équation (4)

Devient :
EC(nᵢ) = 2 ∗ Eelec ∗ k + εamp ∗ k ∗ dᵢ²ј + T (5)

Chapitre I Page 11
Chapitre I : Les Réseaux de capteurs sans fil

Avec Eelec est l’énergie dépensée par le module de transmission ou de

réception et εamp désigne l’énergie nécessaire pour l’amplification du signal
radio.
On note 𝐸(𝐵ᵢ) = 𝑒ᵢ(𝑡)avec 𝑒ᵢ(0)désigne la capacité initiale de la batterie et
𝑒ᵢ(𝑡) = 𝑒ᵢ(0) − 𝑒ᵢ(𝑡) Désigne l’énergie résiduelle d’un nœud capteur
𝑛ᵢ Ainsi, si
𝑒ᵢ(𝑡) > 0 Alors le nœud ni est actif et si 𝑒ᵢ(𝑡) = 0 alors le nœud 𝑛ᵢ est inactif.

I.8-La Couverture :
Les capteurs fonctionnent en utilisant le modèle de seuil, c'est-à-dire
que le capteur a deux régions: la zone de perception (SR) et la zone de
contact (CR). À des fins de planification, nous considérons que ces régions
sont représentées par deux circuits contenant le capteur comme centre,
comme le montre la figure ci-dessous:

Figure I-7 Les deux zones de couverture d’un capteur [19].

En affectant la relation entre le rayon SR et le rayon CR, nous
ajusterons les limitations. Ainsi, nous pourrons réduire le nombre de
nœuds actifs et maximiser la durée de vie du réseau. Si la densité du
capteur est trop élevée et que la zone que vous souhaitez surveiller est
également couverte, les capteurs fonctionneront inutilement [20] [21].
I.9-La Connectivité :
Après les phases de placement/déploiements des nœuds dans la zone
d’intérêt, ces derniers doivent former un réseau connecté afin de pouvoir
assurer le transfert des informations capturées par des nœuds sources vers
la station de base. Selon le type d’architecture utilisé, l’ensemble des nœuds
Chapitre I Page 12
Chapitre I : Les Réseaux de capteurs sans fil

du réseau ou une partie de cet ensemble doivent se connecter de façon

permanente dès qu’une source donnée transmet ses données à la station de
base.

I.9.1-Définition de la connectivité dans les RCSF :

Pour définir la connectivité entre deux nœuds d’un RCSF. On dit que
deux nœuds sont connectés si et seulement s’ils peuvent communiquer
directement (connectivité à un saut) ou indirectement (connectivité multi-
saut). Le RCSF est connecté s’il existe au moins une route entre chaque
nœud du réseau et la station de base. Par conséquent, d’après cette
définition, nous pouvons dire que la connectivité dépend donc
essentiellement de l’existence de routes. Elle est ainsi affectée par les
changements de topologie, dus généralement aux pannes de nœuds, à la
mobilité, etc. Ces changements de topologies ont pour conséquence la perte
des liens de communication, l’isolement des nœuds, le partitionnement du
réseau, etc. À l'instar de la couverture, la connectivité dans les RCSF est
considérée comme un paramètre de mesure de performance très
importante surtout dans le cas des applications de RCSF citées ci-haut.
Ainsi, pour bien garantir toutes les fonctionnalités de telles applications, il
est nécessaire de bien étudier et de prendre en compte les propriétés de
connectivité lors de la conception et le déploiement de tels réseaux [22].

I.9.2-Types de connectivité dans les RCSF :

Il existe deux types de connectivité dans les RCSF qui sont la
connectivité complète et la connectivité intermittente. Une connectivité
complète peut être soit simple (1-connectivité), soit multiple (k-
connectivité). Une connectivité complète d’un RCSF est dite simple s’il
existe un seul chemin entre chaque nœud source et la station de base et elle
est dite multiple s’il existe plusieurs chemins distincts entre chaque nœud
source et la station de base. Selon les stratégies de placement des nœuds
dans la zone de surveillance et selon les caractéristiques de l’application,
une connectivité simple (ou multiple) peut être assurée lors de la phase de
placement des nœuds ou bien être obtenue lors d’une phase de
redéploiement ou d’auto-configuration des nœuds. Dans le cas de certaines
applications des RCSF, il n’est pas nécessaire d’assurer et de maintenir en
continu une connectivité complète du réseau. En effet, pour de telles
applications, il est suffisant de garantir une connectivité intermittente en
Chapitre I Page 13
Chapitre I : Les Réseaux de capteurs sans fil

utilisant par exemple un (ou plusieurs) station de base mobile se déplaçant

afin de recueillir les mesures collectées par les nœuds capteurs déconnectés
[22].

I.10 –Conclusion :
La technologie des réseaux de capteurs sans fil est un domaine en plein
essor, de plus en plus d’applications utilisent cette technologie. En effet, les
avancées électroniques et informatiques d’aujourd’hui sont capables de
développer de minuscules capteurs capables de capter des données,
calculer des informations à l’aide de ces données collectées et de
communiquer à travers un réseau.

Dans le chapitre suivant, nous exposerons les algorithmes génétiques.

Chapitre I Page 14
 Chapitre II :
La couverture dans les réseaux de
capteurs sans fil
Chapitre II : La couverture dans les réseaux de capteurs sans fil

II.1-Introduction :
L'un des principaux problèmes abordés dans la littérature est la
couverture de zones dans les RCSF. Cette dernière est centrée sur une
question fondamentale: comment assurer le suivi d'un domaine d'intérêt
particulier? [23].

Cela se fait en définissant l'activité du capteur, qui peut être dans un

mode actif ou en mode veille, tout en maintenant une couverture aussi
complète que possible de la zone sur laquelle le réseau a été déployé [24].

Dans ce chapitre, nous décrivons la notion de couverture, leurs

différents types, la problématique, les paramètres de la couverture, les
critères attachés à la couverture dans les RCSF ainsi que les protocoles de
la couverture de surface.

II.2-La notion de la couverture :

II.2.1- LA DEFINITION DE LA COUVERTURE :

La couverture dans les RCSF est souvent considérée comme étant une
mesure de performance très importante. Elle reflète la façon dont une zone
donnée est surveillée (contrôlée), c’est-à-dire comment chaque point de la
zone de surveillance est observé et suivi par l’ensemble des nœuds
capteurs. Ainsi, la notion de couverture dans les RCSF peut être vue comme
une mesure de la QoS [25].
En effet, certaines applications peuvent exiger un fort degré de
couverture afin de remplir pleinement leurs missions. Par exemple, c’est le
cas de la surveillance critique de zone, l’agriculture intelligente, etc. Ainsi,
pour ces applications, il faut faire en sorte que si un événement se produit
en un point quelconque de la zone surveillée par les capteurs, il soit détecté
au moins par un capteur donné. Les applications telles que la surveillance
animale, la mesure de températures à l’intérieur d’un bâtiment requièrent
des degrés de couverture plus faibles. D’autres applications comme la
détection d’intrusion fonctionnent généralement avec un degré de
couverture dynamiquement ajustable en fonction des zones de détection en
alerte. Par conséquent, la nécessité de couverture d’une zone donnée varie
en fonction des besoins applicatifs et doit être prise en considération dans
la conception et le déploiement de certaines applications des RCSF [25].

Chapitre II Page 15
Chapitre II : La couverture dans les réseaux de capteurs sans fil

Il existe deux types de couverture dans les RCSF : une couverture

simple et k-couverture définie comme étant une multitude de couvertures
simples et dépendantes de la robustesse et du degré de l’application [25]
[26].

II.2.2- LE BUT DE LA COUVERTURE :

Dans la plupart des travaux, le but de k-couverture consiste à trouver

un nombre minimal de nœuds où tout point de la zone d’intérêt est couvert
par au moins k nœuds. Dans cette optique, plusieurs approches ont été
proposées dans la littérature. Dans [27] [28], les auteurs choisissent un
sous-ensemble de nœuds aléatoirement pour maintenir la couverture de
zone tout en visant à économiser l’énergie globale du réseau.

II.3-Les différents types de couverture :

Le problème de la couverture peut être classé en trois types : [29]
[30].

II.3.1- LA COUVERTURE DE CIBLES :

L'objectif principal de ce type de problème est de couvrir un ensemble

des cibles spécifiques dont la situation géographique est connue. Figure II
.1 montre un exemple d'un groupe de capteurs déployés de manière
aléatoire pour couvrir un ensemble de points (petits carrés) où les nœuds
noirs connectés constituent le groupe de capteurs actif.

Figure II .1– Couverture des cibles [31].

Chapitre II Page 16
Chapitre II : La couverture dans les réseaux de capteurs sans fil

II.3.2- LA COUVERTURE DE ZONES :

Le problème de couverture de zones est approfondi dans les RCSF, où

l'objectif premier du réseau de capteurs est de couvrir une zone
géographique (voire une région). La Figure II .2 montre un exemple de
déploiement aléatoire de capteurs pour couvrir une zone carrée.

Figure II .2 : Couverture d’une zone [31].

II.3.3- LA COUVERTURE DE BARRIERE :

Le but du revêtement du parapet est de réduire la possibilité d'une

pénétration non observée à travers le parapet (réseau de capteurs). La
figure II .3 illustre le problème de couverture de la barrière où les points
de début et de fin du chemin sont choisis parmi les lignes inférieures et la
limite supérieure de la zone. La sélection de la route dépend de la cible.

Figure II .3 : La couverture de barrière [32].

II.4-La problématique de la couverture :
L'un des principaux objectifs des réseaux de capteurs est de fournir
une couverture complète et efficace d'une zone d'intérêt donnée. L'objectif
est de rendre chaque point d'intérêt physique dans la plage de capture d'au
moins un capteur. On dit que la zone d'intérêt est couverte si et seulement
pour chaque point de ce dernier a au moins un capteur actif à une distance
Chapitre II Page 17
Chapitre II : La couverture dans les réseaux de capteurs sans fil

traditionnelle inférieure au rayon de capture. Le rayon de capture ou de

couverture représente la distance euclidienne maximale à laquelle le nœud
est capable de percevoir un événement et de collecter des informations
pertinentes liées à son environnement [33].

II.5-Les paramètres de la couverture dans les RCSF :

Après un déploiement aléatoire de capteurs dans la zone concernée,
deux conditions de base doivent être remplies [34].

1- ce dernier doit former un réseau connecté afin de transférer les

informations capturées par les nœuds sources vers la station de base.
2- surveiller toutes les cibles de zone couvertes.
En réalisant ces deux conditions, nous formerons un réseau de haute
qualité, tout en maintenant le reste des autres capteurs dans un état
d'inactivité, ce qui contribuera à prolonger au maximum la durée de vie du
réseau.
Parmi les conséquences inattendues de la technologie de propagation
aléatoire, certains nœuds de capteur peuvent devenir défectueux et
inopérants en raison de l'épuisement de la puissance. Lors de la conception
des réseaux de capteurs sans fil, les protocoles doivent atteindre le niveau
de tolérance aux pannes des nœuds de capteur, et cela dépend fortement
des applications utilisateur. Dans certaines applications, le niveau de
tolérance aux pannes doit être élevé, comme les applications de
surveillance et de contrôle de champs d’intérêt dont les mesures capturées
sont très critiques.

II.6-Les critères attachés à la couverture dans les RCSF :

Les différentes formulations du problème de la couverture dans les
réseaux de capteurs sont classifiées selon les critères suivants : [35] [36]
a -Objectif du problème :
L'objectif du problème de couverture est de penser à un réseau de
capteurs sans fil (RCSF) dans lequel le périmètre de l'objet cible est
surveillé. Il est entouré de capteurs répartis de manière aléatoire. Chaque
nœud capteur ne peut surveiller qu'une partie de l'océan et ne peut
communiquer qu'avec ses voisins. Pour économiser l'énergie, le nombre

Chapitre II Page 18
Chapitre II : La couverture dans les réseaux de capteurs sans fil

minimum de capteurs capables de surveiller tout le périmètre doit être

activé.

b-Méthode de déploiement des nœuds capteur :

La méthode de déploiement des nœuds capteur sur une zone d’intérêt

diffère selon les conditions de l’environnement. Pour cela, différentes
méthodes de déploiement existent, déploiement aléatoire, où la position
des capteurs n’est pas connue a priori, est utilisé dans les environnements
difficiles.

c-Relation entre les rayons de capture et de communication :

Cette relation détermine l'homogénéité ou l'hétérogénéité du réseau.

Un réseau composé de nœuds de capteur avec les mêmes rayons de capture
et de contact.

d- L’énergie :

La taille des nœuds de capteur et leur déploiement général dans des

zones hostiles et inaccessibles rendent la source d'alimentation,
généralement sous forme de batterie, à énergie limitée, impossible
(presque) à recharger.

e- La connectivité :

La communication est la propriété d'avoir au moins un chemin entre

un nœud capteur et une station de base. Cela permet de garantir que les
informations recueillies sont routées à tout moment et que tous les nœuds
sont accessibles à partir de la station de base.

f- Caractéristiques des algorithmes utilisées :

Les algorithmes de couverture sont distribués ou centralisés.

L'algorithme distribué ne nécessite aucune connaissance du réseau ou de la
topologie de voisinage, qui se limitera aux informations locales et donc à la
mise en œuvre parallèle du protocole. Les algorithmes centralisés
nécessitent des informations complètes sur le réseau.

Chapitre II Page 19
Chapitre II : La couverture dans les réseaux de capteurs sans fil

II.7-Les protocoles de la couverture de surface :

La plupart des protocoles de la couverture de surface utilisent un outil
d’évaluation de couverture; tout nœud u devant décider de son statut
d’activité doit au préalable évaluer la couverture fournie par ses voisins de
communication. Il ne peut être passif que si la surveillance de sa zone est
assurée par ces derniers.

II.7.1- LE PROTOCOLE PEAS :

L'algorithme de couverture de zone conçu pour les réseaux de

capteurs denses et asynchrones est utilisé dans un environnement dans
lequel le déploiement planifié est risqué ou impossible, soit en raison
d'espaces hostiles dans lesquels une intervention humaine n'est pas
possible (les zones ne peuvent pas être atteintes) ou il est lié au grand
nombre de nœuds de capteurs qu’il sera publié dans le cas où la taille de la
région à surveiller est trop importante. Ce protocole est aléatoire et
distribué, et est divisé en deux étapes: [37].
a- Sommeil adaptatif :
Le nœud du capteur reste inactif (veille) jusqu'à ce que le nœud actif
tombe en panne ou que sa batterie soit épuisée. Ensuite, il remplace le
mauvais nœud si nécessaire.
b-Enquête environnementale :
Pour passer de passif à actif, le capteur doit ressentir son
environnement, c'est-à-dire qu'il envoie un soi-disant message vocal à ses
voisins 1, si son voisinage 1 est très proche de lui et donc qu'il couvre sa
zone de détection puis lui demande de rester à l'état négatif, ou s'il n'y a
pas de capteurs actifs autour, il décide de se mettre en mode actif jusqu'à ce
que son énergie soit épuisée.

II.7.2- LE PROTOCOLE Gallais :

Gallais et d'autres proposent un protocole localisé et distribué, où

chaque capteur connaît sa position par GPS. Il est utilisé dans les réseaux
de capteurs simultanés où tous les capteurs ont le même rayon de
détection et de contact et la plage de détection est égale à la plage de
communication. Les messages échangés par le contrat sont supposés

Chapitre II Page 20
Chapitre II : La couverture dans les réseaux de capteurs sans fil

contenir leur emplacement et leur statut, ce qui permet au contrat

d'évaluer la communication de tous les voisins [38] [39].

II.7.3- LE PROTOCOLE DCovPDS (Distributed Coverage Preserving

based on Dominating Set):

Le protocole proposé permet la construction d'EDM de manière

distribuée. En effet, chaque capteur met en œuvre le protocole
indépendamment des autres nœuds afin de déterminer son état: est-il
dominant ou non ? DCovPDS divise la durée de vie du réseau en périodes
d'activité consécutives de même durée, chacune est composée de deux
phases phase de décision et phase de capture [40].

II.7.4- LE PROTOCOLE CCSID (Connected Cover Set based on Identité

of node):

L'objectif du protocole CCSID est de trouver le plus petit ensemble

connexe des nœuds qui permet d'assurer une couverture maximale [41].

CCSID est décomposé en deux phases :

1- phase de construction de l'EDM (Ensemble Dominant Minimal) :

Cette phase consiste à construire l'EDM qui assure la couverture de la

zone d'intérêt. L’EDM est obtenu par la détermination de l'ensemble
indépendant maximal de cardinalité minimale.

2- phase de construction le EDCM (Ensemble Dominant Connecté

Minimal) :

Cette phase est exécutée pour assurer la connectivité entre les nœuds
de l'ensemble EDM de la première phase, et pour garantir une meilleure
couverture de la zone d'intérêt.

II.7.5- LE PROTOCOLE PECAS (Probing Environment and

Collaborating Adaptive Sleeping) :

PECAS est une extension du protocole PEAS. Le nœud reste en mode

actif uniquement pendant la durée spécifiée par le paramètre
(Work_Time_Dur), contrairement à PEAS, où le nœud actif reste éveillé
jusqu'à ce que la batterie s'effondre ou s'épuise. De plus, chaque nœud
contient une variable temporaire appelée (Next_Sleep_Time), qui est

Chapitre II Page 21
Chapitre II : La couverture dans les réseaux de capteurs sans fil

utilisée pour informer le nœud du temps restant avant de passer en mode

inactif [42].

II.7.6- LE PROTOCOLE ACOS (Area-based Collaborative Sleeping):

Ce protocole améliore les performances de PECAS [42] et introduit le

concept de collaboration dans le but d’équilibrer la consommation
d’énergie parmi les capteurs. Dans ce protocole, un capteur peut être dans
l’un des quatre états suivants : passif, actif, pré-actif, ou pré-passif en outre,
les auteurs ont considéré deux niveaux de consommation d’énergie :
(lowpower et consuming-power). Le premier mode de consommation
d’énergie correspond à l’état actif tandis que le deuxième correspond aux
autres états du capteur [43].

II.8-Conclusion :
La couverture est l’une des mesures, les plus importantes, pour
évaluer la qualité de surveillance produite par un réseau de capteurs dans
une zone géographique. Une zone est dite couverte, si tous les points
qu’elle inclut sont observés par au moins un capteur. Dans ce chapitre, nous
avons abordé le problème de couverture, puis nous avons décrit quelques
solutions existantes.

Dans le prochain chapitre, nous présenterons l’implémentation de

notre travail.

Chapitre II Page 22
 Chapitre III :
Les Algorithmes Génétiques
Chapitre III : Les Algorithmes Génétiques

III.1-Introduction :
Les algorithmes génétiques (GA : Genetic Algorithm) sont, sans
conteste, la technique la plus populaire et la plus largement utilisée en
Sciences expérimentales et appliquées. Ce sont des algorithmes
d'optimisation s'appuyant sur des techniques dérivées de la génétique et de
l’évolution naturelle sélection, croisements, mutations, etc. Les origines de
ces algorithmes remontent au début des années 1970, avec les travaux de
John Holland et ses élèves à l’Université du Michigan sur les systèmes
adaptatifs [Holland, 1975] [44] [45].

Ce chapitre est consacré à la présentation des algorithmes génétiques

pour la résolution du problème d'optimisation difficile.

III.2-Définition d'une heuristique :

Heuristique est un algorithme de bon sens pour se déplacer
intelligemment dans l'espace de la solution, afin d'obtenir une solution
approximative, le mieux possible, dans un délai raisonnable. Deux types
d'heuristique sont principalement utilisés: l’heuristique constructive et
l’heuristique des proportions. L’heuristique dépend du problème qui doit
être résolu, principalement dans la sélection du voisinage (et donc dans le
déplacement dans le domaine des solutions) [46] [47] [48].

III.3- Définition d’une méta-heuristique :

Le terme méta-heuristique a été inventé par Fred Glover en 1986, lors
de la conception de la recherche Tabou [49]. Une méta-heuristique est un
processus itératif qui subordonne et qui guide une heuristique, en
combinant intelligemment plusieurs concepts pour explorer et exploiter
tout l’espace de recherche. Des stratégies d’apprentissage sont utilisées
pour structurer l’information afin de trouver efficacement des solutions
optimales, ou presque-optimales [50]. Les méta-heuristiques sont
utilisables pour résoudre différents problèmes d’optimisation, et ne
nécessitent que peu de modifications pour qu’elle puisse s’adapter à un
problème particulier. Elles ont donc pour objectif de pouvoir être
programmées et testées rapidement sur un problème [51].

Chapitre III Page 23

Chapitre III : Les Algorithmes Génétiques

III.4-Les méta-heuristiques pour l’optimisation difficile :

III.4.1-Optimisation <<DIFFICILE>> :

Un problème d'optimisation est dit « difficile », car aucune méthode

exacte n'est capable de le résoudre exactement en un temps « raisonnable ».
On devra alors faire appel à des heuristiques permettant une optimisation
approchée.

L'optimisation difficile peut se découper en deux types de problèmes:

les problèmes discrets et problèmes continus. Le premier cas rassemble aux
problèmes de type NP-complets, tels que le problème de voyageur de
commerce. Un problème « NP>» est dit complet s'il est possible de le
décrire à l'aide d'un algorithme polynomial sous la forme d'un sous-
ensemble d'instances. Concrètement, il est « facile » de décrire une solution
à un problème, mais le nombre de solutions nécessaires à la résolution croit
de manière exponentielle avec la taille de l'instance. Jusqu'à présent, la
conjecture postulant que les problèmes NP-complets ne sont pas solubles
en un temps polynomial n'a été démontré, ni révoquée. Aucun algorithme
polynomial de résolution n'a cependant été trouvé pour de tels problèmes.
L'utilisation d'algorithmes d'optimisation permettant de trouver une
solution approchée en un temps raisonnable est donc courante.

Dans la seconde catégorie, les variables du problème d'optimisation

sont continués. C'est le cas par exemple des problèmes d'identification, ou
l'on cherche à minimiser l'erreur moins formalisée que le précédent, mais
un certain nombre de difficultés sont bien connues, comme l'existence de
nombreuses variables présentant des corrélations non identifiées, la
présence de bruit ou plus généralement une fonction objectif accessible par
simulation uniquement. En pratique, certains problèmes sont mixtes et
présentent à la fois des variables discrètes et des variables continues [54].

III.4.2- Les algorithmes d’optimisation approchée :

Les problèmes d'optimisation combinatoire sont souvent des

problèmes trés difficiles dont la résolution par des méthodes exactes peut
s'avérer très longue ou peu réaliste.

Un algorithme d'optimisation approchée est une méthode permettant

de calculer une solution approchée à un problème algorithmique

Chapitre III Page 24

Chapitre III : Les Algorithmes Génétiques

d'optimisation. Plus précisément, c'est une méta-heuristique garantissant à

la qualité de la solution qui fournit un rapport inférieur (si l'on minimise) à
une constante, par rapport à la qualité optimale d'une solution, pour toutes
les instances possibles du problème [55].

L'intérêt de tels algorithmes est qu'il est parfois plus facile de trouver
une solution approchée qu'une solution exacte, le problème pouvant par
exemple être NP-complet mais admettre un algorithme d'approximation
polynomial. Ainsi, dans les situations où l'on cherche une bonne solution,
mais pas forcément la meilleure, un algorithme d'approximation peut être
un bon outil [56].

III.5-Les algorithmes génétiques(AG) :

III.5.1-INTRODUCTION :

Les algorithmes génétiques (AG), ont été initialement développés par

John Holland (1975) dans deux buts principaux [45] [57].

 Mettre en évidence et expliquer rigoureusement les processus

d'adaptation des systèmes.
 Concevoir des systèmes artificiels qui possèdent les propriétés des
systèmes naturels.

Leurs champs d'application sont très vastes. Outre l'économie, ils sont
utilisés pour I‘optimisation de fonctions numériques difficiles
(discontinues, multimodales, bruitées...), traitement d'images (alignement
de photos satellites, reconnaissance de suspects...), Optimisation d'emplois
du temps, optimisation de design, contrôle de systèmes industriels,
apprentissage des réseaux de neurones etc. La raison de ce grand nombre
d'application est claire c'est la simplicité de leurs mécanismes, la facilité de
leur mise en application et leur efficacité même pour des problèmes
complexes, les (AG) peuvent être utilisées pour contrôler un système
évoluant dans le temps (chaîne de production, centrale nucléaire.) car la
population peut s'adapter à des conditions changeantes [58].

Chapitre III Page 25

Chapitre III : Les Algorithmes Génétiques

III.5.2-LES OUTILS EVOLUTIONNAIRES DE BASE D’UN (AG) :

Les (AG), sont basés sur trois éléments principaux la sélection, le

croisement et la mutation. Dans la littérature il s'agit d'opérateurs de
reproduction. Leur principe est simple, comporte trois phases :

1- la genèse (l'initialisation aléatoire d'individus pour former la population

de la première génération).

2- la reproduction (l'évolution des individus de la génération courante vers

la suivante):

a. la sélection des individus reproducteurs.

b. le croisement génétique de ces individus pour la création de

nouveaux individus.

c. la mutation de certains individus pour que la création génétique ne

s'affaiblisse pas.

d. l'évaluation des individus par le calcul de leur fonction

d'adaptation.

3- Recherche de l'individu le plus adapté selon les critères souhaités. La

solution sera représentée par le meilleur individu de la dernière génération
[59].

III.5.3-Optimisation par les algorithmes génétiques :

Les algorithmes génétiques appliqués à un problème d'optimisation

font évoluer un ensemble de solutions utilisent un mécanisme de sélection
naturelle. Ainsi, les AG ne se basent pas sur un individu, mais sur une
population d'individus qui vont évoluer de génération en génération pour
obtenir un résultat se rapprochant de la solution optimale [59].

La sélection a pour but de favoriser les meilleurs éléments de la

population, tandis que le croisement et la mutation assurent une
exploration efficace de l'espace d'état. Les meilleurs individus d'une
génération vont créer une nouvelle génération plus adaptée au problème
dont la nouvelle population contient une plus grande proportion de
caractéristiques des meilleurs individus de la génération précédente.

Chapitre III Page 26

Chapitre III : Les Algorithmes Génétiques

Figure III- 1 : Organigramme général d'un algorithme génétique [59].

L'organigramme fonctionnel présenté dans la figure III- 1, illustre la

structure générale de l'algorithme génétique. Nous détaillerons dans la
suite les diverses phases qui le constituent et les mécanismes associés à
chacune d'entre elles [59].

III.5.4-Le mécanisme de fonctionnement d’un (AG) :

Les différentes étapes de fonctionnement des (AG) sont :

1. Initialisation: une population initiale de N individus est générée

aléatoirement.

2. Évaluation : chaque individus est décodé, puis évalué.

3. Sélection: création d'une nouvelle population par l'utilisation d'une

méthode de sélection appropriée.

4. Recombinaison: croisement et mutation au sein de la nouvelle

population.
Chapitre III Page 27
Chapitre III : Les Algorithmes Génétiques

5. Retour à 2 à la phase d'évaluation jusqu'à la vérification du critère

d'arrêt de l'algorithme

La mise en œuvre des algorithmes génétiques nécessite donc plusieurs

étapes.

L'idée fondamentale est que: la population choisie contient

potentiellement la solution plutôt la meilleure solution, à un problème
donné. Cette solution n'est pas exprimée car la combinaison génétique sur
laquelle elle repose est dispersée chez plusieurs individus. Ce n'est que par
l'association de ces combinaisons génétiques au cours de la reproduction
que la solution pourra s'exprimer. Lors de la reproduction et de la
recombinaison génétique associée, un individu hérite, par hasard, d'un des
gènes de chacun de ses parents. L'originalité des mécanismes repose en
particulier sur le fait qu'il n'a pas considéré les seules mutations comme
source d'évolution mais aussi et surtout les phénomènes de croisement.
C'est en croisant les solutions potentielles existant que l'on peut se
rapprocher de l'optimum [60].

1-INITIALISATION DE LA POPULATION :

Le choix de la population initiale peut conditionner fortement la

rapidité de l'algorithme. Il doit être capable de produire une population
d'individus non homogènes qui servira de base pour les générations
futures, et capable de rendre plus rapide la convergence vers l'optimum
global [60].

Dans le cas où l'on ne connaît rien du problème à résoudre, il est

essentiel que la population initiale soit assez bien répartie sur tout le
domaine de recherche. Une population trop petite évoluera probablement
vers un optimum local intéressant alors qu'une population trop grande sera
inutile car le temps de convergence sera excessif. La taille de la population
doit être choisie de façon à réaliser un bon compromis entre temps de
calcul et qualité du résultat [60].

2-CODAGE DES VARIABLES :

Le codage est une partie très importante des algorithmes génétiques.

Permet de représente l'individu sous la forme d'un chromosome. Ce

Chapitre III Page 28

Chapitre III : Les Algorithmes Génétiques

chromosome est constitué de gènes qui prennent des valeurs dans un

alphabet binaire ou non [60].

Le choix du codage est délicat doit permettre de coder toutes les

solutions et permettre la mise en œuvre des opérateurs de reproduction.
C'est ainsi que le bon déroulement des algorithmes génétiques sera assuré,
plusieurs types de codages sont utilisés, on citera à titre d'exemple; codage
binaire [60].

 Codage binaire:

Dans le codage binaire le gène est codé par un caractère binaire, 0 ou 1.

C'est le plus courant et celui qui a été employé lors de la première
application des algorithmes génétiques. Un des avantages du codage binaire
est que l'on peut ainsi facilement coder toutes sortes d'objets : des réels, des
entiers, des valeurs booléennes, des chaînes de caractères, cela nécessite
simplement l'usage de fonctions de codage et décodage pour passer d'une
représentation à l'autre [60] [61].

Exemple :

Figure III- 2 : la table d’individu [60].

3-LA FONCTION D'ADAPTATION :

Pour calculer le coût d'un point de l'espace de recherche, on utilise

une fonction d'évaluation ou d'adaptation (F). L'évaluation d'un individu ne
dépendant pas de celle des autres individus, le résultat fourni par la
fonction d'évaluation va permettre de sélectionner ou de refuser un
individu pour ne garder que les individus ayant le meilleur coût en fonction
de la population courante: c'est le rôle de la fonction (F). Cette procédure
permet de s'assurer que les individus performants seront conservés, alors
que les individus peu adaptés seront progressivement éliminés [62].

Chapitre III Page 29

Chapitre III : Les Algorithmes Génétiques

4-LA SELECTION DES PARENTS :

La sélection des parents a pour but de deviner les individus de la

population courante qui seront autorisés à se reproduire (les "parents"). La
sélection est fondée sur la qualité des individus, estimée à l'aide de fonction
d'adaptation. Cette opération est peut-être la plus importante puisqu'elle
permet aux individus d'une population de survivre, de se reproduire ou de
mourir. En règle générale, la probabilité de survie d'un individu sera
directement reliée à son efficacité relative au sein de la population. Il existe
plusieurs méthodes pour la reproduction, on citera à titre d'exemple :

1- La sélection par roulette : La sélection des individus par le système de

la roulette s'inspire des roues de loterie. À chacun des individus de la
population est associé un secteur d'une roue. L'angle du secteur étant
proportionnel à la qualité de l'individu qu'il représente. Vous tournez la
roue et vous obtenez un individu. Les meilleurs individus ont plus de
chances d'être croisés et de participer à l'amélioration de notre population
[64].

2- La sélection par tournoi : Le principe de la sélection par tournoi

augmente les chances pour les individus de piètre qualité de participer à
l'amélioration de la population. Le principe est très rapide à implémenter.
Un tournoi consiste en une rencontre entre plusieurs individus pris au
hasard dans la population. Le vainqueur du tournoi est l'individu de
meilleure qualité [64].

3- La sélection par le rang : La sélection par rang est une variante du

système de roulette. Il s'agit également d'implémenter une roulette, mais
cette fois-ci les secteurs de la roue ne sont plus proportionnels à la qualité
des individus, mais à leur rang dans la population triée en fonction de la
qualité des individus [64].

Parmi ces différents types de sélection la méthode la plus connue et la

plus utilisée reste la roulette, proposée par Goldberg (1989).

5-LA RECOMBINAISON GENETIQUE :

Pour créer un nouvel individu à partir des meilleures solutions

précédemment sélectionnées, il est nécessaire de procéder à la
combinaison des gènes des parents pris de manière aléatoire et d'après la

Chapitre III Page 30

Chapitre III : Les Algorithmes Génétiques

théorie de l'évolution, pour que la génération suivante soit plus adaptée au

problème et plus performante on doit combiner les meilleurs individus de
la population actuelle. Une étape d'identification et de sélection de ses
meilleurs individus est donc nécessaire pour que chaque individu ait une
chance proportionnelle à son adaptation de devenir parent [60].

On distingue deux opérateurs principaux : le croisement et la mutation

qui permette d'explorer l'ensemble des solutions possibles. Ces opérations
sont appliquées aléatoirement, à l'aide de deux paramètres, la probabilité
de croisement et la probabilité de mutation. Ces probabilités sont des
paramètres très importants, qui influent de façon considérable sur la
convergence.

A)-LE CROISEMENT :

Le croisement combine les gènes des deux individus parents pour

donner deux nouveaux chromosomes d'individus enfants (descendants)
possédant des caractéristiques issues des deux parents. La zone de
croisement est généralement choisie aléatoirement dans les chromosomes.
Les méthodes de croisement sont liées au codage mais leur principe est
identique. Il a pour but d'enrichir la diversité de la population en
manipulant la structure des chromosomes, il favorise l'exploration de
l'espace de recherche et permet d'explorer l'ensemble des solutions
possibles. Classiquement, les croisements sont envisagés avec deux parents
et génèrent deux enfants. Dans un groupe d’amont arbitrairement choisi
dans la population chaque paire dans la population formée va parer subir le
croisement avec une probabilité P cross [60].

De nombreux types de croisement existent dans la littérature. Ils

préservent plus ou moins l’identité génétique des parents et permettant un
déplacement dans tout l'espace des solutions, le type de croisement le plus
simple est le croisement à un site.

 Croisement à un site :

Il consiste à échanger les gènes de chacun des parents de longueur L en

vérifiant la probabilité Pc. Le site du croisement S doit être choisi entre 1 et
(L - 1). Le changement va se faire entre le site sélectionné et la position
finale L des deux chaînes comme le montre la figure III-3.

Chapitre III Page 31

Chapitre III : Les Algorithmes Génétiques

Figure III- 3: Croisement à un site [60].

 Croisement à k sites

On choisit au hasard k points de croisements successifs. Cet opérateur

généralement considéré comme plus efficace que le précédent. Le
changement va se faire entre deux sites successifs des deux chaines comme
le montre la figure III- 4.

Figure III- 4: Croisement à k sites [60].

Chapitre III Page 32

Chapitre III : Les Algorithmes Génétiques

B)-LA MUTATION

La mutation prend une place de plus en plus importante dans les

algorithmes génétiques, alors qu'il y a encore quelques années son rôle était
encore considéré comme accessoire. Comme les individus les mieux
adaptés sont les plus susceptibles d'être choisis lors de la sélection, la perte
de certains gènes est inévitable avec le temps. La mutation est l'opérateur
qui permet d'éviter la dégénérescence de la population. Cette
dégénérescence peut se traduire par une convergence des individus vers un
optimum local, d'où l'importance de la mutation. Ce phénomène génétique
d'apparition de "mutants" est rare mais permet d'expliquer les
changements dans la morphologie des espèces, toujours dans le sens d'une
meilleure adaptation au milieu naturel [62].

Dans le cas du codage binaire, chaque bit est remplacé selon une
probabilité Pmut par son inverse comme le montre la figure III-5.

Figure III- 5 : Mutation dans un chromosome [62].

6-LA SELECTION FINALE :

Cette étape consiste à garder seulement les solutions les plus

intéressantes, tout en cant une population assez grande et assez diversifiée.
C'est pourquoi la taille de la population doit rester la même d'une
génération à l'autre.

La sélection revient à choisir les meilleurs individus pour former la

nouvelle génération, c'est-à-dire éliminer N individus parmi les 2N
individus (N parents et N enfants) pour cela plusieurs méthodes sont
proposées [62].

Chapitre III Page 33

Chapitre III : Les Algorithmes Génétiques

A)-LA SELECTION PAR DESCENDANCE :

Dans cette méthode, on garde toujours les enfants, quelle que soit leur
adaptation à la population de la nouvelle génération est obtenue par
descendance, les enfants remplaçant automatiquement leurs parents.
L'inconvénient de cette sélection est que l'on risque de voir disparaitre les
caractéristiques génétiques des parents les mieux adaptés si elles n'ont pas
été totalement transmises lors de la recombinaison génétique.

B)- LA SELECTION PAR COMPETITION :

Une compétition a lieu entre parents et enfants pour déterminer ceux

qui feront partie de la génération suivante. Les enfants sont insérés dans la
population si et seulement si leurs performances sont supérieures à celles
de leurs parents, a rang équivalent.

C)- LA SELECTION DE PROCREATION SELECTIVE :

On garde les N meilleurs individus parmi la population intermédiaire

de parents et d'enfants.

III.6-Quelques travaux existants "les AGs pour la couverture

des RCSF" :
III.6.1- Coverage and connectivity aware energy efficient scheduling in
target based wireless sensor networks: an improved genetic algorithm
based approach :

Dans ce travail, a suggéré une planification basée sur un algorithme

génétique amélioré (GA) pour les WSN. Une représentation chromosomique
efficace est donnée et il est montré qu'elle génère un chromosome valide
après une opération de croisement et de mutation. La fonction de fitness est
dérivée avec quatre objectifs contradictoires, la sélection du nombre
minimum de nœuds de capteur, la couverture complète, la connectivité et le
niveau d'énergie des nœuds de capteur sélectionnés. Ils ont introduit une
nouvelle opération de mutation pour de meilleures performances et une
convergence plus rapide des approches basées sur GA proposées. Ils ont
également formulé le problème d'ordonnancement comme une
programmation linéaire. Une simulation approfondie est effectuée sur
divers scénarios de réseau avec un nombre variable de nœuds de capteurs

Chapitre III Page 34

Chapitre III : Les Algorithmes Génétiques

déployés, le point cible et la longueur du réseau. Ils ont effectué également

un test statistique populaire, une analyse de la variance suivie d'une
analyse post hoc [65J.

III.6.2- Sensor Technology : Un Clustering centralisé et dynamique

basé sur les AGs pour une consommation d'énergie minimale dans les
réseaux de capteurs sans fil :

Deux contributions sont présentées dans ce travail. La première porte

sur une analyse des longueurs des sauts, en effet la durée de vie du réseau
dépend fortement de la manière de communication de données soit par des
courts sauts ou des longs sauts. Les simulations présentées dans ce travail
montrent l’efficacité de la condition présentée et qui réduit de manière
significative la consommation d’énergie. Dans la deuxième contribution, la
technique de clustering est utilisée pour réduire la consommation
d’énergie, le problème reste à déterminer le nombre des cluster-chefs ainsi
que leurs positions dans le réseau pour assurer une consommation
minimale d’énergie et une meilleure couverture réseau. Pour surmonter ce
problème, les algorithmes génétiques sont utilisés comme outils pour
déterminer les paramètres du clustering. Les résultats de simulation,
présentés, montrent que l’approche présentée surmonte les résultats de
l’algorithme LEACH [66J.

III.6.3- Minimisation de la consommation d’énergie des réseaux de

capteurs dans les applications de couverture de cibles :

Dans ce travail, l’objectif est de proposer de nouvelles heuristiques

pour le MLCP tout en considérant des hypothèses plus réalistes sur la durée
de vie et la consommation énergétique des nœuds de capteurs. Tout
d'abord, ils ont proposé deux heuristiques gloutonnes où les nœuds de
capteurs n'ont pas nécessairement la même durée de vie. La première
heuristique est basée sur une méthode adaptative tandis que la seconde
utilise l’idée de liste noire, ils ont développé un système de surveillance de
la pollution atmosphérique et de détection d'incendie basé sur un réseau de
capteurs sans fil et ils ont évalué le gain en termes de durée de vie du
réseau lorsqu'un algorithme pour le MLCP est intégré dans un tel système
[67].

Chapitre III Page 35

Chapitre III : Les Algorithmes Génétiques

III.6.4- Optimisation de la durée de vie dans les réseaux de capteurs

sans fil sous contraintes de couverture et de connectivité réseau :

Le but de ce travail est donc la proposition de nouveaux mécanismes

efficaces pour l’optimisation de la durée de vie dans les RCSF, tout en
garantissant, à tout moment de cette durée de vie, une couverture totale de
la zone de surveillance, ainsi qu’une bonne connectivité du réseau. Pour
atteindre ces objectifs, ils ont étudié et font des propositions dans deux axes
qui sont le placement des nœuds et les mécanismes d’ordonnancement au
niveau de la couche MAC. Pour ces derniers, ils ont mis en place un
algorithme appelé DSMAC (Distributed Scheduling Medium Acces Control)
qui est basé sur la méthode proposée de placement des nœuds. Par ailleurs,
DSMAC permet de couvrir 100% de la zone de surveillance, assure une
bonne connectivité du RCSF et permet également aux nœuds capteurs
d’économiser jusqu’à 30% de leur énergie comparativement à d’autres
protocoles MAC [68].

III.7-Conclusion :
Dans ce chapitre, nous avons donné des généralités sur les méta-
heuristiques pour l'optimisation difficile. En premier lieu, nous avons vues
les problèmes d'optimisation et que ce qu'une optimisation difficile. Puis
nous avons fait un rappel sur les différents types de ces algorithmes
d'optimisation approchée. Ainsi que ce chapitre nous a permis d'avoir une
vue générale sur les concepts des AG, leurs applications et leurs
mécanismes de fonctionnement. Une de ces applications est l'optimisation.
Nous pouvons conclure que les AG sont des algorithmes simples de
conception et peuvent résoudre des problèmes assez complexes. La
résolution de ces problèmes est obtenue grâce aux opérateurs de
reproduction.

Chapitre III Page 36

Chapitre IV :
Implémentation
Chapitre IV : Implémentation

IV.1-Introduction :
Ce chapitre décrit la partie expérimentale de notre travail. Il expose
premièrement notre objectif de travail, puis il donne la description de
l’environnement de simulation utilisé, la formulation de problème utilisée
pour résoudre de la 1-couverture dans les RCSF. Enfin, il décrit notre
simulateur, notre implémentation ainsi que les résultats trouvés.
L’objectif de notre travail est l’utilisation d’un algorithme génétique au
problème de couverture simple (1-couverture) des cibles dans les RCSF afin
d’optimiser un nombre minimum de nœuds de capteurs actifs parmi les
nœuds de capteurs déployés aléatoirement. Les nœuds de capteurs choisis
doivent couvrir tout le nombre prédéfini de points cibles, de manière
périodique ou continue. Simultanément, ces nœuds de capteurs actifs
doivent maintenir la connectivité entre eux et la station de base de sorte
que les précieuses données détectées puissent être transmises à la SB selon
le plus court chemin.
IV.2-L’environnement de simulation :
Le MATLAB (Version R2014a): cette Version est disponible pour les
systèmes d'exploitation Linux (64bits), Windows (32 et 64 bits).
IV.2.1- DEFINTION DE MATLAB :
MATLAB (matrix laboratoire) est un langage de programmation et un
environnement de développement de quatrième génération; Il est utilisé à
des fins de calcul numérique. Développé par MATHWORKS, MATLAB
permet la manipulation de matrices, l'affichage de courbes et de données, la
mise en œuvre d'algorithmes, la création d'interfaces utilisateur et peut
interagir avec d'autres langages tels que C, C ++, Java. Les utilisateurs de
MATLAB (près d'un million d'utilisateurs en 2004) proviennent d'horizons
très différents tels que l'ingénierie, la science et l'économie dans des
contextes industriels et de recherche. MATLAB peut être utilisé seul ou en
combinaison avec des boîtes à outils [63].
IV.2.2- LES PERTICULARITES DU MATLAB :
MATLAB permet le travail interactif soit en mode commande, soit en
mode programmation. Tout en ayant toujours la possibilité de faire des
visualisations graphiques. Considéré comme un des meilleurs langages de

Chapitre IV Page 37
Chapitre IV : Implémentation

programmation (C ou Fortran), MATLAB possède les particularités

suivantes par rapport à ces langages:

 la programmation facile.
 la continuité parmi les valeurs entières, réelles et complexes.
 la gamme étendue des nombres et leurs précisions.
 la bibliothèque mathématique très compréhensive.
 l'outil graphique qui inclut les fonctions d'interface graphique et les
utilitaires.
 la possibilité de liaison avec les autres langages classiques de
programmations (C ou Fortran) [63].

IV.3-L’implémentation
Dans cette section, on expose premièrement la modélisation formelle
du problème traité (1-couverture), puis on donne les différents paramètres
utilisés par l'algorithme génétique et par le RCSF ainsi qu’une description
sur notre travail et sur les résultats obtenus.

IV.3.1-Modélisation du problème :
Dans notre implémentation, nous avons utilisé la modélisation prise de
[65] afin d’utiliser l’algorithme génétique pour traiter le problème de la
couverture (1-couverture) dans le RCSF.
1-La modélisation du RCSF utilisée :
On considère un RCSF avec un ensemble V de N nœuds de capteur
V={v1,v2,v3,……,vN} sont déployés aléatoirement pour surveiller de manière
continue et périodique plus un ensemble C de K nombre de cibles C
={c1,c2,c3,……,cK}.

 Un nœud peut détecter les cibles uniquement si elles se trouvent dans

la plage de détection RD (rayon de détection).
 Les nœuds de capteur envoient les données à la SB (Station de Base)
soit directement ou indirectement.
 Les nœuds peuvent communiquer les uns avec les autres uniquement
s’ils se trouvent dans la plage de communication RC (rayon de
communication) les uns des autres.

Chapitre IV Page 38
Chapitre IV : Implémentation

2-Le modèle mathématique utilisé :

 Les hypothèses du réseau :
 La SB située au hasard dans le champ de détection.
 Le RCSF est stationnaire.
 Tous les nœuds du RCSF ont la même énergie initiale tandis
qu’une partite illimitée d’énergie est définie dans la SB.
 La valeur du RD ≤ RC.
 Le modèle mathématique :
N : nombre de nœud.
K : nombre de cible.
a- Les variables de décision :
1 𝑠𝑖 𝑙𝑒 𝑛𝑜𝑒𝑢𝑑 𝑣ᵢ 𝑒𝑠𝑡 𝑐ℎ𝑜𝑖𝑠𝑖
𝑋𝑖 = { (1)
0 𝑠𝑖𝑛𝑜𝑛
1 𝑠𝑖 𝑙𝑒 𝑐𝑖𝑏𝑙𝑒 𝑐ᵢ 𝑒𝑠𝑡 𝑑𝑎𝑛𝑠 𝑙𝑎 𝑝𝑙𝑎𝑔𝑒 𝑑𝑒 𝑑é𝑡𝑒𝑐𝑡𝑖𝑜𝑛 (𝑅𝐷 )𝑑𝑢 𝑛𝑜𝑒𝑢𝑑 𝑣𝑗
𝑌𝑖𝑗 = { (2)
0 𝑠𝑖𝑛𝑜𝑛
1 𝑠𝑖 𝑣ј 𝑒𝑠𝑡 𝑑𝑎𝑛𝑠 𝑙𝑎 𝑝𝑙𝑎𝑔𝑒 𝑑𝑒 𝑐𝑜𝑚𝑚𝑢𝑛𝑖𝑐𝑎𝑡𝑖𝑜𝑛 (𝑅𝐶 )𝑑𝑢 𝑣ᵢ,
𝐾𝑖𝑗 = { 𝑒𝑡 𝑒𝑛 𝑑𝑖𝑟𝑒𝑐𝑡𝑖𝑜𝑛 𝑣𝑒𝑟𝑠 𝑆𝐵 à 𝑝𝑎𝑟𝑡𝑖𝑟 𝑑𝑒 𝑣ᵢ, 𝑖 ≠ 𝑗 (3)
0 𝑠𝑖𝑛𝑜𝑛
1 𝑠𝑖 𝑣ᵢ 𝑒𝑠𝑡 𝑑𝑎𝑛𝑠 𝑙𝑎 𝑝𝑙𝑎𝑔𝑒 𝑑𝑒 𝑐𝑜𝑚𝑚𝑢𝑛𝑖𝑐𝑎𝑡𝑖𝑜𝑛 (𝑅𝐶 )𝑑𝑒 𝑆𝐵
Z𝑖 = { (4)
0 𝑠𝑖𝑛𝑜𝑛

b- La fonction objectif :

𝑀𝑖𝑛𝐹 = ∑𝑁
𝑖=1 𝑋𝑖 (5)
c- Les contraintes

∑𝑁
𝑗=1 𝑌𝑖𝑗 × 𝑋𝑖 = 1 , ∀𝑖, 1 < 𝑖 ≤ 𝐾, 𝑌𝑖𝑗 ∈ {0,1}, 𝑋ᵢ ∈ {0,1} (6)

La contrainte (6) signifiée que pour chaque cible cᵢ ∀i, 1 < 𝑖 ≤ 𝐾, est
couverte par un est un seul nœud capteur.
( ∑𝑁
𝑗=1 𝐾𝑖𝑗 × 𝑋𝑖 + 𝑍𝑖 ) × 𝑋𝑖 ≥ 1 ∀𝑖, 1 < 𝑖 ≤ 𝑁 , 𝐾𝑖𝑗 ∈ {0,1}, 𝑍𝑖 ∈ {0,1} (7)

La contrainte (7) signifiée que pour tous les nœuds capteurs choisis ont au
moins un nœud de capteur en tant que nœud de diffusion de données ou
que le nœud de capteur se trouve dans la plage de transmission directe de
la station de base. Les nœuds capteurs 𝑣𝑖 sont dans la plage de transmission
de la SB est donnée par la variable 𝑍𝑖 .

Chapitre IV Page 39
Chapitre IV : Implémentation

IV.3.2- LES PARAMETRES DE L'ALGORITHME GENETIQUE UTILISÉS :

Les différents paramètres (décrivent dans le chapitre 03) de

l’algorithme génétique appliqués pour atteindre notre objectif de travail
sont :

 La taille de la population initiale est choisie par l'utilisateur.

 Le codage utilisé des chromosomes est le codage binaire.
 Le type sélection utilisée est le type rang.
 Le type de croisement utilisé est le croisement simple (à un point).
 Le type de mutation est exprimé par le choix d’un morceau de chemin.
 Le teste d’arrêt égal au nombre d’itérations de l’algorithme génétique.

IV.3.3- LES PARAMETRES DU RCSF UTILISES :

Le tableau suivant représente les paramètres du RCSF utilisés :

Paramètres Valeurs Unité de mesure

Nombre des nœuds 60, 80, 100 ---
L’énergie initiale des nœuds 0.5 Joule
Rayon de transmission 30, 35, 40 Mètre
Rayon de capture 29, 34, 39 Mètre
Type de déploiement Aléatoire ---
Type de réseaux Stationnaire ---

Tableaux IV.1 : Les paramètres du RCSF

IV.3.3- FONCTIONNEMENT DU SIMULATEUR REALISÉ :
Le fonctionnement de base de notre simulateur est présenté par
l'organigramme de la figure suivante :
Déploiement des nœuds capteurs

Découverte des nœuds voisins

Application de l’algorithme Génétique

Extraction des résultats

Représentation graphique des résultats

Figure IV.1 : Fonctionnement du simulateur réalisé

Chapitre IV Page 40
 Chapitre IV : Implémentation

IV.3.4- LA DESCRIPTION DU SIMULATEUR REALISÉ :

Nous présentons dans cette section la description de notre simulateur.

1- L'INTERFACE PRINCIPALE:

Une fois l'utilisateur lance l'application alors il obtient la fenêtre

principale suivante :

2
10
3

4 11
5

6 12

7
13
8

9 14

Figure IV.2 : Interface principale.

1- Zone pour saisir la largeur de la surface de déploiement.
2- Zone pour saisir la hauteur de la surface de déploiement.
3- Zone pour saisir le nombre des nœuds du réseau.
4- Zone pour saisir le nombre des cibles.
5- Zone pour saisir rayon de transmission.
6- Zone pour saisir rayon de capture.
7- Zone pour saisir l’énergie initiale d’un nœud.
8- Zone pour saisir le nœud émetteur.
9- Zone pour saisir la station de basse.
10- Zone identifier la taille de la population initiale.
11- Une zone pour saisir un numéro de nœud afin de déterminer la liste
de ses voisins.

Chapitre IV Page 41
Chapitre IV : Implémentation

12- Bouton pour lancer l’application de l’algorithme génétique.

13- Bouton pour lancer le déploiement.
14- Bouton pour quitter l’interface.

2- DÉPLOIEMENT DES NOEUDS DE CAPTEURS

Cette phase comporte le déploiement aléatoire des nœuds de capteurs

dans une surface à deux dimensions. Ce dernier ne respecte pas
l’homogénéité de l’existence dans l’espace; il est fondé sur une fonction
aléatoire qui engendre à chaque fois un emplacement diffèrent par rapport
au emplacement précèdent Chaque nœud au départ détient les
informations suivantes :

 Une position en deux dimensions.

 Une portée radio de transmission lui permettant la détection de ses
voisins.
 Une portée radio de son appareil de découverte lui permettant la
détection de cibles possibles.
 L'énergie initiale de chaque nœud.

Une cible. Nœud actif.

Figure IV.3 : le déploiement des nœuds de capteurs aléatoirement

Chapitre IV Page 42
Chapitre IV : Implémentation

3- LA DÉTERMINATION DE LA LISTE DES NŒUDS VOISINS

La découverte des nœuds voisins est basée principalement sur les

performances de transmission. Si la distance entre deux nœuds est
intérieure ou égale à la portée maximale de la radio de transmission, ils se
voient voisins. La figure qui suit présente le résultat de simulation lors de
l'exécution de cette procédure de découverte des voisins.

Figure IV.4 : la liste des nœuds voisins.

IV.4-Les différentes expérimentations réalisées

Par le biais de plusieurs expérimentations faites et afin d’atteindre notre
objectif de ce travail, nous avons varié les différents paramètres utilisés par
le RCSF simulé ont appliquant l'algorithme génétique détaillé dans la section
précédente.

Il est à noter que nos résultats sont basés sur la simulation de différents
types de réseaux, de 60 à 100 nœuds de capteurs déployés dans une zone de
100 X 100 m2 pendant le nombre d’itérations définit pour dérouler
l’algorithme génétique utilisé pendant la simulation. Dans les différents

Chapitre IV Page 43
Chapitre IV : Implémentation

scénarios utilisés et mis en œuvre, le trafic est généré périodiquement en

modifiant les différentes valeurs des rayons utilisés par chaque nœud (rayon
de transmission varié entre 30 et 40 et le rayon de capture varié entre 29 et
39). L'énergie initiale de chaque nœud de capteur est définie sur 0.5 joule. La
métrique de performance utilisée est de minimiser le nombre des nœuds actif
en maintient la connectivité dans les RCSF simulé.

 Première expérimentation :

La figure ci-dessous montre le déploiement aléatoire de 60 nœuds de

capteurs et de 20 points cibles dont chaque nœud utilise un rayon de
transmission de 40 m et un rayon de couverture de 39 m.

Une cible. Nœud actif. Nœud inactif.

Figure IV.5 : La première expérimentation avec 60 nœuds de capteur et 20

cibles déployés.
La figure IV.5 représente les résultats obtenus après l'application de
l'algorithme génétique utilisé. On note qu'après l’application de ce dernier
que tous les points cibles ont été couverts, en plus de cela, la connexion
entre le nœud émetteur et la station de base est également assurée, de plus,
on constate que seulement, 15 nœuds ont été sélectionnés sur 60 nœuds
actifs.

Chapitre IV Page 44
Chapitre IV : Implémentation

 Deuxième expérimentation :

La figure ci-dessous montre le déploiement aléatoire de 80 nœuds de

capteurs et de 20 points cibles dont chaque nœud utilise un rayon de
transmission de 35 m et un rayon de capture de 34 m.

Une cible. Nœud actif. Nœud inactif.

Figure IV.6 : La première expérimentation avec 80 nœuds de capteur et 20

cibles déployés.
La figure IV.6 représente les résultats obtenus après l'exécution de
l'algorithme génétique utilisé. On remarque qu'après l’application de ce
dernier que tous les points cibles ont été couverts. De plus, la connexion
entre le nœud émetteur et la station de base est identiquement certaine, de
plus, on constate que seulement, 17 nœuds ont été sélectionnés sur 80
nœuds actifs.

 Troisième expérimentation :

La figure ci-dessous montre le déploiement aléatoire de 100 nœuds de

capteurs et de 20 points cibles dont chaque nœud utilise un rayon de
transmission de 30 m et un rayon de capture de 29 m.

Chapitre IV Page 45
Chapitre IV : Implémentation

Une cible. Nœud actif. Nœud inactif.

Figure IV.7 : La première expérimentation avec 100 nœuds de capteur et 20
cibles déployés.
La figure IV.7 représente les résultats obtenus après l'application de
l'algorithme génétique utilisé. On note qu'après l’application de ce dernier
que tous les points cibles ont été couverts, en plus de cela, la connexion
entre le nœud émetteur et la station de base est également assurée, de plus,
on constate que seulement, 12 nœuds ont été sélectionnés sur 80 nœuds
actifs.
 Analyse énergétique pour les trois expérimentations :

Figure IV.8: Les différentes valeurs d’énergie obtenues dans les différents
RCSF simulés.
La figure IV.8 représente les résultats obtenus des différentes valeurs
d’énergie obtenues dans les différentes expérimentations réalisées. On

Chapitre IV Page 46
Chapitre IV : Implémentation

remarque que l'énergie des nœuds actifs nécessaire pour assurer la

couverture et la connectivité (représentée par la couleur rouge) est très
faible par rapport à l’énergie totale du réseau (représentée par la couleur
bleue). On remarque également que l'énergie restante (l'énergie du nœud
inactif représentée par la couleur verte) est très élevée, alors on peut
constater que le gain de performance significatif en termes d’énergie est
assuré, cela nous permet de maintenir la couverture et la connectivité le
plus longtemps possible ainsi le prolongement dans la durée de vie du
réseau.

IV.6-Conclusion :
Dans ce chapitre, nous avons exposé l’utilisation d’un l’algorithme
génétique adopté au problème de 1- couverture en calculant le plus court
chemin entre le nœud émetteur et la station de base. En utilisant divers
exemples de réseau, l’algorithme génétique utilisé est largement simulé
avec un nombre variable de nœuds de capteurs et de points cibles, ainsi que
la densité du réseau. De ca fait, on peut constater que cet algorithme utilisé
peut offrir une 1-couverture des points cibles et également maintenir la
connectivité entre les nœuds de capteurs actifs et la station de base pour
transmettre les données de détection dont la durée de vie du RCSF est
améliorée en désactivant les nœuds redondants.

Chapitre IV Page 47
Conclusion générale
 Conclusion générale

Les RCSFs fil représenteront sans aucun doute un développement

technologique majeur dans les années à venir, car ils apportent des
solutions à de nombreux problèmes dans de nombreux domaines
d'application liés à la sécurité et à la santé, etc. L’un des problèmes qu’on
peut rencontrer dans ce genre de réseau est la problématique de l'économie
d'énergie et l'amélioration de la durée de vie des RCSFs. L’utilisation de
batteries par des capteurs est une contrainte critique, dans lequel les
capteurs sont également parfois déployés sans surveillance et en si grand
nombre que leurs batteries sont difficiles à changer ou à recharger.
Nous avons suivi les étapes suivantes : dans la première étape, nous
avons présenté les réseaux de capteurs sans fil : leurs conceptions,
architectures de communication et leurs domaines d’applications. Nous
avons exposé également la notion de couverture dans la deuxième étape et
les différents types et les paramètres de couvertures utilisés par les RCSFs.
Enfin, nous avons décrit les critères liés au problème de couverture dans les
RCSFs et la classification des différents types de protocoles de la
couverture. Dans la troisième étape, nous avons présenté quelques méta-
heuristiques. Et ensuite, nous avons détaillé les algorithmes génétiques.
Dans ce travail de mémoire, nous avons utilisé un algorithme
génétique pour traiter le problème de 1-couverture. Cet algorithme est
adopté peut fournir une couverture complète des points cibles et également
maintenir la connectivité entre les nœuds de capteurs actifs et la station de
base pour transférer les données collectées. Une modélisation formelle de
ce problème est utilisée, capable de gérer l’objectif de la 1-couverture
traitée avec l'amélioration de la durée de vie du RCSF en désactivant les
nœuds redondants. En utilisant diverses expérimentations, l’algorithme
génétique utilisé est largement simulé avec un nombre variable de densité
du réseau et de points cibles. Enfin, nous pouvons dire que notre travail est
extensible. De ce fait, plusieurs améliorations et perspectives futures
restent à étudier. Entre elles, nous pouvons citer :
 Comparer notre travail de ce mémoire à d’autres travaux similaires ;
 Simuler l’algorithme génétique utilisé pour la 1-couverture par
d’autres simulateurs ;
 Utiliser le même algorithme génétique pour le problème du k-
couverture…..

Conclusion générale Page 48

 Bibliographie

[1] " Définition d’un réseau de capteurs sans fil " Disponible sur<
[Link] > (Consulté
le 22/01/2020).

[2] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci. " A survey

on sensor networks ". IEEE Communications Magazine, 40(8): 102-114, 2002.

[3] " Architecture d’un nœud capteur " Disponible sur<

[Link]
[Link] > (Consulté le 22/01/2020).

[4] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci. " Wireless

sensor networks : a survey. Elsevier Computer Networks Journal ", 38(4): 393-
422, 2002.

[5] J. Feng, F. Koushanfar and M. Potkonjak. " System-Architecture for

Sensor Networks Issues, Alternatives, and Directories ". In Proceedings of the
2002 IEEE International Conference on Computer Design, 2002.

[6] Kacimi, R. (2009). " Techniques de conservation d'énergie pour les réseaux
de capteurs sans fil " (Doctoral dissertation).

[7] " Architecture d'un réseau de capteurs " Disponible sur<

[Link]
[Link] > (Consulté le
22/12/2019).

[8] Villeneuve, E. (2012). " DOCTORAT DE L?UNIVERSITE DE

TOULOUSE " (Doctoral dissertation, Université Toulouse III).

[9] Mohamed, R. (2013)." Problèmes De Sécurité Dans Les Réseaux De

Capteurs Avec Prise En Charge De L? énergie?. " MEMOIRE DE
MAGISTER, UNIVERSITE DE SAAD DAHLAB DE BLIDA.

[10] Khelladi, L., & Badache, N. (2004). " Les réseaux de capteurs: état de
l’art ". Faculté électronique et informatique Bab Ezzouar-Algérie.

[11] Yacine CHALLAL " réseau de capteur sans fil ", support de cours,
17/11/2008.

[12] " La pile protocolaire d’un réseau de capteurs " Disponible sur<
[Link]
[Link] > (Consulté le
15/1/2020).

Bibliographie
 Bibliographie

[13] V. Rajavavivarme, Y. Yang, and T. Yang. " An overview of wireless

sensor network and applications ". In Proceedings of the 35th Southeastern
Symposium on System Theory, pages 432-436, 2003.

[14] M. Ilyas and I. Mahgoub. " Handbook of sensor networks Compact

wireless and wired Sensing Systems ", ISBN 08493196864. CRC PRESS LLS,
USA, 2005.

[15] Sofiane MOAD " Optimisation de la consommation d'énergie dans les

réseaux de capteurs sans fil " Master recherche en 2éme année informatique
Université : FSIC-Rennes 1, Laboratoire de recherche : DYONISOS-IRISA
2008.

[16] Sofiane, M. O. A. D., & Bouabdallah, N. (2008). " La consommation

d'énergie dans les réseaux de capteurs sans fil ". Rapport de recherche, Institut
De formation supérieure en informatique et communication IFSIC, Rennes.

[17] A. Manjeshwar and D. P. Agarwal. "Apteen : A hybrid protocol for

efficient routing ".

[18] " La sur écoute dans une transmission " Disponible sur<
[Link]
[Link] > (Consulté le 22/12/2019).

[19] " Les deux zones de couverture d’un capteur " Disponible sur<
[Link]
[Link] > Consulter le
(18/3/2020).
[20] .[Link], " Réseaux de capteurs : localisation, couverture et fusion de
données ", thèse doctorat, Université de Franche-Comté, 2008.

[21] J.P. Sheu, C.H. Yu, and S.C. Tu. " A distributed protocol for query
execution in sensor Networks. In IEEEWireless Communications and
Networking Conference (WCNC) ", vol.3, Pp.1824-1829, New Orleans, LA,
USA, 2005. .
[22] B. Wang, " Coverage Problems in Sensor Networks: A survey ", in ACM
Computing Surveys43, 2011, pp. 1-56.
[23] [Link] and [Link]. " Coverage in Wireless Sensor Networks".
Department of Computer Science and Engineering Florida Atlantic University
Boca Raton, FL 33431.

Bibliographie
 Bibliographie

[24] [Link], [Link]. " Maintien de la couverture

de surface dans les réseaux de capteurs avec une couche physique non idéale".
Univ. Lille 1. 59655 Villeneuve d’Ascq Cedex, FRANCE, 2006.

[25] I. Khou, P. Minet, A. Laouiti, and S. Mahfoudh, " Survey of Deployment

Algorithms in Wireless Sensor Networks: Coverage and Connectivity Issues
and Challenges ", in International Journal of Autonomous and Adaptive
Communications Systems, 2014, pp. 1-24.

[26] B. Wang, " Coverage Problems in Sensor Networks: A survey ", in ACM
Computing Surveys43, 2011, pp. 1-56.

[27] M. Cardei, D. MacCallum, X. Cheng, M. Min, X. Jia, D. Li, and D.Z. Du.
" Wireless Sensor Networks with Energy Efficient Organization. Journal of
Interconnection Networks ", vol.3, no. 3-4, pp.213-229, 2002.

[28] S. Slijepcevic and M. Potkonjak. " Power Efficient Organization of

Wireless Sensor Networks ". In proceedings of the IEEE International
Conference on Communications, vol.2 .472-476, 2001. [19] D.T. Lee. On k-
nearest neighbor Voronoi diagrams in

[29] M. T. Thai Y. Li M. Cardei and W. Wu. " Energy-Efficient Target

Coverage in Wireless Sensor Networks ". . In 24th Annual Joint Conference of
the IEEE Computer and Commu- nications Societies, 3 : 1976-1984, 2005.

[30] M. Potkonjak S. Meguerdichian, F. Koushanfar and M. Srivastava. "

Coverage Problems in Wireless Ad-Hoc Sensor Networks ". IEEE Infocom
2001, Vol 3, pp 1380-1387, April 2001.
[31] " Couverture des cibles " Disponible sur<
[Link]
[Link] > Consulter le (18/3/2020).

[32] S. Kumar, T. H. Lai and A. Arora. " Barrier Coverage With Wireless
Sensors. In Proceedings of the 11th annual international conference on Mobile
computing and networking ", pages 284-294, 2005.

[33] [Link]. " Partitionnement logique dans les réseaux de capteurs sans
fil. Université de Strasbourg ", Août 2010.

[34] S. K. Gaurav, B. Yigal and S. " Saswati. Lifetime and Coverage

Guarantees through Distributed Coordinate-Free Sensor Activation ". In
Proceedings of the 15th annual international conference on Mobile computing
and networking, pages 169-180, 2009

Bibliographie
 Bibliographie

[35] M. Ilyas and I. Mahgoub, " Handbook of Sensor Networks: Compact

Wireless and Wired Sensing Systems ", in CRC Press, Boca Raton, 2005.

[36] B. Wang, " Coverage Problems in Sensor Networks: A survey ", in ACM
Computing Surveys43, 2011, pp. 1-56.

[37] F. Ye, G. Zhong, J. Cheng, S. Lu, and L. Zhang. " Peas: A robust energy
conserving protocol for long-lived sensor networks ". In Proceedings of
International Conference on Distributed Computing Systems (ICDCS), pp. 28-
37, Rhode Island, USA, 2003

[38] : A. Gallais, J. Carle, D. " Simplot-Ryl and I. Stojmenovic. Localized

Sensor Area Coverage with Low Communication Overhead ". In IEEE
transactions on mobile computing, 7(5): 661-672, 2008.

[39] A. Gallais. " Ordonnancement d’activité dans les réseaux de capteurs :

l’exemple de la cou- verture de surface. Univ ". Lille 1. 59655 Villeneuve
d’Ascq Cedex, FRANCE, 2006.

[40] [Link], " Le traitement du problème de la couverture dans les

réseaux de capteurs sans fil, mémoire de magistère ", Université de Bejaia,
2010.

[41] A. Khalil, " Méthodes analytiques pour la couverture dans un réseau de

capteurs sans fil, mémoire de magistère ", Université de Béjaïa, 2010

[42] [Link] and P. Mohapatra. " Power conservation and quality of

surveillance in target tracking sensor networks. In Proceedings of ACM Mobile
Computing and networking (Mobicom) ", pp.129-143, Philadelphia, PA, USA,
2004.

[43] C. Gui and P. Mohapatra. " Power conservation and quality of

surveillance in target tracking sensor networks. In Proceedings of ACM Mobile
Computing and networking (Mobicom) ", pp.129-143, Philadelphia, PA, USA,
2004.

[44] D. E. Goldberg. " Genetic Algorithms in Search, Optimization, and

Machine Learning. Studies in Computational Intelligence. Addison-Wesley
Longman Publishing Co., Inc., 1st edition ", 1989. ISBN 0201157675.

[45] " Introduction aux algorithmes génétiques " Disponible

sur<[Link] > (Consulté le
22/09/2020).

Bibliographie
 Bibliographie

[46] Re Jean-Louis Le Moigne, dans " La modélisation des systèmes

complexes " (Ed. Dunot, 1991)

[47] " Définition d'une heuristique " Disponible sur

<[Link]
optimisation/heuristiques-meta-heuristiques > (Consulté le 22/09/2020).

[48] Abbas EL DOR. " Perfectionnement des algorithmes d’Optimisation par

Essaim Particulaire ". Applications en segmentation d’images et en
électronique. THÈSE DE DOCTORAT EN [Link]É
PARIS-EST. 2012

[49] F. Glover. " Future paths for integer programming and links to artificial
intelligence ".Computers and Operations Research, Vol. 13, pp. 533–549,
1986.

[50] I. H. Osman ET G. " Laporte: Metaheuristics: A bibliography. Annals of

Operations Research". 63:513.623, 1996.

[51] A. BAPTISTE, " Les métaheuristiques en optimisation combinatoire,

conservatoire national des arts et métiers paris ". 2006.

[52] Disponible sur <

[Link]
s:/[Link]/file/index/docid/753975/[Link]+8cd-1&hl-
fr&ctrclnk&gl-dz > (Consulté le 22/09/2020).

[53] I. Boussaïd, A. Chatterjee, P. Siarry, & M. Ahmed-Nacer. " Hybridizing

biogeography-based optimization with differential evolution for optimal power
allocation in wireless sensor networks ".

[54] J. Dréo, A. Petrowski, É. D. Taillard, & P. Siarry. " Métaheuristiques

pour l’optimisation difficile ". Eyrolles (Editions), November 2003. ISBN
2212113684.

[55] Terki Amel, " Analyse des performances des algorithmes génétiques
utilisant differentes techniques d'evolution de la popuiaton ", Universite
mentourn Constantine.

[56] oir (en) Vijay Vazirani, " Approximation algorithms, Springer Verlag ",
2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7), chap. 5 (« k-center »).

Bibliographie
 Bibliographie

[57] [Link] et R. Martin, " An Overview of Genetic Algorithms ": Part

2, departement of Computing Mathematics, University of Wales Collège of
Cardiff, CF2 4YN, 1993

[58] A. Nabonne. " Algorithmes évolutionnaires et problèmes inverses ",

chapitre 8, Juin 2004.

[59] [Link]," Optimisation de réseaux de neurones pour la

reconnaissance de chiffres manuscrits isolés: sélection et pondération des
primitives par algorithme génétique " . Université du Québec ,2002.

[60] " Le mécanisme de fonctionnement d’un (AG) " Disponible sur

<[Link]
[Link]/These/Papiers/Bibli2/[Link]+&c > (Consulté le
22/09/2020).

[61] Benahmed, " Optimisation de réscaux de neurones pour la reconnaissance

citres manuscrits isolés: sélection et pondération des primitives par algorithime
genetique ". Université du Qucbec, 2002.

[62] [Link]é et [Link]ızoğlu" Présentation des algorithmes génétiques et de

leurs applications en economie ", Universite de Nantes et Universite
Montesquicu Bordeux IV 2001.

[63] Adrian Biran et Moshe Breiner, " MATLAB pour l'ingénieur : Versions 6
et 7 ", Pearson Education, 2004 (ISBN 2744070254).

[64] " Les types de la sélection des parents " Disponible sur
[Link] > (Consulté le
22/09/2020).

[65] Harizan, S., & Kuila, P. (2019). " Coverage and connectivity aware
energy efficient scheduling in target based wireless sensor networks: an
improved genetic algorithm based approach ". Wireless Networks, 25(4), 1995-
2011.

[66] MEKKAOUI, K., & RAHMOUN, A. (2016). " Sensor Technology: Un

Clustering centralisé et dynamique basé sur les AGs pour une consommation
d'énergie minimale dans les réseaux de capteurs sans fil " (Doctoral
dissertation).

[67] Tchakonte, D. T. (2019). " Minimisation de la consommation d’énergie

des réseaux de capteurs dans les applications de couverture de cibles "
(Doctoral dissertation, Université Grenoble Alpes; Université de Yaoundé I).

Bibliographie
 Bibliographie

[68] Ngom, D. (2016). " Optimisation de la durée de vie dans les réseaux de
capteurs sans fil sous contraintes de couvertureet de connectivité réseau "
(Doctoral dissertation, Mulhouse).

Bibliographie