Providing a new scheduling method in fog network using the ant colony algorithm

<!-- metadata commented in wiki content


<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">
'''Providing a new scheduling method in fog network using the ant colony algorithm'''</div>
-->

==Abstract ==

Fog computing provides reliable computing, customized and by guarantee dynamic environments for the end-users, so that more and more people tend to use fog environments every day in their workplace. Virtualization is an integral part of fog. The purpose of using fog computing systems is to minimize the cost of using a virtual machine by service providers and also to maximize revenue from providing service to consumers' applications. Scheduling is a process that considers several parameters simultaneously to optimize the execution of requests in fog computing networks, such as the queue duration of requests and the speed of virtual machine, and the priority of requests, and these parameters result in the success or failure of a request on virtual machine. In this study, we provided a new method of scheduling using ant colony algorithm, which can perform scheduling and execution of tasks with higher quality.

'''Keywords''': Fog Computing, Virtualization, Virtual Machine, Ant Colony Algorithm

==Introduction==

In the past few years, Cloud computing has provided many opportunities for enterprises by offering their customers a range of computing services. Current “pay-as-you-go” cloud computing model becomes an efficient alternative to owning and managing private data centers for customers facing Web applications and batch processing. Cloud computing frees the enterprises and their end users from the specification of many details, such as storage resources, computation limitation and network communication cost. However, this bliss becomes a problem for latency-sensitive applications. When techniques and devices of IoT are getting more involved in people’s life, current Cloud computing paradigm can hardly satisfy their requirements of mobility support, location awareness and low latency [1].

Fog computing is proposed to address the above network. This computing provides low latency, location awareness, and improves quality-of-services (QoS) for streaming and real time applications. Typical examples include industrial automation, transportation, and networks of sensors and actuators. Moreover, this new infrastructure supports heterogeneity as fog devices include end-user devices, access points, edge routers and switches. The Fog paradigm is well positioned for real time big data analytics, supports densely distributed data collection points, and provides advantages in entertainment, advertising, personal computing and other applications [2].

In summary, cloud computing has the following characteristics:

:* Sensitive data is analyzed on the same source device or transmitter, and of course close to the collection location, which prevents large amounts of data from being sent to the network.

:* Action on data is done in milliseconds.

A specific part of the data will be sent to the fog computing section according to the policies defined. There are many challenges in the design and implementation of Internet systems, IoT devices are constantly creating data, and in most cases, data analysis and processing is urgent. Imagine, for example, if the environment temperature exceeds a certain level, the necessary measures should be taken quickly, or it is possible that the time that is spent to send and analyze data at the computer center brings some costs and risks to user. Considering various types of IoT services, its computational requirements can be classified as following:

:* Very low latency: Data analysis at a location close to sensors 2 and IoT devices will help greatly reduce the amount of latency when executing commands and data analysis.

:* Optimal use of bandwidth: Considering the transmission of large amount of data in such systems, many computation and analyses near the site of producing and collecting data will prevent the transmission of large amount of data on the network, which will also play a significant role in reducing network costs.

:* Reduction in security concerns: Considering the minimal data transmission on the network, there consequently will be fewer security risks to the system.

In fog computing, for proper management of the service provider's resources, we need a load balancing that is suggested to the service provider. Load level meter is mechanized, usually for the maintenance of a service, when one or more components of the set fail. The components are monitored regularly, and when one of the components does not respond, the load balancer increases and does not transmit traffic over it. Suitable level meter at the place of resource consumption can often minimize problems, which not only reduces costs and create green computing, but also keeps the pressure low on unique circuits that can potentially prolong their life. In fact, it can be said that the purpose of load balancing is to find a proper mapping of tasks on the existing processors in the system, so that in each processor, an almost equal amount of tasks is performed, so the total performance time reaches its lowest value. By load balancing, the load can be balanced with dynamic transmission of local workload from one machine to another machine in a remote node or a less-used machine [3]. In order to achieve these goals, we need to use scheduling. In the next sections of the article, we first describe the scheduling, the research background in the field of scheduling is presented, and finally we propose the suggested method along with the evaluation.

