LAUSR

Abstract In this work, we investigate the problem of lifetime optimization for partial coverage in heterogeneous sensor networks. This problem which is NP-Hard in its general form is known under the name of α-coverage, where α refers to a prescribed level of coverage threshold that we need to maintain. Sleep-Awake scheduling which turns sensors to On and Off, is the common and the well known technique that has been heavily studied in the literature to deal with energy management under coverage constraint. The question is how to orchestrate the clustering of the sensor nodes into disjoint or non-disjoint covers, and to schedule these covers, so that the total network’s lifetime is maximized. Unlike earlier works, we consider both global (whole targets) resp. local (individual target) monitoring thresholds to improve the coverage quality rather than dealing with a single global leveling threshold as in the literature. In addition, instead of employing a default covers’ activation which may lead to the starvation phenomenon, where targets may remain uncovered for a long time period, we provide a clairvoyant scheduling for the obtained covers to ensure fair smoothing for the cumulated target’s uncovered time periods during the network’s service. First, a novel mathematical Binary Integer Linear Programming (BILP) is proposed to solve the α-coverage problem to optimality. Then, provable guarantees of the upper bound for the number of partial cover sets are given. Next, we formulate the covers’ planning as a p-dispersion problem and due to the NP-Completeness of the former, an efficient Genetic Algorithm (GA) based approach is designed to achieve efficient covers’ scheduling with minimal execution time complexity. Finally, a series of experiments are conducted and several QoS metrics are evaluated to show the usefulness of our proposals.