Toward Effective Service Scheduling for Human Drivers in Vehicular Cyber-Physical Systems

Abstract

It is essential to consider drivers' perceptions and reactions when building Vehicular Cyber-Physical Systems (VCPS) since the effectiveness and efficiency of VCPS will largely depend on how drivers could benefit from such a system. This paper considers, for the first time, novel service scheduling problems from a Human Factors (HF) standpoint by taking into consideration the following fact: a driver may not be able to receive more than one service in a short period of time, even if multiple services can be transmitted to the driver from the conventional communications and networking standpoint. We study a family of the HF-aware Service Scheduling (HFSS) Problems, where the goal is to deliver up to n services, each having a time-dependent (and possibly decreasing) utility to a subset of intended drivers so as to minimize the system-wide total utility loss due to unsuccessful delivery of some services. We show that such problems are different from all existing problems. We formulate the basic HFSS problem (BHFSSP) using Integer Linear Programming (ILP) and prove its NP-Completeness. We then propose efficient heuristics for BHFSSP and its more general versions, and present numerical results from large-scale test cases. We also address several practical issues related to wireless transmission failures, distributed implementation in the multisender scenario, and other HF related considerations.