计算机科学 ›› 2020, Vol. 47 ›› Issue (10): 247-255.doi: 10.11896/jsjkx.190900106
胡俊钦1,2, 张佳俊1,2, 黄引豪1,2, 陈星1,2, 林兵2,3
HU Jun-qin1,2, ZHANG Jia-jun1,2, HUANG Yin-hao1,2, CHEN Xing1,2, LIN Bing2,3
摘要： 深度神经网络(Deep Neural Network,DNN)应用对运行设备的性能要求较高,无法直接在计算资源受限的移动设备上运行。通过计算迁移技术将某些计算复杂的神经网络层迁移到资源丰富的边缘或者远程云端上去执行,是一种有效的解决资源受限问题的方法。计算迁移会产生额外的时间开销,如果迁移过程的时延太长,将严重影响用户体验。为此,文中以得到边缘环境下多任务并行调度的最小平均响应时间为目标,首先提出边缘环境下DNN应用的计算迁移调度问题,并对该问题的解设计了评估算法;然后设计了两种调度算法即贪心算法和遗传算法(Genetic Algorithm,GA)来求解问题;最后设置评估实验,在5种不同的边缘环境下对两种算法的性能进行对比分析。实验数据表明,采用所提算法得到的解十分接近最优解。与传统的迁移方案相比,贪心算法能得到平均响应时间更短的调度方案;遗传算法的平均响应时间比贪心算法短,但其运行时间明显更长。实验结果说明,所提两种调度算法能够有效地缩短边缘环境下DNN应用的计算迁移调度的平均响应时间,提高用户体验。
中图分类号:
| [1]CHEN X,JIAO L,LI W,et al.Efficient Multi-User Computation Offloading for Mobile-Edge Cloud Computing [J].IEEE/ACM Transactions on Networking,2015,24(5):2795-2808. [2]KUMAR K,LIU J,LU Y H,et al.A Survey of Computation Offloading for Mobile Systems [J].Mobile Networks & Applications,2013,18(1):129-140. [3]WANG C,LI Z.A Computation Offloading Scheme on Handheld Devices [J].Journal of Parallel & Distributed Computing,2004,64(6):740-746. [4]KANG Y P,HAUSWALD J,GAO C,et al.Neurosurgeon:Collaborative Intelligence Bet-ween the Cloud and Mobile Edge [J].Acm Sigplan Notices,2017,52(4):615-629. [5]JIA M,LIANG W F,XU Z C,et al.QoS-Aware Cloudlet Load Balancing in Wireless Metropolitan Area Networks [J].IEEE Transactions on Cloud Computing,2018,PP(99):1-1. [6]LIU J Y,WANG X W,HUANG M.Research on an Intelligent Local Mobile Cloud Resource Allocation Mechanism[J].Netinfo Security,2016(10):60-68. [7]WANG D L,YI J Y,LI S H,et al.Task Scheduling of Cloud Computing Based on Fusion of Load Balancing and Bat Algorithm[J].Netinfo Security,2017(1):23-28. [8]BHARATI R D,SURADKAR J A.Computation Offloading:Overview,Frameworks and Challenges [J].International Journal of Computer Applications,2016,134(6):28-31. [9]FENG X,DING F,JIE L,et al.Phone2Cloud:Exploiting Computation Offloading for Energy Saving on Smartphones in Mobile Cloud Com-puting [J].Information Systems Frontiers,2014,16(1):95-111. [10]ALAM G R,HASSAN M M,UDDIN M Z,et al.AutonomicComputation Offloading in Mobile Edge for IoT Applications [J].Future Generation Computer Systems,2019,90(1):149-157. [11]MACH P,BECVAR Z.Mobile Edge Computing:A Survey onArchitecture and Com-putation Offloading [J].IEEE Communications Surveys & Tutorials,2017,19(3):1-1. [12]JEONG H J,JEONG I C,LEE H J,et al.Computation Offloading for Machine Learning Web Apps in the Edge Server Environment[C]//2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS).New York:IEEE,2018:1492-1499. [13]JIA M,CAO J,LEI Y.Heuristic Offloading of Concurrent Tasks for Computation-intensive Applications in Mobile Cloud Computing[C]//Computer Communications Workshops.New York:IEEE Press,2014:352-357. [14]MAO Y,ZHANG J,LETAIEF K B,et al.Dynamic Computation Offloading for Mobile-Edge Computing With Energy Harvesting Devices [J].IEEE Journal on Selected Areas in Communications,2016,34(12):3590-3605. [15]LIU J,MAO Y,ZHANG J,et al.Delay Optimal Computation Task Scheduling for Mobile-Edge Computing Systems[C]// IEEE International Symposium on Information Theory.New York:IEEE Press,2016:1451-1455. [16]GUO S,LIU J,YANG Y,et al.Energy-Efficient Dynamic Computation Offloading and Cooperative Task Scheduling in Mobile Cloud Com-puting [J].IEEE Transactions on Mobile Computing,2019,18(2):319-333. [17]ZHANG Y,CHEN X,CHEN Y,et al.Cost Efficient Scheduling for Delay-Sensitive Tasks in Edge Computing System[C]//2018 IEEE International Conference on Services Computing (SCC).New York:IEEE Press,2018:73-80. [18]QI B,WU M,ZHANG L.A DNN-based Object Detection System on Mobile Cloud Computing[C]//2017 17th International Symposium on Communications and Information Technologies (ISCIT).New York:IEEE Press,2017:1-6. [19]OMARA F A,ARAFA M M.Genetic Algorithms for TaskScheduling Problem [J].Journal of Parallel and Distributed Computing,2010,70(1):13-22. [20]WU A S,YU H,JIN S,et al.An Incremental Genetic Algorithm Approach to Multiprocessor Scheduling [J].IEEE Transactions on Parallel and Distributed Systems,2004,15(9):824-834. [21]KWOK Y,AHMAD I.Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors [J].Acm Computing Surveys,1999,31(4):406-471. [22]ZHONG J,HU X,GU M,et al.Comparison of Performance between Different Selection Strategies on SimpleGenetic Algorithms[C]//Computational Intelligence for Modelling,Control and Automation.New York:IEEE Press,2005:1115-1121. [23]UMBARKAR A J,SHETH P D.Crossover Operators in Genetic Algorithms:A Review [J].ICTACT Journal on Soft Computing,2015,6(1):1083-1092. [24]LIM S M,SULTAN A B,SULAIMAN M N,et al.Crossover and Mutation Operators of Genetic Algorithms [J].International Journal of Machine Learning and Computing,2017,7(1):9-12. |
| [1] | 刘兴光, 周力, 刘琰, 张晓瀛, 谭翔, 魏急波. 基于边缘智能的频谱地图构建与分发方法 Construction and Distribution Method of REM Based on Edge Intelligence 计算机科学, 2022, 49(9): 236-241. https://doi.org/10.11896/jsjkx.220400148 |
| [2] | 孙慧婷, 范艳芳, 马孟晓, 陈若愚, 蔡英. VEC中基于动态定价的车辆协同计算卸载方案 Dynamic Pricing-based Vehicle Collaborative Computation Offloading Scheme in VEC 计算机科学, 2022, 49(9): 242-248. https://doi.org/10.11896/jsjkx.210700166 |
| [3] | 于滨, 李学华, 潘春雨, 李娜. 基于深度强化学习的边云协同资源分配算法 Edge-Cloud Collaborative Resource Allocation Algorithm Based on Deep Reinforcement Learning 计算机科学, 2022, 49(7): 248-253. https://doi.org/10.11896/jsjkx.210400219 |
| [4] | 张翀宇, 陈彦明, 李炜. 边缘计算中面向数据流的实时任务调度算法 Task Offloading Online Algorithm for Data Stream Edge Computing 计算机科学, 2022, 49(7): 263-270. https://doi.org/10.11896/jsjkx.210300195 |
| [5] | 李梦菲, 毛莺池, 屠子健, 王瑄, 徐淑芳. 基于深度确定性策略梯度的服务器可靠性任务卸载策略 Server-reliability Task Offloading Strategy Based on Deep Deterministic Policy Gradient 计算机科学, 2022, 49(7): 271-279. https://doi.org/10.11896/jsjkx.210600040 |
| [6] | 袁昊男, 王瑞锦, 郑博文, 吴邦彦. 基于Fabric的电子病历跨链可信共享系统设计与实现 Design and Implementation of Cross-chain Trusted EMR Sharing System Based on Fabric 计算机科学, 2022, 49(6A): 490-495. https://doi.org/10.11896/jsjkx.210500063 |
| [7] | 杨浩雄, 高晶, 邵恩露. 考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题 Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery 计算机科学, 2022, 49(6A): 191-198. https://doi.org/10.11896/jsjkx.210400005 |
| [8] | 方韬, 杨旸, 陈佳馨. D2D辅助移动边缘计算下的卸载策略优化 Optimization of Offloading Decisions in D2D-assisted MEC Networks 计算机科学, 2022, 49(6A): 601-605. https://doi.org/10.11896/jsjkx.210200114 |
| [9] | 刘漳辉, 郑鸿强, 张建山, 陈哲毅. 多无人机使能移动边缘计算系统中的计算卸载与部署优化 Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems 计算机科学, 2022, 49(6A): 619-627. https://doi.org/10.11896/jsjkx.210600165 |
| [10] | 谢万城, 李斌, 代玥玥. 空中智能反射面辅助边缘计算中基于PPO的任务卸载方案 PPO Based Task Offloading Scheme in Aerial Reconfigurable Intelligent Surface-assisted Edge Computing 计算机科学, 2022, 49(6): 3-11. https://doi.org/10.11896/jsjkx.220100249 |
| [11] | 周天清, 岳亚莉. 超密集物联网络中多任务多步计算卸载算法研究 Multi-Task and Multi-Step Computation Offloading in Ultra-dense IoT Networks 计算机科学, 2022, 49(6): 12-18. https://doi.org/10.11896/jsjkx.211200147 |
| [12] | 彭冬阳, 王睿, 胡谷雨, 祖家琛, 王田丰. 视频缓存策略中QoE和能量效率的公平联合优化 Fair Joint Optimization of QoE and Energy Efficiency in Caching Strategy for Videos 计算机科学, 2022, 49(4): 312-320. https://doi.org/10.11896/jsjkx.210800027 |
| [13] | 田冰川, 田臣, 周宇航, 陈贵海, 窦万春. 减少Hadoop集群中网络队头阻塞的调度算法 Reducing Head-of-Line Blocking on Network in Hadoop Clusters 计算机科学, 2022, 49(3): 11-22. https://doi.org/10.11896/jsjkx.210900117 |
| [14] | 张海波, 张益峰, 刘开健. 基于NOMA-MEC的车联网任务卸载、迁移与缓存策略 Task Offloading,Migration and Caching Strategy in Internet of Vehicles Based on NOMA-MEC 计算机科学, 2022, 49(2): 304-311. https://doi.org/10.11896/jsjkx.210100157 |
| [15] | 林潮伟, 林兵, 陈星. 边缘环境下基于模糊理论的科学工作流调度研究 Study on Scientific Workflow Scheduling Based on Fuzzy Theory Under Edge Environment 计算机科学, 2022, 49(2): 312-320. https://doi.org/10.11896/jsjkx.201000102 |
|
||
首页