We study Markov potential games under the infinite horizon average reward criterion. Most previous studies have been for discounted rewards. We prove that both algorithms based on independent policy gradient and independent natural policy gradient converge globally to a Nash equilibrium for the average reward criterion. To set the stage for gradient-based methods, we first establish that the average reward is a smooth function of policies and provide sensitivity bounds for the differential value functions, under certain conditions on ergodicity and the second largest eigenvalue of the underlying Markov decision process (MDP). We prove that three algorithms, policy gradient, proximal-Q, and natural policy gradient (NPG), converge to an $\epsilon$-Nash equilibrium with time complexity $O(\frac{1}{\epsilon^2})$, given a gradient/differential Q function oracle. When policy gradients have to be estimated, we propose an algorithm with $\tilde{O}(\frac{1}{\min_{s,a}\pi(a|s)\delta})$ sample complexity to achieve $\delta$ approximation error w.r.t the $\ell_2$ norm. Equipped with the estimator, we derive the first sample complexity analysis for a policy gradient ascent algorithm, featuring a sample complexity of $\tilde{O}(1/\epsilon^5)$. Simulation studies are presented.

We establish the first finite-time logarithmic regret bounds for the self-tuning regulation problem. We introduce a modified version of the certainty equivalence algorithm, which we call PIECE, that clips inputs in addition to utilizing probing inputs for exploration. We show that it has a $C \log T$ upper bound on the regret after $T$ time-steps for bounded noise, and $C\log^3 T$ in the case of sub-Gaussian noise, unlike the LQ problem where logarithmic regret is shown to be not possible. The PIECE algorithm is also designed to address the critical challenge of poor initial transient performance of reinforcement learning algorithms for linear systems. Comparative simulation results illustrate the improved performance of PIECE.

Interactive decision making, encompassing bandits, contextual bandits, and reinforcement learning, has recently been of interest to theoretical studies of experimentation design and recommender system algorithm research. One recent finding in this area is that the well-known Graves-Lai constant being zero is a necessary and sufficient condition for achieving bounded (or constant) regret in interactive decision-making. As this condition may be a strong requirement for many applications, the practical usefulness of pursuing bounded regret has been questioned. In this paper, we show that the condition of the Graves-Lai constant being zero is also necessary for a consistent algorithm to achieve delay model robustness when reward delays are unknown (i.e., when feedback is anonymous). Here, model robustness is measured in terms of $\epsilon$-robustness, one of the most widely used and one of the least adversarial robustness concepts in the robust statistics literature. In particular, we show that $\epsilon$-robustness cannot be achieved for a consistent (i.e., uniformly sub-polynomial regret) algorithm, however small the nonzero $\epsilon$ value is, when the Grave-Lai constant is not zero. While this is a strongly negative result, we also provide a positive result for linear rewards models (contextual linear bandits, reinforcement learning with linear MDP) that the Grave-Lai constant being zero is also sufficient for achieving bounded regret without any knowledge of delay models, i.e., the best of both the efficiency world and the delay robustness world.

A robust approach for cybersecurity of industrial control systems (ICSs) that utilize programmable logic controllers (PLCs) to control critical industrial processes is demonstrated in this paper. For example, industrial water/chemical tank-based system, the liquid level sensor measurement output data may be compromised or manipulated by attackers, this can cause tank overflow, unregulated, or even malfunction. We proposed a general-purpose method called Dynamic Watermarking (DW) to secure ICSs. The basic idea of DW is that it adds a private random signal watermark on the control signal from the controller, then this watermark signal propagates through the plant and adequately converted then comes back to the attack detector. The attack detector at the actuator side can detect Man-in-the-middle (MiTM) or Masquerade attack on the cascading system in real time. The proposed method is experimentally tested and validated with several cyber-attack scenarios on a laboratory scale water tank level control system controlled by an Allen-Bradley Micro820 PLC.

A Man-in-the-Middle (MiM) can collect over-the-air packets whether from a mobile or a base station, process them, possibly modify them, and forward them to the intended receiver. This paper exhibits the REVEAL protocol that can detect a MiM, whether it has half-duplex capability, full-duplex capability, or double full-duplex capability. The REVEAL protocol creates a sequence of timing-based challenge packets where the transmission times of the packets, their durations, and their frequencies, are chosen to create conflicts at the MiM, and make it impossible for the MiM to function. Implementing the REVEAL protocol in 4G/5G technology, we instantiate a MiM between the 4G/5G base station and a mobile, and exhibit the successful detection mechanisms. With the shared source code, the MiM can be reproduced using software defined radios and protocol efficacy can be verified using any open software defined cellular networks with off-the-shelf devices.

This paper addresses two challenges faced by mm-Wave communication systems in outdoor environments. A temporary blockage of the narrow Line of Sight (LoS) beam between the base station and the mobile, e.g., by an interposed hand, face or a pedestrian, can cause an outage. It has been suggested that a dense deployment of base stations is necessary to combat blockage, which is however a capital expensive proposition. This paper presents a low cost solution. It shows that in outdoor environments with hard surfaces, such as pavements, parking lots, etc., there is generally a ground reflected beam that allows sufficient data rate for a control channel to maintain time synchronization during the blockage of the LoS beam. This makes possible a quick reversion to the LoS beam as soon as the temporary blockage ends. The design of a protocol TERRA is described, and is experimentally shown to avoid outage$84.5~\%$of the time during pedestrian blockages in outdoor environments. The protocol TERRA also addresses a second problem: when the blockage is permanent, or due to mobility, the user has moved away from the earlier serving base station. In such cases a handover to a neighbor base station is needed. There are several challenges of ensuring a soft handover due to the narrow mmWave beams. Since blockages are sudden, the mobile will need to be always ready to switch to a neighbor base station’s beam. This requires that it always have in hand a suitable neighbor base station, as well as continually realign its beam to that neighbor base station while it is mobile. TERRA shows how this is to be done without the neighbor base station’s active cooperation, since connection with it is not yet established. At the same time, TERRA also needs to and does continually realign the mobile’s beam with its presently serving base station to counteract its mobility. TERRA thereby enables the mobile to perform a soft handover to a neighbor base station in the event of a permanent blockage, without requiring any side information, unlike the existing works. Evaluations show that TERRA maintains received signal strength close to the optimal solution while keeping track of the neighbor base station.

This work studies an independent natural policy gradient (NPG) algorithm for the multi-agent reinforcement learning problem in Markov potential games. It is shown that, under mild technical assumptions and the introduction of the \textit{suboptimality gap}, the independent NPG method with an oracle providing exact policy evaluation asymptotically reaches an $\epsilon$-Nash Equilibrium (NE) within $\mathcal{O}(1/\epsilon)$ iterations. This improves upon the previous best result of $\mathcal{O}(1/\epsilon^2)$ iterations and is of the same order, $\mathcal{O}(1/\epsilon)$, that is achievable for the single-agent case. Empirical results for a synthetic potential game and a congestion game are presented to verify the theoretical bounds.

We study robust reinforcement learning (RL) with the goal of determining a well-performing policy that is robust against model mismatch between the training simulator and the testing environment. Previous policy-based robust RL algorithms mainly focus on the tabular setting under uncertainty sets that facilitate robust policy evaluation, but are no longer tractable when the number of states scales up. To this end, we propose two novel uncertainty set formulations, one based on double sampling and the other on an integral probability metric. Both make large-scale robust RL tractable even when one only has access to a simulator. We propose a robust natural actor-critic (RNAC) approach that incorporates the new uncertainty sets and employs function approximation. We provide finite-time convergence guarantees for the proposed RNAC algorithm to the optimal robust policy within the function approximation error. Finally, we demonstrate the robust performance of the policy learned by our proposed RNAC approach in multiple MuJoCo environments and a real-world TurtleBot navigation task.

Motivated by the problem of learning with small sample sizes, this paper shows how to incorporate into support-vector machines (SVMs) those properties that have made convolutional neural networks (CNNs) successful. Particularly important is the ability to incorporate domain knowledge of invariances, e.g., translational invariance of images. Kernels based on the \textit{maximum} similarity over a group of transformations are not generally positive definite. Perhaps it is for this reason that they have not been studied theoretically. We address this lacuna and show that positive definiteness indeed holds \textit{with high probability} for kernels based on the maximum similarity in the small training sample set regime of interest, and that they do yield the best results in that regime. We also show how additional properties such as their ability to incorporate local features at multiple spatial scales, e.g., as done in CNNs through max pooling, and to provide the benefits of composition through the architecture of multiple layers, can also be embedded into SVMs. We verify through experiments on widely available image sets that the resulting SVMs do provide superior accuracy in comparison to well-established deep neural network benchmarks for small sample sizes.

We consider the problem of controlling an unknown stochastic linear system with quadratic costs -- called the adaptive LQ control problem. We re-examine an approach called ``Reward-Biased Maximum Likelihood Estimate'' (RBMLE) that was proposed more than forty years ago, and which predates the ``Upper Confidence Bound'' (UCB) method, as well as the definition of ``regret'' for bandit problems. It simply added a term favoring parameters with larger rewards to the criterion for parameter estimation. We show how the RBMLE and UCB methods can be reconciled, and thereby propose an Augmented RBMLE-UCB algorithm that combines the penalty of the RBMLE method with the constraints of the UCB method, uniting the two approaches to optimism in the face of uncertainty. We establish that theoretically, this method retains ${\mathcal{O}}(\sqrt{T})$ regret, the best known so far. We further compare the empirical performance of the proposed Augmented RBMLE-UCB and the standard RBMLE (without the augmentation) with UCB, Thompson Sampling, Input Perturbation, Randomized Certainty Equivalence and StabL on many real-world examples including flight control of Boeing 747 and Unmanned Aerial Vehicle. We perform extensive simulation studies showing that the Augmented RBMLE consistently outperforms UCB, Thompson Sampling and StabL by a huge margin, while it is marginally better than Input Perturbation and moderately better than Randomized Certainty Equivalence.

We study policy optimization for Markov decision processes (MDPs) with multiple reward value functions, which are to be jointly optimized according to given criteria such as proportional fairness (smooth concave scalarization), hard constraints (constrained MDP), and max-min trade-off. We propose an Anchor-changing Regularized Natural Policy Gradient (ARNPG) framework, which can systematically incorporate ideas from well-performing first-order methods into the design of policy optimization algorithms for multi-objective MDP problems. Theoretically, the designed algorithms based on the ARNPG framework achieve $\tilde{O}(1/T)$ global convergence with exact gradients. Empirically, the ARNPG-guided algorithms also demonstrate superior performance compared to some existing policy gradient-based approaches in both exact gradients and sample-based scenarios.

This article presents considerations toward an information and control architecture for future electric energy systems driven by massive changes resulting from the societal goals of decarbonization and electrification. This article describes the new requirements and challenges of an extended information and control architecture that needs to be addressed for continued reliable delivery of electricity. It identifies several new actionable information and control loops, along with their spatial and temporal scales of operation, which can together meet the needs of future grids and enable deep decarbonization of the electricity sector. The present architecture of electric power grids designed in a different era is thereby extensible to allow the incorporation of increased renewables and other emerging electric loads.

Management of narrow directional beams is critical for mm-wave communication systems. Translational or rotational motion of the user can cause misalignment of transmit and receive beams with the base station losing track of the mobile. Reacquiring the user can take about one second in 5G New Radio systems and significantly impair performance of applications, besides being energy intensive. It is therefore important to manage beams to continually maintain high received signal strength and prevent outages. It is also important to be able to recover from sudden but transient blockage caused by a hand or face interposed in the Line-of-Sight (LoS) path. This work presents a beam management protocol called BeamSurfer that is targeted to the use case of users walking indoors near a base station. It is designed to be minimalistic, employing only in-band information, and not requiring knowledge such as location or orientation of the mobile device or any additional sensors. Evaluations under pedestrian mobility show that 96% of the time it employs beams that are within 3 dB of what an omniscient Oracle would have chosen as the pair of optimal transmit-receive LoS beams. It also recovers from transient LoS blockage by continuing to maintain control packet communication over a pre-selected reflected path that preserves time-synchronization with the base station, which allows it to rapidly recover to the LoS link as soon as it is unblocked.

