Modeling and Solving of Sensor Network Lifetime Problem with Coverage Model

Abstract

Aiming at the sensor network lifetime problem (SNLP), a sensor network coverage model and its data structure are proposed, and the problem is equivalent to its dual problem, namely minimum weight sensor coverage problem. Firstly, SNLP is constructed as a package linear programming. After finding different sensor coverage satisfying sensor network constraints, the sensor network life is maximized by allocating time for each sensor coverage. Secondly, for solving SNLP, three centralized solving methods are proposed, which are based on Garg-Konemann algorithm, greedy algorithm considering partial sensor coverage and constant approximation algorithm considering communication cost. At the same time, a distributed solving method based on global reshuffle is pro-posed. The reshuffle is triggered when the initial energy supply of a sensor drops to a certain predefined threshold value H among active, idle and intermediate vulnerable states, thus the sensor network lifetime is improved by using smart self-organizing monitoring schedules. Simulation results show that the proposed SNLP, which is based on sensor network coverage model and data structure, and its solving method can achieve preferable running time, network life and network overhead.

Keywords

• |sensor network lifetime|energy consumption|coverage|packing linear programming|approximation algorithm|distributed protocols