A Solution to Cooperative Area Coverage Surveillance for a Swarm of MAVs

Abstract

Considering that coverage evaluation and control is one of the critical areas in surveillance, in this study we use deployment entropy to assess the coverage quality of a swarm of micro air vehicles (MAVs). Depending on the evaluation result of deployment entropy, we also develop a two-level redeployment algorithm to cope with the MAVs' redeployment problem for maximizing coverage. With the goal of distributing the MAVs evenly over the interested region, we divide the redeployment process into two levels: the global level and the local level. We propose a strategy of MAV redeployment for maximizing the deployment entropy at both levels. From numerical simulation, results show that by computing the value of deployment entropy, it is possible to evaluate the distribution of the MAVs' network in a wide area and the two-level algorithm can improve the sensing coverage of MAVs.

Keywords

MAVs Cooperative Surveillance Deployment Entropy Redeployment

1. Introduction

Unmanned aerial vehicles (UAVs) play a pivotal role in both military operations and civilian applications [1]. One of the most important applications is to implement space-based reconnaissance missions [2]. In this paper, we consider a swarm of Micro Aerial Vehicles (MAVs), such as ducted fan aerial vehicles with compact architecture and low cost, to cooperatively execute reconnaissance. The individual MAV may be less capable than a conventional large-scale UAV under development today, but through communications across the swarm of MAVs, the group exhibits behaviours and capabilities that can exceed those demonstrated by more conventional systems that would generally not employ communications between UAVs. Specifically, MAVs have better reconnaissance abilities and higher fault-tolerant abilities because they can cover the entire reconnaissance area effectively, even a large one. The spatial distribution of the MAVs determines the performance of the reconnaissance. The more dispersedly the MAVs are deployed, the more the surveillance area is accumulated and the more the operator knows about the interested area [3]. Related work to ours in the area of cooperative control can be found in [4 –6]. Cooperative surveillance problems in MAVs are divided into two types: one for the several specific targets within a limited detecting region and how to detect as many targets as possible at minimal cost; the other is for a large unknown surveillance area and how to allocate and control the swarm of MAVs to cover as large a surveillance area as possible at minimal cost. The latter problem is also known as the area coverage search problem. In this paper, we focus on the latter.

Considering a swarm of geographically distributed MAVs, we note that the coverage problem presented in this paper is intrinsically global in the sense that a lack of knowledge of any MAV's location may result in the problem being solved incorrectly. Therefore, we assume that each MAV knows its own coordinates as well. MAVs will be randomly deployed in an interested area. This will raise the issue of deployment asymmetry in some parts of the region where only a few MAVs are allocated, which may result in incomplete coverage of the MAV searching path. In other parts of the regions too many MAVs may be scattered, which may result in inefficient detection due to increased multi-MAV collisions and interference. Once a swarm of MAVs is deployed for, say, region surveillance, how can one be sure that the deployment provides the necessary coverage level? How to redeploy the MAVs further? We noticed that Chandler et al. [7] have presented three criteria to which the multi-UAVs assignment should conform: 1) no task should be assigned to more than one UAV, 2) no task should be assigned unless any prerequisite tasks are also assigned and 3) the estimated time at which a task is accomplished should not be before the estimated time of the immediately prerequisite task. In this perspective, one needs a measure that can represent the quality of the deployment and MAVs are required to relocate themselves to overcome such deployment shortcomings. Motivated by this observation, we need to analyse the deployment quality and research redeployment methods of multi-MAVs. Koenig [8] studied a simple means for coordinating teams of simple agents, while Butler [9] presented a distributed multi-robot covering algorithm. Matthew et al. [10] presented a statistical strategy for estimating the range performance required for tactical UAVs. The method begins with an arbitrary number of items of interesting targets randomly distributed over a given geographic area. The area is divided into several equal sized parts and each UAV surveys the target within their respective region. Then the problem of cooperative surveillance is abstracted to an optimization problem. Compared with relatively large UAVs, MAVs are usually deployed in a swarm manner, so the cooperative reconnaissance method of UAVs may not be fully applicable to MAVs when the number of the swarm of MAVs is significantly increased. Thus, we hope to learn from the multi-sensor's cooperative method, which is relatively mature. In these areas there are some research results, such as Ti et al. [11], who present deployment entropy to measure the coverage quality of wireless sensor networks quantitatively. Vieira et al. [12] used both sensor range and radio range to calculate the area of the Voronoi diagram in order to schedule the nodes. Shang et al. [13] proposed a non-overlapping density control to consider the trade-offs between sensing area overlap and sensing gaps. In their work they heavily relied on the sensing region as a criterion or an evaluation method for analysing the deployment quality of sensor nodes. In [14] and [15], authors proposed schemes about where to move the mobile sensors. In their schemes, the sensing field is partitioned into grids and sensors are moved from high-density grids to low-density ones to achieve more uniform coverage. However, this method also has some shortcomings. On the one hand, if the interested field is partitioned into many grids, it is very hard to redeploy the sensors in the grids evenly, so a large amount of movements of mobile nodes are needed. On the other hand, if it is divided into too few grids, inappropriate sensor deployment in sub-grids may still exist.

