eXplainable Artificial Intelligence (XAI) has garnered significant attention for enhancing transparency and trust in machine learning models. However, the scopes of most existing explanation techniques focus either on offering a holistic view of the explainee model (global explanation) or on individual instances (local explanation), while the middle ground, i.e., cohort-based explanation, is less explored. Cohort explanations offer insights into the explainee's behavior on a specific group or cohort of instances, enabling a deeper understanding of model decisions within a defined context. In this paper, we discuss the unique challenges and opportunities associated with measuring cohort explanations, define their desired properties, and create a generalized framework for generating cohort explanations based on supervised clustering.

A prevailing approach to explain time series models is to generate attribution in time domain input. A recent development in time series XAI is the concept of explanation spaces, where any model trained in the time domain can be interpreted with any existing XAI method in alternative domains, such as frequency or time-frequency domain. The prevailing approach is to present XAI attributions either in the time domain or in the domain where the attribution is most sparse. In this paper, we demonstrate that in certain cases, XAI methods can generate attributions that highlight fundamentally different features in the time and frequency domains that are not direct counterparts of one another. This observation suggests that both domains' attributions should be presented to achieve a more comprehensive interpretation. Thus it shows the necessity of multi-domain explanation. To quantify when such cases arise, we introduce the uncertainty principle (UP), originally developed in quantum mechanics and later studied in harmonic analysis and signal processing, to the XAI literature. This principle establishes a lower bound on how much a signal can be simultaneously localized in both the time and frequency domains. By leveraging this concept, we assess whether attributions in the time and frequency domains violate this bound, indicating that they emphasize distinct features. In other words, UP provides a sufficient condition that the time and frequency domain explanations do not match and, hence, should be both presented to the end user. We validate the effectiveness of this approach across various deep learning models, XAI methods, and a wide range of classification and forecasting datasets. The frequent occurrence of UP violations across various datasets and XAI methods highlights the limitations of existing approaches that focus solely on time-domain explanations. This underscores the need for multi-domain explanations as a new paradigm. The source code is available at https://github.com/shrezaei/TS-X-spaces

