publications
List of my publications in reversed chronological order, generated by jekyll-scholar.
2024
- Generating Synthetic Power Grids Using Exponential Random Graph ModelsF. Giacomarra, G. Bet, and A. ZoccaPRX Energy, Jun 2024
Synthetic power grids enable real-world energy system simulations and are crucial for algorithm testing, resilience assessment, and policy formulation. We propose a novel method for the generation of synthetic transmission power grids using exponential random graph (ERG) models. Our two main contributions are (1) the formulation of an ERG model tailored specifically for capturing the topological nuances of power grids and (2) a general procedure for estimating the parameters of such a model conditioned on working with connected graphs. From a modeling perspective, we identify edge counts per bus type and \(k\)-triangles as crucial topological characteristics for synthetic power-grid generation. From a technical perspective, we develop a rigorous methodology to estimate the parameters of an ERG constrained to the space of connected graphs. The proposed model is flexible, easy to implement, and successfully captures the desired topological properties of power grids.
@article{Giacomarra_2024, title = {Generating Synthetic Power Grids Using Exponential Random Graph Models}, volume = {3}, issn = {2768-5608}, url = {http://dx.doi.org/10.1103/PRXEnergy.3.023005}, doi = {10.1103/prxenergy.3.023005}, number = {2}, journal = {PRX Energy}, publisher = {American Physical Society (APS)}, author = {Giacomarra, F. and Bet, G. and Zocca, A.}, year = {2024}, month = jun, } - Sailing through uncertainty: ship pipe routing and the energy transitionB.T. Markhorst, J. Berkhout, A. Zocca, and 2 more authorsInternational Marine Design Conference, May 2024
The energy transition from fossil fuels to sustainable alternatives makes the design of future-proof ships even more important. In the design phase of a ship, it is uncertain how many and which fuels it will use in the future due to many external factors. In fact, a ship typically sails for decades, increasing the likelihood that it will use different fuels during its lifetime. Pipe route design is expensive and time-consuming, mainly done by hand. Motivated by this, in previous research, we have proposed a mathematical optimization framework for automatic pipe routing under uncertainty of the energy transition. In this paper, we build on the state-of-the-art by implementing design constraints in mathematical models based on discussions with maritime design experts. Additionally, we apply these models to realistic, complex situations of a commercial ship design company. Our experiments show that location-dependent installation costs, which reflect reality, increase the usefulness of stochastic optimization compared to deterministic and robust optimization. Additionally, to prepare for a possible transition to more sustainable fuels, we recommend installing suitable pipes near the engine room upfront to prevent expensive retrofits in the future.
@article{Markhorst_2024, title = {Sailing through uncertainty: ship pipe routing and the energy transition}, issn = {3050-4864}, url = {http://dx.doi.org/10.59490/imdc.2024.891}, doi = {10.59490/imdc.2024.891}, journal = {International Marine Design Conference}, publisher = {TU Delft OPEN Publishing}, author = {Markhorst, B.T. and Berkhout, J. and Zocca, A. and Pruyn, J.F.J. and Van der Mei, R.D.}, year = {2024}, month = may, } - Pricing Uncertainty in Stochastic Multi-Stage Electricity MarketsL. Werner, N. Christianson, A. Zocca, and 2 more authorsIn 2023 62nd IEEE Conference on Decision and Control (CDC), May 2024
This work proposes a pricing mechanism for multi-stage electricity markets that does not explicitly depend on the choice of dispatch procedure or optimization method. Our approach is applicable to a wide range of methodologies for the economic dispatch of power systems under uncertainty, including multi-interval dispatch, multi-settlement markets, scenario-based dispatch, and chance-constrained dispatch policies. We prove that our pricing scheme provides both ex-ante and expost dispatch-following incentives by simultaneously supporting per-stage and ex-post competitive equilibria. In numerical experiments on a ramp-constrained test system, we demonstrate the benefits of scheduling under uncertainty and show how our price decomposes into components corresponding to energy, intertemporal coupling, and uncertainty.
@inproceedings{Werner_2024, title = {Pricing Uncertainty in Stochastic Multi-Stage Electricity Markets}, author = {Werner, L. and Christianson, N. and Zocca, A. and Wierman, A. and Low, S.H.}, year = {2024}, doi = {10.1109/CDC49753.2023.10384022}, isbn = {9798350301250}, series = {Proceedings of the IEEE Conference on Decision and Control}, publisher = {IEEE}, pages = {1580--1587}, booktitle = {2023 62nd IEEE Conference on Decision and Control (CDC)}, } - Uncovering Load-Altering Attacks Against \(N-1\,\) Secure Power Grids: A Rare-Event Sampling ApproachM.P. Goodridge, S. Lakshminarayana, and A. ZoccaIEEE Transactions on Power Systems, May 2024
Load-altering attacks targetting a large number of IoT-based high-wattage devices (e.g., smart electric vehicle charging stations) can lead to serious disruptions of power grid operations. In this work, we aim to uncover spatiotemporal characteristics of LAAs that can lead to serious impact. The problem is challenging since existing protection measures such as N−1 security ensures that the power grid is naturally resilient to load changes. Thus, strategically injected load perturbations that lead to network failure can be regarded as \emph{rare events}. To this end, we adopt a rare-event sampling approach to uncover LAAs distributed temporally and spatially across the power network. The key advantage of this sampling method is the ability of sampling efficiently from multi-modal conditional distributions with disconnected support. Furthermore, we systematically compare the impacts of static (one-time manipulation of demand) and dynamic (attack over multiple time periods) LAAs. We perform extensive simulations using benchmark IEEE test simulations. The results show (i) the superiority and the need for rare-event sampling in the context of uncovering LAAs as compared to other sampling methodologies, (ii) statistical analysis of attack characteristics and impacts of static and dynamic LAAs, and (iii) cascade sizes (due to LAA) for different network sizes and load conditions.
@article{Goodridge_2024, title = {Uncovering Load-Altering Attacks Against \(N-1\,\) Secure Power Grids: A Rare-Event Sampling Approach}, issn = {1558-0679}, url = {http://dx.doi.org/10.1109/TPWRS.2024.3419725}, doi = {10.1109/tpwrs.2024.3419725}, journal = {IEEE Transactions on Power Systems}, publisher = {IEEE}, author = {Goodridge, M.P. and Lakshminarayana, S. and Zocca, A.}, year = {2024}, pages = {1–13}, }
2023
- Critical configurations of the hard-core model on square grid graphsS. Baldassarri, V. Jacquier, and A. ZoccaSubmitted to Combinatorics, Probability and Computing, 2023
We consider the hard-core model on a finite square grid graph with stochastic Glauber dynamics parametrized by the inverse temperature \(\beta\). We investigate how the transition between its two maximum-occupancy configurations takes place in the low-temperature regime \(\beta \to \infty\,\) in the case of periodic boundary conditions. The hard-core constraints and the grid symmetry make the structure of the critical configurations, also known as essential saddles, for this transition very rich and complex. We provide a comprehensive geometrical characterization of the set of critical configurations that are asymptotically visited with probability one. In particular, we develop a novel isoperimetric inequality for hard-core configurations with a fixed number of particles and we show how not only their size but also their shape determines the characterization of the saddles.
@article{Baldassarri_2024, title = {Critical configurations of the hard-core model on square grid graphs}, url = {}, doi = {}, journal = {Submitted to Combinatorics, Probability and Computing}, eprint = {arXiv:2308.05041}, publisher = {}, author = {Baldassarri, S. and Jacquier, V. and Zocca, A.}, year = {2023}, month = {}, pages = {}, } - Future-proof ship pipe routing: navigating the energy transitionB.T. Markhorst, J. Berkhout, A. Zocca, and 2 more authorsSubmitted to Ocean Engineering, Dec 2023
The maritime industry must prepare for the energy transition from fossil fuels to sustainable alternatives. Making ships future-proof is necessary given their long lifetime, but it is also complex because the future fuel type is uncertain. Within this uncertainty, one typically overlooks pipe routing, although it is a crucial driver for design time and costs. Therefore, we propose a mathematical approach for modeling uncertainty in pipe routing with deterministic, stochastic, and robust optimization. All three models are based on state-of-the-art integer linear optimization models for the Stochastic Steiner Forest Problem and adjusted to the maritime domain using specific constraints for pipe routing. We compare the models using both artificial and realistic instances and show that considering uncertainty using stochastic optimization and robust optimization leads to cost reductions of up to 22% in our experiments.
@article{Markhorst_2023, title = {Future-proof ship pipe routing: navigating the energy transition}, issn = {}, url = {}, doi = {}, journal = {Submitted to Ocean Engineering}, eprint = {arXiv:2312.09088v2}, author = {Markhorst, B.T. and Berkhout, J. and Zocca, A. and Pruyn, J.F.J. and Van der Mei, R.D.}, year = {2023}, month = dec, } - Multi-Agent Reinforcement Learning for Power Grid Topology OptimizationE. Sar, A. Zocca, and S. BhulaiSubmitted to PSCC 2024, Oct 2023
Recent challenges in operating power networks arise from increasing energy demands and unpredictable renewable sources like wind and solar. While reinforcement learning (RL) shows promise in managing these networks, through topological actions like bus and line switching, efficiently handling large action spaces as networks grow is crucial. This paper presents a hierarchical multi-agent reinforcement learning (MARL) framework tailored for these expansive action spaces, leveraging the power grid's inherent hierarchical nature. Experimental results indicate the MARL framework's competitive performance with single-agent RL methods. We also compare different RL algorithms for lower-level agents alongside different policies for higher-order agents.
@article{van_der_Sar_2023, title = {Multi-Agent Reinforcement Learning for Power Grid Topology Optimization}, author = {van der Sar, E. and Zocca, A. and Bhulai, S.}, journal = {Submitted to PSCC 2024}, issn = {2310.02605}, eprint = {arXiv:2310.02605}, year = {2023}, month = oct, } - Mixed-integer linear programming approaches for tree partitioning of power networksL. Lan, and A. ZoccaSubmitted to IEEE Transactions on Control of Network Systems, Aug 2023
In transmission networks, power flows and network topology are deeply intertwined due to power flow physics. Recent literature shows that a specific more hierarchical network structure can effectively inhibit the propagation of line failures across the entire system. In particular, a novel approach named tree partitioning has been proposed, which seeks to bolster the robustness of power networks through strategic alterations in network topology, accomplished via targeted line switching actions. Several tree partitioning problem formulations have been proposed by considering different objectives, among which power flow disruption and network congestion. Furthermore, various heuristic methods based on a two-stage and recursive approach have been proposed. The present work provides a general framework for tree partitioning problems based on mixed-integer linear programming (MILP). In particular, we present a novel MILP formulation to optimally solve tree partitioning problems and also propose a two-stage heuristic based on MILP. We perform extensive numerical experiments to solve two tree partitioning problem variants, demonstrating the excellent performance of our solution methods. Lastly, through exhaustive cascading failure simulations, we compare the effectiveness of various tree partitioning strategies and show that, on average, they can achieve a substantial reduction in lost load compared to the original topologies.
@article{lan2023, author = {Lan, L. and Zocca, A.}, title = {Mixed-integer linear programming approaches for tree partitioning of power networks}, eprint = {2110.07000v2}, journal = {Submitted to IEEE Transactions on Control of Network Systems}, year = {2023}, month = aug, url = {http://arxiv.org/abs/2110.07000v2}, } - Ising model on clustered networks: A model for opinion dynamicsS. Baldassarri, A. Gallo, V. Jacquier, and 1 more authorPhysica A: Statistical Mechanics and its Applications, Aug 2023
We study opinion dynamics on networks with a nontrivial community structure, assuming individuals can update their binary opinion as the result of the interactions with an external influence with strength \(h \in [ 0, 1 ]\) and with other individuals in the network. To model such dynamics, we consider the Ising model with an external magnetic field on a family of finite networks with a clustered structure. Assuming a unit strength for the interactions inside each community, we assume that the strength of interaction across different communities is described by a scalar \(\epsilon \in [ −1, 1 ]\), which allows a weaker but possibly antagonistic effect between communities. We are interested in the stochastic evolution of this system described by a Glauber-type dynamics parametrized by the inverse temperature \(\beta\). We focus on the low-temperature regime \(\beta \to \infty\), in which homogeneous opinion patterns prevail and, as such, it takes the network a long time to fully change opinion. We investigate the different metastable and stable states of this opinion dynamics model and how they depend on the values of the parameters \(\epsilon\,\) and \(h\). More precisely, using tools from statistical physics, we derive rigorous estimates in probability, expectation, and law for the first hitting time between metastable (or stable) states and (other) stable states, together with tight bounds on the mixing time and spectral gap of the Markov chain describing the network dynamics. Lastly, we provide a full characterization of the critical configurations for the dynamics, i.e., those which are visited with high probability along the transitions of interest.
@article{Baldassarri_2023, title = {Ising model on clustered networks: A model for opinion dynamics}, volume = {623}, issn = {0378-4371}, url = {http://dx.doi.org/10.1016/j.physa.2023.128811}, doi = {10.1016/j.physa.2023.128811}, journal = {Physica A: Statistical Mechanics and its Applications}, publisher = {Elsevier BV}, author = {Baldassarri, S. and Gallo, A. and Jacquier, V. and Zocca, A.}, year = {2023}, month = aug, pages = {128811}, } - Adaptive Network Response to Line Failures in Power SystemsC. Liang, L. Guo, A. Zocca, and 2 more authorsIEEE Transactions on Control of Network Systems, Mar 2023
Transmission line failures in power systems propagate and cascade non-locally. In this work, we propose an adaptive control strategy that offers strong guarantees in both the mitigation and localization of line failures. Specifically, we leverage the properties of network bridge-block decomposition and a frequency regulation method called the unified control. If the balancing areas over which the unified control operates coincide with the bridge-blocks of the network, the proposed strategy drives the post-contingency system to a steady state where the impact of initial line outages is localized within the areas where they occurred whenever possible, stopping the cascading process. When the initial line outages cannot be localized, the proposed control strategy provides a configurable design that progressively involves and coordinates more balancing areas. We compare the proposed control strategy with the classical Automatic Generation Control (AGC) on the IEEE 118-bus and 2736-bus test networks. Simulation results show that our strategy greatly improves overall reliability in terms of the N-k security standard, and localizes the impact of initial failures in the majority of the simulated contingencies. Moreover, the proposed framework incurs significantly less load loss, if any, compared to AGC, in all our case studies.
@article{Liang_2023, title = {Adaptive Network Response to Line Failures in Power Systems}, volume = {10}, issn = {2372-2533}, url = {http://dx.doi.org/10.1109/TCNS.2022.3203367}, doi = {10.1109/tcns.2022.3203367}, eprint = {2005.11319}, number = {1}, journal = {IEEE Transactions on Control of Network Systems}, publisher = {IEEE}, author = {Liang, C. and Guo, L. and Zocca, A. and Low, S.H. and Wierman, A.}, year = {2023}, month = mar, pages = {333–344}, } - Analysis of Cascading Failures Due to Dynamic Load-Altering AttacksM.P. Goodridge, A. Zocca, and S. LakshminarayanaIn 2023 IEEE SmartGridComm, Mar 2023
Large-scale load-altering attacks (LAAs) are known to severely disrupt power grid operations by manipulating several internet-of-things (IoT)-enabled load devices. In this work, we analyze power grid cascading failures induced by such attacks. The inherent security features in power grids such as the \(N-1\,\) design philosophy dictate LAAs that can trigger cascading failures are rare events. We overcome the challenge of efficiently sampling critical LAAs scenarios for a wide range of attack parameters by using the so-called “skipping sampler” algorithm. We conduct extensive simulations using a three-area IEEE-39 bus system and provide several novel insights into the composition of cascades due to LAAs. Our results highlight the particular risks to modern power systems posed by strategically designed coordinated LAAs that exploit their structural and real-time operating characteristics.
@inproceedings{Goodridge_2023, title = {Analysis of Cascading Failures Due to Dynamic Load-Altering Attacks}, author = {Goodridge, M.P. and Zocca, A. and Lakshminarayana, S.}, year = {2023}, doi = {10.1109/SmartGridComm57358.2023.10333960}, publisher = {IEEE}, booktitle = {2023 IEEE SmartGridComm}, address = {United States}, }
2022
- Hopping between distant basinsM.P. Goodridge, J. Moriarty, J. Vogrinc, and 1 more authorJournal of Global Optimization, Mar 2022
We present the Basin Hopping with Skipping (BH-S) algorithm for stochastic optimisation, which replaces the perturbation step of basin hopping (BH) with a so-called skipping proposal from the rare-event sampling literature. Empirical results on benchmark optimisation surfaces demonstrate that BH-S can improve performance relative to BH by encouraging non-local exploration, that is, by hopping between distant basins.
@article{Goodridge_2022, title = {Hopping between distant basins}, doi = {10.1007/s10898-022-01153-z}, author = {Goodridge, M.P. and Moriarty, J. and Vogrinc, J. and Zocca, A.}, journal = {Journal of Global Optimization}, volume = {84}, number = {2}, pages = {465--489}, year = {2022}, publisher = {Springer}, } - Interface Networks for Failure Localization in Power SystemsC. Liang, A. Zocca, S.H. Low, and 1 more authorIn 2022 American Control Conference (ACC), Sep 2022
Transmission power systems usually consist of interconnected sub-grids that are operated relatively independently. When a failure happens, it is desirable to localize its impact within the sub-grid where the failure occurs. This paper introduces three interface networks to connect sub-grids, achieving better failure localization while maintaining robust network connectivity. The proposed interface networks are validated with numerical experiments on the IEEE 118-bus test network under both DC and AC power flow models.
@inproceedings{Liang_2022, author = {Liang, C. and Zocca, A. and Low, S.H. and Wierman, A.}, booktitle = {2022 American Control Conference (ACC)}, title = {Interface Networks for Failure Localization in Power Systems}, year = {2022}, month = sep, volume = {}, number = {}, pages = {4540-4546}, doi = {10.23919/ACC53348.2022.9867209}, } - RangL: A Reinforcement Learning Competition PlatformV. Zobernig, R.A. Saldanha, H. Jinke, and 12 more authorsTechnical report on the RangL platform and the 2022 competition "Pathways to Netzero", Jul 2022
The RangL project hosted by The Alan Turing Institute aims to encourage the wider uptake of reinforcement learning by supporting competitions relating to real-world dynamic decision problems. This article describes the reusable code repository developed by the RangL team and deployed for the 2022 Pathways to Net Zero Challenge, supported by the UK Net Zero Technology Centre. The winning solutions to this particular Challenge seek to optimize the UK's energy transition policy to net zero carbon emissions by 2050. The RangL repository includes an OpenAI Gym reinforcement learning environment and code that supports both submission to, and evaluation in, a remote instance of the open source EvalAI platform as well as all winning learning agent strategies. The repository is an illustrative example of RangL's capability to provide a reusable structure for future challenges.
- Weighted Dyck paths and nonstationary queuesG. Bet, J. Selen, and A. ZoccaStochastic Models, Jan 2022
We consider a model for a queue in which only a fixed number \(N\) of customers can join. Each customer joins the queue independently at an exponentially distributed time. Assuming further that the service times are independent and follow an exponential distribution, this system can be described as a two-dimensional Markov chain on a finite triangular region \(S\,\) of the square lattice. We interpret the resulting random walk on \(S\,\) as a Dyck path that is weighted according to some state-dependent transition probabilities that are constant along one axis, but are rather general otherwise. We untangle the resulting intricate combinatorial structure by introducing appropriate generating functions that exploit the recursive structure of the model. This allows us to derive an explicit expression for the probability mass function of the number of customers served in any busy period (equivalently, of the length of any excursion of the Dyck path above the diagonal) as a weighted sum with alternating sign over a certain subclass of Dyck paths.
@article{Bet_2022, title = {Weighted Dyck paths and nonstationary queues}, volume = {38}, issn = {1532-4214}, url = {http://dx.doi.org/10.1080/15326349.2021.2011748}, doi = {10.1080/15326349.2021.2011748}, number = {2}, journal = {Stochastic Models}, author = {Bet, G. and Selen, J. and Zocca, A.}, year = {2022}, month = jan, pages = {268–287}, eprint = {2002.03424}, }
2021
- A Metropolis-class sampler for targets with non-convex supportJ. Moriarty, J. Vogrinc, and A. ZoccaStatistics and Computing, Sep 2021
We aim to improve upon the exploration of the general-purpose random walk Metropolis algorithm when the target has non-convex support \(A \subset \mathbb{R}^d \), by reusing proposals in \( A^c\) which would otherwise be rejected. The algorithm is Metropolis-class and under standard conditions the chain satisfies a strong law of large numbers and central limit theorem. Theoretical and numerical evidence of improved performance relative to random walk Metropolis are provided. Issues of implementation are discussed and numerical examples, including applications to global optimisation and rare event sampling, are presented.
@article{Moriarty_2021, doi = {10.1007/s11222-021-10044-4}, url = {https://doi.org/10.1007/s11222-021-10044-4}, year = {2021}, month = sep, volume = {31}, number = {6}, author = {Moriarty, J. and Vogrinc, J. and Zocca, A.}, title = {A Metropolis-class sampler for targets with non-convex support}, journal = {Statistics and Computing}, } - Line Failure Localization of Power Networks Part I: Non-Cut OutagesL. Guo, C. Liang, A. Zocca, and 2 more authorsIEEE Transactions on Power Systems, Sep 2021
Transmission line failures in power systems propagate non-locally, making the control of the resulting outages extremely difficult. In this work, we establish a mathematical theory that characterizes the patterns of line failure propagation and localization in terms of network graph structure. It provides a novel perspective on distribution factors that precisely captures Kirchhoff's Law in terms of topological structures. Our results show that the distribution of specific collections of subtrees of the transmission network plays a critical role on the patterns of power redistribution, and motivates the block decomposition of the transmission network as a structure to understand long-distance propagation of disturbances. In Part I of this paper, we present the case when the post-contingency network remains connected after an initial set of lines are disconnected simultaneously. In Part II, we present the case when an outage separates the network into multiple islands.
@article{Guo_2021a, doi = {10.1109/tpwrs.2021.3066336}, url = {https://doi.org/10.1109/tpwrs.2021.3066336}, year = {2021}, month = sep, publisher = {IEEE}, volume = {36}, number = {5}, pages = {4140--4151}, author = {Guo, L. and Liang, C. and Zocca, A. and Low, S.H. and Wierman, A.}, title = {Line Failure Localization of Power Networks Part I: Non-Cut Outages}, journal = {IEEE Transactions on Power Systems}, } - Line Failure Localization of Power Networks Part II: Cut Set OutagesL. Guo, C. Liang, A. Zocca, and 2 more authorsIEEE Transactions on Power Systems, Sep 2021
Transmission line failure in power systems prop-agate non-locally, making the control of the resulting outages extremely difficult. In Part II of this paper, we continue the study of line failure localizability in transmission networks and characterize the impact of cut set outages. We establish a Simple Path Criterion, showing that the propagation pattern due to bridge outages, a special case of cut set failures, are fully determined by the positions in the network of the buses that participate in load balancing. We then extend our results to general cut set outages. In contrast to non-cut outages discussed in Part I whose subsequent line failures are contained within the original blocks, cut set outages typically impact the whole network, affecting the power flows on all remaining lines. We corroborate our analytical results in both parts using the IEEE 118-bus test system, in which the failure propagation patterns exhibit a clear block-diagonal structure predicted by our theory, even when using full AC power flow equations.
@article{Guo_2021b, doi = {10.1109/tpwrs.2021.3068048}, url = {https://doi.org/10.1109/tpwrs.2021.3068048}, year = {2021}, month = sep, publisher = {IEEE}, volume = {36}, number = {5}, pages = {4152--4160}, author = {Guo, L. and Liang, C. and Zocca, A. and Low, S.H. and Wierman, A.}, title = {Line Failure Localization of Power Networks Part II: Cut Set Outages}, journal = {IEEE Transactions on Power Systems}, } - Large fluctuations in locational marginal pricesT. Nesti, J. Moriarty, A. Zocca, and 1 more authorPhilosophical Transactions of the Royal Society A, Jun 2021
This paper investigates large fluctuations of locational marginal prices (LMPs) in wholesale energy markets caused by volatile renewable generation profiles. Specifically, we study events of the form \(\mathbb{P} \left ( \mathbf{LMP} \not\in \prod_{i} [\mathbf{\alpha}^-_i, \mathbf{\alpha}^+_i ]\right)\), where \(\mathbf{LMP}\,\) is the vector of LMPs at the \(n\,\) power grid nodes, and \(\mathbf{\alpha}^-, \mathbf{\alpha}^+ \in \mathbb{R}^n \,\) are vectors of price thresholds specifying undesirable price occurrences. By exploiting the structure of the supply–demand matching mechanism in power grids, we look at LMPs as deterministic piecewise affine, possibly discontinuous functions of the stochastic input process, modelling uncontrollable renewable generation. We use techniques from large deviations theory to identify the most likely ways for extreme price spikes to happen, and to rank the nodes of the power grid in terms of their likelihood of experiencing a price spike. Our results are derived in the case of Gaussian fluctuations, and are validated numerically on the IEEE 14-bus test case.
@article{Nesti_2021, title = {Large fluctuations in locational marginal prices}, volume = {379}, issn = {1471-2962}, url = {http://dx.doi.org/10.1098/rsta.2019.0438}, doi = {10.1098/rsta.2019.0438}, number = {2202}, journal = {Philosophical Transactions of the Royal Society A}, publisher = {The Royal Society}, author = {Nesti, T. and Moriarty, J. and Zocca, A. and Zwart, B.}, year = {2021}, month = jun, pages = {20190438}, } - A Spectral Representation of Power Systems with Applications to Adaptive Grid Partitioning and Cascading Failure LocalizationA. Zocca, C. Liang, L. Guo, and 2 more authorsWork in progress, Jun 2021
Transmission line failures in power systems propagate and cascade non-locally. This well-known yet counter-intuitive feature makes it even more challenging to optimally and reliably operate these complex networks. In this work we present a comprehensive framework based on spectral graph theory that fully and rigorously captures how multiple simultaneous line failures propagate, distinguishing between non-cut and cut set outages. Using this spectral representation of power systems, we identify the crucial graph sub-structure that ensures line failure localization -- the network bridge-block decomposition. Leveraging this theory, we propose an adaptive network topology reconfiguration paradigm that uses a two-stage algorithm where the first stage aims to identify optimal clusters using the notion of network modularity and the second stage refines the clusters by means of optimal line switching actions. Our proposed methodology is illustrated using extensive numerical examples on standard IEEE networks and we discussed several extensions and variants of the proposed algorithm.
@article{Zocca_2021b, title = {A Spectral Representation of Power Systems with Applications to Adaptive Grid Partitioning and Cascading Failure Localization}, author = {Zocca, A. and Liang, C. and Guo, L. and Low, S.H. and Wierman, A.}, year = {2021}, journal = {Work in progress}, } - Optimization of Stochastic Lossy Transport Networks and Applications to Power GridsA. Zocca, and B. ZwartStochastic Systems, Mar 2021
Motivated by developments in renewable energy and smart grids, we formulate a stylized mathematical model of a transport network with stochastic load fluctuations. Using an affine control rule, we explore the trade-off between the number of controllable resources in a lossy transport network and the performance gain they yield in terms of expected power losses. Our results are explicit and reveal the interaction between the level of flexibility, the intrinsic load uncertainty, and the network structure.
@article{Zocca_2021a, doi = {10.1287/stsy.2019.0063}, url = {https://doi.org/10.1287/stsy.2019.0063}, year = {2021}, month = mar, publisher = {INFORMS}, volume = {11}, number = {1}, pages = {34--59}, author = {Zocca, A. and Zwart, B.}, title = {Optimization of Stochastic Lossy Transport Networks and Applications to Power Grids}, journal = {Stochastic Systems}, } - An integrated approach for failure mitigation & localization in power systemsC. Liang, L. Guo, A. Zocca, and 3 more authorsElectric Power Systems Research, Jan 2021Presented at the 21st Power Systems Computation Conference (PSCC 2020)
The transmission grid is often comprised of several control areas that are connected by multiple tie lines in a mesh structure for reliability. It is also well-known that line failures can propagate non-locally and redundancy can exacerbate cascading. In this paper, we propose an integrated approach to grid reliability that (i) judiciously switches off a small number of tie lines so that the control areas are connected in a tree structure; and (ii) leverages a unified frequency control paradigm to provide congestion management in real time. Even though the proposed topology reduces redundancy, the integration of tree structure at regional level and real-time congestion management can provide stronger guarantees on failure localization and mitigation. We illustrate our approach on the IEEE 39-bus network and evaluate its performance on the IEEE 118-bus, 179-bus, 200-bus and 240-bus networks with various network congestion conditions. Simulations show that, compared with the traditional approach, our approach not only prevents load shedding in more failure scenarios, but also incurs smaller amounts of load loss in scenarios where load shedding is inevitable. Moreover, generators under our approach adjust their operations more actively and efficiently in a local manner.
@article{Liang_2021, title = {An integrated approach for failure mitigation & localization in power systems}, volume = {190}, issn = {0378-7796}, url = {http://dx.doi.org/10.1016/j.epsr.2020.106613}, doi = {10.1016/j.epsr.2020.106613}, eprint = {2004.10401}, journal = {Electric Power Systems Research}, publisher = {Elsevier BV}, author = {Liang, C. and Guo, L. and Zocca, A. and Yu, S. and Low, S.H. and Wierman, A.}, note = {Presented at the 21st Power Systems Computation Conference (PSCC 2020)}, year = {2021}, month = jan, pages = {106613}, }
2020
- Mitigating Cascading Failures via Local ResponsesC. Liang, F. Zhou, A. Zocca, and 2 more authorsIn 2020 IEEE SmartGridComm, Nov 2020
This work proposes an approach for failure mitigation in power systems via corrective control named Optimal Injection Adjustment (OIA). In contrast to classical approaches, which focus on minimizing load loss, OIA aims to minimize the post-contingency flow deviations by adjusting node power injections in response to failures. We prove that the optimal control actions obtained from OIA are localized around the original failure and use numerical simulations to highlight that OIA achieves near-optimal control costs despite using localized control actions.
@inproceedings{Liang_2020, author = {Liang, C. and Zhou, F. and Zocca, A. and Low, S.H. and Wierman, A.}, booktitle = {2020 IEEE SmartGridComm}, title = {Mitigating Cascading Failures via Local Responses}, year = {2020}, volume = {67}, month = nov, publisher = {IEEE}, pages = {1-7}, doi = {10.1109/SmartGridComm47815.2020.9302934}, }
2019
- Tunneling behavior of Ising and Potts models in the low-temperature regimeF.R. Nardi, and A. ZoccaStochastic Processes and their Applications, Nov 2019
We consider the ferromagnetic \(q\)-state Potts model with zero external field in a finite volume and assume that the stochastic evolution of this system is described by a Glauber-type dynamics parametrized by the inverse temperature \(\beta\). Our analysis concerns the low-temperature regime \(\beta\to\infty\), in which this multi-spin system has \(q\) stable equilibria, corresponding to the configurations where all spins are equal. Focusing on grid graphs with various boundary conditions, we study the tunneling phenomena of the \(q\)-state Potts model. More specifically, we describe the asymptotic behavior of the first hitting times between stable equilibria as \(\beta\to\infty\) in probability, in expectation, and in distribution and obtain tight bounds on the mixing time as side-result. In the special case \(q=2\), our results characterize the tunneling behavior of the Ising model on grid graphs.
@article{Nardi_2019, title = {Tunneling behavior of Ising and Potts models in the low-temperature regime}, journal = {Stochastic Processes and their Applications}, volume = {129}, number = {11}, pages = {4556 - 4575}, year = {2019}, issn = {0304-4149}, doi = {https://doi.org/10.1016/j.spa.2018.12.001}, url = {http://www.sciencedirect.com/science/article/pii/S0304414918306938}, author = {Nardi, F.R. and Zocca, A.}, eprint = {arXiv:1708.09677}, } - Less is More: Real-time Failure Localization in Power SystemsL. Guo, C. Liang, A. Zocca, and 2 more authorsIn 2019 IEEE 58th Conference on Decision and Control (CDC), Dec 2019
Cascading failures in power systems exhibit nonlocal propagation patterns, which make the analysis and mitigation of failures difficult. In this work, we propose a distributed control framework inspired by the recently proposed concepts of unified controller and network tree-partition that offers strong guarantees in both the mitigation and localization of cascading failures in power systems. In this framework, the transmission network is partitioned into several control areas which are connected in a tree structure, and the unified controller is adopted by generators or controllable loads for fast timescale disturbance response. After an initial failure, the proposed strategy always prevents successive failures from happening, and regulates the system to the desired steady state where the impact of initial failures are localized as much as possible. For extreme failures that cannot be localized, the proposed framework has a configurable design, that progressively involves and coordinates more control areas for failure mitigation and, as a last resort, imposes minimal load shedding. We compare the proposed control framework with Automatic Generation Control (AGC) on the IEEE 118-bus test system. Simulation results show that our novel framework greatly improves the system robustness in terms of the N - 1 security standard, and localizes the impact of initial failures in majority of the load profiles that are examined. Moreover, the proposed framework incurs significantly less load loss, if any, compared to AGC.
@inproceedings{Guo_2019, author = {Guo, L. and Liang, C. and Zocca, A. and Low, S.H. and Wierman, A.}, booktitle = {2019 IEEE 58th Conference on Decision and Control (CDC)}, title = {Less is More: Real-time Failure Localization in Power Systems}, year = {2019}, volume = {}, number = {}, pages = {3871-3877}, doi = {10.1109/CDC40024.2019.9029393}, eprint = {1904.05461}, issn = {2576-2370}, month = dec, } - Tunneling of the hard-core model on finite triangular latticesA. ZoccaRandom Structures & Algorithms, Dec 2019
We consider the hard-core model on finite triangular lattices with Metropolis dynamics. Under suitable conditions on the triangular lattice dimensions, this interacting particle system has three maximum-occupancy configurations and we investigate its high-fugacity behavior by studying tunneling times, i.e., the first hitting times between between these maximum-occupancy configurations, and the mixing time. The proof method relies on the analysis of the corresponding state space using geometrical and combinatorial properties of the hard-core configurations on finite triangular lattices, in combination with known results for first hitting times of Metropolis Markov chains in the equivalent zero-temperature limit. In particular, we show how the order of magnitude of the expected tunneling times depends on the triangular lattice dimensions in the low-temperature regime and prove the asymptotic exponentiality of the rescaled tunneling time leveraging the intrinsic symmetry of the state space.
@article{Zocca_2019, author = {Zocca, A.}, title = {Tunneling of the hard-core model on finite triangular lattices}, journal = {Random Structures & Algorithms}, volume = {55}, number = {1}, pages = {215-246}, doi = {10.1002/rsa.20795}, url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20795}, eprint = {1701.07004}, year = {2019}, } - Temporal starvation in multi-channel CSMA networks: An analytical frameworkA. ZoccaQueueing Systems, Dec 2019
In this paper we consider a stochastic model for a frequency-agile CSMA protocol for wireless networks where multiple orthogonal frequency channels are available. Even when the possible interference on the different channels is described by different conflict graphs, we show that the network dynamics can be equivalently described as that of a single-channel CSMA algorithm on an appropriate virtual network. Our focus is on the asymptotic regime in which the network nodes try to activate aggressively in order to achieve maximum throughput. Of particular interest is the scenario where the number of available channels is not sufficient for all nodes of the network to be simultaneously active and the well-studied temporal starvation issues of the single-channel CSMA dynamics persist. For most networks we expect that a larger number of available channels should alleviate these temporal starvation issues. However, we prove that the aggregate throughput is a non-increasing function of the number of available channels. To investigate this trade-off that emerges between aggregate throughput and temporal starvation phenomena, we propose an analytical framework to study the transient dynamics of multi-channel CSMA networks by means of first hitting times. Our analysis further reveals that the mixing time of the activity process does not always correctly characterize the temporal starvation in the multi-channel scenario and often leads to pessimistic performance estimates.
@article{Zocca_2019b, title = {Temporal starvation in multi-channel CSMA networks: An analytical framework}, volume = {91}, issn = {1572-9443}, url = {https://doi.org/10.1007/s11134-019-09598-y}, doi = {10.1007/s11134-019-09598-y}, eprint = {1808.03602}, pages = {241-263}, number = {3}, journal = {Queueing Systems}, author = {Zocca, A.}, year = {2019}, }
2018
- Failure Localization in Power Systems via Tree PartitionsL. Guo, C. Liang, A. Zocca, and 2 more authorsIn 2018 IEEE Conference on Decision and Control (CDC), Dec 2018
Cascading failures in power systems propagate non-locally, making the control and mitigation of outages extremely hard. In this work, we use the emerging concept of the tree partition of transmission networks to provide an analytical characterization of line failure localizability in transmission systems. Our results rigorously establish the well perceived intuition in power community that failures cannot cross bridges, and reveal a finer-grained concept that encodes more precise information on failure propagations within tree-partition regions. Specifically, when a non-bridge line is tripped, the impact of this failure only propagates within well-defined components, which we refer to as cells, of the tree partition defined by the bridges. In contrast, when a bridge line is tripped, the impact of this failure propagates globally across the network, affecting the power flow on all remaining transmission lines. This characterization suggests that it is possible to improve the system robustness by temporarily switching off certain transmission lines, so as to create more, smaller components in the tree partition; thus spatially localizing line failures and making the grid less vulnerable to large-scale outages. We illustrate this approach using the IEEE 118-bus test system and demonstrate that switching off a negligible portion of transmission lines allows the impact of line failures to be significantly more localized without substantial changes in line congestion.
@inproceedings{Guo_2018, author = {Guo, L. and Liang, C. and Zocca, A. and Low, S.H. and Wierman, A.}, booktitle = {2018 IEEE Conference on Decision and Control (CDC)}, title = {Failure Localization in Power Systems via Tree Partitions}, year = {2018}, volume = {}, number = {}, pages = {6832-6839}, doi = {10.1109/CDC.2018.8619562}, eprint = {1803.08551}, issn = {2576-2370}, month = dec, } - Frequency violations from random disturbances: an MCMC approachJ. Moriarty, J. Vogrinc, and A. ZoccaIn 2018 IEEE Conference on Decision and Control (CDC), Dec 2018
The frequency stability of power systems is increasingly challenged by various types of disturbance. In particular, the increasing penetration of renewable energy sources is increasing the variability of power generation while reducing system inertia against disturbances. In this paper we explore how this could give rise to rate of change of frequency (RoCoF) violations. Correlated and non -Gaussian power disturbances, such as may arise from renewable generation, have been shown to be significant in power system security analysis. We therefore introduce ghost sampling which, given any unconditional distribution of disturbances, efficiently produces samples conditional on a violation occurring. Our goal is to address questions such as “which generator is most likely to be disconnected due to a RoCoF violation?” or “what is the probability of having simultaneous RoCoF violations, given that a violation occurs?”
@inproceedings{Moriarty_2018, author = {Moriarty, J. and Vogrinc, J. and Zocca, A.}, booktitle = {2018 IEEE Conference on Decision and Control (CDC)}, title = {Frequency violations from random disturbances: an MCMC approach}, year = {2018}, volume = {}, number = {}, pages = {1598-1603}, doi = {10.1109/CDC.2018.8619304}, eprint = {1803.08522}, issn = {2576-2370}, month = dec, } - Low-temperature behavior of the multicomponent Widom–Rowlison model on finite square latticesA. ZoccaJournal of Statistical Physics, Dec 2018
We consider the multicomponent Widom-Rowlison with Metropolis dynamics, which describes the evolution of a particle system where \(M\,\) different types of particles interact subject to certain hard-core constraints. Focusing on the scenario where the spatial structure is modeled by finite square lattices, we study the asymptotic behavior of this interacting particle system in the low-temperature regime, analyzing the tunneling times between its \(M\,\) maximum-occupancy configurations, and the mixing time of the corresponding Markov chain. In particular, we develop a novel combinatorial method that, exploiting geometrical properties of the Widom-Rowlinson configurations on finite square lattices, leads to the identification of the timescale at which transitions between maximum-occupancy configurations occur and shows how this depends on the chosen boundary conditions and the square lattice dimensions.
@article{Zocca_2018, title = {Low-temperature behavior of the multicomponent Widom–Rowlison model on finite square lattices}, volume = {171}, issn = {1572-9613}, url = {https://doi.org/10.1007/s10955-018-1961-9}, doi = {10.1007/s10955-018-1961-9}, eprint = {1701.09185}, pages = {1--37}, number = {1}, journal = {Journal of Statistical Physics}, author = {Zocca, A.}, year = {2018}, } - Emergent Failures and Cascades in Power Grids: A Statistical Physics PerspectiveT. Nesti, A. Zocca, and B. ZwartPhys. Rev. Lett., Jun 2018
We model power grids transporting electricity generated by intermittent renewable sources as complex networks, where line failures can emerge indirectly by noisy power input at the nodes. By combining concepts from statistical physics and the physics of power flows, and taking weather correlations into account, we rank line failures according to their likelihood and establish the most likely way such failures occur and propagate. Our insights are mathematically rigorous in a small-noise limit and are validated with data from the German transmission grid.
@article{Nesti_2018, title = {Emergent Failures and Cascades in Power Grids: A Statistical Physics Perspective}, author = {Nesti, T. and Zocca, A. and Zwart, B.}, journal = {Phys. Rev. Lett.}, volume = {120}, issue = {25}, pages = {258301}, numpages = {6}, year = {2018}, month = jun, publisher = {American Physical Society}, doi = {10.1103/PhysRevLett.120.258301}, url = {https://link.aps.org/doi/10.1103/PhysRevLett.120.258301}, eprint = {1709.10166}, }
2017
- Line failure probability bounds for power gridsT. Nesti, A. Zocca, and B. ZwartIn 2017 IEEE Power & Energy Society General Meeting, Jul 2017
We develop upper bounds for line failure probabilities in power grids, under the DC approximation and assuming Gaussian noise for the power injections. Our upper bounds are explicit, and lead to characterization of safe operational capacity regions that are convex and polyhedral, making our tools compatible with existing planning methods. Our probabilistic bounds are derived through the use of powerful concentration inequalities.
@inproceedings{Nesti_2017, title = {Line failure probability bounds for power grids}, url = {http://dx.doi.org/10.1109/PESGM.2017.8274716}, doi = {10.1109/pesgm.2017.8274716}, booktitle = {2017 IEEE Power & Energy Society General Meeting}, publisher = {IEEE}, author = {Nesti, T. and Zocca, A. and Zwart, B.}, year = {2017}, month = jul, pages = {1–5}, eprint = {1611.02338}, }
2016
- Hitting Time Asymptotics for Hard-Core Interactions on GridsF.R. Nardi, A. Zocca, and S.C. BorstJournal of Statistical Physics, Jul 2016
We consider the hard-core model with Metropolis transition probabilities on finite grid graphs and investigate the asymptotic behavior of the first hitting time between its two maximum-occupancy configurations in the low-temperature regime. In particular, we show how the order-of-magnitude of this first hitting time depends on the grid sizes and on the boundary conditions by means of a novel combinatorial method. Our analysis also proves the asymptotic exponentiality of the scaled hitting time and yields the mixing time of the process in the low-temperature limit as side-result. In order to derive these results, we extended the model-independent framework in [27] for first hitting times to allow for a more general initial state and target subset.
@article{Nardi_2016, title = {Hitting Time Asymptotics for Hard-Core Interactions on Grids}, volume = {162}, issn = {1572-9613}, url = {https://doi.org/10.1007/s10955-015-1391-x}, doi = {10.1007/s10955-015-1391-x}, eprint = {1503.06757}, pages = {522--576}, number = {2}, journal = {Journal of Statistical Physics}, author = {Nardi, F.R. and Zocca, A. and Borst, S.C.}, year = {2016}, } - Minimizing heat loss in DC networks using batteriesA. Zocca, and B. ZwartIn 54th Annual Allerton Conference on Communication, Control, and Computing, Sep 2016
Electricity transmission networks dissipate a non-negligible fraction of the power they transport due to the heat loss in the transmission lines. In this work we explore how the transport of energy can be more efficient by adding to the network multiple batteries that can coordinate their operations. Such batteries can both charge using the current excess in the network or discharge to meet the network current demand. Either way, the presence of batteries in the network can be leveraged to mitigate the intrinsic uncertainty in the power generation and demand and, hence, transport the energy more efficiently through the network. We consider a resistive DC network with stochastic external current injections or consumptions and show how the expected total heat loss depends on the network structure and on the batteries operations. Furthermore, in the case where the external currents are modeled by Ornstein-Uhlenbeck processes, we derive the dynamical optimal control for the batteries over a finite time interval.
@inproceedings{Zocca_2016, author = {Zocca, A. and Zwart, B.}, booktitle = {54th Annual Allerton Conference on Communication, Control, and Computing}, doi = {10.1109/ALLERTON.2016.7852385}, eprint = {1607.06040}, isbn = {978-1-5090-4550-1}, month = sep, pages = {1306--1313}, publisher = {IEEE}, title = {Minimizing heat loss in DC networks using batteries}, url = {http://ieeexplore.ieee.org/document/7852385/}, year = {2016}, } - On the Interactions Between Multiple Overlapping WLANs Using Channel BondingB. Bellalta, A. Checco, A. Zocca, and 1 more authorIEEE Transactions on Vehicular Technology, Feb 2016
Next-generation wireless local area networks (WLANs) will support the use of wider channels, which is known as channel bonding, to achieve higher throughput. However, because both the channel center frequency and the channel width are autonomously selected by each WLAN, the use of wider channels may also increase the competition with other WLANs operating in the same area for the available channel resources. In this paper, we analyze the interactions between a group of neighboring WLANs that use channel bonding and evaluate the impact of those interactions on the achievable throughput. A continuous-time Markov network model that is able to capture the coupled dynamics of a group of overlapping WLANs is introduced and validated. The results show that the use of channel bonding can provide significant performance gains, even in scenarios with a high density of WLANs, although it may also cause unfair situations in which some WLANs receive most of the transmission opportunities while others starve.
@article{Bellalta_2016, author = {Bellalta, B. and Checco, A. and Zocca, A. and Barcelo, J.}, doi = {10.1109/TVT.2015.2400932}, issn = {0018-9545}, journal = {IEEE Transactions on Vehicular Technology}, eprint = {1412.0929}, month = feb, number = {2}, pages = {796--812}, title = {On the Interactions Between Multiple Overlapping WLANs Using Channel Bonding}, volume = {65}, year = {2016}, }
2015
- Spatio-temporal dynamics of random-access networks: An interacting particle approachA. ZoccaEindhoven University of Technology, Dec 2015PhD Thesis in Mathematics
@phdthesis{Zocca_2015, title = {Spatio-temporal dynamics of random-access networks: An interacting particle approach}, author = {Zocca, A.}, note = {PhD Thesis in Mathematics}, year = {2015}, month = dec, day = {17}, isbn = {978-90-386-3981-9}, school = {Eindhoven University of Technology}, } - Slow transitions and starvation in dense random-access networksA. Zocca, S.C. Borst, and J.S.H. LeeuwaardenStochastic Models, Dec 2015
We consider dense wireless random-access networks, modeled as systems of particles with hard-core interaction. The particles represent the network users that try to become active after an exponential back-off time, and stay active for an exponential transmission time. Due to wireless interference, active users prevent other nearby users from simultaneous activity, which we describe as hard-core interaction on a conflict graph. We show that dense networks with aggressive back-off schemes lead to extremely slow transitions between dominant states, and inevitably cause long mixing times and starvation effects.
@article{Zocca_2015b, author = {Zocca, A. and Borst, S.C. and van Leeuwaarden, J.S.H.}, doi = {10.1080/15326349.2015.1018441}, eprint = {1403.3325}, issn = {1532-6349}, journal = {Stochastic Models}, number = {3}, pages = {361--402}, title = {Slow transitions and starvation in dense random-access networks}, volume = {31}, year = {2015}, }
2014
- Throughput analysis in CSMA/CA networks using continuous time Markov networks: A tutorialB. Bellalta, A. Zocca, C. Cano, and 3 more authorsIn Lecture Notes in Computer Science, Dec 2014
This book chapter introduces the use of Continuous Time Markov Networks (CTMN) to analytically capture the operation of Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) networks. It is of tutorial nature, and it aims to be an introduction on this topic, providing a clear and easy-to-follow description. To illustrate how CTMN can be used, we introduce a set of representative and cutting-edge scenarios, such as Vehicular Ad-hoc Networks (VANETs), Power Line Communication networks and multiple overlapping Wireless Local Area Networks (WLANs). For each scenario, we describe the specific CTMN, obtain its stationary distribution and compute the throughput achieved by each node in the network. Taking the per-node throughput as reference, we discuss how the complex interactions between nodes using CSMA/CA have an impact on system performance.
@incollection{Bellalta_2014, author = {Bellalta, B. and Zocca, A. and Cano, C. and Checco, A. and Barcelo, J. and Vinel, A.}, booktitle = {Lecture Notes in Computer Science}, doi = {10.1007/978-3-319-10834-6_7}, eprint = {1404.0180}, issn = {16113349 03029743}, title = {Throughput analysis in CSMA/CA networks using continuous time Markov networks: A tutorial}, volume = {8611}, year = {2014}, }
2013
- Delay performance in random-access grid networksA. Zocca, S.C. Borst, J.S.H. Leeuwaarden, and 1 more authorPerformance Evaluation, Oct 2013
We examine the impact of torpid mixing and meta-stability issues on the delay performance in wireless random-access networks. Focusing on regular meshes as prototypical scenarios, we show that the mean delays in an \(L\times L\) toric grid with normalized load \(\rho\,\) are of the order \(\Big (\frac{1} {1-\rho} \Big)^L\). This superlinear delay scaling is to be contrasted with the usual linear growth of the order \(\frac{1} {1-\rho} \) in conventional queueing networks. The intuitive explanation for the poor delay characteristics is that (i) high load requires a high activity factor, (ii) a high activity factor implies extremely slow transitions between dominant activity states, and (iii) slow transitions cause starvation and hence excessively long queues and delays. Our proof method combines both renewal and conductance arguments. A critical ingredient in quantifying the long transition times is the derivation of the communication height of the uniformized Markov chain associated with the activity process. We also discuss connections with Glauber dynamics, conductance, and mixing times. Our proof framework can be applied to other topologies as well, and is also relevant for the hard-core model in statistical physics and sampling from independent sets using single-site update Markov chains.
@article{Zocca_2013, title = {Delay performance in random-access grid networks}, volume = {70}, issn = {0166-5316}, url = {http://dx.doi.org/10.1016/j.peva.2013.08.019}, doi = {10.1016/j.peva.2013.08.019}, eprint = {1307.1532}, number = {10}, journal = {Performance Evaluation}, publisher = {Elsevier BV}, author = {Zocca, A. and Borst, S.C. and van Leeuwaarden, J.S.H. and Nardi, F.R.}, year = {2013}, month = oct, pages = {900–-915}, }
2012
- Mixing Properties of CSMA Networks on Partite GraphsA. Zocca, S.C. Borst, and J.S.H. LeeuwaardenIn Proceedings of the 6th International Conference on Performance Evaluation Methodologies and Tools (VALUETOOLS), Oct 2012
We consider a stylized stochastic model for a wireless CSMA network. Experimental results in prior studies indicate that the model provides remarkably accurate throughput estimates for IEEE 802.11 systems. In particular, the model offers an explanation for the severe spatial unfairness in throughputs observed in such networks with asymmetric interference conditions. Even in symmetric scenarios, however, it may take a long time for the activity process to move between dominant states, giving rise to potential starvation issues. In order to gain insight in the transient throughput characteristics and associated starvation effects, we examine in the present paper the behavior of the transition time between dominant activity states. We focus on partite interference graphs, and establish how the magnitude of the transition time scales with the activation rate and the sizes of the various network components. We also prove that in several cases the scaled transition time has an asymptotically exponential distribution as the activation rate grows large, and point out interesting connections with related exponentiality results for rare events and meta-stability phenomena in statistical physics. In addition, we investigate the convergence rate to equilibrium of the activity process in terms of mixing times.
@inproceedings{Zocca_2012, series = {VALUETOOLS}, title = {Mixing Properties of CSMA Networks on Partite Graphs}, url = {http://dx.doi.org/10.4108/valuetools.2012.250264}, doi = {10.4108/valuetools.2012.250264}, booktitle = {Proceedings of the 6th International Conference on Performance Evaluation Methodologies and Tools (VALUETOOLS)}, publisher = {IEEE}, author = {Zocca, A. and Borst, S.C. and van Leeuwaarden, J.S.H.}, year = {2012}, collection = {VALUETOOLS}, }