Task Replication for Deadline-Constrained Vehicular Cloud Computing: Optimal Policy, Performance Analysis, and Implications on Road Traffic
- 9 November 2017
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Internet of Things Journal
- Vol. 5 (1) , 93-107
Abstract
In vehicular cloud computing (VCC) systems, the computational resources of moving vehicles are exploited and managed by infrastructures, e.g., roadside units, to provide computational services. The offloading of computational tasks and collection of results rely on successful transmissions between vehicles and infrastructures during encounters. In this paper, we investigate how to provide timely computational services in VCC systems. In particular, we seek to minimize the deadline violation probability given a set of tasks to be executed in vehicular clouds. Due to the uncertainty of vehicle movements, the task replication methodology is leveraged which allows one task to be executed by several vehicles, and thus trading computational resources for delay reduction. The optimal task replication policy is of key interest. We first formulate the problem as a finite-horizon sampled-time Markov decision problem and obtain the optimal policy by value iterations. To conquer the complexity issue, we propose the balanced-task-assignment (BETA) policy which is proved optimal and has a clear structure: it always assigns the task with the minimum number of replicas. Moreover, a tight closed-form performance upper bound for the BETA policy is derived, which indicates that the deadline violation probability follows the Rayleigh distribution approximately. Applying the vehicle speed-density relationship in the traffic flow theory, we find that vehicle mobility benefits VCC systems more compared with road traffic systems, by showing that the optimum vehicle speed to minimize the deadline violation probability is larger than the critical vehicle speed in traffic theory which maximizes traffic flow efficiency.Keywords
All Related Versions
Funding Information
- Nature Science Foundation of China (61701275, 91638204, 61571265, 61621091)
- China Post-Doctoral Science Foundation
- Intel Collaborative Research Institute for Mobile Networking and Computing
This publication has 40 references indexed in Scilit:
- Vehicle as a resource (VaaR)IEEE Network, 2015
- Large-scale antenna systems with hybrid analog and digital beamforming for millimeter wave 5GIEEE Communications Magazine, 2015
- A survey on vehicular cloud computingJournal of Network and Computer Applications, 2014
- The tail at scaleCommunications of the ACM, 2013
- Queueing systems with hard delay constraints: a framework for real-time communication over unreliable wireless channelsQueueing Systems, 2012
- Taking VANET to the cloudsInternational Journal of Pervasive Computing and Communications, 2011
- Job replication on multiserver systemsAdvances in Applied Probability, 2009
- Calibration of Microscopic Traffic Simulation Models with Aggregate DataTransportation Research Record: Journal of the Transportation Research Board, 2004
- Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time DisciplineOperations Research, 1968
- Car following models and the fundamental diagram of road trafficTransportation Research, 1967