Optimization of Offloading Scheme Algorithm for Large Number of Tasks in Mobile-Edge Computing

Introduction

Mobile-edge computing is emerging as an effective solution to the problem of executing a large number of tasks on resource constrained devices. In this report, we have proposed an algorithm which uses the concepts of local search and bi-section search to find an approximately optimal task offloading scheme. Our model consists of two devices, denoted as D1 and D2, each executing a certain number of tasks, M and N respectively, with k^th task on D2 requiring the output of (k-1)^th task on D2 and M^th task on D1. To the best of our knowledge, the theoretical complexity of our algorithm, is much less than the algorithms used in previous work. In our experiments, we have compared the approximate solutions generated by our algorithm to the solutions generated by the naive search algorithm. We observed that the approximate solutions are discovered in very few iterations of our algorithm and they satisfy the constraint of one climb policy as well. The sum of energy-time cost of both the devices is also observed to be very close to the best solutions. Hence, very decent offloading schemes are generated in short spans of times for a large number of tasks. The code and the results of our experiments are available at https://github.com/czgdp1807/MECOptimalOffloading.

The rest of the report is organized as follows: i) We have implemented the bi-section search algorithm as described in [1]. We have used a modified version of the pseudocode of the algorithm given in [1]. This algorithm finds the optimal parameters for a given offloading scheme for computing the energy-time cost which was used by [2]. Numerical results for this algorithm are also given in this section itself. ii) In this section, we have proposed a new algorithm which uses local search and the previously mentioned bi-section search algorithms to find an approximately optimal offloading scheme. We have compared the results generated by our algorithm with the best solutions using the parameters in [1] as benchmark.

Bi-section search

This algorithm is used to solve the following optimisation problem,

min_{(a, p, f)} η₁ + η₂

s.t.

T₁^wait ≤ T₂^wait;
0 ≤ p_i,j ≤ P_peak;
0 ≤ f_i,j ≤ f_peak;
a_i,j ∊ {0, 1} ∀ i, j;
0 ≤ i ≤ T_j; 1 ≤ j ≤ 2;

where,

a denotes the offloading scheme, which is given beforehand to the bi-section search algorithm, the a_i,j entry, the i^th task on j^th device, is either 1 i.e., the task is offloaded to another device with more computing power or 0 i.e., the task is computed locally on the same device;
p is a data structure whose each entry p_i,j denotes the optimal transmission power which is to be used by the i^th task on j^th device for offloading the task;
f is a data structure whose each entry f_i,j denotes the optimal CPU frequency to be used by the j^th device for the i^th task;
P_peak denotes the maximum transmission power of any resource constrained device;
f_peak denotes the maximum CPU frequency of any resource constrained device;
T₁^wait denotes the time for which the device has to wait for obtaining the results from another device;
T₂^wait denotes the time for which the device has to wait for obtaining the results from the previous task;
T_j is the number of tasks executed on j^th device;
η₁ is the energy-time cost for the first device in our model with weight β₁^T given to the time part of the cost and β₁^E ( which is 1 - β₁^T) weight given to the energy part;
η₂ is the energy-time cost for the second device in our model with weight β₂^T given to the time part of the cost and β₂^E ( which is 1 - β₂^T) weight given to the energy part;

The pseudocode for the bi-section search algorithm is given below.

Algorithm
input ∊, the precision factor; a, offloading scheme matrix.
output the optimal matrices f and p

set v^UB = β₂^T and v^LB = 0
repeat
 set v = (v^UB + v^LB)/2, λ = v, μ = β₂^T - v
 Compute f according to (26) in [1]
 Compute p according to (27) in [2]
 if T₁^wait - T₂^wait < 0 then
  v^UB = v
 else
  v^LB = v
 end if
until |T₁^wait - T₂^wait| < ∊

Results for Bi-section search

We implemented the above algorithm using Python 3.6.9 and used Matplotlib 3.2.1 to plot the graphs for observing the trends. The configuration parameters in [1] have been used as a benchmark for our implementation. We observed from the numerical and graphical results that our implementation successfully follows the trends as expected. See the graphs here.

In each of the above graphs, note that, as we climb up the blue or red lines, the β₂^T increases which is expected and matches with the results given in [1].

Local search algorithm

