Biblio

It has been a hot research topic to research the incorporation of large-scale PEVs into smart grid, such as the valley-fill strategy. However high charging rates under the valley-fill behavior may result in high battery degradation cost. Consequently in this paper, we novelly setup a framework to study a class of charging coordination problems which deals with the tradeoff between total generation cost and the accumulated battery degradation costs for all PEVs during a multi-time interval. Due to the autonomy of individual PEVs and the computational complexity for the system with large-scale PEV populations, it is impractical to implement the solution in a centralized way. Alternatively we propose a novel decentralized method such that each individual submits a charging profile, with respect to a given fixed price curve, which minimizes its own cost dealing with the tradeoff between the electricity cost and battery degradation cost over the charging interval; the price curve is updated based upon the aggregated PEV charging profiles. We show that, following the proposed decentralized price update procedure, the system converges to the unique efficient (in the sense of social optimality) solution under certain mild conditions.

Monitoring large areas using sensors is fundamental in a number of applications, including electric power grid, traffic networks, and sensor-based pollution control systems. However, the number of sensors that can be deployed is often limited by financial or technological constraints. This problem is further complicated by the presence of strategic adversaries, who may disable some of the deployed sensors in order to impair the operator's ability to make predictions. Assuming that the operator employs a Gaussian-process-based regression model, we formulate the problem of attack-resilient sensor placement as the problem of selecting a subset from a set of possible observations, with the goal of minimizing the uncertainty of predictions. We show that both finding an optimal resilient subset and finding an optimal attack against a given subset are NP-hard problems. Since both the design and the attack problems are computationally complex, we propose efficient heuristic algorithms for solving them and present theoretical approximability results. Finally, we show that the proposed algorithms perform exceptionally well in practice using numerical results based on real-world datasets.

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 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.

To systematically study the implications of additional information about routes provided to certain users (e.g., via GPS-based route guidance systems), we introduce a new class of congestion games in which users have differing information sets about the available edges and can only use routes consisting of edges in their information set. After defining the notion of Information Constrained Wardrop Equilibrium (ICWE) for this class of congestion games and studying its basic properties, we turn to our main focus: whether additional information can be harmful (in the sense of generating greater equilibrium costs/delays). We formulate this question in the form of Informational Braess' Paradox (IBP), which extends the classic Braess' Paradox in traffic equilibria, and asks whether users receiving additional information can become worse off. We provide a comprehensive answer to this question showing that in any network in the series of linearly independent (SLI) class, which is a strict subset of series-parallel network, IBP cannot occur, and in any network that is not in the SLI class, there exists a configuration of edge-specific cost functions for which IBP will occur. In the process, we establish several properties of the SLI class of networks, which are comprised of linearly independent networks joined together. These properties include the characterization of the complement of the SLI class in terms of embedding a specific set of subgraphs, and also show that whether a graph is SLI can be determined in linear time. We further prove that the worst-case inefficiency performance of ICWE is no worse than the standard Wardrop Equilibrium with one type of users.

In modern networked control applications, confidentiality and integrity are important features to address in order to prevent against attacks. Moreover, network control systems are a fundamental part of the communication components of current cyber-physical systems (e.g., automotive communications). Many networked control systems employ Time-Triggered (TT) architectures that provide mechanisms enabling the exchange of precise and synchronous messages. TT systems have computation and communication constraints, and with the aim to enable secure communications in the network, it is important to evaluate the computational and communication overhead of implementing secure communication mechanisms. This paper presents a comprehensive analysis and evaluation of the effects of adding a Hash-based Message Authentication (HMAC) to TT networked control systems. The contributions of the paper include (1) the analysis and experimental validation of the communication overhead, as well as a scalability analysis that utilizes the experimental result for both wired and wireless platforms and (2) an experimental evaluation of the computational overhead of HMAC based on a kernel-level Linux implementation. An automotive application is used as an example, and the results show that it is feasible to implement a secure communication mechanism without interfering with the existing automotive controller execution times. The methods and results of the paper can be used for evaluating the performance impact of security mechanisms and, thus, for the design of secure wired and wireless TT networked control systems.

Minimizing the grid impacts of large-scale plug-in electric vehicle (PEV) charging tends to be associated with coordination strategies that seek to fill the overnight valley in electricity demand. However such strategies can result in high charging power, raising the possibility of local overloads within the distribution grid and of accelerated battery degradation. The paper establishes a framework for PEV charging coordination that facilitates the tradeoff between total generation cost and the local costs associated with overloading and battery degradation. A decentralized approach to solving the resulting large-scale optimization problem involves each PEV minimizing their charging cost with respect to a forecast price profile while taking into account local grid and battery effects. The charging strategies proposed by participating PEVs are used to update the price profile which is subsequently rebroadcast to the PEVs. The process then repeats. It is shown that under mild conditions this iterative process converges to the unique, efficient (socially optimal) coordination strategy.

