Targeted and deliberate exploration of state--action pairs is essential in reward-free Markov Decision Problems (MDPs). More precisely, different state-action pairs exhibit different degree of importance or difficulty which must be actively and explicitly built into a controlled exploration strategy. To this end, we propose a weighted and parameterized family of concave coverage objectives, denoted by $U_ρ$, defined directly over state--action occupancy measures. This family unifies several widely studied objectives within a single framework, including divergence-based marginal matching, weighted average coverage, and worst-case (minimax) coverage. While the concavity of $U_ρ$ captures the diminishing return associated with over-exploration, the simple closed form of the gradient of $U_ρ$ enables an explicit control to prioritize under-explored state--action pairs. Leveraging this structure, we develop a gradient-based algorithm that actively steers the induced occupancy toward a desired coverage pattern. Moreover, we show that as $ρ$ increases, the resulting exploration strategy increasingly emphasizes the least-explored state--action pairs, recovering worst-case coverage behavior in the limit.

We consider an active one-sided hypothesis test for Markov chains in which an investigator actively samples from a given stochastic process to efficiently collect evidence against the (null) hypothesis that the process is generated by a given known Markov chain with a given transition matrix and, in effect, accept an alternative (composite) hypothesis. This problem has practical relevance to a large class of problems in anomaly detection and diagnostics where obtaining the full state of the chain is costly and there is a one-sided asymmetric need for explicit rejection of the the null hypothesis versus accepting it. We note that by strategically choosing when to sample, the investigator can allow the chain to evolve until it is likely in a state which effectively discriminates against the null hypothesis. Using this intuition, along with recent work on one-sided testing for Markov chains, we obtain a data-driven strategy test that ensures bounded type-1 error and improved sample efficiency. Our experimental section provides numerical evidence that our algorithm provides significant advantage over passive testing.

We revisit the classical problem of estimating an unknown distribution from its samples by fitting a mixture model that minimizes cross-entropy loss. Framing the task as a stochastic convex optimization problem over the space of M-component mixture distributions, we propose a family of estimators derived from the stochastic mirror descent (SMD) algorithm. This optimization-based approach provides a principled and flexible framework that generalizes traditional estimators and accommodates a variety of geometries through the choice of Bregman divergences.A key advantage of our method is that it scales efficiently with the number of candidate components fi; that is, one can employ a large set of basis distributions in the mixture model without incurring significant computational overhead. This enables richer approximations and improved estimation accuracy.Moreover, unlike methods that require strict lower bounds on mixture weights (i.e., restricting to the simplex to a denser version where each component is at least δ >0), our framework operates over the full probability simplex ΔM. This allows the estimator to naturally suppress irrelevant components, yielding sparser solutions when appropriate without hard-thresholding.We demonstrate that, under mild conditions, the proposed φ-SMD estimators achieve near-optimal convergence rates in both Kullback–Leibler (KL) divergence and ℓ2-norm, offering practical benefits particularly in high-dimensional or computationally constrained scenarios. Our analysis highlights improved performance guarantees over classical estimators, particularly in terms of sample efficiency, scalability, and dimensional dependence.

Consider an $n$-dimensional binary feature vector with $k$ non-zero entries. The vector can be interpreted as the incident vector corresponding to $n$ items out of which $k$ items are \emph{defective}. The \emph{quantitative group testing} (QGT) problem aims at learning this binary feature vector by queries on subsets of the items that return the total number of defective items. We consider this problem under the \emph{non-adaptive} scenario where the queries on subsets are designed collectively and can be executed in parallel. Most of the existing efficient non-adaptive algorithms for the sublinear regime where $k = n^\alpha$ with $0 < \alpha < 1$ fall short of the information-theoretic lower bound, with a multiplicative gap of $\log k$. Recently, a near-optimal non-adaptive algorithm with a decoding complexity of $O(n^3)$ closed this gap. In this work, we present a concatenated construction method yielding a non-adaptive algorithm with a decoding complexity of $O(n^{2\alpha} + n \log^2 n)$. The probability of decoding failure is analyzed by establishing a connection between the QGT problem and the so-called \emph{balls into bins} problem. Our algorithm reduces the gap between the information-theoretic and computational bound for the number of required queries/tests from $\log k$ to $\log \log k$. This narrows the gap in the number of tests for non-adaptive algorithms within the class of algorithms with $o(n^2)$ decoding complexity. Moreover, although our algorithm exhibits a $\log \log k$ gap in terms of the number of tests, it is surpassed by the existing asymptotically optimal construction only in scenarios where $k$ is exceptionally large for moderate values of $\alpha$, such as $k > 10^{27}$ for $\alpha = 0.7$, thereby highlighting the practical applicability of our proposed concatenated construction.

The aim of quantitative group testing problem is to recover$k$defective items from a set of$n$items using minimal number of quantitative/additive group tests, where each test reveals the number of defective items present in the group. Fully adaptive strategies have been proposed and shown to, in general, require significantly fewer measurements. In the sublinear regime, where$k=n^{\alpha}$for$0 < \alpha < 1$, for instance, this means a gain proportional to$\alpha \log n$. However, this gain is obtained at the cost of significant complexity associated with adapting tests to previous outcomes. This paper introduces a family of low-complexity strategies with efficient construction and decoding. These strategies adapt tests only in stages, allowing for a flexible trade-off between the number of stages, i.e., the complexity cost of adaptation, and the overall number of tests i.e., the adaptivity gain. Specifically, our algorithm matches the state-of-the-art adaptive algorithm in terms of the number of measurements while reducing the required number of stages by a multiplicative factor of$1-\alpha$. Our results demonstrates that a small number of stages can lead to substantial improvements over non-adaptive strategies. Furthermore, in comparison to existing non-adaptive algorithms, our algorithm achieves a 47% improvement in the overall number of tests, with the addition of just one stage.

We consider sequential hypothesis testing among multiple samples of one among$M$pure quantum states in an equidistant ensemble, i.e., those with identical pair-wise inner products. Each measurement in the sequence is a binary projective measurement that collapses the sample of the state measured at that instant into a linear span of a collection of states from the ensemble or its orthogonal complement. The algorithm adaptively decides if additional samples are needed or sufficient observation has been gathered. We show that our sequential measurement algorithm outperforms the sequential testing (ST) receiver, whose error-probability exponent is known to achieve the quantum Chernoff bound asymptotically in the limit of large (and fixed) number of samples. Even though our algorithm does not attain the quantum limit of minimum error probability (the Helstrom limit), it paves the way for future research on more advanced sequential quantum hypothesis tests, e.g., those that go beyond binary projective measurements on each sample.

Millimeter-wave (mmWave) with phase array systems are utilized to increase the data rate in wireless communication systems. With the larger phase array, narrower beams can be generated to compensate for the path loss and boost the effective SNR. In order to perform beamforming, however, one must find the Angle of Arrival (AoA). In this paper, we consider the problem of initial beam alignment and CSI acquisition for (sub-)mmWave communication over a single-path channel with a single RF-chain. A three stage adaptive alignment algorithm based on the posterior probability, called Adaptive Phase Matching, is proposed. The algorithm maps the candidate angles of arrivals onto a simple constellation on the complex plane adaptively. The proposed scheme generalizes HiePM to both account for practically feasible antenna patterns as well as utilize the phase information. Furthermore, an upper bound of the expected search time for any given alignment resolution and error probability is derived.

Understanding complex dynamics of two-sided online matching markets, where the demand-side agents compete to match with the supply-side (arms), has recently received substantial interest. To that end, in this paper, we introduce the framework of decentralized two-sided matching market under non stationary (dynamic) environments. We adhere to the serial dictatorship setting, where the demand-side agents have unknown and different preferences over the supply-side (arms), but the arms have fixed and known preference over the agents. We propose and analyze an asynchronous and decentralized learning algorithm, namely Non-Stationary Competing Bandits (NSCB), where the agents play (restrictive) successive elimination type learning algorithms to learn their preference over the arms. The complexity in understanding such a system stems from the fact that the competing bandits choose their actions in an asynchronous fashion, and the lower ranked agents only get to learn from a set of arms, not dominated by the higher ranked agents, which leads toforced exploration. With carefully defined complexity parameters, we characterize thisforced explorationand obtain sub-linear (logarithmic) regret of NSCB. Furthermore, we validate our theoretical findings via experiments.

We consider sequential hypothesis tests for Markov chains in which the investigator may adaptively abstain from sampling on each time step in exchange for a reduced sampling cost. This allows the investigator to strategically choose to allow the chain to evolve until it is likely in a state which discriminates well among the hypotheses–when it becomes worth paying the full sampling cost. We first explore the reduction of this problem formulation to several standard hypothesis testing scenarios via an appropriate choice of parameters. Then we derive a dynamic programming characterization of the optimal algorithm in this setting and solve it numerically for several model problems that exhibit the rich, interesting behavior that arise from this modification of the hypothesis testing problem.

In this paper, we study the quantitative group testing problem, also known as the heavy hitter detection problem and the coin weighing problem, in a non-adaptive setting. In this problem, the aim is to recover k defective items from a group of n items with the smallest possible number of quantitative/additive tests, where each such test returns the number of defective items participating in the test. In the non-adaptive setting, that we study in this paper, all tests are designed at once and can be, in principle, run in parallel. We establish a novel construction method for designing non-adaptive test matrices with a nested structure inspired by the Plotkin concatenation in the coding theory literature. Our proposed algorithm identifies k defective items among the collection of n items with high probability using $k(1 + o(1))\log \left( {\frac{n}{k}} \right)$ non-adaptive tests in the sub-linear regime of k = o(n). Furthermore, our analysis demonstrates that the probability of decoding failure approaches zero exponentially in k as k, n → ∞. Our approach outperforms existing state-of-the-art methods for designing non-adaptive test schemes with efficient decoders for the quantitative group testing problem in terms of the required number of measurements.

