Connectivity Analysis in Wireless Networks with Correlated Mobility and Cluster Scalability

Connectivity Analysis in Wireless Networks with Correlated Mobility and Cluster Scalability Jinbei Zhang,Luoyi Fu,Qi Wang,Liang Liu,Xinyu Wang,Xinbing Wang Abstract-Since it was found that real mobility processes needed to achieve full connectivity in a multi-hop fashion in exhibit significant degree of correlation (correlated mobility)and the networks with n randomly and independently distributed nodes are often heterogeneously distributed in clustered networks nodes.In [5],Wan et al.also investigated the number of (cluster scalability),there has been a great interest in studying their impact on network performance,such as throughput and neighbors needed to ensure connectivity. delay.However,limited works have been done to investigate their Sector-based strategy:This strategy was discussed in [6]and impact jointly,which may due to the challenges in capturing both related to the 0-coverage problem.In [7].Xue et al.proved features under a unified network model.In this paper,we focus that the exact threshold function for 0-coverage is logfor on their impact on asymptotic connectivity and propose correlated any E(0,2),and -coverage w.h.p.(with high probability) mobile k-hop clustered network model.Two connectivity metrics are considered.One is network connectivity with probability (w.p.). implies overall connectivity with high probability. The other is connectivity almost surely (a.s.),which requires a Distance-based strategy:For G(V,E)and any two nodes stronger condition than connectivity with probability. i,jV,ei EE if and only if the Euclidean distance between With mobility correlation and cluster scalability vary,we show i and j is at most r.The critical value of r for the overall that there are three distinct states for network connectivity, connectivity when the number of nodes n goes to infinity is i.e.,cluster-sparse,cluster-dense state and cluster-inferior dense state,respectively.We first prove the exact value of the critical studied and this is also the main metric in this paper.In [8], transmission range for each state respectively and then further Gupta and Kumar proved that the transmission power level generalize the three states into a unified one,which we call it covering an area of can ensure the asymptot- cluster mixed state.The critical transmission range for connec- ical connectivity of the overall network with probability one if tivity almost surely is v2 times the range for connectivity with and only if c(n)+o0.In [5],Wan et al.obtained the critical probability.Our main contribution lies in how to group correlated nodes into independent ones in various settings,and reveals the transmission radius for k-connectivity in an ad hoc network interrelated relationship between correlated mobility and cluster whose nodes are uniformly and independently placed. scalability through state transitions. Most of the existing studies consider these three strategies in non-clustered (fat)networks.On the other hand,according I.INTRODUCTION to whether the nodes can move or not,previous works can Connectivity performance is a fundamental concern in also be generally classified into two categories. designing and implementing wireless networks,and is of Stationary flat networks:In such networks,all nodes are paramount significance.To achieve the connectivity,nodes randomly and independently distributed in a region and keep in the network will adjust their transmission power to their stationary.Nodes can connect to each other through multihop neighbors.Since the initial works of [2]and [3],there has been fashion.In [9].Santi et al.investigated the range assignment a great interest in the scaling analysis of network performance problem for stationary networks and provided tight upper and many works have been done to explore the asymptotic and lower bounds on the critical transmitting range for one- connectivity of wireless networks.Three main strategies pro- dimensional networks and non-tight bounds for two and three- posed in recent literatures are: dimensional networks.In [10],Nassab et al.considered the Number-of-neighbor-based strategy:In this strategy,for a case where the number of nodes changes with time under graph G(V,E)and any two nodes i,j V,ej E if a stationary distribution and computed the exact probability and only if node j is among node i's o nearest neighbors. of connectivity in discrete and continuous ad hoc networks In [4].Xue et al.proved that e(log n)'nearest neighbors are In [8],Gupta et al.studied the connectivity in flat stationary networks from the perspective of critical power. Part of this work was reported in the Proceedings of ACM Sigmetrics 2014 Mobile flat networks:Mobility has been found to increase (poster)[1]. The authors are with Dept.of Electronic Engineering,Shanghai Jiao Tong the connectivity [11]in ad hoc networks.In mobile net- University,China.Jinbei is also with The State Key Laboratory of Integrated works,nodes can reach others during their movement.In Services Networks,Xidian University,China.Email:fabelchina,yiluofu, [12].Bettstetter et al.demonstrated a lower bound on the fwq911206,liuliang582,maiamibangqiu,xwang8@sjtu.edu.cn. IThe following asymptotic notations are used in this paper.Given non- critical transmitting range through numerical integration.In negative functions f(n)>0 and g(n)>0: [9,Santi et al.considered the mobile version of the range (1)f(n)=o(g(n))means lim0. 了《1) assignment problem and showed the achieved energy saving by (2)f(n)=w(g(n))is equivalent to g(n)=o(f(n)). simulations.Santi further investigated the impact of bounded (3)f(n)=(g(n))means lim sup. and obstacle free mobility on the critical transmitting range (4)f(n)=e(g(n))means f(n)=O(g(n)),g(n)=O(f(n)). for connectivity in MANETs in [13].In a recent work,Wang (5)f(n)=(g(n))is equivalent to g(n)=O(f(n)). et al.[20]investigate the k-connectivity in wireless networks

