Biblio

In this paper, we study the sensor placement problem in urban water networks that maximizes the localization of pipe failures given that some sensors give incorrect outputs. False output of a sensor might be the result of degradation in sensor's hardware, software fault, or might be due to a cyber-attack on the sensor. Incorrect outputs from such sensors can have any possible values which could lead to an inaccurate localization of a failure event. We formulate the optimal sensor placement problem with erroneous sensors as a set multicover problem, which is NP-hard, and then discuss a polynomial time heuristic to obtain efficient solutions. In this direction, we first examine the physical model of the disturbance propagating in the network as a result of a failure event, and outline the multi-level sensing model that captures several event features. Second, using a combinatorial approach, we solve the problem of sensor placement that maximizes the localization of pipe failures by selecting $m$ sensors out of which at most $e$ give incorrect outputs. We propose various localization performance metrics, and numerically evaluate our approach on a benchmark and a real water distribution network. Finally, using computational experiments, we study relationships between design parameters such as the total number of sensors, the number of sensors with errors, and extracted signal features.

This article models the interaction between freeway traffic dynamics and capacity-reducing incidents as a stochastic switched system, and analyzes its long-time properties. Incident events on a multi-cell freeway are modeled by a Poisson-like stochastic process. Randomness in the occurrence and clearance of incidents results in traffic dynamics that switch between a set of incident modes (discrete states). The rates of occurrence and clearance depend on the traffic densities (continuous state). The continuous state evolves in each incident mode according to mode-dependent macroscopic flow dynamics. At steady state, the system state resides in its accessible set, which supports an invariant probability measure. Behavior of the accessible set is studied in terms of inputs (on-ramp inflows) and incident parameters (incident intensity). An over-approximation of accessible set and some useful bounds on the performance metrics (throughput and travel time) are also derived using the limiting states of individual incident modes. These results provide following insights about the steady-state system behavior: (i) Expected loss of throughput increases with the incident intensity for fixed incident rate, but this loss is less sensitive to changes in the occurrence rate for fixed intensity; (ii) Operating an incident-prone freeway close to its capacity significantly increases the expected travel time; (iii) The impact of incidents reduces when certain inputs upstream of incident-prone sections are metered.

This article studies the value of information in route choice decisions when a fraction of players have access to high accuracy information about traffic incidents relative to others. To model such environments, we introduce a Bayesian congestion game, in which players have private information about incidents, and each player chooses her route on a network of parallel links. The links are prone to incidents that occur with an ex-ante known probability. The demand is comprised of two player populations: one with access to high accuracy incident information and another with low accuracy information, i.e. the populations differ only by their access to information. The common knowledge includes: (i) the demand and route cost functions, (ii) the fraction of highly-informed players, (iii) the incident probability, and (iv) the marginal type distributions induced by the information structure of the game. We present a full characterization of the Bayesian Wardrop Equilibrium of this game under the assumption that low information players receive no additional information beyond common knowledge. We also compute the cost to individual players and the social cost as a function of the fraction of highly-informed players when they receive perfectly accurate information. Our first result suggests that below a certain threshold of highly-informed players, both populations experience a reduction in individual cost, with the highly-informed players receiving a greater reduction. However, above this threshold, both populations realize the same equilibrium cost. Secondly, there exists another (lower or equal) threshold above which a further increase in the fraction of highly-informed players does not reduce the expected social costs. Thus, once a sufficiently large number of players are highly informed, wider distribution of more accurate information is ineffective at best, and otherwise socially harmful.

This article focuses on the security assessment of electricity distribution networks (DNs) with vulnerable distributed energy resource (DER) nodes. The adversary model is simultaneous compromise of DER nodes by strategic manipulation of generation set-points. The loss to the defender (DN operator) includes loss of voltage regulation and cost of induced load control under supply-demand mismatch caused by the attack. A 3-stage Defender-Attacker-Defender (DAD) game is formulated: in Stage 1, the defender chooses a security strategy to secure a subset of DER nodes; in Stage 2, the attacker compromises a set of vulnerable DERs and injects false generation set-points; in Stage 3, the defender responds by controlling loads and uncompromised DERs. Solving this trilevel optimization problem is hard due to nonlinear power flows and mixed-integer decision variables. To address this challenge, the problem is approximated by tractable formulations based on linear power flows. The set of critical DER nodes and the set-point manipulations characterizing the optimal attack strategy are characterized. An iterative greedy approach to compute attacker-defender strategies for the original nonlinear problem is proposed. These results provide guidelines for optimal security investment and defender response in pre- and post-attack conditions, respectively.

