Task Scheduling And Resource Management In Edge Computing Networks

Driven by the visions of emerging applications,recent years have seen a paradigm shift in mobile computing,from the centralized cloud computing toward edge computing.The main feature of mobile edge computing is to push computing,network control and storage to the network edges.By exploiting these features,edge computing can process computation intensive and delay sensitive tasks at the network edge to increase the network throughput.Edge computing research is to seamlessly merge the wireless communication and mobile computing,resulting in new designs ranging from techniques for task scheduling to communication and computation resource management.A candidate task scheduling solution has to answer the following questions: where to place each service instance,whether and where to offload task,and how many percent of a task should be decided to offload.The problem of resource management is stated as the allocation and scheduling of radio and computation resources,as well as the edge server collaboration scheme.According to the hierarchical architecture of edge computing paradigm,this thesis studies the following two exemplary scenarios of edge computing,including single-cell multi-user task scheduling and resource management and cooperative computing and networking among multiple edge servers.For the single-cell multi-user scenarios,the end-to-end(E2E)delay performance largely depends on the offloading decision and computing resource allocation.However,the tandem queue formed during task offloading coupled the offloading decision and computing resource allocation,which makes it difficult to develop the optimum solution.For the single-cell massive connection scenarios,having all devices to report their states to the base station(BS)at each slot would lead to prohibitive overhead.The BS can only make decisions based on the outdated device states.For the cooperative networking scenarios,in order to improve the efficiency of collaborative task processing,service placement and task scheduling at each edge server need to be designed with spatial-temporal collaboration.To tackle the aforementioned problems,this thesis focuses on two scenarios of edge computing: single-cell edge computing and cooperative networking edge computing,and investigates the optimization of task scheduling and resource management.The main contributions of this thesis are summarized as follows:1.Design on the offloading decision and resource allocation for E2E delay provisioning.Several existing works focus on statistical delay provisioning through queue stability constraint.However,the delay provisioning under these prior arts is captured by improving the average delay performance,and some of packets may experience unacceptance delay.This thesis alternatively guarantees probability delay by controlling delay bound violation probability.Moreover,the tandem queue formed during task offloading couples the offloading decision and computing resource allocation.To tackle the above challenges,this thesis proposes a two-stage algorithm.At stage Ⅰ,offloading decision is developed to minimize the bandwidth cost while providing local queue’s delay provisioning,with a low time complexity.At stage Ⅱ,a closed-form expression of the minimum required computation resource is derived under the remote queue’s delay bound violation probability.To evaluate the E2E delay performance of the two-stage algorithm,we derive the delay bound violation probability of the tandem queue.Further,we reveal the performance degradation of the two-stage algorithm due to coupling by comparing with a non-decoupled problem.The result shows that under the same E2E delay provisioning,two-stage algorithm can approach to the nondecoupled optimum with an appropriate value of control parameter V.2.Design on the uplink access and resource allocation in massive-connection edge computing network.In the massive-connection edge computing network,all devices report their states(i.e.,data arrivals,channel states,computing resource requirement)to the base station(BS)at each slot would lead to prohibitive overhead.The BS can only make decisions based on the outdated device states.This thesis presents the proactive scheduling algorithm based on outdated knowledge of states.With data queue stability and computing resource availability constraint,the BS optimally schedule the uplink access,admission control and transmit power,thereby maximizing the time-averaged network throughput.The theoretical analysis shows that the proactive scheduling algorithm approaches to the offline optimum with a sufficiently small stepsize.Further,[O(ε),O(1/ε)] tradeoff between throughput and queue length has been revealed.That is if we want to achieve O(ε)-optimal,queue length will grow linearly in O(1/ε).3.Design on spatial-temporal collaboration of service placement and task scheduling in cooperative networking scenarios.Since each edge server can only accommodate a subset of services at a time,relying on individual edge server greatly restricts service diversity.To tackle this,spatial collaboration enables resource limited edge servers to help each other with tasks.Besides,to adapt to the dynamic network states,a collaboration in temporal dimension is desired to pursue a long-term performance.The above necessitate the design of a judicious service placement and task scheduling with spatial-temporal collaboration.Specifically,this thesis first designs an online decentralized collaborative service placement and task scheduling algorithm.Considering that adjusting service placement as frequently as task scheduling would incur service interruption,this thesis manages service placement and task scheduling at two different timescales.This thesis proves that the asymptotic optimality is preserved.However,setting service placement at a relatively larger timescale may slow down the convergence speed of optimal service placement.This thesis further proposes a learn-and-adapt method to speed up the service placement.Theoretical analysis and simulations are performed to validate the efficiency of the proposed algorithm.