Supervised learning with tabular data presents unique challenges, including low data sizes, the absence of structural cues, and heterogeneous features spanning both categorical and continuous domains. Unlike vision and language tasks, where models can exploit inductive biases in the data, tabular data lacks inherent positional structure, hindering the effectiveness of self-attention mechanisms. While recent transformer-based models like TabTransformer, SAINT, and FT-Transformer (which we refer to as 3T) have shown promise on tabular data, they typically operate without leveraging structural cues such as positional encodings (PEs), as no prior structural information is usually available. In this work, we find both theoretically and empirically that structural cues, specifically PEs can be a useful tool to improve generalization performance for tabular transformers. We find that PEs impart the ability to reduce the effective rank (a form of intrinsic dimensionality) of the features, effectively simplifying the task by reducing the dimensionality of the problem, yielding improved generalization. To that end, we propose Tab-PET (PEs for Tabular Transformers), a graph-based framework for estimating and inculcating PEs into embeddings. Inspired by approaches that derive PEs from graph topology, we explore two paradigms for graph estimation: association-based and causality-based. We empirically demonstrate that graph-derived PEs significantly improve performance across 50 classification and regression datasets for 3T. Notably, association-based graphs consistently yield more stable and pronounced gains compared to causality-driven ones. Our work highlights an unexpected role of PEs in tabular transformers, revealing how they can be harnessed to improve generalization.

Obtaining human-readable symbolic formulas via genetic programming-based symbolic distillation of a deep neural network trained on the target dataset presents a promising yet underexplored path towards explainable artificial intelligence (XAI); however, the standard pipeline frequently yields symbolic models with poor predictive accuracy. We identify a fundamental misalignment in functional complexity as the primary barrier to achieving better accuracy: standard Artificial Neural Networks (ANNs) often learn accurate but highly irregular functions, while Symbolic Regression typically prioritizes parsimony, often resulting in a much simpler class of models that are unable to sufficiently distill or learn from the ANN teacher. To bridge this gap, we propose a framework that actively regularizes the teacher's functional smoothness using Jacobian and Lipschitz penalties, aiming to distill better student models than the standard pipeline. We characterize the trade-off between predictive accuracy and functional complexity through a robust study involving 20 datasets and 50 independent trials. Our results demonstrate that students distilled from smoothness-regularized teachers achieve statistically significant improvements in R^2 scores, compared to the standard pipeline. We also perform ablation studies on the student model algorithm. Our findings suggest that smoothness alignment between teacher and student models is a critical factor for symbolic distillation.

Symbolic regression (SR) algorithms learn, from a training set, a concise closed-form function that relates the predictors (features) to the outcomes (labels). Many successful SR approaches, including those based on genetic programming and other evolutionary techniques, rely on stochastic search over a large hypothesis space. While this stochasticity often produces strong performance, it can also lead to sensitivity to perturbations in the training data, resulting in variability across learned models. Understanding and characterizing this behavior is important for assessing reliability and generalization. This paper studies the theoretical relationship between algorithmic stability and generalization in SR. We present the first stability-based theoretical analysis of the generalization gap for SR algorithms. We introduce two stability metrics, the add-one point-wise gap and the add-one training gap, which can be estimated empirically. Using these metrics, we derive a bound on the generalization gap and show how it relates to generalization theory. We provide empirical evidence across multiple SR algorithms, hyperparameter settings, and datasets demonstrating that the proposed stability metrics track and explain generalization behavior. Algorithms and configurations that exhibit greater stability tend to achieve smaller generalization gaps. Finally, we conduct ablation studies to validate the robustness and explanatory power of the proposed metrics.

Status update systems require the timely collection of sensing information for which deploying multiple sensors/servers to obtain diversity gains is considered as a promising solution. In this work, we construct an absorbing Markov chain (AMC) to exactly model Age of Information (AoI) in a discrete-time dual-queue (DTDQ) status update system with generate-at-will (GAW) status updates, discrete phase-type (DPH-type) distributed service times and transmission freezing. Specifically, transmission is frozen for a certain number of slots following the initiation of a transmission, after which one of the two servers is allowed to simultaneously sample the monitored physical process and transmit a status update packet, according to the availabilities and priorities of the two servers. Based on the discrete-time AMC, we provide the exact distributions of both AoI and peak AoI (PAoI), enabling the derivation of arbitrary order moments. In addition, we analytically study the role of freezing using several typical service time distributions, including geometric, uniform, negative binomial, and triangular distributions. The introduction of freezing for DTDQ systems is demonstrated to be significantly beneficial in reducing the mean AoI for various service time distributions. Additionally, we study the impact of the statistical parameters of the service times and heterogeneity between the two servers on the freezing gain, i.e., reduction in mean AoI attained with optimum freezing policies.

We study the two-user broadcast channel with degraded message sets and derive second-order achievability rate regions. Specifically, the channel noises are not necessarily Gaussian and we use spherical codebooks for both users. The weak user with worse channel quality applies nearest neighbor decoding by treating the signal of the other user as interference. For the strong user with better channel quality, we consider two decoding schemes: successive interference cancellation (SIC) decoding and joint nearest neighbor (JNN) decoding. We adopt two performance criteria: separate error probabilities (SEP) and joint error probability (JEP). Under our analysis, SIC and JNN decoding share the same second-order achievable rate region despite the fact that JNN decoding often yields better performance in other multiterminal problems. Furthermore, we generalize our results to the case with quasi-static fading and show that the asymptotic notion of outage capacity region is an accurate performance measure even at finite blocklengths.

This work considers the problem of remote estimation of Wiener processes and proposes a sample preprocessing method to ensure the convergence of the estimation distortion. Specifically, the autocorrelation of the Wiener process is exploited to counteract the effect of strong quantization noise arising from the linearly increasing variance over time. We first derive the exact expression for the convergent mean squared error (MSE) without considering transmission outages to explain the proposed preprocessing method. Then, the analysis is extended to more complex and general scenarios with outages. Based on the derived MSE, the quantization precision, the sampling interval, and the transmission time of a single piece of update information are optimized individually. We further give two algorithms to obtain two global suboptimal MSEs for practical cases considering low thresholds of quantization precision and sampling interval, following a demonstration of the unsolvability of the joint optimization. The numerical results reveal that dynamic distortion plays a greater role than static distortion due to the fast-varying nature of the Wiener process, which also verifies the effectiveness of the proposed preprocessing method in controlling the quantization error.

Genetic Programming Symbolic Regression (GPSR) generates mathematical expressions to model input-output relationships using an evolutionary process. A significant challenge in GPSR lies in the repeated evaluation of entire expressions or their sub-expression, which inflates computational runtime. To address this inefficiency, caching mechanisms have been employed to reduce redundant computations. However, prior studies predominantly employ a single caching strategy, offering limited insights into their comparative performance or memory-runtime trade-offs. In this paper, we present a comprehensive analysis of caching mechanisms for GPSR on synthetic and real-world datasets. We also include an empirical study of key-value usage frequencies under an infinitely large cache, offering insights into optimal cache sizing. Furthermore, we provide actionable guidelines for configuring caching strategies based on computational and memory constraints. Our findings indicate that complex caching mechanisms necessitate a minimum cache size to achieve computational time reductions. Conversely, lightweight caching strategies, such as Least Recently Used (LRU) and, notably, First-In-First-Out (FIFO), can significantly decrease computation time for fitness evaluations, which are a substantial component of the overall runtime.

Symbolic Regression (SR) algorithms select expressions based on prediction performance while also keeping the expression lengths short to produce explainable white box models. In this context, SR algorithms can be evaluated by measuring the extent to which the expressions discovered are Pareto-optimal, in the sense of having the best R-squared score for a given expression length. This evaluation is most commonly done based on relative performance, in the sense that an SR algorithm is judged on whether it Pareto-dominates other SR algorithms selected in the analysis, without any indication on efficiency or attainable limits. In this paper, we explore absolute Pareto-optimal (APO) solutions instead, which have the optimal tradeoff between the multiple SR objectives, for 34 datasets in the widely-used SR benchmark, SRBench, by performing exhaustive search. Additionally, we include comparisons between eight numerical optimization methods. We extract, for every dataset, an APO front of expressions that can serve as a universal baseline for SR algorithms that informs researchers of the best attainable performance for selected sizes. The APO fronts provided serves as an important benchmark and performance limit for SR algorithms and is made publicly available at: https://github.com/kentridgeai/SRParetoFronts

In this work, we propose a novel approach that combines the strengths of FEAT and TabNet through knowledge distillation (KD), which we term FEAT-KD. FEAT is an intrinsically interpretable machine learning (ML) algorithm that constructs a weighted linear combination of concisely-represented features discovered via genetic programming optimization, which can often be inefficient. FEAT-KD leverages TabNet’s deep-learning-based optimization and feature selection mechanisms instead. FEAT-KD finds a weighted linear combination of concisely-represented, symbolic features that are derived from piece-wise distillation of a trained TabNet model. We analyze FEAT-KD on regression tasks from two perspectives: (i) compared to TabNet, FEAT-KD significantly reduces model complexity while retaining competitive predictive performance, effectively converting a black-box deep learning model into a more interpretable white-box representation, (ii) compared to FEAT, our method consistently outperforms in prediction accuracy, produces more compact models, and reduces the complexity of learned symbolic expressions. In addition, we demonstrate that FEAT-KD easily supports multi-target regression, in which the shared features contribute to the interpretability of the system. Our results suggest that FEAT-KD is a promising direction for interpretable ML, bridging the gap between deep learning’s predictive power and the intrinsic transparency of symbolic models.

Estimating the confidence of deep neural network predictions is crucial for safe deployment in high-stakes applications. While softmax probabilities are commonly used, they are often poorly calibrated, and existing calibration methods have been shown to be detrimental to failure prediction. In this paper, we propose using information-theoretic measures to estimate prediction confidence in a post-hoc manner, without modifying network architecture or training. Specifically, we compare three pointwise information (PI) measures: pointwise mutual information (PMI), pointwise $\mathcal{V}$-information (PVI), and the recently proposed pointwise sliced mutual information (PSI). These measures are theoretically grounded in their relevance to predictive uncertainty, with properties such as invariance, convergence rates, and sensitivity to geometric attributes like margin and intrinsic dimensionality. Through extensive experiments on benchmark computer vision models and datasets, we find that PVI consistently outperforms PMI, PSI and existing post-hoc baselines in failure prediction across metrics. For confidence calibration, PVI matches the performance of temperature-scaled softmax, which is already regarded as a highly effective baseline. This indicates that PVI achieves superior failure prediction without compromising its calibration performance. This aligns with our theoretical insights, which suggest that PVI offers the most balanced trade-offs.

In this paper, we consider the problem of remote estimation of Wiener processes and propose a sample preprocessing method to ensure the convergence of estimation distortion. The autocorrelation of the Wiener process is exploited to counteract the effect of strong quantization noise arising from the linearly increasing variance over time. We first derive the convergent expression for the mean squared error without considering transmission outages to explain the proposed preprocessing method. Then, the analysis is extended to more complex and general scenarios with outages. Based on the analyses, the quantization precision and the sampling interval are optimized individually.

Symbolic Regression (SR) algorithms are powerful machine learning tools that discover mathematical expressions from data, but their evaluation is often hindered by the computational cost of optimizing numerical parameters (also called constants) within candidate expressions. To address this limitation, we introduce POVE (PreOptimized Vault of Expressions), a comprehensive repository of preoptimized symbolic expressions where numerical parameters have been efficiently computed using an established optimization technique in SR (i.e., BFGS) on widely used SR regression problems (i.e., SRBench). In addition to optimized constants, POVE stores the corresponding fitness values, quantifying the accuracy of each expression on its respective regression problem, allowing researchers to directly retrieve both optimized expressions and their precomputed performance metrics from memory (e.g., hash tables or dictionaries). By eliminating the need for computationally expensive numerical optimization steps, POVE enables significantly faster evaluation, large-scale benchmarking, and extensive hyperparameter analysis. It provides a structured and standardized foundation for comparing SR algorithms, assessing their consistency across large numbers of random seeds and investigating the impact of hyperparameters without the overhead of numerical parameter optimization. By offering a collection of precomputed expressions, parameters, and fitness values across diverse regression problems, POVE enhances reproducibility, accelerates experimental workflows, and enables scalable SR research. It serves as a valuable resource for both developing novel SR methodologies and improving existing algorithms by providing a reliable reference for optimal expression discovery. With POVE, SR research can shift away from costly optimization, enabling deeper algorithmic exploration and more comprehensive systematic evaluation. POVE also lowers the barrier to entry for SR research and makes large-scale evaluation significantly more accessible. POVE is publicly available at: https://github.com/kentridgeai/POVE

High-Performance Optical Camera Communications (HP-OCC) extends conventional Optical Camera Communication (OCC) by combining single-photon avalanche diode (SPAD) sensors with on-sensor edge processing. This enables highspeed optical communication and centimetre-level localization within a single platform, offering a compelling optical-domain alternative for Integrated Sensing and Communication (ISAC) in RF-restricted or congested environments.

The increasing demands of next-generation wireless applications are straining the limited sub-6 GHz spectrum. While terahertz wave (T-Wave) offers expanded bandwidths for 6G, its short range, increased energy use, and high costs limit viability. Optical Camera Communications (OCC) is a practical alternative, using image sensors to simultaneously decode multiple spatially-separated optical streams. OCC offers T-Wave-like directional communication, with added benefits such as signal origin verification and precise localization, at a higher technology readiness level. As an example, OCC can support applications like vehicle-to-everything (V2X), enabling ranging, lane-level positioning, and pedestrian safety. We also validated OCC's viability in dense, high-throughput scenarios through prototypes built with COTS components.

Mutual Information (MI) based feature selection makes use of MI to evaluate each feature and eventually shortlists a relevant feature subset, in order to address issues associated with high-dimensional datasets. Despite the effectiveness of MI in feature selection, we notice that many state-of-the-art algorithms disregard the so-called unique relevance (UR) of features, which is a necessary condition for the optimal feature subset. In our study of five representative MI based feature selection (MIBFS) algorithms, we find that all of them underperform as they ignore the UR of features and arrive at a suboptimal selected feature subset. We point out that the heart of the problem is that all these MIBFS algorithms follow the criterion of Maximize Relevance with Minimum Redundancy (MRwMR), which does not explicitly target UR. This motivates us to augment the existing criterion with the objective of boosting unique relevance (BUR), leading to a new criterion called MRwMR-BUR. Depending on the task being addressed, MRwMR-BUR has two variants, termed MRwMR-BUR-KSG and MRwMR-BUR-CLF, which estimate UR differently. MRwMR-BUR-KSG estimates UR via a nearest-neighbor based approach called the KSG estimator and is designed for three major tasks: (i) Classification Performance (i.e., higher classification accuracy). (ii) Feature Interpretability (i.e., a more precise selected feature subset for practitioners to explore the hidden relationship between features and labels). (iii) Classifier Generalization (i.e., the selected feature subset generalizes well to various classifiers). MRwMR-BUR-CLF estimates UR via a classifier based approach. It adapts UR to different classifiers, further improving the competitiveness of MRwMR-BUR for classification performance oriented tasks. The performance of MRwMR-BUR-KSG and MRwMR-BUR-CLF is validated via experiments using six public datasets and four popular classifiers. Specifically, as compared to MRwMR, the proposed MRwMR-BUR-KSG improves the test accuracy by 2% – 3% with 25% – 30% fewer features being selected, without increasing the algorithm complexity. MRwMR-BUR-CLF further improves the classification performance by 3.8% – 5.5% (relative to MRwMR), and it also outperforms three popular classifier dependent feature selection methods.

Recently, underwater wireless optical communication (UWOC) has emerged to support the high data rate requirements of oceanic exploration. In this paper, we propose an accurate and closed-form UWOC channel model to understand the effects of dynamic ocean environment on optical signal propagation. The model takes into account the impairments induced by oceanic path-loss, oceanic turbulence, pointing error loss and link interruption due to angle-of-arrival (AoA) fluctuations jointly. We further derive analytical expressions for various outage performance metrics. To boost the system robustness to dynamic ocean environment, we design a probabilistic shaping (PS)-based strategy with unipolar pulse amplitude modulation (PAM), which maximizes the ergodic constellation constrained capacity. Furthermore, considering the limitation of computational resources in real ocean environment, we simplify the PS-based scheme to alleviate the problem. Numerical results verify the accuracy of the proposed channel model and the outage performance analysis. Moreover, the simplified PS-based unipolar M-PAM scheme is validated to be a promising solution for the development and deployment of high speed adaptive UWOC systems.

We introduce a conceptually simple yet effective method to create small, compact decision trees - by using splits found via Symbolic Regression (SR). Traditional decision tree (DT) algorithms partition a dataset on axis-parallel splits. When the true boundaries are not along the feature axes, DT is likely to have a complicated structure and a dense decision boundary. In this paper, we introduce SR-Enhanced DT (SREDT) - a method which utilizes SR to increase the richness of the class of possible DT splits. We evaluate SREDT on both synthetic and real-world datasets. Despite its simplicity, our method produces surprisingly small trees that outperform both DT and oblique DT (ODT) on supervised classification tasks in terms of accuracy and F-score. We show empirically that SREDTs decrease inference time (compared to DT and ODT) and argue that they allow us to obtain more explainable descriptions of the decision process. SREDT also performs competitively against state-of-the-art tabular classification methods, including tree ensembles and deep models. Finally, we introduce a local search mechanism to improve SREDT and evaluate it on 56 PMLB datasets. This mechanism shows improved performance on 77.2% of the datasets, outperforming DT and ODT. In terms of F-Score, local SREDT outperforms DT and ODT in 82.5% and 73.7% of the datasets respectively and in terms of inference time, local SREDT requires 25.8% and 26.6% less inference time than DT and ODT respectively.

Symbolic Regression (SR) is an approach which learns a closed-form function relating the predictors to the outcome in a dataset. Datasets are often multi-level (MuL), meaning that certain features can be used to split data into groups for analysis (we refer to these features as levels). The advantage of viewing datasets as MuL is that we can exploit the high similarity of data within a group. SR is well-suited for MuL datasets, in which the learnt function structure serves as ‘shared information’ between the groups while the learnt parameter values capture the unique relationships within each group. In this context, this paper makes three contributions: (i) We design an algorithm, Multi-level Symbolic Regression (MSR), which runs multiple parallel SR processes for each group and merges them to produce a single function structure. (ii) To tackle datasets that are not explicitly MuL, we develop a metric termed MLICC to select the best feature to serve as a level. (iii) We also release MSRBench, a database of MuL datasets (synthetic and real-world) which we developed and collated, that can be used to evaluate MSR. Our results and ablation studies demonstrate that MSR achieves a higher recovery rate and lower error on MSRBench compared to SOTA methods for SR and MuL datasets.

State-of-the-art Symbolic Regression (SR) algorithms employ evolutionary techniques to fulfill the task of generating a concise mathematical expression that fulfills an objective. A common objective is to fit to a dataset of input-output pairs, in which the faithfulness of a predicted output to the actual output is used as the fitness measure (e.g., R-squared). In many datasets, among the candidate expressions evaluated, there tends to be a large number of pseudo-expressions, referring to expressions that achieve high fitness but do not resemble the ground-truth equation. These pseudo-expressions decrease the equation recovery rate of SR algorithms. To formulate novel fitness measures that function as better discriminators of the ground-truth equation, we introduce a novel meta-learning approach to SR, MetaSR, in which we utilize SR itself to discover new fitness measures that can be complex combinations of existing base measures. In this paper, we focus on frequency-aware symbolic regression, where the fitness can depend on the frequency domain. We show that our new fitness measures better discriminate the ground-truth equation from other equations and demonstrate the improved performance of our method against existing algorithms.

Conventional communication systems focus on re-covering the messages sent by the transmitter at the receiver, by undoing the errors introduced by the channel. In semantic communication, the goal is instead to preserve the semantics (i.e., meaning) of the intended message$X$. A well-known framework adopted by the literature in modelling semantic communication is task-oriented communication. There, an encoder generates a feature representation$Z$(e.g., a trained neural network) to transmit across the channel to fulfill a certain task (e.g., classification with labels$Y$). This naturally leads to the study of the information bottleneck (IB) principle - which proposes reducing the mutual information$I (X; Z)$(compression) while simultaneously maxi-mizing$I (Z; Y)$(fitting). Although this objective seems initially meaningful, we posit that both the standard task-oriented setting for studying semantic communication and the IB approach may not be optimal. In this paper, we first propose a novel paradigm of multi-task generalizable communication, where, at test time, the messages may originate from a different unseen classification task compared to those during training. We intuitively reason that the multi-task generalizable setting is more feasible and relevant in the context of real-world semantic communication, compared to task-oriented communication. Next, we propose a Reconstruction Loss Aware (RLA) approach, which yields better feature encodings that are more generalizable towards unseen tasks. We empirically observe that, in the proposed paradigm, the IB principle is not optimal. We also demonstrate that RLA is better (15%-20% higher accuracy) compared to a benchmark approach for task-oriented communication, for diverse non-overlapping unseen tasks.

