Nothing Special   »   [go: up one dir, main page]
Next Article in Journal
An Iterated Hybrid Local Search Algorithm for Pick-and-Place Sequence Optimization
Previous Article in Journal
Time-Varying Ultra-Wideband Channel Modeling and Prediction
You seem to have javascript disabled. Please note that many of the page functionalities won't work as expected without javascript enabled.
 
 
Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
Journals
Symmetry
Volume 10
Issue 11
10.3390/sym10110632
symmetry-logo
Submit to this Journal Review for this Journal Propose a Special Issue
► Article Menu

Article Menu

share Share announcement Help format_quote Cite question_answer Discuss in SciProfiles thumb_up
...
Endorse textsms
...
Comment
first_page
settings
Order Article Reprints
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Energy-Efficient Swarm Behavior for Indoor UAV Ad-Hoc Network Deployment

by
Fidel Aznar
1,
Mar Pujol
1,
Ramon Rizo
1,
Francisco A. Pujol
2,* and
Carlos Rizo
3
1
Department of Computer Science and Artificial Intelligence, University of Alicante, 03690 San Vicente del Raspeig-Alicante, Spain
2
Department of Computer Technology, University of Alicante, 03690 San Vicente del Raspeig-Alicante, Spain
3
Department of Architectural Constructions, University of Alicante, 03690 San Vicente del Raspeig-Alicante, Spain
*
Author to whom correspondence should be addressed.
Symmetry 2018, 10(11), 632; https://doi.org/10.3390/sym10110632
Submission received: 24 July 2018 / Revised: 23 October 2018 / Accepted: 8 November 2018 / Published: 13 November 2018
Browse Figures
Figure 1
<p>Summary scheme of the main subjects involved in this work.</p> "> Figure 2
<p>(<b>a</b>) Maps used in the experimentation. The starting points of the deployment process in these maps are the following ones (top to bottom): (i) <math display="inline"><semantics> <mrow> <mo>(</mo> <mi>x</mi> <mo>,</mo> <mi>y</mi> <mo>)</mo> <mo>=</mo> <mo>(</mo> <mn>35</mn> <mo>,</mo> <mn>55</mn> <mo>)</mo> </mrow> </semantics></math>, (ii) <math display="inline"><semantics> <mrow> <mo>(</mo> <mi>x</mi> <mo>,</mo> <mi>y</mi> <mo>)</mo> <mo>=</mo> <mo>(</mo> <mn>45</mn> <mo>,</mo> <mn>50</mn> <mo>)</mo> </mrow> </semantics></math>, (iii) <math display="inline"><semantics> <mrow> <mo>(</mo> <mi>x</mi> <mo>,</mo> <mi>y</mi> <mo>)</mo> </mrow> </semantics></math> = <math display="inline"><semantics> <mrow> <mo>(</mo> <mn>35</mn> <mo>,</mo> <mn>50</mn> <mo>)</mo> </mrow> </semantics></math> and (iv) <math display="inline"><semantics> <mrow> <mo>(</mo> <mi>x</mi> <mo>,</mo> <mi>y</mi> <mo>)</mo> <mo>=</mo> <mo>(</mo> <mn>15</mn> <mo>,</mo> <mn>50</mn> <mo>)</mo> </mrow> </semantics></math>. (<b>b</b>,<b>c</b>) Evolution of a selected execution for two sample maps, where white areas are free zones and black areas represent obstacles. Steps 0, 500, 1500, 2000 are shown. In addition, the obstacle detection area of the robots (circle) areas with pheromones (blue) and the coverage range for each agent (red) is presented.</p> "> Figure 3
<p>Number of individuals in each state and percentage of area covered by an individual given a simulation step, where each step is equal to 0.5 s. The mean and standard deviation for 30 different runs are shown until the swarm has covered 85% of the environment.</p> "> Figure 4
<p>In this picture, both the mathematical models and the results of the simulation are shown. We have provided the number of agents in the <span class="html-italic">wander</span> and <span class="html-italic">beacon</span> states, the instant energy consumed by the swarm, the amount of environment covered and the average energy consumed. For these simulations, the average and standard deviation of 50 different executions of our behavior are shown. As can be seen, the models presented and the simulations coincide substantially.</p> "> Figure 5
<p>In this picture, both the mathematical models and the results of the simulation are shown for four different maps. The energy consumption of the swarm vs. the predicted energy consumption for four maps (<b>a</b>–<b>d</b>) is shown. Each map is shown on the right side of its corresponding figure. For each of them, we have provided the number of agents in the <span class="html-italic">wander</span> and <span class="html-italic">beacon</span> states, the instant energy consumed by the swarm, the amount of environment covered and the average of energy consumed. For these simulations, the average and standard deviation of 50 different executions of our behavior are shown. As can be seen, the models presented and the simulations achieve very similar results.</p> ">
Versions Notes

Abstract

:
Building an ad-hoc network in emergency situations can be crucial as a primary tool or even when used prior to subsequent operations. The use of mini and micro Unmanned Aerial Vehicles (UAVs) is increasing because of the wide range of possibilities they offer. Moreover, they have been proven to bring sustainability to many applications, such as agriculture, deforestation and wildlife conservation, among others. Therefore, creating a UAV network for an unknown environment is an important task and an active research field. In this article, a mobility model for the creation of ad-hoc networks using UAVs will be presented. This model will be based on pheromones for robust navigation. We will focus mainly on developing energy-efficient behavior, which is essential for this type of vehicle. Although there are in the literature several models of mobility for ad-hoc network creation, we find that either they are not adapted to the specific energy requirements of UAVs or the proposed motion models are unrealistic or not sufficiently robust for final implantation. We will present and analyze the operation of a distributed swarm behavior able to create an ad-hoc network. Then, an analytical model of the swarm energy consumption will be proposed. This model will provide a mechanism to effectively predict the energy consumption needed for the deployment of the network prior to its implementation. Determining the use of the mobility behavior is a requirement to establish and maintain a communication channel for the required time. Finally, this analytical model will be experimentally validated and compared to the Random Waypoint (RWP) mobility strategy.

1. Introduction

