Multi-objective multi-armed bandit (MO-MAB) problems traditionally aim to achieve Pareto optimality. However, real-world scenarios often involve users with varying preferences across objectives, resulting in a Pareto-optimal arm that may score high for one user but perform quite poorly for another. This highlights the need for customized learning, a factor often overlooked in prior research. To address this, we study a preference-aware MO-MAB framework in the presence of explicit user preference. It shifts the focus from achieving Pareto optimality to further optimizing within the Pareto front under preference-centric customization. To our knowledge, this is the first theoretical study of customized MO-MAB optimization with explicit user preferences. Motivated by practical applications, we explore two scenarios: unknown preference and hidden preference, each presenting unique challenges for algorithm design and analysis. At the core of our algorithms are preference estimation and preference-aware optimization mechanisms to adapt to user preferences effectively. We further develop novel analytical techniques to establish near-optimal regret of the proposed algorithms. Strong empirical performance confirm the effectiveness of our approach.

Large Language Model (LLM) training is increasingly concentrated in homogeneous datacenters, while private data and underutilized GPUs across universities, laboratories, and edge sites remain difficult to use. This extended abstract presents preliminary results from a geo-distributed LLM training prototype that treats networking constraints as first-order design concerns. The prototype connects three heterogeneous GPU sites via cloud-hosted parameter servers, outbound-only gRPC streams, two-stage delta compression (INT8 quantization + Huffman coding, achieving up to 4× payload reduction), and fault-tolerant rejoin. In real deployments, GPT-2 Medium pretraining achieves stable loss reduction and reaches the target loss 15.2% faster in wall-clock time than the best tested baseline; Llama3-1B pretraining remains stable under larger communication pressure; and cross-site latency traces reveal site-dependent WAN spikes of up to 200s. These results motivate adaptive networking support for synchronization, compression, placement, telemetry, and recovery in geo-distributed LLM training.

Partially observable Markov decision processes (POMDPs) are a general framework for sequential decision-making under latent state uncertainty, yet learning in POMDPs is intractable in the worst case. Motivated by sensing and probing constraints in practice, we study how much online state information (OSI) is sufficient to enable efficient learning guarantees. We formalize a model in which the learner can query only partial OSI (POSI) during interaction. We first prove an information-theoretic hardness result showing that, for general POMDPs, achieving an ϵ-optimal policy can require sample complexity that is exponential unless full OSI is available. We then identify two structured subclasses that remain learnable under POSI and propose corresponding algorithms with provably efficient performance guarantees. In particular, we establish regret upper bounds with Õ (√K) dependence on the number of episodesK, together with complementary lower bounds, thereby delineating when POSI suffices for efficient reinforcement learning. Our results highlight a principled separation between intractable and tractable regimes under incomplete online state access and provide new tools for jointly optimizing POSI queries and learning control actions.

The traditional goal in remote tracking of a dynamic source is to keep the current estimate at the destination as close as possible to the true state. However, in domains such as surveillance applications, the destination is also interested in reconstructing the past trajectory of states for further processing. This requires striking a balance between providing current versus past state information so that the destination can optimize the trade-off between the metrics of freshness and reconstruction queue length. In this work, we propose a randomized update policy that decides between head-of-line versus tail-of-line packets in the update queue. As such, our policy combines the strength of Last-Come-First-Serve (LCFS) service discipline (which aims at reducing the age) with the strength of First-Come-First-Serve (FCFS) service discipline (which aims at reducing the reconstruction delay). We evaluate the performance of our proposed policy in terms of its randomization parameter, which can be optimized given the system parameters to achieve a better trade-off.

Continual learning (CL) has garnered significant attention because of its ability to adapt to new tasks that arrive over time. Catastrophic forgetting (of old tasks) has been identified as a major issue in CL, as the model adapts to new tasks. The Mixture-of-Experts (MoE) model has recently been shown to effectively mitigate catastrophic forgetting in CL, by employing a gating network to sparsify and distribute diverse tasks among multiple experts. However, there is a lack of theoretical analysis of MoE and its impact on the learning performance in CL. This paper provides the first theoretical results to characterize the impact of MoE in CL via the lens of overparameterized linear regression tasks. We establish the benefit of MoE over a single expert by proving that the MoE model can diversify its experts to specialize in different tasks, while its router learns to select the right expert for each task and balance the loads across all experts. Our study further suggests an intriguing fact that the MoE in CL needs to terminate the update of the gating network after sufficient training rounds to attain system convergence, which is not needed in the existing MoE studies that do not consider the continual task arrival. Furthermore, we provide explicit expressions for the expected forgetting and overall generalization error to characterize the benefit of MoE in the learning performance in CL. Interestingly, adding more experts requires additional rounds before convergence, which may not enhance the learning performance. Finally, we conduct experiments on both synthetic and real datasets to extend these insights from linear models to deep neural networks (DNNs), which also shed light on the practical algorithm design for MoE in CL.

Multi-Objective Markov Decision Processes (MO-MDPs) are receiving increasing attention, as real-world decision-making problems often involve conflicting objectives that cannot be addressed by a single-objective MDP. The Pareto front identifies the set of policies that cannot be dominated, providing a foundation for finding Pareto optimal solutions that can efficiently adapt to various preferences. However, finding the Pareto front is a highly challenging problem. Most existing methods either (i) rely on traversing the *continuous preference space*, which is impractical and results in approximations that are difficult to evaluate against the true Pareto front, or (ii) focus solely on deterministic Pareto optimal policies, from which there are no known techniques to characterize the full Pareto front. Moreover, finding the structure of the Pareto front itself remains unclear even in the context of dynamic programming, where the MDP is fully known in advance. In this work, we address the challenge of efficiently discovering the Pareto front, involving both deterministic and stochastic Pareto optimal policies. By investigating the geometric structure of the Pareto front in MO-MDPs, we uncover a key property: the Pareto front is on the boundary of a convex polytope whose vertices all correspond to deterministic policies, and neighboring vertices of the Pareto front differ by only one state-action pair of the deterministic policy, almost surely. This insight transforms the global comparison across all policies into a localized search among deterministic policies that differ by only one state-action pair, drastically reducing the complexity of searching for the exact Pareto front. We develop an efficient algorithm that identifies the vertices of the Pareto front by solving a single-objective MDP only once and then traversing the edges of the Pareto front, making it more efficient than existing methods. Furthermore, the entire Pareto front can be found in $V$ iterations, where $V$ represents the number of vertices on the Pareto front. Our empirical studies demonstrate the effectiveness of our theoretical strategy in discovering the Pareto front efficiently.

Accelerated diffusion models hold the potential to significantly enhance the efficiency of standard diffusion processes. Theoretically, these models have been shown to achieve faster convergence rates than the standard $\mathcal O(1/\epsilon^2)$ rate of vanilla diffusion models, where $\epsilon$ denotes the target accuracy. However, current theoretical studies have established the acceleration advantage only for restrictive target distribution classes, such as those with smoothness conditions imposed along the entire sampling path or with bounded support. In this work, we significantly broaden the target distribution classes with a new accelerated stochastic DDPM sampler. In particular, we show that it achieves accelerated performance for three broad distribution classes not considered before. Our first class relies on the smoothness condition posed only to the target density $q_0$, which is far more relaxed than the existing smoothness conditions posed to all $q_t$ along the entire sampling path. Our second class requires only a finite second moment condition, allowing for a much wider class of target distributions than the existing finite-support condition. Our third class is Gaussian mixture, for which our result establishes the first acceleration guarantee. Moreover, among accelerated DDPM type samplers, our results specialized for bounded-support distributions show an improved dependency on the data dimension $d$. Our analysis introduces a novel technique for establishing performance guarantees via constructing a tilting factor representation of the convergence error and utilizing Tweedie's formula to handle Taylor expansion terms. This new analytical framework may be of independent interest.

The denoising diffusion model has recently emerged as a powerful generative technique, capable of transforming noise into meaningful data. While theoretical convergence guarantees for diffusion models are well established when the target distribution aligns with the training distribution, practical scenarios often present mismatches. One common case is in the zero-shot conditional diffusion sampling, where the target conditional distribution is different from the (unconditional) training distribution. These score-mismatched diffusion models remain largely unexplored from a theoretical perspective. In this paper, we present the first performance guarantee with explicit dimensional dependencies for general score-mismatched diffusion samplers, focusing on target distributions with finite second moments. We show that score mismatches result in an asymptotic distributional bias between the target and sampling distributions, proportional to the accumulated mismatch between the target and training distributions. This result can be directly applied to zero-shot conditional samplers for any conditional model, irrespective of measurement noise. Interestingly, the derived convergence upper bound offers useful guidance for designing a novel bias-optimal zero-shot sampler in linear conditional models that minimizes the asymptotic bias. For such bias-optimal samplers, we further establish convergence guarantees with explicit dependencies on dimension and conditioning, applied to several interesting target distributions, including those with bounded support and Gaussian mixtures. Our findings are supported by numerical studies.

Rehearsal-based methods have shown superior performance in addressing catastrophic forgetting in continual learning (CL) by storing and training on a subset of past data alongside new data in current task. While such a concurrent rehearsal strategy is widely used, it remains unclear if this approach is always optimal. Inspired by human learning, where sequentially revisiting tasks helps mitigate forgetting, we explore whether sequential rehearsal can offer greater benefits for CL compared to standard concurrent rehearsal. To address this question, we conduct a theoretical analysis of rehearsal-based CL in overparameterized linear models, comparing two strategies: 1) Concurrent Rehearsal, where past and new data are trained together, and 2) Sequential Rehearsal, where new data is trained first, followed by revisiting past data sequentially. By explicitly characterizing forgetting and generalization error, we show that sequential rehearsal performs better when tasks are less similar. These insights further motivate a novel Hybrid Rehearsal method, which trains similar tasks concurrently and revisits dissimilar tasks sequentially. We characterize its forgetting and generalization performance, and our experiments with deep neural networks further confirm that the hybrid approach outperforms standard concurrent rehearsal. This work provides the first comprehensive theoretical analysis of rehearsal-based CL.

In Reinforcement Learning (RL), tasks with instantaneous hard constraints present significant challenges, particularly when the decision space is non-convex or non-star-convex. This issue is especially relevant in domains like autonomous vehicles and robotics, where constraints such as collision avoidance often take a non-convex form. In this paper, we establish a regret bound of $\tilde{\mathcal{O}}((1 + \tfrac{1}{\tau}) \sqrt{\log(\frac{1}{\tau}) d^3 H^4 K})$, applicable to both star-convex and non-star-convex cases, where $d$ is the feature dimension, $H$ the episode length, $K$ the number of episodes, and $\tau$ the safety threshold. Moreover, the violation of safety constraints is zero with high probability throughout the learning process. A key technical challenge in these settings is bounding the covering number of the value-function class, which is essential for achieving value-aware uniform concentration in model-free function approximation. For the star-convex setting, we develop a novel technique called *Objective–Constraint Decomposition* (OCD) to properly bound the covering number. This result also resolves an error in a previous work on constrained RL. In non-star-convex scenarios, where the covering number can become infinitely large, we propose a two-phase algorithm, Non-Convex Safe Least Squares Value Iteration (NCS-LSVI), which first reduces uncertainty about the safe set by playing a known safe policy. After that, it carefully balances exploration and exploitation to achieve the regret bound. Finally, numerical simulations on an autonomous driving scenario demonstrate the effectiveness of NCS-LSVI.

Reinforcement learning (RL) holds great promise for network control problems, yet its deployment in real-world systems remains limited due to the instability and unpredictability of RL policies during training. To address this challenge, we propose a two-phase conservative RL framework that combines domain expertise from classical network optimization with modern deep RL techniques. Our key idea is to initialize the learning process with a stable base policy, derived from expert knowledge, and then apply conservative fine-tuning under a Kullback–Leibler (KL) divergence constraint to safely explore improved behaviors. We apply this framework to the problem of covert multi-hop routing, where the objective is to optimize data throughput while minimizing detectability by adversaries. In Phase I, we construct a reliable base policy by imitating the back-pressure algorithm, which guarantees throughput-optimal behavior and stable queue dynamics. Phase II fine-tunes this policy to improve covert performance, as measured by the Detection Error Probability (DEP), while preserving training-time stability. Empirical evaluations on a grid network show that our method enables more reliable learning than pure RL. While pure RL (e.g., PPO) can sometimes achieve higher covert performance, it frequently suffers from large queues and collapsed throughput during training. In our experiments, our conservative RL framework reduces the worst-case training-time queue length by over 99% while maintaining comparable covert communication performance.

We consider a real-time monitoring system where a source node (with energy limitations) aims to keep the information status at a destination node as fresh as possible by scheduling status update transmissions over a set of channels. The freshness of information at the destination node is measured in terms of the Age of Information (AoI) metric. In this setting, a natural tradeoff exists between the transmission cost (or equivalently, energy consumption) of the source and the achievable AoI performance at the destination. This tradeoff has been optimized in the existing literature under the assumption of having a complete knowledge of the channel statistics. In this work, we develop online learning-based algorithms with finite-time guarantees that optimize this tradeoff in the practical scenario where the channel statistics are unknown to the scheduler. In particular, when the channel statistics are known, the optimal scheduling policy is first proven to have a threshold-based structure with respect to the value of AoI (i.e., it is optimal to drop updates when the AoI value is below some threshold). This key insight was then utilized to develop the proposed learning algorithms that surprisingly achieve an order-optimal regret (i.e., O(1)) with respect to the time horizon length.

Mobile Robots (MRs), typically equipped with single-antenna radios, face many challenges in maintaining reliable connectivity established by multiple wireless access points (APs). These challenges include the absence of direct line-of-sight (LoS), ineffective beam searching due to the time-varying channel, and interference constraints. This paper presents REMARKABLE, an online learning based adaptive beam selection strategy for robot connectivity that trains kernelized bandit model directly in real-world settings of a factory floor. REMARKABLE employs reconfigurable intelligent surfaces (RISs) with passive reflective elements to create beamforming toward target robots, eliminating the need for multiple APs. We develop a method to create a beamforming codebook, reducing the search space complexity. We also develop a reconfigurable rotational mechanism to expand RIS coverage by rotating its projection plane. To address non-stationary conditions, we adopt the bandit over bandit idea that employs adaptive restarts, allowing the system to forget outdated observations and safely relearn the optimal interference-constrained beam. We show that our approach achieves a dynamic regret and the violation bound of Õ(T3/4B1/4) where T is the total time, and B is the total variation budget which captures the total changes in the environment without even assuming the knowledge of B. Finally, experimental validation with custom-designed RIS hardware and mobile robots demonstrates 46.8% faster beam selection and 94.2% accuracy, outperforming classical methods across diverse mobility settings.

The challenge of classification at the network edge is that due to limited computational resources, the edge must transmit the data to a server for processing. However, the communication constraints at the edge necessitate that these devices compress data before transmission. The question this paper aims to answer is how to efficiently compress and transmit this information in order to achieve timely and accurate edge classification. To that end, we develop scheduling algorithms that optimize age of information (AoI) and classification accuracy. Our analysis reveals that in scenarios with multiple available compression levels, an algorithm that selects at most two compression levels can achieve good theoretical performance guarantees. Numerical results indicate that double-level compression algorithms yield near-optimal performance, suggesting that for many classification tasks, numerous compression levels are unnecessary—only two are sufficient, significantly reducing the storage demands on devices and simplifying the overall system design.

Discrete state space diffusion models have shown significant advantages in applications involving discrete data, such as text and image generation. It has also been observed that their performance is highly sensitive to the choice of rate matrices, particularly between uniform and absorbing rate matrices. While empirical results suggest that absorbing rate matrices often yield better generation quality compared to uniform rate matrices, existing theoretical works have largely focused on the uniform rate matrices case. Notably, convergence guarantees and error analyses for absorbing diffusion models are still missing. In this work, we provide the first finite-time error bounds and convergence rate analysis for discrete diffusion models using absorbing rate matrices. We begin by deriving an upper bound on the KL divergence of the forward process, introducing a surrogate initialization distribution to address the challenge posed by the absorbing stationary distribution, which is a singleton and causes the KL divergence to be ill-defined. We then establish the first convergence guarantees for both the $\tau$-leaping and uniformization samplers under absorbing rate matrices, demonstrating improved rates over their counterparts using uniform rate matrices. Furthermore, under suitable assumptions, we provide convergence guarantees without early stopping. Our analysis introduces several new technical tools to address challenges unique to absorbing rate matrices. These include a Jensen-type argument for bounding forward process convergence, novel techniques for bounding absorbing score functions, and a non-divergent upper bound on the score near initialization that removes the need of early-stopping.

Discrete diffusion models have recently gained significant prominence in applications involving natural language and graph data. A key factor influencing their effectiveness is the efficiency of discretized samplers. Among these, $\tau$-leaping samplers have become particularly popular due to their theoretical and empirical success. However, existing theoretical analyses of $\tau$-leaping often rely on somewhat restrictive and difficult-to-verify regularity assumptions, and their convergence bounds contain quadratic dependence on the vocabulary size. In this work, we introduce a new analytical approach for discrete diffusion models that removes the need for such assumptions. For the standard $\tau$-leaping method, we establish convergence guarantees in KL divergence that scale linearly with vocabulary size, improving upon prior results with quadratic dependence. Our approach is also more broadly applicable: it provides the first convergence guarantees for other widely used samplers, including the Euler method and Tweedie $\tau$-leaping. Central to our approach is a novel technique based on differential inequalities, offering a more flexible alternative to the traditional Girsanov change-of-measure methods. This technique may also be of independent interest for the analysis of other stochastic processes.

Join-the-shortest queue (JSQ) and its variants have often been used in solving load balancing problems. The aim of such policies is to minimize the average system occupation, e.g., the customer's system time. In this paper, we extend the load balancing setting to include constraints that may be imposed, e.g., due to the communication network. First, we cast the problem in the framework of constrained MDPs: this permits us to address both action-dependent constraints, such as, e.g, bandwidth limitation, and state-dependent constraints, such as, e.g., minimum queue utilization. Hence, unlike the state-of-the-art approaches in load balancing, we derive new policies that satisfy the constraints while minimizing system occupancy. Extensive numerical simulations have evaluated their performance under various system settings.

The integration of the Internet of Things (IoT) and modern Artificial Intelligence (AI) has given rise to a new paradigm known as the Artificial Intelligence of Things (AIoT). In this survey, we provide a systematic and comprehensive review of AIoT research. We examine AIoT literature related to sensing, computing, and networking & communication, which form the three key components of AIoT. In addition to advancements in these areas, we review domain-specific AIoT systems that are designed for various important application domains. We have also created an accompanying GitHub repository, where we compile the papers included in this survey: https://github.com/AIoT-MLSys-Lab/AIoT-Survey. This repository will be actively maintained and updated with new research as it becomes available. As both IoT and AI become increasingly critical to our society, we believe that AIoT is emerging as an essential research field at the intersection of IoT and modern AI. It is our hope that this survey will serve as a valuable resource for those engaged in AIoT research and act as a catalyst for future explorations to bridge gaps and drive advancements in this exciting field.

We study the constrained Markov decision processes (CMDPs), in which an agent aims to maximize the expected cumulative reward subject to a constraint on the expected total value of a utility function. Existing approaches have primarily focused on \emph{soft} constraint violation, which allows compensation across episodes, making it easier to satisfy the constraints. In contrast, we consider a stronger \emph{hard} constraint violation metric, where only positive constraint violations are accumulated. Our main result is the development of the \emph{first model-free}, \emph{simulator-free} algorithm that achieves a sub-linear regret and a sub-linear hard constraint violation simultaneously, even in \emph{large-scale} systems. In particular, we show that $\tilde{\mathcal{O}}(\sqrt{d^3H^4K})$ regret and $\tilde{\mathcal{O}}(\sqrt{d^3H^4K})$ hard constraint violation bounds can be achieved, where $K$ is the number of episodes, $d$ is the dimension of the feature mapping, $H$ is the length of the episode. Our results are achieved via novel adaptations of the primal-dual LSVI-UCB algorithm, i.e., it searches for the dual variable that balances between regret and constraint violation within every episode, rather than updating it at the end of each episode. This turns out to be crucial for our theoretical guarantees when dealing with hard constraint violations.

Fairness plays a crucial role in various multi-agent systems (e.g., communication networks, financial markets, etc.). Many multi-agent dynamical interactions can be cast as Markov Decision Processes (MDPs). While existing research has focused on studying fairness in known environments, the exploration of fairness in such systems for unknown environments remains open. In this paper, we propose a Reinforcement Learning (RL) approach to achieve fairness in multi-agent finite-horizon episodic MDPs. Instead of maximizing the sum of individual agents' value functions, we introduce a fairness function that ensures equitable rewards across agents. Since the classical Bellman's equation does not hold when the sum of individual value functions is not maximized, we cannot use traditional approaches. Instead, in order to explore, we maintain a confidence bound of the unknown environment and then propose an online convex optimization based approach to obtain a policy constrained to this confidence region. We show that such an approach achieves sub-linear regret in terms of the number of episodes. Additionally, we provide a probably approximately correct (PAC) guarantee based on the obtained regret bound. We also propose an offline RL algorithm and bound the optimality gap with respect to the optimal fair solution. To mitigate computational complexity, we introduce a policy-gradient type method for the fair objective. Simulation experiments also demonstrate the efficacy of our approach.

Reinforcement learning often needs to deal with the exponential growth of states and actions when exploring optimal control in high-dimensional spaces (often known as the curse of dimensionality). In this work, we address this issue by learning the inherent structure of action-wise similar MDP to appropriately balance the performance degradation versus sample/computational complexity. In particular, we partition the action spaces into multiple groups based on the similarity in transition distribution and reward function, and build a linear decomposition model to capture the difference between the intra-group transition kernel and the intra-group rewards. Both our theoretical analysis and experiments reveal a *surprising and counter-intuitive result*: while a more refined grouping strategy can reduce the approximation error caused by treating actions in the same group as identical, it also leads to increased estimation error when the size of samples or the computation resources is limited. This finding highlights the grouping strategy as a new degree of freedom that can be optimized to minimize the overall performance loss. To address this issue, we formulate a general optimization problem for determining the optimal grouping strategy, which strikes a balance between performance loss and sample/computational complexity. We further propose a computationally efficient method for selecting a nearly-optimal grouping strategy, which maintains its computational complexity independent of the size of the action space.

Federated Learning (FL) has gained significant popularity due to its effectiveness in training machine learning models across diverse sites without requiring direct data sharing. While various algorithms along with their optimization analyses have shown that FL with local updates is a communication-efficient distributed learning framework, the generalization performance of FL with local updates has received comparatively less attention. This lack of investigation can be attributed to the complex interplay between data heterogeneity and infrequent communication due to the local updates within the FL framework. This motivates us to investigate a fundamental question in FL: Can we quantify the impact of data heterogeneity and local updates on the generalization performance for FL as the learning process evolves? To this end, we conduct a comprehensive theoretical study of FL's generalization performance using a linear model as the first step, where the data heterogeneity is considered for both the stationary and online/non-stationary cases. By providing closed-form expressions of the model error, we rigorously quantify the impact of the number of the local updates (denoted as K) under three settings (K = 1, K < ∞, and K = ∞) and show how the generalization performance evolves with the number of rounds t. Our investigation also provides a comprehensive understanding of how different configurations (including the number of model parameters p and the number of training samples n) contribute to the overall generalization performance, thus shedding new insights (such as benign overfitting) for implementing FL over networks.

The widespread adoption of low-cost resource-constrained edge devices and high-performance expensive servers necessitates shifting the complexity burden from edge devices to servers. However, in many applications such as image classification, it is often impractical and communication expensive to transmit full information without any form of compression. To address this issue, this paper introduces a neural network (NN)-based compression technique tailored for resource-constrained edge devices for classification at the network edge. The core idea involves simultaneously training a shallow neural network to-be-implemented by the devices and a deep neural network to-be-implemented by the server. To adapt to the time-varying channel conditions, the compression algorithm at the device side must be able to handle multiple output dimensions. To address this issue, we develop two multi-dimensional compression strategies: the multiple codebook approach, using separate NNs for various dimensions, and the single codebook approach, utilizing one NN for all dimensions. The single codebook approach substantially reduces the storage demands on the device, offering a viable solution for low-cost edge devices. Our analysis offers a theoretical performance guarantee, highlighting that the accuracy of the single codebook approach is comparable to that of the multiple codebook strategy. Through empirical evaluations on real-world datasets, we demonstrate that the single codebook approach achieves near-equivalent performance to the accuracy multiple codebook alternative.

We investigate linear bandits in a network setting in the presence of side-observations across nodes in order to design recommendation algorithms for users connected via social networks. Users in social networks respond to their friends’ activity and, hence, provide information about each other’s preferences. In our model, when a learning algorithm recommends an article to a user, not only does it observe her response (e.g., an ad click) but also the side-observations, i.e., the response of her neighbors if they were presented with the same article. We model these observation dependencies by a graph$\mathcal {G}$in which nodes correspond to users and edges to social links. We derive a problem/instance-dependent lower-bound on the regret of any consistent algorithm. We propose an optimization-based data-driven learning algorithm that utilizes the structure of$\mathcal {G}$in order to make recommendations to users and show that it is asymptotically optimal, in the sense that its regret matches the lower-bound as the number of rounds$T\to \infty $. We show that this asymptotically optimal regret is upper-bounded as$O\left ({{|\chi (\mathcal {G})|\log T}}\right)$, where$|\chi (\mathcal {G})|$is the domination number of$\mathcal {G}$. In contrast, a naive application of the existing learning algorithms results in$O\left ({{N\log T}}\right)$regret, where N is the number of users.

The ever-growing end user data demands, and the reductions in memory costs are fueling edge-caching deployments. Caching at the edge is substantially different from that at the core and needs to consider the nature of individualized data demands. For example, an individual user may not be interested in requesting the same data item again, if it has recently requested it. Such individualized dynamics are not apparent in the aggregated data requests at the core and have not been considered in popularity-driven caching designs for the core. Hence, these traditional caching policies could induce significant inefficiencies when applied at the edges. To address this issue, we develop new edge caching policies optimized for the individualized demands that also leverage overhearing opportunities at the wireless edge. With the objective of maximizing the hit ratio, the proposed policies will actively evict the data items that are not likely to be requested in the near future, and strategically bring them back into the cache via overhearing when they become popular again. Both theoretical analysis and numerical simulations demonstrate that the proposed edge caching policies could outperform the popularity-driven policies that are optimal at the core.

Edge caching has been widely implemented to efficiently serve data requests from end users. Numerous edge caching policies have been proposed to adaptively update the cache contents based on various statistics. One critical statistic is the miss cost, which could measure the latency or the bandwidth/energy consumption to resolve the cache miss. Existing caching policies typically assume that the miss cost for each data item is fixed and known. However, in real systems, they could be random with unknown statistics. A promising approach would be to use online learning to estimate the unknown statistics of these random costs, and make caching decisions adaptively. Unfortunately, conventional learning techniques cannot be directly applied, because the caching problem has additional cache capacity and cache update constraints that are not covered in traditional learning settings. In this work, we resolve these issues by developing a novel edge caching policy that learns uncertain miss costs efficiently, and is shown to be asymptotically optimal. We first derive an asymptotic lower bound on the achievable regret. We then design a Kullback-Leibler lower confidence bound (KL-LCB) based edge caching policy, which adaptively learns the random miss costs by following the “optimism in the face of uncertainty” principle. By employing a novel analysis that accounts for the new constraints and the dynamics of the setting, we prove that the regret of the proposed policy matches the regret lower bound, thus showing asymptotic optimality. Further, via numerical experiments we demonstrate the performance improvements of our policy over natural benchmarks.

We study model-free reinforcement learning (RL) algorithms in episodic non-stationary constrained Markov decision processes (CMDPs), in which an agent aims to maximize the expected cumulative reward subject to a cumulative constraint on the expected utility (cost). In the non-stationary environment, the reward, utility functions, and the transition kernels can vary arbitrarily over time as long as the cumulative variations do not exceed certain variation budgets. We propose the first model-free, simulator-free RL algorithms with sublinear regret and zero constraint violation for non-stationary CMDPs in both tabular and linear function approximation settings with provable performance guarantees. Our results on regret bound and constraint violation for the tabular case match the corresponding best results for stationary CMDPs when the total budget is known. Additionally, we present a general framework for addressing with the well-known challenges associated with analyzing non-stationary CMDPs, without requiring prior knowledge of the variation budget. We apply the approach for both tabular and linear approximation settings.

In this paper, we consider a task offloading problem in a multi-access edge computing (MEC) network, in which edge users can either use their local processing unit to compute their tasks or offload their tasks to a nearby edge server through multiple communication channels each with different characteristics. The main objective is to maximize the energy efficiency of the edge users while meeting computing tasks deadlines. In the multi-user multi-channel offloading scenario, users are distributed with partial observations of the system states. We formulate this problem as a stochastic optimization problem and leverage contextual neural multi-armed bandit models to develop an energy-efficient deadline-aware solution, dubbed E2DA. The proposed E2DA framework only relies on partial state information (i.e., computation task features) to make offloading decisions. Through extensive numerical analysis, we demonstrate that the E2DA algorithm can efficiently learn an offloading policy and achieve close-to-optimal performance in comparison with several baseline policies that optimize energy consumption and/or response time. Furthermore, we provide a comprehensive set of results on the MEC system performance for various applications such as augmented reality (AR) and virtual reality (VR).

Continual learning (CL), which aims to learn a sequence of tasks, has attracted significant recent attention. However, most work has focused on the experimental performance of CL, and theoretical studies of CL are still limited. In particular, there is a lack of understanding on what factors are important and how they affect "catastrophic forgetting" and generalization performance. To fill this gap, our theoretical analysis, under overparameterized linear models, provides the first-known explicit form of the expected forgetting and generalization error for a general CL setup with an arbitrary number of tasks. Further analysis of such a key result yields a number of theoretical explanations about how overparameterization, task similarity, and task ordering affect both forgetting and generalization error of CL. More interestingly, by conducting experiments on real datasets using deep neural networks (DNNs), we show that some of these insights even go beyond the linear models and can be carried over to practical setups. In particular, we use concrete examples to show that our results not only explain some interesting empirical observations in recent studies, but also motivate better practical algorithm designs of CL.

In many applications of Reinforcement Learning (RL), it is critically important that the algorithm performs safely, such that instantaneous hard constraints are satisfied at each step, and unsafe states and actions are avoided. However, existing algorithms for ``safe'' RL are often designed under constraints that either require expected cumulative costs to be bounded or assume all states are safe. Thus, such algorithms could violate instantaneous hard constraints and traverse unsafe states (and actions) in practice. Hence, in this paper, we develop the first near-optimal safe RL algorithm for episodic Markov Decision Processes with unsafe states and actions under instantaneous hard constraints and the linear mixture model. It achieves a regret $\tilde{O}(\frac{d H^3 \sqrt{d K}}{\Delta_c})$ that nearly matches the state-of-the-art regret in the setting with only unsafe actions and that in the unconstrained setting, and is safe at each step, where $d$ is the feature-mapping dimension, $K$ is the number of episodes, $H$ is the episode length, and $\Delta_c$ is a safety-related parameter. We also provide a lower bound $\tilde{\Omega}(\max\{d H \sqrt{K}, \frac{H}{\Delta_c^2}\})$, which indicates that the dependency on $\Delta_c$ is necessary. Further, both our algorithm design and regret analysis involve several novel ideas, which may be of independent interest.

Decentralized bilevel optimization has received increasing attention recently due to its foundational role in many emerging multi-agent learning paradigms (e.g., multi-agent meta-learning and multi-agent reinforcement learning) over peer-to-peer edge networks. However, to work with the limited computation and communication capabilities of edge networks, a major challenge in developing decentralized bilevel optimization techniques is to lower sample and communication complexities. This motivates us to develop a new decentralized bilevel optimization called DIAMOND (decentralized single-timescale stochastic approximation with momentum and gradient-tracking). The contributions of this paper are as follows: i) our DIAMOND algorithm adopts a single-loop structure rather than following the natural double-loop structure of bilevel optimization, which offers low computation and implementation complexity; ii) compared to existing approaches, the DIAMOND algorithm does not require any full gradient evaluations, which further reduces both sample and computational complexities; iii) through a careful integration of momentum information and gradient tracking techniques, we show that the DIAMOND algorithm enjoys $\mathcal{O}\left( {{ \in ^{ - 3/2}}} \right)$ in sample and communication complexities for achieving an ϵ-stationary solution, both of which are independent of the dataset sizes and significantly outperform existing works. Extensive experiments also verify our theoretical findings.

In this paper, we consider a status update system, where an access point collects measurements from multiple sensors that monitor a common physical process, fuses them, and transmits the aggregated sample to the destination over an erasure channel. Under a typical information fusion scheme, the distortion of the fused sample is inversely proportional to the number of measurements received. Our goal is to minimize the long-term average age while satisfying the average energy and general age-based distortion requirements. Specifically, we focus on the setting in which the distortion requirement is stricter when the age of the update is older. We show that the optimal policy is a mixture of two stationary, deterministic, threshold-based policies, each of which is optimal for a parameterized problem that aims to minimize the weighted sum of the age and energy under the distortion constraint. We then derive analytically the associated optimal average age-cost function and characterize its performance in the large threshold regime, the results of which shed critical insights on the tradeoff among age, energy, and the distortion of the samples. We have also developed a closed-form solution for the special case when the distortion requirement is independent of the age, arguably the most important setting for practical applications.