Symbolic Regression (SR) is the task of finding a concise white-box mathematical expression that fulfills a given machine learning (ML) objective. In this work, we introduce the first-of-its-kind SR-based ensemble combiner (SyREC) for ML which utilizes the quasi-arithmetic mean (parameterized by a function$f$) as an ensemble combiner and discovers$f$via SR. Our Sy REC demonstrates advantages over existing ensemble combiners, i.e., averaging methods and meta-learners. Compared to averaging methods, Sy REC allows for increased combiner complexity via exploring a large function class and provides a learning process to tune the ensemble combiner to the specific dataset. Compared to meta-learners, SyREC preserves important ensemble properties, like idempotency, monotonicity and boundedness, which produce predictions more consistent with the base models. We note SyREC produces a white-box ensemble combiner that lies in the intersection of both categories of existing combiners, addressing the weaknesses while capturing the strengths of each category. To evaluate Sy REC, we present experiments on 16 open-source PMLB datasets and commonly used base models, including a large variety of experiments and analyses across different settings: (i) regression and classification tasks, (ii) equally weighted combiners and custom-weighted combiners, (iii) homogeneous and heterogeneous ensembles, (iv) sequential and parallel ensembles. We find that in all these settings, SyREC shows consistent improvement over existing ensembling approaches. This indicates that SyREC is a robust ensemble combiner, which produces explainable and consistent ensemble predictions.

