Dense MANET Configuration
DMC

The DMC facility is in charge of determining the participants of the dense MANET DM(n), i.e., the subset of nodes that have more than n nodes at single-hop distance. In addition, DMC identifies when nodes enter/exit the dense MANET, and triggers the dynamic election of the replica manager node, by minimizing the number of hops required for its messages to reach any dense MANET participant. These functions are crucial for the realization of all other REDMAN facilities and require original solutions that fit the specific characteristics of the dense MANET deployment scenario.

Identification of Dense MANET Participants
REDMAN proposes an original solution to dynamically determine the nodes that currently participate in a dense MANET. The primary idea is not to maintain a centralized, global, and always up-to-date vision of all the nodes and of their network topology, but to design a simple, lightweight, and completely decentralized protocol where any node autonomously determines whether it belongs to the dense MANET. One node is in the dense MANET DM(n) only if the number of its neighbors, i.e., the nodes at single-hop distance, is greater than n. Each node autonomously discovers the number of its neighbors by exploiting simple single-hop broadcast discovery messages.
More in detail, at any time one REDMAN node can start the process of dense MANET identification/update; in the following, we will call that node the initiator. The initiator starts the protocol by broadcasting a discovery message that includes the number of neighbors required to belong to the dense region. When receiving this message, each node willing to participate replies by forwarding the message to its single-hop neighbors (after a Discovery Delay used to avoid collisions), if it has not already sent that message. After a specified time interval (called Participant Advertisement Interval), any node autonomously checks whether the number of received discovery messages is greater than the specified number of neighbors to belong to the dense region, and autonomously decides whether it belongs to the dense MANET. Let us observe that discovery broadcasts could provoke packet collisions ( broadcast storm issue): to avoid this problem, any REDMAN node defers node broadcasts of a random time interval. Notwithstanding this introduced random delay, the time needed to complete the dense MANET identification protocol is limited and largely acceptable; in fact, it shows a linear dependence on the diameter of the dense region, not on the number of its participants.

Figure 1: Node I (the inititator) broadcasts a discovery message.	Figure 2: Upon receiving the broadcast, node B forwards the discovery message to its single-hop neighbors.

Figure 3: Node A repeats the process.

Since dense MANET nodes can move after the identification process, the proposed algorithm includes a lightweight lazy-consistent maintenance phase. Nodes periodically (every Hello Period) exchange Hello packets; each node receiving a Hello message records its source in a table entry, with an associated timeout; next Hellos received from the same source restart a new timeout. Dense MANET nodes periodically (every Check Hello Period) check whether their table entries are still valid; if an entry has expired, the node removes it from the table, and verifies whether the condition to belong to the dense MANET still holds. Decentralized Election of the Replica Manager
REDMAN proposes an original, lightweight, and decentralized protocol to elect the replica manager. To reduce the communication overhead (both in terms of dissipated energy and elapsed time) for the manager to get in touch with all dense MANET participants, it could be useful to choose a node located in a topologically central position. More precisely, REDMAN aims at electing one node that minimizes the number of hops required to reach its farthest nodes belonging to the dense MANET. In addition, the proposed protocol for replica manager election has not the goal of finding the optimal solution with regards to the above minimization criterion: REDMAN exploits some heuristics to relevantly limit the election overhead while achieving a good quality manager designation. The proposed solution explores, as replica manager candidates, only a subset of nodes in the dense MANET, called Investigated Nodes (INs).
To avoid the overhead of an exhaustive search, REDMAN adopts an exploration strategy that limits the number of INs, by only choosing successive INs in order to get closer to the dense MANET topology center at each exploration step, thus decreasing the distance of each successive IN from farthest participants, as better detailed in the following.
Therefore, a primary issue is how INs can autonomously determine the direction towards the dense MANET topology center by exclusively exploiting information about MANET farthest nodes. To this purpose, the adopted guideline is to explore the nodes located along the direction of farthest nodes from previously considered INs. In fact, by moving toward that direction, each protocol step considers an IN that is placed one-hop closer to the previously identified farthest nodes; therefore, the IN distance from farthest nodes tends to decrease and to converge close to the best solution.

Figure 4: REDMAN explores the sequence of INs: I → A → D

Figure 4 shows an example of application of that guideline. The first step of the protocol considers node I: its farthest node is H, located at 4-hop dis-tance; so, I is tagged with the value of that distance (I4 in the figure). Then, the REDMAN manager election protocol considers A because it is the first node along the path from I to H: A's farthest node is H, at 3-hop distance (A3). At the next iteration, the protocol explores node D and elects it as the replica manager; in fact, D can reach any other node in the dense MANET with a maximum of two hops.
After having informally introduced the above main guidelines of the protocol, let us now better detail how the manager election works. The protocol considers the initiator as the first IN; then, it reiterates the farthest node determination process to evaluate other promising nodes, until it reaches a satisfying solution. Each IN executes three operations:

• i) it determines the number of hops of the shortest paths connecting it to any farthest node in the dense MANET (the maximum of those hop numbers is called INvalue);
• ii) it identifies its neighbors located in the direction of its farthest nodes (forwarding neighbors);
• iii) it autonomously chooses the next IN among all the unexplored forwarding neighbors of already explored minimum-valued INs.

The manager election protocol ends when either the REDMAN heuristic criterion determines there are no more promising nodes, or the current INvalue = Min-Int((worst explored INvalue)/2), where MinInt(x) returns the least integer greater than x . Since REDMAN considers bidirectional links among MANET nodes, when the above equation is verified, it is easy to demonstrate that REDMAN has reached the optimal solution for the manager election.
Pseudo-code