Enhancing Rate-Splitting-Based Distributed Edge Computing via Multi-Group Information Recycling

Abstract

To address the straggling effect in distributed edge computing, existing methods often introduce extra computation or communication costs. Recently, information recycling has emerged as an efficient solution that avoids such extra overhead. Nonetheless, the performance of the existing information recycling-assisted rate-splitting-based distributed edge computing scheme significantly hinges on the single common stream, whose rate is limited by the edge node (EN) with the worst channel quality. To this end, a multi-group information recycling scheme for rate-splitting-based distributed edge computing is proposed, where the ENs are clustered into multiple groups, each with its own common stream. In this way, the proposed scheme alleviates the communication limitation of a single common stream, thereby boosting the information recycling mechanism for promoted computation collaboration. A K-medoids-based grouping algorithm is designed for the general multi-antenna case, and a more efficient continuous partitioning-based grouping algorithm is proposed for the special case of single-antenna. Besides, a convex–concave procedure-based algorithm is developed to solve the corresponding latency optimization problem. Simulations demonstrate that the proposed scheme offers significant and robust advantages across various communication and computation conditions. In the considered scenarios, the proposed scheme can substantially reduce the processing latency by up to 51.0% compared to the conventional information recycling scheme.

1. Introduction

In recent years, edge computing has played an increasingly vital role in enhancing the quality of computational services [1,2]. However, the mounting scale of edge intelligence applications, (e.g., big data, augmented reality, and artificial intelligence) is pushing the limits of edge computing. These large-scale and computationally intensive tasks have rendered traditional single-node edge computing insufficient, entailing distributed edge computing, which has emerged as a promising computation paradigm [3,4,5]. This approach partitions and distributes the original large-scale and intensive tasks among multiple edge nodes (ENs), exploiting their computational resources for faster processing.

Nonetheless, the straggling effect presents a notable challenge in distributed edge computing. Specifically, some ENs, known as stragglers, may experience substantial delays or even fail to complete their tasks due to various factors, including hardware heterogeneity, imbalanced workload allocation, I/O contentions, and hardware failures [6,7,8]. This significantly degrades the overall performance, as the system needs to wait for feedback from all the ENs in distributed edge computing [9]. To alleviate the straggling issues, several strategies have been considered in the literature. One typical approach is task replication [10,11,12], where redundant copies of the original task are distributed across multiple ENs, and the execution delay is determined by the fastest EN despite some stragglers. Besides task replication, coded computing [8] has recently been advocated, where the partitioned subtasks are encoded into a set of coded subtasks via coding theory [13]. Thanks to the well-designed coding redundancy, the mobile user can reconstruct the original task result using the feedback from only a subset of ENs, thus avoiding the need to wait for stragglers. In addition, workload reallocation [14,15] is another commonly adopted method, which allows slower ENs to re-transmit part of their remaining workloads to other faster ENs to minimize the overall processing latency. Nevertheless, despite the effectiveness of these pioneering works in mitigating the straggling effect, they often introduce redundant computation or require additional data transmission, which may still limit the overall performance.

To handle straggling without incurring extra computation and communication costs, a physical-layer mechanism known as information recycling has been recently proposed [16], in view of the widespread employment of the spectrum-efficient non-orthogonal transmission techniques (e.g., rate-splitting multiple access (RSMA) [17,18] and power-domain non-orthogonal multiple access (NOMA) [19]) in distributed edge computing [20,21,22,23,24]. The key insight of information recycling is that, under many non-orthogonal transmission techniques involving successive interference cancellation (SIC), each EN has to decode part of the information intended for other ENs [25,26]. Instead of directly discarding this part of the information after interference cancellation, the information recycling mechanism proactively recycles this information (for free), by exploiting the SIC procedure. With the recycled information, faster ENs that complete their own task earlier can help execute the corresponding part of the task for the straggling ENs, instead of waiting for the straggling ENs, thereby mitigating the straggling effect without extra overhead. A concrete example of the information recycling mechanism has been proposed for rate-splitting-based distributed edge computing systems [16]. The performance of this conventional scheme heavily hinges on the single common stream in rate-splitting. Specifically, a larger common stream can increase the portion of tasks available for information recycling and thus promote computation collaboration. However, the rate of the common stream is fundamentally limited by the EN with the worst channel quality. This constraint undermines the benefits of information recycling, since enforcing a large common stream may aggravate the impact of the rate limitation on transmission, leading to sub-optimal communication performance. To the best of our knowledge, developing a new distributed edge computing scheme that can overcome the communication limitation of the single common stream remains an open challenge.

To this end, a novel scheme, coined as multi-group information recycling for rate-splitting-based distributed edge computing, is proposed in this work. Particularly, it will cluster the ENs into multiple groups and offer one common stream for each group, where collaborative computation can still be enabled through information recycling. Since each common stream is decoded by a smaller number of ENs, the communication bottleneck of the single common stream can be alleviated, thereby facilitating the common stream transmission. As a result, the information recycling mechanism can be further boosted, promoting computation collaboration among the ENs for processing latency reduction. The major contributions of this work are summarized as follows:

• A multi-group information recycling scheme for rate-splitting-based distributed edge computing is proposed in this work for processing latency reduction;
• To obtain a good EN grouping strategy, a K-medoids-based grouping algorithm is designed by jointly considering the channel alignment and the channel strength for the general multi-antenna case, and a more efficient continuous partitioning-based grouping algorithm is proposed for the special case of single-antenna;
• By exploiting the inherent structure of the corresponding latency optimization problem and bounding via difference of convex (DC) programming, a convex–concave procedure (CCCP)-based algorithm is developed to find a reasonably good solution.

The remainder of this paper is organized as follows. Related works are briefly reviewed in Section 2, and the system model and the conventional information recycling mechanism are presented in Section 3. In Section 4, the proposed scheme is presented, and the corresponding latency optimization problem is formulated. The latency optimization algorithms are developed in Section 5. Simulation results are presented in Section 6. Finally, conclusions and future works are discussed in Section 7.

Notations: ${\left(·\right)}^H$ denotes the Hermitian transpose. ${\mathbb{C}}^{a\times b}$ represents a complex matrix with dimension $a\times b$. $\mathcal{CN}\left(\mathbf{a},\mathbf{b}\right)$ represents the distribution of a circularly symmetric complex Gaussian random vector with mean vector $\mathbf{a}$ and covariance matrix $\mathbf{b}$. $\mathbb{E}\left[·\right]$ represents expectation. $\mathfrak{R}\left[·\right]$ obtains the real part of a complex number. $\left|·\right|$ is the absolute value. $\mathrm{tr}\left(·\right)$ is the trace.

2. Related Work

Several methods have been considered in the literature to mitigate the straggling effect in distributed edge computing, including task replication [10,11,12], coded computing [27,28,29], as well as workload reallocation [14,15]. For example, in [10], the original computation task is duplicated and assigned to multiple ENs so that the execution latency is determined by the fastest EN rather than the stragglers. The tradeoff between expected completion time and task replication ratio is explored in [11] to identify the optimal replication strategy for various computation straggling models. In [12], a balanced grouping replication strategy is further proposed, focusing on optimizing the redundancy level to minimize average job compute time while preserving task completion time predictability. In addition to task replication, coded computing has gained traction for the ability to mitigate straggling via coding theory [13]. Specifically, the maximum distance separable (MDS) codes are used in [27] for distributed task offloading. It is shown that MDS-coded offloading can effectively mitigate the straggling effect as the mobile user can reconstruct the original task result using feedback from only a subset of fast ENs. Besides, entangled polynomial codes are proposed in [28] to achieve the optimal tradeoff between the recovery threshold (i.e., the minimum number of ENs required to recover the original task) and the per-EN computation workload through different matrix partitioning. In [29], the impact of the coding parameter selection under different task execution models is investigated to alleviate the straggling effect and minimize the processing latency. Moreover, workload reallocation is another widely employed method for straggler mitigation. For instance, in [14], when a faster EN completes its task and becomes idle, part of the straggling ENs’ remaining workloads can be re-transmitted to this faster EN, thereby rebalancing workload and addressing straggling. In [15], by detecting straggling ENs continuously in the computation process, the mobile user can promptly reassign tasks to faster ENs, thereby minimizing idle time and improving overall system performance. Nevertheless, while these methods effectively mitigate the straggling effect, their performance remains constrained. Specifically, task replication and coded computing incur increased communication and computational costs, because replicated or coded subtasks are often larger than the subtasks in traditional distributed computing due to the introduced task redundancy. Besides, workload reallocation necessitates task data retransmission, which brings extra communication costs and limits the overall performance.

