Clustering algorithms for wireless ad hoc networks

ABSTRACT

Efficient clustering algorithms play a very important role in the fast connection establishment of ad hoc networks. In this paper, we describe a communication model that is derived directly from that of Bluetooth, an emerging technology for pervasive computing; this technology is expected to play a major role in future personal area network applications. We further propose two new distributed algorithms for clustering in wireless ad hoc networks. The existing algorithms often become infeasible because they use models where the discovering devices broadcast their Ids and exchange substantial information in the initial stages of the algorithm. We propose a 2-stage distributed O(N) randomized algorithm for an N node complete network, that always finds the minimum number of star-shaped clusters, which have maximum size. We then present a completely deterministic O(N) distributed algorithm for the same model, which achieves the same purpose. We describe in detail how these algorithms can be applied to Bluetooth for efficient scatternet formation. Finally, we evaluate both algorithms using simulation experiments based on the Bluetooth communication model, and compare their performance.

REFERENCES

• 1: http://www, bluetooth, com.
• 2: http://www, bluetooth, net.
• 3: Hosame H. Abu-Amara, Fault-Tolerant Distributed Algorithm for Election in Complete Networks, IEEE Transactions on Computers, v.37 n.4, p.449-453, April 1988 [doi>10.1109/12.2189]
• 4: Hosame Abu-Amara , Arkady Kanevsky, On the Complexities of the Leader Election Algorithms, Proceedings of the Fifth International Conference on Computing and Information, p.202-206, May 27-29, 1993
• 5: H. Abu-Amara , J. Lokre, Election in Asynchronous Complete Networks with Intermittent Link Failures, IEEE Transactions on Computers, v.43 n.7, p.778-788, July 1994 [doi>10.1109/12.293257]
• 6: A. D. Amis, R. Prakash, T. H. P. Vuong, and D. T. Huynh. Max-rain D-cluster formation in wireless ad hoc networks, in INFOCOM, 2000.
• 7: H. Chernoff. A measure of asymptotic efficiency for tests of a hyi)othesis l)ased on sums of observations. Ann. Math Statistist, 23:493-507.
• 8: V. Chvatal. A greedy heuristic for the set-covering problem. In Mathematics of Operations Research, pages 233-235, 1979.
• 9: Bevan Das , Raghupathy Sivakumar , Vaduvur Bharghavan, Routing in Ad Hoc Networks Using a Spine, Proceedings of the 6th International Conference on Computer Communications and Networks, p.34, September 22-25, 1997
• 10: R. Dechter and L. Kleinrock. Broadcast communication and distributed algorithms, iEEE Trans. Computers, pages 210-219, 1986.
• 11: Rong-chii Duh , Martin Fürer, Approximation of k-set cover by semi-local optimization, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.256-264, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258599]
• 12: G. S. Fishman. Monte Carlo, Concepts, Algorithms and Applications. Springer-Verlag, 1996.
• 13: Mario Gerla , Jack Tzu-Chieh Tsai, Multicluster, mobile, multimedia radio network, Wireless Networks, v.1 n.3, p.255-265, 1995 [doi>10.1007/BF01200845]
• 14: Tatsuya Hayashi , Koji Nakano , Stephan Olariu, Randomized Initialization Protocols for Packet Radio Networks, Proceedings of the 13th International Symposium on Parallel Processing and the 10th Symposium on Parallel and Distributed Processing, p.544, April 12-16, 1999
• 15: W. Hoeffding. Probability inequalities for sums of bounded random variables. J. Amer. Statist Assoc, 58:13-29, 1963.
• 16: A. Itah and M. Rodeh. The lord of the ring, or probabilistic methods for breaking symmetry in distributed networks. Technical Report RJ 3110, IBM, Yorktown Heights, N.Y, 1981.
• 17: Madhukar R. Korupolu , C. Greg Plaxton , Rajmohan Rajaraman, Analysis of a local search heuristic for facility location problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.1-10, January 25-27, 1998, San Francisco, California, United States
• 18: A. Mizutani, T. Aihara, S. Shimotono, and H. Ishikawa. Bluetooth scatternet. Technical Report RT5176, IBM Tokyo Research Lab, 1999.
• 19: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 20: C. V. Ramamoorthy, J. Srivatsava, and W. T. Tsai. Clustering techniques for large distributed systems. In INFOCOM, 1986.
• 21: T. Salonidis, P. Bhagwat, and L. Tassiulas. Proximity awareness and fast connection setup in Bluetooth. Submitted for publication.
• 22: David B. Shmoys , Éva Tardos , Karen Aardal, Approximation algorithms for facility location problems (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.265-274, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258600]
• 23: Gurdip Singh, Leader election in complete networks, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.179-190, August 10-12, 1992, Vancouver, British Columbia, Canada [doi>10.1145/135419.135457]
• 24: Jie Wu , Hailan Li, On calculating connected dominating set for efficient routing in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.7-14, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313261]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization

  G. Mathematics of Computing

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory, Verification