# Randomization-Based Dynamic Programming Offloading Algorithm for Mobile Fog Computing

Authors: Wenle Bai; Zhongjun Yang; Jianhong Zhang; Rajiv Kumar
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Offloading to fog servers makes it possible to process heavy computational load tasks in local devices. However, since the generation problem of offloading decisions is an N-P problem, it cannot be solved optimally or traditionally, especially in multitask offloading scenarios. Hence, this paper has proposed a randomization-based dynamic programming offloading algorithm, based on genetic optimization theory, to solve the offloading decision generation problem in mobile fog computing. The algorithm innovatively designs a dynamic programming table-filling approach, i.e., iteratively generates a set of randomized offloading decisions. If some in these sets improve the decisions in the DP table, then they will be merged into the table. The iterated DP table is also used to improve the set of decisions generated in the iteration to obtain the optimal offloading approximate solution. Extensive simulations show that the proposed DPOA can generate decisions within 3 ms and the benefit is especially significant when users are in multitask offloading scenarios.


---

## Body

## 1. Introduction

With the increasing popularity of smart devices, smart applications provide a rich user experience while placing stringent demands on computing power. Due to the limitations of mobile devices, it becomes a challenge to maintain the quality of service when traditional devices are faced with heavy computational demands. To solve this problem, mobile fog computing (MFC) [1] has been proposed to compensate for the lack of computing power in local devices. And, it alleviates the computing congestion of cloud by offloading tasks to fog nodes at the edge of the network, as well.In MFC, there are two major problems to be solved. The first is how to determine whether a task should be offloaded or not. The other is how to balance the delay performance and energy consumption as much as possible, while offloading tasks. In order to solve the above problems, some offloading algorithms have been proposed in the literature. In [2], by modeling task generation as a Poisson process, the processing in the server is modeled as an M/M/1 model. A closed-form expression for the offloading delay is derived to find the global optimal solution with the lowest latency performance. Subdividing a task into the offloadable and non-offloadable part, the study in [3] constructs an opportunistic offloading model. A delayed offloading model is introduced in [4], in which tasks will wait as long as possible until the WIFI link is available to offload before the dead time arrives. Aiming at minimizing the energy consumption, the work in [5] develops an offloading interaction model based on the auction mechanism, while the authors of [6] propose an incentive propagation mechanism (IPM) algorithm.In the traditional MFC network, a key research point is the joint design of the offloading decision and system resource allocation to optimize system effectiveness. The study in [7] proposes a fair and energy-minimized task offloading (FEMTO) algorithm, which considers three important characteristics: the energy consumption of the offloading, the historical average energy of the F-AP, and the priority of the F-AP. The offloading decision problem and the uplink channel assignment problem are designed as a quadratic constrained quadratic programming (QCQP) problem in [8]. Then, the proposed matrix algorithm is used to solve the QCQP problem to obtain the suboptimal solution. The offloading problem in [9] is solved by transforming it into a nonconvex QCQP problem and then solving that with the proposed semidefinite relaxation algorithm.With the boon of deep learning in recent years, some studies have combined deep learning with the MFC. The study in [10] proposes a joint computational offloading and resource allocation algorithm based on deep reinforcement learning (DRL), which is used for deriving a suboptimal solution for the optimization problem. A deep learning-based offloading algorithm is proposed in [11], which uses the trained DNN to generate offloading decisions for each task. The work in [12] introduces an empirical replay technique based on the reinforcement learning, which improves the convergence rate of the offloading algorithm. Similarly, the study in [13] adds a layer of the LSTM network to the deep Q network, which is used for predicting the amount of tasks to be received by the fog node at the next moment. Compared to the deep Q algorithm, the algorithm with the LSTM network can arrive at the optimal decision faster. Although these intelligent algorithms have very high offloading accuracy, the training of the network requires a long time. Meanwhile, these excessively complex algorithms will additionally increase the computational burden of IoT (Internet of Things) devices. Hence, they are not applicable for real-time computational offloading of MFC networks in time-varying environments.In this work, attention is paid to the task offloading problem in an MFC network and a dynamic programming offloading algorithm (DPOA) based on randomization is proposed to solve the offloading decision generation problem. The achievements obtained in this paper are as follows:(1)
Randomization is introduced in the DPOA, where the system periodically generates a random set of offloading decisions of 1 or 0. And, these randomized decisions are used to construct a two-dimensional dynamic programming (DP) table, as well.(2)
The DP table is populated in a novel way, which avoids the double computation of the common decision cells in the generated random set. After enough iterations of the algorithm, the optimal approximate solution can be obtained from a query of the populated DP table.(3)
Extensive simulations show that the algorithm is highly responsive. And, the algorithm maintains optimal approximate decision generation within 3 ms for a wide range of system parameter settings.The rest of this paper is as follows: the model of the MFC network and the closed-form expressions for latency and energy consumption are presented in Section2, as well as the construction of an energy-latency weighted sum minimization problem. The DPOA is referred in Section 3. Section 4 mainly provides the analysis of simulations. And, the conclusions are given in the last section.


