# Dynamic Resource Allocation for Load Balancing in Fog Environment

Authors: Xiaolong Xu; Shucun Fu; Qing Cai; Wei Tian; Wenjie Liu; Wanchun Dou; Xingming Sun; Alex X. Liu
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

Fog computing is emerging as a powerful and popular computing paradigm to perform IoT (Internet of Things) applications, which is an extension to the cloud computing paradigm to make it possible to execute the IoT applications in the network of edge. The IoT applications could choose fog or cloud computing nodes for responding to the resource requirements, and load balancing is one of the key factors to achieve resource efficiency and avoid bottlenecks, overload, and low load. However, it is still a challenge to realize the load balance for the computing nodes in the fog environment during the execution of IoT applications. In view of this challenge, a dynamic resource allocation method, named DRAM, for load balancing in fog environment is proposed in this paper. Technically, a system framework for fog computing and the load-balance analysis for various types of computing nodes are presented first. Then, a corresponding resource allocation method in the fog environment is designed through static resource allocation and dynamic service migration to achieve the load balance for the fog computing systems. Experimental evaluation and comparison analysis are conducted to validate the efficiency and effectiveness of DRAM.


---

## Body

## 1. Introduction

In recent years, the Internet of Things (IoT) has attracted attention from both industry and academia, which is beneficial to humans’ daily lives. The data extracted from the smart sensors are often transmitted to the cloud data centers and the applications are generally executed by the processors in the data centers [1]. The cloud computing paradigm is efficient in provisioning computation and storage resources for the IoT applications, but the ever-increasing amount of resource requirements of the IoT applications leads to the explosively increased energy consumption and the performance degradation of the computing nodes due to data transmission and computing node migration; thus, how to perform IoT applications becomes an urgent issue [2–6]. Fog computing extends the computing process to the edge of the network rather than performing the IoT applications in the cloud platforms.In the fog environment, the routers are the potential physical servers which could provision resources for the fog services at the edge of the network [7, 8]. The routers could enhance the performance of computation and storage, which could be fully utilized as the computing nodes. In the big data era, there are different performance requirements for the IoT applications, especially for the real-time applications; thus, such applications choose the edge computing nodes as a priority to host [9, 10]. In the fog environment, the users could access and utilize the computation, storage, and network resources, like the way the customers use the cloud resources, and the virtualized technology is also applicative to provision the on-demand resources dynamically [11]. The IoT applications could be performed by the fog computing nodes and the physical resources deployed in the remote cloud data center. The resource allocation for the IoT applications should take into account both the centralized and the geodistributed computing nodes, and the resource schedulers and managers should choose the appropriate computing nodes to host the fog services combined in the IoT applications through the design of resource allocation strategies.Resource allocation and resource scheduling are the key technologies to manage the data centers, which contribute a great deal to lowering the carbon emission, improving the resource utilization, and obtaining load balancing for the data centers [12–14]. In the cloud environment, the main goal of resource allocation is to optimize the number of active physical machines (PMs) and make the workloads of the running PMs distributed in a balanced manner, to avoid bottlenecks and overloaded or low-loaded resource usage [14–17]. In the fog environment, resource allocation becomes more complicated since the applications could be responded to by the computing nodes both in fog and in clouds. The computing nodes in the fog are distributed dispersedly in the network of edge, while the computing nodes in the cloud are distributed in a centralized data center. The resource requirements of the IoT applications for the computing nodes are various as the applications have different demands of computing power, storage capacity, and bandwidth. Therefore, it is necessary to undergo resource allocation for the dynamic resource requirements of the IoT applications, to achieve the goal of load balancing.With the above observations, it is still a challenge to realize the load balance for the computing nodes in the fog environment during the execution of IoT applications. In view of this challenge, a dynamic resource allocation method, named DRAM, for load balancing in fog environment is proposed in this paper. Specifically, our main contributions are threefold. Firstly, we present a system framework for IoT applications in fog environment and conduct the load-balance analysis for various types of computing nodes. Then, a corresponding resource allocation method in the fog environment is designed through static resource allocation and dynamic service migration to achieve the load balance for the fog computing systems. Finally, adequate experimental analysis is conducted to verify the performance of our proposed method.The rest of this paper is organized as follows. In Section2, formalized concepts and definitions are presented for load-balance analysis in the fog environment. Section 3 elaborates the proposed resource allocation method DRAM. Section 4 illustrates the comparison analysis and performance evaluation. Section 5 summarizes the related work, and Section 6 concludes the paper and presents the prospect for the future work.


## 2. Preliminary Knowledge

In this section, a fog computing framework for IoT applications is designed and the load-balance analysis is conducted as well.To facilitate dynamic resource allocation for load balancing in fog environment, formal concepts and load-balance analysis are presented in this section. Key notations and descriptions used in this section are listed in the section named “Key Terms and Descriptions Involved in Resource Scheduling in Fog Environment.”


### 2.1. System Framework for Fog Computing

Fog computing is a new computing paradigm, which sufficiently leverages the decentralized resources through the fog and cloud environments, to provision the computation and storage services for the IoT applications. Fog computing extends the data process and data storage between the smart sensors and the cloud data centers. Some of the tasks from the IoT applications could be processed in the fog rather than performing all the tasks in the cloud environment. The virtualized technology could be employed to improve the resource usage in the fog environment.Figure1 shows a hierarchical framework for computing tasks from IoT applications in the fog environment. There are four layers in this framework, that is, the IoT application layer, the service layer, the fog layer, and the cloud layer. The IoT application contains a large amount of service requirements that need to be responded to by selecting appropriate computing nodes according to the time urgency and the resource amount from fog and cloud. The fog layer consists of the edge computing nodes and the intermediate computing nodes. The services with the highest time urgency and less computation density can be calculated by the edge computing nodes in the fog layer, and the less urgent tasks could choose intermediate computing nodes for execution. The cloud layer is appropriate to hosting the loose-fitting tasks with high-density computation and huge-volume storage which often demand a large amount of physical resources. The intermediate computing nodes could be the routers for data transmission, the edge computing nodes could be the mobile devices or sensors, and the computing nodes in the cloud are the PMs.Figure 1
Fog computing framework for IoT applications.Fog computing is useful for IoT applications which combine many fog services. The fog services cover all the procedures of the data extraction, data transmission, data storage, and service execution from the IoT applications.Definition 1 (fog service).
The services requested by the IoT applications are available to be performed in the fog and remote cloud data centers, denoted asS={s1,s2,…,sN}, where N is the number of fog services generated by the IoT applications.The PMs in the remote cloud data centers, the intermediate computing nodes, and the edge computing nodes in the fog environment are all available to be leveraged to provision physical resources for the fog services. Suppose there areM computing nodes in the fog and cloud environment, denoted as P={p1,p2,…,pM}. The virtualized technology has been widely applied in the cloud environment, which is also adaptive in the fog environment to measure the resource capacity of all the computing nodes and the resource requirement of the fog services.Definition 2 (resource capacity of computing nodes).
For all the computing nodes in the fog and cloud, their resource capacities are quantified as the number of resource units, and each resource unit contains various physical resources, including CPU, memory, and bandwidth.Definition 3 (resource requirement ofsn).
The corresponding resource requirement of thenth fog service sn could be quantified as the time requirements, the resource type, and the resource amount to perform sn, denoted as rn={stimn,dutimn,typen,coun}, where stimn, dutimn, typen, and coun represent the request start time, the duration time, the resource type, and the requested amount of sn, respectively.Note that the resource requirements in this paper are measured by the amount of resource units. For example, in the cloud data centers, the resource units are the VM instances, and the customers often rent several VM instances to host one application.


### 2.2. Load Balancing Model in Fog Environment

