Data Gathering in Wireless Sensor Networks Using Unmanned Aerial Vehicles

Abstract

In an IoT world sensor-enabled systems are all around us and accessible for management at any time and place. Besides other technological components, small unmanned aerial vehicles are also expected to have an important role in IoT as they fly at low-altitude becoming suitable data acquisition vehicles in certain situations. In this article we focus on data gathering using unmanned aerial vehicles for applications having delivery limit constraints. The problem is to design an efficient set of paths to gather sensor data at specific places, and to deliver it at the sink node, while accomplishing the delivery limit associated with data. After formalizing the problem, a heuristic approach is developed that incorporates solution improvement mechanisms suitable for data gathering purposes. Results show that the proposed approach is suitable to solve the data gathering problem and clues on how to adjust parameters, according to the nature of the data set, are given.

1 Introduction

As sensors become smaller and cheaper, together with the possibility of organizing them into networks, a whole range of data can be collected, aggregated and shared [11, 14]. This new wave, called Internet of Things (IoT), is seen by many researchers as a new industrial revolution. Devices connected to the Internet will be accessible and may be managed at any time and place. In this new world of IoT, small unmanned aerial vehicles (UAVs), also called drones, are expected to have an important role [6, 8, 9]. UAVs fly at low-altitude becoming suitable data acquisition vehicles in certain situations, e.g. sensor networks at difficult to reach areas. UAV prices are also coming down meaning that new applications are expected in a near future.

The main goal of sensors it to capture the state of the environment (e.g. temperature, humidity, luminosity, etc.) and to relay this information to an entity (sink node or base station) more suited for data processing, visualization, analysis and decision making. A sensor node is a small sensing capable device with limited processing capability, reduced memory capacity and bandwidth, and a limited source of energy [21]. Despite of all these hardware limitations, sensors are very useful nowadays and applications range from simple luminosity measurements to radiation measurements in atomic plants [5].

Due to the limited capabilities of the sensor nodes, local data analysis may not be possible and forwarding data to a more capable device becomes crucial. One of the possibilities is to use a multihop wireless network infrastructure where data is forwarded toward the sink using intermediate wireless nodes. However, since transmission is quite energy consuming this kind of operation may reduce the lifetime of the network. Replacing the energy source of a sensor may not be viable because of the surrounding conditions and in most cases once the sensor is discharged there is nothing left to be done. All these constraints mean that data transmission must be thoughtful and must be used only when strictly required in order to extend network operation. Besides this, for some applications it may not be possible, for economic reasons or due to place conditions, to implement a wireless sensor network that makes a full coverage of an area and/or directly connected to the Internet. In these scenarios, mobile elements (e.g. UAVs) that move directly to the source, receive information from it and then deliver such information at the destination, can be more appropriate.

In this article we focus on data gathering, using UAVs. It is assumed that UAVs have limited buffer sizes and that data collected has a time delivery limit, or time-to-live (TTL) constraint. The goal is to design an efficient set of paths to gather data, and deliver it at the sink, while not violating constraints. We focus on this type of application because, as previously said, new applications are expected to appear in a near future and the delivery limit will be, very likely, an important issue. A heuristic algorithm for delivery limited data gathering has been initially proposed in [13]. Here, in this article, we mathematically formalize the data gathering problem using UAVs, allowing for a better understanding of the problem and for the proposal of an improved heuristic approach with extra improvement procedures incorporated in it. The performance of the heuristic is also compared against optimal solutions.

The remainder of the article is organized as follows. Section 2 discusses data gathering approaches that can be applied to wireless sensor networks and current state of the art. The data gathering problem is defined and mathematically formalized in Sect. 3. The proposed hybrid heuristic approach is presented in Sect. 4, together with a detailed discussion on seeding, constructive solution building and improvement procedures. Section 5 analyses results obtained, making a performance evaluation of the heuristic and comparison with optimal solutions, and Sect. 6 finishes the article with conclusions and future work.

2 Data Gathering in Wireless Sensor Networks

2.1 Data Gathering Approaches

In sensor networks data can be gathered using: (1) classical approach, where there is an infra-structured network; (2) terrestrial mobile elements, such as robots; (3) UAV elements, which are capable of flying. Each of these has its own pros and cons, summarized in Table 1.

Table 1 Comparison between data gathering approaches (adapted from [20])

2.1.1 Classical Networks

In classical networks data is transferred from the sensor node to the base station using the network infrastructure itself. Due to energy constraints, the throughput in such sensor networks is very limited, usually reaching just a few Kbps. Since transmission is the most energy demanding task that sensor nodes perform, communication must be used only when it is strictly necessary, so that network lifetime increases. This concern becomes even more important when multi-hop communication is required. The main advantage of this approach is the small delay associated with the delivery of data, which can reach a few seconds or even less.

2.1.2 Networks with Terrestrial Elements

This approach uses mobile robots to collect the data from sensors for later delivery to a base station where data is processed. In this case bandwidth is high, capable of achieving a few Mbps. The downside issue of this approach is the time delay between data collection and its delivery to the base station. Since the travelling speed of terrestrial elements is considerably low, in most cases less than a meter per second, the delay between collecting data at the sensor and processing it at the base station is significant [19].

