domain: info math

text:
Bartlomiej Blaszczyszyn
email: bartlomiej.blaszczyszyn@inria.fr

Philippe Jacquet
email: philippe.jacquet@inria.fr

Bernard Mans
email: bernard.mans@mq.edu.au

Dalia Popescu

Bart Lomiej B Laszczyszyn •

Bart Lomiej

Energy and Delay Trade-Offs of End-to-End Vehicular Communications using a Hyperfractal Urban Modelling

Keywords: Wireless Networks, Delay, Energy, Fractal, Vehicular Networks, Urban networks

come

Introduction

Motivation and Background

Vehicular communications, to other vehicles, to infrastructure or to everything (V2X), are key components of the 5th Generation (5G) communications. In cities, with an ever increasing connectedness and complexity, it is paramount to provide an effective integration of vehicular networks within a complex urban environment. In addition, sensors allowing automated and autonomous driving in such complex environments generate a huge amount of data demanding high bandwidth and data rates [?]. All these needs require a careful design for optimal connectivity, low interference, and maximum security.

5G NR is essentially a multi-beam system, generated by millimeter-wave (mmWave) technology [?]. For a long time these frequencies have been disregarded for cellular communications due to their large near-field loss, and poor penetration through common material, yet recent research and experiments have shown that communications are feasible in ranges of 150-200 meters dense urban scenarios with the use of such high gain directional antennas [?]. Meanwhile the embedding space of vehicular networks leads mostly to a one dimensional topology since roads are mainly built as straight lines [?].

Given the numerous challenges of mmWave [?] and the important place the vehicular communications hold in the new communications era, it cannot be ignored that the effectiveness of the communications are influenced by the environmental topology. Cars are located on streets and streets are conditioned by a world-wide common generic architecture that has interesting features. One major feature of the urban architecture that we exploit in this work is self-similarity. A self-similar object, is an object in geometry which shows strong similarity (either exactly or approximately) with smaller parts of itself (i.e. the whole has the same shape as one or more of the parts). When the smaller parts are strictly identical with the larger parts, the object is said to be a fractal.

Although being extensively studied in diverse research fields such as biology and chemistry, self-similarity has been only recently introduced in wireless communication design and performance. Self-similarity is present in every aspect of urban environment [?]. The hierarchic organization with different degrees of scaling of cities is a perfect illustration of the quasi fractal structure of human society [?]. Figure ?? presents a snapshot of the traffic in a neighborhood of Minneapolis. Common patterns and hierarchical organizations can easily be identified in the road traffic and shall be further exploited in this paper. In this paper, we exploit the "hyperfractal" model introduced in [?,?] to capture the impact of the network topology on the fundamental performance limits of vehicular networks in urban settings. The model consists of assigning self-similar traffic densities to city streets at any scale, thus avoiding both the extremes of regularity of the basic Manhattan grid and the uniform randomness of Poisson point process. The fitting of the model with traffic data of real cities having been showcased in [?]. The hyperfractal model is characterized by a dimension that is larger than the dimension of the Euclidean dimension of the embedding space, that is larger than 2 when the whole network lays in a 2-dimensional plane as it is the case for city maps.

Previous results in [?] revealed that the number of hops in a routing path between an arbitrary sourcedestination pair increases as a power function of the population n of nodes when n tends to infinity. However, we showed that the exponent tends to zero when the fractal dimension tends to infinity. An initial observation for this model is that the optimal path may have to go through streets of low density where inter-vehicle distance can become large, therefore the transmission could become expensive in terms of energy cost. Hence, in this paper, we investigate the relationship between efficient communications and energy costs.

Contributions and paper organization

Our goal is to characterize trade-offs between the endto-end communication delay and the energy in urban vehicular communications with infrastructure assistance in cities. We will consider the communication with internal routing involving all mobile nodes considered as mobile relays, and fixed relays in the infrastructure. We initially consider that the relays are not connected with an underground wired network (just beacon on traffic lights) and only act as wireless relay between mobile nodes. We will then compare with the case where the relays are connected to an underground network.

Our first contribution is to give an accurate description of the hyperfractal distribution model in the more general framework of stochastic geometry and point processes.

Our main contributions are theoretical bounds for the end-to-end communication energy and delay budget as a function of the number of nodes and relays. We will consider that the main source of energy consumption is the packet transmission, and thus consider that other minor energy costs such as the store and forward energy cost at each relay are negligible value in comparison. Note that our analysis displays the transmission cost and the hop count, thus allowing to capture alternative determination of energy costs in our framework and to be adapted to various other scenarios. Each of these parameters could be again split into various realistic sub-parameters but while this would complicate the analysis, it will not change significantly the orders of our quantitative results.

More precisely, we consider two different energyminimizing goals: (i) total accumulated energy or (ii) maximum energy per node. We will prove that the delay D n , measured by the hop count for an end-to-end transmission, is bounded by

D d F -1 n O(n d F -1-α )
where α is a tunable constant less than 1 which also affects the path energy E n such that for the accumulated energy path

E 1/(δ-1) n D d F -1 n = O(n d F -2 )
where δ > 1 is the attenuation factor of radio transmissions. For the maximum energy path we have E

1/δ n D d F -1 n = O(n d F -2
). In both cases the energy constraint tends to zero when n tends to infinity.

Finally we will show that our model fits real deployments where open data sets are available. The results are confirmed through simulations using different fractal dimensions and path loss coefficients, using a discrete-event simulator in Matlab.

The paper is organized as follows:

-In Section ??, we describe the hyperfractal geometric model [?,?]. Initially, for the sake of the explanation, via a model based on a grid map, then by extending the model realistically by fitting concrete data extracted from city maps. We end this section by deriving some fundamental properties of the archetypal model in the stochastic geometry framework.

-In Section ??, we describe the physical models of the telecommunication system over a city map and in particular we address the energetic balance of the ad hoc routing strategy between nodes. -In Section ??, we list and prove our main results.

More particularly, we quantify the energy-delay trade-off of the end to end communications between mobile nodes. The result are given in order of magnitude as function of the number of nodes n and the intensity ρ of the fixed infrastructure. Importantly we prove that for an end-to-end transmission in a hyperfractal setup, the energy (either accumulated along the path or bounded for each node) decreases if we allow the path length to increase. We also prove a lower bound on the network throughput capacity with constraints on path energy. -In Section ?? we compare the previous results with a scenario where the hop by hop routing strategy is replaced by the interconnection of the fixed relays via an underground cabled network. In this case we show that the underground network greatly improves the performance: with the same number of relays and bounded energy cost, the hop by hop routing strategy requires a delay increasing in n 1/2 while the underground network keeps it constant. -Finally, Section ?? validates our analytical results using a discrete-time event-based simulator developed in Matlab.

Related Works

Millimeter-wave is a key technological brick of the 5G NR networks, as foreseen in the ground-breaking work done in [?] and already proved by ongoing deployments. The research community has been already investigating challenges that may appear and proposing innovative solutions. Vehicular communications are one of the areas that are to benefit from the high capacity offered by the mmWave technology. In [?], the authors propose an information-centric network (ICN)based mmWave vehicular framework together with a decentralized vehicle association algorithm to realize low-latency content disseminations. The study shows that the proposed algorithm can improve the content dissemination efficiency yet there is no consideration about the energy. The purpose of [?] is optimizing energy efficiency in a cellular system with relays with D2D (device-to-device) communications using mmWave.

