Research On Computation Offloading Based On User And Task Dependency In Cloud-Edge Collaborative System

With the development of new-generation information technologies such as big data and artificial intelligence,a series of new intelligent applications and services have emerged,such as smart wearable devices,virtual reality(VR),augmented reality(AR),and autonomous driving.These new intelligent applications generally have high requirements for timeliness and require significant data processing capabilities to run computation-intensive tasks such as image processing.In order to meet the requirements of these applications for low latency and powerful computing resources simultaneously,collaborative cloud computing emerges as the times require.However,the existing research on computing offloading strategies in cloud-edge collaboration is not perfect.The first is the lack of joint consideration of latency and energy consumption.In fact,latency and energy consumption are contradictory,and the requirement for high energy consumption and low latency of new applications exacerbates the conflict.The second is the lack of consideration for the topology structure between tasks and task dependency,reducing offloading efficiency.The third is ignoring the coupling between multiple optimization variables while offloading decisions and resource allocation are often linked in practice.The fourth is that the consideration of computation offloading schemes in heterogeneous scenarios is not detailed enough,such as ignoring matching between terminal device and edge cloud matching problem and task scheduling issues,resulting in the decrease of offloading effectiveness.Given the above problems,this dissertation studies the following problems based on the current research about collaborative cloud computing.The main work and innovation points of this dissertation are summarized as follows:(1)Aiming at single-user computation offloading problem based on task dependency,this dissertation proposes a Q-Learning based Offloading(QLOF)algorithm to optimize edge cloud computing frequency,transmission power,and offloading decisions.The topology and dependency between subtasks of the application make the mathematical model of computational offloading complicated,and the coupling of offloading decisions between subtasks has higher requirements on the offloading computing mechanism.This dissertation first formulates an Application Energy-Time Cost(AETC)minimization problem to optimize transmission power,edge cloud computing frequency,and offloading decisions by considering delay and energy consumption.Since the transmission power and the edge cloud computation frequency configuration between subtasks are independent,the bisection method is firstly used to optimize the transmission power,and then the polynomial analysis method is used to optimize the edge cloud computing frequency.Then,based on the Markov Property,the singlechain application sequential offloading process is modeled as a Markov Decision Process(MDP)by establishing states,actions,policies,and gains,and the original minimization problem is transformed into a System Loss Function(SY LF)minimization problem satisfying uniform MDP.The proposed QLOF optimizes the offloading decision after multiple rounds of Q-value selection by establishing a Q-table to store the Q-value.The experimental results show that the QLOF algorithm proposed in this dissertation can significantly reduce SY LF under different parameters.(2)Aiming at multi-user and multi-edge cloud computation offloading problem based on bilateral matching,this dissertation proposes a Gale-Shapley based Minimum Offloading Algorithm(GS-MOA),and a suboptimal algorithm namely,Gale-Shapley based Sequential Offloading Algorithm(GS-SOA).Due to the intensive deployment of edge clouds and the massive growth of end-users,there are multiple end-users within the coverage area of an edge cloud.Each end-user is in the multiple edge cloud coverage area simultaneously.Therefore,selecting the appropriate edge cloud to offload for end-users becomes a vital issue.This dissertation first formulates the System EnergyTime Cost(SETC)minimization problem to jointly optimize transmission power,edge cloud computing frequency,matching strategies,and offloading decisions by considering delay and energy consumption.Since the offloading decisions and the transmission power are coupled,this dissertation first uses the bisection method to solve the quasiconvex problem to obtain the closed-form of the optimal transmission power concerning the offloading decisions and then uses the polynomial analysis method to optimize edge cloud computing frequency independently.Considering the matching strategy is coupled with offloading decisions,GS-MOA jointly optimizes the matching strategy and offloading decisions by iteratively using the proposed Gale-Shapley based MobileEdge Matching Algorithm(GS-MEMA).To reduce the time complexity,the proposed suboptimal algorithm GS-SOA can significantly reduce the time complexity with close performance.The experimental results show that GS-MOA and GS-SOA can effectively reduce SETC under different parameters compared with the existing offloading algorithms.(3)Aiming at a multi-user multi-edge cloud computation offloading problem based on task dependency scheduling,this dissertation proposes a Maximum Local Searching Offloading algorithm(MLSO),a Sequential Searching Offloading algorithm(SSO)based on Heuristically Search,and a Genetic-based Task Scheduling Algorithm(GTS).For complex applications composed of multiple dependent subtasks,the coupling between combined offloading decision and resource allocation puts forward higher requirements on offloading mechanism.This dissertation formulates a System EnergyTime Cost(SETC)minimization problem by jointly considering delay and energy consumption,subtask dependency,and coupling between combined offloading decisions and edge computing resources.Then,the Lagrangian multiplier method is used to obtain the closed form of the optimal edge computing frequency concerning offloading decisions,and the bisection method is used to optimize the transmission power.Considering the coupling between combined offloading decisions and edge cloud computing resources,MLSO jointly optimizes the edge cloud computing frequency and combined offloading decisions using Heuristically Search and the suboptimal algorithm SSO can effectively reduce time complexity with close performance.To further reduce the SETC,the GTS algorithm models subtasks scheduling problem as a Job Shop Scheduling Problem(JSSP)to optimize tasks computing sequence on each edge cloud.The experimental results show that the proposed offloading algorithms and subtask scheduling algorithm can reduce the SETC effectively.