Similarly to the previous approach, a power consumption problem also arises. Power consumption at mobile elements is very high because mobile elements have considerable size and many nodes must be visited for all data to be gathered. However, replenishing the power source of the mobile element is not a problem in this case. This approach can fully eliminate multi-hop communication at the expense of delay.

2.1.3 Network with UAV Elements

An UAV approach is in all similar to the previous approach. The main advantage now is the drastic reduction of the delay. The UAV elements have flying capabilities with a travelling speed much higher than terrestrial elements, meaning that data scattered across many sensor nodes can be collected more quickly and efficiently [18]. In this article we assume the use of UAV elements.

2.2 State of The Art

Data collection problems in sensor network nodes can have many types of goals. Two common goals are to minimize the time/distance required for data collection, as in [1, 3, 17], and minimize the energy consumed when collecting data, as in [2, 7, 20].

In [3] all sensor nodes must be visited in such a way that the time expended to perform this task is minimized. This problem is a variation of k-Travel Salesman Problem. In [1] the problem has time window constraints meaning that sensor nodes must be visited within their time windows, which is the period of time when the node is awake and capable to communicate. This problem is a straightforward adaptation of Vehicle Routing Problem with Time Windows (VRPTW) in a sensor network. In [17] a set of sensor nodes with limited buffer sizes and different sampling rates must be visited before their buffer overflows, which can be seen as a VRPTW where the deadlines to visit nodes correspond to one-sided time windows.

Concerning energy consumption, in [20] the goal is to find a set of intermediate buffer nodes (rendezvous points) where the data from the sensor nodes is stored. Mobile elements must visit these rendezvous points within a required deadline to gather the data and deliver it to the destination. This problem can be viewed as a VRP where the data must be picked up at rendezvous points and delivered to the destination. In [7] the problem is to build a path for a mobile data collecting robot such that the total data collection cost (i.e., sum of transmission energy of the sensor nodes and movement energy of the robot) in a sensor network is minimized. In [2] an energy aware trajectory computation of mobile data collectors is discussed. Both [2, 7] can be seen as routing problems.

The problem under discussion in our article is more complex than the one in [20] because there are two time related constraints per node. In our work, time window constraints are used to collect data within a deadline, and deliver it to the base station, due to the awake period of sensor nodes, and deadline constraints are used to ensure that data does not arrive outdated. The first basically addresses energy consumption concerns. In [20] the selected nodes to become rendezvous points, and base station also, have a time window constraint only.

3 Data Gathering Problem Formalization

3.1 Assumptions

A generic data gathering problem (DGP) consists in collecting the data from a set of nodes using a set of UAVs. Let us define a graph ${\mathcal {G}}= ({\mathcal {N}},{\mathcal {E}})$ where ${\mathcal {N}} = \{n_0, n_1, \ldots , n_{|{\mathcal {N}}|-1} \}$ is a set of vertices and ${\mathcal {E}} \subset \{(i,j) : i,j \in {\mathcal {N}}\}$ is a set of edges. The set of nodes includes a subset containing only sensor nodes ${\mathcal {C}} = {\mathcal {N}} \setminus \{n_0, n_{|{\mathcal {N}}|-1}\}$ to be visited, and two nodes, $n_0$ and $n_{|{\mathcal {N}}|-1}$, that are the starting and ending points for all paths of the UAVs. The starting and ending points are actually the same place, meaning that node $n_{|{\mathcal {N}}|-1}$ can be seen as a virtual node used for mathematical formalization purposes.

Regarding the set of edges, ${\mathcal {E}}$, this contains links for all pairs of nodes, base station included. That is, a complete graph is assumed since an UAV may travel directly to any node. Every edge has a weight $w_{n_i,n_j}$ and a time $t_{n_i,n_j}$, $\forall (n_i,n_j) \in {\mathcal {E}}$. The weight $w_{n_i,n_j}$ represents the cost associated with the travel from node $n_i$ to node $n_j$, while $t_{n_i,n_j}$ represents the time required to travel from node $n_i$ to node $n_j$, $\forall n_i,n_j \in {\mathcal {N}}$. Here it is assumed that the $w_{n_i,n_j} = t_{n_i,n_j} = d_{n_i,n_j}$ where $d_{n_i,n_j}$ is the euclidean distance between nodes $n_i$ and $n_j$. The developed algorithm is, however, generic and can perform optimization even in cases where the equality is not met.

The set of UAVs will be denoted by ${\mathcal {V}}$ and each UAV $v \in {\mathcal {V}}$ has its own buffer/queue size $q_v$ in bytes. Each sensor node $n \in {\mathcal {C}}$ has $b_{n}$ bytes of data to be gathered, and the total data gathered by an UAV can not exceed its buffer.

