# Workshop Programme

## for period 6 - 9 April 2010

### Spatial Network Models for Wireless Communications

6 - 9 April 2010

Timetable

Tuesday 6 April | ||||

08:30-09:25 | Registration | |||

09:25-09:30 | Welcome from Sir David Wallace (INI Director) | |||

09:30-10:30 | Bollobas, B (Cambridge) |
|||

Percolation on polygon configurations | Sem 1 | |||

Scullard and Ziff found a simple condition for the self-duality of a family of bond percolation models in the plane, and used it to predict their critical probabilities. This family is wide enough to include models with local dependencies between the states of certain bonds. As in the classical case of bond percolation on the square lattice, the mathematical difficulty is to show that self-duality does imply criticality. Very recently, Oliver Riordan and I proved that this does hold for a family generalizing the models considered by Scullard and Ziff: in the talk I shall present some of our results concerning this. |
||||

10:30-11:00 | Tea | |||

11:00-12:00 | Gupta, P (Bell Labs) |
|||

Scaling of the Unicast and Multicast Capacity Regions of Wireless Networks | Sem 1 | |||

Single-parameter capacity scaling in wireless networks under a specific uniform traffic pattern has been widely studied over the last decade. In general networks, however, different users may generate traffic at widely different rates for destinations that are located at widely different distances. In this talk, we discuss some recent results that obtain scaling characterization under essentially arbitrary unicast/multicast traffic patterns, and thus determine the scaling of essentially the entire unicast/multicast capacity regions. (This talk is based on joint works with U. Niesen, S. Subramanian, D. Shah, and S. Shakkottai.) |
||||

12:15-13:30 | Lunch at Wolfson Court | |||

14:00-15:00 | Last, G (Karlsruhe) |
|||

Gamma distributions in Poisson Voronoi and hyperplane tessellations | Sem 1 | |||

Random Voronoi and hyperplane tessellations are basic models of stochastic geometry. Recently they have been proposed as stochastic models for spatial telecommunication networks. In this talk we will discuss Poisson driven tessellations. Since the seminal work by Miles, Moeller and Zuyev it is known, that the (generalized) integral-geometric contents of several closed sets constructed on stationary Poisson Voronoi and hyperplane tessellations are (conditionally) gamma-distributed. Combining the theory of Palm measures with stopping set techniques we will extend und unify these results. Parts of this talk are based on joint work with Volker Baumstark. |
||||

15:00-15:30 | Coffee | |||

15:30-16:30 | Thiran, P (Lausanne) |
|||

Medium Access Control, Fairness and Phase Transitions in Multihop Wireless Networks | Sem 1 | |||

The last couple of years have seen considerable progress in the design of new throughput-optimal Medium Access Control (MAC) protocols for wireless networks. They are however not compatible in general with the IEEE 802.11 protocol, which is the most widely used protocol in current wireless networks. We adopt a dual point a view, which is to find models of 802.11 protocols which capture rigorously all the essential features of this protocol, and remain simple enough to provide insight in the context of multi-hop wireless networks. We consider two scenarios. In the first one, all nodes are saturated with fresh traffic (all queues are thus infinite), and we explore systematically the trade-off between spatial reuse (and thus throughput) and fairness, which is inherent to decentralized CSMA MAC protocols, such as IEEE 802.11. We show in particular that the widely observed unfairness of the protocol in small network topologies does not always persist in large topologies. In large 1-dim. networks, nodes sufficiently far away from the border of the network have equal access to the channel, but not in 2-dim networks, where we observe a phase transition implying a strong unfairness of the protocol. In the second scenario, one node only (the source) is saturated with fresh traffic, whereas all other nodes act as relays or destination for the traffic originated at the source node. We show theoretically and experimentally that IEEE 802.11 can become unstable if the network diameter is larger than 3 hops, and we propose a modification (EZ-flow) that stabilizes the network while staying backward compatible with the former protocol. We evaluate its performance on an experimental testbed. This is a joint work with Adel Aziz, Mathilde Durvy and Olivier Dousse. |
||||

17:00-18:00 | Welcome wine reception | |||

18:45-19:30 | Dinner at Wolfson Court |

Wednesday 7 April | ||||

09:30-10:30 | Aldous, D (Berkeley) |
|||

Discrete and Continuum Random Spatial Networks | Sem 1 | |||