Modifying the reward-biased maximum likelihood method originally proposed in the adaptive control literature, we propose novel learning algorithms to handle the explore-exploit trade-off in linear bandits problems as well as generalized linear bandits problems. We develop novel index policies that we prove achieve order-optimality, and show that they achieve empirical performance competitive with the state-of-the-art benchmark methods in extensive experiments. The new policies achieve this with low computation time per pull for linear bandits, and thereby resulting in both favorable regret as well as computational efficiency.

We address the issue of safety in reinforcement learning. We pose the problem in an episodic framework of a constrained Markov decision process. Existing results have shown that it is possible to achieve a reward regret of $\tilde{\mathcal{O}}(\sqrt{K})$ while allowing an $\tilde{\mathcal{O}}(\sqrt{K})$ constraint violation in $K$ episodes. A critical question that arises is whether it is possible to keep the constraint violation even smaller. We show that when a strictly safe policy is known, then one can confine the system to zero constraint violation with arbitrarily high probability while keeping the reward regret of order $\tilde{\mathcal{O}}(\sqrt{K})$. The algorithm which does so employs the principle of optimistic pessimism in the face of uncertainty to achieve safe exploration. When no strictly safe policy is known, though one is known to exist, then it is possible to restrict the system to bounded constraint violation with arbitrarily high probability. This is shown to be realized by a primal-dual algorithm with an optimistic primal estimate and a pessimistic dual update.

The Industry 4.0 concept promotes a digital manufacturing (DM) paradigm that can enhance quality and productivity, which reduces inventory and the lead time for delivering custom, batch-of-one products based on achieving convergence of additive, subtractive, and hybrid manufacturing machines, automation and robotic systems, sensors, computing, and communication networks, artificial intelligence, and big data. A DM system consists of embedded electronics, sensors, actuators, control software, and interconnectivity to enable the machines and the components within them to exchange data with other machines, components therein, the plant operators, the inventory managers, and customers. This article presents the cybersecurity risks in the emerging DM context, assesses the impact on manufacturing, and identifies approaches to secure DM.

Consider a multihop wireless network serving multiple flows in which wireless interference constraints between links are described by a link-interference graph. The timely-throughput of a flow is defined as the throughput of packets of that flow that reach their destination node within a specified deadline, and the weighted timely throughput of the network is their weighted average over the flows with a given set of positive weights. The problem is particularly challenging, and has generally been open, when there is wireless interference between transmissions. We show that a modified CSMA routing-scheduling policy with an appropriate set of attempt probabilities is nearly optimal for maximizing weighted timely-throughput. This policy has the useful property that the routing-scheduling decision for an individual packet is solely a function of its location and time-to-deadline, and so a wireless node does not require knowledge of the global network state. It is easily implementable in a decentralized fashion by the nodes given the attempt probabilities. A gradient-based adaptive CSMA routing-scheduling policy to determine the optimal attempt probabilities is further provided. It moves along the gradient of the timely throughput and converges to a local maximum.

Inspired by the Reward-Biased Maximum Likelihood Estimate method of adaptive control, we propose RBMLE – a novel family of learning algorithms for stochastic multi-armed bandits (SMABs). For a broad range of SMABs including both the parametric Exponential Family as well as the non-parametric sub-Gaussian/Exponential family, we show that RBMLE yields an index policy. To choose the bias-growth rate $\alpha(t)$ in RBMLE, we reveal the nontrivial interplay between $\alpha(t)$ and the regret bound that generally applies in both the Exponential Family as well as the sub-Gaussian/Exponential family bandits. To quantify the finite-time performance, we prove that RBMLE attains order-optimality by adaptively estimating the unknown constants in the expression of $\alpha(t)$ for Gaussian and sub-Gaussian bandits. Extensive experiments demonstrate that the proposed RBMLE achieves empirical regret performance competitive with the state-of-the-art methods, while being more computationally efficient and scalable in comparison to the best-performing ones among them.

The transportation sector is on the threshold of a revolution as advances in real-time communication, real-time computing, and sensing technologies have brought to fruition the capability to build Transportation Cyber-Physical Systems (TCPS) such as self-driving cars, unmanned aerial vehicles, adaptive cruise control systems, truck platoons, and so on. While there are many benefits that TCPSs have to offer, a major challenge that needs to be addressed to enable their proliferation is their vulnerability to cyber attacks. In this article, we demonstrate, using laboratory prototypes of TCPSs, how the approach of Dynamic Watermarking can secure them from arbitrary sensor attacks. Specifically, we consider two TCPSs of topical interest: (i) an adaptive cruise control system and (ii) a system of self-driving vehicles tracking given trajectories. In each of these systems, we first show how cyber attacks on sensors can compromise safety and cause collisions between vehicles in spite of the presence of a collision avoidance module in the system. We then apply the approach of Dynamic Watermarking and demonstrate that it detects attacks with “low” delay. Once an attack is detected, the controller can take appropriate control actions to prevent collisions, thereby guaranteeing safety in the sense of collision freedom.

As an increasing amount of data is gathered nowadays and stored in databases, the question arises of how to protect the privacy of individual records in a database even while providing accurate answers to queries on the database. Differential Privacy (DP) has gained acceptance as a framework to quantify vulnerability of algorithms to privacy breaches. We consider the problem of how to sanitize an entire database via a DP mechanism, on which unlimited further querying is performed. While protecting privacy, it is important that the sanitized database still provide accurate responses to queries. The central contribution of this work is to characterize the amount of information preserved in an optimal DP database sanitizing mechanism (DSM). We precisely characterize the utility-privacy trade-off of mechanisms that sanitize databases in the asymptotic regime of large databases. We study this in an information-theoretic framework by modeling a generic distribution on the data, and a measure of fidelity between the histograms of the original and sanitized databases. We consider the popular L1-distortion metric, i.e., the total variation norm that leads to the formulation as a linear program (LP). This optimization problem is prohibitive in complexity with the number of constraints growing exponentially in the parameters of the problem. Our focus on the asymptotic regime enables us characterize precisely, the limit of the sequence of solutions to this optimization problem. Leveraging tools from discrete geometry, analytic combinatorics, and duality theorems of optimization, we fully characterize this limit in terms of a power series whose coefficients are the number of integer points on a multidimensional convex crosspolytope studied by Ehrhart in 1967. Employing Ehrhart theory, we determine a simple closed form computable expression for the asymptotic growth of the optimal privacy-fidelity trade-off to infinite precision. At the heart of the findings is a deep connection between the minimum expected distortion and a fundamental construct in Ehrhart theory - Ehrhart series of an integral convex polytope.

Sequential decision making for lifetime maximization is a critical problem in many real-world applications, such as medical treatment and portfolio selection. In these applications, a “reneging” phenomenon, where participants may disengage from future interactions after observing an unsatisfiable outcome, is rather prevalent. To address the above issue, this paper proposes a model of heteroscedastic linear bandits with reneging, which allows each participant to have a distinct “satisfaction level," with any interaction outcome falling short of that level resulting in that participant reneging. Moreover, it allows the variance of the outcome to be context-dependent. Based on this model, we develop a UCB-type policy, namely HR-UCB, and prove that it achieves $\mathcal{O}\big(\sqrt{{T}(\log({T}))^{3}}\big)$ regret. Finally, we validate the performance of HR-UCB via simulations.

We consider the problem of designing a database sanitization mechanism (DSM) that minimizes, in the expected sense, the L1-distortion between the histograms of original and sanitized databases, while being θ-differentially private (DP). The expected L1-distortion of a corresponding optimal θ-DP DSM provides for an important utility-privacy trade-off. This problem reduces to a prohibitively complex linear program (LP). Using tools from Ehrhart theory, analytic combinatorics and LP theory, we solve this problem and thereby provide a simple closed form computable expression characterizing this trade-off.

An increasing number of applications that will be supported by next generation wireless networks require packets to arrive before a certain deadline for the system to have the desired performance. While many time-sensitive scheduling protocols have been proposed, few have been experimentally evaluated to establish realistic performance. Furthermore, some of these protocols involve high complexity algorithms that need to be performed on a per-packet basis. Experimental evaluation of these protocols requires a flexible platform that is readily capable of implementing and experimenting with these protocols.

Ultra-low per-packet latency has become an essential system requirement as well as a critical challenge for wireless networks. While there is a rich literature on real-time wireless scheduling, it is still unclear what the minimum achievable latency is and what level of throughput can be obtained in practice. This demo presents PULS, a processor-supported software-defined wireless testbed that supports ultra-low-latency scheduling protocols. We will demonstrate that PULS provides strict per-packet latency guarantees as low as 1 millisecond with realistic throughput for wireless networks.

In cyber-physical systems, state estimation errors can be caused not just by process noise or measurement noise in sensors, but also by errors in the communication network. Jitter in packet delivery over a communication network carrying sensor measurements can result in timing errors which result in large outlier type state estimation errors, such as, for example, velocity estimation errors in vehicular control networks. These large outlier types of errors can seriously affect performance and robustness of the overall system. For reliability of cyber-physical systems, it is important to design them to be robust to such types of outliers. We propose a two-pronged approach involving a flexible adaptive model identification algorithm with outlier rejection, which in turn uses an adaptive system model to detect and reject outliers, thus shielding the estimation algorithm and thereby improving reliability. We show that the outlier rejection approach which intercepts and filters the data, combined with simultaneous model adaptation, can result in significantly improved performance of Model Predictive Control (MPC). We demonstrate this by reducing trajectory deviation errors in a vehicular testbed. We implement the overall system over Etherware, a middleware supporting a flexible mechanism that allows the suggested algorithm not only to be remotely incorporated without additional computational burden to the downstream controller, but also to be attached or removed at runtime, without reconfiguration, to adapt to any change of the dynamic plant.

Planning under motion and observation uncertainties requires the solution of a stochastic control problem in the space of feedback policies. In this paper, by restricting the policy class to the linear feedback polices, we reduce the general (n2+ n)-dimensional belief space planning problem to an (n)-dimensional problem. As opposed to the previous literature that search in the space of open-loop optimal control policies, we obtain this reduction in the space of closed-loop policies by obtaining a Linear Quadratic Gaussian (LQG) design with the best nominal performance. Then, by taking the entire underlying trajectory of the LQG controller as the decision variable, we pose a coupled design of the trajectory and estimator (while keeping the design of the controller separate) as a NonLinear Program (NLP) that can be solved by a general NLP solver. We prove that under a first-order approximation and a careful usage of the separation principle, our approximations are valid. We provide an analysis on the existing major belief space planning methods and show that our algorithm keeps the lowest computational burden while searching in the policy space. Finally, we extend our solution to contain general state and control constraints. Our simulation results support our design.

Belief space planning is concerned with the problem of finding the control policy under process and measurement uncertainties. Formulated as a stochastic control problem, the solution of a general Decentralized Partially Observed Markov Decision Process (Dec-POMDP) is a collection of feedback policies for individual agents, maximizing a joint value function. In this paper, we design (m) number of Linear Quadratic Gaussian (LQG) policies for (m) number of agents maximizing the joint performance of the team. Casting the problem as a NonLinear Program (NLP), we propose a framework that reduces the optimization dimension from ((mn)2+ mn) to (mn) with (n) referring to the dimension of each individual agent's state space. As a result, the proposed method reduces the formidable generic Dec-POMDP to a computationally tractable multi-agent planning under uncertainty. Our results in 2D and 3D environments demonstrate the performance of the algorithm and its ability to predict and avoid inter-agent collisions.

The emerging connected-vehicle technology provides a new dimension for developing more intelligent traffic control algorithms for signalized intersections. An important challenge for scheduling in networked transportation systems is the switchover delay caused by the guard time before any traffic signal change. The switch-over delay can result in significant loss of system capacity and hence needs to be accommodated in the scheduling design. To tackle this challenge, we propose a distributed online scheduling policy that extends the well-known Max-Pressure policy to address switch-over delay by introducing a bias factor favoring the current schedule. We prove that the proposed policy is throughput-optimal with switch-over delay. Furthermore, the proposed policy remains optimal when there are both connected signalized intersections and conventional fixed-time ones in the system. With connected-vehicle technology, the proposed policy can be easily incorporated into the current transportation systems without additional infrastructure. Through extensive simulation in VISSIM, we show that our policy indeed outperforms the existing popular policies.