A node $n \in {\mathcal {N}}$ can have a time window $[st_{n}, et_{n}]$, where $st_{n}$ and $et_{n}$ represent the start and end times of a sensor node, respectively. An UAV can arrive to a node n before its start time but it will have to wait until $st_{n}$ to receive the data. It is assumed that start time at base station begins at $st_{n}=0$. An UAV is not allowed to arrive to a node n after the end time $et_{n}$. It will also be assumed that:

• Each node must be visited only once.

• All paths begin at node $n_0$ and end at node $n_{|{\mathcal {N}}|-1}$, the starting and ending points.

3.2 Problem Definition

To better define the problem it is important to clearly identify the input information required. The following information is given as input:

• Set of sensor nodes and coordinates that identify their position.

• Buffer size and sampling rate of each node, which means that buffers will reach their limit at different times. These determine the time window at each node.

• Set of UAVs, each with a travelling speed and buffer size.

• Throughput during data transfer, which will determine the service time.

• Expiration time of data being collected, which will determine the time deadline for its delivery at the base station.

Thus, if the buffer size and the sampling rate are known then it is possible to estimate the time when the node buffer will be almost full, requiring a transfer of data to an UAV. The transfer process changes according to the buffer size and throughput. To avoid losing the stored data, each node must be visited by an UAV within its time window. Once the data is transferred to the UAV it must be delivered to the base station, for further processing, within a certain deadline, which is determined by the expiration time of collected data and frequency of visits to nodes. Having all this information in mind, the DGP can be defined as follows:

Definition 1

(DGP) Assuming a wireless sensor network graph ${\mathcal {G}}= ({\mathcal {N}},{\mathcal {E}})$, where ${\mathcal {N}}$ is a set of nodes and ${\mathcal {E}}$ is a set of edges, and a set ${\mathcal {V}}$ of UAVs with different limited buffer sizes, design an efficient (lowest cost) set of paths to gather the sensor node data, without violating the time window constraints of nodes, while accomplishing the delivery limit for all data gathered.

This DGP turns out to be more complex than a VRPTW as data collected from a specific node must reach the base station within a certain time, called delivery limit and denoted by $dl_{n}$. That is, data has an expiration label, or time-to-live (TTL), meaning that it can not arrive outdated at the base station. Vehicle routing and scheduling problems are known to be NP-Hard, see [12], meaning that the DGP will also be hard to solve, at least within an acceptable period of time. Therefore, the development of a heuristic approach, to obtain results faster, becomes crucial.

3.3 Mathematical Formalization

The mathematical formalization of a problem allows optimal solutions to be obtained and a better understanding of the problem. Although such exact solutions are difficult to obtain, at least for large networks involving a huge number of variables, this will allow us to measure more accurately the quality of the heuristic for small networks. To be able to make a mathematical formalization of the DGP, we summarized the input information that will be used as follows:

${\mathcal {N}}$ :

Set of nodes, including sensor nodes $\{n_1, \ldots , n_{|{\mathcal {N}}|-2}\}$, base station $n_0$ and virtual base station $n_{|{\mathcal {N}}|-1}$;

${\mathcal {V}}$ :

Set of UAVs;

${\mathcal {C}}$ :

Set of sensor nodes, where ${\mathcal {C}} = {\mathcal {N}} \setminus \{n_0, n_{|{\mathcal {N}}|-1}\}$;

${\mathcal {E}}$ :

Set of edges;

$b_{n_i}$ :

Amount of data to be gathered at node $n_i \in {\mathcal {N}}$;

$st_{n_i}$ :

Start time at the time window of node $n_i \in {\mathcal {N}}$;

$et_{n_i}$ :

End time at the time window of node $n_i \in {\mathcal {N}}$;

$q_{v}$ :

Buffer size of UAV $v \in {\mathcal {V}}$;

$t_{n_i,n_j}$ :

Travel time from node $n_i \in {\mathcal {N}}$ to node $n_j \in {\mathcal {N}}$;

$w_{n_i,n_j}$ :

Cost associated with the travel from node $n_i \in {\mathcal {N}}$ to node $n_j \in {\mathcal {N}}$;

$s_{n_i}$ :

Service time at node $n_i \in {\mathcal {N}}$.

The variables will be:

$\vartheta _{v}$ :

One if UAV $v \in {\mathcal {V}}$ is required for data gathering, zero otherwise;

$\sigma _{n_i,n_j}^v$ :

One if UAV $v \in {\mathcal {V}}$ travels from node $n_i \in {\mathcal {N}}$ to node $n_j \in {\mathcal {N}}$, zero otherwise;

$\varphi _{n_i}^v$ :

Arrival time of UAV $v \in {\mathcal {V}}$ to node $n_i \in {\mathcal {N}}$;

$\kappa ^{n_i}_{n_j,v}$ :

Concerning data belonging to node $n_i \in {\mathcal {C}}$ being carried by UAV $v \in {\mathcal {V}}$, this is the delivery limit value when data reaches node $n_j \in {\mathcal {N}}\backslash \{0\}$. Note that the delivery limit of data will vanish as the UAV traverses nodes.

The objective function of the DGP can be mathematically expressed as:

$$\begin{aligned} \text {min} \sum _{v\in {\mathcal {V}}} \quad \sum _{n_i\in {\mathcal {N}} \setminus \left\{ n_{|{\mathcal {N}}|-1} \right\} } \quad \sum _{n_j\in {\mathcal {N}} \setminus \left\{ n_0 \right\} } w_{n_i,n_j}\sigma _{n_i,n_j}^v \end{aligned}$$

(1)

This objective function minimizes the total traveling cost, which is basically all total distance traversed by all UAVs. Due to the return path, for data delivery at the base station, the use of many vehicles will be indirectly avoided. The constraints are the following:

• Arriving and Departing UAVs at Nodes:

  $$\begin{aligned}&\sum _{v \in {\mathcal {V}}} \quad \sum _{n_j \in {\mathcal {N}} \setminus \left\{ n_0 \right\} } \sigma _{n_i,n_j}^v = 1, \forall n_i \in {\mathcal {C}} \end{aligned}$$

  (2)
  $$\begin{aligned}&\sum _{v\in {\mathcal {V}}} \quad \sum _{n_i\in {\mathcal {N}} \setminus \left\{ n_{|{\mathcal {N}}|-1} \right\} }\sigma _{n_i,n_j}^v = 1, \forall n_j \in {\mathcal {C}} \end{aligned}$$

  (3)

• Non Violation of Buffer Limit at UAVs:

  $$\begin{aligned} \sum _{n_i \in {\mathcal {C}}} b_{n_i} \sum _{n_j \in {\mathcal {N}} \setminus \left\{ n_0 \right\} }\sigma _{n_i,n_j}^v < q_{v}, \forall v \in {\mathcal {V}} \end{aligned}$$

  (4)

• Flow Conservation Law of Paths:

  $$\begin{aligned} \sum _{n_j \in {\mathcal {N}} \setminus \left\{ n_0 \right\} }\sigma _{n_0,n_j}^v = \vartheta _{v}, \forall v \in {\mathcal {V}} \end{aligned}$$

  (5)
  $$\begin{aligned} \begin{aligned}&\sum _{n_i \in {\mathcal {N}} \setminus \left\{ n_{|{\mathcal {N}}|-1} \right\} } \sigma _{n_i,n_k}^v - \sum _{n_j \in {\mathcal {N}} \setminus \left\{ n_0 \right\} } \sigma _{n_k,n_j}^v = 0, \\&\forall v \in {\mathcal {V}}, \forall n_k \in {\mathcal {C}} \end{aligned} \end{aligned}$$

  (6)
  $$\begin{aligned} \sum _{n_i \in {\mathcal {N}} \setminus \left\{ n_{|{\mathcal {N}}|-1} \right\} } \sigma _{n_i,n_{|{\mathcal {N}}|-1}}^v = \vartheta _{v}, \forall v \in {\mathcal {V}} \end{aligned}$$

  (7)

• Arrival Time at Nodes:

  $$\begin{aligned} \varphi _{n_0}^v= & {}\, 0, \quad \forall v \in {\mathcal {V}} \end{aligned}$$

  (8)
  $$\begin{aligned}&\varphi _{n_i}^v + s_{n_i} + t_{n_i,n_j} - K \times (1-\sigma _{n_i,n_j}^v) \le \varphi _{n_j}^v, \forall v \in {\mathcal {V}},\nonumber \\&\forall n_i \in {\mathcal {N}} \setminus \left\{ n_{|{\mathcal {N}}|-1} \right\} , \forall n_j \in {\mathcal {N}} \setminus \left\{ n_0 \right\} , n_i \ne n_j \end{aligned}$$

  (9)
  $$\begin{aligned}&st_{n_i} \times \vartheta _{v} \le \varphi _{n_i}^v \le et_{n_i} \times \vartheta _{v}, \forall v \in {\mathcal {V}}, \forall n_i \in {\mathcal {N}} \end{aligned}$$

  (10)

where K is a big value.

• Delivery Limit of Data:

  $$\begin{aligned} \kappa ^{n_i}_{n_i,v}=dl_{n_i} \times \sum _{n_j \in {\mathcal {N}}\backslash \{n_0\}}\sigma _{n_i,n_j}^v, \forall n_i \in C, \forall v \in {\mathcal {V}} \end{aligned}$$

  (11)
  $$\begin{aligned} \begin{aligned}&\kappa ^{n_k}_{n_i,v} - s_{n_j} - t_{n_i,n_j} + K \times (1-\sigma _{n_i,n_j}^v) \ge \kappa ^{n_k}_{n_j,v}, \\&\forall k \in {\mathcal {C}}, \forall v \in {\mathcal {V}}, \forall n_i \in {\mathcal {C}},n_j \in {\mathcal {N}}\backslash \{0\} \end{aligned} \end{aligned}$$

  (12)