==Scheduling==

Given that fog computing has provided a great deal of services, including computing services and high-capacity storage, for the users, users from all over the world are keen to use fog computing technology. Due to the high demands of users, it has to be planned in a way so that all users can access the fog computing environment. Accordingly, in order to get better and fair results for all users to have access to the fog space at a given time, the scheduling algorithm is considered to distribute tasks among the data centers with a given time in order to provide services proper to the needs of users at the optimum time. Scheduling uses different algorithms to distribute tasks among virtual machines. Scheduling in fact divides users' requests with respect to the response time among virtual machines [4].

==Previous works==

There are a variety of scheduling algorithms in distributed systems. The main purpose of scheduling algorithms is to obtain high computational performance and the best system performance power. Traditional task scheduling algorithms are not able to provide scheduling in the fog environment because they have cost overhead and the providers opts for using exploratory or hybrid algorithms. In this section, we evaluate some of scheduling algorithms.

In [5], an improved cost-based algorithm is proposed for task scheduling. This algorithm is proposed to efficiently map tasks to existing resources in fog. The two main phases in this algorithm include the use of an improved bee colony optimization (BCO) algorithm to prioritize tasks and then an algorithm for grouping tasks based on their priority. This scheduling algorithm calculates the cost spent on obtaining resources and the efficiency of the calculations performed to complete the workflow tasks. In this algorithm, the proportion of the cost spent on obtaining resources to the cost of efficient communication for workflow tasks has been remarkably improved.

In [6], a time-cost balancing algorithm is proposed whose function is with respect to the features of fog computing. For example, compressing the workflow to reduce execution time and cost is based on the user input information that the user inputs into the system at any time.

In [7], an exploratory algorithm of workflow scheduling is proposed based on group task optimization. The group task algorithm is inspired by the group behavior of animals, such as the collective movement of birds and fish. Since this algorithm starts with a primary random population matrix, its function is similar to many other evolutionary algorithms such as continuous genetic algorithms and competitive-based algorithms. Unlike the genetic algorithm, the group tasks algorithm does not have any evolutionary operator such as mutation and coupling. The workflow scheduling exploratory algorithm, based on group optimization of tasks in order to optimize group tasks, has been designed based on the exploratory approach of applications and according to available resources in the fog, with the goal of reducing the time spent doing the computations and reducing the data transmission time. The algorithm consists of two main components that include the use of exploratory algorithms to correctly discover the resources, and then the use of group optimization algorithm of tasks to correctly map these resources to the tasks. Experimental results show that the use of this algorithm have led to cost saving and balanced distribution of user volume on resources.

In [8], a workflow scheduling optimization algorithm is presented. This algorithm is presented in order to schedule workflows in the fog environment and its overall structure is based on a tree. This algorithm consists of two main phases: in the first phase, using the resource discovery algorithm, all of the available resources are labeled, and then each of the sources transmits its information to the parent node that is directly connected to it, thereby controlling the resources by any parent node will be easier, then in the second phase, assigning resources to perform workflow tasks is done considering the quality of service determined by the user. In general, this algorithm provides a solution for scheduling workflows, taking into account the QOS factors requested by the user. Using this algorithm, a significant improvement has been observed in using CPU.

A cost improvement algorithm for scheduling workflow in hybrid clouds is presented in [9], with two main steps of the algorithm, selection of tasks, and selection of resources, from the general fog and formation of mixed fog. While the scheduler decides which of the tasks will reduce the execution time using the general fog resources, determining the efficiency and costs of execution plays a major role in new scheduling.

==The suggested method ==