Fog computing paradigm releases the load distribution in the cloud environment. Due to the diversity of execution duration and specifications for the computing nodes in the fog, the resources could not be fully utilized. In the fog environment, we try to achieve load balancing for the computing nodes to avoid low utilization or overload of the computing nodes.LetInm(t) be the binary variable to judge whether sn (1≤n≤N) is assigned to the computing node pm (1≤m≤M) at time instant t, which is calculated by(1)Inmt=1,ifsnisassignedtopm,0,otherwise.With the judgement of fog service distribution, the resource utilization for themth computing node pm at time t is calculated by(2)rumt=1cm∑n=1NInmt·rn,where cm is the capacity of the computing node pm.According to the service distribution, the number of services deployed onpm at time instant t is calculated by(3)nsmt=∑n=1NInmt.The load-balance variance should be specified for each type of computing node. Suppose there areW types of computing nodes in cloud and fog environment for performing the fog services.The load-balance variance is closely relevant to the resource utilization. To calculate the resource utilization, the employed amount of computing nodes with typew at the time instant t is calculated by(4)awt=∑m=1Mfmt·βwm,where βwm is a flag to judge whether pm is a type w of computing nodes, which is described in (5), and fm(t) is used to judge whether pm is empty at t, presented in (6). (5)βwm=1,ifpmisawthtypecomputingnode,0,otherwise.(6)fmt=1,ifnsm>0,0,otherwise.The resource utilization for the computing nodes withwth type at time t is calculated by (7)RUwt=1awt∑m=1M∑n=1NInmt·rumt·fmt.Definition 4 (variance of load balance ofpm at time instant t).
The load-balance value is measured by the variance of the resource utilization. The variance value forpm is calculated by(8)lbmt=rumt-∑w=1WRUwt·βwm2.Then, the average variance value for all the typew computing nodes is calculated by(9)LBwt=1awt∑m=1M∑n=1NInmt·lbmt·fmt.For the execution period[T0,T] in the fog and cloud environment, the load-balance variance could be calculated by (10)LBw=1T-T0∫T0TLBwtdt.With these observations, the problem of minimizing the variance of load balance can be formulated as follows:(11)minLBw,∀w=1,…,W(12)s.t.awt≤∑m=1Mβwm,(13)∑n=1Nrn≤∑m=1Mcm,(14)∑n=1NInmrn≤cm,where ∑n=1Nrn in formula (13) represents the resource requirements for all services, ∑m=1Mcm in formula (14) represents the capacity of all computing nodes, and ∑n=1NInmrn in formula (14) represents the resource requirements for all services allocated to the type m computing node.From (11) to (14), we can find that the final objective solved in this paper is an optimization problem with multiple constraints [18–20].


## 2.1. System Framework for Fog Computing

Fog computing is a new computing paradigm, which sufficiently leverages the decentralized resources through the fog and cloud environments, to provision the computation and storage services for the IoT applications. Fog computing extends the data process and data storage between the smart sensors and the cloud data centers. Some of the tasks from the IoT applications could be processed in the fog rather than performing all the tasks in the cloud environment. The virtualized technology could be employed to improve the resource usage in the fog environment.Figure1 shows a hierarchical framework for computing tasks from IoT applications in the fog environment. There are four layers in this framework, that is, the IoT application layer, the service layer, the fog layer, and the cloud layer. The IoT application contains a large amount of service requirements that need to be responded to by selecting appropriate computing nodes according to the time urgency and the resource amount from fog and cloud. The fog layer consists of the edge computing nodes and the intermediate computing nodes. The services with the highest time urgency and less computation density can be calculated by the edge computing nodes in the fog layer, and the less urgent tasks could choose intermediate computing nodes for execution. The cloud layer is appropriate to hosting the loose-fitting tasks with high-density computation and huge-volume storage which often demand a large amount of physical resources. The intermediate computing nodes could be the routers for data transmission, the edge computing nodes could be the mobile devices or sensors, and the computing nodes in the cloud are the PMs.Figure 1
Fog computing framework for IoT applications.Fog computing is useful for IoT applications which combine many fog services. The fog services cover all the procedures of the data extraction, data transmission, data storage, and service execution from the IoT applications.Definition 1 (fog service).
The services requested by the IoT applications are available to be performed in the fog and remote cloud data centers, denoted asS={s1,s2,…,sN}, where N is the number of fog services generated by the IoT applications.The PMs in the remote cloud data centers, the intermediate computing nodes, and the edge computing nodes in the fog environment are all available to be leveraged to provision physical resources for the fog services. Suppose there areM computing nodes in the fog and cloud environment, denoted as P={p1,p2,…,pM}. The virtualized technology has been widely applied in the cloud environment, which is also adaptive in the fog environment to measure the resource capacity of all the computing nodes and the resource requirement of the fog services.Definition 2 (resource capacity of computing nodes).
For all the computing nodes in the fog and cloud, their resource capacities are quantified as the number of resource units, and each resource unit contains various physical resources, including CPU, memory, and bandwidth.Definition 3 (resource requirement ofsn).
The corresponding resource requirement of thenth fog service sn could be quantified as the time requirements, the resource type, and the resource amount to perform sn, denoted as rn={stimn,dutimn,typen,coun}, where stimn, dutimn, typen, and coun represent the request start time, the duration time, the resource type, and the requested amount of sn, respectively.Note that the resource requirements in this paper are measured by the amount of resource units. For example, in the cloud data centers, the resource units are the VM instances, and the customers often rent several VM instances to host one application.


## 2.2. Load Balancing Model in Fog Environment

Fog computing paradigm releases the load distribution in the cloud environment. Due to the diversity of execution duration and specifications for the computing nodes in the fog, the resources could not be fully utilized. In the fog environment, we try to achieve load balancing for the computing nodes to avoid low utilization or overload of the computing nodes.LetInm(t) be the binary variable to judge whether sn (1≤n≤N) is assigned to the computing node pm (1≤m≤M) at time instant t, which is calculated by(1)Inmt=1,ifsnisassignedtopm,0,otherwise.With the judgement of fog service distribution, the resource utilization for themth computing node pm at time t is calculated by(2)rumt=1cm∑n=1NInmt·rn,where cm is the capacity of the computing node pm.According to the service distribution, the number of services deployed onpm at time instant t is calculated by(3)nsmt=∑n=1NInmt.The load-balance variance should be specified for each type of computing node. Suppose there areW types of computing nodes in cloud and fog environment for performing the fog services.The load-balance variance is closely relevant to the resource utilization. To calculate the resource utilization, the employed amount of computing nodes with typew at the time instant t is calculated by(4)awt=∑m=1Mfmt·βwm,where βwm is a flag to judge whether pm is a type w of computing nodes, which is described in (5), and fm(t) is used to judge whether pm is empty at t, presented in (6). (5)βwm=1,ifpmisawthtypecomputingnode,0,otherwise.(6)fmt=1,ifnsm>0,0,otherwise.The resource utilization for the computing nodes withwth type at time t is calculated by (7)RUwt=1awt∑m=1M∑n=1NInmt·rumt·fmt.Definition 4 (variance of load balance ofpm at time instant t).
The load-balance value is measured by the variance of the resource utilization. The variance value forpm is calculated by(8)lbmt=rumt-∑w=1WRUwt·βwm2.Then, the average variance value for all the typew computing nodes is calculated by(9)LBwt=1awt∑m=1M∑n=1NInmt·lbmt·fmt.For the execution period[T0,T] in the fog and cloud environment, the load-balance variance could be calculated by (10)LBw=1T-T0∫T0TLBwtdt.With these observations, the problem of minimizing the variance of load balance can be formulated as follows:(11)minLBw,∀w=1,…,W(12)s.t.awt≤∑m=1Mβwm,(13)∑n=1Nrn≤∑m=1Mcm,(14)∑n=1NInmrn≤cm,where ∑n=1Nrn in formula (13) represents the resource requirements for all services, ∑m=1Mcm in formula (14) represents the capacity of all computing nodes, and ∑n=1NInmrn in formula (14) represents the resource requirements for all services allocated to the type m computing node.From (11) to (14), we can find that the final objective solved in this paper is an optimization problem with multiple constraints [18–20].


## 3. A Dynamic Resource Allocation Method for Load Balancing in Fog Environment

In this section, we propose a dynamic resource allocation method, named DRAM, for load balancing in fog environment. Our method aims to achieve high load balancing for all the types of computing nodes in the fog and the cloud platforms.


### 3.1. Method Overview

