In an IEEE 802.16(d) (WiMAX) mesh network, network bandwidth can be managed by either the centralized scheduling (CS) mode or the distributed scheduling (DS) mode. Compared with the CS mode, the DS mode provides a larger bandwidth capacity and is more scalable. However, because the DS mode uses an on-demand three-way handshake procedure to establish data schedules, the network quality experienced by application programs may fluctuate drastically. To address this problem, in this paper we propose three schemes to improve the data scheduling efficiency of the DS mode of the IEEE 802.16(d) mesh network. Our simulation results show that network performances and qualities experienced by application programs are significantly improved under our schemes.