Meritocracy in the Swarm, How to Elect the Leader in a Homogeneous Swarm

In my earlier article- Monarchy in the Swarm, I tried to answer the question, how to convert individual drones into a swarm.

author avatar

04 Jul, 2019

Meritocracy in the Swarm, How to Elect the Leader in a Homogeneous Swarm

In my earlier article- Monarchy in the Swarm, I tried to answer the question, how to convert individual drones into a swarm. When there is a special drone that is developed especially for leading drone swarms, the problem is easier to solve. The leader starts discovery algorithm, and recursively, whole swarm is discovered. I highly suggest reading that article since I will not repeat myself in this article with basic knowledge given there.

A predetermined leader drone poses the single point of failure problem. If the leader drone malfunctions, the swarm will be mindless at that point and ineffective, if there are no countermeasures for such scenario. One solution would be adding redundant leader drones into the mix that are constantly monitoring the active leader’s health and taking the leader role whenever the active leader fails. But this is also not the final solution, the leader drones are the Achilles’ heel for the drone swarms.

But, what if every drone has the capability of leading swarm? That would be the final solution to our problem. The drone swarm would heal its control structure whenever the leader drone can not lead anymore. New elections are quickly held, and the swarm continues to its mission without significant delay or loss in capability.

Who Should be the Leader?

Like real life, a leader must be the most capable one to lead in the population. But what would be the parameters for such capability? This question would require whole another article to answer. But for simplicity, let’s assume there are two important metrics that signify leadership capability;

  • High number of connections: A leader drone must be in the center of the swarm, not necessarily geographic center but communication center. A leader must be able to transmit to and receive from as many as drones possible so we can create a balanced communication structure.
  • Long Lifetime: Wireless communication is an expensive process. And the leader elections require too many transmissions, thus they are a burden on the swarm. Therefore, we should go for a solution that requires minimum number of reelections. Long lifetime can be directly indicated by remaning energy in the battery. A leader with higher lifetime guarantees eliminating the chance of certain reelection so soon. You do not want to elect a leader with high number of connections but has 2 minutes of energy in its battery.

How can a Drone Find Its Number of Connections?

We identified our parameters of leadership. Each drone can estimate its own remaining life. But how can it know how many drones it can communicate with. Let’s assume each drone keeps a connection list that stores a ID numbers of drones in its communication range.

For this, each drone should repeatedly broadcast its unique ID and nothing else with random periods. Broadcasts should be really short since our wireless medium is shared by all drones and transmissions happening at the same time may cause interference. Repeated broadcasts with random periods are necessary to reduce the chance of two drones interfering with each other at each repeated transmission. Of course this repetition count should be picked carefully since ee do not want too long broadcast process. Swarm’s size and distance between drones are the deciding factors for interference probability.

Whenever a drone receives broadcast of other drones, it should update its connection list with received ID, if it is not added already before. This way, each drone can fill its connection list before elections.

Connection List of a Drone(Representative) 

Time Has Come to Elect the Leader

At this moment, each drone has its connection list(and number of connections) and its own remaining lifetime. Formula below will be used to calculate leadership value(LV) of the drones. Each drone should calculate its LV before starting elections.

LV = NumberOfConnections x RemainingBatteryPercentage

For elections, we will use repeated broadcasts with random periods to cover as much of the swarm as possible. Each drone will broadcast its ID and its LV. Any receiving drone will compare the received LV with its own LV. If the received LV is higher, receiving drone will broadcast received ID and received LV-rebroadcasting. If the receiving drone has higher LV, it will broadcast its own ID and LV to its connection list. This process should continue until all drones in the swarm globally agree on the highest LV drone’s leadership.

Repetition count is important here. We want to make sure each drone in the swarm has the same information about leader’s identity. Each drone might have to broadcast more than once if it hears broadcast about another leader, which is better leader than it has. This algorithm might be modified to prevent excess broadcasts.This way, eventually all the drones will know the leader drone in the swarm.

Example with a Small Swarm

At the start, our topology looks like this;

Drones and Their Communication Range 

Each drone, its communication boundaries and line to those boundaries are the same color. Assuming each drone has the same battery level, we can see that C is the best candidate to lead. Repeated-randomized broadcasts are also ignored for this example. We will accept only one drone transmits at any time for simplicity, there is no interference. Let’s see how our algorithm works.

  1. Remaining battery levels are: A-80%, B-100%, C-70%, D-%90, E-%100.
  2. At first, each drone broadcasts its ID to the drones in its communication range.
  3. Drones who receive these broadcasts update their connection lists.
  4. A has 2, B has 1, C has 3, D has 2 and E has 2 connections in their connection list.
  5. Each drone calculates its LV by the formula : LV = NumberOfConnections x RemainingBatteryPercentage . Results are A-160, B-100, C-210, D-180, E-200.
  6. Let’s assume E is the first drone to broadcast.
  7. E broadcasts its ID and and LV(200).
  8. D receives this broadcast, sees that E is better leader than itself(LV-180). Therefore D rebroadcasts E’s ID and LV(200).
  9. C receives both E’s original broadcast and D’s rebroadcast of E. In either case, C sees its LV(210) is higher than E’s LV(200). C broadcasts its own ID and LV(210).
  10. E and D receives C’s broadcast. They both see C is better leader than them and assume C’s leadership at that moment.
  11. A receives C’s broadcast. A sees its LV(160) is lower than C’s LV(210). A rebroadcasts C’s ID and LV(210). A assumes C’s leadership.
  12. B receives both C’s original broadcast and A’s rebroadcast of C. In both cases, B sees its LV(100) is lower than C’s LV(210). B assumes C’s leadership.
  13. All the nodes, in the end, knows C is the leader of the pack.

We assumed minimum amount of broadcasts that lead us to elect the most capable leader.

After the Elections

At this point, each drone in the swarm knows who is the leader. After this point, all we have to do form a swarm with techniques given in my first article-Monarchy in the Swarm.

Elections should be repeated when necessary, since we know every drone can fail or its battery runs out. There might be many tweaks to this given algorithm to reduce number of elections in a swarm. but that should be another article’s topic.

Conclusion

Autonomous drone swarms has its specific problems. They rely on communicating with each other,if the aim is operating as swarm instead of individual drones. They are vulnerable to targeted or area jamming, control loss due to leader malfunction. The leader of the swarm should not be seen dictator that sets actions of each swarm member also, it is just a coordinator that manages the swarm. Swarm members has their own mission data and plan.

A robust swarm should easily adapt to control loss and recover in such cases. Like insect swarm, a drone swarm who lost its leader or great portion of its members should continue its mission after recovery.

04 Jul, 2019

After graduating from Mersin High School of Science, I attended to Hacettepe University Computer Engineering program. In June 2015, I graduated as honorary student with 3.14 GPA. During my education , I enjoyed concepts of Embedded Systems, and Computer Networks. In my spare time, I developed proje... learn more

Stay Informed, Be Inspired

Wevolver’s free newsletter delivers the highlights of our award winning articles weekly to your inbox.