Swarm robotics is an approach to collective robotics that takes inspiration from the self-organized behaviors of social animals. Through simple rules and local interactions, swarm robotics aims at designing robust, scalable and flexible collective behaviors for the coordination of large numbers of robots [1].
This type of robotics is usually implemented using a great number of robots. These robots are autonomous, have local sensory capabilities, do not have access to control tasks and must cooperate to develop a task. In order to define swarming behaviors, the most common method requires developing the rules of individual robots in an iterative way so that the desired global behavior will emerge from the whole set of robots. To do this, the most common design method for the development of behaviors is the use of probabilistic models [1].
One of the most effective ways of communication used in nature is the communication by means of pheromones. Due to its effectiveness, artificial pheromones have been adopted in multi-robot and swarm robotic systems for more than a decade [2,3].
Among the multiple applications of collective robotics systems, one can find the deployment of a communications network for the swarm itself, which becomes especially important when dealing with Unmanned Aerial Vehicles (UAV) [4,5].
A MANET (Mobile Ad-hoc Network) is a wireless network composed of a set of self-organized portable nodes. UAVs have the potential of being capable to create an ad-hoc network in the air, i.e., ad-hoc networks of UAVs. Most UAVs used in communication networks are equipped with wireless transceivers using omnidirectional antennas. As UAVs may move very fast, in UAV ad-hoc network communication scenarios, the network topology can change quickly with low energy cost. Such position changes require the entire set of vehicles to be moved coherently in order to maintain the network connections required for data transmission [4].
There are many scenarios where it is extremely useful to create such networks using UAVs [5]. In particular, UAVs are highly and successfully used to support environmental sustainability [6]; for example, in order to search for resources in an unknown environment, for pollution monitoring, in precision agriculture and when building communication systems, among others. In this article, we will focus on the last application: a behavior able to create a communication link between a building and its outdoors will be provided, assuming that there is only one access point to the building. When working in indoor environments, there could be situations (such as radio jamming, lack of energy or emergencies) where no internal or external signal for communication or localization—GPRS, WIFI, GPS, etc.—can be accessed. In this case, it is essential to create an ad-hoc communication network [7].
In this article, a swarming behavior aimed at creating ad-hoc networks for UAV vehicles will be initially presented. This behavior will be based on pheromone communication for robust navigation. The behavior will be designed to be executed on an aerial platform, and more precisely on a system of quadcopter-type aerial vehicles. Due to the special particularities of this type of vehicle, our work will focus specifically on analyzing the swarm behavior at an energy efficiency level, which is essential for this type of UAV. Although there are in the literature several models of mobile ad-hoc network creation, it has been found that either they are not adapted to the specific energy requirements of quadcopter UAVs or the proposed motion models are unrealistic or not sufficiently robust for their final implementation. Figure 1 shows a summary scheme of our work.
The rest of this article is organized as follows. Firstly, we will present and analyze the operation of a distributed swarm behavior able to create an ad-hoc network. Then, an analytical model of the swarm energy consumption will be proposed. This model will provide a mechanism to predict the energy consumption needed effectively for the deployment of the network prior to its implementation. Determining the consumption of the mobility behavior is an essential condition to establish and maintain a communication channel for the required time. Finally, this analytical model will be experimentally validated and compared to the Random Waypoint (RWP) mobility strategy.

2. State of the Art

Multi-robot deployment has become a topic of basic research in the field of multi-robot systems. In this section, we will provide a brief review of the existing types of swarm deployment and coverage of terrestrial robots. Then, we will review some applications designed to be executed using aerial vehicles and comment on some examples of stigmergy communication in swarm systems.
Although there is a great amount of applications related to multi-robot deployment [8,9,10], many of them rely on a pre-established communication network or external localization service. This would limit the application of these systems to tasks where the existence of communication networks or GPS cannot be assumed. Therefore, there are several studies where the external communication network is substituted by the deployment of a new network of sensor nodes or radio beacons. For example, [11] used a distributed algorithm to guide a group of robots through a network of sensors. However, this and other similar strategies require the prior deployment of the sensor network, which may be difficult or not practical in emergency situations.
Another alternative is to include the deployment process in the behavior. In this case, the behavior consists of two phases: beacon deployment and robot deployment. In [12], a network of static radio beacons was deployed to form a long-range communication network to assist in robot exploration. However, such strategies cannot be used with micro or small-sized UAVs (the most commonly-used type of UAVs in indoor environments) because of their low load capacity and limited autonomy.
In [13,14], a different strategy was presented, where each individual integrates a beacon, creating its own communication network. However, the design of this behavior is intended for the physical characteristics of the terrestrial robots presented in this paper, called s-bots. This makes it very difficult to generalize to other types of vehicles due to their different types of sensors and actuators.
In our case, we are interested in developing a swarm behavior that uses the advantages of indoor flying vehicles, rather than terrestrial ones, in emergency situations. For example, these vehicles can avoid many obstacles that limit ground vehicles and enable sensor data to be obtained from a vantage point [15,16,17,18,19].
An aerial vehicle requires specific considerations and algorithms to ensure navigability [20,21]. On the one hand, global localization techniques, which are common in outdoor UAVs, cannot be used [22,23]. Thus, in outdoor UAVs, GPS is the most common localization system since it can be adjusted by using on-board inertial sensors. Such systems cannot be used indoors (signal reception occlusion) or in all outdoor locations and situations, so another approximation, such as local localization, must be considered.
Robot local localization commonly requires environment maps and odometry sensors [24]. Environmental mapping may be previously undiscovered, and online map creation requires powerful computing that may not be possible with small flying robots [25]. In addition, these approaches are not successfully scaled up with large swarms [22]. Moreover, there are simple relative localization applications that are suitable for small UAVs; for example, [26] presented the relative positioning of sensors in reference to nearby static robots with a decentralized approach.
One of the first applications related to the UAV deployment task using a robotic swarm can be found in [27]. This application uses a predetermined communication network as the basis for guiding UAVs. Although this behavior does not require an external communication network, it does need a pre-deployment phase, as in the terrestrial application in [28], which is not applicable in real emergency situations that are not predictable in advance. In a later work, [29] reconfigured the network of sensors to maximize the system performance, but the method requires a group of terrestrial robots to transport the sensor network, which is not feasible in our case, since the ground may be impracticable.
More recently, [26,30] presented a behavior where a fully-distributed deployment is achieved while creating a communication network. This system does not require existing communication networks or a global localization system. In addition, it is an effective strategy that is designed to save energy when using UAVs, which is very important for increasing swarm autonomy. The work in [26,30] assumed that a robot can temporarily be attached to the ceiling or floor for surveillance over extended periods of time. However, as the authors discussed, this behavior requires special environment features (straight walls, 90 degree angles, etc.) to be executed (it is not applicable for unstructured environments) and does not take into account uncertainty (for example, the errors in sensor readings and robot actuators), which is very important in UAV systems.