We study the problem of designing an adaptive strategy for querying a noisy zeroth-order-oracle to efficiently learn about the optimizer of an unknown function $f$. To make the problem tractable, we assume that $f$ lies in the reproducing kernel Hilbert space (RKHS) associated with a known kernel $K$, with its norm bounded by $M<\infty$. Prior results, working in a minimax framework, have characterized the worst-case (over all functions in the problem class) limits on regret achievable by any algorithm, and have constructed algorithms with matching (modulo polylogarithmic factors) worst-case performance for the Matern family of kernels. These results suffer from two drawbacks. First, the minimax lower bound gives limited information about the limits of regret achievable by commonly used algorithms on a specific problem instance $f$. Second, the existing upper bound analysis fails to adapt to easier problem instances within the function class. Our work takes steps to address both these issues. First, we derive instance-dependent regret lower bounds for algorithms with uniformly (over the function class) vanishing normalized cumulative regret. Our result, valid for several practically relevant kernelized bandits algorithms, such as, GP-UCB, GP-TS and SupKernelUCB, identifies a fundamental complexity measure associated with every problem instance. We then address the second issue, by proposing a new minimax near-optimal algorithm that also adapts to easier problem instances.

Consider the problem of optimizing a black-box function under the assumption that the function is Holder smooth and has bounded norm in the reproducing kernel Hilbert space associated with a given kernel. We propose the LP-GP-UCB algorithm which augments a Gaussian process surrogate model with local polynomial estimators of the function to construct a multi-scale upper confidence bound to guide the search for the optimizer. We provide high probability bounds on the cumulative regret in terms of the maximum information gain and smoothness parameters for the kernel. We then show that the Holder smoothness assumption is satisfied for several commonly used and practically relevant kernels—the Matern, rational- quadratic, γ-exponential, and piecewise-polynomial kernels—and obtain explicit regret bounds for them as a result. These regret bounds establish the near-optimality of LP-GP-UCB for these kernels and are also the first explicit bounds for many of them. Finally, we demonstrate the practical benefits experimentally.

We consider the problem of Bayesian Optimization (BO) in which the goal is to design an adaptive querying strategy to optimize a function $f:[0,1]^d\mapsto \reals$. The function is assumed to be drawn from a Gaussian Process, and can only be accessed through noisy oracle queries. The most commonly used oracle in BO literature is the noisy Zeroth-Order-Oracle (ZOO) which returns noise-corrupted function value $y = f(x) + \eta$ at any point $x \in \domain$ queried by the agent. A less studied oracle in BO is the First-Order-Oracle (FOO) which also returns noisy gradient value at the queried point. In this paper we consider the fundamental question of quantifying the possible improvement in regret that can be achieved under FOO access as compared to the case in which only ZOO access is available. Under some regularity assumptions on $K$, we first show that the expected cumulative regret with ZOO of any algorithm must satisfy a lower bound of $\Omega(\sqrt{2^d n})$, where $n$ is the query budget. This lower bound captures the appropriate scaling of the regret on both dimension $d$ and budget $n$, and relies on a novel reduction from BO to a multi-armed bandit (MAB) problem. We then propose a two-phase algorithm which, with some additional prior knowledge, achieves a vastly improved $\mc{O}\lp d (\log n)^2 \rp$ regret when given access to a FOO. Together, these two results highlight the significant value of incorporating gradient information in BO algorithms.

Confidence intervals are a crucial building block in the analysis of various online learning problems. The analysis of kernel-based bandit and reinforcement learning problems utilize confidence intervals applicable to the elements of a reproducing kernel Hilbert space (RKHS). However, the existing confidence bounds do not appear to be tight, resulting in suboptimal regret bounds. In fact, the existing regret bounds for several kernelized bandit algorithms (e.g., GP-UCB, GP-TS, and their variants) may fail to even be sublinear. It is unclear whether the suboptimal regret bound is a fundamental shortcoming of these algorithms or an artifact of the proof, and the main challenge seems to stem from the online (sequential) nature of the observation points. We formalize the question of online confidence intervals in the RKHS setting and overview the existing results.

In mmWave communications, higher data rate long-range transmission is achieved by using highly directional beams with access to larger bandwidth. An inherent challenge is tracking channel state information (CSI) necessary for mmWave transmission under systems with unpredictable mobility. We propose a novel method of active and sequential beam tracking at mmWave frequencies and above. We focus on the dynamic scenario of UAV to UAV communications where the problem is equivalent to tracking an optimal beamforming vector along the line-of-sight path. In this setting, the resulting receiver beam ideally points in the direction of the angle of arrival with sufficiently high resolution. Existing solutions account for predictable movements or small random movements using known filtering strategies but resort to re-estimation protocols when tracking fails due to unpredictable movements. We propose an algorithm for actively and sequentially selecting beamforming vectors based on a Bayesian posterior with a prediction step to account for the mobility. Numerically, we analyze the normalized beamforming gain achieved by our proposed algorithm and demonstrate significant improvements over existing strategies.

Machine learning models trained on uncurated datasets can often end up adversely affecting inputs belonging to underrepresented groups. To address this issue, we consider the problem of adaptively constructing training sets which allow us to learn classifiers that are fair in a {\em minimax} sense. We first propose an adaptive sampling algorithm based on the principle of \emph{optimism}, and derive theoretical bounds on its performance. We also propose heuristic extensions of this algorithm suitable for application to large scale, practical problems. Next, by deriving algorithm independent lower-bounds for a specific class of problems, we show that the performance achieved by our adaptive scheme cannot be improved in general. We then validate the benefits of adaptively constructing training sets via experiments on synthetic tasks with logistic regression classifiers, as well as on several real-world tasks using convolutional neural networks (CNNs).

Recent advances in adversarial Deep Learning (DL) have opened up a new and largely unexplored surface for malicious attacks jeopardizing the integrity of autonomous DL systems. This article introduces CuRTAIL, a novel end-to-end computing framework to characterize and thwart potential adversarial attacks and significantly improve the reliability (safety) of a victim DL model. We formalize the goal of preventing adversarial attacks as an optimization problem to minimize the rarely observed regions in the latent feature space spanned by a DL network. To solve the aforementioned minimization problem, a set of complementary but disjoint modular redundancies are trained to validate the legitimacy of the input samples. The proposed countermeasure is unsupervised, meaning that no adversarial sample is leveraged to train modular redundancies. This, in turn, ensures the effectiveness of the defense in the face of generic attacks. We evaluate the robustness of our proposed methodology against the state-of-the-art adaptive attacks in a white-box setting considering that the adversary knows everything about the victim model and its defenders. Extensive evaluations for analyzing MNIST, CIFAR10, and ImageNet data corroborate the effectiveness of CuRTAIL framework against adversarial samples. The computations in each modular redundancy can be performed independently of the other redundancy modules. As such, CuRTAIL detection algorithm can be completely parallelized among multiple hardware settings to achieve maximum throughput. We further provide an open-source Application Programming Interface (API) to facilitate the adoption of the proposed framework for various applications.

This paper considers a target localization problem where at any given time an agent can choose a region to query for the presence of the target in that region. The measurement noise is assumed to be increasing with the size of the query region the agent chooses. Motivated by practical applications such as initial beam alignment in array processing, heavy hitter detection in networking, and visual search in robotics, we consider practically important complexity constraints/metrics: time complexity, computational and memory complexity, and the complexity of possible query sets in terms of geometry and cardinality. Two novel search strategy, dyaPM and hiePM, are proposed. Pertinent to the practicality of our solutions, dyaPM and hiePM are of a connected query geometry (i.e. query set is always a connected set) implemented with low computational and memory complexity. Additionally, hiePM has a hierarchical structure and, hence, a further reduction in the cardinality of possible query sets, making hiePM practically suitable for applications such as beamforming in array processing where memory limitations favors a small and predefined query sets. Through a unified analysis with Extrinsic Jensen Shannon (EJS) Divergence, dyaPM is shown to be asymptotically optimal in search time complexity (asymptotic in both resolution (rate) and error (reliability)). On the other hand, hiePM is shown to be near-optimal in rate. In addition, both hiePM and dyaPM are shown to outperform prior work in the non-asymptotic regime.

In the contemporary big data realm, Deep Neural Networks (DNNs) are evolving towards more complex architectures to achieve higher inference accuracy. Model compression techniques can be leveraged to efficiently deploy these compute-intensive architectures on resource-limited mobile devices. Such methods comprise various hyperparameters that require per-layer customization to ensure high accuracy. Choosing the hyperparameters is cumbersome as the pertinent search space grows exponentially with model layers. This paper introduces GeneCAI, a novel optimization method that automatically learns how to tune per-layer compression hyperparameters. We devise a bijective translation scheme that encodes compressed DNNs to the genotype space. Each genotype's optimality is measured using a multi-objective score based on the accuracy and number of floating-point operations. We develop customized genetic operations to iteratively evolve the non-dominated solutions towards the optimal Pareto front, thus, capturing the optimal trade-off between model accuracy and complexity. GeneCAI optimization method is highly scalable and can achieve a near-linear performance boost on distributed multi-GPU platforms. Our extensive evaluations demonstrate that GeneCAI outperforms existing rule-based and reinforcement learning methods in DNN compression by finding models that lie on a better accuracy/complexity Pareto curve.

We propose CleaNN, the first end-to-end framework that enables online mitigation of Trojans for embedded Deep Neural Network (DNN) applications. A Trojan attack works by injecting a backdoor in the DNN while training; during inference, the Trojan can be activated by the specific backdoor trigger. What differentiates CleaNN from the prior work is its lightweight methodology which recovers the ground-truth class of Trojan samples without the need for labeled data, model retraining, or prior assumptions on the trigger or the attack. We leverage dictionary learning and sparse approximation to characterize the statistical behavior of benign data and identify Trojan triggers. CleaNN is devised based on algorithm/hardware co-design and is equipped with specialized hardware to enable efficient real-time execution on resource-constrained embedded platforms. Proof of concept evaluations on CleaNN for the state-of-the-art Neural Trojan attacks on visual benchmarks demonstrate its competitive advantage in terms of attack resiliency and execution overhead.

