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

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

Authors:

• S. Balaji
• N. Revathi

Keywords:

• ad hoc wireless networks
• dominating sets
• unit disk graphs
• heuristic.

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.