A Multi-Layered Distributed Computing Framework for Enhanced Edge Computing

The network is modeled as a directed graph $\mathcal{G}=\{\mathcal{N},\mathcal{E}\}$, where $\mathcal{N}=\{i|0\leq i\leq N\}$ is the set of edge servers and $\mathcal{E}=\{(i,j)|i,j\in\mathcal{N},i\neq j\}$ is the set of server-to-server communication links that connect servers that can communicate directly.

Let $f_{i}$ denote the computing capacity of server $i$, i.e., CPU-cycle frequency (GHz). Given a task of size $y$, let $b$ denote the total number of CPU cycles required to process one task size unit. The time required for server $i$ to process this task can then be expressed by [8]:

Let $R_{i,j}$ denote the data transmission rate from server $i$ to server $j$, which we assume to be known for the sake of simplifying analysis. This rate can be approximated using the Shannon’s Theory [46] as $R_{i,j}=B_{i,j}log_{2}(1+\frac{s_{i,j}}{n_{i,j}})$, where $B_{i,j}$ is the channel bandwidth, and $s_{i,j}$ and $n_{i,j}$ represent the signal power and noise power, respectively.

The energy consumed for executing a task mainly constitutes two components: energy consumed for computing and energy consumed for communication. The energy consumed for server $i$ to compute a task of size $y$ is given by [20]:

where $\gamma_{i}$ is the effective switched capacitance that depends on the chip architecture of server $i$. The energy consumed for server $i$ to transmit a task of size $y$ to server $j$ is given by [20]:

where $e_{i}$ represents the transmission power of server $i$.

To specify the computation workload allocated to each node $i\in\mathcal{N}$, we introduce decision variables $\boldsymbol{y}=\{y_{0},y_{1},\ldots,y_{N}\}$, where $y_{i}\in[0,Y]$ represents the size of the subtask assigned to node $i$. If $y_{i}=0$, it implies that node $i$ is not assigned any workload. Note that the master may choose to execute (part of) the task locally, in which case $y_{0}$ would be nonzero, i.e., $y_{0}>0$.

To describe the offloading order for subtasks transmitted from the master to the other nodes, we introduce decision variables $\boldsymbol{o}=\{o_{1},o_{2},\ldots,o_{N}\}$, where $o_{i}\in\mathcal{N}\setminus\{0\},\forall i\in\mathcal{N}\setminus\{0\}$ and $o_{i}\neq o_{j},\forall i,j\in\mathcal{N}\setminus\{0\},i\neq j$. When $o_{i}>o_{j}$, node $i$ has a higher priority than node $j$ to receive its subtask, where $i,j\in\mathcal{N}\setminus\{0\}$ and $i\neq j$.

We aim to achieve two objectives simultaneously: minimize the time spent and minimize the energy consumed by each node for executing the task. By employing a weighted sum method, we define the objective function as follows:

where $w_{1},w_{2}\geq 0$ are the weights, representing the relative importance of the two objectives. $T_{i}^{total}$ is the total time required for node $i$ to receive its subtask from the master and complete the assigned subtask. Note that the time required for completing the whole task is $\max T_{i}^{total}$, ${i\in\mathcal{N}}$. $E_{i}^{total}$ is the total energy consumed by node $i$ during task execution. $J_{i}$ is introduced to denote the cost associated with node $i$. In the following sections, parentheses or subscripts may be omitted for simplicity when there is no confusion.

Next, we derive the formulas for $T_{i}^{total}$ and $E^{total}_{i}$.

The task completion time for node $i$, $T_{i}^{total}$, is comprised of three components: 1) time taken to transmit subtask of size $y_{i}$ from the master to node $i$, denoted as $T_{i}^{tran}$; 2) time spent waiting in the queues of relays along the path to node $i$ if any, denoted as $T_{i}^{wait}$; and 3) time to execute the subtask, i.e., $T_{i}^{comp}$. It is noted that the waiting time $T_{i}^{wait}$ is impacted by the task sizes assigned to other nodes and the offloading order, which complicates the optimization problem considered in this study.

