Formation-based Selection of Drone Swarm Services

Let us assume a hospital uses drone delivery services to get medical equipment delivered on a regular basis. These pieces of equipment must be delivered together at the same time on request. In this case, a swarm of drones would be needed to deliver multiple packages to the hospital by a certain deadline. In this context, a swarm of drones would use a skyway network whose vertices would consist of building rooftops with charging stations (see Fig. 1). The main challenge is to determine the best skyway path to deliver all packages within the expected delivery time. In addition, extrinsic constraints would have to be addressed during medical supplies delivery. These constraints include the limited number of charging stations at intermediate nodes. The drones need to recharge due to their limited flight ranges. Another extrinsic constraint is the existence of environmental uncertainties such as wind. Therefore, we reformulate the problem of delivery as finding the best service paths in the skyway given these constraints.

The first task is to select the best set of drones that can meet the deadline while carrying the equipment. The second task is to select the best formation. The swarm will rely on its formation to have an efficient delivery. In this paper we assume the drones set is selected and we focus on the second task. We investigate the effect of different drones formations in a swarm under different wind conditions. Drones energy consumption is affected heavily by wind conditions (Takegami et al., 2019). We propose to implement adaptive swarm formations with the goal of reducing the energy consumption under different wind conditions. The swarm needs to minimize the energy consumption to reduce the stops for battery recharges. This in return, will reduce the overall delivery time by reducing the charging and waiting times caused by sequential recharges at each node. Each segment in a skyway network may have a different wind speed and wind direction. Therefore, we aim to select the best possible swarm formation for every wind condition. This will guide the $SDaaS$ services (skyway segments) selection process.

• •

  Preset swarms: A preset swarm is a swarm whose formation is determined before the selection and composition processes. The decision of the formation is made before the travel is initiated and continues throughout the trip without changing (Fig.2(a)). In this case, selecting the optimal formation relies on the average wind conditions of all $SDaaS$ services. Computations regarding the wind effect on the power consumption are based on the pre-decided swarm formation. The selection eliminates $SDaaS$ where the swarm cannot travel in its pre-decided formation. Services in which the drones battery consumption is not sufficient to continue the travel safely are discarded. The selection process in this type is straight forward and does not require heavy computations during the service selection process. However, it comes with the cost of higher energy consumption. This is because the selection depends on the average wind condition and not the specific conditions in every skyway segment. We refer to this type of selection that deals with preset swarms as Fixed Selection.

• •

  Flexible swarms: A flexible swarm is a swarm whose formation decisions are made throughout the trip. For every skyway segment, the swarm decides the best formation to take based on the wind condition of the segment. Hence, the swarm does not travel from the source to the destination in one formation. The formation changes as the wind condition changes (Fig.2(b)). As mentioned earlier, for every wind condition there is an optimal flight formation that reduces the overall energy consumption of a swarm. Computations regarding the wind effect on the power consumption will be different at each segment based on the decided formation. The selection process eliminates $SDaaS$ services that the swarm cannot travel in regardless of the formation it takes. Services in which the drones battery consumption is not sufficient to continue the travel safely are discarded. This type of swarm overcomes the problem of higher energy consumption due to averaged conditions. We refer to this type of selection that deals with flexible swarms as Adaptive Selection.

Computational fluid dynamics is a branch of fluid mechanics that uses numerical analysis and data structures to analyze and solve problems that involve fluid flows (Anderson and Wendt, 1995). In our case, we consider the wind as the fluid that we analyse its effect on drone swarms. We vary the conditions of wind including speed and direction. We adopt Ansys Discovery Live ⁴⁴4Ansys Discovery Live. https://www.ansys.com/products/3d-design/ansys-discovery-live to simulate the different formations under different conditions. Ansys Dicovery Live allows us to compute the drag force on all the faces of the drone model. This drag value is used to compute the power consumption using the following equation:

where $P$ is the power in Watts, $F_{D}$ is the drag force in Newtons, and $v$ is the velocity of the drone in meters/sec.

In this paper, we focus on modeling the energy consumption of different flight formations using quadcoptors. Although there are many types of drones, including fixed-wing and single-rotor helicopters, a quacopter is the most popular design for small UAVs. A quacopter, or a quadrotor, is a multirotor helicopter lifted and propelled by four rotors. Big companies like DJI, Parrot, and 3DR are churning out quadcopters to take on more roles. One of the main reasons for the popularity of quadcopters is its mechanical simplicity to take-off and hover compared to other drones. In addition, the cost of their production is lesser compared to other drone types (Pounds et al., 2006). In this work, we use the DJI Phantom 3 Model for all our experiments.

