Journal of Communications and Information Networks, Vol.2, No.2, Jun. 2017
DOI: 10.1007/s41650-017-0027-5
c
Posts & Telecom Press and Springer Singapore 2017
Special Issue on Internet of Vehicle
Research paper
Scheduling algorithms for time-constrained big-
file transfers in the Internet of Vehicles
Chuan Lin
1
, Yuanguo Bi
1
*
, Hai Zhao
1
, Zeshen Wang
2
, Jinfa Wang
1
1. School of Computer Science and Engineering, Northeastern University, Shenyang 110819, China
2. School of Business Administration, Northeastern University, Shenyang 110819, China
* Corresponding author, Email: biyuanguo@ise.neu.edu.cn
Abstract: 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 flow 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.
Keywords: Internet of Vehicles, wired-transfer, time-constrained, big-file, scheduling, multi-path routing
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Citation: C. Lin, Y. G. Bi, H. Zhao, et al. Scheduling algorithms for time-constrained big-file transfers in
the Internet of Vehicles [J]. Journal of communications and information networks, 2017, 2(2): 126-135.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1 Introduction
People are spending more time in vehicles than ever
before. There is also a rapidly increasing number
of users in vehicles accessing the Internet through
IP-enabled smart devices. They are eager to en-
joy high quality services through the IoV
[1,2]
, such
as high-definition video streaming, data uploading
and downloading, and driving data recording. Ex-
tremely large data files, frequently called “big-file”,
are generated by applications in IoV. Reliable and
flexible file transfer is critical for supporting these
applications. Additionally, some applications may
require files to be delivered within a short time
constraint. For example, timely delivery of high-
definition video streams to users is critical for achiev-
ing high QoS (Quality of Service)
[3,4]
. As shown
in Fig. 1, file transfer in IoV includes vehicle-to-
infrastructure transfer, vehicle-to-vehicle transfer,
i.e., wireless-transfer and wired-transfer over the In-
ternet. Wired-transfer in IoV is more important than
wireless-transfer because bandwidth is more easily
exhausted as users continue to frequently request
data from remote servers over the Internet. In or-
der to maintain high QoS during wired-transfer, a
network administrator is required to compute feasi-
ble potential paths based on network topology, allo-
cate link bandwidth for each application, and sched-
Manuscript received Mar. 14, 2017; accepted Apr. 24, 2017
This work is supported by the National Natural Science Foundation of China (Nos. 61671142, 61101121, 61373159).