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 that1 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) )