Node Density and Delay in Large-Scale Wireless Networks with Unreliable Links

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入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 wire￾less 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 envi￾ronment [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 large￾scale 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 gener￾al 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 compo￾nent containing a large portion of nodes in the infinitely large network (we also say the network is percolated). However, for λ λL throughout this paper. In large-scale wireless networks, delay is mainly composed of the waiting delay and the propagation delay. The waiting de￾lay 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入z0),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 00),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 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, mak￾ing γ(λ) > 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 sim￾ulation 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 differ￾ent 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 inde￾pendent 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 net￾work model, we need a brief introduction to Continuum Perco￾lation. 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 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 dis￾jointed 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],0Ac(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)0(equivalently,rro (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 λ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 λ 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 JU IU  J JU   U U U U (a) Illustration of connection function g(r). JU IU  J JU   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 λ 0 (equivalently, r r0 (Fig. 1). We say the wireless network has long￾term connectivity if and only if G(λ, r0, f(r)) is percolated, and the critical density λL = λc(f(r)) is defined as the long￾term 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 TAr,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)入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 τ λ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 geo￾metric 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 ∥ λ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 delay￾distance 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 tech￾nique 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 ob￾tain 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)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 00. 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 + ϵ) ≤ λ 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 propa￾gation delay into consideration, we have the following results. Theorem 3. Given a RCM Gt(λ, r0, g(r)) with λ ≥ λL(1+ϵ) (ϵ > 0) and 0 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. Consid￾er 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) = κϵ

