Abstract
Finding the Minimum-size Connected Dominating Set (MCDS), i.e., the communication backbone with the minimum number of nodes is a key problem in wireless networks, which is crucial for designing efficient routing algorithms and for network energy efficiency etc. This paper proposes a new greedy algorithm to approach the MCDS problem. The key idea is to separate nodes in CDS into core nodes and supporting nodes. The core nodes dominate the supporting nodes in CDS, while the supporting nodes dominate other nodes that are not in CDS. The proposed algorithm is verified by simulation, the simulation results show that the CDS constructed by our algorithm has smaller size than the state of the art algorithms in [10].
This work was supported in part by the National Natural Science Foundation of China Grant Nos. 11671400, 61672524; the Fundamental Research Funds for the Central University, and the Research Funds of Renmin University of China, 2015030273.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Blum, J., Ding, M., Cheng, X.: Applications of connected dominating sets in wireless networks. Handb. Comb. Optim. 42, 329–369 (2004)
Ephremides, A., Wieselthier, J.E., Baker, D.J.: A design concept for reliable mobile radio networks with frequency hopping signaling. Proc. IEEE 75(1), 56–73 (1987)
Misra, R., Mandal, C.: Ant-aggregation: ant colony algorithm for optimal data aggregation in wireless sensor networks. In: 2006 IFIP International Conference on Wireless and Optical Communications Networks, p. 5. IEEE (2006)
He, Z., Cai, Z., Cheng, S., Wang, X.: Approximate aggregation for tracking quantiles and range countings in wireless sensor networks. Theoret. Comput. Sci. 607, 381–390 (2015)
Cheng, S., Cai, Z., Li, J., Fang, X.: Drawing dominant dataset from big sensory data in wireless sensor networks. In: IEEE INFOCOM, pp. 531–539 (2015)
Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Ann. Discret. Math. 48, 165–177 (1991)
Wan, P.J., Alzoubi, K.M., Frieder, O.: Distributed construction of connected dominating set in wireless ad hoc networks. In: IEEE INFOCOM, vol. 3, pp. 1597–1604 (2002)
Wan, P.J., Wang, L., Yao, F.: Two-phased approximation algorithms for minimum CDS in wireless ad hoc networks. In: 2008 The 28th International Conference on Distributed Computing Systems, ICDCS 2008, pp. 337–344. IEEE (2008)
Misra, R., Mandal, C.: Minimum connected dominating set using a collaborative cover heuristic for ad hoc sensor networks. Parallel Distrib. Syst. 21(3), 292–302 (2010)
Al-Nabhan, N., Zhang, B., Cheng, X., Al-Rodhaan, M., Al-Dhelaan, A.: Three connected dominating set algorithms for wireless sensor networks. Int. J. Sens. Netw. 21(1), 53–66 (2016)
Shi, T., Cheng, S., Cai, Z., Li, J.: Adaptive connected dominating set discovering algorithm in energy-harvest sensor networks. In: IEEE INFOCOM, pp. 1–9 (2016)
Shi, T., Cheng, S., Cai, Z., Li, Y., Li, J.: Exploring connected dominating sets in energy harvest networks. IEEE/ACM Trans. Netw. (2017). doi:10.1109/TNET.2017.2657688
Shi, T., Cheng, S., Li, J., Cai, Z.: Constructing connected dominating sets in battery-free networks. In: The 36th Annual IEEE International Conference on Computer Communications INFOCOM (2017)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Luo, C., Wang, Y., Yu, J., Chen, W., Li, D. (2017). A New Greedy Algorithm for Constructing the Minimum Size Connected Dominating Sets in Wireless Networks. In: Ma, L., Khreishah, A., Zhang, Y., Yan, M. (eds) Wireless Algorithms, Systems, and Applications. WASA 2017. Lecture Notes in Computer Science(), vol 10251. Springer, Cham. https://doi.org/10.1007/978-3-319-60033-8_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-60033-8_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-60032-1
Online ISBN: 978-3-319-60033-8
eBook Packages: Computer ScienceComputer Science (R0)