Utility Aware Offloading for Mobile-Edge Computing

We provide a gradient-based approach for utility-aware task offloading. The basic idea of the gradient method is to solve the dual problem. We consider the dual decomposition for Problem ( 9 ). Owing to the separability of Constraints ( 10 ) and ( 11 ), we present the Lagrangian form of the primal problem.

(26) $$L(\lambda ,\xi )={\displaystyle \underset{i=1}{\overset{N}{\sum }}}\log (1+{\lambda }_i{d}_i)+\xi \left(\tau -{\displaystyle \underset{i=1}{\overset{N}{\sum }}}{\lambda }_i{c}_i\right)$$

(27) $$\mathrm{s}.\mathrm{t}.{\displaystyle \frac{{\lambda }_i{d}_i}{r_i}}+{\displaystyle \frac{{\lambda }_i{c}_i}{f_e}}+(1-{\lambda }_i)\times {\displaystyle \frac{c_i}{f_i}}⩽t_i,\forall i\in 𝒩$$

(28) $${\displaystyle \frac{{\lambda }_i{d}_i{p}_i}{r_i}}+(1-{\lambda }_i)\times p_i^{\mathrm{loc}}{c}_i⩽e_i,\forall i\in 𝒩$$

(29) $$0⩽{\lambda }_i⩽1,\forall i\in 𝒩$$

We can easily know that

$$L(\lambda ,\xi )=\underset{i=1}{\overset{N}{\sum }}\{\log (1+{\lambda }_i{d}_i)-\xi {\lambda }_i{c}_i\}+\xi \tau ,$$

and $L(\lambda ,\xi )$ is a strictly concave function.

Without the constraints, the maximum value of $L(\lambda ,\xi )$ can be achieved by a given $\xi$ . For a given $\xi$ , ${\lambda }_i^{\star }$ is defined as follows:

(30) $${\lambda }_i^{\star }(\xi )=\arg \underset{{\lambda }_i⩾0}{max}[\log (1+{\lambda }_i{d}_i)-\xi {\lambda }_i{c}_i]$$

${\lambda }_i^{\star }(\xi )$ can be obtained by $\frac{\partial L(\lambda ,\xi )}{\partial {\lambda }_i}=0$ . For $\forall i\in 𝒩$ , we have

(31) $${\displaystyle \frac{\partial L(\lambda ,\xi )}{\partial {\lambda }_i}}={\displaystyle \frac{d_i}{\left(1+{\lambda }_i{d}_i\right)\ln 2}}-\xi c_i$$

(32) $${\lambda }_i^{\star }(\xi )={\displaystyle \frac{1}{\xi c_i\ln 2}}-{\displaystyle \frac{1}{d_i}}$$

According to strict concavity, ${\lambda }_i^{\star }(\xi )$ is unique. The dual problem is as follows:

(33) $$g(\xi )={\displaystyle \underset{i=1}{\overset{N}{\sum }}}g({\lambda }_i^{\star },\xi )+\xi \tau$$

(34) $$\mathrm{s}.\mathrm{t}.g({\lambda }_i^{\star },\xi )=\log (1+{\lambda }_i^{\star }{d}_i)-\xi {\lambda }_i{c}_i$$

(35) $${\lambda }_i^{*}(\xi )={\displaystyle \frac{1}{\xi c_i\ln 2}}-{\displaystyle \frac{1}{d_i}}$$

(36) $$\xi ⩾0$$

Based on the preceding analysis, the gradient approach can be applied:

(37) $$\xi (l+1)={\left[\xi (l)-\phi \left(\tau -\underset{i=1}{\overset{N}{\sum }}{\lambda }_i\left(\xi \left(l\right)\right)\right)\right]}^{+}$$

where $l$ is the iteration index, $\phi >0$ is a small positive step size, and ${[\cdot ]}^{+}$ denotes the projection onto the nonnegative quadrant.

Theorem 3 If we do not consider the Constraints ( 10 ) and ( 11 ), then the dual variable $\xi (m)$ converges to the dual optimal ${\xi }^{\star }$ as $m\to \mathrm{\infty }$ , and the primal variable ${\lambda }_i^{\star }\left(\xi (m)\right)$ also converges to the primal optimal variable ${\lambda }_i^{\star }$ .

