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

07/11/2017
Publication GSI2017
OAI : oai:www.see.asso.fr:17410:22562
contenu protégé  Document accessible sous conditions - vous devez vous connecter ou vous enregistrer pour accéder à ou acquérir ce document.
- Accès libre pour les ayants-droit
 

Résumé

In this work we study a Poisson patterns of xed and mobile nodes on 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 e ect depends on the hyperfractal dimensions. Assuming propagation on axes, we prove results on the scaling of routing metrics and connectivity graph.

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

Collection

application/pdf Self-similar Geometry for Ad-Hoc Wireless Networks: Hyperfractals Philippe Jacquet, Dalia Popescu
Détails de l'article
contenu protégé  Document accessible sous conditions - vous devez vous connecter ou vous enregistrer pour accéder à ou acquérir ce document.
- Accès libre pour les ayants-droit

Self-similar Geometry for Ad-Hoc Wireless Networks: Hyperfractals
application/pdf Self-similar Geometry for Ad-Hoc Wireless Networks: Hyperfractals (slides)

Média

Voir la vidéo

Métriques

0
0
707.96 Ko
 application/pdf
bitcache://722de450f2cc18baedc1e3074c5b2100fcd17184

Licence

Creative Commons Aucune (Tous droits réservés)

Sponsors

Sponsors Platine

alanturinginstitutelogo.png
logothales.jpg

Sponsors Bronze

logo_enac-bleuok.jpg
imag150x185_couleur_rvb.jpg

Sponsors scientifique

logo_smf_cmjn.gif

Sponsors

smai.png
logo_gdr-mia.png
gdr_geosto_logo.png
gdr-isis.png
logo-minesparistech.jpg
logo_x.jpeg
springer-logo.png
logo-psl.png

Organisateurs

logo_see.gif
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/17410/22562</identifier><creators><creator><creatorName>Philippe Jacquet</creatorName></creator><creator><creatorName>Dalia Popescu</creatorName></creator></creators><titles>
            <title>Self-similar Geometry for Ad-Hoc Wireless Networks: Hyperfractals</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2018</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Wed 7 Mar 2018</date>
	    <date dateType="Updated">Wed 7 Mar 2018</date>
            <date dateType="Submitted">Wed 19 Sep 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">722de450f2cc18baedc1e3074c5b2100fcd17184</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>37280</version>
        <descriptions>
            <description descriptionType="Abstract">In this work we study a Poisson patterns of xed and mobile nodes on 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 e ect depends on the hyperfractal dimensions. Assuming propagation on axes, we prove results on the scaling of routing metrics and connectivity graph.
</description>
        </descriptions>
    </resource>
.

