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)