We consider the problem of allocating a fixed budget of samples to a finite set of discrete distributions to learn them uniformly well (minimizing the maximum error) in terms of four common distance measures: $\ell_2^2$, $\ell_1$, $f$-divergence, and separation distance. To present a unified treatment of these distances, we first propose a general \emph{optimistic tracking algorithm} and analyze its sample allocation performance w.r.t. an oracle. We then instantiate this algorithm for the four distance measures and derive bounds on their regret. We also show that the allocation performance of the proposed algorithm cannot, in general, be improved, by deriving lower-bounds on the expected deviation from the oracle allocation for any adaptive scheme. We verify our theoretical findings through some experiments. Finally, we show that the techniques developed in the paper can be easily extended to learn some classes of continuous distributions as well as to the related setting of minimizing the average error (in terms of the four distances) in learning a set of distributions.

Consider the problem of recovering an unknown sparse unit vector via a sequence of linear observations with stochastic magnitude and additive noise. An agent sequentially selects measurement vectors and collects observations subject to noise affected by the measurement vector. We propose two algorithms of varying computational complexity for sequentially and adaptively designing measurement vectors. The proposed algorithms aim to augment the learning of the unit common support vector with an estimate of the stochastic coefficient. Numerically, we study the probability of error in estimating the support achieved by our proposed algorithms and demonstrate improvements over random-coding based strategies utilized in prior works.

We consider the problem of binary classification with the caveat that the learner can abstain from declaring a label incurring a cost λ ∈ [0,1/2] in the process. This is referred to as the problem of binary classification with a fixed-cost of abstention. For this problem, we propose an active learning strategy that constructs a non-uniform partition of the input space and focuses sampling in the regions near the decision boundaries. Our proposed algorithm can work in all the commonly used active learning query models, namely membership-query, pool-based and stream-based. We obtain an upper bound on the excess risk of our proposed algorithm under standard smoothness and margin assumptions and demonstrate its minimax near-optimality by deriving a matching (modulo poly-logarithmic factors) lower bound. The achieved minimax rates are always faster than the corresponding rates in the passive setting, and furthermore the improvement increases with larger values of the smoothness and margin parameters.

In this paper, the problem of estimating the level set of a black-box function from noisy and expensive evaluation queries is considered. A new algorithm for this problem in the Bayesian framework with a Gaussian Process (GP) prior is proposed. The proposed algorithm employs a hierarchical sequence of partitions to explore different regions of the search space at varying levels of detail depending upon their proximity to the level set boundary. It is shown that this approach results in the algorithm having a low complexity implementation whose computational cost is significantly smaller than the existing algorithms for higher dimensional search space $\X$. Furthermore, high probability bounds on a measure of discrepancy between the estimated level set and the true level set for the the proposed algorithm are obtained, which are shown to be strictly better than the existing guarantees for a large class of GPs.In the process, a tighter characterization of the information gain of the proposed algorithm is obtained which takes into account the structured nature of the evaluation points. This approach improves upon the existing technique of bounding the information gain with maximum information gain.

Unsupervised learning for geometric perception (depth, optical flow, etc.) is of great interest to autonomous systems. Recent works on unsupervised learning have made considerable progress on perceiving geometry; however, they usually ignore the coherence of objects and perform poorly under scenarios with dark and noisy environments. In contrast, supervised learning algorithms, which are robust, require large labeled geometric dataset. This paper introduces SIGNet, a novel framework that provides robust geometry perception without requiring geometrically informative labels. Specifically, SIGNet integrates semantic information to make depth and flow predictions consistent with objects and robust to low lighting conditions. SIGNet is shown to improve upon the state-of-the-art unsupervised learning for depth prediction by 30% (in squared relative error). In particular, SIGNet improves the dynamic object class performance by 39% in depth prediction and 29% in flow prediction. Our code will be made available at https://github.com/mengyuest/SIGNet

We consider the problem of communications over the binary symmetric channel with feedback, where the information sequence is made available in a causal, possibly random, fashion. We develop a real-time variant of the renowned Horstein scheme and provide analytical guarantees for its error-probability exponential decay rate. We further use the scheme to stabilize an unstable control plant over a binary symmetric channel and compare the analytical guarantees with its empirical performance as well as with those of anytime-reliable codes.

Counterfactual learning from observational data involves learning a classifier on an entire population based on data that is observed conditioned on a selection policy. This work considers this problem in an active setting, where the learner additionally has access to unlabeled examples and can choose to get a subset of these labeled by an oracle. Prior work on this problem uses disagreement-based active learning, along with an importance weighted loss estimator to account for counterfactuals, which leads to a high label complexity. We show how to instead incorporate a more efficient counterfactual risk minimizer into the active learning algorithm. This requires us to modify both the counterfactual risk to make it amenable to active learning, as well as the active learning process to make it amenable to the risk. We provably demonstrate that the result of this is an algorithm which is statistically consistent as well as more label-efficient than prior work.

Millimeter wave (mmWave) communication with large antenna arrays is a promising technique to enable extremely high data rates due to large available bandwidth in mmWave frequency bands. In addition, given the knowledge of an optimal directional beamforming vector, large antenna arrays have been shown to overcome both the severe signal attenuation in mmWave as well as the interference problem. However, fundamental limits on achievable learning rate of an optimal beamforming vector remain. This paper considers the problem of adaptive and sequential optimization of the beamforming vectors during the initial access phase of communication. With a single-path channel model, the problem is reduced to actively learning the Angle-of-Arrival (AoA) of the signal sent from the user to the Base Station (BS). Drawing on the recent results in the design of a hierarchical beamforming codebook, sequential measurement dependent noisy search strategies, and active learning from an imperfect labeler, an adaptive and sequential alignment algorithm is proposed. For any given resolution and error probability of the estimated AoA, an upper bound on the expected search time of the proposed algorithm is derived via Extrinsic Jensen-Shannon Divergence. The upper bound demonstrates that the search time of the proposed algorithm asymptotically matches the performance of the noiseless bisection search up to a constant factor, in effect, characterizing the AoA acquisition rate. Furthermore, the upper bound shows that the acquired AoA error probability decays exponentially fast with the search time with an exponent that is a decreasing function of the acquisition rate. Numerically, the proposed algorithm is compared with prior work where a significant improvement of the system communication rate is observed. Most notably, in the relevant regime of low (−10 dB to +5 dB) raw SNR, this establishes the first practically viable solution for initial access and, hence, the first demonstration of stand-alone mmWave communication.

Network virtualization and programmability allow operators to deploy a wide range of services over a common physical infrastructure and elastically allocate cloud and network resources according to changing requirements. While the elastic reconfiguration of virtual resources enables dynamically scaling capacity in order to support service demands with minimal operational cost, reconfiguration operations make resources unavailable during a given time period and may incur additional cost. In this paper, we address the dynamic cloud network control problem under non-negligible reconfiguration delay and cost. We show that while the capacity region remains unchanged regardless of the reconfiguration delay/cost values, a reconfiguration-agnostic policy may fail to guarantee throughput-optimality and minimum cost under nonzero reconfiguration delay/cost. We then present an adaptive dynamic cloud network control policy that allows network nodes to make local flow scheduling and resource allocation decisions while controlling the frequency of reconfiguration in order to support any input rate in the capacity region and achieve arbitrarily close to minimum cost for any finite reconfiguration delay/cost values.

This paper considers centralized routing over a network in which the cost of each edge is modeled as a random variable and the objective is to route the packets in a manner that minimizes the expected cost while constraining the variance of the cost to a pre- determined upper bound. This problem arises in the context of flow-based routing for wireless Software-Defined Networks (SDN). A Randomized Dijkstra-based Algorithm (RDBR) with a Lagrangian Relaxation Cost is proposed in which two distinct shortest paths are utilized randomly with an optimized randomization factor. Here the notion of shortest path identified by Dijkstra's algorithm refers to the property that these two paths both are of minimum regularized cost as defined by the expected total cost plus weighted variance. We prove the existence and optimality when the weight coincides with the optimal Lagrange multiplier and propose a sub-gradient descent method to compute the optimal multiplier. Numerical comparisons against other previously proposed solutions in the literature illustrate the performance improvements under RDBR at a significantly lower or comparable computational complexity.

Deep Learning (DL) models have been shown to be vulnerable to adversarial attacks. In light of the adversarial attacks, it is critical to reliably quantify the confidence of the prediction in a neural network to enable safe adoption of DL models in autonomous sensitive tasks (e.g., unmanned vehicles and drones). This article discusses recent research advances for unsupervised model assurance against the strongest adversarial attacks known to date and quantitatively compare their performance. Given the widespread usage of DL models, it is imperative to provide model assurance by carefully looking into the feature maps automatically learned within D1 models instead of looking back with regret when deep learning systems are compromised by adversaries.

Recent advances in adversarial Deep Learning (DL) have opened up a largely unexplored surface for malicious attacks jeopardizing the integrity of autonomous DL systems. With the wide-spread usage of DL in critical and time-sensitive applications, including unmanned vehicles, drones, and video surveillance systems, online detection of malicious inputs is of utmost importance. We propose DeepFense, the first end-to-end automated framework that simultaneously enables efficient and safe execution of DL models. DeepFense formalizes the goal of thwarting adversarial attacks as an optimization problem that minimizes the rarely observed regions in the latent feature space spanned by a DL network. To solve the aforementioned minimization problem, a set of complementary but disjoint modular redundancies are trained to validate the legitimacy of the input samples in parallel with the victim DL model. DeepFense leverages hardware/software/algorithm co-design and customized acceleration to achieve just-in-time performance in resource-constrained settings. The proposed countermeasure is unsupervised, meaning that no adversarial sample is leveraged to train modular redundancies. We further provide an accompanying API to reduce the non-recurring engineering cost and ensure automated adaptation to various platforms. Extensive evaluations on FPGAs and GPUs demonstrate up to two orders of magnitude performance improvement while enabling online adversarial sample detection.

We consider active learning with logged data, where labeled examples are drawn conditioned on a predetermined logging policy, and the goal is to learn a classifier on the entire population, not just conditioned on the logging policy. Prior work addresses this problem either when only logged data is available, or purely in a controlled random experimentation setting where the logged data is ignored. In this work, we combine both approaches to provide an algorithm that uses logged data to bootstrap and inform experimentation, thus achieving the best of both worlds. Our work is inspired by a connection between controlled random experimentation and active learning, and modifies existing disagreement-based active learning algorithms to exploit logged data.