In this research, the ant colony algorithm is used for scheduling. As you know, in the fog data center, virtual machines are placed with different powers and capacities from each other. These differences arise when we give the same tasks to the machines, on the other hand, despite these differences, the tasks tend to move towards high-performance systems. This makes many systems that have good performance to be highly welcomed, resulting in an overload in them, and lower performance systems are not taken into account and remain idle. The result is waste of resources and, consequently, load imbalance reduces the efficiency of the fog data enter.

In the suggested method, the user's tasks are grouped according to the two criteria of minimum cost and the minimum end time service from quality of service parameters. This will reduce the communication cost rate. Grouping will also determine the priority of executing the tasks. So that, in the task group based on the end time of the service, the task with the least end time of service must be implemented first. The list of tasks will be arranged ascending from the lowest to the highest end time. The workflow time for each source can be calculated based on formula (1):
{| class="formulaSCP" style="width: 100%; text-align: center;" 
|-
| <math>TA\, -\, waiting\, time\, for\, virtual\, machine\, +</math><math>\, task\, duration\, .processing\, power\, of\, virtual\, machine\quad \quad \quad \quad \quad \, \, \quad formula\, (1)</math>
|}


After calculating the workflow time for each virtual machine, the virtual machine with the minimum workflow time will be selected and the task will be executed there. Prioritization of tasks based on cost can be calculated according to formula (2):
{| class="formulaSCP" style="width: 100%; text-align: center;" 
|-
| <math>Cost-\, (task\, duration\, /\, processing\, power\, of\, virtual\, machine)\times \, cost\, of\, virtual\, machine\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \, \, formula\, (2)</math>
|}


In this case, the virtual machine with the lowest cost will be selected and tasks will be scheduled until it has a virtual machine. Therefore, the input tasks are categorized based on their types, end time and cost. Then, according to the priority of each task in each group, the task is selected and assigned to the optimum virtual machine obtained from the ant colony algorithm for execution.

Generally, the proposed algorithm process is as following:

In this algorithm, the set of tasks is shown with <math display="inline">T=</math><math>\, \lbrace {T}_{1},{T}_{2},\, \ldots ,{T}_{m}\rbrace</math>  m is total number of tasks, <math display="inline">vm</math> is shown with <math display="inline">vm=</math><math>\, \lbrace {vm}_{1},{vm}_{2},\, \ldots ,{vm}_{n}\rbrace ,</math> n is total number of virtual machines.

First step: The input tasks are categorized based on end time and cost.

Second step: After grouping, the tasks are prioritized based on time and cost; in a way that the tasks with the lowest time has to be scheduled first and the tasks with lower cost has to be executed first.

Step third:

A) Each task has been prioritized based on end time and the ant algorithm is used to select a virtual machine for executing the task as following:

1- A- Producing the ants and assigning the ants randomly to a virtual machine at time zero and calculating the starting pheromone value for each virtual machine based on workflow time of each virtual machine

Formula 3:

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">
<math display="inline">{\tau }_{9}\left( 0\right) -\, waiting\, time\, for\, each\, virtual\, machine\, +</math><math>\, task\frac{duration}{processing}power\, of\, virtual\, machine</math> <math display="inline">formula\, (3)</math></div>

2- A- Ant K selects a task from the list of tasks based on priority and assigns the task to <math display="inline">VMj\,</math> with probability of formula (4). The decision-making mechanism is based on the workflow time.

