REDMAN proposes a simple broadcast-based strategy to detect the lengths of the shortest paths connecting the current IN
to the farthest participants in the dense MANET.
The current IN starts the protocol by broadcasting a farthest node determination message including a counter
initialized to 0. Every node receiving that message and belonging to the dense MANET increases
the counter and forwards the message, without re-sending an already sent message, similarly to the case
of dense MANET identification.
Figure 1 shows the message propagation from node I (the current IN) to all the nodes in the dense MANET.
In the figure, each node is marked with the value of its counter, i.e., its distance from I in number of hops.
For the sake of simplicity, the figure does not show all broadcast messages exchanged, but only those from
closer nodes to farther ones with regard to I.
Figure 1: The current IN (I) broadcasts exploratory messages for replica manager election
To limit bandwidth consumption, each node replies to the IN by communicating its distance if and only if it
cannot detect any node farther than itself at single-hop distance.
In fact, when a node receives a farthest node determination request, it starts a timeout;
at timeout expiration, it replies if it has not received any other broadcast from a node farther than
itself (with a greater counter). Let us rapidly observe that the choice of that timeout is simple because
it represents the time needed for single-hop neighbors to re-broadcast the message and does not depend
on the number of participants and on the dense MANET diameter (considerations about this issue can be found
here).
The nodes replying back to the farthest node determination message include not only the actual
farthest nodes for the current IN, but also other nodes situated at the boundaries of the dense region.
Figure 2 shows that not only H (the only farthest node) replies to I, but also E and M, which are
at the boundaries of the dense MANET. All other nodes, e.g., node A, do not reply because
they are prevented by single-hop neighbors placed at greater distance, e.g., nodes E, F, and D.
Every time the IN receives a reply message, it records the message source identity, its distance,
and the incoming direction, i.e., the neighbor that last for-warded the message.
Finally, the IN determines the identity of the farthest nodes, by excluding non-farthest nodes.
The IN assumes the distance of the determined farthest node(s) as its INvalue.
Figure 2: Only nodes at the dense MANET boundaries (E, F, and H) reply to the current IN I
