Coverage and Energy Consumption Control in Mobile Heterogeneous Wireless Sensor Networks

IEEE TRANSACTIONS ON AUTOMATIC CONTROL Coverage and Energy Consumption Control in Mobile Heterogeneous Wireless Sensor Networks Xinbing Wang,Senior Member;IEEE,Sihui Han,Yibo Wu,and Xiao Wang Abstract-In this paper we investigate the coverage and parameter(s),e.g.the sensing range of sensors.By adjusting the energy consumption control in mobile heterogeneous wireless sensing range,designer can deploy WSNs with proper coverage sensor networks (WSNs).By term heterogeneous,we mean that capability.Often,quantifiable relation between coverage and sensors in the network have various sensing radius,which is an inherent property of many applied WSNs.Two sensor deployment the parameter(s)is established for better analysis.We can know schemes are considered -uniform and Poisson schemes.We study accurately from the results how the parameter(s)impact the the asymptotic coverage under uniform deployment scheme with network performance. i.i.d.and 1-dimensional random walk mobility model,respectively. We propose the equivalent sensing radius (ESR)for both cases Initially,stationary and flat WSNs received most attention in and derive the critical ESR correspondingly.Our results show the coverage study.By the term flat,we mean that sensors in that the network performance largely depends on ESR.By the network have identical sensing radius.In [21],Clouqueur controlling ESR,we can always promise the network achieve studied the sensor deployment strategy to improve the coverage full coverage,regardless of the total number of sensors or the performance of sensor network and proposed path exposure to sensing radius of a single senor under random mobility patterns, measure the performance.Shakkottai [22]took into account the which is a much easier and more general way to operate coverage control.Meanwhile,we can operate a tradeoff control between failure probability of sensors and obtained the necessary and coverage performance and energy consumption by adjusting ESR. sufficient conditions for a sensor grid to achieve asymptotic We demonstrate that 1-dimensional random walk mobility can full coverage.In [23].Liu defined three coverage performance decrease the sensing energy consumption under certain delay measures and characterized asymptotic behavior of these mea- tolerance,though requires larger ESR.Also,we characterize the role of heterogeneity in coverage and energy performance of WSNs sures.In [36]and [37],WSNs are also well studied and give under these two mobility models,and present the discrepancy of us great insights. the impact of heterogeneity under different models.Under the Poisson deployment scheme,we investigate dynamic k-coverage The 1-coverage studied in literature mentioned above is not of WSNs with 2-dimensional random walk mobility model.We satisfactory in many applications and high degree of coverage present the relation between network coverage and the sensing is consequently demanded (cf.[9]for the reasons to require range,which indicates how coverage varies according to sensing k-coverage rather than just 1-coverage).Kumar [9]studied capability.Both k-coverage at an instant and over a time interval asymptotic k-coverage in a mostly sleeping stationary sensor are explored and we derive the expectation of fraction of the network and found the coverage highly depend on the value whole operational region that is k-covered,which also identifies the coverage improvement brought by mobility. of the function (n is the number of sensors and p is the probability that a sensor is active).The sufficient value of Index Terms-Coverage control,mobility,heterogeneity,energy consumption control,scaling law. 藏me r to achieve full coverage.Another related topic is the approach I.INTRODUCTION to guarantee both coverage and connectivity of WSNs.In [10]. Wile ne ot erch moe wh gaion Bai and Xuan proposed deployment schemes to achieve full coverage and k-connectivity.And a new deployment-polygon on coverage is a fundamental one.The coverage of WSNs based methodology was introduced to prove the optimality of is of significance in many applications such as the security proposed deployment patterns. surveillance in estates,intrusion detection in battle-field or One common feature of the above papers is that they all military restricted zone,etc. study static WSNs.Sensor mobility is actually a concern in In this paper,we focus on the blanker coverage or area coverage study.Plenty of related works concentrate on refining coverage,which concentrates on the maximization of detection algorithm to reposition and control sensors to improve coverage rate of targets in the sensing field.The operational region is said [11][20][30].In this sense,mobility is exploited to reconfigure to be fully blanket covered if every single point in the region is the topology of the network.One commonly used approach sensed.The past decade has seen a surge of research activities for coverage control is developing Voronoi-based algorithm. on coverage.Normally,the coverage and energy consumption performance of WSNs are toned by one or several vital network In [32],Wang et al.proposed three movement protocols for sensors to fill the coverage hole based on the Voronoi approach. IThe early version of this paper appeared in the Proceedings of IEEE In [28],the authors optimized coverage performance with ICDCS'11 [31. sensors of limited mobility.In [35],the authors considered

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 1 Coverage and Energy Consumption Control in Mobile Heterogeneous Wireless Sensor Networks Xinbing Wang, Senior Member, IEEE, Sihui Han, Yibo Wu, and Xiao Wang Abstract—In this paper 1 , we investigate the coverage and energy consumption control in mobile heterogeneous wireless sensor networks (WSNs). By term heterogeneous, we mean that sensors in the network have various sensing radius, which is an inherent property of many applied WSNs. Two sensor deployment schemes are considered –uniform and Poisson schemes. We study the asymptotic coverage under uniform deployment scheme with i.i.d. and 1-dimensional random walk mobility model, respectively. We propose the equivalent sensing radius (ESR) for both cases and derive the critical ESR correspondingly. Our results show that the network performance largely depends on ESR. By controlling ESR, we can always promise the network achieve full coverage, regardless of the total number of sensors or the sensing radius of a single senor under random mobility patterns, which is a much easier and more general way to operate coverage control. Meanwhile, we can operate a tradeoff control between coverage performance and energy consumption by adjusting ESR. We demonstrate that 1-dimensional random walk mobility can decrease the sensing energy consumption under certain delay tolerance, though requires larger ESR. Also, we characterize the role of heterogeneity in coverage and energy performance of WSNs under these two mobility models, and present the discrepancy of the impact of heterogeneity under different models. Under the Poisson deployment scheme, we investigate dynamic k-coverage of WSNs with 2-dimensional random walk mobility model. We present the relation between network coverage and the sensing range, which indicates how coverage varies according to sensing capability. Both k-coverage at an instant and over a time interval are explored and we derive the expectation of fraction of the whole operational region that is k-covered, which also identifies the coverage improvement brought by mobility. Index Terms—Coverage control, mobility, heterogeneity, energy consumption control, scaling law. I. INTRODUCTION WIRELESS Sensor Networks (WSNs) have inspired a wide range of research, among which investigation on coverage is a fundamental one. The coverage of WSNs is of significance in many applications such as the security surveillance in estates, intrusion detection in battle-field or military restricted zone, etc. In this paper, we focus on the blanket coverage or area coverage, which concentrates on the maximization of detection rate of targets in the sensing field. The operational region is said to be fully blanket covered if every single point in the region is sensed. The past decade has seen a surge of research activities on coverage. Normally, the coverage and energy consumption performance of WSNs are toned by one or several vital network 1The early version of this paper appeared in the Proceedings of IEEE ICDCS’11 [3]. parameter(s), e.g. the sensing range of sensors. By adjusting the sensing range, designer can deploy WSNs with proper coverage capability. Often, quantifiable relation between coverage and the parameter(s) is established for better analysis. We can know accurately from the results how the parameter(s) impact the network performance. Initially, stationary and flat WSNs received most attention in the coverage study. By the term flat, we mean that sensors in the network have identical sensing radius. In [21], Clouqueur studied the sensor deployment strategy to improve the coverage performance of sensor network and proposed path exposure to measure the performance. Shakkottai [22] took into account the failure probability of sensors and obtained the necessary and sufficient conditions for a sensor grid to achieve asymptotic full coverage. In [23], Liu defined three coverage performance measures and characterized asymptotic behavior of these mea￾sures. In [36] and [37], WSNs are also well studied and give us great insights. The 1-coverage studied in literature mentioned above is not satisfactory in many applications and high degree of coverage is consequently demanded (cf. [9] for the reasons to require k-coverage rather than just 1-coverage). Kumar [9] studied asymptotic k-coverage in a mostly sleeping stationary sensor network and found the coverage highly depend on the value of the function npπr2 log(np) (n is the number of sensors and p is the probability that a sensor is active). The sufficient value of npπr2 log(np) to ensure full coverage was derived under three different deployment model. Hence, the WSNs can take proper value of r to achieve full coverage. Another related topic is the approach to guarantee both coverage and connectivity of WSNs. In [10], Bai and Xuan proposed deployment schemes to achieve full coverage and k-connectivity. And a new deployment-polygon based methodology was introduced to prove the optimality of proposed deployment patterns. One common feature of the above papers is that they all study static WSNs. Sensor mobility is actually a concern in coverage study. Plenty of related works concentrate on refining algorithm to reposition and control sensors to improve coverage [11][20][30]. In this sense, mobility is exploited to reconfigure the topology of the network. One commonly used approach for coverage control is developing Voronoi-based algorithm. In [32], Wang et al. proposed three movement protocols for sensors to fill the coverage hole based on the Voronoi approach. In [28], the authors optimized coverage performance with sensors of limited mobility. In [35], the authors considered

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2 coverage control for mobile sensing networks under controlled better balance between performance and cost of sensors if deployment.Other three extensions concerning the location opportune degree of heterogeneity is incorporated into the optimization of heterogeneous sensors were developed in [29], network by employing high-end and low-end sensors with based on a framework for optimized quantization derived in different sensing capabilities [18].Actually,due to various In [35].On the other hand,in [4],Liu studied dynamic underlying reasons,sensors in WSNs are more likely to have coverage which considered the coverage of sensors during their different sensing radii.One scenario is that sensors in WSNs movement.The work demonstrated how to maintain various are products coming from different manufacturers and there fractions of covered area by adjusting sensing range and sensor is no uniform standard on the sensing range.Plus,sensors velocity in the movement.Coverage over a time interval was deployed in different times may also lead to heterogeneity of also explored,which distinguished the work. the network.And as the service lifetime passes by,degradation These previous works on coverage control mainly focus of sensing capability may be inevitable.Hence,heterogeneity on the controlled movements.From our perspective,how- is an inherent property of many WSNs,which deserves our ever,random mobility has its own advantage and practical attention. meaning.Under random mobility patterns,we can operate We partition sensors into groups based on the sensing the coverage and sensing energy consumption control in a radius.The equivalent sensing radius (ESR)of the mobile simpler and more general way.We only need to control the heterogeneous WSNs will be defined to assist the analysis. equivalent sensing radius (ESR)of the network to promise the The results demonstrate that full coverage of the operational full coverage performance.We can also carry out a flexible region largely depends on the value of ESR,and so does the tradeoff control between coverage performance and sensing energy consumption.By controlling ESR.WSNs may achieve energy consumption,by changing ESR,regardless of the total full coverage.In the study,we concentrate on how mobility number of sensors or the sensing radius of a single senor. and heterogeneity together influence the WSN performance.We In this sense,random mobility patterns provide us a way to derive the critical(necessary and sufficient)ESR in stationary achieve coverage and sensing energy consumption control with flat WSNs and mobile heterogeneous WSNs,respectively.The no need of communication or cooperation between sensors, value of critical ESR can help evaluate the overhead for the which is needed for controlled movements and results in much WSN to achieve full coverage.The advantages and drawbacks overhead.Since random mobility patterns can save the energy brought by mobility and heterogeneity are analyzed based on used to collect and deal with information,it can relatively the results.The trade-offs between coverage and delay,sensing prolong the lifetime of the whole network and requires less energy consumption and cost of sensors will be presented to complex equipments as well.Furthermore,in some cases,the provide insights on WSNs design. sensors or their mobile hosts cannot communicate with each Our main contributions are presented as below: other due to nature or human factors,making it difficult to Under the uniform deployment scheme,we study asymp- collect information from neighborhood and decide where to totic coverage of heterogeneous WSNs with the i.i.d move,or their purpose is simply to monitor the area without mobility model and 1-dimensional random walk mobility any specific target (i.e.they have no destinations in their mind). model.We define ESR of WSNs and analyze network per- As a result,the controlled motion as well as the corresponding formance using this metric.We obtain the critical value of methods can't be applied.Another reason for considering ESR for the WSNs to achieve asymptotic full coverage of random model is that studying random mobility can provide the operational region.We demonstrate that 1-dimensional basic guidelines for other more complicated models,including random walk mobility reduces the energy consumption controlled ones,as it can give us an outlook of the impact of by the order 2 at the expense of (1) mobility for coverage in a relatively clear way.By calculating delay: the energy consumption under random walk mobility,we have Under the uniform deployment scheme,heterogeneity is demonstrated the benefits for coverage performance brought shown to impose no impact on energy consumption in by mobility,promising the worthiness of developing controlled stationary WSNs or WSNs with i.i.d.mobility model but algorithms for sensor movements. to 'slightly'increase sensing energy consumption in WSNs In this paper,we investigate the coverage as well as the with the 1-dimensional random walk model; sensing energy consumption property in WSNs that are both We study the WSNs under Poisson deployment strategy mobile and heterogeneous.Although the sensing energy con- with the 2-dimensional random walk mobility model and sumption is much less than the energy consumption due to derive the expectation of the fraction of operational region communication among sensors,the former should be a concern that is k-covered by the heterogeneous WSNs at an instant in energy-efficient WSN design,since continuous sensing is usually the case in applications while the connection between 2The following asymptotic notations are used throughout this paper.Given sensors is not required all the time.In literature,mobility has non-negative functions f(n)and g(n): been proved to enhance various aspects of network performance 1)f(n)=e(g(n))means that for two constants 0<e1<c2,cig(n)< [14].[15],[17],and many applied WSNs are actually inherently f(n）≤c2g(n)for sufficiently large n. mobile [6].Meanwhile,it has been found that WSNs achieve 2)jm）gtm）means that m+e8=1

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2 coverage control for mobile sensing networks under controlled deployment. Other three extensions concerning the location optimization of heterogeneous sensors were developed in [29], based on a framework for optimized quantization derived in In [35]. On the other hand, in [4], Liu studied dynamic coverage which considered the coverage of sensors during their movement. The work demonstrated how to maintain various fractions of covered area by adjusting sensing range and sensor velocity in the movement. Coverage over a time interval was also explored, which distinguished the work. These previous works on coverage control mainly focus on the controlled movements. From our perspective, how￾ever, random mobility has its own advantage and practical meaning. Under random mobility patterns, we can operate the coverage and sensing energy consumption control in a simpler and more general way. We only need to control the equivalent sensing radius (ESR) of the network to promise the full coverage performance. We can also carry out a flexible tradeoff control between coverage performance and sensing energy consumption, by changing ESR, regardless of the total number of sensors or the sensing radius of a single senor. In this sense, random mobility patterns provide us a way to achieve coverage and sensing energy consumption control with no need of communication or cooperation between sensors, which is needed for controlled movements and results in much overhead. Since random mobility patterns can save the energy used to collect and deal with information, it can relatively prolong the lifetime of the whole network and requires less complex equipments as well. Furthermore, in some cases, the sensors or their mobile hosts cannot communicate with each other due to nature or human factors, making it difficult to collect information from neighborhood and decide where to move, or their purpose is simply to monitor the area without any specific target (i.e. they have no destinations in their mind). As a result, the controlled motion as well as the corresponding methods can’t be applied. Another reason for considering random model is that studying random mobility can provide basic guidelines for other more complicated models, including controlled ones, as it can give us an outlook of the impact of mobility for coverage in a relatively clear way. By calculating the energy consumption under random walk mobility, we have demonstrated the benefits for coverage performance brought by mobility, promising the worthiness of developing controlled algorithms for sensor movements. In this paper, we investigate the coverage as well as the sensing energy consumption property in WSNs that are both mobile and heterogeneous. Although the sensing energy con￾sumption is much less than the energy consumption due to communication among sensors, the former should be a concern in energy-efficient WSN design, since continuous sensing is usually the case in applications while the connection between sensors is not required all the time. In literature, mobility has been proved to enhance various aspects of network performance [14], [15], [17], and many applied WSNs are actually inherently mobile [6]. Meanwhile, it has been found that WSNs achieve better balance between performance and cost of sensors if opportune degree of heterogeneity is incorporated into the network by employing high-end and low-end sensors with different sensing capabilities [18]. Actually, due to various underlying reasons, sensors in WSNs are more likely to have different sensing radii. One scenario is that sensors in WSNs are products coming from different manufacturers and there is no uniform standard on the sensing range. Plus, sensors deployed in different times may also lead to heterogeneity of the network. And as the service lifetime passes by, degradation of sensing capability may be inevitable. Hence, heterogeneity is an inherent property of many WSNs, which deserves our attention. We partition sensors into groups based on the sensing radius. The equivalent sensing radius (ESR) of the mobile heterogeneous WSNs will be defined to assist the analysis. The results demonstrate that full coverage of the operational region largely depends on the value of ESR, and so does the energy consumption. By controlling ESR, WSNs may achieve full coverage. In the study, we concentrate on how mobility and heterogeneity together influence the WSN performance. We derive the critical (necessary and sufficient) ESR in stationary flat WSNs and mobile heterogeneous WSNs, respectively. The value of critical ESR can help evaluate the overhead for the WSN to achieve full coverage. The advantages and drawbacks brought by mobility and heterogeneity are analyzed based on the results. The trade-offs between coverage and delay, sensing energy consumption and cost of sensors will be presented to provide insights on WSNs design. Our main contributions are presented as below: • Under the uniform deployment scheme, we study asymp￾totic coverage of heterogeneous WSNs with the i.i.d mobility model and 1-dimensional random walk mobility model. We define ESR of WSNs and analyze network per￾formance using this metric. We obtain the critical value of ESR for the WSNs to achieve asymptotic full coverage of the operational region. We demonstrate that 1-dimensional random walk mobility reduces the energy consumption by the order Θ log n+log log n n 2 at the expense of Θ(1) delay; • Under the uniform deployment scheme, heterogeneity is shown to impose no impact on energy consumption in stationary WSNs or WSNs with i.i.d. mobility model but to ‘slightly’ increase sensing energy consumption in WSNs with the 1-dimensional random walk model; • We study the WSNs under Poisson deployment strategy with the 2-dimensional random walk mobility model and derive the expectation of the fraction of operational region that is k-covered by the heterogeneous WSNs at an instant 2The following asymptotic notations are used throughout this paper. Given non-negative functions f(n) and g(n): 1) f(n)=Θ(g(n)) means that for two constants 0 < c1 < c2, c1g(n) ≤ f(n) ≤ c2g(n) for sufficiently large n. 2) f(n) ∼ g(n) means that limn→+∞ f(n) g(n) = 1.