1 Connectivity Analysis in Wireless Networks with Correlated Mobility and Cluster Scalability Jinbei Zhang, Luoyi Fu, Qi Wang, Liang Liu, Xinyu Wang, Xinbing Wang Abstract—Since it was found that real mobility processes exhibit significant degree of correlation (correlated mobility) and nodes are often heterogeneously distributed in clustered networks (cluster scalability), there has been a great interest in studying their impact on network performance, such as throughput and delay. However, limited works have been done to investigate their impact jointly, which may due to the challenges in capturing both features under a unified network model. In this paper, we focus on their impact on asymptotic connectivity and propose correlated mobile k-hop clustered network model. Two connectivity metrics are considered. One is network connectivity with probability (w.p.). The other is connectivity almost surely (a.s.), which requires a stronger condition than connectivity with probability. With mobility correlation and cluster scalability vary, we show that there are three distinct states for network connectivity, i.e., cluster-sparse, cluster-dense state and cluster-inferior dense state, respectively. We first prove the exact value of the critical transmission range for each state respectively and then further generalize the three states into a unified one, which we call it cluster mixed state. The critical transmission range for connec￾tivity almost surely is √ 2 times the range for connectivity with probability. Our main contribution lies in how to group correlated nodes into independent ones in various settings, and reveals the interrelated relationship between correlated mobility and cluster scalability through state transitions. I. INTRODUCTION Connectivity performance is a fundamental concern in designing and implementing wireless networks, and is of paramount significance. To achieve the connectivity, nodes in the network will adjust their transmission power to their neighbors. Since the initial works of [2] and [3], there has been a great interest in the scaling analysis of network performance and many works have been done to explore the asymptotic connectivity of wireless networks. Three main strategies pro￾posed in recent literatures are: Number-of-neighbor-based strategy: In this strategy, for a graph G(V, E) and any two nodes i, j ∈ V , eij ∈ E if and only if node j is among node i’s ϕ nearest neighbors. In [4], Xue et al. proved that Θ(log n) 1 nearest neighbors are Part of this work was reported in the Proceedings of ACM Sigmetrics 2014 (poster) [1]. The authors are with Dept. of Electronic Engineering, Shanghai Jiao Tong University, China. Jinbei is also with The State Key Laboratory of Integrated Services Networks, Xidian University, China. Email: {abelchina, yiluofu, fwq911206, liuliang582, maiamibangqiu, xwang8}@sjtu.edu.cn. 1The following asymptotic notations are used in this paper. Given non￾negative functions f(n) > 0 and g(n) > 0: (1) f(n) = o(g(n)) means lim n→∞ f(n) g(n) = 0. (2) f(n) = ω(g(n)) is equivalent to g(n) = o(f(n)). (3) f(n) = O ￾ g(n)
means lim n→∞ sup f(n) g(n) < ∞. (4) f(n) = Θ￾ g(n)
means f(n) = O(g(n)), g(n) = O(f(n)). (5) f(n) = Ω￾ g(n)
is equivalent to g(n) = O(f(n)). needed to achieve full connectivity in a multi-hop fashion in the networks with n randomly and independently distributed nodes. In [5], Wan et al. also investigated the number of neighbors needed to ensure connectivity. Sector-based strategy: This strategy was discussed in [6] and related to the θ-coverage problem. In [7], Xue et al. proved that the exact threshold function for θ-coverage is log 2π 2π−θ for any θ ∈ (0, 2π), and π-coverage w.h.p. (with high probability) implies overall connectivity with high probability. Distance-based strategy: For G(V, E) and any two nodes i, j ∈ V , eij ∈ E if and only if the Euclidean distance between i and j is at most r. The critical value of r for the overall connectivity when the number of nodes n goes to infinity is studied and this is also the main metric in this paper. In [8], Gupta and Kumar proved that the transmission power level covering an area of πr2 = log n+c(n) n can ensure the asymptot￾ical connectivity of the overall network with probability one if and only if c(n) → +∞. In [5], Wan et al. obtained the critical transmission radius for k-connectivity in an ad hoc network whose nodes are uniformly and independently placed. Most of the existing studies consider these three strategies in non-clustered (flat) networks. On the other hand, according to whether the nodes can move or not, previous works can also be generally classified into two categories. Stationary flat networks: In such networks, all nodes are randomly and independently distributed in a region and keep stationary. Nodes can connect to each other through multihop fashion. In [9], Santi et al. investigated the range assignment problem for stationary networks and provided tight upper and lower bounds on the critical transmitting range for one￾dimensional networks and non-tight bounds for two and three￾dimensional networks. In [10], Nassab et al. considered the case where the number of nodes changes with time under a stationary distribution and computed the exact probability of connectivity in discrete and continuous ad hoc networks. In [8], Gupta et al. studied the connectivity in flat stationary networks from the perspective of critical power. Mobile flat networks: Mobility has been found to increase the connectivity [11] in ad hoc networks. In mobile net￾works, nodes can reach others during their movement. In [12], Bettstetter et al. demonstrated a lower bound on the critical transmitting range through numerical integration. In [9], Santi et al. considered the mobile version of the range assignment problem and showed the achieved energy saving by simulations. Santi further investigated the impact of bounded and obstacle free mobility on the critical transmitting range for connectivity in MANETs in [13]. In a recent work, Wang et al. [20] investigate the k-connectivity in wireless networks

