Mobility Increases the Connectivity of Wireless Networks

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 constants0<c1<c2,c1g(n）≤ And this result was independently determined by Penrose [2] f(n）≤c2g(n)for sufficiently large n. 2)f(n)=O(g(n))means for a constant c 0.f(n)<cg(n)for as well.In [3],Wan and Yi determined the precise critical sufficiently large n. transmission range for k-connectivity. 3)f(n)=(g(n))means for a constant c >0,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 strate￾gies 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 pro￾posed 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 non￾clustered (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 < c1 < c2, c1g(n) ≤ f(n) ≤ c2g(n) for sufficiently large n. 2) f(n) = O ( g(n) ) means for a constant c > 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 con￾nectivity 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 clus￾tered networks subject to delay constraints? 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 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 non￾trivial velocities and the i.i.d. mobility model, and in sta￾tionary 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 0<d 1.For ease of presentation, in a certain time-slot.Moreover,we assume that for each we treat nd as an integer in this paper,and all nodes are flow,the packet is forwarded for one hop in each time-slot. placed uniformly and independently in a unit square S in 92. Therefore,the maximum delay for the transmission of a packet Moreover,the unit square is assumed to be a torus. in our network model is k time-slots,or the delay constraint 1)Mobile k-hop clustered networks: is D=k.In section VIIl,we will mainly use the notation D a.Mobility pattern as the delay constraint in our discussion on the power-delay In a mobile k-hop clustered network,we assume that trade-off in k-hop clustered networks. all cluster members move according to a certain mobility pattern while the clustered heads are fixed with the uniform period An. period入b+l distribution. the initiation of sessions 111 Random Walk Mobility Model with Non-Trivial Ve- is synchronized at the the locities 2 [22][23]:Define a discrete random variable V beginning of a period and the packet SRR··· is dropped the speed of a node with the probability mass function P(W=vm）=pm for all m∈M,where the III S:Source index set M is finite and invariant of n.We assume that ay Destination vm）=w(V)(d'<)andm）=O(1,for all time m E M.This assumption,combined with the k-time-slots Other fields deadline that we will introduce next,implies that we are k slots per period interested in the case when the speed is fast enough so that nodes can move multiple transmission ranges before Fig.2.Transmission scheme in mobile k-hop clustered networks. the deadline (please refer to Remark 4.1),for which we expect the scaling laws to differ substantially with that We use the term session to refer to the process that a packet in stationary networks.In addition,we assume that pm is forwarded from its source cluster member to a cluster head. for all m E M does not change with n,and pm >0 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 cluster￾member nodes and n d cluster-head nodes, where d is called the cluster head exponent and 0 < d ≤ 1. For ease of presentation, we treat n d as an integer in this paper, and all nodes are placed uniformly and independently in a unit square S in R2 . Moreover, the unit square is assumed to be a torus. 1) Mobile k-hop clustered networks: a. Mobility pattern In a mobile k-hop clustered network, we assume that all cluster members move according to a certain mobility pattern while the clustered heads are fixed with the uniform distribution. • Random Walk Mobility Model with Non-Trivial Ve￾locities 2 [22] [23]: Define a discrete random variable V the speed of a node with the probability mass function P ( V = v (m) ) = pm for all m ∈ M, where the index set M is finite and invariant of n. We assume that v (m) = ω (√log n nd′ ) (d ′ < d 2 ) and v (m) = O(1), for all m ∈ M. This assumption, combined with the k-time-slots deadline that we will introduce next, implies that we are interested in the case when the speed is fast enough so that nodes can move multiple transmission ranges before the deadline (please refer to Remark 4.1), for which we expect the scaling laws to differ substantially with that in stationary networks. In addition, we assume that pm for all m ∈ M does not change with n, and pm > 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

hold the packet 60 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 forward to a cluster head in both mobile and stationary k-hop clustered networks. and complete a session. Recall that for mobile networks,in every period of k time- Q r(n) slots,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 A,and hold the packet let PA(E)denote the the corresponding probability.We then are ready to define the critical transmission range for clustered mobile cluster member ● cluster head networks. position in movement Definition 3.1:For mobile k-hop clustered networks,r(n) Fig.3.Routing strategy in mobile k-hop clustered networks,random walk is the critical transmission range if mobility. lim PA(E)=1,if r cr(n)for any c>1; n-oo lim PA(E)<1,if r <c'r(n)for some c'<1, multi-hop transmissions may further improve system perfor- For stationary networks,we define E to be the event that mance,establishing multi-hop paths to cluster-heads would all cluster members are connected to a cluster head in k hops. have required the mobile nodes to dynamically discover the cluster-heads that are k times its transmission range away.This Definition 3.2:For stationary k-hop clustered networks, would require either a significantly larger pilot signal trans- r(n)is the critical transmission range if mitted by the cluster-heads,or location information of both lim P(E)=1,if r cr(n)and c>1; the mobile and the cluster-heads.In contrast,our study in n子@。 this paper does not requite these mechanisms.Further,as we lim P(E)<1,if r<c'r(n)and c'<1. can see,even without multi-hop transmissions,the analysis is already quite complicated due to various difficulties in the In parallel,we have the following definition for the critical proofs.Hence,we decided to leave multihop transmissions to number of neighbors.Note that critical number of neighbors the cluster head as future work. (CNoN)in cluster and mobile networks is different from that in flat and stationary network.Due to mobility,the CNoN is d.Memoryless assumption the number of neighbors a node needs to maintain contact within a time period.And due to clustering,each cluster For both mobility models,we further make the following member only needs to maintain contact with the cluster heads. memoryless assumption.That is,all cluster-member nodes Hence,the CNoN is the number of neighbors a cluster member are memoryless about their past experience of the success or needs to check to see whether there is a cluster head. failure of sessions.Furthermore,all cluster-member nodes do not record the positions of any cluster-head nodes with which Definition 3.3:For mobile k-hop clustered networks,given they may have communicated.Thus,under this memoryless that the state of network is observed in the period A,o(n)is assumption,in each period,the distribution of head nodes is the critical number of neighbors if still uniform in the area of network,as seen by the member lim PA(E)=1,if o co(n)and c>1; nodes. lim PA(E)<,if c(n)and<1. 2)Stationary k-hop clustered networks:In a stationary k- hop clustered network,all nodes remain static after uniformly Definition 3.4:For stationary k-hop clustered networks, distributed in the unit area.As in its mobile counterpart,we also assume that the packet is forwarded for one hop in each (n)is the critical number of neighbors if time-slot. lim P(E)=1,if o>co(n)and c>1; n-o 3)Redefining connectivity in clustered networks:Due to lim P(E)<1,if o<c'o(n)and c'<1. 1→● clustering and mobility,the definition of connectivity in clus- tered networks is different from that in flat networks.For B.Main results and intuitions stationary k-hop clustered networks,we say that a cluster member is connected if it can reach a cluster head within We summarize our main results in this paper as follows: k hops.For mobile clustered networks,a cluster member is Under the random walk mobility assumption,the critical connected if it can reach a cluster head within k slots.If all transmission range isr(n)where dis the clus- the cluster members in a network are connected,we define ter head eponent,dminm e that the network has full connectivity. M).Note that v.is a function of n.(See Section II.B)

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 perfor￾mance, 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 trans￾mitted 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 k￾hop 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 clus￾tered 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 time￾slots, 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, if r ≤ c ′ r(n) for some c ′ < 1, For stationary networks, we define E to be the event that all cluster members are connected to a cluster head in k hops. Definition 3.2: For stationary k-hop clustered networks, r(n) is the critical transmission range if limn→∞ P(E) = 1, if r ≥ cr(n) and c > 1; limn→∞ P(E) < 1, if r ≤ c ′ r(n) and c ′ < 1. In parallel, we have the following definition for the critical number of neighbors. Note that critical number of neighbors (CNoN) in cluster and mobile networks is different from that in flat and stationary network. Due to mobility, the CNoN is the number of neighbors a node needs to maintain contact within a time period. And due to clustering, each cluster member only needs to maintain contact with the cluster heads. Hence, the CNoN is the number of neighbors a cluster member needs to check to see whether there is a cluster head. Definition 3.3: For mobile k-hop clustered networks, given that the state of network is observed in the period Λ, ϕ(n) is the critical number of neighbors if limn→∞ P Λ (E) = 1, if ϕ ≥ cϕ(n) and c > 1; limn→∞ P Λ (E) < 1, if ϕ ≤ c ′ϕ(n) and c ′ < 1. Definition 3.4: For stationary k-hop clustered networks, ϕ(n) is the critical number of neighbors if limn→∞ P(E) = 1, if ϕ ≥ cϕ(n) and c > 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 clus￾ter 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)

