Joint Beamforming and Computation Offloading for Multi-user Mobile-Edge Computing

Based on the fast development of electronic devices and mobile communication technologies, smart mobile devices (MDs) are expected to run more complicate applications such as face recognition, interactive gaming, and augmented reality, etc. Unfortunately, due to the constraints of cost and physical size, most MDs do not have enough energy supply or computation capability to run complicate applications. Therefore, efficient methods are required to relieve the contradiction between complicate applications’ demands and limited resources at MDs.

Driven by the growing demands of Internet of Things and mobile applications, mobile edge computing (MEC) is considered as a promising way to enable computation-intensive and latency-critical applications at the resource-limited MDs [1]. In MEC, the computing server is implemented at the edge of the network. Therefore, the computation intensive tasks of MDs can be handled by those edge node to reduce the energy consumption and time delay of certain applications. To promote the application of MEC, a lot of work has been done. The computation offloading strategy and radio resources allocation are jointly considered in an edge and central cloud computing system to optimize the energy consumption and time delay in [2]. The authors in [3] studied an offloading system where a MD can offload computation tasks to multiple edge servers, in which fixed and elastic CPU frequency are considered for MD. In most of the existing studies, MDs and base station (BS) are assumed to be equipped with single antenna, only a few researchers have applied the multi-antenna technology to MD or BS. Multi-antenna based energy harvesting strategy was introduced into MEC system [4] to enhance the computation capability and prolong the operation time of MDs. To realize wireless backhaul and exploit benefits from multi-antenna, the authors in [5] proposed to use receive beamforming at a multi-antenna BS, while multiple single antenna MDs transmit by using orthogonal multiple access techniques such as time/frequency-division. To improve the computation offloading efficiency, the authors in [6] utilized multi-antenna at both MD and BS to realize MIMO transmission. However, the MDs in the small cell still use orthogonal frequency resources.

With the growing of communication technologies, some novel techniques, such as massive MIMO technology [7], can be adopted to improve system’s performance. Uplink MU-MIMO communications was studied in [8], and the results show that uplink MU-MIMO communications can lead to significant improvement in cell throughput. The work in [9] showed that using multi-antenna for MIMO transmission can effectively reduce the transmission power and increase energy efficiency. Inspired by this, applying MU-MIMO transmission to MEC may further bring extra benefits and improve the performance of energy consumption and time delay during computation offloading.

In this paper, we consider the fusion of MEC and MU-MIMO communication to realize the MU-MIMO computation offloading for multiple MDs in the coverage area of a BS. The optimization problem is formulated as a joint offloading decision-making and MU-MIMO beamforming design problem under the constraints of maximum transmit power and time delay. The problem is a mixed-integer non-linear programming problem, which is NP-hard. Due to the complexity of the optimization problem, we deal with the optimization problem in two steps. First, the optimization problem is reformulated via quadratic constrained quadratic programming (QCQP) and semidefinite relaxation (SDR). And the offloading decisions are obtained through the approximation of the SDR solution as in Algorithm 1. Then, a fractional programming based method is adopted to transform the non-convex MU-MIMO beamforming problem into a convex one. And the optimal beamforming matrices are acquired via the proposed Algorithm 2. Simulation results show that the proposed MU-MIMO computation offloading method can effectively reduce the time delay and energy consumption.

As shown in figure 1, this paper considers a MEC system that consists of a BS equipped with a MEC server and $M$ antennas and $K$ MDs equipped with $N$ antennas. Define ${\mathds{U}}=\left\{{1,\ldots,K}\right\}$ as the set of MDs. Then for MD $k$ ($k\in{\mathds{U}}$), its computation task can be processed locally or offloaded to the BS. With the collected information from MDs (e.g. computation task size, local computing capability, channel state information and maximum tolerable delay), the BS can make optimized offloading decisions for MDs. A quasi-static scenario is considered where all the MDs remain stationary during an offloading period [3].

