Recall that limn(n)=K.Then for any 2>0,there Using the union bound we have exists Na such that for all n Na,k(n)<k+.Consider- 2 ing that the probability of disconnectedness is monotonously p(UE）≤p(E) (14) decreasing in K,we obtain, 1 i=1 Pf_rw(n,r(n)) Next we divide the mobile nodes into two sets.The first set Be-(k+号1ogP.+2+) A contains nodes satisfying vi<,while the second set B -nd (e-2(1-)log.(np.)(og logn contains nodes with vi.For each node in A,because we nd. assume that the space is a torus,no path of trajectory overlaps. In contrast,for each in B,if it moves at a small angle along for all n>max{No.,Na).Note that oo),then one of the four sides,paths of trajectory may overlap and loop around the torus.Hence,these two sets need to be treated ndoe-2(1-)log.(np.)(log n) differently.Specifically ndo-e(1do log p. ndo For node in A,since every node's speed satisfies vi2 Umin, =e-do log p:,asn→o. Pta)≤(-(er2+2enn）°<-2nnr）》 Taking limits,we then have For node in B,because v;is larger than the minimum area swept by the trajectory is 2cr(n).This circumstance occurs, liminf Pf_rw(n,r(n)) e.g.when the node moves parallel to one of the four sides of 7→00 ≥0e-(c+学1ogp,+要+0)-e-2x+91ogP.+ the space and loops around the torus.Hence,for node in B. Since this holds for all >0 and any fixed <1,Proposition p(E)≤(1-2rm）”≤1-2 omincr(n))m 4.1 gets proved.Note that has a lower bound lo.. thus the right hand side of Proposition 4.1 will be above zero. where the second inequality holds on because we have as- ◆ sumed that Umin in the definition of the random walk model in Section II.Then,we have Remark 4.2:Proposition 4.1 provides the necessary condi- tion on r(n)in terms of both k(n)and do,i.e.,in addition to the requirement for k(n)to approach infinity and a lower SPE=PB剧+EP iEA iEB bound for k,this condition also says that any do will result in a positive probability of disconnection.To explain ≤∑（1-2 vmincr(n)”+ this implication,suppose two range ro(n)and ri(n).such iEA thatπr(n)）=多12nts@wihk(m）=o(logn.)and 2kv,nd ∑（1-2 kminc6） rio)二之wee山<小Sedi的 iEB a constant.By Proposition 4.1,we know that ri(n)will result =n1-2 kUminCF(mj）r in a disconnected network.Meanwhile,since k(n)=o(log n) ≤ne2 kumincr(n)nd (by(13) we have ro(n)<r1(n)for all sufficiently large n and the =n-cUmin/v,+1 probability of disconnection is monotonously decreasing in r. Therefore,ro(n)will also result in a disconnected network. ≤n-c logn(nPmin)+1 As an consequence of the Proposition 4.1 and Remark 4.2, we have (npmin) Corollary 4.1:Under the random walk mobility assump- tion.is necessary for the coneetivity of the Consequently,for any c>1,we have mobile k-hop clustered networks with random walk mobility model. P(E)≤ →0，asn→o. (15) Hence we have proved the necessity part of Theorem 4.1. (npmin) Thus,using (15)in (14),we have B.Sufficient condition on r(n)of Theorem 4.1 Suppose there are at most n sessions in a period A,and imp(UE）=o let Ei denote the event that si is a failed session,where i= 1 1,2,...,n.Let the transmission range of each node be r= and the result follows. cr(n),where c>1.Then,it suffices to show that Remark 4.3:Note that there is a small gap between the lim necessary and sufficient conditions.The necessary condition 1 roughly requires)while the sufficient condition8 Recall that limn→∞ κ(n) = κ. Then for any ϵ >ˆ 0, there exists Nϵˆ such that for all n ≥ Nϵˆ, κ(n) ≤ κ + ˆϵ. Consider￾ing that the probability of disconnectedness is monotonously decreasing in κ, we obtain, Pf 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 > max{Nθ,ϵ′ , Nϵˆ}. Note that ϵ ′ = o ( 1 log2 n ) , then n d0 e −2(1−ϵ ′ ) logn (np⋆)( d0 2 log n) = n d0 nd0(1−ϵ ′) e −(1−ϵ ′ )d0 log p⋆ = e −d0 log p⋆ , as n → ∞. Taking limits, we then have lim inf n→∞ Pf rw(n, r(n)) ≥ θe−(κ+ d0 2 log p⋆+ d0 2 +ˆϵ) − e −2(κ+ d0 2 log p⋆+ˆϵ) . Since this holds for all ϵ >ˆ 0 and any fixed θ < 1, Proposition 4.1 gets proved. Note that κ has a lower bound d0 2 − d0 2 log p⋆, thus the right hand side of Proposition 4.1 will be above zero. Remark 4.2: Proposition 4.1 provides the necessary condi￾tion on r(n) in terms of both κ(n) and d0, i.e., in addition to the requirement for κ(n) to approach infinity and a lower bound for κ, this condition also says that any d0 < d 2 will result in a positive probability of disconnection. To explain this implication, suppose two range r0(n) and r1(n), such that πr2 0 (n) = d0 2 log n+κ(n) 2kv⋆nd with κ(n) = o(log n), and πr2 1 (n) = d1 2 log n+κ 2kv⋆nd , where d0 < d1 < d 2 , κ(n) → ∞ and κ is a constant. By Proposition 4.1, we know that r1(n) will result in a disconnected network. Meanwhile, since κ(n) = o(log n) we have r0(n) < r1(n) for all sufficiently large n and the probability of disconnection is monotonously decreasing in r. Therefore, r0(n) will also result in a disconnected network. As an consequence of the Proposition 4.1 and Remark 4.2, we have Corollary 4.1: Under the random walk mobility assump￾tion, r(n) ≥ d 2 log n 2kv⋆nd is necessary for the connectivity of the mobile k–hop clustered networks with random walk mobility model. Hence we have proved the necessity part of Theorem 4.1. B. Sufficient condition on r(n) of Theorem 4.1 Suppose there are at most n sessions in a period Λ, and let Ei denote the event that si is a failed session, where i = 1, 2, . . . , n. Let the transmission range of each node be r = cr(n), where c > 1. Then, it suffices to show that limn→∞ P Λ ( ∪n i=1 Ei ) = 0. Using the union bound we have P Λ ( ∪n i=1 Ei ) ≤ ∑n i=1 P Λ (Ei). (14) Next we divide the mobile nodes into two sets. The first set A contains nodes satisfying vi ≤ 1 k , while the second set B contains nodes with vi > 1 k . For each node in A, because we assume that the space is a torus, no path of trajectory overlaps. In contrast, for each in B, if it moves at a small angle along one of the four sides, paths of trajectory may overlap and loop around the torus. Hence, these two sets need to be treated differently. Specifically For node in A, since every node’s speed satisfies vi ≥ vmin, P Λ (Ei) ≤ ( 1− ( πr2+2kvmincr(n) ) )n d < ( 1−2kvmincr(n) )n d . For node in B, because vi is larger than 1 k , the minimum area swept by the trajectory is 2cr(n). This circumstance occurs, e.g. when the node moves parallel to one of the four sides of the space and loops around the torus. Hence, for node in B, P Λ (Ei) ≤ ( 1 − 2cr(n) )n d ≤ ( 1 − 2kvmincr(n) )n d , where the second inequality holds on because we have as￾sumed that vmin ≤ 1 k in the definition of the random walk model in Section II. Then, we have ∑n i=1 P Λ (Ei) = ∑ i∈A P Λ (Ei) +∑ i∈B P Λ (Ei) ≤ ∑ i∈A ( 1 − 2kvmincr(n) )n d + ∑ i∈B ( 1 − 2kvmincr(n) )n d = n ( 1 − 2kvmincr(n) )n d ≤ ne−2kvmincr(n)n d (by (13)) = n −cvmin/v⋆+1 ≤ n −c logn (npmin)+1 = n ( npmin)c Consequently, for any c > 1, we have ∑n i=1 P Λ (Ei) ≤ n ( npmin)c → 0, as n → ∞. (15) Thus, using (15) in (14), we have limn→∞ P Λ ( ∪n i=1 Ei ) = 0, and the result follows. Remark 4.3: Note that there is a small gap between the necessary and sufficient conditions. The necessary condition roughly requires r(n) = d 2 log n 2kv⋆nd , while the sufficient condition