Human understandable explanation of deep learning models is essential for various critical and sensitive applications. Unlike image or tabular data where the importance of each input feature (for the classifier's decision) can be directly projected into the input, time series distinguishable features (e.g. dominant frequency) are often hard to manifest in time domain for a user to easily understand. Additionally, most explanation methods require a baseline value as an indication of the absence of any feature. However, the notion of lack of feature, which is often defined as black pixels for vision tasks or zero/mean values for tabular data, is not well-defined in time series. Despite the adoption of explainable AI methods (XAI) from tabular and vision domain into time series domain, these differences limit the application of these XAI methods in practice. In this paper, we propose a simple yet effective method that allows a model originally trained on the time domain to be interpreted in other explanation spaces using existing methods. We suggest five explanation spaces, each of which can potentially alleviate these issues in certain types of time series. Our method can be easily integrated into existing platforms without any changes to trained models or XAI methods. The source code is available at https://github.com/shrezaei/TS-X-spaces.

Abstract Recent developments in deep reinforcement learning have been very successful in learning complex, previously intractable problems. Sample efficiency and local optimality, however, remain significant challenges. To address these challenges, novelty-driven exploration strategies have emerged and shown promising potential. Unfortunately, no single algorithm outperforms all others in all tasks and most of them struggle with tasks with high-dimensional and complex observations. In this work, we propose Adventurer, a novelty-driven exploration algorithm that is based on Bidirectional Generative Adversarial Networks (BiGAN), where BiGAN is trained to estimate state novelty. Intuitively, a generator that has been trained on the distribution of visited states should only be able to generate a state coming from the distribution of visited states. As a result, novel states using the generator to reconstruct input states from certain latent representations would lead to larger reconstruction errors. We show that BiGAN performs well in estimating state novelty for complex observations. This novelty estimation method can be combined with intrinsic-reward-based exploration. Our empirical results show that Adventurer produces competitive results on a range of popular benchmark tasks, including continuous robotic manipulation tasks (e.g. Mujoco robotics) and high-dimensional image-based tasks (e.g. Atari games).

Abstract Synthetic data has been actively used for various machine learning-based tasks due to its benefits such as massive reproducibility and privacy enhancement compared to using the original data. The quality of the generated synthetic dataset crucially depends on the quality of the original data, and the latter is often corrupted by label noise. While there have been studies on feature noise, how label noise affects synthetic data generation is under-explored. In this paper, we evaluate the impact of the noisy label on synthetic data generation with a focus on tabular data. One challenge is how to evaluate the quality of synthetic data under label noise. To this end, we design comprehensive experiments to measure the impact of label noise on synthetic data generation in different aspects: synthetic data quality, data utility, and convergence for training synthesizers and machine learning models for downstream tasks. The empirical results cover wide aspects of synthetic data generation under label noise and they show quality and utility degrades with higher noise levels while there is no significant effect on the synthesizer convergence observed.

In SplitFed learning (SFL), a global model is split into two segments, where distributed clients train the first segment in a federated manner and a main server trains the other. Existing studies focus on algorithm development but ignore the important issue of incentives, without which self-interested clients may be unwilling to participate. We fill this gap by presenting a first incentive study in SFL. One challenge is that the design requires an understanding of how clients' participation affects the model performance. To this end, we provide a first convergence analysis for SFL considering partial client participation to guide the mechanism design. Another challenge is that monetary payment may not be viable for large distributed systems. To this end, we propose a model-versioning mechanism where the main server assigns different versions of models (of different qualities) to clients as incentives. The design is further complicated by clients' multi-dimensional private information. To this end, we design the model-versioning mechanism so that it decouples clients' decisions and admits a weakly dominant strategy at equilibrium. We prove that our mechanism is feasible, effective, and incentive compatible. Experimental results show that our mechanism greatly improves client participation and model accuracy compared to a benchmark.

Microgrids – decentralized electrical grids that can function both in conjunction with wide area macrogrids and without – are a powerful tool to address energy resiliency and climate change mitigation. Microgrid control , however, remains a challenge; their bespoke nature and the existence of multiple sources of uncertainty lead to a control problem that traditional grid modeling and control techniques are ill-suited to handle. We build a microgrid interface to simulate microgrids under uncertainty and devise off-policy reinforcement learning algorithms to control microgrids. Our algorithms, which incorporate domain randomization and random network distillation for exploration and computational efficiency, achieve performance better than model predictive control and rule based control benchmarks under battery model uncertainty on seven of ten tested scenarios. Our model code is available at https://github.com/ahalev/Microgrid-Control-Under-Uncertainty and our microgrid simulator is available at https://github.com/ahalev/python-microgrid .

Federated learning (FL) is decentralized machine learning framework that finds various applications in health, finance, and the internet of things. This paper studies the under-explored business competition in FL, where organizations are both collaborators in training a shared model and competitors in providing model-based services to a continuum of customers. We focus on an oligopoly case with three organizations. To understand how competition affects FL collaboration, we start with a benchmark case where organizations are not competitors, and show that they have an incentive to collaborate. However, in the presence of competition, organizations may prefer to train local models instead of collaborating via FL (even if FL incurs zero training costs). The reason is that FL intensifies price competition by improving organizations’ model performance to a similar level. To address this issue, we devise a model differentiation mechanism in which organizations adaptively adjust their model performance, enabling differentiated model-based services to customers. We prove that the adaptive mechanism converges in polynomial time and is incentive compatible. Perhaps surprisingly, numerical experiments on CIFAR-10 show that the mechanism can simultaneously improve the model performance, organizations’ revenues, and social welfare. The improvement is up to 22.31%, 14.42%, and 19.50%, respectively.

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.

Deep ensemble learning has been shown to improve accuracy by training multiple neural networks and averaging their outputs. Ensemble learning has also been suggested to defend against membership inference attacks that undermine privacy. In this paper, we empirically demonstrate a trade-off between these two goals, namely accuracy and privacy (in terms of membership inference attacks), in deep ensembles. Using a wide range of datasets and model architectures, we show that the effectiveness of membership inference attacks increases when ensembling improves accuracy. We analyze the impact of various factors in deep ensembles and demonstrate the root cause of the trade-off. Then, we evaluate common defenses against membership inference attacks based on regularization and differential privacy. We show that while these defenses can mitigate the effectiveness of membership inference attacks, they simultaneously degrade ensemble accuracy. We illustrate similar trade-off in more advanced and state-of-the-art ensembling techniques, such as snapshot ensembles and diversified ensemble networks. Finally, we propose a simple yet effective defense for deep ensembles to break the trade-off and, consequently, improve the accuracy and privacy, simultaneously.

We propose MASTAF, a Model-Agnostic Spatio-Temporal Attention Fusion network for few-shot video classification. MASTAF takes input from a general video spatial and temporal representation,e.g., using 2D CNN, 3D CNN, and Video Transformer. Then, to make the most of such representations, we use self- and cross-attention models to highlight the critical spatio-temporal region to increase the inter-class variations and decrease the intra-class variations. Last, MASTAF applies a lightweight fusion network and a nearest neighbor classifier to classify each query video. We demonstrate that MASTAF improves the state-of-the-art performance on three few-shot video classification benchmarks(UCF101, HMDB51, and Something-Something-V2), e.g., by up to 91.6%, 69.5%, and 60.7% for five-way one-shot video classification, respectively.

Federated Learning (FL) is a distributed machine learning paradigm where clients collaboratively train a model using their local datasets. While existing studies focus on FL algorithm development to tackle data heterogeneity across clients, the important issue of data quality (e.g., label noise) in FL is less explored. This paper aims to fill this gap by providing a quantitative study on the impact of label noise on FL. We derive an upper bound for the generalization error that is linear in the summation of clients' label noise levels. Then we conduct experiments on MNIST and CIFAR-10 datasets using various FL algorithms. Our empirical results show that the global model accuracy linearly decreases as the noise level increases, which is consistent with our theoretical analysis. We further find that label noise slows down the convergence of FL training, and the global model tends to overfit when the noise level is high.

As a privacy-preserving paradigm for training machine learning (ML) models, federated learning (FL) has received tremendous attention from both industry and academia. In a typical FL scenario, clients exhibit significant heterogeneity in terms of data distribution and hardware configurations. Thus, randomly sampling clients in each training round may not fully exploit the local updates from heterogeneous clients, resulting in lower model accuracy, slower convergence rate, degraded fairness, etc. To tackle the FL client heterogeneity problem, various client selection algorithms have been developed, showing promising performance improvement. In this article, we systematically present recent advances in the emerging field of FL client selection and its challenges and research opportunities. We hope to facilitate practitioners in choosing the most suitable client selection mechanisms for their applications, as well as inspire researchers and newcomers to better understand this exciting research topic.

Federated learning (FL) is a distributed model training paradigm that preserves clients’ data privacy. It has gained tremendous attention from both academia and industry. FL hyper-parameters (e.g., the number of selected clients and the number of training passes) significantly affect the training overhead in terms of computation time, transmission time, computation load, and transmission load. However, the current practice of manually selecting FL hyper-parameters imposes a heavy burden on FL practitioners because applications have different training preferences. In this paper, we propose, an automatic FL hyper-parameter tuning algorithm tailored to applications’ diverse system requirements in FL training. iteratively adjusts FL hyper-parameters during FL training and can be easily integrated into existing FL systems. Through extensive evaluations of for diverse applications and FL aggregation algorithms, we show that is lightweight and effective, achieving 8.48%-26.75% system overhead reduction compared to using fixed FL hyper-parameters. This paper assists FL practitioners in designing high-performance FL training solutions. The source code of is available at.

Network Function Virtualization (NFV), which decouples network functions from hardware and transforms them into Virtual Network Functions (VNFs), is a crucial technology for data center (DC) networks. A service function chain (SFC) is composed of an ordered set of VNFs and virtual links (VLs) connecting them. To optimize the resource allocation in DC networks, we need to efficiently map SFCs onto the physical network. Nevertheless, the dynamics and diversity of SFC requests in multi-datacenter (MDC) networks pose a significant challenge in embedding SFCs. To overcome this challenge, we design a two-stage graph convolutional network (GCN) assisted deep reinforcement learning (DRL) scheme. This framework aims to maximize the overall acceptance ratio of SFC requests while minimizing the total cost in an MDC network. In the first stage, we propose a GCN-based DRL algorithm as a coarse granularity solution to the SFC embedding problem from the macro perspective. This solution outlines a local observation scope (LOS) for each agent in the multi-agent system of the second stage, where all agents simultaneously handle SFC requests from their respective DCs using a multi-agent framework from the micro perspective. Numerical evaluations show that, compared to state-of-the-art methods, the proposed scheme improves the acceptance ratio by approximately 13% compared with the Kolin algorithm and 18% compared with the DQN algorithm and saves the cost by around 28% compared with the Kolin and the DQN.

Over an extended period, remote-sensing-based individual tree analysis has played a critical role in modern forest inventory and management research. The segmentation of individual trees from aerial point clouds usually depends on the characteristics of peak-like uplift on the crown surface; however, the performance inevitably decreases with increasing visibility of such features in point clouds, especially for high-density forests. Herein, we developed a novel hierarchical region-merging algorithm that first over-segmented the entire forest scene based on local density and then merged the over-segmented partitions into pairs through a stepwise optimal process to produce the final segmentation. In the region-merging method, a global merging cost was introduced to shift from local detection of crown features to use the overall compactness of forest point clouds. The experiments were conducted using unmanned aerial vehicle light detection and ranging (UAV-LiDAR) point clouds from three coniferous stands with different densities and a high-density coniferous and broad-leaved mixed stand. A total of 5510 field-measured trees in 36 plots were used to assess the accuracy of the proposed method. Our method achieved F-scores of 0.91, 0.88, 0.84, and 0.80 for low- (~700 stems/ha), medium- (~1000 stems/ha), and high-density (~2000 stems/ha) conifer stands and coniferous and broad-leaved mixed forests (~1800 stems/ha), respectively. Compared with the classical individual tree segmentation methods (marker-controlled watershed segmentation and point cloud region-growing algorithm), our method obtained comparable performance in low-density conifer stands and superior performance in the other stands. Furthermore, the region-merging algorithm could detect 10% more suppressed trees on average, which led to an apparent improvement in detection accuracy. The proposed algorithm provides a flexible segmentation framework that could be further improved by a different design that merges costs or applies multiscale segmentation with different stopping criteria.

Network traffic classification, the task of associating network traffic with their generating application protocols or applications, is valuable for the control, allocation, and management of resources in today’s TCP/IP networks. In this paper, we propose Ulfar, a multi-scale feature attention approach to network traffic classification, which uses convolutional neural networks (CNN) as the building block of the deep packet analysis model. In Ulfar, we take only one packet per flow for network traffic classification. Ulfar is based on the key insight that format-related bytes appear at fixed offsets or in a specific pattern in the IP packet, and these format-related bytes are important for accurate network traffic classification. Our neural network model can automatically recover the format-related bytes by building high-level, multi-scale${n}$-gram features from raw byte sequences. In addition, at the representation learning side, we try to understand what patterns and signatures our neural network model learns from network traffic. We evaluate Ulfar using two publicly available datasets, and our experimental results show that Ulfar can conduct accurate network traffic classification. Also, we compare the results of Ulfar with four state-of-the-art approaches, and find that Ulfar has the ability to classify network traffic more accurately.

Time series smoothing is essential for time series analysis and forecasting. It helps to identify trends and patterns of time series. However, the presence of irregular perturbations disrupt the time series smoothness and distort information. The goal of time series smoothing is to remove these perturbations while preserving as much information as possible. Existing smoothing algorithms have complete freedom to make corrections to the data points which often over smooth the time series and lose information. None of them considers constraining data corrections to the best of our knowledge. Moreover, most existing methods either do not smooth in real-time or their parameters need to be hand-tuned in different scenarios. To improve smoothing performance while considering data correction constraints, we propose a $\mathbf{C}$onstrained reinforcement learning-based $\mathbf{T}$ime $\mathbf{S}$eries $\mathbf{S}$moothing method, or CTS$^2$. Specifically, we first formulate the smoothing problem as a Constrained Markov Decision Process (CMDP). We then incorporate data correction constraints to restrict the amount of correction at each point. Finally, we learn a policy network with a linear projection layer to smooth the time series. The linear projection layer ensures that all data corrections satisfy the data correction constraints. We evaluate CTS$^2$ on both synthetic and real-world time series datasets; our results show that CTS$^2$ successfully smooths time series in real-time, satisfies all the correction constraints, and works efficiently in a variety of scenarios.

As mobile networks proliferate, we are experiencing a strong diversification of services, which requires greater flexibility from the existing network. Network slicing is proposed as a promising solution for resource utilization in 5G and future networks to address this dire need. In network slicing, dynamic resource orchestration and network slice management are crucial for maximizing resource utilization. Unfortunately, this process is too complex for traditional approaches to be effective due to a lack of accurate models and dynamic hidden structures. We formulate the problem as a Constrained Markov Decision Process (CMDP) without knowing models and hidden structures. Additionally, we propose to solve the problem using CLARA, a Constrained reinforcement LeArning based Resource Allocation algorithm. In particular, we analyze cumulative and instantaneous constraints using adaptive interior-point policy optimization and projection layer, respectively. Evaluations show that CLARA clearly outperforms baselines in resource allocation with service demand guarantees.

Recent studies propose membership inference (MI) attacks on deep models, where the goal is to infer if a sample has been used in the training process. Despite their apparent success, these studies only report accuracy, precision, and recall of the positive class (member class). Hence, the performance of these attacks have not been clearly reported on negative class (non-member class). In this paper, we show that the way the MI attack performance has been reported is often misleading because they suffer from high false positive rate or false alarm rate (FAR) that has not been reported. FAR shows how often the attack model mislabel non-training samples (non-member) as training (member) ones. The high FAR makes MI attacks fundamentally impractical, which is particularly more significant for tasks such as membership inference where the majority of samples in reality belong to the negative (non-training) class. Moreover, we show that the current MI attack models can only identify the membership of misclassified samples with mediocre accuracy at best, which only constitute a very small portion of training samples.We analyze several new features that have not been comprehensively explored for membership inference before, including distance to the decision boundary and gradient norms, and conclude that deep models’ responses are mostly similar among train and non-train samples. We conduct several experiments on image classification tasks, including MNIST, CIFAR-10, CIFAR-100, and ImageNet, using various model architecture, including LeNet, AlexNet, ResNet, etc. We show that the current state-of-the-art MI attacks cannot achieve high accuracy and low FAR at the same time, even when the attacker is given several advantages. The source code is available at https://github.com/shrezaei/MI-Attack.

Reinforcement Learning (RL) algorithms have had tremendous success in simulated domains. These algorithms, however, often cannot be directly applied to physical systems, especially in cases where there are constraints to satisfy (e.g. to ensure safety or limit resource consumption). In standard RL, the agent is incentivized to explore any policy with the sole goal of maximizing reward; in the real world, however, ensuring satisfaction of certain constraints in the process is also necessary and essential. In this article, we overview existing approaches addressing constraints in model-free reinforcement learning. We model the problem of learning with constraints as a Constrained Markov Decision Process and consider two main types of constraints: cumulative and instantaneous. We summarize existing approaches and discuss their pros and cons. To evaluate policy performance under constraints, we introduce a set of standard benchmarks and metrics. We also summarize limitations of current methods and present open questions for future research.

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.

With the proliferation of mobile networks, we face strong diversification of services, demanding the network to be more flexible. To satisfy this dire need, network slicing is embraced as a promising solution for resource utilization in 5G and future networks. However, this process is complicated that the traditional approaches cannot effectively perform resource orchestration due to the lack of accurate models and the existence of dynamic hidden structures. We formulate the resource allocation problem as a Constrained Markov Decision Process and solve it using constrained reinforcement learning. Specifically, we use the adaptive interior-point policy optimization and projection layers to handle cumulative and instantaneous constraints. Our evaluations show that our method is effective in resource allocation and outperforms baselines.

Nowadays, there is an ever-increasing interests in federated learning, which allows end devices to collaboratively train a global machine learning model in a decentralized paradigm without sharing individual data. Despite the advantages of low communication cost and preserving data privacy, federated learning is also facing with new challenges to address. Practically, end devices will consider the resources cost and willingness caused by machine learning model training when they are invited to participate a federated learning task. So, how to assign the preferable tasks to the devices with high willingness has to be considered. Besides, the end devices have the property of high mobility, which means the time of devices localizing within the network is limited. Therefore, to reduce the task execution time is necessary. To address these problems, we first analyze and formulate the latency minimization problem for multitask federated learning in a multiaccess edge computing (MEC) network scenario. Then, we model the corresponding problem as a matching game to find the optimal task assignment solutions. Moreover, considering the large-scale Internet-of-Things (IoT) scenario, it is almost impossible for two sides to know the details of every individual of the other side so that the complete preference list (CPL) cannot be built in reality. Therefore, we propose an algorithm for large-scale matching with the incomplete preference list to address the problem. Finally, we conduct the numerical simulation in various cases to demonstrate the effectiveness of our proposed method. The results show that our approach can achieve similar performance with the CPL case.

In this paper, we study reinforcement learning (RL) algorithms to solve real-world decision problems with the objective of maximizing the long-term reward as well as satisfying cumulative constraints. We propose a novel first-order policy optimization method, Interior-point Policy Optimization (IPO), which augments the objective with logarithmic barrier functions, inspired by the interior-point method. Our proposed method is easy to implement with performance guarantees and can handle general types of cumulative multi-constraint settings. We conduct extensive evaluations to compare our approach with state-of-the-art baselines. Our algorithm outperforms the baseline algorithms, in terms of reward maximization and constraint satisfaction.

Traffic classification has various applications in today's Internet, from resource allocation, billing and QoS purposes in ISPs to firewall and malware detection in clients. Classical machine learning algorithms and deep learning models have been widely used to solve the traffic classification task. However, training such models requires a large amount of labeled data. Labeling data is often the most difficult and time-consuming process in building a classifier. To solve this challenge, we reformulate the traffic classification into a multi-task learning framework where bandwidth requirement and duration of a flow are predicted along with the traffic class. The motivation of this approach is twofold: First, the bandwidth requirement and duration are useful in many applications, including routing, resource allocation, and QoS provisioning. Second, these two values can be obtained from each flow easily without the need for human labeling or capturing flows in a controlled and isolated environment. We show that with a large amount of easily obtainable data samples for bandwidth and duration prediction tasks, and only a few data samples for the traffic classification task, one can achieve high accuracy. Therefore, our proposed multi-task learning framework obviates the need for a large labeled traffic dataset. We conduct two experiments with ISCX and QUIC public datasets and show the efficacy of our approach.

With the proliferation of mobile networks, we face strong diversification of services, demanding the current network to embed more flexibility. To satisfy this daring need, network slicing is embraced as a promising solution for resource utilization, in 5G and future networks. In network slicing, dynamic resource orchestration and network slice management are critical for resource efficiency. However, it is highly complicated such that the traditional approaches can not effectively perform resource orchestration due to the lack of accurate models and hidden problem structures. To address this challenge, we propose a constrained reinforcement learning based approach for network slicing. We formulate the resource allocation problem as a Constrained Markov Decision Process (CMDP) and solve it using constrained reinforcement learning algorithms. Specifically, we use the adaptive interior-point policy optimization and policy safety layer methods to deal with cumulative and instantaneous constraints. Our evaluations show that our method is effective in resource allocation with service demand guarantees and significantly outperforms baselines.

Cellular network configuration plays a critical role n network performance. In current practice, network configuration depends heavily on field experience of engineers and often remains static for a long period of time. This practice is far from optimal. To address this limitation, online-learning-based approaches have great potentials to automate and optimize network configuration. Learning-based approaches face the challenges of learning a highly complex function for each base station and balancing the fundamental exploration-exploitation tradeoff while minimizing the exploration cost. Fortunately, in cellular networks, base stations (BSs) often have similarities even though they are not identical. To leverage such similarities, we propose kernel-based multi-BS contextual bandit algorithm based on multi-task learning. In the algorithm, we leverage the similarity among different BSs defined by conditional kernel embedding. We present theoretical analysis of the proposed algorithm in terms of regret and multi-task-learning efficiency. We evaluate the effectiveness of our algorithm based on a simulator built by real traces.

Network Function Virtualization (NFV) is one of the key drivers of 5G systems, which involves the virtualization of the Evolved Packet Core (EPC) and the 5G Core. This entails deploying virtual instances of core network functions in Cloud Networks (CNs), resulting in a virtual EPC (vEPC)/5G Core network. NFV resource allocation is a popular research topic in 5G systems, and a distributed solution based on the interdependencies between all the important entities is very crucial. Accordingly, in this paper, we propose a three-sided matching based framework for virtual resource allocation in next-generation networks. We utilize the Restricted Three-sided Matching with Size and Cyclic preference (R-TMSC) problem to model the relationships between Tracking Areas (TAs) (Base Stations (BSs) organized together in groups), CNs and Virtual Network Function (VNF) instances in a vEPC/5G Core network. The simulation results clearly demonstrate the superior performance of the proposed framework in terms of the data rates provided by the CNs and user satisfaction, compared to a centralized random allocation approach.

In this paper, we propose and study opportunistic contextual bandits - a special case of contextual bandits where the exploration cost varies under different environmental conditions, such as network load or return variation in recommendations. When the exploration cost is low, so is the actual regret of pulling a sub-optimal arm (e.g., trying a suboptimal recommendation). Therefore, intuitively, we could explore more when the exploration cost is relatively low and exploit more when the exploration cost is relatively high. Inspired by this intuition, for opportunistic contextual bandits with Linear payoffs, we propose an Adaptive Upper-Confidence-Bound algorithm (AdaLinUCB) to adaptively balance the exploration-exploitation trade-off for opportunistic learning. We prove that AdaLinUCB achieves O((log T)^2) problem-dependent regret upper bound, which has a smaller coefficient than that of the traditional LinUCB algorithm. Moreover, based on both synthetic and real-world dataset, we show that AdaLinUCB significantly outperforms other contextual bandit algorithms, under large exploration cost fluctuations.

Cellular network performance depends heavily on the configuration of its network parameters. Current practice of parameter configuration relies largely on expert experience, which is often suboptimal, time-consuming, and error-prone. Therefore, it is desirable to automate this process to improve the accuracy and efficiency via learning-based approaches. However, such approaches need to address several challenges in real operational networks: the lack of diverse historical data, a limited amount of experiment budget set by network operators, and highly complex and unknown network performance functions. To address those challenges, we propose a collaborative learning approach to leverage data from different cells to boost the learning efficiency and to improve network performance. Specifically, we formulate the problem as a transferable contextual bandit problem, and prove that by transfer learning, one could significantly reduce the regret bound. Based on the theoretical result, we further develop a practical algorithm that decomposes a cell's policy into a common homogeneous policy learned using all cells' data and a cell-specific policy that captures each individual cell's heterogeneous behavior. We evaluate our proposed algorithm via a simulator constructed using real network data and demonstrates faster convergence compared to baselines. More importantly, a live field test is also conducted on a real metropolitan cellular network consisting 1700+ cells to optimize five parameters for two weeks. Our proposed algorithm shows a significant performance improvement of 20%.

Complex software systems often provide a large number of parameters so that users can configure them for their specific application scenarios. However, configuration tuning requires a deep understanding of the software system, far beyond the abilities of typical system users. To address this issue, many existing approaches focus on exploring and learning good performance estimation models. The accuracy of such models often suffers when the number of available samples is small, a thorny challenge under a given tuning-time constraint. By contrast, we hypothesize that good configurations often share certain hidden structures. Therefore, instead of trying to improve the performance estimation of a given configuration, we focus on capturing the hidden structures of good configurations and utilizing such learned structure to generate potentially better configurations. We propose ACTGAN to achieve this goal. We have implemented and evaluated ACTGAN using 17 workloads with eight different software systems. Experimental results show that ACTGAN outperforms default configurations by 76.22% on average, and six state-of-the-art configuration tuning algorithms by 6.58%-64.56%. Furthermore, the ACTGAN-generated configurations are often better than those used in training and show certain features consisting with domain knowledge, both of which supports our hypothesis.

Big data analytics frameworks (BDAFs) have been widely used for data processing applications. These frameworks provide a large number of configuration parameters to users, which leads to a tuning issue that overwhelms users. To address this issue, many automatic tuning approaches have been proposed. However, it remains a critical challenge to generate enough samples in a high-dimensional parameter space within a time constraint. In this paper, we present AutoTune-an automatic parameter tuning system that aims to optimize application execution time on BDAFs. AutoTune first constructs a smaller-scale testbed from the production system so that it can generate more samples, and thus train a better prediction model, under a given time constraint. Furthermore, the AutoTune algorithm produces a set of samples that can provide a wide coverage over the high-dimensional parameter space, and searches for more promising configurations using the trained prediction model. AutoTune is implemented and evaluated using the Spark framework and HiBench benchmark deployed on a public cloud. Extensive experimental results illustrate that AutoTune improves on default configurations by 63.70% on average, and on the five state-of-the-art tuning algorithms by 6%-23%.

Vehicular cloud computing (VCC) is proposed to effectively utilize and share the computing and storage resources on vehicles. However, due to the mobility of vehicles, the network topology, the wireless channel states and the available computing resources vary rapidly and are difficult to predict. In this work, we develop a learning-based task offloading framework using the multi-armed bandit (MAB) theory, which enables vehicles to learn the potential task offloading performance of its neighboring vehicles with excessive computing resources, namely service vehicles (SeVs), and minimizes the average offloading delay. We propose an adaptive volatile upper confidence bound (AVUCB) algorithm and augment it with load-awareness and occurrence-awareness, by redesigning the utility function of the classic MAB algorithms. The proposed AVUCB algorithm can effectively adapt to the dynamic vehicular environment, balance the tradeoff between exploration and exploitation in the learning process, and converge fast to the optimal SeV with theoretical performance guarantee. Simulations under both synthetic scenario and a realistic highway scenario are carried out, showing that the proposed algorithm achieves close-to- optimal delay performance.

In this paper, we propose and study opportunistic bandits - a new variant of bandits where the regret of pulling a suboptimal arm varies under different environmental conditions, such as network load or produce price. When the load/price is low, so is the cost/regret of pulling a suboptimal arm (e.g., trying a suboptimal network configuration). Therefore, intuitively, we could explore more when the load/price is low and exploit more when the load/price is high. Inspired by this intuition, we propose an Adaptive Upper-Confidence-Bound (AdaUCB) algorithm to adaptively balance the exploration-exploitation tradeoff for opportunistic bandits. We prove that AdaUCB achieves O(log T) regret with a smaller coefficient than the traditional UCB algorithm. Furthermore, AdaUCB achieves O(1) regret with respect to T if the exploration cost is zero when the load level is below a certain threshold. Last, based on both synthetic data and real-world traces, experimental results show that AdaUCB significantly outperforms other bandit algorithms, such as UCB and TS (Thompson Sampling), under large load/price fluctuations.

Distributed message systems (DMSs) serve as the communication backbone for many real-time streaming data processing applications. To support the vast diversity of such applications, DMSs provide a large number of parameters to configure. However, It overwhelms for most users to configure these parameters well for better performance. Although many automatic configuration approaches have been proposed to address this issue, critical challenges still remain: 1) to train a better and robust performance prediction model using a limited number of samples, and 2) to search for a high-dimensional parameter space efficiently within a time constraint. In this paper, we propose AutoConfig -- an automatic configuration system that can optimize producer-side throughput on DMSs. AutoConfig constructs a novel comparison-based model (CBM) that is more robust that the prediction-based model (PBM) used by previous learning-based approaches. Furthermore, AutoConfig uses a weighted Latin hypercube sampling (wLHS) approach to select a set of samples that can provide a better coverage over the high-dimensional parameter space. wLHS allows AutoConfig to search for more promising configurations using the trained CBM. We have implemented AutoConfig on the Kafka platform, and evaluated it using eight different testing scenarios deployed on a public cloud. Experimental results show that our CBM can obtain better results than that of PBM under the same random forests based model. Furthermore, AutoConfig outperforms default configurations by 215.40% on average, and five state-of-the-art configuration algorithms by 7.21%-64.56%.