• Non Negative and Binary Assignments:

  $$\begin{aligned} \begin{aligned}&\vartheta _{v},\sigma _{n_i,n_j}^v \in \{0,1\}; \varphi _{n_i}^v, \kappa ^{n_i}_{n_j,v} \ge 0, \forall v \in {\mathcal {V}}, \forall n_i \in {\mathcal {N}}, \\&\forall n_j \in {\mathcal {N}} \end{aligned} \end{aligned}$$

  (13)

Constraints (2) and (3) ensure that a single UAV arrives and departs to/from a node, respectively. That is, a node is being served by a single UAV. Constraints (4) ensure that data collected by an UAV does not exceed its buffer size. Constraints (5), (6) and (7) ensure the flow conservation law of paths being built. That is, if an UAV is to be used then it must emanate from the source, must pass through some intermediate nodes and arrive to the base station. Otherwise, no path is created for that UAV. Constraints (8) indicate that all UAVs start the gathering process at instant zero, Constraints (9) indicate that an UAV can not arrive at node $n_j$ before $\varphi _{n_i}^v + s_{n_i} + t_{n_i,n_j}$ if it travels from $n_i$ to $n_j$, and Constraints (10) state that time window restrictions must be fulfilled. Constraints (11) and (12) ensure that the delivery limit value, of data collected at any node $n \in {\mathcal {C}}$, decreases until the base station is reached. Such decrease takes the travel and service times into consideration. Since all variables are non-negative, ensured by Constraint 13, data will not arrive outdated to the base station.

4 Hybrid Heuristic Approach

Finding the exact optimal solution for the DGP optimization problem may become impractical because of its combinatorial nature. For this reason an hybrid heuristic approach is proposed. This includes two steps:

• DGP-Adjusted Push Forward Insertion Heuristic: This is used to find an upper bound solution for the problem using a constructive heuristic approach. Constructive heuristics are fast and, if well designed, can produce good results.

• Solution Improvement: Since constructive heuristics are usually greedy methods, i.e., at each iteration the decision is made using a local criteria, the final solution may be far from optimal, offering room for improvements. At this step, improvement heuristics, which incorporates an existing feasible solution as a starting point, are used. Three improvement approaches, discussed in the following sections, have been used: Neighbourhood Ejection, 2-Opt and Crossover.

4.1 DGP-Adjusted Push Forward Insertion Heuristic

Constructive heuristics, such as the original Push Forward Insertion Heuristic (PFIH) proposed by Solomon [15], build the solution in an iterative way. These heuristics start with an empty solution and at each iteration the current solution is extended. This is done until a complete solution is built. Since PFIH is greedy and starts with an empty solution, the solutions produced can be far from the optimal. For this reason, besides adapting PFIH for DGP purposes, an initial partial solution creation procedure is also used.

4.1.1 Build Initial Partial Solution

A partial solution can be built before DGP-Adjusted PFIH is executed. That is, nodes can be inserted into the routes as long as a feasible solution is produced. To substantially improve the quality of the solution provided by DGP-Adjusted PFIH, nodes should be carefully selected.

Given the average number of bytes to be gathered at sensor nodes, $\frac{\sum _{n \in {\mathcal {C}}} b_{n}}{|{\mathcal {C}}|}$, and the average buffer size of the UAVs, $\frac{\sum _{v \in {\mathcal {V}}} q_{v}}{|{\mathcal {V}}|}$, it is possible to estimate the minimum number of paths that will be required. This will be a lower bound for the required paths/UAVs because time restrictions and time conflicts are not being taken into account. These will be handled by the DGP-Adjusted PFIH heuristic latter, which may create new paths if necessary. This approach has been chosen because an excessive, and unnecessary, number of initial paths can reduce the quality of the solution.

The initial partial solution, also called seed list, should include as many nodes as the number of initial paths and a single node should be included at each initial path, $n_0 \rightarrow n_k \rightarrow n_{|{\mathcal {N}}|-1}$, where $n_k$ is a sensor node from the seed list. At this stage, each UAV will gather data from a single sensor node. Such nodes will be chosen according to their geographical location so that the seed list includes a set of highly dispersed nodes. This is summarized in Algorithm 1.

The DGP-Adjusted PFIH will receive the partial solution generated by Algorithm 1 and insert the remaining nodes at paths where the insertion causes the smallest increment of distance while keeping the solution feasible.

4.1.2 Run DGP-Adjusted PFIH using Initial Partial Solution

The original PFIH basically sorts all nodes using the following PFIH cost function:

$$\begin{aligned} c_{n_i} = -\alpha \times d_{n_i,n_0} + \beta \times et_{n_i} + \gamma \times \frac{p_{n_i}}{360}\times d_{n_i,n_0} \end{aligned}$$

(14)

where $d_{n_i,n_0}$ is the distance between node $n_i$ and the base station, $et_{n_i}$ is the end time of node $n_i$’s time window, $p_{i}$ is the polar angle between node $n_i$ and the base station, and $\alpha + \beta + \gamma = 1$. A larger value for $\alpha$ will render distance the dominant factor, a larger value for $\beta$ will render closing window the dominant factor, while a larger value for $\gamma$ renders the insertion of nodes in a circular, spinning mechanism, the dominant factor. Usually, $\alpha$, $\beta$ and $\gamma$ are empirically established.

