This paper considers the problem of deploying a mobile sensor network in an unknown environment. A mobile sensor network is a distributed collection of nodes, each of which has sensing, computation, communication and locomotion capabilities. 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. We propose a clustered virtual force algorithm (CVFA) as an energy efficiency deployment strategy to enhance the coverage after an initial random placement of sensors. The virtual forces are constructed such that each node is attracted or repelled by other nodes, thereby forcing the network to spread itself throughout the environment. The approach is both distributed and scalable. The major concept of CVFA is to decrease unnecessary excessive movements through efficient communications. Because of the movement is much more expensive than communication and computation in terms of energy. In CVFA, more global information of k-hop neighbors can be acquired by the inter-cluster communications. Hence, mobile sensors can calculate their target locations, move logically, and update new logical locations through inter-cluster communications. Actual movement only occurs when sensors determine their final locations. Simulation results show that CVFA can significantly reduce the energy consumption compared to previous work, while maintaining similar coverage.

This paper considers the problem of deploying a mobile sensor network in an unknown environment. A mobile sensor network is a distributed collection of nodes, each of which has sensing, computation, communication and locomotion capabilities. 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. We propose a clustered virtual force algorithm (CVFA) as an energy efficiency deployment strategy to enhance the coverage after an initial random placement of sensors. The virtual forces are constructed such that each node is attracted or repelled by other nodes, thereby forcing the network to spread itself throughout the environment. The approach is both distributed and scalable. The major concept of CVFA is to decrease unnecessary excessive movements through efficient communications. Because of the movement is much more expensive than communication and computation in terms of energy. In CVFA, more global information of k-hop neighbors can be acquired by the inter-cluster communications. Hence, mobile sensors can calculate their target locations, move logically, and update new logical locations through inter-cluster communications. Actual movement only occurs when sensors determine their final locations. Simulation results show that CVFA can significantly reduce the energy consumption compared to previous work, while maintaining similar coverage.

1. INTRODUCTION 1
2. VIRTUAL FORCE APPROACH 5
3. CLUSTERED VIRTUAL FORCE ALGORITHM 9
3.1. CLUSTERING BY DENSITY 12
3.2. CLUSTERED DEPLOYMENT 18
3.2.1. The intra-cluster deployment phase 18
3.2.2. The inter-cluster deployment phase 24
3.2.3. One-time movement, Adjustment and Stabilization phase 28
4. PERFORMANCE EVALUATIONS 30
4.1. COVERAGE 31
4.1. MOVING DISTANCE 35
4.3. ENERGY CONSUMPTION 43
4.4. UNIFORMITY 45
5. CONCLUSION 47
REFERENCE 49

