Decomposition Theory Meets Reliability Analysis: Processing of Computation-Intensive Dependent Tasks Over Vehicular Clouds With Dynamic Resources

Vehicular cloud (VC) is a promising technology for processing computation-intensive applications (CI-Apps) on smart vehicles. Implementing VCs over the network edge faces two key challenges: (C1) On-board computing resources of a single vehicle are often insufficient to process a CI-App; (C2) The dynamics of available resources, caused by vehicles' mobility, hinder reliable CI-App processing. This work is among the first to jointly address (C1) and (C2), while considering two common CI-App graph representations, directed acyclic graph (DAG) and undirected graph (UG). To address (C1), we consider partitioning a CI-App with m dependent (sub-)tasks into k = m groups, which are dispersed across vehicles. To address (C2), we introduce a generalized reliability metric called conditional mean time to failure (C-MTTF). Subsequently, we increase the C-MTTF of dependent sub-tasks processing via introducing a general framework of redundancy-based processing of dependent sub-tasks over semi-dynamic VCs (RP-V(C)over cap). We demonstrate that RP-VC can be modeled as a non-trivial semi-Markov process (SMP). To analyze this SMP model and its reliability, we develop a novel mathematical framework, called event stochastic algebra ((sic)e(sic)-algebra). Based on (e)-algebra, we propose decomposition theorem (DT) to transform the presented SMP to a decomposed SMP (D-SMP). We subsequently calculate the C-MTTF of our methodology. We demonstrate that (sic)e(sic)-algebra and DT are general mathematical tools that can be used to analyze other cloud-based networks. Simulation results reveal the exactness of our analytical results and the efficiency of our methodology in terms of acceptance and success rates of CI-App processing.

Automated summary

Vehicular cloud is a promising technology for processing computation-intensive applications on smart vehicles. This work addresses the challenges of insufficient computing resources and dynamic resource availability caused by vehicle mobility in implementing vehicular clouds. A general reliability metric and a redundancy-based processing framework are introduced to improve the reliability of CI-App processing. A mathematical framework called event stochastic algebra is developed to analyze the reliability of the proposed methodology. Simulation results demonstrate the accuracy and efficiency of the proposed methodology in CI-App processing.