IEEE TRANSACTIONS ON AUTOMATIC CONTROL as well as over a time interval.The results hold for a o(d general number of sensors except for the asymptotic case, and can provide guidelines on designing WSNs of high degree coverage.Plus,the detection time in the sensing process is investigated. The rest of the paper is organized as follows.In Sec- tion II,the system model and several performance measures are defined.In Section III,we present our main results.The asymptotic coverage problem in mobile heterogeneous WSNs is studied in Section IV and we discuss the impact of mobility Fig.1.A Typical Distribution of D. and heterogeneity based on the results.In Section V,we study k-coverage under Poisson deployment model.In Section VI, the detection delay is investigated.Finally,we conclude our that there are u groups G1,G2,...,Gu in this heterogeneous work in Section VII. network,where u is a positive constant.For y =1,2,...,u. group Gy consists of ny =cun sensors,where n is the total II.SYSTEM MODEL AND PERFORMANCE MEASURES number of sensors in the network and c(y 1,2,...,u)is In this section,we describe the system model regarding called the grouping index which is a positive constant invariant sensing,deployment and mobility pattern,respectively and ofn.e,cy=9(1》and∑y-19=l,For a given group present several measures to assess the coverage performance Gy,sensors in this group possess identical sensing radius r. of mobile heterogeneous WSNs. When ny =1,u=n,it is the special case where each sensor has different sensing radius from each other. A.Deployment Scheme Let the operational region of the sensor network A be an C.Mobility Pattern unit square and this square is assumed to be a torus.This is Sensors move according to certain mobility patterns. to eliminate the boundary effect and equalize all points in the region for convenience of analysis.We consider two models .I.I.D.MOBILITY MODEL-The sensing process is parti- according to which the sensors are deployed. tioned into time slots with unit length.At the beginning of UNIFORM DEPLOYMENT MODEL-n sensors are ran- each time slot,each sensor will randomly and uniformly domly and uniformly deployed in the operational region, choose a position within the operational region and remain independent of each other. stationary in the rest of the time slot. POISSON DEPLOYMENT MODEL-Sensors are deployed .1-DIMENSIONAL RANDOM WALK MOBILITY MODEL according to a 2-dimensional Poisson point process with Sensors in each group are classified into two types of density parameter A=n. equal quantity,H-nodes and V-nodes.And sensors of each These random deployment strategies are favored in the type move horizontally and vertically,respectively.The situation that the geographical region to be sensed is hostile sensing process is also divided into time slots with unit length.At the very beginning of each time slot,each sensor and inimical.Under such circumstance,wireless sensors might will randomly and uniformly choose a direction along its be sprinkled from aircraft,delivered by artillery shell,rocket. missile or thrown from a ship,instead of being placed by human moving dimension and travel in the selected direction a certain distance D which follows the distribution function or programmed robots.Specifically,uniform deployment model is commonly employed when the priori knowledge of the target fp(d).To make the model non-trivial,fp(d)satisfies such requirement:fp(d)=0 when d1,where do area is unavailable,and as a most simple scheme,it provides is an arbitrary constant and 01).it can sensors in the network have different sensing radii.We assume always cover the area along its moving dimension

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 3 as well as over a time interval. The results hold for a general number of sensors except for the asymptotic case, and can provide guidelines on designing WSNs of high degree coverage. Plus, the detection time in the sensing process is investigated. The rest of the paper is organized as follows. In Sec￾tion II, the system model and several performance measures are defined. In Section III, we present our main results. The asymptotic coverage problem in mobile heterogeneous WSNs is studied in Section IV and we discuss the impact of mobility and heterogeneity based on the results. In Section V, we study k-coverage under Poisson deployment model. In Section VI, the detection delay is investigated. Finally, we conclude our work in Section VII. II. SYSTEM MODEL AND PERFORMANCE MEASURES In this section, we describe the system model regarding sensing, deployment and mobility pattern, respectively and present several measures to assess the coverage performance of mobile heterogeneous WSNs. A. Deployment Scheme Let the operational region of the sensor network A be an unit square and this square is assumed to be a torus. This is to eliminate the boundary effect and equalize all points in the region for convenience of analysis. We consider two models according to which the sensors are deployed. • UNIFORM DEPLOYMENT MODEL — n sensors are ran￾domly and uniformly deployed in the operational region, independent of each other. • POISSON DEPLOYMENT MODEL — Sensors are deployed according to a 2-dimensional Poisson point process with density parameter λ = n. These random deployment strategies are favored in the situation that the geographical region to be sensed is hostile and inimical. Under such circumstance, wireless sensors might be sprinkled from aircraft, delivered by artillery shell, rocket, missile or thrown from a ship, instead of being placed by human or programmed robots. Specifically, uniform deployment model is commonly employed when the priori knowledge of the target area is unavailable, and as a most simple scheme, it provides insights for exploring more complex deployment strategies. Poisson deployment is a widely used method in literature to model the location of randomly-dropped sensors due to its memoryless and annexable property [23]. B. Sensing Strategy Basically, we employ the binary disc sensing model in this study, where we assume that a sensor is capable to sense perfectly within the disc of radius r centered at the sensor. Beyond this sensing area, the sensor cannot sense. Here, r denotes the sensing radius of a sensor. Further, our study takes into account the general case that sensors in the network have different sensing radii. We assume 0 1 d fD(d) d0 Fig. 1. A Typical Distribution of D. that there are u groups G1, G2, ··· , Gu in this heterogeneous network, where u is a positive constant. For y = 1, 2, ··· , u, group Gy consists of ny = cyn sensors, where n is the total number of sensors in the network and cy(y = 1, 2, ··· , u) is called the grouping index which is a positive constant invariant of n (i.e., cy = Θ(1)) and u y=1 cy = 1. For a given group Gy, sensors in this group possess identical sensing radius ry. When ny = 1, u = n, it is the special case where each sensor has different sensing radius from each other. C. Mobility Pattern Sensors move according to certain mobility patterns. • I.I.D. MOBILITY MODEL — The sensing process is parti￾tioned into time slots with unit length. At the beginning of each time slot, each sensor will randomly and uniformly choose a position within the operational region and remain stationary in the rest of the time slot. • 1-DIMENSIONAL RANDOM WALK MOBILITY MODEL — Sensors in each group are classified into two types of equal quantity, H-nodes and V-nodes. And sensors of each type move horizontally and vertically, respectively. The sensing process is also divided into time slots with unit length. At the very beginning of each time slot, each sensor will randomly and uniformly choose a direction along its moving dimension and travel in the selected direction a certain distance D which follows the distribution function fD(d). To make the model non-trivial, fD(d) satisfies such requirement: fD(d)=0 when d 1, where d0 is an arbitrary constant and 0 1), it can always cover the area along its moving dimension

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 4 to probability distribution function (p.d.f.)f(0).and at the end of the interval.Let n)denote the fraction of selects a velocity ,max)according to p.d.f.f(v). the whole area that achieves k-coverage within 7. The i.i.d.mobility pattern is widely used since it can provide DELAY OF DETECTION -Suppose certain point in the some intuitions and characterize the upper or lower bound.We operational region is not covered at time t =0.The will present the main approach to asymptotic coverage problem delay of detection D is defined to be the time that initially under this model.The 1-dimensional mobility model is motivat- uncovered point has been first ever covered.Similarly,D ed by certain networks that nodes move along determined tracks denotes the time for the initially uncovered point to be such as the networks employed in streets,systems consisted of k-covered. satellites moving in fixed orbits and so forth.The 2-dimensional random walk model can highly exploit the randomness of the III.MAIN RESULTS motion of nodes and is suitable to depict realistic situation that We summarize our main results in this paper as follows: the statistics about the habit of moving platforms is unknown. 1.Under the uniform deployment scheme: (1-a)With i.i.d.mobility model,the critical ESR is R.(n)= D.Performance Measures log n+log log n 元 To assess the coverage performance of the wireless sensor (1-b)With 1-dimensional random walk mobility model,the networks,we propose four measures. critical ESR is Ro(n)=logntloglogn,where K= ASYMPTOTIC COVERAGE-We define the equivalent k(fp(d))=2d2(1-h)dhdd is the function of sensing radius (ESR)to evaluate the overall performance fD(d). of sensors with different radii. 2.Under the Poisson deployment scheme with the 2- Definition 2.1:The ESR of the mobile heterogeneous dimensional random walk mobility model: WSNs wit油i.d.mobility model is,=√∑y=1c,r号 (2-a)E{e)}=1- T(k,πn∑-1cwr ,whereπr号1: 入=2λr0: lim P(C)0)if it is sensed by at least k different sensors (they A.Overview of Dense Grid may come from various groups),where k is a positive It is relatively difficult to analyze coverage by checking integer.Let n)be the fraction of the whole operational whether all points in the operational region are covered.To region that achieves k-coverage at instant t. approach this problem,certain idea has been presented in [8] K-COVERAGE OVER A TIME INTERVAL-A point in the and [9],that is to transform the coverage of all points within operational region is said to achieve k-coverage during a the operational region to the coverage of certain set of points. time interval,7=0,t)if it has been sensed by at least The set of points,denoted by M,is all the grid points of a k different sensors(they may come from various groups) Vm x Vm grid on the operational region.From LEMMA 3.1

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 4 to probability distribution function (p.d.f.) f(y) Θ (θ), and selects a velocity v ∈ [0, vmax) according to p.d.f. f(y) V (v). The i.i.d. mobility pattern is widely used since it can provide some intuitions and characterize the upper or lower bound. We will present the main approach to asymptotic coverage problem under this model. The 1-dimensional mobility model is motivat￾ed by certain networks that nodes move along determined tracks such as the networks employed in streets, systems consisted of satellites moving in fixed orbits and so forth. The 2-dimensional random walk model can highly exploit the randomness of the motion of nodes and is suitable to depict realistic situation that the statistics about the habit of moving platforms is unknown. D. Performance Measures To assess the coverage performance of the wireless sensor networks, we propose four measures. • ASYMPTOTIC COVERAGE — We define the equivalent sensing radius (ESR) to evaluate the overall performance of sensors with different radii. Definition 2.1: The ESR of the mobile heterogeneous WSNs with i.i.d. mobility model is r = u y=1 cyr2 y, and the ESR for 1-dimensional random walk mobility model is r = u y=1 cyry. Intuitively, the coverage capability of the network is pos￾itively correlated with ESR. The ESR needed when the network exactly achieves asymptotic coverage is called critical ESR. This direct connection between ESR and network performance is important for network design. For the network with ESR greater than critical ESR, the operation region will be full covered with probability one when n is large enough, which promises the sufficiency of critical ESR. While for those with ESR less than critical ESR, though n is large enough, the operation region still can’t be full covered with probability one, which reflects the necessity of critical ESR. Let C denote the event that the operational region is fully covered. Then we can get the following definition. If limn→∞ P(C)=1, if r ≥ cR(n) for any c > 1; limn→∞ P(C) < 1, if r ≤ cRˆ (n) for any 0 < c <ˆ 1, R(n) is the critical ESR under the i.i.d. model. Simi￾larly, we can define the critical ESR R(n) for the 1- dimensional random walk model. • K-COVERAGE AT AN INSTANT — A point in the opera￾tional region is said to achieve k-coverage at an instant t(t ≥ 0) if it is sensed by at least k different sensors (they may come from various groups), where k is a positive integer. Let η(t) be the fraction of the whole operational region that achieves k-coverage at instant t. • K-COVERAGE OVER A TIME INTERVAL — A point in the operational region is said to achieve k-coverage during a time interval, T = [0, t) if it has been sensed by at least k different sensors (they may come from various groups) at the end of the interval. Let η(T ) denote the fraction of the whole area that achieves k-coverage within T . • DELAY OF DETECTION — Suppose certain point in the operational region is not covered at time t = 0. The delay of detection D is defined to be the time that initially uncovered point has been first ever covered. Similarly, Dk denotes the time for the initially uncovered point to be k-covered. III. MAIN RESULTS We summarize our main results in this paper as follows: 1. Under the uniform deployment scheme: (1-a) With i.i.d. mobility model, the critical ESR is  R(n) = log n+log log n πn . (1-b) With 1-dimensional random walk mobility model, the critical ESR is R(n) = log n+log log n κn , where κ = κ (fD(d)) = 2  h≤d 2(1 − h)dhdd is the function of fD(d). 2. Under the Poisson deployment scheme with the 2- dimensional random walk mobility model: (2-a) E{η(t)} = 1 − Γ(k,πnu y=1 cyr2 y) (k−1)! , where πr2 y < |A| holds for arbitrary y, and Γ(a, b) is the upper incomplete gamma function, defined as Γ(a, b) =  +∞ b t a−1e−t dt. (2-b) E{η(T )} = 1− Γ(k,nu y=1 cyE{S(T ,y)}) (k−1)! , where E{S(T ,y)} denotes the expected area covered by a sensor in group Gy during the time interval T and E{S(T ,y)} < |A| holds for arbitrary y and T , Γ(a, b) is the upper incomplete gamma function. 3. Under the Poisson deployment scheme with 2- dimensional random walk mobility model and sensors move at constant velocity v0 in sensing process: (3-a) The delay of detection D1 is exponentially distributed D1 ∼ Exponential 2λv0 u y=1 (cyry) . (3-b) If ry = r and f(y) Θ (θ) = 1 2π for y = 1, 2, ··· , u, the delay of full k-detection Dk is a random variable distributed according to the p.d.f. fDk (d) = λ¯k (k−1)!dk−1e−λd¯ , where λ¯ = 2λrv0. IV. ASYMPTOTIC COVERAGE UNDER UNIFORM DEPLOYMENT SCHEME In this section, we analyze the asymptotic coverage under uniform deployment scheme with i.i.d. and 1-dimensional ran￾dom walk mobility model, respectively. A. Overview of Dense Grid It is relatively difficult to analyze coverage by checking whether all points in the operational region are covered. To approach this problem, certain idea has been presented in [8] and [9], that is to transform the coverage of all points within the operational region to the coverage of certain set of points. The set of points, denoted by M, is all the grid points of a √m × √m grid on the operational region. From LEMMA 3.1