The coming decades may see the large scale deployment of networked cyber-physical systems to address global needs in areas such as energy, water, health care, and transportation. However, as recent events have shown, such systems are vulnerable to cyber attacks. Being safety critical, their disruption or misbehavior can cause economic losses or injuries and loss of life. It is therefore important to secure such networked cyber-physical systems against attacks. In the absence of credible security guarantees, there will be resistance to the proliferation of cyber-physical systems, which are much needed to meet global needs in critical infrastructures and services. This paper addresses the problem of secure control of networked cyber-physical systems. This problem is different from the problem of securing the communication network, since cyber-physical systems at their very essence need sensors and actuators that interface with the physical plant, and malicious agents may tamper with sensors or actuators, as recent attacks have shown. We consider physical plants that are being controlled by multiple actuators and sensors communicating over a network, where some sensors could be “malicious,” meaning that they may not report the measurements that they observe. We address a general technique by which the actuators can detect the actions of malicious sensors in the system and disable closed-loop control based on their information. This technique, called “watermarking,” employs the technique of actuators injecting private excitation into the system, which will reveal malicious tampering with signals. We show how such an active defense can be used to secure networked systems of sensors and actuators.

This paper investigates the problem of optimally determining source-destination connectivity in random networks. Viewing the network as a random graph, we start by investigating the Erdos-Renyi (ER) graph, as well as a structured graph where, interesting, the problem appears to be open. The problem examined is that of determining whether a given pair of nodes, a source S, and a destination D are connected by a path. Assuming that at each step one edge can be tested to see if it exists or not, we determine an optimal policy that minimizes the total expected number of steps. The optimal policy has several interesting features. In order to establish the connectivity of S and D, a policy needs to check all edges on some path to see if they all exist, but to establish the disconnectivity it has to check all edges on some cut to see if none of them exists. The optimal policy has the following form. At each step, it examines the condensation multigraph formed by contracting each known connected component to a single node, and then checks an edge that is simultaneously on a shortest S-D path as well as in a minimum S-D cut. Among such edges, it chooses that which lead to the most opportunities for connection. Interestingly, for an ER graph with n nodes, where there is an edge between two nodes with probability p, the optimal strategy does not depend on p or n, even though the entire graph itself undergoes a sharp transition from disconnectivity to connectivity around p = ln n/n. The policy is efficiently implementable, requiring no more than 30log2n operations to determine which edge to test next. The result also extends to some more general graphs and, meanwhile, provide useful insights into the connectivity determination in random networks.

Planning under process and measurement uncertainties is a challenging problem. In its most general form, it can be modeled as a Partially Observed Markov Decision Process (POMDP) problem. However POMDPs are generally difficult to solve when the underlying spaces are continuous, particularly when beliefs are non-Gaussian, and the difficulty is further exacerbated when there are also non-convex constraints on states. Existing algorithms to address such challenging POMDPs are expensive in terms of computation and memory. In this paper, we provide a feedback policy in non-Gaussian belief space by solving a convex program for common non-linear observation models. The solution involves a Receding Horizon Control strategy using particle filters for the non-Gaussian belief representation. We develop a way of capturing non-convex constraints in the state space and adapt the optimization to incorporate such constraints, as well. A key advantage of this method is that it does not introduce additional variables in the optimization problem and is therefore more scalable than existing constrained problems in belief space. We demonstrate the performance of the method on different scenarios.

Base station (BS) sleeping is an effective way to improve the energy-efficiency of cellular networks. However, it may bring extra user-perceived delay. We conduct a theoretical study into the impact of BS sleeping on both energy-efficiency and user-perceived delay. We consider hysteresis sleep and three typical wake-up schemes, namely single sleep, multiple sleep, and N-limited schemes. We model the system as an M/G/1 vacation queue, which captures the setup time, the mode-changing cost, as well as the counting or detection cost during the sleep mode. Closed-form expressions for the average power and the Laplace-Stieltjes transform of delay distribution are obtained. The impacts of system parameters on these expressions are analyzed. We then formulate an optimization problem to design delay-constrained energy-optimal BS sleeping policies. We show that the optimal solutions possess a special structure, thereby allowing us to obtain them explicitly or numerically by simple bisection search. In addition, the relationship between the optimal power consumption and the mean delay constraint is analyzed, so as to answer the fundamental question: how much energy can be saved by trading off a certain amount of delay? It is shown that this optimal relationship is linear only when the delay constraint is lower than a threshold. Numerical studies are also conducted, where the impact of detection or counting cost during the sleep mode is explored, and the delay distribution under the optimal policy is obtained.

Due to the rapid growth of real-time applications and the ubiquity of IEEE 802.11 MAC as a layer-2 protocol for wireless local area networks (WLANs), it becomes increasingly important to support delay-based quality of service (QoS) in such WLANs. In this paper, we develop a simple and accurate enough analytical model for predicting the queueing delay of real-time multimedia traffic flows in non-homogeneous random access based WLANs. This leads to tractable analysis for meeting queueing delay specifications of a number of flows. In particular, we address the feasibility problem of whether the mean delays required by a set of User Datagram Protocol (UDP) flows supporting real-time multimedia traffic can be guaranteed in WLANs. Based on the model and feasibility analysis, we further develop an optimization technique to minimize the delays for the traffic flows. Moreover, we present a decentralized algorithm and report its implementation and present extensive simulation and experimental trace-based results to demonstrate the accuracy of our model and the performance of the algorithms.

In cyber-physical systems such as in-vehicle wireless sensor networks, a large number of sensor nodes continually generate measurements that should be received by other nodes such as actuators in a regular fashion. Meanwhile, energy-efficiency is also important in wireless sensor networks. Motivated by these, we develop scheduling policies which are energy efficient and simultaneously maintain “regular” deliveries of packets. A tradeoff parameter is introduced to balance these two conflicting objectives. We employ a Markov Decision Process (MDP) model where the state of each client is the time-since-last-delivery of its packet, and reduce it into an equivalent finite-state MDP problem. Although this equivalent problem can be solved by standard dynamic programming techniques, it suffers from a high-computational complexity. Thus we further pose the problem as a restless multi-armed bandit problem and employ the low-complexity Whittle Index policy. It is shown that this problem is indexable and the Whittle indexes are derived. Also, we prove the Whittle Index policy is asymptotically optimal and validate its optimality via extensive simulations.

A problem of much current practical interest is the replacement of the wiring infrastructure connecting approximately 200 sensor and actuator nodes in automobiles by an access point. This is motivated by the considerable savings in automobile weight, simplification of manufacturability, and future upgradability. A key issue is how to schedule the nodes on the shared access point so as to provide regular packet delivery. In this and other similar applications, the mean of the inter-delivery times of packets, i.e., throughput, is not sufficient to guarantee service-regularity. The time-averaged variance of the inter-delivery times of packets is also an important metric. So motivated, we consider a wireless network where an Access Point schedules real-time generated packets to nodes over a fading wireless channel. We are interested in designing simple policies which achieve optimal mean-variance tradeoff in interdelivery times of packets by minimizing the sum of time-averaged means and variances over all clients. Our goal is to explore the full range of the Pareto frontier of all weighted linear combinations of mean and variance so that one can fully exploit the design possibilities. We transform this problem into a Markov decision process and show that the problem of choosing which node's packet to transmit in each slot can be formulated as a bandit problem. We establish that this problem is indexable and explicitly derive the Whittle indices. The resulting Index policy is optimal in certain cases. We also provide upper and lower bounds on the cost for any policy. Extensive simulations show that Index policies perform better than previously proposed policies.

We propose an achievable decode-forward rate region for the two-way multi-relay network. The region is the outcome of a carefully mediated attempt, through a so-called “reverse-order” ranking policy, to privilege the disadvantaged nodes in the network over the advantaged. We use the word “advantage” in reference to the ability of a node to recover the decode-forward outer-bound by virtue of its position in the network. The proposed rate-region shows promise in recovering most of a decode-forward outer-bound which, due to a fundamental deadlock problem we identify, is not tight. The rate region itself is derived from (n-2)! individual regions, each corresponding to a unique decode-forward scheme, which geometrically fit together into an intelligible whole. The underlying theory, offset encoding, appears to be well suited for multi-source multi-relay networks with bidirectional information flow.

In cyber-physical systems such as automobiles, measurement data from sensor nodes should be delivered to other consumer nodes such as actuators in a regular fashion. But, in practical systems over unreliable media such as wireless, it is a significant challenge to guarantee small enough inter-delivery times for different clients with heterogeneous channel conditions and inter-delivery requirements. In this paper, we design scheduling policies aiming at satisfying the inter-delivery requirements of such clients. We formulate the problem as a risk-sensitive Markov Decision Process (MDP). Although the resulting problem involves an infinite state space, we first prove that there is an equivalent MDP involving only a finite number of states. Then we prove the existence of a stationary optimal policy and establish an algorithm to compute it in a finite number of steps.

This demo presents WiMAC, a general-purpose wireless testbed for researchers to quickly prototype a wide variety of real-time MAC protocols for wireless networks. As the interface between the link layer and the physical layer, MAC protocols are often tightly coupled with the underlying physical layer, and need to have extremely small latencies. Implementing a new MAC requires a long time. In fact, very few MACs have ever been implemented, even though dozens of new MAC protocols have been proposed. To enable quick prototyping, we employ the mechanism vs. policy separation to decompose the functionality in the MAC layer and the PHY layer. Built on the separation framework, WiMAC achieves the independence of the software from the hardware, offering a high degree of function reuse and design flexibility. Hence, our platform not only supports easy cross-layer design but also allows protocol changes on the fly. Following the 802.11-like reference design, we demonstrate that deploying a new MAC protocol is quick and simple on the proposed platform through the implementation of the CSMA/CA and CHAIN protocols.

We propose a clean-slate, holistic approach to the design of secure protocols for wireless ad-hoc networks. We design a protocol that enables a collection of distributed nodes to emerge from a primordial birth and form a functioning network. We consider the case when nodes are synchronized and the network is closed, in that no other nodes can join. We define a game between protocols and adversarial nodes, and describe a protocol that is guaranteed to achieve the max-min payoff regardless of what the adversarial nodes do. Moreover, even though the adversarial nodes always know the protocol a priori, we show an even stronger result; the protocol is guaranteed to achieve the min-max payoff. Hence there is a saddle point in the game between protocols and adversarial strategies. Finally, we show that the adversarial nodes are in effect, strategically confined to either jamming or conforming to the protocol. These guarantees are contingent on a set of underlying model assumptions, and cease to be valid if the assumptions are violated.

We build upon the clean-slate, holistic approach to the design of secure protocols for wireless ad-hoc networks proposed in part one. We consider the case when the nodes are not synchronized, but instead have local clocks that are relatively affine. In addition, the network is open in that nodes can enter at arbitrary times. To account for this new behavior, we make substantial revisions to the protocol in part one. We define a game between protocols for open, unsynchronized nodes and the strategies of adversarial nodes. We show that the same guarantees in part one also apply in this game: the protocol not only achieves the max-min utility, but the min-max utility as well. That is, there is a saddle point in the game, and furthermore, the adversarial nodes are effectively limited to either jamming or conforming with the protocol.