Mobility Strategies

The innovation of ad-hoc unmanned aerial vehicles network systems is that the motion of unmanned aerial vehicles is controlled by fully-independent algorithms with two purposes: first, to maintain network connectivity to enable real-time communication between unmanned aerial vehicles and ground equipment; second, to increase detection coverage to identify targets quickly. The main limitations for the use of unmanned aerial vehicles are battery energy, communications bandwidth and processing capabilities. The useful life of drones and the radio transmission range on board are limited. Therefore, the behavior of unmanned aerial vehicles swarms in terms of flight paths and connections must be efficient.
Thus, we find two conflicting objectives: to preserve the connectivity of the individuals at all costs, by using measures such as the SNR (Signal-to-Noise Ratio) or RSSI (Receive Signal Strength Indicator), but to separate them as much as possible to have the majority of the environment covered [31].
Although we have found in the literature several models of mobility for the creation of ad-hoc networks [4,5,7], they are not adapted to the energy needs of UAVs or their motion models are unrealistic. In addition, they do not consider the difference between connectivity and covering, being not robust enough for real implantation. In this paper, a swarm behavior for the energy-efficient creation of ad-hoc networks is presented. This behavior has been designed keeping in mind the requirements of the MANET network construction, its robustness, as well as the energy used to carry out the deployment.

3. Swarm Mobility Behavior

In this paper, a swarm modeling design will be used. Swarm intelligence systems are decentralized, self-organized algorithms used to resolve complex problems with dynamic properties, incomplete information and limited computation capabilities. These systems are related to IoT-based systems [32,33,34,35], which are complex and dynamic aggregations of entities (smart objects), which usually lack decentralized control.
Swarm robotics is an approach to collective robotics that takes inspiration from the self-organized behaviors of social animals. Through simple rules and local interactions, swarm robotics aims at designing robust, scalable and flexible collective behaviors for the coordination of large numbers of robots. This type of robotics is based in swarm intelligence, which describes how complex social behaviors can come from simple non-coordinated individual actions. The control architectures relevant to swarms are scalable, from a few units to thousands or million of units, since they base their coordination on local interactions and self-organization.
Using the ideas presented in [13,14,26,30], a UAV swarm can establish its own communications network. This network can be used for communicating swarm tasks or even to help other robots or a human team with subsequent work [36,37].
A behavior for creating MANET networks must take into account several aspects to balance the goals of covering and connectivity. More specifically, a MANET network must have the following geometric characteristics [5]. It should minimize the uncovered areas of the environment to meet the target covering goal. It should ideally generate the minimum required number of vehicle movements (reducing interference due to displacement). It should be allowed to adjust, directly or indirectly, the number of neighbors of a network node. This number must be balanced, since a high amount of neighbors may cause interferences, but a reduced amount cannot allow multihop networks. Finally, it must maintain the clustering rate of all network nodes uniformly.
From an energetic point of view, we must take into account the difference between the consumption of a UAV in flight or in the standby state. In order to measure individual swarm energy consumption, an energy model, suitable for flying robots is used from [38]. In this model, the energy consumption was split into two parts: the electrical power e f required for flight and the electrical power required to be stationary (landed) e s . For our system, we assume that e f = 120 W and e s = 0.5 W. As will be seen below, our model will take into account the consumption of vehicles implicitly, depending on their state.

3.1. Platform

Indoor flights usually require smaller drones than outdoor ones, mostly because indoor spaces often limit the size of aircraft for safety and maneuverability. However, it should be considered that the size of these devices is directly related to their load capacity. Drones that can fly in urban indoor environments will be used, based on the size required to move a person. To fly with security, UAVs with a maximum radius of half a meter are available. This ensures a secure indoor movement at a speed of no more than 1 m/s. From our point of view, this provides sufficient safety margins for indoor environments. These UAVs must have a mechanism that allows them to detect obstacles in the flying plane.
UAV launching will occur progressively over time from the same launching point. This will simplify the arrangements before take off and will facilitate its application in emergency tasks, where a specific launching point could be a requirement.
A swarm simulator based on the library in [39] has been developed in order to illustrate the experimental section of this paper. A specific physics engine layer for UAV vehicle simulation has also been added using the Chipmunk Physics library [40]. A realistic approach to UAV dynamics has been considered taking also into account the errors of the actuators, sensors and the inherent uncertainty of such systems. In addition, another two items have been developed: on the one hand, a virtual sensor of the quantitative sematectonic pheromones; on the other hand, a network of ultrasonic sensors used for detecting other drones or walls. The implementation has been designed to be as realistic as possible with regard to the final physical implementation.

3.2. Proposed Behavior

