# Task Migration with Partitioning for Load Balancing in Collaborative Edge Computing
## 2 System Model and Problem Formulation  
The MEC system proposed in this paper is shown in Figure 1. We consider a MEC system comprising a set of MECSs, \(M\), located in roadside units (RSUs) and a set of vehicles, \(N\). A MECS can provide seamless communication and computing service coverage for vehicles on the road. We assume that the MECSs communicate with each other through wired links, so communication latency and bandwidth can be ignored [20; 23]. Each MECS uses two queues: a waiting queue and computation queue. The waiting queue uses a limited task buffer to accommodate tasks offloaded from vehicles, and the computation queue operates in a first-in-first-out manner to process tasks. A MECS controller acts as a centralized controller with global knowledge of the MECSs in a system and is responsible for making the decisions for migration and partitioning. Time is divided into slots \(t\), and each time slot has an equal duration of \(\Delta s\). We assume that the vehicle travels at speed \(s\) during the simulation. Figure 1: The architecture of the proposed MEC system. During each time slot, vehicle \(n\) offloads its task in which the data size is \(\lambda_{n}\) (in bits), the computation workload is \(\eta_{n}\) (in CPU cycles), and the delay constraint is \(T_{n}^{max}\), which can be divided into several interdependent subtasks. The dependency among subtasks is modeled by a DAG, i.e., \(\mathcal{G}(\mathcal{V},\ \mathcal{E})\), where \(\mathcal{V}\) is the set of dependent subtasks in task \(n\) and \(\mathcal{E}\) is the set of dependencies between the subtasks in task \(n\). Each subtask \(i\) in task \(n\) is associated with a computation workload \(\eta_{n,i}\). In this paper, we only consider the tree-structured task graph, where the out-degree of each vertex is equal to 1, except for that of the first vertex. The first and last subtasks compute at the serving MECS, to complete the first subtask and migrate other subtasks simultaneously [18], and to gather and transmit computing results at the end of the service session [13]. For example, in an autonomous driving application, recognizing a situation can be the first subtask and driving guidance can be the last subtask. We assume that at the beginning of each time slot \(t\), a vehicle offloads its tasks to the serving MECS, giving it the highest signal, as MECS \(m\). The MECS receives the task offloaded from the vehicle, then the task is placed at the waiting queue of the MECS to be partitioned and migrated. At the end of time slot \(t\), the MECS controller gathers the status information from the MECSs in the system. Based on the information, the MECS controller makes a decision of task migration and partitioning whether/where to migrate or partition tasks in the waiting queues of servers. According to the decision made by a MECS controller, at time slot \(\tau+1\), the tasks stored in the waiting queues are placed into the computation queues of the servers to which they belong or the computation queues of other servers. Once tasks or subtasks are placed in the computation queue, they cannot be partitioned or migrated to another MECS additionally. Assuming that some subtasks in MECS \(m\) are migrated to another MECS \(m^{\prime}\), the subtasks are performed in MECS \(m\) and \(m^{\prime}\) respectively, the computation results of subtasks are merged by MECS \(m\), and sent to the vehicle. These operation of a MEC network are shown in Figure 2.  
The data rate for forwarding the task offloaded from a vehicle to a MECS at time slot \(t\) can be calculated as  
\[R_{n,m}(t)=B_{n}\log_{2}\biggl{(}1+\frac{P\cdot H_{n,m}}{\sigma^{2}}\biggr{)}\, \tag{1}\]  
where \(B_{n}\) is the bandwidth allocated to a channel, \(P\) is the transmission power of the vehicle, \(H_{n,m}\) is the channel gain between vehicle \(n\) and MECS \(m\), and \(\sigma^{2}\) is the received noise power.