Fast and accurate visual search is an enabler for many applications of drones. Prior works use POMDPs to produce effective search strategies. As the observation models are from heuristics, the robustness of these approaches on the field is unclear. This work builds a testbed that combines latest developments in related areas, including mobile CNNs for inference on mobile platforms and policy search with point based methods, in a POMDP framework. A dataset for a simple but realistic application, search for a single basketball, is collected to train the perception modules, investigate their error characteristics and validate the control algorithm. From simulation using realistic parameters, we found the significant role persistent factors in the environment can play in designing a fast search strategy. Failure to taking these factors into account results in up to 60% longer search time at the same success rate. Our empirical tests using mobile CNN and real data reveals that prior assumptions on error rates as functions of heights are wrong. The errors grows non-linearly, and there is significant between false positive and false negative rates. Our findings shed new lights on what to consider in designing visual search strategies in a drone platform and is one step towards a fast and robust algorithm.

This paper considers the problem of bit-wise channel coding over a Binary Symmetric Channel (BSC) with feedback. While it is known that feedback does not increase the capacity of a memoryless channel, it is believed to simplify the coding schemes for some channels. The most significant one is the Binary Erasure Channel (BEC) where capacity is achieved by a simple sequential bit-wise repetition code under which each bit is (re-)transmitted until it is received. This sequential bit-wise feedback code has the added advantage that it can be used for streaming applications over BECs. In contrast, there is no known sequential bit-wise code with feedback that can achieve nonzero transmission rate for a BSC. For example, under Posterior Matching for a binary input channel with feedback, also known as Horstein scheme, each message is considered in its entirety in a block coding manner. This paper proposes a sequential feedback coding scheme with a nested bit-wise structure that generalizes repetition codes. This scheme is shown to achieve strictly positive rate for a large class of binary input channels including a BSC with arbitrary cross-over probability p ∈ (0, 1/2). The analysis relies on characterizing a lower bound on the step-wise Extrinsic Jensen Shannon divergence.

Consider a target moving at a constant velocity on a unit-circumference circle, starting at an arbitrary location. To acquire the target, any region of the circle can be probed to obtain a noisy measurement of the target’s presence, where the noise level increases with the size of the probed region. We are interested in the expected time required to find the target to within some given resolution and error probability. For a known velocity and a given reliability, we provide an asymptotical characterization of the optimal tradeoff between time and resolution. Considering an asymptotically diminishing error probability, we derive the maximal targeting rate, and show that in contrast to the well-studied case of constant measurement noise, measurement dependent noise incurs a multiplicative gap in the maximal targeting rate between adaptive and non-adaptive search strategies. Moreover, for all rates below this maximal rate, our adaptive strategy attains the optimal rate-reliability tradeoff. We further show that accounting for a target moving at an unknown fixed velocity, the optimal non-adaptive search strategy incurs a factor of at least two in the maximal targeting rate.

Multi-task learning aims to improve generalization performance of multiple prediction tasks by appropriately sharing relevant information across them. In the context of deep neural networks, this idea is often realized by hand-designed network architectures with layers that are shared across tasks and branches that encode task-specific features. However, the space of possible multi-task deep architectures is combinatorially large and often the final architecture is arrived at by manual exploration of this space, which can be both error-prone and tedious. We propose an automatic approach for designing compact multi-task deep learning architectures. Our approach starts with a thin multi-layer network and dynamically widens it in a greedy manner during training. By doing so iteratively, it creates a tree-like deep architecture, on which similar tasks reside in the same branch until at the top layers. Evaluation on person attributes classification tasks involving facial and clothing attributes suggests that the models produced by the proposed method are fast, compact and can closely match or exceed the state-of-the-art accuracy from strong baselines by much more expensive models.

We consider the problem of estimating the covariance matrix and the transition matrix of vector autoregressive (VAR) processes from partial measurements. This model encompasses settings where there are limitations in the data acquisition of the underlying measurement systems so that data is lost or corrupted by noise. An estimator for the covariance matrix of the observations is first presented. More refined estimators, factoring in structural constraints on the covariance matrix such as sparsity, bandedness, sparsity of the inverse and low-rankness are then introduced that are particularly useful in the high-dimensional regime. These estimates are then used to perform system identification by estimating the state transition matrix with or without further structural assumptions. Non-asymptotic guarantees are presented for all estimators.

Optical switches have been drawing attention due to their large data bandwidth and low power consumption. However, scheduling policies need to account for the schedule reconfiguration delay of optical switches to achieve good performance. The Adaptive MaxWeight policy achieves optimal throughput for switches with nonzero reconfiguration delay, and has been shown in simulation to have good delay performance. In this paper, we analyze the queue length behavior of a switch with nonzero reconfiguration delay operating under the Adaptive MaxWeight. We first show that the Adaptive MaxWeight policy exhibits a weak state space collapse behavior in steady-state, which could be viewed as an inheritance of the MaxWeight policy in a switch with zero reconfiguration delay. We then use the weak state space collapse result to obtain a steady state delay bound under the Adaptive MaxWeight algorithm in heavy traffic by applying a recently developed drift technique. The resulting delay bound is dependent on the expected schedule duration. We then derive the relation between the expected schedule duration and the steady state queue length through drift analysis, and obtain asymptotically tight queue length bounds in the heavy traffic regime.

This paper considers the problem of searching for the unknown location of a target among a finite number of possible locations by probing multiple locations simultaneously. Outcome of each search measurement is corrupted by Gaussian noise whose intensity is proportional to the number of locations probed. We characterize a non-asymptotic lower bound on adaptivity gain; i.e. reduction in the expected number of measurements under an adaptive search strategies over the non-adaptive search strategies. Then we investigate the adaptivity gain in two complementary asymptotic regimes: one where the total search area is kept fixed but the location width is shrinking or the search resolution is increasing, and the other where each location width is fixed but the total search area is growing. Interestingly, adaptivity gain grows in distinctly different manner in these two regimes. In particular, adaptivity gains are significant in the later regime when the total search space grows; implying adaptivity is far more critical when either total search area or the noise intensity is large.

We consider the problem of estimating the parameters of a vector autoregressive (VAR) process from low-dimensional random projections of the observations. This setting covers the cases where we take compressive measurements of the observations or have limits in the data acquisition process associated with the measurement system and are only able to subsample. We first present fundamental bounds on the convergence of any estimator for the covariance or state-transition matrices with and without considering structural constraints of sparsity and low-rankness. We then construct an estimator for these matrices or the parameters of the VAR process and show that it is order optimal.

This paper considers a problem of distributed active hypothesis testing. At every time instant, individual nodes in the network adaptively choose a sensing action and receive noisy local (private) observations as sensing outcomes. The distribution of observations is parameterized by a discrete parameter (hypotheses). The marginals of the joint observation distribution conditioned on each hypothesis and the action are known locally at the nodes, but the true parameter/hypothesis is not known. An update rule is analyzed in which nodes first choose a possibly randomized action as a function of their past observations and actions. Nodes then perform a Bayesian update of their belief (distribution estimate) on each hypothesis based on their current local observations. Each node communicates these updates to its neighbors, and then performs a “non-Bayesian” linear consensus using the log-beliefs of its neighbors. Under mild assumptions and for a general class of action selection strategies, we show that the belief of any node on a wrong hypothesis converges to zero exponentially fast, and the exponential rate of learning is characterized by the nodes' influence of the network and average distinguishability between the observations' distributions for the (randomized) action under the true hypothesis.

All-optical switching networks have been considered a promising candidate for the next generation data center networks thanks to its scalability in data bandwidth and power efficiency. However, the bufferless nature and the nonzero reconfiguration delay of optical switches remain great challenges in deploying all-optical networks. This paper considers the end-to-end scheduling for all-optical data center networks with no in-network buffer and nonzero reconfiguration delay. A framework is proposed to deal with the nonzero reconfiguration delay. The proposed approach constructs an adaptive variant of any given scheduling policy. It is shown that if a scheduling policy guarantees its schedules to have schedule weights close to the MaxWeight schedule (and thus is throughput optimal in the zero reconfiguration regime), then the throughput optimality is inherited by its adaptive variant (in any nonzero reconfiguration delay regime). As a corollary, a class of adaptive variants of the well-known MaxWeight policy is shown to achieve throughput optimality without prior knowledge of the traffic load. Furthermore, through numerical simulations, the simplest such policy, namely, the Adaptive MaxWeight, is shown to exhibit better delay performance than all prior work.

State-of-the-art object detection systems rely on an accurate set of region proposals. Several recent methods use a neural network architecture to hypothesize promising object locations. While these approaches are computationally efficient, they rely on fixed image regions as anchors for predictions. In this paper we propose to use a search strategy that adaptively directs computational resources to sub-regions likely to contain objects. Compared to methods based on fixed anchor locations, our approach naturally adapts to cases where object instances are sparse and small. Our approach is comparable in terms of accuracy to the state-of-the-art Faster R-CNN approach while using two orders of magnitude fewer anchors on average. Code is publicly available.

The increasing number of connected vehicles in densely populated urban areas provides an interesting opportunity to counteract the high wireless data demands in high density and highly mobile scenarios. The idea is to support the macro base station (BS) with a secondary communication tier composed of a set of smart and connected vehicles that are in movement in the urban area. As a first step towards a comprehensive cost-benefit analysis of this architecture, this paper considers the case where these vehicles are equipped with femto-mobile Access Points (fmAPs) and constitute a mobile out-of-band relay infrastructure. In particular, three techniques to select an fmAP (if more than one is available) are proposed and the maximal feasible gain in the data rate is characterized as a function of the vehicle density, average vehicle speeds, handoff overhead cost, as well as physical layer parameters. The analytical and simulation results provide a first benchmark characterizing this architecture and the definition of guidelines for its future realistic study and implementation.

