Computer Science ›› 2022, Vol. 49 ›› Issue (7): 263-270.doi: 10.11896/jsjkx.210300195

• Computer Network • Previous Articles     Next Articles

Task Offloading Online Algorithm for Data Stream Edge Computing

ZHANG Chong-yu, CHEN Yan-ming, LI Wei   

  1. School of Computer Science and Technology,Anhui University,Hefei 230601,China
  • Received:2021-03-18 Revised:2021-07-09 Online:2022-07-15 Published:2022-07-12
  • About author:ZHANG Zhong-yu,born in 1996,postgraduate.His main research interests include edge computing and Internet of Things.
    CHEN Yan-ming,born in 1983,Ph.D.His main research interests include distributed algorithms,edge computing,neural networks and model compression.
  • Supported by:
    National Natural Science Foundation of China(61802001).

Abstract: With the development of Internet of Things (IoT) technology,its application scenarios have exploded recently,and such applications are generally delay-sensitive and resource-constrained.It is a focused issue in the way of offloading the real-time tasks under the condition of limited resource.Besides,it is a NP-hard combinatorial optimization problem to allocate limited computational resources for the real-time tasks.To solve this problem,this paper proposes a real-time resource management algorithm based on Lyapunov optimization,aiming at stabilizing the virtual queues while optimizing the total power consumption and total utility.Firstly,the optimization model for the total power consumption and weighted total utility is proposed under the constraint of computation and communication resources.This model contains of two virtual buffer queues,and tasks are unloaded in a device-to-device (D2D) scheduling model.Then,an optimization algorithm is proposed based on Lyapunov optimization to decompose the joint long-term average sum energy consumption and sum utility optimization problem into a series of real-time optimization problems.To solve these problems,a greedy-based matching algorithm is proposed.Experimental results demonstrate that the performance of the proposed algorithm is 8.6% better than the best result of random method and can approximate the exhaustive attack method under different connection degrees.

Key words: Computation offloading, Greedy algorithm, Internet of Things, Lyapunov approximation

CLC Number: 

  • TP393
[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.
[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] SUN Hui-ting, FAN Yan-fang, MA Meng-xiao, CHEN Ruo-yu, CAI Ying. Dynamic Pricing-based Vehicle Collaborative Computation Offloading Scheme in VEC [J]. Computer Science, 2022, 49(9): 242-248.
[2] ZHANG Xi-ran, LIU Wan-ping, LONG Hua. Dynamic Model and Analysis of Spreading of Botnet Viruses over Internet of Things [J]. Computer Science, 2022, 49(6A): 738-743.
[3] LIU Zhang-hui, ZHENG Hong-qiang, ZHANG Jian-shan, CHEN Zhe-yi. Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems [J]. Computer Science, 2022, 49(6A): 619-627.
[4] DONG Dan-dan, SONG Kang. Performance Analysis on Reconfigurable Intelligent Surface Aided Two-way Internet of Things Communication System [J]. Computer Science, 2022, 49(6): 19-24.
[5] Ran WANG, Jiang-tian NIE, Yang ZHANG, Kun ZHU. Clustering-based Demand Response for Intelligent Energy Management in 6G-enabled Smart Grids [J]. Computer Science, 2022, 49(6): 44-54.
[6] ZHANG Zhen-chao, LIU Ya-li, YIN Xin-chun. New Certificateless Generalized Signcryption Scheme for Internet of Things Environment [J]. Computer Science, 2022, 49(3): 329-337.
[7] LI Bei-bei, SONG Jia-rui, DU Qing-yun, HE Jun-jiang. DRL-IDS:Deep Reinforcement Learning Based Intrusion Detection System for Industrial Internet of Things [J]. Computer Science, 2021, 48(7): 47-54.
[8] LI Jia-ming, ZHAO Kuo, QU Ting, LIU Xiao-xiang. Research and Analysis of Blockchain Internet of Things Based on Knowledge Graph [J]. Computer Science, 2021, 48(6A): 563-567.
[9] FAN Yan-fang, YUAN Shuang, CAI Ying, CHEN Ruo-yu. Deep Reinforcement Learning-based Collaborative Computation Offloading Scheme in VehicularEdge Computing [J]. Computer Science, 2021, 48(5): 270-276.
[10] LI Zhen-jiang, ZHANG Xing-lin. Resource Allocation and Offloading Decision of Edge Computing for Reducing Core Network Congestion [J]. Computer Science, 2021, 48(3): 281-288.
[11] WANG Xi-long, LI Xin, QIN Xiao-lin. Collaborative Scheduling of Source-Grid-Load-Storage with Distributed State Awareness UnderPower Internet of Things [J]. Computer Science, 2021, 48(2): 23-32.
[12] WANG Wei-hong, CHEN Zhen-yu. Intelligent Manufacturing Security Model Based on Improved Blockchain [J]. Computer Science, 2021, 48(2): 295-302.
[13] LIU Xin, HUANG Yuan-yuan, LIU Zi-ang, ZHOU Rui. IoTGuardEye:A Web Attack Detection Method for IoT Services [J]. Computer Science, 2021, 48(2): 324-329.
[14] LIU Wei, RUAN Min-jie, SHE Wei, ZHANG Zhi-hong, TIAN Zhao. PBFT Optimized Consensus Algorithm for Internet of Things [J]. Computer Science, 2021, 48(11): 151-158.
[15] LIANG Jun-bin, TIAN Feng-sen, JIANG Chan, WANG Tian-shu. Survey on Task Offloading Techniques for Mobile Edge Computing with Multi-devices and Multi-servers in Internet of Things [J]. Computer Science, 2021, 48(1): 16-25.
Full text



No Suggested Reading articles found!