Abstract

Probabilistic model checking mainly concentrates on techniques for reasoning about the probabilities of certain path properties or expected values of certain random variables. For the quantitative system analysis, however, there is also another type of interesting performance measure, namely quantiles. A typical quantile query takes as input a lower probability bound p and a reachability property. The task is then to compute the minimal reward bound r such that with probability at least p the target set will be reached before the accumulated reward exceeds r. Quantiles are well-known from mathematical statistics, but to the best of our knowledge they have not been addressed by the model checking community so far. In this paper, we study the complexity of quantile queries for until properties in discrete-time finite-state Markov decision processes with non-negative rewards on states. We show that qualitative quantile queries can be evaluated in polynomial time and present an exponential algorithm for the evaluation of quantitative quantile queries. For the special case of Markov chains, we show that quantitative quantile queries can be evaluated in time polynomial in the size of the chain and the maximum reward. Document type: Part of book or chapter of book

Abstract

Technological advancements made it possible for Electric vehicles (EVs) to have onboard computation, communication, storage, and sensing capabilities. Nevertheless, most of the time these EVs spend their time in parking lots, which makes onboard devices cruelly underutilized. Thus, a better management and pooling these underutilized resources together would be strongly recommended. The new aggregated resources would be useful for traffic safety applications, comfort related applications or can be used as a distributed data center. Moreover, parked vehicles might also be used as a service delivery platform to serve users. Therefore, the use of aggregated abundant resources for the deployment of different local mobile applications leads to the development of a new architecture called Vehicular Fog Computing (VFC). Through VFC, abundant resources of vehicles in the parking area, on the mall or in the airport, can act as fog nodes. In another context, mobile applications have become more popular, complex and resource intensive. Some sophisticated embedded applications require intensive computation capabilities and high-energy consumption that transcend the limited capabilities of mobile devices. Throughout this work, we tackle the problem of achieving an effective deployment of a VFC system by aggregating unused resources of parked EVs, which would be eventually used as fog nodes to serve nearby mobile users’ computation demands. At first, we present a state of the art on EVs and resource allocation in VFC. In addition, we assess the potential of aggregated resources in EVs for serving local mobile users’ applications demands by considering the battery State of Health (SOH) and State of Charge (SOC). Here, the objective is to choose EVs with a good condition of SOH and SOC so that owners secure tolerable amount of energy for mobility. Then, we address the problem of resource allocation scheme with a new solution based on Markov Decision Process (MDP) that aims to optimize the use of EVs energy for both computing users’ demands and mobility. Hence, the novelty of this contribution is to take into consideration the amount of aggregated EVs resource for serving users’ demands. Finally, we propose a stochastic theoretical game approach to show the dynamics of both mobile users’ computation demands and the availability of EVs resources.; Résumé : Les progrès technologiques ont permis aux véhicules électriques d’avoir des capacités à la fois de calcul, de communication, de stockage et de perception. Néanmoins, la plupart du temps, ces véhicules électriques sont en stationnement, ce qui engendre une sous utilisation de leurs capacités embarquées. Ainsi, une meilleure gestion et une mise en commun de ces ressources sous-utilisées deviennent fortement recommandées. Les ressources agrégées seraient utiles pour des applications de sécurité routière, des applications liées au confort ou pourraient même être utilisées en tant que centre de calcul distribué. En outre, les véhicules en stationnement pourraient également être utilisés comme plate-forme de fourniture de services. Par conséquent, l’utilisation de ressources abondantes agrégées pour le déploiement de différentes applications mobiles locales a conduit au développement du concept d’informatique en brouillard véhiculaire (an anglais, Vehicular Fog Computing - VFC). Grâce à ce dernier, les véhicules dans les aires de stationnement, les centres commerciaux ou les aéroports vont agir en tant que nœuds fog. Dans un autre contexte, les applications mobiles sont devenues de plus en plus populaires, complexes et gourmandes en ressources. Certaines applications mobiles nécessitent des capacités de calcul intensives et une consommation d'énergie élevée qui transcendent les capacités limitées des appareils mobiles. Tout au long de ce travail, nous abordons les verrous liés au déploiement efficace d’un système VFC agrégeant les ressources inutilisées des véhicules électriques en stationnement pour être utilisées comme nœuds fogs répondants aux demandes de calcul des utilisateurs mobiles à proximité. Notre travail commence par un état de l'art sur les véhicules électriques et l'allocation de ressources dans le système VFC. En outre, nous évaluons le potentiel des ressources agrégées dans les véhicules électriques pour répondre aux demandes d'applications d'utilisateurs mobiles locaux en prenant en compte l'état de santé de la batterie (en anglais, State of Health - SOH) et son état de charge (en anglais, State of Charge - SOC). Notre objectif est de choisir des VEs ayant un état de santé et de charge satisfaisants pour faire partie du VFC tout en permettant aux propriétaires de ces véhicules de disposer d’une quantité d’énergie suffisante pour leur mobilité. Nous abordons, par la suite, le problème d’allocation de ressources avec une nouvelle solution basée sur le processus de décision Markovien (en anglais, Markov Decision Process - MDP) qui vise à optimiser l’utilisation de l’énergie des véhicules électriques pour répondre à la fois à aux demandes de calcul et de mobilité des utilisateurs. Enfin, nous proposons une approche basée sur un jeu stochastique pour montrer la dynamique de la demande de calcul des utilisateurs mobiles et la disponibilité des ressources des véhicules électriques.