Cellular network configuration is critical for network performance. Current practice is mostly based on field experience and manual adjustment. The process is labor-intensive, error-prone, and far from optimal. To automate and optimize cellular network configuration, in this paper, we propose an online-learning-based joint-optimization approach that addresses a few specific challenges: limited data availability, convoluted sample data, highly complex optimization due to interactions among neighboring cells, and the need to adapt to network dynamics. In our approach, to learn an appropriate utility function for a cell, we develop a neural-network-based model that addresses the convoluted sample data issue and achieves good accuracy based on data aggregation. Based on the utility function learned, we formulate a global network configuration optimization problem. To solve this high-dimensional nonconcave maximization problem, we design a Gibbs-sampling-based algorithm that converges to an optimal solution when a technical parameter is small enough. Furthermore, we design an online scheme that updates the learned utility function and solves the corresponding maximization problem efficiently to adapt to network dynamics. To illustrate the idea, we use the case study of pilot power configuration. Numerical results illustrate the effectiveness of the proposed approach.

Cellular network configuration is critical for network performance. Current practice is labor-intensive, error-prone, and far from optimal. To automate efficient cellular network configuration, in this work, we propose an online-learning-based joint-optimization approach that addresses a few specific challenges: limited data availability, convoluted sample data, highly complex optimization due to interactions among neighboring cells, and the need to adapt to network dynamics. In our approach, to learn an appropriate utility function for a cell, we develop a neural-network-based model that addresses the convoluted sample data issue and achieves good accuracy based on data aggregation. Based on the utility function learned, we formulate a global network configuration optimization problem. To solve this high-dimensional non-concave maximization problem, we design a Gibbs-sampling-based algorithm that converges to an optimal solution when a technical parameter is small enough. Furthermore, we design an online scheme that updates the learned utility function and solves the corresponding maximization problem efficiently to adapt to network dynamics. To illustrate the idea, we use the case study of pilot power configuration. Numerical results illustrate the effectiveness of the proposed approach.

Crowdsensing systems collect large-scale sensor data from mobile devices to provide a wide-area view of phenomena including traffic, noise and air pollution. Because such data often exhibits sparse structure, it is natural to apply compressive sensing (CS) for data sampling and recovery. However in practice, crowd participants are often distributed highly unevenly across the sensing area, and thus the numbers of observations collected over different areas may vary wildly - an issue we call density disparity. Density disparity leads to inaccuracy in low density areas, and potentially undermines the recovery performance if conventional compressive sensing is applied directly, which equally treats data from areas of different density.

360-degree video is on the cusp of going mainstream. Such videos have a large size (4-5⌉ the size of a regular one). Since each viewer has to wear Head-Mounted Display (HMD), screen sharing is impossible when a group is watching the same content. Multiple parallel video-streams will be required to serve a group of viewers along the last mile (think of a family or a group of friends watching Super Bowl in their HMDs). This would end up quickly choking the entire network. In this paper, we present a scheme to optimize the network bandwidth using motion-prediction-based multicast to serve concurrent viewers. Based on empirical evaluation of more than 150 viewers watching our pool of sixteen 360-degree videos, we observe that most viewers follow similar motion patterns when watching the same video. We present a data- driven scheme for temporal prediction of viewer motion from previous states, and hence optimize the multicast bandwidth consumption by sending only the portion likely to be watched by a group of viewers. Our evaluations with real viewer motion traces show a bandwidth saving of over 50%, compared to full frame video multicast, and significant bandwidth reduction compared to unicast.

Driven by the desire for a better user experience and enabled by improved data storage and processing, much of the recent work has studied user experience prediction in cellular networks. In this paper, moving beyond the prediction-only approach, we propose a data-driven resource allocation framework that uses data-generated prediction models to explicitly guide resource allocation for user experience improvement. In a closed-loop fashion, it further leverages and verifies the causal relation that often exists between certain feature values (e.g., bandwidth) and user experience in computer networks. As a case study, we consider how to reduce the number of user complaints in cellular networks. Our approach consists of three components: we train a logistic regression classifier to predict user experience, utilize the trained likelihood as the objective function to allocate network resource, and then evaluate user experience with allocated resource to (in)validate and adjust the original model. We design a DualHet algorithm to tackle the problem of multi-dimensional resource optimization with heterogeneous users. Numerical simulations based on both synthetic and real network data sets demonstrate the effectiveness of the proposed algorithms. In particular, the simulations based on real data demonstrate up to $2\times $ performance improvement compared with the baseline algorithm.

Demand proportional resource provisioning schemes have been proposed to achieve datacenter energy efficiency, where servers are turned on/off according to the load of requests. Most existing schemes focus on delay sensitive jobs (SENs) only. However, in datacenters, there exist a vast amount of delay-tolerant jobs (TOLs), such as background/maintenance jobs. Thus, we study joint SEN and TOL resource provisioning in this paper, with a focus on TOLs. We consider traffic dynamics of SENs and TOLs in different time scales, and electricity price temporal dynamics and location diversity. Our goal is to minimize total costs, while guaranteeing QoS for SENs and achieving a desirable delay performance for TOLs. Specifically, we propose a joint server provisioning, SEN load dispatching, TOL load shifting, and SEN/TOL capacity allocation scheme, which leverages TOL queue information and does not assume any system statistical information. We also design other benchmark schemes that leverage different system information. Both analytical results and extensive simulation results show the efficiency of the proposed scheme, named OrgQ, in reducing total costs and TOL queue delay.

