Decentralized Network Topology Design for Task Offloading in Mobile Edge Computing

The MEC system is modeled as a graph $G=\{\mathcal{V},\mathcal{E}\}$, where $\mathcal{V}=\{0,1,\ldots,N-1\}$ denotes the set of servers, with the master server labeled as $0$. $\mathcal{E}$ represents the set of edges. An edge between two servers, $i$ and $j$, is established when they are within each other’s communication range, meaning their Euclidean distance, denoted as $d_{ij}$, satisfies $d_{ij}\leq\xi$. The connectivity is described by the adjacency matrix $A$, where each element $a_{ij}$ is equal to $1$ if there is an edge between server $i$ and server $j$, and $0$ otherwise.

Additionally, define $\mathcal{N}_{i}=\{j|a_{ij}=1,\forall j\in\mathcal{V}\}$, where $i\in\mathcal{V}$, as the set of neighbors of server $i$ that are within its communication range. By strategically selecting CHs from the set $\mathcal{N}_{0}$ to receive tasks offloaded from the master, and assigning CMs from the set $\mathcal{N}_{i}$ to each CH $i$ to handle tasks offloaded from CH $i$, the master, CHs, and CMs form a three-layer tree topology, denoted as $\mathcal{T}$. We assume that each CM can belong to only one CH.

To describe data transmission between two servers, we adopt the model in [18]. Specifically, suppose the servers communicate using the Orthogonal Frequency Division Multiplexing protocol [19], where the bandwidth is equally divided when a server transmits data simultaneously to its connected servers via orthogonal channels. For simplicity of analysis, we assume the channels are free from interference. If a server $i$ (e.g., a CH) transmits data to its $m$ neighboring servers (e.g., associated CMs) simultaneously, the data transmission rate for the link between server $i$ and its $j$-th neighbor is given by $R_{ij}=\frac{B}{m}log_{2}(1+\frac{\beta_{ij}}{d_{ij}^{2}})$, where $B$ (MHz) denotes the total bandwidth, and $\beta_{ij}$ represents the signal-to-noise (SNR) ratio.

The computation model from [19] is used in this study to describe the task processing time. Let $b$ represent the number of CPU cycles required to compute 1 bit of data, and $f_{i}$ (MHz) denote the computation capacity of server $i$. Given a task of size $y$ (Gbits), the time taken by server $i$ to process the task is $T_{i}^{comp}=y\gamma_{i}$, where $\gamma_{i}=\frac{b}{f_{i}}$ (s/Mbits) indicates the time taken by server $i$ to process one Gbit of data.

In this subsection, we present the mathematical formulation of the problem.

The master selects a set of CHs from set $\mathcal{N}_{0}$ for task offloading. To describe the selection of CHs, we introduce binary decision variables $o_{i}$, where $i\in\mathcal{N}_{0}$. The variable $o_{i}$ equals 1 if server $i$ is selected as a CH, and 0 otherwise.

After receiving tasks from the master, the CHs select their CMs for further task offloading. To describe the selection of CMs, we introduce decision variables $\boldsymbol{x}_{i}=[x_{i1},x_{i2},\ldots,x_{i|\mathcal{N}_{i}|}]$, where $i\in\mathcal{N}_{0}$ and $|\mathcal{N}_{i}|$ finds the cardinality of the set $\mathcal{N}_{i}$. $\boldsymbol{x}_{i}\in\mathbb{R}^{|\mathcal{N}_{i}|}$ is a binary vector, where its $j$-th element, $x_{ij}$, equals 1 if server $j$ is selected to join the cluster $i$, and 0 otherwise. The resulting cluster with CH $i\in\mathcal{N}_{0}$, denoted as $C_{i}$, is given by $C_{i}=\{j|x_{ij}=1,\forall j\in\mathcal{N}_{i}\}$.

Additionally, we introduce continuous decision variables $y_{i}\in\mathbb{R}_{\geq 0}$ to represent the size of the tasks offloaded to server $i$, where $i\in\mathcal{V}$. In case when $i=0$, $y_{0}$ indicates the size of the tasks processed at the master.

The time required for each server $i$ to receive its assigned tasks can then be expressed as:

Notably, if server $i$ is not selected for task offloading, the associated transmission delay is 0.