In this paper, uplink MU-MIMO communications are considered for computation offloading. Without loss of generality, each MD supports the transmission of $d$ streams over $N$ antennas ($d\leq N$ and $Kd\leq M$). Let ${{\mathds{U}}_{o}}=\left\{{1,\ldots,{N_{o}}}\right\}\subseteq{\mathds{U}}$ be the set of offloading MDs. When MD $k$ ($k\in{{\mathds{U}}_{o}}$) offloads its task to the BS, the received signal of ${l_{th}}$ data stream from MD $k$ at BS can be expressed as [9]

where ${{\bf{q}}_{k(l)}}$ and ${{\bf{v}}_{k(l)}}$ are the ${l_{th}}$ column of $N\times d$ transmit beamforming matrix ${{\bf{Q}}_{k}}$ and $M\times d$ receive beamforming matrix ${{\bf{V}}_{k}}$, respectively. ${x_{k,l}}$ is the ${l_{th}}$ symbol of the transmitted $d\times 1$ data vector ${{\bf{x}}_{k}}$, and ${{\bf{x}}_{k}}$ satisfies $E[{{\bf{x}}_{k}}{\bf{x}}_{k}^{H}]={I_{d}}$ and $E[{{\bf{x}}_{k}}{\bf{x}}_{l}^{H}]={\bf{0}}$ for $k\neq l$. ${{\bf{H}}_{k}}$ denotes the $M\times N$ channel matrix from MD $k$ to BS. ${\bf{n}}$ denotes the additive white Gaussian noise (AWGN) vector and $E[{\bf{n}}{{\bf{n}}^{H}}]={\sigma^{2}}{{\bf{I}}_{M}}$. According to (1), the achievable data rate ${R_{k}}$ of the MD ${k}$ can be given by

where $B_{W}$ (Hz) is the system bandwidth and $I_{N}=\sum\nolimits_{i\in{U_{o}},i\neq k}{\sum\nolimits_{j=1}^{d}{{\bf{v}}_{k(l)}^{H}{{\bf{H}}_{i}}{{\bf{q}}_{i(j)}}{\bf{q}}_{i(j)}^{H}{\bf{H}}_{i}^{H}{{\bf{v}}_{k(l)}}}}+{\sigma^{2}}{\bf{v}}_{k(l)}^{H}{{\bf{v}}_{k(l)}}$.

The computation task of MD $k$ is presented as ${J_{k}}=\left({{B_{k}},\tau_{\max}^{k}}\right)$ ($k\in{\mathds{U}}$), where ${B_{k}}$ (in bits) denotes the size of input data and $\tau_{\max}^{k}$ is the maximum tolerable delay (in seconds). Since the computation result is usually small, the time delay of receiving computation result is uauslly omitted [10]. For MD $k$ ($k\in{{\mathds{U}}_{l}}={\mathds{U}}\backslash{{\mathds{U}}_{o}}$) in local computing, the local computation time can be expressed as ${T_{loc,k}}={{{C_{k}}}}/{{{f_{loc,k}}}}$, where ${C_{k}}=\alpha{B_{k}}$ is the total number of CPU cycles to finish task computing and $\alpha$ (cycles/bit) is the processing density, and ${f_{loc,k}}$ is the local computation capability (cycles/s) of MD $k$. According to [11], the energy consumption of MD $k$ in local computing can be given as ${E_{loc,k}}=\kappa{C_{k}}f_{loc,k}^{2}$, where $\kappa$ is a constant related to the hardware architecture [12].

To simplify the analysis, it is assumed that the BS starts task computation after receiving all MDs’ tasks. Hence, the data transmission delay of MD $k$ in ${{\mathds{U}}_{o}}$ is given as ${T_{tran,k}}={\max_{i\in{U_{o}}}}\left\{{{B_{i}}/{R_{i}}}\right\}$. While the execution time delay at BS can be formulated as ${T_{c,k}}={{{C_{k}}}}/{{{f_{c,k}}}}$, where ${f_{c,k}}$ (cycles/s) is the computation resource allocated to MD $k$.

