Stochastic geometry and telecommunication networks
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Number of Parts | 22 | |
| Author | ||
| License | CC Attribution 3.0 Germany: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. | |
| Identifiers | 10.5446/57502 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
Leibniz MMS Days 202210 / 22
11
19
00:00
GeometryCycle (graph theory)Group actionModel theoryStochastic geometryComputer animation
00:33
Directed graphExplosionMortality rateAbelian categoryBand matrixGeometryVector potentialPoisson processPhysical systemConnectivity (graph theory)Green's functionTessellationTime zoneGradientRandom numberModel theoryKeilförmige AnordnungPredictionConstraint (mathematics)Thermodynamisches SystemMathematical analysisTessellationStochasticGeometryModel theoryEnergy levelSlide ruleKörper <Algebra>Physical systemMaß <Mathematik>Connectivity (graph theory)TheoremRandomizationRandom walkMereologyOperator (mathematics)Point (geometry)Event horizonStochastic processThermodynamisches SystemSpacetimeCartesian coordinate systemAreaPerspective (visual)StatisticsStochastic geometryProcess (computing)PredictabilityPotenz <Mathematik>Ocean currentPower (physics)Centralizer and normalizerExtension (kinesiology)Graph (mathematics)MultiplicationClosed setPressureStandard deviationDecision theory40 (number)Student's t-testCasting (performing arts)Musical ensembleStatistical hypothesis testingComputer animation
08:50
Poisson processTessellationTime zonePhysical systemGradientGeometryThermodynamisches SystemConstraint (mathematics)Random numberKeilförmige AnordnungPredictionModel theoryMathematical analysisProcess (computing)Expandierender GraphConnectivity (graph theory)MultiplicationAerodynamicsDerivation (linguistics)ApproximationEvent horizonTerm (mathematics)Phase transitionLimit (category theory)SpacetimeCartesian coordinate systemPhysical systemAdditionCharacteristic polynomialModel theoryGenetic programmingConnectivity (graph theory)Extension (kinesiology)AreaMathematical analysisGraph (mathematics)Annihilator (ring theory)Multiplication signParameter (computer programming)Kontraktion <Mathematik>Stochastic geometryMereologyVariety (linguistics)Connected spaceNumerical analysisPropagatorDirection (geometry)Point (geometry)Green's functionRadiusAnalytic continuationConfiguration spacePredictabilityPositional notationCentralizer and normalizerKritisches PhänomenResultantMultilaterationThomas BayesOperator (mathematics)Presentation of a groupState of matterLimit (category theory)Set theory2 (number)Ultraviolet photoelectron spectroscopyArithmetic meanComputer animation
17:07
Derivation (linguistics)Mathematical analysisLimit (category theory)Random numberModel theoryPhase transitionPoisson processPseudopotenzialGeometryThermodynamisches SystemProcess (computing)Independence (probability theory)Standard Boolean modelStatisticsInfinityCluster samplingExtension (kinesiology)Parameter (computer programming)Point (geometry)Constraint (mathematics)Mortality rateFunction (mathematics)Exponential functionTheoryPopulation densitySampling (music)Classical physicsTheoremSurvival analysisLogical constantRadiusKeilförmige AnordnungGraph (mathematics)Vertex (graph theory)Connectivity (graph theory)Point (geometry)DiagramConfiguration spaceAreaSpacetimeMultiplication signContinuum hypothesisGraph (mathematics)PercolationSet theoryMathematical analysisNumerical analysisSummierbarkeitConnectivity (graph theory)Mortality rateInfinityTessellationStochastic processProcess (computing)RandomizationStandard deviationPosition operatorGeometryStochastic geometryDerivation (linguistics)Dynamical systemRandom graphIndependence (probability theory)Functional (mathematics)Sampling (statistics)Connected spaceEvent horizonStochasticParameter (computer programming)TheoryPhysical systemGleichverteilungGroup actionSymmetry (physics)Phase transitionSurvival analysisCartesian coordinate systemEstimatorPrice indexMereologyMaß <Mathematik>Thermodynamisches SystemStatistical physicsLocal GroupRange (statistics)Körper <Algebra>ResultantBlock (periodic table)Statistical hypothesis testingEnergy level2 (number)Regulator geneRight angleAnalytic continuationDistanceState of matterExpected valuePopulation densityComputer animation
25:24
GeometryPoisson processProcess (computing)Random numberGraph (mathematics)Vertex (graph theory)InfinityPoint (geometry)Connectivity (graph theory)Keilförmige AnordnungPercolationPoint (geometry)Mathematical analysisGroup actionModel theoryRandomizationMaß <Mathematik>Square numberRoutingPhysical systemGoodness of fitCondition numberParameter (computer programming)Expected valueKritischer Punkt <Mathematik>Configuration spaceRange (statistics)ForceDirection (geometry)Gaussian processMultiplication signProjective planeKontraktion <Mathematik>AreaPosition operatorOperator (mathematics)Perspective (visual)Probability distributionRückkehrpunktRandom graphBand matrixTheoremMoment (mathematics)DivisorMany-sorted logicSpacetimeMultilaterationProcess (computing)Numerical analysisResultantConnected spaceTheory of relativityDirac delta functionComputer animation
Transcript: English(auto-generated)
00:01
Thank you for the introduction. My name is Benedict Janen. I work at the Weierstrass Institute. It's a pleasure to be here and present some joint work within my group, DICOMnet. It's a small group at Vias in Berlin. And we are all probabilists.
00:22
And we use stochastic geometry to model and analyze telecommunication networks. So I also realized that this is a diverse audience. So I tried to essentially do my talk in three parts,
00:43
some motivation, some general ideas, but I don't want to spare you from some theorems at the end of my talk. So you have an idea what we're actually doing every day. So the motivation, as I said, comes from telecommunication
01:01
systems. I guess I don't have to emphasize this too much. There is a strongly increasing demand for communications on all different levels. This is just some slides that I took from, some picture that I took from a big telecommunication
01:21
systems provider, Cisco. And they make predictions in their white papers. And they indicate that we have an explosion of data transmissions, an explosion of subscribers. There's the large field of Internet of Things, where small units communicate with each other.
01:43
Machine to machine is a buzzword in the field. So we have just this tremendous increase in mobile communication, but also in communication of small devices like sensors. Exponential growth, essentially, is what we see right now
02:04
and in the near future. And I want to address a very particular part of this development and how operators try to cope with these challenges. And the part that I want to speak about today
02:21
are spatial networks. So not social networks in the internet, these are spatial networks. And in particular, an aspect of spatial networks that is also already to a small extent implemented in the current 5G mobile standard, but it will be playing a more stronger role.
02:42
Many people predict that it will be playing a stronger role even in the future. And this aspect is device to device communications. So as these simulated pictures should indicate, we have maybe an environment, some kind of edge system here,
03:00
some kind of urban topology maybe, and we have devices that sit in this environment. Here are indicated by blue points. And they're supposed to communicate in a peer-to-peer fashion directly with each other. And this should bring some key benefits to the systems
03:23
that are listed here. It provides more robustness to the system because there's multiple paths that data can be transmitted between components of the networks. It can come with much lower costs. We can get rid of heavy infrastructure, billions worth of infrastructure.
03:41
And our current days, mobile phones have a lot of power themselves, for instance. Security issues come decentralized. This is a benefit, but this can also be a challenge. And we can get rid of a lot of latency. If you think of peer-to-peer communications,
04:02
we don't have to go to the backbone of the system. We don't have to go through base stations. The devices can communicate in a peer-to-peer fashion, makes it faster and more robust. Many more aspects that I have listed here. And of course challenges.
04:21
One of the main challenges is that from an operator's perspective, you cannot control the system. It's an ATOC system. So the network components building this network and you have to deal with the fact that this is somehow not controlled by some operator.
04:43
It's actually hard to read from here. Applications, I mean, I think I've already addressed some of them. Already implemented are mainly sensor networks where for instance, in large solar fields,
05:02
the different sensors communicate with each other. It makes no sense to build up some centralized base station system. The sensors communicate, they accumulate the data and they bring it to some exit point. So you see this implemented already in a few situations in the real world, but we hope and we try to support by our research
05:24
more applications in the new future. For instance, by creating networks in areas of the world where there is no infrastructure available yet.
05:41
So our apriori belief is that we can only understand these systems theoretically by using probabilistic methods. As I tried to convince you, there is an intrinsic randomness in the system because we cannot control how the individual components behave in the system.
06:04
So I want to use the lenses of a probabilist to model and analyze these systems. Randomness enters on various levels. There is an intrinsic randomness on the behavior of the components.
06:21
It's from an operator's perspective, you have a lot of uncertainty how they behave. We have stochastic algorithms that are partially used but can still be developed. And when we deal with randomness, then we can essentially look at the system from two sides. What is the expected behavior of the system?
06:42
That's important from a design perspective and something that is not yet developed so good and we want to make contributions there. We do come make contributions there is to also understand the system in its behavior and its unexpected behavior, which is also critical. You want to understand situations
07:01
where the system behaves really bad and understand why it behaves bad. And this is typically also very hard to simulate if you have a model because maybe these bad situations are very rare. So to make a statistics on the typical behavior within the rare events is difficult.
07:23
And we have some tools to tackle this problem. The others we use is stochastic geometry. So that's maybe roughly 40, 50 years old field within spatial probability. And in essence, you can make a mapping
07:42
between notions in stochastic geometry and the notions that come up when you speak with people from engineering in big telecommunication companies. So for instance, the device locations can be seen as point processes.
08:02
So point processes would be the equivalent notion within the community of stochastic geometry for the locations of the devices or the components of the networks in space. For instance, we can deal with an environment and in this picture, the environment is a street system
08:21
and this can be seen as a tessellation process in space which is also a quite fundamental notion in stochastic geometry. Mobility is a big topic. How do the components move in space? And there's a large array of models
08:41
within the probabilistic community that try to model this. For instance, the random waypoint model which is different from a random walk but it also has some similarities. There is medium access.
09:02
I mean, basically what I tried to convince you that there is a, this is really the right framework. We can find the appropriate notions within the stochastic geometry world for a variety of, yeah, for the models.
09:21
What we want to do, and this is our domain, we want to make rigorous analysis. So by solid mathematical theorems and deductions. So this should enable us to make predictions for the future by understanding these models
09:42
with a particular interest in the critical behavior. So do we see maybe faith transitions? Do we see situations where this model dramatically changes its behavior when you just vary a certain parameter a little bit? So discontinuities with respect to the parameter space.
10:02
And many of these instances are also supported by simulation. So I present to you now three different applications and associated methods that we use
10:22
and the first application is connectivity in mobile urban networks. And just stick with the picture maybe. There is a city topology, maybe some street system and we have mobile devices in blue and we have some additional base station infrastructure
10:42
and now we want to augment the base stations or the system by the possibility to have intermediate peer-to-peer connections. So the green base stations, they come with a certain interaction radius where they can directly be connected with devices but there are lighter green extensions of these areas
11:04
by adding one, two, three additional peer-to-peer hops. And the base stations, they don't move in space but the devices they move maybe along the streets, maybe away from the streets and a characteristic of the network that we want to analyze,
11:22
I put here in the display in mass, symbols don't worry too much, maybe later I will be more precise with the notation. One important quantity is the connection time. So how much time does a typical device connect to an infrastructure using at most khops?
11:43
So if you build such a network, this is very important to understand the quality of the network, how much time do you actually spend connected to the infrastructure via at most khops? Second, maybe how often do you have to reconnect to new base stations? All these quantities play a major role
12:02
in the design of these networks. Let me also say that in many instances, our analysis will be performed in some kind of limiting regime. It's rather hard to come up with vigorous results if you fix parameters.
12:21
So we want to understand essentially the edges and corners of the parameter space by for instance, letting the number of hops become large, letting time become large. So the actual analysis is typically performed in some kind of limiting regime.
12:46
Another application is a data routing. So here's the image or the picture is as follows. One has a central base station and a number of randomly placed devices
13:01
around the base station, base stations in the center. And now the idea is that every device has a certain algorithm that tells them, okay, I want to connect to the base station in the center but I cannot go there directly. So I use, I look for instance for the device
13:21
that is closest to me in the direction of the base station and therefore creating a tree where messages pass through via other devices towards the base station. And then for instance, the question can be, how is the data, how much data does actually a point close
13:43
by the base station has to handle? So how much data is actually passed through nodes that are close to the base station? And also here, the system can be analyzed in its expected behavior. But what is even more interesting is to understand
14:03
what are the typical configurations of the system. So for instance, a large proportion of devices cannot connect to the base station because maybe there's too much throughput in a certain region of space. So this is, we also do again,
14:21
an analysis with respect to the expected behavior but also the unexpected behavior. This is very important. Third application is a malware propagation. And here the idea is that there is wanted data
14:44
in the system, there's unwanted data and this is a decentralized situation. So there is maybe a malware at some typical node at the center of the network and how does it propagate through the network? Obviously, this is very much connected
15:02
maybe to models for epidemic spreading. So I think we make there quite a strong connection towards spatial epidemic modeling. So here you see a picture where you have susceptible devices in space.
15:20
They're connected whenever they're sufficiently close to each other. And we have an initial malware at the center. It spreads through the edges step by step in continuous time in this case and red infected devices appear. But here comes a speciality of our model
15:43
which we designed together with people from Orange by the way, I should mention this. We have a major collaboration with industry. So just to make sure that this is not purely academic. So there's regular contracts. I think we have seven contracts already where we analyze and simulate these systems for them.
16:05
So there is some grounding there. Anyways, the speciality is now, so how can you counteract this spreading of a malware over an infection through the system
16:21
and what they imagine and already in part have prototyped is something that they call a white knight which is also a device in space. It's essentially indistinguishable from the regular devices and it can patch an infected device
16:42
whenever it is attacked. The problem here seems to be that you cannot simply patch any device because of legal reasons you have to wait until you're attacked and only then you can patch. So this makes a system actually quite complicated, highly non-monotonic and what you see in the picture
17:03
here is a later point in time. Initially there is an infection at the origin. There are white knights in green in space, sparsely and then the infection grows and whenever an infection meets a white knight it can retaliate and therefore on the set
17:21
of infected devices patch and they become green. So you see a kind of a chase escape dynamics here. The infection has a slight advantage because it can go to all the susceptible devices but the white knights they have to chase
17:45
because they can only use the infected devices. So this is an analysis that we do and let me also say that one of the main inputs here is that we deal with a random network of positions.
18:03
So many of these things have been done actually quite recently on non-random, let's say grids or non-random topologies, geometries. In our case, we always deal with these
18:22
random point configurations in space. So these are three applications. Now let me address briefly methods that we use from stochastic geometry. One key method is called continuum percolation.
18:43
This is closely linked by the way to statistical physics. And this is one of the key concepts that we explore and use and it goes like this. For instance, in this picture, you have some kind of environment in green
19:01
where you see a certain intensity of points in blue and they all come with a certain interaction value that might be device dependent. So we can model this also by assigning individual IID areas where the devices can form connections.
19:25
And then the question in continuum percolation is if you now tune the intensity of the devices, the expected number of devices you see in a unit volume, does when if you tune this up, so you see more and more devices in expectation,
19:42
is there a point where the system dramatically change from a locally, a local behavior where you see only local clusters of connected devices to a global situation where all of a sudden with a positive probability, a typical device can actually connect to infinity. For us, this is a rough estimate
20:02
of a breaking point of the system where it jumps from a purely local behavior to a global behavior. So for us, this is some kind of a first indication how many people do you actually have to attract
20:22
to such a system have to be part of the system. So you see long range, the possibility of long range connectivity. The second method that is quite underdeveloped
20:44
in the field is the method of large deviations. So as I mentioned briefly, large deviations is a highly developed machinery, methodology within stochastics in general to deal with rare events. And the rare event is for instance,
21:02
this random variable Xn, it wants to be, it has an expected value where it wants to be. There's always a running parameter n, I will maybe later explain more. And we are interested in what is actually the probability that the system behaves away from what it wants to be,
21:20
from its expected behavior. And in many instances, if you have enough independence in the system, this goes exponentially and there is a certain speed, the rate function I, and this rate function can be used to understand the typical behavior within the atypical event.
21:42
And this can be for instance, employed to build an important sampling algorithm. For instance, in this picture, we were interested, okay, here, all these many, many devices, they want to connect to the base station, there's interference. So the problem is, there's a cocktail party problem.
22:03
If a person wants to speak to another person, but there are many people around, it makes it very hard to form this connection. And we're interested in what is the typical behavior of the system in a situation where you see a certain atypical number of disconnected devices.
22:22
And in this case, you even see a face, a symmetry breaking face transition. So it's also from a purely mathematical point of view, an interesting theory and interesting applications for large deviations within the realm of space time point processes.
22:41
The third method is interacting particle systems on random graphs. This is a quite old theory where you look at Markov processes or maybe beyond Markov processes on fixed configurations. You have a configuration of particles, let's say on a grid, they come in different local states.
23:01
And now we devise exponential rates interacting depending on the behavior of a device and one point depends on the neighbors, for instance. And then we look at the long time behavior of these Markov processes.
23:21
And for instance, in the case that I gave you with the white nights and the infection spreading, we can model this in the framework of interacting particle systems, but now on random graphs. And in some cases, for instance, derive face diagrams
23:41
of global extinction and global survival rigorously in the framework of interacting particle systems. How much time do I have? When did I start? Oh, two minutes, okay. So I was a bit slow, but that's okay.
24:04
Just, okay, maybe I actually, two minutes including questions. Okay, just to give you a flavor, quick flavor of how we deal with these things. So we start with a random process, stochastic process. Typically, if we have no statistical knowledge,
24:22
it's a good idea to start with the so-called Poisson point process. This, you should essentially think of a uniform distribution of points in space. We can create a graph G by just connecting two points that are sufficiently close to each other. And there is a famous phase transition of continuum percolation,
24:40
where I see an infinite cluster emerging. And then we can look at such a Voronoi tessellation. These are all the areas of points that are connected to the infinite cluster. And on the second level, now introduce a time process
25:01
where we associate to every edge a certain passing time. And then we can look at the set of infected devices when we initially have an infection at the origin. We can look at all the devices for which there is a pass where the passing times, the sum of the passing times does not exceed a certain time t.
25:22
So this is the set of infected points at time t. And this is a recent result, which is called a shape theorem. So I will also move.
25:42
We're interested in the limiting shape of the infected region. This is the infected region. We scaled at time t, we scaled by t. And what is indeed true if you put some moment conditions and zero conditions here on the passing time tau, that we see a limiting shape which is in fact the ball
26:04
where the parameter phi is two time points. There is t1, you see a certain region infected
26:24
and at some later time point, you see additional infections in the red area. Yeah, some rescaling results, maybe I skip this. Thank you for your attention.
26:44
Thank you very much for this really interesting talk. Questions? Let me start. You always mentioned random networks. From my little experience, I never saw in reality a random network.
27:01
So you have all some structures. Do you mean Erp-Ishreni or also other kind of random networks? Well, here the randomness, I mean, the simplest case, the randomness enters via the position of the devices in space, the points. And randomness here is, I mean,
27:21
we can have a philosophical question about what is randomness, but enters from an operator's perspective, I have no control on where you move. I mean, I cannot control where you move in space. So I have maybe some knowledge that you have a typical path to your office. But if you look at from a global perspective, I have no clue what you're doing.
27:41
Then this is a different perspective. I call this topology, whether it's randomness or not. This is a bit different than your point, I think. I think it has some structure, the topology. But okay, good, good, then it's clear, thank you. Further questions?
28:04
So if you have such a top network, how do you then solve the network routing problems? Because I guess you cannot solve them in a centralized way. Who passes meshes to whom and on which path? Oh, we don't solve them. We make, for instance, we evaluate expected behavior.
28:22
I see, okay. So the routing takes a random path to the- It's a random path, depending on the configuration of the networks. It's a random configuration. We can say something about the path in this configuration. And then we have a probability distribution and we can make analysis of, for instance, the expected behavior, the unexpected behavior.
28:41
Okay, thank you. Yeah, okay. Maybe a quick question. You talked about motivating people. So how can you incentivize participation in a talk peer-to-peer network for mobile communication? I mean, you have to have your GPS on.
29:02
You have to use data all the time to relay calls or data. How do you incentivize and how do you make sure people don't just make their own system, like what you called Uber-ization, I believe? This is actually an interesting story. One of our older projects
29:22
with this major telecommunication company, they're a bit scared that something like Uber happens to them in the sense that you have, for instance, only in a city. You have this company and they say, well, we don't have infrastructure, but we all sign up for this contract and you can use your cell phone so other people can send their messages via view.
29:43
Actually, such apps exist. For instance, Fire chat played a role in the protests in Hong Kong where the government shut down the infrastructure and then via this app, you can send messages. So for them, really, it's a bit of a threat that all of a sudden this company comes up
30:02
and they basically exist via an app and they provide good network so people will sign up for them and leave there. Their billions worth of infrastructure is useless. So they're actually interested in what is the critical number of people
30:21
you have to have in your business so this actually works. You can have long range connectivity, for instance. So the attraction comes from low cost, I guess, essentially. Yeah, also a bit in the direction of the two questions. If I understand correctly,
30:40
you try to avoid, of course, percolation transitions. Hence, if you speak on good or bad messages. I mean, percolation is good if you want to have connectivity. Okay, good. And then you can give conditions for the companies whether to avoid or to reach. For instance, if it's a one parameter model
31:00
where the only parameter is the expected number of devices per unit square kilometer, then I can rigorously, but also via the simulations, tell them there is a critical point where the system jumps from only being local to being global. Okay, okay, okay. That's interesting, yeah.
31:20
Yep, last question. Hi, I'm wondering about bandwidth problems, like I'm really having the mobile phone users in the back of my mind. So if I order a file from a central server, then I expect the server to have a large bandwidth. But if I kind of take this route
31:42
through all small devices, then maybe somebody just doesn't have a good modem and then it will kind of stop. Yeah, that's true. Okay, cool. Then it's not a question. Was it a statement or was it a question? It was a statement that I could hear.
32:03
Okay, but it's not a right question. I'm not at the point where I can make sense of it. Maybe during lunch, yeah. Maybe you should discuss that. Yeah, thank you. Okay, then thank you very much. We are really at the beginning of a discussion what is the best situation to start the break.
32:20
Thank you very much. Okay. Thank you. Thank you.
Recommendations
Series of 11 media
Series of 26 media
Series of 17 media