The total time required for each server $i$ to receive and process the assigned computation tasks is given by $\mathcal{J}_{i}=T_{i}^{tran}+T_{i}^{comp},i\in\mathcal{V}$, where $T_{i}^{comp}=y_{i}\gamma_{i}$. Here, we assume the generated results are small in size, making the transmission delay for sending them back to the master negligible, as is often assumed in existing studies (e.g., [20]). The total task completion time can then be written as $\mathcal{J}=\max\mathcal{J}_{i},\ \forall i\in\mathcal{V}$.

The objective of this study is to minimize the total task completion time by jointly optimizing the selection of CHs and CMs, and the task allocation, which is formulated as follows:

Constraints $C1$-$C3$ ensure that the decision variables take valid values. Constraints $C4$ ensure that clusters do not overlap. Constraints $C5$-$C6$ maintain the integrity of task sizes. It should be noted that solving this problem directly is challenging due to the nonlinear constraints $C4$.

In this phase, each server $i\in\mathcal{N}_{0}$ within the master’s communication range selects its CMs in a decentralized manner, forming a candidate cluster with itself as the CH. These candidate clusters will then be examined by the master in the cluster selection phase as detailed in the next subsection. Notably, this phase allows a server to join multiple clusters.

To select CMs, each server $i\in\mathcal{N}_{0}$ employs a forward selection mechanism, picking CMs from its neighbors $\forall j\in\mathcal{N}_{i}$ one by one until either no further performance gains can be achieved or all neighbors have been evaluated. In each iteration, the CH adds the neighboring server that maximally reduces the task processing time, assuming tasks of any size $y$ are assigned to server $i$. This selection is achieved by identifying the neighboring server with the highest processing capacity, defined as the time to receive and process a unit-sized task, and determining if its addition would reduce the overall task processing time. This is challenging, as a neighboring server’s processing capacity depends on the number of servers in the cluster due to shared bandwidth. Additionally, determining time savings from adding a server requires solving an optimization problem for task allocation. In the following, we first derive the processing capacity, denoted as $\alpha_{i}$.

Initially, the cluster $C_{i}$, with server $i\in\mathcal{N}_{0}$ as the CH, is empty. Therefore, when a neighboring server is added to the cluster, this server can utilize the entire bandwidth resource. Then, for each server $j\in\mathcal{F}=\mathcal{N}_{i}$ within $i$’s communication range, its processing capacity $\alpha_{j}$ can be derived as $\alpha_{j}=\gamma_{j}+\frac{1}{Blog_{2}(1+\beta_{ij}d_{ij}^{-2})},j\in\mathcal{F}$, where $\mathcal{F}$ denotes the set of neighboring servers that have not been added to the cluster. Nevertheless, in subsequent iterations, as the cluster $C_{i}$ becomes nonempty, a neighboring server $j\in\mathcal{F}$ can no longer utilize the entire bandwidth resource, and its processing capacity $\alpha_{j}$ is given by:

Notably, the processing capacity of the CH $i$ is always $\alpha_{i}=\gamma_{i}$ due to local computing.

To determine whether adding a neighboring server $j$ would reduce the task processing time, we define a performance indicator $\mathtt{I}$ that compares the minimum task processing time before and after the server is added. Specifically, consider cluster $C_{i}$ at the $k$-th iteration, for task $y$ assigned to server $i\in\mathcal{N}_{0}$, the minimum task processing time and the optimal task allocation can be derived by solving the following optimization problem:

where $J=\max_{l\in C_{i}\cup\{i\}}J_{l}$ is the task processing time and $J_{l}=y_{l}\alpha_{l}$ is the time required for server $l$ to receive and process its assigned task $y_{l}$. The performance indicator is then defined as $\mathtt{I}=\frac{J^{*}_{C_{i}}}{J^{*}_{C_{i}\cup\{j\}}}$, where $J^{*}_{C_{i}}$ and $J^{*}_{C_{i}\cup\{j\}}$ represent the minimum task processing time obtained before and after adding server $j\in\mathcal{F}$ to cluster $C_{i}$, respectively. Therefore, if $\mathtt{I}>1$, adding the server to the cluster will improve performance; otherwise, it will not.

To derive the formula for $\mathtt{I}$, we solve the above optimization problem, which leads to the following lemma, with the proof provided in the Appendix.