Proof The objective function of Problem ( 9 ) is strictly concave. The problem satisfies Slater’s condition. Thus, the primal Problem ( 9 ) and dual Problem ( 29 ) are strong dualities, if we do not consider the constraints on delay latency and energy cost. As the duality gap is zero, the solution of Problem ( 26 ) is unique because of the strong duality. Therefore, the dual variable $\xi (m)$ converges to the dual optimal ${\xi }^{\star }$ as $m\to \mathrm{\infty }$ , and the primal variable ${\lambda }_i^{\star }\left(\xi (m)\right)$ also converges to the primal optimal variable ${\lambda }_i^{\star }$ .

We can obtain the optimal solution for the primal problem by solving the dual problem. Constraints ( 10 ) and ( 11 ) are linear functions with respect to ${\lambda }_i$ . The feasible solution space is convex. The dual solution $\xi (m+1)$ leads to the primal solution $\lambda$ , when $m\to \mathrm{\infty }$ . In the iterative process, we should check the boundary conditions for ${\lambda }_i$ . For a given ${𝒯}_i=$ $<d_i,c_i,t_i,e_i,p_i,p_i^{\mathrm{loc}}>$ , the boundary condition for ${\lambda }_i$ is easily obtained due to the separability of Constraints ( 10 ) and ( 11 ).

According to the pseudocode as shown in Algorithm 1, the computation complexity depends on the $\delta$ and initial value of ${\xi }_O$ .

Designing an exact algorithm with polynomial-time cost for optimal offloading scheme is difficult. In this section, we prove that the objective function of the proposed problem is increasing and submodular. Then, we provide a greedy algorithm called Increment-based Approximation Algorithm for Offloading Scheme (IAAOS). The approximation ratio bound is proved to be $1+{\displaystyle \frac{1}{\mathrm{e}-1}}$ .

Theorem 4 The objective function of Problem ( 9 ) is submodular.

Proof We denote $\lambda =\{{\lambda }_1,\mathrm{\dots },{\lambda }_N\}$ as a given feasible offloading scheme. For convenience, we define a unit set $I(k,i)=\{0,\mathrm{\dots },{10}^{-k},0,\mathrm{\dots },0\}$ . $\lambda +I(k,i)$ will generate a new set $\hat{\lambda }=\{{\lambda }_1,\mathrm{\dots },{\lambda }_{i-1},{\lambda }_i+{10}^{-k},{\lambda }_{i+1},\mathrm{\dots },{\lambda }_N\}$ , in which the schemes of all the tasks are the same as $\lambda$ , and expect ${\lambda }_i$ added by ${10}^{-k}$ .

We denote $\delta (\lambda ,k,i)$ as the increment of the utility where only ${\lambda }_i$ is added by ${10}^{-k}$ . Thus we can have the following:

(38) $$\delta (\lambda +I(k,i),\lambda )=U(\lambda +I(k,i))-U(\lambda )=$$ $$\log (1+{\lambda }_i{d}_i+{10}^{-k}{d}_i)-\log (1+{\lambda }_i{d}_i)$$

Since $\log (1+{\lambda }_i{d}_i)$ is a monotone increasing function, we know $\delta (\lambda +I(k,i),\lambda )>0$ .

For any given $h$ and $j\ne i$ , we can have

(39) $$\delta (\lambda +I(h,j)+I(k,i),\lambda +I(h,j))=$$ $$\log (1+{\lambda }_j{d}_j+{10}^{-h}{d}_j)+\log (1+{\lambda }_i{d}_i+{10}^{-k}{d}_i)-$$ $$\log (1+{\lambda }_j{d}_j+{10}^{-h}{d}_j)-\log (1+{\lambda }_i{d}_i)=$$ $$\delta (\lambda +I(k,i),\lambda )$$

For any given $h$ and $j=i$ , we can get

$$\delta (\lambda +I(h,i)+I(k,i),\lambda +I(h,i))=$$ $$\log (1+{\lambda }_i{d}_i+({10}^{-h}+{10}^{-k})d_i)-$$ $$\log (1+{\lambda }_i{d}_i+{10}^{-h}{d}_i).$$