[1]W. Heinzelman, J. Kulik, and H. Balakrishnan, "Adaptive protocols for information dissemination in wireless sensor networks," presented at MobiCom '99: Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, 1999.
[2]K. Sohrabi, J. Gao, V. Ailawadhi, and G. J. Pottie, "Protocols for self-organization of a wireless sensor network," Personal Communications, IEEE [see also IEEE Wireless Communications], vol. 7, pp. 16-27, 2000.
[3]G. J. Pottie and W. J. Kaiser, "Wireless integrated network sensors," Commun. ACM, vol. 43, pp. 51-58, 2000.
[4]C. Intanagonwiwat, R. Govindan, and D. Estrin, "Directed diffusion: a scalable and robust communication paradigm for sensor networks," presented at MobiCom '00: Proceedings of the 6th annual international conference on Mobile computing and networking, 2000.
[5]N. Heo and P. K. Varshney, "Energy-efficient deployment of Intelligent Mobile sensor networks," Systems, Man and Cybernetics, Part A, IEEE Transactions on, vol. 35, pp. 78-92, 2005.
[6]S. Tilak, N. Abu-Ghazaleh, and W. Heinzelman, "Infrastructure tradeoffs for sensor networks," presented at WSNA '02: Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, 2002.
[7]T. Clouqueur, V. Phipatanasuphorn, P. Ramanathan, and K. Saluja, "Sensor deployment strategy for target detection," presented at WSNA '02: Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, 2002.
[8]Jr and E. Callaway, Wireless Sensor Networks: Architectures and Protocols: AUERBACH, 2003.
[9]I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "A survey on sensor networks," Communications Magazine, IEEE, vol. 40, pp. 102-114, 2002.
[10]S. S. Iyengar, L. Prasad, and H. Min, Advances in Distributed Sensor Integration: Application and Theory (Prentice Hall Series on Environmental and Intelligent Manufacturing Systems): Prentice Hall, 1995.
[11]A. Howard, M. Mataric, and G. Sukhatme, "Mobile Sensor Network Deployment using Potential Fields: A Distributed," in Proceedings of the 6th International Symposium on Distributed Autonomous Robotics Systems (DARS02). 2002.
[12]A. Howard, Matari, Maja, and G. Sukhatme, "An Incremental Self-Deployment Algorithm for Mobile Sensor Networks," Auton. Robots, vol. 13, pp. 113-126, 2002.
[13]S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava, "Coverage problems in wireless ad-hoc sensor networks," presented at INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, 2001.
[14]A. Winfield, "Distributed sensing and data collection via broken ad hoc wireless connected networks of mobile robots," 2000.
[15]S. S. Dhillon and K. Chakrabarty, "Sensor placement for effective coverage and surveillance in distributed sensor networks," presented at Wireless Communications and Networking, 2003. WCNC 2003. 2003 IEEE, 2003.
[16]Y. Zou and K. Chakrabarty, "Sensor deployment and target localization in distributed sensor networks," Trans. on Embedded Computing Sys., vol. 3, pp. 61-91, 2004.
[17]V. Kawadia and P. R. Kumar, "Power control and clustering in ad hoc networks," presented at INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE, 2003.
[18]C. R. Lin and M. Gerla, "Adaptive clustering for mobile wireless networks," Selected Areas in Communications, IEEE Journal on, vol. 15, pp. 1265-1275, 1997.
[19]M. Tubaishat and S. Madria, "Sensor networks: an overview," Potentials, IEEE, vol. 22, pp. 20-23, 2003.
[20]Y. Xu, J. Heidemann, and D. Estrin, "Geography-informed energy conservation for Ad Hoc routing," presented at MobiCom '01: Proceedings of the 7th annual international conference on Mobile computing and networking, 2001.
[21]O. Younis and S. Fahmy, "HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks," Mobile Computing, IEEE Transactions on, vol. 3, pp. 366-379, 2004.
[22]O. Khatib, "Real-time obstacle avoidance for manipulators and mobile robots," Int. J. Rob. Res., vol. 5, pp. 90-98, 1986.
[23]L. Tong, Q. Zhao, and S. Adireddy, "Sensor networks with mobile agents," presented at Military Communications Conference, 2003. MILCOM 2003. IEEE, 2003.
[24]K. Sohrabi, B. Manriquez, and G. J. Pottie, "Near ground wideband channel measurement in 800-1000 MHz," presented at Vehicular Technology Conference, 1999 IEEE 49th, 1999.
[25]S. Basagni, I. Chlamtac, and A. Farago, "A generalized clustering algorithm for peer-to-peer networks," in Proceedings of Workshop on Algorithmic Aspects of Communication, 1997.
[26]W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, "Energy-Efficient Communication Protocol for Wireless Microsensor Networks," presented at HICSS '00: Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, 2000.
[27]P. Rodriguez, S.-M. Tan, and C. Gkantsidis, "On the feasibility of commercial, legal P2P content distribution," SIGCOMM Comput. Commun. Rev., vol. 36, pp. 75-78, 2006.
[28]L.-H. Yen and C. Yu, "Link probability, network coverage, and related properties of wireless ad hoc networks," presented at Mobile Ad-hoc and Sensor Systems, 2004 IEEE International Conference on, 2004.
[29]M.-C. Su and C.-H. Chou, "A modified version of the K-means algorithm with a distance based on cluster symmetry," Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 23, pp. 674-680, 2001.
[30]D. W. Gage, "Command control for many-robot systems," presented at Proceedings of the Nineteenth Annual AUVS Technical Symposium 1992.