1 Introduction

Air pollution is a hazard that affects not only urban areas (cities) [26], but also rural and industrial environments [20] activities including crop yield, forest monitoring, and animal health, among others.

In the literature, we can observe that traditional methods for air pollution monitoring (fixed monitoring stations) are gradually being replaced by mobile crowdsensing sensors that are small enough to be carried around by users, or installed in different vehicles like taxis, busses, bicycles, or any type of vehicle [1, 4, 7, 12, 24].

The crowdsensing approach is not feasible in rural areas because it clearly requires a minimum number of sensors to be moving inside the target area to be applicable, a requirement that is typically not met in these remote environments. For instance, in this type of scenarios, vehicular traffic is quite scarce, being limited to the main transportation arteries, thereby failing to provide the required granularity in both time and spatial domains.

To effectively carry out monitoring tasks in rural scenarios, an attractive option is to use Unmanned Aerial Vehicles (UAVs) equipped with Commercial Off-The-Shelf (COTS) sensors, allowing them to act as mobile sensors, and being able to reach poorly accessible areas [3]. In fact, this approach allows monitoring most locations in any target area due to UAV flexibility and maneuverability, such as the capability to take samples while hovering.

Focusing on UAV control systems for air pollution monitoring tasks, we have noticed that there were no systems optimized for these purposes. So, we proposed Pollution-driven UAV Control (PdUC) [6], a solution that puts the focus on the most polluted regions by combining a chemotaxis meta-heuristic with an adaptive spiral mobility pattern to automatically track pollution sources and surrounding pollution diffusion in a given target area. In a previous work [6], we showed that PdUC achieves better performance than standard mobility approaches, like the Spiral and the Billiard patterns, in terms of discovering the most polluted areas in a shorter time span. In this paper we propose an optimized algorithm called PdUC-D, which is based on PdUC, but it applies space discretization to substantially reduce the convergence time from 1800-4200 seconds in PdUC to 1200-3000 seconds in PdUC-D, while achieving similar levels of accuracy (about 5% of final relative error) in an area of 4x4 Kilometers, and a step size / tile size equals to 100 meters.

This paper is organized as follows: Section 2 presents an analysis of the related work regarding UAV usage for air pollution monitoring. In Section 3 we describe the proposed PdUC-D protocol. Section 4 presents details regarding the implementation of the protocol, along with a performance comparison including tile size analysis and a comparison against the original PdUC proposal. Finally, in Section 5, we present the conclusions of our work and future lines of research.

2 Related works

The use of UAVs is increasing rapidly in the last years due to their low cost and flexibility. In fact, they are being adopted in different areas including commercial, Earth Sciences, national security, and land management [11, 15]. In the literature we can find several studies analyzing their use. For example, Pajares et al. [23] display the results of a detailed study on different UAVs aspects, showing their applicability in agriculture and forestry, disaster monitoring, localization and rescue, surveillance, environmental monitoring, vegetation monitoring, photogrammetry, and so on.

Focusing on air pollution monitoring using Unmanned Aerial Systems (UAS), different works have been done related to providing UAVs with different useful payloads. For example, Erman et al. [13] use an UAV equipped with a sensor to create a Wireless Sensor Network, thereby enabling each UAV to act as a sink or as a node, but it does not try to optimize the monitoring process. Teh et al. [28] propose a fixed-wing aircraft carrying a sensor node that acts as a mobile gateway, allowing the communication between the UAV and different static base stations which monitor pollution. In this case, the UAV only recovers the data collected by the fixed stations. In [18], the authors propose the design of a lightweight laser-based sensor for measuring trace gas chemical species using UAVs, analyzing how the optical sensor captures the air pollution samples. More recently, Illingworth et al. [16] used a large-sized aircraft equipped with ozone sensors to cover a wide area in an automated manner, showing how the UAS improves the sampling granularity.

