Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Minimum CDS in Multihop Wireless Networks with Disparate Communication Ranges
verfasst von : Lixin Wang, Peng-Jun Wan, Frances Yao
Erschienen in: Wireless Algorithms, Systems, and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Connected dominating set (CDS) has a wide range of applications in mutihop wireless networks. The Minimum CDS problem has been studied extensively in mutihop wireless networks with uniform communication ranges. However, in practice the nodes may have different communication ranges either because of the heterogeneity of the nodes, or due to interference mitigation, or due to a chosen range assignment for energy conservation. In this paper, we present a greedy approximation algorithm for computing a Minimum CDS in multihop wireless networks with disparate communications ranges and prove that its approximation ratio is better than the best one known in the literature. Our analysis utilizes a tighter relation between the independence number and the connected domination number.