6 Lemma 3 gives the rigorous definition of which is a paths.Therefore,it is usually intractable to obtain the delay useful parameter in Theorem 2 and Theorem 3.The proof of from Eqn.(4).To overcome this difficulty,we introduce the Lemma 3 is based on a conclusion on subadditivity and is concept of cluster to cluster transmission. given in section V-A. Consider the packet transmission process from node u to According to lemma 3,we immediately get node v.Assume that at time slot t1,node u(u=u)transmits a packet to other nodes.Since we have ignored the propa- N(d(u,)V是) gation delay,all nodes connected to u in Gt (A,ro,g(r)), lim (d,v) lim d(u,)→oo d,v)】 du,v)+o∞ d(u,v) denoted by Wi,receive the information instantaneously.Then, the transmission process stops.This is because all outgoing (9) connections from Wi are unavailable at this time instance. The transmission process will restart at time slot t2>t1, Then we calculate the delay Tp(m)along path Tm.Accord- when at least one node in Wi find the opportunity to forward ing to the Strong Law of Large Numbers,with probability 1,the packet to a new node,denoted by u2.At this time slot we have u2 transmits the packet to a set of new nodes (not in W) T,(πm) ∑eenT.(e which are connected to u2 in G2(,ro,g(r)),denoted by W2. lim =lim d(u,)→oN(d(u,v)d(u,w)→xN(d(u,v) =E[Te(e)]. instantaneously.This process goes on,until at time slot t, node u and the destination node v are in the same connected Therefore. cluster and the packet is transmitted to node v instantaneously. (u,≤1im ()=细a武u, Tn(πm) We can see that the cluster to cluster transmission as a series d→od(u,v) of outbursts.During each outburst,a set of new nodes receive Tp(πm） Na(d(u,v)) the packet.W,k =1,2,...,M is the set of nodes which u识Ndu, lim d(u,v) receive the information right at the kth outburst.uk W-1 is the starting node at the kth outburst.It is possible that at = 入ET.(el (10) time tk,two nodes u and u find transmission opportunity simultaneously.Choosing different starting nodes will lead to From the definition of the path mm,we know that the length different cluster to cluster transmission processes. of each hop is smaller thanro Besides,the A cluster to cluster transmission process can be fully connection function g(r)is monotone decreasing.Thus,for a described by II ={(t1,u1),(t2,u2),...,(tM,uM)).Packets link e whose length is f,there must be can be transmitted from u to v through II.Define the passage time for the cluster to cluster transmission process II as ET.(e】≤E[T.(e〗-∑kP(T.(e)-k Tp(I)=tM-t1. k=0 ∑k1-9)泸g)=g 1 Then,we have the following lemma. -1.(11) Lema4.Given nodes u,v∈C(G(入，ro,f(r),the first Thus passage time (A) o≤VE(-） Ta(u,v)=inf{Tp(II II is a cluster to cluster (12) transmission process from u to v. Proof:For convenience,we use to denote the set of V all the cluster to cluster transmission processes from u to v. Then Egn.(12)can be rewritten as 入 T(u,v)=inf{T(I)lΠ∈生} Furthermore,from property (2)of theorem 1,we know (A) is a monotone decreasing function.Thus, It is easy to see that for each cluster to cluster transmission processⅡfrom u to v, 1 Y()≤ inf '∈AL(1+e),N z(1+e T,(Π≥T(u,w). Thus, inf{T()lΠ∈}≥T(u,v) (13) B.Lower Bound of (A) 1)Cluster to Cluster Transmission:In section IV-A,we Next,we show that have obtained the upper bound of y(A)by calculating the delay along one path.However,the method used in section IV-A inf{T(I)lΠ∈}≤T(u,v). cannot be used to study the lower bound of ()It is hard to obtain the number of paths connecting two nodes.The delay 7Here.we do not require t2 to be the smallest,i.e.,there may exist t1< t<t2.such that at least one node in w have the opportunity to forward along each path is random and may correlate with that of other the information to a new node at time slot t

6 Lemma 3 gives the rigorous definition of κϵ, which is a useful parameter in Theorem 2 and Theorem 3. The proof of Lemma 3 is based on a conclusion on subadditivity and is given in section V-A. According to lemma 3, we immediately get lim d(u,v)→∞ Nλ(d(u, v)) d(u, v) = lim d(u,v)→∞ NλL (d(u, v) √ λ λL ) d(u, v) = κϵ √ λ λL . (9) Then we calculate the delay Tp(πm) along path πm. Accord￾ing to the Strong Law of Large Numbers, with probability 1, we have lim d(u,v)→∞ Tp(πm) Nλ(d(u, v)) = lim d(u,v)→∞ ∑ e∈πm Tc(e) Nλ(d(u, v)) = E[Tc(e)]. Therefore, γ(λ) = lim d→∞ Tλ(u, v) d(u, v) ≤ lim d→∞ Tp(πm) d(u, v) = lim d(u,v)→∞ Tp(πm) Nλ(d(u, v)) · lim d→∞ Nλ(d(u, v)) d(u, v) = κϵ √ λ λL E[Tc(e)]. (10) From the definition of the path πm, we know that the length of each hop is smaller than r˜ = r0 √ λL(1+ϵ) λ . Besides, the connection function g(r) is monotone decreasing. Thus, for a link e ′ whose length is r˜, there must be E[Tc(e)] ≤ E[Tc(e ′ )] = ∑∞ k=0 kP(Tc(e ′ ) = k) = ∑∞ k=0 k(1 − g(˜r))k g(˜r) = 1 g(˜r) − 1. (11) Thus, γ(λ) = κϵ √ λ λL E[Tc(e)] ≤ κϵ √ λ λL ( 1 g(˜r) − 1 ) = κϵ √ λ λL   1 g ( r0 √ λL(1+ϵ) λ ) − 1   . Furthermore, from property (2) of theorem 1, we know γ(λ) is a monotone decreasing function. Thus, γ(λ) ≤ inf λ ′∈[λL(1+ϵ),λ] κ √ λ ′ λL ( 1 g ( r0 √λL(1+ϵ) λ ′ ) − 1). B. Lower Bound of γ(λ) 1) Cluster to Cluster Transmission: In section IV-A, we have obtained the upper bound of γ(λ) by calculating the delay along one path. However, the method used in section IV-A cannot be used to study the lower bound of γ(λ). It is hard to obtain the number of paths connecting two nodes. The delay along each path is random and may correlate with that of other paths. Therefore, it is usually intractable to obtain the delay from Eqn. (4). To overcome this difficulty, we introduce the concept of cluster to cluster transmission. Consider the packet transmission process from node u to node v. Assume that at time slot t1, node u1(u1 = u) transmits a packet to other nodes. Since we have ignored the propa￾gation delay, all nodes connected to u1 in Gt1 (λ, r0, g(r)), denoted by W1, receive the information instantaneously. Then, the transmission process stops. This is because all outgoing connections from W1 are unavailable at this time instance. The transmission process will restart at time slot t2 > t1 7 , when at least one node in W1 find the opportunity to forward the packet to a new node, denoted by u2. At this time slot, u2 transmits the packet to a set of new nodes (not in W1) which are connected to u2 in Gt2 (λ, r0, g(r)), denoted by W2, instantaneously. This process goes on, until at time slot tM, node uM and the destination node v are in the same connected cluster and the packet is transmitted to node v instantaneously. We can see that the cluster to cluster transmission as a series of outbursts. During each outburst, a set of new nodes receive the packet. Wk, k = 1, 2, ..., M is the set of nodes which receive the information right at the kth outburst. uk ∈ Wk−1 is the starting node at the kth outburst. It is possible that at time tk, two nodes u 1 k and u 2 k find transmission opportunity simultaneously. Choosing different starting nodes will lead to different cluster to cluster transmission processes. A cluster to cluster transmission process can be fully described by Π = {(t1, u1),(t2, u2), ...,(tM, uM)}. Packets can be transmitted from u to v through Π. Define the passage time for the cluster to cluster transmission process Π as Tp(Π) = tM − t1. Then, we have the following lemma. Lemma 4. Given nodes u, v ∈ C(G(λ, r0, f(r))), the first passage time Tλ(u, v) = inf{Tp(Π)|Π is a cluster to cluster transmission process from u to v}. (12) Proof: For convenience, we use L to denote the set of all the cluster to cluster transmission processes from u to v. Then Eqn.(12) can be rewritten as Tλ(u, v) = inf{Tp(Π)|Π ∈ L }. It is easy to see that for each cluster to cluster transmission process Π from u to v, Tp(Π) ≥ Tλ(u, v). Thus, inf{Tp(Π)|Π ∈ L } ≥ Tλ(u, v). (13) Next, we show that inf{Tp(Π)|Π ∈ L } ≤ Tλ(u, v). 7Here, we do not require t2 to be the smallest, i.e., there may exist t1 < t ′ < t2, such that at least one node in w1 have the opportunity to forward the information to a new node at time slot t ′

Recall the definition of Ta(u,v),i.e., The first cluster The second cluster···The Mth cluster T(u,v)=inf{Tp(π)：is a path from u to v}. Let To be the path with minimum delay from u to v,we prove that there exists a cluster to cluster transmission process IIo,such that Tp(Io)=Tp(To). Assume that To =ioii2...ik(io u,ik =v).At time slot t1,some nodes in path mo may be in the same connected cluster as io.Let im-be the node attainable from io with largest subindex,then the link between im-1 and im must be Fig.2.Illustration of a cluster to cluster transmission process. off at this time slot.Let t2>t be the first time slot that this link is on.At time slot t2,let in-be the node attainable from im with largest subindex.Then the link between in- Note that,Vk =1,2,...M-1,u(k+1)is connected to a and in must be off until time slot t3>t2.At time slot tk, node in Wk,denoted by u'.Then, node in and destination node v are in the same connected cluster and the information transmit to v instantaneously.We ‖uk+四-因)‖≤Iuk+-I+‖u-川 denote by Ilo this cluster to cluster transmission process.And ≤Sg,tk,u()()+T0 Π0={(t1,i0),(t2,in),(tk,ik-1)} As for k=M. From the construction of Ilo,it is obvious that Tp(Io)= Tp(no). lyz-uM)I≤Sg.t.ua(, Thus, Combining the above two inequalities together,we obtain, T(u,v)=T(πo)=T,(o) ≥inf{T()lⅢ∈坐} (14) d(u,v)=‖v-ul M- Combining Eqn.(21)and Eqn.(14),we obtain ∑Ik+)-u)I+‖-a0 T(u,v)=inf{T()lΠ∈}. k=1 M- ■ ≤ Based on the cluster to cluster transmission process,we are ∑(Sgu()+ro)+Sgt,n( k=1 now ready to compute a lower bound of (A). M 2)Compute the Lower Bound:In this section,we use the (Sg,u()+r0) (15) concept of cluster to cluster transmission to derive a lower k=1 bound of (A). To start with,we need to introduce a random variable For each k,it is easy to check that S.)admits the Sa.t.u(A)(g is the connection function,u is a node)to same distribution as another random variable g(A).Further, represent the radius of the connected cluster W(fu)in the we can prove the following lemma. instantaneous geometric random graph G(A,ro,g(r)).We Lemma 5.With probability 1,we have establish a cartesian coordinate in R2.We define H(zo,a) as lim ∑SguN=ES,(》 (16) H(20,a)={z=(z红，y)∈R21‖z-20‖ Π={(u),t1),(u②)，t2,,(ua0,tM)} Me(this condition is satisfied for large enough d(u,v)),we have where u(1)=u,and u(M),v are in the same connected cluster at the time instance tM.Then the delay along this cluster to (()+ro<E(S()+ro)+e cluster transmission process is M-1 Combined with Eqn.(15),we have Tn()=tM-t=∑(tk+1-t)≥M-1. k=1 d(u,v)<M(E(Sg()+ro)+e1)

7 Recall the definition of Tλ(u, v), i.e., Tλ(u, v) = inf {Tp(π) : π is a path from u to v}. Let π0 be the path with minimum delay from u to v, we prove that there exists a cluster to cluster transmission process Π0, such that Tp(Π0) = Tp(π0). Assume that π0 = i0i1i2...iK(i0 = u, iK = v). At time slot t1, some nodes in path π0 may be in the same connected cluster as i0. Let iη1−1 be the node attainable from i0 with largest subindex, then the link between iη1−1 and iη1 must be off at this time slot. Let t2 > t1 be the first time slot that this link is on. At time slot t2, let iη2−1 be the node attainable from iη1 with largest subindex. Then the link between iη2−1 and iη2 must be off until time slot t3 > t2...At time slot tk, node iηk−1 and destination node v are in the same connected cluster and the information transmit to v instantaneously. We denote by Π0 this cluster to cluster transmission process. And Π0 = {(t1, i0),(t2, iη1 ), ...,(tk, iηk−1 )}. From the construction of Π0, it is obvious that Tp(Π0) = Tp(π0). Thus, Tλ(u, v) = Tp(π0) = Tp(Π0) ≥ inf{Tp(Π)|Π ∈ L }. (14) Combining Eqn.(21) and Eqn.(14), we obtain Tλ(u, v) = inf{Tp(Π)|Π ∈ L }. Based on the cluster to cluster transmission process, we are now ready to compute a lower bound of γ(λ). 2) Compute the Lower Bound: In this section, we use the concept of cluster to cluster transmission to derive a lower bound of γ(λ). To start with, we need to introduce a random variable Sg,t,u(λ) (g is the connection function, u is a node) to represent the radius of the connected cluster W({u}) in the instantaneous geometric random graph Gt(λ, r0, g(r)). We establish a cartesian coordinate in R 2 . We define H(z0, a) as H(z0, a) = {z = (zx, zy) ∈ R 2 | ∥ z − z0 ∥ 0, ∃Mϵ1 , such that ∀M > Mϵ1 (this condition is satisfied for large enough d(u, v)), we have ∑M k=1(Sg,tk,u(k) (λ) + r0) M < E(Sg(λ) + r0) + ϵ1. Combined with Eqn. (15), we have d(u, v) < M(E(Sg(λ) + r0) + ϵ1)

Then Note that (A)is a monotone decreasing function,thus d(u,v) T,(四≥M-1>ESgA)+0)+4 --1. ()≤ inf (19) Note that the right hand side of the above inequality does not X'e[xz(1+e,月 L(1+e) A depend on the selection of the cluster to cluster transmission processes.Thus, Then we consider the lower bound.Similar to the previous part,we still focus on the cluster to cluster transmission. d(u,v) T(u,w)之E(SgA)+T0)+1 -1. Consider a cluster to cluster transmission process Therefore. Π={(u四，t),(u②，t2）,,(ua,tw)}. Similarly,we have,Vk =1,2,...,M-1, Y() lim T(u,v) d(u,v)oo d(u,v) 川uk+1)-u因)≤Sg.,u肉(2)+r0 E(Sg(A)+ro)+e1 As for k=M, (17) Iu-a0≤Sgtu,e()Ar,the network connectivity is maintained at each time slot,and thus the propagation delay will increase ‖+)-u因)l≤min{Sg.u(A,9}+ro (A)substantially ((A)is now bounded below away from 0). The proof of Theorem 3 is in fact a generalization of that As for k=M, of Theorem 2. v-(M)min{S(),)+ro. Proof:We first consider the upper bound.We have already obtained Eqn.(10),i.e., Again,using the method in section IV-B,we immediately obtain 入 ≤V左Ez.(el ()≥Emim{S,),g)+0 where the length of link e is smaller than=roV λL(1+e) ■ Using similar method in deriving Eqn.(11),we obtain V.PROOF E取o】spI=+P0= A.Proof of Lemma 3 The method used in this proof is similar to that used by 1 Dousse et al.in [11]and Kong et al.in [12]. ∑k+1)1-g()*g(时= g() We first construct a cartesian coordinate system.Without = 1 loss of generality,we assume that there is a node at the origin. (18)Let in =arg minec()d(2,(0,n))).We define 入。 N(m,n)=NAL(d(,m)).We first prove that N(0,m) scales linearly with respect to m (Lemma 6).As we will see where e is link whose length is f.The inequality above is later,Lemma 3 follows directly from Lemma 6. slightly different from Eqn.(11).This is because we have Lemma 6.There exists such that taken propagation delay into consideration. Thus, lim (0,m 入 1 m-0 y()≤re m =Ke. 入L AL(1+e) To prove Lemma 6,we use Liggett's subadditive ergodic theorem,which is formally restated below

8 Then Tp(Π) ≥ M − 1 > d(u, v) E(Sg(λ) + r0) + ϵ1 − 1. Note that the right hand side of the above inequality does not depend on the selection of the cluster to cluster transmission processes. Thus, Tλ(u, v) ≥ d(u, v) E(Sg(λ) + r0) + ϵ1 − 1. Therefore, γ(λ) = lim d(u,v)→∞ Tλ(u, v) d(u, v) ≥ 1 E(Sg(λ) + r0) + ϵ1 (17) Let ϵ1 → 0, we finally obtain γ(λ) ≥ 1 E(Sg(λ) + r0) . C. Impact of Propagation Delay The delay in large-scale Wireless Networks is composed of two parts, i.e., the waiting delay and the propagation delay. In previous sections, we ignored the propagation delay τ . Now, we will consider its impact on γ(λ). The propagation delay will not have much influence on γ(λ) when λ is relatively small, because the first passage delay is dominated by the waiting delay. However, when λ is relatively large, e.g., λ > λI , the network connectivity is maintained at each time slot, and thus the propagation delay will increase γ(λ) substantially (γ(λ) is now bounded below away from 0). The proof of Theorem 3 is in fact a generalization of that of Theorem 2. Proof: We first consider the upper bound. We have already obtained Eqn. (10), i.e., γ(λ) ≤ κϵ √ λ λL E[Tc(e)], where the length of link e is smaller than r˜ = r0 √ λL(1+ϵ) λ . Using similar method in deriving Eqn. (11), we obtain E[Tc(e)] ≤ E[Tc(e ′ )] = ∑∞ k=0 (k + τ )P(Tc(e ′ ) = k) < ∑∞ k=0 (k + 1)(1 − g(˜r))k g(˜r) = 1 g(˜r) = 1 g ( r0 √ λL(1+ϵ) λ ) (18) where e ′ is link whose length is r˜. The inequality above is slightly different from Eqn. (11). This is because we have taken propagation delay into consideration. Thus, γ(λ) ≤ κϵ √ λ λL 1 g ( r0 √ λL(1+ϵ) λ ). Note that γ(λ) is a monotone decreasing function, thus γ(λ) ≤ inf λ ′∈[λL(1+ϵ),λ] κϵ √ λ ′ λL 1 g ( r0 √λL(1+ϵ) λ ′ ). (19) Then we consider the lower bound. Similar to the previous part, we still focus on the cluster to cluster transmission. Consider a cluster to cluster transmission process Π = {(u (1), t1),(u (2), t2), ...,(u (M) , tM)}. Similarly, we have, ∀k = 1, 2, ..., M − 1, ∥ u (k+1) − u (k) ∥≤ Sg,tk,u(k) (λ) + r0. As for k = M, ∥ v − u (M) ∥≤ Sg,tM,u (M) x (λ) < Sg,tM,u(M) (λ) + r0. Besides, the distance transmitted is also limited by the finite hops in one time slot. Since each hop takes τ fraction of a time slot, then a packet can transmit at most 1 τ hops in one time slot. As a result, the longest distance transmitted in one time slot is upper bounded by r0 τ . Then ∀k = 1, 2, ..., M − 1, ∥ u (k+1) − u (k) ∥≤ r0 τ + r0. As for k = M, ∥ v − u (M) ∥≤ r0 τ < r0 τ + r0. Integrating the above four inequalities, we obtain, ∀k = 1, 2, ..., M − 1, ∥ u (k+1) − u (k) ∥≤ min{Sg,tk,u(k) (λ), r0 τ } + r0. As for k = M, ∥ v − u (M) ∥≤ min{Sg,tM,u(M) (λ), r0 τ } + r0. Again, using the method in section IV-B, we immediately obtain γ(λ) ≥ 1 E(min{Sg(λ), r0 τ }) + r0 . V. PROOF A. Proof of Lemma 3 The method used in this proof is similar to that used by Dousse et al. in [11] and Kong et al. in [12]. We first construct a cartesian coordinate system. Without loss of generality, we assume that there is a node at the origin. Let zn = arg minz∈C(B(λL,r0 √ 1+ϵ)){d(z,(0, n))}. We define N ′ λL (m, n) = NλL (d(zn, zm)). We first prove that N ′ λL (0, m) scales linearly with respect to m (Lemma 6). As we will see later, Lemma 3 follows directly from Lemma 6. Lemma 6. There exists κϵ, such that lim m→∞ N ′ λL (0, m) m = κϵ. To prove Lemma 6, we use Liggett’s subadditive ergodic theorem, which is formally restated below

9 Lemma 7.(Liggett [161)Let {SL.m}be a collection of random Before proving Lemma 3,we also need the following variables indexed by integers 0NAL(d(0,2na))-NAL(d(zna:v)).(21) are also satisfied.Now,we only need to prove that conditions Note that 4 and 5 are also satisfied. d(zna:v)i)decays exponentially Using similar method in the proof of Lemma 8,we can with respect to i,then Lemma 8 follows directly.The basic prove E(NAL(d(n)))<oo(to avoid verbosity,we do not idea is to find a sequence of toruses circling nodes zo and elaborate it here).Therefore,N(d(n,v))<oo with prob- zm using nodes in the giant component of B(AL,rov1+e)). ability 1.Further,by the stationarity of Poisson Point Process, Then,we can show that the least number of hops N.,(0,m) N (d(n,v))does not depend on d(u,v).Then,divide Eqn. from zo to Zm cannot be arbitrarily large (see Fig.5).Due (20)and Eqn.(21)by d(u,v),and let d(u,v)oo.We to the supercriticality of B(AL,rov1+e)),we can show that immediately obtain such toruses exist with probability close to 1.Therefore,the probability that NA(0,m)is greater than a large threshold is lim Na(d(u,v)) close to 0.The detailed proof is provided in Section V-B. d(u,v)-oo d(u,v) Then condition 4 of lemma 7 is satisfied.Next,we prove ■ that N (m,n)satisfies condition 5.To demonstrate that N(mk,(m+1))is ergodic.we show that it is strong B.Proof of Lemma 8 mixing,which is a stronger property. Proof:Consider NA (0,m).Let.We draw a Lemma 9.Na (mk,(m+1)k)is strong mixing. series of squares centering at z(Fig.3),and the side lengths The strong mixing property essentially states that the depen- are1,2,4,,2k,… dence between N (mk,(m+1)k)and N((m+n)k,(m+ n+1)k)becomes negligibly small as n becomes large.The strategy to prove this statement resembles some parts of the proof of Lemma 8.We first find two toruses circling the shortest path from 2mk to 2(m+1)k and the shortest path from 2(m+n)k to Z(m+n+1)k,respectively.By the stationarity of Poisson Point Process,we know that the size of the two toruses do not depend on n.Hence,as n increases,the two toruses d/2 will become disjoint eventually.By the spatial independence of Poisson Point Process,we can see that N,(mk,(m+1)k) and N ((m+n)k,(m+n+1))becomes approximately independent when n is large enough.The detailed proof is provided in Section V-C. Fig.3.A series of squares centering at 2. Now,we have proved that N(m,n)satisfy conditions 1-5 of Lemma 7.Thus,there exists ke,such that We use R(d)to denote the rectangle with side lengths and 2d.We say R(d)is good if and only if there exists a crossing lim (0,m) =Ke m m connecting the two short sides in R(d)(Fig.4.(a)).We denote

9 Lemma 7. (Liggett [16])Let {Sl,m} be a collection of random variables indexed by integers 0 ≤ l ≤ m. Suppose {Sl,m} has the following properties: 1) S0,m ≤ S0,l + Sl,m, 0 ≤ l ≤ m; 2) {S(m−1)k,mk, m ≥ 1} is a stationary process for each k; 3) {Sl,l+k, k ≥ 0} = {Sl+1,l+k+1, k ≥ 0} in distribution for each l; 4) E[|S0,m|] < ∞ for each m. Then α , limm→∞ E[S0,m] m = infm≥1 E[S0,m] m ; S , limm→∞ S0,m m exists with probability 1 and E[S] = α. Furthermore, if 5. the stationary process {S(m−1)k,mk, m ≥ 1} is ergodic; then S = α with probability 1. It is easy to see that N ′ λL (0, m) ≤ N ′ λL (0, l) + N ′ λL (l, m)(0 ≤ l ≤ m). Then the first condition of lemma 7 is satisfied. Since Poisson Boolean Model B(λL, r0 √ 1 + ϵ)) is homogeneous, the second and the third conditions of lemma 7 are also satisfied. Now, we only need to prove that conditions 4 and 5 are also satisfied. Lemma 8. E(N ′ λL (0, m)) < ∞. Note that E(N ′ λL (0, m)) = ∑∞ i=1 P(N ′ λL (0, m) ≥ i). If we can show that P(N ′ λL (0, m) ≥ i) decays exponentially with respect to i, then Lemma 8 follows directly. The basic idea is to find a sequence of toruses circling nodes z0 and zm using nodes in the giant component of B(λL, r0 √ 1 + ϵ)). Then, we can show that the least number of hops N ′ λL (0, m) from z0 to zm cannot be arbitrarily large (see Fig. 5). Due to the supercriticality of B(λL, r0 √ 1 + ϵ)), we can show that such toruses exist with probability close to 1. Therefore, the probability that N ′ λL (0, m) is greater than a large threshold is close to 0. The detailed proof is provided in Section V-B. Then condition 4 of lemma 7 is satisfied. Next, we prove that N ′ λL (m, n) satisfies condition 5. To demonstrate that N ′ λL (mk,(m + 1)k) is ergodic, we show that it is strong mixing, which is a stronger property. Lemma 9. N ′ λL (mk,(m + 1)k) is strong mixing. The strong mixing property essentially states that the depen￾dence between N ′ λL (mk,(m+ 1)k) and N ′ λL ((m+n)k,(m+ n + 1)k) becomes negligibly small as n becomes large. The strategy to prove this statement resembles some parts of the proof of Lemma 8. We first find two toruses circling the shortest path from zmk to z(m+1)k and the shortest path from z(m+n)k to z(m+n+1)k, respectively. By the stationarity of Poisson Point Process, we know that the size of the two toruses do not depend on n. Hence, as n increases, the two toruses will become disjoint eventually. By the spatial independence of Poisson Point Process, we can see that N ′ λL (mk,(m + 1)k) and N ′ λL ((m + n)k,(m + n + 1)k) becomes approximately independent when n is large enough. The detailed proof is provided in Section V-C. Now, we have proved that N ′ λL (m, n) satisfy conditions 1 − 5 of Lemma 7. Thus, there exists κϵ, such that lim m→∞ N ′ λL (0, m) m = κϵ. Before proving Lemma 3, we also need the following lemma. Lemma 10. d(zn,(0, n)) < ∞ with probability 1. Intuitively, if d(zn,(0, n)) = ∞, there does not ex￾ist any giant component in B(λL, r0 √ 1 + ϵ)) (otherwise, d(zn,(0, n)) < ∞). This contradict to the supercriticality of B(λL, r0 √ 1 + ϵ)). The detailed proof is presented in section V-D. Now, we are ready to prove Lemma 3. Proof: Consider NλL (d(u, v)). Without loss of generality, we suppose that u is at the origin, v is at the +x axis. Assume that integer nd satisfy nd ≤ d(u, v) < nd + 1, then NλL (d(u, v)) ≤ NλL (d(0, znd )) + NλL (d(znd , v)), (20) and NλL (d(u, v)) ≥ NλL (d(0, znd )) − NλL (d(znd , v)). (21) Note that d(znd , v) ≤ d(znd ,(0, nd)) + d((0, nd), v) ≤ d(znd ,(0, nd)) + 1 < ∞. Using similar method in the proof of Lemma 8, we can prove E(NλL (d(znd , v))) < ∞(to avoid verbosity, we do not elaborate it here). Therefore, NλL (d(znd , v)) < ∞ with prob￾ability 1. Further, by the stationarity of Poisson Point Process, NλL (d(znd , v)) does not depend on d(u, v). Then, divide Eqn. (20) and Eqn. (21) by d(u, v), and let d(u, v) → ∞. We immediately obtain lim d(u,v)→∞ NλL (d(u, v)) d(u, v) = κϵ. B. Proof of Lemma 8 Proof: Consider N ′ λL (0, m). Let z ′ = z0+zm 2 . We draw a series of squares centering at z ′ (Fig. 3), and the side lengths are 1, 2, 4, ..., 2 k , ....                         G G z᱐ G Fig. 3. A series of squares centering at z ′ . We use R(d) to denote the rectangle with side lengths d 2 and 2d. We say R(d) is good if and only if there exists a crossing connecting the two short sides in R(d) (Fig. 4.(a)). We denote