Most entropy measures depend on the spread of the probability distribution over the sample space |X|, and the maximum entropy achievable scales proportionately with the sample space cardinality |X|. For a finite |X|, this yields robust entropy measures which satisfy many important properties, such as invariance to bijections, while the same is not true for continuous spaces (where |X|=infinity). Furthermore, since R and R^d (d in Z+) have the same cardinality (from Cantor's correspondence argument), cardinality-dependent entropy measures cannot encode the data dimensionality. In this work, we question the role of cardinality and distribution spread in defining entropy measures for continuous spaces, which can undergo multiple rounds of transformations and distortions, e.g., in neural networks. We find that the average value of the local intrinsic dimension of a distribution, denoted as ID-Entropy, can serve as a robust entropy measure for continuous spaces, while capturing the data dimensionality. We find that ID-Entropy satisfies many desirable properties and can be extended to conditional entropy, joint entropy and mutual-information variants. ID-Entropy also yields new information bottleneck principles and also links to causality. In the context of deep learning, for feedforward architectures, we show, theoretically and empirically, that the ID-Entropy of a hidden layer directly controls the generalization gap for both classifiers and auto-encoders, when the target function is Lipschitz continuous. Our work primarily shows that, for continuous spaces, taking a structural rather than a statistical approach yields entropy measures which preserve intrinsic data dimensionality, while being relevant for studying various architectures.

In this paper, we study the memorization and generalization behaviour of deep neural networks (DNNs) using sliced mutual information (SMI), which is the average of the mutual information (MI) between one-dimensional random projections. We argue that the SMI between features in a DNN ($T$) and ground truth labels ($Y$), $SI(T;Y)$, can be seen as a form of usable information that the features contain about the labels. We show theoretically that $SI(T;Y)$ can encode geometric properties of the feature distribution, such as its spherical soft-margin and intrinsic dimensionality, in a way that MI cannot. Additionally, we present empirical evidence showing how $SI(T;Y)$ can capture memorization and generalization in DNNs. In particular, we find that, in the presence of label noise, all layers start to memorize but the earlier layers stabilize more quickly than the deeper layers. Finally, we point out that, in the context of Bayesian Neural Networks, the SMI between the penultimate layer and the output represents the worst case uncertainty of the network’s output.

When deploying deep learning models such as convolutional neural networks (CNNs) in safety-critical domains, it is important to understand the predictions made by these black-box models. While many different approaches have been taken to improve the interpretability of deep models, most methods lack theoretical properties, making it hard to justify the correctness of the explanations provided. In this paper, we take an information-theoretic approach to understand why CNNs make their predictions. Building upon sliced mutual information, we propose pointwise sliced mutual information (PSI) as a tool for measuring the amount of useful information that a feature has about the label for a single instance. We theoretically justify the use of PSI for explaining predictions made by CNNs through the connection with margin. We show that PSI works as an explainability tool in two ways: (i) Fiber-wise PSI constructs a saliency map that highlights regions in the image which are important in predicting the labels; (ii) Sample-wise PSI provides confidence scores for predictions on the labels.

Most approaches to resource allocation in energy harvesting systems for Internet-of-Things (IoT) networks do not consider real-time periodic task allocation with Quality of Service (QoS). This article studies the offline 2-D optimization problem for allocating randomly harvested energy flowing causally between slots into different real-time periodic tasks on an IoT device. We formulate an energy allocation problem, for tasks with different energy costs and requested QoS, which aims to maximize a convex reward function subject to energy causality (EC), energy saturation (ES) and task executable (TE) constraints within a certain length of time. We decouple the optimization problem into two subproblems after analysis. First, we propose a novel method to allocate energy to slots based on the Karush–Kuhn–Tucher conditions only considering the EC & ES constraints. The proposed method outperforms the state-of-the-art “Tunnel Policy,” based on geometric programming. Next, an adaption is made to satisfy the TE constraints by allocating in the original constant power slots directly without iteratively checking the wasted energy. Finally, the energy already allocated to slots is put into tasks to complete the 2-D allocation. The effectiveness of the proposed methods and task framework are validated by extensive experiments.

The process of demodulating an unknown wireless communication signal without knowledge of the channel state and modulation type is called the dual-blind demodulation problem. We focus on solving the dual-blind demodulation problem in the presence of multipath fading and noise. Traditional blind receivers have different functional blocks to preprocess the incoming signal and recognize the modulation type. However, the independence among these blocks may limit performance. In this paper, we propose a dual-mode equalizer combined with a modulation classifier with a loop evaluation structure, called the automatic modulation classification (AMC) loop. We also introduce an AMC algorithm with a novel cluster-to-constellation (c2c) distance. Via experiments, we show that the proposed loop structure achieves better demodulation and classification accu-racy in a dual-blind scenario than (i) the traditional approach without the loop structure, and (ii) loop structures with alternate AMC algorithms. We also show that the proposed novel AMC-Loop structure with an AMC based on c2c distance is crucial for good performance via an ablation study.

Along with the practical success of deep neural networks, several theories have been proposed to explain their excellent generalization behaviour. One such theory is information bottleneck, using mutual information (MI) as a measure to understand the learning dynamics of these black-box models. However, estimating MI in high dimensions and in deterministic settings is problematic, often resulting in widely varying estimates for different estimators. This paper takes an alternative approach to analyze the behaviour of deep models by using a recently proposed information measure known as sliced mutual information (SMI), which is more computationally efficient to estimate than MI in high dimensions. We theoretically connect SMI to the classifier margin, thereby showcasing its ability to encode geometric properties of the feature distribution. We also study SMI empirically and demonstrate that the SMI between the hidden layer and the labels encodes information about the network’s ability to predict labels correctly.

This article performs a unified analysis of three coordinated multipoint (CoMP) transmission strategies in the downlink of mmWave cellular networks, including the fixed-number base station (BS) cooperation (FNC), the fixed-region BS cooperation (FRC), and the interference-aware BS cooperation (IAC). We first develop a comprehensive framework for CoMP operation in cellular networks, and investigate the network performance under a Poisson point process (PPP) model together with mmWave spectrum. To show what fraction of users in the network achieve target reliability for a given signal to interference-plus-noise ratio (SINR)/signal-to-interference ratio (SIR), we derive the SINR/SIR meta distributions, and further obtain the coverage probability as well as mean local delay for the three cooperation strategies. A pivotal intermediate step to compute the performance metrics is the derivation of joint distributions of distances between a typical user and cooperative BSs. Our analysis demonstrates that parameters of blockage have a significant influence on the network performance for the three CoMP schemes. We find that the FRC scheme makes more users achieve the given link reliability for the scenario with a low density of BSs, while the IAC scheme provides better performance for the network with a high density of BSs. Moreover, the optimal CoMP scheme can be approximately selected by considering the nearest distance from the serving BS to user and the radius of the approximate line-of-sight (LoS) region in the cellular networks.

Mobile crowdsensing (MCS) is an emerging human-powered service for large-scale sensing and data collection. Most existing frameworks for controlling MCS services focus on a system-initiated setting where the crowdsourcer selects a subset of contributors and incentivizes them to collect the sensing data after the queries from the consumers arrive at the system. Such a system-initiated setting may cause large delays for the system to answer the consumers’ queries, which is not suitable for many real-time sensing applications. In this article, we propose contributor-initiated proactive sensing (CIPS) frameworks for MCS where the sensing data are collected in a proactive manner before the consumers’ queries arrive. In CIPS, the consumers can get answers about their queries with virtually no delay, which opens the door for MCS to many real-time applications. We first propose a centralized algorithm called C-CIPS as a benchmark for sensing scheduling by assuming the contributors are truthful and the consumer queries are knowna priori. Next, we propose a distributed algorithm called D-CIPS to deal with strategic contributors and unknown consumer queries. Through rigorous theoretical analysis, we prove that both C-CIPS and D-CIPS can achieve near-optimal solutions. Furthermore, D-CIPS is proved to be truthful. Through comprehensive simulations with both synthetic and real-world data sets, we demonstrate the effectiveness of the proposed algorithms.

We study segmented edit channels where the channel input is divided into disjoint segments, and each segment suffers at most one error, either a deletion or an insertion. The model was first introduced by Liu and Mitzenmacher [2010] over the binary alphabet, and was extended for the q-ary alphabet by Abroshan et al. [2018]. In this work, we first propose an efficient construction for segments with less redundancy than previous works, hence significantly improving the redundancy over the entire sequence, for any q-ary alphabet where$q$≥ 3. Additionally, motivated by the applications of constrained codes in DNA-based data storage systems and energy harvesting communication channels, to reduce the probability of having errors, we also impose certain weight constraints in every segment instead of over the whole sequence. In particular, for DNA storage systems, besides error correction capability, our coding method guarantees that all segments in every codeword are almost GC-balanced.

What makes a classifier have the ability to generalize? There have been a lot of important attempts to address this question, but a clear answer is still elusive. Proponents of complexity theory find that the complexity of the classifier's function space is key to deciding generalization, whereas other recent work reveals that classifiers which extract invariant feature representations are likely to generalize better. Recent theoretical and empirical studies, however, have shown that even within a classifier's function space, there can be significant differences in the ability to generalize. Specifically, empirical studies have shown that among functions which have a good training data fit, functions with lower Kolmogorov complexity (KC) are likely to generalize better, while the opposite is true for functions of higher KC. Motivated by these findings, we propose, in this work, a novel measure of complexity called Kolmogorov Growth (KG), which we use to derive new generalization error bounds that only depend on the final choice of the classification function. Guided by the bounds, we propose a novel way of regularizing neural networks by constraining the network trajectory to remain in the low KG zone during training. Minimizing KG while learning is akin to applying the Occam's razor to neural networks. The proposed approach, called network-to-network regularization, leads to clear improvements in the generalization ability of classifiers. We verify this for three popular image datasets (MNIST, CIFAR-10, CIFAR-100) across varying training data sizes. Empirical studies find that conventional training of neural networks, unlike network-to-network regularization, leads to networks of high KG and lower test accuracies. Furthermore, we present the benefits of N2N regularization in the scenario where the training data labels are noisy. Using N2N regularization, we achieve competitive performance on MNIST, CIFAR-10 and CIFAR-100 datasets with corrupted training labels, significantly improving network performance compared to standard cross-entropy baselines in most cases. These findings illustrate the many benefits obtained from imposing a function complexity prior like Kolmogorov Growth during the training process.

Freshness of information is an important requirement in many real-time applications. It is measured by a metric called the age of information (AoI), defined as the time elapsed since the generation of the last successful update received by the destination. We consider M sources (users) updating their statuses to a base station (BS) over a block-fading multiple access channel (MAC). At the start of each fading block, the BS acquires perfect information about channel power gain realizations of all the users in the block. Using this information, a centralized scheduling policy at the BS decides, for each block, which users should transmit and with what powers. The objective is to minimize a long-term weighted average AoI across all users subject to a long-term average power constraint at each user. Under this setting, we first consider a simple time-division multiple access (TDMA) strategy, in which at most one user can transmit in a slot, and propose a simple age-independent stationary randomized policy (AI-SRP). The AI-SRP makes transmission decisions based on the channel power gain realizations, without considering the AoIs. We then consider a more general non-orthogonal multiple access (NOMA) strategy, in which any number of users can transmit in a slot subject to capacity constraints of the MAC and propose an AI-SRP. The AI-SRPs we propose are optimal solutions to appropriate optimization problems. We show that the minimum achievable weighted average AoIs across the users under the proposed AI-SRPs are at most two times those of the respective optimal policies under TDMA and NOMA strategies.

Constrained coding is used widely in digital communication and storage systems. In this article, we study a generalized sliding window constraint called the skip-sliding window. A skip-sliding window (SSW) code is defined in terms of the length L of a sliding window, skip length J, and cost constraint E in each sliding window. Each valid codeword of length L + kJ is determined by k+1 windows of length L where window i starts at (iJ + 1)th symbol for all non-negative integers i such that i ≤ k; and the cost constraint E in each window must be satisfied. SSW coding constraints naturally arise in applications such as simultaneous energy and information transfer, and SSW codes are also potential candidates for visible light communications. In this work, two methods are given to enumerate the size of SSW codes and further refinements are made to reduce the enumeration complexity. Using the proposed enumeration methods, the noiseless capacity of binary SSW codes is determined and some useful observations are made, such as the fact that SSW codes provide greater capacity than certain related classes of constrained codes. Moreover, we provide noisy capacity bounds for SSW codes.

Recent advances in underwater networking exploit the large propagation delays in underwater channels to schedule transmissions which increase the performance of underwater acoustic sensor networks (UASNs). The underwater channel is broadcast in nature so it supports broadcast and multicast transmissions. In this paper, we discuss novel scheduling strategies, based on TDMA (Time Division Multiple Access), for UASNs where packets may be bound for multiple destinations. The main contributions are to establish an upper bound on the throughput of multicast networks, in which each packet has the same number of intended destinations, by exploiting large propagation delays, and explore network topologies that can achieve this bound. As an example, we study the throughput of unicast and multicast ring networks, including the properties of optimal, valid, perfect and fair transmission schedules. Further, several algorithms to find fair and optimal schedules for unicast and multicast ring networks are presented. Finally, we perform extensive simulations for uniform ring networks, as well as more general ring networks, in both noiseless and noisy underwater channels. Simulation results verify that the proposed algorithms can effectively determine the optimal schedules for ring networks, which achieve the maximum possible throughput and asymptotically approach the upper bound on the throughput of multicasting UASNs.

Colorectal cancer is among the top three most commonly occurring cancers worldwide, and around 30-40% of patients treated by curative intent surgery will experience cancer recurrence. Proactive prognostication would enable clinicians to better plan treatment modality and intensity, and follow-up frequency to reduce recurrence. Here, we study the application of machine learning models to predict cancer recurrence in a cohort of 904 post-resection colorectal cancer patients. We employ heterogeneous structured and temporal clinical features including demographic and diagnostic information, tumour stage and location details, biochemistry and molecular typing results, as well as surgical details and treatment parameters. We characterize the performance of multiple machine learning classifiers including logistic regression, support vector machine, gradient boosting and multi-layer perceptron on structured data. Our best model achieved a sensitivity of 80.7% and a specificity of 88.2%. This is comparable to and even exceeding the performance of carcinoembryonic antigen (CEA), a tumour marker commonly used in the clinic for colorectal cancer monitoring. We also demonstrate feasibility for accurate forecasting of recurrence up to 4 months in advance, as well as the possibility of predicting recurrence as early as 6 months post-surgery. Our results have positive implications for better management of colorectal cancer patients in the post-resection setting.

The problem of decoding an (n, k, d) error-correcting block code, where a k-bit message word is mapped to an n-bit codeword, can be cast as a single-label classification problem. While it has been observed that the performance of such single-label neural decoders closely approaches that of the corresponding maximum likelihood decoder (MLD), the number of output nodes increases exponentially with k, making it prohibitive to implement for large k. To address this issue, we explore classification based multi-label neural decoders, in which the number of output nodes increases linearly with k. We consider well-known linear and non-linear block codes, as well as concatenated block codes, which have applications in emerging wireless networks. Our study finds that (i) although the number of output nodes linearly increases with k in a multi-label decoder, it requires more hidden layers and nodes in each hidden layer than the corresponding single-label decoder to achieve its best performance, and (ii) although one can design a multi-label decoder with bit error rate matching that of the MLD, it leaves more blocks in error leading to a reduced performance in terms of block error rate. We also note that the performance of the proposed decoder for concatenated codes is at least as good as that of a natural decoding algorithm in which the inner code is first decoded using the MLD and then the outer code is decoded with a polynomial-time decoding algorithm.

Modern deep neural networks require a significant amount of computing time and power to train and deploy, which limits their usage on edge devices. Inspired by the iterative weight pruning in the Lottery Ticket Hypothesis, we propose DropNet, an iterative pruning method which prunes nodes/filters to reduce network complexity. DropNet iteratively removes nodes/filters with the lowest average post-activation value across all training samples. Empirically, we show that DropNet is robust across a wide range of scenarios, including MLPs and CNNs using the MNIST, CIFAR-10 and Tiny ImageNet datasets. We show that up to 90% of the nodes/filters can be removed without any significant loss of accuracy. The final pruned network performs well even with reinitialisation of the weights and biases. DropNet also achieves similar accuracy to an oracle which greedily removes nodes/filters one at a time to minimise training loss, highlighting its effectiveness.

There has been a growing interest in designing neural-network based decoders (or neural decoders in short) for communication systems. In the prior work, we cast the problem of decoding an (n, k) block code as a single-label classification problem, and it is shown that the performance of such single-label neural decoders closely approaches that of the corresponding maximum likelihood soft-decision (ML-SD) decoders. The main issue is that the number of output nodes of single-label neural decoders increases exponentially with k, making it prohibitive to decode a code with medium or large dimension. To address this issue, we first explore a multi-label classification based neural decoder for block codes, in which the number of output nodes increases linearly with k. The complexity of the multi-label neural decoder is lower, but the performance is still close to that of the ML-SD decoder. We also consider concatenating a high-rate short-length outer code with the original code as the inner code. The proposed concatenated decoding architecture consists of a multi-label neural decoder for the inner code and a single label neural decoder for the outer code. The results demonstrate that the concatenated decoding approach leads to better bit and block error performance as compared to a benchmark soft-decision decoder. We note that the overall size of the concatenated neural decoder is close to that of the single-label neural decoder.

Mutual Information (MI), a measure from information theory, is widely used in feature selection. Despite its great success, a promising feature property, namely the unique relevance (UR) of a feature, remains unexplored. In this paper, we improve the performance of mutual information based feature selection (MIBFS) by exploring the utility of unique relevance (UR). We provide a theoretical justification for the value of UR and prove that the optimal feature subset must contain all features with UR. Since existing MIBFS follows the criterion of Maximize Relevance with Minimum Redundancy (MRwMR) which ignores UR of features, we augment it to include the objective of boosting unique relevance (BUR). This leads to a new criterion for MIBFS, called MRwMR-BUR. We conduct experiments on six public datasets and the results indicate that MRwMR-BUR consistently outperforms MRwMR when tested with three popular classifiers. We believe this new insight can lead to new optimality bounds and algorithms.

Vital signs including heart rate, respiratory rate, body temperature and blood pressure, are critical in the clinical decision making process. Abnormal vital signs help to alert medical practitioners to potential health problems. Effective and long-range early prediction of vital signs may prevent adverse health outcomes and reduce cost. In this paper, we suggest a new approach called generative boosting, in order to effectively perform long-range early prediction of vital signs. Generative boosting consists of a generative model, to generate synthetic data for the next few time steps, and a predictive model, to directly make long-range predictions based on observed and generated data. We explore generative boosting via long short-term memory (LSTM) for both the predictive and generative models, leading to a scheme called generative LSTM (GLSTM). Our experiments indicate that GLSTM outperforms a diverse range of strong benchmark models, with and without generative boosting. As expected, the results also indicate that more accurately generated data leads to more accurate long-range predictions. In light of this, we use a mutual information based clustering algorithm to select a more representative dataset to train the generative model. This leads to significantly improved accuracy of the long-range prediction of high variation vital signs such as heart rate and systolic blood pressure. Overall, our best results indicate that the proposed method is able to predict heart rate and systolic blood pressure 20 minutes in advance, with a mean absolute percentage error of 7.41% and 6.17%, respectively.

We consider the design of efficient neural-network based algorithms, referred to as neural decoders, for decoding linear and non-linear block codes, such as Hamming and constant-weight codes, respectively. Our goal is to study the impact of the number of layers and the number of hidden nodes in each layer on the performance and generalization ability of neural decoders. Specifically, we want to find the minimum number of hidden layers and the minimum number of hidden nodes in each layer required to achieve or closely approach the performance of the optimal maximum-likelihood soft-decision (ML-SD) decoder for a given code. For the linear block codes studied, we find that when the block-length is n, a neural network with a single hidden layer with n hidden units is necessary and sufficient to achieve the performance of the ML-SD decoder. For the non-linear block codes studied, a single hidden layer with n nodes results in performance that closely approaches that of the ML-SD decoder. In both the cases, we find that training at a signal-to-noise ratio (SNR) of 0 dB gives fairly good generalization ability, meaning that the neural decoder trained at an SNR of 0 dB works well across a wide range of SNR values.

In energy harvesting (EH) communications, it is customary to use a battery to temporarily store harvested energy prior to using it for communication. In practice, these batteries suffer from degradation in the usable capacity when they are repeatedly charged after being partially discharged and vice versa. The capacity can be recovered by imposing the full-cycle constraint, which says that a battery must be charged only after it is fully discharged and vice versa. Further, practical batteries cannot be charged and discharged simultaneously. With the above constraints, we consider and compare EH communication systems under two cases: (a) the single-battery case and (b) the dual-battery case, in which the transmitters are equipped with a single battery of capacity 2B joules and two batteries, each having capacity of B joules, respectively. Under (a) and (b), our goal is to obtain the long-term average throughputs and throughput regions in a point-to-point (P2P) channel and a multiple access channel (MAC), respectively. For the P2P channel, we derive the optimal solution in the single-battery case, and propose optimal and suboptimal power allocation policies for the dual-battery case, assuming Bernoulli energy arrivals. Based on these policies, we obtain long-term average achievable throughput regions in MACs by jointly allocating rates and powers. From numerical simulations, we find that the optimal throughput in the dual-battery case is significantly higher than that in the single-battery case, although the total storage capacity in both cases is 2B joules.

Motivated by real-world machine learning applications, we analyze approximations to the non-asymptotic fundamental limits of statistical classification. In the binary version of this problem, given two training sequences generated according to two unknown distributions P1and P2, one is tasked to classify a test sequence which is known to be generated according to either P1or P2. This problem can be thought of as an analogue of the binary hypothesis testing problem but in the present setting, the generating distributions are unknown. Due to finite sample considerations, we consider the second-order asymptotics (or dispersion-type) tradeoff between type-I and type-II error probabilities for tests which ensure that (i) the type-I error probability for all pairs of distributions decays exponentially fast and (ii) the type-II error probability for a particular pair of distributions is non-vanishing. We generalize our results to classification of multiple hypotheses with the rejection option.

We apply the generalized sphere-packing bound to two classes of subblock-constrained codes. À la Fazeli et al. (2015), we make use of automorphisms to significantly reduce the number of variables in the associated linear programming problem. In particular, we study binary constant subblock-composition codes (CSCCs), characterized by the property that the number of ones in each subblock is constant, and binary subblock energy-constrained codes (SECCs), characterized by the property that the number of ones in each subblock exceeds a certain threshold. For CSCCs, we show that the optimization problem is equivalent to finding the minimum of N variables, where N is independent of the number of subblocks. We then provide closed-form solutions for the generalized sphere-packing bounds for t-error correcting CSCCs for t ∈ {1, 2, 3}. For SECCs, we provide closed-form solutions for the generalized sphere-packing bounds for single errors in certain special cases. We also obtain improved bounds on the optimal asymptotic rate for CSCCs and SECCs, and provide numerical examples to highlight the improvement.

Communication systems for multicasting information and energy simultaneously to more than one user are investigated. In the system under study, a transmitter sends the same message and signal to multiple receivers over distinct and independent channels. The fundamental communication limit under a received energy constraint, called the multicast capacity-energy function, is studied and a single-letter expression is derived. This is based on coding theorems for compound channels. The problem of receiver segmentation, where receivers are divided into related groups, is also considered.

We consider binary skip-sliding window (SSW) codes which satisfy certain weight constraints over a skip-sliding window. When on-off keying is employed, these weight constraints ensure real-time energy content in the transmitted signal. For a given energy requirement and battery size at an energy harvesting receiver, we investigate the maximum achievable rate using SSW codes which avoid energy outage at the receiver. The SSW codes generalize sliding window constrained (SWC) codes and subblock energy constrained (SEC) codes; we show that SSW codes with window length equal to twice the skip-length can outperform both SWC and SEC codes in terms of outage-constrained rate.

We consider the lossy transmission of a single source over parallel additive white Gaussian noise channels with independent quasi-static fading, which we term the lossy multi-connectivity problem. We assume that only the decoder has access to the channel state information. Motivated by ultra-reliable and low latency communication requirements, we are interested in the finite blocklength performance of the problem, i.e., the minimal excess-distortion probability of transmitting k source symbols over n channel uses. By generalizing non-asymptotic bounds by Kostina and Verdú for the lossy joint source-channel coding problem, we derive non-asymptotic achievability and converse bounds for the lossy multi-connectivity problem. Using these non-asymptotic bounds and under mild conditions on the fading distribution, we derive approximations for the finite blocklength performance in the spirit of second-order asymptotics for any discrete memoryless source under an arbitrary bounded distortion measure. Furthermore, in the achievability part, we analyze the performance of a universal coding scheme by modifying the universal joint source-channel coding scheme by Csiszár and using a generalized minimum distance decoder. Our results demonstrate that the asymptotic notions of outage probability and outage capacity are in fact reasonable criteria even in the finite blocklength regime. Finally, we illustrate our results via numerical examples.

Motivated by the idea of “transmitting energy and information simultaneously,” we investigate, in this paper, the impact of constraints on the amount of energy that individual symbols carry, i.e., minimum amplitude constraints. We consider a Gaussian mixture noise channel with both minimum and peak amplitude constraints. First, we prove that the capacity-achieving input has a discrete distribution with a finite number of probability mass points. Then, we further investigate the number and positions of the probability mass points for the capacity-achieving input. Specifically, when the interference is constant and known at both the transmitter and the receiver, it can be totally eliminated so that the channel operates like an AWGN channel. In this case, we give a theorem to determine whether the optimal input is binary. For more general cases, such as non-binary inputs and non-constant interference, we investigate optimal inputs and capacities via numerical computations.

In this paper, we revisit two multi-terminal lossy source coding problems: the lossy source coding problem with side information available at the encoder and one of the two decoders, which we term as the Kaspi problem (Kaspi, 1994), and the multiple description coding problem with one semi-deterministic distortion measure, which we refer to as the Fu-Yeung problem (Fu and Yeung, 2002). For the Kaspi problem, we first present the properties of optimal test channels. Subsequently, we generalize the notion of the distortion-tilted information density for the lossy source coding problem to the Kaspi problem and prove a non-asymptotic converse bound using the properties of optimal test channels and the well-defined distortion-tilted information density. Finally, for discrete memoryless sources, we derive refined asymptotics which includes the second-order, large, and moderate deviations asymptotics. In the converse proof of second-order asymptotics, we apply the Berry-Esseen theorem to the derived non-asymptotic converse bound. The achievability proof follows by first proving a type-covering lemma tailored to the Kaspi problem, then properly Taylor expanding the well-defined distortion-tilted information densities and finally applying the Berry-Esseen theorem. We then generalize the methods used in the Kaspi problem to the Fu-Yeung problem. As a result, we obtain the properties of optimal test channels for the minimum sum-rate function, a non-asymptotic converse bound and refined asymptotics for discrete memoryless sources. Since the successive refinement problem is a special case of the Fu-Yeung problem, as a by-product, we obtain a non-asymptotic converse bound for the successive refinement problem, which is a strict generalization of the non-asymptotic converse bound for successively refinable sources (Zhou, Tan, and Motani, 2017).

We consider a joint source channel coding (JSCC) problem in which we desire to transmit an arbitrary memoryless source over an arbitrary additive channel. We propose a mismatched coding architecture that consists of Gaussian codebooks for both the source reproduction sequences and channel codewords. The natural nearest neighbor encoder and decoder, however, need to be judiciously modified to obtain the highest communication rates at finite blocklength. In particular, we consider an unequal error protection scheme in which all sources are partitioned into disjoint power-type classes. We also regularize the nearest neighbor decoder so that an appropriate measure of the size of each power type class is taken into account in the decoding strategy. For such an architecture, we derive ensemble-tight second-order and moderate deviations results. Our first-order (optimal bandwidth expansion ratio) result generalizes the seminal results by Lapidoth (1996 and 1997). The dispersion of our JSCC scheme is a linear combination of the mismatched dispersions for the channel coding saddle-point problem by Scarlett, Tan, and Durisi (2017) and the rate-distortion saddle-point problem by the present authors, thus also generalizing these results.

The rate-distortion saddle-point problem considered by Lapidoth (1997) consists in finding the minimum rate to compress an arbitrary ergodic source when one is constrained to use a random Gaussian codebook and minimum (Euclidean) distance encoding is employed. We extend Lapidoth's analysis in several directions in this paper. First, we consider refined asymptotics. In particular, when the source is stationary and memoryless, we establish the second-order, moderate, and large deviation asymptotics of the problem. Second, by random Gaussian codebook, Lapidoth referred to a collection of random codewords, each of which is drawn independently and uniformly from the surface of an n -dimensional sphere. To be more precise, we term this as a spherical codebook. We also consider i.i.d. Gaussian codebooks in which each random codeword is drawn independently from a product Gaussian distribution. We derive the second-order, moderate, and large deviation asymptotics when i.i.d. Gaussian codebooks are employed. In contrast to the recent work on the channel coding counterpart by Scarlett, Tan, and Durisi (2017), the dispersions for spherical and i.i.d. Gaussian codebooks are identical. The ensemble excess-distortion exponents for both spherical and i.i.d. Gaussian codebooks are established for all rates. Furthermore, we show that the i.i.d. Gaussian codebook has a strictly larger excess-distortion exponent than its spherical counterpart for any rate greater than the ensemble rate-distortion function derived by Lapidoth.

Analyzing patients' health data using machine learning techniques can improve both patient outcomes and hospital operations. However, heterogeneous patient data (e.g., vital signs) and inefficient feature learning methods affect the implementation of machine learning-based patient data analysis. In this paper, we present a novel unsupervised deep learning-based feature learning (DFL) framework to automatically learn compact representations from patient health data for efficient clinical decision making. Real-world pneumonia patient data from the National University Hospital in Singapore are collected and analyzed to evaluate the performance of DFL. Furthermore, publicly available electroencephalogram data are extracted from the UCI Machine Learning Repository to test and support our findings. Using both data sets, we compare the performance of DFL to that of several popular feature learning methods and demonstrate its advantages.

Graphical models have been widely applied in distributed network computation problems such as inference in large-scale sensor networks. While belief propagation (BP) based on message passing is a powerful approach to solving such distributed inference problems, one major challenge, in the context of wireless sensor networks, is how to systematically address the trade-off between energy efficiency and inference performance. In this paper, we consider a distributed structure optimization problem and investigate the impacts of graphical model structure on energy consumption and inference performance. We first formulate the problem as a multi-objective constrained combinatorial optimization problem and prove its NP-hardness. Then, we propose an efficient distributed heuristic to solve the problem in polynomial time. Through extensive simulations, using both real-world sensor network data and synthetic data, we empirically evaluate our proposed graphical model structure optimization framework. The simulation results demonstrate that the graphical model constructed by the proposed framework can efficiently trades off the performance of the inference algorithm (measured by the mean squared error) with the energy consumed by the inference algorithm (measured by the energy used in communication). In addition, our proposed framework provides valuable insights for network designers on designing efficient model selection algorithms for distributed inference problems.

We consider a multiple-access channel (MAC), where transmitters are powered by energy harvesting. They are equipped with batteries having non-ideal charging and discharging characteristics, resulting in a fractional loss of power driven into or drawn from them. Assuming that each user consumes constant power for circuit operation during transmission, we optimize the throughput region, the set of all tuples of the number of bits delivered by the users over a finite duration of time. When circuit powers are zero, it is known that a non-orthogonal multiple access (NOMA) strategy, called Pure-NOMA (P-NOMA), where user transmissions always overlap, achieves all points on the largest throughput region. We show that P-NOMA is no longer optimal with non-zero circuit power and propose a hybrid strategy called H-NOMA that combines P-NOMA with time-division multiple access (TDMA). H-NOMA allocates fixed time windows for single-user and non-orthogonal multi-user transmissions. We maximize the sum-throughput in H-NOMA with non-casual and causal knowledge of the harvested powers and channel power gains. With causal knowledge, we obtain the optimal online policy via dynamic programming and deduce some structural properties and propose a simpler suboptimal online policy that performs significantly better than a naive greedy policy. We numerically show the largest throughput regions of P-NOMA and TDMA are contained within that of H-NOMA.

In the real-world, it is virtually impossible to have non-causal knowledge of future events. Research in energy harvesting (EH) systems that assumes knowledge of future energy arrivals falls short in terms of practical utility, pointing to the need for online strategies. In addition, the modeling and analysis for EH transmitter and receiver are inherently different. Compared with EH transmitter, EH receiver has received less attention. In this paper, we formulate Markov decision process problems and perform online optimization to maximize the number of bits decoded for an EH receiver with a time-switching architecture, which harvests energy from both a dedicated transmitter and other sources. We consider both infinite and finite horizon scenarios. For the infinite horizon, we provide an upper bound on the average expected reward. Then, we find an optimal policy which can achieve performance arbitrarily close to this bound. For the finite horizon, we first provide a policy obtained from standard backward induction with space quantization. Its performance can be close to optimal online performance as the number of quantization intervals increases, at the cost of relatively high computational complexity. Then, by carefully restricting the state space, we present a computationally efficient policy, which achieves comparatively good performance.

In this paper, we are interested in the lossy transmission of a single source over parallel additive white Gaussian noise channels with independent quasi-static fading and receiver channel state information. We call this the lossy multi-connectivity problem. Motivated by the ultra-reliable and low latency communication requirements, we consider the finite blocklength performance of lossy multi-connectivity. By generalizing the non-asymptotic bounds of Kostina and Verdti for the lossy joint source-channel coding problem, we derive nonasymptotic achievability and converse bounds for the lossy multi-connectivity problem. Using these non-asymptotic bounds, under mild conditions on the fading distribution, we derive good approximations for the finite blocklength performance in the spirit of second-order asymptotics for any discrete memoryless source under any bounded distortion measure. Our results demonstrate that the asymptotic notions of outage probability and outage capacity are actually good criteria even in the finite blocklength regime. Finally, we illustrate our results via numerical examples.

The rate-distortion saddle-point problem considered by Lapidoth (1997) consists in finding the minimum rate to compress an arbitrary ergodic source when one is constrained to use a random Gaussian codebook and minimum (Euclidean) distance encoding is employed. We extend Lapidoth's analysis in several directions in this paper. Firstly, we consider second-order asymptotics. In particular, when the source is stationary and memoryless, we establish ensemble tight second-order coding rate for the problem. Secondly, by “random Gaussian codebook”, Lapidoth refers to a collection of random codewords, each of which is drawn independently and uniformly from the surface of an n-dimensional sphere. To be more precise, we term this as a spherical Gaussian codebook. We also consider i.i.d. Gaussian codebooks in which each random codeword is drawn independently from a product Gaussian distribution. We also derive the second-order asymptotics when i.i.d. Gaussian codebooks are employed. Interestingly, in contrast to the recent work on the channel coding counterpart by Scarlett, Tan and Durisi (2017), the dispersions for spherical and i.i.d. Gaussian code books are identical for the rate-distortion saddle-point problem.

We consider a universal joint source channel coding (JSCC) scheme to transmit an arbitrary memoryless source over an arbitrary additive channel. We adopt an architecture that consists of Gaussian codebooks for both the source reproduction sequences and channel codewords. The natural minimum Euclidean distance encoder and decoder, however, need to be judiciously modified to ensure universality as well as to obtain the best (highest) possible communication rates. In particular, we consider the analogue of an unequal error (or message) protection scheme in which all sources are partitioned into disjoint power type classes. We also regularize the nearest neighbor decoder so an appropriate measure of the size of each power type class is taken into account in the decoding strategy. For such an architecture, we derive ensemble tight second-order asymptotics.

We consider a multiple-access channel where the users are powered from batteries having non-negligible internal resistance. When power is drawn from the battery, a variable fraction of the power, which is a function of the power drawn from the battery, is lost across the internal resistance. Hence, the power delivered to the load is less than the power drawn from the battery. The users consume a constant power for the circuit operation during transmission but do not consume any power when not transmitting. In this setting, we obtain the maximum sum-rates and achievable rate regions under various cases. We show that, unlike in the ideal battery case, the TDMA (time-division multiple access) strategy, wherein the users transmit orthogonally in time, may not always achieve the maximum sum-rate when the internal resistance is non-zero. The users may need to adopt a hybrid NOMA-TDMA strategy which combines the features of NOMA (non-orthogonal multiple access) and TDMA, wherein a set of users are allocated fixed time windows for orthogonal single-user and non-orthogonal joint transmissions. We also numerically show that the largest achievable rate regions in NOMA and TDMA strategies are contained within the largest achievable rate region of the hybrid NOMA-TDMA strategy.

Constrained coding is used widely in digital communication and storage systems. In this paper, we study a generalized sliding window constraint called the skip-sliding window constraint. A skip-sliding window (SSW) code is defined in terms of the length L of a sliding window, skip length J, and cost constraint E in each sliding window. Each valid codeword of length L+kJ is determined by k+1 windows of length L where window i starts at (iJ+1)th symbol for all non-negative integers i such that i ≤ k; and the cost constraint E in each window must be satisfied. In this work, two methods are given to enumerate the size of SSW codes. Using the proposed enumeration methods, the noiseless capacity of binary SSW codes is determined and observations such as greater capacity than other classes of codes are made. Moreover, some noisy capacity bounds are given. SSW coding constraints arise in various applications including simultaneous energy and information transfer.

Subblock-constrained codes are an important class of constrained codes, having applications in many diverse fields. In this paper, we provide closed-form expressions for the best known upper bounds on the asymptotic rates of subblock-constrained codes for a range of relative distance values via a generalized sphere-packing approach. In particular, we study binary subblock energy-constrained codes (SECCs), characterized by the property that the number of ones in each subblock exceeds a certain thresh-old, and binary constant subblock-composition codes (CSCCs), characterized by the property that the number of ones in each subblock is constant. Improved bounds on the optimal asymptotic rate for SECCs and CSCCs are obtained by applying a generalized sphere-packing approach and judiciously choosing appropriate constrained spaces for estimating asymptotic ball sizes. We also use numerical examples to highlight the improvement.

Constant subblock-composition codes (CSCCs) are a type of constrained codes in which codewords are partitioned into smaller subblocks with each subblock having the same composition. These constrained codes have applications in diverse fields such as simultaneous energy and information transfer, visible light communication, and design of low-cost authentication methods. In this paper, we characterize the sphere packing error exponent for CSCCs over discrete memoryless channels. We also derive computationally efficient bounds on the CSCC sphere packing error exponent, and show that these bounds are asymptotically tight in the subblock length. In addition, we present several numerical examples, highlighting the impact of subblock length, subblock-composition, and transmission rate, on the CSCC sphere packing error exponent.

Internet of Things (IoT) systems will increasingly rely on energy harvested from their environment, and energy harvesting (EH) techniques necessitate a rethinking of how we design and optimize IoT systems. The performance of EH IoT systems is affected by the battery nonidealities and the energy consumption for transmitting and receiving. While EH considerations at the transmitter have been widely studied, the EH receiver has received relatively much less attention. Motivated by this, we investigate, in this paper, the performance of EH receivers in IoT systems with batteries having non-negligible internal resistance. We first consider a receiver with a dual-path architecture and give an optimal battery management scheme. Then, based on this management scheme, we maximize the amount of information decoded at the receiver for single and multiple block scenarios. In the multiple block scenario, we transform the nonconvex problem into a series of convex problems by exploiting certain structural properties of the nonconvex constraints. Additionally, we present extensive numerical results to validate our analysis and to study the impact of the internal resistance. This paper suggests that the internal resistance significantly impacts the design and performance of EH IoT systems. However, the dual-path architecture can be an efficient way to reduce the performance loss caused by internal resistance. Finally, we discuss implementation considerations.

The difficulty of modeling energy consumption in communication systems leads to challenges in energy harvesting (EH) systems, in which nodes scavenge energy from their environment. An EH receiver must harvest enough energy for demodulating and decoding. The energy required depends upon factors, such as code rate and signal-to-noise ratio, which can be adjusted dynamically. We consider a receiver which harvests energy from the transmitter and other ambient sources, meaning the received signal is used for both EH and information decoding. Assuming a generalized function for energy consumption, we maximize the total number of information bits decoded, under both average and peak power constraints at the transmitter, by carefully optimizing the power used for EH, power used for information transmission, fraction of time for EH, and code rate. For transmission over a single block, we find there exist problem parameters for which either maximizing power for information transmission or maximizing power for EH is optimal. In the general case, the optimal solution is a tradeoff of the two. For transmission over multiple blocks, we give an upper bound on performance and give sufficient and necessary conditions to achieve this bound. Finally, we give some numerical results to illustrate our results and analysis.

The study of subblock-constrained codes has recently gained attention due to their application in diverse fields. We present bounds on the size and asymptotic rate for two classes of subblock-constrained codes. The first class is binary constant subblock-composition codes (CSCCs), where each codeword is partitioned into equal sized subblocks, and every subblock has the same fixed weight. The second class is binary subblock energy-constrained codes (SECCs), where the weight of every subblock exceeds a given threshold. We present novel upper and lower bounds on the code sizes and asymptotic rates for the binary CSCCs and SECCs. For a fixed subblock length and small relative distance, we show that the asymptotic rate for CSCCs (respectively SECCs) is strictly lower than the corresponding rate for constant weight codes (CWCs) [respectively heavy weight codes (HWCs)]. Furthermore, for codes with high weight and low relative distance, we show that the asymptotic rate for CSCCs is strictly lower than that of SECCs, which contrasts with the fact that the asymptotic rate for the CWCs is equal to that of the HWCs. We also provide a correction to an earlier result by Chee et al. (2014) on the asymptotic CSCC rate. In addition, we present several numerical examples comparing the rates for the CSCCs and SECCs with those for the CWCs and HWCs.

Motivated by streaming multi-view video coding and wireless sensor networks, we consider the problem of blockwise streaming compression of a pair of correlated sources, which we term streaming Slepian-Wolf coding. We study the moderate deviations regime in which the rate pairs of a sequence of codes converge, along a straight line, to various points on the boundary of the Slepian-Wolf region at a speed slower than the inverse square root of the blocklength n, while the error probability decays subexponentially fast in n. Our main result focuses on the directions of approaches to corner points of the Slepian-Wolf region. It states that for each correlated source and all corner points, there exists a non-empty subset of directions of approaches, such that the moderate deviations constant (the constant of proportionality for the subexponential decay of the error probability) is enhanced (over the non-streaming case) by at least a factor of T, the block delay of decoding source block pairs. We specialize our main result to the setting of streaming lossless source coding and generalize this result to the setting, where we have different delay requirements for each of the two source blocks. The proof of our main result involves the use of various analytical tools and amalgamates several ideas from the recent information-theoretic streaming literature. We adapt the so-called truncated memory encoding idea from Draper and Khisti (2011) and Lee, Tan, and Khisti (2016) to ensure that the effect of error accumulation is nullified in the limit of large block lengths. We also adapt the use of the so-called minimum weighted empirical suffix entropy decoder, which was used by Draper, Chang, and Sahai (2014) to derive achievable error exponents for symbolwise streaming Slepian-Wolf coding.

We revisit the high-dimensional content identification with lossy recovery problem (Tuncel and Gündüz, 2014) and establish an exponential strong converse theorem. As a corollary of the exponential strong converse theorem, we derive an upper bound on the joint identification-error and excess-distortion exponent for the problem. Our main results can be specialized to the biometrical identification problem (Willems, 2003) and the content identification problem (Tuncel, 2009) since these two problems are both special cases of the content identification with lossy recovery problem. We leverage the information spectrum method introduced by Oohama and adapt the strong converse techniques therein to be applicable to the problem at hand.

Modern patient data tends to be large-scale and multi-dimensional, containing both spatial and temporal features. Learning good spatio-temporal features from large patient data is a challenging task, especially when there are missing observations. In this paper, we propose a spatio-temporal autoencoder (STAE), an unsupervised deep learning scheme, to learn features from large-scale and high-dimensional patient data with missing observations. Through both spatial and temporal encoding, STAE is able to automatically identify patterns and dependencies in the patient data, even with missing values, and learn a compact representation of each patient for better classification. Publicly available electroencephalogram (EEG) data are extracted from the UCI Machine Learning Repository to test and support our findings. Through simulations, we compare STAE with several baseline feature selection methods and demonstrate its effectiveness in the presence of missing data.

In this paper, we revisit the lossy source coding problem with side information available at the encoder and one of the two decoders, which we term as the Kaspi problem (Kaspi, 1994). For the Kaspi problem, we first present the properties of optimal test channels for the rate-distortion function. Subsequently, we generalize the notion of distortion-tilted information density for the lossy source coding problem to the Kaspi problem and prove a non-asymptotic converse bound using the properties of optimal test channels and the well- defined distortion-tilted information density. Finally, we derive the exact second-order coding rate of the Kaspi problem for discrete memoryless sources.

In this paper, we revisit the multiple description coding problem with one semi-deterministic distortion measure, which we term as the Fu- Yeung problem (Fu and Yeung, 2002). We present the properties of optimal test channels for the minimum sum-rate function, a non- asymptotic converse bound and second-order asymptotics for discrete memoryless sources. Since the successive refinement problem is a special case of the Fu-Yeung problem, as a by-product, we obtain a non-asymptotic converse bound for the successive refinement problem, which turns out to be a strict generalization of the non-asymptotic converse bound for successively refinable sources (Zhou, Tan and Motani, 2017).

The large propagation delay of underwater acoustic signals significantly affects the throughput performance of underwater communication networks. While past research focused on mitigating the impact of large propagation delays, recent work has suggested exploiting large delays. In this paper, we consider an underwater linear unicast network which employs a time- division based scheduling strategy to exploit large propagation delays to improve network throughput. We assume the protocol model in a network with partially overlapping collision domains, where the transmission range is normalized as 1 and the interference range is an integer k. We systematically discuss the throughput of the linear networks with single traffic flow, showing that the average throughput of an N-node linear network with single traffic flow cannot exceed (N-1)/k. We then propose a general transmission scheduling strategy that can achieve the throughput upper bound and also give some examples of the optimal schedules.

We consider rate maximization for an energy harvesting node transmitting delay-constrained information over a slow fading channel corrupted by additive white Gaussian noise. Time is divided into frames of fixed duration equal to the channel coherence block length, the time duration for which the channel power gain remains constant before changing to a different value, independently. We assume that the transmitter does not know the exact channel state but has access to the channel statistics. The transmitter is equipped with a battery having non-zero internal resistance. Using superposition coding, we formulate and study an average rate maximization problem with non-causal knowledge of the harvested power. Further, assuming statistical knowledge and causal information of the harvested power variations, we propose a sub-optimal algorithm, and compare with the stochastic dynamic programming based solution and a greedy policy.

Mobile cloud computing (MCC) leverages the advantages of both cloud computing and mobile computing. With trusted, resource-rich and Internet-connected computing units, referred to as cloudlets, MCC brings cloud resources closer to the mobile users (MU) at the network edge. While MCC has plenty of advantages, unique challenges exist for efficient operation in practical MCC systems. First, the system-wide utility depends on both the offloading policy at the MUs and the task admission policy at the cloudlets. When the computation tasks have heterogeneous deadlines, determining optimal policies at both the MUs and the cloudlets in a distributed manner is nontrivial. Additionally, truthful mechanisms are needed for MCC markets in order to achieve desirable trading behaviors between MUs and cloudlets. In this paper, we present a novel scheme, called Stochastic Offloading in Mobile cloud computing (SOM), to address the above challenges through an online auction approach. SOM achieves desirable economic properties, such as truthfulness, individual rationality and budget balance. Furthermore, by leveraging Lyapunov optimization techniques, the proposed SOM scheme can drive the long-term system-wide utility towards a near-optimum. Through rigorous theoretical analysis and comprehensive simulations, we demonstrate the effectiveness of SOM.

In this paper, we consider a scalar Gaussian Channel with minimum amplitude constraint, and investigate when the capacity-achieving input is binary. First, we study the case that the input satisfies both minimum and peak amplitude constraints and find that the optimal input is discrete. Then, for a given minimum amplitude, we find sufficient conditions that the peak amplitude constraint must satisfy such that the optimal input is binary and when it is not binary. Similarly, for a given peak amplitude, we find sufficient conditions that the minimum amplitude constraint must satisfy such that the optimal input is binary and when it is not binary. Finally, we find that when the input satisfies minimum amplitude and average power constraints, the optimal input is not binary, regardless of whether there is also a peak amplitude constraint.

The study of binary constant subblock-composition codes (CSCCs) has recently gained attention due to their application in diverse fields. These codes are a class of constrained codes where each codeword is partitioned into equal sized subblocks, and every subblock has the same fixed weight. We present novel upper and lower bounds on the asymptotic rate for binary CSCCs, using the sphere-packing and Gilbert-Varshamov (GV) type bounds, respectively. For a fixed subblock length and small code distance, we show that the asymptotic rate for CSCCs is strictly lower than the corresponding rate for constant weight codes (CWCs). We also provide a correction to an earlier result by Chee et al. (2014) on the asymptotic CSCC rate.

The subblock energy-constrained codes (SECCs) have recently been shown to be suitable candidates for simultaneous energy and information transfer, where bounds on SECC capacity were presented for communication over noisy channels. In this paper, we study binary SECCs with given error correction capability, by considering codes with a certain minimum distance. Binary SECCs are a class of constrained codes where each codeword is partitioned into equal sized subblocks, and every subblock has weight exceeding a given threshold. We present several upper and lower bounds on the optimal SECC code size, and also derive the asymptotic Gilbert-Varshamov (GV) and sphere-packing bounds for SECCs. A related class of codes are the heavy weight codes (HWCs) where the weight of each codeword exceeds a given threshold. We show that for a fixed subblock length, the asymptotic rate for SECCs is strictly lower than the corresponding rate for HWCs when the relative distance of the code is small. The rate gap between HWCs and SECCs denotes the penalty due to imposition of weight constraint per subblock, relative to the codeword based weight constraint.

In this paper, we revisit the content identification problem with lossy recovery (Tuncel and Gündüz, 2014) and establish the exponential strong converse theorem for the problem. Further, we derive an upper bound on the joint excess-distortion and error exponent for the problem.

Motivated by streaming multi-view video coding, we consider the problem of blockwise streaming compression of a pair of correlated sources, which we term streaming Slepian-Wolf coding. We study the moderate deviations regime in which the rate pairs of a sequence of codes converges, along a straight line, to various points on the boundary of the Slepian-Wolf region at a speed slower than the inverse square root of the blocklength n, while the error probability decays subexponentially fast in n. Our main result focuses on directions of approaches to corner points of the Slepian-Wolf region. It states that for each correlated source and all corner points, there exists a non-empty subset of directions of approaches such that the moderate deviations constant (the constant of proportionality for the subexponential decay of the error probability) is enhanced (over the non-streaming case) by at least a factor of T, the block delay of decoding symbol pairs. Further, we specialize our main result to the setting of lossless streaming source coding.

In this paper, we give a framework for constructing codes over the binary energy harvesting channel when the energy arrivals are random and the battery has large but finite size. We study both noiseless and noisy binary channels (i.e., bit flips). In the noiseless case, we present an encoding strategy (called exponential backoff encoding) which uses a decreasing amount of energy in consecutive transmissions between energy arrivals. We analyze the achievable rate of backoff encoding and show that it can outperform a uniform energy usage policy. We then extend the encoding strategy to a noisy binary channel, suggest a corresponding decoder, and analyze its performance. We believe our constructive approach complements existing approaches which focus on the information capacity of energy harvesting channels.

The pervasiveness of mobile phones and the increasing sensing capabilities of their built-in sensors have made mobile crowd sensing (MCS) a promising approach for large-scale event detection and collective knowledge formation. In a typical MCS system, the crowdsourcer purchases sensing data from some mobile phone users (i.e., contributors) and sells it to consumers for revenue. This kind of sensing data exchange has its unique challenges in practical MCS systems. On one hand, the crowdsourcer wants to maximize the information utility to get the most revenue under heterogeneous requests from the consumers while offering incentives to strategic contributors. On the other hand, the contributors need to make optimal real-time sensing and data selling decisions by considering their real-time sensing cost and quality of information, in order to maximize their own profit. In this paper, we propose a novel Information-driven Data Auction (IDA) scheme for data exchange in practical stochastic MCS systems, which offers optimal strategies for both the crowdsourcer and the contributors. By applying stochastic Lyapunov optimization and mechanism design theory, IDA is able to achieve a near-optimal time-averaged system-wide utility, while offering incentives to the contributors. Moreover, IDA achieves favourable economic properties including truthfulness, individual rationality, and budget balance. We demonstrate the efficacy of IDA through rigorous theoretical analysis and comprehensive simulations.

In this paper, we revisit the discrete lossy Gray-Wyner problem. In particular, we derive its optimal second-order coding rate region, its error exponent (reliability function), and its moderate deviations constant under mild conditions on the source. To obtain the second-order asymptotics, we extend some ideas from Watanabe's work. In particular, we leverage the properties of an appropriate generalization of the conditional distortion-tilted information density, which was first introduced by Kostina and Verdú. The converse part uses a perturbation argument by Gu and Effros in their strong converse proof of the discrete Gray-Wyner problem. The achievability part uses two novel elements: 1) a generalization of various type covering lemmas and 2) the uniform continuity of the conditional rate-distortion function in both the source (joint) distribution and the distortion level. To obtain the error exponent, for the achievability part, we use the same generalized type covering lemma, and for the converse, we use the strong converse together with a change-of-measure technique. Finally, to obtain the moderate deviations constant, we apply the moderate deviations theorem to probabilities defined in terms of information spectrum quantities.

We derive the optimal second-order coding region and moderate deviations constant for successive refinement source coding with a joint excess-distortion probability constraint. We consider two scenarios: 1) a discrete memoryless source (DMS) and arbitrary distortion measures at the decoders and 2) a Gaussian memoryless source (GMS) and quadratic distortion measures at the decoders. For a DMS with arbitrary distortion measures, we prove an achievable second-order coding region, using type covering lemmas by Kanlis and Narayan and by No, Ingber, and Weissman. We prove the converse using the perturbation approach by Gu and Effros. When the DMS is successively refinable, the expressions for the second-order coding region and the moderate deviations constant are simplified and easily computable. For this case, we also obtain new insights on the second-order behavior compared with the scenario where separate excess-distortion proabilities are considered. For example, we describe a DMS, for which the optimal second-order region transitions from being characterizable by a bivariate Gaussian to a univariate Gaussian, as the distortion levels are varied. We then consider a GMS with quadratic distortion measures. To prove the direct part, we make use of the sphere covering theorem by Verger-Gaugry, together with appropriately-defined Gaussian type classes. To prove the converse, we generalize Kostina and Verdú's one-shot converse bound for point-to-point lossy source coding. We remark that this proof is applicable to general successively refinable sources. In the proofs of the moderate deviations results for both scenarios, we follow a strategy similar to that for the second-order asymptotics and use the moderate deviations principle.