From the above lemma, we can derive that $J^{*}_{C_{i}}=y_{l}^{*}\alpha_{l}$ and $J^{*}_{C_{i}\cup\{j\}}=\bar{y}_{l}^{*}\bar{\alpha}_{l}=\bar{y}_{j}^{*}\bar{\alpha}_{j}$ for $l\in C_{i}\cup\{i\}$. Here, $\alpha_{l}$ and $\bar{\alpha}_{l}$ represent the processing capacities for server $l$ before and after adding server $j$ to cluster $C_{i}$, respectively, while $y^{*}_{l}$ and $\bar{y}^{*}_{l}$ denote the corresponding optimal task allocations. Therefore, we have $\mathtt{I}=\frac{y_{l}^{*}\alpha_{l}}{\bar{y}_{l}^{*}\bar{\alpha}_{l}}$. In this equation, the processing capacities $\alpha_{l}$ and $\bar{\alpha}_{l}$ can be readily computed using (2). Specifically, if $l\in C_{i}$, $\alpha_{l}=\gamma_{l}+\frac{|C_{i}|}{Blog_{2}(1+\beta_{il}d_{il}^{-2})}$ and $\bar{\alpha}_{l}=\gamma_{l}+\frac{|C_{i}|+1}{Blog_{2}(1+\beta_{il}d_{il}^{-2})}$; otherwise, if $l=i$, $\alpha_{i}=\bar{\alpha}_{i}=\gamma_{i}$. However, determining the optimal task allocations $y_{l}^{*}$ and $\bar{y}_{l}^{*}$ by solving $\mathcal{P}_{1}$ at each iteration is time-consuming. To address this issue, we introduce an iterative method to efficiently compute the values of $\mathtt{I}$, $y_{l}^{*}$ and $\bar{y}_{l}^{*}$.

Initially, $C_{i}$ is empty. Hence, we can easily obtain that $y_{i}^{*}=y$ before adding server $j$, and $\bar{y}^{*}_{i}=\frac{\bar{\alpha}_{j}y}{\bar{\alpha}_{i}+\bar{\alpha}_{j}}$, $\bar{y}^{*}_{j}=\frac{\bar{\alpha}_{i}y}{\bar{\alpha}_{i}+\bar{\alpha}_{j}}$ after adding server $j$ based on Lemma 1. Thus, $\mathtt{I}=\frac{\bar{\alpha}_{i}+\bar{\alpha}_{j}}{\bar{\alpha}_{i}}$. In subsequent iterations, to derive $\mathtt{I}$, we note the existence of following relationships:

which yields

Since $\bar{y}_{j}^{*}\bar{\alpha}_{j}=\bar{y}_{l}^{*}\bar{\alpha}_{l}$, $\mathtt{I}=\frac{y_{l}^{*}\alpha_{l}}{\bar{y}_{l}^{*}\bar{\alpha}_{l}}$, and $y_{l}^{*}\alpha_{l}=y_{i}^{*}\alpha_{i}$, we have

Combining (3c), (4), and (5), we can derive that

Since $y^{*}_{l}$ was obtained in the previous iteration, i.e., $y^{*(k)}_{l}=\bar{y}^{*(k-1)}_{l}$, where superscript $(k)$ indicates the iteration index, (6) can be readily computed. Moreover, once $\mathtt{I}$ is obtained, we can derive $\bar{y}_{l}^{*}$ by $\bar{y}_{l}^{*}=\frac{y_{l}^{*}\alpha_{l}}{\bar{\alpha_{l}}\mathtt{I}},\forall l\in C_{i}\cup\{i\}$, and $\bar{y}_{j}^{*}$ can be obtained by (4). Algorithm 1 summarizes the procedure.

In this phase, the master examines the candidate clusters formed in the LCF phase, selects the CHs and their associated CMs, and resolves any overlaps between clusters.

To select CHs, the master evaluates each server $i\in\mathcal{N}_{0}$ within its communication range, following a procedure similar to that of LCF. Particularly, in each iteration, the master identifies the neighboring server $i\in\mathcal{N}_{0}$ with the highest processing capacity and adds it to the set of CHs, denoted as $C_{0}$, if doing so would reduce task processing time. The iteration stops when no further reduction in processing is achievable or when all neighboring servers of the master have been examined.

Unlike the processing capacity defined for individual servers in the LCF phase, the processing capacity of each candidate CH $i\in\mathcal{N}_{0}$ here is defined as the time required for it and its CMs, as a team, to receive and process a unit-sized task. Specifically, for server $i$, the time to receive a unit-sized task from the master is $\frac{1}{R_{0i}}$. Moreover, once server $i$ receives this task, according to Lemma 1, the minimum time required for it and its CMs to process this task is $\frac{y_{i}^{*}\gamma_{i}}{y}$, where $y_{i}^{*}$ is the output of Algorithm 2. Therefore, the processing capacity of server $i\in\mathcal{N}_{0}$ in the GCF phase, denoted as $\eta_{i}$, is given by $\eta_{i}=\frac{y_{i}^{*}\gamma_{i}}{y}+\frac{1}{R_{0i}}$. Notably, the processing capacity of the master is $\eta_{0}=\gamma_{0}$.