IEEE TRANSACTIONS ON AUTOMATIC CONTROL ● Fig.2.Dense Grid Within the Operational Region Fig.3.Coverage Under L.I.D Mode.1 and THEOREM 4.1 in [9],we know that if m is large enough, such as m =n log n(i.e.,the grid is dense enough),the sensing radius that is sufficient to guarantee the asymptotic coverage of 1)Necessary ESR for Full Coverage of Dense Grid:Let g points in M will be sufficient to ensure the asymptotic coverage denote the event that the dense grid M is not fully covered and of the entire operational region as well.And the necessary we have the following proposition sensing radius for M is also necessary for the whole operational Proposition 4.1:In the mobile heterogeneous WSNs with region to achieve full coverage.Then we can focus on the coverage of the dense grid.And we will derive the critical (both i.i.d.mobility model,ifr(n)-)and the necessary and sufficient)ESR for sensor networks to achieve density of the dense grid M is m =n log n,then full coverage of the dense grid. liminfP(©)≥e-f-e-2s, n- B.Critical ESR Under I.I.D.Mobility Model whereξ=limn→+o(n). Let G denote the event that the dense grid M is covered. Proof:To begin with,we study the case where r.(n)= And we derive the critical ESR to guarantee asymptotic full logn+loglogn+for a fixed Applying the Bonferroni in- n coverage of M. equality,we have that Definition 4.1:For mobile heterogeneous WSNs with i.i.d. P(g)≥ P({some point P is not covered}) mobility model,r.(n)is the critical equivalent sensing radius PEM for M if P(is the only uncovered point}) lim P(9)=1,if r.cr.(n)for any c>1; PEM lim P(g)P({P:is not covered})>0e-, (4) P.EM

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 5 Fig. 2. Dense Grid Within the Operational Region. and THEOREM 4.1 in [9], we know that if m is large enough, such as m = n log n (i.e., the grid is dense enough), the sensing radius that is sufficient to guarantee the asymptotic coverage of points in M will be sufficient to ensure the asymptotic coverage of the entire operational region as well. And the necessary sensing radius for M is also necessary for the whole operational region to achieve full coverage. Then we can focus on the coverage of the dense grid. And we will derive the critical (both necessary and sufficient) ESR for sensor networks to achieve full coverage of the dense grid. B. Critical ESR Under I.I.D. Mobility Model Let G denote the event that the dense grid M is covered. And we derive the critical ESR to guarantee asymptotic full coverage of M. Definition 4.1: For mobile heterogeneous WSNs with i.i.d. mobility model, r(n) is the critical equivalent sensing radius for M 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. We have the following useful lemmas. Lemma 4.1: Given x = x(n) and y = y(n) both of which are positive functions of n, then (1 − x)y ∼ e−xy if x and x2y approach 0 as n → +∞. Proof: Refer to Appendix. Lemma 4.2: If r(n) = log n+log log n+ξ πn and m = m(n) = n log n, for any fixed θ < 1, m u y=1  1 − πr2 y(n) cyn ≥ θe−ξ, (1) holds for all sufficiently large n. Proof: See Appendix. Fig. 3. Coverage Under I.I.D Mode.l 1) Necessary ESR for Full Coverage of Dense Grid: Let G denote the event that the dense grid M is not fully covered and we have the following proposition. Proposition 4.1: In the mobile heterogeneous WSNs with i.i.d. mobility model, if r(n) = log n+log log n+ξ(n) πn and the density of the dense grid M is m = n log n, then lim inf n→+∞ P(G) ≥ e−ξ − e−2ξ, where ξ = limn→+∞ ξ(n).  Proof: To begin with, we study the case where r(n) = log n+log log n+ξ πn for a fixed ξ. Applying the Bonferroni in￾equality, we have that P(G) ≥ Pi∈M P({some point Pi is not covered}) ≥ Pi∈M P({Pi is the only uncovered point}) ≥ Pi∈M P({Pi is not covered}) − P i=Pj Pi,Pj∈M P({Pi and Pj are not covered}) (2) Respectively, we can evaluate the two terms on the right hand side of (2). As for the first term, we have P({Pi is not covered}) = u y=1 P({Pi is not covered by sensors in Gy}) = u y=1  1 − πr2 y(n) cyn . (3) Using Lemma 4.2, we bound the first term that for any θ < 1, Pi∈M P({Pi is not covered}) ≥ θe−ξ, (4)

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-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）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 θ 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) 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.

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 0P(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 P(i,y,τ) and P(Fi) can be calculated according to the distribution of D

IEEE TRANSACTIONS ON AUTOMATIC CONTROL using Lemma 4.1,we have log(R.H.S.of (15)) =(n(s(1-a+aam,m)》 for all sufficiently large n,considering =o(r).Therefore, >Pr({P;is not covered})=e(me-logn-loglogn-E)20e- PEM (16 Fig.5.Coverage Under 1-Dimensional Random Walk Mobility Model. for any fixed 1 and all nN(E,0). Let t(n)=kry(n)and to(n)=kro(n).And we can similarly obtain the lower bound 2)Necessary ESR for Full Coverage of Dense Grid:Let denote the event that the dense grid M is not fully covered in the given time slot r.We present the following proposition P({Pi,P;are not covered}) regarding the necessary condition on ESR. (1-4rr(n)(1-2(1+Sy)kr,(m) Proposition 4.2:In the mobile heterogeneous WSNs with y=1 1-dimensional random walk mobility model,if ro= e-2n∑-i(cwtw(n) (17) logntloglognts(n)and the density of the dense grid M is m =n logn,then and the upper bound lim inf P,(C7)>e-6-e-26. P({Pi,Pj are not covered}) whereξ=limn→+o(n). sira(-a+ro)°"+i-a+ow,m】 Proof:The technique used in this proof is similar to that used in the proof of Proposition 4.1,and we present the main steps here.We begin with the case thatrogno ≤Πrmj(1-m,(m)+Π(1-r,(m)n kn y=1 for a fixed E. e-2n∑-1(cvtv(m) P,(g)≥ >P({P:is not covered}) PEM Combining (17)and (18),we have P≠P P({Pi,P;are not covered}).(14) P≠P P,P,EM P(P P;are not covered}) P,P;EM Based on (13),we can evaluate the first term of on the right m2e-2n∑y-1(m》=e-25 (18) hand of side of (14)and have Thus,using (16)and (18)into (14),we obtain P(P:is not covered}) =Ⅱ1-(rm+m,m》 P,(gr)≥0e-f-e-2 (19) y=1 (15) Taking into account the case that is a function of n,the =Π(1-(1+Sg)kr,)” conclusion still holds. ◆ From Proposition 4.2.we know thatro is where Let we can easily obtain necessary to achieve the full coverage of M. =o(r).Taking the logarithm of the right side of (15)and

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 8 Fig. 5. Coverage Under 1-Dimensional Random Walk Mobility Model. 2) Necessary ESR for Full Coverage of Dense Grid: Let Gτ denote the event that the dense grid M is not fully covered in the given time slot τ . We present the following proposition regarding the necessary condition on ESR. Proposition 4.2: In the mobile heterogeneous WSNs with 1-dimensional random walk mobility model, if r = log n+log log n+ξ(n) κn and the density of the dense grid M is m = n log n, then lim inf n→+∞ Pτ (Gτ ) ≥ e−ξ − e−2ξ. where ξ = limn→+∞ ξ(n). Proof: The technique used in this proof is similar to that used in the proof of Proposition 4.1, and we present the main steps here. We begin with the case that r = log n+log log n+ξ κn for a fixed ξ. Pτ (Gτ ) ≥ Pi∈M Pτ ({Pi is not covered}) − P i=Pj Pi,Pj∈M Pτ ({Pi, Pj are not covered}).(14) Based on (13), we can evaluate the first term of on the right hand of side of (14) and have Pτ ({Pi is not covered}) = u y=1  1 − (πr2 y(n) + κry(n)) cyn = u y=1  1 − (1 + ζy)κry(n) cyn . (15) where ζy = πry(n) κ . Let ζ = u y=1 cyζy, we can easily obtain ζ = o(r). Taking the logarithm of the right side of (15) and using Lemma 4.1, we have log(R.H.S. of (15)) = u y=1  cyn  log  1 − (1 + ζy)κry(n) ∼ − u y=1  cynκry(n) = − log n − log log n − ξ for all sufficiently large n, considering ζ = o(r). Therefore, Pi∈M Pτ ({Pi is not covered}) = Θ(me− log n−log log n−ξ) ≥ θe−ξ (16) for any fixed θ N(ξ, θ). Let ty(n) = κry(n) and t(n) = κr(n). And we can similarly obtain the lower bound Pτ ({Pi, Pj are not covered}) ≥ u y=1  1 − 4πr2 y(n) (1 − 2(1 + ζy)κry(n))cyn ∼ e−2nu y=1(cyty(n)), (17) and the upper bound Pτ ({Pi, Pj are not covered}) ≤ u y=1 πr2 y(n)  1 − (1 + ζy)κry(n) cyn + u y=1  1 − (1 + ζy)κry(n) cyn ≤ u y=1 πr2 y(n)  1 − κry(n) cyn + u y=1  1 − κry(n) cyn ∼e−2nu y=1(cyty(n)). Combining (17) and (18), we have P i=Pj Pi,Pj∈M Pτ ({Pi, Pj are not covered}) ∼ m2e−2nu y=1(cyty(n)) = e−2ξ. (18) Thus, using (16) and (18) into (14), we obtain Pτ (Gτ ) ≥ θe−ξ − e−2ξ. (19) Taking into account the case that ξ is a function of n, the conclusion still holds. From Proposition 4.2, we know that r ≥ log n+log log n κn is necessary to achieve the full coverage of M.

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.

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 10 2)Impact of Heterogeneity:Second,we consider the impact E.Full Coverage Control and Sensing Energy Consumption of heterogeneity.We have the following technical lemma. Control Lemma 4.3:For arbitrary g that 0日 log n log log n (24) n 0 500 100015002000 2500300035004000 Total Number of Sensors n E.w.0,the expectation of the WSNs with i.i.d.mobility model,however,the covered area is fraction of operational region that is k-covered at instant t is on the order ofr2.This discrepancy of dependence on sensing radius leads the impact of heterogeneity to be different under g}=1- (k,m∑y=1yr) the two models. (k-1)1

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 10 2) Impact of Heterogeneity: Second, we consider the impact of heterogeneity. We have the following technical lemma. Lemma 4.3: For arbitrary q that 0 Θ log n + log log n n 2  ; (24) Er.w.  u y=1 cyry 2 . And the upper bound results from Lemma 4.3. Hence, with the sensing energy model Ey ∝ r2 y, heterogene￾ity does not make any difference to sensing energy in WSNs under i.i.d. mobility model or stationary WSNs, which can be seen from (20) and (23). However, from (21) and (24) we know that under 1-dimensional random walk mobility model, sensing energy consumption will increase due to heterogeneity. And there is a trade-off in mobile WSNs that designers must face: on one hand, heterogeneous WSNs composed of high￾end sensors with large sensing range and low-end sensors with small sensing range can reduce the cost of WSNs and guarantee a satisfactory sensing performance; on the other hand, heterogeneity will increase sensing energy consumption. From the upper bound in (25), the order of energy consumption in terms of n approaches the order (i.e., n2) in the case without heterogeneity. Hence, the energy efficiency will not be dramatically deteriorated by the heterogeneity. Remark 4.1: The sensing process in WSNs depends on the area covered by each sensor. And under the 1-dimensional random walk mobility model, the area covered by sensors is on the same order of sensing radius r. In stationary WSNs or WSNs with i.i.d. mobility model, however, the covered area is on the order of r2. This discrepancy of dependence on sensing radius leads the impact of heterogeneity to be different under the two models. E. Full Coverage Control and Sensing Energy Consumption Control From previous discussions, we can know that critical ESR is the critical condition for full coverage of the operational region. Therefore, we can control the ESR to promise the network achieve full coverage under different random mobility patterns, as shown in Figure 6. As the total number of sensors increases, 0 500 1000 1500 2000 2500 3000 3500 4000 0 0.02 0.04 0.06 0.08 0.1 0.12 Total Number of Sensors n Critical ESR I.I.D mobility model 1−dimensional random walk model Fig. 6. Relationship between ESR and total number of sensors n. the critical ESR decreases for I.I.D mobility model and 1- dimensional random walk mobility model. When we want to control the full coverage, we can make the network achieve the critical ESR under I.I.D mobility and 1-dimensional random walk mobility model as illustrated in the figure. Since the sensing energy consumption is positively correlated to the ESR as discussed previously, if we want to further decrease the energy consumption, we have to decrease the ESR. This further reduction of ESR will make the network not be full covered, thus sacrificing the coverage performance, which is actually a tradeoff control realized by the value of ESR. V. K-COVERAGE IN MOBILE HETEROGENEOUS WSNS UNDER POISSON DEPLOYMENT MODEL In this section, we study k-coverage at an instant and over a time interval in mobile heterogeneous WSNs. The sensor locations within the operational region are modeled as 2-dimensional Poisson process with density n. Thus, the coverage problem can be described by the frequently used Poisson-Boolean model. Besides, the 2-dimensional random walk mobility model is employed in this part. A. K-coverage at an Instant We start with the results regarding k-coverage at an instant. Theorem 5.1: Given an instant t > 0, the expectation of the fraction of operational region that is k-covered at instant t is E{η(t)} = 1 − Γ k, πnu y=1 cyr2 y (k − 1)! ,