Under the i.i.d.mobility assumption,the critical trans- IV.THE CRITICAL TRANSMISSION RANGE FOR MOBILE mission range is√器，whee是<d≤l. K-HOP CLUSTERED NETWORKS,RANDOM WALK For stationary k-hop clustered networks,the critical trans- MOBILITY mission range is r(n)where We first define several key notations that will be For both mobile and stationary k-hop clustered networks, v(m+) O(nl-dlogn)neighbors are necessary and sufficient. used throughout this section.Let .=jos mim(g,Ym∈M,m,=arg min(mp-,vm∈M v(m) Before we prove these results rigorously,we now give an and pm.=p.,wherem)is the value of the discrete random intuitive approach to estimate the order of critical transmission variable V-the speed of cluster member.Recall that by our range in each scenario here: assumption,m.is independent of n when n is large while v. Suppose there are n cluster members and nd cluster heads is a function of n for all n.(See Section II.B)Also v,is not uniformly distributed in a unit square.Thus,roughly speaking, equal to v(m.),which can be easily seen from the definition there is one cluster head within an area of of v.. Under the random walk mobility assumption,the area In this section,we have the following main result. covered by movement during k time-slots constitutes the dominating part of a cluster member's coverage area. Theorem 4.1:Under the random walk mobility assumption, Assume that the velocities of nodes are uniformly a the critical transmission range is(n)where constant v.Thus,in order to reach a cluster head,on d<1. average we need Remark Recall the assumption thatm)) 1 1 logn 2kurm）=a,orrm）=2km with <Combined withr(n)it implies that (n)=o(nd-d).In other words,the speed is fast enough so 他U With certain transmission range,consider the number of that nodes can move multiple transmission ranges before the other nodes within the coverage of an arbitrary cluster deadline.Further,it is easy to verify that r(n)=o member during its movement in one period,we have nd- (n)=(n+n).2kr(n)=n1-d+1. A.Necessary condition on r(n)of Theorem 4.1 Under the i.i.d.mobility assumption,considering that We start with the following lemma. cluster members actually remain static during any time- slot,the coverage consists of the overall area of k disks. Thus,on average we need Lema:rr)=产，where<<he for any fixed1and)there exists No such that for all n>No,the following holds kπr2(n)= nd,or r(n)= n(-1+m)2nmm)≥e-李s,- Similarly,we have (1) (n）=(m+n4·krr2(n)=n1-d+1. where0<d≤l. Proof:Taking the logarithm of the left hand side of(1), .In the stationary networks,a reachable cluster head is we get roughly within a disk with a radius kr(n)of the cluster member,and thus we need log (L.H.S.of (1))=logn+ 2 rraP-点w间-g n41og(1-(1+(n)2km.r(m) (2) Similarly,we obtain Using the power series expansion for log(1-x), (n)=(n+n4·π(kr(n)2=n-d+1. log (L.H.S.of (1)) In the following,we will prove the necessary and sufficient (1+(n)2kmr(m)】》 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 sn-n(cmko)'+sa)e do zero if the critical transmission range is no greater than r(n). Similarly,for proofs of sufficient conditions,we will prove that where the probability of session failure (i.e.network disconnected) would approach 0 asymptotically. G(n,k,e(n))=(1+e(n))2kv(m.)r(n)

5 • Under the i.i.d. mobility assumption, the critical trans￾mission range is √ log n kπnd , where 1 k < d ≤ 1. • For stationary k-hop clustered networks, the critical trans￾mission 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 time￾slot, 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)