# Task Migration with Partitioning for Load Balancing in Collaborative Edge Computing
## 3 Task Partitioning and Migration Methods
### Task Migration Method  
The proposed task migration method is presented in Algorithm 1. The objective of our method is to balance the loads among MECSs in the MEC system, particularly between the overloaded and underloaded MECSs. The MECS controller must determine which MECS \(m\) to migrate from and select the target MECS \(m^{\prime}\) to migrate to. If MECS \(m\) migrates its task to target MECS \(m^{\prime}\), the MECS controller must determine the task and the amount of workload to be migrated to MECS \(m^{\prime}\). At the end of time slot \(t\), the MECS controller monitors the load status of the MECSs. Subsequently, the MECS controller calculates the average load of the MECSs in the MEC system as follows:  
\[\zeta(t)=\frac{1}{M}\sum_{m=1}^{M}\zeta_{m}(t), \tag{7}\]  
The MECS controller classifies the overloaded or underloaded MECSs based on their average load. The MECSs whose loads are higher than \(\zeta(t)\) are overloaded compared with other MECSs as a set of \(\alpha\). Similarly, the MECSs whose loads are equal to or lower than \(\zeta(t)\) are underloaded compared with other MECSs as a set \(\beta\). To balance the loads among MECSs in the MEC system, particularly between the overloaded and underloaded MECSs, tasks in overloaded MECSs migrate to underloaded MECSs. Therefore, the MECS controller determines that each MECS \(m\) in set \(\alpha\) migrates its tasks to MECS \(m^{\prime}\) in set \(\beta\). The MECS controller calculates the load difference between the MECS in set \(\alpha\) and MECS in the set \(\beta\). This is expressed as follows:  
\[\varphi_{m,m^{\prime}}(t)=\zeta_{m}(t)-\zeta_{m^{\prime}}(t),\ \ m\in\alpha,\ \ m^{\prime}\in\beta, \tag{8}\]  
Now, the MECS controller determines a target MECS \(m^{\prime}\) with the highest \(\varphi_{m,m^{\prime}}(t)\) for MECS \(m\). The MECS \(m\) then migrates the amount of workload to the target MECS \(m^{\prime}\) as according to the load difference between the MECS \(m\) and MECS \(m^{\prime}\). Here, the amount of workload of subtasks that MECS \(m\) migrates to MECS \(m^{\prime}\) should be less than \(\varphi_{m,m^{\prime}}(t)\) Tasks to be migrated in the waiting queue of MECS \(m\) are selected in descending order.  
Figure 3: Example of DAG task graph and clusters.  
After partitioning and migrating the subtasks, the MEC controller removes \(m\) and \(m^{\prime}\) from \(\alpha\) and \(\beta\) if their loads become similar to the average load of all MECSs or if the load difference between \(m\) and \(m^{\prime}\) is similar. The MECS controller repeats this procedure until \(\alpha\) or \(\beta\) is empty, or all of the tasks in \(m\) are partitioned and migrated.  
```
at time slot \(t\), initialize \(\zeta(t)\) initialize set \(\alpha=\{m|\zeta_{m}(t)>\zeta(t)\}\) initialize set \(\beta=\{m^{\prime}|\zeta_{m^{\prime}}(t)\leq\zeta(t)\}\) if\(|\alpha|\
eq\varnothing\) and \(|\beta|\
eq\varnothing\)then  MECS \(m=argmax_{m\in\alpha}\zeta_{m}(t)\)  select task \(i\) in the waiting queue of MECS \(m\)  a set of subtasks in task \(i\), \(C=\{C_{i}\}\), sort by the amount of workload in descending order for the number of subtasks in \(C\), \(|C|\)do  MECS \(m^{\prime}=argmax_{m\in\alpha,\;m^{\prime}\in\beta}\varphi_{m,m^{\prime}}(t)\) if\(l_{i}^{c}\leq\varphi_{m,m^{\prime}}(t)\)then  migrate \(C_{i}\) to MECS \(m^{\prime}\)  update \(\zeta_{m(i)}=\zeta_{m}(t)-l_{i}^{c}\), \(\zeta_{m^{\prime}}=\zeta_{m^{\prime}}(t)+l_{i}^{c}\) else break  update \(\varphi_{m,m^{\prime}}(t)=\zeta_{m}(t)-\zeta_{m^{\prime}}(t)\) if\(\varphi_{m,m^{\prime}}(t)\leq\)thresholdthen continue else \(\alpha=\alpha\backslash\{\text{m}\}\) \(\beta=\beta\backslash\{m^{\prime}\}\) \(\text{else}\) tasks in the waiting queue are placed into its computation queue
```  
**Algorithm 1**Proposed method