Energy-aware scheduling with quality of surveillance guarantee in wireless sensor networks

ABSTRACT

We propose and evaluate an energy-efficient scheduling algorithm for detection of mobile targets in wireless sensor networks. We consider a setting where the sensors are deployed for both road surveillance and mobile target tracking. A typical example would be where some sensors are deployed along the entrance roads of a city to detect the vehicles entering the city and other sensors can wake up and track the vehicles after detection. We show an important relationship between the overall energy consumed by the sensors and the average detection time of a target, both of which are very critical aspects in our problem. To this end, we define the quality of surveillance (QoSv)as the reciprocal value of the average detection time for vehicles. We propose an optimal scheduling algorithm that guarantees the detection of every target with specified QoSv and at the same time minimizes the overall energy consumed by the sensor nodes. By minimizing the energy consumed, we maximize the lifetime of the sensor network. Also, along with the quality of surveillance guarantee, we ensure that no target goes undetected. We theoretically derive the upper bound on the lifetime of the sensor network for a given QoSv guarantee and prove that our method can always achieve this upper bound. Our simulation results validate the claims made on the algorithm optimality and QoSv guarantee.

References

1. S. Meguerdichian and M. Potkonjak,"Low Power 0/1 Coverage and Scheduling Techniques in Sensor Networks", UCLA Technical Report No.030001, January 2003.
2. S. Meguerdichian et al. "Coverage Problems in Wireless Ad-hoc Sensor Networks", IEEE INFOCOM April 2001.
3. J. O'Rourke, "Computational Geometry Column 15", International Journal of Computational Geometry and Applications Vol.2, pp. 215--217,June 1992.
4. C-F. Huang and Y-C. Tseng, "The Coverage Problem in a Wireless Sensor Network", ACM WSNA September 2003.
5. X. Wang et al. "Integrated Coverage and Connectivity Configuration in Wireless Sensor Networks", ACM SENSYS November 2003.
6. B. Chen et al. "Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks", ACM MOBICOM July 2001.
7. H. Zhang and J. C. Hou, "Maintaining Sensing Coverage and Connectivity in Large Sensor Networks", Ad Hoc and Sensor Wireless Networks Vol.1, pp. 89--124 Old City Publishing, Inc., March 2005.
8. S. Shakkottai, R. Srikant and N. Shroff, "Unreliable Sensor Grids: Coverage, Connectivity, and Diameter", IEEE INFOCOM April 2003.
9. T. Yan, T. He, and J. A. Stankovic, "Differentiated Surveillance for Sensor Networks", ACM SENSYS 2003.
10. F. Ye et al. "PEAS: A Robust Energy Conserving Protocol for Long-lived Sensor Networks", IEEE ICDCS May 2003.
11. C. Gui and P. Mohapatra, "Power Conservation and Quality of Surveillance in Target Tracking Sensor Networks", ACM MOBICOM September 2004.
12. S. Kumar, T. Lai and A. Arora, "Barrier Coverage With Wireless Sensors", ACM MOBICOM August 2005.
13. M. H. DeGroot and M. J. Schervish, "Probability and Statistics (3rd Edition)", Addison Wesley October 2001.
14. M. H. MacDougall, "Simulating Computer Systems: Techniques and Tools", MIT Press 1987.
15. J. Jeong, S. Sharafkandi and D. Du, "Energy-Aware Scheduling with Quality of Surveillance Guarantee in Sensor Networks", Technical Report of University of Minnesota No. 06-021, June 2006: http://www.cs.umn.edu/research/technicalreports.php/?page=year&year=2006

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles