The advancement of mobile computing is mainly limited by battery lifetime of a end device, and thus power management is always a critical design issue in various wireless networks. To conserve power consumption of mobile subscribe stations (MSSs), three types of power saving classes are defined in the IEEE 802.16e standard. However, the defined power saving mechanism is per-connection basis, and thus when an MSS has multiple connections, the power saving efficiency degrades significantly. In this paper, a Least-Awake-Frames Scheduling (LAFS) algorithm is proposed to achieve both energy saving and Quality-of-Service (QoS) fulfillment. The proposed LAFS consists of three phases to take all service classes into consideration. The goals of the first two phases are determining awake-frame candidate sets for unsolicited grant service (UGS) connections and sleep/awake intervals for connections of the remaining service classes; the third phase is to determine sleep and awake frames of an MSS. The simulation results show that our proposed LAFS algorithm outperforms the power saving protocol defined in the IEEE 802.16e, and other existing power saving algorithms.