A Mobility-Resistant Efficient Clustering Approach for ad hoc and sensor networks

ABSTRACT

This paper presents a Mobility-Resistant, Efficient Clustering Approach (MRECA) for ad hoc and sensor networks. MRECA can provide robustness against moderate node mobility and at the same time render energy-eficiency. The identified clusterheads cover the whole network and each node in the network can determine its cluster and only one cluster. The algorithm terminates in deterministic time without iterations, and each node transmits only one message during the algorithm. We prove analytically the correctness and complexity of the algorithm, and simulation results demonstrate that MRECA is energy-efficient, resilient against node mobility, and robust against synchronization errors

REFERENCES

• 1: I. F. Akyildiz , W. Su , Y. Sankarasubramaniam , E. Cayirci, Wireless sensor networks: a survey, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.4, p.393-422, 15 March 2002 [doi>10.1016/S1389-1286(01)00302-4 ]
• 2: Stefano Basagni, Distributed Clustering for Ad Hoc Networks, Proceedings of the 1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99), p.310, June 23-25, 1999
• 3: S. Basagni, D. Turgut, and S. K. Das, "Mobility-adaptive protocols for managing large ad hoc networks," in Proc. of the IEEE International Conference on Communications, 2001.
• 4: S. Basagni, M. Mastrogiovanni, and C. Petrioli, "A performance comparion of protocols for clustering and backbone formation in large scale ad hoc networks," in Proc. Int'l conference on Mobile Ad Hoc and Sensor Systems, 2004.
• 5: H. Chan and A. Perrig, " ACE: An Emergent Algorithm for Highly Uniform Cluster Formation", in Proc. of the First European Workshop on Sensor Networks(EWSN), January 2004.
• 6: 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 ]
• 7: Fei Dai , Jie Wu, An Extended Localized Algorithm for Connected Dominating Set Formation in Ad Hoc Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.15 n.10, p.908-920, October 2004 [doi>10.1109/TPDS.2004.48]
• 8: Jeremy Elson , Lewis Girod , Deborah Estrin, Fine-grained network time synchronization using reference broadcasts, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060304]
• 9: F. Garcia Nocetti, J. Solano Gonzales, and I. Stojmenovic, "Connectivity based k-hop clustering in wireless networks," TelecommunicationSystems, vol. 22, no. 1-4, pp. 205--220, 2003.
• 10: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 11: U. C. Kozat, G. Kondylis, B. Ryu, and M. K. Marina, "Virtual dynamic backbone for mobile ad hoc networks," in Proc. of the IEEE International Conference on Communications (2001).
• 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: J. H. Li, M. Yu, and R. Levy, "Distributed Efficient Clustering Approach for Ad Hoc and Sensor Networks" in Proc International Conference on Mobile Ad hoc and Sensor Networks, 2005.
• 14: C. R. Lin and M. Gerla, "Adaptive clustering for mobile wireless networks," Journal on Selected Areas in Communications, vol. 15, no. 7, pp. 1265--1275, September 1997.
• 15: A. B. McDonald and T. Znati, "A mobility-based framework for adaptive clustering in wireless ad hoc networks," IEEE Journal on Selected Areas in Communications, vol. 17, no. 8, pp. 1466--1487, August 1999.
• 16: The Clade Vertebrata: Spines and Routing in Ad Hoc Networks, Proceedings of the Third IEEE Symposium on Computers & Communications, p.599, June 30-July 02, 1998
• 17: Raghupathy Sivakumar , Bevan Das , Vaduvur Bharghavan, Spine routing in ad hoc networks, Cluster Computing, v.1 n.2, p.237-248, 1998 [doi>10.1023/A:1019045801829 ]
• 18: R. Sivakumar, P. Sinha, and V. Bharghavan, "CEDAR: A core-extraction distributed ad hoc routing algorithm," IEEE Journal on Selected Areasin Communications, vol. 17, no. 8, pp. 1454--1465, 1999.
• 19: Ivan Stojmenovic , Mahtab Seddigh , Jovisa Zunic, Dominating Sets and Neighbor Elimination-Based Broadcasting Algorithms in Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.13 n.1, p.14-25, January 2002 [doi>10.1109/71.980024 ]
• 20: J. Wu and H. Li, "On calculating connected dominating sets for efficient routing in ad hoc wireless networks," Telecommunication Systems, vol. 18, no. 113, pp. 13--36, September 2001.
• 21: J. Wu, F. Dai, M. Gao, and I. Stojmenovic," On calculating poweraware connected dominating sets for efficient routing in ad hoc wireless networks," Journal of Communications and Networks, vol. 4, no. 1, pp. 1--12, March 2002.
• 22: Ossama Younis , Sonia Fahmy, HEED: A Hybrid, Energy-Efficient, Distributed Clustering Approach for Ad Hoc Sensor Networks, IEEE Transactions on Mobile Computing, v.3 n.4, p.366-379, October 2004 [doi>10.1109/TMC.2004.41]

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
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols
      C.2.6 Internetworking

General Terms:
Algorithms, Design, Performance