Efficient algorithms to solve Broadcast Scheduling problem in WiMAX mesh networks

WiMAX is a last mile technology which provides efficient broadband access and coverage like MAN networks. The WiMAX standard IEEE 802.16d also called as WiMAX Mesh network can operate in multihop mode, in which the subscriber stations can communicate with the base station without having direct link between them. In such type of networks, the allocation of channel for the Subscriber Stations is an open issue. Also, if spatial reuse is enabled in such networks then many links can be activated simultaneously, thus increasing the effective usage of the available resources and providing better service to the available nodes. This paper deals with providing an efficient algorithm for spatial reuse. First, a dynamic programming (DP) algorithm to find the conflict-free set of nodes that can be activated to achieve optimality in throughput is proposed. Next, a genetic algorithm is provided, which is more scalable than the DP approach, but does not guarantee optimality. The results indicate that the algorithms proposed give better performance than the existing algorithms that address the same issue.