The DGP-Adjusted PFIH, used by the proposed hybrid heuristic approach, extends expression (14) in order to incorporate the difference between the end and start times of each node, $st_{n_i}$ and $et_{n_i}$, and the delivery limit of each one, $dl_{n_i}$, as follows:

$$\begin{aligned} c^{DGP}_{n_i}= & {} -\alpha \times d_{n_i,n_0} + \beta \times et_{n_i} + \nonumber \\&\quad +\, \gamma \times \frac{p_{n_i}}{360}\times d_{n_i,n_0} + \lambda \times (et_{n_i} - st_{n_i}) + \tau \times dl_{n_i} \end{aligned}$$

(15)

where $\lambda$ and $\tau$ are additional weight parameters, and $\alpha + \beta + \gamma + \lambda + \tau = 1$. Larger values for $\lambda$ will render time window the dominant factor, while larger values for $\tau$ will render delivery limit the dominant factor. For the DGP under analysis the best results were obtained when setting the weights as follows: $\alpha =0.4$, $\beta =0.2$, $\gamma =0.1$, $\lambda =0.1$ and $\tau =0.2$. The DGP-Adjusted PFIH will be used to establish the upper bound of the problem. The solution produced by this heuristic will be used as input information for the next improvement heuristics.

4.2 Solution Improvement

At this step improvement heuristics, which start working with an already existing and feasible solution, are used. At each iteration the improvement heuristics explore the neighbourhood of the current solution to find a better one. The hybrid heuristic approach includes the following improvement approaches:

4.2.1 Neighbourhood Ejection

This method selects a path and, for each node located in it, ejects a certain number of neighbour nodes (from that selected path or other paths). The ejection can be done using many criteria:

• Random: a random number of neighbour nodes is selected for ejection;

• PFIH cost: neighbour nodes are ejected according to their PFIH cost, previously defined;

• Proximity: nodes from distant neighbourhoods are ejected;

• Similarity: similar/distinct neighbour nodes are ejected.

In our case the similarity of time constraints will be used as a criteria for ejection. Removing nodes from more distant neighbourhoods, with completely different time constraints, becomes inefficient since the probability of a future reinsertion for reduction of distance and number of paths (solution improvement) is considerably low. This means that only nearby nodes with similar time constraints should be ejected. This method can significantly improve the solution given as input.

The neighbourhood ejection procedure is described in Algorithm 2. Paths are chosen using a roulette method inspired by the rank selection used in genetic algorithms [10].

4.2.2 Local Search Using Inter-Route and Intra-Route Neighbourhood

Local search is an improvement heuristic and, as such, it needs an initial solution as input [4]. The local search operators to be used can, in general, be divided into intra-route and inter-route. Intra route operators perform operations on a single route at a time, rearranging the sequence of nodes in a route in order to make it more efficient. On the other hand, inter route operators perform operations on two routes. These methods swap or rearrange the nodes between two routes in order to improve their quality and, consequently, to improve the solution. The intra-route and inter-route operators applied at the hybrid heuristic are the 2-Opt and Crossover, respectively.

Figure 1a illustrates the use of the 2-Opt. The sequence by which nodes are visited at the initial solution generated by the DGP-Adjusted PFIH, is rearranged so that the distance of paths is reduced. The base stations represent the start and the end points of each path, which in our case is the same place. In this specific case, the sequence of the first path changed from $BS \rightarrow 3 \rightarrow 11 \rightarrow 7 \rightarrow 2 \rightarrow BS$ to $BS \rightarrow 11 \rightarrow 7 \rightarrow 3 \rightarrow 2 \rightarrow BS$, nodes 9 and 1 were swapped at the second path, and at the third path there were no changes (i.e., any possible change would increase the distance of the path length). The criteria to choose the nodes to be swapped, so that the solution given by the DGP-Adjusted PFIH is improved, was the similarity of their location and time constraints.

Fig. 1

Illustration of route operators. a Intra route operator, b inter route operator

Figure 1b illustrates the use of the Crossover. This method reallocates a node, or a set of nodes, from one path to another in order to optimize the current solution (i.e, reduce distance). Here, a single point crossover operator is used that takes two paths as input, makes reallocation and, if feasible, returns two new paths. The input paths are $BS \rightarrow 4 \rightarrow 8 \rightarrow 1 \rightarrow 5 \rightarrow 3 \rightarrow BS$ and $BS \rightarrow 7 \rightarrow 2 \rightarrow 6 \rightarrow 9 \rightarrow BS$. The crossover point that will determine reallocation is at the third position. The new routes are $BS \rightarrow 4 \rightarrow 8 \rightarrow 6 \rightarrow 9 \rightarrow BS$ and $BS \rightarrow 7 \rightarrow 2 \rightarrow 1 \rightarrow 5 \rightarrow 3 \rightarrow BS$. The criteria to choose the Crossover point was also the similarity of the location and time constraints of nodes.