Formula (4):
{| class="formulaSCP" style="width: 100%; text-align: center;" 
|-
| <math>if\, \, j\in 1,\, \ldots ,\, n\quad \quad \quad \, {\rho }_{j}^{K}=\left\{ \begin{matrix}\frac{{\left[ {\tau }_{j}\left( t\right) \right] }^{\alpha }{\left[ T{A}_{j}\right] }^{\beta }}{\sum _{}^{}{\left[ {\tau }_{j}\left( t\right) \right] }^{\alpha }{\left[ T{A}_{j}\right] }^{\beta }}\\0\end{matrix}\quad \, \, \, \quad \quad \quad \quad formula\, (4)\, \, \right.</math> 
|}
{|class="formulaSCP" style="width: 100%; text-align: center;" 
|-
| <math>Otherwise:\, \,</math> 
|}


<math display="inline">{\tau }_{9}\left( t\right)</math>  Shows the value of pheromone <math display="inline">{VM}_{j}</math> at time t, TA shows the workflow time of virtual machine.

3- A- When each ant finds an optimal solution for each task, the pheromone value of the virtual machine selected by the best ant that has the lowest end time is updated. Since <math display="inline">{\tau }_{j}\left( t\right)</math>  is the intensity of pheromone <math display="inline">VMj</math> at time t. The pheromone is updated according to formula (5):
{| class="formulaSCP" style="width: 100%; text-align: center;" 
|-
| <math>{\tau }_{j}=\left( t+1\right) =\left( 1-\rho \right) \times {\tau }_{j}\left( t\right) +</math><math>\Delta {\tau }_{j}\quad \quad \, \, \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \, \, \quad formula\, (5)</math>
|}


ρϵ(0,1] is reduction factor of pheromone. The highest value per fog is with ρ and the lowest per fog is with value of the pheromone for the previous solution. The value is Δτ<sub>j </sub>per fog showing with the shortest path that has been searched by the kth ant in its replication. Therefore, at the end, the task is assigned to the best and the most proper virtual machine to minimize the workflow time. In this way, the end time of task will be also minimized.

B) Each task has been prioritized based on cost:

The ant algorithm is used to select a virtual machine for executing the task, as following:

:1- B- Producing the ants and assigning the ants randomly to a virtual machine at time zero and calculating the starting pheromone value for each virtual machine based on processing power and cost of each virtual machine based on formula (5):

:2-

<div style="text-align: right; direction: ltr; margin-left: 1em;">
<math display="inline">\Tau j(0)=</math><math>\, (task\, duration/\, processing\, power\, of\, resource)\, \times \, cost\, of\, resource</math>            Formula (5)</div>