The maximum type-I and type-II error exponents associated with the newly introduced almost-fixed-length hypothesis testing is characterized. In this class of tests, the decision-maker declares the true hypothesis almost always after collecting a fixed number of samples n; however in very rare cases with exponentially small probability the decision maker is allowed to collect another set of samples (no more than polynomial in n). This class of hypothesis tests are shown to bridge the gap between the classical hypothesis testing with a fixed sample size and the sequential hypothesis testing, and improve the trade-off between type-I and type-II error exponents.

Consider a target search problem on a unit interval where at any given time an agent can choose a region to probe into for the presence of the target in that region. The measurement noise is assumed to be increasing with the size of the search region the agent chooses. In this paper, a single-phase sequential and adaptive search algorithm is proposed and shown to achieve the best possible targeting rate and error exponent among all adaptive search algorithms. The proposed algorithm simply adopts a low complexity sorting operation on the posterior of the target and then pick up locations with larger posterior until the probability that the search region contains the target is closest to half.

We study active learning where the labeler can not only return incorrect labels but also abstain from labeling. We consider different noise and abstention conditions of the labeler. We propose an algorithm which utilizes abstention responses, and analyze its statistical consistency and query complexity under fairly natural assumptions on the noise and abstention rate of the labeler. This algorithm is adaptive in a sense that it can automatically request less queries with a more informed or less noisy labeler. We couple our algorithm with lower bounds to show that under some technical conditions, it achieves nearly optimal query complexity.

We consider the problem of routing packets across a multi-hop network consisting of multiple sources of traffic and wireless links while ensuring bounded expected delay. Each packet transmission can be overheard by a random subset of receiver nodes among which the next relay is selected opportunistically. The main challenge in the design of minimum-delay routing policies is balancing the trade-off between routing the packets along the shortest paths to the destination and distributing the traffic according to the maximum backpressure. Combining important aspects of shortest path and backpressure routing, this paper provides a systematic development of a distributed opportunistic routing policy with congestion diversity (D-ORCD). D-ORCD uses a measure of draining time to opportunistically identify and route packets along the paths with an expected low overall congestion. D-ORCD with single destination is proved to ensure a bounded expected delay for all networks and under any admissible traffic, so long as the rate of computations is sufficiently fast relative to traffic statistics. Furthermore, this paper proposes a practical implementation of D-ORCD which empirically optimizes critical algorithm parameters and their effects on delay as well as protocol overhead. Realistic QualNet simulations for 802.11-based networks demonstrate a significant improvement in the average delay over comparable solutions in the literature.

This paper considers the end-to-end scheduling for all-optical data center networks with zero in-network buffer and non-negligible reconfiguration delay. It is known that in the regime where the scheduling reconfiguration delay is non-negligible, the rate of schedule reconfiguration should be limited in such a way as to minimize the impact of reduced duty-cycles and to ensure bounded delay. However, when the scheduling rate is restricted, the existing literature also tends to restrict the rate of monitoring and decision processes. We first present a framework for scheduling with reconfiguration delay that decouples the rate of scheduling from the rate of monitoring. Under this framework, we then present two scheduling algorithms for switches with reconfiguration delay, both based on the well-known MaxWeight scheduling policy. The first one is the Periodic MaxWeight (PMW), which is simpler in computation, but requires prior knowledge of traffic load. The other is the Adaptive MaxWeight (AMW), which, in contrast, requires no prior knowledge. We show the stability condition for both algorithms and evaluate their delay performance through simulations.

We consider a search problem in which multiple targets are uniformly placed on the unit interval. An agent, who might not know the number of targets in advance, is interested in acquiring all targets to within some resolution δ as quickly as possible. To that end, at each time unit, the agent can probe any region of the unit interval for the presence of targets but the associated measurement noise increases with the size of the probed region. We characterize the maximal targeting rate, the optimal tradeoff between resolution and expected search time, with adaptive and non-adaptive search strategies, highlighting the advantage of adaptive strategies. We show that even when the number of targets is known, in contrast to the case of constant measurement noise, there is a multiplicative gap between the performance of adaptive and non-adaptive search. This gap, however, diminishes as the number of targets grow.

We consider the estimation of a standard Gaussian random variable under an observation attack where an adversary may add a zero mean Gaussian noise with variance in a bounded, closed interval to an otherwise noiseless observation. A straightforward approach would entail either ignoring the attack and simply using an optimal estimator under normal operation or taking the worst-case attack into account and using a minimax estimator that minimizes the cost under the worst-case attack. In contrast, we seek to characterize the optimal tradeoff between the MSE under normal operation and the MSE under the worst-case attack. Equivalently, we seek a minimax estimator for any fixed prior probability of attack. Our main result shows that a unique minimax estimator exists for every fixed probability of attack and is given by the Bayesian estimator for a least-favorable prior on the set of possible variances. Furthermore, the least-favorable prior is unique and has a finite support. While the minimax estimator is linear when the probability of attack is 0 or 1, our numerical results show that the minimax linear estimator is far from optimal for all other probabilities of attack and a simple nonlinear estimator does much better.

It is widely believed that future small-cell unmanaged wireless networks will be dominated by interference caused by packet collisions and not by signal-to-noise issues. In such a network, a large fraction of the collisions are caused by hidden terminals. Here we present the design and evaluation of RoXOR, a system that can effectively combat random collisions caused by bursty traffic from hidden terminals. RoXOR relies on jointly using both the amount of redundancy and the structure of the redundancy, as expressed by a code. Using these degrees of freedom, we design and experimentally evaluate an iterative rateless code that with high probability achieves better performance as compared to methods such as ZigZag. The mean improvement, as measured by the per packet delay, is 12-18% for values typically used for a 802.11× protocol.

A novel architecture for the future data center networks with possibly up to a thousand of Top of the Rack (ToR) switches is proposed. The proposed architecture, WiCOD, relies on a wireless control plane serving an all-optical data plane. The first contribution of the work is the separation of the data and the control planes: while the data is switched between the ToR switches in an all-optical high rate network, the network state and control information is continuously conveyed to and from a central unit over an ultra low-latency wireless network. A proof of concept for this architecture is also presented by considering the initial design possibilities for each one of the planes. In order to obtain low packet delays, the data plane scheduling policies take non-zero reconfiguration and monitoring delays into consideration. The results prove that very low queueing delays are guaranteed for strictly frequent updates on the network state. Based on this observation, a technique for monitoring of ToR switch queue occupancy information is purposed. This monitoring technique uses mmWave wireless communications via a spatially adapted MIMO Orthogonal Frequency Division Multiple Access (MIMO-OFDMA) over a static frequency selective channel with large number of densely packed ToRs. The reduced monitoring delays, offered by this low-latency radio access technology, makes the fine-grained and adaptive circuit switching feasible and, in turn, enables a high utilization of optical switches.

In-network queuing in the Internet-style networks enables the distributed operation and scalability across the network at the cost of excessive delay and tardy flow completion times. Data center networking, in contrast, are proposed to depart from this classical approach and avoid in-network queuing all together. In this new class of network solutions serving interdata center traffic, a densely packed fairly local area network of stationary end hosts are often managed by a single entity, allowing for fine-grained management and scheduling of flows across the data center. The overall objective of this work is to develop a framework, from first principles, which relies on the unique attributes of data centers to propose a transformative novel networking architecture with increased level of efficiency and significantly smaller latency. By separating the control and data planes, the proposed hybrid architecture avoids in-network queuing and results in significantly lower delay. The critical technical challenge is to design endend circuit switching mechanisms that account for monitoring as well as circuit reconfiguration delays. Furthermore, the design has to minimize the computational complexity of the scheduling algorithm as well as the cost of monitoring across the network. In this context, this paper underlines a family of recent technologies and networking advances as promising enablers and discusses the most significant set of challenges.

We consider the problem of noisy Bayesian active learning where we are given a finite set of functions H, a sample space X , and a label set £. One of the functions in H assigns labels to samples in X . The goal is to identify the function that generates the labels even though the result of a label query on a sample is corrupted by independent noise. More precisely, the objective is to declare one of the functions in H as the true label generating function with high confidence using as a few label queries as possible, by selecting the queries adaptively and in a strategic manner. Previous work in Bayesian active learning considers generalized binary search and its variants for the noisy case, and analyzes the number of queries required by these sampling strategies. In this paper, we show that these schemes are, in general, suboptimal. Instead we propose and analyze an alternative strategy for sample collection. Our sampling strategy is motivated by a connection between Bayesian active learning and active hypothesis testing, and is based on querying the label of a sample, which maximizes the extrinsic Jensen-Shannon divergence at each step. We provide upper and lower bounds on the performance of this sampling strategy, and show that these bounds are better than the previous bounds in the literature.

This paper considers the problem of variable-length coding over a discrete memoryless channel with noiseless feedback. This paper provides a stochastic control view of the problem whose solution is analyzed via a newly proposed symmetrized divergence, termed extrinsic Jensen-Shannon (EJS) divergence. It is shown that strictly positive lower bounds on EJS divergence provide nonasymptotic upper bounds on the expected code length. This paper presents strictly positive lower bounds on EJS divergence, and hence nonasymptotic upper bounds on the expected code length, for the following two coding schemes: 1) variable-length posterior matching and 2) MaxEJS coding scheme that is based on a greedy maximization of the EJS divergence. As an asymptotic corollary of the main results, this paper also provides a rate-reliability test. Variable-length coding schemes that satisfy the condition(s) of the test for parameters R and E are guaranteed to achieve a rate R and an error exponent E. The results are specialized for posterior matching and MaxEJS to obtain deterministic one-phase coding schemes achieving capacity and optimal error exponent. For the special case of symmetric binary-input channels, simpler deterministic schemes of optimal performance are proposed and analyzed.

This paper reports on a comprehensive study comparing congestion-aware routing algorithms for wireless mesh networks with a state-of-the-art shortest-path routing protocol: Link-Quality Source Routing (LQSR). In particular, a set of congestion-aware protocols in the literature, Backpressure (BP), Enhanced-Backpressure (E-BP) and Congestion Diversity Protocol (CDP) are suitably adapted for implementation on 802.11-compatible radios. A testbed consisting of 802.11g nodes is deployed to empirically compare the performance of these congestion-aware routing protocols against LQSR. The results show that, under moderate to heavy UDP traffic, CDP delivers significant improvement compared to LQSR in 80-90 percent of the instances studied, while backpressure-based routing algorithms (BP and E-BP) frequently show significant degradation with respect to LQSR for both UDP and TCP traffic.

