Latency Minimization for mmWave D2D Mobile Edge Computing Systems: Joint Task Allocation and Hybrid Beamforming Design

In this paper, we adopt a general compression model and denote the computational results as $\alpha L$ bits, where $0\leq\alpha\leq 1$ denotes the compression ratio for the computation task and can be chosen as different values based on the category of the task and the adopted algorithm [38]. Defining $K_{L}\triangleq\frac{L}{F_{L}}$, $K_{E}\triangleq\frac{L}{F_{E}}$, $K_{1}\triangleq\frac{L}{R_{1}}$, $K_{2}\triangleq\frac{\alpha L}{R_{2}}$ and $K_{3}\triangleq\frac{\alpha L}{R_{3}}$ for convenience of notation, where $F_{L}$ and $F_{E}$ stand for the local computing capacity and the edge computing capacity (computing capacity of the MEC server), respectively, and $R_{1}$, $R_{2}$ and $R_{3}$ represent the transmission rates of the uplink (from user A to the BS), downlink and D2D link, respectively. We express different delays as follows,

• •

  The local computing time: $T_{L}^{c}=(1-\rho)K_{L}$.

• •

  The computing time at the MEC server: $T_{E}^{c}=\rho K_{E}$.

• •

  The offloading time from user A to the BS: $T_{up}^{t}=\rho K_{1}$.

• •

  The delay for transmitting the computational result from the BS to user B: $T_{down}^{t}=\rho K_{2}$.

• •

  The delay for transmitting the computational result from user A to user B: $T_{D2D}^{t}=(1-\rho)K_{3}$.

Let us consider the process of computation and transmission more concretely. As shown in Fig. 2, there are four cases in total.

• •

  Case 1: $T_{up}^{t}\geq T_{L}^{c}$ and $T_{E}^{c}\geq T_{D2D}^{t}$. In this case, the local computing at user A finishes before the edge offloading. Thus user A has to wait until the task offloading is over to send the local computing result to user B through the D2D link. Moreover, in this case the transmission of the local computing result ends before the edge computing. Hence, the BS can send the edge computing results to user B directly without waiting until the transmission of D2D link is over.

• •

  Case 2: $T_{up}^{t}\geq T_{L}^{c}$ and $T_{E}^{c}<T_{D2D}^{t}$. In this case, the local computing at user A also finishes before the edge offloading. Hence, similar with Case 1, user A has to wait until the task offloading is over. However, we consider that the edge computing finishes before the transmission of the local computing result. Under this situation, the BS has to wait until the D2D link transmission is over to send the edge computing results to user B. Otherwise, collisions would happen at user B.

• •

  Case 3: $T_{up}^{t}<T_{L}^{c}$ and $T_{up}^{t}+T_{E}^{c}<T_{L}^{c}+T_{D2D}^{t}$. In this case, the edge offloading ends before the local computing. Hence user A can send the local computing results to user B through the D2D link directly since the communication resource is available at the moment. Moreover, in this case the edge computing finishes before the D2D transmission of the local computing result from user A to user B. Thus, the BS has to wait until the D2D link transmission is over to send the edge computing result to user B.²²2It is also possible that the edge computing finishes before the local computing. However, if the BS transmits the edge computing results to user B immediately, collisions may happen because user A does not know when the BS finishes its transmission and may send the local computing results to user B simultaneously. Thus, we assume that user A has a priority to transmit results to user B compared to the BS, even if the computation at the BS ends earlier.

• •

  Case 4: $T_{up}^{t}<T_{L}^{c}$ and $T_{up}^{t}+T_{E}^{c}\geq T_{L}^{c}+T_{D2D}^{t}$. In this case, the edge offloading ends before the local computing, and the D2D link transmission finishes before the edge computing. As a result, no wait happens.

According to the four cases discussed above, we obtain the expression for the overall system delay as follows,