Base station (BS) sleeping operation is one of the effective ways to save energy consumption of cellular networks, but it may lead to longer delay to the customers. The fundamental question then arises: How much energy can be traded off by a tolerable delay? In this paper, we characterize the fundamental tradeoffs between total energy consumption and overall delay in a BS with sleep mode operations by queueing models. Here, the BS total energy consumption includes not only the transmitting power but also basic power (for baseband processing, power amplifier, etc.) and switch-over power of the BS working mode, and the overall delay includes not only transmission delay but also queueing delay. Specifically, the BS is modeled as an M/G/1 vacation queue with setup and close-down times, where the BS enters sleep mode if no customers arrive during the close-down (hysteretic) time after the queue becomes empty. When asleep, the BS stays in sleep mode until the queue builds up to N customers during the sleep period ( N-Policy) . Several closed-form formulas are derived to demonstrate the tradeoffs between the energy consumption and the mean delay for different wake-up policies by changing the close-down time, setup time, and the parameter N. It is shown that the relationship between the energy consumption and the mean delay is linear in terms of mean close-down time, but non-linear in terms of N. The explicit relationship between total power consumption and average delay with varying service rate is also analyzed theoretically, indicating that sacrificing delay cannot always be traded off for energy saving. In other words, larger N may lead to lower energy consumption, but there exists an optimal N* that minimizes the mean delay and energy consumption at the same time. We also investigate the maximum delay (delay bound) for certain percentage of service and find that the delay bound is nearly linear in mean delay in the cases tested. Therefore, similar tradeoffs exist between energy consumption and the delay bound. In summary, the closed-form energy-delay tradeoffs cast light on designing BS sleeping and wake-up control policies that aim to save energy while maintaining acceptable quality of service.

Hou et al. have analyzed wireless networks where clients served by an access point require a timely-throughput of packets to be delivered by hard per-packet deadlines and also proved the timely-throughput optimality of certain debt-based policies. However, this is a weak notion of optimality; there might be long time intervals in which a client does not receive any packets, undesirable for real-time applications. Motivated by this, the authors, in an earlier work, introduced a pathwise cost function based on the law of the iterated logarithm, studied in fluctuation theory, which captures the deviation from a steady stream of packet deliveries and showed that a debt-based policy is optimal if the frame length is one. This work extends the analysis of debt-based policies to general frame lengths greater than one, as is important for general applications.

This paper investigates the problem of optimally determining source-destination connectivity in random graphs. We consider the classic Erdos-Renyi (ER) random graph with $n$ nodes, where an edge independently exists between any two nodes with probability p. The problem examined is that of determining whether a given pair of nodes, a source S and a destination D, are connected by a path. Assuming that at each step one edge can be tested to see if it exists or not, we determine an optimal policy that minimizes the total expected number of steps. The optimal policy has several interesting features. In order to establish connectivity of S and D, a policy needs to check all edges on some path to see if they all exist, but to establish disconnectivity it has to check all edges on some cut to see if none of them exists. The optimal policy has the following form. At each step it examines the condensation multigraph formed by contracting each known connected component to a single node, and then checks an edge that is simultaneously on a shortest S-D path as well as in a minimum S-D cut. Among such edges, it chooses that which leads to the most opportunities for connection. Interestingly, the optimal strategy does not depend on p or n, even though the entire graph itself undergoes a sharp transition from disconnectivity to connectivity around p = ln n/n. The policy is efficiently implementable, requiring no more than 30 log2n operations to determine which edge to test next. The result also extends to some more general graphs.

Internet-scale data centers (IDCs) have rapidly proliferated to such an extent that their energy consumption and GreenHouse Gas (GHG) emissions have become an important concern to society. As a result, many IDC operators have started using renewable energy, e.g., wind power, to power their data centers. Unfortunately, the utilization of wind energy has stayed at a low ratio due to the intermittent nature of wind. This paper makes the case that it is in fact possible for a distributed IDC system to exploit multiple uncorrelated wind energy sources to significantly reduce the effect of intermittency and nearly achieve “entirely green” cloud-scale services. This result is obtained based on the analysis of real-world wind power traces from 69 wind farms. The idea is to leverage the front-end load dispatching server to send work to the location where wind power is available. We propose a wind-power-aware (WPA) policy that routes jobs based only on the current states of workloads and wind power availabilities in the data centers. We show that with the WPA policy more than 95% of energy consumption in IDCs can in fact be satisfied by wind power, and, secondly, that achieving this does not require the delaying of processing of jobs due to wind availability. We also show that the locations where data centers are placed play an important role in achieving high wind power utilization. Our analysis shows that wind power utilization can generally lie in a range from 44% to 96%, depending on how the locations of wind farms are selected. We propose a method for location selection that uses the coefficient of variation instead of the correlation coefficient, and show that with this method the utilization can lie in the high end of the above range. Finally, we verify these results by simulations that are based on real-world traces for both workloads and wind power generations.

We consider collocated wireless sensor networks, where each node's transmissions can be heard by every other node. Each node has a Boolean measurement and the goal of the network is to compute a given Boolean function of these measurements. We first consider the worst case setting and study optimal block computation strategies for computing symmetric Boolean functions. We study three classes of functions: threshold functions, delta functions and interval functions. We provide optimal strategies for the first two classes, and a scaling law order-optimal strategy with optimal preconstant for interval functions. We extend the results to the case of integer measurements and certain integer-valued functions. Next, we address the problem of minimizing the expected total number of bits that are transmitted when node measurements are random and drawn from independent Bernoulli distributions. In the case of computing a single instance of a Boolean threshold function, the problem reduces to one of determining the optimal order in which the nodes should transmit. We show that the optimal order of transmissions depends in an extremely simple way on the values of previously transmitted bits and the ordering of the marginal probabilities of the Boolean variables according to the k-th least likely rule: At any transmission, the node that transmits is the one that has the k-th least likely value of its Boolean variable, where k reduces by one whenever a node transmits a one. Initially the value of k is (n +1 - Threshold). Interestingly, the order of transmissions does not depend on the exact values of the probabilities of the Boolean variables. In the case of identically distributed measurements, we further show that the average-case complexity of block computation of a Boolean threshold function is O(θ), where θ is the threshold. We further show how to generalize to a pulse model of communication. One can also consider the related problem of approximate computation given a fixed number of bits. For the special case of the parity function, we show that the greedy strategy is optimal.

We introduce a discrete network corresponding to any Gaussian wireless network that is obtained by simply quantizing the received signals and restricting the transmitted signals to a finite precision. Since signals in the discrete network are obtained from those of a Gaussian network, the Gaussian network can be operated on the quantization-based digital interface defined by the discrete network. We prove that this digital interface is near optimal for Gaussian relay networks and the capacities of the Gaussian and the discrete networks are within a bounded gap ofO(M2) bits, whereMis the number of nodes. We also prove that any near-optimal coding strategy for the discrete network can be naturally transformed into a near-optimal coding strategy for the Gaussian network merely by quantization. We exploit this property by designing a linear coding strategy for the case of layered discrete relay networks. The linear coding strategy is near optimal and achieves all rates withinO(M2) bits of the capacity, independent of channel gains or signal-to-noise ratio. The linear code is therefore a near-optimal strategy for layered Gaussian relay networks and can be used as on the Gaussian network after simply quantizing the signals. The relays in the linear code need not know the channel gains on either the incoming or the outgoing links. The transmit and receive signals at all relays are simply quantized to binary tuples of the same lengthn, which is all that the nodes need to know. The linear network code is a particularly simple scheme and requires all the relay nodes to collect the received binary tuples into a long binary vector and apply a linear transformation on the long vector. The resulting binary vector is split into smaller binary tuples for transmission by the relays. The quantization requirements of the linear network code are completely defined by the parametern, which therefore also determines the resolution of the analog-to-digital and digital-to-analog converters that are required for operating the network within a bounded gap of the network's capacity. As evident from the description, the linear network code explicitly connects network coding for wireline networks with codes for Gaussian networks.

We propose three theories, which can be regarded as attempts to characterize and establish guaranteed properties of wireless networks: (i) How and to what extent can we deliver packets with hard delay bounds? (ii) How and to what extent can we synchronize clocks in wireless networks? (iii) Can we develop provably secure protocols for the entire life-cycle of wireless networks that also optimize a utility measure while operating in a hostile environment? For the first problem, consider an access point serving several clients over unreliable wireless links. Suppose packets arrive for/from the clients, with each packet having a hard deadline, after which it is dropped. We characterize precisely the mix of delivery ratios, channel unreliabilities and hard deadline that the access point can guarantee, under some models. For the second problem, consider a wireless network where clocks at the nodes are linear, though with different rates (skews) and offsets. Nodes can exchange packets with their neighbors, with direction dependent delays. We characterize precisely to what extent clocks can and cannot be synchronized and delays determined. Under a random model the end-to-end error can be kept bounded irrespective of network size. Concerning the third problem, traditionally, wireless protocols have been developed to provide performance. As attacks are identified, the protocols are fortified against the identified vulnerabilities. However, holistic guarantees are not provided against other attacks. We seek to reverse this paradigm. We propose a provable approach that guarantees the protocol suite is secure when the nodes are subject to certain assumptions. The protocols take a set of good nodes mingled with unknown malicious nodes from primordial birth to an operating network, while attaining min-max of a utility function. The maximization is over protocols announced and followed by the good nodes, and the minimization is over all behaviors of the malicious nodes. Further, the malicious nodes are reduced to either cooperating or jamming. [Joint work with Vivek Borkar, Nikolaos Freris, Scott Graham, I-Hong Hou, Yih-Chun Hu, Jonathan Ponniah and Roberto Solis].

The 28 papers in this special issue focus on cooperative networking. The papers can be divided into three categories. The ten papers in the first category focus on relay selection and routing in the network layer. The nine papers in the second category deal with coding and power allocation in the physical layer. The nine papers in the third category study application performance.

The articles in this special issue are devoted to the topic of cooperative networking where individual network nodes can cooperate to achieve desired network performance in a coordinated manner.

Cyber-physical systems (CPSs) are the next generation of engineered systems in which computing, communication, and control technologies are tightly integrated. Research on CPSs is fundamentally important for engineered systems in many important application domains such as transportation, energy, and medical systems. We overview CPS research from both a historical point of view in terms of technologies developed for early generations of control systems, as well as recent results on CPSs in many relevant research domains such as networked control, hybrid systems, real-time computing, real-time networking, wireless sensor networks, security, and model-driven development. We outline the potential for CPSs in many societally important application domains.

We consider the problem of information aggregation in sensor networks, where one is interested in computing a function of the sensor measurements. We allow for block processing and study in-network function computation in directed graphs and undirected graphs. We study how the structure of the function affects the encoding strategies and the effect of interactive information exchange. Depending on the application, there could be a designated collector node, or every node might want to compute the function. We begin by considering a directed graph C = (γ. ε) on the sensor nodes, where the goal is to determine the optimal encoders on each edge which achieve function computation at the collector node. Our goal is to characterize the rate region in R|ε|, i.e., the set of points for which there exist feasible encoders with given rates which achieve zero-error computation for asymptotically large block length. We determine the solution for directed trees, specifying the optimal encoder and decoder for each edge. For general directed acyclic graphs, we provide an outer bound on the rate region by finding the disambiguation requirements for each cut, and describe examples where this outer bound is tight. Next, we address the scenario where nodes are connected in an undirected tree network, and every node wishes to compute a given symmetric Boolean function of the sensor data. Undirected edges permit interactive computation, and we therefore study the effect of interaction on the aggregation and communication strategies. We focus on sum-threshold functions and determine the minimum worst case total number of bits to be exchanged on each edge. The optimal strategy involves recursive in-network aggregation which is reminiscent of message passing. In the case of general graphs, we present a cut-set lower bound and an achievable scheme based on aggregation along trees. For complete graphs, we prove that the complexity of this scheme is no more than twice that of the optimal scheme.

In traditional wireless networks, two nodes cannot simultaneously transmit their packets to each other with one radio device (having no machinery enabling full duplex). To ensure bidirectional communications, we need a medium access protocol to coordinate neighboring nodes' transmissions. Two conflicting design goals for the medium access protocol are the ease of implementation and performance guarantees. We propose a novel medium access protocol which is easily implementable (not requiring clock synchronization) and guarantees performance (the fraction of available slots). Our basic idea is to exploit a set of binary sequences having provably low cross-correlation. Each node has its own code sequence and determines whether to transmit or receive a packet by sequentially examining each bit of the code sequence. As an example, we consider the application of Gold code sequences and theoretically analyze the the fraction of available slots that a Gold-code- based MAC can provide. Our simulation verifies our analysis and shows that a Gold-code-based MAC guarantees the fraction of available slots even on a short time scale.

