Target Monitoring inWireless Sensor Networks: A Localized Approach
Kamrul Islam and Selim G. Akl
We consider the following target monitoring problem: Given a set of stationary targets T = {t1, . . . , tm} and a set V = {v1, . . . , vn} of sensors, the target monitoring problem asks for generating a family of subsets of sensors V1, . . . , Vs called monitoring sets, such that each Vi monitors all targets. In doing so, the objective of this problem is to maximize z = s/k, where k = maxvj ∈V |{i : vj ∈ Vi}|. Maximizing z means generating a large number of monitoring sets and minimizing the number of frequencies of a sensor (or node) in these sets. As energy is one of the main issues of wireless sensor networks and sensing consumes energy, maximizing z has a direct impact in prolonging the lifetime of sensor networks. This is because by maximizing z, we distribute the monitoring responsibilities to all sensors as equally as possible and at the same time, reduce the participations of individual nodes in these monitoring sets. Towards achieving this goal, we present a localized algorithm. The algorithm is simple and requires each node to know only its 2-hop neighborhood. Furthermore, nodes do not need to know their geographic positions. In short, the main idea is that each node maintains a record (counter, ID), where counter is the number of previous monitoring sets in which the node has been selected to monitor the targets. To select sensors for the next monitoring set, for each target, the lexicographically smallest sensor covering it, is selected. We provide special instances where the algorithm obtains an optimum result. As a by-product of the algorithm, it is shown that the size of a monitoring set is at most a constant times the size of a minimum monitoring set when the number of targets is a constant.We present extensive simulation results to evaluate the performance of the algorithm in randomly generated graphs.
Keywords: Wireless sensor networks, target monitoring, localized algorithm, monitoring schedule.