Analyzing works related to mobility models for UAS mobility control that could be used for air pollution monitoring tasks, the majority of these solutions mainly involve, swarm creation protocols and communication interaction to synchronize their movements. An example of such work is [31], where authors propose a mobility model for a group of nodes following “Virtual Tracks” (highways, valleys, etc.) operating in a predefined Switch Station mode, through which groups of nodes can split or merge with others. Furthermore, regarding solely UAV control issues, no work focuses on the coverage improvement for a certain area taking pollution levels into account.

For instance, in [9], the authors propose a mobility model based on the Enhanced Gauss-Markov model to eliminate or limit the sudden stops and sharp turns that the random waypoint mobility model typically creates. Also, in [30], the authors present a semi-random circular movement (SRCM) based model. They analyze the coverage and network connectivity by comparing results against the random waypoint mobility model.

The authors of [22] compare their models against the random-waypoint-based, the Markov-based, and the Brownian-motion-based algorithms to cover a specific area, analyzing the influence of collision avoidance systems in the time required to achieve a full area coverage. The work in [19] compares the results of using the Random Mobility Model and the Distributed Pheromone Repel Mobility Model as direction decision criteria (selection of next waypoint) in UAV environments. Finally, the authors in [29] propose an algorithm to cover a specific area; it selects a point in space along with the line perpendicular to its heading direction, and then it drives the UAV based on geometric considerations.

Focusing solely on existing proposals addressing mobility models, we can find works such as [10], where authors propose the Paparazzi Mobility Model (PPRZM) by defining five types of movements: Stay-On, Way-Point, Eight, Scan, and Oval. They follow a state machine with different probabilities to change between states. There are even studies following animal-based navigation patterns. An example of such work is [8], where authors investigate the UAV placement and navigation strategies, with the end goal of improving network connectivity, using local flocking rules that aerial living beings, like birds and insects, typically follow. However, none of these works tries to optimize the monitoring process or the path followed by the UAV.

Since in the literature we could not find solutions where multi-rotor UAVs are used for air pollution monitoring in a specific area, we proposed PdUC (Pollution-driven UAV Control) [5, 6] to automatically track pollution sources in a target area, and to dynamically provide a pollution map of the surrounding region; as an improvement upon this previous work, in this paper we propose the PdUC-D (Discretized PdUC) protocol, which is described and validated in the next sections.

3 PdUC-D: discretized pollution-driven UAV control protocol

Pollution-driven UAV Control (PdUC) is composed of two phases: (i) A Search phase, in which the UAV searches for a global maximum pollution value, and (ii) an Explore phase, where the UAV explores the surrounding area, following a spiral movement, until it covers the whole area. Such phase can end prematurely if the allowed flight time ends (e.g., battery is depleted), or if it finds another maximum value, in which case it returns to the Search phase.

Despite PdUC [6] being more effective than other mobility patterns (Spiral and Billiard) in terms of polluted areas monitoring times, finding the most highly polluted locations earlier, it still spends too much time focusing on small variations. Tracking these variations, that can also be produced by sensor errors, is not too efficient in obtaining the global pollution map. On the contrary, the Spiral and Billiard models present simpler mobility patterns that, by themselves, avoid such redundant sampling. So, in this work, the main idea is to optimize PdUC by discretizing the whole target area, creating a grid composed of small tiles. Notice that discretization is one of the most efficient mathematical approaches to optimize a system by transforming a continuous domain into its discrete counterpart [14], as shown in Fig. 1. Notice that the UAV can only move to the center of each tile, and each tile can only be monitored once, thereby reducing redundant sampling, which in turn reduces the full coverage time significantly.

Fig. 1
figure 1

Example of a discretized area, calculating the tiles and their center to restrict movements

Full size image

PdUC-D, just like PdUC, combines a chemotaxis meta-heuristic with an adaptive spiral, the difference being that both these mechanisms are adapted to operate with discretized space environments. Therefore, PdUC-D starts by first searching the tile with the highest pollution level (Search phase). Next, it covers the surrounding area by following an adaptive spiral until all the area is covered, or until it can find another tile with a higher pollution value (Explore phase), thereby switching back to the Search phase.

