Research ArticleOpen AccessGoogle Scholar indexed
Complexity Results for Wireless Sensor Network Scheduling
- 1
Wireless Sensor Network·Volume 02 (2010)·Pages 343–346·Published 27 May 2010·DOI10.4236/wsn.2010.24045
Copy link · social · email
Abstract
We study the problem of scheduling multi sensors to visit and observe a group of sites at discrete time points over a planning horizon of given length. We show that scheduling under a given number of visits for each site and in each period is an NP-complete problem by providing equivalence with a problem in discrete tomography. We also give a polynomial time algorithm to schedule the sensors under a given number of visits in each period.
KeywordsDiscrete TomographySensor SchedulingCombinatorial Optimization
- A. Sorokin, N. Boyko, V. Boginski, S. Uryasev and P. M. Pardalos, “Mathematical Programming Techniques for Sensor Networks,” Algorithms, 2009, pp. 565-581.
- K. Wu, C. Liu, J. Pan and D. Huang, “Robust Range-Free Localization in Wireless Sensor Networks,” Mobile Networks & Applications, Vol. 12, No. 5, 2007, pp. 392-405.
- C. Wang and L. Xiao, “Sensor Localization in Concave Environments,” ACM Transactions on Sensor Networks, Vol. 4, No. 1, 2008, pp. 1-31.
- D. Koutsonikolas, S. M. Das and Y. C. Hu, “Path Planning of Mobile Landmarks for Localization in Wireless Sensor Networks,” Computer Communications, Vol. 30, No. 13, 2007, pp. 2577-2592.
- M. Rudafshani and S. Datta, “Localization in Wireless Sensor Networks,” Proceedings of the 6th International Conference on Information Processing in Sensor Networks, New York, 2007, pp. 51-60.
- J. Jeong, S. Sharafkandi and D. H. C. Du, “Energy-Aware Scheduling with Quality of Surveillance Guarantee in Wireless Sensor Networks,” Proceedings of the 2006 Workshop on Dependability Issues in Wireless Ad Hoc Networks and Sensor Networks, New York, 2006, pp. 55-64.
- K. Wu, Y. Gao, F. Li and Y. Xiao, “Lightweight Deployment-Aware Scheduling for Wireless Sensor Networks,” Mobile Networks & Applications, Vol. 10, No. 6, 2005, pp. 837-852.
- S. S. Singh, N. Kantas, B. N. Vo, A. Doucet and R. J. Evans, “Simulation-Based Optimal Sensor Scheduling with Application to Observer Trajectory Planning,” Automatica, Vol. 43, No. 5, 2007, pp. 817-830.
- Klappenecker, H. Lee and J. L. Welch, “Scheduling Sensors by Tilinglattices,” Proceedings of the 27th ACM Symposium on Principles of Distributed Computing, New York, 2008, pp. 437-437.
- M. Yavuz and D. Jeffcoat, “Single Sensor Scheduling for Multi-Site Surveillance,” Technical Report, Air Force Research Laboratory, 2007.
- M. Yavuz and D. Jeffcoat, “An Analysis and Solution of the Sensor Scheduling Problem,” In Proceedings of the 7th International Conference on Cooperative Control and Optimization, Gainesville, 2007.
- C. Commander, P. Pardalos, V. Ryabchenko and S. Uryasev, “The Wireless Network Jamming Problem,” Journal of Combinatorial Optimization, 2007, pp. 481-498.
- C. Commander, P. Pardalos, V. Ryabchenko, S. Sarykalin, T. Turko and S. Uryasev, “Robust Wireless Network Jamming Problems,” Lecture Notes in Control and Information Sciences, Springer, 2008.