Radio map estimation (RME) aims at providing a radio frequency metric, such as the received power strength, at every location of a geographical region of interest by relying on measurements acquired at multiple positions. Although a large number of estimators have been proposed so far, their performance has been analyzed mostly on simulated data. The theoretical aspects of the RME problem as well as performance bounds remain an open problem. This paper takes a step towards filling this gap by means of a theoretical analysis of the RME problem in a free-space propagation environment. First, the complexity of the estimation problem is quantified by means of upper bounds on the spatial variability of radio maps. Second, error bounds are derived for zeroth-order and first-order interpolation estimators. The proximity coefficient, which depends proportionally on the transmitted power and inversely proportionally on the cube of the distance from the transmitters to the mapped region, is proposed to quantify the complexity of the RME problem. One of the main findings is that the error of the considered estimators is roughly proportional to this proximity coefficient. Simple numerical experiments verify the tightness of the obtained bounds.

Radio maps provide radio frequency metrics, such as the received signal strength, at every location of a geographic area. These maps, which are estimated using a set of measurements collected at multiple positions, find a wide range of applications in wireless communications, including the prediction of coverage holes, network planning, resource allocation, and path planning for mobile robots. Although a vast number of estimators have been proposed, the theoretical understanding of the radio map estimation (RME) problem has not been addressed. The present work aims at filling this gap along two directions. First, the complexity of the set of radio map functions is quantified by means of lower and upper bounds on their spatial variability, which offers valuable insight into the required spatial distribution of measurements and the estimators that can be used. Second, the reconstruction error for power maps in free space is upper bounded for three conventional spatial interpolators. The proximity coefficient, which is a decreasing function of the distance from the transmitters to the mapped region, is proposed to quantify the complexity of the RME problem. Numerical experiments assess the tightness of the obtained bounds and the validity of the main takeaways in complex environments.

This paper studies bandit algorithms under data poisoning attacks in a bounded reward setting. We consider a strong attacker model in which the attacker can observe both the selected actions and their corresponding rewards, and can contaminate the rewards with additive noise. We show that any bandit algorithm with regret O(log T) can be forced to suffer a regret O(T) with an expected amount of contamination O(log T). This amount of contamination is also necessary, as we prove that there exists an O(log T) regret bandit algorithm, specifically the classical UCB, that requires Omega(log T) amount of contamination to suffer regret Omega(T). To combat such poisoning attacks, our second main contribution is to propose verification based mechanisms, which use limited verification to access a limited number of uncontaminated rewards. In particular, for the case of unlimited verifications, we show that with O(log T) expected number of verifications, a simple modified version of the Explore-then-Commit type bandit algorithm can restore the order optimal O(log T) regret irrespective of the amount of contamination used by the attacker. We also provide a UCB-like verification scheme, called Secure-UCB, that also enjoys full recovery from any attacks, also with O(log T) expected number of verifications. To derive a matching lower bound on the number of verifications, we also prove that for any order-optimal bandit algorithm, this number of verifications O(log T) is necessary to recover the order-optimal regret. On the other hand, when the number of verifications is bounded above by a budget B, we propose a novel algorithm, Secure-BARBAR, which provably achieves O(min(C,T/sqrt(B))) regret with high probability against weak attackers (i.e., attackers who have to place the contamination before seeing the actual pulls of the bandit algorithm), where C is the total amount of contamination by the attacker, which breaks the known Omega(C) lower bound of the non-verified setting if C is large.

To understand the security threats to reinforcement learning (RL) algorithms, this paper studies poisoning attacks to manipulate any order-optimal learning algorithm towards a targeted policy in episodic RL and examines the potential damage of two natural types of poisoning attacks, i.e., the manipulation of reward or action. We discover that the effect of attacks crucially depends on whether the rewards are bounded or unbounded. In bounded reward settings, we show that only reward manipulation or only action manipulation cannot guarantee a successful attack. However, by combining reward and action manipulation, the adversary can manipulate any order-optimal learning algorithm to follow any targeted policy with \Theta(\sqrt{T}) total attack cost, which is order-optimal, without any knowledge of the underlying MDP. In contrast, in unbounded reward settings, we show that reward manipulation attacks are sufficient for an adversary to successfully manipulate any order-optimal learning algorithm to follow any targeted policy using \tilde{O}(\sqrt{T}) amount of contamination. Our results reveal useful insights about what can or cannot be achieved by poisoning attacks, and are set to spur more work on the design of robust RL algorithms.

We provide a general and easy to implement method for reducing the number of parameters of Convolutional Neural Networks (CNNs) during the training and inference phases. We introduce a simple trainable auxiliary neural network which can generate approximate versions of “slices” of the sets of convolutional filters of any CNN architecture from a low dimensional “code” space. These slices are then concatenated to form the sets of filters in the CNN architecture. The auxiliary neural network, which we call “Convolutional Slice Generator” (CSG), is unique to the network and provides the association among its convolutional layers. We apply our method to various CNN architectures including ResNet, DenseNet, MobileNet and ShuffleNet. Experiments on CIFAR-10 and ImageNet-1000, without any hyper-parameter tuning, show that our approach reduces the network parameters by approximately $2\times$ while the reduction in accuracy is confined to within one percent and sometimes the accuracy even improves after compression. Interestingly, through our experiments, we show that even when the CSG takes random binary values for its weights that are not learned, still acceptable performances are achieved. To show that our approach generalizes to other tasks, we apply it to an image segmentation architecture, Deeplab V3, on the Pascal VOC 2012 dataset. Results show that without any parameter tuning, there is $\approx 2.3\times$ parameter reduction and the mean Intersection over Union (mIoU) drops by $\approx 3%$. Finally, we provide comparisons with several related methods showing the superiority of our method in terms of accuracy.

Recently, the$\delta$-mutual information between uncertain variables has been introduced as a generalization of Nair's non-stochastic mutual information functional [1], [2]. Within this framework, we introduce four different notions of capacity and present corresponding coding theorems. Our definitions include an analogue of Shannon's capacity in a non-stochastic setting, and a generalization of the zero-error capacity. The associated coding theorems hold for stationary, memoryless, non-stochastic uncertain channels. These results establish the relationship between the$\delta$-mutual information and our operational definitions, providing a step towards the development of a complete non-stochastic information theory.

