Quality of monitoring of stochastic events by periodic & proportional-share scheduling of sensor coverage

ABSTRACT

We analyze the quality of monitoring (QoM) of stochastic events by a periodic sensor which monitors a point of interest (PoI) for q time every p time. We show how the amount of information captured at a PoI is affected by the proportion q/p, the time interval p over which the proportion is achieved, the event type, and the stochastic event arrival dynamics and staying times. The periodic PoI sensor schedule happens in two broad contexts. In the case of static sensors, a sensor monitoring a PoI may be periodically turned off to conserve energy, thereby extending the lifetime of the monitoring until the sensor can be recharged or replaced. In the case of mobile sensors, a sensor may move between the PoIs in a repeating visit schedule. In this case, the PoIs may vary in importance, and the scheduling objective is to distribute the sensor's coverage time in proportion to the importance levels of the PoIs. Based on our QoM analysis, we optimize a class of periodic mobile coverage schedules that can achieve such proportional sharing while maximizing the QoM of the total system.

REFERENCES

• 1: Nabhendra Bisnik , Alhussein Abouzeid , Volkan Isler, Stochastic event capture using mobile sensors subject to a quality metric, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161102]
• 2: V. Cerny. Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal of Optimization Theory and Applications, 45(1), 1985.
• 3: Srijan Chakraborty , Yu Dong , David K. Y. Yau , John C. S. Lui, On the Effectiveness of Movement Prediction to Reduce Energy Consumption in Wireless Communication, IEEE Transactions on Mobile Computing, v.5 n.2, p.157-169, February 2006 [doi>10.1109/TMC.2006.24]
• 4: Himanshu Gupta , Samir R. Das , Quinyi Gu, Connected sensor cover: self-organization of sensor networks for efficient query execution, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778438]
• 5: Bret Hull , Vladimir Bychkovsky , Yang Zhang , Kevin Chen , Michel Goraczko , Allen Miu , Eugene Shih , Hari Balakrishnan , Samuel Madden, CarTel: a distributed mobile sensor computing system, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182821]
• 6: K. Jeffay , F. D. Smith , A. Moorthy , J. Anderson, Proportional Share Scheduling of Operating System Services for Real-Time Applications, Proceedings of the IEEE Real-Time Systems Symposium, p.480, December 02-04, 1998
• 7: S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, New Series, 220(4598): 671--680, May 1983.
• 8: Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks: the single-node case, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.344-357, June 1993 [doi>10.1109/90.234856]
• 9: R. E. Lapp and H. L. Andrews. Nuclear Radiation Physics. Prentice Hall, 1948.
• 10: R. W. Lee and J. J. Kulesz. A risk-based sensor placement methodology. Technical report, Computational Sciences and Engineering Division, ORNL, 2006.
• 11: Will E. Leland , Murad S. Taqqu , Walter Willinger , Daniel V. Wilson, On the self-similar nature of Ethernet traffic, Conference proceedings on Communications architectures, protocols and applications, p.183-193, September 13-17, 1993, San Francisco, California, United States
• 12: S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava. Coverage problems in wireless ad-hoc sensor networks. In IEEE INFOCOM, 2001.
• 13: Wei Wang , Vikram Srinivasan , Kee-Chaing Chua, Using mobile relays to prolong the lifetime of wireless sensor networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080858]
• 14: D. K. Y. Yau, N. K. Yip, C. Y. T. Ma, N. S. Rao, and M. Shankar. Quality of monitoring of stochastic events by proportional-share mobile sensor coverage www.cs.purdue.edu/homes/lans/publications/tr-08-011.pdf. Technical Report 08-011, Purdue University, April 2008.
• 15: H. Zhang and J. C. Hou. Maintaining sensing coverage and connectivity in large sensor networks. Wireless Ad-hoc and Sensor Networks, 1(1--2), January 2005.
• 16: Xiaolan Zhang , Jim Kurose , Brian Neil Levine , Don Towsley , Honggang Zhang, Study of a bus-based disruption-tolerant network: mobility modeling and impact on routing, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287876]
• 17: 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]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Signal processing systems

General Terms:
Design, Experimentation, Measurement, Performance