# An Auction-Based Bid Prediction Mechanism for Fog-Cloud Offloading Using Q-Learning

Authors: Reza Besharati; Mohammad Hossein Rezvani; Mohammad Mehdi Gilanian Sadeghi
Journal: Complexity
 (2023)

---

## Abstract

In the fog computing paradigm, if the computing resources of an end device are insufficient, the user’s tasks can be offloaded to nearby devices or the central cloud. In addition, due to the limited energy of mobile devices, optimal offloading is crucial. The method presented in this paper is based on the auction theory, which has been used in recent studies to optimize computation offloading. We propose a bid prediction mechanism using Q-learning. Nodes participating in the auction announce a bid value to the auctioneer entity, and the node with the highest bid value is the auction winner. Then, only the winning node has the right to offload the tasks on its upstream (parent) node. The main idea behind Q-learning is that it is stateless and only considers the current state to perform an action. The evaluation results show that the bid values predicted by the Q-learning method are near-optimal. On average, the proposed method consumes less energy than traditional and state-of-the-art techniques. Also, it reduces the execution time of tasks and leads to less consumption of network resources.


---

## Body

## 1. Introduction

Recently, a new paradigm called fog computing has emerged, also known as “cloud at the edge” [1]. The use of this technology in areas such as e-health [2, 3], industry [4, 5], vehicular traffic management [6–8], and agriculture [9] is expanding rapidly. The core idea of fog computing is to transfer large volumes of data from the Internet of Things (IoT) devices to the remote cloud, especially for delay-constraint applications. Here, if an end device’s computing capacity is insufficient, the task is offloaded to a near fog device. Similarly, if the resources in the fog device are inadequate, the task is offloaded to the remote cloud.A review of the literature shows that the primary concern in most fog computing research is the minimization of execution delays. This operation, if performed alone, may result in higher energy consumption throughout the system. This is because, with such a single goal, mobile devices tend to offload their tasks to the nearest fog, which does not necessarily lead to minimal total energy consumption. Therefore, performing a joint optimization of delay and energy consumption is necessary.So far, extensive research has been conducted on offloading optimization in fog computing. Some of the essential methods used in the literature are game theory [10], auction theory [1, 11, 12], probabilistic modeling [13], heuristic [14], and metaheuristic [15]. Recently, the use of machine learning methods, especially reinforcement learning (RL) [16] to optimize offloading has received much attention from the research community. Here, each agent learns to behave in a way that leads to optimizing a predetermined goal by performing a series of actions and inspecting the reward/penalty. This learning method is inspired by behavioral psychology. In other words, the RL enables an agent to learn in an interactive environment using experiences gained from previous actions. For example, when a child’s hand burns in the face of heat, he/she quickly learns that fire is dangerous. Pleasure/pain is an excellent example of the reward/penalty through which humans and animals learn environmental behavior.We believe that the auction theory is one of the most important mathematical tools to motivate fog nodes to participate in offloading operations. We consider the bandwidth of services as a commodity. Fog nodes and cloud datacenter play the role of bidders and auctioneers, respectively. Each fog node has an output queue (buffer). Once the output buffer becomes full, the fog node requests the auction operation by sending a message to the upstream (parent) node. The parent node announces the winner after collecting the bids of all downstream nodes. In the proposed mechanism, nodes participating in the auction report their bid values to the corresponding parent nodes. The node with the highest bid value wins the auction and offloads its tasks to the parent node. Bid value has an important impact on the winning of a participating node. The operation is performed suboptimally if the buffer of the winner node is empty or it has no task to offload. This, in turn, leads to increased energy consumption and latencies in executing tasks. Therefore, there is a need to design an optimal auction mechanism. For this purpose, the designed mechanism must guarantee optimal bidding. In this paper, we use RL to predict bid values.Various studies have been conducted for bid prediction using RL. The difference between these studies is in the goals and, most importantly, the subtleties used in the RL system design. Designing actions, states, and reward functions are some of the critical differences among previous researches. The main contribution of this paper is as follows:(i)
We solve the joint minimization of latency and energy consumption with the Q-learning method. Unlike other RL research, we model the system with queuing theory to better capture agents’ behavior in the real world.(ii)
We design a price-based reward function in the Q-learning model. In this function, each joule of energy consumption has a predetermined price. This paper complements one of the state-of-the-art research [1], in which each agent uses a second-price sealed-bid (SPSB) auction mechanism for offloading. In our modeling in this paper, the user who wins the auction has a different state than the others. The winning user can immediately use the fog device resources to offload his/her tasks. Nevertheless, our proposed model considers different situations for other users who may resubmit their requests shortly.The remainder of this paper is organized as follows: Section2 reviews the most critical studies on offloading optimization based on RL methods; Section 3 explains the system model; Section 4 describes the proposed method; Section 5 presents the evaluation results of the proposed method along with statistical analysis; finally, Section 6 concludes the study and outlines future research trends.


## 2. Related Work

Machine learning is a primary method to solve the offloading problem. Significant efforts have focused on supervised learning methods [4, 17] and reinforcement learning (RL). Given that our proposed method is based on RL, we focus on this type of research in this section. The RL is a method based on rewarding desirable behaviors or punishing undesirable behaviors [16]. Each agent can understand and interpret the environment and perform several actions here. The agent’s sequence of movements over time through trial and error leads to learning the optimal state. The main difference between previous research is in arranging the above details and presumptions.We now proceed to explain research in the scope of RL. Most of the research in this area is related to deep reinforcement learning (DRL). Readers interested in studying DRL models for IoT applications can refer to [18, 19]. Santos et al. [20] proposed a DRL method for embedding service function chains (SFCs) in a fog environment using mixed integer linear programming (MILP). They aimed at joint minimization of energy consumption and cost. Then, they showed that the proposed method could achieve a 95% acceptance ratio for user requests. Gazori et al. [21] proposed a task scheduling algorithm to minimize the latency and cost of tasks. They also paid special attention to load balancing and showed that the proposed method could resolve the challenges of the single point of failure. Zhang et al. [7] targeted the problem of selecting and switching mobile network operators (MNOs) by considering the cost of switching and QoS requirements among MNOs and cloud/fog servers. Using the DRL, they proposed a switching policy that could guarantee the average long-term cost of each vehicle with reliable latency. Performance evaluations using datasets collected from a city-wide LTE network showed that their proposed approach could reduce the cost of payment by any vehicle connected to the fog. Rahman et al. [22] proposed an algorithm to minimize fog radio access networks (F-RANs) latency. Their algorithm uses DRL to decide on local execution or offloading and allocates the desired amount of computing resources and power. A similar study was conducted by Jazayeri et al. [23] to jointly minimize latency and energy consumption using the DRL. Their results showed that the proposed method could reduce latency, energy consumption, and network usage compared to full local execution and First-Fit (FF) methods.Chen et al. [24] solved the same problem using the deep deterministic policy gradient (DDPG) algorithm. The most important advantage of this method is that it does not need to know the transmission probabilities in different network states. The simulation results showed the superiority of the proposed method compared to the policy gradient (PG), deterministic policy gradient (DPG), and actor-critic (AC) methods. Baek and Kaddoum [25] proposed a combination of DRL and game theory to solve the offloading optimization problem. In this game, each fog node cooperates to maximize local rewards while it only has access to local observations. To deal with partial visibility, the DRL approximates the optimal value functions. The results show that the proposed algorithm can achieve a higher success rate and fewer overflows than the baseline methods. Shi et al. [8] aimed at minimizing execution delay using the AC-based DRL. The proposed algorithm maximizes expected rewards and policy entropy so that vehicles are motivated to share their idle computing resources through dynamic pricing. Chen et al. [5], by leveraging collaborative DRL, propose a method to minimize the delay and energy consumption of tasks. This study considers the mobility of mobile users to select the most effective samples of shared experiences. Also, they use a distributed collaborative method to learn the probability distribution of the approximate reward and optimize the parameters. The simulation results show that their method has fast convergence and high stability. The DRL method has also been used in fog computing for other purposes. Some of these goals include caching [26], combining blockchain with fog computing [2], and cloud-fog optical networks [27]. Readers interested in studying other DRL-based research can refer to [28, 29].We now review research conducted using other RL methods. Mebrek et al. [30] targeted the problem of joint computation and communication optimization through game theory and RL. Their goal is to achieve an optimal policy that makes a trade-off between energy consumption and QoS. The core idea of the proposed method is to learn the optimal offloading policy without having prior knowledge of system dynamics. Cui et al. [31] proposed an optimal offloading mechanism based on the multiarmed bandit (MAB) theory for unmanned surface vehicles (USVs). Their sole purpose is to minimize offloading delays in environments where the topology and wireless channel states constantly change. Dehury and Srirama [32] conducted a similar study to provide personalized services. Neelakantam et al. [33] designed an offloading system using Q-learning to minimize passenger waiting time in a smart city. They showed that the Q-learning method is more effective than SARSA’s popular RL method. Nassar and Yilmaz [34] targeted the problem of latency minimization in the F-RAN for 5G communications. They compared the performance of several RL methods, including SARSA and expected SARSA, with the baseline method. Their results show that RL methods consistently achieve the best possible performance regardless of the IoT environment.So far, very few studies have been conducted regarding bid value prediction in online auctions using RL. For example, in [35], the stochastic game predicts the bid value. The authors then solved the problem with multiagent RL. In [36], the environment depends on the number of applied impressions. Therefore, the proposed solution is not suitable for dynamic and online environments. In [37], the Markov decision process (MDP) method was used to hold an online auction. The authors first model the bid prediction problem with MDP and define transition and reward functions based on users’ click rates. They then solve the problem by leveraging dynamic programming. In [38], CMDP optimizes the bid value in a sequential auction. The authors model the CMDP with a six-element tuple. Tuple elements are state, action, state transition function, reward, cost, and constraint value, respectively. They consider click-through rate (CTR) as the state and the number of clicks on each ad as the reward. After modeling the CMDP, they solve the problem by leveraging linear programming.RL has also been used in other areas of fog computing. Due to space limitations, we do not review this research in depth. The most interesting topics that have attracted the attention of researchers are traffic signal controlling [39], secure offloading [40], medical information processing [41], load balancing [42, 43], and service function chain allocation [44].After reviewing the literature, the following points can be presented as the most important differences between our modeling and previous research:(1)
None of the above research has used queuing theory to model user behavior. Such modeling allows us to have closed-form relations for delay and energy. This, in turn, can be used later in the design of the reward function. In other words, the system model formulation based on queuing theory provides a more realistic description of the fog-cloud environment.(2)
None of the above research has designed the reward function based on price. We set a predetermined price for each joule of energy consumption. In addition to bidding values, these prices are used in the reward function, which will be formulated later in (32).


