Introduction
Related work
Ref. | Cloud/ Fog | Optimization method | Optimization criteria | Mobility |
---|---|---|---|---|
[19] | Cloud | GA | Makespan and load balancing | No |
[20] | Cloud | GA and PSO + (SJFP) | Makespan | No |
[21] | Cloud | Canonical PSO and fully-informed PSO | Throughput and delay | No |
[22] | Cloud | ABC + (FCFS, SJF, LJF) | Makespan and load balancing | No |
[23] | Cloud | IWC (Improved WOA) | Execution time, system load, and price cost | No |
[24] | Cloud | WOA | Makespan, deadline, and resource utilization | No |
[25] | Fog | Moth-flame | Execution time, transfer time, and makespan | No |
[26] | Fog | Knapsack + symbiotic organisms search | Energy consumption, execution cost, total network usage, and sensor lifetime | No |
[27] | Fog | Hybrid heuristic (IACO + IPSO) | Completion time, energy consumption, and reliability | No |
[28] | Fog | NSGA-II | Service latency and stability | No |
[29] | Fog | Lyapunov optimization | Service delay and energy consumption | No |
[30] | Fog | Ant Colony | Energy consumption, resource consumption, and total completion task | No |
[31] | Fog | GA | Execution time and operating cost | No |
[32] | Fog | Bees Life | Execution time and allocated memory | No |
[33] | Fog | GA + Gaussian Mixture Model | Temperature of CDC, latency, energy, and bandwidth | No |
[34] | Fog | Deep Reinforcement learning | Energy consumption, response time, migration time, SLA violations and cost | No |
[35] | Fog | Deep Reinforcement learning | Average energy consumption of IoT device and response delay | No |
[36] | Fog | Lyapunov optimization + drift-plus-penalty | Time-average and energy consumption | No |
[37] | Fog | Adaptive GA | Offloading success rate and energy consumption | Yes |
[38] | Fog | - | Energy consumption | Yes |
[39] | Fog | - | Delay and power consumption | Yes |
Our work | Fog | WOA+OB learning + chaos | Response delay and energy consumption | No |
Proposed system model and formulation for the task scheduling problem
Use-case scenario
Fog-based architecture for task scheduling problem
-
The clusters are created automatically and remain unchangeable.
-
The state of network is static.
-
The programming codes for the execution of IoT tasks are deployed in all fog and cloud nodes.
-
The data required for the execution of an IoT task are associated to a single fog cluster manager
Proposed qoS parameters modelling for task scheduling problem
Proposed formulation for task scheduling problem
Symbol | Description |
---|---|
T | Set of IoT tasks in the task scheduling requests |
n | Number of tasks in the task scheduling requests |
ti | The ith task in the task scheduling request |
F | Set of fog nodes in the system |
m | Number of fog nodes in the system |
fj | The jth fog node in the system |
Di | Input data size of task ti |
Ii | Required computing density of task ti |
DEi | Deadline of task ti |
\(C^{max}_{j}\) | Computing capacity of fog node fj |
\(S^{max}_{j}\) | Storage capacity of fog node fj |
\(E^{max}_{j}\) | Battery capacity of fog node fj |
aij | A binary variable determining whether ti is assigned to fj |
Aassign | assign matrix of size n∗m |
U(Aassign) | Overall utility of a task scheduling solution |
Q(i,j) | QoS score related to ti that is assigned to fog node fj |
wt | Weight for time QoS parameter |
we | Weight for energy QoS parameter |
Ttotal(aij) | Total time consumption for assigning IoT task ti to fog node fj |
Tup(aij) | Time consumption for transmitting IoT data for executing the task ti on fog node fj |
Texecute(aij) | Time consumption for executing IoT task ti in fog node fj |
Etotal(aij) | Total energy consumption for assigning IoT task ti to fog node fj |
Eup(aij) | Energy consumption for transmitting IoT data for executing the task ti on fog node fj |
Eexecute(aij) | Energy consumption for executing IoT task ti in fog node fj |
Rij | Transmission capacity of the channel between IoT device and fog node fj |
Proposed approach
Whale optimization algorithm (WOA)
Encircling prey
Bubble-net feeding (exploitation)
Search for prey (exploration)
Limitations of WOA
Opposition-based learning
Quasi and super opposition-based learning
Partial-opposition-based learning
The proposed partial-opposition-based learning
Jumping rate
Chaos theory
Non-linear functions
Fog task scheduling using oppoCWOA
Solution encoding
Population initialization
Fitness evaluation
Whale position updating
Opposite-population
OppoCWOA algorithm
Computational complexity
Experiment results
Parameter | Value | Description |
---|---|---|
n | 50−300 | Number of tasks |
m | 20 | Number of fog nodes |
Di | 10−50 Mb | The data size of task ti |
Ii | 300−500 Cycles/bit | Computing density of task ti |
\(C_{j}^{max}\) | 1−2 Giga cycles/bit | The computing capacity of fog node fj |
\(S_{j}^{max}\) | 500−2000 Mb | Storage capacity of fog node fj |
B | 100−200 MHz | Bandwidth between IoT device and fog node |
Lj | 1.5−2 Km | Distance of fog node fj from the fog node manager |
pj | 1−5 W | Power consumption of fog node fj |
pi | 0.1 W | Transmission power of IoT task device ti |
Chaotic maps effect
Chaos maps for \(\vec {r}\)
Chaos maps for p
Opposition-based techniques effect
Jumping rate effect
Non-linear functions
OppoCWOA evaluation
Method | Value |
---|---|
Chaotic map for \(\vec {r}\) | Circle |
Chaotic map for p-value | Sinusoidal |
Opposition-based learning type | Partial |
Non-linear function for \(\vec {A}\) | Beta2 |
Jumping rate | 0.7 |
Conclusion and future works
Appendix
Name | Function | Possible Effect | Diagram |
---|---|---|---|
Linear | y=2−2x | In the first half of the iterations, WOA is mostly devoted to global exploration, while in the other half iterations, it is mostly devoted to local exploitation. | |
Beta1 | y=2−2x3 | In more than half of the iterations, WOA is devoted to global exploration (about 4/5 of the iterations), while in the other iterations, it is devoted to local exploitation. Better global exploration capability. | |
Beta2 |
\(y= 2 - \sqrt {4 - 4(x-1)^{2}}\)
| In more than half of the iterations, WOA is devoted to local exploitation(more than 4/5 of the iterations), while in the other iterations, it is devoted to global exploration. Better local exploitation capability. | |
Beta3 |
\(y = \left \{\begin {array}{lll} Beta1 & \qquad \text {if } x \leq 0.5 \\ Beta2 &\qquad \text {Otherwise } \\ \end {array} \right.\)
| In the first half of the iterations, WOA is strictly devoted to global exploration, while in the other iterations, it is strictly devoted to local exploitation. | |
Beta4 |
\(y = \left \{ \begin {array}{lll} Beta2 & \qquad \text {if } x \leq 0.5 \\ Beta1 &\qquad \text {Otherwise } \\ \end {array} \right.\)
| In the first quarter of the iterations, WOA is devoted to global exploration, in the second quarter of the iterations, it is devoted to local exploitation. In the third quarter of the iteration, it is devoted to global exploration, while in the last quarter of iterations, it is devoted to local exploitation. |
Number | Name | Chaotic Map | Diagram |
---|---|---|---|
1 | Chebyshev [47] |
\(\begin {array}{c}x_{(i+1)}= \cos (i cos^{-1} x_i) \\ x_0=0.7\end {array}\)
| |
2 | Circle [48] |
\(\begin {array}{c} x_{(i+1)}=(x_i+b-(\frac {a}{2\pi })\sin (2 \pi x_i))\text {mod}(1) \\ a=0.5,b=0.2,x_0=0.7 \end {array}\)
| |
3 | Cubic [49] |
\(\begin {array}{c} x_{(i+1)}=2.59 x_i (1 - x_{i}^{2}) \\ x_0 = 0.7 \end {array}\)
| |
4 | Guass [50] |
\(\begin {array}{c} x_{(i+1)} = \left \{ \begin {array}{lll} 0 & \qquad \text {if } x_i = 0 \\ \frac {1}{x_i} \text {mod}(1) &\qquad \text {if } x_{i}\neq 0 \end {array} \right. \\ x_0=0.7 \end {array}\)
| |
5 | Iterative [51] |
\(\begin {array}{c} x_{(i+1)} = \sin (\frac {a\pi }{x_i}) \\ a=0.7, x_0=0.7 \end {array}\)
| |
6 | Logistic [51] |
\(\begin {array}{c} x_{(i+1)}=a x_i (1 - x_{i}) \\ a=4, x_0=0.7 \end {array}\)
| |
7 | Piecewise [52] |
\(\begin {array}{c} x_{(i+1)} = \left \{\begin {array}{lll} \nicefrac {x_i}{p} & \qquad \text {if } x_i < p \\ \nicefrac {x_i - p}{0.5 - p} &\qquad \text {if } p\leq x_{i}\leq 0.5 \\ \nicefrac {1 - p - x_i}{0.5 - p}&\qquad \text {if } 0.5 \leq x_{i}\leq 1-p \\ \nicefrac {1 - x_i}{p}&\qquad \text {if } 1-p < x_i \end {array} \right. \\ p = 0.4, x_0=0.7 \end {array}\)
| |
8 | Sine [53] |
\(\begin {array}{c} x_{(i+1)}= \frac {a}{4} \sin (\pi x_i) \\ a=0.4, x_0 = 0.7 \end {array}\)
| |
9 | Singer [54] |
\(\begin {array}{c} x_{(i+1)}= \mu (7.86 x_i - 23.31 x_{i}^{2} + 28.75 x_{i}^{3} - 13.302875 x_{i}^{4}) \\ \mu = 1.073, x_0=0.7 \end {array}\)
| |
10 | Sinusoidal [55] |
\(\begin {array}{c} x_{(i+1)}=a x_{i}{2}\sin (\pi x_i) \\ a=2.3, x_0 = 0.7 \end {array}\)
| |
11 | Tent [56] |
\(\begin {array}{c} x_{(i+1)} = \left \{ \begin {array}{lll} \nicefrac {x_i}{0.7} & \qquad \text {if } x_i < 0.7 \\ \nicefrac {10}{3} (1-x_i) &\qquad \text {otherwise } \\ \end {array} \right. \end {array}\)
|
Evaluation metric | Statistics | Chebyshev | Circle | Cubic | Gauss | Iterative | Logistic | Piecewise | Sine | Singer | Sinusoidal | Tent | No Chaos |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Energy
|
Max
| 510.06 | 509.23 | 511.9 | 498.18 | 514.31 | 493.91 | 502.92 | 502.42 | 492.55 | 519.93 | 511.47 | 502.14 |
Min
| 386.96 | 380.17 | 392.38 | 424.6 | 407.76 | 321.38 | 396.5 | 417.73 | 411.97 | 425.55 | 398.06 | 383.84 | |
Mean
| 459.65 | 448.47 | 460.6 | 460.02 | 455.45 | 459.49 | 460.52 | 458.4 | 453.51 | 464.95 | 464.71 | 453.07 | |
Median
| 457.38 | 453.35 | 462.38 | 463.46 | 458.07 | 460.96 | 470.33 | 458.74 | 455.46 | 463.81 | 469.1 | 449.4 | |
Time
|
Max
| 85.9 | 68.72 | 86.31 | 79.24 | 84.6 | 81.01 | 79.06 | 78.59 | 74.4 | 93.38 | 75.28 | 81.29 |
Min
| 48.53 | 47.61 | 54.44 | 49.76 | 51.93 | 48.27 | 50.11 | 47.63 | 42.06 | 49.61 | 50.14 | 47.02 | |
Mean
| 66.79 | 62.08 | 65.97 | 64.52 | 64.54 | 64.08 | 66.34 | 66.09 | 61.09 | 67.78 | 64.66 | 62.1 | |
Median
| 66.35 | 64.12 | 64.51 | 62.4 | 64.13 | 66.78 | 67.91 | 68.77 | 63.15 | 66.42 | 65.89 | 61.07 | |
Time – Energy
|
Max
| 320.87 | 319.92 | 324.16 | 322.13 | 327.1 | 317.75 | 322.5 | 318.69 | 325.55 | 321.24 | 322.17 | 328.25 |
Min
| 260.07 | 255.78 | 245.8 | 258.96 | 255.31 | 240.15 | 257.41 | 255.94 | 264.26 | 265.66 | 268.85 | 250.68 | |
Mean
| 291.66 | 288.13 | 293.37 | 290.49 | 291.61 | 287.43 | 292.8 | 291.62 | 300.25 | 293.47 | 296.47 | 293.23 | |
Median
| 292.5 | 288.05 | 291.81 | 292.97 | 293.3 | 291.67 | 297.06 | 293.12 | 301.66 | 290.02 | 296.9 | 289.83 |
Evaluation metric | Statistics | Chebyshev | Circle | Cubic | Gauss | Iterative | Logistic | Piecewise | Sine | Singer | Sinusoidal | Tent | No Chaos |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Energy
|
Max
| 482.41 | 478.04 | 486.95 | 508.69 | 505.02 | 482.45 | 495.37 | 484.4 | 481.73 | 490.62 | 484.81 | 502.14 |
Min
| 406.34 | 406.41 | 403.43 | 402.02 | 393.84 | 373.87 | 402.71 | 406.95 | 301.87 | 389.03 | 390.01 | 383.84 | |
Mean
| 442.69 | 449.83 | 451.01 | 462.3 | 454.78 | 442.55 | 452.13 | 440.58 | 437.02 | 440.43 | 442.63 | 453.07 | |
Median
| 443.7 | 448.62 | 450.81 | 457.02 | 452.55 | 447.64 | 456.14 | 438.3 | 449.24 | 437.93 | 446.14 | 449.4 | |
Time
|
Max
| 70.35 | 74.05 | 72.23 | 85.28 | 84.33 | 68.08 | 70.13 | 74.35 | 68.23 | 68.79 | 69.07 | 81.29 |
Min
| 49.2 | 52.87 | 49.63 | 49.07 | 44.32 | 47.6 | 46.56 | 46.33 | 39.88 | 44.19 | 49.77 | 47.02 | |
Mean
| 60.39 | 63.09 | 60.35 | 66.97 | 66.2 | 59.51 | 60.98 | 61.25 | 59.06 | 57.46 | 58.76 | 62.1 | |
Median
| 61.24 | 61.48 | 58.93 | 64.48 | 65.65 | 60.85 | 62.53 | 60.39 | 60.29 | 58.2 | 58.51 | 61.07 | |
Time – Energy
|
Max
| 320.7 | 331.87 | 316.66 | 317.69 | 328.24 | 314.08 | 306.96 | 320.77 | 311.32 | 311.54 | 316.26 | 328.25 |
Min
| 256.13 | 238.4 | 257.08 | 266.88 | 273.77 | 231.86 | 256.23 | 244.74 | 245.91 | 242.62 | 248.11 | 250.68 | |
Mean
| 283.03 | 286.28 | 282.8 | 296.14 | 295.26 | 282.1 | 284.8 | 288.49 | 282.63 | 274.38 | 286.73 | 293.23 | |
Median
| 283.06 | 285.69 | 278.54 | 298.03 | 293.63 | 278.79 | 284.72 | 291.91 | 288.64 | 276.44 | 292.96 | 289.83 |
Evaluation metric | Statistics | WOA | OWOA | POWOA | QOWOA | SOWOA |
---|---|---|---|---|---|---|
Energy
|
Max
| 502.15 | 491.83 | 480.75 | 502.31 | 501.41 |
Min
| 383.84 | 405.04 | 355.72 | 378.69 | 403.88 | |
Mean
| 453.08 | 450.01 | 417.64 | 454.37 | 446.44 | |
Median
| 449.4 | 450.98 | 412.11 | 468.51 | 446.3 | |
Time
|
Max
| 81.3 | 70.77 | 79.84 | 79.9 | 77.27 |
Min
| 47.02 | 54.31 | 56.93 | 50.39 | 43.26 | |
Mean
| 62.1 | 63.47 | 62.67 | 64.23 | 59.68 | |
Median
| 61.07 | 63.38 | 60.67 | 62.69 | 60.83 | |
Time – Energy
|
Max
| 328.26 | 319.08 | 310.84 | 340.33 | 313.31 |
Min
| 250.68 | 233.09 | 232.06 | 223.64 | 264.67 | |
Mean
| 293.23 | 283.87 | 269.32 | 293.15 | 285.84 | |
Median
| 289.83 | 281.56 | 267.41 | 297.39 | 285.54 |
Evaluation metric | Statistics | Linear | Beta1 | Beta2 | Beta3 | Beta4 |
---|---|---|---|---|---|---|
Energy
|
Max
| 502.15 | 504.37 | 484.95 | 485.05 | 514.8 |
Min
| 383.84 | 413.63 | 407.31 | 412.51 | 421.54 | |
Mean
| 453.08 | 457.48 | 458.31 | 452.52 | 466.08 | |
Median
| 449.4 | 457.95 | 458.16 | 454.71 | 478.06 | |
Time
|
Max
| 81.3 | 80.07 | 75.23 | 74.73 | 74.72 |
Min
| 47.02 | 47.73 | 44.96 | 45.07 | 50.95 | |
Mean
| 62.01 | 65.59 | 60.75 | 60.49 | 62.6 | |
Median
| 61.07 | 66.34 | 62.28 | 60.71 | 63.43 | |
Time – Energy
|
Max
| 328.26 | 315.33 | 303.52 | 321.92 | 316.23 |
Min
| 250.68 | 252.55 | 265.21 | 258.88 | 241.04 | |
Mean
| 293.23 | 286.33 | 282.26 | 289.41 | 291.28 | |
Median
| 289.83 | 288.22 | 280.92 | 287.15 | 292.28 |
Evaluation metric | Statistics | WOA | PSO | ABC | GA | OppoCWOA |
---|---|---|---|---|---|---|
Max
| 502.15 | 467.75 | 444.95 | 447.1 | 441.12 | |
Min
| 383.84 | 368.91 | 400.89 | 408.66 | 309.87 | |
Energy
|
Mean
| 453.08 | 438.39 | 422.34 | 429.58 | 384.48 |
Median
| 449.4 | 441.16 | 417.74 | 432.66 | 386.25 | |
Max
| 81.3 | 87.09 | 81.97 | 62.2 | 72.94 | |
Min
| 47.02 | 56.28 | 62.32 | 41.55 | 40.23 | |
Time
|
Mean
| 62.01 | 72.56 | 73.6 | 50.97 | 58.64 |
Median
| 61.07 | 72.2 | 74.11 | 51.22 | 59.54 | |
Max
| 328.26 | 303.09 | 287.19 | 281.64 | 306.91 | |
Min
| 250.68 | 255.13 | 244.42 | 249.17 | 214.58 | |
Time – Energy
|
Mean
| 293.23 | 282.45 | 270.2 | 265.25 | 254.7 |
Median
| 289.83 | 286.18 | 271.14 | 268.46 | 251.82 |