Algorithme d’ordonnancement en-ligne embarqué dans les véhicules

Les véhicules connectés génèrent des évènements à partir des informations brutes obtenues des capteurs sur l’environnement. Par exemple, un véhicule connecté peut générer un évènement qui indique la présence (ou l’absence) d’un panneau de signalisation, un évènement qui indique l’occurrence d’un freinage d’urgence, etc. Pour pouvoir facilement faire référence aux évènements générés par un véhicule et destinés à être transmis vers le Cloud, nous choisissons de les appeler évènements V2C. La Figure 4 illustre des évènements qui pourraient être générés par un système de reconnaissance d’image pour l’aide à la conduite.

La pertinence d’un évènement V2C varie avec le temps, parce qu’un évènement V2C caractérise l’environnement et l’environnement varie avec le temps. Par exemple, imaginons qu’un véhicule génère un évènement qui indique une place de parking libre dans un parking très prisé. L’évènement va rapidement perdre de l’utilité avec son âge, puisque la place de parking libre peut être prise par quelqu’un à tout instant. Au contraire, un évènement qui indique la présence d’un panneau de limitation de vitesse sera probablement valide plusieurs jours .

Puisque tous les évènements V2C ne peuvent pas être transmis vers le Cloud et puisque la pertinence des évènements varie avec le temps, maximiser l’utilité des évènements transmis requiert une priorisation adéquate pour décider lesquels doivent être transmis et quand. En raison de la nature fortement dynamique des véhicules et de l’environnement dans l’espacetemps, il est difficile de prévoir les évènements qui seront générés dans l’horizon futur, même lorsque l’horizon considéré est court. La solution proposée doit donc permettre une priorisation de la transmission des évènements V2C qui soit dynamique et fortement réactive.

Pour commencer, nous montrons comment le problème peut être défini comme un problème d’ordonnancement basé-valeur dans la théorie des systèmes temps-réel souple. Ensuite, nous proposons une évaluation expérimentale de différents algorithmes d’ordonnancement afin d’identifier celui qui résout le plus efficacement notre problème. Comme pour toute méthode expérimentale, il est nécessaire de s’assurer que les résultats obtenus sont représentatifs de cas réels. Comme les cas réels ne sont pas disponibles aujourd’hui, nous ne pouvons pas garantir que les résultats obtenus sont représentatifs de la réalité future. Le choix arbitraire des scénarios générés peut nous amener à introduire un biais de sélection et, in-fine, à des analyses et conclusions peu pertinentes, voire erronées. Pour limiter ce problème, nous étendons une méthode d’évaluation expérimentale d’algorithmes d’ordonnancement déjà existante pour améliorer la diversité des scénarios générés. La méthode que nous proposons permet d’investiguer, si besoin, des paramètres qui pourraient influencer la performance des algorithmes, ce qui confère une plus grande transparence de nos résultats. Les algorithmes évalués sont confrontés à deux instances d’un algorithme clairvoyant en-ligne qui fournissent des bornes pour l’évaluation et une juste référence pour la comparaison [Baruah et al., 1992, Gan and Suel, 2009, Attiya et al., 2010]. Les résultats que nous obtenons indiquent que l’algorithme DTD1 est le plus efficace en terme d’utilité cumulée, et est un candidat prometteur pour gérer le problème d’optimisation du transfert du flux de données V2C.

Définition du problème 

Au niveau logique, les évènements sont contenus dans des messages ; un message peut être composé de plusieurs évènements. Au niveau réseau, les messages sont divisés en paquet(s) de taille fixe. Nous supposons que l’envoie d’un paquet est une action atomique, c’est-à-dire que cette action ne peut être interrompue. En revanche, il est possible de suspendre (resp. reprendre) la transmission d’un message par la suspension (resp. la reprise) de la transmission des paquets restants. La préemption de la transmission d’un message est donc possible ; nous supposons de plus que cette préemption est instantanée et n’engendre pas de sur-coûts .

Les messages sont transmis vers le Cloud individuellement par chaque véhicule via un unique canal de communication de façon séquentielle, i.e. un message à la fois. La bande passante de communication disponible est connue et constante durant l’entièreté de la simulation. Malgré le fait que ces hypothèses sont très fortes pour notre contexte, où en réalité la bande passante disponible peut fortement varier et être difficile à prévoir, la pertinence de nos résultats expérimentaux est justifiée par le choix approprié des algorithmes évalués. En effet, nous avons argumenté en introduction que la priorisation du transfert des messages doit être fortement dynamique en raison de la forte dynamique des véhicules et de leur environnement. Les algorithmes que nous avons choisi d’évaluer possèdent deux caractéristiques pour répondre à ce besoin :
— les algorithmes prennent des décisions très fréquentes, avant le transfert de chaque paquet, ce qui confère la capacité d’adapter très rapidement la priorité des messages.
— les algorithmes considèrent un horizon futur relativement court, ce qui leur confère une certaine robustesse aux aléas du futur, par exemple une variation de la charge dû à l’apparition de nouveaux évènements, à une variation de la bande passante du réseau, etc.

