计算机科学 ›› 2018, Vol. 45 ›› Issue (4): 94-99.doi: 10.11896/j.issn.1002-137X.2018.04.014
• 2017年全国理论计算机科学学术年会 • 上一篇 下一篇
史雯隽,武继刚,罗裕春
SHI Wen-jun, WU Ji-gang and LUO Yu-chun
摘要: 计算量较大的应用程序由于需要大量的能耗,因此在电池容量有限的移动设备上运行时十分受限。云计算迁移技术是保证此类应用程序在资源有限的设备上运行的主流方法。针对无线网络中应用程序任务图的调度和迁移问题,提出了一种快速高效的启发式算法。该算法将能够迁移到云端的任务都安排在云端完成这种策略作为初始解,通过逐次计算可迁移任务在移动端运行的能耗节省量,依次将节省量最大的任务迁移到移动端,并依据任务间的通讯时间及时更新各个任务的能耗节省量。为了寻找全局最优解,构造了适用于此问题的禁忌搜索算法,给出了相应的编码方法、禁忌表、邻域解以及算法终止准则。构造的禁忌搜索算法以提出的启发式解为初始解进行全局搜索,并实现对启发解的进一步优化。通过 实验 将所提方法与无迁移、随机迁移、饱和迁移3类算法进行对比,结果表明提出的启发式算法能够快速有效地给出能耗更小的解。例如,在宽度为10的任务图上,当深度为8时,无迁移、随机迁移与饱和迁移的能耗分别为5461、3357和2271能量单位,而给出的启发解对应的能耗仅为2111。在此基础上禁忌搜索算法又将其能耗降低到1942, 这进一步说明了提出的启发式算法能够产生高质量的近似解。
[1] DINH H T,LEE C,NIYATO D,et al.A survey of mobile cloud computing:architecture,applications,and approaches [J].Wireless Communications & Mobile Computing,2013,13(18):1587-1611. [2] BARBAROSSA S,SARDELLITTI S,LORENZO P D.Communicating While Computing:Distributed mobile cloud computing over 5G heterogeneous networks [J].IEEE Signal Processing Magazine,2014,31(6):45-55. [3] KUMAR K,LU Y H.Cloud Computing for Mobile Users:Can Offloading Computation Save Energy? [M].IEEE Computer Society Press,2010. [4] VALLINA-RODRIGUEZ N,CROWCROFT J.Energy Management Techniques in Modern Mobile Handsets [J].IEEE Communications Surveys & Tutorials,2013,15(1):179-198. [5] KEPHART J O,CHESS D M.The Vision of Autonomic Computing [J].Computer,2003,36(1):41-50. [6] SHU P,LIU F,JIN H,et al.eTime:Energy-efficient transmission between cloud and mobile devices[C]∥INFOCOM,2013 Proceedings IEEE.IEEE,2013:195-199. [7] LIN Y D,CHU T H,LAI Y C,et al.Time-and-Energy-Aware Computation Offloading in Handheld Devices to Coprocessors and Clouds [J].IEEE Systems Journal,2015,9(2):393-405. [8] ZHANG W,WEN Y,GUAN K,et al.Energy-Optimal Mobile Cloud Computing under Stochastic Wireless Channel [J].IEEE Transactions on Wireless Communications,2013,12(9):4569-4581. [9] MAHMOODI S E,SUBBALAKSHMI K P,SAGAR V.Cloudoffloading for multi-radio enabled mobile devices[C]∥IEEE International Conference on Communications.IEEE,2015:5473-5478. [10] WU H,WANG Q,WOLTER K.Tradeoff between performance improvement and energy saving in mobile cloud offloading systems[C]∥IEEE Conference on Communications Workshops.IEEE,2013:728-732. [11] CUERVO E,BALASUBRAMANIAN A,CHO D K,et al.MAUI:making last longer with code offload[C]∥International Conference on Mobile Systems,Applications,and Services.DBLP,2010:49-62. [12] KOSTA S,AUCINAS A,HUI P,et al.ThinkAir:Dynamic resource allocation and parallel execution in the cloud for mobile code offloading[C]∥INFOCOM,2012 Proceedings IEEE.IEEE,2012:945-953. [13] ZHANG W,WEN Y,WU D O.Collaborative Task Execution in Mobile Cloud Computing Under a Stochastic Wireless Channel [J].IEEE Transactions on Wireless Communications,2015,14(1):81-93. [14] HUANG D,WANG P,NIYATO D.ADynamic Offloading Algorithm for Mobile Computing [J].IEEE Transactions on Wireless Communications,2012,11(6):1991-1995. [15] CHUN B G,IHM S,MANIATIS P,et al.Clone Cloud:elastic execution between mobile device and cloud[C]∥Conference on Computer Systems.ACM,2011:301-314. [16] MAHMOODI S E,SUBBALAKSHMI K P,SAGAR V.Cloud offloading for multi-radio enabled mobile devices[C]∥IEEE International Conference on Communications.IEEE,2015:5473-5478. [17] MAHMOODI S E,UMA R N,SUBBALAKSHMI K P.Optimal Joint Scheduling and Cloud Offloading for Mobile Applications[J].IEEE Transactions on Cloud Computing,2016,PP(99):1. [18] BALAKRISHNAN P,THAM C K.Energy-Efficient Mappingand Scheduling of Task Interaction Graphs for Code Offloading in Mobile Cloud Computing[C]∥IEEE/ACM International Conference on Utility and Cloud Computing.IEEE,2014:34-41. [19] KOVACHEV D,YU T,KLAMMA R.Adaptive ComputationOffloading from Mobile Devices into the Cloud[C]∥International Symposium on Parallel and Distributed Processing with Applications.IEEE,2012:784-791. [20] NIR M,MATRAWY A,ST-HILAIRE M.An energy optimizing scheduler for mobile cloud computing environments[C]∥IEEE INFOCOM 2014-IEEE Conference on Computer Communications Workshops.IEEE,2014:404-409. [21] BARBAROSSA S,SARDELLITTI S,LORENZO P D.Computation offloading for mobile cloud computing based on wide cross-layer optimization[C]∥Future Network and Mobile Summit.IEEE,2013:1-10. [22] RUBIN P..http://orinanobworld.blogspot.de/2010/10/binary-variables-and-quadratic-terms.html. |
No related articles found! |
|