Enhancing the reasoning capabilities of language models (LMs) remains a key challenge, especially for tasks that require complex, multistep decision-making where existing Chain-of-Thought (CoT) approaches struggle with consistency and verification.In this paper, we propose a novel reasoning framework, referred to as Structure-aware Planning with an Accurate World Model (SWAP), that integrates structured knowledge representation with learned planning.Unlike prior methods that rely purely on natural language reasoning, SWAP leverages entailment graphs to encode structured dependencies and enable symbolic verification of intermediate steps.To systematically construct and update the graph, SWAP employs a policy model to propose candidate expansions and a world model to predict structural updates.To improve accuracy, the world model generates multiple alternative updates, and a discriminator re-ranks them based on plausibility.To encourage diverse exploration, we introduce Diversity-based Modelling (DM), which samples candidates from the remaining probability mass after removing previously sampled candidates from the original policy distribution.Additionally, SWAP improves the discrimination accuracy through Contrastive Ranking (CR), which directly compares candidates within prompts and incorporates metaknowledge to improve ranking quality.We evaluate SWAP across diverse reasoning-intensive benchmarks including math reasoning, logical reasoning, and coding tasks.Extensive experiments demonstrate that SWAP significantly improves upon the base models and consistently outperforms existing reasoning methods 1 .

Recent major developments in semantic communication systems stem from integration of deep learning (DL) techniques. Following the discovery of capacity achieving codes, the primary motivation for adopting the semantic approach, which retrieves meaning without requiring an exact reconstruction, is its potential to further conserve resources such as bandwidth and power. In this paper, we propose a novel semantic communication framework for textual data over additive white Gaussian noise (AWGN) channels via DL. Our framework leverages the information bottleneck (IB) principle to balance minimizing bit transmission under wireless channel rate constraints with maximizing semantic information retention. Unlike previous works, we integrate the bilingual evaluation understudy (BLEU) sentence similarity score into the training objective to enhance model performance. In particular, inspired by knowledge distillation, we utilize large language models (LLMs) during training to transfer their knowledge of text semantics into our model. Using IB principle, we train a neural semantic encoder at the transmitter and a neural semantic decoder at the receiver that incorporates into its objective function the rate constraint together with the BLEU score and the knowledge encoded in the soft probabilities produced by the LLM. Through extensive experiments, our proposed framework demonstrates a notable improvement of up to 45% in text semantic similarity compared to state-of-the-art benchmarks operating at the same channel capacity, significantly outperforming traditional communication systems. Moreover, it exhibits robustness to variations in signal-to-noise ratio (SNR) and achieves significant gains across both low and medium SNR regimes.

This work presents an analysis of semantic communication in the context of First-Order Logic (FOL)-based deduction. Specifically, the receiver holds a set of hypotheses about the State of the World (SotW), while the transmitter has incomplete evidence about the true SotW but lacks access to the ground truth. The transmitter aims to communicate limited information to help the receiver identify the hypothesis most consistent with true SotW. We formulate the objective as approximating the posterior distribution at the transmitter to the receiver. Using Stirling’s approximation, this reduces to a constrained, finite-horizon resource allocation problem. Applying the Karush-Kuhn-Tucker conditions yields a truncated water-filling solution. Despite the problem’s non-convexity, symmetry and permutation invariance ensure global optimality. Based on this, we design message selection strategies, both for single- and multi- round communication, and model the receiver’s inference as an m-ary Bayesian hypothesis testing problem. Under the Maximum A Posteriori (MAP) rule, our communication strategy achieves optimal performance within budget constraints. We further analyze convergence rates and validate the theoretical findings through experiments, demonstrating reduced error over random selection and prior methods.

One of the fundamental challenges in reinforcement learning RL is to take a complex task and be able to decompose it to subtasks that are simpler for the RL agent to learn. In this paper, we report on our work that would identify subtasks by using some given positive and negative trajectories for solving the complex task. We assume that the states are represented by first-order predicate logic using which we devise a novel algorithm to identify the subtasks. Then we employ a Large Language Model (LLM) to generate first-order logic rule templates for achieving each subtask. Such rules were then further fined tuned to a rule-based policy via an Inductive Logic Programming (ILP)-based RL agent. Through experiments, we verify the accuracy of our algorithm in detecting subtasks which successfully detect all of the subtasks correctly. We also investigated the quality of the common-sense rules produced by the language model to achieve the subtasks. Our experiments show that our LLM-guided rule template generation can produce rules that are necessary for solving a subtask, which leads to solving complex tasks with fewer assumptions about predefined first-order logic predicates of the environment.

Understanding causal relationships between variables is fundamental across scientific disciplines. Most causal discovery algorithms rely on two key assumptions: (i) all variables are observed, and (ii) the underlying causal graph is acyclic. While these assumptions simplify theoretical analysis, they are often violated in real-world systems, such as biological networks. Existing methods that account for confounders either assume linearity or struggle with scalability. To address these limitations, we propose DCCD-CONF, a novel framework for differentiable learning of nonlinear cyclic causal graphs in the presence of unmeasured confounders using interventional data. Our approach alternates between optimizing the graph structure and estimating the confounder distribution by maximizing the log-likelihood of the data. Through experiments on synthetic data and real-world gene perturbation datasets, we show that DCCD-CONF outperforms state-of-the-art methods in both causal graph recovery and confounder identification. Additionally, we provide consistency guarantees for our framework, reinforcing its theoretical soundness.

In this paper, we address the problem of lossy semantic communication to reduce uncertainty about the State of the World (SotW) for deductive tasks in point to point communication. A key challenge is transmitting the maximum semantic information with minimal overhead suitable for down-stream applications. Our solution involves maximizing semantic content information within a constrained bit budget, where SotW is described using First-Order Logic, and content informativeness is measured by the usefulness of the transmitted information in reducing the uncertainty of the SotW perceived by the receiver. Calculating content information requires computing inductive logical probabilities of state descriptions; however, naive approaches are infeasible due to the massive size of the state space. To address this, our algorithm draws inspiration from state-of-the-art model counters and employs tree search-based model counting to reduce the computational burden. These algorithmic model counters, designed to count the number of models that satisfy a Boolean equation, efficiently estimate the number of world states that validate the observed evidence. Empirical validation using the FOLIO and custom deduction datasets demonstrate that our algorithm reduces uncertainty and improves task performance with fewer bits compared to baselines.

Conventional embedding-based models approach event time prediction in temporal knowledge graphs (TKGs) as a ranking problem. However, they often fall short in capturing essential temporal relationships such as order and distance. In this paper, we propose TEILP, a logical reasoning framework that naturaly integrates such temporal elements into knowledge graph predictions. We first convert TKGs into a temporal event knowledge graph (TEKG) which has a more explicit representation of time in term of nodes of the graph. The TEKG equips us to develop a differentiable random walk approach to time prediction. Finally, we introduce conditional probability density functions, associated with the logical rules involving the query interval, using which we arrive at the time prediction. We compare TEILP with state-of-the-art methods on five benchmark datasets. We show that our model achieves a significant improvement over baselines while providing interpretable explanations. In particular, we consider several scenarios where training samples are limited, event types are imbalanced, and forecasting the time of future events based on only past events is desired. In all these cases, TEILP outperforms state-of-the-art methods in terms of robustness.

While large language models (LLMs) have demonstrated remarkable reasoning capabilities, they are not without their flaws and inaccuracies.Recent studies have introduced various methods to mitigate these limitations.Temporal reasoning (TR), in particular, presents a significant challenge for LLMs due to its reliance on diverse temporal concepts and intricate temporal logic.In this paper, we propose TG-LLM, a novel framework towards languagebased TR.Instead of reasoning over the original context, we adopt a latent representation, temporal graph (TG) that enhances the learning of TR.A synthetic dataset (TGQA), which is fully controllable and requires minimal supervision, is constructed for fine-tuning LLMs on this text-to-TG translation task.We confirmed in experiments that the capability of TG translation learned on our dataset can be transferred to other TR tasks and benchmarks.On top of that, we teach LLM to perform deliberate reasoning over the TGs via Chain-of-Thought (CoT) bootstrapping and graph data augmentation.We observed that those strategies, which maintain a balance between usefulness and diversity, bring more reliable CoTs and final results than the vanilla CoT distillation. 1 * Equal contribution. 1 Code and data are available at https://github.com/ xiongsiheng/TG-LLM.Once upon a time in the quaint town of Weston, a baby boy named John Thompson was brought into the world in the year 1921.Growing up, he had a vibrant spirit and an adventurous soul.…Step 1: Text-to-Temporal Graph Translation True or false: event (John Thompson owned Pearl Network) was longer in duration than event (Sophia Parker was married to John Thompson) ?The duration for each event can be calculated as follows:(John Thompson owned Pearl Network) starts at 1942, ends at 1967

Advancements in logical reasoning, utilizing LLMs to convert natural language into logical symbolism, combined with the use of external theorem provers, have repositioned the symbolic approach as a central point of interest. The main challenge within this paradigm lies in the LLMs’ capability to accurately translate natural language (NL) statements into first-order-logic (FOL) expressions. Although LLMs have shown notable success, there remains a gap in understanding the limitations and challenges they encounter in NL-FOL translation. This is primarily due to the absence of datasets and evaluation test beds at the required fine-grained level. We present MALLS, a dataset of 28K diverse and verified sentence-level NL-FOL pairs collected from GPT4. We utilize a combined strategy of FOL rule parsing, human annotation, and automatic filtering to ensure quality. We also present LogicLLaMA, a LLaMA2-7B/13B fine-tuned on MALLS for NL-FOL translation, which can be used standalone or to correct previously generated rules by GPT3.5 after being further fine-tuned via a novel reinforcement learning with human feedback (RLHF) framework. We benchmark a wide range of LLMs on MALLS and previous datasets, highlighting weaknesses in them in NL-FOL translation and demonstrating the advantages of MALLS. We also show that LogicLLaMA achieves GPT4-level performance and can generalize to other datasets. Project repo is available at https://github.com/gblackout/LogicLLaMA

In this paper, we consider distributed Independent Component Analysis (ICA) in wireless networks, where data from several geographically distributed wireless nodes (nodes) must be transmitted to a central server (server) to extract original sources through ICA. However, transmitting the vast amount of data over wireless channels to the server poses significant challenges due to limited bandwidth and privacy concerns. Our research addresses how to encode node data to meet channel rate constraints while providing maximally relevant information for ICA. Particularly, we propose a distributed functional compression framework for learning ICA over orthogonal AWGN channels. The framework leverages the Information Bottleneck (IB) principle to encode and compress the data to meet the channel rate constraint while maximally preserving the functionally relevant information for ICA. We train both neural encoders at the nodes and a neural decoder at the server in an unsupervised manner using the IB principle. We consider ICA for both linear and nonlinear mixing setups. Compared to the state-of-the-art, over real dataset, our proposed framework demonstrates a remarkable improvement of up to approximately 43% in accurately estimating the source signals in ICA while meeting the channels’ rate constraints. Finally, we propose a three-stage training algorithm, where the raw sensory data never leaves the nodes either for training or inference, to reduce the communication overhead. We show that our proposed training algorithm notably reduces channel use compared to the traditional cloud-based method, where the observed data from the nodes are compressed and transmitted to the cloud for learning ICA.

In this paper, we consider the parallel implementation of an already-trained deep model on multiple processing nodes (a.k.a. workers). Specifically, we investigate as to how a deep model should be divided into several parallel sub-models, each of which is executed efficiently by a worker. Since latency due to synchronization and data transfer among workers negatively impacts the performance of the parallel implementation, it is desirable to have minimum interdependency among parallel sub-models. To achieve this goal, we propose to rearrange the neurons in the neural network, partition them (without changing the general topology of the neural network), and modify the weights such that the interdependency among sub-models is minimized under the computations and communications constraints of the workers while minimizing its impact on the performance of the model. We propose RePurpose, a layer-wise model restructuring and pruning technique that guarantees the performance of the overall parallelized model. To efficiently apply RePurpose, we propose an approach based on L0 optimization and the Munkres assignment algorithm. We show that, compared to the existing methods, RePurpose significantly improves the efficiency of the distributed inference via parallel implementation, both in terms of communication and computational complexity.

Learning causal relationships between variables is a well-studied problem in statistics, with many important applications in science. However, modeling real-world systems remain challenging, as most existing algorithms assume that the underlying causal graph is acyclic. While this is a convenient framework for developing theoretical developments about causal reasoning and inference, the underlying modeling assumption is likely to be violated in real systems, because feedback loops are common (e.g., in biological systems). Although a few methods search for cyclic causal models, they usually rely on some form of linearity, which is also limiting, or lack a clear underlying probabilistic model. In this work, we propose a novel framework for learning nonlinear cyclic causal graphical models from interventional data, called NODAGS-Flow. We perform inference via direct likelihood optimization, employing techniques from residual normalizing flows for likelihood estimation. Through synthetic experiments and an application to single-cell high-content perturbation screening data, we show significant performance improvements with our approach compared to state-of-the-art methods with respect to structure recovery and predictive performance.

The first arrival time of seismic waves is a crucial parameter for seismic data analysis, which is used to determine the depth and location of subsurface structures. However, the estimation of first arrival time is often challenging due to the presence of noise and uncertainties in the data. In this study, we propose a novel approach that utilizes the Kalman filter with generalized likelihood ratio (GLR) to estimate the first arrival time in seismic data. First, a discrete time linear system with unknown amplitudes changes occurring at unknown time instants is used to reformulate the convolutional model. Then, to provide residual signals, we apply a Kalman filter based on the no change hypothesis to the linear system. Finally, to estimate the first arrival time, a generalized likelihood ratio (GLR)-based change detection technique is utilized. Using the simulated data, we verified the performance of the proposed approach. Overall, this study presents a promising approach for improving the accuracy of first arrival picking in the presence of different noise levels.

Deep vision models have provided new capability across a spectrum of applications in transportation, manufacturing, agriculture, commerce, and security. However, recent studies have demonstrated that these models are vulnerable to adversarial attack, exposing a risk-of-use in critical applications where untrusted parties have access to the data environment or even directly to the sensor inputs. Existing adversarial defense methods are either limited to specific types of attacks or are too complex to be applied to practical vision models. More importantly, these methods rely on techniques that are not interpretable to humans. In this work, we argue that an effective defense should produce an explanation as to why the system is attacked, and by using a representation that is easily readable by a human user, e.g. a logic formalism. To this end, we propose logic adversarial defense (LogicDef), a defense framework that utilizes the scene graph of the image to provide a contextual structure for detecting and explaining object classification. Our framework first mines inductive logic rules from the extracted scene graph, and then uses these rules to construct a defense model that alerts the user when the vision model violates the consistency rules. The defense model is interpretable and its robustness is further enhanced by incorporating existing relational commonsense knowledge from projects such as ConceptNet. In order to handle the hierarchical nature of such relational reasoning, we use a curriculum learning approach based on object taxonomy, yielding additional improvements to training and performance.

With the recent advancement in technology and a vast amount of information available, research in pattern mining has started to attract more attention. Specifically, various techniques have been developed for clickstream mining, which is a specific type of sequential pattern mining, to discover the underlying patterns from the Internet user clickstream. Due to the complexity of clickstream patterns, many of the existing works applied sequential pattern algorithms to generate an exponential candidate space of patterns with respect to patterns letters. Further, those patterns were generated in a noiseless environment. To address this problem, we focus on a nonoverlapping clickstream pattern mining task with noisy interleaving clicks between the clickstream patterns letters. Additionally, we are interested in labeling the extracted patterns in the user browsing history. A modified suffix tree is proposed to extract those patterns with the exact occurrence in the user noisy database. Following this, we model the user browsing behavior via a Hidden Markov Model (HMM) to capture the dependencies between the extracted patterns and then predict the future clickstream patterns. Experimental results on both real-life and synthetic datasets show that our proposed algorithms outperform the state-of-the-art benchmarks in efficiency and prediction accuracy.