This paper considers a problem of distributed hypothesis testing and social learning. Individual nodes in a network receive noisy (private) observations whose distribution is parameterized by a discrete parameter (hypotheses). The distributions are known locally at the nodes, but the true parameter/hypothesis is not known. An update rule is analyzed in which agents first perform a Bayesian update of their belief (distribution estimate) of the parameter based on their local observation, communicate these updates to their neighbors, and then perform a “non-Bayesian” linear consensus using the log-beliefs of their neighbors. The main result of this paper is that under mild assumptions, the belief of any agent in any incorrect parameter converges to zero exponentially fast, and the exponential rate of learning is a characterized by the network structure and the divergences between the observations' distributions.

The optimal strategy for dynamic joint source-channel coding with feedback was recently shown to be a simple mapping between the source symbols and channel inputs, where the mapping only depends on the decoder's posterior belief about the source. In this work, we derive the optimal joint source-channel coding strategies for two specific channels - binary erasure channels and Z-channels. It is found that the mappings required for the optimal strategies and the way they are used vary significantly with the channel cost of transmission.

Consider a target moving with a constant velocity on a unit-circumference circle, starting from an arbitrary location. To acquire the target, any region of the circle can be probed for its presence, but the associated measurement noise increases with the size of the probed region. We are interested in the expected time required to find the target to within some given resolution and error probability. For a known velocity, we characterize the optimal tradeoff between time and resolution (i.e., maximal rate), and show that in contrast to the case of constant measurement noise, measurement dependent noise incurs a multiplicative gap between adaptive search and non-adaptive search. Moreover, our adaptive scheme attains the optimal rate-reliability tradeoff. We further show that for optimal non-adaptive search, accounting for an unknown velocity incurs a factor of two in rate.

In wireless body area networks (WBANs) it is necessary to devise an energy-efficient MAC scheduling mechanism which is capable of meeting strict QoS requirements. In this paper, special characteristics of WBAN channels, namely, the slow fading, the periodicity of fading, and the correlation among the channels have been exploited to formulate the sensor scheduling problem as a partially observable Markov decision problem (POMDP). Specific algorithms based on value iteration and pruning have been proposed in order to reduce the computational burden associated with the corresponding POMDP. The proposed scheduling mechanism is compared against a TDMA scheduling for a three-sensor network, and an average 22-32% improvement in energy consumption and slight improvement in reliability is reported.

This paper considers real time joint source-channel coding of a Markov source over a discrete memoryless channel with noiseless feedback. The encoder incurs a cost which is minimized along with a real-time end-to-end distortion. The problem is mapped to a partially observable Markov decision problem and the corresponding optimality equations, in the form of dynamic programming equations, are derived. As a consequence of the dynamic programming formulation, basic structural properties of the optimal encoding and decoding strategies are established. In addition, the problem formulation and solution obtained for dynamic joint source-channel coding with noiseless feedback is shown to encompass a much broader class of problems including that of information acquisition and real time tracking.

Consider the problem of sequentially searching for a single target in an image. Let the image be divided into M × M equal sized segments where M determines the resolution of the search. The goal is to find the segment that contains the target quickly and accurately. In each step, the player can visually inspect an allowable combination of the segments, and the outcome of the inspection is noisy. In this paper, a lower bound on the optimal total cost is derived. Furthermore, two heuristic policies are considered: A policy that visually inspects a segment with the highest probability of having the target; and a policy that in each step inspects a combination that maximizes the Extrinsic Jensen- Shannon divergence. Via numerical and asymptotic analysis, the performance of the above policies are investigated.

Consider a decision maker who is responsible to dynamically collect observations so as to enhance his information in a speedy manner about an underlying phenomena of interest while accounting for the penalty of wrong declarations. In this paper, Extrinsic Jensen-Shannon (EJS) divergence is introduced as a measure of information. Using EJS as an information utility, a heuristic policy for selecting actions is proposed. Via numerical and asymptotic optimality analysis, the performance of the proposed policy, hence the applicability of the EJS divergence in the context of the active hypothesis testing is investigated.

This paper considers the problem of variable-length coding over a binary-input channel with noiseless feedback. A deterministic sequential coding scheme is proposed and shown to attain the optimal error exponent for any binary-input channel whose capacity is achieved by the uniform input distribution. The proposed scheme is deterministic and has only one phase of operation, in contrast to all previous coding schemes that achieve the optimal error exponent.

The capacity region of the -sender Gaussian multiple access channel with feedback is not known in general. This paper studies the class of linear-feedback codes that includes (nonlinear) nonfeedback codes at one extreme and the linear-feedback codes by Schalkwijk and Kailath, Ozarow, and Kramer at the other extreme. The linear-feedback sum-capacity under symmetric power constraints is characterized, the maximum sum-rate achieved by linear-feedback codes when each sender has the equal block power constraint . In particular, it is shown that Kramer's code achieves this linear-feedback sum-capacity. The proof involves the dependence balance condition introduced by Hekstra and Willems and extended by Kramer and Gastpar, and the analysis of the resulting nonconvex optimization problem via a Lagrange dual formulation. Finally, an observation is presented based on the properties of the conditional maximal correlation-an extension of the Hirschfeld-Gebelein-Rényi maximal correlation-which reinforces the conjecture that Kramer's code achieves not only the linear-feedback sum-capacity, but also the sum-capacity itself (the maximum sum-rate achieved by arbitrary feedback codes).

This paper considers the problem of throughput optimal routing/scheduling in a multi-hop constrained queueing network with random connectivity whose special cases include opportunistic multi-hop wireless networks and input-queued switch fabrics. The main challenge in the design of throughput optimal routing policies is closely related to identifying appropriate and universal Lyapunov functions with negative expected drift. The few well-known throughput optimal policies in the literature are constructed using simple quadratic or exponential Lyapunov functions of the queue backlogs and as such they seek to balance the queue backlogs across network independent of the topology. By considering a class of continuous, differentiable, and piece-wise quadratic Lyapunov functions, this paper provides a large class of throughput optimal routing policies. The proposed class of Lyapunov functions allow for the routing policy to control the traffic along short paths for a large portion of state-space while ensuring a negative expected drift. This structure enables the design of a large class of routing policies. In particular, and in addition to recovering the throughput optimality of the well-known backpressure routing policy, an opportunistic routing policy with congestion diversity is proved to be throughput optimal.

A distributed adaptive opportunistic routing scheme for multihop wireless ad hoc networks is proposed. The proposed scheme utilizes a reinforcement learning framework to opportunistically route the packets even in the absence of reliable knowledge about channel statistics and network model. This scheme is shown to be optimal with respect to an expected average per-packet reward criterion. The proposed routing scheme jointly addresses the issues of learning and routing in an opportunistic context, where the network structure is characterized by the transmission success probabilities. In particular, this learning framework leads to a stochastic routing scheme that optimally “explores” and “exploits” the opportunities in the network.

This work presents the Congestion Diversity Protocol (CDP), a routing protocol for multi-hop wireless networks that combines important aspects of shortest-path and backpressure routing to achieve improved end-end delay performance. In particular, CDP delivers lower end-to-end delay and fewer packet drops than existing routing protocols while maintaining equivalent throughput. This paper reports on a practical (hardware and software) implementation of CDP in an indoor WiFi network consisting of 12 802.11g nodes. This small test-bed enables an imperical comparison of CDP's performance against a set of state of the art protocols which include both congestion unaware and congestion aware routing protocols. In most topologies and scenarios we consider, CDP provides improvements for UDP traffic with respect to both end-end delay and throughput over the existing protocols.

Consider a decision maker who is responsible to dynamically collect observations so as to enhance his information in a speedy manner about an underlying phenomena of interest while accounting for the cost of data collection. Due to the sequential nature of the problem, the decision maker relies on his current information state to adaptively (re-)evaluate the tradeoff between the cost of various sensing actions and the precision of their outcomes. In this paper, using results in dynamic programming, a lower bound for the optimal total cost is established. Moreover, an upper bound is obtained using a heuristic policy for dynamic selection of actions. Using the obtained bounds, the closed loop (feedback) gain is shown to be at least logarithmic in the penalty associated with wrong declarations. Furthermore, it is shown that the proposed heuristic achieves asymptotic optimality in many practically relevant problems such as variable-length coding with feedback and noisy dynamic search.

Scheduling for multi-channel (e.g., OFDM-based) wireless downlink systems is considered with the objective of providing low delay performance to users with real-time and stochastic traffic. The main contribution is the design of a low-complexity scheduling algorithm for the system with desired performance (in a large deviations sense). In particular, as the number of users and channels grows, the algorithm ensures an exponential decay of the probability of encountering significant delay at a near optimal decay rate when the arrivals are symmetric and the channel follows an ON-OFF model with multi-packet reception. The algorithm also provides consistently good performance in the larger set up by guaranteeing throughput optimality, and a non-zero decay rate if it is possible under any other algorithm.

In this paper, a many-sources large deviations principle (LDP) for the transient workload of a multiqueue single-server system is established where the service rates are chosen from a compact, convex, and coordinate-convex rate region and where the service discipline is the max-weight policy. Under the assumption that the arrival processes satisfy a many-sources LDP, this is accomplished by employing Garcia's extended contraction principle that is applicable to quasi-continuous mappings. For the traditional single-server queue (simplex rate-region), an LDP for the stationary workload is also established under the additional requirements that the scheduling policy be work-conserving and that the arrival processes satisfy certain mixing conditions. The LDP results can be used to calculate asymptotic buffer overflow probabilities accounting for the multiplexing gain, e.g., when the arrival process is an average of i.i.d. processes. The rate function for the stationary workload is expressed in term of the rate functions of the finite-horizon workloads when the arrival processes have i.i.d. increments.

