Patent ID: 11886993
Assignee: BEIJING UNIVERSITY OF POSTS AND TELECOMMUNICATIONS
Field: Computer technology (Electrical engineering)
Classification: CPC G | IPC G

Claim 0:
1. A method for task scheduling based on deep reinforcement learning, comprising:
obtaining multiple target subtasks to be scheduled; wherein, the multiple target subtasks are subtasks obtained by performing subtask division processing on a target task, which is a to-be-executed data processing task for a target vehicle;
building target state data corresponding to the multiple target subtasks, wherein the target state data comprises a first set, a second set, a third set, and a fourth set;
the first set represents the number of CPUs required when each of the target subtasks is executed, the second set represents a data amount and storage location of data required when each of the target subtasks is executed, the third set represents current remaining execution time of an assigned task in each of target nodes, and the fourth set represents a CPU clock frequency of each of the target nodes; the target nodes are nodes for executing the target task in Internet of Vehicles;
inputting the target state data into a pre-trained task scheduling model, to obtain a scheduling result of each of the target subtasks; wherein, the scheduling result of each of the target subtasks comprises a probability that the target subtask is scheduled to each of the target nodes; and
for each of the target subtasks, determining a target node to which the target subtask is to be scheduled based on the scheduling result of the target subtask, and scheduling the target subtask to the determined target node;
wherein, the task scheduling model is a model obtained by training a preset deep neural network through training samples; the training samples comprise sample state data and decision actions corresponding to multiple sample subtasks; the multiple sample subtasks are subtasks obtained by performing the subtask division processing on a sample task related to vehicles which have been executed; each of the decision actions is an action corresponding to each of the sample subtasks during execution; the action corresponding to each of the sample subtasks is to schedule this sample subtask to a sample node, which is a node for executing the sample task in the Internet of Vehicles,
wherein the deep neural network is a network using an Asynchronous Advantage Actor-Critic (A3C) algorithm;
a process of training the task scheduling model comprises:
acquiring actual scheduling data about the sample task when the sample task is executed at multiple target moments;
assigning values to a preset state space s and a preset action space a based on the acquired actual scheduling data, to obtain sample state data St and decision actions at corresponding to the multiple sample subtasks of the sample task at each of the target moments;
training the deep neural network by at least using the sample state data St, the decision actions at, a preset reward function and a preset loss function, to obtain the task scheduling model;
wherein, the state space S={Ftask, L, T, Fnode}; Ftask, L, T and Fnode are all sets; Ftask represents the number of CPUs required when each of the sample subtasks is executed, L represents a data amount and storage location of data required when each of the sample subtasks is executed, T represents remaining execution time of an assigned task in each of sample nodes, and Fnode represents a CPU clock frequency of each of the sample nodes; the action space a is a set comprising decision actions corresponding to the multiple sample subtasks;
wherein, the reward function is a function for setting a reward to minimize average execution time; the loss function is a function for calculating a sum of a first type of loss and a second type of loss; the first type of loss is an average loss of Actor networks, and the second type of loss is a loss of a Critic network,
wherein the deep neural network comprises an input layer, a shared sub-network and an output sub-network that are connected in series;
wherein, the sample state data is input into the input layer;
the shared sub-network comprises multiple fully connected layers connected in series;
the output sub-network comprises multiple first branch sub-networks and one second branch sub-network which are parallel sub-networks; each of the first branch sub-networks is used as one Actor network to predict a scheduling result of one sample subtask, and the second branch sub-network is used as a Critic network to calculate a reward value of the sample state data; and
each of the first branch sub-networks comprises at least one fully connected layer and one softmax output layer, and the second branch sub-network comprises at least one fully connected layer and one linear output layer,
wherein the loss function is:

L(θ1,θ2, . . . ,θi, . . . ,θM,θv)=(Σi=1MLactor(θi))/M+Lcritic(θv)

wherein, L(θ1, θ2, . . . , θi, . . . , θM, θv) is a loss value of the deep neural network, M is the number of first branch sub-networks to be trained, θ1, θ2, . . . , θi, . . . , θM are network parameters of M first branch sub-networks, θi is a network parameter of the i-th first branch sub-network, and θv is a network parameter of the second branch sub-network;
wherein Lactor(θi) is a loss function of the i-th first branch sub-network:

Lactor(θi)=log πi(at,i|st;θi)(Rt−V(st;θv))+βH(πi(st;θi))

wherein, πi(at,i|st; θi) is a probability of outputting an action at,i by the i-th first branch sub-network, πi(st; θi) is a probability distribution of outputting actions by the i-th first branch sub-network H(πi(st; θi)) is an entropy of the probability distribution, β is a parameter for controlling an intensity of entropy regularization term, the action at,i is an action corresponding to the i-th sample subtask in the decision actions at, and each of the actions outputted by the i-th first branch sub-network is an action of scheduling the i-th sample subtask to each of the sample nodes;
H(πi(st; θi)) is calculated by a formula:, H
    ⁡
    
      (
      
        
          π
          i
        
        ⁡
        
          (
          
            
              s
              t
            
            ;
            
              θ
              i
            
          
          )
        
      
      )
    
  
  =
  
    -
    
      
        ∑
        
          j
          =
          1
        
        N
      
      ⁢
      
        
          p
          ⁡
          
            (
            
              a
              
                t
                ,
                i
              
              j
            
            )
          
        
        ⁢
        
          log
          ⁡
          
            (
            
              2
              ,
              
                p
                ⁡
                
                  (
                  
                    a
                    
                      t
                      ,
                      i
                    
                    j
                  
                  )
                
              
            
            )
          
        
      
    
  

wherein, p(at,ij) is a probability of outputting an action j by the i-th first branch sub-network at a moment t; N is the number of the sample nodes; and the action j is an action of scheduling the i-th sample subtask to a sample node j;
Lcritic(θv) is the loss function of the second branch sub-network:

Lcritic(θv)=(Rt−V(si;θv))2 

wherein Rt is a cumulative reward of at, and V(si; θv) is a reward value output by the second branch sub-network,
Rt is calculated by a formula:, R
    t
  
  =
  
    
      ∑
      
        k
        =
        0
      
      ∞
    
    ⁢
    
      
        γ
        k
      
      ⁢
      
        r
        
          t
          +
          k
        
      
    
  

γ∈[0,1] is a preset discount factor, and rt+k is a reward value in the state represented by the sample state data St+k.