Open AccessEditor’s ChoiceArticle

Asymptotically Optimal Deployment of Drones for Surveillance and Monitoring

Andrey V. Savkin

and

Hailong Huang

School of Electrical Engineering and Telecommunications, University of New South Wales, Sydney 2052, Australia

Author to whom correspondence should be addressed.

Sensors 2019, 19(9), 2068; https://doi.org/10.3390/s19092068

Submission received: 8 April 2019 / Revised: 28 April 2019 / Accepted: 30 April 2019 / Published: 3 May 2019

(This article belongs to the Special Issue Deployment and Navigation of Aerial Drones for Surveillance and Monitoring)

Download

Browse Figures

Versions Notes

Abstract

This paper studies the problem of placing a set of drones for surveillance of a ground region. The main goal is to determine the minimum number of drones necessary to be deployed at a given altitude to monitor the region. An easily implementable algorithm to estimate the minimum number of drones and determine their locations is developed. Moreover, it is proved that this algorithm is asymptotically optimal in the sense that the ratio of the number of drones required by this algorithm and the minimum number of drones converges to one as the area of the ground region tends to infinity. The proof is based on Kershner’s theorem from combinatorial geometry. Illustrative examples and comparisons with other existing methods show the efficiency of the developed algorithm.

Keywords:

drones; UAVs; aerial surveillance; aerial monitoring; coverage control; triangular coverage; flying robots; internet of flying robots; internet of drones; Kershner’s theorem

1. Introduction

Unmanned Aerial Vehicles (UAVs) (also referred to as drones or flying robots) are quickly becoming more and more important in numerous real life applications [1], including ground traffic surveillance [2,3], precision agriculture and inspection of agricultural fields [4], aerial goods delivery [5,6,7], infrastructure monitoring and inspection [8,9,10,11], 3D surface reconstruction [12], providing wireless communication [13,14,15,16,17,18,19,20,21], natural disaster areas surveillance [22], rescue missions, and ground monitoring for security purposes [23,24,25,26,27,28,29,30,31,32,33]. A significant class of such UAV problems consists of various drone placement problems. For infrastructure monitoring, the fundamental problem is the coverage path planning, i.e., the drones can completely inspect the infrastructure during the movement along their trajectories [8]. For providing wireless communication, the question of where to locate UAV base stations to guarantee communications to users in either natural disaster areas or during popular celebration type events so that the users can receive acceptable communication service is an important issue [16]. For surveillance and monitoring, an important problem is where to place aerial surveillance drones to monitor all points of a region of interest [22].

In surveillance applications, a typical situation is that a fleet of drones, carrying some specific sensors such as ground-facing cameras, monitors some ground objects for the purpose of surveillance. The cameras can see a disc on the ground, and the altitude of the drone, as well as the visibility angle, have significant impacts on this visible region. In this kind of application, a significant technical problem is to deploy the minimum number of drones to cover a given area of ground completely. This important problem attracts both researchers and industry practitioners since this number is closely related to the system total cost.

The above problem of minimization of the number of drones for monitoring is addressed in the current manuscript. We develop a method of deployment a number of drones so that every point of a given ground region is seen from at least one drone. Moreover, we prove that the proposed deployment is asymptotically optimal in the sense that the ratio of the number of drones deployed and the minimum possible number of drones needed to cover the ground region converges to 1 as the area of the ground region tends to infinity. This theoretical result is derived from the so-called Kershner’s theorem [34], a powerful and elegant tool of combinatorial geometry. Furthermore, the proposed algorithm is based on constructing a triangulation of the ground plane consisting of congruent equilateral triangles, and not all but most of the drones are deployed at the vertices of triangulation. This makes the proposed method easily understandable and very computationally efficient. Moreover, the proposed algorithm results in a deployment in which positions of drones are separated from each other, which greatly reduces the danger of collisions. To the best knowledge of the authors, there are no other publications presenting such an efficient method to deploy drones to fully cover a given region that lead to placement of drones in a regular triangular pattern.

The rest of the manuscript is structured as follows. The problem statement is given in Section 2. The developed deployment algorithm and the main results characterizing asymptotic optimality of the algorithm are stated in Section 3. Mathematically rigorous proofs of the main results are also presented in Section 3. Section 4 contains illustrative examples of applying the proposed UAV placement algorithm, together with comparisons with another UAV placement algorithm. A summarizing conclusion is given in Section 5.

