Efficient load-balancing routing for wireless mesh networks

Wireless mesh networks (WMNs) consist of static wireless routers, some of which, called gateways, are directly connected to the wired infrastructure. User stations are connected to the wired infrastructure via wireless routers. This paper presents a simple and effective management architecture for WMNs, termed configurable access network (CAN). Under this architecture, the control function is separated from the switching function, so that the former is performed by an network operation center (NOC) which is located in the wired infrastructure. The NOC monitors the network topology and user performance requirements, from which it computes a path between each wireless router and a gateway, and allocates fair bandwidth for carrying the associated traffic along the selected route. By performing such functions in the NOC, we offload the network management overhead from wireless routers, and enable the deployment of simple/low-cost wireless routers. Our goal is to maximize the network utilization by balancing the traffic load, while providing fair service and quality of service (QoS) guarantees to the users. Since, this problem is NP-hard, we devise approximation algorithms that provide guarantees on the quality of the approximated solutions against the optimal solutions. The simulations show that the results of our algorithms are very close to the optimal solutions. (C) 2006 Published by Elsevier B.V.