Geometrized Task Scheduling and Adaptive Resource Allocation for Large-Scale Edge Computing in Smart Cities

Edge computing is vital in developing smart cities by providing on-site computational resources to support the surging Internet of Things demands. However, the distributed nature of edge nodes and large scale of tasks distributed in expansive urban spaces challenge task scheduling and resource allocation. In this paper, a novel framework is developed to achieve efficient task scheduling (assignment and offloading) and resource allocation for large-scale edge computing in both wired and wireless smart-city applications. To overcome overparameterization in existing optimization-based heuristic algorithms, the geometrized task scheduling problem is addressed by transforming the assignment of clustered tasks into a regional partition problem in a two-dimensional graph and applying a Tetris-like task offloading strategy for edge-cloud cooperation. These approaches avoid combinatorial explosion and NP-hardness, and the regional partition problem is solved by multiplicative weighted Voronoi diagrams with polynomial computational complexity. Furthermore, an adaptive resource allocation algorithm is proposed to overcome the dynamic, uncertain, and highly concurrent task requests. An online learning algorithm is adopted to adjust the sliding window length according to the evolving conditions. Comparison results show that the proposed framework significantly reduces the average task deadline violation rate, i.e., up to 4.72% of (more than 20 times better than) those using the other schemes, especially when handling large-scale workloads.