Analysis on a Localized Pruning Method for Connected Dominating Sets
John Sum, Jie Wu, Kevin I.-J. Ho · Journal of information science and engineering · 2007
While restricted rule-k has been succeeded in generating a connected dominating set (CDS) of small size, not much theoretical analysis on the size has been done. In this paper, an analysis on the expected size of a CDS generated by such algorithm and its relation to different node density is presented. Assume N nodes are deployed uniformly and randomly in a square of size L(subscript N)×L(subscript N) (where N and L(subscript N)→∞∞); three results are obtained. (1) It is proved that the node degree distribution of such a network follows a Poisson distribution. (2) The expected size of a CDS that is derived by the restricted pruning rule-k is a decreasing function with respect to the node density (The Symbol is abbreviated). For (The Symbol is abbreviated)≥30. it is found that the expected size is close to N/(The Symbol is abbreviated). (3) It is proved that the lower bound on the expected size of a CDS for a Poissonian network of node density (The Symbol is abbreviated) is given by (The equation is abbreviated)N. The second result is of paramount importance for practitioners. It provides the information about the expected size of a CDS when the node density (The Symbol is abbreviated) is between 6 and 30. The data (expected CDS size) for this range can hardly be provided by simulations.