Modern systems will increasingly rely on energy harvested from their environment. Such systems utilize batteries to smooth out the random fluctuations in harvested energy. These fluctuations induce highly variable battery charge and discharge rates, which affect the efficiencies of practical batteries that typically have non-zero internal resistance. In this paper, we study an energy harvesting communication system using a finite battery with non-zero internal resistance. We adopt a dual-path architecture, in which harvested energy can be directly used, or stored and then used. In a frame, both time and power can be split between energy storage and data transmission. For a single frame, we derive an analytical expression for the rate optimal time and power splitting ratios between harvesting energy and transmitting data. We then optimize the time and power splitting ratios for a group of frames, assuming non-causal knowledge of harvested power and fading channel gains, by giving an approximate solution. When only the statistics of the energy arrivals and channel gains are known, we derive a dynamic programming-based policy and propose three sub-optimal policies, which are shown to perform competitively. In summary, this paper suggests that battery internal resistance significantly impacts the design and performance of energy harvesting communication systems and must be considered.

The analysis and optimization of energy-harvesting transmitters and receivers are different. This paper considers an end-to-end communication with an energy-harvesting receiver. The receiver has a time-switching architecture and can harvest energy from both a dedicated transmitter and other ambient radio-frequency (RF) sources. We first argue that the energy consumed for decoding (per channel use) can be expressed in terms of the gap to channel capacity and utilize this model to optimize two schemes for receiver operation. The two schemes are harvest-then-receive and harvest-when-receive, and they differ primarily in how and when they use the harvested energy for decoding. For transmission over a single block, we compare their performance from various aspects. Then we consider transmission over multiple blocks. When the energy harvested is all from the transmitter, we provide the solution for choosing the optimal code rate and fraction of channels used for energy harvesting for each block. When the energy harvested can also be from other RF sources, we provide a table-search algorithm to find a solution. Finally, we present some numerical examples to validate the accuracy of our analysis.

We consider the design of energy management policies for multimedia wireless sensor nodes that rely entirely on harvesting energy from the environment for both the data acquisition and transmission. In many high volume data sensing applications, the sampled data is compressed before transmission to meet the bandwidth and transmit power constraints. The compression results in data distortion, but it reduces the amount of data to be transmitted. As a consequence, the transmission energy is reduced, but excessive compression may consume more energy than what is saved by transmitting less data. This points to a trade-off between compression and transmission (in terms of both the energy and time allocated to these operations). Our goal is to identify the optimal energy management policies that minimize the long-term average distortion at the receiver. We first study the optimal solution in an off-line setting and then propose three on-line policies. We highlight the importance of the compression power, showing that, all other system parameters being equal, the average distortion decreases exponentially as the compression power is increased by processing at a faster rate.

Compared with energy-harvesting transmitters, the performance of energy-harvesting receivers has not been fully investigated. The main consumption of energy at transmitters is for transmission, while that at receivers is for information decoding. Hence, the analysis and optimization of energy-harvesting transmitters and receivers are inherently different. Motivated by the above, in this paper, we analyze the performance of a time-switching energy-harvesting receiver, which switches between harvesting and decoding. We assume that the receiver can only harvest energy from the electromagnetic signal radiated by the transmitter and the energy consumption of other processing is negligible compared with decoding. We first argue that the energy consumed for decoding (per channel use) can be expressed in terms of the gap to channel capacity and utilize this model to optimize two schemes for receiver operation. The two schemes are Harvest-then-Receive and Harvest-when-Receive, and they differ primarily in how and when they use the harvested energy for decoding. We address the problem of maximizing the amount of information decoded over both single and multiple blocks, and use the binary symmetric channel as an example to validate the accuracy of our analysis.

Compared with energy-harvesting transmitters, the performance of energy-harvesting receivers has not been fully investigated. The main consumption of energy at transmitters is for transmission, while that at receivers is for information decoding. Hence, the analysis and optimization of energy-harvesting transmitters and receivers are inherently different. This paper considers optimization of a communication system using an energy-harvesting receiver. We assume that the receiver antenna operates over a relatively wide range of frequencies; hence the receiver can harvest energy from both the in-band signal sent by the transmitter and other possibly out-of-band sources. The receiver adopts a time-switching architecture, i.e., in each block, the receiver first harvests energy then decodes information. We assume the energy consumption for decoding is a non-decreasing convex function of the normalized code rate and dominates the energy used for other processing tasks. In this context, we formulate a non-convex optimization problem to maximize the amount of information decoded over multiple blocks. We solve this non-convex problem by converting it into an equivalent convex problem. We also provide numerical examples to validate the accuracy of our analysis and compare our scheme with two suboptimal schemes requiring less overhead.

Consider an energy-harvesting receiver that uses the same received signal both for decoding information and for harvesting energy, which is employed to power its circuitry. In the scenario where the receiver has limited battery size, a signal with bursty energy content may cause power outage at the receiver since the battery will drain during intervals with low signal energy. The energy content in the signal may be regularized by partitioning each codeword into smaller subblocks and requiring that sufficient energy is carried in every subblock duration. In this paper, we study subblock energy-constrained codes (SECCs) which, by definition, are codes satisfying the subblock energy constraint. For SECCs, we provide a sufficient condition on the subblock length to avoid power outage at the receiver. We consider discrete memoryless channels and characterize the SECC capacity, and also provide different bounds on the SECC capacity. Further, we characterize and bound the random coding error exponent for SECCs.

We derive the optimal second-order coding region for the lossy Gray-Wyner source coding problem for discrete memoryless sources under mild conditions. To do so, we leverage the properties of an appropriate generalization of the conditional distortion-tilted information density, which was first introduced by Kostina and Verdú (2012). The converse part uses the perturbation argument by Gu and Effros (2009) in their strong converse proof of the discrete Gray-Wyner problem. The achievability part uses a generalization of type covering lemmas and the uniform continuity of the conditional rate-distortion function in both the source joint distribution and the distortion level.

We derive the optimal second-order coding region for the discrete successive refinement source coding problem under the joint excess-distortion event. To do so, we define a generalization of the tilted information density and leverage its properties. In the achievability part, we make use of type covering lemmas by Kanlis and Narayan (1996) and by No, Ingber and Weissman (2015). In the converse proof, we make use of the perturbation approach by Gu and Effros (2009). We also specialize our results to successively refinable sources and provide an alternative converse proof for such sources by generalizing Kostina and Verdú's (2012) one-shot converse bound for point-to-point lossy source coding.

Graphical models have been widely applied in distributed network computation problems such as inference in large-scale sensor networks. While belief propagation (BP) based on message passing is a powerful approach to solving such distributed inference problems, one major challenge, in the context of wireless sensor networks, is how to systematically address the trade-off between energy efficiency and inference performance. Although various energy-efficient message passing algorithms based on a given graphical model have been proposed in the literature, little work has been done to optimize the graphical model structure to achieve good energy efficiency and inference performance at the same time. In this paper, we propose an efficient distributed algorithm for optimizing the graphical model structure in order to minimize the communication cost required by the inference algorithm without incurring significant performance loss. We first formulate the problem as a multi-objective constrained problem and prove its NP-hardness. Then, we propose an efficient heuristic to solve the problem in polynomial time. Through extensive simulations, using both real-world sensor network data and synthesized data, we empirically evaluate our proposed graphical model structure optimization framework. The simulation results demonstrate that the optimized graphical model efficiently balances the performance of the inference algorithm (measured by mean squared error) and the energy consumed by the inference algorithm (measured by energy used in communication). These highlight the advantages of our proposed framework.

