FR 2959637 A1 20111104 FR 1001869 A 20100430 Procédé et dispositif de configuration d'un réseau de capteurs sans fils déposés La présente invention concerne un procédé de configuration d'un réseau de capteurs sans fils déposés, du type constitué de noeuds interconnectés comportant chacun un capteur, une source propre d'alimentation en énergie, des moyens de calcul, des moyens de communication, des moyens de sauvegarde d'une configuration de fonctionnement et des moyens de gestion de son fonctionnement en fonction de cette configuration mémorisée. Les Réseaux de Capteurs Sans-fil Déposés, désignés RCSD dans la suite (en anglais « UGS networks » - Unattended Ground Sensor networks), sont destinés à détecter une intrusion dans une zone à surveiller et à prévenir de cette intrusion après détection. Ils sont composés de dispositifs autonomes formant des noeuds qui possèdent une alimentation autonome en énergie, des capacités de communication radio, des capacités d'observation (via l'utilisation de transducteurs ou de modules plus complexes), et des capacités de calcul (plus ou moins élevées). Ces noeuds sont mis en réseau en utilisant le plus souvent des fonctions d'auto organisation à la manière des réseaux dits « ad hoc ». Dans ce cas, puisque la communication n'est a priori possible qu'entre les noeuds en portée radio, un protocole de routage (par exemple Direct Diffusion) assure alors le relai des paquets de données pour assurer la connectivité de bout en bout lorsque la topologie du réseau le permet. Dans les RCSD, les noeuds sont déposés (par exemple largage par un avion, dépose par un opérateur à pied) à une localisation ou dans une zone géographique donnée afin d'accomplir une fonction de surveillance. Les capteurs déposés surveillent de manière collaborative (ou non) les activités d'intérêt (par exemple, intrusions) dans la zone où ils opèrent, puis remontent des alertes vers des noeuds dits « passerelles » (gateway, en anglais) afin qu'elles soient transmises vers d'autres parties du système de surveillance (par exemple centre de commande et contrôle, autres capteurs, actuateurs). Les RCSD ont des applications militaires dans le cadre de missions de surveillance, mais aussi civiles pour la surveillance d'infrastructures critiques (par exemple usines classifiées, ponts) ou pour la surveillance environnementale (par exemple risque sismique, agriculture, écologie). Les noeuds RCSD ont en général des contraintes d'alimentation en énergie. Dans la majorité de cas, ils opèrent sur batterie. Pour économiser la batterie, ils sont équipés de mécanisme de mise en veille par intermittence des capteurs de mesure et des moyens de transmission. L'opérateur doit alors, lors du déploiement ou en cours d'opération, décider d'un certain nombre de paramètres du système à savoir : • L'emplacement de chaque noeud, qui a une influence sur la performance en termes de détection. • La durée pendant laquelle et le nombre de fois qu'un capteur observe un phénomène qui a une influence sur la consommation énergétique du capteur et, plus globalement, un impact global sur la durée du vie du système et sur la dégradation dans le temps de ses performances de détection. • La durée pendant laquelle et le nombre de fois qu'un capteur active son interface de communication sans-fil pour recevoir ou envoyer des informations a un impact sur la durée de vie du capteur et sur les performances réseaux, en termes de délai de transmission notamment. Le choix des paramètres du système influence fortement ses performances. Par exemple les indicateurs de performances suivants sont définis : • Pmd (Probabilité de non-détection ou en anglais - Probability of missdetection): Il s'agit de la probabilité que le réseau ne détecte pas un événement (par exemple arrivée d'une cible ou d'un phénomène) sachant qu'il est en train de se produire. Cette probabilité dépend par exemple du niveau de vigilance des noeuds (par exemple fréquence d'échantillonnage du signal sismique), de leur position géographique, de la capacité des capteurs à corréler de manière collaborative leurs observations. • Far (Taux de fausses alarmes ou en anglais - False alarm rate) : Il s'agit du nombre de fois par unité de temps que le système remontre des alarmes relatives à des événements inintéressants. Par exemple, si le système remonte une alarme disant qu'un piéton vient de s'introduire dans la zone alors qu'il s'agit d'un gibier. Des techniques de classification (pouvant être distribuées) sont généralement utilisées pour « désambiguïser » les alarmes. • D (Délais de transmission de l'alerte) : il s'agit du délai de transmission de l'alerte vers le noeud passerelle. Ce délai dépend en général du protocole MAC (Medium Access Control) et du routage utilisé ainsi que des paramètres associés. • L (Durée de vie du système ou en anglais û Lifetime) : cet indicateur donne le temps pendant lequel le système est considéré comme opérationnel. II 30 peut être calculé de différentes manières, par exemple : durée jusqu'à ce qu'au moins un capteur manque d'énergie pour fonctionner. Dans les RCSD, l'opérationnel en charge de sa configuration et de son déploiement doit donc décider des paramètres système correspondant à un point de fonctionnement donné (par exemple Pmd Dans P. Medagliani, J. Leguay, V. Gay, M. Lopez Ramos, G. Ferrari. Engineering Energy-Efficient Target Detection Applications in Wireless Sensor Networks. Conference IEEE Percom 2010 (Mannheim, Germany, March 2010) désigné dans la suite par [Meda09], les auteurs considèrent le cas d'un déploiement stochastique et étendent le travail de L. Lazos, R. Poovendran, and J. A. Ritcey, "Analytic evaluation of target detection in heterogeneous wireless sensor networks," ACM Trans. Sensor Networks, vol. 5, no. 2, pp. 1-38, March 2009, en intégrant le fait que les capteurs puissent réaliser leurs observations de manière périodique (et non de manière permanente) afin de réduire leur consommation énergétique. Les auteurs proposent également une modélisation du délai de transmission des alertes en considérant le cas du protocole X-MAC, qui utilise également des activations/désactivations périodiques de l'interface de communication pour réduire la consommation énergétique. Enfin, ce travail comprend un modèle de la consommation énergétique d'un réseau de capteurs, permettant de déduire de manière plus globale la durée de vie du réseau en fonction de l'énergie restante et du niveau d'activités/vigilance du réseau RCSD. Les auteurs montrent l'utilisation de ce cadre analytique à l'aide de techniques d'optimisation multi objectifs. Ceci permet à l'opérateur de visualiser les performances globales du système en fonction de ses contraintes (par exemple durée de vie, performance de détection). L'opérateur peut ainsi percevoir les compromis auxquels il doit faire face et décider de la configuration qu'il souhaite adopter. L'outil proposé est utilisé pour un nombre de noeuds fixe, déployés de manière aléatoire. Dans J.J. Sylvester, "On a funicular solution of Buffon's "problem of the needle" in its most general form," Acta Mathematica, vol. 14, no. 1, pp. 185-205, 1890., Sylvester adresse le problème géométrique dit « de l'aiguille » : Un plan est strié de droites parallèles espacées d'une distance. On lance au hasard une aiguille de longueur 1. Avec quelle probabilité l'aiguille coupe-t-elle une des droites ? La résolution de ce problème par Sylvester permet de raffiner analytiquement la borne supérieure donnée par L. Lazos, R. Poovendran, and J. A. Ritcey, "Analytic evaluation of target detection in heterogeneous wireless sensor networks," ACM Trans. Sensor Networks, vol. 5, no. 2, pp. 1-38, March 2009, pour la probabilité de non-détection dans le cas déterministe. Le cadre analytique proposé dans [Meda09] permet de modéliser un système RCSD dans le cadre d'un déploiement stochastique. D'un point de vu opérationnel, les opérateurs peuvent manipuler ce modèle en utilisant des outils d'optimisation pour observer l'espace des configurations optimales en fonction des objectifs et contraintes définis par l'opérateur lui-même. Ceci permet de comprendre les compromis sous-jacents au fonctionnement du système. Les contraintes et objectifs peuvent être par exemple de maximisation des performances de détection sous réserve de contraintes sur les délais de transmission des alertes. Ce modèle et l'outillage ne fournissent pas de résultats spécifiques à un déploiement donné de capteurs (cas plus intéressant pour les opérateurs de RCSD). Ils fournissent des résultats moyens (au sens mathématique) devant être utilisés à titre indicatif par les opérateurs afin de décider du paramétrage de leur réseau. Par ailleurs ils ne permettent pas d'aider l'opérateur à placer les noeuds dans une zone géographique particulière. Enfin, il n'existe pas d'outil permettant à l'opérateur de connaître le nombre minimal de noeuds requis pour satisfaire les contraintes et objectifs opérationnels à remplir. Les méthodes de l'état de la technique ne permettent pas d'assister les opérateurs de RCSD pour le placement des noeuds et la configuration des paramètres du système dans le cadre de contextes opérationnels particuliers du type surveillance de camp/zone. Par ailleurs, les méthodes de l'état de la technique ne permettent pas de déterminer le nombre minimum de noeuds requis sur un ensemble de zones distinctes à surveiller, chacune ayant des contraintes et objectifs opérationnels particuliers. L'invention a pour but de proposer un procédé et un dispositif de configuration d'un réseau de capteurs sans fils déposés dans un ou plusieurs zones géographiques qui permettent de déterminer le nombre et la position des capteurs pour atteindre des performances, répondant à des critères de performance cibles. A cet effet, l'invention a pour objet un procédé de configuration d'un réseau de capteurs sans fils déposés du type précité, caractérisé en ce qu'il comporte les étapes suivantes 1. Définir des critères de performance constituant des contraintes, avec des valeurs seuil associées, et au moins un critère de performance à optimiser, pour au moins une zone à équiper de noeuds, chaque critère de performance étant défini par un modèle 2. Définir pour la ou chaque zone : a. Des caractéristiques de la zone b. Des caractéristiques des capteurs dans la zone 3. Allouer à la ou chaque zone à équiper, un nombre de noeuds 4. Appliquer un processus d'optimisation par zone sur la ou chaque zone, le processus d'optimisation par zone mettant en oeuvre les étapes suivantes : 30 a. Déterminer la position des noeuds dans la zone si il existe pour satisfaire un critère d'optimisation prédéterminé ; b. Déterminer un point de fonctionnement si il existe, caractérisant le comportement du réseau de capteurs dans la zone, et c. Déterminer la configuration du réseau de capteurs dans la zone si elle existe, définissant les paramètres de configuration du réseau de capteurs, et d. Déterminer le besoin éventuel d'utiliser davantage de noeuds ou réviser les critères de performance définis à l'étape 1, 5. Augmenter le nombre de noeuds ou modifier les critères de performance définis dans la ou chaque zone où les critères de performance ne sont pas satisfaits et reproduire dans ces zones le processus d'optimisation par zone avec le nouveau nombre de noeuds ou les nouveaux critères de performance, et 6. Appliquer la configuration déterminée à chaque noeud dans la ou chaque zone. Suivant des modes particuliers de réalisation, le procédé comporte l'une ou plusieurs des caractéristiques suivantes : - l'étape de définition des critères de performance à optimiser comprend la définition d'une valeur seuil à atteindre pour au moins un critère de performance à optimiser, et le processus d'optimisation par zone comporte une étape d'incrémentions du nombre de noeuds pour équiper la zone, si au moins un critère de performance à optimiser n'est pas satisfait afin de déterminer le nombre minimal de noeuds requis pour satisfaire les critères de performance et une reproduction des étapes 4a à 4c avec le nouveau nombre de noeuds incrémenté. ; - l'étape de définition des critères de performance à optimiser comprend la définition d'une valeur seuil à atteindre pour au moins un critère de performance à optimiser, et le processus d'optimisation par zone comporte une étape de décrémentation du nombre de noeuds pour équiper la zone, si tous les critères de performance à optimiser sont satisfaits afin de déterminer le nombre minimal de noeuds requis pour satisfaire les critères de performance et une reproduction des étapes 4a à 4c avec le nouveau nombre de noeuds décrémenté ; - l'étape de définition des caractéristiques de la zone comprend la définition d'une valeur minimale pour la dimension de la zone, et le processus d'optimisation par zone comporte des étapes successives d'incrémentation de la dimension de la zone et de reproduction des étapes 4a à 4c avec la nouvelle dimension de la zone, jusqu'à ce qu'il n'existe aucun point de fonctionnement satisfaisant les critères de performances contraintes constituant des contraintes ; - le critère d'optimisation prédéterminé, pour la détermination de la position des noeuds, est de minimiser une probabilité de non détection par le réseau sous l'hypothèse d'une activation permanente du capteur de chaque noeud ; - l'étape d'allocation des noeuds comprend, dans au une zone, la fixation de positions imposées pour au moins un noeud dans la zone et l'étape de détermination de la position des noeuds prend en compte les positions imposées pour au moins ledit noeud ; et - le procédé comporte, une modélisation analytique de la probabilité de non-détection d'une cible mettant en oeuvre les positions connues des capteurs. L'invention a pour objet un dispositif de configuration d'un réseau de capteurs sans fils déposés du type précité, comportant des moyens de mise en oeuvre des étapes du procédé tel que défini ci-dessus. L'invention a également pour objet un programme d'ordinateur comportant des instructions propres mettant en oeuvre le procédé tel que défini ci-dessus, lorsque mis en oeuvre sur ordinateur. L'invention sera mieux comprise à la lecture de la description qui va suivre, donnée uniquement à titre d'exemple et faite en se référant aux dessins sur lesquels : - la figure 1 est un schéma illustrant un réseau de capteurs sans fils déposés protégeant un camp ; - la figure 2 est une vue schématique du dispositif mettant en oeuvre le procédé de configuration selon l'invention ; - la figure 3 est un organigramme du procédé général selon l'invention pour un exemple de mise en oeuvre sur 3 zones géographiques - la figure 4 est un schéma d'un exemple des résultats successifs du procédé général selon l'invention ; - la figure 5 est un organigramme d'une sous-procédure mise en oeuvre dans le procédé selon l'invention illustrée sur la figure 3 ; - la figure 6 est un graphique montrant un espace de solutions satisfaisant les critères de performance dans le cadre de la mise en oeuvre d'une sous-procédure mise en oeuvre dans le procédé selon l'invention ; - la figure 7 est un schéma d'un exemple des résultats successifs de la sous-procédure décrite en regard de la figure 5 ; - la figure 8 est une vue schématique de la plage de couverture d'un noeud du réseau de capteurs ; - la figure 9 est un schéma illustrant les cycles d'endormissement d'un module d'un noeud ; - les figures 10, 11 et 12 sont des vues schématique des plages de couverture de deux noeuds illustrant différents calculs mis en oeuvre dans le procédé ; et - la figure 13 est un vue illustrant le déploiement de capteurs dans une zone . Sur la figure 1 est représenté vue de dessus terrain devant être protégé. Au centre se trouve un campement 1 équipé d'un terminal de surveillance 1A vers lequel les éventuelles alarmes de détection d'intrusions sont remontées par un réseau de capteurs sans fils déposés désigné par RCSD dans la suite. Ce réseau comporte un ensemble de noeuds 2 interconnectés par des liaisons sans fils 3 reliant de manière directe ou indirecte les noeuds au terminal de surveillance 1A. Les liaisons indirectes se font comme connu en soi au travers d'autres noeuds intermédiaires. Les noeuds 2 correspondent chacun à un capteur du réseau. Ils comportent chacun par exemple un capteur sismique permettant de détecter une vibration du sol dans son champ d'action lorsqu'une personne ou un véhicule y pénètre. Chacun des noeuds possède outre son propre capteur, une source propre d'alimentation en énergie, ses moyens de communication avec les autres noeuds 2 et/ou le terminal 1A, ses propres moyens de calculs ainsi que des moyens de sauvegarde d'une configuration de fonctionnement et de gestion de son fonctionnement en fonction de cette configuration mémorisée. Dans l'exemple de la figure 1, les noeuds 2 sont répartis dans deux zones concentriques 4A et 4B entourant le campement 1. Ces zones, couramment dénommées glacis, constituent zones de détection d'une éventuelle intrusion par différents noeuds porteurs de capteurs. Dans chacune de ces zones, le RCSD est configuré de manière différente afin d'atteindre des performances cibles différentes. Le procédé est mis en oeuvre dans un dispositif portable utilisé par l'opérateur et comportant notamment, comme illustré sur la figure 2 : - une unité de traitement d'information 5, - un clavier de saisie d'information 6, - un écran 7 d'affichage pour la mise à disposition d'information pour l'opérateur - une base de données 8 contenant notamment : - les caractéristiques des noeuds utilisables et leur modèle de comportement ; - un modèle pour chaque critère de performance en fonction du nombre de noeuds déployés ; et - le procédé mis en oeuvre selon l'invention, et - une interface 9 de connexion temporaire à chaque noeud pour la sauvegarde dans celui-ci de sa configuration Comme connu en soi, notamment de [Meda09], plusieurs critères de performance, notés CP, sont définis pour caractériser le fonctionnement d'un RCSD dans une zone donnée. Par exemple, sont considérés comme CP : • La probabilité de non-détection (Pmd) • Le délai de transmission des alertes (D) • La durée de vie du système (L) Pour chaque type de CP, le dispositif mettant en oeuvre le procédé comporte un modèle sous forme empirique (par exemple abaque) ou analytique (par exemple expression mathématique). Chaque modèle prend en compte les paramètres configurables du système décrits en section dans la suite (par exemple : placement des noeuds, proportion du temps où le module capteur est actif (3sens, proportion du temps où le module radio est actif Rcomm)• Un exemple pour chacun des CP mentionnés ci-dessus est donné dans la suite de la description. Dans le cadre du déploiement d'un RCSD à des fins de surveillance, deux catégories de CP sont définies : • Les CP constituant des Contraintes (CPC) : ce sont des CP pour lesquels l'opérateur définit un ensemble de valeurs "seuil", noté CPC*, qui contraignent le point de fonctionnement à atteindre. Par exemple, le RCSD doit opérer de manière telle que Pmd soit inférieur à (Pmd)* = 10%, autrement dit telle que la probabilité de manquer une cible traversant la zone soit inférieur à 10%. • Les CP à Optimiser (CPO) : ce sont des CP pour lesquels l'opérateur souhaite connaître la valeur optimale sous réserve de CPC* donnés. Le(s) type(s) de CPO indique(nt) implicitement la(les) direction(s) selon laquelle(lesquelles) une technique d'optimisation, FOPT, définie plus loin dans la description doit opérer. Par exemple : CPO={ Pmd } : Minimisation de la probabilité de non-détection Pmd o CPO={L} : Maximisation du temps de vie du système L o CPO={D} : Minimisation du délai de transmission des alertes D Par exemple, l'opérateur souhaite maximiser L au vu de contraintes sur Pmd et D, on a : CPO={L}, CPC={Pmd, D}, avec CPC*={Pmd * = 10% et D* = 100ms}. Dans ce cas, la technique d'optimisation indique par exemple que la valeur maximale de L est de 30 jours. Lors de la mise en oeuvre du procédé, l'opérateur spécifie initialement parmi l'ensemble des CP au moins un CPC, associé à une valeur CPC*, et au moins un CPO. Un type de CP ne peut être à la fois associé à un CPC et un CPO. On appelle point de fonctionnement, noté PF, un n-uplet de valeurs correspondant aux différents CP, qui caractérise le fonctionnement du RCSD pour un dimensionnement donné des paramètres système du RCSD. Par exemple, pour le paramétrage (j3sens = 4%, Rcomm =13%) et un certain placement de noeuds, le point de fonctionnement PF est ainsi défini : Pmd = 17% , D = 113ms, L = 27 jours. Le but du procédé est d'assister un opérateur en charge du déploiement ou de la maintenance d'un RCSD en l'aidant à faire les choix de configuration système au regard de. • Contraintes opérationnelles. Par exemple : Valeurs "seuil" sur les CPC. Par exemple, le point de fonctionnement sur une zone doit satisfaire que la probabilité de non-détection d'une cible est inférieure à 10% (Pmd* = 10%). o Positionnement de certains noeuds grâce à la connaissance qu'a l'opérateur du terrain. (optionnel) Valeurs « objectif » sur les CPO. Par exemple, il faut que la meilleure durée de vie atteignable soit d'au moins 100 jours. Le procédé peut être utilisé pour configurer k sous-systèmes déployés dans un ensemble de zones à surveiller, noté Z = {Z1, Z2, ..., Zk}, chaque zone ayant des contraintes opérationnelles spécifiques. Pour déterminer la configuration optimale d'une zone, le procédé prévoit deux modes que l'opérateur peut sélectionner et qui correspondent à deux approches différentes : o MODE1 : l'opérateur souhaite opérer le sous-système d'une manière qui satisfasse en priorité des contraintes sur certains CP (CPC), peu importe la valeur optimale obtenue sur d'autres CP (CPO). Dans ce cas, aucun objectif n'est fixé sur le CP à optimiser. Le but est de déterminer, s'il existe, le PF optimal pour un nombre de noeuds donné, c'est-à-dire le PF qui respecte les contraintes et donne la meilleure valeur que l'on puisse espérer pour CPO, peu importe cette dernière. Par exemple, si CPO={L}, CPC={Pmd, D}, avec CPC*={Pmd * = 10% et D* =100ms}, le procédé détermine que le meilleur point de fonctionnement, avec 5 noeuds, au vu de L, est tel que : L = 30 jours, Pmd = 10%, D = 100ms. o MODE2 : l'opérateur souhaite opérer le RCSD d'une manière qui satisfasse d'une part les contraintes sur certains CP et, d'autre part, telle que la valeur optimale sur certains CP, soit au-delà d'une valeur « objectif », noté CPOobJ. Un objectif est fixé sur le CP à optimiser. Le but est de déterminer le nombre 10 minimum de noeuds à utiliser tel que CPOobi est atteint et les contraintes sont respectées pour le PF optimal. Par exemple, si CPO={L} avec CPOobJ = Lobs = 10 jours, et CPC={Pmd, D}, avec CPC*={Pmd * = 10% et D* = 100ms}, le procédé indique que le nombre minimum de noeuds requis pour que le sous-système dure au moins 10 jours est de 3 noeuds. 15 En jouant sur le nombre de noeuds, leurs positions éventuelles, sur les contraintes (par exemple CPC*, dimension de la zone) et objectifs définis (par exemple CPOobj), l'opérateur est invité à faire fonctionner le procédé global, noté PROC_GLOBALZ, de manière itérative jusqu'à trouver les points de fonctionnement le satisfaisant pour l'ensemble des zones dans la limite du nombre total de noeuds à sa disposition 20 Le procédé global d'assistance au déploiement est noté PROC_GLOBALZ. Ce procédé s'applique sur un ensemble de zones Z dont les caractéristiques et contraintes opérationnelles varient. La figure 3 montre le principe de fonctionnement du procédé global dans le cas où 3 zones sont mises en oeuvre. 25 Selon l'invention, le procédé est itératif et les étapes principales sont mises en oeuvre plusieurs fois avec des nombres de noeuds différents. De manière schématique, pour commencer à utiliser le procédé, l'opérateur : • Indique aux étapes 10 les caractéristiques invariantes des zones qu'il souhaite protéger (par exemple dimensions, énergie initiale contenue dans les noeuds) 30 • Initialise aux étapes 12 un jeu de contraintes CPC et objectifs CPO qu'il souhaite atteindre sur les critères de performances de chaque zone. Après itération du procédé, l'opérateur : • Analyse les résultats en visualisant les zones qui nécessitent davantage de noeuds et/ou un relâchement des contraintes CPC et objectifs CPO. Tant qu'il n'a pas abouti à une configuration réalisable répondant à ses besoins opérationnels sur chaque zone (par exemple : il reste des zones où aucun point de fonctionnement ne satisfait les contraintes, ou des zones où l'objectif sur le CP à optimiser n'est pas atteint), les étapes du procédé sont réitérées : • En augmentant à l'étape 14 le nombre de noeuds utilisés dans certaines zones, à condition que des noeuds puissent leur être réallouées • En relâchant à l'étape 16 certaines des contraintes ou objectifs sur le CP à optimiser dans ces zones Le procédé global PROC_GLOBALz est appelé comme suit. On détaille ci-après les entrées et sorties correspondantes ainsi que le fonctionnement. PROC GLOBALZ( Ntot, (CPC*W, CPOoe, POSNO('), Ns,,ppr" Nmax('), dW) pour toute zone Z,) = ((POSNreq(i), PFop Sorties L'opérateur obtient en sortie : o Nréa,,oa : le nombre de noeuds pouvant être réalloués. Pour chaque zone Z; ^ POSNreq(') : le positionnement de l'ensemble des noeuds ^ PF0,, : le point de fonctionnement optimal au vu des CPC* (et CPOobj si ce dernier est défini), c.à.d les valeurs de CP qui satisfont CPC* et CPOobj avec la configuration système bas-niveau du RCSD correspondant à ces valeurs. CONF(') : le paramétrage du système (par exemple (3sens, Rcom) correspondant au point de fonctionnement PFopt('' ^ NreQW : le nombre minimum de noeuds requis dans la zone ^ Me Motif de sortie de PROC Z;(CPC*0), CPOobj('), POSNOW, Nsupp(i), Nmex0), Le procédé fonctionne de manière itérative en sollicitant une interaction avec l'opérateur à la fin de chaque itération. En particulier, une itération du procédé global consiste à : • Appliquer un processus d'optimisation par zone, par application aux étapes 22 d'une procédure PROCZ; décrite en regard de la figure 5 ou PROC_MAX-SURFACEZ; sur chacune des zones. • Interagir avec l'opérateur en lui présentant les résultats sur l'ensemble des zones, notamment dans les zones qui nécessitent davantage de noeuds et/ou un relâchement des contraintes et objectifs. • Enregistrer les nouvelles entrées à appliquer sur les zones (par exemple ajout de noeuds, assouplissement des contraintes). Tant qu'une configuration réalisable répondant aux besoins opérationnels de l'opérateur n'est pas atteinte sur chaque zone, le procédé est réitéré en initialisant ou modifiant le jeu de contraintes et objectifs que l'opérateur souhaite atteindre. Le procédé peut ainsi s'exprimer par l'algorithme qui suit décrit toujours en regard de la figure 3. RETOUR = CONTINUER PROBLEME = NULL (la variable PROBLEME indique si une zone ne peut satisfaire les CP avec les Nreq('» Tant que RETOUR = CONTINUER Pour chaque zone Z;, Exécuter à l'étape 22 le processus d'optimisation par zone : PROCZ; Stocker à l'étape 24 : NfegW : le nombre de noeuds requis dans la zone POSN(0: le positionnement des noeuds dans la zone PFopt(i) : le point de fonctionnement optimal s'il a été déterminé CONF('): le paramétrage du système correspondant MS(» : le motif de sortie de PROCZ; Si le motif de sortie de PROCz; est ECHEC_CONTRAINTES-IRREALISABLES ou ECHEC_CPO-OBJECTIF-INATTEIGNABLE PROBLEME = VRAI Un test est effectué à l'étape 26 pour déterminer suivant la valeur de la variable PROBLEME, si les CP ne peuvent être atteints dans au moins une zone. Si PROBLEME = NULL Afficher, à l'étape 28, pour chaque zone : Nreq('), PFopt(», POSN('), CONF0)et le motif de sortie. RETOUR = STOP Sinon : Calculer, à l'étape 30, le cumul de noeuds requis au minimum sur l'ensemble des zones et le nombre de noeuds pouvant être potentiellement réalloués Nréalloc. A l'étape 32, un test est effectué sur la valeur de Nréalloc. Si Nréalloc est nul L'opérateur est informé à l'étape 14 qu'il est impossible de configurer un RCSD sur l'ensemble des zones dans la limite des noeuds disponibles et au vu des contraintes et objectifs éventuellement définis. Suggérer à l'étape 14 de relâcher les contraintes et/ou objectifs éventuellement définis dans les zones dont le motif de sortie est ECHEC_CONTRAINTES- IRREALISABLES ou ECHEC_CPO-OBJECTIF-INATTEIGNABLE RETOUR = STOP Sinon Faire réallouer à l'opérateur à l'étape 16 les noeuds disponibles aux zones ayant retourné ECHEC_CONTRAINTES-IRREALISABLES ou ECHEC_CPO-OBJECTIF- INATTEIGNABLE Mémoriser aux étapes 10 et/ou 12 la nouvelle allocation de noeuds par zone et/ou les nouvelles contraintes et/ou les nouveaux objectifs. PROBLEME = NULL Recommencer Exemple d'itération du procédé global La figure 4 montre le déroulement du procédé global sur trois zones où 2 itérations seront nécessaires pour trouver une configuration réalisable sur l'ensemble des zones. Le fonctionnement du processus d'optimisation sur une zone Z noté PROCz va maintenant être décrit en regard de la figure 5. II peut être instancié selon les 2 modes MODE1 et MODE2 décrits précédemment. On détaille ci-après les entrées et sorties correspondantes. PROCz(CPC , CPOopi, POSNO, N,wpp, Nmax, d) = (POSN PFopt, Nreq, CONF, MS) Entrées Les entrées suivantes peuvent être initialisées par l'opérateur au premier appel du procédé, ou incrémentées ou décrémentées lors d'une itération du procédé. Les entrées se répartissent comme suit : Constantes sur les noeuds : o Ej : l'énergie initiale contenue dans la batterie du noeud j Constantes sur le dimensionnement du système : o d: la dimension de la zone (par exemple largeur de la zone carrée à surveiller de 1000m) - Nombre et positions des noeuds : o Nsupp : le nombre de capteurs à déployer dont la position n'est pas imposée par l'opérateur. o (optionnel) POSNO: la position souhaitée d'un sous-ensemble No de noeuds. o (optionnel) Nmax le nombre de noeuds maximum à déployer dans la zone si l'opérateur dispose d'un nombre limité de noeuds. - Contraintes opérationnelles o CPC*: la valeur "seuil" des CP Contraintes. Par exemple : ^ Pmd* = 10% (Probabilité de non-détection inférieure à 10%) ^ D* = 100ms (Délai de transmission de l'alerte jusqu'au noeud passerelle inférieur à 100ms) ^ L* = 30 jours (Durée de vie du système supérieure à 30 jours) o (optionnel) Forçage si besoin des paramètres bas niveau du système : Rsens = 10% (proportion du temps où le module d'observation est actif, ici de 10%). ^ Rcomm = 10% (proportion du temps où le module de transmission radio est actif, ici de 10%). 25 - Stratégie o CPO : le type de CP à optimiser. Par exemple, CPO = {L, D}. o (optionnel) CPOOb; : la valeur "objectif' du CP à optimiser Sorties Le procédé produit en sortie : 20 - POSN : le positionnement de l'ensemble des noeuds requis - PFopt: le point de fonctionnement optimal au vu des CPC* et CPOob; (si ce paramètre est défini), c'est-à-dire les valeurs de CP qui satisfont CPC* et CPOobb (si ce paramètre est défini), avec la configuration bas-niveau du RCSD correspondant à ces valeurs. CONF: le paramétrage du système (par exemple Rsens, (3oom) correspondant au point de fonctionnement PFopt N,eQ : le nombre de noeuds requis. Selon le mode dans lequel le processus fonctionne, il se peut que ce nombre de noeuds diffère du nombre de noeuds alloués initialement en entrée (dans le MODE2, le processus peut déterminer qu'un nombre supérieur, ou inférieur, au Nsupp initial est requis pour satisfaire la valeur objectif sur CPO) - MS : le motif de sortie o ECHECCONTRAINTES-IRREALISABLES : il n'existe aucune manière de configurer les systèmes tel qu'un point de fonctionnement satisfasse les valeurs « seuil » CPC* o ECHEC_CPO-OBJECTIF-INATTEIGNABLE : il n'est pas possible, dans la limite du nombre de noeuds disponibles, de trouver un point de fonctionnement tel que l'objectif sur CPO soit atteint o SUCCES_PAS-DE-CPO-OBJECTIF-DEFINI : pour le nombre de noeuds utilisés, Nsupp initial, au moins un point de fonctionnement existe qui satisfait les contraintes. Le procédé indique alors le meilleur des points de fonctionnement au vu du CPO (peu importe la valeur optimale du CPO). o SUCCES CPO-OBJECTIF-ATTEINT-MIN-NOEUDS : le nombre de noeuds requis Nreq (éventuellement différent du Nsupp initial) est minimum pour que le meilleur point de fonctionnement atteignable satisfasse à la fois les contraintes et la valeur objectif sur CPO. Pour un nombre de noeuds donné, le processus PROCz détermine dans une • La position géographique optimale de l'ensemble des noeuds • Le point de fonctionnement optimal au vu de CPO et des valeurs « seuil » sur les CPC (i.e., CPC*), ainsi que le paramétrage du système correspondant. zone: Dans le MODE1, le processus PROCz présente les résultats ci-dessus à l'opérateur à la fin d'une itération du procédé PROC_GLOBALZ. Dans le MODE2, le processus PROCz itère sur le nombre de noeuds utilisés jusqu'à déterminer le nombre minimum de noeuds requis pour atteindre une valeur « objectif » sur les CPO. Pour ce nombre de noeuds, le processus PROCz présente les résultats à l'opérateur à la fin d'une itération du procédé PROC_GLOBALz. Le procédé fonctionne par étapes comme suit: RETOUR = CONTINUER ; CPO_OK = NULL Tant que RETOUR = CONTINUER A l'étape 50, on détermine la position de l'ensemble des noeuds, notée POSN POSN est l'ensemble des positions des noeuds qui maximisent la probabilité de non-détection dans la situation hypothétique où le module capteur de chaque noeud est constamment actif (i.e., Rsens=1). POSN = FPOS(POSNO, Nsupp, d) où POSN est la position géographique de l'ensemble des noeuds déployés dans la zone. Cet ensemble inclue les No noeuds dont la position est fixée par l'opérateur et les Nsupp noeuds supplémentaires à placer dans la zone. Garder en mémoire POSN. et où FPos est la technique d'optimisation décrite ci-dessous. La fonction d'optimisation Fpos est mise en oeuvre pour déterminer le positionnement optimal d'un certain nombre de capteurs à l'intérieur d'une zone. Pour suggérer un positionnement des noeuds dans une zone de couverture, les techniques d'algorithme génétique de tri non-dominé connues en soi sont mises en oeuvre. FPos détermine alors l'ensemble des positions des noeuds tel que la valeur de Pmd est minimale dans le cas où les modules capteur des noeuds sont constamment actifs. II est possible de fixer en entrée la position d'un certain nombre de noeuds. Entrées de FPos - (optionnel) le positionnement prédéterminée d'un sous-ensemble de noeuds POSNo - le nombre de noeuds dont la position n'est pas imposée par l'opérateur - d : la dimension de la zone Sorties de Fpos û POSNO : la position de l'ensemble des noeuds Sachant POSN, on détermine à l'étape 52 l'espace des solutions noté Eopo.,opo. Cet espace donne l'ensemble des réalisations particulières de CPO qui sont obtenues pour tout CPC en-deça des valeurs "seuil" CPC*. Cet ensemble est visualisable sous la forme d'un graphique G multi-dimensionnel tel qu'illustré sur la figure 6. Ecpc•,cao = { CPC(°), CPO(0) tel que CPO(0) = FoPT(CPC(°), POSN) pour tout CPC(°) qui satisfait CPC*} où FOPT désigne une technique d'optimisation simple ou multi-objectif décrites ci-dessous. En utilisant les modèles analytiques décrits précédemment, deux méthodes d'optimisation peuvent être utilisées selon que l'on cherche à déterminer la valeur optimale d'un ou plusieurs critères de performance sous réserve de certaines contraintes. On appelle FOPT la méthode d'optimisation mise en oeuvre. • Lorsqu'un seul critère de performance doit être optimisé, FOPT désigne une technique d'optimisation simple-objectif, telle que l'optimisation par descente de gradient. Celle-ci peut être mise en oeuvre si l'ensemble des équations identifiées pour modéliser le système constitue un ensemble convexe. • Lorsque deux ou plusieurs critères de performance doivent être optimisés, FOPT désigne une technique d'optimisation multi-objectif, qui permet d'optimiser simultanément des fonctions d'objectifs contradictoires, sous réserve de certaines contraintes éventuelles. Nous pouvons par exemple utiliser une méthode de classement, basée sur la Pareto optimalité, mettant en jeu des techniques récentes, à savoir l'algorithme génétique de tri non-dominé (en anglais, Non-dominated Sorting Genetic Algorithm-II) Entrées de FOPT - le positionnement de l'ensemble des noeuds POSN - CPC(°): l'ensemble des valeurs des CP Contraintes - CPO: l'ensemble des CP dont la valeur doit être optimisée - d: la dimension de la zone Sorties de FoPT - CPOopt(0): l'ensemble formé des valeurs optimales pour chaque CP inclus dans CPO Par exemple, si l'opérateur choisit d'avoir: CPC = {D, Pmd} avec CPC* _ {D* = 100ms, Pmd* = 10%) CPO = {L} Alors ED* = 1OOms,Pmd*=1°%, L _ {Lopt(» , (Pmd)max(»,Dmax(0) tel que : Lopt(» = FOPT((Pmd)max(°),Dmax(m) et (Pmd)max(°) Toujours dans cet exemple, le graphique G est alors tel que dans la figure 6. G comporte notamment des points indiquant que : la durée de vie maximale est de 18 jours avec (Pmd)max = 2% et Dmax = 80ms. 60ms. Une exploration des résultats est effectuée lors des phases 60. la durée de vie maximale est de 13 jours avec (Pmd)max = 10% et Dmax = a) Si : ECPC*,CPO est vide lors de l'étape 62 Par exemple, il n'existe aucun PF avec 5 noeuds dans la zone tel que Pmd 30 relâcher les valeurs "seuil" imposées aux CPC. RETOUR = ECHEC_CONTRAINTES-IRREALISABLES (étape 66) b) Sinon : Ecpc*,cpo est non-vide (CPOperf existe) (test effectué en 62) On détermine à l'étape 68 la valeur la plus performante du CPOperf sur l'espace des solutions Ecpc*,cpo (s'il est non vide) On note.CPOperf la valeur la plus performante du CPO sur l'espace des solutions Ecpc•,cpo. Par exemple, Lperf (Pmd*,D*) = max Lopt(o) sur l'ensemble ED*,Pmd*, L. Dans l'exemple, Lperf (Pmd* = 10%,D*=100ms) = 25j au vu de Eo* = 1ooms,pmd*=fo%, L On note PFopf le point de fonctionnement optimal tel que CPO= CPOperf et CONF le paramétrage du système permettant d'atteindre PFopf. Déterminer et garder en mémoire PFopf et CONF. Un test est effectué à l'étape 70 pour définir le mode retour. i) Si aucun objectif n'a été défini sur les CPO (MODE1), c'est-à-dire que l'opérateur cherche à opérer le RCSD dans un PF satisfaisant les contraintes (CPC*) et se limite à connaître la valeur la plus performante sur un CP à optimiser (CPO). Afficher, à l'étape 72, le point de fonctionnement optimal et la configuration obtenue à l'étape 54, ainsi que la topologie obtenue à l'étape 50 et le nombre de nœuds utilisés (NsUpp + No) RETOUR = SUCCES_PAS-DE-CPO-OBJECTIF-DEFINI (étape 74) Recommencer ii) Sinon : un objectif CPOpbb a été défini sur CPO (MODE2) Un test est effectué à l'étape 76 pour définir l'atteinte de l'objectif CPO_OK. (1) Si CPOperf ne satisfait pas CPOobJ (Si la meilleure performance atteignable sur le CP à optimiser est en deçà de l'objectif) Si CPO_OK = VRAI (étape 78) Afficher à l'étape 80 le point de fonctionnement optimal et la configuration obtenue à l'étape 54 à l'itération précédente, ainsi que la topologie obtenue à l'étape 50 et le nombre de noeuds utilisés (NsUpp + No) à l'itération précédente. RETOUR = SUCCES_CPO-OBJECTIF-ATTEINT-MIN-NOEUDS (étape 82) Recommencer Sinon (c'est-à-dire que CPO_OK = FAUX ou CPO_OK = NULL) CPO_OK = FAUX (étape 83) Un test est effectué à l'étape 84 pour définir si Nsä pp est égal au maximum 5 disponible éventuellement défini à l'étape 84. Si Nsä pp est égal au maximum disponible éventuellement défini Afficher à l'étape 86 le point de fonctionnement optimal et la configuration obtenue à l'étape 54, ainsi que la topologie obtenue à l'étape 50 et le nombre de noeuds utilisés (Nsupp + No) 10 RETOUR = ECHEC_CPO-OBJECTIF-INATTEIGNABLE (étape 88) Sinon Incrémenter Nsupp à l'étape 90 Recommencer. 15 (2) Sinon : CPOperf satisfait CPOobj à l'étape 76 (c'est-à-dire la meilleure performance atteignable sur le CP à optimiser est au-delà de l'objectif) Un test sur la valeur de CPO_OK est effectué à l'étape 92 Si CPO_OK = FAUX alors : Afficher, à l'étape 80, le point de fonctionnement optimal et la configuration 20 obtenue à l'étape 54, ainsi que la topologie obtenue à l'étape 50 et le nombre de noeuds utilisés (Nsupp + No) RETOUR = SUCCES_CPO-OBJECTIF-ATTEINT-MIN-NCEUDS (étape 82) Recommencer Sinon (c'est-à-dire que CPO_OK = VRAI ou CPO_OK = NULL) 25 CPO_OK = VRAI (étape 93) Un test sur le nombre de noeuds utilisés est comparé à l'unité à l'étape 94. Si le nombre de noeuds utilisés est strictement supérieur à 1 Recommencer en utilisant moins de noeuds (i.e., décrémentant Nsupp) à l'étape 96 Sinon Afficher à l'étape 80 le point de fonctionnement optimal et la configuration obtenues en 3), ainsi que la topologie obtenue en 1) et le nombre de noeuds utilisés (Nsupp + No) RETOUR = SUCCES_CPO-OBJECTIF-ATTEINT-MIN-NOEUDS (étape 82) Recommencer La figure 7 montre les sorties pouvant être produites par le procédé PROCz sur deux zones, chacune d'entre elle utilisant un mode d'appel du procédé. Dans la zone Zl, on utilise le MODE1 car l'opérateur souhaite connaître la configuration qui satisfait prioritairement des contraintes sur Pmd et D, et donne, de manière secondaire, la meilleure durée de vie. Pour le nombre de noeuds donné, le processus détermine le meilleur point de fonctionnement s'il existe. Dans la zone Z2, on utilise le MODE2 car l'opérateur souhaite connaître la configuration qui satisfait des contraintes sur Pmd et D, et telle que la meilleure durée de vie est au-delà d'un objectif. Au bout de quelques itérations, le processus détermine le nombre minimal de noeuds requis pour que le meilleur point de fonctionnement satisfasse, si possible, aussi bien les contraintes que l'objectif. Ce nombre minimal de noeuds est éventuellement supérieur ou inférieur au nombre de noeuds initialement alloués à la zone. Une variante notée PROC_MAX-SURFACEZ du procédé PROCz, illustré sur la figure 5, consiste à déterminer la surface maximale d'une zone telle qu'il existe un point de fonctionnement satisfaisant les critères de performance. Par exemple, en disposant de 15 noeuds, l'opérateur souhaite savoir quelle est la couverture maximale de la zone autour d'une location donnée, qui lui garantit que la probabilité de non-détection est inférieure à 10%. On note le procédé PROC_MAX-SURFACEz(CPC*, Nsupp) ou, pour simplifier, PROC_MAX-SURFACEZ. Le procédé fonctionne comme suit. On détaille ci-après les entrées et sorties correspondantes. PROC_MAX-SURFACEZ(CPC , C, N) = (POSN PFapr, CONF, MS) Entrées 2330 Les entrées suivantes sont initialisées par l'opérateur au premier appel du procédé. Les entrées se répartissent comme suit : - Constantes sur le dimensionnement du système : o dm;,,: la dimension minimale de la zone (par exemple largeur de la zone carrée à surveiller de lm minimum) o C: la position du centre de la zone o Ei : L'énergie initiale contenue dans les batteries Nombre de noeuds : o N: le nombre de capteurs à déployer dont la position n'est pas imposée par l'opérateur Contraintes opérationnelles o CPC*: la valeur "seuil" des CP Contraintes. Par exemple : ^ Pmd* = 10% (Probabilité de non-détection inférieure à 10%) 15 (optionnel) Forçage si besoin des paramètres bas niveau du système. - Stratégie o CPO : le type de CP à optimiser. Par exemple, CPO = {L, D}. 20 Sorties Le procédé produit en sortie : - dmax : la taille maximale de la zone - PF,pt: le point de fonctionnement optimal au vu des CPC*, c'est-à-dire les valeurs de CP qui satisfont CPC* avec la configuration bas-niveau du RCSD 25 correspondant à ces valeurs. CONF: le paramétrage du système (par exemple Rsens, Pcom) correspondant au point de fonctionnement PF,pt - POSN: le positionnement de l'ensemble des noeuds dans la zone de taille maximale obtenue. 10 - MS : le motif de sortie o ECHECIMPOSSIBLE-POUR-TAILLE-MINIMALE : il n'existe aucune manière de configurer le système tel qu'un point de fonctionnement satisfasse les valeurs « seuil » CPC* pour la taille minimale de la zone. o SUCCESTAILLE-MAXIMALE-ATTEINTE : Déroulement Pour un nombre de noeuds donné, le processus PROC_MAX-SURFACE détermine dans une zone: • La position géographique optimale de l'ensemble des noeuds ^ Le point de fonctionnement optimal au vu de CPO et des valeurs « seuil » sur les CPC (i.e., CPC*), ainsi que le paramétrage du système correspondant Tant qu'il existe un point de fonctionnement optimal, le processus PROC_MAXSURFACE itère sur la taille de la zone jusqu'à déterminer la taille maximale pour qu'un point de fonctionnement, optimal, existe. Pour cette taille maximale, le processus présente les résultats à l'opérateur à la fin d'une itération du procédé PROC_GLOBALZ. Le procédé fonctionne par étapes comme suit : RETOUR = CONTINUER ; d = dmin dstep, le pas d'incrémentation de d Tant que RETOUR = CONTINUER 1) Déterminer la position de l'ensemble des noeuds, notée POSN POSN est l'ensemble des positions des noeuds qui minimise la probabilité de non- détection dans la situation hypothétique où le module capteur de chaque noeud est constamment actif (i.e., 6sens=1). POSN = Fpos(N, d) où Fpo est la technique d'optimisation décrite dans la section 6.4 "Techniques d'optimisation". 25 Garder en mémoire POSN 2) Sachant POSN, déterminer l'espace des solutions noté Ecpc*cpo• Cet espace donne l'ensemble des réalisations particulières de CPO qui sont obtenues pour tout CPC en-deçà des valeurs "seuil" CPC*. Cet ensemble est visualisable sous la forme d'un graphique G multi-dimensionnel. Ecpc•,cpo = { CPC(°), CPO(0) tel que CPO(0) = FoPT(CPC(0), POSN) pour tout CPC(°) qui satisfait CPC*} où FoPT désigne une technique d'optimisation simple ou multi-objectif telle que décrite précédemment. 3) Exploration des résultats a) Si : Ecpc*,cpo est vide. Pour une zone centrée sur C et de taille d, il est impossible de configurer et opérer le RCSD dans un point de fonctionnement tel que les contraintes sont satisfaites. (Par exemple, pour une zone de largeur 1000m où l'on déploie 5 noeuds, il est impossible de trouver une configuration du RCSD telle que que Pmd RETOUR = SUCCES TAILLE-MAXIMALE-ATTEINTE Recommencer. b) Sinon : Ecpc.,cpo est non-vide d = dmin + deep (Incrémenter la taille de la zone) Mémoriser le graphique G représentant Ecpc•,cpo et la topologie déterminée en 1). Recommencer Le processus d'optimisation est réalisé sur une description du système sous la forme de « modèle du système ». Ce modèle est composé des fonctions ou relations entre les paramètres décrivant le fonctionnement du système. II permet de dériver les indicateurs de performances sur lesquels l'opérateur place des objectifs (par exemple maximisation du temps de vie du système L). Le procédé peut comporter par exemple les fonctions suivantes : • Pmd = f (PosN, Rsens) : Probabilité de non-détection en fonction de la position des noeuds PosN et de la proportion du temps où le module d'observation est actif, [3sens• PosN a une influence sur la couverture capteur et Rsens a une influence sur la capacité d'un capteur à détecter la cible lorsqu'elle est en portée. • D = h(PosN, Rcomm) Délai de transmission des alertes en fonction de la position des noeuds PosN et de la proportion du temps où le module de transmission radio est actif Rcomm. PosN a une influence sur le nombre de bonds radio et Rcomm sur le délai à chaque bond dans le cas de l'utilisation de X-MAC par exemple. • L = g(Ncomm, Rsens, Ntarget) : Durée de vie du système en fonction du niveau d'effort consacré pour la partie capteurs (par exemple (3sens) et pour la partie réseau (par 25 exemple Rcomm), et en fonction du nombre moyen de cibles détectées par jour Ntarget. Dans la suite de cette section, on présente 3 fonctions caractérisant le fonctionnement du système. Ces fonctions caractérisent la probabilité de non-détection Pmd, la durée de vie du système L et le délai de transmission des alertes D. L'extension de la formulation de la probabilité de non-détection Pmd proposée par [Lazos09] dans le 30 cadre de l'utilisation de cycles d'endormissement constitue une contribution de ce document. Le reste des formulations est repris de l'état de l'art. II est à noter que les techniques d'optimisation utilisées pour déterminer les points de fonctionnement du système sont génériques de sorte que d'autres modèles peuvent être intégrés dans le système. Cela peut permettre de raffiner la modélisation du système et/ou d'étendre les indicateurs de performances caractérisant le fonctionnement du système. Hypothèses Afin de pouvoir calculer Pmd (la probabilité de non-détection), nous faisons les hypothèses suivantes. La zone d'intérêt à surveiller est un carré de largeur d5 (dimension: [m]). N noeuds capteurs ayant des couvertures circulaires de rayon rs illustré sur la figure 8 sont alors déployés pour détecter la présence de cibles dans la zone. Le modèle de comportement de cibles considéré suppose un mouvement rectiligne uniforme où la trajectoire est caractérisée par un angle d'arrivée 9. La vitesse constante est v (dimension: [m/s]). Le point d'entrée de ces cibles étant inconnu a priori, il est choisi aléatoirement sur le contour de la zone. Les noeuds capteurs comportent au moins deux sous-modules : (i) le module capteurs (par exemple transducteur) et (ii) le module de communication sans-fils. Afin de réduire la consommation de ces deux modules, des cycles d'endormissement (« dutycycles » en anglais) sont utilisés. Ces cycles sont constitués alternativement d'une phase où le module est actif et d'une phase où le module est inactif. Ils sont caractérisés par deux paramètres : la période du cycle TSens (dimension: [s]) et la proportion du temps Rsens dans [0,1] où le module est actif tel qu'illustré sur la figure 9. Dans le reste du document, les paramètres sont (Nsens, Tsens) et (Rcomm, Tcomm) pour respectivement le module capteur et le module de communication. La puissance consommée lorsque le module capteur est actif est de Csens• Dans le reste du calcul, nous considérons également que tous les noeuds capteurs ont les mêmes valeurs pour les paramètres rs, 8sens, et Tsens. Modélisation de la probabilité de non-détection Pmd Considérons N noeuds capteurs placés d'une certaine façon et considérons 8.sens = 1, la probabilité de détection correspond à la probabilité que la trajectoire de la cible croise au moins un capteur Pd s'exprime de la manière suivante : =1ùPmd=P(e nU.t2U..,U . (1) où 1 est la ligne correspondant à la trajectoire de la cible, A; l'aire de la portée capteurs du noeud i. L'équation (1) peut être réécrite, en utilisant le principe d'inclusion-exclusion de Feller, comme la somme des probabilités conjointes qu'une ligne coupe les diverses couvertures capteurs. On a alors : Pt = 0)_) P(enÀànAi 0)+...+(_t)ttiP(ff1/AtnA2... Agi; 0) (2) D'après [Lazos09], le cas du déploiement déterministe des noeuds capteurs n'est pas calculable facilement de manière analytique. En revanche, des bornes supérieure et inférieure sont calculables. D'après les inégalités de Bonferroni, les bornes inférieure et supérieure suivantes peuvent être calculées : Pd Pd (3) où Pd, et Pd2 s'expriment comme suit : P(PnA;nA 0) _ 'rtn2 (,J) P = N (5) Les équations (4) et (5) ne prennent pas en compte Rsens• Dans la suite de ce 15 calcul, nous étendons Pdl et Pd2 afin de prendre en compte les cycles d'endormissement du module capteur qui s'expriment alors : P{Asti Pte P { Activity.,i} (7) (6) où les nouveaux facteurs introduits sont : o P{Activity,} : la probabilité que le module capteur du noeud i soit ou 20 devienne actif pendant que la cible traverse sa zone de couverture. o P{Activity,;j} : la probabilité que les modules capteur des noeud i et j soient ou deviennent actifs pendant que la cible traverse leurs zones de couverture. Pour estimer les bornes inférieure et supérieure de l'équation (3), on calcule Pdl puis Pd2. Formulation de Pd, Dans le cas où la zone de couverture du module capteur est un disque de rayon rs, nous avons m,(i)= 2 u rs / 4 ds et le facteur P{Activity,} peut être calculé selon les résultats présentés par [Meda09] (équation 10). Formulation de Pd2 D'après l'équation (7), Pd2 s'exprime comme suit : ) P{Acthr i- Calcul de m2(i,i) Le terme "k (r,.i) = P(t' n n A.i ≠ 0) exprime la probabilité que la trajectoire de la cible coupe à la fois les portées des noeuds i et j. En tenant compte du recouvrement éventuel des couvertures des noeuds i et j, la formulation générale de m2(i,j) est comme suit: Ain 0 n A = 0($) où les termes correspondants sont, et tel qu'illustré sur la figure 8 : o L; et Li: les périmètres des zones de couverture respectives des noeuds i et j, o la distance entre les deux noeuds, o Lin : la longueur de la ligne « en huit » entourant les deux zones de couverture o Lotir : la longueur de la ligne entourant les deux zones de couverture sans se croiser o Lo : le périmètre de la zone surveillée D'après nos hypothèses, on obtient la formulation de m2(i,j) en sachant que L; = L; 2rrrs, Lo = 4 ds et d'autre part, d'après [Lazos09] (équations 37 et 38): La1.Gt «di i) = 27rïs + 2d, 27r - 2arccos 10 ii- Calcul de P{Activity;,} Par définition, P(Activity;,,) est la probabilité conjointe de deux événements compatibles, à savoir les modules capteur des noeud i et j sont ou deviennent actifs pendant que la cible traverse leurs zones de couverture. On a donc : P{Actïv ty, } = P{Act ivit;yi} • P{Acti F t, F } (9) En distinguant le cas où le noeud i est actif à l'entrée de la cible dans sa zone et le cas où il devient actif durant la traversée, nous avons comme pour le calcul de P{Activity,} pour Pdl (voir [Meda09]),: 15 P{ Acth Yi + (1 >i sorts)P{e rget, (10) où P{edecletaxrgtd., &SOT;} exprime la probabilité que le noeud i devienne actif durant la traversée de sa zone par la cible. Pour calculer cette probabilité, on calcule la densité de probabilité jointe de la durée de la traversée notée Tcross et du temps relatif d'arrivée de la cible après le début du cycle d'endormissement, noté Ta. Pour chaque noeud, cette 20 fonction s'écrit : 7a,Tcr+ . f 'cr; s 1 V puisque Ta est uniformément distribuée sur l'intervalle [0,c] où c = (1 - 13sens)Tsens. Formulation de la longueur de la corde Li ou Lj Les trajectoires prises en compte coupent à la fois les portées de i et de]. D'après les schémas des figures 11 et 12, l'angle pour les points d'entrée possibles dans le noeud i (zone orange) est de largeur [Ohtm, = 271- 01iml Sur la base de considérations géométriques, on obtient la longueur de la corde, notée 1, constituant une réalisation particulière de L;, en fonction de l'angle d'entrée e: ds tifs r ssin8 } °sils n2O t_ + , bl bt + d2 * 2r5dcoso et où d s'exprime comme suit : + d2-2 r sd selon que l'on considère le noeud i ou le noeud j. (i) + rs (j) 15 Comme l'équation (11) est assez complexe, on peut approximer 1 avec une fonction parabolique : I = a162 + a26 + a3 avec 6 in {Oiirt, 2ar - 0E4 pour le noeud i, et - Ohm:, + 0tim2j pour le noeud j. Les coefficients a,, a2 et a3 sont obtenus comme dans le tableau ci-après. ers ù (12 ùtai 7r a.3 al 71-2 + 2 v En exploitant cette approximation et en appliquant le même théorème fondamental que dans [Meda09] (équations 6 et 7), et en effectuant la substitution Y=Uv nous obtenons: 2r 16r2 -- 8rit ' si (l Y' s et 0 sinon. V 20 OÙ C = (1 - Rsens)Tsens• que: Finalement, en intégrant sur l'ensemble des réalisations de Li (resp. Lj), on montre if 2r/t, }ùttcrgv 12r• ct' Il otherwi e. 3 (12) Ainsi, P{Activity,) ù P{Activity/), et on obtient finalement Pd2 en combinant les équations (8), (9), (10) et (12). Délai de transmission des alertes Nous proposons un modèle analytique pour le délai de transmission d'alerte, c'est-à-dire la durée entre la détection de la présence d'un intrus par un noeud capteur et la notification de cette détection au noeud passerelle. Dans la suite, nous calculons le délai à un bond radio, noté DI hop puis le délai sur un chemin multi-sauts. Pour modéliser le délai, nous considérons X-MAC, un protocole couche MAC, basse puissance et asynchrone, utilisé dans les réseaux de capteurs mettant en oeuvre des cycles d'activation pour la radio. X-MAC utilise un mécanisme d'écoute du canal à faible puissance (en anglais, Low Power Listening ou LPL) pour permettre des communications entre un émetteur et un récepteur qui ne synchronisent pas leurs programmes de réveil et d'endormissement. En effet, lorsqu'un noeud souhaite envoyer des données, il émet un préambule pendant une durée au moins aussi longue que l'intervalle de sommeil du noeud récepteur. Ceci garantit que le récepteur va se réveiller, détecter le préambule, et rester éveillé pour recevoir les données du noeud émetteur. X- MAC utilise un préambule haché avec lequel l'expéditeur alterne rapidement entre l'envoi de l'adresse de destination du paquet de donnée et un court temps d'attente. Ceci permet au destinataire d'avorter le processus afin de recevoir les données. Le délai de transmission moyen, à un saut, peut être exprimé comme suit : où Rcomm est la proportion du temps (normalisée) où le module de transmission radio est actif sur le cycle de durée Tcomm, et Sp, Sa,, Sd, les durées respectives de l'envoi du préambule élémentaire, de la réception de d'acquittement du préambule, et de l'envoi du paquet de données relatif à l'intrusion détectée. Si l'on considère l'état du noeud destinataire, à savoir l'état actif ou inactif de son module de communication, la probabilité qu'un noeud commence sa transmission lorsque le noeud destinataire est actif est Padma, et le délai associé est Sp + Sa, + Sd. À l'inverse, la probabilité qu'un noeud soit éteint est 1 - 3comm• Nous évaluons Dt'=open faisant la moyenne entre le cas le moins favorable et celui le plus favorable, en termes de délai. Le cas le plus favorable est celui où le noeud commence à émettre son préambule exactement au moment où le noeud destinataire sort de son cycle d'endormissement. Dans ce cas là, le paquet est transmis après la durée Sp + Sa, + Sd. Dans le cas le moins favorable, le noeud émetteur attend pendant toute la durée d'endormissement du noeud destinataire. De plus, comme le noeud destinataire doit recevoir un préambule élémentaire entier avant d'acquitter l'envoi du paquet, le délai prend en compte que deux transmissions du préambule élémentaire peuvent être nécessaires avant le début de l'échange des données. Dans ce cas, le délai de transmission à un saut est (1 - (3comm) Tcomm + (Sp + Sa,) + Sd. On obtient l'équation ci-dessus (1) en pondérant dans chaque équation le terme lié à l'attente avant l'envoi du préambule par la probabilité que le destinataire soit dans l'état actif ou inactif, et (2) en moyennant les cas le moins et le plus favorable. Modèle de consommation énergétique Etant donné que les noeuds opèrent sur batterie, la manière dont ils consomment de l'énergie influe directement sur la durée de vie du système de surveillance. Afin d'en tenir compte, nous proposons ici un modèle d'énergie simple pour la consommation d'énergie à l'échelle du réseau de capteurs. La consommation énergétique des noeuds peut être donnée par la somme des énergies consommées par ses composants matériel. Par souci de simplicité, nous n'intégrons dans le modèle énergétique que les contributions du module de détection et de l'émetteur-récepteur radio. Nous définissons également la durée de vie du réseau comme le temps nécessaire à ce que l'énergie moyenne résiduelle Er passe sous une valeur seuil Eth. Pour obtenir une expression de la durée de vie du réseau, nous évaluons l'énergie consommée après un intervalle de temps donné t. Er, l'énergie résiduelle moyenne à l'instant t, peut être exprimée comme suit Er(~=NE,-M2tott où Ei est l'énergie initiale d'un noeud et Otot est la puissance requise par l'opération des modules de détection et de communication. Selon la description du protocole X-MAC, le module de communication peut être dans l'un des quatre états suivants : (i) transmission, (ii) réception, (iii) sommeil, et (iv) LPL. Les budgets de puissance respectifs sont notés OR, OT, Os et OLPL. Otot peut alors être calculée comme suit : Otot = Os + OLPL + (OR + OT)PdNrarget où OR, OT, Os et OLPL Os sont les puissances décrits précédemment ; Pd est la probabilité de détection d'une cible, et Ntarget est le nombre de fois où une cible apparaît au cours d'une période de référence. Le reste du calcul figure dans [Meda09]. On détaille ci-après la mise en oeuvre du procédé global pour l'assistance au déploiement d'un RCSD. On envisage deux types de scénarios : • Scénario « zone simple » : dans ce cas, l'espace surveillé est par exemple une zone unique, à savoir une surface carrée au centre de laquelle est situé le camp ou bivouac à protéger. • Scénario « zones multiples » : dans ce cas, l'espace surveillé est par exemple constitué de multiples zones autour ou aux environs du camp. Ces zones peuvent être de différentes formes (par exemple disques, patatoïdes). L'opérateur cherchera par exemple à surveiller un ensemble de zones mal couvertes par un système optronique ou radar. Scénario « zone simple » Dans ce cas, on imagine par exemple que l'opérateur dispose de 20 noeuds à déployer pour la surveillance d'une surface carrée de 1000 mètres de côté. Les contraintes de performance que le système de surveillance doit remplir sont d'une part un délai D inférieur à 100ms, et d'autre part une probabilité de détection manquée, Pmd, inférieure à 10%. Enfin, la présence de points de passage importants impose à l'opérateur de placer un capteur à chacun des coins de la zone. En initialisant le procédé décrit dans le document, avec 13 noeuds mis à disposition dans un premier temps (No = 4, NsUpp = 9), le procédé va ainsi suggérer à l'opérateur de positionner les noeuds comme indiqué sur la Figure 13. Au cours de son fonctionnement, le processus PROC va décrire l'espace de solutions respectant les valeurs « seuil » des contraintes. Au vu de l'espace de solutions, la meilleure des valeurs optimales de durée de vie est de 25 jours environ, avec comme performances Pmd = 10% et D = 100ms. Le procédé informe l'opérateur de ce point de fonctionnement optimal, ainsi que de la configuration système associée. Avec le MODE2 et un objectif fixé par exemple à 20 jours, le processus aurait réitéré avec un nombre inférieur de noeuds à déployer. Au contraire, avec un objectif par exemple à 30 jours, le processus aurait réitéré avec un nombre supérieur de noeuds à déployer. Scénario « multi-zones » Ce scénario envisage le déploiement d'un RCSD sur un ensemble de zones, sachant qu'il existe des contraintes différentes pour chacune des zones. La motivation pour un tel déploiement peut être : 25 • Etendre la couverture de la zone de surveillance autour du camp avec la mise en place d'un second glacis caractérisé par des contraintes moins strictes en termes de fiabilité de détection et délai • Assurer la surveillance de zones sensibles éloignées du camp (par exemple zone 1 autour d'un col, zone 2 autour d'un point d'eau, zone 3 autour d'un centre 30 de ravitaillement en carburant). • Combler les diverses zones non couvertes par un système d'observation longue portée (par exemple caméra, radar). Prenons l'exemple de l'extension de la zone de surveillance autour du camp.20 • 15 noeuds à placer au maximum. • Dans la zone 1 entourant le camp dans un rayon de 100m : o Pmd1 • Dans la zone 1, il existe une configuration optimale du système, satisfaisant les contraintes et permettant d'avoir une durée de vie du système égale à 50,5 jours. Il faut déposer au minimum 8 noeuds pour atteindre cette durée de vie. Le procédé présente le point de fonctionnement optimal et la configuration correspondante. • Dans la zone 2, en utilisant 5 noeuds, la taille maximale de la zone pour que les contraintes soient respectées est de 817m. Le procédé présente le point de fonctionnement optimal et la configuration correspondante. Au vu de ces résultats, soit l'opérateur est satisfait du déploiement et de la configuration suggérés, soit il choisit par exemple de réitérer le procédé en réallouant les 2 noeuds encore à sa disposition à la zone 2 afin d'étendre au maximum la couverture de celle-ci. Après une 2ème itération du procédé global, il obtient des résultats différents dans la 2ème zone. Par exemple, la taille maximale est alors de 1289m. Le procédé présente le point de fonctionnement optimal et la configuration correspondante. La figure 1 présente un exemple de répartition et positionnement des noeuds fourni à la fin du procédé global sur les 2 zones pour les entrées définies précédemment. Les avantages de ce procédé sont : • Sa capacité à intégrer et calculer les positions exactes des capteurs • La possibilité pour l'opérationnel de fonctionner de manière itérative • Sa capacité à relier toutes les composantes du système entre elles • L'assistance à l'opérationnel gérant le déploiement pour prendre les meilleures décisions possibles quant au paramétrage du système • Son caractère extensible dans la mesure où les modèles peuvent être changés ou étendus. REVENDICATIONS1.- Procédé de configuration d'un réseau de capteurs sans fils déposés, constitué de noeuds interconnectés comportant chacun un capteur, une source propre 5 d'alimentation en énergie, des moyens de calcul, des moyens de communication, des moyens de sauvegarde d'une configuration de fonctionnement et des moyens de gestion de son fonctionnement en fonction de cette configuration mémorisée, caractérisé en ce qu'il comporte les étapes suivantes : 1 Définir (étape 12) des critères de performance constituant des contraintes (CPC), avec des valeurs seuil associées (CPC*), et au moins un critère de performance à optimiser (CPO), pour au moins une zone (Z;) à équiper de noeuds, chaque critère de performance étant défini par un modèle 2 Définir (étape 10) pour la ou chaque zone (Z;) : a. Des caractéristiques (d) de la zone b. Des caractéristiques (Ei) des capteurs dans la zone 3 Allouer (étape 10) à la ou chaque zone (Z1) à équiper, un nombre de noeuds 4 Appliquer (étape 22) un processus d'optimisation par zone sur la ou chaque zone (Z;), le processus d'optimisation par zone mettant en oeuvre 20 les étapes suivantes : a. Déterminer (étape 50) la position des noeuds dans la zone si il existe pour satisfaire un critère d'optimisation prédéterminé ; b. Déterminer (étapes 72, 80, 86) un point de fonctionnement (PF) si il existe, caractérisant le comportement du réseau de capteurs dans la zone, et c. Déterminer (étapes 72, 80, 86) la configuration (Conf) du réseau de capteurs dans la zone si elle existe, définissant les paramètres de configuration du réseau de capteurs, et d. Déterminer (étapes 66, 88) le besoin éventuel d'utiliser davantage de noeuds ou réviser les critères de performance (CPC* et CPO) définis à l'étape 1, Augmenter (16) le nombre de noeuds ou modifier (14) les critères de performance (CPC* et CPO) définis dans la ou chaque zone où les critères de performance ne sont pas satisfaits et reproduire dans ces zones le processus d'optimisation par zone avec le nouveau nombre de noeuds ou les nouveaux critères de performance (CPC* et CPO), et 15 25 30 356 Appliquer la configuration déterminée à chaque noeud dans la ou chaque zone. 2.- Procédé selon la revendication 1, caractérisé en ce que l'étape de définition des critères de performance à optimiser (CPO) comprend (étape 12) la définition d'une valeur seuil (CPOobJ) à atteindre pour au moins un critère de performance à optimiser (CPO) et en ce que le processus d'optimisation (étape 22) par zone comporte une étape d'incrémentions (étape 90) du nombre de noeuds pour équiper la zone, si au moins un critère de performance à optimiser (CPO) n'est pas satisfait afin de déterminer le nombre minimal de noeuds requis pour satisfaire les critères de performance (CPC* et CPOob;) et une reproduction des étapes 4a à 4c avec le nouveau nombre de noeuds incrémenté. 3.- Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que l'étape de définition des critères de performance à optimiser (CPO) comprend (étape 12) la définition d'une valeur seuil (CPOobj) à atteindre pour au moins un critère de performance à optimiser (CPO) et en ce que le processus d'optimisation (étape 22) par zone comporte une étape de décrémentation (étape 96) du nombre de noeuds pour équiper la zone, si tous les critères de performance à optimiser (CPO) sont satisfaits afin de déterminer le nombre minimal de noeuds requis pour satisfaire les critères de performance (CPC* et CPOobj) et une reproduction des étapes 4a à 4c avec le nouveau nombre de noeuds décrémenté. 4.- Procédé selon la revendication 1, caractérisé en ce que l'étape de définition des caractéristiques (d) de la zone comprend la définition d'une valeur minimale pour la dimension de la zone (dmin), et en ce que le processus d'optimisation (étape 22) par zone (PROC_MAX-SURFACE) comporte des étapes successives d'incrémentation de la dimension de la zone et de reproduction des étapes 4a à 4c avec la nouvelle dimension de la zone, jusqu'à ce qu'il n'existe aucun point de fonctionnement satisfaisant les critères de performances contraintes constituant des contraintes (CPC*). 5.- Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que le critère d'optimisation prédéterminé, pour la détermination de la position des noeuds, est de minimiser une probabilité de non détection (Pmd) par le réseau sous l'hypothèse d'une activation permanente (f3sens = 100%) du capteur de chaque noeud. 6.- Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que l'étape d'allocation des noeuds comprend, dans au une zone (Z;), la fixation de positions (POSNO) imposées pour au moins un noeud dans la zone (Z;) et l'étape (50) de détermination de la position des noeuds prend en compte les positions imposées pour au moins ledit noeud.T- Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce qu'il comporte, une modélisation analytique de la probabilité de non-détection d'une cible mettant en oeuvre les positions connues des capteurs (Calcul du Pmd). 8.- Dispositif comportant des moyens de mise en oeuvre des étapes du procédé selon l'une quelconque des revendications précédentes. 9.- Programme d'ordinateur comportant des instructions propres mettant en oeuvre le procédé selon l'une quelconque des revendications 1 à 7 lorsque mis en oeuvre sur ordinateur.