In online service systems, the delay experienced by users from service request to service completion is one of the most critical performance metrics. To improve user delay experience, recent industrial practices suggest a modern system design mechanism: proactive serving, where the service system predicts future user requests and allocates its capacity to serve these upcoming requests proactively. This approach complements the conventional mechanism of capability boosting. In this paper, we propose queuing models for online service systems with proactive serving capability and characterize the user delay reduction by proactive serving. In particular, we show that proactive serving decreases average delay exponentially (as a function of the prediction window size) in the cases where service time follows light-tailed distributions. Furthermore, the exponential decrease in user delay is robust against prediction errors (in terms of miss detection and false alarm) and user demand fluctuation. Compared with the conventional mechanism of capability boosting, proactive serving is more effective in decreasing delay when the system is in the light-load regime. Our trace-driven evaluations demonstrate the practical power of proactive serving: for example, for the data trace of light-tailed YouTube videos, the average user delay decreases by 50% when the system predicts 60 s ahead. Our results provide, from a queuing-theoretical perspective, justifications for the practical application of proactive serving in online service systems.

Enabled by the rapid development of virtual reality hardware and software, 360-degree video content has proliferated. From the network perspective, 360-degree video transmission imposes significant challenges because it consumes 4 6χ the bandwidth of a regular video with the same resolution. To address these challenges, in this paper, we propose a motion-prediction-based transmission mechanism that matches network video transmission to viewer needs. Ideally, if viewer motion is perfectly known in advance, we could reduce bandwidth consumption by 80%. Practically, however, to guarantee the quality of viewing experience, we have to address the random nature of viewer motion. Based on our experimental study of viewer motion (comprising 16 video clips and over 150 subjects), we found the viewer motion can be well predicted in 100~500ms. We propose a machine learning mechanism that predicts not only viewer motion but also prediction deviation itself. The latter is important because it provides valuable input on the amount of redundancy to be transmitted. Based on such predictions, we propose a targeted transmission mechanism that minimizes overall bandwidth consumption while providing probabilistic performance guarantees. Real-data-based evaluations show that the proposed scheme significantly reduces bandwidth consumption while minimizing performance degradation, typically a 45% bandwidth reduction with less than 0.1% failure ratio.

360-degree video transmission consumes 4∼6× the bandwidth of a regular video, and thus imposes significant challenges to networks. To address this challenge, in this paper, we propose a motion-prediction-based transmission mechanism that matches network video transmission to viewer needs. Ideally, if viewer motion is perfectly known in advance, we could reduce bandwidth consumption by 80%. Practically, however, we have to address the random nature of viewer motion, in order to guarantee the quality of the viewing experience. Based on our experimental study of viewer motion (comprising 16 video clips and over 150 subjects), we propose a machine learning mechanism that predicts viewer motion. Based on such predictions, we propose a partial-content-transmission mechanism that reduces the overall bandwidth consumption while providing probabilistic performance guarantees. Real-trace-based evaluations show that the proposed scheme significantly reduces bandwidth consumption with negligible performance degradation. For example, given a failure ratio of 0.1%, we can reduce bandwidth consumption by more than 40%.

Machine learning methods have been widely used in modeling and predicting network user experience. In this paper, moving beyond user experience prediction, we propose a closed-loop approach that uses data-generated prediction models to explicitly guide resource allocation for user experience improvement. The closed-loop approach leverages and verifies the causal relation that often exists between certain feature values (e.g., bandwidth) and user experience in computer networks. The approach consists of three components: we train a neural network classifier to predict user experience, utilize the trained neural network classifier as the objective function to allocate network resource, and then evaluate user experience with allocated resource to (in)validate and adjust the original model. Specifically, we propose a dual decomposition algorithm to solve the neural network-based resource optimization problem, which is complex and non-convex. We further develop an iterative mechanism for classifier optimization. Numerical results show that the dual algorithm reduces the expected number of unsatisfied users by up to 2x compared with the baseline, and the optimized classifier further improves the performance by 50%.

In this paper, we propose a Double Thompson Sampling (D-TS) algorithm for dueling bandit problems. As its name suggests, D-TS selects both the first and the second candidates according to Thompson Sampling. Specifically, D-TS maintains a posterior distribution for the preference matrix, and chooses the pair of arms for comparison according to two sets of samples independently drawn from the posterior distribution. This simple algorithm applies to general Copeland dueling bandits, including Condorcet dueling bandits as its special case. For general Copeland dueling bandits, we show that D-TS achieves $O(K^2 \log T)$ regret. Moreover, using a back substitution argument, we refine the regret to $O(K \log T + K^2 \log \log T)$ in Condorcet dueling bandits and many practical Copeland dueling bandits. In addition, we propose an enhancement of D-TS, referred to as D-TS+, that reduces the regret by carefully breaking ties. Experiments based on both synthetic and real-world data demonstrate that D-TS and D-TS$^+$ significantly improve the overall performance, in terms of regret and robustness.

Mobile Virtual Network Operators (MVNOs) serve their customers by leasing resource from physical Mobile Network Operators (MNOs). Guaranteeing service quality by connecting customers to appropriate MNOs based on their performance is important for MVNOs, but obtaining accurate statistics of performance for all MNOs is costly. In this paper, we study the scheduling problem with QoS constraints for MVNOs without a priori knowledge on the system statistics such as traffic and service quality. We propose a Learning-Aided Scheduling (LSchd) algorithm based on Lyapunov optimization approaches. We show that LSchd achieves near-optimal network utility subject to average QoS constraints. Further, we propose a Dual-Learning-Aided Scheduling (DSchd) algorithm to accelerate the convergence speed. The proposed algorithms are evaluated by simulations based on real network traces. The simulation results show that even when the system statistics are non-stationary, the proposed algorithms achieve near-optimal utilities and the DSchd algorithm quickly approaches the near-optimal performance.

Existing channel-aware scheduling work has mainly focused on scheduling in small timescales, that is, tens to hundreds of seconds. We propose to use long-term user profiles to provide useful statistical information on future network conditions in large timescales. We design scheduling algorithms based on Markov decision theory. We collect and use a large set of real-life traces from the general public. Extensive trace-driven evaluations show that many real mobile users can benefit from our framework. In addition, we compare our framework against state-of-the-art algorithms and observe significant performance differences because the existing algorithms were not designed for the large timescale scenario.

Motivated by the increasing popularity of learning and predicting human user behavior in communication and computing systems, in this paper, we investigate the fundamental benefit of predictive scheduling, i.e., predicting and pre-serving arrivals, in controlled queueing systems. Based on a lookahead-window prediction model, we first establish a novel queue-equivalence between the predictive queueing system with a fully efficient scheduling scheme and an equivalent queueing system without prediction. This result allows us to analytically demonstrate that predictive scheduling necessarily improves system delay performance and drives it to zero with increasing prediction power. It also enables us to exactly determine the required prediction power for different systems and study its impact on tail delay. We then propose the Predictive Backpressure (PBP) algorithm for achieving optimal utility performance in such predictive systems. PBP efficiently incorporates prediction into stochastic system control and avoids the great complication due to the exponential state space growth in the prediction window size. We show that PBP achieves a utility performance that is within O(ε) of the optimal, for any ε > 0, while guaranteeing that the system delay distribution is a shifted-to-the-left version of that under the original Backpressure algorithm. Hence, the average delay under PBP is strictly better than that under Backpressure, and vanishes with increasing prediction window size. This implies that the resulting utility-delay tradeoff with predictive scheduling can beat the known optimal [O(ε),O(log(1/ε))] tradeoff for systems without prediction. We also develop the Predictable-Only PBP (POPBP) algorithm and show that it effectively reduces packet delay in systems where traffic can only be predicted but not pre-served.

Although cellular networks can be provisioned according to the peak demand, they usually experience large fluctuations in both channel conditions and traffic load level. Scheduling with both channel and load awareness allows us to exploit the delay tolerance of data traffic to alleviate network congestion, and thus reduce the peak. However, solving the optimal scheduling problem leads to a large-scale Markov decision process (MDP) with extremely high complexity. In this paper, we propose a scalable and distributed approach to this problem, called Coordinated Scheduling (CoSchd). CoSchd decomposes the large-scale MDP problem into many individual MDP problems, each of which can be solved independently by each user under a limited amount of coordination signals from the base station (BS). We show that CoSchd is close to optimal when the number of users becomes large. Furthermore, we propose an approximation of CoSchd that iteratively updates the scheduling policy based on online measurements. Simulation results demonstrate that exploiting channel and load awareness with CoSchd can effectively alleviate cellular network congestion.

Opportunistic scheduling of delay-tolerant traffic has been shown to substantially improve spectrum efficiency. To encourage users to adopt delay-tolerant scheduling for capacity -improvement, it is critical to provide guarantees in terms of completion time. In this paper, we study application-level scheduling with deadline constraints, where the deadline is pre-specified by users/applications and is associated with a deadline violation probability. To address the exponentially-high complexity due to temporally-varying channel conditions and deadline constraints, we develop a novel asymptotic approach that exploits the largeness of the network to our advantage. Specifically, we identify a lower bound on the deadline violation probability, and propose simple policies that achieve the lower bound in the large-system regime. The results in this paper thus provide a rigorous analytical framework to develop and analyze policies for application-level scheduling under very general settings of channel models and deadline requirements. Further, based on the asymptotic approach , we propose the notion of Application-Level Effective Capacity region, i.e., the throughput region that can be supported subject to deadline constraints, which allows us to quantify the potential gain of application-level scheduling. Simulation results show that application-level scheduling can improve the system capacity significantly while guaranteeing the deadline constraints.

Mobile crowdsourcing is a powerful tool for collecting data of various types. The primary bottleneck in such systems is the high burden placed on the user who must manually collect sensor data or respond in-situ to simple queries (e.g., experience sampling studies). In this work, we present Compressive CrowdSensing (CCS) -- a framework that enables compressive sensing techniques to be applied to mobile crowdsourcing scenarios. CCS enables each user to provide significantly reduced amounts of manually collected data, while still maintaining acceptable levels of overall accuracy for the target crowd-based system. Naïve applications of compressive sensing do not work well for common types of crowdsourcing data (e.g., user survey responses) because the necessary correlations that are exploited by a sparsifying base are hidden and non-trivial to identify. CCS comprises a series of novel techniques that enable such challenges to be overcome. We evaluate CCS with four representative large-scale datasets and find that it is able to outperform standard uses of compressive sensing, as well as conventional approaches to lowering the quantity of user data needed by crowd systems.

Compressive Sensing is a technique that can help reduce the sampling rate of sensing tasks. In mobile crowdsensing applications or wireless sensor networks, the resource burden of collecting samples is often a major concern. Therefore, compressive sensing is a promising approach in such scenarios. An implicit assumption underlying compressive sensing -- both in theory and its applications -- is that every sample has the same cost: its goal is to simply reduce the number of samples while achieving a good recovery accuracy. In many networked sensing systems, however, the cost of obtaining a specific sample may depend highly on the location, time, condition of the device, and many other factors of the sample.

Social networks are the most engaging applications on mobile devices, and they are becoming the main sources for users to consume content. However, content retrieval, especially for embedded links and multimedia, can often be too slow, too energy hungry or too expensive for on-the-go mobile users. To address these issues, we collect and analyze a large set of traces from over 6000 real-life users of a popular mobile Twitter client. Based on the unique challenges identified from our dataset, we present inference-based social network content prefetcher, Earlybird. It uses the specific signals unique to social data in order to retrieve news feeds and associated links and multimedia ahead of users' usage. Our regression-based content prediction model is able to estimate a user's likely content interests 55% of the time. Second, we develop a prefetch scheduling scheme to maximize delay reduction under users' resource constraints. For validation, we apply Earlybird to our collected dataset. We show that on average users can reduce their delays by 62% at the cost of no more than 3% battery and 40MB/month cellular data.

We study contextual bandits with budget and time constraints under discrete contexts, referred to as constrained contextual bandits. The time and budget constraints significantly complicate the exploration and exploitation tradeoff because they introduce complex coupling among contexts over time. To gain insight, we first study unit-cost systems with known context distribution. When the expected rewards are known, we develop an approximation of the oracle, referred to Adaptive-Linear-Programming(ALP), which achieves near-optimality and only requires the ordering of expected rewards. With these highly desirable features, we then combine ALP with the upper-confidence-bound (UCB) method in the general case where the expected rewards are unknown a priori. We show that the proposed UCB-ALP algorithm achieves logarithmic regret except in certain boundary cases.Further, we design algorithms and obtain similar regret analysis results for more general systems with unknown context distribution or heterogeneous costs. To the best of our knowledge, this is the first work that shows how to achieve logarithmic regret in constrained contextual bandits. Moreover, this work also sheds light on the study of computationally efficient algorithms for general constrained contextual bandits.

