International Journal of Information Technology and Computer Science (IJITCS)
IJITCS Vol. 4, No. 2, 8 Mar. 2012
Cover page and Table of Contents: PDF (size: 119KB)
Algorithmic Aspects for Total Connected Dominating Sets in Mobile Ad Hoc Wireless Networks
Full Text (PDF, 119KB), PP.34-40
Views: 0 Downloads: 0
Author(s)
Index Terms
Total Connected Dominating Set, Independent Set, ad hoc networks, connected dominating set, maximal independent set, mobility
Abstract
A Total connected dominating set (TCDS) for a graph G(V,E) is a subset V'of V , such that each node in V−V' is adjacent to some node in V' and V' induces a connected subgraph.
A TCDS has been proposed as a virtual backbone for routing in wireless ad hoc networks. However, it is NP-hard to find a minimum connected dominating set (MCDS). Approximation algorithms for MCDS have been proposed in the literature. Most of these algorithms suffer from a very poor approximation ratio, and from high time complexity and message complexity. Recently, new distributed heuristics for constructing a TCDS were developed, with constant approximation ratio of 8. These new heuristics are based on a construction of a spanning tree, which makes it very costly in terms of communication overhead to maintain the TCDS in the case of mobility and topology changes.
Investigating the algorithmic complexity of total domination for wireless ad hoc network as relevant open question .An O(n^2) algorithm has been proposed for this problem by Bertossi [1].Keil [10] proposed an O(n+m)
In this paper, we propose the first distributed approximation algorithm to construct a MCDS for the unit-disk-graph with a constant approximation ratio O(n), and linear time and linear message complexity. This algorithm is fully localized, and does not depend on the spanning tree. Thus, the maintenance of the TCDS after changes of topology guarantees the maintenance of the same approximation ratio. In this algorithm each node requires knowledge of its single hop neighbors, and only a constant number of two-hop and three-hop neighbors.
Cite This Paper
C.D.Guruprakash, B.P.Mallikarjunaswamy, "Algorithmic aspects for total connected dominating sets in Mobile Ad Hoc Wireless Networks", International Journal of Information Technology and Computer Science(IJITCS), vol.4, no.2, pp.34-40, 2012. DOI:10.5815/ijitcs.2012.02.05
Reference
[1]B. Clack, C. Colbourn, and D. Johnson, ”Unit Disk Graphs,”Discrete Mathematics, vol. 86, pp. 165–177, 1990.
[2]P.-J. Wan, K. M. Alzoubi, and O. Frieder, ”Distributed Construction on Connected Dominating Set in Wireless Ad Hoc Networks”,Proceedings of the Conference of the IEEE Communications Society (INFOCOM), 2002.
[3]Y. Li, M. T. Thai, F. Wang, C.-W. Yi, P.-J. Wang, and D.-Z.Du, ”On Greedy Construction of Connected Dominating Sets in Wireless Networks”, Special issue of Wireless Communications and Mobile Computing (WCMC), 2005.
[4]S. Funke, A. Kesselman, U. Meyer, and M. Segal,”A Simple Improved Distributed Algorithm for Minimum CDS in Unit Disk Graphs”, 1st IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), 2005.
[5]M. Cardei, M.X. Cheng, X. Cheng, and D.-Z. Du, ”Connected Domination in Ad Hoc Wireless Networks”, Proceedings of the Sixth International Conference on Computer Science and Informatics (CSI), 2002.
[6]S. Guha and S. Khuller, ”Approximation Algorithms for Connected Dominating Sets”, Algorithmica, vol. 20, pp. 374–387,1998.
[7]L. Ruan, H. Du, X. Jia, W. Wu, Y. Li, and L.-I. Ko, ”A Greedy Approximation for Minimum Connected Dominating Sets”, Theoretical Computer Science, 2005.
[8]J. Wu and H. Li, ”On Calculating Connected Dominating Sets for Efficient Routing in Ad Hoc Wireless Networks”, Proceedings of the Third International Workshop Discrete Algorithms and Methods for Mobile Computing and Comm., 1999.
[9]Y. Li, S. Zhu, M. T. Thai, and D.-Z. Du, ”Localized Construction of Connected Dominating Set in Wireless Networks”, NSF International Workshop on Thoretical Aspects of Wireless Ad Hoc, Sensor and Peer-to-Peer Networks, 2004.
[10]T.W.Haynes and P.J.Slater “Paired Domination in Graphs Networks,32(1998),199-206.
[11]T.W.Haynes and P.J.Slater “Paired Domination and paired dominating number,2091995),65-72.
[12]K.M. Alzoubi, P.-J. Wang, and O. Frieder, ”Message-Optimal Connected Dominating Sets in Mobile Ad Hoc Networks”, Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), 2002.
[13]B. Das, R. Sivakumar, and V. Bharghavan, ”Routing in Ad Hoc Networks Using a Spine”, International Conferfence on Computers and Communication Networks, 1997.
[14]B. Das and V. Bharghavan, ”Routing in Ad Hoc Networks Using Minimum Connected Dominating Sets”, International Conference on Communications, 1997.
[15]R. Sivakumar, B. Das, and V. Bharghavan, ”An Improved Spinebased Infrastructure for Routing in Ad Hoc Networks”, IEEE Symposium on Computers and Communications, 1998.
[16]M. R. Garey, D. S. Johnson, ”Computers and Intractability. A guide to the Theory of NP-completeness”, Freeman, New York, 1979.
[17]K.M. Alzoubi, P.-J. Wan, and O. Frieder, ”New Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc Networks”, Proceedings of the 35th Hawaii International Conference on System Scicences, Hawaii, 2002.
[18]K.M. Alzoubi, P.-J. Wan, and O. Frieder, ”Distributed Heuristics for Connected Dominating Sets in Wireless Ad Hoc Networks”, Journal of Communications and Networks, vol. 4, no. 1, March 2002.
[19]H. Breu and D.G. Kirkpatrick. Unit disk graph recognition is NP-hard. Computational Geometry. Theory and Applications, 9(1-2):3–24, 1998.
[20]T.M. Chan. Polynomial-time approximation schemes for packing and piercing fat objects. Journal of Algorithms, 46(2):178–189, 2003.
[21]X. Cheng, X. Huang, D. Li, W. Wu, and D.-Z. Du. A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks, 42:202–208,2003.
[22]B. N. Clark, C. J. Colburn, and D. S. Johnson. Unit disks graphs. Discrete Mathematics,86:165–177, 1990.
[23]I.Cidon and O. Mokryn, ”Propagation and Leader Election in Multihop Broadcast Environment”, The 12th International Sysposium on distributed Computing (DISC), 1998.
[24]I.J. Dejter and O. Serra, E_cient dominating sets in Cayley graphs",Discrete Applied Mathematics, Vol.129, (2003), pp.319-328.
[25]T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, (2000).
[26]Jia Huang and Jun-Ming Xu, The bondage numbers and efficient dominations of vertex-transitive graphs", Discrete Mathematics, Vol.308,(2008), pp.571-582.
[27]S. Lakshmivarahan and S.K. Dhall, Ring, torus and hypercube architectures/ algorithms for parallel computing", Parallel Computing, Vol.25,(1999), pp.1877-1906.
[28]J. Lee, Independent perfect domination sets in Cayley graphs", Journal of Graph Theory, Vol.37, No.4, (2001), pp.213-219.
[29]N. Obradovi_c, J. Peters and Goran Ru_zi_c, E_cient domination in circulant graphs with two chord lengths", Information Processing Letters,Vol.102, (2007), pp.253-258.
[30]T. Tamizh Chelvam and I. Rani, Dominating sets in Cayley Graphs on Zn", Tamkang Journal of Mathematics, Vol.38, No.4, (2007), pp.341-345.
[31]T. Tamizh Chelvam and I. Rani, Independent domination number of Cayley graphs on Zn", The Journal of Combinatorial Mathematics and Combinatorial Computing, Vol.69, (2009), pp.251-255.
[32]T.Tamizh Chelvam and I.Rani, Total and Connected domination numbers for Cayley graphs on Zn", Advanced Studies in Contemporary Mathematics, Vol.20, (2010), pp.57-61.