We study “active” decision making over sensor networks where the sensors' sequential probing actions are actively chosen by continuously learning from past observations. We consider two network settings: with and without central coordination. In the first case, the network nodes interact with each other through a central entity, which plays the role of a fusion center. In the second case, the network nodes interact in a fully distributed fashion. In both of these scenarios, we propose sequential and adaptive hypothesis tests extending the classic Chernoff test. We compare the performance of the proposed tests to the optimal sequential test. In the presence of a fusion center, our test achieves the same asymptotic optimality of the Chernoff test, minimizing the risk, expressed by the expected cost required to reach a decision plus the expected cost of making a wrong decision, when the observation cost per unit time tends to zero. The test is also asymptotically optimal in the higher moments of the time required to reach a decision. Additionally, the test is parsimonious in terms of communications, and the expected number of channel uses per network node tends to a small constant. In the distributed setup, our test achieves the same asymptotic optimality of Chernoff's test, up to a multiplicative constant in terms of both risk and the higher moments of the decision time. Additionally, the test is parsimonious in terms of communications in comparison to state-of-the-art schemes proposed in the literature. The analysis of these tests is also extended to account for message quantization and communication over channels with random erasures.

Immunoglobulin genes are formed through V(D)J recombination, which joins the variable (V), diversity (D), and joining (J) germline genes. Since variations in germline genes have been linked to various diseases, personalized immunogenomics focuses on finding alleles of germline genes across various patients. Although reconstruction of V and J genes is a well-studied problem, the more challenging task of reconstructing D genes remained open until the IgScout algorithm was developed in 2019. In this work, we address limitations of IgScout by developing a probabilistic MINING-D algorithm for D gene reconstruction, apply it to hundreds of immunosequencing datasets from multiple species, and validate the newly inferred D genes by analyzing diverse whole genome sequencing datasets and haplotyping heterozygous V genes.

We study online learning when partial feedback information is provided following every action of the learning process, and the learner incurs switching costs for changing his actions. In this setting, the feedback information system can be represented by a graph, and previous works studied the expected regret of the learner in the case of a clique (Expert setup), or disconnected single loops (Multi-Armed Bandits (MAB)). This work provides a lower bound on the expected regret in the Partial Information (PI) setting, namely for general feedback graphs –excluding the clique. Additionally, it shows that all algorithms that are optimal without switching costs are necessarily sub-optimal in the presence of switching costs, which motivates the need to design new algorithms. We propose two new algorithms: Threshold Based EXP3 and EXP3.SC. For the two special cases of symmetric PI setting and MAB, the expected regret of both of these algorithms is order optimal in the duration of the learning process. Additionally, Threshold Based EXP3 is order optimal in the switching cost, whereas EXP3.SC is not. Finally, empirical evaluations show that Threshold Based EXP3 outperforms the previously proposed order-optimal algorithms EXP3 SET in the presence of switching costs, and Batch EXP3 in the MAB setting with switching costs.

This work investigates the adversarial Bandits with Knapsack (BwK) learning problem, where a player repeatedly chooses to perform an action, pays the corresponding cost of the action, and receives a reward associated with the action. The player is constrained by the maximum budget that can be spent to perform the actions, and the rewards and the costs of these actions are assigned by an adversary. This setting is studied in terms of expected regret, defined as the difference between the total expected rewards per unit cost corresponding the best fixed action and the total expected rewards per unit cost of the learning algorithm. We propose a novel algorithm EXP3.BwK and show that the expected regret of the algorithm is order optimal in the budget. We then propose another algorithm EXP3++.BwK, which is order optimal in the adversarial BwK setting, and incurs an almost optimal expected regret in the stochastic BwK setting where the rewards and the costs are drawn from unknown underlying distributions. These results are then extended to a more general online learning setting, by designing another algorithm EXP3++.LwK and providing its performance guarantees. Finally, we investigate the scenario where the costs of the actions are large and comparable to the budget. We show that for the adversarial setting, the achievable regret bounds scale at least linearly with the maximum cost for any learning algorithm, and are significantly worse in comparison to the case of having costs bounded by a constant, which is a common assumption in the BwK literature.

The δ-mutual information between uncertain variables is introduced as a generalization of Nair's non-stochastic information functional. Several properties of this new quantity are illustrated, and used to prove a channel coding theorem in a non-stochastic setting. Namely, it is shown that the largest δ mutual information between a metric space and its ε-packing equals the (ε,δ)-capacity of the space. This notion of capacity generalizes the Kolmogorov ε-capacity to packing sets of overlap at most δ, and is a variation of a previous definition proposed by one of the authors. These results provide a framework for developing a non-stochastic information theory motivated by potential applications in control and learning theories. Compared to previous non-stochastic approaches, the theory admits the possibility of decoding errors as in Shannon's probabilistic setting, while retaining its worst-case non-stochastic character.

We propose a decentralized, sequential and adaptive hypothesis test in sensor networks, which extends Chernoff's test to a decentralized setting. We show that the proposed test achieves the same asymptotic optimality of the original one, minimizing the expected cost required to reach a decision plus the expected cost of making a wrong decision, when the observation cost per unit time tends to zero. We also show that the proposed test is parsimonious in terms of communications. Namely, in the regime of vanishing observation cost per unit time, the expected number of channel uses required by each sensor to complete the test converges to four.

We consider an agent-based distributed algorithm with exponentially distributed waiting times in which agents with binary states interact locally over a geometric graph, and based on this interaction and on the value of a common intolerance threshold τ, decide whether to change their states. This model is equivalent to an Asynchronous Cellular Automaton (ACA) with extended Moore neighborhoods, a zero-temperature Ising model with Glauber dynamics, or a Schelling model of self-organized segregation in an open system, and has applications in the analysis of social and biological networks, and spin glasses systems.

