Abstract
A wireless sensor network (WSN) consists of one or more wireless data collectors and many autonomous sensors to monitor physical phenomena or collect environmental information. Each sensor usually uses a battery to enable its function, which limits its lifetime. In order to prolong the lifetime of WSNs, it is important to schedule the sensors to be activated in WSNs, which is called the wireless sensor network scheduling problem. The WSN scheduling problem is described as follows: Given a set of sensors, and a set of regions to be monitored, each region can be monitored by a subset of the sensors, and a sensor also can monitor more than one region. In order to prolong the lifetime of WSN, we decompose the sensors into disjoint subsets such that every subset of sensors needs to monitor all the regions, i.e. activating a subset of sensors to observe all the regions in each time slot, and the number of times slots (i.e. the number of subsets of sensors), that is, the lifetime of the WSN, is maximized. We investigate the WSN scheduling problem in two different models, and provide several polynomial time algorithms for approximating this problem. When the monitored range of each sensor is the same, i.e. the distance r, and the distance between any two regions is at least √3 r+ε, we present a 3/4 -ratio approximation algorithm to solve the WSN scheduling problem. In addition, when every monitored region is represented by a closed area, and each sensor can monitor at most three regions, we provide a 3/8 -ratio approximation algorithm to solve this model. Moreover, we also can identify critical sensors of WSNs; a sensor is called critical if the lifetime of WSNs must decrease when the sensor is broken. The identification of critical sensors can assist the reliability analysis of wireless sensor networks.