IEEE TRANSACTIONS ON AUTOMATIC CONTROL 7 1)Failure Probability of a Point in M:We use Fi to denote Then,we can have the p.d.f.of G and H the event that point Pi in M is not covered by any sensor and use P(F)to denote the probability that point P in M is not fc(g)= 2 0≤g≤： covered. 0, otherwise. We first consider the probability that an arbitrary point Pi in M can be successfully covered by a sensor Xy in group G.and denote the probability as P()When sensor moves 2(1-h),0≤h≤1： fH(h)= under 1-dimensional random walk mobility,it can cover more 0, otherwise. space (a rectangular of size ryx D)during a time slot T than stationary condition,thus increasing P(iy).For P(i)we have Point Pi can be successfully covered by Xy if and only if Xy P(a,y)=πr号+P(a,y,)wherer号denotes the probability that can enter the circle with radius ry centered at Pi.For P() can coverPwhen it is stationary.and P)denotes the probability that Xy can cover P considering its mobility.In the following part,we first derive P(i and then obtain P(i) P,)=P(G≤r)-P(H≤D) as well as P(Fi). Because of the symmetry of the topology,we only need to (2r)2(1-h)dhdd kry.(12) = take into account the case that X moves horizontally. Here=2(1-h)dhdd is a constant if fD(d)is known. P在，)=Tr号+P(,,)=πr+Ty (13) Before we derive the critical ESR,firstly we would like to derive the range of do.to promise P()together with P() H a point in the nonzero.For K,we have dense grid a right moving K= 2(1-h)dhdd H-sensor fD(d)2(1-h)dhdd 0 1 0 (2d-d2)fp(d)dd 4 Fig.4.Coverage of a Single Point. According to this integration,if fp(d)is independent of d (uniform deployment as an example),the necessary condition Since Xu chooses to move left or right with equal probability. for P(i.v.)to be nonzero is we suppose X moves right.Initially,sensors are uniformly deployed and according to the 1-dimensional random walk mobility model,sensors are always uniformly distributed at f广2d-rad do each time slot r in the operational region seen by the points in -36+2 M.On the other hand,the dense grid is randomly and uniformly 3 located in the operational region. (d0-1)d-1+V3-1-③>0 We build a Cartesian coordinate system in the operational 3 region and denote the position of Xy and P with (u1,v1) and (u2,v2),respectively.Then we know that u,v1,u2,v are Thus we get 0<do<1. uniformly distributed from 0 to 1. For cases when fp(d)is a function of d.intuitively,if 0< Since Xy does not move vertically,when considering the do <1,the sensor always has the chance to move long enough vertical distance between Xy and P which is denoted as to cover the point i in one step,since the maximum distance in G.we should recognize the fact that the upper boundary the operational region is 1,which promises the necessity that of the operational region is adjacent to the lower boundary P(i,y.r）is nonzero. (considering the operational region is a torus).Hence,we have Therefore 0<do<1 is necessary for P(i.)to be nonzero G=min{lv-v2l,1-v1-v2l}.However,on the horizontal in one move or a fixed number of moves,since P(i.)>P(i.v.) dimension,Xy moves in certain direction and might sense Pi on and P(F)can be calculated according to the distribution of D. its way,which leads the horizontal distance to be H=.IEEE TRANSACTIONS ON AUTOMATIC CONTROL 7 1) Failure Probability of a Point in M: We use Fi to denote the event that point Pi in M is not covered by any sensor and use P(Fi) to denote the probability that point Pi in M is not covered. We first consider the probability that an arbitrary point Pi in M can be successfully covered by a sensor Xy in group Gy, and denote the probability as P(i,y). When sensor moves under 1-dimensional random walk mobility, it can cover more space (a rectangular of size ry × D ) during a time slot τ than stationary condition, thus increasing P(i,y). For P(i,y) we have P(i,y) = πr2 y + P(i,y,τ), where πr2 y denotes the probability that Xy can cover Pi when it is stationary, and P(i,y,τ) denotes the probability that Xy can cover Pi considering its mobility. In the following part, we first derive P(i,y,τ) and then obtain P(i,y) as well as P(Fi). Because of the symmetry of the topology, we only need to take into account the case that Xy moves horizontally. H D a right moving H-sensor a point in the dense grid ry v u G Fig. 4. Coverage of a Single Point. Since Xy chooses to move left or right with equal probability, we suppose Xy moves right. Initially, sensors are uniformly deployed and according to the 1-dimensional random walk mobility model, sensors are always uniformly distributed at each time slot τ in the operational region seen by the points in M. On the other hand, the dense grid is randomly and uniformly located in the operational region. We build a Cartesian coordinate system in the operational region and denote the position of Xy and Pi with (u1, v1) and (u2, v2), respectively. Then we know that u1, v1, u2, v1 are uniformly distributed from 0 to 1. Since Xy does not move vertically, when considering the vertical distance between Xy and Pi which is denoted as G, we should recognize the fact that the upper boundary of the operational region is adjacent to the lower boundary (considering the operational region is a torus). Hence, we have G = min{|v1 − v2|, 1 − |v1 − v2|}. However, on the horizontal dimension, Xy moves in certain direction and might sense Pi on its way, which leads the horizontal distance to be H = |u1−u2|. Then, we can have the p.d.f. of G and H fG(g) =  2, 0 ≤ g ≤ 1 2 ; 0, otherwise. fH(h) =  2(1 − h), 0 ≤ h ≤ 1; 0, otherwise. Point Pi can be successfully covered by Xy if and only if Xy can enter the circle with radius ry centered at Pi. For P(i,y), P(i,y,τ) = P(G ≤ ry) · P(H ≤ D) = (2ry)   h≤d 2(1 − h)dhdd = κry. (12) Here κ =  h≤d 2(1−h)dhdd is a constant if fD(d) is known. P(i,y) = πr2 y + P(i,y,τ) = πr2 y + κry (13) Before we derive the critical ESR, firstly we would like to derive the range of d0, to promise P(i,y) together with P(i,y,τ) nonzero. For κ, we have κ =   h≤d 2(1 − h)dhdd =  1 d0 fD(d)  d 0 2(1 − h)dhdd =  1 d0 (2d − d2)fD(d)dd According to this integration, if fD(d) is independent of d (uniform deployment as an example), the necessary condition for P(i,y,τ) to be nonzero is  1 d0 (2d − d2)dd = d3 0 − 3d2 0 + 2 3 = (d0 − 1)(d0 − 1 + √3)(d0 − 1 − √3) 3 > 0 Thus we get 0 < d0 < 1 . For cases when fD(d) is a function of d, intuitively, if 0 < d0 < 1, the sensor always has the chance to move long enough to cover the point i in one step, since the maximum distance in the operational region is 1, which promises the necessity that P(i,y,τ) is nonzero. Therefore 0 < d0 < 1 is necessary for P(i,y) to be nonzero in one move or a fixed number of moves, since P(i,y) > P(i,y,τ) and P(Fi) can be calculated according to the distribution of D