A solution for the completely blind sensing problem of determining the minimum number of measurements sufficient to recover multi-band signals without any spectral information beside an upper bound on the measure of the whole support set in the frequency domain is presented. The number of measurements sufficient for reconstruction is provided, as well as a tight converse bound. Results show that a factor of two in the measurement rate is the price pay for blindness, compared to reconstruction with full spectral knowledge. The minimum number of measurements is also related to the fractal (Minkowski-Bouligand) dimension of a discrete approximating set, defined in terms of the Kolmogorov e-entropy. A comparison with analogous results in compressed sensing is illustrated, where the relevant dimensionality notion in a stochastic setting is the information (Renyi) dimension, defined in terms of the Shannon entropy.

We consider an agent-based model in which two types of agents interact locally over a graph and have a common intolerance threshold τ for changing their types with exponentially distributed waiting times. The model is equivalent to an unperturbed Schelling model of self-organized segregation, an Asynchronous Cellular Automata (ACA) with extended Moore neighborhoods, or a zero-temperature Ising model with Glauber dynamics, and has applications in the analysis of social and biological networks, and spin glasses systems. Some rigorous results were recently obtained in the theoretical computer science literature, and this work provides several extensions. We enlarge the intolerance interval leading to the formation of large segregated regions of agents of a single type from the known size ε>0 to size ~0.134. Namely, we show that for 0.433 < τ < 1/2 (and by symmetry 1/2<τ<0.567), the expected size of the largest segregated region containing an arbitrary agent is exponential in the size of the neighborhood. We further extend the interval leading to large segregated regions to size ~0.312 considering "almost segregated" regions, namely regions where the ratio of the number of agents of one type and the number of agents of the other type vanishes quickly as the size of the neighborhood grows. In this case, we show that for 0.344 < τ ≤ 0.433 (and by symmetry for 0.567 ≤ τ<0.656) the expected size of the largest almost segregated region containing an arbitrary agent is exponential in the size of the neighborhood. This behavior is reminiscent of supercritical percolation, where small clusters of empty sites can be observed within any sufficiently large region of the occupied percolation cluster. The exponential bounds that we provide also imply that complete segregation, where agents of a single type cover the whole grid, does not occur with high probability for p=1/2 and the range of tolerance considered.

The deterministic notions of capacity and entropy are studied in the context of communication and storage of information using square-integrable and bandlimited signals subject to perturbation. The (E, δ)-capacity that extends the Kolmogorov E-capacity to packing sets of overlap at most δ is introduced and compared with the Shannon capacity. The functional form of the results indicates that in both Kolmogorov and Shannon's settings, capacity and entropy grow linearly with the number of degrees of freedom, but only logarithmically with the signal to noise ratio. This basic insight transcends the details of the stochastic or deterministic description of the information theoretic model. For δ = 0, the analysis leads to a tight asymptotic expression of the Kolmogorov E-entropy of bandlimited signals. A deterministic notion of error exponent is introduced. Applications of the theory are briefly discussed.

In the paper above[1], published in the March 2017 issue of the IEEE Transactions on Information Theory, the following changes are noted.•In the Abstract, page 1349, left column, line 3, “using square-integrable and bandlimited signals” should be replaced by “using square-integrable, bandlimited signals.”

We provide a bound on the ε-entropy of square-integrable bandlimited waveforms in terms of their energy and of the spatial extension of the domain where they are observed. This result is closely related to the largest amount of information that can be contained in a physical system of a given size, known as the Bekenstein universal entropy bound.

The deterministic notion of (ε, δ) capacity is introduced and studied in the context of communication with squareintegrable, bandlimited signals subject to additive ε-noise. This extends the Kolmogorov 2-capacity to packing sets of overlap at most δ. For δ = 0, a previous lower bound on the 2ε-capacity is recovered, and an improved version of the upper bound is derived. For δ > 0 new bounds are obtained, and a notion of deterministic error exponent is introduced, that depends only on the transmission rate, the bandwidth, and the signal to noise ratio. The functional form of upper and lower bounds indicates that in both Kolmogorov and Shannon's settings capacity grows linearly with the number of degrees of freedom, but only logarithmically with the signal to noise ratio. This basic information-theoretic insight transcends the details of the stochastic or deterministic description of the communication model.

Several new expressions for the anytime capacity of Sahai and Mitter are presented for a time-varying rate-limited channel with noiseless output feedback. These follow from a parametric characterization obtained in the case of Markov channels, and include an explicit formula for the r-bit Markov erasure channel, as well as formulas for memoryless rate processes including Binomial, Poisson, and Geometric distributions. Beside the memoryless erasure channel and the additive white Gaussian noise channel with input power constraint, these are the only cases where explicit anytime capacity formulas are obtained. At the basis of these results is the study of the threshold function for mth moment stabilization of a scalar linear system controlled over a Markov time-varying digital feedback channel that depends on m and on the channel's parameters. This threshold is shown to be a continuous and strictly decreasing function of m and to have as extreme values the Shannon capacity and the zero-error capacity as m tends to zero and infinity, respectively. Its operational interpretation is that of achievable communication rate, subject to a reliability constraint.

A variation of Landau's eigenvalue theorem describing the phase transition of the eigenvalues of a time-frequency limiting, self adjoint operator is presented. The total number of degrees of freedom of square-integrable, multidimensional, bandlimited functions is defined in terms of Kolmogorov's n -width and computed in some limiting regimes, where the original theorem cannot be directly applied. Results are used to characterize up to order the total amount of information that can be transported in time and space by multiple-scattered electromagnetic waves, rigorously addressing a question originally posed in the early works of Toraldo di Francia and Gabor. Applications in the context of wireless communication and electromagnetic sensing are discussed.

A variation of Landau's eigenvalue theorem describing the phase transition behavior of the eigenvalues of a time-frequency limiting, self adjoint operator is presented, and its applications are discussed in the context of communication with waves.

