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=1IEEE 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.