I will give an overview of ongoing research concerning networks in two-dimensional space, emphasizing two aspects. (1) There is a general class of "proximity graphs", defined for arbitrary vertices, which are always connected. Applying to random points gives a class of random networks which are connected and have bounded mean degree. This class has scarcely been studied, but seems an appealing modeling alternative to the classical geometric random graphs for which one cannot have both connectivity and bounded mean degree. (2) The models above envisage e.g. inter-city road networks linking distinct cities. To instead abstract online maps, suppose that for each pair of points in the plane (addresses) there is a route between them. Does it make sense to think of such a network as a realization from a probability distribution invariant under Euclidean translation and scaling? |
||||

10:30-11:00 | Tea | |||

11:00-12:00 | Bordenave, C (Toulouse) |
|||

Load optimization in a planar network | Sem 1 | |||

We will analyze the asymptotic properties of an Euclidean optimization problem on the plane. Specifically, we consider a network with 3 bins and n objects spatially uniformly distributed, each object being allocated to a bin at a cost depending on its position. Two allocations are considered: the allocation minimizing the bin loads and the allocation allocating each object to its less costly bin. This model is motivated by issues in wireless cellular networks. We will aim at the asymptotic properties of these allocations as the number of objects grows to infinity. Using the symmetries of the problem, we will derive a law of large numbers, a central limit theorem and a large deviation principle for both loads with explicit expressions. In particular, we prove that the two allocations satisfy the same law of large numbers, but they do not have the same asymptotic fluctuations and rate functions. |
||||

12:15-13:30 | Lunch at Wolfson Court | |||

13:45-14:45 | Franceschetti, M (San Diego) |
|||

The percolation benefit of spreading random connection functions | Sem 1 | |||

We consider random connection models in Euclidian space. Although it is in general not possible to determine the exact percolation threshold for the resulting random graphs, we ask a perhaps simpler but related question, namely how the percolation threshold changes with the shape of the connection function. It turns out that for a natural spreading transformation of the connection function, the critical density for these models decreases \emph{strictly} to its limiting value. This indicates that in many real networks it is in principle possible to exploit the presence of spread-out, long range connections to achieve connectivity more easily, at a strictly lower density value. In the course of the talk, we will describe some previous results on spreading transformations and spread-out limits, we will try to emphasize the role of long-range connections for reaching connectivity, and we will mention some open problems. Finally, we will also hint at the role of the strict inequality $p_c^{ bond} < p_c^{site}$ to prove the strict monotonicity result. |
||||

15:00-15:30 | Coffee | |||

16:00-17:00 | Soljanin, E (Bell Labs) |
|||

On Storing and Retrieving (coded) Data in Mobile P2P Networks | Sem 1 | |||

Imagine an agent having a piece of information that he wants to communicate to his partner. The agent knows that his partner resides in a certain part of an occupied city but does not want to be seen talking with him, or with anyone else on the street for a long time. The agent and his partner have a number of friends walking in the same part of the city, and are willing to relay small pieces of information between the secret couple. Because of that, the agent decides to split his data in small chunks which he can inconspicuously pass to his friends. To increase persistency of the data among the friends who are moving in an adverse environment, the agent also decides to make these data chunks redundant by using erasure correcting codes. Assuming that all participants in this storing and retrieving process perform simple random walks over a finite, random, regular, graph, and can exchange information only when they are on the same node of the graph, we describe how coding, at the expense of introducing redundancy and processing complexity, not only increases the persistence of the data, but also reduces the average time necessary for the transfer of information between the agent and his partner. |
||||

18:45-19:30 | Dinner at Wolfson Court |

Thursday 8 April | ||||

09:30-10:30 | Peres, Y (Microsoft) |
|||

Finding Sparse Cuts Locally Using Evolving Sets and the anatomy of random graphs | Sem 1 | |||

10:30-11:00 | Tea | |||

11:00-12:00 | Shah, D (MIT) |
|||

Medium Access using Queues | Sem 1 | |||

