The top load balanced forest routing in mesh networks
Yean‐Fu Wen, F.Y.-S. Lin · 2006
Abstract —Public wireless local area networks (PWLAN), which provide last-mile connectivity to the Internet, are popular worldwide, especially in heavily populated cities. Traditional ad hoc shortest path routing algorithms, such as AODV and DSR, focus on minimum hops that cause traffic to concentrate on some TAPs, while others are light. Thus, the major issue addressed this paper is how to cluster backbone mesh networks efficiently so that routing is concentrated on given gateways. We formulate the problem as an integer programming problem with minimal routing traffic as the objective function, subject to the top load balancing and link capacity. We propose a greedy algorithm, called Greedy Load Balancing Routing (GLBR), to solve this problem and evaluate it by the Lagrangian Relaxation approach to quantify the objective value correctly. The experimental results show that the algorithm achieves near-optimization, and obtains a gap smaller than 5% and 10% in grid-based and random-based architectures, respectively.