The actor-critic RL is widely used in various robotic control tasks. However, by viewing the actor-critic RL from the perspective of variational inference (VI), in practice, the actor-critic RL may yield suboptimal policy estimates due to the amortization gap and insufficient exploration. In this work, inspired by the previous use of Hamiltonian Monte Carlo (HMC) in VI, we propose to integrate the policy network of actor-critic RL with HMC, which is termed as Hamiltonian Policy. As such we propose to evolve actions from the base policy according to HMC. First, HMC can improve the policy distribution to better approximate the posterior and hence reduce the amortization gap. Second, HMC can also guide the exploration more to the regions of action spaces with higher Q values, enhancing the exploration efficiency. Further, instead of directly applying HMC into RL, we propose a new leapfrog operator to simulate the Hamiltonian dynamics. With comprehensive empirical experiments on continuous control baselines, including MuJoCo and PyBullet Roboschool, we show that the proposed approach is a data-efficient and easy-to-implement improvement over previous actor-critic methods.

Teaching a deep reinforcement learning (RL) agent to follow instructions in multi-task environments is a challenging problem. We consider that user defines every task by a linear temporal logic (LTL) formula. However, some causal dependencies in complex environments may be unknown to the user in advance. Hence, when human user is specifying instructions, the robot cannot solve the tasks by simply following the given instructions. In this work, we propose a hierarchical reinforcement learning (HRL) framework in which a symbolic transition model is learned to efficiently produce high-level plans that can guide the agent efficiently solve different tasks. Specifically, the symbolic transition model is learned by inductive logic programming (ILP) to capture logic rules of state transitions. By planning over the product of the symbolic transition model and the automaton derived from the LTL formula, the agent can resolve causal dependencies and break a causally complex problem down into a sequence of simpler low-level sub-tasks. We evaluate the proposed framework on three environments in both discrete and continuous domains, showing advantages over previous representative methods.

In many diverse fields, distributed IoT devices perform collaborative inference by communicating with an edge router. Often sensory data contains sensitive attributes that should not be revealed to the router. To address this, we develop, to the best of our knowledge, the first privacy-aware machine learning framework for distributed functional compression over AWGN channels. The key feature of our approach to privacy is that we focus only on sensitive attributes of data rather than paying a high cost to protect everything. Employing a mutual information based privacy constraint, we first propose a novel approximate upper bound to protect sensitive attributes in the compressed representations of the sensory data. Next, in conjunction with the upper bound, we propose an adversarial lower bound to enhance the protection further. Thirdly, we propose novel decompositions to these bounds such distributed edge devices can ensure overall privacy by independently privatizing their components. This allows us to propose an enhanced privacy-aware algorithm that protects sensitive information during training and inference. Our experiments show that the privacy-utility trade-off from our proposed methods is significantly better than existing mechanisms.

This work develops a model-based compression scheme for seismic data. First, seismic traces are modeled as multitone sinusoidal waves superposition. Each sinusoidal wave is regarded as a model component and is represented by a set of distinct parameters. Second, a parameter estimation algorithm for this model is proposed accordingly. In this algorithm, the parameters are estimated for each component sequentially. A suitable number of model components is determined by the level of the residuals energy. Next, the residuals are compressed using entropy coding or quantization coding techniques. The corresponding compression ratios are presented. Finally, the proposed model-based compression scheme is compared with the linear predictive coding (LPC) algorithm and the distributed principal component analysis (DPCA) algorithm on a real seismic database. The performance of the proposed model based is shown to be superior to that of the LPC and DPCA.

Visual question answering (VQA) has been gaining a lot of traction in the machine learning community in the recent years due to the challenges posed in understanding information coming from multiple modalities (i.e., images, language). In VQA, a series of questions are posed based on a set of images and the task at hand is to arrive at the answer. To achieve this, we take a symbolic reasoning based approach using the framework of formal logic. The image and the questions are converted into symbolic representations on which explicit reasoning is performed. We propose a formal logic framework where (i) images are converted to logical background facts with the help of scene graphs, (ii) the questions are translated to first-order predicate logic clauses using a transformer based deep learning model, and (iii) perform satisfiability checks, by using the background knowledge and the grounding of predicate clauses, to obtain the answer. Our proposed method is highly interpretable and each step in the pipeline can be easily analyzed by a human. We validate our approach on the CLEVR and the GQA dataset. We achieve near perfect accuracy of 99.6% on the CLEVR dataset comparable to the state of art models, showcasing that formal logic is a viable tool to tackle visual question answering. Our model is also data efficient, achieving 99.1% accuracy on CLEVR dataset when trained on just 10% of the training data.

In this paper, we study Joint Source-Channel Coding (JSCC) for distributed analog functional compression over both Gaussian Multiple Access Channel (MAC) and AWGN channels. Notably, we propose a deep neural network based solution for learning encoders and decoders. We propose three methods of increasing performance. The first one frames the problem as an autoencoder; the second one incorporates the power constraint in the objective by using a Lagrange multiplier; the third method derives the objective from the information bottleneck principle. We show that all proposed methods are variational approximations to upper bounds on the indirect rate-distortion problem's minimization objective. Further, we show that the third method is the variational approximation of a tighter upper bound compared to the other two. Finally, we show empirical performance results for image classification. We compare with existing work and showcase the performance improvement yielded by the proposed methods.

This paper proposes a general framework to design a sparse sensing matrix ${\mathbf {A}} \in \mathbb{R}^{m\times n}$, in a linear measurement system ${\mathbf {y = Ax}}^{\sharp } + {\mathbf {w}}$, where ${\mathbf {y}} \in \mathbb{R}^{n}, {\mathbf {x}}^{\sharp } \in \mathbb{R}^{n}$, and w denote the measurements, the signal with certain structures, and the measurement noise, respectively. By viewing the signal reconstruction from the measurements as a message passing algorithm over a graphical model, we leverage tools from coding theory in the design of low density parity check codes, namely the density evolution, and provide a framework for the design of matrix A. Particularly, compared to the previous methods, our proposed framework enjoys the following desirable properties: (i) Universality: the design supports both regular sensing and preferential sensing, and incorporates them in a single frame-work; (ii) Flexibility: the framework can easily adapt the design of A to a signal $x^{\sharp }$ with different underlying structures. As an illustration, we consider the $\ell_{1}$ regularizer, which correspond to Lasso, for both the regular sensing and preferential sensing scheme. Noteworthy, our framework can reproduce the classical result of Lasso, i.e., $m \geq c_{0}k\log (n/k)$ (the regular sensing) with regular design after proper distribution approximation, where $c_{0}\gt 0$ is some fixed constant. We also provide numerical experiments to confirm the analytical results and demonstrate the superiority of our framework whenever a preferential treatment of a sub-block of vector $x^{\sharp }$ is required.

Predicting mobile users' web-access behavior can have substantial impacts on resource allocation and cost reduction for wireless networks. Therefore, we propose a machine learning platform to forecast the web traffic and access time of mobile users. Based on the observation, the traffic patterns exhibit complex dependency on time, location, and popularity of webpages. Thus, a Recurrent Neural Network (RNN) with Long Short Term Memory (LSTM) is developed based on distinct engineered features to learn and predict users' web browsing activities. Then, to forecast the future access-time of mobile users, we propose a Self-exciting Memory Neural Network (SMNN). The access activities are modeled as self-exciting point processes, and intensities are adopted for prediction. Moreover, we extend the proposed predicting framework to cell towers. To cope with the diversity of traffic at the cell tower, we resort to clustering methods to group the similar users of each tower. Then, we develop an LSTM model for each cluster separately to predict the web domain traffic activities for the cell tower. Finally, we show that our proposed models outperform the baseline prediction models based on cellular networks dataset. We also show that for the cell tower access prediction task, the clustering method can significantly improve the prediction accuracy.

Event-based social networks (EBSNs) have become increasingly popular, which provide online social event management platforms for event organizers to publish and share social events (e.g., outdoor activities). In EBSNs, a major challenge for a social event organizer is how to plan a social event to attract the maximum number of attendance. To organize an event, three essential elements are required, namely, what (i.e., event content), where (i.e., event location), and when (i.e., event time). In this paper, we focus on the social event planning problem, which selects a location and time to hold a social event for the organizer with the given event content, to maximize the total number of participants. The solution of the social event planning problem could support decision-making for social event organizers. For simplicity, we denote a location and time pair as an item in this paper. To solve the social event planning problem, we present a hybrid pairwise Markov random field (H-PMRF) model which takes latent preferences of users, latent attributes of items, similarities between users and similarities between items into consideration. In particular, we construct an undirected graph where each node represents a user's decision on a specific item and each edge represents the relationship between the nodes, define the node potentials and edge potentials which model the dependency relationships between nodes, and give a joint probability distribution over the graph. Further, we adopt the Loopy Belief Propagation algorithm to compute the posterior probability distribution of each node in H-PMRF and select the location and time to hold the event which could attract the maximum number of participants. We collect real-world data set from DoubanEvent website and conduct extensive experiments on it. Experimental results show that the proposed model outperforms several baselines.

In this paper, we present a learning scheme for Joint Source-Channel Coding (JSCC) over analog independent additive noise channels. We formulate the learning problem by showing that the minimization loss function from rate-distortion theory, is upper bounded by the loss function of the Variational Autoencoder (VAE). We show that when the source dimension is greater than the channel dimension, the encoding of two source samples in the neighborhood of each other need not be near each other. Such discontinuous projection needs to be accounted for by using multiple encoders and selecting an encoder to encode samples on a particular side of the discontinuity. We explore two selection methodologies, one based on an intuitive rule and the other where it is posed as a learning task in a Mixture-of-Experts (MoE) setup. We analyze the gradients of these methods and reason why the latter is better at avoiding local optima. We show the efficacy of the proposed methodology by simulating the performance of the system for JSCC of Gaussian sources over AWGN channels and showing that the learned solutions are close to or better than the ones proposed earlier. The proposed methodology is also naturally capable of generalizing to other source distributions which we showcase by simulating for Laplace sources. The learned systems are also robust to changes in channel conditions. Further, a single system can be trained to generalize over a range of channel conditions provided the channel conditions are known at both the transmitter and the receiver. Finally, we evaluate our proposed methodology on three different image datasets and showcase consistent improvement over existing methods due to the VAE formulation.

In distributed training of deep models, the transmission volume of stochastic gradients (SG) imposes a bottleneck in scaling up the number of processing nodes. On the other hand, the existing methods for compression of SGs have two major drawbacks. First, due to the increase in the overall variance of the compressed SG, the hyperparameters of the learning algorithm must be readjusted to ensure the convergence of the training. Further, the convergence rate of the resulting algorithm still would be adversely affected. Second, for those approaches for which the compressed SG values are biased, there is no guarantee for the learning convergence and thus an error feedback is often required. We propose Quantized Compressive Sampling (QCS) of SG that addresses the above two issues while achieving an arbitrarily large compression gain. We introduce two variants of the algorithm: Unbiased-QCS and MMSE-QCS and show their superior performance w.r.t. other approaches. Specifically, we show that for the same number of communication bits, the convergence rate is improved by a factor of 2 relative to state of the art. Next, we propose to improve the convergence rate of the distributed training algorithm via a weighted error feedback. Specifically, we develop and analyze a method to both control the overall variance of the compressed SG and prevent the staleness of the updates. Finally, through simulations, we validate our theoretical results and establish the superior performance of the proposed SG compression in the distributed training of deep models. Our simulations also demonstrate that our proposed compression method expands substantially the region of step-size values for which the learning algorithm converges.

Transmitting the gradients or model parameters is a critical bottleneck in distributed training of large models. To mitigate this issue, we propose an indirect quantization and compression of stochastic gradients (SG) via factorization. The gist of the idea is that, in contrast to the direct compression methods, we focus on the factors in SGs, i.e., the forward and backward signals in the backpropagation algorithm. We observe that these factors are correlated and generally sparse in most deep models. This gives rise to rethinking of the approaches for quantization and compression of gradients with the ultimate goal of minimizing the error in the final computed gradients subject to the desired communication constraints. We have proposed and theoretically analyzed different indirect SG quantization (ISGQ) methods. The proposed ISGQ reduces the reconstruction error in SGs compared to the direct quantization methods with the same number of quantization bits. Moreover, it can achieve compression gains of more than 100, while the existing traditional quantization schemes can achieve compression ratio of at most 32 (quantizing to 1 bit). Further, for a fixed total batch-size, the required transmission bit-rate per worker decreases in ISGQ as the number of workers increases.

In this paper, we propose a deep neural network framework for Joint Source-Channel Coding of an m dimensional i.i.d. Gaussian source for transmission over a single additive white Gaussian noise channel with no delay. The framework employs two neural encoder-decoder pairs that learn to split the input signal space into two disjoint support sets. The encoder and the decoder are jointly trained to minimize the mean square error subject to a power constraint on the signal transmitted across the channel. The proposed method achieves results as good as the state of the art for m=3,4 and is easily extendable to higher dimensions. The trained model, we discovered, assigns almost equal probability to the disjoint support sets. The results show that the scheme performance is within 1.9dB of the Shannon optimal limit over a wide range of Channel Signal to Noise Ratios (CSNR) from 0dB to 30dB for various values of m. The method is also robust, i.e. employing a model trained at CSNR+/-5dB is only 0.6dB worse than a model trained specifically for that CSNR.

Performance of the reconstruction algorithms in compressed sensing largely depends on the characteristics of measurement matrices. As such, the construction and analysis of the measurement matrix is of paramount interest. In this paper, for the first time, we focus on the class of sparse sensing matrices with (non-negative) integer entries. This problem, among other applications, is particularly motivated by the constraint of measuring gene regulatory expressions. We study randomly generated matrices from the integer family and analyze their properties in terms of the covariance and RIP constant. We derive bounds for the coherence and RIP constant of such measurement matrices. Further, apart from the coherence, we find that the RIP constant is closely related to the minimum non-diagonal entry ρnin the covariance matrix, which is rarely studied before.

In this paper, we study joint source-channel coding of gaussian sources over multiple AWGN channels where the source dimension is greater than the number of channels. We model our system as a Variational Autoencoder and show that its loss function takes up a form that is an upper bound on the optimization function got from rate-distortion theory. The constructed system employs two encoders that learn to split the source input space into almost half with no constraints. The system is jointly trained in a data-driven manner, end-to-end. We achieve state of the art results for certain configurations, some of which are 0.7dB better than previous works. We also showcase that the trained encoder/decoder is robust, i.e., even if the channel conditions change by +/-5dB, the performance of the system does not vary by more than 0.7dB w.r.t. a system trained at that channel condition. The trained system, to an extent, has the ability to generalize when a single input dimension is dropped and for some scenarios it is less than 1dB away from the system trained for that reduced dimension.

In this paper, we study a general framework for compressive sensing assuming the existence of the prior knowledge that x* belongs to the union of multiple convex sets, x* ε υi ℒi. In fact, by proper choices of these convex sets in the above framework, the problem can be transformed to well known CS problems such as the phase retrieval, quantized compressive sensing, and model-based CS. First we analyze the impact of this prior knowledge on the minimum number of measurements M to guarantee the uniqueness of the solution. Then we formulate a universal objective function for signal recovery, which is both computationally inexpensive and flexible. Then, an algorithm based on multiplicative weight update and proximal gradient descent is proposed and analyzed for signal reconstruction. Finally, we investigate as to how we can improve the signal recovery by introducing regularizers into the objective function.

In general, uncertainties in the sensing matrix weakens the system performance and reduces the reliability of recovered signals. In some applications, the sign values of signals instead of their exact values may be needed. In this paper, we show that as long as the uncertainty in the sensing matrix is sparse, a thresholding mechanism can be developed to recover the sign vector. In particular, provided that the true signal satisfies certain conditions, the exact sign vector can be recovered with high probability even under uncertain sensing matrices. Simulations are also presented to verify our theoretical results.