Moreover, to assess whether adding server $i$ to the set of CHs, $C_{0}$, would improve performance, we use the same performance indicator $\mathtt{I}$, which can be computed similarly as detailed in the previous subsection. Particularly, at the $k$-th iteration, we have:

where $\eta_{l}$ and $\bar{\eta}_{l}$ denote the processing capacities of server $l\in C_{0}\cup\{0\}$ before and after adding server $i$ to the cluster $C_{0}$, and we have

when $l\in C_{0}\cup\{0\}$. $y^{*}_{l}$ and $\bar{y}^{*}_{l}$ denote the optimal task allocations before and after adding server $i$. Similarly, the updating equation for $\bar{y}_{l}^{*}$ is $\bar{y}_{l}^{*}=\frac{y_{l}^{*}\eta_{l}}{\bar{\eta_{l}}\mathtt{I}},\forall l\in C_{0}\cup\{0\}$, and we have:

To resolve any overlaps between clusters, the selected CH $i$ and its CMs are “removed” from the network at the end of each iteration and do not participate in subsequent iterations. At the start of each new iteration, the unselected neighbors of the master undergo the LCF phase to update their CMs, ensuring that clusters remain distinct and non-overlapping. Algorithm 3 outlines the core procedure of our approach, which constructs the three-layer tree topology $\mathcal{T}$ and determines the associated optimal task allocation $\{y^{*}_{l}\}_{\mathcal{T}}$.

We randomly generate and distribute servers within a $100\times 100$m area, with the exception of the master, which is fixed at the location $(20,20)$m. The computing power of each server $f_{i}$ is sampled from a uniform distribution over $[0.1,10]$ MHz, with $b$ set to $1$. The SNR ratio $\beta_{ij}$ is sampled from a uniform distribution over $[30,40]$dbm. The task size $Y$ is set to $100$Gbits, and the bandwidth $B$ is set to 50MHz. To evaluate the performance of our method, we compare it with the following three benchmarks:

• •

  Unequal Cluster (Unequal)[14]: This method selects CHs by comparing servers’ computing power; if two CHs are within each other’s communication range, the server with higher computing power is selected as the CH. CMs join the nearest CH.

• •

  Leach-C [21]: A centralized approach that calculates each server’s probability of being a CH based on computing power (originally, energy level was used), with the top servers selected as CHs. CMs join the CH with the highest received signal strength (originally, minimal communication energy was used).

• •

  LBAS [22]: CHs are selected using an iterative approach that considers distance, number of neighbors, and computing power, with higher-scoring servers selected as CHs. A similar procedure is applied to select CMs.

• •

  Dijkstra’s [8]: A tree topology is constructed by identifying the shortest routes with the least transmission delay from the master to each server using the Dijkstra’s algorithm. Servers more than two hops away are pruned.

Notably, these benchmarks only generate the tree topology $\mathcal{T}$. The associated optimal task allocation is derived using the same approach as ours.

In the first experiment, we compare the performance of different approaches across networks of varying sizes and topologies. Specifically, we examine a small-scale network with $N=20$ servers and a large-scale network with $N=100$ servers. For each network size, we randomly generate 10 different topologies by varying server locations, with each server’s communication range set to $50$ m. As shown in Fig. (1), our approach outperforms all benchmarks in both small-scale (Fig. 1) and large-scale networks (Fig. 1). The performance advantage is more pronounced in large-scale networks, due to the increase of servers that can potentially slow down processing if included without careful selection. Comparing the two figures, we can see that the task completion time generally decreases with the increase of the number of servers, due to more servers participating in computations.

In the second experiment, we compare the performance of different approaches under varying server communication ranges. Specifically, we consider $N=20$ servers distributed over the simulation area, as illustrated in Fig. 2. The communication range $\xi$ is configured to be the same for each server, and we vary $\xi$ from $10$m to $130$m. From Fig. 2, we can see that our approach outperforms all benchmarks and continues to improve as the communication range $\xi$ increases. This improvement occurs because, as $\xi$ grows, network connectivity strengthens as more servers within each other’s communication range. This expanded connectivity enables more servers to contribute to task processing, which, when properly selected, further reduces task completion time.