In contrast to the above work, we utilize deployment entropy to evaluate the coverage of MAVs, which only depends on the positions of the MAVs. Then, we introduce a two-level redeployment algorithm to achieve appropriate distribution of MAVs. MAVs' redeployment process is divided into two independent steps: first, the MAVs relocate themselves in the global target field, which is partitioned into few local regions, second, MAVs redeploy themselves in each local sub-region. Our aim is to move the MAVs from high-density regions to low-density regions, to make the multi-MAVs distributed as evenly as possible and to minimize the movement cost.

The paper is organized as follows. In Section 2 an algorithm based on entropy approach is applied to evaluate the distribution quality problem. Some examples using deployment entropy to evaluate the deployment of the multi-MAVs are also presented. In Section 3, we introduce a two-level redeployment algorithm. Simulations are presented in Section 4 and finally conclusions are given in Section 5.

2. Coverage Evaluations by Deployment Entropy

2.1 Deployment Entropy

In this paper, we focus on MAVs such as ducted fan aerial vehicles [16] for executing reconnaissance missions. This kind of MAV has a unique aerodynamic shape and excellent flight performance. Particularly, it can hang in the air, where the velocity can equal to zero. Therefore, a swarm of this kind of MAVs can be regarded as a static network and the surveillance coverage evaluation of MAVs could be considered as a static two-dimensional coverage evaluation problem. We assume that each MAV knows its own coordinates.

Figure 1 shows a typical scenario of interested region surveillance by a swarm of MAVs. The image sensors are mounted at the bottom of the MAVs. The dark circles show the sensing regions of the MAVs. The red points show the positions of the MAVs on the ground. The objective of surveillance coverage is to make MAVs sense every point in the interested region. In other words, every part of the interested region should be covered by the sensing regions of MAVs. As discussed before, due to the assumption that the coverage of MAVs could be considered as region coverage by a static network, the achievable sensing coverage strongly depends on the way that the MAVs are deployed. We can utilize deployment entropy [11] in a wireless sensor network to measure the quality of the coverage of MAVs.

Figure 1.

The interested region is under surveillance by a swarm of MAVs

Deployment entropy expresses the uniformity of the deployment of sensors or MAVs between sub-regions. Any effort toward equalization of deployment between sub-regions will increase the value of deployment entropy. In the deployment entropy evaluation method, the interested region is divided into M sub-regions. Based on the partition, the number of MAVs distributed in each sub-region can be collected. Then the whole deployment of MAVs in the interested area could be expressed by the deployment entropy, which is described as follows:

H = - \sum_{i = 1}^{n} p_{i} \ln p_{i}

(1)

where,

\begin{array}{l} p_{i} = \frac{r a t i o_{i}}{\sum_{k = 1}^{n} r a t i o_{k}}, r a t i o_{i} = \frac{N_{i}}{S_{i}}, \\ N_{t o t a l} = \sum_{i = 1}^{n} N_{i}, S_{t o t a l} = \sum_{i = 1}^{n} S_{i} \end{array}

N_i is the amount of MAVs in the i^th sub-region, S_i is the area of the i_th sub-region, ratio is the ratio of MAVs amount over the i^th sub-region area, pi is the unitary proportion of the i^th ratio in the sum of all ratios, N_total is the total number of all the MAVs, S_total is the total area of the interested region and. n is the number of sub-regions that the interested region is composed of. The quantity H has some interesting properties, which further substantiate it as a reasonable measure of the deployment of MAVs or other agents.

Maximality property: If and only if the value of each ratio equals to N_total/S_total, H will achieve the maximum value.

Monotonicity property: H is a strictly convex function

As a result, by utilizing the value of H, we can evaluate the distribution of MAVs in the interested region. Furthermore, based on H, we can assess the performance of sensors' surveillance coverage. Note that the computation of the overlapped sensing region by multiple MAVs is avoided; therefore, the calculating burden of the deployment entropy evaluation method is little compared with other coverage evaluation methods.

