Analytic modeling of detection latency in mobile sensor networks

ABSTRACT

An envisioned usage of sensor networks is in surveillance systems for detecting a target or monitoring a physical phenomenon in a region. Traditionally, stationary sensor networks are deployed to carry out the sensing operations. In many applications, if the monitored region is relatively large compared to the sensing range of a node, a large number of nodes are required in the region to achieve high coverage. Using mobile nodes in such situations can be an attractive alternative. Mobility of sensor nodes has been studied in sensor networks for many purposes such as power saving, data collection, and packet delivery. However, nearly all research literature for the target detection problem has focused on stationary sensor networks. This paper investigates the problem of detecting the presence/absence of a target using mobile sensor networks. It presents an analytic method to evaluate the detection latency based on a collaborative sensing approach using nodes with uncoordinated mobility. We verify the analytic model through simulations. The analytic method provides a simple way of analyzing the tradeoff between number of nodes and detection latency in a mobile sensor network. The analysis is also used to compare the performance of mobile and stationary sensor networks with respect to these measures. Results show that if the target is present at the worst possible location in a given deployment, then detection latency of mobile sensor networks is considerably less as compared to that of stationary networks with the same number of nodes.

REFERENCES

• 1: Paolo Santi , Douglas M. Blough, The Critical Transmitting Range for Connectivity in Sparse Wireless Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.2 n.1, p.25-39, January 2003 [doi>10.1109/TMC.2003.1195149]
• 2: R. Shah, S. Roy, S. Jain, and W. Brunette. Data MULEs: modeling a three-tier architecture for sparse sensor networks. In Proc. of the first IEEE International Workshop on Sensor Network Protocols and Applications, pages 30--41, May 2003.
• 3: W. Zhao , M. Ammar , E. Zegura, A message ferrying approach for data delivery in sparse mobile ad hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989483]
• 4: David Kiyoshi Goldenberg , Jie Lin , A. Stephen Morse , Brad E. Rosen , Y. Richard Yang, Towards mobility as a network control primitive, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989481]
• 5: T.-L. Chin, P. Ramanathan, K. K. Saluja, and K.-C. Wang. Exposure for collaborative detection using mobile sensor networks. In Proc. of MASS, Nov. 2005.
• 6: G. T. sibley, M. H. Rahimi, and G. S. Sukhatme. Robomote: A tiny mobile robot platform for large-scale ad-hoc sensor networks. In Proceedings of IEEE International Conference on Robotics and Automation, pages 1143--1148, 2002.
• 7: M. B. McMickell, B. Goodwine, and L. A. Montestruque. MICAbot: A robotic platform for large-scale distributed robotics. In Proceedings of IEEE International Conference on Robotics and Automation, pages 1600--1605, 2003.
• 8: M. Rahimi, H. Shah, G. S. Sukhatme, J. Heidemann, and D. Estrin. Studying the feasibility of energy harvesting in a mobile sensor network. In Proceedings of IEEE International Conference on Robotics and Automation, pages 19--24, 2003.
• 9: M. Haenggi. Mobile sensor-actuator networks: Opportunities and challenges. In Proceedings of IEEE International Workshop on Cellular Neural Networks and Their Applications, pages 283--290, 2002.
• 10: G. Kesidis, T. Konstantopoulos, and S. Phoha. Surveillance coverage of sensor networks under a random mobility strategy. In Proceedings of IEEE Sensors, pages 961--965, 2003.
• 11: J. S. Litt, E. Wong, M. J. Krasowski, and L. C. Greer. Cooperative multi-agent mobile sensor platforms for jet engine inspection - Concept and implementation. In Proceedings of International Conference on Integration of Knowledge Intensive Multi-Agent Systems, pages 716--721, 2003.
• 12: T. D. Parsons. Pursuit-evasion in a graph. In Y. Alani and D. R. Lick, editors, Theory and Application of Graphs, pages 426--441. Springer-Verlag, 1976.
• 13: N. Megiddo , S. L. Hakimi , M. R. Garey , D. S. Johnson , C. H. Papadimitriou, The complexity of searching a graph, Journal of the ACM (JACM), v.35 n.1, p.18-44, Jan. 1988 [doi>10.1145/42267.42268]
• 14: J. P. Hespanha, H. J. Kim, and S. Sastry. Multiple-agent probabilistic pursuit-evasion games. In Proceedings of the Conference on Decision and Control, December 1999.
• 15: Theodore Rappaport, Wireless Communications: Principles and Practice, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 16: M. Hata. Empirical formula for propagation loss in land mobile radio service. IEEE Transactions on Vehicular Technology, 29:317--325, Aug. 1980.
• 17: G. R. Grimmett and D. R. Stirzaker. Probability and random processes. Oxford University Press, New York, 2001.
• 18: S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. Srivastava. Coverage problems in wireless ad-hoc sensor networks. In Proc. of INFOCOM, pages 1380--1387, Apr. 2001.
• 19: Thomas Clouqueur , Veradej Phipatanasuphorn , Parameswaran Ramanathan , Kewal K. Saluja, Sensor deployment strategy for detection of targets traversing a region, Mobile Networks and Applications, v.8 n.4, p.453-461, August 2003 [doi>10.1023/A:1024596016427]
• 20: A. Howard, M. Mataric, and G. Sukhatme. Mobile sensor network deployment using potential fields: A distributed, scalable solution to the area coverage problem. In DARS, June 2002.
• 21: Yi Zou , Krishnendu Chakrabarty, Sensor deployment and target localization in distributed sensor networks, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.1, p.61-91, February 2004 [doi>10.1145/972627.972631]
• 22: G. Wang, G. Cao, and T. La Porta. Movement-assisted sensor deployment. In Proc. of INFOCOM, pages 2469--2479, Mar. 2004.
• 23: 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]
• 24: 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]
• 25: M. Rahimi, R. Pon, W. J. Kaiser, G. S. Sukhatme, D. Estrin, and M. Srivastava. Adaptive sampling for environmental robotics. in IEEE Int. Conf. on Robotics and Automation, New Orleans, LA, 2004.
• 26: David J. C. MacKay, Information-based objective functions for active data selection, Neural Computation, v.4 n.4, p.590-604, July 1992 [doi>10.1162/neco.1992.4.4.590]
• 27: R. Nowak, U. Mitra, and R. Willett. Estimating inhomogeneous fields using wireless sensor networks. IEEE Journal on Selected Areas in Communications, pages 999--1006, August 2004.
• 28: R. Willett, A. Martin, and R. Nowak. Backcasting: A new approach to energy conservation in sensor networks. Technical Report TRECE-03-4, University of Wisconsin, 2003.
• 29: K.-C. Wang and P. Ramanathan. Collaborative sensing using sensors of uncoordinated mobility. In DCOSS, pages 293--306, June 2005.
• 30: Philo Juang , Hidekazu Oki , Yong Wang , Margaret Martonosi , Li Shiuan Peh , Daniel Rubenstein, Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with ZebraNet, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Algorithms, Performance, Theory

Keywords:
analytic model, collaborative detection, detection latency, mobile sensor networks