Bilevel optimization has become a powerful tool in a wide variety of machine learning problems. However, the current nonconvex bilevel optimization considers an offline dataset and static functions, which may not work well in emerging online applications with streaming data and time-varying functions. In this work, we study online bilevel optimization (OBO) where the functions can be time-varying and the agent continuously updates the decisions with online streaming data. To deal with the function variations and the unavailability of the true hypergradients in OBO, we propose a single-loop online bilevel optimizer with window averaging (SOBOW), which updates the outer-level decision based on a window average of the most recent hypergradient estimations stored in the memory. Compared to existing algorithms, SOBOW is computationally efficient and does not need to know previous functions. To handle the unique technical difficulties rooted in single-loop update and function variations for OBO, we develop a novel analytical technique that disentangles the complex couplings between decision variables, and carefully controls the hypergradient estimation error. We show that SOBOW can achieve a sublinear bilevel local regret under mild conditions. Extensive experiments across multiple domains corroborate the effectiveness of SOBOW.

We consider the problem of minimizing the age of information when a source can transmit status updates over two heterogeneous channels. Our work is motivated by recent developments in 5 G mmWave technology, where transmissions may occur over an unreliable but fast (e.g., mmWave) channel or a slow reliable (e.g., sub-6 GHz) channel. The unreliable channel is modeled as a time-correlated Gilbert-Elliot channel at a high rate when the channel is in the “ON” state. The reliable channel provides a deterministic but lower data rate. The scheduling strategy determines the channel to be used for transmission in each time slot, aiming to minimize the time-average age of information (AoI). The optimal scheduling problem is formulated as a Markov Decision Process (MDP), which is challenging to solve because super-modularity does not hold in a part of the state space. We address this challenge and show that a multi-dimensional threshold-type scheduling policy is optimal for minimizing the age. By exploiting the structure of the MDP and analyzing the discrete time Markov chains (DTMCs) of the threshold-type policy, we devise a low-complexity bisection algorithm to compute the optimal thresholds. We compare different scheduling policies using numerical simulations.

In this paper, we consider transmission scheduling in a status update system, where updates are generated periodically and transmitted over a Gilbert-Elliott fading channel. The goal is to minimize the long-run average age of information (AoI) under a long-run average energy constraint. We consider two practical cases to obtain channel state information (CSI): (i) without channel sensing and (ii) with delayed channel sensing. For (i), CSI is revealed by the feedback (ACK/NACK) of a transmission, but when no transmission occurs, CSI is not revealed. Thus, we have to balance tradeoffs across energy, AoI, channel exploration, and channel exploitation. The problem is formulated as a constrained partially observable Markov decision process (POMDP). We show that the optimal policy is a randomized mixture of no more than two stationary deterministic policies each of which is of a threshold-type in the belief on the channel. For (ii), (delayed) CSI is available via channel sensing. Then, the tradeoff is only between the AoI and energy. The problem is formulated as a constrained MDP. The optimal policy is shown to have a similar structure as in (i) but with an AoI associated threshold. With these, we develop an optimal structure-aware algorithm for each case.

Millimeter wave (mmWave) communication has the potential to achieve very high data rates but is highly vulnerable to blockage. In this paper, we provision an integrated mmWavesub-6 GHz architecture to combat blockage and intermittent connectivity of the mmWave communications. To this end, we model the mmWave channel as a two-state Markov channel and investigate the problem of scheduling packets across the mmWave and sub-6 GHz interfaces such that the long-term average delay of system is minimized. We prove that the optimal policy is of a threshold-type with state-dependent thresholds, i.e., packets should always be routed to the mmWave interface as long as the number of packets in the system is smaller than the state-dependent threshold. Numerical results demonstrate that under heavy traffic, integrating sub-6 GHz with mmWave can reduce the average delay by over 70%. Moreover, considering the difficulty of tracking the mmWave channel state in practice, we develop heuristics of substituting a single fixed threshold (state-independent) for two state-dependent thresholds. Our simulation results indicate that the replacement only incurs a slight increase in average delay. Moreover, when system parameters are not known, we propose a certainty-equivalence threshold-based learning algorithm, and provide an upper bound on its regret.

In this paper, we aim to design an optimal sampler for a system in which fresh samples of a signal (source) are sent through an unreliable channel to a remote estimator, and acknowledgments are sent back over a feedback channel. Both the forward and feedback channels could have random transmission times due to time varying channel conditions. Motivated by distributed sensing, the estimator can estimate the real-time value of the source signal by combining the signal samples received through the channel and the noisy signal observations collected from a local sensor. We prove that the estimation error is a non-decreasing function of the Age of Information (AoI) for the received signal samples and design an optimal sampling strategy that minimizes the long-term average estimation error subject to a sampling rate constraint. The sampling strategy is also optimal for minimizing the long-term average of general non-decreasing functions of the AoI. The optimal sampler design follows a randomized threshold strategy: If the last transmission was successful, the source waits until the expected estimation error upon delivery exceeds a threshold and then sends out a new sample. If the last transmission fails, the source immediately sends out a new sample without waiting. The threshold is the root of a fixed-point equation and can be solved with low complexity (e.g., by bisection search). The optimal sampling strategy holds for general transmission time distributions of the forward and feedback channels. Numerical simulations are provided to compare different sampling policies.

In this paper, we consider the Gaussian process (GP) bandit optimization problem in a non-stationary environment. To capture external changes, the black-box function is allowed to be time-varying within a reproducing kernel Hilbert space (RKHS). To this end, we develop WGP-UCB, a novel UCB-type algorithm based on weighted Gaussian process regression. A key challenge is how to cope with infinite-dimensional feature maps. To that end, we leverage kernel approximation techniques to prove a sublinear regret bound, which is the first (frequentist) sublinear regret guarantee on weighted time-varying bandits with general nonlinear rewards. This result generalizes both non-stationary linear bandits and standard GP-UCB algorithms. Further, a novel concentration inequality is achieved for weighted Gaussian process regression with general weights. We also provide universal upper bounds and weight-dependent upper bounds for weighted maximum information gains. These results are of independent interest for applications such as news ranking and adaptive pricing, where weights can be adopted to capture the importance or quality of data. Finally, we conduct experiments to highlight the favorable gains of the proposed algorithm in many cases when compared to existing methods.

In this paper, we study a sampling problem in which fresh samples of a signal (source) are sent through an unreliable channel to a remote estimator, and acknowledgments are sent back over a feedback channel. Both the forward and feedback channels are subject to random transmission times. Motivated by distributed sensing, the estimator can estimate the real-time value of the source signal by combining the signal samples received through the channel and noisy signal observations collected from a local sensor. We prove that the estimation error is a non-decreasing function of the Age of Information (AoI) for received signal samples and design an optimal sampling strategy that minimizes the long-term average estimation error. The optimal sampler design follows a threshold strategy: If the last transmission was successful, the source waits until the expected estimation error upon delivery exceeds a threshold and then sends out a new sample. If the last transmission fails, the source immediately sends out a new sample without waiting. The threshold is the unique root of a fixed-point equation and can be solved with low complexity (e.g., by bisection search). In addition, the proposed sampling strategy is also optimal for minimizing the long-term average of general non-decreasing functions of the AoI. Its optimality holds for general transmission time distributions of the forward and feedback channels.

