Notation Definition has full connectivity.In this definition,g(n,a,B,can be na The number of access points. degenerated into g(n,a,y)because we regard each cluster as a The access point exponent,0<a<1. an entirety. m The number of clusters,m =nY. Note that both definitions require all nodes to be connected Y The cluster exponent,0<y<1. to the access points in k timeslots,and thus are equivalent 切 The number of cluster members for each cluster.They will be adopted for different cluster scalability states to The cluster member exponent for each cluster, simplify the analysis. 0≤e<1.1 R The radius of each cluster,R=(n5) D.Definition of Critical Transmission Range 8 The cluster radius exponent,B<0. During a time slot A,each cluster-member node would The member density of a cluster,d=(R2).attempt to connect to an access point with a common radius C The jth cluster (j=1,2,...,m). r,which is also called the transmission range for each cluster 2h The hth access point (h =1,2,...,n). member.Let Mn denote the event that all cluster-member Hi The home point of cluster Cj. nodes are connected in a given period A(A {1,2,...,}) H分 The position of Hj during time slot A. and let PA(Mn)be the corresponding probability.Then,for The kth cluster member in C;during A.It is cluster-member connectivity,the critical transmission range also used to denote the position of during rp and ras.are defined as follows.The definitions for A if there is no ambiguity (=1,2,...,). cluster connectivity are similar. F The event that Ci is disconnected in k slots.2 Definition 1:For a correlated mobile k-hop clustered net- The event that is disconnected during A. work g(n,a,B,)r-v.is the critical transmission range The event that all are disconnected.3 with which g(n,a,B,will be connected with probability 1 We have= nn for the three separate states. lim PA(Mn)=1,if r z crt p.,c>1; 2 This means that during k time slots at least one cluster member in Ci is disconnected to any access point. lim PA(Mn)<1,if r c'r-p.,c<1. 3This is fora specific cluster memberduring alltime slots For the eventM will hold with probability 1. TABLE 2.1:Important Notations. However,given any sufficient large n,there may exists infinite number of N >n.such that My will fail.To avoid this case. we further introduce the connectivity for almost surely. Specifically,at the beginning of each time slot,every home Definition 2:For a correlated mobile k-hop clustered net- point will uniformly and independently choose a position with- work g(n,o,B,)r is the critical transmission range with in the unit torus O.Then each cluster member will uniformly which g(n,a,B,will be connected almost surely if and independently choose its location in the corresponding P(lim∩nMk)=1,ifr≥cr8,c>1: cluster region.In the rest of the time slot,home points and P(im∩2nMk)<1,ifr≤r.,c<1 cluster members will remain stationary 2子风 III.MAIN RESULTS AND INTUITIONS C.Connectivity Definition In this section,we summarize the main results and We present two equivalent definitions for connectivity,i.e., present the intuitions behind.Denote the network as cluster-member connectivity and cluster connectivity. g(n,,i},rep),in which there are ny clusters. We first define cluster-member connectivity.A cluster mem- The i-th cluster has wi=nf members and a radius of n ber is connected if it can reach an access point within k where i=1,2,...,n7.Since in this model,each cluster can slots and disconnected otherwise.If all cluster members can have different radius and different member number,we call it be connected within k slots,the network is said to have cluster-mixed state (w.p.). full connectivity.Let g(n,o,B,y)denote the initial graph Theorem 1:In a correlated mobile k-hop clustered network (clustered network).During each time slot A(A=1,2,...,k), G(n,a,Bil,i),,rp)for the cluster-mixed state (w.p.). an edge eij will be added between a cluster member i and an the critical transmission range is mm access point j into g(n,a.B.y)if their Euclidean distance is 3 less than r,where r is the critical transmission range.And, nk(+2)+where m is the number of clusters 1 G(n,a,B,has full connectivity if and only if every cluster- satisfying B,≤-号，m2 is the number of clusters satisfying member node can be connected to one access point directly -号<B:≤-号+靠，and m3 is the number of clusters during k time slots.According to our definition,multihop satisfying B,≥-号+条. transmission is not allowed. Note that our model allows cluster scalability and also The other is the cluster connectivity.A cluster is connected correlated mobility,which exhibit significantly difference with if all the cluster-member nodes within it are connected (they existing work [20]where n nodes move independently in may connect to different access points),while a cluster is the network.However,an "independent"property will be disconnected if at least one cluster member is disconnected.greatly preferred in the analysis and understanding on our If all clusters are connected within k time slots,the network problem.Our main effort is therefore devoted to bridge the3 Notation Definition n α The number of access points. α The access point exponent, 0 < α ≤ 1. m The number of clusters, m = n γ . γ The cluster exponent, 0 < γ ≤ 1. ϖ The number of cluster members for each cluster.1 ϵ The cluster member exponent for each cluster, 0 ≤ ϵ < 1. 1 R The radius of each cluster, R = Θ(n β ). β The cluster radius exponent, β ≤ 0. d The member density of a cluster, d = ϖ/(πR2 ). Cj The jth cluster (j = 1, 2, . . . , m). Qh The hth access point (h = 1, 2, . . . , nα). Hj The home point of cluster Cj . Hλ j The position of Hj during time slot λ. ψ λ jκ The κth cluster member in Cj during λ. It is also used to denote the position of ψ λ jκ during λ if there is no ambiguity (κ = 1, 2, . . . , ϖ). Fj The event that Cj is disconnected in k slots.2 f λ jκ The event that ψ λ jκ is disconnected during λ. fjκ The event that all ψ λ jκ are disconnected.3 1 We have ϖ = n m = n 1−γ = n ϵ for the three separate states. 2 This means that during k time slots at least one cluster member in Cj is disconnected to any access point. 3 This is for a specific cluster member ψ λ jκ during all k time slots. TABLE 2.1: Important Notations. Specifically, at the beginning of each time slot, every home point will uniformly and independently choose a position with￾in the unit torus O. Then each cluster member will uniformly and independently choose its location in the corresponding cluster region. In the rest of the time slot, home points and cluster members will remain stationary. C. Connectivity Definition We present two equivalent definitions for connectivity, i.e., cluster-member connectivity and cluster connectivity. We first define cluster-member connectivity. A cluster mem￾ber is connected if it can reach an access point within k slots and disconnected otherwise. If all cluster members can be connected within k slots, the network is said to have full connectivity. Let G(n, α, β, γ) denote the initial graph (clustered network). During each time slot λ (λ = 1, 2, . . . , k), an edge eij will be added between a cluster member i and an access point j into G(n, α, β, γ) if their Euclidean distance is less than r, where r is the critical transmission range. And, G(n, α, β, γ) has full connectivity if and only if every cluster￾member node can be connected to one access point directly during k time slots. According to our definition, multihop transmission is not allowed. The other is the cluster connectivity. A cluster is connected if all the cluster-member nodes within it are connected (they may connect to different access points), while a cluster is disconnected if at least one cluster member is disconnected. If all clusters are connected within k time slots, the network has full connectivity. In this definition, G(n, α, β, γ) can be degenerated into G(n, α, γ) because we regard each cluster as an entirety. Note that both definitions require all nodes to be connected to the access points in k timeslots, and thus are equivalent. They will be adopted for different cluster scalability states to simplify the analysis. D. Definition of Critical Transmission Range During a time slot λ, each cluster-member node would attempt to connect to an access point with a common radius r, which is also called the transmission range for each cluster member. Let Mn denote the event that all cluster-member nodes are connected in a given period Λ(Λ ⊆ {1, 2, . . . , k}) and let P Λ(Mn) be the corresponding probability. Then, for cluster-member connectivity, the critical transmission range r w.p. c and r a.s. c are defined as follows. The definitions for cluster connectivity are similar. Definition 1: For a correlated mobile k-hop clustered net￾work G(n, α, β, γ), r w.p. c is the critical transmission range with which G(n, α, β, γ) will be connected with probability if limn→∞ P Λ(Mn) = 1, if r ≥ crw.p. c , c > 1; limn→∞ P Λ(Mn) < 1, if r ≤ c ′ r w.p. c , c ′ < 1. For r w.p. c , the event Mn will hold with probability 1. However, given any sufficient large n, there may exists infinite number of N > n, such that MN will fail. To avoid this case, we further introduce the connectivity for almost surely. Definition 2: For a correlated mobile k-hop clustered net￾work G(n, α, β, γ), r a.s. c is the critical transmission range with which G(n, α, β, γ) will be connected almost surely if P Λ( limn→∞ T∞ k=n Mk) = 1, if r ≥ cra.s. c , c > 1; P Λ( limn→∞ T∞ k=n Mk) < 1, if r ≤ c ′ r a.s. c , c ′ < 1. III. MAIN RESULTS AND INTUITIONS In this section, we summarize the main results and present the intuitions behind. Denote the network as G(n, α, {βi}, {ϖi}, γ, rw.p. c ), in which there are n γ clusters. The i-th cluster has ϖi = n ϵi members and a radius of n βi , where i = 1, 2, ..., nγ . Since in this model, each cluster can have different radius and different member number, we call it cluster-mixed state (w.p.). Theorem 1: In a correlated mobile k-hop clustered network G(n, α, {βi}, {ϖi}, γ, rw.p. c ) for the cluster-mixed state (w.p.), the critical transmission range is r w.p. c = Èlog ¯m kπnα , m¯ = m1+ mP2 i=1 n k(α+2βi) + mP3 i=1 ϖi , where m1 is the number of clusters satisfying βi ≤ −α 2 , m2 is the number of clusters satisfying − α 2 < βi ≤ −α 2 + ϵi 2k , and m3 is the number of clusters satisfying βi ≥ −α 2 + ϵi 2k . Note that our model allows cluster scalability and also correlated mobility, which exhibit significantly difference with existing work [20] where n nodes move independently in the network. However, an “independent” property will be greatly preferred in the analysis and understanding on our problem. Our main effort is therefore devoted to bridge the