Introduction
This work, “LARS: A Latency-aware and Real-time Scheduling Framework for Edge-enabled Internet of Vehicles,” was accepted by the IEEE Transactions on Service Computing (TSC) in August 2021. The main content of the paper includes:
-
By analyzing real traffic datasets, the feasibility of forming vehicle clusters (Herd) in Edge Internet of Vehicles (IoV) has been verified, providing strong practical conditions and basis for the design of the LARS platform.
-
A framework for Edge IoV, LARS, has been designed to manage the Herd within the coverage area of the Edge IoV. Based on the vehicle’s mobility and resource status, a clustering algorithm GetHerds is proposed to generate vehicle resource clusters Herds to coordinate computing service provision; a task scheduling algorithm GBTSA is proposed to offload tasks, aiming to minimize the total delay of tasks and maximize the resource utilization of Herd.
-
Based on real vehicle trajectory data, simulations validate that the GetHerds algorithm can generate stable Herd to provide computing services for users; two case experiments based on a Testbed show that the proposed GBTSA performs well in reducing task delay and maximizing resource utilization.
01
—
Research Background
With the development of the Internet of Things (IoT) and mobile computing, the explosive growth of latency-sensitive applications has posed higher computational demands on mobile devices. Powerful onboard computers, high-capacity storage, and more advanced communication module configurations make future vehicles smarter. Today, offloading application computation to Edge IoV has become an effective solution. Without deploying additional servers, Edge IoV can effectively alleviate network congestion during peak times.
However, existing research mostly assumes that edge vehicle clusters can be easily formed in real environments, neglecting their feasibility in practice. In previous studies of application computation offloading, most applications are simulated as single tasks or multiple unrelated tasks. However, in real applications, the data relationships between tasks cannot be ignored. For example, in target recognition applications, the target detection task can only proceed after the feature extraction task is completed. Therefore, this paper proposes a scheduling framework LARS for Edge IoV that can generate stable Herd to provide computing and achieve real-time scheduling of tasks for users.
02
—
Data Analysis and System Model
First, the traffic trajectory dataset of Shenzhen City was analyzed. This dataset covers the traffic trajectory data of over 10,000 taxis within a 24-hour period on October 22, 2013, collected every 30 seconds. The statistical results indicate that the peak hours of the day are from 18:00 to 20:00, when the number of active vehicles is the highest, as this period coincides with the end of work and nightlife peak. Moreover, during this time, mobile users in real life also generate numerous application requests. Therefore, resources from the clustering of moving vehicles on the road can be utilized to handle application requests. Then, the time period from 18:00 to 18:05 was selected to statistically analyze the hotspot areas of vehicle clustering. As shown in Figure 1, many traffic flow hotspot areas can be observed throughout the city. In this study, a vehicle belongs to an Edge IoV system within a time period, contributing its idle virtualized resources.
Figure 1: City Traffic Flow Hotspot Map
Then, this study considers a scenario of an Edge IoV system as shown in Figure 2, where all vehicles equipped with powerful edge servers form an IoV system within the communication range of the controller (BS or RSU). Different vehicles can aggregate into different Herd, forming an IoV with edge computing capabilities. Each vehicle is regarded as a computing worker in the Herd. The controller is responsible for information collection, resource coordination, and task scheduling among vehicles in the Edge IoV.
Figure 2: Edge IoV System Model
03
—
LARS Framework Design
LARS can periodically form Herd to dynamically provide computing services for latency-sensitive applications. The main components include applications generated by mobile users and Herd composed of moving vehicles. During high traffic flow periods, when the computing demand of users approaches the load of the controller, the controller periodically schedules vehicles within the driving range of the Edge IoV to form multiple Herd to collaboratively provide computing services for mobile users, as shown in Figure 3.
Figure 3: LARS Framework Design
-
Control Center:The controller periodically collects mobility and resource status information of all vehicles. Mobility status information includes location, current speed, and trajectory based on GPS navigation systems. Resource status information indicates the available resources and available time of vehicles.
-
Applications: In LARS, applications from mobile users need to be divided into multiple tasks to generate a task dependency graph. Due to the characteristics of different tasks and the actual environment, acceleration evaluation needs to be conducted before task offloading. Then, the offloading controller submits a job consisting of a set of tasks to LARS via the user API. The job allocator selects the most suitable Herd based on the information of the offloaded job. Then, the task scheduler calls resource services via internal API to provide optimal task allocation messages.
-
Herd Generator:Considering that the available resources and available time of each vehicle are different, to coordinate vehicle resources to provide services for users, we form Herd with vehicles that have similar resource status and close mobility status, maximizing vehicle resource utilization while minimizing task failure and migration rates. This paper uses the classic clustering algorithm K-means to generate Herd.
-
Offloading Controller:Before task offloading, a computing acceleration evaluator is designed to assess whether it is necessary to offload each task in the application partition. Computing acceleration refers to the acceleration of task processing delays.
-
Job Scheduler:In an Edge IoV, the controller manages several Herds. The differences in computing resources and available time among different Herd require the controller to make trade-offs when assigning jobs to the appropriate Herd. This paper assumes that each job is committed to finding the Herd with the highest computing acceleration and lowest cost for processing.
-
Task Scheduling:The task scheduling problem in a dynamic environment is an NP-hard problem, making it difficult to obtain optimal solutions. This paper proposes a task scheduling algorithm GBTSA based on greedy principles, aiming to schedule tasks to appropriate workers and order tasks on each worker to minimize job delays while maximizing resource utilization of Herd.
04
—
Performance Evaluation
Figure 4: LARS System Implementation
-
Case Study: Scene Understanding
Figure 5: Average Response Time Under Different Algorithms
From the perspective of application jobs, the proposed GBTSA aims to minimize the total delay of offloaded jobs. Figure 5 shows the results of 20 jobs under five algorithms, namely GBTSA, local computation, random scheduling, STTF, and SQLF. It can be observed from Figure 5 that generally, the response time of jobs under GBTSA is the lowest, followed by SQLF and STTF, while the response time of jobs under random scheduling and local computation is the highest.
Figure 6: Average Number of Service Workers Under Different Algorithms
05
—
Conclusion
This paper designs a dynamic scheduling framework LARS. In LARS, a k-means-based clustering algorithm GetHerds is proposed to generate Herd. For offloaded jobs, the job allocator in the controller first selects the appropriate Herd, and then uses a greedy-based task scheduling algorithm GBTSA to schedule tasks to appropriate workers and order tasks on each worker. Experimental results show that LARS can generate stable Herd to provide computing services for users; at the same time, GBTSA performs well in reducing the total delay of jobs and maximizing the resource utilization of Edge IoV.
Paper Address:
Citation Format:
Shihong Hu, Guanghui Li, and Weisong Shi. “LARS: A Latency-aware and Real-time Scheduling Framework for Edge-enabled Internet of Vehicles.” IEEE Transactions on Services Computing, Aug 2021.
Laboratory Homepage:http://thecarlab.org/
