Using the Lagrange Relaxation Method to Solve the Routing and Packet Scheduling Problem in IEEE 802.16 Mesh Networks

Abstract

In an IEEE 802.16 mesh network, the routing and packet scheduling (RPS) problem is to design a fast scheduling scheme to meet the requirement of all the subscriber stations (SSs) so that all of the packets can be delivered to the base stations (BS) while minimizing the number of time slots and prohibiting the interference between any two packets. There has existed an integer linear programming formulation (ILPF) for the RPS problem, named as ILPF-for-RPS, which can find its optimal solution. However, the execution time of MIPF-for-MSC is very long when the number of SSs is large. This is because that the RPS problem has been proven to be NP-complete. In this paper, the Lagrange relaxation method is applied to shrink the solution space of the ILPF-for-RPS for the purpose of shortening the solution-searching time. First, we theoretically transform the ILPF-for-RPS into a Lagrange relaxation ILPF-for-RPS, whose objective function is then proved to be a concave function. This Lagrange relaxation ILPF-for-RPS simplifies the original ILPF-for-RPS and can be used to find an optimal solution for the RPS problem within a shorter time. According to the computer simulations, in contrast to the original ILPF-for-RPS, our Lagrange relaxation ILPF-for-RPS can attain a minimum time slot schedule within a shorter time for the RPS problem. To be more specific, compared with the original ILPF-for-RPS, our Lagrange relaxation ILPF-for-RPS can decrease the running time by more than 90% in most cases.