Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19] [ 20] [ 21]

@

Journal of Information Science and Engineering, Vol. 23 No. 4, pp. 1073-1086 (July 2007)

Analysis on a Localized Pruning Method for Connected Dominating Sets

John Sum, Jie Wu and Kevin Ho
1Department of Information Management
Chung-Shan Medical University
Taichung, 402 Taiwan
E-mail: pfsum@csmu.edu.tw
2Department of Computer Science and Engineering
Florida Atlantic University
Boca Raton, Florida 33431, U.S.A.
E-mail: jie@cse.fau.edu
3Department of Computer Science and Communication Engineering
Providence University
Taichung, 433 Taiwan
E-mail: ho@pu.edu.tw

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

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

Full Text () Retrieve PDF document (200707_08.pdf)

Received September 15, 2006; accepted February 6, 2007.
Communicated by Ten H. Lai, Chung-Ta King and Jehn-Ruey Jiang.