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

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.

Authors:

• T. N. Janakiraman
• J. Janet Lourds Rani

Keywords:

• Clique
• cycles
• delay preserving substructures
• maximal connected sub graph.

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).