An Efficient Heuristic for the Minimum Connected Dominating Set Problem on Ad Hoc Wireless Networks

Authors: S. Balaji, N. Revathi

Abstract:

Connected dominating set (CDS) problem in unit disk graph has signi£cant impact on an ef£cient design of routing protocols in wireless sensor networks, where the searching space for a route is reduced to nodes in the set. A set is dominating if all the nodes in the system are either in the set or neighbors of nodes in the set. In this paper, a simple and ef£cient heuristic method is proposed for £nding a minimum connected dominating set (MCDS) in ad hoc wireless networks based on the new parameter support of vertices. With this parameter the proposed heuristic approach effectively £nds the MCDS of a graph. Extensive computational experiments show that the proposed approach outperforms the recently proposed heuristics found in the literature for the MCD

Keywords: ad hoc wireless networks, dominating sets, unit disk graphs, heuristic.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1058125

References:

[1] K. M. Alzoubi, P -J. Wan, O. Frieder: Distrbuted heuristics for connected dominating set in ad hoc wireless networks. IEEE ComSoc/KICS Journal on communication networks, 4(1) (2002) 22-29.
[2] D. Applegate, W. Cook, A. Rohe, Chained Lin-Kernighan for large traveling salesman problems, Informs Journal of Computing, 15(1) (2003) 82-92.
[3] B. S. Baker: Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM, 41(1), (1994) 153-180.
[4] S. Butenko, X. Cheng, D.-Z. Du, P. M. Pardalos: On the construction of virtual backbone for ad hoc wireless networks, In S. Butenko, R. Murphey and P. M. Pardalos, editors, Cooperative control: Models, Application and Algorithms, Kluwer Academic publishers, 43-54 (2004).
[5] S. Butenko, X. Cheng, C. A. S. Oliveira, P. M. Pardalos: A new heuristics for the minimum connected dominating set problem on ad hoc wireless networks, In S. Butenko, R. Murphey and P. M. Pardalos, editors, Recent developments in cooperative control and optimization, Kluwer Academic publishers, 61-73 (2004).
[6] S. Butenko, S. K-Anderoglu, O. Ursulenko: On connected domination in unit ball graphs, Optimization Letters, 5(2) (2011) 195-205.
[7] D. Chen, X. Mao, X. Fei, K. Xing, F. Liu, M. Song: A convex -hull based algorithm to connect the maximal independent set in unit disk graphs, Wireless algorithms: systems and applications (2006) 36-370.
[8] F. Dai, J. Wu: On constructing k-connected k-dominating set in wireless ad hoc and sensor networks, Journal of parallel and distributed computing, 66 (2006) 947-958.
[9] B. Das, V. Bharghavan: Routing in adhoc networks using minimum connected dominating sets. In International conference on communications, 376-380 (1997).
[10] T. S. Feo, M. G. C. Resende, S. H. Smith: A greedy randomized adaptive search procedure for maximum independent set, Operations Research, 42(5) (1994) 860-978.
[11] X. Gao, W. Wang, Z. Zhang, S. Zhu, W. Wu: A PTAS for minimum d-hop connected dominating set in growth bounded graphs, Optimization Letters, 4 (2010) 321-333.
[12] M. R. Garey, D. S. Johnson: Computers and Intractability: A Guide to the theory NP - completeness, San Francisco: Freeman (1979).
[13] S. Guha and S. Khuller: Approximation algorithms for connected dominating sets, Algorithmica, 20(4) (1998) 374-387.
[14] B. Han: Zone-based virtual backbone formation in wireless ad hoc networks, Ad Hoc Networks, 7 (2009) 183-200.
[15] T. W. Haynes, S. T. Hedetniemi, P. J. Slater: Fundamentals of domination in graphs, New Slater: Fundamentals of domination in graphs, New ork, Marcel Dekker Inc., (1998).
[16] K. Islam, S. G. Akl, H. Meijr: A constant factor localized algorithm for computing connected dominatng sets in wireless sensor networks, Proc. of the 14th IEEE international conference on parallel and distributed systems (2008).
[17] K. Katayama, H. Narihisa, Iterated local search approach using genetic transformation to the traveling salesman problem, Proceedings of the Genetic and Evolutionary Computation Conference, (1999) 321-328
[18] K. Katayama, A. Hamamoto, H. Nirihisa, An effective local search for the maximum clique problem, Information Processing Letters, 95 (2005) 503-511.
[19] B. W. Kernighan, S. Lin, An ef£cient heuristic procedure for partitioning graphs, Bell System Techn. J. 49 (1970) 291-307.
[20] Y. Li, S. Zhu, M. Thai, D. Du: Localized construction of connected dominating set in wireless networks, In Proc. YAWN (2004)
[21] S. Lin, B. W. Kernighan, An effective heuristic algorithm for traveling salesman problem, Oper. Res. 21 (1973) 498-516.
[22] G. Lu, M. T. Zhou, Y. Tang, M. Y. Zhao, X. Z. Niu, K. She: Approximation algorithms for the connected dominating set problem in unit disk graphs, Journal of electronic science and technology of china, 7(3) (2009) 214-222.
[23] M. V. Marathe, H. Breu, H. B. Hunt III, S. S. Ravi, D. J. Rosenkrantz: Simple heuristics for unit disk graphs, Networks, 25 (1995) 59-68.
[24] P. Merz, B. Freisleben, Fitness landscapes, memetic algorithms and greedy operators for graph partitioning, Evolutionary Computing, 8(1) (2000) 61-91.
[25] P. Merz, B. Freisleben, Memetic algorithms for the traveling salesman problem, Complex Systems, 13(4) (2001) 297-345.
[26] P. Merz, K. Katayama, Memetic algorithms for the unconstrained binary quadratic programming problem, Biosystems, 78(1-3) (2004) 99-118.
[27] R. Misra, C. Mandal: Minimum connected dominating set using a collaborative cover heuristic for ad hoc sensor networks, IEEE transactions on parallel and distributed systems, 21(3) (2010) 292-302.
[28] W. Pullan, Phased local search for the maximum clique problem, J. Comb. Optim. 12 (2006) 303-323.
[29] W. Pullan, Approximating the maximum vertex/edge weighted clique using local search, J. Heuristics, 14 (2008) 117-134.
[30] K. Sakai, S. C-H. Huang, W-S. Ku, M-T. Sun, X. Chang: Timer-based CDS construction in wireless Ad Hoc networks, IEEE Transactions on Mobile Computing, 10(10) (2011) 1388-1402.
[31] L. A. Sanchis: Experimental analysis of heuristic algorithms for the dominating set problem, Algorithmica, 33 (2002) 59-68.
[32] I. Stojmenovic, M. Seddigh, J. Zunic: Dominating sets and neighbor elimination based routing algorithms in wireless networks. IEEE Transaction Parallel distributed systems, 13(1) (2002) 14-25.
[33] P -J. Wan, K. M. Alzoubi, O. Frieder: Distributed construction of connected dominating set in ad hoc wireless networks. In Proc. INFOCOM (2002).
[34] W. Wu, X. Gao, P. M. Pardalos, D -Z. Du: Wireless networking, dominating and packing, Optimization Letters, 4 (2010) 347-358.
[35] J. Wu, H. Li: On calculating connected dominating set for ef£cient routing in ad hoc wireless networks, In proceedings of the 3rd ACM international workshop on Discrete Algorithms and methods for Mobile computing and communications, 7-14 (1999).
[36] M. Yaguira, T. Yamaguchi, T. Ibaraki, A variable depth search algorithm for the generalized assignment problem, in S. Voss, S. Martello, I. H. Osman, C. Roucairol(Eds.), Meta-Heuristics: Advance and Trends in Local Search Paradigms for Optimization, Kluwer, Dordrecht, (1999) 459-471.
[37] Y. Yang, M. Cardei: Adaptive energy ef£cient sensor scheduling for wireless sensor networks, Optimization Letters, 4 (2010) 359-369.
[38] J. Yu, N. Wang, G. Wang: Heuristic algorithms for constructing connected dominating sets with minimum size and bounded diameter in wireless networks, LNCS 6221 (2010) 11-20.
[39] W. Zhang, I. Shin, F. Zou, W. Wu, M. T. Thai: Construction of virtual backbone with multiple factors constraints in wireless ad-hoc network, Ad-Hoc and sensor wireless networks, 10(1) (2010) 27-59.