MODELLING OF COMMUNICATION NETWORKS VIA STOCHASTIC GEOMETRY

held on March 25-28, 1998, at the International Conference Center "Schloss Dagstuhl", in D-66687 Wadern, between Saarbrücken and Trier (Germany).
 
 

The aim of this workshop was to bring together a representative group of

• Applied probabilists and statisticians interested in the development of new models based spatial point processes and stochastic geometry for modelling communication networks;
• Computer scientists and engineers working in the design of the architecture of communication networks, particularly cellular communication systems;
• Economists focusing on cost analysis and on production functions for large communication networks.

•  basic stochastic geometry patterns for communication networks;
• identification of stochastic models for spatial point patterns, line patterns, etc. in this framework;
• their statistical analysis and Monte Carlo simulation;
• random tessellations (Voronoi tesselation, Delaunay triangulation, power tesselations, etc.) and random coverage processes (Boolean model, germ-grain model, etc.) for modelling wired and wireless communications;
• problems of spatial interference and random resource management (measurement-based power control, channel assignement, call access control, etc.) in cellular radio communications
• stochastic modelling of propagation and (hard/soft) hand-off in mobile communications;
• stochastic geometry representation of mobility;
• modelling of architecture of large networks;
• global cost analysis of communication networks; cost function of access, traffic and transmission in communication networks.

ORGANIZERS

 

Professor Francois Baccelli   INRIA Sophia Antipolis  2004, Route des Lucioles  B.P. 93  F-06902 Sophia Antipolis Cedex  baccelli@sophia.inria.fr

Professor Volker Schmidt  University of Ulm  Institute of Stochastics  Helmholtzstr. 18  D-89069 Ulm  schmidt@mathematik.uni-ulm.de

 
 
 

Joint work in progress with Mogens Bladt, IIMAS, National University of Mexico.

Joint work with S. Zuyev (INRIA, Sophia).

In approach (1), recent progress includes the development of another summary function J, with good properties and some connections with survival analysis. We describe the J function and some of its extensions.

As an example of progress in approach (2) we describe a technique for computing approximate maximum pseudolikelihood estimates of the parameters of a spatial point process. The method is an extension of Berman and Turner's device for maximising the likelihoods of inhomogeneous spatial Poisson processes. For a very wide class of spatial point process models, the likelihood is intractable, while the pseudolikelihood is known explicitly, except for the computation of an integral over the sampling region. Approximating this integral by a finite sum yields an approximate pseudolikelihood which is formally equivalent to the likelihood of a loglinear model with Poisson responses. This can be maximised using standard statistical software for generalised linear or additive models, provided the conditional intensity of the process takes an `exponential family' form. Using this approach we are able to rapidly fit a wide variety of spatial point process models of Gibbs type, incorporating spatial trends, interaction between points, dependence on spatial covariates, and mark information.

Joint work with T. Rolf Turner (New Brunswick).

Keywords: Gibbs processes, Markov random fields, spacial BMAPs.

 Service times are distributed exponentially with rate c depending on the position of the user served. A single server moves from one user to the other. After serving one, the next user it moves to is determined by a function  of the positions of all other waiting users and the server's position. The time needed to move from one user to the next will be neglected.

The model in E. Çinlar [1], section 4.5 ``Spatial M/M/1 queues'' coincides with the special case of exponential interarrival time distribution. In the sequel, a closer determination of the stationary distribution shall be undertaken.
 

Literature
[1] Çinlar, E.: An introduction to spatial queues. In: J.H. Dshalalow (Ed.): ``Advances in Queueing'', CRC Press 1995.

The idea of factorial moment expansion is applied in order to derive approximation formulas for characteristics of Boolean models. For example we consider the two-dimensional Boolean model which grains are circles with random radius and which can be used to model the power of users (germs) in a mobile communication system [3]. The intersection with a line (road) form a one-dimensional Boolean model, where the clumps of intersection segments can be interpreted as the regions of interference on the road. Hence one is intereseted in the covered and uncovered parts of the road. For the distribution of the length L of a typical clump, we derive an approximation formula of the form ,where  is the intensity of the underlying Poisson process, and we give a recursion formula for the coefficients a_i. Furthermore, we derive an approximation of the same kind for the distribution of the sum V of the uncovered parts in a given interval.

For the expected clump length of the two-dimensional Boolean model, which grains are segments with random length and orientation, similar approximation formulas can be derived [4].

Numerical experiments demonstrate the goodness of the approximations.
 

Literature
[1] F. Baccelli, S. Hasenfuss and V. Schmidt (1997) Differentiability of functionals of Poisson processes via coupling. Preprint, INRIA Sophia Antipolis/University of Ulm.
[2] B. Baszczyszyn, E. Merzbach and V. Schmidt (1997) A note on expansion for functionals of spatial marked point processes. Statistics and Probability Letters 36, 299-306.
[3] A. Frey and V. Schmidt (1997) Marked point processes in the plane I - a survey with applications to spatial modeling of communication networks. Advances in Performance Analysis (to appear).
[4] C. Rau (1997) Series expansion for characteristics of Boolean models. Diploma thesis, University of Ulm.

To each cell of T, one can associate its center of gravity. This defines a new stationary point process Z. The cells of T are of different types depending on whether they contain both a point of N1 and a point of N2, only one of them, or none of them. These types define various stationary sub-processes of Z. A few basic geometrical characteristics of these cells are considered using Palm probabilities with respect to Z and its sub-processes.

