Node Density and Delay in Large-Scale Wireless Networks with Unreliable Links Shizhen Zhao,Xinbing Wang Department of Electronic Engineering Shanghai Jiao Tong University,China Email:[shizhenzhao,xwang8@sjtu.edu.cn Abstract-We study the delay performance in large-scale wire- power required to maintain full connectivity increases with less multi-hop networks with unreliable links from percolation the size of the network).Hence,it is necessary to introduce a perspective'.Previous works [12][3][11]have showed that the slightly weaker connectivity criterion,in which we only ensure end-to-end delay scales linearly with the source-to-destination distance,and thus the delay performance can be characterized that a large portion of the network nodes are connected via by the delay-distance ratio However,the range of y,which may multiple hops with each other.Thanks to percolation theory be the most important parameter for delay,remains unknown. [10]15],it is possible to achieve this weaker connectivity in We expect that y may depend heavily on the node density A large-scale networks with power bounded per node. of a wireless multi-hop network.In this paper,we investigate the fundamental relationship between y and A.Obtaining the Percolation theory [10],especially continuum percolation,is exact value of y(A)is extremely hard,mainly because of the a powerful mathematical tool when analyzing the connectivity dynamically changing network topologies caused by the link and the delay of wireless networks.An important and gener- unreliability.Instead,we provide both upper bound and lower al model of Continuum Percolation is Random Connection bound to the delay-distance ratio (A).Simulations are conducted Model (RCM).RCM describes the behavior of connected to verify our theoretical analysis. components in an infinitely large random geometric graph, Index Terms-Connectivity,Delay,Density in which nodes are distributed according to poisson point process with node density A,and two nodes share a link with probability h(r)(r is the distance between the two nodes). I.INTRODUCTION A classical result of RCM points out a fundamental phase Large-scale wireless multi-hop networks are fast becoming transition effect at a critical node densityλe∈(0，o).For the most preferred way for communication in outdoor envi- A>Ac(supercritical),there exists a unique connected compo- ronment [1].Each user in a wireless multi-hop network could nent containing a large portion of nodes in the infinitely large initiate a communication in a multi-hop fashion without of network (we also say the network is percolated).However,for the aid of any network infrastructure.Thus,the maintenance A<A(subcritical),all connected component in the network cost for communication networks can be significantly reduced. are finite almost surely. However,relays of a wireless multi-hop network may be also Applying percolation theory to large-scale wireless multi- users,which are highly unreliable due to the unexpected user hop networks,we introduce two important concepts,i.e.,the behavior and the time-varying wireless channel.Thus,it is instantaneous connectivity and the long-term connectivity.The highly possible that a connection may get lost during data Instantaneous connectivity requires wireless networks perco- transmission.in which case the data has to wait at some lated at all the time instances.While the long-term connectivity node and resume its transmission after the reestablishment of only requires wireless network percolated in the long run (we the network connection.The lost of connection could cause will elaborate it more clearly later in sectionII-B1).The instan- significant delay to data transmission.Therefore,it is very taneous critical density,denoted by Ar,is the critical density critical to provide some delay guarantee for wireless multi-hop for the instantaneous connectivity and the long-term critical networks.Note that the data communication reliability can be density,denoted by AL,is the critical density for the long-term improved by some back-up routes,and it is usually easier to connectivity.Long-term connectivity is a weaker criterion for find more routes when the node density is higher.Hence,we connectivity,thus AL<Ar.To ensure connectivity,we assume expect that the data communication delay may depend heavily that入>入L throughout this paper. on the node density.Our goal in this paper is to quantify the In large-scale wireless networks,delay is mainly composed fundamental relationship between node density and delay. of the waiting delay and the propagation delay.The waiting de- To make our study meaningful,we assume that the large- lay is caused by the loss of connection at some time instances, scale wireless network is connected.Full connectivity [4]can which is due to the lack of instantaneous connectivity.Packets ensure the successful communication between each node pair must wait for some time until the connection is reestablished. in a wireless network.However,it is overly power consuming Usually,such a waiting time is in the order of seconds, to achieve full connectivity in large-scale networks (i.e.,the minutes or more.The propagation delay is the time required for a packet to transverse a link whenever the link is active. An earlier version of this paper appeared in ACM MobiCom 2011 [19] Mostly,the propagation delay is in the order of milliseconds
1 Node Density and Delay in Large-Scale Wireless Networks with Unreliable Links Shizhen Zhao, Xinbing Wang Department of Electronic Engineering Shanghai Jiao Tong University, China Email: {shizhenzhao,xwang8}@sjtu.edu.cn Abstract—We study the delay performance in large-scale wireless multi-hop networks with unreliable links from percolation perspective1 . Previous works [12][3][11] have showed that the end-to-end delay scales linearly with the source-to-destination distance, and thus the delay performance can be characterized by the delay-distance ratio γ. However, the range of γ, which may be the most important parameter for delay, remains unknown. We expect that γ may depend heavily on the node density λ of a wireless multi-hop network. In this paper, we investigate the fundamental relationship between γ and λ. Obtaining the exact value of γ(λ) is extremely hard, mainly because of the dynamically changing network topologies caused by the link unreliability. Instead, we provide both upper bound and lower bound to the delay-distance ratio γ(λ). Simulations are conducted to verify our theoretical analysis. Index Terms—Connectivity, Delay, Density I. INTRODUCTION Large-scale wireless multi-hop networks are fast becoming the most preferred way for communication in outdoor environment [1]. Each user in a wireless multi-hop network could initiate a communication in a multi-hop fashion without of the aid of any network infrastructure. Thus, the maintenance cost for communication networks can be significantly reduced. However, relays of a wireless multi-hop network may be also users, which are highly unreliable due to the unexpected user behavior and the time-varying wireless channel. Thus, it is highly possible that a connection may get lost during data transmission, in which case the data has to wait at some node and resume its transmission after the reestablishment of the network connection. The lost of connection could cause significant delay to data transmission. Therefore, it is very critical to provide some delay guarantee for wireless multi-hop networks. Note that the data communication reliability can be improved by some back-up routes, and it is usually easier to find more routes when the node density is higher. Hence, we expect that the data communication delay may depend heavily on the node density. Our goal in this paper is to quantify the fundamental relationship between node density and delay. To make our study meaningful, we assume that the largescale wireless network is connected. Full connectivity [4] can ensure the successful communication between each node pair in a wireless network. However, it is overly power consuming to achieve full connectivity in large-scale networks (i.e., the 1An earlier version of this paper appeared in ACM MobiCom 2011 [19] power required to maintain full connectivity increases with the size of the network). Hence, it is necessary to introduce a slightly weaker connectivity criterion, in which we only ensure that a large portion of the network nodes are connected via multiple hops with each other. Thanks to percolation theory [10][15], it is possible to achieve this weaker connectivity in large-scale networks with power bounded per node. Percolation theory [10], especially continuum percolation, is a powerful mathematical tool when analyzing the connectivity and the delay of wireless networks. An important and general model of Continuum Percolation is Random Connection Model (RCM). RCM describes the behavior of connected components in an infinitely large random geometric graph, in which nodes are distributed according to poisson point process with node density λ, and two nodes share a link with probability h(r) (r is the distance between the two nodes). A classical result of RCM points out a fundamental phase transition effect at a critical node density λc ∈ (0, ∞). For λ > λc (supercritical), there exists a unique connected component containing a large portion of nodes in the infinitely large network (we also say the network is percolated). However, for λ < λc (subcritical), all connected component in the network are finite almost surely. Applying percolation theory to large-scale wireless multihop networks, we introduce two important concepts, i.e., the instantaneous connectivity and the long-term connectivity. The Instantaneous connectivity requires wireless networks percolated at all the time instances. While the long-term connectivity only requires wireless network percolated in the long run (we will elaborate it more clearly later in sectionII-B1). The instantaneous critical density, denoted by λI , is the critical density for the instantaneous connectivity and the long-term critical density, denoted by λL, is the critical density for the long-term connectivity. Long-term connectivity is a weaker criterion for connectivity, thus λL < λI . To ensure connectivity, we assume that λ > λL throughout this paper. In large-scale wireless networks, delay is mainly composed of the waiting delay and the propagation delay. The waiting delay is caused by the loss of connection at some time instances, which is due to the lack of instantaneous connectivity. Packets must wait for some time until the connection is reestablished. Usually, such a waiting time is in the order of seconds, minutes or more. The propagation delay is the time required for a packet to transverse a link whenever the link is active. Mostly, the propagation delay is in the order of milliseconds
3 Therefore,it is negligibly small compared to the waiting delay.our theoretical findings.We summarize the paper in Section For ease of analysis,we first ignore the impact of propagation VII.Some proofs of the theorems and lemmas are presented delay and will consider its effect in the last. in section V. We study the delay performance for flooding in large-scale wireless networks.Ignoring the propagation delay,previous works[l2][3][1l]have showed that if入z<入<入，the II.BACKGROUND AND NETWORK MODEL end-to-end delay scales linearly with the source-to-destination In this section,we introduce some background knowledge distance ((A)>0),and that if A>Ar,the end-to-end and the network model. delay scales sub-linearly with distance ((A)=0).However, these results are far from enough to provide reasonable delay A.Background guarantee.It remains extremely important to find out the exact 1)Poisson Point Process:In large-scale wireless multi-hop value or the lower and upper bounds of y(A). networks.it is extremely difficult to predict the exact locations In this paper,we present a theoretical analysis about the of different users (nodes)due to the random behavior of differ- flooding delay in wireless multi-hop networks with unreliable ent users.To model the location-randomness,we use Poisson links.We first ignore the propagation delay and find the upper Point Process [18].One way to visualize the Poisson Point and lower bounds of y(A).For the upper bound,we first find Process is to assume that all users are distributed uniformly a path between two nodes using percolation theory.And then in a given area,e.g.,An2 nodes are evenly distributed in a we calculate the number of hops along this path using another n x n area.If we let n-oo,then the distribution of these coupling technique and the delay at each hop.We obtain the random processes(indexed by n)will converge in distribution result of upper bound by multiplying the above two items.For to Poisson Point Process with rate A. the lower bound,we first introduce a concept called cluster Poisson Point Process has the following two properties: to cluster transmission process and establish the relationship The superposition of two independent Poisson Point between delay and the cluster to cluster transmission process, Processes is still a Poisson Point Process. which reveals the essence of the flooding delay in wireless The number of nodes counted in disjoint areas are inde- multi-hop networks.Then,based on the delay of the cluster pendent from each other (spatial independence). to cluster transmission,we obtain a lower bound of y(A). As readers will see,the above two properties are extremely We then generalize the previous result to the case with useful in our analysis. nonzero propagation delay.Propagation delay will aggravate 2)Random Connection Model:Before introducing the net- the delay performance in Large-Scale wireless Networks,mak- work model,we need a brief introduction to Continuum Perco ing (A)>0 even when A >Ar.Using similar methods,we lation.Connectivity is a significant issue in wireless network, present new upper and lower bounds to (A)for all A>AL. which has been extensively explored by [4]5]611718191.In Finally,we conduct simulation to verify our theoretical results. this paper,we present the definition of connectivity in the The original contributions that we have made in the paper percolation perspective.To make the results in this paper are highlighted as follows: applicable to the most scenarios,we focus on a fairly general model in Continuum Percolation Theory,i.e.,the Random We present two properties to y(A),i.e,(A)=0 Connection Model(RCM)[15]. whenever propagation delay is0and入>；y()is In the RCM,nodes are distributed according to Poisson a monotone decreasing function. point process in Rd.Here we only focus on the case of R2 with Ignoring propagation delay,we provide the upper bound node density A>0.Each node x connects to another node y and the lower bound to reflect the range of variation on according to some predefined connection function h(r),where Y(入). r=-yll is the distance between z and y.Specifically, Taking propagation delay into consideration,we obtain nodes x and y are connected with probability h(r).We assume further results. We conduct simulations to obtain experimental values that h(r)satisfies 0<2h(r)drdy <oo,which ensures the phase transition effect [15]in the Random Connection Model. of (A)in the above two cases.The new observation arises from our comparison between theoretical and sim- We denote a RCM by G(A,ro,h(r))2,where A is the ulation results is that the delay-distance ratio (A)can node density,ro supfrh(r)>0),h(r)is the connection function.Then g(A,ro,h(r))is a set of nodes connected by be approximated by the lower bound in relative dense random links.For convenience,we assume that the origin networks while the experimental values of (A)get closer 0∈g(入，ro,h(r)). to the upper bound in relative sparse networks.This also Obviously,G(A,ro,h(r))is composed of a set of dis- justifies the soundness of our theoretical conclusion. jointed connected components.Let us denote W(A),A C The rest of the paper is organized as follows.In section II, C(A,ro.h(r)),the set of nodes attainable from nodes in set we introduce our network model,several useful mathematical A,i.e., tools and some important notations.In section III,we first give two properties of (A),and then present our main results W(A)={x∈G(入，To,h(r)l3a∈A,aHx}, concerning the upper and lower bound of (A).The analysis for obtaining the upper and lower bounds is given in section 2In general,a RCM can be fully determined by A and h(r)only.We just use ro to emphasize that we only focus on functions h(r)that are 0 for r IV.Simulation results are presented in Section VI to justify larger than some finite value ro
2 Therefore, it is negligibly small compared to the waiting delay. For ease of analysis, we first ignore the impact of propagation delay and will consider its effect in the last. We study the delay performance for flooding in large-scale wireless networks. Ignoring the propagation delay, previous works [12][3][11] have showed that if λL < λ < λI , the end-to-end delay scales linearly with the source-to-destination distance (γ(λ) > 0), and that if λ > λI , the end-to-end delay scales sub-linearly with distance (γ(λ) = 0). However, these results are far from enough to provide reasonable delay guarantee. It remains extremely important to find out the exact value or the lower and upper bounds of γ(λ). In this paper, we present a theoretical analysis about the flooding delay in wireless multi-hop networks with unreliable links. We first ignore the propagation delay and find the upper and lower bounds of γ(λ). For the upper bound, we first find a path between two nodes using percolation theory. And then we calculate the number of hops along this path using another coupling technique and the delay at each hop. We obtain the result of upper bound by multiplying the above two items. For the lower bound, we first introduce a concept called cluster to cluster transmission process and establish the relationship between delay and the cluster to cluster transmission process, which reveals the essence of the flooding delay in wireless multi-hop networks. Then, based on the delay of the cluster to cluster transmission, we obtain a lower bound of γ(λ). We then generalize the previous result to the case with nonzero propagation delay. Propagation delay will aggravate the delay performance in Large-Scale wireless Networks, making γ(λ) > 0 even when λ > λI . Using similar methods, we present new upper and lower bounds to γ(λ) for all λ > λL. Finally, we conduct simulation to verify our theoretical results. The original contributions that we have made in the paper are highlighted as follows: • We present two properties to γ(λ), i.e., γ(λ) = 0 whenever propagation delay is 0 and λ > λI ; γ(λ) is a monotone decreasing function. • Ignoring propagation delay, we provide the upper bound and the lower bound to reflect the range of variation on γ(λ). • Taking propagation delay into consideration, we obtain further results. • We conduct simulations to obtain experimental values of γ(λ) in the above two cases. The new observation arises from our comparison between theoretical and simulation results is that the delay-distance ratio γ(λ) can be approximated by the lower bound in relative dense networks while the experimental values of γ(λ) get closer to the upper bound in relative sparse networks. This also justifies the soundness of our theoretical conclusion. The rest of the paper is organized as follows. In section II, we introduce our network model, several useful mathematical tools and some important notations. In section III, we first give two properties of γ(λ), and then present our main results concerning the upper and lower bound of γ(λ). The analysis for obtaining the upper and lower bounds is given in section IV. Simulation results are presented in Section VI to justify our theoretical findings. We summarize the paper in Section VII. Some proofs of the theorems and lemmas are presented in section V. II. BACKGROUND AND NETWORK MODEL In this section, we introduce some background knowledge and the network model. A. Background 1) Poisson Point Process: In large-scale wireless multi-hop networks, it is extremely difficult to predict the exact locations of different users (nodes) due to the random behavior of different users. To model the location-randomness, we use Poisson Point Process [18]. One way to visualize the Poisson Point Process is to assume that all users are distributed uniformly in a given area, e.g., λn2 nodes are evenly distributed in a n × n area. If we let n → ∞, then the distribution of these random processes (indexed by n) will converge in distribution to Poisson Point Process with rate λ. Poisson Point Process has the following two properties: • The superposition of two independent Poisson Point Processes is still a Poisson Point Process. • The number of nodes counted in disjoint areas are independent from each other (spatial independence). As readers will see, the above two properties are extremely useful in our analysis. 2) Random Connection Model: Before introducing the network model, we need a brief introduction to Continuum Percolation. Connectivity is a significant issue in wireless network, which has been extensively explored by [4][5][6][7][8][9]. In this paper, we present the definition of connectivity in the percolation perspective. To make the results in this paper applicable to the most scenarios, we focus on a fairly general model in Continuum Percolation Theory, i.e., the Random Connection Model(RCM) [15]. In the RCM, nodes are distributed according to Poisson point process in R d . Here we only focus on the case of R 2 with node density λ > 0. Each node x connects to another node y according to some predefined connection function h(r), where r =∥ x − y ∥ is the distance between x and y. Specifically, nodes x and y are connected with probability h(r). We assume that h(r) satisfies 0 < ∫ R2 h(r)dxdy < ∞, which ensures the phase transition effect [15] in the Random Connection Model. We denote a RCM by G(λ, r0, h(r))2 , where λ is the node density, r0 = sup{r|h(r) > 0}, h(r) is the connection function. Then G(λ, r0, h(r)) is a set of nodes connected by random links. For convenience, we assume that the origin 0 ∈ G(λ, r0, h(r)). Obviously, G(λ, r0, h(r)) is composed of a set of disjointed connected components. Let us denote W(A), A ⊆ G(λ, r0, h(r)), the set of nodes attainable from nodes in set A, i.e., W(A) = {x ∈ G(λ, r0, h(r))|∃a ∈ A, a ↔ x}, 2 In general, a RCM can be fully determined by λ and h(r) only. We just use r0 to emphasize that we only focus on functions h(r) that are 0 for r larger than some finite value r0
where,a means that nodes a and x are in the same g(r) f(r) connected component. Besides,we use W to represent the cardinality of the set g(0 W.Further,we define n(A)=Ph(W(0))=oo)3 and Xh(A)=E.h(IW({0))4 g(r Then,the critical density can be determined in two ways, i.e., (a)Illustration of connection (b)Illustration of connection λg(h)=inf{0h(A)>0}: (1) function g(r). function f(r). 入x(h)=inf{Xh(A)=o}. (2) Fig.1.Illustration of two connection functions. According to Theorem 6.2 in [15],0<Ae(h)=Ax(h)= Ac(h)<oo.Furthermore,there exists a unique infinite con- Based on the above discussion,the network at each time nected component containing a large portion of the nodes in slot t can be represented by a RCM G(A,ro,g(r)).Here,we G(A,ro,h(r))with probability 1 if A>Ac(h)(supercritical). use subscript t to indicate that the network is dynamic.Note This infinite connected component is also called the giant that if>(g(r)),G(A,ro,g(r))is percolated for allt(we component,denoted by C(g(,ro,h(r))).In this case.we call also say the network has instantaneous connectivity);while if G(A,ro,h(r))percolated.On the other hand.if Ae(h)<Ae(g(r)).G(A,ro,g(r))is not percolated for all t.Thus. (subcritical),all the connected components are finite almost the instantaneous critical density Ar =Ac(g(r)). surely. Next,we introduce the concept of the long-term connectivi- Another useful model in Continuum Percolation is Poisson ty.We first construct a new graph.The location of all nodes in Boolean Model,denoted by B(A,r).In the Poisson Boolean this graph is the same as that in G(A,ro,g(r)).Two nodes Model B(A,r),nodes are distributed according to Poisson and y share a link in this graph if and only if there exist t,such Point Process with density A,and two nodes can communicate that x and y share an open link in G:(A,ro,g(r)).Note that if and only if their distance is smaller than r.Poisson Boolean x and y has the potential to share a link in G(A,ro,g(r)) Model can be viewed as a special case of Random Connection for some t,whenever g(r)>0(equivalently,r<ro). Model.Thus,the conclusions for Random Connection Model Thus this new geometric graph can be represented by a RCM also hold for Poisson Boolean Model. G(A,ro,f(r))(it can be also represented by Poisson Boolean Model B(,ro)).Here,f(r)=1 when r ro,and f(r)=0 B.Model when r>ro (Fig.1).We say the wireless network has long- 1)Network Model:We model the large-scale wireless term connectivity if and only if g(,ro,f(r))is percolated, multi-hop network as a random graph with dynamically vary- and the critical density AL=Ac(f(r))is defined as the long- ing edges.We assume that the network nodes are distributed term critical density. according to Poisson Point Process with node density A in Note that the long-term connectivity graph G(A,ro,f(r)) an infinite two-dimensional space R2.For each node u,we is a super-graph of all the instantaneous connectivity graph use u to represent both this node and its location without G(A,ro,g(r)).Thus,whenever Gt(A,ro,g(r))is percolated, causing confusion.We say two nodes share a link if and G(A,ro,f(r))is percolated.Based on this observation,it only if their distance is smaller than ro.However,due to the is easy to know thatλL≤入.Since the prerequisite for unreliability of the wireless channel and the unexpected user communication in large-scale wireless network is connectivity, behaviors,each link suffers the possibility to fail.We say a it is enough to only focus on the case A>AL. link open at a time slot if this link can successfully transmit 2)Modeling Delay in Large-Scale Wireless Networks:The a packet,and closed otherwise.We model the link failure as definition of delay of large-scale network is based on the each link opening or closing intermittently.Specifically,we First Passage Percolation [2].Specifically,given a Random assume that time is slotted,and the duration of each time slot Connection Model G(A,ro,h(r)),we attach each link e of is 1.Consider a link with length r,at time slot t.We let it open G(A,ro,h(r))a random variable Te(e).representing the time with probability g(r)(Fig.1),independent of its former states. needed to pass through the link e.Consider a path the In reality,the farther two nodes are apart,the more difficult for passage time is defined as a successful communication.Moveover,when r>ro,there Tn(π)=T(e). exists no link.Thus,it is reasonable to assume that g(r)is a eEr monotone decreasing function and g(r)=0 whenever r>ro. We then define the first-passage time T(z,y)for any two Further,we place another constraint on g(r),i.e., nodes x and y (x,y are not necessarily adjacent)as the 1>g(0)2g(r)2g(ro)>0,0≤r≤To (3) minimum delay among all possible routes,i.e., As readers will see,constraint (3)is used to ensure that the T(x,y)）=inf{Tp(x):πis a path from x toy}.(4) expected traversing delay over each possible link is bounded We now give the detailed definition of Te(e).Generally, above. the time needed to cross the link e is composed of two parts. 3P is the probability of a event. The first part is called waiting delay,which is caused by the 4E()is the expectation of random variable unreliability of this link.The second part is called propagation
3 where, a ↔ x means that nodes a and x are in the same connected component. Besides, we use |W| to represent the cardinality of the set W. Further, we define θh(λ) = Pλ,h(|W({0})| = ∞) 3 and χh(λ) = Eλ,h(|W({0})|) 4 . Then, the critical density can be determined in two ways, i.e., λθ(h) = inf{λ|θh(λ) > 0}; (1) λχ(h) = inf{λ|χh(λ) = ∞}. (2) According to Theorem 6.2 in [15], 0 < λθ(h) = λχ(h) = λc(h) < ∞. Furthermore, there exists a unique infinite connected component containing a large portion of the nodes in G(λ, r0, h(r)) with probability 1 if λ > λc(h) (supercritical). This infinite connected component is also called the giant component, denoted by C(G(λ, r0, h(r))). In this case, we call G(λ, r0, h(r)) percolated. On the other hand, if λ < λc(h) (subcritical), all the connected components are finite almost surely. Another useful model in Continuum Percolation is Poisson Boolean Model, denoted by B(λ, r). In the Poisson Boolean Model B(λ, r), nodes are distributed according to Poisson Point Process with density λ, and two nodes can communicate if and only if their distance is smaller than r. Poisson Boolean Model can be viewed as a special case of Random Connection Model. Thus, the conclusions for Random Connection Model also hold for Poisson Boolean Model. B. Model 1) Network Model: We model the large-scale wireless multi-hop network as a random graph with dynamically varying edges. We assume that the network nodes are distributed according to Poisson Point Process with node density λ in an infinite two-dimensional space R 2 . For each node u, we use u to represent both this node and its location without causing confusion. We say two nodes share a link if and only if their distance is smaller than r0. However, due to the unreliability of the wireless channel and the unexpected user behaviors, each link suffers the possibility to fail. We say a link open at a time slot if this link can successfully transmit a packet, and closed otherwise. We model the link failure as each link opening or closing intermittently. Specifically, we assume that time is slotted, and the duration of each time slot is 1. Consider a link with length r, at time slot t. We let it open with probability g(r) (Fig. 1), independent of its former states. In reality, the farther two nodes are apart, the more difficult for a successful communication. Moveover, when r > r0, there exists no link. Thus, it is reasonable to assume that g(r) is a monotone decreasing function and g(r) = 0 whenever r > r0. Further, we place another constraint on g(r), i.e., 1 > g(0) ≥ g(r) ≥ g(r0) > 0, 0 ≤ r ≤ r0. (3) As readers will see, constraint (3) is used to ensure that the expected traversing delay over each possible link is bounded above. 3P is the probability of a event. 4E(x) is the expectation of random variable x J U I U J J U U U U U (a) Illustration of connection function g(r). J U I U J J U U U U U (b) Illustration of connection function f(r). Fig. 1. Illustration of two connection functions. Based on the above discussion, the network at each time slot t can be represented by a RCM Gt(λ, r0, g(r)). Here, we use subscript t to indicate that the network is dynamic. Note that if λ > λc(g(r)), Gt(λ, r0, g(r)) is percolated for all t (we also say the network has instantaneous connectivity); while if λ < λc(g(r)), Gt(λ, r0, g(r)) is not percolated for all t. Thus, the instantaneous critical density λI = λc(g(r)). Next, we introduce the concept of the long-term connectivity. We first construct a new graph. The location of all nodes in this graph is the same as that in Gt(λ, r0, g(r)). Two nodes x and y share a link in this graph if and only if there exist t, such that x and y share an open link in Gt(λ, r0, g(r)). Note that x and y has the potential to share a link in Gt(λ, r0, g(r)) for some t, whenever g(r) > 0 (equivalently, r < r0). Thus this new geometric graph can be represented by a RCM G(λ, r0, f(r)) (it can be also represented by Poisson Boolean Model B(λ, r0)). Here, f(r) = 1 when r < r0, and f(r) = 0 when r > r0 (Fig. 1). We say the wireless network has longterm connectivity if and only if G(λ, r0, f(r)) is percolated, and the critical density λL = λc(f(r)) is defined as the longterm critical density. Note that the long-term connectivity graph G(λ, r0, f(r)) is a super-graph of all the instantaneous connectivity graph Gt(λ, r0, g(r)). Thus, whenever Gt(λ, r0, g(r)) is percolated, G(λ, r0, f(r)) is percolated. Based on this observation, it is easy to know that λL ≤ λI . Since the prerequisite for communication in large-scale wireless network is connectivity, it is enough to only focus on the case λ > λL. 2) Modeling Delay in Large-Scale Wireless Networks: The definition of delay of large-scale network is based on the First Passage Percolation [2]. Specifically, given a Random Connection Model G(λ, r0, h(r)), we attach each link e of G(λ, r0, h(r)) a random variable Tc(e), representing the time needed to pass through the link e. Consider a path π, the passage time is defined as Tp(π) = ∑ e∈π (Tc(e)). We then define the first-passage time Tλ(x, y) for any two nodes x and y (x, y are not necessarily adjacent) as the minimum delay among all possible routes, i.e., Tλ(x, y) = inf {Tp(π) : π is a path from x to y}. (4) We now give the detailed definition of Tc(e). Generally, the time needed to cross the link e is composed of two parts. The first part is called waiting delay, which is caused by the unreliability of this link. The second part is called propagation
￥ delay 5,which is the time required for a packet to transverse .(Section II-B2)T(e)is the passage time for a link e; the link e whenever the link is on.We assume that the duration Tp()is the passage time for a path T(,y)is the first of a time slot is long enough for a packet to be successfully passage time from node x to y;(Section IV-B1)T(II) transmitted over a link.Equivalently,the propagation delay is the passage time for a cluster to cluster transmission over a link is smaller than 1 time slot.For ease of analysis. processΠ； we assume that all active links can transmit simultaneously .(Section IV-A)N(d(u,v))is the minimum number of with the same propagation delay T,where T<1 time slot. hops from node u to v. Based on the above discussion,we can express the crossing represents a path;II represents a cluster to cluster time T(e)as a geometrically distributed random variable. transmission process. Specifically,assume that the length of the link e is 0<r<ro. then we have P(Te(e)=k+T)=(1-g(r))"g(r). (5) III.MAIN RESULTS Now we are ready to introduce the delay-distance ratio In this section,we first give two properties on the delay- (A).Consider two nodes z,yc(g(A,ro,f(r)))6.Pre- distance ratio (A).After that,we present our main results vious works [12][3][11]have proved that,the two limits concerning the relationship between node density A and (A), lim.and lim(exist almost d(z.y) in which an upper bound and a lower bound for ()are surely.Furthermore, given. E(T(x,y)) lim Tx(r,y)=lim ,a.5.(6) d(z)→o∞dx,y）d(x,y)→ood(x,y） A.Properties of (X) We denote the above limit by (A).(A)characterizes the first (A)can be viewed as a function mapping from (AL,oo) passage delay T(,y)with respect to the distance d(,y).We to R.The properties of (A)are listed below. need to emphasize that (A)depends on A.In fact,previous results also show that if T =0 and A>Ar,y=0.Otherwise, Theorem 1.(X)has the following two properties: y>0.However,none of the previous works studies the exact l)fT=0,then入>λ，y(A)=0: relationship between (A)and A,especially,how y(A)varies with respect to A in the region (L Arl.In this paper,we will 2)(X)is a monotone decreasing function. give a more detailed quantification of (A). Proof:The first property has already been proved by previous literatures [12][11][3][17].Thus,we only present the proof of the property (2)here. C.Useful Notations Given A1 >A2.consider two Random Connection Models Some useful notations are listed as follows. G(A1,ro,g(r))and G(A2,ro,g(r)).We use coupling tech- .(Section II-A2)g(A,ro,h(r))is a Random Connection nique to prove 7(1)<7(A2).Nodes in Gt(A1,ro,g(r)) Model,and h(r)is the connection function;B(A,r)is and Gi(A2,ro,g(r))are distributed according to Poisson Point the Poisson Boolean Model;we use c(g(A,ro,h(r)))Processes,denoted by I and IA2,with node densities and C(B(A,r))to represent the giant component of Ai and A2.respectively.Note that I can be viewed as G(A,ro,h(r))and B(A,r)respectively. the superposition of Tx2 and another Poisson Point Process ·(SectionⅡ-Bl)gt(入，ro,g(r)is the instantaneous geo- Tx1-x2 with node densityλ1-λ2. metric graph at time slot t and its critical density is Ar; Consider nodes y E Ix2,since IA2 IA,we ob- G(A,ro,f(r))is the long-term geometric graph and its tain ,y I.For any path connecting x and y in critical density is AL. G(2,ro,g(r)),this path also exists in G(1,ro,g(r)).By P()represents the probability of some event;E() the definition of Ta(,y),we must have represents the expectation of a random variable;z() represents the x(y)-coordinate of z;d(u,v)=u-v T1(x,)≤T2(x,y) is the Euclidean distance between node u and v. (Section IV-B)H(zo,a)is a circular region defined as Divide the above inequality by d(,y),and let d(,y) H(0,a）={z=(zx,2g)∈R21‖z-20‖<a} oo,we obtain The random variable Sg.t.u(A)is defined as Sg.t.u(A)= y(入1)≤Y(A2): supfa node v E H(u,a),v and u are connected in G(,ro,g(r))}.In fact,all Sa.t.u()'s (indexed by t ■ and u)have the same distribution.Thus,we write the expectation of Sg.t.u()as E(Sg(A))for short. B.Main results on (X) STo be precise,this propagation delay includes both the processing delay at the sending node,and the propagation delay along the link We have obtained several properties of (A).Now we are 6Such a giant component exists with probability 1,because we focus on ready to present our main results. the case入>入in this paper
4 delay 5 , which is the time required for a packet to transverse the link e whenever the link is on. We assume that the duration of a time slot is long enough for a packet to be successfully transmitted over a link. Equivalently, the propagation delay over a link is smaller than 1 time slot. For ease of analysis, we assume that all active links can transmit simultaneously with the same propagation delay τ , where τ < 1 time slot. Based on the above discussion, we can express the crossing time Tc(e) as a geometrically distributed random variable. Specifically, assume that the length of the link e is 0 < r < r0, then we have P(Tc(e) = k + τ ) = (1 − g(r))k g(r). (5) Now we are ready to introduce the delay-distance ratio γ(λ). Consider two nodes x, y ∈ C(G(λ, r0, f(r)))6 . Previous works [12][3][11] have proved that, the two limits limd(x,y)→∞ Tλ(x,y) d(x,y) and limd(x,y)→∞ E(Tλ(x,y)) d(x,y) exist almost surely. Furthermore, lim d(x,y)→∞ Tλ(x, y) d(x, y) = lim d(x,y)→∞ E(Tλ(x, y)) d(x, y) , a.s. (6) We denote the above limit by γ(λ). γ(λ) characterizes the first passage delay Tλ(x, y) with respect to the distance d(x, y). We need to emphasize that γ(λ) depends on λ. In fact, previous results also show that if τ = 0 and λ > λI , γ = 0. Otherwise, γ > 0. However, none of the previous works studies the exact relationship between γ(λ) and λ, especially, how γ(λ) varies with respect to λ in the region (λL, λI ]. In this paper, we will give a more detailed quantification of γ(λ). C. Useful Notations Some useful notations are listed as follows. • (Section II-A2) G(λ, r0, h(r)) is a Random Connection Model, and h(r) is the connection function; B(λ, r) is the Poisson Boolean Model; we use C(G(λ, r0, h(r))) and C(B(λ, r)) to represent the giant component of G(λ, r0, h(r)) and B(λ, r) respectively. • (Section II-B1) Gt(λ, r0, g(r)) is the instantaneous geometric graph at time slot t and its critical density is λI ; G(λ, r0, f(r)) is the long-term geometric graph and its critical density is λL. • P(•) represents the probability of some event; E(•) represents the expectation of a random variable; zx (zy) represents the x(y)-coordinate of z; d(u, v) =∥ u − v ∥ is the Euclidean distance between node u and v. • (Section IV-B) H(z0, a) is a circular region defined as H(z0, a) = {z = (zx, zy) ∈ R 2 | ∥ z − z0 ∥< a}. The random variable Sg,t,u(λ) is defined as Sg,t,u(λ) = sup{a|∃ node v ∈ Hc (u, a), v and u are connected in Gt(λ, r0, g(r))}. In fact, all Sg,t,u(λ)’s (indexed by t and u) have the same distribution. Thus, we write the expectation of Sg,t,u(λ) as E(Sg(λ)) for short. 5To be precise, this propagation delay includes both the processing delay at the sending node, and the propagation delay along the link 6Such a giant component exists with probability 1, because we focus on the case λ > λL in this paper. • (Section II-B2) Tc(e) is the passage time for a link e; Tp(π) is the passage time for a path π; Tλ(x, y) is the first passage time from node x to y; (Section IV-B1) Tp(Π) is the passage time for a cluster to cluster transmission process Π; • (Section IV-A) Nλ(d(u, v)) is the minimum number of hops from node u to v. • π represents a path; Π represents a cluster to cluster transmission process. III. MAIN RESULTS In this section, we first give two properties on the delaydistance ratio γ(λ). After that, we present our main results concerning the relationship between node density λ and γ(λ), in which an upper bound and a lower bound for γ(λ), are given. A. Properties of γ(λ) γ(λ) can be viewed as a function mapping from (λL,∞) to R. The properties of γ(λ) are listed below. Theorem 1. γ(λ) has the following two properties: 1) if τ = 0, then ∀λ > λI , γ(λ) = 0; 2) γ(λ) is a monotone decreasing function. Proof: The first property has already been proved by previous literatures [12][11][3][17]. Thus, we only present the proof of the property (2) here. Given λ1 > λ2, consider two Random Connection Models Gt(λ1, r0, g(r)) and Gt(λ2, r0, g(r)). We use coupling technique to prove γ(λ1) ≤ γ(λ2). Nodes in Gt(λ1, r0, g(r)) and Gt(λ2, r0, g(r)) are distributed according to Poisson Point Processes, denoted by Γλ1 and Γλ2 , with node densities λ1 and λ2, respectively. Note that Γλ1 can be viewed as the superposition of Γλ2 and another Poisson Point Process Γλ1−λ2 with node density λ1 − λ2. Consider nodes x, y ∈ Γλ2 , since Γλ2 ⊆ Γλ1 , we obtain x, y ∈ Γλ1 . For any path π connecting x and y in Gt(λ2, r0, g(r)), this path also exists in Gt(λ1, r0, g(r)). By the definition of Tλ(x, y), we must have Tλ1 (x, y) ≤ Tλ2 (x, y). Divide the above inequality by d(x, y), and let d(x, y) → ∞, we obtain γ(λ1) ≤ γ(λ2). B. Main results on γ(λ) We have obtained several properties of γ(λ). Now we are ready to present our main results
Theorem 2.Given a RCM G(A,ro,g(r))with AL(1+e)<must be infinity),and calculate (A)from this subset.This X<XI (e>0)and T=0,the corresponding y(X)satisfies technique is used in deriving the upper bound. Now we are to obtain the upper bound of y(A).The delay E(S,()+m≤) T(,y)is defined as the minimum delay along all paths connecting nodes x and y.Thus,it must be smaller than or equal to the delay along one specific path.In this part,we inf first find a subset of nodes of c(G(,ro,f(r))).Then,we X∈L(1+e), L(1+e find a path for each node pair in this subset.After that,we calculate the delay along this path.Finally,dividing the delay where Ke is a constant independent of X. by distance,we obtain an upper bound of (A). Before proceeding,we need the following lemma. Theorem 2 ignores the propagation delay.If we take propa- gation delay into consideration,we have the following results. Lemma 2.Consider Poisson Boolean models in R2.Let Xe(r) denote the critical density in the case where the transmission Theorem3.Given a RCM G(X,ro,g(r)with入≥入L(1+e) range is r.Then it is the case that (e>0)and 0<T 1.Then the corresponding (satisfies 1 λc(r1)r1=入c(r2)r E(min{Sg(A),})+ro ≤Y(A) where r1,r2 >0. KeVX'/XL ≤ inf (8) Proof:See Proposition 2.10 in [15]. ■ 'EAL(1+e), AL(1+E) The long-term critical density AL is also the critical density of Poisson Boolean Model with transmission range ro.Consid- where Ke is a constant independent of A. er the network with density A>AL,according to lemma 2,we We need to emphasize that the two ke's in Theorem 2 and immediately know that whenr2>zr,ie,r>√头ro, Theorem 3 are the same.The rigorous definition of Ke is Poisson Boolean Model B(A,r)is percolated. postponed to Section IV-A (see Lemma 3). Let元=rOVALC+9,then B(入，）is percolated.Fther. Our results provide a way to estimate delay in Large-scale since A>AL(1+e),we must have<ro.Note that, wireless multi-hop networks.Our result is also very general. the Random Connection Model G(A,ro,f(r))is essentially By changing the connection function g(r),our results can be a Poisson Boolean Model B(A,ro)with ro f.Hence, easily applied to different scenarios in real networks. B(,)is a subgraph of G(A,ro,f(r)).(Here,B(,)has the same node locations as G(A,ro,f(r)).)We denote the IV.UPPER AND LOWER BOUNDS OF Y() giant component of B(A,r)by C(B(A,).According to the In this section,we first give an upper bound to the delay- uniqueness of giant component in supercritical case,there must distance ratio,y(A).Then,we make further analysis on first be C(B(,))C(G(A,ro,f(r))).According to lemma 1, passage delay and introduce a concept called cluster to cluster when calculating (A),we only need to focus on the case that transmission.Using this concept,we derive a lower bound. both nodes belong to C(B(入，). Finally,we take propagation delay into consideration,and Assume that nodes u,vEC(B(,))Then there exists at formulate its impact on () least one path in B(A,)from u to v.We choose the path with minimum number of hops,and denote it by Tm. A.Upper Bound of ( Up to now,we have found a path connecting u and v.Next, we are to calculate the delay along this path.To start with,we Recall the definition of (A)(Eqn.6)that (A)= lim where belongs to the giant com- need to compute the number of hops,denoted by Na(d(u,v)), in Tm.We can find a relationship between Na(d(u,v))and A ponent of G(A,ro,f(r)).To compute such a limit,we do not using the following scaling arguments. have to calculate (for all ,y c(G(A,ro,f(r))).The 入 correctness of this assertion is assured by the following lemma. Scale the network B(,)up by,then the network B(A,becomes another network B(AL,rov1+e).Further, Lemma 1.Given a convergent sequence (xk},k 1,2,.... the original distance d(u,v)between u and v becomes and lim1..is a subsequence of d(u,)Then to compute Nd,)).it is equivalent k},and limkoo yk yo.Then To y0. It is easy to see that the number of nodes in to compute N(d(u,)).Next,we present the lemma C(g(A,ro,f(r)))is countable.We enumerate for all nodes. concerning N (d). We randomly select a node and label it as xo.and then Lemma 3.Given B(AL,rov1+e).and u,v label other nodes according to the distance from o (larger C(B(AL,rov1+e)).the minimal number of hops among all subscript means larger distance from To).Define sequence paths from u to v is NA (d(u,v)).Then there exist Ke such fmk2..).m then limg oo m that (A).According to lemma 1,we only need to find a subset lim Nz(d(u,u》=Ke. of nodes of c(g(A,ro,f(r)))(the cardinality of this subset d(u,)→ood(u,v）
5 Theorem 2. Given a RCM Gt(λ, r0, g(r)) with λL(1 + ϵ) ≤ λ < λI (ϵ > 0) and τ = 0, the corresponding γ(λ) satisfies 1 E(Sg(λ) + r0) ≤ γ(λ) ≤ inf λ ′∈[λL(1+ϵ),λ] κϵ √ λ ′ λL 1 g ( r0 √λL(1+ϵ) λ ′ ) − 1 ,(7) where κϵ is a constant independent of λ. Theorem 2 ignores the propagation delay. If we take propagation delay into consideration, we have the following results. Theorem 3. Given a RCM Gt(λ, r0, g(r)) with λ ≥ λL(1+ϵ) (ϵ > 0) and 0 < τ < 1. Then the corresponding γ(λ) satisfies 1 E(min{Sg(λ), r0 τ }) + r0 ≤ γ(λ) ≤ inf λ ′∈[λL(1+ϵ),λ] κϵ √ λ ′ /λL g ( r0 √λL(1+ϵ) λ ′ ) (8) where κϵ is a constant independent of λ. We need to emphasize that the two κϵ’s in Theorem 2 and Theorem 3 are the same. The rigorous definition of κϵ is postponed to Section IV-A (see Lemma 3). Our results provide a way to estimate delay in Large-scale wireless multi-hop networks. Our result is also very general. By changing the connection function g(r), our results can be easily applied to different scenarios in real networks. IV. UPPER AND LOWER BOUNDS OF γ(λ) In this section, we first give an upper bound to the delaydistance ratio, γ(λ). Then, we make further analysis on first passage delay and introduce a concept called cluster to cluster transmission. Using this concept, we derive a lower bound. Finally, we take propagation delay into consideration, and formulate its impact on γ(λ). A. Upper Bound of γ(λ) Recall the definition of γ(λ) (Eqn. 6) that γ(λ) = limd(x,y)→∞ Tλ(x,y) d(x,y) , where x, y belongs to the giant component of G(λ, r0, f(r)). To compute such a limit, we do not have to calculate γ(λ) for all x, y ∈ C(G(λ, r0, f(r))). The correctness of this assertion is assured by the following lemma. Lemma 1. Given a convergent sequence {xk}, k = 1, 2, ..., and limk→∞ xk = x0. {yk}, k = 1, 2, ..., is a subsequence of {xk}, and limk→∞ yk = y0. Then x0 = y0. It is easy to see that the number of nodes in C(G(λ, r0, f(r))) is countable. We enumerate for all nodes. We randomly select a node and label it as x0, and then label other nodes according to the distance from x0 (larger subscript means larger distance from x0). Define sequence {mk, k = 1, 2, ..., }, mk = Tλ(x0,xk) d(x0,xk) , then limk→∞ mk = γ(λ). According to lemma 1, we only need to find a subset of nodes of C(G(λ, r0, f(r))) (the cardinality of this subset must be infinity), and calculate γ(λ) from this subset. This technique is used in deriving the upper bound. Now we are to obtain the upper bound of γ(λ). The delay Tλ(x, y) is defined as the minimum delay along all paths connecting nodes x and y. Thus, it must be smaller than or equal to the delay along one specific path. In this part, we first find a subset of nodes of C(G(λ, r0, f(r))). Then, we find a path for each node pair in this subset. After that, we calculate the delay along this path. Finally, dividing the delay by distance, we obtain an upper bound of γ(λ). Before proceeding, we need the following lemma. Lemma 2. Consider Poisson Boolean models in R 2 . Let λc(r) denote the critical density in the case where the transmission range is r. Then it is the case that λc(r1)r 2 1 = λc(r2)r 2 2 , where r1, r2 > 0. Proof: See Proposition 2.10 in [15]. The long-term critical density λL is also the critical density of Poisson Boolean Model with transmission range r0. Consider the network with density λ > λL, according to lemma 2, we immediately know that when λr2 > λLr 2 0 , i.e., r > √ λL λ ·r0, Poisson Boolean Model B(λ, r) is percolated. Let r˜ = r0 √ λL(1+ϵ) λ , then B(λ, r˜) is percolated. Further, since λ ≥ λL(1 + ϵ), we must have r˜ ≤ r0. Note that, the Random Connection Model G(λ, r0, f(r)) is essentially a Poisson Boolean Model B(λ, r0) with r0 ≥ r˜. Hence, B(λ, r˜) is a subgraph of G(λ, r0, f(r)). (Here, B(λ, r˜) has the same node locations as G(λ, r0, f(r)).) We denote the giant component of B(λ, ˜r) by C(B(λ, r˜)). According to the uniqueness of giant component in supercritical case, there must be C(B(λ, r˜)) ⊆ C(G(λ, r0, f(r))). According to lemma 1, when calculating γ(λ), we only need to focus on the case that both nodes belong to C(B(λ, r˜)). Assume that nodes u, v ∈ C(B(λ, r˜)). Then there exists at least one path in B(λ, r˜) from u to v. We choose the path with minimum number of hops, and denote it by πm. Up to now, we have found a path connecting u and v. Next, we are to calculate the delay along this path. To start with, we need to compute the number of hops, denoted by Nλ(d(u, v)), in πm. We can find a relationship between Nλ(d(u, v)) and λ using the following scaling arguments. Scale the network B(λ, r˜) up by √ λ λL , then the network B(λ, r˜) becomes another network B(λL, r0 √ 1 + ϵ). Further, the original distance d(u, v) between u and v becomes d(u, v) √ λ λL . Then to compute Nλ(d(u, v)), it is equivalent to compute NλL (d(u, v) √ λ λL ). Next, we present the lemma concerning NλL (d). Lemma 3. Given B(λL, r0 √ 1 + ϵ), and u, v ∈ C(B(λL, r0 √ 1 + ϵ)), the minimal number of hops among all paths from u to v is NλL (d(u, v)). Then there exist κϵ such that lim d(u,v)→∞ NλL (d(u, v)) d(u, v) = κϵ