计算机科学 ›› 2022, Vol. 49 ›› Issue (7): 263-270.doi: 10.11896/jsjkx.210300195
张翀宇, 陈彦明, 李炜
ZHANG Chong-yu, CHEN Yan-ming, LI Wei
摘要： 近年来,随着物联网(Internet of Things,IoT)技术的发展,其应用场景呈爆炸式增长,这类应用一般具有时延敏感性和资源受限性。如何在有限的资源环境下实现任务的实时分配是当前的一个研究热点,而将这些有限的计算资源动态分配给实时任务,一般来说是一个NP-hard的组合优化问题。为解决此问题,设计了一种基于李雅普诺夫优化的实时调度算法,在保持虚拟队列稳定的情况下优化长期平均总能耗和总效用。首先在计算资源和通信资源约束下建立联合总能耗和加权总效用的优化模型,该模型包含两层虚拟缓冲队列,通过端到端(Device-to-Device,D2D)的调度方式进行任务卸载;然后基于李雅普诺夫优化,将长期平均总能耗和总效用的联合优化问题转化为一系列实时优化问题,为此还设计了一种基于贪心的设备匹配算法。数值实验的结果显示,该算法的效果比随机法所能达到的最好情况提升了8.6%,并且在不同连接概率下其效果逼近穷举法。
中图分类号:
| [1]WANG B Y.Review on internet of things[J].Journal of Electronic Measurement and Instrumentation,2009,23(12):1-7. [2]SHI W S,SUN H,CAO J,et al.Edge Computing-An Emerging Computing Model for the Internet of Everything Era[J].Journal of Computer Research and Development,2017,54(5):907-924. [3]XIE R C,LIAN X F,JIA Q M,et al.Survey on computation offloading in mobile edge computing[J].Journal on Communications,2018,39(11):138-155. [4]BEIGI N K,PARTOV B,FAROKHI S.Real-time cloud robotics in practical smart city applications[C]//IEEE 2017 IEEE 28th Annual International Symposium on Personal,Indoor,and Mobile Radio Communications (PIMRC).Montreal,Canada,2017:1-5. [5]GUO M,LI L,GUAN Q.Energy-Efficient and Delay-Guaran-teed Workload Allocation in IoT-Edge-Cloud Computing Systems[J].IEEE Access,2019,7(99):78685-78697. [6]CHEN Y,YANG T,LI C,et al.A Binarized Segmented ResNet Based on Edge Computing for Re-Identification[J].Sensors,2020,20(23):1-19. [7]LI Z,ZHANG X.Resource Allocation and Offloading Decision of Edge Computing for Reducing Core Network Congestion[J].Computer Science,2021,48(3):281-288. [8]KUMAR K,LU Y H.Cloud computing for mobile users:Can offloading computation save energy?[J].Computer,2010(4):51-56. [9]BARBERA M V,KOSTA S,MEI A,et al.To Offload or Not to Offload?The Bandwidth and Energy Costs of Mobile Cloud Computing[C]//Proceedings of IEEE INFOCOM.Turin,Italy,2013. [10]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. [11]MAO Y,ZHANG J,SONG S H,et al.Stochastic Joint Radioand Computational Resource Management for Multi-User Mobile-Edge Computing Systems[J].IEEE Transactions on Wireless Communications 2017,16(9):5994-6009. [12]LI G S,WANG J P,WU J H,et al.Data processing delay optimization in mobile edge computing[J/OL].Wireless Communications and Mobile Computing,2018:1-9.https://www.hindawi.com/journals/wcmc/2018/6897523/. [13]LI N,MARTINEZ-ORTEGA J F,DIAZ V H J I A.Distributed power control for interference-aware multi-user mobile edge computing:A game theory approach[J].IEEE Access,2018,6:36105-36114. [14]SAHNI Y,CAO J,ZHANG S,et al.Edge Mesh:A new paradigm to enable distributed intelligence in Internet of Things[J].IEEE Access,2017,5:16441-16458. [15]FORTUNA C,GALE T.Streaming Data Processing for IoT[M].John Wiley & Sons,Ltd,2020. [16]ARRIBAS E,MANCUSO V.Achieving Per-Flow Satisfaction with Multi-Path D2D[J].Ad Hoc Networks,2020(106):1-16. [17]ZHANG Z,WU Y,CHU X,et al.Energy-Efficient Transmission Rate Selection and Power Control for Relay-Assisted Device-to-Device Communications Underlaying Cellular Networks[J].IEEE Wireless Communication Letters,2020,9(8):1133-1136. [18]BACCARELLI E,NARANJO P G V,SHOJAFAR M,et al.Energy and delay-efficie nt dynamic queue management in TCP/IP virtualized data centers[J].Computer Communications,2016,102:1-37. [19]LIU J,LUO K,ZHOU Z,et al.ERP:Edge Resource Pooling for Data Stream Mobile Computing[J].IEEE Internet of Things Journal,2019,6(3):4355-4368. [20]JIA Q,XIE R,TANG Q,et al.Energy-Efficient ComputationOffloading in 5G Cellular Networks with Edge Computing and D2D Communications[J].IET Communications,2019,13(8):1122-1130. [21]PU L,CHEN X,XU J,et al.D2D Fogging:An Energy-Efficient and Incentive-Aware Task Offloading Framework via Network-Assisted D2D Collaboration[J].IEEE Journal on Selected Areas in Communications,2016,34(12):3887-3901. [22]MICHAEL N.Stochastic Network Optimization with Applica-tion to Communication and Queueing Systems [M].Morgan & Claypool,2010. [23]WIMP J.Pi and the AGM:A study in analytic number theory and computational complexity (Jonathan M.Borwein and Peter B.Borwein)[J].SIAM Review,1988,30(3):530-533. |
| [1] | 孙慧婷, 范艳芳, 马孟晓, 陈若愚, 蔡英. VEC中基于动态定价的车辆协同计算卸载方案 Dynamic Pricing-based Vehicle Collaborative Computation Offloading Scheme in VEC 计算机科学, 2022, 49(9): 242-248. https://doi.org/10.11896/jsjkx.210700166 |
| [2] | 刘漳辉, 郑鸿强, 张建山, 陈哲毅. 多无人机使能移动边缘计算系统中的计算卸载与部署优化 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 |
| [3] | 张翕然, 刘万平, 龙华. 物联网僵尸网络病毒的传播动力学模型与分析 Dynamic Model and Analysis of Spreading of Botnet Viruses over Internet of Things 计算机科学, 2022, 49(6A): 738-743. https://doi.org/10.11896/jsjkx.210300212 |
| [4] | 周天清, 岳亚莉. 超密集物联网络中多任务多步计算卸载算法研究 Multi-Task and Multi-Step Computation Offloading in Ultra-dense IoT Networks 计算机科学, 2022, 49(6): 12-18. https://doi.org/10.11896/jsjkx.211200147 |
| [5] | 董丹丹, 宋康. RIS辅助双向物联网通信系统性能分析 Performance Analysis on Reconfigurable Intelligent Surface Aided Two-way Internet of Things Communication System 计算机科学, 2022, 49(6): 19-24. https://doi.org/10.11896/jsjkx.220100064 |
| [6] | 沈家芳, 钱丽萍, 杨超. 面向集能型中继窄带物联网的非正交多址接入和多维网络资源优化 Non-orthogonal Multiple Access and Multi-dimension Resource Optimization in EH Relay NB-IoT Networks 计算机科学, 2022, 49(5): 279-286. https://doi.org/10.11896/jsjkx.210400239 |
| [7] | 张振超, 刘亚丽, 殷新春. 适用于物联网环境的无证书广义签密方案 New Certificateless Generalized Signcryption Scheme for Internet of Things Environment 计算机科学, 2022, 49(3): 329-337. https://doi.org/10.11896/jsjkx.201200256 |
| [8] | 张叶, 李志华, 王长杰. 基于核密度估计的轻量级物联网异常流量检测方法 Kernel Density Estimation-based Lightweight IoT Anomaly Traffic Detection Method 计算机科学, 2021, 48(9): 337-344. https://doi.org/10.11896/jsjkx.200600108 |
| [9] | 李贝贝, 宋佳芮, 杜卿芸, 何俊江. DRL-IDS:基于深度强化学习的工业物联网入侵检测系统 DRL-IDS:Deep Reinforcement Learning Based Intrusion Detection System for Industrial Internet of Things 计算机科学, 2021, 48(7): 47-54. https://doi.org/10.11896/jsjkx.210400021 |
| [10] | 薛艳芬, 高继梅, 范贵生, 虞慧群, 许亚杰. 边缘计算中基于能耗感知的容错协同任务执行算法 Energy-aware Fault-tolerant Collaborative Task Execution Algorithm in Edge Computing 计算机科学, 2021, 48(6A): 374-382. https://doi.org/10.11896/jsjkx.200900027 |
| [11] | 李嘉明, 赵阔, 屈挺, 刘晓翔. 基于知识图谱的区块链物联网领域研究分析 Research and Analysis of Blockchain Internet of Things Based on Knowledge Graph 计算机科学, 2021, 48(6A): 563-567. https://doi.org/10.11896/jsjkx.200600071 |
| [12] | 范艳芳, 袁爽, 蔡英, 陈若愚. 车载边缘计算中基于深度强化学习的协同计算卸载方案 Deep Reinforcement Learning-based Collaborative Computation Offloading Scheme in VehicularEdge Computing 计算机科学, 2021, 48(5): 270-276. https://doi.org/10.11896/jsjkx.201000005 |
| [13] | 李振江, 张幸林. 减少核心网拥塞的边缘计算资源分配和卸载决策 Resource Allocation and Offloading Decision of Edge Computing for Reducing Core Network Congestion 计算机科学, 2021, 48(3): 281-288. https://doi.org/10.11896/jsjkx.200700025 |
| [14] | 王锡龙, 李鑫, 秦小麟. 电力物联网下分布式状态感知的源网荷储协同调度 Collaborative Scheduling of Source-Grid-Load-Storage with Distributed State Awareness UnderPower Internet of Things 计算机科学, 2021, 48(2): 23-32. https://doi.org/10.11896/jsjkx.200900209 |
| [15] | 王卫红, 陈震宇. 基于改进区块链的智能制造安全模型 Intelligent Manufacturing Security Model Based on Improved Blockchain 计算机科学, 2021, 48(2): 295-302. https://doi.org/10.11896/jsjkx.191200159 |
|
||
首页