Under the i.i.d.mobility assumption,the critical trans- IV.THE CRITICAL TRANSMISSION RANGE FOR MOBILE mission range is√器，whee是<d≤l. K-HOP CLUSTERED NETWORKS,RANDOM WALK For stationary k-hop clustered networks,the critical trans- MOBILITY mission range is r(n)where We first define several key notations that will be For both mobile and stationary k-hop clustered networks, v(m+) O(nl-dlogn)neighbors are necessary and sufficient. used throughout this section.Let .=jos mim(g,Ym∈M,m,=arg min(mp-,vm∈M v(m) Before we prove these results rigorously,we now give an and pm.=p.,wherem)is the value of the discrete random intuitive approach to estimate the order of critical transmission variable V-the speed of cluster member.Recall that by our range in each scenario here: assumption,m.is independent of n when n is large while v. Suppose there are n cluster members and nd cluster heads is a function of n for all n.(See Section II.B)Also v,is not uniformly distributed in a unit square.Thus,roughly speaking, equal to v(m.),which can be easily seen from the definition there is one cluster head within an area of of v.. Under the random walk mobility assumption,the area In this section,we have the following main result. covered by movement during k time-slots constitutes the dominating part of a cluster member's coverage area. Theorem 4.1:Under the random walk mobility assumption, Assume that the velocities of nodes are uniformly a the critical transmission range is(n)where constant v.Thus,in order to reach a cluster head,on d<1. average we need Remark Recall the assumption thatm)) 1 1 logn 2kurm）=a,orrm）=2km with <Combined withr(n)it implies that (n)=o(nd-d).In other words,the speed is fast enough so 他U With certain transmission range,consider the number of that nodes can move multiple transmission ranges before the other nodes within the coverage of an arbitrary cluster deadline.Further,it is easy to verify that r(n)=o member during its movement in one period,we have nd- (n)=(n+n).2kr(n)=n1-d+1. A.Necessary condition on r(n)of Theorem 4.1 Under the i.i.d.mobility assumption,considering that We start with the following lemma. cluster members actually remain static during any time- slot,the coverage consists of the overall area of k disks. Thus,on average we need Lema:rr)=产，where<<he for any fixed1and)there exists No such that for all n>No,the following holds kπr2(n)= nd,or r(n)= n(-1+m)2nmm)≥e-李s,- Similarly,we have (1) (n）=(m+n4·krr2(n)=n1-d+1. where0<d≤l. Proof:Taking the logarithm of the left hand side of(1), .In the stationary networks,a reachable cluster head is we get roughly within a disk with a radius kr(n)of the cluster member,and thus we need log (L.H.S.of (1))=logn+ 2 rraP-点w间-g n41og(1-(1+(n)2km.r(m) (2) Similarly,we obtain Using the power series expansion for log(1-x), (n)=(n+n4·π(kr(n)2=n-d+1. log (L.H.S.of (1)) In the following,we will prove the necessary and sufficient (1+(n)2kmr(m)】》 conditions for the critical transmission range r(n)under random walk,i.i.d.and stationary k-hop models.The main idea for the proofs of necessary condition is to show that the probability of disconnection would be lower bounded from sn-n(cmko)'+sa)e do zero if the critical transmission range is no greater than r(n). Similarly,for proofs of sufficient conditions,we will prove that where the probability of session failure (i.e.network disconnected) would approach 0 asymptotically. G(n,k,e(n))=(1+e(n))2kv(m.)r(n)5 • Under the i.i.d. mobility assumption, the critical trans￾mission range is √ log n kπnd , where 1 k < d ≤ 1. • For stationary k-hop clustered networks, the critical trans￾mission range is r(n) = 1 k √d log n πnd , where 0 < d < 1. • For both mobile and stationary k-hop clustered networks, Θ(n 1−d log n) neighbors are necessary and sufficient. Before we prove these results rigorously, we now give an intuitive approach to estimate the order of critical transmission range in each scenario here: Suppose there are n cluster members and n d cluster heads uniformly distributed in a unit square. Thus, roughly speaking, there is one cluster head within an area of 1 nd . • Under the random walk mobility assumption, the area covered by movement during k time-slots constitutes the dominating part of a cluster member’s coverage area. Assume that the velocities of nodes are uniformly a constant v. Thus, in order to reach a cluster head, on average we need 2kvr(n) = 1 nd , or r(n) = 1 2kvnd ; With certain transmission range, consider the number of other nodes within the coverage of an arbitrary cluster member during its movement in one period, we have ϕ(n) = (n + n d ) · 2kvr(n) = n 1−d + 1. • Under the i.i.d. mobility assumption, considering that cluster members actually remain static during any time￾slot, the coverage consists of the overall area of k disks. Thus, on average we need kπr 2 (n) = 1 nd , or r(n) = √ 1 kπnd ; Similarly, we have ϕ(n) = (n + n d ) · kπr 2 (n) = n 1−d + 1. • In the stationary networks, a reachable cluster head is roughly within a disk with a radius kr(n) of the cluster member, and thus we need π ( kr(n) )2 = 1 nd , or r(n) = 1 k √ 1 πnd ; Similarly, we obtain ϕ(n) = (n + n d ) · π ( kr(n) )2 = n 1−d + 1. In the following, we will prove the necessary and sufficient conditions for the critical transmission range r(n) under random walk, i.i.d. and stationary k-hop models. The main idea for the proofs of necessary condition is to show that the probability of disconnection would be lower bounded from zero if the critical transmission range is no greater than r(n). Similarly, for proofs of sufficient conditions, we will prove that the probability of session failure (i.e. network disconnected) would approach 0 asymptotically. IV. THE CRITICAL TRANSMISSION RANGE FOR MOBILE K-HOP CLUSTERED NETWORKS, RANDOM WALK MOBILITY We first define several key notations that will be used throughout this section. Let v⋆ = v (m⋆) logn npm⋆ = min{ v (m) logn npm , ∀m ∈ M}, m⋆ = arg min{ v (m) logn npm , ∀m ∈ M} and pm⋆ = p⋆, where v (m) is the value of the discrete random variable V — the speed of cluster member. Recall that by our assumption, m⋆ is independent of n when n is large while v⋆ is a function of n for all n. (See Section II.B) Also v⋆ is not equal to v (m⋆) , which can be easily seen from the definition of v⋆. In this section, we have the following main result. Theorem 4.1: Under the random walk mobility assumption, the critical transmission range is r(n) = log n 2kv⋆nd , where 0 < d ≤ 1. Remark 4.1: Recall the assumption that v (m) = ω( √log n nd′ ) with d ′ < d 2 . Combined with r(n) = log n 2kv⋆nd , it implies that r(n) kv⋆ = o(n d ′−d ). In other words, the speed is fast enough so that nodes can move multiple transmission ranges before the deadline. Further, it is easy to verify that r(n) = o ( √ log n n d− d′ 2 ) . A. Necessary condition on r(n) of Theorem 4.1 We start with the following lemma. Lemma 4.1: If r(n) = d0 2 log n+κ 2kv⋆nd , where d ′ < d0 < d, then for any fixed θ < 1 and ϵ(n) = 1 log n , there exists N0 such that for all n ≥ N0, the following holds n do 2 ( 1 − ( 1 + ϵ(n) ) 2kv(m⋆) r(n) )n d ≥ θe−κ− d0 2 log p⋆− d0 2 , (1) where 0 < d ≤ 1. Proof: Taking the logarithm of the left hand side of (1), we get log ( L.H.S. of (1)) = d0 2 log n+ n d log ( 1 − ( 1 + ϵ(n) ) 2kv(m⋆) r(n) ) . (2) Using the power series expansion for log (1 − x), log (L.H.S. of (1)) = d0 2 log n − n d∑∞ i=1 (( 1 + ϵ(n) ) 2kv(m⋆) r(n) )i i = d0 2 log n − n d (∑ 2 i=1 1 i ( G ( n, κ, ϵ(n) ) )i + δ(n) ) (3) where G ( n, κ, ϵ(n) ) = ( 1 + ϵ(n) ) 2kv(m⋆) r(n)