gap between our correlated and clustered mobility with the number of nodes in each cluster can differ from each other in i.i.d mobility.The main intuition is to divide clusters into cluster mixed situation.The network is therefore denoted as "independent"groups which can be virtually regarded as a g(n,a,[Bi},,rp),in which there are n7 clusters. representative node.Investigating the cluster-mixed state in The ith cluster has i=ns members and a radius of n, Theorem I directly would be challenging.Therefore,in the where i=1,2,...,n7. analysis,we will first study the case that every cluster has a (C4).Cluster-mixed state (w.p.). same number of members and a same radius.Depending on the This state is a generalization of the above three separate relationship between average coverage of access points., states and can generalize previous results.We rewrite m to and the cluster region R2=e(n28),we will have different bem=1+咒na+2a,+咒，which means that we divisions.As three special and main cases of Theorem 1,i.e., =1 i=1 cluster-dense,cluster-sparse,and cluster-interior dense states, regard the cluster as a whole for those in cluster-sparse state, their results and intuitions are presented as follows,from(C1) regard sub-clusters as a group for clusters in cluster-inferior to (C3). dense state,and regard members as separate nodes for clusters (C1).Cluster-sparse state (a+2B <0). in cluster dense state.In other word,m denotes the number We have=V,where0<a≤l,0<y≤1. of "independent"node groups in the network.Therefore,we 1og In this state,we have a+28<0 andR2=o().The have rep.-VKans cluster size is relatively small compared to the average cover- (C5).Cluster-mixed state (a.s.). age of each access point and clusters are sparsely distributed 2og而，wherem=m1+ We have re.a.=√kana nk(a+28)+ in O.On the other hand,the member density of each cluster d= (n-28-)is large,which means the cluster members stay very close in their belonging clusters.Therefore, i=1 This state requires a stronger network connectivity,i.e., each cluster can be virtually regarded as a whole or even as almost surely connectivity.Since cluster mixed state can one representative node and the critical transmission range for generalize the three separate states,we will only prove the this representative node is rp.(R will be shown to be very a.s.connectivity in mixed situation.We show that the price small compared with r2P).Then,the unit square consists of m representative nodes.Recall that the home point of each from w.p.to a.s.is a factor of v2,i.e.,ra.s.=v2rw-p.. cluster moves independently.Therefore,using the result for modelin.we have==V票 IV.CRITICAL TRANSMISSION RANGE FOR CLUSTER-SPARSE STATE (C2).Cluster-dense state (a+28 ) We have.where 0<1. As a special case of Theorem 1,we first investigate the case for critical transmission range in cluster-sparse state. In this state,we have a+2B≥長andπR2=w(&) Proposition 1:In a correlated mobile k-hop clustered net- The cluster size is large,clusters are densely distributed in work g(n,a,B,,ru-p.)for the cluster-sparse state,the crit- O and might intersect with each other.The member density d is small,and hence this is also called the member-sparse ical transmission range is where< state.Therefore,different with previous state,members in a 1,a+28<0,0<Y≤1. same cluster tends to be move more independently,since the In the following,we will first show the necessary condition of Proposition 1,and then show its sufficient condition.As range of each cluster are large.If regarding cluster members discussed in Section III,cluster members in this state stay as independent nodes,the correlated mobility model will de- generate into the i.i.d model.Thus,the network contains n very close with each other and the cluster size is small. Therefore,we regard each cluster as a whole and consider independent nodes,each of which has a critical transmission range re.Using the existing results,we have cluster connectivity here. (C3).Cluster-inferior dense state (0<a+28<). We have rp.=(at2a)logn,where 0<10< A.Necessary Condition of Proposition I y≤1. Denote Peas(n,a,B,y,rtp.)as the probability that In this state,we have0≤a+2B<.andπR2=w(是).t G(n,a,B,y,r-p)has some clusters disconnected.We is the transitional state between the cluster-sparse and cluster- will prove the necessary condition by showing that dense state.We can neither regard cluster members as a whole Pess (n,a,B,rp)is strictly larger than zero. nor as independent nodes.Instead,we group nodes into sub- 1)Investigation of Cluster Connectivity:Denote P(Fj)as clusters.Each cluster is divided into n(+2)sub-clusters the probability that cluster C;is disconnected in all k timeslots. and we regard each sub-cluster as a whole,which can be Then we have the following lemma. seen as independent over different sub-clusters.Thus,there Lemma 1:Yj=1,2,...,m,P(Fi)is bounded by are totally mnk(+28)sub-clusters and we have re-p.= kn Vsm-√a++ （1-πr+R)2）≤P()≤(1-(r-R)2 (4-1) kxna T机a Furthermore,we study the scenario where all the three kinds of clusters co-exist in the network.Different with wherer()and R-0(n). previous scenarios where the number of nodes and radius are Proof:Due tor).we have(R). assumed to be the same for each cluster,we let the radius and To bound P(F),we first bound the cluster disconnection4 gap between our correlated and clustered mobility with the i.i.d mobility. The main intuition is to divide clusters into “independent” groups which can be virtually regarded as a representative node. Investigating the cluster-mixed state in Theorem 1 directly would be challenging. Therefore, in the analysis, we will first study the case that every cluster has a same number of members and a same radius. Depending on the relationship between average coverage of access points, 1 nα , and the cluster region πR2 = Θ(n 2β ), we will have different divisions. As three special and main cases of Theorem 1, i.e., cluster-dense, cluster-sparse, and cluster-interior dense states, their results and intuitions are presented as follows, from (C1) to (C3). (C1). Cluster-sparse state (α + 2β < 0). We have r w.p. c = Èγ log n kπnα , where 0 < α ≤ 1, 0 < γ ≤ 1. In this state, we have α + 2β < 0 and πR2 = o( 1 nα ). The cluster size is relatively small compared to the average cover￾age of each access point and clusters are sparsely distributed in O. On the other hand, the member density of each cluster d = ϖ πR2 = Θ(n 1−2β−γ ) is large, which means the cluster members stay very close in their belonging clusters. Therefore, each cluster can be virtually regarded as a whole or even as one representative node and the critical transmission range for this representative node is r w.p. c (R will be shown to be very small compared with r w.p. c ). Then, the unit square O consists of m representative nodes. Recall that the home point of each cluster moves independently. Therefore, using the result for i.i.d model in [20], we have r w.p. c = Èlog m kπnα = Èγ log n kπnα . (C2). Cluster-dense state (α + 2β ≥ ϵ k ). We have r w.p. c = È log n kπnα , where 0 < α ≤ 1. In this state, we have α + 2β ≥ ϵ k and πR2 = ω( 1 nα ). The cluster size is large, clusters are densely distributed in O and might intersect with each other. The member density d is small, and hence this is also called the member-sparse state. Therefore, different with previous state, members in a same cluster tends to be move more independently, since the range of each cluster are large. If regarding cluster members as independent nodes, the correlated mobility model will de￾generate into the i.i.d model. Thus, the network O contains n independent nodes, each of which has a critical transmission range rc. Using the existing results, we have r w.p. c = È log n kπnα . (C3). Cluster-inferior dense state (0 ≤ α + 2β < ϵ k ). We have r w.p. c = È[k(α+2β)+γ] log n kπnα , where 0 < α ≤ 1, 0 < γ ≤ 1. In this state, we have 0 ≤ α+2β < ϵ k and πR2 = ω( 1 nα ). It is the transitional state between the cluster-sparse and cluster￾dense state. We can neither regard cluster members as a whole nor as independent nodes. Instead, we group nodes into sub￾clusters. Each cluster is divided into n k(α+2β) sub-clusters and we regard each sub-cluster as a whole, which can be seen as independent over different sub-clusters. Thus, there are totally mnk(α+2β) sub-clusters and we have r w.p. È c = log(mnk(α+2β)) kπnα = È[k(α+2β)+γ] log n kπnα . Furthermore, we study the scenario where all the three kinds of clusters co-exist in the network. Different with previous scenarios where the number of nodes and radius are assumed to be the same for each cluster, we let the radius and number of nodes in each cluster can differ from each other in cluster mixed situation. The network is therefore denoted as G(n, α, {βi}, {ϖi}, γ, rw.p. c ), in which there are n γ clusters. The ith cluster has ϖi = n ϵi members and a radius of n βi , where i = 1, 2, ..., nγ . (C4). Cluster-mixed state (w.p.). This state is a generalization of the above three separate states and can generalize previous results. We rewrite m¯ to be m¯ = mP1 i=1 1 + mP2 i=1 n α+2βi + mP3 i=1 ϖi , which means that we regard the cluster as a whole for those in cluster-sparse state, regard sub-clusters as a group for clusters in cluster-inferior dense state, and regard members as separate nodes for clusters in cluster dense state. In other word, m¯ denotes the number of “independent” node groups in the network. Therefore, we have r w.p. c = Èlog ¯m kπnα . (C5). Cluster-mixed state (a.s.). We have r a.s. c = È2 log ¯m kπnα , where m¯ = m1+ mP2 i=1 n k(α+2βi)+ mP3 i=1 ϖi . This state requires a stronger network connectivity, i.e., almost surely connectivity. Since cluster mixed state can generalize the three separate states, we will only prove the a.s. connectivity in mixed situation. We show that the price from w.p. to a.s. is a factor of √ 2, i.e., r a.s. c = √ 2r w.p. c . IV. CRITICAL TRANSMISSION RANGE FOR CLUSTER-SPARSE STATE As a special case of Theorem 1, we first investigate the case for critical transmission range in cluster-sparse state. Proposition 1: In a correlated mobile k-hop clustered net￾work G(n, α, β, γ, rw.p. c ) for the cluster-sparse state, the crit￾ical transmission range is r w.p. c = Èγ log n kπnα , where 0 < α ≤ 1, α + 2β < 0, 0 < γ ≤ 1. In the following, we will first show the necessary condition of Proposition 1, and then show its sufficient condition. As discussed in Section III, cluster members in this state stay very close with each other and the cluster size is small. Therefore, we regard each cluster as a whole and consider cluster connectivity here. A. Necessary Condition of Proposition 1 Denote Pcss(n, α, β, γ, rw.p. c ) as the probability that G(n, α, β, γ, rw.p. c ) has some clusters disconnected. We will prove the necessary condition by showing that Pcss(n, α, β, γ, rw.p. c ) is strictly larger than zero. 1) Investigation of Cluster Connectivity: Denote P(Fj ) as the probability that cluster Cj is disconnected in all k timeslots. Then we have the following lemma. Lemma 1: ∀j = 1, 2, . . . , m, P(Fj ) is bounded by  1 − π(r + R) 2 knα ≤ P(Fj ) ≤  1 − π(r − R) 2 knα (4-1) where r = Θ€Èγ log n kπnα Š and R = Θ(n β ). Proof: Due to r = Θ€Èγ log n kπnα Š , we have r = ω(R). To bound P(Fj ), we first bound the cluster disconnection