This paper develops a new framework for data compression in seismic sensor networks by using the distributed principal component analysis (DPCA). The proposed DPCA scheme compresses all seismic traces in the network at the sensor level. First of all, the statistics of the seismic traces acquired at all sensors are represented by a mixture model of a number of probability density functions. Based on this mixture model, the DPCA finds the global PCs at the fusion center. These PCs are then sent back to all sensors so that each sensor projects its own traces over these PCs. This scheme does not require transmitting the original traces, here, leading to a low computational load and a high compression ratio, compared with compression obtained using the local PC analysis (LPCA). Furthermore, we develop an efficient communication solution for the DPCA implementation on practical sensor networks. Finally, the proposed scheme is evaluated using real and synthetic seismic data showing improved performance over the LPCA and the traditional 2-D discrete cosine transform (DCT-2-D) compression. Specifically, to preserve a given signal energy during the compression, the DPCA is shown to achieve a higher compression ratio than the LPCA and the DCT-2-D.

Seismic data (traces) usually demonstrate high correlation. We propose a scheme based on online dictionary learning, which explores the resemblance among local seismic traces to facilitate compression for communication. In order to alleviate the transmission overhead caused by the slow convergence of online dictionary scheme, sparse constraints and a sliding window mechanism are applied to the incremental components of the dictionaries, which significantly improve the performance of online dictionary learning scheme in the sense of communication cost.

We consider a non-stationary data stream in which the data statistics may change abruptly from one sample to another, i.e. each sample might be generated from a different (unknown) source in a mixture of K sources. The problem of identifying the models and parameters of K sources, as well as the source switching model is investigated. We proposed an algorithm based on Bayesian Information Criterion and Expectation Maximization to determine the models and estimate the mixture parameters. The estimated data generation model can be used in memory-assisted universal compression to decrease the coding rate further. Simulation results confirmed that using the proposed algorithm for source identification and universal compression can significantly decrease the compression redundancy.

We consider the problem of learning dictionaries for data compression. Different from ordinary learning methods, the objective is to design a dictionary such that the signal has a low entropy representation in the basis of the dictionary, rather than giving a sparse or low-energy representation. To achieve this goal, we need to consider the effect of quantization on the rate-distortion curve as well as an estimation of the distributions of the coefficients. Based on this probability estimation, the coefficients are computed, quantized and then entropy-coded. As such, we have developed algorithms for different classes of dictionaries; orthonormal, union of orthonormals and general dictionaries with unit-norm atoms, to iteratively learn the dictionary and the distribution models of the coefficients. A mixture of Gaussians is adopted to estimate the probability and is updated using the expectation maximization algorithm together with the dictionary learning. Simulation results on the real seismic data show the effectiveness of the proposed algorithm compared to ordinary dictionary learning methods.

The sensor selection problem arises in many applications ranging from sensor networks for event detection to determining concentrations of bio-markers for disease detection. In this paper, we assume that in addition to noise, there exist interference signals (which can be correlated with the desired signals) corrupting the measurements. We consider two different criteria to measure the performance of the selected sensors; average error and minimax analysis. For each case, the cost function is defined over the reconstruction algorithm (or matrix in the linear case), which in turn, explicitly determines the selected sensors. Therefore, minimizing the cost function with some sparsity constraints on the reconstruction algorithm results in the best subset of sensors and as to how we recover the desired signals from the selected measurements. In this paper, we consider the problem for the linear measurement system in various settings and derive the optimization problems. Finally, we propose various methods to solve these problems, and show the effectiveness of the proposed algorithms through simulations.

In this paper, we propose using stochastic framework for computations by biological cells. The key observation is that the input molecules activate receptors of a biological cell independently with probability p that is dependent on the molecule's concentration. Hence, the (active/inactive) states of the receptors can be viewed as a stochastic number representing the input concentration or probability p. We construct the addition operation via a cell having two different types of receptors. We also develop the multiplication by using a receptor that is active (with some probability) when both types of input molecules present. We analyze the computing accuracy of a cell w.r.t. parameters such as number of receptors and the input sensitivity of the cell.

In certain applications, recovering the signs of values may be more critical than the values themselves. Inspired by advances of sparse recovery of signals with fewer measurements, we would like to study the sign recovery problem and generalize it from a linear case to a non-linear setup. We focus on the sign values in quadratic measurement systems and provide theorems for the consistency condition, which ensures the signs are recovered correctly with probability close to 1. In deriving the consistency condition, we adopt a new penalty term using the trace operation and transform the optimization problem to the widely known Lasso problem. We also present simulation results to verify the correctness of our theorems.

In many sparse sensing applications, it is desirable to limit not only the number of non-zero variables but also the amplitude or energy of the signal, i.e., the non-zero variables are expected to be in a certain range. One approach to incorporate the energy constraint is using objective functions such as IIxII22+ λ||χ||ο In this paper, we consider minimizing this objective function, given the linear sensing system y = Ax. As this optimization problem is not convex, we first find the convex envelope of the objective function and then analyze the relation between the uniqueness of the solution and the required number of sensors. Further, we show that the sparsity of the measurement matrix A has negative effects on the required number of sensors.

Despite recent advances in molecular communication among bio agents, the design of reliable communication schemes remains an open problem. One of the requirements is to develop suitable coding schemes, which meet the molecular communication specific constraints in terms of reliability and complexity, and take into account the communication channel properties. In this paper, we consider diffusion-based molecular communication in which the information is encoded into the concentration (e.g., on/off keying). Such a communication system is modeled as operating over a completely asymmetric channel where one of the bits can be transmitted without any error while the other can undergo a random error by the channel. Because of the limitations of bio-agents, we focus on error-detection schemes, which require far less complexity at the receiver relative to error-correction codes. To obtain an optimal detection scheme, we model the detection problem via an erasure channel and propose algorithms to obtain the optimal codewords efficiently for two different optimality measures. Then, we consider an error-free subfamily of such codes, namely constant weight codes, and propose an implementation specific to the molecular communication. We analyze the rate of the constant-weight coding scheme, compare it to the theoretical limits and specify the optimal weights and lengths of such codes.

The existence of considerable amount of redundancy in the Internet traffic at the packet level has stimulated the deployment of packet-level redundancy elimination techniques within the network by enabling network nodes to memorize data packets. Redundancy elimination results in traffic reduction which in turn improves the efficiency of network links. In this paper, the concept of network compression is introduced that aspires to exploit the statistical correlation beyond removing large duplicate strings from the flow to better suppress redundancy. In the first part of the paper, we introduce “memory-assisted compression,” which utilizes the memorized content within the network to learn the statistics of the information source generating the packets which can then be used toward reducing the length of codewords describing the packets emitted by the source. Using simulations on data gathered from real network traces, we show that memory-assisted compression can result in significant traffic reduction. In the second part of the paper, we study the scaling of the average network-wide benefits of memory-assisted compression. We discuss routing and memory placement problems in network for the reduction of overall traffic. We derive a closed-form expression for the scaling of the gain in Erdös-Rényi random network graphs, where obtain a threshold value for the number of memories deployed in a random graph beyond which network-wide benefits start to shine. Finally, the network-wide benefits are studied on Internet-like scale-free networks. We show that non-vanishing network compression gain is obtained even when only a tiny fraction of the total number of nodes in the network are memory-enabled.

Traces derived from real-world traffic show that significant redundancy exists at the packet level in mobile network traffic. This has inspired new solutions to suppress the redundancy present in the packet data to manage the explosive traffic. In this paper, we propose a novel approach to performing redundancy elimination by employing universal compression using memory-enabled overhearing helpers without backhaul connectivity, referred to as wireless network compression. The helpers overhear the data packets previously sent by the wireless gateway to various mobile clients within their coverage and use them as side information to reduce the overall communication cost. We study wireless network compression via overhearing helpers from an information-theoretic point of view and conclude that this approach potentially offers a threefold benefit: 1) offloading the wireless gateway and hence increasing the maximum number of mobile nodes the gateway can reliably serve; 2) reducing the average packet delay; and 3) improving the overall throughput in the network.

Social media like Twitter has been widely adopted for information dissemination due to its convenience and efficiency. However, false information and rumors on social media are undermining its utility as a valuable real-time information source. Existing works for information credibility analysis are based on offline batch analysis, often incurring a long lag since the event first occurs. In this paper, we develop a generative probabilistic model for real-time event credibility prediction in Twitter. We propose an online prediction algorithm based on streaming tweets, without storing or reprocessing the past tweets. We evaluate both the offline batch prediction and online streaming prediction performance of the proposed model on the Twitter dataset. The empirical results show that its batch prediction performance outperforms other algorithms based on aggregation analysis, and the online prediction performance quickly approaches that of the batch prediction with only a few hundred tweets.

Online social networks are becoming important platforms where users make social connections and share information. However, they are vulnerable to malevolent activities by malicious users. Hence, it necessitates effective automatic methods to predict user trustworthiness. The existing works mostly predict the trustworthiness of individual users separately from other users, ignoring the fact that users are related to each other through online social relationships. In this paper, we propose a probabilistic model based on Pairwise Markov Random Field (PMRF) that takes into account both user features and social relationships. In addition, we apply the Belief Propagation (BP) algorithm to perform inference efficiently in PMRF. The complexity of the algorithm grows only linear in the number of users. The experiment results on the Twitter datasets show that the proposed PMRF model can effectively exploit the social relationships to significantly improve the prediction performance.

Despite the recent research activities in molecular communication among bio agents, the design of reliable schemes remains an open problem. One of the challenges is to develop suitable coding schemes which meet the molecular communication specific constraints in terms of reliability and complexity. In this paper, we consider diffusion-based molecular communication in which the information is encoded into the concentration (e.g., on/off keying). Such a communication system operates over a completely asymmetric channel where one of the bits can be transmitted without any error while the other can undergo a random error by the channel. Because of the limitations of bio agents, we focus on error-detecting schemes which require far less complexity at the receiver relative to error-correction codes. We model the detection process at the receiver via an erasure channel and propose an algorithm that obtains the optimal codewords efficiently. Then, we consider an error-free sub-family of such codes, namely constant weight codes, and propose an implementation specific to the molecular communication. We analyze the rate of the constant-weight coding scheme and specify the optimal weights and lengths of such codes. We also show that this coding scheme, by design, would enable the nodes to synchronize their communications.

We consider the problem of decodability when random linear coding (RLC) is performed on a stream of packets in a line network. First, we clearly define the problem of decodability for a stream of arriving packets, and discuss its importance with some examples. Then, we will find the limits on the mean arrival rate under which the stream is decodable. Further, upper bounds will be derived for the average length of a decoded block of packets in multi-hop line networks. Finally, these analytical results are validated via simulations.

In this paper, we consider the bacterial point-to-point communication problem with one transmitter and one receiver by considering the ligand receptor binding process. The most commonly investigated signalling model, referred to as the Level Scenario (LS), uses one type of a molecule with different concentration levels for signaling. An alternative approach is to employ multiple types of molecules with a single concentration level, referred to as the Type Scenario (TS). We investigate the trade-offs between the two scenarios for the ligand receptor from the capacity point of view. For this purpose, we evaluate the capacity using numerical algorithms. Moreover, we derive an upper bound on the capacity of the ligand receptor for a Binomial Channel (BIC) model, using symmetrized Kullback-Leibler (KL) divergence. A lower bound is also derived when the environment noise is negligible. Finally, we analyse the effect of blocking of a receptor by a molecule of a different type, by proposing a new Markov model in the multiple-type signalling.

Molecular communication between biological entities is a new paradigm in which biological nodes sense the environment, communicate and cooperate with each other. Ligand receptors are among the most common mechanisms used by biological entities such as bacteria to sense the molecular signals in their surroundings. In such a mechanism, molecules (i.e., ligands) bind to certain proteins (i.e., receptors) and activate a signaling cascade inside the cell. In this paper, we study the distortion in sensing and estimation of the concentration of molecular signals by ligand receptors in biological agents. The sensing distortion is caused by both the randomness in the ligand reception and the quantization of the final receiver output. The random measurement of the signal by the binding activity differentiates this case from classical quantization problems. We propose an optimal random quantization technique that minimizes the overall distortion described above. The performance of this optimal technique is compared with a uniform quantizer design and the regions where the optimal quantizer can offer a considerable advantage are identified. Furthermore, we analyze the effect of the number of the output levels (i.e., the output rate) on the overall distortion compared with the theoretical limit given by Shannon. Following this, the best practical number of levels beyond which no significant improvement can be made is presented.

In this paper, we study the block delivery delay of random linear network coding in two-hop single-unicast delay-tolerant networks with grid-based mobility. By block delivery delay, we mean how long it takes the destination to receive all the K information packets of a single block. Our work includes two parts. First, we give a general analysis of the dependency between packet spaces spanned by different nodes in a stochastic way. Then we simplify the result by means of the approximation. By the dependency analysis, we can accurately update nodes' innovativeness rank. Second, via tracking the innovativeness ranks of all nodes, we develop an analytic framework to iteratively compute the cumulative distribution function of the block delivery delay. Our simulation results verify that both parts of our analysis are sufficiently accurate. Copyright © 2013 John Wiley & Sons, Ltd.

Rapid growth of emerging medical applications such as e-health and tele-medicine requires fast, low cost, and often lossless access to massive amount of medical images and data over bandlimited channels. In this paper, we first show that significant amount of correlation and redundancy exist across different medical images. Such a correlation can be utilized to achieve better compression, and consequently less storage and less communication overhead on the network. We propose a novel memory-assisted compression technique, as a learning-based universal coding, which can be used to complement any existing algorithm to further eliminate redundancies across images. The approach is motivated by the fact that, often in medical applications, massive amount of correlated images from the same family are available as training data for learning the dependencies and deriving appropriate reference models. Such models can then be used for compression of any new image from the same family. In particular, Principal Component Analysis (PCA) is applied on a set of images from training data to form the required reference models. The proposed memory-assisted compression allows each image to be processed independently of other images, and hence allows individual image access and transmission. Experimental results on X-ray images show that the proposed algorithm achieves 20% improvement over and above traditional lossless image compression methods reported in the literature.

Molecular communication allows bio nodes to communicate and cooperate in an aqueous environment. We recently proposed an m-ary modulation scheme in which the information is encoded into the concentration of molecules emitted by the bio nodes. The performance of such scheme, among other factors, is limited by the maximum concentration of molecules that can be induced by the transmitter at the receiver. This paper investigates relaying to improve the reliability of such molecular communication. We consider the case that nodes consist of a population of biological agents and study the scenario in which the relay node decodes the incoming information symbol and forwards it to the destination using the same or a different type of molecules as the transmitter. We show how the use of relaying in molecular communication can increase the effective range of molecular concentration induced at the receiver and also can help with achieving diversity at the receiver. We use a generalized form of Maximum Ratio Combining (MRC) and show as to how the probability of error is improved using the optimal relaying. We also compare this scenario with the case that the relay node uses the same type of the molecule.

Social recommender systems exploit the historic user data as well as user relations in the social networks to make recommendations. However, users are increasingly concerned with their online privacy, and hence, they are not willing to reveal their personal data to the general public. In this paper, we propose a social recommendation algorithm for top-N recommendation using only implicit user preference data. In particular, we model users' consumption behavior in the social network with Bayesian networks, using which we can infer the probabilities for items to be selected by each user. We develop an Expectation Propagation (EP) message-passing algorithm to perform approximate inference efficiently in the constructed Bayesian network. The original proposed algorithm is a central scheme, in which the user data are collected and processed by a central authority. However, it can be easily adapted for a distributed implementation, where users only exchange messages with their directly connected friends in the social network. This helps further protect user privacy, as users do not release any data to the public. We evaluate the proposed algorithm on the Epinions dataset, and compare it with other existing social recommendation algorithms. The results show its superior top-N recommendation performance in terms of recall.