2. Problem Statement

Let

(x, y)

be Cartesian coordinates on the ground plane and z be the coordinate axis perpendicular to the ground plane, where the equation

z = 0

describes the ground plane itself. Moreover, let

D

be a given bounded and Lebesgue measurable region [35] of the ground plane

z = 0

with piecewise smooth boundary. Our objective is to deploy a number of drones to monitor the corresponding area of the ground region

D

. Also, let

Z_{m i n}

and

Z_{m a x}

be the minimum and maximum altitudes for drone deployment,

Z_{m a x} > Z_{m i n} > 0

. Assume that each drone can be deployed only at some points

(x_{d}, y_{d}, z_{d})

such that (Equation (1))

(x_{d}, y_{d}) \in D, z_{d} \in [Z_{m i n}, Z_{m a x}] .

(1)

Moreover, drones have a given observation angle

0 < α < π

, which defines the visibility cone of each drone, so that a drone with the coordinates

(x_{d}, y_{d}, z_{d})

can only see points

(x, y, z)

of the ground that are inside of the circle of radius (Equation (2))

\begin{matrix} r : = tan (\frac{α}{2}) z_{d} \end{matrix}

(2)

centred at

(x_{d}, y_{d})

. A point P on the terrain is visible from a drone if P is inside of the visibility cone of the drone, see Figure 1.

Definition 1.

Deployment of a number of drones is said to be covering if the constraints (1) are satisfied and every point on the ground region

D

can be seen by at least one of the drones.

It is obvious that when we increase the altitude of a drone, its visibility cone is increasing. Therefore, if there exits a covering deployment at some altitude

z_{d}

then there exists a covering deployment at any altitude z such that

Z_{m a x} \geq z > z_{d}

. In this paper, the goal is to place the UAVs at the lowest possible altitude to reduce the distances between the UAVs and the points of the monitored ground area.

Problem Statement: Let N be the number of drones, and

z_{d}

be a given drone’s altitude satisfying (1). Our aim is to construct, if possible, a covering deployment, i.e., to deploy N drones at the altitude

z_{d}

so that any point of the ground region

D

is seen by at least one drone. Moreover, we want to find the minimum altitude

z_{d}

for which there still exists a covering deployment with N drones.

Remark 1.

Many publications consider various problems of path planning for drones where the objective is to get information about some area of interest, see, e.g., [11,32]. The difference with the problem studied in this paper is that we consider a problem of deploying drones in steady positions to achieve constant surveillance of each point of an area of interest.

Remark 2.

A very effective tool for many drone placement problems is convex programming, see, e.g., [36]. In this paper, we consider the problem of finding the minimum number of drones that cover some given bounded ground area. The conic visibility sector of each drone is indeed convex. However, the union of visibility sectors of several drones is non-convex. Furthermore, the ground area to be covered may be non-convex as well. Therefore, the problem under consideration is non-convex.

3. Deployment Algorithm

On the plane

z = z_{d}

that is parallel to the ground, we will consider triangulations consisting of equilateral triangles with the side

r_{t} = \sqrt{3} r

where r is the radius (2), see Figure 2. Any such triangulation

T (λ, x_{0}, y_{0})

is defined by the angle

λ \in [0, \frac{π}{3})

and the parameters

x_{0}, y_{0}

that are the Cartesian coordinates of some point inside a rhombus with the side

r_{t}

consisting of two equilateral triangles. Here,

λ

is the angle between the coordinate axis x and one of the directions of the triangulation

T (λ, x_{0}, y_{0})

, and

x_{0}, y_{0}

are the coordinates of one of the vertices of this triangulation, see Figure 2. Moreover, for an equilateral triangle, we will consider its centre C and three congruent Voronoi cells consisting of points of the triangle for which a certain vertex of the triangle is closer than the other two vertices [37], see Figure 3.

The proposed deployment algorithm of deployment drones on the plane

z = z_{d}

consists of the following steps.

Step A1: We choose some

λ, x_{0}, y_{0}

and construct the triangulation

T (λ, x_{0}, y_{0})

Step A2: We deploy drones at all vertices of the triangulation

T (λ, x_{0}, y_{0})

that belong to the ground region

D

Step A3: We consider any triangle

W

of the triangulation

T (λ, x_{0}, y_{0})

such that it has some overlap with the ground region

D

but not all the three vertices of the triangle are inside

D