Our method consists of four main steps, that is, fog service partition, spare space detection for computing nodes, static resource allocation for fog service subset, and the load-balance driven global resource allocation, as shown in the section named “Specification of our Proposed Resource Allocation Method for Load Balancing in Fog Environment.” In this method, Step1 is the preprocess procedure, Step 2 is employed to detect the resource usage for Steps 3 and 4, and Step 3 is designed for static resource allocation for the fog services in the same subset and it provides the primary resource provision strategies for Step 4. Finally, Step 4 is a global resource allocation method to realize dynamic load balance.Specification of Our Proposed Resource Allocation Method for Load Balancing in Fog EnvironmentStep 1 (fog service partition).
There are different types of computing nodes for the performance of fog services. To efficiently provision resources, the fog services are classified as several sets based on the resource requirements of node type. Furthermore, these sets are divided into multiple subsets according to the request start time.Step 2 (spare space detection for computing nodes).
To judge whether a computing node is portable to host the fog service, it is necessary to detect the spare space of all the computing nodes. We analyze the employed resource units through the analysis of occupation records, and then the spare space of the computing nodes could be obtained.Step 3 (static resource allocation for fog service subset).
For the fog services in the same service subset, the proper computing nodes are identified to host these services. When allocating resource units for a fog service, the computing node with the least and enough spare space is selected. Besides, some workloads from the computing nodes with higher resource usage are migrated to the computing nodes with low resource usage.Step 4 (load-balance driven global resource allocation).
For all the fog service subsets, we could find the initialized resource allocation strategies in Step4, and then the dynamic resource allocation adjustment is conducted at the competition moments of the fog services to achieve the global load balance during the execution period of the fog services.


### 3.2. Fog Service Partition

The fog services from different IoT applications have different requirements of computing resources; that is, the fog services need to choose different types of computing nodes for resource response. Suppose there areW types of processing nodes, including the PMs in cloud platforms, the intermediate nodes, and the edge nodes near the sensors.In this paper, we try to achieve the goal of load balancing for each type of computing node; we assume that the fog services need to be performed with the same type of computing nodes. As a result, the fog services could be partitioned asW different service sets, denoted as F={f1,f2,…,fW}.The resource requirements of the fog services in the same set have different resource response time. To efficiently realize resource allocation for the services, the fog services in the same set should be partitioned to several subsets according to the start time for occupying the resource units of the computing nodes. Then, we can allocate resource units for the fog services in the same set to achieve high load balancing.The subsetfw (w=1,2,…,W) in F is divided into multiple subsets according to the requested start time of the fog services. Let fw,i be the ith (1≤i≤|fw|) subset contained in fw. After the partition process, the fog services in fw,i have the same request start time.For example, there are 6 fog services, that is,s1~s6, and the resource requirements of these 6 services are s1: (0, 1,1, 2), s2: (0, 0.8,1, 1), s3: (1, 0.5,1, 1), s4: (1, 0.7,1, 3), s5: (0, 1.5,2, 2), and s6: (1, 1,2, 3), as shown in Figure 2. These 6 fog services are put in two different sets f1 and f2 according to the requested type of computing nodes, f1={s1,s2,s3,s4} and f2={s5,s6}. Then, f1 and f2 are partitioned to the subsets according to the requested start time. Partition f1 is divided into 2 subsets, f1,1={s1,s2} and f1,2={s3,s4}; meanwhile, f2 is also separated as 2 subsets, that is, f2,1={s5} and f2,2={s6}.Figure 2
An example of subset acquisition with 6 fog services (i.e.,s1~s6).Algorithm1 specifies the process of fog services subset acquisition. In Algorithm 1, the input is the resource requirements of IoT applications, that is, R, and the output is the partitioned fog service set F. We traverse all the fog services (Line (1)), and the services are put in different sets according to the requested resource type (Lines (1) to (6)), and then the fog services are put in W different service sets. Then, the set fw is divided to multiple subsets, according to the required start time (Lines (8) to (17)).Algorithm 1:Fog service subset acquisition.
Input: The resource requirements of IoT applications R Output: The partitioned fog service set F (1) for i = 1 to Ndo (2)  for j = 1 to Wdo //There areW types of computing nodes in fog and cloud (3)   if t y p e i = = j then (4)    Add ri to fi (5)   end if (6)  end for (7) end for (8) for i = 1 to Wdo (9)  nn=0, q=0, f=stim0 (10)  while n n < | f s i | do (11)     if s t i m q ≤ f then (12)      Add the mth fog service to fsi,nn (13)     else n n = n n + 1, q=q+1, f=stimq (14)      Add the qth fog service to fsi,nn (15)     end if (16)  end while (17) end for (18) Return F


### 3.3. Spare Space Detection for Computing Nodes

The fog services need to be put on the computing nodes; thus, those computing nodes with spare space should be identified. For all the computing nodes, the allocation records are employed to monitor the resource usage of all the computing nodes in the fog and cloud.Definition 5 (occupation recordrsm,i).
Theith (1≤i≤|rsm|) occupation record in rsm contains the response fog service, the occupation start time, the duration time, and the resource units, which is a 4-tuple, denoted as rsm,i=(fsm,i,stm,i,dtm,i,usm,i), where fsm,i, stm,i, dtm,i, and usm,i are the fog service, the start time, the duration time, and the resource unit sets of rsm,i, respectively.A computing node has a set of occupation records, since it could host several fog services. The record set for the computing nodepm (1≤m≤M) is recorded as rsm. Then, for all the computing nodes in the fog and cloud, there are M occupation record sets, denoted as RS={rs1,rs2,…,rsM}. In rsm, there are many occupation records, which reflect the resource usage of the computing node pm.The occupation records are dynamically updated according to the real-time resource provisioning for the fog services. Once the fog services are moved to the other computing nodes during their lifetime, the occupation time parameter should be updated accordingly for the relevant records. The occupation records are generated from the users when they apply for resources in the fog and cloud data center for implementing the services generated from the IoT applications.Benefiting from the resource monitoring, the occupied resource units of all the computing nodes and the spare units could be detected for resource allocation at any time.Definition 6 (spare space ofpm).
The spare space of the computing nodepm is defined as the idle amount of resource units, which is measured by the difference value of the capacity and the occupied amount of resource units on pm.The spare space of the computing nodepm could be detected from the analysis of occupation records. In these records, if occupation start time is less than the statistic time instant for checking the PM status and the occupation finish time is over the statistic time, the relevant resource units combined in the occupation records could be obtained. With these acquired resource units and the resource capacity of pm, the spare space could be finally detected.For example, there are 6 occupation records for the computing nodep1, that is, r1:(1,0,0.5,{u1,1}), r2:(2,0.3,0.7,{u1,2}), r3:(3,1.3,1,{u1,1,u1,2}), r4:(4,1.4,1.2,{u1,3}), r5:(5,1.4,0.8,{u1,4,u1,5}), and r6:(6,2.5,0.5,{u1,1}), as shown in Figure 3. If the statistic instant for spare space detection is 1.5, the identified occupation records within the statistic time are r3, r4, and r5. Based on the analysis of the occupation records, the employed resource units at this moment are u1,1, u1,2, u1,3, u1,4, and u1,5. Suppose the capacity of p1 is 6; then, the spare space of p1 at time instant 1.5 is 1.Figure 3
An example of spare space detection with 6 occupation records (i.e.,r1~r6).Algorithm2 specifies the key idea of spare space detection for computing nodes. In Algorithm 2, the input and the output are the occupation records of the computing node pm and the spare space for pm. According to Definition 7, we need to calculate the occupation amount of resource units on pm first (Lines (1) to (8)), and then the spare space could be detected (Line (8)).Algorithm 2:Spare space detection for computing nodes.
Input: The occupation record for the computing node pm Output: The spare space for pm (1) c o u = 0 (2) for i = 1 to |rsm|do (3) c t m , i = s t m , i + d t m , i //ctm,i is the finish time for the occupation of resource units (4)  if t ≥ s t m , i   & &   t < c t m , i then //t is the request time for statistics (5) c o u = c o u + | u s m , i | (6)  end if (7) end for (8) c o u = c m - c o u (9) Return cou


### 3.4. Static Resource Allocation for Fog Service Subset