Simple, distributed and iterative algorithms, popularly known as message-passing, have emerged as the architecture of choice for a variety of networks. They have been surprisingly effective despite their simplicity. In this talk, I will try to argue in favor of such algorithms by discussing an example from wireless communication networks. Specifically, I will discuss the design of an efficient medium access algorithm for wireless networks using queue-sizes. Here nodes wish to transmit without interfering with each other while maximizing utilization of the wireless medium. To minimize co-ordination cost, solutions implemented in practice are based on `random access'. However, they perform quite poorly as proved in theory and observed in practice. I will present an `adaptive' random access algorithm that is provably efficient in both asynchronous and synchronous setup. This work draws insights from the classical variational principle, mixing times of Markov chains and reversibility. The talk is based on joint work with Jinwoo Shin, MIT. |
||||

12:15-13:00 | Lunch at Wolfson Court | |||

13:00-15:00 | Poster session | |||

15:00-16:00 | van der Hofstad, R (Eindhoven) |
|||

Random graph asymptotics on high-dimensional tori: volume, diameter and mixing time | Sem 1 | |||

We study finite-size scaling in high-dimensional percolation, where edges are independently kept with probability p. It is well known that percolation has a phase transition, i.e., there exists a critical value p_c such that for p>p_c there is a unique infinite connected component, while for p < p_c all connected components are finite. In the last decades, substantial progress has been made in the understanding of percolation in high-dimensions. In particular, we know that there is no infinite cluster at the critical value, and various critical exponents have been identified as the ones for percolation on a tree. The reason for this is that the geometry trivializes, since far away pieces of connected components are close to independent. In this talk we shall investigate the largest connected component for critical percolation on a high-dimensional torus. We shall prove that it shares many features with percolation on the complete graph, or the Erd\H{o}s-R\'enyi random graph (ERRG). We shall also discuss conjectures for the scaling limit, as well as for inhomogeneous spatial percolation models where the edges remain independent, but depend on certain vertex weights. For non-spatial versions, which Bollob\'as, Janson and Riordan call the rank-1 inhomogeneous random graph, we have a characterization when the scaling limit of the critical clusters ordered in size is equal to the one on the ERRG, and when it is different. This is joint work with Shankar Bhamidi, Johan van Leeuwaarden, Markus Heydenreich, Gordon Slade, Christian Borgs, Jennifer Chayes and Joel Spencer. |
||||

16:00-16:30 | Coffee | |||

16:30-17:30 | Xie, L-L (Waterloo) |
|||

Omnidirectional Relay in Wireless Networks | Sem 1 | |||

For wireless networks with multiple sources, an omnidirectional relay scheme is developed, where each node can help relay multiple messages in different directions. This is accomplished by the decode-and-forward relay strategy, with each relay binning the multiple messages to be transmitted, in the same spirit of network coding. Specially for the all-source all-cast problem, where each node is an independent source to be transmitted to all the other nodes, this scheme completely eliminates interference in the whole network, and the signal transmitted by any node is used by any other node. For networks with some kind of symmetry, assuming no beamforming is to be performed, this omnidirectional relay scheme is capable of achieving the maximum achievable rate. I will try to expose the key ideas behind this interference-free wireless networking, starting with the basic single-relay channel. |
||||

19:30-22:00 | Conference Dinner at Clare College |

Friday 9 April | ||||

09:30-10:30 | Penrose, M (Bath) |
|||

Strict inequalities of critical points in continuum percolation | Sem 1 | |||

For any infinite connected graph, the critical probabilities for bond percolation and for site percolation satisfy the inequality $p_c^{\rm bond} \leq p_c^{\rm site}$. Moreover, this is known to be a strict inequality on a large class of lattices. In this talk, we discuss the extension of the strict inequality to certain {\em random} graphs arising in continuum percolation, including the Gilbert graph in which each point of a homogeneous planar Poisson point process of supercritical intensity $\lambda$ is connected by an edge to every other Poisson point within unit distance. More generally, we consider the random connection model, in which each pair of Poisson points distant at most $r$ apart is connected by an edge with probability $p$, so that the average node degree is $\lambda \pi r^2 p$. Given $r$ and $p$ there is a critical intensity $\lambda_c(p,r)$ above which the graph percolates. As well as the strict inequality $p_c^{\rm bond} < p_c^{\rm site}$ for this graph, we discuss a related result which says that $\lambda_c(r^{-2},r)$ is strictly decreasing in $r $. That is, for a given average node degree it is easier to percolate in a graph with long-range connections than in a graph with only short-range connections. |
||||