In a previous paper [7] we have identified a special class of linear hybrid automata, called Deterministic Transversal Linear Hybrid Automata, and shown that an e-reach set up to a finite time, called a bounded e-reach set, can be computed using infinite precision calculations. However, given the linearity of the system and the consequent presence of matrix exponentials, numerical errors are inevitable in this computation. In this paper we address the problem of determining a bounded e-reach set using variable finite precision numerical approximations. We present an algorithm for computing it that uses only such numerical approximations. We further develop an architecture for such bounded e-reach set computation which decouples the basic algorithm for an e-reach set with given parameter values from the choice of several runtime adaptation needed by several parameters in the variable precision approximations.

Mobile devices adopt the IEEE 802.11 PSM (Power-Saving Mode) scheme and its enhancements to reduce their energy consumption when using Wi-Fi interfaces. However, the capability of PSM to save energy is limited when the WLANs are highly congested by other Wi-Fi clients. In this paper, instead of further pursuing the trade-off between power saving and the incurred delay on the client side, we take a different approach and explore the energy saving potential by considering the scheduling policy on the Access Point (AP) side. We find that the traditional packet-level first-come-first-serve policy is not sleep optimal since it keeps the PSM clients awake unnecessarily. We propose SOFA, an AP-centric scheme, which helps PSM clients save energy by minimizing the time they are forced to stay awake while down link traffic is being transmitted to other clients. SOFA delivers down link packets to the PSM clients in an optimal sequence, such that several objective are simultaneously achieved: (i) system-sleep optimality, (ii) energy-fairness, (iii) attention fairness, and (iv) no unnecessary deferral of packets beyond a beacon period. First, it determines an attention quota for each client at the beginning of each beacon period, without requiring any knowledge of available wireless capacity. Then it takes the attention "quota'' and attention request as inputs to decide the down link packet scheduling. We prove the stability and optimality of SOFA. Simulation results shows SOFA dramatically decreases the energy consumption of PSM clients in a crowded WLAN, especially for those clients with small attention requests.

Due to the rapid growth of real-time applications and the ubiquity of IEEE 802.11 MAC as a layer-2 protocol for wireless local area networks (WLANs), it is of increasing interest to support quality of service (QoS) in such WLANs. In this paper, we develop a simple but accurate enough analytical model for predicting queueing delay in non-homogeneous random access based WLANs. This leads to tractable solutions for meeting queueing delay specifications of a number of flows. Using this model, we address the feasibility problem of whether the mean delays required by a set of inelastic flows can be guaranteed in WLANs. Based on the model and feasibility analysis, we further develop an optimization technique to minimize the delays for inelastic flows. We present extensive simulation results to demonstrate the accuracy of our model and the performance of the algorithms.

IEEE 802.11 DCF is the dominant protocol used in existing WLANs. However, the efficiency of DCF progressively degrades with the increase of contending clients in the network as well as the wireless link rate. To address this issue, in this paper, we present a distributed random media access protocol, named CHAIN, which significantly improves uplink performance of WLANs. CHAIN mainly uses overhearing to coordinate clients in a network, and thus introduces little control overhead. The key in CHAIN is a novel piggyback transmission opportunity. In CHAIN, clients maintain a precedence relation among one another, and a client can immediately transmit a new packet after it overhears a successful transmission of its predecessor, without going through the regular contending process. When the network load is low, CHAIN behaves similar to DCF; But when the network becomes congested, clients automatically start chains of transmissions to improve efficiency. CHAIN is derived from DCF and co-exists friendly with it. Moreover, it possesses all the advantages of the 802.11 DCF standard - simplicity, robustness, and scalability. We analytically prove the correctness and fairness of CHAIN. Our extensive simulations on J-SIM verify our analytical results, and demonstrate significant performance gain of CHAIN over DCF.

There is increasing demand for using wireless networks for applications that generate packets with strict per-packet delay constraints. In addition to delay constraints, such applications also have various traffic patterns and require guarantees on throughputs of packets that are delivered within their delay constraints. Furthermore, a mechanism for serving delay-constrained traffic needs to specifically consider the unreliable nature of wireless links, which may differ from link to link. Also, as it is usually infeasible to gather feedback information from all clients after each transmission, broadcasting delay-constrained traffic requires addressing the challenge of the lack of feedback information.

We study the problem of scheduling periodic real-time tasks which have individual minimum reward requirements. We consider situations where tasks generate jobs that can be provided arbitrary service times before their deadlines, and obtain rewards based on the service times received by the jobs of the task. We show that this model is compatible with the imprecise computation models and the increasing reward with increasing service models. In contrast to previous work on these models, which mainly focus on maximizing the total reward in the system, we additionally aim to fulfill different reward requirements by different tasks. This provides better fairness and also allows fine-grained tradeoff between tasks. We first derive a necessary and sufficient condition for a system with reward requirements of tasks to be feasible. We next obtain an off-line feasibility optimal scheduling policy. We then study a sufficient condition for a policy to be feasibility optimal or achieve some approximation bound. This condition serves as a guideline for designing on-line scheduling policy and we obtain a greedy policy based on it. We prove that the on-line policy is feasibility optimal when all tasks have the same periods, and also obtain an approximation bound for the policy under general cases. We test our policies in comparative simulations.

For every Gaussian network, there exists a corresponding deterministic network called the discrete superposition network . We show that this discrete superposition network provides a near-optimal digital interface for operating a class consisting of many Gaussian networks in the sense that any code for the discrete superposition network can be naturally lifted to a corresponding code for the Gaussian network, while achieving a rate that is no more than a constant number of bits lesser than the rate it achieves for the discrete superposition network. This constant depends only on the number of nodes in the network and not on the channel gains or SNR. Moreover the capacities of the two networks are within a constant of each other, again independent of channel gains and SNR. We show that the class of Gaussian networks for which this interface property holds includes relay networks with a single source-destination pair, interference networks, multicast networks, and the counterparts of these networks with multiple transmit and receive antennas. The code for the Gaussian relay network can be obtained from any code for the discrete superposition network simply by pruning it. This lifting scheme establishes that the superposition model can indeed potentially serve as a strong surrogate for designing codes for Gaussian relay networks. We present similar results for the K ×K Gaussian interference network, MIMO Gaussian interference networks, MIMO Gaussian relay networks, and multicast networks, with the constant gap depending additionally on the number of antennas in case of MIMO networks.

Congestion control algorithms seek to optimally utilize network resources by allocating a certain rate for each user. However, malicious clients can disregard the congestion control algorithms implemented at the clients and induce congestion at bottleneck links. Thus, in an adversarial environment, the network must enforce the congestion control algorithm in order to attain the optimal network utilization offered by the algorithm. Prior work protects only a single link incident on the enforcement routers neglecting damage inflicted upon other downstream links. We present CRAFT, a capability-based scheme to secure all downstream links of a deploying router. Our goal is to enforce a network-wide congestion control algorithm on all flows. As a reference design, we develop techniques to enforce the TCP congestion control. Our design regulates all flows to share bandwidth resources in a TCP-fair manner by emulating the TCP state machine in a CRAFT router. As a result, once a flow passes a single CRAFT router, it is TCP-fair on all downstream links of that router.

In wireless networks, how to select transmit power that maximizes throughput is a challenging problem. On one hand, transmissions at a high power level could increase interference to others; on the other hand, transmissions at a low power level are prone to being interfered by others. Prior works consider this problem as a search for afixedoptimal power setting that maximizes communication spatial reuse. In this paper, we pursue a novel approach that combines power selection with a random medium access mechanism. For each transmission, a noderandomlyselects a transmit power from all available power levels to access the medium. In this way, all combinations of network power settings could be selected with some probability. Using a recently developed Markov chain model, we derive a distributed scheme that determines the access probabilities of each power setting, according to the arrival rate of traffic and the service rate achieved by the scheme. We show that this scheme always converges to the optimal solution. Moreover, we also show that the random scheme can attain the maximal throughput region that can be obtained by any time-sharing between power settings, and which is consequently larger than the region any fixed power setting can achieve.

This paper studies the problem of utility maximization for clients with delay based QoS requirements in wireless networks. We adopt a model used in a previous work that characterizes the QoS requirements of clients by their delay constraints, channel reliabilities, and timely throughput requirements. In this work, we assume that the utility of a client is a function of the timely throughput it obtains. We treat the timely throughput for a client as a tunable parameter by the access point (AP), instead of a given value as in the previous work. We then study how the AP should assign timely throughputs to clients so that the total utility of all clients is maximized. We apply the techniques introduced in two previous papers to decompose the utility maximization problem into two simpler problems, a CLIENT problem and an ACCESS-POINT problem. We show that this decomposition actually describes a bidding game, where clients bid for the service time from the AP. We prove that although all clients behave selfishly in this game, the resulting equilibrium point of the game maximizes the total utility. In addition, we also establish an efficient scheduling policy for the AP to reach the optimal point of the ACCESS-POINT problem. We prove that the policy not only approaches the optimal point but also achieves some forms of fairness among clients. Finally, simulation results show that our proposed policy does achieve higher utility than all other compared policies.

We develop a general approach for designing scheduling policies for real-time traffic over wireless channels. We extend prior work, which characterizes a real-time flow by its traffic pattern, delay bound, timely-throughput requirement, and channel reliability, to allow time-varying channels, allow clients to have different deadlines, and allow for the optional employment of rate adaptation. Thus, our model allow the treatment of more realistic fading channels as well as scenarios with mobile nodes, and the usage of more general transmission strategies. We derive a sufficient condition for a scheduling policy to be feasibility optimal, and thereby establish a class of feasibility optimal policies. We demonstrate the utility of the identified class by deriving a feasibility optimal policy for the scenario with rate adaptation, time-varying channels, and heterogeneous delay bounds. When rate adaptation is not available, we also derive a feasibility optimal policy for time-varying channels. For the scenario where rate adaptation is not available but clients have different delay bounds, we describe a heuristic. Simulation results are also presented which indicate the usefulness of the scheduling policies for more realistic and complex scenarios.

We address a sequential decision problem that arises in the computation of symmetric Boolean functions of distributed data. We consider a collocated network, where each node's transmissions can be heard by every other node. Each node has a Boolean measurement and we wish to compute a given Boolean function of these measurements. We suppose that the measurements are independent and Bernoulli distributed. Thus, the problem of optimal computation becomes the problem of optimally ordering nodes' transmissions so as to minimize the total expected number of bits. We solve the ordering problem for the class of Boolean threshold functions. The optimal ordering is dynamic, i.e., it could potentially depend on the values of previously transmitted bits. Further, it depends only on the ordering of the marginal probabilites, but not on their exact values. This provides an elegant structure for the optimal strategy. For the case where each node has a block of measurements, the problem is significantly harder, and we conjecture the optimal strategy.

In this paper, we address the scenario where nodes with sensor data are connected in a tree network, and every node wants to compute a given symmetric Boolean function of the sensor data. We first consider the problem of computing a function of two nodes with integer measurements. We allow for block computation to enhance data fusion efficiency, and determine the minimum worst-case total number of bits to be exchanged to perform the desired computation. We establish lower bounds using fooling sets, and provide a novel scheme which attains the lower bounds, using information theoretic tools. For a class of functions called sum-threshold functions, this scheme is shown to be optimal. We then turn to tree networks and derive a lower bound for the number of bits exchanged on each link by viewing it as a two node problem. We show that the protocol of recursive in-network aggregation achieves this lower bound in the case of sum-threshold functions. Thus we have provided a communication and in-network computation strategy that is optimal for each link. All the results can be extended to the case of non-binary alphabets. In the case of general graphs, we present a cut-set lower bound, and an achievable scheme based on aggregation along trees. For complete graphs, the complexity of this scheme is no more than twice that of the optimal scheme.