In data centers, traffic demand varies in both large and small time scales. A data center with dynamic traffic often needs to over-provision active servers to meet the peak demand, which incurs significant energy cost. In this paper, our goal is to reduce energy cost of a set of distributed Internet data centers (IDCs) while maintaining the quality of service of the dynamic traffic. In particular, we consider the outage probability as the QoS metric, where outage is defined as service demand exceeding the capacity. We require the outage probability at each IDC to be smaller than a predefined threshold. Our goal is thus to minimize total energy cost over all IDCs, subject to the outage probability constraint. We achieve the goal by dynamically adjusting server capacity and performing load shifting in different time scales. We propose three different load-shifting and joint capacity allocation schemes with different complexity and performance. Our schemes leverage both stochastic multiplexing gain and electricity-price diversity. Thus, improving over prior work, our schemes reduce energy consumption/cost even when all IDCs have the same electricity price. We use both simulated load traces and real traffic traces to evaluate the performance of the proposed schemes. Results show that our proposed schemes are efficient in reducing energy cost, and robust in QoS provisioning.

In this paper, we study how to use the solar radiation model to predict energy arrivals and to allocate energy resource at an energy harvesting base station (BS). First, some primary knowledge about solar radiation is reviewed and summarized. We present two solar energy models for cloudless days and cloudy days, respectively. Then artificial neural network (ANN) is used to predict solar energy arrivals in a short period, which has an improved performance compared with the previous linear model. In the end, the allocation of received energy is considered, and one optimal offline algorithm and four heuristics online algorithms are proposed. We evaluate the performance of the algorithms using Denver's solar radiation data in recent 27 years from National Renewable Energy Laboratory (NERL). Simulation results show our prediction and optimization algorithm achieves nearly optimal performance.

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.

Opportunistic scheduling of delay-tolerant traffic has been shown to substantially improve spectrum efficiency. To encourage users to adopt delay-tolerant scheduling for capacity-improvement, it is critical to provide guarantees in terms of completion time. In this paper, we study application-level scheduling with deadline constraints, where the deadline is pre-specified by users/applications and is associated with a deadline violation probability. To address the exponentially-high complexity due to temporally-varying channel conditions and deadline constraints, we develop a novel asymptotic approach that exploits the largeness of the network to our advantage. Specifically, we identify a lower bound on the deadline violation probability, and propose simple policies that achieve the lower bound in the large-system regime. The results in this paper thus provide a rigorous analytical framework to develop and analyze policies for application-level scheduling under very general settings of channel models and deadline requirements. Further, based on the asymptotic approach, we propose the notion of Application-Level Effective Capacity region, i.e., the throughput region that can be supported subject to deadline constraints, which allows us to quantify the potential gain of application-level scheduling.

Motivated by the increasing popularity of learning and predicting human user behavior in communication and computing systems, in this paper, we investigate the fundamental benefit of predictive scheduling, i.e., predicting and pre-serving arrivals, in controlled queueing systems. Based on a lookahead-window prediction model, we first establish a novel queue-equivalence between the predictive queueing system with a fully-efficient scheduling scheme and an equivalent queueing system without prediction. This result allows us to analytically demonstrate that predictive scheduling necessarily improves system delay performance and drives it to zero with increasing prediction power. It also enables us to exactly determine the required prediction power for different systems and study its impact on tail delay. We then propose the Predictive, Backpressure, (PBP) algorithm for achieving optimal utility performance in such predictive systems. PBP efficiently incorporates prediction into stochastic system control and avoids the great complication due to the exponential state space growth in the prediction window size. We show that PBP achieves a utility performance that is within O(ε) of the optimal, for any ε>0, while guaranteeing that the system delay distribution is a shifted-to-the-left version of that under the original Backpressure algorithm. Hence, the average delay under PBP is strictly better than that under Backpressure, and vanishes with increasing prediction window size. This implies that the resulting utility-delay tradeoff with predictive scheduling can beat the known optimal [O(ε), O(log(1/ε))] tradeoff for systems without prediction.

In this paper, we investigate the power of online learning in stochastic network optimization with unknown system statistics a priori. We are interested in understanding how information and learning can be efficiently incorporated into system control techniques, and what are the fundamental benefits of doing so. We propose two Online Learning-Aided Control techniques, OLAC and OLAC2, that explicitly utilize the past system information in current system control via a learning procedure called dual learning. We prove strong performance guarantees of the proposed algorithms: OLAC and OLAC2 achieve the near-optimal [O(ε), O([log(1/ε)]2)] utility-delay tradeoff and OLAC2 possesses an O(ε-2/3) convergence time. Simulation results also confirm the superior performance of the proposed algorithms in practice. To the best of our knowledge, OLAC and OLAC2 are the first algorithms that simultaneously possess explicit near-optimal delay guarantee and sub-linear convergence time, and our attempt is the first to explicitly incorporate online learning into stochastic network optimization and to demonstrate its power in both theory and practice.

In online service systems, delay experienced by a user from the service request to the service completion is one of the most critical performance metrics. To improve user delay experience, in this paper, we investigate a novel aspect of system design: proactive serving, where the system can predict future user request arrivals and allocate its capacity to serve these upcoming requests proactively. In particular, we investigate the average user delay under proactive serving from a queuing theory perspective. We show that proactive serving reduces the average user delay exponentially (as a function of the prediction window size) under M/M/1 queueing models. Our simulation results show that, for G/G/1 queueing models, the average user delay also decreases significantly under proactive serving.

In this paper, we propose a resource allocation scheme for interference management in heterogeneous networks. We particularly consider downlink interference from a Home eNB (HeNB) to macrocell user equipments (MUEs) in the coverage of the traditional macrocell basestation (MBS). By overhearing uplink feedback information from MUEs and Home User Equipments (HUEs) together with downlink control information (DCI) from the MBS, the HeNB formulates a dynamic programming problem with the objective of maximizing the total reward over an infinite horizon. By exploiting the feedback information as well as the DCI at the HeNB, we show that the solution of the dynamic programming problem follows a greedy policy at the HeNB, which simplifies the solution of the infinite horizon dynamic programming problem. We also examine the effect of uncertainty in the feedback information on the performance of our proposed scheme.

This paper studies interference mitigation in heterogeneous cellular networks consisting of traditional macrocells and newly envisioned femtocells. The mutual interference between macrocells and femtocells arises as a result of decentralized femtocell deployment and backhaul delay. To mitigate downlink interference between the femtocell clients, known as Home User Equipments (HUEs), and macrocell clients, known as Macrocell User Equipments (MUEs), we present methods of dynamic distributed beamforming that are fully compatible with MIMO precoding mechanisms in existing LTE standard releases. We develop three MIMO beamforming schemes for interference mitigation that take into account the Quality of Service (QoS) requirement of both femtocell and macrocell clients. These new heterogeneous MIMO precoding strategies improve flexibility in resource provisioning and signaling requirement while responding to different QoS needs. We also present MUE mean throughput analysis by applying order statistics to our proposed methods. Moreover, we provide an approximate closed form for the mean throughput in terms of basic transmitter, channel, and receiver parameters. Furthermore, we extend our proposed interference control precoding schemes to spatial multiplexing for MIMO transmissions. Finally, we extend our solution to tackle the more general case involving multiple MUEs, multiple HUEs, and multiple femtocells.

We design, implement, and evaluate an H.264/SVC decoder and an HTTP video streaming client on multi-core mobile devices. The decoder employs multiple decoder threads to leverage the multi-core CPUs, and the streaming server/client support adaptive HTTP video streaming. To evaluate the decoder performance, we conduct experiments using real H.264/SVC videos on a tablet and a smart phone running Android 4.0. Our experimental results demonstrate that real-time H.264/SVC decoding is feasible on multi-core mobile devices. For example, for 960×544 videos, our decoder achieves up to 20.72 FPS (Frame-Per-Second), and for 480×272 videos, it achieves up to 42.03 FPS. We also conduct extensive HTTP video streaming experiments over live WiFi and 3G cellular networks, which show that high frame rate (up to ~42 FPS), and short initial delay (as small as ~2.5 sec) are possible. We make our testbed publicly available to the research communities.

No abstract available.

No abstract available.

Many data applications in the next generation cellular networks, such as content precaching and video progressive downloading, require flow-level quality of service (QoS) guarantees. One such requirement is deadline, where the transmission task needs to be completed before the application-specific time. To minimize the number of uncompleted transmission tasks, we study laxity-based scheduling policies in this paper. We propose a Less-Laxity-Higher-Possible-Rate (L2HPR) policy and prove its asymptotic optimality in underloaded identical-deadline systems. The asymptotic optimality of L2HPR can be applied to estimate the schedulability of a system and provide insights on the design of scheduling policies for general systems. Based on it, we propose a framework and three heuristic policies for practical systems. Simulation results demonstrate the asymptotic optimality of L2HPR and performance improvement of proposed policies over greedy policies.

Market mechanisms have been exploited as important means for spectrum acquisition and access in cognitive radio networks. In this paper, we propose a two-tier market for decentralized dynamic spectrum access. In the proposed Tier-1 market, spectrum is traded from a primary user (PU) to secondary users (SUs) in a relatively large time scale to reduce signaling overhead. Then, driven by dynamic traffic demands, SUs set up the Tier-2 market to redistribute channels among themselves in a small time scale. More specifically, we use a Nash bargain game to model the spectrum acquisition of SUs in the Tier-1 market and derive the equilibrium prices. We then employ a strategic bargain game to study the spectrum redistribution in the Tier-2 market, where SUs can exchange channels with low overhead through random matching, bilateral bargain, and the predetermined market equilibrium price. We investigate how various factors, such as the availability of channels and bargain partners, matching strategies, and traffic dynamics, affect the market relationships. This work provides new understanding on the spectrum market and valuable guidelines to primary and secondary network operators.

We propose region- and action-aware virtual world clients. To develop such clients, we present a parameterized network traffic model, based on a large collection of Second Life traces gathered by us. Our methodology is also applicable to virtual worlds other than Second Life. With the traffic model, various optimization criteria can be adopted, including visual quality, response time, and energy consumption. We use energy consumption as the show case, and demonstrate via trace-driven simulations that, compared to two existing schemes, a mobile client can save up to 36% and 41% communication energy by selectively turning on its WiFi network interface.

Supporting massive device transmission is challenging in machine-to-machine (M2M) communications. Particularly, in event-driven M2M communications, a large number of devices become activated within a short period of time, which in turn causes high radio congestions and severe access delay. To address this issue, we propose a Fast Adaptive S-ALOHA (FASA) scheme for random access control of M2M communication systems with bursty traffic. Instead of the observation in a single slot, the statistics of consecutive idle and collision slots are used in FASA to accelerate the tracking process of network status that is critical for optimizing S-ALOHA systems. With a design based on drift analysis, the estimate of the number of the active devices under FASA converges fast to the true value. Furthermore, by examining the T-slot drifts, we prove that the proposed FASA scheme is stable as long as the average arrival rate is smaller than e-1, in the sense that the Markov chain derived from the scheme is geometrically ergodic. Simulation results demonstrate that under highly bursty traffic, the proposed FASA scheme outperforms traditional additive schemes such as PB-ALOHA and achieves near-optimal performance in reducing access delays. Moreover, compared to multiplicative schemes, FASA shows its robustness under heavy traffic load in addition to better delay performance.

This work studies femtocell resource allocation in shared spectrum heterogeneous networks. We propose an enhanced shadow chasing method for femtocell resource allocation to achieve interference mitigation in heterogeneous networks serving both Macrocell User Equipments (MUEs) and Home User Equipments (HUEs). Shadow chasing home eNB (HeNB) uses Downlink Control Information (DCI) together with over-heard macrocell user ACK/NAK feedbacks and CQI reports to assign its own downlink resources to mitigate downlink interference to MUEs. Since the HeNB receives outdated DCI due to backhaul delay, we derive a likelihood metric for each resource unit being either empty or assigned to a (low-interference) outdoor MUE based on a finite-state Markov chain model for each resource unit. By dynamically separating MUE and HUE assignments, the enhanced shadow chasing can better control the downlink interference to MUEs for QoS assurance. It effectively reduces the probability of resource collision and MUE interference compared to schemes not considering backhaul delay effect or user feedbacks.

In this paper, we investigate distributed control of multiple secondary users attempting to access the channel of a high priority primary user. Our aim is to maximize the sum cognitive (secondary) user throughput under the constraint of primary user's queue stability. We consider the effect of primary user link adaptation that allows the primary transmitter (PTx) to adapt its transmission rate in response to the secondary interference-level at the primary receiver (PRx). To control the sum secondary interference to PRx beyond the traditional collision-avoidance paradigm, we propose a novel power-control algorithm for secondary nodes to function. To develop such a distributed algorithm and to improve secondary user adaptability, we allow secondary nodes to monitor primary's radio link control information on the feedback channel. We present practical schemes that approximate the optimum solution without relying on global channel information at each secondary node.

