Scheduling of Modules in Fog Computing by Knapsack-Based Symbiotic Organisms Search
Subject Areas : electrical and computer engineering
1 -
2 -
Keywords: Symbiotic organism searchschedulingknapsackfog computing,
Abstract :
Wireless sensor networks have limitations such as processing power, storage resources, and time delay in data transfer to the cloud. The cloud computing by the development of cloud-based services to the edge of the network reduces traffic and delays, so these types of networks are used in many systems, such as medical care, wearable devices, transportation systems and smart cities. Task scheduling techniques in fog computing are considered to be NP-hard issues. Applications require resources to run. Network fog devices are close to the sensors and the cloud and have the required processing power to run the applications. Each fog device can be used to run resource allocation policies. In this paper, we present an optimized Knapsack-based method optimized by symbiotic organism search to allocate resources appropriately to tasks in fog network. The proposed method is simulated in the iFogsim as a developed library from Cloudsim for fog computing. The results indicate improvement in energy consumption, resource consumption, and execution cost of the network. The proposed method is better than FCFS and Knapsack methods.
[1] H. Gupta, A. V. Dastjerdi, S. K. Ghosh, and R. Buyya, "IFogsim: a toolkit for modeling and simulation of resource management techniques in internet of things, edge and fog computing environments," Software: Practice and Experience, vol. 47, no. 9, pp. 1275-1296, Jun. 2017.
[2] M. Aazam, M. St-Hilaire, C. H. Lung, and I. Lambadaris, "Pre-fog: Iot trace based probabilistic resource estimation at fog," in Proc. 13th IEEE Annual. Consumer Communications and Networking Conf., CCNC'16, pp. 12-17, Jan. 2016.
[3] A. M. Rahmani, T. N. Gia, B. Negash, A. Anzanpour, I. Azimi, M. Jiang, and P. Liljeberg, "Exploiting smart e-health gateways at the edge of healthcare internet-of-things: a fog computing approach," Future Generation Computer Systems, vol. 78, no. 2, pp. 641-658, Feb. 2017.
[4] M. Satyanarayanan, P. Bahl, R. Caceres, and N. Davies, "The case for vm-based cloudlets in mobile computing," IEEE Pervasive Computing, vol. 8, no. 4, pp. 14-23, Oct. 2009.
[5] P. Gupta and S. P. Ghrera, "Trust and deadline aware scheduling algorithm for cloud infrastructure using ant colony optimization," in Proc. IEEE Int. Conf. on Innovation and Challenges in Cyber Security, ICICCS-INBUSH'16, pp. 187-191, Noida, India, 3-5 Feb. 2016.
[6] M. A. Rodriguez and R. Buyya, "Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds," IEEE Trans. on Cloud Computing, vol. 2, no. 2, pp. 222-235, Apr. 2014.
[7] J. Lv, X. Wang, M. Huang, H. Cheng, and F. Li, "Solving 0-1 knapsack problem by greedy degree and expectation efficiency," Applied Soft Computing, vol. 41, pp. 94-103, Apr. 2016.
[8] M. Y. Cheng and D. Prayogo, "Symbiotic organisms search: a new metaheuristic optimization algorithm," Computers & Structures, vol. 139, vol. 139, pp. 98-112, Jul. 2014.
[9] M. A. Rodriguez and R. Buyya, "A taxonomy and survey on scheduling algorithms for scientific workflows in iaas cloud computing environments," Concurrency and Computation: Practice and Experience, vol. 29, no. 8, pp. 1-23, Dec. 2017.
[10] M. E. Frincu, S. Genaud, and J. Gossa, "Comparing provisioning and scheduling strategies for workflows on clouds," in Proc. IEEE 27th Int. Parallel and Distributed Processing Symp. Workshops and PhD Forum, IPDPSW'13, pp. 2101-2110, Cambridge, MA, USA, 20-24 May. 2013.
[11] M. Malawski, K. Figiela, M. Bubak, E. Deelman, and J. Nabrzyski, "Scheduling multilevel deadline-constrained scientific workflows on clouds based on cost optimization," Scientific Programming, vol. 2015, pp. 1-13, Jan. 2015.
[12] J. J. Durillo and R. Prodan, "Multi-objective workflow scheduling in amazon ec2," Cluster Computing, vol. 17, no. 2, pp. 169-189, Jun. 2014.
[13] D. Poola, K. Ramamohanarao, and R. Buyya, "Fault-tolerant workflow scheduling using spot instances on clouds," Procedia Computer Science, vol. 29, pp. 523-533, Jun. 2014.
[14] X. Zhu, J. Wang, H. Guo, D. Zhu, L. T. Yang, and L. Liu, "Fault-tolerant scheduling for real-time scientific workflows with elastic resource provisioning in virtualized clouds," IEEE Trans. on Parallel and Distributed Systems, vol. 27, no. 12, pp. 3501-3517, Mar. 2016.
[15] L. F. Bittencourt, J. Diaz-Montes, R. Buyya, O. F. Rana, and M. Parashar, "Mobility-aware application scheduling in fog computing," IEEE Cloud Computing, vol. 4, no. 2, pp. 26-35, Apr. 2017.
[16] X. Q. Pham and E. N. Huh, "Towards task scheduling in a cloud-fog computing system," in Proc. 18th Asia-Pacific IEEE Network Operations and Management Symp., APNOMS', 4 pp., Kanazawa, Japan, 5-7 Oct. 2016.
[17] Y. Sun, T. Dang, and J. Zhou, "User scheduling and cluster formation in fog computing based radio access networks," in Proc. IEEE Int. Conf. on Ubiquitous Wireless Broadband ICUWB, 4 pp., Nanjing, China, 16-19 Oct. 2016.
[18] X. Chen and L. Wang, "Exploring fog computing-based adaptive vehicular data scheduling policies through a compositional formal methodpepa," IEEE Communications Letters, vol. 21, no. 4, pp. 745-748, Jan. 2017.
[19] H. E. Zahaf, A. E. H. Benyamina, R. Olejnik, and G. Lipari, "Energy efficient scheduling for moldable real-time tasks on heterogeneous computing platforms," J. of Systems Architecture, vol. 74, pp. 46-60, Mar. 2017.
[20] S. Bitam, S. Zeadally, and A. Mellouk, "Fog computing job scheduling optimization based on bees swarm," Enterprise Information Systems, vol. vol. 12 no. 4, pp. 373-397, Apr. 2017.
[21] T. Wang, X. Wei, C. Tang, and J. Fan, "Efficient multi-tasks scheduling algorithm in mobile cloud computing with time constraints," Peer-to-Peer Networking and Applications, 11, no. 4, pp. 793-807, Jul. 2017.
[22] F. Lao, X. Zhang, and Z. Guo, "Parallelizing video transcoding using map-reduce-based cloud computing," in Proc. IEEE Int.Symp.on Circuits and Systems, ISCAS'12, pp. 2905-2908, Seoul, South Korea, 20-23 May 2012.
[23] M. A. Rodriguez and R. Buyya, "A responsive knapsack-based algorithm for resource provisioning and scheduling of scientific workflows in clouds," in Proc. 44th IEEE Int. Conf. on Parallel Processing, ICPP'15, pp. 839-848, Beijing, China, 1-4 Sept. 2015.
[24] S. Rahim, et al., "Towards multiple knapsack problem approach for home energy management in smart grid," in Proc. 18th IEEE Int. Conf. on Network-Based Information Systems, NBiS'15, pp. 48-52, Taipei, Taiwan, 2-4 Sept. 2015.
[25] S. Chen, J. Wu, and Z. Lu, "A cloud computing resource scheduling policy based on genetic algorithm with multiple fitness," in Proc. 12th IEEE Int. Conf. on Computer and Information Technology, CIT'12, pp. 177-184, Chengdu, China, 27-29 Oct. 2012.
[26] Q. Ni, A. B. Garcia Hernando, and I. P. de la Cruz, "The elderlys independent living in smart homes: a characterization of activities and sensing infrastructure survey to facilitate services development," Sensors, vol. 15, no. 5, pp. 11312-11362, May 2015.
[27] R. N. Calheiros, R. Ranjan, A. Beloglazov, C. A. De Rose, and R. Buyya, "Cloudsim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms," Software: Practice and Experience, vol. 41, no. 1, pp. 23-50, Aug. 2011.