On Optimal Scheduling of OTA Software Updates for Smart Vehicles Leveraging Fog Computing

摘要

Recently, the problem of optimal resource scheduling for the increasingly growing number of smart vehicles has emerged as a daunting research challenge. While Over the Air (OTA) software updates are critical for the safe routing/driving of smart vehicles, they consume precious network resources if not planned or scheduled appropriately. In this paper, we consider a smart fog computing network to serve the smart vehicles with OTA updates and present two optimal resource scheduling problems $SP_{1}$ and $SP_{2}$. The objective of $SP_{1}$ is to minimize the maximum waiting time of any smart vehicle and the objective of $SP_{2}$ aims to minimize the maximum transmission time of any channel. These problems cannot always ascertain optimal solutions in polynomial time. We first propose a random algorithm and a greedy algorithm for these problems and find that these two algorithms may not perform adequately in many cases. Hence, we propose a local search algorithm which takes any feasible solution of a scheduling problem as input and improves that solution. Computer-based simulations demonstrate the effectiveness of our proposed algorithms.