We study the constrained reinforcement learning problem, in which an agent aims to maximize the expected cumulative reward subject to a constraint on the expected total value of a utility function. In contrast to existing model-based approaches or model-free methods accompanied with a `simulator’, we aim to develop the first \emph{model-free}, \emph{simulator-free} algorithm that achieves a sublinear regret and a sublinear constraint violation even in \emph{large-scale} systems. To this end, we consider the episodic constrained Markov decision processes with linear function approximation, where the transition dynamics and the reward function can be represented as a linear function of some known feature mapping. We show that $\tilde{\mathcal{O}}(\sqrt{d^3H^3T})$ regret and $\tilde{\mathcal{O}}(\sqrt{d^3H^3T})$ constraint violation bounds can be achieved, where $d$ is the dimension of the feature mapping, $H$ is the length of the episode, and $T$ is the total number of steps. Our bounds are attained without explicitly estimating the unknown transition model or requiring a simulator, and they depend on the state space only through the dimension of the feature mapping. Hence our bounds hold even when the number of states goes to infinity. Our main results are achieved via novel adaptations of the standard LSVI-UCB algorithms. In particular, we first introduce primal-dual optimization into the LSVI-UCB algorithm to balance between regret and constraint violation. More importantly, we replace the standard greedy selection with respect to the state-action function with a soft-max policy. This turns out to be key in establishing uniform concentration (a critical step for provably efficient model-free exploration) for the constrained case via its approximation-smoothness trade-off. Finally, we also show that one can achieve an even zero constraint violation for large enough $T$ by trading the regret a little bit but still maintaining the same order with respect to $T$.

In this paper, we study the generalization performance of overparameterized 3-layer NTK models. We show that, for a specific set of ground-truth functions (which we refer to as the "learnable set"), the test error of the overfitted 3-layer NTK is upper bounded by an expression that decreases with the number of neurons of the two hidden layers. Different from 2-layer NTK where there exists only one hidden-layer, the 3-layer NTK involves interactions between two hidden-layers. Our upper bound reveals that, between the two hidden-layers, the test error descends faster with respect to the number of neurons in the second hidden-layer (the one closer to the output) than with respect to that in the first hidden-layer (the one closer to the input). We also show that the learnable set of 3-layer NTK without bias is no smaller than that of 2-layer NTK models with various choices of bias in the neurons. However, in terms of the actual generalization performance, our results suggest that 3-layer NTK is much less sensitive to the choices of bias than 2-layer NTK, especially when the input dimension is large.

To fully utilize the abundant spectrum resources in millimeter wave (mmWave), Beam Alignment (BA) is necessary for large antenna arrays to achieve large array gains. In practical dynamic wireless environments, channel modeling is challenging due to time-varying and multipath effects. In this paper, we formulate the beam alignment problem as a nonstationary online learning problem with the objective to maximize the received signal strength under interference constraint. In particular, we employ the non-stationary kernelized bandit to leverage the correlation among beams and model the complex beamforming and multipath channel functions. Furthermore, to mitigate interference to other user equipment, we leverage the primal-dual method to design a constrained UCB-type kernelized bandit algorithm. Our theoretical analysis indicates that the proposed algorithm can adaptively adjust the beam in time-varying environments, such that both the cumulative regret of the received signal and constraint violations have sublinear bounds with respect to time. This result is of independent interest for applications such as adaptive pricing and news ranking. In addition, the algorithm assumes the channel is a black-box function and does not require any prior knowledge for dynamic channel modeling, and thus is applicable in a variety of scenarios. We further show that if the information about the channel variation is known, the algorithm will have better theoretical guarantees and performance. Finally, we conduct simulations to highlight the effectiveness of the proposed algorithm.

Edge caching has been widely implemented to efficiently serve data requests from end users. Numerous edge caching policies have been proposed to adaptively update cache content based on various statistics including data popularities and miss costs. Nevertheless, these policies typically assume that the miss cost for each data item is known, which is not true in real systems. A promising approach would be to use online learning to estimate these unknown miss costs. However, existing techniques cannot be directly applied, because the caching problem has additional cache capacity and cache update constraints that are not covered in traditional learning settings. In this work, we resolve these issues by developing a novel edge caching policy that learns uncertainty miss costs efficiently, and is shown to be asymptotically optimal. We first derive an asymptotic lower bound on the achievable regret. We then design a Kullback-Leibler lower confidence bound (KL-LCB) based edge caching policy, which adaptively learns the random miss costs by following the “optimism in the face of uncertainty” principle. By employing a novel analysis that accounts for the new constraints and the dynamics of the setting, we prove that the regret of the proposed policy matches the regret lower bound, thus showing asymptotic optimality. Further, via numerical experiments we demonstrate the performance improvements of our policy over natural benchmarks.

In this paper, we study the generalization performance of min $\ell_2$-norm overfitting solutions for the neural tangent kernel (NTK) model of a two-layer neural network with ReLU activation that has no bias term. We show that, depending on the ground-truth function, the test error of overfitted NTK models exhibits characteristics that are different from the "double-descent" of other overparameterized linear models with simple Fourier or Gaussian features. Specifically, for a class of learnable functions, we provide a new upper bound of the generalization error that approaches a small limiting value, even when the number of neurons $p$ approaches infinity. This limiting value further decreases with the number of training samples $n$. For functions outside of this class, we provide a lower bound on the generalization error that does not diminish to zero even when $n$ and $p$ are both large.

In this paper we study the problem of regret minimization in reinforcement learning (RL) under differential privacy constraints. This work is motivated by the wide range of RL applications for providing personalized service, where privacy concerns are becoming paramount. In contrast to previous works, we take the first step towards non-tabular RL settings, while providing a rigorous privacy guarantee. In particular, we consider the adaptive control of differentially private linear quadratic (LQ) systems. We develop the first private RL algorithm, Private-OFU-RL which is able to attain a sub-linear regret while guaranteeing privacy protection. More importantly, the additional cost due to privacy is only on the order of$\frac{\ln(1/\delta)^{1/4}}{\varepsilon^{1/2}}$given privacy parameters$\varepsilon, \delta > 0$. Through this process, we also provide a general procedure for adaptive control of LQ systems under changing regularizers, which not only generalizes previous non-private controls, but also serves as the basis for general private controls.

In this paper, we consider transmission scheduling in a status update system, where updates are generated periodically and transmitted over a Gilbert-Elliott fading channel. The goal is to minimize the long-run average age of information (AoI) at the destination under an average energy constraint. The channel state is revealed by the feedback (Ack/Nack) of a transmission; while it remains unknown if there is no transmission. Thus, we have to design a scheduling policy that balances tradeoffs across energy, AoI, channel exploration, and channel exploitation. The problem is formulated as a constrained partially observable Markov decision process problem (POMDP). We show that the optimal policy is a randomized mixture of no more than two stationary deterministic policies each of which is of a threshold-type in the belief on the channel. We propose a finite-state approximation for our infinite-state belief MDP and show convergence. Based on the theoretical insights gained from studying this problem, we develop an optimal algorithm using the structure of the problem.

Seamless Internet access under extreme user mobility is highly demanded on high-speed trains and vehicles. However, existing mobile networks (e.g., 4G LTE and 5G NR) cannot reliably satisfy this demand, with a 5.5%-12.6% handover failure ratio at 200–350 km/h. A root cause is that, the 4G/5G handovers have to balance the exploration of more measurements for satisfactory handover and the exploitation for timely handover before the fast-moving user leaves the coverage.We design BaTT, an online learning solution for reliable handovers in extreme mobility. BaTT decomposes the explorationexploitation tradeoff into two multi-armed bandit problems. It uses ϵ-binary-search to optimize the threshold of a serving cell’s signal strength to initiate the handover with $\mathcal{O}(\log J\log T)$ regrets. It further adopts opportunistic Thompson sampling to optimize the sequence of target cells measured for reliable handovers. BaTT can be implemented using the recent Open Radio Access Network (O-RAN) framework in operational 4G LTE and 5G NR. Our evaluations over a dataset from operational LTE networks on the Chinese high-speed rails show a 29.1% handover failure reduction at the speed of 200-350 km/h.

In this paper, we study the problem of minimizing the age of information when a source can transmit status updates over two heterogeneous channels. Our work is motivated by recent developments in 5G mmWave technology, where transmissions may occur over an unreliable but fast (e.g., mmWave) channel or a slow reliable (e.g., sub-6GHz) channel. The unreliable channel is modeled as a time-correlated Gilbert-Elliot channel, where information can be transmitted at a high rate when the channel is in the "ON" state. The reliable channel provides a deterministic but lower data rate. The scheduling strategy determines the channel to be used for transmission with the aim to minimize the time-average age of information (AoI). The optimal scheduling problem is formulated as a Markov Decision Process (MDP), which in our setting poses some significant challenges because e.g., supermodularity does not hold for part of the state space. We show that there exists a multi-dimensional threshold-based scheduling policy that is optimal for minimizing the age. A low-complexity bisection algorithm is further devised to compute the optimal thresholds. Numerical simulations are provided to compare different scheduling policies.

In this paper, we consider a status update system, in which update packets are sent to the destination via a wireless medium that allows for multiple rates, where a higher rate also naturally corresponds to a higher error probability. The data freshness is measured using age of information, which is defined as the age of the recent update at the destination. A packet that is transmitted with a higher rate, will encounter a shorter delay and a higher error probability. Thus, the choice of the transmission rate affects the age at the destination. In this paper, we design a low-complexity scheduler that selects between two different transmission rate and error probability pairs to be used at each transmission epoch. This problem can be cast as a Markov Decision Process. We show that there exists a threshold-type policy that is age-optimal. More importantly, we show that the objective function is quasi-convex or non-decreasing in the threshold, based on the system parameters values. This enables us to devise a low-complexity algorithm to minimize the age. These results reveal an interesting phenomenon: While choosing the rate with minimum mean delay is delay-optimal, this does not necessarily minimize the age.

We study the sample complexity (i.e., the number of comparisons needed) bounds for actively ranking a set of $n$ items from multi-wise comparisons. Here, a multi-wise comparison takes $m$ items as input and returns a (noisy) result about the best item (the winner feedback) or the order of these items (the full-ranking feedback). We consider two basic ranking problems: top-$k$ items selection and full ranking. Unlike previous works that study ranking from multi-wise comparisons, in this paper, we do not require any parametric model or assumption and work on the fundamental setting where each comparison returns the correct result with probability $1$ or a certain probability larger than $\frac{1}{2}$. This paper helps understand whether and to what degree utilizing multi-wise comparisons can reduce the sample complexity for the ranking problems compared to ranking from pairwise comparisons. Specifically, under the winner feedback setting, one can reduce the sample complexity for top-$k$ selection up to an $m$ factor and that for full ranking up to a $\log{m}$ factor. Under the full-ranking feedback setting, one can reduce the sample complexity for top-$k$ selection up to an $m$ factor and that for full ranking up to an $m\log{m}$ factor. We also conduct numerical simulations to confirm our theoretical results.

In this work, we consider a network, where n distributed information sources whose states evolve according to a random process transmit their time-varying states to a remote estimator over a shared wireless channel. Each source generates packets in a decentralized manner and employs a slotted random access mechanism to transmit the packets. In particular, we are interested in networks with a large number of low-complexity devices that share low-capacity random access channels. Accordingly, we investigate update strategies for remote tracking of source states that require each update to constitute as few bits as possible. To that end, we develop update strategies requiring only one-bit of information per update. We first consider a natural benchmark update policy and reveal that the benchmark policy cannot guarantee stability under all conditions. We then introduce an improvement of the benchmark policy that employs a local cancellation strategy, which makes the system always stable. We further analyze and optimize the performance of the cancellation-enabled update policy to bound the estimation error at the receiver. Through simulations, we compare the proposed cancellation-enabled one-bit update policy with zero-wait sampling and threshold-based sampling policies that require more than one-bit of information per update. The comparisons show that the cancellation-enabled update policy at its optimal threshold level outperforms the multi-bit update policies. This suggests that the cancellation-enabled one-bit update policy could be greatly beneficial for applications where transmission power or shared channel capacity are limited.

Identifying “superspreaders” of disease is a pressing concern for society during pandemics such as COVID-19. Superspreaders represent a group of people who have much more social contacts than others. The widespread deployment of WLAN infrastructure enables non-invasive contact tracing via people’s ubiquitous mobile devices. This technology offers promise for detecting superspreaders. In this paper, we propose a general framework for WLAN-log-based superspreader detection. In our framework, we first use WLAN logs to construct contact graphs by jointly considering human symmetric and asymmetric interactions. Next, we adopt three vertex centrality measurements over the contact graphs to generate three groups of superspreader candidates. Finally, we leverage SEIR simulation to determine groups of superspreaders among these candidates, who are the most critical individuals for the spread of disease based on the simulation results. We have implemented our framework and evaluate it over a WLAN dataset with 41 million log entries from a large-scale university. Our evaluation shows superspreaders exist on university campuses. They change over the first few weeks of a semester, but stabilize throughout the rest of the term. The data also demonstrate that both symmetric and asymmetric contact tracing can discover superspreaders, but the latter performs better with daily contact graphs. Further, the evaluation shows no consistent differences among three vertex centrality measures for long-term (i.e., weekly) contact graphs, which necessitates the inclusion of SEIR simulation in our framework. We believe our proposed framework and these results can provide timely guidance for public health administrators regarding effective testing, intervention, and vaccination policies.

We consider a joint sampling and scheduling problem for optimizing data freshness in multi-source systems. Data freshness is measured by a non-decreasing penalty function of age of information, where all sources have the same age-penalty function. Sources take turns to generate update packets, and forward them to their destinations one-by-one through a shared channel with random delay. There is a scheduler, that chooses the update order of the sources, and a sampler, that determines when a source should generate a new packet in its turn. We aim to find the optimal scheduler-sampler pairs that minimize the total-average age-penalty at delivery times (Ta-APD) and the total-average age-penalty (Ta-AP). We prove that the Maximum Age First (MAF) scheduler and the zero-wait sampler are jointly optimal for minimizing the Ta-APD. Meanwhile, the MAF scheduler and a relative value iteration with reduced complexity (RVI-RC) sampler are jointly optimal for minimizing the Ta-AP. The RVI-RC sampler is based on a relative value iteration algorithm whose complexity is reduced by exploiting a threshold property in the optimal sampler. Finally, a low-complexity threshold-type sampler is devised via an approximate analysis of Bellman's equation. This threshold-type sampler reduces to a simple water-filling sampler for a linear age-penalty function.

In a variety of network applications, there exists a significant amount of shared data between two end hosts. Examples include data synchronization services that replicate data from one node to another. Given that shared data may have a high correlation with new data to transmit, we question how such shared data can be best utilized to improve the efficiency of data transmission. To answer this, we develop an inter-data encoding technique, SyncCoding, that effectively replaces bit sequences of the data to be transmitted with the pointers to their matching bit sequences in the shared data so called references. By doing so, SyncCoding can reduce data traffic, speed up data transmission, and save energy consumption for transmission. Our evaluations of SyncCoding implemented in Linux show that it outperforms existing popular encoding techniques, Brotli, LZMA, Deflate, and Deduplication. The gains of SyncCoding over those techniques in the perspective of data size after compression in a cloud storage scenario are about 12.5, 20.8, 30.1, and 66.1 percent, and are about 78.4, 80.3, 84.3, and 94.3 percent in a web browsing scenario, respectively.

We consider the problem of optimizing the freshness of status updates that are sent from a large number of low-power sources to a common access point. The source nodes utilize carrier sensing to reduce collisions and adopt an asynchronized sleep-wake scheduling strategy to achieve a target network lifetime (e.g., 10 years). We useage of information(AoI) to measure the freshness of status updates, and design sleep-wake parameters for minimizing the weighted-sum peak AoI of the sources, subject to per-source battery lifetime constraints. When the sensing time (i.e., the time duration of carrier sensing) is zero, this sleep-wake design problem can be solved by resorting to a two-layer nested convex optimization procedure; however, for positive sensing times, the problem is non-convex. We devise a low-complexity solution to solve this problem and prove that, for practical sensing times that are short, the solution is within a small gap from the optimum AoI performance. When the mean transmission time of status-update packets is unknown, we devise a reinforcement learning algorithm that adaptively performs the following two tasks in an “efficient way”: a) it learns the unknown parameter, b) it also generates efficient controls that make channel access decisions. We analyze its performance by quantifying its “regret”, i.e., the sub-optimality gap between its average performance and the average performance of a controller that knows the mean transmission time. Our numerical and NS-3 simulation results show that our solution can indeed elongate the batteries lifetime of information sources, while providing a competitive AoI performance.

In this paper, we prove that under mild stochastic assumptions, work-conserving disciplines are asymptotic optimal for minimizing total completion time. As a byproduct of our analysis, we obtain tight upper bound on the competitive ratios of work-conserving disciplines on minimizing the metric of flow time.

This paper studies the sample complexity (aka number of comparisons) bounds for the active best-$k$ items selection from pairwise comparisons. From a given set of items, the learner can make pairwise comparisons on every pair of items, and each comparison returns an independent noisy result about the preferred item. At any time, the learner can adaptively choose a pair of items to compare according to past observations (i.e., active learning). The learner’s goal is to find the (approximately) best-$k$ items with a given confidence, while trying to use as few comparisons as possible. In this paper, we study two problems: (i) finding the probably approximately correct (PAC) best-$k$ items and (ii) finding the exact best-$k$ items, both under strong stochastic transitivity and stochastic triangle inequality. For PAC best-$k$ items selection, we first show a lower bound and then propose an algorithm whose sample complexity upper bound matches the lower bound up to a constant factor. For the exact best-$k$ items selection, we first prove a worst-instance lower bound. We then propose two algorithms based on our PAC best items selection algorithms: one works for $k=1$ and is sample complexity optimal up to a loglog factor, and the other works for all values of $k$ and is sample complexity optimal up to a log factor.

The emergence of bandwidth-intensive latency-critical traffic in 5G Networks, such as Virtual Reality and Cloud Gaming, has motivated interest in wireless resource allocation problems for flows with hard-deadlines. Attempting to solve this problem brings about the following two key challenges: (i) The flow arrival and the wireless channel state information are not known to the Base Station (BS) apriori, thus, the allocation decisions need to be made in an online manner. (ii) Resource allocation algorithms that attempt to maximize a reward in the wireless setting will likely be unfair, causing unacceptable service for some users. In the first part of this paper, we model the problem of allocating resources to deadline-sensitive traffic as an online convex optimization problem, where the BS acquires a per-request reward that depends on the amount of traffic transmitted within the required deadline. We address the question of whether we can efficiently solve that problem with low complexity. In particular, whether we can design a constant-competitive scheduling algorithm that is oblivious to requests' deadlines. To this end, we propose a primal-dual Deadline-Oblivious (DO) algorithm, and show it is approximately 3.6-competitive. Furthermore, we show via simulations that our algorithm tracks the prescient offline solution very closely, significantly outperforming several algorithms that were previously proposed. Our results demonstrate that even though a scheduler may not know the deadlines of each flow, it can still achieve good theoretical and empirical performance. In the second part, we impose a stochastic constraint on the allocation, requiring a guarantee that each user achieves a certain timely throughput (amount of traffic delivered within the deadline over a period of time). We propose a modified version of our algorithm, called the Long-term Fair Deadline Oblivious (LFDO) algorithm for that setup. We combine the Lyapunov framework for stochastic optimization with the Primal-Dual analysis of online algorithms, to show that LFDO retains the high-performance of DO, while satisfying the long-term stochastic constraints.

Age of information, as a metric measuring the data freshness, has drawn increasing attention due to its importance in many data update applications. Most existing studies have assumed that there is one single channel in the system. In this work, we are motivated by the plethora of multi-channel systems that are being developed, and investigate the following question: how can one exploit multi-channel resources to improve the age performance? We first derive a policy-independent lower bound of the expected long-term average age in a multi-channel system. The lower bound is jointly characterized by the external arrival process and the channel statistics. Since direct analysis of age in multi-channel systems is very difficult, we focus on the asymptotic regime, when the number of users and number of channels both go to infinity. In the many-channel asymptotic regime, we propose a class of Maximum Weighted Matching policies that converge to the lower bound near exponentially fast. In the many-user asymptotic regime, we design a class of Randomized Maximum Weighted Matching policies that achieve a constant competitive ratio compared to the lower bound. Finally, we use simulations to validate the aforementioned results.

In this paper, we consider the problem of optimizing the freshness of status updates that are sent from a large number of low-power source nodes to a common access point. The source nodes utilize carrier sensing to reduce collisions and adopt an asychronized sleep-wake strategy to achieve an extended battery lifetime (e.g., 10-15 years). We use age of information (AoI) to measure the freshness of status updates, and design the sleep-wake parameters for minimizing the weighted-sum peak AoI of the sources, subject to per-source battery lifetime constraints. When the sensing time is zero, this sleep-wake design problem can be solved by resorting to a two-layer nested convex optimization procedure; however, for positive sensing times, the problem is non-convex. We devise a low-complexity solution to solve this problem and prove that, for practical sensing times that are short and positive, the solution is within a small gap from the optimum AoI performance. Our numerical and NS-3 simulation results show that our solution can indeed elongate the batteries lifetime of information sources, while providing a competitive AoI performance.

In this paper, we study the effect of predictive caching on the delay of wireless networks. We explore the possibility of caching at wireless end-users where caches are typically very small, orders of magnitude smaller than the catalog size. We develop a predictive multicasting and caching scheme, where the Base Station (BS) in a wireless cell proactively multicasts popular content for end-users to cache, and access locally if requested. We analyze the impact of this joint multicasting and caching on the delay performance. Our analysis uses a novel application of Heavy-Traffic theory under the assumption of vanishing caches to show that predictive caching fundamentally alters the asymptotic throughput-delay scaling. This in turn translates to a several-fold delay improvement in simulations over the on-demand unicast baseline as the network operates close to the full load. We highlight a fundamental delay-memory trade-off in the system and identify the correct memory scaling to fully benefit from the network multicasting gains.

In this paper, delay-optimal and energy-efficient communication is studied for a single link under Markov random arrivals. We present the optimal tradeoff between delay and power over Additive White Gaussian Noise (AWGN) channels and extend the optimal tradeoff for block fading channels. Under time-correlated traffic arrivals, we develop a cross-layer solution that jointly considers the arrival rate, the queue length, and the channel state in order to minimize the average delay subject to a power constraint. For this purpose, we formulate the average delay and power problem as a Constrained Markov Decision Process (CMDP). Based on steady-state analysis for the CMDP, a Linear Programming (LP) problem is formulated to obtain the optimal delay-power tradeoff. We further show the optimal transmission strategy using a Lagrangian relaxation technique. Specifically, the optimal adaptive transmission is shown to have a threshold type of structure, where the thresholds on the queue length are presented for different transmission rates under the given arrival rates and channel states. By exploiting the result, we develop a threshold-based algorithm to efficiently obtain the optimal delay-power tradeoff. We show how a trajectory-sampling version of the proposed algorithm can be developed without the prior need of arrival statistics.

One fundamental challenge in 5G URLLC is how to optimize massive MIMO systems for achieving low latency and high reliability. A natural design choice to maximize reliability and minimize retransmission is to select the lowest allowed target error rate. However, the overall latency is the sum of queueing latency and retransmission latency, hence choosing the lowest target error rate does not always minimize the overall latency. In this paper, we minimize the overall latency by jointly designing the target error rate and transmission rate adaptation, which leads to a fundamental tradeoff point between queueing and retransmission latency. This design problem can be formulated as a Markov decision process, which is theoretically optimal, but its complexity is prohibitively high for real-system deployments. We managed to develop a low-complexity closed-form policy named Large-arraY Reliability and Rate Control (LYRRC), which is proven to be asymptotically latency-optimal as the number of antennas increases. In LYRRC, the transmission rate is twice of the arrival rate, and the target error rate is a function of the antenna number, arrival rate, and channel estimation error. With simulated and measured channels, our evaluations find LYRRC satisfies the latency and reliability requirements of URLLC in all the tested scenarios.

This paper studies the problem of identifying any $k$ distinct arms among the top $\rho$ fraction (e.g., top 5%) of arms from a finite or infinite set with a probably approximately correct (PAC) tolerance $\epsilon$. We consider two cases: (i) when the threshold of the top arms’ expected rewards is known and (ii) when it is unknown. We prove lower bounds for the four variants (finite or infinite arms, and known or unknown threshold), and propose algorithms for each. Two of these algorithms are shown to be sample complexity optimal (up to constant factors) and the other two are optimal up to a log factor. Results in this paper provide up to $\rho n/k$ reductions compared with the “$k$-exploration” algorithms that focus on finding the (PAC) best $k$ arms out of $n$ arms. We also numerically show improvements over the state-of-the-art.

In large-scale distributed linear transform problems, coded computation plays an important role to reduce the delay caused by slow machines. However, existing coded schemes could end up destroying the significant sparsity that exists in large-scale machine learning problems, and in turn increase the computational delay. In this paper, we propose a coded computation strategy, referred to as diagonal code, that achieves the optimum recovery threshold and the optimum computation load. Furthermore, by leveraging the ideas from random proposal graph theory, we design a random code that achieves a constant computation load, which significantly outperforms the existing best known result. We apply our schemes to the distributed gradient descent problem and demonstrate the advantage of the approach over current fastest coded schemes.

Stochastic multi-armed bandits form a class of online learning problems that have important applications in online recommendation systems, adaptive medical treatment, and many others. Even though potential attacks against these learning algorithms may hijack their behavior, causing catastrophic loss in real-world applications, little is known about adversarial attacks on bandit algorithms. In this paper, we propose a framework of offline attacks on bandit algorithms and study convex optimization based attacks on several popular bandit algorithms. We show that the attacker can force the bandit algorithm to pull a target arm with high probability by a slight manipulation of the rewards in the data. Then we study a form of online attacks on bandit algorithms and propose an adaptive attack strategy against any bandit algorithm without the knowledge of the bandit algorithm. Our adaptive attack strategy can hijack the behavior of the bandit algorithm to suffer a linear regret with only a logarithmic cost to the attacker. Our results demonstrate a significant security threat to stochastic bandits.

FlexRadio, a recent breakthrough in wireless Multi-RF technology, has introduced a new way to unify MIMO and full-duplex into a single framework with a fully flexible design. FlexRadio allows a wireless node to use an arbitrary number of RF chains to support transmission and reception, which makes MIMO and full-duplex subset configurations of FlexRadio. This new architecture has greatly changed the feasibility constraint in wireless networks, which makes the design of high performance MAC layer algorithms even more challenging. First, the RF chain becomes a new resource that needs to be allocated across the network, and the optimal configuration depends not only on the network topology and flow demand, but also on the number of available RF chains at each node. Second, it is not clear how to jointly allocate links and RF chain resources based on the arrival rates and queueing dynamics. In this paper, we introduce a new virtual link model to characterize the feasibility constraint from the perspective of contending RF chain usage. Based on this novel model, a distributed CSMA-like framework is developed to fully leverage the flexibility of RF chain resource allocation.

In this paper, we consider the problem of minimizing the age of information in a multi-source system, where samples are taken from multiple sources and sent to a destination via a channel with random delay. Due to interference, only one source can be scheduled at a time. We consider the problem of finding a decision policy that determines the sampling times and transmission order of the sources for minimizing the total average peak age (TaPA) and the total average age (TaA) of the sources. Our investigation of this problem results in an important separation principle: The optimal scheduling strategy and the optimal sampling strategy are independent of each other. In particular, we prove that, for any given sampling strategy, the Maximum Age First (MAF) scheduling strategy provides the best age performance among all scheduling strategies. This transforms our overall optimization problem into an optimal sampling problem, given that the decision policy follows the MAF scheduling strategy. While the zero-wait sampling strategy (in which a sample is generated once the channel becomes idle) is shown to be optimal for minimizing the TaPA, it does not always minimize the TaA. We use Dynamic Programming (DP) to investigate the optimal sampling problem for minimizing the TaA. Finally, we provide an approximate analysis of Bellman's equation to approximate the TaA-optimal sampling strategy by a water-filling solution which is shown to be very close to optimal through numerical evaluations.

Each camera on digital devices is made of hundreds of thousands of sensors, with which it can separate and capture the light from spatial points in a fine-grain manner, enabling high-rate data transfer from the digital display to the camera, i.e. screen-camera communication. Compared with RF (Radio Frequency) technologies, visible light approaches are more convenient and secure.

This paper studies the problem of finding the exact ranking from noisy comparisons. A noisy comparison over a set of $m$ items produces a noisy outcome about the most preferred item, and reveals some information about the ranking. By repeatedly and adaptively choosing items to compare, we want to fully rank the items with a certain confidence, and use as few comparisons as possible. Different from most previous works, in this paper, we have three main novelties: (i) compared to prior works, our upper bounds (algorithms) and lower bounds on the sample complexity (aka number of comparisons) require the minimal assumptions on the instances, and are not restricted to specific models; (ii) we give lower bounds and upper bounds on instances with \textit{unequal} noise levels; and (iii) this paper aims at the \textit{exact} ranking without knowledge on the instances, while most of the previous works either focus on approximate rankings or study exact ranking but require prior knowledge. We first derive lower bounds for pairwise ranking (i.e., compare two items each time), and then propose (nearly) \textit{optimal} pairwise ranking algorithms. We further make extensions to listwise ranking (i.e., comparing multiple items each time). Numerical results also show our improvements against the state of the art.

Millimeter wave (mmWave) technologies have the potential to achieve very high data rates, but suffer from intermittent connectivity. In this paper, we provision an architecture to integrate sub-6 GHz and mmWave technologies, where we incorporate the sub-6 GHz interface as a fallback data transfer mechanism to combat blockage and intermittent connectivity of the mmWave communications. To this end, we investigate the problem of scheduling data packets across the mmWave and sub-6 GHz interfaces such that the average delay of system is minimized. This problem can be formulated as Markov Decision Process. We first investigate the problem of discounted delay minimization, and prove that the optimal policy is of the threshold-type, i.e., data packets should always be routed to the mmWave interface as long as the number of packets in the system is smaller than a threshold. Then, we show that the results of the discounted delay problem hold for the average delay problem as well. Through numerical results, we demonstrate that under heavy traffic, integrating sub-6 GHz with mmWave can reduce the average delay by up to 70%. Further, our scheduling policy substantially reduces the delay over the celebrated MaxWeight policy.

In this paper, we investigate scheduling policies that minimize the age of information in single-hop queueing systems. We propose a Last-Generated, First-Serve (LGFS) scheduling policy, in which the packet with the earliest generation time is processed with the highest priority. If the service times are i.i.d. exponentially distributed, the preemptive LGFS policy is proven to be age-optimal in a stochastic ordering sense. If the service times are i.i.d. and satisfy a New-Better-than-Used (NBU) distributional property, the non-preemptive LGFS policy is shown to be within a constant gap from the optimum age performance. These age-optimality results are quite general: (i) they hold for arbitrary packet generation times and arrival times (including out-of-order packet arrivals); (ii) they hold for multi-server packet scheduling with the possibility of replicating a packet over multiple servers; (iii) and they hold for minimizing not only the time-average age and mean peak age, but also for minimizing the age stochastic process and any non-decreasing functional of the age stochastic process. If the packet generation time is equal to the packet arrival time, the LGFS policies reduce to the Last-Come, First-Serve (LCFS) policies. Hence, the age optimality results of LCFS-type policies are also established.

Information updates in multihop networks such as Internet of Things (IoT) and intelligent transportation systems have received significant recent attention. In this paper, we minimize the age of a single information flow in interference-free multihop networks. When preemption is allowed and the packet transmission times are exponentially distributed, we prove that a preemptive last-generated, first-served (LGFS) policy results in smaller age processes across all nodes in the network than any other causal policy (in a stochastic ordering sense). In addition, for the class of new-better-than-used (NBU) distributions, we show that the non-preemptive LGFS policy is within a constant age gap from the optimum average age. In contrast, our numerical result shows that the preemptive LGFS policy can be very far from the optimum for some NBU transmission time distributions. Finally, when preemption is prohibited and the packet transmission times are arbitrarily distributed, the non-preemptive LGFS policy is shown to minimize the age processes across all nodes in the network among all work-conserving policies (again in a stochastic ordering sense). Interestingly, these results hold under quite general conditions, including (1) arbitrary packet generation and arrival times, and (2) for minimizing both the age processes in stochastic ordering and any non-decreasing functional of the age processes.

Mobile crowdsensing has found a variety of applications (e.g., spectrum sensing, environmental monitoring) by leveraging the “wisdom” of a potentially large crowd of mobile users. An important metric of a crowdsensing task is data accuracy, which relies on the data quality of the participating users' data (e.g., users' received SNRs for measuring a transmitter's transmit signal strength). However, the quality of a user can be its private information (which, e.g., may depend on the user's location) that it can manipulate to its own advantage, which can mislead the crowdsensing requester about the knowledge of the data's accuracy. This issue is exacerbated by the fact that the user can also manipulate its effort made in the crowdsensing task, which is a hidden action that could result in the requester having incorrect knowledge of the data's accuracy. In this paper, we devise truthful crowdsensing mechanisms for Quality and Effort Elicitation (QEE), which incentivize strategic users to truthfully reveal their private quality and truthfully make efforts as desired by the requester. The QEE mechanisms achieve the truthful design by overcoming the intricate dependency of a user's data on its private quality and hidden effort. Under the QEE mechanisms, we show that the crowdsensing requester's optimal (RO) effort assignment assigns effort only to the best user that has the smallest “virtual valuation”, which depends on the user's quality and the quality's distribution. We also show that, as the number of users increases, the performance gap between the RO effort assignment and the socially optimal effort assignment decreases, and converges to 0 asymptotically. We further discuss some extensions of the QEE mechanisms. Simulation results demonstrate the truthfulness of the QEE mechanisms and the system efficiency of the RO effort assignment.

Social networking environments provide major platforms for the discussion and formation of opinions in diverse areas, including, but not limited to, political discourse, market trends, news, and social movements. Often, these opinions are of a competing nature, e.g., radical vs. peaceful ideologies, correct information vs. misinformation, and one technology vs. another. We study the battles of such competing opinions over evolving social networks. The novelty of our model is that it captures the exposure and adoption dynamics of opinions that account for the preferential and random nature of exposure as well as the persuasion power and persistence of different opinions. We provide a complete characterization of the mean opinion dynamics over time as a function of the initial adoption, as well as the particular exposure, adoption, and persistence dynamics. Our analysis, supported by case studies, reveals the key metrics that govern the spread of opinions and establishes the means to engineer the desired impact of an opinion in the presence of other competing opinions.

The cost of energy usage is of significant concern in cloud/data center systems that support a large number of servers. A simple way to reduce energy consumption and the electricity bill is to turn some of the servers off during periods of under utilization. However, turning a server back on typically consumes a lot of energy. Another way to reduce the energy cost is to equip cloud systems with renewable resources and batteries. Most works in the literature have focused on one or the other approach. In this work, we propose a joint server on-off and energy control policy, which determines the servers' on-off status, as well as the energy purchasing behavior, by taking electricity price, renewable resources, possible future tasks and turn-on cost into account. The server on-off control component is proved to be optimal in terms of energy consumption minimization. The joint policy is shown to be arbitrarily close to the optimal solution in terms of electricity bill minimization, in the case where the battery has infinite capacity with stable energy level. Simulation results show that even under reasonable battery size, a significant electricity cost reduction is achieved with the proposed policy.

We consider stochastic multi-armed bandit problems with graph feedback, where the decision maker is allowed to observe the neighboring actions of the chosen action. We allow the graph structure to vary with time and consider both deterministic and Erdos-Renyi random graph models. For such a graph feedback model, we first present a novel analysis of Thompson sampling that leads to tighter performance bound than existing work. Next, we propose new Information Directed Sampling based policies that are graph-aware in their decision making. Under the deterministic graph case, we establish a Bayesian regret bound for the proposed policies that scales with the clique cover number of the graph instead of the number of actions. Under the random graph case, we provide a Bayesian regret bound for the proposed policies that scales with the ratio of the number of actions over the expected number of observations per iteration. To the best of our knowledge, this is the first analytical result for stochastic bandits with random graph feedback. Finally, using numerical evaluations, we demonstrate that our proposed IDS policies outperform existing approaches, including adaptions of upper confidence bound, epsilon-greedy and Exp3 algorithms.

The multi-armed bandit problem has been extensively studied under the stationary assumption. However in reality, this assumption often does not hold because the distributions of rewards themselves may change over time. In this paper, we propose a change-detection (CD) based framework for multi-armed bandit problems under the piecewise-stationary setting, and study a class of change-detection based UCB (Upper Confidence Bound) policies, CD-UCB, that actively detects change points and restarts the UCB indices. We then develop CUSUM-UCB and PHT-UCB, that belong to the CD-UCB class and use cumulative sum (CUSUM) and Page-Hinkley Test (PHT) to detect changes. We show that CUSUM-UCB obtains the best known regret upper bound under mild assumptions. We also demonstrate the regret reduction of the CD-UCB policies over arbitrary Bernoulli rewards and Yahoo! datasets of webpage click-through rates.

In a large-scale and distributed matrix multiplication problem $C=A^{\intercal}B$, where $C\in\mathbb{R}^{r\times t}$, the coded computation plays an important role to effectively deal with “stragglers” (distributed computations that may get delayed due to few slow or faulty processors). However, existing coded schemes could destroy the significant sparsity that exists in large-scale machine learning problems, and could result in much higher computation overhead, i.e., $O(rt)$ decoding time. In this paper, we develop a new coded computation strategy, we call sparse code, which achieves near optimal recovery threshold, low computation overhead, and linear decoding time $O(nnz(C))$. We implement our scheme and demonstrate the advantage of the approach over both uncoded and current fastest coded strategies.

In this work, we address the open problem of finding low-complexity near-optimal multi-armed bandit algorithms for sequential decision making problems. Existing bandit algorithms are either sub-optimal and computationally simple (e.g., UCB1) or optimal and computationally complex (e.g., kl-UCB). We propose a boosting approach to Upper Confidence Bound based algorithms for stochastic bandits, that we call UCBoost. Specifically, we propose two types of UCBoost algorithms. We show that UCBoost(D) enjoys O(1) complexity for each arm per round as well as regret guarantee that is 1/e-close to that of the kl-UCB algorithm. We propose an approximation-based UCBoost algorithm, UCBoost(epsilon), that enjoys a regret guarantee epsilon-close to that of kl-UCB as well as O(log(1/epsilon)) complexity for each arm per round. Hence, our algorithms provide practitioners a practical way to trade optimality with computational complexity. Finally, we present numerical results which show that UCBoost(epsilon) can achieve the same regret performance as the standard kl-UCB while incurring only 1% of the computational cost of kl-UCB.

In this paper, we investigate the problem of beam alignment in millimeter wave (mmWave) systems, and design an optimal algorithm to reduce the overhead. Specifically, due to directional communications, the transmitter and receiver beams need to be aligned, which incurs high delay overhead since without a priori knowledge of the transmitter/receiver location, the search space spans the entire angular domain. This is further exacerbated under dynamic conditions (e.g., moving vehicles) where the access to the base station (access point) is highly dynamic with intermittent on-off periods, requiring more frequent beam alignment and signal training. To mitigate this issue, we consider an online stochastic optimization formulation where the goal is to maximize the directivity gain (i.e., received energy) of the beam alignment policy within a time period. We exploit the inherent correlation and unimodality properties of the model, and demonstrate that contextual information improves the performance. To this end, we propose an equivalent structured Multi-Armed Bandit model to optimally exploit the exploration-exploitation tradeoff. In contrast to the classical MAB models, the contextual information makes the lower bound on regret (i.e., performance loss compared with an oracle policy) independent of the number of beams. This is a crucial property since the number of all combinations of beam patterns can be large in transceiver antenna arrays, especially in massive MIMO systems. We further provide an asymptotically optimal beam alignment algorithm, and investigate its performance via simulations.

A fundamental challenge in wireless multicast has been how to simultaneously achieve high-throughput and low-delay for reliably serving a large number of users. In this paper, we show how to harness substantial throughput and delay gains by exploiting multi-channel resources. We develop a new scheme called Multi-Channel Moving Window Codes (MC-MWC) for multi-channel multi-session wireless multicast. The salient features of MC-MWC are three-fold. (i) High throughput: we show that MC-MWC achieves order-optimal throughput in the many-user many-channel asymptotic regime. Moreover, the number of channels required by a conventional channel-allocation based scheme is shown to be doubly-exponentially larger than that required by MC-MWC. (ii) Low delay: using large deviations theory, we show that the delay of MC-MWC decreases linearly with the number of channels, while the delay reduction of conventional schemes is no more than a finite constant. (iii) Low feedback overhead: the feedback overhead of MC-MWC is a constant that is independent of both the number of receivers in each session and the number of sessions in the network. Finally, our trace-driven simulation and numerical results validate the analytical results and show that the implementation complexity of MC-MWC is low.

Mobile data crowdsourcing has found a broad range of applications (e.g., spectrum sensing, environmental monitoring) by leveraging the "wisdom" of a potentially large crowd of "workers" (i.e., mobile users). A key metric of crowdsourcing is data accuracy, which relies on the quality of the participating workers' data (e.g., the probability that the data is equal to the ground truth). However, the data quality of a worker can be its own private information (which the worker learns, e.g., based on its location) that it may have incentive to misreport, which can in turn mislead the crowdsourcing requester about the accuracy of the data. This issue is further complicated by the fact that the worker can also manipulate its effort made in the crowdsourcing task and the data reported to the requester, which can also mislead the requester. In this paper, we devise truthful crowdsourcing mechanisms for Quality, Effort, and Data Elicitation (QEDE), which incentivize strategic workers to truthfully report their private worker quality and data to the requester, and make truthful effort as desired by the requester. The truthful design of the QEDE mechanisms overcomes the lack of ground truth and the coupling in the joint elicitation of worker quality, effort, and data. Under the QEDE mechanisms, we characterize the socially optimal and the requester's optimal task assignments, and analyze their performance. We show that the requester's optimal assignment is determined by the largest "virtual valuation" rather than the highest quality among workers, which depends on the worker's quality and the quality's distribution. We evaluate the QEDE mechanisms using simulations which demonstrate the truthfulness of the mechanisms and the performance of the optimal task assignments.

The rapid growth of mobile data traffic is straining cellular networks. A natural approach to alleviate cellular networks congestion is to use, in addition to the cellular interface, secondary interfaces such as WiFi, Dynamic spectrum and mmWave to aid cellular networks in handling mobile traffic. The fundamental question now becomes: How should traffic be distributed over different interfaces, taking into account different application QoS requirements and the diverse nature of radio interfaces. To this end, we propose the Discounted Rate Utility Maximization (DRUM) framework with interface costs as a means to quantify application preferences in terms of throughput, delay, and cost. The flow rate allocation problem can be formulated as a convex optimization problem. However, solving this problem requires non-causal knowledge of the time-varying capacities of all radio interfaces. To this end, we propose an online predictive algorithm that exploits the predictability of wireless connectivity for a small look-ahead window w. We show that, under some mild conditions, the proposed algorithm achieves a constant competitive ratio independent of the time horizon T. Furthermore, the competitive ratio approaches 1 as the prediction window increases. We also propose another predictive algorithm based on the "Receding Horizon Control" principle from control theory that performs very well in practice. Numerical simulations serve to validate our formulation, by showing that under the DRUM framework: the more delay-tolerant the flow, the less it uses the cellular network, preferring to transmit in high rate bursts over the secondary interfaces. Conversely, delay-sensitive flows consistently transmit irrespective of different interfaces' availability. Simulations also show that the proposed online predictive algorithms have a near-optimal performance compared to the offline prescient solution under all considered scenarios.

Communications in the millimeter wave (mmWave) band faces significant challenges due to variable channels, intermittent connectivity, and high energy usage. Moreover, speeds for electronic processing of data is of the same order as typical rates for mmWave interfaces, making the use of complex algorithms for tracking channel variations and adjusting resources impractical. In order to mitigate some of these challenges, we propose an architecture that integrates the sub-6 GHz and mmWave technologies. Our system exploits the spatial correlations between the sub-6 GHz and mmWave interfaces for beamforming and data transfer. Based on extensive experimentation in indoor and outdoor settings, we demonstrate that analog beamforming can be used in mmWave without incurring large overhead, thanks to the spatial correlations with sub-6 GHz. In addition, we incorporate the sub-6 GHz interface as a fallback (secondary) data transfer mechanism such that: 1) the negative effects of highly intermittent mmWave connectivity are mitigated and 2) the abundant mmWave capacity is fully exploited. To achieve these goals, we consider the problem of scheduling the arrival traffic over the mmWave or sub-6 GHz in order to maximize the mmWave throughput while delay (due to mmWave outages) is guaranteed to be bounded. We prove using subadditivity analysis that the optimal scheduling policy is based on a single threshold that can be easily adopted despite high link variations. Numerical results demonstrate that our scheduler provides a bounded mmWave delay performance, while it achieves a similar throughput performance as the throughput-optimal policies (e.g., MaxWeight).

Cognitive Radio (CR) networks have received significant attention as a promising approach to improve the spectrum efficiency of current license-based regulatory system. In CR networks, a Secondary User (SU) can use a spectrum vacancy that can be detected by either sensing-before-transmission or database access. However, it is often difficult to detect a vacant spectrum opportunity because of inaccuracies due to sensing and delays to update and/or the database that holds this information. In this paper, we develop a hybrid detection framework in multi-channel CR networks, where an SU can selectively sense a channel for spectrum vacancy by accessing the spectrum history of Markovian channels. We focus on the value of the channel history information offered by the Primary Provider (PP) of each channel, and consider a market for the information exchange between multiple PPs and SUs. We investigate the interplay between of the PPs and the SUs through their pricing and buying decisions for this information, in the presence of sensing inaccuracy, i.e., false alarm and miss detection.

Security agencies have found security games to be useful models to understand how to better protect their assets. The key practical elements in this work are: (i) the attacker can simultaneously attack multiple targets, and (ii) different targets exhibit different types of dependencies based on the assets being protected (e.g., protection of critical infrastructure, network security, etc.). However, little is known about the computational complexity of these problems, especially when there exist dependencies among the targets. Moreover, previous security game models do not in general scale well. In this paper, we investigate a general security game where the utility function is defined on a collection of subsets of all targets, and provide a novel theoretical framework to show how to compactly represent such a game, efficiently compute the optimal (minimax) strategies, and characterize the complexity of this problem. We apply our theoretical framework to the network security game. We characterize settings under which we find a polynomial time algorithm for computing optimal strategies. In other settings we prove the problem is NP-hard and provide an approximation algorithm.

Cybersecurity is increasingly threatened by advanced and persistent attacks. As these attacks are often designed to disable a system (or a critical resource, e.g., a user account) repeatedly, it is crucial for the defender to keep updating its security measures to strike a balance between the risk of being compromised and the cost of security updates. Moreover, these decisions often need to be made with limited and delayed feedback due to the stealthy nature of advanced attacks. In addition to targeted attacks, such an optimal timing policy under incomplete information has broad applications in cybersecurity. Examples include key rotation, password change, application of patches, and virtual machine refreshing. However, rigorous studies of optimal timing are rare. Further, existing solutions typically rely on a pre-defined attack model that is known to the defender, which is often not the case in practice. In this work, we make an initial effort towards achieving optimal timing of security updates in the face of unknown stealthy attacks. We consider a variant of the influential FlipIt game model with asymmetric feedback and unknown attack time distribution, which provides a general model to consecutive security updates.The defender's problem is then modeled as a time associative bandit problem with dependent arms. We derive upper confidence bound based learning policies that achieve low regret compared with optimal periodic defense strategies that can only be derived when attack time distributions are known.

In this paper, we aim to obtain the optimal delay-power tradeoff and the corresponding optimal scheduling policy for arbitrary i.i.d. arrival process and adaptive transmissions. The number of backlogged packets at the transmitter is known to a scheduler, who has to determine how many backlogged packets to transmit during each time slot. The power consumption is assumed to be convex in transmission rates. Hence, if the scheduler transmits faster, the delay will be reduced but with higher power consumption. To obtain the optimal delay-power tradeoff and the corresponding optimal policy, we model the problem as a Constrained Markov Decision Process (CMDP), where we minimize the average delay given an average power constraint. By steady-state analysis and Lagrangian relaxation, we can show that the optimal tradeoff curve is decreasing, convex, and piecewise linear, and the optimal policy is threshold-based. Based on the revealed properties of the optimal policy, we develop an algorithm to efficiently obtain the optimal tradeoff curve and the optimal policy. The complexity of our proposed algorithm is much lower than a general algorithm based on Linear Programming. We validate the derived results and the proposed algorithm through Linear Programming and simulations.

Mobile applications that provide ever-changing information such as social media and news feeds applications are designed to consistently update their contents in the background. This operation, often called “prefetching”, provides the users with immediate access to up-to-date contents. However, such updates often result in the unwanted side-effect of draining the battery of mobile devices. It is considered as pure waste when updated contents are not accessed before being renewed. In this paper, we develop an optimal strategy to update the contents in the background under a given energy constraint. The key challenge is to predict when the user will access the contents in a probabilistic manner from the statistics of the accessed patterns in the past. We model our problem as a constrained Markov decision process (C-MDP) and propose to tackle its high complexity with a two-step solution that combines: (1) a threshold-based backward induction algorithm for the Lagrangian relaxation of our C-MDP, and (2) an iterative root finding algorithm, iMUTE (iterative Method for optimal UpdaTe policy with Energy constraint). We prove that iMUTE converges superlinearly to the optimal solution of the original C-MDP under a mild condition. We also experimentally verify that iMUTE outperforms the periodic policy as well as the additive and multiplicative increase policies that are adopted in the Doze mode of Android systems and HUSH, in terms of user experience and energy saving.

We consider a cognitive radio network, where primary users have priority over the spectrum resources, and secondary users can exploit the unused resources through channel sensing. Due to sensing inaccuracy, the secondary traffic may obstruct the primary traffic. A penalty for collision has been used to protect the primary traffic, which is often designed to provide a fixed per-collision compensation or to restrict the collision rate at an acceptable level. In this work, we develop a framework that can protect the primary traffic taking into account the Quality of Service of the primary traffic. In particular, we pay attention to the delay performance, which is determined not only by the collision rate but also by the amount of traffic in both networks. We design a novel model with coupled queues, and successfully incorporate dynamic interactions between the two systems through the standard optimization problem. We also consider the practical requirement of no direct sharing of the system information between the two networks, and develop a close-to-optimal solution of per-collision price and channel sensing under mild assumptions. We evaluate its performance through simulations.

The problem of reducing the age-of-information has been extensively studied in single-hop networks. In this paper, we minimize the age-of-information in general multihop networks. If the packet transmission times over the network links are exponentially distributed, we prove that a preemptive Last Generated First Served (LGFS) policy results in smaller age processes at all nodes of the network (in a stochastic ordering sense) than any other causal policy. In addition, for arbitrary distributions of packet transmission times, the non-preemptive LGFS policy is shown to minimize the age processes at all nodes among all non-preemptive work-conserving policies (again in a stochastic ordering sense). It is surprising that such simple policies can achieve optimality of the joint distribution of the age processes at all nodes even under arbitrary network topologies, as well as arbitrary packet generation and arrival times. These optimality results not only hold for the age processes, but also for any non-decreasing functional of the age processes.

Full duplex techniques can potentially double the channel capacity and achieve lower delays by empowering two radios to simultaneously transmit in thesame frequency band.However, full duplex is only available between two adjacent nodes within the communication range. In this paper, we present BiPass to break this limitation.With the help of full duplex capable relays, weenable simultaneous bidirectional in-band cut-through transmissions between two far apart nodes, so they can do full duplex communications as if they were within each other's transmission range.To design such a system, we analyze interference patterns and propose a loop-back interference cancellation strategy. We identify the power amplification problem at relay nodes and develop an algorithm to solve it. We also develop a routing algorithm, an opportunistic forwarding scheme, and a real-time feedback strategy to leverage this system in ad-hoc networks.To evaluate the real world performance of BiPass, we build a prototype and conduct experiments using software defined radios. We show that BiPass can achieve 1.6x median throughput gain over state-of-the-art one-way cut-through systems, and 4.09x gain over the decode-and-forward scheme. Our simulations further reveal that even when the data traffic is not bidirectional, BiPass has 1.36x throughput gain and 47\% delay reduction overone-way cut-through systemsin large networks.

An essential step for achieving multiplexing gain in MIMO downlink systems is to collect accurate channel state information (CSI) from the users. Traditionally, CSIs have to be collected before any data can be transmitted. Such a sequential scheme incurs a large feedback overhead, which substantially limits the multiplexing gain especially in a network with a large number of users. In this paper, we propose a novel approach to mitigate the feedback overhead by leveraging the recently developed Full-duplex radios. Our approach is based on the key observation that using Full-duplex radios, when the base-station (BS) is collecting CSI of one user through the uplink channel, it can use the downlink channel to simultaneously transmit data to other (non-interfering) users for which CSIs are already known. By allowing concurrent channel probing and data transmission, our scheme can potentially achieve a higher throughput compared to traditional schemes using Half-duplex radios. The new flexibility introduced by our scheme, however, also leads to fundamental challenges in achieving throughout optimal scheduling. In this paper, we make an initial effort to this important problem by considering a simplified group interference model. We develop a throughput optimal scheduling policy with complexity O((N/I)I), where N is the number of users and I is the number of user groups. To further reduce the complexity, we propose a greedy policy with complexity O(N log N) that not only achieves at least 2/3 of the optimal throughput region, but also outperforms any feasible Half-duplex solutions. We derive the throughput gain offered by Full-duplex under different system parameters and show the advantage of our algorithms through numerical studies.

It is well known that, for a linear program (LP) with constraint matrix $\mathbf{A}\in\mathbb{R}^{m\times n}$, the Alternating Direction Method of Multiplier converges globally and linearly at a rate $O((\|\mathbf{A}\|_F^2+mn)\log(1/\epsilon))$. However, such a rate is related to the problem dimension and the algorithm exhibits a slow and fluctuating ``tail convergence'' in practice. In this paper, we propose a new variable splitting method of LP and prove that our method has a convergence rate of $O(\|\mathbf{A}\|^2\log(1/\epsilon))$. The proof is based on simultaneously estimating the distance from a pair of primal dual iterates to the optimal primal and dual solution set by certain residuals. In practice, we result in a new first-order LP solver that can exploit both the sparsity and the specific structure of matrix $\mathbf{A}$ and a significant speedup for important problems such as basis pursuit, inverse covariance matrix estimation, L1 SVM and nonnegative matrix factorization problem compared with current fastest LP solvers.

The energy consumption of cellular networks has increased dramatically due to high demand for wireless communication. Base-stations (BSs) use about 60% to 80% of the energy consumed by these networks. An attractive way to reduce energy consumption is to turn the BSs off during periods of under-utilization. However, turning a BS back on typically consumes a lot of energy, which has not been considered in previous works, but critical to good energy management strategies. In this work, we dynamically determine the on-off schedule of these base-stations by taking both operation-cost and turn-on-cost into account. We develop the first online algorithm that only uses future information to decide the on-off status of each BS and characterize its performance using competitive ratio analysis. We extend it by utilizing history information which helps improve the competitive ratio. A heuristic adaptive online algorithm is then designed to balance the utilization of history and future information. We then show via simulation results that the adaptive algorithm works well under a wide range of traffic intensities.

Mobile crowd sensing has found a variety of applications (e.g., spectrum sensing, environmental monitoring) by leveraging the "wisdom" of a potentially large crowd of mobile users. An important metric of a crowd sensing task is data accuracy, which relies on the qualities of the participating users' data (e.g., users' received SNRs for measuring a transmitter's transmit signal strength). However, the quality of a user can be its private information (which, e.g., may depend on the user's location) that it can manipulate to its own advantage, which can mislead the crowd sensing requester about the knowledge of the data's accuracy. This issue is exacerbated by the fact that the user can also manipulate its effort made in the crowd sensing task, which is a hidden action that could result in the requester having incorrect knowledge of the data's accuracy. In this paper, we devise truthful crowd sensing mechanisms for Quality and Effort Elicitation (QEE), which incentivize strategic users to truthfully reveal their private qualities and truthfully make efforts as desired by the requester. The QEE mechanisms achieve the truthful design by overcoming the intricate dependency of a user's data on its private quality and hidden effort. Under the QEE mechanisms, we show that the crowd sensing requester's optimal (CO) effort assignment assigns effort only to the best user that has the smallest "virtual valuation", which depends on the user's quality and the quality's distribution. We also show that, as the number of users increases, the performance gap between the CO effort assignment and the socially optimal effort assignment decreases, and converges to 0 asymptotically. We further show that while the requester's payoff and the social welfare attained by the CO effort assignment both increase as the number of users increases, interestingly, the corresponding users' payoffs can decrease. Simulation results demonstrate the truthfulness of the QEE mechanisms and the system efficiency of the CO effort assignment.

We propose a hybrid architecture to integrate RF (i.e., sub-6 GHz) and millimeter wave (mmWave) interfaces for 5G cellular systems. To alleviate the challenges associated with mmWave communications, our proposed architecture integrates the RF and mmWave interfaces for beamforming and data transfer, and exploits the spatio-temporal correlations between the interfaces. Based on extensive experimentation in indoor and outdoor settings, we demonstrate that an integrated RF/mmWave signaling and channel estimation scheme can remedy the problem of high training overhead associated with mmWave beamforming. In addition, cooperation between two interfaces at the higher layers effectively addresses the high delays caused by highly intermittent connectivity in mmWave channels. Subsequently, we formulate an optimal scheduling problem over the RF and mmWave interfaces where the goal is to maximize the delay-constrained throughput of the mmWave interface. We prove using subadditivity analysis that the optimal scheduling policy is based on a single threshold that can be easily adopted despite high link variations. We design an optimal scheduler that opportunistically schedules the packets over the mmWave interface, while the RF link acts as a fallback mechanism to prevent high delay.

Each individual's usage behavior on mobile devices depends on a variety of factors, such as time, location, and previous actions. Hence, context-awareness provides great opportunities to make the networking and computing capabilities of mobile systems more personalized and more efficient in managing their resources. To this end, we first reveal new findings from our own Android user experiment: 1) the launching probabilities of applications follow Zipf's law and 2) inter-running and running times of applications conform to log-normal distributions. We also find contextual dependencies between application usage patterns, for which we classify contexts autonomously with unsupervised learning methods. Using the knowledge acquired, we develop a context-aware application scheduling framework, context-aware application scheduler (CAS), that adaptively unloads and preloads background applications for a joint optimization in which the energy saving is maximized and the user discomfort from the scheduling is minimized. Our trace-driven simulations with 96 user traces demonstrate that the context-aware design of the CAS enables it to outperform existing process scheduling algorithms. Our implementation of the CAS over Android platforms and its end-to-end evaluations verify that its human-involved design indeed provides substantial user-experience gains in both energy and application launching latency.

To support the multi-gigabit per second data rates of 5G wireless networks, there have been significant efforts on the research and development of massive MIMO (M-MIMO) technologies at the physical layer. So far, however, the understanding of how M-MIMO could affect the performance of network control, and optimization algorithms remain rather limited. In this paper, we focus on analyzing the performance of the queue-length-based joint congestion control and scheduling framework over M-MIMO cellular networks with limited channel state information (CSI). Our contributions in this paper are twofold. First, we characterize the scaling performance of the queue-lengths and show that there exists a phase transitioning phenomenon in the steady-state queue-length deviation with respect to the CSI quality (reflected in the number of bits B that represent CSI). Next, we characterize the congestion control rate scaling performance and show that there also exists a phase transitioning phenomenon in steady-state congestion control rate deviation with respect to the CSI quality. Collectively, the findings in this paper advance our understanding of the tradeoffs between delay, throughput, and the accuracy/complexity of CSI acquisition in M-MIMO cellular network systems.

In this paper, we aim to obtain the optimal tradeoff between the average delay and the average power consumption in a communication system. In our system, the arrivals occur at each timeslot according to a Bernoulli arrival process, and are buffered at the transmitter waiting to be scheduled. We consider a finite buffer and allow the scheduling decision to depend on the buffer occupancy. In order to capture the realism in communication systems, the transmission power is assumed to be an increasing and convex function of the number of packets transmitted in each timeslot. This problem is modeled as a constrained Markov decision process (CMDP). We first prove that the optimal policy of the Lagrangian relaxation of the CMDP is deterministic and threshold-based. We then show that the optimal delay-power tradeoff curve is convex and piecewise linear, and the optimal policies of the original problem are also threshold-based. Based on the results, we propose an algorithm to obtain the optimal policy and the optimal tradeoff curve. We also show that the proposed algorithm is much more efficient than using general methods. The theoretical results and the algorithm are validated by linear programming and simulations.

In this paper, we study how to optimally manage the freshness of information updates sent from a source node to a destination via a channel. A proper metric for data freshness at the destination is the age-of-information, or simply age, which is defined as how old the freshest received update is, since the moment that this update was generated at the source node (e.g., a sensor). A reasonable update policy is the zero-wait policy, i.e., the source node submits a fresh update once the previous update is delivered, which achieves the maximum throughput and the minimum delay. Surprisingly, this zero-wait policy does not always minimize the age. This counter-intuitive phenomenon motivates us to study how to optimally control information updates to keep the data fresh and to understand when the zero-wait policy is optimal. We introduce a general age penalty function to characterize the level of dissatisfaction on data staleness and formulate the average age penalty minimization problem as a constrained semi-Markov decision problem with an uncountable state space. We develop efficient algorithms to find the optimal update policy among all causal policies and establish sufficient and necessary conditions for the optimality of the zero-wait policy. Our investigation shows that the zero-wait policy is far from the optimum if: 1) the age penalty function grows quickly with respect to the age; 2) the packet transmission times over the channel are positively correlated over time; or 3) the packet transmission times are highly random (e.g., following a heavy-tail distribution).

Usage patterns of mobile devices depend on a variety of factors such as time, location, and previous actions. Hence, context-awareness can be the key to make mobile systems to become personalized and situation dependent in managing their resources. We first reveal new findings from our own Android user experiment: (i) the launching probabilities of applications follow Zipf's law, and (ii) inter-running and running times of applications conform to log-normal distributions. We also find context-dependency in application usage patterns, for which we classify contexts in a personalized manner with unsupervised learning methods. Using the knowledge acquired, we develop a novel context-aware application scheduling framework, CAS that adaptively unloads and preloads background applications in a timely manner. Our trace-driven simulations with 96 user traces demonstrate the benefits of CAS over existing algorithms. We also verify the practicality of CAS by implementing it on the Android platform.

The last decade has seen significant advances in optimization-based resource allocation and control approaches for wireless networks. However, the existing work suffer from poor performance in one or more of the metrics of optimality, delay, and convergence speed. To overcome these limitations, in this paper, we introduce a largely overlooked but highly effective heavy-ball optimization method. Based on this heavy-ball technique, we develop a cross-layer optimization framework that offers utility-optimality, fast-convergence, and significant delay reduction. Our contributions are three-fold: i) we propose a heavy-ball joint congestion control and routing/scheduling framework for both single-hop and multi-hop wireless networks; ii) we show that the proposed heavy-ball method offers an elegant three-way trade-off in utility, delay, and convergence, which is achieved under a near index-type simple policy; and more importantly, iii) our work opens the door to an unexplored network control and optimization paradigm that leverages advanced optimization techniques based on “memory/momentum” information.

There have been recent attempts to develop scheduling schemes for downlink transmission in a single cell of a multi-channel (e.g., OFDM-based) cellular network. These works have been quite promising in that they have developed low-complexity index scheduling policies that are delay-optimal (in a large deviation rate-function sense). However, these policies require that the channel is ON or OFF in each time-slot with a fixed probability (i.e., there is no memory in the system), while the reality is that due to channel fading and doppler shift, channels are often time-correlated in these cellular systems. Thus, an important open question is whether one can find simple index scheduling policies that are delay-optimal even when the channels are time-correlated. In this paper, we attempt to answer this question for time-correlated ON/OFF channels. In particular, we show that the class of oldest packets first (OPF) policies that give a higher priority to packets with a large delay is delay rate-function optimal under two conditions: 1) The channel is non-negatively correlated, and 2) The distribution of the OFF period is geometric. We use simulations to further elucidate the theoretical results.

In this work we study how to manage the freshness of status updates sent from a source to a remote monitor via a network server. A proper metric of data freshness at the monitor is the age-of-information, which is defined as how old the freshest update is since the moment this update was generated at the source. A logical policy is the zero-wait policy, i.e., the source submits a fresh update once the server is free, which achieves the maximum throughput and the minimum average delay. Surprisingly, this zero-wait policy does not always minimize the average age. This motivates us to study how to optimally control the status updates to keep data fresh and to understand when the zero-wait policy is optimal. We introduce a penalty function to characterize the level of “dissatisfaction” on data staleness, and formulate the average age penalty minimization problem as a constrained semi-Markov decision process (SMDP) with an uncountable state space. Despite of the difficulty of this problem, we develop efficient algorithms to find the optimal status update policy. We show that, in many scenarios, the optimal policy is to wait for a certain amount of time before submitting a new update. In particular, the zero-wait policy can be far from the optimum if (i) the penalty function grows quickly with respect to the age, and (ii) the update service times are highly random and positive correlated. To the best of our knowledge, this is the first optimal control policy which is proven to minimize the age-of-information in status update systems.

In many applications including interactive services and big data analytics, a timely result with a good match is often more valuable than a perfect yet delayed result. This fact can be utilized to improve the total utility gain of a cloud computing platform by allowing partial execution of jobs. A fundamental challenge, however, is that in many real environments, scheduling decisions have to be made online without knowledge about future jobs, which makes it difficult to choose between more valuable jobs with large deadlines and less valuable jobs that are more emergent. Moreover, jobs are often heterogeneous in their utilities, deadlines, and demands for different types of resources. In this paper, we study the problem of online scheduling for deadline-sensitive jobs with concave utility functions that can deliver partial results. We develop efficient online multi-resource allocation algorithms that achieve low competitive ratios for both continuous and discrete job models.

In this work, we investigate the design of information-update systems, where incoming update packets are forwarded to a remote destination through multiple servers (each server can be viewed as a wireless channel). One important performance metric of these systems is the data freshness at the destination, also called the age-of-information or simply age, which is defined as the time elapsed since the freshest packet at the destination was generated. Recent studies on information-update systems have shown that the age-of-information can be reduced by intelligently dropping stale packets. However, packet dropping may not be appropriate in many applications, such as news and social updates, where users are interested in not just the latest updates, but also past news. Therefore, all packets may need to be successfully delivered. In this paper, we study how to optimize age-of-information without throughput loss. We consider a general scenario where incoming update packets do not necessarily arrive in the order of their generation times. We prove that a preemptive Last Generated First Served (LGFS) policy simultaneous optimizes the age, throughput, and delay performance in infinite buffer queueing systems. We also show age-optimality for the LGFS policy for any finite queue size. These results hold for arbitrary, including non-stationary, arrival processes.

In recent years, there have been significant efforts on the research and development of Massive MIMO (M-MIMO) technologies at the physical layer. So far, however, the understanding of how M-MIMO could affect the performance of network control and optimization algorithms remains rather limited. In this paper, we focus on analyzing the performance of the queue-length-based joint congestion control and scheduling framework (QCS) over M-MIMO cellular networks with limited channel state information (CSI). Our contributions in this paper are two-fold: i) We characterize the scaling performance of the queue-lengths and show that there exists a phase transitioning phenomenon in the steady-state queue-length deviation respect to the CSI quality (reflected in the number of bits B that represent CSI); and ii) We characterize the congestion control rate scaling performance and show that there also exists a phase transitioning phenomenon in steady-state congestion control rate deviation respect to the CSI quality. Collectively, the findings in this paper advance our understanding of the trade-offs between delay, throughput, and the accuracy/complexity of CSI acquisition in M-MIMO cellular network systems.

For a multicast group of n receivers, existing techniques either achieve high throughput at the cost of prohibitively large (e.g., O(n)) feedback overhead, or achieve low feedback overhead but without either optimal or near-optimal throughput guarantees. Simultaneously achieving good throughput guarantees and low feedback overhead has been an open problem and could be the key reason why wireless multicast has not been successfully deployed in practice. In this paper, we develop a novel anonymous-query based rate control, which approaches the optimal throughput with a constant feedback overhead independent of the number of receivers. In addition to our theoretical results, through implementation on a software-defined ratio platform, we show that the anonymous-query based algorithm achieves low-overhead and robustness in practice.

In this paper, we study how to cluster Remote Radio Heads (RRHs) into Virtual Base-Stations (VBSs) in a Cloud-based Radio Access Network to optimally manage the tradeoff between improving the performance of cell-edge users and maintaining high spatial reuse for the overall system. We develop Gibbs-sampling based algorithms that can find the desirable global VBS configuration from an arbitrarily given set of allowable VBS configurations. While Gibbs-sampling has been used to solve other wireless control problems, its application to VBS clustering faces new challenges both due to the difficulty in estimating the quality of a VBS configuration under rapid channel variations, and due to a new global coupling effect. We leverage Random Matrix Theory to develop a method that can quickly estimate the quality of a VBS configuration based only on average channel statistics. Further, we use perturbation analysis to develop a distributed approximation of the Gibbs sampler to circumvent the global coupling effect, which then allows different parts of the network to search for better VBS configurations in parallel. Our numerical results demonstrate how the proposed algorithm can be used as a general tool to evaluate the system performance under a variety of clustering constraints.

Predicting spreading patterns of information or virus has been a popular research topic for which various mathematical tools have been developed. These tools have mainly focused on estimating the average time of spread to a fraction (e.g.,$\alpha$) of the agents, i.e., so-called average$\alpha$-completion time$E(T_{\alpha})$. We claim that understanding stochastic confidence on the time$T_{\alpha}$rather than only its average gives more comprehensive knowledge on the spread behavior and wider engineering choices. Obviously, the knowledge also enables us to effectively accelerate or decelerate a spread. To demonstrate the benefits of understanding the distribution of spread time, we introduce a new metric$G_{\alpha, \beta}$that denotes the time required to guarantee$\alpha$completion (i.e., penetration) with probability$\beta$. Also, we develop a new framework characterizing$G_{\alpha, \beta}$for various spread parameters such as number of seeders, contact rates between agents, and heterogeneity in contact rates. We apply our technique to a large-scale experimental vehicular trace and show that it is possible to allocate resources for acceleration of spread in a far more elaborated way compared to conventional average-based mathematical tools.

We investigate the downlink scheduling problem under Markovian ON/OFF fading channels, where the instantaneous channel state information is not directly accessible, but is revealed via ARQ-type feedback. The scheduler can exploit the temporal correlation/channel memory inherent in the Markovian channels to improve network performance. However, designing low-complexity and throughput-optimal algorithms under temporal correlation is a challenging problem. In this paper, we find that under an average number of transmissions constraint, a low-complexity index policy is throughput-optimal. The policy uses Whittle's index value, which was previously used to capture opportunistic scheduling under temporally correlated channels. Our results build on the interesting finding that, under the intricate queue length and channel memory evolutions, the importance of scheduling a user is captured by a simple multiplication of its queue length and Whittle's index value. The proposed queue-based index policy has provably low complexity. Numerical results show that significant throughput gains can be realized by exploiting the channel memory using the proposed low-complexity policy.

In this paper, we focus on a mobile wireless network comprising a powerful communication center and a multitude of mobile users. We investigate the propagation of latency-constrained content in the wireless network characterized by heterogeneous (time-varying and user-dependent) wireless channel conditions, heterogeneous user mobility, and where communication could occur in a hybrid format (e.g., directly from the central controller or by exchange with other mobiles in a peer-to-peer manner). We show that exploiting double opportunities, i.e., both time-varying channel conditions and mobility, can result in substantial performance gains. We develop a class of double opportunistic multicast schedulers and prove their optimality in terms of both utility and fairness under heterogeneous channel conditions and user mobility. Extensive simulation results are provided to demonstrate that these algorithms can not only substantially boost the throughput of all users (e.g., by 50% to 150%), but also achieve different consideration of fairness among individual users and groups of users.

We investigate the problem of minimizing the sum of the queue lengths of all the nodes in a wireless network with a tree topology. Nodes send their packets to the tree's root (sink). We consider a time-slotted system and a K-hop interference model. We characterize the existence of causal sample-path optimal scheduling policies in these networks, i.e., we wish to find a policy such that at each time-slot, for any traffic arrival pattern, the sum of the queue lengths of all the nodes is minimum among all policies. We provide an algorithm that takes any tree and K as inputs, and outputs whether a causal sample-path optimal policy exists for this tree under the K-hop interference model. We show that when this algorithm returns FALSE, there exists a traffic arrival pattern for which no causal sample-path optimal policy exists for the given tree structure. We further show that for certain tree structures, even noncausal sample-path optimal policies do not exist. We provide causal sample-path optimal policies for those tree structures for which the algorithm returns TRUE. Thus, we completely characterize the existence of such policies for all trees under the K-hop interference model. The nonexistence of sample-path optimal policies in a large class of tree structures implies that we need to study other (relatively) weaker metrics for this problem.

It has been known that scheduling algorithms designed to achieve throughput optimality and good delay performance often require solving the Maximum Weighted Independent Set (MWIS) problem. However, under most realistic network settings, the MWIS problem is known to be NP-hard. In non-fading environments, low-complexity scheduling algorithms have been provided that converge either to the MWIS solution in time or to a solution that achieves at least a provable fraction of the achievable throughput. However, in more practical systems the channel conditions can vary at faster time-scales than convergence occurs in these lower-complexity algorithms. Hence, these algorithms cannot take advantage of opportunistic gains, and may no longer result in achieving good performance. In this paper, we propose a low-complexity scheduling scheme that performs provably well under fading channels and is amenable to implement in a distributed manner. To the best of our knowledge, this is the first scheduling scheme under fading environments that requires only local information, has a low complexity that grows logarithmically with the network size (provided that the conflict graph has bounded maximum vertex degree), and achieves provable performance guarantees (arbitrarily close to that of the well-known centralized Greedy Maximal Scheduler). We verify that the throughput and the delay of our proposed scheme are close to those of the optimal MaxWeight that solves MWIS at each time. Further, we implement our algorithm in a testbed by modifying the existing IEEE 802.11 DCF. The experiment results show that our implementation successfully accounts for wireless fading, attains the short-term opportunistic gains in practice, and hence substantially outperforms IEEE 802.11 DCF.

Distributed joint congestion control and routing optimization has received a significant amount of attention recently. To date, however, most of the existing schemes follow a key idea called the back-pressure algorithm. Despite having many salient features, the first-order subgradient nature of the back-pressure based schemes results in slow convergence and poor delay performance. To overcome these limitations, in this paper, we make a first attempt at developing a second-order joint congestion control and routing optimization framework that offers utility-optimality, queue-stability, fast convergence, and low delay. Our contributions in this paper are three-fold: i) we propose a new second-order joint congestion control and routing framework based on a primal-dual interior-point approach; ii) we establish utility-optimality and queue-stability of the proposed second-order method; and iii) we show how to implement the proposed second-order method in a distributed fashion.

The problem of online packet scheduling with hard deadlines has been studied extensively in the single-hop setting, whereas it is notoriously difficult in the multihop setting. This difficulty stems from the fact that packet scheduling decisions at each hop influence and are influenced by decisions on other hops, and only a few provably efficient online scheduling algorithms exist in the multihop setting. We consider a multihop wired network (interference-free and full duplex transmissions) in which packets with various deadlines and weights arrive at and are destined to different nodes through given routes. We study the problem of joint admission control and packet scheduling in order to maximize the cumulative weights of the packets that reach their destinations within their deadlines. We first focus on uplink transmissions in the tree topology and show that the well-known Earliest Deadline First algorithm achieves the same performance as the optimal offline algorithm for any feasible arrival pattern. We then address the general topology with multiple source-destination pairs, develop a simple online algorithm, and show that it is O(PMlog PM)-competitive, where PMis the maximum route length among all packets. Our algorithm only requires information along the route of each packet, and our result is valid for general arrival samples. Moreover, we show that O(PMlog PM)-competitive is the best any online algorithm can do. Via numerical results, we also show that our algorithm achieves performance that is comparable to the noncausal optimal offline algorithm. To the best of our knowledge, this is the first algorithm with a provable (based on a sample-path construction) competitive ratio, subject to hard deadline constraints for general network topologies.

Video streaming generates a substantial fraction of the traffic on the Internet. The demands of video streaming also increase the workload on the video server, which in turn leads to substantial slowdowns. In order to resolve the slowdown problem, and to provide a scalable and robust infrastructure to support on-demand streaming, helper-assisted video-on-demand (VoD) systems have been introduced. In this architecture, helper nodes, which are micro-servers with limited storage and bandwidth resources, download and store the user-requested videos from a central server to decrease the load on the central server. Multi-layer videos, in which a video is divided into different layers, can also be used to improve the scalability of the system. In this paper, we study the problem of utilizing the helper nodes to minimize the pressure on the central servers. We formulate the problem as a linear programming using joint inter- and intra-layer network coding. Our solution can also be implemented in a distributed manner. We show how our method can be extended to the case of wireless live streaming, in which a set of videos is broadcasted. Moreover, we extend the proposed method to the case of unreliable connections. We carefully study the convergence and the gain of our distributed approach.

We consider the scheduling problem in downlink wireless networks with heterogeneous, Markov-modulated, on/off channels. It is well known that the performance of scheduling over fading channels relies heavily on the accuracy of the available channel state information (CSI), which is costly to acquire. Thus, we consider the CSI acquisition via a practical ARQ-based feedback mechanism whereby channel states are revealed at the end of only scheduled users' transmissions. In the assumed presence of temporally correlated channel evolutions, the desired scheduler must optimally balance the exploitation-exploration tradeoff, whereby it schedules transmissions both to exploit those channels with up-to-date CSI and to explore the current state of those with outdated CSI. In earlier works, Whittle's Index Policy had been suggested as a low-complexity and high-performance solution to this problem. However, analyzing its performance in the typical scenario of statistically heterogeneous channel state processes has remained elusive and challenging, mainly because of the highly coupled and complex dynamics it possesses. In this work, we overcome these difficulties to rigorously establish the asymptotic optimality properties of Whittle's Index Policy in the limiting regime of many users. More specifically: 1) we prove the local optimality of Whittle's Index Policy, provided that the initial state of the system is within a certain neighborhood of a carefully selected state; (2) we then establish the global optimality of Whittle's Index Policy under a recurrence assumption that is verified numerically for our problem. These results establish that Whittle's Index Policy possesses analytically provable optimality characteristics for scheduling over heterogeneous and temporally correlated channels.

A vehicle-to-vehicle (V2V) network is one type of mobile ad hoc network. Due to mobility, the topology in a V2V network is time-varying, which complicates the analysis and evaluation of network performance. In this paper, we model the network as geometric elements of lines and points and analyze the connectivity and capacity of the network using geometric probability. Under the assumption that n vehicles randomly arrive with a Poisson distribution, our analysis shows that the spatial distribution of vehicles within a given distance D, is uniform and that the average number of vehicles to be fully connected is approximately (1/a)(log (1/a) + log log (1/a)) for a = RT/D, where RT is the maximum transmission range of a vehicle. When a random access scheme is adopted, only (1/2)(1 - e-2)nof links comprised of two adjacent nodes are simultaneously activated, on average, so the expected network capacity increases in a way linearly proportional to (1/2)(1-e-2) as the number of vehicles increases. Through numerical studies and simulations, we verify the efficacy of our analytical results.

Many interactive applications running in data centers such as web search, social networks, online gaming, and financial services are delay-sensitive, and often have a deadline. These deadlines vary across users and applications, which makes the job scheduling problem very challenging when the overall system performance needs to be optimized. In this paper, the performance of interest is the total utility gain of multiple interactive jobs, and our objective is to maximize the total utility gain. The interactive jobs arrive to the system over time, and are allowed to be partially executed before their deadlines. We focus on the preemptive scenario, where a job in service can be interrupted by other jobs, and its service can be resumed later. We propose a deadline agnostic scheduler, called ISPEED (Interactive Services with Partial Execution and Deadlines). Being deadline agnostic is an attractive property of ISPEED because data center schedulers are often not privy to individual job deadlines, and thus schedulers that are deadline dependent may not be amenable to implementation. We first prove that ISPEED achieves the maximum total utility when jobs have homogeneous deadlines and their utility functions are non-decreasing and concave. Then, in the case of heterogeneous job deadlines we prove that ISPEED achieves a competitive ratio of 2 + α, where α is a shape parameter for a large class of non-decreasing utility functions. In the special case of α = 0, i.e., The utility functions are concave, ISPEED has a competitive ratio of 2, while no causal scheduler can achieve a competitive ratio smaller than ½5+1/2. Finally, we show through trace-driven simulations that ISPEED outperforms the state-of-the-art schedulers in a wide range of scenarios.

One key requirement for storage clouds is to be able to retrieve data quickly. Recent system measurements have shown that the data retrieving delay in storage clouds is highly variable, which may result in a long latency tail. One crucial idea to improve the delay performance is to retrieve multiple data copies by using parallel downloading threads. However, how to optimally schedule these downloading threads to minimize the data retrieving delay remains to be an important open problem. In this paper, we develop low-complexity thread scheduling policies for several important classes of data downloading time distributions, and prove that these policies are either delay-optimal or within a constant gap from the optimum delay performance. These theoretical results hold for an arbitrary arrival process of read requests that may contain finite or infinite read requests, and for heterogeneous MDS storage codes that can support diverse storage redundancy and reliability requirements for different data files. Our numerical results show that the delay performance of the proposed policies is significantly better than that of First-Come-First-Served (FCFS) policies considered in prior work.

The recent breakthrough in wireless full-duplex communication makes possible a brand new way of multi-hop wireless communication, namely full-duplex cut-through transmission, where for a traffic flow that traverses through multiple links, every node along the route can receive a new packet and simultaneously forward the previously received packet. This wireless transmission scheme brings new challenges in the design of MAC layer algorithms that aim to reap its full benefit. First, the MAC layer rate region of the cut-through enabled network is directly a function of the routing decision, leading to a strong coupling between routing and scheduling. Second, it is unclear how to dynamically form/change cut-through routes based on the traffic rates and patterns. In this work, we introduce a novel method to characterize the interference relationship between links in the network with cut-through transmission, which decouples the routing decision with the scheduling decision and enables a seamless adaptation of traditional half-duplex routing/scheduling algorithm into wireless networks with full-duplex cut-through capabilities. Based on this interference model, a queue-length based CSMA-type scheduling algorithm is proposed, which both leverages the flexibility of full-duplex cut-through transmission and permits distributed implementation.

The number and size of data centers has seen a rapid growth in the last few years. It is no longer uncommon to see large data centers with thousands or even tens of thousands of machines. Hence, it is critical to develop scalable scheduling mechanisms for processing the enormous number of jobs handled by popular paradigms such as the MapReduce framework. This work explores the possibility of simplifying the scheduling procedure by exploiting the “largeness” of the data center system. Specifically, we consider the problem of minimizing the total flow time of a sequence of jobs under the MapReduce framework, where the jobs arrive over time and need to be processed through both Map and Reduce procedures before leaving the system. We show that any work-conserving scheduler is asymptotically optimal under a wide range of traffic loads, including the heavy traffic limit. Our results are shown for scenarios in which the tasks can be preempted and served in parallel over different machines, as well as scenarios when each task has to be served only on one machine and cannot be preempted. This result implies, somewhat surprisingly, that when we have a large number of machines, there is little to be gained by optimizing beyond ensuring that a scheduler should be work-conserving. For long running applications, we also study the relationship between the number of machines and total running time, and show sufficient conditions to guarantee the asymptotic optimality of work-conserving schedulers. Further, we run extensive simulations, that indeed verify that when the total number of machines is large, state-of-the-art work-conserving schedulers have similar and close-to-optimal delay performance.

We are in the midst of a major data revolution. The total data generated by humans from the dawn of civilization until the turn of the new millennium is now being generated every two days. Driven by a wide range of data-intensive devices and applications, this growth is expected to continue its astonishing march, and fuel the development of new and larger data centers. In order to exploit the low-cost services offered by these resource-rich data centers, application developers are pushing computing and storage away from the end-devices and instead deeper into the data-centers. Hence, the end-users' experience is now dependent on the performance of the algorithms used for data retrieval, and job scheduling within the data-centers. In particular, providing low-latency services are critically important to the end-user experience for a wide variety of applications. Our goal has been to develop the analytical foundations and methodologies to enable cloud storage and computing solutions that result in low-latency services. In this talk, I will overview some of the recent research efforts at fast data retrieval in these large-scale data center systems. Specifically, our focus will be on the new tools and techniques required to address these complex issues, the progress made, and the open challenges that remain.

A major challenge of wireless multicast is being able to support a large number of users while simultaneously maintaining low delay and low feedback overhead. In this paper, we develop a joint coding and feedback scheme named moving window network coding with anonymous feedback (MWNC-AF) that simultaneously achieves constant decoding delay and constant feedback overhead, irrespective of the number of receivers n, without sacrificing either throughput or reliability. We explicitly characterize the asymptotic decay rate of the tail probability of the decoding delay and prove that injecting a fixed amount of information bits into the MWNC-AF encoder buffer in each time slot (called “constant data injection process”) achieves the fastest decay rate, thus showing how to obtain delay optimality in a large deviation sense. We then investigate the average decoding delay of MWNC-AF and show that, when the traffic load approaches capacity, the average decoding delay under the constant injection process is at most one half of that under a Bernoulli injection process. We prove that the per-packet encoding and decoding complexities of MWNC-AF both scale as O(logn) and are thus insensitive to the increase of the number of receivers n. Our simulations further underscore the performance of our scheme through comparisons with existing schemes and show that the delay, encoding, and decoding complexities are low even for a large number of receivers, demonstrating the efficiency, scalability, and ease of implementability of MWNC-AF.

This paper introduces the vector sparse matrix transform (vector SMT), a new decorrelating transform suitable for performing distributed processing of high-dimensional signals in sensor networks. We assume that each sensor in the network encodes its measurements into vector outputs instead of scalar ones. The proposed transform decorrelates a sequence of pairs of vector outputs, until these vectors are decorrelated. In our experiments, we simulate distributed anomaly detection by a network of cameras, monitoring a spatial region. Each camera records an image of the monitored environment from its particular viewpoint and outputs a vector encoding the image. Our results, with both artificial and real data, show that the proposed vector SMT transform effectively decorrelates image measurements from the multiple cameras in the network while maintaining low overall communication energy consumption. Since it enables joint processing of the multiple vector outputs, our method provides significant improvements to anomaly detection accuracy when compared with the baseline case when the images are processed independently.

We study opportunistic multiuser scheduling in downlink networks with Markov-modeled outage channels. We consider the scenario that the scheduler does not have full knowledge of the channel state information, but instead estimates the channel state by exploiting the memory inherent in the Markov channels along with Automatic-Repeat-reQues-styled-styled feedback from the scheduled users. Opportunistic scheduling is optimized in two stages: 1) channel estimation and rate adaptation are performed to maximize the short-term throughput, i.e., the successful transmission rate of the scheduled user in the current slot and 2) user scheduling is performed, based on the short-term throughput, to maximize the overall long-term sum-throughput of the downlink. The scheduling problem is a partially observable Markov decision process with the classic exploitation versus exploration tradeoff that is difficult to quantify. We, therefore, study the problem in the framework of restless multiarmed bandit processes, and perform a Whittle's indexability analysis. Whittle's indexability is traditionally known to be hard to establish and the index policy derived based on Whittle's indexability is known to have optimality properties in various settings. We show that the problem of downlink scheduling under imperfect channel state information is Whittle indexable and derive the Whittle's index policy in closed form. Through extensive numerical experiments, we show that the Whittle's index policy has near-optimal performance and is robust against various imperfections in channel state feedback. Our work reveals that, under incomplete channel state information, exploiting channel memory for opportunistic scheduling can result in significant system-level performance gains and that almost all of these gains can be realized using the polynomial-complexity Whittle's index policy.

Cognitive radio networks allow unlicensed users to access licensed spectrum opportunistically without disrupting primary user (PU) communication. Developing a distributed implementation that can fully utilize the spectrum opportunities for secondary users (SUs) has so far remained elusive. Although throughput optimal algorithms based on the well-known maximal weight scheduling (MWS) algorithm exist for cognitive radio networks, they require central processing of network-wide SU information. In this paper, a new distributed algorithm is introduced that asymptotically achieves the capacity region of the cognitive radio systems. The proposed algorithm achieves the full SU capacity region while adapting to the channel availability dynamics caused by unknown primary user activity. Extensive simulation results are provided to illustrate the efficacy of the algorithm.

In this paper, we focus on the scheduling problem in multichannel wireless networks, e.g., the downlink of a single cell in fourth-generation (4G) OFDM-based cellular networks. Our goal is to design practical scheduling policies that can achieve provably good performance in terms of both throughput and delay, at a low complexity. While a class of O(n2.5log n)-complexity hybrid scheduling policies is recently developed to guarantee both rate-function delay optimality (in the many-channel many-user asymptotic regime) and throughput optimality (in the general non-asymptotic setting), their practical complexity is typically high. To address this issue, we develop a simple greedy policy called Delay-based Server-Side-Greedy (D-SSG) with a lower complexity 2n2+2n, and rigorously prove that D-SSG not only achieves throughput optimality, but also guarantees near-optimal asymptotic delay performance. Specifically, the rate-function of the delay-violation probability attained by D-SSG for any fixed integer delay threshold b > 0 is no smaller than the maximum achievable rate-function by any scheduling policy for threshold b-1. Thus, we are able to achieve a reduction in complexity (from O(n2.5logn) of the hybrid policies to 2n2+ 2n) with a minimal drop in the delay performance. More importantly, in practice, D-SSG generally has a substantially lower complexity than the hybrid policies that typically have a large constant factor hidden in the O(·) notation. Finally, we conduct simulations to validate our theoretical results in various scenarios. The simulation results show that in all scenarios we consider, D-SSG not only guarantees a near-optimal rate-function, but also empirically has a similar delay performance to the rate-function delay-optimal policies.

In this paper, we characterize the throughput of a broadcast network with n receivers using rateless codes with block size K. We assume that the underlying channel is a Markov modulated erasure channel that is i.i.d. across users, but can be correlated in time. We characterize the system throughput asymptotically in n. Specifically, we explicitly show how the throughput behaves for different values of the coding block size K as a function of n, as n→ ∞. For finite values of K and n, under the more restrictive assumption of Gilbert-Elliott erasure channels, we are able to provide a lower bound on the maximum achievable throughput. Using simulations, we show the tightness of the bound with respect to system parameters n and K and find that its performance is significantly better than the previously known lower bounds.

Storage clouds, such as Amazon S3, are being widely used for web services and Internet applications. It has been observed that the delay for retrieving data from and placing data into the clouds is quite random, and exhibits weak correlations between different read/write requests. This inspires us to investigate a key problem: can we reduce the delay by transmitting data replications in parallel or using powerful erasure codes? In this paper, we study the problem of reducing the delay of downloading data from cloud storage systems by leveraging multiple parallel threads, assuming that the data has been encoded and stored in the clouds using fixed rate forward error correction (FEC) codes with parameters (n, k). That is., each file is divided into k equal-sized chunks, which are then expanded into n chunks such that any k chunks out of the n are sufficient to successfully restore the original file. The model can be depicted as a multiple-server queue with arrivals of data retrieving requests and a server corresponding to a thread. However, this is not a typical queueing model because a server can terminate its operation, depending on when other servers complete their service (due to the redundancy that is spread across the threads). Hence, to the best of our knowledge, the analysis of this queueing model remains quite uncharted. Real traces from Amazon S3 show that the time to retrieve a fixed size chunk is random and can be accurately approximated as an i.i.d. exponentially distributed random variable. We show that any work-conserving scheme is delay-optimal when k = 1. When k > 1, we find that a simple greedy scheme, which allocates all available threads to the head of line request, is delay optimal, which appears surprising.

Many opportunistic scheduling techniques are impractical because they require accurate channel state information (CSI) at the transmitter. In this paper, we investigate the scheduling of unicast and multicast services in a downlink network with a very limited amount of feedback information. Specifically, unicast users send imperfect (or no) CSI and infrequent acknowledgements (ACKs) to a base station, and multicast users only report infrequent ACKs to avoid feedback implosion. We consider the use of physical-layer rateless codes, which not only combats channel uncertainty, but also reduces the overhead of ACK feedback. A joint scheduling and power allocation scheme is developed to realize multiuser diversity gain for unicast service and multicast gain for multicast service. We prove that our scheme achieves a near-optimal throughput region. Our simulation results show that our scheme significantly improves the network throughput over schemes employing fixed-rate codes or using only unicast communications.

Recent breakthroughs in wireless communication show that by using new signal processing techniques, a wireless node is capable of transmitting and receiving simultaneously on the same frequency band by activating both of its RF chains, thus achieving full-duplex communication and potentially doubling the link throughput. However, with two sets of RF chains, one can build a half-duplex multi-input and multi-output (MIMO) system that achieves the same gain. While this gain is the same between a pair of nodes, the gains are unclear when multiple nodes are involved, as in a general network. The key reason is that MIMO and full-duplex have different interference patterns. A MIMO transmission blocks transmissions around its receiver and receptions around its transmitter. A full-duplex bidirectional transmission blocks any transmission around the two communicating nodes, but allows a reception on one RF chain. Thus, in a general network, the requirements for the two technologies could result in potentially different achievable throughput regions. This work investigates the achievable throughput performance of MIMO, full-duplex and their variants that allow simultaneous activation of two RF chains. It is the first work of its kind to precisely characterize the conditions under which these technologies outperform each other for a general network topology under a binary interference model. The analytical results in this paper are validated using software-defined radios.

Smart mobile devices are generating a tremendous amount of data traffic that is putting stress on even the most advanced cellular networks. Delayed offloading has recently been proposed as an efficient mechanism to substantially alleviate this stress. The idea is simple. It allows a mobile device to delay transmission of data packets for a certain amount of time, while it searches WiFi (or similarly femtocell) networks to offload the data during the time. When the time expires, it completes the remaining portion of the delayed transmission through the cellular network that is available at the moment. In this paper, we develop an analytical framework using an embedded Markov process for the delayed offloading system. We provide a closed-form expression for estimating how much data generated by the users can be offloaded to WiFi networks from cellular networks even when there are non-Markovian data arrivals and service interruptions. We conduct extensive numerical studies with various ranges of delay, service interruption time, arrived data, and service rate. These numerical studies show that the current deployment of WiFi networks measured from a metropolitan city is capable of offloading about 80% of the generated data with 30 minutes of delay and 1 Mbps of WiFi data rate, but increasing the data rate does not help improve the amount of offloading. Further studies using this framework on two new deployment strategies of WiFi networks give guidance on how to upgrade WiFi networks by revealing that the amount of offloading for 30 minutes of delay and 1 Mbps of data rate can be drastically improved to about 90% or 98% according to the strategy.

We study the stochastic multi-armed bandit (MAB) problem in the presence of side-observations across actions. In our model, choosing an action provides additional side observations for a subset of the remaining actions. One example of this model occurs in the problem of targeting users in online social networks where users respond to their friends's activity, thus providing information about each other's preferences. Our contributions are as follows: 1) We derive an asymptotic (with respect to time) lower bound (as a function of the network structure) on the regret (loss) of any uniformly good policy that achieves the maximum long term average reward. 2) We propose two policies - a randomized policy and a policy based on the well-known upper confidence bound (UCB) policies, both of which explore each action at a rate that is a function of its network position. We show that these policies achieve the asymptotic lower bound on the regret up to a multiplicative factor independent of network structure. The upper bound guarantees on the regret of these policies are better than those of existing policies. Finally, we use numerical examples on a real-world social network to demonstrate the significant benefits obtained by our policies against other existing policies.

In this paper, we consider the problem of distributed load shedding optimization for disaster recovery in smart grids. We develop distributed second-order interior-point based load shedding algorithms that enjoy a fast quadratic convergence rate. Our main contributions are two-fold: (i) We propose a rooted spanning tree based reformulation that enables our distributed algorithm design; (ii) Based on the spanning tree reformulation, we design distributed computation schemes for our proposed second-order interior-point based load shedding. Collectively, these results serve as an important first step in load shedding and disaster recovery that uses second-order distributed techniques.

OFDMA has been selected as the multiple access scheme for emerging broadband wireless communication systems. However, designing efficient resource allocation algorithms for OFDMA systems is a challenging task, especially in the uplink, due to the combinatorial nature of subcarrier assignment and the distributed power budget for different users. Inspired by Glauber dynamics, in this paper, we propose a randomized iteration-based uplink OFDMA resource allocation algorithm. We show that our algorithm is near-optimal in the sense that by increasing the number of iterations (which scales up the complexity), with arbitrarily large probability, the algorithm can converge to the subcarrier/power allocation pattern with the maximum sum-utility. We also show that this algorithm can be generalized to solve a joint uplink-downlink allocation problem in full-duplex OFDMA systems. Simulations are conducted to compare the performance of our algorithm with existing ones.

Recent studies have shown that retransmissions can cause heavy-tailed transmission delays even when packet sizes are light tailed. In addition, the impact of heavy-tailed delays persists even when packets size are upper bounded. The key question we study in this paper is how the use of coding techniques to transmit information, together with different system configurations, would affect the distribution of delay. To investigate this problem, we model the underlying channel as a Markov modulated binary erasure channel, where transmitted bits are either received successfully or erased. Erasure codes are used to encode information prior to transmission, which ensures that a fixed fraction of the bits in the codeword can lead to successful decoding. We use incremental redundancy codes, where the codeword is divided into codeword trunks and these trunks are transmitted one at a time to provide incremental redundancies to the receiver until the information is recovered. We characterize the distribution of delay under two different scenarios: 1) decoder uses memory to cache all previously successfully received bits and 2) decoder does not use memory, where received bits are discarded if the corresponding information cannot be decoded. In both cases, we consider codeword length with infinite and finite support. From a theoretical perspective, our results provide a benchmark to quantify the tradeoff between system complexity and the distribution of delay.

In this paper, we investigate the utility maximization problem for a sensor network with energy replenishment. Each sensor node consumes energy in its battery to generate and deliver data to its destination via multihop communications. Although the battery can be replenished from renewable energy sources, the energy allocation should be carefully designed in order to maximize system performance, especially when the replenishment profile is unknown in advance. In this paper, we address the joint problem of energy allocation and routing to maximize the total system utility, without prior knowledge of the replenishment profile. We first characterize optimal throughput of a single node under general replenishment profile and extend our idea to the multihop network case. After characterizing the optimal network utility with an upper bound, we develop a low-complexity online solution that achieves asymptotic optimality. Focusing on long-term system performance, we can greatly simplify computational complexity while maintaining high performance. We also show that our solution can be approximated by a distributed algorithm using standard optimization techniques. In addition, we show that the required battery size is O(ln(1/ξ)) to constrain the performance of our scheme within ξ-neighborhood of the optimum. Through simulations with replenishment profile traces for solar and wind energy, we numerically evaluate our solution, which outperforms a state-of-the-art scheme that is developed based on the Lyapunov optimization technique.

Link adaptation technologies, such as Adaptive Modulation and Coding (AMC) and Multiple-Input-Multiple-Output (MIMO), are used in advanced wireless communication systems to achieve high spectrum efficiency. Communication performance can be improved significantly by adaptive transmissions based on the quality of received signals, i.e., the signal-to-interference-plus-noise ratio (SINR). However, for multihop wireless communications, most link scheduling schemes have been developed under simplified interference models that do not account for accumulative interference and cannot fully exploit the recent advances in PHY-layer communication theory. This paper focuses on developing link scheduling schemes that can achieve optimal performance under the SINR model. One key idea is to treat an adaptive wireless link as multiple parallel virtual links with different signal quality, building on which we develop throughput-optimal scheduling schemes using a two-stage queueing structure in conjunction with recently developed carrier-sensing techniques. Furthermore, we introduce a novel three-way handshake to ensure, in a distributed manner, that all transmitting links satisfy their SINR requirements. We evaluate the proposed schemes through rigorous analysis and simulations.

We investigate the problem of minimizing the sum of the queue lengths of all the nodes in a wireless network with a forest topology. Each packet is destined to one of the roots (sinks) of the forest. We consider a time-slotted system and a primary (or one-hop) interference model. We characterize the existence of causal sample-path optimal scheduling policies for this network topology under this interference model. A causal sample-path optimal scheduling policy is one for which at each time-slot, and for any sample-path traffic arrival pattern, the sum of the queue lengths of all the nodes in the network is minimum among all policies. We show that such policies exist in restricted forest structures, and that for any other forest structure, there exists a traffic arrival pattern for which no causal sample-path optimal policy can exist. Surprisingly, we show that many forest structures for which such policies exist can be scheduled by converting the structure into an equivalent linear network and scheduling the equivalent linear network according to the one-hop interference model. The nonexistence of such policies in many forest structures underscores the inherent limitation of using sample-path optimality as a performance metric and necessitates the need to study other (relatively) weaker metrics of delay performance.

In this paper, we study the scheduling problem for downlink transmission in a multichannel (e.g., OFDM-based) wireless network. We focus on a single cell, with the aim of developing a unifying framework for designing low-complexity scheduling policies that can provide optimal performance in terms of both throughput and delay. We develop new easy-to-verify sufficient conditions for rate-function delay optimality (in the many-channel many-user asymptotic regime) and throughput optimality (in general nonasymptotic setting), respectively. The sufficient conditions allow us to prove rate-function delay optimality for a class of Oldest Packets First (OPF) policies and throughput optimality for a large class of Maximum Weight in the Fluid limit (MWF) policies, respectively. By exploiting the special features of our carefully chosen sufficient conditions and intelligently combining policies from the classes of OPF and MWF policies, we design hybrid policies that are both rate-function delay-optimal and throughput-optimal with a complexity of O(n2.5log n), where n is the number of channels or users. Our sufficient condition is also used to show that a previously proposed policy called Delay Weighted Matching (DWM) is rate-function delay-optimal. However, DWM incurs a high complexity of O(n5). Thus, our approach yields significantly lower complexity than the only previously designed delay and throughput-optimal scheduling policy. We also conduct numerical experiments to validate our theoretical results.

In this paper, we study the implication of wireless broadcast for data aggregation in lossy wireless sensor networks. Each sensor node generates information by sensing its physical environment and transmits the data to a special node called the sink, via multihop communications. The goal of the network system is to compute a function at the sink from the information gathered by spatially distributed sensor nodes. In the course of collecting information, in-network computation at intermediate forwarding nodes can substantially increase network efficiency by reducing the number of transmissions. On the other hand, it also increases the amount of the information contained in a single packet and makes the system vulnerable to packet loss. Instead of retransmitting lost packets, which incurs additional delay, we develop a wireless system architecture that exploits the diversity of the wireless medium for reliable operations. To elaborate, we show that for a class of aggregation functions, wireless broadcasting is an effective strategy to improve delay performance while satisfying reliability constraint. We provide scaling law results on the performance improvement of our solution over unicast architecture with retransmissions. Interestingly, the improvement depends on the transmission range as well as the reliability constraint.

Cognitive radio networks (CRNs) allow unlicensed users to opportunistically access the licensed spectrum without causing disruptive interference to the primary users (PUs). One of the main challenges in CRNs is the ability to detect PU transmissions. Recent works have suggested the use of secondary user (SU) cooperation over individual sensing to improve sensing accuracy. In this paper, we consider a CRN consisting of multiple PUs and SUs to study the problem of maximizing the total expected system throughput. First, we study the sensing decision problem for maximizing the system throughput subject to a constraint on the PU throughput, and we design a Bayesian decision rule-based algorithm. The problem is shown to be strongly NP-hard and solved via a greedy algorithm with time complexity O([(N5)/(log2[1/(1-ε)])]), where N is the total number of SUs. The algorithm achieves a throughput strictly greater than 1/2(1-ε) of the optimal solution and results in a small constraint violation that goes to zero with ε. We then investigate the more general problem with constraints on both PU throughput and the sensing time overhead, which limits the number of SUs that can participate in cooperative sensing. We illustrate the efficacy of the performance of our algorithms and provide sensitivity analysis via a numerical investigation.

Retransmissions serve as the basic building block that communication protocols use to achieve reliable data transfer. Until recently, the number of retransmissions was thought to follow a geometric (light-tailed) distribution. However, recent work shows that when the distribution of the packet sizes have infinite support, retransmission-based protocols may result in heavy-tailed delays and possibly zero throughput even when the aforementioned distribution is light-tailed. In reality, however, packet sizes are often bounded by the maximum transmission unit (MTU), and thus the aforementioned result merits a deeper investigation. To that end, in this paper, we allow the distribution of the packet size$L$to have finite support. Under mild conditions, we show that the transmission duration distribution exhibits a transition from a power-law main body to an exponential tail. The timescale to observe the power-law main body is roughly equal to the average transmission duration of the longest packet. The power-law main body, if significant, may cause the channel throughput to be very close to zero. These theoretical findings provide an understanding on why some empirical measurements suggest heavy tails. We use these results to further highlight the engineering implications of distributions with power-law main bodies and light tails by analyzing two cases: 1) the throughput of on–off channels with retransmissions, where we show that even when packet sizes have small means and bounded support the variability in their sizes can greatly impact system performance; 2) the distribution of the number of jobs in an$M/M/\infty$queue with server failures. Here, we show that retransmissions can cause long-range dependence and quantify the impact of the maximum job sizes on the long-range dependence.

In this paper, we focus on mobile wireless networks comprising of a powerful communication center and a multitude of mobile users. We investigate the propagation of deadline-based content in the wireless network characterized by heterogeneous (time-varying and user-dependent) wireless channel conditions, heterogeneous user mobility, and where communication could occur in a hybrid format (e.g., directly from the central controller or by exchange with other mobiles in a peer-to-peer manner). We show that exploiting double opportunities, i.e., both time-varying channel conditions and mobility, can result in substantial performance gains. We develop a class of double opportunistic multicast schedulers and prove their optimality in terms of both utility and fairness under heterogeneous channel conditions and user mobility. Extensive simulation results are provided to demonstrate that these algorithms can not only substantially boost the throughput of all users (e.g., by 50% to 150%), but also achieve different consideration of fairness among individual users and groups of users.

In this paper, we focus on the scheduling problem in multi-channel wireless networks, e.g., the downlink of a single cell in fourth generation (4G) OFDM-based cellular networks. Our goal is to design efficient scheduling policies that can achieve provably good performance in terms of both throughput and delay, at a low complexity. While a recently developed scheduling policy, called Delay Weighted Matching (DWM), has been shown to be both rate-function delay-optimal (in the many-channel many-user asymptotic regime) and throughput-optimal (in general non-asymptotic setting), it has a high complexity O(n5), which makes it impractical for modern OFDM systems. To address this issue, we first develop a simple greedy policy called Delay-based Queue-Side-Greedy (D-QSG) with a lower complexity O(n3), and rigorously prove that D-QSG not only achieves throughput optimality, but also guarantees near-optimal rate-function-based delay performance. Specifically, the rate-function attained by D-QSG for any fixed integer threshold b>0, is no smaller than the maximum achievable rate-function by any scheduling policy for threshold b-1. Further, we develop another simple greedy policy called Delay-based Server-Side-Greedy (D-SSG) with an even lower complexity O(n2), and show that D-SSG achieves the same performance as D-QSG. Thus, we are able to achieve a dramatic reduction in complexity (from O(n5) of DWM to O(n2)) with a minimal drop in the delay performance. Finally, we conduct numerical simulations to validate our theoretical results in various scenarios. The simulation results show that our proposed greedy policies not only guarantee a near-optimal rate-function, but also empirically are virtually indistinguishable from the delay-optimal policy DWM.

In this paper, we focus on the issue of stability in multihop wireless networks under flow-level dynamics, and explore the inefficiency and instability of the celebrated Back-Pressure algorithms. It has been well-known that the Back-Pressure (or Max-Weight) algorithms achieve queue stability and throughput optimality in a wide variety of scenarios. Yet, these results all rely on the assumptions that the set of flows is fixed, and that all the flows are long-lived and keep injecting packets into the network. Recently, in the presence of flow-level dynamics, where flows arrive and request to transmit a finite amount of packets, it has been shown that the Max-Weight algorithms may not guarantee stability due to channel fading or inefficient spatial reuse. However, these observations are made only for single-hop traffic, and thus have resulted in partial solutions that are limited to the single-hop scenarios. An interesting question is whether straightforward extensions of the previous solutions to the known instability problems would achieve throughput optimality in multihop traffic setting. To answer the question, we explore potential inefficiency and instability of the Back-Pressure algorithms, and provide interesting examples that are useful to obtain insights into developing an optimal solution. We also conduct simulations to further illustrate the instability issue of the Back-Pressure algorithms in various scenarios. Our study reveals that new types of inefficiencies may arise in the settings with multihop traffic due to underutilization of the link capacity or inefficient routing, and the stability problem becomes more challenging than in the single-hop traffic counterpart.

Regulating the ISPs to adopt more security measures has been proposed as an effective method in mitigating the threats of attacks in the Internet. However, economic incentives of the ISPs and the network effects of security measures can lead to an under-investment in their adoption. We study the potential gains in a network's social utility when a regulator implements a monitoring and penalizing mechanism on the outbound threat activities of autonomous systems (ASes). We then show how freeriding can render regulations futile if the subset of ASes under the regulator's authority is smaller than a threshold. Finally, we show how heterogeneity of the ASes affect the responses of the ISPs and discuss how the regulator can leverage such information to improve the overall effectiveness of different security policies.

A variety of mathematical tools have been developed for predicting the spreading patterns in a number of varied environments including infectious diseases, computer viruses, and urgent messages broadcast to mobile agents (e.g., humans, vehicles, and mobile devices). These tools have mainly focused on estimating the average time for the spread to reach a fraction (e.g., α) of the agents, i.e., the so-called average completion time E(Tα). We claim that providing probabilistic guarantee on the time for the spread Tαrather than only its average gives a much better understanding of the spread, and hence could be used to design improved methods to prevent epidemics or devise accelerated methods for distributing data. To demonstrate the benefits, we introduce a new metric Gα,βthat denotes the time required to guarantee α completion with probability β, and develop a new framework to characterize the distribution of Tαfor various spread parameters such as number of seeds, level of contact rates, and heterogeneity in contact rates. We apply our technique to an experimental mobility trace of taxies in Shanghai and show that our framework enables us to allocate resources (i.e., to control spread parameters) for acceleration of spread in a far more efficient way than the state-of-the-art.

In Cognitive Radio Networks (CRNs), secondary users (SUs) are allowed to opportunistically access the unused/under-utilized channels of primary users (PUs). To utilize spectrum resources efficiently, an auction scheme is often applied where an operator serves as an auctioneer and accepts spectrum requests from SUs. Most existing works on spectrum auctions assume that the operator has perfect knowledge of PU activities. In practice, however, it is more likely that the operator only has statistical information of the PU traffic when it is trading a spectrum hole, and it is acquiring more accurate information in real time. In this paper, we distinguish PU channels that are under the control of the operator, where accurate channel states are revealed in real-time, and channels that the operator acquires from PUs out of its control, where a sense-before-use paradigm has to be followed. Considering both spectrum uncertainty and sensing inaccuracy, we study the social welfare maximization problem for serving SUs with various levels of delay tolerance. We first model the problem as a finite horizon Markov decision process when the operator knows all spectrum requests in advance, and propose an optimal dynamic programming based algorithm. We then investigate the case when spectrum requests are submitted online, and propose a greedy algorithm that is 1/2-competitive for homogeneous channels and is comparable to the offline algorithm for more general settings. We further extend the online algorithm to an online auction scheme, which ensures incentive compatibility for the SUs and also provides a way for trading off social welfare and revenue.

Due to the rapidly growing scale and heterogeneity of wireless networks, the design of distributed cross-layer optimization algorithms has received significant interest from the networking research community. So far, the standard distributed cross-layer approach in the literature is based on the first-order Lagrangian dual decomposition and the subgradient method, which suffers from a slow convergence rate. In this paper, we make the first known attempt to develop a distributed Newton's method, which is second-order and enjoys a quadratic convergence rate. However, due to the inherent interference in wireless networks, the Hessian matrix of the cross-layer problem has a non-separable structure. As a result, developing a distributed second-order algorithm is far more difficult than its counterpart for wireline networks. Our main contributions in this paper are two-fold: i) For a special network setting where all links mutually interfere, we derive closed-form expressions for the Hessian inverse, which further yield a distributed Newton's method; ii) For general wireless networks where the interference relationships are arbitrary, we propose a double matrix-splitting scheme, which also leads to a distributed Newton's method. Collectively, these results create a new theoretical framework for distributed cross-layer optimization in wireless networks. More importantly, our work contributes to a potential second-order paradigm shift in wireless networks optimization theory.

The problem of online job or packet scheduling with hard deadlines has been studied extensively in the single hop setting, whereas it is notoriously difficult in the multihop setting. This difficulty stems from the fact that packet scheduling decisions at each hop influences and are influenced by decisions on other hops and only a few provably efficient online scheduling algorithms exist in the multihop setting. We consider a general multihop network topology in which packets with various deadlines and weights arrive at and are destined to different nodes through given routes. We study the problem of joint admission control and packet scheduling in order to maximize the cumulative weights of the packets that reach their destinations within their deadlines. We first focus on uplink transmissions in the tree topology and show that the well known earliest deadline first algorithm achieves the same performance as the optimal off-line algorithm for any feasible arrival pattern. We then address the general topology with multiple source-destination pairs, develop a simple online algorithm and show that it is O(PM log PM)-competitive where PM is the maximum route length among all packets. Our algorithm only requires information along the route of each packet and our result is valid for general arrival samples. Via numerical results, we show that our algorithm achieves performance that is comparable to the non-causal optimal off-line algorithm. To the best of our knowledge, this is the first algorithm with a provable (based on a sample-path construction) competitive ratio, subject to hard deadline constraints for general network topologies.

Wireless network scheduling and control techniques (e.g., opportunistic scheduling) rely heavily on access to Channel State Information (CSI). However, obtaining this information is costly in terms of bandwidth, time, and power, and could result in large overhead. Therefore, a critical question is how to optimally manage network resources in the absence of such information. To that end, we develop a cross-layer solution for downlink cellular systems with imperfect (and possibly no) CSI at the transmitter. We use rateless codes to resolve channel uncertainty. To keep the decoding complexity low, we explicitly incorporate time-average block-size constraints, and aim to maximize the system utility. The block-size of a rateless code is determined by both the network control decisions and the unknown CSI of many time slots. Therefore, unlike standard utility maximization problems, this problem can be viewed as a constrained partial observed Markov decision problem (CPOMDP), which is known to be hard due to the “curse of dimensionality.” However, by using a modified Lyapunov drift method, we develop a dynamic network control scheme, which yields a total network utility within O(1/Lav) of utility-optimal point achieved by infinite block-size channel codes, where Lavis the enforced value of the time-average block-size of rateless codes. This opens the door of being able to trade complexity/delay for performance gains in the absence of accurate CSI. Our simulation results show that the proposed scheme improves the network throughput by up to 68% over schemes that use fixed-rate codes.

With the rapid increase in size and number of jobs that are being processed in the MapReduce framework, efficiently scheduling jobs under this framework is becoming increasingly important. We consider the problem of minimizing the total flowtime of a sequence of jobs in the MapReduce framework, where the jobs arrive over time and need to be processed through both Map and Reduce procedures before leaving the system. We show that for this problem for non-preemptive tasks, no on-line algorithm can achieve a constant competitive ratio (defined as the ratio between the completion time of the online algorithm to the completion time of the optimal non-causal off-line algorithm). We then construct a slightly weaker metric of performance called the efficiency ratio. An online algorithm is said to achieve an efficiency ratio of γ when the flow-time incurred by that scheduler divided by the minimum flow-time achieved over all possible schedulers is almost surely less than or equal to γ. Under some weak assumptions, we then show a surprising property that, for the flow-time problem, any work-conserving scheduler has a constant efficiency ratio in both preemptive and nonpreemptive scenarios. More importantly, we are able to develop an online scheduler with a very small efficiency ratio (2), and through simulations we show that it outperforms the state-of-the-art schedulers.

This paper considers reliable communications over a multiple-input multiple-output (MIMO) Gaussian channel, where the channel matrix is within a bounded channel uncertainty region around a nominal channel matrix, i.e., an instance of the compound MIMO Gaussian channel. We study the optimal transmit covariance design to achieve the capacity of compound MIMO Gaussian channels, where the channel uncertainty region is characterized by the spectral norm. This design problem is a challenging non-convex optimization problem. However, in this paper, we reveal that this design problem has a hidden convexity property, and hence it can be simplified as a convex optimization problem. Towards this goal, we first prove that the optimal transmit design is to diagonalize the nominal channel, and then show that the duality gap between the capacity of the compound MIMO Gaussian channel and the minimal channel capacity is zero, which proves the conjecture of Loyka and Charalambous (IEEE Trans. Inf. Theory, vol. 58, no. 4, pp. 2048-2063, 2012). The key tools for showing these results are a novel matrix determinant inequality and some unitarily invariant properties.

Developing scheduling mechanisms that can simultaneously achieve throughput optimality and good delay performance often require solving the Maximum Independent Weighted Set (MWIS) problem. However, under most realistic network settings, the MWIS problem can be shown to be NP-hard. In non-fading environments, low-complexity scheduling algorithms have been provided that converge either to the MWIS solution in time or to a solution that achieves at least a provable fraction of the achievable throughput. However, in more practical systems the channel conditions can vary at faster time-scales than convergence occurs in these lower-complexity algorithms. Hence, these algorithms cannot take advantage of the opportunistic gain, and may no longer guarantee good performance. In this paper, we propose a low-complexity scheduling scheme that performs provably well under fading channels and is amenable to implement in a distributed manner. To the best of our knowledge, this is the first scheduling scheme under fading environments that requires only local information, has a low complexity that grows logarithmically with the network size, and achieves provable performance guarantees (which is arbitrarily close to that of the well-known centralized Greedy Maximal Scheduler). Through simulations we verify that both the throughput and the delay under our proposed distributed scheduling scheme are close to that of the optimal solution to MWIS. Further, we implement a preliminary version of our algorithm in a testbed by modifying the existing IEEE 802.11 DCF. The preliminary experiment results show that our implementation successfully accounts for wireless fading, and attains the opportunistic gains in practice, and hence substantially outperforms IEEE 802.11 DCF.

The smart grid is the new generation of electricity grid that can efficiently utilize new distributed sources of energy (e.g., harvested renewable energy), and allow for dynamic electricity price. In this paper, we investigate the cost minimization problem for an end-user, such as a home, community, or a business, which is equipped with renewable energy devices when electrical appliances allow different levels of delay tolerance. The varying price of electricity presents an opportunity to reduce the electricity bill from an end-user's point of view by leveraging the flexibility to schedule operations of various appliances and HVAC systems. We assume that the end user has an energy storage battery as well as an energy harvesting device so that harvested renewable energy can be stored and later used when the price is high. The energy storage battery can also draw energy from the external grid. The problem we formulate here is to minimize the cost of the energy drawn from the external grid while usage of appliances are subject to individual delay constraints and a long-term average delay constraint. The resulting algorithm requires some future information regarding electricity prices, but it achieves provable performance without requiring future knowledge of either the power demands or the task arrival process. Moreover, we analyze the influence of the assumption that energy can be sold from the battery to the grid. An alternative algorithm is proposed to take advantage of the ability to sell energy. The performance gap between our proposed algorithm and the optimum is shown to diminish as energy selling price approaches the electricity price.

We consider a single-user, single-hop wireless communication system, in which data packets arrive at a data queue to be transmitted to a receiver over a block fading channel, privately from an eavesdropper. We assume that the eavesdropper listens to the transmitter over another independently fading channel and that the transmitter only has knowledge of the distribution of the eavesdropper's channel. We propose a joint secrecy rate, transmission, and admission controller based on a simple index policy that only relies on the distribution of the eavesdropper's channel rate. Given any arrival sample path, we show that our controller achieves the maximum possible data admission rate, while keeping the data queue stable as well as meeting an upper bound on the rate of secrecy outage, i.e., the fraction of data packets that are in part or fully decodable by the eavesdropper. While the solution is not unique, i.e., there are other schemes that can achieve the aforementioned performance, we show that our scheme also achieves a low queuing delay for the data packets enqueued at the data queue by striking the correct balance between direct secrecy encoding for data bits and secret key generation and utilization. To obtain this result, our transmission controller makes use of the secret key queue to smooth out the variations in the achievable secrecy rate of the associated fading wiretap channel.

This paper considers point-to-point secure communication over flat fading channels under an outage constraint. More specifically, we extend the definition of outage capacity to account for the secrecy constraint and obtain sharp characterizations of the corresponding fundamental limits under two different assumptions on the transmitter channel state information (CSI). First, we find the outage secrecy capacity assuming that the transmitter has perfect knowledge of the legitimate and eavesdropper channel gains. In this scenario, the capacity achieving scheme relies on opportunistically exchanging private keys between the legitimate nodes. These keys are stored in a key buffer and later used to secure delay sensitive data using the Vernam's one time pad technique. We then extend our results to the more practical scenario where the transmitter is assumed to know only the legitimate channel gain. Here, our achievability arguments rely on privacy amplification techniques to generate secret key bits. In the two cases, we also characterize the optimal power control policies which, interestingly, turn out to be a judicious combination of channel inversion and the optimal ergodic strategy. Finally, we analyze the effect of key buffer overflow on the overall outage probability.

This paper considers reliable communications over a multiple-input multiple-output (MIMO) Gaussian channel, where the channel matrix is within a bounded channel uncertainty region around a nominal channel matrix, i.e., an instance of the compound MIMO Gaussian channel. We study the optimal transmit covariance matrix design to achieve the capacity of compound MIMO Gaussian channels, where the channel uncertainty region is characterized by the spectral norm. This design problem is a challenging nonconvex optimization problem. However, in this paper, we reveal that this problem has a hidden convexity property, which can be exploited to map the problem into a convex optimization problem. We first prove that the optimal transmit design is to diagonalize the nominal channel, and then show that the duality gap between the capacity of the compound MIMO Gaussian channel and the min-max channel capacity is zero, which proves and generalizes a conjecture of Loyka and Charalambous. The key tools for showing these results are a new matrix determinant inequality and some unitarily invariant properties.

In an unreliable single-hop broadcast network setting, we investigate the throughput and decoding-delay performance of random linear network coding as a function of the coding window size and the network size. Our model consists of a source transmitting packets of a single flow to a set of n users over independent time-correlated erasure channels. The source performs random linear network coding (RLNC) over k (coding window size) packets and broadcasts them to the users. We note that the broadcast throughput of RLNC must vanish with increasing n, for any fixed k. Hence, in contrast to other works in the literature, we investigate how the coding window size k must scale for increasing n. Our analysis reveals that the coding window size of Θ(ln(n)) represents a phase transition rate, below which the throughput converges to zero, and above which, it converges to the broadcast capacity. Further, we characterize the asymptotic distribution of decoding delay and provide approximate expressions for the mean and variance of decoding delay for the scaling regime of k=ω(ln(n)). These asymptotic expressions reveal the impact of channel correlations on the throughput and delay performance of RLNC. We also show that how our analysis can be extended to other rateless block coding schemes such as the LT codes. Finally, we comment on the extension of our results to the cases of dependent channels across users and asymmetric channel model.

The problem of developing distributed scheduling algorithms for high throughput in multihop wireless networks has been extensively studied in recent years. The design of a distributed low-complexity scheduling algorithm becomes even more challenging when taking into account a physical interference model, which requires the SINR at a receiver to be checked when making scheduling decisions. To do so, we need to check whether a transmission failure is caused by interference due to simultaneous transmissions from distant nodes. In this paper, we propose a scheduling algorithm under a physical interference model, which is amenable to distributed implementation with 802.11 CSMA technologies. The proposed scheduling algorithm is shown to achieve throughput optimality. We present two variations of the algorithm to enhance the delay performance and to reduce the control overhead, respectively, while retaining throughput optimality.

In this paper, we consider the problem of link scheduling in multihop wireless networks under general interference constraints. Our goal is to design scheduling schemes that do not use per-flow or per-destination information, maintain a single data queue for each link, and exploit only local information, while guaranteeing throughput optimality. Although the celebrated back-pressure algorithm maximizes throughput, it requires per-flow or per-destination information. It is usually difficult to obtain and maintain this type of information, especially in large networks, where there are numerous flows. Also, the back-pressure algorithm maintains a complex data structure at each node, keeps exchanging queue-length information among neighboring nodes, and commonly results in poor delay performance. In this paper, we propose scheduling schemes that can circumvent these drawbacks and guarantee throughput optimality. These schemes use either the readily available hop-count information or only the local information for each link. We rigorously analyze the performance of the proposed schemes using fluid limit techniques via an inductive argument and show that they are throughput-optimal. We also conduct simulations to validate our theoretical results in various settings and show that the proposed schemes can substantially improve the delay performance in most scenarios.

Scheduling is a critical and challenging resource allocation mechanism for multihop wireless networks. It is well known that scheduling schemes that favor links with larger queue length can achieve high throughput performance. However, these queue-length-based schemes could potentially suffer from large (even infinite) packet delays due to the well-known last packet problem, whereby packets belonging to some flows may be excessively delayed due to lack of subsequent packet arrivals. Delay-based schemes have the potential to resolve this last packet problem by scheduling the link based on the delay the packet has encountered. However, characterizing throughput optimality of these delay-based schemes has largely been an open problem in multihop wireless networks (except in limited cases where the traffic is single-hop.) In this paper, we investigate delay-based scheduling schemes for multihop traffic scenarios with fixed routes. We develop a scheduling scheme based on a new delay metric and show that the proposed scheme achieves optimal throughput performance. Furthermore, we conduct simulations to support our analytical results and show that the delay-based scheduler successfully removes excessive packet delays, while it achieves the same throughput region as the queue-length-based scheme.

Delay-capacity tradeoffs for mobile networks have been analyzed through a number of research works. However, Lévy mobility known to closely capture human movement patterns has not been adopted in such work. Understanding the delay-capacity tradeoff for a network with Lévy mobility can provide important insights into understanding the performance of real mobile networks governed by human mobility. This paper analytically derives an important point in the delay-capacity tradeoff for Lévy mobility, known as the critical delay. The critical delay is the minimum delay required to achieve greater throughput than what conventional static networks can possibly achieve (i.e., O(1/√n) per node in a network with n nodes). The Lévy mobility includes Lévy flight and Lévy walk whose step-size distributions parametrized by α ∈ (0,2] are both heavy-tailed while their times taken for the same step size are different. Our proposed technique involves: 1) analyzing the joint spatio-temporal probability density function of a time-varying location of a node for Lévy flight, and 2) characterizing an embedded Markov process in Lévy walk, which is a semi-Markov process. The results indicate that in Lévy walk, there is a phase transition such that for α ∈ (0,1), the critical delay is always Θ(n[1/2]), and for α ∈ [1,2] it is Θ(n[(α)/2]). In contrast, Lévy flight has the critical delay Θ(n[(α)/2]) for α ∈ (0,2].

In this paper, we study distributed scheduling in multihop multiple-input–multiple-output (MIMO) networks. We first develop a “MIMO-pipe” model that provides the upper layers a set of rates and signal-to-interference-plus-noise ratio (SINR) requirements that capture the rate–reliability tradeoff in MIMO communications. The main thrust of this paper is then dedicated to developing distributed carrier sense multiple access (CSMA) algorithms for MIMO-pipe scheduling under the SINR interference model. We choose the SINR model over the extensively studied protocol-based interference models because it more naturally captures the impact of interference in wireless networks. The coupling among the links caused by the interference under the SINR model makes the problem of devising distributed scheduling algorithms very challenging. To that end, we explore the CSMA algorithms for MIMO-pipe scheduling from two perspectives. We start with an idealized continuous-time CSMA network, where control messages can be exchanged in a collision-free manner, and devise a CSMA-based link scheduling algorithm that can achieve throughput optimality under the SINR model. Next, we consider a discrete-time CSMA network, where the message exchanges suffer from collisions. For this more challenging case, we develop a “conservative” scheduling algorithm by imposing a more stringent SINR constraint on the MIMO-pipe model. We show that the proposed conservative scheduling achieves an efficiency ratio bounded from below.

This paper investigates the distributed power allocation problem for coordinated multipoint (CoMP) transmissions in distributed antenna systems (DAS). Traditional duality-based optimization techniques cannot be directly applied to this problem, because the non-strict concavity of the CoMP transmission's achievable rate with respect to the transmission power induces that the local power allocation subproblems have non-unique optimum solutions. We propose a distributed power allocation algorithm to resolve this non-strict concavity difficulty. This algorithm only requires local information exchange among neighboring base stations serving the same user, and is thus flexible with respect to network size and topology. The step-size parameters of this algorithm are determined by only local user access relationship (i.e., the number of users served by each antenna), but do not rely on channel coefficients. Therefore, the convergence speed of this algorithm is quite robust to channel fading. We rigorously prove that this algorithm converges to an optimum solution of the power allocation problem. Simulation results are presented to demonstrate the effectiveness of the proposed power allocation algorithm.

The security of the Internet can be significantly improved if Internet Service Providers adopt firewalls to monitor traffic entering and leaving access networks. But this process suffers due to `free-riding', and hence, regulatory requirements and `seeding' strategies are required to influence the adoption process. In this paper, we analytically derive the equilibrium adoption levels and relate them to the initial seeding and mandating condition, and explore the issues of incentive alignment across users, firewall developers, and regulators. We define different notions of optimality and analytically develop optimum seeding and mandating policies.