, i.e., some of its vertices were not occupied by drones in Step A2. Let l be the number of such unoccupied vertices of

W

l \in {1, 2, 3}

Step A4: Consider the Voronoi cell of

W

corresponding to some unoccupied vertex of

W

. If this Voronoi cell contains some point of

D

that is not covered by any drone deployed in Step A2, we deploy a drone at the point that is closest to the triangle centre C among all the points of this Voronoi cell belonging to

D

Step A5: If

l \geq 2

, we consider the Voronoi cell of

W

corresponding to some unoccupied vertex of

W

other than considered in A4. If this Voronoi cell contains some point of

D

that is not covered by any drone deployed in Steps A2, A4, we deploy a drone at the point that is closest to the triangle centre C among all the points of this Voronoi cell belonging to

D

Step A6: If

l = 3

, we consider the Voronoi cell of

W

corresponding to the third unoccupied vertex of

W

. If this Voronoi cell contains some point of

D

that is not covered by any drone deployed in Steps A2, A4, A5, we deploy a drone at the point that is closest to the triangle centre C among all the points of this Voronoi cell belonging to

D

Remark 3.

It is obvious that for any triangle fromA3, we deploy no more than l new drones at its vertices.

Proposition 1.

Let an altitude

z_{d}

be given,

Z_{m i n} \leq z_{d} \leq Z_{m a x}

. Then the deployment algorithmA1–A6is covering.

Proof.

It is obvious that the distance between any two points in a certain Voronoi cell of a certain equilateral triangle with side length

\sqrt{3} r

is no greater than r, see Figure 3, where r is defined by (2). Hence, if for any point of the ground region

D

, there exists a drone located at some point of the same Voronoi cell of our triangulation to which this point of

D

belongs to, then point is covered by this drone. It is obvious that the deployment algorithm A1–A6 is placing a drone at some point of any Voronoi cell that contains at least one point of the region

D

. This completes the proof of Proposition 1. □

We will also analyse optimality of the algorithm A1–A6. Let

γ > 1

be some number. Introduce the region

D_{γ}

obtained from the region

D

by the linear transformation that maps any point

(x, y) \in D

to the point

(γ x, γ y)

, see Figure 4. So the region

D_{γ}

is similar to

D

but larger. It is also obvious that (Equation (3))

A (D_{γ}) = γ^{2} A (D)

(3)

where

A (\cdot)

denotes the area of a planar region.

Furthermore, consider some family

F (γ)

of covering deployments of the regions

D_{γ}

for all

γ > 1

. Let

N (γ)

be the number of drones in the deployment

F (γ)

. Let

M (γ)

be the minimum possible number of drones in all covering deployments of the region

D_{γ}

. It is clear that since the region

D_{γ}

increase as

γ

is increases, both

M (γ)

and

N (γ)

tend to infinity as

γ

tends to infinity.

Definition 2.

A family

F (γ)

of covering deployments of the regions

D_{γ}

is said to be asymptotically optimal, if (Equation (4))

lim_{γ \to \infty} \frac{N (γ)}{M (γ)} = 1 .

(4)

In other words, a covering deployment is asymptotically optimal, if as the ground region becomes larger, the number of drones in this deployment becomes close to the minimum possible number of drones for any covering deployment.

Proposition 2.

Let an altitude

z_{d}

be given,

Z_{m i n} \leq z_{d} \leq Z_{m a x}

. Let

F (γ)

be the family of covering deployments of the regions

D_{γ}

constructed by the deployment algorithmA1–A6. Then

F (γ)

is asymptotically optimal. Moreover, (Equation (5))

lim_{γ \to \infty} \frac{N (γ)}{γ^{2}} = \frac{2 A (D)}{3 \sqrt{3} {tan}^{2} (\frac{α}{2}) z_{d}^{2}} .

(5)

Proof.

Indeed, let

\hat{N} (γ)

be the number of vertices of the triangulation

T (λ, x_{0}, y_{0})

constructed in Step A1 such that there is at least one triangle of this triangulation with its vertex intersecting with the region

D_{γ}

. Then it is obvious that (Equation (6))

lim_{γ \to \infty} \frac{N (γ)}{\hat{N} (γ)} = 1 .

(6)

Furthermore, covering a ground region by the minimum number of drones deployed at altitude

z_{d}

is equivalent to covering the minimum number of discs of radius r, where r is defined by (2). Introduce the variable

ϵ : = r γ^{- 1}

. It is obvious that