We consider multi-source energy harvesting communication systems, where the energy harvested from two independent processes is used for the transmission of the data packets. The data packets arrive randomly and wait in a queue for accumulation of sufficient energy and for service completion of previously arrived packets. Thus, the data queue dynamics are influenced jointly by the energy arrival process, the data arrival process, and the data service process. This coupling between the data and energy queues makes an exact system analysis extremely hard, and has led researchers to resort to either computationally intensive numerical solutions or to make simplifying approximations. In this paper, we employ Diphase, a two phase queueing formulation, which decouples the wait stages for the energy arrival process and the service process, to derive closed-form expressions for the average packet delay and the probability of data packet loss due to buffer overflow. These expressions are shown to be exact when the service time is negligible, and robust for a relatively wide range of values of the average service time. We show that these expressions are useful in selecting system design parameters, which maximize the throughput while meeting the required quality of service constraints.

Consider an energy-harvesting receiver that uses the same received signal both for decoding information and for harvesting energy, which is employed to power its circuitry. In the scenario where the receiver has limited battery size, a signal with bursty energy content may cause power outage at the receiver, since the battery will drain during intervals with low signal energy. In this paper, we analyze subblock energy-constrained codes (SECCs), which ensure that sufficient energy is carried within every subblock duration. We consider discrete memoryless channels and characterize the SECC capacity and the SECC error exponent, and provide useful bounds for these values. We also study constant subblock-composition codes (CSCCs), which are a subclass of SECCs where all the subblocks in every codeword have the same fixed composition, and this subblock composition is chosen to maximize the rate of information transfer while meeting the energy requirement. Compared with constant composition codes (CCCs), we show that CSCCs incur a rate loss and that the error exponent for CSCCs is also related to the error exponent for CCCs by the same rate loss term. We exploit the symmetry in CSCCs to obtain a necessary and sufficient condition on the subblock length for avoiding power outage at the receiver. Furthermore, for CSCC sequences, we present a tight lower bound on the average energy per symbol within a sliding time window. We provide numerical examples highlighting the tradeoff between the delivery of sufficient energy to the receiver and achieving high information transfer rates. It is observed that the ability to use energy in real-time imposes less of penalty compared with the ability to use information in real-time.

We contend that context information of Internet clients can help to efficiently manage a variety of underlying resources for different Internet services and systems. We therefore propose a resource distribution framework that provides quality of experience (QoE) aware service differentiation, which means that starving clients are prioritized in resource allocation to enhance the corresponding end-user's QoE. The framework also actively motivates each Internet client to consistently provide its actual context information and to adopt moderate competition policies, given that all clients are selfish but rational in nature. We analyze the Internet client's behavior by formulating a non-cooperative game and prove that the framework guides all clients (game players) towards a unique Nash equilibrium. Furthermore, we prove that the distribution results computed by the framework maximize a social welfare function. Throughout this paper, we demonstrate the motivation, operation and performance of the framework by presenting a Web system example, which leverages on the advanced context information deduced by a context-aware system.

We consider the design of transmission policies for sensor nodes that rely entirely on harvesting energy from the environment. Nodes store the harvested energy in a storage element which has constraints on maximum discharge rate and charging efficiency. Non-zero circuit power is considered and limitations on channel bandwidth and processor clock-rate are incorporated. We assume an additive white Gaussian noise (AWGN) channel and that time is divided into frames, with a fixed number of symbols transmitted in the frame duration. We consider an energy arrival process in which energy arrives at a constant rate within a frame but varies stochastically and independently across frames. In this context, we propose a dual-path architecture for energy flow that is shown to mitigate the performance loss due to the discharge rate constraint. For a given frame, we determine the rate-optimal time sharing ratio between harvesting energy and transmitting data. We also propose three sub-optimal policies, including statistical directional water-filling, for determining the time sharing ratio for a group of frames and compare their performance with an upper bound. We highlight that the discharge rate constraint is an important limitation of the storage element that can potentially hinder the effective use of energy.

Even though underwater acoustic communication suffers from long propagation delays and has very limited bandwidth, it still plays a key role in supporting long-distance, low-power communication in underwater sensor networks. Many previous studies have tried to mitigate the impact of long propagation delays, but recently, the focus has shifted from mitigating to exploiting large propagation delays. In this paper, we consider an underwater acoustic network which employs a time- division based scheduling strategy and supports multicasting, meaning that packets may have multiple destinations. In this context, we establish an upper bound on the throughput of a general multicasting network, and study networks which can achieve this bound. We also study the throughput of ring networks (in which nodes are uniformly located on a circle) and give some examples and schedules which achieve the maximum possible throughput. Finally, we explore the properties of valid, perfect, and fair slot schedules for ring networks.

The burgeoning cost of healthcare has forced industry experts and academics to rethink current healthcare systems. There is a compelling argument that the increasing costs are primarily due to the fundamentally reactionary approach used in healthcare today, with the focus being on treatment and cure rather than on prevention. Consequently, building a sustainable healthcare system requires a paradigm shift towards a proactive prevention based approach. A critical requirement of such a system is the ubiquitous collection of and access to patient physiological data. Both real-time and historical analysis of this data is the basis of a preventive healthcare system. To this end, we are developing a pervasive real-time health monitoring framework to seamlessly connect both patients and healthy people to healthcare professionals. In this paper, we present the design of this framework, which is intended to be lightweight, agile and scalable. The design primarily utilizes a resource-oriented architecture (ROA) based RESTful HTTP to connect wireless biosensors, wireless networks and a cloud computing platform. The paper also discusses a proof-of-concept implementation of the framework that demonstrates the effectiveness of the technology choices made in achieving the required design goals.

Consider an energy-harvesting receiver that uses the same received signal both for decoding information and for harvesting energy to power its circuitry. When the receiver has limited battery size, a signal with bursty energy content may cause power outage since the battery will drain during intervals with low signal energy. The energy content in the signal may be regularized by requiring that sufficient energy is carried in every subblock duration. In this paper, we study constant subblock-composition codes (CSCCs) where all subblocks in every codeword have the same composition, and this composition is chosen such that the real-time energy requirement at the receiver is met. For a given energy storage capacity at the receiver, we give a necessary and sufficient condition on the subblock length for avoiding outage. We show that CSCC capacity on a discrete memoryless channel can be efficiently computed by exploiting certain symmetry conditions, and compare it with the capacity of constant composition codes. We provide numerical examples highlighting the tradeoff between delivery of sufficient energy to the receiver and achieving high information transfer rates.

Sensor nodes equipped with renewable energy sources are capable of recharging their batteries and supporting data collection and transmission indefinitely. Energy and data management of these types of systems is challenging primarily due to the variability of renewable energy sources and transmission channels. This paper explores a methodology for designing the control of such systems. The goal is to jointly control the energy usage and data sampling rate to maximize the long-term performance of the system subject to the constraints imposed by the available energy and data. The design of this control is based on estimates of the large deviations of the energy stored in the battery and of the queued data. A low-complexity control policy is proposed that does not depend on the instantaneous charge of the battery and data backlog and almost maximizes the long-term data transmission rate. Moreover, the results show that one can decouple the analysis of the energy and of the data queue without much loss in performance.

In 1975, Carleial presented a special case of an interference channel, called the very strong interference regime, in which the interference does not reduce the capacity of the constituent point-to-point Gaussian channels. In this paper, we show that in the strictly very strong interference regime, the dispersions are similarly unaffected. More precisely, in this paper, we characterize the second-order coding rates of the Gaussian interference channel in the strictly very strong interference regime. In other words, we characterize the speed of convergence of rates of optimal block codes toward a boundary point of the (rectangular) capacity region. These second-order coding rates are expressed in terms of the average probability of error and variances of appropriately defined information densities which coincide with the dispersion of the (single-user) Gaussian channel. This allows us to conclude that the dispersions are unaffected by interference in this channel model.

Recent results have shown that feedback can significantly increase the capacity of interference networks. This paper considers the impact of noise on such gains due to feedback. In particular, this paper considers the two-user linear deterministic interference channel with noisy feedback, as a stepping stone to characterize the approximate capacity region for the two-user Gaussian interference channel with noisy feedback. First, the capacity region for the symmetric linear deterministic interference channel with noisy feedback is obtained. It is shown that noisy feedback enlarges the capacity region if and only if the number of feedback bits l is greater than a certain threshold l*. It is found that, excluding the regime (1/2) ≤ α ≤ 2, where α is the normalized interference level, in which even full feedback does not increase symmetric capacity, this threshold l* is equal to the per-user symmetric capacity without feedback. One of the key ideas is a novel converse outer bounding technique for the weighted sum rates 2R1+ R2and R1+ 2R2. These results and the techniques developed for the linear deterministic model are then applied to characterize inner bounds and outer bounds for the symmetric Gaussian interference channel with noisy feedback. The outer bounds are shown to be at most 4.7 b/s/Hz away from the achievable rate region. As a corollary, the generalized-degrees-of-freedom region, which approximates the capacity region of the symmetric Gaussian interference channel at high SNR, is found.

Collaborative spectrum sensing in cognitive radio networks mitigates the negative propagation effects of the wireless channel and increases the sensing reliability. Collaborative sensing requires sensors to share their local spectrum sensing information (SSI) with other users. This paper proposes distributed iterative time slot allocation algorithms for SSI sharing on a dedicated common control channel in a cognitive radio ad hoc network scenario. The proposed algorithms are based on a collision detection and acknowledgment scheme. This scheme allows the network nodes to receive knowledge about collisions regarding their transmitted SSI packets. The nodes use this information to update their operating time slots using a probabilistic approach; each node maintains and updates a parameter representing the probability of switching the time slot in case of a collision. Both fixed and adaptive probability based schemes are proposed. The proposed algorithms are proven to converge to a collision-free allocation with probability one if such an allocation exists. Moreover, an analytical expression for the expected convergence time is established. Extensive simulation results illustrating the rapid convergence, excellent performance, and small reporting overhead of the proposed time slot allocation algorithms are provided.

Unlike most existing underwater medium access control (MAC) protocols that use unidirectional data exchange, the recently proposed BiC-MAC protocol allows each sender-receiver pair to exchange multiple rounds of bidirectional-concurrent data transmissions. Via simulations, it was shown that BiC-MAC greatly improves channel utilization. In this paper, we propose a novel analytical framework based on an absorbing Markov chain to analyze the single-hop saturation throughput for slotted BiC-MAC, under error-prone channel conditions. Motivated by the insight that time-slotting loses its effects when inter-nodal delay is longer than packet transmission time, the presented results can serve as a close approximation for the original, unslotted BiC-MAC protocol. We model the protocol behavior for a sender-receiver pair that attempts to bidirectionally exchange their backlogged batch of packets. To compute saturation throughput from batch service time, we systematically derive both the state transition probabilities and the expected time spent in each Markov chain. Via comparison against the simulation results of unslotted and slotted BiC-MAC in both small and large topologies with channel errors, we show that the model approximates unslotted BiC-MAC reasonably well. We also present another approach that uses the actual inter-nodal delay information and offers even closer approximation to the throughput of unslotted BiC-MAC.

Directional Medium Access Control protocols (DMACs) have been studied for decades. Since most existing DMACs assume an ideal antenna model which does not consider the minor-lobe interference, their performance cannot be guaranteed in practice. Other approaches assuming non-ideal antenna require either extra equipment or clock synchronization, making the system more complicated. It is also observed that directional transmission is rarely discussed in multi-channel scenarios. In this paper, a Cooperative Multi-channel Directional Medium Access Control protocol (CMDMAC) is proposed, incorporating directional transmission and multi-channel transmission to enhance system performance. Without making the terminals more complex or requiring clock synchronization, CMDMAC uses cooperative methods to solve the hidden terminal and deafness problems, taking into account minor-lobe interference effects of the directional antennas. Protocol performance is studied via simulation in NS2, showing that CMDMAC has good performance in terms of throughput and data packet transmission ratio.

The second-order asymptotics of the Gaussian interference channel in the strictly very strong interference regime are considered. The rates of convergence to a given point on the boundary of the (first-order) capacity region are determined. These rates are expressed in terms of the average probability of error and variances of selected modified information densities which coincide with the dispersion of the (single-user) Gaussian channel. Interestingly, under the strictly very strong interference assumption, the intuition that receivers can decode messages from non-intended transmitters carries over to the second-order analysis.

Energy harvesting communication systems provide a “green” solution by obtaining energy from ambient sources, such as sunlight or vibrations. This energy is stored for transmission of data packets which arrive at the link layer of an energy harvesting transmitter. Since the data and energy arrival processes are independent and random, the data packets wait in a queue for the accumulation of sufficient amount of energy and for service completion of previously arrived packets. Thus, the energy arrival process and the data service process jointly impact the data queue dynamics. This makes the queueing analysis of an energy harvesting communication system challenging. In this paper, we formulate a two stage virtual queueing system which decouples the wait stages for the energy arrival process and the service process. This virtual queueing system leads to closed-form expressions for the average packet delay and the probability of data packet loss due to buffer overflow. We assume that the data and energy arrivals are independent Poisson processes and the service time for data packets may have any general distribution. The expressions for the average packet delay and the probability of buffer overflow are shown to be exact when the service time becomes negligible, and the packet delay gets dominated by data packets waiting for arrival of sufficient energy. These expressions are compared with Monte Carlo simulations and are shown to be robust even when the service time is increased up to sixty percent of the average packet delay.

In this paper, we consider three transmit strategies for the fading three-node two-way relay network, namely, physical-layer network coding (PNC), digital network coding (DNC), and codeword superposition (CW-Sup). The aim is to minimize the total average energy needed to deliver a given pair of required average rates. Full channel state information is assumed to be available at all transmitters and receivers. The optimization problems corresponding to the various strategies in fading channels are formulated, solved, and compared. For the DNC-based strategies, a simple time sharing of transmission of the network-coded message and the remaining bits of the larger message (DNC-TS) is considered first. We extend this approach to include a superposition strategy (DNC-Sup), in which the network-coded message and the remainder of the longer source message are superimposed before transmission. It is theoretically demonstrated that DNC-Sup outperforms DNC-TS and CW-Sup in terms of total average energy usage. More importantly, it is shown in the simulation that DNC-Sup performs better than PNC if the required rate is low and worse otherwise. Finally, an algorithm to select the optimal strategy in terms of energy usage subject to different rate pair requirements is presented.

In this paper, we consider a three-node, two-way relay network with digital network coding over fading channels. The aim is to minimize total energy consumption for a given pair of required rates through this network. The uplink is a multiple access channel. In the downlink, we first consider orthogonal time sharing of network coded broadcasting and one way forwarding. We extend this approach to include a superposition strategy for the downlink, in which the network coded message and the remaining bits of the larger message are superimposed. This network coding superposition strategy is shown to always decrease total energy usage. We verify our findings via a series of numerical computations of the total energy consumption of the two strategies.

In this work, achievable dispersions for the discrete memoryless interference channel (DM-IC) are derived. In other words, we characterize the backoff from the Han-Kobayashi (HK) achievable region, the largest inner bound known to date for the DM-IC. In addition, we also characterize the backoff from Sato's region in the strictly very strong interference regime, and the backoff from Costa and El Gamal's region in the strong interference regime. To do so, Feinstein's lemma is first generalized to be applicable to the interference channel. Making use of the generalized Feinstein's lemma, it is found that the dispersions for the DM-IC can be represented by the information variances of eight information densities when HK message splitting is involved, and of six information densities for another encoding strategy. We also derive an outer bound that leverages on a known dispersion result for channels with random state by Ingber-Feder. It is shown that for the strictly very strong interference regime, the inner and outer bound have similar algebraic forms.

In this paper, we consider a three-node, two-way relay system with digital network coding over static channels. For a given pair of random packet arrival rates, we aim to minimize total energy consumption while ensuring queue stability at all nodes. A set of transmission modes is considered and we solve for the optimal fraction of resources allocated to each mode, including a multi-access uplink transmission mode and a network coded broadcasting mode. For the downlink, we further consider whether it is more energy-efficient, to superimpose the excess bits of the larger message for one user with the network coded message for both users. We formulate and solve the corresponding optimization problem, deriving conditions under which it is better to use superposition coding. Finally, we present a detailed analysis of the queues at each node using a random scheduling method that closely approximates the theoretical design, through a Markov chain model.

In this paper, distributed iterative time slot allocation algorithms for spectrum sensing information (SSI) sharing in cognitive radio ad hoc networks are proposed. The proposed algorithms are based on a collision detection and acknowledgment scheme, which allows nodes to receive knowledge about collisions with their two-hop neighbors. The nodes use this information to update their operating time slots using a probabilistic approach, i.e., each node maintains a parameter representing the probability of switching the time slot in case of a collision. Both fixed and adaptive probability based schemes are proposed. Simulation results show the rapid convergence and excellent performance of the proposed time slot allocation algorithms.

Delay sensitive applications such as gaming and video streaming require relatively low average packet delay, an important higher layer metric which directly affects the user experience. In this paper, we consider a polling based multiple access scheme and study the impact of channel coding on the average packet delay where the link layer employs Automatic Repeat Request (ARQ) to provide error free packet transmission. The communication model assumes that users share a common physical channel and communicate with a central server which polls them for transmission in a cyclic order. Using an average waiting time analysis, we prove that, compared to an uncoded system, it is sufficient for a coding scheme to reduce the average service time in order to achieve lower average packet delay. We use the bounds on the minimum distance of linear codes to choose that code for which the reduction in the number of retransmissions (due to a decrease in probability of packet error) outweighs the increase in packet time (due to an increase in packet length by channel coding) such that the average service time is minimized. We also show that the percentage reduction in average service time by employing channel coding (compared to an uncoded system) results in corresponding reduction in average transmit energy required for successful transfer of a data packet. Numerical examples are provided to highlight the tradeoffs involved in the choice of an appropriate channel coding scheme.

In this paper, we consider the medium access control (MAC) protocol design for random access cognitive radio network (CRN). Based on asynchronous spectrum sensing technique and RTS/CTS mechanism, a new MAC protocol, namely, cognitive-radio-based carrier sense medium access with collision avoidance (CR-CSMA/CA) is proposed to coordinate the channel access of secondary network as well as protect the operation of primary network, which applies to both single and multiple channel models. Using the G/G/1 queuing model with consideration of unsaturated and saturated network condition, we develop a framework to analyze the proposed MAC protocol and also derive closed-form expressions of specific performance metrics such as normalized throughput, average packet service time, etc. Performance evaluations illustrate and validate that the performance of CR-CSMA/CA varies with the offered traffic load of secondary network and the spectrum utilization rate of primary network, respectively, and also show that CR-CSMA/CA outperforms other relevant MAC protocols.

In this paper, we derive explicit expressions for the capacity region of the two-user symbol-asynchronous Gaussian vector multiple-access channel. Verdú considered the case where each user linearly modulates a fixed waveform in each symbol period, where the symbol periods for the users are not perfectly aligned at the receiver. He derived explicit capacity region expressions for the case where the transmitters have knowledge of the mutual offset and also for the case where the transmitters have no knowledge of the mutual offset. In this paper, we extend Verdú's results to allow each user to linearly modulate a set of orthonormal waveforms, instead of a single waveform, in each symbol period and with no restrictions imposed on the waveforms. We consider group power constraints, which include individual sum power constraints, as orthonormal waveforms assigned to each user may come from different frequency bands with different power constraints. Similar to the case where each user is allowed to linearly modulate only a single waveform, our results hold regardless of whether or not the transmitters are frame synchronous. In addition, we present some results that are necessary to numerically compute the capacity region expressions with general purpose convex optimization algorithms. Next, we simplify the capacity region expression when there are only individual sum power constraints and when the transmitters know the mutual offset. We also prove a sufficient condition for a similar simplification to hold when the transmitters have no knowledge of the mutual offset. Finally, we consider a specialized algorithm to numerically compute the simplified capacity region expression when the transmitters know the mutual offset.

Existing approaches to indoor tracking have various limitations. Location-fingerprinting approaches are labor intensive and vulnerable to environmental changes. Trilateration approaches require at least three line-of-sight beacons for coverage at any point in the service area, which results in heavy infrastructure cost. Dead reckoning (DR) approaches rely on knowledge of the initial location and suffer from tracking error accumulation. Despite this, we adopt DR for location tracking because of the recent emergence of affordable hand-held devices equipped with low-cost DR-enabling sensors. In this paper, we propose an indoor pedestrian tracking system that comprises of a DR subsystem implemented on a mobile phone and a ranging subsystem with a sparse infrastructure. A particle-filter-based fusion scheme is applied to bound the accumulated tracking error by fusing DR with sparse range measurements. Experimental results show that the proposed system is able to track users much better than DR alone. The system is robust even when: 1) the initial user location is not available; 2) range updates are noisy; and 3) range updates are intermittent, both temporally and spatially.

In this paper, we consider a three-node, two-way relay system with digital network coding. The aim is to minimize total energy consumption while ensuring queue stability at all nodes, for a given pair of random packet arrival rates. Specifically, we allow for a set of transmission modes and solve for the optimal fraction of resources allocated to each mode. First, we formulate and solve the static-channel problem, where all link gains are constant over the duration of transmission. Then, we solve the fading-channel problem, where link gains are random. We call the latter the ergodic energy efficiency problem and show that its solution has a water-filling structure. Finally, we provide a detailed analysis of the queues at each node when a random scheduling method that closely approximates the theoretical design is used.