10:30-11:00 | Tea | |||

11:00-12:00 | Zuyev, S (Gothenburg) |
|||

Thinning-stable point processes: new models in telecommunications | Sem 1 | |||

Point processes recently gained recognition in modelling different aspects of telecommunication systems: network components, mobile customers, infrastructure, etc. In many cases though the underlying system shows highly irregular spatial characteristics: number requests serviced by a web-server varies hugely as a function of popularity and happening events. Number of active mobile users calling during popular events: football match, rock concert differs in order of magnitudes from normal periods. This calls for development of point process models exhibiting such bursty behaviour, in time or in space. We introduce a wide class of point processes which generally have infinite expected number of points in a bounded domain, yet they appear unavoidably as limit in the thinning-superposition of point processes schemes. We show that these processes are necessarily Cox processes driven by strictly stable parameter measure and give insight into their cluster structure and further distributional properties. |
||||

12:15-13:30 | Lunch at Wolfson Court | |||

14:00-15:00 | Blaszczyszyn, B (Paris and Wroclaw) |
|||

Stochastic geometry and wireless ad-hoc networks - from the coverage probability to the asymptotic end-to-end delay on long routes | Sem 1 | |||

The aim of this talks is to show how stochastic geometry can be used to analyze some key phenomena that arise in the context of medium access (MAC) and routing in wireless ad-hoc networks. We limit ourselves to simple (yet not simplistic) model of Poisson mobile ad-hoc network (MANET) with slotted Aloha and concentrate on the so-called outage scenario, where a successful transmission requires a signal-to-Interference-and-Noise (SINR) larger than some threshold. We also assume Rayleigh fading. Starting from a simple explicit expression for the successful transmission probability we will show first how various network performance metrics related to the throughput can be evaluated in the scenario where all the receivers are located within some fixed distance to the receiver. Then we make a first step towards a joint analysis of MAC and routing considering a few more complex scenarios for receiver location, all motivated by the fact that real routing mechanisms typically select receivers in the vicinity of the respective emitters. The analysis of these more adequate models reveals interesting phenomena related to the local delay in MANETS, namely the number of times slots required for nodes to transmit a packet to their prescribed next-hop receivers. We will show that in most cases, each node has a finite-mean geometric random delay and thus a positive next hop throughput, however, the spatial (or large population) averaging of these individual finite mean-delays leads to infinite values in several practical cases. In some cases it exhibits a phase transition, where the spatial average is finite when certain model parameters are below a threshold and infinite above. Finally, we consider a fully cross-layer MAC/routing model, where there is no predefined route and where the routing scheme tries to take advantage of the variability of MAC and fading to decide on the next relay for each packet at each time slot. An important negative consequence of the previous observation on local delays is that the mean end-to-end delay of a packet delivery in Poisson MANET scales superlinearly with the distance between source and destination, or, in other words, the asymptotic velocity of a typical packet is null, even if this packet is considered as a priority packet and experiences no queuing in the nodes. The main positive result, formulated and proved using the framework of the first passage percolation on a SINR space-time graph, states that when adding a periodic node infrastructure of arbitrarily small intensity to the Poisson MANET makes the end-to-end delay scale linearly with the delivery distance. The talk is based several papers written jointly with F. Baccelli, P. Muhlethaler and O. Mirsadeghi. A more detailed exposition of this subject can be found in the book "Stochastic Geometry and Wireless Networks, Volume II- Applications" by F. Baccelli and B.B., Foundations and Trends in Networking, NoW. |
||||

15:00-15:30 | Coffee | |||

15:30-16:30 | Leveque, O (Lausanne) |
|||

Optimal cooperation in large wireless networks | Sem 1 | |||

In this talk, I will present a new way to handle communication in wireless networks, that uses a recursive cooperation architecture and distributed MIMO communications. This new scheme allows to get rid of the interference limitation experienced by classical multi-hop strategies, achieving therefore much higher capacity scaling than multi-hop for a wide range of network parameters. I will then study in detail the performance of the proposed scheme and compare it to that of multi-hop, when either power or space (i.e. network area) becomes a scarce resource in the network. The main conclusion to be drawn from this analysis provides a rejoinder with the recent work of Franceschetti et al. on the physical limits of wireless networks. |
||||

18:45-19:30 | Dinner at Wolfson Court |