## 3. System Model

An illustration of the system model is shown in Figure1. The system includes M mobile users, F fog devices, and a central cloud. Each mobile user can only connect to a fog node via the base station (BS). The set of mobile users is denoted by U=u1,u2,…,uM. Also, the set of fog nodes is denoted by F=f1,f2,…,fF. Every mobile user has several tasks to be performed. These tasks are entered into the system continuously. If the user’s computational resources are insufficient to perform the task or the user intends to save his/her resources, he/she can offload them into a fog node. Similarly, if the computational resources of the fog node are insufficient, the task is offloaded to the central cloud. For each fog node fj, we denote all users who are offloading to it by a set Cfj. For example, in Figure 1, Cf1=u1,u2,u3,u4 indicates that users u1, u2, u3, and u4 are offloading their tasks to the node f1. Similarly, in this figure, we can write Cf2=u5,u6 and Cc1=f1,f2. The notations used in this study are shown in Table 1. We model mobile user traffic in this study as an M/M/1/K queue. As mentioned in [1], this model can capture the behavior of mobile users better than M/M/1, which was previously used by researchers [45]. Also, we model each fog node as an M/M/c/K queue [1, 46].Figure 1
An illustration of the system model.Table 1
The notations used in this research.
Sym.Symbol descriptionMTotal number of mobile usersFTotal number of fog devicesUThe set of all mobile usersFThe set of all fog devicesCfjThe set of users who are offloading their tasks to the fog devicefjλuiThe arrival rate of tasks to a mobile useruiλuikThe arrival rate of tasks to a mobile userui, when there are already k tasks in itλuiaThe rate that is acceptable to a mobile useruiλfjThe arrival rate of tasks to a fog nodefjλfjaThe rate that is acceptable by the fog devicefjμuiThe rate of service for a mobile useruiμuikThe rate of service at the mobile userui, when there are already k tasks in itμfjThe rate of service at the fog devicefjμThe rate of service for each server inside the fog deviceθiThe average task size entered by a mobile userui (bit)σiThe number of CPU cycles required to perform each bit of the task in the mobile useruiρuiThe utilization of a mobile useruiρfjThe utilization of a fog devicefjπuikProbability of havingk tasks in a mobile user ui's deviceπuiKThe probability of blocking the execution of tasks for a mobile useruiπui0Probability of not submitting any task to the mobile useruiπfjkProbability of havingk tasks in a fog device fjπfjK′The probability of blocking the execution of tasks for a fog devicefjπfj0Probability of not submitting any task to the fog devicefjCuiComputing capacity in a mobile userui (cycle/sec)CfjComputing capacity at the fog devicefj (cycles/sec)tuilResponse time for each task when it is executed locally by the mobile useruitfjlResponse time for each task when it is executed by a fog devicefjtuioThe time required for each task to be offloaded by the mobile userui toward a fog devicetfjoThe time required for each task to be offloaded by the fog devicefj toward the central cloudtuisThe time required for a task to be executed using the computing capacity of a mobile useruitfjsThe time required for a task to be executed using the computing capacity of a fog devicefjLuiThe average number of tasks by the mobile useruiLfjNumber of tasks queued in the fog devicefjriThe rate at which tasks are offloaded from the mobile deviceui to the relevant fog deviceRiThe uplink rate at which tasks are offloaded from the mobile deviceui to the relevant fog devicehiThe gain of the channel located between the mobile userui and the base station (BS)WThe channel bandwidthN0The noise of the channel between the mobile user and the fog devicePuilPower required to execute a task locally at the mobile userui (watts)PfjlPower required to execute a task locally at the fog devicefj (watts)PuioPower required to offload a task from the mobile userui to the relevant fog device (watts)PfjoPower required to transfer a task from the fog devicefj to the central cloud (watts)PitThe transmission power of the mobile useruiPimaxThe maximum transmission power of the mobile useruiEuilThe amount of energy consumed by the mobile userui to perform tasks locallyEuiremThe remaining energy in the mobile userui (J)EuiThrThe threshold limit for the lowest energy level in the mobile userui (J)EfjlThe amount of energy consumed by the fog devicefj to perform tasks locallyEfjremThe remaining energy in the fog devicefj (J)EfjThrThe threshold limit for the lowest energy level in the fog devicefj (J)EuioThe amount of energy consumed by the mobile userui to offload a taskEfjoThe amount of energy consumed by the fog devicefj to offload a taskpujPrice per joule of energy to be paid by the mobile userui (US$/J)buifjThe bid price per joule of energy to be paid by the mobile userui to the fog device fj (US$/J)buiThe budget of the mobile userui (US$)NfjThe number of end devices connected to a fog devicefjmuiThe expected payoff of an end deviceui∈U when it reports buifj to the parent fog device fj, while other buyers tell the truthquiThe probability that an end deviceui∈U gets the resource when reporting its bid value buiSThe set of all possible statesstiThe state of the mobile userui at a time tStThe system state vector at a timetTThe set of terminal statesAThe set of actionsatiThe action performed by the mobile userui at a time trt+1iThe reward that an agentui gets when moved to a new state at a time t+1QThe learned action-value functionQ∗The optimal action-value function vectorαThe learning rateγThe discount factorVsThe value function in the statesV∗sThe optimal value function in the statesFuiThe bidding distribution function for the mobile userui


### 3.1. The Edge Layer Modeling

As with previous research [1], we assume that each mobile user ui∈U can have multiple tasks to be performed. The number of these tasks follows the Poisson distribution [46] with the mean arrival rate λui. The size of each task submitted to the user ui is denoted by θi. Performing this task requires spending several processor cycles for each bit that is denoted by σi. The time needed to complete the task on the processor of the mobile device ui, hereafter referred to as local execution, is calculated as follows [47]:(1)tuis=σi.θiCui.In the above formula,Cui represents the computing capacity of the mobile user ui in cycles/sec. Therefore, the service rate on the mobile device ui is calculated as follows:(2)μui=1tuis.As mentioned earlier, we use an M/M/1/K queuing system to model the mobile user in this study. In this model, the maximum number of buffer rooms isK. If the number of tasks entered is more than K, the extra ones will be dropped. Tasks are entered at a rate λui while the acceptance rate by the mobile device is λuia. Let πuiK represent the task blocking ratio. This means that when the mobile device queue is full, only 1−πuiK percent of the tasks can be served, and the rest are not accepted [48]. For admitted tasks, the local acceptance rate, λuia, is as follows:(3)λuia=1−πuiK.λui.Tasks that are not accepted on the mobile device must be offloaded to the appropriate fog device. Before we proceed, let us define the utilization of a mobile userui as follows:(4)ρui′=λuiaμui.Given that the above birth-death process is a discrete-time Markov chain (DTMC), the following two properties always hold:(5)πuik=ρuik.πui0,(6)∑k=0Kπuik=1.Simplifying (6) and replacing it in (5) give the blocking probability (i.e., k=K) as follows:(7)πuiK=1−ρui.ρuiK1−ρuiK+1.The average number of tasks,Lui, for the mobile user ui is obtained as follows:(8)Lui=∑k=0Kk.πuik=1−ρui.ρui1−ρuiK+1∑k=0Kk.ρuik−1.After simplification, it follows that(9)Lui=ρui1−ρui−K+1.ρuiK+11−ρuiK+1.Now, applying Little’s law gives the local execution time for each task,tuil, as follows:(10)tuil=Luiλuia=1λuia.ρui1−ρui−K+1.ρuiK+11−ρuiK+1.Now, the local energy consumption of the mobile userui is calculated as follows:(11)Euil=Puil.tuil=Puilλuia.ρui1−ρui−K+1.ρuiK+11−ρuiK+1.In the above formula,Puil represents the local power of the mobile user ui. Before calculating the offloading time, tuio, let us define the offloading rate, Ri. Applying Shannon’s law, the offloading rate for each mobile device ui is obtained as follows [49]:(12)Ri=W⋅log21+Pit⋅hiN0⋅W.In the above formula,W represents the bandwidth of the communication channel. Also, Pit is the transmission energy for the mobile user ui for which 0<Pit≤Pimax. Here, Pimax is the maximum transmission power of the mobile user ui. Also, hi represents the channel gain through which the mobile user connects to the BS, and N0 denotes the noise that affects the channel during transmission. Now, the offloading time is calculated as follows:(13)tuio=πuiK.λui.θiRi.Finally, the energy consumed during the task offloading from the mobile deviceui to the relevant fog device is calculated as follows:(14)Euio=Puio.tuio=Puio.πuiK.λui.θiRi.


### 3.2. The Fog Layer Modeling

Like [1], we represent the incoming traffic to each fog device with an M/M/c/K′ model, in which there are c individual internal servers and a buffer of size K′. As mentioned in the previous section, if a task cannot be admitted to the mobile device ui∈U, it will be offloaded to the relevant fog device fj, for which ui∈Cfj. The size of a task that is submitted from the mobile device ui to the fog device fj is denoted by θi. Performing this task requires spending several processor cycles for each bit that is denoted by σi. The time required to perform the task on the fog device fj is calculated as follows:(15)tfjs=σi.θiCfj.In the above formula,Cfj represents the computing capacity of the fog device fj in cycles/sec. Therefore, the service rate on the fog device fj is calculated as follows:(16)μfj=1tfjs.At any given time, the fog devicefj may receive several tasks, each of which comes from the child nodes. Here, the child nodes are mobile devices that offload their extra tasks into the fog device. The rate of arrival of tasks to the fog device, λfj, is calculated by summing the rates submitted by the children as follows:(17)λfj=∑i∈Cfjλui−λuia.Let us denote the blocking ratio and the admitted arrival rate byπfjK′ and λfja, respectively. Now, the utilization of the fog device fj is defined as ρfj=λfj/μfj. Then, the probability that k tasks are present in the fog device is obtained as follows [37]:(18)πfjk=ρfjkk!πfj0,0≤k<c,ρfjkck−cc!πfj0,c≤k<K′.If we normalize the above equation according to the characteristics of DTMC, the probability of emptying the queue,πfj0, in the fog device fj is obtained as follows:(19)πfj0=∑k=0c−1ρfjkk!+∑k=cK′ρfjkck−cc!−1.Supposea=ρfj/c, and then with a series of simplifications, we get the following expression [1]:(20)πfj0=∑k=0c−1ρfjkk!+ρfjcc!.1−aK′−c+11−a,−1a≠1,∑k=0c−1ρfjkk!+ρfjcc!.K′−c+1−1,a=1.We now proceed to calculate the number of tasks,Lfjq, in the fog device queue. Using the definition of mathematical expectation, we write(21)Lfjq=∑k=c+1K′k−c.πfjk=∑k=c+1K′k−c.ρfjkck−cc!.πfj0=πfj0.ρfjcc!∑k=c+1K′k−c.ρfjk−cck−c=πfj0.ρfjc.ac!∑k=c+1K′k−c.ak−c−1=πfj0.ρfjc.ac!∑i=1K′−ci.ai−1=πfj0.ρfjc.ac!∂∂a∑i=0K′−cai=πfj0.ρfjc.ac!∂∂a1−aK′−c+11−a.After a series of simplifications, it follows(22)Lfjq=πfj0.ρfjc.ac!1−a21−aK′−c+1−1−a.K′−c+1.aK′−c.The rate at which tasks arrive at the fog device is calculated when the system is not full. Therefore, it follows that(23)λfka=λfk.1−πfjK′=μfk.c.On the other hand, the number of system tasks,Lfj, is equal to the number of tasks in the queue, Lfjq, plus the number of those currently being served by CPUs. This leads us to the following relation:(24)Lfj=Lfjq+c.Altogether, from (23) and (24), it follows that(25)Lfj=Lfjq+ρfk.1−πfjK′.Similar to (10), using Little’s law gives the local execution time for each task in the fog device fj as follows:(26)tfjl=Lfjλfja.Now, the local energy consumption of the fog devicefj is calculated as follows:(27)Efjl=Pfjl.tfjl=Pfjl.tfjq+1μfj.In the above formula,Pfjl represents the local power of the fog device fj. If the computing resources in the fog device are insufficient to process a task, it is offloaded to the central cloud. We denote the communication capacity between the fog device fj and the central cloud by Rj. Similar to (13), the offloading time by the fog device fj is calculated as follows:(28)tfjo=πfjK′.λfj.θiRj,i∈Cfj.Finally, the energy consumed during the task offloading from the fog devicefj to the central cloud is calculated as follows:(29)Efjo=Pfjo.tfjo=Pfjo.πfjK′.λfj.θiRj,i∈Cfj.


