Temporal connectivity in finite networks with non-uniform measures
Pete Pratt Carl P. Dettmann Woon Hau Chin


1]Pete Pratt
1]Carl P. Dettmann
2]Woon Hau Chin
[1]School of Mathematics, University of Bristol, University Walk, Bristol, BS8 1TW, UK

[2]Toshiba Telecommunications Research Laboratory, 32 Queens Square, Bristol, BS1 4ND, UK
Temporal connectivity in finite networks with non-uniform measures
    [
    December 30, 2023
==================================================================

arabic

Abstract


Soft Random Geometric Graphs (SRGGs) have been widely applied to various models including those of wireless sensor, communication, social and  neural  networks.
SRGGs are constructed by randomly placing nodes in some space and making pairwise links probabilistically using a connection function that is system specific and usually decays with distance. 
In this paper we focus on the application of SRGGs to wireless communication networks where information is relayed in a multi hop fashion, although the analysis is more general and can be applied elsewhere by using different distributions of nodes and/or connection functions.
We adopt a general non-uniform density which can model the stationary distribution of different mobility models, with the interesting case being when the density goes to zero along the boundaries. 
The global connectivity properties of these non-uniform networks are likely to be determined by highly isolated nodes, where isolation can be caused by the spatial distribution or the local geometry (boundaries).
We  extend the analysis to temporal-spatial networks where we fix the underlying non-uniform distribution of points and the dynamics are caused by the temporal variations in the link set, and explore the probability a node near the corner is isolated at time T. 
This work allows for insight into how non-uniformity (caused by mobility) and boundaries impact the connectivity features of temporal-spatial networks. 
We provide a simple method for approximating these probabilities for a range of different connection functions  and  verify them against simulations.
Boundary nodes are numerically shown to dominate the connectivity properties of these finite networks with non-uniform measure. 






§ INTRODUCTION

Since the seminal paper by Gilbert in 1961 <cit.> where Random Geometric Graphs (RGGs) (originally labelled random plane networks) were first introduced, they have been applied to model the spread of diseases, fires and information; in fact even in the original paper wireless networks were proposed as a relevant application.
More recently, RGGs have been used to help model how devices are deployed, and subsequently interact, in wireless sensor networks <cit.>, for example with a mesh architecture where there is no fixed infrastructure and information is transferred in a multi-hop fashion. 
In the classical RGG points are randomly placed in some space and two points form a link if their distance is less than some critical distance r_0 <cit.>. 


The original RGG model was extended by Waxman in 1988 <cit.>,focusing on packet routing in wireless networks to include probabilistic connections, more recently coined Soft Random Geometric Graphs (SRGGs) <cit.>.  
The additional source of randomness produced by the probabilistic connection functions generates a wider array of  applications including neural and social networks  <cit.> and a wider range of communication networks. 


Even for a spatial network where the node locations are fixed, the set of edges can vary with time due to random link failures <cit.> which themselves can often be spatially correlated <cit.>.
For example in a wireless sensor network where the location of nodes remains unchanged, a node may go from being connected to disconnected in consecutive time slots  due to fluctuations in the communication channel.
Thus, it makes sense to talk about both the temporal and spatial features of these networks, herein referred to as temporal spatial networks. 
The impact of these random failures can be mitigated in a very mobile environment as problems of a node being located form a neighbour is very short lived<cit.>; equivalently one can think of the time needed to transmit information, and the time for a node to change its location as having a similar time scale. 
However, in reality retransmissions in smart devices occur on a much smaller time scale compared with human mobility, say; so to  accommodate these different time scales we assume the locations of nodes are fixed throughout time, but connections are made during each time step according to a connection function  independent of the past.
In particular we focus on the local property of node isolation near a corner where the distribution of points is non-uniform (and can go to zero at the boundary) over multiple time slots and explore how these local properties impact the global picture of connectivity. 



The connectivity of SRGGs is closely related to that of  continuum percolation where, unlike it's classical counterpart,  the locations of nodes in the graph are random. 
Early bounds were given in Ref<cit.> on the conditions needed for there to exist a connected component of infinite size (giant component) in a RGG in ^2  by relating the problem to a branching process (lower bound) and bond percolation on the square lattice (upper bound).
For a fixed r_0 there exists a percolation transition where a node goes from belonging to a component of finite size almost surely, to being connected to the giant component with positive probability. 
Various work has focused on improving these bounds discussed in Ref<cit.>, while others have looked at different regimes, for example in sparse communication networks no additional infrastructure is required in two dimensions when devices are well scattered, this is true in one dimension  <cit.>. 
More recent work has focused on local power management (vary the connection range r_0) to achieve connectivity <cit.>, a result extended to Poisson hole networks, (the holes represent regions nodes cannot be, see Ref<cit.>), which model competing cognitive radio networks  <cit.>.
Percolation on SRGGs is less well studied, with some of the more notable work being done on networks where interference is included so a link between any two nodes also depends on the location of other nodes in the network <cit.>.

For networks in a finite domain a more natural 
and stronger condition than that of percolation
is one of full connectivity, P_fc, i.e. when is there a multi-hop path between any two nodes in the network. 
Understanding the bottle neck to P_fc is of great importance in applications of wireless mesh networks, for example where disconnected nodes may represent isolated sensors which hold important information or else dissatisfied customers.
In the classical RGG the transition from disconnected to fully connected occurs when there are no more isolated nodes<cit.>, which are located far from the boundary; a result which was later extended to SRGGs <cit.>.
Interestingly, this work highlights how the local effects of isolation probabilities determine the macroscopic behaviour of P_fc in the limit as the number of nodes tends to infinity and the typical connection range goes to zero.
Similar work has been done on the RGG with a large class of densities in 2 dimensions by Hsing and Rootzen <cit.>, in higher dimensions when nodes are normally distributed <cit.> and when the connection range is location dependent <cit.>. 

In finite networks it is likely that border effects will dominate. 
A cluster expansion approach was utilised by Coon, Georgiou and one of the present authors to show that P_fc can be decomposed into contributions from the bulk and the different types of boundary, where the latter tend to dominate <cit.>.  
This result was extended to a more general class of connection functions showing that boundaries can obstruct P_fc in dense networks <cit.>. 



A feature of wireless mesh networks is that they have no fixed infrastructure as the locations of nodes may vary with time as they move according to some mobility model. 
Simply put, mobility models are a set of rules (usually probabilistic in nature) that describe the movement of nodes. 
The complexity of the mobility model is inversely correlated to its mathematical tractability.
For example, one of the simplest mobility models is a Random Walk (RW), or Brownian motion, where a new direction of travel is chosen at random at each time step, with trajectories of paths being reflected off any boundaries <cit.>. 
The RW is recurrent in dimensions ≤ 2 meaning that a single node explores the whole of the domain <cit.>,  consequently,  a uniform spatial distribution can be used to approximate the mobility of dense mesh network in this case <cit.>.


However, the spatial distribution of nodes is unlikely to be uniform as people tend to congregate around popular places such as city centres and this behaviour can be captured by the stationary distribution of the Random Waypoint Mobility (RWP)  Model <cit.>.
In the RWP model each node moves independently form one another, so it suffices to describe the process of a single node. 
A single node is placed in the domain uniformly at random, chooses a waypoint uniformly at random  and travels toward it in a straight line with a speed taken also from a uniform distribution. 
Once at the destination, the node pauses for some time, taken from some appropriate distribution,  with probability p_T and then selects its next waypoint, independently from the past. 
If p_T = 0 then the density goes to zero along the boundary. The RWP converges to a stationary distribution, with the majority of nodes found within the bulk due to the travelling paths <cit.>.


Networks with other non-uniform measures have been studied, with more recent work focusing on their fractal nature <cit.> where it was shown that the approximation of isolated nodes causing disconnectivity improves in this case <cit.>. 
This in essence suggests isolated nodes in networks with non-uniform measures are "more isolated" than their counterparts in uniform networks.
 

To date there has been little focus on temporal-spatial networks where the dynamics on the network are caused by the probabilistic nature of links, node mobility or both.
One approach is to assume the nodes have infinite mobility resulting in no spatial correlation between time slots, or alternatively fix the underlying distribution of nodes, either way this has largely been focused on the uniform case<cit.>.
When the node locations are fixed, uniformly distributed on the torus (mitigating edge effects by using periodic boundary conditions) and links are drawn during each time slot, connectivity is determined by those nodes which are "highly isolated"   <cit.>.
When the nodes are mobile, and follow a RW in ^d, Ref <cit.> obtained asymptotic results for how long a node takes to connect to any other node in the graph when the connection model is that of the RGG. 

In this work we address the question of  how boundary and non-uniform densities impact the local and global connectivity properties of temporal spatial networks.
Of particular interest in this paper are wireless communication networks, where the random location of points represent mobile smart devices, and the connection functions represent different channel conditions. 
For example, a wireless sensor network is likely to have close range connections due to power constraints so will be closer to the classical RGG, where as communication networks will have longer ("softer") connections derived from an information theoretic standpoint.
The impact of human mobility is approximated by a fixed non-uniform distribution of users, where we assume that the time scale for transmissions is much smaller than that of human mobility. 
An interesting example, which is so far unexplored in the context of full connectivity  with the exception of Ref <cit.>, is when the density  goes to zero along the boundaries, with a motivating example being  the stationary distribution of the RWP with no pause time. 

Although the connection functions are motivated from a wireless networks perspective our analysis is general enough to incorporate connection functions from other literature. 
Finally, we make comparisons between how long one node near the corner is isolated for  compared with how long any node in the network is isolated for which provides an approximation of P_fc in temporal spatial networks. 


The paper is structured accordingly: in Sec <ref> we define the model and introduce the tools required for the analysis; Sec <ref> calculates the isolation probabilities for functions with compact support; Sec <ref> and Sec <ref> provide different methods for calculating isolation probabilities for connection functions with infinite support; Sec <ref> compares approximations with computer simulations and Sec <ref> concludes the paper. 



§ MODEL



 §.§ Network Model

The aim is to understand how boundaries and non-uniformity impact on the global connectivity properties of temporal-spatial networks. 
With this in mind we use a non-uniform Poisson Point Process (PPP) in a triangular region to model the random locations of nodes in the network which represent the locations of people with mobile smart devices.
In particular we focus on a point  located near the corner of the region and study how long it remains isolated from the rest of the network[ is not in the point process since this would break some of our later assumptions. For example, we will sometimes want to choose  such that it is on the boundary, but often we will also choose the density such that it goes to zero at the boundary]. 
The distribution of nodes is generally taken to be non-uniform which is assumed to be a consequence of human mobility.   
In our calculations we assume the node locations remain fixed throughout the process; this can be interpreted as the system having two different time scales: that  of human mobility, and sending a wireless packet, with the latter being assumed to be much smaller.

Another important assumption is that there is no temporal dependence between time slots, that is to say the probability a node is isolated at time T is independent from the past. 


The main metric for discussion will be ℙ_C_T(), which is the probability a node  has made at least one link to another node in the network in any of the previous time steps. 
For brevity our formulas will be written in terms of the complement of the connection probability ℙ_iso^T() = 1- ℙ_C_T(), that is the probability  does not make a single connection in any of the previous time slots  t = 1,2,...T-1, T.

We now proceed by discussing the point process, distribution of nodes, and the connection functions we adopt in the subsequent subsections. 



 §.§ Point Process

Let Φ be a Poisson point process in a region A with non-uniform measure Λ with density λ(r, θ), thus the measure Λ(A) of a set A is given by Λ(A) = ∫_Aλ(r, θ) r  r θ. 
The PPP is defined by the following two properties <cit.>:


  * For all measurable A ⊂^d, the number of points from Φ in A ( denoted Φ(A)) is Poisson distributed with mean Λ(A),

  * Φ(A_i) are independent random variables if A_i are mutually disjoint compact subsets of ^d.

Therefore, the probability the number of points in A is k is,  
ℙ[Φ(A) = k] = e^-∫_A λ(r, θ) r r θ(∫_A λ(r, θ) r r θ)^k/k!
In this paper the region A is a right angled triangle determined by A = {(x,y): 0≤ x ≤ L, 0 ≤ y ≤ x tanϕ}



 §.§ Distribution of points in Φ

To investigate the impact non-uniformity has we choose a general the density to grow away from the corner,
λ(r, θ) = N̅ c r^αg_ϕ(θ),    α≥0

where N̅ is the mean number of nodes in the PPP, c is a normalisation constant such that ∫_A λ(r, θ) r  r θ = N̅ and g_ϕ(θ) can be suitably chosen such that the density  goes to zero on one, both or none of the boundaries. 
One particular example is when  α = 2 and  g_ϕ(θ) = sin(θ)sin(ϕ-θ) which approximates the  stationary distribution of the RWP model near a corner.

To approximate the RWP near a corner of a triangle we assume the spatial distribution can be calculated from three independent one-dimensional processes.
The exact expression for the RWP on the line is provided in  <cit.> ,f_1d(x) = -6/L^3x^2 +6/L^2x,   0≤x≤L

Thus, making use of the above,  the approximation following the relevant transformations can be written as 
f^approx_Δ(x,y)    = f_1d(y) f_1d(x cos(π/2 - ϕ) - y sin(π/2-ϕ))

   ×f_1d((x-L) cos(π/2 + ϕ) - y sin(π/2+ϕ))
Since we  concern ourselves with what happens near the corner for a large domain, we take the leading order expansion for small r = √(x^2 + y^2),  
f^approx_Δ(r,θ) ∼sin(θ)sin(θ-ϕ)r^2 + O(r^3)
So we see that when g_ϕ = sin (ϕ)sin(ϕ-θ) and α=2, eq.(<ref>)  models the RWP model and when α = 0, g_ϕ = 1 we have the uniform case.


When α > 0, even when the domain is taken to be infinite, discussed later,  the expected number of isolated nodes is finite whilst for α≤ 0 this may not be so <cit.>.
Regardless, we are concerned with the isolation probability of a node near the corner, so approximating the domain to be infinite has little impact and only improves tractability; this is discussed further in the following section.





 §.§ Connection Model
 






In this paper we consider a range of connection functions controlling the link probabilities, which we assume to have no temporal dependence[in a more realistic interference model this cannot be assumed<cit.>]. 
In general our analysis holds for a wider range of connection functions that are non-increasing, but we focus on those used predominately found in the wireless literature. 

Let r be the Euclidean distance between two nodes in the point process Φ, and thus let (r) be the probability these two nodes connect. 
Let r_0  be the typical connection range, which is implicit in (r) and can be seen in Table<ref>.
For connection functions with compact support, it is typical that only devices that are closer than r_0 can form a link, however we also provide variations on this in terms of the Soft Annulus and Qausi Disk models, see below. 
For connection functions with global support  r_0 represents how the signal decays resulting in long range connections becoming increasingly unlikely.  
Moreover, r_0 can be thought of as a power constraint on transmitting devices and as such we assume the system size to be much larger than the typical connection range, L ≫ r_0. 
As we consider functions that are non-increasing the significant contributions come from close by which
allows us to take the dimension of the triangle to be infinite, referred to as a wedge (𝒲), exploited in Sec <ref> and <ref>, without losing much accuracy.

To investigate the impact of boundaries we assume the node  is located near the corner, and that || < r_0.

This is to simplify calculations involving connection functions with finite support.  More general calculations are straightforward but cumbersome, and do not provide greater insight.

We define the following seven connection functions in Table <ref>, and discuss the connection functions with compact and infinite support separately below,see Ref <cit.> for more background. 
 


 

  


  §.§.§ Connection Functions with finite support
 
The soft-disk model (SDM) is a variation on the random geometric graph (RGG), introduced in <cit.>.
Two nodes form a link with probability ℘∈ (0,1] if their Euclidean separation r≤ r_0.
The probability ℘ is used throughout this paper to incorporate a temporal aspect into the models with compact support; with ℘ = 1 we have a deterministic model and no temporal aspect, the  case ℘ = 0 is excluded as every node is isolated.
The nodes in Φ (equivalently links) can be thought of as becoming active with probability ℘.
 
The Soft-annulus(SA) model  is a modified version on the SD model where links can only be formed in the interval r  ∈ [r_-, r_+].
Intuitively  this exclusion region  can be seen as a simple channel access scheme ensuring two nodes in close proximity transmit on different channels (thus cannot connect to each other) in order to mitigate interference effects.

The Quasi Disk  (QD) model is the first model we discuss that models the connection probability decaying with distance. 
The QD model is a piecewise connection model that has support on r ∈ [0, r_+] and combines the SD model and one which decays with r; for r ∈ [0, r_-] the connection probability is ℘, whilst for  r ∈ (r_-, r_+] the connection probability decays to zero. 
The factor ℘ is included throughout to ensure (r) is continuous at r_-, whilst the parameter μ is used to tune how "fast" the connection probability decays to zero, with it doing so faster for small values of μ. 
Notice that by taking r_- = 0 the connection probability decays to zero with r, whilst it reduces to the SD model when r_- = r_+.
Intuitively the reader can think of  QD model to represent a connection environment which is clutter free within the ball B(,r_-), whilst the signal decays between r_- and r_+ due to the appearance of obstacles.

Alternatively, the inner ball could model a region where all transmissions are done on separate channels whilst channels are shared in the outer ball creating interference.



  §.§.§ Connection Functions with infinite support
 
One of the  most widely used connection functions in wireless communications (which has a similar analgoue in neral networks  <cit.>) is the probability that the Signal-to-Noise-Ratio (SNR) is greater than some threshold q. 
By modelling the signal as the product of channel gain |h|^2 (an exponential random variable with mean 1 which models the small scale fluctuations in the channel) and  pathloss function r^-η (which models how the signal decays with distance), and taking the noise to be σ^2 one can show that the connection function behaves like a stretched exponential, with a scaling r_0^-η = 1/q σ^2.
More specifically, 
= ℙ[SNR > q] = ℙ[|h|^2 r^-η/σ^2 > q] =exp(- qσ^2/r^-η)
 
Empirical observations have shown that typically η∈ [2,6] in urban environments <cit.>, when η = 2 the signal decays like that in free-space, where as in cities there is less likely to be long range connections due to obstacles thus η will generally be larger.
In highly reflective mediums η < 2. 

The Waxman case, see Table <ref>, is closely related to the Rayleigh  model, where connections are very soft. 
The Rayleigh model reduces to the Waxman model for η = 1, and assuming β = 1. 

The MIMO (Multiple input and multiple output) connection function models the case when  the receiver and transmitter have multiple antennas. 
Due to the limited battery power of mobile devices, the number of antennas is unlikely to be large so we focus on the case when each device has two input and two output antennas, and the channels are assumed to be i.i.d Rayleigh channels.
Work on a more general array of antennas can be found here <cit.>.


  


Finally the last connection function we consider is one that includes interference, where the noise σ^2 is negligible.

Due to links being dependent on the number and  locations of other nodes in Φ,  the network can become highly directional unlike the other models previously discussed; the probability a node  can successfully transmit a message to  is distinct from the probability it can receive a message from .
For simplicity we consider the latter as the interference is measured at the  receiver . 

We proceed by giving the general definition for the connection probability between a transmitter in Φ, _𝒯 = (X_𝒯, θ_𝒯), and receiver _ℛ = (X_ℛ, θ_ℛ), (the receiver is assumed not to be in Φ), with r = |_𝒯 - _ℛ| being the point to point distance of the link.
Denote the interfering nodes in Φ as _ℐ = (X_ℐ, ω_ℐ). 
(r)   =ℙ[SINR > q]

   =𝔼[ℙ[|h_τ|^2 r^-η/ζ ∑__ℐ ∈Φ\_𝒯|h_k|^2 |_ℐ - _ℛ|^-η > q|Φ]]

   = exp(-N̅∫_𝒲 λ(z, ω) z/1+ (z^2 +X_ℛ^2 - 2 z X_ℛ cos(θ_ℛ - ω_ℐ))^η/2/q ζr^η  z ω)

 
In the third equality we have used that the channel gain |h_k|^2 is an i.i.d exponential random variable, and used the PGFL to average over all possible locations of the interferers <cit.>. 
It is often the case that eq.(<ref>) cannot be given in closed form for an arbitrary location of  in finite domains with non-uniform measure.
In section <ref> we will make several approximations to allow for a more tractable analysis. 
 
The interference model is the only connection model that depends on the underlying point process. The other connection models can be thought of as having networking protocols which mitigate the impact of interference, hence the restriction that r_0 ≪ L due to a finite amount of network resources. 




§ ISOLATION PROBABILITIES

In this section we provide three methods for computing the probability a node  is isolated for T consecutive time slots near a corner. 
The first method is applied to connection functions with compact support, whilst the other two are used for connection functions with global support. 
The last two methods can also be applied to those connection functions with compact support and the corresponding discontinuities can be handled separately although these contributions can often be ignored in the small parameter expansions <cit.>. 
We proceed by giving the initial formulation of the analysis, and then consider each method separately in the subsequent subsections. 

The probability that a user  is isolated from all other points in Φ, conditioned on Φ, for T consecutive time steps is,

ℙ_iso^T(|Φ)    =  ∏_∈Φ (1 - (|- |))^T,

By averaging over all possible realisations of Φ, and using the probability generating functional for poisson point processes <cit.>,
G(v) = 𝔼[∏_ζ∈Φv(ζ)] = exp(- ∫(1-u(ζ))Λ(ζ)),
we can write eq(<ref>) as,
ℙ_iso^T()=  exp(-∫_A(1 - (1 - (|- |))^T)Λ())

where the integral is over the triangular region, and Λ is the intensity measure of Φ.
For a single time slot eq (<ref>) reduces to, 
ℙ_iso^T=1()=  exp(-∫_A (|- |) λ()) = e^-M()

where M() is the usual connectivity mass, <cit.>


As an aside, it turns out that if mobility is included between time slots, the average time it takes for  to connect decreases <cit.>.
For example, as a crude lower bound we can consider the case where each node in Φ has infinite mobility,  i.e there is no spatial correlation in the location of nodes from one time step to another,then the probability a node is isolated for T consecutive time steps is simply 
e^-T M().
The probability a node  is connected at time T is the CDF of a geometric random variable with mean  M(), therefore  can always transmit in finite time provided M()>0.
In this model the number of points in Φ during each time slot is a random variable with mean N̅ and can be thought of as nodes randomly turning on/off. 
Alternatively, one could condition on the number of points in each time step by using the Binomial Point Process.

For a fixed stationary distribution of nodes we return to  eq.(<ref>).
Consider the limit as T→∞ for any (r) > 0 with infinite support, in a finite domain A,
ℙ_iso^T() =^T→∞ exp(- ∫_A λ(r,θ) r r θ) = e^-N̅ > 0
The probability that a node  is isolated is always positive, since the probability the point process Φ is empty (e^-N̅) is also positive, a finite domain effect.
A similar analysis holds for connection functions with compact support, but instead  ℙ_iso^T() equals the probability the region where links can be made is empty. 
Consequently, the local mean in/out delay (average time it takes for a node to transmit a packet) is infinite for finite networks. 
This can also be the case for infinite networks where the connection function is (r) = e^-(r/r_0)^η which is a result of the appearance of arbitrarily large voids in the network  <cit.>.

This behaviour can be mitigated in both cases by conditioning on a point being a distance d<∞ away, or in the case of a finite network and unbounded support fixing the number of points. 

We proceed by using eq.(<ref>) to calculate the isolation probabilities for different connection functions expressed in Sec <ref>, starting with those with compact support. 



 §.§ Connection functions with compact support

The method used for calculating the isolation probability (and thus connection probability) for  is very similar for all models (with the exception of the Quasi-disk case which is discussed in Sec<ref>) so we proceed by deriving it for the Soft Disk model, and give the results for the SA model in Table <ref>.

Example: Soft Disk Model

From eq.(<ref>) it is not possible to obtain an explicit expression not in terms of integrals  for ℙ_iso^T when  is located at an arbitrary location in A. 
However, in this paper we concern our analysis with the particular case when = (x, ω) isolated near the corner, and r_0 ≥ x which guarantees that the ball centred at  with radius r_0, B_(r_0), intersects both boundaries and includes the vertex at the origin.   
From these assumptions, and eq.(<ref>) we have, 
ℙ_iso^T((x, ω))    = exp(- (1-(1-℘)^T)∫_0^ϕ∫_0^z λ(r, θ) r r θ)

ℙ_iso^T((x, ω))    = (exp(- ∫_0^ϕ∫_0^z λ(r, θ) r r θ))^(1-(1-℘)^T)

ℙ_iso^T((x, ω))    = V_ℬ(, r_0)^(1-(1-℘)^T)
where z = √(r_0^2 + x^2 - 2 r_0 x cos(θ - ω)), and V_ℬ(, r_0) is the void probability , the probability there is no node in the ball (ℬ(, r_0)) of radius r_0 centred at  in A which is directly computed by setting k= 0 in eq.(<ref>).  
For the uniform case (α = 0, g_ϕ(θ) = 1) the inner integral in eq.(<ref>) is proportional to the size of the region.
For the general case we expand the integrand of eq(<ref>) for small x (≤ r_0) to provide a closed form approximation,

ℙ_iso^T((x,ω))    = exp(-N̅ c(1-(1-℘)^T)(r_0^α+ 2/α+ 2 G_ϕ
   - G_c(ω) r_0^α+ 1 x + G_2(ω) r_0^α x^2 ) )
 
where G_ϕ = ∫_0^ϕ g_ϕ(θ) θ, G_c(ω) = ∫_0^ϕ g_ϕ(θ) cos(θ) θ, G_2(ω) = ∫_0^ϕ1/2g_ϕ (1 + αcos^2(θ - ω)) θ.
At the corner the above reduces to just taking the leading order term.
See Table <ref> for a similar expression for the soft-annulus model.


In the limit as T→∞ we return to the original void probability, for the SA model it converges to the probability the annulus V_𝒜(,r_-, r_+) is empty.
We notice that this type of connection function with compact support results in no guarantee that  connects, even if the PP is non-empty as the relevant connection region might be; trivially this all or nothing type of connection means we need at least the average number of nearest neighbours to be greater than one<cit.>.




 §.§ User Isolation - Method I

In this section we focus on connection functions with global support, and provide a method based on translating the distance between points, since local behaviour will dominate (very long connections are unlikely)  we approximate the domain to be infinite for tractability. 

We first start by writing eq.(<ref>) as 
ℙ_iso^T()    = exp(-∫_0^ϕ∫_0^L/cosθ(z)λ(y,θ)y  y θ),
where the node  is located (in polar coordinates) at (x, ω),^T(z) = (1 -(1-(z))^T)  and  z = √(x^2+y^2 - 2 xy cos(θ-ω)) is the corresponding transformation using the cosine rule. 
By assuming discrete time we can expand the integrand using the binomial theorem,  expand for small radial component x and assume the contributions come from near by so the domain is assumed to be infinite to give, 
ℙ_iso^T()    =  exp(-c N̅ ∑_k=1^T (-1)^k+1 T k  (_k,α+1G_ϕ

   - k 1/r_0 ^'_k-1,α+1x G_c(ω) + O(x^2) ) )

where  G_ϕ, G_c(ω) are as before, 
^(n)_k,α = ∫_0^∞^(n)(y/r_0) ^k(y/r_0) y^α y and ^(n) corresponds to n^th derivative. 

We now proceed by calculating the isolation probabilities for the Rayleigh and Interference connection functions outlined in section <ref> through direct application of eq.(<ref>). 




Example I: Rayleigh Connection Model

First we consider the Rayleigh connection function defined in Table <ref> and through eq.(<ref>) we obtain,

-logℙ_iso^T()/c N̅    = r_0^α+2/ηΓ[2+α/η]H_T,1^2+α/ηG_ϕ

   +  r_0^α+1 Γ[1+α/η + 1]H_T,1^1+α/ηx G_c(ω) +...  


where H_T,β^s = ∑_k=1^T (-1)^k+1T  k k^-sβ^k is the generalised Roman harmonic number given in <cit.>.
Note that we include the constant β for the Waxman case, the result of which is given in Table <ref>.
Using an asymptotic approximation provided in <cit.>, we can approximate the isolation probabilities for large T, where γ is the Euler-Mascheroni constant, 
H_T^s≈(logT)^s/s+γ(logT)^s-1 + (6 γ^2 + π^2)(s-1)/12(logT)^s-2 + ...

This provides a good match when s ≤  which implies for more cluttered environments (higher value of η) the approximation improves; for s = 1 we obtain the standard harmonic number.
The above approximation can be rescaled to include a constant β by replacing log T with log(β T).

Conversely, when α + 2/η is large, we have,
∫_0^∞(1-(1-e^-z)^T)z^α+2/η - 1z    ∼T Γ[α+2/η]

This is a useful approximation for a very inhomogeneous network (or a highly reflective environment) and suggests the isolation of nodes after time T slots behaves like exp(- constant T). 
When η =1 (Waxman model) the above provides a good approximation, particularly for the RWP distribution. 
Remark: The exact transition behaviour between the two regimes is more subtle and not studied here.




Interference

In Sec.<ref> we introduce the interference limited connection function for a node with a general location in A. 
A tractable form of  (not expressed in terms of hyper geometric functions) is only possible for the specific case when  is located at the corner and the domain is assumed to be infinite (Wedge). 
(r)    = exp(-∫_0^ϕ∫_0^L/cosθ (1 - 1/1 + q ζr^η/z^η)λ(z,θ)zz θ)

   =^(*) c N̅s^2+α/ηπ/η((2+α)π/η)G_ϕ

   = c N̅ G_ϕc_ℐ r^2+α
where * denotes we have assumed an infinite wedge, c_ℐ =  (q ζ)^2+α/ηπ/η((2+α)π/η)  and we require α + 2 < η to hold. 
The condition that α + 2 < η  ensures that there is indeed positive probability of connection; there exists a phase transition at η = dimension such that for η≤ dim the global behaviour begins to  dominate and the aggregate interference causes disconnection.
Since we assume an infinite wedge, which has an infinite number of nodes, we need to ensure the  local behaviour dominates, hence α + 2 < η.
Consequently, for the RWP case we need η > 4; i.e a "very" urban environment like a large city such as New York.
Alternatively we can make the approximation that all non-negligible interference comes form all those devices within a distance r_ℐ which allows for the relaxation of the α+2 < η restriction;  but yields a connection function in terms of hyper geometric functions which leads to an intractable calculation later; see <cit.> amongst others on approximating interference.



When the node is located near the corner we can compute the approximation through method I or II (outlined in the next section).
For method I we approximate the connection probability at x to be the same as at the vertex a the origin such that we can apply eq(<ref>), noting r_0 = 1, to get 

-logℙ_iso^T()    =H_T/(2+α)c_ℐ

   +(c N̅)^1/2+α/(c_ℐ G_ϕ)^1+α/2+αΓ[3+2α/2+α]H_T^1+α/2+α x G_c(ω) + O(x^2) 

where H_T^s is the Roman harmonic number defined earlier and H_T is the usual harmonic number with asymptotic expansion
 H_T
   =  logT + γ+ 1/2T - 1/12 T^2 + O(T^-4)
 
The leading order term in  eq.(<ref>) is independent of the density of users and the angle of the wedge. 
This is consistent with the results in <cit.> which highlights how any increase in signal power due to proximity is counter balanced by an increase in the interference field.

However, the second term (first order correction term) scales like N̅^1/2+α and does in fact depend on both the geometry of the wedge and the density of users, ultimately leading to  lim_N̅→∞ℙ_iso^T() →ℙ_iso^T(0).
Intuitively this is because in the high density limit[this is only true for our particular choice of path loss model <ref> <cit.>],  the local picture for each node looks the same due to the scaling of power and interference which means connections are dominated by local nodes ( assuming α +2 < η). 


 §.§ User Isolation - Method II

In this section our aim is to give an alternative approach to Method I which provides greater tractability and  is more suited to more complicated connection functions (r).
As such,this method, Method II, is more suited to more complicated connection functions such as MIMO or those outlined in <cit.> where closed form expressions cannot be obtained via method I, or else the computation of the higher order moments of the connection function are time consuming.   
For a non-increasing connection function (r) with global support the approximation can be expressed as a combination of one-dimensional integrals which are quick to numerically compute.
In this analysis we require the  density to go to zero along the top border, which is akin to the RWP case or other mobility models where boundaries are left largely unexplored. 

In this section we will consider the user located on the bottom boundary, = (ξ_x, 0), and divide the domain into three regions M_A, M_B and M_C, see Fig.<ref>, such that, 
ℙ_iso^T(= (ξ_x,0))   = exp(-(M_A + M_b + M_c)) 

To obtain an expression for a user located near the corner, but not on either boundary, we can combine two triangular domains together along the non-zero boundaries to obtain  ℙ^T_iso[ξ_x,ω]. 
In general the two triangular regions not be identical, but we assume so merely for brevity.
We now proceed to calculate each of the contributions from these sub-regions using eq.(<ref>), starting with M_A . 


  §.§.§ Region M_A

The region M_A, as shown by the purple region in Fig<ref>, has a transformed polar coordinate system centred at (ξ_x, 0). 
For this case we use the cosine rule to make the necessary transformation of the density.
M_A    =∫_0^ϕ ∫_0^(L- ξ_x)/cosθ ^T λ(z, ω̂) y y θ̂

   =∫_0^∞^T(y^α+1G_ϕ+(α+ 1) y^αG_c(0) ξ_x + ... ) y

where z = √(y^2 + ξ_x^2 - 2 y  ξ_x cos(π- θ̂)), ω̂ = arcsin[y sinθ̂/√(y^2 + ξ_x^2 + 2 y ξ_x cosθ)] and  ^T = 1-(1-(y))^T. 
In the above, we have expanded for small ξ_x and  assumed an infinite wedge. 

In fact the main contribution arises form the region M_A as we will see in the following subsections as  the contributions form other regions are of order ξ_x^2.


  §.§.§ M_B

The region M_B is coloured yellow in Fig<ref> and has a translated and rotated coordinate system (x̂, ŷ). 
Throughout this section, since the function g_ϕ(θ) goes to zero near the border we approximate ŷ as small. 
The connection function can therefore be approximated as, 
(√(x̂^2 + ŷ^2))^k      ≈^k(x̂)+k/ x̂(x̂)^k-1^'(x̂)ŷ^2+...


Using this approximation, and assuming the discrete time so we can rewrite the integrand as a sum, we have that the contribution from the region M_B is, 
M_B    = ∫_M_B(|- |)^T λ(y,θ) yy θ

   ≈N̅cg_ϕ^'(ϕ)/2 ∑_k=1^T T k(-1)^k+1ξ_x^2sin^2ϕ_k,α-1(x̂)+ o(ξ_x^2) 


We notice immediately that the leading order term is indeed of order ξ_x^2 which we will neglect from our final approximation.  



  §.§.§ M_C

For the M_C region, neighbouring nodes are close by so we approximate (r) ≈ 1, and we observe that the contribution is proportional to the size of the region, 
M_C    = ∫_0^ϕ∫_0^ξ_x cosϕ/cos(ϕ+θ) (1-(1-(r))^T)λ(r,θ)rrθ

   = ∫_0^ϕ∫_0^ξ_x cosϕ/cos(ϕ+θ) ^T(r) λ(r,θ)rrθ

   ≈N̅ cξ_x^2+α/2+α ∫_0^ϕg_ϕ(θ) (cosϕ(θ-ϕ))^2+α θ
In fact the best case scenario (in this particular model) is for the uniform distribution,where  α = 0, and g_ϕ(θ) = 1 leaving, 
M_C = N̅ c sin(2 ϕ)/4ξ_x^2
By combining the contributions from each region and taking terms up to order ξ_x the probability a point located along the border is isolated can be written in terms of the following simplified 1-dimensional integral,
-logℙ^T_iso[(ξ_x,0)]/c N̅   ≈∫_0^∞ ^T (r^α+1 G_ϕ+(α+ 1) G_c r^αξ_x+...)r , 

We now have the integral in the form, with a change of variables, 
I(s) = r_0^s+1∫_0^∞ (1- (1- (r))^T)r^s r
and for the asymptotic approximations we need only expand once for large T and we are done.
This method provides a greater tractability since it involves computing only one integral (albeit with different parameters s), and for large times often an asymptotic approximation can be found. 


We now proceed by computing the isolation probabilities for the MIMO and Quasi-disk connection functions. 


Example: MIMO

For the MIMO connection function we apply eq. (<ref>) directly.
-logℙ_iso^T()/N̅c    =
r_0^α+2G_ϕ/η ∫_0^∞ ^T r^α+1 r

   + (α+1)r_0^α+1 G_c  ξ_x/η ∫_0^∞ ^T r^αr 

   =r_0^α+2G_ϕ/η I_1(α+2/η)

   + (α+1)r_0^α+1 G_c ξ_x/η I_1(α+1/η)

where the integral is I_1(s) = ∫_0^∞ (1 - (1- e^-x(2 + x^2 - e^-x)^T)x^s-1 x.
First we consider the case when α is large (equivalently s large); and T small in comparison, we can get a simple expression for the asymptotic behaviour. 
I_1(s)   =∫_0^∞(1 - ( 1- e^-x(2 + x^2 - e^-x))^T)x^s - 1 x

   ∼2 T Γ[s] + T Γ[s+2] - T2^-sΓ[s] 
For  s ≤ 1, which will often be the case, we can do a similar asymptotic expansion to <cit.> by splitting the integral up at ĉlog T, where ĉ is a constant. 
I_1(s)    = ∫_0^∞(1 - ( 1- e^-x(2 + x^2 - e^-x))^T)x^s-1x

    = ĉ log^s T/s + (log[T^1-ĉ(ĉ log[T])^2] + γ) (ĉ log[T])^s-1

   + (6γ^2 + π^2 + 12γlog[T^1-ĉ(ĉ log[T])^2]

   + 6(log[T^1-ĉ(ĉ log[T])^2])^2)(s-1)/12(ĉ log[T])^s-2+...


This method provides a good approximation [This is used more as an illustrative example and a better approximation can be found if more care is taken on how to split up the integral which will depend on both α and η.] provided s = α + 2/η≤ 1and T > 10. 

Example II: Quasi Disk Model
The quasi-disk model (Sec. <ref>)  is a piecewise connection function  which can model a change in channel conditions; for example transitioning from a clutter free environment to a cluttered one. 
In general, assuming a soft-disk model transitioning to a decay function one at r_-, through application of eq.(<ref>) we obtain, 
   -logℙ_iso^T()/N̅c̅ = (1- (1-℘)^T) ∫_𝒲 ∩B_(r_-)r^α+1g_ϕ(θ)r θ

   +∫_𝒲 ∩𝒜_(r_-,r_+)(1-(1-℘+℘(r-r_-/r_+- r_-)^μ)^T)r^α+1 r g_ϕ(θ) θ



We can use the previous result for the soft-disk model (see Table <ref>) for the first term on the right hand side in eq(<ref>).
The second term, (denoting the inner radial integral as I_radial) can only be given in semi-analytic form using the previously outlined methods when ≠ 0.
That is to say we are left with an integral of the form  ∫_0^ϕ g_ϕ(θ)(..._2 F_1 (a, b;c;ξcosθ)) θ, where _2 F_1 (a, b;c;z) is the Gauss hypergeometric function,  which cannot be computed. 
For simplicity we focus on the case when μ = 1 and let r_+ = κ r_-.
From method II we need to compute the radial integral 
I_r(α+1)   = ∫_r_-^κr_-(1-(1-℘+℘(r-r_-/r_+- r_-)^μ)^T)r^α+1 r 


Through direct calculation of the integral in eq.(<ref>), 
I_r(α+1)    = r_-^2+α/2+α(κ^2+α - 1 + (1/Δ(1 - κ))^T

   ×(ψ(T, α, ℘Δ) - κ^2+αψ(T, α, κ℘Δ) )) 

where ψ(T, α, Δ) = _2F_1(-T;2+α;3+α;Δ), Δ = 1/1 - κ(1-℘) and κ≠1/1-℘ so Δ≠ 0.
For the case when κ = 1/1-℘ we use the following limit, 
lim_c→0 c^T(-1)^T _2F_1(-T, a, b, 1/c) = Γ[b]Γ[a+T]/Γ[a]Γ[b+T]
We now directly use the above result to give I_radial when κ = 1/1-℘, 
I_r(α+1)   = r_-^2+α(κ^2+α-1/2+α+ ℘^T(1-κ^2+α+T)/(2+T+α)(κ-1)^T)G_ϕ
We can now use method II to provide a general approximation for I_radial(α+1)
-logℙ_iso^T(ξ_x)/c N̅    =(1-(1-℘)^T)(r_0^α+2/α+2G_ϕ+ F_c r_0^α+1 ξ_x )

   + I_r(α+1) G_ϕ + (α+1)I_r(α) F_c ξ_x

In the limit as T→∞ the probability of connection converges to the void probability for the ball of radius κ r_-. 
lim_T→∞ℙ_iso^T() →V_ℬ(,κr_-)

We remark that the quasi disk can be defined such that it has an exponential decay function and the analysis is very similar to that above, the major difference being that the integral I_r(α) is expressed in terms of Roman harmonic numbers rather than hypergeometric functions. 


 





§ NUMERICS




 




Firstly, the approximations provided in the previous sections, included in Table  <ref>, are a good fit for the simulated data points, see Fig<ref>.
One general observation (all connection functions expect for the interference case) is that the probability of connection tends to its maximum much faster for larger N̅ (similarly for larger r_0 or smaller α) as the local neighbourhood becomes increasingly dense. 
For the interference model the change in connection probability is much smaller as the density changes since only the second term depends on N̅, a result of the trade-off between connectivity and interference, and as nodes are added to the network the probability of connections are counter balanced by the increase in interference field. 





 §.§ Connection functions with compact support

For connection functions with compact support the probability  is connected tends to the  complement of the void probability and is represented by the dashed lines in  Fig<ref>.
That is to say, the limiting behaviour is restricted to there existing a node within the connection range, i.e the void probability which is characterised by the PPP Φ and r_0, r_-,r_+. 
Such connection functions are employed in the modelling of wireless sensor networks, and an easy way to ensure connectivity  is to enforce an underlying structure to the network (lattice) so that the maximum distance between any two sensors is at most r_0.
However, in dense networks (or equivalently when the typical connection range is large)  where devices are located predominately within the bulk, it is likely that a lattice structure is not needed and will only waste resources. 
Our results highlight how the boundaries, along with inhomogeneities, significantly decrease the connection probability.
For example, if r_0 = 1; L = 10; ϕ = π/2 then the mean degree when α = 0 is ≈ 0.407 compared with    ≈ 0.003 when α = 2. 
As a result, in networks that exhibit such behaviour it is likely nodes need only need be added near the boundary to ensure connectivity. 


 §.§ Connection functions with global support

For connection functions with infinite support we see that the probability approaches the complement of the probability the PPP is non-empty, see section <ref>, and does so faster for a larger r_0, N̅ and smaller α. 
This behaviour is a finite domain effect, and if we condition on there being at least one point in the PPP (or else use a Binomial Point Process), then 
ℙ[C_T] →^T→∞  1 . 
For both the Rayleigh and MIMO cases the asymptotic expansions work well for large T, and improve when the path-loss exponent η increases (the signal decays faster), or the distribution of points becomes more uniform. 
For the MIMO case a better approximation can be provided for specific α, η but it is unclear how to improve it for the general case. 
However, as the probability for long links increases, such as in the Waxman case, the usefulness of the large T approximation is limited to the uniform case, but for the non-uniform case the approximation for very inhomogeneous networks works well.  

The connectivity of infinite networks are obstructed by corner nodes, provided some assumptions on the density that it grows away from the corner, α>0.
If however, the PP is uniform, or even if α < 0 then  the network may never connect, you may have infinitely many isolated nodes <cit.>.



 §.§ Full connectivity

In static networks P_fc is defined as there existing a multi-hop path between any two nodes in the network. 
In a temporal network this is more complicated since there exists a network with directional (causal) paths between nodes.
We introduce a weaker sense of full connectivity, that is the probability that every node in the network has made at least one link to some other at, or prior to, time slot T; we will denote this as P_fc^T.    
Analogous to other work, we want to make use of there being no isolated nodes to approximate that of P_fc^T. 
Indeed, focusing on the idea that boundary nodes are likely to be "more isolated" we see that nodes near the corner are the last to connect when links are independent,see Fig<ref>. 
Naturally, when considering interference this behaviour is not necessarily true since nodes near the bulk may be in outage if the interference field is to high; in fact the boundary may help connectivity due to a decreased interference field. 
Essentially, we have shown in Fig<ref> that the time for every node in the network to form a link is determined by how long the highly isolated nodes take to form a link. 
Furthermore, provided the network is dense enough and α⪆ 1 then it is likely the first causal path occurs from any node in the network to a boundary node when the boundary node makes a single connection.  

For infinite networks with non-uniform measure isolated nodes are likely be play a more significant role for P_fc <cit.>. 
For example, if α≤ 0 then the the number of isolated nodes is infinite, and thus P_fc = 0 can never be achieved, whereas when α > 0 the behaviour is likely to be determined by highly isolated nodes <cit.>.




§ CONCLUSIONS




In this paper we look at the impact local geometries and non-uniform densities have on wireless networks, and show those nodes near the corners dominate the global connectivity properties of the network, especially when the local neighbourhood is sparse. 
The location of nodes were modelled by a non-uniform Poisson Point Process in a triangular domain, and links were formed during each time slot, independently from the past, based on a probabilistic connection function that depended on node separation. 
The time for information to flow through the network was assumed to be much less than the time scale for mobility, thus we could assume the location of nodes to be fixed (albeit not uniformly distributed).
More specifically, two methods were provided for calculating the probability a node near the corner was isolated at time T for a general connection function, where some examples were given from the wireless literature. 
The first method was used to generate closed form expressions for general densities r^α g_ϕ(θ) (not necessarily vanishing at the borders) which required calculating the higher moments of the connection function.
For more complicated connection functions (where the higher order moments were not integrable, easy to calculate or did not provide closed form expressions) a second method was proposed in order to reduce the number of integrals that needed to be computed.
The latter required that the density went to zero along one of the boundaries, which was not a requirement in the first method. 
For all the connection functions discussed in this paper we provide asymptotic approximations for large T and/or large α and show they are a good fit compared with simulations.
Furthermore, we also provided an approximation for full connectivity that it is those nodes near the corner (and with few close neighbours) that are highly isolated that are the main obstacle.
This naturally assumes that nodes within the bulk have made multiple connections in the previous time slots and thus any information has flowed through the rest of the network.  

Although the examples given in this paper are from the wireless literature they can easily be extended to different connection functions. 
 

This work can provide insight into the demand for future network design, for example smaller access points (small base stations as those required for the deployment of 5G networks) should be deployed near boundaries or regions of low density to  ensure connectivity. 
In general, the properties of isolation near the boundaries in networks with non-uniform measure could in theory be exploited to halt the spread of forest fires, or disease, where border nodes represent a bridge between networks with high betweenness centrality. 


In this paper we assume a static distribution of nodes but it would be interesting if the locations of receiver nodes vary with time according to some mobility model and how this impacts on the global connectivity of the network.
Future work could also include finding an effective method to approximate the number of connected subgraphs in finite networks with non-uniform measure. 
This would allow a deeper understanding into the transition from disconnected to a fully connected network. 
A closed form expression involving multiple integrals can be derived using the theory of point processes but approximating the expected number of clusters of a particular size remains open; even for the case of isolated nodes  with non-uniform measure.
This is of particular interest since it has been recently shown that the property of disconnection beings more heavily coupled with that of isolated nodes when the density is non-uniform <cit.>. 




§ ACKNOWLEDGEMENTS

The authors would like to thank the directors of the Toshiba
Telecommunications Research Laboratory for their support.
This work was supported by the EPSRC [grant number
EP/N002458/1]. In addition, Pete Pratt is partially supported
by an EPSRC Doctoral Training Account.



ieeetr
	