In this paper, we propose an enhancement to a resource allocation scheme known as shadow chasing for interference mitigation in heterogeneous networks composed of Macrocell User Equipments (MUEs) and Home User Equipments (HUEs). In shadow chasing, the Home eNB (HeNB) uses Downlink Control Information (DCI) together with the overheard ACK/NAK feedback and CQI reports to assign its HUEs the Physical Resource Blocks (PRBs) that are assigned to outdoor MUEs. Since the HeNB receives an outdated DCI due to backhaul delay, our solution is to derive a likelihood metric for each PRB being either empty or assigned to an outdoor MUE by using a MC model for the state of each PRB. By dynamically separating the MUE and HUE PRB assignments, enhanced shadow chasing can better constrain the downlink interference to the MUE. Our results show effective reduction of probability of PRB assignment collision and MUE interference compared to schemes that do not integrate the delay effect or exploit user feedbacks.

When GPS devices are widely integrated into smart phones, researchers stand a big chance of collecting massive location information, that is necessary in studying users' moving behavior and predicting the next location of the users. Once the next location of a user can be determined, it can serve as input for many applications, such as location based service, scheduling users access in a mobile network or even home automation. One important task in predicting the next location is to identify typical users' moving patterns. In this paper, we propose a novel method to extract the patterns using deep learning. Experiment results show significant performance improvement of the proposed method compared to the classical principal component analysis method.

In this paper1, we study interference mitigation in cellular networks with femtocells. We propose to use adaptive distributed beamforming to mitigate downlink interference between femtocell users, known as Home User Equipments (HUEs), and macrocell users, known as Macrocell User Equipments (MUEs). We develop three MEVIO beamforming schemes for interference mitigation that take into account the QoS requirement of femtocell and macrocell clients. These new heterogeneous MIMO precoding strategies improve flexibility in resource provisioning and signaling requirement in response to QoS need. The proposed schemes minimize the interference at the MUE or maximize the throughput at the HUE depending on the network traffic and QoS constraints. We also analyze the MUE mean throughput by applying order statistics theory.

Cognitive radio gives users the ability to switch channels and make use of dynamic spectrum opportunities. However, switching channels takes time, and may affect the quality of a user's transmission. When a cognitive radio user's channel becomes unavailable, sometimes it may be better waiting until its current channel becomes available again. Motivated by the recent FCC ruling on TV white space, we consider the scenario where cognitive radio users are given the foreknowledge of channel availabilities. Using this information, each user must decide when and how to switch channels. The users wish to exploit spectrum opportunities, but they must take account of the cost of switching channels and the congestion that comes from sharing channels with one another. We model the scenario as a game which, as we show, is equivalent to a network congestion game in the literature after proper and non-trivial transformations. This allows us to design a protocol which the users can apply to find Nash equilibria in a distributed manner. We further evaluate how the performance of the proposed schemes depends on switching cost using real channel availability measurements.

To reduce datacenter energy consumption and cost, current practice has considered demand-proportional resource provisioning schemes, where servers are turned on/off according to the load of requests. Most existing work considers instantaneous (Internet) requests only, which are explicitly or implicitly assumed to be delay-sensitive. On the other hand, in datacenters, there exist a vast amount of delay-tolerant jobs, such as background/maintainance jobs. In this paper, we explicitly differentiate delay-sensitive jobs and delay tolerant jobs. We focus on the problem of using delay-tolerant jobs to fill the extra capacity of datacenters, referred to as trough/valley filling. Giving a higher priority to delay-sensitive jobs, our scheme complements most existing demand-proportional resource provisioning schemes. Our goal is to design an intelligent trough filling mechanism that is energy efficient and also achieves good delay performance. Specifically, we propose a joint dynamic speed scaling and traffic shifting scheme. The scheme does not need statistical information of the system, which is usually difficult to obtain. In the proposed scheme, energy cost saving comes from dynamic speed scaling, statistical multiplexing, electricity price diversity, and service efficiency diversity. In addition, good delay performance is achieved via load shifting and capacity allocation based on queue conditions. We show the efficiency of the proposed scheme by both analysis and simulation.

Today's mobile Internet is heavily overloaded by the increasing demand and capability of mobile devices, in particular, multimedia traffic. However, not all traffic is created equal, and a large portion of multimedia contents on the mobile Internet is delay tolerant. We study the problem of capitalizing the content transfer opportunities under better network conditions via postponing the transfers without violating the user-specified deadlines. We propose a new framework called SmartTransfer, which offers a unified content transfer interface to mobile applications. We also develop two scheduling algorithms to opportunistically schedule the content transfers. Via extensive trace-driven simulations, we show that our algorithms outperform a baseline scheduling algorithm by far: up to 17 times improvement in upload throughput and/or at most 20 dBm boost in signal strength. The simulation results also reveal various tradeoff between the two proposed scheduling algorithms. We have implemented our framework and one of the scheduling algorithms on Android, to demonstrate their practicality and efficiency.

On-demand video services such as Youtube and Hulu are expected to comprise a large percentage of the increasing data loads in mobile networks. On-demand video is distinctive because it is pre-recorded and therefore can be considered elastic traffic because the video frame buffer can be downloaded well past the current point of playback. Based on this observation, we propose Video Rest-and-Download (VR&D) as a video download application framework that aims to reduce network congestion while maintaining playback quality. The intuition for VR&D is that, in a scenario where radio resources are shared by multiple data users, the video user can “rest” for some amount of time until fewer users are in the network, thereby allowing other data users to complete their downloads faster, without affecting playback quality. We present an algorithmic framework for VR&D based on the Markov Decision Process that uses the history and current state of network activity to determine how aggressive the user should be in downloading video frames. We evaluate its performance using a simulated UMTS network with HSDPA data service based on real network traces from a major U.S. carrier. Our results show that, compared to the existing solution, during the time of video playback this application can reduce download time by as high as 50%, and alleviate network congestion by up to 30% with minimal effect on playback quality.

Machine-to-Machine (M2M) communication is now playing a market-changing role in a wide range of business world. However, in event-driven M2M communications, a large number of devices activate within a short period of time, which in turn causes high radio congestions and severe access delay. To address this issue, we propose a Fast Adaptive S- ALOHA (FASA) scheme for M2M communication systems with bursty traffic. The statistics of consecutive idle and collision slots, rather than the observation in a single slot, are used in FASA to accelerate the tracking process of network status. Furthermore, the fast convergence property of FASA is guaranteed by using drift analysis. Simulation results demonstrate that the proposed FASA scheme achieves near-optimal performance in reducing access delay, which outperforms that of traditional additive schemes such as PB-ALOHA. Moreover, compared to multiplicative schemes, FASA shows its robustness even under heavy traffic load in addition to better delay performance.

Cognitive radio systems capable of opportunistic spectrum access represent a new paradigm for improving the efficiency of current spectrum utilisation. In this work, the authors present a novel cognitive channel access method based on learning from both primary channel transmissions and the receiver ARQ feedback signals. This new sensing-plus-confirmation scheme constitutes a non-trivial generalisation of the more traditional ‘Listen-Before-Talk’ (LBT) strategy that merely listens to and yields to primary transmissions regardless of primary receiver (PRx) responses. Our new method exploits the bi-directional and interactive nature of most wireless communication links to facilitate better opportunistic secondary access while achieving PRx protection. By allowing the secondary users to learn from both primary transmissions and the corresponding receiver confirmations, our approach allows secondary cognitive users to exploit critical information that PRxs regularly send to their transmitters. The authors show that, by monitoring both primary transmissions and receiver feedback signals, secondary radio access can improve throughput over the traditional LBT while limiting the probability of collision with primary user signals.

Cognitive radio (CR) improves spectrum efficiency by allowing secondary users (SUs) to dynamically exploit the idle spectrum owned by primary users (PUs). This paper studies optimal bandwidth allocation of SUs for throughput efficiency. Consider the following tradeoff: an SU increases its instantaneous throughput by accessing more spectrum, but channel access/switching overhead, contention among multiple SUs, and dynamic PU activity create higher liability for larger bandwidths. So how much is too much? In this paper, we study the optimal bandwidth allocation for multiple SUs. Our approach is twofold. We first study the optimal bandwidth an SU should use to maximize the per-SU throughput in the long term. The optimal bandwidth is derived in the context of dynamic PU activity, where we consider both independent and correlated PU channel scenarios while accounting for the effects of channel switching overhead. We further consider the case of suboptimal spectrum use by SUs in the short term due to PU activity dynamics. We propose an efficient channel reconfiguration (CREC) scheme to improve SUs' performance. We use real PU channel activity traces in the simulations to validate our results. The work sheds light on the design of spectrum sharing protocols in cognitive radio networks.

Cognitive radio (CR) technology has great potential to alleviate spectrum scarcity in wireless communications. It allows secondary users (SUs) to opportunistically access spectrum licensed by primary users (PUs) while protecting PU activity. The protection of the PUs is central to the adoption of this technology since no PU would accommodate SU access to its own detriment. In this paper, we consider an SU that must protect multiple PUs simultaneously. We focus on the PU packet collision probability as the protection metric. The PUs are unslotted and may have different idle/busy time distributions and protection requirements. Under general idle time distributions, we determine the form of the SU optimal access policy and identify two special cases for which the computation of the optimal policy is significantly reduced. We also present a simple algorithm to determine these policies using principles of convex optimization theory. We then derive the optimal policy for the same system when an SU has extra “side information” on PU activity. We evaluate the performance of these policies through simulation.

Virtual worlds, such as Second Life, are computer-simulated spaces divided into multiple regions, in which each user controls an avatar to perform actions (such as run and fly) in order to interact with other users. Second Life incurs diverse traffic patterns in different regions and with different actions. Hence, we propose region- and action-aware Second Life clients, which adapt to and take advantages of the diverse traffic patterns for user-specified optimization criterion, such as high visual quality, low energy consumption, and short response time. To achieve this, we develop a parameterized traffic model to predict Second Life traffic patterns. We systematically derive the traffic model parameters using public Second Life traces [1], and we validate the model accuracy using another set of real network traces. To the best of our knowledge, region- and action-aware virtual world clients have never been considered in the literature. In addition, the proposed parameterized traffic model is of interest in its own right to various parties, including: (i) virtual world developers, (ii) researchers, and (iii) Internet Service Providers (ISPs).

Traffic density in wireless networks is time- and space-varying as users move from one area to another. For example, the majority of traffic stays in residential areas in the early morning and late evening; but moves to business or commercial areas in daytime. Therefore, it is challenging to efficiently locate base stations during network planning stage, due to the time-varying traffic distribution. Base stations vary from highly congested to seldom utilized depending on time. However, measurement studies show that the movement of the traffic density is highly predictable, and the traffic always travel along similar routes among different parts in a city or town during one day or over a week. Therefore, we introduce the traffic-tracing gateway (TTG), which acts as the base station that tracks the movement of the traffic. Given the traffic distribution of a period, we design an algorithm to determine the optimal trajectories of TTGs that can cover the maximum traffic. Our solution framework can optimally deploy TTGs in the congested areas to provide better coverage and relieve congestion. Our simulation studies based on realistic user mobility show that TTGs can result in significant improvement over fixed infrastructure based network across multiple metrics in multiple scenarios.

In this paper, our goal is to achieve an optimal tradeoff between energy efficiency and service performance over a set of distributed IDCs with dynamic demand. In particular, we consider the outage probability as the QoS metric, where outage is defined as service demand exceeding the capacity of an IDC. Our goal is thus to minimize total energy cost over all IDCs, subject to the outage probability constraint. We achieve the goal by dynamically adjusting server capacity and performing load shifting in different time scales. We propose three different load-shifting and joint capacity allocation schemes with different complexity and performance. Our schemes leverage both stochastic multiplexing gain and electricity-price diversity.

Although network traces of virtual worlds are valuable to ISPs (Internet service providers), virtual world software developers, and research communities, they do not exist in the public domain. In this work, we implement a complete testbed to efficiently collect and analyze network traces from a popular virtual world: Second Life. We use the testbed to gather traces from 100 regions with diverse characteristics. The network traces represent more than 60 hours of virtual world traffic and the trace files are created in a well-structured and concise format. Our preliminary analysis on the collected traces is consistent with previous work in the literature. It also reveals some new insights: for example, local avatar/object density imposes clear implications on traffic patterns. The developed testbed and released trace files can be leveraged by research communities for various studies on virtual worlds. For example, accurate traffic models can be derived from our trace files, which in turn can guide developers for better virtual world designs

This work on cognitive radio access ventures beyond the more traditional "listen-before-talk" paradigm that underlies many cognitive radio access proposals. We exploit the bi-directional interaction of most primary communication links. By intelligently controlling their access parameters based on the inference from observed link control signals of primary user (PU) communications, cognitive secondary users (SUs) can achieve higher spectrum efficiency while limiting their interference to the PU network. In one specific implementation, we let the SUs listen to the PU's feedback channel to assess their own interference on the primary receiver, and adjust radio power accordingly to satisfy the PU's interference constraint. We propose a discounted distributed power control algorithm to achieve non-intrusive secondary spectrum access without either a centralized controller or active PU cooperation. We present an analytical study of its convergence property. We show that the link control feedback information inherent in many two-way primary systems can be used as important reference signal among multiple SU pairs to distributively achieve a joint performance assurance for primary receiver's quality of service.