Improvements in mobile networking combined with the ubiquitous availability and adoption of low-cost development boards have enabled the vision of mobile platforms of Cyber-Physical Systems (CPS), such as fractionated spacecraft and UAV swarms. Computation and communication resources, sensors, and actuators that are shared among different applications characterize these systems. The cyber-physical nature of these systems means that physical environments can affect both the resource availability and software applications that depend on resource availability. While many application development and management challenges associated with such systems have been described in existing literature, resilient operation and execution have received less attention. This paper describes our work on improving runtime support for resilience in mobile CPS, with a special focus on our runtime infrastructure that provides autonomous resilience via self-reconfiguration. We also describe the interplay between this runtime infrastructure and our design-time tools, as the later is used to statically determine the resilience properties of the former. Finally, we present a use case study to demonstrate and evaluate our design-time resilience analysis and runtime self-reconfiguration infrastructure.

This paper presents the Robot Operating System Model-driven development tool suite, (ROSMOD) an integrated development environment for rapid prototyping component-based software for the Robot Operating System (ROS) middleware. ROSMOD is well suited for the design, development and deployment of large-scale distributed applications on embedded devices. We present the various features of ROSMOD including the modeling language, the graphical user interface, code generators, and deployment infrastructure. We demonstrate the utility of this tool with a real-world case study: an Autonomous Ground Support Equipment (AGSE) robot that was designed and prototyped using ROSMOD for the NASA Student Launch competition, 2014–2015.

We formulate and analyze a general class of stochastic dynamic games with asymmetric information arising in dynamic systems. In such games, multiple strategic agents control the system dynamics and have different information about the system over time. Because of the presence of asymmetric information, each agent needs to form beliefs about other agents’ private information. Therefore, the specification of the agents’ beliefs along with their strategies is necessary to study the dynamic game. We use Perfect Bayesian equilibrium (PBE) as our solution concept. A PBE consists of a pair of strategy profile and belief system. In a PBE, every agent’s strategy should be a best response under the belief system, and the belief system depends on agents’ strategy profile when there is signaling among agents. Therefore, the circular dependence between strategy profile and belief system makes it difficult to compute PBE. Using the common information among agents, we introduce a subclass of PBE called common information based perfect Bayesian equilibria (CIB-PBE), and provide a sequential decomposition of the dynamic game. Such decomposition leads to a backward induction algorithm to compute CIB-PBE. We illustrate the sequential decomposition with an example of a multiple access broadcast game. We prove the existence of CIBPBE for a subclass of dynamic games.

We consider mechanism design problems for strategic agents with multi-dimensional private information and uncertainty in their utility/cost function. We show that the optimal mechanism with firm allocation can be implemented as a nonlinear pricing scheme, and the optimal mechanism with random allocation can be implemented as a menu of nonlinear pricing schemes.We provide two examples to demonstrate the results: an optimal energy procurement mechanism from a strategic seller with renewable (random) generation, and the design of an optimal demand response program for a network of heterogeneous loads.

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.

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.

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.

With the increased level of distributed generation and demand response comes the need for associated mechanisms that can perform well in the face of increasingly complex deregulated energy market structures. Using Lagrangian duality theory, we develop a decentralized market mechanism that ensures that, under the guidance of a market operator, self-interested market participants: generation companies (GenCos), distribution companies (DistCos), and transmission companies (TransCos), reach a competitive equilibrium. We show that even in the presence of informational asymmetries and nonlinearities (such as power losses and transmission constraints), the resulting competitive equilibrium is Pareto efficient.

The runway configuration is a key driver of airport capacity at any time. Several factors, such as weather conditions (wind and visibility), traffic demand, air traffic controller workload, and the coordination of flows with neighboring airports influence the selection of runway configuration. This paper identifies a discrete-choice model of the configuration selection process from empirical data. The model reflects the importance of various factors in terms of a utility function. Given the weather, traffic demand and the current runway configuration, the model provides a probabilistic forecast of the runway configuration at the next 15-minute interval. This prediction is then extended to obtain the 3-hour probabilistic forecast of runway configuration. The proposed approach is illustrated using case studies based on data from LaGuardia (LGA) and San Francisco (SFO) airports, first by assuming perfect knowledge of weather and demand 3-hours in advance, and then using the Terminal Aerodrome Forecasts (TAFs). The results show that given the actual traffic demand and weather conditions 3 hours in advance, the model predicts the correct runway configuration at LGA with an accuracy of 82%, and at SFO with an accuracy of 85%. Given the forecast weather and scheduled demand, the accuracy of correct prediction of the runway configuration 3 hours in advance is 80% for LGA and 82% for SFO.

