LAUSR

Abstract Wireless Sensor Networks (WSNs) consist of a set of devices with limited energy capacity, therefore the longevity of the network can be one of the decisive quality parameters of WSNs. We study the problem of WSN lifetime maximization for a model of the network where sensors are randomly deployed over an area to keep watch on a number of points of interest (POI). Although sensors have limited battery capacity, their number is large, and their monitoring ranges overlap. Therefore, not all the sensors have to be active all the time. Moreover, for effective monitoring, it is enough to observe all the time just a required percentage of POIs, not all of them. Our goal is to create a schedule of sensor activity giving the longest possible time of effective monitoring of a given set of POIs. Here, we present three heuristic algorithms for sensors activity scheduling: a random and fine-tuning approach, an approach inspired by cellular automata, and a hypergraph model approach. Since the outcome of these algorithms does not represent optimal solutions and can be further improved, we use the obtained schedules as an input for a local search strategy with problem-specific neighborhood functions. Three versions of schedule perturbation operators are presented. We also propose a suite of benchmark test cases for experimental evaluation of our algorithms and present the results of experiments with heuristic algorithms and local search methods.