Cluster Overlay Broadcast (COB): MANET routing with complexity polynomial in source-destination distance

Luke Ritchie, Hyo Sik Yang, Andrea Richa, Martin Reisslein

Research output: Contribution to journalArticlepeer-review

32 Scopus citations


Routing algorithms with time and message complexities that are provably low and independent of the total number of nodes in the network are essential for the design and operation of very large scale wireless mobile ad hoc networks (MANETs). In this paper, we develop and analyze Cluster Overlay Broadcast (COB), a low-complexity routing algorithm for MANETs. COB runs on top of a one-hop cluster cover of the network, which can be created and maintained using, for instance, the Least Cluster Change (LCC) algorithm. We formally prove that the LCC algorithm maintains a cluster cover with a constant density of cluster leaders with minimal update cost. COB discovers routes by flooding (broadcasting) route requests through the network of cluster leaders with a doubling radius technique. Building on the constant density property of the network of cluster leaders, we formally prove that, if there exists a route from a source to a destination node with a minimum hop count of Δ, then COB discovers a route with at most O(Δ) hops from the source to the destination node in at most O(Δ) time and by sending at most O(Δ2) messages. We prove this result for arbitrary node distributions and mobility patterns and also show that COB adapts asymptotically optimally to the mobility of the nodes. In our simulation experiments, we examine the network layer performance of COB, compare it with Dynamic Source Routing, and investigate the impact of the MAC layer on COB routing.

Original languageEnglish (US)
Pages (from-to)653-666
Number of pages14
JournalIEEE Transactions on Mobile Computing
Issue number6
StatePublished - Jun 2006


  • Algorithm/protocol design and analysis
  • Message complexity
  • One-hop clustering
  • Routing protocol
  • Scalability
  • Time complexity
  • Wireless mobile ad hoc network

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Cluster Overlay Broadcast (COB): MANET routing with complexity polynomial in source-destination distance'. Together they form a unique fingerprint.

Cite this