joint mac-aware routing and load balancing in mesh networks
Past approaches to routing in mesh networks either (i) do not account for the MAC-layer interactions between the links in a tractable manner, or (ii) are agnostic to load-balancing across gateways. Our answer to these problems is MaLB (MAC-aware and Load Balanced routing algorithm), a greedy, tractable, and distributed mesh routing algorithm. Since the underlying objective function has high combinatorial complexity, MaLB uses a greedy approach. MaLB finds an optimum routing forest (union of trees rooted at the gateways) by taking into account MAC-layer interaction between links, as well as optimum multi-hop association of mesh nodes to gateways. MaLB builds on top of ETP (Expected Through-Put), a recently proposed MAC-aware routing metric. We also propose a low complexity variant of MaLB called LB (Load Balanced routing algorithm) which performs load balancing in a MAC-agnostic manner. MaLB performs especially well in networks with skewed topologies that result from unplanned mesh network deployment, as well as in the presence of gateway failures. Simulations with an enhanced version of ns-2 show that MaLB results in up to 60\% higher throughput than a shortest path algorithm with ETX (Expected Transmission Count). Furthermore, MaLB results in up to 30\% improvement over the LB algorithm, as well as a shortest path algorithm with ETT (Expected Transmission Time).
routing load balancing mesh mesh network network account interaction links routing algorithm algorithm distributed object functional complexity trees association metrication topologies deployment presence failure simulation version throughput shortest path timing layer