Relay-assisted Device-to-Device Networks: Connectivity and Uberization Opportunities
Quentin Le Gall Bartłomiej Błaszczyszyn Elie Cali Taoufik En-Najjary






Relay-assisted Device-to-Device Networks: Connectivity and Uberization Opportunities



    Quentin Le Gall12, Bartłomiej Błaszczyszyn2, Elie Cali1 and Taoufik En-Najjary1
1Modelling and Statistical Analysis, Orange Labs Networks, Châtillon, France

Email: quentin1.legall@orange.com, elie.cali@orange.com and taoufik.ennajjary@orange.com
2Inria-ENS, Paris, France
Email: quentin.le.gall@ens.fr, bartek.blaszczyszyn@ens.fr
    Received 27 September 2019; accepted 25 May 2020; published 1 July 2020
==============================================================================================================================================================================================================================================================================================================================================




It has been shown that deploying device-to-device (D2D) networks in urban environments requires equipping a considerable proportion of crossroads with relays. This represents a necessary economic investment for an operator.


In this work, we tackle the problem of the economic feasibility of such relay-assisted D2D networks. First, we propose a stochastic model taking into account a positive surface for streets and crossroads, 
thus allowing for a more realistic estimation of the minimal number of needed relays.


Secondly, we introduce a cost model for the deployment of relays, allowing one to study operators' D2D deployment strategies. We investigate the example of an uberizing neo-operator willing to set up a network entirely relying on D2D and show that a return on the initial investment in relays is possible in a realistic period of time, even if the network is funded by a very low revenue per D2D user. Our results bring quantitative arguments to the discussion on possible uberization scenarios of telecommunications networks. 



Device-to-device networks, relays, cooperative networks, cost model, uberization




§ INTRODUCTION

With the exponential increase of connected devices and users' intensive data demand comes the need for new ways of thinking the future cellular networks. In this regard, Device-to-Device (D2D) communication has been identified as a key component of the fifth generation (5G) of mobile networks <cit.>. In particular, by taking advantage of the densification of networks, 
D2D opens the way to cooperative networks and crowd-networking scenarios <cit.>. 

Over the recent years, many areas of the economy have shifted towards service-based peer-to-peer business models, a process also known as uberization. In this context, the challenge of crowd-networking aided by D2D seems of critical importance for telecommunications operators.

To investigate such possibilities, mathematical models of D2D networks, more amenable to predictions and numerical simulations, have recently been introduced. 

In 5G networks, the main part of the useful spectrum consists of very high frequencies <cit.> allowing only for line-of-sight (LOS) communications.  In urban environments this requires signal relaying at crossroads to ensure connectivity between adjacent streets,  a situation  often called canyon  shadowing. In <cit.>, using 
a simple stochastic percolation model, the authors have shown that large-scale connectivity requires at least 71.3% of crossroads equipped with relays. However, the chosen  models for streets and users resulted in a zero probability of having a user located at a crossroad. In real life, one can yet expect some part of the relaying to be performed by D2D users themselves present at crossroads.

In order to get a more realistic estimate of the minimal number of relays needed for connectivity, we introduce new geometric models taking into account the surface of crossroads. Then, we introduce a related deployment and operational D2D network cost model, allowing one to study plausible uberization scenarios of telecommunications networks through D2D. 



The main results of this paper are the following ones:
Taking into account the possible presence of users at crossroads, we considerably reduce estimates of the minimal number of required relays. Based on our economic model, we show that a favorable return on investment is possible for an uberizing neo-operator relying on D2D only to construct its network. 







The rest of this paper is organised as follows: We begin by recalling related works in Section <ref>. Then we present our D2D connectivity  model in Section <ref>, the details of the  mathematical derivation of the geometric properties of our  crossroad models being presented  in the Appendix. The economic model for D2D costs deployment and uberization strategy is introduced in Section <ref>.
Finally, our results are presented in Section <ref> and concluding remarks are given in Section <ref>.





§ RELATED WORKS