In this paper, we investigate the utility maximization problem for a sensor network with energy replenishment. Each sensor node consumes energy in its battery to generate and deliver data to its destination via multi-hop communications. Although the battery can be replenished from renewable energy sources, the energy allocation should be carefully designed in order to maximize system performance, especially when the replenishment profile is unknown in advance. In this paper, we address the joint problem of energy allocation and routing to maximize the total system utility, without prior knowledge of the replenishment profile. We first characterize optimal throughput of a single node under general replenishment profile, and extend our idea to the multi-hop network case. After characterizing the optimal network utility with an upper bound, we develop a low-complexity online solution that achieves asymptotic optimality. Focusing on long-term system performance, we can greatly simplify computational complexity while maintaining high performance. We also show that our solution can be approximated by a distributed algorithm using standard optimization techniques. Through simulations with replenishment profile traces for solar and wind energy, we numerically evaluate our solution, which outperforms a state-of-the-art scheme that is developed based on the Lyapunov optimization technique.

We investigate the problem of minimizing the sum of the queue lengths of all the nodes in a wireless network with a tree topology. Nodes send their packets to the tree's root (sink). We consider a time-slotted system, and a K-hop interference model. We characterize the existence of causal sample-path optimal scheduling policies in these networks, i.e., we wish to find a policy such that at each time slot, for any traffic arrival pattern, the sum of the queue lengths of all the nodes is minimum among all policies. We provide an algorithm that takes any tree and K as inputs, and outputs whether a causal sample-path optimal policy exists for this tree under the K-hop interference model. We show that when this algorithm returns FALSE, there exists a traffic arrival pattern for which no causal sample-path optimal policy exists for the given tree structure. We further show that for certain tree structures, even non-causal sample-path optimal policies do not exist. We provide causal sample-path optimal policies for those tree structures for which the algorithm returns TRUE. Thus, we completely characterize the existence of such policies for all trees under the K-hop interference model. The non-existence of sample-path optimal policies in a large class of tree structures implies that we need to study other (relatively) weaker metrics for this problem.

