Task assignment method based on cloud-fog cooperative model

doi:10.11772/j.issn.1001-9081.2018071642

Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (1): 8-14.DOI: 10.11772/j.issn.1001-9081.2018071642

• 2018 CCF Annual Conference on Distributed and Parallel Computing Systems (DPCS 2018) • Previous Articles Next Articles

Task assignment method based on cloud-fog cooperative model

LIU Pengfei, MAO Yingchi, WANG Longbao

College of Computer and Information, Hohai University, Nanjing Jiangsu 211100, China

Received:2018-07-19 Revised:2018-08-11 Online:2019-01-10 Published:2019-01-21
Supported by:
This work is partially supported by the National Key Technology Research and Development Program of the Ministry of Science and Technology of China (2016YFC0400910, 2018YFC0407905, 2018YFC0407105), the Fundamental Research Funds for the Central Universities (2017B16814, 2017B20914), the Key Technology Project of China Huaneng Group (HNKJ17-21).

基于云雾协作模型的任务分配方法

刘鹏飞, 毛莺池, 王龙宝

河海大学计算机与信息学院, 南京 211100

通讯作者: 刘鹏飞
作者简介:刘鹏飞(1995-),男,山东滨州人,硕士研究生,主要研究方向:分布式计算与并行处理;毛莺池(1976-),女,上海人,教授,博士,CCF会员,主要研究方向:分布计算与并行处理、分布式数据管理;王龙宝(1977-),男,江苏盐城人,讲师,主要研究方向:智能数据处理。
基金资助:
“十三五”国家重点研发计划项目（2016YFC0400910，2018YFC0407905，2018YFC0407105）；中央高校业务费资助项目（2017B16814，2017B20914）；华能集团重点研发项目（HNKJ17-21）。

Abstract

Abstract:

To realize reasonable allocation and scheduling of mobile user task requests under cloud and fog collaboration, a task assignment algorithm based on cloud-fog collaboration model, named IGA (Improved Genetic Algorithm), was proposed. Firstly, individuals were coded in the way of mixed coding, and initial population was generated randomly. Secondly, the objective function was set as the cost of service providers. Then select, cross, and mutate were used to produce new qualified individuals. Finally, the request type in a chromosome was assigned to the corresponding resource node and iteration counter was updated until the iteration was completed. The simulation results show that compared with traditional cloud model, cloud-frog collaboration model reduces the time delay by nearly 30 seconds, reduces Service Level Objective (SLO) violation rate by nearly 10%, and reduces the cost of service providers.

Key words: cloud computing, fog calculating, task allocation, task scheduling, Genetic Algorithm (GA)

摘要：

针对在云雾协作下实现移动用户任务请求的合理分配与调度的问题，提出了一种基于云雾协作模型的任务分配算法——IGA。首先，采用混合编码的方式对个体进行编码，并采用随机的方式产生初始种群；其次设定服务商的花费作为目标函数；然后进行选择、交叉、变异操作产生出符合条件的新个体；最后，根据染色体中的任务请求类型分配到相应的资源节点上，并更新迭代计数器，直到迭代完成。仿真结果表明，在处理移动用户请求时，与传统的云模型相比，云雾协作模型在时延上降低了近30 s，服务水平目标（SLO）违规率上降低了约10个百分比，在服务提供商花费上亦有所减少。

关键词: 云计算, 雾计算, 任务分配, 任务调度, 遗传算法

CLC Number:

TP393.027

LIU Pengfei, MAO Yingchi, WANG Longbao. Task assignment method based on cloud-fog cooperative model[J]. Journal of Computer Applications, 2019, 39(1): 8-14.

刘鹏飞, 毛莺池, 王龙宝. 基于云雾协作模型的任务分配方法[J]. 计算机应用, 2019, 39(1): 8-14.

References