The particular case where N1 and N2 are independent Poisson processes is studied in detail. Using the mean characteristics relationship for planar tessellations, we obtain explicit expressions for the geometrical characteristics of a typical cell under the Palm probability with respect to Z. Integral representations are also derived for the mean value of the area of the cell which contains the origin, under other probability measures, including the Palm probability with respect to the sub-processes of Z, and the underlying stationary probability measure. Asymptotic expansions in k, the ratio of the intensities of the two processes, are used to evaluate these integrals.

Such compound tessellations arise naturally when considering the interconnection of subscribers of two competing telecommunication operators. Here, the point processes N1 and N2 represent the locations of the concentrators of the two operators, whereas T1 and T2 represent the local zones associated with these concentrators. Two subscribers, one of operator 1, and the other of operator 2, belonging to the same cell of T induce different interconnection costs depending on the type of the cell they belong to.

In the first approach, we assume mobiles move independently, but interact through the mutual interference they create for each other. Users control their transmitter powers to counteract their own path losses, but do not react to the power levels of other users. We show that if the arrival process of calls is Poisson, then at any instant the spatial distribution of traffic is Poisson, and using Campbell's theorem we can calculate the mean and variance of other-cell interference. Using the fact in-cell interference is Poisson, and taking a Gaussian approximation for the other-cell interference, we show how outage probabilities can be calculated. This approach requires the spatial traffic intensity function to be known over time, perhaps by direct measurement.

In the second approach, we allow the power levels of users to interact. This is more efficient from a signal processing point of view, but makes performance analysis much harder. In this part of the talk we do not consider time-variation, but that is definitely in the background. For simplicity, we consider how to measure spatial congestion for a given fixed set of users distributed in space. We use a matrix description of the network configuration, and show how the Perron-Frobenius eigenvalue measures congestion, whether that be due to a localized hotspot, or to network-wide congestion.

We study the number N_x(t) of intervals accepted during [0,t]. By Laplace-transform methods, we derive large-x estimates of  and  with error terms exponentially small in x uniformly in , where T is any fixed positive constant. We prove that, as , , ,uniformly in ,where  and  are given by explicit, albeit complicated formulas. Using these asymptotic estimates we show that N_x(t) satisfies a central limit theorem, i.e., for any fixed t

Our interval packing problem has applications similar to those of the parking problem in the physical sciences, but the primary source of our interest is the modeling of reservation systems, especially those designed for multi-media communication systems to handle high-bandwidth, real-time demands.

Joint work with E.G. Coffman Jr, L. Flatto (Bell Labs) and B. Poonen (University of California). 

Joint work with R. Schassberger (Technical University of Braunschweig).

Joint work with G. Latouche (Université Libre de Bruxelles). 

To which extend do existing stochastic geometry models and results meet this end, and what future work would improve the applicability of the theory to actual telecommunication problems ?

Telecommunications network are technically complex and models integrating full deterministic descriptions of a network are incompatible with the synthetic economical analysis tools needed by the telecommunication industry. Existing stochastic geometry models are shown to be robust and reliable and can already be used in economical analysis. However, they cover only a small part of problems to be addressed. So new stochastic geometry research is needed, in mathematics and in statistics, both to improve existing models and to cover new fields.

The network architecture, which is described first, basically consists of a hierarchy of switched sub-networks, a connection architecture between the switches on the different levels according to traffic hypothesis on the links. A cost formula is then defined as a set of relations between relevant network parameters. Finally, a global cost formula is established.

Joint work with C. Gloaguen (France Telecom-Cnet DAC/GTR) and M. Lebourges (France Telecom-Cnet DPS/SEE, Paris).

Joint work with A. Koski and I. Norros (VTT Information Technology). 

This is based on joint work with both Ward Whitt and Kin Leung (AT&T Labs Research).

1.

A realistic, but tractable, mobility model,

2.

a precise description of signalling costs, and

3.

an optimization method to solve the complicated minimization problems.

1.

An open Jackson network with customer classes is developed to describe user mobility and network flows.

2.

A careful analysis of the number of signalling messages and database accesses yields an accurate cost function.

3.

In steady state of the network, integer linear programming is used to find an optimal register allocation strategy for the so called dedicated MHLR policy, where each location area is assigned to an individual MHLR.

Joint work with M. Hellebrandt (Aachen University of Technology).

1.

The process is Markovian, with finite dimensional distributions which are multivariate exponential in the sense of Marshall-Olkin, in particular  and hence E(Z^*(t))=1/t,

2.

The counting process of the jumps is a non-homogeneous Poisson process with rate 1/t.

3.

The process fulfills the distributional equation that , where a>0. Notice that functional equation f(x)= a f(ax) has the solution f(x)=f(1)/x and hence the name hyperbolic.

4.

The process  is symmetric around the line x=t: The inverse process  defined by is equal in distribution to .

Joint work with Andreas Frey (University of Ulm).

In the second model, base station locations are arbitrary and mobile density is arbitrary. We consider the power control problem for a deterministic "fluid limit" of the system, and solve it through an efficient numerical procedure. Comparison to simulation shows that the fluid limit system gives good approximation for the average interference levels at the base stations.

Joint work with F. Baccelli (INRIA, Sophia).

Joint work with I. Molchanov (University of Glasgow).