On the other hand, significant research has been conducted on strengthening communication in distributed edge computing using non-orthogonal transmission techniques. For instance, in [22], the computation subtasks are offloaded to the ENs via NOMA, and the processing latency is minimized by jointly optimizing transmission duration and workload allocation. In [23], the benefits of NOMA are investigated for both uplink and downlink transmissions in mobile edge computing. In [24], the total multi-user processing latency of an RSMA-based distributed edge computing system is optimized and the superiority of RSMA in serving distributed edge computing is manifested as compared to NOMA. However, most of these pioneering works mainly consider how non-orthogonal transmission strengthens the communication in distributed edge computing, while the straggling issue is largely ignored.

To handle straggling without incurring extra computation and communication costs, the information recycling mechanism is proposed in [16], which can be integrated into the non-orthogonal transmission techniques. In particular, by recycling the task information intended for other ENs in the decoded common stream, the faster ENs can help execute the corresponding part of the task for the slower ENs, thereby mitigating the straggling effect. However, the effectiveness of the existing information recycling-assisted distributed edge computing scheme highly hinges on the single common stream in rate-splitting and the rate of the common stream is inherently limited by the EN with the poorest channel quality. This constraint diminishes the advantages of information recycling, as dedicating resources to a single common stream can promote collaborative computation but may also degrade overall communication performance. In contrast to these pioneering works, by clustering ENs into multiple groups and transmitting several common streams, the proposed multi-group information recycling scheme can alleviate the single common stream’s communication limitation to facilitate the transmission of the common streams, thus promoting the information recycling mechanism for enhanced computation collaboration among the ENs.

3. System Model

In this section, the system model of rate-splitting-based distributed edge computing with stragglers will be presented, together with the conventional information recycling mechanism.

3.1. System Model

Consider a distributed edge computing system consisting of a mobile user and K ENs indexed by $\mathcal{K}=\{1,2,\dots ,K\}$. The mobile user wirelessly offloads its computation-intensive task $\mathcal{W}$ to these K ENs for faster processing. Specifically, the computation task W can be divided into K independent subtasks $\{W_1, W_2, \dots , W_K\}$ (Take (large-scale) matrix multiplication, a fundamental operation in many machine learning algorithms [30], as an example of the practical application. The original matrix multiplication task $\mathbf{Fb}$ will be partitioned into K sub-tasks {${\mathbf{F}}_1\mathbf{b}, {\mathbf{F}}_2\mathbf{b}, \dots , {\mathbf{F}}_K\mathbf{b}$} with ${\mathbf{F}}^T=\left[{\mathbf{F}}_1^T, {\mathbf{F}}_2^T, \dots , {\mathbf{F}}_K^T\right]$). Each sub-task $W_k$ will be offloaded to EN k for processing (As in the existing literature [1,23,31,32], it is assumed that the size of the computing results is much smaller compared to the offloaded subtasks, making the downlink transmission latency negligible).

3.1.1. Communication Phase

For better spectrum efficiency in communications, it is assumed that the mobile user employs RSMA to offload the subtasks to the K ENs during the communication phase. Specifically, each subtask $W_k$ is split into a common part $W_k^c$ and a private part $W_k^p$ (In the matrix multiplication, this corresponds to partition ${\mathbf{F}}_k$ along the rows into two parts, ${\mathbf{F}}_k^c$ and ${\mathbf{F}}_k^p$, where ${\mathbf{F}}_k^T=\left[{\mathbf{F}}_k^{c,T},{\mathbf{F}}_k^{c,T}\right]$). In the wireless physical layer, all the common parts $\{W_1^c, W_2^c, \dots , W_K^c\}$ are encoded into a single common stream $s^c$, while each private part $W_k^p$ is encoded into a private stream $s_k^p$. By employing superposition coding, the transmitted signal $\mathbf{x}$ from the mobile user is given by

$$\mathbf{x}={\mathbf{w}}^c{s}^c+{\sum }_{k\in \mathcal{K}}{\mathbf{w}}_k^p{s}_k^p,$$

(1)

where ${\mathbf{w}}^c\in {\mathbb{C}}^{N_t\times 1}$ and ${\mathbf{w}}_k^p\in {\mathbb{C}}^{N_t\times 1}$ are the precoding vectors for the common stream $s^c$ and the private stream $s_k^p$, respectively, with $N_t$ denoting the number of antennas of the mobile user. The received wireless signal $y_k$ at EN k can be expressed as

$$y_k={\mathbf{h}}_k^H\mathbf{x}+n_k,$$

(2)

where ${\mathbf{h}}_k\in {\mathbb{C}}^{N_t\times 1}$ represents the gain of the wireless channel between the mobile user and EN k, and $n_k\sim \mathcal{CN}(0,{\sigma }^2)$ is the corresponding additive white Gaussian noise. According to the decoding rules of rate-splitting [18], each EN k first decodes the common stream $s^c$ by treating the interference from all private streams as noise and then subtracts it from the received signal using SIC. Thereafter, EN k decodes its private stream $s_k^p$ by treating the remaining interference from the other private streams as noise. Hence, by plugging (1) into (2), the signal-to-interference-plus-noise ratios (SINRs) of the common stream $s^c$ and the private stream $s_k^p$ to EN k are, respectively, given by

$$\begin{array}{cc}\hfill & {\gamma }_k^c={\displaystyle \frac{{\left|{\mathbf{h}}_k^H{\mathbf{w}}^c\right|}^2}{{\sum }_{j\in \mathcal{K}}{\left|{\mathbf{h}}_k^H{\mathbf{w}}_j^p\right|}^2+{\sigma }^2}}, \forall k\in \mathcal{K},\hfill \end{array}$$

(3)

$$\begin{array}{cc}\hfill & {\gamma }_k^p={\displaystyle \frac{{\left|{\mathbf{h}}_k^H{\mathbf{w}}_k^p\right|}^2}{{\sum }_{j\in \mathcal{K}\setminus k}{\left|{\mathbf{h}}_k^H{\mathbf{w}}_j^p\right|}^2+{\sigma }^2}}, \forall k\in \mathcal{K}.\hfill \end{array}$$

(4)

With the above SINRs, the rates $R_k^p$’s of the private steams should admit

$$R_k^p\le B{log}_2(1+{\gamma }_k^p),\forall k\in \mathcal{K},$$

(5)

where B is the system bandwidth. To ensure that the common stream $s^c$ can be successfully decoded by all ENs, the rate $R^c$ of the common stream should admit

$$R^c\le {min}_{k\in \mathcal{K}}\left\{B{log}_2(1+{\gamma }_k^c)\right\}.$$

(6)

As the rate $R^c$ of the common stream is shared among all ENs to offload $\{W_1^c, W_2^c, \dots , W_K^c\}$, it has ${\sum }_{k=1}^K{R}_k^c=R^c$, where $R_k^c$ is the uplink transmission rate of the common part $W_k^c$ of subtask $W_k$. Hence, the overall uplink transmission rate $R_k$ to EN k is given by

$$R_k=R_k^c+R_k^p.$$

(7)

3.1.2. Computation Phase

In the computation phase, each EN k processes its received offloaded subtask $W_k$. To account for the straggling effect [8,9], the computation rate $C_k$ of EN k can be modeled as follows [29]

$$C_k=\overline{C}-{\Delta }_k.$$

(8)

Here, $\overline{C}={\displaystyle \frac{f_e}{\beta }}$ denotes the maximum computation rate of the ENs, where $f_e$ is the maximum processor frequency, and $\beta$ represents the number of CPU cycles required to process one bit of data. ${\Delta }_k$ is a non-negative random variable representing the degradation in computation capability due to the straggling effect. The variables ${\left\{{\Delta }_k\right\}}_{k=1}^K$ are assumed to be independent and identically distributed (i.i.d.).

3.2. Conventional Information Recycling

The idea of conventional information recycling for rate-splitting-based distributed edge computing [16] is introduced in the sequel. According to the rate-splitting transmission principle [18], each EN k will decode the task messages $\left\{W_1^c,\dots ,W_{k-1}^c,W_{k+1}^c,\dots ,W_K^c\right\}$ intended for other ENs when decoding the common stream $s^c$ to obtain its own message $W_k$. In conventional distributed computing, after decoding, these messages will be discarded directly. As a result, each EN can only compute its own subtask $W_k$, and the faster EN that completes its own task earlier can do nothing but wait for the straggling ENs. As shown in Figure 1a, both EN 1 and EN 3 can do nothing but wait for the straggling EN 3 and remain idle, which undoubtedly wastes the computation capability of the system. In contrast, the information recycling mechanism enables the ENs to proactively recycle the messages $\left\{W_1^c,\dots ,W_{k-1}^c,\right.$$\left.W_{k+1}^c,\dots ,W_K^c\right\}$, as shown in Figure 1b. In this way, each EN will have full knowledge of the common parts $\{W_1^c,W_2^c,\dots ,W_K^c\}$ of all the subtasks ${\left\{W_k\right\}}_{k=1}^K$. When a certain EN i is straggling, another faster EN j can help compute (the common part of) its subtask based on the recycled information $W_i^c$.

