K-clustering in wireless ad hoc networks

ABSTRACT

Ad hoc networks consist of wireless hosts that communicate with each other in the absence of a fixed infrastructure. Clustering is commonly used in order to limit the amount of routing information stored and maintained at individual hosts. A k-clustering is a framework in which the wireless network is divided into non-overlapping sub networks, also referred to as clusters, and where every two wireless hosts in a sub network are at most k hops from each other. The algorithmic complexity of k-clustering is known to be NP-Complete for simple undirected graphs. For the special family of graphs that represent ad hoc wireless networks, modeled as unit disk graphs, we introduce a two phase distributed polynomial time and message complexity approximation solution with O(k) worst case ratio over the optimal solution. The first phase constructs a spanning tree of the network and the second phase then partitions the spanning tree into subtrees with bounded diameters.

REFERENCES

• 1: Nesrine Abbas , Lorna Stewart, Clustering bipartite and chordal graphs: complexity, sequential and parallel algorithm, Discrete Applied Mathematics, v.91 n.1-3, p.1-23, Jan. 26, 1999 [doi>10.1016/S0166-218X(98)00094-8]
• 2: K. Alzoubi , P.-J. Wan , O. Frieder, New Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc Networks, Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS'02)-Volume 9, p.297, January 07-10, 2002
• 3: Alan D. Amis , Ravi Prakash, Load-Balancing Clusters in Wireless Ad Hoc Networks, Proceedings of the 3rd IEEE Symposium on Application-Specific Systems and Software Engineering Technology (ASSET'00), p.25, March 24-25, 2000
• 4: A. Amis, R. Prakash, T. Vuong, and D. Huynh. Max-min d-cluster formation in wireless ad hoc networks. In Proceedings of IEEE INFOCOM, pages 32--41, March 1999.
• 5: D. Baker and A. Ephremides. The architectural organization of a mobile radio network via a distributed algorithm. IEEE Transactions on Communication, pages 1694--1701, November 1981.
• 6: Yuanzhu Peter Chen , Arthur L. Liestman, Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513821]
• 7: Brent N. Clark , Charles J. Colbourn , David S. Johnson, Unit disk graphs, Discrete Mathematics, v.86 n.1-3, p.165-177, Dec. 14, 1990 [doi>10.1016/0012-365X(90)90358-O]
• 8: Jitender S. Deogun , Dieter Kratsch , George Steiner, An approximation algorithm for clustering graphs with dominating diametral path, Information Processing Letters, v.61 n.3, p.121-127, Feb. 1997 [doi>10.1016/S0020-0190(97)81663-8]
• 9: A. Farley, S. Hedetniemi, and A. Proskurowski. Partitioning trees: matching, domination, and maximum diameter. International Journal Computing Information Science, 10(1):55--61, February 1981.
• 10: R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
• 11: T. Gonzalez. Clustering to minimize the maximum inter-cluster distance. Theoretical Computer Science, NorthHolland, 38:293--306, 1985.
• 12: P. Krishna , N. H. Vaidya , M. Chatterjee , D. K. Pradhan, A cluster-based approach for routing in dynamic networks, ACM SIGCOMM Computer Communication Review, v.27 n.2, p.49-64, Apr. 1997 [doi>10.1145/263876.263885]
• 13: C.-H. Lin and M. Gerla. A distributed control scheme in multi-hop packet radio networks for voice/data traffic support. In Proceeding of IEEE GLOBECOM, pages 1238--1242, 1995.
• 14: M. V. Marathe, H. Breu, H. B. Hunt III, S. S. Ravi, and D. J. Rosenkrantz. Simple heuristics for unit disk graphs. Networks, 25:59--68, 1995.
• 15: A. McDonald and T. Znati. A mobility-based framework for adaptive clustering in ad hoc networks. IEEE Journal on Selected Areas in communications, 17(8):1466--1487, August 1999.
• 16: A. K. Parekh. Selecting routers in ad-hoc wireless networks. In Proceeding ITS, 1994.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms

Keywords:
competitive ratio, connected dominating set, distributed algorithm, k-clustering, wireless ad hoc networks