As mmWave is highly directional and blockages raise concerns, the authors of [?] propose an online learning algorithm addressing the problem of beam selection with environment-awareness in mmWave vehicular systems. The sensitivity to blockages is generally solved with the assistance of the relaying infrastructure. The authors of [?] attempt to solve the dependency of infrastructure for relaying in vehicular communications by exploiting social interactions. In [?], the problem of relay selection and power is solved using a centralized hierarchical deep reinforcement learning based method. Yet the authors use a simplified highway scenario, which cannot scale up to a city structure.

Stochastic geometry studies have shown results on the interactions between vehicles on the highways or in the street intersections [?,?]. The work in [?] performs statistical studies on traces of taxis to identify a planar point process that matches the random vehicle locations. The authors find that a Log Gaussian Cox Process provides a good fit for particular traces. In [?] the authors propose a novel framework for performance analysis and design of relay selections in mmWave multi-hop V2V communications. More precisely, the distance between adjacent cars is modeled as shiftedexponential distribution.

Self-similarity for urban ad hoc networks has been introduced in [?,?], where the hyperfractal model exploits the fractal features of urban ad hoc networks with road-side infrastructure. In [?], we presented an analysis of the propagation of information in a vehicular network where the cars (the only communication entities) are modeled using the hyperfractal model. The setting is different to this paper: without relays at the intersections the network is disconnected but becomes connected over time with mobility. The packets are being broadcast and results on typical metrics for delay tolerant networks were presented without investigation on power or energy. The study in [?] provides results on the minimal path routing using the hyperfractal model for static nodes to model the road-side infrastructure that assumes an infinite radio range, creating concerns for allowed transmission power and network energy consumption. In contrast, in this paper, we add constraints on these quantities to provide insights on the achievable trade-offs between the endto-end transmission energy and delay.

Geometric Model

In appendix we give a table summarizing our main notations

Hyperfractal distribution of street traffic in a city archetypal model

In this model we initially consider that the city map is a unit square supporting a network of North-South streets intersecting a collection of West-East streets. Thus imagine a city map organized like a Manhattan map with the difference that the network is dense and that the traffic density varies to sum to finite value even if the number of streets is infinite.

As we will show later, the procedure of fitting traffic maps to hyperfractals does not require grid-like structures of cities. The necessary condition is only that the increasing cumulated distance with decreasing density (i.e., the hyperfractal model makes no assumption on the geometric shape but only on the scaling of the population density).

If we rank the streets by traffic density the latter will decays in k 1-d F where k is the rank of the street.

In the archetypal model displayed in Figure ?? the central cross is assigned at level 0. The other streets will be assigned at higher levels. For H ≥ 0 there will be 2 H North-South streets at level H and and 2 H West-East streets at level H. The density of mobile users on a street of level H will be

λ H = p 2
q 2 H with 0 < p < 1 and q = 1 -p. With this definition it comes that:

d F = log(4/q) log 2 ≥ 2.
The placement process of a mobile user is described on [?,?]. In short, with probability p the user is placed uniformly on the central cross, otherwise it goes uniformly in one the four quadrants and the process is repeated until it finds a cross in one of the sub-• • • -sub quadrants. At each iteration, the level of the streets of central crosses is incremented by one.

€ 1 -p r 2 ⎛ ⎝ ⎜ ⎞ ⎠ ⎟ 2 € 1 -p r 2 ⎛ ⎝ ⎜ ⎞ ⎠ ⎟ 2 € 1 -p r 2 ⎛ ⎝ ⎜ ⎞ ⎠ ⎟ 2 € 1 -p r 2 ⎛ ⎝ ⎜ ⎞ ⎠ ⎟ 2 € p r 2 € 1 -p r 2 ⎛ ⎝ ⎜ ⎞ ⎠ ⎟ p r € 1 -p r 2 ⎛ ⎝ ⎜ ⎞ ⎠ ⎟ p r
The recursive placement process makes that starting from a unity mass, we place p on the central cross, and q/4 is placed in each quadrant and that the quadrant strictly similar to the main initial map with exception halving the lengths. Therefore the fractal dimension d F should satisfy.

q 4 = 1 2 d F .

Hyperfractal distribution of relay placement of relays in the city archetypal model

In addition to mobile nodes being able to relay like in a MANET, the network will also use fixed relays placed on existing infrastructures. These fixed relays will have the same technology as the mobile nodes and will be placed at street intersection in order to extend the radio coverage. Indeed without fixed relays at some street intersections, the packets could not be forwarded outside its originator street due to poor penetration of radio millimeter waves in buildings. Indeed the cars does not spend enough time on street intersection when in line of sight of both streets to make a timely forwarding of all the waiting packets. The placement of the fixed relays will be hyperfractal, and the abscissa and the ordinate are independent. We fix a parameter 0 < p r < 1 and q r = 1 -p r . For each coordinate we have a recursive placement. Let us concentrate on the selection. With probability p r the abscissa is exactly the middle of the segment and is level 0. Otherwise it will be in the left or right segment, the process repeat, the level increments, until it is placed in the middle of one of the sub-

H et V is p(H, V ) = p 2 r q r 2 H+V .
The set of relay positions on a segment is an hyperfractal set of dimension (2/qr) log 2 . The combination of abscissa or ordinate multiplies by two this dimension:

d r = 2 (2/q r ) log 2 ≥ 2.
In the following we consider that the total number of relays is a Poisson random variable of mean ρ. This is a simplifying assumption in order to cope with the dependencies introduced by a fixed number of relays. The probability that an intersection of two streets of level H and V does not contain a relay is exp(-ρp(H, V )) and the event is independent of the other intersection. If a street intersection were to carry more than one relay, these relays will be merged in a single one.

In [?] we show that the average total number of merged relays R(ρ) is sublinear since

R(ρ) = ∞ k=0 (k + 1)2 k q r 2 nk = O(ρ 2/dr log ρ).

Fitting the hyperfractal model for traffic distribution to real city maps

Most important above all, one must understand that the hyperfractal model is not a variation on the Manhattan street model. Indeed the grid aspect which appears in our description when displaying the most dense streets is just a convenience of presentation. In fact the essence of the model is not in the overall shape of the city map, but resides in its local organisation of the street density distribution. It is not needed for a city map to be grid-like with a binary organisation of the streets levels in order to fit a hyperfractal model [?,?].

The condition is that the street densities decay in a heavy polynomial tail, and that the streets of low density alternate with streets of higher densities at any arbitrary scale. Of course this would imply an infinite number of streets which is of course an unrealistic hypothesis, but this is mitigated by the fact that the streets with very low theoretical densities will not show up because they will not carry any node in practice. Again the overall shape of the city map does not need to be square, it can be any shape and the streets can take arbitrary orientations.

The hyperfractal models for traffic and for relays distributions have been derived by making observations on the scaling of traffic densities and the scaling of the infrastructures, with road lengths, distances between intersections which allow rerouting of packets, etc.

