Abstract
In wireless sensor networks, virtual backbone has been proposed as the routing infrastructure to alleviate the broadcasting storm problem and perform some other tasks such as area monitoring. Previous work in this area has mainly focused on how to set up a small virtual backbone for high efficiency, which is modelled as the minimum Connected Dominating Set (CDS) problem. In this paper we consider how to establish a small virtual backbone to balance efficiency and fault tolerance. This problem can be formalized as the minimum m-connected k-dominating set problem, which is a general version of minimum CDS problem with m = 1 and k = 1. In this paper we will propose some approximation algorithms for this problem that beat the current best performance ratios.
This work was supported in part by the Research Grants Council of Hong Kong under Grant No. CityU 1165/04E, the National Natural Science Foundation of China under Grant No. 70221001 and 10531070.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alzoubi, K.M., Wan, P.-J., Frieder, O.: Distributed heuristics for connected dominating sets in wireless ad hoc networks. Journal of Communications and Networks 4(1), 22–29 (2002)
Bredin, J.L., Demaine, E.D., Hajiaghayi, M., Rus, D.: Deploying sensor networks with guaranteed capacity and fault tolerance. In: Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), pp. 309–319. ACM Press, New York (2005)
Dai, F., Wu, J.: On constructing k-connected k-dominating set in wireless networks. In: IEEE International Parallel and Distributed Processing Symposium, IEEE Computer Society Press, Los Alamitos (2005)
Kuhn, F., Moscibroda, T., Wattenhofer, R.: Fault-Tolerant Clustering in Ad Hoc and Sensor Networks. In: Proceedings 26th International Conference on Distributed Computing Systems (ICDCS) (2006)
Koskinen, H., Karvo, J., Apilo, O.: On improving connectivity of static ad-hoc networks by adding nodes. In: Proceedings of the 4th annual Mediterranean Workshop on Ad Hoc Networks (Med-Hoc-Net), pp. 169–178 (2005)
Li, Y.S., Thai, M.T., Wang, F., Yi, C.-W., Wan, P.-J., Du, D.-Z.: On greedy construction of connected dominating sets in wireless networks. Wiley Journal on Wireless Communications and Mobile Computing 5(8), 927–932 (2005)
Shang, W.-P., Yao, F., Wan, P.-J., Hu, X.-D.: Algorithms for minimum m-connected k-tuple dominating set problem. Theoretical Computer Science (submitted)
Sinha, P., Sivakumar, R., Bharghavan, V.: Enhancing ad hoc routing with dynamic virtual infrastructures. In: Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 3, pp. 1763–1772 (2001)
Tarjan, R.: Depth first search and linear graph algorithms. SIAM Journal on Computing 1(2), 146–160 (1972)
Wan, P.-J., Alzoubi, K.M., Frieder, O.: Distributed construction of connected dominating set in wireless ad hoc networks. Mobile Networks and Applications 9(2), 141–149 (2004)
Wang, F., Thai, T.: On the construction of 2-connected virtual backbone in wireless networks. IEEE Transactions on Wireless Communications (to appear)
Wu, W., Du, H., Jia, X., Li, Y., Huang, C.-H.: Minimum connected dominating sets and maximal independent sets in unit disk graphs. Theoretical Computer Science 352(1), 1–7 (2006)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Shang, W., Yao, F., Wan, P., Hu, X. (2007). Algorithms for Minimum m-Connected k-Dominating Set Problem. In: Dress, A., Xu, Y., Zhu, B. (eds) Combinatorial Optimization and Applications. COCOA 2007. Lecture Notes in Computer Science, vol 4616. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73556-4_21
Download citation
DOI: https://doi.org/10.1007/978-3-540-73556-4_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73555-7
Online ISBN: 978-3-540-73556-4
eBook Packages: Computer ScienceComputer Science (R0)