Consider the three mmWave links that adopt hybrid A/D beamforming structures. User A and user B are equipped with $N_{a}$, $N_{b}$ antennas, respectively, and $N_{rfa}$ $(N_{rfa}\leq N_{a})$, $N_{rfb}$ $(N_{rfb}\leq N_{b})$ RF chains, respectively, while the BS has $N$ antennas and $N_{rf}$ $(N_{rf}\leq N)$ RF chains. Let $\mathbf{s}_{1}\in\mathbb{C}^{d_{1}\times 1}$, $\mathbf{s}_{2}\in\mathbb{C}^{d_{2}\times 1}$ and $\mathbf{s}_{3}\in\mathbb{C}^{d_{3}\times 1}$ $\sim\mathcal{CN}(\mathbf{0},\mathbf{I})$ denote the data symbols that transmitted from user A to the BS, the BS to user B and user A to user B, respectively. The received signal at the uplink, the downlink and the D2D link can be written as³³3 Here we adopt a single analog beamforming matrix $\mathbf{F}_{a}$ at user A and $\mathbf{F}_{b}$ at user B for different transmission phases, because this scheme can avoid frequent hand-off of the analog beamforming matrices with acceptable performance loss. Moreover, although we introduce the proposed algorithm under this case, it can be readily extended to the situation that there are independent analog beamforming matrices for different transmission stages.

respectively, where $\mathbf{W}_{a1}\in\mathbb{C}^{N_{rfa}\times d_{1}}$ and $\mathbf{W}_{a3}\in\mathbb{C}^{N_{rfa}\times d_{3}}$ represent the transmitting digital beamforming matrices of user A for the uplink and the D2D link, respectively. $\mathbf{F}_{a}\in\mathbb{C}^{N_{a}\times N_{rfa}}$ represents the long-term transmitting analog beamforming matrices of user A. $\mathbf{W}_{b2}\in\mathbb{C}^{N_{rfb}\times d_{2}}$ and $\mathbf{W}_{b3}\in\mathbb{C}^{N_{rfb}\times d_{3}}$ represent the receiving digital beamforming matrices of user B for the downlink and the D2D link, respectively. $\mathbf{F}_{b}\in\mathbb{C}^{N_{b}\times N_{rfb}}$ represents the long-term receiving analog beamforming matrices of user B. $\mathbf{V}_{1}\in\mathbb{C}^{N_{rf}\times d_{1}}$ and $\mathbf{V}_{2}\in\mathbb{C}^{N_{rf}\times d_{2}}$ represent the receiving and transmitting digital beamforming vectors at the BS, respectively, and $\mathbf{U}_{1}\in\mathbb{C}^{N\times N_{rf}}$ and $\mathbf{U}_{2}\in\mathbb{C}^{N\times N_{rf}}$ represent the long-term receiving and transmitting analog beamforming matrices at the BS, respectively. $\mathbf{H}_{1}\in\mathbb{C}^{N\times N_{a}}$, $\mathbf{H}_{2}\in\mathbb{C}^{N_{b}\times N}$, and $\mathbf{H}_{3}\in\mathbb{C}^{N_{b}\times N_{a}}$ denote the channel matrices of the uplink, downlink and D2D link, respectively, $\mathbb{E}\{\mathbf{n}_{1}\mathbf{n}_{1}^{H}\}=\sigma_{1}^{2}\mathbf{I}$, $\mathbb{E}\{\mathbf{n}_{2}\mathbf{n}_{2}^{H}\}=\sigma_{2}^{2}\mathbf{I}$, and $\mathbb{E}\{\mathbf{n}_{3}\mathbf{n}_{3}^{H}\}=\sigma_{3}^{2}\mathbf{I}$ denote the zero mean additive white Gaussian noise of the uplink, downlink and D2D link, respectively.

With the above definitions, we write the transmission rate for the uplink $R_{1}$, downlink $R_{2}$, and D2D link $R_{3}$, respectively as (2)-(4)⁴⁴4We do not include the receiving digital beamformers in the rate expressions because it is well-known that the optimal digital receivers (i.e., minimum mean square error (MMSE) receivers) can achieve the maximum system rate, see [48] for more details.,

where $B_{1}$, $B_{2}$ and $B_{3}$ represent the bandwidth of the uplink, downlink and D2D link, respectively.

In practice, the relationship between the circuit power and the output power may be non-linear due to the working mode of RF power amplifiers (PA) in mmWave band [39]. Hence, it is necessary to take the non-linear energy efficiency of PAs into consideration. Specifically, we consider the Doherty PA in this paper, which is one of the most widely used PA architecture in high frequency band that has enhanced energy efficiency and linearity [40]. The relationship between the output power $P_{out}$ and the actual PA power consumption $P_{PA}$ is given by [41]