## 3.1. The Edge Layer Modeling

As with previous research [1], we assume that each mobile user ui∈U can have multiple tasks to be performed. The number of these tasks follows the Poisson distribution [46] with the mean arrival rate λui. The size of each task submitted to the user ui is denoted by θi. Performing this task requires spending several processor cycles for each bit that is denoted by σi. The time needed to complete the task on the processor of the mobile device ui, hereafter referred to as local execution, is calculated as follows [47]:(1)tuis=σi.θiCui.In the above formula,Cui represents the computing capacity of the mobile user ui in cycles/sec. Therefore, the service rate on the mobile device ui is calculated as follows:(2)μui=1tuis.As mentioned earlier, we use an M/M/1/K queuing system to model the mobile user in this study. In this model, the maximum number of buffer rooms isK. If the number of tasks entered is more than K, the extra ones will be dropped. Tasks are entered at a rate λui while the acceptance rate by the mobile device is λuia. Let πuiK represent the task blocking ratio. This means that when the mobile device queue is full, only 1−πuiK percent of the tasks can be served, and the rest are not accepted [48]. For admitted tasks, the local acceptance rate, λuia, is as follows:(3)λuia=1−πuiK.λui.Tasks that are not accepted on the mobile device must be offloaded to the appropriate fog device. Before we proceed, let us define the utilization of a mobile userui as follows:(4)ρui′=λuiaμui.Given that the above birth-death process is a discrete-time Markov chain (DTMC), the following two properties always hold:(5)πuik=ρuik.πui0,(6)∑k=0Kπuik=1.Simplifying (6) and replacing it in (5) give the blocking probability (i.e., k=K) as follows:(7)πuiK=1−ρui.ρuiK1−ρuiK+1.The average number of tasks,Lui, for the mobile user ui is obtained as follows:(8)Lui=∑k=0Kk.πuik=1−ρui.ρui1−ρuiK+1∑k=0Kk.ρuik−1.After simplification, it follows that(9)Lui=ρui1−ρui−K+1.ρuiK+11−ρuiK+1.Now, applying Little’s law gives the local execution time for each task,tuil, as follows:(10)tuil=Luiλuia=1λuia.ρui1−ρui−K+1.ρuiK+11−ρuiK+1.Now, the local energy consumption of the mobile userui is calculated as follows:(11)Euil=Puil.tuil=Puilλuia.ρui1−ρui−K+1.ρuiK+11−ρuiK+1.In the above formula,Puil represents the local power of the mobile user ui. Before calculating the offloading time, tuio, let us define the offloading rate, Ri. Applying Shannon’s law, the offloading rate for each mobile device ui is obtained as follows [49]:(12)Ri=W⋅log21+Pit⋅hiN0⋅W.In the above formula,W represents the bandwidth of the communication channel. Also, Pit is the transmission energy for the mobile user ui for which 0<Pit≤Pimax. Here, Pimax is the maximum transmission power of the mobile user ui. Also, hi represents the channel gain through which the mobile user connects to the BS, and N0 denotes the noise that affects the channel during transmission. Now, the offloading time is calculated as follows:(13)tuio=πuiK.λui.θiRi.Finally, the energy consumed during the task offloading from the mobile deviceui to the relevant fog device is calculated as follows:(14)Euio=Puio.tuio=Puio.πuiK.λui.θiRi.


## 3.2. The Fog Layer Modeling

Like [1], we represent the incoming traffic to each fog device with an M/M/c/K′ model, in which there are c individual internal servers and a buffer of size K′. As mentioned in the previous section, if a task cannot be admitted to the mobile device ui∈U, it will be offloaded to the relevant fog device fj, for which ui∈Cfj. The size of a task that is submitted from the mobile device ui to the fog device fj is denoted by θi. Performing this task requires spending several processor cycles for each bit that is denoted by σi. The time required to perform the task on the fog device fj is calculated as follows:(15)tfjs=σi.θiCfj.In the above formula,Cfj represents the computing capacity of the fog device fj in cycles/sec. Therefore, the service rate on the fog device fj is calculated as follows:(16)μfj=1tfjs.At any given time, the fog devicefj may receive several tasks, each of which comes from the child nodes. Here, the child nodes are mobile devices that offload their extra tasks into the fog device. The rate of arrival of tasks to the fog device, λfj, is calculated by summing the rates submitted by the children as follows:(17)λfj=∑i∈Cfjλui−λuia.Let us denote the blocking ratio and the admitted arrival rate byπfjK′ and λfja, respectively. Now, the utilization of the fog device fj is defined as ρfj=λfj/μfj. Then, the probability that k tasks are present in the fog device is obtained as follows [37]:(18)πfjk=ρfjkk!πfj0,0≤k<c,ρfjkck−cc!πfj0,c≤k<K′.If we normalize the above equation according to the characteristics of DTMC, the probability of emptying the queue,πfj0, in the fog device fj is obtained as follows:(19)πfj0=∑k=0c−1ρfjkk!+∑k=cK′ρfjkck−cc!−1.Supposea=ρfj/c, and then with a series of simplifications, we get the following expression [1]:(20)πfj0=∑k=0c−1ρfjkk!+ρfjcc!.1−aK′−c+11−a,−1a≠1,∑k=0c−1ρfjkk!+ρfjcc!.K′−c+1−1,a=1.We now proceed to calculate the number of tasks,Lfjq, in the fog device queue. Using the definition of mathematical expectation, we write(21)Lfjq=∑k=c+1K′k−c.πfjk=∑k=c+1K′k−c.ρfjkck−cc!.πfj0=πfj0.ρfjcc!∑k=c+1K′k−c.ρfjk−cck−c=πfj0.ρfjc.ac!∑k=c+1K′k−c.ak−c−1=πfj0.ρfjc.ac!∑i=1K′−ci.ai−1=πfj0.ρfjc.ac!∂∂a∑i=0K′−cai=πfj0.ρfjc.ac!∂∂a1−aK′−c+11−a.After a series of simplifications, it follows(22)Lfjq=πfj0.ρfjc.ac!1−a21−aK′−c+1−1−a.K′−c+1.aK′−c.The rate at which tasks arrive at the fog device is calculated when the system is not full. Therefore, it follows that(23)λfka=λfk.1−πfjK′=μfk.c.On the other hand, the number of system tasks,Lfj, is equal to the number of tasks in the queue, Lfjq, plus the number of those currently being served by CPUs. This leads us to the following relation:(24)Lfj=Lfjq+c.Altogether, from (23) and (24), it follows that(25)Lfj=Lfjq+ρfk.1−πfjK′.Similar to (10), using Little’s law gives the local execution time for each task in the fog device fj as follows:(26)tfjl=Lfjλfja.Now, the local energy consumption of the fog devicefj is calculated as follows:(27)Efjl=Pfjl.tfjl=Pfjl.tfjq+1μfj.In the above formula,Pfjl represents the local power of the fog device fj. If the computing resources in the fog device are insufficient to process a task, it is offloaded to the central cloud. We denote the communication capacity between the fog device fj and the central cloud by Rj. Similar to (13), the offloading time by the fog device fj is calculated as follows:(28)tfjo=πfjK′.λfj.θiRj,i∈Cfj.Finally, the energy consumed during the task offloading from the fog devicefj to the central cloud is calculated as follows:(29)Efjo=Pfjo.tfjo=Pfjo.πfjK′.λfj.θiRj,i∈Cfj.


## 4. Proposed Method

