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)