An Evolutionary Multi-objective Optimization Technique to Deploy the IoT Services in Fog-enabled Networks: An Autonomous Approach

Figures & data

Figure 1. Cloud-Fog-IoT three-layer ecosystem architecture.

Figure 2. Some advantages of fog calculations.

Table 1. Description of the symbols related to the problem of services placement

Parameter	Description	Parameter	Description
$t$	Current time	$R_{A^k}$	Request time of $A_k$
$\rho$	Time period	$x_{a^l}^{f^j}$	Decision variables related to $f^j$ and $a^l$
$n$	Total number of colonies	$x_{a^l}^O$	Decision variables related to orchestration and $a^l$
$F^i$	$i$ ^th fog colony	$x_{a^l}^N$	Decision variables related to nearest colony and $a^l$
$O^i$	$i$ ^th fog orchestration control node	$K$	Total number of services
$f^j$	$j$ ^th fog node	$C$	Total number of resources available in the period $\rho$
$Res\left(F^i\right)$	Set of subordinate fog nodes in $F^i$	$UF$	utilization of fog
$Re{s}^{a^l}\left(F^i\right)$	set of fog nodes associated with $a^l$ in $F^i$	$TP$	Throughput
$AP$	Set of requested applications	$RT$	Response time
$A^k$	$k$ ^th application/request	$SC$	Service cost
$m$	Total number of applications	${\xi }_{UF}$	Utilization of fog weight
$r^k$	Number of services in $A_k$	${\xi }_{TP}$	Throughput weight
$a^l$	$l$ ^th service of an application	${\xi }_{RT}$	Response time weight
$U_{F^i}$	CPU usage rate of $F^i$	${\xi }_{SC}$	Service cost weight
$M_{F^i}$	RAM usage rate of $F^i$	$x_{a^l}^{f^j}$	Decision variable for node $f^j$
$S_{F^i}$	Storage usage rate of $F^i$	$x_{a^l}^O$	Decision variable for orchestration node
$U_{f^j}$	CPU usage rate of $f^j$	$x_{a^l}^N$	Decision variable for nearest neighbor colony
$M_{f^j}$	RAM usage rate of $f^j$	$Sr{v}_D$	Number of services deployed before the deadline
$S_{f^j}$	Storage usage rate of $f^j$	$Sr{v}_{TD}$	All services sent to fog colony
$U_{a^l}$	CPU usage rate of $a^l$	$Cos{t}_{Sr{v}_D}$	Cost of services related to $Sr{v}_{TD}$
$M_{a^l}$	RAM usage rate of $a^l$	$W{T}_{a^l}$	Waiting time for service deployment $a^l$
$S_{a^l}$	Storage usage rate of $a^l$	$E{C}_{a^l}$	Execution time for service $a^l$
$D_{a^l}$	Deadline of $a_l$	$S{C}_{comm}$	Communication cost
$D_{A^k}$	Deadline of $A^k$	$S{C}_{comp}$	Computing cost
$l^{f^j}$	Latency between $f^j$ and $O^i$	$c{v}_{\alpha ,\beta }$	Data size between requests $t_{\alpha }$ and $t_{\beta }$
$l^N$	Link latency of a colony with the nearest colony	$BW$	Bandwidth between two nodes
$l^R$	Link latency between the middleware and cloud	$CP$	Communication unit price
$R{T}_{A^k}$	Response time of $A_k$	$PP$	Computing unit price

Table 2. A summary of the approaches examined