Given the difference between the energy consumption of a UAV in flight or landed, it seems coherent to consider two different energy states in our model: in flight (wander) or with the engines stopped (beacon).
Initially, our behavior will start with an agent in the beacon state, which will mark the access point of the environment to be explored. Then, in regular time intervals, wander agents will be added. These agents have a unique numerical identifier, which is incremented for each new added agent. Its primary mission is to explore the surroundings. Thus, these agents will be in flight, traveling through the environment using their collision sensors and moving probabilistically until the signal strength (using for example the RSSI of the transceiver device) is at a certain threshold li ∈ R where it will be necessary to stop the vehicle to avoid breaking the communication channel. In this case, we will proceed to land the UAV and change its state to beacon.
In the beacon state, a vehicle obtains a substantial battery savings. Its mission is to relay any signal from any members of the swarm, establishing a communications network where each node can be an information router. This behavior is required to send information from the control point to the swarm or when requiring information about the environment or the state of the covering process. Moreover, beacon vehicles play a key role in developing the stigmergy strategy. We propose the use of quantitative sematectonic stigmergy, that is the deposit of the same individuals in the environment as a mechanism for communicating quantitative information.
In this way, beacon vehicles are key players in the process. Their task is to receive the virtual pheromones broadcast within their range of communication and to store them. In addition, to emulate the operation of natural pheromones, they also remove the intensity of stored pheromones as time goes by. This provides a good mechanism of forgetting, which is very useful in dynamic environments.
The use of pheromones in our behavior is essential and facilitates its development in complex environments in a robust way. Wander agents emit pheromones when moving around with a certain radius Ψ r w ∈ R and intensity Ψ δ w ∈ R. Similarly, when an agent makes a transition from the wander to the beacon state, the vehicles emit a pheromone footprint with a larger radius Ψ r b ∈ R and intensity Ψ δ b ∈ R than the previous one. This footprint is emitted only once, fading in time, where the linear rate of decrease per second is indicated by Ψ ∈ ∈ R.
Wander agents’ navigation is determined by a potential field function f, made of three functions (f 1 , f 2 , f 3 ). The movement to be developed by the robot is the sum of all three components with an adjustment term for each of them. To execute the movement of an agent, only the unit vector of f ^ = f | f | is calculated, because we need to know which direction to take. Terms α i allow graduating the intensity of each component.
The first component f 1 is obtained as a vector pointing to the lowest intensity zone of pheromones within the vehicle perception radius, so that this intensity decreases with the square of the distance. Assuming that the vehicle position is the center of the coordinates, this component can be specified so that:
C = ( x , y ) | x 2 + y 2 ≤ Ψ r b
f 1 = ∑ c ∈ C v | v | 2 · Ψ f i e l d x , y
where C is a set of tuples with all the points that belong to the discretization of the circle (in our case, we have discretized in cells of 1 cm) within the radius of pheromones Ψ r b and v is a vector that is constructed with the coordinates of the tuple (x, y) for each element of the set C. Ψ field x , y is the component (x, y) of a matrix containing the pheromone reading of space coordinates (x, y) returned by the virtual sensor of stigmergy.
The second component f 2 determines the obstacle avoidance. It is defined as a vector that points to the area with fewer obstacles detected by the ultrasonic sensors:
f 2 = ∑ j = 1 | R | r j − p
where R is a set of detected obstacles, r j the position of the obstacle j and p the current robot position.
Finally, it must be noted that sensor readings and actuator commands are not always accurate. In this way, a random component is included to select the next move to make:
f 3 ( t ) = f 3 ( t − 1 ) + α 4 · rand
where t indicates the current time, rand is a vector of uniform random numbers, so that rand i ∈ [0, 1], and α 4 is a term that allows adjusting the importance of the random influence.

3.3. Behavior Analysis

Once this behavior has been presented, let us analyze its performance based on an environment of 100 × 100 m with the following microscopic parameters:
l i , Ψ r w , Ψ δ w , Ψ b w , Ψ δ b , α 1 , α 2 = ( 15 m , 10 m , 0.03 , 10 m , β , 0.2 , 0.4 , 0.4 )
β = swarm s i z e - robot i d swarm s i z e
Initially, a beacon robot will be available at position p 0 = (40, 50) of the map presented in Figure 2. New robots will be added progressively from this position each minute.
Therefore, the effectiveness of this covering process can be seen, which is completed within 30 min of operation. In the early stages of this behavior, the number of agents in the beacon state increases quickly. This is because an agent can easily find an empty area that is not covered by the RF signal. As this behavior advances, the number of wander agents is incremented, because it is more difficult to find an uncovered zone, and more wander agents are added to the system.
This behavior is completely decentralized, scalable and robust. Robustness is mainly derived from the advantages of using pheromones in navigation [41]. These allow unstructured exploration in complex environments and even in dynamic environments. As shown in Figure 3, all the executions achieve a full environment covering. It should be noted that due to space constrictions, we have not presented various trials with different maps, although in our tests, this algorithm is equally robust and highly tolerant to noise.

4. Obtaining the Energy Swarm Consumption

The microscopic behavior of the swarm, presented in the previous section, is executed individually by all members. The prediction of the global swarm behavior from the agents’ behavior requires analyzing the interaction between them. In our case, we are interested in analyzing how the agents’ state evolves while the behavior is executed. The following recurrence equation represents the number of agents in the wander and beacon state for each time n, if we assume that the added drones’ rate is constant:
w n b n t 1 n t 2 n t 3 n = − α 1 − α 2 + 1 0 α 3 − α 4 0 α 2 1 0 α 4 0 0 0 1 0 0 0 0 0 1 − 1 0 0 0 0 1 w n − 1 b n − 1 t 1 n − 1 t 2 n − 1 t 3 n − 1
Let A be the matrix:
A = − α 1 − α 2 + 1 0 α 3 − α 4 0 α 2 1 0 α 4 0 0 0 1 0 0 0 0 0 1 − 1 0 0 0 0 1
where α 1 ∈ R integrates the collision rate and how it affects the wander agents and the α 2 ∈ R term integrates the state transition between the wander and beacon states. Moreover, α 3 ∈ R determines the intensity of the addition of new drones per unit of time, and t 1 ∈ R is a variable that models that more drones will exist in the system as time runs.
As can be seen in the previous equation, a system of linear recurrence equations has been proposed to enable the calculation of its closed form. However, the term α 3 is not constant, because in the initial stages of the behavior, the space to be covered is empty, and therefore, most drones are in beacon mode. Variables t 2 ∈ R and t 3 ∈ R take into account this issue. We know w 0 = 0 and b 0 = 1 by the behavior definition, so that the linearization variables t1 0 = 1 and t2 0 = 1. However, α 4 and t3 0 = α 5 depend on the size and characteristics of the environment.
A linear recurrence is a sequence of vectors defined by the equation X i + 1 = A X i for some constant matrix A. To find this constant matrix A, we could find the matrix A n to find the n-th term. From the previous equation, the amount of existing agents in each state for a given time can be known, obtaining the expressions w(n) and b(n) from the matrix A n , which is presented in Equation (9).
This equation calculates the number of agents for each state with the parameters used in the next experimental simulations (negligible collision rate of α 1 = 0 and an aggregation drone rate of α 3 = 0.01).
w ( n ) = 1 α 2 2 − α 4 + − 0 . 1 α 2 α 3 + α 4 + α 2 α 4 α 5 1 − α 2 n + α 2 0 . 1 α 3 − α 4 α 5 + α 4 n
b ( n ) = 1 α 2 2 ( α 4 + α 2 0 . 1 α 3 − α 4 α 5 − α 4 1 − α 2 n + α 2 − 0 . 1 α 3 + α 2 0 . 1 α 3 n + 1 + α 4 α 5 − n )
It is easy to obtain the energy consumption W n of the swarm behavior in Watts from the start of the execution until a given time n:
W n = e f ∑ i = 0 n w ( i ) + e s ∑ i = 0 n b ( i )
From the equation above, the average consumption of the swarm and the average energy consumption by an individual UAV are obtained. Using this theoretical model, any parameter related to the energy consumed by the swarm can be calculated, provided that the values of α 1 , α 2 , α 3 , α 4 and α 5 are known.