We use the Beaufort wind force scale to categorize the wind speeds. This scale relates wind speed to observed conditions at sea or on land (Huler, 2007). Table 1 shows the different wind speeds using Beaufort scale. We only consider Beaufort numbers 0 to 6 as the most commercial quadcopters are safe to fly under 13.8 m/s wind speed. We also consider three directions respective to the swarm origin including Front, Right, and Left. In the following subsections, we show the effect of the upwash and downwash forces generated by front drones in the swarm. We then test the different swarm formations under different wind conditions. This will help us select the best formation for every wind condition to be used in the $SDaaS$ service selection phase.

There are two types of selections we propose in this paper: Fixed and Adaptive. We create two algorithms for each selection type. A selection consists of two main components. The first is the selection of the swarm formation. The second is the selection of the $SDaaS$ services. We assume the drones in the swarm are already selected. We also assume that all the drones in the swarm carry the same payload. We also assume that the drones fly in a relatively similar altitude throughout the journey. Hence, the effect of varying air pressure is minimal and is not considered in this work. We focus on studying the effect of formations on the service selection.

1. (1)

   Fixed SDaaS Selection
   In a fixed selection all wind conditions of all the services connecting the source and destination nodes are averaged. We take the average wind speed value between all skyway segments and the most common wind direction. We use this averaged value to choose the best fixed formation that will traverse the network without changing. Then, we check all the services, i.e. skyway segments, where all the drones in the swarm will have successful flights to the next node. A successful flight is a flight where all the drones in the swarm have sufficient power to reach the destination $\forall E_{c}<=100\%$. The total energy consumption $E_{c}$ is equal to the sum of energy consumption due to flight range, wind drag forces, and upwash/downwash forces, $E_{c}=E_{fr}+E_{drag}+E_{upwash/downwash}$. Algorithm 1 describes the fixed selection process.

2. (2)

   Adaptive SDaaS Selection
   In an adaptive selection, the formation of the swarm can change at every skyway segment. In this type of selection, we look at every skyway segment and choose the best formation accordingly. The best formation is the formation that reduces the energy consumption due to wind drag force $E_{drag}$ and upwash/downwash forces $E_{upwash/downwash}$. Then, we check all the services, i.e. skyway segments, where all the drones in the swarm will have successful flights to the next node. A successful flight is a flight where all the drones in the swarm have sufficient power to reach the destination $\forall E_{c}<=100\%$. Note here that selecting the optimal formation does not guarantee a successful flight. This is because the energy consumption is affected by other factors like the flight range and payload. The total energy consumption $E_{c}$ is equal to the sum of energy consumption due to flight range, wind drag forces, and upwash/downwash forces. $E_{c}=E_{fr}+E_{drag}+E_{upwash/downwash}$. Algorithm 2 describes the adaptive selection process.

Assuming that the swarm size is 5, i.e. the swarm composes of a set of five identical drones, we run Ansys software to test the drag forces on every individual drone in the swarm numbered in Fig. 6. We used a DJI Phantom 3 model to run our tests⁵⁵5DJI Phantom 3 3D model: https://grabcad.com/library/dji-phantom3-1. We then compute the average energy consumption of the full swarm. We fix the wind speed to Beaufort scale 5, i.e. 9.35m/s to test the drag from different wind directions. We also assume that the drones are flying at a speed of 15.6m/s. Table 2 summarizes the results of the first experiment. We can notice that the best formation that reduces the drag forces when the wind comes from the front is the Column formation. On the other hand, the Front formation performed best when the wind is coming from the right or left. Note that we do not consider the upwash/downwash forces in this experiment. If we look at the drag forces of individual drones, we can get insights on which drones face most drag due to wind:

• •

  In a Column Formation, the front drones protect the drones at the back from the front wind. Hence, the drag is in a decreasing manner from drone 1 to 5. However, when the wind comes from the right or left, the drones at the edge (1 and 5) face more drag than the inner drones. This is because we compute the drag on all the faces of the drone. The side faces of the inner drones are protected from the wind by the neighbouring drones.

