Ordonnancement des tâches pour radar multifonction avec contrainte en temps dur et priorité

18/01/2016
Publication REE REE 2015-5
OAI : oai:www.see.asso.fr:1301:2015-5:14950
contenu protégé  Document accessible sous conditions - vous devez vous connecter ou vous enregistrer pour accéder à ou acquérir ce document.
Prix : 10,00 € TVA 20,0% comprise (8,33 € hors TVA) - Accès libre pour les ayants-droit
 

Résumé

Ordonnancement des tâches pour radar multifonction avec contrainte en temps dur et priorité

Auteurs

Optimal matching between curves in a manifold
Drone Tracking Using an Innovative UKF
Jean-Louis Koszul et les structures élémentaires de la Géométrie de l’Information
Poly-Symplectic Model of Higher Order Souriau Lie Groups Thermodynamics for Small Data Analytics
Session Geometrical Structures of Thermodynamics (chaired by Frédéric Barbaresco, François Gay-Balmaz)
Opening and closing sessions (chaired by Frédéric Barbaresco, Frank Nielsen, Silvère Bonnabel)
GSI'17-Closing session
GSI'17 Opening session
Démonstrateur franco-britannique "IRM" : gestion intelligente et homéostatique des radars multifonctions
Principes & applications de la conjugaison de phase en radar : vers les antennes autodirectives
Nouvelles formes d'ondes agiles en imagerie, localisation et communication
Compréhension et maîtrise des tourbillons de sillage
Wake vortex detection, prediction and decision support tools
Ordonnancement des tâches pour radar multifonction avec contrainte en temps dur et priorité
Symplectic Structure of Information Geometry: Fisher Metric and Euler-Poincaré Equation of Souriau Lie Group Thermodynamics
Reparameterization invariant metric on the space of curves
Probability density estimation on the hyperbolic space applied to radar processing
SEE-GSI'15 Opening session
Lie Groups and Geometric Mechanics/Thermodynamics (chaired by Frédéric Barbaresco, Géry de Saxcé)
Opening Session (chaired by Frédéric Barbaresco)
Invited speaker Charles-Michel Marle (chaired by Frédéric Barbaresco)
Koszul Information Geometry & Souriau Lie Group 4Thermodynamics
MaxEnt’14, The 34th International Workshop on Bayesian Inference and Maximum Entropy Methods in Science and Engineering
Koszul Information Geometry & Souriau Lie Group Thermodynamics
Robust Burg Estimation of stationary autoregressive mixtures covariance
Koszul Information Geometry and Souriau Lie Group Thermodynamics
Koszul Information Geometry and Souriau Lie Group Thermodynamics
Oral session 7 Quantum physics (Steeve Zozor, Jean-François Bercher, Frédéric Barbaresco)
Opening session (Ali Mohammad-Djafari, Frédéric Barbaresco)
Tutorial session 1 (Ali Mohammad-Djafari, Frédéric Barbaresco, John Skilling)
Prix Thévenin 2014
SEE/SMF GSI’13 : 1 ère conférence internationale sur les Sciences  Géométriques de l’Information à l’Ecole des Mines de Paris
Synthèse (Frédéric Barbaresco)
POSTER SESSION (Frédéric Barbaresco)
ORAL SESSION 16 Hessian Information Geometry II (Frédéric Barbaresco)
Information/Contact Geometries and Koszul Entropy
lncs_8085_cover.pdf
Geometric Science of Information - GSI 2013 Proceedings
Médaille Ampère 2007

Métriques

10
4
595.93 Ko
 application/pdf
bitcache://9033a7a845c688cd5aea564aefcf55c1b09f6727

Licence

Creative Commons Aucune (Tous droits réservés)
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/1301:2015-5/14950</identifier><creators><creator><creatorName>Frédéric Barbaresco</creatorName></creator><creator><creatorName>Vincent Jeauneau</creatorName></creator><creator><creatorName>Thomas Guenais</creatorName></creator></creators><titles>
            <title>Ordonnancement des tâches pour radar multifonction avec contrainte en temps dur et priorité</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2016</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Mon 18 Jan 2016</date>
	    <date dateType="Updated">Thu 26 Jan 2017</date>
            <date dateType="Submitted">Mon 15 Oct 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">9033a7a845c688cd5aea564aefcf55c1b09f6727</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>25483</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