We modify the PdUC phases by adapting its functionality to a discretized space, as shown in Fig. 2. So, the first step involves splitting the target area into small tiles, and calculating the center positions of these tiles (actual locations where monitoring takes place). Next, the Search and the Explore phases are modified to operate within the obtained discretized space.

Fig. 2
figure 2

Change of the PdUC to PdUC-D algorithm

Full size image

The Search phase is based on a chemotaxis mobility pattern, and an adaptation of the Particle Swarm Optimization (PSO) [17] algorithm. Figure 3 graphically shows the modification introduced for the chemotaxis and the PSO algorithm. Regarding chemotaxis movement, a particle moving in a Euclidean plane between two tiles, and following a specific direction, moves toward the next tile in the same direction (Run move) if the pollution variation is increasing along it. Otherwise, if the pollution variation is decreasing, it moves around the tile with higher previously monitored pollution values, assigning a higher priority to the nearer tiles (Tumble move); namely, it chooses the nearest tile. The procedure of moving around the maximum monitored value is an adaptation of the PSO algorithm, which takes the maximum value into account. If all tiles around the one with the highest detected value have already been monitored, the algorithm switches to the Explore phase, just like PdUC does.

Fig. 3
figure 3

Differences between the PdUC and PdUC-D algorithms for the Search phase: Chemotaxis (top) and PSO (bottom)

Full size image

The Explore phase is based on an adaptive spiral movement pattern modified to accommodate a discretized space environment, as shown in Fig. 4. There are three main movement patterns involved:

  • First, starting at the tile with the highest monitored pollution value, it follows a square spiral (see Fig. 4 top). For each round in the spiral, it skips an increasing number of tiles. Namely, in the first round it has a radius of 3 tiles and skips 1 tile; in the second round, it has a radius of 5 tiles and skips 2 tiles, and so on.

  • Next, to avoid excessively long steps, if the spiral radius reaches a scenario border or previously monitored areas, the direction of the spiral is changed alternating the movement direction to rotate in the opposite direction, as shown Fig. 4 (middle).

  • Finally, for controlling previously monitored areas (see Fig. 4 bottom), we consider as an already monitored area the whole square created at the end of each spiral round.

Fig. 4
figure 4

Change of the PdUC to PdUC-D algorithm in the Explore phase: Adaptive Spiral (top), Alternate direction (middle), and Avoidance of previously monitored areas (bottom)

Full size image

With regard to movement control, and to avoid re-visiting previously monitored areas, we use two matrices: Pm,n and Bm,n, to store the sampled values and the monitored tiles, respectively. Notice that n × m represents the size of the grid (rows and columns respectively).

$$P_{m,n}=\left( \begin{array}{llll} p_{1,1} & p_{1,2} & {\cdots} & p_{1,n} \\ p_{2,1} & p_{2,2} & {\cdots} & p_{2,n} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ p_{m,1} & p_{m,2} & {\cdots} & p_{m,n} \end{array}\right) $$
$$B_{m,n}=\left( \begin{array}{llll} b_{1,1} & b_{1,2} & {\cdots} & b_{1,n} \\ b_{2,1} & b_{2,2} & {\cdots} & b_{2,n} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ b_{m,1} & b_{m,2} & {\cdots} & b_{m,n} \end{array}\right) $$

First, both matrices are initialized, P with NaN (null), and B with 0’s. In the Search phase, when monitoring a tile ti,j (i and j are the row and the column position, respectively), the obtained pollution values are stored in Pi,j, and Bi,j are set to 1. When monitoring a tile either in the Explore phase or the Search phase, both P and B values are stored. However, when completing a spiral round, all tiles inside the square are set as visited in B, thereby avoiding to monitor the same area again in the future.

4 Validation

We have implemented PdUC-D in the R programming language [25], and we have a wide set of simulations with different configurations. Figure 5 shows a screenshot of the simulation script output, which includes four images: the base pollution map created based on a Kriging-based interpolation, the pollution map created when introducing a random sampling error of 10 ppb (parts-per-billion) for each point, the sampled data (P matrix values), and the areas marked as already monitored (B matrix values).

