# Security and Makespan Trade-Off Strategy in Fog-Enabled IoT Networks

Authors: Xiaoli Wang; Bharadwaj Veeravalli; Yulong Tan; Zhihao Tong
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Fog computing relieves the Internet of Things (IoT) from a heavy burden of workload computation, consequently minimizes workload makespan, and reduces the considerable energy consumption of IoT devices. However, the fog-enabled IoT poses a risk to data security due to the intrinsic open and distributed structure of the fog. Hence, it is imperative to search for an optimal scheduling strategy on fog nodes to minimize workload makespan, while guaranteeing high data security. In this study, we investigate the trade-off between security and makespan and propose a multiobjective optimization model to optimize them simultaneously. To achieve this goal, we design an evolutionary algorithm together with two effective measures to handle large-scale partitionable workloads: a conflict-free multi-installment scheduling (ConfMIS) strategy as well as a security criterion based on Eigenvector centrality measure. Experimental results show that the proposed algorithm can generate a set of widely spread and uniformly distributed solutions in the decision space. Among these representative solutions, system designers/decision-makers can choose their favorite one based on specific IoT application demands.


---

## Body

## 1. Introduction

Along with other emerging technologies such as AI, the IoT has been regarded as an indispensable part of the Fourth Industrial Revolution [1]. Making use of web-enabled sensors, processors, and communication hardware, the IoT touches and enables nearly every industry, including telemedicine, automated manufacturing, diverse retail, distance learning, smart home, etc. Trends indicate that IoT use is both rapidly diversifying and becoming more commonplace.The IoT is not just about connected sensors and devices—it is about the data those devices collect from their environments and especially the powerful information derived from that data after deep processing. As the majority of IoT devices are incapable of intensive computation due to their restricted hardware and limited battery life, they generally analyze partial data locally, while sending the remaining to the cloud or fog for intensive processing. Compared to the cloud, in recent years, fog computing is becoming increasingly preferable in undertaking IoT workloads [2]. This is because cloud computing is usually situated remotely and thus usually costs excessive bandwidth usage to communicate, resulting easily in unbearable long latency [3]. By contrast, fog computing provides services of computation at the proximity of IoT sensors, so it is more convenient for fog nodes to collect data from sensors and feedback results. By taking full advantage of fog computing, the IoT gets relieved from a heavy burden of workload computation and hence saves considerable energy consumption of IoT devices. For example, wearable devices, the future of healthcare, are electronics physically worn by individuals to track and analyze biometric data from heart rate to sleep patterns. Wearable devices can notify doctors of the emergency of patients, so that they can assist patients timely. Thus, rapid data processing and useful information feedback become particularly essential in biomedical applications, while putting a major challenge considering the energy shortage of battery-powered wearable devices. Works in [4] revealed that transferring the complex and energy-consuming machine-learning computations to fog computing can significantly reduce the energy consumption of wearable devices and speed up workload computation.It is referred to as fog-enabled IoT in this study for the kind of IoT that offloads computational workloads on fog computing to alleviate its energy-consumption stress and minimize workload makespan. Other research available also calls it fog-aided IoT [5], fog computing empowered IoT [6], or fog supporting IoT [7]. Existing works in the domain of fog-enabled IoT mainly studied optimal workload offloading decisions or optimal task scheduling strategies for the purpose of minimizing workload makespan to meet IoT applications’ real-time requirements.Authors in literature [8] optimize workload offloading decisions by investigating the trade-off between workload makespan and energy consumption. The offloading problem is modeled as a mixed-integer nonlinear program and solved by a suboptimal algorithm based on artificial intelligent algorithms. Work [9] pointed out that the offloading decision is affected by the environment’s current dynamics as well since other IoT users are also competing to maximize their resource utilization. Hence, the competition between makespan and energy consumption is modeled as a game where IoT devices' decision for the optimal distribution of tasks is captured in a joint optimization problem. Similarly, two distributed fog resource allocation algorithms are developed in reference [10] to deploy offloading solutions efficiently in cases of resource competition. Besides, the uncertainty caused by the channel measurements is considered in reference [11], based on which the offloading problem is transformed into a mixed-integer nonlinear programming problem and is solved by applying Benders decomposition to find an optimal offloading solution. Literature [12] studied how to dynamically adapt the placement of IoT applications running on the fog, depending on application needs and evolution of resource usage. In reference [13], an optimal task allocation in the fog is investigated to minimize the makespan of workloads under the constraint of IoT device's battery capacity and each workload's completion deadline. An application placement technique based on a memetic algorithm is proposed in reference [14] to minimize the execution time and energy consumption of IoT applications, and a batch application placement decision for concurrent IoT applications is obtained. In reference [15], a distance-aware, occurrence-aware, and task-property-aware volatile upper confidence bound algorithm is designed to minimize the long-term delay of task offloading. Authors in reference [16] developed an energy-optimal dynamic offloading scheme to minimize energy consumption when workloads are accomplished within a desired energy overhead and delay.However, previously mentioned methods may suffer from the following two major limitations concerning the specific architecture of fog-enabled IoT: on the one hand, fog computing consists of a wide variety of computational devices, referred to as fog nodes, such as routers, gateways, access points, base stations, and speciﬁc fog servers. As an open structure, fog nodes are geographically distributed and widely scattered in complex network environments, while forming into an expanded attack surface, which reveals underlying security vulnerabilities of the nodes. Hence, for the sake of security, workloads should be scheduled to nodes with high security as much as possible, that is, nodes with less possibility of being attacked by hackers. However, this objective of high security may conflict with the objective of minimum makespan. To achieve the latter objective, we tend to schedule workloads on fog nodes with high performance, including high-speed computing capability and strong network connectivity. Those nodes are happened to be the preferable ones for cyber hackers. Therefore, it is necessary to study the trade-off between data security and the makespan of workloads. Unfortunately, to the best of our knowledge, no studies available have systematically explored this issue. In this study, we focus on the two conflicting objectives and propose a multiobjective optimization model to optimize them simultaneously. With this model, we design an evolutionary algorithm to obtain a set of representative solutions for decision-makers to choose according to each IoT application’s practical needs.On the other hand, IoT sensors may collect data intermittently over several periods, so the data involved in workload computation could be transferred discontinuously to the fog. If the fog layer waits until all required data finish uploaded and then starts computing, then it inevitably results in a significant waste of time. Therefore, the discontinuity feature of IoT data should be carefully considered in the design of task-scheduling strategies on the fog. With this in mind, in this study, we design a conflict-free multi-installment scheduling (ConfMIS) strategy. It distributes load fractions to fog nodes in several installments instead of solely one time, which applies to the data characteristics of IoT applications. Moreover, in order to minimize the makespan of workloads, the ConfMIS strategy compacts scheduling installments as much as possible but without time conflicts between any two installments.The ConfMIS strategy divides the scheduling process into two parts: the internal installments and the last installment. In order to simplify the scheduling process, every internal installment is set to be uniform, that is, an identical amount of load is distributed in every installment, while the last installment is designed to make sure all fog nodes involved in workload computation finish computing at the same time. The ConfMIS strategy is different from existing periodic multi-installment scheduling (PMIS) strategies [17, 18]. As for PMIS, the total load fraction assigned to fog nodes in the last installment is forced to be identical to that in each internal installment, which may give rise to time conflicts between the last installment and the last but one. We shall demonstrate the existence of time conflicts for PMIS with an example in this study. By contrast, the ConfMIS strategy avoids time conflicts by subtly adjusting workload assignments between internal installments and the last installment.The remainder of this study is structured as follows: in Section2, the task-scheduling problem in a fog-enabled IoT system is formulated, with which we propose a multiobjective optimization model. In Section 3, we introduce a multi-installment scheduling strategy ConfMIS to obtain an optimal makespan of workloads. To solve the proposed model, Section 4 presents an evolutionary algorithm based on decomposition, which is evaluated in Section 5. Finally, the study concludes in Section 6.


