Mobility Increases the Connectivity of Wireless Networks.pdf_大学文库

1 Mobility Increases the Connectivity of Wireless Networks Xinbing Wang,Xiaojun Lin2,Qingsi Wang,Wentao Luan 1.Department of Electronic Engineering,Shanghai Jiao Tong University,China 2.Department of Electrical and Computer Engineering,Purdue University,USA Abstract-In this paper we investigate the connectivity for this strategy does not ensure that the degree of each node is large-scale clustered wireless sensor and ad hoc networks.We strictly equal to o.Actually,we have the degree of each node study the effect of mobility on the critical transmission range Di>o,since the o-nearest-neighbor relation is asymmetric. for asymptotic connectivity in k-hop clustered networks,and compare to existing results on non-clustered stationary networks. In [4],Xue and Kumar proved that for a network with n nodes By introducing k-hop clustering,any packet from a cluster to be asymptotically connected,(logn)I neighbors are member can reach a cluster head within k hops,and thus the necessary and sufficient.Wan and Yi [3]obtained an improved transmission delay is bounded as e(1)for any finite k.We first asymptotic upper bound on the critical neighbor number for characterize the critical transmission range for connectivity in k-connectivity. mobile k-hop clustered networks where all nodes move under either the random walk mobility model with non-trivial velocity Another strategy is the sector-based strategy that was pro- or the i.i.d.mobility model.By the term non-trivial velocity,we posed as a topology control algorithm by Wattenhofer et al. mean that the velocity of a node v is w(r(n)),where r(n)is the [5]and was further discussed by Li et al.in [6].This strategy transmission range of the node.We then compare with the critical is based on the neighbor connection as described above and transmission range for stationary k-hop clustered networks.In further concerns with the 0-coverage problem.Given that a addition,the critical number of neighbors is studied in a parallel manner for both stationary and mobile networks.We also study node connects bidirectionally to its on nearest neighbors in the transmission power versus delay trade-off and the average the network,where on is a deterministic function of n to be energy consumption per flow among different types of networks specified,for an angle 0 (0,2m),the node is called to be We show that random walk mobility with non-trivial velocities 0-covered by its on nearest neighbors if among them,it can increases connectivity in k-hop clustered networks,and thus find a node in every sector of angle 0.If every node in the significantly decreases the energy consumption and improves the power-delay trade-off.The decrease of energy consumption per graph satisfies this property,the graph is called 0-covered.One flow is shown to be)in clustered networks.These results then wants to find the relation between 0-coverage and overall provide insights on network design and fundamental guidelines connectivity of the network,and to determine the critical value on building a large-scale wireless network. of e which is a deterministic function of 0.In [7].Xue and Kumar determined that the exact threshold function for 0- I.INTRODUCTION coverage,including even the pre-constant,is logn,for YONNECTIVITY is a basic concern in designing and any 0 E(0,2),and m-coverage with high probability implies overall connectivity with high probability. implementing wireless networks,and hence is also of The network models studied in these prior works are non- paramount significance.Nodes in the networks need to connect clustered (or flat)and stationary networks.Flat networks are to others by adjusting their transmission power and thus carry out the network's functionalities.Therefore,three main found to have poor scalability [8][9]and energy ineffi- ciency [10][11].Clustering and mobility have been found schemes of connecting strategies are proposed in literature. The first type of connecting strategies is distance-based. to improve various aspects of network performance.First, clustered networks and clustering algorithms are studied by That is,for a graph (network)G(V,E)and any two nodes i,j V,eij E if and only if the Euclidean distance many researchers [12][13][14][15]and have applications in both sensor networks [10][16]and ad hoc networks [17][18]. between i and j is at most r.The critical value of r for With random infrastructure support,the throughput capacity connectivity when the number of nodes grows to infinity has been studied.In [1].Gupta and Kumar proved that with range IThe following asymptotic notations are used throughout this paper.Given r(n)=,overall connectivity can be established non-negative functions f(n)and g(n): with probability one as noo if and only if c(n)oo. 1)f(n)=日(g(n)）means for two constants00,f(n)>cg(n)for sufficiently large n. Of equal importance,the second type of connecting strate- 4)f(n)g(n）means lim-+oxgm=1.】 gies is the number-of-neighbor-based strategy,which means 5)f(n)=o(g(n))means limn-oo that for G(V,E)and any two nodes i,j∈V,ey∈Eif 80 6)f(n)=w(g(n))means g(n)=o(f(n)) and only if j is among i's nearest neighbors.Note that