10 the event that R(d)is good by Ar(d).Note that the Poisson [it must intersect with the circuit in C()(Fig Boolean Model B(AL,rov1+e)is percolated.By Corollary 5).We can replace the part of the path ACB with ADB,then 4.1 in [15],we have the resulting path is shorter.Thus,the shortest path from zo to lim P(AR(d))=1. (22) 2m must be contained in [ 2 2d d (a)Illustration of a good rectangle (b)Illustration of a good square R(d). torus C(d).Here,=(2). Fig.4.Illustration of a good rectangle and a good square torus. -2- We use C(d)to denote the square torus (d,dx Fig.5.The contradiction if the shortest path from zo to is not contained [y-d,y+d)八2-是2+引×[y-是，2y+)We say in2红-2*，2红+21×2g-2*,2g+21. C(d)is good if and only if there exists a circuit in C(d)(Fig. 4.(b)).We denote the event that C(d)is good by Ac(d).From Fig.4.(b),we can see that C(d)is composed of four x 2d Suppose u,v,w are three consecutive nodes along this rectangles,i.e,Ri(d)=[2z-d,z]x [zy-d,zu+dl, shortest path.Then u-w>(1+e)ro,or we can eliminate R2(d=+是，+d×y-d,g+d,(d=-d,z2+ node v,and get a shorter path.This also indicates that if d×y+是，g+,R4(④=[以-d,2+d×[g-d,,-1 we draw disks with radius centering at u and w respectively,the two disks are disjoint.Assume the number of And we use Ar(d)(i=1,2,3,4)to represent the event that Ri(d)is good. hops of the shortest path is N,then we can draw disjoint Obviously,if Vi =1,2,3,4,Ri(d)is good,C(d)must be disks in total.And these disks are all located in a square with good.Thus, side length 2+1+(1+e)ro.Thus, P(Ac(d)≥P(AR(d∩AR(d∩AR(d∩AR(d) 台但+e严y≤e++oP 2 Note that Vi =1,2,3,4.AR,(d)is an increasing events. According to the FKG Inequality (Theorem 2.4 in [10]),we Then. have Ls82+1+1+9m2 π(1+e)ro)2 P(Ac(d)≥P(AR,(d∩AR(d∩AR(d∩AR(d) ≥ P(AR,(d))P(ARz(d))P(ARs(d))P(ARa(d)) Note that N(0,m)is the minimum number of hops from P(AR(d))4. (23) To to Im,thus Combine Eqn.(22)with Eqn.(23),and we obtain N(0,m)≤L≤ (2*+1+(1+e)ro)2 lim P(Ac(d))=1. π(1+e)ro)2 d-oa Thus,vi s((r),then none of ((1+E)ro)2 P(Ac(d)≥p. C(2k+1),C(2k+2),...C(2)is good.Thus, Let ko=min{l2k≥‖zm-20l,2k≥dp},then for all k≥ko P(Nz(0,m)> 82*+1+1+gro) P(Ac(2)≥p π(1+e)ro)2 Assume that C(2)(>ko)is good,if the shortest path P(A8(2)≤(1-p)-ko from z0 to zm is not contained in the square [,x o+1 8A random variable N is on the measurable pair(,)is called increasing ifN(w)≤N(u)whenever w≤w Let lk 8((ro),then. x((1+e)r0)2

10 the event that R(d) is good by AR(d). Note that the Poisson Boolean Model B(λL, r0 √ 1 + ϵ) is percolated. By Corollary 4.1 in [15], we have lim d→∞ P(AR(d)) = 1. (22) G G G G G G G G (a) Illustration of a good rectangle R(d).                         G G ]ÿ (b) Illustration of a good square torus C(d). Here, z ′ = (z ′ x, z ′ y ). Fig. 4. Illustration of a good rectangle and a good square torus. We use C(d) to denote the square torus ([z ′ x − d, z′ x + d] × [z ′ y −d, z′ y +d]) \ ([z ′ x − d 2 , z ′ x + d 2 ]×[z ′ y − d 2 , z ′ y + d 2 ]). We say C(d) is good if and only if there exists a circuit in C(d) (Fig. 4.(b)). We denote the event that C(d) is good by AC (d). From Fig. 4.(b), we can see that C(d) is composed of four d 2 × 2d rectangles, i.e., R1(d) = [z ′ x − d, z′ x − d 2 ] × [z ′ y − d, z′ y + d], R2(d) = [z ′ x+ d 2 , z ′ x+d]×[z ′ y−d, z′ y+d], R3(d) = [z ′ x−d, z′ x+ d]×[z ′ y + d 2 , z ′ y +d], R4(d) = [z ′ x−d, z′ x+d]×[z ′ y −d, z′ y − d 2 ]. And we use ARi (d)(i = 1, 2, 3, 4) to represent the event that Ri(d) is good. Obviously, if ∀i = 1, 2, 3, 4, Ri(d) is good, C(d) must be good. Thus, P(AC (d)) ≥ P(AR1 (d) ∩ AR2 (d) ∩ AR3 (d) ∩ AR4 (d)). Note that ∀i = 1, 2, 3, 4, ARi (d) is an increasing event8 . According to the FKG Inequality (Theorem 2.4 in [10]), we have P(AC (d)) ≥ P(AR1 (d) ∩ AR2 (d) ∩ AR3 (d) ∩ AR4 (d)) ≥ P(AR1 (d))P(AR2 (d))P(AR3 (d))P(AR4 (d)) = P(AR(d))4 . (23) Combine Eqn. (22) with Eqn. (23), and we obtain lim d→∞ P(AC (d)) = 1. Thus, ∀ 1 2 (1 +ϵ)r0, or we can eliminate node v, and get a shorter path. This also indicates that if we draw disks with radius (1+ϵ)r0 2 centering at u and w respectively, the two disks are disjoint. Assume the number of hops of the shortest path is N, then we can draw L 2 disjoint disks in total. And these disks are all located in a square with side length 2 k+1 + (1 + ϵ)r0. Thus, L 2 · π( (1 + ϵ)r0 2 ) 2 ≤ (2k+1 + (1 + ϵ)r0) 2 . Then, L ≤ 8(2k+1 + (1 + ϵ)r0) 2 π((1 + ϵ)r0) 2 . Note that N ′ λL (0, m) is the minimum number of hops from x0 to xm, thus N ′ λL (0, m) ≤ L ≤ 8(2k+1 + (1 + ϵ)r0) 2 π((1 + ϵ)r0) 2 . Now, if N ′ λL (0, m) > 8(2k+1+(1+ϵ)r0) 2 π((1+ϵ)r0) 2 , then none of C(2k0+1), C(2k0+2), ..., C(2k ) is good. Thus, P(N ′ λL (0, m) > 8(2k+1 + (1 + ϵ)r0) 2 π((1 + ϵ)r0) 2 ) ≤ ∏ k i=k0+1 P(A c C (2i )) ≤ (1 − ρ) k−k0 . Let lk = 8(2k+1+(1+ϵ)r0) 2 π((1+ϵ)r0) 2 , then