## 2. Network Model and Problem Formulation

### 2.1. Network Model

As shown in Figure1, the network model investigates an MFC network consisting of multiple users, a single fog access point (F-AP), and a remote cloud server, where users interact with the F-AP through a wireless channel for data interaction. The F-AP and the cloud server are interconnected with an optical fiber. Assume that each user has N mutually independent tasks to compute, denoted as N=1,2,…,N. Each task is indivisible to the user and can be processed either locally, offloaded to a F-AP for processing or further to the cloud server.Figure 1
Network scenarios and offloading computation models for mobile fog computing.The offloading decision of then-th task at the local side is represented by the binary variable XFn∈0,1. Then, XFn=0 (XFn=1) represents the task that will be processed at the local side (offloaded to the fog). Similarly, let XCn∈0,1 represent the n-th task’s decision that is on the fog side. XCn=0 denotes the task that will remain on the fog side for computation, and, conversely, XCn=1 represents the task being further offloaded to the cloud.


### 2.2. Problem Formulation

In the local computing mode, as the task is computed only in the local processor without involving data upload, the total energy and total time consumed are equal to those of the processor. The size ofn-th task is denoted by Mn. Let κ and fL represent the energy consumption per bit of task computed and the computation rate (cycle/s) at the local device, respectively. The energy consumption and latency of Mn computed locally are(1)ELn=κMn,(2)TLn=MnϕfL,where ϕ indicates the number of CPU revolutions required that processes per bit of data (cycle/bit), which is determined by the CPU process. Without loss of generality, it is presumed that the all covered ϕ of the devices in this paper are all equal.WhenXFn=1 is in place, the task will be offloaded to the nearest F-AP over the wireless network. The task offloaded to the fog will be redistributed by the algorithm, and some will be further offloaded to the cloud server. According to [9, 11, 14, 15], it is known that the offloading backhaul data is extremely small, much smaller than of the offloaded, so the return cost is chosen to be ignored. Let the transmission rate between users and F-AP be BF; then, the transmission time to the fog is(3)TtFn=MnBF.WithfF denoting the processing rate of the fog server, the computation time consumed in the fog is(4)TFn=MnϕfF.About the cloud computing model, F-APs are interconnected with the cloud server through the fiber and the transfer rate between both is expressed in terms ofBC. Then, the total time cost from the local side to the cloud can be recorded as(5)TtCn=MnBF+MnBC.Representing the processing rate of the cloud server byfC, the cloud computing time cost for the n-th task is(6)TCn=MnϕfC.For energy consumption, as the essence of offloading is to handle complex or large tasks, which is difficult for the local side, this paper only considers the transmission and standby energy consumption in the local device while ignoring the energy cost at the server. Hence, the transmission energy consumption of then-th task offloading to the fog is shown in(7)Etn=αMn,where α is the energy consumption of the local device that transmits per bit of data.In addition, the output of the local device is modeled as anM/M/1 queue and the system distributes the n+1th task only when the n-th has been processed. Meanwhile, if task n is offloaded, the local device will remain in the standby mode. Using P to present the standby power of the device, the standby energy consumption during offloading Mn can be expressed as Ewn:(8)Ewn=P⋅XFnTtFn+TFn+XFnXCnTtCn+TCn.For any user in the MFC network, the total latency and energy consumption of processing all tasks can be expressed, respectively, as follows:(9)T=∑n=1N1−XFnTLn+XFn1−XCnTtFn+TFn+XFnXCnTtCn+TCn,(10)E=∑n=1NXFnEtn+1−XFnELn+Ewn.In order to minimize the total energy and time consumption to complete all tasks, this paper introduces a system utilityΘ defined as a weighted sum of energy and latency, as shown in(11)ΘX=E+γT,where X=XFn,XCn|n∈N and γ∈0,+∞; (J/s) is the weight variable. When γ=0, the system will focus only on the energy performance, and if a balance between energy and latency is to be maintained, then γ=1 is required. For γ>1, the system focuses more on the rapidity of the offloading.After that, an optimization problem (P) is constructed to minimize the overall utility of the systemΘX with the help of optimizing the offloading decision X for each task. The optimization problem is as follows:(12a)P:Θ∗X=minimizeXF,XCE+γT,(12b)subject toXF∈0,1,(12c)XC∈0,1,(12d)T≤Tlimit,(12e)gamma≥0.where (12b) and (12c) constrain the binary nature of the offloading decision. Besides, (12d) is the offloading time limit. If the latency is greater than the time limit, then the decision will not be adopted. Moreover, the algorithm will add an extremely large penalty value, such as Θ∗X=Θ∗X+σ where σ=109, to the system utility at this point to force the decision to be eliminated in subsequent comparisons.Generally speaking, a binary decision problem of this kind belongs to the N-P problem, which has no exact solution by default. In the next section, we will propose a dynamic programming offloading algorithm, which is based on randomized decision, to find the optimal approximate solution of such problems. Furthermore, the definitions of the symbols used in this paper are shown in Table1.Table 1
Symbols used in the paper.
SymbolMeaningMnData size of usersn-th taskXFnLocal-to-fog offloading decision of usersn-th taskXFn=1offloading0localXCnFog-to-cloud offloading decision of usersn-th taskXCn=1cloud0fogfLLocal computing ratefFFog computing ratefCCloud computing rateBFBandwidth between the local and fogBCBandwidth between the fog and cloudTLnLocal processing time of usersn-th taskkEnergy cost of the device computed per bit of dataTFnFog processing time of usersn-th taskαEnergy consumption per bit of data in local-to-fog transmissionTCnCloud processing time of usersn-th taskPDevice standby powerTtFnTransmission delay ofn-th task from the local to fogϕNumber of CPU revolutions required to process per bit of dataTtCnTransmission delay ofn-th task from the fog to cloudTTotal delay of the userELnLocal energy consumption of usersn-th taskγThe relative importance of delay and energyEtnUploaded energy cost of usersn-th taskσSystem-set penalty valueEwnStandby energy cost of the device when it offloads tasknETotal energy cost of the userHNumber of algorithm iterationsΛhThe set of random offloading decisions produced at theh-th iterationΛh∗Theh-th offloading decision set after updatingηRelative offloading accuracy rate