The specific process of collaborative computing for the common parts is introduced as follows and summarized in Algorithm 1. Each common part task $W_k^c$ is divided into $A_k$ mini-tasks ${\left\{W_{k,u}^c\right\}}_{u=1}^{A_k}$, where $A_k=⌈{\displaystyle \frac{D_k^c}{D_m}}⌉$. In the matrix multiplication, each common part ${\mathbf{F}}_k^c$ is further partitioned along the rows into $A_k$ smaller parts $\left\{{\mathbf{F}}_{k,1}^c,{\mathbf{F}}_{k,2}^c,\dots ,{\mathbf{F}}_{k,A_k}^c\right\}$ to form mini-tasks ${\left\{{\mathbf{F}}_{k,u}^c\mathbf{b}\right\}}_{u=1}^{A_k}$, where ${\mathbf{F}}_k^{c,T}=\left[{\mathbf{F}}_{k,1}^{c,T},{\mathbf{F}}_{k,2}^{c,T},\dots ,{\mathbf{F}}_{k,A_k}^{c,T}\right]$. Here, $D_k^c$ and $D_m$ are the sizes of the task $W_k^c$ and each mini-task, respectively, (note that $D_m$ is a parameter determined during the engineering implementation process; therefore, its specifics are beyond the scope of this paper). The system also maintains an ordered task queue for each EN k, which is initialized as ${\left\{W_{k,u}^c\right\}}_{u=1}^{A_k}$. Each EN sequentially processes the mini-tasks according to their queuing order. Upon completing the mini-task $W_{k,u}^c$, EN j sends a finishing signal $S_{k,u}^{\mathrm{fin}}$ to inform the mobile user. Besides, whenever a certain EN j completes all its assigned mini-tasks and the overall computation task has not yet been finished, it can assist other straggling ENs in computing their mini-tasks by information recycling. Specifically, if straggling EN i has the longest unfinished task queue at the current time, and task $W_{k,v}^c$ at the end of its task queue, the mobile user will send a recycling signal $S_{k,v}^{\mathrm{rec}}$ to EN j and a canceling signal $S_{k,v}^{\mathrm{can}}$ to EN i. The signals $S_{k,v}^{\mathrm{rec}}$ and $S_{k,v}^{\mathrm{can}}$ direct EN j to begin computing $W_{k,v}^c$ using information recycling and EN i to remove $W_{k,v}^c$ from its task queue, respectively. This collaboration continues until the overall computation task is completed, allowing fast ENs and slow ENs to collaboratively compute the common parts $\{W_1^c,W_2^c,\dots ,W_K^c\}$. An illustrative example is depicted in Figure 2. With the information recycling mechanism enabling computation collaboration, theoretically, the computation capabilities of all ENs can be captured for the computation of $\left\{W_1^c,W_2^c,\dots ,W_K^c\right\}$ and the overall computation rate $C^{\mathrm{rec}}$ can be made to

$$C^{\mathrm{rec}}={\sum }_{k=1}^K{C}_k.$$

(9)

Algorithm 1 The collaborative computing process of information recycling

1: Initialize: For each EN k, divide the common part $W_k^c$ into mini-tasks and initialize the ordered task queue ${\left\{W_{k,u}^c\right\}}_{u=1}^{A_k}$; 2: Each EN starts to sequentially process the mini-tasks according to their queuing order; 3: while The overall computation task is not completed do 4:   for $j=1\dots K$ do 5:    if EN j completes a mini-task $W_{k,u}^c$ then 6:      EN j sends a finishing signal $S_{k,u}^{\mathrm{fin}}$ to the mobile user; 7:    end if 8:    if EN j receives a recycling signal $S_{k,v}^{\mathrm{rec}}$ then 9:      EN j adds $W_{k,v}^c$ to its task queue and begins computing $W_{k,v}^c$ via information recycling; 10:    end if 11:    if EN j receives a canceling signal $S_{k,v}^{\mathrm{can}}$ then 12:      EN j removes $W_{k,v}^c$ from its task queue; 13:    end if 14:   end for 15:   if The mobile user receives a finishing signal $S_{k,u}^{\mathrm{fin}}$ from EN j and determines that EN j has completed all assigned mini-tasks then 16:    Finding the EN i with the longest unfinished task queue, and task $W_{k,v}^c$ at the end of its task queue, the mobile user sends a recycling signal $S_{k,v}^{\mathrm{rec}}$ to EN j and a canceling signal $S_{k,v}^{\mathrm{can}}$ to EN i; 17:   end if 18: end while

4. Proposed Multi-Group Information Recycling

4.1. Multi-Group Information Recycling Scheme

The performance of the conventional information recycling assisted distributed edge computing highly depends on the single common stream [16]. Specifically, when more resources are allocated to the common stream, the common parts $\left\{W_1^c,W_2^c,\dots ,W_K^c\right\}$ will occupy a larger portion of the task, thus facilitating the information recycling mechanism for straggler mitigation. Nonetheless, enforcing a too-strong common stream may not be necessarily good for communication, as the rate of the common stream $s^c$ is restricted by the EN with the worst channel quality. This may offset the performance gain brought by the information recycling mechanism. For this reason, a new information recycling scheme that can overcome the communication limitation of the single common stream is required. To this end, a multi-group information recycling scheme is proposed for rate-splitting-based distributed edge computing below.

Assume that the K ENs are divided into G mutually-exclusive groups and each group g contains ${\mathcal{K}}_g$ ENs with ${\bigcup }_{g\in \mathcal{G}}{\mathcal{K}}_g=\mathcal{K}$. For the communication phase, as shown in Figure 3a, the common parts $\left\{W_k^c|k\in {\mathcal{K}}_g\right\}$ of the ENs in each group g are combined as $W_{{\mathcal{K}}_g}^c$ and encoded into the common stream $s_{{\mathcal{K}}_g}^c$ in the wireless layer. Meanwhile, the private part $W_k^p$ is still encoded into $s_k^p$. By employing superposition coding, the transmitted signal $\mathbf{x}$ from the mobile user is given by

$$\mathbf{x}=\sum _{g\in \mathcal{G}}{\mathbf{w}}_{{\mathcal{K}}_g}^c{s}_{{\mathcal{K}}_g}^c+\sum _{k\in \mathcal{K}}{\mathbf{w}}_k^p{s}_k^p,$$

(10)

where ${\mathbf{w}}_{{\mathcal{K}}_g}^c\in {\mathbb{C}}^{N_t\times 1}$ is the precoding vector for the common stream $s_{{\mathcal{K}}_g}^c$. By plugging (10) into (2), the received signal $y_k$ at EN k is given by

$$y_k=\sum _{g\in \mathcal{G}}{\mathbf{h}}_k^H{\mathbf{w}}_{{\mathcal{K}}_g}^c{s}_{{\mathcal{K}}_g}^c+\sum _{j\in \mathcal{K}}{\mathbf{h}}_k^H{\mathbf{w}}_k^p{s}_j^p+n_k.$$

(11)

The decoding procedure of EN k in group g (i.e., $k\in {\mathcal{K}}_g$) is performed as follows: EN k in group g decodes its common stream $s_{{\mathcal{K}}_g}^c$ by treating other common streams and all private streams as interference and removes it from the received signal using SIC. Thereafter, EN k decodes its private stream $s_k^p$ by treating the other common streams and private streams as interference. Accordingly, the signal-to-interference-plus-noise ratios (SINRs) of the common stream $s_{{\mathcal{K}}_g}^c$ and the private stream $s_k^p$ to EN k in group g are given as follows

$$\begin{array}{cc}\hfill & {\gamma }_{{\mathcal{K}}_g,k}^c={\displaystyle \frac{{\left|{\mathbf{h}}_k^H{\mathbf{w}}_{{\mathcal{K}}_g}^c\right|}^2}{{\displaystyle \sum _{g^{\prime }\in \mathcal{G},g^{\prime }\ne g}}{\left|{\mathbf{h}}_k^H{\mathbf{w}}_{{\mathcal{K}}_{g^{\prime }}}^c\right|}^2+{\displaystyle \sum _{j\in \mathcal{K}}}{\left|{\mathbf{h}}_k^H{\mathbf{w}}_j^p\right|}^2+{\sigma }^2}},g\in \mathcal{G},k\in {\mathcal{K}}_g,\hfill \end{array}$$

(12)