In our previous works [?], we have introduced a procedure which allows transforming traffic flow maps into hyperfractal by computing the fractal dimension d F of each traffic flow map then quantify the metrics of interest. The fitting procedure exploits the scaling between the length of different levels of the streets and the scaling of the 1-dimensional intensity per street and street intersection. The difficulty is that the roads rarely have an explicit level hierarchy since the data we have about cities are in general about road segment lengths and average street traffic densities.

To circumvent this problem, we do a ranking of the road segments in the decreasing order of their traffic density. If S is a segment we denote η(S) its density and L(S) the accumulated length of the segment ranked before S (i.e. of larger density than η(S)). For ξ > 0 we denote µ(ξ) = η(L -1 (ξ)). Formally L -1 (ξ) is the road segment S with the smallest density such that L(S) ≤ ξ. The hyperfractal dimension will appear in the asymptotic estimate of µ(ξ) when ξ → ∞ via the following property:

µ(ξ) = Θ ξ 1-d F .
(1)

The following table summarize several hyperfractal dimensions of nodes analysed so far:

City d F Adelaide 2.8 Minneapolis 2.9 Nyon 2.3 Seattle 2.3

Fitting the hyperfractal model for relay nodes to real city maps

The procedure is similar to the previous procedure and has the following steps. First, we consider the set of road intersections I defined by the pair of segments (S 1 , S 2 ) such that S 1 and S 2 intersect. Let ξ 1 , ξ 2 be two real numbers we define p(ξ 1 , ξ 2 ) as the probability that two intersecting segments S 1 and S 2 such that C l (S 1 ) ≤ ξ 1 and C l (S 2 ) ≤ ξ 2 contains a relay. The hyperfractality of the distribution of the relay distribution implies when ξ 1 , ξ 2 → ∞:

p(ξ 1 , ξ 2 ) = Θ (ξ 1 ξ 2 ) -dr/2 . ( 2
)
Since the probability is not directly measurable we have to estimate it via measurable samples. Indeed let N (ξ 1 , ξ 2 ) be the number of intersections (S 1 , S 2 ) ∈ I such that C l (S 1 ) ≤ ξ 1 and C l (S 2 ) ≤ ξ 2 and let R(ξ 1 , ξ 2 ) be the number of relays between segments (S 1 , S 2 ) such that C l (S 1 ) ≤ ξ 1 and C l (S 2 ) ≤ ξ 2 . One should have:

R(ξ 1 , ξ 2 ) N (ξ 1 , ξ 2 ) = Θ (ξ 1 ξ 2 ) -dr/2 (3)
and from here get the fractal dimension of the relay process.

Data Fitting Examples

Using public measurements [?], we show that the data validates the hyperfractal scaling of relays distribution with density and length of streets. While traffic data is becoming accessible, the exact length of each street segment is difficult to find, therefore the fitting has been done manually.

Figure ?? shows a snapshot of the traffic lights locations in a neighborhood of Adelaide, together with traffic densities on the streets, when available. As the roadside infrastructure for V2X communications has not been deployed yet or not at a city scale, we will use traffic light data as an example for relays [?]. By applying the described fitting procedure and using equation (??) the estimated fractal dimension of the traffic lights distribution in Adelaide is d r = 3.5 which is significantly larger than the fractal dimension for the traffic distribution (2.8). In Figure ?? we show the fitting of the data for the density distribution function.

Note that it is the asymptotic behavior of the plots that are of interest (i.e., the increasing accumulated distance with decreasing density therefore decreasing the probability of having a relay installed) since the

Fundamental properties of the Hyperfractal point processes

We come back to our hyperfractal archetypal model with the grid binary street model.

As we saw, the support of the population of n mobile nodes is a grid of streets. Let us denote this structure by

X = ∞ l=0 X H with X H = b {b2 -(H+1) } × [0, 1] ∪ [0, 1] × {b2 -(H+1) }
where l denotes the level and l starts from 0, and b denotes all odd integers between 1 and 2 H+1 -1. Figure ?? displays three first levels, H = 0, 1, 2. Observe that the central "cross" X 0 splits ∞ H=1 X H in 4 "quadrants" which all are homothetic to X with the scaling factor 1/2.

Street traffic

Following [?], the Poisson point process Φ of (mobile) users on the support X with total intensity (mean number of points) n (0 < n < ∞) having 1-dimensional intensity nλ H on each street of level H.

The process Φ is neither stationary nor isotropic. However, it has the following self-similarity property: the intensity measure of Φ on X is hypothetically reproduced in each of the four quadrants of ∞ l=1 X l with the scaling of its support by the factor 1/2 and of its value by q/4.

The fractal dimension is a scalar parameter characterizing a geometric object with repetitive patterns. It indicates how the volume of the object decreases when submitted to an homothetic scaling. When the object is a convex subset of an euclidian space of finite dimension, the fractal dimension is equal to this dimension. When the object is a fractal subset of this euclidian space as defined in [?], it is a possibly a non integer but positive scalar strictly smaller than the euclidian dimension. When the object is a measure defined in the euclidian space, as it is the case in this paper, then the fractal dimension can be strictly larger than the euclidian dimension. In this case we say that the measure is hyperfractal (i.e., when d F > 2).

Notice that when p = 1 the model reduces to the Poisson process on the central cross, while for p → 0, d F → 2 it corresponds to the uniform measure in the unit square.

Fixed Relays

We denote the fixed relay placement process by Ξ. To define Ξ it is convenient to consider an auxiliary Poisson process Φ r with both processes supported by a 1dimensional subset of X namely, the set of intersections of segments constituting X . We assume that Φ r has discrete intensity p(H, V ) at all intersections X H ∩ X V for H, V = 0, . . . , ∞ for some parameter, recalling that ρ > 0 is the relay intensity parameter. That is, at any such intersection the mass of Φ r is Poisson random variable with parameter ρp(H, V ) and ρ is the total expected number of points of Φ r in the model. The selfsimilar structure of Φ r is explained by its construction as explained before, as illustrated in Figure ??. The Poisson process Φ r is not simple: we define the relay process Ξ as the support measure of Φ r , i.e., only one relay is installed at crossings where Φ r has at least one point.

Remark 1 Note that the relay process Ξ forms a nonhomogeneous binomial point process (i.e. points are placed independently) on the crossings of X with a given intersection of two segments from X H and X V occupied by a relay point with probability 1exp(-ρp(H, V )).

A complete hyperfractal map with mobile nodes and relays is illustrated in Figure ??. In the following, we shall provide some fundamental tools that allow one to handle our model in a typical stochastic geometric framework. This section gives insights about the theoretical foundations of hyperfractal point process which is of independent interest to our main results and can be used in other works.

Let L + 1 be a geometric random variable with parameter p (i.e., P(L = l) = p(1 -p) l , l = 0, 1, . . .) and given L, let x 0 be the random location uniformly chosen on X L . We call x 0 the typical mobile user of Φ. More precisely, we shall consider the point process Φ ∪ {x 0 } where x 0 is sampled as described above and independently of Φ.

Similarly, let U + 1 and W + 1 be two independent geometric random variables with parameter p r and given (U, W ), let x * be a crossing uniformly sampled from all the intersections of X U ∩ X W . We call x * the typical auxiliary point of Φ r . More precisely, we shall consider point process Φ r ∪ {x * } where x * is sampled as described above and independently of Φ r .