In our previous research [1], we used the auction algorithm for offloading in fog computing. Each end device has a local memory (buffer); after filling this buffer, it announces the auction request to its parent. The parent node requests bid values from its children. A child with the highest bid wins the auction and offloads its tasks to its parent (higher layer). Figure 2 and Table 2 show the sequence diagram (workflow) and the messages’ specifications of the proposed auction method.Figure 2
The sequence diagram (workflow) of messages.Table 2
The specification of messages in the proposed mechanism.
MessageAbbr.Message formatDescriptionOffloading Auction RequestOAR????????Specification of the requested source by a nodeejBidding Value RequestBVR<>The monopolist auctioneerfi asks each of his children to send him their bid valuesBidding Value ConfirmBVCxejEach bidderej submits its bid value xej to the relevant monopoly auctioneer fiFinding Winner DoneFWDwThe bidderw is introduced as the winner of the auctionInvoice Approval RequestIARmwxwThe amount of payment that the bidderw (as the auction winner) must pay to the seller fiInvoice Approval ConfirmIAC< >The winning bidderw confirms the payment mwxw to the seller fiThe bid value’s effect on the participant’s winning node is very high. Since the winner performs the offloading, the bid value significantly impacts the execution time and energy consumption. An RL method has been used to predict the bid value in the auction operation.To predict the bid value, we use one of the model-free algorithms of RL theory called Q-learning. It lies in the finite Markov decision process (FMDP) family of approaches. Here, “Q” refers to the function that the algorithm calculates. This function also called a reward function, is the expected reward, rt+1, for an action at performed in a given state st. Agents learn to treat the environment based on previous experiences they have gained. These previous experiences are captured by the Q value and controlled by the reward function. As shown in Figure 3, after each action at, the agent is moved from the state st to a new state st+1 and receives a reward rt+1. This reward reflects the importance of the action and can be the basis for deciding what to do next. The sequences of states in which each agent enters over time can be represented by s0,r0,a0,s1,r1,a1,s2,r2,a2,…,st,rt,at. In Figure 3, the environment for each fog node fi consists of the rest of the nodes, denoted by f−i. In this way, the model captures the experiences acquired from other agents. As we will see later, the model rewards/punishes the agent for these experiences. This makes the RL process more dynamic than the supervised learning case.Figure 3
Elements of Q-learning: environment, action, state, and reward.Q-learning is called model-free because it does not need any prior knowledge of the environment to learn the value of an action in a given state. It can solve the bid prediction problem with rewards without needing consistency. Here, an optimal policy can maximize the expected value of the total reward through multiple iterations. In this way, Q-training can find the optimal action-selection policy for each FMDP over time through a somewhat random policy. The components of our RL-based bid prediction approach are as follows:


### 4.1. Agent

For each fog devicefj, all mobile users ui, which are i∈Cfj, are the operating agents in the proposed modeling.


### 4.2. State

The state of the mobile userui at a time t is denoted by sti∈S, in which S represents the set of all possible states as follows:(30)S=″offload_pending″,″local_pending″,″running″.A“local_pending” state means that the user intends to perform the task locally on the end device. A “offload_pending” state means that the user intends to offload the task on the fog device to save local resources. Here, we use the second-price sealed-bid (SPSB) mechanism proposed in one of the state-of-the-art researches [1]. Here, first, the tasks of all users who want to offload are submitted to the fog device. Then, using the SPSB auction mechanism, they send their bids to the fog device. These are the prices that different users are willing to pay for each joule of energy consumption to the fog device. In other words, the unit of the bid price is the dollar per joule (US$/J). The offloading optimization problem for an end device ui∈U using SPSB is defined as follows [1]:(31)maxEmuibui,subject to(I)
The mechanism isincentive compatible (IC), i.e., the requirement that quj be nondecreasing.(II)
The mechanism isindividual rational (IR), i.e., the requirement that mui0≤0.In the above equation,muibui denotes the expected payoff of the end device ui∈U when it reports buifj to the parent fog device fj, while other buyers tell the truth. Also, quibui denotes the probability that the end device ui∈U gets the resource when reporting its bid value bui.After determining the winning user, whom we denoted byuw, the fog device allocates computing resources to him/her. At this moment, the user state changes from “offload_pending” to “running.” This means that the fog device processes the winning user’s task in a nonpreemptive way until it is completed. Let us denote all users except uw, who are losers in the auction, by e−w. These users may experience one of two situations: (a) the user remains in the same state “offload_pending” to participate in the next round of the auction or (b) the user refuses to offload, in which case, his/her state changes from “offload_pending” to “local_pending.” Thus, if the number of end devices connected to a fog device fj is Nfj, the state of all users at a time t can be represented by a Nfj-size vector St. For example, suppose four users are connected to a fog node and all, but the last one intends to offload. Now, if the third user wins the auction, the system state vector is represented as follows:St=“offload_pending,”“offload_pending,”“running,”“local_pending”. Now, if the capacity of the fog node is still sufficient, users whose state is “offload_pending” can try again to offload their tasks. For example, if at the next time t+1, the second user wins the auction, the state vector changes to St+1=“offload_pending,”“running,”“running,”“local_pending”. As is common in FMDP, at least one of the states must be defined as the terminal state T. For a user ui, if his/her state at the time t, namely sti, belongs to the set T, then its value will not change with any future action. In our problem, the state “running” is terminal, i.e., T=“running”. In other words, if a user’s task is in “running” state (that is sti∈T), it stays in that state until the task is completed.


### 4.3. Action

The action performed by the mobile userui at a time t is denoted by ati∈A. Here, A is a set of all possible actions as follows:(32)A=″local_request″,″offload_request″.The simplest way is to select an action based on a greedy strategy. In this strategy, the action is selected to have the highest value,ati≐argmaxaiQtsti,ai.


### 4.4. Transition Function

It is the probability that an agentui will move from the state sti=s to a new state st+1i=s′ when it acts ati=a. It is denoted by a matrix Ps′,r|s,a, which P:S×A×S⟶0,1 and ∑s′∑rPs′,r|s,a=1.


### 4.5. Reward Function

Depending on what action the agent chooses, it will receive a reward as follows:(33)rt+1i=−pui.Euil,pui.Euil−pui.Euio−buifj.Efjl,0,if st+1i==local_pending,else if st+1i==running,else if st+1i==offloading_pending.As stated in the above relation, if after actingati, the mobile user ui is moved to a new state local_pending, he/she will receive a reward −pui.Euil. Note that the system’s goal here is to minimize the energy consumption of mobile devices. In other words, the proposed algorithm encourages users to offload their tasks to fog devices instead of performing them locally on their own devices. If the user performs the task locally, he/she will receive a penalty pui.Euil. Simply speaking, if the user offloaded the task instead of running it locally, he/she could save pui.Euil dollars by not consuming valuable local resources. The second condition in the above relation states that if the user is moved to a state “running”, he/she will receive a reward pui.Euil−pui.Euio−buifj.Efjl. Here, the first term, pui.Euil, is the amount of money the user has saved by not performing the task locally. Simply put, if the user wanted to run the task locally instead of offloading it, he/she would have to pay pui.Euil dollars for local resource usage. The second term, −pui.Euio, is the amount of money that must be paid to transmit the task to the BS. The third term, −buifj.Efjl, is the amount of money that must be paid to the fog device to perform the task. Note that buifj is the bid price previously offered by the user ui to the fog device fj. As mentioned earlier, in this research we adopt the SPSB auction mechanism proposed by Besharati et al. [1]. When all users submit their bids to the fog device, only one of them who has offered the highest bid (here, the user ui), will win the auction. Then, the winning user ui has to pay buifj dollars for each joule of energy consumption to the fog device. Finally, the last condition in (33) states that if the user is moved to a state “offloading_pending”, he/she will not receive any reward. Although this user tends to offload the task, his/her bid price has not been the highest compared to other competitors. Therefore, the user is temporarily moved to the state “offloading_pending” so that he/she may win the auction in the next time slot.Based on performing a specific action, the agent is transferred from one state to another. The basic form of the Q-learning algorithm for the agentui is sti,ati,rt+1i,st+1i,at+1i, meaning that the agent was in the state sti, performed the action ati, received the reward rt+1i, and finally ended up in the state st+1i, from where it decided to act at+1i. By doing so, it provides a new iteration to update Qsti,ati.The Q-learning algorithm is one of the off-policy RL methods. We adopt the simplest form of it, which is called single-step Q-learning. It is defined as follows:(34)Qsti,ati⟵Qsti,ati+αrt+1i+γmaxbiQst+1i,bi−Qsti,ati.In the above formula,Q and α are the learned action-value function and learning rate, respectively. The α value strikes a balance between the agent’s findings from the environment and what he/she has learned. Also, γ denotes the discount factor, which satisfies 0≤γ≤1. A lower discount factor encourages the agent to take action sooner rather than postponing it indefinitely. In other words, it determines how much importance should be given to immediate rewards and future rewards. This helps us to avoid infinity as a reward. A value of γ=0 means that more priority is given to immediate rewards, and a value of γ=1 means that more importance is given to future rewards. In practice, the discount factor γ=0 is never learned because it only considers immediate rewards, and the discount factor γ=1 continues for future rewards, which may lead to infinity. Therefore, the optimal value for the discount factor, γ, is in the range (0, 1).After determining the transition functionP and the received reward rt+1i by the parent node (controller), the MDP problem can be easily solved using dynamic programming algorithms. Here, the core idea is to use the value function Vs to find the optimal action a∗i. The optimal action in any state sti is the action that brings the most reward to the agent. For this purpose, the state value function must be expressed in the following form, which is known as the Bellman equation:(35)V∗s=maxErt+1i+γ.V∗st+1i|sti=s,ati=a.The above formula after simplification can be rewritten as follows:(36)V∗s=maxa∑s′,rPs′,r|s,ar+γ.V∗s′.One of the most common ways to solve the Bellman equation is to rewrite it in the following recursive form:(37)Vt+1s=maxa∑s′,rPs′,r|s,ar+γ.Vts′.Thus, the value of all states can be obtained. Given that0≤γ≤1, it can be proved that the Bellman equation will converge and, therefore, the solution is as follows:(38)V∗s=limt⟶∞Vts.The key advantage of Q-learning over other RL methods is that it converges very quickly. The main reason is thatQ can directly approximate the optimal action-value function, q∗. Here, the policy serves to determine which state-action pairs to be visited and updated. Like most RL methods, the prerequisite for convergence here is that all pairs continue to be updated. Under this assumption and other common indefinite approximation conditions in the sequence of size-step parameters, it is found that Q converges with a probability of 1 to q∗. Another advantage of Q-learning is that it does not require a specific model of the environment. In RL terminology, it is a model-free method and does not require a predetermined policy to find any optimal state-action pair.Note that the Q-learning algorithm is executed both in the fog layer and in the cloud layer. Due to space limitations and the similarity of pseudocodes, we only show the offloading operation in the fog layer. The pseudocode of the Q-learning for the offloading problem is shown in Algorithm1. Also, Algorithms 2 and 3 represent the pseudocode of the mobile user ui and the fog device fj (controller), respectively. Algorithm 3 itself calls Algorithm 4 to calculate the bid price per joule of energy consumption based on the second-price sealed-bid (SPSB) mechanism [1]. Let us now give a brief description of these algorithms. In lines 5–8 of Algorithm 2, if the energy consumption is within the allowable range and does not exceed the remaining energy of the mobile device, the task is performed locally. In this case, the state of the task, sti, is changed to “local_execution” and then the user adds the revenue from the local energy consumption, pui.Euil, to his/her current budget. In lines 10–12 of Algorithm 2, because the energy consumption has exceeded the residual energy of the mobile device, the task is offloaded to the fog device by calling Algorithm 3. In this case, the costs of offloading, pui.Euio, and remote processing, buifj.Efjl, are deducted from the mobile user’s budget. Similarly, in lines 7–14 of Algorithm 3, if the task energy consumption exceeds the remaining energy of the fog device, it is offloaded to the remote cloud. In this case, in addition to the cost of offloading, pui.Euio, and processing in the fog device buifj.Efjl, the cost of offloading to the remote cloud, pfj.Efjo, must also be deducted from the user’s budget. Otherwise, if the user’s budget is sufficient to process the task on the fog device, the task state is changed to “offload_pending”; otherwise, it must be processed locally on the mobile device itself. In lines 15–17 of Algorithm 3, a second-price sealed-bid (SPSB) auction mechanism is held by calling Algorithm 4. Readers interested in a detailed study of Algorithm 4 can refer to [1]. Finally, after determining the auction winner, the task state for the user who won the auction is changed to “running”. Then, in line 18 of Algorithm 3, the optimal action-value function vector Q∗ is found by calling Algorithm 1. This vector specifies exactly on which device each task should be performed. The task must be performed locally on the user’s device, the fog device, or the remote cloud. Here, an important question arises regarding Algorithm 4: if the bid value of two nodes is the same, which one will have more priority? According to the implementation in [1], in such a case, the node whose remaining buffer capacity and the remaining energy are less has a higher priority.


