Keywords

1 Introduction

Air pollution is a hazard not only affecting urban areas (cities) [1], but also rural and industrial environments [2] in different aspects such as crop yield, forest 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, buses, bicycles, or any type of land vehicle [3,4,5,6,7].

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, able to reach poorly accessible areas [8]. In fact, this approach allows monitoring most locations in any target area due to UAV flexibility and maneuverability, like the capability to take samples while hovering.

Focusing on UAV control systems for air pollution monitoring tasks, we have previously noticed that there are no systems optimized for these purposes. So, we proposed PdUC (Pollution-driven UAV Control [9]), a solution that puts focus on the most polluted regions by combining a chemotaxis metaheuristic with adaptive spiral mobility patterns to automatically track pollution sources and surrounding pollution values in a given target area. In that previous work [9] we showed that PdUC achieves better performances 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 applies space discretization to substantially reduce the convergence time while achieving similar levels of accuracy.

This paper is organized as follows: in Sect. 2 we describe the proposed PdUC-D protocol. Section 3 presents the implementations of the protocol in the R tool, along with a performance comparison against the original PdUC protocol. Finally, in Sect. 4, we present the conclusions of our work and the future work.

2 PdUC-D: Discretized Pollution-Driven UAV Control Protocol

Despite PdUC [9] is more effective than other mobility patterns (Spiral and Billiard) in terms of polluted areas monitoring times, finding the most highly polluted locations earlier, PdUC still spends too much time focusing on small variations (variations produced by sensor errors, or little pollution variations) in nearby areas, which are not too useful when 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, we attempt to avoid redundant movements (sampling) by discretizing the target area, dividing it into small tiles.

Fig. 1.
figure 1

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

Full size image

The main idea is to optimize PdUC by discretizing the whole target area in a grid forming small tiles, as shown in Fig. 1. The UAV can only move to the center of each tile, thereby reducing redundant sampling, which in turn reduces the full coverage time significantly. Each tile is monitored only once.

PdUC-D, just like PdUC, is based on a chemotaxis metaheuristic and on an adaptive spiral, with the difference that now both these mechanisms are adapted to operate with discretized space environments. Therefore, PdUC-D first starts by searching the tile with the highest pollution level (Search phase). Next, it covers the surrounding area 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 space discretization as follows:

The search phase is based on a chemotaxis mobility pattern, as shown in Fig. 2: a particle moving in an euclidean plane between two tiles, and following a specific direction, moves towards 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 higher priority to nearer tiles (Tumble move); namely, it chooses the nearest tile. If all tiles around the one with the highest detected value have already been monitored, the algorithm switches to the Explore phase.

Fig. 2.
figure 2

Search phase: calculation of the next tile following the chemotaxis-based mobility pattern.

Full size image
Fig. 3.
figure 3

Explore phase: adaptive spiral followed by PdUC-D showing a normal spiral movement (left) and alternating movement (right).

Full size image

The Explore phase is based on a adaptive spiral, as shown in Fig. 3 (left): Starting at the tile with the highest monitored pollution value, it then follows a square spiral. For each round in the spiral, it skips an increasing number of tiles. Namely, in the first round it has an radius of 3 tiles and skips 1 tile; in the second round, it has an radius of 5 tiles and skips 2 tiles, and so on. To avoid excessively long steps, if the spiral radius reaches a scenario border, or previously monitored areas, the direction of the spiral is altered, as shown Fig. 3 (right).

Fig. 4.
figure 4

Explore phase: example of the adaptive square spiral showing the possible moves.

Full size image

Figure 4 shows the behaviour of the adaptive spiral: it first starts by following a square spiral but, when it reaches the border, it alternates the direction of movement to rotate in the opposite direction.

With regard to movement control, and to avoid previously monitored areas, we use two matrixes: \(P_{m,n}\), and \(B_{m,n}\) to store the sampled values and the monitored tiles, respectively. Notice that \(n \times m\) represent the size of the grid, and the position of the tiles.

$$\begin{aligned} P_{m,n} = \begin{pmatrix} 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{pmatrix} B_{m,n} = \begin{pmatrix} 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{pmatrix} \end{aligned}$$
(1)

