Distributed connected dominating set election from uniform random to power law network graphs

摘要

This work describes an analysis of applying different election heuristics to connected dominated set (CDS) algorithms within different topological graph taxonomies. Our initial motivation for this study was a general observation that a significant amount of research in mobile ad hoc network (manet) algorithm design and related election heuristic evaluation is based upon geometric random or other types of uniform random network models. Our hypothesis is that small world or scale-free network topology analysis can result in significantly different design feedback that may be suppressed by exclusive use of uniform random analysis. Previous research has shown that power law based networks more accurately represent types of real world and social networks and we believe it is important to understand the potential tradeoffs in distributed algorithm design for self-organizing networks beyond traditional random network models. We provide a concrete example by applying the existing specification for the essential-CDS algorithm used within the mobile ad hoc network (manet) Simplified Multicast Forwarding (SMF) and the OSPF Extensions for MANET MDR approach. We model random, small world, and power law based network types based upon well known models. We demonstrate that the network graph taxonomy used in modeling affects the design analysis such as understanding the resulting effectiveness of various distributed election heuristics. Future work is planned to extend these initial results to more dynamic analysis.