In this paper, we consider a hidden terminal scenario where two transmitters A and B, hidden to each other, wish to communicate to a common access point, AP. When a collision occurs at AP, due to the inherent asynchrony between the colliding packets, the mutual interference between them is effectively decreased. This achieves a higher signal-to-interference-plus-noise (SINR) ratio which improves the probability of successfully decoding both colliding packets through conventional successive interference cancellation (SIC). When neither colliding packet can be decoded first through SIC, we propose an enhanced SIC (ESIC) scheme. The proposed decoding scheme does not require synchronization, coordination or power control between the transmitters or a sophisticated coding design. By exploiting the inherent asynchrony between the two colliding packets, there exists, with high probability, an interference-free chunk together with an interfered chunk in a packet ready for decoding. Thus it is still possible for both colliding packets to be recovered eventually from a single collision. Our results demonstrate that through the proposed ESIC scheme, both colliding packets can be recovered with a higher probability thus improving the system throughput.

The linear deterministic interference channel (LD-IC) with partial feedback is considered. Partial feedback for the LD-IC models a scenario in which the top l most-significant-bits of the channel output of receiver j are received as feedback at transmitter j, for j = 1, 2. The rationale for studying the LD-IC with partial feedback comes from the fact that it is a good approximation to the Gaussian interference channel with output feedback corrupted by additive white Gaussian noise (commonly referred to as noisy feedback). The main contribution of this paper is a characterization of the sum-capacity of the symmetric LD-IC with partial feedback. The differences between the models of partial feedback and rate-limited feedback are emphasized and highlighted by comparing the corresponding sum-capacities, which are shown to differ in general.

This paper investigates price-based resource allocation strategies for two-tier femtocell networks, in which a central macrocell is underlaid with distributed femtocells, all operating over the same frequency band. Assuming that the macrocell base station (MBS) protects itself by pricing the interference from femtocell users, a Stackelberg game is formulated to study the joint utility maximization of the macrocell and femtocells subject to a maximum tolerable interference power constraint at the MBS. Two practical femtocell network models are investigated: sparsely deployed scenario for rural areas and densely deployed scenario for urban areas. For each scenario, two pricing schemes: uniform pricing and non-uniform pricing, are proposed. The Stackelberg equilibriums for the proposed games are characterized, and an effective distributed interference price bargaining algorithm with guaranteed convergence is proposed for the uniform-pricing case. Numerical examples are presented to verify the proposed studies. It is shown that the proposed schemes are effective in resource allocation and macrocell protection for both the uplink and downlink transmissions in spectrum-sharing femtocell networks.

The activity around the standardization of an IEEE 802.11 mesh protocol has gained momentum in recent years. The mesh architecture presents a huge potential for multiple device-to-device communication, which will likely be realized through multi-channel access techniques. Prior studies on multi-channel access focus on routing and media access control (MAC) layers and are limited primarily to analysis and simulation. In this paper, we present the application of a novel approach called distributed information sharing (DISH) to provide a simple multi-channel access solution for 802.11 mesh networks. We present a cooperative multi-channel access extension of the 802.11 MAC protocol by incorporating DISH into the IEEE 802.11 DCF design and implement the protocol using commodity 802.11 hardware and open source Linux drivers. The paper also presents protocol design considerations, implementation challenges and experimental results from a mesh testbed. The study clearly demonstrates the performance superiority of the technique under heavy traffic conditions and confirms that cooperative multi-channel access is a promising technology for boosting the performance of 802.11 mesh networks.

ABSTRACT Task allocation for wireless sensor networks with multiple concurrent applications (such as target tracking and event detection) requires sharing applications' tasks (such as sensing and computation) and available network resources. In this paper, we model the distributed task allocation problem for multiple concurrent applications by using a reverse combinatorial auction, in which the bidders (sensor nodes) are supposed to bid cost values (according to their available resources) for accomplishing the subset of the applications' tasks. Trust management schemes consist of a powerful tool for the detection of unexpected node behaviors (such as faulty or malicious). It is critical for participants (i.e., bidders and auctioneer) to estimate each other's trustworthiness before initiating the task allocation procedure. To address this issue, we introduce a real‐time trust management module for our auction system that is able to validate the reliable bid value and determine faulty nodes and malicious entities. The main objective of our task allocation scheme is to maximize the network lifetime by sharing tasks and network resources within applications, while enhancing the overall application quality of service (e.g., deadline). We also propose a heuristic two‐phase winner determination protocol to deal with the combinatorial reverse auction problem. Simulation results show that the proposed scheme offers the promising performance and efficiency. Copyright © 2012 John Wiley & Sons, Ltd.

We consider spectrum sharing in a cognitive radio network where a secondary system co-exists with an automatic repeat-request (ARQ)-based primary system. A cooperate-and-access spectrum sharing protocol is proposed where the secondary system alternates between cooperation and access modes. In the cooperation mode, the secondary system serves as a relay to assist the primary transmission, and in return accumulates credits. The credits allow the secondary system to gain spectrum access by exploiting the ARQ retransmissions of the primary system. We show analytically that through the proposed credit system, as long as the credits accumulated in cooperation mode compensate for the degradation in primary performance during access mode, an equal or higher average throughput is achieved for the primary system than in the case without spectrum sharing, while providing spectrum access opportunities for the secondary system.

We study the half-duplex multiple-relay channel (HD-MRC) where every node can either transmit or listen but cannot do both at the same time. We obtain a capacity upper bound based on a max-flow min-cut argument and achievable transmission rates based on the decode-forward (DF) coding strategy, for both the discrete memoryless HD-MRC and the phase-fading HD-MRC. We discover that both the upper bound and the achievable rates are functions of the transmit/listen state (a description of which nodes transmit and which receive). More precisely, they are functions of the time fraction of the different states, which we term a schedule. We formulate the optimal scheduling problem to find an optimal schedule that maximizes the DF rate. The optimal scheduling problem turns out to be a maximin optimization, for which we propose an algorithmic solution. We demonstrate our approach on a four-node multiple-relay channel, obtaining closed-form solutions in certain scenarios. Furthermore, we show that for the received signal-to-noise ratio degraded phase-fading HD-MRC, the optimal scheduling problem can be simplified to a max optimization.

Distributed Information SHaring (DISH) is a new cooperative approach to designing multichannel MAC protocols. It aids nodes in their decision making processes by compensating for their missing information via information sharing through neighboring nodes. This approach was recently shown to significantly boost the throughput of multichannel MAC protocols. However, a critical issue for ad hoc communication devices, viz. energy efficiency, has yet to be addressed. In this paper, we address this issue by developing simple solutions that reduce the energy consumption without compromising the throughput performance and meanwhile maximize cost efficiency. We propose two energy-efficient strategies: in-situ energy conscious DISH, which uses existing nodes only, and altruistic DISH, which requires additional nodes called altruists. We compare five protocols with respect to these strategies and identify altruistic DISH to be the right choice in general: it 1) conserves 40-80 percent of energy, 2) maintains the throughput advantage, and 3) more than doubles the cost efficiency compared to protocols without this strategy. On the other hand, our study also shows that in-situ energy conscious DISH is suitable only in certain limited scenarios.

Wireless sensor networks (WSNs) are usually assigned tasks for a single application. Recently, the concept of shared sensor networks, which support multiple concurrent applications, has emerged, reducing the deployment and administrative costs, and increasing the usability and efficiency of the network. Supporting task allocation for multiple concurrent applications in sensor networks (such as target tracking, event detection, etc.) requires sharing applications' tasks (such as sensing, computation, etc.) and available network resources. In this paper, we model the distributed task allocation problem for multiple concurrent applications using a reverse combinatorial auction, in which the bidders (sensor nodes) bid the cost value (in terms available resources) for accomplishing the subset of the applications' tasks. The main objective is to maximize the network lifetime by sharing tasks and network resources among applications, while enhancing the overall application QoS (e.g., deadline). We also propose a heuristic two-phase winner determination protocol to solve the combinatorial reverse auction problem. Simulation results show that the proposed scheme offers efficiency and network scalability.

This paper investigates price-based resource allocation strategies for the uplink transmission of a spectrum-sharing femtocell network, in which a central macrocell is underlaid with distributed femtocells, all operating over the same frequency band as the macrocell. Assuming that the macrocell base station(MBS) protects itself by pricing the interference from the femtocell users, a Stackelberg game is formulated to study the joint utility maximization of the macrocell and the femtocells subject to a maximum tolerable interference power constraint at the MBS. In particular, two pricing schemes: uniform pricing and non-uniform pricing, are investigated. Then, the Stackelberg equilibriums for the proposed games are studied, and the relationship between the two pricing schemes is examined. It is shown that the nonuniform pricing scheme maximizes the revenue of the MBS, while the uniform pricing scheme maximizes the sum-rate of the femtocell users.

We present a downlink opportunistic scheduling algorithm when there are user equipments (UEs) served by multiple mobile terminals (MTs) in a time- slotted cellular system. We study two scenarios, namely Scenario (i) when the scheduler knows the presence of such UEs; and Scenario (ii) when the scheduler has no knowledge of the presence of such UEs. We establish the optimality and present the main properties of our scheduling scheme. Simulations under High-Speed Down-link Packet Access (HSDPA) model are implemented which show that our algorithm works well and provides an approximately 20% performance improvement for the UEs served by multiple MTs as compared to previous opportunistic scheduling schemes. Furthermore, our algorithm is able to provide better overall performance even in the worst case. The objective behind this research work is to establish the performance of cellular systems that provides differentiated quality of service (QoS).

In this paper, we consider the medium access control (MAC) protocol design for cognitive radio networks. An opportunistic spectrum access protocol named Slotted CR-ALOHA is proposed, and its performances in terms of normalized throughput and average packet delay are evaluated. Simulation results show that for various frame lengths and number of SUs, the optimal performance can be achieved at an appropriate spectrum sensing time, and there also exists a tradeoff between the achievable performance of secondary network and the protection effect on primary network.

In this paper, we propose a cooperative spectrum sharing protocol (CSSP) between two overlapping static ad hoc wireless networks where the primary and secondary networks consist of n and m randomly distributed nodes respectively. The secondary network achieves spectrum access along with the primary network by allowing its nodes to relay the primary traffic. Taking advantage of the broadcast nature of wireless channels, the secondary nodes are able to forward primary and secondary packets simultaneously by transmitting a superimposed signal. We analyze the throughput and delay scaling performance of the proposed protocol and show that given m ≥ n, the primary network is able to achieve a per-node throughput scaling which is better than that of a stand-alone network with n nodes. At the same time, the secondary network achieves the same throughput scaling as a stand-alone network with m nodes. We also derive the throughput-delay tradeoff for both the primary and secondary systems in this scenario.

Traffic congestion has become an increasingly important issue worldwide. One way to mitigate this problem is to provide real time traffic information to drivers and help them make better decisions. Hence, a system with the function of traffic sensing, data aggregation and information delivery is desired. In this paper, we illustrate how we design and build such a system, which is called ISSTA (An Integrated Sensing System for Transportation Applications).This system consists of two parts: the front end is a mobile device attached to a vehicle; it can perform real time traffic and environment sensing, wireless information transmission, and interaction with drivers. The back end is a server, which stores the information collected and implements smart decision-making. In addition to this, the system supports "plug-and-play" for a list of sensing components. At the same time, the information collected and decision made can be easily monitored in real time through web service. Applications like real time environment monitoring and lane sensing have already been implemented and tested on this system. We have shown that it is a reliable system by itself and can provide valuable help to drivers and researchers.

In this paper, we present results on the equivalence of some coding strategies for the general relay channel. Cover & El Gamal described two basic coding strategies for the relay channel, more commonly known as decode-and-forward and compress-and-forward. These two strategies were combined in a mixed strategy that employed irregular encoding and successive forward decoding to give a tighter lower bound for the capacity of the general relay channel. Recently, the authors presented two different mixed strategies, SeqBack decoding and SimBack decoding, that make use of regular encoding and backward decoding. We identify a termination problem in SeqBack/SimBack decoding and present a simple fix. Next, we compare the rates achievable with the various mixed strategies. We first show that SeqBack decoding and SimBack decoding achieve the same rate. We then present alternative characterizations, without feasibility constraints, for the rates achievable with the various mixed strategies. Comparing the alternative characterizations, we note that the rate of SeqBack/SimBack decoding contains the rate of Cover & El Gamal's mixed strategy since there is a more relaxed inequality in the rate expression. We also prove that simultaneously decoding all unknown quantities in each block at the receiver does not increase the achievable rate for backward decoding. Hence, successive decoding in each block proves to be just as effective as simultaneous decoding. Finally, we present a sliding-window decoding strategy that achieves the same rate as SeqBack/SimBack decoding. The sliding-window decoding strategy also avoids the aforementioned termination problem as the receiver commences decoding after three block decoding delay.

The relay channel consists of a transmitter inputx1, a relay inputx2, a relay outputy2, and a receiver outputy3. In this paper, we establish the capacity of three new classes of semi-deterministic relay channels: 1) a class of degraded semi-deterministic relay channels, 2) a class of semi-deterministic orthogonal relay channels, and 3) a class of semi-deterministic relay channels with relay-transmitter feedback. For the first class of relay channels, the output of the relayy2depends on a deterministic function of the transmitter's inputx1, i.e., ons=f1(x1), rather than onx1directly. In addition, the relay channels satisfy the condition thatS→ (X2,Y2) →Y3forms a Markov chain for all input probability distributionsp(x1,x2). Hence, the first class of relay channels includes, but is strictly not limited to, the class of degraded relay channels previously considered by Cover and El Gamal. The partial decode-and-forward strategy achieves the capacity of the class of degraded semi-deterministic relay channels. Next, we consider the class of semi-deterministic orthogonal relay channels where there are orthogonal channels from the relay to the receiver and from the transmitter to the receiver. In addition, the output of the relayy2is a deterministic function ofx1,x2andy3, i.e.,y2=f4(x1,x2,y3). The class of semi-deterministic orthogonal relay channels is a generalization of the class of deterministic relay channels considered by Kim. The compress-and-forward strategy achieves the capacity of the class of semi-deterministic orthogonal relay channels. For the third class of relay channels, there is a causal and noiseless feedback from the relay to the transmitter. In addition, similar to the second class of relay channels, the output of the relayy2is a deterministic function ofx1,x2, andy3. Both the generalized strategy of Gabbai and Bross and the hash-and-forward strategy of Kim achieve the capacity of the class of semi-deterministic relay channels with relay-transmitter feedback.

Recently there has been increasing interest in building networks with Ambient Intelligence (AmI), which incorporates the user-centricity and context awareness. However, both the Internet TCP/IP protocol stack and the seven-layer OSI reference model are not suitable for AmI networks, because they do not specifically take the end-user requirements into consideration in their architecture design. Under the client-server architecture, we propose to explicitly take the end-user into account by defining a new layer called User Layer above the traditional application layer. The User Layer empowers the end-users to influence network performance based on their interaction activities with the networks. We adopt the Model Human Processor (MHP) approach for building the User Model. After that we present an exemplary User Layer implementation to illustrate how the User Layer interacts with the underlying protocol stack and improves end-user's satisfaction with network performance.

Accurate indoor pedestrian tracking has wide applications in the healthcare, retail, and entertainment industries. However, existing approaches to indoor tracking have various limitations. For example, location-fingerprinting approaches are labor-intensive and vulnerable to environmental changes. Trilateration approaches require at least three Line-of-Sight (LoS) beacons to cover any point in the service area, which results in heavy infrastructure cost. Dead Reckoning (DR) approaches rely on knowledge of the initial user location and suffer from tracking error accumulation. Despite this, we adopt DR for location tracking because of the recent emergence of affordable hand-held devices equipped with low cost DR-enabling sensors. In this paper, we propose an indoor pedestrian tracking system which comprises a DR sub-system implemented on a mobile phone, and a ranging sub-system with a sparse infrastructure. A probabilistic fusion scheme is applied to bound the accumulated tracking error of DR when new range measurements are available from sparsely deployed beacons. Experimental results show that the proposed system is able to track users much better than DR alone, with reductions in average error by up to 71.9%. The system is robust and works well even when the initial user location is not available and range updates are intermittent. This highlights the potential of using sparse but reasonably accurate partial information to limit location tracking errors.

This paper addresses building networks that emphasizes on user-centric human computer interaction and context awareness. To achieve this user-centric intelligent network goal, we propose to explicitly take the end-user into account by defining a new layer called the User Layer above the traditional application layer. By exposing some lower layer information to the end-user, the new User Layer establishes a feedback loop between the end-user and the underlying network infrastructure, empowering the end-user to control and influence network performance based on his own behavior and preferences. A cross-layer design approach using a shared database between the different lower layers is adopted. To illustrate the User Layer in action, we present an exemplary implementation of the User Layer, which can dynamically allocate network resources by leveraging on the TCP flow control mechanism. We evaluated network performance via simulation and show that such a design improves the user perceived quality of service (QoS).

In most existing sender-initiated handshaking based underwater Media Access Control (MAC) protocols, only the initiating sender is allowed to transmit data packets to its intended receiver after the channel has been reserved; none of the potentially backlogged neighbors of the sender can transmit in the duration after the current handshake. Therefore, each of those neighbors must initiate their own handshakes, which incur additional overheads and potentially result in poor channel utilization. In this paper, we present a novel approach to increase the channel utilization by allowing a sender to invite its one-hop neighbors (appenders) to opportunistically transmit (append) their data packets. After the sender finishes transmitting its packets to its own receiver, it can immediately switch its role to receive the incoming appended data packets, which arrive in a packet train manner. This greatly reduces the relative proportion of time spent on control signaling. We refer to this MAC protocol as ROPA -- Reverse Opportunistic Packet Appending. From our extensive simulations and comparisons with existing protocols, we show that ROPA significantly increases the channel utilization and offers performance gains in terms of throughput and delay.

We investigate routing in cooperative multiple-terminal wireless networks in which the nodes can collaborate with each other in data transmission. First, we motivate cooperation by showing that decode-forward, an information-theoretic cooperative coding strategy, achieves rates significantly higher than those achievable by the conventional multi-hop routing, a point-to-point non-cooperative coding strategy. We then construct an algorithm to find optimal (rate-maximizing) routes for decode-forward. We show that the algorithm is able to find shortest optimal routes and is optimal in fading channels. However, the algorithm runs in factorial time in the worst case. So, we propose a near-optimal heuristic algorithm that runs in polynomial time. The heuristic algorithm always outputs optimal routes when the nodes transmit independent codewords, and outputs optimal routes with high probability when the nodes transmit arbitrarily correlated codewords. Lastly, we implement decode-forward using low-density parity-check codes to compare the bit error rate performance of different routes.

In this paper, an amplify-and-forward (AF) two-path half-duplex relaying scheme is considered in which one of the relays additionally performs inter-relay interference cancellation. We first generalize lower bounds for the diversity-multiplexing tradeoff (DMT) of an arbitrary block lower triangular channel matrix. We then characterize the diversity-multiplexing tradeoff for the AF two-path relaying scheme and show that the DMT achieves the multiple-input single-output (MISO) upper bound. The analysis also demonstrates that, with a careful choice of the coding strategy, the DMT of this scheme is achievable for finite codeword lengths. We then propose using an equivalent linear space time code at the source, which does not require any form of channel state information, as a simple and effective coding strategy to achieve the full DMT of the scheme. From the DMT perspective, the proposed AF two-path relaying with the equivalent linear space time coding outperforms existing schemes. Our analysis is then extended to the slotted-amplify-and-forward (SAF) scheme with multiple relays, where we provide a stronger result by deriving the DMT while taking into account inter-relay interference.

In wireless networks, node cooperation has been exploited as a data relaying mechanism for decades. However, the wireless channel allows for much richer interaction among nodes. In particular, Distributed Information SHaring (DISH) represents a new improvement to multichannel MAC protocol design by using a cooperative element at the control plane. In this approach, nodes exchange control information to make up for other nodes' insufficient knowledge about the environment, and thereby aid in their decision making. To date, what is lacking is a theoretical understanding of DISH. In this paper, we view cooperation as a network resource and evaluate the availability of cooperation, p_{co}. We first analyze p_{co} in the context of a multichannel multihop wireless network, and then perform simulations which show that the analysis accurately characterizes p_{co} as a function of underlying network parameters. Next, we investigate the correlation between p_{co} and network metrics such as collision rate, packet delay, and throughput. We find a near-linear relationship between p_{co} and the metrics, which suggests that p_{co} can be used as an appropriate performance indicator itself. Finally, we apply our analysis to solving a channel bandwidth allocation problem, where we derive optimal schemes and provide general guidelines on bandwidth allocation for DISH networks.

Verdu determined the capacity region of the symbol-asynchronous two-user Gaussian multiple-access channel. In this channel, each user modulates a fixed waveform in each symbol period and the symbol periods for the users do not coincide at the receiver. First, he explicitly evaluated the capacity region of this class of multiple-access channels in the case where the transmitters know the offset. The result was also extended to the case where the transmitters have no knowledge of the offset. In this paper, we extend the result to the case where each user modulates K orthogonal waveforms and the transmitters know the offset. In addition, the users' orthogonal waveforms are not assumed to be identical. Similar to the case where each user is allowed to modulate a fixed waveform, the result holds regardless of whether or not the transmitters are frame-asynchronous. We later extend the result to certain situations where the transmitters do not know the offset.

