In the IEEE 802.16e/m standard, three power saving classes (PSCs) are defined to save the energy of a mobile sub-scriber station (MSS). However, how to set the parameters of PSCs to maximize the power saving and guarantee the quality of service is not specified in the standard. Thus, many algorithms were proposed to set the PSCs in IEEE 802.16 networks. However, most of the proposed algorithms consider only the power saving for a single MSS. In the algorithms designed for multiple MSSs, the sleep state, which is set for activation of state transition overhead power, is not considered. The PSC setting for real-time connections in multiple MSSs with consideration of the state transition overhead is studied. The problem is non-deterministic polynomial time hard (NP-hard), and a suboptimal algorithm for the problem is proposed. Simulation results demonstrate that the energy saving of the proposed algorithm is higher than that of state-of-the-art algorithms and approaches the optimum limit.