Share This Article:

Complexity Results for Wireless Sensor Network Scheduling

Abstract Full-Text HTML Download Download as PDF (Size:224KB) PP. 343-346
DOI: 10.4236/wsn.2010.24045    4,461 Downloads   8,274 Views   Citations
Author(s)    Leave a comment

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.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

F. Jarray, "Complexity Results for Wireless Sensor Network Scheduling," Wireless Sensor Network, Vol. 2 No. 5, 2010, pp. 343-346. doi: 10.4236/wsn.2010.24045.

References

[1] A. Sorokin, N. Boyko, V. Boginski, S. Uryasev and P. M. Pardalos, “Mathematical Programming Techniques for Sensor Networks,” Algorithms, 2009, pp. 565-581.
[2] 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.
[3] C. Wang and L. Xiao, “Sensor Localization in Concave Environments,” ACM Transactions on Sensor Networks, Vol. 4, No. 1, 2008, pp. 1-31.
[4] 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.
[5] 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.
[6] 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.
[7] 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.
[8] 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.
[9] 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.
[10] M. Yavuz and D. Jeffcoat, “Single Sensor Scheduling for Multi-Site Surveillance,” Technical Report, Air Force Research Laboratory, 2007.
[11] 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.
[12] C. Commander, P. Pardalos, V. Ryabchenko and S. Uryasev, “The Wireless Network Jamming Problem,” Journal of Combinatorial Optimization, 2007, pp. 481-498.
[13] 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.
[14] K. Kalpakis, K. Dasgupta and P. Namjoshi, “Efficient Algorithms for Maximum Lifetime Data Gathering and Aggregation in Wireless Sensor Networks,” Computer Networks, Vol. 42, No. 6, 2003, pp. 697-716.
[15] S. Stanczak, M. Wiczanowski and H. Boche, “Theory and Algorithms for Resource Allocation in Wireless Networks,” Lecture Notes in Computer Science, Springer, 2006.
[16] G. Herman and A. Kuba, “Discrete Tomography: Foundations, Algorithms and Applications,” Birkhauser, 1999.
[17] G. Herman and A. Kuba, “Advances in Discrete Tomography and its Applications,” Birkhauser, 2007.
[18] H. J. Ryser, “Combinatorial Properties of Matrices of Zeros and Ones,” Canadian Journal of Mathematics, Vol. 9, 1957, pp. 371-377.
[19] F. Jarray, M.-C. Costa and C. Picouleau, “Complexity Results for the Horizontal Bar Packing Problem,” Information Processing Letters, Vol. 108, No. 6, 2008, pp. 356-359.

  
comments powered by Disqus

Copyright © 2019 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.