To obtain the transmission time $T_{i}^{tran}$, we introduce the notation $\boldsymbol{p}_{i}$ to denote the sequence of nodes that lie on the path from the master to node $i$, and the notation $p_{ik}$ to denote the $k$-th node in the sequence, where $1\leq k\leq|\boldsymbol{p}_{i}|$, $p_{i1}=0$ and $p_{i|\boldsymbol{p}_{i}|}=i$. $|\cdot|$ finds the cardinality of a set. $T_{i}^{tran}$ can then be expressed by:

Let’s now consider the waiting time $T_{i}^{wait}$. Let $\mathcal{A}_{t}$ denote the full set of nodes in the $t$-th subtree of the master, where $t\in\mathcal{I}_{1}$, and $\cup_{t\in\mathcal{I}_{1}}\mathcal{A}_{t}=\mathcal{N}\setminus\{0\}$. Additionally, define $\mathcal{B}_{i}=\{j|o_{j}>o_{i},i,j\in\mathcal{A}_{t},i\neq j\}$ as the set of nodes whose subtasks will be transmitted before node $i$. Note that if nodes $i$ and $j$ belong to different subtrees, i.e., $i\in\mathcal{A}_{t}$ while $j\notin\mathcal{A}_{t}$, the subtask for node $j$ is transmitted using a different channel that is orthogonal to the one used for node $i$, and hence node $i$ does not need to wait for node $j$’s subtask to be transmitted even if $o_{j}>o_{i}$. Based on these definitions, we can then express the waiting time as follows:

where $\boldsymbol{p}_{s}=\boldsymbol{p}_{i}\cap\boldsymbol{p}_{j}$.

Based on (1), (5), and (6), we then have

With $T_{i}^{total}$ and (2)-(3), the energy consumption $E_{i}^{total}$ can then be expressed by:

In the above equation, $\mathcal{C}_{i}$ is the set of children of node $i$, whose subtasks will be relayed by node $i$.

It is noted that $\mathcal{P}_{0}$, which aims to minimize the maximum cost of individual nodes, is a minmax optimization problem. Hence, we can convert it into an equivalent mixed integer linear programming (MILP) problem by introducing an auxiliary variable $z$ as follows:

Then, the minimum cost $\mathcal{J}^{\star}=z^{\star}$, where $z^{\star}$ is the minimum value of $z$ found by solving $\mathcal{P}_{1}$.

Problem $\mathcal{P}_{1}$ can be further decomposed into two subproblems. The first subproblem aims to optimize the task allocation $\boldsymbol{y}$, given a particular offloading order denoted as $\boldsymbol{o}=\boldsymbol{o}_{k}$:

Denote the optimal solution to problem $\mathcal{P}_{1}^{(a)}$ at $\boldsymbol{o}=\boldsymbol{o}_{k}$ as $\{{\boldsymbol{y}^{*}}(\boldsymbol{o}_{k}),{z}^{*}(\boldsymbol{o}_{k})\}$. The second subproblem aims to optimize the offloading order $\boldsymbol{o}$:

Now let’s consider subproblem $\mathcal{P}_{1}^{(a)}$, which can be solved using Lagrange multipliers [5]. Particularly, the Lagrangian function can be defined as follows:

where $\boldsymbol{\lambda}=[\lambda_{0},\lambda_{1},\ldots,\lambda_{N}]$ and $\mu$ are Lagrangian multipliers. $\lambda_{i}\geq 0$, $\forall i\in\mathcal{N}$. Define

The dual optimization problem is then constructed as follows:

As the objective function and the inequality constraints in our problem are convex, and the equality constraints are affine and strictly feasible, Slater’s condition [3] is satisfied and the strong duality holds. That means the optimal value of the primal problem $\mathcal{P}_{1}^{(a)}$ is equal to the optimal value of its dual problem (V-A1). The optimal solution to $\mathcal{P}_{1}^{(a)}$ can then be found by solving the following equation set, known as the Karush-Kuhn-Tucker (KKT) conditions [31]:

