Stochastic event capture using mobile sensors subject to a quality metric

ABSTRACT

Mobile sensors cover more area over a period of time than the same number of stationary sensors. However, the quality of coverage achieved by mobile sensors depends on the velocity, mobility pattern, number of mobile sensors deployed and the dynamics of the phenomenon being sensed. The gains attained by mobile sensors over static sensors and the optimal motion strategies for mobile sensors are not well understood. In this paper we consider the problem of event capture using mobile sensors. The events of interest arrive at certain points in the sensor field and fade away according to arrival and departure time distributions. An event is said to be captured if it is sensed by one of the mobile sensors before it fades away. For this scenario we analyze how the quality of coverage scales with the velocity, path and number of mobile sensors. We characterize the cases where the deployment of mobile sensors has no advantage over static sensors and find the optimal velocity pattern that a mobile sensor should adopt.We also present algorithms for two motion planning problems: (i) for a single sensor, what is the minimum speed and sensor trajectory required to satisfy a bound on event loss probability and (ii) for sensors with fixed speed, what is the minimum number of sensors required to satisfy a bound on event loss probability. When events occur only along a line or a closed curve our algorithms return optimal velocity for the minimum velocity problem. For the minimum sensor problem, the number of sensors used is within a factor two of the optimal solution. For the case where the events occur at arbitrary points on a plane we present heuristic algorithms for the above motion planning problems and bound their performance with respect to the optimal. The results of this paper have wide range of applications in areas like surveillance, wildlife monitoring, hybrid sensor networks and under-water sensor networks.

REFERENCES

