In wireless sensor networks (WSNs), a good sensor deployment method is vital to the quality of service (QoS) provided by WSNs. This QoS depends on the coverage of the monitoring area. In WSNs with locomotion facilities, sensors can move around and self-deploy to ensure coverage and load balancing. In SMART [1], various optimization problems are defined to minimize different parameters. In this paper, we focus on minimizing total moving distance and propose an optimal, but centralized solution, based on the Hungarian method. We then propose several efficient, albeit non-optimal, distributed solutions based on the scanbased solution in [1]. Extensive simulations have been done to verify the effectiveness of the proposed solutions.