Local search operators may reduce distances by optimizing paths. However, these are not able to reduce the number of paths, which is ensured by the neighbourhood ejection procedure previously described. The local search procedure is applied as shown in Algorithm 3.

4.3 Overall Operation of Proposed Heuristic

After discussing the key pieces of the heuristic algorithm we proceed with the presentation and discussion of its overall operation. Algorithm 4 shows the pseudo code.

Lines 1–3 are the initialization steps of the DGP-Adjusted PFIH algorithm. Line 1 generates a highly dispersed initial partial solution, then the weights required to evaluate $c^{DGP}_{n}$ [see expression (15)] are defined in line 2. This will influence the sequence by which the sensor nodes will be inserted in the solution. The DGP-Adjusted PFIH can then be executed (Line 3) returning a feasible solution, which is stored in CurrentSolution. Initially this is also the best solution, meaning that BestSolution (Line 4) is updated.

From Line 5 to Line 8 a few required settings are defined. The loop in Line 10 will improve the current solution, stored in variable Solution, using different ejection rates. When entering in loop at Line 12, a copy of Solution is done to $Solution'$ so that the current solution can be restored if there is no improvement. Line 14 makes neighbourhood ejection and updates the solution. The ejected nodes are reinserted in Line 15. Further solution improvements using the 2-Opt and Crossover operators is done at Lines 16 and 17. Line 18 tests the potential of the solution obtained. That is, if the solution obtained does not increase the number of routes and it is better than, or approaches, the stored solution then it should be stored in $Solution'$, for further improvement, or replace $Solution^*$ if in fact it is better than the currently stored optimal. This way, the solution obtained can be further improved if it is temporarily slightly worse than the stored one. The value used for Th will determine the extend of such scanning.

5 Simulation and Analysis of Results

In this section the performance of the hybrid heuristic approach is analysed. To make this evaluation the sets of VRPTW instances (network topologies) with 100 nodes, from Solomon’s benchmark [16], were used. The VRPTW instances provide, for each node, the coordinates, demand, time window and service time. For the vehicles there is also information about their capacity. The DGP under study, however, also requires the definition of the delivery limit for nodes, $dl_{n}$. To define them we need to have in mind that the lowest possible delivery limit will be the time required to return to the depot, i.e., $dl^{MIN}=max_{n_i \in {\mathcal {N}}}\{d_{n_0,n_i}\}$. Also, it makes no sense to use a delivery limit that exceeds the end time value of the base station. This value determines the arriving deadline to the base station, which must be accomplished, meaning that delivery limits higher than this value will have no effect on the solution. That is, $dl^{MAX}=et_{n_{|{\mathcal {N}}|-1}}$. Therefore, the delivery limit of nodes in an instance should take values from $dl^{MIN}$ to $dl^{MAX}$, where $dl^{GAP}=dl^{MAX}-dl^{MIN}$ is the gap between these bounds. To evaluate different slack levels for the delivery limit the following five ranges have been tested:

$$\begin{aligned} \varDelta _1= & {} [dl^{MIN},dl^{MIN}+20\%dl^{GAP}] \\ \varDelta _2= & {} [dl^{MIN}+20\%dl^{GAP},dl^{MIN}+40\%dl^{GAP}] \\ \varDelta _3= & {} [dl^{MIN}+ 40\%dl^{GAP},dl^{MIN}+60\%dl^{GAP}] \\ \varDelta _4= & {} [dl^{MIN}+ 60\%dl^{GAP},dl^{MIN}+80\%dl^{GAP}] \\ \varDelta _5= & {} [dl^{MIN}+ 80\%dl^{GAP},dl^{MIN}+100\%dl^{GAP}]\\ \end{aligned}$$

When using a specific instance, the delivery limit of a node will be a random number at the range under consideration.

The VRPTW instances include 6 different sets: R1 and R2 having randomly generated geographical data, sets C1 and C2 having clustered geographical data, and sets RC1 and RC2 having a mix of randomly and clustered geographical data. Sets R1, C1 and RC1 have a short scheduling horizon while sets R2, C2 and RC2 have a long scheduling horizon, allowing more sensor nodes to be served by the same UAV. At each set, the vehicle (UAV in our case) capacity and service time do not change between instances.

5.1 Optimal Versus Heuristic Solutions for Sets C1 and C2

The optimal solutions from the discussed mathematical formalization were obtained using CPLEX¹ package. Due to the complexity of the problem, only solutions for C1 and C2 instances, assuming delivery limit ranges $\varDelta _3$, $\varDelta _4$ and $\varDelta _5$, could be obtained. When nodes are randomly distributed (R1, R2, RC1 and RC2) CPLEX takes too much time to converge to a solution. The same happens for tighter delivery limits, $\varDelta _1$ and $\varDelta _2$, for any instance set.

Table 2 show the optimal and heuristic values obtained for $\varDelta _3$, $\varDelta _4$ and $\varDelta _5$, respectively. The coloured rows highlight the instances where there is more similarity between heuristic and optimal values throughout different values of $\varDelta$. From this results it is possible to state that the heuristic performs better under the following conditions:

• Very high maximum time window sizes (C202, C203, C204);

• Medium/high maximum time window sizes with a relatively high average time window size, meaning that there are more nodes with large time windows (C103, C104);

• When the maximum, average and minimum time window sizes are equal, but only for the highest values (C109, C205, C208);

• Low/medium maximum time window sizes, but only when the minimum and average time window sizes approach the maximum time window size (C108).

Thus, the heuristic performs better when time windows are large or when the variability of time windows is low, meaning that the choices made by the algorithm are less risky. This might indicate that different strategies could exist for different types of sets. That is, sets with highly variable time windows could render $\lambda$ the dominant factor, while for the remaining sets other factors would dominate. That is, $\alpha$, $\beta$, $\gamma$, $\lambda$ and $\tau$ should dynamically follow the intrinsic nature of the sets.

Table 2 Solutions for Delivery Limits at Range $\varDelta _3$, $\varDelta _4$ and $\varDelta _5$

5.2 Heuristic Solutions for all Sets

The following plots relate to the total distance travelled by the UAVs, and the total number of paths/UAVs required, obtained by the heuristic approach for all sets. Sets C1, C2, R1, R2, RC1 and RC2 include between 8 and 12 instances and, although the capacity of vehicles and service time is the same for all instances of a set, the demand, time window and delivery limit of nodes will be different from instance to instance. This means that there might be different performances for different instances. For this reason, the solution’s distance and number of UAVs of instance i undergoes the following formulas so that the increasing factor (IF) of each instance is obtained:

$$\begin{aligned} IF^{Distance}_i= & {} \frac{Distance_i - Distance^*_i}{Distance^*_i} \end{aligned}$$

(16)

$$\begin{aligned} IF^{NumUAV}_i= & {} \frac{NumUAV_i - NumUAV^*_i}{NumUAV^*_i} \end{aligned}$$

(17)

where $Distance_i$ and $NumUAV_i$ is the distance and number of UAVs obtained by the proposed hybrid heuristic and $Distance_i^*$ and $NumUAV_i^*$ are the best known solutions identified by heuristics for the VRPTW, obtained from [16]. The best known results from VRPTW have been used because no DGP best known results are known, and also because DGP gets similar to VRPTW as the delivery limit approaches infinity.

Figure 2 relates to distances and shows the minimum, average and maximum distance increase factor, considering all instances of a set, for all sets under analysis and different delivery limit ranges. The minimum and maximum can be seen as the lower and upper bounds of algorithm’s performance. From these three plots it is possible to observe that, as the delivery limit range becomes less tight the more the solutions obtained by the hybrid heuristic closely approximate the best known solutions for the VRPTW. Therefore, we can state that the proposed hybrid heuristic algorithm is expected to be a good approach for the DGP. The clustered sets C1 and C2 are the ones for which the hybrid heuristic performs worse. Therefore, this algorithm is more suitable for topologies having dispersed nodes.

Fig. 2

Distance increase factor (IF): lowest/average/highest value from each set of instances

Concerning the lowest and highest distance increase factors the smallest the difference between them the higher the certainty degree for a specific set. That is, if a small difference is obtained for a specific set then the outcome of the algorithm is more predictable whatever the network scenario (instance), fitting into that set, is used. Therefore, although the clustered sets perform worse, its performance is quite good, with a high certainty degree, for many ranges ($\varDelta _2$ to $\varDelta _5$). The certainty degree is also high for the other sets.

Figure 3 also relate to lowest, average, and highest increase factors, but now concerning the number of UAVs. We can observe that sets R2, C2 and RC2 with a long scheduling horizon, allowing more sensor nodes to be served by the same UAV, are the ones with an higher increase factor. This is so because delivery limits override the long scheduling horizon, avoiding UAVs to serve many sensor nodes. Therefore, the gap between DGP and VRPTW solutions will be higher. However, for ranges $\varDelta _2$ to $\varDelta _5$ the number of UAVs reduces significantly, also with high certainty degree. Since with sets R1, C1 and RC1, with short scheduling horizon, the hybrid heuristic algorithm closely approaches the best known solutions for the VRPTW, we can reconfirm that the proposed hybrid heuristic algorithm is expected to be a good approach for the DGP.

Fig. 3

UAV increase factor (IF) : lowest/average/highest value from each set of instances

6 Conclusions and Future Work

This article focus on data gathering using UAVs. The goal is to design efficient paths to gather data that has a time delivery limit associated with it. A mathematical analysis of the problem is presented together with a hybrid heuristic approach that incorporates solution improvement mechanisms suitable for data gathering purposes. Results show that the heuristic is able to solve the problem efficiently presenting, for most data sets and time delivery deadline ranges, high quality solutions. Clues on how to adjust parameters, according to the nature of the data set, are also given.

Future work will focus on tuning the algorithm parameters and making it more generic and capable to deal with other variations of the problem, such as multiple base stations and dynamic nodes that can appear during the execution of the algorithm. Another feature that will be incorporated into the algorithm is the use of self-managing node clusters where one of the nodes acts as the data collector.