2- B- Ant K selects a task from the list of tasks based on priority and assigns the task to VMj with probability of formula (6). The decision-making mechanism is based on the cost.
{| class="formulaSCP" style="width: 100%; text-align: center;" 
|-
| <math>if\, \, j\in 1,\, \ldots ,\, n\quad \quad \quad \, {\rho }_{j}^{K}=\left\{ \begin{matrix}\frac{{\left[ {\tau }_{j}\left( t\right) \right] }^{\alpha }{\left[ T{A}_{j}\right] }^{\beta }}{\sum _{}^{}{\left[ {\tau }_{j}\left( t\right) \right] }^{\alpha }{\left[ T{A}_{j}\right] }^{\beta }}\\0\end{matrix}\quad \quad \right.</math> 
|}
{|class="formulaSCP" style="width: 100%; text-align: center;" 
|-
| <math>Otherwise:</math>
|}


<div style="text-align: right; direction: ltr; margin-left: 1em;">
Formula (6)</div>

3- B- When each ant finds an optimal solution for each task, the pheromone value of the virtual machine selected by the best ant that has the lowest end time is updated. Since <math display="inline">{\tau }_{j}\left( t\right)</math>  is the intensity of pheromone <math display="inline">{VM}_{j}</math> at time t. The pheromone is updated according to formula (4). The rest of the calculations are the same as the previous one. At the end, the virtual machine with the lowest cost is selected, and tasks are scheduled on it until the virtual machine has capacity.

==Results==

In this section, experiments are performed with 10 data centers with 50 virtual machines and 100-1000 tasks under the simulated ifogsim platform. Duration of tasks varies from 1000 to 20000 million instructions. The setting of the fog simulator parameters is shown in Table (1). Several values for each parameter have been investigated by keeping other parameters consonant in order to optimize the task scheduling to the virtual machine.

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">
<span style="text-align: center; font-size: 75%;">Table 1: Configuration Details</span></div>

{| style="width: 66%;margin: 1em auto 0.1em auto;border-collapse: collapse;" 
|-
|  style="border: 1pt solid black;text-align: center;vertical-align: bottom;"|<span style="text-align: center; font-size: 75%;">Duration of tasks 1000-2000</span>
|-
|  style="border: 1pt solid black;text-align: center;vertical-align: bottom;"|<span style="text-align: center; font-size: 75%;">Total number of tasks 100-1000</span>
|-
|  style="border: 1pt solid black;text-align: center;"|<span id='_GoBack'>Number of processors required to execute 1</span>
|-
|  style="border: 1pt solid black;text-align: center;"|<span style="text-align: center; font-size: 75%;">Input file size 300</span>
|-
|  style="border: 1pt solid black;text-align: center;"|<span style="text-align: center; font-size: 75%;">Output file size 300</span>
|-
|  style="border: 1pt solid black;text-align: center;"|<span style="text-align: center; font-size: 75%;">Total number of virtual machines 50</span>
|-
|  style="border: 1pt solid black;text-align: center;"|<span style="text-align: center; font-size: 75%;">500-2000 millions of instructions per second</span>
|-
|  style="border: 1pt solid black;text-align: center;"|<span style="text-align: center; font-size: 75%;">Size of virtual machine image 10000</span>
|-
|  style="border: 1pt solid black;text-align: center;"|<span style="text-align: center; font-size: 75%;">RAM 256-2048</span>
|-
|  style="border: 1pt solid black;text-align: center;"|<span style="text-align: center; font-size: 75%;">Bandwidth 500-1000</span>
|-
|  style="border: 1pt solid black;text-align: center;"|<span style="text-align: center; font-size: 75%;">Number of processors 1-4</span>
|-
|  style="border: 1pt solid black;text-align: center;"|<span style="text-align: center; font-size: 75%;">Scheduling policy of shared place</span>
|-
|  style="border: 1pt solid black;text-align: center;"|<span style="text-align: center; font-size: 75%;">Number of data centers 10</span>
|-
|  style="border: 1pt solid black;text-align: center;"|<span style="text-align: center; font-size: 75%;">Number of host machines 2-6</span>
|-
|  style="border: 1pt solid black;text-align: center;"|<span style="text-align: center; font-size: 75%;">Scheduling policy of shared place and shared time</span>
|}


We used paper [10] to compare. This paper has used the improved ant colony algorithm to schedule tasks. The simulation and comparison results are explained below.

End time is one of the important parameters for quality of service to schedule tasks in fog computing. As there is less end time, the users will wait a short time to get the result of the request in fog. The simulation and comparison result of the proposed method is shown in Figure 1. In this scenario, the size of tasks is fixed and the number of machines in each stage is increased.

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">
 [[Image:Draft_Ghaffari_457888260-chart1.svg|408px]] </div>

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">
<span style="text-align: center; font-size: 75%;">'''Figure 1End time of tasks with variable number of machines'''</span></div>

In the scheduling algorithms, the less response time to tasks, the higher quality the method has. The response time is the time a task waits after entering the system to reach its resources. The number of machines varies and the result is shown in Figure 2.

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">
 [[Image:Draft_Ghaffari_457888260-chart2.svg|420px]] </div>

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">
<span style="text-align: center; font-size: 75%;">'''Figure2: Response time with variable number of machines'''</span></div>

The more balanced the distribution of workload among virtual machines, the better performance the virtual machines will have and, as a result, the lower the response time will be. To determine the load balance among virtual machines, we used the degree of imbalance which is calculated using the following equation.

<div style="text-align: right; direction: ltr; margin-left: 1em;">
{| class="formulaSCP" style="width: 100%; text-align: center;" 
|-
| <math>Degree\, of\, Imbalance=\, \frac{{Execution\, Time}_{max}-\, {Execution\, Time}_{min}\, }{{Execution\, Time}_{Avg}}</math>
|}
</div>

The simulation result for the above criterion is shown in Figure 3.

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">
 [[Image:Draft_Ghaffari_457888260-chart3.svg|438px]] </div>

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">
<span style="text-align: center; font-size: 75%;">'''Figure3: Load distribution in machines'''</span></div>

Reducing energy consumption is one of the most important issues of the day, especially in the industrial sector. In recent years, the human's increasing needs to computer systems have led to more emergence and expansion of data centers with a large number of computers, which have a significant overall power consumption. Obviously, in this condition, many efforts have been made by experts to reduce power consumption in these centers, and now efforts in this regard are of particular importance. One of the ways to reduce power consumption in data centers is virtual machine migration. The energy consumed is the energy consumed by the physical machines that they have consumed after receiving the tasks and executing them as shown in Figure 4. In this figure, the number of machines varies.

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">
 [[Image:Draft_Ghaffari_457888260-chart4.svg|408px]] </div>

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">
<span style="text-align: center; font-size: 75%;">'''Figure3: Comparison of energy consumed'''</span></div>

The simulation and comparison result shows that the proposed method has acceptable performance.

==Conclusion ==

Fog computing provides a virtual collection of resources through the Internet for users. Since the ability and availability of resources varies dynamically, task scheduling is considered as the most challenging issue in fog computing. Hence, in this paper, after introducing the fog computing technology, the issue of scheduling was discussed. In scheduling, there is an appropriate method to assign tasks to machines in the least amount of time and cost; therefore, a method was proposed to group the tasks first, then to select an optimal virtual machine using the ant algorithm.

==References ==

1. Vaquero, L. M., & Rodero-Merino, L. (2014). Finding your way in the fog: Towards a comprehensive definition of fog computing. ''ACM SIGCOMM Computer Communication Review'', ''44''(5), 27-32.

2. Yi, S., Li, C., & Li, Q. (2015, June). A survey of fog computing: concepts, applications and issues. In ''Proceedings of the 2015 workshop on mobile big data'' (pp. 37-42). ACM.

3. Bittencourt, L. F., Diaz-Montes, J., Buyya, R., Rana, O. F., & Parashar, M. (2017). Mo

4. Gupta, H., Vahid Dastjerdi, A., Ghosh, S. K., & Buyya, R. (2017). iFogSim: A toolkit for modeling and simulation of resource management techniques in the Internet of Things, Edge and Fog computing environments. ''Software: Practice and Experience'', ''47''(9), 1275-1296.

5. Cardellini, V., Grassi, V., Presti, F. L., & Nardelli, M. (2015, July). On QoS-aware scheduling of data stream applications over fog computing infrastructures. In ''Computers and Communication (ISCC), 2015 IEEE Symposium on'' (pp. 271-276). IEEE.

6. Pham, X. Q., & Huh, E. N. (2016, October). Towards task scheduling in a cloud-fog computing system. In ''Network Operations and Management Symposium (APNOMS), 2016 18th Asia-Pacific'' (pp. 1-4). IEEE.

7. Bitam, S., Zeadally, S., & Mellouk, A. (2018). Fog computing job scheduling optimization based on bees swarm. ''Enterprise Information Systems'', ''12''(4), 373-397.

8. Yin, L., Luo, J., & Luo, H. (2018). Tasks scheduling and resource allocation in fog computing based on containers for smart manufacture. ''IEEE Transactions on Industrial Informatics''.

9. Wan, J., Chen, B., Wang, S., Xia, M., Li, D., & Liu, C. (2018). Fog Computing for Energy-aware Load Balancing and Scheduling in Smart Factory. ''IEEE Transactions on Industrial Informatics''.

10. Dam, S., Mandal, G., Dasgupta, K., & Dutta, P. (2018). An Ant-Colony-Based Meta-Heuristic Approach for Load Balancing in Cloud Computing. In ''Applied Computational Intelligence and Soft Computing in Engineering'' (pp. 204-232). IGI Global.