According to the analysis stated above, when offloading decision is considered, the time delay of MD $k$ in ${\mathds{U}}$ during computation offloading can be denoted as ${T_{off,k}}={\max_{i\in U}}\left\{{{{{c_{i}}{B_{i}}}\mathord{\left/{\vphantom{{{c_{i}}{B_{i}}}{{R_{i}}}}}\right.\kern-1.2pt}{{R_{i}}}}}\right\}+{T_{c,k}}$, where ${c_{i}}\in\left\{{0,1}\right\}$ is the offloading decision of MD $i$. If ${c_{i}}=0$, the MD $i$ computes its task at local; otherwise, the task is offloaded to the BS.

The circuit energy consumption of MD $k$ during idle time ${T_{c,k}}$ can be formulated as ${E_{c,k}}=p_{k}^{id}{T_{c,k}}$, where $p_{k}^{id}$ is the power consumption (in watt) in idle state. Therefore, the energy consumption of MD $k$ during computation offloading can be given as ${E_{off,k}}=\left({{{{B_{k}}}\mathord{\left/{\vphantom{{{B_{k}}}{{R_{k}}}}}\right.\kern-1.2pt}{{R_{k}}}}}\right)p_{k}^{t}+{E_{c,k}}$, where $p_{k}^{t}=\left\|{{{\bf{Q}}_{k}}}\right\|_{F}^{2}$ is the transmission power of MD $k$. Since the computing result is usually small, the energy consumption of receiving the computing result is ignored at MD side. Finally, the time delay and energy consumption of MD $k$ can be computed respectively as

Based on the above analysis, the objective of this paper is to minimize the weighted sum of energy consumption and time delay of all MDs. Mathematically, the optimization problem is formulated as

where ${\mathds{Q}}=\left\{{{{\bf{Q}}_{1}},\ldots,{{\bf{Q}}_{K}}}\right\}$ and ${\mathds{V}}=\left\{{{{\bf{V}}_{1}},\ldots,{{\bf{V}}_{K}}}\right\}$ are the sets of transmit beamforming matrices and receive beamforming matrices, respectively. ${\bf{c}}={[{c_{1}},{c_{2}},\ldots,{c_{K}}]^{T}}$ is the offloading decisions of all MDs. $P_{\max}^{k}$ is the maximum transmit power of MD $k$. Note that in (5), the constraint (5b) guarantees that the offloading decision of each MD is binary variable. Constraint (5c) denotes the maximum transmission power of each MD, and constraint (5d) indicates the maximum tolerable delay. It can be observed that (5) is a mixed-integer non-linear programming problem, which is generally NP-hard [13]. Due to space limitation, the proof of the NP-hard problem (5) is omitted.

In this section, the QCQP and SDR based transformations are proposed to solve the offloading decision problem. Let $\max\left\{{{{{B_{k}}}}/{{{R_{k}}}}p_{k}^{t}}\right\}=p_{k}^{com}$ and ${\max_{k\in{\mathds{U}}}}\left\{{{c_{k}}{{{B_{k}}}}/{{{R_{k}}}}}\right\}=t$, we have ${B_{k}}p_{k}^{t}\leq p_{k}^{com}{R_{k}},\forall k\in{\mathds{U}}$ and ${B_{k}}{c_{k}}\leq t{R_{k}},\forall k\in{\mathds{U}}$. Then, the problem (5) can be transformed to the problem (6) as

where ${{\bf{p}}^{com}}=\left\{{p_{1}^{com},\ldots,p_{K}^{com}}\right\}$, ${\delta_{k}}=\lambda_{k}^{e}E_{c,k}+\lambda_{k}^{t}T_{c,k}{\rm{-}}\left({\lambda_{k}^{e}E_{loc,k}+\lambda_{k}^{t}T_{loc,k}}\right)$ ($\forall k\in{\mathds{U}}$) and $\eta{\rm{=}}\sum\nolimits_{k=1}^{K}{\left({\lambda_{k}^{e}E_{loc,k}+\lambda_{k}^{t}T_{loc,k}}\right)}$ are constant, and $\eta$ can be omitted in the following analysis. The integer constraint in (5b) is replaced by quadratic constraint in (6b). To perform the QCQP transformation, a $(4K+1)\times 1$ vector s is defined as