Based on Lagrange mean value theorem, it can be known that

(40) $$\{\begin{array}{c}\delta (\lambda +I(k,i),\lambda )=\frac{d_i{10}^{-k}}{(1+x_1{d}_i)\ln 2},\hfill \\ \delta (\lambda +I(h,i)+I(k,i),\lambda +I(h,i))=\frac{d_i{10}^{-k}}{(1+x_2{d}_i)\ln 2}\hfill \end{array}$$

where $x_1\in (\lambda ,\lambda +{10}^{-k})$ and $x_2\in (\lambda +{10}^{-h},\lambda +{10}^{-h}+{10}^{-k})$ . And then we can have

(41) $$\delta (\lambda +I(h,i)+I(k,i),\lambda +I(h,i))<\delta (\lambda +I(k,i),\lambda )$$

According to the definition of submodular set function^{[ 33 ]}, the objective function of Problem ( 9 ) is submodular.

In the following, we propose an increment per-cost-based greedy algorithm and analyze the approximation ratio.

Step 1. We enumerate all feasible solutions of cardinality $3$ .

Step 2. For each feasible solution, we find the offloading task with the largest increment per cost. Let the corresponding $\lambda$ be increased by ${10}^{-k}$ , until Constraints ( 10 )-( 13 ) are not be satisfied. Then, $k$ is the input parameter for precision, which can be defined by the users.

Step 3. Finally, the algorithm returns the offloading scheme with the largest utility among all the schemes derived from Step 2, thereby obtaining the final result.

Based on the preceding analysis, Algorithm 2 presents the pseudocode of calculating the feasible offloading scheme.

Corollary 1 For a given precision parameter $k$ , let $Q_{\mathrm{OPT}}(k)$ denote the utility of the optimal solutions of Problem ( 9 ). We denote the utility derived from the solution of Algorithm 2 as $Q_{\mathrm{IAAOS}}(k)$ . Then, the approximation ratio $r={\displaystyle \frac{Q_{\mathrm{OPT}}(k)}{Q_{\mathrm{IAAOS}}(k)}}$ satisfies

(42) $$r⩽1+\frac{1}{\mathrm{e}-1}$$

Proof Based on Theorem 4, the objective function of Problem ( 9 ) is increasing and submodular. According to Ref. [ 34 ], the provided greedy-based approximation algorithm is with ratio bound $1+{\displaystyle \frac{1}{\mathrm{e}-1}}$ .

In Corollary 1, we note that the approximation ratio is also related to precision parameter $k$ . This condition means that for $\forall i\in \{1,2,\mathrm{\dots },N\}$ , ${\lambda }_i\in$ $\{0,1\times {10}^{-k},2\times {10}^{-k},\mathrm{\dots },{10}^k\times {10}^{-k}\}$ .

$N^3$ feasible schemes exist, such that ${\displaystyle \underset{i=1}{\overset{N}{\sum }}}{\lambda }_i⩽3\times$ ${10}^{-k}$ . According to Algorithm 2, the time complexity for enumerating all feasible solutions of cardinality $3$ is $O(N^3)$ . For each feasible scheme $\lambda (h)$ , the complexity for greedily increasing ${\lambda }_i(h)$ by ${10}^{-k}$ is $O\left(\min \{{\displaystyle \frac{N\tau }{c_{\min }}},{10}^k\}\right)$ , where $c_{\min }=\min \{c_i|i=1,2,$ $\mathrm{\dots },N\}$ . Then, the cost is $O\left({\displaystyle \frac{N^4\tau }{c_{\min }}}\right)$ from Lines $4$ $-$ $14$ . Based on the preceding analysis, the computation complexity is $O\left({\displaystyle \frac{N^4\tau }{c_{\min }}}\right)$ . The space complexity is $O(N^3)$ . In conclusion, the proposed algorithm can be implemented in time complexity of $O\left({\displaystyle \frac{N^4\tau }{c_{\min }}}\right)$ and space complexity of $O(N^3)$ .