An optimum branching-based efficient distributed broadcast scheme for wireless ad hoc networks

In Ad hoc networks, links between nodes may be asymmetric for many reasons. In general, a graph with asymmetric link costs provides a more realistic network modeling perspective. In an earlier work, we proposed a broadcast routing scheme based on Edmonds algorithm for ad hoc networks with asymmetric link costs. The method involved setting up link state, finding minimum in-edge, detecting cycles, re-weighting and breaking cycles. In this paper, the distributed implementation of the method is examined. In centralized routing algorithms, link state and other relevant information are kept in the routing table of each node. In order to obtain such information, global information exchanges are required which incur high overhead and waste of energy resources. In contrast, the distributed implementation of the Edmonds-based broadcast routing only calls for local information exchanges. The distributed algorithm is compared against distributed BIP and MCDS using different performance metrics.