To solve problem $\mathcal{P}_{1}^{(b)}$, we can use exhaustive search. This involves computing the cost $z^{*}(\boldsymbol{o}_{k})$ for each possible offloading order $\boldsymbol{o}_{k}$ and selecting the one that yields the smallest cost. However, as $\boldsymbol{o}_{k}$ can take $N!$ possible values, evaluating each possible value is time-consuming. A significant reduction in the number of possible values to evaluate can be achieved by exploiting the parallelism in sending subtasks belonging to different subtrees of the master. Specifically, the offloading orders for nodes in any subtree $\mathcal{A}_{t}$ are independent of those in any other subtree $\mathcal{A}_{t^{\prime}}$, where $t,t^{\prime}\in\mathcal{I}_{1}$ and $t\neq t^{\prime}$. Therefore, the number of possible values of $\boldsymbol{o}_{k}$ that need to be evaluated can be reduced to $\prod_{t\in\mathcal{I}_{1}}|\mathcal{A}_{t}|!$. Algorithm 1 summarizes the procedure of the proposed approach, named the centralized MILP-based optimization (CMO).

As the equation set (11) involves $2N+4$ unknown variables, solving it requires $O(N^{3})$ amount of time in the worst case [17]. The computational complexity of CMO is hence $O(\prod_{t\in\mathcal{I}_{1}}|\mathcal{A}_{t}|!N^{3})$, with a worst-case complexity of $O(N!N^{3})$.

The parallelism involved in sending subtasks belonging to different subtrees of the master can be further harnessed to greatly enhance efficiency. Specifically, the key idea is to decompose problem $\mathcal{P}_{1}$ alternatively into two different subproblems. The first subproblem optimizes the task allocation and scheduling for nodes within each subtree, which can be solved in parallel. The second subproblem optimizes the total workload assigned to each subtree.

Mathematically, let $Y_{t}$ be the total workload assigned to nodes within the $t$-th subtree of the master, i.e., $Y_{t}=\sum_{i\in\mathcal{A}_{t}}y_{i}$, $t\in\mathcal{I}_{1}$. Additionally, let $\boldsymbol{y}_{t}=\{y_{i}|i\in\mathcal{A}_{t}\}$ and $\boldsymbol{o}_{t}=\{o_{i}|i\in\mathcal{A}_{t}\}$ represent the decision variables associated with nodes within the subtree $\mathcal{A}_{t}$. Then, the first subproblem can be formulated as follows:

Since tasks assigned to different subtrees can be transmitted simultaneously, this problem can be solved independently and in parallel for different subtrees.

Suppose given $Y_{t}$, the optimal solution to problem $\mathcal{P}_{1}^{(a^{\prime})}$ for subtree $\mathcal{A}_{t}$ is $\{\bar{z}_{t}(Y_{t}),\bar{\boldsymbol{y}}_{t}(Y_{t}),\bar{\boldsymbol{o}}_{t}(Y_{t})\}$. The second subproblem aims to optimize the workload assigned to each subtree as well as to the master, denoted as $\boldsymbol{\mathcal{Y}}=\{Y_{t}|t\in\mathcal{I}_{1}\}\cup\{y_{0}\}$, which can be mathematically formulated as follows:

where $J_{0}(\boldsymbol{\mathcal{Y}})=w_{1}T_{0}^{total}+w_{2}E_{0}^{total}=w_{1}\frac{y_{0}b}{f_{0}}+w_{2}\left[\gamma_{0}y_{0}b(f_{0})^{2}+\sum_{t\in\mathcal{I}_{1}}\frac{e_{0}Y_{t}}{R_{0,t}}\right]$. Of note, this subproblem can be conceptualized by abstracting each subtree as a single node. Therefore, $\mathcal{T}$ is abstracted as a one-layer tree (see Fig. 3). The optimization of the workload $Y_{t}$ assigned to each abstracted node (subtree) thus does not require consideration of the offloading order. Then, the optimal solution to $\mathcal{P}^{(b^{\prime})}_{1}$, denoted as $Y^{*}_{t}$, $\forall t\in\mathcal{I}_{1}$, can be used to derive the optimal solution to the original problem $\mathcal{P}_{1}$. Particularly, $\boldsymbol{y}^{\star}=\{\bar{\boldsymbol{y}}_{t}(Y^{*}_{t})|t\in\mathcal{I}_{1}\}$, and the optimal offloading order for nodes within each subtree $t$ is given by $\bar{\boldsymbol{o}}_{t}(Y^{*}_{t})$.

