Cooperation Mechanism And Scheduling Algorithms In Edge Computing

With the proliferation of smart devices and the rapid development of Internet of Things(Io T)technologies,many emerging applications(e.g.,virtual reality,ultra-highdefinition video streaming,and autonomous driving)are placing increasing demands on computing power.In order to provide high-quality computing services to users,researchers have extended the traditional cloud computing model and introduced the concept of edge computing.By densely deploying computing servers throughout the network,edge computing sinks communication,computation,and storage functions from the cloud to the edge of the network,and provides computing services in proximity to users.Compared with cloud computing,the communication distance in edge computing is significantly shortened,so it inherently has the characteristics of low latency,high bandwidth,and localized services.However,the computing resources of each edge server are usually very limited,making it difficult to provide satisfactory performance when facing bursty task offloading requests.An effective solution to the above challenges is to establish a cooperative relationship among neighboring edge servers,allowing part of computation tasks to be offloaded from high-load servers to low-load ones.Through load balancing,the resource utilization is escalated and thus the system performance is improved.However,in reality,different edge servers often belong to multiple self-interested service providers,so they have no incentive to help others.To address this issue,edge computing systems need a proper incentive mechanism to promote cooperation.Since the cooperation mechanism involves collaboration among multiple edge servers,it is necessary to design scheduling algorithms that jointly optimize the overall system performance.In addition,more and more newly emerged applications propose additional requirements on both the system architecture and performance metrics of edge computing,which demands specially designed scheduling algorithms.In order to solve the above problems,this dissertation studies the cooperation mechanism and scheduling algorithms in edge computing under different application scenarios and quality of service requirements based on theoretical approaches such as game theory and online optimization.The main research content of this dissertation can be divided into the following three aspects.(1)Research on the incentive mechanism in collaborative edge computing.First,this dissertation extends the concept of Shapley value in cooperative game theory to accommodate the situation where the revenue of coalitions is related to the offloading decisions.Based on this new concept,a revenue allocation mechanism among different service providers is proposed.Theoretical analysis demonstrates that the mechanism induces optimal scheduling decisions and ensures that each service provider benefits from cooperation.In order to protect the privacy of service providers,the mechanism introduces a profit aggregation function,which guarantees the normal operation of the system without requiring the private information of service providers.Second,this dissertation studies the incentive mechanism between users and multiple collaborative edge servers.By introducing dual variables,the mechanism maintains a dynamic price for the computing resources at each edge server.The prices are used to calculate the running cost of each task,and the acceptance of the task's offloading request is decided by comparing the running cost with its utility.Based on the structure of the optimal scheduling,an efficient scheduling algorithm is designed with polynomial-time computational complexity.The theoretical analysis further demonstrates that the incentive mechanism achieves desirable properties such as truthfulness and a favorable competitive ratio.(2)Scheduling algorithms with worst-case latency guarantee in collaborative edge computing.Existing scheduling algorithms for collaborative edge computing tend to optimize the average latency of tasks.But for many practical applications,it is equally important to provide worst-case latency guarantees.To address this issue,this dissertation considers scheduling algorithms that provide worst-case latency guarantees under homogeneous and heterogeneous tasks.The objective is to achieve the maximum system utility while satisfying the worst-case latency requirements and the time-average energy consumption constraint.To achieve this goal,this dissertation extends the conventional Lyapunov optimization theory by introducing two different virtual queues and proving that the worst-case latency guarantees can be realized by restricting the maximum length of virtual queues.Based on theoretical analysis,this dissertation provides an upper bound of the worst-case latency for both cases and shows that there is an O(V)-O(1/V)tradeoff between this upper bound and the system utility.The simulation results demonstrate that the proposed algorithms can produce near-optimal solutions while guaranteeing the worst-case latency.(3)Scheduling algorithms under different system architectures and performance metrics in edge computing.With the development of the Io T industry,various emerging applications have put forward new requirements on the system architecture and performance metrics in edge computing.In wireless-powered mobile edge computing,the base station not only needs to communicate with wireless devices,but also needs to transmit specific radio frequency signals to charge them.Since these two processes share time and spectrum resources,it is necessary to design new scheduling algorithms that jointly optimize the related control decisions.This dissertation first formulates the energy consumption minimization problem in wireless-powered edge computing networks with partial offloading.To reduce the solving complexity,this dissertation relaxes a part of the constraints and decomposes the original joint optimization problem into multiple independent subproblems.After solving each subproblem,the obtained solutions are adjusted based on the optimality conditions to realize a feasible solution to the original problem.Another application scenario considered in this dissertation is the edge computing-based monitoring and control systems.Since these applications have stringent requirements for the freshness of environmental information,the optimization objective of the system changes from the task's latency to its age of information.This dissertation models the online scheduling problem as a Markov decision process,which can be solved by reinforcement learning algorithms such as Q-learning.To improve the algorithm's running efficiency,this dissertation introduces post-decision states to decompose and compress the system states,which accelerates the convergence process by fully exploiting the knowledge of system dynamics.