Clients in wireless networks may have per-packet delay con-straints on their traffic. Further, in contrast to wireline net-works, the wireless medium is subject to fading. In such a time-varying environment, we consider the system problem of maximizing the total utility of clients, where the utilities are determined by their long-term average rates of being served within their delay constraints. We also allow for the addi-tional fairness requirement that each client may require a cer-tain minimum service rate. This overall model can be applied to a wide range of applications, including delay-constrained networks, mobile cellular networks, and dynamic spectrum allocation. We address this problem through convex programming. We propose an on-line scheduling policy and prove that it is utility-optimal. Surprisingly, this policy does not need to know the probability distribution of system states. We also design an auction mechanism where clients are scheduled and charged according to their bids. We prove that the auction mechanism restricts any selfish client from improving its utility by faking its utility function. We also show that the auction mechanism schedules clients in the same way as that done by the on-line scheduling policy. Thus, the auction mechanism is both truth-ful and utility-optimal. Finally, we design specific algorithms that implement the auction mechanism for a variety of appli-cations.

VANET protocols need to exploit the special structure of vehicular networks. This structure includes the one-dimensional nature of roads, the structure of lanes, the group mobility of vehicles, and the communication patterns of the envisaged applications. It is therefore of interest to examine how to specifically tailor VANET protocols to exploit all the above properties. In this paper, motivated by the goal of providing significantly better application level QoS, we study the MAC problem, and examine to what extent one can improve the performance of the mechanism employed in the IEEE 802.11p protocol. We design a dynamic channel reservation (DCR) protocol which leverages the special structure of VANET, and provides greater predictability in channel access, simplifying QoS provision. The key idea, in light of the periodic communication pattern of VANET applications, is to transform the per-packet channel contention mechanism of 802.11p into a per-vehicle one in DCR. We implement the protocol on NS-2 for a comparative evaluation against 802.11p under realistic VANET scenarios. DCR demonstrates lower packet loss probability and higher throughput over 802.11p, and the simulation results appear promising enough to develop a complete protocol specifically for vehicular networks.

Sensor networks potentially feature large numbers of nodes. The nodes can monitor and sense their environment over time, communicate with each other over a wireless network, and process information that they exchange with each other. They differ from data networks in that the network as a whole may be designed for a specific application. We study the theoretical foundations of such large-scale sensor networks. We address four fundamental organizational and operational issues related to large sensor networks: connectivity, capacity, clocks, and function computation. To begin with, a sensor network must be connected so that information can indeed be exchanged between nodes. The connectivity graph of an ad hoc network is modeled as a random graph and the critical range for asymptotic connectivity is determined, as well as the critical number of neighbors that a node needs to connect to. Next, given connectivity, we address the issue of how much data can be transported over the sensor network. We present fundamental bounds on capacity under several models, as well as architectural implications for how wireless communication should be organized. Temporal information is important both for the applications of sensor networks as well as their operation. We present fundamental bounds on the synchronizability of clocks in networks, and also present and analyze algorithms for clock synchronization. Finally, we turn to the issue of gathering relevant information, which sensor networks are designed to do. One needs to study optimal strategies for in-network aggregation of data, in order to reliably compute a composite function of sensor measurements, as well as the complexity of doing so. We address the issue of how such computation can be performed efficiently in a sensor network and the algorithms for doing so, for some classes of functions.

In this paper we present fundamental results on secure clock synchronization and man-in-the-middle detection using only timing information. Under the assumption of afflne clocks, we present a clock synchronization protocol that can operate on any channel on which data can be sent. We present a clock synchronization protocol from the literature and add verification steps on top of this protocol. These verification steps force man- in-the-middle attackers, who want to delay traffic between the endpoints and yet remain undetected, to impose only constant delays on packets. In a special case, we show that it is possible to identify and ignore attacker-delayed packets. We then show three different types of attackers: a half-duplex attacker that can always be caught using timing information alone, a double full-duplex attacker that can never be caught using only timing information, and a full-duplex attacker whose capability to perform man-in-the- middle attacks depends on its location relative to the endpoints and on the turnaround times of the endpoints. In particular, we prove that certain attackers are impossible to detect using only timing, and we construct defensive protocols that prevent all other man-in- the-middle delay attacks. A particularly noteworthy result is that a single attacker using the same radio technology as the endpoints can never successfully perform a man-in-the-middle attack to delay traffic. These results form a lightweight man-in-the-middle attack detection protocol, on top of which a wide variety of protocols can be built, including routing protocols and more sophisticated heavyweight protocols.

Wireless networks are increasingly used to carry applications with QoS constraints. Two problems arise when dealing with traffic with QoS constraints. One is admission control, which consists of determining whether it is possible to fulfill the demands of a set of clients. The other is finding an optimal scheduling policy to meet the demands of all clients. In this paper, we propose a framework for jointly addressing three QoS criteria: delay, delivery ratio, and channel reliability. We analytically prove the necessary and sufficient condition for a set of clients to be feasible with respect to the above three criteria. We then establish an efficient algorithm for admission control to decide whether a set of clients is feasible. We further propose two scheduling policies and prove that they are feasibility optimal in the sense that they can meet the demands of every feasible set of clients. In addition, we show that these policies are easily implementable on the IEEE 802.11 mechanisms. We also present the results of simulation studies that appear to confirm the theoretical studies and suggest that the proposed policies outperform others tested under a variety of settings.

In many low-power networks, the power cost for a node to remain ON to listen to transmissions from other nodes or to transmit to other nodes can constitute a significant part of the total power consumption by the radio. Thus, unlike the traditional relay channel model, under a low power constraint, the relay node cannot stay ON and listen to the entire duration of the transmission. We study the slope of the capacity-power function at zero power for relay channels where the power cost of remaining ON is explicitly taken into account. We show that in this low-power limit, information is conveyed primarily through the ON-OFF activity of the source. The relay node should have significantly more power compared to the source node in order to improve the slope at zero power. The rough intuition is that, in order for a relay node to be useful, it needs to stay ON and listen during a significant portion of the time during which the source node may transmit. This fact limits the utility of the relay to those cases where the it has much higher power than the source node it is trying to help.

Providing differentiated Quality of Service (QoS) over unreliable wireless channels is an important challenge for supporting several future applications. We analyze a model that has been proposed to describe the QoS requirements by four criteria: traffic pattern, channel reliability, delay bound, and throughput bound. We study this mathematical model and extend it to handle variable bit rate applications. We then obtain a sharp characterization of schedulability vis-a-vis latencies and timely throughput. Our results extend the results so that they are general enough to be applied on a wide range of wireless applications, including MPEG Variable-Bit-Rate (VBR) video streaming, VoIP with differentiated quality, and wireless sensor networks (WSN).

Routing protocols for multihop wireless networks have traditionally used shortest path routing to obtain paths to destinations and do not consider traffic load or delay as an explicit factor in the choice of routes. We focus on static mesh networks and formally establish that if the number of sources is not too large, then it is possible to construct a perfect flow-avoiding routing, which can boost the throughput provided to each user over that of the shortest path routing by a factor of four when carrier sensing can be disabled or a factor of 3.2 otherwise. So motivated, we address the issue of designing a multipath, load adaptive routing protocol that is generally applicable even when there are more sources. We develop a protocol that adaptively equalizes the mean delay along all utilized routes from a source to destination and does not utilize any routes that have greater mean delay. This is the property satisfied by a system in Wardrop equilibrium. We also address the architectural challenges confronted in the software implementation of a multipath, delay-feedback-based, probabilistic routing algorithm. Our routing protocol is 1) completely distributed, 2) automatically load balances flows, 3) uses multiple paths whenever beneficial, 4) guarantees loop-free paths at every time instant even while the algorithm is suntil converging, and 5) amenable to clean implementation. An ns-2 simulation study indicates that the protocol is able to automatically route flows to "avoid" each other, consistently out-performing shortest path protocols in a variety of scenarios. The protocol has been implemented in user space with a small amount of forwarding mechanism in a modified Linux 2.4.20 kernel. Finally, we discuss a proof-of-concept measurement study of the implementation on a six node testbed.

Motivated by the increasing usage of wireless broadcast networks for multicast real-time applications like video, this paper considers a canonical real-time multicast scheduling problem for a wireless broadcast LAN. A wireless access point (AP) has N latency-sensitive flows, each associated with a deadline and a multicast group of receivers that desire to receive all the packets successfully by their corresponding deadlines. We consider periodic and one-shot models of real-time arrivals. The channel from the AP to each receiver is a wireless erasure channel, independent across users and slots. We wish to find a communication strategy that minimizes the total deadlines missed across all receivers, where a receiver counts a miss if it does not receive a packet by its deadline. We cast this problem as a restless bandit in stochastic control. We use Whittle's relaxation framework for restless bandits to establish Whittle-indexability for multicast realtime scheduling under the assumption of complete feedback from all receivers in every slot. For the Whittle relaxation, we show that for each flow, the AP's decision between transmitting in a slot and idling has a threshold structure. For the homogeneous case where the erasure channel to each receiver is identically distributed with parameter p, the Whittle index of a flow is xi(1 - p) , where xiis the number of receivers who have yet to receive the current packet of flow i. For the general heterogeneous case in which the erasure channel to receiver j has loss probability pj, the Whittle index corresponding to each flow is Sigmaj(1- pj), where the sum is over all multicast receivers who are yet to receive the packet. We bound the performance of the optimal Whittle relaxation with respect to the optimal wireless multicast real-time scheduler. The heuristic index policy that schedules the flow with the maximum Whittle index in each slot is simple. To relax the complete feedback assumption, we design a scalable mechanism based on statistical estimation theory that obtains the required feedback from all the receivers using a single ACK per packet transmission. The resultant policy is amenable to low-complexity implementation.

We study channel aware distributed scheduling in ad hoc networks where many links contend for the common channel using random access, and the focus here is on the model where each transmitter node has multiple intended receivers. In such a network, channel probing takes place in two phases: 1) in phase I, all transmitters contend for the channel using random access to reserve the channel, and the probing to accomplish a successful channel contention takes a random duration; and 2) in phase II, subsequent probings are carried out to estimate the link conditions from the successful transmitter in phase I to its intended receivers, according to specific probing mechanisms, and the probing for each receiver takes a constant duration. We shall study various probing mechanisms for utilizing multi-receiver diversity in phase II and multiuser diversity in phase I for ad hoc (peer-to-peer) communications. Clearly, further probing increases the likelihood of seeing better channel conditions for exploiting diversities, but at the cost of additional time. Therefore, channel probing must be done efficiently to balance the tradeoff between the throughput gain from better channel conditions and the probing cost. One main objective of this study is to characterize this tradeoff in a stochastic decision making framework. Specifically, we cast network throughput optimization as an optimal stopping problem, and then explore channel aware distributed scheduling to leverage multi-receiver diversity and multiuser diversity in a joint manner. We show that the optimal scheduling policies for all proposed probing mechanisms exhibit threshold structures, indicating that they are amenable to easy distributed implementation. We show that the optimal thresholds and the maximum network throughput can be obtained off-line by solving fixed point equations. We further develop iterative algorithms to compute the optimal thresholds and the throughput.

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

In networked control, there is locational freedom in choosing the node at which to locate the controller, so as to mitigate the effects of packet losses in the network. What is the optimal location for the placement of the control logic? Second, what is the optimal control law in that position? The difficulty in answering these two questions is that analysis of optimality in networked control systems subject to random packet drops suffers from Witsenhausen's 'non-classical information pattern'. Thus, the general problem is considered intractable. We make headway on this problem by using a "Long Packet Assumption", LPA, which allows packets to be arbitrarily long. This is not intended for implementation, but only to develop a lower bound on the cost. In particular, under this assumption the optimal controller location can be shown to be collocated with the actuator. For this position, under the LPA, we can also calculate the optimal cost, which is then a lower bound on the optimal cost for the original problem for all locations. Despite the apparent strength of the LPA, we have found that this lower bound is often close to currently realizable upper bounds. This establishes the near optimality of currently implementable controllers in such instances. Using the lower bound on cost we obtain a necessary condition for stabilizability over all controller locations. This condition matches known sufficient conditions for some special cases, thus establishing a necessary and sufficient condition for location optimized stabilizability of networked control systems with packet loss.