Authors	Optimization type	Utilization of resource	Response time	Cost	Latency	QoS	Throughput	Deadline	Energy	Two-level
Minh et al. (2017)	Single objective	✓	×	×	×	×	×	×	×	×
Ramirez et al. (2017)	Single objective	×	✓	×	×	×	×	×	✓	×
Skarlat et al. (2017)	Single objective	✓	×	×	×	×	×	×	×	×
Mahmoud et al. (2018)	Single objective	×	×	×	×	×	✓	×	✓	×
Yousefpour et al. (2018)	Single objective	×	✓	×	×	×	×	×	×	×
Souza et al. (2018)	Single objective	✓	✓	×	×	×	×	×	×	×
Kim and Chung (2018)	Single objective	×	×	×	×	×	×	×	✓	×
Santoyo-Gonzalez and Cervello-Pastor (2018)	Single objective	×	×	✓	×	×	×	✓	×	×
Jia et al. (2018)	Single objective	×	×	✓	×	✓	✓	×	×	×
Yang et al. (2018)	Single objective	×	✓	×	×	×	×	×	✓	×
Zhang, Wang, and Huang (2018)	Multi-objective	×	✓	×	×	×	✓	×	×	×
Brogi et al. (2018)	Multi-objective	✓	×	✓	×	✓	×	×	×	×
Yousefpour et al. (2019)	Single objective	×	×	✓	✓	×	×	×	×	×
Hassan, Azizi, and Shojafar (2020)	Single objective	×	✓	×	×	×	×	×	✓	×
Murtaza et al. (2020)	Single objective	×	✓	×	×	×	×	×	✓	×
Xavier et al. (2020)	Single objective	✓	✓	×	×	×	×	×	×	×
Chen et al. (2020)	Single objective	✓	✓	×	×	×	×	×	×	×
Khosroabadi, Fotouhi-Ghazvini, and Fotouhi (2021)	Multi-objective	✓	✓	✓	✓	×	✓	×	×	×
Natesha and Guddeti (2021)	Multi-objective	✓	✓	✓	×	×	×	✓	✓	✓
Salimian, Ghobaei‐Arani, and Shahidinejad (2021)	Multi-objective	✓	✓	✓	✓	×	✓	✓	×	×
Proposed approach	Multi-objective	✓	✓	✓	✓	×	✓	✓	×	×

Figure 3. Taxonomy of services placement problem.

Figure 4. Proposed ecosystem framework with three layers of cloud-fog-IoT.

Figure 4. Continued.

Table

Algorithm 1. Pseudocode of the proposed framework
	Input: Set of IoT services requested for $A_k$ and details of fog nodes
	Output: Services deployment planning
1:	for	each time period $\rho$ in MADE-k model do
2:		for	each set of application $A_k$ at time period $\rho$ do
3:			Monitor (set of IoT services requested for $A_k$).
4:			Monitor ($U_{a_l}$, $M_{a_l}$, $S_{a_l}$, $D_{a_l}$).
5:		end
6:		for	each fog node $f^j$ in $F^i$ at time period $\rho$ do
7:			Monitor ($f^j$ status in $F^i$ at time period $\rho$).
8:			Monitor ($U_{f^j}$, $M_{f^j}$, $S_{f^j}$, $D_{f^j}$).
9:		end
10:		for	each set of application $A_k$ at time period $\rho$ do
11:			Calculate the priority of IoT services with Eq. (1)(1) $P\left(A_k\right)=\alpha \times \frac{1}{D_{A_k}}+\left(1-\alpha \right)\times \frac{1}{t-R_{A_k}}$(1) .
12:		end
13:		for	each set of application $A_k$ at time period $\rho$ do
14:			Using PSO to determine a deployment plan to map fog nodes to IoT services. // Deployment planning is based on service priority and monitoring of fog nodes.
15:		end
16:		for	each set of application $A_k$ at time period $\rho$ do
17:			Perform IoT services placement on fog nodes based on deployment plan for $A_k$.
18:		end
19:	end
20:	Planning the deployment of IoT services created by the PSO algorithm.

Table 3. Description of the symbols related to the PSO algorithm

Description	Parameter	Description	Parameter
$N_P$	Population size	$x_{min}$	Lower bound of position
$Ite{r}_{max}$	Maximum iteration	$x_{max}$	Upper bound of position
$pbes{t}_i$	Local best position of $i$ ^th particle	$v_{min}$	Lower bound of velocity
$gbest$	Global best position of all particles	$v_{max}$	Upper bound of velocity
$X_i$	Position vector	$c_1$ and $c_2$	Acceleration constants
$V_i$	Velocity vector	$r_1$ and $r_2$	Random values in $\left[0,1\right]$ range
$\omega$	Inertia weight to control the velocity impact	$\tau$	Iteration

Table 4. Fog colony structure and the IoT services requested for the first scenario

Characteristic	Value
Number of types of services supported in the fog colony	20
Number of resource blocks for each fog node	Random between 5500 and 6000
Number of resource blocks for each service	Random between 25 and 35
Cost of each service	Random between 10 and 20
Number of fog colony nodes	15
The range of the number of services requested in a time period	{50, 100, 150, 200, 250, 300, 350, 400, 450, 500}

Figure 5. An example of a solution structure in the PSO algorithm.

Table 5. Fog colony structure and the IoT services requested for the second scenario