## 2. Task-Scheduling Problem on Fog-Enabled IoT

A fog-enabled IoT system composed ofN heterogeneous fog nodes, denoted as F=f1,f2,…,fN, is considered, as shown in Figure 1. They are connected by physical or virtual communication links, denoted as adjacency matrix MN×N, where each entry mij flags whether there exists a connection between fog nodes fi and fj in the network. Let ℋ be the size of workload transferred from IoT to the fog. It shall be divided into small load fractions and distributed to n fog nodes, denoted as P=p1,p2,…,pn, to finish computing. Certainly, not all fog nodes available are supposed to get involved in workload computation. Hence, we have n<N and P∈F. The challenge is to determine which fog nodes should be selected to accomplish workload computation (node selection scheme) and how to partition the workload into load fractions and efficiently distribute them on the selected fog nodes (load scheduling scheme), so that the data security S and the makespan T of the workload could strike a trade-off (be optimized to the maximum).Figure 1
Hierarchical network of fog-enabled IoT.In this section, we first propose a multi-installment scheduling strategy ConfMIS to obtain the makespanT of the workload and then introduce a security criterion based on Eigenvector centrality to show how data security S is measured in this study. Based on this, a multiobjective optimization model is given at the end of this section.


### 2.1. MakespanT

Figure2 illustrates the scheduling process of ConfMIS strategy. As can be seen, there are m installments in total, which are divided into two parts: (m−1 identical internal installments and the last installment. In each internal installment, an identical amount of load V is distributed and completed among n fog nodes. The last installment differs from internal ones because it is responsible for guaranteeing that all nodes stop computing at the same time, so that the makespan could be minimized. The last installment completes hV size of workload, where h is a real number satisfying h>1. Since m−1V+hV=ℋ, we have V=ℋ/m+h−1.Figure 2
The Gantt chart of ConfMIS.The master sends chunkαiV and βiV to fog node pi with i=1,2,…,n in each internal installment and the last installment, respectively. We have αi>0, βi>0, and ∑i=1nαi=∑i=1nβi=1. It takes the master time oi+ziαiV to transmit chunk αiV to node pi and costs node pi time si+wiαiV to finish computing this chunk, where oi and si are communication and computation start-up overheads, respectively, while wi represents the ratio of the time taken by node pi to compute a given workload to that by a standard fog node, and zi is the reciprocal of network transmission speed between the master and fog node pi. The overall makespan is determined by the last fog node to finish its assigned chunk, which is equal to the finish time of the last installment since all fog nodes stop computing at the same instant. By observing Figure 2, we can obtain the function of makespan T as follows:(1)TP=m−1α1ℋm+h−1w1+s1+o1+β1hℋm+h−1w1+s1.The makespanT depends on the node selection scheme and the load scheduling scheme. The former determines which fog nodes are selected to participate in workload computation, while the latter is an optimal solution to scheduling strategy ConfMIS. This solution includes optimal load partitions for internal installments and the last installment, an optimal number of installments, and a feasible value for h, which represents how large proportion of workloads the last installment completes compared to each internal installment. We shall further demonstrate in Section 3 that given a node selection scheme P, the load scheduling scheme (an optimal solution to ConfMIS strategy) can be obtained. Hence, the function of makespan T involves only one set of variables, that is node selection scheme P.


### 2.2. SecurityS

Since fog nodes are heterogeneous and widely scattered in a complex network environment, they form into an expanded attack surface, which reveals underlying security vulnerabilities. Hence, for the sake of data security, workloads ought to be primarily scheduled on fog nodes with high security, that is, nodes with less possibility of being attacked by hackers. To measure the vulnerability of fog nodes, we introduce the concept of node centrality.Node centrality is the term used to describe how important a node is within a network. In the context of security, it means how favorable a node is for hackers. The node centrality is often calculated by simply counting the number of links in and out of each node in the network (degree centrality), by measuring how short the shortest paths are from one node to the others (closeness centrality) or calculating how often a node lies on the shortest path between other nodes (betweenness centrality). These centrality measures are useful in some cases, but they rely heavily on the degree of nodes and do not consider each node’s relationship with other important nodes. For example, if one fog node with high centrality in the network has a high possibility of getting attacked, then nodes in its neighborhood should also be ranked with a relatively high centrality value due to the continuity of attacks. Eigenvector centrality is a measure of the influence of a node in a network. It holds the idea that connections to high-scoring nodes contribute more to the score of the node than that to low-scoring nodes.The Eigenvector centrality of a fog nodefi is given by the following equation:(2)ci=vfi,where vector v is the eigenvector of unit length corresponding to the largest eigenvalue of the adjacency matrix MN×N of the network and vfi is the i-th entry of vector v. Hence, one could determine the Eigenvector centrality of every fog node by just computing this eigenvector v.Figure3 shows a network that contains two local substructures—a hierarchy and a core-periphery, with one connection linking them. We calculate the degree centrality, betweenness centrality, closeness centrality, and Eigenvector centrality and compare them in Table 1. As can be seen, node 8 has the highest Eigenvector centrality value, followed by nodes 9 and 10. Although node 1 connects the complete hierarchy of the left subnetwork, its Eigenvector centrality is smaller than node 8, which connects the right subnetwork. In comparison to the degree centrality, in which nodes 8 and 9 have equal degree centrality values, here since node 8 is connected to nodes that are “more connected” and thus more important, and since node 9 is connected to isolated node 12, node 8 has a higher Eigenvector centrality value. As for the betweenness centrality and closeness centrality, node 13 is considered more important than node 8. This is a result of the fact that all the paths between the left and the right subnetworks must pass through node 13.Figure 3
An example of Eigenvector centrality.Table 1
Comparison among different centrality measures.
NodeDegree centralityBetweenness centralityCloseness centralityEigenvector centrality130.2556820.4444440.239731230.1193180.3529410.144301330.1193180.3529410.144301410.0000000.2666670.058403510.0000000.2666670.058403610.0000000.2666670.058403710.0000000.2666670.058403830.1818180.3870970.510702930.0625000.3157890.4790571030.0625000.3157890.4790571110.0000000.2448980.1938881210.0000000.2448980.1938881320.1988640.4285710.303722Assume that onlyn fog nodes P=p1,p2,…,pn are selected to take part in workload computation, we define the security of node selection scheme P as follows:(3)SP=n∑i=1ncj|pi=fj,j∈1,N=n∑i=1nvpi.


### 2.3. Multiobjective Optimization Model

Based on the above analysis on security and makespan functions, we propose a multiobjective optimization model as follows:(4)minPTP=m−1α1ℋm+h−1w1+s1+o1+β1hℋm+h−1w1+s1,minP1SP=1n∑i=1nvpi.Here, P=p1,p2,…,pn∈F=f1,f2,…,fN.There are two objectives considered in our model, where functionTP refers to makespan minimization, while function 1/SP represents the reciprocal of security maximization. This model optimizes data security and makespan simultaneously. It involves only one set of variables, that is, the node selection scheme P. This is because once P is given, an optimal workload scheduling scheme can be obtained by ConfMIS strategy. We shall illustrate in the next section how ConfMIS strategy works and how to derive its solution, including optimal load partitions α1 and β1, optimal number m of installments, and a feasible value for h, which are involved in the proposed model.


## 2.1. MakespanT

Figure2 illustrates the scheduling process of ConfMIS strategy. As can be seen, there are m installments in total, which are divided into two parts: (m−1 identical internal installments and the last installment. In each internal installment, an identical amount of load V is distributed and completed among n fog nodes. The last installment differs from internal ones because it is responsible for guaranteeing that all nodes stop computing at the same time, so that the makespan could be minimized. The last installment completes hV size of workload, where h is a real number satisfying h>1. Since m−1V+hV=ℋ, we have V=ℋ/m+h−1.Figure 2
The Gantt chart of ConfMIS.The master sends chunkαiV and βiV to fog node pi with i=1,2,…,n in each internal installment and the last installment, respectively. We have αi>0, βi>0, and ∑i=1nαi=∑i=1nβi=1. It takes the master time oi+ziαiV to transmit chunk αiV to node pi and costs node pi time si+wiαiV to finish computing this chunk, where oi and si are communication and computation start-up overheads, respectively, while wi represents the ratio of the time taken by node pi to compute a given workload to that by a standard fog node, and zi is the reciprocal of network transmission speed between the master and fog node pi. The overall makespan is determined by the last fog node to finish its assigned chunk, which is equal to the finish time of the last installment since all fog nodes stop computing at the same instant. By observing Figure 2, we can obtain the function of makespan T as follows:(1)TP=m−1α1ℋm+h−1w1+s1+o1+β1hℋm+h−1w1+s1.The makespanT depends on the node selection scheme and the load scheduling scheme. The former determines which fog nodes are selected to participate in workload computation, while the latter is an optimal solution to scheduling strategy ConfMIS. This solution includes optimal load partitions for internal installments and the last installment, an optimal number of installments, and a feasible value for h, which represents how large proportion of workloads the last installment completes compared to each internal installment. We shall further demonstrate in Section 3 that given a node selection scheme P, the load scheduling scheme (an optimal solution to ConfMIS strategy) can be obtained. Hence, the function of makespan T involves only one set of variables, that is node selection scheme P.


## 2.2. SecurityS

Since fog nodes are heterogeneous and widely scattered in a complex network environment, they form into an expanded attack surface, which reveals underlying security vulnerabilities. Hence, for the sake of data security, workloads ought to be primarily scheduled on fog nodes with high security, that is, nodes with less possibility of being attacked by hackers. To measure the vulnerability of fog nodes, we introduce the concept of node centrality.Node centrality is the term used to describe how important a node is within a network. In the context of security, it means how favorable a node is for hackers. The node centrality is often calculated by simply counting the number of links in and out of each node in the network (degree centrality), by measuring how short the shortest paths are from one node to the others (closeness centrality) or calculating how often a node lies on the shortest path between other nodes (betweenness centrality). These centrality measures are useful in some cases, but they rely heavily on the degree of nodes and do not consider each node’s relationship with other important nodes. For example, if one fog node with high centrality in the network has a high possibility of getting attacked, then nodes in its neighborhood should also be ranked with a relatively high centrality value due to the continuity of attacks. Eigenvector centrality is a measure of the influence of a node in a network. It holds the idea that connections to high-scoring nodes contribute more to the score of the node than that to low-scoring nodes.The Eigenvector centrality of a fog nodefi is given by the following equation:(2)ci=vfi,where vector v is the eigenvector of unit length corresponding to the largest eigenvalue of the adjacency matrix MN×N of the network and vfi is the i-th entry of vector v. Hence, one could determine the Eigenvector centrality of every fog node by just computing this eigenvector v.Figure3 shows a network that contains two local substructures—a hierarchy and a core-periphery, with one connection linking them. We calculate the degree centrality, betweenness centrality, closeness centrality, and Eigenvector centrality and compare them in Table 1. As can be seen, node 8 has the highest Eigenvector centrality value, followed by nodes 9 and 10. Although node 1 connects the complete hierarchy of the left subnetwork, its Eigenvector centrality is smaller than node 8, which connects the right subnetwork. In comparison to the degree centrality, in which nodes 8 and 9 have equal degree centrality values, here since node 8 is connected to nodes that are “more connected” and thus more important, and since node 9 is connected to isolated node 12, node 8 has a higher Eigenvector centrality value. As for the betweenness centrality and closeness centrality, node 13 is considered more important than node 8. This is a result of the fact that all the paths between the left and the right subnetworks must pass through node 13.Figure 3
An example of Eigenvector centrality.Table 1
Comparison among different centrality measures.
NodeDegree centralityBetweenness centralityCloseness centralityEigenvector centrality130.2556820.4444440.239731230.1193180.3529410.144301330.1193180.3529410.144301410.0000000.2666670.058403510.0000000.2666670.058403610.0000000.2666670.058403710.0000000.2666670.058403830.1818180.3870970.510702930.0625000.3157890.4790571030.0625000.3157890.4790571110.0000000.2448980.1938881210.0000000.2448980.1938881320.1988640.4285710.303722Assume that onlyn fog nodes P=p1,p2,…,pn are selected to take part in workload computation, we define the security of node selection scheme P as follows:(3)SP=n∑i=1ncj|pi=fj,j∈1,N=n∑i=1nvpi.


## 2.3. Multiobjective Optimization Model

Based on the above analysis on security and makespan functions, we propose a multiobjective optimization model as follows:(4)minPTP=m−1α1ℋm+h−1w1+s1+o1+β1hℋm+h−1w1+s1,minP1SP=1n∑i=1nvpi.Here, P=p1,p2,…,pn∈F=f1,f2,…,fN.There are two objectives considered in our model, where functionTP refers to makespan minimization, while function 1/SP represents the reciprocal of security maximization. This model optimizes data security and makespan simultaneously. It involves only one set of variables, that is, the node selection scheme P. This is because once P is given, an optimal workload scheduling scheme can be obtained by ConfMIS strategy. We shall illustrate in the next section how ConfMIS strategy works and how to derive its solution, including optimal load partitions α1 and β1, optimal number m of installments, and a feasible value for h, which are involved in the proposed model.


## 3. Conflict-free Multi-Installment Scheduling Strategy

In this section, we first derive closed-form solutions to an optimal load partition, and then by rigorous proof of two theorems, we derive a closed-form solution to an optimal number of installments. Subsequently, we demonstrate by an example that whenh=1 (as adopted in the existing studies on PMIS [17, 18]), there exist time conflicts between the last installment and the last but one. To avoid these time conflicts, we derive a feasible value for h at the end of this section.


### 3.1. Optimal Load Partition

To achieve a minimum makespan, there is no idle time between any two adjacent internal installments for each fog node. The time period fromt1 to t5 in Figure 2 is taken as an example. It costs fog node p1 time α1Vw1+s1 to compute load fraction α1V in the second installment. Meanwhile, the time period from t1 to t5 equals the time period from t1 to t2 (communication time z1α1V for node p1 in the second installment) plus time period from t2 to t3 (communication start-up overhead o2 for node p2 in the second installment) plus time period from t3 to t4 (computation start-up overhead s2 for node p2) plus time period from t4 to t7 (computation time w2α2V for node p2 in the second installment) minus time period from t6 to t7 (communication start-up overhead o2 for node p2 in the third installment) minus time period from t5 to t6 (communication time z1α1V for node p1 in the third installment). Hence, we have α1Vw1+s1 = z1α1V+o2+s2+α2Vw2−o2−z1α1V. That is, α1Vw1+s1 = s2+α2Vw2. Similarly, we arrive at the following equations:(5)α1Vw1+s1=α2Vw2+s2=⋯=αnVwn+sn.Thus,αi with i=1,2,…,n can be written in terms of α1 as follows:(6)αi=α1Vw1+s1−siVwi.Let(7)Δi=w1wi,Φi=s1−siwi.Simplifying equation (6) by equation (7), we have(8)αi=α1Φi+1VΦi,i=2,3,…,n.Combining equation (8) with ∑i=1nαi=1, we can obtain(9)1V∑i=2nΦi+1+∑i=2nΔiα1=1.Rearranging equations (8) and (9) yields the closed-form solutions to an optimal load partition for internal installments:(10)α1=1−1/V∑i=2nΦi1+∑i=2nΔi,αi=1VΦi+Δiα1,i=2,3,…,n.A necessary condition for a feasible load partition is given byαi>0 with i=1,2,…,n.Likewise, to achieve the minimum makespan, all fog nodes stop computing at the same time in the last installment. By observing Figure2, we have the following equations:(11)si+wiβihV=oi+1+ziβihV+si+1+wi+1βi+1hV,i=1,2,…,n−1.One can expressβi+1 with i=1,…,n−1 in terms of βi by rearranging equation (11) as follows:(12)βi+1=si−oi+1+si+1hVwi+1+wi−ziwi+1βi.Let(13)δi+1=si−oi+1+si+1wi+1,εi+1=wi−ziwi+1.Simplifying equation (12) by equation (13) yields(14)βi+1=1hVδi+1+εi+1βi,i=1,2,…,n−1.Denoting(15)Ei=∏j=2iεjandΓi=∑j=2iδj∏k=j+1iεk.By means of equation (15), βi can be written in terms of β1 from recursive derivation of equation (14) as follows:(16)βi=Eiβ1+1hVΓi,i=2,3,…,n.Together equation (16) with ∑i=1nβi=1, closed-form solutions to an optimal load partition can be obtained for the last installment:(17)β1=1−1hV∑i=2nΓi/1+∑i=2nEi,βi=1hVΓi+Eiβ1,i=2,3,…,n.It is worth noting thatβi>0 with i=1,2,…,n should hold to ensure a feasible load partition.


### 3.2. Optimal Number of Installments

Through the above analysis, we know that given the values ofm and h, an optimal load partition can be obtained by equations (10) and (17). Note that not all values of mm>0 and hh>0, denoted as m,h, lead to a feasible load scheduling scheme since αi>0 and βi>0 with i=1,2,…,n should be guaranteed in the first place. We regard m,h as a feasible solution to ConfMIS strategy if the load partitions obtained based on m,h satisfy the above constraints; otherwise, m,h is an infeasible solution.Theorem 1.
Ifm,h is a feasible solution to ConfMIS strategy, then m′,h with m′<m is also a feasible solution.Proof.
Sincem,h is a feasible solution to ConfMIS strategy, load partitions αi and βi obtained by equations (10) and (17) satisfy that αi>0 and βi>0 for ∀i∈1,2,…,n. When i=1, we have(18)α1=1−m+h−1/ℋ∑i=2nΦi1+∑i=2nΔi>0,β1=1−m+h−1/hℋ∑i=2nΓi1+∑i=2nEi>0.
Hence,(19)∑i=2nΦi<ℋm+h−1,∑i=2nΓi<hℋm+h−1.
As for solutionm′,h with m′=m−1, one can also obtain load partitions αi′ and βi′ via equations (10) and (17). For αi′ and βi′, we have(20)α1′=1−m+h−2/ℋ∑i=2nΦi1+∑i=2nΔi>1−m+h−2/ℋℋ/m+h−11+∑i=2nΔi>0,β1′=1−m+h−2/hℋ∑i=2nΓi1+∑i=2nEi>1−m+h−2/hℋhℋ/m+h−11+∑i=2nEi>0.
Given thatαi>0 and βi>0 with i=1,2,…,n, we have proved in the above that α1′>0 and β1′>0. Then, we proceed to prove that αi′>0 and βi′>0 for i=2,3,…,n by contradiction. Assume that ∃j∈2,3,…,n, αj′<0, that is, αj′=Φj/V+Δjα1′<0 according to equation (8). Substituting V=ℋ/m+h−2 into αj′, we have Φj<−Δjα1′ℋ/m+h−2. Since αj>0, we have αj=Δjα1+1/VΦj>0. Likewise, substituting V by ℋ/m+h−2 yields Φj>−Δjα1ℋ/m+h−1. Therefore, we arrive at −Δjα1ℋ/m+h−1<Φj<−Δjα1′ℋ/m+h−2. After simplifying this, one can obtain that α1m+h−2>α1′m+h−1. Expanding α1 and α1′, we have(21)m+h−2−m+h−1m+h−2ℋ∑i=2nΦi>m+h−1−m+h−1m+h−2ℋ∑i=2nΦi.
Sincem+h−2>m+h−1, a contradiction occurs. Hence, the initial assumption that ∃j∈2,3,…,n, αj′<0 must be false. In the same way, one can prove that βi′>0. To summarize, when m,h is a feasible solution to ConfMIS strategy, that is αi>0 and βi>0 with i=1,2,…,n, m′,h with m′=m−1 is also a feasible solution to ConfMIS strategy since αi′>0 and βi′>0. By mathematical induction, we can conclude that if m,h is a feasible solution to ConfMIS strategy, then m′,h with m′<m is also a feasible solution.Theorem 2.
Consider all feasible solutionsm,h under a certain node selection scheme P, as number m of installments increases, the makespan T first decreases and then increases.Proof.
For a certain node selection schemeP, one can implement ConfMIS strategy with feasible values of m,h on the selected fog nodes and further obtain its corresponding makespan T by equation (1). Substituting V for ℋ/m+h−1 into equation (1) and expanding α1 and β1 by equations (10) and (17), we have(22)Tm,h=m−11−1/V∑i=2nΦi1+∑i=2nΔiw1V+s1+1−1/hV∑i=2nΓi1+∑i=2nEihVw1+o1+s1.
Denoting(23)a=∑i=2nΦi,b=1+∑i=2nΔi,c=∑i=2nΓi,d=1+∑i=2nEi.
Then,Tm,h can be simplified as follows:(24)Tm,h=m−1ℋbm+h−1−m−1abw1+hℋdm+h−1−cdw1+o1+ms1.
Dividing both sides of the equation byw1 yields(25)Tm,hw1=m−1ℋbm+h−1−m−1ab+hℋdm+h−1−cd+ms1w1+o1w1.
Suppose thatm+1,h is a feasible solution to ConfMIS strategy, then m,h and m−1,h are also feasible solutions according to Theorem 1. Similarly, Tm+1,h/w1 and Tm−1,h/w1 can be obtained by equation (25). Comparing Tm,h/w1 with them, we have(26)Tm+1,hw1−Tm,hw1=ℋhd−bbdm+hm+h−1+s1w1−ab,(27)Tm,hw1−Tm−1,hw1=ℋhd−bbdm+h−1m+h−2+s1w1−ab.
Let(28)λ=s1w1−ab.
Equations (26) and (27) can be rewritten as follows:(29)Tm+1,hw1−Tm,hw1=ℋhd−bbdm+hm+h−1+λ,(30)Tm,hw1−Tm−1,hw1=ℋhd−bbdm+h−1m+h−2+λ.
According to the definitions ofa, b, and d in equation (23), we have(31)λ=s1ω1−∑i=1ns1−si/wi∑i=1nw1/wi=∑i=1nsi/wi∑i=1nΔi>0,and(32)b−d=∑i=2nΔi−Ei=∑i=2nw1wi−∏j=2iwj−1−zj−1wj=∑i=2nw1∏j=2i−1wj∏j=2i1wj−∏j=2iwj−1−zj−1∏j=2i1wj=∑i=2nw1∏j=2i−1wj−w1−z1∏j=2i−1wj−zj>0.
From equations (31) and (32), we know that λ>0 and b>d. Thus, it can be inferred from equation (29) that Tm+1>Tm when m+hm+h−1>ℋhb−d/bdλ. By solving this inequality for m, we can conclude that the makespan T increases as m increases when m<3/2−h+hℋb−d/bd\λ+1/4. Similarly, by analyzing equation (30), one can claim that the makespan T decreases as m increases when m>1/2−h+hℋb−d/bd\λ+1/4. In summary, the makespan first decreases and then increases as the number of installments increases.Theorem 3.
This reveals a fact that there exists a knee point for the makespanT with respect to m. This knee point satisfies the bounds on m given by 1/2−h+hℋb−d/bd\λ+1/4<m<3/2−h+hℋb−d/bd\λ+1/4. The upper bound of m is exactly 1 larger than the lower bound, so that the makespan T reaches its minimum when(33)m=32−h+hℋb−d/bd\λ+14.
Equation (31) gives an optimal solution to the number of installments.


### 3.3. Time Conflict Whenh = 1

In the existing studies on PMIS [17, 18], the total load fraction assigned to fog nodes in the last installment is forced to be identical to that in each internal installment. This can be considered as a special case in our scheduling model as h=1. Then, we demonstrate by an example that PMIS may give rise to time conflicts between the last installment and the last but one.Three heterogeneous fog nodes scheduled in three installments are considered, that is,n=m=3. For simplicity of calculation, workload size is set as ℋ=270. Relevant parameters of the three fog nodes are listed as follows:(34)o1=2,s1=3,z1=0.3,w1=10,o2=1,s2=2,z2=1.5,w2=30.o3=3,s3=1,z3=1.8,w3=50.The scheduling sequence of the three fog nodes follows the increasing order ofzi, that is, P=p1,p2,p3. According to equations (10) and (17), we obtain an optimal load partition as follows:(35)α1≈0.652,α2≈0.217,α3≈0.131,β1≈0.664,β2≈0.214,β3≈0.122The start timeTbi of arbitrary fog node pi in the last installment can be calculated by(36)Tbi=∑j=1i−1oj+zjβjhV+oi+m−1s1+w1α1V.Meanwhile, the finish timeTei of pi in the last installment can be computed by(37)Tei=∑j=1i−1oj+zjαjV+oi+m−1si+wiαiV.Here, we have the start timeTb3 and finish time Te3 of fog node p3 as follows:(38)Tb3=∑j=12oj+zjβjhV+o3+2s1+w1α1V≈1231.84,Te3=∑j=12oj+zjαjV+o3+2s3+w3α3V≈1231.93.It is noted thatTe3>Tb3, which means there is a time conflict for node p3 between the last installment and second to the last. If such time conflicts are allowed in the scheduling, then workload cannot be completed as planned. Therefore, it is imperative to search for a feasible scheduling scheme without time conflicts. We shall fulfill this goal by finding a feasible value for h.


### 3.4. Feasible Value forh

To avoid time conflicts, the start timeTbi of arbitrary fog node pi in the last installment should be greater than or equal to its finish time Tei in the last installment but one. Combining equations (36) and (37), we have(39)Tbi−Tei=∑j=1i−1oj+zjβjhV+oi+m−1s1+w1α1V−∑j=1i−1oj+zjαjV−oi−m−1si+wiαiV.According to equation (5), s1+w1α1V=si+wiαiV. Thus, we have(40)Tbi−Tei=∑j=1i−1oj+zjβjhV−∑j=1i−1oj+zjαjV=V∑j=1i−1zjβjh−αj.Expandingαj and βj according to equations (10) and (17) yields(41)Tbi−Tei=∑j=1i−1zjΓj+Ejβ1hV−Φj+Δjα1VIt is considered that both communication and computation start-up overheads are nearly neglectable compared to considerable communication time and computation time. Rearranging equation (41) by deleting start-up overheads yields(42)Tbi−Tei≈V∑j=1i−1zjEjβ1h−Δjα1.LetTbi−Tei≥0, we have Ejβ1h−Δjα1≥0 with ∀j∈1,i−1. Hence, Ejβ1h/Δjα1≥1. Comparing equations (10) and (17), it is easy to find that β1>α1. Therefore,(43)Ejβ1hΔjα1>hEjΔj=h∏k=1j−1wk−zk∏k=2jwkwkw1=h∏k=1j−11−zkwk,j=2,3,…,i−1.One can observe from equation (43) that if j=i−1 and h∏k=1j−11−zk/wk=1, then for ∀j=2,3,…,i−2, h∏k=1j−11−zk/wk>1 must be true. Hence, we have Ejβ1h/Δjα1>hEj/Δj≥1 hold for equation (43). Consequently, Tbi−Tei>0 holds for equation (42), that is, no time conflicts exist. Therefore, from equation h∏k=1j−11−zk/wk=1 with j=i−1, one can find a feasible value for h as follows:(44)h=1∏k=1i−21−zk/wk.In summary, given a certain node selection schemeP, one can first calculate an optimal number m of installments by equation (33) and then find a feasible value for h by equation (44). Taking the values of m and h from equations (10) and (17), one can get an optimal load partition for ConfMIS strategy. Hence, as mentioned in the earlier, the makespan T of workloads on the fog only determines by node selection scheme P.


## 3.1. Optimal Load Partition

To achieve a minimum makespan, there is no idle time between any two adjacent internal installments for each fog node. The time period fromt1 to t5 in Figure 2 is taken as an example. It costs fog node p1 time α1Vw1+s1 to compute load fraction α1V in the second installment. Meanwhile, the time period from t1 to t5 equals the time period from t1 to t2 (communication time z1α1V for node p1 in the second installment) plus time period from t2 to t3 (communication start-up overhead o2 for node p2 in the second installment) plus time period from t3 to t4 (computation start-up overhead s2 for node p2) plus time period from t4 to t7 (computation time w2α2V for node p2 in the second installment) minus time period from t6 to t7 (communication start-up overhead o2 for node p2 in the third installment) minus time period from t5 to t6 (communication time z1α1V for node p1 in the third installment). Hence, we have α1Vw1+s1 = z1α1V+o2+s2+α2Vw2−o2−z1α1V. That is, α1Vw1+s1 = s2+α2Vw2. Similarly, we arrive at the following equations:(5)α1Vw1+s1=α2Vw2+s2=⋯=αnVwn+sn.Thus,αi with i=1,2,…,n can be written in terms of α1 as follows:(6)αi=α1Vw1+s1−siVwi.Let(7)Δi=w1wi,Φi=s1−siwi.Simplifying equation (6) by equation (7), we have(8)αi=α1Φi+1VΦi,i=2,3,…,n.Combining equation (8) with ∑i=1nαi=1, we can obtain(9)1V∑i=2nΦi+1+∑i=2nΔiα1=1.Rearranging equations (8) and (9) yields the closed-form solutions to an optimal load partition for internal installments:(10)α1=1−1/V∑i=2nΦi1+∑i=2nΔi,αi=1VΦi+Δiα1,i=2,3,…,n.A necessary condition for a feasible load partition is given byαi>0 with i=1,2,…,n.Likewise, to achieve the minimum makespan, all fog nodes stop computing at the same time in the last installment. By observing Figure2, we have the following equations:(11)si+wiβihV=oi+1+ziβihV+si+1+wi+1βi+1hV,i=1,2,…,n−1.One can expressβi+1 with i=1,…,n−1 in terms of βi by rearranging equation (11) as follows:(12)βi+1=si−oi+1+si+1hVwi+1+wi−ziwi+1βi.Let(13)δi+1=si−oi+1+si+1wi+1,εi+1=wi−ziwi+1.Simplifying equation (12) by equation (13) yields(14)βi+1=1hVδi+1+εi+1βi,i=1,2,…,n−1.Denoting(15)Ei=∏j=2iεjandΓi=∑j=2iδj∏k=j+1iεk.By means of equation (15), βi can be written in terms of β1 from recursive derivation of equation (14) as follows:(16)βi=Eiβ1+1hVΓi,i=2,3,…,n.Together equation (16) with ∑i=1nβi=1, closed-form solutions to an optimal load partition can be obtained for the last installment:(17)β1=1−1hV∑i=2nΓi/1+∑i=2nEi,βi=1hVΓi+Eiβ1,i=2,3,…,n.It is worth noting thatβi>0 with i=1,2,…,n should hold to ensure a feasible load partition.


## 3.2. Optimal Number of Installments

Through the above analysis, we know that given the values ofm and h, an optimal load partition can be obtained by equations (10) and (17). Note that not all values of mm>0 and hh>0, denoted as m,h, lead to a feasible load scheduling scheme since αi>0 and βi>0 with i=1,2,…,n should be guaranteed in the first place. We regard m,h as a feasible solution to ConfMIS strategy if the load partitions obtained based on m,h satisfy the above constraints; otherwise, m,h is an infeasible solution.Theorem 1.
Ifm,h is a feasible solution to ConfMIS strategy, then m′,h with m′<m is also a feasible solution.Proof.
Sincem,h is a feasible solution to ConfMIS strategy, load partitions αi and βi obtained by equations (10) and (17) satisfy that αi>0 and βi>0 for ∀i∈1,2,…,n. When i=1, we have(18)α1=1−m+h−1/ℋ∑i=2nΦi1+∑i=2nΔi>0,β1=1−m+h−1/hℋ∑i=2nΓi1+∑i=2nEi>0.
Hence,(19)∑i=2nΦi<ℋm+h−1,∑i=2nΓi<hℋm+h−1.
As for solutionm′,h with m′=m−1, one can also obtain load partitions αi′ and βi′ via equations (10) and (17). For αi′ and βi′, we have(20)α1′=1−m+h−2/ℋ∑i=2nΦi1+∑i=2nΔi>1−m+h−2/ℋℋ/m+h−11+∑i=2nΔi>0,β1′=1−m+h−2/hℋ∑i=2nΓi1+∑i=2nEi>1−m+h−2/hℋhℋ/m+h−11+∑i=2nEi>0.
Given thatαi>0 and βi>0 with i=1,2,…,n, we have proved in the above that α1′>0 and β1′>0. Then, we proceed to prove that αi′>0 and βi′>0 for i=2,3,…,n by contradiction. Assume that ∃j∈2,3,…,n, αj′<0, that is, αj′=Φj/V+Δjα1′<0 according to equation (8). Substituting V=ℋ/m+h−2 into αj′, we have Φj<−Δjα1′ℋ/m+h−2. Since αj>0, we have αj=Δjα1+1/VΦj>0. Likewise, substituting V by ℋ/m+h−2 yields Φj>−Δjα1ℋ/m+h−1. Therefore, we arrive at −Δjα1ℋ/m+h−1<Φj<−Δjα1′ℋ/m+h−2. After simplifying this, one can obtain that α1m+h−2>α1′m+h−1. Expanding α1 and α1′, we have(21)m+h−2−m+h−1m+h−2ℋ∑i=2nΦi>m+h−1−m+h−1m+h−2ℋ∑i=2nΦi.
Sincem+h−2>m+h−1, a contradiction occurs. Hence, the initial assumption that ∃j∈2,3,…,n, αj′<0 must be false. In the same way, one can prove that βi′>0. To summarize, when m,h is a feasible solution to ConfMIS strategy, that is αi>0 and βi>0 with i=1,2,…,n, m′,h with m′=m−1 is also a feasible solution to ConfMIS strategy since αi′>0 and βi′>0. By mathematical induction, we can conclude that if m,h is a feasible solution to ConfMIS strategy, then m′,h with m′<m is also a feasible solution.Theorem 2.
Consider all feasible solutionsm,h under a certain node selection scheme P, as number m of installments increases, the makespan T first decreases and then increases.Proof.
For a certain node selection schemeP, one can implement ConfMIS strategy with feasible values of m,h on the selected fog nodes and further obtain its corresponding makespan T by equation (1). Substituting V for ℋ/m+h−1 into equation (1) and expanding α1 and β1 by equations (10) and (17), we have(22)Tm,h=m−11−1/V∑i=2nΦi1+∑i=2nΔiw1V+s1+1−1/hV∑i=2nΓi1+∑i=2nEihVw1+o1+s1.
Denoting(23)a=∑i=2nΦi,b=1+∑i=2nΔi,c=∑i=2nΓi,d=1+∑i=2nEi.
Then,Tm,h can be simplified as follows:(24)Tm,h=m−1ℋbm+h−1−m−1abw1+hℋdm+h−1−cdw1+o1+ms1.
Dividing both sides of the equation byw1 yields(25)Tm,hw1=m−1ℋbm+h−1−m−1ab+hℋdm+h−1−cd+ms1w1+o1w1.
Suppose thatm+1,h is a feasible solution to ConfMIS strategy, then m,h and m−1,h are also feasible solutions according to Theorem 1. Similarly, Tm+1,h/w1 and Tm−1,h/w1 can be obtained by equation (25). Comparing Tm,h/w1 with them, we have(26)Tm+1,hw1−Tm,hw1=ℋhd−bbdm+hm+h−1+s1w1−ab,(27)Tm,hw1−Tm−1,hw1=ℋhd−bbdm+h−1m+h−2+s1w1−ab.
Let(28)λ=s1w1−ab.
Equations (26) and (27) can be rewritten as follows:(29)Tm+1,hw1−Tm,hw1=ℋhd−bbdm+hm+h−1+λ,(30)Tm,hw1−Tm−1,hw1=ℋhd−bbdm+h−1m+h−2+λ.
According to the definitions ofa, b, and d in equation (23), we have(31)λ=s1ω1−∑i=1ns1−si/wi∑i=1nw1/wi=∑i=1nsi/wi∑i=1nΔi>0,and(32)b−d=∑i=2nΔi−Ei=∑i=2nw1wi−∏j=2iwj−1−zj−1wj=∑i=2nw1∏j=2i−1wj∏j=2i1wj−∏j=2iwj−1−zj−1∏j=2i1wj=∑i=2nw1∏j=2i−1wj−w1−z1∏j=2i−1wj−zj>0.
From equations (31) and (32), we know that λ>0 and b>d. Thus, it can be inferred from equation (29) that Tm+1>Tm when m+hm+h−1>ℋhb−d/bdλ. By solving this inequality for m, we can conclude that the makespan T increases as m increases when m<3/2−h+hℋb−d/bd\λ+1/4. Similarly, by analyzing equation (30), one can claim that the makespan T decreases as m increases when m>1/2−h+hℋb−d/bd\λ+1/4. In summary, the makespan first decreases and then increases as the number of installments increases.Theorem 3.
This reveals a fact that there exists a knee point for the makespanT with respect to m. This knee point satisfies the bounds on m given by 1/2−h+hℋb−d/bd\λ+1/4<m<3/2−h+hℋb−d/bd\λ+1/4. The upper bound of m is exactly 1 larger than the lower bound, so that the makespan T reaches its minimum when(33)m=32−h+hℋb−d/bd\λ+14.
Equation (31) gives an optimal solution to the number of installments.


## 3.3. Time Conflict Whenh = 1

In the existing studies on PMIS [17, 18], the total load fraction assigned to fog nodes in the last installment is forced to be identical to that in each internal installment. This can be considered as a special case in our scheduling model as h=1. Then, we demonstrate by an example that PMIS may give rise to time conflicts between the last installment and the last but one.Three heterogeneous fog nodes scheduled in three installments are considered, that is,n=m=3. For simplicity of calculation, workload size is set as ℋ=270. Relevant parameters of the three fog nodes are listed as follows:(34)o1=2,s1=3,z1=0.3,w1=10,o2=1,s2=2,z2=1.5,w2=30.o3=3,s3=1,z3=1.8,w3=50.The scheduling sequence of the three fog nodes follows the increasing order ofzi, that is, P=p1,p2,p3. According to equations (10) and (17), we obtain an optimal load partition as follows:(35)α1≈0.652,α2≈0.217,α3≈0.131,β1≈0.664,β2≈0.214,β3≈0.122The start timeTbi of arbitrary fog node pi in the last installment can be calculated by(36)Tbi=∑j=1i−1oj+zjβjhV+oi+m−1s1+w1α1V.Meanwhile, the finish timeTei of pi in the last installment can be computed by(37)Tei=∑j=1i−1oj+zjαjV+oi+m−1si+wiαiV.Here, we have the start timeTb3 and finish time Te3 of fog node p3 as follows:(38)Tb3=∑j=12oj+zjβjhV+o3+2s1+w1α1V≈1231.84,Te3=∑j=12oj+zjαjV+o3+2s3+w3α3V≈1231.93.It is noted thatTe3>Tb3, which means there is a time conflict for node p3 between the last installment and second to the last. If such time conflicts are allowed in the scheduling, then workload cannot be completed as planned. Therefore, it is imperative to search for a feasible scheduling scheme without time conflicts. We shall fulfill this goal by finding a feasible value for h.


## 3.4. Feasible Value forh

To avoid time conflicts, the start timeTbi of arbitrary fog node pi in the last installment should be greater than or equal to its finish time Tei in the last installment but one. Combining equations (36) and (37), we have(39)Tbi−Tei=∑j=1i−1oj+zjβjhV+oi+m−1s1+w1α1V−∑j=1i−1oj+zjαjV−oi−m−1si+wiαiV.According to equation (5), s1+w1α1V=si+wiαiV. Thus, we have(40)Tbi−Tei=∑j=1i−1oj+zjβjhV−∑j=1i−1oj+zjαjV=V∑j=1i−1zjβjh−αj.Expandingαj and βj according to equations (10) and (17) yields(41)Tbi−Tei=∑j=1i−1zjΓj+Ejβ1hV−Φj+Δjα1VIt is considered that both communication and computation start-up overheads are nearly neglectable compared to considerable communication time and computation time. Rearranging equation (41) by deleting start-up overheads yields(42)Tbi−Tei≈V∑j=1i−1zjEjβ1h−Δjα1.LetTbi−Tei≥0, we have Ejβ1h−Δjα1≥0 with ∀j∈1,i−1. Hence, Ejβ1h/Δjα1≥1. Comparing equations (10) and (17), it is easy to find that β1>α1. Therefore,(43)Ejβ1hΔjα1>hEjΔj=h∏k=1j−1wk−zk∏k=2jwkwkw1=h∏k=1j−11−zkwk,j=2,3,…,i−1.One can observe from equation (43) that if j=i−1 and h∏k=1j−11−zk/wk=1, then for ∀j=2,3,…,i−2, h∏k=1j−11−zk/wk>1 must be true. Hence, we have Ejβ1h/Δjα1>hEj/Δj≥1 hold for equation (43). Consequently, Tbi−Tei>0 holds for equation (42), that is, no time conflicts exist. Therefore, from equation h∏k=1j−11−zk/wk=1 with j=i−1, one can find a feasible value for h as follows:(44)h=1∏k=1i−21−zk/wk.In summary, given a certain node selection schemeP, one can first calculate an optimal number m of installments by equation (33) and then find a feasible value for h by equation (44). Taking the values of m and h from equations (10) and (17), one can get an optimal load partition for ConfMIS strategy. Hence, as mentioned in the earlier, the makespan T of workloads on the fog only determines by node selection scheme P.


## 4. Evolutionary Algorithm Based on Decomposition

In this section, we put forward an evolutionary algorithm based on decomposition to solve the proposed model in Section2. Since the objectives of security and makespan contradict each other, the best trade-offs between security and makespan can be stated by Pareto optimality [19]. The pareto optimality is the state at which objectives are optimized in a way that one objective cannot improve without a second worsening. The goal of the evolutionary algorithm is to obtain an approximation to the pareto front (PF), from which a system designer or decision-maker can choose an appropriate solution based on IoT application demands.As there is only one set of variables involved in the proposed model, we encode individuals directly as the node selection schemeP, which is a sequence of fog nodes selected from the fog. For example, suppose there are N=200 fog nodes in total, from which an IoT application requires n=10 fog nodes to participate in workload computation. A possible individual could be encoded as P=p1,p2,…,p10=5,184,30,42,107,44,2,97,143,65, where pi∈1,N=1,200.To obtain a set of uniformly distributed solutions, we decompose the two objective functions intoK subproblems via the Tchebycheff approach and optimize them simultaneously. Let {γ1,γ2,…,γK} be a set of evenly spread weight vectors in the objective space, where γi=γ1i,γ2i. Each weight vector γi has a neighborhood of V closest weight vectors, denoted as set Bi, which can be obtained by calculating the Euclidean distances between any two weight vectors in {γ1,γ2,…,γK}. Let rb=r1b,r2b and rw=r1w,r2w be the reference points, where rb records the best values (the minimum) of the two objectives TP and 1/SP, while rw corresponds to the worst values (the maximum) found so far. Each subproblem can be described as follows:(45)gjP=maxγ1j×TP−r1br1w−r1b,γ2j×1/SP−r2br2w−r2bwherej=1,2,…,K.The evolutionary algorithm works as follows:Step 1.Initialization: set external population EP=∅, which is used to contain nondominated solutions found so far. Generate an initial population POP=P1,…,PK, where Pi=p1i,p2i,…,pni with i=1,…,K satisfies pji∈1,N and ∀j,k∈1,n,pji≠pki. Compute each individual’s objective functions TPi and 1/SPi according to equations (1) and (3). Initialize rb=r1b,r2b and rw=r1w,r2w, respectively, based on current population POP.Step 2.Evolution: for i=1,2,…,K, doStep 2.1.Crossover: randomly select two indexes a,b∈1,V from set Bi and then apply crossover operator on individuals Pa and Pb to generate offspring O1 and O2.Step 2.2.Mutation: apply mutation operator on O1 and O2 according to mutation probability pmut to generate offspring O3 and O4. Compute the objective functions of O3 and O4 according to equations (1) and (3).Step 2.3.Update Reference Pointsrbandrw: for k=3,4, if TOk<r1b, set r1b=TOk; if 1/SOk<r2b, set r2b=1/SOk; if TOk>r1w, set r1w=TOk; if 1/SOk>r2w, set r2w=1/SOk.Step 2.4.Update Neighbors: for each index j∈Biandk=3,4, if gjOk<gjPj, set Pj=Ok.Step 2.4.Update EP: remove all solutions in EP dominated by point TO3,1/SO3 and TO4,1/SO4 in the objective space. Meanwhile, add O3 to EP if no solutions in EP dominate it, so does O4.Step 3.Stopping Criteria: if Step 2 iterates more than times, then stop and output ; otherwise, go to Step 2.In Step 2.1, a crossover operator is adopted on individualsPa and Pb to generate offsprings O1 and O2. The crossover operator works as follows:Step 1.Exchange Genes: create two random crossover points in the parents and copy the genes between them from the first parent to the second offspring while the second parent to the first offspring.Step 2.Copy from Head to Tail: starting from the first gene in the parents until the first crossover point, copy the remaining unused genes from the first parent to the first offspring while the second parent to the second offspring.Step 3.Copy from Tail to Head: starting from the last gene in the parents until the second crossover point, copy the remaining unused genes from the first parent to the first offspring while the second parent to the second offspring.Figure4 demonstrates how the crossover operator works under the circumstance that N=200 and n=10. As demonstrated in Figure 4, parents Pa and Pb generate offsprings O1 and O2 via crossover.Figure 4
An example of crossover operator.In Step 2.2, a mutation operator is adopted on individualsO1 and O2 to generate offsprings O3 and O4. For each gene in the individuals produced by crossover, the mutation operator first generates a random real number prand∈0,1 and compares it with mutation probability pmut. If prand≤pmut, then this gene is changed to a random integer gr, satisfying that gr∈1,N and that gr differs from other genes in the individual.


## 5. Experiments and Result Analysis

We first introduce the parameters adopted in our experiments and then investigate the performance of our proposed evolutionary algorithm on a set of test instances.The complexity of the scheduling problem in this study isANn=n!/n−m!, referring to a selection of n fog nodes from a set of N nodes in which order matters. Without a doubt, we could not explore all possible solutions in the variable space when n and N are large. Hence, we randomly enumerate 100, 1000, and 10000 solutions respectively under the circumstance of ℋ=2000 and n=10 and calculate out their PFs, which are demonstrated in Figure 5. As can be seen, nondominated solutions grow in number and stretch out more widely in the objective space as the number of random solutions increases. Due to the time limit, we adopt 10000 random solutions as a benchmark for comparison.Figure 5
PFs obtained by random solutions.Without loss of generality, we setn=10 and vary workload size ℋ from 2000 to 2500. Figure 6 shows the PFs obtained by our proposed algorithm. It can be observed in Figure 6 that the two objectives (maximizing security and minimizing makespan) conflict with each other. When the makespan reaches its minimum (points in the bottom right), security becomes the worst (the reciprocal of security is the highest). On the contrary, those solutions with high-security values (points in the top left) perform badly in terms of makespan. Moreover, as the workload size increases, the makespan gets larger and larger, while the general trend and variation range of security stay unchanged. This is because the number of fog nodes involved in workload computation is the same in this experiment.Figure 6
PFs obtained by a proposed algorithm.We compare the solutions obtained by the proposed algorithm and the random one under different cases whenn∈10,12,15 and ℋ∈2000,2500. Figure 7 shows the experimental results. We can observe from this figure that for a certain workload, as more fog nodes get involved in workload computation, the makespan decreases while the variation range of security turns out to be stable for the proposed algorithm but narrows sharply for the random algorithm. This proves the powerful global searching ability of our proposed algorithm. Furthermore, for any workload cases with any number of computational fog nodes, the solutions obtained by our proposed algorithm can dominate those by the random algorithm. This means the proposed algorithm can obtain better solutions with a shorter makespan and higher security. Most important of all, Figure 7 shows that the solutions obtained by the random algorithm aggregate to a relatively small area, while those obtained by the proposed algorithm spread widely and distribute uniformly in the objective space. With these representative solutions, decision-makers own more choices in variety and can choose whichever they need according to diverse IoT application demands.Figure 7
Comparison between the proposed algorithm and the random one. (a)ℋ=2000. (b) ℋ=2100. (c) ℋ=2200. ℋ=2300. (d) ℋ=2400. (e) ℋ=2500.
(a)(b)(c)(d)(e)(f)Figure8 shows the variation range of solutions in terms of each objective function when n=10 and ℋ∈2000,2500. One can observe from Figure 8(a) that as the workload enlarges, the makespan becomes longer for both algorithms. Meanwhile, a nearly stable behavior can be observed from Figure 8(b) for both algorithms with regard to security. This is because security values are partially determined by the number of fog nodes getting involved in workload computation and that we set n=10 as a fixed value in this experiment. Furthermore, it can be observed from Figure 8 that for both objectives, the proposed algorithm yields a much wider variation range of solutions than the random one does. More diverse candidate solutions imply that decision-makers can have richer and better choices to cope with various IoT application demands.Figure 8
Boxplots showing the variation range of solutions. (a) Boxplot for makespan. (b) Boxplot for security.
(a)(b)


## 6. Conclusions

In this study, we explored the trade-offs between security and makespan when offloading workloads on fog nodes from IoT. Since these two objectives contradict each other, we proposed a multiobjective optimization model in this study, where Eigenvector centrality is adopted to measure node security and a conflict-free multi-installment scheduling (ConfMIS) strategy is designed to minimize the makespan. To solve the proposed model, we put forward an evolutionary algorithm based on decomposition and a tailor-made crossover operator. Experimental results show that the proposed algorithm achieves our goal and presents salient features. First, as more fog nodes get involved in workload computation, a nearly stable behavior can be observed for our proposed algorithm with regard to solutions’ variation range of security, which proves its powerful global searching ability. Second, the proposed algorithm has superior performance in obtaining better solutions with a shorter makespan and higher security, compared to the benchmark. Third, the proposed algorithm can yield representative solutions that are widely spread and uniformly distributed in the objective space. With more diverse candidate solutions, system designers or decision-makers can have richer and better choices when facing various IoT application demands.



---

*Source: 5184453-2022-05-23.xml*