This paper considers the problem of routing packets across a multi-hop network consisting of multiple sources of traffic and wireless links with stochastic reliability while ensuring bounded expected delay. Each packet transmission can be overheard by a random subset of receiver nodes among which the next relay is selected opportunistically. The main challenge in the design of minimum-delay routing policies is balancing the trade-off between routing the packets along the shortest paths to the destination and distributing traffic across the network. Opportunistic variants of shortest path routing may, under heavy traffic scenarios, result in severe congestion and unbounded delay. While the opportunistic variants of backpressure, which ensure a bounded expected delay, are known to exhibit poor delay performance at low to medium traffic conditions. Combining important aspects of shortest path routing with those of backpressure routing, this paper provides an opportunistic routing policy with congestion diversity (ORCD). ORCD uses a measure of draining time to opportunistically identify and route packets along the paths with an expected low overall congestion. Previously, ORCD was proved to ensure a bounded expected delay for all networks and under any admissible traffic (without any knowledge of traffic statistics). This paper proposes practical implementations and discusses criticality of various aspects of the algorithm. Furthermore, the expected delay encountered by the packets in the network under ORCD is compared against known existing routing policies via simulations where substantial improvements are observed.

This paper studies the class of generalized linear feedback codes for additive white Gaussian noise multiple access channel. This class includes (nonlinear) nonfeedback codes at one extreme and linear feedback codes by Schalkwijk and Kailath, Ozarow, and Kramer at the other extreme. The linear sum capacity CL(P), the maximum sum-rate achieved by the generalized linear feedback codes, is characterized under symmetric block power constraints P for all the senders. In particular, it is shown that the Kramer linear code achieves CL(P). Based on the properties of the conditional maximal correlation, an extension of the Hirschfeld-Gebelein-Renyi maximal correlation, it is conjectured that Kramer's linear code achieves not only the linear sum capacity, but also the general sum capacity, i.e., the maximum sum-rate achieved by arbitrary feedback codes.

This paper considers a generalized sequential hypothesis testing problem in which a decision maker not only can sequentially trade off the sensing cost with the declaration precision, but also can exert control over the sensed information. Here, the decision maker's action impacts the sensing cost as well as outcome. Numerically solving an appropriate DP, it is shown that the sensing outcome has a dual role: (1) it immediately reduces the uncertainty in the decision maker's belief; and (2) it shapes the future belief via Bayes' rule. This paper focuses on sufficient conditions rendering the optimal sensing actions independent of the current and future belief vector, and reducing the problem to a classical (passive) hypothesis testing problem.

We consider the problem of coordinating a group of mobile nodes communicating through a wireless medium. The objective of the network is the alignment of all the nodes towards a common direction through local interactions, without the need for global knowledge such as the network topology or the maximum degree of the network, or even local parameters, such as the number of neighbors. The key feature of our algorithm is that each node state update is done through voting, where the probability of each vote is biased by the state of the node neighbors. We propose two possible physical implementations for our algorithm. The first is based on the explicit exchange of packetized messages, while the second is a cross-layer approach. Our analysis unveils key convergence properties of this simple class of alignment algorithms, via analytical and simulated results.

In this paper, an adaptive opportunistic routing scheme for multi-hop wireless ad-hoc networks is proposed. The proposed scheme utilizes a reinforcement learning framework to achieve the optimal performance even in the absence of reliable knowledge about channel statistics and network model. This scheme is shown to be optimal with respect to an expected average per packet cost criterion. The proposed routing scheme jointly addresses the issues of learning and routing in an opportunistic context, where the network structure is characterized by the transmission success probabilities. In particular, this learning framework leads to a stochastic routing scheme which optimally ldquoexploresrdquo and ldquoexploitsrdquo the opportunities in the network.

Data transmission over a discrete memoryless channel is considered when the arrival of data is bursty and is subject to a delay deadline. An exponential decay of the probability of delay violation with respect to a large delay deadline is proved when the block length scales linearly with the deadline. When considered in conjunction with Gallager's error exponents, the first natural consequence of this result is a separation principle: a separated scheme of buffering traffic and block-coding transmissions achieves arbitrarily high reliability for an asymptotically large delay budget. Furthermore, the exponential decay nature of the result provides some insight as how to budget the delay limit between the coding time and the waiting time in the queue.

We consider a network where each route comprises a backlogged source, a number of relays and a destination at a finite distance. The locations of the sources and the relays are realizations of independent Poisson point processes. Given that the nodes observe a TDMA/ALOHA MAC protocol, our objective is to determine the number of relays and their placement such that the mean end-to-end delay in a typical route of the network is minimized. We first study an idealistic network model where all routes have the same number of hops, the same distance per hop and their own dedicated relays. Combining tools from queueing theory and stochastic geometry, we provide a precise characterization of the mean end-to-end delay. We find that the delay is minimized if the first hop is much longer than the remaining hops and that the optimal number of hops scales sublinearly with the source-destination distance. Simulating the original network scenario reveals that the analytical results are accurate, provided that the density of the relay process is sufficiently large. We conclude that, given the considered MAC protocol, our analysis provides a delay-minimizing routing strategy for random, multihop networks involving a small number of hops.

This paper considers opportunistic communication over multiple channels where the state (ldquogoodrdquo or ldquobadrdquo) of each channel evolves as independent and identically distributed (i.i.d.) Markov processes. A user, with limited channel sensing capability, chooses one channel to sense and decides whether to use the channel (based on the sensing result) in each time slot. A reward is obtained whenever the user senses and accesses a ldquogoodrdquo channel. The objective is to design a channel selection policy that maximizes the expected total (discounted or average) reward accrued over a finite or infinite horizon. This problem can be cast as a partially observed Markov decision process (POMDP) or a restless multiarmed bandit process, to which optimal solutions are often intractable. This paper shows that a myopic policy that maximizes the immediate one-step reward is optimal when the state transitions are positively correlated over time. When the state transitions are negatively correlated, we show that the same policy is optimal when the number of channels is limited to two or three, while presenting a counterexample for the case of four channels. This result finds applications in opportunistic transmission scheduling in a fading environment, cognitive radio networks for spectrum overlay, and resource-constrained jamming and antijamming.

This paper studies the problem of secure communication over a wiretap channel p(y,z|x) with a secure feedback link of rate Rf, where X is the channel input, and Y and Z are channel outputs observed by the legitimate receiver and the eavesdropper, respectively. It is shown that the secrecy capacity, the maximum data rate of reliable communication while the intended message is not revealed to the eavesdropper, is upper bounded as Cs(Rf) les maxmin/p(x) {I(X;Y), I(X;Y |Z) + Rf}. The proof of the bound crucially depends on a recursive argument which is used to obtain the single-letter characterization. This upper bound is shown to be tight for the class of physically degraded wiretap channels. A capacity-achieving coding scheme is presented for this case, in which the receiver securely feeds back fresh randomness with rate Rf, generated independent of the received channel output symbols. The transmitter then uses this shared randomness as a secret key on top of Wyner's coding scheme for wiretap channels without feedback. Hence, when a feedback link is available, the receiver should allocate all resources to convey a new key rather than sending back the channel output.

This work analyzes the high-SNR asymptotic error performance of outage-limited communications with fading, where the number of bits that arrive at the transmitter during any timeslot is random but the delivery of bits at the receiver must adhere to a strict delay limitation. Specifically, bit errors are caused by erroneous decoding at the receiver or violation of the strict delay constraint. Under certain scaling of the statistics of the bit-arrival process with SNR, this paper shows that the optimal decay behavior of the asymptotic total probability of bit error depends on how fast the burstiness of the source scales down with SNR. If the source burstiness scales down too slowly, the total probability of error is asymptotically dominated by delay-violation events. On the other hand, if the source burstiness scales down too quickly, the total probability of error is asymptotically dominated by channel-error events. However, at the proper scaling, where the burstiness scales linearly with${{ 1}\over { \sqrt {\log {\rm SNR} }}}$and at the optimal coding duration and transmission rate, the occurrences of channel errors and delay-violation errors are asymptotically balanced. In this latter case, the optimal exponent of the total probability of error reveals a tradeoff that addresses the question of how much of the allowable time and rate should be used for gaining reliability over the channel and how much for accommodating the burstiness with delay constraints.

This paper considers the problem of optimal server allocation in a time-slotted system with N statistically symmetric queues and K servers when the arrivals and channels are stochastic and time-varying. In this setting, we identify two classes of "desirable" policies with potentially competing goals of maximizing instantaneous throughput versus balancing the load. Via an example, we show that these goals, in general, can be incompatible, implying an empty intersection between the two classes of policies. On the other hand, we establish the existence of a policy achieving both goals when the connectivities between each queue and each server are random and either "ON" or "OFF". We use dynamic programming (DP) and properties of the value function to establish the delay optimality of a policy, which, at each time-slot, simultaneously maximizes the instantaneous throughput and balances the queues.

The implementation of QoS provisioning at the MAC layer requires users to classify their traffic into QoS categories. In realistic scenarios where users are selfish and interested in maximizing their own utility, users may have an interest in misrepresenting the QoS category of their traffic. We examine a simplified model for IEEE 802.11e networks in which channel access can be obtained via random access or polling. Using concepts from game theory, we show that a polling based incentive mechanism can stimulate users to truthfully report the QoS category of their traffic. Furthermore, we show that our incentive mechanism improves the system capacity, in terms of the number of QoS constrained users that can be admitted, when users are strategic.

In this paper, we examine the use of pricing for distributed, incentive-compatible and socially optimal resource allocation in a QoS-differentiated random-access wireless network. We argue that QoS mechanisms in wireless networks are susceptible to misuse by self-interested users. We first present a simple pricing scheme that leads to social optimality (i.e., achieves QoS-differentiated proportional fairness) when users' utility functions are known to the AP. We then characterize the price of anarchy when users are strategic. Finally, the centerpiece of this paper is a pricing scheme that ensures socially optimal operation as a Nash equilibrium strategy among users whose utility functions are not known and who attempt to access the channel in a decentralized manner.