Mathematical models of ad-hoc networks based on stochastic geometry tools go a long way back and have been introduced with Gilbert's pioneering work <cit.>. Since then, refinements of this original model taking interference into account <cit.> have extensively been studied. The importance of the underlying geometry in mathematical models of ad-hoc networks has yet only been recently considered, based on statistical procedures proposing tools for the fitting of street systems by random tessellations <cit.>. In light of these developments, a mathematical model of D2D networks with particular attention to the modelling of geometric features and of the street system has been introduced in <cit.>. As a refinement, the impact of canyon shadowing 
has been modelled and studied in <cit.>. 

Performance analyses have shown that, thanks to D2D relaying, a significant coverage extension and an enhanced quality of service (QoS) can be achieved <cit.>. 
Regarding cost considerations, energy efficiency and energy costs of D2D networks are a key topic of research <cit.>. For instance, optimization of power allocation in underlay D2D has been studied in <cit.>. Mechanisms for optimisation of resource costs <cit.> have also been proposed. However, all the aforementioned works do not consider the problem of connectivity and start from the assumption that connectivity of the network is already established. Moreover, to the state of our knowledge, our work is the first of its kind to investigate the use of D2D in uberization scenarios with an economic perspective. 
 





§ CONNECTIVITY MODEL DESCRIPTION


We first recall the D2D network model in a canyon shadowing urban scenario introduced in the previous work <cit.>. Then, we present our new modelling of crossroads taking into account a possible population by D2D users.


 §.§ D2D network model


In <cit.>, a stochastic model for a D2D network in an urban scenario with the canyon shadowing assumption was introduced. The model consists of three fundamental layers:  
    
  * Streets of the city are modelled by a random tessellation <cit.> S, chosen to be a Poisson-Voronoi tessellation (PVT). The average total street length per unit area, expressed in km/km^2, is denoted by γ. Other choices of tessellations can also be considered <cit.>. 
    
  * Nodes of the network consist either of D2D users equipped with mobile phones or network relays. On the one hand, D2D users are distributed on the edges of S (i.e. streets of the city) according to a Cox point process <cit.> X with linear intensity λ, expressed in km^-1. On the other hand, relays are placed on the vertices of S (i.e. crossroads of the streets) according to a Bernoulli point process Y <cit.> with parameter p ∈ [0;1]. The point processes X and Y are also assumed to be independent conditionnally to the realisation of S. Contrary to previous models (e.g. <cit.>) where relays are modelled as an independent Poisson point process (PPP), the random support for streets and the canyon shadowing assumption require resorting to a Bernoulli model for relays.
    
  * The D2D communication range is assumed to be a global constant r>0, expressed in km. Two nodes of the network (either D2D users or network relays) can communicate by a D2D link if and only if they are in line-of-sight (LOS), i.e. located on the same street of S, and the distance between them is less than r.


In the aforementioned model, several assumptions have been made. First, the communication radius r is considered to be a global deterministic constant, as in <cit.>. This implies that the D2D users and the relays are assumed to all have the same transmission power. Moreover, note that interference phenomena and user mobility are neglected, for the sake of simplicity and mathematical tractability. In terms of relaying technique, physical and medium access technicalities (e.g. as covered by <cit.>) are out of the scope this paper. 

In what follows, parameters of interest will be p, λ and r. We will consider γ as a fixed characteristic given by geographical location. A typical value for a classical European city centre is γ = 20  km/km^2.
 
The previous construction gives rise to a random connectivity graph 𝒢_p,λ,r which symbolises the network. Good connectivity is then mathematically interpreted as percolation of this graph, i.e. the existence of an infinite connected component with positive probability. 








 §.§ Modelling of crossroads



  §.§.§ Crossroad surface


The street system S being a PVT, the degree of each crossroad is almost surely equal to 3 <cit.>. Therefore, a typical crossroad,
when  centered  at the origin,
can be represented by the dashed lines (d_1), (d_2) and (d_3) of Figure <ref>, with (not necessarily equal) angles α,β,δ being random variables.



