We investigate the problem of optimally mitigating the progression of an adversary through a network in real-time, decreasing the probability of it reaching its goal(s), while minimizing the negative impact to availability. Our model is based on a type of attack graph, termed a condition dependency graph, which models the dependencies between security conditions (attacker capabilities) and exploits. By embedding a state space on the graph, we are able to quantify the progression of the attacker over time. The defender is able to interfere with the attacker's progression by blocking some exploits from being carried out. The nature of the attacker's progression through the network is dictated by its private strategy, which depends on the defender's action. The defender's uncertainty of the attacker's true strategy is modeled by considering a finite collection of attacker types. Using noisy security alerts (exhibiting both missed detections and false alarms), the defender maintains a belief representing the joint distribution over the attacker's current capabilities and true strategy. The resulting problem of determining how to optimally interfere with the attacker's progression is cast as a partially observable Markov decision process. To deal with the large state space, we develop a scalable online defense algorithm for tracking beliefs and prescribing defense actions over time. Using the context provided by the state, we are able to efficiently process security alerts even in the presence of a high rate of false alarms. The behavior of the computed defense policy is demonstrated on an illustrative example.

We consider a multiple access communication system where multiple users share a common collision channel. In this system, coordination among users is essential to resolve collision issues. However, each system user can only observe its own local traffic and the feedback from the channel. Without a centralized controller, it is challenging to design an efficient coordination protocol. We present a decentralized common information-based multiple access protocol (CIMA). We show that under CIMA collision is totally avoided without channel sensing and the full throughput region of the collision channel is achieved. In addition, simulation results indicate that the CIMA protocol incurs low transmission delay.

We consider the channel sensing problem arising in opportunistic scheduling over fading channels, cognitive radio networks, and resource constrained jamming. The same problem arises in many other areas of science and technology as it is an instance of restless bandit problems. The communication system consists of N channels. Each channel is modeled as a multi-state Markov chain. At each time instant a user selects one channel to sense and uses it to transmit information. A reward depending on the state of the selected channel is obtained for each transmission. The objective is to design a channel sensing policy that maximizes the expected total reward collected over a finite or infinite horizon. This problem can be viewed as an instance of restless bandit problems, for which the form of optimal policies is unknown in general. We discover sets of conditions sufficient to guarantee the optimality of a myopic sensing policy; we show that under one particular set of conditions the myopic policy coincides with the Gittins index rule.

This note corrects an error in the paper, "An Efficient Game Form for Multi-Rate Multicast Service Provisioning" (ibid., vol. 30, no. 11,pp. 2093-2104, December 2012) which presents a rate allocation mechanism for multi-rate multicast service provisioning in networks with arbitrary topology and strategic users.

We consider the decentralized bandwidth/rate allocation problem in multi-rate multicast service provisioning with strategic users. We demonstrate that such a situation is the combination of a market problem and a public goods problem. We present a mechanism/game form which possesses the following properties when the users' utilities are concave: (1) It implements in Nash equilibria the solution of the corresponding centralized rate allocation problem in multi-rate multicast service provisioning. (2) It is individually rational. (3) It is budget-balanced at all Nash equilibria of the game induced by the mechanism/game form as well as at all off equilibrium messages/strategies that result in feasible allocations.

In this paper we study resource allocation in decentralized information local public good networks. A network is a local public good network if each user's actions directly affect the utility of an arbitrary subset of network users. We consider networks where each user knows only that part of the network that either affects or is affected by it. Furthermore, each user's utility and action space are its private information, and each user is a self utility maximizer. This network model is motivated by several applications including wireless communications. For this network model we formulate a decentralized resource allocation problem and develop a decentralized resource allocation mechanism (game form) that possesses the following properties: (i) All Nash equilibria of the game induced by the mechanism result in allocations that are optimal solutions of the corresponding centralized resource allocation problem (Nash implementation). (ii) All users voluntarily participate in the allocation process specified by the mechanism (individual rationality). (iii) The mechanism results in budget balance at all Nash equilibria and off equilibrium.

In the above titled paper (ibid., vol. 57. no. 8, pp. 5410-5435, Aug. 2011), a correction to the second sentence after equation (4) in Section II is necessary. The correction is presented here.

Sequential problems in decentralized detection are considered. Peripheral sensors make repeated noisy observations of a binary hypothesis. At each time, a peripheral sensor has to decide whether to stop and send a final binary message to a coordinating sensor/fusion center or to continue taking costly measurements. The coordinating sensor's operation is explored under two different scenarios. In the first scenario, the coordinating sensor waits to receive the final message from each of the peripheral sensors and then starts taking costly measurements of its own. The coordinating sensor is then faced with a stopping problem on whether to stop and declare a decision on the hypothesis or to continue taking measurements. In the second scenario, the coordinating sensor starts taking measurements from the beginning, without waiting for the final messages from the peripheral sensors. At any time, the coordinating sensor has to decide whether to stop and declare a decision on the hypothesis or to continue to take more measurements and wait for the peripheral sensors to send their final message. Parametric characterization of optimal policies for the peripheral and the coordinating sensors are obtained under both scenarios. A sequential methodology for finding the optimal policies is presented.

