A Subset-Based Coverage-Preserving Distributed Scheduling Algorithm

Recent research has found that management of node duty circles, termed sensor scheduling, is able to save significant energy and prolong the lifetime of sensor networks. Sensor scheduling schemes could be categorized into two types in terms of scheduling features: round-based scheduling scheme and subset-based scheduling scheme respectively. Compared with round-based scheduling scheme, subset-based scheduling scheme is an effective solution because it is only carried out once after deployment. When sensor nodes are randomly deployed to a target region, existing subset-based scheduling algorithms can not guarantee that any subset of sensor nodes is uniformly distributed over the target region. Motivated by these reasons, firstly a maximum similarity distribution model is set up and an approximation algorithm, the subset-based coverage-preserving distributed scheduling algorithm is proposed. The algorithm is robust to clock asynchrony of nodes in different clusters, hence it is applicable to large-scale sensor networks, for which precise time synchronization is very hard. In addition, the analytical results for the theoretical upper bound of average coverage rate are presented, while nodes are randomly distributed over the target region. The experimental simulations demonstrate that this algorithm has the ability that sensor nodes in each subset are rather uniformly distributed over the target area, and available coverage rate approaches the upper bound.