Does semantic expression spread online from person to person? And if so, what kinds of expression are most likely to spread? To address these questions, we developed a nonexperimental, noninvasive method to detect and quantify contagion of semantic expression in massive online social networks, which we review and discuss here. Using only observational data, the method avoids performing emotional experiments on users of online social networks, a research practice that recently became an object of criticism and concern. Our model combines geographic aggregation and instrumental variables regression to measure the effect of an exogenous variable on an individual's expression and the influence of this change on the expression of others to whom that individual is socially connected. In a previous work, we applied our method to the emotional content of posts generated by a large sample of users over a period of three years. Those results suggest that each post expressing a positive or negative emotion can cause friends to generate one to two additional posts expressing the same emotion, and it also inhibits their use of the opposite emotion. Here, we generalize our method so it can be applied to contexts different than emotional expression and to different forms of content generated by the users of online platforms. The method allows us to determine the usage of words in the same semantic category spread, and to estimate a signed relationship between different semantic categories, showing that an increase in the usage of one category alters the usage of another category in one's social contacts. Finally, it also allows us to estimate the total cumulative effect that a person has on all of her social contacts.

We consider the scenario in which a set of sources generates messages in a network and a receiver node demands an arbitrary linear function of these messages. We formulate an algebraic test to determine whether an arbitrary network can compute linear functions using linear codes. We identify a class of linear functions that can be computed using linear codes in every network that satisfies a natural cut-based condition. Conversely, for another class of linear functions, we show that the cut-based condition does not guarantee the existence of a linear coding solution. For linear functions over the binary field, the two classes are complements of each other.

The performance of cooperation strategies for broadcast services sharing a common wireless channel is studied in the framework of coalitional game theory. Two strategies are examined. The first represents an open sharing model where each service provider is allowed to transmit at any time but simultaneous transmissions result in interference. It is shown analytically that in the absence of coordination cost, the grand coalition formed by all providers cooperating to avoid simultaneous transmissions is both sum-rate optimal and stable. The second strategy represents an orthogonal access method where service providers are granted exclusive access to a subset of the available channels, each having a guaranteed successful transmission opportunity. In the absence of coordination cost, the grand coalition where all providers cooperate by sharing their guaranteed right to access the channel is sum-rate optimal but unstable, in the sense that some group of providers may have an incentive to deviate from the grand coalition. In the presence of coordination cost, a different scenario arises. In both models large coalitions do not form, and simulation results suggest that the open access model for large networks can lead to a regime where performance is considerably limited by interference.

Consider a network where an unidentified source starts a rumor. The rumor spreads along the edges of the network to other nodes in the network. After a sufficiently long amount of time, we observe a subset of the nodes that have heard the rumor, and using this information wish to identify the source. Optimal estimators were recently proposed for regular (exponential growth) and irregular geometric (polynomial growth) trees when all nodes that heard the rumor reveal themselves. We provide the extension to the case in which nodes reveal whether they have heard the rumor with probability p, independent of each other. For geometric trees and p > 0, we achieve the same performance as the optimal estimator with p = 1. For regular trees, the estimator can achieve performance within ε of the optimal, provided that p is larger than a threshold.

We study the use of linear codes for network computing in single-receiver networks with various classes of target functions of the source messages. Such classes include reducible, semi-injective, and linear target functions over finite fields. Computing capacity bounds and achievability are given with respect to these target function classes for network codes that use routing, linear coding, or nonlinear coding.

A basic trade-off between spatial and frequency diversities available for communication with multiple scattered waves is presented. A rigorous notion of the total number of space-frequency degrees of freedom of the field is introduced based on Slepian's theory of spectral concentration of L2functions. This definition agrees with the “rule of thumb” of multiplying the degrees of freedom available in space and frequency. However, while the mathematical definition requires both frequency and spatial bandwidths to scale simultaneously, a physical argument precludes such a scaling to occur in practice. Hence, since the nature of wireless communication prevents unbounded and simultaneous spatial and frequency diversity gains, rule of thumb definitions of degrees of freedom should be taken with care as they are inherently imprecise.

A code for communication over the k-receiver complex additive white Gaussian noise broadcast channel (BC) with feedback is presented and analyzed using tools from the theory of linear quadratic Gaussian optimal control. It is shown that the performance of this code depends on the noise correlation at the receivers and it is related to the solution of a discrete algebraic Riccati equation. For the case of independent noises, the sum rate achieved by the proposed code, satisfying average power constraint P, is characterized as 1/2 log(1+Pφ), where the coefficient φ ∈ [1,k] quantifies the power gain due to the presence of feedback. This includes a previous result by Elia and strictly improves upon the codes by Ozarow and Leung and by Kramer. When the noises are correlated, the prelog of the sum capacity of the BC with feedback can be strictly greater than 1. It is established that for all noise covariance matrices of rank r the prelog of the sum capacity is at most k-r+1 and, conversely, there exists a noise covariance matrix of rank r for which the proposed code achieves this upper bound. This generalizes a previous result by Gastpar et al. for the two-receiver BC.

This paper considers a random access system where each sender is in one of two possible states, active or not active, and the states are only known to the common receiver. Active senders encode data into independent information streams, a subset of which is decoded depending on the collective interference. An information-theoretic formulation of the problem is presented and the set of achievable rates is characterized with a guaranteed gap to optimality. Inner and outer bounds on the capacity region of a two-sender system are tight in the case of a binary-expansion deterministic channel and differ by less than one bit in the case of a Gaussian channel. In systems with an arbitrary number of senders, the symmetric scenario of equal access probabilities and received power constraints is studied and the system throughput, i.e., the maximum achievable expected sum rate, is characterized. It is shown that a simple coding scheme where active senders transmit a single message is optimum for a binary-expansion deterministic channel and achieves within one bit of the optimum in the case of a Gaussian channel. Finally, a comparison with the slotted ALOHA protocol is provided, showing that encoding rate adaptation at the transmitters achieves constant (rather than zero) throughput as the number of users tends to infinity.

We study the use of linear codes for network computing in single-receiver networks with various classes of target functions of the source messages. Such classes include reducible, injective, and semi-injective target functions. Computing capacity bounds are given with respect to these target function classes for network codes that use routing, linear coding, or nonlinear coding.