3 where n nodes are independently and randomly mobile in the and also mixed state when n->oo,under the condition of network and there are na access points.It is shown that the with probability convergence,and the condition of almost critical transmission range isr(n)for a node to surely convergence. reach an access point in k time slots. In this paper,we find that nodes in a cluster can be However,flat networks have poor scalability [14][15]and regarded as independent nodes or grouped into indepen- poor energy efficiency [16].On the contrast,clustering was dent sub-clusters.or the cluster can be even seen as a found to improve various aspects of network performance whole node,depending on the parameter settings.Our [17][18][19].In [17],Kozat et al.proved that the capacity results are general and can shed lights on how to evaluate of random ad hoc networks could be greatly improved and connectivity in various correlated clustered networks. the capacity gain was when the number of ad The rest of this paper is organized as follows.In Section II, hoc nodes per access point is bounded as e(1).Other works we introduce our correlated mobile k-hop clustered networks on clustered or infrastructure-based networks concentrating on model,on which the later analysis bases.In Section III,we capacity include [18][19].However,little efforts are devoted present our main results and intuitions.The critical transmis- to the analysis of connectivity in clustered networks.It was sion ranges for cluster sparse state,cluster dense state and found that real mobility processes exhibit significant degree cluster inferior-dense state are analyzed in Sections IV,V and of correlation and incur heterogeneity nodes'distribution VI,respectively.In Section VII,we generalize the results for (clustering)[21]-[25].Furthermore,since mobility,especially the three separate states and prove the critical transmission correlated mobility,and node spatial heterogeneity (cluster range for cluster-mixed state (w.p.).In Section VIIl,we prove scalability)2 has been found to be able to improve the network the result in cluster-mixed state under the condition of almost throughput [11][26][27],we are thus of great interests surely convergence.In section IX,we conduct some discussion in studying the impact of correlated mobility and cluster on our results.Finally,in Section X,we conclude this paper. scalability on connectivity in mobile k-hop clustered networks. Specifically,we adopt the correlated mobility model in [26] II.CORRELATED MOBILE K-HOP CLUSTERED NETWORK to implement the group mobility,and suppose that there are MODEL na(0<a 1)access points and n7(0<y<1)clusters, In the network.there are n nodes and na access points. each has n(0<e<1)nodes and a cluster radius of R= where a is the access point exponent and 0<a<1.The e(n)(B<0)in the whole network which is assumed to network is assumed to be a unit torus to avoid border effects. be a unit torus.The cluster radius can scale with the number Access points are uniformly and independently distributed in of nodes n,and with different values of B we can implement 0 the cluster scalability.We try to present a general investigation on their impact in this paper: A.Cluster Scalability What is the impact of correlated mobility and cluster To model the network clusters,we assume nodes are scalability on connectivity in correlated mobile k-hop grouped into m clusters,where m n7 and 0<<1 clustered networks when the number of nodes n-oo? is the cluster exponent.Thus each cluster is composed of What are the impact of the factors a,B.y and e on correlated mobility,cluster scalability and network con- 可=是=nl-y=ncluster members,.where is the cluster member exponent and 0 e<1.Every cluster is nectivity performance? centered around a logical center(home point)and has a radius With different values of o,B and e,we find that the network R=(n5),where B <0 is the cluster radius exponent. states can be divided into three categories,i.e.,the cluster- Home points are uniformly and independently distributed in sparse state (a+28<0),cluster-dense state (a+28 >and O.Cluster-member nodes are randomly distributed in their cluster-inferior dense state (0<a+28<).We prove the belonging cluster regions,each of which is with a circular critical transmission range for these three separate states to be area of R2.Some important notations are listed in Table 2.1. logn,V Vg&and (a+2 og亚，respectively..After As we can see.the cluster can scale with n.When B is 程T机9 that,we prove the critical transmission range for a generalized small,the cluster size will be small and clusters are sparsely scenario,the cluster-mixed state,both for w.p.connectivity and distributed in O.When B is large,the cluster region will a.s.connectivity.Finally,we discuss the results and present the become relatively large,which leads to overlapped distributed underlying insights obtained. clusters.Note that this cluster scalability also leads to node The major contributions of this paper are listed as follows: distribution heterogeneity. We employ correlated mobility to illustrate the clustering of the nodes and correlated node movements in clustered B.Correlated Mobility networks,and further propose the correlated mobile k- To model the network mobility,we assume that access hop clustered model for network connectivity. points are stationary and the cluster members are mobile. We implement cluster scalability and derive the exact The position of a cluster member is determined by both the critical transmission range for the three separate states movement of its belonging cluster and its relative motion within the cluster region.Therefore,the mobility of cluster 2Note that in clustered networks,the spatial node heterogeneity can be achieved by controlling the cluster scales,i.e..we can achieve spatial members in the same cluster are correlated and we call this heterogeneity via cluster scalability. mobility model as the correlated mobility model

2 where n nodes are independently and randomly mobile in the network and there are n α access points. It is shown that the critical transmission range is r(n) = È log n kπnα for a node to reach an access point in k time slots. However, flat networks have poor scalability [14] [15] and poor energy efficiency [16]. On the contrast, clustering was found to improve various aspects of network performance [17] [18] [19]. In [17], Kozat et al. proved that the capacity of random ad hoc networks could be greatly improved and the capacity gain was Θ €È n log n Š when the number of ad hoc nodes per access point is bounded as Θ(1). Other works on clustered or infrastructure-based networks concentrating on capacity include [18] [19]. However, little efforts are devoted to the analysis of connectivity in clustered networks. It was found that real mobility processes exhibit significant degree of correlation and incur heterogeneity nodes’ distribution (clustering) [21]–[25]. Furthermore, since mobility, especially correlated mobility, and node spatial heterogeneity (cluster scalability) 2 has been found to be able to improve the network throughput [11] [26] [27], we are thus of great interests in studying the impact of correlated mobility and cluster scalability on connectivity in mobile k-hop clustered networks. Specifically, we adopt the correlated mobility model in [26] to implement the group mobility, and suppose that there are n α(0 < α ≤ 1) access points and n γ (0 < γ ≤ 1) clusters, each has n ϵ (0 ≤ ϵ < 1) nodes and a cluster radius of R = Θ(n β )(β ≤ 0) in the whole network O which is assumed to be a unit torus. The cluster radius can scale with the number of nodes n, and with different values of β we can implement the cluster scalability. We try to present a general investigation on their impact in this paper: • What is the impact of correlated mobility and cluster scalability on connectivity in correlated mobile k-hop clustered networks when the number of nodes n → ∞? • What are the impact of the factors α, β, γ and ϵ on correlated mobility, cluster scalability and network con￾nectivity performance? With different values of α, β and ϵ, we find that the network states can be divided into three categories, i.e., the cluster￾sparse state (α+2β < 0), cluster-dense state (α+2β ≥ ϵ k ) and cluster-inferior dense state (0 ≤ α + 2β < ϵ k ). We prove the critical transmission range for these three separate states to be Èγ log n kπnα , È log n kπnα and È[k(α+2β)+γ] log n kπnα , respectively. After that, we prove the critical transmission range for a generalized scenario, the cluster-mixed state, both for w.p. connectivity and a.s. connectivity. Finally, we discuss the results and present the underlying insights obtained. The major contributions of this paper are listed as follows: • We employ correlated mobility to illustrate the clustering of the nodes and correlated node movements in clustered networks, and further propose the correlated mobile k￾hop clustered model for network connectivity. • We implement cluster scalability and derive the exact critical transmission range for the three separate states 2Note that in clustered networks, the spatial node heterogeneity can be achieved by controlling the cluster scales, i.e., we can achieve spatial heterogeneity via cluster scalability. and also mixed state when n → ∞, under the condition of with probability convergence, and the condition of almost surely convergence. • In this paper, we find that nodes in a cluster can be regarded as independent nodes or grouped into indepen￾dent sub-clusters, or the cluster can be even seen as a whole node, depending on the parameter settings. Our results are general and can shed lights on how to evaluate connectivity in various correlated clustered networks. The rest of this paper is organized as follows. In Section II, we introduce our correlated mobile k-hop clustered networks model, on which the later analysis bases. In Section III, we present our main results and intuitions. The critical transmis￾sion ranges for cluster sparse state, cluster dense state and cluster inferior-dense state are analyzed in Sections IV, V and VI, respectively. In Section VII, we generalize the results for the three separate states and prove the critical transmission range for cluster-mixed state (w.p.). In Section VIII, we prove the result in cluster-mixed state under the condition of almost surely convergence. In section IX, we conduct some discussion on our results. Finally, in Section X, we conclude this paper. II. CORRELATED MOBILE K-HOP CLUSTERED NETWORK MODEL In the network, there are n nodes and n α access points, where α is the access point exponent and 0 < α ≤ 1. The network is assumed to be a unit torus O to avoid border effects. Access points are uniformly and independently distributed in O. A. Cluster Scalability To model the network clusters, we assume nodes are grouped into m clusters, where m = n γ and 0 < γ ≤ 1 is the cluster exponent. Thus each cluster is composed of ϖ = n m = n 1−γ = n ϵ cluster members, where ϵ is the cluster member exponent and 0 ≤ ϵ < 1. Every cluster is centered around a logical center (home point) and has a radius R = Θ(n β ), where β ≤ 0 is the cluster radius exponent. Home points are uniformly and independently distributed in O. Cluster-member nodes are randomly distributed in their belonging cluster regions, each of which is with a circular area of πR2 . Some important notations are listed in Table 2.1. As we can see, the cluster can scale with n. When β is small, the cluster size will be small and clusters are sparsely distributed in O. When β is large, the cluster region will become relatively large, which leads to overlapped distributed clusters. Note that this cluster scalability also leads to node distribution heterogeneity. B. Correlated Mobility To model the network mobility, we assume that access points are stationary and the cluster members are mobile. The position of a cluster member is determined by both the movement of its belonging cluster and its relative motion within the cluster region. Therefore, the mobility of cluster members in the same cluster are correlated and we call this mobility model as the correlated mobility model

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 the