[1] The World Telecommunication Standardization Assembly. ITU.WTSA-16:setting the standard[R]. Yasmine Hammamet:WTSA-16, 2016:1-9.
[2] CHIANG M, ZHANG T. Fog and IoT:an overview of research opportunities[J]. IEEE Internet of Things Journal, 2017, 3(6):854-864.
[3] SARKAR S, MISRA S. Theoretical modelling of fog computing:a green computing paradigm to support IoT applications[J]. IET Networks, 2016, 5(2):23-29.
[4] 北京物联远信息技术有限公司.一种面向物联网的雾计算架构:中国,201511019375.3[P].2016-05-25. (Beijing Wulianyuan Information Technology Co., Ltd. A fog computing architecture for the Internet of Things:China, 201511019375.3[P].2016-05-25.)
[5] DENG R, LU R, LAI C, et al. Optimal workload allocation in fog-cloud computing towards balanced delay and power consumption[J]. IEEE Internet of Things Journal, 2016, 3(6):1171-1181.
[6] HE J, CHENG P, SHI L, et al. Time synchronization in WSNs:a maximum-value-based consensus approach[J]. IEEE Transactions on Automatic Control, 2014, 59(3):660-675.
[7] LI D, SUN X L. Nonlinear Integer Programming[M]. Berlin:Springer, 2006:70-82.
[8] KUHN H W. The Hungarian method for the assignment problem[J]. Naval Research Logistics, 2010, 52(1):7-21.
[9] SONG N N, GONG C, AN X S, et al. Fog computing dynamic load balancing mechanism based on graph repartitioning[J]. China Communications, 2016, 13(3):156-164.
[10] CARDELLINI V, GRASSI V, PRESTI F L, et al. On QoS-aware scheduling of data stream applications over fog computing infrastructures[C]//Proceedings of the 2015 IEEE Symposium on Computers and Communication. Piscataway, NJ:IEEE, 2016:271-276.
[11] OUEIS J, STRINATI E C, BARBAROSSA S. The fog balancing:load distribution for small cell cloud computing[C]//Proceedings of the 2015 IEEE 81st Vehicular Technology Conference. Piscataway, NJ:IEEE, 2015:1-6.
[12] 韩奎奎,谢在鹏,吕鑫.一种基于改进遗传算法的雾计算任务调度策略[J].计算机科学,2018,45(4):137-142.(HAN K K, XIE Z P, LYU X. A fog computing task scheduling strategy based on improved genetic algorithm[J]. Computer Science, 2018,45(4):137-142.)
[13] BITAM S, ZEADALLY S, MELLOUK A. Fog computing job scheduling optimization based on bees swarm[J]. Enterprise Information Systems, 2018, 12(4):373-379.
[14] WU L, GARG S K, VERSTEEG S, et al. SLA-based resource provisioning for hosted software-as-a-service applications in cloud computing environments[J]. IEEE Transactions on Services Computing, 2014, 7(3):465-485.
[15] 胡志刚,陈俊.网格工作流中一种扩展的QD-Sufferage调度算法[J].计算机应用研究,2008,25(5):1504-1506.(HU Z G, CHEN J. An extended QD-sufferage scheduling algorithm in grid workflow[J]. Application Research of Computers, 2008, 25(5):1504-1506.)
[16] WEN Z, YANG R, GARRAGHAN P, et al. Fog orchestration for IoT services:issues, challenges and directions[J]. IEEE Internet Computing, 2016, 21(2):16-24.
[17] 王小平,曹立明.遗传算法:理论、应用与软件实现[M].西安:西安交通大学出版社,2002:123-130.(WANG X P, CAO L M. Genetic Algorithm:Theory, Application and Software Realization[M]. Xi'an:Xi'an Jiaotong University Press, 2002:123-130.)
[18] 王洪燕.云环境下基于预测的资源调度研究[D].北京:华北电力大学(北京),2017:31-38.(WANG H Y. Prediction-based resource scheduling in cloud environment[D]. Beijing:North China Electric Power University (Beijing), 2017:31-38.)
[19] 周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,1999:20-33.(ZHOU M, SUN S D. Principle and Application of Genetic Algorithm[M]. Beijing:National Defense Industry Press, 1999:20-33.)
[20] 程冬梅,李志.基于雾计算的医院信息服务系统[J].计算机科学,2015,42(7):170-173.(CHENG D M, LI Z. Hospital information service system based on fog computing[J]. Computer Science, 2015, 42(7):170-173.)
[21] 贺晓丽.一种用于任务调度的广义遗传算法[J].计算机工程,2010,36(17):184-186.(HE X L. A generalized genetic algorithm for task scheduling[J].Computer Engineering, 2010, 36(17):184-186.)
[22] 陈玉兰,郑骏,胡文心.一种多QoS约束的网格资源调度算法[J].华东师范大学学报(自然科学版),2009(1):111-116.(CHEN Y L, ZHENG J, HU W X. A multi-QoS constrained grid resource scheduling algorithm[J]. Journal of East China Normal University (Natural Science Edition), 2009(1):111-116.)