$$\begin{array}{cc}\hfill & {\gamma }_k^p={\displaystyle \frac{{\left|{\mathbf{h}}_k^H{\mathbf{w}}_k^p\right|}^2}{{\displaystyle \sum _{g^{\prime }\in \mathcal{G},g^{\prime }\ne g}}{\left|{\mathbf{h}}_k^H{\mathbf{w}}_{{\mathcal{K}}_{g^{\prime }}}^c\right|}^2+{\displaystyle \sum _{j\in \mathcal{K},j\ne k}}{\left|{\mathbf{h}}_k^H{\mathbf{w}}_j^p\right|}^2+{\sigma }^2}},k\in \mathcal{K}.\hfill \end{array}$$

(13)

With the above SINRs, the achievable rate $R_k^p$ of the private stream $s_k^p$ admits

$$R_k^p\le B{log}_2\left(1+{\gamma }_k^p\right),\forall k\in \mathcal{K}.$$

(14)

To ensure that each common stream $s_{{\mathcal{K}}_g}^c$ can be successfully decoded by the ENs in group g, the achievable rate $R_{{\mathcal{K}}_g}^c$ of the common stream $s_{{\mathcal{K}}_g}^c$ should admit

$$R_{{\mathcal{K}}_g}^c\le \underset{k\in {\mathcal{K}}_g}{min}\left\{B{log}_2\left(1+{\gamma }_{{\mathcal{K}}_g,k}^c\right)\right\},\forall g\in \mathcal{G}.$$

(15)

For the computation phase, as shown in Figure 3b, the ENs in each group g will first collaboratively compute the common parts $\left\{W_k^c|k\in {\mathcal{K}}_g\right\}$ with information recycling. Next, each EN k will compute its private part $W_k^p$ independently.

Remark 1. 

In the proposed scheme, each common stream $s_{{\mathcal{K}}_g}^c$ is decoded by a smaller number of ENs instead of all ENs. As a result, the communication bottleneck of the single common stream can be alleviated, which allows more resources to be allocated to form stronger common streams. Consequently, the size of the common parts $\left\{W_1^c,W_2^c,\dots ,W_K^c\right\}$ can be increased, thereby boosting the advantage of information recycling.

4.2. Problem Formulation

As presented before, the original task W with size D will finally be converted into G combined common parts $\left\{W_{{\mathcal{K}}_1}^c,W_{{\mathcal{K}}_2}^c,\dots ,W_{{\mathcal{K}}_G}^c\right\}$ and K private parts $\left\{W_1^p,W_2^p,\dots ,W_K^p\right\}$ for transmission. The uplink transmission time $T_{u,{\mathcal{K}}_g}^c$ of the combined common part $W_{{\mathcal{K}}_g}^c$ is given by

$$T_{u,{\mathcal{K}}_g}^c={\displaystyle \frac{D_{{\mathcal{K}}_g}^c}{R_{{\mathcal{K}}_g}^c}},$$

(16)

where $D_{{\mathcal{K}}_g}^c$ is the size of $W_{{\mathcal{K}}_g}^c$. The uplink transmission time $T_{u,k}^p$ of the private part $W_k^p$ of the EN k is given by

$$T_{u,k}^p={\displaystyle \frac{D_k^p}{R_k^p}},$$

(17)

where $D_k^p$ is the size of $W_k^p$. As the common streams and the private streams are transmitted concurrently, the overall uplink transmission time $T_u$ should admit

$$T_u\ge max\left\{\underset{g\in \mathcal{G}}{max}{T}_{u,{\mathcal{K}}_g}^c,\underset{k\in \mathcal{K}}{max}{T}_{u,k}^p\right\}=max\left\{\underset{g\in \mathcal{G}}{max}{\displaystyle \frac{D_{{\mathcal{K}}_g}^c}{R_{{\mathcal{K}}_g}^c}},\underset{k\in \mathcal{K}}{max}{\displaystyle \frac{D_k^p}{R_k^p}}\right\}.$$

(18)

In the computation phase, the ENs in each group g will first collaboratively compute the combined common part $W_{{\mathcal{K}}_g}^c=\left\{W_k^c|k\in {\mathcal{K}}_g\right\}$. By (9), the corresponding computation latency $T_{e,{\mathcal{K}}_g}^c$ in group g is given by

$$T_{e,{\mathcal{K}}_g}^c={\displaystyle \frac{D_{{\mathcal{K}}_g}^c}{{\sum }_{k\in {\mathcal{K}}_g}{C}_k}}+\eta ,$$

(19)

where $\eta$ is the cost for the signaling transmission (c.f., Section 3.2). Next, the ENs in group g start to compute their own private part, and the computation latency $T_{e,k}^p$ of the private part $W_k^p$ is given by

$$T_{e,k}^p={\displaystyle \frac{D_k^p}{C_k}}.$$

(20)

Accordingly, the computation latency $T_{e,{\mathcal{K}}_g}^p$ for the private parts in group g is given by

$$T_{e,{\mathcal{K}}_g}^p=\underset{k\in {\mathcal{K}}_g}{max}\left\{{\displaystyle \frac{D_k^p}{C_k}}\right\}.$$

(21)

Hence, the overall latency $T_e$ for the total computation phase is given by

$$T_e=\underset{g\in \mathcal{G}}{max}\left\{T_{e,{\mathcal{K}}_g}^c+T_{e,{\mathcal{K}}_g}^p\right\}=\underset{g\in \mathcal{G}}{max}\left\{{\displaystyle \frac{D_{{\mathcal{K}}_g}^c}{{\sum }_{k\in {\mathcal{K}}_g}{C}_k}}+\eta +\underset{k\in {\mathcal{K}}_g}{max}\left\{{\displaystyle \frac{D_k^p}{C_k}}\right\}\right\}.$$

(22)

Based on the above, the expected latency minimization problem can be formulated as follows

$$\begin{array}{cc}\hfill {\mathcal{P}}_1:\underset{\mathcal{N},\mathbf{w},\mathbf{D},\mathbf{R}}{min}& T_u+\mathbb{E}\left[T_e\right]\hfill \\ \hfill \mathrm{s}.\mathrm{t}.& \left(14\right), \left(15\right), \left(18\right), \left(22\right),\hfill \end{array}$$

$$\begin{array}{cc}\hfill & \sum _{g\in \mathcal{G}}{D}_{{\mathcal{K}}_g}^c+\sum _{k\in \mathcal{K}}{D}_k^p=D,\hfill \end{array}$$

(23)

$$\begin{array}{cc}\hfill & tr\left(\mathbf{w}{\mathbf{w}}^H\right)\le P_t,\hfill \end{array}$$

(24)

$$\begin{array}{cc}\hfill & \bigcup _{g\in \mathcal{G}}{\mathcal{K}}_g=\mathcal{K},\hfill \end{array}$$

(25)

$$\begin{array}{cc}\hfill & {\mathcal{K}}_i\cap {\mathcal{K}}_j=\varnothing ,\forall i,j\in \mathcal{G},\hfill \end{array}$$

(26)

where $\mathcal{N}=\left[{\mathcal{K}}_1,{\mathcal{K}}_2,\dots ,{\mathcal{K}}_G\right],\mathbf{w}=\left[{\mathbf{w}}_{{\mathcal{K}}_1}^c,{\mathbf{w}}_{{\mathcal{K}}_2}^c,\dots ,{\mathbf{w}}_{{\mathcal{K}}_G}^c,{\mathbf{w}}_1^p,{\mathbf{w}}_2^p,\dots ,{\mathbf{w}}_K^p\right],\mathbf{D}=\left[D_{{\mathcal{K}}_1}^c,D_{{\mathcal{K}}_2}^c,\right.\left.\dots ,D_{{\mathcal{K}}_G}^c,D_1^p,D_2^p,\dots ,D_K^p\right]$, and $\mathbf{R}=\left[R_{{\mathcal{K}}_1}^c,R_{{\mathcal{K}}_2}^c,\dots ,R_{{\mathcal{K}}_G}^c,R_1^p,R_2^p,\dots ,R_K^p\right]$ are compact representations of the corresponding variables. The expectation in ${\mathcal{P}}_1$ is over the randomness of the computation rates ${\left\{C_k\right\}}_{k=1}^K$ of the ENs (c.f. (8)). Constraint (24) restricts the total transmit power of the mobile user to $P_t$.

5. Optimization Algorithm

Since the original problem ${\mathcal{P}}_1$ is a non-convex combinatorial problem involving random variables, it turns out to be quite challenging to solve it directly. To this end, the optimization of the problem ${\mathcal{P}}_1$ is suboptimally decomposed into two steps: deriving an effective grouping strategy, and optimizing the rest of the variables under the given grouping strategy.