1 Mobility Increases the Connectivity of Wireless Networks Xinbing Wang1 , Xiaojun Lin2 , Qingsi Wang1 , Wentao Luan1 1. Department of Electronic Engineering, Shanghai Jiao Tong University, China 2. Department of Electrical and Computer Engineering, Purdue University, USA Abstract—In this paper we investigate the connectivity for large-scale clustered wireless sensor and ad hoc networks. We study the effect of mobility on the critical transmission range for asymptotic connectivity in k-hop clustered networks, and compare to existing results on non-clustered stationary networks. By introducing k-hop clustering, any packet from a cluster member can reach a cluster head within k hops, and thus the transmission delay is bounded as Θ(1) for any finite k. We first characterize the critical transmission range for connectivity in mobile k-hop clustered networks where all nodes move under either the random walk mobility model with non-trivial velocity or the i.i.d. mobility model. By the term non-trivial velocity, we mean that the velocity of a node v is ω ( r(n) ) , where r(n) is the transmission range of the node. We then compare with the critical transmission range for stationary k-hop clustered networks. In addition, the critical number of neighbors is studied in a parallel manner for both stationary and mobile networks. We also study the transmission power versus delay trade-off and the average energy consumption per flow among different types of networks. We show that random walk mobility with non-trivial velocities increases connectivity in k-hop clustered networks, and thus significantly decreases the energy consumption and improves the power-delay trade-off. The decrease of energy consumption per flow is shown to be Θ ( log n nd ) in clustered networks. These results provide insights on network design and fundamental guidelines on building a large-scale wireless network. I. INTRODUCTION C ONNECTIVITY is a basic concern in designing and implementing wireless networks, and hence is also of paramount significance. Nodes in the networks need to connect to others by adjusting their transmission power and thus carry out the network’s functionalities. Therefore, three main schemes of connecting strategies are proposed in literature. The first type of connecting strategies is distance-based. That is, for a graph (network) 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 connectivity when the number of nodes grows to infinity has been studied. In [1], Gupta and Kumar proved that with range r(n) = √ log n+c(n) πn , overall connectivity can be established with probability one as n → ∞ if and only if c(n) → ∞. And this result was independently determined by Penrose [2] as well. In [3], Wan and Yi determined the precise critical transmission range for k-connectivity. Of equal importance, the second type of connecting strategies is the number-of-neighbor-based strategy, which means that for G(V, E) and any two nodes i, j ∈ V , eij ∈ E if and only if j is among i’s ϕ nearest neighbors. Note that this strategy does not ensure that the degree of each node is strictly equal to ϕ. Actually, we have the degree of each node Di ≥ ϕ, since the ϕ-nearest-neighbor relation is asymmetric. In [4], Xue and Kumar proved that for a network with n nodes to be asymptotically connected, Θ ( log n ) 1 neighbors are necessary and sufficient. Wan and Yi [3] obtained an improved asymptotic upper bound on the critical neighbor number for k-connectivity. Another strategy is the sector-based strategy that was proposed as a topology control algorithm by Wattenhofer et al. [5] and was further discussed by Li et al. in [6]. This strategy is based on the neighbor connection as described above and further concerns with the θ-coverage problem. Given that a node connects bidirectionally to its ϕn nearest neighbors in the network, where ϕn is a deterministic function of n to be specified, for an angle θ ∈ (0, 2π), the node is called to be θ-covered by its ϕn nearest neighbors if among them, it can find a node in every sector of angle θ. If every node in the graph satisfies this property, the graph is called θ-covered. One then wants to find the relation between θ-coverage and overall connectivity of the network, and to determine the critical value of ϕθ which is a deterministic function of θ. In [7], Xue and Kumar determined that the exact threshold function for θ- coverage, including even the pre-constant, is log 2π 2π−θ n, for any θ ∈ (0, 2π), and π-coverage with high probability implies overall connectivity with high probability. The network models studied in these prior works are nonclustered (or flat) and stationary networks. Flat networks are found to have poor scalability [8] [9] and energy ineffi- ciency [10] [11]. Clustering and mobility have been found to improve various aspects of network performance. First, clustered networks and clustering algorithms are studied by many researchers [12] [13] [14] [15] and have applications in both sensor networks [10] [16] and ad hoc networks [17] [18]. With random infrastructure support, the throughput capacity 1The following asymptotic notations are used throughout this paper. Given non-negative functions f(n) and g(n): 1) f(n) = Θ( g(n) ) means for two constants 0 0, f(n) ≤ cg(n) for sufficiently large n. 3) f(n) = Ω( g(n) ) means for a constant c > 0, f(n) ≥ cg(n) for sufficiently large n. 4) f(n) ∼ g(n) means limn→∞ f(n) g(n) = 1. 5) f(n) = o ( g(n) ) means limn→∞ f(n) g(n) = 0. 6) f(n) = ω ( g(n) ) means g(n) = o ( f(n) )

3 of random ad hoc networks can be greatly improved,and clustered networks,and it also significantly decreases the the capacity gain is found as when the number energy consumption and the power-delay trade-off.Hence, of ad hoc nodes per access point is bounded as e(1)[19]. these results provide fundamental insights on the design of In [10],Heinzelman et al.presented that in sensor networks large-scale wireless networks. where nodes have sinks or base stations to gather their data, The rest of the paper is organized as follows.In section II, organizing nodes into clusters and using cluster head electing we describe the k-hop clustered network models.We provide and rotating can be more energy-efficient than non-clustered the main results and some intuition behind these results in multi-hop transmission to base stations which is normally section III.In section IV,V and VI,we give the proofs adopted in ad hoc networks.In a separate direction,mobility of the critical transmission range in mobile k-hop clustered has been found to increase the capacity [20]and help security networks under the random walk mobility model with non [21]in ad hoc networks. trivial velocities and the i.i.d.mobility model,and in sta- However,compared to the relatively mature study on the tionary k-hop clustered networks,respectively.As a parallel connectivity of flat and stationary networks,studies on the con- discussion,we consider the critical number of neighbors for nectivity of mobile and clustered networks are quite limited. connectivity in both stationary and mobile clustered network Most previous work on cluster or infrastructure-based mobile in section VII.We then have a discussion on the impact of network focus on capacity [33][34])In a clustered network, mobility on connectivity and network performance in k-hop a packet only needs to reach one of the cluster heads.We clustered networks in section VIII.We conclude in section IX. are interested in two cases in this paper.In a stationary k-hop clustered network,a packet must reach a cluster head withink II.K-HOP CLUSTERED NETWORK MODELS hops.In a mobile k-hop clustered network,a packet must reach In this section,we first provide an overview of flat networks a cluster head directly in k time-slots.Clearly,clustering has and then introduce models of clustered networks.A classifi- an inherent advantage compared to flat networks,and it can cation of k-hop clustered networks is given and related issues alter the energy efficiency and delay of the system.First,it can such as the transmission scheme and the routing strategy are require a different critical transmission range for connectivity, presented,respectively. which may depend on the number of cluster heads and whether the network is stationary or mobile.Second,it can lead to A.An overview of flat networks different delay.For example,with k-hop clustering,the delay Before studying clustered networks,we now give an is bounded by k (i.e.,e(1)).In contrast,in a flat network overview of the so-called flat networks as depicted in Figure 1. with the minimum transmission range,the number of hops A flat network can be defined as a network in which all nodes will increase sadso does the delay.Finally have homogeneousoand functionalities(while theymay both the transmission range and the number of hops can affect have different hardware capabilities),and they can reach each the energy consumption of the network.We can then ask the other without going through any intermediary service points following open question in this paper: such as base stations or sinks.In one word,flat networks are What is the impact of mobility on connectivity of clus- self-organized and infrastructure-free,like ad hoc networks in tered networks subject to delay constraints? common context. In this paper,we concentrate on one of the above con- necting strategies,namely,the distance-based strategy,and the number-of-neighbor-based strategy is briefly studied in a parallel manner afterwards.We study the critical transmission range for connectivity in mobile k-hop clustered networks where all nodes move under either the random walk mobility model with non-trivial velocity or the i.i.d.mobility model. By the term non-trivial velocity,we mean that the velocity of nodesv=w(r(n)).Note that both i.i.d and random walk model can be viewed as the extreme cases of more Fig.1.Flat networks under the distance-based connecting strategies general classes of mobility models [36],[37].For example, the ii.d model may provide useful insights when mobile There are several concepts related to flat networks whose nodes stay around an area for an extended period of time counterparts in clustered networks will be studied in the rest of and then move quickly to another area.Hence,studies under this paper.The most concerned in this paper is connectivity. these two models may provide important insights for the Before defining connectivity of flat networks,we formulate performance and inherent tradeoffs in more general system. flat networks as follows.Let A denote a unit area in 92,and We then compare with the critical transmission range for g(n)be the graph (network)formed when n nodes are placed connectivity in stationary k-hop clustered networks.We also uniformly and independently in A.An edge eij exists between use these results to study the power-delay trade-off and the two nodes i and j,if the distance between them is less than energy efficiency of different types of networks,including r(n)under the distance-based strategy.Then,graph g(n)is flat networks.Our results show that random walk mobility connected if and only if there is a path between any pair of with non-trivial velocity does improve connectivity in k-hop nodes in g(n)