Fig. 5
figure 5

Screenshots of the different elements involved in the R implementation of PdUC-D: (i) initial pollution map (top-left); (ii) pollution map after introducing sampling errors (top-right); (iii) sampled data/P Matrix (bottom-left) and (iv) area considered as already monitored/B matrix (bottom-right). The values on both axes correspond to the ratio with respect to the total area (0 to 1)

Full size image

To prepare a suitable data environment, we have created various pollution distribution maps representing ozone levels to be used as inputs. These pollution maps were also generated using the R programming language, following Kriging-based interpolation [27]. In particular, a Gaussian distribution is used to adjust the parameters coming from random data sources of ozone concentration. The actual values range between 40 and 180 ppb, which are representative of different realistic conditions according to the Air Quality Index (AQI) [2], thereby providing a realistic ozone distribution.

Similarly to PdUC, we are proposing the PdUC-D algorithm for rural environments, and so the simulation area defined is 4 × 4 Km. Since samples are taken using off-the-shelf sensors, which are not precise, we introduce a random sampling error of ± 10ppb based on real tests using the MQ131 (Ozone) sensor [21]. In our simulation, we set the maximum UAV speed to 20 m/s, a value achievable by many commercial UAVs. The step distance defined between consecutive samples is 100 m since it offers a good trade-off between granularity and flight time. Once a new sampling location is reached, the monitoring time per sample is defined to be 4 seconds.

Obtained data using PdUC-D was compared against previous results obtained using PdUC [6]. Figure 6 shows an example of the path followed by an UAV using (a) PdUC, and (b) PdUC-D as a guidance system. As expected, both algorithms have, in general, a similar behavior: the UAV starts a search process throughout the scenario until it locates a position with the highest degree of pollution (local maximum). Afterward, it follows a spiral pattern to gain awareness of the surrounding gradients. If, while following the spiral-shaped scan path, it finds a higher pollution value, the algorithm again switches to the Search phase. Finally, when the entire target area has been sampled, the algorithm finishes. When adopting PdUC-D, though, we can clearly see that it achieves better performance in terms of reducing the time to cover the whole area and the monitoring error, while avoiding redundant sampling.

Fig. 6
figure 6

Example of a path followed by an UAV guided by the PdUC and PdUC-D protocols

Full size image

To analyze PdUC-D, we used the same simulation parameters as the ones adopted for validating PdUC [5]. Table 1 summarizes the parameters used in the simulations.

Table 1 Simulation parameters
Full size table

First of all, we analyze the impact of varying the tile size between 50[m] and 400[m]. Our goal is to determine which is the best size considering our restrictions.

Figure 7 shows the Cumulative Distribution Function (CDF) relative to the flight time required to cover the whole area for four tile sizes (50[m], 100[m], 200[m], and 400[m]). It can be seen that, as expected, the smaller the tile size, the higher the coverage time, reaching values that range from 2400 to 4600 seconds for a tile size of 50[m], while for tiles size of 200[m] and 400[m] these coverage times are in the range from 800 to 1500 seconds. For a tile size of 100[m], the coverage time is between 1500 and 2400 seconds, which represents 40 minutes of flight time. Such flight time is realistic, being achieved by some of the currently available commercial UAVs.

Fig. 7
figure 7

Cumulative Distribution Function of the time spent by PdUC-D to fully cover the area for different tile sizes: 50, 100, 200, and 400 meters, respectively

Full size image

To gain further insight into the goodness of the proposed algorithm, we also analyze the relative error for all cases at different time instants (600, 1200, 1800, 2400, 3000, and 6000 seconds); this error is defined by Eq. 1:

$$ e_{t} = \frac{{\sum}_{i = 1}^{m} {\sum}_{j = 1}^{n} \lvert \frac{s_{x,y,t} - b_{x,y}}{\triangle b} \rvert}{m \cdot n} $$
(1)