In the literature, one of the key assumptions in characterizing the scaling laws for wireless mobile networks, is to assume that nodes do not communicate while being mobile. In other words, contact opportunities are not considered during the mobility process itself. However, we find that this assumption leads to an inflated estimate of the delay, even in an order sense. To address this issue, a new framework that allows nodes to communicate while being mobile is proposed in this paper. Under this framework, it is shown that delays to obtain various levels of throughput for i.i.d. mobility model are overestimated and a new tighter delay-capacity tradeoff is suggested. Also, the framework is used to analytically derive the delay-capacity tradeoff of Lévy flight model for various levels of throughput, where Lévy flight is a random walk of a power-law flight distribution with an exponent α ∈ (0, 2]. It is known as a mobility model which closely captures human movement patterns. The tradeoffs from the proposed framework between the delay (D̅) and per-node throughput (λ) indicate that D̅ = O(√(max(1,nλ3))) holds for i.i.d. mobility and D̅ = O(√(min(n1+αλ,n2))) holds for Lévy flight.

Cognitive Radio Networks allow unlicensed users to opportunistically access the licensed spectrum without causing disruptive interference to the primary users (PUs). One of the main challenges in CRNs is the ability to detect PU transmissions. Recent works have suggested the use of secondary user (SU) cooperation over individual sensing to improve sensing accuracy. In this paper, we consider a CRN consisting of a single PU and multiple SUs to study the problem of maximizing the total expected system throughput. We propose a Bayesian decision rule based algorithm to solve the problem optimally with a constant time complexity. To prioritize PU transmissions, we re-formulate the throughput maximization problem by adding a constraint on the PU throughput. The constrained optimization problem is shown to be strongly NP-hard and solved via a greedy algorithm with pseudo-polynomial time complexity that achieves strictly greater than 1/2 of the optimal solution. We also investigate the case for which a constraint is put on the sensing time overhead, which limits the number of SUs that can participate in cooperative sensing. We reveal that the system throughput is monotonic over the number of SUs chosen for sensing. We illustrate the efficacy of the performance of our algorithms via a numerical investigation.

