This article studies a problem of strategic network inspection, in which a defender (agency) is tasked with detecting the presence of multiple attacks in the network. An inspection strategy entails monitoring the network components, possibly in a randomized manner, using a given number of detectors. We formulate the network inspection problem [Formula: see text] as a large-scale bilevel optimization problem, in which the defender seeks to determine an inspection strategy with minimum number of detectors that ensures a target expected detection rate under worst-case attacks. We show that optimal solutions of [Formula: see text] can be obtained from the equilibria of a large-scale zero-sum game. Our equilibrium analysis involves both game-theoretic and combinatorial arguments and leads to a computationally tractable approach to solve [Formula: see text]. First, we construct an approximate solution by using solutions of minimum set cover (MSC) and maximum set packing (MSP) problems and evaluate its detection performance. In fact, this construction generalizes some of the known results in network security games. Second, we leverage properties of the optimal detection rate to iteratively refine our MSC/MSP-based solution through a column generation procedure. Computational results on benchmark water networks demonstrate the scalability, performance, and operational feasibility of our approach. The results indicate that utilities can achieve a high level of protection in large-scale networks by strategically positioning a small number of detectors.
more »
« less
Voltage Collapse Stabilization in Star DC Networks
Voltage collapse is a type of blackout-inducing
dynamic instability that occurs when the power demand exceeds
the maximum power that can be transferred through the
network. The traditional (preventive) approach to avoid voltage
collapse is based on ensuring that the network never reaches
its maximum capacity. However, such an approach leads to
inefficiencies as it prevents operators to fully utilize the network
resources and does not account for unprescribed events. To
overcome this limitation, this paper seeks to initiate the study
of voltage collapse stabilization.
More precisely, for a DC star network, we formulate the
problem of voltage stability as a dynamic problem where each
load seeks to achieve a constant power consumption by updating
its conductance as the voltage changes. We show that such a
system can be interpreted as a game, where each player (load)
seeks to myopically maximize their utility using a gradient-based
response.
Using this framework, we show that voltage collapse is the
unique Nash Equilibrium of the induced game and is caused
by the lack of cooperation between loads. Finally, we propose a
Voltage Collapse Stabilizer (VCS) controller that uses (flexible)
loads that are willing to cooperate and provides a fair allocation
of the curtailed demand. Our solution stabilizes voltage collapse
even in the presence of non-cooperative loads. Numerical
simulations validate several features of our controllers.
more »
« less
- NSF-PAR ID:
- 10106065
- Date Published:
- Journal Name:
- American Control Conference
- Page Range / eLocation ID:
- 1957 to 1964
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)Saving energy for latency-critical applications like web search can be challenging because of their strict tail latency constraints. State-of-the-art power management frameworks use Dynamic Voltage and Frequency Scaling (DVFS) and Sleep states techniques to slow down the request processing and finish the search just-in-time. However, accurately predicting the compute demand of a request can be difficult. In this paper, we present Gemini, a novel power management framework for latency- critical search engines. Gemini has two unique features to capture the per query service time variation. First, at light loads without request queuing, a two-step DVFS is used to manage the CPU power. Our two-step DVFS selects the initial CPU frequency based on the query specific service time prediction and then judiciously boosts the initial frequency at the right time to catch-up to the deadline. The determination of boosting time further relies on estimating the error in the prediction of individual query’s service time. At high loads, where there is request queuing, only the current request being executed and the critical request in the queue adopt a two-step DVFS. All the other requests in-between use the same frequency to reduce the frequency transition overhead. Second, we develop two separate neural network models, one for predicting the service time and the other for the error in the prediction. The combination of these two predictors significantly improves the power saving and tail latency results of our two-step DVFS. Gemini is implemented on the Solr search engine. Evaluations on three representative query traces show that Gemini saves 41% of the CPU power, and is better than other state-of-the-art techniques.more » « less
-
The Digital Power Network (DPN) is an energy-on-demand approach. In terms of Internet of Things (IoT), it treats the energy itself as a `thing' to be manipulated (in contrast to energy as the `thing's enabler'). The approach is mostly appropriate for energy starving micro-grids with limited capacity, such as a generator for the home while the power grid is down. The process starts with a request of a user (such as, appliance) for energy. Each appliance, energy source or energy storage has an address which is able to communicate its status. A network server, collects all requests and optimizes the energy dissemination based on priority and availability. Energy is then routed in discrete units to each particular address (say air-condition, or, A/C unit). Contrary to packets of data over a computer network whose data bits are characterized by well-behaved voltage and current values at high frequencies, here we deal with energy demands at highvoltage, low-frequency and fluctuating current. For example, turning a motor ON requires 8 times more power than the level needed to maintain a steady states operation. Our approach is seamlessly integrating all energy resources (including alternative sources), energy storage units and the loads since they are but addresses in the network. Optimization of energy requests and the analysis of satisfying these requests is the topic of this paper. Under energy constraints and unlike the current power grid, for example, some energy requests are queued and granted later. While the ultimate goal is to fuse information and energy together through energy digitization, in its simplest form, this micro-grid can be realized by overlaying an auxiliary (communication) network of controllers on top of an energy delivery network and coupling the two through an array of addressable digital power switches.more » « less
-
more » « less
Abstract Increasing demand for self-powered wearable sensors has spurred an urgent need to develop energy harvesting systems that can reliably and sufficiently power these devices. Within the last decade, reverse electrowetting-on-dielectric (REWOD)-based mechanical motion energy harvesting has been developed, where an electrolyte is modulated (repeatedly squeezed) between two dissimilar electrodes under an externally applied mechanical force to generate an AC current. In this work, we explored various combinations of electrolyte concentrations, dielectrics, and dielectric thicknesses to generate maximum output power employing REWOD energy harvester. With the objective of implementing a fully self-powered wearable sensor, a “zero applied-bias-voltage” approach was adopted. Three different concentrations of sodium chloride aqueous solutions (NaCl-0.1 M, NaCl-0.5 M, and NaCl-1.0 M) were used as electrolytes. Likewise, electrodes were fabricated with three different dielectric thicknesses (100 nm, 150 nm, and 200 nm) of Al2O3and SiO2with an additional layer of CYTOP for surface hydrophobicity. The REWOD energy harvester and its electrode–electrolyte layers were modeled using lumped components that include a resistor, a capacitor, and a current source representing the harvester. Without using any external bias voltage, AC current generation with a power density of 53.3 nW/cm2was demonstrated at an external excitation frequency of 3 Hz with an optimal external load. The experimental results were analytically verified using the derived theoretical model. Superior performance of the harvester in terms of the figure-of-merit comparing previously reported works is demonstrated. The novelty of this work lies in the combination of an analytical modeling method and experimental validation that together can be used to increase the REWOD harvested power extensively without requiring any external bias voltage.
-
We consider a variant of the vehicle routing problem (VRP) where each customer has a unit demand and the goal is to minimize the total cost of routing a fleet of capacitated vehicles from one or multiple depots to visit all customers. We propose two parallel algorithms to efficiently solve the column-generation-based linear-programming relaxation for this VRP. Specifically, we focus on algorithms for the “pricing problem,” which corresponds to the resource-constrained elementary shortest path problem. The first algorithm extends the pulse algorithm for which we derive a new bounding scheme on the maximum load of any route. The second algorithm is based on random coloring from parameterized complexity which can be also combined with other techniques in the literature for improving VRPs, including cutting planes and column enumeration. We conduct numerical studies using VRP benchmarks (with 50–957 nodes) and instances of a medical home care delivery problem using census data in Wayne County, Michigan. Using parallel computing, both pulse and random coloring can significantly improve column generation for solving the linear programming relaxations and we can obtain heuristic integer solutions with small optimality gaps. Combining random coloring with column enumeration, we can obtain improved integer solutions having less than 2% optimality gaps for most VRP benchmark instances and less than 1% optimality gaps for the medical home care delivery instances, both under a 30-minute computational time limit. The use of cutting planes (e.g., robust cuts) can further reduce optimality gaps on some hard instances, without much increase in the run time. Summary of Contribution: The vehicle routing problem (VRP) is a fundamental combinatorial problem, and its variants have been studied extensively in the literature of operations research and computer science. In this paper, we consider general-purpose algorithms for solving VRPs, including the column-generation approach for the linear programming relaxations of the integer programs of VRPs and the column-enumeration approach for seeking improved integer solutions. We revise the pulse algorithm and also propose a random-coloring algorithm that can be used for solving the elementary shortest path problem that formulates the pricing problem in the column-generation approach. We show that the parallel implementation of both algorithms can significantly improve the performance of column generation and the random coloring algorithm can improve the solution time and quality of the VRP integer solutions produced by the column-enumeration approach. We focus on algorithmic design for VRPs and conduct extensive computational tests to demonstrate the performance of various approaches.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.23919/ACC.2019.8814708