5.1. EN Grouping

The optimal grouping strategy can be identified by exhaustively searching through all potential grouping strategies $\mathcal{N}$’s. However, this brute-force approach is computationally infeasible due to its prohibitively high complexity, which scales approximately as $O\left(G^K\right)$. To this end, alternative methods can be employed to derive a sub-optimal grouping strategy with significantly lower complexity. Intuitively, if EN i and EN j exhibit sufficiently different channel conditions, clustering them together and transmitting a shared common stream will likely harm the communication rate due to the mismatch in their channel characteristics. Hence, it is essential to design an algorithm that can cluster ENs based on channel similarity to obtain a good grouping strategy. With this consideration, a K-medoids [33] based grouping algorithm is designed by jointly considering the channel alignment and the channel strength for the general multi-antenna case (It is worth noting that other heuristic clustering algorithms, such as K-means [34], can also be used for EN grouping in the proposed scheme). Besides, a more efficient continuous partitioning-based grouping algorithm is proposed for the special case of single-antenna.

Remark 2. 

As collaborated by the simulation results in Section 6, both the K-medoids-based grouping algorithm and the continuous partitioning-based grouping algorithm can lead to a reasonably good grouping strategy.

For the K-medoids-based grouping algorithm, both channel strength and channel alignment are jointly considered to assess the similarity between the channel characteristics of different ENs. Accordingly, the distance of the EN i and j is defined as

$$d\left(i,j\right)=l\left|{\displaystyle \frac{{\parallel {\mathbf{h}}_i\parallel }_2-{\parallel {\mathbf{h}}_j\parallel }_2}{max\{{∥{\mathbf{h}}_i∥}_2,{∥{\mathbf{h}}_j∥}_2\}}}\right|+(1-l)\left(1-{\displaystyle \frac{{∥{\mathbf{h}}_i^H{\mathbf{h}}_j∥}_2}{{\parallel {\mathbf{h}}_i\parallel }_2{\parallel {\mathbf{h}}_j\parallel }_2}}\right),$$

(27)

where $l\in \left[0,1\right]$ is a weighting parameter; the first term and the second term account for the channel similarity in magnitude and direction, respectively.

Remark 3. 

The intuition of (22) is the following: as shown in (12) and (15), decreasing the variation in channel strengths within each group positively impacts the transmission of common streams. Similarly, reducing differences in channel alignment yields comparable benefits.

With this distance metric, the standard K-medoids clustering algorithm can be applied, yielding a grouping strategy with complexity $O\left(K^{2}G\right)$ [33]. The K-medoids-based grouping algorithm has significantly lower complexity compared to the naive brute-force search while achieving a reasonable performance for problem ${\mathcal{P}}_1$. The specific process is summarized in Algorithm 2.

Algorithm 2 K-medoids-based grouping algorithm

Input:  Channel state information $\{{\mathbf{h}}_1,{\mathbf{h}}_2,\dots ,{\mathbf{h}}_K\}$, number of groups G, distance metric $d(i,j)$; Output:  Groups $\left\{{\mathcal{K}}_1,{\mathcal{K}}_2,\dots ,{\mathcal{K}}_G\right\}$; 1: Randomly select G ENs $\mathcal{M}=\{M_1,M_2,\dots ,M_G\}$ as the initial medoids and set ${\mathcal{M}}^{\prime }=\mathcal{M}$; 2: repeat 3:   Set $\mathcal{M}={\mathcal{M}}^{\prime }$ and ${\mathcal{K}}_g=\varnothing ,\forall g\in \mathcal{G}$; 4:   for $i=1,\dots ,K$ do 5:    Compute $j=arg{min}_{j\in \mathcal{G}}d(i,M_j)$ and Set ${\mathcal{K}}_j$ = ${\mathcal{K}}_j\bigcup \left\{i\right\}$; 6:   end for 7:   for $g=1,\dots ,G$ do 8:    Select a new medoid $M_g^{\prime }$ that minimizes the total intra-group distance: $M_g^{\prime }=arg{min}_{j\in {\mathcal{K}}_g}{\sum }_{i\in {\mathcal{K}}_g}d(i,j)$; 9:   end for 10: until $\mathcal{M}={\mathcal{M}}^{\prime }$

In the single-antenna case, besides the K-medoids-based grouping algorithm, a more efficient continuous partitioning-based grouping algorithm is further proposed. Specifically, in this case, the channel alignment term in the distance metric becomes irrelevant, focusing solely on channel strength. Without loss of generality, assume that the channel strengths of all ENs satisfy $\left|h_1\right|\le \left|h_2\right|\le \dots \le \left|h_K\right|$. The continuous partition-based grouping algorithm defines each group g as ${\mathcal{K}}_g=\left\{c_{g-1}+1,c_{g-1}+2,\dots ,c_g\right\}$, where $c_0=0<c_1<\dots <c_{g-1}<c_g=K$. By selecting different values for $\left\{c_1,c_2,\dots c_{g-1}\right\}$ from the set $\left\{1,2,\dots ,K-1\right\}$, this algorithm can generate $\left({\displaystyle \genfrac{}{}{0pt}{}{K-1}{G-1}}\right)$ candidate strategies, denoted as $\mathcal{C}$. Besides, through searching through all grouping strategies in $\mathcal{C}$, the continuous partitioning-based grouping algorithm can also achieve a good performance with much lower complexity than the brute-force search approach. In particular, this algorithm can achieve the same performance as the naive brute-force search approach in a special case of problem ${\mathcal{P}}_1$, where $D_k^p=D_1^p,\forall k\in \mathcal{K}$. The latency optimization problem of this special case can be formulated as follows

$$\begin{array}{cc}\hfill {\mathcal{P}}_2:\underset{\mathcal{N},\mathbf{w},\mathbf{D},\mathbf{R}}{min}& T_u+\mathbb{E}\left[T_e\right]\hfill \\ \hfill \mathrm{s}.\mathrm{t}.& \left(14\right), \left(15\right), \left(18\right), \left(22\right), \left(23\right), \left(24\right), \left(25\right), \left(26\right),\hfill \end{array}$$

$$\begin{array}{cc}\hfill & D_k^p=D_1^p,\forall k\in \mathcal{K}.\hfill \end{array}$$

(28)

Proposition 1. 

For problem ${\mathcal{P}}_2$, the optimal grouping strategy belongs to $\mathcal{C}$.

Proof. 

Please see Appendix A.    □

5.2. Optimization Algorithm with Given Grouping

In this subsection, the optimization algorithm with a given grouping strategy $\mathcal{N}$ will be introduced. Specifically, consider the following problem

$$\begin{array}{cc}\hfill {\mathcal{P}}_3:\underset{\mathbf{w},\mathbf{D},\mathbf{R}}{min}& T_u+\mathbb{E}\left[T_e\right]\hfill \\ \hfill \mathrm{s}.\mathrm{t}.& \left(14\right), \left(15\right), \left(18\right), \left(22\right), \left(23\right), \left(24\right).\hfill \end{array}$$

(29)

In the objective function of ${\mathcal{P}}_3$, due to the randomness of the computation capabilities $C_k$’s, it turns out to be difficult to find $\mathbb{E}\left[T_e\right]$ in a closed form. To this end, by (22), a lower bound of the objective function can be obtained as follows

$$\begin{array}{cc}\hfill & T_u+\mathbb{E}\left[T_e\right]\hfill \\ \hfill \ge & T_u+\underset{g\in \mathcal{G}}{max}\left\{\mathbb{E}\left[{\displaystyle \frac{D_{{\mathcal{K}}_g}^c}{{\sum }_{k\in {\mathcal{K}}_g}{C}_k}}+\eta +\underset{k\in {\mathcal{K}}_g}{max}\left\{{\displaystyle \frac{D_k^p}{C_k}}\right\}\right]\right\}\hfill \\ \hfill \ge & T_u+\underset{g\in \mathcal{G}}{max}\left\{\mathbb{E}\left[{\displaystyle \frac{D_{{\mathcal{K}}_g}^c}{{\sum }_{k\in {\mathcal{K}}_g}{C}_k}}+\eta \right]+\underset{k\in {\mathcal{K}}_g}{max}\left\{\mathbb{E}\left[{\displaystyle \frac{D_k^p}{C_k}}\right]\right\}\right\}.\hfill \end{array}$$

(30)

Accordingly, the following optimization problem will be considered in the sequel