RADARS À ANTENNES ÉLECTRONIQUESRADAR 2014 64 REE N°5/2015 Ordonnancement des tâches pour radar multifonction avec contrainte en temps dur et priorité Par Vincent Jeauneau1 , Frédéric Barbaresco2 , Thomas Guenais2 LIP6, UPMC1 ,Thales Air Systems, Advanced Radar Systems2 This paper presents the radar tasks problem for a set of tasks called Hard Time Constraint tasks which cannot delay their processing by more than a positive constant and for a set of tasks called Soft Time Constraint tasks which can be processed at any time. For solving this problem, we present a method based upon an heuristic sequencing STC tasks and a selection rule determining which task has to be scheduled between the first task of both sequences. ABSTRACT Introduction Les radars multifonction utilisent des antennes à balayage électronique permettant de pointer leurs faisceaux électromagnétiques presque instanta- nément suivant deux axes en azimut et en élévation. Cette flexibilité accroit l’agi- lité du senseur et permet au radar de réaliser plusieurs fonctions avec la même antenne, telles que la surveillance volu- mique de l’espace, la poursuite de cibles menaçantes, la reconnaissance non-coo- pérative des objets les plus menaçants, le guidage de missile de l’engagement jusqu’à l’interception… Chacune de ces fonctions radar est composée d’une ou plusieurs tâches, de durée variable (qui dépend de la forme d’onde émise cal- culée dynamiquement), qui doivent être exécutées séquentiellement par l’antenne, en respectant les contraintes temporelles associées (date d’activation, période, date d’échéance) et l’ordre res- pectif de leur priorité traduisant l’impor- tance opérationnelle de réalisation de la tâche à un instant donné. Dans [2] [3], Barbaresco présente les principes généraux de la gestion dyna- mique des ressources pour les radars multifonction ainsi qu’une architecture fonctionnelle pour sa mise en œuvre. Cette allocation optimale des ressources du senseur entre ses différentes fonctions est particulièrement critique lorsque le radar est soumis à des surcharges locales ou globales, découlant d’un excès de demandes de tâches. Dans ce contexte, lorsque les tâches à séquencer entrent en conflit, l’ordonnanceur joue un rôle pri- mordial pour déterminer l’ordre temporel des tâches à exécuter et sélectionner la liste des tâches à rejeter ou à retarder. L’algorithme d’ordonnancement a pour rôle de construire le séquencement temporel optimal des tâches en tenant compte conjointement des contraintes temporelles et de l’importance rela- tive entre ces tâches (codées par des niveaux de priorité). Pour un panorama plus large des problématiques de gestion dynamique des ressources radar et des algorithmes associés, nous renvoyons le lecteur à la lecture de l’article du DRDC canadien [8], dans lequel Ding y pré- sente un état de l’art du domaine. Les études relatives à l’ordonnan- cement des tâches radar peuvent se scinder en deux grandes familles. Une première famille de problèmes considère des tâches radar couplées. Nous parlons de tâches couplées, lorsque la tâche est composée d’un intervalle de temps d’émission (ai ) suivi par un temps mort (Li ) et terminé par un intervalle de récep- tion (bi ). Ces problèmes se différencient d’une seconde famille, pour laquelle les tâches sont supposées non sécables, définies par une durée globale égale à ai + Li + bi , qui doit être séquencée dans sa totalité. Dans les deux cas, nous considé- rerons pour le domaine applicatif radar, des tâches non-préemptives. Dans le cas de d’ordonnancement des tâches radar couplées, l’objectif est d’es- sayer d’entrelacer les tâches afin d’utiliser avantageusement l’intervalle de temps mort entre l’émission et la réception. Pour résoudre ce problème, Izquierdo- Fuente & al. dans [10] ont développé un algorithme d’entrelacement optimal basé sur un réseau de neurones, et en paral- lèle, Orman & al. du DSTL UK dans [16] ont introduit un algorithme basé sur une heuristique temps réel dont ils ont étu- dié les performances. Dans [7], Duron et al. ont considéré un algorithme d’ordon- nancement basé sur des priorités entre des tâches entrelacées et des tâches non entrelacées. Dans [14], Miranda et al. ont comparé les algorithmes d’ordon- nancement proposés par Butler dans [4] à ceux proposés par Orman & al. dans [16]. Enfin, Barbaresco avec Zheng et Baptiste du département LIX de l’Ecole Polytechnique dans [17] ont étudié le problème d’ordonnancement de tâches REE N°5/2015 65 Ordonnancement des tâches pour radar multifonction avec contrainte en temps dur et priorité radar couplées avec des contraintes de facteur de forme (duty cycle : contraintes sur le ratio durée d’émission et durée de réception). Pour le problème d’ordonnancement des tâches radar non sécables et non préemptives, Butler & al. [5] ont pro- posé un algorithme qui essaie d’ordon- nancer les tâches au plus proche de la date d’exécution requise par le système. Dans [1] [2] [3] Barbaresco et al. ont pré- senté des méthodes d’ordonnancement de type “short-planner”, basées sur une planification à l’échelle d’une trame (la trame est l’ensemble des tâches trans- mises à l’antenne), associées à des stratégies de relaxations itératives des contraintes. Dans [6], [11] et [15], les auteurs ont reformulé le problème d’or- donnancement des tâches radar à l’aide de fonctions d’utilités. Enfin plus récem- ment, Jeauneau, Barbaresco & Guenais dans [12] [18] [19] ont considéré le pro- blème d’ordonnancement des tâches radar avec des contraintes en temps dur et ont proposé une méthode qui maxi- mise le nombre d’exécutions de tâches de ce type, en minimisant le retard des tâches non contraintes. Dans cet article, nous étudions le problème d’ordonnancement de tâches radar paramétrées par des niveaux de priorité, (importance de la tâche) et des contraintes en temps dur. Pour résoudre ce problème, nous construisons sépa- rément une séquence pour les tâches contraintes en temps dur et une autre séquence pour les tâches contraintes en temps mou. Nous développons ensuite un algorithme qui détermine quelle pre- mière tâche de chacune des séquences doit être exécutée. L’article est organisé de la manière suivante : - troduisons le problème d’ordonnance- ment et sa modélisation. permet de séquencer les tâches avec contraintes en temps mou. la gestion des tâches contraintes en temps dur. Enfin, dans la cinquième section, nous présentons l’algorithme d’ordonnance- ment globale qui séquence conjointe- ment les deux familles de tâches. Nous concluons en illustrant les performances avec des résultats de simulation. Le problème d’ordonnan- cement avec des contraintes de priorités et de temps dur Dans un radar multifonction, il y a plusieurs types de tâches à exécuter (figure 1). Certaines sont périodiques : surveillance, pistage, guidage missile… D’autres sont apériodiques : classifica- tion, confirmation de destruction, etc. Nous étudions un système de défense aérienne où le radar doit explorer un volume de l’espace dans le but de détec- ter des cibles menaçantes. Le volume total de recherche peut être vu comme une matrice de n lignes et m colonnes. Chaque élément de la matrice repré- sente une position. A chaque position est associée une tâche radar de surveillance. Quand un objet est détecté, le radar doit le poursuivre avec des pointages dédiés de poursuite pour alimenter un filtre de pistage de type Kalman. A la demande du centre de contrôle, un ou plusieurs objets peuvent être engagés et une tâche de guidage missile est associée à chaque objet devant être intercepté. A la fin de l’interception, une tâche de confirma- tion de destruction sera exécutée pour déterminer si la cible a été détruite. Nous Figure 1 : Les différents types de tâches d’un radar multifonction - Source : Thalès. RADARS À ANTENNES ÉLECTRONIQUESRADAR 2014 66 REE N°5/2015 verrons qu’il existe une structure de prio- rité entre les différents types de tâches. Plus précisément, le problème est modélisé par des tâches périodiques qui souhaitent se répéter avec une période i entre deux exécutions. Cette période i correspond au temps séparant deux exé- cutions de la tâche Ti donnant les meil- leures performances pour cette tâche. Ce moment est appelé date d’exécution désirée oi de la tâche et est calculé en ajoutant la période i à l’instant si de dernière exécution de la tâche. Bien que oi soit la date d’exécution désirée de la tâche, il n’y a pas d’obligation de l’exé- cuter à cet instant. Comme le montre la figure 2, une tâche Ti peut être exécutée avant oi (ce qui augmente la charge in- duite par la tâche sans améliorer ses per- formances), après oi (ce qui diminue la charge induite par la tâche mais diminue encore plus ses performances) ou juste à la date oi . En revanche une tâche non périodique est caractérisée seulement par sa date de création ci et sa date d’exé- cution désirée oi . Tout comme les tâches périodiques, une tâche apériodique peut être exécutée avant, après ou à sa date d’exécution requise. Dans notre problème, les tâches sont séparées en deux classes. La première classe définit l’ensemble des tâches contraintes en temps dur (HTC). Ces tâches doivent être exécutées à leur date d’exécution requise avec un retard maximal autorisé . En revanche, les tâches HTC ne peuvent pas être exé- cutées avant leur date d’exécution sou- haitée. Cela signifie qu’une tâche HTC doit commencer son exécution entre [oi , oi + ] ou doit être rejetée (voir fi- gure 3). Ce type de contraintes strictes sur la fenêtre temporelle d’exécution concerne principalement les pointages de poursuite active en phase de pistage terminal lors de d’interception de cibles menaçantes. La deuxième classe définit l’ensemble des tâches contraintes en temps mou (STC). Ces tâches peuvent être retardées à volonté mais plus elles sont retardées, plus leur performance est faible. Par exemple, une tâche de surveillance est une tâche STC. Un re- tard excessif peut pénaliser les perfor- mances de la veille et réduire la portée de première détection. Comme mentionné précédemment, il existe une structure de priorité entre les différents types de tâches traduisant l’importance opérationnelle liée à leur exécution. Ainsi en cas de surcharge, l’ordonnanceur privilégiera les tâches de poursuite active sur les cibles mena- çantes par rapport aux tâches de surveil- lance, dans le cas d’un radar fonctionnant en mode « poursuite prioritaire » (le radar pouvant inversement aussi fonctionner en mode « surveillance prioritaire »). Cette priorité assignée par type de cibles pourra être affinée en tenant compte d’informations de contexte comme des informations de menaces. Par exemple, une tâche de pistage sur une cible mena- çante sera plus prioritaire qu’une tâche de pistage sur une cible alliée ou neutre. De même, parmi les cibles menaçantes à distance proche, celles disposant d’une vitesse de ralliement plus élevée seront plus prioritaires. Pour la veille, les poin- tages illuminant des zones plus sensibles comme les lignes de crêtes en milieu côtier pourront être privilégiés. Nous résumons les paramètres décri- vant les tâches radar non sécables : - tion si (dans le cas d’une tâche pério- dique) ou une date de création ci (dans le cas d’une tâche apériodique) ; i (seulement pour les tâches périodiques) ; i ; i ; i = oi + pi + (seulement pour les tâches HTC) ; i . Dans cet article, nous considérons un problème d’ordonnancement dans Figure 2 : Répétition d’une tâche périodique. Figure 3 : Retard maximal autorisé pour l’exécution d’une tâche HTC. REE N°5/2015 67 Ordonnancement des tâches pour radar multifonction avec contrainte en temps dur et priorité lequel de nouvelles tâches peuvent ap- paraître suite à la sélection des tâches précédentes. En effet, chaque tâche exécutée peut générer des évène- ments (détection, non-détection, requête externe...) et au cours du temps des tâches apparaissent, disparaissent ou sont mises à jour. En pratique, le sys- tème radar exécute les tâches à l’aide de trames (ensemble de tâches de poin- tage transmises à l’antenne). Pendant la construction d’une trame, l’environ- nement est figé et sera mis à jour juste avant la construction de la trame suivante [1], [2] et [3]. L’ordonnanceur construit la trame n + 1, pendant que l’antenne exécute la trame n transmise précédem- ment. Le choix d’une trame trop longue réduit la réactivité du radar. Inversement, une trame trop courte réduit le temps laissé à l’ordonnanceur pour optimiser le séquencement. Séquencer les tâches contraintes en temps mou Comme mentionné précédemment, les tâches STC peuvent être exécutées à tout moment mais plus elles sont retar- dées et plus leurs performances sont faibles. C’est pourquoi, dans cette sec- tion, nous allons séquencer les tâches STC en fonction de leur date d’exécution requise et leur priorité (voir figure 4 pour une vue générale de la procédure de construction d’une séquence). Si une tâche Ti est exécutée avant sa date d’exécution désirée oi , alors cette tâche a besoin de pi unités de temps sur un intervalle de taille inférieure à (oi – ai ), où ai = si si Ti est périodique, ai = ci si ce n’est pas le cas. Nous re- marquons que l’exécution de la tâche Ti avant sa date d’exécution souhaitée n’améliore pas les performances par rapport au cas où la tâche Ti est exécu- tée juste à l’instant oi (si la tâche Ti est exécutée à oi , alors Ti a besoin de pi uni- tés de temps sur un intervalle de taille (oi – ai )). En conséquence, il n’y pas de bénéfice à exécuter une tâche avant sa date d’exécution requise puisque la charge induite de la tâche sera plus im- portante et ses performances ne seront pas améliorées pour autant. C’est pour- quoi dans la suite, nous interdirons d’exé- cuter une tâche avant sa date d’exécution requise tant qu’il y a au moins une tâche qui est en retard par rapport à sa date d’exécution désirée. Cette interdiction nous permet de définir une première règle dans le but de séquencer les tâches STC. Nous décidons donc de trier les tâches dans l’ordre décroissant de leur date d’exé- cution requise. Nous séparons ensuite ces tâches en deux sous-ensembles de tâches. Le premier sous-ensemble appelé « urgent » contient les tâches qui sont en retard par rapport à leur date d’exécution désirée. Le second sous-en- semble appelé « non urgent » contient les tâches qui ne peuvent pas être exé- cutées tant qu’il y a au moins une tâche en retard. Cette séparation est faite en utilisant la valeur du temps courant t. Si une tâche possède une date d’exécu- tion requise inférieure au temps courant, alors cette tâche est en retard et sera mise dans l’ensemble des tâches « ur- gentes », sinon elle appartiendra à l’autre ensemble par défaut. Quand le système radar est sur- chargé, il est préférable d’ordonnancer les tâches ayant la plus grande priorité. Par conséquent, les tâches dans l’en- semble « urgent » doivent être réarran- gées par ordre croissant de leur priorité. Enfin, les tâches de l’ensemble « non urgent» sont réarrangées par ordre dé- croissant de leur Relative Delay (retard normalisé par leur période nominale re- quise) pour minimiser la charge générée par ces tâches. Séquencer les tâches contraintes en temps dur Dans cette section, nous considérons l’ensemble des tâches contraintes en temps dur et nous nous fixons l’objectif de séquencer ces tâches pour minimiser la priorité maximale des tâches rejetées. Comme mentionné auparavant, une tâche HTC doit être exécutée à sa date d’exécution requise avec un retard maxi- mal autorisé . De plus, une tâche HTC Figure 4 : Vue générale de la procédure pour séquencer les tâches STC. RADARS À ANTENNES ÉLECTRONIQUESRADAR 2014 68 REE N°5/2015 ne peut pas être exécutée avant sa date d’exécution souhaitée. Par conséquent, une tâche HTC doit être intégralement exécutée dans l’intervalle [oi , di ] ou doit être rejetée. Garey & al. [9] ont prouvé que quand toutes les tâches satisfont la relation di = ri + pi + , où ri est la date de disponibilité de la tâche, alors il existe toujours un ordon- nancement admissible (un ordonnance- ment où toutes les tâches respectent leurs contraintes temporelles), respectant la forme standard définie comme un ordon- nancement qui commence par les tâches T1 , T2 , …Tj , puis est suivi par les tâches restantes Tn , Tj+1 , Tj+2 … Tn-1 exécutées dans cet ordre, sans aucun temps mort et aus- sitôt que possible (voir la figure 5 pour un exemple). Notons qu’une forme standard est définie pour les tâches indexées en fonction de leur date d’échéance crois- sante (d1 d2 … dn ). Comme les tâches HTC ne peuvent pas être exécutées avant leur date d’exécution désirée, alors nous pouvons définir une date de disponibilité pour chacune de ces tâches qui est égale à leur date d’exécu- tion désirée (ri = oi ). Avec cette définition, nous avons di = ri + pi + pour chaque tâche HTC. De plus, déterminer une séquence qui minimise la priorité maxi- male des tâches rejetées est équivalent à déterminer une séquence admissible de tâches qui maximise la priorité maximale des tâches comprises dans cet ensemble parmi tous les ensembles admissibles de tâches HTC. En se référant à la définition de la forme standard, nous déduisons que parmi toutes les séquences admissibles qui maximisent la priorité maximale des tâches de la séquence, il en existe une sous forme standard. Par conséquent, nous n’avons pas besoin de considérer toutes les séquences de tâches HTC mais uniquement celles qui sont sous forme standard. Définissons par SF(i, t) une séquence sous forme standard du sous ensemble de tâches {T1 , T2 , …, Ti } où le nombre de tâches de chaque priorité de la sé- quence est contenu dans le tableau t. Par exemple, si SF(i, t) est une séquence de tâches de priorité (1, 3, 5, 3, 4), alors le tableau t est le suivant : [1 ; 0 ; 2 ; 1 ; 1]. Définissons C(i, t) comme la date de fin de la séquence SF(i, t) lorsque chaque tâche est exécutée aussitôt que possible. D’après la forme standard, nous savons que nous avons SF(i, t) qui est composée de SF(j, t’) pour 0 j i – 1 et suivie par la séquence (Ti , Tj+1 , …, Ti-1 ). Nous proposons une variante de récurrence l de la séquence SFj l (i, t) qui est composée de SF(j, t’) avec j fixé et est suivie par la sous séquence (Ti , Tj+1 , …, TJ+l-1 ). En d’autres termes, le para- mètre de récurrence l indique le nombre de tâches de la séquence (Ti , Tj+1 …TJ+l-1 ) qui sont considérées. Comme pour une itération ifixée, les valeurs de SF(j, t’) et C(j, t’) sont supposées connues pour j = 0, 1…i – 1 et pour toutes les valeurs possibles de t’, alors les formules de ré- currences suivantes calculent les valeurs de SFj l (i, t) et Cj l (i, t) pour l = 0, 1 … i – j : a) pour l = 0 : Figure 5 : Un ordonnancement sous forme standard. b) pour l = 1 : c) pour l 2 : REE N°5/2015 69 Ordonnancement des tâches pour radar multifonction avec contrainte en temps dur et priorité Lorsque l = i – j, nous avons alors chaque séquence SFj (i, t) pour toutes les valeurs de t et de j grâce à : Et enfin, la séquence SF(i, t) est obte- nue à partir de l’indice j* pour lequel Cj* (i, t) est minimal, nous avons alors : Lorsque toutes les séquences SF(i, t) et les valeurs de C(i, t) sont connues pour toutes les valeurs de t, alors l’itération courante est terminée. En itérant sur i, la séquence des tâches HTC qui maximise la priorité maximale des tâches contenues dans la séquence, est obtenue, lorsque i = n, par SF(n, t* ), t* étant la meilleure solution pour laquelle la valeur de C(n, t* ) . Notons qu’entre deux solutions t1 = [0 ; 1 ; 2 ; 1 ; 3] et t2 = [0 ; 0 ; 1 ; 2 ; 3], la solution t2 est meilleure que la solution t1 car t1 exécute trois tâches de priorité 5 et une de prio- rité 4 alors que t2 exécute trois tâches de priorité 5 et deux de priorité 4. Algorithme et résultats de simulation Algorithme Dans cette section, nous présentons l’algorithme d’ordonnancement pour le problème d’ordonnancement global des tâches radar. Comme mentionné aupa- ravant, l’utilisation de trames nous offre une flexibilité puisque tant qu’une trame n’est pas terminée, il est encore possible de changer la séquence des tâches. D’un autre côté, cette stratégie génère un délai sur la prise en compte de l’évolution de l’environnement. Les évènements sont pris en compte juste avant de débuter la construction d’une trame. Par consé- quent, quand une trame radar est exé- cutée, les évènements causés par cette trame n’ont pas encore d’influence dans la construction de la trame suivante mais seront pris en compte pour la construc- tion de celle d’après. Quand la construction d’une trame radar commence, notre algorithme com- mence par appeler les méthodes déve- loppées dans les sections précédentes dans le but de construire une séquence de tâches pour les tâches HTC et les tâches STC séparément. A ce moment, nous avons deux séquences et notre algorithme doit combiner ces séquences dans le but de construire la trame radar. Ces séquences, nous donne un ordre dans lequel les tâches STC et les tâches HTC doivent être exécutées séparément. Par conséquent, notre algorithme doit déterminer quelle tâche doit être ajou- tée à la trame avant la première tâche de chaque séquence. Comme chaque tâche HTC ne peut pas être exécutée avant sa date d’exé- cution désirée, nous devons vérifier si le temps courant est supérieur à la date d’exécution désirée de la tâche avant de l’insérer dans la trame radar. Cette restriction sera utilisée pour déterminer quelle tâche sera insérée dans la trame radar entre la première tâche de cha- cune des séquences. Par conséquent, si le temps courant est supérieur à la date d’exécution désirée de la première tâche HTC, alors cette tâche sera retirée de sa séquence et sera insérée dans la trame radar. Sinon la première tâche STC sera Figure 6 : Vue générale de l’algorithme d’ordonnancement des tâches radar. RADARS À ANTENNES ÉLECTRONIQUESRADAR 2014 70 REE N°5/2015 retirée de sa séquence et insérée dans la trame radar. Quand une tâche est insérée dans la trame radar, nous supposons que la tâche sera exécutée au temps courant par l’antenne radar. En conséquence, nous mettons à jour le temps courant en y ajoutant la durée d’exécution de la tâche. Le processus est répété jusqu’à ce que la construction de la trame courante soit terminée (elle atteint ou dépasse la durée fixée d’une trame). Une vue géné- rale de cet algorithme est illustrée dans la figure 6. Résultats de simulation Une plate-forme de simulation en JAVA a été utilisée pour implémenter cet algorithme et le valider (figure 7). Dans cette section, nous présentons quelques résultats de simulation pour un radar multifonction ayant un domaine de cou- verture de [– 45°, + 45°] en azimut et de [0°, 70°] en élévation. Pour ce radar multifonction, les tâches de pistage ont une priorité plus élevée que les tâches de surveillance. Par conséquent, quand la charge globale du système est supé- rieure à 100%, les tâches de surveillance sont pénalisées par rapport aux tâches de pistage. Ce radar multifonction explore son domaine de couverture dans le but de détecter des cibles. Nous considérons deux types de cibles : les cibles mena- çantes et les cibles alliées ou neutres. Une tâche HTC sera associée à chaque cible menaçante, alors qu’une tâche STC sera associée à chaque cible alliée ou neutre. Chaque cible menaçante demande à être ordonnancée toutes les X millisecondes avec un retard maximal de , alors qu’une cible alliée ou neutre requiert d’être exécutée toutes les Y secondes. La priorité d’une cible mena- çante sera initialement fixée à wx alors que celle d’une cible alliée ou neutre sera fixée à wy x y . Pendant la simulation, si une tâche de pistage sur une cible menaçante est rejetée, alors nous augmentons la pé- riode de cette tâche de X millisecondes ; nous augmentons la priorité de la tâche de 1 et nous réinsérons la tâche dans le système avec ces nouveaux paramètres. Lorsque cette tâche sera ordonnancée, ses paramètres seront réinitialisés à X millisecondes pour sa période et wx pour sa priorité car la prochaine répétition de cette tâche pourra être exécutée légale- ment avec ces paramètres. Figure 7 : Plate-forme de simulation radar – Source : Thalès. REE N°5/2015 71 Ordonnancement des tâches pour radar multifonction avec contrainte en temps dur et priorité Les performances du système sont évaluées sur la base de la pire période sur les cibles menaçantes : cela signifie qu'on doit privilégier de pister deux cibles menaçantes toutes les 2.X millisecondes plutôt qu'une toutes les X millisecondes et l’autre toutes les 3.X millisecondes. Nous avons développé deux simu- lations. La première simulation SHTC exécute l’algorithme présenté dans la pre- mière partie de cette section et piste les cibles menaçantes avec des tâches HTC. La seconde simulation SSTC exécute un algorithme classique qui piste les cibles menaçantes avec des tâches STC de la manière suivante : une cible menaçante est pistée toutes les X millisecondes avec une priorité de wx par une tâche STC. Si une de ces tâches est exécutée avec un délai plus grand que , alors la tâche est rejetée et ses paramètres sont mis à jour (la période est augmentée de X millise- condes et la priorité est indexée d’une valeur 1). Lorsqu’une de ces tâches est exécutée, ses paramètres sont réinitiali- sés à X millisecondes pour la période et à wx pour la priorité. La figure 8 et la figure 9 représentent la période de répétition des tâches de pistage sur les cibles menaçantes pour la simulation SHTC et la simulation SSTC. Pour ces simulations, nous consi- dérons un scénario avec quatre cibles Figure 8 : Simulation SHTC. Figure 9 : Simulation SSTC. RADARS À ANTENNES ÉLECTRONIQUESRADAR 2014 72 REE N°5/2015 menaçantes. Les résultats de simulation pour SHTC montrent que le radar mul- tifonction avec l’algorithme décrit dans le présent article est capable de pister les quatre cibles avec une période de répétition maximale de 2.X millisecondes alors que pour SSTC la période de répé- tition croit jusqu’à 3.X millisecondes. Cet exemple illustre la capacité de l’algo- rithme proposé pour fournir un meilleur séquencement opérationnel qu’un algo- rithme classique, en particulier pour gérer le pistage sur des cibles à haute priorité, pour lesquelles nous voulons une préci- sion de pistage très élevée. La figure 10 représente un zoom de la figure 8 sur les périodes [X, X + ] et [2X, 2X + ]. La figure 11 illustre la période de répétition des tâches de surveillance au cours du temps. Nous pouvons, voir sur cette figure, trois périodes de charge : la charge standard, la surcharge et la sous-charge. La première période cor- respond à la charge standard du radar, la charge globale du système est d’environ 100%. Pendant cette période, les cibles ne sont pas encore classifiées comme menaçantes. Par conséquent, elles sont pistées avec des tâches STC. Durant la seconde période, le système devient petit à petit surchargé car des cibles commencent à être classifiées comme menaçantes. Dans ce cas,, le système passe d’une tâche STC à une tâche HTC pour pister la cible ce qui est illustré par la montée en charge progressive. A la fin de la période de surcharge, toutes les cibles ont été détruites et la charge du radar diminue car il ne reste plus que les tâches de surveillance à séquencer. Les tâches de surveillance correspondent à une charge demandée de 80% pour les périodes requises. Pendant cette période de sous-charge, le système ordonnance les tâches avant leur date d’exécution requise afin d’utiliser les 100% du temps radar disponible. Conclusion Dans cet article, nous avons présen- té un problème d’ordonnancement de tâches radar dans le cas de contraintes en temps dur pour assurer une préci- sion de mesure élevée sur les pistes très prioritaires, ces tâches devant être or- Figure 10 : Zoom sur les périodes [X, X + ] et [2X, 2X + ] de la simulation SHTC. Figure 11 : Ralentissement des pointages de veille. REE N°5/2015 73 Ordonnancement des tâches pour radar multifonction avec contrainte en temps dur et priorité donnancées au mieux à leur date d’exécu- tion requise et au plus tard après un délai . Pour résoudre ce problème, nous avons introduit deux classes de tâches : les tâches contraintes en temps dur et les tâches contraintes en temps mou. Nous avons en- suite construit une séquence pour chacune de ces classes. Les tâches STC sont d’abord triées en fonction de leur date d’exécution requise, puis séparées en deux sous-en- sembles de tâches. Nous retrions séparé- ment ces deux sous-ensembles à l’aide d’une heuristique. Nous avons proposé d’adapter un algorithme de programmation dynamique basé sur une propriété de dominance [9] l’algorithme prend ces deux séquences en entrées et construit une trame de tâches radar en sortie. A chaque état, cet algorithme décide quelle tâche doit être insérée dans la trame radar entre la première tâche de chaque séquence. Cette sélection est faite en testant si la première tâche HTC est dis- ponible (le temps courant est plus grand que la date d’exécution désirée de la tâche). Si c’est le cas, alors la tâche HTC est insérée dans la trame radar ; sinon, la tâche STC est insérée de façon alternative. Les résultats de simulation ont montré que l’algorithme pro- posé est plus performant que les algorithmes classiques pour séquencer les tâches néces- sitant une plus grande précision de pistage. Remerciements Les auteurs de cet article voudraient remercier la DGA/MRIS pour avoir financé la thèse CIFRE Défense DGA/THALES de Vincent Jeauneau, faite en collaboration avec le laboratoire d’informatique LIP6 de l’univer- sité UPMC. Références [1] F. Barbaresco, C. Boschet, J. C. Deltour, G. Desodt, B. Durand, T. Guenais & A. Merisse, Dynamic Multifunction Radar Resources Management: Rotating/Sta- ring Modes Performance Evaluation Based on Intensive Runs on ASTRAD Simulation Platform, IET UK/SEE COGIS’10 LES AUTEURS Frédéric Barbaresco est Senior Scientist & Advanced Studies Manager au sein de la Business Unit ARC (Advanced Radar Concepts) de THALES AIR SYSTEMS. Il est en charge de la spécification de la fonction GEDY (Gestion Dynamique des Ressources Radar) pour les futurs radars à balayage deux plans et a spécifié les algorithmes de beamscheduling de plusieurs radars THALES opérationnels. Il était l’expert technique des études EUROFINDER IRM “Intelligent Radar Mana- gement” et de plusieurs PEAs DGA sur le sujet. Il est correspondant THALES pour le groupe OTAN SET-223 “Adaptive Radar Resources Management”. Diplô- mé de SUPELEC en 1991, il est membre émérite de la SEE. Il a reçu en 2014, le prix Aymé Poirson de l’Académie des Sciences qui récompense l’application des sciences à l’industrie. Thomas Guenais est ingénieur d’études amont et algorithmes avancés au sein de la Business Unit ARC (Advanced Radar Concepts) de THALES AIR SYSTEMS. Il est en charge des simulations de la fonction GEDY (Gestion Dynamique des Ressources Radar) pour les futurs radars à balayage deux plans et implémente les algorithmes de beamscheduling. Il a participé aux études EUROFINDER IRM “Intelligent Radar Management” et à plusieurs PEAs DGA sur le sujet. Il est spé- cialisé dans l’optimisation des architectures logicielles de simulation radar pour une analyse comportementale (vision 2D/3D) temps réel des performances des systèmes complexes spécifiés. Il est diplômé d’études supérieures en infor- matique et spécialisé dans les systèmes et communications homme-machine à l’université Paris XI. Vincent Jeauneau est diplômé en 2010 d’un master informatique en intelli- gence artificielle et décision, spécialisation aide à la décision, recherche opéra- tionnelle et résolution de problèmes à la faculté de Paris VI. Il a ensuite effectué une thèse chez THALES AIR SYSTEMS sur les problèmes de beamscheduling liés aux développements d’une nouvelle génération de radars quatre panneaux fixes. En décembre 2013, il obtient le titre de docteur de l’université Paris VI en informatique, télécommunications et électronique de Paris. En février 2014, Vincent Jeauneau a débuté un post doctorat au sein de l’University College London sur le beamscheduling lié aux développements d’un réseau de radars bi-statiques. RADARS À ANTENNES ÉLECTRONIQUESRADAR 2014 74 REE N°5/2015 Conference, 22 November 2010, Crawley, UK. [2] F. Barbaresco, C. Y. Chanot, Intelligent Radar Resources management’, IRSI’07, International Radar Symposium, 10-13 December 2007, Bangalore, India. [3] F. Barbaresco, R. Wills, Intelligent Radar Management by advanced Beamscheduling algorithms based on time constraints relaxation strategies, IEEE International Symposium on Phased Array Systems, 14-17 October 2003, Boston, Massachusetts, USA. [4] J. M. Butler, Multi-function radar tracking and control, Ph.D. thesis, UCL University College London, 1998. [5] J. M. Butler, A. R. Moore & H.D. Griffiths, Resource management for a rotating multi-function radar, Radar 97 (Conf. Publ. No . 449), 1997, vol. 1, pp. 105-116. [6] A. Charlish, K. Woodbridge & H. Griffiths, Phased array radar resource management using continuous double auction, IEEE Transactions on Aerospace and Electronic Systems, Volume 51, Issue 3, pp. 2212-2224, July 2015. [7] C. Duron, J. M. Proth, Multi-function radar: task scheduling, Jour-nal of Mathematical Modeling and Algorithms, 2002, pp. 568-572. [8] Z. Ding, A survey of radar resource management algorithms, Canadian Conf. Electrical and Computer Engi- neering CCECE 2008, 2008, pp. 1559- 1564. [9] M. R. Garey, R. E. Tarjan, G. T. Wilfong, One-Processor Scheduling with Sy- mmetric Earliness and Tardiness Penalties, Mathematics of Operations Research, 1988, vol. 13, no . 2, pp. 330- 348. [10] A.Izquierdo-Fuente,J.R.Casar-Corredera, Optimal radar pulse scheduling using a neuralnetwork,InternationalConference Neural Network, 1996, Vol. 7, pp. 4558- 4591. [11] D. S. Jang, H. L. Choi & J. E. Roh, Search optimization for minimum load under detection performance constraints in multifunction radars, Aerospace Science and Technology, Volume 40, January 2015, pp. 86-95. [12] V. Jeauneau, T. Guenais, F. Barbaresco, Scheduling on a fixed multifunction radar antenna with hard time const- raint, International Radar Symposium, IRS’13, Dresden, 2013. [13] E. L. Lawler, Knapsack-Like Scheduling Problems, the Moore-Hodgson Al- gorithm and the “Tower of Sets” Property, Mathematical Computer Modeling, 20(2), 91-106, 1994. [14] S. L. C. Miranda, C. J. Baker, K. Woodbrige & H. D. Griffiths, Com- parision of scheduling algorithms for multifunction radar, IET Radar Sonar Navig., 2007, 1(6), pp. 414-424. [15] P.W.Moo,Schedulingformultifunction radar via two-slope benefit functions, IET Radar Sonar Navig., 2011, 5(8), pp. 884-894. [16] A. J. Orman, C. N. Potts, A. K. Shahani, & A. R. Moore, Scheduling for a mul- tifunction phased array systems, Euro- pean Journal of Operational Research, April 1996, vol. 90, no . 1, pp. 13-25. [17] Q. Zheng, P. Baptiste, & F. Barbaresco, On scheduling a multifunction radar with duty cycle budget, International Conference COGIS’09 (COGnitive systems with Interactive Sensors), November 2009, Paris. [18] V. Jeauneau, F. Barbaresco & T. Guenais, Radar Tasks Scheduling for a Multifunction Phased Array Radar with Hard Time Constraint and Priority, International Radar Conference, RADAR’14, Lille, October 2014. [19] V. Jeauneau, Contribution à l’ordon- nancement temps réel : Applications aux radars multifonctions, Thèse de Doctorat de l’université Pierre et Marie Curie, spécialité Informatique (École Doctorale Informatique, Télé- communication et Électronique de Paris), 13 Décembre 2013, supervisé par Philippe Chrétienne et Frédéric Barbaresco.