and selected cells u(n) 6(n)= 雪(c.t) 1(c(a,,em)） 31-G(n,k,e(m) 1(Gn,kem)）3 ndo 3 G(n,K,e(n)) c) Fig.4.Cell Selection (4) for all large n.Substituting(4)in (3),we get Note that,by appropriately choosing u(n)(e.g.choosing log (L.H.S.of (1)) u(n)= /Clogn,where the factor C can be set according to the value of do and pm..For a rigorous proof,see [35. lemma 11]),with high probability,there are at least one cluster member in each of these selected cells taking the speed (m). 2 d Pick such a cluster member node from each of these selected （+)ga+g.仰） cells.There are a total of n of these nodes.Let Y denote the set of such cluster member nodes.Note that any two nodes --空s,-间学gn+空g+网 in Y are at a distance of at least away.Let si be the = session initiated by node i and we say that session si fails if i is not connected (i.e.,it cannot reach a cluster head in k -(1+e(n))klogn p. time-slots).Then,consider an arbitrary period A,we have 5((1+e(n))(logn+s)logn(np.) 6 nd P片rn(n,r(n) Since c(n)o the right hand side converges to 2PA({some session si fails in Gru(n,r(n))}) logp.as n oo.Hence,for any0 we can choose Na such that ≥∑pA({s is the only failed session in(n,r(ml)） iEY b(L-H5.of())之-发-岁gw-空-2 ≥ pA(s;is a failed session in (nr(n)}) ieY for all n>Na.Taking the exponent of both sides and using 0=e-,the result follows. -∑∑pA({s ands are failed sessions ieYj≠i Let g(n,r(n))denote the network where two nodes can in Grw(n,r(n))}). (5) communicate if their Euclidean distance is at most r(n)and PA(n,r(n))be the probability that G(n(n))has some node that is not connected in the period A.Then we have the Next,we will evaluate the two terms on the right hand side of following proposition. (5),respectively.We will find a lower bound for the first term Proposition4.:frm)）=學logn+(n),hen and an upper bound for the second term.Then,P(n,r(n)) 2kv,nd will be proved to be bounded away from zero.Proposition 4.1 will then follows. lim infP片rn(n,r(n) ≥e-(k+粤1ogp)(e-号-e-(k+91og)） 3Equation (2)is similar to the corresponding equation in the proof of where k =limno k(n),K>do-logp.. Theorem 2.1 in [1].However,the summation in [1]is over all nodes,while here the summation is only over nodes i and j in the set Y.The reason Proof:Let u(n)O)Then we divide the unit that we have to consider a smaller set Y is because otherwise the second summation may diverge.In [1],in order to ensure the convergence of the square intocells and each cell is of size (n). corresponding second summation,it is essential that,when nodes i and j Now,among these cells,pick n of them such that each are both disconnected,they must be at least some distance apart.In our case.the corresponding property would require that,if si and sj are both of them is at least away from others.For example,we failed sessions,nodes i and j must be some distance apart.Unfortunately, this property does not hold for all nodes.On the other hand,the restriction can choose a subset of the highlighted cells in Figure 4. to the set Y helps to enforce this property.6 and δ(n) = ∑∞ i=3 1 i ( G ( n, κ, ϵ(n) ) )i ≤ ∑∞ i=3 1 3 ( G ( n, κ, ϵ(n) ) )i = 1 3 ( G ( n, κ, ϵ(n) ) )3 1 − G ( n, κ, ϵ(n) ) ≤ 1 3 ( G ( n, κ, ϵ(n) ) )3 G ( n, κ, ϵ(n) ) = 1 3 ( G ( n, κ, ϵ(n) ) )2 , (4) for all large n. Substituting (4) in (3), we get log ( L.H.S. of (1)) ≥ d0 2 log n − n d ( G ( n, κ, ϵ(n) ) + 5 6 ( G ( n, κ, ϵ(n) ) )2 ) = d0 2 log n − n d ( ( 1 + ϵ(n) ) d0 2 log n + κ nd logn (np⋆) + 5 6 (( 1 + ϵ(n) ) d0 2 log n + κ nd logn (np⋆) )2 ) = −κ − d0 2 log p⋆ − ϵ(n)(d0 2 log n + d0 2 log p⋆ + κ) − ( 1 + ϵ(n) ) κ logn p⋆ − 5 6 (( 1 + ϵ(n) ) ( d0 2 log n + κ) logn (np⋆) )2 nd . Since ϵ(n) = 1 log n , the right hand side converges to −κ − d0 2 log p⋆ − d0 2 as n → ∞. Hence, for any ϵ >˜ 0 we can choose Nϵ˜ such that log ( L.H.S. of (1)) ≥ −κ − d0 2 log p⋆ − d0 2 − ϵ,˜ for all n > Nϵ˜. Taking the exponent of both sides and using θ = e −ϵ˜ , the result follows. Let Grw(n, r(n)) denote the network where two nodes can communicate if their Euclidean distance is at most r(n) and P Λ f rw(n, r(n)) be the probability that Grw(n, r(n)) has some node that is not connected in the period Λ. Then we have the following proposition. Proposition 4.1: If r(n) = d0 2 log n+κ(n) 2kv⋆nd , then lim inf n→∞ P Λ f rw(n, r(n)) ≥ e −(κ+ d0 2 log p⋆) ( e − d0 2 − e −(κ+ d0 2 log p⋆) ) where κ = limn→∞ κ(n), κ > d0 2 − d0 2 log p⋆. Proof: Let u(n) = O (√ log n n ) . Then we divide the unit square into 1 u(n) × 1 u(n) cells and each cell is of size u 2 (n). Now, among these cells, pick n d0 2 of them such that each of them is at least √ 1 nd0 away from others. For example, we can choose a subset of the highlighted cells in Figure 4. YKRKIZKJIKRRY Fig. 4. Cell Selection Note that, by appropriately choosing u(n) (e.g. choosing u(n) = √ C log n n , where the factor C can be set according to the value of d0 and pm⋆ . For a rigorous proof, see [35, lemma 11] ), with high probability, there are at least one cluster member in each of these selected cells taking the speed v (m⋆) . Pick such a cluster member node from each of these selected cells. There are a total of n d0 2 of these nodes. Let Y denote the set of such cluster member nodes. Note that any two nodes in Y are at a distance of at least √ 1 nd0 away. Let si be the session initiated by node i and we say that session si fails if i is not connected (i.e., it cannot reach a cluster head in k time-slots). Then, consider an arbitrary period Λ, we have3 P Λ f rw(n, r(n)) ≥ P Λ ({some session si fails in Grw(n, r(n))}) ≥ ∑ i∈Y P Λ ({si is the only failed session in Grw(n, r(n))}) ≥ ∑ i∈Y P Λ ({si is a failed session in Grw(n, r(n))}) − ∑ i∈Y ∑ j̸=i P Λ ({si and sj are failed sessions in Grw(n, r(n))}). (5) Next, we will evaluate the two terms on the right hand side of (5), respectively. We will find a lower bound for the first term and an upper bound for the second term. Then, P Λ f rw(n, r(n)) will be proved to be bounded away from zero. Proposition 4.1 will then follows. 3Equation (2) is similar to the corresponding equation in the proof of Theorem 2.1 in [1]. However, the summation in [1] is over all nodes, while here the summation is only over nodes i and j in the set Y. The reason that we have to consider a smaller set Y is because otherwise the second summation may diverge. In [1], in order to ensure the convergence of the corresponding second summation, it is essential that, when nodes i and j are both disconnected, they must be at least some distance apart. In our case, the corresponding property would require that, if si and sj are both failed sessions, nodes i and j must be some distance apart. Unfortunately, this property does not hold for all nodes. On the other hand, the restriction to the set Y helps to enforce this property.