Around the Poisson-Voronoi

Point processes play a crucial role in modeling wireless networks with base stations and users. Explore the concepts of Poisson-Voronoi tessellations, homogenous Poisson point processes, and planar random tessellations in the context of network theory. Understand how point processes define the distribution and connectivity of wireless networks based on proximity and spatial arrangement.

• Wireless Networks
• Point Process
• Poisson-Voronoi Tessellations
• Network Theory
• Spatial Modeling

slaza Follow

Uploaded on Mar 13, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. Around the Poisson-Voronoi tessellation Pierre Popineau Network theory reading group 09/06/2021

2. Motivation wireless networks Wireless network with base stations placed at given locations Each user connects to the closest base station Assume that BS are distributed according a point process and users are inside the associated Voronoi diagram 13/03/2025 Poisson-Voronoi tessellations 2

3. Point process Let ( , ,?) be a probability space and (?, ) a measurable space, ? being locally compact and separated. A point process on ? is a mapping : such that: - ( ,?) is a locally finite measure on ?, ? - ?, is an integer-valued random variable, ? defined as follows is a random variable on ( ) the set of locally finite measures on 13/03/2025 Poisson-Voronoi tessellations 3

4. Point process Alternative representation: ? ? = ??? ?=1 Where ? is an integer-value RV and ?? ? are drawn randomly If the ?? are almost-surely different (i.e. ?,? 1 = 1 ? ?), then is simple. If is translation-invariant, it is stationary 13/03/2025 Poisson-Voronoi tessellations 4

5. Poisson point process Take ? = ?, ? 1, with the associated Borel ?-algebra If there exists ?: ? 0, and ? = ?? ? ?? such that: (?)? ?! - For any given ?1, ,?? such that ? ? ?? ??= , the events ?? = ?? are independent ? (?) - ? , ? = ? = Then, is a Poisson point process with intensity measure 13/03/2025 Poisson-Voronoi tessellations 5

6. Poisson point process If ? ? = ?? for ? > 0, then is an homogenous Poisson point process with parameter ?. The homogenous Poisson point process is isotropic and translation invariant. To simulate a homogenous PPP: - Fix a window ? and draw ? ? ? ? - Draw independently, uniformly at random ? points in ? 13/03/2025 Poisson-Voronoi tessellations 6

7. Planar random tessellation Take ? = 2. A tessellation of 2 is a set = ?? such that: - ? ???= 2 - ? ? ?? ??= ?: set of tessellations of 2 A tessellation of the plane can be seen as the surface of a infinite-sized polyhedron 13/03/2025 Poisson-Voronoi tessellations 7

8. Voronoi diagram Let ? ? and x ?. The Voronoi cell of ? in ? is: ? ? = {? ? | ? ? ? ? , ? ?\{?}} The Voronoi tessellation associated with ? is ? ? = {? ? ,? ?} Let be a point process. ? is a random planar tessellation 13/03/2025 Poisson-Voronoi tessellations 8

9. Typical cell vs zero-cell Two objects of interest in a tessellation: - The typical cell: any cell chosen uniformly at random - The zero-cell: the cell containing the origin Palm distribution: probability distribution conditioned on an event happening at the origin 1 0? = ? ? = 1?? ? ?? ???? ? ? ? 13/03/2025 Poisson-Voronoi tessellations 9

10. Typical cell vs 0-cell Two objects of interest: - The typical cell ?: any randomly chosen item in the PV tessellation - The 0-cell ?0: the PV cell containing the origin Define: - ?0 the PP of vertices of with intensity ?0 - ?1 the PP of edge midpoints of with intensity ?1 - ?2 the PP of centroids of with intensity ?2 13/03/2025 Poisson-Voronoi tessellations 10

11. Typical cell vs 0-cell Results of note : - The 0-cell has on average 6 edges - ?0= 2?2, ?1= 3?2 and ?0 ?1+ ?2= 0 (similar to Euler s formula) - -almost surely, no 4 points lie in a circle Typical cell: is a simple stationary point process with intensity ? > 0 =1 ? ? ? What about ?0 ? 13/03/2025 Poisson-Voronoi tessellations 11

12. Typical cell vs 0-cell ??( ) and ? = ?0 ?1 ?2( ) are stationary PP The Palm distribution 0 of ? is equal to: ?? 0? = ??? ? (??) ? ? ? ? 0,1 Let ? be measurable function on ? and ?2= ? ?:? ?2(?) . We define: =?? ?2? ? ? 0(??) ?2 ?2 13/03/2025 Poisson-Voronoi tessellations 12

13. Typical cell vs 0-cell Then: ?2?2 ? ? ?? = ?? 2??2? ??0? ? ? ? + ? ?? 0?? ?0 ? Using a mass transportation argument, for any measurable function ?: ?? 2? ?,? ?? 0?? = ? ?,? ? (??) ? ? ? ? ? 13/03/2025 Poisson-Voronoi tessellations 13

14. Typical cell vs 0-cell With ? ?,? = ??2? ??0? ? ?(? + ?): ?2?2 ? ? ?? = ??2? ? ??0? ? ? ? ? ?? ?0 ? ? ? ? ??2? ? ??0 ? ? ? = 1 iff ? belongs in the 0-cell of ? ? There is only one such ? in each ?, thus: ?2?2 ? ? ?? = ?[? ] ?0 13/03/2025 Poisson-Voronoi tessellations 14