A code for communication over the k-receiver additive white Gaussian noise broadcast channel with feedback is presented and analyzed using tools from the theory of linear quadratic Gaussian optimal control. It is shown that the performance of this code depends on the noise correlation at the receivers and it is related to the solution of a discrete algebraic Riccati equation. For the case of independent noises, the sum rate achieved by the proposed code, satisfying average power constraint P, is characterized as 1/2 log(1 + Pφ), where the coefficient φ ∈ [1, k] quantifies the power gain due to the presence of feedback. When specialized to the case of two receivers, this includes a previous result by Elia and strictly improves upon the code of Ozarow and Leung. When the noises are correlated, the pre-log of the sum-capacity of the broadcast channel with feedback can be strictly greater than one. It is established that for all noise covariance matrices of rank r the pre-log of the sum capacity is at most k - r + 1 and, conversely, there exists a noise covariance matrix of rank r for which the proposed code achieves this upper bound. This generalizes a previous result by Gastpar and Wigger for the two-receiver broadcast channel.

This paper considers the following network computation problem: n nodes are placed on a √n×√n grid, each node is connected to every other node within distance r(n) from itself, and is given an arbitrary input bit. Nodes communicate with each other so that finally a designated sink node can compute a target function f of the input bits. We focus on computing the identity function and the class of symmetric functions under two different communication models. We first consider a noiseless model where links are independent and noise-free, suitable for modeling wired networks. Next, we study a noisy broadcast model in which when a node transmits a bit, each of its neighbors receives a noisy copy of the bit. This is a simple model for wireless communications, originally proposed by El Gamal (1987). We use the protocol model for interference and nodes which do not share neighbors are allowed to transmit simultaneously. For every connection radius r(n), we present lower bounds on the minimum number of transmissions and the minimum number of time slots required to compute f. We then describe efficient protocols which can match both these lower bounds up to a constant factor.

The following network computing problem is considered. Source nodes in a directed acyclic network generate independent messages and a single receiver node computes a target functionfof the messages. The objective is to maximize the average number of timesfcan be computed per network usage, i.e., the “computing capacity”. The network coding problem for a single-receiver network is a special case of the network computing problem in which all of the source messages must be reproduced at the receiver. For network coding with a single receiver, routing is known to achieve the capacity by achieving the network min-cut upper bound. We extend the definition of min-cut to the network computing problem and show that the min-cut is still an upper bound on the maximum achievable rate and is tight for computing (using coding) any target function in multi-edge tree networks. It is also tight for computing linear target functions in any network. We also study the bound's tightness for different classes of target functions. In particular, we give a lower bound on the computing capacity in terms of the Steiner tree packing number and a different bound for symmetric functions. We also show that for certain networks and target functions, the computing capacity can be less than an arbitrarily small fraction of the min-cut bound.

The problem of determining the number of spatial degrees of freedom (d.o.f.) of the signals carrying information in a wireless network is reduced to the computation of the geometric variation of the environment with respect to the cut through which the information must flow. Physically, this has an appealing interpretation in terms of the diversity induced on the cut by the possible richness of the scattering environment. Mathematically, this variation is expressed as an integral along the cut, which we call cut-set integral, and whose scaling order is evaluated exactly in the case of planar networks embedded in arbitrary three-dimensional (3-D) environments. Presented results shed some new light on the problem of computing the capacity of wireless networks, showing a fundamental limitation imposed by the size of the cut through which the information must flow. In an attempt to remove what may appear as apparent inconsistencies with previous literature, we also discuss how our upper bounds relate to corresponding lower bounds obtained using the techniques of multihop, hierarchical cooperation, and interference alignment.

This paper considers the following network computation problem:nnodes are placed on a √n × √n grid, each node is connected to every other node within distancer(n) of itself, and it is assigned an arbitrary input bit. Nodes communicate with their neighbors and a designated sink node computes a functionfof the input bits, wherefis either the identity or a symmetric function. We first consider a model where links are interference and noise-free, suitable for modeling wired networks. Then, we consider a model suitable for wireless networks. Due to interference, only nodes which do not share neighbors are allowed to transmit simultaneously, and when a node transmits a bit, all of its neighbors receive an independent noisy copy of the bit. We present lower bounds on the minimum number of transmissions and on the minimum number of time slots required to computef. We also describe efficient schemes that match both of these lower bounds up to a constant factor and are thus jointly (near) optimal with respect to the number of transmissions and the number of time slots required for computation. At the end of the paper, we extend results on symmetric functions to general network topologies, and obtain a corollary that answers an open question posed by El Gamal in 1987 regarding the computation of the parity function over ring and tree networks.

It is shown using first physical principles and without relying on stochastic fading channel models, that the number of spatial degrees of freedom available in planar wireless networks embedded in a three-dimensional propagation environment is limited by the spatial size of the cut that divides the environment into two parts. Specifically, in the case of propagation inside a cylinder of height h and base area n, containing n communicating source-destination node pairs, the number of available channels is at most proportional to h√n and hence, as the number of nodes increases, the per-user information capacity must follow an inverse square-root of n law.

This paper considers function computation in a network where intermediate nodes perform randomized network coding, through appropriate choice of the subspace codebooks at the source nodes. Unlike traditional network coding for computing functions, that requires intermediate nodes to be aware of the function to be computed, our designs are transparent to the intermediate node operations.

This paper considers a slotted ALOHA random access system where users send packets to a common receiver with multipacket reception capability. A collection of m users access the shared medium independently of each other with probability p and, upon access, they choose an encoding rate. A collision occurs when the sum of the rates of all the users exceeds the capacity of the channel. We analytically characterize as a function of m and p the encoding rate which maximizes the expected global though put of the system. It is shown that for any value of p the throughput converges to one when m tends to infinity, hence there is no loss due to packet collisions. This is in striking contrast with the well known behavior of slotted ALOHA systems in which users cannot adjust the encoding rate. In that case the throughput decreases to zero as the number of users increases. Finally, assuming that users are selfish, we characterize the encoding rate which maximizes the expected individual throughput of each user, and show that the corresponding Nash equilibrium is not globally optimum.