In the equation, et is the relative error at time t, sx,y,t is the recreated pollution value at position (x, y) using the samples taken during simulation until time t, bx,y is the reference pollution value at position (x, y), and n and m are the dimensions of the target area, respectively.

Figure 8 shows the temporal evolution of the relative error for different tile sizes (50[m], 100[m], 200[m], and 400[m]), as well as the reference values. We can observe that, even though at the end a smaller relative error (4.8%) is achieved for a tile size of 50[m], the time to reach this value is too long (more than 4000 seconds). On the other hand, in the 200 and 400[m] cases, they reach their minimum relative error faster, but the error values can be considered too high (almost 10%) when compared with the other cases. In the 100[m] case, although the final relative error is only a bit higher (almost 6%) than the 50[m] case (4.8%), the time to reach this error is still manageable. For these reasons, we consider that the tile size offering the best trade-off between flight time and accuracy is 100 meters.

Fig. 8
figure 8

Relative error comparison for PdUC-D varying tile sizes: 50, 100, 200, and 400 meters, respectively

Full size image

To further emphasize on the benefits of using PdUC-D, we now proceed to compare it against the PdUC, Spiral, and Billiard [5] strategies. We use the same simulation parameters as defined above, and we adopt the optimum calculated tile size (100 meters).

Figure 9 shows the Cumulative Distribution Function relative to the time required to cover the whole area for PdUC, Billiard, Spiral, and PdUC-D mobility models. It can be seen that the PdUC-D model spends much less time (1500-3000 seconds) than the PdUC model (1800-4300 seconds) to achieve the same goal. Moreover, it spends less time that the Spiral approach in nearly all cases, and it clearly outperforms the Billiard mobility pattern.

Fig. 9
figure 9

Cumulative Distribution Function (CDF) of the time spent to fully cover the area for the PdUC, PdUC-D, Billiard and Spiral mobility models

Full size image

Figure 10 shows the temporal evolution of the relative error between the model-based predictions (using PdUC, Spiral, Billiard, and PdUC-D) and the reference values. We can observe that all mobility models roughly exhibit the same behavior: they start with a high relative error, which is foreseeable since we are using Kriging interpolation to recreate the pollution distribution, and it gradually decreases toward the mean error value as the number of samples increases. Then, as more and more samples become available, the spatial interpolation process quickly becomes more precise. Moreover, we can observe that, even in this analysis, PdUC-D still obtains better results than the other three approaches by significantly reducing the relative error at different times.

Fig. 10
figure 10

Relative error comparison between the PdUC, PdUC-D, Billiard and Spiral mobility models at different times

Full size image

5 Conclusions and future work

Air pollution monitoring in rural areas is a relevant issue that typically finds many obstacles due to the lack of monitoring infrastructures, and due to the complexity of having mobile ground sensors in many cases. In this context, UAVs equipped with air quality sensors emerge as a novel and powerful alternative.

In this paper we follow this research line by describing Discretized Pollution-driven UAV Control (PdUC-D), an algorithm for air pollution monitoring tasks that improves upon our previous proposal (PdUC). In particular, it operates as an UAV guidance system to move toward the most polluted areas, mapping pollution maps in the surrounding area afterward. PdUC-D is based on the Chemotaxis and Adaptive Spiral principles, but its functionality was modified to work in a space-discretized area, thereby making it much more optimal in terms of coverage time and reducing prediction errors.

We have analyzed the optimum tile size taking into account our flight time restrictions, and compared four tile sizes (50[m], 100[m], 200[m], and 400[m]), finding that a tile sized 100×100 m is the best option.

We have compared PdUC-D against PdUC, as well as against standard mobility models (Billiard and Spiral), by creating several simulations in an R environment, and comparing these results with the previously obtained ones. Experimental results show that PdUC-D outperforms PdUC in all aspects, reducing the time to cover the same area, and reducing the monitoring error as well.

As the next step of our research, we plan to translate our algorithm to a real UAV, and test it in a real-world testbed.