$$\begin{array}{cc}\hfill {\mathcal{P}}_4:\underset{\mathbf{w},\mathbf{D},\mathbf{R}}{min}& T_u+\underset{g\in \mathcal{G}}{max}\left\{\mathbb{E}\left[{\displaystyle \frac{D_{{\mathcal{K}}_g}^c}{{\sum }_{k\in {\mathcal{K}}_g}{C}_k}}+\eta \right]+\underset{k\in {\mathcal{K}}_g}{max}\left\{\mathbb{E}\left[{\displaystyle \frac{D_k^p}{C_k}}\right]\right\}\right\}\hfill \\ \hfill \mathrm{s}.\mathrm{t}.& \left(14\right), \left(15\right), \left(18\right), \left(23\right), \left(24\right).\hfill \end{array}$$

(31)

Remark 4. 

As corroborated by the simulation results, using the solution obtained by optimizing this lower bound, a quite good expected processing latency can be achieved for ${\mathcal{P}}_1$.

By introducing the auxiliary variables $\mathbf{t}=\left[t_e,t_{e,{\mathcal{K}}_1},\dots ,t_{e,{\mathcal{K}}_G}\right]$, problem ${\mathcal{P}}_4$ can be readily transformed into the following equivalent problem

$$\begin{array}{cc}\hfill {\mathcal{P}}_5:\underset{\mathbf{w},\mathbf{D},\mathbf{R},\mathbf{t}}{min}& T_u+t_e\hfill \\ \hfill \mathrm{s}.\mathrm{t}.& \left(14\right), \left(15\right), \left(18\right), \left(23\right), \left(24\right),\hfill \end{array}$$

$$\begin{array}{cc}\hfill & t_e\ge t_{e,{\mathcal{K}}_g},\forall g\in \mathcal{G},\hfill \end{array}$$

(32)

$$\begin{array}{cc}\hfill & t_{e,{\mathcal{K}}_g}\ge \mathbb{E}\left[{\displaystyle \frac{D_{{\mathcal{K}}_g}^c}{{\sum }_{k\in {\mathcal{K}}_g}{C}_k}}+\eta \right]+\mathbb{E}\left[{\displaystyle \frac{D_k^p}{C_k}}\right],\forall k\in {\mathcal{K}}_g.\hfill \end{array}$$

(33)

In the sequel, the non-convex problem ${\mathcal{P}}_5$ will be first transformed into a DC programming problem. In particular, by introducing the auxiliary variables $\mathit{\nu }=\left\{{\nu }_{{\mathcal{K}}_g,k}^c,{\nu }_k^p|\forall g\in \mathcal{G},\forall k\in {\mathcal{K}}_g\right\}$ to ${\mathcal{P}}_5$, constraints (14) and (15) can be equivalently written as