We study the computation of the arithmetic sum of the q-ary source messages in the reverse butterfly network. Specifically, we characterize the maximum rate at which the message sum can be computed at the receiver and demonstrate that linear coding is suboptimal.

This paper considers the following network computation problem: n nodes are placed on a radic(n)timesradic(n) grid, each node in the network is connected to every other node within distance r(n) of itself, and is given an arbitrary input bit. Connected nodes communicate with each other over independent binary symmetric channels of a given transition probability epsiv ges 0, and an arbitrarily designated node computes a symmetric target function f of the input bits. We characterize up to order the minimum number of transmissions required to compute f with a probability of error less than any given positive constant delta. As a side result, we answer an open question posed by El Gamal in 1987 regarding the number of transmissions required to compute the parity function over ring and tree networks.

Wireless networks are fundamentally limited by the intensity of the received signals and by their interference. Since both of these quantities depend on the spatial location of the nodes, mathematical techniques have been developed in the last decade to provide communication-theoretic results accounting for the networks geometrical configuration. Often, the location of the nodes in the network can be modeled as random, following for example a Poisson point process. In this case, different techniques based on stochastic geometry and the theory of random geometric graphs -including point process theory, percolation theory, and probabilistic combinatorics-have led to results on the connectivity, the capacity, the outage probability, and other fundamental limits of wireless networks. This tutorial article surveys some of these techniques, discusses their application to model wireless networks, and presents some of the main results that have appeared in the literature. It also serves as an introduction to the field for the other papers in this special issue.

The one tutorial and 22 papers in this special issue focus on geometry and random graph for the analysis and design of wireless networks. The papers are organized into five groups: Topology; Outage, throughput, capacity, and scaling laws; Connectivity and coverage; Co-existence of disparate wireless networks and cognitive radio; and Distributed algorithms.

This paper studies the problem of secure communication over a wiretap channel p(y,z|x) with a secure feedback link of rate Rf, where X is the channel input, and Y and Z are channel outputs observed by the legitimate receiver and the eavesdropper, respectively. It is shown that the secrecy capacity, the maximum data rate of reliable communication while the intended message is not revealed to the eavesdropper, is upper bounded as Cs(Rf) les maxmin/p(x) {I(X;Y), I(X;Y |Z) + Rf}. The proof of the bound crucially depends on a recursive argument which is used to obtain the single-letter characterization. This upper bound is shown to be tight for the class of physically degraded wiretap channels. A capacity-achieving coding scheme is presented for this case, in which the receiver securely feeds back fresh randomness with rate Rf, generated independent of the received channel output symbols. The transmitter then uses this shared randomness as a secret key on top of Wyner's coding scheme for wiretap channels without feedback. Hence, when a feedback link is available, the receiver should allocate all resources to convey a new key rather than sending back the channel output.

A single-input-single-output (SISO) Poisson fading channel with perfect channel state information (CSI) at the transmitter and the receiver is considered. For a fixed basic rater0, a service outage occurs when the instantaneous transmission rate falls below the rater0. The objective of this paper is to maximize the expected transmission rate subject to peak and average transmitter power constraints and a constraint on the service outage probability. The optimal power allocation scheme is shown to be a combination of the ergodic capacity-achieving power allocation and the outage capacity-achieving power allocation schemes with a randomization between the two deterministic schemes in a boundary set. This randomization is not necessary when the channel fade distribution is continuous. By combining the concepts of ergodic and outage capacity, the proposed optimal scheme judiciously resolves the conflicting objectives of high expected transmission rate and low outage probability.

It is shown that the capacity scaling of wireless networks is subject to a fundamental limitation which is independent of power attenuation and fading models. It is a degrees of freedom limitation which is due to the laws of physics. By distributing uniformly an order ofnusers wishing to establish pairwise independent communications at fixed wavelength inside a two-dimensional domain of size of the order ofn, there are an order ofncommunication requests originating from the central half of the domain to its outer half. Physics dictates that the number of independent information channels across these two regions is only of the order ofradicn, so the per-user information capacity must follow an inverse square-root ofnlaw. This result shows that information-theoretic limits of wireless communication problems can be rigorously obtained without relying on stochastic fading channel models, but studying their physical geometric structure.

The concept of information transmission in a multiple antenna channel with scattering objects is studied from first physical principles. The amount of information that can be transported by electromagnetic radiation is related to the space-wavenumber and the time-frequency spectra of the system composed by the transmitting antennas and the scattering objects, and to the spatial extension of the receiving domain. The spatial information content of the field is related to the number of relevant communication modes of the channel. It is shown that for narrow-band frequency transmission space and time can be decoupled, leading to a space-time information duality principle in the computation of the capacity of the radiating system. In contrast, in the case of wide-band frequency transmission, it is shown that time and space cannot be decoupled and they jointly characterize the wave's information content.

In this letter a physical limit to the information capacity of a multiple-input multiple-output (MIMO) Gaussian channel is presented exploiting the theory of non-redundant sampling of scattered fields. For a MIMO narrow-band system of arbitrarily large spatial extension, the information capacity limit is the same as the one of a single-input single-output (SISO) ultra-wide band (UWB) system. For MIMO systems of finite size, transmitting over a range of frequencies, space and frequency diversities can be optimally combined by allocating the signal power uniformly across space, and increasing linearly across frequency.

This paper studies the problem of secure communication over a degraded wiretap channel p(y, z|x) = p(y|x)p(z|y) with secure feedback link of rate Rf, where X is the channel input, and Y and Z are channel outputs observed by the legitimate receiver and the wiretapper respectively. The secrecy capacity is characterized as Cs{Rf) = maxmin{I(X; Y), I(X; Y|Z) + Rf}. p(x)equation. A capacity-achieving coding scheme is presented, in which the receiver securely feeds back fresh randomness with rate Rf, independent of the received channel output. The transmitter then uses the shared randomness as a secret key on top of Wynerpsilas coding scheme for wiretap channel without feedback. Hence, when the receiver has a means of interacting with the transmitter, he should allocate all resources to convey a new key rather than sending back the channel output. For the converse, a recursive argument is used to obtain the single-letter characterization.

