Resource allocation for edge cloud and smart grid
Open Access
- Author:
- Farhadi, Vaji
- Graduate Program:
- Computer Science and Engineering
- Degree:
- Doctor of Philosophy
- Document Type:
- Dissertation
- Date of Defense:
- February 17, 2022
- Committee Members:
- Thomas La Porta, Co-Chair & Dissertation Advisor
Mort Webster, Outside Unit & Field Member
Ting He, Co-Chair & Dissertation Advisor
Nilanjan Ray Chaudhuri, Major Field Member
Chitaranjan Das, Program Head/Chair - Keywords:
- DC-QSS
cascading failure
blackouts
preventive control
SCADA
PLCC
Mobile edge computing
workload scheduling
service placement
complexity analysis
algorithm design
Resource Allocation - Abstract:
- This dissertation develops solutions for optimized resource allocation in various distributed systems, including data-intensive applications in edge clouds and SCADA-based control systems in power grid networks. The abstract resource allocation problem concerns how to optimally use resources for different tasks. In the context of this dissertation, the resources are CPU cycles, wireless link bandwidth, and storage space in mobile edge computing networks or the budget for deploying communication links in the smart grid network. The optimized resource allocation problem for data-intensive applications in edge clouds: Mobile edge computing provides a highly distributed computing environment that can be used to deploy applications and services as well as to store and process content in close proximity to mobile users. In this dissertation, the research on mobile edge computing begins by jointly considering service placement and request scheduling problems for data-intensive applications in edge clouds under communication, computation, and storage constraints. A budget constraint to control the operation cost due to service replication/migration is also imposed. To properly formulate this problem, we separate the time scales of the two decisions: service placement occurs at a larger scale (frames) to prevent system instability, and request scheduling occurs at a smaller scale (slots) to support real-time services. We fully characterize the complexity of our problem by analyzing the hardness of various cases. By casting our problem as a set function optimization, we develop a polynomial-time algorithm that achieves a constant-factor approximation under certain conditions. Furthermore, we develop a polynomial-time request scheduling algorithm by computing the maximum flow in a constructed auxiliary graph, which satisfies hard resource constraints and is provably optimal in the special case where requests have homogeneous resource demands. Extensive synthetic and trace-driven simulations show that the proposed algorithm serves 90% of the requests that could be served from the edge under the optimal solution. The optimized resource allocation problem for smart grid systems: In this dissertation, the research on the control network of the smart grid addresses the optimized allocation of budget for deploying the communication links in a system in which the power grid is coupled with a geographically co-located SCADA-based communication network. We consider the problem of Power Line Carrier Communication (PLCC) and non-PLCC (fiber, microwave, etc.) link allocation and study the impact of the coupling between the communication and the power networks as it affects a SCADA-based preventive control system in the occurrence of the cascading failures. Loss of a power transmission line disables PLCC links; hence failure in the power network leads to an outage in the communication network and consequently disrupts monitoring and control of the power system. Non-PLCC links are immune to failures in the power grid; however, they are costly. In the first part of the research on optimized resource allocation in smart grids, we start with a baseline where all the communication links are PLCC. Next, we pose the problem of allocating non-PLCC communication links with a budget constraint for a given power system with a given control center location. The ultimate objective of the design of the communication network is to ensure that the re-dispatch-based preventive control can effectively restrict the propagation of cascade. We propose a heuristic that enhances the total demand served at the end of cascade, and show its effectiveness when tested in a 2383-bus Polish network. In the second part, we focus on (a) relaxing the idealistic assumption that the topology of the power grid (all breaker statuses of the lines) are known, and (b) assuming that only the minimum number of lines are associated with communication links. Meanwhile, the observability of all nodes at the control center before cascade is provided. Such a realistic scenario poses new challenges that were not present in the previous case. In the absence of a fully known admittance matrix (which provides the topology of the power system), we use the estimated admittance matrix proposed in [1]. In this work, the authors divide the problem of the admittance matrix estimation into two steps, first detecting the islands formed within in power grid due to failure, and second estimating connectivity of unobservable lines within islands. The effectiveness of the redispatch-based control depends upon the accuracy of these two steps. Here, we propose a novel scheme in designing the communication network comprised of both PLCC and non-PLCC links in preparation of possible failures under a budget constraint on the communication link deployment cost. First, we characterize the fundamental hardness of our problem. Next, we develop a solvable MILP-based algorithm, which attains a constant-factor approximation under certain conditions. Finally, we show via simulations on the IEEE 118-bus system that the proposed algorithm achieves superior performance in terms of enabling more accurate topology estimation and more served demand in the face of cascades.