where $P_{max}$ is the maximum output power of the PA. In order to compute the total power consumption of all PAs, we must calculate the output power of each PA first, which is given by

where $P_{out1}(i)$ and $P_{out3}(i)$ represent the output power of the $i$th PA of user A in the uplink and D2D link, respectively, and $P_{out2}(i)$ represents the output power of the $i$th PA of the BS in the downlink. By substituting (6)-(8) into (5), the power consumption of each PA, i.e. $P_{PA1}(i)$, $P_{PA2}(i)$ and $P_{PA3}(i)$ can be obtained.

In a typical mobile radio environment, the channel matrices appearing in the system model of Section II will exhibit a random behavior and change more or less rapidly over time. The joint design of A/D hybrid beamforming matrices and offloading ratio for each channel instance is not realistic for implementation since as it requires repeated application of a search-based algorithm with extremely high computational complexity [42]. Moreover, this approach entails a huge amount of overhead in the estimation and exchange of real-time CSI information, and is likely to be very sensitive to CSI delays. Therefore, to circumvent these difficulties, we hereby propose a practical two-timescale hybrid beamforming scheme that takes into account changes in both the instantaneous CSI and their local statistics. Let us define the following concepts of timescales:

• •

  Long-timescale: The time interval over which the channel statistics⁵⁵5In this work, channel statistics refer to the moments or distribution of the channel fading realizations. The proposed long-term beamforming design only has to obtain a single (potentially outdated) channel sample at each frame. By observing one channel sample at each time, our proposed algorithm can automatically learn the channel statistics and converge to a stationary point of the considered stochastic optimization problem. are assumed constant.

• •

  Short-timescale: The time interval over which the channel gains are assumed constant, i.e. the channel coherence time.

As illustrated in Fig. 3, the time domain is divided into a number of super frames within which the channel statistics are invariant. Each super frame consist of $T_{f}$ frames, and each frame is further divided into $T_{s}$ time slots. In our proposed approach, to reduce CSI overhead, we only make use of one complete estimated CSI at the end of each frame, while we employ a so-called effective CSI (the multiplication of the analog beamforming matrices and the CSI matrices, take the uplink as an example, $\mathbf{H}_{ef1}\triangleq\mathbf{U}_{1}^{H}\mathbf{H}_{1}\mathbf{F}_{a}\in\mathbb{C}^{N_{rf}\times N_{rfa}}$ while $\mathbf{H}_{1}\in\mathbb{C}^{N\times N_{a}}$) with reduce dimension within each time slot. The short-timescale digital beamforming matrices and the offloading ratio are optimized in each time slot by using the effective real-time channel matrices with reduced dimension, and the long-timescale analog beamforming matrices are updated at the end of each frame based on estimated (possibly outdated) CSI. In the following, we formulate the long-term optimization problem and the short-term optimization problem, respectively.

Note that the long-timescale analog beamforming matrices should be optimized based on the CSI statistics over a long-term scale, and we cannot directly optimize them by minimizing the system latency that relies on the optimal digital beamforming matrices and offloading ratio for all channel realizations. To overcome this difficulty, we propose to optimize the analog beamforming matrices by maximizing the weighted ergodic sum capacity, that does not depend on the short-term variables. Then, we minimize the system latency by optimizing the digital beamforming matrices and offloading ratio in each time slot.⁶⁶6Note that it makes sense that the maximization of the channel capacity by designing long-term analog beamforming matrices can help minimize the system latency and this formulation is more suitable for practical design. Moreover, we validate the effectiveness of the proposed algorithm in our simulation.

1) The long-term master problem for designing analog beamforming matrices yields

