# Energy-Efficient Resource Provisioning Strategy for Reduced Power Consumption in Edge Computing +
## 4 Energy-Efficient Scheduling Scheme
### Scheduling Scheme Based on Branch and Bound (PSBB)  
In this subsection, we propose a scheduling scheme based on the branch and bound method which is a fast search tree algorithm based on a depth-first searching algorithm. According to the problem formulation, we have that the scheduling problem for multiple users can transform into a discrete combinatorial optimization problem. The core idea of our scheduling scheme is efficiently searching candidate solutions on the solution space tree. The candidate solution set is considered to be a rooted tree that forms a complete set on the root. The algorithm explores the branches of the tree, which represents a subset of the solution set. Before enumerating the candidate solutions of a branch, the candidate solution of the branch will be checked according to the feasibility of the current optimal solution based on the estimated upper and lower bounds of the optimal solution. If it cannot produce a better solution than the optimal one currently, the algorithm will discard the solution. The branch and bound method can be applied to a variety of maximum and minimum problems. The above problem happens to be the minimum problem that will solve finite candidate solutions, which meets the requirements of the branch and bound method. For example, if it is assumed that a task needs to be scheduled, the task has a sub-task set \(v_{j}\in V\). Since each sub-task can be offloaded independently, each sub-task \(\{v_{1},v_{2},v_{3},\cdots,v_{j}\}\) need to be determined the computing location through an algorithm. Therefore, the algorithm in this section needs to build a tree to represent the solution space of the computing location of the sub-task. The \(n_{th}\) layer of the tree represents the possible calculation position of the sub-task \(n\), and each node has 3 children, which are the \(n+1\) possible calculation locations for sub-tasks. It is inferred from this that the output (scheduling scheme) is the path from the root to a leaf of this tree. In this algorithm, the solution space is represented as a topology \(G\), as one of the input parameters. The specific steps of applying this algorithm to the above problem are shown in Algorithm 1. We take the topology of fog nodes \(G\), and the set of users \(U\) as our inputs. The output is the scheduling scheme \(X\) for the set of users \(U\). We use \(|V|\) and \(|U|\) to denote the numbers of edge nodes and users, respectively. We first initialize the bound \(L\) and temporary set \(S\) in lines 3 and 5. In line 6, we calculate the power consumption of sub-tasks, where \(E_{c}(u_{i}^{k})\) is the power consumption of sub-task \(u_{i}^{k}\) for executing at local device. \(E_{t}(u_{i}^{k})\) is the power consumption of sub-task \(u_{i}^{k}\) for executing at remote edge node. We send the results into set \(S\) and find the minimum one as the branch as shown in lines 7 to 8. Then we calculate the total power consumption \(E(u_{i})\) for sub-task \(u_{i}\) in line 9. If both \(E(u_{i})\) and \(D_{i}\) satisfy the constraints, we will check whether \(u_{i}^{k}\) is the last sub-task of \(u_{i}\). If \(k==|u_{i}|\), we will update the bound \(L=E(u_{i})\). Otherwise, we continue to calculate next sub-task in line 15. If either \(E(u_{i})\) or \(D_{i}\) are beyond the constraints, we will cut this branch and do not continue to traverse in line 18. The entire process ends after all edge nodes are traversed or all sub-tasks of users are finished. We calculate the total power consumption \(E\) and return \(X\) in lines 23 to 25. The key of this algorithm is to save the optimal solution boundary \(L\) as the basis for pruning. Since the power consumption of each node in the searching tree is greater than the power consumption of its parent, when a node's power consumption exceeds the optimal solution boundary \(L\), it must be concluded that the power consumption of the node and its children must be greater than the current optimal solution boundary.