# Two-Stage Optimal Task Scheduling for Smart Home Environment Using Fog Computing Infrastructures
## 3 Proposed Model
### Problem Formulation
The hybrid heuristic algorithm is a combination of ACO and PSO, and the idea behind their combination is that PSO has a fast search speed and ACO provides high accuracy; thus, their combination contributes to the optimal task allocation in the fog environment. The working of the proposed 2-ST hybrid algorithm can be easily understood by looking at Algorithms 1 and 2. In particle swarm optimization, the position of each particle represents a task's possible scheduling, and according to the task allocation decisions \(s_{ij}(t)\), the position of particle \(i\) can be simplified as \(s_{ij}\), \(s_{ij}\in 0,1\), \(i=1,2,\ldots,n\); \(j=1,2,\ldots,m\). Similarly, the speed of particle \(i\) can be simplified as \(v_{i}\),\(j\), \(v_{j}\)\(e\) [\(\mathrm{vmax}\), \(\mathrm{vmax}\)], \(i=1,2,\ldots,n\); \(j=1,2,\ldots,m\). The inertia weight \(w\) determines the search ability of the particles in the global and local search, which follows the premise that the greater \(w\) is, the stronger the global searching ability of the algorithm. Otherwise, the local search ability of the algorithm is stronger. To improve the intelligence of the particle swarm optimization algorithm, many methods have been proposed regarding inertia weighting, such as a linearly decreasing weight, the weight decrease of the linear differential equation, and so on. This paper combined the  
Figure 3: Data flow of the 2-stage task scheduling algorithm for optimal task allocation. \begin{table}
\begin{tabular}{l l} \hline \hline
**Fog Node Parameters** & **Values** \\ \hline Number of fog nodes & 4 \\ \hline Processing capacity & 11 MIPS \\ \hline RAM & 8 KB \\ \hline Bandwidth & 1024 Mbps \\ \hline Storage & 92 KB \\ \hline Idle power consumption & 0.36 Watt \\ \hline Execution power consumption & 0.44 watt \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Fog node parameters. inertia weight with the number of iterations, and the solution formula of the inertia weight is shown below. \[ \begin{split} w=w_{max}-\frac{(w_{max})-w_{min}}{k_{max}}k& <0.7\times k_{max}\\ =w_{min}+(w_{max}-w_{min}\times rand)k&\geq 0.7\times k_{ max}\end{split}  \tag{6}\]  
where \(w_{max}\) is the maximum inertia weight, \(w_{min}\) is the minimum inertia weight, \(k\) is the number of iterations, and \(k_{max}\) is the largest number of iterations. The inertia weight changes dynamically with the increase of the iterations, which guarantees that the algorithm has the opportunity to gain a larger inertia weight value later in the search and is prevented from falling into the local optimum. This approach is used to maintain a balance between exploration-exploitation for this hybrid approach of optimization. The entire proposed mechanism can be easily understood by looking at Algorithm 1. ```
Input value: Task (\(T1\), \(T2\),..., \(T_{n}\)) Output: Optimal task allocation Step 1:\(DOT_{i}=\) new received task Step 2: All nodes \(I_{n}=I=1,2,\ldots,N\) Assign rank for \(T_{i}\) Step 3: Priority queue = \(T_{i}\) Step 4: Sort priority queue according to ranks Step 5: Allocation of VM \(<\)-allocation\({}_{u}\)singNaiveBayes() Step 6: Calculate fitness function Step 7: Fitness optimization using hybrid heuristic algorithm
```  
**Algorithm 1** Optimal task allocation algorithm. The smart home environment as an example was considered in this study, and Figure 4 shows a few tasks that could be considered in this scenario, for example: alarm generation, processing of the humidifier, lights on/off, surveillance video, and many others. A few tasks would be delay-tolerant, and a few would be non-delay-tolerant. These tasks will be allocated to the fog nodes. Suppose in the above scenario that the smoke detector is a non-delay-tolerant task and considered as a Rank 1 task. Similarly, the water pump turning on/off is also a non-delay-tolerant task, so the ranking table plays an important role here. Such tasks will be allocated to the fog nodes with specified resources. The proposed 2-ST hybrid algorithm is used for optimal task allocation using Algorithms 1 and 2.