| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Movement-Assisted Sensor Deployment
June 2006 (vol. 5 no. 6)
pp. 640-652
Adequate coverage is very important for sensor networks to fulfill the issued sensing tasks. In many working environments, it is necessary to make use of mobile sensors, which can move to the correct places to provide the required coverage. In this paper, we study the problem of placing mobile sensors to get high coverage. Based on Voronoi diagrams, we design two sets of distributed protocols for controlling the movement of sensors, one favoring communication and one favoring movement. In each set of protocols, we use Voronoi diagrams to detect coverage holes and use one of three algorithms to calculate the target locations of sensors if holes exist. Simulation results show the effectiveness of our protocols and give insight on choosing protocols and calculation algorithms under different application requirements and working conditions.
[1] 640 “Berkeley Sensor and Actuator Center,” http:/www-bsac.eecs. berkeley.edu, 2004.[2] “Wireless Sensing Networks,” http:/wins.rsc.rockwell.com, 2005.[3] “US Naval Observatory (USNO) GPS Operations,” http://tycho.usno.navy.milgps.html, Apr. 2001.[4] F. Aurenhammer, “Voronoi Diagrams— A Survey of a Fundamental Geometric Data Structure,” ACM Computing Surveys, vol. 23, pp. 345-405, 1991.[5] T. Clouqueur, V. Phipatanasuphorn, P. Ramanathan, and K.K. Saluja, “Sensor Deployment Strategy for Target Detection,” Proc. First ACM Int'l Workshop Wireless Sensor Networks and Applications, 2002.[6] D. Koditschek, “Planning and Control via Potential Functions,” Robotics Rev. I, pp. 349-367, 1989.[7] D. Niculescu and B. Nath, “Ad Hoc Positioning Systems (APS) Using AoA,” Proc. IEEE Infocom, 2003.[8] F. Zhao and L. Guibas, Wireless Sensor Networks. Morgan Kaufmann, 2004.[9] S. Fortune, D. Du, and F. Hwang, “Voronoi Diagrams and Delaunay Triangulations,” Euclidean Geometry and Computers, 1992.[10] G. Wang, G. Cao, and T. La Porta, “Movement-Assisted Sensor Deployment,” Proc. IEEE Infocom, March 2004.[11] W.R. Heinzelman, J. Kulik, and H. Balakrishnan, “Adaptive Protocols for Information Dissemination in Wireless Sensor Network,” Proc. ACM MobiCom, 1999.[12] A. Howard, M.J. Mataric, and G.S. Sukhatme, “An Incremental Self-Deployment Algorithm for Mobile Sensor Networks,” Autonomous Robots, special issue on intelligent embedded systems, Sept. 2002.[13] A. Howard, M.J. Mataric, and G.S. Sukhatme, “Mobile Sensor Networks Deployment Using Potential Fields: A Distributed, Scalable Solution to the Area Coverage Problem,” Proc. Sixth Int'l Symp. Distributed Autonomous Robotics Systems, June 2002.[14] L. Hu and D. Evans, “Localization for Mobile Sensor Networks,” Proc. ACM MobiCom, 2004.[15] C. Intanagonwiwat, R. Govindan, and D. Estrin, “Directed Diffusion: A Scalable and Robust Communication,” Proc. ACM MobiCom, 2000.[16] J. Nocedal and S.J. Wright, Numerical Optimization. New York: Springer, 1999.[17] J. Lengyel, M. Reichert, B. Donald, and D. Greenberg, “Real-Time Robot Motion Planning Using Rasterizing Computer Graphics Hardware,” Proc. SIGGRAPH, 1990.[18] Q. Li, M. De Rosa, and D. Rus, “Distributed Algorithms for Guiding Navigation across a Sensor Network,” Proc. ACM MobiCom, 2003.[19] N. Megiddo, “Linear-Time Algorithms for Linear Programming in $R^3$ and Related Problems,” SIAM J. Computing, vol. 12, pp. 759-776, 1983.[20] S. Meguerdichian, F. Koushanfar, G. Qu, and M. Potkonjak, “Exposure In Wireless Ad-Hoc Sensor Networks,” Proc. ACM MobiCom, 2001.[21] S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M.B. Srivastava, “Coverage Problems in Wireless Ad-Hoc Sensor Network,” Proc. IEEE Infocom, 2001.[22] N. Patwari and A. HeroIII, “Using Proximity and Quantized RSS for Sensor Location in Wireless Location in Wireless Networks,” Proc. Workshop Wireless Sensor Networks and Applications, 2003.[23] C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity. Dover, 1998.[24] G.J. Pottie and W.J. Kaiser, “Wireless Integrated Network Sensors,” Comm. ACM, May 2000.[25] A. Savvides, C. Han, and M.B. Strivastava, “Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors,” Proc. ACM MobiCom, 2001.[26] G.T. Sibley, M.H. Rahimi, and G.S. Sukhatme, “Robomote: A Tiny Mobile Robot Platform for Large-Scale Sensor Networks,” Proc. IEEE Int'l Conf. Robotics and Automation, 2002.[27] S. Skyum, “A Simple Algorithm for Computing the Smallest Enclosing Circle,” Information Processing Letters, vol. 37, pp. 121-125, 1991.[28] K. Sohrabi, J. Gao, V. Ailawadhi, and G.J. Pottie, “Protocols for Self-Organization of a Wireless Sensor Network,” IEEE Personal Comm., vol. 7, no. 5, pp. 16-27, Oct. 2000.[29] E. Welzl, “Smallest Enclosing Disks (Balls and Ellipsoids),” New Results and New Trends in Computer Science, pp. 359-370, 1991.[30] Y. Zou and K. Chakrabarty, “Sensor Deployment and Target Localization Based on Virtual Forces,” Proc. IEEE Infocom, 2003.
Index Terms:
Mobile sensor networks, sensor coverage, distributed algorithm.
Citation:
Guiling Wang, Guohong Cao, Thomas F. La Porta, "Movement-Assisted Sensor Deployment," IEEE Transactions on Mobile Computing, vol. 5, no. 6, pp. 640-652, June 2006, doi:10.1109/TMC.2006.80