3 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

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 disconnection

4 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

probability P(D)for a given cluster C;and a given access minimum distance between any point outside T and inside point Oh in timeslot A.Then extend the analysis to na access C;is larger than r.Therefore,we obtain points during k time slots which is exactly P(F). The related positions of Hi and Oh at one timeslot A are P(T)≥1-S()=1-x(r+R)2, (4-4) illustrated in Figure 4.1.As in Figure 4.1(a),we denote the region centered around Hj with radius (r-R)as A.If where S(T)is the area of Qh∈ThA during入，Cj can connect to Oh no matter where the cluster members are.This is because the distance between Let T denote the event that no cluster member in Cj can any point in and Cj is no larger than r.But if connect to any access point during timeslot A.Then,we have the cluster connectivity to Oh cannot be guaranteed because P)=((T). (4-5) the cluster members may appear in the dead zone shown in Figure 4.1(a).Thus,we have P(D)≤1-P() (4-2) Obviously,we have TF.This is because T is ≤1-π(r-R)2 the sufficient condition of And note thatis not the sufficient condition of T.Because even if C is disconnected, each access point might still cover some cluster members in Ocoverage of h⊙Ci Cj.Hence, P()=((r)≥(PT)” (4-6) ≥(-r+) Therefore,with Egn.(4-3)and Egn.(4-6),we can obtain Lemma 1. ■ dead zone 2)Investigation of the Necessary Condition:Lemma 2 will Fig.4.1:Related positions of Hi and Oh at one timeslot.(a) show that m.P(Fj)is bounded from 0. Left figure.(b)Right figure. Lemma 2:If r=V osm+,a+26<0,<a≤1，fr For the upper bound,we consider the eventsF and D. kana any fixed 0<0<1 and sufficiently large n,we have F is the event that cluster Cj is disconnected during one time slot A.Note that for F,Cj can be covered by several m(-+刚) ≥0e-s (47) access points.D is the event that for any access point,a single access point can not cover Cj.Therefore,it is obvious where r is the transmission range and R-(nB). that FD.And we have Proof:Because ofr==(re).we have P(F)=P(∩F) r=w(R).Taking the logarithm of the left hand side and the λ= power series expansion for log(1-z),we have =(e) log(L.H.S.of Eqn.(47)）】 ≤(eD) (4-3) logm kna log (1-(r +R)2) (48) =(eD)) 2 log m-kn (π+R2） +m) ≤-r-), =1 where o(n)is equal to where the fourth equality is due to the independent distribution of access points and the last inequality follows from(4-2). 6(n)= 、(+R2) For the lower bound,an illustration is shown in the right =3 figure of Fig.4.1.Denote the region centered around Hj with (49) radius(r+R)as ThA.Let ThA denote the event that no cluster a+R) ≤ member in C;can connect to the access point h during 3 timeslot入.During入，Qh∈maybe able to connect to Note that the second inequality is due toπ(r+R)2≤，for some.But if生T入，no can reach it because the all sufficiently large n

