The goal is to compare the performance of both versions of the CEL algorithm, with Gómez-Calzado et al. algorithm [Góm+13], using different transmission ranges on both mobility patterns. Note that the number of components in the system is strongly correlated with the transmission range.
The following three metrics have been considered: average number of messages sent per second per node, average of the median path to the leader and instability.
Similarly as in Section 4.4.1.0, this metric does not consider beacon messages, since the same number of beacons is sent every τ milliseconds by the underlying data-link layer in all three algorithms. In both CEL versions, beacon messages are used at the MAC layer by the cross-layer mechanism.
Compared to the metric in Section 4.4.1.0, this metric characterizes how fast a leader can be reached by a majority of nodes (at least 50%) in its component. First is computed the longest path of all shortest paths from every node to their current leader, except for single node components, as its null path would unfairly improve the metric. Then, the average of all medians over time is computed. Note that this metric is expressed in number of hops, and is not a ratio between the longest leader path and the component diameter as in Section 4.4.1.0.
This metric is the same as the one defined in Section 4.4.1.0. The oracle is based on the closeness centrality for CEL, and on the oldest node of the connected component with the highest identifier for Gómez-Calzado et al. algorithm.
Average number of messages sent per second is shown in Figures 5.4 and 5.5 for both mobility patterns. Right y-axes give the average number of components and their average diameter. In the Gómez-Calzado algorithm, nodes periodically send join messages when they are alone, in order to connect with a bigger component.
On both mobility models, CEL-1 sends more messages than CEL-0.7, as it floods the network by broadcasting every received knowledge message. CEL-0.7 reduces the number of messages sent per second, especially in larger transmission ranges, where more messages are broadcast at each topological change. There is an average reduction of 36% when ρ is set to 0.7 compared to ρ sets to 1, on both mobility patterns for a transmission range from 20m to 80m.
Note that the average message sent size varies from 4.56 to 6.58 bytes in the Gómez-Calzado algorithm, and from 263.03 to 1322.69 bytes for both versions of the CEL algorithm, as they share the topological knowledge of the component, and fits into the MTU of a single network packet.
Average of the median path to the leader is shown in Figures 5.6 and 5.7 for both mobility patterns. Figure 5.6 shows that the average of the median path from every nodes of the components to the leader, is shorter in CEL than in Gómez-Calzado algorithm for the Random Walk mobility model, with a gain of up to 26% in larger transmission ranges. Interestingly, the probabilistic gossip version of CEL has a low impact on the leader path. These results are interesting, because the median represents half of the component nodes, which is the size of a quorum in Paxos-type consensus algorithms.
The Truncated Lévy Walk pattern shows in Figure 5.7 the impact of flying nodes which disrupt the component, by quickly moving in and out, therefore, modifying potential paths to the leader. Therefore, the difference between the CEL algorithm with ρ sets to 0.7 and the Gómez-Calzado algorithm, leads to a shortest path up to 15%.
Sharing a topological knowledge like in the CEL algorithm, allows the election of a central leader per component. Consequently, the results confirm that the number of hops to reach the leader by the nodes of its component is reduced.
Instability evolution is shown in Figures 5.8 and 5.9, according to the transmission range, and for both patterns. It is observed that the average instability increases when the transmission range increases, since components are composed of more nodes with a larger diameter. Hence, it takes a longer time to elect a new leader for all the algorithms.
In Figure 5.8, the percentage of instability in Gómez-Calzado algorithm is on average 69% higher than on both CEL versions. There is no significant instability difference between the CEL versions.
The instability for the Truncated Lévy Walk pattern in Figure 5.9, shows that the CEL algorithm is more stable than Gómez-Calzado algorithm when the transmission range increases. On average, CEL versions are 57% more stable than Gómez-Calzado algorithm. It can also be observed that the probabilistic gossip version of CEL with ρ sets to 0.7, is slightly less stable than the flooding version with ρ sets to 1. This is induced by a lower number of broadcast messages, making disrupting changes caused by flying nodes, to take more time to be spread over large components diameter.
Focusing on the 60 meters range over time is interesting to understand in detail the differences between the algorithms behaviors, on an approximate range of usual Wi-Fi indoor devices. Figures 5.10 and 5.11 show the average instability from time 0 to time t for both mobility patterns. The right y-axis gives the exact number of components at time t.
In Figure 5.10, at the beginning of the experiment on the Random Walk pattern, Gómez-Calzado algorithm has a higher instability rate, which quickly decreases to reach a threshold of 50% at 240 seconds, with a slight increase over time. Both CEL algorithm versions need a few seconds to stabilize, before reaching a threshold of around 430 seconds. The probabilistic gossip version (CEL-0.7) is less stable than the flooding version, as some knowledge messages are not broadcast by nodes to their neighborhood.
Figure 5.11 shows that the Truncated Lévy Walk model increases the instability of Gómez-Calzado algorithm, where an instability threshold of 59% is reached after 416 seconds. On the other hand, both CEL versions have a common instability evolution over time, with a small difference at the end of the experiment following the rebroadcast probability.
A comparative analysis with the Topology Aware algorithm presented in Chapter 4 shows the performance gain by both the neighbor-aware and self-pruning mechanisms which exploit the topological knowledge, and by the probabilistic gossip.
The Topology Aware algorithm elects a central leader, but assumes reliable communication channels, which are not suitable for realistic environments with message interference and collisions. A global view of the network is exchanged using probes and an update mechanism, leading to message collisions and losses. Furthermore, the knowledge of the topology is not used to improve communication performance, and the bidirectional links assumption is not taken into account to optimize knowledge sharing.
| Topology Aware | CEL-1 | CEL-0.7 | |
| Messages sent | 53.32/s | 24.91/s | 14.97/s |
| Leader path (in hop) | 2.44 | 2.20 | 2.24 |
| Instability | 21.75% | 12.15% | 19.04% |
| Topology Aware | CEL-1 | CEL-0.7 | |
| Messages sent | 84.06/s | 52.35/s | 30.74/s |
| Leader path (in hop) | 3.50 | 3.14 | 2.96 |
| Instability | 54.53% | 45.92% | 62.36% |
Experiments ran in the realistic OMNeT++ environment described in Section 5.3, with a probe frequency τ = 102.4ms for Topology Aware. The analysis is focused on a Wi-Fi transmission range of 80 meters, as it is the highest range of the experiments and a complex configuration with large components diameters.
Results for the Random Walk mobility pattern in Table 5.1, show that exploiting the topological knowledge reduces the number of messages sent per second by 71.92% comparing the Topology Aware algorithm to CEL-0.7, while having a shorter leader path. Instability is 44.14% lower comparing Topology Aware to CEL-1.
For the Truncated Levy Walk pattern in Table 5.2, the comparison between Topology Aware and CEL-0.7 shows a reduction of the number of messages sent per second by 63.43%, and an average median leader path lower by 15.43%. Note that while the instability percentage is lower for CEL-1, the reduction of the number of messages by the probabilistic gossip version (CEL-0.7) may lead to lower stability than Topology Aware, especially when high transmission ranges imply large components.
