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 connectivity 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 proposed 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 nonnegative 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 asymptotical 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 onedimensional networks and non-tight bounds for two and threedimensional 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 networks, 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(0and 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 connectivity performance? With different values of α, β and ϵ, we find that the network states can be divided into three categories, i.e., the clustersparse 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 khop 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 independent 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 transmission 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,01; 2 This means that during k time slots at least one cluster member in Ci is disconnected to any access point. lim PA(Mn)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; limn→∞ P Λ(Mn) 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 network 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 coverage 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 degenerate 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 clusterdense state. We can neither regard cluster members as a whole nor as independent nodes. Instead, we group nodes into subclusters. 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 network G(n, α, β, γ, rw.p. c ) for the cluster-sparse state, the critical 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
Substituting (n)andr into Eqn.(4-8).and for all sufficient large n,we further have Then wen bound boud P() log(L.H.S of Eqn.(4-7)) PUF)≤∑PF) 2≥osm-kr(et+P+(xr+P）) ≥1ogm-km(ar+R2+8（a2rjP)） 26-- (414) =-5-kre(n+28)-2vk(n logn+5) ≤me-r(r-R2kna 40(y logn +)2 1 e2cvk(n log n) ekTe(na+28) e-ξ-1 -n(e-1) (4-10) where the second equality is due to Lemma 1. Since a+280,u can be arbitrarily close to Since >0 and a+28 1 such that Eqn.(4-13)holds. 6=e#i0e--m2e-2xkn"(r-R)2 P(fis)=(1-πr2)km =0e-5-e-2e2kr8(na+2a0)+4vKme(n2V√iogn+） The following lemma will show the probability that there exists one cluster member not connected,if we regard each 0e-f-(1+2)e-2 cluster member as independent nodes. (4-12) Lemma4:fr=Va志，a+28≥，00.Note that the fourth any fixed 01), the following equality holds. sa-r2))2osm-an（(am2+8car2) ▣(g心0)=▣U)= =--50ogn+)2 6kna 会-ξ-43 (4-13) (5-3)
6 Substituting δ(n) and r = Èγ log n+ξ kπnα into Eqn. (4-8), and for all sufficient large n, we further have log L.H.S of Eqn. (4-7) ≥log m − knα π(r + R) 2 + 5 6 π(r + R) 2 2 ≥ log m − knα π(r + R) 2 + 5 6 π(2r) 2 2 = − ξ − kπΘ(n α+2β ) − 2 √ kπΘ(n α+2β 2 È γ log n + ξ) − 40(γ log n + ξ) 2 3knα , − ξ − µ1. (4-10) Since α + 2β 0, µ1 can be arbitrarily close to 0 when n is large. Taking the exponent of both sides and let θ = e −µ1 0. Note that the fourth inequality is due to Lemma 1 and the fifth inequality is due to Lemma 2. Recall that θ can be arbitrarily close to 1 and µ2 is arbitrarily close to 0 for sufficient large n, we can obtain Lemma 3. B. Sufficient Condition of Proposition 1 Recall that f λ jκ is the event that cluster member ψ λ jκ is disconnected during λ. Therefore, for the sufficient condition of Proposition 1, it suffices to show that when r = crw.p. c (c > 1), the following equality holds. limn→∞ P [m j=1 [ϖ κ=1 ( \ k λ=1 f λ jκ) = limn→∞ P( [m j=1 Fj ) = 0. (4-13) Then we use union bound to bound P( Sm j=1 Fj ): P( [m j=1 Fj ) ≤ Xm j=1 P(Fj ) ≤ Xm j=1 1 − π(r − R) 2 knα ≤me−π(r−R) 2knα = 1 n(c 2−1)γ · e 2c √ kπγΘ(n α+2β 2 log n) e kπΘ(nα+2β) , (4-14) where the second equality is due to Lemma 1. Since γ > 0 and α + 2β 1 such that Eqn. (4-13) holds. V. CRITICAL TRANSMISSION RANGE FOR CLUSTER-DENSE STATE In this state, we have α + 2β ≥ ϵ k and πR2 = ω( 1 nα ). Different from the cluster-sparse state focusing on the cluster connectivity perspective, we investigate cluster-dense state mainly from the perspective of cluster-member connectivity, since cluster members behave more like independent nodes now. Let Pcds(n, α, β, γ, rw.p. c ) denote the probability that G(n, α, β, γ, rw.p. c ) has some cluster members disconnected. Proposition 2: In a correlated mobile k-hop clustered network G(n, α, β, γ, rw.p. c ) for the cluster-dense state, the critical transmission range is r w.p. c = È log n kπnα , where α + 2β ≥ ϵ k , 0 < α ≤ 1, 0 < γ ≤ 1. A. Necessary Condition of Proposition 2 The probability that a cluster member is not connected during k timeslots is P(fjκ) = (1 − πr2 ) knα . (5-1) The following lemma will show the probability that there exists one cluster member not connected, if we regard each cluster member as independent nodes. Lemma 4: If r = Èlog n+ξ kπnα , α + 2β ≥ ϵ k , 0 < α ≤ 1, for any fixed 0 < θ < 1 and sufficiently large n, we have θe−ξ ≤ n 1 − πr2 knα ≤ e −ξ . (5-2) Proof: For the right hand side of Eqn. (5-2), n 1 − πr2 knα ≤ ne−kπnαr 2 = e −ξ . Then employing similar technique in the proof of Lemma 2, for all sufficient large n, we have log n 1 − πr2 knα ≥ log n − knα πr2 + 5 6 (πr2 ) 2 = − ξ − 5(log n + ξ) 2 6knα , − ξ − µ3. (5-3)
As n goes to infinity,H3 will go to 0.Let =e#2r）≤(1-2mr2)n 2logn (5-10) (5-5) ≤n~e-装 where in the second equality we let t=-0.Let noo where the second inequality is due to Lemma 4. and the lemma follows. Lemma6:fr=√s+d,where a+28≥元，0< When2r,the related positions of and krna a≤l,0<y≤1 and lim(m)=ξ<+oo,we have are shown in Figure 5.1.Therefore we have lim inf Ped(m,a,B,,rp）≥e(1-e). (5-6) P(I,e‖=x)P(会nfe|le,el=x)d ≤ 2”红1-22士Acs茎2Yr2上 f2r2rxd江 Proof:For a fixed E,let Km denote the event that fir is the only failed session during k time slots and we have 42 sin 20(1-2wr2+20r2-r2 sin 20)mdo m四 Pc(n,a,B,x,rp)≥∑∑P(c) 4r2 j=1k=1 ≤R0 sin 20e(2si 20)ndo 空-三.n加) =e-2mnor2 4p2 sin 20e 2do 台台 (5-7) 2 -∑∑∑∑(f, ≤n-是e-等e善4(logn+) sin 20e odo krna R2 Jo j=1K=1≠jk'=1 =n-e-等e是4logn+1n走 The second term to compute the probability that two members kmno Ra o(1ogn〉 (5-11) in a same cluster failed.The third term is to compute the probability that two memebrs in different clusters failed. where we let t=2r cos6 in the second equality,and the last equality is due to Lemma 5. For the first and third terms,we have By substituting Eqn.(5-10),Eqn.(5-11)and r into Eqn. ∑PU-∑∑∑三PUxn5) (5-9),we can bound Peds(n,a,B,r-p.)as follows. =1=】 j=1k=1i≠jk'=1 Pf_cds(n,a,B,Y,rP) ≥2U)-(∑PU (5-8) ≥9e-(1-e-)-e-2cn-y1+4e是logn+o kinaR20(oo// =n(1-πr2)km(1-n(1-r2m） =e-f1-e-)-e2x(n-2+4e是1+5 ≥0e-f(1-e-)】 色0e-f-(1+4e-2E knnoian-go(1) where the third inequality is due to Lemma 4. (5-12)
7 As n goes to infinity, µ3 will go to 0. Let θ = e −µ 2r, we have P f λ jκ ∩ f λ jκ′ | ∥ψ λ jκ, ψλ jκ′∥ > 2r ≤ (1 − 2πr2 ) n α ≤ n − 2 k e − 2ξ k , (5-10) where the second inequality is due to Lemma 4. When ∥ψ λ jκ, ψλ jκ′∥ ≤ 2r, the related positions of ψ λ jκ and ψ λ jκ′ are shown in Figure 5.1. Therefore we have Z 2r x=0 P ∥ψ λ jκ, ψλ jκ′∥ = x P f λ jκ ∩ f λ jκ′ | ∥ψ λ jκ, ψλ jκ′∥ = x dx ≤ Z 2r 0 2πx dx πR2 1 − 2πr 2 + 4 arccos x 2 r 2π · πr 2 − x É r 2 − x2 4 n α = 4r 2 R2 Z π 2 0 sin 2θ(1 − 2πr 2 + 2θr2 − r 2 sin 2θ) n α dθ ≤ 4r 2 R2 Z π 2 0 sin 2θe(−2πr2+2θr2−r 2 sin 2θ)n α dθ = e −2πnαr 2 4r 2 R2 Z π 2 0 sin 2θe(2θr2−r 2 sin 2θ)n α dθ ≤ n − 2 k e − 2ξ k e ξ k 4(log n + ξ) kπnαR2 Z π 2 0 sin 2θe 2θ−sin 2θ kπ log n dθ = n − 2 k e − 2ξ k e ξ k 4(log n + ξ) kπnαR2 o( n 1 k log n ). (5-11) where we let x = 2r cos θ in the second equality, and the last equality is due to Lemma 5. By substituting Eqn. (5-10), Eqn. (5-11) and r into Eqn. (5-9), we can bound Pcds(n, α, β, γ, rw.p. c ) as follows. Pf cds(n, α, β, γ, rw.p. c ) ≥ θe−ξ (1 − e −ξ ) − e −2ξn −γ 1 + 4e ξ k log n + ξ kπnαR2 o( n 1 k log n ) k = θe−ξ (1 − e −ξ ) − e −2ξ n − γ k + 4e ξ k 1 + ξ log n kπnα+2β− ϵ k o(1)k , θe−ξ − (1 + µ4)e −2ξ (5-12)
for any u>0 and sufficient large n.The second equality is B.Necessary Condition of Proposition 3 due to Egn.(5-8)and Egn.(5-9). ■ For convenience,we re-index the sub-clusters in each cluster from 1 to nk(+28)and define several notations. B.Sufficient Condition of Proposition 2 .Cix:the kth sub-cluster in the jth cluster. Similar to previous section,we let r =cr2-p.(c>1),and .Six:the event that the Cix is disconnected. use the union bound to obtain .Ki:the event that the Cix is the only sub-cluster in the whole system that is disconnected. P(U(U∩)≤∑∑（∩） 1 =1k=1 入= Similar to the proof in Section IV,we will first bound the a-wr) probability that a given sub-cluster is not connected during k (5-13) timeslots.Later,we will show that the probability that there exists a sub-cluster that is not connected,is bounded from ≤ne~kanar2 0.Since these sub-clusters are not really independent,the 1 disconnected probability should minus the probability that two -ne-1' sub-clusters are disconnected concurrently.The detail analysis is as follows. Taking limits of both sides,and note that c>1,we finish the proof of the sufficient condition of rp.in Proposition 2. Note that the sub-clusters have the feature of clusters in cluster-sparse state,we can use similar way to bound P(Sjs). VI.THE CRITICAL TRANSMISSION RANGE FOR （1-πr+2)≤PS)≤（1-r-3)m.61D CLUSTER-INFERIOR DENSE STATE The cluster-inferior dense state is a transition state between If we regard each cluster member as independent nodes,the the cluster-sparse and cluster-dense state and 0e(1-e-). (6-4) large,each sub-cluster will not be empty.Furthermore,these sub-clusters have the feature of clusters in cluster-sparse state because their radius r=o(rc),and we will virtually regard Proof:For a fixed value of we evaluate the nodes in each sub-cluster as a whole. lim inf Pcids(n,a,B,,rp)from the perspective of
8 for any µ4 > 0 and sufficient large n. The second equality is due to Eqn. (5-8) and Eqn. (5-9). B. Sufficient Condition of Proposition 2 Similar to previous section, we let r = crw.p. c (c > 1), and use the union bound to obtain P [m j=1 [ϖ κ=1 ( \ k λ=1 f λ jκ) ≤ Xm j=1 Xϖ κ=1 P( \ k λ=1 f λ jκ) ≤ Xm j=1 Xϖ κ=1 (1 − πr2 ) n α k ≤ne−kπnαr 2 = 1 nc 2−1 . (5-13) Taking limits of both sides, and note that c > 1, we finish the proof of the sufficient condition of r w.p. c in Proposition 2. VI. THE CRITICAL TRANSMISSION RANGE FOR CLUSTER-INFERIOR DENSE STATE The cluster-inferior dense state is a transition state between the cluster-sparse and cluster-dense state and 0 ≤ α+2β < ϵ k . Therefore πR2 = ω( 1 nα ). Let Pcids(n, α, β, γ, rw.p. c ) denote the probability that G(n, α, β, γ, rw.p. c ) is disconnected. Proposition 3: In a correlated mobile k-hop clustered network G(n, α, β, γ, rw.p. c ) for the cluster-inferior dense state, the critical transmission range is r w.p. c = È[k(α+2β)+γ] log n kπnα , where 0 < α ≤ 1, 0 ≤ α + 2β < ϵ k , 0 < γ ≤ 1. In this state, since 0 ≤ α + 2β < ϵ k , we have r w.p. c = o(R). Nodes in a same cluster can neither be treated totally independently, nor as a whole. The proof for necessary condition is conducted from the perspective of sub-cluster, which is introduced as follows. A. Basis of Sub-Cluster For each cluster, we cut out n α+2β small circular areas (with radius of r¯ = 1 n α 2 log n ), not overlapping with each other. Since the total area of these small circular areas is n α+2β · πr¯ 2 = o(n 2β ), the division is feasible. After segmentation, we get n α+2β sub-areas in each cluster. We denote a sub-cluster as a set of k sub-areas, in which there is one sub-area at one timeslot. Specifically, a sub-cluster is indexed by (a1, a2, ..., ak), where 0 ≤ ai ≤ n α+2β − 1, i = 1, 2, ..., k. A node x ∈ (a1, a2, ..., ak) if and only if x is in subarea ai during time slot i, where i = 1, 2, ..., k. It is easy to see that there are totally n k(α+2β) sub-clusters in k time slots. The average number of nodes in each sub-cluster is ϖ · ( πr¯ 2 πR2 ) k = Θ( n k[ ϵ k −(α+2β)] log2k n ). Therefore, when n is sufficiently large, each sub-cluster will not be empty. Furthermore, these sub-clusters have the feature of clusters in cluster-sparse state because their radius r¯ = o(rc), and we will virtually regard the nodes in each sub-cluster as a whole. B. Necessary Condition of Proposition 3 For convenience, we re-index the sub-clusters in each cluster from 1 to n k(α+2β) and define several notations. • Cjκ: the κth sub-cluster in the jth cluster. • Sjκ: the event that the Cjκ is disconnected. • Ks jκ: the event that the Cjκ is the only sub-cluster in the whole system that is disconnected. Similar to the proof in Section IV, we will first bound the probability that a given sub-cluster is not connected during k timeslots. Later, we will show that the probability that there exists a sub-cluster that is not connected, is bounded from 0. Since these sub-clusters are not really independent, the disconnected probability should minus the probability that two sub-clusters are disconnected concurrently. The detail analysis is as follows. Note that the sub-clusters have the feature of clusters in cluster-sparse state, we can use similar way to bound P(Sjκ). 1 − π(r + ¯r) 2 knα ≤ P(Sjκ) ≤ 1 − π(r − r¯) 2 knα . (6-1) If we regard each cluster member as independent nodes, the following lemma presents the probability that there exists one sub-cluster that is not connected. Lemma 7: If r = È[k(α+2β)+γ] log n+ξ kπnα , 0 ≤ α + 2β < ϵ k , r¯ = 1 n α 2 log n , for any fixed θ < 1 and sufficiently large n, we have n k(α+2β)+γ 1 − π(r + ¯r) 2 knα ≥ θe−ξ . (6-2) Proof: Employing similar technique in the proof of Lemma 2, for all sufficient large n, we have log n k(α+2β)+γ 1 − π(r + ¯r) 2 knα ≥ k(α + 2β) + γ log n − knα π(r + ¯r) 2 + 5 6 π(2r) 2 2 = − ξ − 2kπÊ k(α + 2β) + γ log n + ξ log2 n − kπ log2 n − 40 k(α + 2β) + γ log n + ξ 2 3knα , − ξ − µ5. (6-3) Taking the exponent of both sides and let θ = e −µ5 < 1 , the result follows. Lemma 8: If r = È[k(α+2β)+γ] log n+ξ(n) kπnα , where 0 ≤ α+ 2β < ϵ k , 0 < α ≤ 1, 0 < γ ≤ 1 and limn→∞ ξ(n) = ξ < +∞, we have lim inf n→∞ Pcids(n, α, β, γ, rw.p. c ) ≥ e −ξ (1 − e −ξ ). (6-4) Proof: For a fixed value of ξ, we evaluate lim inf n→∞ Pcids(n, α, β, γ, rw.p. c ) from the perspective of
9 sub-clusters as follows. Therefore, nk(a+28) Pcids(n,a,B,Y,r0p）≥ F(Kj) 会28.nss的*， nk(a+23) k-1 (6-9) 合刚-g8.n nk(a+28)nk(a+28) =日(n-). P(Sn∩Sjx） (6-5) Substituting Egn.(6-6),Egn.(6-7)and Egn.(6-9)into Eqn. (6-5),and let n-oo,the result follows. ■ nk(a+ 2 会名s-22sns C.Sufficient Condition of Proposition 3 -(君6 In this part,we also do segmentation for each cluster.As shown in Figure 6.1,we first cut the cluster into disjoint rings with radii ofk标，k=l,2,·,n号，where手=n-tR. And then cut the k-th ring equally into 2k-1 sub-areas.This segmentation has two features:(1)the whole region of the With Eqn.(6-1)and Lemma 7,we have cluster is covered and(2)each sub-area can be covered by a n(+28) circle with a radius rk.As shown in Figure 6.2,we can bound 日王6小≥mma6-+P)r≥e5 Tk by (6-6) (ksin nk(a+2 会三ss会三-w-y ≤7V+(P (6-10) ≤V1+π2 Sm2n2k(a+28)e-2kzne(r-F)2 ≤4. =e-2.4vot座-头 ≌(1+6)e-2 Cluster Region (6-7) where u6 >0 and can be arbitrary close to 0. Sub-area Then we evaluate the term P(Sixnj).Let k= (a1,a2,...,ak)and=(b1,b2,...,b).Suppose there are exactly t (0<t <k-1)identical elements between the sequences k and k,i.e.,={s(1),s(2),...,s(t)} (1,2,...,k}that as(i)=bs(i),i <t.P(Six n Sj)is determined by three items.i)For eacht,therearechoices on 3.ii)For the t timeslots that Si and Si overlap.the /na+2\ probability is not larger than Fig.6.1:Segmentation illustration iii)For the other k-t timeslots,since the sub-areas don't overlap with each other,the probability is not larger than After this segmentation,we get n+2 sub-areas,each with na+28 ·（1-26-)-0 Putting all these an area of Similar to previous subsection,we can obtain 2 nk(+28)sub-clusters.The average number of nodes in each together,we can prove that (o可)=n(t-a+2）,which shows sub-cluster is·（,az） P()≤()n, (6-8) that when n is sufficiently large,each sub-cluster will not be empty. for sufficient large n. The proof is carried out from the perspective of sub-clusters
9 sub-clusters as follows. Pcids(n, α, β, γ, rw.p. c ) ≥ Xm j=1 n kX (α+2β) κ=1 P(K s jκ) ≥ Xm j=1 n kX (α+2β) κ=1 P(Sjκ) − Xm j=1 X κ̸=κ′ P(Sjκ ∩ Sjκ′ ) − Xm i=1 X j̸=i n kX (α+2β) κ=1 n kX (α+2β) κ′=1 P(Siκ ∩ Sjκ′ ) ≥ Xm j=1 n kX (α+2β) κ=1 P(Sjκ) − Xm j=1 X κ̸=κ′ P(Sjκ ∩ Sjκ′ ) − Xm j=1 n kX (α+2β) κ=1 P(Sjκ) 2 . (6-5) With Eqn. (6-1) and Lemma 7, we have Xm j=1 n kX (α+2β) κ=1 P(Sjκ) ≥ mnk(α+2β) 1−π(r+ ¯r) 2 knα ≥ θe−ξ . (6-6) Xm j=1 n kX (α+2β) κ=1 P(Sjκ) 2 ≤ Xm j=1 n kX (α+2β) κ=1 1 − π(r − r¯) 2 knα 2 ≤m2n 2k(α+2β) e −2kπnα(r−r¯) 2 =e −2ξ e 4 √ kπ· √[k(α+2β)+γ] log n+ξ log n − 2kπ log2 n ,(1 + µ6)e −2ξ , (6-7) where µ6 > 0 and can be arbitrary close to 0. Then we evaluate the term P(Sjκ ∩ Sjκ′ ). Let κ = (a1, a2, ..., ak) and κ ′ = (b1, b2, ..., bk). Suppose there are exactly t (0 ≤ t ≤ k − 1) identical elements between the sequences κ and κ ′ , i.e., ∃ −→s = {s(1), s(2), ..., s(t)} ⊆ {1, 2, ..., k} that as(i) = bs(i) , i ≤ t. P(Sjκ ∩ Sjκ′ ) is determined by three items. i) For each t, there are k t choices on −→s . ii) For the t timeslots that Sjκ and Sjκ′ overlap, the probability is not larger than n α+2β 1 t · 1−π(r −r¯) 2 tnα . iii) For the other k − t timeslots, since the sub-areas don’t overlap with each other, the probability is not larger than n α+2β 2 k−t · 1 − 2π(r − r¯) 2 (k−t)n α . Putting all these together, we can prove that P(Sjκ ∩ Sjκ′ ) ≤ k t n t−2k k γ (6-8) for sufficient large n. Therefore, Xm j=1 X κ̸=κ′ P(Sjκ ∩ Sjκ′ ) ≤ m k X−1 t=0 k t n t−2k k γ = n γ k X−1 t=0 k t n t−2k k γ = Θ(n − γ k ). (6-9) Substituting Eqn. (6-6), Eqn. (6-7) and Eqn. (6-9) into Eqn. (6-5), and let n → ∞, the result follows. C. Sufficient Condition of Proposition 3 In this part, we also do segmentation for each cluster. As shown in Figure 6.1, we first cut the cluster into disjoint rings with radii of kr, k ¯¯ = 1, 2, · · · , n α+2β 2 , where r¯¯ = n − α+2β 2 R. And then cut the k-th ring equally into 2k −1 sub-areas. This segmentation has two features: (1) the whole region of the cluster is covered and (2) each sub-area can be covered by a circle with a radius rk. As shown in Figure 6.2, we can bound rk by rk = r¯¯ É cos2 π 2k − 1 + (k sin π 2k − 1 ) 2 ≤ r¯¯ r 1 + ( kπ 2k − 1 ) 2 ≤ r¯¯ p 1 + π 2 ≤ 4r.¯¯ (6-10) r 2 R n r 2 α β + = Cluster Region Sub-area Fig. 6.1: Segmentation illustration After this segmentation, we get n α+2β sub-areas, each with an area of πr¯¯ 2 . Similar to previous subsection, we can obtain n k(α+2β) sub-clusters. The average number of nodes in each sub-cluster is ϖ · 1 nα+2β) k = n k ϵ k −(α+2β) , which shows that when n is sufficiently large, each sub-cluster will not be empty. The proof is carried out from the perspective of sub-clusters
10 ically,m =m in cluster-sparse state,m =mnk(+28)in 02k-1 π21),we use the union bound and obtain Proof:With a same definition on K.i,and K,we 2k(a+2) have P(U(U∩)=P(U(US) Pems(n,a,(Bi},(wil,,rep) 1=1=1入=1 j=1 m nk(o+28) m2 nk(o+28,) ≤∑∑P(S) + PCx)+∑∑PK=) j=1R=1 j=1k=1 m nk(o+28) ≥∑P(one component failed) 合三--) P(two components in a same state failed) ≤n(a+28)+ye-krn°(r-4标)2 P(two components in different states failed). (7-5) =ne2-(a+2+）+o(点) The first and second terms can be characterized similar to (6-11) previous analysis.The difference lies in the third term,which For c>1,taking limits of both sides,we finish the proof however can still be bounded by the property that clusters in of the sufficient condition of rP.in Proposition 3. different states are independent. VII.CRITICAL TRANSMISSION RANGE FOR For simplicity of presentation,we let x= F.y= =1 CLUSTER-MIXED STATE (W.P.) In this section,we first present an interesting observation =1 P(Sj),2 是rU.Then we have j=1k=1 from the obtained result in previous 3 distinct states and then prove this observation will hold in a more general scenario. mi First trace back to the result in Section IV. 2P(C≥x-x2-y-r网 (7-6) ylogn log ny log m (7-1) where z-x2 is the first and second terms in Eqn.(7-5)whose Vkπna Vkπna proof is similar to (9-4),and xy+zz is the probability in the Then trace back to the proof in Section VI,where each third term of Eqn.(7-5). cluster is split into sub-clusters.The total number of sub- Similarly to Eqn.(6-5), clusters is mnk(+28).And the critical transmission range is as follows. 2 nk(a+28j) log mnk(a+28) PKx)≥y-2-∑∑P(SjnNSj) /k(a+28)+]1ogn Tc=V (7-2) j=1K≠K 1 kπna kxna yx-yz. Finally,trace back to the proof in Section V.In the proof (7-7) we treat each node as an independent cluster and the result is Similar to Eqn.(5-7), as follows. m3 m3 logn Te=kana (7-3) ∑∑PK)≥a-2-∑∑∑PUsn5N) =1=1 j=1K=1K'≠K From Egn.(7-1),Egn.(7-2)and Eqn.(7-3),we define -2-2y relative cluster number m to unify these three states.Specif- (7-8)
10 ( 1) k r − r θ 2 1 k π θ = − O x y kr 2 2 cos ( sin ) 4 2 1 2 1 kr r k r k k π π = + 1), we use the union bound and obtain P [m j=1 [ϖ κ=1 ( \ k λ=1 f λ jκ) =P [m j=1 n k(α+2β) [ κ=1 P(Sjκ) ≤ Xm j=1 n kX (α+2β) κ=1 P(Sjκ) ≤ Xm j=1 n kX (α+2β) κ=1 1 − π(r − 4r¯¯) 2 knα ≤n k(α+2β)+γ e −kπnα(r−4r¯¯) 2 =n −(c 2−1) k(α+2β)+γ +Θ( √ 1 log n ) . (6-11) For c > 1, taking limits of both sides, we finish the proof of the sufficient condition of r w.p. c in Proposition 3. VII. CRITICAL TRANSMISSION RANGE FOR CLUSTER-MIXED STATE (W.P.) In this section, we first present an interesting observation from the obtained result in previous 3 distinct states and then prove this observation will hold in a more general scenario. First trace back to the result in Section IV. rc = r γ log n kπnα = r log nγ kπnα = r log m kπnα . (7-1) Then trace back to the proof in Section VI, where each cluster is split into sub-clusters. The total number of subclusters is mnk(α+2β) . And the critical transmission range is as follows. rc = r [k(α + 2β) + γ] log n kπnα = r log mnk(α+2β) kπnα . (7-2) Finally, trace back to the proof in Section V. In the proof we treat each node as an independent cluster and the result is as follows. rc = r log n kπnα . (7-3) From Eqn. (7-1), Eqn. (7-2) and Eqn. (7-3), we define relative cluster number m¯ to unify these three states. Specifically, m¯ = m in cluster-sparse state, m¯ = mnk(α+2β) in cluster-inferior dense state and m¯ = n in cluster-dense state. Therefore, m¯ can be regarded as the number of independent node groups in the network, and this is also the main finding and contribution of this work. In the following, we will show that this finding still holds in cluster-mixed networks, where distinct states of clusters co-exist in the network. A. Necessary Condition of Theorem 1 Lemma 9: If r = Èlog ¯m+ξ(n) kπnα , where 0 < α ≤ 1 and limn→∞ ξ(n) = ξ < +∞, we have lim inf n→∞ Pcms(n, α, β, γ, rw.p. c ) ≥ 0.9e −ξ (1 − e −ξ ). (7-4) Proof: With a same definition on Kc i ,Ks jκ, and Km jκ, we have Pcms(n, α, {βi}, {ϖi}, γ, rw.p. c ) ≥ Xm1 i=1 P(K c i ) +Xm2 j=1 n k(α+2βj X ) κ=1 P(K s jκ) +Xm3 j=1 Xϖj κ=1 P(K m jκ) ≥ XP(one component failed) − XP(two components in a same state failed) − XP(two components in different states failed). (7-5) The first and second terms can be characterized similar to previous analysis. The difference lies in the third term, which however can still be bounded by the property that clusters in different states are independent. For simplicity of presentation, we let x = mP1 i=1 P(Fi), y = mP2 j=1 n k(α+2βj ) P κ=1 P(Sjκ), z = mP3 j=1 Pϖj κ=1 P(fjκ). Then we have Xm1 i=1 P(K c i ) ≥ x − x 2 − xy − xz, (7-6) where x−x 2 is the first and second terms in Eqn. (7-5) whose proof is similar to (9-4), and xy + xz is the probability in the third term of Eqn. (7-5). Similarly to Eqn. (6-5), Xm2 j=1 n k(α+2βj X ) κ=1 P(K s jκ) ≥y − y 2 − Xm2 j=1 X κ̸=κ′ P(Sjκ ∩ Sjκ′ ) − yx − yz. (7-7) Similar to Eqn. (5-7), Xm3 j=1 Xϖj κ=1 P(K m jκ) ≥z − z 2 − Xm3 j=1 Xϖj κ=1 X κ′̸=κ P(fjκ ∩ fjκ′ ) − zx − zy. (7-8)