2.2 Example of Coverage Evaluation by Deployment Entropy

In order to examine the effectiveness of deployment entropy in evaluating the coverage quality of MAVs, we provide some numerical results produced in MATLAB. We select a two-dimensional indoor area as the interested region. Firstly, we calculate the deployment entropy under different MAV deployment in the same partitions of the interested region. We use a Voronoi diagram to decompose the region into ten sub-regions, shown as in Figure 2, because it can generate random partitions. We use three different deployments of 50 MAVs to take comparisons: (1) MAVs are artificially deployed in a relatively small region, which is shown in Fig. 2(a), (2) and (3) are the two different random distributions of MAVs over the whole region, which are shown in Fig. 2(b) and Fig. 2(c) respectively.

Figure 2.

(a) MAVs scatter in a relative small region; (b) and (c): MAVs are randomly distributed over the whole region; (d) the result of deployment entropy and coverage percentage.

Figure 2(d) illustrates the results of deployment entropy and the coverage percentage, which is the ratio of the area covered by MAVs to the region area. It is evident that when the MAVs tightly gather in a small region, the value of deployment entropy is correspondingly little. This is in accordance with our common sense: this deployment of MAVs is not good enough, which may result in an inefficient network of MAVs. When the 50 MAVs are randomly distributed over the whole region, it is not easily to differentiate which deployment is better. The deployment entropy in Scenario (3) is about 2.27 and covers about 80% of the region. The H in (2) is about 2.17 and the covered area is about 70%. Therefore, it could be verified that the more dispersed MAVs are, the greater the value of H.

Secondly, we present a simulation scenario that calculates the value of H for the same deployments of MAVs in the different partitions of the region. We divide the interested region into ten regular quadrangles, shown as in Figure 3. The three deployments of MAVs are the same as those in above simulation. The values of deployment entropy are shown in Table 1. We can also obtain the results that Scenario (3) has the maximum H and Scenario (1) has the minimum one. However, the values of deployment entropy in the first simulation do not equal those in the second simulation. This difference shows that although the distributions of MAVs are the same, distinct partition strategies could influence the value of H. As a result, the same partition should be adopted to evaluate the coverage quality of MAVs by deployment entropy.

Table 1.

Deployment entropy in different scenarios

	Scenario 1	Scenario 2	Scenario 3
H	0.95	2.20	2.27

Figure 3.

The distributions of MAVs are same as that in Fig.2, but the region partitions are different from that in Fig.2.

To sum up, when we use MAVs to execute a surveillance coverage mission, it is reasonable to use deployment entropy to measure the distribution of MAVs. Meanwhile, deployment entropy can be taken as a reference for adjusting the reconnaissance positions of MAVs in real time, that is to say, choosing the strategy with a greater value of H.

3. Two-level redeployment scheme

In the real applications, the swarm of MAVs usually comes from the same external point and they spread themselves over the interested region. If they spread randomly, it is possible that some sub-regions may be insufficiently covered by MAVs and some sub-regions may even have no MAVs. To improve coverage, redeployment of MAVs is needed. Besides, in some cases, a strategy of controlling the MAVs' distribution from the start point to the overall region is also needed. In this paper, we present a two-level redeployment to maximize the coverage of MAVs.

The two-level redeployment of an MAV network is divided herein into two separate steps. On the global level, the interested field is partitioned into several relatively large grids. As discussed above, the deployment entropy is used to measure how well a region is covered by MAVs. Therefore, deployment entropy can be regarded as a basis for redeploying the MAVs to maximise the coverage. In order to estimate the quality of the MAVs' distribution, we want to set a threshold of H. If the current deployment of MAVs on the global level has an H over the threshold, it can be regarded as a satisfied deployment. If the current H of the MAVs' distribution is less than the threshold, the MAVs have to relocate themselves with the goal of achieving the requirements of deployment entropy. At the local level, each grid is also partitioned into several small sub-grids. We also use deployment entropy to decide whether to redeploy the MAVs in each grid. If the deployment entropy in the grid is less than the threshold of H, the MAVs in the gird make further movements to distribute themselves as evenly as possible among the small sub-grids, with the goal of maximizing deployment entropy.

In order to achieve such goal, some rules for MAVs' movements are required:

We use a grid-based partition method that has the advantage of simplicity and clarity, especially in area computation of sub-grids. At the global level, the interested region is partitioned into several relatively large grids evenly. At the local level, each grid is further divided into several smaller sub-grids.

