Supporting Quality of Service (QoS) guarantees for diverse multimedia services is the primary concern for IEEE802.16j networks. A scheduling scheme that satisfies the QoS requirements has become more important for wireless communications. We proposed an adaptive nontransparent-based distributed scheduling scheme (ANDS) for IEEE 802.16j networks. ANDS comprises three major components: Priority Assignment, Resource Allocation, Preserved Bandwidth Adjustment. Different service-type connections primarily depend on their QoS requirements to adjust priority assignments and dispatch bandwidth resources dynamically. Meanwhile, we promote the connections, which do not satisfy QoS requirements, to avoid the delay and starvation. Simulation results show that our APS methodology outperforms the representative scheduling approaches in both QoS satisfaction and maintains fairness in starvation prevention.