Analysis on a localized pruning method for connected dominating sets

作者：Sum John^*; Wu Jie; Ho Kevin

来源：Journal of Information Science and Engineering, 2007, 23(4): 1073-1086.

• connected dominating set (CDS)
• expected size
• lower bound
• restricted pruning rule
• wireless mobile ad hoc network

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(N) x L(N) (where N and L(N) -> infinity); 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 (n) over cap. For (n) over cap >= 30. it is found that the expected size is close to N / (n) over cap. (3) It is proved that the lower bound on the expected size of a CDS for a Poissonian network of node density (n) over cap is given by {1/(n) over cap -1-(n) over cap/(n) over cap -1exp(-((n) over cap -1))}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 h is between 6 and 30. The data (expected CDS size) for this range can hardly be provided by simulations.

• 出版日期2007-7