We consider opportunistic communications over multiple channels where the state ("good" or "bad") of each channel evolves as independent and identically distributed Markov processes. A user, with limited sensing and access capability, chooses one channel to sense and subsequently access (based on the sensed channel state) in each time slot. A reward is obtained when the user senses and accesses a "good" channel. The objective is to design the optimal channel selection policy that maximizes the expected reward accrued over time. This problem can be generally formulated as a Partially Observable Markov Decision Process (POMDP) or a restless multi-armed bandit process, to which optimal solutions are often intractable. We show in this paper that the myopic policy, with a simple and robust structure, achieves optimality under certain conditions. This result finds applications in opportunistic communications in fading environment, cognitive radio networks for spectrum overlay, and resource-constrained jamming and anti-jamming.

This paper studies the problem of secure communication over a degraded wiretap channel p(y, z|x) = p(y|x)p(z|y) with secure feedback link of rate Rf, where X is the channel input, and Y and Z are channel outputs observed by the legitimate receiver and the wiretapper respectively. The secrecy capacity is characterized as Cs{Rf) = maxmin{I(X; Y), I(X; Y|Z) + Rf}. p(x)equation. A capacity-achieving coding scheme is presented, in which the receiver securely feeds back fresh randomness with rate Rf, independent of the received channel output. The transmitter then uses the shared randomness as a secret key on top of Wynerpsilas coding scheme for wiretap channel without feedback. Hence, when the receiver has a means of interacting with the transmitter, he should allocate all resources to convey a new key rather than sending back the channel output. For the converse, a recursive argument is used to obtain the single-letter characterization.

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

This paper considers the integration of communication and control with respect to the task of coordinated heading control for a group of N vehicles with the energy efficiency of communications in mind. The heading control employed on each vehicle is a discretization of the well-known Kuramoto model of nonlinearly coupled oscillators over a sequence of logical graphs. Stability for both all-to-all and random one- to-all broadcasts is shown to be dependent on the coupling strength, K, and the time discretization, DeltaT. For desired system performance characteristics, DeltaT imposes a tight deadline by which the state information (M bits) must be propagated through the communication network. Routing optimization with respect to minimizing energy consumption is formulated considering the DeltaT deadline. Due to the tight time deadline, a one-to-all single- hop broadcasting scheme is shown to be more energy efficient for practical choices of M/DeltaT. The proposed modularization is illustrated via a set of simulations where the overall communication energy to reach alignment is optimized.

To implement network coding, users need to coordinate and cooperate with respect to their strategies in terms of duplicating and transmitting side information across specific parts of the network. In unicast applications where users have no inherent interest in providing (or concealing) their information to (or from) any destinations except for their unique one, this assumption becomes critical in the face of users' autonomy. This paper addresses the issue of cooperation in unicast network coding via a game theoretic approach. Implementation of a given network coding scheme induces a network coding game among source-destination pairs (users). In a network with autonomous and rational unicast flows, the equilibrium properties (as well as efficiency) of a network coding scheme is shown to be related to the properties of the corresponding network coding game. In a simple generalization of butterfly networks with two users, we propose a network coding scheme whose capacity achieving operation coincides with users' dominant strategies.

In this correspondence, we consider the problem of delay optimal rate allocation in a (potentially asymmetric) multiaccess channel. The rate feasibility region of such a network is well studied and is shown to be of a polymatroid structure. We consider this problem with unsaturated sources, i.e., jobs arrive at sources at random times and the source has the possibility of being empty. In such a setting, all stable rate allocation policies result in a throughput matched with the average arrival rate. Hence, we are interested in rate allocation policies that minimize expected delay in the system. In this correspondence, we show that a policy of threshold type is optimal in minimizing the average queueing delay. We study the average delay criterion as the limit of an infinite-horizon discounted cost function when the discount factor approaches 1.

This work investigates the asymptotic error performance of outage-limited communications in cooperative wireless relay networks, with fading that is quasi-static, with an information-arrival process that is stochastic and bursty, and with bits that have a strictly limited lifespan. Employing large- deviation techniques, we analyze the probability of bit error where such errors are due to both erroneous decoding as well as due to delay violation. We derive a tradeoff between, on one hand, the optimal negative SNR exponent of the total probability of error, and on the other hand, the ratio of the average bit- arrival rate to the ergodic capacity of the channel. This is for the case of the orthogonal amplify-and-forward protocol, constant system loading, many flows and asymptotically high values of SNR. The tradeoff holds for any delay limitation. As a practical consequence, the tradeoff tells us how to better balance the effects of channel atypicality (outage) and burstiness atypicality, by proper choice of transmission rate and by optimizing the cooperative cluster size, i.e., limiting the cooperation to a specific subset of the cooperative users.

In this correspondence, we consider joint uplink and downlink rate allocations over a multiaccess/broadcast channel pair in a single-cell system. We assume a network of heterogeneous users, where the uplink utility of each user is held as private information and is unknown to the base station. The challenge is to design an optimal rate allocation scheme in the presence of such incomplete information when considering strategic users. Here, we provide an incentive-compatible mechanism that leverages downlink demand to ensure that users truthfully reveal their uplink utilities, enabling the socially optimal uplink rate allocation. In addition, we give numerical results on a kind of efficiency of downlink allocations for two specific uplink multiple-access channels (MACs): information theoretic additive white Gaussian noise (AWGN) , MAC, and code-division multiple-access (CDMA)-based uplink.

Multiple antennas at the transmitters and receivers in a multiple access channel (MAC) can provide simultaneous diversity, spatial multiplexing, and space-division multiple access gains. The fundamental tradeoff in the asymptotically large SNR regime is shown by Tse et al. (2004). On the other hand, MAC scheduling can provide a statistical-multiplexing gain to improve the delay performance as shown by Bertsimas et al. (1998) and Stolyar and Ramanan (2001). In this paper, we formulate and analytically derive bounds on the optimal operating point for MIMO-MAC channel for bursty sources with delay constraints. Our system model brings together the four types of gains: diversity, spatial multiplexing, space-division multiple-access, and statistical-multiplexing gains. Our objective is to minimize the end-to-end performance as defined by the delay bound violation probability as well as the channel decoding error probability. We And the optimal diversity gain and rate region in which the system should operate. As an example, we illustrate our technique and the optimal operating point for the case of a compound Poisson source. In addition, we note an interesting interplay between the intensity of the traffic and resource pooling with regard to both multiple-access and statistical-multiplexing gains.

In this paper, we formulate an optimal rate allocation scheme for uplink and downlink in a single-cell CDMA system. Using concepts from game theory, we show that it is possible to construct a game in which the socially optimal rate allocation arises as a subgame perfect Nash equilibrium. We further show that this equilibrium can be achieved via a distributed algorithm at the uplink using practical signaling mechanisms.

In this paper, the problem of end-to-end weighted max-min fair rate assignment in a two-channel multi-hop CDMA wireless access network is discussed. We show that end-to-end endweighted global max-min fairness (hierarchical as well as flow-based) can be achieved by simple extension of mac-layer fairness. In particular, we show that weighted end-to-end flow-based as well as hierarchical global max-min fairness can be simply insured if and only if weighted mac-layer max-min and weighted transport-layer max-min fair rates are achieved. The same results can easily be shown to be valid for more general wireless networks, which will be briefly discussed in this paper as well. In addition, we discuss a mac-layer algorithm, MAC-α G algorithm, that, with careful choice of parameters, not only provides weighted α-proportional fairness at the mac layer, but also leads to end-to-end weighted global max-min fairness (both flow-based and hierarchical) with an appropriate higher-layer protocol (i.e. weighted transport-layer max-min fair protocol).

We consider a system with a bursty and delay-sensitive data source to be transmitted over a constant-rate MIMO channel with no CSI information at the transmitter. Given the diversity-multiplexing tradeoff region of the MIMO channel, we find the optimal multiplexing rate that optimizes the end-to-end loss probability. Based on the effective bandwidth model of the source, we present an analytical tradeoff between the error probability over the MIMO channel and the probability of delay violation. We illustrate the optimal operating points for i.i.d. sources and Markov-modulated sources and show the relation between sources burstiness, delay bound, and optimal multiplexing rate

In this paper we present a proxy-level scheduler that can significantly improve QoS in heterogeneous wireless sensor networks while at the same time reducing the overall power consumption. Our scheduler is transparent to both applications and MAC in order to take the advantage of the standard off-the-shelf components. The proposed scheduling reduces collisions through a generalized TDMA implementation, and thus improves throughput and QoS, by activating only a subset of stations at a time. Power savings are achieved by scheduling transfer of larger bursts of IP packets followed by longer idle periods during which node's radio can either enter sleep or be turned off. Our simulation and measurement results show significant power savings with an improvement in QoS. On average we get 18% of saturation throughput enhancement for real traffic and 79% of power reduction in a highly loaded network

As the demand for wireless broadband data services grows, it becomes increasingly important to address the issue of optimal resource allocation. Specifically, such allocation should address not only quality of service (QOS) requirements, but continually changing resource demands. This paper examines such optimal resource allocation through nonuniform rate assignment in a CDMA system, using a proportional fair scheme. We also examine distributed algorithms for such a rate assignment, and their performance in dynamic systems.

We consider a wideband CDMA network with arbitrary but known layout of sectors and base-stations, and with variable mobile rate. In this paper, we investigate the issue of rate assignment in a CDMA network. We show that in a broadband wireless data system based on a wideband CDMA technology, there exists an optimal decentralized rate assignment. We show how this method is related to the traditional window or rate based flow control mechanisms widely used in TCP/IP networks.

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

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

We examine high-throughput scheduling algorithms for buffered crossbar switch fabrics containing one buffer per crosspoint. We propose a scheduling system that uses longest queue first (LQF) scheduling for virtual output queues (VOQs) at the inputs and round-robin (RR) scheduling for the crosspoints. It is shown, through fluid model techniques, that this system achieves 100% throughput for input traffic that satisfies the strong law of large numbers and that produces a load /spl les/1/N for any input/output pair of an N/spl times/N switching fabric. Simulations indicate that 100% throughput may be attained for a much larger class of admissible loads.