New Evolutionary Algorithm Approach for Centralized Drone Mesh Networks

We all know that in the past, drones (UAVs) were mostly used in the military operations in order to monitor, overview as well as mainly prevent pilot losses. Thanks to the technological revolution, drones have been commercialized and made a product that is cost-effective and useful in both residential and commercial applications.

However, among the challenges of drones as a rising technology, there is the communication network among the UAVs which seems to remain a challenging task. The authors, Sérgio Sabino and António Grilo of the Instituto Superior Técnico, a public school of engineering and technology and part of Universidade de Lisboa, have submitted a paper to address these issues, presenting a new, revolutionary multi-objective algorithm approach that is optimized to cover all ground nodes using a minimum number of drones – all while maximizing the fulfillment of their data requirements. The paper is titled, Centralized Unmanned Aerial Vehicle (UAV) Mesh Networks Placement Scheme‘.

Finding a Set of Optimal Positions – Ground Nodes for UAVs

The algorithm also focuses on finding a set of optimal positions to place UAVs (as the groud nodes) and therefore cover the target area and the data rate requirement of the ground nodes. Thanks to simulation, the authors saw that this algorithm can optimize the UAV placement given the requirement and the positions of the ground nodes in a specific geographical area.

System model overview

According to the authors:

“UAV placement schemes can help to mitigate the aforementioned issues by finding suitable 51 positions to place UAVs while maintaining connectivity and improving the network performance. 52 The UAV placement optimization schemes can be classified as centralized or distributed. The former 53 assumes that the UAV positions are selected by a centralized entity and conveyed to the UAVs by 54 means of special purpose long-range low bit rate radio interface. On the other hand, in distributed 55 approaches, UAVs work cooperatively to adjust their position based on local interactions to achieve 56 optimal coverage.”

The work, as such, is more related with centralized placement optimization and focuses on minimizing the number of UAVs needed to service the ground network (a number which must be limited), the inter-UAV links and their maximum range, the end-to-end inter-GN traffic and the GN-UAV links as orthogonal.

Defining the Problem and Formulating an UAV Placement Optimization as the Main Model

Through the use of graphs, experiments and estimates, the authors define the problem (Multi-Objective Optimization Problem) and formulate a proposed UAV Placement Optimization as their model.

With this, they manage to minimize the number of UAVs in their study, estimating the ground areas and sub-areas which need to be adjusted. The algorithm takes into account multiple uses as well as many factors (initial population, selection, genetic operators, crossover etc.)

Crossover procedure

UAV removal and reallocation procedures during mutation

In the “Discussion” section, the authors note that “the experimental results presented in previous section are specific to the proposed scenarios and 342 assumptions which were considered in our system model. In a realistic environment, one should take 343 into account additional constraints such as the effect of interference, GN mobility, number of GNs to 344 be covered, terrain conditions, etc.”

Results and Findings

As such, the paper presents an optimized placement scheme for UAV access points that provide network connectivity to the ground nodes with differentiated data rate requirements. Therefore, the main goal of the proposed algorithm is to deploy as few as possible connected UAVs to cover and satisfy the aforementioned requirements of the GNs.

As the simulation results show (and confirm), this algorithm optimizes the UAV placement given the requirements and positions of the GNs, considering the trade-off between the number of UAVs and the quality of the coverage.

Citation: Sabino, S.; Grilo, A. Centralized Unmanned Aerial Vehicle (UAV) Mesh Networks Placement Scheme: A Multi-Objective Evolutionary Algorithm Approach. Preprints 2018, 2018100335 (doi: 10.20944/preprints201810.0335.v1). http://www.preprints.org/manuscript/201810.0335/v1