Scheduling algorithms for time-constrained big-file transfers in the Internet of Vehicles

In order to transfer large files and provide high-quality services in the IoV (Internet of Vehicles), intelligent routing and scheduling are indispensable for fast transfers and efficient network utilization, particularly when multi-path routing is allowed in the wired-transfer. Thus, a network administrator must select a set of feasible paths over which the transfer can be conducted. We consider a TBTS (Time-constrained Big-file Transfer Scheduling) problem in this paper. We prove that TBTS problem is NP-hard and that the TBTS problem can be solved by addressing a corresponding maximum ow over time problem with multi-path routing technique. We then propose both a heuristic algorithm (TBTS-H) and an exact algorithm (TBTS-A) to solve the TBTS problem. Although both of the proposed approaches can solve the TBTS problem, the heuristic runs more efficiently by trading accuracy for delay, while the exact algorithm can achieve high accuracy for delay, at the cost of increased running-time. The corresponding simulation results illustrate this trade-off. Additionally, we conduct some comparisons between our proposed approaches and a traditional single-path routing scheme.