Here we have presented an algorithm to find an offloading scheme i.e., a which is approximately optimal and is very near to the best scheme. [1] has suggested two algorithms for the same task, first one being the naive search whose time complexity is O(16^M+N) and therefore will be very inefficient for even moderately large Ms(~10) and Ns(~10). They have used one climb policy to scale down the search of offloading scheme and the resulting algorithm has a time complexity of O(M²N²) which is an improvement but the algorithm will still be inefficient for large Ms(> 100) and N(> 100). As can be seen in the pseudocode below, our algorithm starts from a random offloading scheme and updates it in a direction where the total energy-time cost is reduced. It executes for a fixed number of iterations and hence it’s time complexity is O(MN) much faster than any of the algorithms suggested in [1].

Algorithm
input n, the maximum number of iterations;
output a, offloading scheme;

set a to random two dimensional matrix with each entry ∊ {0, 1}
set η₁ to ∞, η₂ to ∞
set k to 0
repeat
 set i to 0
 repeat
  set flag to True, j to 0
  repeat
   if flag == False then
    break
   a_copy = a
   update(a, i, j)
   Bi-section search 0.001, a
   if η₁^new + η₂^new <= η₁ + η₂ then
    set η₁ to η₁^new, η₂ to η₂^new
    set flag to False
   else
    a = a_copy
   j = j + 1
  until j < T₂
  i = i + 1
 until i < T₁
 k = k + 1
until k < n

The update function updates a, the offloading scheme by inverting the values at a_i,1 and a_j,2 to move the a to the neighbouring offloading scheme.

Results for Local search

We evaluated our local search algorithm on the parameters in [1]. We observed that the best solution generated by inefficient algorithms and the solutions generated by our algorithms were not having much difference which helped us in concluding that our local search algorithm can be a much better replacement for the naive algorithms for finding the optimal offloading scheme. We have provided a comparison for supporting our claims.

For T₁ = 3 and T₂ = 5, the best solution is found as, a₁ = {0, 1, 1} and a₂ = {1, 1, 0, 1, 1} with energy-time costs, η₁ = 0.213 and η₂ = 0.489 i.e., η₁ + η₂ = 0.702. Note that this algorithm took 4096 calls to Bi-section search.
For the same parameters, the local search algorithm found, a₁ = {1, 0, 1} and a₂ = {0, 0, 1, 0, 0} as solutions with energy-time costs, η₁ = 0.384 and η₂ = 0.373 i.e., η₁ + η₂ = 0.757. This algorithm took just 5 calls to Bi-section search to find the solution.
The following can be noted from the above two results, i) Both naive and local search algorithm have found an offloading scheme which satisfies the one climb policy, which states that the offloading of tasks from device to server will happen at most once or in other words, there will be at most only one i such that, a_i,j = 1 and a_i-1,j = 0. ii) The total energy-time costs are very close for the schemes found by both the algorithms. Numerically, the energy time costs are only 7.8% higher for the local search algorithm’s solution as compared to the best solution which is not a big difference at the level of precision we are working. One interesting observation is that the local search has found a scheme which has, η₁ ~ η₂, however, in the best solution, η₂ > η₁. The benefit of η₁ ~ η₂ is that both the devices will require similar costs irrespective of the number of tasks performed by them, thus saving costs for the device performing greater number of tasks. iii) The local search algorithm is way faster than the naive search. Specifically for the above example, local search took 0.122 % of the computation efforts as compared to the naive search.

Conclusions

We conclude this report by summarising the work done in the project,

1. A modified form of the Bi-section search algorithm first presented in [1] is implemented. The trends in β₂^T, for fixed values of β₁^T, are observed to be as expected.
2. An efficient local search algorithm is proposed which finds the offloading schemes which are very close to the optimal offloading schemes using very little computation efforts as compared to the search algorithms presented in [1].
3. Numerical benchmarking has been done on the basis of parameters used in [1] for each algorithm implemented to verify the correctness and to support our claims.

References

[1] J. Yan, S. Bi, and Y. J. Zhang, “Optimal offloading and resource allocation in mobile-edge computing with inter-user task dependency,” accepted by IEEE GLOBECOM, Dec. 2018.
[2] Y. Mao, C. You, J. Zhang, K. Huang, and K. B. Letaief, “A survey on mobile edge computing: The communication perspective,” IEEE Commun. Surveys Tuts., vol. 19, no. 4, pp. 2322–2358, Fourthquarter 2017.