A real-time communication system with two encoders communicating with a single receiver over separate noisy channels is considered. The two encoders make distinct partial observations of a Markov source. Each encoder must encode its observations into a sequence of discrete symbols. The symbols are transmitted over noisy channels to a finite memory receiver that attempts to reconstruct some function of the state of the Markov source. Encoding and decoding must be done in real-time, that is, the distortion measure does not tolerate delays. Under the assumption that the encoders' observations are conditionally independent Markov chains given an unobserved time-invariant random variable, results on the structure of optimal real-time encoding and decoding functions are obtained. It is shown that there exist finite-dimensional sufficient statistics for the encoders. The problem with noiseless channels and perfect memory at the receiver is then considered. A new methodology to find the structure of optimal real-time encoders is employed. A sufficient statistic with a time-invariant domain is found for this problem. This methodology exploits the presence of common information between the encoders and the receiver when communication is over noiseless channels.

In this paper, we consider the problem of monitoring soil moisture evolution using a wireless network of in situ sensors. Continuously sampling moisture levels with these sensors incurs high-maintenance and energy consumption costs, which are particularly undesirable for wireless networks. Our main hypothesis is that a sparser set of measurements can meet the monitoring objectives in an energy-efficient manner. The underlying idea is that we can trade off some inaccuracy in estimating soil moisture evolution for a significant reduction in energy consumption. We investigate how to dynamically schedule the sensor measurements so as to balance this tradeoff. Unlike many prior studies on sensor scheduling that make generic assumptions on the statistics of the observed phenomenon, we obtain statistics of soil moisture evolution from a physical model. We formulate the optimal measurement scheduling and estimation problem as a partially observable Markov decision problem (POMDP). We then utilize special features of the problem to approximate the POMDP by a computationally simpler finite-state Markov decision problem (MDP). The result is a scalable, implementable technology that we have tested and validated numerically and in the field.

We consider a sequential problem in decentralized detection. Two observers can make repeated noisy observations of a binary hypothesis on the state of the environment. At any time, observer 1 can stop and send a final message to observer 2 or it may continue to take more measurements. Every time observer 1 postpones its final message to observer 2, it incurs a penalty. We consider observer 2's operation under two different scenarios. In the first scenario, observer 2 waits to receive the final message from observer 1 and then starts taking measurements of its own. It is then faced with a stopping problem on whether to stop and declare a decision on the hypothesis or to continue taking measurements. In the second scenario, observer 2 starts taking measurements from the beginning. It is then faced with a different stopping problem. At any time, observer 2 can decide whether to stop and declare a decision on the hypothesis or to continue to take more measurements and wait for observer 1 to send its final message. We obtain parametric characterization of optimal policies for the two observers under both scenarios. We then extend these characterizations to a problem with multiple peripheral sensors that each send a single final message to a coordinating sensor who makes the final decision on the hypothesis.

Optimal design of sequential real-time communication of a Markov source over a noisy channel is investigated. In such a system, the delay between the source output and its reconstruction at the receiver should equal a fixed prespecified amount. An optimal communication strategy must minimize the total expected symbol-by-symbol distortion between the source output and its reconstruction. Design techniques or performance bounds for such real-time communication systems are unknown. In this paper a systematic methodology, based on the concepts of information structures and information states, to search for an optimal real-time communication strategy is presented. This methodology trades off complexity in communication length (linear in contrast to doubly exponential) with complexity in alphabet sizes (doubly exponential in contrast to exponential). As the communication length is usually order of magnitudes bigger than the alphabet sizes, the proposed methodology simplifies the search for an optimal communication strategy. In spite of this simplification, the resultant optimality equations cannot be solved efficiently using existing algorithmic techniques. The main idea is to formulate a zero-delay communication problem as a dynamic team with nonclassical information structure. Then, an appropriate choice of information states converts the dynamic team problem into a centralized stochastic control problem in function space. Thereafter, Markov decision theory is used to derive nested optimality equations for choosing an optimal design. For infinite horizon problems, these optimality equations give rise to a fixed point functional equation. Communication systems with fixed finite delay constraint, a higher-order Markov source, and channels with memory are treated in the same manner after an appropriate expansion of the state space. Thus, this paper presents a comprehensive methodology to study different variations of real-time communication.

We have developed a new concept for a smart sensor web technology for measurements of soil moisture that include spaceborne and in-situ assets. The objective of the technology is to enable a guided/adaptive sampling strategy for the in-situ sensor network to meet the measurement validation objectives of the spaceborne sensors with respect to resolution and accuracy. One potential application is the Soil Moisture Active/Passive (SMAP) mission. The science measurements considered are the surface-to-depth profiles of soil moisture estimated from satellite radars and radiometers, with calibration and validation using in-situ sensors. Installing an in-situ network to sample the field for all ranges of variability is impractical. However, a sparser but smarter network can provide the validation estimates by operating in a guided fashion with guidance from its own sparse measurements. The feedback and control take place in the context of a dynamic data assimilation system subject to energy and accuracy constraints. The overall design of the smart sensor web including the control architecture, assimilation framework, and actuation hardware are presented in this paper. We also present results of initial numerical and laboratory demonstrations of the sensor web concept, which includes a small number of soil moisture.