Mathematically, P2 is transformed into the following standard QCQP problem

where ${{\bf{c}}_{0}}=\left({1/2}\right){\left[{{\delta_{1}},\ldots,{\delta_{K}},{{\bf{0}}_{1\times 3K}},{0_{1\times 1}}}\right]^{T}}$ is a constant $\left({4K+1}\right)\times 1$ vector; ${{\bf{e}}_{k}}$ and ${{\bf{e}}^{\prime}_{k}}$ are standard unit vector with size of ${\left({4K+1}\right)\times 1}$ and $K\times 1$, respectively. And the matrices of ${{\bf{M}}_{1}}$, ${{\bf{M}}_{2}}$, ${{\bf{M}}_{3}}$, ${{\bf{M}}_{4}}$, ${{\bf{M}}_{5}}$, ${{\bf{D}}_{e}}$, ${{\bf{c}}_{t}}$ and ${{\bf{D}}_{p}}$ in (8) are listed as follows

To solve the QCQP problem (8), the SDR method proposed in [14] can be used to transform P3 into a Semidefinite programming (SDP) problem. Define matrix ${\bf{G}}=\left[{\begin{array}[]{*{20}{c}}{\bf{s}}\\ 1\end{array}}\right]\left[{\begin{array}[]{*{20}{c}}{{{\bf{s}}^{T}}}&1\end{array}}\right]$, then, P3 can be rewritten as

where the matrices of ${{\bf{W}}_{0}}$, ${{\bf{W}}_{1}}$, ${{\bf{W}}_{2}}$, ${{\bf{W}}_{3}}$, ${{\bf{W}}_{4}}$, ${{\bf{W}}_{5}}$ are listed as follows

In the problem (16), only the constraint (16h) is non-convex. By dropping the rank-1 constraint (16h), (16) becomes a positive SDP problem which can be solved using standard CVX tools [15].

Define ${{\bf{G}}^{*}}$ as the optimal solution of the problem (16) without the rank-1 constraint, and note that ${\bf{G}}\left({4K+2,k}\right)=s\left(k\right)$ for $k=1,\ldots,4K+1$. Therefore, ${{\bf{G}}^{*}}\left({4K+2,k}\right)$, ($k=1,\ldots,K$) can be used to recover the binary offloading decision ${c_{k}}$. Define ${\bf{D}}={\left[{{d_{1}},\ldots,{d_{K}}}\right]^{T}}$, and let $D={\left[{{{\bf{G}}^{*}}(4K+2,1),\ldots,{{\bf{G}}^{*}}(4K+2,K)}\right]^{T}}$. Note that ${d_{k}}\in\left[{0,1}\right]$ for $k=1,\ldots,K$. Define ${\bf{\tilde{\bf{c}}}}={\left[{{{\tilde{c}}_{1}},\ldots,{{\tilde{c}}_{K}}}\right]^{T}}$ as the feasible binary offloading decision vector and $\gamma$ as the decision making threshold, if ${d_{k}}>\gamma$, ${\tilde{c}_{k}}=1$; otherwise, ${\tilde{c}_{k}}=0$. The overall offloading decision making and MU-MIMO Computation Offloading (DM-MMCO) algorithm is summarized in Algorithm 1.

When the offloading decision vector ${\bf{\tilde{c}}}$ is achieved as stated in section III, the problem (P1) can be rewritten as

subject to constraints (5c)-(5d), where $\zeta\!=\!\sum\nolimits_{i\in{{\mathds{U}}_{l}}}{\left({\lambda_{i}^{e}E_{loc,i}+\lambda_{i}^{t}T_{loc,i}}\right)}+\sum\nolimits_{j\in{{\mathds{U}}_{o}}}{\left({\lambda_{j}^{e}E_{c,j}+\lambda_{j}^{t}T_{c,j}}\right)}$ is a constant and can be omitted in the following analysis. Obviously, the problem (23) is a nonconvex problem and is difficult to solve. Let ${\max_{k\in{{\mathds{U}}_{o}}}}\left\{{{B_{k}}/{R_{k}}}\right\}=q$ and the problem (23) can be transformed into

