IEEE TRANSACTIONS ON AUTOMATIC CONTROL 6 for all n>Ne. 2)Sufficient ESR for Full Coverage of Dense Grid:Let Fi Let s(n)=mr2(n)and s,(n)=rr2(n),then s,(n)=denote the event that point P in M is not covered.If r. ∑-=19ys,l(m)）=ogn+o贤o8nt.Hence for ally= cgn where c1,then l,2,…,u,s,(n)=日(logn+loglog n+）which indicates that sy(n)and s(n)(cun)approach 0 as n+oo.From Lemma 4.1,we obtain that for arbitrary positive constant a, (1-asy(n))cun~e-an(cs(n)) (5) ≤(nlogn))Ⅱ(1-r子m)n =1 Thus,for two points Pi and P in M,we obtain that (nlogn)e-nx(r.)2 P({P:and P;are not covered)) (nlog n)e2-I' ≥Π(1-4πr(m)(1-2πrm)” For any c 1,we then have the following result =1 e-2n∑-1(cgsv(m) 6 )=0. and on the other hand,we have the upper bound i=】 P({P;and Pj are not covered)) Therefore,r,≥Vy logn+loglogn is sufficient to guarantee the n full coverage of the dense grid. 2ri(n))cvn y=1 3)Critical ESR for Full Coverage of Operational Region: e-2n∑#-1(cgsv(n) (7) The density of the dense grid m =n logn is sufficiently large to evaluate the coverage problem of the whole operational From (6)and (7),we know that region.Referring to LEMMA 3.1 in [9]and using similar approach as THEOREM 4.1 in [9],we can demonstrate that P({Band乃are not covered))e-2n∑y-i(c,s,(). (8) .is sufficient to achieve the full coverage T Then the following result holds of the whole operational region.On the other hand,points in M constitute a subregion of the operational region,which indicates P≠P that the necessary condition for the dense grid is surely the P({P;and P;are not covered) necessary condition for the whole operational region. P,P∈M Hence,we have the following theorem m2e-2n∑g-1(cysv(mj0 Theorem 4.1:Under the uniform deployment scheme with (nlogn)2e-2ns.(n) i.i.d.mobility model,the critical ESR for mobile heteroge- =(nlog n)2e-2(log n+log logn+e) neous WSNs to achieve asymptotic full coverage is R.(n)= =e-25 (9) /log n+loglog n Using (4)and (9)into (2).we have C.Critical ESR Under 1-Dimensional Random Walk Mobility P(g)≥9e-<-e-2. (10)Model for any 1. Under the 1-dimensional random walk mobility model,the As for the case that is a function of n with sensing process is slotted and sensors make use of each time limn-→+oes(n),we know(n）)≤ξ+&for any 6>0all slot to move and sense.We use gr to denote the event that n N5.Since P(C)is monotonously decreasing in r.and M is covered in a given time slot r.and Pr(g)to denote the thus in 6,we have corresponding probability.Similarly,we define the critical ESR for 1-dimensional random walk model. P(©)≥0e-(+)-e-2(+) (11) Definition 4.2:For mobile heterogeneous WSNs with 1- for all n Ne.6.Then the result follows. ■ dimensional random walk mobility model,r(n)is the critical equivalent sensing radius for the dense grid if From Proposition 4.1,P(G)is bounded away from zero with positive probability if lim→+oξ(n）<+oo.Combined with limP,(g)=1,ifr。≥cro(m)for any c>l; 刀+0d Deinition4.L,we know thatr.≥√sn+Hsos亚is necessar时y n limP,(g)<l,ifr。≤cro(n)for any0<c<1. n+00 to achieve the full coverage of the dense grid M.IEEE TRANSACTIONS ON AUTOMATIC CONTROL 6 for all n>Nξ. Let sy(n) = πr2 y(n) and s(n) = πr2 (n), then s(n) = u y=1 cysy(n) = log n+log log n+ξ n . Hence for all y = 1, 2, ··· , u, sy(n)=Θ log n+log log n+ξ n which indicates that sy(n) and s2 y(n)(cyn) approach 0 as n → +∞. From Lemma 4.1, we obtain that for arbitrary positive constant α, (1 − αsy(n))cyn ∼ e−αn(cysy(n)). (5) Thus, for two points Pi and Pj in M, we obtain that P({Pi and Pj are not covered}) ≥ u y=1  1 − 4πr2 y(n) 1 − 2πr2 y(n) cyn ∼ e−2nu y=1(cysy(n)). (6) and on the other hand, we have the upper bound P({Pi and Pj are not covered}) ≤ u y=1 πr2 y(n)  1 − πr2 y(n) cyn + u y=1  1 − 2πr2 y(n) cyn ∼ e−2nu y=1(cysy(n)). (7) From (6) and (7), we know that P({Pi and Pj are not covered}) ∼ e−2nu y=1(cysy(n)). (8) Then the following result holds P i=Pj Pi,Pj∈M P({Pi and Pj are not covered}) ∼ m2e−2nu y=1(cysy(n)) = (n log n) 2 e−2ns(n) = (n log n) 2 e−2(log n+log log n+ξ) = e−2ξ. (9) Using (4) and (9) into (2), we have P(G) ≥ θe−ξ − e−2ξ. (10) for any θ < 1. As for the case that ξ is a function of n with ξ = limn→+∞ ξ(n), we know ξ(n) ≤ ξ + δ for any δ > 0 all n>Nδ. Since P(G) is monotonously decreasing in r and thus in ξ, we have P(G) ≥ θe−(ξ+δ) − e−2(ξ+δ) , (11) for all n>Nθ,δ. Then the result follows. From Proposition 4.1, P(G) is bounded away from zero with positive probability if limn→+∞ ξ(n) < +∞. Combined with Definition 4.1, we know that r ≥ log n+log log n πn is necessary to achieve the full coverage of the dense grid M. 2) Sufficient ESR for Full Coverage of Dense Grid: Let Fi denote the event that point Pi in M is not covered. If r = c log n+log log n πn where c > 1, then P  m i=1 Fi ≤ m i=1 P(Fi) ≤ (n log n) u y=1  1 − πr2 y(n) cyn ∼ (n log n)e−nπ(r)2 = 1 (n log n)c2−1 . For any c > 1, we then have the following result lim n→+∞ P  m i=1 Fi = 0. Therefore, r ≥ log n+log log n πn is sufficient to guarantee the full coverage of the dense grid. 3) Critical ESR for Full Coverage of Operational Region: The density of the dense grid m = n log n is sufficiently large to evaluate the coverage problem of the whole operational region. Referring to LEMMA 3.1 in [9] and using similar approach as THEOREM 4.1 in [9], we can demonstrate that r ≥ log n+log log n πn is sufficient to achieve the full coverage of the whole operational region. On the other hand, points in M constitute a subregion of the operational region, which indicates that the necessary condition for the dense grid is surely the necessary condition for the whole operational region. Hence, we have the following theorem Theorem 4.1: Under the uniform deployment scheme with i.i.d. mobility model, the critical ESR for mobile heteroge-  neous WSNs to achieve asymptotic full coverage is R(n) = log n+log log n πn . C. Critical ESR Under 1-Dimensional Random Walk Mobility Model Under the 1-dimensional random walk mobility model, the sensing process is slotted and sensors make use of each time slot to move and sense. We use Gτ to denote the event that M is covered in a given time slot τ , and Pτ (Gτ ) to denote the corresponding probability. Similarly, we define the critical ESR for 1-dimensional random walk model. Definition 4.2: For mobile heterogeneous WSNs with 1- dimensional random walk mobility model, r(n) is the critical equivalent sensing radius for the dense grid if limn→∞ Pτ (Gτ )=1, if r ≥ cr(n) for any c > 1; limn→∞ Pτ (Gτ ) < 1, if r ≤ crˆ (n) for any 0 < c <ˆ 1.