ϵ \to 0

γ \to \infty

. Therefore, the problem of covering the region

D_{γ}

by the minimum number of discs of radius r as

γ \to \infty

is equivalent to the problem of covering the region

D

by the minimum number of discs of radius

ϵ

ϵ \to 0

. Therefore, (5) and Kershner’s theorem [34] imply the statement of this proposition. This completes the proof of Proposition 2. □

Let N be the number of drones we can deploy. Now we present our deployment algorithm that includes a search for the minimum altitude

z_{d}

Step B1: We start with the altitude

z_{d} : = Z_{m a x}

. We make some search in the space of parameters

(λ, x_{0}, y_{0})

where the angle

λ \in [0, \frac{π}{3})

and the parameters

x_{0}, y_{0}

that are the Cartesian coordinates of some point inside a rhombus with the side

r_{t}

consisting of two equilateral triangles, and apply the deployment algorithm A1–A6 to the triangulation

T (λ, x_{0}, y_{0})

. We take a triangulation that gives a minimal number of drones.

Step B2: We decrease the altitude

z_{d}

by some small value

ϵ > 0

z_{d} : = z_{d} - ϵ

and repeat step B1.

Step B3: We stop when we either reach the minimum altitude

Z_{m i n}

or failed to find a triangulation at the current altitude

z_{d}

for which the algorithm A1–A6 requires no more than N drones.

Remark 4.

InB1, we conduct a complete search for all the feasible configurations of

(λ, x_{0}, y_{0})

. As the triangles in the triangulation are all similar, we can discretise the area into grids with a given resolution and only consider the grids falling into one triangle. At each grid, the angle λ can take value in the range

[0, \frac{π}{3})

. Setting another resolution for λ, a full set of configurations of

(λ, x_{0}, y_{0})

is obtained. Given the triangle side

r_{t}

, the number of the initial configurations depends on the selection of the two resolutions.

Remark 5.

The algorithmB1–B3is a recursive algorithm. It will check a lower altitude if the current altitude enables the full coverage with N drones. In the worst case, this algorithm repeats for

⌈ \frac{Z_{m a x} - Z_{m i n}}{ϵ} ⌉

times.

Remark 6.

It should be pointed out that the proposed algorithmsA1–A6andB1–B3result in deployments in which not all but most drones are placed at vertices of a triangulation consisting of congruent equilateral triangles. This means that the positions of drones are usually sufficiently separated from each other. Such a separation prevents collisions between UAVs, which is crucial for real life UAV systems, see, e.g., [38,39,40].

Remark 7.

A very practically important extension of the obtained results would be the case of complex ground structures, e.g., environments with high-rise buildings causing blocking of view from some drones to certain fragments of the ground area that are inside of drones’ visibility cones. In [29], some method for complete coverage over such complex environments was suggested. However, the method of [29] does result in complete coverage, but does not guarantee optimality in the sense of the current paper. A very important direction of future research will be to combine the method of [29] with optimality approach of the current paper. However, this is a very difficult problem, because it would require obtaining a 3D analogue of Kershner’ theorem [34].

Remark 8.

The reason why we need to place drones in a triangular formation is as follows. We state our problem as finding the minimum number of drones that cover each point of a bounded ground region of interest. Proposition 2 shows that the optimal solution of this problem is a triangular formation. More precisely, it is an almost triangular formation as not all but most of the drones need to be placed at vertices of a triangular grid. Of course, there are many other problem statements which lead to other deployment patterns. Those problem statements may have their advantages in certain real life problems. However, in our problem statement, a triangular deployment is the optimal solution which has been proved in a mathematically rigorous way in Proposition 2.

4. Simulation Results

In this section, computer simulation results and comparisons with [19] are presented to demonstrate the performance of the proposed approach. Consider a region

D

in a 1000 m by 1000 m square, see Figure 5. We take

Z_{m a x} =

120 m,

Z_{m i n} =