We consider the scheduling problem in downlink wireless networks with heterogeneous, Markov-modulated, ON/OFF channels. It is well-known that the performance of scheduling over fading channels heavily depends on the accuracy of the available Channel State Information (CSI), which is costly to acquire. Thus, we consider the CSI acquisition via a practical ARQ-based feedback mechanism whereby channel states are revealed at the end of only scheduled users' transmissions. In the assumed presence of temporally-correlated channel evolutions, the desired scheduler must optimally balance the exploitation-exploration trade-off, whereby it schedules transmissions both to exploit those channels with up-to-date CSI and to explore the current state of those with outdated CSI. In earlier works, Whittle's Index Policy had been suggested as a low-complexity and high-performance solution to this problem. However, analyzing its performance in the typical scenario of statistically heterogeneous channel state processes has remained elusive and challenging, mainly because of the highly-coupled and complex dynamics it possesses. In this work, we overcome these difficulties to rigorously establish the asymptotic optimality properties of Whittle's Index Policy in the limiting regime of many users. More specifically: (1) we prove the local optimality of Whittle's Index Policy, provided that the initial state of the system is within a certain neighborhood of a carefully selected state; (2) we then establish the global optimality of Whittle's Index Policy under a recurrence assumption that is verified numerically for the problem at hand. These results establish, for the first time to the best of our knowledge, that Whittle's Index Policy possesses analytically provable optimality characteristics for scheduling over heterogeneous and temporally-correlated channels.

In this work, we investigate the use of epidemic routing in energy constrained Delay Tolerant Networks (DTNs). In DTNs, connected paths between source and destination rarely materialize due to the mobility and sparse density of nodes. Epidemic routing is well-suited for these environments due to its simplicity and fully distributed implementation. In epidemic routing, messages are relayed by intermediate nodes at contact opportunities, i.e., when pairs of nodes come within transmission range. Each node needs to decide whether to forward its message upon contact with a new node based on its residual energy level and the age of that message.

In this paper, we characterize the throughput of a broadcast network with n receivers using rateless codes with block size K. We assume that the underlying channel is a Markov modulated erasure channel that is i.i.d. across users, but can be correlated in time. We characterize the system throughput asymptotically in n. Specifically, we explicitly show how the throughput behaves for different values of the coding block size K as a function of n, as n approaches infinity. Under the more restrictive assumption of memoryless channels, we are able to provide a lower bound on the maximum achievable throughput for any finite values of K and n. Using simulations we show the tightness of the bound with respect to system parameters n and K, and find that its performance is significantly better than the previously known lower bound.

Cooperative networking is known to have significant potential in increasing network capacity and transmission reliability. Although there have been extensive studies on applying cooperative networking in multi-hop ad hoc networks, most works are limited to the basic three-node relay scheme and single-antenna systems. These two limitations are interconnected and both are due to a limited theoretical understanding of the optimal power allocation structure in MIMO cooperative networks (MIMO-CN). In this paper, we study the structural properties of the optimal power allocation in MIMO-CN with per-node power constraints. More specifically, we show that the optimal power allocations at the source and each relay follow a matching structure in MIMO-CN. This result generalizes the power allocation result under the basic three-node setting to the multi-relay setting, for which the optimal power allocation structure has been heretofore unknown. We further quantify the performance gain due to cooperative relay and establish a connection between cooperative relay and pure relay. Finally, based on these structural insights, we reduce the MIMO-CN rate maximization problem to an equivalent scalar formulation. We then propose a global optimization method to solve this simplified and equivalent problem.

This paper focuses on the downlink of a cellular system and studies opportunistic multiuser scheduling under imperfect channel state information, by exploiting the memory inherent in the channel. The channel between the base station and each user is modeled by a two-state Markov chain and the scheduled user sends back an ARQ feedback that arrives at the scheduler with a random delay, i.i.d. across users and time. The scheduler indirectly estimates the channel via accumulated delayed-ARQ feedback and uses this information to make scheduling decisions. The throughput maximization problem is formulated as a partially observable Markov decision process (POMDP). For the case of two users in the system, it is shown that a greedy policy is sum throughput optimal for any distribution on the ARQ feedback delay. For the case of more than two users, the greedy policy is suboptimal and numerical studies demonstrate that it has near optimal performance. Also, the greedy policy can be implemented by a simple algorithm that does not require the statistics of the underlying Markov channel or the ARQ feedback delay, thus making it robust against errors in system parameter estimation. Establishing an equivalence between the two-user system and a genie-aided system, a simple closed form expression for the sum capacity of the downlink is obtained. Further, inner and outer bounds on the capacity region of the downlink are obtained.

In recent years, there has been a significant amount of work done in developing low-complexity scheduling schemes to achieve high performance in multihop wireless networks. A centralized suboptimal scheduling policy, called Greedy Maximal Scheduling (GMS) is a good candidate because its empirically observed performance is close to optimal in a variety of network settings. However, its distributed realization requires high complexity, which becomes a major obstacle for practical implementation. In this paper, we develop simple distributed greedy algorithms for scheduling in multihop wireless networks. We reduce the complexity by relaxing the global ordering requirement of GMS, up to near zero. Simulation results show that the new algorithms approximate the performance of GMS, and outperform the state-of-the-art distributed scheduling policies.

This paper considers network control for wireless networks with finite buffers. We investigate the performance of joint flow control, routing, and scheduling algorithms that achieve high network utility and deterministically bounded backlogs inside the network. Our algorithms guarantee that buffers inside the network never overflow. We study the tradeoff between buffer size and network utility and show that under the one-hop interference model, if internal buffers have size$(N-1)/(2 \epsilon)$, then$\epsilon $-optimal network utility can be achieved, where$\epsilon $is a control parameter and$N$is the number of network nodes. The underlying scheduling/routing component of the considered control algorithms requires ingress queue length information (IQI) at all network nodes. However, we show that these algorithms can achieve the same utility performance with delayed ingress queue length information at the cost of a larger average backlog bound. We also show how to extend the results to other interference models and to wireless networks with time-varying link quality. Numerical results reveal that the considered algorithms achieve nearly optimal network utility with a significant reduction in queue backlog compared to existing algorithms in the literature.

In this paper, we develop an energy-efficient routing scheme that takes into account four key wireless system elements: transmission power; interference; residual energy; and energy replenishment. Since energy is a scarce resource, many energy-aware routing algorithms have been proposed to improve network performance. However, previous algorithms have been designed for a subset of these four main elements, which could limit their applicability. Thus, our contribution is here to develop a unified routing algorithm called the Energy-efficient Unified Routing (EURo) algorithm that accommodates any combination of these above key elements and adapts to varying wireless environments. We study the impact of key wireless elements on routing, and show via simulations that EURo outperforms the state-of-the-art.

In this paper, the power control problem is considered for access-point based wireless networks under the SINR interference model. This problem is NP hard in terms of the number of APs in the network, and if not designed properly can have high polynomial complexity in terms of the power levels. We first separate the overall problem into two sub-problems using the primal-dual method. We then develop an efficient algorithm under the SINR-interference model that uses only two power levels to solve a subproblem of the overall power control problem, which we call the utility-independent power control (UIPC) subproblem. This approach allows the optimality gap of the UIPC subproblem to be bounded. Moreover, a two-stage iterative algorithm is developed that solves the overall power control problem within a small neighborhood of the global optimum. This offline algorithm has a significantly lower computational complexity than the globally optimal algorithm. Further, based on the structure of the iterative algorithm, an efficient heuristic two-stage greedy algorithm is proposed with low polynomial time complexity. Finally, numerical results are provided to demonstrate the efficacy of our solution.

In this paper, we investigate the problem of maximizing the throughput over a finite-horizon time period for a sensor network with energy replenishment. The finite-horizon problem is important and challenging because it necessitates optimizing metrics over the short term rather than metrics that are averaged over a long period of time. Unlike the infinite-horizon problem, the fact that inefficiencies cannot be made to vanish to infinitesimally small values, means that the finite-horizon problem requires more delicate control. The finite-horizon throughput optimization problem can be formulated as a convex optimization problem, but turns out to be highly complex. The complexity is brought about by the “time coupling property,” which implies that current decisions can influence future performance. To address this problem, we employ a three-step approach. First, we focus on the throughput maximization problem for a single node with renewable energy assuming that the replenishment rate profile for the entire finite-horizon period is known in advance. An energy allocation scheme that is equivalent to computing a shortest path in a simply-connected space is developed and proven to be optimal. We then relax the assumption that the future replenishment profile is known and develop an online algorithm. The online algorithm guarantees a fraction of the optimal throughput. Motivated by these results, we propose a low-complexity heuristic distributed scheme, called NetOnline, in a rechargeable sensor network. We prove that this heuristic scheme is optimal under homogeneous replenishment profiles. Further, in more general settings, we show via simulations that NetOnline significantly outperforms a state-of-the-art infinite-horizon based scheme, and for certain configurations using data collected from a testbed sensor network, it achieves empirical performance close to optimal.

Scheduling is a critical and challenging resource allocation mechanism for multi-hop wireless networks. It is well known that scheduling schemes that give a higher priority to the link with larger queue length can achieve high throughput performance. However, this queue-length-based approach could potentially suffer from large (even infinite) packet delays due to the well-known last packet problem, whereby packets may get excessively delayed due to lack of subsequent packet arrivals. Delay-based schemes have the potential to resolve this last packet problem by scheduling the link based on the delay for the packet has encountered. However, the throughput performance of delay-based schemes has largely been an open problem except in limited cases of single-hop networks. In this paper, we investigate delay-based scheduling schemes for multi-hop traffic scenarios. We view packet delays from a different perspective, and develop a scheduling scheme based on a new delay metric. Through rigorous analysis, we show that the proposed scheme achieves the optimal throughput performance. Finally, we conduct extensive simulations to support our analytical results, and show that the delay-based scheduler successfully removes excessive packet delays, while it achieves the same throughput region as the queue-length-based scheme.

