3.4. Algorithmes d'ordonnancement d'activité
dans les RCSF :
L'activité des capteurs est ordonnancée en
fonction du critère de couverture de surface ou les noeuds doivent
coopérer et s'organiser de façon à ce que ceux qui
décident de se mettre en état actif couvrent une surface en tout
point équivalente à celle couverte par tous des capteurs. Pour ce
faire, les noeuds nécessitent l'évaluation de la couverture de la
zone de surveillance qui soit dans leur rayon de surveillance ou de celui des
leurs voisins. Nous supposons ici qu'un noeud doit calculer le taux de
couverture fourni par des voisins dont il connaît la position et le rayon
de surveillance. Différentes méthodes ont déjà
été proposées dans la littérature et nous en
faisons un résumé.
Les algorithmes d'ordonnancement d'activités
détectent d'abord les capteurs redondants du réseau, leurs
appliquent une stratégie d'ordonnancement, pour les faire passer du mode
actif au mode veille danse le but d'optimiser la consommation d'énergie
et maximiser la durée de vie du réseau. Nous citons dans ce qui
suit quelques algorithmes et techniques de quelques travaux récents :
a) Balanced Energy-based Sleep Scheduling (BS)
:
Dans [19,21], les auteurs ont mis au point une technique
d'ordonnancement de mise en veille équitable basé sur
l'énergie (BS). Le schéma de probabilité d'arrêt est
conçu de façon à répartir la consommation de
l'énergie de la détection et des tâches de transmission
uniformément entre tous les noeuds capteurs sans fil. La consommation de
l'énergie est contrôlée sur la base de la distance des
capteurs du chef du cluster. Par conséquent, la stratégie peut
être considérée comme un cas particulier de la
programmation basée sur la distance. Dans le schéma BS, les
auteurs ont également étudié le coefficient de variation
de la consommation d'énergie par noeud. Les expériences montrent
de meilleurs résultats pour les BS par rapport à la programmation
basée distance, simple.
b) Linear Distance-based Scheduling (LDS) :
Dans [20], la technique d'ordonnancement basé sur une
distance linéaire (LDS) est prévu pour l'adaptation des
périodes de veilles pour les capteurs dans une haute densité ou
redondance. L'idée générale du projet est de mettre les
capteurs en veille avec une probabilité plus élevée que la
distance de la densité la plus proche augmente. La probabilité de
la mise en veille est donc calculée en fonction de la distance d'un
capteur à partir de sa tête de grappe. La simulation donne des
résultats surpassant pour LDS en termes de durée de vie du
réseau par rapport au schéma randomisé (RS). Toutefois, en
gardant la tête du cluster de noeuds éveillé tout le temps
augmente les chances de collision et l'écoute ralenti. Afin de
répondre à ce problème Buddha Singh et K. Lobiyal
[21] ont proposé une nouvelle programmation de mise en veille
basé sur la densité de déploiement Gaussien.
c) Connectivity-based Partition Approach (CPA)
:
Une méthode d'ordonnancement de mise en veille et de
connectivité basée sur l'approche de la partition(CPA), qui est
l'algorithme distribué heuristique, est développée dans
[22]. La méthode d'ordonnancement partitionne les capteurs
déployés en groupes sur la base de la connectivité par
paires (entre les noeuds) des endroits plutôt géographiquement. La
connectivité du réseau est maintenue par les capteurs actifs de
chaque partition à la fois. En outre, les capteurs gardent l'alternation
entre état actif et sommeil périodiquement pour équilibrer
la charge de l'énergie. La
25
simulation des résultats ont montré que CPA a
une meilleure adaptabilité aux environnements où la propagation
radio est généralement non homogène.
d) Data-Coverage Sleep Scheduling (DCS) :
Une nouvelle approche d'ordonnancement de mise en veille pour
assurer la couverture (DCS) est fournie dans [23], ce dernier garantit non
seulement la réduction de la consommation d'énergie mais aussi
tente de récupérer les pertes de données dues à des
noeuds dans l'état de sommeil. Le système permet aux noeuds
actifs de retrouver les données manquantes des noeuds endormis en
exploitant la corrélation spatio-temporelle. En outre, un algorithme de
réduction est utilisé pour sélectionner l'ensemble des
noeuds actifs. Les simulations montrent une amélioration des
performances de DCS à l'égard de régime de couverture
complète de la région.
e) Range Based Sleep Scheduling (RBSS) :
Une autre technique d'ordonnancement de mise en veille est
décrite dans [24] pour conserver l'énergie tout en conservant la
couverture du réseau. Le système RBSS, n'a pas besoin des
informations de localisation des capteurs mais plutôt à la
distance du capteur à capteur. Schéma d'ordonnancement divise le
temps en périodes de longueur fixe appelés Round. Dans chaque
round, un protocole de recrutement pour sélectionner un ensemble de
capteurs co-travailleurs. Tous les autres que le maître, les noeuds
co-travailleurs sont mis en veille pour réduire la consommation
d'énergie. Les résultats montrent que RBSS avec moins de capteurs
actifs est mieux que ceux basés sur la localisation.
f) Garg-Konemann (GK) scheme and linear programming
duality :
Dans [25], l'ordonnancement de la mise en veille est
modélisé comme sous problème de partitionnement en
exploitant la relation de redondance par paires entre les noeuds capteurs.
Cette approche distribuée utilise un algorithme d'approximation qui est
basé sur le schéma Garg - Konemann (GK) et programmation
linéaire. Le schéma GK comprend en outre un algorithme
distribué asynchrone qui permet d'approximation du problème du
sous graphe minimum de valeur supérieur (Problème MWDS).
g) Distributed Sleep Scheduling Algorithm with Range
Adjustment (DSRA) :
Pour éviter la assurer la couverture et de prolonger
durée de vie du réseau, les auteurs de [26] ont
présenté un algorithme d'ordonnancement de mise en veille avec
ajustement d'échelle (CSRD). C'est basé sur l'énergie
résiduelle d'un noeud capteur ainsi que la taille de la région de
entre le noeud et ses voisins. En outre, la communication est assurée
entre les noeuds actifs et ajustés de façon à fournir une
couverture complète. Les résultats de simulation fournissent de
meilleurs résultats par rapport aux techniques de couverture
aléatoire.
| 
