Recently, various mobile stations become widely available due to the advance of communication and computer technologies. Because of the mobility of terminal devices and the bandwidth limitation of wireless networks, it is difficult to apply traditional error recovery schemes for fixed networks to mobile network environments directly. So, several recovery schemes for mobile environments have been proposed. They are improved versions of the backward recoveries, especially the checkpointing and the message logging. However, these schemes consider either the total cost or the recovery time. In this paper, we propose two new schemes which consider both of the cost and the time.