In this paper, we extend our previous work on the half duplex multiple-relay channel (MRC). A capacity upper bound based on the max-flow min-cut argument and achievable transmission rates based on the decode-forward coding strategy (DF) for the half duplex MRC have been shown to be functions of the schedule of the network, which is defined as the probability mass function of the transmit state vector (a description of which nodes transmit and which receive). Finding the optimal (rate-maximizing) schedule for DF can be formulated as a maximin optimization problem which is not easily solved in general. In our recent paper, we presented a technique to find optimal schedules for the 4-node MRC based on minimax hypothesis testing. Closed-form solutions were obtained for certain channel topologies. In this paper, we extend the technique to solve for optimal schedules for the general D-node half duplex MRC, where D ges 3.

Body Area Networks (BANs) can perform the task of continuous, remote monitoring of a patient's physiological signals in diverse environments. Apart from providing healthcare professionals with extensive logs of a patient's physiological history, BANs can be used to identify and react to emergency situations. We identify three important factors that afflict wireless communication in BANs: impermeability of the human body to radio waves at frequencies commonly used in BANs, efficient operation in mobile and time-varying environments, and mission-critical requirements for quick response to emergencies. An understanding of the link layer behavior of wireless sensor nodes placed on the body is crucial to address these and other challenges such as reducing energy consumption and increasing network lifetime.

In this paper, we consider the medium access control (MAC) protocol design problem for random access cognitive radio networks. A MAC protocol using a two-level opportunistic spectrum access strategy, called CR-CSMA, is proposed to efficiently schedule secondary users' packets, and yet to protect primary users' operations. We employ normalized throughput and average packet delay as network metrics, and derive closed-form expressions to evaluate our protocol. For various offered traffic rates of secondary users and frame lengths, the optimal performances of secondary users can be achieved at the same spectrum sensing time, and also there exists a tradeoff between performance and agility.

Cognitive radio technology increases spectrum utilization by enabling secondary users to opportunistically use the spectrum when primary users are inactive. Secondary users use spectrum sensing to detect the presence of primary users in order to avoid causing harmful interference. To the best of our knowledge, all existing spectrum sensing methods are essentially physical spectrum sensing, in the sense that nodes physically tune their radio to each frequency band to sense the spectrum. In this paper, we propose a complementary approach, virtual spectrum sensing, which achieves the same goal but only senses a very small portion of the spectrum. This approach enables a Distributed Information SHaring (DISH) mechanism, where neighboring users cooperatively share spectrum usage information (obtained from virtual spectrum sensing) with users who need it in decision making. This paper presents an application of DISH to cognitive radio networks. We provide a Cognitive DISH framework which describes guidelines for cognitive radio protocol design based on virtual spectrum sensing and DISH. Under this framework, we design a protocol, VISH-I, and evaluate its performance via simulations. As the number of secondary users increases, the interference caused to primary users results in only 5% performance degradation, but the overall channel utilization is increased by 87-203%. In addition, to demonstrate that virtual sensing is complementary to physical sensing, we design a hybrid spectrum sensing protocol, VISH-II, which improves performance by 7-50% over VISH-I.

As body sensor networks (BSNs) advance to fulfill the promise of continuous, non-intrusive, remote monitoring of patients, it is important that we achieve efficient communication between energy constrained on-body sensors. An important design choice which has significant impact on achieving this goal is the network architecture. Star architecture has been the natural choice for BSNs due to the short distances between the nodes. In this paper, we revisit this choice by quantitatively studying architecture choices using data from experiments conducted by deploying nodes operating at the 2.4 GHz band on actual human volunteers. We compare the star and multihop architectures to highlight their respective performance characteristics. In particular, we use our data to construct multihop networks with routes that maximize end-to-end packet delivery ratio (PDR) and routes that minimize the average number of retransmissions. Since BSNs span an entire spectrum of applications, each with its unique constraints and requirements, there is no solution that is optimal for all applications. Instead, we show the performance across a variety of metrics and the trade-offs that are achievable. We see that a multihop network minimizing retransmissions has several advantages including having better network lifetime as well as the lowest delay and energy consumption.

Half duplex devices are widely used in today's wireless networks. These devices can only send or receive, but not do both at the same time. In this paper, we use cooperative decode-forward relay strategies to increase the throughput of half-duplex wireless networks. Due to the half duplex constraint, relays need to carefully choose their transmission states in order to maximize the throughput. We show that the transmission schedule optimization can be formulated as a linear programming problem. Although the number of possible states grows exponentially as the number of relays increases, only a small subset of these states needs to be used in the optimal transmission schedule. This observation allows us to use heuristic algorithms to solve for near-optimal schedule in large networks. Our numerical results show that the decode-forward strategy can provide nearly 3 times more throughput than the traditional multi-hop relaying strategy in half duplex wireless networks.

The capacity region of a class of discrete memoryless interference channels with common information is established. The setup is similar to the class of deterministic interference channels without common information studied by El Gamal and Costa, which was later extended to the class of deterministic interference channels with common information. In this paper, certain conditions that were originally imposed by El Gamal and Costa are relaxed and it is shown, by a specific example, that this new class of interference channels is strictly larger than the class of deterministic interference channels previously studied. In fact, the result of this paper is obtained by combining the class of deterministic interference channels with the class of discrete memoryless interference channels with strong interference. Hence, it also includes the capacity region of the class of discrete memoryless interference channels with strong interference as a special case.

Medium access control (MAC) protocols have been studied under different contexts for decades. In decentralized contexts, transmitter-receiver pairs make independent decisions, which are often suboptimal due to insufficient knowledge about the communication environment. In this paper, we introduce distributed information sharing (DISH), which is a distributed flavor of control-plane cooperation, as a new approach to wireless protocol design. The basic idea is to allow nodes to share control information with each other such that nodes can make more informed decisions in communication. This notion of control-plane cooperation augments the conventional understanding of cooperation, which sits at the data plane as a data relaying mechanism. In a multichannel network, DISH allows neighboring nodes to notify transmitter-receiver pairs of channel conflicts and deaf terminals to prevent collisions and retransmissions. Based on this, we design a single-radio cooperative asynchronous multichannel MAC protocol called CAM-MAC. For illustration and evaluation purposes, we choose a specific set of parameters for CAM-MAC First, our analysis shows that its throughput upper bound is 91 percent of the system bandwidth and our simulations show that it actually achieves a throughput of 96 percent of the upper bound. Second, our analysis shows that CAM-MAC can saturate 15 channels at maximum and our simulations show that it saturates 14.2 channels on average, which indicates that, although CAM-MAC uses a control channel, it does not realistically suffer from control channel bottleneck. Third, we compare CAM-MAC with its noncooperative version called UNCOOP, and observe a throughput ratio of 2.81 and 1.70 in single-hop and multihop networks, respectively. This demonstrates the value of cooperation. Fourth, we compare CAM-MAC with three recent multichannel MAC protocols, MMAC, SSCH, and AMCP, and find that CAM-MAC significantly outperforms all of them. Finally, we implement CAM-MAC and UNCOOP on commercial off-the-shelf hardware and share lessons learned in the implementation. The experimental results confirm the viability of CAM-MAC and the idea of DISH.

Low latency anonymity systems are susceptive to traffic analysis attacks. In this paper, we propose a dependent link padding scheme to protect anonymity systems from traffic analysis attacks while providing a strict delay bound. The covering traffic generated by our scheme uses the minimum sending rate to provide full anonymity for a given set of flows. The relationship between user anonymity and the minimum covering traffic rate is then studied via analysis and simulation. When user flows are Poisson processes with the same sending rate, the minimum covering traffic rate to provide full anonymity to m users is O(log m). For Pareto traffic, we show that the rate of the covering traffic converges to a constant when the number of flows goes to infinity. Finally, we use real Internet trace files to study the behavior of our algorithm when user flows have different rates.

Unlike terrestrial wireless communication which uses radio waves, underwater communication relies on acoustic waves. The long latency and limited bandwidth pose great challenges in underwater Media Access Control (MAC) protocol design. As a result, terrestrial MAC protocols perform inefficiently when deployed directly in an underwater environment. In this paper, we examine how an existing asynchronous handshaking based protocol called Multiple Access Collision Avoidance (MACA) can be adapted for use in multi-hop underwater networks. Three areas of improvement are investigated, namely, the state transition rules, the packet forwarding strategy, and the backoff algorithm. Throughput performance is also evaluated through extensive simulation in multi-hop underwater networks. Due to its simplicity and throughput stability, our proposed MAC protocol can be adopted as a reference MAC protocol for underwater networks, with which a more sophisticated underwater MAC may benchmark its performance.

We collected packet traces from second life client sessions and analyzed the packet contents. We observed that textures constitute a majority of the network traffic. We further characterized the textures from three selected regions in second life in terms of their size and spatial distributions. We found that textures in these regions exhibit a different size distribution from files on a file system or documents on the Web. We also verified the intuition that texture objects are spatially non-uniformly distributed. Surprisingly, we found that the selected second life regions can contain up to hundreds of megabytes of textures, and there exist locations in these regions that encompass a large portion of these textures within their area-of-interest. Our work motivates the need to manage textures carefully and efficiently in the design of networked virtual environments such as second life, and hints at the amount of storage and bandwidth required at a peer if peer-to-peer techniques are applied for texture caching. Our traces are useful for simulation studies and can lead to a model to generate realistic workload for networked virtual environments.

The capacity regions of two new classes of deterministic relay channels are established. In the first class of deterministic relay channels, the family of conditional probability distributions describing the relay channel can be written as p(y2, y3|x1, x2)=p(y3|x1, x2)p(y2|s, x2, y3) where s is a deterministic function of x1, i.e., s=f1(x1). In addition, we require that Srarr(X2, Y2)rarrY3form a Markov chain for all input probability distributions p(x1, x2). In the second class of deterministic relay channels, there is causal noiseless feedback from relay to sender and the relay output is a deterministic function of x1, x2, and y3, i.e., y2=f3(x2, x2, y3). We consider two alternative schemes to achieve the capacity. The first is based on a generalized strategy of Gabbai and Bross. The second strategy is based on a ldquohash-and-forwardrdquo scheme by Cover and Kim.

For long, node cooperation has been exploited as a data relaying mechanism. However, the wireless channel allows for much richer interaction between nodes. One such scenario is in a multi-channel environment, where transmitter-receiver pairs may make incorrect decisions (e.g., in selecting channels) but idle neighbors could help by sharing information to prevent undesirable consequences (e.g., data collisions). This represents a Distributed Information SHaring (DISH) mechanism for cooperation and suggests new ways of designing cooperative protocols. However, what is lacking is a theoretical understanding of this new notion of cooperation. In this paper, we view cooperation as a network resource and evaluate the availability of cooperation via a metric, pco, the probability of obtaining cooperation. First, we analytically evaluate pco in the context of multi-channel multi-hop wireless networks. Second, we verify our analysis via simulations and the results show that our analysis accurately characterizes the behavior of pco as a function of underlying network parameters. This step also yields important insights into DISH with respect to network dynamics. Third, we investigate the correlation between pco and network performance in terms of collision rate, packet delay, and throughput. The results indicate a near-linear relationship, which may significantly simplify performance analysis for cooperative networks and suggests that pco be used as an appropriate performance indicator itself. Throughout this work, we utilize, as appropriate, three different DISH contexts - model-based DISH, ideal DISH, and real DISH - to explore pco.

Safety-critical wireless sensor networks, such as a distributed fire- or burglar-alarm system, require that all sensor nodes are up and functional. If an event is triggered on a node, this information must be forwarded immediately to the sink, without setting up a route on demand or having to find an alternate route in case of a node or link failure. Therefore, failures of nodes must be known at all times and in case of a detected failure, an immediate notification must be sent to the network operator. There is usually a bounded time limit, e.g., five minutes, for the system to report network or node failure. This paper presents DiMo, a distributed and scalable solution for monitoring the nodes and the topology, along with a redundant topology for increased robustness. Compared to existing solutions, which traditionally assume a continuous data-flow from all nodes in the network, DiMo observes the nodes and the topology locally. DiMo only reports to the sink if a node is potentially failed, which greatly reduces the message overhead and energy consumption. DiMo timely reports failed nodes and % greatly minimizes the false-positive rate and energy consumption compared with other prominent solutions for node monitoring.

We consider cross-layer adaptive transmission for a single-user system with stochastic data traffic and a time- varying wireless channel. The objective is to vary the transmit power and rate according to the buffer and channel conditions so that the system throughput, defined as the long-term average rate of successful data transmission, is maximized, subject to an average transmit power constraint. When adaptation is subject to a fixed bit error rate (BER) requirement, maximizing the system throughput is equivalent to minimizing packet loss due to buffer overflow. When the BER requirement is relaxed, maximizing the system throughput is equivalent to minimizing total packet loss due to buffer overflow and transmission errors. In both cases, we obtain optimal transmission policies through dynamic programming. We identify an interesting structural property of these optimal policies, i.e., for certain correlated fading channel models, the optimal transmit power and rate can increase when the channel gain decreases toward outage. This is in sharp contrast to the water-filling structure of policies that maximize the rate of transmission over fading channels. Numerical results are provided to support the theoretical development.

We consider a point-to-point communication system in which data packets randomly arrive to a finite-length buffer and are subsequently transmitted to a receiver over a time-varying wireless channel. Data packets are subject to loss due to buffer overflow and transmission errors. We study the problem of adapting the transmit power and rate based on the buffer and channel conditions so that the system throughput is maximized, subject to an average transmit power constraint. Here, the system throughput is defined as the rate at which packets are successfully transmitted to the receiver. We consider this buffer/channel adaptive transmission when only incomplete system state information is available for making control decisions. Incomplete system state information includes delayed and/or imperfectly estimated channel gain and quantized buffer occupancy. We show that, when some delayed but error-free channel state information is available, optimal buffer/channel adaptive transmission policies can be obtained using Markov decision theory. When the channel state information is subject to errors and when the buffer occupancy is quantized, we discuss various buffer/channel adaptive heuristics that achieve good performance. In this paper, we also consider the tradeoff between packet loss due to buffer overflow and packet loss due to transmission errors. We show by simulation that exploiting this tradeoff leads to a significant gain in the system throughput.

In this correspondence, we derive a simplified description of the Han–Kobayashi rate region for the general interference channel. Using this result, we establish that the recently discovered Chong–Motani–Garg rate region is a new representation of the Han–Kobayashi region. Moreover, a tighter bound for the cardinality of the time-sharing auxiliary random variable emerges from our simplified description.

This correspondence investigates the interplay between cooperation and achievable rates in multiterminal networks. Cooperation refers to the process of nodes working together to relay data toward the destination. There is an inherent tradeoff between achievable information transmission rates and the level of cooperation, which is determined by how many nodes are involved and how the nodes encode/decode the data. We illustrate this tradeoff by studying information-theoretic decode–forward-based coding strategies for data transmission in multiterminal networks. Decode-forward strategies are usually discussed in the context ofomniscient coding, in which all nodes in the network fully cooperate with each other, both in encoding and decoding. In this correspondence, we investigatemyopic coding, in which each node cooperates with only a few neighboring nodes. We show that achievable rates of myopic decode–forward can be as large as that of omniscient decode–forward in the low signal-to-noise ratio (SNR) regime. We also show that when each node has only a few cooperating neighbors, adding one node into the cooperation increases the transmission rate significantly. Furthermore, we show that myopic decode–forward can achieve nonzero rates as the network size grows without bound.

We propose MAX, a system that facilitates human-centric search of the physical world. Instead of organizing objects a priori, it allows humans to search for and locate them as needed. Designed for the following objectives: (i) human-centric operation, (ii) privacy, and (iii) efficient searching of any tagged object, MAX provides location information in a form natural to humans, that is, with reference to identifiable landmarks (such as, “on the dining table”) rather than precise coordinates. In the system, all physical objects—from documents to clothing—can be tagged, users then locate objects using an intuitive search interface. To make searching efficient, MAX adopts a hierarchical architecture consisting of tags (bound to objects), substations (bound to landmarks), and base-stations (bound to localities). Tags can be marked as either public or private, with private tags searchable only by the owner. MAX also provides for privacy of physical spaces. It requires minimal initial configuration, and is robust to reconfiguration of the physical space. We also present a methodology to design energy-optimal and delay-optimal query protocols for a variety of device choices, this optimizes system performance, and affords insight into the appropriate actions for various scenarios. We have implemented a simple prototype of MAX, demonstrating the feasibility of the system for human-centric search over several locations across a wide area. We contend that a MAX-like search system will enable sharing (e.g., books on a college campus) and trading (e.g., buying and selling used books) of physical resources, and will be the engine for a host of new applications.

The capacity region of a class of discrete memoryless interference channels is established. The setup is similar to the class of deterministic interference channels studied by El Gamal and Costa. However, we relax certain conditions that were imposed by El Gamal and Costa. The capacity region of this class of interference channels also includes the capacity region of the discrete memoryless interference channels with strong interference. Finally, we extend the result to the case where both transmitters have a common message to transmit.

In this paper, we study a routing problem on the Gaussian multiple relay channel, in which nodes employ a decode-and-forward coding strategy. We are interested in routes for the information flow through the relays that achieve the highest DF rate. We first construct an algorithm that provably finds optimal DF routes. As the algorithm runs in factorial time in the worst case, we propose a polynomial time heuristic algorithm that finds an optimal route with high probability. We demonstrate that that the optimal (and near optimal) DF routes are good in practice by simulating a distributed DF coding scheme using low density parity check codes with puncturing and incremental redundancy.

Recently, a new notion of cooperation was proposed to solve multi-channel coordination problems. When a transmit-receive pair wishes to initiate communication, neighboring nodes share their knowledge of channel usage. This helps to substantially reduce collisions and increases throughput significantly. However, it comes at the cost of increased energy consumption since idle nodes have to stay awake to overhear and acquire channel usage information. In fact this can be as high as 264% of a power-saving protocol without cooperation. In this paper, we propose a strategy called altruistic cooperation for cooperative multi-channel MAC protocols to conserve energy. The core idea is to introduce specialized nodes called altruists in the network whose only role is to acquire and share channel usage information. All other nodes, termed peers, go in to the sleep mode when idle. This strategy seems naive because it needs additional nodes to be deployed. In fact, it is unclear whether a desirable throughput-energy trade-off can be achieved and whether the cost of additional nodes can offset the performance gain. We perform a close study on this strategy in terms of three aspects: network deployment, cost efficiency, and system performance. Our study indicates that only a few additional nodes need to be deployed and cost efficiency is more than doubled in terms of a new metric called bit-price ratio that we propose. By using the strategy, a cooperative protocol is found to save up to 70% energy while not compromising throughput.

In many delay tolerant applications, information is opportunistically exchanged between mobile devices who encounter each other. In order to effect such information exchange, mobile devices must have knowledge of other devices in their vicinity. We consider scenarios in which there is no infrastructure and devices must probe their environment to discover other devices. This can be an extremely energy consuming process and highlights the need for energy conscious contact probing mechanisms. If devices probe very infrequently, they might miss many of their contacts. On the other hand, frequent contact probing might be energy inefficient. In this paper, we investigate the trade-off between the probability of missing a contact and the contact probing frequency. First, via theoretical analysis, we characterize the trade-off between the probability of a missed contact and the contact probing interval for stationary processes. Next, for time varying contact arrival rates, we provide an optimization framework to compute the optimal contact probing interval as a function of the arrival rate. We characterize real world contact patterns via Bluetooth phone contact logging experiments and show that the contact arrival process is self-similar. We design STAR, a contact probing algorithm which adapts to the contact arrival process. Via trace driven simulations on our experimental data, we show that STAR consumes three times less energy when compared to a constant contact probing interval scheme.

In order to meet the requirements of real-time applications, Optical Burst Switched backbone networks need to provide quantitative edge-to-edge loss guarantees to traffic flows. For this purpose, there have been several proposals based on the relative differentiation quality of service (QoS) model. However, this model has an inherent difficulty in communicating information about internal network states to the edge in a timely manner for making admission control decisions. In this paper, we propose an absolute QoS framework to overcome this difficulty. The key idea is to offer quantitative loss guarantees at each hop using a differentiation mechanism and an admission control mechanism. The edge-to-edge loss requirement is then translated into a series of small per-node loss probabilities that are allocated to the intermediate core nodes. The framework includes a preemptive differentiation scheme, a node-based admission control scheme and an edge-to-edge reservation scheme. The schemes are analyzed and evaluated through simulation. It is shown that the framework can effectively offer quantitative edge-to-edge loss guarantees under various traffic conditions.

This correspondence studies coding strategies for a three-node relay channel. We start with the basic coding strategies of Cover and El Gamal: the relay decodes the source message and forward it to the destination (cooperation); the relay transmits its compressed channel outputs to the destination (facilitation); or the relay superimposes both cooperation and facilitation (generalized). In this paper, two new generalized strategies superimposing cooperation and facilitation are introduced and investigated on the general relay channel. The first strategy makes use of sequential backward (SeqBack) decoding while the second strategy makes use of simultaneous backward (SimBack) decoding. The achievable rate for the second strategy is shown to include that of the generalized strategy of Cover and El Gamal. Assuming zero-mean, jointly Gaussian random variables, the two new strategies give higher achievable rates than the generalized strategy of Cover and El Gamal for certain parameters on the Gaussian relay channel

