Delay Preserving Substructures in Wireless Networks Using Edge Difference between a Graph and its Square Graph

Authors: T. N. Janakiraman, J. Janet Lourds Rani

Abstract:

In practice, wireless networks has the property that the signal strength attenuates with respect to the distance from the base station, it could be better if the nodes at two hop away are considered for better quality of service. In this paper, we propose a procedure to identify delay preserving substructures for a given wireless ad-hoc network using a new graph operation G 2 – E (G) = G* (Edge difference of square graph of a given graph and the original graph). This operation helps to analyze some induced substructures, which preserve delay in communication among them. This operation G* on a given graph will induce a graph, in which 1- hop neighbors of any node are at 2-hop distance in the original network. In this paper, we also identify some delay preserving substructures in G*, which are (i) set of all nodes, which are mutually at 2-hop distance in G that will form a clique in G*, (ii) set of nodes which forms an odd cycle C2k+1 in G, will form an odd cycle in G* and the set of nodes which form a even cycle C2k in G that will form two disjoint companion cycles ( of same parity odd/even) of length k in G*, (iii) every path of length 2k+1 or 2k in G will induce two disjoint paths of length k in G*, and (iv) set of nodes in G*, which induces a maximal connected sub graph with radius 1 (which identifies a substructure with radius equal 2 and diameter at most 4 in G). The above delay preserving sub structures will behave as good clusters in the original network.

Keywords: Clique, cycles, delay preserving substructures, maximal connected sub graph.

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

References:

[1] M.R. Garey, D.S.Johnson, "Computers and Intractability, Freeman, San Francisco, 1978.
[2] T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds), Fundamentals of Domination in Graphs, Marcel Dekker, Inc.,1998.
[3] Baker, D., Ephremides, A., "The Architectural Organization of a Mobile Radio Network via a Distributed Algorithm, Communications", IEEE Transactions, vol.29-11, (1981), pp.1694-1701..
[4] Gerla, M, Tsai, J.T., "Multicluster, mobile, multimedia radio network, Wireless Networks", vol.1 (3), (1995), pp.255-265.
[5] Chen, G., Nocetti, F.G., Gonzalez, J.S., Stojmenovic, I., "Connectivity based k-hop clustering in wireless networks", System Sciences, HICSS, Proceedings of the 35th Annual Hawaii International Conference, (2002), 2450-2459.
[6] Han, B.,Jia, W., "Efficient Construction of Weakly-Connected Dominating Set for Clustering Wireless Ad Hoc Networks", IEEE Globecom, (2006), pp. 1-5.
[7] Han, B., Jia, W., "Clustering Wireless Ad Hoc Networks with weakly- Connected Dominating Set", Journal of Parallel and Distributed Computing, vol. 67(6), (2007), pp.727-737.
[8] Alzoubi, K.M., Wan, P.J., Frieder, O. ".Maximal Independent Set, Weakly Connected Dominating set, and Induced Spanners for Mobile Ad hoc Networks", International Journal of Foundations of Computer Science, vol.14(2), 92003), pp.287-303.
[9] Stojmenovic, I., Seddigh, M., Zunic, J., "Dominating Sets and neighbor elimination-based broadcasting algorithms in wireless networks", IEEE Transactions on Parallel and Distributed Systems, (2002), pp. 14-125.
[10] Ghua, S., Khuller, S.,"Approximation Algorithms for Connected dominating Sets", Springer-Verlag New York, (1998), LLC, ISSN:178- 4617.
[11] M.Chateerjee, S.K.Das, and D.Turgut, "An On-Demand Weighted Clustering Algorithm (WCA) for Ad Hoc Networks", in Proceedings IEEE Globecom, 00, 2000, pp.1697-1701.
[12] F.Dai, J.Wu, "On Constructing k-connected k-dominating set in wireless networks", Proceedings of the IEEE IPDPS, 2005.
[13] Z.Shi, P.K.Srimani, "A new adaptive distributed routing protocol using d-hop dominating sets for mobile ad hoc networks", Proceedings of the international Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA), 2004.
[14] T.N. Janakiraman, J.Janet Lourds Rani, "An Efficient Clustering for Wireless Ad Hoc Networks Using Ranking", Proceedings of IEEE conference, ICCIMA 2007.
[15] T.N. Janakiraman, J.Janet Lourds Rani, " An Efficient Clustering for wireless ad hoc networks using weighted paired domination", International Journal of Information and Communication Technology, vol.1.(3).
[16] Gallagher, R.G., Humblet, P.A., Spira, P.M.A, "Distributed Algorithm for Minimum-Weight Spanning Trees", ACM Transactions on Programming Languages and Systems (1983), pp. 66-77.
[17] Gentile, C., Haerri, J., Vandyck, R.E., "Kinetic minimum-power routing and clustering in mobile ad hoc networks", Proc.Vehicular Tech Conf., (2002).
[18] Ya-feng, w., Yin-long, X., Guo-liang, C., Kun, W., "On the construction of virtual multicast backbone for wireless ad hoc networks", MASS 04,(2004), pp.25-27.
[19] Chen, Y.P., Liestman, A.L., "a zonal algorithm for clustering ad hoc networks", International Journal of Foundations of Computer Science, vol.14 (2), (2003), pp.305-322.
[20] Y.P.Chen, A.L.Liestman, J.Liu, Ad hoc and Sensor Networks, Nova Science Publisher, 2004 (Chapter: Clustering algorithms for ad hoc wireless networks).