Characteristic	Value
Number of types of services supported in the fog colony	20
Number of resource blocks for each fog node	Random between 3000 and 3500
Number of resource blocks for each service	Random between 5 and 15
Cost of each service	Random between 5 and 15
Number of fog colony nodes	5
Number of services requested to fay colony (random selection)	Period $\rho$	1	2	3	4	5	6	7	8	9	10
	Time $t$	8	16	24	32	40	48	56	64	72	80
	Number of services	71	48	48	46	96	77	37	52	85	55

Table 6. Details of resources for fog nodes

Fog node type	CPU (MIPS)	RAM (MB)	Storage (MB)
Fog node 1	100–200	256	256
Fog node 2	200–300	512	512
Fog node 3	300–1400	1024	1024
Fog node 4	1400–1600	2048	2048
Fog node 5	1600–3000	4096	4096

Table 7. Details of resources for different types of services

Service	CPU (MIPS)	RAM (MB)	Storage (MB)
Service type 1	100–200	128	128
Service type 2	200–300	256	256
Service type 3	300–1400	512	512
Service type 4	1400–1600	1024	2048
Service type 5	1600–3000	4096	4096

Figure 6. Comparison results of different algorithms based on convergence speed for one period.

Figure 7. Comparison results of different algorithms based on runtime for one period.

Figure 8. Comparison results of different algorithms based on the fitness function for one period.

Figure 9. Comparison results of different algorithms based on the number of services performed before the deadline for 10 periods.

Figure 10. Comparison results of different algorithms based on the runtime for 10 periods.

Figure 11. Comparison results of different algorithms based on the average waiting time before the deadline for 10 periods.

Figure 12. Comparison results of different algorithms based on the number of failed services for 10 periods.

Figure 13. Comparison results of different algorithms based on the fitness function for 10 periods.

Figure 14. Comparison results of different algorithms based on the average fitness function after the end of 10 periods.

Table 8. Comparison results of different algorithms based on the number of remaining services for planning in the 11^th period

Algorithms	Total services monitored in fog	Services performed up to 10^th period	Number of services failed	Remaining services for the 11^th period
PSO	615	585	28	2
COA	615	461	141	13
ODMA	615	577	36	2
WOA	615	572	41	2
CSA	615	572	41	2

Table 9. Summary of results of different algorithms

Evaluation metric	PSO	COA	ODMA	WOA	CSA
Number of monitored services	615	615	615	615	615
Average runtime (s)	7.50	34.11	8.16	8.42	8.91
Number of services performed (%)	95.12	74.96	93.82	93.01	93.01
Average waiting time (s)	5.37	10.74	5.48	5.54	5.64
Failed services (%)	4.55	22.93	4.23	6.67	6.67
Remaining services (%)	0.33	2.11	0.33	0.33	0.33
Cost services	327	248	322	319	319

Minh, Q. T., D. T. Nguyen, A. Van Le, H. D. Nguyen, and A. Truong (2017, November). Toward service placement on fog computing landscape. In 2017 4th NAFOSTED conference on information and computer science, Hanoi, Vietnam, (pp. 291–96). IEEE.

 Google Scholar

Ramírez, W., X. Masip-Bruin, E. Marin-Tordera, V. B. C. Souza, A. Jukan, G. J. Ren, and O. G. de Dios. 2017. Evaluating the benefits of combined and continuous Fog-to-Cloud architectures. Computer Communications 113:43–52. doi:10.1016/j.comcom.2017.09.011.

 Web of Science ®Google Scholar

Skarlat, O., M. Nardelli, S. Schulte, M. Borkowski, and P. Leitner. 2017. Optimized IoT service placement in the fog. Service Oriented Computing and Applications 11 (4):427–43. doi:10.1007/s11761-017-0219-8.

 Web of Science ®Google Scholar

Mahmoud, M. M., J. J. Rodrigues, K. Saleem, J. Al-Muhtadi, N. Kumar, and V. Korotaev. 2018. Towards energy-aware fog-enabled cloud of things for healthcare. Computers & Electrical Engineering 67:58–69. doi:10.1016/j.compeleceng.2018.02.047.

 Web of Science ®Google Scholar

Yousefpour, A., G. Ishigaki, R. Gour, and J. P. Jue. 2018. On reducing IoT service delay via fog offloading. IEEE Internet of Things Journal 5 (2):998–1010. doi:10.1109/JIOT.2017.2788802.

 Web of Science ®Google Scholar