We consider the two-user Z channel (ZC), where there are two senders and two receivers. One of the senders transmits information to its intended receiver (without interfering with the unintended receiver), while the other sender transmits information to both receivers. The complete characterization of the discrete memoryless ZC remains unknown to date. For the Gaussian ZC, the capacity has only been established for a crossover link gain of $1$. In this work, we study both the discrete memoryless ZC and the Gaussian ZC. We first establish achievable rates for the general discrete memoryless ZC. The coding strategy uses rate-splitting and superposition coding at the sender with information for both receivers. At the receivers, we use joint decoding. We then specialize the rates obtained to two different types of degraded discrete memoryless ZCs and also derive respective outer bounds to their capacity regions. We show that as long as a certain condition is satisfied, the achievable rate region is the capacity region for one type of degraded discrete memoryless ZC. The results are then extended to the two-user Gaussian ZC with different crossover link gains. We determine an outer bound to the capacity region of the Gaussian ZC with strong crossover link gain and establish the capacity region for moderately strong crossover link gain.

The multiple-access channel with feedback and correlated sources (MACFCS) models a sensor network in which sensors collect and transmit correlated data to a common sink. We present four achievable rate regions and a capacity outer bound for the MACFCS. For the first achievable region, we construct a decode-forward based coding strategy. The sources first exchange their data, and then cooperate to send full information to the destination. We term this strategy full decoding at sources with decode-forward (FDS-DF). For two of the other achievable regions, we first perform Slepian–Wolf coding to remove the correlation among the source data. This is followed by either (i) a compress-forward based coding strategy for the multiple-access channel with feedback, or (ii) an existing coding strategy for the multiple-access channel. We also find another achievable region using a multihop coding strategy, which only uses point-to-point coding (no cooperation). From numerical computations, we see that different strategies perform better under certain source correlation structures and network topologies. More specifically, FDS-DF approaches the capacity when (i) the inter-source distance decreases, or (ii) the correlation among the sources gets higher. Furthermore, the cooperative coding strategies considered support larger achievable rate regions than the noncooperative multihop strategy.

Achieving energy efficiency to prolong the network lifetime is an important design criterion for wireless sensor networks. In this article, we propose a novel approach that exploits the broadcast nature of the wireless medium for energy conservation in spatially correlated wireless sensor networks. Since wireless transmission is inherently broadcast, when one sensor node transmits, other nodes in its coverage area can receive the transmitted data. When data collected by different sensors are correlated, each sensor can utilize the data it overhears from other sensors to compress its own data and conserve energy in its own transmissions. We apply this idea to a class of cluster-based wireless sensor networks in which each sensing node transmits collected data directly to its cluster head using time division multiple access (TDMA). We formulate the problem in which sensors in each cluster collaborate their transmitting, receiving, and compressing activities to optimize their lifetimes. We show that this lifetime optimization problem can be solved by a sequence of linear programming problems. We also propose a heuristic scheme which has low complexity and achieves near optimal performance. Important characteristics of wireless sensor networks such as node startup cost and packet loss due to transmission errors are also considered. Numerical results show that by exploiting the broadcast nature of the wireless medium, our control schemes achieve significant improvement in the sensors' lifetimes.

Medium access control (MAC) protocols have been studied under different contexts for several years now. In all these MAC protocols, nodes make independent decisions on when to transmit a packet and when to back-off from transmission. In this paper, we introduce the notion of node cooperation into MAC protocols. Cooperation adds a new degree of freedom which has not been explored before. Specifically we study the design of cooperative MAC protocols in an environment where each node is equipped with a single transceiver and has multiple channels to choose from. Nodes cooperate by helping each other select a free channel to use. We show that this simple idea of cooperation has several qualitative and quantitative advantages. Our cooperative asynchronous multi-channel MAC protocol (CAM-MAC) is extremely simple to implement and, unlike other multi-channel MAC protocols, is naturally asynchronous. We conduct extensive simulation experiments. We first compare CAM-MAC with IEEE 802.11b and a version of CAM-MAC with the cooperation element removed. We use this to show the value of cooperation. Our results show significant improvement in terms of number of collisions and throughput for CAM-MAC. We also compare our protocol with MMAC and SSCH and show that CAM-MAC significantly outperforms both of them.

10.1109/INFOCOM.2006.118

We consider the two-user Gaussian zigzag channel, where there are two senders and two receivers. One of the senders transmits information to its intended receiver (without interfering with the unintended receiver) while the other sender transmits information to both receivers. We first establish achievable rates for the discrete memoryless zigzag channel under strong interference which can be extended to the Gaussian zigzag channel with strong and very strong crossover link gain (a2ges 1). We also determine an outer bound for the Gaussian zigzag channel under strong and very strong crossover link gain (a2ges 1). Moreover, we establish the capacity of the Gaussian zigzag channel under (strictly) strong crossover link gain (1 les a2les 1 + P1)

In this paper, we derive the capacity of a special class of mesh networks. A mesh network is defined as a heterogeneous wireless network in which the transmission among power limited nodes is assisted by powerful relays, which use the same wireless medium. We find the capacity of the mesh network when there is one source, one destination, and multiple relays. We call this channel the single source multiple relay single destination (SSMRSD) mesh network. Our approach is as follows. We first look at an upper bound on the information theoretic capacity of these networks in the Gaussian setting. We then show that the bound is achievable asymptotically using the compress-forward strategy for the multiple relay channel. Theoretically, the results indicate the value of cooperation and the utility of carefully deployed relays in wireless ad-hoc and sensor networks. The capacity characterization quantifies how the relays can be used to either conserve node energy or to increase transmission rate

In this paper, we investigate communication strategies for the multiple access channel with feedback and correlated sources (MACFCS). The MACFCS models a wireless sensor network scenario in which sensors distributed throughout an arbitrary random field collect correlated measurements and transmit them to a common sink. We derive achievable rate regions for the three-node MACFCS. First, we study the strategy when source coding and channel coding are combined, which we term full decoding at sources. Second, we look at several strategies when source coding and channel coding are separated, which we term full decoding at destination. From numerical computations on Gaussian channels, we see that different strategies perform better under certain source correlations and channel setups

Characterizing mobility or contact patterns in a campus environment is of interest for a variety of reasons. Existing studies of these patterns can be classified into two basic approaches - model based and measurement based. The model based approach involves constructing a mathematical model to generate movement patterns while the measurement based approach measures locations and proximity of wireless devices to infer mobility patterns. In this paper, we take a completely different approach. First we obtain the class schedules and class rosters from a university-wide Intranet learning portal, and use this information to infer contacts made between students. The value of our approach is in the population size involved in the study, where contact patterns among 22341 students are analyzed. This paper presents the characteristics of these contact patterns, and explores how these patterns affect three scenarios. We first look at the characteristics from the DTN perspective, where we study inter-contact time and time distance between pairs of students. Next, we present how these characteristics impact the spread of mobile computer viruses, and show that viruses can spread to virtually the entire student population within a day. Finally, we consider aggregation of information from a large number of mobile, distributed sources, and demonstrate that the contact patterns can be exploited to design efficient aggregation algorithms, in which only a small number of nodes (less than 0.5%) is needed to aggregate a large fraction (over 90%) of the data.

In this paper, we present simulation-based studies of the performance and tradeoffs of cooperative communications in wireless ad-hoc networks. While cooperative schemes can potentially improve throughput performance, this improvement often comes at a price in terms of higher energy consumption and the involvement of additional nodes. As such, we contend that it is worthwhile to consider schemes that adapt to different link conditions such that cooperation is only invoked when necessary. We study these issues quantitatively by looking at the throughput and energy consumption of cooperative and non-cooperative schemes in a 3-node network. In particular, two different modes of cooperation, namely multihop routing and cooperative relaying, are considered. We aim to determine which modes of cooperation work well under a variety of link conditions and how their performances compare against direct transmissions. Our results are uniquely presented through vivid graphical representations, which facilitate visualization and easy comparison between the different transmission modes

In this paper, we describe and study a phenomenon unique to bufferless optical burst switched (OBS) networks called the streamline effect. This is the phenomenon wherein bursts within an input stream to a core node only contend with those from other input streams but not among themselves. It causes the burst loss probability at a link to depend strongly on the number of input streams to the link and their relative burst rates. We analyse the streamline effect and provide a burst loss probability formula that is more accurate than the traditionally used Erlang B formula. The formula is then used in a load balancing scheme for reservation-based quality of service (QoS) traffic to give a better link cost function. Through extensive simulation experiments for different traffic scenarios, we show that the proposed load balancing scheme utilising the streamline effect performs better than the shortest path routing scheme and the load balancing scheme without considering the streamline effect.

Of late, there has been an avalanche of cross-layer design proposals for wireless networks. A number of researchers have looked at specific aspects of the network performance and, by approaching cross-layer design as per their interpretation of what it implies, presented several cross-layer design proposals involving different layers of the protocol stack. There have also been works relating to the implementation of cross-layer interactions. It is high time that these various individual efforts be put into perspective and a more holistic view be taken. This paper is a step in that direction. In this paper, we take stock of the existing work in the area of cross-layer design. We do so by suggesting a definition for cross-layer design, by creating a taxonomy of the existing cross-layer design proposals, and by categorizing the initial proposals on how cross-layer interactions can be implemented. We then extract the key insights from the current literature regarding which layers need to be coupled and in what ways. Finally, we highlight some open challenges and new opportunities for cross-layer design that designers can start addressing as they move forward.

The objective of this paper is to exploit the broadcast nature of the wireless medium for energy conservation in spatially correlated wireless sensor networks. Since wireless transmission is inherently-broadcast when one sensor node transmits, other nodes in its coverage area can receive the transmitted data. When data collected by different sensors are correlated, each sensor can utilize the data it overhears from other sensors to compress its own data and conserve energy in its own transmissions. We apply this idea to a class of cluster-based wireless sensor networks and formulate the problem of optimizing the lifetimes of all nodes in each cluster. By optimal, we mean that any other policy cannot increase the lifetime of the node which dies first. We show that this optimization problem can be structured as a linear programming problem. We also propose a heuristic policy, which has low complexity and achieves near optimal performance.

The vertical Bell-labs layered space-time (VBLAST) scheme can be used to exploit the capacity potential provided by multiple transmit antenna systems. In VBLAST systems, detection and decoding are performed layer by layer in a successive way. However, successive processing degrades performance because of the low minimum diversity and error propagation. In this paper, we propose a new STBC-VBLAST scheme, which integrates G orthogonal n/spl times/m space-time block codes (STBC) into the lower layers of VBLAST systems with n/sub T/ transmit and n/sub R/ receive antennas. The remaining higher layers transmit independent data streams. At the receiver, low-complexity detection with modified sorted QR decomposition (SQRD) and successive interference cancellation is used. With STBC-VBLAST, the minimum diversity d among all the layers is the smaller of n(n/sub R/-n/sub T/) + n/sup 2/ and n/sub R/-n/sub T/ +Gn + 1, which is generally larger than that for other VBLAST systems. Noting that the performance improvement is accompanied by a partial loss in spectral efficiency, we also indicate how to choose G to get good performance while using bandwidth efficiently.

This paper studies coding strategies for a three-node relay channel. We first review the basic coding strategies of Cover and El Gamal for the relay channel. Next, two new coding strategies superimposing cooperation and facilitation are developed. One of the coding strategies is shown to include the generalized strategy of Cover and El Gamal. For certain parameters of the Gaussian relay channel, the two new strategies give higher achievable rates than the generalized strategy of Cover and El Gamal

In this paper, we investigate achievable rates for data transmission from sources to sinks through multiple relay networks. We consider myopic coding, a constrained communication strategy in which each node has only a local view of the network, meaning that nodes can only transmit to and decode from neighboring nodes. We compare this with omniscient coding, in which every node has a global view of the network and all nodes can cooperate. Using Gaussian channels as examples, we find that when the nodes transmit at low power, the rates achievable with two-hop myopic coding are as large as that under omniscient coding in a five-node multiple relay channel and close to that under omniscient coding in a six-node multiple relay channel. These results suggest that we may do local coding and cooperation without compromising much on the transmission rate. Practically, myopic coding schemes are more robust to topology changes because encoding and decoding at a node are not affected when there are changes at remote nodes. Furthermore, myopic coding mitigates the high computational complexity and large buffer/memory requirements of omniscient coding

People often seek information by asking other people even when they have access to vast reservoirs of information such as the Internet and libraries. This is because people are great sources of unique information, especially that which is location-specific, community-specific and time-specific. Social networking is effective because this type of information is often not easily available anywhere else. In this paper, we conceive a wireless virtual social network which mimics the way people seek information via social networking. PeopleNet is a simple, scalable and low-cost architecture for efficient information search in a distributed manner. It uses the infrastructure to propagate queries of a given type to users in specific geographic locations, called bazaars. Within each bazaar, the query is further propagated between neighboring nodes via peer-to-peer connectivity until it finds a matching query. The PeopleNet architecture can overlay easily on existing cellular infrastructure and entails minimal software installation. We identify three metrics for system performance: (i) probability of a match, (ii) time to find a match and (iii) number of matches found by a query. We describe two simple models, called the swap and spread models, for query propagation within a bazaar. We qualitatively argue that the swap model is better with respect to the performance metrics identified and demonstrate this via simulations. Next, we compute analytically the probability of match for the swap model. We show that the probability of match can be significantly improved if, prior to swapping queries, the nodes exchange some limited information about their buffer contents. We propose a simple greedy algorithm which uses this limited information to decide which queries to swap. We show via simulation that this algorithm achieves significantly better performance. Overall our results demonstrate that PeopleNet, with its bazaar concept and peer-to-peer query propagation, can provide a simple and efficient mechanism for seeking information.

MAX is a system that facilitates human-centric search of the physical world. It allows humans to search for and locate objects as and when they need it instead of organizing them a priori. It provides location information in a form natural to humans, i.e., with reference to identifiable landmarks (e.g., on the dining table) rather than precise coordinates. MAX was designed with the following objectives: (i) human-centric operation, (ii) privacy, and (iii) efficient search of any tagged object. In the system, all physical objects, from documents to clothing, can be tagged and people locate objects using an intuitive search interface. To make search efficient, MAX adopts a hierarchical architecture consisting of tags (bound to objects), sub-stations (bound to landmarks) and base-stations (bound to localities). Tags can be marked as either public or private, with private tags searchable only by the owner. MAX also provides for privacy of physical spaces.MAX requires minimal initial configuration, and is robust to reconfiguration of the physical space. To optimize system performance, we present a methodology to design energy and delay optimal query protocols for a variety of device choices. We have implemented MAX using Crossbow motes and conducted user trials in a 5m by 5m cluttered office. The user feedback was positive, demonstrating the feasibility of MAX for human-centric search. We contend that a MAX-like search system will enable sharing (e.g., books on a college campus) and trading (e.g., buying and selling used books) of physical resources, and will be the engine for a host of new applications.

Recently, some absolute QoS schemes have been proposed to offer quantitative loss guarantees at core nodes in OBS networks. By moving the admission control process to core nodes, which have the most updated information about their own traffic conditions, these schemes can provide reliable and robust per-link loss guarantees. However, the issue of how to provide edge-to-edge guarantees for burst flows over the entire edge-to-edge paths have not been investigated in any of the proposals. In this paper, we propose a signalling and reservation scheme to coordinate the reservation and teardown process over the edge-to-edge path in the absolute QoS model. The key idea is to judiciously divide the edge-to-edge loss requirement into a series of small loss probabilities that are allocated to the intermediate links. The performance of the scheme is evaluated through simulation.

In wireless data communications, it has been realized that by adapting the transmit power and rate, not only to the channel conditions, but also to higher layer parameters, such as the buffer occupancy and data arrival statistics, the system performance can be significantly improved. However, most of the existing approaches deal only with single user scenarios. In this paper, we consider a multiuser scenario in which N users share a common time-varying wireless channel. During each time slot, a scheduler allows only one user to access the common channel for data transmission. We show that, under certain scheduling policies, the problem of optimal adaptive transmission for this multiuser system can be decoupled into N single-user problems. This allows the use of optimal adaptive single-user policies, where the adaptation is done with respect to each user's effective channel.

An efficient adaptive list decoder for Reed-Solomon (RS) codes by adaptively adjusting the list size is presented. Simulations show that it performs better than the Koetter-Vardy decoder (KVD) for small list sizes, with only a marginal increase in complexity. For larger list sizes, we propose an iterative decoder which, when applied to a parallel concatenated RS code, performs significantly better than the KVD, applied to an RS code of the same rate.

We consider the problem of buffer and channel adaptive transmission over fading channels. In the model, data packets arrive stochastically into a finite-length buffer which transmits them over a time-varying correlated fading channel. We assume that knowledge of the buffer occupancy and the fading state is available at the transmitter. The objective is to vary the transmission power and rate according to the buffer and channel conditions so that the long-term system throughput is maximized under some average transmission power constraint. Here, maximizing the system throughput is equivalent to minimizing packet loss due to both buffer overflow and transmission error. We formulate this optimization problem as a Markov decision process (MDP) and use dynamic programming techniques to obtain the solution. Next, we look at the effects of error and delay in the channel state information and propose an optimal adaptive policy that is obtained by formulating a partially observable Markov decision process (POMDP). Simulation results are given to show the performance of the policies over fading channels with perfect and imperfect channel state information.

We consider the problem of adaptive modulation for increasing the throughput of transmission over fading channels. In the model, packets arrive at a finite-length buffer according to a Poisson distribution and are mapped into M-ary quadrature amplitude modulated (MQAM) symbols for transmission over a correlated Rayleigh fading channel. We assume that buffer and channel state information are always available at the transmitter. Our objective is to vary the transmit power and the signal constellation size of the modulator according to both the buffer and channel states so that the system throughput is maximized under some average transmit power and bit error rate (BER) constraints. We formulate this optimization problem as a Markov decision process (MDP) and use dynamic programming techniques to obtain the solution. More importantly, we show that, under certain conditions, the optimal transmission rate increases when the channel gain decreases toward the outage threshold - the point below which communication is not possible. This is in contrast to the water-filling structure of the link adaptive policy that achieves capacity on fading channels.

It is well known that jointly optimal multiuser detection for code division multiplex access (CDMA) systems has complexity which grows exponentially with the number of users. Recently, several authors [S. Ulukus and R. D. Yates, April 1998], [C. Sankaran and A. Ephremides, Sept. 1998], [C. Schlegel and A. Grant, 2000] have reported that, for certain special sets of spreading sequences, optimal multiuser detection in synchronous CDMA systems can be performed with computational complexity which is polynomial in the number of users. In this paper, we show that the existing polynomial complexity (PC) algorithms of [S. Ulukus and R. D. Yates, April 1998], [C. Sankaran and A. Ephremides, Sept. 1998], [C. Schlegel and A. Grant, 2000] lead to efficient algorithms for a wider class of spreading sequences than initially proposed. We identify these sequences and prove the existence of optimal polynomial-complexity algorithms for detecting synchronous CDMA signals using these sequences. We also give constructions of sets of binary antipodal spreading sequences for which optimal polynomial-complexity algorithms exist and show that for any sequence length N, we can construct at least N such sequences.

In this paper, we provide a new scheme for transmission of video information over wireless channels. This scheme is constructed by combining the prioritized discrete cosine transform (DCT) for video compression with multiple description codes based on forward error correction (FEC) codes. Reed-Solomon codes with different error correction abilities are applied to different parts of the progressive source bitstream, and finally these blocks are split into several equal descriptions for transmission. The prioritized DCT coder gives a wonderful progressive feature with less complexity and can be easily combined with the FEC based multiple description generation. We demonstrate via simulation that this scheme can improve the robustness of video transmission over wireless channels and allow video quality to degrade gracefully as channel conditions worsen.

This paper analyzes the performance of the linear parallel interference cancellation (LPIC) multiuser detector in a synchronous multiuser communication scenario with binary signaling, nonorthogonal multiple access interference, and an additive white Gaussian noise channel. The LPIC detector has been considered in the literature lately due to its low computational complexity, potential for good performance under certain operating conditions, and close connections to the decorrelating detector. In this paper, we compare the performance of the two-stage LPIC detector to the original multistage detector proposed by Varanasi and Aazhang (1990, 1991) for CDMA systems. The general M-stage LPIC detector is compared to the conventional matched filter detector to describe operating conditions where the matched filter detector outperforms the LPIC detector in terms of error probability at any stage M. Analytical results are presented that show that the LPIC detector may exhibit divergent error probability performance under certain operating conditions and may actually yield error probabilities greater than 0.5 in some cases. Asymptotic results are presented for the case where the number of LPIC stages goes to infinity. Implications of the prior results for code division multiple access (CDMA) systems with random binary spreading sequences are discussed in the "large-system" scenario. Our results are intended to analytically corroborate the simulation evidence of other authors and to provide cautionary guidelines concerning the application of LPIC detector to CDMA communication systems.