Minimum CDS in multihop wireless networks with disparate communication ranges
Research output: Conference Papers › RGC 32 - Refereed conference paper (without host publication) › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages | 47-56 |
| Publication status | Published - 15 Aug 2010 |
Conference
| Title | 5th International Conference on Wireless Algorithms, Systems, and Applications (WASA 2010) |
|---|---|
| Place | China |
| City | Beijing |
| Period | 15 - 17 August 2010 |
Link(s)
Abstract
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.
Citation Format(s)
Minimum CDS in multihop wireless networks with disparate communication ranges. / Wang, L.; Wan, P.-J.; Yao, F.
2010. 47-56 Paper presented at 5th International Conference on Wireless Algorithms, Systems, and Applications (WASA 2010), Beijing, China.
2010. 47-56 Paper presented at 5th International Conference on Wireless Algorithms, Systems, and Applications (WASA 2010), Beijing, China.
Research output: Conference Papers › RGC 32 - Refereed conference paper (without host publication) › peer-review
