Download Bachelor`s Thesis

Transcript
4 Algorithm Outline
4.2 Phase 2: Seed Election
During the execution, a robot can have two different roles, either the one of a seed or
that of a non-seed. In the beginning, no robot is assign to a role. A seed robot’s task is
to construct a local coordinate system. To ensure that enough of these local coordinate
systems are distributed amongst the swarm, every non-seed robot must eventually see at
least two seeds. Similarly, every seed must see at least one other seed.
To elect the seed robots, two protocols are executed, one for the so called top seed
election and one for the bottom seed election. Starting with the top seed election, every
robot sends its ID to its neighbours. Whenever a robot receives a value greater than its
own ID, it does not become a seed. If none of the messages contain a greater ID, the robot
becomes a top seed. The remaining non-seeds continue with the bottom seed election
protocol. The idea is the same as before: Every non-seed broadcasts its ID and becomes
a seed if no message is received that indicates that a neighbour is assigned a greater ID.
Once a robot becomes a seed, it starts to announce its new role. In the end of the bottom
seed election protocol, every robot checks whether it is able to see enough seeds. If this
is not the case, it broadcasts a message, inducing a new bottom seed election with its
neighbours.
This procedure is repeated, until every robot sees at least two, respectively every seed at
least one other seed robot. The roles of the top and bottom seeds are identical, and they
are not distinguished any more in the phases below.
Figure 4.1: Possible excerpt of a collective. Red: seed robots with respective communication ranges.
12