Complexity Results for Wireless Sensor Network Scheduling

Fethi Jarray

.

DOI: 10.4236/wsn.2010.24045                

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.

Keywords

Discrete Tomography, Sensor Scheduling, Combinatorial Optimization

Conflicts of Interest

The authors declare no conflicts of interest.

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.