In the wireless communication systems, the power consumption of a mobile device is very important issue due to its battery limitations. Hence most of the standards for wireless networks including a mobile WiMAX system are supporting their own power saving mode in way that a mobile device is able to reduce its energy usage while in the mode. However, those standards just define the arrangement of special time intervals, called a paging listening interval, during which the device needs to receive the paging-related control messages, and they do not specify how to effectively reduce the power in many different network environments. This means the amount of power spent by the device is very dependent on the implementations of individual device-vendors, and undesirable paging loss may happen according to the channel conditions. To reduce unnecessary power usage and the risk of paging loss, this paper proposes the effective frequency/BS selection algorithm applicable to a mobile device operating in the power saving mode, which serves the device with better BS based on the tracking for channel variation. This algorithm consists of the channel estimation phase during each paging listening interval, the tracking phase for the measured results, the frequency reselection phase based on the tracking activity, and the preferred BS reselection phase. Thus the proposed method can improve the paging performance while the device is moving in the network. Also the simulation result shows that the presented scheme is superior to other candidates in energy efficiency due to the channel-adaptive frequency/BS selection.