In the restructured electricity industry, Generation Expansion Planning (GEP) is an oligopoly of strategic Generation Companies (GenCos) with private information investing in a highly uncertain environment. Strategic planning and uncertainties can result in market manipulation and underinvestment (short-term planning). We present a forward moving approach to the problem of investment expansion planning in the restructured electricity industry. This approach accounts for technological, political and environmental uncertainties in the problem's environment and leads to long-term planning. At each step of the approach we present a block investment market mechanism that has the following features. (F1) It is individually rational. (F2) It is budget balanced. (F3) The expansion and production allocations corresponding to the unique Nash Equilibrium (NE) of the game induced by the mechanism are the same as those that maximize the sum of utilities of the producers and the demand. (F4) It is price efficient that is, the price for electricity at equilibrium is equal to the marginal utility of the demand and to the marginal cost of production by producers with free capacity.

(No abstract.)

We formulate and analyze dynamic games with d-step (d ≥ 1) delayed sharing information structure. The resulting game is a dynamic game of asymmetric information with hidden actions, imperfect observations, and controlled and interdependent system dynamics. We adopt common in- formation based perfect Bayesian equilibrium (CIB-PBE) as the solution concept, and provide a sequential decomposition of the dynamic game. Such a decomposition leads to a backward induction algorithm to compute CIB-PBEs. We discuss the features of our approach to the above class of games and address the existence of CIB-PBEs.

Complex traffic networks include a number of controlled intersections, and, commonly, multiple districts or municipalities. The result is that the overall traffic control problem is extremely complex computationally. Moreover, given that different municipalities may have distinct, non-aligned, interests, traffic light controller design is inherently decentralized, a consideration that is almost entirely absent from related literature. Both complexity and decentralization have great bearing both on the quality of the traffic network overall, as well as on its security. We consider both of these issues in a dynamic traffic network. First, we propose an effective local search algorithm to efficiently design system-wide control logic for a collection of intersections. Second, we propose a game theoretic (Stackelberg game) model of traffic network security in which an attacker can deploy denial-of-service attacks on sensors, and develop a resilient control algorithm to mitigate such threats. Finally, we propose a game theoretic model of decentralization, and investigate this model both in the context of baseline traffic network design, as well as resilient design accounting for attacks. Our methods are implemented and evaluated using a simple traffic network scenario in SUMO.

Spear-phishing attacks pose a serious threat to sensitive computer systems, since they sidestep technical security mechanisms by exploiting the carelessness of authorized users. A common way to mitigate such attacks is to use e-mail filters which block e-mails with a maliciousness score above a chosen threshold. Optimal choice of such a threshold involves a tradeoff between the risk from delivered malicious emails and the cost of blocking benign traffic. A further complicating factor is the strategic nature of an attacker, who may selectively target users offering the best value in terms of likelihood of success and resulting access privileges. Previous work on strategic threshold-selection considered a single organization choosing thresholds for all users. In reality, many organizations are potential targets of such attacks, and their incentives need not be well aligned. We therefore consider the problem of strategic threshold-selection by a collection of independent self-interested users. We characterize both Stackelberg multi-defender equilibria, corresponding to short-term strategic dynamics, as well as Nash equilibria of the simultaneous game between all users and the attacker, modeling long-term dynamics, and exhibit a polynomial-time algorithm for computing short-term (Stackelberg) equilibria. We find that while Stackelberg multi-defender equilibrium need not exist, Nash equilibrium always exists, and remarkably, both equilibria are unique and socially optimal.

The expanding penetration of non-dispatchable renewable resources within power system generation portfolios is motivating the development of demand-side strategies for balancing generation and load. Commercial heating, ventilation, and air conditioning (HVAC) loads are potential candidates for providing such demand-response (DR) services as they consume significant energy and because of the temporal flexibility offered by their inherent thermal inertia. Several ancillary services markets have recently opened up to participation by DR resources, provided they can satisfy certain performance metrics. We discuss different control strategies for providing frequency regulation DR from commercial HVAC systems and components, and compare performance results from experiments and simulation. We also present experimental results from a single  30,000-m2 office building and quantify the DR control performance using standardized performance criteria. Additionally, we evaluate the cost of delivering this service by comparing the energy consumed while providing DR against a counterfactual baseline.

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.

(No abstract.)

In recent years, we have seen a number of successful attacks against high-profile targets, some of which have even caused severe physical damage. These examples have shown us that resourceful and determined attackers can penetrate virtually any system, even those that are secured by the "air-gap." Consequently, in order to minimize the impact of stealthy attacks, defenders have to focus not only on strengthening the first lines of defense but also on deploying effective intrusion-detection systems. Intrusion-detection systems can play a key role in protecting sensitive computer systems since they give defenders a chance to detect and mitigate attacks before they could cause substantial losses. However, an over-sensitive intrusion-detection system, which produces a large number of false alarms, imposes prohibitively high operational costs on a defender since alarms need to be manually investigated. Thus, defenders have to strike the right balance between maximizing security and minimizing costs. Optimizing the sensitivity of intrusion detection systems is especially challenging in the case when multiple interdependent computer systems have to be defended against a strategic attacker, who can target computer systems in order to maximize losses and minimize the probability of detection. We model this scenario as an attacker-defender security game and study the problem of finding optimal intrusion detection thresholds.