Improving construction for connected dominating set with Steiner tree in wireless sensor networks.

*(English)*Zbl 1103.90097Summary: The connected dominating set plays an important role in ad hoc wireless networking. Many constructions for approximating the minimum connected dominating set have been proposed in the literature. In this paper, we propose a new one with Steiner tree, which produces approximation solution within a factor of 6.8 from optimal. This approximation algorithm can also be implemented distributedly.

##### MSC:

90C35 | Programming involving graphs or networks |

90B10 | Deterministic network models in operations research |

PDF
BibTeX
XML
Cite

\textit{M. Min} et al., J. Glob. Optim. 35, No. 1, 111--119 (2006; Zbl 1103.90097)

Full Text:
DOI

##### References:

[1] | Alzoubi, K. M., Wan, P. -J., and Frieder, O. (2002) Message-optimal connected dominating sets in mobile ad hoc networks, Proceedings of the 3rd ACM International Symposium on Mobile ad hoc Networking and Computing, June 09–11, Lausanne, Switzerland. |

[2] | Bharghavan, V. and Das, B. Routing in ad hoc networks using minimum connected dominating sets, International Conference on Communication, Montreal, Canada, June 1997. |

[4] | Chen, Y. P. and Liestman, A. L. (2002), Approximating minimum size weakly connected dominating sets for clustering mobile ad hoc networks, Proceedings of the third ACM International Symposium on Mobile ad hoc Networking and Computing, June 09–11, Lausanne, Switzerland. |

[5] | Cadei, M., Cheng, M.X., Cheng, X. and Du, D.-Z. (2002), Connected domination in ad hoc wireless networks, Proceedings the Sixth International Conference on Computer Science and Informatics (CS& I’2002). |

[7] | Deering, S., Farinacci, D., Jacobson, V., Lui, C. and Wei, L. (1994), An Architecture for Wide Area Multicast Routing, Proceedings of ACM SIGCOMM 1994, September 1994. |

[8] | Du, D. -Z., Wang, L. and Xu, B. (2001), The Euclidean Bottleneck Steiner Tree and Steiner Tree with Minimum Number of Steiner Points, COCOON’ 2001, pp. 509–518 · Zbl 0991.68157 |

[9] | Eriksson, H. (1994), MBone: The Multicast Backbone, Communications of the ACM, August 1994. |

[11] | Lin G.-H. and Xue G.L. (1999) Steiner tree problem with minimum number of Steiner points and bounded edge-length. Information Processing Letters 69:53–57 · Zbl 1339.68209 |

[12] | Ramamurthy, B., Iness J. and Mukherjee, B. (1997), Minimizing the number of optical amplifiers needed to support a multi-wavelength optical LAN/MAN, Proceeding IEEE INFOCOM’97, pp. 261–268, April 1997. |

[14] | Salhieh, A., Weinmann, J., Kochha, M. and Schwiebert, L. (2001), Power Efficient topologies for wireless sensor networks, ICPP’2001, pp. 156–163. |

[15] | Sivakumar, R., Das, B. and Bharghavan, V. (1998), An improved spine-based infrastructure for routing in ad hoc networks, IEEE Symposium on Computer and Communications, Athens, Greece, June, 1998. |

[16] | Stojmenovic, I., Seddigh, M. and Zunic, J. (2001), Dominating sets and neighbor elimination based broadcasting algorithms in wireless networks, Proceeding IEEE Hawaii International Conference on System Sciences, January 2001. |

[17] | Wan, P.-J., Alzoubi, K.M. and Frieder, O. (2002), Distributed construction of connected dominating set in wireless ad hoc networks, Proceedings of Infocom’2002. |

[18] | Wu J. and Li, H.L. (1991), On calculating connected dominating set for efficient routing in ad hoc wireless networks, Proceedings of the 3rd ACM International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 7–14. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.