We study the integrated WiFi/WiMAX networks, where users are equipped with dual-radio interfaces that can connect to either a WiFi or a WiMAX network. Previous research on integrated heterogeneous networks (e.g., WiFi/cellular) usually considers one network as the main and the other as the auxiliary. The performance of the integrated network is compared with the "main” network. The gain is apparently due to the additional resources from the auxiliary network. In this study, we are interested in integration gain that comes from the better utilization of the resource rather than the increase of the resource. The heterogeneity of the two networks is the fundamental reason for the integration gain. To quantify it, we design a generic framework that supports different performance objectives. We focus on the max-min throughput fairness in this work and also briefly cover the proportional fairness metric. We first prove that it is NP-hard to achieve integral max-min throughput fairness, then propose a heuristic algorithm, which provides two-approximation to the optimal fractional solution. Simulation results demonstrate significant integration gain from three sources, namely, spatial multiplexing, multinetwork diversity, and multiuser diversity. For the proportional fairness metric, we derive the formulation and propose a heuristic algorithm, which shows satisfactory performance when compared with the optimal solution.

In this paper, we analyze the delay performance of a secondary user (SU) under dynamic spectrum access. We design simple time-threshold policies for the SU to minimize the average delay while satisfying the collision probability constraint of the primary user (PU). Such policies perform closely to an optimized policy found by a Markov Decision Process (MDP) formulation, while facilitating analytical analysis of the delay and collision probability. For general PU busy and idle period distributions, we analyze the performance of threshold policies through a one-dimensional Markov chain, and develop analytical expressions to approximate the delay and collision probability. The accuracy of the Markov chain analysis and the analytical approximations is examined under various busy and idle distributions. We investigate the impact of busy and idle distributions on system performance. We find that while the idle distribution determines the time capacity of SU access, the busy distribution significantly affects the delay performance of the threshold policies. The effect of imperfect sensing is also studied.

By exploiting multiple network interfaces on one device, e.g., Wireless Wide Area Network (WWAN) and Wireless Local Area Network (WLAN), peers receiving different subsets of WWAN broadcast/multicast packets can perform Cooperative Peer-to-peer Repair (CPR) by exchanging received WWAN packets with their local WLAN peers. This effectively improves the transmission success from a WWAN broadcast/multicast source to a CPR collective. In this paper, we propose a novel joint source/channel bit allocation scheme for WWAN scalable video multicast that leverages the CPR paradigm. One key observation is that given a peer can successfully receive a packet either from theWWAN channel directly, or via a CPR neighbor using ad-hoc WLAN connections, more bits can be redistributed from channel to source coding out of a fixed WWAN bit budget to further minimize individual node's expected visual distortion. In our proposal, groups of peers requiring different video resolutions are assigned to the same multicast group, and we perform one WWAN resource allocation and subsequent CPR over heterogeneous peers of different resolutions together. Our simulations show that our joint multicast group optimization can improve video quality by up to 2.84 dB, compared to a scheme where both WWAN resource allocation and WLAN CPR are separately performed for heterogeneous peers.

Recent research has exploited the multi-homing property (one terminal with multiple network interfaces) of modern devices to improve communication performance in wireless networks. Cooperative Peer-to-peer Repair (CPR) is one example where given simultaneous connections to both a Wireless Wide Area Network (WWAN) and an ad-hoc Wireless Local Area Network (WLAN), peers receiving different subsets of WWAN broadcast packets can exchange received WWAN packets with their ad-hoc WLAN peers for local recovery. In our previous work, we have shown that by using Network Coding (NC) to linearly combine received packets into new CPR packets for local exchanges, packet recovery can be improved. Moreover, by imposing Structure on Network Coding (SNC) when encoding a CPR packet, decoding of at least the important packets becomes possible in the event when insufficient number of CPR packets were received for full recovery. Given SNC is used during CPR, the key decision for each peer is to determine which SNC type to encode a repair packet at each WLAN transmission opportunity. The decision is further complicated by the observation that peers in general receive different numbers of CPR packets from neighbors due to varying amount of WLAN link contentions and interference experienced. In this paper, we propose a novel counter-based deterministic SNC type selection scheme. Using this approach, we show that a simple local optimization procedure, taking advantage of available neighbors' state information, can be easily implemented to further improved CPR performance. Simulation results show that our proposed scheme outperformed our previous randomized SNC type selection scheme by up to 1.87dB.

We venture beyond the "listen-before-talk" strategy that is common in many traditional cognitive radio access schemes. We exploit the bi-directional nature of most primary communication systems. By intelligently choosing their transmission parameters based on the observation of primary user (PU) communications, secondary users (SUs) in a cognitive network can achieve higher spectrum usage while limiting their interference to the PU. Specifically, we propose that the SUs listen to the PU's feedback channel to assess their interference on the primary receiver (PU-Rx), and adjust radio power accordingly to satisfy the PU's interference constraint. We investigate both centralized and distributed power control algorithms without active PU cooperation. We show that the PU feedback information inherent in many two-way primary systems can be used as important coordination signal among multiple SUs to distributively achieve a joint performance guarantee on the primary receiver's quality of service.

Market mechanisms have been exploited as important means for spectrum acquisition and access in cognitive radio networks. In this paper, we propose a two-tier market for decentralized dynamic spectrum access. In the proposed Tier-1 market, spectrum is traded from a primary user (PU) to secondary users (SUs) in a relatively large time scale to reduce signaling overhead. Then driven by dynamic traffic demands, SUs set up the Tier-2 market to redistribute channels among themselves in a small time scale. More specifically, we use Nash bargain game to model the spectrum acquisition of SUs in the Tier-1 market and derive the equilibrium prices. We then use strategic bargain game to study the spectrum redistribution in the Tier-2 market, where SUs can exchange channels with low overhead through random matching, bilateral bargain, and the predetermined market equilibrium prices. We disclose how various factors, such as availability of channels and bargain partners, matching schemes, and traffic dynamics, impact the market relationships. This work provides better understanding on the spectrum market and valuable guidelines to primary and secondary network operators.

Third Generation (3G) cellular networks take advantage of time-varying and location-dependent channel conditions of mobile users to provide broadband services. Under fairness and QoS constraints, they use opportunistic scheduling to efficiently utilize the available spectrum. Opportunistic scheduling algorithms rely on the collaboration among all mobile users to achieve their design objectives. However, we demonstrate that rogue cellular devices can exploit vulnerabilities in popular opportunistic scheduling algorithms, such as Proportional Fair (PF) and Temporal Fair (TF), to usurp the majority of time slots in 3G networks. Our simulations show that under realistic conditions, only five rogue device per 50-user cell can capture up to 95 percent of the time slots, and can cause 2-second end-to-end interpacket transmission delay on VoIP applications for every user in the same cell, rendering VoIP applications useless. To defend against this attack, we propose strengthening the PF and TF schedulers and a robust handoff scheme.

In the above titled paper (ibid., vol. 11, no. 4, pp. 730-741, Jun. 09), simulation errors were discovered. This errata outlines a corrective derivation and presents updated simulation results.

We consider wireless ad hoc networks with a large number of users. Subsets of users might be interested in identical information, and so we have a regime in which several multicast sessions may coexist. We first calculate an upper bound on the achievable transmission rate per multicast flow as a function of the number of multicast sources in such a network. We then propose a simple comb-based architecture for multicast routing, which achieves the upper bound in an order sense under certain constraints. Compared to the approach of constructing a Steiner tree to decide multicast paths, our construction achieves the same order-optimal results while requiring little location information and no computational overhead.

We present a framework based on Markov decision process to optimize software on mobile phones. Unlike previous approaches in literature that focus on energy optimization while meeting a specific task-related time constraint, we model the desired talk-time as an explicit user given parameter and formulate the optimization of resources such as battery-life on a mobile phone as a decision processes that maximizes a user specified application specific reward or utility metric while meeting the talk-time constraint. We propose efficient techniques to solve the optimization problem based on dynamic programming and illustrate how it can be used in the context of realistic applications such as WiFi radio power optimization and email synchronization. We present a design methodology to use the proposed technique and experimental results using the Android platform from Google running on the HTC mobile phone.

In cognitive wireless networks where secondary users (SUs) opportunistically access spectral white spaces of primary users (PUs), there exists an inherent tradeoff between sensing and transmission due to the competing goals of PU protection and SU access maximization. This paper studies means of sensing-transmission for SUs to better manage the competing goals by defining utility function to reward the SU for successful packet transmissions and to penalize it for colliding with PU. To maximize the SU utility, we present a threshold-based sensing-transmission structure that is optimal under a technical constraint. Both perfect sensing and imperfect sensing are considered, with or without SU acknowledgement of reception. This SU access scheme optimizes SU access efficiency while protecting PU performance. It sets a benchmark and provides insight for the design of sensing-transmission control in cognitive networks such as IEEE 802.22.

Because of frequent wireless packet losses and inapplicability of retransmission-based schemes due to the wellknown NAK implosion problem, providing high quality video multicast over wireless wide area networks (WWAN) remains difficult. Traditional joint source/channel coding schemes for video multicast-optimal bit allocation among source coding and channel coding such as forward error correction (FEC) subject to a bitrate constraint-target a chosen nth-percentile WWAN user. Not only is FEC bitwise expensive, users with poorer reception than nth-percentile user suffer substantial channel losses, while users with better reception have more channel coding than necessary, meaning too few bits are devoted for source coding to reduce quantization noise and sub-optimal video quality. Instead, in this paper we perform joint source/channel coding of WWAN video multicast for an entire collective of multi-homed ad-hoc peers in the same multicast group and connected via wireless local area networks (WLAN). In a cooperative peer-to-peer repair (CPR) scenario, after each peer received a different subset of WWAN packets, the peer group repairs WWAN losses locally by packet-forwarding to each other via WLAN. From an end-to-end system view, CPR means that a packet can be transmitted from source to a peer either via WWAN directly, or via WLAN local repairs exploiting neighboring peers' WWAN links; the overall more general transmission condition means a clever joint source/channel coding scheme can now allocate more bits to source coding without suffering more packet losses, leading to higher video quality. To efficiently implement both WWAN FEC and WLAN CPR repairs, we propose to use network coding for this dual purpose to reduce decoding complexity at the peers. We show through simulations that using our proposed scheme dramatically improves video quality over existing optimization scheme where joint source/channel coding was performed, but WLAN CPR was not used, by up to 8.4 dB, and over scheme when WLAN CPR and WWAN joint source/channel coding were performed separately by up to 4.4 dB.

Cognitive radio offers a promising technology to mitigate spectrum shortage in wireless communications. It enables secondary users (SUs) to opportunistically access low-occupancy primary spectral bands as long as their negative effect on the primary user (PU) access is constrained. This PU protection requirement is particularly challenging for multiple SUs over a wide geographical area. In this paper, we study the fundamental performance limit on the throughput of cognitive radio networks under the PU packet collision constraint. With perfect sensing, we develop an optimum spectrum access strategy under generic PU traffic patterns. Without perfect sensing, we quantify the impact of missed detection and false alarm, and propose a modified threshold-based spectrum access strategy that achieves close-to-optimal performance. Moreover, we develop and evaluate a distributed access scheme that enables multiple SUs to collectively protect the PU while adapting to behavioral changes in PU usage patterns. Our results provide useful insight on the trade-off between the protection of the primary user and the throughput performance of cognitive radios.

Joint routing-and-scheduling has been considered in wireless mesh networks for its significant performance improvement. While existing work assumes it, accurate traffic information is usually not available due to traffic dynamics, as well as inaccuracy and delay in its measurement and dissemination. In addition, the joint routing and scheduling usually requires a centralized controller to calculate the optimal routing and scheduling and distribute such policies to all the nodes. Thus, even if the accurate traffic information is always available, the central controller has to compute the routing and scheduling repeatedly because the traffic demands change continuously. This leads to prohibitive computation and distribution overhead. Therefore, in this paper, we propose a joint routing-scheduling scheme that achieves robust performance under traffic information uncertainty. In particular, it achieves worst-case optimal performance under a range of traffic conditions. This unique feature validates the use of centralized routing and scheduling in wireless mesh networks. As long as the traffic variation is within the estimation range, the routing and scheduling do not need to be recomputed and redistributed. Through extensive simulations, we show that our proposed scheme meets the objective (i.e., optimizes the worst-case performance). Moreover, although it only guarantees the worst-case performance in theory, its average performance is also good. For example, our proposed scheme can perform better than a fixed optimal routing and scheduling scheme in more than 80 percent of 500 random traffic instances. Our scheme provides insights on the desired properties of multipath routing, namely, spatial reuse and load balancing.