• •

  In a Front Formation, a reciprocal behaviour to the column formation is seen. In a front wind, the edge drones (1 and 5) face more drag than the inner drones. This is because the side faces of the inner drones are protected from the wind by the neighbouring drones. In a right and left winds, the drag is in a decreasing manner with the maximum drag at the first drone facing the wind direction. The rest of the drones are protected by the drones ahead.

• •

  The Echelon Formation is one of the highest formations facing drag forces. However, we can notice, that the drones consume energy in a decreasing manner from drones 1 to 5 in a front and left wind direction as some parts of the drones are covered by the front drones. The opposite behavior is noted for the right wind direction with drone 5 first facing the wind.

• •

  In a Vee Formation, the drones facing the wind experience more drag. With a front wind, drone 1 experiences maximum drag followed by drones 4 and 5 at the back. This aligns with the study made in (Mirzaeinia et al., 2019) which found that fixed-wing drones in a Vee formation experience more drag at the front and back of the swarm compared to the inner drones. When wind comes from the right or the left, the drones closer facing the wind experience more drag compared to the rest of the swarm which are protected in the swarm.

• •

  In a Diamond Formation, the drag forces on drones 3 and 5 are significantly lower than the others in the front wind. This can be important in applications where the most valuable delivery items are carried by these specific drones that fly in the formation to be protected from the wind. Similar behavior is noticed in drones 2 and 3 with the right wind and drones 3 and 4 with the left wind.

In the second experiment, we evaluate the combined effect of drag forces with the upwash/downwash forces. We can see from Table 3 that the formations that consume the least amount of energy is the Vee formation for the front wind and the Diamond formation for right and left winds. Although the Column and Front formation performed better when only the drag forces are computed, the Vee and Diamond outperformed them due to the upwash/downwash forces from the drones swarm positions. The energy consumption is computed using Equation 1.

In the third experiment, we evaluate the effect of varying different wind speeds according to Beaufort scale. The results of this experiment on the Vee formation are shown in Fig.7. As shown, Beaufort scales 0 and 1 have minimal effect on the drag value. As the scale increases the drag value approximately doubles at each scale number. Similar behavior is seen for the different formations. Since the behavior is similar in all formations, the selection of the formation mainly depends on the wind direction rather than the speed. The drag values based on the speed are used for the service selection in the next subsection.

The dataset used in the experiments is an urban road network dataset from the city of London with nodes representing intersections and edge length representing the distances between the nodes (Karduni et al., 2016). For the experiments, we took a sub-network of connected nodes with size 2732 to mimic a possible arrangement of a skyway network. We then synthesize different wind speeds and wind directions for every segment. We assume that the drones model is DJI Phantom 3 flying at a speed of 15.6 m/s. The rest of the experimental variables are summarized in Table 4. These variables are used to compute the energy consumption based on the flight range, drag forces, and upwash/downwash forces.

In the first experiment, we evaluate the energy consumption of both selection algorithms, i.e. Fixed and Adaptive. We group the output of the algorithms, i.e. the selected services, based on their distances. Unselected services are discarded as the swarm will fail its journey due to lack of battery power in these services. The x-axis in Fig.8 represents the distance and the y-axis represents the energy consumption due to drag forces and upwash/downwash forces. As shown in the graph, the proposed adaptive algorithm outperforms the fixed algorithm significantly. The adaptive algorithm saves more energy since the optimal formation that saves the most energy is selected at each skyway segment.

In the second experiment, we repeat the first experiment but we group the services based on their wind speeds rather than distance. This will allow us to see the performance of both algorithms under different wind conditions. As shown in Fig. 9 the adaptive algorithm outperforms the fixed algorithm in terms of energy consumption. This is because the drones in the fixed algorithm select the formation based on average wind conditions which may not be the optimal solution under different wind conditions.

Although the adaptive algorithm outperformed the fixed algorithm, it comes with the cost of execution time. This is shown in Fig.10 where the x-axis represents the number of nodes of different sub-networks of our full network. As the network size increases the adaptive algorithm takes more execution time compared to the fixed algorithm. We conclude, that depending on the application, the choice of algorithm implementation would be different. For example, in the case of an emergency where we need to ensure a fast delivery with the least number of stops for recharging, more resources may be utilized for the computation. The computations are usually done on edge nodes. On the other hand, if the delivery time is flexible but the number of resources for computation is limited, then the fixed algorithm would be the better choice.