Quand un message est reçu dans le Cloud, le message génère une certaine utilité au système global. Une définition exacte de l’utilité est hors du champ de ce chapitre; mais de façon très grossière, l’utilité représente la contribution que chaque message apporte à la qualité de service fournie à l’utilisateur final. La valeur d’utilité d’un message est liée aux évènements qu’il contient, et donc à leurs propriétés spatio-temporelles. Prenons par exemple le cas d’un évènement qui contient de l’information liée à la mobilité d’un véhicule. Après quelques secondes, le véhicule peut s’être déplacé de plusieurs centaines de mètres dans différentes directions, ou avoir modifié sa vitesse, rendant alors l’évènement peu pertinent pour des services critiques de sûreté, comme l’évitement de collision. Au contraire, un évènement indiquant la présence d’un panneau peut rester pertinent pour le système plusieurs heures voire plusieurs jours après sa génération.

La Quality of Service (QoS) du trafic dans les réseaux de communication sans-fil a été sujet à des efforts de recherche considérable dans les années récentes. Satisfaire des spécifications de QoS dans un environnement à ressources contraintes, comme un réseau de capteurs, est exceptionnellement difficile [Younis et al., 2010, Chen and Varshney, 2004, Alanazi and Elleithy, 2015]. Dans un réseau de capteur fortement mobile comme celui des véhicules, les difficultés posées par la QoS sont encore plus importantes. Il est également peu pertinent de borner le flux du trafic V2C, car la dynamique du réseau peut causer des ravages dans un transfert de données urgent [Ameen et al., 2008]. Tenant compte de ces considérations, nous supposons que les évènements transmis ne sont pas de nature critique, c’est-à-dire que de ne pas réussir à transmettre un évènement en temps voulu ne doit pas avoir une conséquence catastrophique sur le système.

On prévoit qu’une très grande quantité de données sera générée par des millions de véhicules. Envoyer tous les évènements générés par chaque véhicule n’est pas envisageable, étant donné que l’infrastructure cellulaire a déjà atteint sa capacité limite aujourd’hui. Et même dans l’éventualité où cette solution serait techniquement possible, la quantité de données transférées puis agrégées dans le Cloud serait telle que les coûts engendrés ne seraient pas tenables. Pour que le projet soit viable, il est nécessaire de trouver un compromis entre la quantité de données transmises et l’utilité globale générée. Nous supposons ici que la quantité de ressources disponibles pour la transmission des données est finie et déterminée au(x) niveau(x) supérieur(s) L1 et/ou L2, selon la décomposition du problème global que nous avons proposé et détaillé dans la partie I. Ici, nous devons donc décider quel message doit être transmit (en premier) et quand, en tenant compte de contraintes temporelles, dans l’objectif de maximiser l’utilité générée par le système global, sous une contrainte de ressources finies.

Nous supposons une isolation entre les véhicules, c’est-à-dire que les véhicules ne coopèrent pas entre eux. Ainsi, le problème de maximiser l’utilité générée par le système globale se réduit à maximiser l’utilité générée par chaque véhicule considéré indépendamment. Cette hypothèse permet une réduction considérable de la complexité du problème pour un meilleur passage à l’échelle. Dans ces travaux, nous ne considérons pas comment les messages sont construits à partir des évènements, et nous supposons que la date d’arrivée des futurs messages n’est pas connue à l’avance. En conséquence, nous nous concentrons sur l’étude d’algorithmes d’ordonnancement dynamique (= en-ligne, à la volée) en situation inconnue, et de possible surcharge. Le problème que nous résolvons dans notre travail ici consiste à trouver un algorithme d’ordonnancement préemptif, dynamique, et efficace pour envoyer un ensemble de messages (qui ont des propriétés d’utilité et temporelles), de sorte à ce que l’utilité soit maximisée pour chaque véhicule considéré individuellement. Dans la prochaine section, nous montrons que ce problème peut être traduit comme un problème d’ordonnancement à temps-réel souple.

Modélisation

Problème à temps-réel souple

Considérons un problème d’ordonnancement temps-réel où un ensemble de N jobs indépendants doivent être exécutés sur un unique processeur. Chaque job a une date d’arrivée, avant laquelle il ne peut pas être traité. Un job nécessite de traiter un certain nombre d’unités d’exécution pour être accompli. A chaque unité de temps, le processeur peut être au repos, ou au travail. La vitesse du processeur réfère au nombre d’unité d’exécution qu’il peut traiter par unité de temps (lorsqu’il est au travail). Au temps k, si s [k] dénote la vitesse du processeur et cj [k] dénote le nombre d’unités d’exécution restant pour qu’un job soit traité, min (cj [k] , s [k]) unités d’exécution sont traitées durant cette unité de temps.