## 2.1. Network Model

As shown in Figure1, the network model investigates an MFC network consisting of multiple users, a single fog access point (F-AP), and a remote cloud server, where users interact with the F-AP through a wireless channel for data interaction. The F-AP and the cloud server are interconnected with an optical fiber. Assume that each user has N mutually independent tasks to compute, denoted as N=1,2,…,N. Each task is indivisible to the user and can be processed either locally, offloaded to a F-AP for processing or further to the cloud server.Figure 1
Network scenarios and offloading computation models for mobile fog computing.The offloading decision of then-th task at the local side is represented by the binary variable XFn∈0,1. Then, XFn=0 (XFn=1) represents the task that will be processed at the local side (offloaded to the fog). Similarly, let XCn∈0,1 represent the n-th task’s decision that is on the fog side. XCn=0 denotes the task that will remain on the fog side for computation, and, conversely, XCn=1 represents the task being further offloaded to the cloud.


## 2.2. Problem Formulation

In the local computing mode, as the task is computed only in the local processor without involving data upload, the total energy and total time consumed are equal to those of the processor. The size ofn-th task is denoted by Mn. Let κ and fL represent the energy consumption per bit of task computed and the computation rate (cycle/s) at the local device, respectively. The energy consumption and latency of Mn computed locally are(1)ELn=κMn,(2)TLn=MnϕfL,where ϕ indicates the number of CPU revolutions required that processes per bit of data (cycle/bit), which is determined by the CPU process. Without loss of generality, it is presumed that the all covered ϕ of the devices in this paper are all equal.WhenXFn=1 is in place, the task will be offloaded to the nearest F-AP over the wireless network. The task offloaded to the fog will be redistributed by the algorithm, and some will be further offloaded to the cloud server. According to [9, 11, 14, 15], it is known that the offloading backhaul data is extremely small, much smaller than of the offloaded, so the return cost is chosen to be ignored. Let the transmission rate between users and F-AP be BF; then, the transmission time to the fog is(3)TtFn=MnBF.WithfF denoting the processing rate of the fog server, the computation time consumed in the fog is(4)TFn=MnϕfF.About the cloud computing model, F-APs are interconnected with the cloud server through the fiber and the transfer rate between both is expressed in terms ofBC. Then, the total time cost from the local side to the cloud can be recorded as(5)TtCn=MnBF+MnBC.Representing the processing rate of the cloud server byfC, the cloud computing time cost for the n-th task is(6)TCn=MnϕfC.For energy consumption, as the essence of offloading is to handle complex or large tasks, which is difficult for the local side, this paper only considers the transmission and standby energy consumption in the local device while ignoring the energy cost at the server. Hence, the transmission energy consumption of then-th task offloading to the fog is shown in(7)Etn=αMn,where α is the energy consumption of the local device that transmits per bit of data.In addition, the output of the local device is modeled as anM/M/1 queue and the system distributes the n+1th task only when the n-th has been processed. Meanwhile, if task n is offloaded, the local device will remain in the standby mode. Using P to present the standby power of the device, the standby energy consumption during offloading Mn can be expressed as Ewn:(8)Ewn=P⋅XFnTtFn+TFn+XFnXCnTtCn+TCn.For any user in the MFC network, the total latency and energy consumption of processing all tasks can be expressed, respectively, as follows:(9)T=∑n=1N1−XFnTLn+XFn1−XCnTtFn+TFn+XFnXCnTtCn+TCn,(10)E=∑n=1NXFnEtn+1−XFnELn+Ewn.In order to minimize the total energy and time consumption to complete all tasks, this paper introduces a system utilityΘ defined as a weighted sum of energy and latency, as shown in(11)ΘX=E+γT,where X=XFn,XCn|n∈N and γ∈0,+∞; (J/s) is the weight variable. When γ=0, the system will focus only on the energy performance, and if a balance between energy and latency is to be maintained, then γ=1 is required. For γ>1, the system focuses more on the rapidity of the offloading.After that, an optimization problem (P) is constructed to minimize the overall utility of the systemΘX with the help of optimizing the offloading decision X for each task. The optimization problem is as follows:(12a)P:Θ∗X=minimizeXF,XCE+γT,(12b)subject toXF∈0,1,(12c)XC∈0,1,(12d)T≤Tlimit,(12e)gamma≥0.where (12b) and (12c) constrain the binary nature of the offloading decision. Besides, (12d) is the offloading time limit. If the latency is greater than the time limit, then the decision will not be adopted. Moreover, the algorithm will add an extremely large penalty value, such as Θ∗X=Θ∗X+σ where σ=109, to the system utility at this point to force the decision to be eliminated in subsequent comparisons.Generally speaking, a binary decision problem of this kind belongs to the N-P problem, which has no exact solution by default. In the next section, we will propose a dynamic programming offloading algorithm, which is based on randomized decision, to find the optimal approximate solution of such problems. Furthermore, the definitions of the symbols used in this paper are shown in Table1.Table 1
Symbols used in the paper.
SymbolMeaningMnData size of usersn-th taskXFnLocal-to-fog offloading decision of usersn-th taskXFn=1offloading0localXCnFog-to-cloud offloading decision of usersn-th taskXCn=1cloud0fogfLLocal computing ratefFFog computing ratefCCloud computing rateBFBandwidth between the local and fogBCBandwidth between the fog and cloudTLnLocal processing time of usersn-th taskkEnergy cost of the device computed per bit of dataTFnFog processing time of usersn-th taskαEnergy consumption per bit of data in local-to-fog transmissionTCnCloud processing time of usersn-th taskPDevice standby powerTtFnTransmission delay ofn-th task from the local to fogϕNumber of CPU revolutions required to process per bit of dataTtCnTransmission delay ofn-th task from the fog to cloudTTotal delay of the userELnLocal energy consumption of usersn-th taskγThe relative importance of delay and energyEtnUploaded energy cost of usersn-th taskσSystem-set penalty valueEwnStandby energy cost of the device when it offloads tasknETotal energy cost of the userHNumber of algorithm iterationsΛhThe set of random offloading decisions produced at theh-th iterationΛh∗Theh-th offloading decision set after updatingηRelative offloading accuracy rate


