Low-latency and energy-efficient scheduling in fog-based IoT applications

In today’s world, the internet of things (IoT) is developing rapidly. Wireless sensor network (WSN) as aninfrastructure of IoT has limitations in the processing power, storage, and delay for data transfer to cloud. The large volume of generated data and their transmission between WSNs and cloud are serious challenges. Fog computing (FC) as an extension of cloud to the edge of the network reduces latency and traffic; thus, it is very useful in IoT applications such as healthcare applications, wearables, intelligent transportation systems, and smart cities. Resource allocation and task scheduling are the NP-hard issues in FC. Each application includes several modules that require resources to run. Fog devices (FDs) have the ability to run resource management algorithms because of their proximity to sensors and cloud as well as the proper processing power. In this paper, we review the scheduling strategies and parameters as well as providing a greedy knapsack-based scheduling (GKS) algorithm for allocating resources appropriately to modules in fog network. Our proposed method was simulated in iFogsim as a standard simulator for FC. The results show that the energy consumption, execution cost, and sensor lifetime in GKS are better than those of the first-come-first-served (FCFS), concurrent, and delay-priority algorithms.

PDF

___

[1] Gupta H, Dastjerdi AV, Ghosh SK, Buyya R. ifogsim: toolkit for modeling and simulation of resource management techniques in internet of things, edge and fog computing environments. Software: Practice and Experience 2017; 47(9): 1275-1296. doi: 10.1002/spe.2509
[2] Hu P, Dhelim S, Ning H, Qiu T. Survey on fog computing: architecture, key technologies, applications and open issues. Journal of Network and Computer Applications 2017; 98: 27-42. doi: 10.1016/j.jnca.2017.09.002
[3] Yu W, Liang F, He X, Hatcher WG, Lu C et al. A survey on the edge computing for the internet of things. IEEE access 2018; 6: 6900-6919. doi: 10.1109/ACCESS.2017.2778504
[4] Rahmani AM, Gia TN, Negash B, Anzanpour A, Azimi I et al. Exploiting smart e-health gateways at the edge of healthcare internet-of-things: a fog computing approach. Future Generation Computer Systems 2018; 78(2): 641-658. doi: 10.1016/j.future.2017.02.014
[5] Aazam M, St-Hilaire M, Lung CH, Lambadaris I. Pre-fog: Iot trace based probabilistic resource estimation at fog. In: 13th IEEE Annual, Consumer Communications & Networking Conference (CCNC); Las Vegas, NV, USA; 2016. pp. 12-17.
[6] Mahmud R, Kotagiri R, Buyya R. Fog computing: a taxonomy, survey and future directions. Internet of everything. Springer 2018; 103-130. doi: 10.1007/978-981-10-5861-5_5
[7] Singh SP, Nayyar A, Kumar R, Sharma A. Fog computing: from architecture to edge computing and big data processing. The Journal of Supercomputing 2018; 1-36. doi: 10.1007/s11227-018-2701-2
[8] Jiang Y, Huang A, Tsang DH. Challenges and solutions in fog computing orchestration. IEEE Network 2018; 32(3): 122-129. doi: 10.1109/MNET.2017.1700271
[9] Satyanarayanan M, Bahl V, Caceres R, Davies N. The case for vm-based cloudlets in mobile computing. IEEE pervasive Computing 2009; 8(4): 14-23. doi: 10.1109/MPRV.2009.82
[10] Gupta P, Ghrera SP. Trust and deadline aware scheduling algorithm for cloud infrastructure using ant colony optimization. In: International Conference on Innovation and Challenges in Cyber Security (ICICCS-INBUSH); Noida, India; 2016. pp. 187-191.
[11] Rodriguez MA, Buyya R. Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds. IEEE Transactions on Cloud Computing 2014; 2(2): 222-235. doi: 10.1109/TCC.2014.2314655
[12] Lv J, Wang X, Huang M, Cheng H, Li F. Solving 0-1 knapsack problem by greedy degree and expectation efficiency. Applied Soft Computing 2016; 41: 94-103. doi: 10.1016/j.asoc.2015.11.045
[13] Bittencourt LF, Diaz-Montes J, Buyya R, Rana OF, Parashar M. Mobility-aware application scheduling in fog computing. IEEE Cloud Computing 2017; 4(2): 26-35. doi: 10.1109/MCC.2017.27
[14] Mathew T, Sekaran KC, Jose J. Study and analysis of various task scheduling algorithms in the cloud computing environment. In: International Conference on Advances in Computing, Communications and Informatics (ICACCI); New Delhi, India: IEEE; 2014. pp. 658-664.
[15] Tsai CW, Huang WC, Chiang MH, Chiang MC, Yang CS. A hyper-heuristic scheduling algorithm for cloud. IEEE Transactions on Cloud Computing 2014; 2(2): 236-250. doi: 10.1109/TCC.2014.2315797
[16] Patil N, Aeloor D. A review-different scheduling algorithms in cloud computing environment. In: 11th International Conference on Intelligent Systems and Control (ISCO); Coimbatore, India: IEEE; 2017. pp. 182-185.
[17] Rodriguez MA, Buyya R. A taxonomy and survey on scheduling algorithms for scientific workflows in iaas cloud computing environments. Concurrency and Computation: Practice and Experience 2017; 29(8). doi: 10.1002/cpe.4041
[18] Frincu ME, Genaud S, Gossa J. Comparing provisioning and scheduling strategies for workflows on clouds. In: IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW); Cambridge, MA, USA; 2013. pp. 2101-2110.
[19] Malawski M, Figiela K, Bubak M, Deelman E, Nabrzyski J. Scheduling multilevel deadline-constrained scientific workflows on clouds based on cost optimization. Scientific Programming 2015; 2015: 1-13. doi: 10.1155/2015/680271
[20] Durillo JJ, Prodan R. Multi-objective workflow scheduling in amazon ec2. Cluster computing 2014; 17(2): 169-189. doi: 10.1007/s10586-013-0325-0
[21] Poola D, Ramamohanarao K, Buyya R. Fault-tolerant workflow scheduling using spot instances on clouds. Procedia Computer Science 2014; 29: 523-533. doi: 0.1016/j.procs.2014.05.047
[22] Zhu X, Wang J, Guo H, Zhu D, Yang LT et al. Fault-tolerant scheduling for real-time scientific workflows with elastic resource provisioning in virtualized clouds. IEEE Transactions on Parallel and Distributed Systems 2016; 27(12): 3501-3517. doi: 10.1109/TPDS.2016.2543731
[23] Li C, Bai J, Tang J. Joint optimization of data placement and scheduling for improving user experience in edge computing. Journal of Parallel and Distributed Computing 2019; 125: 93-105. doi: 10.1016/j.jpdc.2018.11.006
[24] Pham XQ, Huh EN. Towards task scheduling in a cloud-fog computing system. In: 18th Asia-Pacific Network Operations and Management Symposium (APNOMS); Kanazawa, Japan: IEEE; 2016. pp. 1-4.
[25] Sun Y, Dang T, Zhou J. User scheduling and cluster formation in fog computing based radio access networks. In: IEEE International Conference on Ubiquitous Wireless Broadband (ICUWB); Nanjing, China; 2016. pp. 1-4.
[26] Chen X, Wang L. Exploring fog computing-based adaptive vehicular data scheduling policies through a compositional formal method—pepa. IEEE Communications Letters 2017; 21(4): 745-748. doi: 10.1109/LCOMM.2016.2647595
[27] Zahaf HE, Benyamina AEH, Olejnik R, Lipari G. Energy-efficient scheduling for moldable real-time tasks on heterogeneous computing platforms. Journal of Systems Architecture 2017; 74: 46-60. doi: 10.1016/j.sysarc.2017.01.002
[28] Lao F, Zhang X, Guo Z. Parallelizing video transcoding using map-reduce-based cloud computing. In: IEEE International Symposium on Circuits and Systems (ISCAS); Seoul, South Korea; 2012. pp. 2905-2908.
[29] Fang W, Zhou W, Li Y, Yao X, Xue F et al. A distributed admm approach for energy-efficient resource allocation in mobile edge computing. Turkish Journal of Electrical Engineering & Computer Sciences 2018; 26(6): 3335-3344. doi: 10.3906/elk-1806-112
[30] Pham XQ, Man ND, Tri NDT, Thai NQ, Huh EN. A cost-and performance-effective approach for task scheduling based on collaboration between cloud and fog computing. International Journal of Distributed Sensor Networks 2017; 13(11): 1-16. doi: 10.1177/1550147717742073
[31] Kamal MB, Javaid N, Naqvi SAA, Butt H, Saif T et al. Heuristic min-conflicts optimizing technique for load balancing on fog computing. In: International Conference on Intelligent Networking and Collaborative Systems, Springer; Bratislava, Slovakia; 2018. pp.207-219.
[32] Xu X, Liu Q, Qi L, Yuan Y, Dou W et al. A heuristic virtual machine scheduling method for load balancing in fogcloud computing. In: IEEE 4th International Conference on Big Data Security on Cloud (BigDataSecurity), IEEE International Conference on High Performance and Smart Computing, (HPSC) and IEEE International Conference on Intelligent Data and Security (IDS); Omaha, NE, USA; 2018. pp. 83-88.
[33] Chen YA, Walters JP, Crago SP. Load balancing for minimizing deadline misses and total runtime for connected car systems in fog computing. In: IEEE International Symposium on Parallel and Distributed Processing with Applications and 2017 IEEE International Conference on Ubiquitous Computing and Communications (ISPA/IUCC); Guangzhou, China; 2017. pp. 683-690.
[34] Yang Y, Wang K, Zhang G, Chen X, Luo X et al. Meets: Maximal energy efficient task scheduling in homogeneous fog networks. IEEE Internet of Things Journal 2018; 5(5): 4076-4087. doi: 10.1109/JIOT.2018.2846644
[35] Venkatraman S, Selvagopal D. An optimized multiobjective cpu job scheduling using evolutionary algorithms. Turkish Journal of Electrical Engineering & Computer Sciences 2018; 26(1): 101-114. doi: 10.3906/elk-1701-22
[36] Singh P, Dutta M, Aggarwal N. A review of task scheduling based on meta-heuristics approach in cloud computing. Knowledge and Information Systems 2017; 52(1): 1-51. doi: 10.1007/s10115-017-1044-2
[37] Sheff I, Magrino T, Liu J, Myers AC, Van Renesse R. Safe serializable secure scheduling: Transactions and the trade-off between security and consistency. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security; Vienna, Austria; 2016. pp. 229-241.
[38] Domanal S, Guddeti RM, Buyya R. A hybrid bio-inspired algorithm for scheduling and resource management in cloud environment. IEEE Transactions on Services Computing 2017. doi: 10.1109/TSC.2017.2679738
[39] Wang T, Wei X, Tang C, Fan J. Efficient multi-tasks scheduling algorithm in mobile cloud computing with time constraints. Peer-to-Peer Networking and Applications 2018; 11(4): 793-807. doi: 10.1007/s12083-017-0561-9
[40] Bitam S, Zeadally S, Mellouk A. Fog computing job scheduling optimization based on bees swarm. Enterprise Information Systems 2017; 12(4): 373-397. doi: 10.1080/17517575.2017.1304579
[41] Rodriguez MA, Buyya R. A responsive knapsack-based algorithm for resource provisioning and scheduling of scientific workflows in clouds. In: IEEE 2015 44th International Conference on Parallel Processing (ICPP); Beijing, China; 2015. pp. 839-848.
[42] Rahim S, Khan SA, Javaid N, Shaheen N, Iqbal Z et al. Towards multiple knapsack problem approach for home energy management in smart grid. In: IEEE 18th International Conference on Network-Based Information Systems (NBiS); Taipei, Taiwan; 2015. pp. 48-52.
[43] Chen S, Wu J, Lu Z. A cloud computing resource scheduling policy based on genetic algorithm with multiple fitness. In: IEEE 2012 12th International Conference on Computer and Information Technology (CIT); Chengdu, China; 2012. pp. 177-184.
[44] Sun Y, Lin F, Xu H. Multi-objective optimization of resource scheduling in fog computing using an improved nsga-ii.Wireless Personal Communications 2018; 102(2): 1369-1385. doi: 10.1007/s11277-017-5200-5
[45] Gai K, Qiu M. Optimal resource allocation using reinforcement learning for iot content-centric services. Applied Soft Computing 2018; 70: 12-21. doi: 10.1016/j.asoc.2018.03.056
[46] Zhang Q, Lin M, Yang LT, Chen Z, Khan SU et al. A double deep q-learning model for energy-efficient edge scheduling. Transactions on Services Computing 2018. doi: 10.1109/TSC.2018.2867482
[47] Calheiros RN, Ranjan R, Beloglazov A, De Rose CAF, Buyya R. Cloudsim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms. Software: Practice and experience 2011; 41(1): 23-50. doi: 10.1002/spe.995
[48] Marler RT, Arora JS. The weighted sum method for multi-objective optimization: new insights. Structural and multidisciplinary optimization 2010; 41(6): 853-862. doi: 10.1007/s00158-009-0460-7
[49] Zao JK, Gan TT, You CK, Méndez SJR, Chung CE et al. Augmented brain computer interaction based on fog computing and linked data. In: IEEE 2014 International Conference on Intelligent Environments (IE); Shanghai, China; 2014. pp. 374-377.