GAR: Gradient assisted routing for topology self-organization in dynamic mesh networks

Research output: Contribution to journalArticleScientificpeer-review

10 Downloads (Pure)


Modern mobile handheld devices, such as smartphones and tablets, feature multiple wireless interfaces, some of which can support device-to-device communications, which enable mesh networks on even when the infrastructure is unavailable. One of the key technological challenges hampering the use of multi-hop mesh networks is the extremely high communication overhead of route discovery and maintenance algorithms. The problem is especially pronounced under dynamic network conditions caused by user mobility and nodes joining and leaving the network. In this paper, we propose a fully distributed algorithm for constructing a virtual coordinate system used for geo-like routing by approximating the physical network nodes coordinate. The proposed algorithm, called gradient assisted routing (GAR), builds upon two-hop neighbors’ information exchanged in beacons in contrast to conventional geographic routing protocols which rely on external positioning information. We evaluate the proposed solution using algorithmic, topological, and routing-related metrics of interest. We further numerically quantify how the node mobility increases the time needed for topology stabilization, and how network size affects the route discovery success rate. Our comparison also shows that for small to mid-size mesh networks (up to 60 nodes), the performance of the proposed routing procedure is similar to the conventional geographic routing protocols that exploit external positioning information. The proposed solution may efficiently supplement the traditional on-demand routing in small to mid-size mesh systems by independently establishing 50 to 70% of paths and thereby reducing the discovery overheads.

Original languageEnglish
Pages (from-to)10-23
Number of pages14
JournalComputer Communications
Publication statusPublished - 1 Jun 2022
Publication typeA1 Journal article-refereed


  • Geographical routing
  • Topology maintenance
  • Topology organization
  • Virtual coordinate system
  • Wireless mesh

Publication forum classification

  • Publication forum level 1

ASJC Scopus subject areas

  • Computer Networks and Communications


Dive into the research topics of 'GAR: Gradient assisted routing for topology self-organization in dynamic mesh networks'. Together they form a unique fingerprint.

Cite this