IEEE TRANSACTIONS ON AUTOMATIC CONTROL 9 3)Sufficient ESR for Full Coverage of Dense Grid:If ro= (b)Under 1-Dimensional Random Walk Mobility Model: c.logntloglogn where c>1,then Kn log n +log logn (21) ( Er.w. ≤∑P(F) n From the derivation of ESR under i.i.d.mobility model,we (nlogn can realize that i.i.d.mobility is actually quasi-static since y=1 the reshuffle of sensor positions does not increase the area of sensed region in a time slot compared with the stationary (nlogn)(1-kr(n))cwm case.The energy consumption Estat.in static WSNs equals y= that in WSNs with i.i.d model.In COROLLARY 5.1 of [9]. (nlogn)e-nz(ro)2 the author presented that in a static and homogeneous network under uniform deployment, (n log n)c2-→0asn→+o. cm)≥1+mp）+klog log((np log(np) Therefore,is sufficient to guarantee the full coverage of the dense grid M. is sufficient for an unit square to be asymptotically k-covered, 4)Further Discussion:If we only take the rectangular area where()三影高，op)=loo(mpand p is the the sensor covers when it moves into account(i.e.use P()to probability that a sensor is currently operating.By assuming replace P()),we can also prove the necessity and sufficiency p=1,k 1 and ignoring o(np)as noo,we translate this of to guarantee the full coverage of dense landmark result to our model.We obtain grid M using similar approach. nmr2 loglog n 1+ Thus we can conclude that when we consider the critical logn log n ESR for sensors under 1-dimensional random walk mobility, log n log log n the rectangular area the sensor covers when it moves contributes most for coverage rather than the circle area it covers when it πn is static which matches our results under i.i.d.mobility model,verifying 5)Critical ESR for Full Coverage of Operational Region: that Eii.d.=Eatat..Therefore,we obtain that Similar to the analysis in the i.i.d.mobility model,we can reach the following theorem. Em.=日 logn log logn .Estat. n Theorem 4.2:Under the uniform deployment scheme with which indicates that 1-dimensional random walk mobility mod- 1-dimensional random walk mobility model,the critical ESR el can decrease energy consumption in WSNs. for mobile heterogeneous WSNs to achieve asymptotic full coverage is Ro(n)=logn+loglogn However,this improvement in energy efficiency sacrifices Kn the timeliness of detection since under 1-dimensional random walk mobility model we evaluate the coverage performance D.The Impact of Mobility and Heterogeneity on Sensing of WSNs in a time slot r while in stationary WSNs full Energy Consumption coverage is maintained in any time instant.The delay to achieve full coverage is upper bounded by e(1).This is the We discuss the impact of mobility and heterogeneity on trade-off between energy consumption and delay of coverage sensing energy consumption based on the results obtained in in mobile WSNs.Practically,designers should also consider previous parts of this section. another possible source of energy consumption:agents motion. We used the sensing energy model as Er2.where E Sometimes sensors move by motors and wheels equipped on is the energy consumption of sensors with sensing radius ry. them,which must consume the electricity in the battery they Let E denote the average energy consumption of the mobile carry.As sensors keep moving in all time slots under both 1- heterogenous WSNs,thus E=c dimensional and 2-dimensional random walk mobility model, 1)Impact of Mobility:First,we consider the impact of energy consumption of this part should be of large quantity. mobility and sensors are assumed to have identical sensing However,the specific value of energy consumed depends main- radius,i.e.,ry r.or ry =ro(y 1,2,..,u)under i.i.d ly on the physical entity of the agents,and therefore is totally and 1-dimensional random walk mobility model,respectively. another topic which is beyond our scope.Otherwise,sensors We have the following results are fixed on moving vehicles or flyers and move passively with (a)Under I.I.D.Mobility Model: their "hosts".Energy consumption by motion needs not be discussed in these scenarios.Then designers can balance energy logn log log n consumption and delay of coverage by choosing sensors to be Ei.i.d.= (20)mobile or not.IEEE TRANSACTIONS ON AUTOMATIC CONTROL 9 3) Sufficient ESR for Full Coverage of Dense Grid: 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 − (1 + ζy)κry(n) cyn ≤ (n log n) u y=1  1 − κry(n) cyn ∼ (n log n)e−nπ(r)2 = 1 (n log n)c2−1 → 0 as n → +∞. Therefore, r ≥ log n+log log n κn is sufficient to guarantee the full coverage of the dense grid M. 4) Further Discussion: If we only take the rectangular area the sensor covers when it moves into account(i.e. use P(i,y,τ) to replace P(i,y)), we can also prove the necessity and sufficiency of r ≥ log n+log log n κn to guarantee the full coverage of dense grid M using similar approach. Thus we can conclude that when we consider the critical ESR for sensors under 1-dimensional random walk mobility, the rectangular area the sensor covers when it moves contributes most for coverage rather than the circle area it covers when it is static. 5) Critical ESR for Full Coverage of Operational Region: Similar to the analysis in the i.i.d. mobility model, we can reach the following theorem. Theorem 4.2: Under the uniform deployment scheme with 1-dimensional random walk mobility model, the critical ESR for mobile heterogeneous WSNs to achieve asymptotic full coverage is R(n) = log n+log log n κn . D. The Impact of Mobility and Heterogeneity on Sensing Energy Consumption We discuss the impact of mobility and heterogeneity on sensing energy consumption based on the results obtained in previous parts of this section. We used the sensing energy model as Ey ∝ r2 y, where Ey is the energy consumption of sensors with sensing radius ry. Let E denote the average energy consumption of the mobile heterogenous WSNs , thus E ∝ u y=1 cyr2 y. 1) Impact of Mobility: First, we consider the impact of mobility and sensors are assumed to have identical sensing radius, i.e., ry = r or ry = r(y = 1, 2, ··· , u) under i.i.d and 1-dimensional random walk mobility model, respectively. We have the following results (a) Under I.I.D. Mobility Model: Ei.i.d. = Θ log n + log log n n . (20) (b) Under 1-Dimensional Random Walk Mobility Model: Er.w. = Θ log n + log log n n 2  . (21) From the derivation of ESR under i.i.d. mobility model, we can realize that i.i.d. mobility is actually quasi-static since the reshuffle of sensor positions does not increase the area of sensed region in a time slot compared with the stationary case. The energy consumption Estat. in static WSNs equals that in WSNs with i.i.d model. In COROLLARY 5.1 of [9], the author presented that in a static and homogeneous network under uniform deployment, c(n) ≥ 1 + φ(np) + k log log(np) log(np) is sufficient for an unit square to be asymptotically k-covered, where c(n) = npπr2 log(np) , φ(np) = o(log log(np)) and p is the probability that a sensor is currently operating. By assuming p = 1, k = 1 and ignoring φ(np) as n → ∞, we translate this landmark result to our model. We obtain nπr2 log n ≥ 1 + log log n log n r ≥ log n + log log n πn which matches our results under i.i.d. mobility model, verifying that Ei.i.d. = Estat.. Therefore, we obtain that Er.w. = Θ log n + log log n n · Estat., which indicates that 1-dimensional random walk mobility mod￾el can decrease energy consumption in WSNs. However, this improvement in energy efficiency sacrifices the timeliness of detection since under 1-dimensional random walk mobility model we evaluate the coverage performance of WSNs in a time slot τ while in stationary WSNs full coverage is maintained in any time instant. The delay to achieve full coverage is upper bounded by Θ(1). This is the trade-off between energy consumption and delay of coverage in mobile WSNs. Practically, designers should also consider another possible source of energy consumption: agents motion. Sometimes sensors move by motors and wheels equipped on them, which must consume the electricity in the battery they carry. As sensors keep moving in all time slots under both 1- dimensional and 2-dimensional random walk mobility model, energy consumption of this part should be of large quantity. However, the specific value of energy consumed depends main￾ly on the physical entity of the agents, and therefore is totally another topic which is beyond our scope. Otherwise, sensors are fixed on moving vehicles or flyers and move passively with their ”hosts”. Energy consumption by motion needs not be discussed in these scenarios. Then designers can balance energy consumption and delay of coverage by choosing sensors to be mobile or not.