Paper Menu >>
Journal Menu >>
![]() Wireless Sensor Network, 2010, 2, 343-346 doi:10.4236/wsn.2010.24045 Published Online May 2010 (http://www.SciRP.org/journal/wsn) Copyright © 2010 SciRes. WSN Complexity Results for Wireless Sensor Network Scheduling Fethi Jarray Laboratoire Cédric, Paris, France Gabes University of Sciences, Gabes, Tunisia Al-Imam Mohamed Ibn Saoud University, Riyadh, Saudi Arabia E-mail: Fethi.jarray@cnam.fr Received January 31, 2010; revised February 22, 2010; accepted Febr uary 23, 2010 Abstract We study the problem of scheduling multiple 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 vis- its in each period. Keywords: Discrete Tomography, Sensor Scheduling, Combinatorial Optimization 1. Introduction A wireless sensor is a small physical device having a battery with a limited capacity and having a transmission, a reception capability of limited range and capable to take various measurements of its neighborhood. These measurements include temperature, acoustic, solar radia- tion, etc. Since a single sensor is not able to monitor a hole field, a group of sensors should be deployed and frequently interact with each other to exchange informa- tion. This group of distributed sensors forms the wireless sensor networks (WSN). Generally, the basic goal of a WSN is to ensure the surveillan ce of a given region with a limited number of sensors and eventually transmit the sensed data to a processing unit. The management and the organization of WSN have been investigated by many researchers. Depending on the application and the goal of researchers, several com- binatorial optimization models and solution techniques have been proposed [1]. These models and problems include, among others, sensor localization and tracking [2-5], sensor scheduling [6-11] communication neutrali- zation [12,13] and energy consumption [14,15]. There are a wide variety of methods and models because on one had several issues are considered in WSN. On the other hand, the most addressed problems are NP-com- plete, i.e., there is no polynomial time algorithm to solves these problems unless P = NP. This paper is concerned with WSN scheduling to pe- riodically monitor and observe an environment. WSN scheduling is needed in various applications such as traf- fic monitoring at roads, military, medical, pollution de- tection, etc. In this paper, we show the complexity results of WSN scheduling by supposing that the number of required visits for each period are given. We will use a reduction from an independent problem of discrete to- mography. For clarity, the next section is devoted to the area of discre t e tomog raphy. The remainder of this paper is organized as follows. In Section 2, the problem of discrete tomography and bi- nary matrices reconstruction will be presented. In Sec- tion 3, Sensor scheduling with a given numbers of visits per period and per site will be studied. In Section 4, sen- sor scheduling with a given numbers of visits per period is addressed. 2. Discrete Tomography Discrete Tomography (DT) is an emergent area of com- puter science (refer to the books of Hermann and Kuba [16,17] for further information on the theory, algorithms and applications). It deals with the reconstruction of bi- nary matrices and images from horizontal and vertical projections. Let A be a binary matrix of size m × n, we denote by the number of ones on row i and by 1 n i j hA 1 m ij j ij i vA the number of ones on column j. ![]() F. JARRAY 344 The vectors 1,, m H hh and are called the horizontal and the vertical projection respec- tively. The problem of reconstructing a binary matrix from orthogonal projections, denoted MB(H,V), is de- fined as follows: given two vectors H and V, we search to reconstruct a binary matrix consistent with these pro- jections or to report that such a matrix does not exist. It is well known that this problem is polynomial [18] (Figure 1). However, it becomes NP-complete by imposing a maximal length of sequence of zeros between the con- secutive ones [19], i.e., we impose a maximal number of zeros between two consecutive ones. 1,, n Vv v i 3. WSN Scheduling with Given Number of Visits per Period and Site SSHV(a,b) We consider the following problem SSHV(a, b) of sen- sors scheduling. There are m sites to observe , s i , a set of m sensors and a scheduling horizon (interval) T composed of n periods 1,...,m 1,...,Tn ,; ; ij . During period tj of the time interval T, exactly vj sites should be observed by vj sensors. Each site si, should be observed during hi periods. When site si is not observed at period tj, a non visiting penalty aij is incurred and an information loss penalty bijlij is also incurred. We suppo se that aij and bij are given non negative and lij is the number of elapsed periods since last visiting site si. Note that the informa- tion loss penalty is p roportional to the time in terval when the site is not observed . The problem now is to determine a surveillance schedule, i.e., to decide for each period which site to observe minimizing the maximum non vis- iting penalties and information loss penalties. The problem SSHV(a,b) can be reformulated as a mixed integer linear program inspired from [11]. We introduce the binary decision variables xij and the real variables yij such that xij = 1 and if the site si is observed at time slot j. The real variable yij represents the last time ,- 1 1j , , 0, ,; 1 , ij ijij j i i jij ij ij x by xv j hi yy jx jij yi xyR 1 1 1 min .. 0, 0, ij m ij i n ij j ij ij i ij C st Ca Px ij jx y v j h i Figure 1. A binary matr ix with horizontal project ion H = (2, 2, 5, 3) and vertical projection V = (3, 1, 3, 1, 4); maximal length of sequences of zeros is 3. where site si was observed before period j. This gives us the following MIP model: The constraint (1) ensures that the objective function (C) consists in minimizing the maximum penalty. The constraint (2) ensures that in each period tj there are vj visited sites. The constraints (3) ensure that each site si is visited in hi periods. Constraints (4) and (5) together en- sure that yij is modified only if site si is visite d (xij = 1) and takes the value j. Constraint (6) implies that all the sites are not obs erved bef or e the firs t period. A solution to the problem SSHV(a,b) will be pre- sented by an m × n binary matrix A such that aij = 1 only if site si is visited at period tj. Consider the subproblem SSHV(0,1) with aij = 0 and bij = 1 for all the sites over all the periods. Thus for each couple of site and period (si,tj) the total penalty is (j-yij) which is the number of consecutive non visiting periods before time slot tj. If we consider the schedule as a binary matrix, the total penalty is exactly the length of the se- quence of zeros before the entry (i,j). Hence the sub- problem SSHV(0,1) is equivalent to reconstructing a binary matrix with horizontal projection H and vertical projection V and minimizing the length of the longest sequence of zeros which is NP-complete ( see Section 2). So the general problem SSHV(a,b) is also NP-complete. Proposition 1 (1) The problem SSHV(a,b) is NP-complete. (2) 4. WSN Scheduling with a Given Number of Visits per Period (3) (4) In this scheduling problem, we search for a sensor sche- duling respecting the periodically numbers of visits, i.e., in period j there are vj visits while minimizing the maxi- mal penalty. The problem SSV(a,b) can be considered as a relaxation of the problem SSHV(a,b) where the number of visits for each site is omitted. Yavuz and Jeffcoat [11] studied an NP-complete problem very close to SSV(a,b). (5) (6) Copyright © 2010 SciRes. WSN ![]() F. JARRAY345 They supposed that in each period, at most m sites was observed instead of exactly vj sites as in SSV(a,b). In this section, we show that the problem SSV(0,1) can be solved by a polynomial time a lgorithm. As in the previous section, a solution to the problem SSV(0,1) will be presented by an m × n binary matrix A such that aij = 1 only if site si is visited at period tj. Thus solving SSV(0,1) with vector of visits V is equivalent to reconstructing a binary matrix m × n respecting the ver- tical projection V and minimizing the maximal distance. We recall that the distance is the length of a sequ ence of consecutive zeros. We propose the following cyclic al- gorithm to solve SSV(0,1) where the rows are associated to the sites and the columns are associated to the periods. Algorithm A-SSV Assign a number from 1 to m to each site Assign the visits on column 1 to the first v1 rows Assign the visits on column 2 to the next v2 rows This process is continued cyclically with row 1 being treated as the next row after row m. We state the following result: Proposition 2 The algorithm A-SSV solves SSV(0,1) in O(mn). Proof The algorithm A-SSV provides a solution S* respecting the vertical projection since at each step j vj ones are assigned to the rows. Let us show that S* minimizes the maximal distance. Suppose that in S*, the maximal distance is reached be- tween two 1s placed on cells (i,j) and (i,j') with j < j'. Since on row i, there is no 1 placed between columns j + 1 and j' – 1 then . If S* is not optimal then there exists a so lution S with a maximal distance les s than that of S*. On each row of S, there is at least an 1 placed between columns j + 1 and j' – 1. Hence , contrary with . 1j k kj vm 1j k kj vm 1j k kj vm Note that in both addressed problems SSV(0,1) and SSHV(a,b), once the schedule is established, the visits should be cyclically assigned to the sensors to improve the lifetime of WSN. 5. Conclusions In this paper, we have studied the wireless sensor net- work scheduling problem. We have proved that schedul- ing with a given number of visits for each site and each period with a minimum maximal penalty is an NP-com- plete problem. We have also proposed a polynomial time algorithm to schedule sensors under only a given number of visits for each period. The problems studied in this paper belong to a rich and relatively unexplored area. Investigating the problems under more real constraints and designing heuristic to solve the hard problems are possible research directions. 6. References [1] A. Sorokin, N. Boyko, V. Boginski, S. Uryasev and P. M. Pardalos, “Mathematical Programming Techniques for Sensor Networks,” Algorithms, Vol. 2, 2009, pp. 565-581. [2] K. Wu, C. Liu, J. Pan and D. Huang, “Robust Range-Free Localization in Wireless Sensor Networks,” Mobile Net- works & 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 Plan- ning 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 Net- works, New York, 25 April 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, 25 September 2006, pp. 55-64. [7] K. Wu, Y. Gao, F. Li and Y. Xiao, “Lightweight De- ployment-Aware Scheduling for Wireless Sensor Net- works,” 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,” Au- tomatica, Vol. 43, No. 5, 2007, pp. 817-830. [9] Klappenecker, H. Lee and J. L. Welch, “Scheduling Sen- sors by Tilinglattices,” Proceedings of the 27th ACM Symposium on Principles of Distributed Computing, New York, 11 June 2008, pp. 437-437. [10] M. Yavuz and D. Jeffcoat, “Single Sensor Scheduling for Multi-Site Surveillance,” Technical Report, Air Force Research Laboratory, Maui, 2007. [11] M. Yavuz and D. Jeffcoat, “An Analysis and Solution of the Sensor Scheduling Problem,” Proceedings of the 7th International Conference on Cooperative Control and Optimization, Gainesville, 31 January-2 February 2007. [12] C. Commander, P. Pardalos, V. Ryabchenko and S. Uryasev, “The Wireless Network Jamming Problem,” Journal of Combinatorial Optimization, Vol. 14, No. 1, 2007, pp. 481-498. [13] C. Commander, P. Pardalos, V. Ryabchenko, S. Sarykalin, Copyright © 2010 SciRes. WSN ![]() F. JARRAY Copyright © 2010 SciRes. WSN 346 T. Turko and S. Uryasev, “Robust Wireless Network Jamming Problems,” Lecture Notes in Control and In- formation Sciences, Springer, Berlin, 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 Net- works,” Lecture Notes in Computer Science, Springer, Ber- lin, 2006. [16] G. Herman and A. Kuba, “Discrete Tomography: Foun- dations, Algorithms and Applications,” Applied and Nu- merical Harmonic Analysis, Birkhäuser, Boston, 1999. [17] G. Herman and A. Kuba, “Advances in Discrete Tomo- graphy and its Applications,” Applied and Numerical Har- monic Analysis, Birkhäuser, Boston, 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,” Infor- mation Processing Letters, Vol. 108, No. 6, 2008, pp. 356-359. |