First, both matrices are initialized, P with NA (null), and B with 0’s. In the search phase, when monitoring a tile \(t_{x,y}\), the pollution values are stored in \(P_{x,y}\), and \(B_{x,y}\) are set to 1. In the explore phase, as well as in the search phase, when monitoring a tile, both P and B values are stored but, when finishing 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.

3 Validation

We have implemented PdUC-D in the R Graph tool [10], and we have run several simulations with different configurations.

To prepare a suitable data environment, we have created various pollution distribution maps representing ozone levels to be used as inputs for testing. These pollution maps were also generated using the R Graph tool following Kriging-based interpolation [11]. 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 (parts-per-billion), thereby providing a realistic ozone distribution.

Fig. 5.
figure 5

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

Full size image

Obtained data using PdUC-D was compared against previous results obtained using PdUC [9]. Figure 5 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 behaviour: 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 while avoiding redundant sampling.

To compare PdUC-D against PdUC [12] we use the same simulation parameters, previously used for validating PdUC. Table 1 summarizes the parameters used in the simulations.

Table 1. Simulation parameters.
Full size table

Since we are proposing the PdUC and PdUC-D algorithms for rural environments, the simulation area defined is a \(4 \times 4\) Km area. The pollution distribution relies on synthetic maps that are generated by combining a random Kriging interpolation following a Gaussian model with values between 40 and 180 units based on the Air Quality Index (AQI) [13]. Since samples are taken using off-the-shelf sensors, which are not precise, we introduce a random sampling error of \(\pm 10\) ppb based on real tests using the MQ131 (Ozone) sensor. 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 s.

Fig. 6.
figure 6

Cumulative Distribution Function of the time spent at covering the complete area for the PdUC and PdUC-D mobility models.

Full size image
Fig. 7.
figure 7

Relative error comparison between the PdUC and PdUC-D mobility models at different times.

Full size image

Figure 6 shows the Cumulative Distribution Function relative to the time required to cover the whole area for PdUC and PdUC-D mobility models. It can be seen that the PdUC-D model spends much less time (1500–3000 s) than the PdUC model (1800–4300 s) to achieve the same goal.

To gain further insight into the goodness of the proposed algorithm, we also analyze the relative error for the two mobility models at different time instants (600, 1200, 1800, 2400, 3000 and 600 s); this error is defined by Eq. 2:

$$\begin{aligned} e_{t} = \frac{\sum _{i=1}^{m} \sum _{j=1}^{n} |\frac{s_{x,y,t} - b_{x,y}}{\triangle b} |}{m \cdot n} \end{aligned}$$
(2)

where, \(e_{t}\) is the relative error at time t; \( s_{x,y,t}\) is the recreated pollution value at position (x, y) using the samples taken during simulation until time t, \(b_{x,y}\) is the reference pollution value at position (x, y), and n and m are the dimensions of the target area, respectively.

Figure 7 shows the temporal evolution of the relative error between model-based predictions (PdUC and PdUC-D) and the reference values. We can observe that both mobility models have roughly 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 tends to the mean value when the number of samples is not enough. Then, as more samples become available, the spatial interpolation process quickly becomes more precise. Moreover, we can observe that, even in this analysis, PdUC-D obtains better results than PdUC by significantly reducing the relative error at different times.

4 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 ground mobile 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 assumption by describing an algorithm for air pollution monitoring tasks called PdUC-D (Discretized Pollution-driven UAV Control), that is based on a previous work (PdUC). In particular, it operates as an UAV guidance system to move towards the most polluted areas, and map pollution in the surrounding area. PdUC-D has the same phases as the original PdUC proposal (Search and Explore), and it is based in the same principles (Chemotaxis and Adaptive Spiral), but its functionality was modified to work in an space-discretized area, thereby making it much more optimal.

We have compared PdUC-D against PdUC by creating several simulations in the R Tool, and comparing these results with the previously obtained ones. Experimental results show that PdUC-D has much better performance than PdUC in all aspects, reducing the time to cover a same area, and reducing the error.

The next step of our research is to translated our algorithm to a real UAV, and test it in real-world testbed.