PaMeLA: A joint channel assignment and routing algorithm for multi-radio multi-channel wireless mesh networks with grid topology

The performance of multi-radio multi-channel Wireless Mesh Networks (WMNs) based on the IEEE 802.11 technology depends significantly on how the channels are assigned to the radios and how traffic is routed between the access points and the gateways. In this paper we propose an algorithmic approach to this problem, for which no conclusive solution has been put forward in the literature so far. The core of our scheme, called PaMeLA, consists of splitting the overall Joint Channel Assignment and Routing (JCAR) problem into a number of local optimization subproblems, one for every node of the WMN, that are solved sequentially. Any sub-problem is formulated as an Integer Linear optimization Problem (ILP), whose optimal solution can be found using branch-and-cut in a reasonable amount of time. The final solution is obtained after a post-processing phase. In its current form, the algorithm is tailored to suit WMNswith a single gateway in a square-grid topology, which is of practical interest in many application scenarios. PaMeLA is compared through detailed packetlevel simulation with several state-of-the-art JCAR algorithms and it is shown to attain better performance, in terms of the packet loss rate. ©2009 IEEE.