2 of random ad hoc networks can be greatly improved, and the capacity gain is found as Θ (√ n log n ) when the number of ad hoc nodes per access point is bounded as Θ(1) [19]. In [10], Heinzelman et al. presented that in sensor networks where nodes have sinks or base stations to gather their data, organizing nodes into clusters and using cluster head electing and rotating can be more energy-efficient than non-clustered multi-hop transmission to base stations which is normally adopted in ad hoc networks. In a separate direction, mobility has been found to increase the capacity [20] and help security [21] in ad hoc networks. However, compared to the relatively mature study on the connectivity of flat and stationary networks, studies on the connectivity of mobile and clustered networks are quite limited. ( Most previous work on cluster or infrastructure-based mobile network focus on capacity [33] [34]) In a clustered network, a packet only needs to reach one of the cluster heads. We are interested in two cases in this paper. In a stationary k-hop clustered network, a packet must reach a cluster head within k hops. In a mobile k-hop clustered network, a packet must reach a cluster head directly in k time-slots. Clearly, clustering has an inherent advantage compared to flat networks, and it can alter the energy efficiency and delay of the system. First, it can require a different critical transmission range for connectivity, which may depend on the number of cluster heads and whether the network is stationary or mobile. Second, it can lead to different delay. For example, with k-hop clustering, the delay is bounded by k (i.e., Θ(1)). In contrast, in a flat network with the minimum transmission range, the number of hops will increase as Θ (√ n log n ) , and so does the delay. Finally, both the transmission range and the number of hops can affect the energy consumption of the network. We can then ask the following open question in this paper: • What is the impact of mobility on connectivity of clustered networks subject to delay constraints? In this paper, we concentrate on one of the above connecting strategies, namely, the distance-based strategy, and the number-of-neighbor-based strategy is briefly studied in a parallel manner afterwards. We study the critical transmission range for connectivity in mobile k-hop clustered networks where all nodes move under either the random walk mobility model with non-trivial velocity or the i.i.d. mobility model. By the term non-trivial velocity, we mean that the velocity of nodes v = ω ( r(n) ) . Note that both i.i.d and random walk model can be viewed as the extreme cases of more general classes of mobility models [36], [37]. For example, the i.i.d model may provide useful insights when mobile nodes stay around an area for an extended period of time and then move quickly to another area. Hence, studies under these two models may provide important insights for the performance and inherent tradeoffs in more general system. We then compare with the critical transmission range for connectivity in stationary k-hop clustered networks. We also use these results to study the power-delay trade-off and the energy efficiency of different types of networks, including flat networks. Our results show that random walk mobility with non-trivial velocity does improve connectivity in k-hop clustered networks, and it also significantly decreases the energy consumption and the power-delay trade-off. Hence, these results provide fundamental insights on the design of large-scale wireless networks. The rest of the paper is organized as follows. In section II, we describe the k-hop clustered network models. We provide the main results and some intuition behind these results in section III. In section IV, V and VI, we give the proofs of the critical transmission range in mobile k-hop clustered networks under the random walk mobility model with nontrivial velocities and the i.i.d. mobility model, and in stationary k-hop clustered networks, respectively. As a parallel discussion, we consider the critical number of neighbors for connectivity in both stationary and mobile clustered network in section VII. We then have a discussion on the impact of mobility on connectivity and network performance in k-hop clustered networks in section VIII. We conclude in section IX. II. K-HOP CLUSTERED NETWORK MODELS In this section, we first provide an overview of flat networks and then introduce models of clustered networks. A classifi- cation of k-hop clustered networks is given and related issues such as the transmission scheme and the routing strategy are presented, respectively. A. An overview of flat networks Before studying clustered networks, we now give an overview of the so-called flat networks as depicted in Figure 1. A flat network can be defined as a network in which all nodes have homogeneous roles and functionalities (while they may have different hardware capabilities), and they can reach each other without going through any intermediary service points such as base stations or sinks. In one word, flat networks are self-organized and infrastructure-free, like ad hoc networks in common context. XT Fig. 1. Flat networks under the distance-based connecting strategies There are several concepts related to flat networks whose counterparts in clustered networks will be studied in the rest of this paper. The most concerned in this paper is connectivity. Before defining connectivity of flat networks, we formulate flat networks as follows. Let A denote a unit area in R2 , and G(n) be the graph (network) formed when n nodes are placed uniformly and independently in A. An edge eij exists between two nodes i and j, if the distance between them is less than r(n) under the distance-based strategy. Then, graph G(n) is connected if and only if there is a path between any pair of nodes in G(n)