Every grid or every sub-grid can only interact with its neighbours, which means MAVs in a grid or sub-grid can only go to or come from their neighbour grid or sub-grids.

MAVs can only relocate themselves from one grid or sub-grid with a high ratio to others with a low ratio. This is the same as the conventional density control redeployment method.

It is possible that one MAV may move between two neighbouring grids or sub-grids endlessly when the MAV amount difference between them is only one. In order to avoid plunging into this endless move, we set a minimum ratio difference threshold. If the ratio difference between neighbour grids or sub-grids is lower than that threshold, the MAV's movement should be interrupted.

Only one MAV can be selected to move for each grid in each computing cycle. When more than one MAV needs to move, we have to find the MAV with the shortest distance between its position and the target grid centre.

D_{i j} = \sqrt{{(x_{i} - X_{j})}^{2} + {(y_{i} - Y_{j})}^{2}}

(2)

xi and yi represent the coordinates of i^th MAV, X_j and Y_j are the geometrical centre of j^th grid and D_ij is the distance between the i^th MAV to the j^th grid centre.

Based on the definition of deployment entropy and the above rules, the algorithm of our two-level redeployment can be established. We adopt a pseudo code form to describe our two-level redeployment scheme, shown in Figure 4.

Figure 4.

Pseudo code of two-level redeployment

4. Simulations

In this section, we have performed some simulations to evaluate the effectiveness of our proposed two-level redeployment scheme. First, we initially deploy 50 MAVs over a 300×300 field, as shown in Figure 5(a). On the global level, the field is partitioned into nine square-shape grids. Each grid is further divided into four smaller square-shape sub-grids in the local level. We utilize the two-level redeployment scheme to adjust the positions of MAVs. Figure 5(b) shows the redeployment result in global level. Every grid contains five or six MAVs after global redeployment. Figure 5(c) shows the results after two-level redeployment. There are one or two MAVs in each sub-grid. Figure 5(d) plots the coverage percentage at the different stages. In the initial stage, the coverage percentage is about 76.9%. After the global redeployment, the coverage percentage is improved to 78.2%. When the MAVs are further redeployed by the local level redeployment scheme, the coverage percentage is increased to 88.2%. Therefore, the proposed redeployment is effective to improve the coverage performance of MAVs in the tasks of region surveillance.

Figure 5.

Performance of the proposed scheme when the MAVs are randomly deployed in the region

We also consider a scenario where MAVs come from a certain external point. We assume that 50 MAVs enter the region from the original point (0, 0). When all the MAVs enter, they are located in a very small 50×50 area, shown in Figure 6(a). We utilized the proposed redeployment scheme to control the MAVs to spread over the region. After the global redeployment, the results of MAVs positions are as shown in Figure 6(b). Figure 6(c) shows the results of MAVs positions after two-level redeployment. Figure 6(d) shows the coverage percentage.

Figure 6.

Performance of the proposed scheme when the MAVs come from the same point

From Figure 6(d), we can see that at the beginning the coverage percentage is only about 6.4%. After the global level deployment, the coverage percentage becomes 47.6%. When the two-level redeployment is complete, the coverage percentage increases to 89.4%. Therefore, this simulation shows that the proposed redeployment scheme is also effective when the MAVs come from the same point.

In order to the show the efficiency of the proposed two-level redeployment scheme, we take a one-level redeployment scheme [17] as a reference. In the one-level deployment scheme, the 300×300 field is divided into 36 grids. In our two-level redeployment scheme, the field is partition into nine grids at the global level and then each grid is divided into four sub-grids at the local level. The MAVs randomly deployed in the field changes from 40 to 100. The results of the coverage percentage are shown in Figure 7. We use the number of hops of all sensor nodes as the movement cost in this paper, which is shown in Figure 8.

Figure 7.

The coverage percentage after redeployments.

Figure 8.

Movements costs of two redeployment method.

As shown in Fig.7, both the one-level and the two-level redeployment schemes have almost the same coverage percentages after the MAVs' re-distribution. However, the hops of MAV movements are very different, as shown in Figure 8. The movement cost in our proposed method is far less than that of the one-level redeployment methods. For instance, the two-level scheme needs 22 hops to achieve an even distribution when 50 MAVs are deployed, in contrast with 56 hops in the one-level scheme. Figure 8 also shows that the more sensors that are deployed in the interested field, the greater the movement cost of the one-level method is than the proposed two-level redeployment method. For example, when 100 MAVs are deployed in the interested field, the one-level redeployment needs 384 hops to achieve an even distribution, whereas, our two-level redeployment method needs only 62 hops.