Cyber-physical systems are networked, component-based, real-time systems that control and monitor the physical world. We need software architectures that limit fault-propagation across unreliable components. This paper introduces our simplex reference model which is distinguished by: a plant being controlled in an external context, a machine performing the control, a domain model that estimates the plant state, and the safety requirements that must be met. The simplex reference model assists with constructing CPS architectures which limit fault-propagation. We present a representative case study to highlight the ideas behind the model and our particular decomposition.

The seven papers in this special issue focus on developments in the area of vehicular networks.

Networks with multiple source–destination pairs, involving possibly multicast, and where there are multiple nodes that can serve as potential relay nodes, are considered. A multisource, multirelay coding scheme is developed. In this scheme, each source's information is sent to its destination nodes via a multirelay route, with the multiple multirelay routes operating concurrently even when they intersect with each other, in the same spirit as code-division multiple access (CDMA). It is found that in the generalization to multiple sources, backward decoding achieves higher rates than sliding-window decoding. The routing structure where a joint backward decoding can be performed is characterized. The achievable rate region is found to combine aspects of both multiple relay and multiple access. Potential applications of this coding scheme to sensor networks are discussed. In particular, the exact capacity for the data downloading problem in sensor networks, where there are multiple sensor sources and one sink or collector node, is established for certain geometries when there is phase fading that is unknown to the transmitter.

A multi-relay scheme is developed for networks with multiple sources. By this scheme, each source is sent to its destination nodes via a multi-relay route, and the multiple multi-relay routes from the multiple sources can operate at the same time even if they intersect with each other, in the same spirit of the code-division multiple-access (CDMA). It is found that in the generalization to multiple sources, the backward decoding achieves higher rates than the sliding-window decoding. The corresponding achievable rate region is characterized. Potential applications of this scheme to sensor networks are discussed, where capacity results in certain scenarios are established

Patterns are a valuable method for communicating software engineering expertise about proven solutions for common problems. This paper evaluates the use of domain-independent patterns in a case study of Etherware, a middleware for networked control with a real-time, safety-critical applications model. The case study illustrates the positive and negative impact that four existing patterns have on availability, reliability, and robustness for real-time, safety-critical systems. In particular, we observe Etherware's specialized usage of the filter pattern, confirm this usage among other middleware technologies, and subsequently present the adaptive control filter, a design pattern for real-time, safety-critical middleware which can mitigate timing dependencies in networked control

Wireless networks with a minimum inter-node separation distance are studied where the signal attenuation grows in magnitude as 1/ρ/sup δ/ with distance ρ. Two performance measures of wireless networks are analyzed. The transport capacity is the supremum of the total distance-rate products that can be supported by the network. The energy cost of information transport is the infimum of the ratio of the transmission energies used by all the nodes to the number of bit-meters of information thereby transported. If the phases of the attenuations between node pairs are uniformly and independently distributed, it is shown that the expected transport capacity is upper-bounded by a multiple of the total of the transmission powers of all the nodes, whenever δ>2 for two-dimensional networks or δ>5/4 for one-dimensional networks, even if all the nodes have full knowledge of all the phases, i.e., full channel state information. If all nodes have an individual power constraint, the expected transport capacity grows at most linearly in the number of nodes due to the linear growth of the total power. This establishes the best case order of expected transport capacity for these ranges of path-loss exponents since linear scaling is also feasible. If the phases of the attenuations are arbitrary, it is shown that the transport capacity is upper-bounded by a multiple of the total transmission power whenever δ>5/2 for two-dimensional networks or δ>3/2 for one-dimensional networks, even if all the nodes have full channel state information. This shows that there is indeed a positive energy cost which is no less than the reciprocal of the above multiplicative constant. It narrows the transition regime where the behavior is still open, since it is known that when δ<3/2 for two-dimensional networks, or δ<1 for one-dimensional networks, the transport capacity cannot generally be bounded by any multiple of the

Wireless planar networks have been used to model wireless networks in a tradition that dates back to 1961 to the work of E. N. Gilbert. Indeed, the study of connected components in wireless networks was the motivation for his pioneering work that spawned the modern field of continuum percolation theory. Given that node locations in wireless networks are not known, random planar modeling can be used to provide preliminary assessments of important quantities such as range, number of neighbors, power consumption, and connectivity, and issues such as spatial reuse and capacity. In this paper, the problem of connectivity based on nearest neighbors is addressed. The exact threshold function for /spl theta/-coverage is found for wireless networks modeled as n points uniformly distributed in a unit square, with every node connecting to its /spl phi//sub n/ nearest neighbors. A network is called /spl theta/-covered if every node, except those near the boundary, can find one of its /spl phi//sub n/ nearest neighbors in any sector of angle /spl theta/. For all /spl theta//spl isin/(0,2/spl pi/), if /spl phi//sub n/=(1+/spl delta/)log/sub 2/spl pi//2/spl pi/-/spl theta//n, it is shown that the probability of /spl theta/-coverage goes to one as n goes to infinity, for any /spl delta/>0; on the other hand, if /spl phi//sub n/=(1-/spl delta/)log/sub 2/spl pi//2/spl pi/-/spl theta//n, the probability of /spl theta/-coverage goes to zero. This sharp characterization of /spl theta/-coverage is used to show, via further geometric arguments, that the network will be connected with probability approaching one if /spl phi//sub n/=(1+/spl delta/)log/sub 2/n. Connections between these results and the performance analysis of wireless networks, especially for routing and topology control algorithms, are discussed.

The functional lifetime of a sensor network is defined as the maximum number of times a certain data collection function or task can be carried out without any node running out of energy. The specific task considered in this paper is that of communicating a specified quantity of information from each sensor to a collector node. The problem of finding the communication scheme which maximizes functional lifetime can be formulated as a linear program, under "fluid-like" assumptions on information bits. This paper focuses on analytically solving the linear program for some simple regular network topologies. The two topologies considered are a regular linear array, and a regular two-dimensional network. In the linear case, an upper bound on functional lifetime is derived, as a function of the initial energies and quantities of data held by the sensors. Under some assumptions on the relative amounts of the energies and data, this upper bound is shown to be achievable, and the exact form of the optimal communication strategy is derived. For the regular planar network, upper and lower bounds on functional lifetime, differing only by a constant factor, are obtained. Finally, it is shown that the simple collection scheme of transmitting only to nearest neighbors, yields a nearly optimal lifetime in a scaling sense.

One of the triumphs of wireline network research of the last decade has been the casting of the Internet congestion control problem within an optimization framework based on utility functions. Such an approach provides a sound understanding of the underlying stability and fairness issues, as well as a post-facto justification of TCP-like additiveincrease multiplicative-decrease (AIMD) algorithms. This paper provides a counter-example showing that the same result cannot be extended to wireless networks, at least not in a straightforward manner. The fundamental difference is that wireless networks are of a broadcast nature. There is no strict notion of a “link,” since transmissions from nearby nodes interfere with each other. Using a simple model of interference in wireless networks, a counter-example of a wireless network is presented in which the congestion control mechanism has an unstable equilibrium point at the desired fair solution. Further, ns-2 simulations of this counter-example manifest an oscillatory behavior. Surprisingly, this oscillatory behavior appears to be fairly typical in wireless networks, with most randomly chosen network examples manifesting it. This loss of stability suggests a possible need for the re-design of wireless TCP and wireless queue management to explicitly account for the wireless nature of the effects of interference.

In wireless sensor networks, one is not interested in downloading all the data from all the sensors. Rather, one is only interested in collecting from a sink node a relevant function of the sensor measurements. This paper studies the maximum rate at which functions of sensor measurements can be computed and communicated to the sink node. It focuses on symmetric functions, where only the data from a sensor is important, not its identity. The results include the following. The maximum rate of downloading the frequency histogram in a random planar multihop network with n nodes is O(1/logn) A subclass of functions, called type-sensitive functions, is maximally difficult to compute. In a collocated network, they can be computed at rate O(1/n), and in a random planar multihop network at rate O(1/logn). This class includes the mean, mode, median, etc. Another subclass of functions, called type-threshold functions, is exponentially easier to compute. In a collocated network they can be computed at rate O(1/logn), and in a random planar multihop network at rate O(1/loglogn). This class includes the max, min, range, etc. The results also show the architecture for processing information across sensor networks.

Transmit power control is a prototypical example of a cross-layer design problem. The transmit power level affects signal quality and, thus, impacts the physical layer, determines the neighboring nodes that can hear the packet and, thus, the network layer affects interference which causes congestion and, thus, affects the transport layer. It is also key to several performance measures such as throughput, delay, and energy consumption. The challenge is to determine where in the architecture the power control problem is to be situated, to determine the appropriate power level by studying its impact on several performance issues, to provide a solution which deals properly with the multiple effects of transmit power control, and finally, to provide a software architecture for realizing the solution. We distill some basic principles on power control, which inform the subsequent design process. We then detail the design of a sequence of increasingly complex protocols, which address the multidimensional ramifications of the power control problem. Many of these protocols have been implemented, and may be the only implementations for power control in a real system. It is hoped that the approach in this paper may also be of use in other topical problems in cross-layer design.

For the multiple-level relay channel, an achievable rate formula, and a simple coding scheme to achieve it, are presented. Generally, higher rates can be achieved with this coding scheme in the multiple-level relay case than previously known. For a class of degraded channels, this achievable rate is shown to be the exact capacity. An application of the coding scheme to the allcast problem is also discussed.

We consider networks consisting of nodes with radios, and without any wired infrastructure, thus necessitating all communication to take place only over the shared wireless medium. The main focus of this paper is on the effect of fading in such wireless networks. We examine the attenuation regime where either the medium is absorptive, a situation which generally prevails, or the path loss exponent is greater than 3. We study the transport capacity, defined as the supremum over the set of feasible rate vectors of the distance weighted sum of rates. We consider two assumption sets. Under the first assumption set, which essentially requires only a mild time average type of bound on the fading process, we show that the transport capacity can grow no faster than O(n), where n denotes the number of nodes, even when the channel state information (CSI) is available noncausally at both the transmitters and the receivers. This assumption includes common models of stationary ergodic channels; constant, frequency-selective channels; flat, rapidly varying channels; and flat slowly varying channels. In the second assumption set, which essentially features an independence, time average of expectation, and nonzeroness condition on the fading process, we constructively show how to achieve transport capacity of /spl Omega/(n) even when the CSI is unknown to both the transmitters and the receivers, provided that every node has an appropriately nearby node. This assumption set includes common models of independent and identically distributed (i.i.d.) channels; constant, flat channels; and constant, frequency-selective channels. The transport capacity is achieved by nodes communicating only with neighbors, and using only point-to-point coding. The thrust of these results is that the multihop strategy, toward which much protocol development activity is currently targeted, is appropriate for fading environments. The low attenuation regime is open.

This paper presents the computing and communicating statistics in sensor networks. A deterministic sequence of message passing between sensors, result in the vector of function values being, communicated to the fusion center, for any combination of individual measurement vectors. A wireless communication model using protocols is also discussed.

This paper proposes a new coding scheme and proved a new achievable rate formula for the Gaussian case. The scheme is simpler and avoids some inconvenient techniques (e.g., the Slepian-Wolf partitioning), in giving the same achievable rate for the single relay case. More importantly, this new coding scheme is easier to extend to the multiple level relay case, and generally achieves higher rates. Here we present the results for the discrete memoryless case. The paper also goes on to obtain the capacity of some relay channels under fading, which is the first significant capacity result for such channels, and one, which may possibly constitute a breakthrough in the field.

We study the transport capacity of wireless networks with fading, in the high attenuation regime where either the medium is absorptive or the path loss exponent is greater than 3. For a network of n nodes we show that even were the states of all channels to be noncausally known a-priori, the transport capacity is no more than O(n). On the other hand, even when the channels are frequency selective and independent from time to time, G(n) is achievable through a multihop strategy

