Clustering overhead for hierarchical routing in mobile ad hoc networks

John Sucec, Ivan Marsic

Research output: Contribution to journalConference articlepeer-review

75 Scopus citations


Numerous clustering algorithms have been proposed that can support routing in mobile ad hoc networks (MANETs). However, there is very little formal analysis that considers the communication overhead incurred by these procedures. Further, there is no published investigation of the overhead associated with the recursive application of clustering algorithms to support hierarchical routing. This paper provides a theoretical upper bound on the communication overhead incurred by a particular clustering algorithm for hierarchical routing in MANETs. It is demonstrated that, given reasonable assumptions, the average clustering overhead generated per node per second is only polylogarithmic in the node count. To derive this result, novel techniques to assess cluster maintenance overhead are employed.

Original languageEnglish (US)
Pages (from-to)1698-1706
Number of pages9
JournalProceedings - IEEE INFOCOM
StatePublished - 2002
EventIEEE Infocom 2002 - New York, NY, United States
Duration: Jun 23 2002Jun 27 2002

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Electrical and Electronic Engineering


  • Hierarchical routing
  • Mobile ad hoc network


Dive into the research topics of 'Clustering overhead for hierarchical routing in mobile ad hoc networks'. Together they form a unique fingerprint.

Cite this