We consider a service outage based power and rate allocation problem for the Poisson fading channel with perfect channel state information at the transmitter and the receiver. A service outage occurs when the instantaneous transmission rate falls below the basic rate r0. The objective of the allocation problem is to maximize the expected transmission rate subject to peak and average transmitter power constraints and a constraint on the outage probability epsiv. A general class of probabilistic power allocation schemes are considered, and the optimum power allocation scheme is shown to be deterministic except for channel fades in a boundary set. When the problem is feasible, the optimum scheme is a combination of ergodic capacity-achieving power allocation and outage capacity-achieving power allocation schemes with a randomization between the two deterministic schemes in the boundary set. This randomization is not necessary when the channel fade distribution is continuous.

It is shown that the capacity scaling of three- dimensional wireless networks is subject to a degrees of freedom limitation which is due to the propagation laws of electromagnetic waves. By distributing uniformly an order of n users wishing to establish pairwise independent communications at fixed wavelength lambda inside a domain of (normalized) volume of the order of n, there are an order of n communication requests originating from the central half of the domain to its outer half. Physics dictates that the number of independent information channels across these two regions is only of the order of n2/3, so the peruser information capacity must follow an inverse-cube root of n law.

The 13 papers in this special issue focus on control and communications. The papers are summarized here.

The information outage probability of a shot-noise limited direct detection multiple-input–multiple-output (MIMO) optical channel subject to block fading is considered. Information is transmitted over this channel by modulating the intensity of a number of optical signals, one corresponding to each transmit aperture, and individual photon arrivals are observed at multiple receive photodetector apertures. The transmitted signals undergo multiplicative fading. The fading occurs in coherence intervals of fixed duration in each of which the channel fade matrix remains constant, and changes across successive such intervals in an independent and identically distributed fashion. The transmitter and the receiver are assumed to be provided with perfect channel state information (CSI). An optimization formulation for the outage probability problem is outlined and an exact characterization of the optimal average conditional duty cycles is provided.

The throughput of delay sensitive traffic in a Rayleigh fading network is studied by adopting a scaling limit approach. The case of study is that of a pair of nodes establishing a data stream that has routing priority over all the remaining traffic in the network. For every delay constraint, upper and lower bounds on the achievable information rate between the two end-points of the stream are obtained as the network size grows. The analysis concerns decentralized schemes, in the sense that all nodes make next-hop decisions based only on local information, namely their channel strength to other nodes in the network and the position of the destination node. This is particularly important in a fading scenario, where the channel strength varies with time and hence pre-computing routes can be of little help. Natural applications are remote surveillance using sensor networks, and communication in emergency scenarios.

The information outage probability of a shot-noise limited direct detection multiple-input multiple-output (MIMO) optical channel subject to block fading is considered. Information is transmitted over this channel by modulating the intensity of a number of optical signals, one corresponding to each transmit aperture, and individual photon arrivals are observed at multiple receive photodetector apertures. The transmitted signals undergo multiplicative fading, and the fading occurs in coherence intervals of fixed duration in each of which the channel fade matrix remains constant. The channel fade matrix varies across successive coherence intervals in an independent and identically distributed fashion. The transmitter and the receiver are assumed to have perfect channel state information (CSI). The main contributions are a formulation of the outage probability problem as an optimization problem and an exact characterization of the optimal solution for the special case of the MIMO Poisson fading channel with two transmit apertures.

This paper considers control and estimation problems where the sensor signals and the actuator signals are transmitted to various subsystems over a network. In contrast to traditional control and estimation problems, here the observation and control packets may be lost or delayed. The unreliability of the underlying communication network is modeled stochastically by assigning probabilities to the successful transmission of packets. This requires a novel theory which generalizes classical control/estimation paradigms. The paper offers the foundations of such a novel theory.

An alternative proof of the Leveque-Telatar (2005) upper bound on the maximum achievable information rate per communication pair in a wireless ad hoc network is presented. The argument exploits the spatial structure of the random point process representing the location of the nodes, and it is based on a simple geometric ldquostrippingrdquo construction that avoids complicated large deviation estimates.

An achievable bit rate per source-destination pair in a wireless network of n randomly located nodes is determined adopting the scaling limit approach of statistical physics. It is shown that randomly scattered nodes can achieve, with high probability, the same 1/radicn transmission rate of arbitrarily located nodes. This contrasts with previous results suggesting that a 1/radicnlogn reduced rate is the price to pay for the randomness due to the location of the nodes. The network operation strategy to achieve the result corresponds to the transition region between order and disorder of an underlying percolation model. If nodes are allowed to transmit over large distances, then paths of connected nodes that cross the entire network area can be easily found, but these generate excessive interference. If nodes transmit over short distances, then such crossing paths do not exist. Percolation theory ensures that crossing paths form in the transition region between these two extreme scenarios. Nodes along these paths are used as a backbone, relaying data for other nodes, and can transport the total amount of information generated by all the sources. A lower bound on the achievable bit rate is then obtained by performing pairwise coding and decoding at each hop along the paths, and using a time division multiple access scheme

The thirty-four papers in this special issue are devoted to models, theories, and codes for relaying and cooperation in communication networks. The demand for large, more efficient, reliable, and cost effective communication networks is motivating new network architectures for cellular and wireless communications as well as cognitive radio and sensor networks.

It is known that linear codes are sufficient to solve the multicast network coding problem when each out-edge of a network node carries its own specific function of the in-edges of the node, i.e. operating in "point-to-point-mode." Alternatively, in "broadcast-mode," a network has the property that for each node, every out-edge of the node carries the same function of the in-edges of the node. Only one transmission is required in order to send the same function on all of the out-edges of a node. The edge functions in broadcast-mode can vary from node to node and each edge can carry an arbitrary number of transmissions, with at most one per time unit. We prove that linear codes are sufficient, in terms of total number of transmissions, for multicast networks in broadcast-mode. That is, we show that for any broadcast-mode solution to a multicast network, there exists a linear broadcast-mode solution over some finite field which does not increase the total number of network transmissions