The promise of middleware is to enable integration and evolution of complex systems dynamically. In demanding domains such as wireless control networks, fulfilling this promise while maintaining complete generality is extremely complicated. Understanding and exploiting the forcing functions of a domain helps manage this complexity by avoiding redundant generalizations. Domainware exploits this technique and adopts a simpler architecture to support more important nonfunctional requirements effectively. This paper presents Etherware, a domainware for wireless control networks. Capitalizing on our development of a fairly complex control system testbed, commonly supported yet redundant generalizations are identified and eliminated. The resulting architecture is simple, and can support a wide range of trade-offs that can be manipulated easily at run-time. This is illustrated by showing how the performance of control time protocol (CTP), an Etherware service, is optimized by the additional options available in Etherware

In recent years there has been much interest in mobile ad hoc wireless networks. More recently, there has been great interest in mesh networks which are essentially stationary ad hoc networks. Also the focus of much recent interest are wireless sensor networks that are formed by nodes with environmental sensing capability as well as computational and wireless communication capability. Since actuation closely follows sensing we anticipate that a next phase of the information technology revolution could be the convergence of control, i.e., sensing and actuation, with communication and computation. We give a brief account of some issues of interest in each of these areas.

Solving complex source inference and estimation problems in the distributed environment of sensor networks is a difficult task. Data is distributed, as is computational power, and energy is limited. We consider the problem of detecting and locating a heat source appearing in a region monitored by a sensor network. This task requires complex computations that must be shared by all sensors. One significant difficulty we overcome is the problem of local minima. By using a two step procedure, where in the first step the nodes estimate their distances to the source, and in the second step we localize it and avoid the problem of having erroneous location estimates of the local minima. Furthermore, to organize the computations involved, we draw on ideas from graphical models. We develop an algorithm that has a property which we call "increasing correctness" that at any time the algorithm can be stopped and it nevertheless provides the correct answer for the problem defined by the information that has been fed into the algorithm up to that time.

How much information can be carried over a wireless network with a multiplicity of nodes, and how should the nodes cooperate to transfer information? To study these questions, we formulate a model of wireless networks that particularly takes into account the distances between nodes, and the resulting attenuation of radio signals, and study a performance measure that weights information by the distance over which it is transported. Consider a network with the following features. I) n nodes located on a plane, with minimum separation distance /spl rho//sub min/>0. II) A simplistic model of signal attenuation e/sup -/spl gamma//spl rho////spl rho//sup /spl delta// over a distance /spl rho/, where /spl gamma//spl ges/0 is the absorption constant (usually positive, unless over a vacuum), and /spl delta/>0 is the path loss exponent. III) All receptions subject to additive Gaussian noise of variance /spl sigma//sup 2/. The performance measure we mainly, but not exclusively, study is the transport capacity C/sub T/:=sup/spl Sigma/on/sub /spl lscr/=1//sup m/R/sub /spl lscr///spl middot//spl rho//sub /spl lscr//, where the supremum is taken over m, and vectors (R/sub 1/,R/sub 2/,...,R/sub m/) of feasible rates for m source-destination pairs, and /spl rho//sub /spl lscr// is the distance between the /spl lscr/th source and its destination. It is the supremum distance-weighted sum of rates that the wireless network can deliver. We show that there is a dichotomy between the cases of relatively high and relatively low attenuation. When /spl gamma/>0 or /spl delta/>3, the relatively high attenuation case, the transport capacity is bounded by a constant multiple of the sum of the transmit powers of the nodes in the network. However, when /spl gamma/=0 and /spl delta/<3/2, the low-attenuation case, we show that there exist networks that can provide unbounded transport capacity for fixed total power, yielding zero energy priced communication. Examples show that nodes can profitably cooperate over large distances using coherence and multiuser estimation when the attenuation is low. These results are established by developing a coding scheme and an achievable rate for Gaussian multiple-relay channels, a result that may be of interest in its own right.

Abstract We obtain improved upper and lower bounds on the best case and random case transport capacities of wireless networks under the Protocol Model of communication in Reference [ 1 ]. These results bracket the best case transport capacity to within a factor of $\sqrt8$ for wireless networks on a disk. This is done by identifying larger exclusion regions for receivers. The general result on exclusion regions can also be applied to arbitrary wireless footprints, including those arising from directional antennas, thus obtaining superior bounds for such technologies too. Copyright © 2004 John Wiley & Sons, Ltd.

In this paper, we consider the problem of power control when nodes are nonhomogeneously dispersed in space. In such situations, one seeks to employ per packet power control depending on the source and destination of the packet. This gives rise to a joint problem which involves not only power control but also clustering. We provide three solutions for joint clustering and power control. The first protocol, CLUSTERPOW, aims to increase the network capacity by increasing spatial reuse. We provide a simple and modular architecture to implement CLUSTERPOW at the network layer. The second, Tunnelled CLUSTERPOW, allows a finer optimization by using encapsulation, but we do not know of an efficient way to implement it. The last, MINPOW, whose basic idea is not new, provides an optimal routing solution with respect to the total power consumed in communication. Our contribution includes a clean implementation of MINPOW at the network layer without any physical layer support. We establish that all three protocols ensure that packets ultimately reach their intended destinations. We provide a software architectural framework for our implementation as a network layer protocol. The architecture works with any routing protocol, and can also be used to implement other power control schemes. Details of the implementation in Linux are provided.

We study communication networks of arbitrary size and topology and communicating over a general vector discrete memoryless channel (DMC). We propose an information-theoretic constructive scheme for obtaining an achievable rate region in such networks. Many well-known capacity-defining achievable rate regions can be derived as special cases of the proposed scheme. A few such examples are the physically degraded and reversely degraded relay channels, the Gaussian multiple-access channel, and the Gaussian broadcast channel. The proposed scheme also leads to inner bounds for the multicast and allcast capacities. Applying the proposed scheme to a specific wireless network of n nodes located in a region of unit area, we show that a transport capacity of /spl Theta/(n) bit-meters per second (bit-meters/s) is feasible in a certain family of networks, as compared to the best possible transport capacity of /spl Theta/(/spl radic/n) bit-meters/s in Gupta et al. (2000), where the receiver capabilities were limited. Even though the improvement is shown for a specific class of networks, a clear implication is that designing and employing more sophisticated multiuser coding schemes can provide sizable gains in at least some large wireless networks.

For original paper see "The capacity of wireless networks", Gupta and Kumar, ibid., vol. 46, p. 388-404 (2000). The proof of lemma 4.8 is corrected.

We present a network information theory for wireless communications. This theory addresses the following issues: (i) How the amount of information that can be carried over a wireless network scales as the number n of nodes in the network increases. (ii) Obtains bounds on the pre-constant in the scaling law, thus obtaining bounds on network capability as a function of n, the number of nodes in the network. (iii) What, strategies for operating the wireless network give optimal performance up to order.

Motivated by the poor experimental scaling reported in a study of the performance of ad hoc networks in [15], we propose a new protocol for media access control in ad hoc networks. Our protocol seeks to avoid collisions without making explicit reservations for each and every packet. The key idea is to employ a random schedule which is driven by a pseudo-random number generator. By exchangine the seeds of their pseudo-random number generators within two-hop neighborhood, the nodes effectively publish their schedules to all hidden as well as exposed nodes. This allows each node to opportunistically choose transmission slots. This scheme can also be employed during the reservation phase of a protocol such as IEEE 802.11. Throughput calculations and simulation results are presented

We provide an introduction to the application of queueing network models to the design and analysis of semiconductor wafer fabs. We introduce the basic issues that confront the system manager and discuss a variety of queueing network based tools for addressing these issues. A representative collection of existing results in this area is also briefly surveyed.

When n identical randomly located nodes, each capable of transmitting at W bits per second and using a fixed range, form a wireless network, the throughput /spl lambda/(n) obtainable by each node for a randomly chosen destination is /spl Theta/(W//spl radic/(nlogn)) bits per second under a noninterference protocol. If the nodes are optimally placed in a disk of unit area, traffic patterns are optimally assigned, and each transmission's range is optimally chosen, the bit-distance product that can be transported by the network per second is /spl Theta/(W/spl radic/An) bit-meters per second. Thus even under optimal circumstances, the throughput is only /spl Theta/(W//spl radic/n) bits per second for each node for a destination nonvanishingly far away. Similar results also hold under an alternate physical model where a required signal-to-interference ratio is specified for successful receptions. Fundamentally, it is the need for every node all over the domain to share whatever portion of the channel it is utilizing with nodes in its local neighborhood that is the reason for the constriction in capacity. Splitting the channel into several subchannels does not change any of the results. Some implications may be worth considering by designers. Since the throughput furnished to each user diminishes to zero as the number of users is increased, perhaps networks connecting smaller numbers of users, or featuring connections mostly with nearby neighbors, may be more likely to be find acceptance.

In the 1970's, Baskett, Chandy, Muntz and Palacios, Kelly, and others, generalized the earlier results of Jackson (1957) and obtained explicit solutions for the steady-state distributions of some restricted queueing networks. These queueing networks are called "product-form networks," due to the structure of their explicit solutions. The class of such tractable networks is quite small, however. For example, if customers require different mean service times on different revisits to the same server, or if customers on a later visit are given higher priority, then very little is known concerning whether the network is even stable or what form the steady-state distribution has if it exists. Recently, some new methods have been developed for establishing the stability of a system and for obtaining bounds on key performance measures such as mean delay, mean number in system, or mean throughput. Since they are based on the well-developed computational tool of linear programming, these methods can be widely employed in diverse applications in communication networks, computer systems, and manufacturing systems. We provide a tutorial exposition of some of these recent developments.>

We consider a manufacturing system producing several part-types on several machines. Raw parts are input to the system. Each unit of a given part-type requires a predetermined processing time at each of several machines, in a given order. A setup time is required whenever a machine switches from processing one part-type to another. For a single machine system with constant demand rates, we present a class of generalized round-robin scheduling policies for which the buffer level trajectory of each part-type converges to a steady state level. Furthermore, for all small initial conditions, we show that these policies can be Pareto-efficient with respect to the buffer sizes required. Allowing the input streams to have some burstiness, we derive upper bounds on the buffer levels for small initial conditions. For non-acyclic systems, we consider a class of policies which are stable for all inputs with bounded burstiness. We show how to employ system elements, called regulators, to stabilize systems. Using the bounds for the single machine case, we analyze the performance of regulated systems implementing generalized round-robin scheduling policies.< >

To learn, it suffices to estimate the error of all candidate hypotheses simultaneously. We study the problem of when this “simultaneous estimation” is possible and show that it leads to new learning procedures and weaker sufficient conditions for a broad class of learning problems. We modify the standard Probably Approximately Correct (PAC) setup to allow concepts that are “stochastic functions.” A deterministic function maps a set X into a set Y, whereas a stochastic function is a probability distribution on X x Y. We approach the simultaenous estimation problem by concentrating on a subset of all estimators, those that satisfy a natural “smoothness” constraint. The common empirical estimator falls within this class. We show that smooth simultaneous estimability can be characterized by a sampling-based criterion. Also, we describe a canonical estimator for this class of problems. This canonical estimator has a unique form: it uses part of the samples to select a finite subset of hypotheses that approximates the class of candidate hypotheses, and then it uses the rest of the samples to estimate the error of each hypothesis in the subset. Finally, we show that a learning procedure based on the canonical estimator will work in every case where empirical error minimization does.

In this paper four approaches to the calculation of error rates for optical fiber system repeaters are compared ("Exact" calculation, Monte Carlo simulation, Chernoff bounds and the Gaussian approximation). We conclude that the "Exact" and Monte Carlo calculations are in complete agreement. This allows the Monte Carlo results to be used to calibrate other methods. The relatively simple Chernoff bound is in very good agreement with the above, and should be used whenever computational facilities allow. For simpler calculations, or analytical expressions for the effects of parameter variations, the Guassian approximation gives a reasonable good estimate of the receiver sensitivity. However, it tends to underestimate the threshold setting and overestimate the optimal avalanche gain.