$$\left\{\begin{array}{}\mathrm{(34)}& R_{{\mathcal{K}}_g}^c\le B{log}_2{\nu }_{{\mathcal{K}}_g,k}^c,\forall g\in \mathcal{G},k\in {\mathcal{K}}_g,\hfill \mathrm{(35)}& R_k^p\le B{log}_2{\nu }_k^p,\forall k\in \mathcal{K},\hfill \mathrm{(36)}& {\nu }_{{\mathcal{K}}_g,k}^c\le 1+{\gamma }_{{\mathcal{K}}_g,k}^c,\forall g\in \mathcal{G},\forall k\in {\mathcal{K}}_g,\hfill \mathrm{(37)}& {\nu }_k^p\le 1+{\gamma }_k^p,\forall k\in \mathcal{K}.\hfill \end{array}\right.$$

By invoking (12) and (13), (36) and (37) can be further transformed into the following DC form

$$\begin{array}{cc}\hfill & \sum _{g^{\prime }\in \mathcal{G},g^{\prime }\ne g}{\left|{\mathbf{h}}_k^H{\mathbf{w}}_{{\mathcal{K}}_{g^{\prime }}}^c\right|}^2+\sum _{j\in \mathcal{K}}{\left|{\mathbf{h}}_k^H{\mathbf{w}}_j^p\right|}^2+{\sigma }^2-{\displaystyle \frac{{\displaystyle \sum _{g^{\prime }\in \mathcal{G}}}{\left|{\mathbf{h}}_k^H{\mathbf{w}}_{{\mathcal{K}}_{g^{\prime }}}^c\right|}^2+{\displaystyle \sum _{j\in \mathcal{K}}}{\left|{\mathbf{h}}_k^H{\mathbf{w}}_j^p\right|}^2+{\sigma }^2}{{\nu }_{{\mathcal{K}}_g,k}^c}}\le 0,\hfill \end{array}$$

$$\begin{array}{c}\forall g\in \mathcal{G},k\in {\mathcal{K}}_g,\hfill \end{array}$$

(38)

$$\begin{array}{cc}\hfill & \sum _{g^{\prime }\in \mathcal{G},g^{\prime }\ne g}{\left|{\mathbf{h}}_k^H{\mathbf{w}}_{{\mathcal{K}}_{g^{\prime }}}^c\right|}^2+{\displaystyle \sum _{j\in \mathcal{K},j\ne k}}{\left|{\mathbf{h}}_k^H{\mathbf{w}}_j^p\right|}^2+{\sigma }^2-{\displaystyle \frac{{\displaystyle \sum _{g^{\prime }\in \mathcal{G},g^{\prime }\ne g}}{\left|{\mathbf{h}}_k^H{\mathbf{w}}_{{\mathcal{K}}_{g^{\prime }}}^c\right|}^2+{\displaystyle \sum _{j\in \mathcal{K}}}{\left|{\mathbf{h}}_k^H{\mathbf{w}}_j^p\right|}^2+{\sigma }^2}{{\nu }_k^p}}\le 0,\hfill \end{array}$$

$$\begin{array}{c}\forall g\in \mathcal{G},k\in {\mathcal{K}}_g.\hfill \end{array}$$

(39)

Besides, it can be obtained that (18) can be rewritten into the following DC form

$$\begin{array}{cc}\hfill & D_{{\mathcal{K}}_g}^c+\Omega \left(T_u,R_{{\mathcal{K}}_g}^c\right)\le 0,\forall g\in \mathcal{G},\hfill \end{array}$$

(40)

$$\begin{array}{cc}\hfill & D_k^p+\Omega \left(T_u,R_k^p\right)\le 0,\forall k\in \mathcal{K},\hfill \end{array}$$

(41)

where $\Omega \left(a,b\right)\triangleq 1/4·{\left(a-b\right)}^2-1/4·{\left(a+b\right)}^2$. Besides, it is not difficult to verified that constraint (32) is linear about $t_e$ and $t_{e,{\mathcal{K}}_g}$, and constraint (33) is linear about $t_{e,{\mathcal{K}}_g}$, $D_{{\mathcal{K}}_g}^c$ and $D_k^p$. Consequently, ${\mathcal{P}}_5$ can be equivalently transformed into the following DC programming problem

$$\begin{array}{cc}\hfill {\mathcal{P}}_6:\underset{\mathbf{w},\mathbf{D},\mathbf{R},\mathbf{t},\mathit{\nu }}{min}& T_u+t_e\hfill \end{array}$$

(42)

$$\begin{array}{cc}\hfill \mathrm{s}.\mathrm{t}.& \left(23\right), \left(24\right), \left(32\right), \left(33\right), \left(34\right), \left(35\right), \left(38\right), \left(39\right), \left(40\right), \left(41\right).\hfill \end{array}$$

The above DC programming problem ${\mathcal{P}}_6$ can be efficiently solved by the CCCP technique [35], which is briefly introduced in the following. Consider DC programming problems which have the form

$$\begin{array}{cc}\hfill \underset{x}{min}& f_0\left(x\right)-g_0\left(x\right)\hfill \\ \hfill \mathrm{s}.\mathrm{t}.& f_a\left(x\right)-g_a\left(x\right)\le 0,a=1,\dots ,m,\hfill \end{array}$$

(43)

where x is the optimization variable and $f_a$ and $g_a$ are convex for $a=0,1,\dots ,m$. The fundamental concept of CCCP is to solve a sequence of approximate convex problems iteratively. At the $i+1$-th iteration, the approximated problem is given by the following:

$$\begin{array}{cc}\hfill \underset{x}{min}& f_0\left(x\right)-{\widehat{g}}_0(x;x^i)\hfill \\ \hfill \mathrm{s}.\mathrm{t}.& f_a\left(x\right)-{\widehat{g}}_a(x;x^i)\le 0,a=1,\dots ,m,\hfill \end{array}$$

(44)

where ${\widehat{g}}_a(x;x^i)=g_a\left(x^i\right)+\nabla g_a\left(x^i\right)(x-x^i)$ and $x^i$ is the optimal solution of problem (44) at the i-th iteration. As the number of iterations increases, the optimal solution $x^i$ will converge to a Karush–Kuhn–Tucker (KKT) point of the original problem [35].

For the considered problem ${\mathcal{P}}_6$, at the $\left(i+1\right)$-th iteration of the CCCP procedure, the concave parts in both the objective function and the constraints will be linearized at the point $\left({\mathbf{w}}^i,{\mathbf{D}}^i,{\mathbf{R}}^i,{\mathbf{t}}^i,{\mathit{\nu }}^i\right)$, where ${\mathbf{w}}^i=\left[{\mathbf{w}}_{{\mathcal{K}}_1}^{c,i},{\mathbf{w}}_{{\mathcal{K}}_2}^{c,i},\dots ,{\mathbf{w}}_{{\mathcal{K}}_G}^{c,i},{\mathbf{w}}_1^{p,i},{\mathbf{w}}_2^{p,i},\dots ,{\mathbf{w}}_K^{p,i}\right],$${\mathbf{D}}^i=\left[D_{{\mathcal{K}}_1}^{c,i},D_{{\mathcal{K}}_2}^{c,i},\dots ,D_{{\mathcal{K}}_G}^{c,i},D_1^{p,i},D_2^{p,i},\dots ,D_K^{p,i}\right]$, ${\mathbf{R}}^i=\left[R_{{\mathcal{K}}_1}^{c,i},R_{{\mathcal{K}}_2}^{c,i},\dots ,R_{{\mathcal{K}}_G}^{c,i},R_1^{p,i},R_2^{p,i},\dots ,R_K^{p,i}\right]$, ${\mathbf{t}}^i=\left[t_e^i,t_{e,{\mathcal{K}}_1}^i,\dots ,t_{e,{\mathcal{K}}_G}^i\right]$ and ${\mathit{\nu }}^i=\left\{{\nu }_{{\mathcal{K}}_g,k}^{c,i},{\nu }_k^{p,i}|\forall k\in \mathcal{K},\forall g\in \mathcal{G}\right\}$ are compact representations of the corresponding optimization variables obtained in the i-th iteration. Specifically, as the objective function (42) and the constraints (24), (32), (33), (34) and (35) are convex, they do not require the treatment of linearization. For the constraints (38) and (39), by linearizing their concave parts, their approximations for the $\left(i+1\right)$-th iteration are, respectively, given by

$$\begin{array}{cc}\hfill & \sum _{g^{\prime }\in \mathcal{G},g^{\prime }\ne g}{\left|{\mathbf{h}}_k^H{\mathbf{w}}_{{\mathcal{K}}_{g^{\prime }}}^c\right|}^2+\sum _{j\in \mathcal{K}}{\left|{\mathbf{h}}_k^H{\mathbf{w}}_j^p\right|}^2+{\sigma }^2+\left(\sum _{g^{\prime }\in \mathcal{G}}{\left|{\mathbf{h}}_k^H{\mathbf{w}}_{{\mathcal{K}}_{g^{\prime }}}^c\right|}^2+\sum _{j\in \mathcal{K}}{\left|{\mathbf{h}}_k^H{\mathbf{w}}_j^p\right|}^2+{\sigma }^2\right)\times \hfill \\ \hfill & {\nu }_{{\mathcal{K}}_g,k}^c/{\left({\nu }_{{\mathcal{K}}_g,k}^{c,i}\right)}^2-2\mathfrak{R}\left[\sum _{g^{\prime }\in \mathcal{G}}{\left({\mathbf{w}}_{{\mathcal{K}}_{g^{\prime }}}^{c,i}\right)}^H{\mathbf{h}}_k{\mathbf{h}}_k^H{\mathbf{w}}_{{\mathcal{K}}_{g^{\prime }}}^c+\sum _{j\in \mathcal{K}}{\left({\mathbf{w}}_j^{p,i}\right)}^H{\mathbf{h}}_k{\mathbf{h}}_k^H{\mathbf{w}}_j^p+{\sigma }^2\right]/{\nu }_{{\mathcal{K}}_g,k}^{c,i}\le 0,\hfill \end{array}$$

$$\begin{array}{c}\forall g\in \mathcal{G},k\in {\mathcal{K}}_g,\hfill \end{array}$$

(45)

$$\begin{array}{cc}\hfill & \sum _{g^{\prime }\in \mathcal{G},g^{\prime }\ne g}{\left|{\mathbf{h}}_k^H{\mathbf{w}}_{{\mathcal{K}}_{g^{\prime }}}^c\right|}^2+\sum _{j\in \mathcal{K},j\ne k}{\left|{\mathbf{h}}_k^H{\mathbf{w}}_j^p\right|}^2+{\sigma }^2+\left(\sum _{g^{\prime }\in \mathcal{G},g^{\prime }\ne g}{\left|{\mathbf{h}}_k^H{\mathbf{w}}_{{\mathcal{K}}_{g^{\prime }}}^c\right|}^2+\sum _{j\in \mathcal{K}}{\left|{\mathbf{h}}_k^H{\mathbf{w}}_j^p\right|}^2+{\sigma }^2\right)\times \hfill \\ \hfill & {\nu }_k^p/{\left({\nu }_k^{p,i}\right)}^2-2\mathfrak{R}\left[\sum _{g^{\prime }\in \mathcal{G},g^{\prime }\ne g}{\left({\mathbf{w}}_{{\mathcal{K}}_{g^{\prime }}}^{c,i}\right)}^H{\mathbf{h}}_k{\mathbf{h}}_k^H{\mathbf{w}}_{{\mathcal{K}}_{g^{\prime }}}^c+\sum _{j\in \mathcal{K}}{\left({\mathbf{w}}_j^{p,i}\right)}^H{\mathbf{h}}_k{\mathbf{h}}_k^H{\mathbf{w}}_j^p+{\sigma }^2\right]/{\nu }_k^{p,i}\le 0,\hfill \end{array}$$

$$\begin{array}{c}\forall g\in \mathcal{G},k\in {\mathcal{K}}_g.\hfill \end{array}$$

(46)

Similarly, for the constraints (40) and (41), their approximations for the $\left(i+1\right)$-th iteration are, respectively, given by

$$\begin{array}{cc}\hfill & D_{{\mathcal{K}}_g}^c+\Phi \left(T^u,R_{{\mathcal{K}}_g}^c;T_u^i,R_{{\mathcal{K}}_g}^{c,i}\right)\le 0,\forall g\in \mathcal{G},\hfill \end{array}$$

(47)

$$\begin{array}{cc}\hfill & D_k^p+\Phi \left(T^u,R_k^p;T_u^i,R_k^{p,i}\right)\le 0,\forall k\in \mathcal{K},\hfill \end{array}$$

(48)

where ${\Phi }^i\left(a,b;a^i,b^i\right)\triangleq {\displaystyle \frac{1}{4}}{(a-b)}^2+{\displaystyle \frac{1}{4}}{(a^i+b^i)}^2-{\displaystyle \frac{1}{2}}(a^i+b^i)(a+b)$ and $T_u^i$ can be computed by using (18) and $\left({\mathbf{D}}^i,{\mathbf{R}}^i\right)$.

Based on the above, given the optimal solution $\left({\mathbf{w}}^i,{\mathbf{D}}^i,{\mathbf{R}}^i,{\mathbf{t}}^i,{\mathit{\nu }}^i\right)$ at the i-th iteration, the approximate convex problem of ${\mathcal{P}}_6$ for the $\left(i+1\right)$-th iteration is given by

$$\begin{array}{cc}\hfill {\mathcal{P}}_7:\underset{\mathbf{w},\mathbf{D},\mathbf{R},\mathbf{t},\mathit{\nu }}{min}& T_u+t_e\hfill \\ \hfill \mathrm{s}.\mathrm{t}.& \left(23\right), \left(24\right), \left(32\right), \left(33\right), \left(34\right), \left(35\right), \left(45\right), \left(46\right), \left(47\right), \left(48\right).\hfill \end{array}$$

The convex problem ${\mathcal{P}}_7$ can be solved by standard methods [36]. Specifically, with the interior point method, the computational complexity for solving problem ${\mathcal{P}}_7$ is approximately $\mathcal{O}\left({\left(\left(K+G\right)N_t\right)}^{3.5}\right)$ [36]. The above procedure will be repeated until convergence as summarized in Algorithm 3. Additionally, since the problem size of ${\mathcal{P}}_7$ does not scale with the number of iterations, the computation complexity of Algorithm 3 is $\mathcal{O}\left({\left(\left(K+G\right)N_t\right)}^{3.5}I\right)$, where I is the total number of iterations required for the convergence.

Algorithm 3 CCCP-based optimization for problem ${\mathcal{P}}_3$

Input:  Tolerance $ϵ$, power constraint $P_t$, distributions of the computation rates of all ENs ${\left\{C_k\right\}}_{i=1}^K$, task size D; Output:  Precoder ${\mathbf{w}}^{*}$, task partitioning vector ${\mathbf{D}}^{*}$, rate vector ${\mathbf{R}}^{*}$; 1: Set iteration index $i=0$; 2: Find an initial feasible point $\left({\mathbf{w}}^0,{\mathbf{D}}^0,{\mathbf{R}}^0,{\mathbf{t}}^0,{\mathit{\nu }}^0\right)$ of ${\mathcal{P}}_5$; 3: repeat 4:   Using $\left({\mathbf{w}}^i,{\mathbf{D}}^i,{\mathbf{R}}^i,{\mathbf{t}}^i,{\mathit{\nu }}^i\right)$ obtained from the last iteration, solve problem ${\mathcal{P}}_7$ and obtain an optimal solution $\left({\mathbf{w}}^{i+1},{\mathbf{D}}^{i+1},{\mathbf{R}}^{i+1},{\mathbf{t}}^{i+1},{\mathit{\nu }}^{i+1}\right)$; 5:   Compute the corresponding objective function $O_E^{i+1}$; 6:   Update iteration index $i=i+1$; 7: until $\left|O_E^i-O_E^{i-1}\right|\le ϵ$; 8: return ${\mathbf{w}}^{*}={\mathbf{w}}^i$, ${\mathbf{D}}^{*}={\mathbf{D}}^i$, ${\mathbf{R}}^{*}={\mathbf{R}}^i$.

6. Simulation Results

In this section, simulation results are presented to collaborate on the effectiveness of the proposed scheme. In the simulations, the number K of the ENs is set to 8. The size of the original computation task is set to $1\times {10}^6$ bits. For communication, the one-ring model [37] is adopted to characterize the channel between the mobile user and each EN, assuming that the mobile user’s antennas have a uniform linear array structure [25,38,39]. Besides, the location angle of EN k with respect to the mobile user’s antennas is set to ${\displaystyle \frac{2\pi k}{K}}$ and the angular spread of the scattering associated with EN k follows uniform distribution on $\left[{\displaystyle \frac{\pi }{36}},{\displaystyle \frac{\pi }{18}}\right]$. The average channel power gain $\rho$ is set to $-85$ dB. The bandwidth B is set to 1 (MHz); the noise power ${\sigma }^2$ is set to $1\times {10}^{-10}$ (W); the maximum transmit power $P_t$ of the mobile user is set to 1 (W). The number of antennas of the mobile user $N_t$ is set to 6. For computation, processing each bit of the computation task is assumed to take $\beta =400$ CPU cycles. The maximum processor frequency $f_e$ is set to $2.5$ (GHz). The disturbed part ${\Delta }_k$ of the computation rate is assumed to follow Bernoulli distribution [29,40,41] with parameter $p_k$ = 0.3; that is, $\mathbb{P}\{{\Delta }_k=S\}=p_k$ and $\mathbb{P}\{{\Delta }_k=0\}=1-p_k$. Here, S is the maximum value of the disturbed part and is set to ${\displaystyle \frac{19}{20}}\overline{C}$. The cost $\eta$ for the signaling transmission of the collaboration is set to $1\times {10}^{-2}$ second. The weighting parameter l in (27) is set to 0.5. To demonstrate the advantage of the proposed scheme, three baseline schemes are considered. The first baseline is the naive (uncoded) distributed edge computing with neither information recycling nor coded computing. The second baseline is conventional coded computing with the optimal coding parameter. The third baseline is the conventional information recycling for distributed edge computing, (i.e., the proposed scheme with $G=1$ and ${\mathcal{K}}_{G_1}=\mathcal{K}$). Besides, the K-medoids algorithm and continuous partitioning algorithm are both demonstrated in the single-antenna case for the proposed scheme.

The task processing latency of the proposed scheme and those of the three baselines under different B with $N_t=1$ and $N_t=6$ are compared in Figure 4 and Figure 5, respectively. It can be seen that the performance gain brought by the proposed scheme is significant. For instance, when $N_t=1$ and the bandwidth is 1 (MHz), the proposed scheme with continuous partitioning algorithm can substantially reduce the processing latency to about $0.29$ (s) and achieves about 59.8 % and 51.0 % performance gains as compared to Baseline 2 and Baseline 3. Intuitively, the reason is that the proposed scheme does not introduce extra task coding redundancy as compared to Baseline 2 and alleviates the communication limitation by transmitting multiple common streams as compared to Baseline 3. Besides, it can be observed from Figure 4 that the proposed scheme with the continuous partitioning algorithm achieves a better performance than that with the heuristic K-medoids algorithm. To better demonstrate the advantage of the proposed scheme over Baseline 3, the common streams’ power ratio ${\displaystyle \frac{{\sum }_{g=1}^G{\left|{\mathbf{w}}_{{\mathcal{K}}_g}^c\right|}^2}{P_t}}$ and task ratio ${\displaystyle \frac{{\sum }_{g=1}^G{\mathcal{D}}_{{\mathcal{K}}_g}}{D}}$ of the proposed scheme and Baseline 3 are compared in Figure 6. It can be observed that the proposed scheme has a higher power ratio ${\displaystyle \frac{{\sum }_{g=1}^G{\left|{\mathbf{w}}_{{\mathcal{K}}_g}^c\right|}^2}{P_t}}$ and task ratio ${\displaystyle \frac{{\sum }_{g=1}^G{\mathcal{D}}_{{\mathcal{K}}_g}}{D}}$ as compared to Baseline 3. For example, when the bandwidth is 0.5 (MHz), the power ratio and task ratio of the proposed scheme are 0.91 and 0.75, respectively, while the power ratio and task ratio of Baseline 3 are 0.62 and 0.23, respectively. The reason is that, by alleviating the rate limitation of the single common stream through the transmission of multiple common streams, the proposed scheme can allocate more power to enlarge the common streams, thereby increasing the task ratio of the common part(s) and promoting computation collaboration for processing latency reduction.

Besides, the task processing latency of the proposed scheme and those of the three baselines under different $\rho$ with $N_t=1$ and $N_t=6$ are compared in Figure 7 and Figure 8, respectively. It can be seen that the advantages of the proposed scheme are still robust. For instance, when the average power gain $\rho$ is $-90$ (dB), the proposed scheme can substantially reduce the processing latency to about $0.39$ (s) and $0.30$ (s), respectively, which further demonstrates the effectiveness of the proposed scheme.

Moreover, the communication phase latency and the computation phase latency under different $f_e$ with $N_t=6$ are compared in Figure 9 and Figure 10, respectively. It can be seen that the proposed scheme achieves both lower communication latency and computation latency as compared to Baseline 3, further demonstrating its superiority in overcoming the communication limitation of the single common stream to facilitate communication and promote information recycling for enhanced computation collaboration. Meanwhile, it can be seen from Figure 9 that, the proposed scheme has much lower communication latency than Baseline 2. The reason is that, due to the introduction of task redundancy for straggler mitigation, Baseline 2 (i.e., coded computing) incurs additional communication overhead, resulting in relatively high communication latency.

Furthermore, the task processing latency of the proposed scheme and those of the three baselines with $K=12$ under different B and $\rho$ are compared in Figure 11 and Figure 12, respectively.

It can be observed from Figure 11 and Figure 12 that, the performance gain brought by the proposed scheme scheme is still significant. For example, when the bandwidth is 0.5 (MHz), the proposed scheme can substantially reduce the processing latency to about 0.33 (s) and achieve about 28.5 % and 31.3% performance gains as compared to Baseline 2 and Baseline 3.

7. Conclusions and Further Works

In this work, a novel multi-group information recycling scheme is proposed for rate-splitting-based distributed edge computing, which can better utilize the information recycling mechanism for processing latency reduction. In particular, by clustering ENs into different groups and transmitting multiple common streams, the proposed scheme can overcome the communication limitation of the single common stream and allocate more resources to the common streams to foster information recycling for straggler mitigation. To achieve an effective EN grouping strategy, a K-medoids-based algorithm is developed by jointly considering the channel alignment and channel strength for the general multi-antenna case, and a more efficient continuous partitioning-based algorithm is proposed for the specific case of single-antenna. Besides, through bounding the corresponding latency optimization problem via DC programming, a CCCP-based algorithm is developed to find a good solution. Simulation results show that the proposed scheme can substantially outperform the baselines and greatly enhance the system’s performance.

Extension to group number optimization, advanced grouping strategies exploration, practical implementation and compatibility with existing infrastructures, imperfect channel state information problem, security and vulnerability issues related to the common streams transmission, energy consumption optimization and distributed network congestion, as well as integrating information recycling into other non-orthogonal transmission techniques for distributed edge computing are all worthwhile future works.