## 4.1. Agent

For each fog devicefj, all mobile users ui, which are i∈Cfj, are the operating agents in the proposed modeling.


## 4.2. State

The state of the mobile userui at a time t is denoted by sti∈S, in which S represents the set of all possible states as follows:(30)S=″offload_pending″,″local_pending″,″running″.A“local_pending” state means that the user intends to perform the task locally on the end device. A “offload_pending” state means that the user intends to offload the task on the fog device to save local resources. Here, we use the second-price sealed-bid (SPSB) mechanism proposed in one of the state-of-the-art researches [1]. Here, first, the tasks of all users who want to offload are submitted to the fog device. Then, using the SPSB auction mechanism, they send their bids to the fog device. These are the prices that different users are willing to pay for each joule of energy consumption to the fog device. In other words, the unit of the bid price is the dollar per joule (US$/J). The offloading optimization problem for an end device ui∈U using SPSB is defined as follows [1]:(31)maxEmuibui,subject to(I)
The mechanism isincentive compatible (IC), i.e., the requirement that quj be nondecreasing.(II)
The mechanism isindividual rational (IR), i.e., the requirement that mui0≤0.In the above equation,muibui denotes the expected payoff of the end device ui∈U when it reports buifj to the parent fog device fj, while other buyers tell the truth. Also, quibui denotes the probability that the end device ui∈U gets the resource when reporting its bid value bui.After determining the winning user, whom we denoted byuw, the fog device allocates computing resources to him/her. At this moment, the user state changes from “offload_pending” to “running.” This means that the fog device processes the winning user’s task in a nonpreemptive way until it is completed. Let us denote all users except uw, who are losers in the auction, by e−w. These users may experience one of two situations: (a) the user remains in the same state “offload_pending” to participate in the next round of the auction or (b) the user refuses to offload, in which case, his/her state changes from “offload_pending” to “local_pending.” Thus, if the number of end devices connected to a fog device fj is Nfj, the state of all users at a time t can be represented by a Nfj-size vector St. For example, suppose four users are connected to a fog node and all, but the last one intends to offload. Now, if the third user wins the auction, the system state vector is represented as follows:St=“offload_pending,”“offload_pending,”“running,”“local_pending”. Now, if the capacity of the fog node is still sufficient, users whose state is “offload_pending” can try again to offload their tasks. For example, if at the next time t+1, the second user wins the auction, the state vector changes to St+1=“offload_pending,”“running,”“running,”“local_pending”. As is common in FMDP, at least one of the states must be defined as the terminal state T. For a user ui, if his/her state at the time t, namely sti, belongs to the set T, then its value will not change with any future action. In our problem, the state “running” is terminal, i.e., T=“running”. In other words, if a user’s task is in “running” state (that is sti∈T), it stays in that state until the task is completed.


## 4.3. Action

The action performed by the mobile userui at a time t is denoted by ati∈A. Here, A is a set of all possible actions as follows:(32)A=″local_request″,″offload_request″.The simplest way is to select an action based on a greedy strategy. In this strategy, the action is selected to have the highest value,ati≐argmaxaiQtsti,ai.


## 4.4. Transition Function

It is the probability that an agentui will move from the state sti=s to a new state st+1i=s′ when it acts ati=a. It is denoted by a matrix Ps′,r|s,a, which P:S×A×S⟶0,1 and ∑s′∑rPs′,r|s,a=1.


## 4.5. Reward Function

Depending on what action the agent chooses, it will receive a reward as follows:(33)rt+1i=−pui.Euil,pui.Euil−pui.Euio−buifj.Efjl,0,if st+1i==local_pending,else if st+1i==running,else if st+1i==offloading_pending.As stated in the above relation, if after actingati, the mobile user ui is moved to a new state local_pending, he/she will receive a reward −pui.Euil. Note that the system’s goal here is to minimize the energy consumption of mobile devices. In other words, the proposed algorithm encourages users to offload their tasks to fog devices instead of performing them locally on their own devices. If the user performs the task locally, he/she will receive a penalty pui.Euil. Simply speaking, if the user offloaded the task instead of running it locally, he/she could save pui.Euil dollars by not consuming valuable local resources. The second condition in the above relation states that if the user is moved to a state “running”, he/she will receive a reward pui.Euil−pui.Euio−buifj.Efjl. Here, the first term, pui.Euil, is the amount of money the user has saved by not performing the task locally. Simply put, if the user wanted to run the task locally instead of offloading it, he/she would have to pay pui.Euil dollars for local resource usage. The second term, −pui.Euio, is the amount of money that must be paid to transmit the task to the BS. The third term, −buifj.Efjl, is the amount of money that must be paid to the fog device to perform the task. Note that buifj is the bid price previously offered by the user ui to the fog device fj. As mentioned earlier, in this research we adopt the SPSB auction mechanism proposed by Besharati et al. [1]. When all users submit their bids to the fog device, only one of them who has offered the highest bid (here, the user ui), will win the auction. Then, the winning user ui has to pay buifj dollars for each joule of energy consumption to the fog device. Finally, the last condition in (33) states that if the user is moved to a state “offloading_pending”, he/she will not receive any reward. Although this user tends to offload the task, his/her bid price has not been the highest compared to other competitors. Therefore, the user is temporarily moved to the state “offloading_pending” so that he/she may win the auction in the next time slot.Based on performing a specific action, the agent is transferred from one state to another. The basic form of the Q-learning algorithm for the agentui is sti,ati,rt+1i,st+1i,at+1i, meaning that the agent was in the state sti, performed the action ati, received the reward rt+1i, and finally ended up in the state st+1i, from where it decided to act at+1i. By doing so, it provides a new iteration to update Qsti,ati.The Q-learning algorithm is one of the off-policy RL methods. We adopt the simplest form of it, which is called single-step Q-learning. It is defined as follows:(34)Qsti,ati⟵Qsti,ati+αrt+1i+γmaxbiQst+1i,bi−Qsti,ati.In the above formula,Q and α are the learned action-value function and learning rate, respectively. The α value strikes a balance between the agent’s findings from the environment and what he/she has learned. Also, γ denotes the discount factor, which satisfies 0≤γ≤1. A lower discount factor encourages the agent to take action sooner rather than postponing it indefinitely. In other words, it determines how much importance should be given to immediate rewards and future rewards. This helps us to avoid infinity as a reward. A value of γ=0 means that more priority is given to immediate rewards, and a value of γ=1 means that more importance is given to future rewards. In practice, the discount factor γ=0 is never learned because it only considers immediate rewards, and the discount factor γ=1 continues for future rewards, which may lead to infinity. Therefore, the optimal value for the discount factor, γ, is in the range (0, 1).After determining the transition functionP and the received reward rt+1i by the parent node (controller), the MDP problem can be easily solved using dynamic programming algorithms. Here, the core idea is to use the value function Vs to find the optimal action a∗i. The optimal action in any state sti is the action that brings the most reward to the agent. For this purpose, the state value function must be expressed in the following form, which is known as the Bellman equation:(35)V∗s=maxErt+1i+γ.V∗st+1i|sti=s,ati=a.The above formula after simplification can be rewritten as follows:(36)V∗s=maxa∑s′,rPs′,r|s,ar+γ.V∗s′.One of the most common ways to solve the Bellman equation is to rewrite it in the following recursive form:(37)Vt+1s=maxa∑s′,rPs′,r|s,ar+γ.Vts′.Thus, the value of all states can be obtained. Given that0≤γ≤1, it can be proved that the Bellman equation will converge and, therefore, the solution is as follows:(38)V∗s=limt⟶∞Vts.The key advantage of Q-learning over other RL methods is that it converges very quickly. The main reason is thatQ can directly approximate the optimal action-value function, q∗. Here, the policy serves to determine which state-action pairs to be visited and updated. Like most RL methods, the prerequisite for convergence here is that all pairs continue to be updated. Under this assumption and other common indefinite approximation conditions in the sequence of size-step parameters, it is found that Q converges with a probability of 1 to q∗. Another advantage of Q-learning is that it does not require a specific model of the environment. In RL terminology, it is a model-free method and does not require a predetermined policy to find any optimal state-action pair.Note that the Q-learning algorithm is executed both in the fog layer and in the cloud layer. Due to space limitations and the similarity of pseudocodes, we only show the offloading operation in the fog layer. The pseudocode of the Q-learning for the offloading problem is shown in Algorithm1. Also, Algorithms 2 and 3 represent the pseudocode of the mobile user ui and the fog device fj (controller), respectively. Algorithm 3 itself calls Algorithm 4 to calculate the bid price per joule of energy consumption based on the second-price sealed-bid (SPSB) mechanism [1]. Let us now give a brief description of these algorithms. In lines 5–8 of Algorithm 2, if the energy consumption is within the allowable range and does not exceed the remaining energy of the mobile device, the task is performed locally. In this case, the state of the task, sti, is changed to “local_execution” and then the user adds the revenue from the local energy consumption, pui.Euil, to his/her current budget. In lines 10–12 of Algorithm 2, because the energy consumption has exceeded the residual energy of the mobile device, the task is offloaded to the fog device by calling Algorithm 3. In this case, the costs of offloading, pui.Euio, and remote processing, buifj.Efjl, are deducted from the mobile user’s budget. Similarly, in lines 7–14 of Algorithm 3, if the task energy consumption exceeds the remaining energy of the fog device, it is offloaded to the remote cloud. In this case, in addition to the cost of offloading, pui.Euio, and processing in the fog device buifj.Efjl, the cost of offloading to the remote cloud, pfj.Efjo, must also be deducted from the user’s budget. Otherwise, if the user’s budget is sufficient to process the task on the fog device, the task state is changed to “offload_pending”; otherwise, it must be processed locally on the mobile device itself. In lines 15–17 of Algorithm 3, a second-price sealed-bid (SPSB) auction mechanism is held by calling Algorithm 4. Readers interested in a detailed study of Algorithm 4 can refer to [1]. Finally, after determining the auction winner, the task state for the user who won the auction is changed to “running”. Then, in line 18 of Algorithm 3, the optimal action-value function vector Q∗ is found by calling Algorithm 1. This vector specifies exactly on which device each task should be performed. The task must be performed locally on the user’s device, the fog device, or the remote cloud. Here, an important question arises regarding Algorithm 4: if the bid value of two nodes is the same, which one will have more priority? According to the implementation in [1], in such a case, the node whose remaining buffer capacity and the remaining energy are less has a higher priority.