In a scenario where each peer of an ad-hoc wireless local area network (WLAN) receives one of many available video streams from a wireless wide area network (WWAN), we propose a network-coding-based cooperative repair framework for the ad-hoc peer group to improve broadcast video quality during channel losses. Specifically, we first impose network coding structures globally, and then select the appropriate video streams and network coding types within the structures locally, so that repair can be optimized for broadcast video in a rate-distortion manner. Innovative probability—the likelihood that a repair packet is useful in data recovery to a receiving peer—is analyzed in this setting for accurate optimization of the network codes. Our simulation results show that by using our framework, video quality can be improved by up to 19.71 dB over un-repaired video stream and by up to 5.39 dB over video stream using traditional unstructured network coding.

Cooperative Peer-to-Peer Repair (CPR) has been proposed to recover from packet losses incurred during 3G broadcast. CPR leverages the increasing presence of multi-homed mobile devices having both 3G cellular and IEEE 802.11 wireless interfaces. Mobile devices can, therefore, draw upon IEEE 802.11 peering links to cooperatively achieve out-of-band repair of 3G broadcasting losses. This paper considers the problem of employing Network Coding (NC) to exploit the broadcast nature of the wireless medium towards enhancing the efficiency of CPR. We show that the minimum latency scheduling problem for NC based CPR (NC-CPR) is NP-Hard. We present heuristics for NC-CPR that assume a priori topology and packet loss information. Insights gained from our heuristics are leveraged to propose NC-DCPR, a fully distributed protocol for NC-CPR. We conduct extensive simulation experiments under realistic network conditions. Our results show that employing network coding significantly improves the efficiency of CPR.

Driven by regulatory initiatives and radio technology advances, opportunistic spectrum access has the potential to mitigate spectrum scarcity and meet the increasing demand for spectrum. In this paper, we consider a scenario where secondary users can opportunistically access unused spectrum vacated by idle primaries. We introduce two metrics to protect primary performance, namely collision probability and overlapping time. We present three spectrum access schemes using different sensing, back-off, and transmission mechanisms. We show that they achieve indistinguishable secondary performance under given primary constraints. We provide closed form analysis on secondary user performance, present a tight capacity upper bound, and reveal the impact of various design options, such as sensing, packet length distribution, back-off time, packet overhead, and grouping. Our work sheds light on the fundamental properties and design criteria on opportunistic spectrum access.

Wi-Fi-based mesh networks have been considered as a viable option to provide wireless coverage for a vast area, such as community-wide or city-wide. However, interference due to multihop transmissions and potential isolated (disconnected) nodes are the major obstacles to achieve high performance. In this paper, we propose a heterogeneous wireless network architecture, consisting of Wi-Fi and WiMAX, to overcome these limitations. We first construct an optimization problem to analyze the benefits of heterogeneous networks. Then, we design a practical protocol to efficiently combine the resources of Wi-Fi and WiMAX networks. The evaluations show that our new scheme greatly improves the system performance in terms of throughput and fairness.

By providing coding ability at intermediate nodes, network coding has been shown to improve throughput in wireless broadcast/multicast networks. Considering a scenario where wireless ad-hoc peers cooperatively relay packets to each other to recover packets lost during MBMS broadcast, we show that by first imposing coding structures globally and then selecting the appropriate types within the structures locally, network coding can be optimized for video streaming in a rate-distortion manner. Experimental results show that our proposed scheme can improve video quality noticeably, by up to 19.71 dB over un-repaired video stream and by up to 8.34 dB over video stream using traditional unstructured network coding.

Previous results show that a node's throughput scales poorly as the network size increases when every node has traffic. However, in many cases, only a fraction of nodes in large networks have data to send or receive at any given time, while other nodes can act as relays/routers. Therefore, in this paper, we study the scaling behavior from a user's viewpoint (a user is a node with traffic). We first derive an upper bound on per user throughput. To derive the lower bound, we propose a simple scheduling scheme that enables users to cooperate with relay nodes and fully utilize the networks capacity. We show that per user throughput depends on the network size, the number of users, and the node deployment schemes, and is in general much more optimistic. Our scheme also sheds light on designing efficient cooperation protocols in heterogeneous networks and cognitive radio networks.

By providing coding ability at intermediate nodes, network coding has been shown to improve network throughput in broadcast/multicast wireless networks. In this paper, we show that by imposing coding structure, network coding can be further optimized specifically for video streaming in a rate-distortion manner, in a scenario where wireless adhoc peers cooperatively relay packets to each other to repair packet losses during MBMS broadcast. Experimental results show that our proposed scheme can improve video quality noticeably, by up to 19.71dB over un-repaired video stream and by up to 7.90dB over video stream using traditional unstructured network coding.

Cognitive radio has recently been identified as a potential relief to spectrum scarcity by improving temporal spectral efficiency. We investigate a flexible non-intrusive cognitive radio network based on smart antenna technologies. The proposed scheme exploits transmit beamforming to enable better spectral sharing between primary users and cognitive (secondary) users. As proposed, the cognitive transmitter equipped with antenna array forms transmit beamforming to keep the interference to primary receiver below a given threshold. By also adopting smart antennas at primary transmitters, we can significantly boost the successful transmission probability of cognitive users; thereby improving the spectrum utilization efficiency of the wireless communication networks.

In distributed wireless access networks, the short-term unfairness of IEEE 802.11 distributed coordination function (DCF) has been revealed by many works. In this paper, a modified DCF, based on the principle of priority collision resolution (PCR), is proposed to improve the short-term fairness in distributed access wireless networks. Our PCR-DCF achieves short-term fairness improvement without estimating behaviors of other users and the system contention level, such as the number of active users. Only the capability to identify collision is required. Theoretical analysis is carried out to validate the performance of PCR-DCF based on a slotted system model. Both simulations and analyses show that PCR-DCF has a much smaller packet transmission delay jitter than IEEE 802.11 DCF, with little degradation on the average packet transmission delay. Moreover, the analysis and simulation results indicate that PCR- DCF also experiences a much lower packet drop rate than IEEE 802.11 DCF in almost all load ranges with reasonable retransmission limit.

We explore the use of partially overlapped channels in wireless mesh networks that consist of multiple 802.11-based access points. We propose novel channel allocation and link scheduling algorithms in the MAC layer to enhance network performance. Due to different traffic characteristics in multi-hop WMNs compared to those in one-hop 802.11 networks, we perform our optimization based on end-to-end flow requirement, instead of the sum of link capacity. In addition, we discuss other factors affecting the performance of POC, including topology, node density, and distribution.

We consider wireless ad hoc networks with a large number of users. Subsets of users might be interested in identical information, and so we have a regime in which several multicast sessions may coexist. We first calculate an upper-bound on the achievable transmission rate per multicast flow as a function of the number of multicast sources in such a network. We then propose a simple comb-based architecture for multicast routing which achieves the upper bound in an order sense under certain constraints. Compared to the approach of constructing a Steiner tree to decide multicast paths, our construction achieves the same order-optimal results while requiring little location information and no computational overhead.

Capacity limitation is one of the fundamental issues in wireless mesh networks. This paper addresses capacity improvement issues in multi-radio multi-channel wireless mesh networks. Our objective is to find a dynamic channel assignment and link schedule that maximizes the network capacity for ftp-type applications and video-type applications, respectively. Specifically, we minimize the number of time slots needed to schedule all the flows for ftp-type applications and maximize the minimal link satisfaction ratio for video-type applications. The problems are formulated as linear programming and we provide two heuristics to solve these problems. One heuristic uses a set covering strategy and the other uses a link-weight- adjusting strategy. We perform a trade-off analysis between network performance and hardware cost based on the number of radios and channels in different topologies. This work provides valuable insights for wireless mesh network designers during network planning and deployment.

In this paper, we investigate efficient strategies for supporting on-demand information dissemination and gathering in large-scale wireless sensor networks. In particular, we propose a "comb-needle" discovery support model resembling an ancient method: use a comb to help find a needle in sand or a haystack. The model combines push and pull for information dissemination and gathering. The push component features data duplication in a linear neighborhood of each node. The pull component features a dynamic formation of an on-demand routing structure resembling a comb. The comb-needle model enables us to investigate the cost of a spectrum of push and pull combinations for supporting query and discovery in large-scale sensor networks. Our result shows that the optimal routing structure depends on the frequency of query occurrence and the spatial-temporal frequency of related events in the network. The benefit of balancing push and pull for information discovery is demonstrated

Future wireless networks will support the growing demands of heterogeneous and delay sensitive applications. In this paper, a users' satisfaction factor (USF) is defined to quantify quality of service (QoS) for different types of services such as voice, data, and multimedia, as well as for different delay constraints. This USF not only predicts the final delivered QoS during transmission, but also take advantages of the fact that different packets can be decoded at different time in the receivers. Based on this USF, four types of scheduling schemes considering tradeoffs between system performance and individual fairness are proposed. These schemes explore the time, channel, and multi-user diversity to guarantee quality of service and enhance the network performance. From the simulation results, the proposed scheduling schemes achieve different tradeoffs between individual fairness and high system performance for the heterogeneous and delay sensitive applications, compared with the weighted round-robin and the modified proportional fairness scheduling schemes

We study the deployment of data back-haul nodes for wireless networks with energy constraints. We address the following problem: given the required lifetime of a sensor network, the energy constraint of back-haul nodes, and the area to be covered, what is the minimum number of nodes needed to construct such a back-haul network and what is the corresponding deployment scheme? Finding an efficient deployment scheme involves location management, routing, and power management. We focus on linear networks and formulate a deployment optimization problem. We then propose and analyze a greedy deployment scheme that achieves close to optimal performance. We reveal the closed-form relationship among different design parameters, namely, the number of sensor nodes, the desired lifetime, and the coverage distance. We also study the effect of miscellaneous power consumptions and non-uniform data density, and consider extensions to planar networks

In this paper, we study coverage with connectivity properties in large wireless sensor networks. We consider three classes: full coverage with connectivity, partial coverage with connectivity, and constrained coverage with connectivity. We outline two simple network topologies to satisfy the constrained coverage with connectivity criterion. We compare the surveillance performance and deployment cost for networks with different coverage with connectivity criteria. Together, they cover a whole spectrum of surveillance quality in wireless sensor networks at different cost. We outline potential research topics in the area.

Abstract — Wireless networks with multi-channel multi-radio availability are attracting more and more attention from the research community because of its performance improvement and relatively low cost and complexity. Most work in the literature consider the performance of multi-channel multiradio wireless networks with predefined numbers of channels and radios, and develop algorithms for channel allocation and transmission scheduling. The capacity limit on multi-channel multi-radio wireless networks was seldom addressed before. In this work, we study two problems: In a specific topology, 1) what is the maximum capacity we can get given the number of channels and radios? and 2) what is the impact of the number of radios on the system performance? To answer the above questions, we propose a general framework to find the maximum capacity given a multi-channel multi-radio wireless network. Its result also provides an indication of the “goodness ” of a topology. We then use the framework to study the impact of radio constraints. I.

One of the main design issues for wireless sensor networks is the sensor placement problem. We formulate a constrained multivariable nonlinear programming problem to determine both the locations of the sensor nodes and data transmission pattern. Our two objectives are to maximize the network lifetime and to minimize the application-specific total cost, given a fixed number of sensor nodes in a region with a certain coverage requirement. We first study a linear network, and find optimal placement strategies numerically. Through numerical results, we show that the optimal node placement strategies provide significant benefit over a commonly used uniform placement scheme. Furthermore, we also present a performance bound as a benchmark. Lastly, we extend the results to a more sophisticated planar network, and use numerical results to evaluate the performance of the proposed strategies.

In this paper we investigate efficient strategies for supporting on-demand information dissemination and gathering in large-scale vwireless sensor networks. In particular, we propose a "comb-needle" discovery support model resembling an ancient method: use a comb to help find a needle in sands or a haystack. The model combines push and pull for information dissemination and gathering. The push component features data duplication in a linear neighborhood of each node. The pull component features a dynamic formation of an on-demand routing structure resembling a comb. The comb-needle model enables us to investigate the cost of a spectrum of push and pull combinations for supporting discovery and query in large scale sensor networks. Our result shows that the optimal routing structure depends on the frequency of query occurrence and the spatial-temporal frequency of related events in the network. The benefit of balancing push and pull for discovery in large scale geometric networks are demonstrated. We also raise the issue of query coverage in unreliable networks and investigate how redundancy can improve the coverage via both theoretical analysis and simulation. Last, we study adaptive strategies for the case where the frequencies of query and events are unknown a priori and time-varying.

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.

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.