Extending cloud infrastructure to the Network Edge represents a breakthrough to support delay-sensitive applications in next 5G cellular systems. In this context, to enable ultrashort response times, fast relocation of service instances between edge nodes is required to cope with user mobility. To face this issue, proactive service replication is considered a promising strategy to reduce the overall migration time and to guarantee the desired Quality of Experience (QoE). On the other hand, the provisioning of replicas over multiple edge nodes increases the resource consumption of constrained edge nodes and the relevant deployment cost. Given the two conflicting objectives, in this paper we investigate different optimization models for proactive service migration at the Network Edge, which can exploit prediction of user mobility patterns. In particular, we define two Integer Linear Problem optimization schemes, which aim at respectively minimizing the QoE degradation due to service migration, and the cost of replicas' deployment. Performance evaluation shows the effectiveness of our proposed solutions.