This article considers a two-player strategic game for network routing under link disruptions. Player 1 (defender) routes flow through a network to maximize her value of effective flow while facing transportation costs. Player 2 (attacker) simultaneously disrupts one or more links to maximize her value of lost flow but also faces cost of disrupting links. Linear programming duality in zero-sum games and the Max-Flow Min-Cut Theorem are applied to obtain properties that are satisfied in any Nash equilibrium. A characterization of the support of the equilibrium strategies is provided using graph-theoretic arguments. Finally, conditions under which these results extend to budget-constrained environments are also studied. These results extend the classical minimum cost maximum flow problem and the minimum cut problem to a class of security games on flow networks.

Unreliable link capacities cause a significant amount of delay in transportation networks. In this paper, we propose a novel approach to studying the traffic queues due to capacity-reducing events under a class of control policies. First, we propose a Piecewise-Deterministic Queueing (PDQ) model in which the link saturation rates switch between a finite set of values (modes) according to a Markov chain, which captures the occurrence and clearance of capacity-reducing events. Second, we derive results on the stability of PDQ networks, i.e. when the joint distribution of the link queue sizes converges to a unique invariant probability measure. On one hand, a necessary condition for stability is that the average inflow to each link is less than the link's effective capacity. On the other hand, a sufficient condition is that a set of bilinear matrix inequalities involving model parameters and the control policy has a feasible solution. Third, we provide an analytical characterization of the steady-state distribution of bimodal PDQ systems, which enables us to obtain the optimal static/mode-dependent routing policy for bimodal PDQ networks by solving a convex min-cost problem.

Traffic signals were originally standalone hardware devices running on fixed schedules, but by now, they have evolved into complex networked systems. As a consequence, traffic signals have become susceptible to attacks through wireless interfaces or even remote attacks through the Internet. Indeed, recent studies have shown that many traffic lights deployed in practice have easily exploitable vulnerabilities, which allow an attacker to tamper with the configuration of the signal. Due to hardware-based failsafes, these vulnerabilities cannot be used to cause accidents. However, they may be used to cause disastrous traffic congestions. Building on Daganzo's well-known traffic model, we introduce an approach for evaluating vulnerabilities of transportation networks, identifying traffic signals that have the greatest impact on congestion and which, therefore, make natural targets for attacks. While we prove that finding an attack that maximally impacts congestion is NP-hard, we also exhibit a polynomial-time heuristic algorithm for computing approximately optimal attacks. We then use numerical experiments to show that our algorithm is extremely efficient in practice. Finally, we also evaluate our approach using the SUMO traffic simulator with a real-world transportation network, demonstrating vulnerabilities of this network. These simulation results extend the numerical experiments by showing that our algorithm is extremely efficient in a microsimulation model as well.

Traffic signals were originally standalone hardware devices running on fixed schedules, but by now, they have evolved into complex networked systems. As a consequence, traffic signals have become susceptible to attacks through wireless interfaces or even remote attacks through the Internet. Indeed, recent studies have shown that many traffic lights deployed in practice have easily exploitable vulnerabilities, which allow an attacker to tamper with the configuration of the signal. Due to hardware-based failsafes, these vulnerabilities cannot be used to cause accidents. However, they may be used to cause disastrous traffic congestions. Building on Daganzo's well-known traffic model, we introduce an approach for evaluating vulnerabilities of transportation networks, identifying traffic signals that have the greatest impact on congestion and which, therefore, make natural targets for attacks. While we prove that finding an attack that maximally impacts congestion is NP-hard, we also exhibit a polynomial-time heuristic algorithm for computing approximately optimal attacks. We then use numerical experiments to show that our algorithm is extremely efficient in practice. Finally, we also evaluate our approach using the SUMO traffic simulator with a real-world transportation network, demonstrating vulnerabilities of this network. These simulation results extend the numerical experiments by showing that our algorithm is extremely efficient in a microsimulation model as well.