Finding the definition of the typical relay node ξ 0 is less explicit yet similar to the typical point definition. Informally, the conditional distribution of points "seen" from the origin given that the process has a point there is exactly the same as the conditional distribution of points of the process "seen" from an arbitrary location given the process has a point at that location.

We define it as the random location on the set of the crossings of X involving the following biasing of the distribution of x * by the inverse of the total number of the auxiliary points co-located with x *

P(ξ 0 = x) = E 1(x * =x) 1+Φr({x * }) E 1 1+Φr({x * })
.

More precisely we consider Ξ ′ ∪{ξ 0 } (which distribution is given for any intersection x of segments in X and a possible configuration ϕ of relays) by considering

P( ξ 0 = x, Ξ ′ = ϕ ) = E 1(x * =x)1(supp(Φr)\{x}=ϕ) 1+Φr({x * }) E 1 1+Φr({x * })
where Φ r and x * are independent (as defined above). Note that, in contrast to the typical points of Poisson processes Φ and Φ r , the typical relay ξ 0 is not independent of remaining relays Ξ ′ .

In what follows, we shall prove that our typical points support the Campbell-Mecke formula (see [?,?]) thus justifying our definition and also providing an important tool for future exploiting the model in a typical stochastic geometric framework.

Theorem 1 (Campbell-Mecke formula) For all measurable functions f (x, ϕ) where x ∈ X and ϕ is a realization of a point process on X ,

E xi∈Φ f (x i , Φ) = nE [f (x 0 , Φ ∪ {x 0 })] (4) E xi∈Φr f (x i , Φ r ) = ρE [f (x * , Φ r ∪ {x * })] (5)
and

E xi∈Ξ f (x i , Ξ) = E [Ξ(X )] E [f (ξ 0 , Ξ ′ ∪ {ξ 0 })] (6)
where the total expected number of relay nodes

E [Ξ(X )] = R(ρ)
Proof (Proof of Theorem ??.) First, consider the process of users Φ. The Campbell-Mecke formula and the Slivnyak theorem [?] for the non-stationary Poisson point processes Φ give

E xi∈Φ f (x i , Φ) = X E [f (x, Φ ∪ {x})] µ(dx), (7)
where µ(dx) is the intensity measure of the process Φ. Specifying this intensity measures the right-hand side term of (??), thus this becomes

∞ l=0 X l E [f (x, Φ ∪ {x})] n(1 -p) l pdx.
In this expression, one can recognize E [f (x 0 , Φ ∪ {x 0 })] which concludes the proof of (??). The proof of (??) follows the same lines. Consider now the relay process Ξ. By the definition of Ξ, one can express the left-hand side of (??) in the following way:

E xi∈Ξ f (x i , Ξ) = E xi∈Φr f (x i , supp(Φ r )) Φ r ({x i }) ,
where supp(Φ r ) denotes the support of Φ r . Using (??), we thus obtain:

E xi∈Ξ f (x i , Ξ) = ρE f (x * , supp(Φ r ∪ {x * })) 1 + Φ r ({x * }) . (8)
By the definition of the joint distribution of x * and supp(Φ r ∪ {x * }) the right-hand side of (??) is equal to

ρE 1 1 + Φ r ({x * }) E [f (ξ 0 , Ξ ′ ∪ {ξ 0 })] .
This completes the proof of (??) with

E [Ξ(X )] = ρE 1 1 + Φ r ({x * })
.

Hyperfractal Properties and Communication model, Canyon effect

Our model is a store-and-forward routing and not a store-carry-and-forward routing. The packet received at one time slot is immediately re-transmitted to the next relay on the very next time slot. Under this hypothesis a convenient hypothesis is to consider that all the mobile nodes are immobile during the routing of the packets toward their destination. Indeed the propagation speed (including store-and-forward operation) are infinitely larger than the physical motion speed of the mobile nodes, somewhat 100 km/sec compared to few 10 m/s. Using a store-carry-and-forward routing strategy like in a Delay Tolerant Network would lead to far too large end-to-end delays which will severely impact the perceived quality of the connection.

In this section we extract the relevant properties of the Hyperfractal model and relate them to our communication model. We also provide some additional insights into these models via the framework of the stochastic geometry and point process. These latter results are of independent interest and allow to lay foundations for other works.

As explained in our previous works [?], the poor penetration capability of the millimeter waves leads to the so-called "canyon effect", which basically tells that radio signals emitted by mobile user mostly propagate on streets and do not penetrate buildings. In this work we consider a hop by hop routing strategy between mobile nodes in a store and forward ad hoc mode. We consider that the mobility of users will be considerably slow compared to the speed of packet commutation. Assuming that mobile nodes stay a negligible time at intersection (indeed in the archetypal model nodes are distributed like a uniform Poisson in each street and the intersection points with the other streets make a non measurable set), their communication would unlikely escape their original street in absence of fixed relays at intersection. The fixed relays are assumed to cover their two streets and will be instrumental to extend connectivity to (mostly) the whole city.

As we primarily seek to understand the relationship between end-to-end communications and energy costs, we do not consider detailed aspects of the communication protocol that impact these (e.g., the distributed aspects needed to gather position information and construct routing tables in every node). The transmission is done in a half-duplex way, a node is not allowed to transmit and receive during the same time-slot. The received signal is affected by additive white Gaussian noise (AWGN) noise N and path-loss with pathloss exponent δ ≥ 2.

As a consequence of the high directivity and low permeability of the waves in high frequency (6GHz, 28GHz, 73 GHz as candidates for 5G NR), the next hop is always the next neighbor on a street, i.e. there exists no other node between the transmitter and the receiver. Indeed, while a lot of work is still dedicated to characterising the exact overall network connectivity for mmWave communications V2V in urban setting [?], it is known that intermediate vehicles create significant blockage and a severe attenuation of the received power for vehicles past near neighbours [?,?]. Thus the routing strategy considered is a nearest neighbor routing. In fact, we can show that, under reasonable assumptions, this strategy is optimal.

Lemma 1 If the noise conditions are the same around each node, then the nearest neighbor routing strategy is optimal in terms of energy.

Proof To simplify this proof we ignore the signal attenuation due to the mobile users positioned as radio obstacles between the sender and the receiver of one hop packet transmission, although this will have an important impact on energy. Consider the packet transmission from a node at a location x to a node at location y on the same street. If N is the noise level and K is the required SNR, then the transmitter must use a signal of power |y -x| δ N K. Assume that there is a node at position z between x and y. Transmitting from x to z and then from z to y would require a cumulated energy (|z -x| δ + |y -z| δ )N K which is smaller than the required energy for the direct transmission, since |x -

z| δ + |z -y| δ ≤ (|x -z| + |z -y|) δ .
Let us make the simplifying assumption that all nodes on a street transmit with the same nominal power P m which depends only on the number m of nodes on the street. We argue that a good approximation is to suppose that:

P m = P max m δ (9)
where P max is the transmitting power necessary for a node at one end of the street to transmit a packet directly to a node at the other end of the street. In other words, assume a road of infinite length where the nodes are regularly spaced by intervals of length L is the length of our street. If in this configuration every node has a nominal power of P max , then the nominal power to achieve the same performance with a density m times larger but with the same noise values should be P max m -δ in order to cope with the loss effect. Thus would give expression (??) if the nodes were regularly spaced by intervals of length L/m. But since the spacing intervals are irregular, one should cope with the largest gap L m /m, this brings a small complication in the evaluation of P m . But the probability that there exists a spacing larger than a given value x/m is smaller than m(1 -x mL ) m ≤ m x/L . Thus we have L m = O(log m/m) (asymptotically almost surely, and in fact as soon as lim inf m L m / log m > 1), and consequently P m = O(P max log δ m/m δ ). To help the reader, we focus on the expression (??) as we are mainly interested in the order of magnitude.

