Connectivity-based clustering with stretching technique in MANETs

ABSTRACT

In this paper, we propose a multi-hop stretching clustering scheme for MANETs. As the solution of k-hop minimum dominating set, our proposed scheme aims to reduce the number of cluster-heads which are responsible for maintaining the cluster backbone. By considering the intra connectivity, nodes with low communication reliability can join better clusters for better communication quality. We also prove the relationship between intra-connectivity and the remaining staying time of one node in its current cluster. Based on that, the intra-connection degree is taken into account when one mobile node chooses cluster candidates for joining. Next, we apply a stretching technique in clustering to decrease the leaving frequency of cluster-members. Finally, extensive performance evaluation verifies our results under different system settings.

REFERENCES

• 1: P. Guptar, and P. R. Kumar, "The capacity of Wireless Networks," IEEE Transaction Information Theory, Volume 46, Issue 2, March 2000, pp. 417--427.
• 2: J. Y. Yu, and P. H. J. Chong, "A survey of Clustering schemes for Mobile Ad hoc Networks," IEEE Communication Surveys and Tutorials, Volume 7, Issue 1, 2005, pp. 32--48.
• 3: M. Abolhasan, T. Wysocki, and E. Dutkiewicz, "A review of Routing Protocols for Mobile Ad hoc Networks," Ad Hoc Networks, Volume 2, Number 1, January 2004, pp. 1--22.
• 4: M. Joa-Ng, and I. T. Lu, "A Peer-to-Peer Zone-based Two-level Link State Routing for Mobile Ad hoc Networks," IEEE Journal on Selected Areas in Communications, Volume 17, Issue 8, August 1999, pp. 1415--1425.
• 5: S. Leng, L. Zhang, H. Fu, and J. Yang, "A Novel Location Service Protocol Based on $k$-hop Clustering for Mobile Ad hoc Networks," IEEE Transactions on Vehicular Technology, Volume 56, March 2007, pp. 810--817.
• 6: C. R. Lin, and M. Gerla, "Adaptive Clustering for Mobile Wireless Networks," IEEE Journal on Selected Areas in Communication, Volume 15, Issue 7, September 1997, pp. 1265--1275.
• 7: F. G. Nocetti and J. S. Gonzalez, "Connectivity Based $k$-hop clustering in Wireless Networks," Telecommunication System, Volume 22, 2003, pp. 205--220.
• 8: A. D. Amis, R. Prakash, T. H. P Vuong, and D. T. Huynh, "Max-min d-cluster formation in wireless ad hoc networks," Proc. IEEE INFOCOM, 2000, pp. 32--41.
• 9: Matthias R. Brust , Hannes Frey , Steffen Rothkugel, Dynamic multi-hop clustering for mobile hybrid wireless networks, Proceedings of the 2nd international conference on Ubiquitous information management and communication, January 31-February 01, 2008, Suwon, Korea [doi>10.1145/1352793.1352820]
• 10: C. C. Chiang, H. K. Wu and W. Liu, "Routing in Clustered Multi-hop, Mobile Wireless Networks with Fading Channel," Proceedings of IEEE SICON, 1997, pp. 197--211.
• 11: T. J. Kwon, M. Gerla, V. K. Varma, M. Barton and T. R. Hsing, "Efficient flooding with Passive Clustering-an overhead-free selective forward mechanism for Ad hoc/Sensor Networks," Proceedings of the IEEE, Volume 91, August 2003, pp. 1210--1220.
• 12: Chien-Chung Shen , Chavalit Srisathapornphat , Rui Liu , Zhuochuan Huang , Chaiporn Jaikaeo , Errol L. Lloyd, CLTC: A Cluster-Based Topology Control Framework for Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.3 n.1, p.18-32, January 2004 [doi>10.1109/TMC.2004.1261814]
• 13: Kishor S. Trivedi, Probability and statistics with reliability, queuing and computer science applications, John Wiley and Sons Ltd., Chichester, UK, 2001

INDEX TERMS

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

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

General Terms:
Design, Performance

Keywords:
k-hop dominating set, ad hoc networks, mobility, multi-hop clustering, stability, stretching clustering