Design and Analysis of Distributed Tree Growing Algorithms

Tree-based systems rely on real-time dissemination trees to deliver information to nodes. In order to offer good services, two fundamental aspects should guide the real-time growth process: low node degree and short distances to the server. In this paper, we propose a growth process to construct trees and make a detailed study on modeling and performance analysis of these tree-based systems. Our generative mechanism is based on the preferential attachment principle, where preference is given in terms of node quality. The proposed growth mechanism has a single parameter to weigh the relative importance of node degree and node distance on assessing node quality. We aim at understanding this mechanism when considering the local aspect of the node’s degree and the global aspect of the distance to a source. With this goal, we investigate our model through simulations and compare it to other growth processes. Our results indicate that the proposed model is capable of self-organizing nodes into good trees under six metrics of interest.