Mathematical models and algorithms for the maximum lifetime coverage problems in wireless sensor networks

Abstract

Due to the recent advances in digital technology, developments of low-cost and multi-functional sensors become possible. When a large number of sensors collaborate using wireless communication, they constitute wireless sensor network. Although wireless sensor network has many applications, it has limited lifetime due to the limited amount of power equipped in each sensor, and replacing the battery is impractical in many applications. Therefore, one of the important design issues in the network is how to use the energy efficiently to extend the network lifetime for performing the sensing and communication tasks. To monitor a set of targets with known hostile locations, we can spread a large population of sensors in the proximity of the targets instead of positioning them in precise locations. This increases the network density, thus the sensing area of some sensors may overlap. Now we can schedule the sensors` activities such as to allow the redundant sensors to enter the sleep state and save energy for future use. Let the set of sensors which can perform the monitoring task independently as an active set. To maximize the network lifetime, it is critical to rotate the roles of the active set among the sensors in the network. Thus, at any time, only one set of sensors belong to one active set are asked to be active, instead of all the network sensors. Generally, we use a graph to represent the network. Each sensor of the network is represented as a vertex and there exists an edge between two vertices if and only if two vertices are located within a communication range. A dominating set is a subset of vertices such that each vertex of the graph is either in the dominating set or has a neighbor in the dominating set. Now an active set in the network equivalent to the dominating set in a graph. In this thesis, we consider several optimization problems to extend the network lifetime in wireless sensor network . First, we consider the maximum disjoint set covers...