Based on the fog service partition in Section3.1 and spare space detection for computing nodes in Section 3.2, the fog services that need to be processed and the available computing resources for fog service execution are identified, which are all beneficial for resource allocation.In the fog environment, the fog services need to be responded to by the computing nodes, and the time requirements also should be presented when allocating the resources to the fog services. In this section, we define the resource allocation records to reserve the allocation history about resource provisioning for the fog services.Definition 7 (resource allocation record forsn).
The resource allocation record forsn consists of the node type, the number of resource units, the start time, and the desired duration time, which is denoted as an=(ntn,numn,stn,dtn), where ntn, numn, stn, and dtn are the node type, the amount of resource units, the service start time, and the resource occupation time for sn, respectively.The fog services in the same fog service subset have the same required node type and start time. When allocating resource units for the fog service subset, each fog service should find a portable computing node to host it. Thus, we need to find the available nodes first. The computing nodes with the requested type, which have spare space, which could be detected by Algorithm2, are chosen as the candidate resources to be provided for the fog services in the subset.To achieve the load balancing of the computing nodes, we try to achieve high resource usage of the employed computing nodes. The problem of static resource allocation is like bin packing problem, which is NP-hard. Here, we leverage the idea of Best Fit Decreasing to realize the process of computing node matching for the fog services. Before resource allocation, the fog services are sorted in the decreasing order of requested resource amount. The service with more required resource units will be processed first. And it chooses the computing node with the least and enough spare space for hosting the service.For example, there are 3 computing nodesP1, P2, and P3, and the spare spaces of these 3 computing nodes are 4, 6, and 9, respectively, as shown in Figure 4. There are two fog services in the same subset, that is, S1 and S2, and the requested resource amounts of these two services are 2 and 6. When conducting resource allocation for S1 and S2, S2 has more resource requirements, and thus S2 is processed first. After resource allocation, S2 chose P3 for hosting and S1 chose P1 for hosting.Figure 4
An example of static resource allocation for fog servicesS1 and S2, with computing nodes P1, P2, and P3.The above allocation may lead to the unbalanced distribution of the workloads of some computing nodes. In this section, a thresholdρ is employed to judge whether the computing node is in low resource utilization. If a computing node is in low resource utilization and there are no other computing nodes that could host the workloads in this computing node, we choose to move some workloads to this computing node to improve the load balance.After resource allocation, there are several allocation records generated, to record the allocation history for the fog services in the service subset. Meanwhile, there are some computing nodes, providing resource units for executing the fog services, which also generate some occupation records.Algorithm3 illustrates the key idea of static resource allocation for fog service subset fw,i. The input of Algorithm 3 is the fog service subset fw,i, and the output of this algorithm is the resource allocation records for the fog services in fw,i. The required computing nodes of fog services in the same subset have the same node type, which should be obtained first (Line (1)). The services with fewer requested resource units will be processed first, so fw,i should be sorted in the increasing order of the amount of values of required resources. Then, each service could be responded to with computing nodes sequentially (Line (3)). When selecting a computing node to provision resources for a fog service, the available computing nodes with enough spare space to host the service, calculated by Algorithm 2, should be achieved first (Lines (4) to (11)). The computing nodes also should be sorted in the increasing order of spare space (Line (12)). Then, the computing node with the least spare space will be selected to accommodate the service (Line (13)). Some workloads from the computing nodes with higher resource usage will be migrated to the computing nodes with low resource utilization to improve load balance (Lines (15) to (24)). Finally, the relevant occupation records and the resource allocation record for the fog service should be updated (Lines (25) and (26)).Algorithm 3:Static resource allocation for fog service subset.
Input: The fog service subset fw,i Output: The relevant resource allocation records (1)Get the node type nt in the service subset fw,i (2)Sort fw,i in decreasing order of required resource amount (3) foreach fog service in fw,ido (4)  for i = 1 to Mdo (5)   if p m has the same type with ntthen (6)Get the spare space byAlgorithm2 (7)    if p m has enough space to host the servicethen (8)Add the computing node to CL (9)    end if (10)   end if (11)  end for (12)Sort CL in increasing order of spare space (13)Put the service in the first computing node in CL (14) end for (15)flag = 1, i=1 (16)Identify the occupied computing nodes from CL to CL′ (17)Sort CL′ in the decreasing order of spare space (18) whileflag == 1do (19)  ifthe resource usage of cli′ is less than ρthen (20)Select the tasks to migrate to the computing node (21) i = i + 1 (22)  elseflag = 0 (23)  end if (24) end while (25)Update the relevant occupation records (26)Generate an allocation records


### 3.5. Load-Balance Driven Global Resource Allocation

From the analysis in Sections3.2 and 3.4, the initialized resource allocation is conducted, and the different types of computing nodes could achieve high resource utilization and load balancing at the allocation moment. However, the static resource allocation only could achieve the temporary load balancing at the service arrival moments. During the service running, the resource usage of the computing nodes is dynamically changed due to the various lifetimes of the fog services. In this section, a global resource allocation strategy is designed to make load balancing come true during the execution of the fog services.The fog service subsets demand the same type of computing nodes for hosting sequentially according to the requested start time of the resources. Letbtw,i be the requested start time for resource occupation of the ith subset fw,i in fw. For dynamic adjustment of resource allocation at the finish time of the fog services in btw,i (1≤i<fw), the scheduling time should be with the time period (btw,i,btw,i+1). When i=fw, the scheduling time should be the competition time for the rest of the fog service loads during the period for the execution of the fog services in fw,i.At the scheduling time, the running workloads occupy some computing nodes, and these computing nodes may be with low resource usage due to the service competition. The computing nodes with the same type in fog or cloud could be sorted in the decreasing order of the resource usage. The workloads in the computing nodes with the lower resource usage could be migrated to the computing nodes with higher resource usage, to achieve higher resource utilization. Besides, the migration of workloads could also help to realize the goal of load balancing as the computing nodes with more spare space could be moved vacant and shut down further.For the workloads from different fog services, it is necessary to find the destination computing nodes to host them. The selection of destination computing nodes decides on the resource requirements of the workloads and the spare space of the computing nodes. If all the workloads from the same computing node could find the destination computing nodes, these workloads could be migrated to the destination computing nodes. Finally, the resource allocation records and the occupation records are generated or updated according to the real occupation computing nodes and the usage time of the corresponding resource units.Algorithm4 illustrates the key process of load-balance driven global resource allocation. The key idea of Algorithm 4 is to conduct static resource allocation for the fog services at the start execution time and dynamically adjust the service placement according to the resource usage of all the employed computing nodes. The input of this algorithm is the fog service set S, and the final output of this algorithm is the resource allocation records and the occupation records. In this algorithm, the fog service subset is achieved first by Algorithm 1 (Line (1)), and then we traverse each subset for resource allocation (Line (2)) and conduct static resource allocation for the subsets by Algorithm 3 (Line (3)). Then, for each subset, the competition time list CL is extracted for load-balance driven dynamic resource allocation (Line (5)). Then, at each competition instant, we adjust the resource allocation records for the running services (Line (6)). The fog services on the computing node with less spare space would be moved to the computing node with higher resource usage, which has enough spare space to host the services (Lines (8) to (20)). When all the fog services on a computing node could find the destination node, the relevant allocation records and the occupation records for the resource units will be generated and updated (Lines (15) to (27)).Algorithm 4:Load-balance driven global resource allocation.
Input: The fog service set S Output: The resource allocation records The occupation records on computing nodes (1)Obtain fog service subset F by Algorithm1 (2) for i = 1 to Wdo (3)  for j = 1 to |fw|do (4) Algorithm 3 Static resource allocation for fw,j (5)Calculate CT // CT is the competition time list // CT ={ct1,ct2,…,ctK} (6)   for k = 1 to Kdo (7)Update the current run list in fw,j (8)    for l = 1 to Mdo (9)Get spare space by Algorithm2 at ctk (10)     if p l has spare space and is not emptythen (11)Add pl to SL (12)     end if (13)    end for (14)Sort SL in increasing order of spare space (15)flag = 1, q=1 (16)    whileflag == 1do (17)Get the occupied resources sets on slq (18)      for each occupied resource setdo (19)Confirm the destination PM (20)      end for (21)      ifthe resource sets can be movedthen (22) q = q + 1 (23)Update the relevant allocation records (24)Update the occupation records (25)      elseflag = 0 (26)      end if (27)    end while (28)   end for (29)  end for (30) end for


## 3.1. Method Overview

