Brevet FR2902588A1 — publié le 20071221

"Procédé d'optimisation d'un masque et d'un ou plusieurs filtres d'un gestionnaire de réseau de véhicule automobile". L'invention concerne un procédé de détermination d'un masque et d'un ou plusieurs filtres d'un gestionnaire de protocole d'un calculateur de véhicule automobile relié à un réseau. Un calculateur relié à un réseau de véhicule automobile de type CAN est destiné notamment à recevoir des trames de données. Il comprend un composant, appelé gestionnaire de protocole ou contrôleur de protocole, incluant une ou plusieurs mémoires tampon aptes à recevoir des trames de données. A la différence des autres réseaux, chaque trame circulant dans un réseau de type CAN ne comprend pas de données représentatives de son émetteur ni de son destinataire. Chaque trame circulant dans le réseau CAN contient cependant un identificateur, une même trame pouvant ainsi être reçue par tous les calculateurs reliés au réseau. Lorsqu'un calculateur a reçu une trame, il détermine s'il doit ou non la consommer, à partir de la valeur de l'identificateur de cette trame. Un filtrage est prévu pour réduire la quantité de trames non consommées que reçoit le calculateur. A chaque mémoire tampon, est associé un masque et au moins un filtre, pour sélectionner les identifiants des trames à accepter dans cette mémoire tampon. Le masque spécifie les indicateurs binaires de l'identificateur qui sont significatifs, et le filtre indique les valeurs devant être prises par les indicateurs binaires significatifs pour que la trame contenant cet identificateur soit acceptée dans la mémoire tampon. Les indicateurs binaires du masque valant "un" correspondent aux indicateurs binaires significatifs de l'identificateur, le masque étant par exemple un mot binaire de même longueur que le mot binaire constitué par l'identificateur. L'opérateur ET logique est appliqué entre l'identificateur et le masque, et le résultat est comparé à la valeur du filtre, la trame étant acceptée en cas d'égalité. Avec un masque valant 111 1111 0000b auquel est associé un filtre valant 011 1100 XXXXb, et un identificateur valant 011 1100 1010b ou bien 011 1100 llllb, le résultat du masquage est 011 1100 0000b. Le filtre vaut 011 1100 XXXXb de sorte que la trame est acceptée, c'est-à-dire inscrite en mémoire tampon. Avec un identificateur valant 011 1101 1010b, le résultat du masquage est 011 1101 0000b, ce qui ne correspond pas au filtre 011 1100 XXXXb de sorte que la trame n'est pas acceptée. Si le masque comprend n indicateurs binaires valant zéro, alors le filtre laisse passer 2 puissance n 20 identifiants différents. Un filtre est spécifique à un identifiant unique, si la valeur du masque auquel il est associé est représentative du fait que tous les indicateurs binaires de l'identificateur sont significatifs, ce qui est le cas 25 si ce masque ne comprend que des "un", et il est dit non spécifique dans le cas contraire. Si le masque vaut 111 1111 llllb, et si le filtre vaut 010 0000 1000b, alors seul l'identificateur 010 0000 1000b est accepté. Si le masque vaut 111 1111 1100b, et 30 si le filtre vaut 010 0000 10XXb, alors quatre trames sont acceptées, à savoir les trames 010 0000 1001b, 010 0000 1010b, 010 0000 1011b. Un gestionnaire de protocole donné comprend un certain nombre de masques, de filtres, et de mémoires 35 tampon, un masque étant dit global lorsqu'il est associé à plusieurs filtres. Un exemple d'architecture est illustré en figure 1, dans laquelle Le gestionnaire de protocole comprend un masque global M1 pour les filtres F1-F14, un masque spécifique M2 pour le F15, une mémoire tampon par filtre, ces mémoires étant repérées par T1-T15. Un autre exemple d'architecture est représenté en figure 2, dans laquelle le gestionnaire de protocole comprend un masque spécifique M1 pour le filtre F1, un masque spécifique M2 pour le filtre F2, et une unique mémoire tampon T1. Les valeurs des masques et des filtres doivent être choisies pour accepter dans une ou des mémoires tampon disponibles au moins toutes les trames que le calculateur doit consommer. L'architecture du gestionnaire de protocole peut permettre de placer une trame consommée par mémoire tampon, de sorte que le calcul des valeurs de masque et de filtres est alors simple et immédiat. Mais l'architecture du gestionnaire de protocole peut aussi ne pas permettre de placer une trame consommée par mémoire tampon. Certaines mémoires tampon doivent alors accepter plusieurs trames consommées. Les masques et filtres associés à une telle mémoire tampon doivent alors être du type non spécifique pour pouvoir accepter des trames correspondant à plusieurs valeurs d'identificateurs différentes. Il n'est pas exclu que le masque et le filtre acceptent des trames parasites, c'est-à-dire qui ne sont pas destinées à être consommées par le calculateur. Par conséquent, pour une situation donnée, certaines valeurs de masque et de filtres sont plus avantageuses que d'autres. Considérons par exemple le cas où le calculateur doit consommer les trames 1, 2, 3 et 4 ayant respectivement les identificateurs 010 0000 1000b, 010 1000 1000b, 010 0100 1000b, 010 0010 1000b, et dans lequel une trame ne devant pas être consommée, ayant l'identificateur 010 0110 1000b, circule également sur le réseau. Avec deux filtres valant respectivement 010 X000 1000b et 010 OXXO 1000b, les trames 1 et 2 sont acceptées par le premier filtre, et les trames 3 et 4 sont acceptées par le second filtre. Mais la trame non consommée ayant l'identificateur 010 0110 1000b est aussi acceptée par le second filtre. Si les filtres valent respectivement 010 00X0 1000b et 010 XX00 1000b, les trames 1 et 4 sont acceptées par le premier filtre, et les trames 2 et 3 sont acceptées par le second filtre. Mais la trame non consommée, ayant l'identificateur 010 0110 1000b n'est acceptée par aucun filtre. Le second choix est donc meilleur que le premier puisqu'il n'accepte pas de trame parasite. Les trames parasites sont néfastes car elles occupent inutilement les mémoires tampon, elles obligent un filtrage logiciel supplémentaire, et elles interrompent inutilement le processeur du calculateur. Le but de l'invention est de proposer un procédé d'optimisation des valeurs des masques et des filtres d'un gestionnaire de protocole d'un calculateur, vis à vis des trames que consomme le calculateur et des trames que le calculateur ne consomme pas. A cet effet, l'invention a pour objet un procédé de détermination d'un masque et d'un ou plusieurs filtres, pour un gestionnaire de protocole d'un calculateur relié à un réseau de véhicule automobile de type CAN dans lequel circulent des trames de données comprenant chacune un identificateur, le calculateur consommant des trames dont les identificateurs ont certaines valeurs prédéterminées une trame étant acceptée si l'application de l'opérateur logique "ET" entre le masque et l'identificateur donne un résultat identique à la valeur du filtre, toutes les trames à consommer par le calculateur devant être acceptées et minimisant l'acceptation des trames ne devant pas être acceptées, caractérisé en ce qu'il consiste à : a) générer aléatoirement une population comprenant un nombre prédéterminé d'individus incluant chacun un masque et un ou plusieurs filtres ayant des valeurs définies ; b) évaluer un individu de la population en le testant avec les identificateurs de toutes les trames pouvant circuler sur le réseau pour déterminer un score représentatif de sa performance vis à vis des trames acceptées et des trames à consommer par le calculateur et de la fréquences de l'apparition de ces trames sur le réseau ; c) retenir l'individu testé si son score satisfait 15 à un critère prédéfini et évaluer un autre individu si le score ne satisfait pas à ce critère prédéfini ; d) générer une nouvelle population et reprendre en b) si aucun individu de la population ne satisfait au critère prédéfini. 20 L'invention concerne également un procédé tel que défini ci-dessus, dans lequel la génération d'une nouvelle population dans l'étape d) comprend la sélection de N individus dans la population courante en choisissant les individus présentant les meilleurs scores, un 25 individu pouvant être sélectionné plusieurs fois. L'invention concerne également un procédé tel que défini ci-dessus, dans lequel la génération d'une nouvelle population dans l'étape d) comprend le croisement et/ou la mutation de certains des individus 30 sélectionnés. L'invention concerne également un procédé tel que défini ci-dessus, dans lequel le score d'un individu est d'autant meilleur que les trames non consommées qu'il accepte ont une périodicité importante. 35 L'invention concerne également un procédé tel que défini ci-dessus, consistant à croiser deux individus selon une probabilité prédéterminée. L'invention concerne également un procédé tel que défini ci-dessus, consistant à muter deux individus selon une probabilité prédéterminée. L'invention sera maintenant décrite plus en détail, et en référence aux dessins annexés qui en illustrent une forme de réalisation à titre d'exemple non limitatif. - La figure 1 est une représentation schématique d'une première architecture de gestionnaire de protocole ; - La figure 2 est une représentation schématique d'une seconde architecture de gestionnaire de protocole ; - La figure 3 est une représentation schématique de différentes architectures possibles ; - La figure 4 est une représentation schématique 15 d'une architecture particulière ; - La figure 5 est une représentation schématique d'une solution particulière correspondant à l'architecture de la figure 4 ; - La figure 6 est une représentation schématique de 20 l'invention. L'invention est un procédé d'optimisation des valeurs des masques et des filtres d'un gestionnaire de protocole d'un calculateur. Pour représenter une solution, un modèle 25 d'architecture de gestionnaire de protocole est défini. Ce modèle prend en compte le nombre de masques, le nombre de filtres, et le nombre de mémoires tampon, ainsi que les relations existant entre les masques les filtres et les mémoires tampon pour le gestionnaire de protocole 30 considéré. Pour représenter les différentes architectures possibles, il faut considérer qu'à un masque M peut être associé un ou plusieurs filtres F, qu'un filtre F est associé à un unique masque M et à une unique mémoire 35 tampon T, et qu'à une mémoire tampon T peut être associé un ou plusieurs filtres F, ce qui est illustré schématiquement en figure 3. Le modèle prend aussi en compte la profondeur de chaque mémoire tampon, la taille de chaque masque et de chaque filtre. Ces paramètres peuvent être représentés par quatre tables . Une première table donne pour chaque indice de masque une taille en nombre d'indicateurs binaires, par exemple en associant la taille 11 aux masques M1 et M2. Une deuxième table donne pour chaque indice de filtre une taille en nombre d'indicateurs binaires, par exemple en associant la taille 11 aux filtres F1, F2 et F3. Une troisième table donne pour chaque mémoire tampon sa profondeur, par exemple en associant la profondeur 1 aux mémoires T1 et T2. Une quatrième table associe à chaque indice de filtre un indice de masque et un indice de mémoire tampon, par exemple en associant aux filtres F1 et F2, le masque M1 et la mémoire tampon T1, et en associant au filtre F3, le masque M2 et la mémoire T2. Les tables ci-dessus représentent l'architecture représentée en figure 4. Une solution particulière au problème peut être celle qui est illustrée en figure 5, dans laquelle on a attribué aux masques M1-M2 et aux filtres F1-F3 des valeurs avec lesquelles au moins toutes les trames à consommer par le calculateur sont acceptées dans les mémoires tampon T1 et T2. Une fonction d'adéquation ou fonction de coût, est ensuite définie pour associer à une solution donnée, un score représentatif de la performance de cette solution vis-à-vis des trames acceptées et des trames consommées. Ce score dépend du nombre de trames consommées acceptées, du nombre de trames parasites acceptées, du nombre total de trames acceptées, de la périodicité des trames parasites acceptées, etc. Pour obtenir ces informations et calculer ce score, il est nécessaire de connaître l'intégralité des trames consommées et non consommées par le calculateur. Ceci permet de comptabiliser, pour une solution donnée, les trames consommées et les trames parasites acceptées dans chaque mémoire tampon. La fonction d'adéquation peut être définie soit pour attribuer un score d'autant plus élevé que la performance est satisfaisante, ou bien d'autant plus faible que la performance est satisfaisante, ce choix pouvant être conditionné par l'algorithme d'optimisation qui est choisi. Les contraintes de la fonction d'adéquation peuvent être définies comme suit : le score est meilleur lorsque le nombre de trames parasites acceptées diminue ; le score est meilleur lorsque les occurrences des trames parasites acceptées diminuent ; le score est meilleur lorsque le nombre de trames consommées acceptées augmente ; le score est meilleur lorsque le nombre total d'identifiants acceptés diminue ; etc. Un algorithme métaheuristique de résolution approchée du problème est ensuite mis en oeuvre. Cet algorithme est par exemple celui qui est représenté en figure 6. Cet algorithme représenté symboliquement par le bloc A reçoit en entrée trois catégories d'informations : l'architecture d'une solution, notée STR, définie par les quatre tables mentionnées plus haut ; des informations sur les trames TC devant être consommées par le calculateur, à savoir leurs identificateurs et leurs périodicités ; des informations sur les trames TNC ne devant pas être consommées par le calculateur, c'est-à-dire leurs identificateurs et leurs périodicités. L'ensemble des trames TC et des trames TNC est représentatif de la totalité des trames circulant sur le réseau auquel le calculateur est relié. Partant des données STR, TC et TNC, l'algorithme A fournit en sortie les valeurs optimisées, notées S0, des masques et des filtres. Cet algorithme génère des solutions qu'il évalue, et il retient par exemple la première solution dont le score répond à un critère prédéterminé. Ce critère est par exemple un score minimal si la fonction d'adéquation attribue un score d'autant plus élevé que la performance de la solution est satisfaisante. Dans le cas où cette fonction attribue un score d'autant plus faible que la solution est performante, le critère peut être une valeur maximale du score. Avantageusement, la fonction d'adéquation assure que le score d'une solution n'acceptant pas toutes les trames consommées par le calculateur ne peut pas remplir le critère, de sorte que cette solution ne pourra pas être retenue. L'algorithme A peut être basé sur l'algorithme générique ci-dessous, dans lequel chaque individu représente une solution particulière, c'est-à-dire des valeurs pour les masques et pour les filtres, et dans lequel une population est un ensemble d'individus. Cet algorithme se décrit comme suit : - Créer une population de N individus - Initialiser aléatoirement une population de N individus - Pour chaque génération -Evaluer les individus de la population actuelle - Sélectionner N individus pour créer une population intermédiaire - Croiser les individus de la population intermédiaire avec une probabilité Pc -Muter les individus de la population intermédiaire avec une probabilité Pm - La population intermédiaire devient la population actuelle - Si la condition de sortie est vérifiée alors 35 -Arrêter l'algorithme - Sinon - Créer une nouvelle génération - Fin si - Fin pour Cet algorithme comprend trois paramètres : N qui est la taille de la population, Pc qui est la probabilité de croisement, et Pm qui est la probabilité de mutation. Supposons par exemple qu'un individu est représenté par la structure de la figure 4, la création d'une population de N individus consiste alors à créer N fois la structure représentée en figure 4. L'initialisation aléatoire des individus est réalisée en attribuant aléatoirement les valeurs des masques M1 et M2 et des filtres F1-F3 à chacun des N individus. A l'issue de cette opération un individu est par exemple représenté par la figure 5. L'évaluation des N individus de la population consiste à calculer le score de chaque individu avec la fonction d'adéquation mentionnée plus haut. En connaissant toutes les trames consommées TC et toutes les trames non consommées TNC, on détermine quelles sont les trames acceptées dans mémoires tampon T1 et T2 par l'individu en cours d'évaluation, ce qui permet de déterminer le score de cet individu. La sélection consiste à choisir N individus dans la population, un individu pouvant être choisi plusieurs fois. La probabilité qu'un individu soit choisi dépend de son score plus le score d'adéquation est bon, plus l'individu a des chances d'être sélectionné. Le croisement de deux individus est effectué avec un opérateur de croisement pour créer un individu fils dépendant de deux individus parents. Par exemple, si les parents ont les valeurs de masque 11001101110 et 00101100101, on peut définir un opérateur de croisement tel que le fils aura pour valeur de masque 11001100101 qui est constitué par les premières valeurs binaires du premier parent, et les dernières valeurs binaires du second parent. Le croisement est appliqué avec une probabilité Pc, si Pc = 50 %, la moitié des individus seront croisés. Le croisement des individus de la population permet l'intensification et l'exploitation des solutions. La mutation est également réalisée avec un opérateur de mutation qui peut, par exemple, consister à choisir un masque ou un filtre d'un individu et à faire le complément à 1 de sa valeur en binaire : 01001110101 devient 10110001010. La mutation est appliquée avec une probabilité Pm. Par exemple, si Pm = 0,5%, 0,5% des individus subiront une mutation. La mutation de la population permet la diversification et l'exploration des solutions. Le fait que la condition de sortie de l'algorithme est vérifiée consiste à déterminer s'il existe parmi la population évaluée, un individu ayant un score remplissant le critère prédéterminé, par exemple un score supérieur à une valeur minimale. L'algorithme est mis en oeuvre sur un calculateur pour définir les valeurs optimisées des masques et des filtres, à partir de l'architecture du gestionnaire de protocole et des trames circulant sur le réseau qui constituent les données du problème, résultant de la structure générale qui a été choisie pour le réseau. La mise en oeuvre de l'algorithme dans un calculateur tel qu'un ordinateur consiste notamment à simuler pour chaque individu, sa réaction vis à vis de chaque trame pouvant circuler sur le réseau de manière à déterminer le score de cet individu. L'invention permet ainsi de minimiser la quantité de trames parasites acceptées en mémoire tampon. Elle permet, grâce à la prise en compte des périodes des trames, de minimiser les occurrences des trames parasites acceptées. En d'autres termes, elle permet de favoriser des trames parasites ayant une grande période telle qu'une seconde, plutôt que des trames REVENDICATIONS 1. Procédé de détermination d'un masque (Ml, M2) et d'un ou plusieurs filtres (F1-F3), pour un gestionnaire de protocole d'un calculateur relié à un réseau de véhicule automobile de type CAN dans lequel circulent des trames de données (TC, TNC) comprenant chacune un identificateur, le calculateur consommant des trames (TC) dont les identificateurs ont certaines valeurs prédéterminées, une trame étant acceptée si l'application de l'opérateur logique "ET" entre le masque (Ml, M2) et l'identificateur donne un résultat identique à la valeur du filtre (F1-F3), toutes les trames à consommer par le calculateur devant être acceptées et minimisant l'acceptation des trames ne devant pas être acceptées, caractérisé en ce qu'il consiste à : a) générer aléatoirement une population (P) comprenant un nombre prédéterminé (N) d'individus incluant chacun un masque (Ml, M2) et un ou plusieurs filtres (F1-F3) ayant des valeurs définies ; b) évaluer un individu de la population en lescore ne satisfait pas à ce critère prédéfini ; d) générer une nouvelle population et reprendre en b) si aucun individu de la population ne satisfait au 25 critère prédéfini. 2. Procédé selon la revendication 1, dans lequel la génération d'une nouvelle population dans l'étape d) comprend la sélection de N individus dans la population courante en choisissant les individus présentant les 30 meilleurs scores, un individu pouvant être sélectionné plusieurs fois. 3. Procédé selon la revendication 2, dans lequel la génération d'une nouvelle population dans l'étape d) comprend le croisement et/ou la mutation de certains des 35 individus sélectionnés. 4. Procédé selon l'une des revendications 1 à 3, dans lequel le score d'un individu est d'autant meilleurque les trames non consommées qu'il accepte ont une périodicité importante. 5. Procédé selon la revendication 3 ou 4, consistant à croiser les individus selon une probabilité 5 (Pc) prédéterminée. 6. Procédé selon l'une des revendications 3 à 5, consistant à muter les individus selon une probabilité (Pm) prédéterminée.