# Global Resource Scheduling for Distributed Edge Computing
## 4 Algorithm Design  
### Design of Heuristic Algorithm Based on ACO  
Since problem \(S\) has been proven to be NP-Hard, we choose a heuristic algorithm to solve this problem. In the heuristic algorithm, this paper chooses the ACO to design. The ACO is an intelligent heuristic algorithm. It solves some optimization problems by simulating the process of ants' foraging in nature. In the whole search process, the ants will leave pheromones on the path every time they pass through a path. The ants tend to find the path with high pheromone concentration in the subsequent process. The higher the concentration of pheromones, the higher the probability that the path will be selected. The ACO was first proposed to solve the travelling salesman problem (TSP). The process of implementing TSP with the ACO is as follows: select \(m\) ants and \(n\) cities, and first give the initial pheromone concentration on the path as \(\tau_{0}\), and then let \(m\) ants move from the random initial city, passing through all cities once and only once, and then update the pheromone on the path. In the next iteration, the ants will choose a path with a higher concentration. The probability \(p_{ij}^{k}(t)\) of the \(k\)-th and going from the \(i\)-th city to the \(j\)-th city at time \(t\) can be expressed as follows:  
\[p_{ij}^{k}(t)=\left\{ \begin{array}{ll}\frac{\left[\tau_{ij}(t)\right]^{k} \cdot[\eta]^{k}}{\sum_{i\in N_{i}^{k}}[\tau_{ij}(t)]^{k}\cdot[\eta]^{k}}&j\in N _{i}^{k}\\ 0&j\
otin N_{i}^{k}\end{array} \right. \tag{7}\]  
where \(N_{i}^{k}\) represents the next hop node-set, which node \(i\) can select in the \(k\)-th iteration. The heuristic information \(\eta_{ij}\) is generally set as \(1/d_{ij}\). Moreover, \(\alpha\) is the relative importance of the pheromones left in the previous iteration, \(\beta\) is used to measure the importance of heuristic information, and \(N_{i}^{k}\) is the set of possible target cities, that is, the cities that have not been visited. We use a tour list to preserve the cities that ants have passed through, that is, cities that can no longer be selected during the selection process. The pheromone is updated according to the following formulas:  
\[\tau_{ij}(t+n)=(1-\rho)\cdot\tau_{ij}(t)+\Delta\tau_{ij} \tag{8}\] \[\Delta\tau_{ij}=\sum_{k=0}^{m}\Delta\tau_{ij}^{k}\] \[\Delta\tau_{ij}^{k}=\left\{ \begin{array}{ll}\frac{Q}{L_{k}}& \text{if $\text{edge}(i,j)$ its tour}\\ 0&\text{otherwise}\end{array} \right.\]where \(\rho\) indicates the volatilization rate of the pheromone, then \((1-\rho)\) refers to the extent to which the pheromone inherits the pheromone at the last time. It is also called the residual factor. \(\Delta\tau_{ij}\) represents the increased concentration of pheromones on edges\((i,j)\). \(Q\) is a constant, and \(L_{k}\) represents the length of the path that the \(k\)-th ant walked in this iteration. The traditional ACO is prone to slow convergence and may only obtain the optimal local solution but not the optimal global solution. Moreover, for the parameters in the traditional ACO \(\alpha,\beta\), the parameters obtained through experiments in advance are not necessarily the optimal parameters. In this paper, the pheromone concentration on the path composed of every two nodes at the initial time is the same, which is a constant \(\tau_{0}\). Each edge has the same attraction to ants at the initial time, so the probability of selecting the next node depends on the distance \(d_{ij}\) and the price of resources. From a global perspective, for the path with low scheduling cost, the local shortest path length does not mean it is the optimal result. In Figure 3, assume that \(l_{ij_{1}}<l_{ij}\) and \(l_{jk}<l_{j_{k}k_{1}}\), but \(l_{ik}<l_{ik_{1}}\), it can be concluded that the scheduling cost of each subpath is not necessarily the minimum on the path with the lowest scheduling cost. To address the challenge of the traditional ACO potentially converging to a suboptimal solution in the large-scale distributed resource migration problem, this paper introduces an enhanced approach.