## 5. Performance Evaluation

In this section, after explaining the simulation settings, we will compare the proposed method with one of the state-of-the-art methods [1]. This comparison is made in terms of important criteria such as execution time, power consumption, and network usage.


### 5.1. Experimental Setting

The iFogSim software has been used for simulation [50]. Also, statistical analysis of the simulation results was performed using SPSS software. The results were obtained on a laptop with a 64-bit Intel® Core™ i5-8269U processor, 6 MB Cache, 4 Cores, 4.20 GHz CPU, and 8 GB of RAM. As with other research [1], a three-tier hierarchical tree structure has been used for the simulation, which includes the central cloud layer, the fog device layer, such as routers and switches, and the end device layer.Algorithm 1: Pseudocode of the Q-learning for the offloading problem.
Input: The fog node identifier fj, the set of states S, the set of actions A, the set of terminal states TOutput: the optimal action-value function vector Q∗(1)
Sett=0(2)
fori∈Cfjdo(3)
forsti∈Sdo(4)
forati∈Ado(5)
InitializeQsti,ati arbitrarily(6)
Initialize terminal state value,QTi,.=0(7)
end for(8)
end for(9)
end for(10)
repeat(11)
InitializeSt(12)
repeat (for each step of the episode)(13)
ChooseAt from St using policy derived from Qt (e.g., ℇ-greedy)(14)
Take actionAt, observe Rt+1, St+1(15)
QSt,At⟵QSt,At+αRt+1+γmaxBQSt+1,B−QSt,At using equation (33)(16)
St⟵St+1(17)
untilSt∈T(18)
t⟵t+1(19)
untilMax_Num_Episodes(20)
Q∗⟵QSt,At using equation (37)(21)
returnQ∗Algorithm 2: Pseudocode of a mobile user ui in the proposed offloading method.
Input: The arrival rate of tasks λui, the task size of the mobile user θi, the number of CPU cycles required to perform each bit of the task in the mobile user σi, computing capacity in mobile user Cui, the uplink rate at which tasks are offloaded Ri, the gain of the channel located between the mobile user ui and the BS hi, the channel bandwidth W, the noise of the channel N0, power required to execute a task locally Puil, the maximum transmission power of the mobile user Pimax, price per joule of energy to be paid by the mobile user pujOutput: local energy consumption Euil, the offloading energy consumption Euio(1)
Calculate the response time of the task in local execution,tuil, using equation (10)(2)
Calculate the offloading time of the task,tuio, using equation (13)(3)
Calculate the local energy consumption,Euil, using equation (11)(4)
Calculate the offloading energy consumption,Euio, using equation (14)(5)
if (Euil≤Euirem and Euirem≥Euithr) then(6)
sti⟵“local_execution”(7)
Perform the task locally(8)
budgetui=budgetui+pui.Euil(9)
else(10)
Sendpui, Euil and Euio to the fog device fj (controller) by calling Algorithm 3(11)
budgetui=budgetui−pui.Euio−buifj.Efjl(12)
end ifAlgorithm 3: Pseudocode of a fog device fj (controller) in the proposed offloading method.
Input: The arrival rate of tasks in the fog node λfj, the task size of the mobile user θi, the number of CPU cycles required to perform each bit of the task in the mobile user σi, computing capacity in the fog device Cfj, the power required to execute a task at the fog device Pfjl, price per joule of energy to be paid by the mobile user pujOutput: the optimal action-value function vector Q∗(1)
Calculate the response time of the task when it is executed by the fog device,tfjl, using equation (26)(2)
Calculate the offloading time of the task towards the central cloud,tfjo, using equation (28)(3)
Calculate the local energy consumption,Efjl, using equation (27)(4)
Calculate the offloading energy consumption towards the central cloud,Efjo, using equation (29)(5)
Call Algorithm1 to get the optimal action-value function vector Q∗(6)
Update computing capacity in the fog deviceCfj(7)
if (Efjl>Efjrem or Efjrem<EfjThr) then(8)
Sendpfj, tfjl, and tfjo to the remote cloud(9)
budgetui=budgetui−pui.Euio−buifj.Efjl−pfj.Efjo(10)
else if (pfj.Efjl≤budgetui) then(11)
sti⟵“offload_pending”(12)
else(13)
sti⟵“local_execution”(14)
end if(15)
call Algorithm4 to hold the second-price sealed-bid (SPSB) auction(16)
w⟵the identifier of the node who is the winner of the auction(17)
stw⟵“running”(18)
call Algorithm1 to calculate the optimal action-value function vector Q∗Algorithm 4: Pseudocode of the Second-price Sealed-bid (SPSB) auction [1].
Input: The identifier of the buyer ui (bidder node), the bidding distribution function FuiOutput: the identifier of the node who is the winner of the auction w, the bidding value which must be paid by the winner to the fog device fj for each Joules of energy consumption bwfj(1)
Wait to receive the bidding valuexui from all mobile users ui(2)
buifj⟵Maximum bidding value(3)
w⟵the identifier of the node who is the winner of the auction(4)
Introduce the winnerw to other bidder nodes(5)
Delete the nodew from the set of future bidders(6)
Returnw and bwfjAs mentioned earlier, this study adopts the second-price sealed-bid (SPSB) auction mechanism proposed in [1] to determine the price of computational resources concerning parent-child nodes. Accordingly, in the diagrams in this section, we abbreviate the baseline method of [1] to SPSB_Auction. We also abbreviate our proposed method to SPSB_Auction_RL. Note that there is no learning mechanism in SPSB_Auction [1], and the only contribution is the auction-based pricing method. However, SPSB_Auction_RL uses a dynamic approach based on RL. We also compare our results with the default offloading mechanism used in the iFogSim, i.e., First-Come-First-Serve (FCFS). This method asks the corresponding parent node to perform the offloading operation when a node’s queue becomes full.For the sake of simplicity, we ignore interdependencies between tasks. In other words, each task is independent of its previous and subsequent tasks. Although this assumption is not always correct, it still makes sense in many web applications. The time between the arrival of tasks in the iFogSim simulator follows an exponential distribution in which the arrival rate,λui, is 50 tasks per minute. The buffer size of each fog device is 20. For fairness, we adopt the settings used by [1] on iFogSim. Table 3 shows the details of the simulation settings. Since some parameters of iFogSim follow probabilistic distributions, we performed each test 40 times. Then, average values were used to draw the curves.Table 3
The simulation settings.
ModuleCPU computing capacity (MIPS)RAM (MB)UP bandwidth (kbps)Down bandwidth (kbps)Cloud44800400001000010000Gateway (fog)280040001000010000End device3200100010000270


### 5.2. Execution Time