Definition 1 The end-to-end transmission delay is represented by the total number of hops the packet takes in its path towards the destination.

As the energy to transmit a packet is the transmission power per unit of time, we consider the time necessary to send a packet as being equal to the length of a time-slot. We thus do not consider any MAC protocol for re-transmission and acknowledgment of the reception (e.g., we do not consider CSMA-like protocols). In any case, as it will be later observed throughout our derivations, varying the MAC protocol would just change some constants but not the overall scaling. Therefore, from now on, we will refer to P max as the nominal power. Following this reasoning, the accumulated energy to cover a whole street containing m nodes with uniform distribution via nearest neighbor routing is mP m = Pmax m δ-1 . In this case, the larger the population of the street the smaller the nominal power and the smaller the energy to cover the street.

Foxed relays stand in intersections, and thus on two streets with different values of m. We consider a relay to use two different radio interfaces, each with a transmission power according to the previously mentioned rule for each of the streets. This is a perfectly valid assumption, in line with 5G devices specifications for dual connectivity [?].

Main Results

We now provide our theoretical bounds for the end-toend communication hop count. The number of mobile nodes is exactly n, where n is an integer which runs to infinity.

Energy vs Delay

Given that the transmitting power is dependent on the average density of the nodes on the streets and that the transmission power per node is limited by the protocols to a value of P max , the connectivity is restricted. We introduce the following notions and notations. Let t be a node and let P (t) be the nominal transmission energy of this node.

Definition 2 Let T be a sequence of nodes that constitutes a routing path. The path length is D(T ) = |T |. The relevant energy quantities related to the paths are:

-The path accumulated energy is the quantity E(T ) = t∈T P (t).

-The path maximum energy is the quantity M (T ) = max t∈T P (t).

The path accumulated energy is of interest as we want to optimize the quantity of energy expended in the-end-to-end communication, and respectively, the path maximum power as we want to find the path which maximum power does not exceed a given threshold depending on the energy sustainability of the nodes or the protocol. For example, it is unlikely that a node can sustain a nominal power of P max equal to the power needed to transmit in a range corresponding to the entire length of a street. In this case it is necessary to find a path that uses streets with enough population to reduce the node nominal power and communication range (due to the mmWave technology limitations).

Definition 3 Let E be a quantity of energy.

-Let G(n, E) be the set of all nodes connected to the central cross with a path accumulated energy not exceeding E. -Let G k (n, E) be the subset of G(n, E), where the path to the central cross should not go through more than k fixed relays.

Definition 4 Let G ′ (n, E) and G ′ k (n, E) be the respective equivalents of G(n, E) and G k (n, E) but with the consideration of the path maximum power instead of accumulated energy.

Path accumulated energy

The following theorem gives the asymptotic connectivity properties of the hyperfractal in function of the accumulated energy and in function of the path maximum power. This shows that for n large, even for some sequences of energy thresholds E n tending to zero, the sets G 1 (n, E n ) asymptotically dominate the network. The same holds for the sets sequence G ′ 1 (n, E n ).

Theorem 2 In an urban network with n mobile nodes following a hyperfractal distribution, when ρ n both tend to infinity the following holds:

lim n→∞ E |G 1 (n, n -γ P max )| n = 1 (10)
for γ < δ -1, and

lim n→∞ E |G ′ 1 (n, n -γ P max )| n = 1 (11)
for γ < δ, where δ is the pathloss coefficient.

The following lemma ensures the existence of nodes in a street (with proof in the Appendix).

Lemma 2 There exists a > 0 such that, for all integers H and n, the probability that a street of level H contains less than nλ H /2 mobile nodes or more than 2nλ H mobile nodes is smaller than exp(-anλ H ).

The following corollary gives a result on the scaling of the number of mobile relays in a segment of street and the accumulated energy, getting us one step closer to the results we are looking for.

Corollary 1 Let 0 < τ ≤ 1, assume an interval corresponding to a fraction τ of the street length. If the interval is on a street of level H, the probability that it contains less than τ λ H n/2 nodes and it is covered with accumulated energy greater than ϕ(nλ H ) 1-δ P max is smaller than e -anτ λ H . The probability that the energy for each transmission is smaller than (nλ H ) -δ P max is smaller than e -anλ H . Proof This is a slight variation of the previous proof. If we denote by N H (n, τ ) the number of nodes on the segment, we have E[e tN H (n,τ ) ] = (1 + λ H τ (e z -1))

n . The previous proof applies by replacing λ H by τ λ H . The accumulated energy has the expression P max

N H (n,τ ) N δ H (n) .
Further applying the previous reasoning to each of the random variables N H (n) and N H (n, τ ) gets the first result.

The second result is simpler to get because at level H the energy for transmission is equal to m -δ P max where m is the number of mobile in the streets. Since this number is larger than nλ H with probability larger 1 -exp(-anλ H ).

Proof (of Theorem ??)

We will prove first for G 1 (n, n -γ P max ). Let H n be a sequence of integer which tends to infinity. We consider the horizontal street of the central cross. The probability that all the intersections with the streets of level smaller than H n contains a relay is greater than (1exp(-ρ n p 2 r (q r /2) Hn )) 2 Hn (with q r = 1 -p r ) and finally greater than 1 -2 Hn exp(-ρ n p 2 r (q r /2) Hn ). This probability tends to 1 when H n = ⌊ 1 2 log(ρ n p 2 r )/ log(2/q r )⌋ since it is larger than (1 -x ν n exp(-x n )) with x n = e - √ ρnp 2 r and ν = log(2)/ log(2/q r ). Let us reduce H n if necessary in order to have nλ Hn > n γ/(δ-1) . Applying corollary ?? (with τ = 1), we cover all nodes in each streets of level H n or lower by a cumulated energy smaller than n -γ P max with probability smaller than 2 Hn exp(-n γ/(δ-1) ) since

H n = O(log n).
To terminate this part of the proof it suffices to notice that the proportion of the mobile nodes carried by all the streets of level H n compared to the total population of nodes tends to 1 in probability.

The part on the coverage of the giant component G ′ 1 (n, n -γ P max ) proceeds the same way but with the second result of Corollary ??.

Throughout the rest of the paper, we consider ρ n = n θ (or of the order of) for some 0 < θ < 1.

The following theorem is the main result of our paper and shows that increasing the path length decreases the accumulated energy. In fact, for n → ∞, the limiting energy goes to zero.

Theorem 3 In a hyperfractal city with n nodes, with mobile fractal dimension d F and relays fractal dimension d r , with the condition d r > (d F -1)θ the shortest path of accumulated energy E n = c E n (1-δ)(1-α) P max , where c E > 0 and α < d F -1 dr θ, between two nodes belonging to the giant component G 1 (n, E n ), passes through a number of hops:

D n = O(n 1-α d F -1 ) (12)
Although the source and the destination belong to G 1 (n, E n ), it is not necessary that all the nodes constituting the path also belong to G 1 (n, E n ), i.e., the path may include nodes that are more than one hop from the central cross.

Remark 2 We have the identity

E n P max 1/(δ-1) D d F -1 n = O(n d F -2 ). ( 13
)
Let us now prove the theorem.

Proof The main part of our proof is to consider the case when the source, denoted by m H , and the destination, m V , both stand on two different segments of the central cross. In this case, we consider the energy constraint 1 3 E n . We can easily extend the result to the case when the source and the destination stand anywhere in the giant component G 1 (n, E n ) by taking E n as energy constraint and the theorem follows.

When m H and m V are on the central cross, there exists a direct path that takes the direct route by staying on the central cross, more specifically, in Figure ??(a), the segments [SA],[AO],[OC], [CD]. Then, the path length is of order Θ(n) while the accumulated energy of order Θ(n 1-δ )P max .

In order to significantly reduce the order of magnitude of the path hop length, one must consider a diverted path with three fixed relays, as indicated in Figure ??(a). The diverted path proceeds into two streets of level x. Let T be the path. It is considered that, for 0 < β < 1/2,

x = β log(ρ n ) log(2/q r ) ( 14
)
The path is made of two times two segments: the segment of street [SA] on the central cross which corresponds to the distance from the source to the first fixed relay to a street of level x, and then the segment [AB] between this relay and the fixed relay to the crossing street of level x. The second part of the path is symmetric and corresponds to the connection between this relay and the destination through segment [BC] and [CD]. Denote by L(x, y) the distance from an arbitrary position on a street of level y to the first fixed relay to a street of level x. The probability that a fixed relay exists at a crossing of two streets of respective level x and y is 1 -exp(-ρ n p(x, y)). Since the spacing between the streets of level x is 2 -x , it is known from [?] that

L(x, y) ≤ 2 -x 1 -exp(-ρ n p(x, y))
where ρ n is the effective intensity of relays in the map The average distance from m H to the first relay to a street of level x is L(x, 0). Since ρ n p(x, 0) = p 2 r ρ 1-β n which tends polynomially to infinity when n → ∞ (with ρ n = n θ ). Therefore the probability that the relay does not exist at the intersection with the first street of level x decays exponentially fast and L(x, 0) ∼ 2 -x . If we assume that the two diverted routes from m H and m V , namely [AB] and [BC] have a relay at their intersection point, denoted B in Figure ??(a), then T is a valid path and has with high probability the following energy score:

E(T ) = O(L(x, 0)n 1-δ P max ) + O((nλ x ) 1-δ P max )
which holds under the condition of corollary ??, namely that nλ x → ∞ so that the estimates be valid almost surely. The number of nodes on the path, D(T ), satisfies with probability tending to 1, exponentially fast:

D(T ) = O(L(x, 0)n) + O(nλ x ).
The second term in the both right-hand side assumes the worst case when [AB] and [BC] segments span from end to end on their respective street. The condition for this is that nλ x → ∞. We have

nλ x = p 2 nρ -2 β dr (d F -1) n
which tends to infinity since ρ n = n θ , β < 1/2 and 2 β dr (d F -1)θ < 1. We detect that the main contributor of the accumulated energy are the segments [m H A] and [Cm V ] with a cumulated energy which is with high probability O(2 -x n 1-δ P max ) or

O nρ -2β/dr n 1-δ P max while [AB] and [BC], have a contribution which is O((nλ x ) 1-δ P max ), of order nρ -2β(d F -1)/dr n 1-δ
which is preponderant over the contribution of [m H A] and [Cm V ] (since δ > 1 and

d F > 2), thus E[T ] = O nρ -2β(d F -1)/dr n 1-δ P max .
But regarding the number of hops, the segments [m H A] and [Cm V ] have the preponderant contributions and

D[T ] = O nρ -2β/dr n
. In summary we have with high probability

       E[T ] = O n 1-δ ρ -2 β dr (d F -1)(1-δ) n P max D[T ] = O nρ -2 β dr n . ( 15
)
The probability that the two streets of level x have a fixed relay at their crossing is 1 -exp(-ρ n p(x, x)). Since ρ n p(x, x) = p 2 r ρ 1-2β n the probability tends to 1 when α < 1/2 . Thus the energy-delay balance formula of (??) is valid when β < 1/2.

By using α = 2 β dr (d F -1)θ, we can now complete the proof of Theorem ??.

In Theorem ??, it is always assumed that E n → 0, since α < 1. In this case, D n spans from O(n 1-1/(d F -1) ) to O(n) (corresponding to a path staying on the central cross). When the fractal dimension d F is large it does not make a large span. In fact, if E n is assumed to be constant, i.e. α = 1, then we can have a substantial reduction in the number of hops, as described in the following theorem.

Theorem 4 In a hyperfractal unit map with n nodes, with mobile fractal dimension d F and relays fractal dimension d r , and θ = 1, the shortest path of accumulated energy E n = v E P max with v E > 6, between two nodes belonging to the giant component G 1 (n, E n ), passes through a number of hops D n with:

D n = O n 1- 2 dr (1+1/d F )
The theorem shows the achievable limits of delay and number of hops when the constraint on the path energy is let loose. In fact, this allows taking the path with five fixed relays as in Figure ??(b). The condition on v E > 6 comes from the 5 relays plus the step required to escape the giant component.

Remark 3 When d r → 2 then D n = O(n 1/(d F +1
) ), and the hyperfractal model is behaving like a hypercube of dimension d F + 1. Notice that in this case D n tends to be O(1) when d F → ∞.

Proof In the proof of Theorem ??, it is assumed that x < log ρn 2 log(2/qr) in order to ensure that the number of hops on the route of level x tends to infinity. However, we can rise the parameter x in the range log ρn 2 log(2/qr) ≤ x < log n 2 log(2/q) . We have nλ x → 0. In this case, E(T ) → 2P max since the streets of level x are empty of nodes with probability tending to 1. Let us denote x = γ log n 2 log(2/q) with γ < 1. We have D(T ) = O(L(x, 0)n) = O(n 1-γ/dr ). Clearly, γ cannot be greater than 1 as, in this case, the two streets of level x will not hold a fixed relay with high probability and the packet will not turn at the intersection. Therefore the smallest order that one can obtain on the diverted path with three relays is limited to n 1-1/dr , which is not the claimed one.

To obtain the claimed order, one must use the diverted path with five fixed relays, as shown in Figure ??(b). The diverted path is composed by the segments:

[SA ′ ],[A ′ E],[EF ],[F G],[GC ′ ] and [C ′ D ′ ]. It is shown in [?]
that the order can be decreased to n 1-2/((1+1/d F )dr) .

Path maximum power

The next results revisit the previous theorems on the path accumulated energy in the alternative case of the imposed constraint on the path maximum power.

Theorem 5 Let d r > 2 (d F -1) d F +1 d F θ.
The shortest path of maximum power less than M n = n -δ(1-α) P max with α < 2 (d F -1)d F (d F +1)dr θ, between two nodes belonging to the giant component G ′ 1 (n, M n ), passes through a number of hops:

D n = O n 1-α/(d F -1)
It is important to note that although the orders of magnitude of path length D n are the same in both Theorem ?? and Theorem ??, the results consider two different giant components:

(accumulated) G 1 (n, E n ) and (maximum) G ′ 1 (n, M n ). Remark 4
We have the identity

M n P max 1/δ D d F -1 n = O(n d F -2 ). ( 16
)
Proof The proceed the same way as with Theorem ?? and we same construction with β < 1/2 we get again (??) (as we only need to replace 1 -δ by -δ) (with M [T ] as the maximum transmission power on the path T ):

       M [T ] = O n -δ ρ 2 β dr (d F -1)δ n P max D[T ] = O nρ -2 β dr n
But if we look carefully this would give a value for the α parameter which could not go beyond d F -1 dr θ while the theorem claims 2 (d F -1)d F (d F +1)dr θ which would make β to go slightly beyond 1/2.

To this end we rely on the construction of Figure ??(b) where we make a derivation from point E and point G which are intersection to streets of level y with

y = (1 -β) log ρ n log(2/q r ) ,
The derivation is needed because the point B ′ will not contain a relay with a probability tending to 1.

The points E and G are the first intersections from point B ′ with streets of level y which contains relays. The two streets intersect at point F . The probability that point F contains a relay is 1 -exp(-ρ n p(y, y)). Since ρ n p(y, y) = p 2 r ρ 1-β n and tends to infinity because β < 1, thus the probability tends to 1.

Similarly the average distance between B ′ and the points E and G is L(y, x) and is equivalent to 2 -y since the probability of holding a relay is 1 -exp(-ρ n p(x, y)) which tends to 1 since ρ n p(x, y) = p 2 r ρ 1/2 n . Thus the maximum energy in the new path T , M (T ), satisfies with high probability

M [T ] = O(L(x, 0)n 1-δ P max ) + O((nλ x ) 1-δ P max ) +O(L(y, x)(nλ y ) 1-δ P max ) D[T ] = O(L(x, 0)n) + O(nλ x ) + O(L(y, x)nλ y )
Here the condition taken from corollary ?? are less demanding since it is nλ x and nλ y to be tending to infinity when n → ∞ that is we want

   nλ x = p 2 nρ -2 β dr (d F -1) n → ∞ nλ y = p 2 nρ -2 1-β dr (d F -1) n → ∞ which is the direct consequence of the fact that 1 -β < β < d F d F +1
Taking away the non preponderant terms and using the fact that L(y, x) ∼ 2 -y and 2 -y λ y =

p 2 ρ -2(1-β)d F /dr n we get        M [T ] = O n -δ ρ 2 β dr (d F -1)δ n P max D[T ] = O n ρ -2 β dr n + ρ -2 (1-β)d F ) dr n (17) Since β < d F d F +1
the above formula is equivalent to (??). increasing β above d F d F +1 will not decrease the order of D[T ] as expected because we already know that this is the optimal order for the delay obtained in [?].