Recently, we proposed wireless network compression via memory-enabled overhearing helpers as an endeavor to reduce the traffic load on the wireless gateway via elimination of the redundant data in the network. In this setup, each memory-enabled helper overhears the data packets previously sent by the wireless gateway to various mobile clients within its coverage and uses them toward forming a model about the content of the packets from the traffic. The resulting model is then used as side information by the wireless network compression module in a two-part code to reduce the overall cost of delivering a packet to a client over links with asymmetric cost (where the helper-client link is far less costly than the gateway-client link). One main challenge in this scenario is the fact that memory-enabled overhearing helpers do not receive all of the sequences sent to the mobile clients (as there is no feedback in place in the overhearing link), resulting in mismatched side information between the encoder (i.e., gateway) and the helper. In this paper, we present an information theoretic formulation for the mismatched side information problem. We study this problem in the context of universal lossless compression and derive bounds on the average minimax redundancy of encoding each packet. Our results also lead to construction of coding schemes for the mismatched side information using two-part codes.

In this paper, the problem of universal lossless one-to-one compression (without prefix constraint) is studied. A converse bound is obtained on the average minimax (and maximin) redundancy that shows the redundancy is at least (d-2)=2 log n+O(1) for the universal compression of a sequence of length n from a d-dimensional parametric source. Further, the type-size coding strategy is shown to be minimax optimal up to o(log n) for the class of memoryless sources, achieving the converse leading to characterization of the fundamental performance limit of universal compression for memoryless sources. Finally, through a numerical example, our results imply that the reduction on the codeword length due to relaxing the prefix constraint is negligible when compared to the cost of universality.

Recommender systems have been widely used in e-commerce websites to suggest items that meet users' preferences. Collaborative filtering, which is the most popular recommendation algorithm, is vulnerable to shilling attacks, where a group of spam users collaborate to manipulate the recommendations. Several attack detection algorithms have been developed to detect spam users and remove them from the system. However, the existing algorithms focus mostly on rating patterns of users. In this paper, we develop a probabilistic inference framework that further exploits the target items for attack detection. In addition, the user features can also be conveniently incorporated in this framework. We utilize the Belief Propagation (BP) algorithm to perform inference efficiently. Experimental results verify that the proposed algorithm significantly improves detection performance as the number of target items increases.

We consider disruption tolerant networks (DTNs) wherein a direct communication path from a source to a destination via multiple hops does not exist due to both mobility and sparseness of the nodes. Hence, mobile nodes will deliver messages from source to destination using a “store, carry, and forward” strategy. In this paper, our goal is to analytically study the packet latency in such networks for a two-hop unicast scenario with Bernoulli packet arrivals at the source. We exploit an embedded Markov chain approach combined with our novel iterative estimation technique to study both network delay and queuing delay. Constraints posed by both the limited node buffer size and contention between nodes for wireless channel are also considered to obtain a more realistic model. Finally, our results are validated using simulations for a random-walk on a two-dimensional grid mobility model.

Recent studies have shown the existence of considerable amount of packet-level redundancy in the network flows. Since application-layer solutions cannot capture the packet-level redundancy, development of new content-aware approaches capable of redundancy elimination at the packet and sub-packet levels is necessary. These requirements motivate the redundancy elimination of packets from an information-theoretic point of view. For efficient compression of packets, a new framework called memory-assisted universal compression has been proposed. This framework is based on learning the statistics of the source generating the packets at some intermediate nodes and then leveraging these statistics to effectively compress a new packet. This paper investigates both theoretically and experimentally the memory-assisted compression of network packets. Clearly, a simple source cannot model the data traffic. Hence, we consider traffic from a complex source that is consisted of a mixture of simple information sources for our analytic study. We develop a practical code for memory-assisted compression and combine it with a proposed hierarchical clustering to better utilize the memory. Finally, we validate our results via simulation on real traffic traces. Memory-assisted compression combined with hierarchical clustering method results in compression of packets close to the fundamental limit. As a result, we report a factor of two improvement over traditional end-to-end compression.

This paper is eligible for the student paper award. Molecular communication between biological entities is a new paradigm in communications. Recently, we studied molecular communication between two nodes formed from synthetic bacteria. Due to high randomness in behavior of bacteria, we used a population of them in each node. The reliability of such communication systems depends on both the maximum concentration of molecules that a transmitter node is able to produce at the receiver node as well as the number of bacteria in each nodes. This maximum concentration of molecules falls with distance which makes the communication to the far nodes nearly impossible. In order to alleviate this problem, in this paper, we propose to use a molecular relaying node. The relay node can resend the message either by the different or the same type of molecules as the original signal from the transmitter. We study two scenarios of relaying. In the first scenario, the relay node simply senses the received concentration and forwards it to the receiver. We show that this sense and forward scenario, depending on the type of molecules used for relaying, results in either increasing the range of concentration of molecules at the receiver or increasing the effective number of bacteria in the receiver node. For both cases of sense and forward relaying, we obtain the resulting improvement in channel capacity. We conclude that multi-type molecular relaying outperforms the single-type relaying. In the second scenario, we study the decode and forward relaying for the M-ary signaling scheme. We show that this relaying strategy increases the reliability of M-ary communication significantly.

In this paper, we develop a Belief Propagation (BP) algorithm for similarity computation to improve the recommendation accuracy of the neighborhood method, which is one of the most popular Collaborative Filtering (CF) recommendation algorithms. We formulate a probabilistic inference problem as to compute the marginal posterior distributions of similarity variables from their joint posterior distribution given the observed ratings. However, direct computation is prohibitive in large-scale recommender systems. Therefore, we introduce an appropriate chosen factor graph to express the factorization of the joint distribution function, and utilize the BP algorithm that operates in the factor graph to exploit the factorization for efficient inference. In addition, since the high degree at the factor node incurs an exponential increase in computational complexity, we also propose a complexity-reduction technique. The overall complexity of the proposed BP algorithm on a factor graph is linear in the number of variables, which ensures scalability. Finally, through experiments on the MovieLens dataset, we show the superior prediction accuracy of the proposed BP-based similarity computation algorithm for recommendation.

We consider sparse mobile ad-hoc networks (i.e., disruption-tolerant networks or DTNs) wherein a direct communication path from a source to a destination via multiple hops does not exist due to both mobility and sparseness of the nodes. Hence, the nodes will deliver messages from source to destination using a “store, carry, and forward” strategy. Our goal is to analytically study the packet latency in such networks for a two-hop unicast scenario with bursty packet arrivals at the source. We exploit an embedded Markov chain approach combined with our novel iterative estimation technique to study both network delay and queuing delay. Constraints posed by both the limited node buffer size and contention between nodes for wireless channel are also considered in order to obtain a more realistic model. Finally, our iterative results are validated using simulations for well-known mobility models such as random walk on a grid and the random waypoint mobility.

Many analytic results for the connectivity, coverage, and capacity of wireless networks have been reported for the case where the number of nodes, n , tends to infinity (large-scale networks). The majority of these results have not been extended for small or moderate values of n ; whereas in many practical networks, n is not very large. In this article, we consider finite (small-scale) wireless sensor networks. We first show that previous asymptotic results provide poor approximations for such networks. We provide a set of differences between small-scale and large-scale analysis and propose a methodology for analysis of finite sensor networks. Furthermore, we consider two models for such networks: unreliable sensor grids and sensor networks with random node deployment. We provide easily computable expressions for bounds on the coverage and connectivity of these networks. With validation from simulations, we show that the derived analytic expressions give very good estimates of such quantities for finite sensor networks. Our investigation confirms the fact that small-scale networks possess unique characteristics different from their large-scale counterparts, necessitating the development of a new framework for their analysis and design.

The design of biologically-inspired wireless communication systems using bacteria as the basic element of the system is initially motivated by a phenomenon called Quorum Sensing. Due to high randomness in the individual behavior of a bacterium, reliable communication between two bacteria is almost impossible. Therefore, we have recently proposed that a population of bacteria in a cluster is considered as a bio node in the network capable of molecular transmission and reception. This proposition enables us to form a reliable bio node out of many unreliable bacteria. In this paper, we study the communication between two nodes in such a network where information is encoded in the concentration of molecules by the transmitter. The molecules produced by the bacteria in the transmitter node propagate through the diffusion channel. Then, the concentration of molecules is sensed by the bacteria population in the receiver node which would decode the information and output light or fluorescent as a result. The uncertainty in the communication is caused by all three components of communication, i.e., transmission, propagation and reception. We study the theoretical limits of the information transfer rate in the presence of such uncertainties. Finally, we consider M-ary signaling schemes and study their achievable rates and corresponding error probabilities.

The problem of the universal compression of a sequence from a library of several small to moderate length sequences from similar context arises in many practical scenarios, such as the compression of the storage data and the Internet traffic. In such scenarios, it is often required to compress and decompress every sequence individually. However, the universal compression of the individual sequences suffers from significant redundancy overhead. In this paper, we aim at answering whether or not having a memory unit in the middle can result in a fundamental gain in the universal compression. We present the problem setup in the most basic scenario consisting of a server node S, a relay node R (i.e., the memory unit), and a client node C.

Consider an intermittently-connected mobile ad-hoc network with a single source/destination aided by n mobile relay nodes each of which has a finite storage buffer. In this paper we develop, for the first time, an analysis of the steady-state performance of multihop routing in such a network with a general mobility model and characterize it in terms of throughput and transmission-cost overhead. We investigate whether multihop routing has any potential for improvement over two hop routing. We show that analytical models for performance under multihop can be obtained by employing queuing-theoretic techniques and embedded-Markov-chain identification. The solution offered is in the form of non-linear steady-state equations which can be efficiently solved iteratively. The key outcome of this work is that multihop can indeed improve upon two-hop routing in the finite-buffer regime, by means of mitigating the reduction in throughput caused by limited storage (leading to blocking/saturation of buffers). However, the improvement in throughput diminishes as the buffer size grows, and comes at the cost of additional relay-to-relay transmissions.

We consider the problem of estimating throughput and average latency in wireless erasure networks with nodes having finite buffers. In these networks, packets are either lost due to link erasures or dropped because of full buffers. Further, a finite-buffer adaptation of backpressure routing policy is used. The exact Markov chain modeling of such networks for the sake of performance analysis turns out to be an extremely difficult problem in general due to the large number of states and their complicated transitions. In this paper, we propose a novel iterative method that estimates the performance parameters of such networks with much less complexity comparing to the exact analysis. The proposed framework leads to an accurate estimate of the steady-state probability distribution of buffer occupancies using which analytical expressions are obtained for throughput and average packet delay in the network. Finally, these analytical results are validated via simulations.

Recently, the existence of considerable amount of redundancy in the Internet traffic has stimulated the deployment of several redundancy elimination techniques within the network. These techniques are often based on either packet-level Redundancy Elimination (RE) or Content-Centric Networking (CCN). However, these techniques cannot exploit sub-packet redundancies. Further, other alternative techniques such as the end-to-end universal compression solutions would not perform well either over the Internet traffic, as such techniques require infinite length traffic to effectively remove redundancy. This paper proposes a memory-assisted universal compression technique that holds a significant promise for reducing the amount of traffic in the networks. The proposed work is based on the observation that if a source is to be compressed and sent over a network, the associated universal code entails a substantial overhead in transmission due to finite length traffic. However, intermediate nodes can learn the source statistics and this can be used to reduce the cost of describing the source statistics, reducing the transmission overhead for such traffics. We present two algorithms (statistical and dictionary-based) for the memory-assisted universal lossless compression of information sources. These schemes are universal in the sense that they do not require any prior knowledge of the traffic's statistical distribution. We demonstrate the effectiveness of both algorithms and characterize the memorization gain using the real Internet traces. Furthermore, we apply these compression schemes to Internet-like power-law graphs and solve the routing problem for compressed flows. We characterize the network-wide gain of the memorization from the information theoretic point of view. In particular, through our analysis on power-law graphs, we show that non-vanishing network-wide gain of memorization is obtained even when the number of memory units is a tiny fraction of the total number of nodes in the network. Finally, we validate our predictions of the memorization gain by simulation on real traffic traces.

In this paper we introduce the first application of the Belief Propagation (BP) algorithm in the design of recommender systems. We formulate the recommendation problem as an inference problem and aim to compute the marginal probability distributions of the variables which represent the ratings to be predicted. However, computing these marginal probability functions is computationally prohibitive for large-scale systems. Therefore, we utilize the BP algorithm to efficiently compute these functions. Recommendations for each active user are then iteratively computed by probabilistic message passing. As opposed to the previous recommender algorithms, BPRS does not require solving the recommendation problem for all the users if it wishes to update the recommendations for only a single active. Further, BPRS computes the recommendations for each user with linear complexity and without requiring a training period. Via computer simulations (using the 100K MovieLens dataset), we verify that BPRS iteratively reduces the error in the predicted ratings of the users until it converges. Finally, we confirm that BPRS is comparable to the state of art methods such as Correlation-based neighborhood model (CorNgbr) and Singular Value Decomposition (SVD) in terms of rating and precision accuracy. Therefore, we believe that the BP-based recommendation algorithm is a new promising approach which offers a significant advantage on scalability while providing competitive accuracy for the recommender systems.

Slepian-Wolf theorem is a well-known framework that targets almost lossless compression of (two) data streams with symbol-by-symbol correlation between the outputs of (two) distributed sources. However, this paper considers a different scenario which does not fit in the Slepian-Wolf framework. We consider two identical but spatially separated sources. We wish to study the universal compression of a sequence of length n from one of the sources provided that the decoder has access to (i.e., memorized) a sequence of length m from the other source. Such a scenario occurs, for example, in the universal compression of data from multiple mirrors of the same server. In this setup, the correlation does not arise from symbol-by-symbol dependency of two outputs from the two sources. Instead, the sequences are correlated through the information that they contain about the unknown source parameter. We show that the finite-length nature of the compression problem at hand requires considering a notion of almost lossless source coding, where coding incurs an error probability pe(n) that vanishes with sequence length n. We obtain a lower bound on the average minimax redundancy of almost lossless codes as a function of the sequence length n and the permissible error probability pewhen the decoder has a memory of length m and the encoders do not communicate. Our results demonstrate that a strict performance loss is incurred when the two encoders do not communicate even when the decoder knows the unknown parameter vector (i.e., m → ∞).

Many applications require data processing to be performed on individual pieces of data which are of finite sizes, e.g., files in cloud storage units and packets in data networks. However, traditional universal compression solutions would not perform well over the finite-length sequences. Recently, we proposed a framework called memory-assisted universal compression that holds a significant promise for reducing the amount of redundant data from the finite-length sequences. The proposed compression scheme is based on the observation that it is possible to learn source statistics (by memorizing previous sequences from the source) at some intermediate entities and then leverage the memorized context to reduce redundancy of the universal compression of finite-length sequences. We first present the fundamental gain of the proposed memory-assisted universal source coding over conventional universal compression (without memorization) for a single parametric source. Then, we extend and investigate the benefits of the memory-assisted universal source coding when the data sequences are generated by a compound source which is a mixture of parametric sources. We further develop a clustering technique within the memory-assisted compression framework to better utilize the memory by classifying the observed data sequences from a mixture of parametric sources. Finally, we demonstrate through computer simulations that the proposed joint memorization and clustering technique can achieve up to 6-fold improvement over the traditional universal compression technique when a mixture of non-binary Markov sources is considered.

