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

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.