Our method consists of four main steps, that is, fog service partition, spare space detection for computing nodes, static resource allocation for fog service subset, and the load-balance driven global resource allocation, as shown in the section named “Specification of our Proposed Resource Allocation Method for Load Balancing in Fog Environment.” In this method, Step1 is the preprocess procedure, Step 2 is employed to detect the resource usage for Steps 3 and 4, and Step 3 is designed for static resource allocation for the fog services in the same subset and it provides the primary resource provision strategies for Step 4. Finally, Step 4 is a global resource allocation method to realize dynamic load balance.Specification of Our Proposed Resource Allocation Method for Load Balancing in Fog EnvironmentStep 1 (fog service partition).
There are different types of computing nodes for the performance of fog services. To efficiently provision resources, the fog services are classified as several sets based on the resource requirements of node type. Furthermore, these sets are divided into multiple subsets according to the request start time.Step 2 (spare space detection for computing nodes).
To judge whether a computing node is portable to host the fog service, it is necessary to detect the spare space of all the computing nodes. We analyze the employed resource units through the analysis of occupation records, and then the spare space of the computing nodes could be obtained.Step 3 (static resource allocation for fog service subset).
For the fog services in the same service subset, the proper computing nodes are identified to host these services. When allocating resource units for a fog service, the computing node with the least and enough spare space is selected. Besides, some workloads from the computing nodes with higher resource usage are migrated to the computing nodes with low resource usage.Step 4 (load-balance driven global resource allocation).
For all the fog service subsets, we could find the initialized resource allocation strategies in Step4, and then the dynamic resource allocation adjustment is conducted at the competition moments of the fog services to achieve the global load balance during the execution period of the fog services.


## 3.2. Fog Service Partition

The fog services from different IoT applications have different requirements of computing resources; that is, the fog services need to choose different types of computing nodes for resource response. Suppose there areW types of processing nodes, including the PMs in cloud platforms, the intermediate nodes, and the edge nodes near the sensors.In this paper, we try to achieve the goal of load balancing for each type of computing node; we assume that the fog services need to be performed with the same type of computing nodes. As a result, the fog services could be partitioned asW different service sets, denoted as F={f1,f2,…,fW}.The resource requirements of the fog services in the same set have different resource response time. To efficiently realize resource allocation for the services, the fog services in the same set should be partitioned to several subsets according to the start time for occupying the resource units of the computing nodes. Then, we can allocate resource units for the fog services in the same set to achieve high load balancing.The subsetfw (w=1,2,…,W) in F is divided into multiple subsets according to the requested start time of the fog services. Let fw,i be the ith (1≤i≤|fw|) subset contained in fw. After the partition process, the fog services in fw,i have the same request start time.For example, there are 6 fog services, that is,s1~s6, and the resource requirements of these 6 services are s1: (0, 1,1, 2), s2: (0, 0.8,1, 1), s3: (1, 0.5,1, 1), s4: (1, 0.7,1, 3), s5: (0, 1.5,2, 2), and s6: (1, 1,2, 3), as shown in Figure 2. These 6 fog services are put in two different sets f1 and f2 according to the requested type of computing nodes, f1={s1,s2,s3,s4} and f2={s5,s6}. Then, f1 and f2 are partitioned to the subsets according to the requested start time. Partition f1 is divided into 2 subsets, f1,1={s1,s2} and f1,2={s3,s4}; meanwhile, f2 is also separated as 2 subsets, that is, f2,1={s5} and f2,2={s6}.Figure 2
An example of subset acquisition with 6 fog services (i.e.,s1~s6).Algorithm1 specifies the process of fog services subset acquisition. In Algorithm 1, the input is the resource requirements of IoT applications, that is, R, and the output is the partitioned fog service set F. We traverse all the fog services (Line (1)), and the services are put in different sets according to the requested resource type (Lines (1) to (6)), and then the fog services are put in W different service sets. Then, the set fw is divided to multiple subsets, according to the required start time (Lines (8) to (17)).Algorithm 1:Fog service subset acquisition.
Input: The resource requirements of IoT applications R Output: The partitioned fog service set F (1) for i = 1 to Ndo (2)  for j = 1 to Wdo //There areW types of computing nodes in fog and cloud (3)   if t y p e i = = j then (4)    Add ri to fi (5)   end if (6)  end for (7) end for (8) for i = 1 to Wdo (9)  nn=0, q=0, f=stim0 (10)  while n n < | f s i | do (11)     if s t i m q ≤ f then (12)      Add the mth fog service to fsi,nn (13)     else n n = n n + 1, q=q+1, f=stimq (14)      Add the qth fog service to fsi,nn (15)     end if (16)  end while (17) end for (18) Return F


## 3.3. Spare Space Detection for Computing Nodes

The fog services need to be put on the computing nodes; thus, those computing nodes with spare space should be identified. For all the computing nodes, the allocation records are employed to monitor the resource usage of all the computing nodes in the fog and cloud.Definition 5 (occupation recordrsm,i).
Theith (1≤i≤|rsm|) occupation record in rsm contains the response fog service, the occupation start time, the duration time, and the resource units, which is a 4-tuple, denoted as rsm,i=(fsm,i,stm,i,dtm,i,usm,i), where fsm,i, stm,i, dtm,i, and usm,i are the fog service, the start time, the duration time, and the resource unit sets of rsm,i, respectively.A computing node has a set of occupation records, since it could host several fog services. The record set for the computing nodepm (1≤m≤M) is recorded as rsm. Then, for all the computing nodes in the fog and cloud, there are M occupation record sets, denoted as RS={rs1,rs2,…,rsM}. In rsm, there are many occupation records, which reflect the resource usage of the computing node pm.The occupation records are dynamically updated according to the real-time resource provisioning for the fog services. Once the fog services are moved to the other computing nodes during their lifetime, the occupation time parameter should be updated accordingly for the relevant records. The occupation records are generated from the users when they apply for resources in the fog and cloud data center for implementing the services generated from the IoT applications.Benefiting from the resource monitoring, the occupied resource units of all the computing nodes and the spare units could be detected for resource allocation at any time.Definition 6 (spare space ofpm).
The spare space of the computing nodepm is defined as the idle amount of resource units, which is measured by the difference value of the capacity and the occupied amount of resource units on pm.The spare space of the computing nodepm could be detected from the analysis of occupation records. In these records, if occupation start time is less than the statistic time instant for checking the PM status and the occupation finish time is over the statistic time, the relevant resource units combined in the occupation records could be obtained. With these acquired resource units and the resource capacity of pm, the spare space could be finally detected.For example, there are 6 occupation records for the computing nodep1, that is, r1:(1,0,0.5,{u1,1}), r2:(2,0.3,0.7,{u1,2}), r3:(3,1.3,1,{u1,1,u1,2}), r4:(4,1.4,1.2,{u1,3}), r5:(5,1.4,0.8,{u1,4,u1,5}), and r6:(6,2.5,0.5,{u1,1}), as shown in Figure 3. If the statistic instant for spare space detection is 1.5, the identified occupation records within the statistic time are r3, r4, and r5. Based on the analysis of the occupation records, the employed resource units at this moment are u1,1, u1,2, u1,3, u1,4, and u1,5. Suppose the capacity of p1 is 6; then, the spare space of p1 at time instant 1.5 is 1.Figure 3
An example of spare space detection with 6 occupation records (i.e.,r1~r6).Algorithm2 specifies the key idea of spare space detection for computing nodes. In Algorithm 2, the input and the output are the occupation records of the computing node pm and the spare space for pm. According to Definition 7, we need to calculate the occupation amount of resource units on pm first (Lines (1) to (8)), and then the spare space could be detected (Line (8)).Algorithm 2:Spare space detection for computing nodes.
Input: The occupation record for the computing node pm Output: The spare space for pm (1) c o u = 0 (2) for i = 1 to |rsm|do (3) c t m , i = s t m , i + d t m , i //ctm,i is the finish time for the occupation of resource units (4)  if t ≥ s t m , i   & &   t < c t m , i then //t is the request time for statistics (5) c o u = c o u + | u s m , i | (6)  end if (7) end for (8) c o u = c m - c o u (9) Return cou


## 3.4. Static Resource Allocation for Fog Service Subset

