Relay nodes (RN) have been suggested to be placed near the edge of a cellular network in order to improve link qualities of cell edge user equipments (UEs). Compared to conventional homogeneous networks, system performance for the relay-enhanced network can be significantly degraded if handovers between the RNs and evolved node base-station (eNB) are not correctly and immediately determined by the eNB. Therefore, the UEs may suffer from worse channel conditions which can result in increased energy consumption of entire network. In existing long term evolution advanced (LTE-A) standard, fixed reporting time period from the UEs to eNB is considered inflexible which can be too long to provide immediate handover decisions. Hence, prediction-based handover (PH) scheme is proposed to allow eNBs to make potential handover decisions within the UE's reporting period. The channel qualities for both the direct and relay-enhanced links during this period are predicted based on the partially observable Markov decision process. Moreover, three objectives are designed for the proposed PH scheme including maximizing received signal to interference plus noise ratios of UEs, and minimizing system energy consumption without and with considerations of energy outage of relay nodes. Numerical results show that the proposed PH schemes outperform conventional handover scheme from the perspectives of both system energy consumption and outage probability.