A simulation-based performance evaluation of a randomized MIS-based clustering algorithm for ad hoc networks

Ad-hoc networks represent distributed systems that comprise wireless nodes which can dynamically self-organize into arbitrary and temporary network topologies, without relying on pre-existing infrastructure, and thus network hierarchy formation via clustering is vital for them. The present article conducts a comprehensive simulation-based evaluation of the performance achieved by a recently proposed, biology-inspired, clustering algorithm used in wireless ad hoc networks, namely the Randomized Beep Based Maximum Independent Set (RanMIS)(RanMIS) (Afek et al., 2011). This is the first evaluation done for this high-performance algorithm. The evaluation is done for a set of metrics (measures for protocol cost, backbone description and robustness) some of which has not been used in earlier simulation studies and are developed here. Our study confirms the virtues (message complexity) and reveals the shortcomings of RanMISRanMIS (latency issues), and quantifies the impact of some of its administratively-tuned parameters. RanMISRanMIS is compared with two representative graph-theoretic node clustering methods and a new one developed here; the results confirm the message optimality of RanMISRanMIS, but reveal some shortcomings of it, basically related to the excessive number of rounds that needs to run in order to complete the network clustering.