where we define $\bm{\theta}_{\mathbf{U}_{1}}=\angle\mathbf{U}_{1}$, $\bm{\theta}_{\mathbf{U}_{2}}=\angle\mathbf{U}_{2}$, $\bm{\theta}_{\mathbf{F}_{a}}=\angle\mathbf{F}_{a}$ and $\bm{\theta}_{\mathbf{F}_{b}}=\angle\mathbf{F}_{b}$ for convenience to meet the unit modulus constraint, and the weight $w_{1},w_{2}$ and $w_{3}$ can be empirically chosen based on the transmission tasks of the corresponding link. Specifically, we choose the weight as $w_{k}=\frac{\bar{L}_{k}}{\sum_{i=1}^{3}\bar{L}_{i}},k=1,2,3$, where $\bar{L}_{1}$, $\bar{L}_{2}$ and $\bar{L}_{3}$ denote the total number of transmission bits of the uplink, the downlink and the D2D link in the last super frame. Please note that this formulation is quite similar with that of maximizing the queue-length-weighted sum rate, which is widely adopted in the area of wireless resource scheduling [43, 44, 45], and it is also reasonable to use the number of transmission data in the last super frame because this information is available at the BS and the statistics between two adjacent super frames are much alike. By defining

then, the expressions of the ergodic channel capacity for the link between user A and the BS, the link between the BS and user B, and the link between user A and user B, are given by $\bar{C}_{1}\triangleq\mathbb{E}\{C_{1}\}$, $\bar{C}_{2}\triangleq\mathbb{E}\{C_{2}\}$, and $\bar{C}_{3}\triangleq\mathbb{E}\{C_{3}\}$, respectively [46], and $g(\bm{\theta}_{\mathbf{U}_{1}},\bm{\theta}_{\mathbf{U}_{2}},\bm{\theta}_{\mathbf{F}_{a}},\bm{\theta}_{\mathbf{F}_{b}})\triangleq w_{1}C_{1}+w_{2}C_{2}+w_{3}C_{3}$.

2) The short-term optimization problem for designing the digital beamforming matrices and offloading ratio can be expressed as

where $\mathcal{S}\triangleq\{\rho,\mathbf{W}_{a1},\mathbf{W}_{a3},\mathbf{V}_{2}\}$ denotes the set of the short-term optimization variables. (13c) and (13d) denote the transmit power constraints at user A and the BS, respectively. (13e) denotes the output power constraints of the PAs.

Due to the fact that the transmissions occur over orthogonal time in a single time slot, the transmission rates of the uplink, downlink and D2D link, i.e. $R_{1}$, $R_{2}$, $R_{3}$ are independent of each other. Furthermore, since the overall system delay (13a) is nonincreasing with $R_{1}$, $R_{2}$ and $R_{3}$, we can maximize the transmission rates first, and then optimize the offloading ratio. Hence the short-term latency minimization problem $\mathcal{P}$2 can be equivalently decomposed into the following two parts.

• •

  The digital beamforming design subproblems for the uplink, the downlink and the D2D link, respectively, are provided as:

  	$\displaystyle\mathcal{P}3\text{-}1:\max\limits_{\left\{\mathbf{W}_{a1}\right\}}$	$\displaystyle\quad R_{1}$		(24a)
  	s.t.	$\displaystyle\sum_{i=1}^{N_{a}}P_{PA1}(i)\leq P_{UA},$		(24b)
  		$\displaystyle 0\leq\|\mathbf{F}_{a}(i,:)\mathbf{W}_{a1}\|^{2}\leq P_{max},\forall i,$		(24c)

  	$\displaystyle\mathcal{P}3\text{-}2:\max\limits_{\left\{\mathbf{V}_{2}\right\}}$	$\displaystyle\quad R_{2}$		(25a)
  	s.t.	$\displaystyle\sum_{i=1}^{N}P_{PA2}(i)\leq P_{BS},$		(25b)
  		$\displaystyle 0\leq\|\mathbf{U}_{2}(i,:)\mathbf{V}_{2}\|^{2}\leq P_{max},\forall i,$		(25c)

  	$\displaystyle\mathcal{P}3\text{-}3:\max\limits_{\left\{\mathbf{W}_{a3}\right\}}$	$\displaystyle\quad R_{3}$		(26a)
  	s.t.	$\displaystyle\sum_{i=1}^{N_{a}}P_{PA3}(i)\leq P_{UA},$		(26b)
  		$\displaystyle 0\leq\|\mathbf{F}_{a}(i,:)\mathbf{W}_{a3}\|^{2}\leq P_{max},\forall i,$		(26c)

• •

  The offloading ratio optimization subproblem is given by:

  $$\mathcal{P}4:\min_{0\leq\rho\leq 1}\,\,T_{total}.\vspace{-0.5em}$$

  (27)