Dans notre problème, transmettre des messages vers le Cloud est similaire à traiter des jobs avec un processeur. Dans cette analogie, le nombre de paquets pour transmettre un message correspond au nombre d’unités d’exécution pour traiter un job.

Selon la terminologie usuelle [Buttazzo, 2011b], un job temps-réel est :
— souple, si accomplir le job en retard (= après sa deadline) peut malgré tout procurer de l’utilité au système, bien que l’utilité procurée soit dévaluée,
— ferme, si accomplir le job en retard est inutile pour le système, mais n’engendre pas de dommage,
— dur, si accomplir le job en retard peut engendrer des conséquences catastrophiques pour le système.

Si l’utilité que procure un job est indépendante de sa date d’accomplissement, le job est dit non temps-réel. Comme déjà discuté dans la Section 1, la transmission d’un message n’est pas critique d’un point de vue sûreté ; un message correspond à un job temps-réel souple ou ferme, mais pas dur. En accord avec le modèle introduit dans [Buttazzo, 2011a], nous caractérisons un job temps-réel Ji par un 5-uplet < ai , ci , vi , di , δi >, où :
— ai ∈ N est la date d’arrivée du job. Un job n’est pas instancié avant sa date d’arrivée ; un job ne peut donc pas être traité avant sa date d’arrivée. Un algorithme non-clairvoyant n’est pas conscient d’un job avant sa date d’arrivée.
— ci ∈ N, ci > 0 est le nombre d’unités d’exécution qu’il faut traiter pour que le job soit accompli. C’est une valeur entière, qui correspond à la transmission de paquet sur le réseau, un évènement que nous supposons être atomique.
— vi ∈ R + est l’utilité de base d’un job.
— di ∈ N est la limite de temps ferme (relative) du job.
— δi ∈ N est le retard limite du job.

Table des matières

I Introduction générale
1 Motivation, contexte, et problématique
1.1 Comment améliorer les systèmes de transport ?
1.2 Projet eHorizon
1.3 Nécessité d’optimiser le flux de données des véhicules vers le Cloud
1.4 Problématique
2 Objectifs de la recherche et décomposition du problème
2.1 Hypothèses initiales
2.2 Décomposition du problème
3 Contributions
3.1 Algorithme d’ordonnancement en-ligne embarqué dans les véhicules
3.2 Mécanisme d’Allocation Centralisé dans le Cloud
4 Structure du manuscrit
II Algorithme d’ordonnancement en-ligne embarqué dans les véhicules
1 Définition du problème
2 Modélisation
2.1 Problème à temps-réel souple
2.2 Méthode d’évaluation
2.3 Génération de scénarios
2.4 Modèle de simulation
3 Résultats et analyses
4 Travaux associés
III Mécanisme d’Allocation Centralisé dans le Cloud
1 Définition du problème
1.1 Modélisation des acteurs et de leurs intéractions
1.2 Non-soustractibilité des données
1.3 Exclusion à la consommation
2 Construction d’une famille de mécanismes à étudier
2.1 Formalisme préliminaire
2.2 Règles d’inclusion
2.3 Règles de redistribution
2.3.1 Paiement minimal d’un agent pour la règle d’inclusion NE
2.3.2 Paiement minimal d’un agent pour la règle d’inclusion 1HB
2.3.3 Paiement minimal d’un agent pour la règle d’inclusion MCT
2.3.4 Synthèse
2.4 Mécanismes populaires qui s’inscrivent dans notre modèle
2.4.1 First-Price Sealed-Bid Auctions with a Reservation Price (FPSBARP)
2.4.2 Provision-Point-Mechanism (PPM)
2.4.3 Equal Cost Sharing with Maximal Participation (ECSMP)
3 Moyen d’analyse
3.1 Choix de l’approche ACE
3.2 Principe de l’apprentissage multi-agents
3.3 Modèle de l’environnement multi-agents
3.4 Mise en œuvre de l’algorithme d’apprentissage
4 Résultats
4.1 Mécanismes de provision évalués
4.2 Paramètres et analyses
4.3 Processus de génération des résultats
4.4 Critères d’évaluation
4.5 Analyse de sensibilité au degré de compatibilité des besoins
4.6 Analyse de sensibilité au niveau d’équilibre des apports
5 Travaux associés
5.1 Travaux qui nous ont fortement inspirés
5.2 Travaux qui utilisent une méthodologie similaire à la nôtre
IV Conclusion générale

Lire le rapport complet