Solving problem $\mathcal{P}_{1}^{(a^{\prime})}$ given $Y_{t}$ is relatively straightforward. However, directly addressing subproblem $\mathcal{P}_{1}^{(b^{\prime})}$ is challenging because $Y_{t}$ is continuous, and obtaining $\bar{z}_{t}(Y_{t})$ in the constraints requires solving subproblem $\mathcal{P}_{1}^{(a^{\prime})}$. Before we proceed with our approach to solving these subproblems, we present the following lemma and theorem, which allow for their simplification.

Lemma 1 leads directly to the following theorem.

The proportionality property described in Theorem 2 infers that, given the optimal solution to $\mathcal{P}_{1}^{(a^{\prime})}$ for any $Y^{\prime}_{t}$, i.e., $\{\bar{z}_{t}(Y^{\prime}_{t}),\bar{\boldsymbol{y}}_{t}(Y^{\prime}_{t}),\bar{\boldsymbol{o}}_{t}(Y^{\prime}_{t})\}$, the subproblem $\mathcal{P}_{1}^{(b^{\prime})}$ can be simplified to:

Since $Y^{\prime}_{t}$ and $\bar{z}_{t}(Y^{\prime}_{t})$ are known (by solving $\mathcal{P}_{1}^{(a^{\prime})}$), $\mathcal{P}^{(c^{\prime})}_{1}$ is now straightforward to solve.

Next, we describe our approach to solve subproblems $\mathcal{P}^{(a^{\prime})}_{1}$ and $\mathcal{P}^{(c^{\prime})}_{1}$. Particularly, for $\mathcal{P}^{(a^{\prime})}_{1}$, we can solve it by leveraging the CMO algorithm (Algorithm 1). For each subtree $\mathcal{A}_{t}$, $t\in\mathcal{I}_{1}$, we run the CMO algorithm on the tree formed by $\mathcal{A}_{t}$ as well as the master (as highlighted by the green dashed circle in Fig. 3), denoted as $\mathcal{T}_{t}$, where the input $Y$ can take any value. Suppose the output generated by CMO for $\mathcal{T}_{t}$ is denoted as $\{\tilde{z}_{t},\tilde{\boldsymbol{y}}_{t},\tilde{\boldsymbol{o}}_{t}\}$, where $\tilde{\boldsymbol{y}}_{t}=\{\tilde{y}_{i}|i\in\mathcal{A}_{t}\}\cup\{\tilde{y}_{0}\}$ specifies the tasks allocated to the nodes within $\mathcal{T}_{t}$. Then we let $Y^{\prime}_{t}=\sum_{i\in\mathcal{A}_{t}}\tilde{y}_{i}$, $\bar{z}_{t}(Y^{\prime}_{t})=\max\{J_{i}(\tilde{\boldsymbol{y}}_{t},\tilde{\boldsymbol{o}}_{t})|i\in\mathcal{A}_{t}\}$. Given $Y^{\prime}_{t}$ and $\bar{z}_{t}(Y^{\prime}_{t})$ for each $t\in\mathcal{I}_{1}$, we can then solve the subproblem $\mathcal{P}^{(c^{\prime})}_{1}$ using a commercial solver, such as Gurobi [34] and CVX [18].

Denote the optimal solution to subproblem $\mathcal{P}^{(c^{\prime})}_{1}$ as $\boldsymbol{\mathcal{Y}}^{*}=\{{Y}^{*}_{t}|t\in\mathcal{I}_{1}\}\cup\{{y}^{*}_{0}\}$. The optimal solution to the original problem $\mathcal{P}_{1}$ can then be derived as:

$\tilde{\boldsymbol{o}}_{t}$, $t\in\mathcal{I}_{1}$, specifies the optimal offloading order for subtasks assigned to each node within each subtree $\mathcal{A}_{t}$, where subtasks for different subtrees can be transmitted simultaneously.

Algorithm 2 summarizes the procedure of the parallel MILP-based optimization (PMO) method.

Since subtree $\mathcal{T}_{t}$, $t\in\mathcal{I}_{1}$, contains $|\mathcal{A}_{t}|+1$ nodes, CMO$(\mathcal{T}_{t},Y)$ requires $O((|\mathcal{A}_{t}|+1)!(|\mathcal{A}_{t}|+1)^{3})$ time to execute. The complexity of PMO is $O(\max_{t\in\mathcal{I}_{1}}(|\mathcal{A}_{t}|+1)!(|\mathcal{A}_{t}|+1)^{3})$ with a worst-case complexity of $\mathcal{O}(N!N^{3})$.