B.Classification of k-hop clustered networks remain static during the rest of the time-slot.In addition, In contrast to flat networks,in clustered networks nodes are we assume that d >(Please refer to the proof of organized into clusters.A cluster head is selected within each Proposition 5.1 where we need the condition that d>.) cluster to serve the other cluster-member nodes (i.e.,clients). b.Transmission scheme We assume that a clustered network consists of n cluster- We divide the channel into W(W 2)sub-channels,and member nodes and nd cluster-head nodes,where d is called the thus the network can accommodate at least W flows initiated cluster head exponent and 00 for In every packet,we assume that there is a TTL (time to live) all m.Further,we assume that there exists an index m field to record the number of hops that the packet has been D(m,) 公e品a7 v(m) forwarded.The initial value of TTL is set to 1 and each relay increases the counter by one when it receives the packet.When and we assume that Umin<.In other words,not all the hop counter is greater than k,the packet is discarded and nodes can traverse a side of the torus in k slots.Note we say that the session is failed.Every k time-slots constitute that we do allow v(m)to scale with n.We will see a period.We assume that there is a SYN(synchronize)field later that the probability of full connectivity will depend for all nodes to be synchronized and data-flows are initiated heavily on the dynamics of the nodes belonging to class only at the beginning of each period.This assumption accords m,.We then partition the data transmission process into with the design of some novel energy-efficient duty-circle time-slots with unit length.At the beginning of each MAC protocols (RMAC [24],DW-MAC [25]).Our proposed period (i.e.,every k slots;see Transmission scheme for transmission scheme is illustrated in Figure 2. the definition of a period)each member node randomly c.Routing strategy and independently select a speed V=v according to As to the routing strategy,we simply assume that a cluster the distribution of V,and uniformly and independently member holds the packet (acting as the relay of itself),if it choose a random direction 6 [0,2).The node then does not have a cluster head in its transmission range during moves along this direction with the constant speed v its course of movement,or sends the packet to the cluster head for the entire period.Note that the mobility pattern of once they meet. nodes in our model is slightly different from that defined Note that this assumption requires that a cluster member can in [22]and they do not bounce off the border since we know the existence of a cluster head within the transmission have assumed the unit square to be a torus. range.Such an assumption would be valid when (1)the cluster I.I.D.Mobility Model:The transmission process is also heads are static and the cluster member has knowledge of divided into slots as we did above and at the beginning its own position and the positions of cluster heads;or (2) of each time-slot each member node will randomly and the cluster heads broadcast a pilot signal that covers nearby uniformly choose a position within the unit torus and cluster members.Our routing strategy under the random walk mobility assumption is illustrated in Figure 3. 2In the random walk mobility model defined in [22],each movement either corresponds to a constant time interval t,or corresponds to a constant distance Note that in the above model we choose not to use multi-hop traveled.The model we use conforms with the former case. transmissions in mobile k-hop clustered networks.Although