Based on the fog service partition in Section3.1 and spare space detection for computing nodes in Section 3.2, the fog services that need to be processed and the available computing resources for fog service execution are identified, which are all beneficial for resource allocation.In the fog environment, the fog services need to be responded to by the computing nodes, and the time requirements also should be presented when allocating the resources to the fog services. In this section, we define the resource allocation records to reserve the allocation history about resource provisioning for the fog services.Definition 7 (resource allocation record forsn).
The resource allocation record forsn consists of the node type, the number of resource units, the start time, and the desired duration time, which is denoted as an=(ntn,numn,stn,dtn), where ntn, numn, stn, and dtn are the node type, the amount of resource units, the service start time, and the resource occupation time for sn, respectively.The fog services in the same fog service subset have the same required node type and start time. When allocating resource units for the fog service subset, each fog service should find a portable computing node to host it. Thus, we need to find the available nodes first. The computing nodes with the requested type, which have spare space, which could be detected by Algorithm2, are chosen as the candidate resources to be provided for the fog services in the subset.To achieve the load balancing of the computing nodes, we try to achieve high resource usage of the employed computing nodes. The problem of static resource allocation is like bin packing problem, which is NP-hard. Here, we leverage the idea of Best Fit Decreasing to realize the process of computing node matching for the fog services. Before resource allocation, the fog services are sorted in the decreasing order of requested resource amount. The service with more required resource units will be processed first. And it chooses the computing node with the least and enough spare space for hosting the service.For example, there are 3 computing nodesP1, P2, and P3, and the spare spaces of these 3 computing nodes are 4, 6, and 9, respectively, as shown in Figure 4. There are two fog services in the same subset, that is, S1 and S2, and the requested resource amounts of these two services are 2 and 6. When conducting resource allocation for S1 and S2, S2 has more resource requirements, and thus S2 is processed first. After resource allocation, S2 chose P3 for hosting and S1 chose P1 for hosting.Figure 4
An example of static resource allocation for fog servicesS1 and S2, with computing nodes P1, P2, and P3.The above allocation may lead to the unbalanced distribution of the workloads of some computing nodes. In this section, a thresholdρ is employed to judge whether the computing node is in low resource utilization. If a computing node is in low resource utilization and there are no other computing nodes that could host the workloads in this computing node, we choose to move some workloads to this computing node to improve the load balance.After resource allocation, there are several allocation records generated, to record the allocation history for the fog services in the service subset. Meanwhile, there are some computing nodes, providing resource units for executing the fog services, which also generate some occupation records.Algorithm3 illustrates the key idea of static resource allocation for fog service subset fw,i. The input of Algorithm 3 is the fog service subset fw,i, and the output of this algorithm is the resource allocation records for the fog services in fw,i. The required computing nodes of fog services in the same subset have the same node type, which should be obtained first (Line (1)). The services with fewer requested resource units will be processed first, so fw,i should be sorted in the increasing order of the amount of values of required resources. Then, each service could be responded to with computing nodes sequentially (Line (3)). When selecting a computing node to provision resources for a fog service, the available computing nodes with enough spare space to host the service, calculated by Algorithm 2, should be achieved first (Lines (4) to (11)). The computing nodes also should be sorted in the increasing order of spare space (Line (12)). Then, the computing node with the least spare space will be selected to accommodate the service (Line (13)). Some workloads from the computing nodes with higher resource usage will be migrated to the computing nodes with low resource utilization to improve load balance (Lines (15) to (24)). Finally, the relevant occupation records and the resource allocation record for the fog service should be updated (Lines (25) and (26)).Algorithm 3:Static resource allocation for fog service subset.
Input: The fog service subset fw,i Output: The relevant resource allocation records (1)Get the node type nt in the service subset fw,i (2)Sort fw,i in decreasing order of required resource amount (3) foreach fog service in fw,ido (4)  for i = 1 to Mdo (5)   if p m has the same type with ntthen (6)Get the spare space byAlgorithm2 (7)    if p m has enough space to host the servicethen (8)Add the computing node to CL (9)    end if (10)   end if (11)  end for (12)Sort CL in increasing order of spare space (13)Put the service in the first computing node in CL (14) end for (15)flag = 1, i=1 (16)Identify the occupied computing nodes from CL to CL′ (17)Sort CL′ in the decreasing order of spare space (18) whileflag == 1do (19)  ifthe resource usage of cli′ is less than ρthen (20)Select the tasks to migrate to the computing node (21) i = i + 1 (22)  elseflag = 0 (23)  end if (24) end while (25)Update the relevant occupation records (26)Generate an allocation records


## 3.5. Load-Balance Driven Global Resource Allocation

From the analysis in Sections3.2 and 3.4, the initialized resource allocation is conducted, and the different types of computing nodes could achieve high resource utilization and load balancing at the allocation moment. However, the static resource allocation only could achieve the temporary load balancing at the service arrival moments. During the service running, the resource usage of the computing nodes is dynamically changed due to the various lifetimes of the fog services. In this section, a global resource allocation strategy is designed to make load balancing come true during the execution of the fog services.The fog service subsets demand the same type of computing nodes for hosting sequentially according to the requested start time of the resources. Letbtw,i be the requested start time for resource occupation of the ith subset fw,i in fw. For dynamic adjustment of resource allocation at the finish time of the fog services in btw,i (1≤i<fw), the scheduling time should be with the time period (btw,i,btw,i+1). When i=fw, the scheduling time should be the competition time for the rest of the fog service loads during the period for the execution of the fog services in fw,i.At the scheduling time, the running workloads occupy some computing nodes, and these computing nodes may be with low resource usage due to the service competition. The computing nodes with the same type in fog or cloud could be sorted in the decreasing order of the resource usage. The workloads in the computing nodes with the lower resource usage could be migrated to the computing nodes with higher resource usage, to achieve higher resource utilization. Besides, the migration of workloads could also help to realize the goal of load balancing as the computing nodes with more spare space could be moved vacant and shut down further.For the workloads from different fog services, it is necessary to find the destination computing nodes to host them. The selection of destination computing nodes decides on the resource requirements of the workloads and the spare space of the computing nodes. If all the workloads from the same computing node could find the destination computing nodes, these workloads could be migrated to the destination computing nodes. Finally, the resource allocation records and the occupation records are generated or updated according to the real occupation computing nodes and the usage time of the corresponding resource units.Algorithm4 illustrates the key process of load-balance driven global resource allocation. The key idea of Algorithm 4 is to conduct static resource allocation for the fog services at the start execution time and dynamically adjust the service placement according to the resource usage of all the employed computing nodes. The input of this algorithm is the fog service set S, and the final output of this algorithm is the resource allocation records and the occupation records. In this algorithm, the fog service subset is achieved first by Algorithm 1 (Line (1)), and then we traverse each subset for resource allocation (Line (2)) and conduct static resource allocation for the subsets by Algorithm 3 (Line (3)). Then, for each subset, the competition time list CL is extracted for load-balance driven dynamic resource allocation (Line (5)). Then, at each competition instant, we adjust the resource allocation records for the running services (Line (6)). The fog services on the computing node with less spare space would be moved to the computing node with higher resource usage, which has enough spare space to host the services (Lines (8) to (20)). When all the fog services on a computing node could find the destination node, the relevant allocation records and the occupation records for the resource units will be generated and updated (Lines (15) to (27)).Algorithm 4:Load-balance driven global resource allocation.
Input: The fog service set S Output: The resource allocation records The occupation records on computing nodes (1)Obtain fog service subset F by Algorithm1 (2) for i = 1 to Wdo (3)  for j = 1 to |fw|do (4) Algorithm 3 Static resource allocation for fw,j (5)Calculate CT // CT is the competition time list // CT ={ct1,ct2,…,ctK} (6)   for k = 1 to Kdo (7)Update the current run list in fw,j (8)    for l = 1 to Mdo (9)Get spare space by Algorithm2 at ctk (10)     if p l has spare space and is not emptythen (11)Add pl to SL (12)     end if (13)    end for (14)Sort SL in increasing order of spare space (15)flag = 1, q=1 (16)    whileflag == 1do (17)Get the occupied resources sets on slq (18)      for each occupied resource setdo (19)Confirm the destination PM (20)      end for (21)      ifthe resource sets can be movedthen (22) q = q + 1 (23)Update the relevant allocation records (24)Update the occupation records (25)      elseflag = 0 (26)      end if (27)    end while (28)   end for (29)  end for (30) end for


## 4. Experimental Analysis

In this section, the cloud simulator Cloudsim is applied to evaluate our proposed method DRAM. The intermediate computing nodes and the edge computing nodes are simulated as two computing data centers. The resource allocation method for fog environment is NP-hard, like the bin packing problem; thus, the typical and efficient resource allocation methods FF, BF, FFD, and BFD are employed for comparison analysis.


