The limitation on battery lifetime has been a critical issue for the advancement of mobile computing. Different types of power-saving techniques have been proposed in various fields. In order to provide feasible energy-conserving mechanisms for the mobile subscriber stations (MSSs), three power-saving types have been proposed for the IEEE 802.16e broadband wireless networks. However, these power-saving types are primarily targeting for the cases with a single connection between the base station (BS) and the MSS. With the existence of multiple connections, the power efficiency obtained by adopting the conventional scheduling algorithm can be severely degraded. In this paper, with the consideration of multiple connections and their quality-of-service (QoS) constraints, a frame aggregation-based power-saving scheduling (FAPS) algorithm is proposed to enhance the power efficiency by aggregating multiple under-utilized frames into fully-utilized ones. The optimality on the minimum number of listen frames in the proposed FAPS algorithm is also provided, and is further validated via the correctness proofs. Performance evaluation of proposed FAPS scheme is conducted and compared via simulations. Simulation results show that the power efficiency of FAPS algorithm outperforms the other existing protocols with tolerable frame delay.