Although limiting the number of backhauls, specifically chosen transit access points (TAPs) that forward traffic from other TAPs, reduces the overall costs of a wireless mesh network (WMN), an egress bottleneck is induced, which aggregates traffic and limits the bandwidth. To avoid such problems while working to minimize budgetary expenses, we balanced traffic flow on 'to-be-determined' backhauls and adjacent links, a mixed nonlinear- and integer-programming problem that minimizes the aggregated flow subject to budget, backhaul assignment, top-level load-balanced routing, and link capacity constraints. Two algorithms are proposed, weighted backhaul assignment (WBA) and greedy load-balanced routing (GLBR), that operate in conjunction with Lagrangean relaxation (LR), used for constructing LR-based heuristics and also as a means of quantification and evaluation of the proposed algorithms. Experiment results show that the proposed algorithms achieve near-optimization, outperforming related solutions. Copyright (C) 2008 John Wiley & Sons, Ltd.
