In view of the fact that the current online virtual network embedding algorithms do not consider the fragment resources generated in the embedding process deeply enough, resulting in the problem that the acceptance ratio and the revenue to cost ratio are both low, a mathematical model for virtual network reconfiguration is constructed and a heuristic algorithm for fragment-aware virtual network reconfiguration (FA-VNR) is proposed. The FA-VNR algorithm selects the set of virtual nodes to be migrated according to the fragment degrees of the physical nodes, and selects the best virtual node migration scheme according to the reduction of the fragment degrees of the physical nodes as well as the reduction of the embedding cost of the embedded virtual networks. Extensive simulation results show that the proposed FA-VNR algorithm not only can obviously improve the acceptance ratio and the revenue to cost ratio of the current online virtual network embedding algorithm, but also has better optimization effect than the existing virtual network reconfiguration algorithm.