5. Conclusions

In this paper, we considered the problem of surveillance coverage evaluation undertaken by measuring the dispersion of an MAV network and that of a redeployment method for maximizing coverage. In the former perspective, this paper describes deployment entropy as a novel quantitative measurement of distribution of MAVs when they execute surveillance coverage mission. The properties of deployment entropy make it a reasonable method to measure the distribution. In the later perspective, the two-level redeployment method is developed to relocate the MAVs to achieve an even distribution. Some simulation results reveal that the proposed algorithm can improve the coverage percentage of the MAVs network no matter when the MAVs are randomly deployed in the interested region or the MAVs enters the region from the same point. The simulation also shows that our proposed two-level redeployment scheme has a lower movement cost when achieving the same coverage percentage as the one-level scheme.

Footnotes

6. Acknowledgement

This study was supported by the National Natural Science Foundation of China (Grant No: 11102019).

References

Shaferman

Shima

, Unmanned aerial vehicles cooperative tracking of moving ground target in urban environments, Journal of guidance, control, and dynamics, vol.31, no.5, pp. 1360–1371, 2008.

Tian

Shen

Research on Multi-base Multi-UAV Cooperative Reconnaissance Problem, ACTA AERONAU TICA ET ASTRONAU TICA SINICA, vol.28, no.4, pp. 913–920, 2007.

Moore

B. J.

Passino

K. M.

, Distributed Balancing of AAVs for Uniform Surveillance Coverage, Proceedings of the 44th IEEE Conference on Decision and Control, and The European Control Conference 2005, Seville, Spain, pp. 7060–7065, 2005.

Baum

M. T.

Passino

K. M.

, A Search-theoretic Approach to Cooperative Control for Uninhabited Air Vehicles, AIAA Guidance, Navigation, and Control Conference and Exhibit, Monterey, California, 2002.

Jacques

Leblanc

Effectiveness Analysis for Wide area Search Munitions, Proceedings of the AIAA Missile Sciences Conference, Monterey, CA, 1998.

Polycarpou

Yang

Passino

, Cooperative Control of Distributed Multi-agent Systems, IEEE Control Systems Magazine, 2002.

Chandler

P. R.

Complexity in UAV cooperative control, Proceedings of the American Control Conference, (Anchorage, Alaska), 2002.

Koenig

Tiu

Terrain Coverage with Ant Robots: A Simulation Study, Proceedings of the Fifth International Conference on Autonomous Agents, Montreal, Canada: ACM Press, pp. 600–607, 2001.

Butler

Z. J.

Rizzi

Cooperative Coverage of Rectilinear Environments, Proceedings of IEEE International Conference on Robotics and Automation, San Francisco: IEEE, pp. 2722–2727, 2000.

10.

Hutchison

M. G.

A Method for Estimating Range Requirements of Tactical Reconnaissance UAVs, AIAA's 1st Technical Conference and Workshop on Unmanned Aerospace Vehicles, Portsmouth, Virginia: AIAA, 2002.

11.

Zhang

, Coverage analysis and active scheme of wireless sensor networks, IET wireless sensor systems, vol.2, no.2, pp. 86–91, 2012.

12.

Vieira

M. A. M.

Vieira

L. F. M.

Scheduling Nodes in Wireless Sensor Networks: A Voronoi Approach, 28th Annual IEEE International conference on local computer networks, Germany, pp. 423–429, 2003.

13.

Shang

Shen

Shi

A new Density Control Algorithm of WSNs, 29th Annual IEEE international conference on local computer networks, Florida, pp. 577–578, 2004.

14.

Lin

Improving Sensor Network Performance by Deploying Mobile Sensors, Proc. 24th IEEE Int'l Performance, Computing, and Comm. Conf. pp. 67–71, 2005.

15.

Shen

Chang

Jiang

Wang

Yan

A Generic Framework for optimal Mobile Sensor Redeployment, IEEE Transactions on Vehicular Technology, vol.59, no.8, pp. 4043–4057, 2000.

16.

Wang

Guo

Ch.

Numerical analysis of aerodynamic characteristics for the design of a small ducted fan aircraft. Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering. doi:10.1177/0954410012458619(Online).

17.

Shen

Chang

Jiang

Wang

Yan

, A Generic Framework for Optimal Mobile Sensor Redeployment, IEEE Transactions on Vehicular Technology, vol.59, no. 8, pp. 4043–4057, 2010.