Self-similar Geometry for Ad-Hoc Wireless Networks: Hyperfractals Philippe Jacquet and Dalia Popescu Bell Labs, Nokia, France, {philippe.jacquet, dalia-georgiana.herculea}@nokia-bell-labs.com Abstract In this work we study a Poisson patterns of fixed and mobile nodes on lines designed for 2D urban wireless networks. The particularity of the model is that, in addition to capturing the irregularity and variabi- lity 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 propagation on axes, 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 analyze wireless networks that exhibit a high degree of randomness [1, 2]. For the modeling of networks with high degree of regularity, lattice structures such as Manhattan grid are often deployed [6]. Recently introduced models of fractal repartition [3,4] have 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 Section 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 p0 the probability that the mobile node is located on the cross according to a uniform distribution and q0 the complementary probability. With probability q0 /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 ≥ 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 Figure 2. Taking the unit density for the initial map, the density of mobile nodes in a quadrant is q0 /4. Let µH be the density of mobile nodes assigned on a street of level H. It satisfies: µH = (p0 /2)(q0 /2)H (1) Figure 1: Indianapolis 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Figure 2: Hyperfractal support 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 q0 /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, dm, 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 q0 /4. One obtains:  1 2 dm = q0 /4 thus dm = log( 4 q0 ) log 2 > 2 (2) This property can only be explained via the concept of measure. Notice that when p0 → 0 then dm → 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 p2 , 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 Figure 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 dr: dr = 2 log(2/q) log 2 . (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 2H+V of such crossings. We have: p(H, V ) = p2 (q/2)H+V . (4) Thus the probability that such crossing is selected to host a relay is 1 − (1 − p(H, V )) 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 ρ, 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 LH(ρ) and satisfies the identity: LH(ρ) = X V ≥0 2V (1 − exp(−p(H, V )ρ)) . (5) The average total number of relays in the city, R(ρ), has the expression: R(ρ) = X H,V ≥0 2H+V (1 − exp(−p(H, V )ρ)) (6) Furthermore: R(ρ) = O(ρ2/dr log ρ) (7) A complete Hyperfractal map containing both mobile nodes and relays is presented in Figure 4. 3 Routing The routing table will be computed according to a minimum cost path over a cost matrix [tij] where tij represents the cost of directly transmitting a packet from ) 2 / (q p 2 ) 2 / (q 2 ) 2 / (q 2 ) 2 / (q 2 ) 2 / (q ) 2 / (q p ) 2 / (q p ) 2 / (q p Figure 3: Relay placement procedure 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 mobile nodes relays Figure 4: Mobiles and relays 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 mij and satisfies: mij = min k {mik + tkj} , ∀(i, j), (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      tij = 1 if nodes i and j are aligned and @k such that d(i, j) = d(i, k) + d(k, j) tij = ∞ otherwise 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 mij = ∞. 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 [1 2 , 1 2 ] . Theorem 1. The fraction of mobile nodes in the giant component tends to 1 when ρ → ∞ and the average number of mobile nodes outside the giant component is O(Nρ−2(dm−2)/dr ) when ρ → ∞. Remark: For a configuration where dm − 2 > dr/2, the average number of mobile nodes outside the giant component tends to zero when ρ = 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−ρp2 (q/2)H . On each line of level H the density of mobiles is (p0 /2)(q0 /2)H . Furthermore, there are 2H of such lines intersecting each of the lines forming the central cross. We multiply by 2 and obtain g(ρ), the cumulated density of lines connected to the central cross with a single relay: g(ρ) = 2 X H≥1 2H (p0 /2)(q0 /2)H (1 − e−ρp2 (q/2)H ) (9) The quantity g(ρ) 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(ρ). Let E(ρ, N) be the average number of mobile nodes outside the giant component. We have E(ρ, N) ≤ Ne(ρ) represented with an harmonic sum: e(ρ) = 1 − 2p − g(ρ) = 2 X H≥1 2H (p0 /2)(q0 /2)H e−ρp2 (q/2)H (10) The Mellin Transform e∗ (s) of e(ρ) is : e∗ (s) = Z ∞ 0 e(ρ)ρs−1 dρ = Γ(s)2 X H≥1 2H ( p0 2 )( q0 2 )H (p2 (q/2)H )−s = p0 q0 (p2 q 2 )−s 1 − q0( q 2 )−s Γ(s) (11) The Mellin transform is defined for R(s) > 0 and has s a simple pole at s0 = log(1/q0 ) log(2/q) = −2(dm−2) dr . Using the inverse Mellin transform e(ρ) = 1 2iπ R c+i∞ c−i∞ e∗ (s)ρ−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 equation 2 and relay fractal dimension from equation 3, one gets e(ρ) = O(ρ−s0 ) which proves the theorem. Notice than when s0 > 1 we have E(ρ, N) → 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 dm and dr is: DN = O  N1− 2 (1+1/dm)dr  (12) Proof. Mobile node mH on a line of level H sends a packet to mV , on a line of level V as in Figure 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. V mH mV x y mH mV y a) b) Figure 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(−ρp(a, b)). Since such crossings are regularly spaced by interval 2−a we get: L(a, b) ≤ 2−a 1 − exp(−ρp(a, b)) . (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µ0L(x, 0) + 2Nµ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 Figure 5,b) has to be added. Given the probabilities of existence of relays and the densities of lines computed according to the logic described in Section 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: DN = O(Nρ− 2 (1+1/dm)dr ) (14) 4 Numerical Results The configuration studies is chosen as to validate the constraint given by The- orem 1, dm − 2 > dr 2 , dm