### 4.1. Experimental Context

To discuss the effectiveness of DRAM, 4 datasets with different scale of fog services are utilized, which are shared athttps://drive.google.com/drive/folders/0B0T819XffFKrZTV4MFdzSjg0dDA?usp=sharing. The parameters for experimental evaluation are presented in Table 1.Table 1
Parameter settings.
Parameter Domain Number of fog services { 500,1000,1500,2000 } Number of computing nodes 3000 Number of node types 3 Resource capacity { 7,12,18 } Resource requirements of fog services [ 1,15 ] Duration for each service [ 0.1,4.8 ]The fog services employ three types of computing nodes, that is, the edge computing node, the intermediate node, and the PMs in cloud for resource response. The number of services for each type of computing node contained in the 4 different datasets is shown in Figure5. For example, when the number of fog services is 1000, there are 324 fog services that need edge computing nodes, 353 fog services that need intermediate computing nodes, and 323 fog services that need PMs in the remote cloud for resource response.Figure 5
Number of fog services for the 3 types of computing nodes with different datasets.


### 4.2. Performance Evaluation

Our proposed method tends to minimize the load-balance variance, which is relevant to the resource utilization of each computing node and the average resource utilization. Therefore, we conduct performance evaluation for this fog computing system on the employed number of computing nodes, resource utilization, and load-balance variance.(  1) Performance Evaluation on the Employed Number of Computing Nodes. The number of the computing nodes could reflect the efficiency of resource usage. Figure 6 shows the comparison of the number of employed computing nodes by FF, BF, FFD, BFD, and DRAM by using the 4 different scales of datasets. From Figure 6, we can find that our proposed method DRAM as well as BFD could employ fewer computing nodes, compared with FF, BF, and FFD, when the number of fog services is 500, 1000, and 2000. When the number of fog services is 1500, our proposed DRAM could even get higher efficiency on the employed number of computing nodes than BFD. In the process of static resource allocation, DRAM leverages the basic idea of BFD; thus, in most cases, DRAM and BFD have similar performance on the amount of employed computing nodes. But when some of the computing nodes are spared through the process of DRAM, thus in some cases, DRAM is superior to BFD.Figure 6
Comparison of the number of employed computing nodes by FF, BF, FFD, BFD, and DRAM with different datasets.As there are 3 types of computing nodes in our experimental evaluations, we should evaluate DRAM for the different types of computing nodes, compared to the other four methods. The 4 subfigures in Figure7 show the comparison of the number of the employed computing nodes with different types by FF, BF, FFD, BFD, and DRAM using different datasets. It is intuitive from Figure 7 that our proposed method DRAM is fit for all kinds of computing nodes, which employs fewer computing nodes than FF, BF, and FFD, and gets similar performance to BFD in most cases.Figure 7
Comparison of the number of the employed computing nodes with different types by FF, BF, FFD, BFD, and DRAM using different datasets.
(a)
Number of fog services = 500 (b)
Number of fog services = 1000 (c)
Number of fog services = 1500 (d)
Number of fog services = 2000(  2) Performance Evaluation on Resource Utilization. The resource utilization is a key factor to decide the load-balance variance; thus we evaluate this value to discuss the resource usage achieved by FF, BF, FFD, BFD, and DRAM with different datasets. The resource utilization is referenced to the resource usage of the resource units on the computing nodes. Figure 8 shows the comparison of average resource utilization by FF, BF, FFD, BFD, and DRAM with different datasets. It is intuitive from Figure 8 that DRAM could obtain better resource utilization than FF, BF, FFD, and BFD, since DRAM is a dynamic and adaptive method which could adjust the load distribution during the fog service execution.Figure 8
Comparison of average resource utilization by FF, BF, FFD, BFD, and DRAM with different datasets.Similar to the evaluation on the employed amount of computing nodes, the performance evaluation on resource utilization is conducted from the perspective of the different types of the computing nodes. Figure9 shows the comparison of resource utilization for different types of computing nodes by FF, BF, FFD, BFD, and DRAM with different datasets. From Figure 9, we can find that DRAM could achieve higher resource utilization than FF, BF, FFD, and BFD. For example, in Figure 9(c), when the number of fog services is 1500, DRAM obtains the resource utilization over 80%, whereas FF, BF, FFD, and BFD obtain near or below 70% resource utilization for each type of computing node.Figure 9
Comparison of resource utilization for different types of computing nodes by FF, BF, FFD, BFD, and DRAM with different datasets.
(a)
Number of fog services = 500 (b)
Number of fog services = 1000 (c)
Number of fog services = 1500 (d)
Number of fog services = 2000(  3) Performance Evaluation on Load-Balance Variance. The evaluation of the load-balance variance is also conducted by FF, BF, FFD, BFD, and DRAM using 4 different scales of datasets. Figure 10 shows the comparison of average load-balance variance, where we can find that our proposed method DRAM is superior to the other methods, that is, FF, BF, FFD, and BFD. For example, when the number of fog services is 500, the load-balance variance obtained by DRAM is near 2.5 × 10−2, whereas FF, BF, FFD, and BFD obtain the load-balance value over 3 × 10−2.Figure 10
Comparison of average load-balance variance by FF, BF, FFD, BFD, and DRAM with different datasets.The evaluation on the load-balance variance also should take into consideration the computing node type. Figure11 shows the comparison of load-balance variance values for different types of computing nodes by FF, BF, FFD, BFD, and DRAM with different datasets. From Figure 11, we can find that when changing the scale of datasets, our method can keep the priority on the load-balance variance for each type of computing node.Figure 11
Comparison of load-balance variance values for different types of computing nodes by FF, BF, FFD, BFD, and DRAM with different datasets.
(a)
Number of fog services = 500 (b)
Number of fog services = 1000 (c)
Number of fog services = 1500 (d)
Number of fog services = 2000


## 4.1. Experimental Context

To discuss the effectiveness of DRAM, 4 datasets with different scale of fog services are utilized, which are shared athttps://drive.google.com/drive/folders/0B0T819XffFKrZTV4MFdzSjg0dDA?usp=sharing. The parameters for experimental evaluation are presented in Table 1.Table 1
Parameter settings.
Parameter Domain Number of fog services { 500,1000,1500,2000 } Number of computing nodes 3000 Number of node types 3 Resource capacity { 7,12,18 } Resource requirements of fog services [ 1,15 ] Duration for each service [ 0.1,4.8 ]The fog services employ three types of computing nodes, that is, the edge computing node, the intermediate node, and the PMs in cloud for resource response. The number of services for each type of computing node contained in the 4 different datasets is shown in Figure5. For example, when the number of fog services is 1000, there are 324 fog services that need edge computing nodes, 353 fog services that need intermediate computing nodes, and 323 fog services that need PMs in the remote cloud for resource response.Figure 5
Number of fog services for the 3 types of computing nodes with different datasets.


## 4.2. Performance Evaluation

