Load-Based Metrics and Flooding in Wireless Mesh Networks

摘要

On-demand routing protocols in wireless ad-hoc (mesh) networks use route requests to search for a routing path. To determine a route that optimizes a metric function, an intermediate node retransmits a route request that has a lower metric value. This can create flooding waves, where a large number of route requests are retransmitted through the network. In this paper, we study different classes of node load-based metric functions that are useful in sensor networks and telephony applications. We tackle the problem of determining optimal routes while minimizing flooding waves. We define a notion of efficient flooding and show that an online algorithm can discover an optimal metric path while achieving efficient flooding for a sum load metric, but this is not possible for a min-max load metric. We simulate an online algorithm that is provably efficient in terms of flooding for some classes of metrics and analyze its performance for different load-based metric functions.