We address the problem of opportunistic multiuser scheduling in downlink networks with Markov-modeled outage channels. We consider the scenario in which the scheduler does not have full knowledge of the channel state information, but instead estimates the channel state information by exploiting the memory inherent in the Markov channels along with ARQ-styled feedback from the scheduled users. Opportunistic scheduling is optimized in two stages: (1) Channel estimation and rate adaptation to maximize the expected immediate rate of the scheduled user; (2) User scheduling, based on the optimized immediate rate, to maximize the overall long term sum-throughput of the downlink. The scheduling problem is a partially observable Markov decision process with the classic `exploitation vs exploration' trade-off that is difficult to quantify. We therefore study the problem in the framework of Restless Multi-armed Bandit Processes (RMBP) and perform a Whittle's indexability analysis. Whittle's indexability is traditionally known to be hard to establish and the index policy derived based on Whittle's indexability is known to have optimality properties in various settings. We show that the problem of downlink scheduling under imperfect channel state information is Whittle indexable and derive the Whittle's index policy in closed form. Via extensive numerical experiments, we show that the index policy has near-optimal performance. Our work reveals that, under incomplete channel state information, exploiting channel memory for opportunistic scheduling can result in significant performance gains and that almost all of these gains can be realized using an easy-to-implement index policy.

Recent work has shown that retransmissions can cause heavy-tailed transmission delays even when packet sizes are light-tailed. Moreover, the impact of heavy tailed delays persist even when packets are of finite size. The key question we study in this paper is how the use of coding techniques to transmit information could mitigate delays. To investigate this problem, we consider an important communication channel called the Binary Erasure Channel, where transmitted bits are either received successfully or lost (called an erasure). This model is a good abstraction of not only the wireless channel but also the higher layer link, where erasure errors can happen. Many coding schemes, known as erasure codes, have been designed for this channel. Specifically, we focus on the fixed rate coding scheme, where decoding is said to be successful if a certain fraction β of the codeword is received correctly. We study two different scenarios: (I) A codeword of length Lcis retransmitted as a unit until the receiver successfully receives more than βLcbits in the last transmission. (II) All successfully received bits from every (re)transmissions are buffered at the receiver according to their positions in the codeword, and the transmission completes once the received bits become decodable for the first time. Our studies reveal that complicated and surprising relationships exist between the coding complexity and the transmission delay/throughput. From a theoretical perspective, our results provide a benchmark to quantify the tradeoffs between coding complexity and transmission throughput for receivers that use memory to buffer (re)transmissions until success and those that do not buffer intermediate transmissions.

In this paper, we develop a mathematical framework for studying the problem of maximizing the "information" received at the sink in a data gathering wireless sensor network. We explicitly account for unreliable links, energy constraints, and in-network computation. The network model is that of a sensor network arranged in the form of a tree topology, where the root corresponds to the sink node, and the rest of the network detects an event and transmits data to the sink over one or more hops. This problem of sending data from multiple sources to a common sink is often referred to as the convergecasting problem. We develop an integer optimization based framework for this problem, which allows for tackling link unreliability using general error-recovery schemes. Even though this framework has a non-linear objective function, and cannot be relaxed to a convex programming problem, we develop a low complexity, distributed solution. The solution involves finding a Maximum Weight Increasing Independent Set (MWIIS) in rectangle graphs over each hop of the network, and can be obtained in polynomial time. Further, we apply these techniques to a target tracking problem where we optimally select sensors to track a given target such that the information obtained is maximized subject to constraints on the per-node sensing and communication energy. We validate our algorithms through numerical evaluations, and illustrate the advantages of explicitly considering link unreliability in the optimization framework.

We investigate the problem of minimizing the sum of the queues of all the nodes in a wireless network with a tree topology. Nodes send their packets to the tree's root (sink). We consider a time-slotted system, and a primary interference model. We first consider the case where the root has only one child while the rest of the tree is arbitrary, and provide a causal sample-path delay optimal scheduling policy, i.e., at each time slot, for any traffic arrival pattern, the sum of the queues of all the nodes is minimum among all policies. We are able to fully characterize tree structures for which such policies exist. In particular, when the root has multiple children, there exists a causal sample-path delay optimal policy as long as only one child is not a leaf node. We also show that for any other tree structure there exists no causal sample-path delay optimal policy, thus underscoring the inherent limitation of using sample-path optimality as a performance metric and implying that other weaker metrics of delay performance should be investigated.

We study the problem of maximizing the aggregated information in a wireless sensor network. We consider a sensor network with a tree topology, where the root corresponds to the sink, and the rest of the network detects an event and transmits data to the sink. We formulate an integer optimization problem that maximizes the aggregated information that reaches the sink under deadline and interference constraints. This framework allows using a variety of error recovery schemes to tackle link unreliability. We show that the optimal solution involves solving a Job Interval Selection Problem (JISP) which is known to be MAX SNP-Hard. We construct a sub-optimal version, and develop a low complexity, distributed optimal solution to this version. We investigate tree structures for which this solution is optimal to the original problem. Our numerical results show that the sub-optimal solution outperforms existing JISP approximation algorithms even for general trees.

This paper focuses on designing and analyzing throughput-optimal scheduling policies that avoid using per-flow or per-destination information, maintain a single data queue for each link, exploit only local information, and potentially improve the delay performance, for multi-hop wireless networks under general interference constraints. Although the celebrated backpressure algorithm maximizes throughput, it requires per-flow or per-destination information (which may be difficult to obtain and maintain), maintains per-flow or per-destination queues at each node, relies on constant exchange of queue length information among neighboring nodes to calculate link weights, and may result in poor delay performance. In contrast, the proposed schemes can circumvent these drawbacks while guaranteeing throughput optimality. We rigorously analyze the throughput performance of the proposed schemes and show that they are throughput-optimal using fluid limit techniques via an inductive argument. We also conduct simulations to show that the proposed schemes can substantially improve the delay performance.

We analyze the delay performance of a multihop wireless network with a fixed route between each source–destination pair. We develop a new queue grouping technique to handle the complex correlations of the service process resulting from the multihop nature of the flows. A general set-based interference model is assumed that imposes constraints on links that can be served simultaneously at any given time. These interference constraints are used to obtain a fundamental lower bound on the delay performance of any scheduling policy for the system. We present a systematic methodology to derive such lower bounds. For a special wireless system, namely the clique, we design a policy that is sample-path delay-optimal. For the tandem queue network, where the delay-optimal policy is known, the expected delay of the optimal policy numerically coincides with the lower bound. We conduct extensive numerical studies to suggest that the average delay of the back-pressure scheduling policy can be made close to the lower bound by using appropriate functions of queue length.

In wireless sensor networks (WSNs), asynchronous sleep-wake scheduling protocols can be used to significantly reduce energy consumption without incurring the communication overhead for clock synchronization needed for synchronous sleep-wake scheduling protocols. However, these savings could come at a significant cost in delay performance. Recently, researchers have attempted to exploit the inherent broadcast nature of the wireless medium to reduce this delay with virtually no additional energy cost. These schemes are called “anycasting,” where each sensor node forwards the packet to the first node that wakes up among a set of candidate next-hop nodes. In this paper, we develop a delay-optimal anycasting scheme under periodic sleep-wake patterns. Our solution is computationally simple and fully distributed. Furthermore, we show that periodic sleep-wake patterns result in the smallest delay among all wake-up patterns under given energy constraints. Simulation results illustrate the benefit of our proposed schemes over the state of the art.

We study the optimal control of communication networks in the presence of heterogeneous traffic requirements. Specifically, we distinguish the flows into two crucial classes: inelastic for modeling high-priority, delay-sensitive, and fixed-throughput applications; and elastic for modeling low-priority, delay-tolerant, and throughput-greedy applications. We note that the coexistence of such diverse flows creates complex interactions at multiple levels (e.g., flow and packet levels), which prevent the use of earlier design approaches that dominantly assume homogeneous traffic. In this work, we develop the mathematical framework and novel design methodologies needed to support such heterogeneous requirements and propose provably optimal network algorithms that account for the multilevel interactions between the flows. To that end, we first formulate a network optimization problem that incorporates the above throughput and service prioritization requirements of the two traffic types. We, then develop a distributed joint load-balancing and congestion control algorithm that achieves the dual goal of maximizing the aggregate utility gained by the elastic flows while satisfying the fixed throughput and prioritization requirements of the inelastic flows. Next, we extend our joint algorithm in two ways to further improve its performance: in delay through a virtual queue implementation with minimal throughput degradation and in utilization by allowing for dynamic multipath routing for elastic flows. A unique characteristic of our proposed dynamic routing solution is the novel two-stage queueing architecture it introduces to satisfy the service prioritization requirement.

Renewable energy sources can be attached to sensor nodes to provide energy replenishment for prolonging the lifetime of sensor networks. However, for networks with replenishment, conservative energy expenditure may lead to missed recharging opportunities due to battery capacity limitations, while aggressive usage of energy may result in reduced coverage or connectivity for certain time periods. Thus, new power allocation schemes need to be designed to balance these seemingly contradictory goals, in order to maximize sensor network performance. In this paper, we study the problem of how to jointly control the data queue and battery buffer to maximize the long-term average sensing rate of a single communication link in rechargeable sensor networks. The coupling between the battery and data buffers does not lend itself amenable to traditional resource optimization techniques. Thus, we develop a new power and rate allocation scheme that explicitly takes this coupling into account. The new scheme is a simple myopic scheme whose performance is shown to be arbitrarily close to optimal analytically and via simulations.

In recent years, the famous wiretap channel has been revisited by many researchers and information theoretic secrecy has become an active area of research in this setting. In this paper, we design a wireless communication system that achieves constant bit rate data transmission over a block fading channel, securely from an eavesdropper that listens to the transmitter over another independent block fading channel. It is well known that, the method of sending secure information using the binning techniques inspired by the wiretap channel fails to secure the information at times when the eavesdropper channel has favorable conditions over the main channel. This phenomenon is called secrecy outage. In our system, however, we exploit the times at which the main channel is favorable over the eavesdropper channel for us to be able to transmit some random secret key bits along with the data bits. These key bits are stored in a separate key queue at the transmitter as well as the receiver, and are utilized to secure data bits, whenever the channel conditions favor the eavesdropper. We show that, our system achieves a high performance at any given desired outage probability by jointly controlling the key queue and the transmit power. We show that the optimal power control involves a time sharing between secure waterfilling and channel inversion strategies and the key queue operates in the heavy traffic regime to achieve the maximum delay limited rate possible, under a small outage constraint. This work can be viewed as a first step in providing a framework that combines both information theory and queueing analysis for the study of information theoretic security.

In-network aggregation has become a promising technique for improving the energy efficiency of wireless sensor networks. Aggregating data at various nodes in the network results in a reduction in the amount of bits transmitted over the network, and hence, saves energy. In this paper, we focus on another important aspect of aggregation, i.e., delay performance. In conjunction with link scheduling, in-network aggregation can reduce the delay by lessening the demands for wireless resources and thus expediting data transmissions. We formulate the problem that minimizes the sum delay of sensed data, and analyze the performance of optimal scheduling with in-network aggregation in tree networks under the node-exclusive interference model. We provide a system wide lower bound on the delay and use it as a benchmark for evaluating different scheduling policies. We numerically evaluate the performance of myopic and non-myopic scheduling policies, where myopic one considers only the current system state for a scheduling decision while non-myopic one simulates future system states. We show that the one-step non-myopic policies can substantially improve the delay performance. In particular, the proposed non-myopic greedy scheduling achieves a good tradeoff between performance and implementability.

This paper considers network control for wireless networks with finite buffers. We investigate the performance of joint flow control, routing, and scheduling algorithms which achieve high network utility and deterministically bounded backlogs inside the network. Our algorithms guarantee that buffers inside the network never overflow. We study the tradeoff between buffer size and network utility and show that if internal buffers have size (N - 1)/¿ then a high fraction of the maximum utility can be achieved, where ¿ captures the loss in utility and N is the number of network nodes. The underlying scheduling/routing component of the considered control algorithms requires ingress queue length information (IQI) at all network nodes. However, we show that these algorithms can achieve the same utility performance with delayed ingress queue length information. Numerical results reveal that the considered algorithms achieve nearly optimal network utility with a significant reduction in queue backlog compared to the existing algorithm in the literature. Finally, we discuss extension of the algorithms to wireless networks with time-varying links.

We study the problem of distributed scheduling in multi-hop MIMO networks. We first develop a ``MIMO-pipe" model that provides the upper layers a set of rates and SINR requirements, which capture the rate-reliability tradeoff in MIMO communications. The main thrust of this study is then dedicated to developing CSMA-based MIMO-pipe scheduling under the SINR model. We choose the SINR model over the extensively studied matching or protocol-based interference models because it more naturally captures the impact of interference in wireless networks. The coupling among the links caused by the interference makes the problem of devising distributed scheduling algorithms particularly challenging. To that end, we explore CSMA-based MIMO-pipe scheduling, from two perspectives. First, we consider an idealized continuous time CSMA network. We propose a dual-band approach in which control messages are exchanged instantaneously over a channel separate from the data channel, and show that CSMA-based scheduling can achieve throughput optimality under the SINR model. Next, we consider a discrete time CSMA network. To tackle the challenge due to the coupling caused by interference, we propose a ``conservative" scheduling algorithm in which more stringent SINR constraints are imposed based on the MIMO-pipe model. We show that this suboptimal distributed scheduling can achieve an efficiency ratio bounded from below.

Retransmissions serve as the basic building block that communication protocols use to achieve reliable data transfer. Until recently, the number of retransmissions were thought to follow a light tailed (in particular, a geometric) distribution. However, recent work seems to suggest that when the distribution of the packets have infinite support, retransmission-based protocols may result in heavy tailed delays and even possibly zero throughput. While this result is true even when the distribution of packet sizes are light-tailed, it requires the assumption that the packet sizes have infinite support. However, in reality, packet sizes are often bounded by the Maximum Transmission Unit (MTU), and thus the aforementioned result merits a deeper investigation. To that end, in this paper, we allow the distribution of the packet size L to have finite support. This packet is sent over an on-off channel {(Ai,Ui)} with alternating available Aiand unavailable Uiperiods. If L ? Ai, the transmission fails and we wait for the next period Ai + 1to retransmit the packet. The transmission duration is thus measured from the first attempt to a point when a channel available period larger than L. Under mild conditions, we show that the transmission duration distribution exhibits a transition from a power law main body to an exponential tail with Weibull type distributions between the two. The time scale to observe the power law main body is roughly equal to the average transmission duration of the longest packet. Both the power law main body and the exponential tail could dominate the overall performance. For example, the power law main body, if significant, may cause the channel throughput to be very close to zero. On the other hand, the exponential tail, if more evident, may imply that the system operates in a benign environment. These theoretical findings provide an understanding on why some empirical measurements suggest heavy tails and light tails for others (e.g., wireless networks). We use these results to further highlight the engineering implications from distributions with power law main bodies and light tails by analyzing two cases: (1) The throughput of on-off channels with retransmissions, where we show that even when packet sizes have small means and bounded support the variability in their sizes can greatly impact system performance. (2) The distribution of the number of jobs in an M/M/? queue with server failures. Here we show that retransmissions can cause long-range dependence and quantify the impact of the maximum job sizes on the long-range dependence.

The energy efficiency of the widely used convergecast pattern depends substantially on the choice of medium access control (MAC) and routing protocol. In this paper, we formalize the maximization of convergecast energy efficiency with respect to its MAC and routing as a resource constrained optimization problem. We then analytically show that this maximization problem is linear in the context of two prototypical MACs - a locally synchronized wakeup (as in S-MAC) and a locally staggered wakeup MAC (as in O-MAC) - assuming low, uniform traffic that is delivered reliably and without interference. With this insight, we present a centralized algorithm, MeeCast, that solves the optimization problem utilizing linear programming techniques. We also design a distributed version of MeeCast, for the case where the traffic is ultra-low, and prove that it achieves optimality as well as fast convergence time. Notably, this version is self-stabilizing, so it autonomically handles changes in traffic load, network topology, loss of coordination and state corruption. In comparison with Dozer, a state-of-the-art convergecast protocol, MeeCast achieves better energy efficiency and application lifetime in the context of S-MAC and identical energy efficiency but better application lifetime in the context of O-MAC.

We investigate the performance of longest-queue-first (LQF) scheduling (i.e., greedy maximal scheduling) for wireless networks under the SINR interference model. This interference model takes network geometry and the cumulative interference effect into account, which, therefore, capture the wireless interference more precisely than binary interference models. By employing the ρ-local pooling technique, we show that LQF scheduling achieves zero throughput in the worst case. We then propose a novel technique to localize interference which enables us to decentralize the LQF scheduling while preventing it from having vanishing throughput in all network topologies. We characterize the maximum throughput region under interference localization and present a distributed LQF scheduling algorithm. Finally, we present numerical results to illustrate the usefulness and to validate the theory developed in the paper.

The problem of developing high-performance distributed scheduling algorithms for multi-hop wireless networks has seen enormous interest in recent years. The problem is especially challenging when studied under a physical interference model, which requires the SINR at the receiver to be above a certain threshold for decoding success. Under such an SINR model, transmission failure may be caused by interference due to simultaneous transmissions from far away nodes, which exacerbates the difficulty in developing a distributed algorithm. In this paper, we propose a scheduling algorithm that exploits carrier sensing and show that the algorithm is not only amenable to distributed implementation, but also results in throughput optimality. Our algorithm has a feature called the dual-state approach, which separates the transmission schedules from the system state and can be shown to improve delay performance.

No abstract available.

When there exists only a single multicast session in a directed acyclic/cyclic network, the existence of a network coding solution is characterized by the classic min-cut/max-flow theorem. For the case of more than one coexisting sessions, network coding also demonstrates throughput improvement over noncoded solutions. This paper proposes pairwise intersession network coding, which allows for arbitrary directed networks but restricts the coding operations to being between two symbols (for acyclic networks) or between two strings of symbols (for cyclic networks). A graph-theoretic characterization of pairwise intersession network coding is proven based on paths with controlled edge-overlap. This new characterization generalizes the edge-disjoint path characterization of noncoded network communication and includes the well-studied butterfly graph as a special case. Based on this new characterization, various aspects of pairwise intersession network coding are studied, including the sufficiency of linear codes, the complexity of identifying coding opportunities, its topological analysis, and bandwidth- and coding-efficiency.

In this paper, we develop a distributed rate-control algorithm for networks with multiple unicast sessions when network coding is allowed across different sessions. Building on recent flow-based characterization ofpairwise intersession network coding, the corresponding optimal rate-control problem is formulated as a convex optimization problem. The formulation exploits pairwise coding possibilities between any pair of sessions, where any coded symbol is formed by coding over at most two original symbols. The objective function is the sum of the utilities based on the rates supported by each unicast session. Working on the Lagrangian of the formulated problem, a distributed algorithm is developed with little coordination among intermediate nodes. Each unicast session has the freedom to choose its own utility function. The only information exchange required by the source is the weighted sum of the queue length of each link, which can be piggybacked to the acknowledgment messages. In addition to the optimal rate-control algorithm, we propose a decentralizedpairwise random codingscheme that decouples the decision of coding from that of rate control, which further enhances the distributiveness of the proposed scheme. The convergence of the rate-control algorithm is proven analytically and verified by extensive simulations. Simulation results also demonstrate the advantage of the proposed algorithm over the state-of-the-art in terms of both throughput and fairness.

Energy efficiency is critical for wireless sensor networks. The data-gathering process must be carefully designed to conserve energy and extend network lifetime. For applications where each sensor continuously monitors the environment and periodically reports to a base station, a tree-based topology is often used to collect data from sensor nodes. In this work, we first study the construction of a data-gathering tree when there is a single base station in the network. The objective is to maximize the network lifetime, which is defined as the time until the first node depletes its energy. The problem is shown to be NP-complete. We design an algorithm that starts from an arbitrary tree and iteratively reduces the load on bottleneck nodes (nodes likely to soon deplete their energy due to high degree or low remaining energy). We then extend our work to the case when there are multiple base stations and study the construction of a maximum-lifetime data-gathering forest. We show that both the tree and forest construction algorithms terminate in polynomial time and are provably near optimal. We then verify the efficacy of our algorithms via numerical comparisons.

In this paper, we study the joint power and channel resource allocation problem for a multiuser F/TDMA decode-and-forward (DF) relay network under per-node power constraints and a total channel resource constraint. Our goal is to maximize the total throughput achieved by the systems. To that end, we formulate a joint power and channel resource allocation problem. We develop an iterative optimization algorithm to solve this problem, whose convergence and optimality are guaranteed. Due to the per-node power constraints, more than one relay node may be needed for a single data stream. Our solution also provides a way of finding the optimal relays among the assisting relay nodes.

We analyze the delay performance of a multi-hop wireless network with a fixed route between each source-destination pair. There are arbitrary interference constraints on the set of links that can be served simultaneously at any given time. These interference constraints impose a fundamental lower bound on the delay performance of any scheduling policy for the system. We present a methodology to derive such lower bounds. For the tandem queue network, where the delay optimal policy is known, the expected delay of the optimal policy numerically coincides with the lower bound. We conduct extensive numerical studies to suggest that the average delay of the back-pressure scheduling policy can be made close to the lower bound by using appropriate functions of queue length.

In wireless sensor networks, asynchronous sleep-wake scheduling protocols can significantly reduce energy consumption without incurring the communication overhead for clock synchronization used in typical sleep-wake scheduling protocols. However, the savings could come at a significant cost in delay performance. Recently, researchers have attempted to exploit the inherent broadcast nature of the wireless medium to reduce this delay with virtually no additional energy cost. These schemes are called "anycasting," where each sensor node forwards the packet to the first node that wakes up among a set of candidate next-hop nodes. In this paper, we develop a delay-optimal anycasting scheme under periodic sleep-wake patterns. Our solution is computationally simple and fully distributed. We show that periodic sleep-wake patterns result in the smallest delay among all wake-up patterns under given energy constraints. Simulation results illustrate the benefit of our proposed schemes over the state-of-the art.

In this work, we study the control of communication networks in the presence of both inelastic and elastic traffic flows. The characteristics of these two types of traffic differ significantly. Hence, earlier approaches that focus on homogeneous scenarios with a single traffic type are not directly applicable. We formulate a new network optimization problem that incorporates the performance requirements of inelastic and elastic traffic flows. The solution of this problem provides us with a new queueing architecture, and distributed load balancing and congestion control algorithm with provably optimal performance. In particular, we show that our algorithm achieves the dual goal of maximizing the aggregate utility gained by the elastic flows while satisfying the demands of inelastic flows. Our base optimal algorithm is extended to provide better delay performance for both types of traffic with minimal degradation in throughput. It is also extended to the practically relevant case of dynamic arrivals and departures. Our solution allows for a controlled interaction between the performance of inelastic and elastic traffic flows. This performance can be tuned to achieve the appropriate design tradeoff. The network performance is studied both theoretically and through extensive simulations.

There has been significant recent interest in covert communication using timing channels. In network timing channels, information is leaked by controlling the time between transmissions of consecutive packets. Our work focuses on network timing channels and provides two main contributions. The first is to quantify the threat posed by covert network timing channels. The other is to use timing channels to communicate at a low data rate without being detected. In this paper, we design and implement a covert TCP/IP timing channel. We are able to quantify the achievable data rate (or leak rate) of such a covert channel. Moreover, we show that by sacrificing data rate, the traffic patterns of the covert timing channel can be made computationally indistinguishable from that of normal traffic, which makes detecting such communication virtually impossible. We demonstrate the efficacy of our solution by showing significant performance gains in terms of both data rate and covertness over the state-of-the-art.

For wireless multi-hop networks with unicast sessions, most coding opportunities involve only two or three sessions as coding across many sessions requires greater transmission power to broadcast the coded symbol to many receivers, which enhances interference. This work shows that with a new flow-based characterization of pairwise intersession network coding (coding across two unicast sessions), an optimal joint coding, scheduling, and rate-control scheme can be devised and implemented using only the binary XOR operation. The new scheduling/rate-control scheme demonstrates provably graceful throughput degradation with imperfect scheduling, which facilitates the design tradeoff between the throughput optimality and computational complexity of different scheduling schemes. Our results show that pairwise intersession network coding improves the throughput of non-coding solutions regardless of whether perfect/imperfect scheduling is used. Both the deterministic and stochastic packet arrivals and departures are considered. This work shows a striking resemblance between pairwise intersession network coding and non-coded solutions, and thus advocates extensions of non-coding wisdoms to their network coding counterpart.

In this paper, we develop an energy-efficient routing scheme that takes into account the interference created by existing flows in the network. The routing scheme chooses a route such that the network expends the minimum energy satisfying with the minimum constraints of flows. Unlike previous works, we explicitly study the impact of routing a new flow on the energy consumption of the network. Under certain assumptions on how links are scheduled, we can show that our proposed algorithm is asymptotically (in time) optimal in terms of minimizing the average energy consumption. We also develop a distributed version of the algorithm. Our algorithm automatically detours around a congested area in the network, which helps mitigate network congestion and improve overall network performance. Using simulations, we show that the routes chosen by our algorithm (centralized and distributed) are more energy efficient than the state of the art.

Wireless sensor networks attract more and more attention since they are capable of monitoring the environment. Since wireless sensor nodes typically have limited energy and power, power efficiency is a main concern in designing protocols for wireless sensor networks. Data aggregation is one of the strategies that can reduce the power consumption in wireless sensor networks. In this paper, we propose a cross layer algorithm with data aggregation to minimize the power consumption. Most importantly, our proposed algorithm is distributed and therefore, it is suitable for wireless sensor networks. From numerical results, we conclude that not all data packets should be aggregated before they arrive the destination nodes.

Several popular simulation and emulation environments fail to account for realistic packet forwarding behaviors of commercial switches and routers. Such simulation or emulation inaccuracies can lead to dramatic and qualitative impacts on the results. In this paper, we present a measurement-based model for routers and other forwarding devices, which we use to simulate two different Cisco routers under varying traffic conditions. The structure of our model is device-independent, but requires device-specific parameters. We construct a profiling tool and use it to derive router parameter tables within a few hours. Our preliminary results indicate that our model can approximate the Cisco routers. The compactness of the parameter tables and simplicity of the model makes it possible to use it for high-fidelity simulations while preserving simulation scalability.

In this paper, we characterize the performance of an important class of scheduling schemes, called greedy maximal scheduling (GMS), for multi-hop wireless networks. While a lower bound on the throughput performance of GMS is relatively well-known in the simple node-exclusive interference model, it has not been thoroughly explored in the more general K-hop interference model. Moreover, empirical observations suggest that the known bounds are quite loose, and that the performance of GMS is often close to optimal. In this paper, we provide a number of new analytic results characterizing the performance limits of GMS. We first provide an equivalent characterization of the efficiency ratio of GMS through a topological property called the local-pooling factor of the network graph. We then develop an iterative procedure to estimate the local-pooling factor under a large class of network topologies and interference models. We use these results to study the worst-case efficiency ratio of GMS on two classes of network topologies. First, we show how these results can be applied to tree networks to prove that GMS achieves the full capacity region in tree networks under the K-hop interference model. Second, we show that the worst-case efficiency ratio of GMS in geometric network graphs is between 1/6 and 1/3.

In this paper we develop a distributed rate control algorithm for multiple-unicast-sessions when network coding is allowed. Building on our recent flow-based characterization of network coding, we formulate the problem as a convex optimization problem. The formulation exploits pairwise coding possibilities between any pair of sessions, where the objective function is the sum of the utilities based on the rates supported by each session. With some manipulation on the Lagrangian of the formulated problem, a distributed algorithm is developed with no interaction between intermediate nodes, and each source having the freedom to choose its own utility function. The only information required by the source is the weighted sum of the queue length updates of each link, which can be piggy-backed on the acknowledgment messages. In addition to the optimal rate control algorithm, we propose a decentralized pairwise random coding scheme (PRC) that is optimal when a sufficiently large finite field is used for network coding. The convergence of the rate control algorithm is proved analytically and verified by extensive simulations. Simulations also demonstrate the advantage of our algorithm over the state-of-the-art in terms of throughput and fairness.

Sleep-wake scheduling is an effective mechanism to prolong the lifetime of energy-constrained wireless sensor networks. However, it incurs an additional delay for packet delivery when each node needs to wait for its next-hop relay node to wake up, which could be unacceptable for delay-sensitive applications. Prior work in the literature has proposed to reduce this delay using anycast, where each node opportunistically selects the first neighboring node that wakes up among multiple candidate nodes. In this paper, we study the joint control problem of how to optimally control the sleep-wake schedule, the anycast candidate set of next-hop neighbors, and anycast priorities, to maximize the network lifetime subject to a constraint on the expected end-to-end delay. We provide an efficient solution to this joint control problem. Our numerical results indicate that the proposed solution can substantially outperform prior heuristic solutions in the literature, especially under the practical scenarios where there are obstructions in the coverage area of the wireless sensor network.

In this paper, we develop an energy-efficient routing scheme that takes into account three key wireless system elements: transmission power; interference; and residual energy. Since energy is a scarce resource, many energy-aware routing algorithms have been proposed to improve network performance. However, previous algorithms have been designed for a subset of these three main elements, which could limit their applicability. Thus, our contribution is here to develop a unified routing algorithm called the Energy-efficient Unified Routing (EURo) algorithm that accommodates any combination of these above key elements. We show via simulations that EURo outperforms the state-of-the-art.

Energy efficiency is critical for wireless sensor networks. The data gathering process must be carefully designed to conserve energy and extend the network lifetime. For applications where each sensor continuously monitors the environment and periodically reports to a base station, a tree-based topology is often used to collect data from sensor nodes. In this work, we study the construction of a data gathering tree to maximize the network lifetime, which is defined as the time until the first node depletes its energy. The problem is shown to be NP-complete. We design an algorithm which starts from an arbitrary tree and iteratively reduces the load on bottleneck nodes (nodes likely to soon deplete their energy due to high degree or low remaining energy). We show that the algorithm terminates in polynomial time and is provably near optimal.

We develop a class of schemes called GMWM that guarantee optimal throughput for queuing systems with arbitrary constraints on the set of jobs that can be served simultaneously. We obtain an analytical upper bound on the expected queue length. To further tighten the upper bound, we formulate it as a convex optimization problem. We also show that whenever the arrival process is stabilizable, the scheme is guaranteed to achieve an expected queue length that is no larger than the expected queue length of any stationary randomized policy.

Self-propagating codes, called worms, such as Code Red, Nimda, and Slammer, have drawn significant attention due to their enormously adverse impact on the Internet. Thus, there is great interest in the research community in modeling the spread of worms and in providing adequate defense mechanisms against them. In this paper, we present a (stochastic) branching process model for characterizing the propagation of Internet worms. The model is developed for uniform scanning worms and then extended to preference scanning worms. This model leads to the development of an automatic worm containment strategy that prevents the spread of a worm beyond its early stage. Specifically, for uniform scanning worms, we are able to 1) provide a precise condition that determines whether the worm spread will eventually stop and 2) obtain the distribution of the total number of hosts that the worm infects. We then extend our results to contain preference scanning worms. Our strategy is based on limiting the number of scans to dark-address space. The limiting value is determined by our analysis. Our automatic worm containment schemes effectively contain both uniform scanning worms and local preference scanning worms, and it is validated through simulations and real trace data to be nonintrusive. We also show that our worm strategy, when used with traditional firewalls, can be deployed incrementally to provide worm containment for the local network and benefit the Internet.

In this paper, we are interested in the connection-level stability of a network employing congestion control. In particular, we study how the stability region of the network (i.e., the set of offered loads for which the number of active users in the network remains finite) is affected by congestion control. Previous works in the literature typically adopt a time-scale separation assumption, which assumes that, whenever the number of users in the system changes, the data rates of the users are adjusted instantaneously to the optimal and fair rate allocation. Under this assumption, it has been shown that such rate assignment policies can achieve the largest possible stability region. In this paper, this time-scale separation assumption is removed and it is shown that the largest possible stability region can still be achieved by a large class of control algorithms. A second assumption often made in prior work is that the packets of a source (or user) are offered to each link along its path instantaneously, rather than passing through one queue at a time. We show that connection-level stability is again maintained when this assumption is removed, provided that a back-pressure scheduling algorithm is used jointly with the appropriate congestion controller.

Sleep-wake protocols are critical in sensor networks to ensure long-lived operation. However, an open problem is how to develop efficient mechanisms that can be incorporated with sleep-wake protocols to ensure both long-lived operation and a high degree of security. Our contribution in this paper is to address this problem by using local monitoring, a powerful technique for detecting and mitigating control and data attacks in sensor networks. In local monitoring, each node oversees part of the traffic going in and out of its neighbors to determine if the behavior is suspicious, such as, unusually long delay in forwarding a packet. Here, we present a protocol called SLAM to make local monitoring parsimonious in its energy consumption and to integrate it with any extant sleep-wake protocol in the network. The challenge is to enable sleep-wake in a secure manner even in the face of nodes that may be adversarial and not wake up nodes responsible for monitoring its traffic. We prove analytically that the security coverage is not weakened by the protocol. We perform simulations in ns-2 to demonstrate that the performance of local monitoring is practically unchanged while listening energy saving of 30 to 129 times is achieved, depending on the network load.

The performance of scheduling schemes in multi-hop wireless networks has attracted significant attention in the recent literature. It is well known that optimal scheduling solutions require centralized information and lead to impractical implementations due to their enormous complexity (high-degree polynomial or NP-hard, depending on the interference scenario). Further, multi-hop networks typically require distributed algorithms that operate on local information. Thus, in this paper, we develop a constant-time distributed random access algorithm for scheduling in multi-hop wireless networks. An important feature of this scheme is that it is guaranteed to achieve a fraction (efficiency factor) of the optimal performance. We show that this scheme theoretically achieves a superior efficiency factor as well as numerically achieves a significant performance improvement over the state-of-the-art. Simulation results also confirm that the performance of this scheme is close to a greedy centralized scheme.

In this paper, we analyze the impact of straight line routing in large homogeneous multi-hop wireless networks. We estimate the nodal load, which is defined as the number of packets served at a node, induced by straight line routing. For a given total offered load on the network, our analysis shows that the nodal load at each node is a function of the node's Voronoi cell, the node's location in the network, and the traffic pattern specified by the source and destination randomness and straight line routing. The traffic pattern determines where the hot spot is created in the network, and straight line routing itself can balance the relay load in certain cases. In the asymptotic regime, each node's probability that the node serves a packet arriving to the network can be approximated as the multiplication of a half length of its Voronoi cell perimeter and the probability density function that a packet goes through the node's location. Both simulations and analysis confirm that this approximation converges to the exact value. The scaling order of network performance in our analysis is independent of traffic patterns generated by source-destination pair randomness, but for a given node the performance of each node is strongly related to the source-destination pair randomness.

In this work, we study the problem of minimizing the total power consumption in a multi-hop wireless network subject to a given offered load. It is well-known that the total power consumption of multi-hop wireless networks can be substantially reduced by jointly optimizing power control, link scheduling, and routing. However, the known optimal cross-layer solution to this problem is centralized, and with high computational complexity. In this paper, we develop a low-complexity and distributed algorithm that is provably power-efficient. In particular, under the node exclusive interference model, we can show that the total power consumption of our algorithm is at most twice as large as the power consumption of the optimal (but centralized and complex) algorithm. Our algorithm is not only the first such distributed solution with provable performance bound, but its power-efficiency ratio is also tighter than that of another sub-optimal centralized algorithm in the literature.

We consider the problem of throughput-optimal cross-layer design of wireless networks. We propose a joint congestion control and scheduling algorithm that achieves a fraction 1/dI(G) of the capacity region, where dI(G) depends on certain structural properties of the underlying connectivity graph G of the wireless network and also on the type of interference constraints. For a wide range of wireless networks, dI(G) can be upper bounded by a constant, independent of the number of nodes in the network. The scheduling element of our algorithm is the maximal scheduling policy. Although maximal scheduling policy has been considered in many of the previous works, the difficulties that arise in implementing it in a distributed fashion in the presence of interference have not been dealt with previously. In this paper, we propose two novel randomized distributed algorithms for implementing the maximal scheduling policy under the 1-hop and 2-hop interference models.

We study sleep/wake scheduling for low duty cycle sensor networks. Our work is different from prior work in that we explicitly consider the effect of synchronization error in the design of the sleep/wake scheduling algorithm. In our previous work, we have studied sleep/wake scheduling for single hop communications, e.g., intra-cluster communications between a cluster head and cluster members. We showed that the there is an inherent trade-off between energy consumption and message delivery performance (defined as the message capture probability). We proposed an optimal sleep/wake scheduling algorithm, which satisfies a message capture probability threshold (assumed to be given) with minimum energy consumption. In this work, we consider multi-hop communications. We remove the previous assumption that the capture probability threshold is already given, and study how to decide the per-hop capture probability thresholds to meet the quality of services (QoS) requirements of the application. In many sensor network applications, the QoS is decided by the amount of data delivered to the base station(s), i.e., the multi-hop delivery performance. We formulate an optimization problem, which aims to set the capture probability threshold at each hop such that the network lifetime is maximized, while the multi-hop delivery performance is guaranteed. The problem turns out to be non-convex and hard to solve exactly. By investigating the unique structure of the problem and using approximation techniques, we obtain a solution that achieves at least 0.73 of the optimal performance.

It is well known that queues with exponentially distributed service times have the smallest Shannon capacity among all single-server queues with the same service rate. In this paper, we study the capacity of timing channels in which the service time distributions have bounded support, i.e., Bounded Service Timing Channels (BSTC). We derive an upper bound and two lower bounds on the capacity of such timing channels. The tightness of these bounds is investigated analytically as well as via simulations. We find that the uniform BSTC serves a role for BSTCs that is similar to what the exponential service timing channel does for the case of timing channels with unbounded service time distributions. That is, when the length of the support interval is small, the uniform BSTC has the smallest capacity among all BSTCs.

The problem of network coding with two simple unicast sessions is considered for general directed acyclic graphs. An explicit graph-theoretic characterization is provided for the feasibility of whether two symbols at different sources can be simultaneously transmitted to the designated sinks via network coding. The existence of a routing scheme is equivalent to finding edge-disjoint paths. Similarly, in this paper it is proven that the existence of a network coding scheme is equivalent to finding paths with controlled edge overlaps, and the characterization includes the well-studied butterfly graph as a special case. Various generalizations and implications are discussed based on the constructive nature of the flow-based conditions. For example, it is shown that a linear network coding scheme using only six paths is as effective as any non-linear network coding scheme.

In this paper, we develop an energy efficient routing scheme that takes into account the interference created by existing flows in the network. Unlike previous works, we explicitly study the impact of routing a new flow on the energy consumption of the network. Under certain assumptions on how links are scheduled, we can show that our proposed algorithm is asymptotically (in time) optimal in terms of minimizing the average energy consumption. We also develop a distributed version of the algorithm. Our algorithm automatically detours around a congested area in the network, which helps mitigate network congestion and improve overall network performance. Using simulations, we show that the routes chosen by our algorithm (centralized and distributed) are more energy efficient than the state of the art.

We study sleep/wake scheduling for low-duty cycle sensor networks. Our work is different from previous work in that we explicitly consider the effect of the synchronization error. We study a widely used synchronization scheme and show that the synchronization error is non-negligible, and using a conservative guard time is energy wasteful. Hence, we formulate an optimization problem to minimize the expected energy consumption, with the constraint that the message capture probability should be no less than a threshold. We find that the problem is non-convex, hence cannot be solved by conventional convex optimization techniques. By investigating the unique structure of the problem, we transform the problem into a convex equivalent, and solve it using an efficient search method. Simulations show that our scheme significantly outperforms schemes that do not intelligently consider the synchronization error. We also remove the assumption that the capture probability threshold is given, and study how to decide it to meet the quality of services (QoS) requirements of the application

We consider the problem of throughput-optimal scheduling in wireless networks subject to interference constraints. We model the interference using a family of K -hop interference models. We define a K-hop interference model as one for which no two links within K hops can successfully transmit at the same time (Note that IEEE 802.11 DCF corresponds to a 2-hop interference model.) .For a given K, a throughput-optimal scheduler needs to solve a maximum weighted matching problem subject to the K-hop interference constraints. For K=1, the resulting problem is the classical Maximum Weighted Matching problem, that can be solved in polynomial time. However, we show that for K>1,the resulting problems are NP-Hard and cannot be approximated within a factor that grows polynomially with the number of nodes. Interestingly, we show that for specific kinds of graphs, that can be used to model the underlying connectivity graph of a wide range of wireless networks, the resulting problems admit polynomial time approximation schemes. We also show that a simple greedy matching algorithm provides a constant factor approximation to the scheduling problem for all K in this case. We then show that under a setting with single-hop traffic and no rate control, the maximal scheduling policy considered in recent related works can achieve a constant fraction of the capacity region for networks whose connectivity graph can be represented using one of the above classes of graphs. These results are encouraging as they suggest that one can develop distributed algorithms to achieve near optimal throughput in case of a wide range of wireless networks.

This tutorial paper overviews recent developments in optimization-based approaches for resource allocation problems in wireless systems. We begin by overviewing important results in the area of opportunistic (channel-aware) scheduling for cellular (single-hop) networks, where easily implementable myopic policies are shown to optimize system performance. We then describe key lessons learned and the main obstacles in extending the work to general resource allocation problems for multihop wireless networks. Towards this end, we show that a clean-slate optimization-based approach to the multihop resource allocation problem naturally results in a "loosely coupled" cross-layer solution. That is, the algorithms obtained map to different layers [transport, network, and medium access control/physical (MAC/PHY)] of the protocol stack, and are coupled through a limited amount of information being passed back and forth. It turns out that the optimal scheduling component at the MAC layer is very complex, and thus needs simpler (potentially imperfect) distributed solutions. We demonstrate how to use imperfect scheduling in the cross-layer framework and describe recently developed distributed algorithms along these lines. We conclude by describing a set of open research problems.

There has been significant recent interest within the networking research community to characterize the impact of mobility on the capacity and delay in mobile ad hoc networks. In this correspondence, the fundamental tradeoff between the capacity and delay for a mobile ad hoc network under the Brownian motion model is studied. It is shown that the two-hop relaying scheme proposed by Grossglauser and Tse (2001), while capable of achieving a per-node throughput of /spl Theta/(1), incurs an expected packet delay of /spl Omega/(logn//spl sigma//sub n//sup 2/), where /spl sigma//sub n//sup 2/ is the variance parameter of the Brownian motion model. It is then shown that an attempt to reduce the delay beyond this value results in the throughput dropping to its value under static settings. In particular, it is shown that under a large class of scheduling and relaying schemes, if the mean packet delay is O(n/sup /spl alpha////spl sigma//sub n//sup 2/), for any /spl alpha/<0, then the per-node throughput must be O(1//spl radic/n). This result is in sharp contrast to other results that have recently been reported in the literature.

In this paper, we present an opportunistic power scheduling scheme, i.e., a joint time-slot and power allocation scheme for downlink communication in wireless systems. Unlike past works, we allow multiple transmissions in a time-slot that could potentially interfere with each other. These multiple transmissions are allowed to achieve high system efficiency. Hence, it is important to not only select the mobiles to be scheduled in a time-slot, but also to allocate an appropriate transmission power level to these scheduled mobiles. We model the time-varying wireless channel as a stochastic process and formulate a stochastic optimization problem that attempts to maximize the expected total system utility with general constraints on performance or fairness. The power scheduling algorithm is obtained by using stochastic duality and implemented via stochastic subgradient techniques

In this paper, we propose a new geographic routing algorithm that alleviates the effect of location errors on routing in wireless ad hoc networks. In most previous work, geographic routing has been studied assuming perfect location information. However, in practice there could be significant errors in obtaining location estimates, even when nodes use GPS. Hence, existing geographic routing schemes will need to be appropriately modified. We investigate how such location errors affect the performance of geographic routing strategies. We incorporate location errors into our objective function by considering both transmission failures and backward progress. Each node then forwards packets to the node that maximizes this objective function. We call this strategy maximum expectation within transmission range (MER). Simulation results with MER show that accounting for location errors significantly improves the performance of geographic routing. We also show that MER is robust to the location error model and model parameters. Further, via simulations, we show that in a mobile environment MER performs better than existing approaches.

In multihop wireless systems, such as ad-hoc and sensor networks, the need for cooperation among nodes to relay each other's packets exposes them to a wide range of security attacks. A particularly devastating attack is known as the wormhole attack, where a malicious node records control and data traffic at one location and tunnels it to a colluding node, which replays it locally. This can have an adverse effect in route establishment by preventing nodes from discovering routes that are more than two hops away. In this paper, we present a lightweight countermeasure for the wormhole attack, called LITEWORP, which does not require specialized hardware. LITEWORP is particularly suitable for resource-constrained multihop wireless networks, such as sensor networks. Our solution allows detection of the wormhole, followed by isolation of the malicious nodes. Simulation results show that every wormhole is detected and isolated within a very short period of time over a large range of scenarios. The results also show that the fraction of packets lost due to the wormhole when LITEWORP is applied is negligible compared to the loss encountered when the method is not applied.

Self-propagating codes, called worms, such as Code Red, Nimda, and Slammer, have drawn significant attention due to their enormous adverse impact on the Internet. There is a great interest in the research community in modeling the spread of worms and in providing adequate defense mechanisms against them. In this paper, we present a (stochastic) branching process model for characterizing the propagation of Internet worms. This model leads to the development of an automatic worm containment strategy that prevents the spread of worms beyond its early stages. Specifically, using the branching process model, we are able to (1) provide a precise condition that determines whether the worm will eventually die out and (2) provide the probability that the total number of hosts that the worm infects will be below a certain level. We use these insights to develop a simple automatic worm containment scheme, which is demonstrated, through simulations and real trace data, to be both effective and non-intrusive.

In this paper, we study cross-layer design for rate control in multihop wireless networks. In our previous work, we have developed an optimal cross-layered rate control scheme that jointly computes both the rate allocation and the stabilizing schedule that controls the resources at the underlying layers. However, the scheduling component in this optimal cross-layered rate control scheme has to solve a complex global optimization problem at each time, and hence is too computationally expensive for online implementation. In this paper, we study how the performance of cross-layer rate control can be impacted if the network can only use an imperfect (and potentially distributed) scheduling component that is easier to implement. We study both the case when the number of users in the system is fixed and the case with dynamic arrivals and departures of the users, and we establish desirable results on the performance bounds of cross-layered rate control with imperfect scheduling. Compared with a layered approach that does not design rate control and scheduling together, our cross-layered approach has provably better performance bounds, and substantially outperforms the layered approach. The insights drawn from our analyses also enable us to design a fully distributed cross-layered rate control and scheduling algorithm for a restrictive interference model.

In this paper, we model and characterize the performance of multihop radio networks in the presence of energy constraints and design routing algorithms to optimally utilize the available energy. The energy model allows vastly different energy sources in heterogeneous environments. The proposed algorithm is shown to achieve a competitive ratio (i.e., the ratio of the performance of any off-line algorithm that has knowledge of all past and future packet arrivals to the performance of our online algorithm) that is asymptotically optimal with respect to the number of nodes in the network. The algorithm assumes no statistical information on packet arrivals and can easily be incorporated into existing routing frameworks (e.g., proactive or on-demand methodologies) in a distributed fashion. Simulation results confirm that the algorithm performs very well in terms of maximizing the throughput of an energy-constrained network. Further, a new threshold-based scheme is proposed to reduce the routing overhead while incurring only minimum performance degradation.

In this talk we study the issue of cross-layer design for rate control in multihop wireless networks. We have developed an optimal cross-layered rate control scheme that jointly computes both the rate allocation and the stabilizing schedule that controls the resources at the underlying layers. However, the scheduling component in this optimal cross-layered rate control scheme has to solve a complex global optimization problem at each time, and is hence too computationally expensive for online implementation. Thus, we study the impact on the performance of cross-layer rate control if the network can only use an imperfect (and potentially distributed) scheduling component that is easier to implement. We study scenarios with both fixed number of users as well as when the number of users change due to arrivals and departures in the system. In each case, we establish desirable results on the performance bounds of cross-layered rate control with imperfect scheduling. Our cross-layered approach provides provably better performance bounds when compared with a layered approach (that does not design rate control and scheduling together). The insights drawn from our analyses also enable us to design a fully distributed cross-layered rate control and scheduling algorithm under a restrictive interference model.

We consider a heterogeneous sensor network in which nodes are to be deployed over a unit area for the purpose of surveillance. An aircraft visits the area periodically and gathers data about the activity in the area from the sensor nodes. There are two types of nodes that are distributed over the area using two-dimensional homogeneous Poisson point processes; type 0 nodes with intensity (average number per unit area) /spl lambda//sub 0/ and battery energy E/sub 0/; and type 1 nodes with intensity /spl lambda//sub 1/ and battery energy E/sub 1/. Type 0 nodes do the sensing while type 1 nodes act as the cluster heads besides doing the sensing. Nodes use multihopping to communicate with their closest cluster heads. We determine them optimum node intensities (/spl lambda//sub 0/, /spl lambda//sub 1/) and node energies (E/sub 0/, E/sub 1/) that guarantee a lifetime of at least T units, while ensuring connectivity and coverage of the surveillance area with a high probability. We minimize the overall cost of the network under these constraints. Lifetime is defined as the number of successful data gathering trips (or cycles) that are possible until connectivity and/or coverage are lost. Conditions for a sharp cutoff are also taken into account, i.e., we ensure that almost all the nodes run out of energy at about the same time so that there is very little energy waste due to residual energy. We compare the results for random deployment with those of a grid deployment in which nodes are placed deterministically along grid points. We observe that in both cases /spl lambda//sub 1/ scales approximately as /spl radic/(/spl lambda//sub 0/). Our results can be directly extended to take into account unreliable nodes.

We show that significant simplicities can be obtained for the analysis of a network when link capacities are large enough to carry many flows. We develop a network decomposition approach in which network analysis can be greatly simplified. We prove that the queue length at the downstream queue converges to that of a single queue obtained by removing the upstream queue, as the capacity and the number of flows at the upstream queue increase. The precise modes of convergence vary depending on the type of input traffic, i.e., from regulated traffic arrivals to point process inputs. Our results thus help simplify network analysis by decomposing the original network into a simplified network in which all the nodes with large capacity have been eliminated. By means of extensive numerical investigation under various network scenarios, we demonstrate different aspects and implications of our network decomposition approach. Some of our findings are that our techniques perform well especially for the cases when: i) many flows are multiplexed as they enter the queue and/or ii) departing flows are routed to different downstream nodes, i.e., no single flow dominates at any node.

In this paper, we investigate the problem of distributively allocating transmission data rates to users in the Internet. We allow users to have concave as well as sigmoidal utility functions as appropriate for different applications. In the literature, for simplicity, most works have dealt only with the concave utility function. However, we show that applying rate control algorithms developed for concave utility functions in a more realistic setting (with both concave and sigmoidal types of utility functions) could lead to instability and high network congestion. We show that a pricing-based mechanism that solves the dual formulation can be developed based on the theory of subdifferentials with the property that the prices "self-regulate" the users to access the resources based on the net utility. We discuss convergence issues and show that an algorithm can be developed that is efficient in the sense of achieving the global optimum when there are many users.

In this paper we consider a power allocation problem in multi-class wireless systems. We focus on the downlink of the system. Each mobile has a utility function that characterizes its degree of satisfaction for the received service. The objective is to obtain a power allocation that maximizes the total system utility. Typically, natural utility functions for each mobile are nonconcave. Hence, we cannot use existing convex optimization techniques to derive a global optimal solution. We develop a simple (distributed) algorithm to obtain a power allocation that is asymptotically optimal in the number of mobiles. The algorithm is based on dynamic pricing and consists of two stages. At the mobile selection stage, the base station selects mobiles to which power is allocated. At the power allocation stage, the base station allocates power to the selected mobiles. We provide numerical results that illustrate the performance of our scheme. In particular, we show that our algorithm results in system performance that is close to the performance of a global optimal solution in most cases.

We show that when networks are large significant simplicity can be achieved for pricing-based control. We first consider a general loss network with Poisson arrivals and arbitrary holding time distributions. In dynamic pricing schemes, the network provider can charge different prices to the user according to the current utilization level of the network and also other factors. We show that when the system becomes large the performance (in terms of expected revenue) of an appropriately chosen static pricing scheme, whose price is independent of the current network utilization, will approach that of the optimal dynamic pricing scheme. Further, we show that under certain conditions, this static price is independent of the route that the flows take. We then extend the result to the case of dynamic routing, and show that the performance of an appropriately chosen static pricing scheme with bifurcation probability determined by average parameters can also approach that of the optimal dynamic routing scheme when the system is large. These results deepen our understanding of pricing-based network control. In particular, they provide us with the insight that, when the system is large, an appropriate pricing strategy based on the average network conditions (hence, slowly changing) can approach optimality.

In this paper, we consider a network with both controllable and uncontrollable flows. Uncontrollable flows are typically generated from applications with stringent QoS requirements and are given high priority. On the other hand, controllable flows are typically generated by elastic applications and can adapt to the available link capacities in the network. We provide a general model of such a system and analyze its queueing behavior. Specially, we obtain a lower bound and an asymptotic upper bound for the tail of the workload distribution at each link in the network. These queueing results provide us with guidelines on how to design a feedback flow control system. Simulation results show that the lower bound and asymptotic upper bound are quite accurate and that our feedback control method can effectively control the queue length in the presence of both controllable and uncontrollable traffic. Finally, we describe a distributed strategy that uses the notion of Active Queue Management (AQM) for implementing our flow control solution.

In this paper, we investigate the problem of distributively allocating transmission rates to users on the Internet. We allow users to have concave as well as sigmoidal utility functions that are natural in the context of various applications. In the literature, for simplicity, most works have dealt only with the concave case. However, we show that when applying rate control algorithms developed for concave utility functions in a more realistic setting (with both concave and sigmoidal types of utility functions), they could lead to instability and high network congestion. We show that a pricing based mechanism that solves the dual formulation can be developed based on the theory of subdifferentials with the property that the prices "self-regulate" the users to access the resource based on the net utility. We discuss convergence issues and show that an algorithm can be developed that is efficient in the sense of achieving the global optimum when there are many users.

We present and power scheduling scheme, i.e., a joint time-slot and power allocation method for wireless cellular systems. We allow multiple transmissions in a time-slot that can interfere with each other. Hence, it is important to not only select the mobiles to he scheduled in a time-slot, hut also important to allocate an appropriate power level for transmission to these scheduled mobiles in order to achieve high system performance and quality of service. We model the time-varying wireless channel as a stochastic process and formulate a stochastic programming problem that attempts to maximize the expected total system utility, with constraints on the minimum expected utility for each mobile. The power scheduling algorithm is obtained by using stochastic duality and implemented via stochastic subgradient techniques.

In this paper, we propose an optimization based approach for quality of service routing in high-bandwidth networks. We view a network that employs QoS routing as an entity that distributively optimizes some global utility function. By solving the optimization problem, the network is driven to an efficient operating point. In earlier work, it has been shown that when the capacity of the network is large, this optimization takes on a simple form, and once the solution to this optimization problem is found, simple proportional QoS routing schemes will suffice. However, this optimization problem requires global information. We develop a distributed and adaptive algorithm that can efficiently solve the optimization online. Compared with existing QoS routing schemes, the proposed optimization based approach has the following advantages: (1) The computation and communication overhead can be greatly reduced without sacrificing performance; (2) The operating characteristics of the network can be analytically studied; and (3) The desired operating point can be tuned by choosing appropriate utility functions.

We present a study of topological characteristics of mobile wireless ad-hoc networks. The characteristics studied are connectivity, coverage, and diameter. Knowledge of topological characteristics of a network aids in the design and performance prediction of network protocols. We introduce intelligent goal-directed mobility algorithms for achieving desired topological characteristics. A simulation-based study shows that to achieve low, medium and high network QoS defined in terms of combined requirements of the three metrics, the network needs respectively 8, 16, and 40 nodes. If nodes can fail, the requirements increase to 8, 36 and 60 nodes respectively. We present a theoretical derivation of the improvement due to the mobility models and the sufficient condition for 100% connectivity and coverage. Next, we show the effect of improved topological characteristics in enhancing QoS of an application level protocol, namely, a location determination protocol called Hop-Terrain. The study shows that the error in location estimation is reduced by up to 68% with goal-directed mobility.

In this paper, we develop a new predictive flow control scheme and analyze its performance. This scheme controls the nonreal-time (controllable) traffic based on predicting the real-time (uncontrollable) traffic. The goal of the work is to operate the network in a low congestion, high throughput regime. We provide a rigorous analysis of the performance of our flow control method and show that the algorithm has attractive and useful properties. From our analysis we obtain an explicit condition that gives us design guidelines on how to choose a predictor. We learn that it is especially important to take the queueing effect into account in developing the predictor. We also provide numerical results comparing different predictors that use varying degrees of information from the network.

In this paper, we show that significant simplicities can arise in the analysis of a network when link capacities are large enough to carry many flows. In particular, we prove that, when an upstream queue serves a large number of regulated traffic sources, the queue-length of the downstream queue converges almost surely to the queue-length of a simplified queueing system (single queue) obtained by removing the upstream queue. We provide similar results (convergence of the queue-length in distribution) for general (including nonregulated) traffic arrivals. In both cases, the convergence of the overflow probability is uniform and at least exponentially fast. Through an extensive numerical investigation, we demonstrate several aspects and implications of our results in simplifying network analysis.

We consider an unreliable wireless sensor grid-network with n nodes placed in a square of unit area. We are interested in the coverage of the region and the connectivity of the network. We first show that the necessary and sufficient conditions for the random grid network to cover the unit square region as well as ensure that the active nodes are connected are of the form p(n)r2(n) ~ log(n)/n, where r(n) is the transmission radius of each node and p(n) is the probability that a node is "active" (not failed). This result indicates that, when n is large, even if each node is highly unreliable and the transmission power is small, we can still maintain connectivity with coverage. We also show that the diameter of the random grid (i.e., the maximum number of hops required to travel from any active node to another) is of the order √{n/log(n)}. Finally, we derive a sufficient condition for connectivity of the active nodes (without necessarily having coverage). If the node success probability p(n) is small enough, we show that connectivity does not imply coverage.

We describe a measurement-analytic approach for estimating the overflow probability, an important measure of the quality of service (QoS), at a given multiplexing point in the network. A multiplexing point in the network could be a multiplexer or an output port of a switch or router where resources such as bandwidth and buffers are shared. Our approach impinges on using the notion of the dominant time scale (DTS), which corresponds to the most probable time scale over which overflow occurs. The DTS provides us with a measurement window for the statistics of the traffic, but is in fact itself defined in terms of the statistics of the traffic over all time. This, in essence, results in a chicken-and-egg type of unresolved problem. For the DTS to be useful for on-line measurements, we need to be able to break this chicken-and-egg cycle, and to estimate the DTS with only a bounded window of time over which the statistics of the traffic are to be measured. We present a stopping criterion to successfully break this cycle and find a bound on the DTS. Thus, the result has significant implications for network measurements. Our approach is quite different from other works in the literature that require off-line measurements of the entire trace of the traffic. In our case, we need to measure only the statistics of the traffic up to a bound on the DTS. We also investigate the characteristics of this upper bound on the DTS, and provide numerical results to illustrate the utility of our measurement analytic approach.

Distributed power-control algorithms for systems with hard signal-to-interference ratio (SIR) constraints may diverge when infeasibility arises. We present a power-control framework called utility-based power control (UBPC) by reformulating the problem using a softened SIR requirement (utility) and adding a penalty on power consumption (cost). Under this framework, the goal is to maximize the net utility, defined as utility minus cost. Although UBPC is still noncooperative and distributed in nature, some degree of cooperation emerges: a user will automatically decrease its target SIR (and may even turn off transmission) when it senses that traffic congestion is building up. This framework enables us to improve system convergence and to satisfy heterogeneous service requirements (such as delay and bit error rate) for integrated networks with both voice users and data users. Fairness, adaptiveness, and a high degree of flexibility can be achieved by properly tuning parameters in UBPC.

We use a utility based power allocation framework in the downlink to treat multi-class CDMA wireless services in a unified way. Our goal is to obtain a power allocation which maximizes the total system utility. Natural utility functions for each mobile are non-concave. Hence we cannot use existing techniques on convex optimization problems to derive a social optimal solution. We propose a simple distributed algorithm to obtain an approximation to the social optimal power allocation. The algorithm is based on dynamic pricing and allows partial cooperation between mobiles and the base station. The algorithm consists of two stages. At the first stage, the base station selects mobiles to which power is allocated, considering their partial-cooperative nature. This is called partial-cooperative optimal selection, since in a partial-cooperative setting and pricing scheme, this selection is optimal and satisfies system feasibility. At the next stage, the base station allocates power to the selected mobiles. This power allocation is a social optimal power allocation among mobiles in the partial-cooperative optimal selection, thus, we call it a partial-cooperative optimal power allocation. We compare the partial-cooperative optimal power allocation with the social optimal power allocation for the single class case. From these results, we infer that the system utility obtained by partial-cooperative optimal power allocation is quite close to the system utility obtained by social optimal allocation.

We study bursty data communications in the downlink in code division multiple access (CDMA) systems. We first present a new model that simultaneously takes into account the traffic burstiness and time-varying fading for studying the multi-access interference (MAI), and characterize the MAI from a stochastic process perspective. This new approach enables us to understand the temporal correlation structure. Our finding reveals that the MAI exhibits scale-invariant burstiness and is "self similar" across multiple time scales. The MAI self similarity indicates the existence of a nontrivial predictive MAI structure, which we exploit to conduct resource allocation for interference management. In particular, we utilize the MAI temporal structure to construct a multiple time-scale interference predictor, which is used to predict the MAI level. Rate adaptation is then carried out based on the predicted MAI. Our results show that this rate control scheme achieves better performance than that of the packet-level predictor, and can yield significant performance gain. We also devise a joint rate control and admission control scheme. Specifically, observation time windows are divided into slots, and rate control based on interference prediction is conducted in each slot. Then, the corresponding throughput in each observation window is used for admission control. We also investigate the impact of feedback delay and data burstiness on the system performance.

In ATM networks cell loss or channel errors can cause data to be dropped in the channel. When digital images/video are transmitted over these networks one must be able to reconstruct the missing data so that the impact of the errors is minimized. We overview the problem of using EZW encoders in channels where data-loss is possible. We also describe an error resilience scheme based on unequal error protection and data interleaving that addresses the problem of using rate scalable encoders over ATM networks.

In this paper we describe a measurement-analytic framework for estimating the overflow probability, an important measure of quality of service (QoS), at a given multiplexing point in the network. A multiplexing point in the network could be a multiplexer or an output port of a switch where resources such as bandwidth and buffers are shared. Our approach impinges on using the notion of the dominant or critical time scale, which corresponds to the time-scale relevant for describing the queueing behavior based on particular network configurations. The dominant time-scale provides us with a measurement window for the statistics of the traffic, but is unfortunately itself defined in terms of the statistics of the traffic over all time. This in essence results in a chicken and an egg type of unresolved problem. For the dominant time scale to be useful for on-line measurements, we need to be able to break this chicken and egg type of cycle. In this paper, we present a stopping criterion to successfully break this cycle through online measurements and find a bound on the dominant time scale. Thus, the result has significant implications for network measurements. Our approach is quite different from other works in the literature that require off-line measurements of the entire trace of the traffic (since in our case, we need to measure only the statistics of the traffic up to a bound on the dominant time scale.) We also investigate the characteristics of this upper bound on the dominant time scale, and provide numerical results to illustrate the utility of our measurement analytic approach.

We present an "opportunistic" transmission scheduling policy that exploits time-varying channel conditions and maximizes the system performance stochastically under a certain resource allocation fairness constraint. We establish the optimality of the scheduling scheme and also describe a practical scheduling procedure to implement our scheme. Through simulation results, we show that the scheme also works well for nonstationary scenarios and results in performance improvements of 20-150% compared with a scheduling scheme that does not take into account channel conditions. Furthermore, we note that in wireless networks, an important role of resource allocation is to balance the system performance and fairness among "good" and "bad" users. We propose three heuristic time-fraction assignment schemes, which approach the problem from different viewpoints.

Distributed power control algorithms for systems with hard SIR constraints may diverge when infeasibility arises. We present a power control framework called utility-based power control (UBPC) by reformulating the problem using a softened SIR requirement (utility) and adding a penalty on power consumption (cost). Under this framework, the goal is to maximize the net utility, defined as utility minus cost. Although UBPC is still non-cooperative and distributed in nature, some degree of cooperation emerges: a user will automatically decrease its target SIR (and may even turn off transmission) when it senses that traffic congestion is building up. This framework enables us to improve the system convergence and to satisfy heterogeneous service requirements (such as delay and bit error rate) for integrated networks with both voice users and data users. Fairness, adaptiveness, and a high degree of flexibility can be achieved by properly tuning parameters in UBPC.

We present an "opportunistic" transmission scheduling scheme that exploits time-varying channel conditions and maximizes the average system performance under minimum-performance guarantees. We establish the optimality of the scheduling scheme, and show that the proposed opportunistic scheduling scheme can provide a "no-loss" guarantee compared to non-opportunistic scheduling policies. Furthermore, we show that the feasibility region of users' requirements is convex, and discuss the associated admission control issues. Last, through simulation results, we show that the scheme results in significant performance improvement.

We present an "opportunistic" transmission scheduling policy that exploits time-varying channel conditions and maximizes the system performance stochastically under a certain resource allocation constraint. We establish the optimality of the scheduling scheme and also that every user experiences a performance improvement over any nonopportunistic scheduling policy when users have independent performance values. We demonstrate via simulation results that the scheme is robust to estimation errors and also works well for nonstationary scenarios, resulting in performance improvements of 20%-150% compared with a scheduling scheme that does not take into account channel conditions. Last, we discuss an extension of our opportunistic scheduling scheme to improve "short-term" performance.

We propose an approximation for the loss probability, P/sub L/(x), in a finite buffer system with buffer size x. Our study is motivated by the case of a high-speed network where a large number of sources are expected to be multiplexed. Hence, by appealing to central limit theorem type of arguments, we model the input process as a general Gaussian process. Our result is obtained by making a simple mapping from the tail probability in an infinite buffer system to the loss probability in a finite buffer system. We also provide a strong asymptotic relationship between our approximation and the actual loss probability for a fairly large class of Gaussian input processes. We derive some interesting asymptotic properties of our approximation and illustrate its effectiveness via a detailed numerical investigation.

It is well known that power control can help to improve spectrum utilization in cellular wireless systems. However, many existing distributed power control algorithms do not work well without an effective connection admission control (CAC) mechanism, because they could diverge and result in dropping existing calls when an infeasible call is admitted. In this work, based on a system parameter defined as the discriminant, we propose two distributed CAC algorithms for a power-controlled system. Under these CAC schemes, an infeasible call is rejected early, and incurs only a small disturbance to existing calls, while a feasible call is admitted and the system converges to the Pareto optimal power assignment. Simulation results demonstrate the performance of our algorithms.

When transmitting compressed video over a data network, one has to deal with how channel errors affect the decoding process. This is particularly a problem with data loss or erasures. In this paper we describe techniques to address this problem in the context of asynchronous transfer mode (ATM) networks. Our techniques can be extended to other types of data networks such as wireless networks. In ATM networks channel errors or congestion cause data to be dropped, which results in the loss of entire macroblocks when MPEG video is transmitted. In order to reconstruct the missing data, the location of these macroblocks must be known. We describe a technique for packing ATM cells with compressed data, whereby the location of missing macroblocks in the encoded video stream can be found. This technique also permits the proper decoding of correctly received macroblocks, and thus prevents the loss of ATM cells from affecting the decoding process. The packing strategy can also be used for wireless or other types of data networks. We also describe spatial and temporal techniques for the recovery of lost macroblocks. In particular, we develop several optimal estimation techniques for the reconstruction of missing macroblocks that contain both spatial and temporal information using a Markov random field model. We further describe a sub-optimal estimation technique that can be implemented in real time.

With the advent of high-speed networks, a single link will carry hundreds or even thousands of applications. This results in a very natural application of the central limit theorem, to model the network traffic by a Gaussian stochastic processes. We study the tail probability P({Q>x}) of a queueing system when the input process is assumed to be a very general class of Gaussian processes which includes a large class of self similar or other types of long-range dependent Gaussian processes. For example, past work on fractional Brownian motion, and variations therein, are but a small subset of the work presented in this paper. This study is based on extreme value theory and we show that log P({Q>x})+m/sub x//2 grows at most on the order of logx, where m/sub x/ corresponds to the reciprocal of the maximum (normalized) variance of a Gaussian process directly related to the aggregate input process. The result is considerably stronger than the existing results in the literature based on large deviation theory, and we theoretically show that this improvement can be quite important in characterizing the asymptotic behavior of P({Q>x}). Through numerical examples, we also demonstrate that exp[-m/sub x//2] provides a very accurate estimate for a variety of long-range and short-range dependent input processes over the entire buffer range.

We study an approach for sharing channels to improve network utilization in packet-switched cellular networks. This scheme exploits unused resources in neighboring cells without the need for global coordination. We formulate a minimax approach to optimizing the allocation of channels in this sharing scheme. We develop a distributed algorithm to achieve this objective and study its convergence. We illustrate, via simulation results, that the distributed channel sharing scheme performs better than the fixed channel scheme over a wide variety of traffic conditions.

We present a novel static power control scheme to improve system capacity in wireless cellular networks. Our basic idea is to reduce intercellular interference and improve the capture probability by coordinating transmission powers of users in different cells. This coordination is determined beforehand and no real-time coordination is required. Power control is static and fixed. We formulate and solve a generic optimal scheduling problem with our coordination scheme. We find that the optimal scheduling policy is in a simple form of bang-bang control, which is illustrated for a specific case with the uniform fairness constraint. We evaluate, via numerical analysis and simulation, both throughput and delay, and compare them with other schemes. We find that the coordination scheme can achieve significant performance improvement, in terms of both maximum throughput and throughput-delay tradeoff, over a wide range of capture ratio values.

Enhancing system capacity while maintaining quality of service is an important issue in wireless cellular networks. In this paper, we present a localized channel sharing scheme to address this problem. Our basic idea is to allow channels to be shared between adjacent cells at the expense of a smaller initial allocation of channels per cell. We show that this tradeoff results in a better utilization of network resources. An important feature of our sharing scheme is that channel management is localized between adjacent cells, and no global coordination or optimization is required, thus making it suitable for implementation. The sharing scheme can also facilitate handoff processing. We provide numerical results comparing our scheme with the channel reservation technique, and find a significant performance improvement over a wide range of traffic parameters and a variety of quality of service requirements.

In this paper, we propose a novel feedforward adaptive quantization scheme called the sample-adaptive product quantizer (SAPQ). This is a structurally constrained vector quantizer that uses unions of product codebooks. SAPQ is based on a concept of adaptive quantization to the varying samples of the source and is very different from traditional adaptation techniques for nonstationary sources. SAPQ quantizes each source sample using a sequence of quantizers. Even when using scalar quantization in SAPQ, we can achieve performance comparable to vector quantization (with the complexity still close to that of scalar quantization). We also show that important lattice-based vector quantizers can be constructed using scalar quantization in SAPQ. We mathematically analyze SAPQ and propose a algorithm to implement it. We numerically study SAPQ for independent and identically distributed Gaussian and Laplacian sources. Through our numerical study, we find that SAPQ using scalar quantizers achieves typical gains of 13 dB in distortion over the Lloyd-Max quantizer. We also show that SAPQ can he used in conjunction with vector quantizers to further improve the gains.

We present a new scheme that addresses the call handoff problem in mobile cellular networks. Efficiently solving the handoff problem is important for guaranteeing quality of service to already admitted calls in the network. Our scheme is based on a new approach called channel carrying: when a mobile user moves from one cell to another, render certain mobility conditions, the user is allowed to carry its current channel into the new cell. We propose a new channel assignment scheme to ensure that this movement of channels will not lead to any extra co-channel interference or channel locking. In our scheme, the mobility of channels relies entirely on localized information, and no global coordination is required. Therefore, the scheme is simple and easy to implement. We further develop a hybrid channel carrying scheme that allows us to maximize performance under various constraints.

We present a novel reduced-power channel reuse scheme to improve the spectrum efficiency in wireless packet cellular networks. The basic idea is to reduce intercellular interference and improve the capture probability by an a priori assignment of power levels of channels used in different cells. We formulate and solve an optimal channel-selection problem for our scheme. We find that the optimal policy is in a form of bang-bang control. We illustrate our channel-selection solution by a case study with uniform fairness constraint. We evaluate, via numerical analysis and simulation, both throughput and delay of the new scheme, and compare them with other schemes. We find that our scheme can achieve significant performance improvements, in terms of both the maximum throughput and throughput-delay tradeoff, over a wide range of capture ratio values.

We study P({Q>x}), the tail of the steady state queue length distribution at a high-speed multiplexer. The tail probability distribution P({Q>x}) is a fundamental measure of network congestion and thus important for the efficient design and control of networks. In particular, we focus on the case when the aggregate traffic to the multiplexer can be characterized by a stationary Gaussian process. In our approach, a multiplexer is modeled by a fluid queue serving a large number of input processes. We propose two asymptotic upper bounds for P({Q>x}), and provide several numerical examples to illustrate the tightness of these bounds. We also use these bounds to study important properties of the tail probability. Further, we apply these bounds for a large number of non-Gaussian input sources, and validate their performance via simulations. We have conducted our simulation study using importance sampling in order to improve its reliability and to effectively capture rare events. Our analytical study is based on extreme value theory, and therefore different from the approaches using traditional Markovian and large deviations techniques.

Enhancing system capacity is an important issue in wireless cellular networks. In this paper, we present a new channel sharing scheme to address this problem. Our basic idea is to allow channels to be shared between adjacent cells. We propose a fixed channel assignment scheme to maximize channel reuse efficiency while allowing channel sharing. An important feature of our sharing scheme is that channel management is localized between adjacent cells, and no global coordination or optimization is required thus simplifying implementation. We provide simulation results comparing our scheme with the fixed channel assignment scheme.

The problem of handoffs in cellular networks is compounded in a LEO (low Earth orbit) satellite-based cellular network due to the relative motion of the satellites themselves with respect to a stationary observer on Earth. Typically, the velocity of motion of mobile telephones can be ignored when compared to the very high velocity of the footprints of satellites. We exploit this property of the LEO satellite systems and propose a handoff scheme that results in a significant decrease in handoff dropping. For the same handoff dropping probability, our scheme has a significantly lower new call blocking probability than the conventional reservation scheme. We present an analytical approximation that is in very good accord with simulation results.

In this paper, we study P(/spl Qscr/>x), the tail of the steady-state queue length distribution at a high-speed multiplexer. In particular, we focus on the case when the aggregate traffic to the multiplexer can be characterized by a stationary Gaussian process. We provide two asymptotic upper bounds for the tail probability and an asymptotic result that emphasizes the importance of the dominant time scale and the maximum variance. One of our bounds is in a single-exponential form and can be used to calculate an upper bound to the asymptotic constant. However, we show that this bound, being of a single-exponential form, may not accurately capture the tail probability. Our asymptotic result on the importance of the maximum variance and our extensive numerical study on a known lower bound motivate the development of our second asymptotic upper bound. This bound is expressed in terms of the maximum variance of a Gaussian process, and enables the accurate estimation of the tail probability over a wide range of queue lengths. We apply our results to Gaussian as well as multiplexed non-Gaussian input sources, and validate their performance via simulations. Wherever possible, we have conducted our simulation study using importance sampling in order to improve its reliability and to effectively capture rare events. Our analytical study is based on extreme value theory, and therefore different from the approaches using traditional Markovian and large deviations techniques.

In this paper we develop a simple and accurate analytical technique to determine the loss probability at an access node to an asynchronous transfer mode (ATM) network. This is an important problem from the point of view of admission control and network design. The arrival processes we analyze are the Markov-modulated Poisson process (MMPP) and the Markov-modulated fluid (MMF) process. These arrival processes have been shown to model various traffic types, such as voice, video, and still images, that are expected to be transmitted by ATM networks. Our hybrid analytical technique combines results from large buffer theories and quasi-stationary approaches to analyze the loss probability of a finite-buffer queue being fed by Markov-modulated sources such as the MMPP and MMF. Our technique is shown to be valid for both heterogeneous and homogeneous sources. We also show that capacity allocation based on the popular effective-bandwidth scheme can lead to considerable under-utilization of the network and that allocating bandwidth based on our model can improve the utilization significantly. We provide numerical results for different types of traffic and validate our model via simulations.

In this paper we develop a novel mechanism for feedback based flow control in ATM networks. The underlying flow control mechanism is a class of back-pressure algorithms that ensure no data loss and operate based on simple 'stop' and 'start' signals. We present a methodology which allows us to specify design control parameters for a given set of performance objectives. It allows the real-time traffic (CBR, VBR) and the ABR traffic to effectively share the bandwidth and buffer space at each node. It is scalable with distance, link speed, and number of connections, hence it is suitable for both LAN and WAN environments. Also, it can operate with a small buffer size requirement, low management complexity, and low signalling overhead. Further, it is highly responsive to changes in available bandwidth, leading to virtually 100% utilization when ABR sources always have data to transfer. The numerical results show that the proposed algorithm achieves high utilization with low overall complexity and small buffer size requirements.

In ATM networks cell loss or channel errors can cause data to be dropped in the channel. When digital video is transmitted over these networks one must be able to reconstruct the missing data so that the impact of these errors is minimized. In this paper we describe a Bayesian approach to concealing these errors by post-processing the received data. In a previous paper (see IEEE Proc. Int. Conf. on Image Processing p.49-52, 1996), each frame in the sequence was modeled as a Markov random field, and maximum a posteriori estimates of the missing macroblocks were obtained. However, the maximum a posteriori estimate is not unique, and the algorithm is also computationally intensive. In this paper we demonstrate, that by using median filtering we arrive at a suboptimal estimate. This will allow real-time nearly optimal reconstruction of the missing data.

In this paper, we develop a simple analytical technique to determine P({Q>q}), the tail of the queue length distribution, at an ATM multiplexer. The ATM multiplexer is modeled as a fluid queue serving a large number of independent sources. Our method is based on the central limit theorem and the maximum variance approximation, and enables us to avoid the state explosion problem. The approach is quite general and not limited by a Markovian framework. We apply our analytical method to study the buffer behavior for various traffic sources such as multiplexed homogeneous and heterogeneous Markov modulated sources, sources that are correlated at multiple time scales, sources whose autocorrelation function exhibits heavy (sub-exponential) tail behavior, and sources generated from real MPEG-encoded video sequences.

We present a new scheme that addresses the call handoff problem in mobile cellular networks. Efficiently solving the handoff problem is important for guaranteeing quality of service (QoS) to already admitted calls in the network. Our scheme is based on a new concept called channel carrying: when a mobile user moves from one cell to another, under certain mobility conditions, the user is allowed to carry its current channel. We propose a new channel assignment scheme to ensure that this movement of channels will not lead to any extra co-channel interference or channel locking. In our scheme, the mobility of the channels relies entirely on localized information, and no global coordination is required. Therefore, the scheme is simple and easy to implement. We further develop a hybrid channel carrying scheme that allows us to maximize the performance under various constraints. We provide numerical results comparing our scheme with the traditional channel reservation techniques. We find that our scheme outperforms the reservation scheme over a broad range of traffic parameters.

We are developing a new graduate program at Purdue in Video and Image Systems Engineering (VISE). The project is comprised of three parts: a new curriculum centered around a degree option in VISE to be earned as part of the Masters or Ph.D. degrees; a state-of-the-art lecture/laboratory facility for instruction, laboratory experiments, and project and homework activities in VISE courses; and enhancement of existing courses and development of new courses in the VISE area.

In ATM networks cell loss causes data to be dropped in the channel. When digital video is transmitted over these networks one must be able to reconstruct the missing data so that the impact of these errors is minimized. In this paper we describe a Bayesian approach to conceal these errors. Assuming that the digital video has been encoded using the MPEG1 or MPEG2 compression scheme, each frame is modeled as a Markov random field. A maximum a posteriori estimate of the missing macroblocks and motion vectors is described based on the model.

In this paper we study the problem of scheduling real-time traffic in high-speed ATM networks. Scheduling can be performed at different points in the ATM network, such as, at the multiplexers and switches. In our model the arriving traffic cells are assumed to have weights associated with them which determine their importance measure (for example, cells belonging to one traffic class may have different weights than cells belonging to another traffic class). Further, a cell is said to have been lost if its deadline Is violated. We develop a simple procedure, S-OPT, to minimize the cell loss rate for single-class traffic. Using this procedure we develop an optimal algorithm, M-OPT, that minimizes the weighted loss rate at a network node. Finally, we provide a heuristic algorithm, M-HEUR, which significantly reduces the complexity of M-OPT and closely approximates its performance. In each case the scheduling decisions are based only on the current information in the queue. Using numerical results we show that our scheduling algorithms significantly outperform well known algorithms such as first-in-first-out (FIFO) and static priority (SP).

In this paper we develop a simple and accurate analytical technique to determine the loss probability at an access node to an ATM network. This is an important problem from the point of view of admission control and network design. The arrival processes we analyze are the Markov modulated Poisson processes (MMPP) and the Markov modulated fluid (MMF) processes which are important in modeling various traffic types, such as voice, video, and still images. Our hybrid analytical technique combines results from large buffer theories and quasi-stationary approaches to analyze the loss probability of a finite buffer queue. Our technique is shown to be valid even for heterogeneous sources. We also show that capacity allocation based on the popular effective bandwidth scheme can lead to considerable underutilization of the network, and that allocating bandwidth based on our model can improve the utilization significantly. We provide numerical results for different types of traffic and validate our model via simulations.

In this paper we describe two error-recovery approaches for MPEG encoded video over ATM networks. The first approach aims at reconstructing each lost pixel by spatial interpolation from the nearest undamaged pixels. The second approach recovers lost macroblocks by minimizing intersample variations within each block and across its boundaries. Moreover, a new technique for packing ATM cells with compressed data is also proposed.

Video traffic is expected to become increasingly important with the large scale deployment of broadband ISDN. In the literature, it suggested that smoothing variable bit rate (VBR) video traffic before transmitting it onto the network would help reduce the probability of packet loss. The authors show why deterministic smoothing at the source approximates the minimum achievable loss over the network end-to-end of all possible smoothing schemes. Furthermore, they develop a powerful yet simple analytical technique that can efficiently calculate the loss probability at any point in a network carrying video traffic. They validate the analytical results using traces of actual video segments. The results can be used for admission control and traffic management. They find that in the case of highly correlated traffic such as video, the way to control loss is to ensure that the fraction of time the arrival process exceeds the service process is small.>

An analytical approach is provided for determining the performance of a virtual circuit connection for data transmission in high speed asynchronous transfer mode (ATM) network buffers at wide area network (WAN) nodes. The analysis assumes that the network operates using the best effort delivery strategy and that the end-to-end virtual circuit is responsible for guaranteeing the integrity of the connection. As the normal Markovian assumptions do not apply, a concise exact solution is impossible to obtain. A hybrid model incorporating finite buffers at the nodes was developed to study the effect on the performance of both link errors and buffer overflow in conjunction with an end-to-end packet loss recovery scheme.>