The advancement of mobile computing is mainly limited by battery lifetime of an 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. When having multiple connections, the power saving efficiency of an MSS 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. The goals of the first two phases are determining awake-frame candidate sets of unsolicited grant service (UGS) connections and sleep/awake intervals of remaining service-classes connections; 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.