Achieving Provable Performance Guarantees for Cyber-Physical Systems: From Internet-of-Things to Smart Grids

The world is witnessing an unprecedented growth of cyber-physical systems (CPS), driven by the significant growth in the sectors of big data and artificial intelligence. Increasingly, in addition to human communication devices, a large number of physical devices are also connected into the network to support new services and applications such as environmental monitoring, e-health systems, intelligent transportation systems, smart grid, etc. However, a serious gap still remains between the cyber-world, where information is exchanged and processed, and the physical-world in which we live. In order to achieve reliable, efficient and real-time operations, CPS’s have to provide satisfactory performance under various constraints, including communication constraints and physical constraints. In this thesis, we provide solutions for performance guarantees under these two major constraints by investigating two emerging and promising scenarios for CPS: Internet-of-things and smart grid.

In the first part of the thesis, we focus on a type of communication-critical CPS, known as internet-of-things (IoT). The unique IoT traffic characteristics require high spectrum efficiency, low overhead and low latency in communication. The traditional communication protocols for human communication (e.g., 4G LTE), while highly spectrum-efficient, fail to meet low-overhead or time-sensitive requirement.

• We first focus on delay-tolerant IoT applications. Specifically, we study an uplink (UL) IoT system where the base station equipped with multiple antennas is serving massive single-antenna IoT devices with infinite backlog of packets. Using pseudo-random beamforming (PRBF) approach, we design a low-overhead random access scheme for UL IoT that can utilize MIMO (multi-input multi-output) technology to achieve high spectrum efficiency with ultra-low overhead. With a sufficient number of devices, our distributed random access scheme can provably achieve 1/e of the system throughput under centralized scheduling. Then, we turn our focus to a heterogeneous variant of the system, where a multi-antenna base station is serving heterogeneous IoT devices with stochastic arrivals. We develop low-overhead random access algorithms that jointly solve the channel assignment and distributed scheduling. Even compared to optimal centralized and offline policies, our proposed algorithms can achieve a provable fraction of the maximum system capacity. Our results demonstrate the importance of provably providing the stability guarantee of the system.
• Next, we turn to time-sensitive IoT systems, where the information freshness is the top concern. We study how to optimize the expected Age-of-Information (AoI) in these IoT systems with heterogeneous and unreliable channels, where the standard Whittle index policy is not applicable. We develop a new low-complexity computational framework based on the concept of partial-index, and show that our proposed policy is asymptotically optimal under suitable conditions. Further, the proposed computational framework could be useful to other large-scale MDP problems with heterogeneous resources.

The second part of the thesis focuses on electricity power system (or smart grid), another type of CPS with stringent physical constraints, whose reliability is facing significant challenges due to the uncertainty and variability of renewable generation. In this thesis, we design robust online strategies for jointly operating energy storage units and fossil-fuel generators to achieve provably reliable grid operations at all times under high renewable uncertainty, without the need of renewable curtailment. In particular, we jointly consider two power system operations, namely day-ahead reliability assessment commitment (RAC) and real-time dispatch. We first extend the concept of “safe-dispatch sets” in the literature to our setting. While finding such safe-dispatch sets and checking their non-emptiness provide crucial answers to both RAC and real-time dispatch, their computation incurs high complexity in general. To develop computationally-efficient solutions, we first study a single-bus case with one generator-storage pair, where we derive necessary conditions and sufficient conditions for the safe-dispatch sets. Our results reveal fundamental trade-offs between storage capacity and generator ramp-up/-down limits to ensure grid reliability. Then, for the more general multi-bus scenario, we split the net-demand among virtual generator-storage pairs (VGSPs) and apply our single-bus decision strategy to each VGSP. Simulation results on an IEEE 30-bus system show that, compared with state-of-art solutions, our scheme requires significantly less storage to ensure reliable grid operation without any renewable curtailment.