4.1. Using the Energy Model

Before using the previous energy model, it is necessary to determine the following parameters of the previous equation: α 1 , α 2 , α 3 , α 4 and α 5 . As discussed above, α 1 = 0, α 3 = 0.01.
Parameters α 2 , α 4 and α 5 can be estimated from the environment complexity, the maximum distance between agents and the used pheromones’ radius, respectively. These parameters can be adjusted using hyperparameter optimization (by using, for example, grid search or Bayesian optimization). We have presented specific values obtained using Bayesian optimization [42] for our simulation environment, although the obtaining process is beyond the scope of this paper. Parameters have been adjusted for the map shown in Figure 2.
α 1 , α 2 , α 3 , α 4 , α 5 = 0 ; 0.00036 ; 0.01 ; 4.18 × 10 − 6 ; 2500
Therefore, it should be noted that the obtained hyperparameters depend, among other factors, on the type of map to be used. The parameters have been obtained based on maps with structure, size and coverage similar to those presented in Figure 4 and Figure 5. In order to predict the energy consumption for other maps, it is required either to obtain the hyperparameters that model them appropriately or to determine how the underlying behavioral and environmental characteristics of the macroscopic model are affected [43].
Our prediction model requires prior learning of the hyperparameters. This learning must be performed on a specific map. This map is presented in Figure 4. In order to verify the suitability of the presented predictive model, its performance will be tested in four new maps (presented in Figure 2) on which the model was not adjusted. To check the accuracy of the presented theoretical model, we have conducted a total of 250 simulations of our swarm behavior, using five different maps and taking into account the consumption required to achieve an 85% coverage of the environment area. This coverage percentage has been chosen as it is representative of the covering process. It also allows certain flexibility to the behavior, since there may be environments that, due to their configuration, do not achieve a total coverage or require a time-consuming process.
In Figure 4, an analysis of the simulated data compared to our theoretical model is presented for a specific map. The proposed state predicting models calculate correctly the transition between states that can be observed in the simulation. In addition, the energy prediction model substantially coincides with the energy required in the simulation. In this figure, the instantaneous consumption rate for each simulation step is also shown. It should be noted that the variations in energy consumption observed in this figure are produced each time an active drone is introduced into the system. This consumes a large amount of energy (120 W), required to stay in flight. When an agent lands, the use of energy decreases (beacons only consume 0.5 W) until another new drone is introduced.
In order to validate the model correctly, the same tests have been carried out, but using a set of different maps with a similar occupation and structure. Figure 5 shows the result of the conducted analysis. It can be seen that the results of the theoretical model are significantly similar to the practical results obtained. It is also shown that the required energy is higher as the map has more obstacles (Figure 5c), being lower in maps with lower density (Figure 5a,b,d). The covering process is successfully completed in the five maps considered. There is a slight deviation of the predicted energy for maps (a,b), although we consider this prediction to be acceptable. As mentioned above, the difference is due to the fact that the hyperparameters obtained for the map in Figure 4 are being used.
Using the presented model the swarm energy consumption (instant or accumulated) is calculated without requiring any physical evidence or simulation. We have conducted preliminary tests on physical robots that confirm the data predicted by the model using four drones and a smaller environment ( 30 × 30 m). If we compare the energy consumption of Random Waypoint (RWP), the most common alternative for mobility strategies, we found that its energy requirements are much higher than our approximation, and therefore, it is not well suited for UAVs.
The random waypoint model is the most used mobility model, because of both its simplicity and the lack of a clearly better option. The RWP takes a fixed number of nodes in a rectangle of fixed size. The simulation begins with the nodes uniformly distributed in the rectangle. Each node selects a random destination and a random velocity evenly distributed over the interval [vmin, vmax]. Once it reaches the destination, it pauses for a random time uniformly evenly distributed in [ P m i n , P m a x ] , then it chooses a new speed and destination and repeats the process.
Therefore, the consumption of the swarm is higher than our mobility strategy because since all the agents are in an energy state equivalent to wander consumption w, and consequently:
R W P W n ≈ e f ∑ i = 0 n w ′ ( i ) , where w ′ ( i ) ≫ w ( i )
As a result, when comparing the previous equation with the ones in Section 3, it must be pointed out that RWP requires much higher energy consumption because w’(i) ≫ w(i). In addition, due to its stochastic behavior, the RWP strategy will take much more time to complete a full covering of the environment.

5. Conclusions