30 m (https://bit.ly/2HfWUC4), and

α = \frac{π}{2}

Firstly, the proposed approach is applied to find the minimum number and the positions of drones. Starting from

z_{d} = Z_{m a x}

in Step B1, 3400 configurations of

λ, x_{0}, y_{0}

are randomly generated (the resolution for

λ

takes

\frac{π}{30}

and that for

x_{0}

and

y_{0}

takes 5 m), and then the algorithm A1–A6 is applied to each of them. The deployment which corresponds to the minimum number of drones is recorded. In Step B2,

ϵ

is set as 1 m. With the decrease of

z_{d}

, the number of drones keeps 19; while when

z_{d}

turns to 108 m, the number of drones increases to 20, see Figure 6. Therefore, to fully cover

D

, 19 drones are required and their lowest altitude is 109 m. The corresponding deployment of the 19 drones at the altitude 109 m is demonstrated in Figure 7.

For comparison, the method proposed by [19] is applied to the same case. Given a number of drones, the paper [19] presents a Voronoi cell based approach to maximize the coverage quality, which is modelled as minimizing the weighted distance from the points in the region to drones. To make this method work for the current scenario, the points inside

D

are given the weight 1, while others are given the weight 0. For the altitude

z_{d} = 109

m, the proposed approach requires 19 drones to completely cover

D

. For the compared method, N is first set as 19 and the method [19] is used to compute the corresponding deployment. The drones are deployed at the centres of the Voronoi cells. To completely cover a Voronoi cell, the coverage range of a drone should be a circle and the radius equals the distance from the farthest point in the cell to the centre. Therefore, to cover all the cells at the same altitude, the coverage radius of drones should be the maximum one among all the radii of the Voronoi cells. For

N = 19

, 20 sets of simulations with different initializations are conducted and the smallest radius is 114 m, which corresponds to the altitude 114 m (as

tan (\frac{α}{2}) = 1

). Comparing this with Figure 7 it can be seen that there are more overlaps between circles in Figure 8a than in Figure 7, which results in the fact that to cover the same area with the same number of drones, the method of [19] needs larger radius (i.e., higher altitude) than the proposed approach. Now, the number of drones is decreased by one and the above procedures are repeated. The deployment as shown in Figure 8b is obtained where the coverage radius is 108 m (which is comparable to 109 m), so as the altitude of drones. Therefore, in covering a given area

D

at the same (similar) altitude, the proposed method outperforms [19] in terms of the required number of drones.

Now, Proposition 2 is illustrated through the following simulations. The area of

D

is about 0.41 km². By setting the altitude

z_{d}

as 109 m, the right hand of Equation (5) is 13.2. The parameter

γ

takes values from 1 to 10. For each

γ

, 20 configurations of

λ

x_{0}

, and

y_{0}

are randomly generated. For all these configurations, the triangulations are constructed and the drones are deployed following the algorithm A1–A6. For each

γ

, the deployment that has the lowest number of drones is recorded. The relationship between

\frac{N (γ)}{γ^{2}}

and

γ

is shown in Figure 9. Notice that with the increase of

γ

, the region

D_{γ}

becomes larger. For a fixed altitude

z_{d}

, the coverage radius of the drones r is fixed, so as

r_{t}

. Thus, the number of vertices in the constructed triangulation increases significantly with

γ

, which increases the simulation time dramatically. So, the simulations are conducted only for

γ

up to 10. It can be seen from Figure 9 that

\frac{N (γ)}{γ^{2}}

converges to 13.2, as predicted by Proposition 2. For comparison, the method of [19] is also applied to the cases with different

γ

. Again, the deployments which have the smallest numbers of drones among 20 simulations for each

γ

are recorded. The corresponding

\frac{N (γ)}{γ^{2}}

versus

γ

is shown in Figure 9 as well. Clearly, the proposed approach outperforms the deployment algorithm of [19] in terms of number of drones.

5. Conclusions

A problem of drone deployment for surveillance and monitoring was studied. In this problem, drones equipped with ground-facing cameras are to be placed over a ground region with the aim to observe every point of the region. An easily implementable algorithm for estimating the minimum number of drones and determining their coordinates was obtained. Moreover, the developed algorithm is asymptotically optimal in the sense that the number of drones deployed according to this algorithm is close to the minimum number of drones for large ground regions. Illustrative examples and comparisons with another method showed the efficiency of the proposed approach.

Author Contributions

Conceptualization, A.V.S.; methodology, A.V.S.; software, H.H.; validation, A.V.S, and H.H.; formal analysis, A.V.S.; investigation, H.H.; resources, A.V.S.; data curation, H.H.; writing—original draft preparation, A.V.S.; writing—review and editing, H.H.; visualization, H.H.; supervision, A.V.S.; project administration, H.H.; funding acquisition, A.V.S.

Funding

This work is supported by Australian Research Council.

Conflicts of Interest

The authors declare no conflict of interest.

References

Vachtsevanos, G.J.; Valavanis, K.P. Military and civilian unmanned aircraft. In Handbook of Unmanned Aerial Vehicles; Springer: Berlin, Germany, 2015; pp. 93–103. [Google Scholar]
Kanistras, K.; Martins, G.; Rutherford, M.J.; Valavanis, K.P. Survey of unmanned aerial vehicles (UAVs) for traffic monitoring. In Handbook of Unmanned Aerial Vehicles; Springer: Berlin, Germany, 2015; pp. 2643–2666. [Google Scholar]
Vahidi, V.; Saberinia, E.; Morris, B.T. OFDM Performance Assessment for Traffic Surveillance in Drone Small Cells. IEEE Trans. Intell. Transp. Syst. 2018. [Google Scholar] [CrossRef]
Huang, H.; Savkin, A.V. Towards the Internet of Flying Robots: A Survey. Sensors 2018, 18, 4038. [Google Scholar] [CrossRef]
Dorling, K.; Heinrichs, J.; Messier, G.G.; Magierowski, S. Vehicle routing problems for drone delivery. IEEE Trans. Syst. Man Cybern. Syst. 2017, 47, 70–85. [Google Scholar] [CrossRef]
Hong, I.; Kuby, M.; Murray, A.T. A range-restricted recharging station coverage model for drone delivery service planning. Transp. Res. Part C Emerg. Technol. 2018, 90, 198–212. [Google Scholar] [CrossRef]
Kim, S.; Moon, I. Traveling Salesman Problem With a Drone Station. IEEE Trans. Syst. Man Cybern. Syst. 2019, 49, 42–52. [Google Scholar] [CrossRef]
Papachristos, C.; Alexis, K.; Carrillo, L.R.G.; Tzes, A. Distributed infrastructure inspection path planning for aerial robotics subject to time constraints. In Proceedings of the 2016 International Conference on Unmanned Aircraft Systems (ICUAS), Washington, DC, USA, 6–10 June 2016; pp. 406–412. [Google Scholar]
Phung, M.D.; Quach, C.H.; Dinh, T.H.; Ha, Q. Enhanced discrete particle swarm optimization path planning for UAV vision-based surface inspection. Autom. Constr. 2017, 81, 25–33. [Google Scholar] [CrossRef] [Green Version]
Zhou, Z.; Zhang, C.; Xu, C.; Xiong, F.; Zhang, Y.; Umer, T. Energy-Efficient Industrial Internet of UAVs for Power Line Inspection in Smart Grid. IEEE Trans. Ind. Inform. 2018, 14, 2705–2714. [Google Scholar] [CrossRef]
Saska, M.; Krátkỳ, V.; Spurnỳ, V.; Báča, T. Documentation of dark areas of large historical buildings by a formation of unmanned aerial vehicles using model predictive control. In Proceedings of the 2017 22nd IEEE International Conference on Emerging Technologies and Factory Automation (ETFA), Limassol, Cyprus, 12–15 September 2017; pp. 1–8. [Google Scholar]
Calì, M.; Ambu, R. Advanced 3D Photogrammetric Surface Reconstruction of Extensive Objects by UAV Camera Image Acquisition. Sensors 2018, 18, 2815. [Google Scholar] [CrossRef]
Kalantari, E.; Shakir, M.Z.; Yanikomeroglu, H.; Yongacoglu, A. Backhaul-aware robust 3D drone placement in 5G+ wireless networks. In Proceedings of the 2017 IEEE International Conference on Communications Workshops (ICC Workshops), Lumpur, Malaysia, 23–27 May 2017; pp. 109–114. [Google Scholar] [CrossRef]
Lagum, F.; Bor-Yaliniz, I.; Yanikomeroglu, H. Strategic Densification With UAV-BSs in Cellular Networks. IEEE Wirel. Commun. Lett. 2018, 7, 384–387. [Google Scholar] [CrossRef]
Yang, Z.; Pan, C.; Shikh-Bahaei, M.; Xu, W.; Chen, M.; Elkashlan, M.; Nallanathan, A. Joint Altitude, Beamwidth, Location, and Bandwidth Optimization for UAV-Enabled Communications. IEEE Commun. Lett. 2018, 22, 1716–1719. [Google Scholar] [CrossRef] [Green Version]
Huang, H.; Savkin, A.V. A Method for Optimized Deployment of Unmanned Aerial Vehicles for Maximum Coverage and Minimum Interference in Cellular Networks. IEEE Trans. Ind. Inform. 2018. [Google Scholar] [CrossRef]
Huang, H.; Savkin, A.V. An Algorithm of Efficient Proactive Placement of Autonomous Drones for Maximum Coverage in Cellular Networks. IEEE Wirel. Commun. Lett. 2018, 7, 994–997. [Google Scholar] [CrossRef]
Yang, P.; Cao, X.; Yin, C.; Xiao, Z.; Xi, X.; Wu, D. Proactive Drone-Cell Deployment: Overload Relief for a Cellular Network Under Flash Crowd Traffic. IEEE Trans. Intell. Transp. Syst. 2017, 18, 2877–2892. [Google Scholar] [CrossRef]
Savkin, A.V.; Huang, H. Deployment of Unmanned Aerial Vehicle Base Stations for Optimal Quality of Coverage. IEEE Wirel. Commun. Lett. 2019, 8, 321–324. [Google Scholar] [CrossRef]
Fotouhi, A.; Ding, M.; Hassan, M. Flying Drone Base Stations for Macro Hotspots. IEEE Access 2018, 6, 19530–19539. [Google Scholar] [CrossRef]
Uluturk, I.; Uysal, I.; Chen, K.C. Efficient 3D Placement of Access Points in an Aerial Wireless Network. In Proceedings of the 2019 16th IEEE Annual Consumer Communications & Networking Conference (CCNC), Las Vegas, NV, USA, 11–14 January 2019; pp. 1–7. [Google Scholar]
Savkin, A.V.; Huang, H. A Method for Optimized Deployment of a Network of Surveillance Aerial Drones. IEEE Syst. J. 2019. [Google Scholar] [CrossRef]
Yanmaz, E. Connectivity versus area coverage in unmanned aerial vehicle networks. In Proceedings of the International Conference on Communications (ICC), Ottawa, ON, Canada, 10–15 June 2012; pp. 719–723. [Google Scholar] [CrossRef]
Pugliese, L.D.P.; Guerriero, F.; Zorbas, D.; Razafindralambo, T. Modelling the mobile target covering problem using flying drones. Optim. Lett. 2016, 10, 1021–1052. [Google Scholar] [CrossRef]
Trotta, A.; Di Felice, M.; Montori, F.; Chowdhury, K.R.; Bononi, L. Joint Coverage, Connectivity, and Charging Strategies for Distributed UAV Networks. IEEE Trans. Robot. 2018, 34, 883–900. [Google Scholar] [CrossRef]
Caillouet, C.; Razafindralambo, T. Efficient deployment of connected unmanned aerial vehicles for optimal target coverage. In Proceedings of the Global Information Infrastructure and Networking Symposium (GIIS), Saint Pierre, Reunion Island, France, 25–27 October 2017; pp. 1–8. [Google Scholar]
Caillouet, C.; Giroire, F.; Razafindralambo, T. Optimization of mobile sensor coverage with UAVs. In Proceedings of the Conference on Computer Communications Workshops (INFOCOM WKSHPS), Honolulu, HI, USA, 15–19 April 2018; pp. 622–627. [Google Scholar]
Lyu, J.; Zeng, Y.; Zhang, R.; Lim, T.J. Placement Optimization of UAV-Mounted Mobile Base Stations. IEEE Commun. Lett. 2017, 21, 604–607. [Google Scholar] [CrossRef] [Green Version]
Savkin, A.V.; Huang, H. Proactive Deployment of Aerial Drones for Coverage over Very Uneven Terrains: A Version of the 3D Art Gallery Problem. Sensors 2019, 19, 1438. [Google Scholar] [CrossRef]
Khan, M.; Heurtefeux, K.; Mohamed, A.; Harras, K.A.; Hassan, M.M. Mobile target coverage and tracking on drone-be-gone UAV cyber-physical testbed. IEEE Syst. J. 2017, 99, 1–12. [Google Scholar] [CrossRef]
Zhao, H.; Wang, H.; Wu, W.; Wei, J. Deployment Algorithms for UAV Airborne Networks towards On-demand Coverage. IEEE J. Sel. Areas Commun. 2018, 36, 2015–2031. [Google Scholar] [CrossRef]
Ješke, P.; Klouček, Š.; Saska, M. Autonomous Compact Monitoring of Large Areas Using Micro Aerial Vehicles with Limited Sensory Information and Computational Resources. In Proceedings of the International Conference on Modelling and Simulation for Autonomous Systesm, Prague, Czech Republic, 17–19 October 2018; Springer: Berlin, Germany, 2018; pp. 158–171. [Google Scholar]
Huang, H.; Savkin, A.V. An Algorithm of Reactive Collision Free 3D Deployment of Networked Unmanned Aerial Vehicles for Surveillance and Monitoring. IEEE Trans. Ind. Inform. 2019. [Google Scholar] [CrossRef]
Kershner, R. The number of circles covering a set. Am. J. Math. 1939, 61, 665–671. [Google Scholar] [CrossRef]
Carothers, N.L. Real Analysis; Cambridge University Press: Cambridge, UK, 2000. [Google Scholar]
Boyd, S.; Vandenberghe, L. Convex Optimization; Cambridge University Press: Cambridge, UK, 2004. [Google Scholar]
Okabe, A.; Boots, B.; Sugihara, K.; Chiu, S.N. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams; John Wiley & Sons: Hoboken, NJ, USA, 2009; Volume 501. [Google Scholar]
Savkin, A.V.; Matveev, A.S.; Hoy, M.; Wang, C. Safe Robot Navigation among Moving and Steady Obstacles; Elsevier: Amsterdam, The Netherlands, 2015. [Google Scholar]
Hoy, M.; Matveev, A.S.; Savkin, A.V. Algorithms for collision-free navigation of mobile robots in complex cluttered environments: A survey. Robotica 2015, 33, 463–497. [Google Scholar] [CrossRef]
Wang, C.; Savkin, A.V.; Garratt, M. A strategy for safe 3D navigation of non-holonomic robots among moving obstacles. Robotica 2018, 36, 275–297. [Google Scholar] [CrossRef]

Figure 1. The visibility cone. Point

P_{2}

can be seen by the drone while point

P_{1}

cannot.

Figure 1. The visibility cone. Point

P_{2}

can be seen by the drone while point

P_{1}

cannot.

Figure 2. A triangulation

T (λ, x_{0}, y_{0})

consisting of equilateral triangles.

Figure 2. A triangulation

T (λ, x_{0}, y_{0})

consisting of equilateral triangles.

Figure 3. The centre of an equilateral triangle and the three congruent Voronoi cells, which are in different colors.

Figure 4. Constructing region

D_{γ}

from region

D

Figure 4. Constructing region

D_{γ}

from region

D

Figure 5. The ground region

D

Figure 5. The ground region

D

Figure 6. The number of drones N versus

z_{d}

Figure 6. The number of drones N versus

z_{d}

Figure 7. Deployment of 19 drones at 109 m by the proposed approach. The green dash circles are the coverage areas of drones.

Figure 8. The deployments by the algorithm of [19]. (a)

N = 19

and the drones are at the altitude 114 m. (b)

N = 20

and the drones are at the altitude 108 m.

Figure 8. The deployments by the algorithm of [19]. (a)

N = 19

and the drones are at the altitude 114 m. (b)

N = 20

and the drones are at the altitude 108 m.

Figure 9.

\frac{N (γ)}{γ^{2}}

versus

γ

Figure 9.

\frac{N (γ)}{γ^{2}}

versus

γ

© 2019 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Savkin, A.V.; Huang, H. Asymptotically Optimal Deployment of Drones for Surveillance and Monitoring. Sensors 2019, 19, 2068. https://doi.org/10.3390/s19092068

AMA Style

Savkin AV, Huang H. Asymptotically Optimal Deployment of Drones for Surveillance and Monitoring. Sensors. 2019; 19(9):2068. https://doi.org/10.3390/s19092068

Chicago/Turabian Style

Savkin, Andrey V., and Hailong Huang. 2019. "Asymptotically Optimal Deployment of Drones for Surveillance and Monitoring" Sensors 19, no. 9: 2068. https://doi.org/10.3390/s19092068

APA Style

Savkin, A. V., & Huang, H. (2019). Asymptotically Optimal Deployment of Drones for Surveillance and Monitoring. Sensors, 19(9), 2068. https://doi.org/10.3390/s19092068

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Asymptotically Optimal Deployment of Drones for Surveillance and Monitoring

Abstract

1. Introduction

2. Problem Statement

3. Deployment Algorithm

4. Simulation Results

5. Conclusions

Author Contributions

Funding

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI