Self-similar Geometry for Ad-Hoc Wireless Networks: Hyperfractals

Abstract

In this work we study a Poisson patterns of fixed and mobile nodes distributed on straight lines designed for 2D urban wireless networks. The particularity of the model is that, in addition to capturing the irregularity and variability of the network topology, it exploits self-similarity, a characteristic of urban wireless networks. The pattern obeys to “Hyperfractal” measures which show scaling properties corresponding to an apparent dimension larger than 2. The hyperfractal pattern is best suitable for capturing the traffic over the streets and highways in a city. The scaling effect depends on the hyperfractal dimensions. Assuming radio propagation limited to streets, we prove results on the scaling of routing metrics and connectivity graph.

1 Introduction

The modeling of topology of ad hoc wireless networks makes extensive use of stochastic geometry. Uniform Poisson spatial models have been successfully applied to the analysis of wireless networks which exhibit a high degree of randomness [1, 2]. Other modeling of networks such as lattice structures like Manhattan grid [6] are often used for their high degree of regularity.

We recently introduced new models based on fractal repartition [3, 4] which are proven to model successfully an environment displaying self-similarity characteristics. Results have shown, [4], that a limit of the capacity in a network with a non-collaborative protocol is inversely proportional to the fractal dimension of the support map of the terminals. In the model of [4], the nodes have locations defined as a Poisson shot inside a fractal subset, for example a Cantor set.

By definition, a fractal set has a dimension smaller than the Euclidean dimension of the embedding vector space; it can be arbitrary smaller. In this work we study a recently introduced model [5], which we named “Hyperfractal”, for the ad hoc urban wireless networks. This model is focused on the self-similarity of the topology and captures the irregularity and variability of the nodes distribution. The hyperfractal model is a Poisson shot model which has support a measure with scaling properties instead of a pure fractal set. It is a kind of generalization of fractal Poisson shot models, and in our cases it will have a dimension that is larger than the dimension of the underlying Euclidean space and this dimension can be arbitrarily large. This holds for every case of our urban traffic models.

A novel aspect is that the radio model now comprises specific phenomenons such as the “urban canyon” propagation effect, a characteristic property of metropolitan environments with tall or medium sized buildings.

Using insights from stochastic geometry and fractal geometry, we study scaling laws of information routing metrics and we prove by numerical analysis and simulations the accuracy of our expressions.

The papers is organized as follows. Section 2 reminds the newly introduced geometrical model and its basic properties. Section 3 gives results on the connectivity graph and information routing metrics that are validated through simulations in Sect. 4.

2 System Model and Geometry

Let us briefly remind the new model we introduced in a recent work [5] and its basic properties. The map is assumed to be the unit square and it is divided into a grid of streets similar to a Manhattan grid but with an infinite resolution. The horizontal (resp vertical streets) streets have abscissas (resp. ordinates) which are integer multiple of inverse power of two. The number of binary digits after the coma minus indicates the level of the street, starting with the street with abscissas (resp ordinate) 1 / 2 being at level 0. Notice that these two streets make a central cross.

This model can be modified and generalized by taking integer multiple of inverse power of any other number called the street-arity, the street-arity could change with the levels, the central cross could be an initial grid of main streets, etc.. Figure 1 shows a map of Indianapolis as an example. It could also model the pattern of older cities in the ancient world. In this case, the model would display a similar hierarchical street distribution but plugged into a more chaotic geometric pattern instead that of the grid pattern.

2.1 Hyperfractal Mobile Nodes Distribution

The process of assigning points to the streets is performed recursively, in iterations, similar to the process for obtaining the Cantor Dust.

The two streets of level 0 form a central cross which splits the map in exactly 4 quadrants. We denote by probability $p'$ the probability that the mobile node is located on the cross according to a uniform distribution and $q'$ the complementary probability. With probability $q'/4$, it is located in one the four quadrants. The assignation procedure recursively continues and it stops when the mobile node is assigned to a cross of a level $m\ge 0$. A cross of level m consists of two intersecting segments of streets of level m. An example of a decreasing density in the street assignment process performed in $L=4$ steps is given in Fig. 2.

Fig. 1.

Indianapolis

Fig. 2.

Hyperfractal support

Taking the unit density for the initial map, the density of mobile nodes in a quadrant is $q'/4$. Let $\mu _H$ be the density of mobile nodes assigned on a street of level H. It satisfies:

$$\begin{aligned} \mu _H=(p'/2)(q'/2)^H \end{aligned}$$

(1)

The measure (understood in the Lebesgue meaning) which represents the actual density of mobile nodes in the map has strong scaling properties. The most important one is that the map as a whole is identically reproduced in each of the four quadrants but with a weight $q'/4$ instead of 1. Thus the measure has a structure which recalls the structure of a fractal set, such as the Cantor map. A crucial difference lies in the fact that its dimension, $d_m$, is in fact greater than 2, the dimension of the underlying Euclidean space. Indeed, considering the map in only half of its length consists into considering the same map but with a reduced weight by a factor $q'/4$. One obtains:

$$\begin{aligned} \left( \frac{1}{2}\right) ^{d_m}=q'/4 \qquad \text {thus}\qquad d_m=\frac{\log (\frac{4}{q'})}{\log 2}>2 \end{aligned}$$

(2)

This property can only be explained via the concept of measure. Notice that when $p'\rightarrow 0$ then $d_m\rightarrow 2$ and the measure tends to the uniform measure in the unit square (weak convergence).

2.2 Canyon Effect and Relays

Due to the presence of buildings, the radio wave can hardly propagate beyond the streets borders. Therefore, we adopt the canyon propagation model where the signal emitted by a mobile node propagates only on the axis where it stands on. Considering the given construction process, the probability that a mobile node is placed in an intersection tends to zero and mobiles positioned on two different streets will never be able to communicate. Therefore, one needs to add relays in some street crossings in order to guarantee connectivity and packet delivery.

We again make use of a hyperfractal process to select the intersections where a relay will be placed. We denote by p a fixed probability and $q=1-p$ the complementary probability. A run for selecting a street crossing requires two processes: the in-quadrant process and the in-segment process. The selection starts with the in-quadrant process as follows. (i) With probability $p^2$, the selection is the central crossing of the two streets of level 0; (ii) with probability p(q / 2), the relay is placed in one of the four street segments of level 0 starting at this point: North, South, West or East, and the process continues on the segment with the in-segment process. Otherwise, (iii) with probability $(q/2)^2$, the relay is placed in one of the four quadrants delimited by the central cross and the in-quadrant process recursively continues.

The process of placing the relays is illustrated in Fig. 3. We perform M independent runs of selection. If one crossing is selected several times (e.g. the central crossing), only one relay will be installed in the respective crossing. This reduction will mean that the number of actually placed relays will be much smaller than M.

Some basics results following the construction process and shown in [5] are as following. The relay placement is hyperfractal with dimension $d_r$:

$$\begin{aligned} d_r=2\frac{\log (2/q)}{\log 2}. \end{aligned}$$

(3)

Let p(H, V) be the probability that the run selects a crossing of two streets, one horizontal street of level H and one vertical street of level V. There are $2^{H+V}$ of such crossings. We have:

$$\begin{aligned} p(H,V)=p^2(q/2)^{H+V}. \end{aligned}$$

(4)

Thus the probability that such crossing is selected to host a relay is $1-\left( 1-p(H,V)\right) ^M$ which is equivalent to $1-\exp (-Mp(H,V))$ when M is large. From now, we assume that the number of crossing selection run is a Poisson random variable of mean $\rho$, and the probability that a crossing hosts a relay is now exactly $1-\exp (-Mp(H,V))$.

The average number of relays on a streets of level H is denoted by $L_H(\rho )$ and satisfies the identity:

$$\begin{aligned} L_H(\rho )=\sum _{V\ge 0} 2^V\left( 1-\exp (-p(H,V)\rho )\right) . \end{aligned}$$

(5)

The average total number of relays in the city, $R(\rho )$, has the expression:

$$\begin{aligned} R(\rho )=\sum _{H,V\ge 0} 2^{H+V}\left( 1-\exp (-p(H,V)\rho )\right) \end{aligned}$$

(6)

Furthermore:

$$\begin{aligned} R(\rho )=O(\rho ^{2/d_r}\log \rho ) \end{aligned}$$

(7)

A complete Hyperfractal map containing both mobile nodes and relays is presented in Fig. 4.

Fig. 3.

Relay placement procedure

Fig. 4.

Mobiles and relays

3 Routing

The routing table will be computed according to a minimum cost path over a cost matrix $[t_{ij}]$ where $t_{ij}$ represents the cost of directly transmitting a packet from node i to node j. The min cost path from node i to node j which optimizes the relaying nodes (either mobile nodes or fixed relays) is denoted $m_{ij}$ and satisfies:

$$\begin{aligned} m_{ij}=\displaystyle \mathop {\min }_{k}\left\{ m_{ik}+t_{kj}\right\} , \ \forall (i, j), \end{aligned}$$

(8)

Furthermore, we study here the nearest neighbor routing scenario considering the canyon effect. In this strategy the next relay is always a next neighbor on an axis, i.e. there exist no other nodes between the transmitter and the receiver. Thus

$$ {\left\{ \begin{array}{ll} t_{ij}=1 &{} \text {if nodes}~i\,\, \text {and}\,\, j\,\, \text {are aligned} \\ &{}\text {and } \not \exists k~\text {such that}~ d(i,j)=d(i,k)+d(k,j)\\ t_{ij}= \infty &{} \text {otherwise} \\ \end{array}\right. } $$

Due to the canyon effect some nodes can be disconnected from the rest of the network, several connected components may appear and some routes may not exist. In the case node i and node j cannot communicate $m_{ij}=\infty$. Therefore, a very important implication in the routing process has the connectivity of the hyperfractal. Next, we study this connectivity by looking at the properties of the giant component.

3.1 Giant Component

We restrict our analysis to the giant component of the network. Following the construction process which assigns a relay in the central cross with high probability, the giant component will be formed around this relay with coordinates $[\frac{1}{2},\frac{1}{2}]$.

Theorem 1

The fraction of mobile nodes in the giant component tends to 1 when $\rho \rightarrow \infty$ and the average number of mobile nodes outside the giant component is $O(N \rho ^{-2(d_m-2)/d_r})$ when $\rho \rightarrow \infty$.

Remark: For a configuration where $d_m-2>d_r/2$, the average number of mobile nodes outside the giant component tends to zero when $\rho =O(N)$.

Let us now sketch a proof that will show the validity of Theorem 1.

Proof

Given a horizontal line of level H, the probability that the line is connected to the vertical segment in the central cross is $1-e^{-\rho p^2(q/2)^H}$.

On each line of level H the density of mobiles is $(p'/2)(q'/2)^H$.

Furthermore, there are $2^H$ of such lines intersecting each of the lines forming the central cross. We multiply by 2 and obtain $g(\rho )$, the cumulated density of lines connected to the central cross with a single relay:

$$\begin{aligned} g(\rho )=2 \sum _{H \ge 1} 2^H (p'/2)(q'/2)^H (1-e^{-\rho p^2(q/2)^H}) \end{aligned}$$

(9)

The quantity $g(\rho )$ is a lower bound of the fraction of mobile nodes connected to the central cross. It is indeed a lower bound as a line can be connected to the central cross via a sequence of relays, while above we consider the lines which are connected via a single relay. The fraction of nodes connected to the central nodes including those nodes in the central relay (which are in density 2p) is therefore lower bounded by the quantity $2p+g(\rho )$.

Let $E(\rho ,N)$ be the average number of mobile nodes outside the giant component. We have $E(\rho ,N) \le Ne(\rho )$ represented with an harmonic sum:

$$\begin{aligned} e(\rho )=1-2p-g(\rho )=2 \sum _{H \ge 1} 2^H (p'/2)(q'/2)^H e^{-\rho p^2(q/2)^H} \end{aligned}$$

(10)

The Mellin Transform $e^*(s)$ of $e(\rho )$ is:

$$\begin{aligned} e^*(s)=\int _0^\infty e(\rho )\rho ^{s-1}d\rho =\varGamma (s)2 \sum _{H \ge 1} 2^H(\frac{p'}{2})(\frac{q'}{2})^H (p^2(q/2)^H)^{-s}=\frac{p'q'(\frac{p^2q}{2})^{-s}}{1-q'^(\frac{q}{2})^{-s}}\varGamma (s) \end{aligned}$$

(11)

The Mellin transform is defined for $R(s)>0$ and has s a simple pole at $s_0=\frac{\log (1/q')}{\log (2/q)}=\frac{-2(d_m-2)}{d_r}$.

Using the inverse Mellin transform $e(\rho )=\frac{1}{2i\pi }\int _{c-i\infty }^{c+i\infty }e^*(s)\rho ^{-s}ds$ for any given number c within the definition domain of $e^*(s)$, following the similar analysis as with the expressions used for mobile fractal dimension from Eq. 2 and relay fractal dimension from Eq. 3, one gets $e(\rho )=O(\rho ^{-s_0})$ which proves the theorem.

Notice than when $s_0>1$ we have $E(\rho ,N)\rightarrow 0$. Therefore, the connectivity graph tends to contain all the nodes.

3.2 Routing on the Giant Component

Let us now remind shortly a result on routing from [5] performed on the giant component. In the context of nearest neighbor routing strategy, the following holds:

Theorem 2

The average number of hops in a Hyperfractal of N mobile nodes and hyperfractal dimensions of mobile nodes and relays $d_m$ and $d_r$ is:

$$\begin{aligned} D_N=O\left( N^{1-\frac{2}{(1+1/d_m)d_r}}\right) \end{aligned}$$

(12)

Proof

Mobile node mH on a line of level H sends a packet to mV, on a line of level V as in Fig. 5(a) [5]. The dominant case is $V=H=0$. As lines H and V have high density of population, the packet will be diverted by following a vertical line of level $x>0$ with a much lower density. A similar phenomenon happens towards mobile mV. We will consider [5] that $x=y$.

Fig. 5.

Routing in a Hyperfractal (a) intermediate levels x and y, (b)extra intermediate levels

For changing direction in the route, it is mandatory that a relay exists at the crossing. Let L(a, b) be the average distance between a random mobile node on a street of level a to the first relay to a street of level b. Every crossing between streets of level a and b is independent and holds a relay with probability $1-\exp (-\rho p(a,b))$. Since such crossings are regularly spaced by interval $2^{-a}$ we get:

$$\begin{aligned} L(a,b)\le \frac{2^{-a}}{1-\exp (-\rho p(a,b))}. \end{aligned}$$

(13)

Let us assume that the two streets of level x have a relay at their intersection. In this case, the average number of traversed nodes is upper bounded by $2N\mu _0 L(x,0)+2N\mu _x$.

In [5], the authors showed that the probability that there exists a valid relay at level x street intersection is very low, therefore an intermediate level (see Fig. 5b) has to be added. Given the probabilities of existence of relays and the densities of lines computed according to the logic described in Sect. 2, the order of the number of nodes that the packet hops on towards its destination is obtained to be as [5]: The minimized value of the number of hops is, thus:

$$\begin{aligned} D_N=O(N\rho ^{-\frac{2}{(1+1/d_m)d_r}}) \end{aligned}$$

(14)

4 Numerical Results

The configuration studies is chosen as to validate the constraint given by Theorem 1, $d_m-2>\frac{d_r}{2}$, $d_m=d_r=3$, $N=\rho =200, 300, 400, 500, 800, 1200, 1600$ nodes.

Figure 6 illustrates the variation of fraction of mobile nodes that are not included in the giant component. As claimed by Theorem 1, the fraction decreases with the increase of number of mobiles. Furthermore, the actual number of mobiles comprised in the giant component nodes follows the scaling law $O(N^{\frac{1}{3}})$ as shown in Fig. 7.

Fig. 6.

Fraction of points in the giant component

Fig. 7.

Number of points outside the giant component

5 Conclusion

This work studies routing properties and scaling of a recently introduced geometrical model for wireless ad-hoc networks, called “Hyperfractal”. This model which is best fit for urban wireless networks as it captures not only the irregularity and variability of the node configuration but also the self-similarity of the topology. We showed here that the connectivity properties of the Hyperfractal exhibits good properties, supporting the Hyperfractal as a new topology for urban ad-hoc wireless networks.