The recent advances in unmanned aerial vehicles (UAVs) enormously improve their utility and expand their application scope. The UAV and swarm implementation further prevail in Smart City practices with the aid of edge computing and urban Internet of Things. The lead–follow formation in UAV swarm is an important organization means and has been adopted in diverse exercises, for its efficiency and ease of control. However, the reliability of centralization makes the entire swarm system in risk of collapse and instability, if a fatal fault incident happens in the leader. Here, we propose a voting-based leader election scheme inspired by the Raft method in distributed computation consensus to build a mechanism helping the distributed swarm recover from possible failures.
The trend of global urbanization is seemingly increasing as the world population is expected to double in the next few decades [1
]. It is undoubted that citizens and governors are now concentrating on multiple fields of cities, i.e., indispensable management [3
], sustainable development [4
], trustable security [2
], reliable environment protection [5
], etc. The smart city concept [6
] is raised for the above issues and has been evolving [8
] for decades. The recent development of Internet of Things (IoT) [9
], fifth-generation (5G) communication [11
] and multi-access edge computing (MEC) techniques [12
] further stimulate implementations and applications for efficient city operation, for instance information framework [4
], anomaly identification [14
] and cyber-threat detection [15
Although advancing technologies empower modern smart city schemes, drawbacks and challenges exist in several components of smart city operations [1
]. For example, the transportation system in cities [16
] is one of special interest. To relieve traffic congestions in various periods, massive amounts of sensors, cameras and other equipments should be widely deployed to gather abundant data and gain a global view for subsequent deep analysis [3
]. This inevitably induces massive cost and numerous static deployments fail to collect real-time data [1
]. Another case would be efficient communication and networking. One may argue that the 5G technique enriches mobile applications and accelerates the emergence of diverse scenarios, promoting the potential of current and future solutions [17
]. Despite some efforts having been made to improve the availability and quality of experience (QoE) [19
], the placement and cost issues would still affect adaptation to dramatically dynamic implementations [11
], i.e., natural catastrophes [22
] and military events [23
Now the unmanned aerial vehicles (UAVs) or drones-enabled scheme is drawing increasing attention and is generally accepted to be a promising way to alleviate some difficulties, such as relayed long-range communication [1
], air-quality sensing [5
], traffic improving [3
] and information sharing in battlegrounds [23
]. In effect, unmanned aerial vehicles (UAVs) have high potential, nevertheless one single UAV may have limitations in energy, sensor loads, computing and communication capacities [25
]. Multiple UAVs, which can be called UAV swarm in a large-scale number, are put forward to cooperatively accomplish tasks that a single drone fails to tackle [27
]. One high-performance way to organize UAVs is the lead–follow formation. It appoints a UAV to acting as leader, who takes charge of spreading unambiguous instructions and coordinating behaviors of subordinates [22
], known as a lead–follow
manner. The rest of swarm members are thus called followers. The focus of this article is on the lead–follow UAV swarm manner.
The limitation of lead–follow is straightforward. As a leader is centralized node, it is also a fragile node, which make the whole swarm fragile [23
]. Notice that we use “fragile
” with a global perspective to describe one that can impose influence on all other entities. In other words, if a leader cannot continue its functionality because of crashing, malfunctioning or being faulty, the swarm probably falls apart and causes a holistic swarm fault. In the lead–follow manner, a failure of the leader is likely to cause collapse and chaos of the swarm system. The lead-election is to guarantee the fault tolerance and adapt to complex, unexpected and even potentially hostile circumstances. An intuitive and viable approach to guarantee swarm working is to rapidly determine a back-up UAV to tolerate exceptions. It is nonetheless static and cannot find the optimal one based on real situations. The conventional way could be presetting a series of successors, which seems to be helpful in changeless environment. However, there might be some problems. The predetermined method is probably not able to foresee the highly uncertain situations and may not result in a suitable leader for a given task. For instance, one individual is more likely to be elected if it happens to be within the task region, or occupy the full information of targets, especially in complex and harsh battlegrounds [23
]. Another case could be that a new leader should be close enough to the ground stations for forwarding of appropriate instructions, communication relay and orchestration [22
]. Therefore, there needs to be an elastic and adjustable way to encourage the rest to make a decision [31
]. The goal of this research is to make the rest of the collective UAVs recover from the systematic faults. We manage to construct an effective voting-based algorithm to discover an optimal drone to be the leader in condition that the original leader is disabled and all UAVs are decentralized. The entire process is called leader election.
It is also notable that the voting mechanism will benefit the applications in an aquatic environment. Nowadays, two major types of vehicles have drawn immense attention in unmanned research community, Unmanned Underwater Vehicles (UUV) and Unmanned Surface Vehicles (USV), respectively [32
]. Various unmanned vehicles occasionally can be jointly called Unmanned Aerial and Aquatic Vehicles (UAAV) [33
]. Since the UAAV network shares vital common features, some efforts are made to investigate the feasibility of method transferring [33
]. In general, the acoustic communication is employed in the UUV, such as a sonar system, due to the absorption of radio signal under water [34
]. For the USV, two signal transportation media are available, acoustic modem underwater and wireless access through air [35
]. Apparently, the underlying network performance could be strictly limited, i.e., bandwidth, data rate, throughput, range, etc. To enable swarming of UUV and USV, distributed approaches are essential and indispensable for coordination and cooperation, where the voting-based method will play an active role. At the same time, the UAV may suffer a similar communication burden as in urban or rural situations [36
]. The communication capability is always affected by the energy consumption and swarm dynamic mobility. In addition, the excessively overlapped wireless coverage may cause potential resource usage conflicts, for instance frequency spectrum and bandwidth. The proposed voting algorithm can thus be useful and applicable in a UAV lead–follow swarm.
As for the election process, there are several important concerns. Firstly, since the original leader is down, all followers shall make the decision together to approve a leader in a fully decentralized mode. A negotiation rule should be made, such that a group of independent and autonomous drones could seek out the most suitable member acting as the leader role. Secondly, all followers are assumed to have a limited communication range and be able to reach local peers. Due to the locality of swarm, the only one who has a global connection to broadcast task instructions is the leader. This configuration is essential in practice, because the networking resource and energy of UAVs are constrained [37
]. It is also worth noting that the global connection describes the wide-area communication mode in which an alive leader is working. A practical implementation for a UAV is to program two working configurations, the leader and the follower, respectively. Only the leader will take charge of coordination and possess the key elements to relieve the interference and resource competing as aforementioned. For followers, each one would activate its limited abilities. Lastly, there ought to be an elastic metric to calculate to what extent a UAV can fit in the leader duty. That is how a UAV can recognize its local condition and quantify it to be comparable. It should also work in a UAV local computing component in an acceptable time period. A metric needs to be intentionally planned to strike a balance between the availability and computation pressure.
The leader election is illustrated in Figure 1. In the normal operation stage, each follower agent receives a periodical daemon (also named heartbeat) signal to remain in lead–follow behavior. If the leader fails to keep its functionality, an election process will be triggered among the rest of the followers. After a voting program in the swarm agents, an appropriate agent should be elected based on a unified measurement. Once the daemon/heartbeat signal has been rebroadcasted from the new leader, the lead–follow swarm behavior is then reformed automatically. It is noteworthy that daemon signal and granted votes ought to be transmitted through a communication channel. The communication condition, namely communication range/radius, is considered and implemented by a communication resource pool.
Figure 1. A visualization of leader-election process.
2. Lead-Follow UAV Swarm with Constrained Communication
During recent decades, unmanned aerial vehicles (UAVs) or the drones-enabled scheme have been drawing increasing attention. The common wisdom is that the drone-based scheme should be promising for solving various challenges, owing to characteristics such as flexibility, low-cost, adaptability, mobility and et al. [43
]. UAVs are indeed deployed for military purposes at the beginning [23
], while the civilians are also benefactors from their potential [45
]. Drones and UAVs are helpful in smart cities with urban IoT and edges [8
], such as enhancing communication [1
], reducing air pollution [5
], monitoring and managing traffic [3
] and building robust military forces [23
]. However, an single UAV unit is facing problems, for example, energy shortage, payloads restrictions, computation capacities and etc., [25
]. Multi-UAVs and UAV swarm techniques are developed to leverage the advantages of cooperation [46
Admittedly, swarming has advantages, and there should be interaction protocols for UAVs collaboration in swarm, owing to distribution and dispersion [47
]. Efforts have been made to settle the challenges, for example decentralization [48
] and hierarchical structure [49
]. However, decentralization may consume plenty of communication resources and require a specific control protocol [25
], which incurs implementation difficulty. A lead–follow formation has become a conventional and useful solution to a plenty of urban problems [22
The consensus idea initially comes from distributed computation [40
] in computer science, which principally targets fault tolerance in distributed networking environments [51
], a classic problem called the “Byzantine Generals” problem. One may trace consensus in distribution back to a harmony among data consistency, system availability and partition tolerance [52
]. The most recent explosion of Bitcoin leads to a research surge of consensus in blockchain [53
], which is expected to verify and ensure the data integrity. There has been well-known research motivating distributed machines to reach a consensus targeting the “Byzantine Generals” problem [39
]. Since the Paxos
] is braodly believed to be difficult to understand, the Raft
] is deliberately built to simplify the consensus procedure and strives to achieve a balance between performance and understandability. The Raft algorithm decompose the consensus into three subproblems: leader election, log replication and safety. Our proposal is accordingly inspired by the leader-election
stage and modified to fit in a UAV swarm scenario.
As for the consensus in a UAV swarm, it can be viewed as all UAV agents attempting to cooperatively reach agreement on issues in terms of task decision [41
]. Originally, the Boids/Reynolds model is proposed in [55
], followed by a series of works in dynamic multi-agent flocking controling and collectives consensus analysis [41
]. Similarly, the lead–follow swarm behavior is also considered with consensus [47
]. A distributed swarm system thus must effectively deal with orchestration, organization, interaction and so on [27
]. On the contrary, a lead–follow enabled swarm is a centralized swarm system and is unified by nature, because only one center is responsible for commanding discrete elements. This intrinsic feature thus gives the leader an indispensable role in several tasks [56
To find a proper agent to serve as the leader, some existing works focus on clustering collective units and determine a cluster head [31
]. Mou Zhiyu et al. [56
] investigate the hierarchical UAV swarm structure and employ a graph attention-based algorithm to detect clusters and the leaders. In [58
], an energy-aware node clustering algorithm is proposed in order to extend the lifetime in a wireless sensor network, which is based on particle swarm optimization with combined objects to optimize the utility. The method merely considers two energy-related factors and has difficulty fitting in highly dynamic applications. Ma Ting et al. [57
] introduce a modified k-means algorithm to select a super cluster head UAV agent with low latency, gaining an efficient swarm management. The authors in [31
] are dedicated to optimal drone communication and put forward a bio-inspired cluster head selection algorithm. They endeavour to divide the whole swarm into small groups and enable the algorithm locally based on residual energy and distance. These methods are specifically designed to meet trajectory and groundstation matching demands regardless of fault and disaster recovery for the swarm. Frequent changing cluster heads probably brings about the instability of swarm and extra communication overheads. Additionally, the mutual communication capacity has not been explicitly examined. In this work, we unfold several useful measurement designing principles and propose Raft-inspired low-cost voting scheme to make the collectives obtain a deterministic leader. Ultimately, the experiments illustrate advantages of the proposal over the original Raft algorithm.
The Raft algorithm is proposed for the consensus achievement in distributed computing. There are some relevant works dedicated to swarm clustering and head selection. These works prefer a well-designed measurement calculation to determine which one is capable of handling the cluster-head role, for instance, distance- and residual energy-related fitness values are designed in [31
The Leader Election Process
The leader election scheme in UAV swarm generally employs a similar process to that of the Raft algorithm in order to reach an agreement. At the beginning, a leader UAV (called a leader agent in simulation) can be appointed in a swarm based on the incoming tasks, preference of an operator, specific demands or randomly. After the startup, it is assumed that the UAV swarm turns to conduct predefined tasks in a lead–follow manner.
From the view of a leader, it is not only responsible for working coordination through communication, but also keeps daemon module alive and periodically broadcasts heartbeat signals to manage the whole swarm system. Whenever there exists an event making the swarm lose its leader, i.e., crashing or fatal malfunctioning, the leader-election process would take place subsequently.
From the perspective of followers, one may expect to receive the heartbeat signal to maintain the leader-follower relationship. A short-term waiting process with a countdown clock is setup in each follower to determine whether they are losing contact with the leader. When a heartbeat message is detected, the clock is reset for a new waiting time slot. Once the heartbeat signal is terminated and the waiting process finally ends with the clock timeout, a leader-election process will be instantly triggered to reform the lead–follow swarming manner. The scheme described above can be regarded as a state-transition process, commonly including the follower state, the candidate state and the terminal leader state if elected.
A comprehensive process diagram can be seen in Figure 2. UAV agents start from the Normal Running Loop and emerge as lead–follow swarming. After the leader crashes, the election process in each agent is then activated. Followers convert themselves into candidates which conduct a voting operation. In the voting operation, each individual calculates a qualification measure for itself and accordingly votes for the highest one becoming the new leader. Lastly, the lead–follow swarming has been reformed.
Figure 2. A comprehensive leader election process diagram.
This entry is adapted from 10.3390/electronics11142143