The design of biological networks using bacteria as the basic elements of the network is initially motivated by a phenomenon called quorum sensing. Through quorum sensing, each bacterium performs sensing the medium and communicating it to others via molecular communication. As a result, bacteria can orchestrate and act collectively and perform tasks impossible otherwise. In this paper, we consider a population of bacteria as a single node in a network. In our version of biological communication networks, such a node would communicate with one another via molecular signals. As a first step toward such networks, this paper focuses on the study of the transfer of information to the population (i.e., the node) by stimulating it with a concentration of special type of a molecules signal. These molecules trigger a chain of processes inside each bacteria that results in a final output in the form of light or fluorescence. Each stage in the process adds noise to the signal carried to the next stage. Our objective is to measure (compute) the maximum amount of information that we can transfer to the node. This can be viewed as the collective sensing capacity of the node. The molecular concentration, which carries the information, is the input to the node, which should be estimated by observing the produced light as the output of the node (i.e., the entire population of bacteria forming the node. The molecules are trapped in the bacteria receptors forming complexes inside the bacteria which affect the genes responsible for producing the light. We focus on the noise caused by the random process of trapping molecules at the receptors as well as the variation of outputs of different bacteria in the node. The optimal input distribution to maximize the mutual information between the output of the node, e.g., light, and the applied molecule concentration is derived. Further, the capacity variation with the number of bacteria in the node and the number of receptors per bacteria is obtained. Finally, we investigated the collective sensing capability of the node when a specific form of molecular signaling concentration (which resembles M-ary modulation) is used. The achievable sensing capacity and the corresponding error probabilities were obtained for such practical signaling techniques.

Molecular communication is an expanding body of research. Recent advances in biology have encouraged using genetically engineered bacteria as the main component in the molecular communication. This has stimulated a new line of research that attempts to study molecular communication among bacteria from an information-theoretic point of view. Due to high randomness in the individual behavior of the bacterium, reliable communication between two bacteria is almost impossible. Therefore, we recently proposed that a population of bacteria in a cluster is considered as a node capable of molecular transmission and reception. This proposition enables us to form a reliable node out of many unreliable bacteria. The bacteria inside a node sense the environment and respond accordingly. In this paper, we study the communication between two nodes, one acting as the transmitter and the other as the receiver. We consider the case in which the information is encoded in the concentration of molecules by the transmitter. The molecules produced by the bacteria in the transmitter node propagate in the environment via the diffusion process. Then, their concentration sensed by the bacteria in the receiver node would decode the information. The randomness in the communication is caused by both the error in the molecular production at the transmitter and the reception of molecules at the receiver. We study the theoretical limits of the information transfer rate in such a setup versus the number of bacteria per node. Finally, we consider M-ary modulation schemes and study the achievable rates and their error probabilities.

In this paper, for the first time, we introduce a Belief Propagation (BP)-based distributed trust and reputation management algorithm. The proposed algorithm can be utilized in many distributed systems from Peer-to-peer (P2P) networks to social and mesh networks. In this work, we focus on P2P networks and explore the application of BP-based trust and reputation management in a decentralized environment in the presence of malicious peers. In a typical P2P trust and reputation management system, after each transaction, the client peer (who receives a service) provides its rating about the quality of the service provided by the server peer for that transaction. In such a system, we view the problem of trust and reputation management as to compute two sets of variables: 1. the reputation parameters of peers based on their quality of service, and 2. the trustworthiness parameters of peers based on the ratings they provide after each transaction. We distinguish between these two parameters as a peer might provide high quality service as a server while providing malicious ratings as a client. The proposed scheme, referred to as BP-P2P, relies on the BP algorithm in an appropriately chosen factor graph representation of the P2P network. The reputation and trustworthiness parameters are computed by a BP-based distributed message passing algorithm between the peers on the factor graph. We provide a detailed evaluation of BP-P2P via analysis and computer simulations. We show that BP-P2P is very robust in computing trustworthiness values and filtering out malicious ratings. Specifically, we prove that BP-P2P iteratively reduces the error in the reputation values of peers due to the malicious ratings with a high probability. Further, comparison of BP-P2P with some well-known and commonly used P2P reputation management techniques (e.g., EigenTrust and Bayesian Framework) indicates the superiority of the proposed scheme in terms of robustness against malicious behavior. We also show that the computational complexity of BP-P2P grows only linearly with the number of peers and the communication overhead of BP-P2P is lower than the well-known EigenTrust algorithm.

In this paper, we introduce the first application of the belief propagation algorithm in the design and evaluation of trust and reputation management systems. We approach the reputation management problem as an inference problem and describe it as computing marginal likelihood distributions from complicated global functions of many variables. However, we observe that computing the marginal probability functions is computationally prohibitive for large-scale reputation systems. Therefore, we propose to utilize the belief propagation algorithm to efficiently (in linear complexity) compute these marginal probability distributions; resulting a fully iterative probabilistic and belief propagation-based approach (referred to as BP-ITRM). BP-ITRM models the reputation system on a factor graph. By using a factor graph, we obtain a qualitative representation of how the consumers (buyers) and service providers (sellers) are related on a graphical structure. Further, by using such a factor graph, the global functions factor into products of simpler local functions, each of which depends on a subset of the variables. Then, we compute the marginal probability distribution functions of the variables representing the reputation values (of the service providers) by message passing between nodes in the graph. We show that BP-ITRM is reliable in filtering out malicious/unreliable reports. We provide a detailed evaluation of BP-ITRM via analysis and computer simulations. We prove that BP-ITRM iteratively reduces the error in the reputation values of service providers due to the malicious raters with a high probability. Further, we observe that this probability drops suddenly if a particular fraction of malicious raters is exceeded, which introduces a threshold property to the scheme. Furthermore, comparison of BP-ITRM with some well-known and commonly used reputation management techniques (e.g., Averaging Scheme, Bayesian Approach, and Cluster Filtering) indicates the superiority of the proposed scheme in terms of robustness against attacks (e.g., ballot stuffing, bad mouthing). Finally, BP-ITRM introduces a linear complexity in the number of service providers and consumers, far exceeding the efficiency of other schemes.

Delay/Disruption Tolerant Networks (DTNs) have been identified as one of the key areas in the field of wireless communication, wherein sparseness and delay are particularly high. They are emerging as a promising technology in vehicular, planetary/interplanetary, military/tactical, disaster response, underwater and satellite networks. DTNs are characterized by large end-to-end communication latency and the lack of end-to-end path from a source to its destination. These characteristics pose several challenges to the security of DTNs. Especially, Byzantine attacks in which one or more legitimate nodes have been compromised and fully controlled by the adversary can give serious damages to the network in terms of latency and data availability. Using reputation-based trust management systems is shown to be an effective way to handle the adversarial behavior in Mobile Ad hoc Networks (MANETs). However, because of the unique characteristics of DTNs, those traditional techniques do not apply to DTNs. Our main objective in this paper is to develop a robust trust mechanism and an efficient and low cost malicious node detection technique for DTNs. Inspired by our recent results on reputation management for online systems and e-commerce, we develop an iterative malicious node detection mechanism for DTNs referred as ITRM. The proposed scheme is a graph-based iterative algorithm motivated by the prior success of message passing techniques for decoding low-density parity-check codes over bipartite graphs. Applying ITRM to DTNs for various mobility models, we observed that the proposed iterative reputation management scheme is far more effective than well-known reputation management techniques such as the Bayesian framework and EigenTrust. Further, we concluded that the proposed scheme provides high data availability and packet-delivery ratio with low latency in DTNs under various adversary attacks which attempt to both undermine the trust and detection scheme and the packet delivery protocol.

Security services such as data confidentiality, authenticity, and availability are critical in wireless sensor networks (WSNs) deployed in adversarial environments. Due to the resource constrain's of sensor nodes, the existing protocols currently in use in adhoc networks cannot be employed in WSNs. In this article, we propose a protocol called location-aware network-coding security (LNCS) that provides all the aforementioned security services. By dividing the terrain into nonoverlapping cells, the nodes take advantage of the location information to derive different location-binding keys. The key idea in LNCS is that all the nodes involved in the protocol collaborate in every phase. We employ random network coding in order to provide data availability significantly higher than that in other schemes. A hash tree-based authentication mechanism is utilized to filter the bogus packets enroute. We provide a comparison between our scheme and previously proposed schemes. The results reveal significant improvement in data availability while maintaining the same level of data confidentiality and authenticity.

In this paper, we investigate the redundancy in the universal compression of finite length smooth parametric sources. Rissanen demonstrated that for a smooth parametric source with d unknown parameters, the expected redundancy for regular codes is asymp totically given by | logn + o(logn) for almost all sources. Clarke and Barron derived the "minimax expected redundancy" for memoryless sources, which is the maximum redundancy of the best code over the space of source parameters. However, the minimax redundancy is for a particular parameter value, which does not provide much insight about different source parameters. We derived a lower bound on the compression of finite-length memoryless sequences using a probabilistic treatment. In this paper, we extend our analysis to smooth parametric sequences. We focus on two part codes with an asymptotic 0(1) extra redundancy. We also require that the length function be regular, which is not restrictive since all codes that we know are regular.

In a typical reputation management system, after each transaction, the buyer (who receives a service or purchases a product) provides its report/rating about the quality of the seller for that transaction. In such a system, the problem of reputation management is to compute two sets of variables: 1. the (global) reputation parameters of entities who act as sellers, and 2. the trustworthiness parameters of the entities who act as the raters (i.e., buyers). In this paper, for the first time, we introduce an iterative probabilistic method for reputation management. The proposed scheme, referred to as RPM, relies on a probabilistic message passing algorithm in the graph-based representation of the reputation management problem on an appropriately chosen factor graph. In the graph representation of the problem, the sellers and buyers are arranged as two sets of variable and factor nodes, respectively, that are connected via some edges. Then, the reputation and trustworthiness parameters are computed by a fully iterative and probabilistic message passing algorithm between these nodes in the graph. We provide a detailed evaluation of RPM via computer simulations. We observe that RPM iteratively reduces the error in the reputation estimates of the sellers due to the malicious raters. Finally, comparison of RPM with some well- known and commonly used reputation management techniques (e.g., Averaging Scheme, Bayesian Approach and Cluster Filtering) indicates the superiority of the proposed scheme both in terms of robustness against attacks (e.g., ballot-stuffing, bad-mouthing) and computational efficiency.

This paper introduces the first application of Belief Propagation (BP) in reputation systems. We view the reputation management as an inference problem, and hence, describe the reputation management problem as computing marginal likelihood distributions from complicated global functions of many variables. However, we observe that computing the marginal probability functions of the reputation variables is computationally prohibitive for large scale reputation systems. Therefore, we propose to utilize the BP algorithm to efficiently (i.e., in linear complexity) compute these marginal probability distributions; leading to a fully iterative probabilistic and BP-based approach (referred to as BP-ITRM). BP-ITRM describes the reputation system on a factor graph, using which we can obtain a qualitative representation of how the service providers (sellers) and consumers (buyers) are related. Further, by using such a graph representation, we compute the marginal probability distribution functions of the variables representing the global reputation values via an iterative message passing algorithm. We show that BP-ITRM significantly outperforms the well-known and commonly used reputation management schemes such as the Averaging Scheme, Bayesian Approach and Cluster Filtering in the presence of attackers. Further, its complexity is linear in the number of service providers and consumers, far exceeding the efficiency of other schemes.

In this paper, we investigate the redundancy of universal coding schemes on smooth parametric sources in the finite-length regime. We derive an upper bound on the probability of the event that a sequence of length n, chosen using Jeffreys' prior from the family of parametric sources with d unknown parameters, is compressed with a redundancy smaller than (1 - ∈) d/2 log n for any ∈ >; 0. Our results also confirm that for large enough n and d, the average minimax redundancy provides a good estimate for the redundancy of most sources. Our result may be used to evaluate the performance of universal source coding schemes on finite-length sequences. Additionally, we precisely characterize the minimax redundancy for two-stage codes. We demonstrate that the two-stage assumption incurs a negligible redundancy especially when the number of source parameters is large. Finally, we show that the redundancy is significant in the compression of small sequences.

In diffusion-based molecular communications, messages can be conveyed via the variation in the concentration of molecules in the medium. In this paper, we intend to analyze the achievable capacity in transmission of information from one node to another in a diffusion channel. We observe that because of the molecular diffusion in the medium, the channel possesses memory. We then model the memory of the channel by a two-step Markov chain and obtain the equations describing the capacity of the diffusion channel. By performing a numerical analysis, we obtain the maximum achievable rate for different levels of the transmitter power, i.e., the molecule production rate.

A diffusion-based molecular communication system has two major components: the diffusion in the medium, and the ligand-reception. Information bits, encoded in the time variations of the concentration of molecules, are conveyed to the receiver front through the molecular diffusion in the medium. The receiver, in turn, measures the concentration of the molecules in its vicinity in order to retrieve the information. This is done via ligand-reception process. In this paper, we develop models to study the constraints imposed by the concentration sensing at the receiver side and derive the maximum rate by which a ligand-receiver can receive information. Therefore, the overall capacity of the diffusion channel with the ligand receptors can be obtained by combining the results presented in this paper with our previous work on the achievable information rate of molecular communication over the diffusion channel.

Several studies have identified a significant amount of redundancy in the network traffic. For example, it is demonstrated that there is a great amount of redundancy within the content of a server over time. This redundancy can be leveraged to reduce the network flow by the deployment of memory units in the network. The question that arises is whether or not the deployment of memory can result in a fundamental improvement in the performance of the network. In this paper, we answer this question affirmatively by first establishing the fundamental gains of memory-assisted source compression and then applying the technique to a network. Specifically, we investigate the gain of memory-assisted compression in random network graphs consisted of a single source and several randomly selected memory units. We find a threshold value for the number of memories deployed in a random graph and show that if the number of memories exceeds the threshold we observe network-wide reduction in the traffic.

In this paper, we present an exact model for the analysis of the performance of Random Linear Network Coding (RLNC) in wired erasure networks with finite buffers. In such networks, packets are delayed due to either random link erasures or blocking by full buffers. We assert that because of RLNC, the content of buffers have dependencies which cannot be captured directly using the classical queueing theoretical models. We model the performance of the network using Markov chains by a careful derivation of the buffer occupancy states and their transition rules. We verify by simulations that the proposed framework results in an accurate measure of the network throughput offered by RLNC. Further, we introduce a class of acyclic networks for which the number of state variables is significantly reduced.

This work investigates the effect of finite buffer sizes on the throughput capacity and packet delay of line networks with packet erasure links that have perfect feedback. These performance measures are shown to be linked to the stationary distribution of an underlying irreducible Markov chain that models the system exactly. Using simple strategies, bounds on the throughput capacity are derived. The work then presents two iterative schemes to approximate the steady-state distribution of node occupancies by decoupling the chain to smaller queueing blocks. These approximate solutions are used to understand the effect of buffer sizes on throughput capacity and the distribution of packet delay. Using the exact modeling for line networks, it is shown that the throughput capacity is unaltered in the absence of hop-by-hop feedback provided packet-level network coding is allowed. Finally, using simulations, it is confirmed that the proposed framework yields accurate estimates of the throughput capacity and delay distribution and captures the vital trends and tradeoffs in these networks.

Multi-channel, multi-interface ad hoc wireless networks can obtain substantial capacity improvements by mitigating co-channel interference. Channel assignment and routing algorithms that relieve co-channel interference and balance traffic loads are critical for obtaining these large capacity increases. However, with a limited number of channels and interfaces, this approach cannot avoid traffic overload as the network traffic increases. This paper proposes a novel scheme of multi-channel/interface network coding that is based on the combination of a new concept of coded-overhearing and coding-aware channel assignment. The proposed algorithms overcome the radio coverage limitations present in conventional network coding schemes, and exhibit improved flexibility in terms of aggregate throughput when there are an insufficient number of interfaces and a outage of network coding opportunities. Our scheme attains significant improvement in the aggregate throughput as compared to a no network coding scheme.

We consider the problem of distributing a file in a network of storage nodes whose storage budget is limited but at least equals the size file. We first generate T encoded symbols (from the file) which are then distributed among the nodes. We investigate the optimal allocation of T encoded packets to the storage nodes such that the probability of reconstructing the file by using any r out of n nodes is maximized. Since the optimal allocation of encoded packets is difficult to find in general, we find another objective function which well approximates the original problem and yet is easier to optimize. We find the optimal symmetric allocation for all coding redundancy constraints using the equivalent approximate problem. We also investigate the optimal allocation in random graphs. Finally, we provide simulations to verify the theoretical results.

The exact Markov modeling analysis of erasure networks with finite buffers is an extremely hard problem due to the large number of states in the system. In such networks, packets are lost due to either link erasures or blocking by the full buffers. In this paper, we propose a novel method that iteratively estimates the performance parameters of the network and more importantly reduces the computational complexity compared to the exact analysis. This is the first work that analytically studies the effect of finite memory on the throughput and latency in general wired acyclic networks with erasure links. As a case study, a random packet routing scheme with ideal feedback on the links is used. The proposed framework yields a fairly accurate estimate of the probability distribution of buffer occupancies at the intermediate nodes using which we can not only identify the congested and starving nodes but also obtain analytical expressions for throughput and average delay of a packet in the network. The theoretical framework presented here can be applied to many wired networks, from Internet to more futuristic applications such as networks-on-chip under various communication and network coding scenarios.

In this paper we report our progress in the first application of iterative probabilistic algorithms in the design and evaluation of recommender systems. The proposed iterative recommender system (referred to as BPRS) is based on the belief propagation, a powerful decoding algorithm for turbo codes and Low-Density Parity-Check (LDPC) codes. The belief propagation algorithm relies on a graph-based representation of an appropriately chosen factor graph for the recommender systems. The factor graph representation of the recommender systems turned out to be a bipartite graph, where the users and products are arranged as two sets of variable and factor nodes that are connected via some edges. Recommendations (predicted ratings) for each particular user can be computed by probabilistic message passing between nodes in the graph. We provide an evaluation of BPRS via computer simulations using the MovieLens dataset. We observed that BPRS iteratively reduces the error in the predicted ratings of the users until it converges. Further, our initial results indicate an improvement in the Mean Average Error (MAE) and Root Mean Square Error (RMSE) over the Item Averaging. Therefore, we are confident that the belief propagation is a new promising approach which will offer robustness and accuracy for the recommender systems.

We investigate the problem of reliable and energy-efficient one-to-all broadcasting in multihop wireless networks, and propose fractional transmission scheme (FTS) - a low-complexity and scalable broadcasting scheme. FTS exploits the broadcasting nature of wireless channels and random encoding of rateless codes to reduce energy consumption while ensuring reliable delivery of packets to all nodes in the network. In the proposed scheme, different neighbors of a node share the responsibility of transmitting packets by sending only a fraction of encoded packets required by the node to successfully receive the data sent by the source. A detailed analysis of the performance of FTS is presented for grid and random deployment networks. Further, extensive simulations compare our scheme with present energy-efficient methods such as random linear coding, multipoint relaying, dominant pruning, and broadcast incremental power scheme. Simulations reveal that FTS offers good performance and adaptability at a low computational cost.

Trust and reputation play critical roles in most environments wherein entities participate in various transactions and protocols among each other. The recipient of the service has no choice but to rely on the reputation of the service provider based on the latter's prior performance. This paper introduces an iterative method for trust and reputation management referred as ITRM. The proposed algorithm can be applied to centralized schemes, in which a central authority collects the reports and forms the reputations of the service providers as well as report/rating trustworthiness of the (service) consumers. The proposed iterative algorithm is inspired by the iterative decoding of low-density parity-check codes over bipartite graphs. The scheme is robust in filtering out the peers who provide unreliable ratings. We provide a detailed evaluation of ITRM via analysis and computer simulations. Further, comparison of ITRM with some well-known reputation management techniques (e.g., Averaging Scheme, Bayesian Approach and Cluster Filtering) indicates the superiority of our scheme both in terms of robustness against attacks (e.g., ballot-stuffing, bad-mouthing) and efficiency. Furthermore, we show that the computational complexity of the proposed ITRM is far less than the Cluster Filtering; which has the closest performance (to ITRM) in terms of resiliency to attacks. Specifically, the complexity of ITRM is linear in the number of clients, while that of the Cluster Filtering is quadratic.

The problem of computing the throughput capacity of general unicast in a Delay-Tolerant Network under the finite-buffer regime is addressed in this paper. A sparse mobile wireless network deployed on an M times M square-grid is considered, wherein m unique mobile source/destination pairs communicate with the aid of n mobile relay nodes using the store, carry, and forward paradigm. Each mobile relay node is equipped with a finite storage. Thus, several source/destination pairs contend for limited network resources. Under this setup, the throughput achieved per source-destination pair at steady-state node-mobility is analyzed, incorporating practical considerations such as node-to-node contention and finite communication range, for a class of two-hop relay protocols. In addition, two different approaches for buffer management are considered. The paper shows that, using a novel approach based on embedded Markov-chains, accurate analysis of the throughput can be achieved for the above model, as it is validated by simulations. A significant conclusion of this work is that considerable throughput improvements can be achieved by judicially managing the relay-node buffer-space.

Efforts to improve the capacity of multi-channel, multi-interface wireless mesh networks have mainly focused on mitigating channel interference and balancing traffic loads. In a limited number of channels and interfaces, this approach cannot help encountering the network overload and traffic saturation, as network traffic increases. It will be serious, especially at intersecting nodes such as the nodes around gateways for last-mile connectivity. Considering this situation, which degrades the aggregate throughput of networks, a more aggressive strategy to cope with network traffic saturation is necessary. We propose a novel cooperative network coding scheme, which exploits coded-overhearing, for unicast in multi-channel, multi-interface wireless mesh networks. Further, we present a coding-aware channel assignment algorithm with new metrics to support our network coding scheme, resulting in substantial improvement in the aggregate throughput. The combination of the proposed network coding scheme and the channel assignment algorithm contributes to overcoming geographical limitations in conventional network coding. It also shows better flexibility for the insufficient number of interfaces and the outage of coding opportunities. Our evaluation results show maximally a 52% improvement in terms of the aggregate throughput by using our coded-overhearing algorithm with a coding-aware channel assignment.

In this paper, we address the problem of distributing a large amount of bulk data to a sparse vehicular network from roadside infostations, using efficient vehicle-to-vehicle collaboration. Due to the highly dynamic nature of the underlying vehicular network topology, we depart from architectures requiring centralized coordination, reliable MAC scheduling, or global network state knowledge, and instead adopt a distributed paradigm with simple protocols. In other words, we investigate the problem of reliable dissemination from multiple sources when each node in the network shares a limited amount of its resources for cooperating with others. By using rateless coding at the Road Side Unit (RSU) and using vehicles as data carriers, we describe an efficient way to achieve reliable dissemination to all nodes (even disconnected clusters in the network). In the nutshell, we explore vehicles as mobile storage devices. We then develop a method to keep the density of the rateless codes packets as a function of distance from the RSU at the desired level set for the target decoding distance. We investigate various tradeoffs involving buffer size, maximum capacity, and the mobility parameter of the vehicles.

Consider a mobile network wherein nodes are confined to move and communicate in a given area. The network is assumed to be sparse, wherein a direct communication path from a source node via multiple hops to a destination node almost never exists. The nodes resort to storing, carrying, and forwarding packets when a contact occurs, as a means of communication. This paper investigates the question of computing the throughput capacity of the resulting network, in other words, the rate at which a source node can send packets to a destination node using the other nodes in the network as relays. It proposes an accurate generalized framework valid for any mobility model that exhibits stationarity. The framework uses the embedded Markov-Chain approach using which the capacity of such a network can be accurately determined by computing certain well-defined characteristic parameters from the mobility model. Constraints posed by limited node storage and contention between nodes for the wireless channel are also considered in order to obtain a realistic model for the throughput. The paper also illustrates the proposed framework under two specific cases: the random walk, random waypoint, and restricted random waypoint mobility models, and validates the same using simulations.

In this paper, we study rate-compatible puncturing of finite-length low-density parity-check (LDPC) codes. We present a novel rate-compatible puncturing scheme that is easy to implement. Our scheme uses the idea that the degradation in performance is reduced by selecting a puncturing pattern wherein the punctured bits are far apart from each other in the Tanner graph of the code. Although the puncturing scheme presented is tailored to regular codes, it is also directly applicable to irregular parent ensembles. By simulations, the proposed rate-compatible puncturing scheme is shown to be superior to the existing puncturing methods for both regular and irregular LDPC codes over the binary erasure channel (BEC) and the additive white Gaussian noise (AWGN) channel.

In this paper, we propose a novel threshold key pre-distribution scheme for wireless sensor networks using symmetric multivariate polynomials. In the proposed scheme, called multi-variate key pre-distribution scheme (MKPS), every node is assigned a unique d-tuple as its ID. The ID assignment mechanism is used to distribute shares of multivariate polynomials among nodes prior to the network deployment. After the deployment, some nodes can establish exactly (d-1) common keys. The final secret key is a symmetric combination of all these keys. We show that this feature significantly improves the security of MKPS over previous schemes. We also propose a procedure to choose a dimension d that is optimal with respect to network resiliency and network connectivity. We provide complete security and performance evaluations of MKPS. Results reveal that the proposed scheme provides robustness in design and outperforms the previous schemes in term of the network resiliency against the node capture without increasing the memory requirement.

In this paper, we propose a new multicast subgraph construction algorithm and a distributed source coding-based multicast (DSCM) protocol for multihop wireless networks. The DSCM emphasize reliability, rate optimality, and energy efficiency. Both algorithms are based on local knowledge of the network. DSCM uses rateless error correcting codes to provide reliability and rate optimality, and distributed source coding to ensure the energy efficiency. We compared our scheme to energy-efficient methods such as network coding (NC) and multicast incremental power (MIP). Simulation results show DSCM performs close to these algorithms. However unlike the proposed algorithm, NC and MIP assume full knowledge of the network topology and have much higher decoding complexity than DSCM.

This paper propose a secure and efficient routing scheme using a game theoretical approach and trust relationships between the nodes. We assume a ldquoBayesian Gamerdquo model among the nodes to find the optimal behavior of legitimate and malicious nodes. Moreover, using a ldquowatchdogrdquo mechanism and an ldquoacknowledgementrdquo mechanism (ACK), we construct trust relationships between the nodes.

Modeling the fundamental limits of communication in intermittently connected mobile wireless scenarios is an important problem in understanding such networks. Real-world deployments such as delay tolerant networks (DTNs) exhibit such intermittent connectivity. In addition, the effect of finite buffers in such communication paradigms requires investigation. This paper deals with the problem of modeling the throughput and message delivery delay in networks modeled by nodes performing a random walk on a grid-graph. In addition to finite buffer effects, features such as channel access constraints are introduced in the model , presenting a fairly realistic networking scenario. By means of identifying simple, finite-state embedded Markov chains in such mobile systems, closed-form solutions for the problems addressed may be obtained.

This paper proposes a reliable and secure broadcast protocol for ad hoc wireless networks. Since coding and security compete for the same resources, we jointly solve for reliability, availability and integrity for a broadcast scenario. Packets sent by the source node would travel in a hop-by-hop fashion to the other nodes. Hence, it is critical to reduce the number of transmissions and latency. We assume Byzantine attacks in which the adversary can drop (or modify) legitimate packets and inject its own packets via several insider nodes. We require that the source data is reached to all legitimate nodes in the presence of any number of colluding Byzantine attackers as long as the legitimate nodes are connected. We also require that each receiver node in the network to be equipped with a mechanism to verify the source node and the integrity of the received packets using limited cryptographic primitives. It is essential that every node receiving a malicious packet immediately filters it out and uses only the legitimate ones for forwarding to the next hop and decoding. Designing a broadcasting mechanism that satisfies all the above requirements is a very challenging problem. We develop an authentication scheme, using a reliable and energy-efficient broadcasting protocol called Collaborative Rateless Broadcast (CRBcast) and limited cryptographic primitives. On contrary to the previous schemes, our scheme is resilient with respect to Byzantine failures as well as routing and flooding attacks and protocol exploits. Moreover, we compared our scheme with the previously proposed broadcast authentication schemes and showed that our scheme outperforms them in terms of efficiency. This is a crucial improvement over the previous schemes that ensure availability by flooding, but with very large communication overhead and latency.

In the past, many analytic results for wireless networks have been reported for the case where the number of nodes n in the network tends to infinity (large-scale networks). These include connectivity, coverage, and capacity. These results have not been extended for small or moderate values of n, although in many practical networks n is not very large. In this paper, we first show that previous asymptotic results provide poor approximations for the finite networks (small-scale networks). We then aim to develop a framework to analytically study network properties without assuming that n is large. We provide a set of differences between small-scale and large-scale analysis. We consider wireless networks in which the location of the nodes is random. We study routing algorithms, coverage, connectivity and capacity of finite wireless networks. We provide easily computable expressions for different network properties. With validation from simulations, we show that these analytic expressions give very good estimates of these quantities for finite wireless networks. Our investigation suggests that the small- scale networks posses unique characteristics that require a new framework for analysis and design.

In this paper, we propose and evaluate two distributed protocols for finding low-cost broadcast and multicast trees in wireless networks. The constructed trees can then be used for reliable and energy-efficient data broadcast and multicast in wireless networks. The proposed schemes, referred to as broadcast decremental power (BDP) and multicast decremental power (MDP), evolve a given spanning tree of a network and form other spanning trees with lower costs of broadcast/multicast. In our schemes, the Bellman-Ford (BF) tree is considered as the initial spanning tree. Links in a network are assumed to have some cost based on parameters such as the distance between nodes, link losses, etc. We consider two different network scenarios. In the first one, nodes in the network have adjustable transmission power, and in the second one, the transmission power is fixed. Exhaustive simulation results are provided for the two different communication power scenarios and different network topologies to evaluate the proposed schemes. We show that broadcast/multicast cost is substantially improved over BF and previous well-known centralized schemes such as broadcast incremental power (BIP) and multicast incremental power (MIP), which can be implemented for the adjustable radius model. For the fixed power model, substantial improvement over BF and Network Coding (NC) is observed.

In this paper, we propose a scheme for distributed source coding of correlated sources using a single systematic LDPC code. In particular, since we are interested in wireless sensor network applications, we consider LDPC codes with short to moderate lengths that achieve every arbitrary coding rate on the Slepian-Wolf rate region. We simplify the distributed source coding problem to the rate-compatible LDPC code design with an unequal error protection property. The decoders communicate to each other to exchange information bits prior to decoding. However, thereafter, each performs the decoding independently. Therefore, errors in one decoder do not affect the other one. The simulation results confirm that the gap from the theoretical limit remains almost the same for different rates on the Slepian-Wolf rate region. First, we consider two correlated sources. We show that our proposed scheme improves the performance of distributed source coding of two sources considerably. This benefit is more stressed for application with short to moderate length sequences. Then, we study distributed source coding of three sources. As a special case, we investigate three sources that are pairwise correlated with the same correlation probability. We show that the gap from the theoretical limit is smaller than that of previous work. We also investigate the distributed source coding of correlated sources when there is no prior knowledge of the correlation parameter at the time of code design. We note that although the proposed distributed source coding is well suited for sensor networks (where sequences with less than 10000 bits are used), the method can be generalized to other distributed source coding applications.

This paper introduces a novel two-phase broadcast scheme referred to as collaborative rateless broadcast (CRBcast). CRBcast is a scalable approach for reliable and energy-efficient broadcasting in a multihop wireless sensor networks that also addresses load balancing, while requiring no knowledge of network topology. CRBcast combines the energy-efficiency offered by probabilistic broadcasting (PBcast) with the reliability features offered by application-layer rateless coding. In the first phase of CRBcast, packets encoded using a rateless code are dispersed into the network based on PBcast. In the second phase, simple collaboration of neighboring nodes ensures that all nodes recover original data with a very high probability of success. Since the performance of CRBcast rests heavily on that of PBcast, first part of this paper analyzes both analytically and via simulations the probabilistic broadcasting scheme. We then study the effectiveness of CRBcast. We show that CRBcast provides both reliability and energy efficiency simultaneously. Simulation results indicate that CRBcast provides an energy savings of at least 72% and 60% in comparison with flooding and PBcast, respectively.

Security services such as data confidentiality, authenticity, and availability are critical in wireless sensor networks deployed in adversarial environments. Due to the resource constrains of sensor nodes, the existing protocols currently in use in ad-hoc networks cannot be employed in wireless sensor networks. In this paper, we propose a protocol called location-aware network coding security (LNCS) that provides all the aforementioned security services. By dividing the terrain into non-overlapping cells, the nodes take advantage of the location information to derive different location binding keys. An event in the field is sensed by several nodes and aggregated by all of them. Using a secret sharing algorithm, the aggregated information is divided into several shares that are forwarded toward the sink in a cell-by-cell fashion. The key idea in LNCS is that all the nodes involved in the protocol collaborate in every phase. We employ random network coding in our scheme to provide data availability significantly higher than that in other schemes. To generate authentication information, a hash tree is constructed on the generated packets. The packets that fail the authenticity test are considered as bogus and filtered enroute. Every node transmits only a small fraction of the generated packets along the corresponding authentication information to the next cell. The sink is the final entity being able to reconstruct the original message using a few shares of the message. We have provided a comparison between our scheme and previously proposed schemes. The results reveal significant improvement in data availability while maintaining the same level of data confidentiality and authenticity.

Privacy is a critical service in node-to-node communications when sensor networks are deployed in adversarial environments. However, providing this service is a nontrivial task because of the lack of infrastructure and node limitations. Existing techniques distribute secret keys to the network users through a trusted third party or using computationally-complex public-key methods. An alternative approach is pre-distributing keying material to the nodes prior to the network deployment. Exploiting the mathematical properties of symmetric polynomials, we propose a multivariate key pre-distribution scheme (MKPS) in this paper. In this scheme, using uniquely assigned IDs, shares of d-variate polynomials are stored into the memory of every sensor. After the network deployment, every two neighbor nodes at the unit Hamming distance of each other establish exactly d-1 common keys without any interaction with a third party in the network. The final secret key used by these nodes is a symmetric combination of all the common keys. We will show that this feature significantly improves the security of the MKPS over previous schemes. The proposed method is in the category of threshold schemes, i.e., it remains perfectly secure up to the capture of a certain fraction of sensor nodes. We also propose a location-aware MKPS in which, by taking advantage of the location information, perfect connectivity is achieved. The new location-aware scheme is a cell-based method in which nodes are randomly deployed within hexagonal cells. Nodes are unaware of their exact locations. Nevertheless, they know the coordinates of their residing cells. One MKPS is used to secure communications within every cell and one to secure communications between cells. This location-based scheme significantly improves the resiliency of the network against the node capture.

The problem of reliable and energy-efficient one-to-all broadcasting in multihop wireless networks is investigated in this paper and a low-complexity and scalable scheme (referred to as FTS) is proposed. This scheme utilizes rateless coding and the broadcasting nature of wireless channels to reduce the cost of broadcasting. In FTS, raw data is first encoded, and each node requires to send only a fraction of the total encoded packets. We compare our schemes with present energy-efficient methods such as Network Coding (NC), Multipoint Relaying (MPR), Broadcast Incremental Power (BIP), and Collaborative Rateless Broadcast (CRBcast). Our simulations reveal that our scheme performs well in comparison with these strategies, while having lower complexity and higher adaptability in comparison with some of them.

In this paper, we propose a scheme to construct low-density parity-check (LDPC) codes that are suitable for unequal error protection (UEP). We derive density evolution (DE) formulas for the proposed unequal error protecting LDPC ensembles over the binary erasure channel (BEC). Using the DE formulas, we optimize the codes. For the finite-length cases, we compare our codes with some other LDPC codes, the time-sharing method, and a previous work on UEP using LDPC codes. Simulation results indicate the superiority of the proposed design methodology for UEP

This paper first introduces an improved decoding algorithm for low-density parity-check (LDPC) codes over binary-input-output-symmetric memoryless channels. Then some fundamental properties of punctured LDPC codes are presented. It is proved that for any ensemble of LDPC codes, there exists a puncturing threshold. It is then proved that for any rates R1and R2satisfying 0121to R2resulting in asymptotically good codes for all rates R1lesRlesR2. Specifically, this implies that rates arbitrarily close to one are achievable via puncturing. Bounds on the performance of punctured LDPC codes are also presented. It is also shown that punctured LDPC codes are as good as ordinary LDPC codes. For BEC and arbitrary positive numbers R121lesRlesR2is shown. Based on the above observations, a method is proposed to design good punctured LDPC codes over a broad range of rates. Finally, it is shown that the results of this paper may be used for the proof of the existence of the capacity-achieving LDPC codes over binary-input-output-symmetric memoryless channels

In this correspondence, a generalization of rateless codes is proposed. The proposed codes provide unequal error protection (UEP). The asymptotic properties of these codes under the iterative decoding are investigated. Moreover, upper and lower bounds on maximum-likelihood (ML) decoding error probabilities of finite-length LT and Raptor codes for both equal and unequal error protection schemes are derived. Further, our work is verified with simulations. Simulation results indicate that the proposed codes provide desirable UEP. We also note that the UEP property does not impose a considerable drawback on the overall performance of the codes. Moreover, we discuss that the proposed codes can provide unequal recovery time (URT). This means that given a target bit error rate, different parts of information bits can be decoded after receiving different amounts of encoded bits. This implies that the information bits can be recovered in a progressive manner. This URT property may be used for sequential data recovery in video/audio streaming

In this correspondence, we first investigate some analytical aspects of the recently proposed improved decoding algorithm for low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We derive a necessary and sufficient condition for the improved decoding algorithm to successfully complete decoding when the decoder is initialized to guess a predetermined number of guesses after the standard message-passing terminates at a stopping set. Furthermore, we present improved bounds on the number of bits to be guessed for successful completion of the decoding process when a stopping set is encountered. Under suitable conditions, we derive a lower bound on the number of iterations to be performed for complete decoding of the stopping set. We then present a superior, novel improved decoding algorithm for LDPC codes over the binary erasure channel (BEC). The proposed algorithm combines the observation that a considerable fraction of unsatisfied check nodes in the neighborhood of a stopping set are of degree two, and the concept of guessing bits to perform simple and intuitive graph-theoretic manipulations on the Tanner graph. The proposed decoding algorithm has a complexity similar to previous improved decoding algorithms. Finally, we present simulation results of short-length codes over BEC that demonstrate the superiority of our algorithm over previous improved decoding algorithms for a wide range of bit error rates

In this paper, we consider the tradeoffs of binary and M-ary signaling in page-oriented holographic storage systems that multiplex pages using two methods: conventional angle multiplexing throughout the volume and localized recording. We study the mutual information transfer, which is increasingly easy to achieve in practice, between the recorded and recovered data and use it to assess the trade-offs in these systems. We use the transmission model developed by Heanue, Bashaw, and Hesselink [7] for deriving the mutual information bound on capacity and examine the interplay between the storage density and the number of recorded pages within the medium. This result is useful for deciding the number of recorded pages and the desired level of a multi-level modulation code for maximizing the storage density in a volume holographic memory. We analyze our results for localized and angle multiplexed recording and compare the performance in these two cases.

We introduce a construction of raptor codes to be used over symmetric channels. An important property of the proposed scheme is that unlike the previous construction of raptor codes, it allows to design codes that are approaching the capacity of the underlying channel in a rate-compatible way. We also show that for finite-length codes, the proposed construction outperforms the previous constructions of raptor codes.

In this paper, we propose a two-phase broadcasting scheme referred as Collaborative Rateless Broadcast (CRBcast). We are particularly interested in reliability and energy efficiency of the broadcasting scheme for multi-hop wireless sensor networks. Our two-phase protocol is based on Probabilistic Broadcasting (PBcast) and an application layer rateless coding. At the first phase, the rateless-encoded packets are broadcasted based on PBcast, in which each node probabilistically relays every new received packet. The second recovery phase, which is based on simple collaborations of nodes, ensures that all nodes can recover original data. We first investigate PBcast analytically and with simulation, since the characteristics of PBcast influence CRBcast. Then, we investigate the effectiveness of CRBcast. We show that CRBcast can provide both reliability and energy efficiency. Simulation results indicate that CRBcast saves at least 72% and 60% energy in comparison with flooding and PBcast, respectively.

Energy efficiency is a very critical consideration in the design of low cost sensor networks which typically have fairly low node battery life. This raises the need for providing periodic sleep cycles for the radios in the sensor nodes. Keeping sensors in sleep state also implies that node to sink communication incurs certain delays and there exists a threshold on the duty cycling for the communication delay to be bounded, giving rise to an upperbound on the lifetime of the network i.e., the time until at least one node in the network is able to communicate its sensed data to the sink. This paper aims at establishing tight analytical bounds on the sleeping probabilities of nodes and on the achievable lifetime of wireless sensor networks in a very generic setting. Bounds on the sleeping probability need to be satisfied for proper network functionality. Further, an energy efficient deployment scheme is suggested wherein the battery power depletion is fairly uniformly deployed throughout the network. This scheme makes use of the availability of low power auxiliary channel listening radio. With this scheme, we shown that an improvement in lifetime by a factor of O(√n overlog n) over uniform distribution of nodes is achievable, where n is the number of nodes in the network. We also show that the throughput capacity of the network is also improved by the same factor. We show also that the maximum lifetime of the network is bounded above by O(n3/2 over √log n). Further, the accuracy of our analysis is verified by the simulation results presented.

We propose an algebraic framework for designing trap-door one-way functions with applications in multivariate signature schemes. Multivariate schemes are attractive because of their efficiency. The proposed framework involves paraunitary matrices, a special subset of invertible polynomial-matrices. Using the algebraic framework, we propose the general template of paraunitary digital-signature scheme (PDSS). The general framework paves the way for a computational-security analysis of the PDSS. We also propose a practical instance of the PDSS that operates on the field GF (28). The message block and the secret key both consist of 16 symbols from GF (28). The signature is a block of length 26 symbols from GF (28). The complexity analysis of this instance reveals that it is, at least, as efficient as the hidden-field equations (HFE) scheme. In addition, our cryptanalysis shows that the proposed instance is secure

In this paper, we propose rateless codes that provide unequal error protection (UEP) property. We analyze the asymptotic properties of these codes under the iterative decoding algorithm. We further verify our work with simulations. The simulation results indicate that the proposed codes have strong UEP property. Moreover, the UEP property does not have a considerable drawback on the overall performance of the codes. We also discuss that the proposed codes can provide unequal recovery time (URT). This means that given a target bit error rate, different parts of information bits can be decoded after receiving different amounts of encoded bits. This implies that the information bits can be recovered in a progressive manner. This URT property may be used for sequential data recovery in video/audio streaming

In this paper, we study rate-compatible puncturing of finite-length Low-Density Parity-Check (LDPC) codes. First, we derive simple and yet good bounds on the expected performance of punctured codes (constructed by random puncturing) over Binary Erasure Channel (BEC) as a function of the performance of their parent LDPC code. We then present a novel rate-compatible puncturing scheme that is very easy to implement. Our scheme uses the idea that a more uniform distribution of punctured bits across the Tanner graph results in punctured codes with better performance. Although the puncturing scheme tailored to regular codes is presented, it is also directly applicable to irregular parent ensembles. By simulations, the proposed rate-compatible puncturing scheme is shown to be superior to the existing puncturing methods for both regular and irregular LDPC codes over BEC and Additive White Gaussian Noise (AWGN) Channel.

The task of providing security services for wireless sensor networks is not trivial due to the resource constraints of the sensor nodes. An adversary may launch a wide range of attacks including eavesdropping, message forgery, packet dropping, and noise injection. In this paper, we propose random coding security (RCS) that provides protection against all the aforementioned attacks. For this purpose, the proposed protocol makes extensive use of node collaboration and data redundancy. Moreover, using location information, we both localize adversarial activities to the area under attack and enhance routing the data toward the sink. The objectives of using the novel idea of sparse random coding in RCS are twofold. First, every node generates correlated data by calculating random linear combinations of the received packets. Hence, the availability of the data at the receiver is guaranteed with a high probability. The second advantage is the feasibility of implementing the RCS in the real case scenario in which the communication media between the sensors is usually modeled as the erasure channel. The existing protocols cannot be trivially modified to suit this realistic situation. In the overall, RCS provides many security services with computation and communication overheads comparable with other schemes

This correspondence studies the performance of the iterative decoding of low-density parity-check (LDPC) code ensembles that have linear typical minimum distance and stopping set size. We first obtain a lower bound on the achievable rates of these ensembles over memoryless binary-input output-symmetric channels. We improve this bound for the binary erasure channel. We also introduce a method to construct the codes meeting the lower bound for the binary erasure channel. Then, we give upper bounds on the rate of LDPC codes with linear minimum distance when their right degree distribution is fixed. We compare these bounds to the previously derived upper bounds on the rate when there is no restriction on the code ensemble.

Summary form only given. First, we consider a system of two statistically dependent signals, X/sub 1/ and X/sub 2/. The correlation between signals X/sub 1/ and X/sub 2/ is modeled as the input and output of a binary symmetric channel with crossover probability. We propose a non-uniform LDPC code that considers the fact that different bits are subject to different sources of noise. Simulation results show that our proposed method improves the source coding performance considerably. We further study an extension of our approach to three correlated nodes. For simplicity, we consider the case that assumes that the sources are pairwise correlated with the same correlation probability. We show that this assumption cannot be generalized to more than three sources. In this case, a fourth source is not be a random variable and it can be identified by the first three sources.

A generalization of rateless codes (LT and Raptor codes) to provide unequal error protection (UEP) property is proposed in this paper. The proposed codes (UEP-LT and UEP-Raptor codes) are analyzed for the best possible performance over the binary erasure channel (BEC) in finite-length cases. We derive upper and lower bounds on the bit error probabilities under the maximum-likelihood (ML) decoding. We further verify our work with simulations. Simulation results indicate that the bounds are tight for small error rates, and the proposed codes have strong UEP property.

Temporal and spatial correlation in the sensed data in wireless distributed sensor networks gives room for better energy efficiency in the network. Several data aggregation schemes have been suggested in the literature. However a clear-cut solution which quantitatively describes most energy-efficient routing scheme is still lacking. In this paper, we propose a novel, generalized clustering-based aggregation scheme, called "annular slicing-based clustering (ASC)" and show that by varying the cluster size and the distribution of clusters in the deployment area, one can approach the most energy-efficient aggregation scheme. Analytical expressions for the optimal cluster size and distribution have been arrived at, for a specific correlation model and a cost function based on the Euclidean distance traversed by the transmitted data. With the help of numerical simulation, it has been found that the proposed aggregation technique can achieve optimality over a wide range of correlation

This paper presents a new improved decoding algorithm for low-density parity-check (LDPC) codes over the binary erasure channel (BEC). The proposed algorithm combines the fact that a considerable fraction of unsatisfied check nodes are of degree two with the concept of guessing bits to perform simple graph-theoretic manipulations on the Tanner graph. The proposed decoding algorithm has a complexity similar to present improved decoding algorithms [H. Pishro-Nik et al., 2004]. Simulations of codes of very short lengths over BEC reveal the superiority of our algorithm over present improved decoding algorithms for a wide range of bit error rates.

We propose a novel framework to design a stream cipher based on wavelets over finite fields. Encryption and decryption are performed by inverse wavelets and their corresponding wavelet transforms. The system is iterative with each round consisting of two wavelet systems and a nonlinear feedback in the encryption and a nonlinear feedforward in the decryption. The input to the proposed wavelet stream cipher (WSC) is a sequence in the Galois field GF(2/sup 8/). The key consists of 16 symbols of GF(2/sup 8/) that specify the wavelet systems. The security of the system relies on the difficulty of solving nonlinear equations over finite fields which is known to be NP-complete. We have studied the vulnerability of our system to several attacks. Our studies show that although one round might be vulnerable, two rounds resists against all known attacks.

Key agreement in sensor networks is a dif- ficult problem because of resource constraints of the sensors. The classical approaches used in general networks are impractical in sensor networks. Hence, several key pre-distribution schemes are proposed. In this paper, we propose a hypercube multivariate scheme (HMS) that is a threshold-based scheme. In the HMS, a hypercube in the multidimensional space is designed and a number of multivariate polynomials are assigned to every point on the hypercube. The points on the hypercube are uniquely assigned to the sensors. Using this technique, a direct key is established between any two sensors at Hamming distance of one from each other. Other sensors are also able to establish indirect keys. Our analysis shows an improvement in the security of HMS compared to other similar schemes. We also propose a location-aware scheme that takes advantage of the distribution information to boost the security. In the proposed scheme, the target field is divided into hexagonal cells because of their efficient coverage compared to square cells. The sensors are randomly distributed in every cell. An HMS scheme is employed to pre-distribute keys in every cell. For the communication between adjacent cells, we propose a grid- based scheme in which the sensors of every cell are divided into groups. Shares of bivariate polynomials are stored in the sensors of every group. As a result, every two sensor in two adjacent cells are able to establish a direct key. Our security analysis shows improvements over similar schemes.

Hierarchical routing protocols are studied in terms of energy usage, packet latency, and security in the presence of node compromise attacks. We analyze clustering and tree-based structures of hierarchical algorithms to establish a method by which to design wireless sensor networks with particular energy, latency and security demands. Networks of homogeneous nodes and random deployment over a field are considered. We present analysis of the distribution of the distances between nodes of the sensor network and also provide simulations to validate and expound on these ideas.

In this paper, we propose a scheme for distributed source coding (DSC) that achieves any arbitrary rate on the Slepian-Wolf rate region using a single systematic LDPC code. This method is based on sending a fraction of the information bits along with a fraction of parity bits generated by the LDPC code. First, we study the problem of DSC of two correlated sources at the symmetric rate. We propose to use nonuniform LDPC codes for this application. Then, we generalize our approach to any arbitrary rate. The detailed construction of this scheme is investigated. We illustrate that the design procedure for the LDPC code simplifies to the design of rate-adaptive LDPC codes that need unequal error protection. It is shown that the performance of DSC at any arbitrary rate is almost the same as that of asymmetric rates. Because of the proposed decoding algorithm, each of the sources is decoded independently (only part of the information bits are being exchanged between the decoders). Therefore, this approach does not suffer from the problems of heavy damage or propagation of errors. This method can be easily applied to joint source-channel coding.

This correspondence introduces a framework to design and analyze low-density parity-check (LDPC) codes over nonuniform channels. We study LDPC codes for channels with nonuniform noise distributions, rate-adaptive coding, and unequal error protection. First, we propose a technique to design LDPC codes for volume holographic memory (VHM) systems for which the noise distribution is nonuniform. We show that the proposed coding scheme has an easy design procedure and results in efficient codes for holographic memories. An important property of the proposed technique is the design of the codes that have a low error floor and low variable node degrees, while maintaining performance close to the Shannon limit. We then show that punctured LDPC codes can be studied as a special case of our design methodology for nonuniform channels. Finally, we propose a method to generate LDPC codes that can provide unequal error protection in addition to having a good overall performance. Moreover, the highly protected bits can be decoded without requiring the entire word to be decoded.

The factorization of 2D FIR paraunitary filter banks is addressed in this paper. Our work is a generalization of the factorization algorithm for 1D paraunitary matrices. We present a complete factorization for multichannel, 2D, FIR paraunitary filter banks. The main idea is considering a bivariate FIR matrix as a univariate polynomial whose coefficients are matrices with univariate polynomial entries. With this representation, a generalized version of the factorization algorithm for the 1D case, developed in this paper, can be used. In this direction, a new definition for paraunitary matrices is proposed and a new degree-one building block is presented. The final result is a building block that generates all 2D FIR paraunitary matrices.

There are building blocks to generate all 1D two-channel filter banks over fields of characteristic two. In this paper, we extend the previous work and give building blocks for a first-level factorization of 2D filter banks over the ring of polynomials. Further factorization depends on the structure of the factors. Our approach is based on representing a bivariate (2V) PU matrix as a matrix polynomial in one variable whose coefficients are matrices over the ring of polynomials in the other variable. This representation allows using a factorization algorithm similar to the ID one. We also extend the definition of paraunitariness to the ring of polynomials.

This paper studies the performance of the iterative decoding of LDPC code ensembles that have linear typical minimum distance and stopping set size. We first obtain a lower bound on the achievable rates of these ensembles over MBIOS channels. Then, we give upper bounds on the rate of LDPC codes with linear minimum distance, given their right degree distribution over the BEC.

In this study, we propose a scheme to construct low-density parity-check (LDPC) codes that are suitable for unequal error protection (UEP). We derive density evolution formulas for the proposed ensemble over the binary erasure channel (BEC). For the finite length case, we compare our code with some other LDPC codes and the time-sharing method. Simulation results indicate the superiority of the proposed design methodology for unequal error protection.

In this paper we study some fundamental properties of punctured LDPC codes. We first prove that for any ensemble of LDPC codes, there exists a puncturing threshold p*. We then find lower bounds on the achievable rates of punctured codes over general MBIOS channels. These bounds are satisfied by using only one encoder and decoder for all rates. We then prove that for any rates R/sub 1/ and R/sub 2/ satisfying 0 < R/sub 1/ < R/sub 2/ < 1, there exists an ensemble of LDPC codes with the following property. The ensemble can be punctured from rate R/sub 1/ to R/sub 2/ resulting in asymptotically good codes for all rates R/sub 1/ /spl les/ R /spl les/ R/sub 2/. Specifically, this implies that rates arbitrarily close to one are achievable via puncturing. We also show that punctured LDPC codes are as good as ordinary LDPC codes. For binary erasure channel (BEC) and arbitrary positive numbers R/sub 1/ < R/sub 2/ < 1, we prove the existence of the sequences of punctured LDPC codes that are capacity achieving for all rates R/sub 1/ /spl les/ R /spl les/ R/sub 2/. Based on the above observations, we then propose a method to design good punctured LDPC codes over a broad range of rates. The method is very simple and does not suffer from the performance degradation at high rates. Finally, we show that punctured codes might be useful for proof of the existence of capacity-achieving LDPC codes over memoryless binary-input output-symmetric channels.

This paper introduces two-dimensional wavelet codes (TDWC). First, we study the encoder of half-rate TDWC. We show that these linear codes are lattice-cyclic. We prove that any two-dimensional lattice-cyclic code can also be generated by a two-dimensional wavelet transform. Second, we introduce a methodology to design TDWC over binary erasure channels. We show that the half-rate TDWC of dimensions N/sub 1/ /spl times/ N/sub 2/ can recover burst erasures of size up to N/sub 1/ /spl times/ N/sub 2//2 and N/sub 1//2 /spl times/ N/sub 2/, and N/sub 2//2 /spl times/ N/sub 2/. Finally, we present examples of TDWC that satisfy the Reiger bound with equality (capable of correcting any burst of size (N/sub 1/N/sub 2/)/2). Since these codes are lattice-cyclic, their erasure decoding can be simplified.

In this paper, we study connectivity properties of large-scale wireless sensor networks and discuss their effect on routing algorithms. In our model, n sensors are distributed randomly over a field based on a given distribution function. Two sensor nodes are connected with probability p/sub e/(n) if they are within the communication range of each other. The sensor nodes may also be unreliable. We find the necessary and sufficient conditions for the network to be k-connected, where k is a positive integer. We also find the distribution of isolated vertices. While connectivity (i.e, k = 1) insures that all nodes can communicate with each other, k-connectivity for k > 1 is required for multi-path routing. Additionally, it was found that the lengths of these multiple paths in a k-connected network are all close to the shortest path.

In this paper, we study two problems of providing reliable data transmission and developing aggregation techniques for correlated data in wireless sensor networks. A system with forward error correction (FEC) can provide an objective reliability while using less transmission power than a system without FEC. Because of the additional parity bits and encoding/decoding energy consumptions, we study the effect of FEC on energy efficiency. We propose to use LDPC codes for FEC. We show that wireless sensor networks using LDPC codes are almost 45% more energy efficient than those that use BCH codes, which were shown to be 15% more energy efficient than the best performing convolutional codes. Then we study the problem of providing aggregation for two and three correlated nodes in wireless sensor networks. We propose to use LDPC codes in wireless sensor networks for source and channel coding to obtain a two-fold energy savings. For two correlated nodes, we study both distributed source coding and joint source-channel coding. While distributed source coding using LDPC codes was studied before, joint source-channel coding using LDPC codes is introduced for the first time. The difference between our work in distributed source coding using LDPC codes and the previous work lies in the LDPC code design procedure. The simulation results show that our proposed design criteria improves the performance of the source coding. The convergence of the non-uniform LDPC code of our design technique is almost 60% closer to the Slepian-Wolf limit. For three correlated nodes, we study distributed source coding using LDPC codes. We simplified the problem of design procedure to randomly punctured LDPC codes. This is a new approach for designing LDPC codes and the simulation results for code of length 1000 shows that the convergence of the LDPC code is achieved at compression rate 0.3174 which is only 0.08 away from the Slepian-Wolf limit.

This paper investigates decoding of low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We study the iterative and maximum-likelihood (ML) decoding of LDPC codes on this channel. We derive bounds on the ML decoding of LDPC codes on the BEC. We then present an improved decoding algorithm. The proposed algorithm has almost the same complexity as the standard iterative decoding. However, it has better performance. Simulations show that we can decrease the error rate by several orders of magnitude using the proposed algorithm. We also provide some graph-theoretic properties of different decoding algorithms of LDPC codes over the BEC which we think are useful to better understand the LDPC decoding methods, in particular, for finite-length codes.

We propose a technique for designing low-density parity-check (LDPC) codes over non-uniform channels. In particular, we investigate LDPC codes for volume holographic memory (VHM) systems. We show that the proposed coding scheme for holographic memories has an easy design procedure and results in efficient codes. An important property of the proposed technique is that we can design simple codes whose performance is close to the Shannon limit, while they are very good in terms of the error floor effect. We also derive a capacity bound and the stability condition for the proposed codes over the binary erasure channel. We briefly discuss other applications like punctured codes, OFDM systems and multilevel coding.

This paper expands on the idea of wavelet coding. It undertakes construction of arbitrary rate error correcting codes using finite-field wavelets and filter banks. We show that a rate K / L code can be constructed by a combination of a K-band trivial analysis bank and an L-band synthesis bank. Several issues regarding these wavelet codes are investigated. Among other results, we develop a methodology to construct maximum-distance separable (MDS) codes using finite-field wavelets. In this method, a rate K / L code is constructed by a direct sum of the K rate 1/L subcodes which have been designed using the Bose-Chaudhuri-Hocquenghem (BCH) bound such that their direct sum generates an MDS code.

Recently we introduced a new framework to study error control coding using finite-field wavelets. In this paper we show that any double-circulant code over an arbitrary finite-field can be constructed by a simple two-band filter bank structure. Additionally for all double-circulant wavelet codes we introduce efficient tail-biting trellises on which we can perform soft-decision decoding. These tail-biting trellises are called π-minimal in which the product of all state space sizes is minimized.

Motivated by our wavelet framework for error-control coding, we proceed to develop an important family of wavelet transforms over finite fields. Paraunitary (PU) filter banks that are realizations of orthogonal wavelets by multirate filters are an important subclass of perfect reconstruction (PR) filter banks. A parameterization of PU filter banks that covers all possible PU systems is very desirable in error-control coding because it provides a framework for optimizing the free parameters to maximize coding performance. This paper undertakes the problem of classifying all PU matrices with entries from a polynomial ring, where the coefficients of the polynomials are taken from finite fields. It constructs Householder transformations that are used as elementary operations for the realization of all unitary matrices. Then, it introduces elementary PU building blocks and a factorization technique that is specialized to obtain a complete realization for all PU filter banks over fields of characteristic two. This is proved for the 2 /spl times/ 2 case, and conjectured for the M /spl times/ M case, where M /spl ges/ 3. Using these elementary building blocks, we can construct all PU filter banks over fields of characteristic two. These filter banks can be used to implement transforms which, in turn, provide a powerful new perspective on the problems of constructing and decoding arbitrary-rate error-correcting codes.

The primary goal of this paper is to give examples of the recently developed (finite-field) wavelet coding method by studying the encoder and decoder for some half-rate codes. We propose a decoding methodology based on estimating the polyphase components of the channel error pattern. To demonstrate the striking computational savings of the wavelet coding method over alternatives, we show that bounded-distance decoding of the (24,12,8) Golay code requires only weight computations (or at the worst case, it needs a cyclic lookup table of table size 12). The simplicity and computational savings that finite field wavelets offer for the encoding and decoding of wavelet block codes indicate their powerful capacities for error control coding applications.

Paraunitary filter banks are multi-rate filter realizations of orthogonal wavelet transforms. They are an important subclass of perfect reconstruction filter banks that provide a new framework for error control coding and decoding. This paper undertakes the problem of classifying all paraunitary matrices with entries from a polynomial ring, where the coefficients of the polynomials are taken from finite fields. It constructs Householder transformations that are used as elementary operations for the realization of all unitary matrices. Then, it introduces elementary paraunitary building blocks and a factorization technique that are specialized to obtain a complete realization for all paraunitary filter banks over fields of characteristic two (this is proved for the 2-band case, and a conjecture is applied for the proof of the M-band case, where M/spl ges/3). Using these elementary building blocks, we can construct all paraunitary filter banks over fields of characteristic two.

This paper presents an approach for the effective combination of interpolation with binarization of gray level text images to reconstruct a high resolution binary image from a lower resolution gray level one. We study two nonlinear interpolative techniques for text image interpolation. These nonlinear interpolation methods map quantized low dimensional 2 x 2 image blocks to higher dimensional 4 x 4 (possibly binary) blocks using a table lookup operation. The first method performs interpolation of text images using context-based, nonlinear, interpolative, vector quantization (NLIVQ). This system has a simple training procedure and has performance (for gray-level high resolution images) that is comparable to our more sophisticated generalized interpolative VQ (GIVQ) approach, which is the second method. In it, we jointly optimize the quantizer and interpolator to find matched codebooks for the low and high resolution images. Then, to obtain the binary codebook that incorporates binarization with interpolation, we introduce a binary constrained optimization method using GIVQ. In order to incorporate the nearest neighbor constraint on the quantizer while minimizing the distortion in the interpolated image, a deterministic-annealing-based optimization technique is applied. With a few interpolation examples, we demonstrate the superior performance of this method over the NLIVQ method (especially for binary outputs) and other standard techniques e.g., bilinear interpolation and pixel replication.

We develop the theory of the wavelet transform over Galois fields. To avoid the limitations inherent in the number theoretic Fourier transform over finite fields, our wavelet transform relies on a basis decomposition in the time domain rather than in the frequency domain. First, we characterize the infinite dimensional vector spaces for which an orthonormal basis expansion of any sequence in the space can be obtained using a symmetric bilinear form. Then, by employing a symmetric, non-degenerate, canonical bilinear form we derive the necessary and sufficient condition that basis functions over finite fields must satisfy in order to construct an orthogonal wavelet transform. Finally, we give a design methodology to generate the mother wavelet and scaling function over Galois fields by relating the wavelet transform to a two channel paraunitary filter bank.

We discuss the problem of reconstruction of a high resolution image from a lower resolution image by a jointly optimum interpolative vector quantization method. The interpolative vector quantizer maps quantized low dimensional 2/spl times/2 image blocks to higher dimensional 4/spl times/4 blocks by a table lookup method. As a special case of generalized vector quantization (GVQ), a jointly optimal quantizer and interpolator (GIVQ) is introduced to find the corresponding code books for the low and high resolution image. In order to incorporate the nearest neighborhood constraint on the quantizer and also to obtain the desired distortion in the interpolated image, a deterministic annealing based optimization technique has been applied. With a small interpolation example, we demonstrate the superior performance of this method over nonlinear interpolative vector quantization (NLIVQ), in which the interpolator is optimized for a given input quantizer.