The key idea of NP is to “prune” nodes that are too costly to use. Specifically, this strategy evaluates each node one by one. For a given node $i$, it estimates the cost of using this node by performing partial offloading [20], which finds the optimal task partition between the master and node $i$ exclusively. The obtained cost, denoted as $z^{p}_{i}$, is then compared with the cost of local computing, i.e., the cost of processing the entire task $Y$ at the root node, denoted as $z^{(0)}$, which can be obtained by running $\text{CMO}(\mathcal{I}_{0},Y)$. If the cost reduction, measured by $\frac{z^{(0)}-z^{p}_{i}}{z^{(0)}}$, exceeds a predefined threshold $\theta_{p}$, node $i$ is selected; otherwise, it is “pruned”. Here, “prune” means that no workload is assigned to the node. If the node is a leaf, it is removed from the tree. However, if it is an intermediate node with unpruned children, it remains and only acts as a relay.

The key idea of LP is to trim nodes that are excessively distant from the master node, whose computing resources are too costly to use considering the significant communication costs. Specifically, this strategy evaluates the top $\xi$ levels of the original network tree, removing levels from $\xi+1$ to $H$. The resulting tree, denoted as $\mathcal{T}^{\xi}$, satisfies $\mathcal{T}^{\xi}=\mathcal{T}\setminus\cup_{l=\xi}^{H}\mathcal{I}_{l}$.

We first consider the four small-scale network topologies depicted in Fig. 4. In this experiment, the threshold parameter $\theta_{p}$ in NP is set to $0.312,0.43,0.3,0.4$, respectively, such that one node in each topology is pruned. The threshold parameter $\xi$ in LP is set to $5,1,4,2$ for the four topologies, respectively, resulting in the pruning of the last level of each topology. For GA, the parameters are configured as $G=5,P=4,\alpha=0.2,\beta=0.05$. To measure the efficiency of proposed approaches, we run each method 20 times and record the mean execution time, denoted as $T_{\text{exe}}$.

Fig. 7(a) shows the costs of the solutions found by the five methods. Comparing GA with the optimal methods, CMO and PMO, reveals that GA can find optimal solutions for small networks. This similarity in performance further demonstrates the optimality of GA for small networks. The worker selection methods, NP and LP, underperform compared to the other three methods, which is attributed to the reduced number of nodes involved in sharing the computational workload. Moreover, comparing the performance of LP across different topologies indicates that the extent of performance degradation is closely related to the proportion of nodes pruned from the network tree. Specifically, LP prunes 14.28%, 57.14%, 11.11%, and 37.5% of the nodes in the four topologies, respectively. The largest pruning proportion occur in Topology 2, resulting in the maximum level of performance degradation. For NP, as only one node is “pruned” in each topology, it performs better than LP in these scenarios.

The base-10 logarithm of the execution time, i.e., $\log_{10}T_{\text{exe}}$, of each method is shown in Fig. 7(b). As expected, the optimal methods, CMO and PMO, are more time-consuming than the three heuristic methods. Moreover, PMO, being a parallelized version of CMO, significantly reduces execution time in Topologies 2-4 due to its parallelism. For Topology 1, since the root has a single subtree, PMO is equivalent to CMO. Among the heuristic methods, LP achieves the least execution time by pruning the most nodes and significantly reducing the search space. GA, on the other hand, is the least efficient and even underperforms PMO in Topologies 2 & 4. This suggests that for small networks, PMO can be directly applied. Furthermore, comparing NP and PMO, we can observe that NP does not improve efficiency in all scenarios, despite reducing the number of workers. This is because only one node is “pruned” in each topology, and the time saved by pruning is offset by the overhead generated by the pruning procedure.