5 probability P(Dhλ j ) for a given cluster Cj and a given access point Qh in timeslot λ. Then extend the analysis to n α access points during k time slots which is exactly P(Fj ). The related positions of Hj and Qh at one timeslot λ are illustrated in Figure 4.1. As in Figure 4.1(a), we denote the region centered around Hj with radius (r − R) as J hλ j . If Qh ∈ J hλ j during λ, Cj can connect to Qh no matter where the cluster members are. This is because the distance between any point in J hλ j and Cj is no larger than r. But if Qh ∈ J/ hλ j , the cluster connectivity to Qh cannot be guaranteed because the cluster members may appear in the dead zone shown in Figure 4.1(a). Thus, we have P(D hλ j ) ≤ 1 − P(J hλ j ) ≤ 1 − π(r − R) 2 . (4-2) Fig. 4.1: Related positions of Hj and Qh at one timeslot. (a) Left figure. (b) Right figure. For the upper bound, we consider the events F λ j and Dλ j . F λ j is the event that cluster Cj is disconnected during one time slot λ. Note that for F λ j , Cj can be covered by several access points. Dλ j is the event that for any access point, a single access point can not cover Cj . Therefore, it is obvious that F λ j ⊆ Dλ j . And we have P(Fj ) = P( \ k λ=1 F λ j ) = € P(F λ j ) Šk ≤  P(D λ j ) k = € P(D hλ j ) Šn α k ≤  1 − π(r − R) 2 knα , (4-3) where the fourth equality is due to the independent distribution of access points and the last inequality follows from (4-2). For the lower bound, an illustration is shown in the right figure of Fig. 4.1. Denote the region centered around Hj with radius (r+R) as TÜhλ j . Let T hλ j denote the event that no cluster member in Cj can connect to the access point Qh during timeslot λ. During λ, Qh ∈ TÜhλ j maybe able to connect to some ψ λ jκ. But if Qh ∈/ TÜhλ j , no ψ λ jκ can reach it because the minimum distance between any point outside TÜhλ j and inside Cj is larger than r. Therefore, we obtain P(T hλ j ) ≥ 1 − S(TÜhλ j ) = 1 − π(r + R) 2 , (4-4) where S(TÜhλ j ) is the area of TÜhλ j . Let T λ j denote the event that no cluster member in Cj can connect to any access point during timeslot λ. Then, we have P(T λ j ) = € P(T hλ j ) Šn α . (4-5) Obviously, we have T λ j ⊆ Fλ j . This is because T λ j is the sufficient condition of F λ j . And note that F λ j is not the sufficient condition of T λ j . Because even if Cj is disconnected, each access point might still cover some cluster members in Cj . Hence, P(Fj ) =  P(F λ j ) k ≥  P(T λ j ) k ≥  1 − π(r + R) 2 knα . (4-6) Therefore, with Eqn. (4-3) and Eqn. (4-6), we can obtain Lemma 1. 2) Investigation of the Necessary Condition: Lemma 2 will show that m · P(Fj ) is bounded from 0. Lemma 2: If r = Èγ log n+ξ kπnα , α + 2β < 0, γ k < α ≤ 1, for any fixed 0 < θ < 1 and sufficiently large n, we have m  1 − π(r + R) 2 knα ≥ θe−ξ (4-7) where r is the transmission range and R = Θ(n β ). Proof: Because of r = Èγ log n+ξ kπnα = Θ(rc), we have r = ω(R). Taking the logarithm of the left hand side and the power series expansion for log(1 − x), we have log€ L.H.S. of Eqn.(4-7) Š = log m + knα log € 1 − π(r + R) 2 Š = log m − knα X 2 i=1 € π(r + R) 2 Ši i + δ(n)  , (4-8) where δ(n) is equal to δ(n) =X∞ i=3 € π(r + R) 2 Ši i ≤ € π(r + R) 2 Š2 3 . (4-9) Note that the second inequality is due to π(r + R) 2 ≤ 1 2 , for all sufficiently large n