Tomasz Schreiber
(Faculty of Mathematics and Computer Science
Nicolaus Copernicus University, Torun, Poland)
Stabilizing functionals of Gibbs point processes
Theory of stabilizing functionals, so far developed mainly in the context of binomial and Poisson input fields (Baryshnikov, Penrose, Yukich et al.), proved to be a strong and useful tool in many areas of applied probability. In particular, when combined with the so-called objective method, it provides a unified framework for establishing limit theorems (laws of large numbers, central limit theorems, large and moderate deviations) for a wide range of geometric functionals (broad class of random graphs and networks, random packing and deposition, Boolean models, spacing statistics, stochastic quantization), with the limiting characteristics (expectation, variance, relative entropy density) explicitly expressed in terms of the local geometry of the field. In this talk we show how these results can be extended to cover a general class of Gibbs input fields away from their phase transition regime (which is an indispensible assumption because the limit behavior at criticality is known to often violate the classical limit theory). The particular feature of our approach is that it is based on windowed perfect simulation schemes from thermodynamic limit, in the spirit of Fernandez, Ferrari and Garcia, involving subcritical directed percolation based bounds for decay of dependencies, which enables us to establish our limit results in purely geometric terms thus fully preserving the direct links between the limit characteristics and the local geometry of both the stabilizing functional considered and the interaction present in the Gibbsian input field. Last but not least, the algorithmic features of our proofs provide natural and efficient perfect simulation tools allowing for numeric evaluation of limit constants.
Talk based on joint work with J.E. Yukich.
Reaching consensus about gossip: convergence times and costs
Gossip algorithms have recently received significant attention, mainly because they constitute simple and robust methods for distributed information processing over networks. However, for many topologies that are realistic for wireless adhoc and sensor networks (such as grids and random geometric graphs), the standard nearest-neighbor gossip converges slowly. In this talk, we will introduce and discuss metrics for convergence time and cost that allow us to clearly characterize the steady state regime of the convergence, not only for i.i.d. but for all stationary and ergodic time-varying networks. We will next describe a variation of geographic gossip that averages along routed paths, and which is proven to be order optimal, contrary to standard nearest-neighbor gossip.
Based on joint work with Patrick Denantes (EPFL), Alexandros G. Dimakis (UC Berkeley), Martin Vetterli (EPFL).
Performance of random multi-access algorithms in large networks
In this talk, we will provide a method to analyze networks where interfering users share a resource using random MAC algorithms. We will show that this method is asymptotically exact when the number of users grows large, and explain why it also provides accurate performance estimates even for small systems. We will apply this analysis to address the stability region of non-adaptive ALOHA-like systems. Specifically, we consider a fixed number of users receiving packets from independent exogenous processes and accessing the resource using ALOHA-like algorithms. We provide an explicit expression to approximate the stability region of this system, and prove its accuracy. We will also outline how to apply the analysis to predict the performance of adaptive MAC algorithms, such as the exponential back-off algorithm, in a system where saturated users interact through partial interference.
This is a joint work with David McDonald (University of Ottawa) and Alexandre Proutiere (Microsoft Research).
See presentation in pdf file.
Information-theoretic and physical limits on the capacity scaling of wireless ad-hoc networks
By distributing uniformly at random an order of n nodes wishing to establish pair-wise independent communications inside a 2D domain of area of the order of n using electromagnetic waves, the per-node information rate must follow an inverse square-root of n law, as n tends to infinity. This scaling limit result is computed without postulating fading channel and path loss models, but applying directly Maxwell's physics of wave propagation in conjunction to Shannon's theory of information. Indeed, the upper bound is due to a limitation in the spatial degrees of freedom of the propagating field which can be rigorously proved via functional analysis. Broad conclusions are drawn from this result on the value of the spatial resource in wireless networks, and a description of different configurations of networks which can achieve in principle a much higher (i.e. constant) bit-rate will follow.
Joint work with M.D. Migliore, and P. Minero.
See presentation in ppt file.
Ad hoc wireless networks: information-theoretic optimal operating regimes
See presentation in pdf file.
On Adaptive Rate Control over Multiple Spatial Channels in Ad Hoc Networks
In ad hoc networks of nodes equipped with multiple antennas, the tradeoff between spatial multiplexing and diversity gains in each link impacts the overall network capacity. An optimal algorithm is developed for adaptive rate and power control for a communication link over multiple channels in a Poisson field of interferers. The algorithm and its analysis demonstrate that an optimum area spectral efficiency is achieved when each communication link in a large distributed wireless network properly balances between diversity and multiplexing techniques. The channel adaptive algorithm is shown to be superior to traditional and static multi-antenna architectures, as well as to certain channel adaptive strategies previously proposed. Lastly, the adaptive rate control algorithm is coupled with an optimum frequency hopping scheme to achieve the maximum area spectral efficiency.
Routing Hitting Probability for a Class of Ad Hoc Routing Protocols
We compute the probability that a path is discovered by a class of reactive routing protocols which we denote as random reactive protocols. These reactive protocols do not flood the network, but attempt to find a path from the source to the destination by sending a packet to a destination chosen randomly. Several protocols, including VRR or AODV-NF can be included in this class.
We compute the route hitting probability for such packet, namely the probability that the packet will encounter a node which has a path to the destination. We analytically model the performance of a route discovery scheme which does not rely on flooding to find the connection destination, and show that such system is theoretically promising.
Robust Design of Geographical Networks based on a Population against Failures and Attacks
Robust and efficient design of networks on a realistic geographical space is one of the important issues to realize dependable communication systems. In this paper, based on a percolation theory and a geometric graph property, we investigate it in the following viewpoints: 1) network evolution according to a spatially inhomogeneous population, 2) optimal modality of degrees for the tolerant connectivity against both failures and attacks, and 3) decentralized routing within short paths. Furthermore, we point out the weakened tolerance by geographical constraints than the theoretical prediction, and propose a practical strategy to improve it by adding shortcut links between randomly chosen nodes. These properties of the bounded distance of path, the efficient routing, and the small modality to be robust will be useful for constructing future ad-hoc networks in wide area communication.
On the Coverage Process of a Moving Target in a Dynamic Nonstationary Sensor Field
We analyze the statistical properties of the k-coverage of a point-target moving in a straight line in a dynamic, nonstationary sensor field. The availability of each node is modeled by an independent, {0,1}-valued continuous time Markov chain. Sensor locations form a nonhomogeneous spatial Poisson process. The sensing areas of the sensors are circles of i.i.d. radii. We first describe the induced nonstationary Markov-Boolean model and obtain k-coverage of the target at an arbitrary time instant. We then obtain $k$-coverage statistics for the time interval [0,T.$ A pointwise stationary approximation that yields a limit theorem is also discussed. Numerical results illustrate the analysis.