A Mesh based Robust Topology Discovery Algorithm for Hybrid Wireless Networks

Wireless networks in home, office and sensor applications consist of nodes with low mobility. Most of these networks have at least a few powerful machines additionally connected by a wireline network. Topology information of the wireless network at these powerful nodes can be used to control transmission power, avoid congestion, compute routing tables, discover resources, and to gather data. In this paper we propose an algorithm for topology discovery in wireless networks with slow moving nodes and present various performance characteristics of this algorithm. The proposed algorithm discovers all links and nodes in a stable wireless network and has an excellent message complexity: the algorithm has an optimal message complexity in a stable network and the overhead degrades slowly with increasing mobility of the nodes.