As the performance of the proposed approaches largely depend on the network size, we further vary the network size by increasing the number of subtrees, $|\mathcal{I}_{1}|$, where each subtree consists of 2 levels and 1 node in each level. The scenario where the network size expands due to the growth of subtrees is explored in the subsequent subsection. In this experiment, we configure parameter $\theta_{p}$ in NP in a way such that one additional node is “pruned” when including an additional subtree. Parameter $\xi$ in LP is set to $1$ in all cases, meaning that the node(s) in the last level are pruned. For GA, its parameters are configured as $P=4,G=100,\alpha=0.2,\beta=0.05$. Fig. 8(a) shows the performance of different methods as the number of subtrees $|\mathcal{I}_{1}|$ increases. As we can see, increasing the number of subtrees results in a reduced total cost $J$, as more nodes are involved in sharing the computational workload. When comparing NP and LP, NP consistently outperforms LP. It’s noteworthy that both methods prune the same number of nodes, each trimming one node from every subtree. This underscores the effectiveness of NP’s worker selection process, which employs a more rigorous approach compared to LP that simply selects nodes at the top levels. However, the simplicity of LP makes it more efficient than NP, as shown in Fig. 8(b). Additionally, from Fig. 8(b), we can observe a significant increase in the execution time of CMO as more subtrees are considered, compared to the other four methods. This is due to the parallelism inherent in the other four methods. Moreover, comparing PMO with the other methods further demonstrates the good performance of PMO in both optimality and efficiency in cases of small networks.

In this experiment, we consider larger networks and evaluate the performance of the three heuristic methods, NP, LP, and GA. For the implementation of NP and LP, GA is applied after pruning to determine the task allocation. Given that all these methods evaluate subtrees in parallel and their efficiency is bounded by the largest subtree, we evaluate their performance on networks with a single subtree. This approach allows us to avoid considering the impact of the number of subtrees. These networks are randomly generated with node counts of 10, 20, 30, and 50. The parameters in NP and LP are configured to prune a similar number of nodes as follows: the threshold $\theta_{p}$ in NP is set to $0.36,0.45,0.5,0.38$, and the threshold $\xi$ in LP is set to $4,3,3,12$ for the corresponding networks, respectively. The parameters in GA, applied across all methods, are set to $P=4,G=100,\alpha=0.2,\beta=0.05$.

As shown in Fig. 9(a), the total cost $J$ generally decreases with the increase in network size for each method, as more nodes share the workload. Notably, the performance of GA degrades when the network size reaches 50. This is due to the large search space, making GA difficult to converge within 100 generations. Comparing the three methods, we can observe that GA outperforms the other two methods by considering all nodes in the network. NP generates better solutions than LP, although they prune roughly the same number of nodes. Additionally, NP and LP achieve performance comparable to GA in large networks (greater than 30 nodes), but with significantly lower execution times, as shown in Fig. 9(b). This suggests that for large networks, NP and/or LP can be applied first to select a subset of workers, followed by GA for task allocation.

In NP, a worker is selected if the cost reduction from including this node exceeds the threshold $\theta_{p}$. Therefore, a higher threshold will result in fewer nodes being selected and more nodes being “pruned”. This is demonstrated by the results shown in Fig. 10(a). As we can see, the best performance is achieved when $\theta_{p}=0$, in which case no nodes are “pruned”. The worst performance occurs at $\theta_{p}=1$, where all workers are “pruned” and all computations are done locally at the master. Moreover, as $\theta_{p}$ decreases, more workers are selected, resulting in a decrease in cost $J$ (see Fig. 10(a)) but an increase in execution time $T_{\text{exe}}$ (see Fig. 10(b)). Notably, when $\theta$ is reduced to 0.4, $J$ tends to converge. This suggests that an appropriate value of $\theta_{p}$ that balances optimality and efficiency can be identified by selecting the value at which a sharp change in cost $J$ occurs.

LP selects all nodes in the top $\xi$ levels as workers. In the special case when $\xi=0$, no nodes are selected, resulting in all computations being conducted locally at the master. This leads to the highest cost $J$, as shown in Fig. 11(a). As $\xi$ increases and more nodes are selected, performance improves, as indicated by the decreasing cost $J$. However, the performance improvement slows down when $\xi$ exceeds 3. The best performance is achieved when $\xi$ reaches its maximum value, $H$ (height of the network tree), which is 12 in this experiment. Given the rapid increase in execution time with higher $\xi$, as shown in Fig. 11(b), a proper value for $\xi$ can be chosen at the point where the rate of decrease in $J$ slows down.