The 13 papers in this special issue focus on control and communications. The papers are summarized here.

A real-time communication system with noisy feedback is considered. The system consists of a Markov source, forward and backward discrete memoryless channels, and a receiver with limited memory. The receiver can send messages to the encoder over the backward noisy channel. The encoding at the encoder and the decoding, the feedback, and the memory update at the receiver must be done in real-time. A distortion metric that does not tolerate delays is given. The objective is to design an optimal real-time communication strategy, i.e., design optimal real-time encoding, decoding, feedback, and memory update strategies to minimize a total expected distortion over a finite horizon. This problem is formulated as a decentralized stochastic optimization problem and a methodology for its sequential decomposition is presented. This results in a set of nested optimality equations that can be used to sequentially determine optimal communication strategies. The methodology exponentially simplifies the search for determining an optimal real-time communication strategy.

We consider zero-delay or fixed finite-delay joint source channel coding of Markov sources using finite memory encoder and decoder. The objective is to choose designs that minimize expected total distortion over a finite horizon, expected discounted distortion over an infinite horizon and average distortion per unit time over an infinite horizon. The above problem is a dynamic team with non-classical information structure. We develop a sequential decomposition for this problem. The main contribution of this paper is to provide a systematic methodology for determination of optimal joint source-channel encoding-decoding strategies for zero-delay or fixed finite-delay point-to-point communication with limited memory

The output of a discrete-time Markov source must be encoded into a sequence of discrete variables. The encoded sequence is transmitted through a noisy channel to a receiver that must attempt to reproduce reliably the source sequence. Encoding and decoding must be done in real-time and the distortion measure does not tolerate delays. The structure of real-time encoding and decoding strategies that jointly minimize an average distortion measure over a finite horizon is determined. The results are extended to the real-time broadcast problem and a real-time variation of the Wyner-Ziv problem

We examine the sensitivity of optimal routing policies in ad hoc wireless networks with respect to estimation errors in channel quality. We consider an ad hoc wireless network where the wireless links from each node to its neighbors are modeled by a probability distribution describing the local broadcast nature of wireless transmissions. These probability distributions are estimated in real-time. We investigate the impact of estimation errors on the performance of a set of proposed routing policies.

We present an approach to defining probability of outage as a system-wide QoS measure for cellular systems. We describe how to use this approach to define an admission region where the requirements on probability of outage are satisfied. We illustrate the approach by constructing the aforementioned admission region for a few examples.

We investigate a conjecture stated by Coffman, Flatto, and Wright within the context of a stochastic machine minimization problem with a hard deadline. We prove that the conjecture is true.

We address the problem of failure diagnosis in discrete event systems with decentralized information. We propose a coordinated decentralized architecture consisting of local sites communicating with a coordinator that is responsible for diagnosing the failures occurring in the system. We extend the notion of diagnosability, originally introduced in Sampath et al. (1995) for centralized systems, to the proposed coordinated decentralized architecture. We specify three protocols, i.e. the diagnostic information generated at the local sites, the communication rules used by the local sites, and the coordinator's decision rule, that realize the proposed architecture. We analyze the diagnostic properties of each protocol. We also state and prove necessary and sufficient conditions for a language to be diagnosable under each protocol. These conditions are checkable off-line. The online diagnostic process is carried out using the diagnosers introduced in the above article or a slight variation of these diagnosers. The key features of the proposed protocols are: (i) they achieve, each under a set of assumptions, the same diagnostic performance as the centralized diagnoser; and (ii) they highlight the performance vs. complexity tradeoff that arises in coordinated decentralized architectures. The correctness of two of the protocols relies on some stringent global ordering assumptions on message reception at the coordinator's site, the relaxation of which is briefly discussed.

The process of communicating in the presence of interference that is unknown or hostile is modeled as a two-person zero-sum game with the communicator and the jammer as the players. The objective function considered is the rate of reliable communication. The communicator's strategies are encoders and distributions on a set of quantizers. The jammer's strategies are distributions on the noise power subject to certain constraints. Various conditions are considered on the jammer's strategy set and on the communicator's knowledge. For the case where the decoder is uninformed of the actual quantizer chosen, it is shown that, from the communicator's perspective, the worst-case jamming strategy is a distribution concentrated on a finite number of points, thereby converting a functional optimization problem into a nonlinear programming problem. Moreover, the worst-case distributions can be characterized by means of necessary and sufficient conditions which are easy to verify. For the case where the decoder is informed of the actual quantizer chosen, the existence of saddle-point strategies is demonstrated. The analysis is also seen to be valid for a number of situations where the jammer is adaptive.>