Applying Simulated Annealing to Joint Routing, Scheduling and Variable-Width Channel Allocation for Multi-hop WMNs

Abstract

This pager studies the joint routing, scheduling, and channel assignment problem in single-radio multi-channel WMNs. All the three subproblems are related to the packet transmission rate: the routing problem is to find the transmission paths for packets; the scheduling problem is to plan the transmission order of packets; the channel assignment problem is related to signal interference and synchronization. The joint problem has been studied in the past, but they can only solve small-scale problems and did not consider the effect of signal interference, so that their methods are not efficient and do not meet the practical scenario. With regards to this, we propose a simulated annealing approach with a new coding scheme that divides time into a number of time slots to model the dynamic process of packets. In addition, this paper demonstrates a variable-bandwidth channel allocation method that achieves a good balance between higher synchronization and better control of interference. Experimental results show that our proposed simulated annealing approach can find the same or similar solutions with the exact methods for the cases with a small number of nodes and low traffic load.