Routing and packet scheduling in WiMAX mesh networks

This paper considers the problem of maximizing the system throughput in IEEE 802.16 broadband access networks with mesh topology, and the following results are presented. We consider a linear chain network and discuss its applicability for providing cost effective solutions in sparsely populated areas, such as interstate highways and rural communities. We provide an optimal scheduling algorithm and establish an analytical result on the length of the schedule for linear chain networks. We also consider the problem of routing and packet scheduling in general topology, and show its NP-completeness. Based on our optimal algorithm for linear networks, we propose algorithms that find routes and schedules of packet transmissions in general mesh topologies. The performance of our proposed algorithms is analyzed using the NS-2 simulator. The results show that the proposed algorithms perform significantly better than other existing algorithms.