3 B. Classification of k-hop clustered networks In contrast to flat networks, in clustered networks nodes are organized into clusters. A cluster head is selected within each cluster to serve the other cluster-member nodes (i.e., clients). We assume that a clustered network consists of n clustermember nodes and n d cluster-head nodes, where d is called the cluster head exponent and 0 0 for all m. Further, we assume that there exists an index m⋆ such that for all sufficiently large n, v (m) logn npm ≥ v (m⋆) logn npm⋆ for all m. Let vmin represent the minimum value of V , and we assume that vmin ≤ 1 k . In other words, not all nodes can traverse a side of the torus in k slots. Note that we do allow v (m) to scale with n. We will see later that the probability of full connectivity will depend heavily on the dynamics of the nodes belonging to class m⋆. We then partition the data transmission process into time-slots with unit length. At the beginning of each period (i.e., every k slots; see Transmission scheme for the definition of a period) each member node randomly and independently select a speed V = v according to the distribution of V , and uniformly and independently choose a random direction θ ∈ [0, 2π). The node then moves along this direction θ with the constant speed v for the entire period. Note that the mobility pattern of nodes in our model is slightly different from that defined in [22] and they do not bounce off the border since we have assumed the unit square to be a torus. • I.I.D. Mobility Model: The transmission process is also divided into slots as we did above and at the beginning of each time-slot each member node will randomly and uniformly choose a position within the unit torus and 2 In the random walk mobility model defined in [22], each movement either corresponds to a constant time interval t, or corresponds to a constant distance traveled. The model we use conforms with the former case. remain static during the rest of the time-slot. In addition, we assume that d > 1 k . (Please refer to the proof of Proposition 5.1 where we need the condition that d > 1 k .) b. Transmission scheme We divide the channel into W(W ≥ 2) sub-channels, and thus the network can accommodate at least W flows initiated in a certain time-slot. Moreover, we assume that for each flow, the packet is forwarded for one hop in each time-slot. Therefore, the maximum delay for the transmission of a packet in our network model is k time-slots, or the delay constraint is D = k. In section VIII, we will mainly use the notation D as the delay constraint in our discussion on the power-delay trade-off in k-hop clustered networks. QYRUZYVKXVKXOUJ 9 8 8 8 8 * 9 8 8 9 8 8 8 8 8 8 8 ZNK::2K^VOXKY GTJZNKVGIQKZ OYJXUVVKJ ZNKOTOZOGZOUTULYKYYOUTY OYY_TINXUTO`KJGZZNK HKMOTTOTMULGVKXOUJ ZOSK 9 9U[XIK 8 8KRG_ * *KYZOTGZOUT 9?4 ::2 5ZNKXLOKRJY VKXOUJť VKXOUJť H H VKXOUJťH Fig. 2. Transmission scheme in mobile k-hop clustered networks. We use the term session to refer to the process that a packet is forwarded from its source cluster member to a cluster head. In every packet, we assume that there is a TTL (time to live) field to record the number of hops that the packet has been forwarded. The initial value of TTL is set to 1 and each relay increases the counter by one when it receives the packet. When the hop counter is greater than k, the packet is discarded and we say that the session is failed. Every k time-slots constitute a period. We assume that there is a SYN (synchronize) field for all nodes to be synchronized and data-flows are initiated only at the beginning of each period. This assumption accords with the design of some novel energy-efficient duty-circle MAC protocols (RMAC [24], DW-MAC [25]). Our proposed transmission scheme is illustrated in Figure 2. c. Routing strategy As to the routing strategy, we simply assume that a cluster member holds the packet (acting as the relay of itself), if it does not have a cluster head in its transmission range during its course of movement, or sends the packet to the cluster head once they meet. Note that this assumption requires that a cluster member can know the existence of a cluster head within the transmission range. Such an assumption would be valid when (1) the cluster heads are static and the cluster member has knowledge of its own position and the positions of cluster heads; or (2) the cluster heads broadcast a pilot signal that covers nearby cluster members. Our routing strategy under the random walk mobility assumption is illustrated in Figure 3. Note that in the above model we choose not to use multi-hop transmissions in mobile k-hop clustered networks. Although

4 XT \: LUX]GXJZUGIR[YZKXNKGJ GTJIUSVRKZKGYKYYOUT NURJZNKVGIQKZ SUHORKIR[YZKXSKSHKX IR[YZKXNKGJ VUYOZOUTOTSU\KSKTZ NURJZNKVGIQKZ Fig. 3. Routing strategy in mobile k-hop clustered networks, random walk mobility. multi-hop transmissions may further improve system performance, establishing multi-hop paths to cluster-heads would have required the mobile nodes to dynamically discover the cluster-heads that are k times its transmission range away.This would require either a significantly larger pilot signal transmitted by the cluster-heads, or location information of both the mobile and the cluster-heads. In contrast, our study in this paper does not requite these mechanisms. Further, as we can see, even without multi-hop transmissions, the analysis is already quite complicated due to various difficulties in the proofs. Hence, we decided to leave multihop transmissions to the cluster head as future work. d. Memoryless assumption For both mobility models, we further make the following memoryless assumption. That is, all cluster-member nodes are memoryless about their past experience of the success or failure of sessions. Furthermore, all cluster-member nodes do not record the positions of any cluster-head nodes with which they may have communicated. Thus, under this memoryless assumption, in each period, the distribution of head nodes is still uniform in the area of network, as seen by the member nodes. 2) Stationary k-hop clustered networks: In a stationary khop clustered network, all nodes remain static after uniformly distributed in the unit area. As in its mobile counterpart, we also assume that the packet is forwarded for one hop in each time-slot. 3) Redefining connectivity in clustered networks: Due to clustering and mobility, the definition of connectivity in clustered networks is different from that in flat networks. For stationary k-hop clustered networks, we say that a cluster member is connected if it can reach a cluster head within k hops. For mobile clustered networks, a cluster member is connected if it can reach a cluster head within k slots. If all the cluster members in a network are connected, we define that the network has full connectivity. III. MAIN RESULTS AND INTUITIONS A. Defintions Before we state our main results, we first formally define the critical transmission range and the critical number of neighbors in both mobile and stationary k-hop clustered networks. Recall that for mobile networks, in every period of k timeslots, each node may attempt to connect to the cluster head. For mobile k-hop clustered networks, let E denote the event that all cluster members are connected in a given period Λ, and let P Λ(E) denote the the corresponding probability. We then are ready to define the critical transmission range for clustered networks. Definition 3.1: For mobile k-hop clustered networks, r(n) is the critical transmission range if limn→∞ P Λ (E) = 1, if r ≥ cr(n) for any c > 1; limn→∞ P Λ (E) 1; limn→∞ P(E) 1; limn→∞ P Λ (E) 1; limn→∞ P(E) < 1, if ϕ ≤ c ′ϕ(n) and c ′ < 1. B. Main results and intuitions We summarize our main results in this paper as follows: • Under the random walk mobility assumption, the critical transmission range is r(n) = log n 2kv⋆nd , where d is the cluster head exponent, 0 < d ≤ 1, v⋆ = min{ v (m) logn npm , ∀m ∈ M}.Note that v⋆ is a function of n. (See Section II.B)

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

and selected cells u(n) 6(n)= 雪(c.t) 1(c(a,,em)） 31-G(n,k,e(m) 1(Gn,kem)）3 ndo 3 G(n,K,e(n)) c) Fig.4.Cell Selection (4) for all large n.Substituting(4)in (3),we get Note that,by appropriately choosing u(n)(e.g.choosing log (L.H.S.of (1)) u(n)= /Clogn,where the factor C can be set according to the value of do and pm..For a rigorous proof,see [35. lemma 11]),with high probability,there are at least one cluster member in each of these selected cells taking the speed (m). 2 d Pick such a cluster member node from each of these selected （+)ga+g.仰） cells.There are a total of n of these nodes.Let Y denote the set of such cluster member nodes.Note that any two nodes --空s,-间学gn+空g+网 in Y are at a distance of at least away.Let si be the = session initiated by node i and we say that session si fails if i is not connected (i.e.,it cannot reach a cluster head in k -(1+e(n))klogn p. time-slots).Then,consider an arbitrary period A,we have 5((1+e(n))(logn+s)logn(np.) 6 nd P片rn(n,r(n) Since c(n)o the right hand side converges to 2PA({some session si fails in Gru(n,r(n))}) logp.as n oo.Hence,for any0 we can choose Na such that ≥∑pA({s is the only failed session in(n,r(ml)） iEY b(L-H5.of())之-发-岁gw-空-2 ≥ pA(s;is a failed session in (nr(n)}) ieY for all n>Na.Taking the exponent of both sides and using 0=e-,the result follows. -∑∑pA({s ands are failed sessions ieYj≠i Let g(n,r(n))denote the network where two nodes can in Grw(n,r(n))}). (5) communicate if their Euclidean distance is at most r(n)and PA(n,r(n))be the probability that G(n(n))has some node that is not connected in the period A.Then we have the Next,we will evaluate the two terms on the right hand side of following proposition. (5),respectively.We will find a lower bound for the first term Proposition4.:frm)）=學logn+(n),hen and an upper bound for the second term.Then,P(n,r(n)) 2kv,nd will be proved to be bounded away from zero.Proposition 4.1 will then follows. lim infP片rn(n,r(n) ≥e-(k+粤1ogp)(e-号-e-(k+91og)） 3Equation (2)is similar to the corresponding equation in the proof of where k =limno k(n),K>do-logp.. Theorem 2.1 in [1].However,the summation in [1]is over all nodes,while here the summation is only over nodes i and j in the set Y.The reason Proof:Let u(n)O)Then we divide the unit that we have to consider a smaller set Y is because otherwise the second summation may diverge.In [1],in order to ensure the convergence of the square intocells and each cell is of size (n). corresponding second summation,it is essential that,when nodes i and j Now,among these cells,pick n of them such that each are both disconnected,they must be at least some distance apart.In our case.the corresponding property would require that,if si and sj are both of them is at least away from others.For example,we failed sessions,nodes i and j must be some distance apart.Unfortunately, this property does not hold for all nodes.On the other hand,the restriction can choose a subset of the highlighted cells in Figure 4. to the set Y helps to enforce this property

6 and δ(n) = ∑∞ i=3 1 i ( G ( n, κ, ϵ(n) ) )i ≤ ∑∞ i=3 1 3 ( G ( n, κ, ϵ(n) ) )i = 1 3 ( G ( n, κ, ϵ(n) ) )3 1 − G ( n, κ, ϵ(n) ) ≤ 1 3 ( G ( n, κ, ϵ(n) ) )3 G ( n, κ, ϵ(n) ) = 1 3 ( G ( n, κ, ϵ(n) ) )2 , (4) for all large n. Substituting (4) in (3), we get log ( L.H.S. of (1)) ≥ d0 2 log n − n d ( G ( n, κ, ϵ(n) ) + 5 6 ( G ( n, κ, ϵ(n) ) )2 ) = d0 2 log n − n d ( ( 1 + ϵ(n) ) d0 2 log n + κ nd logn (np⋆) + 5 6 (( 1 + ϵ(n) ) d0 2 log n + κ nd logn (np⋆) )2 ) = −κ − d0 2 log p⋆ − ϵ(n)(d0 2 log n + d0 2 log p⋆ + κ) − ( 1 + ϵ(n) ) κ logn p⋆ − 5 6 (( 1 + ϵ(n) ) ( d0 2 log n + κ) logn (np⋆) )2 nd . Since ϵ(n) = 1 log n , the right hand side converges to −κ − d0 2 log p⋆ − d0 2 as n → ∞. Hence, for any ϵ >˜ 0 we can choose Nϵ˜ such that log ( L.H.S. of (1)) ≥ −κ − d0 2 log p⋆ − d0 2 − ϵ,˜ for all n > Nϵ˜. Taking the exponent of both sides and using θ = e −ϵ˜ , the result follows. Let Grw(n, r(n)) denote the network where two nodes can communicate if their Euclidean distance is at most r(n) and P Λ f rw(n, r(n)) be the probability that Grw(n, r(n)) has some node that is not connected in the period Λ. Then we have the following proposition. Proposition 4.1: If r(n) = d0 2 log n+κ(n) 2kv⋆nd , then lim inf n→∞ P Λ f rw(n, r(n)) ≥ e −(κ+ d0 2 log p⋆) ( e − d0 2 − e −(κ+ d0 2 log p⋆) ) where κ = limn→∞ κ(n), κ > d0 2 − d0 2 log p⋆. Proof: Let u(n) = O (√ log n n ) . Then we divide the unit square into 1 u(n) × 1 u(n) cells and each cell is of size u 2 (n). Now, among these cells, pick n d0 2 of them such that each of them is at least √ 1 nd0 away from others. For example, we can choose a subset of the highlighted cells in Figure 4. YKRKIZKJIKRRY Fig. 4. Cell Selection Note that, by appropriately choosing u(n) (e.g. choosing u(n) = √ C log n n , where the factor C can be set according to the value of d0 and pm⋆ . For a rigorous proof, see [35, lemma 11] ), with high probability, there are at least one cluster member in each of these selected cells taking the speed v (m⋆) . Pick such a cluster member node from each of these selected cells. There are a total of n d0 2 of these nodes. Let Y denote the set of such cluster member nodes. Note that any two nodes in Y are at a distance of at least √ 1 nd0 away. Let si be the session initiated by node i and we say that session si fails if i is not connected (i.e., it cannot reach a cluster head in k time-slots). Then, consider an arbitrary period Λ, we have3 P Λ f rw(n, r(n)) ≥ P Λ ({some session si fails in Grw(n, r(n))}) ≥ ∑ i∈Y P Λ ({si is the only failed session in Grw(n, r(n))}) ≥ ∑ i∈Y P Λ ({si is a failed session in Grw(n, r(n))}) − ∑ i∈Y ∑ j̸=i P Λ ({si and sj are failed sessions in Grw(n, r(n))}). (5) Next, we will evaluate the two terms on the right hand side of (5), respectively. We will find a lower bound for the first term and an upper bound for the second term. Then, P Λ f rw(n, r(n)) will be proved to be bounded away from zero. Proposition 4.1 will then follows. 3Equation (2) is similar to the corresponding equation in the proof of Theorem 2.1 in [1]. However, the summation in [1] is over all nodes, while here the summation is only over nodes i and j in the set Y. The reason that we have to consider a smaller set Y is because otherwise the second summation may diverge. In [1], in order to ensure the convergence of the corresponding second summation, it is essential that, when nodes i and j are both disconnected, they must be at least some distance apart. In our case, the corresponding property would require that, if si and sj are both failed sessions, nodes i and j must be some distance apart. Unfortunately, this property does not hold for all nodes. On the other hand, the restriction to the set Y helps to enforce this property.

7 Specifically, for the first term, using Lemma 4.1 with ϵ(n) = 1 log n , we know that it is bounded by n d0 2 ( 1 − ( πr2 (n) + 2kv(m⋆) r(n) ) )n d = n d0 2 ( 1 − ( 1 + ϵ1(n) ) 2kv(m⋆) r(n) )n d > n d0 2 ( 1 − ( 1 + ϵ(n) ) 2kv(m⋆) r(n) )n d ≥ θe−κ− d0 2 log p⋆− d0 2 , (6) where ϵ1(n) = πr(n) 2kv(m⋆) π/2 as shown in Figure 6. The angle of intersection can be close to π if the two tracks are along a straight line. But we can show that this event happens with very low probability. Let ϕ be the angle of intersection and ε = ε(n) = log2 n nd−d′ , where d ′ π − ε) d > d0. Then, for such π/2 ≤ ϕ ≤ π − ε, the intersection is of area 2r(n) sin ϕ · 2r(n) ≤ 4r(n)kv(m⋆) · r(n) kv(m⋆) · 1 ε(n) = o ( 4r(n)kv(m⋆) log2 n ) , (10) where we have used Remark 4.1. Let S Λ i+j denote the total area covered by i and j during the period Λ. Then for some ϵ ′ = o ( 1 log2 n ) we can obtain that, whenever ϕ ≤ π − ε the following holds. S Λ i+j ≥ 4r(n)kv(m⋆) − o ( 4r(n)kv(m⋆) log2 n ) = (1 − ϵ ′ )4r(n)kv(m⋆) , (11) for all n > Nϵ ′ . Let Tij be the event that S Λ i+j ≥ (1 − ϵ ′ )4r(n)kv(m⋆) , taking into account both cases we have P(Tij ) > 1 − log4 n 4π 2nd⋆ . Therefore, each term in the second summation is bounded by P Λ ({si and sj are failed sessions in Grw}) = P Λ ({si and sj are failed sessions in Grw} | Tij )P(Tij ) +P Λ ({si and sj are failed sessions in Grw} | Tij )P(Tij ) ≤ P Λ ({si and sj are failed sessions in Grw} | Tij ) + P(Tij ) ≤ ( 1 − ( 1 − ϵ ′ ) 4r(n)kv(m⋆) )n d + log4 n 4π 2nd⋆ ≤ e −4n d (1−ϵ ′ )r(n)kv(m⋆) + log4 n 4π 2nd⋆ ≤ e −2(1−ϵ ′ ) logn (np⋆)( d0 2 log n+κ) + log4 n nd⋆ (12) where the forth step is due to the well-known bound 1 − x ≤ e −x for x ∈ [0, 1]. (13) Therefore, combined with (6) and (12) in (5), we obtain P Λ f rw(n, r(n)) ≥ θe−κ− d0 2 log p⋆− d0 2 −n d0 ( e −2(1−ϵ ′ ) logn (np⋆)( d0 2 log n+κ) + log4 n nd⋆ ) , for all n > Nθ,ϵ′ = max{Nθ, Nϵ ′}

9 roughly requires r(n) = log n 2kv⋆nd . Nonetheless, the order in terms of n is the same. Also note that by assuming the network area is a torus, we have eliminated the possibility that nodes get reflected at the boundary. If reflection is allowed, it will lead to minimal change to our conclusions. Specifically, the critical transmission range under this case is r(n) = log n kv⋆nd , where 0 0. Proof: Unlike the techniques employed in the proof of Proposition 4.1, we will consider all pairs of node i and j that are disconnected cluster members. To evaluate Pf iid(n, r(n), we have Pf iid(n, r(n)) ≥ ∑n i=1 P({si is a failed session in Giid(n, r(n))}) − ∑n i=1 ∑ j̸=i P({si and sj are failed sessions in Giid(n, r(n))}). (17) Then we evaluate the two terms on the right hand side of (17), respectively, and we have P({si is a failed session}) ≥ (( 1 − πr2 (n) )n d )k (18) and P({si and sj are failed sessions}) ≤ ( 4πr2 (n) ( 1 − πr2 (n) )n d + ( 1 − 4πr2 (n) ) ( 1 − 2πr2 (n) )n d )k . (19) The two terms in the parenthesis on the right hand side of (19) take into account the cases where the two nodes carrying the packet of si and sj are at a distance less than 2r(n) and greater than 2r(n) when initially distributed, respectively. Using (18) and (19) in (17), we obtain Pf iid(n, r(n)) ≥ n ( 1 − πr2 (n) )knd − n 2 ( 4πr2 (n) ( 1 − πr2 (n) )n d + ( 1 − 2πr2 (n) )n d )k . (20) Using Lemma 5.1 and (13), for any fixed θ 0 and for all n > Nϵ,θ,κ. Note that we need d > 1 k in the last step. Since limn→∞ κ(n) = κ, for any ϵ there exits N′ (ϵ) such that for all n ≥ N′ (ϵ), κ(n) ≤ κ + ϵ. Considering that the probability of disconnectedness is monotonously decreasing in κ, then we have Pf iid(n, r(n)) ≥ θe−(κ+ϵ) − (1 + ϵ)e −2(κ+ϵ) , for n ≥ max{Nϵ,θ,κ+ϵ, N′ ϵ}. Taking limits lim inf n→∞ Pf iid(n, r(n)) ≥ θe−(κ+ϵ) − (1 + ϵ)e −2(κ+ϵ) . Since this holds for all ϵ > 0 and θ < 1, the result follows. Then we have the following corollary to prove the necessity part of Theorem 5.1. Corollary 5.1: Under the i.i.d. mobility assumption, the mobile k-hop clustered network is to have failed sessions with positive probability bounded away from zero if πr2 (n) = log n+κ(n) knd and limn→∞ κ(n) < +∞, which means πr2 (n) ≥ log n knd is necessary for the connectivity of mobile k–hop clustered networks with i.i.d. mobility model

10 B.Sufficient condition on r(n)of Theorem 5.1 The specific set of is and js are selected as follow.Let Suppose there are at most n sessions in a periodandu(n).Then we divide the unit square into let E:denote the event that s;is a failed session,where cells such that each cell is of size u2(n). i=1,2,...,n.Let each node have the transmission range Now,among these cells,pick ndo of them such that each of r=cr(n),where c 1.Using the existing approach in Section IV-B,we have them is at least away from others,as shown in Figure 8. selected cells =1 u(n) ≤ n(1-r2） ≤ ne-kndxr2 do 1 4nc2- For any c>1,the result follows. VI.THE CRITICAL TRANSMISSION RANGE FOR CONNECTIVITY OF STATIONARY K-HOP CLUSTERED NETWORKS In this section,our main result is the following theorem. Fig.8.Cell selection Theorem 6.1:For the stationary k-hop clustered networks, Pick one cluster member node from each of these selected the critical transmision rangeis(o）=t√，whee cells to form a set consisted of ndo nodes.Let Y denote the 0e-w(1-e), As to the first term in the right hand side of(21),it is 2+●如 bounded by where k limnoK(n),K>0. Proof:The proof applies similar techniques as that of -roj月产≥n,g: ‘ne=e-% Proposition 4.1,we will not considered all pairs of nodes i where 0<<1.To bound the second term,note that i,jY and j that are disconnected cluster members.The problem for this is that there are too many of these pairs.The intuitive are at least away,which will be larger than 2kr(n) explanation is depicted in the following figure. when n is sufficiently large.Thus,each term in the second summation is bounded by ,·cluster head more than kr(n)away P(and je discomcted))≤(1-2a(kr(m)）". 00 There are too many pairs ij Therefore, in this region such that both i,j are disconnected from the cluster head. Pa_stat((n,r(n)）≥0e-k-n2doe-2mr(r(n)2 ≥0eR-e-2r, Fig.7.An intuitive explanation of the problem in the above approach for all n Ne.x. Further,such i and j may be very close to each other,making The rest of steps are omitted and follows these in the earlier it difficult to bound the probability. proofs

10 B. Sufficient condition on r(n) of Theorem 5.1 Suppose there are at most n sessions in a period λb, and let Ei denote the event that si is a failed session, where i = 1, 2, . . . , n. Let each node have the transmission range r = cr(n), where c > 1. Using the existing approach in Section IV-B, we have P ( ∪n i=1 Ei ) ≤ ∑n i=1 P(Ei) ≤ n (( 1 − πr2 )n d )k ≤ ne−kndπr2 = 1 4nc 2−1 . For any c > 1, the result follows. VI. THE CRITICAL TRANSMISSION RANGE FOR CONNECTIVITY OF STATIONARY K-HOP CLUSTERED NETWORKS In this section, our main result is the following theorem. Theorem 6.1: For the stationary k-hop clustered networks, the critical transmission range is r(n) = 1 k √d log n πnd , where 0 0. Proof: The proof applies similar techniques as that of Proposition 4.1, we will not considered all pairs of nodes i and j that are disconnected cluster members. The problem for this is that there are too many of these pairs. The intuitive explanation is depicted in the following figure. IR[YZKXNKGJ SUXKZNGTQXTG]G_ :NKXKGXKZUUSGT_VGOXYOP OTZNOYXKMOUTY[INZNGZHUZN OPGXKJOYIUTTKIZKJLXUSZNK IR[YZKXNKGJ Fig. 7. An intuitive explanation of the problem in the above approach Further, such i and j may be very close to each other, making it difficult to bound the probability. The specific set of is and js are selected as follow. Let u(n) = O (√ log n n ) . Then we divide the unit square into 1 u(n) × 1 u(n) cells such that each cell is of size u 2 (n). Now, among these cells, pick n d0 of them such that each of them is at least √ 1 nd0 away from others, as shown in Figure 8. YKRKIZKJIKRRY Fig. 8. Cell selection Pick one cluster member node from each of these selected cells to form a set consisted of n d0 nodes. Let Y denote the set of such cluster member nodes. Note that any two nodes in Y are at a distance of at least √ 1 nd0 away. Further, this distance is larger than kr(n) when n is sufficiently large. Then, using the existing approach of computing the probability that the network is disconnected, we have Pd stat(n, r(n)) ≥ ∑ i∈Y P({i is an disconnected cluster member in Gstat(n, r(n))}) − ∑ i,j∈Y, j̸=i P({i and j are disconnected cluster members in Gstat(n, r(n))}). (21) As to the first term in the right hand side of (21), it is bounded by n d0 ( 1 − π ( kr(n) )2 )n d ≥ n d0 · θ · 1 nd0 e −κ = θe−κ , where 0 Nθ,κ. The rest of steps are omitted and follows these in the earlier proofs.