We then propose the following approach for the modelling of the typical crossroad: we prescribe a positive width l>0 (expressed in meters) for each street
and  imagine some geometric figure 
of non-null area (called in what follows crossroad), where a D2D user can serve as a relay between the three  adjacent streets. In order to simplify the derivation of the formula for the typical crossroad surface,  we propose two scenarios: one where the crossroad  is defined to be the triangle delimited by the intersections of the streets limits (surface 𝒮𝒮(l,α,β) of the triangle ABC
on  Figure <ref>), and one where the resulting surface is the circumcircle of this triangle (surface 𝒮'𝒮'(l,α,β) on the same figure). Note that compared to all possible locations of relays, the first scenario corresponds to a small crossroad surface and the second to a large crossroad surface. The mathematical derivation of formulae for 𝒮(l,α,β) and 𝒮'(l,α,β) is presented in the Appendix. 


 
 

















  §.§.§ Typical crossroad occupation probability

We now compute the probability that the typical crossroad is occupied, either by a physical relay or a D2D user. Denote by  𝒜𝒜(l,α,β) the surface of the crossroad (either 𝒮 or 𝒮' in Section <ref>).
Using the conditional independence of users and relays given the street system 
and the Bernoulli model of the relays in the D2D network model in Section <ref>, 
we pose:

    ℙ(typical crossroad is occupied)   := 1-ℙ(no user in 𝒜)× (1-p).
 
Moreover,  since the linear intensity λ  of users in the Cox process of  
the D2D network model in Section <ref> 
is  equivalent to a surface density  λ / l in our  model where streets have width l>0, we pose:

    ℙ(no user in 𝒜):=𝔼[e^-λ/l𝒜(l,α,β)],

where α and β are random variables and denote the angles spanned by the streets of the typical crossroad of the PVT S. To compute the expectation in (<ref>), we use the joint probability density for the random vector (α,β) (note δ=2π-(α+β)) 
 computed by Muche <cit.>:

    f(α,β)=-8/3πsinαsinβsin(α+β), 
    with  0<α<π, π-α<β<π.






Therefore, the crossroad occupation probability is given by:

    F(λ,p,l):=ℙ(typical crossroad is occupied) 
     =1-(1-p)∫_α=0^π∫_β=π-α^π e^-λ/l𝒜(l,α,β)f(α,β)dβ dα,

where (α,β)↦ f(α,β) is the joint density given by (<ref>) and 𝒜(l,α,β) is the resulting crossroad surface, either 𝒮(l,α,β) or 𝒮'(l,α,β) according to the chosen modelling.



Figure <ref> shows the plotting of the occupation probability of the typical crossroad F(λ,p,l) as a function of the user density λ and the physical relay proportion p, in an example when the crossroad resulting surface is the circumcircle area and the street width l is equal to 20 meters, a typical value for a classical European city centre, estimated via statistical methods suggested in <cit.>.



 §.§ Minimal relay proportion



















Using our new model taking into account the possible population of crossroads by D2D users or physical relays, 
we define the minimal proportion  of physical  relays needed to ensure large-scale connectivity of the D2D network as follows: 

    p_c(λ,r) inf{ p ∈[0,1],  𝒢_F(λ,p,l),λ,r percolates}

where, recall, percolation means    existence  of  an  infinite  connected component with positive probability.
This quantity p_c(λ,r) represents the necessary investment in relays for operators, given the D2D user density and the D2D technology. p_c(λ,r) can be calculated using the estimation  of the  minimal  proportion of occupied crossroads   
    p^*(λ,r) inf{ p ∈[0,1],  𝒢_p,λ,r percolates}

originally defined and estimated in <cit.> by taking p_c(λ,r)=min(1,max(0,p)), where p is the (unique)  
solution of the equation

    F(λ,p,l)=p^*(λ,r).





§ ECONOMIC MODEL DESCRIPTION

We now introduce a cost model for the deployment of relays in a relay-assisted D2D network. This in turn allows us to introduce the uberization strategy of a neo-operator willing to set up a network by entirely relying on D2D technology.



 §.§ Cost model


Relevant parameters of our cost model for the deployment of a relay-assisted D2D network are presented in Table <ref>. In particular, regarding the costs of relays, two types of costs are to be paid by an operator:
 capital expenditures (CAPEX) per relay (c_CAPEX) and  operational expenditures (OPEX) per relay, per year  (c_OPEX) (covering maintenance, energy, etc.), to be taken into account during network's exploitation.
Due to the fact that relays depreciate over time, we consider a relay depreciation period T_DEP of years, after which relays will successively be replaced. 








Regarding the operator's revenue on the use of its D2D network, several sources  are possible. For instance, the use of the D2D service can be billed to users as a monthly subscription fee. Another source of revenue for the operator can consist in funding the deployment of its D2D network by advertisement. For simplicity, we do not take into account the nature of the revenue for the operator and model it by a parameter G ≥ 0 corresponding to the monthly revenue received by the operator per D2D user.




 Moreover, we need to specify the number of relays and D2D users in the network.
 In this regard, we assume that an
area 𝒜 of km^2
 is covered by the considered D2D network. This, together
 with the previously considered network parameters
 (γ, p, λ)  allows us to express the 
 mean number of relays in the network 
 as pγ^2𝒜/2
 (recall from <cit.> that γ^2/2 is the average number of vertices per unit area in the PVT)
 and the mean number of users as
 λγ𝒜.
  
 














 §.§ Neo-operator's uberizing strategy




We now consider an operator willing to deploy its network by relying on D2D technology only (and thus limiting infrastructure investments in base stations) with the following business strategy.

In order to spread CAPEX invesments over time and not massively invest too quickly, deploying relays will be done in two steps: a first network deployment phase before the commercial launch of the service and a second one after this commercial launch, when the neo-operator starts to gain customers. 

Initially, an investment in relays (CAPEX) has to be made before the commercial launch of the service. 
During this initial period of network deployment, no customers have subscribed to the service and so the user density is null (λ(t)=0). Note that once a  relay has been installed, operational costs (c_OPEX)  are to be paid for this relay by the operator. We denote by p_min the proportion of crossroads that the neo-operator wishes to equip with relays at the end of this first phase. The choice of a value for p_min is done by the neo-operator and can be oriented by the results about the minimal relay proportion needed for large-scale connectivity of the network. We assume that the relays are deployed in equal amount during each month of the initial deployment period, as highlighted by Table <ref>. 
 

At month t=T_LAUNCH, the service of the neo-operator is commercially launched. From that moment, the operator gets a revenue G per month for each D2D user.
Worth noticing is that the neo-operator might not have sufficiently many customers yet (and so D2D relays) to ensure a good QoS. Over time and by contagion effect, new customers will be attracted and will allow to reach the critical mass needed to ensure large-scale connectivity of the network.







 This will be taken into account by allowing for the user density  λ(t) to depend on time. 

 When the D2D service is commercially launched, the neo-operator will start its second relay deployment phase, until reaching a proportion p_max at time t=T_CRITICAL. Again, we assume that the relays are deployed in equal amount during each month of this second phase, see Table <ref>.  In practice, the choice of values for p_max and T_CRITICAL is also oriented by the results about the minimal relay proportion needed for large-scale connectivity of the network, and done by the neo-operator in such a way that when all relays have been deployed (i.e. in proportion p_max at time T_CRITICAL), the critical mass of users ensuring large-scale connectivity of the network has almost been reached. In other words, this means that the neo-operator tunes p_max and T_CRITICAL so as to have:
 
    p_max≈ p^*(λ(T_CRITICAL),r).

 Finally, once all relays have been deployed, the neo-operator starts to replace them at time t=T_DEP,  in such a way that the whole relay fleet will entirely be replaced within another depreciation period [T_DEP;2T_DEP], and so on. 







    
    



 
 In the end, the neo-operator wishes to have a return on investment (ROI) by counting on the revenue coming from its customers and a limited investment in renewing physical relays.  
 More specifically,  a first quantity of interest for the operator's strategical decisions is the monthly cash flow CF(t), which corresponds to the difference between the money earned and the money spent each month:
 
    CF(t)  Gλ(t)γ𝒜- N_B(t)c_CAPEX - N(t) η c_CAPEX/12,

 where N_B(t) and N(t) respectively denote the number of relays that need to be bought at the beginning of month t and the total number of relays in the network at the end of month t. 
 A second quantity of interest is the cumulated revenue CR(t) up to month t: 
  
    CR(t) ∑_s=0^t CF(s),

where CF(s) is the cash flow at month s defined by (<ref>).  The ROI is reached when the cumulated revenue becomes positive. 



§ RESULTS


In this section, we present the results of our numerical estimations. We first investigate the physical relay proportion needed for large-scale connectivity of the D2D network, taking into account the presence of mobile users at crossroads. These estimates, combined with our cost model assumptions, allow us to investigate an uberizing scenario described in Section <ref>.





 §.§ Minimal relay proportion needed for large-scale connectivity of a D2D network













































Figure <ref> illustrates two examples of the estimations for this minimal physical relay proportion p_c(λ,r) required for connectivity of the D2D network at large scale. 
In both examples, two facts are of noticeable importance. On the one hand, taking into account the presence of D2D users being able to act as relays on crossroads considerably reduces the former estimates (p^*(λ,r)) provided in <cit.>. 
On the other hand, the influence of the chosen geometry for the modelling of crossroads is crucial: the estimated physical relay proportion required for large-scale connectivity varies by at least a factor two in high user density scenarios. This is due to the fact that the ratio between the area of a triangle and its circumcircle is considerably small. 
As a matter of fact, it is much more likely to find mobile users at crossroads in the circumcircle case than in the triangle case, which results in less physical relays needed at a global scale. 

Figure <ref>(a) presents the estimates when the D2D range r=50  m, which corresponds to a scenario where the radio technology supporting D2D would be WiFi <cit.>. In such a case, note that a sufficiently high density of users, mainly λ≥ 60  km^-1, can fully compensate the relays in the circumcircle case. Note that such a threshold is not unrealistic, as λ≈ 60  km^-1 equivalently means that there are in average 60 D2D users per kilometer of streets, which means less than one user every fifteen meters in average. 

The case of larger connectivity radii is for instance depicted in Figure <ref>(b), where r=200  m.
From the previous work <cit.>, we know  that for such  regimes, we approach an asymptotic situation where the total proportion of equipped crossroads p^*(λ,r) is independent of λ and r and equal to the absolute minimal proportion of 71.3% of crossroads
(cf. the horizontal red line on Figure <ref>(b)).
Such high values of r require the use of  millimeter-Wave frequencies <cit.> for D2D communications. This will be the case in 5G networks, where one will thus approach the asymptotic situation depicted in Figure <ref>(b).








 §.§ Analysis of an uberizing neo-operator's strategy











We performed a numerical evaluation of the uberizing strategy presented in Section <ref> with parameters coming from internal data provided in Table <ref> and a user density λ(t) illustrated by Figure <ref>. We chose a user density t ↦λ(t) which is increasing as a function of time, thus assuming that the neo-operator does not lose customers. Note the user density is null before commercial launch, i.e. for t≤ T_LAUNCH=1  year, then undergoes a steep increase for a six-month period corresponding to early adopters and finally undergoes a slower growth once a critical mass of D2D users has been attained. 



In our numerical example, we took p_min=10% and  p_max=20%.   Moreover, T_CRITICAL=30  months has been chosen. Note that this choice of parameters satisfies (<ref>). Indeed, λ(T_CRITICAL) ≈ 45  km-1. 

In a 5G millimeter-Wave context where r=200  m (see Figure <ref>(b)), assuming circle crossroads, this density of users requires  a minimal relay proportion of about p_c(λ = 45  km-1, r=200  m) ≈ 20%. Thus, at the critical time T_CRITICAL, the neo-operator has fully deployed its relays and ensured large-scale connectivity of its D2D network.









Figure <ref> shows the evolution of the cumulated revenue and of the cash flow over time. With the parameters values prescribed by Table <ref>, we obtain a ROI of 43 months, i.e. 31 months after the commercial launch of the D2D service. Distinguishable times are the ones of the commercial launch 
(where the cash flow CF starts to increase abruptly), the time of the critical connectivity 
(where the cash flow CF increases abruptly for the second time)  and the time 
at which relays start to be replaced (this is when the cash flow CF drops suddenly). 












In practice, note that an ROI of 43 months is more than satisfying for potential investors. Moreover, our cost model is sufficiently generic so that any operator willing to launch a D2D service can replace our simulation parameters by its own internal data (e.g. obtained via marketing analyses) and hence get an idea of when setting up a relay-assisted D2D network will be profitable. This in turn can help to make strategical decisions regarding D2D investments. 

Our cost model paves the way to interesting discussions regarding deployment of relay-assisted D2D networks. In the case of a neo-operator, note that the number of D2D users may be too small at the beginning of the service to get a fully connected network. The neo-operator would then start by offering proximity services <cit.>, until large-scale connectivity of its network is ensured by sufficiently many D2D users. Another possibility to reach this critical mass of users could consist in resorting to customers of extisting operators through negociated costs.  
Finally, funding the D2D service from its very beginning is essential, otherwise the ROI would happen much later in time, and thus the uberization scenario described in our model might not be profitable for a new actor in the telecommunications sector.





§ CONCLUDING REMARKS

Proposing more realistic geometric  models for  crossroads in urban environments, we considerably reduced predictions of the minimal proportion of crossroads  that have to be equipped with relays so as to ensure connectivity. We have also proposed a new cost model for D2D relay deployment, allowing one to more reliably quantify  the necessary investments in relays as a prelude to deploying a relay-assisted D2D network. As a main application, we studied a practical uberization scenario where a neo-operator relies on D2D only to set up its network. We demonstrated that a return on investment with such a strategy  is feasible in a reasonable amount of time, even when the service is funded by low fees. The generic nature of our cost model can help traditional or new actors of the telecommunication sectors to make strategical decisions regarding investments in D2D technology. 

Numerous model extensions are possible. On the geometric point of view, different street systems could be considered, especially those of North American or African cities. On the economic point of view, different scenarios could be studied, e.g. the one of a traditional operator willing to offer D2D as an additional service to its existing customers and hope to get a coverage extension from it. Finally, on the technological point of view, the study of more general shadowing effects, interference or user mobility would lead to more realistic predictions, of greater strategical importance for operators.


[Computation of the typical crossroad surface ]
 It is  well-known that 𝒮'(l,α,β)=π R^2, where R is the circumcircle radius of the triangle ABC given  by:

    R=AB   AC   BC/4𝒮(l,α,β)

Note first that by symmetry arguments in Figure <ref>, it is easily seen that (OA) is the bissector of the angle spanned by the lines (d_1) and (d_2).  A bit of trigonometry henceforth implies that:

    OA = l/2  sin( α/2)    ;    
        OB = l/2  sin( β/2)

And so, by the cross-product formula, the area of the triangle OAB is given by:

    S_OAB   = 1/2OA   OB  sin(OA,OB)
       =l^2/8sin(α/2)sin(β/2)sin(α+β/2).

In the same way, by a circular permutation of α,β and δ, we get analogous formulae for the areas of triangles OBC and OCA. Noting that δ=2π -α -β, we therefore get the surface 𝒮(l,α,β) of the triangle ABC:






    𝒮(l,α,β)    = S_OAB+S_OBC+S_OCA
       = l^2/4[α/2+ β/2 + δ/2] 
       =  l^2/4[α/2+ β/2 - α+β/2].










To derive a formula 𝒮'(l,α,β) we now only need to compute the side lengths, which is easily done by the law of cosines. For example:

    AB^2    = OA^2 + OB^2 -2   OA   OB  cos(OA,OB) 
       = l^2/4sin^2 α/2+l^2/4sin^2 β/2-2l^2/4sinα/2sinβ/2cos(α+β/2).

Factorising by l^2/4, expanding the last cosine and using the classical trigonometric identity 1=cos^2 x + sin^2 x yields:





    AB^2 = l^2/4[(α/2-β/2)^2 +4].


Likewise, by circularly permutating α,β and δ, and using the fact that δ=2π - α - β, we get similar formulae for BC^2 and AC^2. Therefore, 
the area 𝒮'(l,α,β) of the circumcircle is given by:











    𝒮'(l,α,β)=π R^2 = πAB^2   BC^2   AC^2/16𝒮(l,α,β)^2,

 where 𝒮(l,α,β) and AB are respectively given by equations (<ref>) and (<ref>). BC and AC are respectively obtained by the circular permutations (α,β) ↦ (β,δ=2π-α-β) and (α,β) ↦ (δ=2π-α-β,α) in (<ref>).





§ ACKNOWLEDGMENTS

The authors thank Veluppillai Chandrakumar for fruitful discussions on the cost model.












IEEEtran




