> Specifically,for the first term,using Lemma 4.1 with e(n)= along a straight line.But we can show that this event happens we know that it is bounded by with very low probability.Let o be the angle of intersection and e=e(n)=,where d'<and d<do d.Note n n粤(1-(r2(m)+2km.r(m)） that for the angle o to be greater than -E,the trajectories from both i and j must be no more than an angle 5 away =n粤(（1-(1+61(m)2km.rm)” from the line connecting i and j.Then we have >n(1-(1+(n)2kum.r(m)） Po>-9<(会)}=2 4r2nd.,(9) ≥0e-k-孕1ogp,-9, (6) where d,=2(d-d'>d>do.Then,for suchπ/2≤p≤ where n)(n)according to the Remark 4.1 T-E,the intersection is of area and0<0<1. 2rm.2rm≤4r(m)kum). r(n)1 To bound the second term,note that the main difficulty here sino ku(m.)E(n) is that the trajectories of si and si may overlap.Let (0<< )be the angle of intersection.Then the overlapping area can = 0 /4r(n)ku(m.)八 (10) log2n be as large as 4r2(n)/sin.In comparison,the trajectories of si and sj cover an area of 2r(n)kv(m.)each.Hence,in where we have used Remark 4.1. order to show that the overlapping area does not significantly Let S denote the total area covered by i and j during affected the probability of connectivity,the key is to show that the period A.Then for some we can obtain with high probability the angel o cannot be too close to either that,whenever o<m-s the following holds. 0orπ. S4≥4r(n)km.)-o 4r(n)kv(m.) log2n = (1-e)4r(n)km,), (11) for all n>N.Let Tij be the event that S (1- e)4r(n)kv(m.),taking into account both cases we have P(Tu)1 logn Therefore,each term in the second summation is bounded Fig.5.Overlapped Area-1 y There are two cases.First,if</2,then as illustrated PA({s;and sj are failed sessions in Gr}) in Figure 5,the angle of intersection must be of order =PA({si and sj are failed sessions in Gru}Tij)P(Tij) V1/m西 +PA({si and sj are failed sessions in Gru}Tij)P(Tij) kv(m.) ≤pA({si and sj are failed sessions in Gr}|Tj） Hence,in this case,the intersection of the trajectories of i and +P(T) j,with probability one,is of area 1 (2r(n)2 ≤(-1-)4rokm）”+47g sin Vi/nd ~4r(n)km.）.r(m)n号 k(m*丁 e-4nd(1-e')r(n)ku(m.) + 4r(n)kv(m.) 4n2nd. (8) log2n ≤e21-e)1ogn(np.(学1ogn+)+logn nd. where we have used Remark 4.1. (12) where the forth step is due to the well-known bound 1-x≤e-for x∈[0,1. (13) Therefore,combined with (6)and (12)in(5),we obtain P片rm(n,r(n) ≥0e--學1ogn,-当 Fig.6.Overlapped Area-2 -(e-.m+紧2） Next,consider the case when >/2 as shown in Figure 6. The angle of intersection can be close to r if the two tracks are for all n Ne.=max{Na,N).7 Specifically, for the first term, using Lemma 4.1 with ϵ(n) = 1 log n , we know that it is bounded by n d0 2 ( 1 − ( πr2 (n) + 2kv(m⋆) r(n) ) )n d = n d0 2 ( 1 − ( 1 + ϵ1(n) ) 2kv(m⋆) r(n) )n d > n d0 2 ( 1 − ( 1 + ϵ(n) ) 2kv(m⋆) r(n) )n d ≥ θe−κ− d0 2 log p⋆− d0 2 , (6) where ϵ1(n) = πr(n) 2kv(m⋆) < ϵ(n) according to the Remark 4.1 and 0 < θ < 1. To bound the second term, note that the main difficulty here is that the trajectories of si and sj may overlap. Let ϕ(0 ≤ ϕ < π) be the angle of intersection. Then the overlapping area can be as large as 4r 2 (n)/ sin ϕ. In comparison, the trajectories of si and sj cover an area of 2r(n)kv(m⋆) each. Hence, in order to show that the overlapping area does not significantly affected the probability of connectivity, the key is to show that with high probability the angel ϕ cannot be too close to either 0 or π. i j ᵠ Fig. 5. Overlapped Area–1 There are two cases. First, if ϕ < π/2, then as illustrated in Figure 5, the angle of intersection must be of order Θ (√ 1/nd0 kv(m⋆) ) = o (√ 1 nd0−d′ log n ) = Ω (√ 1 nd0 ) . (7) Hence, in this case, the intersection of the trajectories of i and j, with probability one, is of area (2r(n))2 1 sin √ 1/nd0 kv(m⋆) ∼ 4r(n)kv(m⋆) · r(n)n d0 2 = o ( 4r(n)kv(m⋆) log2 n ) , (8) where we have used Remark 4.1. i j ᵠ Fig. 6. Overlapped Area–2 Next, consider the case when ϕ > π/2 as shown in Figure 6. The angle of intersection can be close to π if the two tracks are along a straight line. But we can show that this event happens with very low probability. Let ϕ be the angle of intersection and ε = ε(n) = log2 n nd−d′ , where d ′ < d 2 and d ′ < d0 < d. Note that for the angle ϕ to be greater than π − ε, the trajectories from both i and j must be no more than an angle ε 2 away from the line connecting i and j. Then we have P(ϕ > π − ε) < ( ε 2π )2 = log4 n 4π 2n2(d−d′) = log4 n 4π 2nd⋆ , (9) where d⋆ = 2(d − d ′ ) > d > d0. Then, for such π/2 ≤ ϕ ≤ π − ε, the intersection is of area 2r(n) sin ϕ · 2r(n) ≤ 4r(n)kv(m⋆) · r(n) kv(m⋆) · 1 ε(n) = o ( 4r(n)kv(m⋆) log2 n ) , (10) where we have used Remark 4.1. Let S Λ i+j denote the total area covered by i and j during the period Λ. Then for some ϵ ′ = o ( 1 log2 n ) we can obtain that, whenever ϕ ≤ π − ε the following holds. S Λ i+j ≥ 4r(n)kv(m⋆) − o ( 4r(n)kv(m⋆) log2 n ) = (1 − ϵ ′ )4r(n)kv(m⋆) , (11) for all n > Nϵ ′ . Let Tij be the event that S Λ i+j ≥ (1 − ϵ ′ )4r(n)kv(m⋆) , taking into account both cases we have P(Tij ) > 1 − log4 n 4π 2nd⋆ . Therefore, each term in the second summation is bounded by P Λ ({si and sj are failed sessions in Grw}) = P Λ ({si and sj are failed sessions in Grw} | Tij )P(Tij ) +P Λ ({si and sj are failed sessions in Grw} | Tij )P(Tij ) ≤ P Λ ({si and sj are failed sessions in Grw} | Tij ) + P(Tij ) ≤ ( 1 − ( 1 − ϵ ′ ) 4r(n)kv(m⋆) )n d + log4 n 4π 2nd⋆ ≤ e −4n d (1−ϵ ′ )r(n)kv(m⋆) + log4 n 4π 2nd⋆ ≤ e −2(1−ϵ ′ ) logn (np⋆)( d0 2 log n+κ) + log4 n nd⋆ (12) where the forth step is due to the well-known bound 1 − x ≤ e −x for x ∈ [0, 1]. (13) Therefore, combined with (6) and (12) in (5), we obtain P Λ f rw(n, r(n)) ≥ θe−κ− d0 2 log p⋆− d0 2 −n d0 ( e −2(1−ϵ ′ ) logn (np⋆)( d0 2 log n+κ) + log4 n nd⋆ ) , for all n > Nθ,ϵ′ = max{Nθ, Nϵ ′}