This paper focuses on the optimal sensor placement problem for the identification of pipe failure locations in large-scale urban water systems. The problem involves selecting the minimum number of sensors such that every pipe failure can be uniquely localized. This problem can be viewed as a minimum test cover (MTC) problem, which is NP-hard. We consider two approaches to obtain approximate solutions to this problem. In the first approach, we transform the MTC problem to a minimum set cover (MSC) problem and use the greedy algorithm that exploits the submodularity property of the MSC problem to compute the solution to the MTC problem. In the second approach, we develop a new augmented greedy algorithm for solving the MTC problem. This approach does not require the transformation of the MTC to MSC. Our augmented greedy algorithm provides in a significant computational improvement while guaranteeing the same approximation ratio as the first approach. We propose several metrics to evaluate the performance of the sensor placement designs. Finally, we present detailed computational experiments for a number of real water distribution networks.

This paper presents a modeling and operation approach for tree water supply systems. The network control problem is approximated as a geometric programming (GP) problem. The original nonlinear nonconvex network control problem is transformed into a convex optimization problem. The optimization model can be efficiently solved to optimality using state-of-the-art solvers. Two control schemes are presented: (1) operation of network actuators (pumps and valves) and (2) controlled demand shedding allocation between network consumers with limited resources. The dual of the network control problem is formulated and is used to perform sensitivity analysis with respect to hydraulic constraints. The approach is demonstrated on a small branched-topology network and later extended to a medium-size irrigation network. The results demonstrate an intrinsic trade-off between energy costs and demand shedding policy, providing an efficient decision support tool for active management of water systems.

We formulate a sequential (Stackelberg) game for assessing the vulnerability of radial electricity distribution networks to disruptions in Distributed Energy Resources (DERs). In this model, the attacker disrupts a subset of DER nodes by remotely manipulating the set-points of their inverters. The defender (network operator) responds by controlling the noncompromised DERs and by imposing partial load reduction via direct load control. The attacker’s (resp. defender’s) objective is to maximize (resp. minimize) the weighted sum of cost due to the loss of voltage regulation and the cost of load control. For the sequential play game where the attacker (resp. defender) is the leader (resp. follower) and under linear power flow equations, we show that the problem reduces to standard bilevel network interdiction problem. Under our assumptions on the attack model, we obtain a structural insight that the attacker’s optimal strategy is to compromise the downstream DER nodes as opposed to the upstream ones. We present a small case study to demonstrate the applicability of our model for vulnerability assessment of distribution networks.

We focus on the question of distributed control of electricity distribution networks in the face of security attacks to Distributed Energy Resources (DERs). Our attack model includes strategic manipulation of DER set-points by an external hacker to induce a sudden compromise of a subset of DERs connected to the network. We approach the distributed control design problem in two stages. In the first stage, we model the attacker-defender interaction as a Stackelberg game. The attacker (leader) disconnects a subset of DERs by sending them wrong set-point signals. The distribution utility (follower) response includes Volt-VAR control of non-compromised DERs and load control. The objective of the attacker (resp. defender) is to maximize (resp. minimize) the weighted sum of the total cost due to loss of frequency regulation and the cost due to loss of voltage regulation. In the second stage, we propose a distributed control (defender response) strategy for each local controller such that, if sudden supply-demand mismatch is detected (for example, due to DER compromises), the local controllers automatically respond based on their respective observations of local fluctuations in voltage and frequency. This strategy aims to achieve diversification of DER functions in the sense that each uncompromised DER node either contributes to voltage regulation (by contributing reactive power) or to frequency regulation (by contributing active power). We illustrate the effectiveness of this control strategy on a benchmark network.

