Chapitre 03 Conception du système
3.1 Introduction
Après avoir présenté l’aspect théorique de notre projet, et pour comprendre son
fonctionnement, nous passons à la conception, qui est une étape très importante dans le
processus de développement de logiciel. Dans ce chapitre, nous allons présenter l’architecture
globale que nous allons suivre dans la partie réalisation. Ensuite, nous allons clarifier l’analyse
des besoins ainsi que la conception du système. Puis nous allons construit un algorithme
génétique de tries non dominé (NSGA-II) qui optimise le déploiement des points d’accès dans
les serres intelligentes.
3.2. Contexte générale
Afin de clarifier notre travail, nous avons fait une contexte générale simplifiée, la figure
3.1 représente l'architecture d’une serre intelligente, nous voyons que nous disposons d'une
serre équipée de plusieurs capteurs qui recueillent des informations telles que la température et
l'humidité, ainsi qu'un certain nombre d'actionneurs tels que la pompe et système d’irrigation.
etc. Ces actionneurs et capteurs sont connectés à un micro-contrôleur Raspberry est responsable
de deux fonctionnalités :
Collecter des données à partir de capteurs et les envoyer à la station de base via un point
d’accès.
Contrôler les actionneurs installés dans chaque serre.
Figure 3.1 : Architecture d’une serre intelligente.
46
Chapitre 03 Conception du système
3.3. Architecture détaillée
Dans notre architecture explique en détail le déploiement de point d’accès, pour assurer la
connectivité de N serres, nous avons besoin d’un ensemble de composants électroniques
qui sont : Actionneurs, Capteurs, Collecteur (Sink intermédiaire), point d’accès (répéteur),
station de base (Sink principal).
Voir la figure 3.2 qui représente notre architecture globale.
Figure 3.2 : Architecture détaillée.
47
Chapitre 03 Conception du système
Nous mettons les serres dans certaines cellules de l’espace de 2D.
Nous mettons les capteurs sans fil à l'intérieur de chaque serre (capteur de température,
capteur d'humidité, capteur de lumière, etc.) qui détectent et recueillons des informations
sur l'environnement et les envoient au Sink intermédiaire (Raspberry dans notre cas).
Sink intermédiaire récupération des données des capteurs sans fil avant de les envoyer à le
Sink principal ou station de base et puisque les capteurs sans fil utilisent la communication
ZigBee, nous équipons notre Sink intermédiaire avec un module ZigBee pour lui permettre
de communiquer avec les capteurs sans fil.
Nous plaçons le Sink intermédiaire au centre de chaque cellule des serres qui utilisent la
communication Wi-Fi pour envoyer à le sink principal via les points d ‘accès.
Le Sink principal a également 2 rôles de réception et de collecte d'informations provenant
de chaque Sink intermédiaire avant d'envoyer ces informations à l’utilisateur via internet.
Le deuxième rôle est la réception des commandes de contrôle et la retransmission de ces
commandes à le Sink intermédiaire destiné à la serre correspondante.
3.4 L’optimisation dans le problème de déploiement de RSF :
La résolution d’un problème d’optimisation consiste à explorer un espace de recherche afin
de maximiser (ou minimiser) une fonction donnée.
Le problème de déploiement des RSFs est un problème NP-Difficile. Par conséquent, ce
problème ne pourrait pas être résolu grâce à des méthodes exactes, mais résolu par des méthodes
stochastiques telles que les algorithmes évolutionnaires. Ce problème peut être décrit comme
suit :
Soit A un espace de 2 dimensions, dans lequel un RSF va être déployé.
Un point d'accès déployé, dans la position (x, y) doit assurer deux tâches essentielles :
recevoir des données à partir des collecteurs (sink intermédiaire) dans positions (i, j), et les
communiquer à la plus proche (point d'accès ou station de base).
Chaque point d'accès dispose d’un rayon de couverture et d’un rayon de communication.
Si la distance euclidienne, séparant la position de point d'accès et de sink intermédiaire, est
inférieure au rayon de couverture R couv : ((l − i) ²+ (p − j) ² ≤ R couv).
La méthode d'optimisation multi-objectifs dans le présent travail est basée sur la NSGA-II.
Afin de résoudre le problème de déploiement, nous avons procédé à l’adaptation de méthode
(NSGA-II) qui ont été présentée précédemment.
48
Chapitre 03 Conception du système
3.5 L’objectif du système
L’objectif de notre travail est d’optimisé le placement des points d’accès dans un espace 2d qui
contient N serres qui permet d’avoir le minimum de point d'accès à déployer qui garantissent
une couverture parfaite. Aussi, nous devons assurer une bonne connectivité du réseau (max la
connectivité) en utilisant une méthode d’optimisation combinatoire, l’algorithme génétique de
tries non dominé (NSGAII). Notre système suit le schéma général de tout système
Figure 3.3 : Schéma général d’un système du system.
3.6 Méthode utilisée :
Notre système utilise l’algorithme génétique pour effectuer l’optimisation. Alors dans
cette partie, nous allons présenter l'adaptation d'algorithme NSGA-II à ce problème, en
suivons ces étapes jusqu’à atteindre la solution.
On va détaillée le fonctionnement de chaque partie de l’algorithme.
49
Chapitre 03 Conception du système
3.6.1 Définition d’un individu
Un individu correspond à une solution du problème à optimiser, Le codage d’un individu
peut être binaire, réel ou mixte. Dans notre problème, la solution représentée sous forme d’un
Vecteur réel de taille fixe contenant les positions des différents PA qui doivent répartie dans
l’espace, la présence ou pas d’un PA.
Exemple : en donne la taille de vecteur = la taille de l’espace 2D (nombre de cellule). La figure
(3,4) illustre la représentation de solution dans notre système.
Figure 3.4 : Représentation d’un individu du système.
La solution est appelée chromosome, et est composée des gènes, chaque gène peut représenter
par deux variable (x, y) et existence (0 ou 1).
3.6.2 Création de la population initiale :
Dans notre travail la population initiale est l’ensemble des solutions, ces solutions sont
générées de manière aléatoire dans la grille jusqu’à ce que cette dernière soit totalement
couverte. Générer aléatoirement les individus permet de créer une diversité de la population
tout en ne gardant que des solutions réalisables. La taille de la population N est choisie par
l’utilisateur, Un exemple de population initiale avec trois (03) individus :
Ind1 (x1, y1,1), (x2, y2,0), (x3, y3,0) …. (xn, yn,1)
Ind2 (x1, y1,0), (x2, y2,0), (x3, y3,1) …. (xn, yn,0)
Ind3 (x1, y1,1), (x2, y2,1), (x3, y3,0) …. (xn, yn,1)
50
Chapitre 03 Conception du système
3.6.3 Fonction d’évaluation (Fitness)
Dans ce problème, On aura la valeur de fitness pour chaque individu(solution) à partir des
objectifs imposés dans notre système (minimiser le cout, maximiser la couverture et la
connectivité). Ensuite, Les individus seront classés selon leur dominance par rapport aux
fonctions objectives et ainsi pouvoir identifier les fronts Pareto. Pour cela, nous dérivons trois
fonctions objectifs (fitness) soit A l’espace de déploiement.
F = F1 + F2+F3
F1 : coût
Partant de la définition de l’espace de déploiement, nous considérons une matrice de
déploiement D. Cette matrice est définie comme suit :
1 Si un noeud est deplyé dans la position(i, j)
D (i, j) = {
0 𝑠𝑖𝑛𝑜𝑛
Alors, la fonction de coût qui représente le nombre de nœuds déployés dans la région A.
Cost T(Type) = Σi Σj D (i, j) ∗ Cachât ∗ C installation
Le coût de déploiement qui est représenté par la somme des différents éléments de D.
Cachât, C installation : représentent le coût d’achat et d’installation du nœud déployé dans la cellule
(i, j).
F2 : Couverture :
Point couvert : un point p appartenant à l’espace de déploiement A est dit couvert par un
nœud s i si et seulement si, p appartient au périmètre de captage du nœud S i et aucun obstacle
n’existe entre p et Si. Cette définition peut être représentée
Mathématiquement comme suit :
ΦSi = {p |p ∈ sphère (si, Ri) ∧ ! O (→psi)
Où φSi représente l’ensemble des points couverts par le nœud S i. Sphère (si, Ri) représente
une sphère d’un rayon R i et centrée au nœud si, elle indique l’espace de captage du nœud si
O(→psi) est une variable binaire qui indique la présence (1), ou pas (0), d’un obstacle entre le
nœud s i et le point p.
1 Si la serre (i, j) est couverte par au moins 1 point d’accès
Cov A (i, j) = {
0 𝑠𝑖𝑛𝑜𝑛
51
Chapitre 03 Conception du système
𝛴𝑖=1𝛴𝑗=1𝑐𝑜𝑢𝑣(𝑖,𝑗)
Cov A (S) = ∗ 100
𝑁𝑜𝑚𝑏𝑟𝑒𝑑𝑒𝑆𝑒𝑟𝑟𝑒𝑠
F3 : Connectivité :
Nous avons vu dans le chapitre 1 qu’un lien sans-fil est déterminé en fonction de la puissance
du signal reçu qui est calculée grâce au modèle FRIIS
Chaque nœud doit pouvoir communiquer au minimum avec un autre nœud
E = {(Ne, Nr) ∈ V² e ‡ r ∧ RSSI (er) ≥ RX T sh}
RSSI (er) représente la puissance du signal transmis par le nœud Ne et calculée au niveau du
nœud Nr, RX T sh est la sensibilité de l’antenne de réception (elle représente la puissance
minimale autorisée pour établir une connexion).
Mathématique :
Minimise O1 = Σi (Xi)
Maximise O2 = CouV (Xi)
Maximise O3 = ConC (Xi)
Sous contraintes : PA ∈ A
Σi∈ A (a i, j. Pj) ≥ 1, ∀ j ∈ {1, . . ., |P|} : exprime la nécessité de couvrir chaque collecteur i par
au moins un point d’accès j
Xi : un vecteur
3.6.4 Sélection :
Dans notre cas, la sélection d’individus qui participent au croisement et à la mutation est réalisée
grâce à la méthode ”Tournoie” Elle est décrite dans le chapitre 2.
Les individus sélectionnés sont appelés parents et sont choisis pour participer à la phase
suivante appelée reproduction. Le parent doté de la meilleure valeur de fitness est sélectionné
Si les deux parents sélectionnés ont la même valeur de fitness selon l’algorithme nsga-ii
l’individu doté de la valeur minimale dite de Crowding distance est sélectionné.
Pour générer une nouvelle population, un génère une partie par mutation et l’autre par
croisement. Le nombre de mutations et de croisements est choisi par l ‘utilisateur comme
paramètre d’entrée.
3.6.5 Croisement :
L’opérateur de croisement consiste à appliquer un processus avec une certaine probabilité (Pc)
aux parents sélectionnes auparavant. Dans notre algorithme, nous utilisons le croisement à un
point pour générer de nouveaux individus (enfants), et sa selon le processus suivant :
52
Chapitre 03 Conception du système
Prendre les deux individus sélectionnés par la méthode élitiste.
Choisir le point de découper aléatoirement.
Combiner les deux individus (parents) pour produire deux nouveaux individus
(fils).
On prend en compte par l’opération de croisement les notes suivantes :
Héritabilité : Les enfants doivent hériter les propriétés génétiques de leurs
parents.
Validité : les enfants (individus générés) doivent appartenir à l’espace de
recherche.
La probabilité de croisement 𝑷𝒄 : probabilité de croiser deux parents, doit
comprise entre 0.5 et 0.9.
Figure 3.5 : Croissement.
3.6.6 Mutation :
On choisit aléatoirement deux points à partir de l′individu sélectionné et par une probabilité P m
est généralement comprise entre 0.001 et 0.01 et ensuite on fait une permutation entre les deux
gènes sélectionnés au hasard.
53
Chapitre 03 Conception du système
Figure 3.6 : Mutation.
3.6.7 Remplacement
Après la sélection et l’application des opérateurs génétiques on obtient une nouvelle population
Qt, cette population va être fusionnée avec l’ancienne Pt pour former Rt (qui est une population
de taille 2N), on va par la suite évaluer et classé Rt, sur le on applique la distance de Crowding
pour réajuste la taille de la population a N.
3.6.8 Critère d’arrêt
Tant que le critère d’arrêt qui est le nombre de génération prédéfinie n’est pas satisfait,
l’algorithme reste en fonction.
3.7 Conclusion
Dans cette section, nous étudions comment répartir un nombre de points d’accès.
Nous avons présenté une nouvelle solution qui assure la connectivité des serres intelligentes.
Dans ce chapitre, Nous avons vu au début une architecture d’un système qui peut conduire à
une conception convenable capable de résoudre le problème de déploiement de point d’accès.
Dans le chapitre suivant, nous allons détailler la réalisation de cette conception et les outils
utilisés pour implémenter notre système.
54