Although in the literature, there are several models of mobility for the creation of ad-hoc networks, we found that either they are not well adapted to the energy required by UAVs or the motion models are unrealistic, because they do not consider the entity difference of connectivity and covering or because they are not robust enough for final implementation.
This article presents a behavior aimed at the deployment of a swarm of drones in an unknown environment, by carrying out an analysis of the energy needs required by this behavior for the development of its task. The consumption required by the swarm of UAVs has been analyzed both theoretically and practically. The ultimate goal of this behavior is the creation of MANET networks using UAVs. We consider that this task can be of critical relevance when carrying out rescue or search tasks in emergencies.
It has been proven experimentally that our behavior tends to cover a given area of the environment. We have analyzed the energy consumed by the swarm while executing this behavior. We have provided a theoretical model of the swarm energy consumption. We have also proved the validity of this model, using a realistic swarm of drones simulator, taking into account its main features. In addition, using our energy model, an analytic comparison between the random waypoint mobility strategy and our behavior has been provided. We found that the generic RWP strategy is not suitable to be used in UAV systems because of the energy restrictions of such systems.
In future works, we are currently developing a virtual pheromones sensor, both for indoor (based on Bluetooth Low Energy devices) and outdoor (using XBEE Mesh networks) environments, to test the behavior of our approach using a real UAV swarm. In addition, we will analyze the development of complementary behaviors to reduce both exploration time and energy while keeping the robustness advantages provided by the use of pheromones for communication.

Author Contributions

Formal analysis, M.P. and F.A.; Investigation, F.A., C.R. and F.P.; Methodology, F.A.; Supervision, R.R. and F.P.; Validation, M.P. and C.R.; Writing—original draft, R.R.; Writing—review and editing, F.P.

Funding

This research was funded by the Ministerio de Economía y Competitividad (Spain), project TIN2013- 40982-R and by the Programa Redes-I3CE de Investigación en Docencia Universitaria 2016-2017, Red ICE 3701, of the Instituto de Ciencias de la Educación of the University of Alicante.

Acknowledgments

