Fast clustering and minimum weight matching algorithms for very large mobile backbone wireless networks

A. Ferro, G. Pigola, A. Pulvirenti, D. Shasha

Research output: Contribution to journalArticlepeer-review


Mobile Backbone Wireless Networks (MBWN) [10] are wireless networks in which the base stations are mobile. Our strategy is the following: mobile nodes are dynamically grouped into clusters of bounded radius. In the very large wireless networks we deal with we deal with, several hundreds of clusters may be generated. Clustering makes use of a two dimensional Euclidean version of the Antipole Tree data structure [5]. This very effective structure was originally designed for finite sets of points in an arbitrary metric space to support efficient range searching. It requires only a linear number of pair-wise distance calculations among nodes. Mobile Base Stations occupy an approximate centroid of the clusters and are moved according to a fast practical bipartite matching algorithm which tries to minimize both total and maximum distance. We show that the best known computational geometry algorithms [1] become infeasible for our application when a high number of mobile base stations is required. On the other hand our proposed 8% average error solution requires O(k log k) running time instead of the approximatively O(k2) exact algorithm [1]. Communication among nodes is realized by a Clusterhead Gateway Switching Routing (CGSR) protocol [15] where the mobile base stations are organized in a suitable network. Other efficient clustering algorithms [11, 17] may be used instead of the Antipole Tree. However the nice hierarchical structure of the Antipole Tree makes it applicable to other types of mobile wireless (Ad-Hoc) and wired networks but this will be subject of future work.

Original languageEnglish (US)
Pages (from-to)223-236
Number of pages14
JournalInternational Journal of Foundations of Computer Science
Issue number2
StatePublished - 2003


  • Antipole Clustering
  • Wireless Network
  • closest match
  • mobile base stations

ASJC Scopus subject areas

  • Computer Science (miscellaneous)


Dive into the research topics of 'Fast clustering and minimum weight matching algorithms for very large mobile backbone wireless networks'. Together they form a unique fingerprint.

Cite this