Corollary 2 Let θ = 1 the maximum path transmitting power between two points belonging to the giant component, G ′ 1 (n, M n ) be M n at most O(P max ). The number of hops D n on the shortest path is O n 1-2/(dr(1+1/d F ) .

Proof It suffices to consider θ = 1 and α → (d F -1)d F (d F +1) d r in Theorem ??.

This corollary gives the path length when no constraint on transmitting power exists (the maximum transmitting power allowed is the highest power for a transmission between two neighbors in the hyperfractal map). We obtain here the same results of [?], where an infinite radio range is considered, which is not a feasible result for mmWave technology deployments.

Remarks on the network throughput capacity

Let us consider the scaling of the network throughput capacity with constraints on the energy. In [?], the authors express the throughput capacity of random wireless networks as:

ζ(n) = Θ n 2 i∈G ω i (n) i,j∈G r ij . ( 18
)
where ζ(n) is the throughput capacity, defined as the expected number of packets delivered to their destinations per slot, ω i (n) is the expected transmission rate of each node i among all the nodes n and G is the giant component. In the following, denote by C the transmission rate of each node.

Using our results of Theorems ?? and ?? and substituting them in (??), we obtain the following corollary on a lower bound of the network throughput capacity with constraints on path energy.

Corollary 3 In a hyperfractal with n nodes, fractal dimension of nodes d F , α < 1 and C the transmission rate of each node when either -E n = O n (1-δ)(1-α) P max is the maximum accumulated energy of the minimal path between any pair of nodes in the giant component

G 1 (n, E n ) or -M n = O(n -δ(1-α) P max )
is the maximum path power of the minimal path between any pair of nodes in the giant component

G ′ 1 (n, M n ),
a lower bound on the network throughput is:

ζ(n) = Ω Cn α d F -1 (19)
Remark 5 We notice that with α < 1 and d F > 3 we have ζ(n) of order which can be smaller than n 1/2 which is less than the capacity in a random uniform network with omni-directional propagation as described in [?].

Remark 6 When α = 1, i.e. with no energy constraint E n = c E P max the path length can drop down to D n = O n 1-2/((1+1/d F )dr) and, in this case, we have ζ(n) = Ω(n 2/((1+1/d F )dr) ) which tends to be in O(n) when d F → ∞ and d r → 2. In this situation the capacity is of optimal order since D n tends to be O(1).

Variation of city areas, underground network

In the previous analysis we assumed that the area of the city was not varying with the number n of mobile nodes and the intensity ρ of relays. We assumed that the area stay constant (the unit square). Although we can imagine the number of mobile nodes can vary during the day, but it is difficult to imagine that the fixed relays infrastructure could be partially disabled accordingly (although it could be for the sake of energy saving).

By definition, cities are conceived of networks that constitute the essential functioning of cities [?]. The physical form of cities is the ultimate result of a multitude of hardware and software processes, constrained by the geometry of the man-made world. It is known that their population correlate to their level of activity, and although varying with cultural and functional backgrounds, the city density is more or less constant in the same area [?,?]. In the following the area A of the city will depend on the population of the mobile node: the quantity A(n) is proportional to n, with A(n) = Ω(n).

Under this model a mapping of a city in a square as the one we use for the hyperfractal archetypal model, will imply that the side of the square will be Ω( √ n). In other word, the energy needed to transmit a packet from one end of a street to the other end will something like P max = P 1 n δ/2 where P 1 is the maximum nominal emission power of the wireless nodes. The consequence will be that the parameter P max must be modified in the previous results, with the consequence that the energy balance may no longer tend to zero.

Theorem 6 Assuming θ < dr d F -1 , in variable area hyperfractal city with a bounded maximum emission power, when path accumulated energy tends to zero or stay bounded we necessary have the delay or hop count D n of order n 1/2 . Proof Following Theorem ?? it tends to zero when α < δ/2-1 δ-1 which is possible, assuming that θ < dr d F -1 which allows that θ can be significantly smaller than 1. But this would imply a hop count of greater than n 1-θ/dr which cannot go below the order n 1/2 . On the other hand in [?] we only consider the coverage by fixed relay, e.g. by assuming that the relays are connected via an underground wired network. In the following result we consider that we remove the hop by hop routing option between mobile nodes.

Theorem 7 In the hypothesis of the relays connected to an underground wired network, when θ > dr 4 , then for nodes in the giant component the energy balance is almost surely bounded and the hop count limited to one hop.

Proof We are in the conditions of [?] because the maximal radio range is O( √ n) and when θ > dr 4 , the covered fraction of the network by a single hop from the fixed relays tends to 1 when n → ∞.

Remark 7 We notice that in both situations the parameter θ can be significantly smaller than 1 but in the second case it cannot go below 1/2 which is the limit when d r → 2.

Numerical Evaluation

We evaluate the accuracy of the theoretical findings in different scenarios by comparing them to results obtained by simulating the events in a two-dimensional network. We developed a MatLab discrete time eventbased simulator following the model presented in Section ??. The length of the map is 1000 and, therefore, P max is just 1000 δ , where δ is the pathloss coefficient that will be chosen to be 2, 3 or 4, in line with millimeter-wave propagation characteristics. Figure ?? shows the trade-offs between accumulated end-to-end energy and hop count for a transmitter-receiver pair by selecting randomly pairs of vehicles in a hyperfractal map with n = 800, pathloss coefficient δ = 4, fractal dimension of nodes d F = 4.33 and fractal dimension of relays d r = 3. The plot shows the minimum accumulated energy for the end-to-end transmission for a fixed and allowed number of hops, k, in red circle markers. Note that the energy does not decrease monotonically as forcing to take a longer path may not allow to take the best path. However when considering the minimum accumulated energy of all paths up to a number of hops, the black star markers in Figure ??, the energy decreases and exhibits the behavior claimed in Theorem ??. That is, the minimum accumulated energy is indeed decreasing when the number of hops is allowed to grow (and the end-to-end communication is allowed to choose longer, yet cheaper, paths).

Let us further validate Theorem ?? through simulations performed for 100 randomly chosen transmitterreceiver pairs in hyperfractal maps with various configurations. We run simulations for different values of the number of nodes, n = 800 nodes and 1000 nodes respectively, different values of pathloss, δ = 2 and δ = 3 and different configurations of the hyperfractal map. The setups of the hyperfractal maps are: node fractal dimension d F = 4.33 and relay fractal dimension d r = 3.3 for the first setup and d F = 3.3 and d r = 2.3 for the second setup.

The results exhibited in Figure ?? are obtained by computing, for each of the transmitter-receiver pair, the minimum accumulated end-to-end energy for a path smaller than k, then averaging over the 100 results. The left-hand sides of the Figures ?? ( When changing the pathloss coefficient to δ = 3, the effect of Theorem ?? remains, as illustrated in Figure ?? for a hyperfractal setup of d F = 4.33, d r = 3, n = 800 nodes.

To validate the results of Theorem ?? on the variation of path length with the imposed constraint on maximum energy per node, we choose randomly 100 transmitter-receiver pairs belonging to the central cross and compute the shortest path by applying a

Conclusion

This paper presented results on the trade-offs between the end-to-end communication delay and energy spent on completing a transmission in millimeter-wave vehicular communications in urban settings by exploiting the "hyperfractal" model. This model captures selfsimilarity as an environment characteristic. The self-similar characteristic of the road-side infrastructure has also been incorporated.

Analytical bounds have been derived for the endto-end communication hop count under the constraints of total accumulated energy, and maximum energy per node, exhibiting the achievable trade-offs in a hyperfractal network. The work presented a lower bound on the network throughput capacity with constraints on path energy. Further examples of model fitting with data have been given. The analytical results have been validated using a discrete-time event-based simulator developed in Matlab.

Appendices

9.1 Proof of Lemma ??

Proof Let N H (n) be the number of nodes contained in a street of level H. Let z be a real number. By Chebyshev's inequality, we have when z > 0:

P N H (n) < nλ H 2 = P e -zN H (n) > e znλ H /2 ≤ E[e -zN H (n) ] e -znλ H /2
Since E[e zN H (n) ] = (1 + (e z -1)λ H ) n ;

E[e -zN H (n) ] e -znλ H /2 = exp n log 1 + (e -z -1)λ H + zλ H /2 . For |z| bounded there exists b > 0 such that |e z -1| ≤ b|z| and there exists c such that e z -1 ≤ z+cz 2 . For |x| bounded there exists d such that log(1+x) ≤ x-cx 2 . From these steps we obtain that, for sufficiently small |z|, one has: log 1 + (e

The proof of the second part of the lemma proceeds via similar reasoning, by using the inequality:

P (N H (n) > 2nλ H ) ≤ E[e zN H (n) ] e 2znλ H . (21)

Φ

Poisson process of the mobile nodes d F hyperfractal dimension of the mobile nodes density p geometric decay rate of mobile node density versus street depth, q = 1 -p Φ r Poisson process of fixed relays d r hyperfractal dimension of the fixed relay density p r geometric decay rate of fixed relay versus street depth, q r = 1 -p r X H set of the streets with depth index H

Figure 1 :

 1 Figure 1: Minneapolis traffic snapshot

Figure 2 :

 2 Figure 2: (top) Hyperfractal support; (bottom) Relays process construction.

Figure 3 :

 3 Figure 3: (top) Traffic and lights data in Adelaide; (bottom) Computation of d r

Figure 4 :

 4 Figure 4: Complete hyperfractal map with mobile nodes ("+") and relays ("o")

Figure 5 :

 5 Figure 5: (a) Diverted path with three fixed relays; (b) with five fixed relays.

Figure 6 :

 6 Figure6: Minimum accumulated end-to-end energy versus hops for a transmitter-receiver pair (fixed and allowed number of hops in red circles, and maximum number of hops in black stars).

  a) and ?? (b) show the variation of the minimum path accumulated energy for the path with the increase of the number of hops in a hyperfractal setup of d F = 4.33 and d r = 3 for n = 800 in ?? (a) and n = 1000 in ?? (b). The figures illustrate that, indeed, allowing the hop count to grow decreases the energy considerably. The decay of the maximum accumulated energy with the allowed number of hops is even more visible in logarithmic scale in the right side of the same figures. The decays remain substantial when changing the hyperfractal setup to d F = 3.3, d r = 2.3. Figures ?? (c) and ?? (d) show the results for n = 800 and n = 1000 in the new setup. The decay is dramatic as shown with a logarithmic scale. Even though there can be oscillations around the linearly decreasing characteristic, as seen in Figure ?? (d), left-hand side, the global behavior stays the same, decreasing, as better noticed in logarithmic scale in Figure ?? (d), right-hand side.

Figure 7 :

 7 Figure 7: Minimum accumulated end-to-end energy versus hops, averaging over 100 transmitter-receiver pairs, δ = 2, linear scale left side of sub-figures, logarithmic scale right side of sub-figures

Figure 8 :

 8 Figure 8: Minimum accumulated end-to-end energy versus hops, averaging over 100 transmitter-receiver pairs, δ = 3

Figure 9 :

 9 Figure 9: Path Maximum Energy trade-off with delay (i.e. path length)

  • • • -sub segments. Let H be the attained level. We do the same with the ordinate, let V the level obtained.

	The point obtained is exactly at the intersection of a
	West-East street of level H and a North-South street of
	level H. See Figure ??. The probability that a relay is
	at a given intersection of two streets of respective level

  -zN H (n) ] e -znλ H /2 ≤ e -anλ H .

	-z -1)λ H + z	λ H 2	≤ -z	λ H 2	+ bλ H z 2 -cλ 2 H z 2
			≤ -aλ H .
	which settles that
	E[e