The throughput of wireless networks is known to scale poorly when the number of users grows. The rate at which an arbitrary pair of nodes can communicate must decrease to zero as the number of users tends to infinity, under various assumptions. One of them is the requirement that the network is fully connected: the computed rate must hold for any pair of nodes of the network. We show that this requirement can be responsible for the lack of throughput scalability. We consider a two-dimensional (2-D) network of extending area with only one active source-destination pair at any given time, and all remaining nodes acting only as possible relays. Allowing an arbitrary small fraction of the nodes to be disconnected, we show that the per-node throughput remains constant as the network size increases. As a converse bound, we show that communications occurring at a fixed nonzero rate imply a fraction of the nodes to be disconnected. Our results are of information theoretic flavor, as they hold without assumptions on the communication strategies employed by the network nodes.

This correspondence considers networks where nodes are connected randomly and can fail at random times. It provides scaling laws that allow to find the critical time at which isolated nodes begin to appear in the system as its size tends to infinity. Applications are in the areas of sensor and ad-hoc networks where nodes are subject to battery drainage and 'blind spots' formation becomes a primary concern. The techniques adopted are based on the Chen-Stein method of Poisson approximation, which allows to obtain elegant derivations that are shown to improve upon and simplify previous related results that appeared in the literature. Since blind spots are strongly related to full connectivity, we also obtain some scaling results about the latter.

The throughput of wireless networks is known to scale poorly when the number of users grows. The rate at which an arbitrary pair of nodes can communicate must decrease to zero as the number of users tends to infinity, under various assumptions. One of them is the requirement that the network is fully connected: the computed rate must hold for any pair of nodes of the network. We show that this requirement can be responsible for the lack of throughput scalability. We consider a two-dimensional network of extending area with only one active source-destination pair at any given time, and all remaining nodes acting only as possible relays. Allowing an arbitrary small fraction of the nodes to be disconnected, we show that the per-node throughput remains constant as the network size increases. This result relies on percolation theory arguments and does not hold for one-dimensional networks, where a non-vanishing rate is impossible even if we allow an arbitrary large fraction of nodes to be disconnected. A converse bound is obtained using an ergodic property of shot noises. We show that communications occurring at a fixed nonzero rate imply a fraction of the nodes to be disconnected. Our results are of information theoretic flavor, as they hold without assumptions on the communication strategies employed by the network nodes.

This paper considers networks where nodes are connected randomly and can fail at random times. It provides scaling laws that allow to find the critical time at which isolated nodes begin to appear in the system as its size tends to infinity. Applications are in the areas of sensor and ad-hoc networks where nodes are subject to battery drainage and 'blind spots' formation becomes a primary concern. The techniques adopted are based on the Chen-Stein method of Poisson approximation, which allows to obtain elegant derivations that are shown to improve upon and simplify previous related results that appeared in the literature. Since blind spots are strongly related to full connectivity, we also obtain some scaling results about the latter

A stochastic-ray model of wave propagation based on the theory of random walks that accounts for only two parameters: the amount of clutter and the amount of absorption in the environment is considered. This model applies to indoor and outdoor environments, characterized by a large number of (small) scattering objects. Examples are microcells for personal communication and networks of multihop wireless sensors or laptop computers. We extend our previous results on narrowband signals to impulse waveforms, deriving a closed form solution for the power delay profile of the received signal.

We consider the problem of how throughput in a wireless network with randomly located nodes scales as the number of users grows. Following the physical model of Gupta and Kumar, we show that randomly scattered nodes can achieve the optimal 1/(n)/sup 1/2/ per-node transmission rate of arbitrarily located nodes. This contrasts with previous achievable results suggesting that a 1/(n log n)/sup 1/2/ reduced rate is the price to pay for the additional randomness introduced into the system. Our results rely on percolation theory arguments. In the high density regime the network is fully connected but generates excessive interference. In the low density regime the network loses connectivity. Percolation theory ensures that a wireless backbone forms in the transition region between this two extreme scalings. This backbone does not cover all the nodes, nevertheless it is sufficiently rich in crossing paths so that it can transport all the traffic in the network. By operating the network in this transition region between order and disorder, we are able to prove our tight bound.

Data collection, i.e., the aggregation at the user location of information gathered by sensor nodes, is a fundamental function of sensory networks. Indeed, most sensor network applications rely on data collection capabilities, and consequently, an inefficient data collection process may adversely affect the performance of the network. In this paper, we study via simple discrete mathematical models, the time performance of the data collection and data distribution tasks in sensory networks. Specifically, we derive the minimum delay in collecting sensor data for networks of various topologies such as line, multiline, and tree and give corresponding optimal scheduling strategies. Furthermore, we bound the data collection time on general graph networks. Our analyses apply to networks equipped with directional or omnidirectional antennas and simple comparative results of the two systems are presented.

Consider an infinite square grid G. How many discs of given radius r, centered at the vertices of G, are required, in the worst case, to completely cover an arbitrary disc of radius r placed on the plane? We show that this number is an integer in the set {3,4,5,6} whose value depends on the ratio of r to the grid spacing. One application of this result is to design facility location algorithms with constant approximation factors. Another application is to determine if a grid network design, where facilities are placed on a regular grid in a way that each potential customer is within a reasonably small radius around the facility, is cost effective in comparison to a nongrid design. This can be relevant to determine a cost effective design for base station placement in a wireless network

Presents a solvable specification and gives an algorithm for the group membership problem in asynchronous systems with crash failures. Our specification requires processes to maintain a consistent history in their sequences of views. This allows processes to order failures and recoveries in time and simplifies the programming of high level applications. Previous work has proven that the group membership problem cannot be solved in asynchronous systems with crash failures. We circumvent this impossibility result building a weaker, yet nontrivial specification. We show that our solution is an improvement upon previous attempts to solve this problem using a weaker specification. We also relate our solution to other methods and give a classification of progress properties that can be achieved under different models.