To solve the problem (P6), the quadratic transform proposed in [16] is adopted to solve the problem (24) in this paper. Then, a new objective is given by ${f_{q}}\left({{\mathds{Q,V,W}},q}\right)=\sum\limits_{k\in{{\mathds{U}}_{o}}}{\left({2{w_{k}}\sqrt{\lambda_{k}^{e}{B_{k}}\left\|{{{\bf{Q}}_{k}}}\right\|_{F}^{2}}-w_{k}^{2}{R_{k}}+\lambda_{k}^{t}q}\right)}$, where ${\mathds{W}}=\left\{{{w_{k}},k=1,\ldots,{N_{o}}}\right\}$ with ${w_{k}}\in{\mathds{R}}$ introduced for each offloading MD. The the optimization problem (24) can now be recast to

Then, the multidimensional quadratic transform in [16] is applied to each SINR term inside the ${R_{k}}$ expression in (3), and further recast ${f_{q}}$ to ${f_{qm}}$ as in (26)

where $\xi$ is defined as

$\xi{\rm{=}}{\!\!}\sum\nolimits_{l=1}^{d}{\!\!}{w_{k}^{2}B_{W}{{\log}_{2}}{\!\!}\left({\!}{1{\!\!}+{\!\!}2{\mathop{\rm Re}\nolimits}{\!\!}\left\{{\!\!}{z_{k(l)}^{H}v_{k(l)}^{H}{H_{k}}{q_{k(l)}}}{\!\!}\right\}{\!\!}-{\!\!}z_{k(l)}^{H}{I_{N}}{z_{k(l)}}}{\!\!}\right)}$.

The final reformulation of the problem (24) after the twice use of the quadratic transform now becomes

where ${\mathds{Z}}$ denotes the set of auxiliary variables $\left\{{{z_{k(l)}}\in C|\forall k\in{{\mathds{U}}_{o}},l=1,\ldots,d}\right\}$ with ${z_{k(l)}}\in{\mathds{C}}$ introduced for each data stream $\left({k,l}\right)$. Based on the above definitions, we can see that when ${\mathds{Z}}$ and ${\mathds{W}}$ are both fixed, the problem (27) is a convex problem over ${\mathds{Q}}$ and ${\mathds{V}}$, so the optimal ${\mathds{Q}}$ and ${\mathds{V}}$ can be efficiently found by using the standard numerical method [17].

Therefore, we propose an iterative optimization algorithm to solve the problem (27). According to [16], when all the other variables are fixed, the optimal ${z_{k(l)}}$ is given by

After updating ${z_{k(l)}}$, the optimal ${w_{k}}$ is

Then, the optimal ${\mathds{Q}}$ is obtained by solving the problem (27) when ${\mathds{V}}$, ${\mathds{Z}}$ and ${\mathds{W}}$ are fixed. At last, the optimal ${\mathds{V}}$ is achieved by solving the problem (27) when ${\mathds{Q}}$, ${\mathds{Z}}$ and ${\mathds{W}}$ are fixed. The whole iterative optimization algorithm for solving (27) is summarized in Algorithm 2.

