As demand continues to grow, edge servers are increasingly constrained by their limited com-puting resources. In addition, large-scale deployment of edge servers will inevitably lead to unnecessary waste of resources. To further expand the resources of Vehicular Edge Computing, in this paper, we point out that the idle resources of parked vehicles can be integrated to assist edge servers in processing ofload tasks and propose a computing ofloading framework for parking cluster collaboration. In this framework, the computing task of each vehicle is composed of multiple subtasks that have dependencies between each other. To eficiently manage hetero-geneous resources in the framework, a layered ofloading method based on deep reinforcement learning is proposed to minimize the average completion time of all vehicles. Simulation results show that the proposed method has better performance than the other three baseline methods in terms of task processing time and task execution success rates.
In Vehicular Edge Computing, due to the very limited computing and storage resources, vehicles
are often unable to process some computationally intensive and latency-sensitive intelligent
applications locally, such as digital twins, augmented reality, etc. [
Considering that idle computing resources near vehicles are ubiquitous and do not require
additional deployment, some scholars have studied the use of neighboring vehicles to expand
the capabilities and service scope of edge computing. Some works [
However, the scenarios considered in the above research on parking vehicle-assisted edge computing are too idealistic, and the main scenario considered is the collaborative ofloading problem between a single edge server and multiple unassociated parked vehicles. In addition, the dependencies of subtasks are not taken into account, which limits the potential of parallel processing in edge computing and makes it dificult to meet the needs for low-latency services. In the face of the shortcomings and challenges of existing research, the main contributions of this work are summarized as follows: • We propose to integrate parked vehicles into parking clusters and design a dependent task computation ofloading framework for multiple parking clusters to collaborate with a single edge server. • We propose a deep reinforcement learning algorithm based on a multi-actor and singlecritic network architecture to minimize the average completion time of the application. Guided by a single critic network, multiple actor networks eficiently divide the decision action space into two layers: the first layer determines the location of task execution (locally, on edge servers, or in parking clusters); the second layer selects the specific parked vehicle to execute the task. This approach not only reduces the action space that each actor network handles, but also significantly improves the overall performance and eficiency of the system.
The remainder of the paper is organized as follows: Section II shows the system model studied in this paper, including: scenario modeling, task modeling, computational modeling, and the formalization of the optimization objectives established in this paper. Section III introduces the Double Actor-Layered Deep Deterministic Policy Gradient (DALDDPG) algorithm. We first model the decision-making process of the scenario studied in this paper as a Markov decision process. Then, the network structure of the DALDDPG algorithm, the update method of each network, and the DALDDPG pseudocode are introduced. Section IV evaluates the efectiveness of the proposed algorithm by comparing it with existing algorithms. Finally, we conclude this paper in Section V.
As illustrated in Figure 1, we consider a computation ofloading scenario involving multi-parked vehicles, multi-task vehicles, and a single VEC server. To efectively manage the resources of parked vehicles and facilitate task cooperation among them, we group parked vehicles into multiple Parking Vehicle Clusters (PVC) and designate a Cluster Management Vehicle (CMV) within each cluster. The primary responsibility of the CMV is to maintain basic information about the vehicles within the cluster and report this information to the Road Side Unit (RSU) of its area via V2I communication regularly. Considering that the communication cost of the CMV with exterior entities is usually greater than its communication cost within the cluster, we do not consider the communication delay between the CMV and other vehicles within the cluster. Furthermore, the CMV is regarded as a bridge for the entire cluster to communicate with the exterior, responsible for accurately forwarding messages to the targeted parked vehicles.
We posit that there are M PVCs on the road, denoted as {| = 1, 2, ..., }. In each , there are parked vehicles, where ,1 represents the CMV of the -th PVC, and , represents the -th vehicle in the -th PVC. The computing resource set for the parked vehicles in each is represented as {,| = 1, 2, ..., }, where , signifies the CPU clock frequency of the -th vehicle in the -th PVC. Moreover, there are task vehicles on the road, which can either connect to the RSU in their coverage range through V2I to access the VEC server, or connect to the PVC through V2V.
In this paper, we model the dependent subtask relationships derived from the application , generated by vehicle , as = (, ). Here, = {|0, 1, ..., , + 1} represents the + 2 subtasks of . Specifically, 0 and +1 represent the virtual entry and exit subtasks of , respectively. These two virtual tasks are established to ensure that can start and end on vehicle . Each edge within the set denotes a dependency relationship between subtasks of . Specifically, an edge (, ) ∈ indicates that the result from must be transmitted to before can commence its execution. The tuple {, , , .} is defined to characterize the -th subtask of , where is the input data volume for , is the output data volume resulting from executing , represents the number of CPU cycles required to execute , and . is the maximum tolerable delay for .
The set of computing devices, available for ofloading services within the communication range of the task vehicle, is denoted by = {0, 1, ..., , + 1}, where 0 represents the task vehicle itself, 1 to represent PVCs, and +1 represents the VEC server. The decision variable , is used to indicate whether subtask is ofloaded to the computing device . This variable can be defined as follows: {︃0 if subtask is no ofoaded to device ,
1 if subtask is ofoaded to device .
The decision variable ,, indicates whether subtask is executed on parked vehicle , in PVC . This variable can be defined as follows: ,, = {︃0 if subtask is executed n on parked vehicle , in , 1 if subtask is executed on parked vehicle , in . (1) (2)
In this paper, we assume that the VEC server, parked vehicles, and local vehicles can only handle one subtask at a time and that each subtask can only be processed on a computing device.
When ,0 = 1, the task is executed locally. The local ready time, ,, for , is the time when all the predecessor tasks of have been executed and their results have been trans-mitted back to the local vehicle. , can be expressed as follows: , = m∈ax{ , + ,, } where is the set of all predecessor tasks of ; , refers to the completion time for on the designated computing device based on the ofloading decision; ,, is the time required to transmit the execution results of back to . When is ready locally, it may not immediately be scheduled for execution due to the need to account for local queuing execution times. The completion time of , when executed locally, is denoted as , and can be expressed as follows: (3) (4) (5) (6) (7) , = {,, ,} +
where , stands for the earliest possible scheduling time for the local execution of , and denotes the computing capacity of the local terminal.
When ,+1 = 1, the task is carried out on the VEC server. The transmission delay for vehicle , when uploading data to the VEC server, can be represented as: ,, =
2,
The ready time of on the VEC server, denoted as ,, comprises two components: the upload time for to the VEC server, and the time at which all precursor tasks of get completed and their results are delivered back. Therefore, , can be expressed as:
Once task is ready on the VEC server, it may not necessarily be immediately scheduled for execution due to the queuing execution time on the VEC server. The completion time of , when executed on the VEC server, is denoted as , and can be expressed as: , = {︀ ,, ,}︀ +
where , is the earliest possible scheduling time for on the VEC server, and denotes the computing capacity of the VEC server.
When , = 1 (where ̸= 0 and ̸= + 1), task is executed on the parked vehicle within PVC . The transmission delay for vehicle n, when uploading data to , can be represented as: ,,, =
,2
The ready time ,, for task on the parked vehicle within includes two parts: the time required to upload to PVC , and the time when all precursor tasks of have been completed and their results are delivered back. Therefore, ,, can be expressed as:
The actual completion time for subtask application , denoted as ,, based on the current ofloading decisions, can be expressed as: = ,I+1
, = ,0 , + ,+1 , + ∑︁ , ,, 1
The actual completion time for is the actual completion time of the virtual exit subtask +1 and can be represented as:
Once task is ready on the parked vehicle in , it may not immediately be scheduled for execution due to the queuing execution time on the parked vehicle. The completion time ,, of , when executed on the parked vehicle in , can be expressed as: {︃ ,, = ,,, ∑︁ ,,,, 1 }︃ + ,, ∑︀1 , where ,, denotes the earliest scheduling time for to be executed on the -th parked vehicle in , and , represents the computing capacity of the -th parked vehicle within PVC .
The main objective of this work is to minimize the average completion time of system applications under the condition that each task is completed within its maximum tolerable delay. The optimization problem is formulated as follows: where 1 stipulates that each task can only be executed on a single computing device, and 2 ensures that the actual completion time of each application and its respective subtasks remains within their maximum tolerable delay.
Given that the above optimization problem is a complex mixed integer linear programming problem, traditional optimization algorithms struggle to efectively solve. Moreover, to eficiently manage heterogeneous resources in proposed scenario, we propose a layered task ofloading scheduling algorithm based on deep reinforcement learning with a multi-actor and single-critic network. For this purpose, we first model the ofloading scheduling process for dependent tasks as a Markov Decision Process (MDP). Below, we provide the formal expressions for the state space, action space, and reward function in the MDP.
State. At time t, the Actor1 network in the first layer is responsible for ofloading the subtasks of application to either the local, a PVC, or the VEC server. The local state 1, observed by the Actor1 network includes four main components: the position of the CMV, the available computing resources of parked vehicles, the sequence of tasks that have already been scheduled, and the collection of task priority sequences. Therefore, 1, can be abstractly defined as follows: 2, = {︁1,, 2,, . . . , ,, . . . , ,}︁ (13) (15) (16) (17) 1, = { , , _, _} (14)
The Actor2 network of the second layer is responsible for ofloading the subtasks of application to specific parked vehicles for execution. The local state 2, observed by the Actor2 network includes three main parts: the computing resources available of the parked vehicles, the processing time required for tasks pending in the compute queue of the parked vehicle, and the set of task priority sequences. Therefore, 2, can be abstractly defined as follows: , = {︀ , , _}︀
2
Actions. In the layered action space, for task , the first layer action space 1, that the Actor1 network can take is represented as:
1, = {0,, 1,, . . . , ,, . . . , ,+1} where 1, determines the allocation layer level of task ; if 0, = 1, is executed locally; if ,+1 = 1, is executed on the VEC server; if , = 1 (where ̸= 0 and ̸= + 1), is executed on the -th PVC. Based on the decisions of the first layer, the second layer action space 2, that the Actor2 network can take is defined as:
specific parked vehicle, and if , = 1, is executed on the -th parked vehicle. where 2, specifies that, within the layer determined by 1,,task is further ofloaded to a Rewards. After executing the joint action , = {︁1,, 2,}︁ under the global state , = expressed as follows: {1, ∪ 2,},the Agent receives an immediate reward from the environment, which can be = (− 1:) − (− 1:+1) () where (_1:) denotes the time spent on the subgraph of tasks that have been scheduled under state ,, and () represents the delay when all scheduled tasks are executed locally.
The Double Actor-Layered Deep Deterministic Policy Gradient (DALDDPG) algorithm comprises six networks: the Actor1 network, 1(1| 1); the Actor2 network, 2(2| 2); and their respective target networks, 1′(1| 1′) and 2′(2| 2′). Additionally, it includes a Critic network, (, |), and a corresponding target network, ′(, |′). In the decision-making process, the Actor1 and Actor2 networks independently make first-layer and second-layer decisions based on their local states. The Agent subsequently combines these two decisions (1 , 2 ) into a joint decision, , which is then executed. Following this execution, the global state, , and local states, 1 and 2 , move to the next state and provide the Agent with an immediate reward, . Then the Agent stores the single set of experience (, , +1, ) from the interaction with the environment in the sample pool. During the training phase, a batch of samples is periodically drawn from the experience pool, and the − values for each sample are calculated through the target network, ′(, |′).
− = + ′(︀ ,, ,|′︀) where , = 1′(︀ 1 ,| 1′︀) ∪ 2′(︀ 2 ,|
2′︀) , and is the discount factor.
In this paper, we minimize the loss function () using gradient descent, based on the Temporal Diference algorithm, to update the weight parameter of the Critic. () can be expressed as follows: () = =1 1 ∑︁(︀ − − (, |))︀ 2 where represents the number of samples drawn from the sample pool.
Under the evaluation of the , we employ gradient ascent to update the parameters of the Actor1 and Actor2 networks. The policy gradients are expressed as follows: ∇ 1 = ∇ 2 = 1 ∑︁ (︁ =1 1 ∑︁ (︁ =1 ∇(, |)∇ 1 1︁( | 1
︁) 1 ∇(, |)∇ 2 2︁( | 2
︁) 2 (18) (19) (20) (21) (22)
To update the parameters of the target network, a soft update strategy is employed. The updates for all target networks are expressed as follows: ⎧ 1′ = 1 + (1 − ) 1′ ⎪ ⎨
2′ = 2 + (1 − ) 2′ ⎪⎩′ = + (1 − )′ where is the soft update coeficient.
Algorithm 1 DALDDPG algorithm (23)
We use Python 3.7 and TensorFlow 2.0 for simulations. The simulation scenario considers a
400-meter road populated with ∈ [
To evaluate the performance of the proposed strategy, we compare the following three ofloading strategies: • RS: Tasks are randomly assigned to be executed on the vehicle locally, on the VEC server, or on a parked vehicle; • HUDQN: Tasks are executed according to the ofloading decisions made in the first layer;
• SLDQN: The two-layer ofloading decisions are consolidated into a single-layer framework.
As depicted in Figure 2, as the number of training epochs increases, the rewards under various learning rates increase and stabilize. To balance convergence speed with system stability, we adopt a learning rate of 6 × 10− 4 for model training.
As shown in Figure 3, the average completion time of each strategy escalates with the increase in the number of applications, yet the proposed strategy consistently exhibits the lowest completion time. Compared to the other three strategies, our strategy reduces the average completion time by 11.47%, 25.41%, and 51.01% on average, respectively. Figure 4 shows that as the number of PVCs increases, the average completion time for each strategy decreases, with the proposed strategy performing the best. Compared to the other three strategies, the proposed strategy reduces the average completion time by 15.42% to 26.58% on average. As depicted in Figure 5, with rising task computational complexity, the task completion rates for all strategies gradually decrease, but the proposed strategy maintains the highest completion rate. Compared to the other three strategies, the proposed strategy enhances the completion rate by an average of 42.52%, 13.21%, and 4.21%, respectively. The above improvements are because the proposed strategy has considered well the heterogeneity of parked vehicle resources and adopted a layered task ofloading scheduling framework to optimize task allocation, which significantly improves the performance and eficiency of the system.
In this paper, we design a dependent task scheduling framework, which is composed of multiple parking clusters cooperating with a single edge server. In addition, we propose a deep reinforcement learning algorithm based on a multi-actor and single-critic network architecture to minimize the average completion time of the application. Simulation results show that the proposed algorithm has better performance than the other three baseline algorithms in terms of task processing time and task execution success rates. Future work will explore task ofloading and resource scheduling within a VEC system assisted by multi-parking clusters, while also considering the energy consumption cost of parked vehicles. of vehicles as the infrastructures, IEEE Transactions on Vehicular Technology 65 (2016) 3860–3873. [13] A. B. Reis, S. Sargento, O. K. Tonguz, Parked cars are excellent roadside units, IEEE
Transactions on Intelligent Transportation Systems 18 (2017) 2490–2502. [14] A. J. Kadhim, J. I. Naser, Proactive load balancing mechanism for fog computing supported by parked vehicles in iov-sdn, China Communications 18 (2021) 271–289. [15] X.-Q. Pham, T. Huynh-The, E.-N. Huh, D.-S. Kim, Partial computation ofloading in parked vehicle-assisted multi-access edge computing: A game-theoretic approach, IEEE Transactions on Vehicular Technology 71 (2022) 10220–10225. [16] C. Ma, J. Zhu, M. Liu, H. Zhao, N. Liu, X. Zou, Parking edge computing: Parked-vehicleassisted task ofloading for urban vanets, IEEE Internet of Things Journal 8 (2021) 9344– 9358. [17] H. Zhao, J. Hua, Z. Zhang, J. Zhu, Deep reinforcement learning-based task ofloading for parked vehicle cooperation in vehicular edge computing, Mobile Information Systems 2022 (2022) 9218266.