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.Although3 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