BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Faramarz Fekri

Faramarz Fekri appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITMachine LearningMolecular NetworksNetworking and Internet Architectureeess.SPEmerging TechnologiesDistributed, Parallel, and Cluster ComputingMethodologynlin.AORobotics

Catalog footprint

What is connected

37works
11topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

37 published item(s)

preprint2026arXiv

Analysis of Semantic Communication for Logic-based Hypothesis Deduction

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 of the transmitter at 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.

0 citations0 reviewsNo code linkedOpen access
preprint2026arXiv

SCOUT: Cyclic Causal Discovery Under Soft Interventions with Unknown Targets

Learning causal relationships between variables from data is a fundamental research area with many applications across disciplines. Most existing causal discovery algorithms rely on the assumptions that (i) the underlying system is acyclic, (ii) the exogenous noise variables are Gaussian, and (iii) the intervention targets for the data-generating experiments are known. While these assumptions simplify the analysis, they are violated in real-life systems. Most existing methods that address these issues either assume the underlying model is linear or are constrained to operate in limited interventional settings. To that end, we propose SCOUT, a novel causal discovery framework for learning nonlinear cyclic causal relationships from soft interventional data with unknown targets. Our approach maximizes the data log-likelihood to recover the graph structure, using two normalizing-flow architectures: contractive residual flows and neural spline flows. Through experiments on synthetic and real-world data, we show that SCOUT outperforms state-of-the-art methods in both causal graph recovery and unknown target recovery across various interventional and noise settings.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

NODAGS-Flow: Nonlinear Cyclic Causal Structure Learning

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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

A Framework for Following Temporal Logic Instructions with Unknown Causal Dependencies

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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

A General Compressive Sensing Construct using Density Evolution