Figure4 shows a comparison of runtime for different numbers of fog nodes. Like most previous research [51, 52], we consider the number of fog nodes almost small. This is because a typical fog device does not have as much computing power as a central cloud. As shown in the figure, the average execution time of all methods increases as the number of nodes increases. However, it shows much less growth for SPSB Auction_RL. From a practical point of view, the proposed method offers an attractive implication for scalability for network designers.Figure 4
Execution time for different numbers of fog nodes.An interesting point in Figure4 is the dramatic increase in response time in the SPSB-Auction method (green curve). To explain this, note that the response time consists of two parts: (1) first, it takes time for the nodes to submit their bidding values; (2) after the auction winner is determined, resources are allocated based on the announced price. This is the time that was previously calculated in (15) and (28). In the SPSB-Auction method (green curve), the bidding price is proportional to the number of buffer rooms and the remaining energy of the nodes [1]. As time passes, the nodes experience a lack of buffer and energy. This makes them less likely to win the auction. In other words, when resources are more utilized, the time required to determine the winning node becomes longer. The advantage of the proposed method (blue curve) appears exactly here. Here, better allocation of resources by leveraging RL leads to more equitable distribution of resources. This, in turn, causes the nodes to experience less buffer and energy shortages. Nodes whose buffer is empty or having more remaining energy do not need to offload tasks. Thus, they do not participate in auction operations. By reducing the number of nodes participating in the auction, the time required to announce the winner is reduced dramatically.We use the Analysis of Variance (ANOVA) test to compare the average execution time of the three methodsFCFS, SPSB_Auction, and SPSB_Auction_RL. The ANOVA test compares the mean of a quantitative variable between more than two independent groups. This test is a generalized T-test between two independent samples with the same assumptions. Readers interested in studying more about these statistical tests can refer to [15, 53, 54]. The ANOVA test hypotheses are introduced as follows:(H0)
The average execution time of all methods is the same.(H1)
There is at least one method whose average execution time differs from others.Given that the confidence interval is assumed to be 95% by default, the threshold value for accepting/rejecting the comparison results, called the Sig value, is 0.05. Table4 shows the within-group and between-group values obtained from the ANOVA test regarding the execution time. As seen from the table, since Sig = 0.033 < 0.05, the assumption H0 is rejected. This means that the three methods under study have different average execution times. In Table 4, field F shows the amount of between-groups changes compared to within-group changes. To obtain the F-value for each group, the sum of the squares of the difference of its data concerning the mean is calculated. The larger F is, the higher the probability of rejecting hypothesis H0. On the contrary, a small value of F indicates the nonsignificance of the difference between the groups. In the ANOVA test, the df field indicates the degree of freedom. Statistically, the degree of freedom is the sample size minus the number of parameters estimated from the data.Table 4
Intragroup and intergroup values obtained from the ANOVA test regarding the execution time.
ANOVAExecution timeSum of squaresdfMean squareFSigBetween groups405683979302.6062202841989651.3033.8420.033Within groups1583952298280.723052798409942.691Total1989636277583.3332The pairwise comparison of runtime values for different methods obtained from the ANOVA test is shown in Table5. As seen from the table, the execution time of the SPSB_Auction method is different from the other two methods and has a significant difference. In other words, the SPSB_Auction method has a longer execution delay than others. For the sake of simplicity of comparison, the average execution time of different methods is shown in Figure 5. Again, in this figure, it is clear that the execution time of the SPSB_Auction method is significantly different from other methods.Table 5
Pairwise comparison of runtime values for different methods obtained from the ANOVA test.
Multiple comparisonsDependent variable: execution timeLSD(I) Approach(J) ApproachMean difference (I − J)Std. errorSig95% confidence intervalLower boundUpper boundSPSB Auction_RLSPSB auction−240349.36364∗97978.110.020−440447.3680−40251.3593FCFS−10654.4545597978.110.914−210752.4589189443.5498SPSB auctionSPSB Auction_RL240349.36364∗97978.110.02040251.3593440447.3680FCFS229694.90909∗97978.110.02629596.9048429792.9134FCFSSPSB Auction_RL10654.4545597978.110.914−189443.5498210752.4589SPSB auction−229694.90909∗97978.110.026−429792.9134−29596.9048∗The mean difference is significant at the 0.05 level.Figure 5
The average execution time for different approaches.We use theMann‒Whitney U test to check the correlation between the execution times of the SPSB_Auction and SPSB_Auction_RL methods. Unlike the T-test, here, the sum of the scores is used instead of the mean. For this purpose, the samples are first merged and assigned ranks. The allocated sums are then calculated in each method separately. The total number of data points is 22, half belonging to the SPSB_Auction_RL method and the rest to the SPSB_Auction. First, the 22 data points are sorted in ascending order, and then they receive the smallest rank number 1, and the highest rank number 22. The result of the Mann‒Whitney U test for execution time is shown in Table 6. As can be seen in the table, the “Sum of Ranks” values for the SPSB_Auction_RL and SPSB_Auction methods are 97 and 156, respectively. Since the “Sum of Ranks” in the SPSB_Auction_RL method is less than that of the SPSB_Auction method, its execution time is less than the SPSB_Auction method.Table 6
Ranks assigned to each method in the Mann‒WhitneyU test.
RanksApproachNMean rankSum of ranksExecution timeSPSB Auction_RL118.8297.00SPSB auction1114.18156.00Total22The Mann‒Whitney U value,UMW, for each dataset is calculated as follows [1]:(39)UMW=Srank−NN+12,where N and Srank denote the number of data points in each dataset and the sum of ranks, respectively. According to (39), the Mann‒Whitney U values for the SPSB_Auction_RL and SPSB_Auction methods are 97–11 ∗ 12/2 = 31 and 156–11 ∗ 12/2 = 90, respectively. Figure 6 shows the largest value, 90, which corresponds to the value of Wilcoxon W = 156 for the SPSB_Auction method.Figure 6
Execution time analysis information of different methods in the Mann‒WhitneyU test.Figure6 presents an interesting implication for the “risk aversion” property [55] of SPSB_Auction_RL and SPSB_Auction methods. Based on this property, the bid values announced by mobile users do not differ significantly from each other. This leads to the fact that the execution times of these two methods are slightly different from each other. The hypotheses used are as follows:H0: the selected offloading approach has a significant effect on the execution time.H1: the selected offloading approach has little impact on the execution time.Hypothesis acceptance in the Mann‒WhitneyU test is based on the asymptotic Sig and Mann‒Whitney U value. As shown in Figure 6, we have the asymptotic Sig = 0.053> α = 0.05 and Mann‒Whitney U = 90. Therefore, the hypothesis H0 is not rejected.


### 5.3. Energy Consumption

Figure7 shows the energy consumption of the entire system, which includes the total energy consumed in local execution (11) and (27) and offloading (14) and (29) in all layers. As shown in the figure, the amount of energy consumption in all methods increases with an increase in the number of fog nodes. However, the proposed method, SPSB_Auction_RL, manages to consume less energy than others. Due to space limitations, the results of the ANOVA test have been omitted.Figure 7
Energy consumption for different numbers of fog nodes.For the sake of simplicity of comparison, the average energy consumption of different methods, as well as their variance, is shown in Figures8 and 9. Again, in these figures, it is clear that the energy consumption of the SPSB_Auction_RL method is significantly different from other methods. Also, Figure 9 can provide an interesting implication for the stability of the proposed method. As is evident in the figure, the variance of energy consumption in the SPSB_Auction_RL method is less than others. This indicates that it has acceptable stability concerning selected hyperparameters, α and γ, in (34).Figure 8
The average energy consumption for different approaches.Figure 9
The variance of the energy consumption for different approaches.


### 5.4. Network Usage

Figure10 shows the network usage for different numbers of fog nodes. This is one of the criteria for which the iFogSim simulator generates reports. The network usage criterion is the number of bits transmitted to offload all tasks in the network. As can be seen from the figure, network usage increases as the number of fog nodes increases. However, the network usage in the SPSB_Auction and SPSB_Auction_RL methods is significantly less than that of the FCFS. Also, note that SPSB_Auction and SPSB_Auction_RL methods, themselves, have very little difference in terms of network usage.Figure 10
Network usage for different numbers of fog nodes.Also, the average network usage of different methods is shown in Figure11. Again, in this figure, it is clear that the energy consumption of the FCFS method is significantly different from other methods.Figure 11
The average network usage for different approaches.


## 5.1. Experimental Setting

The iFogSim software has been used for simulation [50]. Also, statistical analysis of the simulation results was performed using SPSS software. The results were obtained on a laptop with a 64-bit Intel® Core™ i5-8269U processor, 6 MB Cache, 4 Cores, 4.20 GHz CPU, and 8 GB of RAM. As with other research [1], a three-tier hierarchical tree structure has been used for the simulation, which includes the central cloud layer, the fog device layer, such as routers and switches, and the end device layer.Algorithm 1: Pseudocode of the Q-learning for the offloading problem.
Input: The fog node identifier fj, the set of states S, the set of actions A, the set of terminal states TOutput: the optimal action-value function vector Q∗(1)
Sett=0(2)
fori∈Cfjdo(3)
forsti∈Sdo(4)
forati∈Ado(5)
InitializeQsti,ati arbitrarily(6)
Initialize terminal state value,QTi,.=0(7)
end for(8)
end for(9)
end for(10)
repeat(11)
InitializeSt(12)
repeat (for each step of the episode)(13)
ChooseAt from St using policy derived from Qt (e.g., ℇ-greedy)(14)
Take actionAt, observe Rt+1, St+1(15)
QSt,At⟵QSt,At+αRt+1+γmaxBQSt+1,B−QSt,At using equation (33)(16)
St⟵St+1(17)
untilSt∈T(18)
t⟵t+1(19)
untilMax_Num_Episodes(20)
Q∗⟵QSt,At using equation (37)(21)
returnQ∗Algorithm 2: Pseudocode of a mobile user ui in the proposed offloading method.
Input: The arrival rate of tasks λui, the task size of the mobile user θi, the number of CPU cycles required to perform each bit of the task in the mobile user σi, computing capacity in mobile user Cui, the uplink rate at which tasks are offloaded Ri, the gain of the channel located between the mobile user ui and the BS hi, the channel bandwidth W, the noise of the channel N0, power required to execute a task locally Puil, the maximum transmission power of the mobile user Pimax, price per joule of energy to be paid by the mobile user pujOutput: local energy consumption Euil, the offloading energy consumption Euio(1)
Calculate the response time of the task in local execution,tuil, using equation (10)(2)
Calculate the offloading time of the task,tuio, using equation (13)(3)
Calculate the local energy consumption,Euil, using equation (11)(4)
Calculate the offloading energy consumption,Euio, using equation (14)(5)
if (Euil≤Euirem and Euirem≥Euithr) then(6)
sti⟵“local_execution”(7)
Perform the task locally(8)
budgetui=budgetui+pui.Euil(9)
else(10)
Sendpui, Euil and Euio to the fog device fj (controller) by calling Algorithm 3(11)
budgetui=budgetui−pui.Euio−buifj.Efjl(12)
end ifAlgorithm 3: Pseudocode of a fog device fj (controller) in the proposed offloading method.
Input: The arrival rate of tasks in the fog node λfj, the task size of the mobile user θi, the number of CPU cycles required to perform each bit of the task in the mobile user σi, computing capacity in the fog device Cfj, the power required to execute a task at the fog device Pfjl, price per joule of energy to be paid by the mobile user pujOutput: the optimal action-value function vector Q∗(1)
Calculate the response time of the task when it is executed by the fog device,tfjl, using equation (26)(2)
Calculate the offloading time of the task towards the central cloud,tfjo, using equation (28)(3)
Calculate the local energy consumption,Efjl, using equation (27)(4)
Calculate the offloading energy consumption towards the central cloud,Efjo, using equation (29)(5)
Call Algorithm1 to get the optimal action-value function vector Q∗(6)
Update computing capacity in the fog deviceCfj(7)
if (Efjl>Efjrem or Efjrem<EfjThr) then(8)
Sendpfj, tfjl, and tfjo to the remote cloud(9)
budgetui=budgetui−pui.Euio−buifj.Efjl−pfj.Efjo(10)
else if (pfj.Efjl≤budgetui) then(11)
sti⟵“offload_pending”(12)
else(13)
sti⟵“local_execution”(14)
end if(15)
call Algorithm4 to hold the second-price sealed-bid (SPSB) auction(16)
w⟵the identifier of the node who is the winner of the auction(17)
stw⟵“running”(18)
call Algorithm1 to calculate the optimal action-value function vector Q∗Algorithm 4: Pseudocode of the Second-price Sealed-bid (SPSB) auction [1].
Input: The identifier of the buyer ui (bidder node), the bidding distribution function FuiOutput: the identifier of the node who is the winner of the auction w, the bidding value which must be paid by the winner to the fog device fj for each Joules of energy consumption bwfj(1)
Wait to receive the bidding valuexui from all mobile users ui(2)
buifj⟵Maximum bidding value(3)
w⟵the identifier of the node who is the winner of the auction(4)
Introduce the winnerw to other bidder nodes(5)
Delete the nodew from the set of future bidders(6)
Returnw and bwfjAs mentioned earlier, this study adopts the second-price sealed-bid (SPSB) auction mechanism proposed in [1] to determine the price of computational resources concerning parent-child nodes. Accordingly, in the diagrams in this section, we abbreviate the baseline method of [1] to SPSB_Auction. We also abbreviate our proposed method to SPSB_Auction_RL. Note that there is no learning mechanism in SPSB_Auction [1], and the only contribution is the auction-based pricing method. However, SPSB_Auction_RL uses a dynamic approach based on RL. We also compare our results with the default offloading mechanism used in the iFogSim, i.e., First-Come-First-Serve (FCFS). This method asks the corresponding parent node to perform the offloading operation when a node’s queue becomes full.For the sake of simplicity, we ignore interdependencies between tasks. In other words, each task is independent of its previous and subsequent tasks. Although this assumption is not always correct, it still makes sense in many web applications. The time between the arrival of tasks in the iFogSim simulator follows an exponential distribution in which the arrival rate,λui, is 50 tasks per minute. The buffer size of each fog device is 20. For fairness, we adopt the settings used by [1] on iFogSim. Table 3 shows the details of the simulation settings. Since some parameters of iFogSim follow probabilistic distributions, we performed each test 40 times. Then, average values were used to draw the curves.Table 3
The simulation settings.
ModuleCPU computing capacity (MIPS)RAM (MB)UP bandwidth (kbps)Down bandwidth (kbps)Cloud44800400001000010000Gateway (fog)280040001000010000End device3200100010000270


