11 Like Proposition 4.1,Proposition 6.1 provides the necessary Figure 10.Let the radius of each disk R(n)be such that condition on r(n)in terms of both k(n)and do.The implica- R(n)=r(n).Then we evaluate the probability that tion behind this is the same as explained in Remark 4.2.We at least one disk does not have cluster heads,and we have can have the following corollary. Corollary6.1:r(m）≥is necessary for the connectivity of stationary k-hop clustered networks. B.Sufficient condition on r(n)of Theorem 6.1 Heuristically,we can use the tessellation-based approach to prove the sufficiency part of Theorem 6.1.However,it can also be shown that we cannot develop a sufficient condition on r(n) by directly applying the similar technique as in the previous proofs.The problem is that when<d 1,we cannot bound Fig.10. Disk tessellation of the unit torus the probability that at least one cell has no cluster heads to asymptotically approach zero,if the size of cell is roughly smaller than (kr(n)).On the other side,when the unit square is tessellated such that the size of cell is roughly equal P(fat least one disk does not have cluster heads}) to (kr(n)),we are also unable to show that any clustered 2 head within the distance of kr(n)is reachable for a cluster ≤2 2(ogn-1kr(n)) member.However,we can overcome this technical problem logn by the trick of considering a distance that is reachable for a and logn (logn -12 cluster member and approaches kr(n)as well. 2a0ogn-1pexp-（1ogn nax(kr(n))) First,we divide the unit square into cells with side length 2ogn-pnd(户 πlogn Thus,thereareog cells along the transmision range r(n).This tessellation is shown in Figure 9. →0.asn-→oo Therefore,r(n)is sufficient to guarantee the connectivity of network. log(n)cells the radius VII.THE CRITICAL NUMBER OF NEIGHBORS FOR CONNECTIVITY OF K-HOP CLUSTERED NETWORKS along t r(n) In this section,we briefly have a parallel discussion on connectivity under the number-of-neighbor-based connecting strategy.We show the critical number of neighbors (CNoN) in k-hop clustered networks for both stationary and mobile cases,respectively. Fig.9.There are log n cells along the transmission range r(n). A.The CNoN in stationary k-hop clustered networks Then we evaluate the probability that at least one cell is As we assumed before,n cluster members and nd cluster empty,and we have heads are uniformly and independently placed in the unit P(fat least one cell is empty}) square network.We denote by gatat(n,n)the network formed when each node is connected to its on nearest neigh- aknd logn(1- 2log nak2nd bors and we have the following result. s ik21ogn/n品-d 2 Theorem 7.1:For Gstat(n,on)to be asymptotically con- nected,(nl-dlogn)neighbors are necessary and sufficient. 0，asn→o. Proof: 1)the necessity part:We consider a disk Di which is Consequently,we know that with high probability there is at least one node in each cell.Then,with the transmission centered at a node with radius Hence.the range r(n),each hop can jump over at least (logn-1)cells. probability of the event that any other node falls into Di is Thus,any cluster head within the distance of()is reachable in k:hops with high probability.Now we have a p=mr2=dlogn k2nd￥ proper cell size to construct the main tessellation. Note that r is the critical transmission range for overall Next,we introduce the disk tessellation(with a minor abuse connectivity of a stationary k-hop clustered network,which is of the term tessellation)of the unit torus,as depicted in argued in Theorem 6.1.We then want to determine the number11 Like Proposition 4.1, Proposition 6.1 provides the necessary condition on r(n) in terms of both κ(n) and d0. The implica￾tion behind this is the same as explained in Remark 4.2. We can have the following corollary. Corollary 6.1: r(n) ≥ 1 k √d log n πnd is necessary for the connectivity of stationary k-hop clustered networks. B. Sufficient condition on r(n) of Theorem 6.1 Heuristically, we can use the tessellation-based approach to prove the sufficiency part of Theorem 6.1. However, it can also be shown that we cannot develop a sufficient condition on r(n) by directly applying the similar technique as in the previous proofs. The problem is that when 1 k < d ≤ 1, we cannot bound the probability that at least one cell has no cluster heads to asymptotically approach zero, if the size of cell is roughly smaller than π ( kr(n) )2 . On the other side, when the unit square is tessellated such that the size of cell is roughly equal to π ( kr(n) )2 , we are also unable to show that any clustered head within the distance of kr(n) is reachable for a cluster member. However, we can overcome this technical problem by the trick of considering a distance that is reachable for a cluster member and approaches kr(n) as well. √ First, we divide the unit square into cells with side length 2 2 r(n) log n . Thus, there are log n cells along the transmission range r(n). This tessellation is shown in Figure 9. ... ... ... ... XT RUMTIKRRY GRUTMZNKXGJO[Y Fig. 9. There are log n cells along the transmission range r(n). Then we evaluate the probability that at least one cell is empty, and we have P({at least one cell is empty}) ≤ 2 d πk2n d log n ( 1 − d 2 log nπk2nd )n ≤ 2 d πk2 log n / n d 2πk2 n1−d log2 n −d → 0, as n → ∞. Consequently, we know that with high probability there is at least one node in each cell. Then, with the transmission range r(n), each hop can jump over at least (log n − 1) cells. Thus, any cluster head within the distance of log n−1 log n kr(n) is reachable in k hops with high probability. Now we have a proper cell size to construct the main tessellation. Next, we introduce the disk tessellation (with a minor abuse of the term tessellation) of the unit torus, as depicted in Figure 10. Let the radius of each disk R(n) be such that R(n) = log n−1 log n kr(n). Then we evaluate the probability that at least one disk does not have cluster heads, and we have Fig. 10. Disk tessellation of the unit torus P({at least one disk does not have cluster heads}) ≤ 2 ( 1 2 ( log n−1 log n kr(n) ) )2( 1 − π (log n − 1 log n kr(n) )2 )n d ≤ πnd log n 2d(log n − 1)2 exp{−(log n − 1 log n )2 n dπ ( kr(n) )2 } ≤ π log n 2d(log n − 1)2 n d−d ( log n−1 log n )2 → 0, as n → ∞. Therefore, r(n) = 1 k √d log n πnd is sufficient to guarantee the connectivity of network. VII. THE CRITICAL NUMBER OF NEIGHBORS FOR CONNECTIVITY OF K-HOP CLUSTERED NETWORKS In this section, we briefly have a parallel discussion on connectivity under the number-of-neighbor-based connecting strategy. We show the critical number of neighbors (CNoN) in k-hop clustered networks for both stationary and mobile cases, respectively. A. The CNoN in stationary k-hop clustered networks As we assumed before, n cluster members and n d cluster heads are uniformly and independently placed in the unit square network. We denote by Gstat(n, ϕn) the network formed when each node is connected to its ϕn nearest neigh￾bors and we have the following result. Theorem 7.1: For Gstat(n, ϕn) to be asymptotically con￾nected, Θ ( n 1−d log n ) neighbors are necessary and sufficient. Proof: 1) the necessity part: We consider a disk Di which is centered at a node ni with radius r = 1 k √d log n πnd . Hence, the probability of the event that any other node falls into Di is p = πr2 = d log n k 2nd , Note that r is the critical transmission range for overall connectivity of a stationary k-hop clustered network, which is argued in Theorem 6.1. We then want to determine the number