## 3. DPOA

In this section, a dynamic programming offloading algorithm for the MFC network, the DPOA, is proposed, in which the two-dimensional DP table is constructed to pick the current optimal binary decision for each task.Because of the similarity of the decision algorithms for the fog decision and the cloud decision, the algorithm is mainly used as an example at the fog server in this section. Since cloud-side decisions and fog-side decisions do not affect each other, when calculating fog-side decisions, we assume that all the decisions of the tasks in the cloud are 0, for example,XCn≡0XC=XCn≡0|n∈N.To store and display the offloading decisions corresponding to each task, as shown in Figure2, a DP table of size N∗N is constructed. Particularly, N is the total number of tasks. After the algorithm begins with H round-robin operations and a set of N randomly offloaded decision elements, denoted as Λh,h∈1,2,…,H is generated in each cycle. In particular, there is no connection between the set of random decisions and the offloading task. While obtaining the generated set of offloading decisions for the current cycle, the system assigns the decisions to the previously constructed DP table according to a specific law. For example, 0 is assigned to the next horizontal cell while 1 is to the next vertical cell. Exceptionally, the starting position is (1, 2) if the first decision is 0 and (2, 1) is for 1. In addition, the construction of the DP table is based on the randomization theory in [9].Figure 2
Two examples of filling out the DP table.
(a)(b)As an example, assumingN = 6, the algorithm constructs a 6 ∗ 6 DP table. Let all the decision sets generated by the first cycle be Λ1=010010 and suppose the decision during the second cycle is Λ2=110101 (as shown in Figure 2(a) with blue numbers) or Λ2=100110 (in Figure 2(b) with red numbers) with two examples. As the first place of Λ1 is 0, the starting cell is (1, 2). Since the second place of Λ1 is 1, the next vertical cell of the previous cell (1, 2) will be assigned to 1, such as (2, 2) = 1. Similarly, with the third place being 0, the next horizontal cell of cell (2, 2) will be assigned to 0, i.e., (2, 3) = 0. The table is filled according to the above rules so as to get the table in Figure 2.Once the decision setΛh is generated, it is first filled into the table according to the rules and the overall system utility ΘXh is calculated at the same time, in which XF=ΛhandXC≡0. Obviously, if the number of iterations is large enough, there will be cases that the Λh has a common subset with the previous cells in the table with different decisions, as in (2, 2) in Figure 2(b). We will consider the utility values Θ0,0 and Θ1,0 for the cell under different offloading decisions, respectively, and select the decision corresponding to the lowest value to replace the original one. Then, the updated set is noted as Λh∗, followed by updating the overall system utility at this point as ΘXh∗, specifically XF=Λh∗.When all the elements inΛh are filled, the final ΘXh∗ is compared with the system utility ΘXh−1∗ of the h-1th cycle. In the special case, when h is equal to 1, then the ΘX0 for the 0-th time is equal to the system utility corresponding to the full 0 set as Λ0. If the utility value of the current loop is greater than of the previous one, the new set is replaced with the old like Λh∗=Λh−1∗. Furthermore, the utility value of the current loop is replaced with the old value as ΘXh∗=ΘXh−1∗, as well. Conversely, if the existing utility value is less than the value of the previous loop, the existing offloading decision is held without change.Having completed all the cycles, the decision setΛH∗ after the H-th cycle is the optimal offloading decision XF in the local-to-fog stage, i.e., XF=ΛH∗. Obviously, if the number of cycles is sufficient, the constructed DP table will be filled up. Once the arbitrary set of offloading decisions generated at this point is filled into the table, the resulting updated set Λh∗ is set as the corresponding optimal solution of the algorithm. And, the code of the DPOA is detailed in Algorithm 1.Algorithm 1:DPOA.
Input: number of tasks N; size of tasks Mn,n∈N;Output: optimal offloading decision set ΛH∗;(1)Initialization: initialize the DP table and set the Tlimit;(2)forh = 1, 2, …, Hdo(3) Generate random offloading decision setsΛh;(4) Fill in the DP table according to the rules and calculate the system utilityΘXh for Λh;(5)if(the filled decisions have a common set and not the same as the cells in the previous table)then(6) Calculate the system utility corresponding to this decision and the original decision, respectively;(7) Select the decision corresponding to the lower value to replace the original decision;(8) RenewΛh∗ and ΘXh∗;(9)else(10) Execute the following:Λh∗=Λh and ΘXh∗=ΘXh;(11)ifΘXh∗>ΘXh−1∗or (T>Tlimit) then(12) Execute the following:Λh∗=Λh−1∗ and ΘXh∗=ΘXh−1∗;For the decision algorithm on the cloud server, it is approximately the same as on the fog. Furthermore, if the fog decision for taskn satisfies XFn=0, then its cloud decision is also 0 (XCn=0|XFn=0,n∈N). In the next section, a large amount of simulations will be used to verify the speed and accuracy of the DPOA.