## 5.2. Execution Time

Figure4 shows a comparison of runtime for different numbers of fog nodes. Like most previous research [51, 52], we consider the number of fog nodes almost small. This is because a typical fog device does not have as much computing power as a central cloud. As shown in the figure, the average execution time of all methods increases as the number of nodes increases. However, it shows much less growth for SPSB Auction_RL. From a practical point of view, the proposed method offers an attractive implication for scalability for network designers.Figure 4
Execution time for different numbers of fog nodes.An interesting point in Figure4 is the dramatic increase in response time in the SPSB-Auction method (green curve). To explain this, note that the response time consists of two parts: (1) first, it takes time for the nodes to submit their bidding values; (2) after the auction winner is determined, resources are allocated based on the announced price. This is the time that was previously calculated in (15) and (28). In the SPSB-Auction method (green curve), the bidding price is proportional to the number of buffer rooms and the remaining energy of the nodes [1]. As time passes, the nodes experience a lack of buffer and energy. This makes them less likely to win the auction. In other words, when resources are more utilized, the time required to determine the winning node becomes longer. The advantage of the proposed method (blue curve) appears exactly here. Here, better allocation of resources by leveraging RL leads to more equitable distribution of resources. This, in turn, causes the nodes to experience less buffer and energy shortages. Nodes whose buffer is empty or having more remaining energy do not need to offload tasks. Thus, they do not participate in auction operations. By reducing the number of nodes participating in the auction, the time required to announce the winner is reduced dramatically.We use the Analysis of Variance (ANOVA) test to compare the average execution time of the three methodsFCFS, SPSB_Auction, and SPSB_Auction_RL. The ANOVA test compares the mean of a quantitative variable between more than two independent groups. This test is a generalized T-test between two independent samples with the same assumptions. Readers interested in studying more about these statistical tests can refer to [15, 53, 54]. The ANOVA test hypotheses are introduced as follows:(H0)
The average execution time of all methods is the same.(H1)
There is at least one method whose average execution time differs from others.Given that the confidence interval is assumed to be 95% by default, the threshold value for accepting/rejecting the comparison results, called the Sig value, is 0.05. Table4 shows the within-group and between-group values obtained from the ANOVA test regarding the execution time. As seen from the table, since Sig = 0.033 < 0.05, the assumption H0 is rejected. This means that the three methods under study have different average execution times. In Table 4, field F shows the amount of between-groups changes compared to within-group changes. To obtain the F-value for each group, the sum of the squares of the difference of its data concerning the mean is calculated. The larger F is, the higher the probability of rejecting hypothesis H0. On the contrary, a small value of F indicates the nonsignificance of the difference between the groups. In the ANOVA test, the df field indicates the degree of freedom. Statistically, the degree of freedom is the sample size minus the number of parameters estimated from the data.Table 4
Intragroup and intergroup values obtained from the ANOVA test regarding the execution time.
ANOVAExecution timeSum of squaresdfMean squareFSigBetween groups405683979302.6062202841989651.3033.8420.033Within groups1583952298280.723052798409942.691Total1989636277583.3332The pairwise comparison of runtime values for different methods obtained from the ANOVA test is shown in Table5. As seen from the table, the execution time of the SPSB_Auction method is different from the other two methods and has a significant difference. In other words, the SPSB_Auction method has a longer execution delay than others. For the sake of simplicity of comparison, the average execution time of different methods is shown in Figure 5. Again, in this figure, it is clear that the execution time of the SPSB_Auction method is significantly different from other methods.Table 5
Pairwise comparison of runtime values for different methods obtained from the ANOVA test.
Multiple comparisonsDependent variable: execution timeLSD(I) Approach(J) ApproachMean difference (I − J)Std. errorSig95% confidence intervalLower boundUpper boundSPSB Auction_RLSPSB auction−240349.36364∗97978.110.020−440447.3680−40251.3593FCFS−10654.4545597978.110.914−210752.4589189443.5498SPSB auctionSPSB Auction_RL240349.36364∗97978.110.02040251.3593440447.3680FCFS229694.90909∗97978.110.02629596.9048429792.9134FCFSSPSB Auction_RL10654.4545597978.110.914−189443.5498210752.4589SPSB auction−229694.90909∗97978.110.026−429792.9134−29596.9048∗The mean difference is significant at the 0.05 level.Figure 5
The average execution time for different approaches.We use theMann‒Whitney U test to check the correlation between the execution times of the SPSB_Auction and SPSB_Auction_RL methods. Unlike the T-test, here, the sum of the scores is used instead of the mean. For this purpose, the samples are first merged and assigned ranks. The allocated sums are then calculated in each method separately. The total number of data points is 22, half belonging to the SPSB_Auction_RL method and the rest to the SPSB_Auction. First, the 22 data points are sorted in ascending order, and then they receive the smallest rank number 1, and the highest rank number 22. The result of the Mann‒Whitney U test for execution time is shown in Table 6. As can be seen in the table, the “Sum of Ranks” values for the SPSB_Auction_RL and SPSB_Auction methods are 97 and 156, respectively. Since the “Sum of Ranks” in the SPSB_Auction_RL method is less than that of the SPSB_Auction method, its execution time is less than the SPSB_Auction method.Table 6
Ranks assigned to each method in the Mann‒WhitneyU test.
RanksApproachNMean rankSum of ranksExecution timeSPSB Auction_RL118.8297.00SPSB auction1114.18156.00Total22The Mann‒Whitney U value,UMW, for each dataset is calculated as follows [1]:(39)UMW=Srank−NN+12,where N and Srank denote the number of data points in each dataset and the sum of ranks, respectively. According to (39), the Mann‒Whitney U values for the SPSB_Auction_RL and SPSB_Auction methods are 97–11 ∗ 12/2 = 31 and 156–11 ∗ 12/2 = 90, respectively. Figure 6 shows the largest value, 90, which corresponds to the value of Wilcoxon W = 156 for the SPSB_Auction method.Figure 6
Execution time analysis information of different methods in the Mann‒WhitneyU test.Figure6 presents an interesting implication for the “risk aversion” property [55] of SPSB_Auction_RL and SPSB_Auction methods. Based on this property, the bid values announced by mobile users do not differ significantly from each other. This leads to the fact that the execution times of these two methods are slightly different from each other. The hypotheses used are as follows:H0: the selected offloading approach has a significant effect on the execution time.H1: the selected offloading approach has little impact on the execution time.Hypothesis acceptance in the Mann‒WhitneyU test is based on the asymptotic Sig and Mann‒Whitney U value. As shown in Figure 6, we have the asymptotic Sig = 0.053> α = 0.05 and Mann‒Whitney U = 90. Therefore, the hypothesis H0 is not rejected.


## 5.3. Energy Consumption

Figure7 shows the energy consumption of the entire system, which includes the total energy consumed in local execution (11) and (27) and offloading (14) and (29) in all layers. As shown in the figure, the amount of energy consumption in all methods increases with an increase in the number of fog nodes. However, the proposed method, SPSB_Auction_RL, manages to consume less energy than others. Due to space limitations, the results of the ANOVA test have been omitted.Figure 7
Energy consumption for different numbers of fog nodes.For the sake of simplicity of comparison, the average energy consumption of different methods, as well as their variance, is shown in Figures8 and 9. Again, in these figures, it is clear that the energy consumption of the SPSB_Auction_RL method is significantly different from other methods. Also, Figure 9 can provide an interesting implication for the stability of the proposed method. As is evident in the figure, the variance of energy consumption in the SPSB_Auction_RL method is less than others. This indicates that it has acceptable stability concerning selected hyperparameters, α and γ, in (34).Figure 8
The average energy consumption for different approaches.Figure 9
The variance of the energy consumption for different approaches.


## 5.4. Network Usage

Figure10 shows the network usage for different numbers of fog nodes. This is one of the criteria for which the iFogSim simulator generates reports. The network usage criterion is the number of bits transmitted to offload all tasks in the network. As can be seen from the figure, network usage increases as the number of fog nodes increases. However, the network usage in the SPSB_Auction and SPSB_Auction_RL methods is significantly less than that of the FCFS. Also, note that SPSB_Auction and SPSB_Auction_RL methods, themselves, have very little difference in terms of network usage.Figure 10
Network usage for different numbers of fog nodes.Also, the average network usage of different methods is shown in Figure11. Again, in this figure, it is clear that the energy consumption of the FCFS method is significantly different from other methods.Figure 11
The average network usage for different approaches.


## 6. Conclusion and Future Trends

This paper used reinforcement learning to optimize bid value prediction in auction-based offloading. In our proposed mechanism, nodes participating in the auction report their bid values to their corresponding parent nodes. The node with the highest bid wins the auction and offloads its tasks to the parent node. After discussing the strengths and weaknesses of previous research, we modeled the problem by queuing theory. In this model, the response time and energy consumption of mobile users’ tasks were formulated in all three layers edge, fog, and cloud. Then, using the Q-learning method, a price-based mechanism was designed to encourage users to offload their tasks so that the energy consumed by the final devices is minimized.The performance of the proposed method was evaluated against one of the state-of-the-art methods, in which only the second-price sealed-bid auction mechanism is used for offloading. The simulation results showed that the proposed method significantly reduces task execution time compared to the baseline and the FCFS methods. The average energy consumption of the proposed method is lower than other methods. However, the FCFS and the baseline methods have almost equal energy consumption. In addition, the lower energy consumption variance makes it more stable than other methods. Unlike the FCFS method, both the proposed and baseline methods save the network resources significantly.One future research trend is considering users’ mobility and hand-off. Also, using other RL methods in combination with metaheuristic methods can probably remarkably reduce learning time.



---

*Source: 5222504-2023-01-17.xml*