This work was partially supported by the Ministerio de Economía y Competitividad (Spain), project TIN2013-40982-R, the FEDER funds and the “Red de Investigación en el uso del aprendizaje colaborativo para la adquisición de competencias básicas. El caso Erasmus+ EUROBOTIQUE”, Red ICE3701, curso 2016–2017.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Brambilla, M.; Ferrante, E.; Birattari, M.; Dorigo, M. Swarm robotics: A review from the swarm engineering perspective. Swarm Intell. 2013, 7, 1–41. [Google Scholar] [CrossRef]
  2. Payton, D.; Daily, M.; Estowski, R.; Howard, M.; Lee, C. Pheromone robotics. Auton. Robots 2001, 11, 319–324. [Google Scholar] [CrossRef]
  3. Arvin, F.; Krajník, T.; Turgut, A.E.; Yue, S. COSΦ: Artificial pheromone system for robotic swarms research. In Proceedings of the 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Hamburg, Germany, 28 September–2 October 2015; pp. 407–412. [Google Scholar]
  4. Alshbatat, A.I.; Dong, L. Performance Analysis of Mobile Ad Hoc Unmanned Aerial Vehicle Communication Networks with Directional Antennas. Int. J. Aerosp. Eng. 2010, 2010, 1–14. [Google Scholar] [CrossRef]
  5. Bouachir, O.; Abrassart, A.; Garcia, F.; Larrieu, N. A mobility model for UAV ad hoc network. In Proceedings of the 2014 International Conference on Unmanned Aircraft Systems (ICUAS), Orlando, FL, USA, 27–30 May 2014; pp. 383–388. [Google Scholar]
  6. Conejero, J.M.; Brito, I.S.; Moreira, A.; Cunha, J.; Araújo, J. Modeling the Impact of UAVs in Sustainability. In Proceedings of the 2016 IEEE 24th International Requirements Engineering Conference Workshops (REW), Beijing, China, 12–16 September 2016; pp. 208–216. [Google Scholar] [CrossRef]
  7. Rosati, S.; Kruzelecki, K.; Heitz, G.; Floreano, D.; Rimoldi, B. Dynamic Routing for Flying Ad Hoc Networks. IEEE Trans. Veh. Technol. 2016, 65, 1690–1700. [Google Scholar] [CrossRef]
  8. Tardós, J.; Aragues, R.; Sagüés, C.; Rubio, C. Simultaneous deployment and tracking multi-robot strategies with connectivity maintenance. Sensors 2018, 18, 927. [Google Scholar] [CrossRef] [PubMed]
  9. Davoodi, M.; Velni, J.M.; Li, C. Coverage Control with Multiple Ground Robots for Precision Agriculture. Mech. Eng. Mag. Sel. Art. 2018, 140, S4–S8. [Google Scholar] [CrossRef]
  10. Sallam, G.; Baroudi, U. Cooperative Robot Deployment: Simulation and Real Experimental Analysis. Arab. J. Sci. Eng. 2018. [Google Scholar] [CrossRef]
  11. Roberts, J.F.; Stirling, T.S.; Zufferey, J.C.; Floreano, D. 2.5 D infrared range and bearing system for collective robotics. In Proceedings of the 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems, St. Louis, MO, USA, 10–15 October 2009; pp. 3659–3664. [Google Scholar]
  12. Li, Q.; Rosa, M.D.; Rus, D. Distributed algorithms for guiding navigation across a sensor network. In Proceedings of the 9th Annual International Conference on Mobile Computing and Networking, San Diego, CA, USA, 14–19 September 2003; pp. 313–325. [Google Scholar]
  13. Nouyan, S.; Campo, A.; Dorigo, M. Path formation in a robot swarm. Swarm Intell. 2008, 2, 1–23. [Google Scholar] [CrossRef]
  14. Nouyan, S.; Groß, R.; Bonani, M.; Mondada, F.; Dorigo, M. Teamwork in self-organized robot colonies. IEEE Trans. Evol. Comput. 2009, 13, 695–711. [Google Scholar] [CrossRef]
  15. Nardi, R.D.; Holland, O. Swarmav: A Swarm of Miniature Aerial Vehicles. 2006. Available online: http://cogprints.org/5569/ (accessed on 1 July 2018).
  16. Oh, P.Y.; Joyce, M.; Gallagher, J. Designing an aerial robot for hover-and-stare surveillance. In Proceedings of the 2005 ICAR’05 12th International Conference on Advanced Robotics, Seattle, WA, USA, 18–20 July 2005; pp. 303–308. [Google Scholar] [Green Version]
  17. Rudol, P.; Wzorek, M.; Conte, G.; Doherty, P. Micro unmanned aerial vehicle visual servoing for cooperative indoor exploration. In Proceedings of the 2008 IEEE Aerospace Conference, Big Sky, MT, USA, 1–8 March 2008; pp. 1–10. [Google Scholar]
  18. Hoffmann, G.; Rajnarayan, D.G.; Waslander, S.L.; Dostal, D.; Jang, J.S.; Tomlin, C.J. The Stanford testbed of autonomous rotorcraft for multi agent control (STARMAC). In Proceedings of the 23rd Digital Avionics Systems Conference, Salt Lake City, UT, USA, 28 October 2004; Volume 2, pp. 1–10. [Google Scholar]
  19. Melhuish, C.; Welsby, J.; Greenway, P. Gradient ascent with a group of minimalist real robots: Implementing secondary swarming. In Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, Yasmine Hammamet, Tunisia, 6–9 October 2002; Volume 2, pp. 509–514. [Google Scholar]
  20. Sartoretti, G.; Hongler, M.O. Interacting Brownian Swarms: Some Analytical Results. Entropy 2016, 18, 27. [Google Scholar] [CrossRef]
  21. Gupte, S.; Mohandas, P.I.T.; Conrad, J.M. A survey of quadrotor Unmanned Aerial Vehicles. In Proceedings of the 2012 Proceedings of IEEE Southeastcon, Orlando, FL, USA, 15–18 March 2012; pp. 1–6. [Google Scholar]
  22. Burgard, W.; Moors, M.; Stachniss, C.; Schneider, F.E. Coordinated multi-robot exploration. IEEE Trans. Robot. 2005, 21, 376–386. [Google Scholar] [CrossRef] [Green Version]
  23. Bamberger, R.J.; Watson, D.P.; Scheidt, D.H.; Moore, K.L. Flight demonstrations of unmanned aerial vehicle swarming concepts. Johns Hopkins APL Tech. Dig. 2006, 27, 41–55. [Google Scholar]
  24. Filliat, D.; Meyer, J.A. Map-based navigation in mobile robots: I. A review of localization strategies. Cogn. Syst. Res. 2003, 4, 243–282. [Google Scholar] [CrossRef]
  25. Grzonka, S.; Grisetti, G.; Burgard, W. Towards a navigation system for autonomous indoor flying. In Proceedings of the 2009 ICRA’09. IEEE International Conference on Robotics and Automation, Kobe, Japan, 12–17 May 2009; pp. 2878–2883. [Google Scholar]
  26. Stirling, T.; Roberts, J.; Zufferey, J.C.; Floreano, D. Indoor navigation with a swarm of flying robots. In Proceedings of the 2012 IEEE International Conference on Robotics and Automation (ICRA), Saint Paul, MN, USA, 14–18 May 2012; pp. 4641–4647. [Google Scholar]
  27. Corke, P.; Peterson, R.; Rus, D. Localization and navigation assisted by networked cooperating sensors and robots. Int. J. Robot. Res. 2005, 24, 771–786. [Google Scholar] [CrossRef]
  28. Hu, W.; Liang, H.; Peng, C.; Du, B.; Hu, Q. A Hybrid Chaos-Particle Swarm Optimization Algorithm for the Vehicle Routing Problem with Time Window. Entropy 2013, 15, 1247–1270. [Google Scholar] [CrossRef] [Green Version]
  29. Corke, P.; Peterson, R.; Rus, D. Coordinating aerial robots and sensor networks for localization and navigation. In Proceedings of the DARS’04 7th International Symposium on Distributed Autonomous Robotic Systems, Toulouse, France, 23–25 June 2007. [Google Scholar]
  30. Stirling, T.; Wischmann, S.; Floreano, D. Energy-efficient indoor search by swarms of simulated flying robots without global information. Swarm Intell. 2010, 4, 117–143. [Google Scholar] [CrossRef] [Green Version]
  31. Zhao, Z.; Braun, T. Topology Control and Mobility Strategy for UAV Ad-hoc Networks: A Survey. In Proceedings of the Joint ERCIM eMobility and MobiSense Workshop, Santorini, Greece, 8 June 2012. [Google Scholar]
  32. Arafah, M.; Alhindi, H.; Mathkour, H.; Faisal, M.; Lytras, M.D. Smart systems approach for development of explicit congestion marking and traffic engineering model for Diffserv/MPLS networks. J. Ambient Intell. Humaniz. Comput. 2018, 1–11. [Google Scholar] [CrossRef]
  33. Torres-Ruiz, M.; Lytras, M.D.; Mathkour, H. Innovative services and applications of wireless sensor networks: Research challenges and opportunities. Int. J. Distrib. Sens. Netw. 2018, 14, 1550147718772973. [Google Scholar] [CrossRef]
  34. Lytras, M.D.; Visvizi, A. Who Uses Smart City Services and What to Make of It: Toward Interdisciplinary Smart Cities Research. Sustainability 2018, 10, 1998. [Google Scholar] [CrossRef]
  35. Visvizi, A.; Lytras, M. It’s Not a Fad: Smart Cities and Smart Villages Research in European and Global Contexts. Sustainability 2018, 10, 2727. [Google Scholar] [CrossRef]
  36. O’Hara, K.J.; Balch, T.R. Distributed path planning for robots in dynamic environments using a pervasive embedded network. In Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, New York, NY, USA, 19–23 July 2004; Volume 3, pp. 1538–1539. [Google Scholar]
  37. Batalin, M.A.; Sukhatme, G.S. Coverage, exploration and deployment by a mobile robot and communication network. Telecommun. Syst. 2004, 26, 181–196. [Google Scholar] [CrossRef]
  38. Stirling, T.; Floreano, D. Energy-Time Efficiency in Aerial Swarm Deployment; Springer: New York, NY, USA, 2013. [Google Scholar]
  39. Luke, S.; Cioffi-Revilla, C.; Panait, L.; Sullivan, K.; Balan, G. MASON: A Multiagent Simulation Environment. Simulation 2005, 81, 517–527. [Google Scholar] [CrossRef] [Green Version]
  40. Chipmunk Physics Library. Available online: http://chipmunk-physics.net (accessed on 15 October 2018).
  41. Russell, K.; Schader, M.; Andrea, K.; Luke, S. Swarm Robot Foraging with Wireless Sensor Motes. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (AAMAS2015), Istanbul, Turkey, 4–8 May 2015; pp. 287–295. [Google Scholar]
  42. Lévesque, J.C.; Gagné, C.; Sabourin, R. Bayesian hyperparameter optimization for ensemble learning. arXiv, 2016; arXiv:1605.06394. [Google Scholar]
  43. Aznar, F.; Pujol, M.; Rizo, R.; Rizo, C. Modelling multi-rotor UAVs swarm deployment using virtual pheromones. PLoS ONE 2018, 13, e0190692. [Google Scholar] [CrossRef] [PubMed]