• 1: James San Jacinto Mountain Reserve. http://www.jamesreserve.edu.
• 2: I. F. Akyildiz, D. Pompili, and T. Melodia. Underwater acoustic sensor networks: research challenges. Ad Hoc Networks, 3(3):257--279, 2005.
• 3: M. Batalin, W. Kaiser, R. Pon, G. S. Sukhatme, G. Pottie, Y. Yu, J. Gordon, M. H. Rahimi, and D. Estrin. Task allocation for event-aware spatiotemporal sampling of environmental variables. In IROS, pages 1846--1853, 2005.
• 4: M. Batalin and G. S. Sukhatme. Sensor network-mediated multi-robot task allocation. In The Third International Naval Research Laboratory Multi-Robot Systems Workshop, pages 27--38, Mar 2005.
• 5: Maxim A. Batalin , Mohammad Rahimi , Yan Yu , Duo Liu , Aman Kansal , Gaurav S. Sukhatme , William J. Kaiser , Mark Hansen , Gregory J. Pottie , Mani Srivastava , Deborah Estrin, Call and response: experiments in sampling the environment, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031499]
• 6: S. Bergbreiter and K. Pister. Cotsbots: An off-the-shelf platform for distributed robotics. In IROS, pages 1632--1637, 2003.
• 7: N. Bisnik, A. Abouzeid, and V. Isler. Event capture problem in mobile sensor networks. Technical Report, ECSE Dept., RPI. Available at http://www.ecse.rpi.edu/abouzeid/mobileCoverage.pdf.
• 8: Thomas Clouqueur , Veradej Phipatanasuphorn , Parameswaran Ramanathan , Kewal K. Saluja, Sensor deployment strategy for target detection, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570745]
• 9: Karthik Dantu , Mohammad Rahimi , Hardik Shah , Sandeep Babel , Amit Dhariwal , Gaurav S. Sukhatme, Robomote: enabling mobility in sensor networks, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 10: Adrian Dumitrescu , Joseph S. B. Mitchell, Approximation algorithms for TSP with neighborhoods in the plane, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.38-46, January 07-09, 2001, Washington, D.C., United States
• 11: Chih-fan Hsin , Mingyan Liu, Network coverage using low duty-cycled sensors: random & coordinated sleep algorithms, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984685]
• 12: R. G. Gallager. Discrete Stochastic Processes, chapter 3, pages 63--64. Kluwer Academic Publishers, first edition, 1995.
• 13: Chao Gui , Prasant Mohapatra, Virtual patrol: a new power conservation design for surveillance using sensor networks, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 14: A. Howard, M. Mataric, and G. Sukhatme. Mobile sensor network deployment using potential fields: A distributed. In DARS, June 2002.
• 15: Chi-Fu Huang , Yu-Chee Tseng, The coverage problem in a wireless sensor network, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941350.941367]
• 16: J. M. Kahn , R. H. Katz , K. S. J. Pister, Next century challenges: mobile networking for “Smart Dust”, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.271-278, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313558]
• 17: Santosh Kumar , Ten H. Lai , József Balogh, On k-coverage in a mostly sleeping sensor network, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023735]
• 18: H. T. Kung and D. Vlah. Efficient location tracking using sensor networks. In WCNC, 2003.
• 19: Jean-Claude Latombe, Robot Motion Planning, Kluwer Academic Publishers, Norwell, MA, 1991
• 20: S. M. LaValle. Planning Algorithms. Cambridge University Press (also available at http://msl.cs.uiuc.edu/planning/).
• 21: Mauro Leoncini , Giovanni Resta , Paolo Santi, Analysis of a wireless sensor dropping problem in wide-area environmental monitoring, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 22: Benyuan Liu , Peter Brass , Olivier Dousse , Philippe Nain , Don Towsley, Mobility improves coverage of sensor networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062728]
• 23: Alan Mainwaring , David Culler , Joseph Polastre , Robert Szewczyk , John Anderson, Wireless sensor networks for habitat monitoring, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570751]
• 24: M. B. McMickell, B. Goodwine, and L. A. Montestruque. Micabot: a robotic platform for large-scale distributed robotics. In ICRA, pages 1600--1605, 2003.
• 25: Seapahn Megerian , Farinaz Koushanfar , Gang Qu , Giacomino Veltri , Miodrag Potkonjak, Exposure in wireless sensor networks: theory and practical solutions, Wireless Networks, v.8 n.5, p.443-454, September 2002 [doi>10.1023/A:1016586011473]
• 26: S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava. Coverage problems in wireless ad-hoc sensor networks. In INFOCOM, pages 1380--1387, 2001.
• 27: Seapahn Meguerdichian , Farinaz Koushanfar , Gang Qu , Miodrag Potkonjak, Exposure in wireless Ad-Hoc sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.139-150, July 2001, Rome, Italy [doi>10.1145/381677.381691]
• 28: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 29: S. Shakkottai, R. Srikant, and N. B. Shroff. Unreliable sensor grids: Coverage, connectivity and diameter. In INFOCOM, 2003.
• 30: G. T. Sibley, M. H. Rahimi, and G. S. Sukhatme. Robomote: A tiny mobile robot platform for large-scale ad-hoc sensor networks. In ICRA, pages 1143--1148, 2002.
• 31: David C. Steere , Antonio Baptista , Dylan McNamee , Calton Pu , Jonathan Walpole, Research challenges in environmental observation and forecasting systems, Proceedings of the 6th annual international conference on Mobile computing and networking, p.292-299, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345961]
• 32: Di Tian , Nicolas D. Georganas, A coverage-preserving node scheduling scheme for large wireless sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570744]
• 33: I. Vasilescu , K. Kotay , D. Rus , M. Dunbabin , P. Corke, Data collection, storage, and retrieval with an underwater sensor network, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098936]
• 34: G. Wang, G. Cao, and T. L. Porta. Movement-assisted sensor deployment. In INFOCOM, 2004.
• 35: Xiaorui Wang , Guoliang Xing , Yuanfang Zhang , Chenyang Lu , Robert Pless , Christopher Gill, Integrated coverage and connectivity configuration in wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958496]
• 36: Guoliang Xing , Chenyang Lu , Robert Pless , Joseph A. O'Sullivan, Co-Grid: an efficient coverage maintenance protocol for distributed sensor networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984683]
• 37: H. Yang and B. Sikdar. A protocol for tracking mobile targets using sensor network. In WSNA, 2003.
• 38: Fan Ye , Gary Zhong , Jesse Cheng , Songwu Lu , Lixia Zhang, PEAS: A Robust Energy Conserving Protocol for Long-lived Sensor Networks, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.28, May 19-22, 2003
• 39: Y. Zou and K. Chakrabarty. Sensor deployment and target localization based on virtual forces. In INFOCOM, 2003.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Performance, Theory

Keywords:
event capture, mobile robot motion planning, reliable coverage, robot sensing systems