Task assignment method based on cloud-fog cooperative model

基于云雾协作模型的任务分配方法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	ZHANG Wenqiang, XING Zheng, YANG Weidong. Hybrid particle swarm optimization with multi-region sampling strategy to solve multi-objective flexible job-shop scheduling problem [J]. Journal of Computer Applications, 2021, 41(8): 2249-2257.
[2]	ZHANG Meng, GUO Jianquan. Channel structure choice of closed-loop supply chain under uncertain demand and recovery [J]. Journal of Computer Applications, 2021, 41(7): 2100-2107.
[3]	CHEN Jiahao, YIN Xinchun. Traceable and revocable ciphertext-policy attribute-based encryption scheme based on cloud-fog computing [J]. Journal of Computer Applications, 2021, 41(6): 1611-1620.
[4]	GE Lina, HU Yugu, ZHANG Guifen, CHEN Yuanyuan. Reverse hybrid access control scheme based on object attribute matching in cloud computing environment [J]. Journal of Computer Applications, 2021, 41(6): 1604-1610.
[5]	LI Jin, WANG Feng, YANG Shenyu. Freight routing optimization model and algorithm of battery-swapping electric vehicle [J]. Journal of Computer Applications, 2021, 41(6): 1792-1798.
[6]	YANG Ling, JIANG Chunmao. Strategy of energy-aware virtual machine migration based on three-way decision [J]. Journal of Computer Applications, 2021, 41(4): 990-998.
[7]	ZHOU Meiling, CHEN Huaili. Fuzzy multi-objective charging scheduling algorithm for electric vehicle based on load balance [J]. Journal of Computer Applications, 2021, 41(4): 1192-1198.
[8]	MA Xiaomei, HE Fei. Label printing production scheduling technology based on improved genetic algorithm [J]. Journal of Computer Applications, 2021, 41(3): 860-866.
[9]	WANG Binrong, TAN Dailun, ZHENG Bochuan. Solving auto part spraying sequence by transforming to traveling salesman problem and genetic algorithm [J]. Journal of Computer Applications, 2021, 41(3): 881-886.
[10]	RAN Jiamin, NI Zhiwei, PENG Peng, ZHU Xuhui. Task allocation strategy considering service quality of spatial crowdsourcing workers and its glowworm swarm optimization algorithm solution [J]. Journal of Computer Applications, 2021, 41(3): 794-802.
[11]	Fan PING, Xiaochun TANG, Yanyu PAN, Zhanhuai LI. Scheduling strategy of irregular tasks on graphics processing unit cluster [J]. Journal of Computer Applications, 2021, 41(11): 3295-3301.
[12]	Xiaoling SUN, Guang YANG, Yanping SHEN, Qiuge YANG, Tao CHEN. Searchable encryption scheme based on splittable inverted index [J]. Journal of Computer Applications, 2021, 41(11): 3288-3294.
[13]	YANG Wei, LI Ran, ZHANG Kun. Task allocation optimization for automated guided vehicles based on variable neighborhood simulated annealing algorithm [J]. Journal of Computer Applications, 2021, 41(10): 3056-3062.
[14]	HUANG Xiaoxiang, HU Yongmei, WU Dan, REN Lijie. Early identification and prediction of abnormal carotid arteries based on variational autoencoder [J]. Journal of Computer Applications, 2021, 41(10): 3082-3088.
[15]	LYU Jiayu, ZHU Zhirong, YAO Zhiqiang. Two-channel dynamic data encryption strategy in cloud computing environment [J]. Journal of Computer Applications, 2020, 40(8): 2268-2273.