Symmetry 10 00632 g001 550
Figure 1. Summary scheme of the main subjects involved in this work.
Figure 1. Summary scheme of the main subjects involved in this work.
Symmetry 10 00632 g001
Symmetry 10 00632 g002 550
Figure 2. (a) Maps used in the experimentation. The starting points of the deployment process in these maps are the following ones (top to bottom): (i) ( x , y ) = ( 35 , 55 ) , (ii) ( x , y ) = ( 45 , 50 ) , (iii) ( x , y ) = ( 35 , 50 ) and (iv) ( x , y ) = ( 15 , 50 ) . (b,c) Evolution of a selected execution for two sample maps, where white areas are free zones and black areas represent obstacles. Steps 0, 500, 1500, 2000 are shown. In addition, the obstacle detection area of the robots (circle) areas with pheromones (blue) and the coverage range for each agent (red) is presented.
Figure 2. (a) Maps used in the experimentation. The starting points of the deployment process in these maps are the following ones (top to bottom): (i) ( x , y ) = ( 35 , 55 ) , (ii) ( x , y ) = ( 45 , 50 ) , (iii) ( x , y ) = ( 35 , 50 ) and (iv) ( x , y ) = ( 15 , 50 ) . (b,c) Evolution of a selected execution for two sample maps, where white areas are free zones and black areas represent obstacles. Steps 0, 500, 1500, 2000 are shown. In addition, the obstacle detection area of the robots (circle) areas with pheromones (blue) and the coverage range for each agent (red) is presented.
Symmetry 10 00632 g002
Symmetry 10 00632 g003 550
Figure 3. Number of individuals in each state and percentage of area covered by an individual given a simulation step, where each step is equal to 0.5 s. The mean and standard deviation for 30 different runs are shown until the swarm has covered 85% of the environment.
Figure 3. Number of individuals in each state and percentage of area covered by an individual given a simulation step, where each step is equal to 0.5 s. The mean and standard deviation for 30 different runs are shown until the swarm has covered 85% of the environment.
Symmetry 10 00632 g003
Symmetry 10 00632 g004 550
Figure 4. In this picture, both the mathematical models and the results of the simulation are shown. We have provided the number of agents in the wander and beacon states, the instant energy consumed by the swarm, the amount of environment covered and the average energy consumed. For these simulations, the average and standard deviation of 50 different executions of our behavior are shown. As can be seen, the models presented and the simulations coincide substantially.
Figure 4. In this picture, both the mathematical models and the results of the simulation are shown. We have provided the number of agents in the wander and beacon states, the instant energy consumed by the swarm, the amount of environment covered and the average energy consumed. For these simulations, the average and standard deviation of 50 different executions of our behavior are shown. As can be seen, the models presented and the simulations coincide substantially.
Symmetry 10 00632 g004
Symmetry 10 00632 g005 550
Figure 5. In this picture, both the mathematical models and the results of the simulation are shown for four different maps. The energy consumption of the swarm vs. the predicted energy consumption for four maps (a–d) is shown. Each map is shown on the right side of its corresponding figure. For each of them, we have provided the number of agents in the wander and beacon states, the instant energy consumed by the swarm, the amount of environment covered and the average of energy consumed. For these simulations, the average and standard deviation of 50 different executions of our behavior are shown. As can be seen, the models presented and the simulations achieve very similar results.
Figure 5. In this picture, both the mathematical models and the results of the simulation are shown for four different maps. The energy consumption of the swarm vs. the predicted energy consumption for four maps (a–d) is shown. Each map is shown on the right side of its corresponding figure. For each of them, we have provided the number of agents in the wander and beacon states, the instant energy consumed by the swarm, the amount of environment covered and the average of energy consumed. For these simulations, the average and standard deviation of 50 different executions of our behavior are shown. As can be seen, the models presented and the simulations achieve very similar results.
Symmetry 10 00632 g005

Share and Cite

MDPI and ACS Style

Aznar, F.; Pujol, M.; Rizo, R.; Pujol, F.A.; Rizo, C. Energy-Efficient Swarm Behavior for Indoor UAV Ad-Hoc Network Deployment. Symmetry 2018, 10, 632. https://doi.org/10.3390/sym10110632

AMA Style

Aznar F, Pujol M, Rizo R, Pujol FA, Rizo C. Energy-Efficient Swarm Behavior for Indoor UAV Ad-Hoc Network Deployment. Symmetry. 2018; 10(11):632. https://doi.org/10.3390/sym10110632

Chicago/Turabian Style

Aznar, Fidel, Mar Pujol, Ramon Rizo, Francisco A. Pujol, and Carlos Rizo. 2018. "Energy-Efficient Swarm Behavior for Indoor UAV Ad-Hoc Network Deployment" Symmetry 10, no. 11: 632. https://doi.org/10.3390/sym10110632

APA Style

Aznar, F., Pujol, M., Rizo, R., Pujol, F. A., & Rizo, C. (2018). Energy-Efficient Swarm Behavior for Indoor UAV Ad-Hoc Network Deployment. Symmetry, 10(11), 632. https://doi.org/10.3390/sym10110632

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

Article Metrics

Back to TopTop