In this section, simulation results are provided to show the performance of the proposed algorithms. Simulations is performed on a Monte Carlo simulation on a Matlab-based simulator. We adopt the 3GPP pathloss model [18] and Rayleigh fading with zero mean and unit variance. The background noise density is set to be $-175$dBm/Hz and $B_{W}=10$MHz. ${B_{k}}$ is uniformly chosen from 0.8MB to 1.2MB. We have $P_{\max}^{k}{\rm{=0}}{\rm{.1W}}$, $\tau_{\max}^{k}{\rm{=3s}}$ and $p_{k}^{id}{\rm{=0}}{\rm{.005W}}$ for each MD. ${f_{loc,k}}$ and ${f_{c,k}}$ for MD $k$ are uniformly chosen from 0.2G to 0.5G cycles/s and 0.8G to 1G cycles/s, respectively. Unless stated otherwise, some system parameters are set as follows: ${M}{\rm{=}}16$, ${N}=d=2$, $\kappa={10^{-25}}$, $\alpha=237.5$ cycles/bit, $\gamma{\rm{=}}0.8$, and error tolerance $\varepsilon{\rm{=}}{10^{-3}}$. Note that we set $\lambda_{k}^{e}=1$ and $\lambda_{k}^{t}=0$ as the default values. For comparison, we also simulate the following offloading schemes: 1) Local-only: all the MDs compute their tasks locally; 2) OP-MMSE: each MD uses single antenna to offload computation tasks to the BS simultaneously. The MDs only have transmit power control, and MMSE receiver is used at BS side; 3) FDMA: MDs equipped with single antenna use orthogonal frequency resources to offload computation tasks and maximum transmit power is used; 4) TDMA: MDs equipped with single antenna sequentially offload computation tasks to the BS and maximum transmit power is used.

Figure 2 shows the energy consumption versus the number of MDs for different offloading schemes. It can be observed that the energy consumption of all offloading schemes increases with the increasing number of MDs. From the figure, it can be seen that the proposed DM-MMCO has the lowest energy consumption. It is because that the transmission time delay can be greatly reduced by using MIMO transmission and the energy efficiency is improved. Since the MD has limited computation capability, the local-only method has the highest energy consumption. It can be shown that without transmit beamforming and multiple data streams, the performance of OP-MMSE is inferior than the proposed DM-MMCO. The energy consumption for FDMA and TDMA grows quickly when the number of MDs increases. It can also be seen that when the number of MDs is small (e.g. 2, 3 and 4), the energy consumption of TDMA is smaller than FDMA. However, when the number of MDs is larger than 4, the energy consumption of TDMA grows fastly and is obviously larger than the energy consumption of FDMA. The reason is that the time delay will accumulate in TDMA and some MDs will choose to compute tasks at local if the maximum tolerable delay is not satisfied. This leads to the increasing of energy consumption in TDMA. It can be noted that the performance gap between the proposed DM-MMCO and OP-MMSE is small, the reason is that the power control method in OP-MMSE also adopts the quadratic transform proposed in [16] and can mitigate inter-user interference at certain degree. In addition, the quadratic transform proposed in [16] is similar to the WMMSE algorithm, which is described in [19]. Therefore, the performance gap between the proposed DM-MMCO and OP-MMSE is small. However, the proposed FP framework in [16] is more computationally efficient than WMMSE, which is proved in [19].

Figure 3 shows the impact of maximum tolerable delay on the energy consumption of different offloading schemes. It can be observed that with the increasing of maximum tolerable delay, all offloading schemes experience the decreasing of energy consumption. It can also be seen that the energy consumption of TDMA drops quickly with the increasing of maximum tolerable delay, which means more MDs choose to offload computation tasks and more energy consumption is reduced. It is shown that the proposed DM-MMCO has the lowest energy consumption among all the offloading schemes. It should be noted that the energy consumption of both the OP-MMSE scheme and the proposed DM-MMCO scheme decreases quickly with the increasing of maximum tolerable delay. The reason is that with the increasing of maximum tolerable delay, MDs in DM-MMCO or OP-MMSE can use less transmission power to finish task offloading, thus the energy consumption is reduced.

In this paper, a joint computation offloading and MU-MIMO transmission problem was studied in a MEC system. A joint optimization of offloading decision-making and MU-MIMO beamforming problem was formulated to minimize MDs’ cost under maximum tolerable delay and transmission power constraints. To solve the optimization problem, two low complexity algorithms were proposed to obtain the offloading decisions and MU-MIMO beamforming matrices, respectively. Simulation results showed that the proposed algorithms have excellent performance in reducing the energy consumption and time delay of computation offloading.

This work is supported in part by the National Nature Science Foundation of China under Grant 61571115 and 61701254, and in part by Natural Science Foundation of Jiangsu Province BK20170901.