The objective of this work is to develop an efficient and practical sensor placement method for the failure detection and localization in water networks. We formulate the problem as the minimum test cover problem (MTC) with the objective of selecting the minimum number of sensors required to uniquely identify and localize pipe failure events. First, we summarize a single-level sensing model and discuss an efficient fast greedy approach for solving the MTC problem. Simulation results on benchmark test networks demonstrate the efficacy of the fast greedy algorithm. Second, we develop a multi-level sensing model that captures additional physical features of the disturbance event, such as the time lapsed between the occurrence of disturbance and its detection by the sensor. Our sensor placement approach using MTC extends to the multi-level sensing model and an improved identification performance is obtained via reduced number of sensors (in comparison to single-level sensing model). In particular, we investigate the bi-level sensing model to illustrate the efficacy of employing multi-level sensors for the identification of failure events. Finally, we suggest extensions of our approach for the deployment of heterogeneous sensors in water networks by exploring the trade-off between cost and performance (measured in terms of the identification score of pipe/link failures).

The article by Amin, Schwartz, Cárdenas, and Sastry investigates energy theft in smart utility networks using techniques from game theory and detection theory. The game-theoretic model considers pricing and investment decisions by a distribution utility when it serves a population of strategic customers, and a fraction of customers are fraudulent. Each fraudulent customer chooses to steal electricity after accounting for the probability of fraud detection and the amount of fine that they pay if detected. The probabilistic rate of successful detection depends on the distributor's implementation of a diagnostic scheme and increases with level of investment made by the distributor monitoring fraud. The distributor (leader) chooses the level of investment, the price per unit quantity of billed electricity, and the fine schedule. The customers (followers) make their choices after they learn the distributor's decision. For specific assumptions on customer utilities and a distributor's profit function, this leader-follower game is used to compute equilibrium customer and distributor choices. For two environments, namely an unregulated monopoly and the case of perfect competition, the results provide an estimate of the extent of stealing for different levels of investment (high versus low). These results point toward the need for creating regulatory measures to incentivize investments in security and fraud monitoring.

This paper considers a 2-player strategic game for network routing under link disruptions. Player 1 (defender) routes flow through a network to maximize her value of effective flow while facing transportation costs. Player 2 (attacker) simultaneously disrupts one or more links to maximize her value of lost flow but also faces cost of disrupting links. This game is strategically equivalent to a zero-sum game. Linear programming duality and the max-flow min-cut theorem are applied to obtain properties that are satisfied in any mixed Nash equilibrium. In any equilibrium, both players achieve identical payoffs. While the defender's expected transportation cost decreases in attacker's marginal value of lost flow, the attacker's expected cost of attack increases in defender's marginal value of effective flow. Interestingly, the expected amount of effective flow decreases in both these parameters. These results can be viewed as a generalization of the classical max-flow with minimum transportation cost problem to adversarial environments.

This paper considers a 2-player strategic game for network routing under link disruptions. Player 1 (defender) routes flow through a network to maximize her value of effective flow while facing transportation costs. Player 2 (attacker) simultaneously disrupts one or more links to maximize her value of lost flow but also faces cost of disrupting links. This game is strategically equivalent to a zero-sum game. Linear programming duality and the max-flow min-cut theorem are applied to obtain properties that are satisfied in any mixed Nash equilibrium. In any equilibrium, both players achieve identical payoffs. While the defender's expected transportation cost decreases in attacker's marginal value of lost flow, the attacker's expected cost of attack increases in defender's marginal value of effective flow. Interestingly, the expected amount of effective flow decreases in both these parameters. These results can be viewed as a generalization of the classical max-flow with minimum transportation cost problem to adversarial environments.

This paper focuses on the optimal sensor placement problem for the identification of pipe failure locations in large-scale urban water systems. The problem involves selecting the minimum number of sensors such that every pipe failure can be uniquely localized. This problem can be viewed as a minimum test cover (MTC) problem, which is NP-hard. We consider two approaches to obtain approximate solutions to this problem. In the first approach, we transform the MTC problem to a minimum set cover (MSC) problem and use the greedy algorithm that exploits the submodularity property of the MSC problem to compute the solution to the MTC problem. In the second approach, we develop a new \textit{augmented greedy} algorithm for solving the MTC problem. This approach does not require the transformation of the MTC to MSC. Our augmented greedy algorithm provides in a significant computational improvement while guaranteeing the same approximation ratio as the first approach. We propose several metrics to evaluate the performance of the sensor placement designs. Finally, we present detailed computational experiments for a number of real water distribution networks.

(No abstract.)