Souza, V. B., X. Masip-Bruin, E. Marín-Tordera, S. Sànchez-López, J. Garcia, G. J. Ren, A. J. Ferrer, and A. Juan Ferrer. 2018. Towards a proper service placement in combined Fog-to-Cloud (F2C) architectures. Future Generation Computer Systems 87:1–15. doi:10.1016/j.future.2018.04.042.

 Web of Science ®Google Scholar

Kim, W.-S., and S.-H. Chung. 2018. User-participatory fog computing architecture and its management schemes for improving feasibility. IEEE Access 6:20262–78. doi:10.1109/ACCESS.2018.2815629.

 Web of Science ®Google Scholar

Santoyo-González, A., and C. Cervelló-Pastor. 2018. Latency-aware cost optimization of the service infrastructure placement in 5G networks. Journal of Network and Computer Applications 114:29–37. doi:10.1016/j.jnca.2018.04.007.

 Web of Science ®Google Scholar

Jia, B., H. Hu, Y. Zeng, T. Xu, and Y. Yang. 2018. Double-matching resource allocation strategy in fog computing networks based on cost efficiency. Journal of Communications and Networks 20 (3):237–46. doi:10.1109/JCN.2018.000036.

 Web of Science ®Google Scholar

Yang, Y., S. Zhao, W. Zhang, Y. Chen, X. Luo, and J. Wang. 2018. DEBTS: Delay energy balanced task scheduling in homogeneous fog networks. IEEE Internet of Things Journal 5 (3):2094–106. doi:10.1109/JIOT.2018.2823000.

 Web of Science ®Google Scholar

Zhang, B., X. Wang, and M. Huang. 2018. Multi-objective optimization controller placement problem in internet-oriented software defined network. Computer Communications 123:24–35. doi:10.1016/j.comcom.2018.04.008.

 Web of Science ®Google Scholar

Brogi, A., S. Forti, and A. Ibrahim (2018, March). Optimising QoS-assurance, resource usage and cost of fog application deployments. In International Conference on Cloud Computing and Services Science (pp. 168–89). Springer, Cham.

 Google Scholar

Yousefpour, A., A. Patil, G. Ishigaki, I. Kim, X. Wang, H. C. Cankaya, J. P. Jue, W. Xie, and J. P. Jue. 2019. FOGPLAN: A lightweight QoS-aware dynamic fog service provisioning framework. IEEE Internet of Things Journal 6 (3):5080–96. doi:10.1109/JIOT.2019.2896311.

 Web of Science ®Google Scholar

Hassan, H. O., S. Azizi, and M. Shojafar. 2020. Priority, network and energy-aware placement of IoT-based application services in fog-cloud environments. IET Communications 14 (13):2117–29. doi:10.1049/iet-com.2020.0007.

 Web of Science ®Google Scholar

Murtaza, F., A. Akhunzada, S. Ul Islam, J. Boudjadar, and R. Buyya. 2020. QoS-aware service provisioning in fog computing. Journal of Network and Computer Applications 165:102674. doi:10.1016/j.jnca.2020.102674.

 Web of Science ®Google Scholar

Xavier, T. C. S., I. L. Santos, F. C. Delicato, P. F. Pires, M. P. Alves, T. S. Calmon, A. C. Oliveira, and C. L. Amorim. 2020. Collaborative resource allocation for Cloud of Things systems. Journal of Network and Computer Applications 159:102592. doi:10.1016/j.jnca.2020.102592.

 Web of Science ®Google Scholar

Chen, Y., Z. Li, B. Yang, K. Nai, and K. Li. 2020. A Stackelberg game approach to multiple resources allocation and pricing in mobile edge computing. Future Generation Computer Systems 108:273–87. doi:10.1016/j.future.2020.02.045.

 Web of Science ®Google Scholar

Khosroabadi, F., F. Fotouhi-Ghazvini, and H. Fotouhi. 2021. SCATTER: service placement in real-time fog-assisted IoT networks. Journal of Sensor and Actuator Networks 10 (2):26. doi:10.3390/jsan10020026.

 Web of Science ®Google Scholar

Natesha, B. V., and R. M. R. Guddeti. 2021. Adopting elitism-based Genetic Algorithm for minimizing multi-objective problems of IoT service placement in fog computing environment. Journal of Network and Computer Applications 178:102972. doi:10.1016/j.jnca.2020.102972.

 Web of Science ®Google Scholar

Salimian, M., M. Ghobaei‐Arani, and A. Shahidinejad. 2021. Toward an autonomic approach for Internet of Things service placement using gray wolf optimization in the fog computing environment. Software: Practice and Experience 51 (8):1745-1772.

 Web of Science ®Google Scholar