## 4. Evaluation and Simulation

In this section, extensive simulation is provided to evaluate the offloading performance of the DPOA. Specifically, it is assumed that the number of tasks to be offloaded by the user is 20, whose size is randomly distributed in the range of 2 MB to 20 MB. Furthermore, the computational energy consumption of the tasks is3.25×10−7J/bit [9] when being processed in the local device and 1.42×10−7J/bit [9] is for the transmit energy per bit of the device. And, the standby power of the device is constant at 40 mw. Moreover, the processing speed of the local device, the fog server, and the cloud server is set to fL=2.1×108cycle/s, fF=5×109cycle/s, and fC=10×109cycle/s [9], respectively. The wireless transmission rate between the local and F-AP is 15 Mbps and from the fog to cloud is 40 Mbps [15]. Besides, ϕ=100cycle/s, Tlimit=1200ms, H=500, and γ=1J/s are further set.The proposed DPOA is compared with the existing SRA (semidefinite relaxation approach) algorithm in the literature [9] and the Greedy algorithm, as shown in Figure 3. Besides, the data when the tasks are computed all locally and all in the cloud are added for reference. Figure 3 illustrates that offloading tasks can significantly reduce the processing latency and energy consumption compared to local computation. The addition of fog computation (DPOA, SRA, and Greedy) to the system can further reduce the utility compared to only cloud computation. From the data in Figure 3, it can be seen that the DPOA is able to find a better solution compared to the mentioned benchmark algorithm (SRA [9] and Greedy).Figure 3
Comparison of the system utility for different algorithms.Here, we define the relative offloading accuracy rate of the DPOA, denoted byη:(13)η=ΘSRAΘDPOA.where ΘSRA denotes the system utility value corresponding to the decision generation by the SRA algorithm, while ΘDPOA represents the value of the DPOA under the same parameters.Figure4 analyzes the performance of the algorithm at different numbers of iterations. In Figure 4(a), the relative accuracy rate increases gradually as the number of iterations continues to increase. When the number of H is higher than 500, the value of the rate tends to be smooth, i.e., the algorithm reaches the convergence state. As the number of iterations increases, the system utility value of the DPOA is decreasing, such as the line graph in Figure 4(b). And, when H is greater than 500, the system utility value tends to be stable. However, from the histogram in Figure 4(b), higher H values correspond to higher decision time points for the system, so that a single increase in the number of iterations may weaken the rapidity of the algorithm.Figure 4
Performance under different number of iterations “H”: (a) convergence of the DPOA; (b) total time cost and system utility.
(a)(b)In Figure5, we consider the offloading when the user is in a wireless transmission rate variation scenario with a transmission rate BF range of 5 Mbps to 25 Mbps. As can be seen in Figure 5(a), the energy under the DPOA is much lower than that of the full cloud computing and outperforms that of the benchmark algorithm. In a poor communication scenario, such as BF=5Mbps, all-local computation is more cost-effective than offloading in terms of energy consumption because of the relatively heavy energy consumption required to offload. However, it is noticed in Figure 5(b) that the all-local computation exceeds the time limit, so the optimal solution is the DPOA in comparison.Figure 5
Comparison of the DPOA and the benchmark algorithms (SRA [5] and Greedy), when time limit = 1200: (a) energy consumption; (b) time cost.
(a)(b)The relationship between the time cost and the wireless transmission rate is exhibited in Figure5(b). As the transmission rate increases, the advantage of offloading computation over non-offloading becomes gradually obvious and the latency of the system to perform offloading computation decreases.As illustrated in Figure6, the performance of the algorithm for different γ has been investigated. It can be seen from the figure that as the value of γ increases, the system utility also increases gradually. However, the utility of the DPOA is always lower than that of the SRA and the Greedy, which means that the DPOA gives a superior approximate solution in comparison. Based on Figures 3, 5, and 6, it can be concluded that the DPOA consistently outperforms the mentioned benchmark algorithm in terms of comprehensive offloading performance.Figure 6
System utility values of different offloading algorithms under differentγ.More specifically, the time cost of this algorithm in generating offloading decisions under different numbers of tasks is also analyzed, as shown in Figure7. Not surprisingly, it can be noticed that the decision-elapsed time of the DPOA increases almost linearly as the number of tasks increases from 10 to 35. At the same time, the average decision time curve shows that with the changing number of tasks, the algorithm can steadily maintain the optimal offloading decision within 3 ms. The above experiments illustrate that the algorithm can handle the massive task offloading problem without reducing its own efficiency and is suitable for multitask offloading scenarios.Figure 7
Time cost for generating decision under different number of tasks using the DPOA.In Figure8, we further investigate the impact of the time limit (Tlimit) on the energy efficiency of the algorithm. Adopting the energy consumption in the case of all-local computing as the benchmark, Figure 8 shows the percentage energy savings of Tlimit relative to the benchmark. It can be seen from the figure that as the time limit is gradually relaxed, more tasks can be offloaded to the server and thus more energy can be saved. Compared with the all-local computing model, the DPOA can reduce the energy consumption of the local device processing tasks by about 9% to 32% while meeting the time constraints.Figure 8
Percentage of energy saved by using the DPOA compared to the all-local computing method, under different time limits.


## 5. Conclusion

Aiming at the offloading decision generation problem in MFC, this paper proposes a randomization-based dynamic programming offloading algorithm, DPOA, to solve this problem. The algorithm uses randomization to cyclically generate a random set of offloading decisions while constructing an overall system utilityΘX, including the total energy and time cost, to dynamically populate the DP table by minimizing the system utility. The simulation results verify that the proposed algorithm is accurate and outperforms the existing benchmark algorithm. Furthermore, the DPOA can better adapt to scenarios with changing transmission rates. However, at higher network rates, it will offload as many tasks as possible to the server, thus converging quickly to the optimal solution. Besides, the algorithm can generate near-optimal offloading decisions in 3 ms and its time cost does not increase drastically with the number of tasks. In conclusion, we hope that this DPOA can be applied in decision time-sensitive MFC scenarios, such as smart IoT in 6G, to improve the efficiency of real-time system offloading.



---

*Source: 4348511-2021-08-31.xml*