15. Typical cell vs 0-cell With ? 1: 1 = ?2?2 ?? = ?2? |?| ?0 With ? 1/|?0|: 1 ?0 1 ? = ?2= ? |?| Using Jensen s inequality: ? |?| ?[ ?0] Feller s paradox 13/03/2025 Poisson-Voronoi tessellations 15

16. Typical cell vs 0-cell Numerically: ? ?0 1.28?[ ? ] 13/03/2025 Poisson-Voronoi tessellations 16

17. Size distribution of PV cells We have no analytical results around the size distribution of cells. Reasonable results achieved with a generalized Gamma distribution: ? ? ?? ? ?? 1exp ??? ? ? = ? Alternatively: ?? ? ?? 1exp ?? ? ? = 13/03/2025 Poisson-Voronoi tessellations 17

18. Size distribution of PV cells We have no analytical results around the size distribution of cells Heuristic (Ferenc, N da, 2007) for the distribution of ?|?| in dimension ? 1: 3? 1 2 exp 3? + 1 ??? = ?? ? 2 3?+1 2 3?+1 2 Where ? = is the normalisation constant 3?+1 2 13/03/2025 Poisson-Voronoi tessellations 18

19. Size distribution of PV cells We have no analytical results around the size distribution of cells Heuristic for the distribution of ?|?| in dimension 2: 5 2exp 7 ??? = ?? 2? Where ? =343 7 2? is the normalisation constant 15 13/03/2025 Poisson-Voronoi tessellations 19

20. Results around the 0-cell Let ? be any measurable non-negative function (Mecke, 2002): 1 ? ? ?0 = ?[ ? ]? ? ? ? = ?? ? ? ? With ? ? = ??: ?= ??[ ??+1] ? ?0 13/03/2025 Poisson-Voronoi tessellations 20

21. Results around the 0-cell With ? = 1: =?[ ?2] ?[ ? ]= ? ? +Var ? ? ? ? ?0 Link between the CDF/PDF: ? 1 ?0? = ? ? ? ? ?? ? ? 0 3? 1 2 1 ? ? exp 3? + 1 ? ? ?0? = ?? ? ??? ? ? 2 13/03/2025 Poisson-Voronoi tessellations 21

22. Results around the 0-cell Size of the 0-cell with ? = 2: ??0? ?? =9 1 ? 1.28?[ ? ] = ? ?0 7 0 This result is only a heuristic, no analytical result exists 13/03/2025 Poisson-Voronoi tessellations 22

23. Practical example wireless network Assume base stations are distributed according a PPP of intensity ? > 0 and mobile user, to a PPP of intensity ? > ?. Open access: users connect to the closest BS in the network Base stations form a PV tessellation of 2 with parameter ? Assume a TDMA setup: users connect to the same antenna and radio resources are equally shared among all users 13/03/2025 Poisson-Voronoi tessellations 23

24. Practical example wireless network Assume that all users receive the same Shannon rate from their association antenna . Using the stationarity of the PPP resume the analysis to the typical MU located at the origin. ? = 1 + ?0 is the RV denoting the numer of MU sharing the 0- cell The average Shannon rate received by the typical MU is equal to: ? 1 ? 0= ? = ? 13/03/2025 Poisson-Voronoi tessellations 24

25. Practical example wireless network Using the previous results: ? 1 1 ? ?0 ?! ? = ? exp( ? ?0) 1 + ?0 ? + 1 ?=1 1 1 ? ? ?0 = ? ? ?0 = ? ??[1 ? ? ?? ?] 13/03/2025 Poisson-Voronoi tessellations 25

26. Practical example wireless network Using the PDF for ?|?|, we get: 7 2 1 ? =? 1 1 +2 ? ? ? ? 7 This results and heuristics allow us to get rapidly closed analytical forms for moment measure related to PV tessellations. 13/03/2025 Poisson-Voronoi tessellations 26

27. Practical example wireless network With ? = ? (1 ? ? ) 13/03/2025 Poisson-Voronoi tessellations 27

28. References Baccelli, Blaszczyszyn, Karray, Random Measures, Point Processes, and Stochastic Geometry, Inria, 2020 Chiu, Stoyan, Mecke, Kendall, Mecke, Stochastic Geometry and its Applications, Wiley, 2013 Mecke, On the relationship between the 0-cell and the typical cell of a stationary random tessellation, 1998 Ferenc, N da, On the size distribution of Poisson Voronoi cells, 2007 Mankar, Parida, Dhillon, Haenggi, Distance from the Nucleus to a Uniformly Random Point in the 0-cell and the Typical Cell of the Poisson- Voronoi Tessellation, 2019 13/03/2025 Poisson-Voronoi tessellations 28

29. Results around the 0-cell No analytical result for the distribution of ?0, higher order moment measures exist (Mankar et al., 2019) : 2? 2= 4? ? ?0 exp ?? ?1?2,? ?1?2??1??2?? 0 0 0 Where ? ?1,?2,? =? ?1 ?2 2+ ?2 2 ?1 2 2 sin2? ?? ?2 sin2? ?? ?1 2 0 0 2sin2?1 = ?2 2sin2?2 And ?1+ ?2= ? ?, ?1 13/03/2025 Poisson-Voronoi tessellations 29