To provide satisfactory coverage is very important in many sensor network applications such as military surveillance. In order to obtain the required coverage in harsh environments, mobile sensors are helpful since they can move to cover the area not reachable by static sensors. Previous work on mobile sensor deployment is based on a round by round process, where sensors move iteratively until the maximum coverage is reached. Although these solutions can deploy mobile sensors in a distributed way, the mobile sensors may move in a zig-zag way and waste a lot of energy compared to moving directly to the final location. To address this problem, we propose a proxy-based sensor deployment protocol. Instead of moving iteratively, sensors calculate their target locations based on a distributed iterative algorithm, move logically, and exchange new logical locations with their new logical neighbors. Actual movement only occurs when sensors determine their final locations. Simulation results show that the proposed protocol can significantly reduce the energy consumption compared to previous work, while maintaining similar coverage.