Although we have decomposed the original problem into several more tractable one, there are still some challenges, i.e. the non-linear power consumption constraint in $\mathcal{P}3$ and the multi-case piece-wise objective function in $\mathcal{P}4$. In the following two subsections, we introduce our proposed algorithms for tackling these issues.

In this subsection, we introduce the proposed short-term digital beamformer design algorithm for solving $\mathcal{P}3\text{-}1$$-$$\mathcal{P}3\text{-}3$. Since these subproblems are essentially the same, we focus on the uplink to introduce our proposed algorithm. First, we equivalently transform $\mathcal{P}3\text{-}1$ into a more tractable form based on the celebrated weighted minimum mean square error (WMMSE) method [48] as follows,

where $\mathbf{Z}$ is an auxiliary variable satisfying $\mathbf{Z}\succeq\mathbf{0}$ and

Then, to tackle the non-linear power constraint, we introduce two auxiliary variables $P_{PA1}$ and $V_{out1}$, and equivalently convert (28) as

where $\bar{\mathcal{S}}\triangleq\{\mathbf{V}_{1},\mathbf{W_{a1}},\mathbf{Z},P_{PA1},V_{out1}\}$ is the set of optimization variables and $\bar{P}_{UA}\triangleq\min(P_{UA}$,$4N_{a}P_{max}/\pi)$, while $h(V_{out1}(i))$ is defined as

Then, we solve the transformed problem based on the penalty-CCCP framework, the detailed introduction of which can be found in [49]. By penalizing the equality constraints (30b), (30e) and (30f) into the objective function (30a), we obtain the penalized problem shown as follows.

where $\varrho$ denotes a penalty coefficient. Referring to the penalty-CCCP, the proposed algorithm contains two loops, where the penalty coefficient is adjusted in the outer loop, while in the inner loop the optimization variables are updated in a block coordinate descent fashion. In each block of the inner loop, we aim to decompose the resulting penalized problem into a number of subproblems, which can be solved easily in parallel. To this end, we divide the optimization variables into three blocks, i.e. $\{\mathbf{V}_{1},P_{PA1}\}$, $\{\mathbf{Z},V_{out1}\}$, $\{\mathbf{W}_{a1}\}$. The detailed solutions within each block are given in Appendix B and we summarize the proposed penalty-CCCP based algorithm for uplink short-term digital beamforming design in Algorithm 2. The complexity is given by $\mathcal{O}\{I_{1}I_{2}(N_{rf}^{3}+N_{rfa}^{3}+NN_{rf}N_{a})\}$, where $I_{1}$ and $I_{2}$ denote the iteration numbers for the outer and inner loops, respectively.

Although the computational complexity in a single iteration is low, the required iteration number may be large for the double loop nature of the penalty-CCCP. Hence, we also propose a low-complexity heuristic algorithm for the short-term digital beamformer design. Ignoring the non-linear power constraint, the uplink digital beamforming design problem yields

where $\mathbf{Q}_{Fa}\triangleq\mathbf{F}_{a}^{H}\mathbf{F}_{a}$. Since the long-term analog beamformer $\mathbf{U}_{1}$ is fixed, we further view $\bar{\mathbf{H}}_{ef1}\triangleq\bar{\mathbf{\Sigma}}^{-1}\bar{\mathbf{V}}\mathbf{H}_{ef1}$ as the effective channel matrix, where $\bar{\mathbf{\Sigma}}$ and $\bar{\mathbf{V}}$ are the diagonal singular value matrix and the right singular vector matrix of $\mathbf{U}_{1}$, respectively. This problem has a well-known water-filling solution which is given by

where $\mathbf{U}_{e}$ is the set of the right singular vectors corresponding to the $N_{a}$ largest singular values of $\bar{\mathbf{H}}_{ef1}\mathbf{Q}_{Fa}^{-1/2}$, and $\mathbf{\Sigma}_{e}$ is the diagonal power allocation matrix. Since this low-complexity algorithm does not consider the nonlinear transmit power constraint directly, we scale the digital beamforming matrix $\mathbf{W}_{a1}$ to satisfy constraint (24b) and (24c), where the scaling factor can be conveniently found by using the bisection search. The computational complexity of the proposed low-complexity short-term digital beamforming design algorithm is given by $\mathcal{O}\{NN_{a}N_{rf}+N_{rf}N_{rfa}^{2}\}$.