This paper proposes a general framework to design a sparse sensing matrix $\ensuremath{\mathbf{A}}\in \mathbb{R}^{m\times n}$, in a linear measurement system $\ensuremath{\mathbf{y}} = \ensuremath{\mathbf{Ax}}^{\natural} + \ensuremath{\mathbf{w}}$, where $\ensuremath{\mathbf{y}} \in \mathbb{R}^m$, $\ensuremath{\mathbf{x}}^{\natural}\in \RR^n$, and $\ensuremath{\mathbf{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 $\ensuremath{\mathbf{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 framework; ($ii$) Flexibility: the framework can easily adapt the design of $\bA$ to a signal $\ensuremath{\mathbf{x}}^{\natural}$ 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 > 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 $\bx^{\natural}$ is required.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Improving Actor-Critic Reinforcement Learning via Hamiltonian Monte Carlo Method

The actor-critic RL is widely used in various robotic control tasks. By viewing the actor-critic RL from the perspective of variational inference (VI), the policy network is trained to obtain the approximate posterior of actions given the optimality criteria. However, 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 {\it Hamiltonian Policy}. As such we propose to evolve actions from the base policy according to HMC, and our proposed method has many benefits. 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. Finally, in safe RL problems, we find that the proposed method can not only improve the achieved return, but also reduce safety constraint violations by discarding potentially unsafe actions. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Structure Learning in Graphical Models from Indirect Observations

This paper considers learning of the graphical structure of a $p$-dimensional random vector $X \in R^p$ using both parametric and non-parametric methods. Unlike the previous works which observe $x$ directly, we consider the indirect observation scenario in which samples $y$ are collected via a sensing matrix $A \in R^{d\times p}$, and corrupted with some additive noise $w$, i.e, $Y = AX + W$. For the parametric method, we assume $X$ to be Gaussian, i.e., $x\in R^p\sim N(μ, Σ)$ and $Σ\in R^{p\times p}$. For the first time, we show that the correct graphical structure can be correctly recovered under the indefinite sensing system ($d < p$) using insufficient samples ($n < p$). In particular, we show that for the exact recovery, we require dimension $d = Ω(p^{0.8})$ and sample number $n = Ω(p^{0.8}\log^3 p)$. For the nonparametric method, we assume a nonparanormal distribution for $X$ rather than Gaussian. Under mild conditions, we show that our graph-structure estimator can obtain the correct structure. We derive the minimum sample number $n$ and dimension $d$ as $n\gtrsim (deg)^4 \log^4 n$ and $d \gtrsim p + (deg\cdot\log(d-p))^{β/4}$, respectively, where deg is the maximum Markov blanket in the graphical model and $β> 0$ is some fixed positive constant. Additionally, we obtain a non-asymptotic uniform bound on the estimation error of the CDF of $X$ from indirect observations with inexact knowledge of the noise distribution. To the best of our knowledge, this bound is derived for the first time and may serve as an independent interest. Numerical experiments on both real-world and synthetic data are provided confirm the theoretical results.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Incorporating Relational Background Knowledge into Reinforcement Learning via Differentiable Inductive Logic Programming

Relational Reinforcement Learning (RRL) can offers various desirable features. Most importantly, it allows for incorporating expert knowledge into the learning, and hence leading to much faster learning and better generalization compared to the standard deep reinforcement learning. However, most of the existing RRL approaches are either incapable of incorporating expert background knowledge (e.g., in the form of explicit predicate language) or are not able to learn directly from non-relational data such as image. In this paper, we propose a novel deep RRL based on a differentiable Inductive Logic Programming (ILP) that can effectively learn relational information from image and present the state of the environment as first order logic predicates. Additionally, it can take the expert background knowledge and incorporate it into the learning problem using appropriate predicates. The differentiable ILP allows an end to end optimization of the entire framework for learning the policy in RRL. We show the efficacy of this novel RRL framework using environments such as BoxWorld, GridWorld as well as relational reasoning for the Sort-of-CLEVR dataset.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Restructuring, Pruning, and Adjustment of Deep Models for Parallel Distributed Inference

Using multiple nodes and parallel computing algorithms has become a principal tool to improve training and execution times of deep neural networks as well as effective collective intelligence in sensor networks. In this paper, we consider the parallel implementation of an already-trained deep model on multiple processing nodes (a.k.a. workers) where the deep model is divided into several parallel sub-models, each of which is executed 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 and partition them (without changing the general topology of the neural network), such that the interdependency among sub-models is minimized under the computations and communications constraints of the workers. 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 $\ell_0$ 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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On ISI-free Modulations for Diffusion based Molecular Communication

A diffusion molecular channel is a channel with memory, as molecules released into the medium hit the receptors after a random delay. Coding over the diffusion channel is performed by choosing the type, intensity, or the released time of molecules diffused in the environment over time. To avoid intersymbol interference (ISI), molecules of the same type should be released at time instances that are sufficiently far apart. This ensures that molecules of a previous transmission are faded in the environment, before molecules of the same type are reused for signaling. In this paper, we consider ISI-free time-slotted modulation schemes. The maximum reliable transmission rate for these modulations is given by the constrained coding capacity of the graph that represents the permissible transmission sequences. However, achieving the constrained coding capacity requires long blocklengths and delays at the decoder, making it impractical for simple nanomachines. The main contribution of this paper is to consider modulations with small delay (short blocklength) and show that they get very close to constrained coding capacity.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Capacity Achieving Probability Measures for Molecular Receivers

In this paper, diffusion-based molecular commu- nication with ligand receptor receivers is studied. Information messages are assumed to be encoded via variations of the con- centration of molecules. The randomness in the ligand reception process induces uncertainty in the communication; limiting the rate of information decoding. We model the ligand receptor receiver by a set of finite-state Markov channels and study the general capacity of such a receiver. Furthermore, the i.i.d. capacity of the receiver is characterized as a lower bound for the general capacity. It is also proved that a finite support probability measure can achieve the i.i.d. capacity of the receiver. Moreover, a bound on the number of points in the support of the probability measure is obtained.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Capacity of Level and Type Modulation in Molecular Communication with Ligand Receptors

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 using 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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Capacity of Point-to-Point and Multiple-Access Molecular Communications with Ligand-Receptors

In this paper, we consider the bacterial point-to-point and multiple-access molecular communications with ligand-receptors. For the point-to-point communication, we investigate common signaling methods, namely the Level Scenario (LS), which uses one type of a molecule with different concentration levels, and the Type Scenario (TS), which employs multiple types of molecules with a single concentration level. We investigate the trade-offs between the two scenarios from the capacity point of view. We derive an upper bound on the capacity using a Binomial Channel (BIC) model and the symmetrized Kullback-Leibler (KL) divergence. A lower bound is also derived when the environment noise is negligible. For the TS, we also consider the effect of blocking of a receptor by a different molecule type. Then, we consider multiple-access communications, for which we investigate three scenarios based on molecule and receptor types, i.e., same types of molecules with Different Labeling and Same types of Receptors (DLSR), Different types of Molecules and Receptors (DMDR), and Same types of Molecules and Receptors (SMSR). We investigate the trade-offs among the three scenarios from the total capacity point of view. We derive some inner bounds on the capacity region of these scenarios when the environment noise is negligible.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Design and Analysis of Wireless Communication Systems Using Diffusion-Based Molecular Communication Among Bacteria

The design of biologically-inspired wireless communication systems using bacteria as the basic element of the system is initially motivated by a phenomenon called \emph{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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Packet-Level Network Compression: Realization and Scaling of the Network-Wide Benefits

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 Erdos-Renyi 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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Relaying in Diffusion-Based Molecular Communication

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Universal Compression of a Mixture of Parametric Sources with Side Information

This paper investigates the benefits of the side information on the universal compression of sequences from a mixture of $K$ parametric sources. The output sequence of the mixture source is chosen from the source $i \in \{1,\ldots ,K\}$ with a $d_i$-dimensional parameter vector at random according to probability vector $\mathbf{w} = (w_1,\ldots,w_K)$. The average minimax redundancy of the universal compression of a new random sequence of length $n$ is derived when the encoder and the decoder have a common side information of $T$ sequences generated independently by the mixture source. Necessary and sufficient conditions on the distribution $\mathbf{w}$ and the mixture parameter dimensions $\mathbf{d} = (d_1,\ldots,d_K)$ are determined such that the side information provided by the previous sequences results in a reduction in the first-order term of the average codeword length compared with the universal compression without side information. Further, it is proved that the optimal compression with side information corresponds to the clustering of the side information sequences from the mixture source. Then, a clustering technique is presented to better utilize the side information by classifying the data sequences from a mixture source. Finally, the performance of the clustering on the universal compression with side information is validated using computer simulations on real network data traces.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

BPRS: Belief Propagation Based Iterative Recommender System

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Capacity of Diffusion-based Molecular Communication with Ligand Receptors

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Collective Sensing-Capacity of Bacteria Populations

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). 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 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 is used.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Data Gathering in Networks of Bacteria Colonies: Collective Sensing and Relaying Using Molecular Communication

The prospect of new biological and industrial applications that require communication in micro-scale, encourages research on the design of bio-compatible communication networks using networking primitives already available in nature. One of the most promising candidates for constructing such networks is to adapt and engineer specific types of bacteria that are capable of sensing, actuation, and above all, communication with each other. In this paper, we describe a new architecture for networks of bacteria to form a data collecting network, as in traditional sensor networks. The key to this architecture is the fact that the node in the network itself is a bacterial colony; as an individual bacterium (biological agent) is a tiny unreliable element with limited capabilities. We describe such a network under two different scenarios. We study the data gathering (sensing and multihop communication) scenario as in sensor networks followed by the consensus problem in a multi-node network. We will explain as to how the bacteria in the colony collectively orchestrate their actions as a node to perform sensing and relaying tasks that would not be possible (at least reliably) by an individual bacterium. Each single bacterium in the colony forms a belief by sensing external parameter (e.g., a molecular signal from another node) from the medium and shares its belief with other bacteria in the colony. Then, after some interactions, all the bacteria in the colony form a common belief and act as a single node. We will model the reception process of each individual bacteria and will study its impact on the overall functionality of a node. We will present results on the reliability of the multihop communication for data gathering scenario as well as the speed of convergence in the consensus scenario.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Memory-Assisted Universal Compression of Network Flows

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Memory-Assisted Universal Source Coding

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$. We assume that server $S$ wishes to send the sequence $x^n$ to the client $C$ who has never had any prior communication with the server, and hence, is not capable of memorization of the source context. However, $R$ has previously communicated with $S$ to forward previous sequences from $S$ to the clients other than $C$, and thus, $R$ has memorized a context $y^m$ shared with $S$. Note that if the relay node was absent the source could possibly apply universal compression to $x^n$ and transmit to $C$ whereas the presence of memorized context at $R$ can possibly reduce the communication overhead in $S$-$R$ link. In this paper, we investigate the fundamental gain of the context memorization in the memory-assisted universal compression of the sequence $x^n$ over conventional universal source coding by providing a lower bound on the gain of memory-assisted source coding.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Network Compression: Memory-Assisted Universal Coding of Sources with Correlated Parameters

In this paper, we propose {\em distributed network compression via memory}. We consider two spatially separated sources with correlated unknown source parameters. 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. In this setup, the correlation does not arise from symbol-by-symbol dependency of two outputs from the two sources (as in Slepian-Wolf setup). Instead, the two sequences are correlated because they are originated from the two sources with \emph{unknown} correlated parameters. 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 $p_e(n)$ that vanishes as sequence length $n$ grows to infinity. We obtain bounds on the redundancy of almost lossless codes when the decoder has access to a random memory of length $m$ as a function of the sequence length $n$ and the permissible error probability $p_e(n)$. Our results demonstrate that distributed network compression via memory has the potential to significantly improve over conventional end-to-end compression when sufficiently large memory from previous communications is available to the decoder.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On Lossless Universal Compression of Distributed Identical Sources

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 $p_e(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 $p_e$ when 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 \to \infty$).

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Results on the Fundamental Gain of Memory-Assisted Universal Source Coding

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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Capacity of Discrete Molecular Diffusion Channels

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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Consensus Problem under Diffusion-based Molecular Communication

We investigate the consensus problem in a network where nodes communicate via diffusion-based molecular communication (DbMC). In DbMC, messages are conveyed via the variation in the concentration of molecules in the medium. Every node acquires sensory information about the environment. Communication enables the nodes to reach the best estimate for that measurement, e.g., the average of the initial estimates by all nodes. We consider an iterative method for communication among nodes that enables information spreading and averaging in the network. We show that the consensus can be attained after a finite number of iterations and variance of estimates of nodes can be made arbitrarily small via communication.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Exact Modeling of the Performance of Random Linear Network Coding in Finite-buffer Networks

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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the Network-Wide Gain of Memory-Assisted Source Coding

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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Results on the Redundancy of Universal Compression for Finite-Length Sequences

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-ε)\frac{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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Study of Throughput and Delay in Finite-Buffer Line Networks

In this work, we study the effects of finite buffers on the throughput and delay of line networks with erasure links. We identify the calculation of performance parameters such as throughput and delay to be equivalent to determining the stationary distribution of an irreducible Markov chain. We note that the number of states in the Markov chain grows exponentially in the size of the buffers with the exponent scaling linearly with the number of hops in a line network. We then propose a simplified iterative scheme to approximately identify the steady-state distribution of the chain by decoupling the chain to smaller chains. The approximate solution is then used to understand the effect of buffer sizes on throughput and distribution of packet delay. Further, we classify nodes based on congestion that yields an intelligent scheme for memory allocation using the proposed framework. Finally, by simulations we confirm that our framework yields an accurate prediction of the variation of the throughput and delay distribution.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Infocast: A New Paradigm for Collaborative Content Distribution from Roadside Units to Vehicular Networks Using Rateless Codes

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 \emph{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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Memory Allocation in Distributed Storage Networks

We consider the problem of distributing a file in a network of storage nodes whose storage budget is limited but at least equals to 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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Study of Throughput and Latency in Finite-buffer Coded Networks

Exact queueing analysis of erasure networks with network coding in a finite buffer regime is an extremely hard problem due to the large number of states in the network. In such networks, packets are lost due to either link erasures or due to blocking due to full buffers. In this paper, a block-by-block random linear network coding scheme with feedback on the links is selected for reliability and more importantly guaranteed decoding of each block. 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. The proposed framework yields an accurate estimate of the distribution of buffer occupancies at the intermediate nodes using which we obtain analytical expressions for network throughput and delay distribution of a block of packets.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Throughput and Latency in Finite-Buffer Line Networks

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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Throughput and Latency of Acyclic Erasure Networks with Feedback in a Finite Buffer Regime

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.

0 citations0 reviewsNo code linkedOpen access