Our proposed method tends to minimize the load-balance variance, which is relevant to the resource utilization of each computing node and the average resource utilization. Therefore, we conduct performance evaluation for this fog computing system on the employed number of computing nodes, resource utilization, and load-balance variance.(  1) Performance Evaluation on the Employed Number of Computing Nodes. The number of the computing nodes could reflect the efficiency of resource usage. Figure 6 shows the comparison of the number of employed computing nodes by FF, BF, FFD, BFD, and DRAM by using the 4 different scales of datasets. From Figure 6, we can find that our proposed method DRAM as well as BFD could employ fewer computing nodes, compared with FF, BF, and FFD, when the number of fog services is 500, 1000, and 2000. When the number of fog services is 1500, our proposed DRAM could even get higher efficiency on the employed number of computing nodes than BFD. In the process of static resource allocation, DRAM leverages the basic idea of BFD; thus, in most cases, DRAM and BFD have similar performance on the amount of employed computing nodes. But when some of the computing nodes are spared through the process of DRAM, thus in some cases, DRAM is superior to BFD.Figure 6
Comparison of the number of employed computing nodes by FF, BF, FFD, BFD, and DRAM with different datasets.As there are 3 types of computing nodes in our experimental evaluations, we should evaluate DRAM for the different types of computing nodes, compared to the other four methods. The 4 subfigures in Figure7 show the comparison of the number of the employed computing nodes with different types by FF, BF, FFD, BFD, and DRAM using different datasets. It is intuitive from Figure 7 that our proposed method DRAM is fit for all kinds of computing nodes, which employs fewer computing nodes than FF, BF, and FFD, and gets similar performance to BFD in most cases.Figure 7
Comparison of the number of the employed computing nodes with different types by FF, BF, FFD, BFD, and DRAM using different datasets.
(a)
Number of fog services = 500 (b)
Number of fog services = 1000 (c)
Number of fog services = 1500 (d)
Number of fog services = 2000(  2) Performance Evaluation on Resource Utilization. The resource utilization is a key factor to decide the load-balance variance; thus we evaluate this value to discuss the resource usage achieved by FF, BF, FFD, BFD, and DRAM with different datasets. The resource utilization is referenced to the resource usage of the resource units on the computing nodes. Figure 8 shows the comparison of average resource utilization by FF, BF, FFD, BFD, and DRAM with different datasets. It is intuitive from Figure 8 that DRAM could obtain better resource utilization than FF, BF, FFD, and BFD, since DRAM is a dynamic and adaptive method which could adjust the load distribution during the fog service execution.Figure 8
Comparison of average resource utilization by FF, BF, FFD, BFD, and DRAM with different datasets.Similar to the evaluation on the employed amount of computing nodes, the performance evaluation on resource utilization is conducted from the perspective of the different types of the computing nodes. Figure9 shows the comparison of resource utilization for different types of computing nodes by FF, BF, FFD, BFD, and DRAM with different datasets. From Figure 9, we can find that DRAM could achieve higher resource utilization than FF, BF, FFD, and BFD. For example, in Figure 9(c), when the number of fog services is 1500, DRAM obtains the resource utilization over 80%, whereas FF, BF, FFD, and BFD obtain near or below 70% resource utilization for each type of computing node.Figure 9
Comparison of resource utilization for different types of computing nodes by FF, BF, FFD, BFD, and DRAM with different datasets.
(a)
Number of fog services = 500 (b)
Number of fog services = 1000 (c)
Number of fog services = 1500 (d)
Number of fog services = 2000(  3) Performance Evaluation on Load-Balance Variance. The evaluation of the load-balance variance is also conducted by FF, BF, FFD, BFD, and DRAM using 4 different scales of datasets. Figure 10 shows the comparison of average load-balance variance, where we can find that our proposed method DRAM is superior to the other methods, that is, FF, BF, FFD, and BFD. For example, when the number of fog services is 500, the load-balance variance obtained by DRAM is near 2.5 × 10−2, whereas FF, BF, FFD, and BFD obtain the load-balance value over 3 × 10−2.Figure 10
Comparison of average load-balance variance by FF, BF, FFD, BFD, and DRAM with different datasets.The evaluation on the load-balance variance also should take into consideration the computing node type. Figure11 shows the comparison of load-balance variance values for different types of computing nodes by FF, BF, FFD, BFD, and DRAM with different datasets. From Figure 11, we can find that when changing the scale of datasets, our method can keep the priority on the load-balance variance for each type of computing node.Figure 11
Comparison of load-balance variance values for different types of computing nodes by FF, BF, FFD, BFD, and DRAM with different datasets.
(a)
Number of fog services = 500 (b)
Number of fog services = 1000 (c)
Number of fog services = 1500 (d)
Number of fog services = 2000


## 5. Related Work

The IoT technology has been widely applied in many fields, including weather forecasting and traffic monitoring. The data storage and processing usually benefit from the cloud computing which provides scalable and elastic resources for executing the IoT applications [21–26]. In the ever-expanding data volume, cloud computing is difficult to provide efficient, low-latency computing services, and fog computing is proposed to complement the above shortage of cloud computing [1, 2].Compared to the remote cloud computing center, fog computing is closer to the Internet of Things devices and sensors. Fog computing can quickly solve lightweight tasks with fast response. In the era of big data, with cloud computing expansion, fog computing is widely used in the medical, transportation, and communication fields, to name a few [21, 27–30].Hu et al. [21] designed a fog calculation framework in detail and compared it with the traditional cloud computing, and a practical application case in the fog computing environment was put forward. Similarly, Kitanov and Janevski [27] compared the cloud computing on computing performance with fog computing in the 5G network, reflecting the superiority of fog computing. Akrivopoulos et al. [28] presented a technology to respond to the combination of IoT applications and the fog computing and introduced the use of fog computing in an automated medical monitoring platform to improve the medical work for the patients. Arfat et al. [29] not only unprecedentedly proposed the integration of mobile applications, big data analysis, and fog computing, but also introduced Google Maps as an example, showing the system of information feedback diversification. Taneja and Davy [30] studied the computational efficiency in the fog environment and constructed a resource-aware placement.Generally, resource allocation refers to the allocation of specific, limited resources and effective management to achieve the optimal use of resources. The original intention of cloud computing is to allocate network resources on demand, so that it is the same as the use of water and electricity billing [31, 32]. In the cloud computing, resource allocation method can effectively help to achieve the goal of high resource usage and energy saving for centralized resource management for different types of applications [4, 33–35]. Fog computing, as an extension of cloud computing paradigm, also needs to conduct resource allocation to achieve high-efficiency resource usage.Mashayekhy et al. [36] proposed an auction-based online mechanism; it can access in real time the actual needs of users and the allocation of appropriate resources to the user price. Kwak et al. [37] developed a DREAM algorithm for complex tasks in mobile devices, saving 35% of total energy and managing network resources. To address the challenges of high latency and resource shortage in clouds, Alsaffar et al. [38] proposed the resource management framework, collaborating the cloud computing and the fog computing, and then they optimized the resource allocation in fog computing. Xiang et al. [39] designed a RAN (F-RAN) architecture based on atomization calculation, which effectively achieved the high resource usage and could coordinate the global resource scheduling.Load balancing is an effective factor to determine the resource allocation strategy. For multiple computing tasks, load balancing could promote the resource managers to assign these tasks to multiple computing nodes for execution. The realization of load balancing not only can save the cost of hardware facilities but also can improve resource efficiency.Banerjee and Hecker [40] proposed a distributed resource allocation protocol algorithm to realize load balancing in a large-scale distributed network; as a result, compared to the FIFO, the response time and resource utilization could be greatly improved. Govindaraju and Duran-Limon [41] designed a method based on the lifecycle-related Service Level Agreement (SLA) parameters of the virtual machines in cloud environment to address resource utilization and cost issues. Evolution algorithms are proved to be powerful to solve the multiobjective problem, which could be leveraged in the resource scheduling in the fog computing [42]. Jeyakrishnan and Sengottuvelan [43] developed a new algorithm, while saving operating costs, while maximizing the use of resources, in the balanced scheduling compared to SA, PSO, and ADS being more outstanding.For the load balancing maximization problem solved in this paper, the traditional operations research is proved to be efficient in optimization problem with constraints [44, 45]. The game theory is also efficient for the resource allocation with resource competition, and the Nash Equilibria are often needed to be verified first [46, 47].To the best of our knowledge, there are few studies focusing on the resource allocation of fog services in the fog environment which aims to realize the load balancing for the computing nodes in both fog and cloud.


## 6. Conclusion and Future Work

In recent years, IoT has been one of the most popular technologies for daily lives. With rapid development of IoT, fog computing is emerging as one of the most powerful paradigms for processing the IoT applications. In the fog environment, the IoT applications are performed by the edge computing nodes and the intermediate computing nodes in the fog, as well as the physical machines in the cloud platforms. To achieve the dynamic load balancing for each type of computing node in the fog and cloud, a dynamic resource allocation method, named DRAM, for load balancing has been developed in this paper. Firstly, a system framework in fog computing was presented and load balancing for the computing nodes is analyzed accordingly. Then, the DRAM method has been implemented based on the static resource allocation and dynamic resource scheduling for fog services. As a result, the experimental evaluations and comparison analysis were carried out to verify the validity of our proposed method.For future work, we try to analyze the negative impact of the service migration, including the traffic for different types of computing nodes, the cost for service migration, the performance degradation for the service migration, and the data transmission cost. Furthermore, we will design a corresponding method to balance the negative effects and the positive impacts for service migration.



---

*Source: 6421607-2018-04-26.xml*